1/*
2 * Copyright (C) 2011, 2012 Google 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
31#include "config.h"
32#include "core/css/CSSCalculationValue.h"
33
34#include "core/css/CSSPrimitiveValueMappings.h"
35#include "core/css/resolver/StyleResolver.h"
36#include "wtf/MathExtras.h"
37#include "wtf/OwnPtr.h"
38#include "wtf/text/StringBuilder.h"
39
40static const int maxExpressionDepth = 100;
41
42enum ParseState {
43    OK,
44    TooDeep,
45    NoMoreTokens
46};
47
48namespace blink {
49
50static CalculationCategory unitCategory(CSSPrimitiveValue::UnitType type)
51{
52    switch (type) {
53    case CSSPrimitiveValue::CSS_NUMBER:
54        return CalcNumber;
55    case CSSPrimitiveValue::CSS_PERCENTAGE:
56        return CalcPercent;
57    case CSSPrimitiveValue::CSS_EMS:
58    case CSSPrimitiveValue::CSS_EXS:
59    case CSSPrimitiveValue::CSS_PX:
60    case CSSPrimitiveValue::CSS_CM:
61    case CSSPrimitiveValue::CSS_MM:
62    case CSSPrimitiveValue::CSS_IN:
63    case CSSPrimitiveValue::CSS_PT:
64    case CSSPrimitiveValue::CSS_PC:
65    case CSSPrimitiveValue::CSS_REMS:
66    case CSSPrimitiveValue::CSS_CHS:
67    case CSSPrimitiveValue::CSS_VW:
68    case CSSPrimitiveValue::CSS_VH:
69    case CSSPrimitiveValue::CSS_VMIN:
70    case CSSPrimitiveValue::CSS_VMAX:
71        return CalcLength;
72    case CSSPrimitiveValue::CSS_DEG:
73    case CSSPrimitiveValue::CSS_GRAD:
74    case CSSPrimitiveValue::CSS_RAD:
75    case CSSPrimitiveValue::CSS_TURN:
76        return CalcAngle;
77    case CSSPrimitiveValue::CSS_MS:
78    case CSSPrimitiveValue::CSS_S:
79        return CalcTime;
80    case CSSPrimitiveValue::CSS_HZ:
81    case CSSPrimitiveValue::CSS_KHZ:
82        return CalcFrequency;
83    default:
84        return CalcOther;
85    }
86}
87
88static bool hasDoubleValue(CSSPrimitiveValue::UnitType type)
89{
90    switch (type) {
91    case CSSPrimitiveValue::CSS_NUMBER:
92    case CSSPrimitiveValue::CSS_PERCENTAGE:
93    case CSSPrimitiveValue::CSS_EMS:
94    case CSSPrimitiveValue::CSS_EXS:
95    case CSSPrimitiveValue::CSS_CHS:
96    case CSSPrimitiveValue::CSS_REMS:
97    case CSSPrimitiveValue::CSS_PX:
98    case CSSPrimitiveValue::CSS_CM:
99    case CSSPrimitiveValue::CSS_MM:
100    case CSSPrimitiveValue::CSS_IN:
101    case CSSPrimitiveValue::CSS_PT:
102    case CSSPrimitiveValue::CSS_PC:
103    case CSSPrimitiveValue::CSS_DEG:
104    case CSSPrimitiveValue::CSS_RAD:
105    case CSSPrimitiveValue::CSS_GRAD:
106    case CSSPrimitiveValue::CSS_TURN:
107    case CSSPrimitiveValue::CSS_MS:
108    case CSSPrimitiveValue::CSS_S:
109    case CSSPrimitiveValue::CSS_HZ:
110    case CSSPrimitiveValue::CSS_KHZ:
111    case CSSPrimitiveValue::CSS_DIMENSION:
112    case CSSPrimitiveValue::CSS_VW:
113    case CSSPrimitiveValue::CSS_VH:
114    case CSSPrimitiveValue::CSS_VMIN:
115    case CSSPrimitiveValue::CSS_VMAX:
116    case CSSPrimitiveValue::CSS_DPPX:
117    case CSSPrimitiveValue::CSS_DPI:
118    case CSSPrimitiveValue::CSS_DPCM:
119    case CSSPrimitiveValue::CSS_FR:
120        return true;
121    case CSSPrimitiveValue::CSS_UNKNOWN:
122    case CSSPrimitiveValue::CSS_STRING:
123    case CSSPrimitiveValue::CSS_URI:
124    case CSSPrimitiveValue::CSS_IDENT:
125    case CSSPrimitiveValue::CSS_ATTR:
126    case CSSPrimitiveValue::CSS_COUNTER:
127    case CSSPrimitiveValue::CSS_RECT:
128    case CSSPrimitiveValue::CSS_RGBCOLOR:
129    case CSSPrimitiveValue::CSS_PAIR:
130    case CSSPrimitiveValue::CSS_UNICODE_RANGE:
131    case CSSPrimitiveValue::CSS_PARSER_HEXCOLOR:
132    case CSSPrimitiveValue::CSS_COUNTER_NAME:
133    case CSSPrimitiveValue::CSS_SHAPE:
134    case CSSPrimitiveValue::CSS_QUAD:
135    case CSSPrimitiveValue::CSS_CALC:
136    case CSSPrimitiveValue::CSS_CALC_PERCENTAGE_WITH_NUMBER:
137    case CSSPrimitiveValue::CSS_CALC_PERCENTAGE_WITH_LENGTH:
138    case CSSPrimitiveValue::CSS_PROPERTY_ID:
139    case CSSPrimitiveValue::CSS_VALUE_ID:
140        return false;
141    };
142    ASSERT_NOT_REACHED();
143    return false;
144}
145
146static String buildCSSText(const String& expression)
147{
148    StringBuilder result;
149    result.appendLiteral("calc");
150    bool expressionHasSingleTerm = expression[0] != '(';
151    if (expressionHasSingleTerm)
152        result.append('(');
153    result.append(expression);
154    if (expressionHasSingleTerm)
155        result.append(')');
156    return result.toString();
157}
158
159String CSSCalcValue::customCSSText() const
160{
161    return buildCSSText(m_expression->customCSSText());
162}
163
164bool CSSCalcValue::equals(const CSSCalcValue& other) const
165{
166    return compareCSSValuePtr(m_expression, other.m_expression);
167}
168
169double CSSCalcValue::clampToPermittedRange(double value) const
170{
171    return m_nonNegative && value < 0 ? 0 : value;
172}
173
174double CSSCalcValue::doubleValue() const
175{
176    return clampToPermittedRange(m_expression->doubleValue());
177}
178
179double CSSCalcValue::computeLengthPx(const CSSToLengthConversionData& conversionData) const
180{
181    return clampToPermittedRange(m_expression->computeLengthPx(conversionData));
182}
183
184DEFINE_EMPTY_DESTRUCTOR_WILL_BE_REMOVED(CSSCalcExpressionNode)
185
186class CSSCalcPrimitiveValue FINAL : public CSSCalcExpressionNode {
187    WTF_MAKE_FAST_ALLOCATED_WILL_BE_REMOVED;
188public:
189
190    static PassRefPtrWillBeRawPtr<CSSCalcPrimitiveValue> create(PassRefPtrWillBeRawPtr<CSSPrimitiveValue> value, bool isInteger)
191    {
192        return adoptRefWillBeNoop(new CSSCalcPrimitiveValue(value, isInteger));
193    }
194
195    static PassRefPtrWillBeRawPtr<CSSCalcPrimitiveValue> create(double value, CSSPrimitiveValue::UnitType type, bool isInteger)
196    {
197        if (std::isnan(value) || std::isinf(value))
198            return nullptr;
199        return adoptRefWillBeNoop(new CSSCalcPrimitiveValue(CSSPrimitiveValue::create(value, type).get(), isInteger));
200    }
201
202    virtual bool isZero() const OVERRIDE
203    {
204        return !m_value->getDoubleValue();
205    }
206
207    virtual String customCSSText() const OVERRIDE
208    {
209        return m_value->cssText();
210    }
211
212    virtual void accumulatePixelsAndPercent(const CSSToLengthConversionData& conversionData, PixelsAndPercent& value, float multiplier) const OVERRIDE
213    {
214        switch (m_category) {
215        case CalcLength:
216            value.pixels += m_value->computeLength<float>(conversionData) * multiplier;
217            break;
218        case CalcPercent:
219            ASSERT(m_value->isPercentage());
220            value.percent += m_value->getDoubleValue() * multiplier;
221            break;
222        default:
223            ASSERT_NOT_REACHED();
224        }
225    }
226
227    virtual double doubleValue() const OVERRIDE
228    {
229        if (hasDoubleValue(primitiveType()))
230            return m_value->getDoubleValue();
231        ASSERT_NOT_REACHED();
232        return 0;
233    }
234
235    virtual double computeLengthPx(const CSSToLengthConversionData& conversionData) const OVERRIDE
236    {
237        switch (m_category) {
238        case CalcLength:
239            return m_value->computeLength<double>(conversionData);
240        case CalcNumber:
241        case CalcPercent:
242            return m_value->getDoubleValue();
243        case CalcAngle:
244        case CalcFrequency:
245        case CalcPercentLength:
246        case CalcPercentNumber:
247        case CalcTime:
248        case CalcOther:
249            ASSERT_NOT_REACHED();
250            break;
251        }
252        ASSERT_NOT_REACHED();
253        return 0;
254    }
255
256    virtual void accumulateLengthArray(CSSLengthArray& lengthArray, double multiplier) const
257    {
258        ASSERT(category() != CalcNumber);
259        m_value->accumulateLengthArray(lengthArray, multiplier);
260    }
261
262    virtual bool equals(const CSSCalcExpressionNode& other) const OVERRIDE
263    {
264        if (type() != other.type())
265            return false;
266
267        return compareCSSValuePtr(m_value, static_cast<const CSSCalcPrimitiveValue&>(other).m_value);
268    }
269
270    virtual Type type() const OVERRIDE { return CssCalcPrimitiveValue; }
271    virtual CSSPrimitiveValue::UnitType primitiveType() const OVERRIDE
272    {
273        return m_value->primitiveType();
274    }
275
276
277    virtual void trace(Visitor* visitor)
278    {
279        visitor->trace(m_value);
280        CSSCalcExpressionNode::trace(visitor);
281    }
282
283private:
284    CSSCalcPrimitiveValue(PassRefPtrWillBeRawPtr<CSSPrimitiveValue> value, bool isInteger)
285        : CSSCalcExpressionNode(unitCategory(value->primitiveType()), isInteger)
286        , m_value(value)
287    {
288    }
289
290    RefPtrWillBeMember<CSSPrimitiveValue> m_value;
291};
292
293static const CalculationCategory addSubtractResult[CalcOther][CalcOther] = {
294//                        CalcNumber         CalcLength         CalcPercent        CalcPercentNumber  CalcPercentLength  CalcAngle  CalcTime   CalcFrequency
295/* CalcNumber */        { CalcNumber,        CalcOther,         CalcPercentNumber, CalcPercentNumber, CalcOther,         CalcOther, CalcOther, CalcOther     },
296/* CalcLength */        { CalcOther,         CalcLength,        CalcPercentLength, CalcOther,         CalcPercentLength, CalcOther, CalcOther, CalcOther     },
297/* CalcPercent */       { CalcPercentNumber, CalcPercentLength, CalcPercent,       CalcPercentNumber, CalcPercentLength, CalcOther, CalcOther, CalcOther     },
298/* CalcPercentNumber */ { CalcPercentNumber, CalcOther,         CalcPercentNumber, CalcPercentNumber, CalcOther,         CalcOther, CalcOther, CalcOther     },
299/* CalcPercentLength */ { CalcOther,         CalcPercentLength, CalcPercentLength, CalcOther,         CalcPercentLength, CalcOther, CalcOther, CalcOther     },
300/* CalcAngle  */        { CalcOther,         CalcOther,         CalcOther,         CalcOther,         CalcOther,         CalcAngle, CalcOther, CalcOther     },
301/* CalcTime */          { CalcOther,         CalcOther,         CalcOther,         CalcOther,         CalcOther,         CalcOther, CalcTime,  CalcOther     },
302/* CalcFrequency */     { CalcOther,         CalcOther,         CalcOther,         CalcOther,         CalcOther,         CalcOther, CalcOther, CalcFrequency }
303};
304
305static CalculationCategory determineCategory(const CSSCalcExpressionNode& leftSide, const CSSCalcExpressionNode& rightSide, CalcOperator op)
306{
307    CalculationCategory leftCategory = leftSide.category();
308    CalculationCategory rightCategory = rightSide.category();
309
310    if (leftCategory == CalcOther || rightCategory == CalcOther)
311        return CalcOther;
312
313    switch (op) {
314    case CalcAdd:
315    case CalcSubtract:
316        return addSubtractResult[leftCategory][rightCategory];
317    case CalcMultiply:
318        if (leftCategory != CalcNumber && rightCategory != CalcNumber)
319            return CalcOther;
320        return leftCategory == CalcNumber ? rightCategory : leftCategory;
321    case CalcDivide:
322        if (rightCategory != CalcNumber || rightSide.isZero())
323            return CalcOther;
324        return leftCategory;
325    }
326
327    ASSERT_NOT_REACHED();
328    return CalcOther;
329}
330
331static bool isIntegerResult(const CSSCalcExpressionNode* leftSide, const CSSCalcExpressionNode* rightSide, CalcOperator op)
332{
333    // Not testing for actual integer values.
334    // Performs W3C spec's type checking for calc integers.
335    // http://www.w3.org/TR/css3-values/#calc-type-checking
336    return op != CalcDivide && leftSide->isInteger() && rightSide->isInteger();
337}
338
339class CSSCalcBinaryOperation FINAL : public CSSCalcExpressionNode {
340public:
341    static PassRefPtrWillBeRawPtr<CSSCalcExpressionNode> create(PassRefPtrWillBeRawPtr<CSSCalcExpressionNode> leftSide, PassRefPtrWillBeRawPtr<CSSCalcExpressionNode> rightSide, CalcOperator op)
342    {
343        ASSERT(leftSide->category() != CalcOther && rightSide->category() != CalcOther);
344
345        CalculationCategory newCategory = determineCategory(*leftSide, *rightSide, op);
346        if (newCategory == CalcOther)
347            return nullptr;
348
349        return adoptRefWillBeNoop(new CSSCalcBinaryOperation(leftSide, rightSide, op, newCategory));
350    }
351
352    static PassRefPtrWillBeRawPtr<CSSCalcExpressionNode> createSimplified(PassRefPtrWillBeRawPtr<CSSCalcExpressionNode> leftSide, PassRefPtrWillBeRawPtr<CSSCalcExpressionNode> rightSide, CalcOperator op)
353    {
354        CalculationCategory leftCategory = leftSide->category();
355        CalculationCategory rightCategory = rightSide->category();
356        ASSERT(leftCategory != CalcOther && rightCategory != CalcOther);
357
358        bool isInteger = isIntegerResult(leftSide.get(), rightSide.get(), op);
359
360        // Simplify numbers.
361        if (leftCategory == CalcNumber && rightCategory == CalcNumber) {
362            return CSSCalcPrimitiveValue::create(evaluateOperator(leftSide->doubleValue(), rightSide->doubleValue(), op), CSSPrimitiveValue::CSS_NUMBER, isInteger);
363        }
364
365        // Simplify addition and subtraction between same types.
366        if (op == CalcAdd || op == CalcSubtract) {
367            if (leftCategory == rightSide->category()) {
368                CSSPrimitiveValue::UnitType leftType = leftSide->primitiveType();
369                if (hasDoubleValue(leftType)) {
370                    CSSPrimitiveValue::UnitType rightType = rightSide->primitiveType();
371                    if (leftType == rightType)
372                        return CSSCalcPrimitiveValue::create(evaluateOperator(leftSide->doubleValue(), rightSide->doubleValue(), op), leftType, isInteger);
373                    CSSPrimitiveValue::UnitCategory leftUnitCategory = CSSPrimitiveValue::unitCategory(leftType);
374                    if (leftUnitCategory != CSSPrimitiveValue::UOther && leftUnitCategory == CSSPrimitiveValue::unitCategory(rightType)) {
375                        CSSPrimitiveValue::UnitType canonicalType = CSSPrimitiveValue::canonicalUnitTypeForCategory(leftUnitCategory);
376                        if (canonicalType != CSSPrimitiveValue::CSS_UNKNOWN) {
377                            double leftValue = leftSide->doubleValue() * CSSPrimitiveValue::conversionToCanonicalUnitsScaleFactor(leftType);
378                            double rightValue = rightSide->doubleValue() * CSSPrimitiveValue::conversionToCanonicalUnitsScaleFactor(rightType);
379                            return CSSCalcPrimitiveValue::create(evaluateOperator(leftValue, rightValue, op), canonicalType, isInteger);
380                        }
381                    }
382                }
383            }
384        } else {
385            // Simplify multiplying or dividing by a number for simplifiable types.
386            ASSERT(op == CalcMultiply || op == CalcDivide);
387            CSSCalcExpressionNode* numberSide = getNumberSide(leftSide.get(), rightSide.get());
388            if (!numberSide)
389                return create(leftSide, rightSide, op);
390            if (numberSide == leftSide && op == CalcDivide)
391                return nullptr;
392            CSSCalcExpressionNode* otherSide = leftSide == numberSide ? rightSide.get() : leftSide.get();
393
394            double number = numberSide->doubleValue();
395            if (std::isnan(number) || std::isinf(number))
396                return nullptr;
397            if (op == CalcDivide && !number)
398                return nullptr;
399
400            CSSPrimitiveValue::UnitType otherType = otherSide->primitiveType();
401            if (hasDoubleValue(otherType))
402                return CSSCalcPrimitiveValue::create(evaluateOperator(otherSide->doubleValue(), number, op), otherType, isInteger);
403        }
404
405        return create(leftSide, rightSide, op);
406    }
407
408    virtual bool isZero() const OVERRIDE
409    {
410        return !doubleValue();
411    }
412
413    virtual void accumulatePixelsAndPercent(const CSSToLengthConversionData& conversionData, PixelsAndPercent& value, float multiplier) const OVERRIDE
414    {
415        switch (m_operator) {
416        case CalcAdd:
417            m_leftSide->accumulatePixelsAndPercent(conversionData, value, multiplier);
418            m_rightSide->accumulatePixelsAndPercent(conversionData, value, multiplier);
419            break;
420        case CalcSubtract:
421            m_leftSide->accumulatePixelsAndPercent(conversionData, value, multiplier);
422            m_rightSide->accumulatePixelsAndPercent(conversionData, value, -multiplier);
423            break;
424        case CalcMultiply:
425            ASSERT((m_leftSide->category() == CalcNumber) != (m_rightSide->category() == CalcNumber));
426            if (m_leftSide->category() == CalcNumber)
427                m_rightSide->accumulatePixelsAndPercent(conversionData, value, multiplier * m_leftSide->doubleValue());
428            else
429                m_leftSide->accumulatePixelsAndPercent(conversionData, value, multiplier * m_rightSide->doubleValue());
430            break;
431        case CalcDivide:
432            ASSERT(m_rightSide->category() == CalcNumber);
433            m_leftSide->accumulatePixelsAndPercent(conversionData, value, multiplier / m_rightSide->doubleValue());
434            break;
435        default:
436            ASSERT_NOT_REACHED();
437        }
438    }
439
440    virtual double doubleValue() const OVERRIDE
441    {
442        return evaluate(m_leftSide->doubleValue(), m_rightSide->doubleValue());
443    }
444
445    virtual double computeLengthPx(const CSSToLengthConversionData& conversionData) const OVERRIDE
446    {
447        const double leftValue = m_leftSide->computeLengthPx(conversionData);
448        const double rightValue = m_rightSide->computeLengthPx(conversionData);
449        return evaluate(leftValue, rightValue);
450    }
451
452    virtual void accumulateLengthArray(CSSLengthArray& lengthArray, double multiplier) const
453    {
454        switch (m_operator) {
455        case CalcAdd:
456            m_leftSide->accumulateLengthArray(lengthArray, multiplier);
457            m_rightSide->accumulateLengthArray(lengthArray, multiplier);
458            break;
459        case CalcSubtract:
460            m_leftSide->accumulateLengthArray(lengthArray, multiplier);
461            m_rightSide->accumulateLengthArray(lengthArray, -multiplier);
462            break;
463        case CalcMultiply:
464            ASSERT((m_leftSide->category() == CalcNumber) != (m_rightSide->category() == CalcNumber));
465            if (m_leftSide->category() == CalcNumber)
466                m_rightSide->accumulateLengthArray(lengthArray, multiplier * m_leftSide->doubleValue());
467            else
468                m_leftSide->accumulateLengthArray(lengthArray, multiplier * m_rightSide->doubleValue());
469            break;
470        case CalcDivide:
471            ASSERT(m_rightSide->category() == CalcNumber);
472            m_leftSide->accumulateLengthArray(lengthArray, multiplier / m_rightSide->doubleValue());
473            break;
474        default:
475            ASSERT_NOT_REACHED();
476        }
477    }
478
479    static String buildCSSText(const String& leftExpression, const String& rightExpression, CalcOperator op)
480    {
481        StringBuilder result;
482        result.append('(');
483        result.append(leftExpression);
484        result.append(' ');
485        result.append(static_cast<char>(op));
486        result.append(' ');
487        result.append(rightExpression);
488        result.append(')');
489
490        return result.toString();
491    }
492
493    virtual String customCSSText() const OVERRIDE
494    {
495        return buildCSSText(m_leftSide->customCSSText(), m_rightSide->customCSSText(), m_operator);
496    }
497
498    virtual bool equals(const CSSCalcExpressionNode& exp) const OVERRIDE
499    {
500        if (type() != exp.type())
501            return false;
502
503        const CSSCalcBinaryOperation& other = static_cast<const CSSCalcBinaryOperation&>(exp);
504        return compareCSSValuePtr(m_leftSide, other.m_leftSide)
505            && compareCSSValuePtr(m_rightSide, other.m_rightSide)
506            && m_operator == other.m_operator;
507    }
508
509    virtual Type type() const OVERRIDE { return CssCalcBinaryOperation; }
510
511    virtual CSSPrimitiveValue::UnitType primitiveType() const OVERRIDE
512    {
513        switch (m_category) {
514        case CalcNumber:
515            ASSERT(m_leftSide->category() == CalcNumber && m_rightSide->category() == CalcNumber);
516            return CSSPrimitiveValue::CSS_NUMBER;
517        case CalcLength:
518        case CalcPercent: {
519            if (m_leftSide->category() == CalcNumber)
520                return m_rightSide->primitiveType();
521            if (m_rightSide->category() == CalcNumber)
522                return m_leftSide->primitiveType();
523            CSSPrimitiveValue::UnitType leftType = m_leftSide->primitiveType();
524            if (leftType == m_rightSide->primitiveType())
525                return leftType;
526            return CSSPrimitiveValue::CSS_UNKNOWN;
527        }
528        case CalcAngle:
529            return CSSPrimitiveValue::CSS_DEG;
530        case CalcTime:
531            return CSSPrimitiveValue::CSS_MS;
532        case CalcFrequency:
533            return CSSPrimitiveValue::CSS_HZ;
534        case CalcPercentLength:
535        case CalcPercentNumber:
536        case CalcOther:
537            return CSSPrimitiveValue::CSS_UNKNOWN;
538        }
539        ASSERT_NOT_REACHED();
540        return CSSPrimitiveValue::CSS_UNKNOWN;
541    }
542
543    virtual void trace(Visitor* visitor)
544    {
545        visitor->trace(m_leftSide);
546        visitor->trace(m_rightSide);
547        CSSCalcExpressionNode::trace(visitor);
548    }
549
550private:
551    CSSCalcBinaryOperation(PassRefPtrWillBeRawPtr<CSSCalcExpressionNode> leftSide, PassRefPtrWillBeRawPtr<CSSCalcExpressionNode> rightSide, CalcOperator op, CalculationCategory category)
552        : CSSCalcExpressionNode(category, isIntegerResult(leftSide.get(), rightSide.get(), op))
553        , m_leftSide(leftSide)
554        , m_rightSide(rightSide)
555        , m_operator(op)
556    {
557    }
558
559    static CSSCalcExpressionNode* getNumberSide(CSSCalcExpressionNode* leftSide, CSSCalcExpressionNode* rightSide)
560    {
561        if (leftSide->category() == CalcNumber)
562            return leftSide;
563        if (rightSide->category() == CalcNumber)
564            return rightSide;
565        return 0;
566    }
567
568    double evaluate(double leftSide, double rightSide) const
569    {
570        return evaluateOperator(leftSide, rightSide, m_operator);
571    }
572
573    static double evaluateOperator(double leftValue, double rightValue, CalcOperator op)
574    {
575        switch (op) {
576        case CalcAdd:
577            return leftValue + rightValue;
578        case CalcSubtract:
579            return leftValue - rightValue;
580        case CalcMultiply:
581            return leftValue * rightValue;
582        case CalcDivide:
583            if (rightValue)
584                return leftValue / rightValue;
585            return std::numeric_limits<double>::quiet_NaN();
586        }
587        return 0;
588    }
589
590    const RefPtrWillBeMember<CSSCalcExpressionNode> m_leftSide;
591    const RefPtrWillBeMember<CSSCalcExpressionNode> m_rightSide;
592    const CalcOperator m_operator;
593};
594
595static ParseState checkDepthAndIndex(int* depth, unsigned index, CSSParserValueList* tokens)
596{
597    (*depth)++;
598    if (*depth > maxExpressionDepth)
599        return TooDeep;
600    if (index >= tokens->size())
601        return NoMoreTokens;
602    return OK;
603}
604
605class CSSCalcExpressionNodeParser {
606    STACK_ALLOCATED();
607public:
608    PassRefPtrWillBeRawPtr<CSSCalcExpressionNode> parseCalc(CSSParserValueList* tokens)
609    {
610        unsigned index = 0;
611        Value result;
612        bool ok = parseValueExpression(tokens, 0, &index, &result);
613        ASSERT_WITH_SECURITY_IMPLICATION(index <= tokens->size());
614        if (!ok || index != tokens->size())
615            return nullptr;
616        return result.value;
617    }
618
619private:
620    struct Value {
621        STACK_ALLOCATED();
622    public:
623        RefPtrWillBeMember<CSSCalcExpressionNode> value;
624    };
625
626    char operatorValue(CSSParserValueList* tokens, unsigned index)
627    {
628        if (index >= tokens->size())
629            return 0;
630        CSSParserValue* value = tokens->valueAt(index);
631        if (value->unit != CSSParserValue::Operator)
632            return 0;
633
634        return value->iValue;
635    }
636
637    bool parseValue(CSSParserValueList* tokens, unsigned* index, Value* result)
638    {
639        CSSParserValue* parserValue = tokens->valueAt(*index);
640        if (parserValue->unit >= CSSParserValue::Operator)
641            return false;
642
643        CSSPrimitiveValue::UnitType type = static_cast<CSSPrimitiveValue::UnitType>(parserValue->unit);
644        if (unitCategory(type) == CalcOther)
645            return false;
646
647        result->value = CSSCalcPrimitiveValue::create(
648            CSSPrimitiveValue::create(parserValue->fValue, type), parserValue->isInt);
649
650        ++*index;
651        return true;
652    }
653
654    bool parseValueTerm(CSSParserValueList* tokens, int depth, unsigned* index, Value* result)
655    {
656        if (checkDepthAndIndex(&depth, *index, tokens) != OK)
657            return false;
658
659        if (operatorValue(tokens, *index) == '(') {
660            unsigned currentIndex = *index + 1;
661            if (!parseValueExpression(tokens, depth, &currentIndex, result))
662                return false;
663
664            if (operatorValue(tokens, currentIndex) != ')')
665                return false;
666            *index = currentIndex + 1;
667            return true;
668        }
669
670        return parseValue(tokens, index, result);
671    }
672
673    bool parseValueMultiplicativeExpression(CSSParserValueList* tokens, int depth, unsigned* index, Value* result)
674    {
675        if (checkDepthAndIndex(&depth, *index, tokens) != OK)
676            return false;
677
678        if (!parseValueTerm(tokens, depth, index, result))
679            return false;
680
681        while (*index < tokens->size() - 1) {
682            char operatorCharacter = operatorValue(tokens, *index);
683            if (operatorCharacter != CalcMultiply && operatorCharacter != CalcDivide)
684                break;
685            ++*index;
686
687            Value rhs;
688            if (!parseValueTerm(tokens, depth, index, &rhs))
689                return false;
690
691            result->value = CSSCalcBinaryOperation::createSimplified(result->value, rhs.value, static_cast<CalcOperator>(operatorCharacter));
692            if (!result->value)
693                return false;
694        }
695
696        ASSERT_WITH_SECURITY_IMPLICATION(*index <= tokens->size());
697        return true;
698    }
699
700    bool parseAdditiveValueExpression(CSSParserValueList* tokens, int depth, unsigned* index, Value* result)
701    {
702        if (checkDepthAndIndex(&depth, *index, tokens) != OK)
703            return false;
704
705        if (!parseValueMultiplicativeExpression(tokens, depth, index, result))
706            return false;
707
708        while (*index < tokens->size() - 1) {
709            char operatorCharacter = operatorValue(tokens, *index);
710            if (operatorCharacter != CalcAdd && operatorCharacter != CalcSubtract)
711                break;
712            ++*index;
713
714            Value rhs;
715            if (!parseValueMultiplicativeExpression(tokens, depth, index, &rhs))
716                return false;
717
718            result->value = CSSCalcBinaryOperation::createSimplified(result->value, rhs.value, static_cast<CalcOperator>(operatorCharacter));
719            if (!result->value)
720                return false;
721        }
722
723        ASSERT_WITH_SECURITY_IMPLICATION(*index <= tokens->size());
724        return true;
725    }
726
727    bool parseValueExpression(CSSParserValueList* tokens, int depth, unsigned* index, Value* result)
728    {
729        return parseAdditiveValueExpression(tokens, depth, index, result);
730    }
731};
732
733PassRefPtrWillBeRawPtr<CSSCalcExpressionNode> CSSCalcValue::createExpressionNode(PassRefPtrWillBeRawPtr<CSSPrimitiveValue> value, bool isInteger)
734{
735    return CSSCalcPrimitiveValue::create(value, isInteger);
736}
737
738PassRefPtrWillBeRawPtr<CSSCalcExpressionNode> CSSCalcValue::createExpressionNode(PassRefPtrWillBeRawPtr<CSSCalcExpressionNode> leftSide, PassRefPtrWillBeRawPtr<CSSCalcExpressionNode> rightSide, CalcOperator op)
739{
740    return CSSCalcBinaryOperation::create(leftSide, rightSide, op);
741}
742
743PassRefPtrWillBeRawPtr<CSSCalcExpressionNode> CSSCalcValue::createExpressionNode(double pixels, double percent)
744{
745    return createExpressionNode(
746        createExpressionNode(CSSPrimitiveValue::create(pixels, CSSPrimitiveValue::CSS_PX), pixels == trunc(pixels)),
747        createExpressionNode(CSSPrimitiveValue::create(percent, CSSPrimitiveValue::CSS_PERCENTAGE), percent == trunc(percent)),
748        CalcAdd);
749}
750
751PassRefPtrWillBeRawPtr<CSSCalcValue> CSSCalcValue::create(CSSParserString name, CSSParserValueList* parserValueList, ValueRange range)
752{
753    CSSCalcExpressionNodeParser parser;
754    RefPtrWillBeRawPtr<CSSCalcExpressionNode> expression = nullptr;
755
756    if (equalIgnoringCase(name, "calc") || equalIgnoringCase(name, "-webkit-calc"))
757        expression = parser.parseCalc(parserValueList);
758    // FIXME calc (http://webkit.org/b/16662) Add parsing for min and max here
759
760    return expression ? adoptRefWillBeNoop(new CSSCalcValue(expression, range)) : nullptr;
761}
762
763PassRefPtrWillBeRawPtr<CSSCalcValue> CSSCalcValue::create(PassRefPtrWillBeRawPtr<CSSCalcExpressionNode> expression, ValueRange range)
764{
765    return adoptRefWillBeNoop(new CSSCalcValue(expression, range));
766}
767
768void CSSCalcValue::traceAfterDispatch(Visitor* visitor)
769{
770    visitor->trace(m_expression);
771    CSSValue::traceAfterDispatch(visitor);
772}
773
774} // namespace blink
775