Source file src/go/types/check.go
1 // Copyright 2011 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 // This file implements the Check function, which drives type-checking. 6 7 package types 8 9 import ( 10 "fmt" 11 "go/ast" 12 "go/constant" 13 "go/token" 14 "internal/godebug" 15 . "internal/types/errors" 16 "os" 17 "sync/atomic" 18 ) 19 20 // nopos, noposn indicate an unknown position 21 var nopos token.Pos 22 var noposn = atPos(nopos) 23 24 // debugging/development support 25 const debug = false // leave on during development 26 27 // position tracing for panics during type checking 28 const tracePos = false // TODO(markfreeman): check performance implications 29 30 // gotypesalias controls the use of Alias types. 31 // As of Apr 16 2024 they are used by default. 32 // To disable their use, set GODEBUG to gotypesalias=0. 33 // This GODEBUG flag will be removed in the near future (tentatively Go 1.24). 34 var gotypesalias = godebug.New("gotypesalias") 35 36 // _aliasAny changes the behavior of [Scope.Lookup] for "any" in the 37 // [Universe] scope. 38 // 39 // This is necessary because while Alias creation is controlled by 40 // [Config._EnableAlias], based on the gotypealias variable, the representation 41 // of "any" is a global. In [Scope.Lookup], we select this global 42 // representation based on the result of [aliasAny], but as a result need to 43 // guard against this behavior changing during the type checking pass. 44 // Therefore we implement the following rule: any number of goroutines can type 45 // check concurrently with the same EnableAlias value, but if any goroutine 46 // tries to type check concurrently with a different EnableAlias value, we 47 // panic. 48 // 49 // To achieve this, _aliasAny is a state machine: 50 // 51 // 0: no type checking is occurring 52 // negative: type checking is occurring without _EnableAlias set 53 // positive: type checking is occurring with _EnableAlias set 54 var _aliasAny int32 55 56 func aliasAny() bool { 57 v := gotypesalias.Value() 58 useAlias := v != "0" 59 inuse := atomic.LoadInt32(&_aliasAny) 60 if inuse != 0 && useAlias != (inuse > 0) { 61 panic(fmt.Sprintf("gotypealias mutated during type checking, gotypesalias=%s, inuse=%d", v, inuse)) 62 } 63 return useAlias 64 } 65 66 // exprInfo stores information about an untyped expression. 67 type exprInfo struct { 68 isLhs bool // expression is lhs operand of a shift with delayed type-check 69 mode operandMode 70 typ *Basic 71 val constant.Value // constant value; or nil (if not a constant) 72 } 73 74 // An environment represents the environment within which an object is 75 // type-checked. 76 type environment struct { 77 decl *declInfo // package-level declaration whose init expression/function body is checked 78 scope *Scope // top-most scope for lookups 79 version goVersion // current accepted language version; changes across files 80 iota constant.Value // value of iota in a constant declaration; nil otherwise 81 errpos positioner // if set, identifier position of a constant with inherited initializer 82 inTParamList bool // set if inside a type parameter list 83 sig *Signature // function signature if inside a function; nil otherwise 84 isPanic map[*ast.CallExpr]bool // set of panic call expressions (used for termination check) 85 hasLabel bool // set if a function makes use of labels (only ~1% of functions); unused outside functions 86 hasCallOrRecv bool // set if an expression contains a function call or channel receive operation 87 88 // go/types only 89 exprPos token.Pos // if valid, identifiers are looked up as if at position pos (used by CheckExpr, Eval) 90 } 91 92 // lookupScope looks up name in the current environment and if an object 93 // is found it returns the scope containing the object and the object. 94 // Otherwise it returns (nil, nil). 95 // 96 // Note that obj.Parent() may be different from the returned scope if the 97 // object was inserted into the scope and already had a parent at that 98 // time (see Scope.Insert). This can only happen for dot-imported objects 99 // whose parent is the scope of the package that exported them. 100 func (env *environment) lookupScope(name string) (*Scope, Object) { 101 for s := env.scope; s != nil; s = s.parent { 102 if obj := s.Lookup(name); obj != nil && (!env.exprPos.IsValid() || cmpPos(obj.scopePos(), env.exprPos) <= 0) { 103 return s, obj 104 } 105 } 106 return nil, nil 107 } 108 109 // lookup is like lookupScope but it only returns the object (or nil). 110 func (env *environment) lookup(name string) Object { 111 _, obj := env.lookupScope(name) 112 return obj 113 } 114 115 // An importKey identifies an imported package by import path and source directory 116 // (directory containing the file containing the import). In practice, the directory 117 // may always be the same, or may not matter. Given an (import path, directory), an 118 // importer must always return the same package (but given two different import paths, 119 // an importer may still return the same package by mapping them to the same package 120 // paths). 121 type importKey struct { 122 path, dir string 123 } 124 125 // A dotImportKey describes a dot-imported object in the given scope. 126 type dotImportKey struct { 127 scope *Scope 128 name string 129 } 130 131 // An action describes a (delayed) action. 132 type action struct { 133 version goVersion // applicable language version 134 f func() // action to be executed 135 desc *actionDesc // action description; may be nil, requires debug to be set 136 } 137 138 // If debug is set, describef sets a printf-formatted description for action a. 139 // Otherwise, it is a no-op. 140 func (a *action) describef(pos positioner, format string, args ...any) { 141 if debug { 142 a.desc = &actionDesc{pos, format, args} 143 } 144 } 145 146 // An actionDesc provides information on an action. 147 // For debugging only. 148 type actionDesc struct { 149 pos positioner 150 format string 151 args []any 152 } 153 154 // A Checker maintains the state of the type checker. 155 // It must be created with [NewChecker]. 156 type Checker struct { 157 // package information 158 // (initialized by NewChecker, valid for the life-time of checker) 159 conf *Config 160 ctxt *Context // context for de-duplicating instances 161 fset *token.FileSet 162 pkg *Package 163 *Info 164 nextID uint64 // unique Id for type parameters (first valid Id is 1) 165 objMap map[Object]*declInfo // maps package-level objects and (non-interface) methods to declaration info 166 impMap map[importKey]*Package // maps (import path, source directory) to (complete or fake) package 167 // see TODO in validtype.go 168 // valids instanceLookup // valid *Named (incl. instantiated) types per the validType check 169 170 // pkgPathMap maps package names to the set of distinct import paths we've 171 // seen for that name, anywhere in the import graph. It is used for 172 // disambiguating package names in error messages. 173 // 174 // pkgPathMap is allocated lazily, so that we don't pay the price of building 175 // it on the happy path. seenPkgMap tracks the packages that we've already 176 // walked. 177 pkgPathMap map[string]map[string]bool 178 seenPkgMap map[*Package]bool 179 180 // information collected during type-checking of a set of package files 181 // (initialized by Files, valid only for the duration of check.Files; 182 // maps and lists are allocated on demand) 183 files []*ast.File // package files 184 versions map[*ast.File]string // maps files to goVersion strings (each file has an entry); shared with Info.FileVersions if present; may be unaltered Config.GoVersion 185 imports []*PkgName // list of imported packages 186 dotImportMap map[dotImportKey]*PkgName // maps dot-imported objects to the package they were dot-imported through 187 brokenAliases map[*TypeName]bool // set of aliases with broken (not yet determined) types 188 unionTypeSets map[*Union]*_TypeSet // computed type sets for union types 189 usedVars map[*Var]bool // set of used variables 190 usedPkgNames map[*PkgName]bool // set of used package names 191 mono monoGraph // graph for detecting non-monomorphizable instantiation loops 192 193 firstErr error // first error encountered 194 methods map[*TypeName][]*Func // maps package scope type names to associated non-blank (non-interface) methods 195 untyped map[ast.Expr]exprInfo // map of expressions without final type 196 delayed []action // stack of delayed action segments; segments are processed in FIFO order 197 objPath []Object // path of object dependencies during type inference (for cycle reporting) 198 cleaners []cleaner // list of types that may need a final cleanup at the end of type-checking 199 200 // environment within which the current object is type-checked (valid only 201 // for the duration of type-checking a specific object) 202 environment 203 204 // debugging 205 posStack []positioner // stack of source positions seen; used for panic tracing 206 indent int // indentation for tracing 207 } 208 209 // addDeclDep adds the dependency edge (check.decl -> to) if check.decl exists 210 func (check *Checker) addDeclDep(to Object) { 211 from := check.decl 212 if from == nil { 213 return // not in a package-level init expression 214 } 215 if _, found := check.objMap[to]; !found { 216 return // to is not a package-level object 217 } 218 from.addDep(to) 219 } 220 221 // Note: The following three alias-related functions are only used 222 // when Alias types are not enabled. 223 224 // brokenAlias records that alias doesn't have a determined type yet. 225 // It also sets alias.typ to Typ[Invalid]. 226 // Not used if check.conf._EnableAlias is set. 227 func (check *Checker) brokenAlias(alias *TypeName) { 228 assert(!check.conf._EnableAlias) 229 if check.brokenAliases == nil { 230 check.brokenAliases = make(map[*TypeName]bool) 231 } 232 check.brokenAliases[alias] = true 233 alias.typ = Typ[Invalid] 234 } 235 236 // validAlias records that alias has the valid type typ (possibly Typ[Invalid]). 237 func (check *Checker) validAlias(alias *TypeName, typ Type) { 238 assert(!check.conf._EnableAlias) 239 delete(check.brokenAliases, alias) 240 alias.typ = typ 241 } 242 243 // isBrokenAlias reports whether alias doesn't have a determined type yet. 244 func (check *Checker) isBrokenAlias(alias *TypeName) bool { 245 assert(!check.conf._EnableAlias) 246 return check.brokenAliases[alias] 247 } 248 249 func (check *Checker) rememberUntyped(e ast.Expr, lhs bool, mode operandMode, typ *Basic, val constant.Value) { 250 m := check.untyped 251 if m == nil { 252 m = make(map[ast.Expr]exprInfo) 253 check.untyped = m 254 } 255 m[e] = exprInfo{lhs, mode, typ, val} 256 } 257 258 // later pushes f on to the stack of actions that will be processed later; 259 // either at the end of the current statement, or in case of a local constant 260 // or variable declaration, before the constant or variable is in scope 261 // (so that f still sees the scope before any new declarations). 262 // later returns the pushed action so one can provide a description 263 // via action.describef for debugging, if desired. 264 func (check *Checker) later(f func()) *action { 265 i := len(check.delayed) 266 check.delayed = append(check.delayed, action{version: check.version, f: f}) 267 return &check.delayed[i] 268 } 269 270 // push pushes obj onto the object path and returns its index in the path. 271 func (check *Checker) push(obj Object) int { 272 check.objPath = append(check.objPath, obj) 273 return len(check.objPath) - 1 274 } 275 276 // pop pops and returns the topmost object from the object path. 277 func (check *Checker) pop() Object { 278 i := len(check.objPath) - 1 279 obj := check.objPath[i] 280 check.objPath[i] = nil 281 check.objPath = check.objPath[:i] 282 return obj 283 } 284 285 type cleaner interface { 286 cleanup() 287 } 288 289 // needsCleanup records objects/types that implement the cleanup method 290 // which will be called at the end of type-checking. 291 func (check *Checker) needsCleanup(c cleaner) { 292 check.cleaners = append(check.cleaners, c) 293 } 294 295 // NewChecker returns a new [Checker] instance for a given package. 296 // [Package] files may be added incrementally via checker.Files. 297 func NewChecker(conf *Config, fset *token.FileSet, pkg *Package, info *Info) *Checker { 298 // make sure we have a configuration 299 if conf == nil { 300 conf = new(Config) 301 } 302 303 // make sure we have an info struct 304 if info == nil { 305 info = new(Info) 306 } 307 308 // Note: clients may call NewChecker with the Unsafe package, which is 309 // globally shared and must not be mutated. Therefore NewChecker must not 310 // mutate *pkg. 311 // 312 // (previously, pkg.goVersion was mutated here: go.dev/issue/61212) 313 314 // In go/types, conf._EnableAlias is controlled by gotypesalias. 315 conf._EnableAlias = gotypesalias.Value() != "0" 316 317 return &Checker{ 318 conf: conf, 319 ctxt: conf.Context, 320 fset: fset, 321 pkg: pkg, 322 Info: info, 323 objMap: make(map[Object]*declInfo), 324 impMap: make(map[importKey]*Package), 325 usedVars: make(map[*Var]bool), 326 usedPkgNames: make(map[*PkgName]bool), 327 } 328 } 329 330 // initFiles initializes the files-specific portion of checker. 331 // The provided files must all belong to the same package. 332 func (check *Checker) initFiles(files []*ast.File) { 333 // start with a clean slate (check.Files may be called multiple times) 334 // TODO(gri): what determines which fields are zeroed out here, vs at the end 335 // of checkFiles? 336 check.files = nil 337 check.imports = nil 338 check.dotImportMap = nil 339 340 check.firstErr = nil 341 check.methods = nil 342 check.untyped = nil 343 check.delayed = nil 344 check.objPath = nil 345 check.cleaners = nil 346 347 // We must initialize usedVars and usedPkgNames both here and in NewChecker, 348 // because initFiles is not called in the CheckExpr or Eval codepaths, yet we 349 // want to free this memory at the end of Files ('used' predicates are 350 // only needed in the context of a given file). 351 check.usedVars = make(map[*Var]bool) 352 check.usedPkgNames = make(map[*PkgName]bool) 353 354 // determine package name and collect valid files 355 pkg := check.pkg 356 for _, file := range files { 357 switch name := file.Name.Name; pkg.name { 358 case "": 359 if name != "_" { 360 pkg.name = name 361 } else { 362 check.error(file.Name, BlankPkgName, "invalid package name _") 363 } 364 fallthrough 365 366 case name: 367 check.files = append(check.files, file) 368 369 default: 370 check.errorf(atPos(file.Package), MismatchedPkgName, "package %s; expected package %s", name, pkg.name) 371 // ignore this file 372 } 373 } 374 375 // reuse Info.FileVersions if provided 376 versions := check.Info.FileVersions 377 if versions == nil { 378 versions = make(map[*ast.File]string) 379 } 380 check.versions = versions 381 382 pkgVersion := asGoVersion(check.conf.GoVersion) 383 if pkgVersion.isValid() && len(files) > 0 && pkgVersion.cmp(go_current) > 0 { 384 check.errorf(files[0], TooNew, "package requires newer Go version %v (application built with %v)", 385 pkgVersion, go_current) 386 } 387 388 // determine Go version for each file 389 for _, file := range check.files { 390 // use unaltered Config.GoVersion by default 391 // (This version string may contain dot-release numbers as in go1.20.1, 392 // unlike file versions which are Go language versions only, if valid.) 393 v := check.conf.GoVersion 394 395 // If the file specifies a version, use max(fileVersion, go1.21). 396 if fileVersion := asGoVersion(file.GoVersion); fileVersion.isValid() { 397 // Go 1.21 introduced the feature of setting the go.mod 398 // go line to an early version of Go and allowing //go:build lines 399 // to set the Go version in a given file. Versions Go 1.21 and later 400 // can be set backwards compatibly as that was the first version 401 // files with go1.21 or later build tags could be built with. 402 // 403 // Set the version to max(fileVersion, go1.21): That will allow a 404 // downgrade to a version before go1.22, where the for loop semantics 405 // change was made, while being backwards compatible with versions of 406 // go before the new //go:build semantics were introduced. 407 v = string(versionMax(fileVersion, go1_21)) 408 409 // Report a specific error for each tagged file that's too new. 410 // (Normally the build system will have filtered files by version, 411 // but clients can present arbitrary files to the type checker.) 412 if fileVersion.cmp(go_current) > 0 { 413 // Use position of 'package [p]' for types/types2 consistency. 414 // (Ideally we would use the //build tag itself.) 415 check.errorf(file.Name, TooNew, "file requires newer Go version %v (application built with %v)", fileVersion, go_current) 416 } 417 } 418 versions[file] = v 419 } 420 } 421 422 func versionMax(a, b goVersion) goVersion { 423 if a.cmp(b) < 0 { 424 return b 425 } 426 return a 427 } 428 429 // pushPos pushes pos onto the pos stack. 430 func (check *Checker) pushPos(pos positioner) { 431 check.posStack = append(check.posStack, pos) 432 } 433 434 // popPos pops from the pos stack. 435 func (check *Checker) popPos() { 436 check.posStack = check.posStack[:len(check.posStack)-1] 437 } 438 439 // A bailout panic is used for early termination. 440 type bailout struct{} 441 442 func (check *Checker) handleBailout(err *error) { 443 switch p := recover().(type) { 444 case nil, bailout: 445 // normal return or early exit 446 *err = check.firstErr 447 default: 448 if len(check.posStack) > 0 { 449 doPrint := func(ps []positioner) { 450 for i := len(ps) - 1; i >= 0; i-- { 451 fmt.Fprintf(os.Stderr, "\t%v\n", check.fset.Position(ps[i].Pos())) 452 } 453 } 454 455 fmt.Fprintln(os.Stderr, "The following panic happened checking types near:") 456 if len(check.posStack) <= 10 { 457 doPrint(check.posStack) 458 } else { 459 // if it's long, truncate the middle; it's least likely to help 460 doPrint(check.posStack[len(check.posStack)-5:]) 461 fmt.Fprintln(os.Stderr, "\t...") 462 doPrint(check.posStack[:5]) 463 } 464 } 465 466 // re-panic 467 panic(p) 468 } 469 } 470 471 // Files checks the provided files as part of the checker's package. 472 func (check *Checker) Files(files []*ast.File) (err error) { 473 if check.pkg == Unsafe { 474 // Defensive handling for Unsafe, which cannot be type checked, and must 475 // not be mutated. See https://go.dev/issue/61212 for an example of where 476 // Unsafe is passed to NewChecker. 477 return nil 478 } 479 480 // Avoid early returns here! Nearly all errors can be 481 // localized to a piece of syntax and needn't prevent 482 // type-checking of the rest of the package. 483 484 defer check.handleBailout(&err) 485 check.checkFiles(files) 486 return 487 } 488 489 // checkFiles type-checks the specified files. Errors are reported as 490 // a side effect, not by returning early, to ensure that well-formed 491 // syntax is properly type annotated even in a package containing 492 // errors. 493 func (check *Checker) checkFiles(files []*ast.File) { 494 // Ensure that _EnableAlias is consistent among concurrent type checking 495 // operations. See the documentation of [_aliasAny] for details. 496 if check.conf._EnableAlias { 497 if atomic.AddInt32(&_aliasAny, 1) <= 0 { 498 panic("EnableAlias set while !EnableAlias type checking is ongoing") 499 } 500 defer atomic.AddInt32(&_aliasAny, -1) 501 } else { 502 if atomic.AddInt32(&_aliasAny, -1) >= 0 { 503 panic("!EnableAlias set while EnableAlias type checking is ongoing") 504 } 505 defer atomic.AddInt32(&_aliasAny, 1) 506 } 507 508 print := func(msg string) { 509 if check.conf._Trace { 510 fmt.Println() 511 fmt.Println(msg) 512 } 513 } 514 515 print("== initFiles ==") 516 check.initFiles(files) 517 518 print("== collectObjects ==") 519 check.collectObjects() 520 521 print("== packageObjects ==") 522 check.packageObjects() 523 524 print("== processDelayed ==") 525 check.processDelayed(0) // incl. all functions 526 527 print("== cleanup ==") 528 check.cleanup() 529 530 print("== initOrder ==") 531 check.initOrder() 532 533 if !check.conf.DisableUnusedImportCheck { 534 print("== unusedImports ==") 535 check.unusedImports() 536 } 537 538 print("== recordUntyped ==") 539 check.recordUntyped() 540 541 if check.firstErr == nil { 542 // TODO(mdempsky): Ensure monomorph is safe when errors exist. 543 check.monomorph() 544 } 545 546 check.pkg.goVersion = check.conf.GoVersion 547 check.pkg.complete = true 548 549 // no longer needed - release memory 550 check.imports = nil 551 check.dotImportMap = nil 552 check.pkgPathMap = nil 553 check.seenPkgMap = nil 554 check.brokenAliases = nil 555 check.unionTypeSets = nil 556 check.usedVars = nil 557 check.usedPkgNames = nil 558 check.ctxt = nil 559 560 // TODO(gri): shouldn't the cleanup above occur after the bailout? 561 // TODO(gri) There's more memory we should release at this point. 562 } 563 564 // processDelayed processes all delayed actions pushed after top. 565 func (check *Checker) processDelayed(top int) { 566 // If each delayed action pushes a new action, the 567 // stack will continue to grow during this loop. 568 // However, it is only processing functions (which 569 // are processed in a delayed fashion) that may 570 // add more actions (such as nested functions), so 571 // this is a sufficiently bounded process. 572 savedVersion := check.version 573 for i := top; i < len(check.delayed); i++ { 574 a := &check.delayed[i] 575 if check.conf._Trace { 576 if a.desc != nil { 577 check.trace(a.desc.pos.Pos(), "-- "+a.desc.format, a.desc.args...) 578 } else { 579 check.trace(nopos, "-- delayed %p", a.f) 580 } 581 } 582 check.version = a.version // reestablish the effective Go version captured earlier 583 a.f() // may append to check.delayed 584 585 if check.conf._Trace { 586 fmt.Println() 587 } 588 } 589 assert(top <= len(check.delayed)) // stack must not have shrunk 590 check.delayed = check.delayed[:top] 591 check.version = savedVersion 592 } 593 594 // cleanup runs cleanup for all collected cleaners. 595 func (check *Checker) cleanup() { 596 // Don't use a range clause since Named.cleanup may add more cleaners. 597 for i := 0; i < len(check.cleaners); i++ { 598 check.cleaners[i].cleanup() 599 } 600 check.cleaners = nil 601 } 602 603 // go/types doesn't support recording of types directly in the AST. 604 // dummy function to match types2 code. 605 func (check *Checker) recordTypeAndValueInSyntax(x ast.Expr, mode operandMode, typ Type, val constant.Value) { 606 // nothing to do 607 } 608 609 // go/types doesn't support recording of types directly in the AST. 610 // dummy function to match types2 code. 611 func (check *Checker) recordCommaOkTypesInSyntax(x ast.Expr, t0, t1 Type) { 612 // nothing to do 613 } 614 615 // instantiatedIdent determines the identifier of the type instantiated in expr. 616 // Helper function for recordInstance in recording.go. 617 func instantiatedIdent(expr ast.Expr) *ast.Ident { 618 var selOrIdent ast.Expr 619 switch e := expr.(type) { 620 case *ast.IndexExpr: 621 selOrIdent = e.X 622 case *ast.IndexListExpr: // only exists in go/ast, not syntax 623 selOrIdent = e.X 624 case *ast.SelectorExpr, *ast.Ident: 625 selOrIdent = e 626 } 627 switch x := selOrIdent.(type) { 628 case *ast.Ident: 629 return x 630 case *ast.SelectorExpr: 631 return x.Sel 632 } 633 634 // extra debugging of go.dev/issue/63933 635 panic(sprintf(nil, nil, true, "instantiated ident not found; please report: %s", expr)) 636 } 637