Source file src/go.starlark.net/resolve/resolve.go

Documentation: go.starlark.net/resolve

     1  // Copyright 2017 The Bazel Authors. All rights reserved.
     2  // Use of this source code is governed by a BSD-style
     3  // license that can be found in the LICENSE file.
     4  
     5  // Package resolve defines a name-resolution pass for Starlark abstract
     6  // syntax trees.
     7  //
     8  // The resolver sets the Locals and FreeVars arrays of each DefStmt and
     9  // the LocalIndex field of each syntax.Ident that refers to a local or
    10  // free variable.  It also sets the Locals array of a File for locals
    11  // bound by top-level comprehensions and load statements.
    12  // Identifiers for global variables do not get an index.
    13  package resolve // import "go.starlark.net/resolve"
    14  
    15  // All references to names are statically resolved.  Names may be
    16  // predeclared, global, or local to a function or file.
    17  // File-local variables include those bound by top-level comprehensions
    18  // and by load statements. ("Top-level" means "outside of any function".)
    19  // The resolver maps each global name to a small integer and each local
    20  // name to a small integer; these integers enable a fast and compact
    21  // representation of globals and locals in the evaluator.
    22  //
    23  // As an optimization, the resolver classifies each predeclared name as
    24  // either universal (e.g. None, len) or per-module (e.g. glob in Bazel's
    25  // build language), enabling the evaluator to share the representation
    26  // of the universal environment across all modules.
    27  //
    28  // The lexical environment is a tree of blocks with the file block at
    29  // its root. The file's child blocks may be of two kinds: functions
    30  // and comprehensions, and these may have further children of either
    31  // kind.
    32  //
    33  // Python-style resolution requires multiple passes because a name is
    34  // determined to be local to a function only if the function contains a
    35  // "binding" use of it; similarly, a name is determined to be global (as
    36  // opposed to predeclared) if the module contains a top-level binding use.
    37  // Unlike ordinary top-level assignments, the bindings created by load
    38  // statements are local to the file block.
    39  // A non-binding use may lexically precede the binding to which it is resolved.
    40  // In the first pass, we inspect each function, recording in
    41  // 'uses' each identifier and the environment block in which it occurs.
    42  // If a use of a name is binding, such as a function parameter or
    43  // assignment, we add the name to the block's bindings mapping and add a
    44  // local variable to the enclosing function.
    45  //
    46  // As we finish resolving each function, we inspect all the uses within
    47  // that function and discard ones that were found to be function-local. The
    48  // remaining ones must be either free (local to some lexically enclosing
    49  // function), or top-level (global, predeclared, or file-local), but we cannot tell
    50  // which until we have finished inspecting the outermost enclosing
    51  // function. At that point, we can distinguish local from top-level names
    52  // (and this is when Python would compute free variables).
    53  //
    54  // However, Starlark additionally requires that all references to global
    55  // names are satisfied by some declaration in the current module;
    56  // Starlark permits a function to forward-reference a global or file-local
    57  // that has not
    58  // been declared yet so long as it is declared before the end of the
    59  // module.  So, instead of re-resolving the unresolved references after
    60  // each top-level function, we defer this until the end of the module
    61  // and ensure that all such references are satisfied by some definition.
    62  //
    63  // At the end of the module, we visit each of the nested function blocks
    64  // in bottom-up order, doing a recursive lexical lookup for each
    65  // unresolved name.  If the name is found to be local to some enclosing
    66  // function, we must create a DefStmt.FreeVar (capture) parameter for
    67  // each intervening function.  We enter these synthetic bindings into
    68  // the bindings map so that we create at most one freevar per name.  If
    69  // the name was not local, we check that it was defined at module level.
    70  //
    71  // We resolve all uses of locals in the module (due to load statements
    72  // and comprehensions) in a similar way and compute the file's set of
    73  // local variables.
    74  //
    75  // Starlark enforces that all global names are assigned at most once on
    76  // all control flow paths by forbidding if/else statements and loops at
    77  // top level. A global may be used before it is defined, leading to a
    78  // dynamic error. However, the AllowGlobalReassign flag (really: allow
    79  // top-level reassign) makes the resolver allow multiple to a variable
    80  // at top-level. It also allows if-, for-, and while-loops at top-level,
    81  // which in turn may make the evaluator dynamically assign multiple
    82  // values to a variable at top-level. (These two roles should be separated.)
    83  
    84  import (
    85  	"fmt"
    86  	"log"
    87  	"sort"
    88  	"strings"
    89  
    90  	"go.starlark.net/internal/spell"
    91  	"go.starlark.net/syntax"
    92  )
    93  
    94  const debug = false
    95  const doesnt = "this Starlark dialect does not "
    96  
    97  // global options
    98  // These features are either not standard Starlark (yet), or deprecated
    99  // features of the BUILD language, so we put them behind flags.
   100  var (
   101  	AllowSet            = false // allow the 'set' built-in
   102  	AllowGlobalReassign = false // allow reassignment to top-level names; also, allow if/for/while at top-level
   103  	AllowRecursion      = false // allow while statements and recursive functions
   104  	LoadBindsGlobally   = false // load creates global not file-local bindings (deprecated)
   105  
   106  	// obsolete flags for features that are now standard. No effect.
   107  	AllowNestedDef = true
   108  	AllowLambda    = true
   109  	AllowFloat     = true
   110  	AllowBitwise   = true
   111  )
   112  
   113  // File resolves the specified file and records information about the
   114  // module in file.Module.
   115  //
   116  // The isPredeclared and isUniversal predicates report whether a name is
   117  // a pre-declared identifier (visible in the current module) or a
   118  // universal identifier (visible in every module).
   119  // Clients should typically pass predeclared.Has for the first and
   120  // starlark.Universe.Has for the second, where predeclared is the
   121  // module's StringDict of predeclared names and starlark.Universe is the
   122  // standard set of built-ins.
   123  // The isUniverse predicate is supplied a parameter to avoid a cyclic
   124  // dependency upon starlark.Universe, not because users should ever need
   125  // to redefine it.
   126  func File(file *syntax.File, isPredeclared, isUniversal func(name string) bool) error {
   127  	return REPLChunk(file, nil, isPredeclared, isUniversal)
   128  }
   129  
   130  // REPLChunk is a generalization of the File function that supports a
   131  // non-empty initial global block, as occurs in a REPL.
   132  func REPLChunk(file *syntax.File, isGlobal, isPredeclared, isUniversal func(name string) bool) error {
   133  	r := newResolver(isGlobal, isPredeclared, isUniversal)
   134  	r.stmts(file.Stmts)
   135  
   136  	r.env.resolveLocalUses()
   137  
   138  	// At the end of the module, resolve all non-local variable references,
   139  	// computing closures.
   140  	// Function bodies may contain forward references to later global declarations.
   141  	r.resolveNonLocalUses(r.env)
   142  
   143  	file.Module = &Module{
   144  		Locals:  r.moduleLocals,
   145  		Globals: r.moduleGlobals,
   146  	}
   147  
   148  	if len(r.errors) > 0 {
   149  		return r.errors
   150  	}
   151  	return nil
   152  }
   153  
   154  // Expr resolves the specified expression.
   155  // It returns the local variables bound within the expression.
   156  //
   157  // The isPredeclared and isUniversal predicates behave as for the File function.
   158  func Expr(expr syntax.Expr, isPredeclared, isUniversal func(name string) bool) ([]*Binding, error) {
   159  	r := newResolver(nil, isPredeclared, isUniversal)
   160  	r.expr(expr)
   161  	r.env.resolveLocalUses()
   162  	r.resolveNonLocalUses(r.env) // globals & universals
   163  	if len(r.errors) > 0 {
   164  		return nil, r.errors
   165  	}
   166  	return r.moduleLocals, nil
   167  }
   168  
   169  // An ErrorList is a non-empty list of resolver error messages.
   170  type ErrorList []Error // len > 0
   171  
   172  func (e ErrorList) Error() string { return e[0].Error() }
   173  
   174  // An Error describes the nature and position of a resolver error.
   175  type Error struct {
   176  	Pos syntax.Position
   177  	Msg string
   178  }
   179  
   180  func (e Error) Error() string { return e.Pos.String() + ": " + e.Msg }
   181  
   182  func newResolver(isGlobal, isPredeclared, isUniversal func(name string) bool) *resolver {
   183  	file := new(block)
   184  	return &resolver{
   185  		file:          file,
   186  		env:           file,
   187  		isGlobal:      isGlobal,
   188  		isPredeclared: isPredeclared,
   189  		isUniversal:   isUniversal,
   190  		globals:       make(map[string]*Binding),
   191  		predeclared:   make(map[string]*Binding),
   192  	}
   193  }
   194  
   195  type resolver struct {
   196  	// env is the current local environment:
   197  	// a linked list of blocks, innermost first.
   198  	// The tail of the list is the file block.
   199  	env  *block
   200  	file *block // file block (contains load bindings)
   201  
   202  	// moduleLocals contains the local variables of the module
   203  	// (due to load statements and comprehensions outside any function).
   204  	// moduleGlobals contains the global variables of the module.
   205  	moduleLocals  []*Binding
   206  	moduleGlobals []*Binding
   207  
   208  	// globals maps each global name in the module to its binding.
   209  	// predeclared does the same for predeclared and universal names.
   210  	globals     map[string]*Binding
   211  	predeclared map[string]*Binding
   212  
   213  	// These predicates report whether a name is
   214  	// pre-declared, either in this module or universally,
   215  	// or already declared in the module globals (as in a REPL).
   216  	// isGlobal may be nil.
   217  	isGlobal, isPredeclared, isUniversal func(name string) bool
   218  
   219  	loops   int // number of enclosing for/while loops
   220  	ifstmts int // number of enclosing if statements loops
   221  
   222  	errors ErrorList
   223  }
   224  
   225  // container returns the innermost enclosing "container" block:
   226  // a function (function != nil) or file (function == nil).
   227  // Container blocks accumulate local variable bindings.
   228  func (r *resolver) container() *block {
   229  	for b := r.env; ; b = b.parent {
   230  		if b.function != nil || b == r.file {
   231  			return b
   232  		}
   233  	}
   234  }
   235  
   236  func (r *resolver) push(b *block) {
   237  	r.env.children = append(r.env.children, b)
   238  	b.parent = r.env
   239  	r.env = b
   240  }
   241  
   242  func (r *resolver) pop() { r.env = r.env.parent }
   243  
   244  type block struct {
   245  	parent *block // nil for file block
   246  
   247  	// In the file (root) block, both these fields are nil.
   248  	function *Function             // only for function blocks
   249  	comp     *syntax.Comprehension // only for comprehension blocks
   250  
   251  	// bindings maps a name to its binding.
   252  	// A local binding has an index into its innermost enclosing container's locals array.
   253  	// A free binding has an index into its innermost enclosing function's freevars array.
   254  	bindings map[string]*Binding
   255  
   256  	// children records the child blocks of the current one.
   257  	children []*block
   258  
   259  	// uses records all identifiers seen in this container (function or file),
   260  	// and a reference to the environment in which they appear.
   261  	// As we leave each container block, we resolve them,
   262  	// so that only free and global ones remain.
   263  	// At the end of each top-level function we compute closures.
   264  	uses []use
   265  }
   266  
   267  func (b *block) bind(name string, bind *Binding) {
   268  	if b.bindings == nil {
   269  		b.bindings = make(map[string]*Binding)
   270  	}
   271  	b.bindings[name] = bind
   272  }
   273  
   274  func (b *block) String() string {
   275  	if b.function != nil {
   276  		return "function block at " + fmt.Sprint(b.function.Pos)
   277  	}
   278  	if b.comp != nil {
   279  		return "comprehension block at " + fmt.Sprint(b.comp.Span())
   280  	}
   281  	return "file block"
   282  }
   283  
   284  func (r *resolver) errorf(posn syntax.Position, format string, args ...interface{}) {
   285  	r.errors = append(r.errors, Error{posn, fmt.Sprintf(format, args...)})
   286  }
   287  
   288  // A use records an identifier and the environment in which it appears.
   289  type use struct {
   290  	id  *syntax.Ident
   291  	env *block
   292  }
   293  
   294  // bind creates a binding for id: a global (not file-local)
   295  // binding at top-level, a local binding otherwise.
   296  // At top-level, it reports an error if a global or file-local
   297  // binding already exists, unless AllowGlobalReassign.
   298  // It sets id.Binding to the binding (whether old or new),
   299  // and returns whether a binding already existed.
   300  func (r *resolver) bind(id *syntax.Ident) bool {
   301  	// Binding outside any local (comprehension/function) block?
   302  	if r.env == r.file {
   303  		bind, ok := r.file.bindings[id.Name]
   304  		if !ok {
   305  			bind, ok = r.globals[id.Name]
   306  			if !ok {
   307  				// first global binding of this name
   308  				bind = &Binding{
   309  					First: id,
   310  					Scope: Global,
   311  					Index: len(r.moduleGlobals),
   312  				}
   313  				r.globals[id.Name] = bind
   314  				r.moduleGlobals = append(r.moduleGlobals, bind)
   315  			}
   316  		}
   317  		if ok && !AllowGlobalReassign {
   318  			r.errorf(id.NamePos, "cannot reassign %s %s declared at %s",
   319  				bind.Scope, id.Name, bind.First.NamePos)
   320  		}
   321  		id.Binding = bind
   322  		return ok
   323  	}
   324  
   325  	return r.bindLocal(id)
   326  }
   327  
   328  func (r *resolver) bindLocal(id *syntax.Ident) bool {
   329  	// Mark this name as local to current block.
   330  	// Assign it a new local (positive) index in the current container.
   331  	_, ok := r.env.bindings[id.Name]
   332  	if !ok {
   333  		var locals *[]*Binding
   334  		if fn := r.container().function; fn != nil {
   335  			locals = &fn.Locals
   336  		} else {
   337  			locals = &r.moduleLocals
   338  		}
   339  		bind := &Binding{
   340  			First: id,
   341  			Scope: Local,
   342  			Index: len(*locals),
   343  		}
   344  		r.env.bind(id.Name, bind)
   345  		*locals = append(*locals, bind)
   346  	}
   347  
   348  	r.use(id)
   349  	return ok
   350  }
   351  
   352  func (r *resolver) use(id *syntax.Ident) {
   353  	use := use{id, r.env}
   354  
   355  	// The spec says that if there is a global binding of a name
   356  	// then all references to that name in that block refer to the
   357  	// global, even if the use precedes the def---just as for locals.
   358  	// For example, in this code,
   359  	//
   360  	//   print(len); len=1; print(len)
   361  	//
   362  	// both occurrences of len refer to the len=1 binding, which
   363  	// completely shadows the predeclared len function.
   364  	//
   365  	// The rationale for these semantics, which differ from Python,
   366  	// is that the static meaning of len (a reference to a global)
   367  	// does not change depending on where it appears in the file.
   368  	// Of course, its dynamic meaning does change, from an error
   369  	// into a valid reference, so it's not clear these semantics
   370  	// have any practical advantage.
   371  	//
   372  	// In any case, the Bazel implementation lags behind the spec
   373  	// and follows Python behavior, so the first use of len refers
   374  	// to the predeclared function.  This typically used in a BUILD
   375  	// file that redefines a predeclared name half way through,
   376  	// for example:
   377  	//
   378  	//	proto_library(...) 			# built-in rule
   379  	//      load("myproto.bzl", "proto_library")
   380  	//	proto_library(...) 			# user-defined rule
   381  	//
   382  	// We will piggyback support for the legacy semantics on the
   383  	// AllowGlobalReassign flag, which is loosely related and also
   384  	// required for Bazel.
   385  	if AllowGlobalReassign && r.env == r.file {
   386  		r.useToplevel(use)
   387  		return
   388  	}
   389  
   390  	b := r.container()
   391  	b.uses = append(b.uses, use)
   392  }
   393  
   394  // useToplevel resolves use.id as a reference to a name visible at top-level.
   395  // The use.env field captures the original environment for error reporting.
   396  func (r *resolver) useToplevel(use use) (bind *Binding) {
   397  	id := use.id
   398  
   399  	if prev, ok := r.file.bindings[id.Name]; ok {
   400  		// use of load-defined name in file block
   401  		bind = prev
   402  	} else if prev, ok := r.globals[id.Name]; ok {
   403  		// use of global declared by module
   404  		bind = prev
   405  	} else if r.isGlobal != nil && r.isGlobal(id.Name) {
   406  		// use of global defined in a previous REPL chunk
   407  		bind = &Binding{
   408  			First: id, // wrong: this is not even a binding use
   409  			Scope: Global,
   410  			Index: len(r.moduleGlobals),
   411  		}
   412  		r.globals[id.Name] = bind
   413  		r.moduleGlobals = append(r.moduleGlobals, bind)
   414  	} else if prev, ok := r.predeclared[id.Name]; ok {
   415  		// repeated use of predeclared or universal
   416  		bind = prev
   417  	} else if r.isPredeclared(id.Name) {
   418  		// use of pre-declared name
   419  		bind = &Binding{Scope: Predeclared}
   420  		r.predeclared[id.Name] = bind // save it
   421  	} else if r.isUniversal(id.Name) {
   422  		// use of universal name
   423  		if !AllowSet && id.Name == "set" {
   424  			r.errorf(id.NamePos, doesnt+"support sets")
   425  		}
   426  		bind = &Binding{Scope: Universal}
   427  		r.predeclared[id.Name] = bind // save it
   428  	} else {
   429  		bind = &Binding{Scope: Undefined}
   430  		var hint string
   431  		if n := r.spellcheck(use); n != "" {
   432  			hint = fmt.Sprintf(" (did you mean %s?)", n)
   433  		}
   434  		r.errorf(id.NamePos, "undefined: %s%s", id.Name, hint)
   435  	}
   436  	id.Binding = bind
   437  	return bind
   438  }
   439  
   440  // spellcheck returns the most likely misspelling of
   441  // the name use.id in the environment use.env.
   442  func (r *resolver) spellcheck(use use) string {
   443  	var names []string
   444  
   445  	// locals
   446  	for b := use.env; b != nil; b = b.parent {
   447  		for name := range b.bindings {
   448  			names = append(names, name)
   449  		}
   450  	}
   451  
   452  	// globals
   453  	//
   454  	// We have no way to enumerate the sets whose membership
   455  	// tests are isPredeclared, isUniverse, and isGlobal,
   456  	// which includes prior names in the REPL session.
   457  	for _, bind := range r.moduleGlobals {
   458  		names = append(names, bind.First.Name)
   459  	}
   460  
   461  	sort.Strings(names)
   462  	return spell.Nearest(use.id.Name, names)
   463  }
   464  
   465  // resolveLocalUses is called when leaving a container (function/module)
   466  // block.  It resolves all uses of locals/cells within that block.
   467  func (b *block) resolveLocalUses() {
   468  	unresolved := b.uses[:0]
   469  	for _, use := range b.uses {
   470  		if bind := lookupLocal(use); bind != nil && (bind.Scope == Local || bind.Scope == Cell) {
   471  			use.id.Binding = bind
   472  		} else {
   473  			unresolved = append(unresolved, use)
   474  		}
   475  	}
   476  	b.uses = unresolved
   477  }
   478  
   479  func (r *resolver) stmts(stmts []syntax.Stmt) {
   480  	for _, stmt := range stmts {
   481  		r.stmt(stmt)
   482  	}
   483  }
   484  
   485  func (r *resolver) stmt(stmt syntax.Stmt) {
   486  	switch stmt := stmt.(type) {
   487  	case *syntax.ExprStmt:
   488  		r.expr(stmt.X)
   489  
   490  	case *syntax.BranchStmt:
   491  		if r.loops == 0 && (stmt.Token == syntax.BREAK || stmt.Token == syntax.CONTINUE) {
   492  			r.errorf(stmt.TokenPos, "%s not in a loop", stmt.Token)
   493  		}
   494  
   495  	case *syntax.IfStmt:
   496  		if !AllowGlobalReassign && r.container().function == nil {
   497  			r.errorf(stmt.If, "if statement not within a function")
   498  		}
   499  		r.expr(stmt.Cond)
   500  		r.ifstmts++
   501  		r.stmts(stmt.True)
   502  		r.stmts(stmt.False)
   503  		r.ifstmts--
   504  
   505  	case *syntax.AssignStmt:
   506  		r.expr(stmt.RHS)
   507  		isAugmented := stmt.Op != syntax.EQ
   508  		r.assign(stmt.LHS, isAugmented)
   509  
   510  	case *syntax.DefStmt:
   511  		r.bind(stmt.Name)
   512  		fn := &Function{
   513  			Name:   stmt.Name.Name,
   514  			Pos:    stmt.Def,
   515  			Params: stmt.Params,
   516  			Body:   stmt.Body,
   517  		}
   518  		stmt.Function = fn
   519  		r.function(fn, stmt.Def)
   520  
   521  	case *syntax.ForStmt:
   522  		if !AllowGlobalReassign && r.container().function == nil {
   523  			r.errorf(stmt.For, "for loop not within a function")
   524  		}
   525  		r.expr(stmt.X)
   526  		const isAugmented = false
   527  		r.assign(stmt.Vars, isAugmented)
   528  		r.loops++
   529  		r.stmts(stmt.Body)
   530  		r.loops--
   531  
   532  	case *syntax.WhileStmt:
   533  		if !AllowRecursion {
   534  			r.errorf(stmt.While, doesnt+"support while loops")
   535  		}
   536  		if !AllowGlobalReassign && r.container().function == nil {
   537  			r.errorf(stmt.While, "while loop not within a function")
   538  		}
   539  		r.expr(stmt.Cond)
   540  		r.loops++
   541  		r.stmts(stmt.Body)
   542  		r.loops--
   543  
   544  	case *syntax.ReturnStmt:
   545  		if r.container().function == nil {
   546  			r.errorf(stmt.Return, "return statement not within a function")
   547  		}
   548  		if stmt.Result != nil {
   549  			r.expr(stmt.Result)
   550  		}
   551  
   552  	case *syntax.LoadStmt:
   553  		// A load statement may not be nested in any other statement.
   554  		if r.container().function != nil {
   555  			r.errorf(stmt.Load, "load statement within a function")
   556  		} else if r.loops > 0 {
   557  			r.errorf(stmt.Load, "load statement within a loop")
   558  		} else if r.ifstmts > 0 {
   559  			r.errorf(stmt.Load, "load statement within a conditional")
   560  		}
   561  
   562  		for i, from := range stmt.From {
   563  			if from.Name == "" {
   564  				r.errorf(from.NamePos, "load: empty identifier")
   565  				continue
   566  			}
   567  			if from.Name[0] == '_' {
   568  				r.errorf(from.NamePos, "load: names with leading underscores are not exported: %s", from.Name)
   569  			}
   570  
   571  			id := stmt.To[i]
   572  			if LoadBindsGlobally {
   573  				r.bind(id)
   574  			} else if r.bindLocal(id) && !AllowGlobalReassign {
   575  				// "Global" in AllowGlobalReassign is a misnomer for "toplevel".
   576  				// Sadly we can't report the previous declaration
   577  				// as id.Binding may not be set yet.
   578  				r.errorf(id.NamePos, "cannot reassign top-level %s", id.Name)
   579  			}
   580  		}
   581  
   582  	default:
   583  		log.Panicf("unexpected stmt %T", stmt)
   584  	}
   585  }
   586  
   587  func (r *resolver) assign(lhs syntax.Expr, isAugmented bool) {
   588  	switch lhs := lhs.(type) {
   589  	case *syntax.Ident:
   590  		// x = ...
   591  		r.bind(lhs)
   592  
   593  	case *syntax.IndexExpr:
   594  		// x[i] = ...
   595  		r.expr(lhs.X)
   596  		r.expr(lhs.Y)
   597  
   598  	case *syntax.DotExpr:
   599  		// x.f = ...
   600  		r.expr(lhs.X)
   601  
   602  	case *syntax.TupleExpr:
   603  		// (x, y) = ...
   604  		if isAugmented {
   605  			r.errorf(syntax.Start(lhs), "can't use tuple expression in augmented assignment")
   606  		}
   607  		for _, elem := range lhs.List {
   608  			r.assign(elem, isAugmented)
   609  		}
   610  
   611  	case *syntax.ListExpr:
   612  		// [x, y, z] = ...
   613  		if isAugmented {
   614  			r.errorf(syntax.Start(lhs), "can't use list expression in augmented assignment")
   615  		}
   616  		for _, elem := range lhs.List {
   617  			r.assign(elem, isAugmented)
   618  		}
   619  
   620  	case *syntax.ParenExpr:
   621  		r.assign(lhs.X, isAugmented)
   622  
   623  	default:
   624  		name := strings.ToLower(strings.TrimPrefix(fmt.Sprintf("%T", lhs), "*syntax."))
   625  		r.errorf(syntax.Start(lhs), "can't assign to %s", name)
   626  	}
   627  }
   628  
   629  func (r *resolver) expr(e syntax.Expr) {
   630  	switch e := e.(type) {
   631  	case *syntax.Ident:
   632  		r.use(e)
   633  
   634  	case *syntax.Literal:
   635  
   636  	case *syntax.ListExpr:
   637  		for _, x := range e.List {
   638  			r.expr(x)
   639  		}
   640  
   641  	case *syntax.CondExpr:
   642  		r.expr(e.Cond)
   643  		r.expr(e.True)
   644  		r.expr(e.False)
   645  
   646  	case *syntax.IndexExpr:
   647  		r.expr(e.X)
   648  		r.expr(e.Y)
   649  
   650  	case *syntax.DictEntry:
   651  		r.expr(e.Key)
   652  		r.expr(e.Value)
   653  
   654  	case *syntax.SliceExpr:
   655  		r.expr(e.X)
   656  		if e.Lo != nil {
   657  			r.expr(e.Lo)
   658  		}
   659  		if e.Hi != nil {
   660  			r.expr(e.Hi)
   661  		}
   662  		if e.Step != nil {
   663  			r.expr(e.Step)
   664  		}
   665  
   666  	case *syntax.Comprehension:
   667  		// The 'in' operand of the first clause (always a ForClause)
   668  		// is resolved in the outer block; consider: [x for x in x].
   669  		clause := e.Clauses[0].(*syntax.ForClause)
   670  		r.expr(clause.X)
   671  
   672  		// A list/dict comprehension defines a new lexical block.
   673  		// Locals defined within the block will be allotted
   674  		// distinct slots in the locals array of the innermost
   675  		// enclosing container (function/module) block.
   676  		r.push(&block{comp: e})
   677  
   678  		const isAugmented = false
   679  		r.assign(clause.Vars, isAugmented)
   680  
   681  		for _, clause := range e.Clauses[1:] {
   682  			switch clause := clause.(type) {
   683  			case *syntax.IfClause:
   684  				r.expr(clause.Cond)
   685  			case *syntax.ForClause:
   686  				r.assign(clause.Vars, isAugmented)
   687  				r.expr(clause.X)
   688  			}
   689  		}
   690  		r.expr(e.Body) // body may be *DictEntry
   691  		r.pop()
   692  
   693  	case *syntax.TupleExpr:
   694  		for _, x := range e.List {
   695  			r.expr(x)
   696  		}
   697  
   698  	case *syntax.DictExpr:
   699  		for _, entry := range e.List {
   700  			entry := entry.(*syntax.DictEntry)
   701  			r.expr(entry.Key)
   702  			r.expr(entry.Value)
   703  		}
   704  
   705  	case *syntax.UnaryExpr:
   706  		r.expr(e.X)
   707  
   708  	case *syntax.BinaryExpr:
   709  		r.expr(e.X)
   710  		r.expr(e.Y)
   711  
   712  	case *syntax.DotExpr:
   713  		r.expr(e.X)
   714  		// ignore e.Name
   715  
   716  	case *syntax.CallExpr:
   717  		r.expr(e.Fn)
   718  		var seenVarargs, seenKwargs bool
   719  		var seenName map[string]bool
   720  		var n, p int
   721  		for _, arg := range e.Args {
   722  			pos, _ := arg.Span()
   723  			if unop, ok := arg.(*syntax.UnaryExpr); ok && unop.Op == syntax.STARSTAR {
   724  				// **kwargs
   725  				if seenKwargs {
   726  					r.errorf(pos, "multiple **kwargs not allowed")
   727  				}
   728  				seenKwargs = true
   729  				r.expr(arg)
   730  			} else if ok && unop.Op == syntax.STAR {
   731  				// *args
   732  				if seenKwargs {
   733  					r.errorf(pos, "*args may not follow **kwargs")
   734  				} else if seenVarargs {
   735  					r.errorf(pos, "multiple *args not allowed")
   736  				}
   737  				seenVarargs = true
   738  				r.expr(arg)
   739  			} else if binop, ok := arg.(*syntax.BinaryExpr); ok && binop.Op == syntax.EQ {
   740  				// k=v
   741  				n++
   742  				if seenKwargs {
   743  					r.errorf(pos, "keyword argument may not follow **kwargs")
   744  				} else if seenVarargs {
   745  					r.errorf(pos, "keyword argument may not follow *args")
   746  				}
   747  				x := binop.X.(*syntax.Ident)
   748  				if seenName[x.Name] {
   749  					r.errorf(x.NamePos, "keyword argument %q is repeated", x.Name)
   750  				} else {
   751  					if seenName == nil {
   752  						seenName = make(map[string]bool)
   753  					}
   754  					seenName[x.Name] = true
   755  				}
   756  				r.expr(binop.Y)
   757  			} else {
   758  				// positional argument
   759  				p++
   760  				if seenVarargs {
   761  					r.errorf(pos, "positional argument may not follow *args")
   762  				} else if seenKwargs {
   763  					r.errorf(pos, "positional argument may not follow **kwargs")
   764  				} else if len(seenName) > 0 {
   765  					r.errorf(pos, "positional argument may not follow named")
   766  				}
   767  				r.expr(arg)
   768  			}
   769  		}
   770  
   771  		// Fail gracefully if compiler-imposed limit is exceeded.
   772  		if p >= 256 {
   773  			pos, _ := e.Span()
   774  			r.errorf(pos, "%v positional arguments in call, limit is 255", p)
   775  		}
   776  		if n >= 256 {
   777  			pos, _ := e.Span()
   778  			r.errorf(pos, "%v keyword arguments in call, limit is 255", n)
   779  		}
   780  
   781  	case *syntax.LambdaExpr:
   782  		fn := &Function{
   783  			Name:   "lambda",
   784  			Pos:    e.Lambda,
   785  			Params: e.Params,
   786  			Body:   []syntax.Stmt{&syntax.ReturnStmt{Result: e.Body}},
   787  		}
   788  		e.Function = fn
   789  		r.function(fn, e.Lambda)
   790  
   791  	case *syntax.ParenExpr:
   792  		r.expr(e.X)
   793  
   794  	default:
   795  		log.Panicf("unexpected expr %T", e)
   796  	}
   797  }
   798  
   799  func (r *resolver) function(function *Function, pos syntax.Position) {
   800  	// Resolve defaults in enclosing environment.
   801  	for _, param := range function.Params {
   802  		if binary, ok := param.(*syntax.BinaryExpr); ok {
   803  			r.expr(binary.Y)
   804  		}
   805  	}
   806  
   807  	// Enter function block.
   808  	b := &block{function: function}
   809  	r.push(b)
   810  
   811  	var seenOptional bool
   812  	var star *syntax.UnaryExpr // * or *args param
   813  	var starStar *syntax.Ident // **kwargs ident
   814  	var numKwonlyParams int
   815  	for _, param := range function.Params {
   816  		switch param := param.(type) {
   817  		case *syntax.Ident:
   818  			// e.g. x
   819  			if starStar != nil {
   820  				r.errorf(param.NamePos, "required parameter may not follow **%s", starStar.Name)
   821  			} else if star != nil {
   822  				numKwonlyParams++
   823  			} else if seenOptional {
   824  				r.errorf(param.NamePos, "required parameter may not follow optional")
   825  			}
   826  			if r.bind(param) {
   827  				r.errorf(param.NamePos, "duplicate parameter: %s", param.Name)
   828  			}
   829  
   830  		case *syntax.BinaryExpr:
   831  			// e.g. y=dflt
   832  			if starStar != nil {
   833  				r.errorf(param.OpPos, "optional parameter may not follow **%s", starStar.Name)
   834  			} else if star != nil {
   835  				numKwonlyParams++
   836  			}
   837  			if id := param.X.(*syntax.Ident); r.bind(id) {
   838  				r.errorf(param.OpPos, "duplicate parameter: %s", id.Name)
   839  			}
   840  			seenOptional = true
   841  
   842  		case *syntax.UnaryExpr:
   843  			// * or *args or **kwargs
   844  			if param.Op == syntax.STAR {
   845  				if starStar != nil {
   846  					r.errorf(param.OpPos, "* parameter may not follow **%s", starStar.Name)
   847  				} else if star != nil {
   848  					r.errorf(param.OpPos, "multiple * parameters not allowed")
   849  				} else {
   850  					star = param
   851  				}
   852  			} else {
   853  				if starStar != nil {
   854  					r.errorf(param.OpPos, "multiple ** parameters not allowed")
   855  				}
   856  				starStar = param.X.(*syntax.Ident)
   857  			}
   858  		}
   859  	}
   860  
   861  	// Bind the *args and **kwargs parameters at the end,
   862  	// so that regular parameters a/b/c are contiguous and
   863  	// there is no hole for the "*":
   864  	//   def f(a, b, *args, c=0, **kwargs)
   865  	//   def f(a, b, *,     c=0, **kwargs)
   866  	if star != nil {
   867  		if id, _ := star.X.(*syntax.Ident); id != nil {
   868  			// *args
   869  			if r.bind(id) {
   870  				r.errorf(id.NamePos, "duplicate parameter: %s", id.Name)
   871  			}
   872  			function.HasVarargs = true
   873  		} else if numKwonlyParams == 0 {
   874  			r.errorf(star.OpPos, "bare * must be followed by keyword-only parameters")
   875  		}
   876  	}
   877  	if starStar != nil {
   878  		if r.bind(starStar) {
   879  			r.errorf(starStar.NamePos, "duplicate parameter: %s", starStar.Name)
   880  		}
   881  		function.HasKwargs = true
   882  	}
   883  
   884  	function.NumKwonlyParams = numKwonlyParams
   885  	r.stmts(function.Body)
   886  
   887  	// Resolve all uses of this function's local vars,
   888  	// and keep just the remaining uses of free/global vars.
   889  	b.resolveLocalUses()
   890  
   891  	// Leave function block.
   892  	r.pop()
   893  
   894  	// References within the function body to globals are not
   895  	// resolved until the end of the module.
   896  }
   897  
   898  func (r *resolver) resolveNonLocalUses(b *block) {
   899  	// First resolve inner blocks.
   900  	for _, child := range b.children {
   901  		r.resolveNonLocalUses(child)
   902  	}
   903  	for _, use := range b.uses {
   904  		use.id.Binding = r.lookupLexical(use, use.env)
   905  	}
   906  }
   907  
   908  // lookupLocal looks up an identifier within its immediately enclosing function.
   909  func lookupLocal(use use) *Binding {
   910  	for env := use.env; env != nil; env = env.parent {
   911  		if bind, ok := env.bindings[use.id.Name]; ok {
   912  			if bind.Scope == Free {
   913  				// shouldn't exist till later
   914  				log.Panicf("%s: internal error: %s, %v", use.id.NamePos, use.id.Name, bind)
   915  			}
   916  			return bind // found
   917  		}
   918  		if env.function != nil {
   919  			break
   920  		}
   921  	}
   922  	return nil // not found in this function
   923  }
   924  
   925  // lookupLexical looks up an identifier use.id within its lexically enclosing environment.
   926  // The use.env field captures the original environment for error reporting.
   927  func (r *resolver) lookupLexical(use use, env *block) (bind *Binding) {
   928  	if debug {
   929  		fmt.Printf("lookupLexical %s in %s = ...\n", use.id.Name, env)
   930  		defer func() { fmt.Printf("= %v\n", bind) }()
   931  	}
   932  
   933  	// Is this the file block?
   934  	if env == r.file {
   935  		return r.useToplevel(use) // file-local, global, predeclared, or not found
   936  	}
   937  
   938  	// Defined in this block?
   939  	bind, ok := env.bindings[use.id.Name]
   940  	if !ok {
   941  		// Defined in parent block?
   942  		bind = r.lookupLexical(use, env.parent)
   943  		if env.function != nil && (bind.Scope == Local || bind.Scope == Free || bind.Scope == Cell) {
   944  			// Found in parent block, which belongs to enclosing function.
   945  			// Add the parent's binding to the function's freevars,
   946  			// and add a new 'free' binding to the inner function's block,
   947  			// and turn the parent's local into cell.
   948  			if bind.Scope == Local {
   949  				bind.Scope = Cell
   950  			}
   951  			index := len(env.function.FreeVars)
   952  			env.function.FreeVars = append(env.function.FreeVars, bind)
   953  			bind = &Binding{
   954  				First: bind.First,
   955  				Scope: Free,
   956  				Index: index,
   957  			}
   958  			if debug {
   959  				fmt.Printf("creating freevar %v in function at %s: %s\n",
   960  					len(env.function.FreeVars), env.function.Pos, use.id.Name)
   961  			}
   962  		}
   963  
   964  		// Memoize, to avoid duplicate free vars
   965  		// and redundant global (failing) lookups.
   966  		env.bind(use.id.Name, bind)
   967  	}
   968  	return bind
   969  }
   970  

View as plain text