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.
8 "cmd/compile/internal/syntax"
13 // Type-checking Named types is subtle, because they may be recursively
14 // defined, and because their full details may be spread across multiple
15 // declarations (via methods). For this reason they are type-checked lazily,
16 // to avoid information being accessed before it is complete.
18 // Conceptually, it is helpful to think of named types as having two distinct
19 // sets of information:
20 // - "LHS" information, defining their identity: Obj() and TypeArgs()
21 // - "RHS" information, defining their details: TypeParams(), Underlying(),
24 // In this taxonomy, LHS information is available immediately, but RHS
25 // information is lazy. Specifically, a named type N may be constructed in any
26 // of the following ways:
27 // 1. type-checked from the source
28 // 2. loaded eagerly from export data
29 // 3. loaded lazily from export data (when using unified IR)
30 // 4. instantiated from a generic type
32 // In cases 1, 3, and 4, it is possible that the underlying type or methods of
33 // N may not be immediately available.
34 // - During type-checking, we allocate N before type-checking its underlying
35 // type or methods, so that we may resolve recursive references.
36 // - When loading from export data, we may load its methods and underlying
37 // type lazily using a provided load function.
38 // - After instantiating, we lazily expand the underlying type and methods
39 // (note that instances may be created while still in the process of
40 // type-checking the original type declaration).
42 // In cases 3 and 4 this lazy construction may also occur concurrently, due to
43 // concurrent use of the type checker API (after type checking or importing has
44 // finished). It is critical that we keep track of state, so that Named types
45 // are constructed exactly once and so that we do not access their details too
48 // We achieve this by tracking state with an atomic state variable, and
49 // guarding potentially concurrent calculations with a mutex. At any point in
50 // time this state variable determines which data on N may be accessed. As
51 // state monotonically progresses, any data available at state M may be
52 // accessed without acquiring the mutex at state N, provided N >= M.
54 // GLOSSARY: Here are a few terms used in this file to describe Named types:
55 // - We say that a Named type is "instantiated" if it has been constructed by
56 // instantiating a generic named type with type arguments.
57 // - We say that a Named type is "declared" if it corresponds to a type
58 // declaration in the source. Instantiated named types correspond to a type
59 // instantiation in the source, not a declaration. But their Origin type is
61 // - We say that a Named type is "resolved" if its RHS information has been
62 // loaded or fully type-checked. For Named types constructed from export
63 // data, this may involve invoking a loader function to extract information
64 // from export data. For instantiated named types this involves reading
65 // information from their origin.
66 // - We say that a Named type is "expanded" if it is an instantiated type and
67 // type parameters in its underlying type and methods have been substituted
68 // with the type arguments from the instantiation. A type may be partially
69 // expanded if some but not all of these details have been substituted.
70 // Similarly, we refer to these individual details (underlying type or
71 // method) as being "expanded".
72 // - When all information is known for a named type, we say it is "complete".
74 // Some invariants to keep in mind: each declared Named type has a single
75 // corresponding object, and that object's type is the (possibly generic) Named
76 // type. Declared Named types are identical if and only if their pointers are
77 // identical. On the other hand, multiple instantiated Named types may be
78 // identical even though their pointers are not identical. One has to use
79 // Identical to compare them. For instantiated named types, their obj is a
80 // synthetic placeholder that records their position of the corresponding
81 // instantiation in the source (if they were constructed during type checking).
83 // To prevent infinite expansion of named instances that are created outside of
84 // type-checking, instances share a Context with other instances created during
85 // their expansion. Via the pidgeonhole principle, this guarantees that in the
86 // presence of a cycle of named types, expansion will eventually find an
87 // existing instance in the Context and short-circuit the expansion.
89 // Once an instance is complete, we can nil out this shared Context to unpin
90 // memory, though this Context may still be held by other incomplete instances
93 // A Named represents a named (defined) type.
95 check *Checker // non-nil during type-checking; nil otherwise
96 obj *TypeName // corresponding declared object for declared types; see above for instantiated types
98 // fromRHS holds the type (on RHS of declaration) this *Named type is derived
99 // from (for cycle reporting). Only used by validType, and therefore does not
100 // require synchronization.
103 // information for instantiated types; nil otherwise
106 mu sync.Mutex // guards all fields below
107 state_ uint32 // the current state of this type; must only be accessed atomically
108 underlying Type // possibly a *Named during setup; never a *Named once set up completely
109 tparams *TypeParamList // type parameters, or nil
111 // methods declared for this type (not the method set of this type)
112 // Signatures are type-checked lazily.
113 // For non-instantiated types, this is a fully populated list of methods. For
114 // instantiated types, methods are individually expanded when they are first
118 // loader may be provided to lazily load type parameters, underlying type, and methods.
119 loader func(*Named) (tparams []*TypeParam, underlying Type, methods []*Func)
122 // instance holds information that is only necessary for instantiated named
124 type instance struct {
125 orig *Named // original, uninstantiated type
126 targs *TypeList // type arguments
127 expandedMethods int // number of expanded methods; expandedMethods <= len(orig.methods)
128 ctxt *Context // local Context; set to nil after full expansion
131 // namedState represents the possible states that a named type may assume.
132 type namedState uint32
135 unresolved namedState = iota // tparams, underlying type and methods might be unavailable
136 resolved // resolve has run; methods might be incomplete (for instances)
137 complete // all data is known
140 // NewNamed returns a new named type for the given type name, underlying type, and associated methods.
141 // If the given type name obj doesn't have a type yet, its type is set to the returned named type.
142 // The underlying type must not be a *Named.
143 func NewNamed(obj *TypeName, underlying Type, methods []*Func) *Named {
144 if asNamed(underlying) != nil {
145 panic("underlying type must not be *Named")
147 return (*Checker)(nil).newNamed(obj, underlying, methods)
150 // resolve resolves the type parameters, methods, and underlying type of n.
151 // This information may be loaded from a provided loader function, or computed
152 // from an origin type (in the case of instances).
154 // After resolution, the type parameters, methods, and underlying type of n are
155 // accessible; but if n is an instantiated type, its methods may still be
157 func (n *Named) resolve() *Named {
158 if n.state() >= resolved { // avoid locking below
162 // TODO(rfindley): if n.check is non-nil we can avoid locking here, since
163 // type-checking is not concurrent. Evaluate if this is worth doing.
167 if n.state() >= resolved {
172 assert(n.underlying == nil) // n is an unresolved instance
173 assert(n.loader == nil) // instances are created by instantiation, in which case n.loader is nil
177 underlying := n.expandUnderlying()
179 n.tparams = orig.tparams
180 n.underlying = underlying
181 n.fromRHS = orig.fromRHS // for cycle detection
183 if len(orig.methods) == 0 {
184 n.setState(complete) // nothing further to do
192 // TODO(mdempsky): Since we're passing n to the loader anyway
193 // (necessary because types2 expects the receiver type for methods
194 // on defined interface types to be the Named rather than the
195 // underlying Interface), maybe it should just handle calling
196 // SetTypeParams, SetUnderlying, and AddMethod instead? Those
197 // methods would need to support reentrant calls though. It would
198 // also make the API more future-proof towards further extensions.
200 assert(n.underlying == nil)
201 assert(n.TypeArgs().Len() == 0) // instances are created by instantiation, in which case n.loader is nil
203 tparams, underlying, methods := n.loader(n)
205 n.tparams = bindTParams(tparams)
206 n.underlying = underlying
207 n.fromRHS = underlying // for cycle detection
216 // state atomically accesses the current state of the receiver.
217 func (n *Named) state() namedState {
218 return namedState(atomic.LoadUint32(&n.state_))
221 // setState atomically stores the given state for n.
222 // Must only be called while holding n.mu.
223 func (n *Named) setState(state namedState) {
224 atomic.StoreUint32(&n.state_, uint32(state))
227 // newNamed is like NewNamed but with a *Checker receiver.
228 func (check *Checker) newNamed(obj *TypeName, underlying Type, methods []*Func) *Named {
229 typ := &Named{check: check, obj: obj, fromRHS: underlying, underlying: underlying, methods: methods}
233 // Ensure that typ is always sanity-checked.
235 check.needsCleanup(typ)
240 // newNamedInstance creates a new named instance for the given origin and type
241 // arguments, recording pos as the position of its synthetic object (for error
244 // If set, expanding is the named type instance currently being expanded, that
245 // led to the creation of this instance.
246 func (check *Checker) newNamedInstance(pos syntax.Pos, orig *Named, targs []Type, expanding *Named) *Named {
247 assert(len(targs) > 0)
249 obj := NewTypeName(pos, orig.obj.pkg, orig.obj.name, nil)
250 inst := &instance{orig: orig, targs: newTypeList(targs)}
252 // Only pass the expanding context to the new instance if their packages
253 // match. Since type reference cycles are only possible within a single
254 // package, this is sufficient for the purposes of short-circuiting cycles.
255 // Avoiding passing the context in other cases prevents unnecessary coupling
256 // of types across packages.
257 if expanding != nil && expanding.Obj().pkg == obj.pkg {
258 inst.ctxt = expanding.inst.ctxt
260 typ := &Named{check: check, obj: obj, inst: inst}
262 // Ensure that typ is always sanity-checked.
264 check.needsCleanup(typ)
269 func (t *Named) cleanup() {
270 assert(t.inst == nil || t.inst.orig.inst == nil)
271 // Ensure that every defined type created in the course of type-checking has
272 // either non-*Named underlying type, or is unexpanded.
274 // This guarantees that we don't leak any types whose underlying type is
275 // *Named, because any unexpanded instances will lazily compute their
276 // underlying type by substituting in the underlying type of their origin.
277 // The origin must have either been imported or type-checked and expanded
278 // here, and in either case its underlying type will be fully expanded.
279 switch t.underlying.(type) {
281 if t.TypeArgs().Len() == 0 {
282 panic("nil underlying")
285 t.under() // t.under may add entries to check.cleaners
290 // Obj returns the type name for the declaration defining the named type t. For
291 // instantiated types, this is same as the type name of the origin type.
292 func (t *Named) Obj() *TypeName {
296 return t.inst.orig.obj
299 // Origin returns the generic type from which the named type t is
300 // instantiated. If t is not an instantiated type, the result is t.
301 func (t *Named) Origin() *Named {
308 // TypeParams returns the type parameters of the named type t, or nil.
309 // The result is non-nil for an (originally) generic type even if it is instantiated.
310 func (t *Named) TypeParams() *TypeParamList { return t.resolve().tparams }
312 // SetTypeParams sets the type parameters of the named type t.
313 // t must not have type arguments.
314 func (t *Named) SetTypeParams(tparams []*TypeParam) {
315 assert(t.inst == nil)
316 t.resolve().tparams = bindTParams(tparams)
319 // TypeArgs returns the type arguments used to instantiate the named type t.
320 func (t *Named) TypeArgs() *TypeList {
327 // NumMethods returns the number of explicit methods defined for t.
328 func (t *Named) NumMethods() int {
329 return len(t.Origin().resolve().methods)
332 // Method returns the i'th method of named type t for 0 <= i < t.NumMethods().
334 // For an ordinary or instantiated type t, the receiver base type of this
335 // method is the named type t. For an uninstantiated generic type t, each
336 // method receiver is instantiated with its receiver type parameters.
337 func (t *Named) Method(i int) *Func {
340 if t.state() >= complete {
344 assert(t.inst != nil) // only instances should have incomplete methods
350 if len(t.methods) != len(orig.methods) {
351 assert(len(t.methods) == 0)
352 t.methods = make([]*Func, len(orig.methods))
355 if t.methods[i] == nil {
356 assert(t.inst.ctxt != nil) // we should still have a context remaining from the resolution phase
357 t.methods[i] = t.expandMethod(i)
358 t.inst.expandedMethods++
360 // Check if we've created all methods at this point. If we have, mark the
361 // type as fully expanded.
362 if t.inst.expandedMethods == len(orig.methods) {
364 t.inst.ctxt = nil // no need for a context anymore
371 // expandMethod substitutes type arguments in the i'th method for an
372 // instantiated receiver.
373 func (t *Named) expandMethod(i int) *Func {
374 // t.orig.methods is not lazy. origm is the method instantiated with its
375 // receiver type parameters (the "origin" method).
376 origm := t.inst.orig.Method(i)
380 // Ensure that the original method is type-checked.
382 check.objDecl(origm, nil)
385 origSig := origm.typ.(*Signature)
386 rbase, _ := deref(origSig.Recv().Type())
388 // If rbase is t, then origm is already the instantiated method we're looking
389 // for. In this case, we return origm to preserve the invariant that
390 // traversing Method->Receiver Type->Method should get back to the same
393 // This occurs if t is instantiated with the receiver type parameters, as in
394 // the use of m in func (r T[_]) m() { r.m() }.
400 // We can only substitute if we have a correspondence between type arguments
401 // and type parameters. This check is necessary in the presence of invalid
403 if origSig.RecvTypeParams().Len() == t.inst.targs.Len() {
404 smap := makeSubstMap(origSig.RecvTypeParams().list(), t.inst.targs.list())
407 ctxt = check.context()
409 sig = check.subst(origm.pos, origSig, smap, t, ctxt).(*Signature)
413 // No substitution occurred, but we still need to create a new signature to
414 // hold the instantiated receiver.
420 if origm.hasPtrRecv() {
426 sig.recv = substVar(origSig.recv, rtyp)
427 return substFunc(origm, sig)
430 // SetUnderlying sets the underlying type and marks t as complete.
431 // t must not have type arguments.
432 func (t *Named) SetUnderlying(underlying Type) {
433 assert(t.inst == nil)
434 if underlying == nil {
435 panic("underlying type must not be nil")
437 if asNamed(underlying) != nil {
438 panic("underlying type must not be *Named")
440 t.resolve().underlying = underlying
441 if t.fromRHS == nil {
442 t.fromRHS = underlying // for cycle detection
446 // AddMethod adds method m unless it is already in the method list.
447 // t must not have type arguments.
448 func (t *Named) AddMethod(m *Func) {
449 assert(t.inst == nil)
451 if i, _ := lookupMethod(t.methods, m.pkg, m.name, false); i < 0 {
452 t.methods = append(t.methods, m)
456 // TODO(gri) Investigate if Unalias can be moved to where underlying is set.
457 func (t *Named) Underlying() Type { return Unalias(t.resolve().underlying) }
458 func (t *Named) String() string { return TypeString(t, nil) }
460 // ----------------------------------------------------------------------------
463 // TODO(rfindley): reorganize the loading and expansion methods under this
466 // under returns the expanded underlying type of n0; possibly by following
467 // forward chains of named types. If an underlying type is found, resolve
468 // the chain by setting the underlying type for each defined type in the
469 // chain before returning it. If no underlying type is found or a cycle
470 // is detected, the result is Typ[Invalid]. If a cycle is detected and
471 // n0.check != nil, the cycle is reported.
473 // This is necessary because the underlying type of named may be itself a
474 // named type that is incomplete:
482 // The type of C is the (named) type of A which is incomplete,
483 // and which has as its underlying type the named type B.
484 func (n0 *Named) under() Type {
487 // If the underlying type of a defined type is not a defined
488 // (incl. instance) type, then that is the desired underlying
491 switch u1 := u.(type) {
493 // After expansion via Underlying(), we should never encounter a nil
495 panic("nil underlying")
505 panic("Named.check == nil but type is incomplete")
508 // Invariant: after this point n0 as well as any named types in its
509 // underlying chain should be set up when this function exits.
513 seen := make(map[*Named]int) // types that need their underlying type resolved
514 var path []Object // objects encountered, for cycle reporting
519 path = append(path, n.obj)
521 if i, ok := seen[n]; ok {
523 check.cycleError(path[i:])
528 switch u1 := u.(type) {
535 // Continue collecting *Named types in the chain.
540 for n := range seen {
541 // We should never have to update the underlying type of an imported type;
542 // those underlying types should have been resolved during the import.
543 // Also, doing so would lead to a race condition (was go.dev/issue/31749).
544 // Do this check always, not just in debug mode (it's cheap).
545 if n.obj.pkg != check.pkg {
546 panic("imported type with unresolved underlying type")
554 func (n *Named) lookupMethod(pkg *Package, name string, foldCase bool) (int, *Func) {
556 // If n is an instance, we may not have yet instantiated all of its methods.
557 // Look up the method index in orig, and only instantiate method at the
558 // matching index (if any).
559 i, _ := lookupMethod(n.Origin().methods, pkg, name, foldCase)
563 // For instances, m.Method(i) will be different from the orig method.
564 return i, n.Method(i)
567 // context returns the type-checker context.
568 func (check *Checker) context() *Context {
569 if check.ctxt == nil {
570 check.ctxt = NewContext()
575 // expandUnderlying substitutes type arguments in the underlying type n.orig,
576 // returning the result. Returns Typ[Invalid] if there was an error.
577 func (n *Named) expandUnderlying() Type {
579 if check != nil && check.conf.Trace {
580 check.trace(n.obj.pos, "-- Named.expandUnderlying %s", n)
584 check.trace(n.obj.pos, "=> %s (tparams = %s, under = %s)", n, n.tparams.list(), n.underlying)
588 assert(n.inst.orig.underlying != nil)
589 if n.inst.ctxt == nil {
590 n.inst.ctxt = NewContext()
594 targs := n.inst.targs
596 if asNamed(orig.underlying) != nil {
597 // We should only get a Named underlying type here during type checking
598 // (for example, in recursive type declarations).
602 if orig.tparams.Len() != targs.Len() {
603 // Mismatching arg and tparam length may be checked elsewhere.
607 // Ensure that an instance is recorded before substituting, so that we
608 // resolve n for any recursive references.
609 h := n.inst.ctxt.instanceHash(orig, targs.list())
610 n2 := n.inst.ctxt.update(h, orig, n.TypeArgs().list(), n)
613 smap := makeSubstMap(orig.tparams.list(), targs.list())
616 ctxt = check.context()
618 underlying := n.check.subst(n.obj.pos, orig.underlying, smap, n, ctxt)
619 // If the underlying type of n is an interface, we need to set the receiver of
620 // its methods accurately -- we set the receiver of interface methods on
621 // the RHS of a type declaration to the defined type.
622 if iface, _ := underlying.(*Interface); iface != nil {
623 if methods, copied := replaceRecvType(iface.methods, orig, n); copied {
624 // If the underlying type doesn't actually use type parameters, it's
625 // possible that it wasn't substituted. In this case we need to create
626 // a new *Interface before modifying receivers.
627 if iface == orig.underlying {
629 iface = check.newInterface()
630 iface.embeddeds = old.embeddeds
631 assert(old.complete) // otherwise we are copying incomplete data
632 iface.complete = old.complete
633 iface.implicit = old.implicit // should be false but be conservative
636 iface.methods = methods
637 iface.tset = nil // recompute type set with new methods
639 // If check != nil, check.newInterface will have saved the interface for later completion.
640 if check == nil { // golang/go#61561: all newly created interfaces must be fully evaluated
649 // safeUnderlying returns the underlying type of typ without expanding
650 // instances, to avoid infinite recursion.
652 // TODO(rfindley): eliminate this function or give it a better name.
653 func safeUnderlying(typ Type) Type {
654 if t := asNamed(typ); t != nil {
657 return typ.Underlying()