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