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  		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.dump("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) dump(format string, args ...interface{}) {
		76  	fmt.Println(">>> " + r.sprintf(format, args...))
		77  }
		78  
		79  func (r *resolver) sprintf(format string, args ...interface{}) 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.dump("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.dump("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 interface{}, scope *ast.Scope, kind ast.ObjKind, idents ...*ast.Ident) {
	 129  	for _, ident := range idents {
	 130  		// "type" is used for type lists in interfaces, and is otherwise an invalid
	 131  		// identifier. The 'type' identifier is also artificially duplicated in the
	 132  		// type list, so could cause panics below if we were to proceed.
	 133  		if ident.Name == "type" {
	 134  			continue
	 135  		}
	 136  		assert(ident.Obj == nil, "identifier already declared or resolved")
	 137  		obj := ast.NewObj(kind, ident.Name)
	 138  		// remember the corresponding declaration for redeclaration
	 139  		// errors and global variable resolution/typechecking phase
	 140  		obj.Decl = decl
	 141  		obj.Data = data
	 142  		ident.Obj = obj
	 143  		if ident.Name != "_" {
	 144  			if debugResolve {
	 145  				r.dump("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 = fmt.Sprintf("\n\tprevious declaration at %s", r.handle.Position(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.dump("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  //
	 197  func (r *resolver) resolve(ident *ast.Ident, collectUnresolved bool) {
	 198  	if ident.Obj != nil {
	 199  		panic(fmt.Sprintf("%s: identifier %s already declared or resolved", r.handle.Position(ident.Pos()), ident.Name))
	 200  	}
	 201  	// '_' and 'type' should never refer to existing declarations: '_' because it
	 202  	// has special handling in the spec, and 'type' because it is a keyword, and
	 203  	// only valid in an interface type list.
	 204  	if ident.Name == "_" || ident.Name == "type" {
	 205  		return
	 206  	}
	 207  	for s := r.topScope; s != nil; s = s.Outer {
	 208  		if obj := s.Lookup(ident.Name); obj != nil {
	 209  			assert(obj.Name != "", "obj with no name")
	 210  			ident.Obj = obj
	 211  			return
	 212  		}
	 213  	}
	 214  	// all local scopes are known, so any unresolved identifier
	 215  	// must be found either in the file scope, package scope
	 216  	// (perhaps in another file), or universe scope --- collect
	 217  	// them so that they can be resolved later
	 218  	if collectUnresolved {
	 219  		ident.Obj = unresolved
	 220  		r.unresolved = append(r.unresolved, ident)
	 221  	}
	 222  }
	 223  
	 224  func (r *resolver) walkExprs(list []ast.Expr) {
	 225  	for _, node := range list {
	 226  		ast.Walk(r, node)
	 227  	}
	 228  }
	 229  
	 230  func (r *resolver) walkLHS(list []ast.Expr) {
	 231  	for _, expr := range list {
	 232  		expr := unparen(expr)
	 233  		if _, ok := expr.(*ast.Ident); !ok && expr != nil {
	 234  			ast.Walk(r, expr)
	 235  		}
	 236  	}
	 237  }
	 238  
	 239  func (r *resolver) walkStmts(list []ast.Stmt) {
	 240  	for _, stmt := range list {
	 241  		ast.Walk(r, stmt)
	 242  	}
	 243  }
	 244  
	 245  func (r *resolver) Visit(node ast.Node) ast.Visitor {
	 246  	if debugResolve && node != nil {
	 247  		r.dump("node %T@%v", node, node.Pos())
	 248  	}
	 249  
	 250  	switch n := node.(type) {
	 251  
	 252  	// Expressions.
	 253  	case *ast.Ident:
	 254  		r.resolve(n, true)
	 255  
	 256  	case *ast.FuncLit:
	 257  		r.openScope(n.Pos())
	 258  		defer r.closeScope()
	 259  		r.walkFuncType(n.Type)
	 260  		r.walkBody(n.Body)
	 261  
	 262  	case *ast.SelectorExpr:
	 263  		ast.Walk(r, n.X)
	 264  		// Note: don't try to resolve n.Sel, as we don't support qualified
	 265  		// resolution.
	 266  
	 267  	case *ast.StructType:
	 268  		r.openScope(n.Pos())
	 269  		defer r.closeScope()
	 270  		r.walkFieldList(n.Fields, ast.Var)
	 271  
	 272  	case *ast.FuncType:
	 273  		r.openScope(n.Pos())
	 274  		defer r.closeScope()
	 275  		r.walkFuncType(n)
	 276  
	 277  	case *ast.CompositeLit:
	 278  		if n.Type != nil {
	 279  			ast.Walk(r, n.Type)
	 280  		}
	 281  		for _, e := range n.Elts {
	 282  			if kv, _ := e.(*ast.KeyValueExpr); kv != nil {
	 283  				// See issue #45160: try to resolve composite lit keys, but don't
	 284  				// collect them as unresolved if resolution failed. This replicates
	 285  				// existing behavior when resolving during parsing.
	 286  				if ident, _ := kv.Key.(*ast.Ident); ident != nil {
	 287  					r.resolve(ident, false)
	 288  				} else {
	 289  					ast.Walk(r, kv.Key)
	 290  				}
	 291  				ast.Walk(r, kv.Value)
	 292  			} else {
	 293  				ast.Walk(r, e)
	 294  			}
	 295  		}
	 296  
	 297  	case *ast.InterfaceType:
	 298  		r.openScope(n.Pos())
	 299  		defer r.closeScope()
	 300  		r.walkFieldList(n.Methods, ast.Fun)
	 301  
	 302  	// Statements
	 303  	case *ast.LabeledStmt:
	 304  		r.declare(n, nil, r.labelScope, ast.Lbl, n.Label)
	 305  		ast.Walk(r, n.Stmt)
	 306  
	 307  	case *ast.AssignStmt:
	 308  		r.walkExprs(n.Rhs)
	 309  		if n.Tok == token.DEFINE {
	 310  			r.shortVarDecl(n)
	 311  		} else {
	 312  			r.walkExprs(n.Lhs)
	 313  		}
	 314  
	 315  	case *ast.BranchStmt:
	 316  		// add to list of unresolved targets
	 317  		if n.Tok != token.FALLTHROUGH && n.Label != nil {
	 318  			depth := len(r.targetStack) - 1
	 319  			r.targetStack[depth] = append(r.targetStack[depth], n.Label)
	 320  		}
	 321  
	 322  	case *ast.BlockStmt:
	 323  		r.openScope(n.Pos())
	 324  		defer r.closeScope()
	 325  		r.walkStmts(n.List)
	 326  
	 327  	case *ast.IfStmt:
	 328  		r.openScope(n.Pos())
	 329  		defer r.closeScope()
	 330  		if n.Init != nil {
	 331  			ast.Walk(r, n.Init)
	 332  		}
	 333  		ast.Walk(r, n.Cond)
	 334  		ast.Walk(r, n.Body)
	 335  		if n.Else != nil {
	 336  			ast.Walk(r, n.Else)
	 337  		}
	 338  
	 339  	case *ast.CaseClause:
	 340  		r.walkExprs(n.List)
	 341  		r.openScope(n.Pos())
	 342  		defer r.closeScope()
	 343  		r.walkStmts(n.Body)
	 344  
	 345  	case *ast.SwitchStmt:
	 346  		r.openScope(n.Pos())
	 347  		defer r.closeScope()
	 348  		if n.Init != nil {
	 349  			ast.Walk(r, n.Init)
	 350  		}
	 351  		if n.Tag != nil {
	 352  			// The scope below reproduces some unnecessary behavior of the parser,
	 353  			// opening an extra scope in case this is a type switch. It's not needed
	 354  			// for expression switches.
	 355  			// TODO: remove this once we've matched the parser resolution exactly.
	 356  			if n.Init != nil {
	 357  				r.openScope(n.Tag.Pos())
	 358  				defer r.closeScope()
	 359  			}
	 360  			ast.Walk(r, n.Tag)
	 361  		}
	 362  		if n.Body != nil {
	 363  			r.walkStmts(n.Body.List)
	 364  		}
	 365  
	 366  	case *ast.TypeSwitchStmt:
	 367  		if n.Init != nil {
	 368  			r.openScope(n.Pos())
	 369  			defer r.closeScope()
	 370  			ast.Walk(r, n.Init)
	 371  		}
	 372  		r.openScope(n.Assign.Pos())
	 373  		defer r.closeScope()
	 374  		ast.Walk(r, n.Assign)
	 375  		// s.Body consists only of case clauses, so does not get its own
	 376  		// scope.
	 377  		if n.Body != nil {
	 378  			r.walkStmts(n.Body.List)
	 379  		}
	 380  
	 381  	case *ast.CommClause:
	 382  		r.openScope(n.Pos())
	 383  		defer r.closeScope()
	 384  		if n.Comm != nil {
	 385  			ast.Walk(r, n.Comm)
	 386  		}
	 387  		r.walkStmts(n.Body)
	 388  
	 389  	case *ast.SelectStmt:
	 390  		// as for switch statements, select statement bodies don't get their own
	 391  		// scope.
	 392  		if n.Body != nil {
	 393  			r.walkStmts(n.Body.List)
	 394  		}
	 395  
	 396  	case *ast.ForStmt:
	 397  		r.openScope(n.Pos())
	 398  		defer r.closeScope()
	 399  		if n.Init != nil {
	 400  			ast.Walk(r, n.Init)
	 401  		}
	 402  		if n.Cond != nil {
	 403  			ast.Walk(r, n.Cond)
	 404  		}
	 405  		if n.Post != nil {
	 406  			ast.Walk(r, n.Post)
	 407  		}
	 408  		ast.Walk(r, n.Body)
	 409  
	 410  	case *ast.RangeStmt:
	 411  		r.openScope(n.Pos())
	 412  		defer r.closeScope()
	 413  		ast.Walk(r, n.X)
	 414  		var lhs []ast.Expr
	 415  		if n.Key != nil {
	 416  			lhs = append(lhs, n.Key)
	 417  		}
	 418  		if n.Value != nil {
	 419  			lhs = append(lhs, n.Value)
	 420  		}
	 421  		if len(lhs) > 0 {
	 422  			if n.Tok == token.DEFINE {
	 423  				// Note: we can't exactly match the behavior of object resolution
	 424  				// during the parsing pass here, as it uses the position of the RANGE
	 425  				// token for the RHS OpPos. That information is not contained within
	 426  				// the AST.
	 427  				as := &ast.AssignStmt{
	 428  					Lhs:		lhs,
	 429  					Tok:		token.DEFINE,
	 430  					TokPos: n.TokPos,
	 431  					Rhs:		[]ast.Expr{&ast.UnaryExpr{Op: token.RANGE, X: n.X}},
	 432  				}
	 433  				// TODO(rFindley): this walkLHS reproduced the parser resolution, but
	 434  				// is it necessary? By comparison, for a normal AssignStmt we don't
	 435  				// walk the LHS in case there is an invalid identifier list.
	 436  				r.walkLHS(lhs)
	 437  				r.shortVarDecl(as)
	 438  			} else {
	 439  				r.walkExprs(lhs)
	 440  			}
	 441  		}
	 442  		ast.Walk(r, n.Body)
	 443  
	 444  	// Declarations
	 445  	case *ast.GenDecl:
	 446  		switch n.Tok {
	 447  		case token.CONST, token.VAR:
	 448  			for i, spec := range n.Specs {
	 449  				spec := spec.(*ast.ValueSpec)
	 450  				kind := ast.Con
	 451  				if n.Tok == token.VAR {
	 452  					kind = ast.Var
	 453  				}
	 454  				r.walkExprs(spec.Values)
	 455  				if spec.Type != nil {
	 456  					ast.Walk(r, spec.Type)
	 457  				}
	 458  				r.declare(spec, i, r.topScope, kind, spec.Names...)
	 459  			}
	 460  		case token.TYPE:
	 461  			for _, spec := range n.Specs {
	 462  				spec := spec.(*ast.TypeSpec)
	 463  				// Go spec: The scope of a type identifier declared inside a function begins
	 464  				// at the identifier in the TypeSpec and ends at the end of the innermost
	 465  				// containing block.
	 466  				r.declare(spec, nil, r.topScope, ast.Typ, spec.Name)
	 467  				if tparams := typeparams.Get(spec); tparams != nil {
	 468  					r.openScope(spec.Pos())
	 469  					defer r.closeScope()
	 470  					r.walkTParams(tparams)
	 471  				}
	 472  				ast.Walk(r, spec.Type)
	 473  			}
	 474  		}
	 475  
	 476  	case *ast.FuncDecl:
	 477  		// Open the function scope.
	 478  		r.openScope(n.Pos())
	 479  		defer r.closeScope()
	 480  
	 481  		// Resolve the receiver first, without declaring.
	 482  		r.resolveList(n.Recv)
	 483  
	 484  		// Type parameters are walked normally: they can reference each other, and
	 485  		// can be referenced by normal parameters.
	 486  		if tparams := typeparams.Get(n.Type); tparams != nil {
	 487  			r.walkTParams(tparams)
	 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.TParams 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) walkFieldList(list *ast.FieldList, kind ast.ObjKind) {
	 540  	if list == nil {
	 541  		return
	 542  	}
	 543  	r.resolveList(list)
	 544  	r.declareList(list, kind)
	 545  }
	 546  
	 547  // walkTParams is like walkFieldList, but declares type parameters eagerly so
	 548  // that they may be resolved in the constraint expressions held in the field
	 549  // Type.
	 550  func (r *resolver) walkTParams(list *ast.FieldList) {
	 551  	if list == nil {
	 552  		return
	 553  	}
	 554  	r.declareList(list, ast.Typ)
	 555  	r.resolveList(list)
	 556  }
	 557  
	 558  func (r *resolver) walkBody(body *ast.BlockStmt) {
	 559  	if body == nil {
	 560  		return
	 561  	}
	 562  	r.openLabelScope()
	 563  	defer r.closeLabelScope()
	 564  	r.walkStmts(body.List)
	 565  }
	 566
View as plain text