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