1// Copyright 2014 The Chromium Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style license that can be
3// found in the LICENSE file.
4
5#include "config.h"
6#include "core/css/parser/SizesCalcParser.h"
7
8#include "core/css/MediaValues.h"
9#include "core/css/parser/MediaQueryToken.h"
10
11namespace blink {
12
13SizesCalcParser::SizesCalcParser(MediaQueryTokenIterator start, MediaQueryTokenIterator end, PassRefPtr<MediaValues> mediaValues)
14    : m_mediaValues(mediaValues)
15    , m_viewportDependant(false)
16    , m_result(0)
17{
18    m_isValid = calcToReversePolishNotation(start, end) && calculate();
19}
20
21unsigned SizesCalcParser::result() const
22{
23    ASSERT(m_isValid);
24    return m_result;
25}
26
27static bool operatorPriority(UChar cc, bool& highPriority)
28{
29    if (cc == '+' || cc == '-')
30        highPriority = false;
31    else if (cc == '*' || cc == '/')
32        highPriority = true;
33    else
34        return false;
35    return true;
36}
37
38bool SizesCalcParser::handleOperator(Vector<MediaQueryToken>& stack, const MediaQueryToken& token)
39{
40    // If the token is an operator, o1, then:
41    // while there is an operator token, o2, at the top of the stack, and
42    // either o1 is left-associative and its precedence is equal to that of o2,
43    // or o1 has precedence less than that of o2,
44    // pop o2 off the stack, onto the output queue;
45    // push o1 onto the stack.
46    bool stackOperatorPriority;
47    bool incomingOperatorPriority;
48
49    if (!operatorPriority(token.delimiter(), incomingOperatorPriority))
50        return false;
51    if (!stack.isEmpty() && stack.last().type() == DelimiterToken) {
52        if (!operatorPriority(stack.last().delimiter(), stackOperatorPriority))
53            return false;
54        if (!incomingOperatorPriority || stackOperatorPriority) {
55            appendOperator(stack.last());
56            stack.removeLast();
57        }
58    }
59    stack.append(token);
60    return true;
61}
62
63void SizesCalcParser::appendNumber(const MediaQueryToken& token)
64{
65    SizesCalcValue value;
66    value.value = token.numericValue();
67    m_valueList.append(value);
68}
69
70bool SizesCalcParser::appendLength(const MediaQueryToken& token)
71{
72    SizesCalcValue value;
73    double result = 0;
74    if (!m_mediaValues->computeLength(token.numericValue(), token.unitType(), result))
75        return false;
76    value.value = result;
77    value.isLength = true;
78    m_valueList.append(value);
79    return true;
80}
81
82void SizesCalcParser::appendOperator(const MediaQueryToken& token)
83{
84    SizesCalcValue value;
85    value.operation = token.delimiter();
86    m_valueList.append(value);
87}
88
89bool SizesCalcParser::calcToReversePolishNotation(MediaQueryTokenIterator start, MediaQueryTokenIterator end)
90{
91    // This method implements the shunting yard algorithm, to turn the calc syntax into a reverse polish notation.
92    // http://en.wikipedia.org/wiki/Shunting-yard_algorithm
93
94    Vector<MediaQueryToken> stack;
95    for (MediaQueryTokenIterator it = start; it != end; ++it) {
96        MediaQueryTokenType type = it->type();
97        switch (type) {
98        case NumberToken:
99            appendNumber(*it);
100            break;
101        case DimensionToken:
102            m_viewportDependant = m_viewportDependant || CSSPrimitiveValue::isViewportPercentageLength(it->unitType());
103            if (!CSSPrimitiveValue::isLength(it->unitType()) || !appendLength(*it))
104                return false;
105            break;
106        case DelimiterToken:
107            if (!handleOperator(stack, *it))
108                return false;
109            break;
110        case FunctionToken:
111            if (it->value() != "calc")
112                return false;
113            // "calc(" is the same as "("
114        case LeftParenthesisToken:
115            // If the token is a left parenthesis, then push it onto the stack.
116            stack.append(*it);
117            break;
118        case RightParenthesisToken:
119            // If the token is a right parenthesis:
120            // Until the token at the top of the stack is a left parenthesis, pop operators off the stack onto the output queue.
121            while (!stack.isEmpty() && stack.last().type() != LeftParenthesisToken && stack.last().type() != FunctionToken) {
122                appendOperator(stack.last());
123                stack.removeLast();
124            }
125            // If the stack runs out without finding a left parenthesis, then there are mismatched parentheses.
126            if (stack.isEmpty())
127                return false;
128            // Pop the left parenthesis from the stack, but not onto the output queue.
129            stack.removeLast();
130            break;
131        case CommentToken:
132        case WhitespaceToken:
133        case EOFToken:
134            break;
135        case PercentageToken:
136        case IdentToken:
137        case CommaToken:
138        case ColonToken:
139        case SemicolonToken:
140        case LeftBraceToken:
141        case LeftBracketToken:
142        case RightBraceToken:
143        case RightBracketToken:
144        case StringToken:
145        case BadStringToken:
146            return false;
147        }
148    }
149
150    // When there are no more tokens to read:
151    // While there are still operator tokens in the stack:
152    while (!stack.isEmpty()) {
153        // If the operator token on the top of the stack is a parenthesis, then there are mismatched parentheses.
154        MediaQueryTokenType type = stack.last().type();
155        if (type == LeftParenthesisToken || type == FunctionToken)
156            return false;
157        // Pop the operator onto the output queue.
158        appendOperator(stack.last());
159        stack.removeLast();
160    }
161    return true;
162}
163
164static bool operateOnStack(Vector<SizesCalcValue>& stack, UChar operation)
165{
166    if (stack.size() < 2)
167        return false;
168    SizesCalcValue rightOperand = stack.last();
169    stack.removeLast();
170    SizesCalcValue leftOperand = stack.last();
171    stack.removeLast();
172    bool isLength;
173    switch (operation) {
174    case '+':
175        if (rightOperand.isLength != leftOperand.isLength)
176            return false;
177        isLength = (rightOperand.isLength && leftOperand.isLength);
178        stack.append(SizesCalcValue(leftOperand.value + rightOperand.value, isLength));
179        break;
180    case '-':
181        if (rightOperand.isLength != leftOperand.isLength)
182            return false;
183        isLength = (rightOperand.isLength && leftOperand.isLength);
184        stack.append(SizesCalcValue(leftOperand.value - rightOperand.value, isLength));
185        break;
186    case '*':
187        if (rightOperand.isLength && leftOperand.isLength)
188            return false;
189        isLength = (rightOperand.isLength || leftOperand.isLength);
190        stack.append(SizesCalcValue(leftOperand.value * rightOperand.value, isLength));
191        break;
192    case '/':
193        if (rightOperand.isLength || rightOperand.value == 0)
194            return false;
195        stack.append(SizesCalcValue(leftOperand.value / rightOperand.value, leftOperand.isLength));
196        break;
197    default:
198        return false;
199    }
200    return true;
201}
202
203bool SizesCalcParser::calculate()
204{
205    Vector<SizesCalcValue> stack;
206    for (Vector<SizesCalcValue>::iterator it = m_valueList.begin(); it != m_valueList.end(); ++it) {
207        if (it->operation == 0) {
208            stack.append(*it);
209        } else {
210            if (!operateOnStack(stack, it->operation))
211                return false;
212        }
213    }
214    if (stack.size() == 1 && stack.last().isLength) {
215        m_result = clampTo<unsigned>(stack.last().value);
216        return true;
217    }
218    return false;
219}
220
221} // namespace blink
222