Source file src/go/types/validtype.go
1 // Code generated by "go test -run=Generate -write=all"; DO NOT EDIT. 2 // Source: ../../cmd/compile/internal/types2/validtype.go 3 4 // Copyright 2022 The Go Authors. All rights reserved. 5 // Use of this source code is governed by a BSD-style 6 // license that can be found in the LICENSE file. 7 8 package types 9 10 import "go/token" 11 12 // validType verifies that the given type does not "expand" indefinitely 13 // producing a cycle in the type graph. 14 // (Cycles involving alias types, as in "type A = [10]A" are detected 15 // earlier, via the objDecl cycle detection mechanism.) 16 func (check *Checker) validType(typ *Named) { 17 check.validType0(nopos, typ, nil, nil) 18 } 19 20 // validType0 checks if the given type is valid. If typ is a type parameter 21 // its value is looked up in the type argument list of the instantiated 22 // (enclosing) type, if it exists. Otherwise the type parameter must be from 23 // an enclosing function and can be ignored. 24 // The nest list describes the stack (the "nest in memory") of types which 25 // contain (or embed in the case of interfaces) other types. For instance, a 26 // struct named S which contains a field of named type F contains (the memory 27 // of) F in S, leading to the nest S->F. If a type appears in its own nest 28 // (say S->F->S) we have an invalid recursive type. The path list is the full 29 // path of named types in a cycle, it is only needed for error reporting. 30 func (check *Checker) validType0(pos token.Pos, typ Type, nest, path []*Named) bool { 31 typ = Unalias(typ) 32 33 if check.conf._Trace { 34 if t, _ := typ.(*Named); t != nil && t.obj != nil /* obj should always exist but be conservative */ { 35 pos = t.obj.pos 36 } 37 check.indent++ 38 check.trace(pos, "validType(%s) nest %v, path %v", typ, pathString(makeObjList(nest)), pathString(makeObjList(path))) 39 defer func() { 40 check.indent-- 41 }() 42 } 43 44 switch t := typ.(type) { 45 case nil: 46 // We should never see a nil type but be conservative and panic 47 // only in debug mode. 48 if debug { 49 panic("validType0(nil)") 50 } 51 52 case *Array: 53 return check.validType0(pos, t.elem, nest, path) 54 55 case *Struct: 56 for _, f := range t.fields { 57 if !check.validType0(pos, f.typ, nest, path) { 58 return false 59 } 60 } 61 62 case *Union: 63 for _, t := range t.terms { 64 if !check.validType0(pos, t.typ, nest, path) { 65 return false 66 } 67 } 68 69 case *Interface: 70 for _, etyp := range t.embeddeds { 71 if !check.validType0(pos, etyp, nest, path) { 72 return false 73 } 74 } 75 76 case *Named: 77 // TODO(gri) The optimization below is incorrect (see go.dev/issue/65711): 78 // in that issue `type A[P any] [1]P` is a valid type on its own 79 // and the (uninstantiated) A is recorded in check.valids. As a 80 // consequence, when checking the remaining declarations, which 81 // are not valid, the validity check ends prematurely because A 82 // is considered valid, even though its validity depends on the 83 // type argument provided to it. 84 // 85 // A correct optimization is important for pathological cases. 86 // Keep code around for reference until we found an optimization. 87 // 88 // // Exit early if we already know t is valid. 89 // // This is purely an optimization but it prevents excessive computation 90 // // times in pathological cases such as testdata/fixedbugs/issue6977.go. 91 // // (Note: The valids map could also be allocated locally, once for each 92 // // validType call.) 93 // if check.valids.lookup(t) != nil { 94 // break 95 // } 96 97 // Don't report a 2nd error if we already know the type is invalid 98 // (e.g., if a cycle was detected earlier, via under). 99 // Note: ensure that t.orig is fully resolved by calling Underlying(). 100 if !isValid(t.Underlying()) { 101 return false 102 } 103 104 // If the current type t is also found in nest, (the memory of) t is 105 // embedded in itself, indicating an invalid recursive type. 106 for _, e := range nest { 107 if Identical(e, t) { 108 // We have a cycle. If t != t.Origin() then t is an instance of 109 // the generic type t.Origin(). Because t is in the nest, t must 110 // occur within the definition (RHS) of the generic type t.Origin(), 111 // directly or indirectly, after expansion of the RHS. 112 // Therefore t.Origin() must be invalid, no matter how it is 113 // instantiated since the instantiation t of t.Origin() happens 114 // inside t.Origin()'s RHS and thus is always the same and always 115 // present. 116 // Therefore we can mark the underlying of both t and t.Origin() 117 // as invalid. If t is not an instance of a generic type, t and 118 // t.Origin() are the same. 119 // Furthermore, because we check all types in a package for validity 120 // before type checking is complete, any exported type that is invalid 121 // will have an invalid underlying type and we can't reach here with 122 // such a type (invalid types are excluded above). 123 // Thus, if we reach here with a type t, both t and t.Origin() (if 124 // different in the first place) must be from the current package; 125 // they cannot have been imported. 126 // Therefore it is safe to change their underlying types; there is 127 // no chance for a race condition (the types of the current package 128 // are not yet available to other goroutines). 129 assert(t.obj.pkg == check.pkg) 130 assert(t.Origin().obj.pkg == check.pkg) 131 t.underlying = Typ[Invalid] 132 t.Origin().underlying = Typ[Invalid] 133 134 // Find the starting point of the cycle and report it. 135 // Because each type in nest must also appear in path (see invariant below), 136 // type t must be in path since it was found in nest. But not every type in path 137 // is in nest. Specifically t may appear in path with an earlier index than the 138 // index of t in nest. Search again. 139 for start, p := range path { 140 if Identical(p, t) { 141 check.cycleError(makeObjList(path[start:]), 0) 142 return false 143 } 144 } 145 panic("cycle start not found") 146 } 147 } 148 149 // No cycle was found. Check the RHS of t. 150 // Every type added to nest is also added to path; thus every type that is in nest 151 // must also be in path (invariant). But not every type in path is in nest, since 152 // nest may be pruned (see below, *TypeParam case). 153 if !check.validType0(pos, t.Origin().fromRHS, append(nest, t), append(path, t)) { 154 return false 155 } 156 157 // see TODO above 158 // check.valids.add(t) // t is valid 159 160 case *TypeParam: 161 // A type parameter stands for the type (argument) it was instantiated with. 162 // Check the corresponding type argument for validity if we are in an 163 // instantiated type. 164 if d := len(nest) - 1; d >= 0 { 165 inst := nest[d] // the type instance 166 // Find the corresponding type argument for the type parameter 167 // and proceed with checking that type argument. 168 for i, tparam := range inst.TypeParams().list() { 169 // The type parameter and type argument lists should 170 // match in length but be careful in case of errors. 171 if t == tparam && i < inst.TypeArgs().Len() { 172 targ := inst.TypeArgs().At(i) 173 // The type argument must be valid in the enclosing 174 // type (where inst was instantiated), hence we must 175 // check targ's validity in the type nest excluding 176 // the current (instantiated) type (see the example 177 // at the end of this file). 178 // For error reporting we keep the full path. 179 res := check.validType0(pos, targ, nest[:d], path) 180 // The check.validType0 call with nest[:d] may have 181 // overwritten the entry at the current depth d. 182 // Restore the entry (was issue go.dev/issue/66323). 183 nest[d] = inst 184 return res 185 } 186 } 187 } 188 } 189 190 return true 191 } 192 193 // makeObjList returns the list of type name objects for the given 194 // list of named types. 195 func makeObjList(tlist []*Named) []Object { 196 olist := make([]Object, len(tlist)) 197 for i, t := range tlist { 198 olist[i] = t.obj 199 } 200 return olist 201 } 202 203 // Here is an example illustrating why we need to exclude the 204 // instantiated type from nest when evaluating the validity of 205 // a type parameter. Given the declarations 206 // 207 // var _ A[A[string]] 208 // 209 // type A[P any] struct { _ B[P] } 210 // type B[P any] struct { _ P } 211 // 212 // we want to determine if the type A[A[string]] is valid. 213 // We start evaluating A[A[string]] outside any type nest: 214 // 215 // A[A[string]] 216 // nest = 217 // path = 218 // 219 // The RHS of A is now evaluated in the A[A[string]] nest: 220 // 221 // struct{_ B[P₁]} 222 // nest = A[A[string]] 223 // path = A[A[string]] 224 // 225 // The struct has a single field of type B[P₁] with which 226 // we continue: 227 // 228 // B[P₁] 229 // nest = A[A[string]] 230 // path = A[A[string]] 231 // 232 // struct{_ P₂} 233 // nest = A[A[string]]->B[P] 234 // path = A[A[string]]->B[P] 235 // 236 // Eventually we reach the type parameter P of type B (P₂): 237 // 238 // P₂ 239 // nest = A[A[string]]->B[P] 240 // path = A[A[string]]->B[P] 241 // 242 // The type argument for P of B is the type parameter P of A (P₁). 243 // It must be evaluated in the type nest that existed when B was 244 // instantiated: 245 // 246 // P₁ 247 // nest = A[A[string]] <== type nest at B's instantiation time 248 // path = A[A[string]]->B[P] 249 // 250 // If we'd use the current nest it would correspond to the path 251 // which will be wrong as we will see shortly. P's type argument 252 // is A[string], which again must be evaluated in the type nest 253 // that existed when A was instantiated with A[string]. That type 254 // nest is empty: 255 // 256 // A[string] 257 // nest = <== type nest at A's instantiation time 258 // path = A[A[string]]->B[P] 259 // 260 // Evaluation then proceeds as before for A[string]: 261 // 262 // struct{_ B[P₁]} 263 // nest = A[string] 264 // path = A[A[string]]->B[P]->A[string] 265 // 266 // Now we reach B[P] again. If we had not adjusted nest, it would 267 // correspond to path, and we would find B[P] in nest, indicating 268 // a cycle, which would clearly be wrong since there's no cycle in 269 // A[string]: 270 // 271 // B[P₁] 272 // nest = A[string] 273 // path = A[A[string]]->B[P]->A[string] <== path contains B[P]! 274 // 275 // But because we use the correct type nest, evaluation proceeds without 276 // errors and we get the evaluation sequence: 277 // 278 // struct{_ P₂} 279 // nest = A[string]->B[P] 280 // path = A[A[string]]->B[P]->A[string]->B[P] 281 // P₂ 282 // nest = A[string]->B[P] 283 // path = A[A[string]]->B[P]->A[string]->B[P] 284 // P₁ 285 // nest = A[string] 286 // path = A[A[string]]->B[P]->A[string]->B[P] 287 // string 288 // nest = 289 // path = A[A[string]]->B[P]->A[string]->B[P] 290 // 291 // At this point we're done and A[A[string]] and is valid. 292