src/cmd/compile/internal/types2/mono.go

   1 // Copyright 2021 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 (
   8         "cmd/compile/internal/syntax"
   9 )
  10
  11 // This file implements a check to validate that a Go package doesn't
  12 // have unbounded recursive instantiation, which is not compatible
  13 // with compilers using static instantiation (such as
  14 // monomorphization).
  15 //
  16 // It implements a sort of "type flow" analysis by detecting which
  17 // type parameters are instantiated with other type parameters (or
  18 // types derived thereof). A package cannot be statically instantiated
  19 // if the graph has any cycles involving at least one derived type.
  20 //
  21 // Concretely, we construct a directed, weighted graph. Vertices are
  22 // used to represent type parameters as well as some defined
  23 // types. Edges are used to represent how types depend on each other:
  24 //
  25 // * Everywhere a type-parameterized function or type is instantiated,
  26 //   we add edges to each type parameter from the vertices (if any)
  27 //   representing each type parameter or defined type referenced by
  28 //   the type argument. If the type argument is just the referenced
  29 //   type itself, then the edge has weight 0, otherwise 1.
  30 //
  31 // * For every defined type declared within a type-parameterized
  32 //   function or method, we add an edge of weight 1 to the defined
  33 //   type from each ambient type parameter.
  34 //
  35 // For example, given:
  36 //
  37 //      func f[A, B any]() {
  38 //              type T int
  39 //              f[T, map[A]B]()
  40 //      }
  41 //
  42 // we construct vertices representing types A, B, and T. Because of
  43 // declaration "type T int", we construct edges T<-A and T<-B with
  44 // weight 1; and because of instantiation "f[T, map[A]B]" we construct
  45 // edges A<-T with weight 0, and B<-A and B<-B with weight 1.
  46 //
  47 // Finally, we look for any positive-weight cycles. Zero-weight cycles
  48 // are allowed because static instantiation will reach a fixed point.
  49
  50 type monoGraph struct {
  51         vertices []monoVertex
  52         edges    []monoEdge
  53
  54         // canon maps method receiver type parameters to their respective
  55         // receiver type's type parameters.
  56         canon map[*TypeParam]*TypeParam
  57
  58         // nameIdx maps a defined type or (canonical) type parameter to its
  59         // vertex index.
  60         nameIdx map[*TypeName]int
  61 }
  62
  63 type monoVertex struct {
  64         weight int // weight of heaviest known path to this vertex
  65         pre    int // previous edge (if any) in the above path
  66         len    int // length of the above path
  67
  68         // obj is the defined type or type parameter represented by this
  69         // vertex.
  70         obj *TypeName
  71 }
  72
  73 type monoEdge struct {
  74         dst, src int
  75         weight   int
  76
  77         pos syntax.Pos
  78         typ Type
  79 }
  80
  81 func (check *Checker) monomorph() {
  82         // We detect unbounded instantiation cycles using a variant of
  83         // Bellman-Ford's algorithm. Namely, instead of always running |V|
  84         // iterations, we run until we either reach a fixed point or we've
  85         // found a path of length |V|. This allows us to terminate earlier
  86         // when there are no cycles, which should be the common case.
  87
  88         again := true
  89         for again {
  90                 again = false
  91
  92                 for i, edge := range check.mono.edges {
  93                         src := &check.mono.vertices[edge.src]
  94                         dst := &check.mono.vertices[edge.dst]
  95
  96                         // N.B., we're looking for the greatest weight paths, unlike
  97                         // typical Bellman-Ford.
  98                         w := src.weight + edge.weight
  99                         if w <= dst.weight {
 100                                 continue
 101                         }
 102
 103                         dst.pre = i
 104                         dst.len = src.len + 1
 105                         if dst.len == len(check.mono.vertices) {
 106                                 check.reportInstanceLoop(edge.dst)
 107                                 return
 108                         }
 109
 110                         dst.weight = w
 111                         again = true
 112                 }
 113         }
 114 }
 115
 116 func (check *Checker) reportInstanceLoop(v int) {
 117         var stack []int
 118         seen := make([]bool, len(check.mono.vertices))
 119
 120         // We have a path that contains a cycle and ends at v, but v may
 121         // only be reachable from the cycle, not on the cycle itself. We
 122         // start by walking backwards along the path until we find a vertex
 123         // that appears twice.
 124         for !seen[v] {
 125                 stack = append(stack, v)
 126                 seen[v] = true
 127                 v = check.mono.edges[check.mono.vertices[v].pre].src
 128         }
 129
 130         // Trim any vertices we visited before visiting v the first
 131         // time. Since v is the first vertex we found within the cycle, any
 132         // vertices we visited earlier cannot be part of the cycle.
 133         for stack[0] != v {
 134                 stack = stack[1:]
 135         }
 136
 137         // TODO(mdempsky): Pivot stack so we report the cycle from the top?
 138
 139         var err error_
 140         err.code = _InvalidInstanceCycle
 141         obj0 := check.mono.vertices[v].obj
 142         err.errorf(obj0, "instantiation cycle:")
 143
 144         qf := RelativeTo(check.pkg)
 145         for _, v := range stack {
 146                 edge := check.mono.edges[check.mono.vertices[v].pre]
 147                 obj := check.mono.vertices[edge.dst].obj
 148
 149                 switch obj.Type().(type) {
 150                 default:
 151                         panic("unexpected type")
 152                 case *Named:
 153                         err.errorf(edge.pos, "%s implicitly parameterized by %s", obj.Name(), TypeString(edge.typ, qf)) // secondary error, \t indented
 154                 case *TypeParam:
 155                         err.errorf(edge.pos, "%s instantiated as %s", obj.Name(), TypeString(edge.typ, qf)) // secondary error, \t indented
 156                 }
 157         }
 158         check.report(&err)
 159 }
 160
 161 // recordCanon records that tpar is the canonical type parameter
 162 // corresponding to method type parameter mpar.
 163 func (w *monoGraph) recordCanon(mpar, tpar *TypeParam) {
 164         if w.canon == nil {
 165                 w.canon = make(map[*TypeParam]*TypeParam)
 166         }
 167         w.canon[mpar] = tpar
 168 }
 169
 170 // recordInstance records that the given type parameters were
 171 // instantiated with the corresponding type arguments.
 172 func (w *monoGraph) recordInstance(pkg *Package, pos syntax.Pos, tparams []*TypeParam, targs []Type, xlist []syntax.Expr) {
 173         for i, tpar := range tparams {
 174                 pos := pos
 175                 if i < len(xlist) {
 176                         pos = syntax.StartPos(xlist[i])
 177                 }
 178                 w.assign(pkg, pos, tpar, targs[i])
 179         }
 180 }
 181
 182 // assign records that tpar was instantiated as targ at pos.
 183 func (w *monoGraph) assign(pkg *Package, pos syntax.Pos, tpar *TypeParam, targ Type) {
 184         // Go generics do not have an analog to C++`s template-templates,
 185         // where a template parameter can itself be an instantiable
 186         // template. So any instantiation cycles must occur within a single
 187         // package. Accordingly, we can ignore instantiations of imported
 188         // type parameters.
 189         //
 190         // TODO(mdempsky): Push this check up into recordInstance? All type
 191         // parameters in a list will appear in the same package.
 192         if tpar.Obj().Pkg() != pkg {
 193                 return
 194         }
 195
 196         // flow adds an edge from vertex src representing that typ flows to tpar.
 197         flow := func(src int, typ Type) {
 198                 weight := 1
 199                 if typ == targ {
 200                         weight = 0
 201                 }
 202
 203                 w.addEdge(w.typeParamVertex(tpar), src, weight, pos, targ)
 204         }
 205
 206         // Recursively walk the type argument to find any defined types or
 207         // type parameters.
 208         var do func(typ Type)
 209         do = func(typ Type) {
 210                 switch typ := typ.(type) {
 211                 default:
 212                         panic("unexpected type")
 213
 214                 case *TypeParam:
 215                         assert(typ.Obj().Pkg() == pkg)
 216                         flow(w.typeParamVertex(typ), typ)
 217
 218                 case *Named:
 219                         if src := w.localNamedVertex(pkg, typ.Origin()); src >= 0 {
 220                                 flow(src, typ)
 221                         }
 222
 223                         targs := typ.TypeArgs()
 224                         for i := 0; i < targs.Len(); i++ {
 225                                 do(targs.At(i))
 226                         }
 227
 228                 case *Array:
 229                         do(typ.Elem())
 230                 case *Basic:
 231                         // ok
 232                 case *Chan:
 233                         do(typ.Elem())
 234                 case *Map:
 235                         do(typ.Key())
 236                         do(typ.Elem())
 237                 case *Pointer:
 238                         do(typ.Elem())
 239                 case *Slice:
 240                         do(typ.Elem())
 241
 242                 case *Interface:
 243                         for i := 0; i < typ.NumMethods(); i++ {
 244                                 do(typ.Method(i).Type())
 245                         }
 246                 case *Signature:
 247                         tuple := func(tup *Tuple) {
 248                                 for i := 0; i < tup.Len(); i++ {
 249                                         do(tup.At(i).Type())
 250                                 }
 251                         }
 252                         tuple(typ.Params())
 253                         tuple(typ.Results())
 254                 case *Struct:
 255                         for i := 0; i < typ.NumFields(); i++ {
 256                                 do(typ.Field(i).Type())
 257                         }
 258                 }
 259         }
 260         do(targ)
 261 }
 262
 263 // localNamedVertex returns the index of the vertex representing
 264 // named, or -1 if named doesn't need representation.
 265 func (w *monoGraph) localNamedVertex(pkg *Package, named *Named) int {
 266         obj := named.Obj()
 267         if obj.Pkg() != pkg {
 268                 return -1 // imported type
 269         }
 270
 271         root := pkg.Scope()
 272         if obj.Parent() == root {
 273                 return -1 // package scope, no ambient type parameters
 274         }
 275
 276         if idx, ok := w.nameIdx[obj]; ok {
 277                 return idx
 278         }
 279
 280         idx := -1
 281
 282         // Walk the type definition's scope to find any ambient type
 283         // parameters that it's implicitly parameterized by.
 284         for scope := obj.Parent(); scope != root; scope = scope.Parent() {
 285                 for _, elem := range scope.elems {
 286                         if elem, ok := elem.(*TypeName); ok && !elem.IsAlias() && elem.Pos().Cmp(obj.Pos()) < 0 {
 287                                 if tpar, ok := elem.Type().(*TypeParam); ok {
 288                                         if idx < 0 {
 289                                                 idx = len(w.vertices)
 290                                                 w.vertices = append(w.vertices, monoVertex{obj: obj})
 291                                         }
 292
 293                                         w.addEdge(idx, w.typeParamVertex(tpar), 1, obj.Pos(), tpar)
 294                                 }
 295                         }
 296                 }
 297         }
 298
 299         if w.nameIdx == nil {
 300                 w.nameIdx = make(map[*TypeName]int)
 301         }
 302         w.nameIdx[obj] = idx
 303         return idx
 304 }
 305
 306 // typeParamVertex returns the index of the vertex representing tpar.
 307 func (w *monoGraph) typeParamVertex(tpar *TypeParam) int {
 308         if x, ok := w.canon[tpar]; ok {
 309                 tpar = x
 310         }
 311
 312         obj := tpar.Obj()
 313
 314         if idx, ok := w.nameIdx[obj]; ok {
 315                 return idx
 316         }
 317
 318         if w.nameIdx == nil {
 319                 w.nameIdx = make(map[*TypeName]int)
 320         }
 321
 322         idx := len(w.vertices)
 323         w.vertices = append(w.vertices, monoVertex{obj: obj})
 324         w.nameIdx[obj] = idx
 325         return idx
 326 }
 327
 328 func (w *monoGraph) addEdge(dst, src, weight int, pos syntax.Pos, typ Type) {
 329         // TODO(mdempsky): Deduplicate redundant edges?
 330         w.edges = append(w.edges, monoEdge{
 331                 dst:    dst,
 332                 src:    src,
 333                 weight: weight,
 334
 335                 pos: pos,
 336                 typ: typ,
 337         })
 338 }