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 // validType verifies that the given type does not "expand" indefinitely
   8 // producing a cycle in the type graph. Cycles are detected by marking
   9 // defined types.
  10 // (Cycles involving alias types, as in "type A = [10]A" are detected
  11 // earlier, via the objDecl cycle detection mechanism.)
  12 func (check *Checker) validType(typ *Named) {
  13         check.validType0(typ, nil)
  14 }
  15
  16 type typeInfo uint
  17
  18 func (check *Checker) validType0(typ Type, path []Object) typeInfo {
  19         const (
  20                 unknown typeInfo = iota
  21                 marked
  22                 valid
  23                 invalid
  24         )
  25
  26         switch t := typ.(type) {
  27         case *Array:
  28                 return check.validType0(t.elem, path)
  29
  30         case *Struct:
  31                 for _, f := range t.fields {
  32                         if check.validType0(f.typ, path) == invalid {
  33                                 return invalid
  34                         }
  35                 }
  36
  37         case *Union:
  38                 for _, t := range t.terms {
  39                         if check.validType0(t.typ, path) == invalid {
  40                                 return invalid
  41                         }
  42                 }
  43
  44         case *Interface:
  45                 for _, etyp := range t.embeddeds {
  46                         if check.validType0(etyp, path) == invalid {
  47                                 return invalid
  48                         }
  49                 }
  50
  51         case *Named:
  52                 // If t is parameterized, we should be considering the instantiated (expanded)
  53                 // form of t, but in general we can't with this algorithm: if t is an invalid
  54                 // type it may be so because it infinitely expands through a type parameter.
  55                 // Instantiating such a type would lead to an infinite sequence of instantiations.
  56                 // In general, we need "type flow analysis" to recognize those cases.
  57                 // Example: type A[T any] struct{ x A[*T] } (issue #48951)
  58                 // In this algorithm we always only consider the original, uninstantiated type.
  59                 // This won't recognize some invalid cases with parameterized types, but it
  60                 // will terminate.
  61                 t = t.orig
  62
  63                 // don't report a 2nd error if we already know the type is invalid
  64                 // (e.g., if a cycle was detected earlier, via under).
  65                 if t.underlying == Typ[Invalid] {
  66                         check.infoMap[t] = invalid
  67                         return invalid
  68                 }
  69
  70                 switch check.infoMap[t] {
  71                 case unknown:
  72                         check.infoMap[t] = marked
  73                         check.infoMap[t] = check.validType0(t.fromRHS, append(path, t.obj))
  74                 case marked:
  75                         // cycle detected
  76                         for i, tn := range path {
  77                                 // Even though validType now can hande cycles through external
  78                                 // types, we can't have cycles through external types because
  79                                 // no such types are detected yet.
  80                                 // TODO(gri) Remove this check once we can detect such cycles,
  81                                 //           and adjust cycleError accordingly.
  82                                 if t.obj.pkg != check.pkg {
  83                                         panic("type cycle via package-external type")
  84                                 }
  85                                 if tn == t.obj {
  86                                         check.cycleError(path[i:])
  87                                         check.infoMap[t] = invalid
  88                                         // don't modify imported types (leads to race condition, see #35049)
  89                                         if t.obj.pkg == check.pkg {
  90                                                 t.underlying = Typ[Invalid]
  91                                         }
  92                                         return invalid
  93                                 }
  94                         }
  95                         panic("cycle start not found")
  96                 }
  97                 return check.infoMap[t]
  98         }
  99
 100         return valid
 101 }