Source file src/go/types/named.go
1 // Copyright 2011 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 package types 6 7 import ( 8 "go/token" 9 "sync" 10 ) 11 12 // A Named represents a named (defined) type. 13 type Named struct { 14 check *Checker 15 obj *TypeName // corresponding declared object for declared types; placeholder for instantiated types 16 orig *Named // original, uninstantiated type 17 fromRHS Type // type (on RHS of declaration) this *Named type is derived of (for cycle reporting) 18 underlying Type // possibly a *Named during setup; never a *Named once set up completely 19 tparams *TypeParamList // type parameters, or nil 20 targs *TypeList // type arguments (after instantiation), or nil 21 22 // methods declared for this type (not the method set of this type). 23 // Signatures are type-checked lazily. 24 // For non-instantiated types, this is a fully populated list of methods. For 25 // instantiated types, this is a 'lazy' list, and methods are instantiated 26 // when they are first accessed. 27 methods *methodList 28 29 // resolver may be provided to lazily resolve type parameters, underlying, and methods. 30 resolver func(*Context, *Named) (tparams *TypeParamList, underlying Type, methods *methodList) 31 once sync.Once // ensures that tparams, underlying, and methods are resolved before accessing 32 } 33 34 // NewNamed returns a new named type for the given type name, underlying type, and associated methods. 35 // If the given type name obj doesn't have a type yet, its type is set to the returned named type. 36 // The underlying type must not be a *Named. 37 func NewNamed(obj *TypeName, underlying Type, methods []*Func) *Named { 38 if _, ok := underlying.(*Named); ok { 39 panic("underlying type must not be *Named") 40 } 41 return (*Checker)(nil).newNamed(obj, nil, underlying, nil, newMethodList(methods)) 42 } 43 44 func (t *Named) resolve(ctxt *Context) *Named { 45 if t.resolver == nil { 46 return t 47 } 48 49 t.once.Do(func() { 50 // TODO(mdempsky): Since we're passing t to the resolver anyway 51 // (necessary because types2 expects the receiver type for methods 52 // on defined interface types to be the Named rather than the 53 // underlying Interface), maybe it should just handle calling 54 // SetTypeParams, SetUnderlying, and AddMethod instead? Those 55 // methods would need to support reentrant calls though. It would 56 // also make the API more future-proof towards further extensions 57 // (like SetTypeParams). 58 t.tparams, t.underlying, t.methods = t.resolver(ctxt, t) 59 t.fromRHS = t.underlying // for cycle detection 60 }) 61 return t 62 } 63 64 // newNamed is like NewNamed but with a *Checker receiver and additional orig argument. 65 func (check *Checker) newNamed(obj *TypeName, orig *Named, underlying Type, tparams *TypeParamList, methods *methodList) *Named { 66 typ := &Named{check: check, obj: obj, orig: orig, fromRHS: underlying, underlying: underlying, tparams: tparams, methods: methods} 67 if typ.orig == nil { 68 typ.orig = typ 69 } 70 if obj.typ == nil { 71 obj.typ = typ 72 } 73 // Ensure that typ is always expanded and sanity-checked. 74 if check != nil { 75 check.needsCleanup(typ) 76 } 77 return typ 78 } 79 80 func (t *Named) cleanup() { 81 // Ensure that every defined type created in the course of type-checking has 82 // either non-*Named underlying, or is unresolved. 83 // 84 // This guarantees that we don't leak any types whose underlying is *Named, 85 // because any unresolved instances will lazily compute their underlying by 86 // substituting in the underlying of their origin. The origin must have 87 // either been imported or type-checked and expanded here, and in either case 88 // its underlying will be fully expanded. 89 switch t.underlying.(type) { 90 case nil: 91 if t.resolver == nil { 92 panic("nil underlying") 93 } 94 case *Named: 95 t.under() // t.under may add entries to check.cleaners 96 } 97 t.check = nil 98 } 99 100 // Obj returns the type name for the declaration defining the named type t. For 101 // instantiated types, this is same as the type name of the origin type. 102 func (t *Named) Obj() *TypeName { 103 return t.orig.obj // for non-instances this is the same as t.obj 104 } 105 106 // Origin returns the generic type from which the named type t is 107 // instantiated. If t is not an instantiated type, the result is t. 108 func (t *Named) Origin() *Named { return t.orig } 109 110 // TODO(gri) Come up with a better representation and API to distinguish 111 // between parameterized instantiated and non-instantiated types. 112 113 // TypeParams returns the type parameters of the named type t, or nil. 114 // The result is non-nil for an (originally) generic type even if it is instantiated. 115 func (t *Named) TypeParams() *TypeParamList { return t.resolve(nil).tparams } 116 117 // SetTypeParams sets the type parameters of the named type t. 118 // t must not have type arguments. 119 func (t *Named) SetTypeParams(tparams []*TypeParam) { 120 assert(t.targs.Len() == 0) 121 t.resolve(nil).tparams = bindTParams(tparams) 122 } 123 124 // TypeArgs returns the type arguments used to instantiate the named type t. 125 func (t *Named) TypeArgs() *TypeList { return t.targs } 126 127 // NumMethods returns the number of explicit methods defined for t. 128 // 129 // For an ordinary or instantiated type t, the receiver base type of these 130 // methods will be the named type t. For an uninstantiated generic type t, each 131 // method receiver will be instantiated with its receiver type parameters. 132 func (t *Named) NumMethods() int { return t.resolve(nil).methods.Len() } 133 134 // Method returns the i'th method of named type t for 0 <= i < t.NumMethods(). 135 func (t *Named) Method(i int) *Func { 136 t.resolve(nil) 137 return t.methods.At(i, func() *Func { 138 return t.instantiateMethod(i) 139 }) 140 } 141 142 // instiateMethod instantiates the i'th method for an instantiated receiver. 143 func (t *Named) instantiateMethod(i int) *Func { 144 assert(t.TypeArgs().Len() > 0) // t must be an instance 145 146 // t.orig.methods is not lazy. origm is the method instantiated with its 147 // receiver type parameters (the "origin" method). 148 origm := t.orig.Method(i) 149 assert(origm != nil) 150 151 check := t.check 152 // Ensure that the original method is type-checked. 153 if check != nil { 154 check.objDecl(origm, nil) 155 } 156 157 origSig := origm.typ.(*Signature) 158 rbase, _ := deref(origSig.Recv().Type()) 159 160 // If rbase is t, then origm is already the instantiated method we're looking 161 // for. In this case, we return origm to preserve the invariant that 162 // traversing Method->Receiver Type->Method should get back to the same 163 // method. 164 // 165 // This occurs if t is instantiated with the receiver type parameters, as in 166 // the use of m in func (r T[_]) m() { r.m() }. 167 if rbase == t { 168 return origm 169 } 170 171 sig := origSig 172 // We can only substitute if we have a correspondence between type arguments 173 // and type parameters. This check is necessary in the presence of invalid 174 // code. 175 if origSig.RecvTypeParams().Len() == t.targs.Len() { 176 ctxt := check.bestContext(nil) 177 smap := makeSubstMap(origSig.RecvTypeParams().list(), t.targs.list()) 178 sig = check.subst(origm.pos, origSig, smap, ctxt).(*Signature) 179 } 180 181 if sig == origSig { 182 // No substitution occurred, but we still need to create a new signature to 183 // hold the instantiated receiver. 184 copy := *origSig 185 sig = © 186 } 187 188 var rtyp Type 189 if origm.hasPtrRecv() { 190 rtyp = NewPointer(t) 191 } else { 192 rtyp = t 193 } 194 195 sig.recv = substVar(origSig.recv, rtyp) 196 return NewFunc(origm.pos, origm.pkg, origm.name, sig) 197 } 198 199 // SetUnderlying sets the underlying type and marks t as complete. 200 // t must not have type arguments. 201 func (t *Named) SetUnderlying(underlying Type) { 202 assert(t.targs.Len() == 0) 203 if underlying == nil { 204 panic("underlying type must not be nil") 205 } 206 if _, ok := underlying.(*Named); ok { 207 panic("underlying type must not be *Named") 208 } 209 t.resolve(nil).underlying = underlying 210 if t.fromRHS == nil { 211 t.fromRHS = underlying // for cycle detection 212 } 213 } 214 215 // AddMethod adds method m unless it is already in the method list. 216 // t must not have type arguments. 217 func (t *Named) AddMethod(m *Func) { 218 assert(t.targs.Len() == 0) 219 t.resolve(nil) 220 if t.methods == nil { 221 t.methods = newMethodList(nil) 222 } 223 t.methods.Add(m) 224 } 225 226 func (t *Named) Underlying() Type { return t.resolve(nil).underlying } 227 func (t *Named) String() string { return TypeString(t, nil) } 228 229 // ---------------------------------------------------------------------------- 230 // Implementation 231 232 // under returns the expanded underlying type of n0; possibly by following 233 // forward chains of named types. If an underlying type is found, resolve 234 // the chain by setting the underlying type for each defined type in the 235 // chain before returning it. If no underlying type is found or a cycle 236 // is detected, the result is Typ[Invalid]. If a cycle is detected and 237 // n0.check != nil, the cycle is reported. 238 // 239 // This is necessary because the underlying type of named may be itself a 240 // named type that is incomplete: 241 // 242 // type ( 243 // A B 244 // B *C 245 // C A 246 // ) 247 // 248 // The type of C is the (named) type of A which is incomplete, 249 // and which has as its underlying type the named type B. 250 func (n0 *Named) under() Type { 251 u := n0.Underlying() 252 253 // If the underlying type of a defined type is not a defined 254 // (incl. instance) type, then that is the desired underlying 255 // type. 256 var n1 *Named 257 switch u1 := u.(type) { 258 case nil: 259 // After expansion via Underlying(), we should never encounter a nil 260 // underlying. 261 panic("nil underlying") 262 default: 263 // common case 264 return u 265 case *Named: 266 // handled below 267 n1 = u1 268 } 269 270 if n0.check == nil { 271 panic("Named.check == nil but type is incomplete") 272 } 273 274 // Invariant: after this point n0 as well as any named types in its 275 // underlying chain should be set up when this function exits. 276 check := n0.check 277 n := n0 278 279 seen := make(map[*Named]int) // types that need their underlying resolved 280 var path []Object // objects encountered, for cycle reporting 281 282 loop: 283 for { 284 seen[n] = len(seen) 285 path = append(path, n.obj) 286 n = n1 287 if i, ok := seen[n]; ok { 288 // cycle 289 check.cycleError(path[i:]) 290 u = Typ[Invalid] 291 break 292 } 293 u = n.Underlying() 294 switch u1 := u.(type) { 295 case nil: 296 u = Typ[Invalid] 297 break loop 298 default: 299 break loop 300 case *Named: 301 // Continue collecting *Named types in the chain. 302 n1 = u1 303 } 304 } 305 306 for n := range seen { 307 // We should never have to update the underlying type of an imported type; 308 // those underlying types should have been resolved during the import. 309 // Also, doing so would lead to a race condition (was issue #31749). 310 // Do this check always, not just in debug mode (it's cheap). 311 if n.obj.pkg != check.pkg { 312 panic("imported type with unresolved underlying type") 313 } 314 n.underlying = u 315 } 316 317 return u 318 } 319 320 func (n *Named) setUnderlying(typ Type) { 321 if n != nil { 322 n.underlying = typ 323 } 324 } 325 326 func (n *Named) lookupMethod(pkg *Package, name string, foldCase bool) (int, *Func) { 327 n.resolve(nil) 328 // If n is an instance, we may not have yet instantiated all of its methods. 329 // Look up the method index in orig, and only instantiate method at the 330 // matching index (if any). 331 i, _ := n.orig.methods.Lookup(pkg, name, foldCase) 332 if i < 0 { 333 return -1, nil 334 } 335 // For instances, m.Method(i) will be different from the orig method. 336 return i, n.Method(i) 337 } 338 339 // bestContext returns the best available context. In order of preference: 340 // - the given ctxt, if non-nil 341 // - check.ctxt, if check is non-nil 342 // - a new Context 343 func (check *Checker) bestContext(ctxt *Context) *Context { 344 if ctxt != nil { 345 return ctxt 346 } 347 if check != nil { 348 if check.ctxt == nil { 349 check.ctxt = NewContext() 350 } 351 return check.ctxt 352 } 353 return NewContext() 354 } 355 356 // expandNamed ensures that the underlying type of n is instantiated. 357 // The underlying type will be Typ[Invalid] if there was an error. 358 func expandNamed(ctxt *Context, n *Named, instPos token.Pos) (tparams *TypeParamList, underlying Type, methods *methodList) { 359 n.orig.resolve(ctxt) 360 assert(n.orig.underlying != nil) 361 362 check := n.check 363 364 if _, unexpanded := n.orig.underlying.(*Named); unexpanded { 365 // We should only get an unexpanded underlying here during type checking 366 // (for example, in recursive type declarations). 367 assert(check != nil) 368 } 369 370 // Mismatching arg and tparam length may be checked elsewhere. 371 if n.orig.tparams.Len() == n.targs.Len() { 372 // We must always have a context, to avoid infinite recursion. 373 ctxt = check.bestContext(ctxt) 374 h := ctxt.instanceHash(n.orig, n.targs.list()) 375 // ensure that an instance is recorded for h to avoid infinite recursion. 376 ctxt.update(h, n.orig, n.TypeArgs().list(), n) 377 378 smap := makeSubstMap(n.orig.tparams.list(), n.targs.list()) 379 underlying = n.check.subst(instPos, n.orig.underlying, smap, ctxt) 380 // If the underlying of n is an interface, we need to set the receiver of 381 // its methods accurately -- we set the receiver of interface methods on 382 // the RHS of a type declaration to the defined type. 383 if iface, _ := underlying.(*Interface); iface != nil { 384 if methods, copied := replaceRecvType(iface.methods, n.orig, n); copied { 385 // If the underlying doesn't actually use type parameters, it's possible 386 // that it wasn't substituted. In this case we need to create a new 387 // *Interface before modifying receivers. 388 if iface == n.orig.underlying { 389 old := iface 390 iface = check.newInterface() 391 iface.embeddeds = old.embeddeds 392 iface.complete = old.complete 393 iface.implicit = old.implicit // should be false but be conservative 394 underlying = iface 395 } 396 iface.methods = methods 397 } 398 } 399 } else { 400 underlying = Typ[Invalid] 401 } 402 403 return n.orig.tparams, underlying, newLazyMethodList(n.orig.methods.Len()) 404 } 405 406 // safeUnderlying returns the underlying of typ without expanding instances, to 407 // avoid infinite recursion. 408 // 409 // TODO(rfindley): eliminate this function or give it a better name. 410 func safeUnderlying(typ Type) Type { 411 if t, _ := typ.(*Named); t != nil { 412 return t.underlying 413 } 414 return typ.Underlying() 415 } 416