Source file src/cmd/compile/internal/types2/validtype.go
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. 4 5 package types2 6 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) 13 } 14 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) { 27 case nil: 28 // We should never see a nil type but be conservative and panic 29 // only in debug mode. 30 if debug { 31 panic("validType0(nil)") 32 } 33 34 case *Array: 35 return check.validType0(t.elem, nest, path) 36 37 case *Struct: 38 for _, f := range t.fields { 39 if !check.validType0(f.typ, nest, path) { 40 return false 41 } 42 } 43 44 case *Union: 45 for _, t := range t.terms { 46 if !check.validType0(t.typ, nest, path) { 47 return false 48 } 49 } 50 51 case *Interface: 52 for _, etyp := range t.embeddeds { 53 if !check.validType0(etyp, nest, path) { 54 return false 55 } 56 } 57 58 case *Named: 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 63 // validType call.) 64 if check.valids.lookup(t) != nil { 65 break 66 } 67 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()) { 72 return false 73 } 74 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 { 78 if Identical(e, t) { 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 86 // present. 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] 104 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 { 111 if Identical(p, t) { 112 check.cycleError(makeObjList(path[start:])) 113 return false 114 } 115 } 116 panic("cycle start not found") 117 } 118 } 119 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)) { 125 return false 126 } 127 128 check.valids.add(t) // t is valid 129 130 case *TypeParam: 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. 134 if len(nest) > 0 { 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) 150 } 151 } 152 } 153 } 154 155 return true 156 } 157 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 { 163 olist[i] = t.obj 164 } 165 return olist 166 } 167 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 171 // 172 // var _ A[A[string]] 173 // 174 // type A[P any] struct { _ B[P] } 175 // type B[P any] struct { _ P } 176 // 177 // we want to determine if the type A[A[string]] is valid. 178 // We start evaluating A[A[string]] outside any type nest: 179 // 180 // A[A[string]] 181 // nest = 182 // path = 183 // 184 // The RHS of A is now evaluated in the A[A[string]] nest: 185 // 186 // struct{_ B[P₁]} 187 // nest = A[A[string]] 188 // path = A[A[string]] 189 // 190 // The struct has a single field of type B[P₁] with which 191 // we continue: 192 // 193 // B[P₁] 194 // nest = A[A[string]] 195 // path = A[A[string]] 196 // 197 // struct{_ P₂} 198 // nest = A[A[string]]->B[P] 199 // path = A[A[string]]->B[P] 200 // 201 // Eventually we reach the type parameter P of type B (P₂): 202 // 203 // P₂ 204 // nest = A[A[string]]->B[P] 205 // path = A[A[string]]->B[P] 206 // 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 209 // instantiated: 210 // 211 // P₁ 212 // nest = A[A[string]] <== type nest at B's instantiation time 213 // path = A[A[string]]->B[P] 214 // 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 219 // nest is empty: 220 // 221 // A[string] 222 // nest = <== type nest at A's instantiation time 223 // path = A[A[string]]->B[P] 224 // 225 // Evaluation then proceeds as before for A[string]: 226 // 227 // struct{_ B[P₁]} 228 // nest = A[string] 229 // path = A[A[string]]->B[P]->A[string] 230 // 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 234 // A[string]: 235 // 236 // B[P₁] 237 // nest = A[string] 238 // path = A[A[string]]->B[P]->A[string] <== path contains B[P]! 239 // 240 // But because we use the correct type nest, evaluation proceeds without 241 // errors and we get the evaluation sequence: 242 // 243 // struct{_ P₂} 244 // nest = A[string]->B[P] 245 // path = A[A[string]]->B[P]->A[string]->B[P] 246 // P₂ 247 // nest = A[string]->B[P] 248 // path = A[A[string]]->B[P]->A[string]->B[P] 249 // P₁ 250 // nest = A[string] 251 // path = A[A[string]]->B[P]->A[string]->B[P] 252 // string 253 // nest = 254 // path = A[A[string]]->B[P]->A[string]->B[P] 255 // 256 // At this point we're done and A[A[string]] and is valid. 257