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