src/go/types/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 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.