Checker infinit looping when using patcher/value and operator overloading

[rrb3942]

I'm adding support for "github.com/shopspring/decimal" to my project that makes use of "expr/patcher/value" and ran into an issue where cpu usage spikes to 100% and expr gets stuck compiling the expression when I try to introduce operator support.

trace.txt

From the trace it seems like it is getting stuck in the checker for some reason.

Here is an example program that can recreate the problem.

package main

import (
	"fmt"
	"log"

	"net/http"
	_ "net/http/pprof"

	"github.com/expr-lang/expr"
	"github.com/expr-lang/expr/patcher/value"
	"github.com/expr-lang/expr/vm"

	"github.com/shopspring/decimal"
)

type myInt struct {
	Int int
}

func (v *myInt) AsInt() int {
	return v.Int
}

func (v *myInt) AsAny() any {
	return v.Int
}

func toDecimal(val any) (decimal.Decimal, error) {
	switch v := val.(type) {
	case int:
		return decimal.NewFromInt(int64(v)), nil
	case int32:
		return decimal.NewFromInt32(v), nil
	case int64:
		return decimal.NewFromInt(v), nil
	case float32:
		return decimal.NewFromFloat32(v), nil
	case float64:
		return decimal.NewFromFloat(v), nil
	case string:
		d, err := decimal.NewFromString(v)

		if err != nil {
			return decimal.Decimal{}, err
		}

		return d, nil
	case decimal.Decimal:
		return v, nil
	default:
		return decimal.Decimal{}, fmt.Errorf("Unhandled type for rounding (type: %T)", v)
	}
}

func ExampleAnyValuer() {
	env := make(map[string]any)
	//using a plain int here also works fine
	//env["ValueOne"] = 1
	//But value types are broken
	env["ValueOne"] = &myInt{1}
	env["ValueTwo"] = &myInt{2}

	fmt.Println("Compiling")

	//this is fine
	//program, err := expr.Compile("decimal(1) * decimal(2)",

	//these are broken
	//program, err := expr.Compile("decimal(ValueOne) * decimal(ValueTwo)",
	program, err := expr.Compile("decimal(ValueOne) * decimal(2)",
		expr.Env(env),
		value.ValueGetter,
		expr.Function(
			"decimal",
			func(params ...any) (any, error) {
				return toDecimal(params[0])
			},
			new(func(int) decimal.Decimal),
			new(func(int32) decimal.Decimal),
			new(func(int64) decimal.Decimal),
			new(func(float32) decimal.Decimal),
			new(func(float64) decimal.Decimal),
			new(func(string) decimal.Decimal),
		),
		expr.Function(
			"_decimalMul",
			func(params ...any) (any, error) {
				return params[0].(decimal.Decimal).Mul(params[1].(decimal.Decimal)), nil
			},
			new(func(decimal.Decimal, decimal.Decimal) decimal.Decimal),
		),
		expr.Operator("*", "_decimalMul"),
	)

	if err != nil {
		panic(err)
	}

	fmt.Println("Running")
	out, err := vm.Run(program, env)

	if err != nil {
		panic(err)
	}

	fmt.Println(out)
}

func main() {

	go func() {
		log.Println(http.ListenAndServe("localhost:6060", nil))
	}()

	ExampleAnyValuer()
}

If there is any additional information that would help just let me know.

[antonmedv]

@rrb3942 could you try to debug the problem?

[rrb3942]

@antonmedv

Even though the trace showed all the cpu in the checker it is actually a problem in the patching phase.

Looks like there is some special logic around the operator overload patching that causes it to re-run all the patchers.

expr/expr.go

Lines 202 to 222 in e6dfb71

	if len(config.Visitors) > 0 {
	for i := 0; i < 1000; i++ {
	more := false
	for _, v := range config.Visitors {
	// We need to perform types check, because some visitors may rely on
	// types information available in the tree.
	_, _ = checker.Check(tree, config)
	ast.Walk(&tree.Node, v)
	if v, ok := v.(interface {
	ShouldRepeat() bool
	}); ok {
	more = more || v.ShouldRepeat()
	}
	}
	if !more {
	break
	}
	}
	}

So if the value patcher is passed first it will continually get re-run and, for some reason the operator patching will keep returning true for ShouldRepeat and continue looping . This results in an ever expanding tree as the value patcher gets applied over and over again.

&{_decimalMul(decimal($patcher_value_getter($patcher_value_getter($patcher_value_getter($patcher_value_getter($patcher_value_getter($patcher_value_getter($patcher_value_getter(ValueOne)))))))), decimal(2)) 0xc0000ab170}

Something I don't understand is why the operator patching continues to signal the ShouldRepeat(). My only guess is that OperatorOverloading.applied might need to get reset for every run?

Reordering the options so that the value patcher comes last fails instantly but the operator patching never seems to happen, most likely because of typing issues because the value isn't converted yet.

2024/05/06 12:49:16 &{decimal($patcher_value_getter(ValueOne)) * decimal(2) 0xc0000ab170}
panic: invalid operation: * (mismatched types decimal.Decimal and decimal.Decimal) (1:19)
 | decimal(ValueOne) * decimal(2)
 | ..................^

Removing the check for ShouldRepeat() allows the statement to compile and run.

[rrb3942]

@antonmedv I can try to write up a patch for this, just not sure on the approach to take. How do you feel about splitting any patcher that satisfies the ShouldRepeat interface into a separate patch phase that runs after the non-repeatable patchers?

[antonmedv]

I’m actually not understand this problem. Could you please explain what is happening?

[rrb3942]

@antonmedv Please see pull request #658 which fixes part of the problem.

The remaining issue is that an operator patcher applying causes all patchers to re-run, which makes the assumption that all patchers are idempotent. However in the case of this patcher it is not, as the node it patches is simply wrapped in a CallNode with the current node as an argument, so when the tree is walked and patched again it will trigger on the argument. Patchers that fully replace the node they are patching are not impacted.

Please note that this is a change in behavior for patchers introduced with 3da8527

My thought is too run two passes over patchers. The first pass runs any non-repeatable patchers without looping (old patcher behavior). The second pass would run repeatable (aka operators) only, repeating as necessary.

[antonmedv]

Fixed!