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 #170diff --git a/resolve/resolve.go b/resolve/resolve.go
index 9f73008..18a0bf2 100644
--- a/resolve/resolve.go
+++ b/resolve/resolve.go
@@ -414,11 +414,11 @@
}
// resolveLocalUses is called when leaving a container (function/module)
-// block. It resolves all uses of locals within that block.
+// block. It resolves all uses of locals/cells within that block.
func (b *block) resolveLocalUses() {
unresolved := b.uses[:0]
for _, use := range b.uses {
- if bind := lookupLocal(use); bind != nil && bind.Scope == syntax.LocalScope {
+ if bind := lookupLocal(use); bind != nil && (bind.Scope == syntax.LocalScope || bind.Scope == syntax.CellScope) {
use.id.Binding = bind
} else {
unresolved = append(unresolved, use)
@@ -877,10 +877,14 @@
if !ok {
// Defined in parent block?
bind = r.lookupLexical(use, env.parent)
- if env.function != nil && (bind.Scope == syntax.LocalScope || bind.Scope == syntax.FreeScope) {
+ if env.function != nil && (bind.Scope == syntax.LocalScope || bind.Scope == syntax.FreeScope || bind.Scope == syntax.CellScope) {
// Found in parent block, which belongs to enclosing function.
// Add the parent's binding to the function's freevars,
- // and add a new 'free' binding to the inner function's block.
+ // and add a new 'free' binding to the inner function's block,
+ // and turn the parent's local into cell.
+ if bind.Scope == syntax.LocalScope {
+ bind.Scope = syntax.CellScope
+ }
index := len(env.function.FreeVars)
env.function.FreeVars = append(env.function.FreeVars, bind)
bind = &syntax.Binding{