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