Update ANGLE
[WebKit-https.git] / Source / WebCore / css / parser / SizesCalcParser.cpp
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
37 namespace WebCore {
38
39 SizesCalcParser::SizesCalcParser(CSSParserTokenRange range, const Document& document)
40     : m_result(0)
41     , m_document(document)
42 {
43     m_isValid = calcToReversePolishNotation(range) && calculate();
44 }
45
46 float SizesCalcParser::result() const
47 {
48     ASSERT(m_isValid);
49     return m_result;
50 }
51
52 static 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
63 bool 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
88 void SizesCalcParser::appendNumber(const CSSParserToken& token)
89 {
90     SizesCalcValue value;
91     value.value = token.numericValue();
92     m_valueList.append(value);
93 }
94
95 bool 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
105 void SizesCalcParser::appendOperator(const CSSParserToken& token)
106 {
107     SizesCalcValue value;
108     value.operation = token.delimiter();
109     m_valueList.append(value);
110 }
111
112 bool 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
202 static 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
241 bool 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