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

2 files changed, 67 insertions, 21 deletions

diff --git a/internal/compile/compile.go b/internal/compile/compile.go
index 6d98fc1..48d5fc3 100644
--- a/internal/compile/compile.go
+++ b/internal/compile/compile.go
@@ -8,8 +8,12 @@
 //   - an stack of active iterators.
 //   - an array of local variables.
 //     The number of local variables and their indices are computed by the resolver.
+//     Locals (possibly including parameters) that are shared with nested functions
+//     are 'cells': their locals array slot will contain a value of type 'cell',
+//     an indirect value in a box that is explicitly read/updated by instructions.
 //   - an array of free variables, for nested functions.
-//     As with locals, these are computed by the resolver.
+//     Free variables are a subset of the ancestors' cell variables.
+//     As with locals and cells, these are computed by the resolver.
 //   - an array of global variables, shared among all functions in the same module.
 //     All elements are initially nil.
 //   - two maps of predeclared and universal identifiers.
@@ -36,7 +40,7 @@ import (
 const debug = false // TODO(adonovan): use a bitmap of options; and regexp to match files
 
 // Increment this to force recompilation of saved bytecode files.
-const Version = 7
+const Version = 8
 
 type Opcode uint8
 
@@ -89,18 +93,20 @@ const (
 	FALSE     // - FALSE False
 	MANDATORY // - MANDATORY Mandatory	     [sentinel value for required kwonly args]
 
-	ITERPUSH    //       iterable ITERPUSH -     [pushes the iterator stack]
-	ITERPOP     //              - ITERPOP -      [pops the iterator stack]
-	NOT         //          value NOT bool
-	RETURN      //          value RETURN -
-	SETINDEX    //        a i new SETINDEX -
-	INDEX       //            a i INDEX elem
-	SETDICT     // dict key value SETDICT -
+	ITERPUSH    //       iterable ITERPUSH    -  [pushes the iterator stack]
+	ITERPOP     //              - ITERPOP     -    [pops the iterator stack]
+	NOT         //          value NOT         bool
+	RETURN      //          value RETURN      -
+	SETINDEX    //        a i new SETINDEX    -
+	INDEX       //            a i INDEX       elem
+	SETDICT     // dict key value SETDICT     -
 	SETDICTUNIQ // dict key value SETDICTUNIQ -
-	APPEND      //      list elem APPEND -
-	SLICE       //   x lo hi step SLICE slice
+	APPEND      //      list elem APPEND      -
+	SLICE       //   x lo hi step SLICE       slice
 	INPLACE_ADD //            x y INPLACE_ADD z      where z is x+y or x.extend(y)
-	MAKEDICT    //              - MAKEDICT dict
+	MAKEDICT    //              - MAKEDICT    dict
+	SETCELL     //     value cell SETCELL     -
+	CELL        //           cell CELL        value
 
 	// --- opcodes with an argument must go below this line ---
 
@@ -118,7 +124,7 @@ const (
 	SETLOCAL    //             value SETLOCAL<local>     -
 	SETGLOBAL   //             value SETGLOBAL<global>   -
 	LOCAL       //                 - LOCAL<local>        value
-	FREE        //                 - FREE<freevar>       value
+	FREE        //                 - FREE<freevar>       cell
 	GLOBAL      //                 - GLOBAL<global>      value
 	PREDECLARED //                 - PREDECLARED<name>   value
 	UNIVERSAL   //                 - UNIVERSAL<name>     value
@@ -146,6 +152,7 @@ var opcodeNames = [...]string{
 	CALL_KW:     "call_kw ",
 	CALL_VAR:    "call_var",
 	CALL_VAR_KW: "call_var_kw",
+	CELL:        "cell",
 	CIRCUMFLEX:  "circumflex",
 	CJMP:        "cjmp",
 	CONSTANT:    "constant",
@@ -187,6 +194,7 @@ var opcodeNames = [...]string{
 	POP:         "pop",
 	PREDECLARED: "predeclared",
 	RETURN:      "return",
+	SETCELL:     "setcell",
 	SETDICT:     "setdict",
 	SETDICTUNIQ: "setdictuniq",
 	SETFIELD:    "setfield",
@@ -217,6 +225,7 @@ var stackEffect = [...]int8{
 	CALL_KW:     variableStackEffect,
 	CALL_VAR:    variableStackEffect,
 	CALL_VAR_KW: variableStackEffect,
+	CELL:        0,
 	CIRCUMFLEX:  -1,
 	CJMP:        -1,
 	CONSTANT:    +1,
@@ -257,6 +266,7 @@ var stackEffect = [...]int8{
 	POP:         -1,
 	PREDECLARED: +1,
 	RETURN:      -1,
+	SETCELL:     -2,
 	SETDICT:     -3,
 	SETDICTUNIQ: -3,
 	SETFIELD:    -2,
@@ -308,6 +318,7 @@ type Funcode struct {
 	Code                  []byte          // the byte code
 	pclinetab             []uint16        // mapping from pc to linenum
 	Locals                []Binding       // locals, parameters first
+	Cells                 []int           // indices of Locals that require cells
 	Freevars              []Binding       // for tracing
 	MaxStack              int
 	NumParams             int
@@ -446,6 +457,13 @@ func (pcomp *pcomp) function(name string, pos syntax.Position, stmts []syntax.St
 		},
 	}
 
+	// Record indices of locals that require cells.
+	for i, local := range locals {
+		if local.Scope == syntax.CellScope {
+			fcomp.fn.Cells = append(fcomp.fn.Cells, i)
+		}
+	}
+
 	if debug {
 		fmt.Fprintf(os.Stderr, "start function(%s @ %s)\n", name, pos)
 	}
@@ -895,33 +913,43 @@ func (fcomp *fcomp) setPos(pos syntax.Position) {
 }
 
 // set emits code to store the top-of-stack value
-// to the specified local or global variable.
+// to the specified local, cell, or global variable.
 func (fcomp *fcomp) set(id *syntax.Ident) {
 	bind := id.Binding
 	switch bind.Scope {
 	case syntax.LocalScope:
 		fcomp.emit1(SETLOCAL, uint32(bind.Index))
+	case syntax.CellScope:
+		// TODO(adonovan): opt: make a single op for LOCAL<n>, SETCELL.
+		fcomp.emit1(LOCAL, uint32(bind.Index))
+		fcomp.emit(SETCELL)
 	case syntax.GlobalScope:
 		fcomp.emit1(SETGLOBAL, uint32(bind.Index))
 	default:
-		log.Fatalf("%s: set(%s): neither global nor local (%d)", id.NamePos, id.Name, bind.Scope)
+		log.Fatalf("%s: set(%s): not global/local/cell (%d)", id.NamePos, id.Name, bind.Scope)
 	}
 }
 
 // lookup emits code to push the value of the specified variable.
 func (fcomp *fcomp) lookup(id *syntax.Ident) {
 	bind := id.Binding
+	if bind.Scope != syntax.UniversalScope { // (universal lookup can't fail)
+		fcomp.setPos(id.NamePos)
+	}
 	switch bind.Scope {
 	case syntax.LocalScope:
-		fcomp.setPos(id.NamePos)
 		fcomp.emit1(LOCAL, uint32(bind.Index))
 	case syntax.FreeScope:
+		// TODO(adonovan): opt: make a single op for FREE<n>, CELL.
 		fcomp.emit1(FREE, uint32(bind.Index))
+		fcomp.emit(CELL)
+	case syntax.CellScope:
+		// TODO(adonovan): opt: make a single op for LOCAL<n>, CELL.
+		fcomp.emit1(LOCAL, uint32(bind.Index))
+		fcomp.emit(CELL)
 	case syntax.GlobalScope:
-		fcomp.setPos(id.NamePos)
 		fcomp.emit1(GLOBAL, uint32(bind.Index))
 	case syntax.PredeclaredScope:
-		fcomp.setPos(id.NamePos)
 		fcomp.emit1(PREDECLARED, fcomp.pcomp.nameIndex(id.Name))
 	case syntax.UniversalScope:
 		fcomp.emit1(UNIVERSAL, fcomp.pcomp.nameIndex(id.Name))
@@ -1706,14 +1734,16 @@ func (fcomp *fcomp) function(pos syntax.Position, name string, f *syntax.Functio
 	}
 	fcomp.emit1(MAKETUPLE, uint32(n))
 
-	// Capture the values of the function's
+	// Capture the cells of the function's
 	// free variables from the lexical environment.
 	for _, freevar := range f.FreeVars {
+		// Don't call fcomp.lookup because we want
+		// the cell itself, not its content.
 		switch freevar.Scope {
-		case syntax.LocalScope:
-			fcomp.emit1(LOCAL, uint32(freevar.Index))
 		case syntax.FreeScope:
 			fcomp.emit1(FREE, uint32(freevar.Index))
+		case syntax.CellScope:
+			fcomp.emit1(LOCAL, uint32(freevar.Index))
 		}
 	}
 	fcomp.emit1(MAKETUPLE, uint32(len(f.FreeVars)))
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,