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