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, 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 provided environment. The environment is
  17 // nil if typ is not part of (the RHS of) an instantiated type, in that case
  18 // any type parameter encountered must be from an enclosing function and can
  19 // be ignored. The nest list describes the stack (the "nest in memory") of
  20 // types which contain (or embed in the case of interfaces) other types. For
  21 // instance, a struct named S which contains a field of named type F contains
  22 // (the memory of) F in S, leading to the nest S->F. If a type appears in its
  23 // own nest (say S->F->S) we have an invalid recursive type. The path list is
  24 // the full path of named types in a cycle, it is only needed for error reporting.
  25 func (check *Checker) validType0(typ Type, env *tparamEnv, 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, env, nest, path)
  36
  37         case *Struct:
  38                 for _, f := range t.fields {
  39                         if !check.validType0(f.typ, env, nest, path) {
  40                                 return false
  41                         }
  42                 }
  43
  44         case *Union:
  45                 for _, t := range t.terms {
  46                         if !check.validType0(t.typ, env, nest, path) {
  47                                 return false
  48                         }
  49                 }
  50
  51         case *Interface:
  52                 for _, etyp := range t.embeddeds {
  53                         if !check.validType0(etyp, env, 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, env.push(t), 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 have one.
 112                 if env != nil {
 113                         if targ := env.tmap[t]; targ != nil {
 114                                 // Type arguments found in targ must be looked
 115                                 // up in the enclosing environment env.link. The
 116                                 // type argument must be valid in the enclosing
 117                                 // type (where the current type was instantiated),
 118                                 // hence we must check targ's validity in the type
 119                                 // nest excluding the current (instantiated) type
 120                                 // (see the example at the end of this file).
 121                                 // For error reporting we keep the full path.
 122                                 return check.validType0(targ, env.link, nest[:len(nest)-1], path)
 123                         }
 124                 }
 125         }
 126
 127         return true
 128 }
 129
 130 // makeObjList returns the list of type name objects for the given
 131 // list of named types.
 132 func makeObjList(tlist []*Named) []Object {
 133         olist := make([]Object, len(tlist))
 134         for i, t := range tlist {
 135                 olist[i] = t.obj
 136         }
 137         return olist
 138 }
 139
 140 // A tparamEnv provides the environment for looking up the type arguments
 141 // with which type parameters for a given instance were instantiated.
 142 // If we don't have an instance, the corresponding tparamEnv is nil.
 143 type tparamEnv struct {
 144         tmap substMap
 145         link *tparamEnv
 146 }
 147
 148 func (env *tparamEnv) push(typ *Named) *tparamEnv {
 149         // If typ is not an instantiated type there are no typ-specific
 150         // type parameters to look up and we don't need an environment.
 151         targs := typ.TypeArgs()
 152         if targs == nil {
 153                 return nil // no instance => nil environment
 154         }
 155
 156         // Populate tmap: remember the type argument for each type parameter.
 157         // We cannot use makeSubstMap because the number of type parameters
 158         // and arguments may not match due to errors in the source (too many
 159         // or too few type arguments). Populate tmap "manually".
 160         tparams := typ.TypeParams()
 161         n, m := targs.Len(), tparams.Len()
 162         if n > m {
 163                 n = m // too many targs
 164         }
 165         tmap := make(substMap, n)
 166         for i := 0; i < n; i++ {
 167                 tmap[tparams.At(i)] = targs.At(i)
 168         }
 169
 170         return &tparamEnv{tmap: tmap, link: env}
 171 }
 172
 173 // TODO(gri) Alternative implementation:
 174 // We may not need to build a stack of environments to
 175 // look up the type arguments for type parameters. The
 176 // same information should be available via the path:
 177 // We should be able to just walk the path backwards
 178 // and find the type arguments in the instance objects.
 179
 180 // Here is an example illustrating why we need to exclude the
 181 // instantiated type from nest when evaluating the validity of
 182 // a type parameter. Given the declarations
 183 //
 184 //   var _ A[A[string]]
 185 //
 186 //   type A[P any] struct { _ B[P] }
 187 //   type B[P any] struct { _ P }
 188 //
 189 // we want to determine if the type A[A[string]] is valid.
 190 // We start evaluating A[A[string]] outside any type nest:
 191 //
 192 //   A[A[string]]
 193 //         nest =
 194 //         path =
 195 //
 196 // The RHS of A is now evaluated in the A[A[string]] nest:
 197 //
 198 //   struct{_ B[P₁]}
 199 //         nest = A[A[string]]
 200 //         path = A[A[string]]
 201 //
 202 // The struct has a single field of type B[P₁] with which
 203 // we continue:
 204 //
 205 //   B[P₁]
 206 //         nest = A[A[string]]
 207 //         path = A[A[string]]
 208 //
 209 //   struct{_ P₂}
 210 //         nest = A[A[string]]->B[P]
 211 //         path = A[A[string]]->B[P]
 212 //
 213 // Eventutally we reach the type parameter P of type B (P₂):
 214 //
 215 //   P₂
 216 //         nest = A[A[string]]->B[P]
 217 //         path = A[A[string]]->B[P]
 218 //
 219 // The type argument for P of B is the type parameter P of A (P₁).
 220 // It must be evaluated in the type nest that existed when B was
 221 // instantiated:
 222 //
 223 //   P₁
 224 //         nest = A[A[string]]        <== type nest at B's instantiation time
 225 //         path = A[A[string]]->B[P]
 226 //
 227 // If we'd use the current nest it would correspond to the path
 228 // which will be wrong as we will see shortly. P's type argument
 229 // is A[string], which again must be evaluated in the type nest
 230 // that existed when A was instantiated with A[string]. That type
 231 // nest is empty:
 232 //
 233 //   A[string]
 234 //         nest =                     <== type nest at A's instantiation time
 235 //         path = A[A[string]]->B[P]
 236 //
 237 // Evaluation then proceeds as before for A[string]:
 238 //
 239 //   struct{_ B[P₁]}
 240 //         nest = A[string]
 241 //         path = A[A[string]]->B[P]->A[string]
 242 //
 243 // Now we reach B[P] again. If we had not adjusted nest, it would
 244 // correspond to path, and we would find B[P] in nest, indicating
 245 // a cycle, which would clearly be wrong since there's no cycle in
 246 // A[string]:
 247 //
 248 //   B[P₁]
 249 //         nest = A[string]
 250 //         path = A[A[string]]->B[P]->A[string]  <== path contains B[P]!
 251 //
 252 // But because we use the correct type nest, evaluation proceeds without
 253 // errors and we get the evaluation sequence:
 254 //
 255 //   struct{_ P₂}
 256 //         nest = A[string]->B[P]
 257 //         path = A[A[string]]->B[P]->A[string]->B[P]
 258 //   P₂
 259 //         nest = A[string]->B[P]
 260 //         path = A[A[string]]->B[P]->A[string]->B[P]
 261 //   P₁
 262 //         nest = A[string]
 263 //         path = A[A[string]]->B[P]->A[string]->B[P]
 264 //   string
 265 //         nest =
 266 //         path = A[A[string]]->B[P]->A[string]->B[P]
 267 //
 268 // At this point we're done and A[A[string]] and is valid.