src/third_party/WebKit/Source/core/css/parser/SizesCalcParser.cpp

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