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 types 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 := 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 t.Underlying() == Typ[Invalid] { 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 // t cannot be in an imported package otherwise that package 80 // would have reported a type cycle and couldn't have been 81 // imported in the first place. 82 assert(t.obj.pkg == check.pkg) 83 t.underlying = Typ[Invalid] // t is in the current package (no race possibility) 84 // Find the starting point of the cycle and report it. 85 // Because each type in nest must also appear in path (see invariant below), 86 // type t must be in path since it was found in nest. But not every type in path 87 // is in nest. Specifically t may appear in path with an earlier index than the 88 // index of t in nest. Search again. 89 for start, p := range path { 90 if Identical(p, t) { 91 check.cycleError(makeObjList(path[start:])) 92 return false 93 } 94 } 95 panic("cycle start not found") 96 } 97 } 98 99 // No cycle was found. Check the RHS of t. 100 // Every type added to nest is also added to path; thus every type that is in nest 101 // must also be in path (invariant). But not every type in path is in nest, since 102 // nest may be pruned (see below, *TypeParam case). 103 if !check.validType0(t.Origin().fromRHS, append(nest, t), append(path, t)) { 104 return false 105 } 106 107 check.valids.add(t) // t is valid 108 109 case *TypeParam: 110 // A type parameter stands for the type (argument) it was instantiated with. 111 // Check the corresponding type argument for validity if we are in an 112 // instantiated type. 113 if len(nest) > 0 { 114 inst := nest[len(nest)-1] // the type instance 115 // Find the corresponding type argument for the type parameter 116 // and proceed with checking that type argument. 117 for i, tparam := range inst.TypeParams().list() { 118 // The type parameter and type argument lists should 119 // match in length but be careful in case of errors. 120 if t == tparam && i < inst.TypeArgs().Len() { 121 targ := inst.TypeArgs().At(i) 122 // The type argument must be valid in the enclosing 123 // type (where inst was instantiated), hence we must 124 // check targ's validity in the type nest excluding 125 // the current (instantiated) type (see the example 126 // at the end of this file). 127 // For error reporting we keep the full path. 128 return check.validType0(targ, nest[:len(nest)-1], path) 129 } 130 } 131 } 132 } 133 134 return true 135 } 136 137 // makeObjList returns the list of type name objects for the given 138 // list of named types. 139 func makeObjList(tlist []*Named) []Object { 140 olist := make([]Object, len(tlist)) 141 for i, t := range tlist { 142 olist[i] = t.obj 143 } 144 return olist 145 } 146 147 // Here is an example illustrating why we need to exclude the 148 // instantiated type from nest when evaluating the validity of 149 // a type parameter. Given the declarations 150 // 151 // var _ A[A[string]] 152 // 153 // type A[P any] struct { _ B[P] } 154 // type B[P any] struct { _ P } 155 // 156 // we want to determine if the type A[A[string]] is valid. 157 // We start evaluating A[A[string]] outside any type nest: 158 // 159 // A[A[string]] 160 // nest = 161 // path = 162 // 163 // The RHS of A is now evaluated in the A[A[string]] nest: 164 // 165 // struct{_ B[P₁]} 166 // nest = A[A[string]] 167 // path = A[A[string]] 168 // 169 // The struct has a single field of type B[P₁] with which 170 // we continue: 171 // 172 // B[P₁] 173 // nest = A[A[string]] 174 // path = A[A[string]] 175 // 176 // struct{_ P₂} 177 // nest = A[A[string]]->B[P] 178 // path = A[A[string]]->B[P] 179 // 180 // Eventutally we reach the type parameter P of type B (P₂): 181 // 182 // P₂ 183 // nest = A[A[string]]->B[P] 184 // path = A[A[string]]->B[P] 185 // 186 // The type argument for P of B is the type parameter P of A (P₁). 187 // It must be evaluated in the type nest that existed when B was 188 // instantiated: 189 // 190 // P₁ 191 // nest = A[A[string]] <== type nest at B's instantiation time 192 // path = A[A[string]]->B[P] 193 // 194 // If we'd use the current nest it would correspond to the path 195 // which will be wrong as we will see shortly. P's type argument 196 // is A[string], which again must be evaluated in the type nest 197 // that existed when A was instantiated with A[string]. That type 198 // nest is empty: 199 // 200 // A[string] 201 // nest = <== type nest at A's instantiation time 202 // path = A[A[string]]->B[P] 203 // 204 // Evaluation then proceeds as before for A[string]: 205 // 206 // struct{_ B[P₁]} 207 // nest = A[string] 208 // path = A[A[string]]->B[P]->A[string] 209 // 210 // Now we reach B[P] again. If we had not adjusted nest, it would 211 // correspond to path, and we would find B[P] in nest, indicating 212 // a cycle, which would clearly be wrong since there's no cycle in 213 // A[string]: 214 // 215 // B[P₁] 216 // nest = A[string] 217 // path = A[A[string]]->B[P]->A[string] <== path contains B[P]! 218 // 219 // But because we use the correct type nest, evaluation proceeds without 220 // errors and we get the evaluation sequence: 221 // 222 // struct{_ P₂} 223 // nest = A[string]->B[P] 224 // path = A[A[string]]->B[P]->A[string]->B[P] 225 // P₂ 226 // nest = A[string]->B[P] 227 // path = A[A[string]]->B[P]->A[string]->B[P] 228 // P₁ 229 // nest = A[string] 230 // path = A[A[string]]->B[P]->A[string]->B[P] 231 // string 232 // nest = 233 // path = A[A[string]]->B[P]->A[string]->B[P] 234 // 235 // At this point we're done and A[A[string]] and is valid. 236