subst.go raw
1 // Code generated by "go test -run=Generate -write=all"; DO NOT EDIT.
2 // Source: ../../cmd/compile/internal/types2/subst.go
3
4 // Copyright 2018 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 // This file implements type parameter substitution.
9
10 package types
11
12 import (
13 "go/token"
14 )
15
16 type substMap map[*TypeParam]Type
17
18 // makeSubstMap creates a new substitution map mapping tpars[i] to targs[i].
19 // If targs[i] is nil, tpars[i] is not substituted.
20 func makeSubstMap(tpars []*TypeParam, targs []Type) substMap {
21 assert(len(tpars) == len(targs))
22 proj := make(substMap, len(tpars))
23 for i, tpar := range tpars {
24 proj[tpar] = targs[i]
25 }
26 return proj
27 }
28
29 // makeRenameMap is like makeSubstMap, but creates a map used to rename type
30 // parameters in from with the type parameters in to.
31 func makeRenameMap(from, to []*TypeParam) substMap {
32 assert(len(from) == len(to))
33 proj := make(substMap, len(from))
34 for i, tpar := range from {
35 proj[tpar] = to[i]
36 }
37 return proj
38 }
39
40 func (m substMap) empty() bool {
41 return len(m) == 0
42 }
43
44 func (m substMap) lookup(tpar *TypeParam) Type {
45 if t := m[tpar]; t != nil {
46 return t
47 }
48 return tpar
49 }
50
51 // subst returns the type typ with its type parameters tpars replaced by the
52 // corresponding type arguments targs, recursively. subst doesn't modify the
53 // incoming type. If a substitution took place, the result type is different
54 // from the incoming type.
55 //
56 // If expanding is non-nil, it is the instance type currently being expanded.
57 // One of expanding or ctxt must be non-nil.
58 func (check *Checker) subst(pos token.Pos, typ Type, smap substMap, expanding *Named, ctxt *Context) Type {
59 assert(expanding != nil || ctxt != nil)
60
61 if smap.empty() {
62 return typ
63 }
64
65 // common cases
66 switch t := typ.(type) {
67 case *Basic:
68 return typ // nothing to do
69 case *TypeParam:
70 return smap.lookup(t)
71 }
72
73 // general case
74 subst := subster{
75 pos: pos,
76 smap: smap,
77 check: check,
78 expanding: expanding,
79 ctxt: ctxt,
80 }
81 return subst.typ(typ)
82 }
83
84 type subster struct {
85 pos token.Pos
86 smap substMap
87 check *Checker // nil if called via Instantiate
88 expanding *Named // if non-nil, the instance that is being expanded
89 ctxt *Context
90 }
91
92 func (subst *subster) typ(typ Type) Type {
93 switch t := typ.(type) {
94 case nil:
95 // Call typOrNil if it's possible that typ is nil.
96 panic("nil typ")
97
98 case *Basic:
99 // nothing to do
100
101 case *Alias:
102 // This code follows the code for *Named types closely.
103 // TODO(gri) try to factor better
104 orig := t.Origin()
105 n := orig.TypeParams().Len()
106 if n == 0 {
107 return t // type is not parameterized
108 }
109
110 // TODO(gri) do we need this for Alias types?
111 if t.TypeArgs().Len() != n {
112 return Typ[Invalid] // error reported elsewhere
113 }
114
115 // already instantiated
116 // For each (existing) type argument determine if it needs
117 // to be substituted; i.e., if it is or contains a type parameter
118 // that has a type argument for it.
119 if targs := substList(t.TypeArgs().list(), subst.typ); targs != nil {
120 return subst.check.newAliasInstance(subst.pos, t.orig, targs, subst.expanding, subst.ctxt)
121 }
122
123 case *Array:
124 elem := subst.typOrNil(t.elem)
125 if elem != t.elem {
126 return &Array{len: t.len, elem: elem}
127 }
128
129 case *Slice:
130 elem := subst.typOrNil(t.elem)
131 if elem != t.elem {
132 return &Slice{elem: elem}
133 }
134
135 case *Struct:
136 if fields := substList(t.fields, subst.var_); fields != nil {
137 s := &Struct{fields: fields, tags: t.tags}
138 s.markComplete()
139 return s
140 }
141
142 case *Pointer:
143 base := subst.typ(t.base)
144 if base != t.base {
145 return &Pointer{base: base}
146 }
147
148 case *Tuple:
149 return subst.tuple(t)
150
151 case *Signature:
152 // Preserve the receiver: it is handled during *Interface and *Named type
153 // substitution.
154 //
155 // Naively doing the substitution here can lead to an infinite recursion in
156 // the case where the receiver is an interface. For example, consider the
157 // following declaration:
158 //
159 // type T[A any] struct { f interface{ m() } }
160 //
161 // In this case, the type of f is an interface that is itself the receiver
162 // type of all of its methods. Because we have no type name to break
163 // cycles, substituting in the recv results in an infinite loop of
164 // recv->interface->recv->interface->...
165 recv := t.recv
166
167 params := subst.tuple(t.params)
168 results := subst.tuple(t.results)
169 if params != t.params || results != t.results {
170 return &Signature{
171 rparams: t.rparams,
172 // TODO(gri) why can't we nil out tparams here, rather than in instantiate?
173 tparams: t.tparams,
174 // instantiated signatures have a nil scope
175 recv: recv,
176 params: params,
177 results: results,
178 variadic: t.variadic,
179 }
180 }
181
182 case *Union:
183 if terms := substList(t.terms, subst.term); terms != nil {
184 // term list substitution may introduce duplicate terms (unlikely but possible).
185 // This is ok; lazy type set computation will determine the actual type set
186 // in normal form.
187 return &Union{terms}
188 }
189
190 case *Interface:
191 methods := substList(t.methods, subst.func_)
192 embeddeds := substList(t.embeddeds, subst.typ)
193 if methods != nil || embeddeds != nil {
194 if methods == nil {
195 methods = t.methods
196 }
197 if embeddeds == nil {
198 embeddeds = t.embeddeds
199 }
200 iface := subst.check.newInterface()
201 iface.embeddeds = embeddeds
202 iface.embedPos = t.embedPos
203 iface.implicit = t.implicit
204 assert(t.complete) // otherwise we are copying incomplete data
205 iface.complete = t.complete
206 // If we've changed the interface type, we may need to replace its
207 // receiver if the receiver type is the original interface. Receivers of
208 // *Named type are replaced during named type expansion.
209 //
210 // Notably, it's possible to reach here and not create a new *Interface,
211 // even though the receiver type may be parameterized. For example:
212 //
213 // type T[P any] interface{ m() }
214 //
215 // In this case the interface will not be substituted here, because its
216 // method signatures do not depend on the type parameter P, but we still
217 // need to create new interface methods to hold the instantiated
218 // receiver. This is handled by Named.expandUnderlying.
219 iface.methods, _ = replaceRecvType(methods, t, iface)
220
221 // If check != nil, check.newInterface will have saved the interface for later completion.
222 if subst.check == nil { // golang/go#61561: all newly created interfaces must be completed
223 iface.typeSet()
224 }
225 return iface
226 }
227
228 case *Map:
229 key := subst.typ(t.key)
230 elem := subst.typ(t.elem)
231 if key != t.key || elem != t.elem {
232 return &Map{key: key, elem: elem}
233 }
234
235 case *Chan:
236 elem := subst.typ(t.elem)
237 if elem != t.elem {
238 return &Chan{dir: t.dir, elem: elem}
239 }
240
241 case *Named:
242 // subst is called during expansion, so in this function we need to be
243 // careful not to call any methods that would cause t to be expanded: doing
244 // so would result in deadlock.
245 //
246 // So we call t.Origin().TypeParams() rather than t.TypeParams().
247 orig := t.Origin()
248 n := orig.TypeParams().Len()
249 if n == 0 {
250 return t // type is not parameterized
251 }
252
253 if t.TypeArgs().Len() != n {
254 return Typ[Invalid] // error reported elsewhere
255 }
256
257 // already instantiated
258 // For each (existing) type argument determine if it needs
259 // to be substituted; i.e., if it is or contains a type parameter
260 // that has a type argument for it.
261 if targs := substList(t.TypeArgs().list(), subst.typ); targs != nil {
262 // Create a new instance and populate the context to avoid endless
263 // recursion. The position used here is irrelevant because validation only
264 // occurs on t (we don't call validType on named), but we use subst.pos to
265 // help with debugging.
266 return subst.check.instance(subst.pos, orig, targs, subst.expanding, subst.ctxt)
267 }
268
269 case *TypeParam:
270 return subst.smap.lookup(t)
271
272 default:
273 panic("unreachable")
274 }
275
276 return typ
277 }
278
279 // typOrNil is like typ but if the argument is nil it is replaced with Typ[Invalid].
280 // A nil type may appear in pathological cases such as type T[P any] []func(_ T([]_))
281 // where an array/slice element is accessed before it is set up.
282 func (subst *subster) typOrNil(typ Type) Type {
283 if typ == nil {
284 return Typ[Invalid]
285 }
286 return subst.typ(typ)
287 }
288
289 func (subst *subster) var_(v *Var) *Var {
290 if v != nil {
291 if typ := subst.typ(v.typ); typ != v.typ {
292 return cloneVar(v, typ)
293 }
294 }
295 return v
296 }
297
298 func cloneVar(v *Var, typ Type) *Var {
299 copy := *v
300 copy.typ = typ
301 copy.origin = v.Origin()
302 return ©
303 }
304
305 func (subst *subster) tuple(t *Tuple) *Tuple {
306 if t != nil {
307 if vars := substList(t.vars, subst.var_); vars != nil {
308 return &Tuple{vars: vars}
309 }
310 }
311 return t
312 }
313
314 // substList applies subst to each element of the incoming slice.
315 // If at least one element changes, the result is a new slice with
316 // all the (possibly updated) elements of the incoming slice;
317 // otherwise the result it nil. The incoming slice is unchanged.
318 func substList[T comparable](in []T, subst func(T) T) (out []T) {
319 for i, t := range in {
320 if u := subst(t); u != t {
321 if out == nil {
322 // lazily allocate a new slice on first substitution
323 out = make([]T, len(in))
324 copy(out, in)
325 }
326 out[i] = u
327 }
328 }
329 return
330 }
331
332 func (subst *subster) func_(f *Func) *Func {
333 if f != nil {
334 if typ := subst.typ(f.typ); typ != f.typ {
335 return cloneFunc(f, typ)
336 }
337 }
338 return f
339 }
340
341 func cloneFunc(f *Func, typ Type) *Func {
342 copy := *f
343 copy.typ = typ
344 copy.origin = f.Origin()
345 return ©
346 }
347
348 func (subst *subster) term(t *Term) *Term {
349 if typ := subst.typ(t.typ); typ != t.typ {
350 return NewTerm(t.tilde, typ)
351 }
352 return t
353 }
354
355 // replaceRecvType updates any function receivers that have type old to have
356 // type new. It does not modify the input slice; if modifications are required,
357 // the input slice and any affected signatures will be copied before mutating.
358 //
359 // The resulting out slice contains the updated functions, and copied reports
360 // if anything was modified.
361 func replaceRecvType(in []*Func, old, new Type) (out []*Func, copied bool) {
362 out = in
363 for i, method := range in {
364 sig := method.Signature()
365 if sig.recv != nil && sig.recv.Type() == old {
366 if !copied {
367 // Allocate a new methods slice before mutating for the first time.
368 // This is defensive, as we may share methods across instantiations of
369 // a given interface type if they do not get substituted.
370 out = make([]*Func, len(in))
371 copy(out, in)
372 copied = true
373 }
374 newsig := *sig
375 newsig.recv = cloneVar(sig.recv, new)
376 out[i] = cloneFunc(method, &newsig)
377 }
378 }
379 return
380 }
381