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