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 blink { 12 SizesCalcParser(MediaQueryTokenIterator start,MediaQueryTokenIterator end,PassRefPtr<MediaValues> mediaValues)13 SizesCalcParser::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 result() const21 unsigned SizesCalcParser::result() const 22 { 23 ASSERT(m_isValid); 24 return m_result; 25 } 26 operatorPriority(UChar cc,bool & highPriority)27 static 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 handleOperator(Vector<MediaQueryToken> & stack,const MediaQueryToken & token)38 bool 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 appendNumber(const MediaQueryToken & token)63 void SizesCalcParser::appendNumber(const MediaQueryToken& token) 64 { 65 SizesCalcValue value; 66 value.value = token.numericValue(); 67 m_valueList.append(value); 68 } 69 appendLength(const MediaQueryToken & token)70 bool 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 appendOperator(const MediaQueryToken & token)82 void SizesCalcParser::appendOperator(const MediaQueryToken& token) 83 { 84 SizesCalcValue value; 85 value.operation = token.delimiter(); 86 m_valueList.append(value); 87 } 88 calcToReversePolishNotation(MediaQueryTokenIterator start,MediaQueryTokenIterator end)89 bool 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 operateOnStack(Vector<SizesCalcValue> & stack,UChar operation)164 static 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 calculate()203 bool 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