b75830107eff1b8e05a9128cce75ad7d43a5399f
[WebKit-https.git] / Source / WebCore / css / CSSCalculationValue.cpp
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 "CSSParser.h"
36 #include "CSSParserTokenRange.h"
37 #include "CSSPrimitiveValueMappings.h"
38 #include "StyleResolver.h"
39 #include <wtf/MathExtras.h>
40 #include <wtf/text/StringBuilder.h>
41
42 static const int maxExpressionDepth = 100;
43
44 enum ParseState {
45     OK,
46     TooDeep,
47     NoMoreTokens
48 };
49
50 namespace WebCore {
51
52 static RefPtr<CSSCalcExpressionNode> createCSS(const CalcExpressionNode&, const RenderStyle&);
53 static RefPtr<CSSCalcExpressionNode> createCSS(const Length&, const RenderStyle&);
54
55 static CalculationCategory unitCategory(CSSPrimitiveValue::UnitType type)
56 {
57     switch (type) {
58     case CSSPrimitiveValue::CSS_NUMBER:
59         return CalcNumber;
60     case CSSPrimitiveValue::CSS_EMS:
61     case CSSPrimitiveValue::CSS_EXS:
62     case CSSPrimitiveValue::CSS_PX:
63     case CSSPrimitiveValue::CSS_CM:
64     case CSSPrimitiveValue::CSS_MM:
65     case CSSPrimitiveValue::CSS_IN:
66     case CSSPrimitiveValue::CSS_PT:
67     case CSSPrimitiveValue::CSS_PC:
68     case CSSPrimitiveValue::CSS_REMS:
69     case CSSPrimitiveValue::CSS_CHS:
70     case CSSPrimitiveValue::CSS_VW:
71     case CSSPrimitiveValue::CSS_VH:
72     case CSSPrimitiveValue::CSS_VMIN:
73     case CSSPrimitiveValue::CSS_VMAX:
74         return CalcLength;
75     case CSSPrimitiveValue::CSS_PERCENTAGE:
76         return CalcPercent;
77     case CSSPrimitiveValue::CSS_DEG:
78     case CSSPrimitiveValue::CSS_RAD:
79     case CSSPrimitiveValue::CSS_GRAD:
80     case CSSPrimitiveValue::CSS_TURN:
81         return CalcAngle;
82     case CSSPrimitiveValue::CSS_MS:
83     case CSSPrimitiveValue::CSS_S:
84         return CalcTime;
85     case CSSPrimitiveValue::CSS_HZ:
86     case CSSPrimitiveValue::CSS_KHZ:
87         return CalcFrequency;
88     default:
89         return CalcOther;
90     }
91 }
92
93 static bool hasDoubleValue(CSSPrimitiveValue::UnitType type)
94 {
95     switch (type) {
96     case CSSPrimitiveValue::CSS_FR:
97     case CSSPrimitiveValue::CSS_NUMBER:
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_TURN:
113     case CSSPrimitiveValue::CSS_MS:
114     case CSSPrimitiveValue::CSS_S:
115     case CSSPrimitiveValue::CSS_HZ:
116     case CSSPrimitiveValue::CSS_KHZ:
117     case CSSPrimitiveValue::CSS_DIMENSION:
118     case CSSPrimitiveValue::CSS_VW:
119     case CSSPrimitiveValue::CSS_VH:
120     case CSSPrimitiveValue::CSS_VMIN:
121     case CSSPrimitiveValue::CSS_VMAX:
122     case CSSPrimitiveValue::CSS_DPPX:
123     case CSSPrimitiveValue::CSS_DPI:
124     case CSSPrimitiveValue::CSS_DPCM:
125         return true;
126     case CSSPrimitiveValue::CSS_UNKNOWN:
127     case CSSPrimitiveValue::CSS_STRING:
128     case CSSPrimitiveValue::CSS_FONT_FAMILY:
129     case CSSPrimitiveValue::CSS_URI:
130     case CSSPrimitiveValue::CSS_IDENT:
131     case CSSPrimitiveValue::CSS_ATTR:
132     case CSSPrimitiveValue::CSS_COUNTER:
133     case CSSPrimitiveValue::CSS_RECT:
134     case CSSPrimitiveValue::CSS_RGBCOLOR:
135     case CSSPrimitiveValue::CSS_PAIR:
136     case CSSPrimitiveValue::CSS_UNICODE_RANGE:
137     case CSSPrimitiveValue::CSS_COUNTER_NAME:
138     case CSSPrimitiveValue::CSS_SHAPE:
139     case CSSPrimitiveValue::CSS_QUAD:
140     case CSSPrimitiveValue::CSS_QUIRKY_EMS:
141     case CSSPrimitiveValue::CSS_CALC:
142     case CSSPrimitiveValue::CSS_CALC_PERCENTAGE_WITH_NUMBER:
143     case CSSPrimitiveValue::CSS_CALC_PERCENTAGE_WITH_LENGTH:
144     case CSSPrimitiveValue::CSS_PROPERTY_ID:
145     case CSSPrimitiveValue::CSS_VALUE_ID:
146 #if ENABLE(DASHBOARD_SUPPORT)
147     case CSSPrimitiveValue::CSS_DASHBOARD_REGION:
148 #endif
149         return false;
150     };
151     ASSERT_NOT_REACHED();
152     return false;
153 }
154
155 static String buildCssText(const String& expression)
156 {
157     StringBuilder result;
158     result.appendLiteral("calc");
159     bool expressionHasSingleTerm = expression[0] != '(';
160     if (expressionHasSingleTerm)
161         result.append('(');
162     result.append(expression);
163     if (expressionHasSingleTerm)
164         result.append(')');
165     return result.toString();
166 }
167
168 String CSSCalcValue::customCSSText() const
169 {
170     return buildCssText(m_expression->customCSSText());
171 }
172
173 bool CSSCalcValue::equals(const CSSCalcValue& other) const
174 {
175     return compareCSSValue(m_expression, other.m_expression);
176 }
177
178 inline double CSSCalcValue::clampToPermittedRange(double value) const
179 {
180     return m_shouldClampToNonNegative && value < 0 ? 0 : value;
181 }
182
183 double CSSCalcValue::doubleValue() const
184 {
185     return clampToPermittedRange(m_expression->doubleValue());
186 }
187
188 double CSSCalcValue::computeLengthPx(const CSSToLengthConversionData& conversionData) const
189 {
190     return clampToPermittedRange(m_expression->computeLengthPx(conversionData));
191 }
192
193 class CSSCalcPrimitiveValue final : public CSSCalcExpressionNode {
194     WTF_MAKE_FAST_ALLOCATED;
195 public:
196     static Ref<CSSCalcPrimitiveValue> create(Ref<CSSPrimitiveValue>&& value, bool isInteger)
197     {
198         return adoptRef(*new CSSCalcPrimitiveValue(WTFMove(value), isInteger));
199     }
200
201     static RefPtr<CSSCalcPrimitiveValue> create(double value, CSSPrimitiveValue::UnitType type, bool isInteger)
202     {
203         if (!std::isfinite(value))
204             return nullptr;
205         return adoptRef(new CSSCalcPrimitiveValue(CSSPrimitiveValue::create(value, type), isInteger));
206     }
207
208 private:
209     bool isZero() const final
210     {
211         return !m_value->doubleValue();
212     }
213
214     String customCSSText() const final
215     {
216         return m_value->cssText();
217     }
218
219     std::unique_ptr<CalcExpressionNode> createCalcExpression(const CSSToLengthConversionData& conversionData) const final
220     {
221         switch (category()) {
222         case CalcNumber:
223             return std::make_unique<CalcExpressionNumber>(m_value->floatValue());
224         case CalcLength:
225             return std::make_unique<CalcExpressionLength>(Length(m_value->computeLength<float>(conversionData), WebCore::Fixed));
226         case CalcPercent:
227         case CalcPercentLength: {
228             return std::make_unique<CalcExpressionLength>(m_value->convertToLength<FixedFloatConversion | PercentConversion>(conversionData));
229         }
230         // Only types that could be part of a Length expression can be converted
231         // to a CalcExpressionNode. CalcPercentNumber makes no sense as a Length.
232         case CalcPercentNumber:
233         case CalcAngle:
234         case CalcTime:
235         case CalcFrequency:
236         case CalcOther:
237             ASSERT_NOT_REACHED();
238         }
239         ASSERT_NOT_REACHED();
240         return nullptr;
241     }
242
243     double doubleValue() const final
244     {
245         if (hasDoubleValue(primitiveType()))
246             return m_value->doubleValue();
247         ASSERT_NOT_REACHED();
248         return 0;
249     }
250
251     double computeLengthPx(const CSSToLengthConversionData& conversionData) const final
252     {
253         switch (category()) {
254         case CalcLength:
255             return m_value->computeLength<double>(conversionData);
256         case CalcPercent:
257         case CalcNumber:
258             return m_value->doubleValue();
259         case CalcPercentLength:
260         case CalcPercentNumber:
261         case CalcAngle:
262         case CalcTime:
263         case CalcFrequency:
264         case CalcOther:
265             ASSERT_NOT_REACHED();
266             break;
267         }
268         ASSERT_NOT_REACHED();
269         return 0;
270     }
271
272     bool equals(const CSSCalcExpressionNode& other) const final
273     {
274         if (type() != other.type())
275             return false;
276
277         return compareCSSValue(m_value, static_cast<const CSSCalcPrimitiveValue&>(other).m_value);
278     }
279
280     Type type() const final { return CssCalcPrimitiveValue; }
281     CSSPrimitiveValue::UnitType primitiveType() const final
282     {
283         return CSSPrimitiveValue::UnitType(m_value->primitiveType());
284     }
285
286 private:
287     explicit CSSCalcPrimitiveValue(Ref<CSSPrimitiveValue>&& value, bool isInteger)
288         : CSSCalcExpressionNode(unitCategory((CSSPrimitiveValue::UnitType)value->primitiveType()), isInteger)
289         , m_value(WTFMove(value))
290     {
291     }
292
293     Ref<CSSPrimitiveValue> m_value;
294 };
295
296 static const CalculationCategory addSubtractResult[CalcAngle][CalcAngle] = {
297 //    CalcNumber         CalcLength         CalcPercent        CalcPercentNumber  CalcPercentLength
298     { CalcNumber,        CalcOther,         CalcPercentNumber, CalcPercentNumber, CalcOther }, //         CalcNumber
299     { CalcOther,         CalcLength,        CalcPercentLength, CalcOther,         CalcPercentLength }, // CalcLength
300     { CalcPercentNumber, CalcPercentLength, CalcPercent,       CalcPercentNumber, CalcPercentLength }, // CalcPercent
301     { CalcPercentNumber, CalcOther,         CalcPercentNumber, CalcPercentNumber, CalcOther }, //         CalcPercentNumber
302     { CalcOther,         CalcPercentLength, CalcPercentLength, CalcOther,         CalcPercentLength }, // CalcPercentLength
303 };
304
305 static CalculationCategory determineCategory(const CSSCalcExpressionNode& leftSide, const CSSCalcExpressionNode& rightSide, CalcOperator op)
306 {
307     CalculationCategory leftCategory = leftSide.category();
308     CalculationCategory rightCategory = rightSide.category();
309     ASSERT(leftCategory < CalcOther);
310     ASSERT(rightCategory < CalcOther);
311
312     switch (op) {
313     case CalcAdd:
314     case CalcSubtract:
315         if (leftCategory < CalcAngle && rightCategory < CalcAngle)
316             return addSubtractResult[leftCategory][rightCategory];
317         if (leftCategory == rightCategory)
318             return leftCategory;
319         return CalcOther;
320     case CalcMultiply:
321         if (leftCategory != CalcNumber && rightCategory != CalcNumber)
322             return CalcOther;
323         return leftCategory == CalcNumber ? rightCategory : leftCategory;
324     case CalcDivide:
325         if (rightCategory != CalcNumber || rightSide.isZero())
326             return CalcOther;
327         return leftCategory;
328     case CalcMin:
329     case CalcMax:
330         ASSERT_NOT_REACHED();
331         return CalcOther;
332     }
333
334     ASSERT_NOT_REACHED();
335     return CalcOther;
336 }
337
338 static CalculationCategory resolvedTypeForMinOrMax(CalculationCategory category, CalculationCategory destinationCategory)
339 {
340     switch (category) {
341     case CalcNumber:
342     case CalcLength:
343     case CalcPercentNumber:
344     case CalcPercentLength:
345     case CalcAngle:
346     case CalcTime:
347     case CalcFrequency:
348     case CalcOther:
349         return category;
350
351     case CalcPercent:
352         if (destinationCategory == CalcLength)
353             return CalcPercentLength;
354         if (destinationCategory == CalcNumber)
355             return CalcPercentNumber;
356         return category;
357     }
358
359     return CalcOther;
360 }
361
362 static inline bool isIntegerResult(CalcOperator op, const CSSCalcExpressionNode& leftSide, const CSSCalcExpressionNode& rightSide)
363 {
364     // Performs W3C spec's type checking for calc integers.
365     // http://www.w3.org/TR/css3-values/#calc-type-checking
366     return op != CalcDivide && leftSide.isInteger() && rightSide.isInteger();
367 }
368
369 static inline bool isIntegerResult(CalcOperator op, const Vector<Ref<CSSCalcExpressionNode>>& nodes)
370 {
371     // Performs W3C spec's type checking for calc integers.
372     // http://www.w3.org/TR/css3-values/#calc-type-checking
373     if (op == CalcDivide)
374         return false;
375
376     for (auto& node : nodes) {
377         if (!node->isInteger())
378             return false;
379     }
380
381     return true;
382 }
383
384 static bool isSamePair(CalculationCategory a, CalculationCategory b, CalculationCategory x, CalculationCategory y)
385 {
386     return (a == x && b == y) || (a == y && b == x);
387 }
388
389 class CSSCalcOperation final : public CSSCalcExpressionNode {
390     WTF_MAKE_FAST_ALLOCATED;
391 public:
392     static RefPtr<CSSCalcOperation> create(CalcOperator op, RefPtr<CSSCalcExpressionNode>&& leftSide, RefPtr<CSSCalcExpressionNode>&& rightSide)
393     {
394         if (!leftSide || !rightSide)
395             return nullptr;
396
397         ASSERT(leftSide->category() < CalcOther);
398         ASSERT(rightSide->category() < CalcOther);
399
400         auto newCategory = determineCategory(*leftSide, *rightSide, op);
401         if (newCategory == CalcOther)
402             return nullptr;
403
404         return adoptRef(new CSSCalcOperation(newCategory, op, leftSide.releaseNonNull(), rightSide.releaseNonNull()));
405     }
406
407     static RefPtr<CSSCalcOperation> createMinOrMax(CalcOperator op, Vector<Ref<CSSCalcExpressionNode>>&& values, CalculationCategory destinationCategory)
408     {
409         ASSERT(op == CalcMin || op == CalcMax);
410
411         std::optional<CalculationCategory> category = std::nullopt;
412         for (auto& value : values) {
413             auto valueCategory = resolvedTypeForMinOrMax(value->category(), destinationCategory);
414
415             ASSERT(valueCategory < CalcOther);
416             if (!category) {
417                 if (valueCategory == CalcOther)
418                     return nullptr;
419                 category = valueCategory;
420             }
421
422             if (category != valueCategory) {
423                 if (isSamePair(category.value(), valueCategory, CalcLength, CalcPercentLength)) {
424                     category = CalcPercentLength;
425                     continue;
426                 }
427                 if (isSamePair(category.value(), valueCategory, CalcNumber, CalcPercentNumber)) {
428                     category = CalcPercentNumber;
429                     continue;
430                 }
431                 return nullptr;
432             }
433         }
434
435         return adoptRef(new CSSCalcOperation(category.value(), op, WTFMove(values)));
436     }
437
438     static RefPtr<CSSCalcExpressionNode> createSimplified(CalcOperator op, RefPtr<CSSCalcExpressionNode>&& leftSide, RefPtr<CSSCalcExpressionNode>&& rightSide)
439     {
440         if (!leftSide || !rightSide)
441             return nullptr;
442
443         auto leftCategory = leftSide->category();
444         auto rightCategory = rightSide->category();
445         ASSERT(leftCategory < CalcOther);
446         ASSERT(rightCategory < CalcOther);
447
448         bool isInteger = isIntegerResult(op, *leftSide, *rightSide);
449
450         // Simplify numbers.
451         if (leftCategory == CalcNumber && rightCategory == CalcNumber) {
452             CSSPrimitiveValue::UnitType evaluationType = CSSPrimitiveValue::CSS_NUMBER;
453             return CSSCalcPrimitiveValue::create(evaluateOperator(op, { leftSide->doubleValue(), rightSide->doubleValue() }), evaluationType, isInteger);
454         }
455
456         // Simplify addition and subtraction between same types.
457         if (op == CalcAdd || op == CalcSubtract) {
458             if (leftCategory == rightSide->category()) {
459                 CSSPrimitiveValue::UnitType leftType = leftSide->primitiveType();
460                 if (hasDoubleValue(leftType)) {
461                     CSSPrimitiveValue::UnitType rightType = rightSide->primitiveType();
462                     if (leftType == rightType)
463                         return CSSCalcPrimitiveValue::create(evaluateOperator(op, { leftSide->doubleValue(), rightSide->doubleValue() }), leftType, isInteger);
464                     CSSPrimitiveValue::UnitCategory leftUnitCategory = CSSPrimitiveValue::unitCategory(leftType);
465                     if (leftUnitCategory != CSSPrimitiveValue::UOther && leftUnitCategory == CSSPrimitiveValue::unitCategory(rightType)) {
466                         CSSPrimitiveValue::UnitType canonicalType = CSSPrimitiveValue::canonicalUnitTypeForCategory(leftUnitCategory);
467                         if (canonicalType != CSSPrimitiveValue::CSS_UNKNOWN) {
468                             double leftValue = leftSide->doubleValue() * CSSPrimitiveValue::conversionToCanonicalUnitsScaleFactor(leftType);
469                             double rightValue = rightSide->doubleValue() * CSSPrimitiveValue::conversionToCanonicalUnitsScaleFactor(rightType);
470                             return CSSCalcPrimitiveValue::create(evaluateOperator(op, { leftValue, rightValue }), canonicalType, isInteger);
471                         }
472                     }
473                 }
474             }
475         } else {
476             // Simplify multiplying or dividing by a number for simplifiable types.
477             ASSERT(op == CalcMultiply || op == CalcDivide);
478             auto* numberSide = getNumberSide(*leftSide, *rightSide);
479             if (!numberSide)
480                 return create(op, leftSide.releaseNonNull(), rightSide.releaseNonNull());
481             if (numberSide == leftSide && op == CalcDivide)
482                 return nullptr;
483             auto& otherSide = leftSide == numberSide ? *rightSide : *leftSide;
484
485             double number = numberSide->doubleValue();
486             if (!std::isfinite(number))
487                 return nullptr;
488             if (op == CalcDivide && !number)
489                 return nullptr;
490
491             auto otherType = otherSide.primitiveType();
492             if (hasDoubleValue(otherType))
493                 return CSSCalcPrimitiveValue::create(evaluateOperator(op, { otherSide.doubleValue(), number }), otherType, isInteger);
494         }
495
496         return create(op, leftSide.releaseNonNull(), rightSide.releaseNonNull());
497     }
498
499 private:
500     bool isZero() const final
501     {
502         return !doubleValue();
503     }
504
505     std::unique_ptr<CalcExpressionNode> createCalcExpression(const CSSToLengthConversionData& conversionData) const final
506     {
507         Vector<std::unique_ptr<CalcExpressionNode>> nodes;
508         nodes.reserveInitialCapacity(m_children.size());
509
510         for (auto& child : m_children) {
511             auto node = child->createCalcExpression(conversionData);
512             if (!node)
513                 return nullptr;
514             nodes.uncheckedAppend(WTFMove(node));
515         }
516         return std::make_unique<CalcExpressionOperation>(WTFMove(nodes), m_operator);
517     }
518
519     double doubleValue() const final
520     {
521         Vector<double> doubleValues;
522         for (auto& child : m_children)
523             doubleValues.append(child->doubleValue());
524         return evaluate(doubleValues);
525     }
526
527     double computeLengthPx(const CSSToLengthConversionData& conversionData) const final
528     {
529         Vector<double> doubleValues;
530         for (auto& child : m_children)
531             doubleValues.append(child->computeLengthPx(conversionData));
532         return evaluate(doubleValues);
533     }
534
535     static String buildCssText(Vector<String> childExpressions, CalcOperator op)
536     {
537         StringBuilder result;
538         result.append('(');
539         switch (op) {
540         case CalcAdd:
541         case CalcSubtract:
542         case CalcMultiply:
543         case CalcDivide:
544             ASSERT(childExpressions.size() == 2);
545             result.append(childExpressions[0]);
546             result.append(' ');
547             result.append(static_cast<char>(op));
548             result.append(' ');
549             result.append(childExpressions[1]);
550             break;
551         case CalcMin:
552         case CalcMax:
553             ASSERT(!childExpressions.isEmpty());
554             const char* functionName = op == CalcMin ? "min(" : "max(";
555             result.append(functionName);
556             result.append(childExpressions[0]);
557             for (size_t i = 1; i < childExpressions.size(); ++i) {
558                 result.append(',');
559                 result.append(' ');
560                 result.append(childExpressions[i]);
561             }
562             result.append(')');
563         }
564         result.append(')');
565
566         return result.toString();
567     }
568
569     String customCSSText() const final
570     {
571         Vector<String> cssTexts;
572         for (auto& child : m_children)
573             cssTexts.append(child->customCSSText());
574         return buildCssText(cssTexts, m_operator);
575     }
576
577     bool equals(const CSSCalcExpressionNode& exp) const final
578     {
579         if (type() != exp.type())
580             return false;
581
582         const CSSCalcOperation& other = static_cast<const CSSCalcOperation&>(exp);
583
584         if (m_children.size() != other.m_children.size() || m_operator != other.m_operator)
585             return false;
586
587         for (size_t i = 0; i < m_children.size(); ++i) {
588             if (!compareCSSValue(m_children[i], other.m_children[i]))
589                 return false;
590         }
591         return true;
592     }
593
594     Type type() const final { return CssCalcOperation; }
595
596     CSSPrimitiveValue::UnitType primitiveType() const final
597     {
598         switch (category()) {
599         case CalcNumber:
600 #if !ASSERT_DISABLED
601             for (auto& child : m_children)
602                 ASSERT(child->category() == CalcNumber);
603 #endif
604             return CSSPrimitiveValue::CSS_NUMBER;
605         case CalcLength:
606         case CalcPercent: {
607             if (m_children.isEmpty())
608                 return CSSPrimitiveValue::CSS_UNKNOWN;
609             if (m_children.size() == 2) {
610                 if (m_children[0]->category() == CalcNumber)
611                     return m_children[1]->primitiveType();
612                 if (m_children[1]->category() == CalcNumber)
613                     return m_children[0]->primitiveType();
614             }
615             CSSPrimitiveValue::UnitType firstType = m_children[0]->primitiveType();
616             for (auto& child : m_children) {
617                 if (firstType != child->primitiveType())
618                     return CSSPrimitiveValue::CSS_UNKNOWN;
619             }
620             return firstType;
621         }
622         case CalcAngle:
623             return CSSPrimitiveValue::CSS_DEG;
624         case CalcTime:
625             return CSSPrimitiveValue::CSS_MS;
626         case CalcFrequency:
627             return CSSPrimitiveValue::CSS_HZ;
628         case CalcPercentLength:
629         case CalcPercentNumber:
630         case CalcOther:
631             return CSSPrimitiveValue::CSS_UNKNOWN;
632         }
633         ASSERT_NOT_REACHED();
634         return CSSPrimitiveValue::CSS_UNKNOWN;
635     }
636
637     CSSCalcOperation(CalculationCategory category, CalcOperator op, Ref<CSSCalcExpressionNode>&& leftSide, Ref<CSSCalcExpressionNode>&& rightSide)
638         : CSSCalcExpressionNode(category, isIntegerResult(op, leftSide.get(), rightSide.get()))
639         , m_operator(op)
640     {
641         m_children.append(WTFMove(leftSide));
642         m_children.append(WTFMove(rightSide));
643     }
644
645     CSSCalcOperation(CalculationCategory category, CalcOperator op, Vector<Ref<CSSCalcExpressionNode>>&& children)
646         : CSSCalcExpressionNode(category, isIntegerResult(op, children))
647         , m_children(WTFMove(children))
648         , m_operator(op)
649     {
650     }
651
652     static CSSCalcExpressionNode* getNumberSide(CSSCalcExpressionNode& leftSide, CSSCalcExpressionNode& rightSide)
653     {
654         if (leftSide.category() == CalcNumber)
655             return &leftSide;
656         if (rightSide.category() == CalcNumber)
657             return &rightSide;
658         return nullptr;
659     }
660
661     double evaluate(const Vector<double>& children) const
662     {
663         return evaluateOperator(m_operator, children);
664     }
665
666     static double evaluateOperator(CalcOperator op, const Vector<double>& children)
667     {
668         switch (op) {
669         case CalcAdd:
670             ASSERT(children.size() == 2);
671             return children[0] + children[1];
672         case CalcSubtract:
673             ASSERT(children.size() == 2);
674             return children[0] - children[1];
675         case CalcMultiply:
676             ASSERT(children.size() == 2);
677             return children[0] * children[1];
678         case CalcDivide:
679             ASSERT(children.size() == 1 || children.size() == 2);
680             if (children.size() == 1)
681                 return std::numeric_limits<double>::quiet_NaN();
682             return children[0] / children[1];
683         case CalcMin: {
684             if (children.isEmpty())
685                 return std::numeric_limits<double>::quiet_NaN();
686             double minimum = children[0];
687             for (auto child : children)
688                 minimum = std::min(minimum, child);
689             return minimum;
690         }
691         case CalcMax: {
692             if (children.isEmpty())
693                 return std::numeric_limits<double>::quiet_NaN();
694             double maximum = children[0];
695             for (auto child : children)
696                 maximum = std::max(maximum, child);
697             return maximum;
698         }
699         }
700         ASSERT_NOT_REACHED();
701         return 0;
702     }
703
704     Vector<Ref<CSSCalcExpressionNode>> m_children;
705     const CalcOperator m_operator;
706 };
707
708 static ParseState checkDepthAndIndex(int* depth, CSSParserTokenRange tokens)
709 {
710     (*depth)++;
711     if (tokens.atEnd())
712         return NoMoreTokens;
713     if (*depth > maxExpressionDepth)
714         return TooDeep;
715     return OK;
716 }
717
718 class CSSCalcExpressionNodeParser {
719 public:
720     explicit CSSCalcExpressionNodeParser(CalculationCategory destinationCategory)
721         : m_destinationCategory(destinationCategory)
722     { }
723
724     RefPtr<CSSCalcExpressionNode> parseCalc(CSSParserTokenRange tokens, CSSValueID function)
725     {
726         Value result;
727         tokens.consumeWhitespace();
728         bool ok = false;
729         if (function == CSSValueCalc || function == CSSValueWebkitCalc)
730             ok = parseValueExpression(tokens, 0, &result);
731         else if (function == CSSValueMin || function == CSSValueMax)
732             ok = parseMinMaxExpression(tokens, function, 0, &result);
733         if (!ok || !tokens.atEnd())
734             return nullptr;
735         return result.value;
736     }
737     
738 private:
739     struct Value {
740         RefPtr<CSSCalcExpressionNode> value;
741     };
742     
743     char operatorValue(const CSSParserToken& token)
744     {
745         if (token.type() == DelimiterToken)
746             return token.delimiter();
747         return 0;
748     }
749     
750     bool parseValue(CSSParserTokenRange& tokens, Value* result)
751     {
752         CSSParserToken token = tokens.consumeIncludingWhitespace();
753         if (!(token.type() == NumberToken || token.type() == PercentageToken || token.type() == DimensionToken))
754             return false;
755         
756         CSSPrimitiveValue::UnitType type = token.unitType();
757         if (unitCategory(type) == CalcOther)
758             return false;
759         
760         bool isInteger = token.numericValueType() == IntegerValueType || (token.numericValueType() == NumberValueType && token.numericValue() == trunc(token.numericValue()));
761         result->value = CSSCalcPrimitiveValue::create(CSSPrimitiveValue::create(token.numericValue(), type), isInteger);
762         
763         return true;
764     }
765     
766     bool parseValueTerm(CSSParserTokenRange& tokens, int depth, Value* result)
767     {
768         if (checkDepthAndIndex(&depth, tokens) != OK)
769             return false;
770
771         auto functionId = tokens.peek().functionId();
772         
773         if (tokens.peek().type() == LeftParenthesisToken || functionId == CSSValueCalc) {
774             CSSParserTokenRange innerRange = tokens.consumeBlock();
775             tokens.consumeWhitespace();
776             innerRange.consumeWhitespace();
777             return parseValueExpression(innerRange, depth, result);
778         }
779
780         if (functionId == CSSValueMax || functionId == CSSValueMin) {
781             CSSParserTokenRange innerRange = tokens.consumeBlock();
782             tokens.consumeWhitespace();
783             innerRange.consumeWhitespace();
784             return parseMinMaxExpression(innerRange, functionId, depth, result);
785         }
786         
787         return parseValue(tokens, result);
788     }
789     
790     bool parseValueMultiplicativeExpression(CSSParserTokenRange& tokens, int depth, Value* result)
791     {
792         if (checkDepthAndIndex(&depth, tokens) != OK)
793             return false;
794         
795         if (!parseValueTerm(tokens, depth, result))
796             return false;
797         
798         while (!tokens.atEnd()) {
799             char operatorCharacter = operatorValue(tokens.peek());
800             if (operatorCharacter != CalcMultiply && operatorCharacter != CalcDivide)
801                 break;
802             tokens.consumeIncludingWhitespace();
803             
804             Value rhs;
805             if (!parseValueTerm(tokens, depth, &rhs))
806                 return false;
807             
808             result->value = CSSCalcOperation::createSimplified(static_cast<CalcOperator>(operatorCharacter), WTFMove(result->value), WTFMove(rhs.value));
809
810             if (!result->value)
811                 return false;
812         }
813         
814         return true;
815     }
816     
817     bool parseAdditiveValueExpression(CSSParserTokenRange& tokens, int depth, Value* result)
818     {
819         if (checkDepthAndIndex(&depth, tokens) != OK)
820             return false;
821         
822         if (!parseValueMultiplicativeExpression(tokens, depth, result))
823             return false;
824         
825         while (!tokens.atEnd()) {
826             char operatorCharacter = operatorValue(tokens.peek());
827             if (operatorCharacter != CalcAdd && operatorCharacter != CalcSubtract)
828                 break;
829             if ((&tokens.peek() - 1)->type() != WhitespaceToken)
830                 return false; // calc(1px+ 2px) is invalid
831             tokens.consume();
832             if (tokens.peek().type() != WhitespaceToken)
833                 return false; // calc(1px +2px) is invalid
834             tokens.consumeIncludingWhitespace();
835             
836             Value rhs;
837             if (!parseValueMultiplicativeExpression(tokens, depth, &rhs))
838                 return false;
839             
840             result->value = CSSCalcOperation::createSimplified(static_cast<CalcOperator>(operatorCharacter), WTFMove(result->value), WTFMove(rhs.value));
841             if (!result->value)
842                 return false;
843         }
844         
845         return true;
846     }
847
848     bool parseMinMaxExpression(CSSParserTokenRange& tokens, CSSValueID minMaxFunction, int depth, Value* result)
849     {
850         if (checkDepthAndIndex(&depth, tokens) != OK)
851             return false;
852
853         CalcOperator op = (minMaxFunction == CSSValueMin) ? CalcMin : CalcMax;
854
855         Value value;
856         if (!parseValueExpression(tokens, depth, &value))
857             return false;
858
859         Vector<Ref<CSSCalcExpressionNode>> nodes;
860         nodes.append(value.value.releaseNonNull());
861
862         while (!tokens.atEnd()) {
863             tokens.consumeWhitespace();
864             if (tokens.consume().type() != CommaToken)
865                 return false;
866             tokens.consumeWhitespace();
867
868             if (!parseValueExpression(tokens, depth, &value))
869                 return false;
870
871             nodes.append(value.value.releaseNonNull());
872         }
873
874         result->value = CSSCalcOperation::createMinOrMax(op, WTFMove(nodes), m_destinationCategory);
875         return result->value;
876     }
877
878     bool parseValueExpression(CSSParserTokenRange& tokens, int depth, Value* result)
879     {
880         return parseAdditiveValueExpression(tokens, depth, result);
881     }
882
883     CalculationCategory m_destinationCategory;
884 };
885
886 static inline RefPtr<CSSCalcOperation> createBlendHalf(const Length& length, const RenderStyle& style, float progress)
887 {
888     return CSSCalcOperation::create(CalcMultiply, createCSS(length, style),
889         CSSCalcPrimitiveValue::create(CSSPrimitiveValue::create(progress, CSSPrimitiveValue::CSS_NUMBER), !progress || progress == 1));
890 }
891
892 static RefPtr<CSSCalcExpressionNode> createCSS(const CalcExpressionNode& node, const RenderStyle& style)
893 {
894     switch (node.type()) {
895     case CalcExpressionNodeNumber: {
896         float value = toCalcExpressionNumber(node).value();
897         return CSSCalcPrimitiveValue::create(CSSPrimitiveValue::create(value, CSSPrimitiveValue::CSS_NUMBER), value == std::trunc(value));
898     }
899     case CalcExpressionNodeLength:
900         return createCSS(toCalcExpressionLength(node).length(), style);
901     case CalcExpressionNodeOperation: {
902         auto& operationNode = toCalcExpressionOperation(node);
903         auto& operationChildren = operationNode.children();
904         CalcOperator op = operationNode.getOperator();
905         if (op == CalcMin || op == CalcMax) {
906             Vector<Ref<CSSCalcExpressionNode>> values;
907             values.reserveInitialCapacity(operationChildren.size());
908             for (auto& child : operationChildren) {
909                 auto cssNode = createCSS(*child, style);
910                 if (!cssNode)
911                     return nullptr;
912                 values.uncheckedAppend(*cssNode);
913             }
914             return CSSCalcOperation::createMinOrMax(operationNode.getOperator(), WTFMove(values), CalcOther);
915         }
916
917         if (operationChildren.size() == 2)
918             return CSSCalcOperation::create(operationNode.getOperator(), createCSS(*operationChildren[0], style), createCSS(*operationChildren[1], style));
919
920         return nullptr;
921     }
922     case CalcExpressionNodeBlendLength: {
923         // FIXME: (http://webkit.org/b/122036) Create a CSSCalcExpressionNode equivalent of CalcExpressionBlendLength.
924         auto& blend = toCalcExpressionBlendLength(node);
925         float progress = blend.progress();
926         return CSSCalcOperation::create(CalcAdd, createBlendHalf(blend.from(), style, 1 - progress), createBlendHalf(blend.to(), style, progress));
927     }
928     case CalcExpressionNodeUndefined:
929         ASSERT_NOT_REACHED();
930     }
931     return nullptr;
932 }
933
934 static RefPtr<CSSCalcExpressionNode> createCSS(const Length& length, const RenderStyle& style)
935 {
936     switch (length.type()) {
937     case Percent:
938     case Fixed:
939         return CSSCalcPrimitiveValue::create(CSSPrimitiveValue::create(length, style), length.value() == trunc(length.value()));
940     case Calculated:
941         return createCSS(length.calculationValue().expression(), style);
942     case Auto:
943     case Intrinsic:
944     case MinIntrinsic:
945     case MinContent:
946     case MaxContent:
947     case FillAvailable:
948     case FitContent:
949     case Relative:
950     case Undefined:
951         ASSERT_NOT_REACHED();
952     }
953     return nullptr;
954 }
955
956 RefPtr<CSSCalcValue> CSSCalcValue::create(CSSValueID function, const CSSParserTokenRange& tokens, CalculationCategory destinationCategory, ValueRange range)
957 {
958     CSSCalcExpressionNodeParser parser(destinationCategory);
959     auto expression = parser.parseCalc(tokens, function);
960     if (!expression)
961         return nullptr;
962     return adoptRef(new CSSCalcValue(expression.releaseNonNull(), range != ValueRangeAll));
963 }
964     
965 RefPtr<CSSCalcValue> CSSCalcValue::create(const CalculationValue& value, const RenderStyle& style)
966 {
967     auto expression = createCSS(value.expression(), style);
968     if (!expression)
969         return nullptr;
970     return adoptRef(new CSSCalcValue(expression.releaseNonNull(), value.shouldClampToNonNegative()));
971 }
972
973 } // namespace WebCore