Infinite loop in ResidualAst

[betawaffle]

Describe the bug
It's possible to get an infinite loop when calling ResidualAst with certain inputs.

To Reproduce
Check which components this affects:

• parser
• checker
• interpreter

Sample expression and input that reproduces the issue:

some_map_variable

Test setup:

func TestResidualAstHang(t *testing.T) {
	opt := cel.Declarations(
		decls.NewVar("msg", decls.NewMapType(decls.String, decls.String)),
	)

	env, err := cel.NewEnv(opt)
	if err != nil {
		t.Fatal(err)
	}

	ast, iss := env.Compile("msg")
	if len(iss.Errors()) > 0 {
		t.Fatal(iss.String())
	}

	prg, err := env.Program(
		ast,
		cel.EvalOptions(cel.OptTrackState),
	)
	if err != nil {
		t.Fatal(err)
	}

	val, details, err := prg.Eval(map[string]interface{}{
		"msg": map[string]string{"foo": "bar"}, // must be a map
	})
	if val == nil {
		t.Fatal(err)
	}
	if err != nil {
		t.Fatal(err)
	}

	t.Logf("calling ResidualAst")

	// This is where the problem happens.
	_, err = env.ResidualAst(ast, details)
	if err != nil {
		t.Fatal(err)
	}

	// unreachable, inifinite loop in interpreter.(*astPruner).nextID
	t.Logf("ResidualAst returned")
}

Expected behavior
The call to ResidualAst should return in a resonable time.

Additional context
I got this with cel-go version 0.7.2, Go version 1.16 on darwin/amd64, and haven't tried with any other versions.

Here's a stack trace, obtained via SIGQUIT of the above test after a few seconds:

goroutine 18 [running]:
runtime.mapaccess2_fast64(0x13dfb80, 0xc000297f80, 0x10563306, 0x17c90c0, 0xc0001f5a00)
	<GOROOT>/src/runtime/map_fast64.go:57 +0x33 fp=0xc0001f59c8 sp=0xc0001f59a0 pc=0x1012913
github.com/google/cel-go/interpreter.(*evalState).Value(0xc00027b488, 0x10563306, 0x0, 0x0, 0x1466d00)
	<GOPATH>/pkg/mod/github.com/google/[email protected]/interpreter/evalstate.go:63 +0x45 fp=0xc0001f5a00 sp=0xc0001f59c8 pc=0x1374185
github.com/google/cel-go/interpreter.(*astPruner).nextID(0xc0001f5e00, 0x1)
	<GOPATH>/pkg/mod/github.com/google/[email protected]/interpreter/prune.go:384 +0x48 fp=0xc0001f5a38 sp=0xc0001f5a00 pc=0x13832a8
github.com/google/cel-go/interpreter.(*astPruner).maybeCreateLiteral(0xc0001f5e00, 0x1, 0x14dfe18, 0xc000295a40, 0x1, 0x0)
	<GOPATH>/pkg/mod/github.com/google/[email protected]/interpreter/prune.go:146 +0x75f fp=0xc0001f5bc8 sp=0xc0001f5a38 pc=0x138083f
github.com/google/cel-go/interpreter.(*astPruner).prune(0xc0001f5e00, 0xc0001d2bc0, 0xc0001f5d58, 0x10fd8f7)
	<GOPATH>/pkg/mod/github.com/google/[email protected]/interpreter/prune.go:227 +0x12dc fp=0xc0001f5db0 sp=0xc0001f5bc8 pc=0x1382fdc
github.com/google/cel-go/interpreter.PruneAst(...)
	<GOPATH>/pkg/mod/github.com/google/[email protected]/interpreter/prune.go:68
github.com/google/cel-go/cel.(*Env).ResidualAst(0xc0000da460, 0xc000297e60, 0xc00029a0c0, 0x0, 0x0, 0x0)
	<GOPATH>/pkg/mod/github.com/google/[email protected]/cel/env.go:386 +0x85 fp=0xc0001f5e98 sp=0xc0001f5db0 pc=0x1389165
anywhere.TestResidualAst(0xc000190180)
	<ANYWHERE>/cel_test.go:46 +0x645 fp=0xc0001f5f80 sp=0xc0001f5e98 pc=0x138d805
testing.tRunner(0xc000190180, 0x1477220)
	<GOROOT>/src/testing/testing.go:1194 +0xef fp=0xc0001f5fd0 sp=0xc0001f5f80 pc=0x10ff74f
runtime.goexit()
	<GOROOT>/src/runtime/asm_amd64.s:1371 +0x1 fp=0xc0001f5fd8 sp=0xc0001f5fd0 pc=0x106e781
created by testing.(*T).Run
	<GOROOT>/src/testing/testing.go:1239 +0x2b3

I did this a few times to confirm that 0x10563306 indicates the value of p.nextExprID passed to Value. Clearly the break condition of that loop in nextID is never happening.

[TristonianJones]

Thanks for the report! I'll look at this tomorrow