diff options
Diffstat (limited to 'resolve/resolve.go')
| -rw-r--r-- | resolve/resolve.go | 969 |
1 files changed, 969 insertions, 0 deletions
diff --git a/resolve/resolve.go b/resolve/resolve.go new file mode 100644 index 0000000..56e33ba --- /dev/null +++ b/resolve/resolve.go @@ -0,0 +1,969 @@ +// Copyright 2017 The Bazel Authors. All rights reserved. +// Use of this source code is governed by a BSD-style +// license that can be found in the LICENSE file. + +// Package resolve defines a name-resolution pass for Starlark abstract +// syntax trees. +// +// The resolver sets the Locals and FreeVars arrays of each DefStmt and +// the LocalIndex field of each syntax.Ident that refers to a local or +// free variable. It also sets the Locals array of a File for locals +// bound by top-level comprehensions and load statements. +// Identifiers for global variables do not get an index. +package resolve // import "go.starlark.net/resolve" + +// All references to names are statically resolved. Names may be +// predeclared, global, or local to a function or file. +// File-local variables include those bound by top-level comprehensions +// and by load statements. ("Top-level" means "outside of any function".) +// The resolver maps each global name to a small integer and each local +// name to a small integer; these integers enable a fast and compact +// representation of globals and locals in the evaluator. +// +// As an optimization, the resolver classifies each predeclared name as +// either universal (e.g. None, len) or per-module (e.g. glob in Bazel's +// build language), enabling the evaluator to share the representation +// of the universal environment across all modules. +// +// The lexical environment is a tree of blocks with the file block at +// its root. The file's child blocks may be of two kinds: functions +// and comprehensions, and these may have further children of either +// kind. +// +// Python-style resolution requires multiple passes because a name is +// determined to be local to a function only if the function contains a +// "binding" use of it; similarly, a name is determined to be global (as +// opposed to predeclared) if the module contains a top-level binding use. +// Unlike ordinary top-level assignments, the bindings created by load +// statements are local to the file block. +// A non-binding use may lexically precede the binding to which it is resolved. +// In the first pass, we inspect each function, recording in +// 'uses' each identifier and the environment block in which it occurs. +// If a use of a name is binding, such as a function parameter or +// assignment, we add the name to the block's bindings mapping and add a +// local variable to the enclosing function. +// +// As we finish resolving each function, we inspect all the uses within +// that function and discard ones that were found to be function-local. The +// remaining ones must be either free (local to some lexically enclosing +// function), or top-level (global, predeclared, or file-local), but we cannot tell +// which until we have finished inspecting the outermost enclosing +// function. At that point, we can distinguish local from top-level names +// (and this is when Python would compute free variables). +// +// However, Starlark additionally requires that all references to global +// names are satisfied by some declaration in the current module; +// Starlark permits a function to forward-reference a global or file-local +// that has not +// been declared yet so long as it is declared before the end of the +// module. So, instead of re-resolving the unresolved references after +// each top-level function, we defer this until the end of the module +// and ensure that all such references are satisfied by some definition. +// +// At the end of the module, we visit each of the nested function blocks +// in bottom-up order, doing a recursive lexical lookup for each +// unresolved name. If the name is found to be local to some enclosing +// function, we must create a DefStmt.FreeVar (capture) parameter for +// each intervening function. We enter these synthetic bindings into +// the bindings map so that we create at most one freevar per name. If +// the name was not local, we check that it was defined at module level. +// +// We resolve all uses of locals in the module (due to load statements +// and comprehensions) in a similar way and compute the file's set of +// local variables. +// +// Starlark enforces that all global names are assigned at most once on +// all control flow paths by forbidding if/else statements and loops at +// top level. A global may be used before it is defined, leading to a +// dynamic error. However, the AllowGlobalReassign flag (really: allow +// top-level reassign) makes the resolver allow multiple to a variable +// at top-level. It also allows if-, for-, and while-loops at top-level, +// which in turn may make the evaluator dynamically assign multiple +// values to a variable at top-level. (These two roles should be separated.) + +import ( + "fmt" + "log" + "sort" + "strings" + + "go.starlark.net/internal/spell" + "go.starlark.net/syntax" +) + +const debug = false +const doesnt = "this Starlark dialect does not " + +// global options +// These features are either not standard Starlark (yet), or deprecated +// features of the BUILD language, so we put them behind flags. +var ( + AllowSet = false // allow the 'set' built-in + AllowGlobalReassign = false // allow reassignment to top-level names; also, allow if/for/while at top-level + AllowRecursion = false // allow while statements and recursive functions + LoadBindsGlobally = false // load creates global not file-local bindings (deprecated) + + // obsolete flags for features that are now standard. No effect. + AllowNestedDef = true + AllowLambda = true + AllowFloat = true + AllowBitwise = true +) + +// File resolves the specified file and records information about the +// module in file.Module. +// +// The isPredeclared and isUniversal predicates report whether a name is +// a pre-declared identifier (visible in the current module) or a +// universal identifier (visible in every module). +// Clients should typically pass predeclared.Has for the first and +// starlark.Universe.Has for the second, where predeclared is the +// module's StringDict of predeclared names and starlark.Universe is the +// standard set of built-ins. +// The isUniverse predicate is supplied a parameter to avoid a cyclic +// dependency upon starlark.Universe, not because users should ever need +// to redefine it. +func File(file *syntax.File, isPredeclared, isUniversal func(name string) bool) error { + return REPLChunk(file, nil, isPredeclared, isUniversal) +} + +// REPLChunk is a generalization of the File function that supports a +// non-empty initial global block, as occurs in a REPL. +func REPLChunk(file *syntax.File, isGlobal, isPredeclared, isUniversal func(name string) bool) error { + r := newResolver(isGlobal, isPredeclared, isUniversal) + r.stmts(file.Stmts) + + r.env.resolveLocalUses() + + // At the end of the module, resolve all non-local variable references, + // computing closures. + // Function bodies may contain forward references to later global declarations. + r.resolveNonLocalUses(r.env) + + file.Module = &Module{ + Locals: r.moduleLocals, + Globals: r.moduleGlobals, + } + + if len(r.errors) > 0 { + return r.errors + } + return nil +} + +// Expr resolves the specified expression. +// It returns the local variables bound within the expression. +// +// The isPredeclared and isUniversal predicates behave as for the File function. +func Expr(expr syntax.Expr, isPredeclared, isUniversal func(name string) bool) ([]*Binding, error) { + r := newResolver(nil, isPredeclared, isUniversal) + r.expr(expr) + r.env.resolveLocalUses() + r.resolveNonLocalUses(r.env) // globals & universals + if len(r.errors) > 0 { + return nil, r.errors + } + return r.moduleLocals, nil +} + +// An ErrorList is a non-empty list of resolver error messages. +type ErrorList []Error // len > 0 + +func (e ErrorList) Error() string { return e[0].Error() } + +// An Error describes the nature and position of a resolver error. +type Error struct { + Pos syntax.Position + Msg string +} + +func (e Error) Error() string { return e.Pos.String() + ": " + e.Msg } + +func newResolver(isGlobal, isPredeclared, isUniversal func(name string) bool) *resolver { + file := new(block) + return &resolver{ + file: file, + env: file, + isGlobal: isGlobal, + isPredeclared: isPredeclared, + isUniversal: isUniversal, + globals: make(map[string]*Binding), + predeclared: make(map[string]*Binding), + } +} + +type resolver struct { + // env is the current local environment: + // a linked list of blocks, innermost first. + // The tail of the list is the file block. + env *block + file *block // file block (contains load bindings) + + // moduleLocals contains the local variables of the module + // (due to load statements and comprehensions outside any function). + // moduleGlobals contains the global variables of the module. + moduleLocals []*Binding + moduleGlobals []*Binding + + // globals maps each global name in the module to its binding. + // predeclared does the same for predeclared and universal names. + globals map[string]*Binding + predeclared map[string]*Binding + + // These predicates report whether a name is + // pre-declared, either in this module or universally, + // or already declared in the module globals (as in a REPL). + // isGlobal may be nil. + isGlobal, isPredeclared, isUniversal func(name string) bool + + loops int // number of enclosing for/while loops + ifstmts int // number of enclosing if statements loops + + errors ErrorList +} + +// container returns the innermost enclosing "container" block: +// a function (function != nil) or file (function == nil). +// Container blocks accumulate local variable bindings. +func (r *resolver) container() *block { + for b := r.env; ; b = b.parent { + if b.function != nil || b == r.file { + return b + } + } +} + +func (r *resolver) push(b *block) { + r.env.children = append(r.env.children, b) + b.parent = r.env + r.env = b +} + +func (r *resolver) pop() { r.env = r.env.parent } + +type block struct { + parent *block // nil for file block + + // In the file (root) block, both these fields are nil. + function *Function // only for function blocks + comp *syntax.Comprehension // only for comprehension blocks + + // bindings maps a name to its binding. + // A local binding has an index into its innermost enclosing container's locals array. + // A free binding has an index into its innermost enclosing function's freevars array. + bindings map[string]*Binding + + // children records the child blocks of the current one. + children []*block + + // uses records all identifiers seen in this container (function or file), + // and a reference to the environment in which they appear. + // As we leave each container block, we resolve them, + // so that only free and global ones remain. + // At the end of each top-level function we compute closures. + uses []use +} + +func (b *block) bind(name string, bind *Binding) { + if b.bindings == nil { + b.bindings = make(map[string]*Binding) + } + b.bindings[name] = bind +} + +func (b *block) String() string { + if b.function != nil { + return "function block at " + fmt.Sprint(b.function.Pos) + } + if b.comp != nil { + return "comprehension block at " + fmt.Sprint(b.comp.Span()) + } + return "file block" +} + +func (r *resolver) errorf(posn syntax.Position, format string, args ...interface{}) { + r.errors = append(r.errors, Error{posn, fmt.Sprintf(format, args...)}) +} + +// A use records an identifier and the environment in which it appears. +type use struct { + id *syntax.Ident + env *block +} + +// bind creates a binding for id: a global (not file-local) +// binding at top-level, a local binding otherwise. +// At top-level, it reports an error if a global or file-local +// binding already exists, unless AllowGlobalReassign. +// It sets id.Binding to the binding (whether old or new), +// and returns whether a binding already existed. +func (r *resolver) bind(id *syntax.Ident) bool { + // Binding outside any local (comprehension/function) block? + if r.env == r.file { + bind, ok := r.file.bindings[id.Name] + if !ok { + bind, ok = r.globals[id.Name] + if !ok { + // first global binding of this name + bind = &Binding{ + First: id, + Scope: Global, + Index: len(r.moduleGlobals), + } + r.globals[id.Name] = bind + r.moduleGlobals = append(r.moduleGlobals, bind) + } + } + if ok && !AllowGlobalReassign { + r.errorf(id.NamePos, "cannot reassign %s %s declared at %s", + bind.Scope, id.Name, bind.First.NamePos) + } + id.Binding = bind + return ok + } + + return r.bindLocal(id) +} + +func (r *resolver) bindLocal(id *syntax.Ident) bool { + // Mark this name as local to current block. + // Assign it a new local (positive) index in the current container. + _, ok := r.env.bindings[id.Name] + if !ok { + var locals *[]*Binding + if fn := r.container().function; fn != nil { + locals = &fn.Locals + } else { + locals = &r.moduleLocals + } + bind := &Binding{ + First: id, + Scope: Local, + Index: len(*locals), + } + r.env.bind(id.Name, bind) + *locals = append(*locals, bind) + } + + r.use(id) + return ok +} + +func (r *resolver) use(id *syntax.Ident) { + use := use{id, r.env} + + // The spec says that if there is a global binding of a name + // then all references to that name in that block refer to the + // global, even if the use precedes the def---just as for locals. + // For example, in this code, + // + // print(len); len=1; print(len) + // + // both occurrences of len refer to the len=1 binding, which + // completely shadows the predeclared len function. + // + // The rationale for these semantics, which differ from Python, + // is that the static meaning of len (a reference to a global) + // does not change depending on where it appears in the file. + // Of course, its dynamic meaning does change, from an error + // into a valid reference, so it's not clear these semantics + // have any practical advantage. + // + // In any case, the Bazel implementation lags behind the spec + // and follows Python behavior, so the first use of len refers + // to the predeclared function. This typically used in a BUILD + // file that redefines a predeclared name half way through, + // for example: + // + // proto_library(...) # built-in rule + // load("myproto.bzl", "proto_library") + // proto_library(...) # user-defined rule + // + // We will piggyback support for the legacy semantics on the + // AllowGlobalReassign flag, which is loosely related and also + // required for Bazel. + if AllowGlobalReassign && r.env == r.file { + r.useToplevel(use) + return + } + + b := r.container() + b.uses = append(b.uses, use) +} + +// useToplevel resolves use.id as a reference to a name visible at top-level. +// The use.env field captures the original environment for error reporting. +func (r *resolver) useToplevel(use use) (bind *Binding) { + id := use.id + + if prev, ok := r.file.bindings[id.Name]; ok { + // use of load-defined name in file block + bind = prev + } else if prev, ok := r.globals[id.Name]; ok { + // use of global declared by module + bind = prev + } else if r.isGlobal != nil && r.isGlobal(id.Name) { + // use of global defined in a previous REPL chunk + bind = &Binding{ + First: id, // wrong: this is not even a binding use + Scope: Global, + Index: len(r.moduleGlobals), + } + r.globals[id.Name] = bind + r.moduleGlobals = append(r.moduleGlobals, bind) + } else if prev, ok := r.predeclared[id.Name]; ok { + // repeated use of predeclared or universal + bind = prev + } else if r.isPredeclared(id.Name) { + // use of pre-declared name + bind = &Binding{Scope: Predeclared} + r.predeclared[id.Name] = bind // save it + } else if r.isUniversal(id.Name) { + // use of universal name + if !AllowSet && id.Name == "set" { + r.errorf(id.NamePos, doesnt+"support sets") + } + bind = &Binding{Scope: Universal} + r.predeclared[id.Name] = bind // save it + } else { + bind = &Binding{Scope: Undefined} + var hint string + if n := r.spellcheck(use); n != "" { + hint = fmt.Sprintf(" (did you mean %s?)", n) + } + r.errorf(id.NamePos, "undefined: %s%s", id.Name, hint) + } + id.Binding = bind + return bind +} + +// spellcheck returns the most likely misspelling of +// the name use.id in the environment use.env. +func (r *resolver) spellcheck(use use) string { + var names []string + + // locals + for b := use.env; b != nil; b = b.parent { + for name := range b.bindings { + names = append(names, name) + } + } + + // globals + // + // We have no way to enumerate the sets whose membership + // tests are isPredeclared, isUniverse, and isGlobal, + // which includes prior names in the REPL session. + for _, bind := range r.moduleGlobals { + names = append(names, bind.First.Name) + } + + sort.Strings(names) + return spell.Nearest(use.id.Name, names) +} + +// resolveLocalUses is called when leaving a container (function/module) +// 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 == Local || bind.Scope == Cell) { + use.id.Binding = bind + } else { + unresolved = append(unresolved, use) + } + } + b.uses = unresolved +} + +func (r *resolver) stmts(stmts []syntax.Stmt) { + for _, stmt := range stmts { + r.stmt(stmt) + } +} + +func (r *resolver) stmt(stmt syntax.Stmt) { + switch stmt := stmt.(type) { + case *syntax.ExprStmt: + r.expr(stmt.X) + + case *syntax.BranchStmt: + if r.loops == 0 && (stmt.Token == syntax.BREAK || stmt.Token == syntax.CONTINUE) { + r.errorf(stmt.TokenPos, "%s not in a loop", stmt.Token) + } + + case *syntax.IfStmt: + if !AllowGlobalReassign && r.container().function == nil { + r.errorf(stmt.If, "if statement not within a function") + } + r.expr(stmt.Cond) + r.ifstmts++ + r.stmts(stmt.True) + r.stmts(stmt.False) + r.ifstmts-- + + case *syntax.AssignStmt: + r.expr(stmt.RHS) + isAugmented := stmt.Op != syntax.EQ + r.assign(stmt.LHS, isAugmented) + + case *syntax.DefStmt: + r.bind(stmt.Name) + fn := &Function{ + Name: stmt.Name.Name, + Pos: stmt.Def, + Params: stmt.Params, + Body: stmt.Body, + } + stmt.Function = fn + r.function(fn, stmt.Def) + + case *syntax.ForStmt: + if !AllowGlobalReassign && r.container().function == nil { + r.errorf(stmt.For, "for loop not within a function") + } + r.expr(stmt.X) + const isAugmented = false + r.assign(stmt.Vars, isAugmented) + r.loops++ + r.stmts(stmt.Body) + r.loops-- + + case *syntax.WhileStmt: + if !AllowRecursion { + r.errorf(stmt.While, doesnt+"support while loops") + } + if !AllowGlobalReassign && r.container().function == nil { + r.errorf(stmt.While, "while loop not within a function") + } + r.expr(stmt.Cond) + r.loops++ + r.stmts(stmt.Body) + r.loops-- + + case *syntax.ReturnStmt: + if r.container().function == nil { + r.errorf(stmt.Return, "return statement not within a function") + } + if stmt.Result != nil { + r.expr(stmt.Result) + } + + case *syntax.LoadStmt: + // A load statement may not be nested in any other statement. + if r.container().function != nil { + r.errorf(stmt.Load, "load statement within a function") + } else if r.loops > 0 { + r.errorf(stmt.Load, "load statement within a loop") + } else if r.ifstmts > 0 { + r.errorf(stmt.Load, "load statement within a conditional") + } + + for i, from := range stmt.From { + if from.Name == "" { + r.errorf(from.NamePos, "load: empty identifier") + continue + } + if from.Name[0] == '_' { + r.errorf(from.NamePos, "load: names with leading underscores are not exported: %s", from.Name) + } + + id := stmt.To[i] + if LoadBindsGlobally { + r.bind(id) + } else if r.bindLocal(id) && !AllowGlobalReassign { + // "Global" in AllowGlobalReassign is a misnomer for "toplevel". + // Sadly we can't report the previous declaration + // as id.Binding may not be set yet. + r.errorf(id.NamePos, "cannot reassign top-level %s", id.Name) + } + } + + default: + log.Panicf("unexpected stmt %T", stmt) + } +} + +func (r *resolver) assign(lhs syntax.Expr, isAugmented bool) { + switch lhs := lhs.(type) { + case *syntax.Ident: + // x = ... + r.bind(lhs) + + case *syntax.IndexExpr: + // x[i] = ... + r.expr(lhs.X) + r.expr(lhs.Y) + + case *syntax.DotExpr: + // x.f = ... + r.expr(lhs.X) + + case *syntax.TupleExpr: + // (x, y) = ... + if isAugmented { + r.errorf(syntax.Start(lhs), "can't use tuple expression in augmented assignment") + } + for _, elem := range lhs.List { + r.assign(elem, isAugmented) + } + + case *syntax.ListExpr: + // [x, y, z] = ... + if isAugmented { + r.errorf(syntax.Start(lhs), "can't use list expression in augmented assignment") + } + for _, elem := range lhs.List { + r.assign(elem, isAugmented) + } + + case *syntax.ParenExpr: + r.assign(lhs.X, isAugmented) + + default: + name := strings.ToLower(strings.TrimPrefix(fmt.Sprintf("%T", lhs), "*syntax.")) + r.errorf(syntax.Start(lhs), "can't assign to %s", name) + } +} + +func (r *resolver) expr(e syntax.Expr) { + switch e := e.(type) { + case *syntax.Ident: + r.use(e) + + case *syntax.Literal: + + case *syntax.ListExpr: + for _, x := range e.List { + r.expr(x) + } + + case *syntax.CondExpr: + r.expr(e.Cond) + r.expr(e.True) + r.expr(e.False) + + case *syntax.IndexExpr: + r.expr(e.X) + r.expr(e.Y) + + case *syntax.DictEntry: + r.expr(e.Key) + r.expr(e.Value) + + case *syntax.SliceExpr: + r.expr(e.X) + if e.Lo != nil { + r.expr(e.Lo) + } + if e.Hi != nil { + r.expr(e.Hi) + } + if e.Step != nil { + r.expr(e.Step) + } + + case *syntax.Comprehension: + // The 'in' operand of the first clause (always a ForClause) + // is resolved in the outer block; consider: [x for x in x]. + clause := e.Clauses[0].(*syntax.ForClause) + r.expr(clause.X) + + // A list/dict comprehension defines a new lexical block. + // Locals defined within the block will be allotted + // distinct slots in the locals array of the innermost + // enclosing container (function/module) block. + r.push(&block{comp: e}) + + const isAugmented = false + r.assign(clause.Vars, isAugmented) + + for _, clause := range e.Clauses[1:] { + switch clause := clause.(type) { + case *syntax.IfClause: + r.expr(clause.Cond) + case *syntax.ForClause: + r.assign(clause.Vars, isAugmented) + r.expr(clause.X) + } + } + r.expr(e.Body) // body may be *DictEntry + r.pop() + + case *syntax.TupleExpr: + for _, x := range e.List { + r.expr(x) + } + + case *syntax.DictExpr: + for _, entry := range e.List { + entry := entry.(*syntax.DictEntry) + r.expr(entry.Key) + r.expr(entry.Value) + } + + case *syntax.UnaryExpr: + r.expr(e.X) + + case *syntax.BinaryExpr: + r.expr(e.X) + r.expr(e.Y) + + case *syntax.DotExpr: + r.expr(e.X) + // ignore e.Name + + case *syntax.CallExpr: + r.expr(e.Fn) + var seenVarargs, seenKwargs bool + var seenName map[string]bool + var n, p int + for _, arg := range e.Args { + pos, _ := arg.Span() + if unop, ok := arg.(*syntax.UnaryExpr); ok && unop.Op == syntax.STARSTAR { + // **kwargs + if seenKwargs { + r.errorf(pos, "multiple **kwargs not allowed") + } + seenKwargs = true + r.expr(arg) + } else if ok && unop.Op == syntax.STAR { + // *args + if seenKwargs { + r.errorf(pos, "*args may not follow **kwargs") + } else if seenVarargs { + r.errorf(pos, "multiple *args not allowed") + } + seenVarargs = true + r.expr(arg) + } else if binop, ok := arg.(*syntax.BinaryExpr); ok && binop.Op == syntax.EQ { + // k=v + n++ + if seenKwargs { + r.errorf(pos, "keyword argument may not follow **kwargs") + } else if seenVarargs { + r.errorf(pos, "keyword argument may not follow *args") + } + x := binop.X.(*syntax.Ident) + if seenName[x.Name] { + r.errorf(x.NamePos, "keyword argument %s repeated", x.Name) + } else { + if seenName == nil { + seenName = make(map[string]bool) + } + seenName[x.Name] = true + } + r.expr(binop.Y) + } else { + // positional argument + p++ + if seenVarargs { + r.errorf(pos, "positional argument may not follow *args") + } else if seenKwargs { + r.errorf(pos, "positional argument may not follow **kwargs") + } else if len(seenName) > 0 { + r.errorf(pos, "positional argument may not follow named") + } + r.expr(arg) + } + } + + // Fail gracefully if compiler-imposed limit is exceeded. + if p >= 256 { + pos, _ := e.Span() + r.errorf(pos, "%v positional arguments in call, limit is 255", p) + } + if n >= 256 { + pos, _ := e.Span() + r.errorf(pos, "%v keyword arguments in call, limit is 255", n) + } + + case *syntax.LambdaExpr: + fn := &Function{ + Name: "lambda", + Pos: e.Lambda, + Params: e.Params, + Body: []syntax.Stmt{&syntax.ReturnStmt{Result: e.Body}}, + } + e.Function = fn + r.function(fn, e.Lambda) + + case *syntax.ParenExpr: + r.expr(e.X) + + default: + log.Panicf("unexpected expr %T", e) + } +} + +func (r *resolver) function(function *Function, pos syntax.Position) { + // Resolve defaults in enclosing environment. + for _, param := range function.Params { + if binary, ok := param.(*syntax.BinaryExpr); ok { + r.expr(binary.Y) + } + } + + // Enter function block. + b := &block{function: function} + r.push(b) + + var seenOptional bool + var star *syntax.UnaryExpr // * or *args param + var starStar *syntax.Ident // **kwargs ident + var numKwonlyParams int + for _, param := range function.Params { + switch param := param.(type) { + case *syntax.Ident: + // e.g. x + if starStar != nil { + r.errorf(param.NamePos, "required parameter may not follow **%s", starStar.Name) + } else if star != nil { + numKwonlyParams++ + } else if seenOptional { + r.errorf(param.NamePos, "required parameter may not follow optional") + } + if r.bind(param) { + r.errorf(param.NamePos, "duplicate parameter: %s", param.Name) + } + + case *syntax.BinaryExpr: + // e.g. y=dflt + if starStar != nil { + r.errorf(param.OpPos, "optional parameter may not follow **%s", starStar.Name) + } else if star != nil { + numKwonlyParams++ + } + if id := param.X.(*syntax.Ident); r.bind(id) { + r.errorf(param.OpPos, "duplicate parameter: %s", id.Name) + } + seenOptional = true + + case *syntax.UnaryExpr: + // * or *args or **kwargs + if param.Op == syntax.STAR { + if starStar != nil { + r.errorf(param.OpPos, "* parameter may not follow **%s", starStar.Name) + } else if star != nil { + r.errorf(param.OpPos, "multiple * parameters not allowed") + } else { + star = param + } + } else { + if starStar != nil { + r.errorf(param.OpPos, "multiple ** parameters not allowed") + } + starStar = param.X.(*syntax.Ident) + } + } + } + + // Bind the *args and **kwargs parameters at the end, + // so that regular parameters a/b/c are contiguous and + // there is no hole for the "*": + // def f(a, b, *args, c=0, **kwargs) + // def f(a, b, *, c=0, **kwargs) + if star != nil { + if id, _ := star.X.(*syntax.Ident); id != nil { + // *args + if r.bind(id) { + r.errorf(id.NamePos, "duplicate parameter: %s", id.Name) + } + function.HasVarargs = true + } else if numKwonlyParams == 0 { + r.errorf(star.OpPos, "bare * must be followed by keyword-only parameters") + } + } + if starStar != nil { + if r.bind(starStar) { + r.errorf(starStar.NamePos, "duplicate parameter: %s", starStar.Name) + } + function.HasKwargs = true + } + + function.NumKwonlyParams = numKwonlyParams + r.stmts(function.Body) + + // Resolve all uses of this function's local vars, + // and keep just the remaining uses of free/global vars. + b.resolveLocalUses() + + // Leave function block. + r.pop() + + // References within the function body to globals are not + // resolved until the end of the module. +} + +func (r *resolver) resolveNonLocalUses(b *block) { + // First resolve inner blocks. + for _, child := range b.children { + r.resolveNonLocalUses(child) + } + for _, use := range b.uses { + use.id.Binding = r.lookupLexical(use, use.env) + } +} + +// lookupLocal looks up an identifier within its immediately enclosing function. +func lookupLocal(use use) *Binding { + for env := use.env; env != nil; env = env.parent { + if bind, ok := env.bindings[use.id.Name]; ok { + if bind.Scope == Free { + // shouldn't exist till later + log.Panicf("%s: internal error: %s, %v", use.id.NamePos, use.id.Name, bind) + } + return bind // found + } + if env.function != nil { + break + } + } + return nil // not found in this function +} + +// lookupLexical looks up an identifier use.id within its lexically enclosing environment. +// The use.env field captures the original environment for error reporting. +func (r *resolver) lookupLexical(use use, env *block) (bind *Binding) { + if debug { + fmt.Printf("lookupLexical %s in %s = ...\n", use.id.Name, env) + defer func() { fmt.Printf("= %v\n", bind) }() + } + + // Is this the file block? + if env == r.file { + return r.useToplevel(use) // file-local, global, predeclared, or not found + } + + // Defined in this block? + bind, ok := env.bindings[use.id.Name] + if !ok { + // Defined in parent block? + bind = r.lookupLexical(use, env.parent) + if env.function != nil && (bind.Scope == Local || bind.Scope == Free || bind.Scope == Cell) { + // 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 turn the parent's local into cell. + if bind.Scope == Local { + bind.Scope = Cell + } + index := len(env.function.FreeVars) + env.function.FreeVars = append(env.function.FreeVars, bind) + bind = &Binding{ + First: bind.First, + Scope: Free, + Index: index, + } + if debug { + fmt.Printf("creating freevar %v in function at %s: %s\n", + len(env.function.FreeVars), env.function.Pos, use.id.Name) + } + } + + // Memoize, to avoid duplicate free vars + // and redundant global (failing) lookups. + env.bind(use.id.Name, bind) + } + return bind +} |