1 // Code generated by "go test -run=Generate -write=all"; DO NOT EDIT.
3 // Copyright 2022 The Go Authors. All rights reserved.
4 // Use of this source code is governed by a BSD-style
5 // license that can be found in the LICENSE file.
9 // validType verifies that the given type does not "expand" indefinitely
10 // producing a cycle in the type graph.
11 // (Cycles involving alias types, as in "type A = [10]A" are detected
12 // earlier, via the objDecl cycle detection mechanism.)
13 func (check *Checker) validType(typ *Named) {
14 check.validType0(typ, nil, nil)
17 // validType0 checks if the given type is valid. If typ is a type parameter
18 // its value is looked up in the type argument list of the instantiated
19 // (enclosing) type, if it exists. Otherwise the type parameter must be from
20 // an enclosing function and can be ignored.
21 // The nest list describes the stack (the "nest in memory") of types which
22 // contain (or embed in the case of interfaces) other types. For instance, a
23 // struct named S which contains a field of named type F contains (the memory
24 // of) F in S, leading to the nest S->F. If a type appears in its own nest
25 // (say S->F->S) we have an invalid recursive type. The path list is the full
26 // path of named types in a cycle, it is only needed for error reporting.
27 func (check *Checker) validType0(typ Type, nest, path []*Named) bool {
28 switch t := typ.(type) {
30 // We should never see a nil type but be conservative and panic
31 // only in debug mode.
33 panic("validType0(nil)")
37 return check.validType0(t.elem, nest, path)
40 for _, f := range t.fields {
41 if !check.validType0(f.typ, nest, path) {
47 for _, t := range t.terms {
48 if !check.validType0(t.typ, nest, path) {
54 for _, etyp := range t.embeddeds {
55 if !check.validType0(etyp, nest, path) {
61 // Exit early if we already know t is valid.
62 // This is purely an optimization but it prevents excessive computation
63 // times in pathological cases such as testdata/fixedbugs/issue6977.go.
64 // (Note: The valids map could also be allocated locally, once for each
66 if check.valids.lookup(t) != nil {
70 // Don't report a 2nd error if we already know the type is invalid
71 // (e.g., if a cycle was detected earlier, via under).
72 // Note: ensure that t.orig is fully resolved by calling Underlying().
73 if !isValid(t.Underlying()) {
77 // If the current type t is also found in nest, (the memory of) t is
78 // embedded in itself, indicating an invalid recursive type.
79 for _, e := range nest {
81 // We have a cycle. If t != t.Origin() then t is an instance of
82 // the generic type t.Origin(). Because t is in the nest, t must
83 // occur within the definition (RHS) of the generic type t.Origin(),
84 // directly or indirectly, after expansion of the RHS.
85 // Therefore t.Origin() must be invalid, no matter how it is
86 // instantiated since the instantiation t of t.Origin() happens
87 // inside t.Origin()'s RHS and thus is always the same and always
89 // Therefore we can mark the underlying of both t and t.Origin()
90 // as invalid. If t is not an instance of a generic type, t and
91 // t.Origin() are the same.
92 // Furthermore, because we check all types in a package for validity
93 // before type checking is complete, any exported type that is invalid
94 // will have an invalid underlying type and we can't reach here with
95 // such a type (invalid types are excluded above).
96 // Thus, if we reach here with a type t, both t and t.Origin() (if
97 // different in the first place) must be from the current package;
98 // they cannot have been imported.
99 // Therefore it is safe to change their underlying types; there is
100 // no chance for a race condition (the types of the current package
101 // are not yet available to other goroutines).
102 assert(t.obj.pkg == check.pkg)
103 assert(t.Origin().obj.pkg == check.pkg)
104 t.underlying = Typ[Invalid]
105 t.Origin().underlying = Typ[Invalid]
107 // Find the starting point of the cycle and report it.
108 // Because each type in nest must also appear in path (see invariant below),
109 // type t must be in path since it was found in nest. But not every type in path
110 // is in nest. Specifically t may appear in path with an earlier index than the
111 // index of t in nest. Search again.
112 for start, p := range path {
114 check.cycleError(makeObjList(path[start:]))
118 panic("cycle start not found")
122 // No cycle was found. Check the RHS of t.
123 // Every type added to nest is also added to path; thus every type that is in nest
124 // must also be in path (invariant). But not every type in path is in nest, since
125 // nest may be pruned (see below, *TypeParam case).
126 if !check.validType0(t.Origin().fromRHS, append(nest, t), append(path, t)) {
130 check.valids.add(t) // t is valid
133 // A type parameter stands for the type (argument) it was instantiated with.
134 // Check the corresponding type argument for validity if we are in an
135 // instantiated type.
137 inst := nest[len(nest)-1] // the type instance
138 // Find the corresponding type argument for the type parameter
139 // and proceed with checking that type argument.
140 for i, tparam := range inst.TypeParams().list() {
141 // The type parameter and type argument lists should
142 // match in length but be careful in case of errors.
143 if t == tparam && i < inst.TypeArgs().Len() {
144 targ := inst.TypeArgs().At(i)
145 // The type argument must be valid in the enclosing
146 // type (where inst was instantiated), hence we must
147 // check targ's validity in the type nest excluding
148 // the current (instantiated) type (see the example
149 // at the end of this file).
150 // For error reporting we keep the full path.
151 return check.validType0(targ, nest[:len(nest)-1], path)
160 // makeObjList returns the list of type name objects for the given
161 // list of named types.
162 func makeObjList(tlist []*Named) []Object {
163 olist := make([]Object, len(tlist))
164 for i, t := range tlist {
170 // Here is an example illustrating why we need to exclude the
171 // instantiated type from nest when evaluating the validity of
172 // a type parameter. Given the declarations
174 // var _ A[A[string]]
176 // type A[P any] struct { _ B[P] }
177 // type B[P any] struct { _ P }
179 // we want to determine if the type A[A[string]] is valid.
180 // We start evaluating A[A[string]] outside any type nest:
186 // The RHS of A is now evaluated in the A[A[string]] nest:
189 // nest = A[A[string]]
190 // path = A[A[string]]
192 // The struct has a single field of type B[P₁] with which
196 // nest = A[A[string]]
197 // path = A[A[string]]
200 // nest = A[A[string]]->B[P]
201 // path = A[A[string]]->B[P]
203 // Eventually we reach the type parameter P of type B (P₂):
206 // nest = A[A[string]]->B[P]
207 // path = A[A[string]]->B[P]
209 // The type argument for P of B is the type parameter P of A (P₁).
210 // It must be evaluated in the type nest that existed when B was
214 // nest = A[A[string]] <== type nest at B's instantiation time
215 // path = A[A[string]]->B[P]
217 // If we'd use the current nest it would correspond to the path
218 // which will be wrong as we will see shortly. P's type argument
219 // is A[string], which again must be evaluated in the type nest
220 // that existed when A was instantiated with A[string]. That type
224 // nest = <== type nest at A's instantiation time
225 // path = A[A[string]]->B[P]
227 // Evaluation then proceeds as before for A[string]:
231 // path = A[A[string]]->B[P]->A[string]
233 // Now we reach B[P] again. If we had not adjusted nest, it would
234 // correspond to path, and we would find B[P] in nest, indicating
235 // a cycle, which would clearly be wrong since there's no cycle in
240 // path = A[A[string]]->B[P]->A[string] <== path contains B[P]!
242 // But because we use the correct type nest, evaluation proceeds without
243 // errors and we get the evaluation sequence:
246 // nest = A[string]->B[P]
247 // path = A[A[string]]->B[P]->A[string]->B[P]
249 // nest = A[string]->B[P]
250 // path = A[A[string]]->B[P]->A[string]->B[P]
253 // path = A[A[string]]->B[P]->A[string]->B[P]
256 // path = A[A[string]]->B[P]->A[string]->B[P]
258 // At this point we're done and A[A[string]] and is valid.