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 an instantiated type of the same kind (either a *Named or 19 // a *Signature). Methods attached to a *Named type are also instantiated, and 20 // associated with a new *Func that has the same position as the original 21 // 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. The use of a shared context does 28 // not guarantee that identical instances are deduplicated in all cases. 29 // 30 // If validate is set, Instantiate verifies that the number of type arguments 31 // and parameters match, and that the type arguments satisfy their 32 // corresponding type constraints. If verification fails, the resulting error 33 // may wrap an *ArgumentError indicating which type argument did not satisfy 34 // its corresponding type parameter constraint, and why. 35 // 36 // If validate is not set, Instantiate does not verify the type argument count 37 // or whether the type arguments satisfy their constraints. Instantiate is 38 // guaranteed to not return an error, but may panic. Specifically, for 39 // *Signature types, Instantiate will panic immediately if the type argument 40 // count is incorrect; for *Named types, a panic may occur later inside the 41 // *Named API. 42 func Instantiate(ctxt *Context, orig Type, targs []Type, validate bool) (Type, error) { 43 if ctxt == nil { 44 ctxt = NewContext() 45 } 46 if validate { 47 var tparams []*TypeParam 48 switch t := orig.(type) { 49 case *Named: 50 tparams = t.TypeParams().list() 51 case *Signature: 52 tparams = t.TypeParams().list() 53 } 54 if len(targs) != len(tparams) { 55 return nil, fmt.Errorf("got %d type arguments but %s has %d type parameters", len(targs), orig, len(tparams)) 56 } 57 if i, err := (*Checker)(nil).verify(token.NoPos, tparams, targs, ctxt); err != nil { 58 return nil, &ArgumentError{i, err} 59 } 60 } 61 62 inst := (*Checker)(nil).instance(token.NoPos, orig, targs, nil, ctxt) 63 return inst, nil 64 } 65 66 // instance instantiates the given original (generic) function or type with the 67 // provided type arguments and returns the resulting instance. If an identical 68 // instance exists already in the given contexts, it returns that instance, 69 // otherwise it creates a new one. 70 // 71 // If expanding is non-nil, it is the Named instance type currently being 72 // expanded. If ctxt is non-nil, it is the context associated with the current 73 // type-checking pass or call to Instantiate. At least one of expanding or ctxt 74 // must be non-nil. 75 // 76 // For Named types the resulting instance may be unexpanded. 77 func (check *Checker) instance(pos token.Pos, orig Type, targs []Type, expanding *Named, ctxt *Context) (res Type) { 78 // The order of the contexts below matters: we always prefer instances in the 79 // expanding instance context in order to preserve reference cycles. 80 // 81 // Invariant: if expanding != nil, the returned instance will be the instance 82 // recorded in expanding.inst.ctxt. 83 var ctxts []*Context 84 if expanding != nil { 85 ctxts = append(ctxts, expanding.inst.ctxt) 86 } 87 if ctxt != nil { 88 ctxts = append(ctxts, ctxt) 89 } 90 assert(len(ctxts) > 0) 91 92 // Compute all hashes; hashes may differ across contexts due to different 93 // unique IDs for Named types within the hasher. 94 hashes := make([]string, len(ctxts)) 95 for i, ctxt := range ctxts { 96 hashes[i] = ctxt.instanceHash(orig, targs) 97 } 98 99 // If local is non-nil, updateContexts return the type recorded in 100 // local. 101 updateContexts := func(res Type) Type { 102 for i := len(ctxts) - 1; i >= 0; i-- { 103 res = ctxts[i].update(hashes[i], orig, targs, res) 104 } 105 return res 106 } 107 108 // typ may already have been instantiated with identical type arguments. In 109 // that case, re-use the existing instance. 110 for i, ctxt := range ctxts { 111 if inst := ctxt.lookup(hashes[i], orig, targs); inst != nil { 112 return updateContexts(inst) 113 } 114 } 115 116 switch orig := orig.(type) { 117 case *Named: 118 res = check.newNamedInstance(pos, orig, targs, expanding) // substituted lazily 119 120 case *Signature: 121 assert(expanding == nil) // function instances cannot be reached from Named types 122 123 tparams := orig.TypeParams() 124 if !check.validateTArgLen(pos, tparams.Len(), len(targs)) { 125 return Typ[Invalid] 126 } 127 if tparams.Len() == 0 { 128 return orig // nothing to do (minor optimization) 129 } 130 sig := check.subst(pos, orig, makeSubstMap(tparams.list(), targs), nil, ctxt).(*Signature) 131 // If the signature doesn't use its type parameters, subst 132 // will not make a copy. In that case, make a copy now (so 133 // we can set tparams to nil w/o causing side-effects). 134 if sig == orig { 135 copy := *sig 136 sig = © 137 } 138 // After instantiating a generic signature, it is not generic 139 // anymore; we need to set tparams to nil. 140 sig.tparams = nil 141 res = sig 142 143 default: 144 // only types and functions can be generic 145 panic(fmt.Sprintf("%v: cannot instantiate %v", pos, orig)) 146 } 147 148 // Update all contexts; it's possible that we've lost a race. 149 return updateContexts(res) 150 } 151 152 // validateTArgLen verifies that the length of targs and tparams matches, 153 // reporting an error if not. If validation fails and check is nil, 154 // validateTArgLen panics. 155 func (check *Checker) validateTArgLen(pos token.Pos, ntparams, ntargs int) bool { 156 if ntargs != ntparams { 157 // TODO(gri) provide better error message 158 if check != nil { 159 check.errorf(atPos(pos), _WrongTypeArgCount, "got %d arguments but %d type parameters", ntargs, ntparams) 160 return false 161 } 162 panic(fmt.Sprintf("%v: got %d arguments but %d type parameters", pos, ntargs, ntparams)) 163 } 164 return true 165 } 166 167 func (check *Checker) verify(pos token.Pos, tparams []*TypeParam, targs []Type, ctxt *Context) (int, error) { 168 smap := makeSubstMap(tparams, targs) 169 for i, tpar := range tparams { 170 // Ensure that we have a (possibly implicit) interface as type bound (issue #51048). 171 tpar.iface() 172 // The type parameter bound is parameterized with the same type parameters 173 // as the instantiated type; before we can use it for bounds checking we 174 // need to instantiate it with the type arguments with which we instantiated 175 // the parameterized type. 176 bound := check.subst(pos, tpar.bound, smap, nil, ctxt) 177 if err := check.implements(targs[i], bound); err != nil { 178 return i, err 179 } 180 } 181 return -1, nil 182 } 183 184 // implements checks if V implements T and reports an error if it doesn't. 185 // The receiver may be nil if implements is called through an exported 186 // API call such as AssignableTo. 187 func (check *Checker) implements(V, T Type) error { 188 Vu := under(V) 189 Tu := under(T) 190 if Vu == Typ[Invalid] || Tu == Typ[Invalid] { 191 return nil // avoid follow-on errors 192 } 193 if p, _ := Vu.(*Pointer); p != nil && under(p.base) == Typ[Invalid] { 194 return nil // avoid follow-on errors (see issue #49541 for an example) 195 } 196 197 errorf := func(format string, args ...any) error { 198 return errors.New(check.sprintf(format, args...)) 199 } 200 201 Ti, _ := Tu.(*Interface) 202 if Ti == nil { 203 var cause string 204 if isInterfacePtr(Tu) { 205 cause = check.sprintf("type %s is pointer to interface, not interface", T) 206 } else { 207 cause = check.sprintf("%s is not an interface", T) 208 } 209 return errorf("%s does not implement %s (%s)", V, T, cause) 210 } 211 212 // Every type satisfies the empty interface. 213 if Ti.Empty() { 214 return nil 215 } 216 // T is not the empty interface (i.e., the type set of T is restricted) 217 218 // An interface V with an empty type set satisfies any interface. 219 // (The empty set is a subset of any set.) 220 Vi, _ := Vu.(*Interface) 221 if Vi != nil && Vi.typeSet().IsEmpty() { 222 return nil 223 } 224 // type set of V is not empty 225 226 // No type with non-empty type set satisfies the empty type set. 227 if Ti.typeSet().IsEmpty() { 228 return errorf("cannot implement %s (empty type set)", T) 229 } 230 231 // V must implement T's methods, if any. 232 if m, wrong := check.missingMethod(V, Ti, true); m != nil /* !Implements(V, Ti) */ { 233 return errorf("%s does not implement %s %s", V, T, check.missingMethodReason(V, T, m, wrong)) 234 } 235 236 // If T is comparable, V must be comparable. 237 // Remember as a pending error and report only if we don't have a more specific error. 238 var pending error 239 if Ti.IsComparable() && !comparable(V, false, nil, nil) { 240 pending = errorf("%s does not implement comparable", V) 241 } 242 243 // V must also be in the set of types of T, if any. 244 // Constraints with empty type sets were already excluded above. 245 if !Ti.typeSet().hasTerms() { 246 return pending // nothing to do 247 } 248 249 // If V is itself an interface, each of its possible types must be in the set 250 // of T types (i.e., the V type set must be a subset of the T type set). 251 // Interfaces V with empty type sets were already excluded above. 252 if Vi != nil { 253 if !Vi.typeSet().subsetOf(Ti.typeSet()) { 254 // TODO(gri) report which type is missing 255 return errorf("%s does not implement %s", V, T) 256 } 257 return pending 258 } 259 260 // Otherwise, V's type must be included in the iface type set. 261 var alt Type 262 if Ti.typeSet().is(func(t *term) bool { 263 if !t.includes(V) { 264 // If V ∉ t.typ but V ∈ ~t.typ then remember this type 265 // so we can suggest it as an alternative in the error 266 // message. 267 if alt == nil && !t.tilde && Identical(t.typ, under(t.typ)) { 268 tt := *t 269 tt.tilde = true 270 if tt.includes(V) { 271 alt = t.typ 272 } 273 } 274 return true 275 } 276 return false 277 }) { 278 if alt != nil { 279 return errorf("%s does not implement %s (possibly missing ~ for %s in constraint %s)", V, T, alt, T) 280 } else { 281 return errorf("%s does not implement %s (%s missing in %s)", V, T, V, Ti.typeSet().terms) 282 } 283 } 284 285 return pending 286 } 287