Use a general Eval function for expressions in templates. (#23927)

One of the proposals in #23328

This PR introduces a simple expression calculator
(templates/eval/eval.go), it can do basic expression calculations.

Many untested template helper functions like `Mul` `Add` can be replaced
by this new approach.

Then these `Add` / `Mul` / `percentage` / `Subtract` / `DiffStatsWidth`
could all use this `Eval`.

And it provides enhancements for Golang templates, and improves
readability.

Some examples:

----

* Before: `{{Add (Mul $glyph.Row 12) 12}}`
* After: `{{Eval $glyph.Row "*" 12 "+" 12}}`

----

* Before: `{{if lt (Add $i 1) (len $.Topics)}}`
* After: `{{if Eval $i "+" 1 "<" (len $.Topics)}}`

## FAQ

### Why not use an existing expression package?

We need a highly customized expression engine:

* do the calculation on the fly, without pre-compiling
* deal with int/int64/float64 types, to make the result could be used in
Golang template.
* make the syntax could be used in the Golang template directly
* do not introduce too much complex or strange syntax, we just need a
simple calculator.
* it needs to strictly follow Golang template's behavior, for example,
Golang template treats all non-zero values as truth, but many 3rd
packages don't do so.

### What's the benefit?

* Developers don't need to add more `Add`/`Mul`/`Sub`-like functions,
they were getting more and more.
Now, only one `Eval` is enough for all cases.
* The new code reads better than old `{{Add (Mul $glyph.Row 12) 12}}`,
the old one isn't familiar to most procedural programming developers
(eg, the Golang expression syntax).
* The `Eval` is fully covered by tests, many old `Add`/`Mul`-like
functions were never tested.

### The performance?

It doesn't use `reflect`, it doesn't need to parse or compile when used
in Golang template, the performance is as fast as native Go template.

### Is it too complex? Could it be unstable?

The expression calculator program is a common homework for computer
science students, and it's widely used as a teaching and practicing
purpose for developers. The algorithm is pretty well-known.

The behavior can be clearly defined, it is stable.

3 files changed, 456 insertions, 39 deletions

diff --git a/modules/templates/eval/eval.go b/modules/templates/eval/eval.go
new file mode 100644
index 0000000000..5d4ac915b9
--- /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...)
+}
diff --git a/modules/templates/eval/eval_test.go b/modules/templates/eval/eval_test.go
new file mode 100644
index 0000000000..c9e514b5eb
--- /dev/null
+++ b/modules/templates/eval/eval_test.go
@@ -0,0 +1,94 @@
+// Copyright 2023 The Gitea Authors. All rights reserved.
+// SPDX-License-Identifier: MIT
+
+package eval
+
+import (
+	"math"
+	"strings"
+	"testing"
+
+	"github.com/stretchr/testify/assert"
+)
+
+func tokens(s string) (a []any) {
+	for _, v := range strings.Fields(s) {
+		a = append(a, v)
+	}
+	return a
+}
+
+func TestEval(t *testing.T) {
+	n, err := Expr(0, "/", 0.0)
+	assert.NoError(t, err)
+	assert.True(t, math.IsNaN(n.Value.(float64)))
+
+	_, err = Expr(nil)
+	assert.ErrorContains(t, err, "unsupported token type")
+	_, err = Expr([]string{})
+	assert.ErrorContains(t, err, "unsupported token type")
+	_, err = Expr(struct{}{})
+	assert.ErrorContains(t, err, "unsupported token type")
+
+	cases := []struct {
+		expr string
+		want any
+	}{
+		{"-1", int64(-1)},
+		{"1 + 2", int64(3)},
+		{"3 - 2 + 4", int64(5)},
+		{"1 + 2 * 3", int64(7)},
+		{"1 + ( 2 * 3 )", int64(7)},
+		{"( 1 + 2 ) * 3", int64(9)},
+		{"( 1 + 2.0 ) / 3", float64(1)},
+		{"sum( 1 , 2 , 3 , 4 )", int64(10)},
+		{"100 + sum( 1 , 2 + 3 , 0.0 ) / 2", float64(103)},
+		{"100 * 5 / ( 5 + 15 )", int64(25)},
+		{"9 == 5", int64(0)},
+		{"5 == 5", int64(1)},
+		{"9 != 5", int64(1)},
+		{"5 != 5", int64(0)},
+		{"9 > 5", int64(1)},
+		{"5 > 9", int64(0)},
+		{"5 >= 9", int64(0)},
+		{"9 >= 9", int64(1)},
+		{"9 < 5", int64(0)},
+		{"5 < 9", int64(1)},
+		{"9 <= 5", int64(0)},
+		{"5 <= 5", int64(1)},
+		{"1 and 2", int64(1)}, // Golang template definition: non-zero values are all truth
+		{"1 and 0", int64(0)},
+		{"0 and 0", int64(0)},
+		{"1 or 2", int64(1)},
+		{"1 or 0", int64(1)},
+		{"0 or 1", int64(1)},
+		{"0 or 0", int64(0)},
+		{"not 2 == 1", int64(1)},
+		{"not not ( 9 < 5 )", int64(0)},
+	}
+
+	for _, c := range cases {
+		n, err := Expr(tokens(c.expr)...)
+		if assert.NoError(t, err, "expr: %s", c.expr) {
+			assert.Equal(t, c.want, n.Value)
+		}
+	}
+
+	bads := []struct {
+		expr   string
+		errMsg string
+	}{
+		{"0 / 0", "integer divide by zero"},
+		{"1 +", "num stack is empty"},
+		{"+ 1", "num stack is empty"},
+		{"( 1", "incomplete sub-expression"},
+		{"1 )", "op stack is empty"}, // can not find the corresponding open bracket after the stack becomes empty
+		{"1 , 2", "expect 1 value as final result"},
+		{"( 1 , 2 )", "too many values in one bracket"},
+		{"1 a 2", "unknown operator"},
+	}
+	for _, c := range bads {
+		_, err = Expr(tokens(c.expr)...)
+		assert.ErrorContains(t, err, c.errMsg, "expr: %s", c.expr)
+	}
+}
diff --git a/modules/templates/helper.go b/modules/templates/helper.go
index 1686e54834..56be050481 100644
--- a/modules/templates/helper.go
+++ b/modules/templates/helper.go
@@ -42,6 +42,7 @@ import (
 	"code.gitea.io/gitea/modules/repository"
 	"code.gitea.io/gitea/modules/setting"
 	"code.gitea.io/gitea/modules/svg"
+	"code.gitea.io/gitea/modules/templates/eval"
 	"code.gitea.io/gitea/modules/timeutil"
 	"code.gitea.io/gitea/modules/util"
 	"code.gitea.io/gitea/services/gitdiff"
@@ -105,24 +106,9 @@ func NewFuncMap() []template.FuncMap {
 		"TimeSinceUnix": timeutil.TimeSinceUnix,
 		"FileSize":      base.FileSize,
 		"LocaleNumber":  LocaleNumber,
-		"Subtract":      base.Subtract,
 		"EntryIcon":     base.EntryIcon,
 		"MigrationIcon": MigrationIcon,
-		"Add": func(a ...int) int {
-			sum := 0
-			for _, val := range a {
-				sum += val
-			}
-			return sum
-		},
-		"Mul": func(a ...int) int {
-			sum := 1
-			for _, val := range a {
-				sum *= val
-			}
-			return sum
-		},
-		"ActionIcon": ActionIcon,
+		"ActionIcon":    ActionIcon,
 		"DateFmtLong": func(t time.Time) string {
 			return t.Format(time.RFC1123Z)
 		},
@@ -377,7 +363,7 @@ func NewFuncMap() []template.FuncMap {
 		"QueryEscape": url.QueryEscape,
 		"DotEscape":   DotEscape,
 		"Iterate": func(arg interface{}) (items []int64) {
-			count := util.ToInt64(arg)
+			count, _ := util.ToInt64(arg)
 			for i := int64(0); i < count; i++ {
 				items = append(items, i)
 			}
@@ -397,6 +383,7 @@ func NewFuncMap() []template.FuncMap {
 				curBranch,
 			)
 		},
+		"Eval": Eval,
 	}}
 }
 
@@ -472,28 +459,8 @@ func NewTextFuncMap() []texttmpl.FuncMap {
 			}
 			return dict, nil
 		},
-		"percentage": func(n int, values ...int) float32 {
-			sum := 0
-			for i := 0; i < len(values); i++ {
-				sum += values[i]
-			}
-			return float32(n) * 100 / float32(sum)
-		},
-		"Add": func(a ...int) int {
-			sum := 0
-			for _, val := range a {
-				sum += val
-			}
-			return sum
-		},
-		"Mul": func(a ...int) int {
-			sum := 1
-			for _, val := range a {
-				sum *= val
-			}
-			return sum
-		},
 		"QueryEscape": url.QueryEscape,
+		"Eval":        Eval,
 	}}
 }
 
@@ -944,6 +911,18 @@ func mirrorRemoteAddress(ctx context.Context, m *repo_model.Repository, remoteNa
 
 // LocaleNumber renders a number with a Custom Element, browser will render it with a locale number
 func LocaleNumber(v interface{}) template.HTML {
-	num := util.ToInt64(v)
+	num, _ := util.ToInt64(v)
 	return template.HTML(fmt.Sprintf(`<gitea-locale-number data-number="%d">%d</gitea-locale-number>`, num, num))
 }
+
+// Eval the expression and return the result, see the comment of eval.Expr for details.
+// To use this helper function in templates, pass each token as a separate parameter.
+//
+//	{{ $int64 := Eval $var "+" 1 }}
+//	{{ $float64 := Eval $var "+" 1.0 }}
+//
+// Golang's template supports comparable int types, so the int64 result can be used in later statements like {{if lt $int64 10}}
+func Eval(tokens ...any) (any, error) {
+	n, err := eval.Expr(tokens...)
+	return n.Value, err
+}