node_binary.go

package expressionlanguage

import (
	"fmt"
	"math"
	"regexp"
	"strconv"
	"strings"
)

type binaryNode struct {
	operator string
	left     Node
	right    Node
}

func NewBinary(operator string, left, right Node) Node {
	return &binaryNode{operator: operator, left: left, right: right}
}
func (n *binaryNode) Compile(functions Functions) (Program, error) {
	return compilePublic(n, functions)
}
func (n *binaryNode) Evaluate(functions Functions, variables Variables) (any, error) {
	return evaluatePublic(n, functions, variables)
}
func (n *binaryNode) compileInternal(functions Functions) (internalProgram, error) {
	if !supportedBinaryOperator(n.operator) {
		return nil, unsupportedBinaryOperator(n.operator)
	}
	if n.operator == "+" {
		return n.compileAddition(functions)
	}
	if n.operator == "matches" && isStaticNode(n.right) {
		result, err := evaluateNodeInternal(n.right, functions, evaluationContext{})
		if err != nil {
			return nil, err
		}
		pattern, ok := result.value.(string)
		if !ok {
			return nil, newSyntaxError(`The regex passed to "matches" must be a string`, 0, "")
		}
		if _, err := compileExpressionRegexp(pattern); err != nil {
			return nil, err
		}
	}
	left, err := compileNode(n.left, functions)
	if err != nil {
		return nil, err
	}
	right, err := compileNode(n.right, functions)
	if err != nil {
		return nil, err
	}
	return func(context evaluationContext) (evaluationResult, error) {
		leftResult, err := left(context)
		if err != nil || leftResult.shortCircuit {
			return leftResult, err
		}
		if (n.operator == "and" || n.operator == "&&") && !truthy(leftResult.value) {
			return evaluationResult{value: false}, nil
		}
		if (n.operator == "or" || n.operator == "||") && truthy(leftResult.value) {
			return evaluationResult{value: true}, nil
		}
		rightResult, err := right(context)
		if err != nil || rightResult.shortCircuit {
			return rightResult, err
		}
		value, err := evaluateBinary(n.operator, leftResult.value, rightResult.value)
		return evaluationResult{value: value}, err
	}, nil
}
func (n *binaryNode) evaluateInternal(functions Functions, context evaluationContext) (evaluationResult, error) {
	if !supportedBinaryOperator(n.operator) {
		return evaluationResult{}, unsupportedBinaryOperator(n.operator)
	}
	if n.operator == "+" {
		accumulator := numericSum{}
		if result, err := evaluateAdditionNode(n, functions, context, &accumulator); err != nil || result.shortCircuit {
			return result, err
		}
		return evaluationResult{value: accumulator.result()}, nil
	}
	left, err := evaluateNodeInternal(n.left, functions, context)
	if err != nil || left.shortCircuit {
		return left, err
	}
	if (n.operator == "and" || n.operator == "&&") && !truthy(left.value) {
		return evaluationResult{value: false}, nil
	}
	if (n.operator == "or" || n.operator == "||") && truthy(left.value) {
		return evaluationResult{value: true}, nil
	}
	right, err := evaluateNodeInternal(n.right, functions, context)
	if err != nil || right.shortCircuit {
		return right, err
	}
	value, err := evaluateBinary(n.operator, left.value, right.value)
	return evaluationResult{value: value}, err
}

func (n *binaryNode) compileAddition(functions Functions) (internalProgram, error) {
	nodes := make([]Node, 0, countAdditionNodes(n))
	collectAdditionNodes(n, &nodes)
	programs := make([]internalProgram, len(nodes))
	for i, node := range nodes {
		program, err := compileNode(node, functions)
		if err != nil {
			return nil, err
		}
		programs[i] = program
	}
	return func(context evaluationContext) (evaluationResult, error) {
		accumulator := numericSum{}
		for _, program := range programs {
			result, err := program(context)
			if err != nil || result.shortCircuit {
				return result, err
			}
			if err := accumulator.add(result.value); err != nil {
				return evaluationResult{}, err
			}
		}
		return evaluationResult{value: accumulator.result()}, nil
	}, nil
}

func countAdditionNodes(node Node) int {
	if binary, ok := node.(*binaryNode); ok && binary.operator == "+" {
		return countAdditionNodes(binary.left) + countAdditionNodes(binary.right)
	}
	return 1
}

func collectAdditionNodes(node Node, nodes *[]Node) {
	if binary, ok := node.(*binaryNode); ok && binary.operator == "+" {
		collectAdditionNodes(binary.left, nodes)
		collectAdditionNodes(binary.right, nodes)
		return
	}
	*nodes = append(*nodes, node)
}

func evaluateAdditionNode(node Node, functions Functions, context evaluationContext, accumulator *numericSum) (evaluationResult, error) {
	if binary, ok := node.(*binaryNode); ok && binary.operator == "+" {
		result, err := evaluateAdditionNode(binary.left, functions, context, accumulator)
		if err != nil || result.shortCircuit {
			return result, err
		}
		return evaluateAdditionNode(binary.right, functions, context, accumulator)
	}
	result, err := evaluateNodeInternal(node, functions, context)
	if err != nil || result.shortCircuit {
		return result, err
	}
	if err := accumulator.add(result.value); err != nil {
		return evaluationResult{}, err
	}
	return evaluationResult{}, nil
}

type numericSum struct {
	integer  int
	floating float64
	isFloat  bool
}

func (s *numericSum) add(value any) error {
	switch value := value.(type) {
	case int:
		if s.isFloat {
			s.floating += float64(value)
		} else {
			s.integer += value
		}
	case float64:
		if !s.isFloat {
			s.floating = float64(s.integer)
			s.isFloat = true
		}
		s.floating += value
	default:
		return fmt.Errorf("operator %q requires numbers", "+")
	}
	return nil
}

func (s *numericSum) result() any {
	if s.isFloat {
		return s.floating
	}
	return s.integer
}
func (n *binaryNode) Dump() string {
	return "(" + n.left.Dump() + " " + n.operator + " " + n.right.Dump() + ")"
}

func supportedBinaryOperator(operator string) bool {
	switch operator {
	case "or", "||", "xor", "and", "&&", "&", "|", "^", "<<", ">>",
		"<", "<=", ">", ">=", "===", "!==", "==", "!=", "-", "+", "*", "/", "%", "**", "~",
		"in", "not in", "..", "starts with", "ends with", "contains", "matches":
		return true
	default:
		return false
	}
}

func unsupportedBinaryOperator(operator string) error {
	return fmt.Errorf(`BinaryNode does not support the %q operator`, operator)
}

func evaluateBinary(operator string, left, right any) (any, error) {
	switch operator {
	case "and", "&&":
		return truthy(left) && truthy(right), nil
	case "or", "||":
		return truthy(left) || truthy(right), nil
	case "xor":
		return truthy(left) != truthy(right), nil
	case "&", "|", "^", "<<", ">>":
		leftInt, leftOK := asInt(left)
		rightInt, rightOK := asInt(right)
		if !leftOK || !rightOK {
			return nil, fmt.Errorf("operator %q requires integers", operator)
		}
		switch operator {
		case "&":
			return leftInt & rightInt, nil
		case "|":
			return leftInt | rightInt, nil
		case "^":
			return leftInt ^ rightInt, nil
		case "<<":
			return leftInt << uint(rightInt), nil
		default:
			return leftInt >> uint(rightInt), nil
		}
	case "===":
		return strictEqual(left, right), nil
	case "!==":
		return !strictEqual(left, right), nil
	case "==":
		return looseEqual(left, right), nil
	case "!=":
		return !looseEqual(left, right), nil
	case "<", "<=", ">", ">=":
		comparison, err := compareValues(left, right)
		if err != nil {
			return nil, err
		}
		switch operator {
		case "<":
			return comparison < 0, nil
		case "<=":
			return comparison <= 0, nil
		case ">":
			return comparison > 0, nil
		default:
			return comparison >= 0, nil
		}
	case "+", "-", "*", "/", "%", "**":
		return arithmetic(operator, left, right)
	case "~":
		return stringify(left) + stringify(right), nil
	case "in", "not in":
		found, err := containsStrict(right, left)
		if err != nil {
			return nil, err
		}
		if operator == "not in" {
			return !found, nil
		}
		return found, nil
	case "..":
		start, startOK := asInt(left)
		end, endOK := asInt(right)
		if !startOK || !endOK {
			return nil, fmt.Errorf("range boundaries must be integers")
		}
		step := 1
		if start > end {
			step = -1
		}
		result := make([]any, 0, absInt(end-start)+1)
		for value := start; ; value += step {
			result = append(result, value)
			if value == end {
				break
			}
		}
		return result, nil
	case "starts with":
		return strings.HasPrefix(stringify(left), stringify(right)), nil
	case "ends with":
		return strings.HasSuffix(stringify(left), stringify(right)), nil
	case "contains":
		return strings.Contains(stringify(left), stringify(right)), nil
	case "matches":
		pattern, ok := right.(string)
		if !ok {
			return nil, newSyntaxError(`The regex passed to "matches" must be a string`, 0, "")
		}
		expression, err := compileExpressionRegexp(pattern)
		if err != nil {
			return nil, err
		}
		if expression.MatchString(stringify(left)) {
			return 1, nil
		}
		return 0, nil
	default:
		return nil, unsupportedBinaryOperator(operator)
	}
}

func arithmetic(operator string, left, right any) (any, error) {
	const (
		divisionByZero = "Division by zero."
		moduloByZero   = "Modulo by zero."
	)
	leftInt, leftIsInt := left.(int)
	rightInt, rightIsInt := right.(int)
	if leftIsInt && rightIsInt {
		switch operator {
		case "+":
			return leftInt + rightInt, nil
		case "-":
			return leftInt - rightInt, nil
		case "*":
			return leftInt * rightInt, nil
		case "/":
			if rightInt == 0 {
				return nil, fmt.Errorf("%s", divisionByZero)
			}
			return leftInt / rightInt, nil
		case "%":
			if rightInt == 0 {
				return nil, fmt.Errorf("%s", moduloByZero)
			}
			return leftInt % rightInt, nil
		case "**":
			return int(math.Pow(float64(leftInt), float64(rightInt))), nil
		}
	}
	leftFloat, leftOK := asFloat(left)
	rightFloat, rightOK := asFloat(right)
	if !leftOK || !rightOK {
		return nil, fmt.Errorf("operator %q requires numbers", operator)
	}
	switch operator {
	case "+":
		return leftFloat + rightFloat, nil
	case "-":
		return leftFloat - rightFloat, nil
	case "*":
		return leftFloat * rightFloat, nil
	case "/":
		if rightFloat == 0 {
			return nil, fmt.Errorf("%s", divisionByZero)
		}
		return leftFloat / rightFloat, nil
	case "%":
		if rightFloat == 0 {
			return nil, fmt.Errorf("%s", moduloByZero)
		}
		return math.Mod(leftFloat, rightFloat), nil
	default:
		return math.Pow(leftFloat, rightFloat), nil
	}
}

func asInt(value any) (int, bool) {
	integer, ok := value.(int)
	return integer, ok
}

func asFloat(value any) (float64, bool) {
	switch value := value.(type) {
	case int:
		return float64(value), true
	case float64:
		return value, true
	default:
		return 0, false
	}
}

func looseEqual(left, right any) bool {
	if strictEqual(left, right) {
		return true
	}
	if leftNumber, ok := numericValue(left); ok {
		if rightNumber, ok := numericValue(right); ok {
			return leftNumber == rightNumber
		}
	}
	return stringify(left) == stringify(right)
}

func numericValue(value any) (float64, bool) {
	if number, ok := asFloat(value); ok {
		return number, true
	}
	text, ok := value.(string)
	if !ok {
		return 0, false
	}
	number, err := strconv.ParseFloat(text, 64)
	return number, err == nil
}

func compareValues(left, right any) (int, error) {
	if leftNumber, ok := asFloat(left); ok {
		rightNumber, ok := asFloat(right)
		if !ok {
			return 0, fmt.Errorf("cannot compare %T and %T", left, right)
		}
		switch {
		case leftNumber < rightNumber:
			return -1, nil
		case leftNumber > rightNumber:
			return 1, nil
		default:
			return 0, nil
		}
	}
	leftString, leftOK := left.(string)
	rightString, rightOK := right.(string)
	if leftOK && rightOK {
		return strings.Compare(leftString, rightString), nil
	}
	return 0, fmt.Errorf("cannot compare %T and %T", left, right)
}

func containsStrict(collection, needle any) (bool, error) {
	switch collection := collection.(type) {
	case []any:
		for _, value := range collection {
			if strictEqual(value, needle) {
				return true, nil
			}
		}
		return false, nil
	case OrderedMap:
		for _, entry := range collection {
			if strictEqual(entry.Value, needle) {
				return true, nil
			}
		}
		return false, nil
	case map[any]any:
		for _, value := range collection {
			if strictEqual(value, needle) {
				return true, nil
			}
		}
		return false, nil
	default:
		return false, fmt.Errorf("right operand of in must be a collection")
	}
}

func compileExpressionRegexp(pattern string) (*regexp.Regexp, error) {
	if pattern == "" || isAlphaNumeric(pattern[0]) || pattern[0] == '\\' || isSpace(pattern[0]) {
		return nil, invalidRegexp(pattern, "Delimiter must not be alphanumeric")
	}
	delimiter := pattern[0]
	closing := -1
	escaped := false
	for i := 1; i < len(pattern); i++ {
		if escaped {
			escaped = false
			continue
		}
		if pattern[i] == '\\' {
			escaped = true
			continue
		}
		if pattern[i] == delimiter {
			closing = i
		}
	}
	if closing < 1 {
		return nil, invalidRegexp(pattern, "No ending delimiter found")
	}
	body := pattern[1:closing]
	modifiers := pattern[closing+1:]
	var prefix strings.Builder
	for _, modifier := range modifiers {
		switch modifier {
		case 'i', 'm', 's':
			prefix.WriteString(string(modifier))
		default:
			return nil, invalidRegexp(pattern, fmt.Sprintf("Unknown modifier %q", modifier))
		}
	}
	if prefix.String() != "" {
		body = "(?" + prefix.String() + ")" + body
	}
	expression, err := regexp.Compile(body)
	if err != nil {
		return nil, invalidRegexp(pattern, err.Error())
	}
	return expression, nil
}

func invalidRegexp(pattern, detail string) error {
	return newSyntaxError(fmt.Sprintf(`Regexp %q passed to "matches" is not valid: %s`, pattern, detail), 0, "")
}

func isStaticNode(node Node) bool {
	switch node := node.(type) {
	case *constantNode:
		return true
	case *unaryNode:
		return isStaticNode(node.operand)
	case *binaryNode:
		return isStaticNode(node.left) && isStaticNode(node.right)
	case *arrayNode:
		for _, element := range node.elements {
			if element.Key != nil && !isStaticNode(element.Key) {
				return false
			}
			if !isStaticNode(element.Value) {
				return false
			}
		}
		return true
	case *conditionalNode:
		return isStaticNode(node.condition) && isStaticNode(node.whenTrue) && isStaticNode(node.whenFalse)
	default:
		return false
	}
}

func stringify(value any) string {
	if value == nil {
		return ""
	}
	if value == true {
		return "1"
	}
	if value == false {
		return ""
	}
	return fmt.Sprint(value)
}

func absInt(value int) int {
	if value < 0 {
		return -value
	}
	return value
}

func isAlphaNumeric(value byte) bool {
	return value >= 'a' && value <= 'z' || value >= 'A' && value <= 'Z' || value >= '0' && value <= '9'
}

func isSpace(value byte) bool {
	switch value {
	case ' ', '\t', '\r', '\n', '\v', '\f':
		return true
	default:
		return false
	}
}