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 "sync/atomic" 11 ) 12 13 // Type-checking Named types is subtle, because they may be recursively 14 // defined, and because their full details may be spread across multiple 15 // declarations (via methods). For this reason they are type-checked lazily, 16 // to avoid information being accessed before it is complete. 17 // 18 // Conceptually, it is helpful to think of named types as having two distinct 19 // sets of information: 20 // - "LHS" information, defining their identity: Obj() and TypeArgs() 21 // - "RHS" information, defining their details: TypeParams(), Underlying(), 22 // and methods. 23 // 24 // In this taxonomy, LHS information is available immediately, but RHS 25 // information is lazy. Specifically, a named type N may be constructed in any 26 // of the following ways: 27 // 1. type-checked from the source 28 // 2. loaded eagerly from export data 29 // 3. loaded lazily from export data (when using unified IR) 30 // 4. instantiated from a generic type 31 // 32 // In cases 1, 3, and 4, it is possible that the underlying type or methods of 33 // N may not be immediately available. 34 // - During type-checking, we allocate N before type-checking its underlying 35 // type or methods, so that we may resolve recursive references. 36 // - When loading from export data, we may load its methods and underlying 37 // type lazily using a provided load function. 38 // - After instantiating, we lazily expand the underlying type and methods 39 // (note that instances may be created while still in the process of 40 // type-checking the original type declaration). 41 // 42 // In cases 3 and 4 this lazy construction may also occur concurrently, due to 43 // concurrent use of the type checker API (after type checking or importing has 44 // finished). It is critical that we keep track of state, so that Named types 45 // are constructed exactly once and so that we do not access their details too 46 // soon. 47 // 48 // We achieve this by tracking state with an atomic state variable, and 49 // guarding potentially concurrent calculations with a mutex. At any point in 50 // time this state variable determines which data on N may be accessed. As 51 // state monotonically progresses, any data available at state M may be 52 // accessed without acquiring the mutex at state N, provided N >= M. 53 // 54 // GLOSSARY: Here are a few terms used in this file to describe Named types: 55 // - We say that a Named type is "instantiated" if it has been constructed by 56 // instantiating a generic named type with type arguments. 57 // - We say that a Named type is "declared" if it corresponds to a type 58 // declaration in the source. Instantiated named types correspond to a type 59 // instantiation in the source, not a declaration. But their Origin type is 60 // a declared type. 61 // - We say that a Named type is "resolved" if its RHS information has been 62 // loaded or fully type-checked. For Named types constructed from export 63 // data, this may involve invoking a loader function to extract information 64 // from export data. For instantiated named types this involves reading 65 // information from their origin. 66 // - We say that a Named type is "expanded" if it is an instantiated type and 67 // type parameters in its underlying type and methods have been substituted 68 // with the type arguments from the instantiation. A type may be partially 69 // expanded if some but not all of these details have been substituted. 70 // Similarly, we refer to these individual details (underlying type or 71 // method) as being "expanded". 72 // - When all information is known for a named type, we say it is "complete". 73 // 74 // Some invariants to keep in mind: each declared Named type has a single 75 // corresponding object, and that object's type is the (possibly generic) Named 76 // type. Declared Named types are identical if and only if their pointers are 77 // identical. On the other hand, multiple instantiated Named types may be 78 // identical even though their pointers are not identical. One has to use 79 // Identical to compare them. For instantiated named types, their obj is a 80 // synthetic placeholder that records their position of the corresponding 81 // instantiation in the source (if they were constructed during type checking). 82 // 83 // To prevent infinite expansion of named instances that are created outside of 84 // type-checking, instances share a Context with other instances created during 85 // their expansion. Via the pidgeonhole principle, this guarantees that in the 86 // presence of a cycle of named types, expansion will eventually find an 87 // existing instance in the Context and short-circuit the expansion. 88 // 89 // Once an instance is complete, we can nil out this shared Context to unpin 90 // memory, though this Context may still be held by other incomplete instances 91 // in its "lineage". 92 93 // A Named represents a named (defined) type. 94 type Named struct { 95 check *Checker // non-nil during type-checking; nil otherwise 96 obj *TypeName // corresponding declared object for declared types; see above for instantiated types 97 98 // fromRHS holds the type (on RHS of declaration) this *Named type is derived 99 // from (for cycle reporting). Only used by validType, and therefore does not 100 // require synchronization. 101 fromRHS Type 102 103 // information for instantiated types; nil otherwise 104 inst *instance 105 106 mu sync.Mutex // guards all fields below 107 state_ uint32 // the current state of this type; must only be accessed atomically 108 underlying Type // possibly a *Named during setup; never a *Named once set up completely 109 tparams *TypeParamList // type parameters, or nil 110 111 // methods declared for this type (not the method set of this type) 112 // Signatures are type-checked lazily. 113 // For non-instantiated types, this is a fully populated list of methods. For 114 // instantiated types, methods are individually expanded when they are first 115 // accessed. 116 methods []*Func 117 118 // loader may be provided to lazily load type parameters, underlying type, and methods. 119 loader func(*Named) (tparams []*TypeParam, underlying Type, methods []*Func) 120 } 121 122 // instance holds information that is only necessary for instantiated named 123 // types. 124 type instance struct { 125 orig *Named // original, uninstantiated type 126 targs *TypeList // type arguments 127 expandedMethods int // number of expanded methods; expandedMethods <= len(orig.methods) 128 ctxt *Context // local Context; set to nil after full expansion 129 } 130 131 // namedState represents the possible states that a named type may assume. 132 type namedState uint32 133 134 const ( 135 unresolved namedState = iota // tparams, underlying type and methods might be unavailable 136 resolved // resolve has run; methods might be incomplete (for instances) 137 complete // all data is known 138 ) 139 140 // NewNamed returns a new named type for the given type name, underlying type, and associated methods. 141 // If the given type name obj doesn't have a type yet, its type is set to the returned named type. 142 // The underlying type must not be a *Named. 143 func NewNamed(obj *TypeName, underlying Type, methods []*Func) *Named { 144 if _, ok := underlying.(*Named); ok { 145 panic("underlying type must not be *Named") 146 } 147 return (*Checker)(nil).newNamed(obj, underlying, methods) 148 } 149 150 // resolve resolves the type parameters, methods, and underlying type of n. 151 // This information may be loaded from a provided loader function, or computed 152 // from an origin type (in the case of instances). 153 // 154 // After resolution, the type parameters, methods, and underlying type of n are 155 // accessible; but if n is an instantiated type, its methods may still be 156 // unexpanded. 157 func (n *Named) resolve() *Named { 158 if n.state() >= resolved { // avoid locking below 159 return n 160 } 161 162 // TODO(rfindley): if n.check is non-nil we can avoid locking here, since 163 // type-checking is not concurrent. Evaluate if this is worth doing. 164 n.mu.Lock() 165 defer n.mu.Unlock() 166 167 if n.state() >= resolved { 168 return n 169 } 170 171 if n.inst != nil { 172 assert(n.underlying == nil) // n is an unresolved instance 173 assert(n.loader == nil) // instances are created by instantiation, in which case n.loader is nil 174 175 orig := n.inst.orig 176 orig.resolve() 177 underlying := n.expandUnderlying() 178 179 n.tparams = orig.tparams 180 n.underlying = underlying 181 n.fromRHS = orig.fromRHS // for cycle detection 182 183 if len(orig.methods) == 0 { 184 n.setState(complete) // nothing further to do 185 n.inst.ctxt = nil 186 } else { 187 n.setState(resolved) 188 } 189 return n 190 } 191 192 // TODO(mdempsky): Since we're passing n to the loader anyway 193 // (necessary because types2 expects the receiver type for methods 194 // on defined interface types to be the Named rather than the 195 // underlying Interface), maybe it should just handle calling 196 // SetTypeParams, SetUnderlying, and AddMethod instead? Those 197 // methods would need to support reentrant calls though. It would 198 // also make the API more future-proof towards further extensions. 199 if n.loader != nil { 200 assert(n.underlying == nil) 201 assert(n.TypeArgs().Len() == 0) // instances are created by instantiation, in which case n.loader is nil 202 203 tparams, underlying, methods := n.loader(n) 204 205 n.tparams = bindTParams(tparams) 206 n.underlying = underlying 207 n.fromRHS = underlying // for cycle detection 208 n.methods = methods 209 n.loader = nil 210 } 211 212 n.setState(complete) 213 return n 214 } 215 216 // state atomically accesses the current state of the receiver. 217 func (n *Named) state() namedState { 218 return namedState(atomic.LoadUint32(&n.state_)) 219 } 220 221 // setState atomically stores the given state for n. 222 // Must only be called while holding n.mu. 223 func (n *Named) setState(state namedState) { 224 atomic.StoreUint32(&n.state_, uint32(state)) 225 } 226 227 // newNamed is like NewNamed but with a *Checker receiver and additional orig argument. 228 func (check *Checker) newNamed(obj *TypeName, underlying Type, methods []*Func) *Named { 229 typ := &Named{check: check, obj: obj, fromRHS: underlying, underlying: underlying, methods: methods} 230 if obj.typ == nil { 231 obj.typ = typ 232 } 233 // Ensure that typ is always sanity-checked. 234 if check != nil { 235 check.needsCleanup(typ) 236 } 237 return typ 238 } 239 240 // newNamedInstance creates a new named instance for the given origin and type 241 // arguments, recording pos as the position of its synthetic object (for error 242 // reporting). 243 // 244 // If set, expanding is the named type instance currently being expanded, that 245 // led to the creation of this instance. 246 func (check *Checker) newNamedInstance(pos token.Pos, orig *Named, targs []Type, expanding *Named) *Named { 247 assert(len(targs) > 0) 248 249 obj := NewTypeName(pos, orig.obj.pkg, orig.obj.name, nil) 250 inst := &instance{orig: orig, targs: newTypeList(targs)} 251 252 // Only pass the expanding context to the new instance if their packages 253 // match. Since type reference cycles are only possible within a single 254 // package, this is sufficient for the purposes of short-circuiting cycles. 255 // Avoiding passing the context in other cases prevents unnecessary coupling 256 // of types across packages. 257 if expanding != nil && expanding.Obj().pkg == obj.pkg { 258 inst.ctxt = expanding.inst.ctxt 259 } 260 typ := &Named{check: check, obj: obj, inst: inst} 261 obj.typ = typ 262 // Ensure that typ is always sanity-checked. 263 if check != nil { 264 check.needsCleanup(typ) 265 } 266 return typ 267 } 268 269 func (t *Named) cleanup() { 270 assert(t.inst == nil || t.inst.orig.inst == nil) 271 // Ensure that every defined type created in the course of type-checking has 272 // either non-*Named underlying type, or is unexpanded. 273 // 274 // This guarantees that we don't leak any types whose underlying type is 275 // *Named, because any unexpanded instances will lazily compute their 276 // underlying type by substituting in the underlying type of their origin. 277 // The origin must have either been imported or type-checked and expanded 278 // here, and in either case its underlying type will be fully expanded. 279 switch t.underlying.(type) { 280 case nil: 281 if t.TypeArgs().Len() == 0 { 282 panic("nil underlying") 283 } 284 case *Named: 285 t.under() // t.under may add entries to check.cleaners 286 } 287 t.check = nil 288 } 289 290 // Obj returns the type name for the declaration defining the named type t. For 291 // instantiated types, this is same as the type name of the origin type. 292 func (t *Named) Obj() *TypeName { 293 if t.inst == nil { 294 return t.obj 295 } 296 return t.inst.orig.obj 297 } 298 299 // Origin returns the generic type from which the named type t is 300 // instantiated. If t is not an instantiated type, the result is t. 301 func (t *Named) Origin() *Named { 302 if t.inst == nil { 303 return t 304 } 305 return t.inst.orig 306 } 307 308 // TypeParams returns the type parameters of the named type t, or nil. 309 // The result is non-nil for an (originally) generic type even if it is instantiated. 310 func (t *Named) TypeParams() *TypeParamList { return t.resolve().tparams } 311 312 // SetTypeParams sets the type parameters of the named type t. 313 // t must not have type arguments. 314 func (t *Named) SetTypeParams(tparams []*TypeParam) { 315 assert(t.inst == nil) 316 t.resolve().tparams = bindTParams(tparams) 317 } 318 319 // TypeArgs returns the type arguments used to instantiate the named type t. 320 func (t *Named) TypeArgs() *TypeList { 321 if t.inst == nil { 322 return nil 323 } 324 return t.inst.targs 325 } 326 327 // NumMethods returns the number of explicit methods defined for t. 328 func (t *Named) NumMethods() int { 329 return len(t.Origin().resolve().methods) 330 } 331 332 // Method returns the i'th method of named type t for 0 <= i < t.NumMethods(). 333 // 334 // For an ordinary or instantiated type t, the receiver base type of this 335 // method is the named type t. For an uninstantiated generic type t, each 336 // method receiver is instantiated with its receiver type parameters. 337 func (t *Named) Method(i int) *Func { 338 t.resolve() 339 340 if t.state() >= complete { 341 return t.methods[i] 342 } 343 344 assert(t.inst != nil) // only instances should have incomplete methods 345 orig := t.inst.orig 346 347 t.mu.Lock() 348 defer t.mu.Unlock() 349 350 if len(t.methods) != len(orig.methods) { 351 assert(len(t.methods) == 0) 352 t.methods = make([]*Func, len(orig.methods)) 353 } 354 355 if t.methods[i] == nil { 356 assert(t.inst.ctxt != nil) // we should still have a context remaining from the resolution phase 357 t.methods[i] = t.expandMethod(i) 358 t.inst.expandedMethods++ 359 360 // Check if we've created all methods at this point. If we have, mark the 361 // type as fully expanded. 362 if t.inst.expandedMethods == len(orig.methods) { 363 t.setState(complete) 364 t.inst.ctxt = nil // no need for a context anymore 365 } 366 } 367 368 return t.methods[i] 369 } 370 371 // expandMethod substitutes type arguments in the i'th method for an 372 // instantiated receiver. 373 func (t *Named) expandMethod(i int) *Func { 374 // t.orig.methods is not lazy. origm is the method instantiated with its 375 // receiver type parameters (the "origin" method). 376 origm := t.inst.orig.Method(i) 377 assert(origm != nil) 378 379 check := t.check 380 // Ensure that the original method is type-checked. 381 if check != nil { 382 check.objDecl(origm, nil) 383 } 384 385 origSig := origm.typ.(*Signature) 386 rbase, _ := deref(origSig.Recv().Type()) 387 388 // If rbase is t, then origm is already the instantiated method we're looking 389 // for. In this case, we return origm to preserve the invariant that 390 // traversing Method->Receiver Type->Method should get back to the same 391 // method. 392 // 393 // This occurs if t is instantiated with the receiver type parameters, as in 394 // the use of m in func (r T[_]) m() { r.m() }. 395 if rbase == t { 396 return origm 397 } 398 399 sig := origSig 400 // We can only substitute if we have a correspondence between type arguments 401 // and type parameters. This check is necessary in the presence of invalid 402 // code. 403 if origSig.RecvTypeParams().Len() == t.inst.targs.Len() { 404 smap := makeSubstMap(origSig.RecvTypeParams().list(), t.inst.targs.list()) 405 var ctxt *Context 406 if check != nil { 407 ctxt = check.context() 408 } 409 sig = check.subst(origm.pos, origSig, smap, t, ctxt).(*Signature) 410 } 411 412 if sig == origSig { 413 // No substitution occurred, but we still need to create a new signature to 414 // hold the instantiated receiver. 415 copy := *origSig 416 sig = © 417 } 418 419 var rtyp Type 420 if origm.hasPtrRecv() { 421 rtyp = NewPointer(t) 422 } else { 423 rtyp = t 424 } 425 426 sig.recv = substVar(origSig.recv, rtyp) 427 return substFunc(origm, sig) 428 } 429 430 // SetUnderlying sets the underlying type and marks t as complete. 431 // t must not have type arguments. 432 func (t *Named) SetUnderlying(underlying Type) { 433 assert(t.inst == nil) 434 if underlying == nil { 435 panic("underlying type must not be nil") 436 } 437 if _, ok := underlying.(*Named); ok { 438 panic("underlying type must not be *Named") 439 } 440 t.resolve().underlying = underlying 441 if t.fromRHS == nil { 442 t.fromRHS = underlying // for cycle detection 443 } 444 } 445 446 // AddMethod adds method m unless it is already in the method list. 447 // t must not have type arguments. 448 func (t *Named) AddMethod(m *Func) { 449 assert(t.inst == nil) 450 t.resolve() 451 if i, _ := lookupMethod(t.methods, m.pkg, m.name, false); i < 0 { 452 t.methods = append(t.methods, m) 453 } 454 } 455 456 func (t *Named) Underlying() Type { return t.resolve().underlying } 457 func (t *Named) String() string { return TypeString(t, nil) } 458 459 // ---------------------------------------------------------------------------- 460 // Implementation 461 // 462 // TODO(rfindley): reorganize the loading and expansion methods under this 463 // heading. 464 465 // under returns the expanded underlying type of n0; possibly by following 466 // forward chains of named types. If an underlying type is found, resolve 467 // the chain by setting the underlying type for each defined type in the 468 // chain before returning it. If no underlying type is found or a cycle 469 // is detected, the result is Typ[Invalid]. If a cycle is detected and 470 // n0.check != nil, the cycle is reported. 471 // 472 // This is necessary because the underlying type of named may be itself a 473 // named type that is incomplete: 474 // 475 // type ( 476 // A B 477 // B *C 478 // C A 479 // ) 480 // 481 // The type of C is the (named) type of A which is incomplete, 482 // and which has as its underlying type the named type B. 483 func (n0 *Named) under() Type { 484 u := n0.Underlying() 485 486 // If the underlying type of a defined type is not a defined 487 // (incl. instance) type, then that is the desired underlying 488 // type. 489 var n1 *Named 490 switch u1 := u.(type) { 491 case nil: 492 // After expansion via Underlying(), we should never encounter a nil 493 // underlying. 494 panic("nil underlying") 495 default: 496 // common case 497 return u 498 case *Named: 499 // handled below 500 n1 = u1 501 } 502 503 if n0.check == nil { 504 panic("Named.check == nil but type is incomplete") 505 } 506 507 // Invariant: after this point n0 as well as any named types in its 508 // underlying chain should be set up when this function exits. 509 check := n0.check 510 n := n0 511 512 seen := make(map[*Named]int) // types that need their underlying type resolved 513 var path []Object // objects encountered, for cycle reporting 514 515 loop: 516 for { 517 seen[n] = len(seen) 518 path = append(path, n.obj) 519 n = n1 520 if i, ok := seen[n]; ok { 521 // cycle 522 check.cycleError(path[i:]) 523 u = Typ[Invalid] 524 break 525 } 526 u = n.Underlying() 527 switch u1 := u.(type) { 528 case nil: 529 u = Typ[Invalid] 530 break loop 531 default: 532 break loop 533 case *Named: 534 // Continue collecting *Named types in the chain. 535 n1 = u1 536 } 537 } 538 539 for n := range seen { 540 // We should never have to update the underlying type of an imported type; 541 // those underlying types should have been resolved during the import. 542 // Also, doing so would lead to a race condition (was issue #31749). 543 // Do this check always, not just in debug mode (it's cheap). 544 if n.obj.pkg != check.pkg { 545 panic("imported type with unresolved underlying type") 546 } 547 n.underlying = u 548 } 549 550 return u 551 } 552 553 func (n *Named) setUnderlying(typ Type) { 554 if n != nil { 555 n.underlying = typ 556 } 557 } 558 559 func (n *Named) lookupMethod(pkg *Package, name string, foldCase bool) (int, *Func) { 560 n.resolve() 561 // If n is an instance, we may not have yet instantiated all of its methods. 562 // Look up the method index in orig, and only instantiate method at the 563 // matching index (if any). 564 i, _ := lookupMethod(n.Origin().methods, pkg, name, foldCase) 565 if i < 0 { 566 return -1, nil 567 } 568 // For instances, m.Method(i) will be different from the orig method. 569 return i, n.Method(i) 570 } 571 572 // context returns the type-checker context. 573 func (check *Checker) context() *Context { 574 if check.ctxt == nil { 575 check.ctxt = NewContext() 576 } 577 return check.ctxt 578 } 579 580 // expandUnderlying substitutes type arguments in the underlying type n.orig, 581 // returning the result. Returns Typ[Invalid] if there was an error. 582 func (n *Named) expandUnderlying() Type { 583 check := n.check 584 if check != nil && trace { 585 check.trace(n.obj.pos, "-- Named.expandUnderlying %s", n) 586 check.indent++ 587 defer func() { 588 check.indent-- 589 check.trace(n.obj.pos, "=> %s (tparams = %s, under = %s)", n, n.tparams.list(), n.underlying) 590 }() 591 } 592 593 assert(n.inst.orig.underlying != nil) 594 if n.inst.ctxt == nil { 595 n.inst.ctxt = NewContext() 596 } 597 598 orig := n.inst.orig 599 targs := n.inst.targs 600 601 if _, unexpanded := orig.underlying.(*Named); unexpanded { 602 // We should only get a Named underlying type here during type checking 603 // (for example, in recursive type declarations). 604 assert(check != nil) 605 } 606 607 if orig.tparams.Len() != targs.Len() { 608 // Mismatching arg and tparam length may be checked elsewhere. 609 return Typ[Invalid] 610 } 611 612 // Ensure that an instance is recorded before substituting, so that we 613 // resolve n for any recursive references. 614 h := n.inst.ctxt.instanceHash(orig, targs.list()) 615 n2 := n.inst.ctxt.update(h, orig, n.TypeArgs().list(), n) 616 assert(n == n2) 617 618 smap := makeSubstMap(orig.tparams.list(), targs.list()) 619 var ctxt *Context 620 if check != nil { 621 ctxt = check.context() 622 } 623 underlying := n.check.subst(n.obj.pos, orig.underlying, smap, n, ctxt) 624 // If the underlying type of n is an interface, we need to set the receiver of 625 // its methods accurately -- we set the receiver of interface methods on 626 // the RHS of a type declaration to the defined type. 627 if iface, _ := underlying.(*Interface); iface != nil { 628 if methods, copied := replaceRecvType(iface.methods, orig, n); copied { 629 // If the underlying type doesn't actually use type parameters, it's 630 // possible that it wasn't substituted. In this case we need to create 631 // a new *Interface before modifying receivers. 632 if iface == orig.underlying { 633 old := iface 634 iface = check.newInterface() 635 iface.embeddeds = old.embeddeds 636 iface.complete = old.complete 637 iface.implicit = old.implicit // should be false but be conservative 638 underlying = iface 639 } 640 iface.methods = methods 641 } 642 } 643 644 return underlying 645 } 646 647 // safeUnderlying returns the underlying type of typ without expanding 648 // instances, to avoid infinite recursion. 649 // 650 // TODO(rfindley): eliminate this function or give it a better name. 651 func safeUnderlying(typ Type) Type { 652 if t, _ := typ.(*Named); t != nil { 653 return t.underlying 654 } 655 return typ.Underlying() 656 } 657