starlark: capture free variables by reference (#172)

This change causes closures for nested functions to capture their
enclosing functions' variables by reference. Even though an inner
function cannot update outer variables, it must observe updates to
them made by the outer function.

A special case of this is a nested recursive function f:

   def outer():
       def f(): ...f()...

The def f statement constructs a closure which captures f, and then
binds the closure value to f. If the closure captures by value (as
before this change), the def statement will fail because f is
undefined (see issue #170). Now, the closure captures a reference
to f, so it is safe to execute before f has been assigned.

This is implemented as follows. During resolving, captured local
variables such as f are marked as as "cells". The compiler assumes and
guarantees that such locals are values of a special internal type
called 'cell', and it emits explicit instructions to load from and
store into the cell. At runtime, cells are created on entry to the function;
parameters may be "spilled" into cells as needed.
Each cell variable gets its own allocation to avoid spurious liveness.
A function's tuple of free variables contains only cells.

Fixes #170

1 files changed, 16 insertions, 0 deletions

diff --git a/internal/compile/serial.go b/internal/compile/serial.go
index b3f986f..0107ef9 100644
--- a/internal/compile/serial.go
+++ b/internal/compile/serial.go
@@ -35,6 +35,8 @@ package compile
 //	pclinetab	[]varint
 //	numlocals	varint
 //	locals		[]Ident
+//	numcells	varint
+//	cells		[]int
 //	numfreevars	varint
 //	freevar		[]Ident
 //	maxstack	varint
@@ -183,6 +185,10 @@ func (e *encoder) function(fn *Funcode) {
 		e.int64(int64(x))
 	}
 	e.bindings(fn.Locals)
+	e.int(len(fn.Cells))
+	for _, index := range fn.Cells {
+		e.int(index)
+	}
 	e.bindings(fn.Freevars)
 	e.int(fn.MaxStack)
 	e.int(fn.NumParams)
@@ -338,6 +344,14 @@ func (d *decoder) bindings() []Binding {
 	return bindings
 }
 
+func (d *decoder) ints() []int {
+	ints := make([]int, d.int())
+	for i := range ints {
+		ints[i] = d.int()
+	}
+	return ints
+}
+
 func (d *decoder) bool() bool { return d.int() != 0 }
 
 func (d *decoder) function() *Funcode {
@@ -349,6 +363,7 @@ func (d *decoder) function() *Funcode {
 		pclinetab[i] = uint16(d.int())
 	}
 	locals := d.bindings()
+	cells := d.ints()
 	freevars := d.bindings()
 	maxStack := d.int()
 	numParams := d.int()
@@ -363,6 +378,7 @@ func (d *decoder) function() *Funcode {
 		Code:            code,
 		pclinetab:       pclinetab,
 		Locals:          locals,
+		Cells:           cells,
 		Freevars:        freevars,
 		MaxStack:        maxStack,
 		NumParams:       numParams,