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