resolver.go

Documentation: go/parser

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