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 = true 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 objList []Object // source-ordered keys of objMap 167 impMap map[importKey]*Package // maps (import path, source directory) to (complete or fake) package 168 // see TODO in validtype.go 169 // valids instanceLookup // valid *Named (incl. instantiated) types per the validType check 170 171 // pkgPathMap maps package names to the set of distinct import paths we've 172 // seen for that name, anywhere in the import graph. It is used for 173 // disambiguating package names in error messages. 174 // 175 // pkgPathMap is allocated lazily, so that we don't pay the price of building 176 // it on the happy path. seenPkgMap tracks the packages that we've already 177 // walked. 178 pkgPathMap map[string]map[string]bool 179 seenPkgMap map[*Package]bool 180 181 // information collected during type-checking of a set of package files 182 // (initialized by Files, valid only for the duration of check.Files; 183 // maps and lists are allocated on demand) 184 files []*ast.File // package files 185 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 186 imports []*PkgName // list of imported packages 187 dotImportMap map[dotImportKey]*PkgName // maps dot-imported objects to the package they were dot-imported through 188 brokenAliases map[*TypeName]bool // set of aliases with broken (not yet determined) types 189 unionTypeSets map[*Union]*_TypeSet // computed type sets for union types 190 usedVars map[*Var]bool // set of used variables 191 usedPkgNames map[*PkgName]bool // set of used package names 192 mono monoGraph // graph for detecting non-monomorphizable instantiation loops 193 194 firstErr error // first error encountered 195 methods map[*TypeName][]*Func // maps package scope type names to associated non-blank (non-interface) methods 196 untyped map[ast.Expr]exprInfo // map of expressions without final type 197 delayed []action // stack of delayed action segments; segments are processed in FIFO order 198 objPath []Object // path of object dependencies during type-checking (for cycle reporting) 199 objPathIdx map[Object]int // map of object to object path index during type-checking (for cycle reporting) 200 cleaners []cleaner // list of types that may need a final cleanup at the end of type-checking 201 202 // environment within which the current object is type-checked (valid only 203 // for the duration of type-checking a specific object) 204 environment 205 206 // debugging 207 posStack []positioner // stack of source positions seen; used for panic tracing 208 indent int // indentation for tracing 209 } 210 211 // addDeclDep adds the dependency edge (check.decl -> to) if check.decl exists 212 func (check *Checker) addDeclDep(to Object) { 213 from := check.decl 214 if from == nil { 215 return // not in a package-level init expression 216 } 217 if _, found := check.objMap[to]; !found { 218 return // to is not a package-level object 219 } 220 from.addDep(to) 221 } 222 223 // Note: The following three alias-related functions are only used 224 // when Alias types are not enabled. 225 226 // brokenAlias records that alias doesn't have a determined type yet. 227 // It also sets alias.typ to Typ[Invalid]. 228 // Not used if check.conf._EnableAlias is set. 229 func (check *Checker) brokenAlias(alias *TypeName) { 230 assert(!check.conf._EnableAlias) 231 if check.brokenAliases == nil { 232 check.brokenAliases = make(map[*TypeName]bool) 233 } 234 check.brokenAliases[alias] = true 235 alias.typ = Typ[Invalid] 236 } 237 238 // validAlias records that alias has the valid type typ (possibly Typ[Invalid]). 239 func (check *Checker) validAlias(alias *TypeName, typ Type) { 240 assert(!check.conf._EnableAlias) 241 delete(check.brokenAliases, alias) 242 alias.typ = typ 243 } 244 245 // isBrokenAlias reports whether alias doesn't have a determined type yet. 246 func (check *Checker) isBrokenAlias(alias *TypeName) bool { 247 assert(!check.conf._EnableAlias) 248 return check.brokenAliases[alias] 249 } 250 251 func (check *Checker) rememberUntyped(e ast.Expr, lhs bool, mode operandMode, typ *Basic, val constant.Value) { 252 m := check.untyped 253 if m == nil { 254 m = make(map[ast.Expr]exprInfo) 255 check.untyped = m 256 } 257 m[e] = exprInfo{lhs, mode, typ, val} 258 } 259 260 // later pushes f on to the stack of actions that will be processed later; 261 // either at the end of the current statement, or in case of a local constant 262 // or variable declaration, before the constant or variable is in scope 263 // (so that f still sees the scope before any new declarations). 264 // later returns the pushed action so one can provide a description 265 // via action.describef for debugging, if desired. 266 func (check *Checker) later(f func()) *action { 267 i := len(check.delayed) 268 check.delayed = append(check.delayed, action{version: check.version, f: f}) 269 return &check.delayed[i] 270 } 271 272 // push pushes obj onto the object path and records its index in the path index map. 273 func (check *Checker) push(obj Object) { 274 if check.objPathIdx == nil { 275 check.objPathIdx = make(map[Object]int) 276 } 277 check.objPathIdx[obj] = len(check.objPath) 278 check.objPath = append(check.objPath, obj) 279 } 280 281 // pop pops an object from the object path and removes it from the path index map. 282 func (check *Checker) pop() { 283 i := len(check.objPath) - 1 284 obj := check.objPath[i] 285 check.objPath[i] = nil // help the garbage collector 286 check.objPath = check.objPath[:i] 287 delete(check.objPathIdx, obj) 288 } 289 290 type cleaner interface { 291 cleanup() 292 } 293 294 // needsCleanup records objects/types that implement the cleanup method 295 // which will be called at the end of type-checking. 296 func (check *Checker) needsCleanup(c cleaner) { 297 check.cleaners = append(check.cleaners, c) 298 } 299 300 // NewChecker returns a new [Checker] instance for a given package. 301 // [Package] files may be added incrementally via checker.Files. 302 func NewChecker(conf *Config, fset *token.FileSet, pkg *Package, info *Info) *Checker { 303 // make sure we have a configuration 304 if conf == nil { 305 conf = new(Config) 306 } 307 308 // make sure we have an info struct 309 if info == nil { 310 info = new(Info) 311 } 312 313 // Note: clients may call NewChecker with the Unsafe package, which is 314 // globally shared and must not be mutated. Therefore NewChecker must not 315 // mutate *pkg. 316 // 317 // (previously, pkg.goVersion was mutated here: go.dev/issue/61212) 318 319 // In go/types, conf._EnableAlias is controlled by gotypesalias. 320 conf._EnableAlias = gotypesalias.Value() != "0" 321 322 return &Checker{ 323 conf: conf, 324 ctxt: conf.Context, 325 fset: fset, 326 pkg: pkg, 327 Info: info, 328 objMap: make(map[Object]*declInfo), 329 impMap: make(map[importKey]*Package), 330 usedVars: make(map[*Var]bool), 331 usedPkgNames: make(map[*PkgName]bool), 332 } 333 } 334 335 // initFiles initializes the files-specific portion of checker. 336 // The provided files must all belong to the same package. 337 func (check *Checker) initFiles(files []*ast.File) { 338 // start with a clean slate (check.Files may be called multiple times) 339 // TODO(gri): what determines which fields are zeroed out here, vs at the end 340 // of checkFiles? 341 check.files = nil 342 check.imports = nil 343 check.dotImportMap = nil 344 345 check.firstErr = nil 346 check.methods = nil 347 check.untyped = nil 348 check.delayed = nil 349 check.objPath = nil 350 check.objPathIdx = nil 351 check.cleaners = nil 352 353 // We must initialize usedVars and usedPkgNames both here and in NewChecker, 354 // because initFiles is not called in the CheckExpr or Eval codepaths, yet we 355 // want to free this memory at the end of Files ('used' predicates are 356 // only needed in the context of a given file). 357 check.usedVars = make(map[*Var]bool) 358 check.usedPkgNames = make(map[*PkgName]bool) 359 360 // determine package name and collect valid files 361 pkg := check.pkg 362 for _, file := range files { 363 switch name := file.Name.Name; pkg.name { 364 case "": 365 if name != "_" { 366 pkg.name = name 367 } else { 368 check.error(file.Name, BlankPkgName, "invalid package name _") 369 } 370 fallthrough 371 372 case name: 373 check.files = append(check.files, file) 374 375 default: 376 check.errorf(atPos(file.Package), MismatchedPkgName, "package %s; expected package %s", name, pkg.name) 377 // ignore this file 378 } 379 } 380 381 // reuse Info.FileVersions if provided 382 versions := check.Info.FileVersions 383 if versions == nil { 384 versions = make(map[*ast.File]string) 385 } 386 check.versions = versions 387 388 pkgVersion := asGoVersion(check.conf.GoVersion) 389 if pkgVersion.isValid() && len(files) > 0 && pkgVersion.cmp(go_current) > 0 { 390 check.errorf(files[0], TooNew, "package requires newer Go version %v (application built with %v)", 391 pkgVersion, go_current) 392 } 393 394 // determine Go version for each file 395 for _, file := range check.files { 396 // use unaltered Config.GoVersion by default 397 // (This version string may contain dot-release numbers as in go1.20.1, 398 // unlike file versions which are Go language versions only, if valid.) 399 v := check.conf.GoVersion 400 401 // If the file specifies a version, use max(fileVersion, go1.21). 402 if fileVersion := asGoVersion(file.GoVersion); fileVersion.isValid() { 403 // Go 1.21 introduced the feature of setting the go.mod 404 // go line to an early version of Go and allowing //go:build lines 405 // to set the Go version in a given file. Versions Go 1.21 and later 406 // can be set backwards compatibly as that was the first version 407 // files with go1.21 or later build tags could be built with. 408 // 409 // Set the version to max(fileVersion, go1.21): That will allow a 410 // downgrade to a version before go1.22, where the for loop semantics 411 // change was made, while being backwards compatible with versions of 412 // go before the new //go:build semantics were introduced. 413 v = string(versionMax(fileVersion, go1_21)) 414 415 // Report a specific error for each tagged file that's too new. 416 // (Normally the build system will have filtered files by version, 417 // but clients can present arbitrary files to the type checker.) 418 if fileVersion.cmp(go_current) > 0 { 419 // Use position of 'package [p]' for types/types2 consistency. 420 // (Ideally we would use the //build tag itself.) 421 check.errorf(file.Name, TooNew, "file requires newer Go version %v (application built with %v)", fileVersion, go_current) 422 } 423 } 424 versions[file] = v 425 } 426 } 427 428 func versionMax(a, b goVersion) goVersion { 429 if a.cmp(b) < 0 { 430 return b 431 } 432 return a 433 } 434 435 // pushPos pushes pos onto the pos stack. 436 func (check *Checker) pushPos(pos positioner) { 437 check.posStack = append(check.posStack, pos) 438 } 439 440 // popPos pops from the pos stack. 441 func (check *Checker) popPos() { 442 check.posStack = check.posStack[:len(check.posStack)-1] 443 } 444 445 // A bailout panic is used for early termination. 446 type bailout struct{} 447 448 func (check *Checker) handleBailout(err *error) { 449 switch p := recover().(type) { 450 case nil, bailout: 451 // normal return or early exit 452 *err = check.firstErr 453 default: 454 if len(check.posStack) > 0 { 455 doPrint := func(ps []positioner) { 456 for i := len(ps) - 1; i >= 0; i-- { 457 fmt.Fprintf(os.Stderr, "\t%v\n", check.fset.Position(ps[i].Pos())) 458 } 459 } 460 461 fmt.Fprintln(os.Stderr, "The following panic happened checking types near:") 462 if len(check.posStack) <= 10 { 463 doPrint(check.posStack) 464 } else { 465 // if it's long, truncate the middle; it's least likely to help 466 doPrint(check.posStack[len(check.posStack)-5:]) 467 fmt.Fprintln(os.Stderr, "\t...") 468 doPrint(check.posStack[:5]) 469 } 470 } 471 472 // re-panic 473 panic(p) 474 } 475 } 476 477 // Files checks the provided files as part of the checker's package. 478 func (check *Checker) Files(files []*ast.File) (err error) { 479 if check.pkg == Unsafe { 480 // Defensive handling for Unsafe, which cannot be type checked, and must 481 // not be mutated. See https://go.dev/issue/61212 for an example of where 482 // Unsafe is passed to NewChecker. 483 return nil 484 } 485 486 // Avoid early returns here! Nearly all errors can be 487 // localized to a piece of syntax and needn't prevent 488 // type-checking of the rest of the package. 489 490 defer check.handleBailout(&err) 491 check.checkFiles(files) 492 return 493 } 494 495 // checkFiles type-checks the specified files. Errors are reported as 496 // a side effect, not by returning early, to ensure that well-formed 497 // syntax is properly type annotated even in a package containing 498 // errors. 499 func (check *Checker) checkFiles(files []*ast.File) { 500 // Ensure that _EnableAlias is consistent among concurrent type checking 501 // operations. See the documentation of [_aliasAny] for details. 502 if check.conf._EnableAlias { 503 if atomic.AddInt32(&_aliasAny, 1) <= 0 { 504 panic("EnableAlias set while !EnableAlias type checking is ongoing") 505 } 506 defer atomic.AddInt32(&_aliasAny, -1) 507 } else { 508 if atomic.AddInt32(&_aliasAny, -1) >= 0 { 509 panic("!EnableAlias set while EnableAlias type checking is ongoing") 510 } 511 defer atomic.AddInt32(&_aliasAny, 1) 512 } 513 514 print := func(msg string) { 515 if check.conf._Trace { 516 fmt.Println() 517 fmt.Println(msg) 518 } 519 } 520 521 print("== initFiles ==") 522 check.initFiles(files) 523 524 print("== collectObjects ==") 525 check.collectObjects() 526 527 print("== sortObjects ==") 528 check.sortObjects() 529 530 print("== directCycles ==") 531 check.directCycles() 532 533 print("== packageObjects ==") 534 check.packageObjects() 535 536 print("== processDelayed ==") 537 check.processDelayed(0) // incl. all functions 538 539 print("== cleanup ==") 540 check.cleanup() 541 542 print("== initOrder ==") 543 check.initOrder() 544 545 if !check.conf.DisableUnusedImportCheck { 546 print("== unusedImports ==") 547 check.unusedImports() 548 } 549 550 print("== recordUntyped ==") 551 check.recordUntyped() 552 553 if check.firstErr == nil { 554 // TODO(mdempsky): Ensure monomorph is safe when errors exist. 555 check.monomorph() 556 } 557 558 check.pkg.goVersion = check.conf.GoVersion 559 check.pkg.complete = true 560 561 // no longer needed - release memory 562 check.imports = nil 563 check.dotImportMap = nil 564 check.pkgPathMap = nil 565 check.seenPkgMap = nil 566 check.brokenAliases = nil 567 check.unionTypeSets = nil 568 check.usedVars = nil 569 check.usedPkgNames = nil 570 check.ctxt = nil 571 572 // TODO(gri): shouldn't the cleanup above occur after the bailout? 573 // TODO(gri) There's more memory we should release at this point. 574 } 575 576 // processDelayed processes all delayed actions pushed after top. 577 func (check *Checker) processDelayed(top int) { 578 // If each delayed action pushes a new action, the 579 // stack will continue to grow during this loop. 580 // However, it is only processing functions (which 581 // are processed in a delayed fashion) that may 582 // add more actions (such as nested functions), so 583 // this is a sufficiently bounded process. 584 savedVersion := check.version 585 for i := top; i < len(check.delayed); i++ { 586 a := &check.delayed[i] 587 if check.conf._Trace { 588 if a.desc != nil { 589 check.trace(a.desc.pos.Pos(), "-- "+a.desc.format, a.desc.args...) 590 } else { 591 check.trace(nopos, "-- delayed %p", a.f) 592 } 593 } 594 check.version = a.version // reestablish the effective Go version captured earlier 595 a.f() // may append to check.delayed 596 597 if check.conf._Trace { 598 fmt.Println() 599 } 600 } 601 assert(top <= len(check.delayed)) // stack must not have shrunk 602 check.delayed = check.delayed[:top] 603 check.version = savedVersion 604 } 605 606 // cleanup runs cleanup for all collected cleaners. 607 func (check *Checker) cleanup() { 608 // Don't use a range clause since Named.cleanup may add more cleaners. 609 for i := 0; i < len(check.cleaners); i++ { 610 check.cleaners[i].cleanup() 611 } 612 check.cleaners = nil 613 } 614 615 // go/types doesn't support recording of types directly in the AST. 616 // dummy function to match types2 code. 617 func (check *Checker) recordTypeAndValueInSyntax(x ast.Expr, mode operandMode, typ Type, val constant.Value) { 618 // nothing to do 619 } 620 621 // go/types doesn't support recording of types directly in the AST. 622 // dummy function to match types2 code. 623 func (check *Checker) recordCommaOkTypesInSyntax(x ast.Expr, t0, t1 Type) { 624 // nothing to do 625 } 626 627 // instantiatedIdent determines the identifier of the type instantiated in expr. 628 // Helper function for recordInstance in recording.go. 629 func instantiatedIdent(expr ast.Expr) *ast.Ident { 630 var selOrIdent ast.Expr 631 switch e := expr.(type) { 632 case *ast.IndexExpr: 633 selOrIdent = e.X 634 case *ast.IndexListExpr: // only exists in go/ast, not syntax 635 selOrIdent = e.X 636 case *ast.SelectorExpr, *ast.Ident: 637 selOrIdent = e 638 } 639 switch x := selOrIdent.(type) { 640 case *ast.Ident: 641 return x 642 case *ast.SelectorExpr: 643 return x.Sel 644 } 645 646 // extra debugging of go.dev/issue/63933 647 panic(sprintf(nil, nil, true, "instantiated ident not found; please report: %s", expr)) 648 } 649