Dan Willemsen | 59ee780 | 2021-12-15 01:08:25 -0800 | [diff] [blame] | 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. |
| 4 | |
| 5 | // This file implements instantiation of generic types |
| 6 | // through substitution of type parameters by type arguments. |
| 7 | |
| 8 | package types |
| 9 | |
| 10 | import ( |
| 11 | "errors" |
| 12 | "fmt" |
| 13 | "go/token" |
| 14 | ) |
| 15 | |
| 16 | // Instantiate instantiates the type orig with the given type arguments targs. |
| 17 | // orig must be a *Named or a *Signature type. If there is no error, the |
| 18 | // resulting Type is a new, instantiated (not parameterized) type of the same |
| 19 | // kind (either a *Named or a *Signature). Methods attached to a *Named type |
| 20 | // are also instantiated, and associated with a new *Func that has the same |
| 21 | // position as the original method, but nil function scope. |
| 22 | // |
| 23 | // If ctxt is non-nil, it may be used to de-duplicate the instance against |
| 24 | // previous instances with the same identity. As a special case, generic |
| 25 | // *Signature origin types are only considered identical if they are pointer |
| 26 | // equivalent, so that instantiating distinct (but possibly identical) |
| 27 | // signatures will yield different instances. |
| 28 | // |
| 29 | // If validate is set, Instantiate verifies that the number of type arguments |
| 30 | // and parameters match, and that the type arguments satisfy their |
| 31 | // corresponding type constraints. If verification fails, the resulting error |
| 32 | // may wrap an *ArgumentError indicating which type argument did not satisfy |
| 33 | // its corresponding type parameter constraint, and why. |
| 34 | // |
| 35 | // If validate is not set, Instantiate does not verify the type argument count |
| 36 | // or whether the type arguments satisfy their constraints. Instantiate is |
| 37 | // guaranteed to not return an error, but may panic. Specifically, for |
| 38 | // *Signature types, Instantiate will panic immediately if the type argument |
| 39 | // count is incorrect; for *Named types, a panic may occur later inside the |
| 40 | // *Named API. |
| 41 | func Instantiate(ctxt *Context, orig Type, targs []Type, validate bool) (Type, error) { |
| 42 | if validate { |
| 43 | var tparams []*TypeParam |
| 44 | switch t := orig.(type) { |
| 45 | case *Named: |
| 46 | tparams = t.TypeParams().list() |
| 47 | case *Signature: |
| 48 | tparams = t.TypeParams().list() |
| 49 | } |
| 50 | if len(targs) != len(tparams) { |
| 51 | return nil, fmt.Errorf("got %d type arguments but %s has %d type parameters", len(targs), orig, len(tparams)) |
| 52 | } |
| 53 | if i, err := (*Checker)(nil).verify(token.NoPos, tparams, targs); err != nil { |
| 54 | return nil, &ArgumentError{i, err} |
| 55 | } |
| 56 | } |
| 57 | |
| 58 | inst := (*Checker)(nil).instance(token.NoPos, orig, targs, ctxt) |
| 59 | return inst, nil |
| 60 | } |
| 61 | |
| 62 | // instance creates a type or function instance using the given original type |
| 63 | // typ and arguments targs. For Named types the resulting instance will be |
| 64 | // unexpanded. |
| 65 | func (check *Checker) instance(pos token.Pos, orig Type, targs []Type, ctxt *Context) (res Type) { |
| 66 | var h string |
| 67 | if ctxt != nil { |
| 68 | h = ctxt.instanceHash(orig, targs) |
| 69 | // typ may already have been instantiated with identical type arguments. In |
| 70 | // that case, re-use the existing instance. |
| 71 | if inst := ctxt.lookup(h, orig, targs); inst != nil { |
| 72 | return inst |
| 73 | } |
| 74 | } |
| 75 | |
| 76 | switch orig := orig.(type) { |
| 77 | case *Named: |
| 78 | tname := NewTypeName(pos, orig.obj.pkg, orig.obj.name, nil) |
| 79 | named := check.newNamed(tname, orig, nil, nil, nil) // underlying, tparams, and methods are set when named is resolved |
| 80 | named.targs = newTypeList(targs) |
Dan Willemsen | 14b5f99 | 2022-03-10 14:27:21 -0800 | [diff] [blame] | 81 | named.resolver = func(ctxt *Context, n *Named) (*TypeParamList, Type, *methodList) { |
Dan Willemsen | 59ee780 | 2021-12-15 01:08:25 -0800 | [diff] [blame] | 82 | return expandNamed(ctxt, n, pos) |
| 83 | } |
| 84 | res = named |
| 85 | |
| 86 | case *Signature: |
| 87 | tparams := orig.TypeParams() |
| 88 | if !check.validateTArgLen(pos, tparams.Len(), len(targs)) { |
| 89 | return Typ[Invalid] |
| 90 | } |
| 91 | if tparams.Len() == 0 { |
| 92 | return orig // nothing to do (minor optimization) |
| 93 | } |
| 94 | sig := check.subst(pos, orig, makeSubstMap(tparams.list(), targs), ctxt).(*Signature) |
| 95 | // If the signature doesn't use its type parameters, subst |
| 96 | // will not make a copy. In that case, make a copy now (so |
| 97 | // we can set tparams to nil w/o causing side-effects). |
| 98 | if sig == orig { |
| 99 | copy := *sig |
| 100 | sig = © |
| 101 | } |
| 102 | // After instantiating a generic signature, it is not generic |
| 103 | // anymore; we need to set tparams to nil. |
| 104 | sig.tparams = nil |
| 105 | res = sig |
| 106 | default: |
| 107 | // only types and functions can be generic |
| 108 | panic(fmt.Sprintf("%v: cannot instantiate %v", pos, orig)) |
| 109 | } |
| 110 | |
| 111 | if ctxt != nil { |
| 112 | // It's possible that we've lost a race to add named to the context. |
| 113 | // In this case, use whichever instance is recorded in the context. |
| 114 | res = ctxt.update(h, orig, targs, res) |
| 115 | } |
| 116 | |
| 117 | return res |
| 118 | } |
| 119 | |
| 120 | // validateTArgLen verifies that the length of targs and tparams matches, |
| 121 | // reporting an error if not. If validation fails and check is nil, |
| 122 | // validateTArgLen panics. |
| 123 | func (check *Checker) validateTArgLen(pos token.Pos, ntparams, ntargs int) bool { |
| 124 | if ntargs != ntparams { |
| 125 | // TODO(gri) provide better error message |
| 126 | if check != nil { |
| 127 | check.errorf(atPos(pos), _WrongTypeArgCount, "got %d arguments but %d type parameters", ntargs, ntparams) |
| 128 | return false |
| 129 | } |
| 130 | panic(fmt.Sprintf("%v: got %d arguments but %d type parameters", pos, ntargs, ntparams)) |
| 131 | } |
| 132 | return true |
| 133 | } |
| 134 | |
| 135 | func (check *Checker) verify(pos token.Pos, tparams []*TypeParam, targs []Type) (int, error) { |
Dan Willemsen | 59ee780 | 2021-12-15 01:08:25 -0800 | [diff] [blame] | 136 | smap := makeSubstMap(tparams, targs) |
| 137 | for i, tpar := range tparams { |
Dan Willemsen | 14b5f99 | 2022-03-10 14:27:21 -0800 | [diff] [blame] | 138 | // Ensure that we have a (possibly implicit) interface as type bound (issue #51048). |
| 139 | tpar.iface() |
Dan Willemsen | 59ee780 | 2021-12-15 01:08:25 -0800 | [diff] [blame] | 140 | // The type parameter bound is parameterized with the same type parameters |
| 141 | // as the instantiated type; before we can use it for bounds checking we |
| 142 | // need to instantiate it with the type arguments with which we instantiated |
| 143 | // the parameterized type. |
| 144 | bound := check.subst(pos, tpar.bound, smap, nil) |
Dan Willemsen | 14b5f99 | 2022-03-10 14:27:21 -0800 | [diff] [blame] | 145 | if err := check.implements(targs[i], bound); err != nil { |
Dan Willemsen | 59ee780 | 2021-12-15 01:08:25 -0800 | [diff] [blame] | 146 | return i, err |
| 147 | } |
| 148 | } |
| 149 | return -1, nil |
| 150 | } |
| 151 | |
| 152 | // implements checks if V implements T and reports an error if it doesn't. |
Dan Willemsen | 14b5f99 | 2022-03-10 14:27:21 -0800 | [diff] [blame] | 153 | // The receiver may be nil if implements is called through an exported |
| 154 | // API call such as AssignableTo. |
| 155 | func (check *Checker) implements(V, T Type) error { |
Dan Willemsen | 59ee780 | 2021-12-15 01:08:25 -0800 | [diff] [blame] | 156 | Vu := under(V) |
| 157 | Tu := under(T) |
| 158 | if Vu == Typ[Invalid] || Tu == Typ[Invalid] { |
Dan Willemsen | 14b5f99 | 2022-03-10 14:27:21 -0800 | [diff] [blame] | 159 | return nil // avoid follow-on errors |
| 160 | } |
| 161 | if p, _ := Vu.(*Pointer); p != nil && under(p.base) == Typ[Invalid] { |
| 162 | return nil // avoid follow-on errors (see issue #49541 for an example) |
Dan Willemsen | 59ee780 | 2021-12-15 01:08:25 -0800 | [diff] [blame] | 163 | } |
| 164 | |
| 165 | errorf := func(format string, args ...any) error { |
Dan Willemsen | 14b5f99 | 2022-03-10 14:27:21 -0800 | [diff] [blame] | 166 | return errors.New(check.sprintf(format, args...)) |
Dan Willemsen | 59ee780 | 2021-12-15 01:08:25 -0800 | [diff] [blame] | 167 | } |
| 168 | |
| 169 | Ti, _ := Tu.(*Interface) |
| 170 | if Ti == nil { |
Dan Willemsen | 14b5f99 | 2022-03-10 14:27:21 -0800 | [diff] [blame] | 171 | var cause string |
| 172 | if isInterfacePtr(Tu) { |
| 173 | cause = check.sprintf("type %s is pointer to interface, not interface", T) |
| 174 | } else { |
| 175 | cause = check.sprintf("%s is not an interface", T) |
| 176 | } |
| 177 | return errorf("%s does not implement %s (%s)", V, T, cause) |
Dan Willemsen | 59ee780 | 2021-12-15 01:08:25 -0800 | [diff] [blame] | 178 | } |
| 179 | |
| 180 | // Every type satisfies the empty interface. |
| 181 | if Ti.Empty() { |
| 182 | return nil |
| 183 | } |
| 184 | // T is not the empty interface (i.e., the type set of T is restricted) |
| 185 | |
| 186 | // An interface V with an empty type set satisfies any interface. |
| 187 | // (The empty set is a subset of any set.) |
| 188 | Vi, _ := Vu.(*Interface) |
| 189 | if Vi != nil && Vi.typeSet().IsEmpty() { |
| 190 | return nil |
| 191 | } |
| 192 | // type set of V is not empty |
| 193 | |
| 194 | // No type with non-empty type set satisfies the empty type set. |
| 195 | if Ti.typeSet().IsEmpty() { |
| 196 | return errorf("cannot implement %s (empty type set)", T) |
| 197 | } |
| 198 | |
Dan Willemsen | 14b5f99 | 2022-03-10 14:27:21 -0800 | [diff] [blame] | 199 | // V must implement T's methods, if any. |
| 200 | if m, wrong := check.missingMethod(V, Ti, true); m != nil /* !Implements(V, Ti) */ { |
| 201 | return errorf("%s does not implement %s %s", V, T, check.missingMethodReason(V, T, m, wrong)) |
Dan Willemsen | 59ee780 | 2021-12-15 01:08:25 -0800 | [diff] [blame] | 202 | } |
| 203 | |
Dan Willemsen | 14b5f99 | 2022-03-10 14:27:21 -0800 | [diff] [blame] | 204 | // If T is comparable, V must be comparable. |
| 205 | // Remember as a pending error and report only if we don't have a more specific error. |
| 206 | var pending error |
| 207 | if Ti.IsComparable() && ((Vi != nil && !Vi.IsComparable()) || (Vi == nil && !Comparable(V))) { |
| 208 | pending = errorf("%s does not implement comparable", V) |
Dan Willemsen | 59ee780 | 2021-12-15 01:08:25 -0800 | [diff] [blame] | 209 | } |
| 210 | |
| 211 | // V must also be in the set of types of T, if any. |
| 212 | // Constraints with empty type sets were already excluded above. |
| 213 | if !Ti.typeSet().hasTerms() { |
Dan Willemsen | 14b5f99 | 2022-03-10 14:27:21 -0800 | [diff] [blame] | 214 | return pending // nothing to do |
Dan Willemsen | 59ee780 | 2021-12-15 01:08:25 -0800 | [diff] [blame] | 215 | } |
| 216 | |
| 217 | // If V is itself an interface, each of its possible types must be in the set |
| 218 | // of T types (i.e., the V type set must be a subset of the T type set). |
| 219 | // Interfaces V with empty type sets were already excluded above. |
| 220 | if Vi != nil { |
| 221 | if !Vi.typeSet().subsetOf(Ti.typeSet()) { |
| 222 | // TODO(gri) report which type is missing |
| 223 | return errorf("%s does not implement %s", V, T) |
| 224 | } |
Dan Willemsen | 14b5f99 | 2022-03-10 14:27:21 -0800 | [diff] [blame] | 225 | return pending |
Dan Willemsen | 59ee780 | 2021-12-15 01:08:25 -0800 | [diff] [blame] | 226 | } |
| 227 | |
| 228 | // Otherwise, V's type must be included in the iface type set. |
| 229 | var alt Type |
| 230 | if Ti.typeSet().is(func(t *term) bool { |
| 231 | if !t.includes(V) { |
| 232 | // If V ∉ t.typ but V ∈ ~t.typ then remember this type |
| 233 | // so we can suggest it as an alternative in the error |
| 234 | // message. |
| 235 | if alt == nil && !t.tilde && Identical(t.typ, under(t.typ)) { |
| 236 | tt := *t |
| 237 | tt.tilde = true |
| 238 | if tt.includes(V) { |
| 239 | alt = t.typ |
| 240 | } |
| 241 | } |
| 242 | return true |
| 243 | } |
| 244 | return false |
| 245 | }) { |
| 246 | if alt != nil { |
| 247 | return errorf("%s does not implement %s (possibly missing ~ for %s in constraint %s)", V, T, alt, T) |
| 248 | } else { |
| 249 | return errorf("%s does not implement %s", V, T) |
| 250 | } |
| 251 | } |
| 252 | |
Dan Willemsen | 14b5f99 | 2022-03-10 14:27:21 -0800 | [diff] [blame] | 253 | return pending |
Dan Willemsen | 59ee780 | 2021-12-15 01:08:25 -0800 | [diff] [blame] | 254 | } |