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