Source file src/go/types/validtype.go
1 // Code generated by "go test -run=Generate -write=all"; DO NOT EDIT. 2 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. 6 7 package types 8 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) 15 } 16 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 := Unalias(typ).(type) { 29 case nil: 30 // We should never see a nil type but be conservative and panic 31 // only in debug mode. 32 if debug { 33 panic("validType0(nil)") 34 } 35 36 case *Array: 37 return check.validType0(t.elem, nest, path) 38 39 case *Struct: 40 for _, f := range t.fields { 41 if !check.validType0(f.typ, nest, path) { 42 return false 43 } 44 } 45 46 case *Union: 47 for _, t := range t.terms { 48 if !check.validType0(t.typ, nest, path) { 49 return false 50 } 51 } 52 53 case *Interface: 54 for _, etyp := range t.embeddeds { 55 if !check.validType0(etyp, nest, path) { 56 return false 57 } 58 } 59 60 case *Named: 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 65 // validType call.) 66 if check.valids.lookup(t) != nil { 67 break 68 } 69 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()) { 74 return false 75 } 76 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 { 80 if Identical(e, t) { 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 88 // present. 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] 106 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 { 113 if Identical(p, t) { 114 check.cycleError(makeObjList(path[start:])) 115 return false 116 } 117 } 118 panic("cycle start not found") 119 } 120 } 121 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)) { 127 return false 128 } 129 130 check.valids.add(t) // t is valid 131 132 case *TypeParam: 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. 136 if len(nest) > 0 { 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) 152 } 153 } 154 } 155 } 156 157 return true 158 } 159 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 { 165 olist[i] = t.obj 166 } 167 return olist 168 } 169 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 173 // 174 // var _ A[A[string]] 175 // 176 // type A[P any] struct { _ B[P] } 177 // type B[P any] struct { _ P } 178 // 179 // we want to determine if the type A[A[string]] is valid. 180 // We start evaluating A[A[string]] outside any type nest: 181 // 182 // A[A[string]] 183 // nest = 184 // path = 185 // 186 // The RHS of A is now evaluated in the A[A[string]] nest: 187 // 188 // struct{_ B[P₁]} 189 // nest = A[A[string]] 190 // path = A[A[string]] 191 // 192 // The struct has a single field of type B[P₁] with which 193 // we continue: 194 // 195 // B[P₁] 196 // nest = A[A[string]] 197 // path = A[A[string]] 198 // 199 // struct{_ P₂} 200 // nest = A[A[string]]->B[P] 201 // path = A[A[string]]->B[P] 202 // 203 // Eventually we reach the type parameter P of type B (P₂): 204 // 205 // P₂ 206 // nest = A[A[string]]->B[P] 207 // path = A[A[string]]->B[P] 208 // 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 211 // instantiated: 212 // 213 // P₁ 214 // nest = A[A[string]] <== type nest at B's instantiation time 215 // path = A[A[string]]->B[P] 216 // 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 221 // nest is empty: 222 // 223 // A[string] 224 // nest = <== type nest at A's instantiation time 225 // path = A[A[string]]->B[P] 226 // 227 // Evaluation then proceeds as before for A[string]: 228 // 229 // struct{_ B[P₁]} 230 // nest = A[string] 231 // path = A[A[string]]->B[P]->A[string] 232 // 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 236 // A[string]: 237 // 238 // B[P₁] 239 // nest = A[string] 240 // path = A[A[string]]->B[P]->A[string] <== path contains B[P]! 241 // 242 // But because we use the correct type nest, evaluation proceeds without 243 // errors and we get the evaluation sequence: 244 // 245 // struct{_ P₂} 246 // nest = A[string]->B[P] 247 // path = A[A[string]]->B[P]->A[string]->B[P] 248 // P₂ 249 // nest = A[string]->B[P] 250 // path = A[A[string]]->B[P]->A[string]->B[P] 251 // P₁ 252 // nest = A[string] 253 // path = A[A[string]]->B[P]->A[string]->B[P] 254 // string 255 // nest = 256 // path = A[A[string]]->B[P]->A[string]->B[P] 257 // 258 // At this point we're done and A[A[string]] and is valid. 259