1// Copyright 2014 The Chromium Authors. All rights reserved.
2// Copyright (C) 2016 Apple Inc. All rights reserved.
3//
4// Redistribution and use in source and binary forms, with or without
5// modification, are permitted provided that the following conditions are
6// met:
7//
8// * Redistributions of source code must retain the above copyright
9// notice, this list of conditions and the following disclaimer.
10// * Redistributions in binary form must reproduce the above
11// copyright notice, this list of conditions and the following disclaimer
12// in the documentation and/or other materials provided with the
13// distribution.
14// * Neither the name of Google Inc. nor the names of its
15// contributors may be used to endorse or promote products derived from
16// this software without specific prior written permission.
17//
18// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29
30#include "config.h"
31#include "SizesCalcParser.h"
32
33#include "CSSParserToken.h"
34#include "RenderView.h"
35#include "SizesAttributeParser.h"
36
37namespace WebCore {
38
39SizesCalcParser::SizesCalcParser(CSSParserTokenRange range, const Document& document)
40 : m_result(0)
41 , m_document(document)
42{
43 m_isValid = calcToReversePolishNotation(range) && calculate();
44}
45
46float SizesCalcParser::result() const
47{
48 ASSERT(m_isValid);
49 return m_result;
50}
51
52static bool operatorPriority(UChar cc, bool& highPriority)
53{
54 if (cc == '+' || cc == '-')
55 highPriority = false;
56 else if (cc == '*' || cc == '/')
57 highPriority = true;
58 else
59 return false;
60 return true;
61}
62
63bool SizesCalcParser::handleOperator(Vector<CSSParserToken>& stack, const CSSParserToken& token)
64{
65 // If the token is an operator, o1, then:
66 // while there is an operator token, o2, at the top of the stack, and
67 // either o1 is left-associative and its precedence is equal to that of o2,
68 // or o1 has precedence less than that of o2,
69 // pop o2 off the stack, onto the output queue;
70 // push o1 onto the stack.
71 bool stackOperatorPriority;
72 bool incomingOperatorPriority;
73
74 if (!operatorPriority(token.delimiter(), incomingOperatorPriority))
75 return false;
76 if (!stack.isEmpty() && stack.last().type() == DelimiterToken) {
77 if (!operatorPriority(stack.last().delimiter(), stackOperatorPriority))
78 return false;
79 if (!incomingOperatorPriority || stackOperatorPriority) {
80 appendOperator(stack.last());
81 stack.removeLast();
82 }
83 }
84 stack.append(token);
85 return true;
86}
87
88void SizesCalcParser::appendNumber(const CSSParserToken& token)
89{
90 SizesCalcValue value;
91 value.value = token.numericValue();
92 m_valueList.append(value);
93}
94
95bool SizesCalcParser::appendLength(const CSSParserToken& token)
96{
97 SizesCalcValue value;
98 double result = SizesAttributeParser::computeLength(token.numericValue(), token.unitType(), m_document);
99 value.value = result;
100 value.isLength = true;
101 m_valueList.append(value);
102 return true;
103}
104
105void SizesCalcParser::appendOperator(const CSSParserToken& token)
106{
107 SizesCalcValue value;
108 value.operation = token.delimiter();
109 m_valueList.append(value);
110}
111
112bool SizesCalcParser::calcToReversePolishNotation(CSSParserTokenRange range)
113{
114 // This method implements the shunting yard algorithm, to turn the calc syntax into a reverse polish notation.
115 // http://en.wikipedia.org/wiki/Shunting-yard_algorithm
116
117 Vector<CSSParserToken> stack;
118 while (!range.atEnd()) {
119 const CSSParserToken& token = range.consume();
120 switch (token.type()) {
121 case NumberToken:
122 appendNumber(token);
123 break;
124 case DimensionToken:
125 if (!CSSPrimitiveValue::isLength(token.unitType()) || !appendLength(token))
126 return false;
127 break;
128 case DelimiterToken:
129 if (!handleOperator(stack, token))
130 return false;
131 break;
132 case FunctionToken:
133 if (!equalIgnoringASCIICase(token.value(), "calc"))
134 return false;
135 // "calc(" is the same as "("
136 FALLTHROUGH;
137 case LeftParenthesisToken:
138 // If the token is a left parenthesis, then push it onto the stack.
139 stack.append(token);
140 break;
141 case RightParenthesisToken:
142 // If the token is a right parenthesis:
143 // Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue.
144 while (!stack.isEmpty() && stack.last().type() != LeftParenthesisToken && stack.last().type() != FunctionToken) {
145 appendOperator(stack.last());
146 stack.removeLast();
147 }
148 // If the stack runs out without finding a left parenthesis, then there are mismatched parentheses.
149 if (stack.isEmpty())
150 return false;
151 // Pop the left parenthesis from the stack, but not onto the output queue.
152 stack.removeLast();
153 break;
154 case WhitespaceToken:
155 case EOFToken:
156 break;
157 case CDOToken:
158 case CDCToken:
159 case AtKeywordToken:
160 case HashToken:
161 case UrlToken:
162 case BadUrlToken:
163 case PercentageToken:
164 case IncludeMatchToken:
165 case DashMatchToken:
166 case PrefixMatchToken:
167 case SuffixMatchToken:
168 case SubstringMatchToken:
169 case ColumnToken:
170 case UnicodeRangeToken:
171 case IdentToken:
172 case CommaToken:
173 case ColonToken:
174 case SemicolonToken:
175 case LeftBraceToken:
176 case LeftBracketToken:
177 case RightBraceToken:
178 case RightBracketToken:
179 case StringToken:
180 case BadStringToken:
181 return false;
182 case CommentToken:
183 ASSERT_NOT_REACHED();
184 return false;
185 }
186 }
187
188 // When there are no more tokens to read:
189 // While there are still operator tokens in the stack:
190 while (!stack.isEmpty()) {
191 // If the operator token on the top of the stack is a parenthesis, then there are mismatched parentheses.
192 CSSParserTokenType type = stack.last().type();
193 if (type == LeftParenthesisToken || type == FunctionToken)
194 return false;
195 // Pop the operator onto the output queue.
196 appendOperator(stack.last());
197 stack.removeLast();
198 }
199 return true;
200}
201
202static bool operateOnStack(Vector<SizesCalcValue>& stack, UChar operation)
203{
204 if (stack.size() < 2)
205 return false;
206 SizesCalcValue rightOperand = stack.last();
207 stack.removeLast();
208 SizesCalcValue leftOperand = stack.last();
209 stack.removeLast();
210 bool isLength;
211 switch (operation) {
212 case '+':
213 if (rightOperand.isLength != leftOperand.isLength)
214 return false;
215 isLength = (rightOperand.isLength && leftOperand.isLength);
216 stack.append(SizesCalcValue(leftOperand.value + rightOperand.value, isLength));
217 break;
218 case '-':
219 if (rightOperand.isLength != leftOperand.isLength)
220 return false;
221 isLength = (rightOperand.isLength && leftOperand.isLength);
222 stack.append(SizesCalcValue(leftOperand.value - rightOperand.value, isLength));
223 break;
224 case '*':
225 if (rightOperand.isLength && leftOperand.isLength)
226 return false;
227 isLength = (rightOperand.isLength || leftOperand.isLength);
228 stack.append(SizesCalcValue(leftOperand.value * rightOperand.value, isLength));
229 break;
230 case '/':
231 if (rightOperand.isLength || !rightOperand.value)
232 return false;
233 stack.append(SizesCalcValue(leftOperand.value / rightOperand.value, leftOperand.isLength));
234 break;
235 default:
236 return false;
237 }
238 return true;
239}
240
241bool SizesCalcParser::calculate()
242{
243 Vector<SizesCalcValue> stack;
244 for (const auto& value : m_valueList) {
245 if (!value.operation)
246 stack.append(value);
247 else {
248 if (!operateOnStack(stack, value.operation))
249 return false;
250 }
251 }
252 if (stack.size() == 1 && stack.last().isLength) {
253 m_result = std::max(clampTo<float>(stack.last().value), (float)0.0);
254 return true;
255 }
256 return false;
257}
258
259} // namespace WebCore
260