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