1
2
3
4
5 package types2
6
7 import (
8 "cmd/compile/internal/syntax"
9 . "internal/types/errors"
10 )
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51 type monoGraph struct {
52 vertices []monoVertex
53 edges []monoEdge
54
55
56
57 canon map[*TypeParam]*TypeParam
58
59
60
61 nameIdx map[*TypeName]int
62 }
63
64 type monoVertex struct {
65 weight int
66 pre int
67 len int
68
69
70
71 obj *TypeName
72 }
73
74 type monoEdge struct {
75 dst, src int
76 weight int
77
78 pos syntax.Pos
79 typ Type
80 }
81
82 func (check *Checker) monomorph() {
83
84
85
86
87
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
98
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
122
123
124
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
132
133
134 for stack[0] != v {
135 stack = stack[1:]
136 }
137
138
139
140 var err error_
141 err.code = InvalidInstanceCycle
142 obj0 := check.mono.vertices[v].obj
143 err.errorf(obj0, "instantiation cycle:")
144
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
149
150 switch obj.Type().(type) {
151 default:
152 panic("unexpected type")
153 case *Named:
154 err.errorf(edge.pos, "%s implicitly parameterized by %s", obj.Name(), TypeString(edge.typ, qf))
155 case *TypeParam:
156 err.errorf(edge.pos, "%s instantiated as %s", obj.Name(), TypeString(edge.typ, qf))
157 }
158 }
159 check.report(&err)
160 }
161
162
163
164 func (w *monoGraph) recordCanon(mpar, tpar *TypeParam) {
165 if w.canon == nil {
166 w.canon = make(map[*TypeParam]*TypeParam)
167 }
168 w.canon[mpar] = tpar
169 }
170
171
172
173 func (w *monoGraph) recordInstance(pkg *Package, pos syntax.Pos, tparams []*TypeParam, targs []Type, xlist []syntax.Expr) {
174 for i, tpar := range tparams {
175 pos := pos
176 if i < len(xlist) {
177 pos = syntax.StartPos(xlist[i])
178 }
179 w.assign(pkg, pos, tpar, targs[i])
180 }
181 }
182
183
184 func (w *monoGraph) assign(pkg *Package, pos syntax.Pos, tpar *TypeParam, targ Type) {
185
186
187
188
189
190
191
192
193 if tpar.Obj().Pkg() != pkg {
194 return
195 }
196
197
198 flow := func(src int, typ Type) {
199 weight := 1
200 if typ == targ {
201 weight = 0
202 }
203
204 w.addEdge(w.typeParamVertex(tpar), src, weight, pos, targ)
205 }
206
207
208
209 var do func(typ Type)
210 do = func(typ Type) {
211 switch typ := Unalias(typ).(type) {
212 default:
213 panic("unexpected type")
214
215 case *TypeParam:
216 assert(typ.Obj().Pkg() == pkg)
217 flow(w.typeParamVertex(typ), typ)
218
219 case *Named:
220 if src := w.localNamedVertex(pkg, typ.Origin()); src >= 0 {
221 flow(src, typ)
222 }
223
224 targs := typ.TypeArgs()
225 for i := 0; i < targs.Len(); i++ {
226 do(targs.At(i))
227 }
228
229 case *Array:
230 do(typ.Elem())
231 case *Basic:
232
233 case *Chan:
234 do(typ.Elem())
235 case *Map:
236 do(typ.Key())
237 do(typ.Elem())
238 case *Pointer:
239 do(typ.Elem())
240 case *Slice:
241 do(typ.Elem())
242
243 case *Interface:
244 for i := 0; i < typ.NumMethods(); i++ {
245 do(typ.Method(i).Type())
246 }
247 case *Signature:
248 tuple := func(tup *Tuple) {
249 for i := 0; i < tup.Len(); i++ {
250 do(tup.At(i).Type())
251 }
252 }
253 tuple(typ.Params())
254 tuple(typ.Results())
255 case *Struct:
256 for i := 0; i < typ.NumFields(); i++ {
257 do(typ.Field(i).Type())
258 }
259 }
260 }
261 do(targ)
262 }
263
264
265
266 func (w *monoGraph) localNamedVertex(pkg *Package, named *Named) int {
267 obj := named.Obj()
268 if obj.Pkg() != pkg {
269 return -1
270 }
271
272 root := pkg.Scope()
273 if obj.Parent() == root {
274 return -1
275 }
276
277 if idx, ok := w.nameIdx[obj]; ok {
278 return idx
279 }
280
281 idx := -1
282
283
284
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 {
289 if idx < 0 {
290 idx = len(w.vertices)
291 w.vertices = append(w.vertices, monoVertex{obj: obj})
292 }
293
294 w.addEdge(idx, w.typeParamVertex(tpar), 1, obj.Pos(), tpar)
295 }
296 }
297 }
298 }
299
300 if w.nameIdx == nil {
301 w.nameIdx = make(map[*TypeName]int)
302 }
303 w.nameIdx[obj] = idx
304 return idx
305 }
306
307
308 func (w *monoGraph) typeParamVertex(tpar *TypeParam) int {
309 if x, ok := w.canon[tpar]; ok {
310 tpar = x
311 }
312
313 obj := tpar.Obj()
314
315 if idx, ok := w.nameIdx[obj]; ok {
316 return idx
317 }
318
319 if w.nameIdx == nil {
320 w.nameIdx = make(map[*TypeName]int)
321 }
322
323 idx := len(w.vertices)
324 w.vertices = append(w.vertices, monoVertex{obj: obj})
325 w.nameIdx[obj] = idx
326 return idx
327 }
328
329 func (w *monoGraph) addEdge(dst, src, weight int, pos syntax.Pos, typ Type) {
330
331 w.edges = append(w.edges, monoEdge{
332 dst: dst,
333 src: src,
334 weight: weight,
335
336 pos: pos,
337 typ: typ,
338 })
339 }
340
View as plain text