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  }
   613
View as plain text