Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 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 Skylark 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 comprehensions outside any function. Identifiers for global |
| 12 | // variables do not get an index. |
| 13 | package resolve |
| 14 | |
| 15 | // All references to names are statically resolved. Names may be |
alandonovan | a1b28d8 | 2018-03-13 10:59:24 -0400 | [diff] [blame] | 16 | // predeclared, global, or local to a function or module-level comprehension. |
| 17 | // The resolver maps each global name to a small integer and each local |
| 18 | // name to a small integer; these integers enable a fast and compact |
| 19 | // representation of globals and locals in the evaluator. |
| 20 | // |
| 21 | // As an optimization, the resolver classifies each predeclared name as |
| 22 | // either universal (e.g. None, len) or per-module (e.g. glob in Bazel's |
| 23 | // build language), enabling the evaluator to share the representation |
| 24 | // of the universal environment across all modules. |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 25 | // |
| 26 | // The lexical environment is a tree of blocks with the module block at |
| 27 | // its root. The module's child blocks may be of two kinds: functions |
| 28 | // and comprehensions, and these may have further children of either |
| 29 | // kind. |
| 30 | // |
| 31 | // Python-style resolution requires multiple passes because a name is |
| 32 | // determined to be local to a function only if the function contains a |
| 33 | // "binding" use of it, and this use may lexically follow a non-binding |
| 34 | // use. In the first pass, we inspect each function, recording in |
| 35 | // 'uses' each identifier and the environment block in which it occurs. |
| 36 | // If a use of a name is binding, such as a function parameter or |
| 37 | // assignment, we add the name to the block's bindings mapping and add a |
| 38 | // local variable to the enclosing function. |
| 39 | // |
| 40 | // As we finish resolving each function, we inspect all the uses within |
alandonovan | a1b28d8 | 2018-03-13 10:59:24 -0400 | [diff] [blame] | 41 | // that function and discard ones that were found to be local. The |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 42 | // remaining ones must be either free (local to some lexically enclosing |
alandonovan | a1b28d8 | 2018-03-13 10:59:24 -0400 | [diff] [blame] | 43 | // function), or nonlocal (global or predeclared), but we cannot tell |
| 44 | // which until we have finished inspecting the outermost enclosing |
| 45 | // function. At that point, we can distinguish local from global names |
| 46 | // (and this is when Python would compute free variables). |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 47 | // |
| 48 | // However, Skylark additionally requires that all references to global |
| 49 | // names are satisfied by some declaration in the current module; |
| 50 | // Skylark permits a function to forward-reference a global that has not |
| 51 | // been declared yet so long as it is declared before the end of the |
| 52 | // module. So, instead of re-resolving the unresolved references after |
| 53 | // each top-level function, we defer this until the end of the module |
| 54 | // and ensure that all such references are satisfied by some definition. |
| 55 | // |
| 56 | // At the end of the module, we visit each of the nested function blocks |
| 57 | // in bottom-up order, doing a recursive lexical lookup for each |
| 58 | // unresolved name. If the name is found to be local to some enclosing |
| 59 | // function, we must create a DefStmt.FreeVar (capture) parameter for |
| 60 | // each intervening function. We enter these synthetic bindings into |
| 61 | // the bindings map so that we create at most one freevar per name. If |
| 62 | // the name was not local, we check that it was defined at module level. |
| 63 | // |
| 64 | // We resolve all uses of locals in the module (due to comprehensions) |
| 65 | // in a similar way and compute the set of its local variables. |
| 66 | // |
| 67 | // Skylark enforces that all global names are assigned at most once on |
| 68 | // all control flow paths by forbidding if/else statements and loops at |
| 69 | // top level. |
| 70 | // |
| 71 | // TODO(adonovan): opt: reuse local slots once locals go out of scope. |
| 72 | |
| 73 | import ( |
| 74 | "fmt" |
| 75 | "log" |
| 76 | "strings" |
| 77 | |
| 78 | "github.com/google/skylark/syntax" |
| 79 | ) |
| 80 | |
| 81 | const debug = false |
| 82 | const doesnt = "this Skylark dialect does not " |
| 83 | |
| 84 | // global options |
| 85 | // These features are either not standard Skylark (yet), or deprecated |
| 86 | // features of the BUILD language, so we put them behind flags. |
| 87 | var ( |
| 88 | AllowNestedDef = false // allow def statements within function bodies |
| 89 | AllowLambda = false // allow lambda expressions |
| 90 | AllowFloat = false // allow floating point literals, the 'float' built-in, and x / y |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 91 | AllowSet = false // allow the 'set' built-in |
| 92 | AllowGlobalReassign = false // allow reassignment to globals declared in same file (deprecated) |
Hittorp | 0a5e39a | 2018-08-09 15:02:30 +0300 | [diff] [blame] | 93 | AllowBitwise = false // allow bitwise operations (&, |, ^, ~, <<, and >>) |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 94 | ) |
| 95 | |
| 96 | // File resolves the specified file. |
alandonovan | 631f7b5 | 2017-10-11 13:04:47 -0400 | [diff] [blame] | 97 | // |
alandonovan | a1b28d8 | 2018-03-13 10:59:24 -0400 | [diff] [blame] | 98 | // The isPredeclared and isUniversal predicates report whether a name is |
| 99 | // a pre-declared identifier (visible in the current module) or a |
| 100 | // universal identifier (visible in every module). |
| 101 | // Clients should typically pass predeclared.Has for the first and |
| 102 | // skylark.Universe.Has for the second, where predeclared is the |
| 103 | // module's StringDict of predeclared names and skylark.Universe is the |
| 104 | // standard set of built-ins. |
| 105 | // The isUniverse predicate is supplied a parameter to avoid a cyclic |
| 106 | // dependency upon skylark.Universe, not because users should ever need |
| 107 | // to redefine it. |
| 108 | func File(file *syntax.File, isPredeclared, isUniversal func(name string) bool) error { |
| 109 | r := newResolver(isPredeclared, isUniversal) |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 110 | r.stmts(file.Stmts) |
| 111 | |
| 112 | r.env.resolveLocalUses() |
| 113 | |
| 114 | // At the end of the module, resolve all non-local variable references, |
| 115 | // computing closures. |
| 116 | // Function bodies may contain forward references to later global declarations. |
| 117 | r.resolveNonLocalUses(r.env) |
| 118 | |
| 119 | file.Locals = r.moduleLocals |
alandonovan | a1b28d8 | 2018-03-13 10:59:24 -0400 | [diff] [blame] | 120 | file.Globals = r.moduleGlobals |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 121 | |
| 122 | if len(r.errors) > 0 { |
| 123 | return r.errors |
| 124 | } |
| 125 | return nil |
| 126 | } |
| 127 | |
| 128 | // Expr resolves the specified expression. |
| 129 | // It returns the local variables bound within the expression. |
alandonovan | 631f7b5 | 2017-10-11 13:04:47 -0400 | [diff] [blame] | 130 | // |
alandonovan | a1b28d8 | 2018-03-13 10:59:24 -0400 | [diff] [blame] | 131 | // The isPredeclared and isUniversal predicates behave as for the File function. |
| 132 | func Expr(expr syntax.Expr, isPredeclared, isUniversal func(name string) bool) ([]*syntax.Ident, error) { |
| 133 | r := newResolver(isPredeclared, isUniversal) |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 134 | r.expr(expr) |
| 135 | r.env.resolveLocalUses() |
alandonovan | 631f7b5 | 2017-10-11 13:04:47 -0400 | [diff] [blame] | 136 | r.resolveNonLocalUses(r.env) // globals & universals |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 137 | if len(r.errors) > 0 { |
| 138 | return nil, r.errors |
| 139 | } |
| 140 | return r.moduleLocals, nil |
| 141 | } |
| 142 | |
| 143 | // An ErrorList is a non-empty list of resolver error messages. |
| 144 | type ErrorList []Error // len > 0 |
| 145 | |
| 146 | func (e ErrorList) Error() string { return e[0].Error() } |
| 147 | |
| 148 | // An Error describes the nature and position of a resolver error. |
| 149 | type Error struct { |
| 150 | Pos syntax.Position |
| 151 | Msg string |
| 152 | } |
| 153 | |
| 154 | func (e Error) Error() string { return e.Pos.String() + ": " + e.Msg } |
| 155 | |
| 156 | // The Scope of a syntax.Ident indicates what kind of scope it has. |
| 157 | type Scope uint8 |
| 158 | |
| 159 | const ( |
alandonovan | a1b28d8 | 2018-03-13 10:59:24 -0400 | [diff] [blame] | 160 | Undefined Scope = iota // name is not defined |
| 161 | Local // name is local to its function |
| 162 | Free // name is local to some enclosing function |
| 163 | Global // name is global to module |
| 164 | Predeclared // name is predeclared for this module (e.g. glob) |
| 165 | Universal // name is universal (e.g. len) |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 166 | ) |
| 167 | |
| 168 | var scopeNames = [...]string{ |
alandonovan | a1b28d8 | 2018-03-13 10:59:24 -0400 | [diff] [blame] | 169 | Undefined: "undefined", |
| 170 | Local: "local", |
| 171 | Free: "free", |
| 172 | Global: "global", |
| 173 | Predeclared: "predeclared", |
| 174 | Universal: "universal", |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 175 | } |
| 176 | |
| 177 | func (scope Scope) String() string { return scopeNames[scope] } |
| 178 | |
alandonovan | a1b28d8 | 2018-03-13 10:59:24 -0400 | [diff] [blame] | 179 | func newResolver(isPredeclared, isUniversal func(name string) bool) *resolver { |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 180 | return &resolver{ |
alandonovan | a1b28d8 | 2018-03-13 10:59:24 -0400 | [diff] [blame] | 181 | env: new(block), // module block |
| 182 | isPredeclared: isPredeclared, |
| 183 | isUniversal: isUniversal, |
| 184 | globals: make(map[string]*syntax.Ident), |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 185 | } |
| 186 | } |
| 187 | |
| 188 | type resolver struct { |
| 189 | // env is the current local environment: |
| 190 | // a linked list of blocks, innermost first. |
| 191 | // The tail of the list is the module block. |
| 192 | env *block |
| 193 | |
| 194 | // moduleLocals contains the local variables of the module |
| 195 | // (due to comprehensions outside any function). |
alandonovan | a1b28d8 | 2018-03-13 10:59:24 -0400 | [diff] [blame] | 196 | // moduleGlobals contains the global variables of the module. |
| 197 | moduleLocals []*syntax.Ident |
| 198 | moduleGlobals []*syntax.Ident |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 199 | |
alandonovan | a1b28d8 | 2018-03-13 10:59:24 -0400 | [diff] [blame] | 200 | // globals maps each global name in the module |
| 201 | // to its first binding occurrence. |
| 202 | globals map[string]*syntax.Ident |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 203 | |
| 204 | // These predicates report whether a name is |
alandonovan | a1b28d8 | 2018-03-13 10:59:24 -0400 | [diff] [blame] | 205 | // pre-declared, either in this module or universally. |
| 206 | isPredeclared, isUniversal func(name string) bool |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 207 | |
| 208 | loops int // number of enclosing for loops |
| 209 | |
| 210 | errors ErrorList |
| 211 | } |
| 212 | |
| 213 | // container returns the innermost enclosing "container" block: |
| 214 | // a function (function != nil) or module (function == nil). |
| 215 | // Container blocks accumulate local variable bindings. |
| 216 | func (r *resolver) container() *block { |
| 217 | for b := r.env; ; b = b.parent { |
| 218 | if b.function != nil || b.isModule() { |
| 219 | return b |
| 220 | } |
| 221 | } |
| 222 | } |
| 223 | |
| 224 | func (r *resolver) push(b *block) { |
| 225 | r.env.children = append(r.env.children, b) |
| 226 | b.parent = r.env |
| 227 | r.env = b |
| 228 | } |
| 229 | |
| 230 | func (r *resolver) pop() { r.env = r.env.parent } |
| 231 | |
| 232 | type block struct { |
| 233 | parent *block // nil for module block |
| 234 | |
| 235 | // In the module (root) block, both these fields are nil. |
| 236 | function *syntax.Function // only for function blocks |
| 237 | comp *syntax.Comprehension // only for comprehension blocks |
| 238 | |
| 239 | // bindings maps a name to its binding. |
| 240 | // A local binding has an index into its innermost enclosing container's locals array. |
| 241 | // A free binding has an index into its innermost enclosing function's freevars array. |
| 242 | bindings map[string]binding |
| 243 | |
| 244 | // children records the child blocks of the current one. |
| 245 | children []*block |
| 246 | |
| 247 | // uses records all identifiers seen in this container (function or module), |
| 248 | // and a reference to the environment in which they appear. |
| 249 | // As we leave each container block, we resolve them, |
| 250 | // so that only free and global ones remain. |
| 251 | // At the end of each top-level function we compute closures. |
| 252 | uses []use |
| 253 | } |
| 254 | |
| 255 | type binding struct { |
| 256 | scope Scope |
| 257 | index int |
| 258 | } |
| 259 | |
| 260 | func (b *block) isModule() bool { return b.parent == nil } |
| 261 | |
| 262 | func (b *block) bind(name string, bind binding) { |
| 263 | if b.bindings == nil { |
| 264 | b.bindings = make(map[string]binding) |
| 265 | } |
| 266 | b.bindings[name] = bind |
| 267 | } |
| 268 | |
| 269 | func (b *block) String() string { |
| 270 | if b.function != nil { |
| 271 | return "function block at " + fmt.Sprint(b.function.Span()) |
| 272 | } |
| 273 | if b.comp != nil { |
alandonovan | 5b0e788 | 2018-08-10 13:44:17 -0400 | [diff] [blame^] | 274 | return "comprehension block at " + fmt.Sprint(b.comp.Span()) |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 275 | } |
| 276 | return "module block" |
| 277 | } |
| 278 | |
| 279 | func (r *resolver) errorf(posn syntax.Position, format string, args ...interface{}) { |
| 280 | r.errors = append(r.errors, Error{posn, fmt.Sprintf(format, args...)}) |
| 281 | } |
| 282 | |
| 283 | // A use records an identifier and the environment in which it appears. |
| 284 | type use struct { |
| 285 | id *syntax.Ident |
| 286 | env *block |
| 287 | } |
| 288 | |
| 289 | // bind creates a binding for id in the current block, |
| 290 | // if there is not one already, and reports an error if |
| 291 | // a global was re-bound and allowRebind is false. |
| 292 | // It returns whether a binding already existed. |
| 293 | func (r *resolver) bind(id *syntax.Ident, allowRebind bool) bool { |
| 294 | // Binding outside any local (comprehension/function) block? |
| 295 | if r.env.isModule() { |
alandonovan | a1b28d8 | 2018-03-13 10:59:24 -0400 | [diff] [blame] | 296 | id.Scope = uint8(Global) |
| 297 | prev, ok := r.globals[id.Name] |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 298 | if ok { |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 299 | // Global reassignments are permitted only if |
| 300 | // they are of the form x += y. We can't tell |
| 301 | // statically whether it's a reassignment |
| 302 | // (e.g. int += int) or a mutation (list += list). |
| 303 | if !allowRebind && !AllowGlobalReassign { |
alandonovan | a1b28d8 | 2018-03-13 10:59:24 -0400 | [diff] [blame] | 304 | r.errorf(id.NamePos, "cannot reassign global %s declared at %s", id.Name, prev.NamePos) |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 305 | } |
alandonovan | a1b28d8 | 2018-03-13 10:59:24 -0400 | [diff] [blame] | 306 | id.Index = prev.Index |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 307 | } else { |
alandonovan | a1b28d8 | 2018-03-13 10:59:24 -0400 | [diff] [blame] | 308 | // first global binding of this name |
| 309 | r.globals[id.Name] = id |
| 310 | id.Index = len(r.moduleGlobals) |
| 311 | r.moduleGlobals = append(r.moduleGlobals, id) |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 312 | } |
| 313 | return ok |
| 314 | } |
| 315 | |
| 316 | // Mark this name as local to current block. |
| 317 | // Assign it a new local (positive) index in the current container. |
| 318 | _, ok := r.env.bindings[id.Name] |
| 319 | if !ok { |
| 320 | var locals *[]*syntax.Ident |
| 321 | if fn := r.container().function; fn != nil { |
| 322 | locals = &fn.Locals |
| 323 | } else { |
| 324 | locals = &r.moduleLocals |
| 325 | } |
| 326 | r.env.bind(id.Name, binding{Local, len(*locals)}) |
| 327 | *locals = append(*locals, id) |
| 328 | } |
| 329 | |
| 330 | r.use(id) |
| 331 | return ok |
| 332 | } |
| 333 | |
| 334 | func (r *resolver) use(id *syntax.Ident) { |
| 335 | // Reference outside any local (comprehension/function) block? |
| 336 | if r.env.isModule() { |
| 337 | r.useGlobal(id) |
| 338 | return |
| 339 | } |
| 340 | |
| 341 | b := r.container() |
| 342 | b.uses = append(b.uses, use{id, r.env}) |
| 343 | } |
| 344 | |
alandonovan | a1b28d8 | 2018-03-13 10:59:24 -0400 | [diff] [blame] | 345 | func (r *resolver) useGlobal(id *syntax.Ident) binding { |
| 346 | var scope Scope |
| 347 | if prev, ok := r.globals[id.Name]; ok { |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 348 | scope = Global // use of global declared by module |
alandonovan | a1b28d8 | 2018-03-13 10:59:24 -0400 | [diff] [blame] | 349 | id.Index = prev.Index |
| 350 | } else if r.isPredeclared(id.Name) { |
| 351 | scope = Predeclared // use of pre-declared |
alandonovan | 631f7b5 | 2017-10-11 13:04:47 -0400 | [diff] [blame] | 352 | } else if r.isUniversal(id.Name) { |
| 353 | scope = Universal // use of universal name |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 354 | if !AllowFloat && id.Name == "float" { |
| 355 | r.errorf(id.NamePos, doesnt+"support floating point") |
| 356 | } |
| 357 | if !AllowSet && id.Name == "set" { |
| 358 | r.errorf(id.NamePos, doesnt+"support sets") |
| 359 | } |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 360 | } else { |
| 361 | scope = Undefined |
| 362 | r.errorf(id.NamePos, "undefined: %s", id.Name) |
| 363 | } |
| 364 | id.Scope = uint8(scope) |
alandonovan | a1b28d8 | 2018-03-13 10:59:24 -0400 | [diff] [blame] | 365 | return binding{scope, id.Index} |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 366 | } |
| 367 | |
| 368 | // resolveLocalUses is called when leaving a container (function/module) |
| 369 | // block. It resolves all uses of locals within that block. |
| 370 | func (b *block) resolveLocalUses() { |
| 371 | unresolved := b.uses[:0] |
| 372 | for _, use := range b.uses { |
| 373 | if bind := lookupLocal(use); bind.scope == Local { |
| 374 | use.id.Scope = uint8(bind.scope) |
| 375 | use.id.Index = bind.index |
| 376 | } else { |
| 377 | unresolved = append(unresolved, use) |
| 378 | } |
| 379 | } |
| 380 | b.uses = unresolved |
| 381 | } |
| 382 | |
| 383 | func (r *resolver) stmts(stmts []syntax.Stmt) { |
| 384 | for _, stmt := range stmts { |
| 385 | r.stmt(stmt) |
| 386 | } |
| 387 | } |
| 388 | |
| 389 | func (r *resolver) stmt(stmt syntax.Stmt) { |
| 390 | switch stmt := stmt.(type) { |
| 391 | case *syntax.ExprStmt: |
| 392 | r.expr(stmt.X) |
| 393 | |
| 394 | case *syntax.BranchStmt: |
| 395 | if r.loops == 0 && (stmt.Token == syntax.BREAK || stmt.Token == syntax.CONTINUE) { |
| 396 | r.errorf(stmt.TokenPos, "%s not in a loop", stmt.Token) |
| 397 | } |
| 398 | |
| 399 | case *syntax.IfStmt: |
| 400 | if r.container().function == nil { |
| 401 | r.errorf(stmt.If, "if statement not within a function") |
| 402 | } |
| 403 | r.expr(stmt.Cond) |
| 404 | r.stmts(stmt.True) |
| 405 | r.stmts(stmt.False) |
| 406 | |
| 407 | case *syntax.AssignStmt: |
Hittorp | 0a5e39a | 2018-08-09 15:02:30 +0300 | [diff] [blame] | 408 | if !AllowBitwise { |
| 409 | switch stmt.Op { |
| 410 | case syntax.AMP_EQ, syntax.PIPE_EQ, syntax.CIRCUMFLEX_EQ, syntax.LTLT_EQ, syntax.GTGT_EQ: |
| 411 | r.errorf(stmt.OpPos, doesnt+"support bitwise operations") |
| 412 | } |
| 413 | } |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 414 | r.expr(stmt.RHS) |
| 415 | // x += y may be a re-binding of a global variable, |
| 416 | // but we cannot tell without knowing the type of x. |
| 417 | // (If x is a list it's equivalent to x.extend(y).) |
| 418 | // The use is conservatively treated as binding, |
| 419 | // but we suppress the error if it's an already-bound global. |
| 420 | isAugmented := stmt.Op != syntax.EQ |
| 421 | r.assign(stmt.LHS, isAugmented) |
| 422 | |
| 423 | case *syntax.DefStmt: |
| 424 | if !AllowNestedDef && r.container().function != nil { |
| 425 | r.errorf(stmt.Def, doesnt+"support nested def") |
| 426 | } |
| 427 | const allowRebind = false |
| 428 | r.bind(stmt.Name, allowRebind) |
| 429 | r.function(stmt.Def, stmt.Name.Name, &stmt.Function) |
| 430 | |
| 431 | case *syntax.ForStmt: |
| 432 | if r.container().function == nil { |
| 433 | r.errorf(stmt.For, "for loop not within a function") |
| 434 | } |
| 435 | r.expr(stmt.X) |
| 436 | const allowRebind = false |
| 437 | r.assign(stmt.Vars, allowRebind) |
| 438 | r.loops++ |
| 439 | r.stmts(stmt.Body) |
| 440 | r.loops-- |
| 441 | |
| 442 | case *syntax.ReturnStmt: |
| 443 | if r.container().function == nil { |
| 444 | r.errorf(stmt.Return, "return statement not within a function") |
| 445 | } |
| 446 | if stmt.Result != nil { |
| 447 | r.expr(stmt.Result) |
| 448 | } |
| 449 | |
| 450 | case *syntax.LoadStmt: |
| 451 | if r.container().function != nil { |
| 452 | r.errorf(stmt.Load, "load statement within a function") |
| 453 | } |
| 454 | |
| 455 | const allowRebind = false |
| 456 | for i, from := range stmt.From { |
| 457 | if from.Name == "" { |
| 458 | r.errorf(from.NamePos, "load: empty identifier") |
| 459 | continue |
| 460 | } |
| 461 | if from.Name[0] == '_' { |
| 462 | r.errorf(from.NamePos, "load: names with leading underscores are not exported: %s", from.Name) |
| 463 | } |
| 464 | r.bind(stmt.To[i], allowRebind) |
| 465 | } |
| 466 | |
| 467 | default: |
| 468 | log.Fatalf("unexpected stmt %T", stmt) |
| 469 | } |
| 470 | } |
| 471 | |
| 472 | func (r *resolver) assign(lhs syntax.Expr, isAugmented bool) { |
| 473 | switch lhs := lhs.(type) { |
| 474 | case *syntax.Ident: |
| 475 | // x = ... |
| 476 | allowRebind := isAugmented |
| 477 | r.bind(lhs, allowRebind) |
| 478 | |
| 479 | case *syntax.IndexExpr: |
| 480 | // x[i] = ... |
| 481 | r.expr(lhs.X) |
| 482 | r.expr(lhs.Y) |
| 483 | |
| 484 | case *syntax.DotExpr: |
| 485 | // x.f = ... |
| 486 | r.expr(lhs.X) |
| 487 | |
| 488 | case *syntax.TupleExpr: |
| 489 | // (x, y) = ... |
| 490 | if len(lhs.List) == 0 { |
| 491 | r.errorf(syntax.Start(lhs), "can't assign to ()") |
| 492 | } |
| 493 | if isAugmented { |
| 494 | r.errorf(syntax.Start(lhs), "can't use tuple expression in augmented assignment") |
| 495 | } |
| 496 | for _, elem := range lhs.List { |
| 497 | r.assign(elem, isAugmented) |
| 498 | } |
| 499 | |
| 500 | case *syntax.ListExpr: |
| 501 | // [x, y, z] = ... |
| 502 | if len(lhs.List) == 0 { |
| 503 | r.errorf(syntax.Start(lhs), "can't assign to []") |
| 504 | } |
| 505 | if isAugmented { |
| 506 | r.errorf(syntax.Start(lhs), "can't use list expression in augmented assignment") |
| 507 | } |
| 508 | for _, elem := range lhs.List { |
| 509 | r.assign(elem, isAugmented) |
| 510 | } |
| 511 | |
Laurent Le Brun | 28ceca7 | 2018-02-26 15:01:53 +0100 | [diff] [blame] | 512 | case *syntax.ParenExpr: |
| 513 | r.assign(lhs.X, isAugmented) |
| 514 | |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 515 | default: |
| 516 | name := strings.ToLower(strings.TrimPrefix(fmt.Sprintf("%T", lhs), "*syntax.")) |
| 517 | r.errorf(syntax.Start(lhs), "can't assign to %s", name) |
| 518 | } |
| 519 | } |
| 520 | |
| 521 | func (r *resolver) expr(e syntax.Expr) { |
| 522 | switch e := e.(type) { |
| 523 | case *syntax.Ident: |
| 524 | r.use(e) |
| 525 | |
| 526 | case *syntax.Literal: |
| 527 | if !AllowFloat && e.Token == syntax.FLOAT { |
| 528 | r.errorf(e.TokenPos, doesnt+"support floating point") |
| 529 | } |
| 530 | |
| 531 | case *syntax.ListExpr: |
| 532 | for _, x := range e.List { |
| 533 | r.expr(x) |
| 534 | } |
| 535 | |
| 536 | case *syntax.CondExpr: |
| 537 | r.expr(e.Cond) |
| 538 | r.expr(e.True) |
| 539 | r.expr(e.False) |
| 540 | |
| 541 | case *syntax.IndexExpr: |
| 542 | r.expr(e.X) |
| 543 | r.expr(e.Y) |
| 544 | |
| 545 | case *syntax.DictEntry: |
| 546 | r.expr(e.Key) |
| 547 | r.expr(e.Value) |
| 548 | |
| 549 | case *syntax.SliceExpr: |
| 550 | r.expr(e.X) |
| 551 | if e.Lo != nil { |
| 552 | r.expr(e.Lo) |
| 553 | } |
| 554 | if e.Hi != nil { |
| 555 | r.expr(e.Hi) |
| 556 | } |
| 557 | if e.Step != nil { |
| 558 | r.expr(e.Step) |
| 559 | } |
| 560 | |
| 561 | case *syntax.Comprehension: |
alandonovan | 0d5491b | 2018-03-30 10:42:13 -0400 | [diff] [blame] | 562 | // The 'in' operand of the first clause (always a ForClause) |
| 563 | // is resolved in the outer block; consider: [x for x in x]. |
| 564 | clause := e.Clauses[0].(*syntax.ForClause) |
| 565 | r.expr(clause.X) |
| 566 | |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 567 | // A list/dict comprehension defines a new lexical block. |
| 568 | // Locals defined within the block will be allotted |
| 569 | // distinct slots in the locals array of the innermost |
| 570 | // enclosing container (function/module) block. |
| 571 | r.push(&block{comp: e}) |
alandonovan | 0d5491b | 2018-03-30 10:42:13 -0400 | [diff] [blame] | 572 | |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 573 | const allowRebind = false |
alandonovan | 0d5491b | 2018-03-30 10:42:13 -0400 | [diff] [blame] | 574 | r.assign(clause.Vars, allowRebind) |
| 575 | |
| 576 | for _, clause := range e.Clauses[1:] { |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 577 | switch clause := clause.(type) { |
| 578 | case *syntax.IfClause: |
| 579 | r.expr(clause.Cond) |
| 580 | case *syntax.ForClause: |
| 581 | r.assign(clause.Vars, allowRebind) |
| 582 | r.expr(clause.X) |
| 583 | } |
| 584 | } |
| 585 | r.expr(e.Body) // body may be *DictEntry |
| 586 | r.pop() |
| 587 | |
| 588 | case *syntax.TupleExpr: |
| 589 | for _, x := range e.List { |
| 590 | r.expr(x) |
| 591 | } |
| 592 | |
| 593 | case *syntax.DictExpr: |
| 594 | for _, entry := range e.List { |
| 595 | entry := entry.(*syntax.DictEntry) |
| 596 | r.expr(entry.Key) |
| 597 | r.expr(entry.Value) |
| 598 | } |
| 599 | |
| 600 | case *syntax.UnaryExpr: |
Hittorp | 0a5e39a | 2018-08-09 15:02:30 +0300 | [diff] [blame] | 601 | if !AllowBitwise && e.Op == syntax.TILDE { |
| 602 | r.errorf(e.OpPos, doesnt+"support bitwise operations") |
| 603 | } |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 604 | r.expr(e.X) |
| 605 | |
| 606 | case *syntax.BinaryExpr: |
| 607 | if !AllowFloat && e.Op == syntax.SLASH { |
| 608 | r.errorf(e.OpPos, doesnt+"support floating point (use //)") |
| 609 | } |
Hittorp | 0a5e39a | 2018-08-09 15:02:30 +0300 | [diff] [blame] | 610 | if !AllowBitwise { |
| 611 | switch e.Op { |
| 612 | case syntax.AMP, syntax.PIPE, syntax.CIRCUMFLEX, syntax.LTLT, syntax.GTGT: |
| 613 | r.errorf(e.OpPos, doesnt+"support bitwise operations") |
| 614 | } |
| 615 | } |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 616 | r.expr(e.X) |
| 617 | r.expr(e.Y) |
| 618 | |
| 619 | case *syntax.DotExpr: |
| 620 | r.expr(e.X) |
| 621 | // ignore e.Name |
| 622 | |
| 623 | case *syntax.CallExpr: |
| 624 | r.expr(e.Fn) |
Alan Donovan | 1b9d0e7 | 2017-11-28 14:19:10 -0500 | [diff] [blame] | 625 | var seenVarargs, seenKwargs, seenNamed bool |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 626 | for _, arg := range e.Args { |
| 627 | pos, _ := arg.Span() |
| 628 | if unop, ok := arg.(*syntax.UnaryExpr); ok && unop.Op == syntax.STARSTAR { |
| 629 | // **kwargs |
| 630 | if seenKwargs { |
| 631 | r.errorf(pos, "multiple **kwargs not allowed") |
| 632 | } |
| 633 | seenKwargs = true |
| 634 | r.expr(arg) |
| 635 | } else if ok && unop.Op == syntax.STAR { |
| 636 | // *args |
| 637 | if seenKwargs { |
| 638 | r.errorf(pos, "*args may not follow **kwargs") |
| 639 | } else if seenVarargs { |
| 640 | r.errorf(pos, "multiple *args not allowed") |
| 641 | } |
| 642 | seenVarargs = true |
| 643 | r.expr(arg) |
| 644 | } else if binop, ok := arg.(*syntax.BinaryExpr); ok && binop.Op == syntax.EQ { |
| 645 | // k=v |
| 646 | if seenKwargs { |
| 647 | r.errorf(pos, "argument may not follow **kwargs") |
| 648 | } |
| 649 | // ignore binop.X |
| 650 | r.expr(binop.Y) |
Alan Donovan | 1b9d0e7 | 2017-11-28 14:19:10 -0500 | [diff] [blame] | 651 | seenNamed = true |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 652 | } else { |
| 653 | // positional argument |
| 654 | if seenVarargs { |
| 655 | r.errorf(pos, "argument may not follow *args") |
| 656 | } else if seenKwargs { |
| 657 | r.errorf(pos, "argument may not follow **kwargs") |
Alan Donovan | 1b9d0e7 | 2017-11-28 14:19:10 -0500 | [diff] [blame] | 658 | } else if seenNamed { |
| 659 | r.errorf(pos, "positional argument may not follow named") |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 660 | } |
| 661 | r.expr(arg) |
| 662 | } |
| 663 | } |
| 664 | |
| 665 | case *syntax.LambdaExpr: |
| 666 | if !AllowLambda { |
| 667 | r.errorf(e.Lambda, doesnt+"support lambda") |
| 668 | } |
| 669 | r.function(e.Lambda, "lambda", &e.Function) |
| 670 | |
Laurent Le Brun | 28ceca7 | 2018-02-26 15:01:53 +0100 | [diff] [blame] | 671 | case *syntax.ParenExpr: |
| 672 | r.expr(e.X) |
| 673 | |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 674 | default: |
| 675 | log.Fatalf("unexpected expr %T", e) |
| 676 | } |
| 677 | } |
| 678 | |
| 679 | func (r *resolver) function(pos syntax.Position, name string, function *syntax.Function) { |
| 680 | // Resolve defaults in enclosing environment. |
| 681 | for _, param := range function.Params { |
| 682 | if binary, ok := param.(*syntax.BinaryExpr); ok { |
| 683 | r.expr(binary.Y) |
| 684 | } |
| 685 | } |
| 686 | |
| 687 | // Enter function block. |
| 688 | b := &block{function: function} |
| 689 | r.push(b) |
| 690 | |
| 691 | const allowRebind = false |
Alan Donovan | 1b9d0e7 | 2017-11-28 14:19:10 -0500 | [diff] [blame] | 692 | var seenVarargs, seenKwargs, seenOptional bool |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 693 | for _, param := range function.Params { |
| 694 | switch param := param.(type) { |
| 695 | case *syntax.Ident: |
| 696 | // e.g. x |
| 697 | if seenKwargs { |
| 698 | r.errorf(pos, "parameter may not follow **kwargs") |
| 699 | } else if seenVarargs { |
| 700 | r.errorf(pos, "parameter may not follow *args") |
Alan Donovan | 1b9d0e7 | 2017-11-28 14:19:10 -0500 | [diff] [blame] | 701 | } else if seenOptional { |
| 702 | r.errorf(pos, "required parameter may not follow optional") |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 703 | } |
| 704 | if r.bind(param, allowRebind) { |
| 705 | r.errorf(pos, "duplicate parameter: %s", param.Name) |
| 706 | } |
| 707 | |
| 708 | case *syntax.BinaryExpr: |
| 709 | // e.g. y=dflt |
| 710 | if seenKwargs { |
| 711 | r.errorf(pos, "parameter may not follow **kwargs") |
| 712 | } else if seenVarargs { |
| 713 | r.errorf(pos, "parameter may not follow *args") |
| 714 | } |
| 715 | if id := param.X.(*syntax.Ident); r.bind(id, allowRebind) { |
| 716 | r.errorf(pos, "duplicate parameter: %s", id.Name) |
| 717 | } |
Alan Donovan | 1b9d0e7 | 2017-11-28 14:19:10 -0500 | [diff] [blame] | 718 | seenOptional = true |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 719 | |
| 720 | case *syntax.UnaryExpr: |
| 721 | // *args or **kwargs |
| 722 | if param.Op == syntax.STAR { |
| 723 | if seenKwargs { |
| 724 | r.errorf(pos, "*args may not follow **kwargs") |
| 725 | } else if seenVarargs { |
| 726 | r.errorf(pos, "multiple *args not allowed") |
| 727 | } |
| 728 | seenVarargs = true |
| 729 | } else { |
| 730 | if seenKwargs { |
| 731 | r.errorf(pos, "multiple **kwargs not allowed") |
| 732 | } |
| 733 | seenKwargs = true |
| 734 | } |
| 735 | if id := param.X.(*syntax.Ident); r.bind(id, allowRebind) { |
| 736 | r.errorf(pos, "duplicate parameter: %s", id.Name) |
| 737 | } |
| 738 | } |
| 739 | } |
| 740 | function.HasVarargs = seenVarargs |
| 741 | function.HasKwargs = seenKwargs |
| 742 | r.stmts(function.Body) |
| 743 | |
| 744 | // Resolve all uses of this function's local vars, |
| 745 | // and keep just the remaining uses of free/global vars. |
| 746 | b.resolveLocalUses() |
| 747 | |
| 748 | // Leave function block. |
| 749 | r.pop() |
| 750 | |
| 751 | // References within the function body to globals are not |
| 752 | // resolved until the end of the module. |
| 753 | } |
| 754 | |
| 755 | func (r *resolver) resolveNonLocalUses(b *block) { |
| 756 | // First resolve inner blocks. |
| 757 | for _, child := range b.children { |
| 758 | r.resolveNonLocalUses(child) |
| 759 | } |
| 760 | for _, use := range b.uses { |
| 761 | bind := r.lookupLexical(use.id, use.env) |
| 762 | use.id.Scope = uint8(bind.scope) |
| 763 | use.id.Index = bind.index |
| 764 | } |
| 765 | } |
| 766 | |
| 767 | // lookupLocal looks up an identifier within its immediately enclosing function. |
| 768 | func lookupLocal(use use) binding { |
| 769 | for env := use.env; env != nil; env = env.parent { |
| 770 | if bind, ok := env.bindings[use.id.Name]; ok { |
| 771 | if bind.scope == Free { |
| 772 | // shouldn't exist till later |
| 773 | log.Fatalf("%s: internal error: %s, %d", use.id.NamePos, use.id.Name, bind) |
| 774 | } |
| 775 | return bind // found |
| 776 | } |
| 777 | if env.function != nil { |
| 778 | break |
| 779 | } |
| 780 | } |
| 781 | return binding{} // not found in this function |
| 782 | } |
| 783 | |
| 784 | // lookupLexical looks up an identifier within its lexically enclosing environment. |
| 785 | func (r *resolver) lookupLexical(id *syntax.Ident, env *block) (bind binding) { |
| 786 | if debug { |
| 787 | fmt.Printf("lookupLexical %s in %s = ...\n", id.Name, env) |
| 788 | defer func() { fmt.Printf("= %d\n", bind) }() |
| 789 | } |
| 790 | |
| 791 | // Is this the module block? |
| 792 | if env.isModule() { |
alandonovan | a1b28d8 | 2018-03-13 10:59:24 -0400 | [diff] [blame] | 793 | return r.useGlobal(id) // global, predeclared, or not found |
Alan Donovan | 312d1a5 | 2017-10-02 10:10:28 -0400 | [diff] [blame] | 794 | } |
| 795 | |
| 796 | // Defined in this block? |
| 797 | bind, ok := env.bindings[id.Name] |
| 798 | if !ok { |
| 799 | // Defined in parent block? |
| 800 | bind = r.lookupLexical(id, env.parent) |
| 801 | if env.function != nil && (bind.scope == Local || bind.scope == Free) { |
| 802 | // Found in parent block, which belongs to enclosing function. |
| 803 | id := &syntax.Ident{ |
| 804 | Name: id.Name, |
| 805 | Scope: uint8(bind.scope), |
| 806 | Index: bind.index, |
| 807 | } |
| 808 | bind.scope = Free |
| 809 | bind.index = len(env.function.FreeVars) |
| 810 | env.function.FreeVars = append(env.function.FreeVars, id) |
| 811 | if debug { |
| 812 | fmt.Printf("creating freevar %v in function at %s: %s\n", |
| 813 | len(env.function.FreeVars), fmt.Sprint(env.function.Span()), id.Name) |
| 814 | } |
| 815 | } |
| 816 | |
| 817 | // Memoize, to avoid duplicate free vars |
| 818 | // and redundant global (failing) lookups. |
| 819 | env.bind(id.Name, bind) |
| 820 | } |
| 821 | return bind |
| 822 | } |