// Copyright 2014 The Chromium Authors. All rights reserved.
// Use of this source code is governed by a BSD-style license that can be
// found in the LICENSE file.

#include "third_party/blink/renderer/core/css/parser/sizes_math_function_parser.h"

#include "third_party/blink/renderer/core/css/media_values.h"
#include "third_party/blink/renderer/core/css/parser/css_parser_token.h"
#include "third_party/blink/renderer/core/css_value_keywords.h"
#include "third_party/blink/renderer/platform/runtime_enabled_features.h"

namespace blink {

SizesMathFunctionParser::SizesMathFunctionParser(CSSParserTokenRange range,
                                                 MediaValues* media_values)
    : media_values_(media_values), result_(0) {
  is_valid_ = CalcToReversePolishNotation(range) && Calculate();
}

float SizesMathFunctionParser::Result() const {
  DCHECK(is_valid_);
  return result_;
}

static bool OperatorPriority(CSSMathOperator cc, bool& high_priority) {
  if (cc == CSSMathOperator::kAdd || cc == CSSMathOperator::kSubtract)
    high_priority = false;
  else if (cc == CSSMathOperator::kMultiply || cc == CSSMathOperator::kDivide)
    high_priority = true;
  else
    return false;
  return true;
}

bool SizesMathFunctionParser::HandleOperator(Vector<CSSParserToken>& stack,
                                             const CSSParserToken& token) {
  // If the token is not an operator, then return. Else determine the
  // precedence of the new operator (op1).
  bool incoming_operator_priority;
  if (!OperatorPriority(ParseCSSArithmeticOperator(token),
                        incoming_operator_priority))
    return false;

  while (!stack.IsEmpty()) {
    // While there is an operator (op2) at the top of the stack,
    // determine its precedence, and...
    const CSSParserToken& top_of_stack = stack.back();
    if (top_of_stack.GetType() != kDelimiterToken)
      break;
    bool stack_operator_priority;
    if (!OperatorPriority(ParseCSSArithmeticOperator(top_of_stack),
                          stack_operator_priority))
      return false;
    // ...if op1 is left-associative (all currently supported
    // operators are) and its precedence is equal to that of op2, or
    // op1 has precedence less than that of op2, ...
    if (incoming_operator_priority && !stack_operator_priority)
      break;
    // ...pop op2 off the stack and add it to the output queue.
    AppendOperator(top_of_stack);
    stack.pop_back();
  }
  // Push op1 onto the stack.
  stack.push_back(token);
  return true;
}

bool SizesMathFunctionParser::HandleRightParenthesis(
    Vector<CSSParserToken>& stack) {
  // If the token is a right parenthesis:
  // Until the token at the top of the stack is a left parenthesis or a
  // function, pop operators off the stack onto the output queue.
  // Also count the number of commas to get the number of function
  // parameters if this right parenthesis closes a function.
  wtf_size_t comma_count = 0;
  while (!stack.IsEmpty() && stack.back().GetType() != kLeftParenthesisToken &&
         stack.back().GetType() != kFunctionToken) {
    if (stack.back().GetType() == kCommaToken)
      ++comma_count;
    else
      AppendOperator(stack.back());
    stack.pop_back();
  }
  // If the stack runs out without finding a left parenthesis, then there
  // are mismatched parentheses.
  if (stack.IsEmpty())
    return false;

  CSSParserToken left_side = stack.back();
  stack.pop_back();

  if (left_side.GetType() == kLeftParenthesisToken ||
      left_side.FunctionId() == CSSValueID::kCalc) {
    // There should be exactly one calculation within calc() or parentheses.
    return !comma_count;
  }

  if (left_side.FunctionId() == CSSValueID::kClamp) {
    if (comma_count != 2)
      return false;
    // Convert clamp(MIN, VAL, MAX) into max(MIN, min(VAL, MAX))
    // https://www.w3.org/TR/css-values-4/#calc-notation
    value_list_.emplace_back(CSSMathOperator::kMin);
    value_list_.emplace_back(CSSMathOperator::kMax);
    return true;
  }

  // Break variadic min/max() into binary operations to fit in the reverse
  // polish notation.
  CSSMathOperator op = left_side.FunctionId() == CSSValueID::kMin
                           ? CSSMathOperator::kMin
                           : CSSMathOperator::kMax;
  for (wtf_size_t i = 0; i < comma_count; ++i)
    value_list_.emplace_back(op);
  return true;
}

bool SizesMathFunctionParser::HandleComma(Vector<CSSParserToken>& stack,
                                          const CSSParserToken& token) {
  // Treat comma as a binary right-associative operation for now, so that
  // when reaching the right parenthesis of the function, we can get the
  // number of parameters by counting the number of commas.
  while (!stack.IsEmpty() && stack.back().GetType() != kFunctionToken &&
         stack.back().GetType() != kLeftParenthesisToken &&
         stack.back().GetType() != kCommaToken) {
    AppendOperator(stack.back());
    stack.pop_back();
  }
  // Commas are allowed as function parameter separators only
  if (stack.IsEmpty() || stack.back().GetType() == kLeftParenthesisToken)
    return false;
  stack.push_back(token);
  return true;
}

void SizesMathFunctionParser::AppendNumber(const CSSParserToken& token) {
  SizesMathValue value;
  value.value = token.NumericValue();
  value_list_.push_back(value);
}

bool SizesMathFunctionParser::AppendLength(const CSSParserToken& token) {
  SizesMathValue value;
  double result = 0;
  if (!media_values_->ComputeLength(token.NumericValue(), token.GetUnitType(),
                                    result))
    return false;
  value.value = result;
  value.is_length = true;
  value_list_.push_back(value);
  return true;
}

void SizesMathFunctionParser::AppendOperator(const CSSParserToken& token) {
  value_list_.emplace_back(ParseCSSArithmeticOperator(token));
}

bool SizesMathFunctionParser::CalcToReversePolishNotation(
    CSSParserTokenRange range) {
  // This method implements the shunting yard algorithm, to turn the calc syntax
  // into a reverse polish notation.
  // http://en.wikipedia.org/wiki/Shunting-yard_algorithm

  Vector<CSSParserToken> stack;
  while (!range.AtEnd()) {
    const CSSParserToken& token = range.Consume();
    switch (token.GetType()) {
      case kNumberToken:
        AppendNumber(token);
        break;
      case kDimensionToken:
        if (!CSSPrimitiveValue::IsLength(token.GetUnitType()) ||
            !AppendLength(token))
          return false;
        break;
      case kDelimiterToken:
        if (!HandleOperator(stack, token))
          return false;
        break;
      case kFunctionToken:
        if (token.FunctionId() == CSSValueID::kMin ||
            token.FunctionId() == CSSValueID::kMax ||
            token.FunctionId() == CSSValueID::kClamp) {
          stack.push_back(token);
          break;
        }
        if (token.FunctionId() != CSSValueID::kCalc)
          return false;
        // "calc(" is the same as "("
        FALLTHROUGH;
      case kLeftParenthesisToken:
        // If the token is a left parenthesis, then push it onto the stack.
        stack.push_back(token);
        break;
      case kRightParenthesisToken:
        if (!HandleRightParenthesis(stack))
          return false;
        break;
      case kCommaToken:
        if (!HandleComma(stack, token))
          return false;
        break;
      case kWhitespaceToken:
      case kEOFToken:
        break;
      case kCommentToken:
        NOTREACHED();
        FALLTHROUGH;
      case kCDOToken:
      case kCDCToken:
      case kAtKeywordToken:
      case kHashToken:
      case kUrlToken:
      case kBadUrlToken:
      case kPercentageToken:
      case kIncludeMatchToken:
      case kDashMatchToken:
      case kPrefixMatchToken:
      case kSuffixMatchToken:
      case kSubstringMatchToken:
      case kColumnToken:
      case kUnicodeRangeToken:
      case kIdentToken:
      case kColonToken:
      case kSemicolonToken:
      case kLeftBraceToken:
      case kLeftBracketToken:
      case kRightBraceToken:
      case kRightBracketToken:
      case kStringToken:
      case kBadStringToken:
        return false;
    }
  }

  // When there are no more tokens to read:
  // While there are still operator tokens in the stack:
  while (!stack.IsEmpty()) {
    // If the operator token on the top of the stack is a parenthesis, then
    // there are unclosed parentheses.
    CSSParserTokenType type = stack.back().GetType();
    if (type != kLeftParenthesisToken && type != kFunctionToken) {
      // Pop the operator onto the output queue.
      AppendOperator(stack.back());
    }
    stack.pop_back();
  }
  return true;
}

static bool OperateOnStack(Vector<SizesMathValue>& stack,
                           CSSMathOperator operation) {
  if (stack.size() < 2)
    return false;
  SizesMathValue right_operand = stack.back();
  stack.pop_back();
  SizesMathValue left_operand = stack.back();
  stack.pop_back();
  bool is_length;
  switch (operation) {
    case CSSMathOperator::kAdd:
      if (right_operand.is_length != left_operand.is_length)
        return false;
      is_length = (right_operand.is_length && left_operand.is_length);
      stack.push_back(
          SizesMathValue(left_operand.value + right_operand.value, is_length));
      break;
    case CSSMathOperator::kSubtract:
      if (right_operand.is_length != left_operand.is_length)
        return false;
      is_length = (right_operand.is_length && left_operand.is_length);
      stack.push_back(
          SizesMathValue(left_operand.value - right_operand.value, is_length));
      break;
    case CSSMathOperator::kMultiply:
      if (right_operand.is_length && left_operand.is_length)
        return false;
      is_length = (right_operand.is_length || left_operand.is_length);
      stack.push_back(
          SizesMathValue(left_operand.value * right_operand.value, is_length));
      break;
    case CSSMathOperator::kDivide:
      if (right_operand.is_length || right_operand.value == 0)
        return false;
      stack.push_back(SizesMathValue(left_operand.value / right_operand.value,
                                     left_operand.is_length));
      break;
    case CSSMathOperator::kMin:
      if (right_operand.is_length != left_operand.is_length)
        return false;
      is_length = (right_operand.is_length && left_operand.is_length);
      stack.push_back(SizesMathValue(
          std::min(left_operand.value, right_operand.value), is_length));
      break;
    case CSSMathOperator::kMax:
      if (right_operand.is_length != left_operand.is_length)
        return false;
      is_length = (right_operand.is_length && left_operand.is_length);
      stack.push_back(SizesMathValue(
          std::max(left_operand.value, right_operand.value), is_length));
      break;
    default:
      return false;
  }
  return true;
}

bool SizesMathFunctionParser::Calculate() {
  Vector<SizesMathValue> stack;
  for (const auto& value : value_list_) {
    if (value.operation == CSSMathOperator::kInvalid) {
      stack.push_back(value);
    } else {
      if (!OperateOnStack(stack, value.operation))
        return false;
    }
  }
  if (stack.size() == 1 && stack.back().is_length) {
    result_ = std::max(clampTo<float>(stack.back().value), (float)0.0);
    return true;
  }
  return false;
}

}  // namespace blink