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