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.
8 "cmd/compile/internal/syntax"
9 . "internal/types/errors"
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
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.
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:
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.
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.
36 // For example, given:
38 // func f[A, B any]() {
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.
48 // Finally, we look for any positive-weight cycles. Zero-weight cycles
49 // are allowed because static instantiation will reach a fixed point.
51 type monoGraph struct {
55 // canon maps method receiver type parameters to their respective
56 // receiver type's type parameters.
57 canon map[*TypeParam]*TypeParam
59 // nameIdx maps a defined type or (canonical) type parameter to its
61 nameIdx map[*TypeName]int
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
69 // obj is the defined type or type parameter represented by this
74 type monoEdge struct {
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.
93 for i, edge := range check.mono.edges {
94 src := &check.mono.vertices[edge.src]
95 dst := &check.mono.vertices[edge.dst]
97 // N.B., we're looking for the greatest weight paths, unlike
98 // typical Bellman-Ford.
99 w := src.weight + edge.weight
105 dst.len = src.len + 1
106 if dst.len == len(check.mono.vertices) {
107 check.reportInstanceLoop(edge.dst)
117 func (check *Checker) reportInstanceLoop(v int) {
119 seen := make([]bool, len(check.mono.vertices))
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.
126 stack = append(stack, v)
128 v = check.mono.edges[check.mono.vertices[v].pre].src
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.
138 // TODO(mdempsky): Pivot stack so we report the cycle from the top?
141 err.code = InvalidInstanceCycle
142 obj0 := check.mono.vertices[v].obj
143 err.errorf(obj0, "instantiation cycle:")
145 qf := RelativeTo(check.pkg)
146 for _, v := range stack {
147 edge := check.mono.edges[check.mono.vertices[v].pre]
148 obj := check.mono.vertices[edge.dst].obj
150 switch obj.Type().(type) {
152 panic("unexpected type")
154 err.errorf(edge.pos, "%s implicitly parameterized by %s", obj.Name(), TypeString(edge.typ, qf)) // secondary error, \t indented
156 err.errorf(edge.pos, "%s instantiated as %s", obj.Name(), TypeString(edge.typ, qf)) // secondary error, \t indented
162 // recordCanon records that tpar is the canonical type parameter
163 // corresponding to method type parameter mpar.
164 func (w *monoGraph) recordCanon(mpar, tpar *TypeParam) {
166 w.canon = make(map[*TypeParam]*TypeParam)
171 // recordInstance records that the given type parameters were
172 // instantiated with the corresponding type arguments.
173 func (w *monoGraph) recordInstance(pkg *Package, pos syntax.Pos, tparams []*TypeParam, targs []Type, xlist []syntax.Expr) {
174 for i, tpar := range tparams {
177 pos = syntax.StartPos(xlist[i])
179 w.assign(pkg, pos, tpar, targs[i])
183 // assign records that tpar was instantiated as targ at pos.
184 func (w *monoGraph) assign(pkg *Package, pos syntax.Pos, tpar *TypeParam, targ Type) {
185 // Go generics do not have an analog to C++`s template-templates,
186 // where a template parameter can itself be an instantiable
187 // template. So any instantiation cycles must occur within a single
188 // package. Accordingly, we can ignore instantiations of imported
191 // TODO(mdempsky): Push this check up into recordInstance? All type
192 // parameters in a list will appear in the same package.
193 if tpar.Obj().Pkg() != pkg {
197 // flow adds an edge from vertex src representing that typ flows to tpar.
198 flow := func(src int, typ Type) {
204 w.addEdge(w.typeParamVertex(tpar), src, weight, pos, targ)
207 // Recursively walk the type argument to find any defined types or
209 var do func(typ Type)
210 do = func(typ Type) {
211 switch typ := Unalias(typ).(type) {
213 panic("unexpected type")
216 assert(typ.Obj().Pkg() == pkg)
217 flow(w.typeParamVertex(typ), typ)
220 if src := w.localNamedVertex(pkg, typ.Origin()); src >= 0 {
224 targs := typ.TypeArgs()
225 for i := 0; i < targs.Len(); i++ {
244 for i := 0; i < typ.NumMethods(); i++ {
245 do(typ.Method(i).Type())
248 tuple := func(tup *Tuple) {
249 for i := 0; i < tup.Len(); i++ {
256 for i := 0; i < typ.NumFields(); i++ {
257 do(typ.Field(i).Type())
264 // localNamedVertex returns the index of the vertex representing
265 // named, or -1 if named doesn't need representation.
266 func (w *monoGraph) localNamedVertex(pkg *Package, named *Named) int {
268 if obj.Pkg() != pkg {
269 return -1 // imported type
273 if obj.Parent() == root {
274 return -1 // package scope, no ambient type parameters
277 if idx, ok := w.nameIdx[obj]; ok {
283 // Walk the type definition's scope to find any ambient type
284 // parameters that it's implicitly parameterized by.
285 for scope := obj.Parent(); scope != root; scope = scope.Parent() {
286 for _, elem := range scope.elems {
287 if elem, ok := elem.(*TypeName); ok && !elem.IsAlias() && cmpPos(elem.Pos(), obj.Pos()) < 0 {
288 if tpar, ok := elem.Type().(*TypeParam); ok {
290 idx = len(w.vertices)
291 w.vertices = append(w.vertices, monoVertex{obj: obj})
294 w.addEdge(idx, w.typeParamVertex(tpar), 1, obj.Pos(), tpar)
300 if w.nameIdx == nil {
301 w.nameIdx = make(map[*TypeName]int)
307 // typeParamVertex returns the index of the vertex representing tpar.
308 func (w *monoGraph) typeParamVertex(tpar *TypeParam) int {
309 if x, ok := w.canon[tpar]; ok {
315 if idx, ok := w.nameIdx[obj]; ok {
319 if w.nameIdx == nil {
320 w.nameIdx = make(map[*TypeName]int)
323 idx := len(w.vertices)
324 w.vertices = append(w.vertices, monoVertex{obj: obj})
329 func (w *monoGraph) addEdge(dst, src, weight int, pos syntax.Pos, typ Type) {
330 // TODO(mdempsky): Deduplicate redundant edges?
331 w.edges = append(w.edges, monoEdge{