src/go/parser/resolver.go

   1 // Copyright 2021 The Go 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 parser
   6
   7 import (
   8         "fmt"
   9         "go/ast"
  10         "go/token"
  11         "strings"
  12 )
  13
  14 const debugResolve = false
  15
  16 // resolveFile walks the given file to resolve identifiers within the file
  17 // scope, updating ast.Ident.Obj fields with declaration information.
  18 //
  19 // If declErr is non-nil, it is used to report declaration errors during
  20 // resolution. tok is used to format position in error messages.
  21 func resolveFile(file *ast.File, handle *token.File, declErr func(token.Pos, string)) {
  22         pkgScope := ast.NewScope(nil)
  23         r := &resolver{
  24                 handle:   handle,
  25                 declErr:  declErr,
  26                 topScope: pkgScope,
  27                 pkgScope: pkgScope,
  28                 depth:    1,
  29         }
  30
  31         for _, decl := range file.Decls {
  32                 ast.Walk(r, decl)
  33         }
  34
  35         r.closeScope()
  36         assert(r.topScope == nil, "unbalanced scopes")
  37         assert(r.labelScope == nil, "unbalanced label scopes")
  38
  39         // resolve global identifiers within the same file
  40         i := 0
  41         for _, ident := range r.unresolved {
  42                 // i <= index for current ident
  43                 assert(ident.Obj == unresolved, "object already resolved")
  44                 ident.Obj = r.pkgScope.Lookup(ident.Name) // also removes unresolved sentinel
  45                 if ident.Obj == nil {
  46                         r.unresolved[i] = ident
  47                         i++
  48                 } else if debugResolve {
  49                         pos := ident.Obj.Decl.(interface{ Pos() token.Pos }).Pos()
  50                         r.trace("resolved %s@%v to package object %v", ident.Name, ident.Pos(), pos)
  51                 }
  52         }
  53         file.Scope = r.pkgScope
  54         file.Unresolved = r.unresolved[0:i]
  55 }
  56
  57 const maxScopeDepth int = 1e3
  58
  59 type resolver struct {
  60         handle  *token.File
  61         declErr func(token.Pos, string)
  62
  63         // Ordinary identifier scopes
  64         pkgScope   *ast.Scope   // pkgScope.Outer == nil
  65         topScope   *ast.Scope   // top-most scope; may be pkgScope
  66         unresolved []*ast.Ident // unresolved identifiers
  67         depth      int          // scope depth
  68
  69         // Label scopes
  70         // (maintained by open/close LabelScope)
  71         labelScope  *ast.Scope     // label scope for current function
  72         targetStack [][]*ast.Ident // stack of unresolved labels
  73 }
  74
  75 func (r *resolver) trace(format string, args ...any) {
  76         fmt.Println(strings.Repeat(". ", r.depth) + r.sprintf(format, args...))
  77 }
  78
  79 func (r *resolver) sprintf(format string, args ...any) string {
  80         for i, arg := range args {
  81                 switch arg := arg.(type) {
  82                 case token.Pos:
  83                         args[i] = r.handle.Position(arg)
  84                 }
  85         }
  86         return fmt.Sprintf(format, args...)
  87 }
  88
  89 func (r *resolver) openScope(pos token.Pos) {
  90         r.depth++
  91         if r.depth > maxScopeDepth {
  92                 panic(bailout{pos: pos, msg: "exceeded max scope depth during object resolution"})
  93         }
  94         if debugResolve {
  95                 r.trace("opening scope @%v", pos)
  96         }
  97         r.topScope = ast.NewScope(r.topScope)
  98 }
  99
 100 func (r *resolver) closeScope() {
 101         r.depth--
 102         if debugResolve {
 103                 r.trace("closing scope")
 104         }
 105         r.topScope = r.topScope.Outer
 106 }
 107
 108 func (r *resolver) openLabelScope() {
 109         r.labelScope = ast.NewScope(r.labelScope)
 110         r.targetStack = append(r.targetStack, nil)
 111 }
 112
 113 func (r *resolver) closeLabelScope() {
 114         // resolve labels
 115         n := len(r.targetStack) - 1
 116         scope := r.labelScope
 117         for _, ident := range r.targetStack[n] {
 118                 ident.Obj = scope.Lookup(ident.Name)
 119                 if ident.Obj == nil && r.declErr != nil {
 120                         r.declErr(ident.Pos(), fmt.Sprintf("label %s undefined", ident.Name))
 121                 }
 122         }
 123         // pop label scope
 124         r.targetStack = r.targetStack[0:n]
 125         r.labelScope = r.labelScope.Outer
 126 }
 127
 128 func (r *resolver) declare(decl, data any, scope *ast.Scope, kind ast.ObjKind, idents ...*ast.Ident) {
 129         for _, ident := range idents {
 130                 if ident.Obj != nil {
 131                         panic(fmt.Sprintf("%v: identifier %s already declared or resolved", ident.Pos(), ident.Name))
 132                 }
 133                 obj := ast.NewObj(kind, ident.Name)
 134                 // remember the corresponding declaration for redeclaration
 135                 // errors and global variable resolution/typechecking phase
 136                 obj.Decl = decl
 137                 obj.Data = data
 138                 // Identifiers (for receiver type parameters) are written to the scope, but
 139                 // never set as the resolved object. See go.dev/issue/50956.
 140                 if _, ok := decl.(*ast.Ident); !ok {
 141                         ident.Obj = obj
 142                 }
 143                 if ident.Name != "_" {
 144                         if debugResolve {
 145                                 r.trace("declaring %s@%v", ident.Name, ident.Pos())
 146                         }
 147                         if alt := scope.Insert(obj); alt != nil && r.declErr != nil {
 148                                 prevDecl := ""
 149                                 if pos := alt.Pos(); pos.IsValid() {
 150                                         prevDecl = r.sprintf("\n\tprevious declaration at %v", pos)
 151                                 }
 152                                 r.declErr(ident.Pos(), fmt.Sprintf("%s redeclared in this block%s", ident.Name, prevDecl))
 153                         }
 154                 }
 155         }
 156 }
 157
 158 func (r *resolver) shortVarDecl(decl *ast.AssignStmt) {
 159         // Go spec: A short variable declaration may redeclare variables
 160         // provided they were originally declared in the same block with
 161         // the same type, and at least one of the non-blank variables is new.
 162         n := 0 // number of new variables
 163         for _, x := range decl.Lhs {
 164                 if ident, isIdent := x.(*ast.Ident); isIdent {
 165                         assert(ident.Obj == nil, "identifier already declared or resolved")
 166                         obj := ast.NewObj(ast.Var, ident.Name)
 167                         // remember corresponding assignment for other tools
 168                         obj.Decl = decl
 169                         ident.Obj = obj
 170                         if ident.Name != "_" {
 171                                 if debugResolve {
 172                                         r.trace("declaring %s@%v", ident.Name, ident.Pos())
 173                                 }
 174                                 if alt := r.topScope.Insert(obj); alt != nil {
 175                                         ident.Obj = alt // redeclaration
 176                                 } else {
 177                                         n++ // new declaration
 178                                 }
 179                         }
 180                 }
 181         }
 182         if n == 0 && r.declErr != nil {
 183                 r.declErr(decl.Lhs[0].Pos(), "no new variables on left side of :=")
 184         }
 185 }
 186
 187 // The unresolved object is a sentinel to mark identifiers that have been added
 188 // to the list of unresolved identifiers. The sentinel is only used for verifying
 189 // internal consistency.
 190 var unresolved = new(ast.Object)
 191
 192 // If x is an identifier, resolve attempts to resolve x by looking up
 193 // the object it denotes. If no object is found and collectUnresolved is
 194 // set, x is marked as unresolved and collected in the list of unresolved
 195 // identifiers.
 196 func (r *resolver) resolve(ident *ast.Ident, collectUnresolved bool) {
 197         if ident.Obj != nil {
 198                 panic(r.sprintf("%v: identifier %s already declared or resolved", ident.Pos(), ident.Name))
 199         }
 200         // '_' should never refer to existing declarations, because it has special
 201         // handling in the spec.
 202         if ident.Name == "_" {
 203                 return
 204         }
 205         for s := r.topScope; s != nil; s = s.Outer {
 206                 if obj := s.Lookup(ident.Name); obj != nil {
 207                         if debugResolve {
 208                                 r.trace("resolved %v:%s to %v", ident.Pos(), ident.Name, obj)
 209                         }
 210                         assert(obj.Name != "", "obj with no name")
 211                         // Identifiers (for receiver type parameters) are written to the scope,
 212                         // but never set as the resolved object. See go.dev/issue/50956.
 213                         if _, ok := obj.Decl.(*ast.Ident); !ok {
 214                                 ident.Obj = obj
 215                         }
 216                         return
 217                 }
 218         }
 219         // all local scopes are known, so any unresolved identifier
 220         // must be found either in the file scope, package scope
 221         // (perhaps in another file), or universe scope --- collect
 222         // them so that they can be resolved later
 223         if collectUnresolved {
 224                 ident.Obj = unresolved
 225                 r.unresolved = append(r.unresolved, ident)
 226         }
 227 }
 228
 229 func (r *resolver) walkExprs(list []ast.Expr) {
 230         for _, node := range list {
 231                 ast.Walk(r, node)
 232         }
 233 }
 234
 235 func (r *resolver) walkLHS(list []ast.Expr) {
 236         for _, expr := range list {
 237                 expr := ast.Unparen(expr)
 238                 if _, ok := expr.(*ast.Ident); !ok && expr != nil {
 239                         ast.Walk(r, expr)
 240                 }
 241         }
 242 }
 243
 244 func (r *resolver) walkStmts(list []ast.Stmt) {
 245         for _, stmt := range list {
 246                 ast.Walk(r, stmt)
 247         }
 248 }
 249
 250 func (r *resolver) Visit(node ast.Node) ast.Visitor {
 251         if debugResolve && node != nil {
 252                 r.trace("node %T@%v", node, node.Pos())
 253         }
 254
 255         switch n := node.(type) {
 256
 257         // Expressions.
 258         case *ast.Ident:
 259                 r.resolve(n, true)
 260
 261         case *ast.FuncLit:
 262                 r.openScope(n.Pos())
 263                 defer r.closeScope()
 264                 r.walkFuncType(n.Type)
 265                 r.walkBody(n.Body)
 266
 267         case *ast.SelectorExpr:
 268                 ast.Walk(r, n.X)
 269                 // Note: don't try to resolve n.Sel, as we don't support qualified
 270                 // resolution.
 271
 272         case *ast.StructType:
 273                 r.openScope(n.Pos())
 274                 defer r.closeScope()
 275                 r.walkFieldList(n.Fields, ast.Var)
 276
 277         case *ast.FuncType:
 278                 r.openScope(n.Pos())
 279                 defer r.closeScope()
 280                 r.walkFuncType(n)
 281
 282         case *ast.CompositeLit:
 283                 if n.Type != nil {
 284                         ast.Walk(r, n.Type)
 285                 }
 286                 for _, e := range n.Elts {
 287                         if kv, _ := e.(*ast.KeyValueExpr); kv != nil {
 288                                 // See go.dev/issue/45160: try to resolve composite lit keys, but don't
 289                                 // collect them as unresolved if resolution failed. This replicates
 290                                 // existing behavior when resolving during parsing.
 291                                 if ident, _ := kv.Key.(*ast.Ident); ident != nil {
 292                                         r.resolve(ident, false)
 293                                 } else {
 294                                         ast.Walk(r, kv.Key)
 295                                 }
 296                                 ast.Walk(r, kv.Value)
 297                         } else {
 298                                 ast.Walk(r, e)
 299                         }
 300                 }
 301
 302         case *ast.InterfaceType:
 303                 r.openScope(n.Pos())
 304                 defer r.closeScope()
 305                 r.walkFieldList(n.Methods, ast.Fun)
 306
 307         // Statements
 308         case *ast.LabeledStmt:
 309                 r.declare(n, nil, r.labelScope, ast.Lbl, n.Label)
 310                 ast.Walk(r, n.Stmt)
 311
 312         case *ast.AssignStmt:
 313                 r.walkExprs(n.Rhs)
 314                 if n.Tok == token.DEFINE {
 315                         r.shortVarDecl(n)
 316                 } else {
 317                         r.walkExprs(n.Lhs)
 318                 }
 319
 320         case *ast.BranchStmt:
 321                 // add to list of unresolved targets
 322                 if n.Tok != token.FALLTHROUGH && n.Label != nil {
 323                         depth := len(r.targetStack) - 1
 324                         r.targetStack[depth] = append(r.targetStack[depth], n.Label)
 325                 }
 326
 327         case *ast.BlockStmt:
 328                 r.openScope(n.Pos())
 329                 defer r.closeScope()
 330                 r.walkStmts(n.List)
 331
 332         case *ast.IfStmt:
 333                 r.openScope(n.Pos())
 334                 defer r.closeScope()
 335                 if n.Init != nil {
 336                         ast.Walk(r, n.Init)
 337                 }
 338                 ast.Walk(r, n.Cond)
 339                 ast.Walk(r, n.Body)
 340                 if n.Else != nil {
 341                         ast.Walk(r, n.Else)
 342                 }
 343
 344         case *ast.CaseClause:
 345                 r.walkExprs(n.List)
 346                 r.openScope(n.Pos())
 347                 defer r.closeScope()
 348                 r.walkStmts(n.Body)
 349
 350         case *ast.SwitchStmt:
 351                 r.openScope(n.Pos())
 352                 defer r.closeScope()
 353                 if n.Init != nil {
 354                         ast.Walk(r, n.Init)
 355                 }
 356                 if n.Tag != nil {
 357                         // The scope below reproduces some unnecessary behavior of the parser,
 358                         // opening an extra scope in case this is a type switch. It's not needed
 359                         // for expression switches.
 360                         // TODO: remove this once we've matched the parser resolution exactly.
 361                         if n.Init != nil {
 362                                 r.openScope(n.Tag.Pos())
 363                                 defer r.closeScope()
 364                         }
 365                         ast.Walk(r, n.Tag)
 366                 }
 367                 if n.Body != nil {
 368                         r.walkStmts(n.Body.List)
 369                 }
 370
 371         case *ast.TypeSwitchStmt:
 372                 if n.Init != nil {
 373                         r.openScope(n.Pos())
 374                         defer r.closeScope()
 375                         ast.Walk(r, n.Init)
 376                 }
 377                 r.openScope(n.Assign.Pos())
 378                 defer r.closeScope()
 379                 ast.Walk(r, n.Assign)
 380                 // s.Body consists only of case clauses, so does not get its own
 381                 // scope.
 382                 if n.Body != nil {
 383                         r.walkStmts(n.Body.List)
 384                 }
 385
 386         case *ast.CommClause:
 387                 r.openScope(n.Pos())
 388                 defer r.closeScope()
 389                 if n.Comm != nil {
 390                         ast.Walk(r, n.Comm)
 391                 }
 392                 r.walkStmts(n.Body)
 393
 394         case *ast.SelectStmt:
 395                 // as for switch statements, select statement bodies don't get their own
 396                 // scope.
 397                 if n.Body != nil {
 398                         r.walkStmts(n.Body.List)
 399                 }
 400
 401         case *ast.ForStmt:
 402                 r.openScope(n.Pos())
 403                 defer r.closeScope()
 404                 if n.Init != nil {
 405                         ast.Walk(r, n.Init)
 406                 }
 407                 if n.Cond != nil {
 408                         ast.Walk(r, n.Cond)
 409                 }
 410                 if n.Post != nil {
 411                         ast.Walk(r, n.Post)
 412                 }
 413                 ast.Walk(r, n.Body)
 414
 415         case *ast.RangeStmt:
 416                 r.openScope(n.Pos())
 417                 defer r.closeScope()
 418                 ast.Walk(r, n.X)
 419                 var lhs []ast.Expr
 420                 if n.Key != nil {
 421                         lhs = append(lhs, n.Key)
 422                 }
 423                 if n.Value != nil {
 424                         lhs = append(lhs, n.Value)
 425                 }
 426                 if len(lhs) > 0 {
 427                         if n.Tok == token.DEFINE {
 428                                 // Note: we can't exactly match the behavior of object resolution
 429                                 // during the parsing pass here, as it uses the position of the RANGE
 430                                 // token for the RHS OpPos. That information is not contained within
 431                                 // the AST.
 432                                 as := &ast.AssignStmt{
 433                                         Lhs:    lhs,
 434                                         Tok:    token.DEFINE,
 435                                         TokPos: n.TokPos,
 436                                         Rhs:    []ast.Expr{&ast.UnaryExpr{Op: token.RANGE, X: n.X}},
 437                                 }
 438                                 // TODO(rFindley): this walkLHS reproduced the parser resolution, but
 439                                 // is it necessary? By comparison, for a normal AssignStmt we don't
 440                                 // walk the LHS in case there is an invalid identifier list.
 441                                 r.walkLHS(lhs)
 442                                 r.shortVarDecl(as)
 443                         } else {
 444                                 r.walkExprs(lhs)
 445                         }
 446                 }
 447                 ast.Walk(r, n.Body)
 448
 449         // Declarations
 450         case *ast.GenDecl:
 451                 switch n.Tok {
 452                 case token.CONST, token.VAR:
 453                         for i, spec := range n.Specs {
 454                                 spec := spec.(*ast.ValueSpec)
 455                                 kind := ast.Con
 456                                 if n.Tok == token.VAR {
 457                                         kind = ast.Var
 458                                 }
 459                                 r.walkExprs(spec.Values)
 460                                 if spec.Type != nil {
 461                                         ast.Walk(r, spec.Type)
 462                                 }
 463                                 r.declare(spec, i, r.topScope, kind, spec.Names...)
 464                         }
 465                 case token.TYPE:
 466                         for _, spec := range n.Specs {
 467                                 spec := spec.(*ast.TypeSpec)
 468                                 // Go spec: The scope of a type identifier declared inside a function begins
 469                                 // at the identifier in the TypeSpec and ends at the end of the innermost
 470                                 // containing block.
 471                                 r.declare(spec, nil, r.topScope, ast.Typ, spec.Name)
 472                                 if spec.TypeParams != nil {
 473                                         r.openScope(spec.Pos())
 474                                         defer r.closeScope()
 475                                         r.walkTParams(spec.TypeParams)
 476                                 }
 477                                 ast.Walk(r, spec.Type)
 478                         }
 479                 }
 480
 481         case *ast.FuncDecl:
 482                 // Open the function scope.
 483                 r.openScope(n.Pos())
 484                 defer r.closeScope()
 485
 486                 r.walkRecv(n.Recv)
 487
 488                 // Type parameters are walked normally: they can reference each other, and
 489                 // can be referenced by normal parameters.
 490                 if n.Type.TypeParams != nil {
 491                         r.walkTParams(n.Type.TypeParams)
 492                         // TODO(rFindley): need to address receiver type parameters.
 493                 }
 494
 495                 // Resolve and declare parameters in a specific order to get duplicate
 496                 // declaration errors in the correct location.
 497                 r.resolveList(n.Type.Params)
 498                 r.resolveList(n.Type.Results)
 499                 r.declareList(n.Recv, ast.Var)
 500                 r.declareList(n.Type.Params, ast.Var)
 501                 r.declareList(n.Type.Results, ast.Var)
 502
 503                 r.walkBody(n.Body)
 504                 if n.Recv == nil && n.Name.Name != "init" {
 505                         r.declare(n, nil, r.pkgScope, ast.Fun, n.Name)
 506                 }
 507
 508         default:
 509                 return r
 510         }
 511
 512         return nil
 513 }
 514
 515 func (r *resolver) walkFuncType(typ *ast.FuncType) {
 516         // typ.TypeParams must be walked separately for FuncDecls.
 517         r.resolveList(typ.Params)
 518         r.resolveList(typ.Results)
 519         r.declareList(typ.Params, ast.Var)
 520         r.declareList(typ.Results, ast.Var)
 521 }
 522
 523 func (r *resolver) resolveList(list *ast.FieldList) {
 524         if list == nil {
 525                 return
 526         }
 527         for _, f := range list.List {
 528                 if f.Type != nil {
 529                         ast.Walk(r, f.Type)
 530                 }
 531         }
 532 }
 533
 534 func (r *resolver) declareList(list *ast.FieldList, kind ast.ObjKind) {
 535         if list == nil {
 536                 return
 537         }
 538         for _, f := range list.List {
 539                 r.declare(f, nil, r.topScope, kind, f.Names...)
 540         }
 541 }
 542
 543 func (r *resolver) walkRecv(recv *ast.FieldList) {
 544         // If our receiver has receiver type parameters, we must declare them before
 545         // trying to resolve the rest of the receiver, and avoid re-resolving the
 546         // type parameter identifiers.
 547         if recv == nil || len(recv.List) == 0 {
 548                 return // nothing to do
 549         }
 550         typ := recv.List[0].Type
 551         if ptr, ok := typ.(*ast.StarExpr); ok {
 552                 typ = ptr.X
 553         }
 554
 555         var declareExprs []ast.Expr // exprs to declare
 556         var resolveExprs []ast.Expr // exprs to resolve
 557         switch typ := typ.(type) {
 558         case *ast.IndexExpr:
 559                 declareExprs = []ast.Expr{typ.Index}
 560                 resolveExprs = append(resolveExprs, typ.X)
 561         case *ast.IndexListExpr:
 562                 declareExprs = typ.Indices
 563                 resolveExprs = append(resolveExprs, typ.X)
 564         default:
 565                 resolveExprs = append(resolveExprs, typ)
 566         }
 567         for _, expr := range declareExprs {
 568                 if id, _ := expr.(*ast.Ident); id != nil {
 569                         r.declare(expr, nil, r.topScope, ast.Typ, id)
 570                 } else {
 571                         // The receiver type parameter expression is invalid, but try to resolve
 572                         // it anyway for consistency.
 573                         resolveExprs = append(resolveExprs, expr)
 574                 }
 575         }
 576         for _, expr := range resolveExprs {
 577                 if expr != nil {
 578                         ast.Walk(r, expr)
 579                 }
 580         }
 581         // The receiver is invalid, but try to resolve it anyway for consistency.
 582         for _, f := range recv.List[1:] {
 583                 if f.Type != nil {
 584                         ast.Walk(r, f.Type)
 585                 }
 586         }
 587 }
 588
 589 func (r *resolver) walkFieldList(list *ast.FieldList, kind ast.ObjKind) {
 590         if list == nil {
 591                 return
 592         }
 593         r.resolveList(list)
 594         r.declareList(list, kind)
 595 }
 596
 597 // walkTParams is like walkFieldList, but declares type parameters eagerly so
 598 // that they may be resolved in the constraint expressions held in the field
 599 // Type.
 600 func (r *resolver) walkTParams(list *ast.FieldList) {
 601         r.declareList(list, ast.Typ)
 602         r.resolveList(list)
 603 }
 604
 605 func (r *resolver) walkBody(body *ast.BlockStmt) {
 606         if body == nil {
 607                 return
 608         }
 609         r.openLabelScope()
 610         defer r.closeLabelScope()
 611         r.walkStmts(body.List)
 612 }