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