Type-checking time grows quadratically with expression length: checker copies its substitution mapping per assignability check #1553

Describe the bug

Type-checking time and memory grow quadratically with the length of an expression that uses macros or parameterized overloads. A conjunction of 400 short terms takes about 1.1s and allocates 841 MiB to check on an Apple M1.

The checker keeps one type substitution mapping for the whole expression, and it only grows: each macro and each parameterized overload such as size(list(A)) adds type parameters to it. isAssignable and isAssignableList in checker/types.go copy the entire mapping before each attempt, so that a failed attempt can be discarded. Overload resolution makes many such attempts per call, so each copy costs time proportional to everything checked so far.

Counting calls to mapping.copy for the expression below (instrumentation in a local copy, not part of any change):

Each term adds 3 type parameters and causes 40 copies, and each copy holds on average half the final mapping, so the entries copied grow with the square of the number of terms.

To Reproduce

Check which components this affects:

• parser
• checker
• interpreter

Sample expression and input that reproduces the issue:

["a0"].map(s, s + "x").size() > 0 && ["a1"].map(s, s + "x").size() > 0 && ... && ["a399"].map(s, s + "x").size() > 0

Test setup:

// BenchmarkCheckLongConjunction checks a conjunction of n terms that each use
// a macro and a parameterized overload, so that every term adds type
// parameters to the checker's substitution mapping.
func BenchmarkCheckLongConjunction(b *testing.B) {
	for _, n := range []int{25, 50, 100, 200, 400} {
		terms := make([]string, n)
		for i := range terms {
			terms[i] = fmt.Sprintf(`["a%d"].map(s, s + "x").size() > 0`, i)
		}
		src := common.NewTextSource(strings.Join(terms, " && "))
		b.Run(fmt.Sprintf("terms=%d", n), func(b *testing.B) {
			p, err := parser.NewParser(parser.Macros(parser.AllMacros...))
			if err != nil {
				b.Fatalf("parser.NewParser() failed: %v", err)
			}
			pAst, errs := p.Parse(src)
			if len(errs.GetErrors()) > 0 {
				b.Fatalf("Parse() failed: %v", errs.ToDisplayString())
			}
			reg, err := types.NewRegistry()
			if err != nil {
				b.Fatalf("types.NewRegistry() failed: %v", err)
			}
			cont, err := containers.NewContainer()
			if err != nil {
				b.Fatalf("containers.NewContainer() failed: %v", err)
			}
			env, err := NewEnv(cont, reg, CrossTypeNumericComparisons(true))
			if err != nil {
				b.Fatalf("NewEnv() failed: %v", err)
			}
			env.AddFunctions(stdlib.Functions()...)
			b.ReportAllocs()
			b.ResetTimer()
			for i := 0; i < b.N; i++ {
				if _, errs := Check(pAst, src, env); len(errs.GetErrors()) > 0 {
					b.Fatalf("Check() failed: %v", errs.ToDisplayString())
				}
			}
		})
	}
}

On master (5dcc82d), Apple M1:

CheckLongConjunction/terms=25-8      3.73ms     3.6 MiB/op     17.8k allocs/op
CheckLongConjunction/terms=50-8     12.60ms    13.8 MiB/op     39.5k allocs/op
CheckLongConjunction/terms=100-8    47.62ms    53.6 MiB/op     87.2k allocs/op
CheckLongConjunction/terms=200-8   249.10ms   211.3 MiB/op    190.9k allocs/op
CheckLongConjunction/terms=400-8  1128.33ms   841.4 MiB/op    427.0k allocs/op

Memory per check grows about 4× each time the expression doubles.

Expected behavior

Checking time and memory grow linearly with the length of the expression.

Additional context

I found this through a language server that type-checks a CEL file on every edit, where files of a few hundred lines became noticeably slow. v0.32.0 behaves the same.

A fix I've tried locally: instead of copying the mapping, isAssignable and isAssignableList change it in place while mapping.add records each entry it replaces, and a failed attempt restores those entries in reverse order. Every caller reaches these functions through checker.isAssignable and checker.isAssignableList, which adopt the result on success, so changing the mapping in place leaves behavior unchanged. With it, on master:

Memory now grows about 2× per doubling. Across the 139 cases of the existing BenchmarkCheck, alternating old and new binaries over 8 runs, time is unchanged (−1.5%), memory is down 3.7%, and allocations are down 6.5%. The checker and cel tests pass.

I'm happy to send this as a pull request with the benchmark and a test that a failed overload attempt leaves the mapping unchanged, if the approach sounds right.