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