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