syntax: expose Binding concept (#171)

This refactoring exposes the concept of Binding, which was previously
internal to the resolver. Previously the Scope and Index fields of the
binding were copied into each Ident; now the relationship is indirect.

A Binding is the entity created by the first binding occurrence of a
name, and the binding ties together all uses of that name.

This change is a preparation for fixing issue #170, which requires
that we mark the bindings that need to be allocated indirectly in
closure cells. Currently, in the absence of an indirect relationship
there is no way to mark a binding so that all Idents are affected.

This change leads to a minor simplification in lookupLexical,
which used to synthesize a new Ident, when logically it is
creating only a new binding.

Unfortunately, Binding and Scope must be declared in the syntax
package even though they logically belong to the resolver,
because the (resolved) syntax trees refer to them.

(If you're familiar with the go/types package, syntax.Binding
corresponds to types.Var. go/types solves its analogous dependency
problem by putting resolver-derived facts in an external map, not the
syntax tree, which is expensive. So perhaps it's more accurate to
say Binding corresponds to the deprecated ast.Object.)

2 files changed, 52 insertions, 11 deletions

diff --git a/syntax/binding.go b/syntax/binding.go
new file mode 100644
index 0000000..2ed10b0
--- /dev/null
+++ b/syntax/binding.go
@@ -0,0 +1,43 @@
+package syntax
+
+// This file defines resolver data types referenced by the syntax tree.
+// We cannot guarantee API stability for these types
+// as they are closely tied to the implementation.
+
+// A Binding ties together all identifiers that denote the same variable.
+// The resolver computes a binding for every Ident.
+type Binding struct {
+	Scope Scope
+
+	// Index records the index into the enclosing
+	// - {DefStmt,File}.Locals, if Scope==Local
+	// - DefStmt.FreeVars,      if Scope==Free
+	// - File.Globals,          if Scope==Global.
+	// It is zero if Scope is Predeclared, Universal, or Undefined.
+	Index int
+
+	First *Ident // first binding use (iff Scope==Local/Free/Global)
+}
+
+// The Scope of Binding indicates what kind of scope it has.
+type Scope uint8
+
+const (
+	UndefinedScope   Scope = iota // name is not defined
+	LocalScope                    // name is local to its function
+	FreeScope                     // name is local to some enclosing function
+	GlobalScope                   // name is global to module
+	PredeclaredScope              // name is predeclared for this module (e.g. glob)
+	UniversalScope                // name is universal (e.g. len)
+)
+
+var scopeNames = [...]string{
+	UndefinedScope:   "undefined",
+	LocalScope:       "local",
+	FreeScope:        "free",
+	GlobalScope:      "global",
+	PredeclaredScope: "predeclared",
+	UniversalScope:   "universal",
+}
+
+func (scope Scope) String() string { return scopeNames[scope] }
diff --git a/syntax/syntax.go b/syntax/syntax.go
index 4ed4066..d805540 100644
--- a/syntax/syntax.go
+++ b/syntax/syntax.go
@@ -71,8 +71,8 @@ type File struct {
 	Stmts []Stmt
 
 	// set by resolver:
-	Locals  []*Ident // this file's (comprehension-)local variables
-	Globals []*Ident // this file's global variables
+	Locals  []*Binding // this file's (comprehension-)local variables
+	Globals []*Binding // this file's global variables
 }
 
 func (x *File) Span() (start, end Position) {
@@ -126,11 +126,11 @@ type Function struct {
 	Body     []Stmt
 
 	// set by resolver:
-	HasVarargs      bool     // whether params includes *args (convenience)
-	HasKwargs       bool     // whether params includes **kwargs (convenience)
-	NumKwonlyParams int      // number of keyword-only optional parameters
-	Locals          []*Ident // this function's local variables, parameters first
-	FreeVars        []*Ident // enclosing local variables to capture in closure
+	HasVarargs      bool       // whether params includes *args (convenience)
+	HasKwargs       bool       // whether params includes **kwargs (convenience)
+	NumKwonlyParams int        // number of keyword-only optional parameters
+	Locals          []*Binding // this function's local variables, parameters first
+	FreeVars        []*Binding // enclosing local variables to capture in closure
 }
 
 func (x *Function) Span() (start, end Position) {
@@ -260,10 +260,8 @@ type Ident struct {
 	NamePos Position
 	Name    string
 
-	// set by resolver:
-
-	Scope uint8 // see type resolve.Scope
-	Index int   // index into enclosing {DefStmt,File}.Locals (if scope==Local) or DefStmt.FreeVars (if scope==Free) or File.Globals (if scope==Global)
+	// set by resolver
+	Binding *Binding
 }
 
 func (x *Ident) Span() (start, end Position) {