/*
 * Copyright (C) 2011, 2012 Google Inc. All rights reserved.
 * Copyright (C) 2014 Apple Inc. All rights reserved.
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions are
 * met:
 *
 *     * Redistributions of source code must retain the above copyright
 * notice, this list of conditions and the following disclaimer.
 *     * Redistributions in binary form must reproduce the above
 * copyright notice, this list of conditions and the following disclaimer
 * in the documentation and/or other materials provided with the
 * distribution.
 *     * Neither the name of Google Inc. nor the names of its
 * contributors may be used to endorse or promote products derived from
 * this software without specific prior written permission.
 *
 * THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
 * "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
 * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
 * A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
 * OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
 * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
 * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
 * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
 * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
 * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
 * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
 */

#include "config.h"
#include "CSSCalculationValue.h"

#include "CSSParser.h"
#include "CSSParserTokenRange.h"
#include "CSSPrimitiveValueMappings.h"
#include "Logging.h"
#include "StyleResolver.h"
#include <wtf/MathExtras.h>
#include <wtf/text/StringBuilder.h>
#include <wtf/text/TextStream.h>

static const int maxExpressionDepth = 100;

namespace WebCore {
class CSSCalcPrimitiveValueNode;
class CSSCalcOperationNode;
}

SPECIALIZE_TYPE_TRAITS_CSSCALCEXPRESSION_NODE(CSSCalcPrimitiveValueNode, type() == WebCore::CSSCalcExpressionNode::Type::CssCalcPrimitiveValue)
SPECIALIZE_TYPE_TRAITS_CSSCALCEXPRESSION_NODE(CSSCalcOperationNode, type() == WebCore::CSSCalcExpressionNode::Type::CssCalcOperation)

namespace WebCore {

static RefPtr<CSSCalcExpressionNode> createCSS(const CalcExpressionNode&, const RenderStyle&);
static RefPtr<CSSCalcExpressionNode> createCSS(const Length&, const RenderStyle&);

static TextStream& operator<<(TextStream& ts, const CSSCalcExpressionNode& node)
{
    node.dump(ts);
    return ts;
}

static CalculationCategory calcUnitCategory(CSSUnitType type)
{
    switch (type) {
    case CSSUnitType::CSS_NUMBER:
        return CalculationCategory::Number;
    case CSSUnitType::CSS_EMS:
    case CSSUnitType::CSS_EXS:
    case CSSUnitType::CSS_PX:
    case CSSUnitType::CSS_CM:
    case CSSUnitType::CSS_MM:
    case CSSUnitType::CSS_IN:
    case CSSUnitType::CSS_PT:
    case CSSUnitType::CSS_PC:
    case CSSUnitType::CSS_Q:
    case CSSUnitType::CSS_REMS:
    case CSSUnitType::CSS_CHS:
    case CSSUnitType::CSS_VW:
    case CSSUnitType::CSS_VH:
    case CSSUnitType::CSS_VMIN:
    case CSSUnitType::CSS_VMAX:
        return CalculationCategory::Length;
    case CSSUnitType::CSS_PERCENTAGE:
        return CalculationCategory::Percent;
    case CSSUnitType::CSS_DEG:
    case CSSUnitType::CSS_RAD:
    case CSSUnitType::CSS_GRAD:
    case CSSUnitType::CSS_TURN:
        return CalculationCategory::Angle;
    case CSSUnitType::CSS_MS:
    case CSSUnitType::CSS_S:
        return CalculationCategory::Time;
    case CSSUnitType::CSS_HZ:
    case CSSUnitType::CSS_KHZ:
        return CalculationCategory::Frequency;
    default:
        return CalculationCategory::Other;
    }
}

static bool hasDoubleValue(CSSUnitType type)
{
    switch (type) {
    case CSSUnitType::CSS_NUMBER:
    case CSSUnitType::CSS_PERCENTAGE:
    case CSSUnitType::CSS_EMS:
    case CSSUnitType::CSS_EXS:
    case CSSUnitType::CSS_CHS:
    case CSSUnitType::CSS_REMS:
    case CSSUnitType::CSS_PX:
    case CSSUnitType::CSS_CM:
    case CSSUnitType::CSS_MM:
    case CSSUnitType::CSS_IN:
    case CSSUnitType::CSS_PT:
    case CSSUnitType::CSS_PC:
    case CSSUnitType::CSS_DEG:
    case CSSUnitType::CSS_RAD:
    case CSSUnitType::CSS_GRAD:
    case CSSUnitType::CSS_TURN:
    case CSSUnitType::CSS_MS:
    case CSSUnitType::CSS_S:
    case CSSUnitType::CSS_HZ:
    case CSSUnitType::CSS_KHZ:
    case CSSUnitType::CSS_DIMENSION:
    case CSSUnitType::CSS_VW:
    case CSSUnitType::CSS_VH:
    case CSSUnitType::CSS_VMIN:
    case CSSUnitType::CSS_VMAX:
    case CSSUnitType::CSS_DPPX:
    case CSSUnitType::CSS_DPI:
    case CSSUnitType::CSS_DPCM:
    case CSSUnitType::CSS_FR:
    case CSSUnitType::CSS_Q:
        return true;
    case CSSUnitType::CSS_UNKNOWN:
    case CSSUnitType::CSS_STRING:
    case CSSUnitType::CSS_FONT_FAMILY:
    case CSSUnitType::CSS_URI:
    case CSSUnitType::CSS_IDENT:
    case CSSUnitType::CSS_ATTR:
    case CSSUnitType::CSS_COUNTER:
    case CSSUnitType::CSS_RECT:
    case CSSUnitType::CSS_RGBCOLOR:
    case CSSUnitType::CSS_PAIR:
    case CSSUnitType::CSS_UNICODE_RANGE:
    case CSSUnitType::CSS_COUNTER_NAME:
    case CSSUnitType::CSS_SHAPE:
    case CSSUnitType::CSS_QUAD:
    case CSSUnitType::CSS_QUIRKY_EMS:
    case CSSUnitType::CSS_CALC:
    case CSSUnitType::CSS_CALC_PERCENTAGE_WITH_NUMBER:
    case CSSUnitType::CSS_CALC_PERCENTAGE_WITH_LENGTH:
    case CSSUnitType::CSS_PROPERTY_ID:
    case CSSUnitType::CSS_VALUE_ID:
        return false;
    };
    ASSERT_NOT_REACHED();
    return false;
}

#if !LOG_DISABLED
static String prettyPrintNode(const CSSCalcExpressionNode& node)
{
    TextStream multilineStream;
    multilineStream << node;
    return multilineStream.release();
}

static String prettyPrintNodes(const Vector<Ref<CSSCalcExpressionNode>>& nodes)
{
    TextStream multilineStream;
    multilineStream << nodes;
    return multilineStream.release();
}
#endif

class CSSCalcPrimitiveValueNode final : public CSSCalcExpressionNode {
    WTF_MAKE_FAST_ALLOCATED;
public:
    static Ref<CSSCalcPrimitiveValueNode> create(Ref<CSSPrimitiveValue>&& value)
    {
        return adoptRef(*new CSSCalcPrimitiveValueNode(WTFMove(value)));
    }

    static RefPtr<CSSCalcPrimitiveValueNode> create(double value, CSSUnitType type)
    {
        if (!std::isfinite(value))
            return nullptr;
        return adoptRef(new CSSCalcPrimitiveValueNode(CSSPrimitiveValue::create(value, type)));
    }

private:
    bool isZero() const final
    {
        return !m_value->doubleValue();
    }

    bool equals(const CSSCalcExpressionNode& other) const final;
    Type type() const final { return CssCalcPrimitiveValue; }

    CSSUnitType primitiveType() const final
    {
        return CSSUnitType(m_value->primitiveType());
    }

    std::unique_ptr<CalcExpressionNode> createCalcExpression(const CSSToLengthConversionData&) const final;
    double doubleValue() const final;

    double computeLengthPx(const CSSToLengthConversionData&) const final;
    void collectDirectComputationalDependencies(HashSet<CSSPropertyID>&) const final;
    void collectDirectRootComputationalDependencies(HashSet<CSSPropertyID>&) const final;

    String customCSSText() const final
    {
        return m_value->cssText();
    }

    void dump(TextStream&) const final;

private:
    explicit CSSCalcPrimitiveValueNode(Ref<CSSPrimitiveValue>&& value)
        : CSSCalcExpressionNode(calcUnitCategory(value->primitiveType()))
        , m_value(WTFMove(value))
    {
    }

    Ref<CSSPrimitiveValue> m_value;
};

std::unique_ptr<CalcExpressionNode> CSSCalcPrimitiveValueNode::createCalcExpression(const CSSToLengthConversionData& conversionData) const
{
    switch (category()) {
    case CalculationCategory::Number:
        return makeUnique<CalcExpressionNumber>(m_value->floatValue());
    case CalculationCategory::Length:
        return makeUnique<CalcExpressionLength>(Length(m_value->computeLength<float>(conversionData), WebCore::Fixed));
    case CalculationCategory::Percent:
    case CalculationCategory::PercentLength: {
        return makeUnique<CalcExpressionLength>(m_value->convertToLength<FixedFloatConversion | PercentConversion>(conversionData));
    }
    // Only types that could be part of a Length expression can be converted
    // to a CalcExpressionNode. CalculationCategory::PercentNumber makes no sense as a Length.
    case CalculationCategory::PercentNumber:
    case CalculationCategory::Angle:
    case CalculationCategory::Time:
    case CalculationCategory::Frequency:
    case CalculationCategory::Other:
        ASSERT_NOT_REACHED();
    }
    ASSERT_NOT_REACHED();
    return nullptr;
}

double CSSCalcPrimitiveValueNode::doubleValue() const
{
    if (hasDoubleValue(primitiveType()))
        return m_value->doubleValue();
    ASSERT_NOT_REACHED();
    return 0;
}

double CSSCalcPrimitiveValueNode::computeLengthPx(const CSSToLengthConversionData& conversionData) const
{
    switch (category()) {
    case CalculationCategory::Length:
        return m_value->computeLength<double>(conversionData);
    case CalculationCategory::Percent:
    case CalculationCategory::Number:
        return m_value->doubleValue();
    case CalculationCategory::PercentLength:
    case CalculationCategory::PercentNumber:
    case CalculationCategory::Angle:
    case CalculationCategory::Time:
    case CalculationCategory::Frequency:
    case CalculationCategory::Other:
        ASSERT_NOT_REACHED();
        break;
    }
    ASSERT_NOT_REACHED();
    return 0;
}

void CSSCalcPrimitiveValueNode::collectDirectComputationalDependencies(HashSet<CSSPropertyID>& values) const
{
    m_value->collectDirectComputationalDependencies(values);
}

void CSSCalcPrimitiveValueNode::collectDirectRootComputationalDependencies(HashSet<CSSPropertyID>& values) const
{
    m_value->collectDirectRootComputationalDependencies(values);
}

bool CSSCalcPrimitiveValueNode::equals(const CSSCalcExpressionNode& other) const
{
    if (type() != other.type())
        return false;

    return compareCSSValue(m_value, static_cast<const CSSCalcPrimitiveValueNode&>(other).m_value);
}

void CSSCalcPrimitiveValueNode::dump(TextStream& ts) const
{
    ts << "value " << m_value->customCSSText();
}


static const CalculationCategory addSubtractResult[static_cast<unsigned>(CalculationCategory::Angle)][static_cast<unsigned>(CalculationCategory::Angle)] = {
//    CalculationCategory::Number         CalculationCategory::Length         CalculationCategory::Percent        CalculationCategory::PercentNumber  CalculationCategory::PercentLength
    { CalculationCategory::Number,        CalculationCategory::Other,         CalculationCategory::PercentNumber, CalculationCategory::PercentNumber, CalculationCategory::Other }, //         CalculationCategory::Number
    { CalculationCategory::Other,         CalculationCategory::Length,        CalculationCategory::PercentLength, CalculationCategory::Other,         CalculationCategory::PercentLength }, // CalculationCategory::Length
    { CalculationCategory::PercentNumber, CalculationCategory::PercentLength, CalculationCategory::Percent,       CalculationCategory::PercentNumber, CalculationCategory::PercentLength }, // CalculationCategory::Percent
    { CalculationCategory::PercentNumber, CalculationCategory::Other,         CalculationCategory::PercentNumber, CalculationCategory::PercentNumber, CalculationCategory::Other }, //         CalculationCategory::PercentNumber
    { CalculationCategory::Other,         CalculationCategory::PercentLength, CalculationCategory::PercentLength, CalculationCategory::Other,         CalculationCategory::PercentLength }, // CalculationCategory::PercentLength
};

static CalculationCategory determineCategory(const CSSCalcExpressionNode& leftSide, const CSSCalcExpressionNode& rightSide, CalcOperator op)
{
    CalculationCategory leftCategory = leftSide.category();
    CalculationCategory rightCategory = rightSide.category();
    ASSERT(leftCategory < CalculationCategory::Other);
    ASSERT(rightCategory < CalculationCategory::Other);

    switch (op) {
    case CalcOperator::Add:
    case CalcOperator::Subtract:
        if (leftCategory < CalculationCategory::Angle && rightCategory < CalculationCategory::Angle)
            return addSubtractResult[static_cast<unsigned>(leftCategory)][static_cast<unsigned>(rightCategory)];
        if (leftCategory == rightCategory)
            return leftCategory;
        return CalculationCategory::Other;
    case CalcOperator::Multiply:
        if (leftCategory != CalculationCategory::Number && rightCategory != CalculationCategory::Number)
            return CalculationCategory::Other;
        return leftCategory == CalculationCategory::Number ? rightCategory : leftCategory;
    case CalcOperator::Divide:
        if (rightCategory != CalculationCategory::Number || rightSide.isZero())
            return CalculationCategory::Other;
        return leftCategory;
    case CalcOperator::Min:
    case CalcOperator::Max:
        ASSERT_NOT_REACHED();
        return CalculationCategory::Other;
    }

    ASSERT_NOT_REACHED();
    return CalculationCategory::Other;
}

static CalculationCategory resolvedTypeForMinOrMax(CalculationCategory category, CalculationCategory destinationCategory)
{
    switch (category) {
    case CalculationCategory::Number:
    case CalculationCategory::Length:
    case CalculationCategory::PercentNumber:
    case CalculationCategory::PercentLength:
    case CalculationCategory::Angle:
    case CalculationCategory::Time:
    case CalculationCategory::Frequency:
    case CalculationCategory::Other:
        return category;

    case CalculationCategory::Percent:
        if (destinationCategory == CalculationCategory::Length)
            return CalculationCategory::PercentLength;
        if (destinationCategory == CalculationCategory::Number)
            return CalculationCategory::PercentNumber;
        return category;
    }

    return CalculationCategory::Other;
}

static bool isSamePair(CalculationCategory a, CalculationCategory b, CalculationCategory x, CalculationCategory y)
{
    return (a == x && b == y) || (a == y && b == x);
}

class CSSCalcOperationNode final : public CSSCalcExpressionNode {
    WTF_MAKE_FAST_ALLOCATED;
public:
    static RefPtr<CSSCalcOperationNode> create(CalcOperator, RefPtr<CSSCalcExpressionNode>&& leftSide, RefPtr<CSSCalcExpressionNode>&& rightSide);
    static RefPtr<CSSCalcOperationNode> createMinOrMax(CalcOperator, Vector<Ref<CSSCalcExpressionNode>>&& values, CalculationCategory destinationCategory);
    static RefPtr<CSSCalcExpressionNode> createSimplified(CalcOperator, RefPtr<CSSCalcExpressionNode>&& leftSide, RefPtr<CSSCalcExpressionNode>&& rightSide);

private:
    CSSCalcOperationNode(CalculationCategory category, CalcOperator op, Ref<CSSCalcExpressionNode>&& leftSide, Ref<CSSCalcExpressionNode>&& rightSide)
        : CSSCalcExpressionNode(category)
        , m_operator(op)
    {
        m_children.reserveInitialCapacity(2);
        m_children.uncheckedAppend(WTFMove(leftSide));
        m_children.uncheckedAppend(WTFMove(rightSide));
    }

    CSSCalcOperationNode(CalculationCategory category, CalcOperator op, Vector<Ref<CSSCalcExpressionNode>>&& children)
        : CSSCalcExpressionNode(category)
        , m_operator(op)
        , m_children(WTFMove(children))
    {
    }

    Type type() const final { return CssCalcOperation; }

    bool isZero() const final
    {
        return !doubleValue();
    }

    bool equals(const CSSCalcExpressionNode&) const final;

    std::unique_ptr<CalcExpressionNode> createCalcExpression(const CSSToLengthConversionData&) const final;

    CSSUnitType primitiveType() const final;
    double doubleValue() const final;
    double computeLengthPx(const CSSToLengthConversionData&) const final;

    void collectDirectComputationalDependencies(HashSet<CSSPropertyID>&) const final;
    void collectDirectRootComputationalDependencies(HashSet<CSSPropertyID>&) const final;

    String customCSSText() const final;

    void dump(TextStream&) const final;

    static CSSCalcExpressionNode* getNumberSide(CSSCalcExpressionNode& leftSide, CSSCalcExpressionNode& rightSide)
    {
        if (leftSide.category() == CalculationCategory::Number)
            return &leftSide;
        if (rightSide.category() == CalculationCategory::Number)
            return &rightSide;
        return nullptr;
    }

    double evaluate(const Vector<double>& children) const
    {
        return evaluateOperator(m_operator, children);
    }

    static double evaluateOperator(CalcOperator, const Vector<double>&);
    static String buildCssText(Vector<String>, CalcOperator);

    const CalcOperator m_operator;
    Vector<Ref<CSSCalcExpressionNode>> m_children;
};

RefPtr<CSSCalcOperationNode> CSSCalcOperationNode::create(CalcOperator op, RefPtr<CSSCalcExpressionNode>&& leftSide, RefPtr<CSSCalcExpressionNode>&& rightSide)
{
    if (!leftSide || !rightSide)
        return nullptr;

    ASSERT(leftSide->category() < CalculationCategory::Other);
    ASSERT(rightSide->category() < CalculationCategory::Other);

    auto newCategory = determineCategory(*leftSide, *rightSide, op);
    if (newCategory == CalculationCategory::Other) {
        LOG_WITH_STREAM(Calc, stream << "Failed to create CSSCalcOperationNode " << op << " node because unable to determine category from " << prettyPrintNode(*leftSide) << " and " << *rightSide);
        return nullptr;
    }

    return adoptRef(new CSSCalcOperationNode(newCategory, op, leftSide.releaseNonNull(), rightSide.releaseNonNull()));
}

RefPtr<CSSCalcOperationNode> CSSCalcOperationNode::createMinOrMax(CalcOperator op, Vector<Ref<CSSCalcExpressionNode>>&& values, CalculationCategory destinationCategory)
{
    ASSERT(op == CalcOperator::Min || op == CalcOperator::Max);

    Optional<CalculationCategory> category = WTF::nullopt;
    for (auto& value : values) {
        auto valueCategory = resolvedTypeForMinOrMax(value->category(), destinationCategory);

        ASSERT(valueCategory < CalculationCategory::Other);
        if (!category) {
            if (valueCategory == CalculationCategory::Other) {
                LOG_WITH_STREAM(Calc, stream << "Failed to create CSSCalcOperationNode " << op << " node because unable to determine category from " << prettyPrintNodes(values));
                return nullptr;
            }
            category = valueCategory;
        }

        if (category != valueCategory) {
            if (isSamePair(category.value(), valueCategory, CalculationCategory::Length, CalculationCategory::PercentLength)) {
                category = CalculationCategory::PercentLength;
                continue;
            }
            if (isSamePair(category.value(), valueCategory, CalculationCategory::Number, CalculationCategory::PercentNumber)) {
                category = CalculationCategory::PercentNumber;
                continue;
            }
            return nullptr;
        }
    }

    return adoptRef(new CSSCalcOperationNode(category.value(), op, WTFMove(values)));
}

RefPtr<CSSCalcExpressionNode> CSSCalcOperationNode::createSimplified(CalcOperator op, RefPtr<CSSCalcExpressionNode>&& leftSide, RefPtr<CSSCalcExpressionNode>&& rightSide)
{
    if (!leftSide || !rightSide)
        return nullptr;

    auto leftCategory = leftSide->category();
    auto rightCategory = rightSide->category();
    ASSERT(leftCategory < CalculationCategory::Other);
    ASSERT(rightCategory < CalculationCategory::Other);

    // Simplify numbers.
    if (leftCategory == CalculationCategory::Number && rightCategory == CalculationCategory::Number) {
        CSSUnitType evaluationType = CSSUnitType::CSS_NUMBER;
        return CSSCalcPrimitiveValueNode::create(evaluateOperator(op, { leftSide->doubleValue(), rightSide->doubleValue() }), evaluationType);
    }

    // Simplify addition and subtraction between same types.
    if (op == CalcOperator::Add || op == CalcOperator::Subtract) {
        if (leftCategory == rightSide->category()) {
            CSSUnitType leftType = leftSide->primitiveType();
            if (hasDoubleValue(leftType)) {
                CSSUnitType rightType = rightSide->primitiveType();
                if (leftType == rightType)
                    return CSSCalcPrimitiveValueNode::create(evaluateOperator(op, { leftSide->doubleValue(), rightSide->doubleValue() }), leftType);
                CSSUnitCategory leftUnitCategory = unitCategory(leftType);
                if (leftUnitCategory != CSSUnitCategory::Other && leftUnitCategory == unitCategory(rightType)) {
                    CSSUnitType canonicalType = canonicalUnitTypeForCategory(leftUnitCategory);
                    if (canonicalType != CSSUnitType::CSS_UNKNOWN) {
                        double leftValue = leftSide->doubleValue() * CSSPrimitiveValue::conversionToCanonicalUnitsScaleFactor(leftType);
                        double rightValue = rightSide->doubleValue() * CSSPrimitiveValue::conversionToCanonicalUnitsScaleFactor(rightType);
                        return CSSCalcPrimitiveValueNode::create(evaluateOperator(op, { leftValue, rightValue }), canonicalType);
                    }
                }
            }
        }
    } else {
        // Simplify multiplying or dividing by a number for simplifiable types.
        ASSERT(op == CalcOperator::Multiply || op == CalcOperator::Divide);
        auto* numberSide = getNumberSide(*leftSide, *rightSide);
        if (!numberSide)
            return create(op, leftSide.releaseNonNull(), rightSide.releaseNonNull());
        if (numberSide == leftSide && op == CalcOperator::Divide)
            return nullptr;
        auto& otherSide = leftSide == numberSide ? *rightSide : *leftSide;

        double number = numberSide->doubleValue();
        if (!std::isfinite(number))
            return nullptr;
        if (op == CalcOperator::Divide && !number)
            return nullptr;

        auto otherType = otherSide.primitiveType();
        if (hasDoubleValue(otherType))
            return CSSCalcPrimitiveValueNode::create(evaluateOperator(op, { otherSide.doubleValue(), number }), otherType);
    }

    return create(op, leftSide.releaseNonNull(), rightSide.releaseNonNull());
}

CSSUnitType CSSCalcOperationNode::primitiveType() const
{
    switch (category()) {
    case CalculationCategory::Number:
#if !ASSERT_DISABLED
        for (auto& child : m_children)
            ASSERT(child->category() == CalculationCategory::Number);
#endif
        return CSSUnitType::CSS_NUMBER;
    case CalculationCategory::Length:
    case CalculationCategory::Percent: {
        if (m_children.isEmpty())
            return CSSUnitType::CSS_UNKNOWN;
        if (m_children.size() == 2) {
            if (m_children[0]->category() == CalculationCategory::Number)
                return m_children[1]->primitiveType();
            if (m_children[1]->category() == CalculationCategory::Number)
                return m_children[0]->primitiveType();
        }
        CSSUnitType firstType = m_children[0]->primitiveType();
        for (auto& child : m_children) {
            if (firstType != child->primitiveType())
                return CSSUnitType::CSS_UNKNOWN;
        }
        return firstType;
    }
    case CalculationCategory::Angle:
        return CSSUnitType::CSS_DEG;
    case CalculationCategory::Time:
        return CSSUnitType::CSS_MS;
    case CalculationCategory::Frequency:
        return CSSUnitType::CSS_HZ;
    case CalculationCategory::PercentLength:
    case CalculationCategory::PercentNumber:
    case CalculationCategory::Other:
        return CSSUnitType::CSS_UNKNOWN;
    }
    ASSERT_NOT_REACHED();
    return CSSUnitType::CSS_UNKNOWN;
}

std::unique_ptr<CalcExpressionNode> CSSCalcOperationNode::createCalcExpression(const CSSToLengthConversionData& conversionData) const
{
    Vector<std::unique_ptr<CalcExpressionNode>> nodes;
    nodes.reserveInitialCapacity(m_children.size());

    for (auto& child : m_children) {
        auto node = child->createCalcExpression(conversionData);
        if (!node)
            return nullptr;
        nodes.uncheckedAppend(WTFMove(node));
    }
    return makeUnique<CalcExpressionOperation>(WTFMove(nodes), m_operator);
}

double CSSCalcOperationNode::doubleValue() const
{
    Vector<double> doubleValues;
    for (auto& child : m_children)
        doubleValues.append(child->doubleValue());
    return evaluate(doubleValues);
}

double CSSCalcOperationNode::computeLengthPx(const CSSToLengthConversionData& conversionData) const
{
    Vector<double> doubleValues;
    for (auto& child : m_children)
        doubleValues.append(child->computeLengthPx(conversionData));
    return evaluate(doubleValues);
}

void CSSCalcOperationNode::collectDirectComputationalDependencies(HashSet<CSSPropertyID>& values) const
{
    for (auto& child : m_children)
        child->collectDirectComputationalDependencies(values);
}

void CSSCalcOperationNode::collectDirectRootComputationalDependencies(HashSet<CSSPropertyID>& values) const
{
    for (auto& child : m_children)
        child->collectDirectRootComputationalDependencies(values);
}

String CSSCalcOperationNode::buildCssText(Vector<String> childExpressions, CalcOperator op)
{
    StringBuilder result;
    result.append('(');
    switch (op) {
    case CalcOperator::Add:
    case CalcOperator::Subtract:
    case CalcOperator::Multiply:
    case CalcOperator::Divide:
        ASSERT(childExpressions.size() == 2);
        result.append(childExpressions[0]);
        result.append(' ');
        result.append(static_cast<char>(op));
        result.append(' ');
        result.append(childExpressions[1]);
        break;
    case CalcOperator::Min:
    case CalcOperator::Max:
        ASSERT(!childExpressions.isEmpty());
        const char* functionName = op == CalcOperator::Min ? "min(" : "max(";
        result.append(functionName);
        result.append(childExpressions[0]);
        for (size_t i = 1; i < childExpressions.size(); ++i) {
            result.append(',');
            result.append(' ');
            result.append(childExpressions[i]);
        }
        result.append(')');
    }
    result.append(')');

    return result.toString();
}

String CSSCalcOperationNode::customCSSText() const
{
    Vector<String> cssTexts;
    for (auto& child : m_children)
        cssTexts.append(child->customCSSText());
    return buildCssText(cssTexts, m_operator);
}

void CSSCalcOperationNode::dump(TextStream& ts) const
{
    ts << "calc operation " << m_operator << " category " << category();

    TextStream::GroupScope scope(ts);
    ts << m_children.size() << " children";
    for (auto& child : m_children)
        ts.dumpProperty("node", child);
}

bool CSSCalcOperationNode::equals(const CSSCalcExpressionNode& exp) const
{
    if (type() != exp.type())
        return false;

    const CSSCalcOperationNode& other = static_cast<const CSSCalcOperationNode&>(exp);

    if (m_children.size() != other.m_children.size() || m_operator != other.m_operator)
        return false;

    for (size_t i = 0; i < m_children.size(); ++i) {
        if (!compareCSSValue(m_children[i], other.m_children[i]))
            return false;
    }
    return true;
}

double CSSCalcOperationNode::evaluateOperator(CalcOperator op, const Vector<double>& children)
{
    switch (op) {
    case CalcOperator::Add:
        ASSERT(children.size() == 2);
        return children[0] + children[1];
    case CalcOperator::Subtract:
        ASSERT(children.size() == 2);
        return children[0] - children[1];
    case CalcOperator::Multiply:
        ASSERT(children.size() == 2);
        return children[0] * children[1];
    case CalcOperator::Divide:
        ASSERT(children.size() == 1 || children.size() == 2);
        if (children.size() == 1)
            return std::numeric_limits<double>::quiet_NaN();
        return children[0] / children[1];
    case CalcOperator::Min: {
        if (children.isEmpty())
            return std::numeric_limits<double>::quiet_NaN();
        double minimum = children[0];
        for (auto child : children)
            minimum = std::min(minimum, child);
        return minimum;
    }
    case CalcOperator::Max: {
        if (children.isEmpty())
            return std::numeric_limits<double>::quiet_NaN();
        double maximum = children[0];
        for (auto child : children)
            maximum = std::max(maximum, child);
        return maximum;
    }
    }
    ASSERT_NOT_REACHED();
    return 0;
}


class CSSCalcExpressionNodeParser {
public:
    explicit CSSCalcExpressionNodeParser(CalculationCategory destinationCategory)
        : m_destinationCategory(destinationCategory)
    { }

    RefPtr<CSSCalcExpressionNode> parseCalc(CSSParserTokenRange, CSSValueID function);
    
private:
    char operatorValue(const CSSParserToken& token)
    {
        if (token.type() == DelimiterToken)
            return token.delimiter();
        return 0;
    }

    bool parseValue(CSSParserTokenRange&, RefPtr<CSSCalcExpressionNode>&);
    bool parseValueTerm(CSSParserTokenRange&, int depth, RefPtr<CSSCalcExpressionNode>&);
    bool parseValueMultiplicativeExpression(CSSParserTokenRange&, int depth, RefPtr<CSSCalcExpressionNode>&);
    bool parseAdditiveValueExpression(CSSParserTokenRange&, int depth, RefPtr<CSSCalcExpressionNode>&);
    bool parseMinMaxExpression(CSSParserTokenRange&, CSSValueID minMaxFunction, int depth, RefPtr<CSSCalcExpressionNode>&);
    bool parseValueExpression(CSSParserTokenRange&, int depth, RefPtr<CSSCalcExpressionNode>&);

    CalculationCategory m_destinationCategory;
};


RefPtr<CSSCalcExpressionNode> CSSCalcExpressionNodeParser::parseCalc(CSSParserTokenRange tokens, CSSValueID function)
{
    RefPtr<CSSCalcExpressionNode> result;
    tokens.consumeWhitespace();
    bool ok = false;
    if (function == CSSValueCalc || function == CSSValueWebkitCalc)
        ok = parseValueExpression(tokens, 0, result);
    else if (function == CSSValueMin || function == CSSValueMax)
        ok = parseMinMaxExpression(tokens, function, 0, result);
    if (!ok || !tokens.atEnd())
        return nullptr;

    if (!result)
        return nullptr;

    LOG_WITH_STREAM(Calc, stream << "CSSCalcExpressionNodeParser::parseCalc " << prettyPrintNode(*result));

    return result;
}

bool CSSCalcExpressionNodeParser::parseValue(CSSParserTokenRange& tokens, RefPtr<CSSCalcExpressionNode>& result)
{
    CSSParserToken token = tokens.consumeIncludingWhitespace();
    if (!(token.type() == NumberToken || token.type() == PercentageToken || token.type() == DimensionToken))
        return false;
    
    CSSUnitType type = token.unitType();
    if (calcUnitCategory(type) == CalculationCategory::Other)
        return false;
    
    result = CSSCalcPrimitiveValueNode::create(CSSPrimitiveValue::create(token.numericValue(), type));
    return true;
}

enum ParseState {
    OK,
    TooDeep,
    NoMoreTokens
};

static ParseState checkDepthAndIndex(int* depth, CSSParserTokenRange tokens)
{
    (*depth)++;
    if (tokens.atEnd())
        return NoMoreTokens;
    if (*depth > maxExpressionDepth)
        return TooDeep;
    return OK;
}

bool CSSCalcExpressionNodeParser::parseValueTerm(CSSParserTokenRange& tokens, int depth, RefPtr<CSSCalcExpressionNode>& result)
{
    if (checkDepthAndIndex(&depth, tokens) != OK)
        return false;

    auto functionId = tokens.peek().functionId();
    
    if (tokens.peek().type() == LeftParenthesisToken || functionId == CSSValueCalc) {
        CSSParserTokenRange innerRange = tokens.consumeBlock();
        tokens.consumeWhitespace();
        innerRange.consumeWhitespace();
        return parseValueExpression(innerRange, depth, result);
    }

    if (functionId == CSSValueMax || functionId == CSSValueMin) {
        CSSParserTokenRange innerRange = tokens.consumeBlock();
        tokens.consumeWhitespace();
        innerRange.consumeWhitespace();
        return parseMinMaxExpression(innerRange, functionId, depth, result);
    }
    
    return parseValue(tokens, result);
}

bool CSSCalcExpressionNodeParser::parseValueMultiplicativeExpression(CSSParserTokenRange& tokens, int depth, RefPtr<CSSCalcExpressionNode>& result)
{
    if (checkDepthAndIndex(&depth, tokens) != OK)
        return false;
    
    if (!parseValueTerm(tokens, depth, result))
        return false;
    
    while (!tokens.atEnd()) {
        char operatorCharacter = operatorValue(tokens.peek());
        if (operatorCharacter != static_cast<char>(CalcOperator::Multiply) && operatorCharacter != static_cast<char>(CalcOperator::Divide))
            break;
        tokens.consumeIncludingWhitespace();
        
        RefPtr<CSSCalcExpressionNode> rhs;
        if (!parseValueTerm(tokens, depth, rhs))
            return false;
        
        result = CSSCalcOperationNode::createSimplified(static_cast<CalcOperator>(operatorCharacter), WTFMove(result), WTFMove(rhs));

        if (!result)
            return false;
    }
    
    return true;
}

bool CSSCalcExpressionNodeParser::parseAdditiveValueExpression(CSSParserTokenRange& tokens, int depth, RefPtr<CSSCalcExpressionNode>& result)
{
    if (checkDepthAndIndex(&depth, tokens) != OK)
        return false;
    
    if (!parseValueMultiplicativeExpression(tokens, depth, result))
        return false;
    
    while (!tokens.atEnd()) {
        char operatorCharacter = operatorValue(tokens.peek());
        if (operatorCharacter != static_cast<char>(CalcOperator::Add) && operatorCharacter != static_cast<char>(CalcOperator::Subtract))
            break;
        if ((&tokens.peek() - 1)->type() != WhitespaceToken)
            return false; // calc(1px+ 2px) is invalid
        tokens.consume();
        if (tokens.peek().type() != WhitespaceToken)
            return false; // calc(1px +2px) is invalid
        tokens.consumeIncludingWhitespace();
        
        RefPtr<CSSCalcExpressionNode> rhs;
        if (!parseValueMultiplicativeExpression(tokens, depth, rhs))
            return false;
        
        result = CSSCalcOperationNode::createSimplified(static_cast<CalcOperator>(operatorCharacter), WTFMove(result), WTFMove(rhs));
        if (!result)
            return false;
    }
    
    return true;
}

bool CSSCalcExpressionNodeParser::parseMinMaxExpression(CSSParserTokenRange& tokens, CSSValueID minMaxFunction, int depth, RefPtr<CSSCalcExpressionNode>& result)
{
    if (checkDepthAndIndex(&depth, tokens) != OK)
        return false;

    CalcOperator op = (minMaxFunction == CSSValueMin) ? CalcOperator::Min : CalcOperator::Max;

    RefPtr<CSSCalcExpressionNode> value;
    if (!parseValueExpression(tokens, depth, value))
        return false;

    Vector<Ref<CSSCalcExpressionNode>> nodes;
    nodes.append(value.releaseNonNull());

    while (!tokens.atEnd()) {
        tokens.consumeWhitespace();
        if (tokens.consume().type() != CommaToken)
            return false;
        tokens.consumeWhitespace();

        if (!parseValueExpression(tokens, depth, value))
            return false;

        nodes.append(value.releaseNonNull());
    }

    result = CSSCalcOperationNode::createMinOrMax(op, WTFMove(nodes), m_destinationCategory);
    return result;
}

bool CSSCalcExpressionNodeParser::parseValueExpression(CSSParserTokenRange& tokens, int depth, RefPtr<CSSCalcExpressionNode>& result)
{
    return parseAdditiveValueExpression(tokens, depth, result);
}


static inline RefPtr<CSSCalcOperationNode> createBlendHalf(const Length& length, const RenderStyle& style, float progress)
{
    return CSSCalcOperationNode::create(CalcOperator::Multiply, createCSS(length, style),
        CSSCalcPrimitiveValueNode::create(CSSPrimitiveValue::create(progress, CSSUnitType::CSS_NUMBER)));
}

static RefPtr<CSSCalcExpressionNode> createCSS(const CalcExpressionNode& node, const RenderStyle& style)
{
    switch (node.type()) {
    case CalcExpressionNodeType::Number: {
        float value = downcast<CalcExpressionNumber>(node).value();
        return CSSCalcPrimitiveValueNode::create(CSSPrimitiveValue::create(value, CSSUnitType::CSS_NUMBER));
    }
    case CalcExpressionNodeType::Length:
        return createCSS(downcast<CalcExpressionLength>(node).length(), style);
    case CalcExpressionNodeType::Operation: {
        auto& operationNode = downcast<CalcExpressionOperation>(node);
        auto& operationChildren = operationNode.children();
        CalcOperator op = operationNode.getOperator();
        if (op == CalcOperator::Min || op == CalcOperator::Max) {
            Vector<Ref<CSSCalcExpressionNode>> values;
            values.reserveInitialCapacity(operationChildren.size());
            for (auto& child : operationChildren) {
                auto cssNode = createCSS(*child, style);
                if (!cssNode)
                    return nullptr;
                values.uncheckedAppend(*cssNode);
            }
            return CSSCalcOperationNode::createMinOrMax(operationNode.getOperator(), WTFMove(values), CalculationCategory::Other);
        }

        if (operationChildren.size() == 2)
            return CSSCalcOperationNode::create(operationNode.getOperator(), createCSS(*operationChildren[0], style), createCSS(*operationChildren[1], style));

        return nullptr;
    }
    case CalcExpressionNodeType::BlendLength: {
        // FIXME: (http://webkit.org/b/122036) Create a CSSCalcExpressionNode equivalent of CalcExpressionBlendLength.
        auto& blend = downcast<CalcExpressionBlendLength>(node);
        float progress = blend.progress();
        return CSSCalcOperationNode::create(CalcOperator::Add, createBlendHalf(blend.from(), style, 1 - progress), createBlendHalf(blend.to(), style, progress));
    }
    case CalcExpressionNodeType::Undefined:
        ASSERT_NOT_REACHED();
    }
    return nullptr;
}

static RefPtr<CSSCalcExpressionNode> createCSS(const Length& length, const RenderStyle& style)
{
    switch (length.type()) {
    case Percent:
    case Fixed:
        return CSSCalcPrimitiveValueNode::create(CSSPrimitiveValue::create(length, style));
    case Calculated:
        return createCSS(length.calculationValue().expression(), style);
    case Auto:
    case Intrinsic:
    case MinIntrinsic:
    case MinContent:
    case MaxContent:
    case FillAvailable:
    case FitContent:
    case Relative:
    case Undefined:
        ASSERT_NOT_REACHED();
    }
    return nullptr;
}

String CSSCalcValue::customCSSText() const
{
    auto expression = m_expression->customCSSText();
    if (expression[0] == '(')
        return makeString("calc", expression);
    return makeString("calc(", expression, ')');
}

bool CSSCalcValue::equals(const CSSCalcValue& other) const
{
    return compareCSSValue(m_expression, other.m_expression);
}

inline double CSSCalcValue::clampToPermittedRange(double value) const
{
    return m_shouldClampToNonNegative && value < 0 ? 0 : value;
}

double CSSCalcValue::doubleValue() const
{
    return clampToPermittedRange(m_expression->doubleValue());
}

double CSSCalcValue::computeLengthPx(const CSSToLengthConversionData& conversionData) const
{
    return clampToPermittedRange(m_expression->computeLengthPx(conversionData));
}

bool CSSCalcValue::isCalcFunction(CSSValueID functionId)
{
    switch (functionId) {
    case CSSValueCalc:
    case CSSValueWebkitCalc:
    case CSSValueMin:
    case CSSValueMax:
        return true;
    default:
        return false;
    }
    return false;
}

void CSSCalcValue::dump(TextStream& ts) const
{
    ts << indent << "(" << "CSSCalcValue";

    TextStream multilineStream;
    multilineStream.setIndent(ts.indent() + 2);

    multilineStream.dumpProperty("should clamp non-negative", m_shouldClampToNonNegative);
    multilineStream.dumpProperty("expression", m_expression.get());

    ts << multilineStream.release();
    ts << ")\n";
}

RefPtr<CSSCalcValue> CSSCalcValue::create(CSSValueID function, const CSSParserTokenRange& tokens, CalculationCategory destinationCategory, ValueRange range)
{
    CSSCalcExpressionNodeParser parser(destinationCategory);
    auto expression = parser.parseCalc(tokens, function);
    if (!expression)
        return nullptr;

    auto result = adoptRef(new CSSCalcValue(expression.releaseNonNull(), range != ValueRangeAll));
    LOG_WITH_STREAM(Calc, stream << "CSSCalcValue::create from tokens: " << *result);
    return result;
}
    
RefPtr<CSSCalcValue> CSSCalcValue::create(const CalculationValue& value, const RenderStyle& style)
{
    auto expression = createCSS(value.expression(), style);
    if (!expression)
        return nullptr;
    auto result = adoptRef(new CSSCalcValue(expression.releaseNonNull(), value.shouldClampToNonNegative()));
    LOG_WITH_STREAM(Calc, stream << "CSSCalcValue::create from CalculationValue: " << *result);
    return result;
}

TextStream& operator<<(TextStream& ts, CalculationCategory category)
{
    switch (category) {
    case CalculationCategory::Number: ts << "number"; break;
    case CalculationCategory::Length: ts << "length"; break;
    case CalculationCategory::Percent: ts << "percent"; break;
    case CalculationCategory::PercentNumber: ts << "percent-number"; break;
    case CalculationCategory::PercentLength: ts << "percent-length"; break;
    case CalculationCategory::Angle: ts << "angle"; break;
    case CalculationCategory::Time: ts << "time"; break;
    case CalculationCategory::Frequency: ts << "frequency"; break;
    case CalculationCategory::Other: ts << "other"; break;
    }

    return ts;
}

TextStream& operator<<(TextStream& ts, const CSSCalcValue& value)
{
    value.dump(ts);
    return ts;
}

} // namespace WebCore