Repository: google/starlark-go (go)

Issue:
panic from built-in function leaves Thread in a bad state
This is the test code:
https://go.dev/play/p/SZFzWgchzeZ
```golang
package main

import (
	"fmt"
	"log"

	"go.starlark.net/starlark"
)

func check(err error) {
	if err != nil {
		log.Fatal(err)
	}
}

func main() {
	t := &starlark.Thread{}
	sd := starlark.StringDict{
		"test": starlark.NewBuiltin("test", func(*starlark.Thread, *starlark.Builtin, starlark.Tuple, []starlark.Tuple) (starlark.Value, error) {
			panic("panic")
			// println("123")
			return starlark.None, nil
		}),
	}
	g, err := starlark.ExecFile(t, "", `
def mytest():
	test()
`, sd)
	check(err)
	g.Freeze()
	v := g["mytest"]

	calltest := func() {
		defer func() {
			if e := recover(); e != nil {
				fmt.Println("get panic", e)
			}
		}()
		_, err = starlark.Call(t, v, make(starlark.Tuple, 0), nil)
		if err != nil {
			println("get err:", err.Error())
		}
	}

	calltest()
	calltest()

}

```

The output I am expecting is:
```
get panic panic
get panic panic
```

But the output I get is：
```
get panic panic
get err: function mytest called recursively
```


When starlark is aborted by Builtin panic, calling starlark.Call again will get an error. I would like a way to have starlark revert to a usable state without renew a Thread

Pull request description:
starlark: use defer for cleanup so that panics pass through safely
This change uses defer for the cleanup logic in in Call and
Function.CallInternal so that panics originating in application
functions called by the interpreter can safely pass through
the interpreter without leaving the thread in a bad state
(e.g. frames still on the stack).

This seems to have an impact of ~0.7% on the 'calling' benchmark,
which represents the worst possible case.

Also, a test.

Fixes #419

Patch:
diff --git a/cmd/starlark/starlark.go b/cmd/starlark/starlark.go
index cf1bb99..8076deb 100644
--- a/cmd/starlark/starlark.go
+++ b/cmd/starlark/starlark.go
@@ -22,6 +22,7 @@ import (
 	"go.starlark.net/repl"
 	"go.starlark.net/resolve"
 	"go.starlark.net/starlark"
+	"golang.org/x/term"
 )
 
 // flags
@@ -120,9 +121,15 @@ func doMain() int {
 			return 1
 		}
 	case flag.NArg() == 0:
-		fmt.Println("Welcome to Starlark (go.starlark.net)")
+		stdinIsTerminal := term.IsTerminal(int(os.Stdin.Fd()))
+		if stdinIsTerminal {
+			fmt.Println("Welcome to Starlark (go.starlark.net)")
+		}
 		thread.Name = "REPL"
 		repl.REPL(thread, globals)
+		if stdinIsTerminal {
+			fmt.Println()
+		}
 	default:
 		log.Print("want at most one Starlark file name")
 		return 1
diff --git a/doc/spec.md b/doc/spec.md
index 90afccc..1e9d05a 100644
--- a/doc/spec.md
+++ b/doc/spec.md
@@ -104,7 +104,7 @@ reproducibility is paramount, such as build tools.
     * [For loops](#for-loops)
     * [Break and Continue](#break-and-continue)
     * [Load statements](#load-statements)
-    * [Module execution](#module-execution)
+  * [Module execution](#module-execution)
   * [Built-in constants and functions](#built-in-constants-and-functions)
     * [None](#none)
     * [True and False](#true-and-false)
@@ -741,11 +741,9 @@ The concatenation operation `x + y` yields a new list containing all
 the elements of the two lists x and y.
 
 For most types, `x += y` is equivalent to `x = x + y`, except that it
-evaluates `x` only once, that is, it allocates a new list to hold
-the concatenation of `x` and `y`.
-However, if `x` refers to a list, the statement does not allocate a
-new list but instead mutates the original list in place, similar to
-`x.extend(y)`.
+evaluates `x` only once. However, if `x` refers to a list, the statement
+`x += y` does not allocate a new list as `x = x + y` would, but instead 
+mutates the original list in place, similar to `x.extend(y)`.
 
 Lists are not hashable, so may not be used in the keys of a dictionary.
 
@@ -1192,8 +1190,8 @@ The [type](#type) of a built-in function is `"builtin_function_or_method"`.
 
 A built-in function value used in a Boolean context is always considered true.
 
-Many built-in functions are predeclared in the environment
-(see [Name Resolution](#name-resolution)).
+Many [built-in functions](#built-in-constants-and-functions) are predeclared 
+in the environment (see [Name binding and variables](#name-binding-and-variables)).
 Some built-in functions such as `len` are _universal_, that is,
 available to all Starlark programs.
 The host application may predeclare additional built-in functions
@@ -2522,7 +2520,7 @@ Example:
 def map(f, list):
     return [f(x) for x in list]
 
-map(lambda x: 2*x, range(3))    # [2, 4, 6]
+map(lambda x: 2*x, range(3))    # [0, 2, 4]
 ```
 
 As with functions created by a `def` statement, a lambda function
@@ -3462,7 +3460,7 @@ type(0.0)               # "float"
 `zip()` returns a new list of n-tuples formed from corresponding
 elements of each of the n iterable sequences provided as arguments to
 `zip`.  That is, the first tuple contains the first element of each of
-the sequences, the second element contains the second element of each
+the sequences, the second tuple contains the second element of each
 of the sequences, and so on.  The result list is only as long as the
 shortest of the input sequences.
 
@@ -3903,7 +3901,7 @@ Currently it must be empty, but it is reserved for future use.
 "a{x}b{y}c{}".format(1, x=2, y=3)               # "a2b3c1"
 "a{}b{}c".format(1, 2)                          # "a1b2c"
 "({1}, {0})".format("zero", "one")              # "(one, zero)"
-"Is {0!r} {0!s}?".format('heterological')       # 'is "heterological" heterological?'
+"Is {0!r} {0!s}?".format('heterological')       # 'Is "heterological" heterological?'
 ```
 
 <a id='string·index'></a>
diff --git a/go.mod b/go.mod
index ae5f371..99a5585 100644
--- a/go.mod
+++ b/go.mod
@@ -7,7 +7,8 @@ require (
 	github.com/chzyer/readline v0.0.0-20180603132655-2972be24d48e
 	github.com/chzyer/test v0.0.0-20180213035817-a1ea475d72b1 // indirect
 	github.com/google/go-cmp v0.5.1 // indirect
-	golang.org/x/sys v0.0.0-20220811171246-fbc7d0a398ab
+	golang.org/x/sys v0.0.0-20220715151400-c0bba94af5f8
+	golang.org/x/term v0.0.0-20220526004731-065cf7ba2467
 	golang.org/x/xerrors v0.0.0-20200804184101-5ec99f83aff1 // indirect
 	google.golang.org/protobuf v1.25.0
 )
diff --git a/go.sum b/go.sum
index 62e9fda..426962b 100644
--- a/go.sum
+++ b/go.sum
@@ -43,8 +43,11 @@ golang.org/x/sync v0.0.0-20181108010431-42b317875d0f/go.mod h1:RxMgew5VJxzue5/jJ
 golang.org/x/sync v0.0.0-20190423024810-112230192c58/go.mod h1:RxMgew5VJxzue5/jJTE5uejpjVlOe/izrB70Jof72aM=
 golang.org/x/sys v0.0.0-20180830151530-49385e6e1522/go.mod h1:STP8DvDyc/dI5b8T5hshtkjS+E42TnysNCUPdjciGhY=
 golang.org/x/sys v0.0.0-20190215142949-d0b11bdaac8a/go.mod h1:STP8DvDyc/dI5b8T5hshtkjS+E42TnysNCUPdjciGhY=
-golang.org/x/sys v0.0.0-20220811171246-fbc7d0a398ab h1:2QkjZIsXupsJbJIdSjjUOgWK3aEtzyuh2mPt3l/CkeU=
-golang.org/x/sys v0.0.0-20220811171246-fbc7d0a398ab/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
+golang.org/x/sys v0.0.0-20210615035016-665e8c7367d1/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
+golang.org/x/sys v0.0.0-20220715151400-c0bba94af5f8 h1:0A+M6Uqn+Eje4kHMK80dtF3JCXC4ykBgQG4Fe06QRhQ=
+golang.org/x/sys v0.0.0-20220715151400-c0bba94af5f8/go.mod h1:oPkhp1MJrh7nUepCBck5+mAzfO9JrbApNNgaTdGDITg=
+golang.org/x/term v0.0.0-20220526004731-065cf7ba2467 h1:CBpWXWQpIRjzmkkA+M7q9Fqnwd2mZr3AFqexg8YTfoM=
+golang.org/x/term v0.0.0-20220526004731-065cf7ba2467/go.mod h1:jbD1KX2456YbFQfuXm/mYQcufACuNUgVhRMnK/tPxf8=
 golang.org/x/text v0.3.0/go.mod h1:NqM8EUOU14njkJ3fqMW+pc6Ldnwhi/IjpwHt7yyuwOQ=
 golang.org/x/tools v0.0.0-20190114222345-bf090417da8b/go.mod h1:n7NCudcB/nEzxVGmLbDWY5pfWTLqBcC2KZ6jyYvM4mQ=
 golang.org/x/tools v0.0.0-20190226205152-f727befe758c/go.mod h1:9Yl7xja0Znq3iFh3HoIrodX9oNMXvdceNzlUR8zjMvY=
diff --git a/lib/json/json.go b/lib/json/json.go
index e893a97..80b6f70 100644
--- a/lib/json/json.go
+++ b/lib/json/json.go
@@ -14,10 +14,12 @@ import (
 	"log"
 	"math"
 	"math/big"
+	"reflect"
 	"sort"
 	"strconv"
 	"strings"
 	"unicode/utf8"
+	"unsafe"
 
 	"go.starlark.net/starlark"
 	"go.starlark.net/starlarkstruct"
@@ -100,8 +102,23 @@ func encode(thread *starlark.Thread, b *starlark.Builtin, args starlark.Tuple, k
 		}
 	}
 
+	path := make([]unsafe.Pointer, 0, 8)
+
 	var emit func(x starlark.Value) error
 	emit = func(x starlark.Value) error {
+
+		// It is only necessary to push/pop the item when it might contain
+		// itself (i.e. the last three switch cases), but omitting it in the other
+		// cases did not show significant improvement on the benchmarks.
+		if ptr := pointer(x); ptr != nil {
+			if pathContains(path, ptr) {
+				return fmt.Errorf("cycle in json structure")
+			}
+
+			path = append(path, ptr)
+			defer func() { path = path[0 : len(path)-1] }()
+		}
+
 		switch x := x.(type) {
 		case json.Marshaler:
 			// Application-defined starlark.Value types
@@ -209,6 +226,26 @@ func encode(thread *starlark.Thread, b *starlark.Builtin, args starlark.Tuple, k
 	return starlark.String(buf.String()), nil
 }
 
+func pointer(i interface{}) unsafe.Pointer {
+	v := reflect.ValueOf(i)
+	switch v.Kind() {
+	case reflect.Ptr, reflect.Chan, reflect.Map, reflect.UnsafePointer, reflect.Slice:
+		return v.UnsafePointer()
+	default:
+		return nil
+	}
+}
+
+func pathContains(path []unsafe.Pointer, item unsafe.Pointer) bool {
+	for _, p := range path {
+		if p == item {
+			return true
+		}
+	}
+
+	return false
+}
+
 // isPrintableASCII reports whether s contains only printable ASCII.
 func isPrintableASCII(s string) bool {
 	for i := 0; i < len(s); i++ {
diff --git a/repl/repl.go b/repl/repl.go
index 97109c6..94f8947 100644
--- a/repl/repl.go
+++ b/repl/repl.go
@@ -53,7 +53,6 @@ func REPL(thread *starlark.Thread, globals starlark.StringDict) {
 			break
 		}
 	}
-	fmt.Println()
 }
 
 // rep reads, evaluates, and prints one item.
diff --git a/starlark/eval.go b/starlark/eval.go
index 4941d44..23614eb 100644
--- a/starlark/eval.go
+++ b/starlark/eval.go
@@ -51,8 +51,13 @@ type Thread struct {
 	// The default behavior is to call thread.Cancel("too many steps").
 	OnMaxSteps func(thread *Thread)
 
-	// steps counts abstract computation steps executed by this thread.
-	steps, maxSteps uint64
+	// Steps a count of abstract computation steps executed
+	// by this thread. It is incremented by the interpreter. It may be used
+	// as a measure of the approximate cost of Starlark execution, by
+	// computing the difference in its value before and after a computation.
+	//
+	// The precise meaning of "step" is not specified and may change.
+	Steps, maxSteps uint64
 
 	// cancelReason records the reason from the first call to Cancel.
 	cancelReason *string
@@ -65,14 +70,9 @@ type Thread struct {
 	proftime time.Duration
 }
 
-// ExecutionSteps returns a count of abstract computation steps executed
-// by this thread. It is incremented by the interpreter. It may be used
-// as a measure of the approximate cost of Starlark execution, by
-// computing the difference in its value before and after a computation.
-//
-// The precise meaning of "step" is not specified and may change.
+// ExecutionSteps returns the current value of Steps.
 func (thread *Thread) ExecutionSteps() uint64 {
-	return thread.steps
+	return thread.Steps
 }
 
 // SetMaxExecutionSteps sets a limit on the number of Starlark
@@ -84,12 +84,20 @@ func (thread *Thread) SetMaxExecutionSteps(max uint64) {
 	thread.maxSteps = max
 }
 
+// Uncancel resets the cancellation state.
+//
+// Unlike most methods of Thread, it is safe to call Uncancel from any
+// goroutine, even if the thread is actively executing.
+func (thread *Thread) Uncancel() {
+	atomic.StorePointer((*unsafe.Pointer)(unsafe.Pointer(&thread.cancelReason)), nil)
+}
+
 // Cancel causes execution of Starlark code in the specified thread to
 // promptly fail with an EvalError that includes the specified reason.
 // There may be a delay before the interpreter observes the cancellation
 // if the thread is currently in a call to a built-in function.
 //
-// Cancellation cannot be undone.
+// Call [Uncancel] to reset the cancellation state.
 //
 // Unlike most methods of Thread, it is safe to call Cancel from any
 // goroutine, even if the thread is actively executing.
@@ -1225,8 +1233,22 @@ func Call(thread *Thread, fn Value, args Tuple, kwargs []Tuple) (Value, error) {
 	fr.callable = c
 
 	thread.beginProfSpan()
+
+	// Use defer to ensure that panics from built-ins
+	// pass through the interpreter without leaving
+	// it in a bad state.
+	defer func() {
+		thread.endProfSpan()
+
+		// clear out any references
+		// TODO(adonovan): opt: zero fr.Locals and
+		// reuse it if it is large enough.
+		*fr = frame{}
+
+		thread.stack = thread.stack[:len(thread.stack)-1] // pop
+	}()
+
 	result, err := c.CallInternal(thread, args, kwargs)
-	thread.endProfSpan()
 
 	// Sanity check: nil is not a valid Starlark value.
 	if result == nil && err == nil {
@@ -1240,9 +1262,6 @@ func Call(thread *Thread, fn Value, args Tuple, kwargs []Tuple) (Value, error) {
 		}
 	}
 
-	*fr = frame{}                                     // clear out any references
-	thread.stack = thread.stack[:len(thread.stack)-1] // pop
-
 	return result, err
 }
 
diff --git a/starlark/hashtable.go b/starlark/hashtable.go
index 9fab60e..fed7c3a 100644
--- a/starlark/hashtable.go
+++ b/starlark/hashtable.go
@@ -372,6 +372,8 @@ func (it *keyIterator) Done() {
 	}
 }
 
+// TODO(adonovan): use go1.19's maphash.String.
+
 // hashString computes the hash of s.
 func hashString(s string) uint32 {
 	if len(s) >= 12 {
diff --git a/starlark/interp.go b/starlark/interp.go
index 9961e2f..b41905a 100644
--- a/starlark/interp.go
+++ b/starlark/interp.go
@@ -81,14 +81,25 @@ func (fn *Function) CallInternal(thread *Thread, args Tuple, kwargs []Tuple) (Va
 
 	var iterstack []Iterator // stack of active iterators
 
+	// Use defer so that application panics can pass through
+	// interpreter without leaving thread in a bad state.
+	defer func() {
+		// ITERPOP the rest of the iterator stack.
+		for _, iter := range iterstack {
+			iter.Done()
+		}
+
+		fr.locals = nil
+	}()
+
 	sp := 0
 	var pc uint32
 	var result Value
 	code := f.Code
 loop:
 	for {
-		thread.steps++
-		if thread.steps >= thread.maxSteps {
+		thread.Steps++
+		if thread.Steps >= thread.maxSteps {
 			if thread.OnMaxSteps != nil {
 				thread.OnMaxSteps(thread)
 			} else {
@@ -646,14 +657,7 @@ loop:
 			break loop
 		}
 	}
-
-	// ITERPOP the rest of the iterator stack.
-	for _, iter := range iterstack {
-		iter.Done()
-	}
-
-	fr.locals = nil
-
+	// (deferred cleanup runs here)
 	return result, err
 }
 


Test patch:
diff --git a/internal/test.sh b/internal/test.sh
index b35ae73..cfca0df 100755
--- a/internal/test.sh
+++ b/internal/test.sh
@@ -6,13 +6,13 @@
 
 set -eu
 
-# Confirm that go.mod and go.sum are tidy
+# Confirm that go.mod and go.sum are tidy.
 cp go.mod go.mod.orig
 cp go.sum go.sum.orig
 go mod tidy
 # Use -w to ignore differences in OS newlines.
-diff -w  go.mod.orig go.mod
-diff -w go.sum.orig go.sum
+diff -w go.mod.orig go.mod || { echo "go.mod is not tidy"; exit 1; }
+diff -w go.sum.orig go.sum || { echo "go.sum is not tidy"; exit 1; }
 rm go.mod.orig go.sum.orig
 
 # Run tests
diff --git a/starlark/bench_test.go b/starlark/bench_test.go
index e62cf59..e860df7 100644
--- a/starlark/bench_test.go
+++ b/starlark/bench_test.go
@@ -12,6 +12,7 @@ import (
 	"strings"
 	"testing"
 
+	"go.starlark.net/lib/json"
 	"go.starlark.net/starlark"
 	"go.starlark.net/starlarktest"
 )
@@ -19,6 +20,8 @@ import (
 func BenchmarkStarlark(b *testing.B) {
 	defer setOptions("")
 
+	starlark.Universe["json"] = json.Module
+
 	testdata := starlarktest.DataFile("starlark", ".")
 	thread := new(starlark.Thread)
 	for _, file := range []string{
diff --git a/starlark/eval_test.go b/starlark/eval_test.go
index 5974579..5378615 100644
--- a/starlark/eval_test.go
+++ b/starlark/eval_test.go
@@ -972,6 +972,13 @@ func TestExecutionSteps(t *testing.T) {
 	if fmt.Sprint(err) != "Starlark computation cancelled: too many steps" {
 		t.Errorf("execution returned error %q, want cancellation", err)
 	}
+
+	thread.Steps = 0
+	thread.Uncancel()
+	_, err = countSteps(1)
+	if err != nil {
+		t.Errorf("execution returned error %q, want nil", err)
+	}
 }
 
 // TestDeps fails if the interpreter proper (not the REPL, etc) sprouts new external dependencies.
@@ -995,3 +1002,52 @@ func TestDeps(t *testing.T) {
 		}
 	}
 }
+
+// TestPanicSafety ensures that a panic from an application-defined
+// built-in may traverse the interpreter safely; see issue #411.
+func TestPanicSafety(t *testing.T) {
+	predeclared := starlark.StringDict{
+		"panic": starlark.NewBuiltin("panic", func(thread *starlark.Thread, b *starlark.Builtin, args starlark.Tuple, kwargs []starlark.Tuple) (starlark.Value, error) {
+			panic(args[0])
+		}),
+		"list": starlark.NewList([]starlark.Value{starlark.MakeInt(0)}),
+	}
+
+	// This program is executed twice, using the same Thread,
+	// and panics both times, with values 1 and 2, while
+	// main is on the stack and a for-loop is active.
+	//
+	// It mutates list, a predeclared variable.
+	// This operation would fail if the previous
+	// for-loop failed to close its iterator during the panic.
+	//
+	// It also calls main a second time without recursion enabled.
+	// This operation would fail if the previous
+	// call failed to pop main from the stack during the panic.
+	const src = `
+list[0] += 1
+
+def main():
+    for x in list:
+        panic(x)
+
+main()
+`
+	thread := new(starlark.Thread)
+	for _, i := range []int{1, 2} {
+		// Use a func to limit the scope of recover.
+		func() {
+			defer func() {
+				if got := fmt.Sprint(recover()); got != fmt.Sprint(i) {
+					t.Fatalf("recover: got %v, want %v", got, i)
+				}
+			}()
+			v, err := starlark.ExecFile(thread, "panic.star", src, predeclared)
+			if err != nil {
+				t.Fatalf("ExecFile returned error %q, expected panic", err)
+			} else {
+				t.Fatalf("ExecFile returned %v, expected panic", v)
+			}
+		}()
+	}
+}
diff --git a/starlark/testdata/benchmark.star b/starlark/testdata/benchmark.star
index 79614f0..b87e5ad 100644
--- a/starlark/testdata/benchmark.star
+++ b/starlark/testdata/benchmark.star
@@ -68,3 +68,52 @@ def bench_dict_equal(b):
     for _ in range(b.n):
         if largedict != largedict:
             fail("invalid comparison")
+
+flat = { "int": 1, "float": 0.2, "string": "string", "list": [], "bool": True, "nil": None, "tuple": (1, 2, 3) }
+deep = {
+    "type": "int",
+    "value": 1, 
+    "next": {
+        "type": "float",
+        "value": 0.2,
+        "next": {
+            "type": "string", 
+            "value": "string",
+            "next": {
+                "type": "list", 
+                "value": [ 1, "", True, None, (1, 2) ],
+                "next": {
+                    "type": "bool",
+                    "value": True,
+                    "next": {
+                        "type": "tuple",
+                        "value": (1, 2.0, "3"),
+                        "next": None
+                    }
+                }
+            }
+        }
+    }
+}
+
+deep_list = [ deep for _ in range(100) ]
+
+def bench_to_json_flat_mixed(b):
+    "Benchmark json.encode builtin with flat mixed input"
+    for _ in range(b.n):
+        json.encode(flat)
+
+def bench_to_json_flat_big(b):
+    "Benchmark json.encode builtin with big flat integer input"
+    for _ in range(b.n):
+        json.encode(largedict)
+
+def bench_to_json_deep(b):
+    "Benchmark json.encode builtin with deep input"
+    for _ in range(b.n):
+        json.encode(deep)
+
+def bench_to_json_deep_list(b):
+    "Benchmark json.encode builtin with a list of deep input"
+    for _ in range(b.n):
+        json.encode(deep)
diff --git a/starlark/testdata/json.star b/starlark/testdata/json.star
index 7c7b316..9e222db 100644
--- a/starlark/testdata/json.star
+++ b/starlark/testdata/json.star
@@ -37,6 +37,18 @@ encode_error(struct(x=[1, {"x": len}]), # nested failure
              'in field .x: at list index 1: in dict key "x": cannot encode...')
 encode_error({1: 2}, 'dict has int key, want string')
 
+recursive_map = {}
+recursive_map["r"] = recursive_map
+encode_error(recursive_map, 'json.encode: in dict key "r": Detected cycle in json structure')
+
+recursive_list = []
+recursive_list.append(recursive_list)
+encode_error(recursive_list, 'json.encode: at list index 0: Detected cycle in json structure')
+
+recursive_tuple = (1, 2, [])
+recursive_tuple[2].append(recursive_tuple)
+encode_error(recursive_tuple, 'json.encode: at tuple index 2: at list index 0: Detected cycle in json structure')
+
 ## json.decode
 
 assert.eq(json.decode("null"), None)