Repository: google/starlark-go (go)

Issue:
starlarkstruct Freeze() can cause a stack overflow if circular references are involved
If `starlarkstruct.Struct` is exposed to the starlark environment, and one creates a struct with a circular reference, and causes it to be frozen, then there will be a stack overflow.

A module with this Starlark content should reproduce the issue, but I haven't double-checked that it actually does:

```python
def make_struct():
    items = []
    foo = struct(items=items)
    foo.items.append(foo)
    return foo

toplevel = make_struct()
```

A fix for this issue could be done as follows:

```diff
--- a/starlarkstruct/struct.go
+++ b/starlarkstruct/struct.go
@@ -99,6 +99,7 @@ func FromStringDict(constructor starlark
 type Struct struct {
        constructor starlark.Value
        entries     entries // sorted by name
+       frozen      bool
 }
 
 // Default is the default constructor for structs.
@@ -172,8 +173,11 @@ func (s *Struct) Hash() (uint32, error) 
        return x, nil
 }
 func (s *Struct) Freeze() {
-       for _, e := range s.entries {
-               e.value.Freeze()
+       if !s.frozen {
+               s.frozen = true
+               for _, e := range s.entries {
+                       e.value.Freeze()
+               }
        }
 }
 ```

Pull request description:
Don't crash when freezing a struct with a circular reference
The Freeze method needs to check for a `frozen` condition just like all the other types of values, otherwise there can be infinite recursion.

The test that I'm adding here would crash without the fix.

* Fixes #566

Patch:
diff --git a/starlark/value.go b/starlark/value.go
index 5e323ca..53bb0e9 100644
--- a/starlark/value.go
+++ b/starlark/value.go
@@ -95,6 +95,11 @@ type Value interface {
 	// structure through this API will fail dynamically, making the
 	// data structure immutable and safe for publishing to other
 	// Starlark interpreters running concurrently.
+	//
+	// Implementations of Freeze must be defensive against
+	// reference cycles; this can be achieved by first checking
+	// the value's frozen state, then setting it, and only then
+	// visiting any other values that it references.
 	Freeze()
 
 	// Truth returns the truth value of an object.
diff --git a/starlarkstruct/struct.go b/starlarkstruct/struct.go
index 2282d7f..44612d2 100644
--- a/starlarkstruct/struct.go
+++ b/starlarkstruct/struct.go
@@ -99,6 +99,7 @@ func FromStringDict(constructor starlark.Value, d starlark.StringDict) *Struct {
 type Struct struct {
 	constructor starlark.Value
 	entries     entries // sorted by name
+	frozen      bool
 }
 
 // Default is the default constructor for structs.
@@ -172,8 +173,11 @@ func (s *Struct) Hash() (uint32, error) {
 	return x, nil
 }
 func (s *Struct) Freeze() {
-	for _, e := range s.entries {
-		e.value.Freeze()
+	if !s.frozen {
+		s.frozen = true
+		for _, e := range s.entries {
+			e.value.Freeze()
+		}
 	}
 }
 


Test patch:
diff --git a/starlarkstruct/testdata/struct.star b/starlarkstruct/testdata/struct.star
index e54fe04..993a84f 100644
--- a/starlarkstruct/testdata/struct.star
+++ b/starlarkstruct/testdata/struct.star
@@ -61,3 +61,12 @@ assert.eq(alice + bob, person(age = 50, city = "NYC", name = "bob"))  # not comm
 assert.fails(lambda : alice + 1, "struct \\+ int")
 assert.eq(http + http, http)
 assert.fails(lambda : http + bob, "different constructors: hostport \\+ person")
+
+# Check that a struct with a circular reference doesn't crash when it gets frozen.
+def struct_with_a_circular_reference():
+    foo = lambda: print(self)
+    self = struct(foo = foo)
+    return self
+
+# A top-level assigment is what causes this value to be frozen at the end of the load.
+toplevel_struct_with_a_circular_reference = struct_with_a_circular_reference()