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