From dd136858f1ea40ad3c94191d647487fa4f31926c Mon Sep 17 00:00:00 2001 From: Daniel Baumann Date: Fri, 18 Oct 2024 20:33:49 +0200 Subject: Adding upstream version 9.0.0. Signed-off-by: Daniel Baumann --- modules/templates/eval/eval.go | 344 +++++++++++++++++++++++++++++++++++++++++ 1 file changed, 344 insertions(+) create mode 100644 modules/templates/eval/eval.go (limited to 'modules/templates/eval/eval.go') diff --git a/modules/templates/eval/eval.go b/modules/templates/eval/eval.go new file mode 100644 index 0000000..5d4ac91 --- /dev/null +++ b/modules/templates/eval/eval.go @@ -0,0 +1,344 @@ +// Copyright 2023 The Gitea Authors. All rights reserved. +// SPDX-License-Identifier: MIT + +package eval + +import ( + "fmt" + "strconv" + "strings" + + "code.gitea.io/gitea/modules/util" +) + +type Num struct { + Value any // int64 or float64, nil on error +} + +var opPrecedence = map[string]int{ + // "(": 1, this is for low precedence like function calls, they are handled separately + "or": 2, + "and": 3, + "not": 4, + "==": 5, "!=": 5, "<": 5, "<=": 5, ">": 5, ">=": 5, + "+": 6, "-": 6, + "*": 7, "/": 7, +} + +type stack[T any] struct { + name string + elems []T +} + +func (s *stack[T]) push(t T) { + s.elems = append(s.elems, t) +} + +func (s *stack[T]) pop() T { + if len(s.elems) == 0 { + panic(s.name + " stack is empty") + } + t := s.elems[len(s.elems)-1] + s.elems = s.elems[:len(s.elems)-1] + return t +} + +func (s *stack[T]) peek() T { + if len(s.elems) == 0 { + panic(s.name + " stack is empty") + } + return s.elems[len(s.elems)-1] +} + +type operator string + +type eval struct { + stackNum stack[Num] + stackOp stack[operator] + funcMap map[string]func([]Num) Num +} + +func newEval() *eval { + e := &eval{} + e.stackNum.name = "num" + e.stackOp.name = "op" + return e +} + +func toNum(v any) (Num, error) { + switch v := v.(type) { + case string: + if strings.Contains(v, ".") { + n, err := strconv.ParseFloat(v, 64) + if err != nil { + return Num{n}, err + } + return Num{n}, nil + } + n, err := strconv.ParseInt(v, 10, 64) + if err != nil { + return Num{n}, err + } + return Num{n}, nil + case float32, float64: + n, _ := util.ToFloat64(v) + return Num{n}, nil + default: + n, err := util.ToInt64(v) + if err != nil { + return Num{n}, err + } + return Num{n}, nil + } +} + +func truth(b bool) int64 { + if b { + return int64(1) + } + return int64(0) +} + +func applyOp2Generic[T int64 | float64](op operator, n1, n2 T) Num { + switch op { + case "+": + return Num{n1 + n2} + case "-": + return Num{n1 - n2} + case "*": + return Num{n1 * n2} + case "/": + return Num{n1 / n2} + case "==": + return Num{truth(n1 == n2)} + case "!=": + return Num{truth(n1 != n2)} + case "<": + return Num{truth(n1 < n2)} + case "<=": + return Num{truth(n1 <= n2)} + case ">": + return Num{truth(n1 > n2)} + case ">=": + return Num{truth(n1 >= n2)} + case "and": + t1, _ := util.ToFloat64(n1) + t2, _ := util.ToFloat64(n2) + return Num{truth(t1 != 0 && t2 != 0)} + case "or": + t1, _ := util.ToFloat64(n1) + t2, _ := util.ToFloat64(n2) + return Num{truth(t1 != 0 || t2 != 0)} + } + panic("unknown operator: " + string(op)) +} + +func applyOp2(op operator, n1, n2 Num) Num { + float := false + if _, ok := n1.Value.(float64); ok { + float = true + } else if _, ok = n2.Value.(float64); ok { + float = true + } + if float { + f1, _ := util.ToFloat64(n1.Value) + f2, _ := util.ToFloat64(n2.Value) + return applyOp2Generic(op, f1, f2) + } + return applyOp2Generic(op, n1.Value.(int64), n2.Value.(int64)) +} + +func toOp(v any) (operator, error) { + if v, ok := v.(string); ok { + return operator(v), nil + } + return "", fmt.Errorf(`unsupported token type "%T"`, v) +} + +func (op operator) hasOpenBracket() bool { + return strings.HasSuffix(string(op), "(") // it's used to support functions like "sum(" +} + +func (op operator) isComma() bool { + return op == "," +} + +func (op operator) isCloseBracket() bool { + return op == ")" +} + +type ExprError struct { + msg string + tokens []any + err error +} + +func (err ExprError) Error() string { + sb := strings.Builder{} + sb.WriteString(err.msg) + sb.WriteString(" [ ") + for _, token := range err.tokens { + _, _ = fmt.Fprintf(&sb, `"%v" `, token) + } + sb.WriteString("]") + if err.err != nil { + sb.WriteString(": ") + sb.WriteString(err.err.Error()) + } + return sb.String() +} + +func (err ExprError) Unwrap() error { + return err.err +} + +func (e *eval) applyOp() { + op := e.stackOp.pop() + if op == "not" { + num := e.stackNum.pop() + i, _ := util.ToInt64(num.Value) + e.stackNum.push(Num{truth(i == 0)}) + } else if op.hasOpenBracket() || op.isCloseBracket() || op.isComma() { + panic(fmt.Sprintf("incomplete sub-expression with operator %q", op)) + } else { + num2 := e.stackNum.pop() + num1 := e.stackNum.pop() + e.stackNum.push(applyOp2(op, num1, num2)) + } +} + +func (e *eval) exec(tokens ...any) (ret Num, err error) { + defer func() { + if r := recover(); r != nil { + rErr, ok := r.(error) + if !ok { + rErr = fmt.Errorf("%v", r) + } + err = ExprError{"invalid expression", tokens, rErr} + } + }() + for _, token := range tokens { + n, err := toNum(token) + if err == nil { + e.stackNum.push(n) + continue + } + + op, err := toOp(token) + if err != nil { + return Num{}, ExprError{"invalid expression", tokens, err} + } + + switch { + case op.hasOpenBracket(): + e.stackOp.push(op) + case op.isCloseBracket(), op.isComma(): + var stackTopOp operator + for len(e.stackOp.elems) > 0 { + stackTopOp = e.stackOp.peek() + if stackTopOp.hasOpenBracket() || stackTopOp.isComma() { + break + } + e.applyOp() + } + if op.isCloseBracket() { + nums := []Num{e.stackNum.pop()} + for !e.stackOp.peek().hasOpenBracket() { + stackTopOp = e.stackOp.pop() + if !stackTopOp.isComma() { + return Num{}, ExprError{"bracket doesn't match", tokens, nil} + } + nums = append(nums, e.stackNum.pop()) + } + for i, j := 0, len(nums)-1; i < j; i, j = i+1, j-1 { + nums[i], nums[j] = nums[j], nums[i] // reverse nums slice, to get the right order for arguments + } + stackTopOp = e.stackOp.pop() + fn := string(stackTopOp[:len(stackTopOp)-1]) + if fn == "" { + if len(nums) != 1 { + return Num{}, ExprError{"too many values in one bracket", tokens, nil} + } + e.stackNum.push(nums[0]) + } else if f, ok := e.funcMap[fn]; ok { + e.stackNum.push(f(nums)) + } else { + return Num{}, ExprError{"unknown function: " + fn, tokens, nil} + } + } else { + e.stackOp.push(op) + } + default: + for len(e.stackOp.elems) > 0 && len(e.stackNum.elems) > 0 { + stackTopOp := e.stackOp.peek() + if stackTopOp.hasOpenBracket() || stackTopOp.isComma() || precedence(stackTopOp, op) < 0 { + break + } + e.applyOp() + } + e.stackOp.push(op) + } + } + for len(e.stackOp.elems) > 0 && !e.stackOp.peek().isComma() { + e.applyOp() + } + if len(e.stackNum.elems) != 1 { + return Num{}, ExprError{fmt.Sprintf("expect 1 value as final result, but there are %d", len(e.stackNum.elems)), tokens, nil} + } + return e.stackNum.pop(), nil +} + +func precedence(op1, op2 operator) int { + p1 := opPrecedence[string(op1)] + p2 := opPrecedence[string(op2)] + if p1 == 0 { + panic("unknown operator precedence: " + string(op1)) + } else if p2 == 0 { + panic("unknown operator precedence: " + string(op2)) + } + return p1 - p2 +} + +func castFloat64(nums []Num) bool { + hasFloat := false + for _, num := range nums { + if _, hasFloat = num.Value.(float64); hasFloat { + break + } + } + if hasFloat { + for i, num := range nums { + if _, ok := num.Value.(float64); !ok { + f, _ := util.ToFloat64(num.Value) + nums[i] = Num{f} + } + } + } + return hasFloat +} + +func fnSum(nums []Num) Num { + if castFloat64(nums) { + var sum float64 + for _, num := range nums { + sum += num.Value.(float64) + } + return Num{sum} + } + var sum int64 + for _, num := range nums { + sum += num.Value.(int64) + } + return Num{sum} +} + +// Expr evaluates the given expression tokens and returns the result. +// It supports the following operators: +, -, *, /, and, or, not, ==, !=, >, >=, <, <=. +// Non-zero values are treated as true, zero values are treated as false. +// If no error occurs, the result is either an int64 or a float64. +// If all numbers are integer, the result is an int64, otherwise if there is any float number, the result is a float64. +func Expr(tokens ...any) (Num, error) { + e := newEval() + e.funcMap = map[string]func([]Num) Num{"sum": fnSum} + return e.exec(tokens...) +} -- cgit v1.2.3