Repository: google/starlark-go

Issue:
Able to crash Starlark with deep recursion
If I have "resolve.AllowRecursion = true", and run the following, Starlark crashes:

dump(recur(0))

def recur(x):
    if x <= 1000000:
        return recur(x+1)
    return x

where dump is my function that dumps its parameters to the caller's web browser. The stack trace is very large, and includes lots of goroutines. The part that looks important to me is attached.

[crash1.txt](https://github.com/user-attachments/files/23158956/crash1.txt)

Discussion:
@alistair-cunningham: Thank you for adding the stack check.

I think there's still a problem in that the documentation says there is a recursion depth limit of 10,000, but this doesn't seem to be enforced. If I change "if x <= 1000000:" to "if x <= 100000:", it runs all 100,000 levels of recursion. I'm not sure if this is a code problem or a documentation problem.@adonovan: > Thank you for adding the stack check.
> 
> I think there's still a problem in that the documentation says there is a recursion depth limit of 10,000, but this doesn't seem to be enforced. If I change "if x <= 1000000:" to "if x <= 100000:", it runs all 100,000 levels of recursion. I'm not sure if this is a code problem or a documentation problem.

The new check is dynamic, not static, and it neither the implementation nor the docs (nor even the test) advertise any particular limit; it's just a local constant in the implementation.

It seems reasonable to both have a limit, and also not to promise what that limit is, other than "enough in most cases".@alistair-cunningham: Ah, I see. Thank you.

Solution patch:
diff --git a/starlark/interp.go b/starlark/interp.go
index 261077f..a0af4cb 100644
--- a/starlark/interp.go
+++ b/starlark/interp.go
@@ -24,7 +24,17 @@ func (fn *Function) CallInternal(thread *Thread, args Tuple, kwargs []Tuple) (Va
 	// but allows CALL to avoid a copy.
 
 	f := fn.funcode
-	if !f.Prog.Recursion {
+	if f.Prog.Recursion {
+		// prevent stack overflow
+		//
+		// Each CallInternal recursion (via Call) uses ~1.4KB,
+		// but the stack limit is on the order of 1GB, so a
+		// maximum of about 700K recursive calls is possible.
+		// Limit it to much less here.
+		if len(thread.stack) > 100_000 {
+			return nil, fmt.Errorf("Starlark stack overflow")
+		}
+	} else {
 		// detect recursion
 		for _, fr := range thread.stack[:len(thread.stack)-1] {
 			// We look for the same function code,



Test patch:
diff --git a/starlark/testdata/recursion.star b/starlark/testdata/recursion.star
index 7029ea0..ebaabc5 100644
--- a/starlark/testdata/recursion.star
+++ b/starlark/testdata/recursion.star
@@ -12,3 +12,10 @@ def fib(n):
 	return fib(n-1) + fib(n-2)
 
 assert.eq(fib(5), 8)
+
+def runaway():
+	return runaway()
+
+# Runaway recursion should not overflow the Go stack (#617).
+# The interpreter imposes a limit long before then.
+assert.fails(runaway, "Starlark stack overflow")
\ No newline at end of file