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