instantiate.go raw
1 // Code generated by "go test -run=Generate -write=all"; DO NOT EDIT.
2 // Source: ../../cmd/compile/internal/types2/instantiate.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 // This file implements instantiation of generic types
9 // through substitution of type parameters by type arguments.
10
11 package types
12
13 import (
14 "errors"
15 "fmt"
16 "go/token"
17 "internal/buildcfg"
18 . "internal/types/errors"
19 )
20
21 // A genericType implements access to its type parameters.
22 type genericType interface {
23 Type
24 TypeParams() *TypeParamList
25 }
26
27 // Instantiate instantiates the type orig with the given type arguments targs.
28 // orig must be an *Alias, *Named, or *Signature type. If there is no error,
29 // the resulting Type is an instantiated type of the same kind (*Alias, *Named
30 // or *Signature, respectively).
31 //
32 // Methods attached to a *Named type are also instantiated, and associated with
33 // a new *Func that has the same position as the original method, but nil function
34 // scope.
35 //
36 // If ctxt is non-nil, it may be used to de-duplicate the instance against
37 // previous instances with the same identity. As a special case, generic
38 // *Signature origin types are only considered identical if they are pointer
39 // equivalent, so that instantiating distinct (but possibly identical)
40 // signatures will yield different instances. The use of a shared context does
41 // not guarantee that identical instances are deduplicated in all cases.
42 //
43 // If validate is set, Instantiate verifies that the number of type arguments
44 // and parameters match, and that the type arguments satisfy their respective
45 // type constraints. If verification fails, the resulting error may wrap an
46 // *ArgumentError indicating which type argument did not satisfy its type parameter
47 // constraint, and why.
48 //
49 // If validate is not set, Instantiate does not verify the type argument count
50 // or whether the type arguments satisfy their constraints. Instantiate is
51 // guaranteed to not return an error, but may panic. Specifically, for
52 // *Signature types, Instantiate will panic immediately if the type argument
53 // count is incorrect; for *Named types, a panic may occur later inside the
54 // *Named API.
55 func Instantiate(ctxt *Context, orig Type, targs []Type, validate bool) (Type, error) {
56 assert(len(targs) > 0)
57 if ctxt == nil {
58 ctxt = NewContext()
59 }
60 orig_ := orig.(genericType) // signature of Instantiate must not change for backward-compatibility
61
62 if validate {
63 tparams := orig_.TypeParams().list()
64 assert(len(tparams) > 0)
65 if len(targs) != len(tparams) {
66 return nil, fmt.Errorf("got %d type arguments but %s has %d type parameters", len(targs), orig, len(tparams))
67 }
68 if i, err := (*Checker)(nil).verify(nopos, tparams, targs, ctxt); err != nil {
69 return nil, &ArgumentError{i, err}
70 }
71 }
72
73 inst := (*Checker)(nil).instance(nopos, orig_, targs, nil, ctxt)
74 return inst, nil
75 }
76
77 // instance instantiates the given original (generic) function or type with the
78 // provided type arguments and returns the resulting instance. If an identical
79 // instance exists already in the given contexts, it returns that instance,
80 // otherwise it creates a new one. If there is an error (such as wrong number
81 // of type arguments), the result is Typ[Invalid].
82 //
83 // If expanding is non-nil, it is the Named instance type currently being
84 // expanded. If ctxt is non-nil, it is the context associated with the current
85 // type-checking pass or call to Instantiate. At least one of expanding or ctxt
86 // must be non-nil.
87 //
88 // For Named types the resulting instance may be unexpanded.
89 //
90 // check may be nil (when not type-checking syntax); pos is used only only if check is non-nil.
91 func (check *Checker) instance(pos token.Pos, orig genericType, targs []Type, expanding *Named, ctxt *Context) (res Type) {
92 // The order of the contexts below matters: we always prefer instances in the
93 // expanding instance context in order to preserve reference cycles.
94 //
95 // Invariant: if expanding != nil, the returned instance will be the instance
96 // recorded in expanding.inst.ctxt.
97 var ctxts []*Context
98 if expanding != nil {
99 ctxts = append(ctxts, expanding.inst.ctxt)
100 }
101 if ctxt != nil {
102 ctxts = append(ctxts, ctxt)
103 }
104 assert(len(ctxts) > 0)
105
106 // Compute all hashes; hashes may differ across contexts due to different
107 // unique IDs for Named types within the hasher.
108 hashes := make([]string, len(ctxts))
109 for i, ctxt := range ctxts {
110 hashes[i] = ctxt.instanceHash(orig, targs)
111 }
112
113 // Record the result in all contexts.
114 // Prefer to re-use existing types from expanding context, if it exists, to reduce
115 // the memory pinned by the Named type.
116 updateContexts := func(res Type) Type {
117 for i := len(ctxts) - 1; i >= 0; i-- {
118 res = ctxts[i].update(hashes[i], orig, targs, res)
119 }
120 return res
121 }
122
123 // typ may already have been instantiated with identical type arguments. In
124 // that case, re-use the existing instance.
125 for i, ctxt := range ctxts {
126 if inst := ctxt.lookup(hashes[i], orig, targs); inst != nil {
127 return updateContexts(inst)
128 }
129 }
130
131 switch orig := orig.(type) {
132 case *Named:
133 res = check.newNamedInstance(pos, orig, targs, expanding) // substituted lazily
134
135 case *Alias:
136 if !buildcfg.Experiment.AliasTypeParams {
137 assert(expanding == nil) // Alias instances cannot be reached from Named types
138 }
139
140 // verify type parameter count (see go.dev/issue/71198 for a test case)
141 tparams := orig.TypeParams()
142 if !check.validateTArgLen(pos, orig.obj.Name(), tparams.Len(), len(targs)) {
143 // TODO(gri) Consider returning a valid alias instance with invalid
144 // underlying (aliased) type to match behavior of *Named
145 // types. Then this function will never return an invalid
146 // result.
147 return Typ[Invalid]
148 }
149 if tparams.Len() == 0 {
150 return orig // nothing to do (minor optimization)
151 }
152
153 res = check.newAliasInstance(pos, orig, targs, expanding, ctxt)
154
155 case *Signature:
156 assert(expanding == nil) // function instances cannot be reached from Named types
157
158 tparams := orig.TypeParams()
159 // TODO(gri) investigate if this is needed (type argument and parameter count seem to be correct here)
160 if !check.validateTArgLen(pos, orig.String(), tparams.Len(), len(targs)) {
161 return Typ[Invalid]
162 }
163 if tparams.Len() == 0 {
164 return orig // nothing to do (minor optimization)
165 }
166 sig := check.subst(pos, orig, makeSubstMap(tparams.list(), targs), nil, ctxt).(*Signature)
167 // If the signature doesn't use its type parameters, subst
168 // will not make a copy. In that case, make a copy now (so
169 // we can set tparams to nil w/o causing side-effects).
170 if sig == orig {
171 copy := *sig
172 sig = ©
173 }
174 // After instantiating a generic signature, it is not generic
175 // anymore; we need to set tparams to nil.
176 sig.tparams = nil
177 res = sig
178
179 default:
180 // only types and functions can be generic
181 panic(fmt.Sprintf("%v: cannot instantiate %v", pos, orig))
182 }
183
184 // Update all contexts; it's possible that we've lost a race.
185 return updateContexts(res)
186 }
187
188 // validateTArgLen checks that the number of type arguments (got) matches the
189 // number of type parameters (want); if they don't match an error is reported.
190 // If validation fails and check is nil, validateTArgLen panics.
191 func (check *Checker) validateTArgLen(pos token.Pos, name string, want, got int) bool {
192 var qual string
193 switch {
194 case got < want:
195 qual = "not enough"
196 case got > want:
197 qual = "too many"
198 default:
199 return true
200 }
201
202 msg := check.sprintf("%s type arguments for type %s: have %d, want %d", qual, name, got, want)
203 if check != nil {
204 check.error(atPos(pos), WrongTypeArgCount, msg)
205 return false
206 }
207
208 panic(fmt.Sprintf("%v: %s", pos, msg))
209 }
210
211 // check may be nil; pos is used only if check is non-nil.
212 func (check *Checker) verify(pos token.Pos, tparams []*TypeParam, targs []Type, ctxt *Context) (int, error) {
213 smap := makeSubstMap(tparams, targs)
214 for i, tpar := range tparams {
215 // Ensure that we have a (possibly implicit) interface as type bound (go.dev/issue/51048).
216 tpar.iface()
217 // The type parameter bound is parameterized with the same type parameters
218 // as the instantiated type; before we can use it for bounds checking we
219 // need to instantiate it with the type arguments with which we instantiated
220 // the parameterized type.
221 bound := check.subst(pos, tpar.bound, smap, nil, ctxt)
222 var cause string
223 if !check.implements(targs[i], bound, true, &cause) {
224 return i, errors.New(cause)
225 }
226 }
227 return -1, nil
228 }
229
230 // implements checks if V implements T. The receiver may be nil if implements
231 // is called through an exported API call such as AssignableTo. If constraint
232 // is set, T is a type constraint.
233 //
234 // If the provided cause is non-nil, it may be set to an error string
235 // explaining why V does not implement (or satisfy, for constraints) T.
236 func (check *Checker) implements(V, T Type, constraint bool, cause *string) bool {
237 Vu := under(V)
238 Tu := under(T)
239 if !isValid(Vu) || !isValid(Tu) {
240 return true // avoid follow-on errors
241 }
242 if p, _ := Vu.(*Pointer); p != nil && !isValid(under(p.base)) {
243 return true // avoid follow-on errors (see go.dev/issue/49541 for an example)
244 }
245
246 verb := "implement"
247 if constraint {
248 verb = "satisfy"
249 }
250
251 Ti, _ := Tu.(*Interface)
252 if Ti == nil {
253 if cause != nil {
254 var detail string
255 if isInterfacePtr(Tu) {
256 detail = check.sprintf("type %s is pointer to interface, not interface", T)
257 } else {
258 detail = check.sprintf("%s is not an interface", T)
259 }
260 *cause = check.sprintf("%s does not %s %s (%s)", V, verb, T, detail)
261 }
262 return false
263 }
264
265 // Every type satisfies the empty interface.
266 if Ti.Empty() {
267 return true
268 }
269 // T is not the empty interface (i.e., the type set of T is restricted)
270
271 // An interface V with an empty type set satisfies any interface.
272 // (The empty set is a subset of any set.)
273 Vi, _ := Vu.(*Interface)
274 if Vi != nil && Vi.typeSet().IsEmpty() {
275 return true
276 }
277 // type set of V is not empty
278
279 // No type with non-empty type set satisfies the empty type set.
280 if Ti.typeSet().IsEmpty() {
281 if cause != nil {
282 *cause = check.sprintf("cannot %s %s (empty type set)", verb, T)
283 }
284 return false
285 }
286
287 // V must implement T's methods, if any.
288 if !check.hasAllMethods(V, T, true, Identical, cause) /* !Implements(V, T) */ {
289 if cause != nil {
290 *cause = check.sprintf("%s does not %s %s %s", V, verb, T, *cause)
291 }
292 return false
293 }
294
295 // Only check comparability if we don't have a more specific error.
296 checkComparability := func() bool {
297 if !Ti.IsComparable() {
298 return true
299 }
300 // If T is comparable, V must be comparable.
301 // If V is strictly comparable, we're done.
302 if comparableType(V, false /* strict comparability */, nil) == nil {
303 return true
304 }
305 // For constraint satisfaction, use dynamic (spec) comparability
306 // so that ordinary, non-type parameter interfaces implement comparable.
307 if constraint && comparableType(V, true /* spec comparability */, nil) == nil {
308 // V is comparable if we are at Go 1.20 or higher.
309 if check == nil || check.allowVersion(go1_20) {
310 return true
311 }
312 if cause != nil {
313 *cause = check.sprintf("%s to %s comparable requires go1.20 or later", V, verb)
314 }
315 return false
316 }
317 if cause != nil {
318 *cause = check.sprintf("%s does not %s comparable", V, verb)
319 }
320 return false
321 }
322
323 // V must also be in the set of types of T, if any.
324 // Constraints with empty type sets were already excluded above.
325 if !Ti.typeSet().hasTerms() {
326 return checkComparability() // nothing to do
327 }
328
329 // If V is itself an interface, each of its possible types must be in the set
330 // of T types (i.e., the V type set must be a subset of the T type set).
331 // Interfaces V with empty type sets were already excluded above.
332 if Vi != nil {
333 if !Vi.typeSet().subsetOf(Ti.typeSet()) {
334 // TODO(gri) report which type is missing
335 if cause != nil {
336 *cause = check.sprintf("%s does not %s %s", V, verb, T)
337 }
338 return false
339 }
340 return checkComparability()
341 }
342
343 // Otherwise, V's type must be included in the iface type set.
344 var alt Type
345 if Ti.typeSet().is(func(t *term) bool {
346 if !t.includes(V) {
347 // If V ∉ t.typ but V ∈ ~t.typ then remember this type
348 // so we can suggest it as an alternative in the error
349 // message.
350 if alt == nil && !t.tilde && Identical(t.typ, under(t.typ)) {
351 tt := *t
352 tt.tilde = true
353 if tt.includes(V) {
354 alt = t.typ
355 }
356 }
357 return true
358 }
359 return false
360 }) {
361 if cause != nil {
362 var detail string
363 switch {
364 case alt != nil:
365 detail = check.sprintf("possibly missing ~ for %s in %s", alt, T)
366 case mentions(Ti, V):
367 detail = check.sprintf("%s mentions %s, but %s is not in the type set of %s", T, V, V, T)
368 default:
369 detail = check.sprintf("%s missing in %s", V, Ti.typeSet().terms)
370 }
371 *cause = check.sprintf("%s does not %s %s (%s)", V, verb, T, detail)
372 }
373 return false
374 }
375
376 return checkComparability()
377 }
378
379 // mentions reports whether type T "mentions" typ in an (embedded) element or term
380 // of T (whether typ is in the type set of T or not). For better error messages.
381 func mentions(T, typ Type) bool {
382 switch T := T.(type) {
383 case *Interface:
384 for _, e := range T.embeddeds {
385 if mentions(e, typ) {
386 return true
387 }
388 }
389 case *Union:
390 for _, t := range T.terms {
391 if mentions(t.typ, typ) {
392 return true
393 }
394 }
395 default:
396 if Identical(T, typ) {
397 return true
398 }
399 }
400 return false
401 }
402