starlark: report "uninitialized cell" errors gracefully (#341)

The contents of a cell may be null, just like any other local.
We should report this as an error.

So that we can name the variable in the error message,
we change the instruction set so that LOCAL<local>+CELL
are combined into a single LOCALCELL<local> instruction,
and FREE<free>+CELL become a single FREECELL<free> instruction.
For symmetry we also combine LOCAL<local>+SETCELL into SETLOCALCELL,
though it cannot fail. (Happily, all three changes are optimizations
previously described by TODO comments.)

Fixes #340

3 files changed, 192 insertions, 166 deletions

diff --git a/internal/compile/compile.go b/internal/compile/compile.go
index eb8e162..ab67018 100644
--- a/internal/compile/compile.go
+++ b/internal/compile/compile.go
@@ -46,7 +46,7 @@ var Disassemble = false
 const debug = false // make code generation verbose, for debugging the compiler
 
 // Increment this to force recompilation of saved bytecode files.
-const Version = 10
+const Version = 11
 
 type Opcode uint8
 
@@ -111,8 +111,6 @@ const (
 	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
-	SETCELL     //     value cell SETCELL     -
-	CELL        //           cell CELL        value
 
 	// --- opcodes with an argument must go below this line ---
 
@@ -122,21 +120,24 @@ const (
 	ITERJMP //            - ITERJMP<addr> elem   (and fall through) [acts on topmost iterator]
 	//       or:          - ITERJMP<addr> -      (and jump)
 
-	CONSTANT    //                 - CONSTANT<constant>  value
-	MAKETUPLE   //         x1 ... xn MAKETUPLE<n>        tuple
-	MAKELIST    //         x1 ... xn MAKELIST<n>         list
-	MAKEFUNC    // defaults+freevars MAKEFUNC<func>      fn
-	LOAD        //   from1 ... fromN module LOAD<n>      v1 ... vN
-	SETLOCAL    //             value SETLOCAL<local>     -
-	SETGLOBAL   //             value SETGLOBAL<global>   -
-	LOCAL       //                 - LOCAL<local>        value
-	FREE        //                 - FREE<freevar>       cell
-	GLOBAL      //                 - GLOBAL<global>      value
-	PREDECLARED //                 - PREDECLARED<name>   value
-	UNIVERSAL   //                 - UNIVERSAL<name>     value
-	ATTR        //                 x ATTR<name>          y           y = x.name
-	SETFIELD    //               x y SETFIELD<name>      -           x.name = y
-	UNPACK      //          iterable UNPACK<n>           vn ... v1
+	CONSTANT     //                 - CONSTANT<constant>  value
+	MAKETUPLE    //         x1 ... xn MAKETUPLE<n>        tuple
+	MAKELIST     //         x1 ... xn MAKELIST<n>         list
+	MAKEFUNC     // defaults+freevars MAKEFUNC<func>      fn
+	LOAD         //   from1 ... fromN module LOAD<n>      v1 ... vN
+	SETLOCAL     //             value SETLOCAL<local>     -
+	SETGLOBAL    //             value SETGLOBAL<global>   -
+	LOCAL        //                 - LOCAL<local>        value
+	FREE         //                 - FREE<freevar>       cell
+	FREECELL     //                 - FREECELL<freevar>   value       (content of FREE cell)
+	LOCALCELL    //                 - LOCALCELL<local>    value       (content of LOCAL cell)
+	SETLOCALCELL //             value SETLOCALCELL<local> -           (set content of LOCAL cell)
+	GLOBAL       //                 - GLOBAL<global>      value
+	PREDECLARED  //                 - PREDECLARED<name>   value
+	UNIVERSAL    //                 - UNIVERSAL<name>     value
+	ATTR         //                 x ATTR<name>          y           y = x.name
+	SETFIELD     //               x y SETFIELD<name>      -           x.name = y
+	UNPACK       //          iterable UNPACK<n>           vn ... v1
 
 	// n>>8 is #positional args and n&0xff is #named args (pairs).
 	CALL        // fn positional named                CALL<n>        result
@@ -151,72 +152,73 @@ const (
 // TODO(adonovan): add dynamic checks for missing opcodes in the tables below.
 
 var opcodeNames = [...]string{
-	AMP:         "amp",
-	APPEND:      "append",
-	ATTR:        "attr",
-	CALL:        "call",
-	CALL_KW:     "call_kw ",
-	CALL_VAR:    "call_var",
-	CALL_VAR_KW: "call_var_kw",
-	CELL:        "cell",
-	CIRCUMFLEX:  "circumflex",
-	CJMP:        "cjmp",
-	CONSTANT:    "constant",
-	DUP2:        "dup2",
-	DUP:         "dup",
-	EQL:         "eql",
-	EXCH:        "exch",
-	FALSE:       "false",
-	FREE:        "free",
-	GE:          "ge",
-	GLOBAL:      "global",
-	GT:          "gt",
-	GTGT:        "gtgt",
-	IN:          "in",
-	INDEX:       "index",
-	INPLACE_ADD: "inplace_add",
-	ITERJMP:     "iterjmp",
-	ITERPOP:     "iterpop",
-	ITERPUSH:    "iterpush",
-	JMP:         "jmp",
-	LE:          "le",
-	LOAD:        "load",
-	LOCAL:       "local",
-	LT:          "lt",
-	LTLT:        "ltlt",
-	MAKEDICT:    "makedict",
-	MAKEFUNC:    "makefunc",
-	MAKELIST:    "makelist",
-	MAKETUPLE:   "maketuple",
-	MANDATORY:   "mandatory",
-	MINUS:       "minus",
-	NEQ:         "neq",
-	NONE:        "none",
-	NOP:         "nop",
-	NOT:         "not",
-	PERCENT:     "percent",
-	PIPE:        "pipe",
-	PLUS:        "plus",
-	POP:         "pop",
-	PREDECLARED: "predeclared",
-	RETURN:      "return",
-	SETCELL:     "setcell",
-	SETDICT:     "setdict",
-	SETDICTUNIQ: "setdictuniq",
-	SETFIELD:    "setfield",
-	SETGLOBAL:   "setglobal",
-	SETINDEX:    "setindex",
-	SETLOCAL:    "setlocal",
-	SLASH:       "slash",
-	SLASHSLASH:  "slashslash",
-	SLICE:       "slice",
-	STAR:        "star",
-	TILDE:       "tilde",
-	TRUE:        "true",
-	UMINUS:      "uminus",
-	UNIVERSAL:   "universal",
-	UNPACK:      "unpack",
-	UPLUS:       "uplus",
+	AMP:          "amp",
+	APPEND:       "append",
+	ATTR:         "attr",
+	CALL:         "call",
+	CALL_KW:      "call_kw ",
+	CALL_VAR:     "call_var",
+	CALL_VAR_KW:  "call_var_kw",
+	CIRCUMFLEX:   "circumflex",
+	CJMP:         "cjmp",
+	CONSTANT:     "constant",
+	DUP2:         "dup2",
+	DUP:          "dup",
+	EQL:          "eql",
+	EXCH:         "exch",
+	FALSE:        "false",
+	FREE:         "free",
+	FREECELL:     "freecell",
+	GE:           "ge",
+	GLOBAL:       "global",
+	GT:           "gt",
+	GTGT:         "gtgt",
+	IN:           "in",
+	INDEX:        "index",
+	INPLACE_ADD:  "inplace_add",
+	ITERJMP:      "iterjmp",
+	ITERPOP:      "iterpop",
+	ITERPUSH:     "iterpush",
+	JMP:          "jmp",
+	LE:           "le",
+	LOAD:         "load",
+	LOCAL:        "local",
+	LOCALCELL:    "localcell",
+	LT:           "lt",
+	LTLT:         "ltlt",
+	MAKEDICT:     "makedict",
+	MAKEFUNC:     "makefunc",
+	MAKELIST:     "makelist",
+	MAKETUPLE:    "maketuple",
+	MANDATORY:    "mandatory",
+	MINUS:        "minus",
+	NEQ:          "neq",
+	NONE:         "none",
+	NOP:          "nop",
+	NOT:          "not",
+	PERCENT:      "percent",
+	PIPE:         "pipe",
+	PLUS:         "plus",
+	POP:          "pop",
+	PREDECLARED:  "predeclared",
+	RETURN:       "return",
+	SETDICT:      "setdict",
+	SETDICTUNIQ:  "setdictuniq",
+	SETFIELD:     "setfield",
+	SETGLOBAL:    "setglobal",
+	SETINDEX:     "setindex",
+	SETLOCAL:     "setlocal",
+	SETLOCALCELL: "setlocalcell",
+	SLASH:        "slash",
+	SLASHSLASH:   "slashslash",
+	SLICE:        "slice",
+	STAR:         "star",
+	TILDE:        "tilde",
+	TRUE:         "true",
+	UMINUS:       "uminus",
+	UNIVERSAL:    "universal",
+	UNPACK:       "unpack",
+	UPLUS:        "uplus",
 }
 
 const variableStackEffect = 0x7f
@@ -224,70 +226,71 @@ const variableStackEffect = 0x7f
 // stackEffect records the effect on the size of the operand stack of
 // each kind of instruction. For some instructions this requires computation.
 var stackEffect = [...]int8{
-	AMP:         -1,
-	APPEND:      -2,
-	ATTR:        0,
-	CALL:        variableStackEffect,
-	CALL_KW:     variableStackEffect,
-	CALL_VAR:    variableStackEffect,
-	CALL_VAR_KW: variableStackEffect,
-	CELL:        0,
-	CIRCUMFLEX:  -1,
-	CJMP:        -1,
-	CONSTANT:    +1,
-	DUP2:        +2,
-	DUP:         +1,
-	EQL:         -1,
-	FALSE:       +1,
-	FREE:        +1,
-	GE:          -1,
-	GLOBAL:      +1,
-	GT:          -1,
-	GTGT:        -1,
-	IN:          -1,
-	INDEX:       -1,
-	INPLACE_ADD: -1,
-	ITERJMP:     variableStackEffect,
-	ITERPOP:     0,
-	ITERPUSH:    -1,
-	JMP:         0,
-	LE:          -1,
-	LOAD:        -1,
-	LOCAL:       +1,
-	LT:          -1,
-	LTLT:        -1,
-	MAKEDICT:    +1,
-	MAKEFUNC:    0,
-	MAKELIST:    variableStackEffect,
-	MAKETUPLE:   variableStackEffect,
-	MANDATORY:   +1,
-	MINUS:       -1,
-	NEQ:         -1,
-	NONE:        +1,
-	NOP:         0,
-	NOT:         0,
-	PERCENT:     -1,
-	PIPE:        -1,
-	PLUS:        -1,
-	POP:         -1,
-	PREDECLARED: +1,
-	RETURN:      -1,
-	SETCELL:     -2,
-	SETDICT:     -3,
-	SETDICTUNIQ: -3,
-	SETFIELD:    -2,
-	SETGLOBAL:   -1,
-	SETINDEX:    -3,
-	SETLOCAL:    -1,
-	SLASH:       -1,
-	SLASHSLASH:  -1,
-	SLICE:       -3,
-	STAR:        -1,
-	TRUE:        +1,
-	UMINUS:      0,
-	UNIVERSAL:   +1,
-	UNPACK:      variableStackEffect,
-	UPLUS:       0,
+	AMP:          -1,
+	APPEND:       -2,
+	ATTR:         0,
+	CALL:         variableStackEffect,
+	CALL_KW:      variableStackEffect,
+	CALL_VAR:     variableStackEffect,
+	CALL_VAR_KW:  variableStackEffect,
+	CIRCUMFLEX:   -1,
+	CJMP:         -1,
+	CONSTANT:     +1,
+	DUP2:         +2,
+	DUP:          +1,
+	EQL:          -1,
+	FALSE:        +1,
+	FREE:         +1,
+	FREECELL:     +1,
+	GE:           -1,
+	GLOBAL:       +1,
+	GT:           -1,
+	GTGT:         -1,
+	IN:           -1,
+	INDEX:        -1,
+	INPLACE_ADD:  -1,
+	ITERJMP:      variableStackEffect,
+	ITERPOP:      0,
+	ITERPUSH:     -1,
+	JMP:          0,
+	LE:           -1,
+	LOAD:         -1,
+	LOCAL:        +1,
+	LOCALCELL:    +1,
+	LT:           -1,
+	LTLT:         -1,
+	MAKEDICT:     +1,
+	MAKEFUNC:     0,
+	MAKELIST:     variableStackEffect,
+	MAKETUPLE:    variableStackEffect,
+	MANDATORY:    +1,
+	MINUS:        -1,
+	NEQ:          -1,
+	NONE:         +1,
+	NOP:          0,
+	NOT:          0,
+	PERCENT:      -1,
+	PIPE:         -1,
+	PLUS:         -1,
+	POP:          -1,
+	PREDECLARED:  +1,
+	RETURN:       -1,
+	SETLOCALCELL: -1,
+	SETDICT:      -3,
+	SETDICTUNIQ:  -3,
+	SETFIELD:     -2,
+	SETGLOBAL:    -1,
+	SETINDEX:     -3,
+	SETLOCAL:     -1,
+	SLASH:        -1,
+	SLASHSLASH:   -1,
+	SLICE:        -3,
+	STAR:         -1,
+	TRUE:         +1,
+	UMINUS:       0,
+	UNIVERSAL:    +1,
+	UNPACK:       variableStackEffect,
+	UPLUS:        0,
 }
 
 func (op Opcode) String() string {
@@ -994,9 +997,7 @@ func (fcomp *fcomp) set(id *syntax.Ident) {
 	case resolve.Local:
 		fcomp.emit1(SETLOCAL, uint32(bind.Index))
 	case resolve.Cell:
-		// TODO(adonovan): opt: make a single op for LOCAL<n>, SETCELL.
-		fcomp.emit1(LOCAL, uint32(bind.Index))
-		fcomp.emit(SETCELL)
+		fcomp.emit1(SETLOCALCELL, uint32(bind.Index))
 	case resolve.Global:
 		fcomp.emit1(SETGLOBAL, uint32(bind.Index))
 	default:
@@ -1014,13 +1015,9 @@ func (fcomp *fcomp) lookup(id *syntax.Ident) {
 	case resolve.Local:
 		fcomp.emit1(LOCAL, uint32(bind.Index))
 	case resolve.Free:
-		// TODO(adonovan): opt: make a single op for FREE<n>, CELL.
-		fcomp.emit1(FREE, uint32(bind.Index))
-		fcomp.emit(CELL)
+		fcomp.emit1(FREECELL, uint32(bind.Index))
 	case resolve.Cell:
-		// TODO(adonovan): opt: make a single op for LOCAL<n>, CELL.
-		fcomp.emit1(LOCAL, uint32(bind.Index))
-		fcomp.emit(CELL)
+		fcomp.emit1(LOCALCELL, uint32(bind.Index))
 	case resolve.Global:
 		fcomp.emit1(GLOBAL, uint32(bind.Index))
 	case resolve.Predeclared:
diff --git a/starlark/interp.go b/starlark/interp.go
index f00382c..642d8f5 100644
--- a/starlark/interp.go
+++ b/starlark/interp.go
@@ -547,11 +547,9 @@ loop:
 			locals[arg] = stack[sp-1]
 			sp--
 
-		case compile.SETCELL:
-			x := stack[sp-2]
-			y := stack[sp-1]
-			sp -= 2
-			y.(*cell).v = x
+		case compile.SETLOCALCELL:
+			locals[arg].(*cell).v = stack[sp-1]
+			sp--
 
 		case compile.SETGLOBAL:
 			fn.module.globals[arg] = stack[sp-1]
@@ -570,9 +568,23 @@ loop:
 			stack[sp] = fn.freevars[arg]
 			sp++
 
-		case compile.CELL:
-			x := stack[sp-1]
-			stack[sp-1] = x.(*cell).v
+		case compile.LOCALCELL:
+			v := locals[arg].(*cell).v
+			if v == nil {
+				err = fmt.Errorf("local variable %s referenced before assignment", f.Locals[arg].Name)
+				break loop
+			}
+			stack[sp] = v
+			sp++
+
+		case compile.FREECELL:
+			v := fn.freevars[arg].(*cell).v
+			if v == nil {
+				err = fmt.Errorf("local variable %s referenced before assignment", f.Freevars[arg].Name)
+				break loop
+			}
+			stack[sp] = v
+			sp++
 
 		case compile.GLOBAL:
 			x := fn.module.globals[arg]
@@ -641,7 +653,7 @@ func (mandatory) Hash() (uint32, error) { return 0, nil }
 // A cell is a box containing a Value.
 // Local variables marked as cells hold their value indirectly
 // so that they may be shared by outer and inner nested functions.
-// Cells are always accessed using indirect CELL/SETCELL instructions.
+// Cells are always accessed using indirect {FREE,LOCAL,SETLOCAL}CELL instructions.
 // The FreeVars tuple contains only cells.
 // The FREE instruction always yields a cell.
 type cell struct{ v Value }
diff --git a/starlark/testdata/function.star b/starlark/testdata/function.star
index bdfa5ac..737df26 100644
--- a/starlark/testdata/function.star
+++ b/starlark/testdata/function.star
@@ -287,6 +287,23 @@ def e():
 
 assert.fails(e, "local variable x referenced before assignment")
 
+def f():
+    def inner():
+        return x
+    if False:
+        x = 0
+    return x # fails (x is an uninitialized cell of this function)
+
+assert.fails(f, "local variable x referenced before assignment")
+
+def g():
+    def inner():
+        return x # fails (x is an uninitialized cell of the enclosing function)
+    if False:
+        x = 0
+    return inner()
+
+assert.fails(g, "local variable x referenced before assignment")
 
 ---
 # A trailing comma is allowed in any function definition or call.