1/*
2 * Copyright (C) 2011, 2012 Google Inc. All rights reserved.
3 *
4 * Redistribution and use in source and binary forms, with or without
5 * modification, are permitted provided that the following conditions are
6 * met:
7 *
8 *     * Redistributions of source code must retain the above copyright
9 * notice, this list of conditions and the following disclaimer.
10 *     * Redistributions in binary form must reproduce the above
11 * copyright notice, this list of conditions and the following disclaimer
12 * in the documentation and/or other materials provided with the
13 * distribution.
14 *     * Neither the name of Google Inc. nor the names of its
15 * contributors may be used to endorse or promote products derived from
16 * this software without specific prior written permission.
17 *
18 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
19 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
20 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
21 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
22 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
23 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
24 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
25 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
26 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
27 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
28 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
29 */
30
31#include "config.h"
32#include "CSSCalculationValue.h"
33
34#include "CSSValueList.h"
35#include "Length.h"
36#include "StyleResolver.h"
37
38#include <wtf/OwnPtr.h>
39#include <wtf/PassOwnPtr.h>
40#include <wtf/text/StringBuilder.h>
41
42static const int maxExpressionDepth = 100;
43
44enum ParseState {
45    OK,
46    TooDeep,
47    NoMoreTokens
48};
49
50namespace WebCore {
51
52static CalculationCategory unitCategory(CSSPrimitiveValue::UnitTypes type)
53{
54    switch (type) {
55    case CSSPrimitiveValue::CSS_NUMBER:
56    case CSSPrimitiveValue::CSS_PARSER_INTEGER:
57        return CalcNumber;
58    case CSSPrimitiveValue::CSS_PERCENTAGE:
59        return CalcPercent;
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        return CalcLength;
71#if ENABLE(CSS_VARIABLES)
72    case CSSPrimitiveValue::CSS_VARIABLE_NAME:
73        return CalcVariable;
74#endif
75    default:
76        return CalcOther;
77    }
78}
79
80static String buildCssText(const String& expression)
81{
82    StringBuilder result;
83    result.append("calc");
84    bool expressionHasSingleTerm = expression[0] != '(';
85    if (expressionHasSingleTerm)
86        result.append('(');
87    result.append(expression);
88    if (expressionHasSingleTerm)
89        result.append(')');
90    return result.toString();
91}
92
93String CSSCalcValue::customCssText() const
94{
95    return buildCssText(m_expression->customCssText());
96}
97
98bool CSSCalcValue::equals(const CSSCalcValue& other) const
99{
100    return compareCSSValuePtr(m_expression, other.m_expression);
101}
102
103#if ENABLE(CSS_VARIABLES)
104String CSSCalcValue::customSerializeResolvingVariables(const HashMap<AtomicString, String>& variables) const
105{
106    return buildCssText(m_expression->serializeResolvingVariables(variables));
107}
108
109bool CSSCalcValue::hasVariableReference() const
110{
111    return m_expression->hasVariableReference();
112}
113#endif
114
115double CSSCalcValue::clampToPermittedRange(double value) const
116{
117    return m_nonNegative && value < 0 ? 0 : value;
118}
119
120double CSSCalcValue::doubleValue() const
121{
122    return clampToPermittedRange(m_expression->doubleValue());
123}
124
125double CSSCalcValue::computeLengthPx(const RenderStyle* currentStyle, const RenderStyle* rootStyle, double multiplier, bool computingFontSize) const
126{
127    return clampToPermittedRange(m_expression->computeLengthPx(currentStyle, rootStyle, multiplier, computingFontSize));
128}
129
130CSSCalcExpressionNode::~CSSCalcExpressionNode()
131{
132}
133
134class CSSCalcPrimitiveValue : public CSSCalcExpressionNode {
135    WTF_MAKE_FAST_ALLOCATED;
136public:
137
138    static PassRefPtr<CSSCalcPrimitiveValue> create(CSSPrimitiveValue* value, bool isInteger)
139    {
140        return adoptRef(new CSSCalcPrimitiveValue(value, isInteger));
141    }
142
143    virtual bool isZero() const
144    {
145        return !m_value->getDoubleValue();
146    }
147
148    virtual String customCssText() const
149    {
150        return m_value->cssText();
151    }
152
153#if ENABLE(CSS_VARIABLES)
154    virtual String serializeResolvingVariables(const HashMap<AtomicString, String>& variables) const
155    {
156        return m_value->customSerializeResolvingVariables(variables);
157    }
158
159    virtual bool hasVariableReference() const
160    {
161        return m_value->isVariableName();
162    }
163#endif
164
165    virtual PassOwnPtr<CalcExpressionNode> toCalcValue(const RenderStyle* style, const RenderStyle* rootStyle, double zoom) const
166    {
167        switch (m_category) {
168        case CalcNumber:
169            return adoptPtr(new CalcExpressionNumber(m_value->getFloatValue()));
170        case CalcLength:
171            return adoptPtr(new CalcExpressionNumber(m_value->computeLength<float>(style, rootStyle, zoom)));
172        case CalcPercent:
173        case CalcPercentLength:
174            return adoptPtr(new CalcExpressionLength(StyleResolver::convertToFloatLength(m_value.get(), style, rootStyle, zoom)));
175        // Only types that could be part of a Length expression can be converted
176        // to a CalcExpressionNode. CalcPercentNumber makes no sense as a Length.
177        case CalcPercentNumber:
178#if ENABLE(CSS_VARIABLES)
179        case CalcVariable:
180#endif
181        case CalcOther:
182            ASSERT_NOT_REACHED();
183        }
184        return nullptr;
185    }
186
187    virtual double doubleValue() const
188    {
189        switch (m_category) {
190        case CalcNumber:
191        case CalcPercent:
192            return m_value->getDoubleValue();
193        case CalcLength:
194        case CalcPercentLength:
195        case CalcPercentNumber:
196#if ENABLE(CSS_VARIABLES)
197        case CalcVariable:
198#endif
199        case CalcOther:
200            ASSERT_NOT_REACHED();
201            break;
202        }
203        return 0;
204    }
205
206    virtual double computeLengthPx(const RenderStyle* currentStyle, const RenderStyle* rootStyle, double multiplier, bool computingFontSize) const
207    {
208        switch (m_category) {
209        case CalcLength:
210            return m_value->computeLength<double>(currentStyle, rootStyle, multiplier, computingFontSize);
211        case CalcPercent:
212        case CalcNumber:
213            return m_value->getDoubleValue();
214        case CalcPercentLength:
215        case CalcPercentNumber:
216#if ENABLE(CSS_VARIABLES)
217        case CalcVariable:
218#endif
219        case CalcOther:
220            ASSERT_NOT_REACHED();
221            break;
222        }
223        return 0;
224    }
225
226    virtual bool equals(const CSSCalcExpressionNode& other) const
227    {
228        if (type() != other.type())
229            return false;
230
231        return compareCSSValuePtr(m_value, static_cast<const CSSCalcPrimitiveValue&>(other).m_value);
232    }
233
234    virtual Type type() const { return CssCalcPrimitiveValue; }
235
236private:
237    explicit CSSCalcPrimitiveValue(CSSPrimitiveValue* value, bool isInteger)
238        : CSSCalcExpressionNode(unitCategory((CSSPrimitiveValue::UnitTypes)value->primitiveType()), isInteger)
239        , m_value(value)
240    {
241    }
242
243    RefPtr<CSSPrimitiveValue> m_value;
244};
245
246static const CalculationCategory addSubtractResult[CalcOther][CalcOther] = {
247    { CalcNumber,        CalcOther,         CalcPercentNumber, CalcPercentNumber, CalcOther },
248    { CalcOther,         CalcLength,        CalcPercentLength, CalcOther,         CalcPercentLength },
249    { CalcPercentNumber, CalcPercentLength, CalcPercent,       CalcPercentNumber, CalcPercentLength },
250    { CalcPercentNumber, CalcOther,         CalcPercentNumber, CalcPercentNumber, CalcOther },
251    { CalcOther,         CalcPercentLength, CalcPercentLength, CalcOther,         CalcPercentLength },
252};
253
254static CalculationCategory determineCategory(const CSSCalcExpressionNode& leftSide, const CSSCalcExpressionNode& rightSide, CalcOperator op)
255{
256    CalculationCategory leftCategory = leftSide.category();
257    CalculationCategory rightCategory = rightSide.category();
258
259    if (leftCategory == CalcOther || rightCategory == CalcOther)
260        return CalcOther;
261
262#if ENABLE(CSS_VARIABLES)
263    if (leftCategory == CalcVariable || rightCategory == CalcVariable)
264        return CalcVariable;
265#endif
266
267    switch (op) {
268    case CalcAdd:
269    case CalcSubtract:
270        return addSubtractResult[leftCategory][rightCategory];
271    case CalcMultiply:
272        if (leftCategory != CalcNumber && rightCategory != CalcNumber)
273            return CalcOther;
274        return leftCategory == CalcNumber ? rightCategory : leftCategory;
275    case CalcDivide:
276        if (rightCategory != CalcNumber || rightSide.isZero())
277            return CalcOther;
278        return leftCategory;
279    }
280
281    ASSERT_NOT_REACHED();
282    return CalcOther;
283}
284
285class CSSCalcBinaryOperation : public CSSCalcExpressionNode {
286
287public:
288    static PassRefPtr<CSSCalcBinaryOperation> create(PassRefPtr<CSSCalcExpressionNode> leftSide, PassRefPtr<CSSCalcExpressionNode> rightSide, CalcOperator op)
289    {
290        ASSERT(leftSide->category() != CalcOther && rightSide->category() != CalcOther);
291
292        CalculationCategory newCategory = determineCategory(*leftSide, *rightSide, op);
293
294        if (newCategory == CalcOther)
295            return 0;
296
297        return adoptRef(new CSSCalcBinaryOperation(leftSide, rightSide, op, newCategory));
298    }
299
300    virtual bool isZero() const
301    {
302        return !doubleValue();
303    }
304
305    virtual PassOwnPtr<CalcExpressionNode> toCalcValue(const RenderStyle* style, const RenderStyle* rootStyle, double zoom) const
306    {
307        OwnPtr<CalcExpressionNode> left(m_leftSide->toCalcValue(style, rootStyle, zoom));
308        if (!left)
309            return nullptr;
310        OwnPtr<CalcExpressionNode> right(m_rightSide->toCalcValue(style, rootStyle, zoom));
311        if (!right)
312            return nullptr;
313        return adoptPtr(new CalcExpressionBinaryOperation(left.release(), right.release(), m_operator));
314    }
315
316    virtual double doubleValue() const
317    {
318        return evaluate(m_leftSide->doubleValue(), m_rightSide->doubleValue());
319    }
320
321    virtual double computeLengthPx(const RenderStyle* currentStyle, const RenderStyle* rootStyle, double multiplier, bool computingFontSize) const
322    {
323        const double leftValue = m_leftSide->computeLengthPx(currentStyle, rootStyle, multiplier, computingFontSize);
324        const double rightValue = m_rightSide->computeLengthPx(currentStyle, rootStyle, multiplier, computingFontSize);
325        return evaluate(leftValue, rightValue);
326    }
327
328    static String buildCssText(const String& leftExpression, const String& rightExpression, CalcOperator op)
329    {
330        StringBuilder result;
331        result.append('(');
332        result.append(leftExpression);
333        result.append(' ');
334        result.append(static_cast<char>(op));
335        result.append(' ');
336        result.append(rightExpression);
337        result.append(')');
338
339        return result.toString();
340    }
341
342    virtual String customCssText() const
343    {
344        return buildCssText(m_leftSide->customCssText(), m_rightSide->customCssText(), m_operator);
345    }
346
347#if ENABLE(CSS_VARIABLES)
348    virtual String serializeResolvingVariables(const HashMap<AtomicString, String>& variables) const
349    {
350        return buildCssText(m_leftSide->serializeResolvingVariables(variables), m_rightSide->serializeResolvingVariables(variables), m_operator);
351    }
352
353    virtual bool hasVariableReference() const
354    {
355        return m_leftSide->hasVariableReference() || m_rightSide->hasVariableReference();
356    }
357#endif
358
359    virtual bool equals(const CSSCalcExpressionNode& exp) const
360    {
361        if (type() != exp.type())
362            return false;
363
364        const CSSCalcBinaryOperation& other = static_cast<const CSSCalcBinaryOperation&>(exp);
365        return compareCSSValuePtr(m_leftSide, other.m_leftSide)
366            && compareCSSValuePtr(m_rightSide, other.m_rightSide)
367            && m_operator == other.m_operator;
368    }
369
370    virtual Type type() const { return CssCalcBinaryOperation; }
371
372private:
373    CSSCalcBinaryOperation(PassRefPtr<CSSCalcExpressionNode> leftSide, PassRefPtr<CSSCalcExpressionNode> rightSide, CalcOperator op, CalculationCategory category)
374        : CSSCalcExpressionNode(category, leftSide->isInteger() && rightSide->isInteger())
375        , m_leftSide(leftSide)
376        , m_rightSide(rightSide)
377        , m_operator(op)
378    {
379    }
380
381    double evaluate(double leftValue, double rightValue) const
382    {
383        switch (m_operator) {
384        case CalcAdd:
385            return leftValue + rightValue;
386        case CalcSubtract:
387            return leftValue - rightValue;
388        case CalcMultiply:
389            return leftValue * rightValue;
390        case CalcDivide:
391            if (rightValue)
392                return leftValue / rightValue;
393            return std::numeric_limits<double>::quiet_NaN();
394        }
395        return 0;
396    }
397
398    const RefPtr<CSSCalcExpressionNode> m_leftSide;
399    const RefPtr<CSSCalcExpressionNode> m_rightSide;
400    const CalcOperator m_operator;
401};
402
403static ParseState checkDepthAndIndex(int* depth, unsigned index, CSSParserValueList* tokens)
404{
405    (*depth)++;
406    if (*depth > maxExpressionDepth)
407        return TooDeep;
408    if (index >= tokens->size())
409        return NoMoreTokens;
410    return OK;
411}
412
413class CSSCalcExpressionNodeParser {
414public:
415    PassRefPtr<CSSCalcExpressionNode> parseCalc(CSSParserValueList* tokens)
416    {
417        unsigned index = 0;
418        Value result;
419        bool ok = parseValueExpression(tokens, 0, &index, &result);
420        ASSERT_WITH_SECURITY_IMPLICATION(index <= tokens->size());
421        if (!ok || index != tokens->size())
422            return 0;
423        return result.value;
424    }
425
426private:
427    struct Value {
428        RefPtr<CSSCalcExpressionNode> value;
429    };
430
431    char operatorValue(CSSParserValueList* tokens, unsigned index)
432    {
433        if (index >= tokens->size())
434            return 0;
435        CSSParserValue* value = tokens->valueAt(index);
436        if (value->unit != CSSParserValue::Operator)
437            return 0;
438
439        return value->iValue;
440    }
441
442    bool parseValue(CSSParserValueList* tokens, unsigned* index, Value* result)
443    {
444        CSSParserValue* parserValue = tokens->valueAt(*index);
445        if (parserValue->unit == CSSParserValue::Operator || parserValue->unit == CSSParserValue::Function)
446            return false;
447
448        RefPtr<CSSValue> value = parserValue->createCSSValue();
449        if (!value || !value->isPrimitiveValue())
450            return false;
451
452        CSSPrimitiveValue* primitiveValue = static_cast<CSSPrimitiveValue*>(value.get());
453        result->value = CSSCalcPrimitiveValue::create(primitiveValue, parserValue->isInt);
454
455        ++*index;
456        return true;
457    }
458
459    bool parseValueTerm(CSSParserValueList* tokens, int depth, unsigned* index, Value* result)
460    {
461        if (checkDepthAndIndex(&depth, *index, tokens) != OK)
462            return false;
463
464        if (operatorValue(tokens, *index) == '(') {
465            unsigned currentIndex = *index + 1;
466            if (!parseValueExpression(tokens, depth, &currentIndex, result))
467                return false;
468
469            if (operatorValue(tokens, currentIndex) != ')')
470                return false;
471            *index = currentIndex + 1;
472            return true;
473        }
474
475        return parseValue(tokens, index, result);
476    }
477
478    bool parseValueMultiplicativeExpression(CSSParserValueList* tokens, int depth, unsigned* index, Value* result)
479    {
480        if (checkDepthAndIndex(&depth, *index, tokens) != OK)
481            return false;
482
483        if (!parseValueTerm(tokens, depth, index, result))
484            return false;
485
486        while (*index < tokens->size() - 1) {
487            char operatorCharacter = operatorValue(tokens, *index);
488            if (operatorCharacter != CalcMultiply && operatorCharacter != CalcDivide)
489                break;
490            ++*index;
491
492            Value rhs;
493            if (!parseValueTerm(tokens, depth, index, &rhs))
494                return false;
495
496            result->value = CSSCalcBinaryOperation::create(result->value, rhs.value, static_cast<CalcOperator>(operatorCharacter));
497            if (!result->value)
498                return false;
499        }
500
501        ASSERT_WITH_SECURITY_IMPLICATION(*index <= tokens->size());
502        return true;
503    }
504
505    bool parseAdditiveValueExpression(CSSParserValueList* tokens, int depth, unsigned* index, Value* result)
506    {
507        if (checkDepthAndIndex(&depth, *index, tokens) != OK)
508            return false;
509
510        if (!parseValueMultiplicativeExpression(tokens, depth, index, result))
511            return false;
512
513        while (*index < tokens->size() - 1) {
514            char operatorCharacter = operatorValue(tokens, *index);
515            if (operatorCharacter != CalcAdd && operatorCharacter != CalcSubtract)
516                break;
517            ++*index;
518
519            Value rhs;
520            if (!parseValueMultiplicativeExpression(tokens, depth, index, &rhs))
521                return false;
522
523            result->value = CSSCalcBinaryOperation::create(result->value, rhs.value, static_cast<CalcOperator>(operatorCharacter));
524            if (!result->value)
525                return false;
526        }
527
528        ASSERT_WITH_SECURITY_IMPLICATION(*index <= tokens->size());
529        return true;
530    }
531
532    bool parseValueExpression(CSSParserValueList* tokens, int depth, unsigned* index, Value* result)
533    {
534        return parseAdditiveValueExpression(tokens, depth, index, result);
535    }
536};
537
538PassRefPtr<CSSCalcValue> CSSCalcValue::create(CSSParserString name, CSSParserValueList* parserValueList, CalculationPermittedValueRange range)
539{
540    CSSCalcExpressionNodeParser parser;
541    RefPtr<CSSCalcExpressionNode> expression;
542
543    if (equalIgnoringCase(name, "calc(") || equalIgnoringCase(name, "-webkit-calc("))
544        expression = parser.parseCalc(parserValueList);
545    // FIXME calc (http://webkit.org/b/16662) Add parsing for min and max here
546
547    return expression ? adoptRef(new CSSCalcValue(expression, range)) : 0;
548}
549
550} // namespace WebCore
551