1 // Copyright 2022 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.
7 // validType verifies that the given type does not "expand" indefinitely
8 // producing a cycle in the type graph.
9 // (Cycles involving alias types, as in "type A = [10]A" are detected
10 // earlier, via the objDecl cycle detection mechanism.)
11 func (check *Checker) validType(typ *Named) {
12 check.validType0(typ, nil, nil)
15 // validType0 checks if the given type is valid. If typ is a type parameter
16 // its value is looked up in the type argument list of the instantiated
17 // (enclosing) type, if it exists. Otherwise the type parameter must be from
18 // an enclosing function and can be ignored.
19 // The nest list describes the stack (the "nest in memory") of types which
20 // contain (or embed in the case of interfaces) other types. For instance, a
21 // struct named S which contains a field of named type F contains (the memory
22 // of) F in S, leading to the nest S->F. If a type appears in its own nest
23 // (say S->F->S) we have an invalid recursive type. The path list is the full
24 // path of named types in a cycle, it is only needed for error reporting.
25 func (check *Checker) validType0(typ Type, nest, path []*Named) bool {
26 switch t := _Unalias(typ).(type) {
28 // We should never see a nil type but be conservative and panic
29 // only in debug mode.
31 panic("validType0(nil)")
35 return check.validType0(t.elem, nest, path)
38 for _, f := range t.fields {
39 if !check.validType0(f.typ, nest, path) {
45 for _, t := range t.terms {
46 if !check.validType0(t.typ, nest, path) {
52 for _, etyp := range t.embeddeds {
53 if !check.validType0(etyp, nest, path) {
59 // Exit early if we already know t is valid.
60 // This is purely an optimization but it prevents excessive computation
61 // times in pathological cases such as testdata/fixedbugs/issue6977.go.
62 // (Note: The valids map could also be allocated locally, once for each
64 if check.valids.lookup(t) != nil {
68 // Don't report a 2nd error if we already know the type is invalid
69 // (e.g., if a cycle was detected earlier, via under).
70 // Note: ensure that t.orig is fully resolved by calling Underlying().
71 if !isValid(t.Underlying()) {
75 // If the current type t is also found in nest, (the memory of) t is
76 // embedded in itself, indicating an invalid recursive type.
77 for _, e := range nest {
79 // We have a cycle. If t != t.Origin() then t is an instance of
80 // the generic type t.Origin(). Because t is in the nest, t must
81 // occur within the definition (RHS) of the generic type t.Origin(),
82 // directly or indirectly, after expansion of the RHS.
83 // Therefore t.Origin() must be invalid, no matter how it is
84 // instantiated since the instantiation t of t.Origin() happens
85 // inside t.Origin()'s RHS and thus is always the same and always
87 // Therefore we can mark the underlying of both t and t.Origin()
88 // as invalid. If t is not an instance of a generic type, t and
89 // t.Origin() are the same.
90 // Furthermore, because we check all types in a package for validity
91 // before type checking is complete, any exported type that is invalid
92 // will have an invalid underlying type and we can't reach here with
93 // such a type (invalid types are excluded above).
94 // Thus, if we reach here with a type t, both t and t.Origin() (if
95 // different in the first place) must be from the current package;
96 // they cannot have been imported.
97 // Therefore it is safe to change their underlying types; there is
98 // no chance for a race condition (the types of the current package
99 // are not yet available to other goroutines).
100 assert(t.obj.pkg == check.pkg)
101 assert(t.Origin().obj.pkg == check.pkg)
102 t.underlying = Typ[Invalid]
103 t.Origin().underlying = Typ[Invalid]
105 // Find the starting point of the cycle and report it.
106 // Because each type in nest must also appear in path (see invariant below),
107 // type t must be in path since it was found in nest. But not every type in path
108 // is in nest. Specifically t may appear in path with an earlier index than the
109 // index of t in nest. Search again.
110 for start, p := range path {
112 check.cycleError(makeObjList(path[start:]))
116 panic("cycle start not found")
120 // No cycle was found. Check the RHS of t.
121 // Every type added to nest is also added to path; thus every type that is in nest
122 // must also be in path (invariant). But not every type in path is in nest, since
123 // nest may be pruned (see below, *TypeParam case).
124 if !check.validType0(t.Origin().fromRHS, append(nest, t), append(path, t)) {
128 check.valids.add(t) // t is valid
131 // A type parameter stands for the type (argument) it was instantiated with.
132 // Check the corresponding type argument for validity if we are in an
133 // instantiated type.
135 inst := nest[len(nest)-1] // the type instance
136 // Find the corresponding type argument for the type parameter
137 // and proceed with checking that type argument.
138 for i, tparam := range inst.TypeParams().list() {
139 // The type parameter and type argument lists should
140 // match in length but be careful in case of errors.
141 if t == tparam && i < inst.TypeArgs().Len() {
142 targ := inst.TypeArgs().At(i)
143 // The type argument must be valid in the enclosing
144 // type (where inst was instantiated), hence we must
145 // check targ's validity in the type nest excluding
146 // the current (instantiated) type (see the example
147 // at the end of this file).
148 // For error reporting we keep the full path.
149 return check.validType0(targ, nest[:len(nest)-1], path)
158 // makeObjList returns the list of type name objects for the given
159 // list of named types.
160 func makeObjList(tlist []*Named) []Object {
161 olist := make([]Object, len(tlist))
162 for i, t := range tlist {
168 // Here is an example illustrating why we need to exclude the
169 // instantiated type from nest when evaluating the validity of
170 // a type parameter. Given the declarations
172 // var _ A[A[string]]
174 // type A[P any] struct { _ B[P] }
175 // type B[P any] struct { _ P }
177 // we want to determine if the type A[A[string]] is valid.
178 // We start evaluating A[A[string]] outside any type nest:
184 // The RHS of A is now evaluated in the A[A[string]] nest:
187 // nest = A[A[string]]
188 // path = A[A[string]]
190 // The struct has a single field of type B[P₁] with which
194 // nest = A[A[string]]
195 // path = A[A[string]]
198 // nest = A[A[string]]->B[P]
199 // path = A[A[string]]->B[P]
201 // Eventually we reach the type parameter P of type B (P₂):
204 // nest = A[A[string]]->B[P]
205 // path = A[A[string]]->B[P]
207 // The type argument for P of B is the type parameter P of A (P₁).
208 // It must be evaluated in the type nest that existed when B was
212 // nest = A[A[string]] <== type nest at B's instantiation time
213 // path = A[A[string]]->B[P]
215 // If we'd use the current nest it would correspond to the path
216 // which will be wrong as we will see shortly. P's type argument
217 // is A[string], which again must be evaluated in the type nest
218 // that existed when A was instantiated with A[string]. That type
222 // nest = <== type nest at A's instantiation time
223 // path = A[A[string]]->B[P]
225 // Evaluation then proceeds as before for A[string]:
229 // path = A[A[string]]->B[P]->A[string]
231 // Now we reach B[P] again. If we had not adjusted nest, it would
232 // correspond to path, and we would find B[P] in nest, indicating
233 // a cycle, which would clearly be wrong since there's no cycle in
238 // path = A[A[string]]->B[P]->A[string] <== path contains B[P]!
240 // But because we use the correct type nest, evaluation proceeds without
241 // errors and we get the evaluation sequence:
244 // nest = A[string]->B[P]
245 // path = A[A[string]]->B[P]->A[string]->B[P]
247 // nest = A[string]->B[P]
248 // path = A[A[string]]->B[P]->A[string]->B[P]
251 // path = A[A[string]]->B[P]->A[string]->B[P]
254 // path = A[A[string]]->B[P]->A[string]->B[P]
256 // At this point we're done and A[A[string]] and is valid.