1/*
2 * Copyright (C) 2011, 2012 Google Inc. All rights reserved.
3 * Copyright (C) 2014 Apple Inc. All rights reserved.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions are
7 * met:
8 *
9 *     * Redistributions of source code must retain the above copyright
10 * notice, this list of conditions and the following disclaimer.
11 *     * Redistributions in binary form must reproduce the above
12 * copyright notice, this list of conditions and the following disclaimer
13 * in the documentation and/or other materials provided with the
14 * distribution.
15 *     * Neither the name of Google Inc. nor the names of its
16 * contributors may be used to endorse or promote products derived from
17 * this software without specific prior written permission.
18 *
19 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
20 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
21 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
22 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
23 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
24 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
25 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
26 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
27 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
28 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
29 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
30 */
31
32#include "config.h"
33#include "CSSCalculationValue.h"
34
35#include "CSSPrimitiveValueMappings.h"
36#include "StyleResolver.h"
37#include <wtf/MathExtras.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 WebCore {
49
50static PassRefPtr<CSSCalcExpressionNode> createCSS(const CalcExpressionNode&, const RenderStyle&);
51static PassRefPtr<CSSCalcExpressionNode> createCSS(const Length&, const RenderStyle&);
52
53static CalculationCategory unitCategory(CSSPrimitiveValue::UnitTypes type)
54{
55    switch (type) {
56    case CSSPrimitiveValue::CSS_NUMBER:
57    case CSSPrimitiveValue::CSS_PARSER_INTEGER:
58        return CalcNumber;
59    case CSSPrimitiveValue::CSS_EMS:
60    case CSSPrimitiveValue::CSS_EXS:
61    case CSSPrimitiveValue::CSS_PX:
62    case CSSPrimitiveValue::CSS_CM:
63    case CSSPrimitiveValue::CSS_MM:
64    case CSSPrimitiveValue::CSS_IN:
65    case CSSPrimitiveValue::CSS_PT:
66    case CSSPrimitiveValue::CSS_PC:
67    case CSSPrimitiveValue::CSS_REMS:
68    case CSSPrimitiveValue::CSS_CHS:
69    case CSSPrimitiveValue::CSS_VW:
70    case CSSPrimitiveValue::CSS_VH:
71    case CSSPrimitiveValue::CSS_VMIN:
72    case CSSPrimitiveValue::CSS_VMAX:
73        return CalcLength;
74    case CSSPrimitiveValue::CSS_PERCENTAGE:
75        return CalcPercent;
76    case CSSPrimitiveValue::CSS_DEG:
77    case CSSPrimitiveValue::CSS_RAD:
78    case CSSPrimitiveValue::CSS_GRAD:
79    case CSSPrimitiveValue::CSS_TURN:
80        return CalcAngle;
81    case CSSPrimitiveValue::CSS_MS:
82    case CSSPrimitiveValue::CSS_S:
83        return CalcTime;
84    case CSSPrimitiveValue::CSS_HZ:
85    case CSSPrimitiveValue::CSS_KHZ:
86        return CalcFrequency;
87    default:
88        return CalcOther;
89    }
90}
91
92static bool hasDoubleValue(CSSPrimitiveValue::UnitTypes type)
93{
94    switch (type) {
95    case CSSPrimitiveValue::CSS_FR:
96    case CSSPrimitiveValue::CSS_NUMBER:
97    case CSSPrimitiveValue::CSS_PARSER_INTEGER:
98    case CSSPrimitiveValue::CSS_PERCENTAGE:
99    case CSSPrimitiveValue::CSS_EMS:
100    case CSSPrimitiveValue::CSS_EXS:
101    case CSSPrimitiveValue::CSS_CHS:
102    case CSSPrimitiveValue::CSS_REMS:
103    case CSSPrimitiveValue::CSS_PX:
104    case CSSPrimitiveValue::CSS_CM:
105    case CSSPrimitiveValue::CSS_MM:
106    case CSSPrimitiveValue::CSS_IN:
107    case CSSPrimitiveValue::CSS_PT:
108    case CSSPrimitiveValue::CSS_PC:
109    case CSSPrimitiveValue::CSS_DEG:
110    case CSSPrimitiveValue::CSS_RAD:
111    case CSSPrimitiveValue::CSS_GRAD:
112    case CSSPrimitiveValue::CSS_MS:
113    case CSSPrimitiveValue::CSS_S:
114    case CSSPrimitiveValue::CSS_HZ:
115    case CSSPrimitiveValue::CSS_KHZ:
116    case CSSPrimitiveValue::CSS_DIMENSION:
117    case CSSPrimitiveValue::CSS_VW:
118    case CSSPrimitiveValue::CSS_VH:
119    case CSSPrimitiveValue::CSS_VMIN:
120    case CSSPrimitiveValue::CSS_VMAX:
121    case CSSPrimitiveValue::CSS_DPPX:
122    case CSSPrimitiveValue::CSS_DPI:
123    case CSSPrimitiveValue::CSS_DPCM:
124        return true;
125    case CSSPrimitiveValue::CSS_UNKNOWN:
126    case CSSPrimitiveValue::CSS_STRING:
127    case CSSPrimitiveValue::CSS_URI:
128    case CSSPrimitiveValue::CSS_IDENT:
129    case CSSPrimitiveValue::CSS_ATTR:
130    case CSSPrimitiveValue::CSS_COUNTER:
131    case CSSPrimitiveValue::CSS_RECT:
132    case CSSPrimitiveValue::CSS_RGBCOLOR:
133    case CSSPrimitiveValue::CSS_PAIR:
134    case CSSPrimitiveValue::CSS_UNICODE_RANGE:
135    case CSSPrimitiveValue::CSS_PARSER_OPERATOR:
136    case CSSPrimitiveValue::CSS_PARSER_HEXCOLOR:
137    case CSSPrimitiveValue::CSS_PARSER_IDENTIFIER:
138    case CSSPrimitiveValue::CSS_TURN:
139    case CSSPrimitiveValue::CSS_COUNTER_NAME:
140    case CSSPrimitiveValue::CSS_SHAPE:
141    case CSSPrimitiveValue::CSS_QUAD:
142    case CSSPrimitiveValue::CSS_CALC:
143    case CSSPrimitiveValue::CSS_CALC_PERCENTAGE_WITH_NUMBER:
144    case CSSPrimitiveValue::CSS_CALC_PERCENTAGE_WITH_LENGTH:
145    case CSSPrimitiveValue::CSS_PROPERTY_ID:
146    case CSSPrimitiveValue::CSS_VALUE_ID:
147#if ENABLE(DASHBOARD_SUPPORT)
148    case CSSPrimitiveValue::CSS_DASHBOARD_REGION:
149#endif
150        return false;
151    };
152    ASSERT_NOT_REACHED();
153    return false;
154}
155
156static String buildCssText(const String& expression)
157{
158    StringBuilder result;
159    result.append("calc");
160    bool expressionHasSingleTerm = expression[0] != '(';
161    if (expressionHasSingleTerm)
162        result.append('(');
163    result.append(expression);
164    if (expressionHasSingleTerm)
165        result.append(')');
166    return result.toString();
167}
168
169String CSSCalcValue::customCSSText() const
170{
171    return buildCssText(m_expression->customCSSText());
172}
173
174bool CSSCalcValue::equals(const CSSCalcValue& other) const
175{
176    return compareCSSValue(m_expression, other.m_expression);
177}
178
179inline double CSSCalcValue::clampToPermittedRange(double value) const
180{
181    return m_shouldClampToNonNegative && value < 0 ? 0 : value;
182}
183
184double CSSCalcValue::doubleValue() const
185{
186    return clampToPermittedRange(m_expression->doubleValue());
187}
188
189double CSSCalcValue::computeLengthPx(const CSSToLengthConversionData& conversionData) const
190{
191    return clampToPermittedRange(m_expression->computeLengthPx(conversionData));
192}
193
194class CSSCalcPrimitiveValue final : public CSSCalcExpressionNode {
195    WTF_MAKE_FAST_ALLOCATED;
196public:
197    static PassRef<CSSCalcPrimitiveValue> create(PassRefPtr<CSSPrimitiveValue> value, bool isInteger)
198    {
199        return adoptRef(*new CSSCalcPrimitiveValue(value, isInteger));
200    }
201
202    static PassRefPtr<CSSCalcPrimitiveValue> create(double value, CSSPrimitiveValue::UnitTypes type, bool isInteger)
203    {
204        if (std::isnan(value) || std::isinf(value))
205            return nullptr;
206        return adoptRef(new CSSCalcPrimitiveValue(CSSPrimitiveValue::create(value, type), isInteger));
207    }
208
209private:
210    virtual bool isZero() const override
211    {
212        return !m_value->getDoubleValue();
213    }
214
215    virtual String customCSSText() const override
216    {
217        return m_value->cssText();
218    }
219
220    virtual std::unique_ptr<CalcExpressionNode> createCalcExpression(const CSSToLengthConversionData& conversionData) const override
221    {
222        switch (category()) {
223        case CalcNumber:
224            return std::make_unique<CalcExpressionNumber>(m_value->getFloatValue());
225        case CalcLength:
226            return std::make_unique<CalcExpressionLength>(Length(m_value->computeLength<float>(conversionData), WebCore::Fixed));
227        case CalcPercent:
228        case CalcPercentLength: {
229            CSSPrimitiveValue* primitiveValue = m_value.get();
230            return std::make_unique<CalcExpressionLength>(primitiveValue
231                ? primitiveValue->convertToLength<FixedFloatConversion | PercentConversion | FractionConversion>(conversionData) : Length(Undefined));
232        }
233        // Only types that could be part of a Length expression can be converted
234        // to a CalcExpressionNode. CalcPercentNumber makes no sense as a Length.
235        case CalcPercentNumber:
236        case CalcAngle:
237        case CalcTime:
238        case CalcFrequency:
239        case CalcOther:
240            ASSERT_NOT_REACHED();
241        }
242        return nullptr;
243    }
244
245    virtual double doubleValue() const override
246    {
247        if (hasDoubleValue(primitiveType()))
248            return m_value->getDoubleValue();
249        ASSERT_NOT_REACHED();
250        return 0;
251    }
252
253    virtual double computeLengthPx(const CSSToLengthConversionData& conversionData) const override
254    {
255        switch (category()) {
256        case CalcLength:
257            return m_value->computeLength<double>(conversionData);
258        case CalcPercent:
259        case CalcNumber:
260            return m_value->getDoubleValue();
261        case CalcPercentLength:
262        case CalcPercentNumber:
263        case CalcAngle:
264        case CalcTime:
265        case CalcFrequency:
266        case CalcOther:
267            ASSERT_NOT_REACHED();
268            break;
269        }
270        ASSERT_NOT_REACHED();
271        return 0;
272    }
273
274    virtual bool equals(const CSSCalcExpressionNode& other) const override
275    {
276        if (type() != other.type())
277            return false;
278
279        return compareCSSValuePtr(m_value, static_cast<const CSSCalcPrimitiveValue&>(other).m_value);
280    }
281
282    virtual Type type() const override { return CssCalcPrimitiveValue; }
283    virtual CSSPrimitiveValue::UnitTypes primitiveType() const override
284    {
285        return CSSPrimitiveValue::UnitTypes(m_value->primitiveType());
286    }
287
288private:
289    explicit CSSCalcPrimitiveValue(PassRefPtr<CSSPrimitiveValue> value, bool isInteger)
290        : CSSCalcExpressionNode(unitCategory((CSSPrimitiveValue::UnitTypes)value->primitiveType()), isInteger)
291        , m_value(value)
292    {
293    }
294
295    RefPtr<CSSPrimitiveValue> m_value;
296};
297
298static const CalculationCategory addSubtractResult[CalcAngle][CalcAngle] = {
299//    CalcNumber         CalcLength         CalcPercent        CalcPercentNumber  CalcPercentLength
300    { CalcNumber,        CalcOther,         CalcPercentNumber, CalcPercentNumber, CalcOther }, //         CalcNumber
301    { CalcOther,         CalcLength,        CalcPercentLength, CalcOther,         CalcPercentLength }, // CalcLength
302    { CalcPercentNumber, CalcPercentLength, CalcPercent,       CalcPercentNumber, CalcPercentLength }, // CalcPercent
303    { CalcPercentNumber, CalcOther,         CalcPercentNumber, CalcPercentNumber, CalcOther }, //         CalcPercentNumber
304    { CalcOther,         CalcPercentLength, CalcPercentLength, CalcOther,         CalcPercentLength }, // CalcPercentLength
305};
306
307static CalculationCategory determineCategory(const CSSCalcExpressionNode& leftSide, const CSSCalcExpressionNode& rightSide, CalcOperator op)
308{
309    CalculationCategory leftCategory = leftSide.category();
310    CalculationCategory rightCategory = rightSide.category();
311
312    if (leftCategory == CalcOther || rightCategory == CalcOther)
313        return CalcOther;
314
315    switch (op) {
316    case CalcAdd:
317    case CalcSubtract:
318        if (leftCategory < CalcAngle || rightCategory < CalcAngle)
319            return addSubtractResult[leftCategory][rightCategory];
320        if (leftCategory == rightCategory)
321            return leftCategory;
322        return CalcOther;
323    case CalcMultiply:
324        if (leftCategory != CalcNumber && rightCategory != CalcNumber)
325            return CalcOther;
326        return leftCategory == CalcNumber ? rightCategory : leftCategory;
327    case CalcDivide:
328        if (rightCategory != CalcNumber || rightSide.isZero())
329            return CalcOther;
330        return leftCategory;
331    }
332
333    ASSERT_NOT_REACHED();
334    return CalcOther;
335}
336
337static inline bool isIntegerResult(CalcOperator op, const CSSCalcExpressionNode& leftSide, const CSSCalcExpressionNode& rightSide)
338{
339    // Performs W3C spec's type checking for calc integers.
340    // http://www.w3.org/TR/css3-values/#calc-type-checking
341    return op != CalcDivide && leftSide.isInteger() && rightSide.isInteger();
342}
343
344class CSSCalcBinaryOperation final : public CSSCalcExpressionNode {
345    WTF_MAKE_FAST_ALLOCATED;
346public:
347    static PassRefPtr<CSSCalcBinaryOperation> create(CalcOperator op, PassRefPtr<CSSCalcExpressionNode> leftSide, PassRefPtr<CSSCalcExpressionNode> rightSide)
348    {
349        ASSERT(leftSide->category() != CalcOther && rightSide->category() != CalcOther);
350
351        CalculationCategory newCategory = determineCategory(*leftSide, *rightSide, op);
352
353        if (newCategory == CalcOther)
354            return nullptr;
355
356        return adoptRef(new CSSCalcBinaryOperation(newCategory, op, leftSide, rightSide));
357    }
358
359    static PassRefPtr<CSSCalcExpressionNode> createSimplified(CalcOperator op, PassRefPtr<CSSCalcExpressionNode> leftSide, PassRefPtr<CSSCalcExpressionNode> rightSide)
360    {
361        CalculationCategory leftCategory = leftSide->category();
362        CalculationCategory rightCategory = rightSide->category();
363        ASSERT(leftCategory != CalcOther && rightCategory != CalcOther);
364
365        bool isInteger = isIntegerResult(op, *leftSide, *rightSide);
366
367        // Simplify numbers.
368        if (leftCategory == CalcNumber && rightCategory == CalcNumber) {
369            CSSPrimitiveValue::UnitTypes evaluationType = isInteger ? CSSPrimitiveValue::CSS_PARSER_INTEGER : CSSPrimitiveValue::CSS_NUMBER;
370            return CSSCalcPrimitiveValue::create(evaluateOperator(op, leftSide->doubleValue(), rightSide->doubleValue()), evaluationType, isInteger);
371        }
372
373        // Simplify addition and subtraction between same types.
374        if (op == CalcAdd || op == CalcSubtract) {
375            if (leftCategory == rightSide->category()) {
376                CSSPrimitiveValue::UnitTypes leftType = leftSide->primitiveType();
377                if (hasDoubleValue(leftType)) {
378                    CSSPrimitiveValue::UnitTypes rightType = rightSide->primitiveType();
379                    if (leftType == rightType)
380                        return CSSCalcPrimitiveValue::create(evaluateOperator(op, leftSide->doubleValue(), rightSide->doubleValue()), leftType, isInteger);
381                    CSSPrimitiveValue::UnitCategory leftUnitCategory = CSSPrimitiveValue::unitCategory(leftType);
382                    if (leftUnitCategory != CSSPrimitiveValue::UOther && leftUnitCategory == CSSPrimitiveValue::unitCategory(rightType)) {
383                        CSSPrimitiveValue::UnitTypes canonicalType = CSSPrimitiveValue::canonicalUnitTypeForCategory(leftUnitCategory);
384                        if (canonicalType != CSSPrimitiveValue::CSS_UNKNOWN) {
385                            double leftValue = leftSide->doubleValue() * CSSPrimitiveValue::conversionToCanonicalUnitsScaleFactor(leftType);
386                            double rightValue = rightSide->doubleValue() * CSSPrimitiveValue::conversionToCanonicalUnitsScaleFactor(rightType);
387                            return CSSCalcPrimitiveValue::create(evaluateOperator(op, leftValue, rightValue), canonicalType, isInteger);
388                        }
389                    }
390                }
391            }
392        } else {
393            // Simplify multiplying or dividing by a number for simplifiable types.
394            ASSERT(op == CalcMultiply || op == CalcDivide);
395            CSSCalcExpressionNode* numberSide = getNumberSide(*leftSide, *rightSide);
396            if (!numberSide)
397                return create(op, leftSide, rightSide);
398            if (numberSide == leftSide && op == CalcDivide)
399                return nullptr;
400            CSSCalcExpressionNode* otherSide = leftSide == numberSide ? rightSide.get() : leftSide.get();
401
402            double number = numberSide->doubleValue();
403            if (std::isnan(number) || std::isinf(number))
404                return nullptr;
405            if (op == CalcDivide && !number)
406                return nullptr;
407
408            CSSPrimitiveValue::UnitTypes otherType = otherSide->primitiveType();
409            if (hasDoubleValue(otherType))
410                return CSSCalcPrimitiveValue::create(evaluateOperator(op, otherSide->doubleValue(), number), otherType, isInteger);
411        }
412
413        return create(op, leftSide, rightSide);
414    }
415
416private:
417    virtual bool isZero() const override
418    {
419        return !doubleValue();
420    }
421
422    virtual std::unique_ptr<CalcExpressionNode> createCalcExpression(const CSSToLengthConversionData& conversionData) const override
423    {
424        std::unique_ptr<CalcExpressionNode> left(m_leftSide->createCalcExpression(conversionData));
425        if (!left)
426            return nullptr;
427        std::unique_ptr<CalcExpressionNode> right(m_rightSide->createCalcExpression(conversionData));
428        if (!right)
429            return nullptr;
430        return std::make_unique<CalcExpressionBinaryOperation>(WTF::move(left), WTF::move(right), m_operator);
431    }
432
433    virtual double doubleValue() const override
434    {
435        return evaluate(m_leftSide->doubleValue(), m_rightSide->doubleValue());
436    }
437
438    virtual double computeLengthPx(const CSSToLengthConversionData& conversionData) const override
439    {
440        const double leftValue = m_leftSide->computeLengthPx(conversionData);
441        const double rightValue = m_rightSide->computeLengthPx(conversionData);
442        return evaluate(leftValue, rightValue);
443    }
444
445    static String buildCssText(const String& leftExpression, const String& rightExpression, CalcOperator op)
446    {
447        StringBuilder result;
448        result.append('(');
449        result.append(leftExpression);
450        result.append(' ');
451        result.append(static_cast<char>(op));
452        result.append(' ');
453        result.append(rightExpression);
454        result.append(')');
455
456        return result.toString();
457    }
458
459    virtual String customCSSText() const override
460    {
461        return buildCssText(m_leftSide->customCSSText(), m_rightSide->customCSSText(), m_operator);
462    }
463
464    virtual bool equals(const CSSCalcExpressionNode& exp) const override
465    {
466        if (type() != exp.type())
467            return false;
468
469        const CSSCalcBinaryOperation& other = static_cast<const CSSCalcBinaryOperation&>(exp);
470        return compareCSSValuePtr(m_leftSide, other.m_leftSide)
471            && compareCSSValuePtr(m_rightSide, other.m_rightSide)
472            && m_operator == other.m_operator;
473    }
474
475    virtual Type type() const override { return CssCalcBinaryOperation; }
476
477    virtual CSSPrimitiveValue::UnitTypes primitiveType() const override
478    {
479        switch (category()) {
480        case CalcNumber:
481            ASSERT(m_leftSide->category() == CalcNumber && m_rightSide->category() == CalcNumber);
482            if (isInteger())
483                return CSSPrimitiveValue::CSS_PARSER_INTEGER;
484            return CSSPrimitiveValue::CSS_NUMBER;
485        case CalcLength:
486        case CalcPercent: {
487            if (m_leftSide->category() == CalcNumber)
488                return m_rightSide->primitiveType();
489            if (m_rightSide->category() == CalcNumber)
490                return m_leftSide->primitiveType();
491            CSSPrimitiveValue::UnitTypes leftType = m_leftSide->primitiveType();
492            if (leftType == m_rightSide->primitiveType())
493                return leftType;
494            return CSSPrimitiveValue::CSS_UNKNOWN;
495        }
496        case CalcAngle:
497            return CSSPrimitiveValue::CSS_DEG;
498        case CalcTime:
499            return CSSPrimitiveValue::CSS_MS;
500        case CalcFrequency:
501            return CSSPrimitiveValue::CSS_HZ;
502        case CalcPercentLength:
503        case CalcPercentNumber:
504        case CalcOther:
505            return CSSPrimitiveValue::CSS_UNKNOWN;
506        }
507        ASSERT_NOT_REACHED();
508        return CSSPrimitiveValue::CSS_UNKNOWN;
509    }
510
511    CSSCalcBinaryOperation(CalculationCategory category, CalcOperator op, PassRefPtr<CSSCalcExpressionNode> leftSide, PassRefPtr<CSSCalcExpressionNode> rightSide)
512        : CSSCalcExpressionNode(category, isIntegerResult(op, *leftSide, *rightSide))
513        , m_leftSide(leftSide)
514        , m_rightSide(rightSide)
515        , m_operator(op)
516    {
517    }
518
519    static CSSCalcExpressionNode* getNumberSide(CSSCalcExpressionNode& leftSide, CSSCalcExpressionNode& rightSide)
520    {
521        if (leftSide.category() == CalcNumber)
522            return &leftSide;
523        if (rightSide.category() == CalcNumber)
524            return &rightSide;
525        return nullptr;
526    }
527
528    double evaluate(double leftSide, double rightSide) const
529    {
530        return evaluateOperator(m_operator, leftSide, rightSide);
531    }
532
533    static double evaluateOperator(CalcOperator op, double leftValue, double rightValue)
534    {
535        switch (op) {
536        case CalcAdd:
537            return leftValue + rightValue;
538        case CalcSubtract:
539            return leftValue - rightValue;
540        case CalcMultiply:
541            return leftValue * rightValue;
542        case CalcDivide:
543            if (rightValue)
544                return leftValue / rightValue;
545            return std::numeric_limits<double>::quiet_NaN();
546        }
547        ASSERT_NOT_REACHED();
548        return 0;
549    }
550
551    const RefPtr<CSSCalcExpressionNode> m_leftSide;
552    const RefPtr<CSSCalcExpressionNode> m_rightSide;
553    const CalcOperator m_operator;
554};
555
556static ParseState checkDepthAndIndex(int* depth, unsigned index, CSSParserValueList* tokens)
557{
558    (*depth)++;
559    if (*depth > maxExpressionDepth)
560        return TooDeep;
561    if (index >= tokens->size())
562        return NoMoreTokens;
563    return OK;
564}
565
566class CSSCalcExpressionNodeParser {
567public:
568    PassRefPtr<CSSCalcExpressionNode> parseCalc(CSSParserValueList* tokens)
569    {
570        unsigned index = 0;
571        Value result;
572        bool ok = parseValueExpression(tokens, 0, &index, &result);
573        ASSERT_WITH_SECURITY_IMPLICATION(index <= tokens->size());
574        if (!ok || index != tokens->size())
575            return nullptr;
576        return result.value;
577    }
578
579private:
580    struct Value {
581        RefPtr<CSSCalcExpressionNode> value;
582    };
583
584    char operatorValue(CSSParserValueList* tokens, unsigned index)
585    {
586        if (index >= tokens->size())
587            return 0;
588        CSSParserValue* value = tokens->valueAt(index);
589        if (value->unit != CSSParserValue::Operator)
590            return 0;
591
592        return value->iValue;
593    }
594
595    bool parseValue(CSSParserValueList* tokens, unsigned* index, Value* result)
596    {
597        CSSParserValue* parserValue = tokens->valueAt(*index);
598        if (parserValue->unit == CSSParserValue::Operator || parserValue->unit == CSSParserValue::Function)
599            return false;
600
601        RefPtr<CSSValue> value = parserValue->createCSSValue();
602        if (!value || !value->isPrimitiveValue())
603            return false;
604
605        CSSPrimitiveValue* primitiveValue = toCSSPrimitiveValue(value.get());
606        result->value = CSSCalcPrimitiveValue::create(primitiveValue, parserValue->isInt);
607
608        ++*index;
609        return true;
610    }
611
612    bool parseValueTerm(CSSParserValueList* tokens, int depth, unsigned* index, Value* result)
613    {
614        if (checkDepthAndIndex(&depth, *index, tokens) != OK)
615            return false;
616
617        if (operatorValue(tokens, *index) == '(') {
618            unsigned currentIndex = *index + 1;
619            if (!parseValueExpression(tokens, depth, &currentIndex, result))
620                return false;
621
622            if (operatorValue(tokens, currentIndex) != ')')
623                return false;
624            *index = currentIndex + 1;
625            return true;
626        }
627
628        return parseValue(tokens, index, result);
629    }
630
631    bool parseValueMultiplicativeExpression(CSSParserValueList* tokens, int depth, unsigned* index, Value* result)
632    {
633        if (checkDepthAndIndex(&depth, *index, tokens) != OK)
634            return false;
635
636        if (!parseValueTerm(tokens, depth, index, result))
637            return false;
638
639        while (*index < tokens->size() - 1) {
640            char operatorCharacter = operatorValue(tokens, *index);
641            if (operatorCharacter != CalcMultiply && operatorCharacter != CalcDivide)
642                break;
643            ++*index;
644
645            Value rhs;
646            if (!parseValueTerm(tokens, depth, index, &rhs))
647                return false;
648
649            result->value = CSSCalcBinaryOperation::createSimplified(static_cast<CalcOperator>(operatorCharacter), result->value, rhs.value);
650            if (!result->value)
651                return false;
652        }
653
654        ASSERT_WITH_SECURITY_IMPLICATION(*index <= tokens->size());
655        return true;
656    }
657
658    bool parseAdditiveValueExpression(CSSParserValueList* tokens, int depth, unsigned* index, Value* result)
659    {
660        if (checkDepthAndIndex(&depth, *index, tokens) != OK)
661            return false;
662
663        if (!parseValueMultiplicativeExpression(tokens, depth, index, result))
664            return false;
665
666        while (*index < tokens->size() - 1) {
667            char operatorCharacter = operatorValue(tokens, *index);
668            if (operatorCharacter != CalcAdd && operatorCharacter != CalcSubtract)
669                break;
670            ++*index;
671
672            Value rhs;
673            if (!parseValueMultiplicativeExpression(tokens, depth, index, &rhs))
674                return false;
675
676            result->value = CSSCalcBinaryOperation::createSimplified(static_cast<CalcOperator>(operatorCharacter), result->value, rhs.value);
677            if (!result->value)
678                return false;
679        }
680
681        ASSERT_WITH_SECURITY_IMPLICATION(*index <= tokens->size());
682        return true;
683    }
684
685    bool parseValueExpression(CSSParserValueList* tokens, int depth, unsigned* index, Value* result)
686    {
687        return parseAdditiveValueExpression(tokens, depth, index, result);
688    }
689};
690
691static inline PassRefPtr<CSSCalcBinaryOperation> createBlendHalf(const Length& length, const RenderStyle& style, float progress)
692{
693    return CSSCalcBinaryOperation::create(CalcMultiply, createCSS(length, style),
694        CSSCalcPrimitiveValue::create(CSSPrimitiveValue::create(progress, CSSPrimitiveValue::CSS_NUMBER), !progress || progress == 1));
695}
696
697static PassRefPtr<CSSCalcExpressionNode> createCSS(const CalcExpressionNode& node, const RenderStyle& style)
698{
699    switch (node.type()) {
700    case CalcExpressionNodeNumber: {
701        float value = toCalcExpressionNumber(node).value();
702        return CSSCalcPrimitiveValue::create(CSSPrimitiveValue::create(value, CSSPrimitiveValue::CSS_NUMBER), value == truncf(value));
703    }
704    case CalcExpressionNodeLength:
705        return createCSS(toCalcExpressionLength(node).length(), style);
706    case CalcExpressionNodeBinaryOperation: {
707        auto& binaryNode = toCalcExpressionBinaryOperation(node);
708        return CSSCalcBinaryOperation::create(binaryNode.getOperator(), createCSS(binaryNode.leftSide(), style), createCSS(binaryNode.rightSide(), style));
709    }
710    case CalcExpressionNodeBlendLength: {
711        // FIXME: (http://webkit.org/b/122036) Create a CSSCalcExpressionNode equivalent of CalcExpressionBlendLength.
712        auto& blend = toCalcExpressionBlendLength(node);
713        float progress = blend.progress();
714        return CSSCalcBinaryOperation::create(CalcAdd, createBlendHalf(blend.from(), style, 1 - progress), createBlendHalf(blend.to(), style, progress));
715    }
716    case CalcExpressionNodeUndefined:
717        ASSERT_NOT_REACHED();
718        return nullptr;
719    }
720    ASSERT_NOT_REACHED();
721    return nullptr;
722}
723
724static PassRefPtr<CSSCalcExpressionNode> createCSS(const Length& length, const RenderStyle& style)
725{
726    switch (length.type()) {
727    case Percent:
728    case Fixed:
729        return CSSCalcPrimitiveValue::create(CSSPrimitiveValue::create(length, &style), length.value() == trunc(length.value()));
730    case Calculated:
731        return createCSS(length.calculationValue().expression(), style);
732    case Auto:
733    case Intrinsic:
734    case MinIntrinsic:
735    case MinContent:
736    case MaxContent:
737    case FillAvailable:
738    case FitContent:
739    case Relative:
740    case Undefined:
741        ASSERT_NOT_REACHED();
742        return nullptr;
743    }
744    ASSERT_NOT_REACHED();
745    return nullptr;
746}
747
748PassRefPtr<CSSCalcValue> CSSCalcValue::create(CSSParserString name, CSSParserValueList& parserValueList, CalculationPermittedValueRange range)
749{
750    CSSCalcExpressionNodeParser parser;
751    RefPtr<CSSCalcExpressionNode> expression;
752
753    if (equalIgnoringCase(name, "calc(") || equalIgnoringCase(name, "-webkit-calc("))
754        expression = parser.parseCalc(&parserValueList);
755    // FIXME: calc (http://webkit.org/b/16662) Add parsing for min and max here
756
757    return expression ? adoptRef(new CSSCalcValue(expression.releaseNonNull(), range != CalculationRangeAll)) : nullptr;
758}
759
760PassRefPtr<CSSCalcValue> CSSCalcValue::create(const CalculationValue& value, const RenderStyle& style)
761{
762    RefPtr<CSSCalcExpressionNode> expression = createCSS(value.expression(), style);
763    if (!expression)
764        return nullptr;
765    return adoptRef(new CSSCalcValue(expression.releaseNonNull(), value.shouldClampToNonNegative()));
766}
767
768} // namespace WebCore
769