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 types2
     6  
     7  import (
     8  	"cmd/compile/internal/syntax"
     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 from (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 { return t.orig.obj } // for non-instances this is the same as t.obj
   103  
   104  // Origin returns the generic type from which the named type t is
   105  // instantiated. If t is not an instantiated type, the result is t.
   106  func (t *Named) Origin() *Named { return t.orig }
   107  
   108  // TODO(gri) Come up with a better representation and API to distinguish
   109  //           between parameterized instantiated and non-instantiated types.
   110  
   111  // TypeParams returns the type parameters of the named type t, or nil.
   112  // The result is non-nil for an (originally) generic type even if it is instantiated.
   113  func (t *Named) TypeParams() *TypeParamList { return t.resolve(nil).tparams }
   114  
   115  // SetTypeParams sets the type parameters of the named type t.
   116  // t must not have type arguments.
   117  func (t *Named) SetTypeParams(tparams []*TypeParam) {
   118  	assert(t.targs.Len() == 0)
   119  	t.resolve(nil).tparams = bindTParams(tparams)
   120  }
   121  
   122  // TypeArgs returns the type arguments used to instantiate the named type t.
   123  func (t *Named) TypeArgs() *TypeList { return t.targs }
   124  
   125  // NumMethods returns the number of explicit methods defined for t.
   126  //
   127  // For an ordinary or instantiated type t, the receiver base type of these
   128  // methods will be the named type t. For an uninstantiated generic type t, each
   129  // method receiver will be instantiated with its receiver type parameters.
   130  func (t *Named) NumMethods() int { return t.resolve(nil).methods.Len() }
   131  
   132  // Method returns the i'th method of named type t for 0 <= i < t.NumMethods().
   133  func (t *Named) Method(i int) *Func {
   134  	t.resolve(nil)
   135  	return t.methods.At(i, func() *Func {
   136  		return t.instantiateMethod(i)
   137  	})
   138  }
   139  
   140  // instiateMethod instantiates the i'th method for an instantiated receiver.
   141  func (t *Named) instantiateMethod(i int) *Func {
   142  	assert(t.TypeArgs().Len() > 0) // t must be an instance
   143  
   144  	// t.orig.methods is not lazy. origm is the method instantiated with its
   145  	// receiver type parameters (the "origin" method).
   146  	origm := t.orig.Method(i)
   147  	assert(origm != nil)
   148  
   149  	check := t.check
   150  	// Ensure that the original method is type-checked.
   151  	if check != nil {
   152  		check.objDecl(origm, nil)
   153  	}
   154  
   155  	origSig := origm.typ.(*Signature)
   156  	rbase, _ := deref(origSig.Recv().Type())
   157  
   158  	// If rbase is t, then origm is already the instantiated method we're looking
   159  	// for. In this case, we return origm to preserve the invariant that
   160  	// traversing Method->Receiver Type->Method should get back to the same
   161  	// method.
   162  	//
   163  	// This occurs if t is instantiated with the receiver type parameters, as in
   164  	// the use of m in func (r T[_]) m() { r.m() }.
   165  	if rbase == t {
   166  		return origm
   167  	}
   168  
   169  	sig := origSig
   170  	// We can only substitute if we have a correspondence between type arguments
   171  	// and type parameters. This check is necessary in the presence of invalid
   172  	// code.
   173  	if origSig.RecvTypeParams().Len() == t.targs.Len() {
   174  		ctxt := check.bestContext(nil)
   175  		smap := makeSubstMap(origSig.RecvTypeParams().list(), t.targs.list())
   176  		sig = check.subst(origm.pos, origSig, smap, ctxt).(*Signature)
   177  	}
   178  
   179  	if sig == origSig {
   180  		// No substitution occurred, but we still need to create a new signature to
   181  		// hold the instantiated receiver.
   182  		copy := *origSig
   183  		sig = &copy
   184  	}
   185  
   186  	var rtyp Type
   187  	if origm.hasPtrRecv() {
   188  		rtyp = NewPointer(t)
   189  	} else {
   190  		rtyp = t
   191  	}
   192  
   193  	sig.recv = substVar(origSig.recv, rtyp)
   194  	return NewFunc(origm.pos, origm.pkg, origm.name, sig)
   195  }
   196  
   197  // SetUnderlying sets the underlying type and marks t as complete.
   198  // t must not have type arguments.
   199  func (t *Named) SetUnderlying(underlying Type) {
   200  	assert(t.targs.Len() == 0)
   201  	if underlying == nil {
   202  		panic("underlying type must not be nil")
   203  	}
   204  	if _, ok := underlying.(*Named); ok {
   205  		panic("underlying type must not be *Named")
   206  	}
   207  	t.resolve(nil).underlying = underlying
   208  	if t.fromRHS == nil {
   209  		t.fromRHS = underlying // for cycle detection
   210  	}
   211  }
   212  
   213  // AddMethod adds method m unless it is already in the method list.
   214  // t must not have type arguments.
   215  func (t *Named) AddMethod(m *Func) {
   216  	assert(t.targs.Len() == 0)
   217  	t.resolve(nil)
   218  	if t.methods == nil {
   219  		t.methods = newMethodList(nil)
   220  	}
   221  	t.methods.Add(m)
   222  }
   223  
   224  func (t *Named) Underlying() Type { return t.resolve(nil).underlying }
   225  func (t *Named) String() string   { return TypeString(t, nil) }
   226  
   227  // ----------------------------------------------------------------------------
   228  // Implementation
   229  
   230  // under returns the expanded underlying type of n0; possibly by following
   231  // forward chains of named types. If an underlying type is found, resolve
   232  // the chain by setting the underlying type for each defined type in the
   233  // chain before returning it. If no underlying type is found or a cycle
   234  // is detected, the result is Typ[Invalid]. If a cycle is detected and
   235  // n0.check != nil, the cycle is reported.
   236  //
   237  // This is necessary because the underlying type of named may be itself a
   238  // named type that is incomplete:
   239  //
   240  //	type (
   241  //		A B
   242  //		B *C
   243  //		C A
   244  //	)
   245  //
   246  // The type of C is the (named) type of A which is incomplete,
   247  // and which has as its underlying type the named type B.
   248  func (n0 *Named) under() Type {
   249  	u := n0.Underlying()
   250  
   251  	// If the underlying type of a defined type is not a defined
   252  	// (incl. instance) type, then that is the desired underlying
   253  	// type.
   254  	var n1 *Named
   255  	switch u1 := u.(type) {
   256  	case nil:
   257  		// After expansion via Underlying(), we should never encounter a nil
   258  		// underlying.
   259  		panic("nil underlying")
   260  	default:
   261  		// common case
   262  		return u
   263  	case *Named:
   264  		// handled below
   265  		n1 = u1
   266  	}
   267  
   268  	if n0.check == nil {
   269  		panic("Named.check == nil but type is incomplete")
   270  	}
   271  
   272  	// Invariant: after this point n0 as well as any named types in its
   273  	// underlying chain should be set up when this function exits.
   274  	check := n0.check
   275  	n := n0
   276  
   277  	seen := make(map[*Named]int) // types that need their underlying resolved
   278  	var path []Object            // objects encountered, for cycle reporting
   279  
   280  loop:
   281  	for {
   282  		seen[n] = len(seen)
   283  		path = append(path, n.obj)
   284  		n = n1
   285  		if i, ok := seen[n]; ok {
   286  			// cycle
   287  			check.cycleError(path[i:])
   288  			u = Typ[Invalid]
   289  			break
   290  		}
   291  		u = n.Underlying()
   292  		switch u1 := u.(type) {
   293  		case nil:
   294  			u = Typ[Invalid]
   295  			break loop
   296  		default:
   297  			break loop
   298  		case *Named:
   299  			// Continue collecting *Named types in the chain.
   300  			n1 = u1
   301  		}
   302  	}
   303  
   304  	for n := range seen {
   305  		// We should never have to update the underlying type of an imported type;
   306  		// those underlying types should have been resolved during the import.
   307  		// Also, doing so would lead to a race condition (was issue #31749).
   308  		// Do this check always, not just in debug mode (it's cheap).
   309  		if n.obj.pkg != check.pkg {
   310  			panic("imported type with unresolved underlying type")
   311  		}
   312  		n.underlying = u
   313  	}
   314  
   315  	return u
   316  }
   317  
   318  func (n *Named) setUnderlying(typ Type) {
   319  	if n != nil {
   320  		n.underlying = typ
   321  	}
   322  }
   323  
   324  func (n *Named) lookupMethod(pkg *Package, name string, foldCase bool) (int, *Func) {
   325  	n.resolve(nil)
   326  	// If n is an instance, we may not have yet instantiated all of its methods.
   327  	// Look up the method index in orig, and only instantiate method at the
   328  	// matching index (if any).
   329  	i, _ := n.orig.methods.Lookup(pkg, name, foldCase)
   330  	if i < 0 {
   331  		return -1, nil
   332  	}
   333  	// For instances, m.Method(i) will be different from the orig method.
   334  	return i, n.Method(i)
   335  }
   336  
   337  // bestContext returns the best available context. In order of preference:
   338  // - the given ctxt, if non-nil
   339  // - check.ctxt, if check is non-nil
   340  // - a new Context
   341  func (check *Checker) bestContext(ctxt *Context) *Context {
   342  	if ctxt != nil {
   343  		return ctxt
   344  	}
   345  	if check != nil {
   346  		if check.ctxt == nil {
   347  			check.ctxt = NewContext()
   348  		}
   349  		return check.ctxt
   350  	}
   351  	return NewContext()
   352  }
   353  
   354  // expandNamed ensures that the underlying type of n is instantiated.
   355  // The underlying type will be Typ[Invalid] if there was an error.
   356  func expandNamed(ctxt *Context, n *Named, instPos syntax.Pos) (tparams *TypeParamList, underlying Type, methods *methodList) {
   357  	n.orig.resolve(ctxt)
   358  	assert(n.orig.underlying != nil)
   359  
   360  	check := n.check
   361  
   362  	if _, unexpanded := n.orig.underlying.(*Named); unexpanded {
   363  		// We should only get an unexpanded underlying here during type checking
   364  		// (for example, in recursive type declarations).
   365  		assert(check != nil)
   366  	}
   367  
   368  	// Mismatching arg and tparam length may be checked elsewhere.
   369  	if n.orig.tparams.Len() == n.targs.Len() {
   370  		// We must always have a context, to avoid infinite recursion.
   371  		ctxt = check.bestContext(ctxt)
   372  		h := ctxt.instanceHash(n.orig, n.targs.list())
   373  		// ensure that an instance is recorded for h to avoid infinite recursion.
   374  		ctxt.update(h, n.orig, n.TypeArgs().list(), n)
   375  
   376  		smap := makeSubstMap(n.orig.tparams.list(), n.targs.list())
   377  		underlying = n.check.subst(instPos, n.orig.underlying, smap, ctxt)
   378  		// If the underlying of n is an interface, we need to set the receiver of
   379  		// its methods accurately -- we set the receiver of interface methods on
   380  		// the RHS of a type declaration to the defined type.
   381  		if iface, _ := underlying.(*Interface); iface != nil {
   382  			if methods, copied := replaceRecvType(iface.methods, n.orig, n); copied {
   383  				// If the underlying doesn't actually use type parameters, it's possible
   384  				// that it wasn't substituted. In this case we need to create a new
   385  				// *Interface before modifying receivers.
   386  				if iface == n.orig.underlying {
   387  					old := iface
   388  					iface = check.newInterface()
   389  					iface.embeddeds = old.embeddeds
   390  					iface.complete = old.complete
   391  					iface.implicit = old.implicit // should be false but be conservative
   392  					underlying = iface
   393  				}
   394  				iface.methods = methods
   395  			}
   396  		}
   397  	} else {
   398  		underlying = Typ[Invalid]
   399  	}
   400  
   401  	return n.orig.tparams, underlying, newLazyMethodList(n.orig.methods.Len())
   402  }
   403  
   404  // safeUnderlying returns the underlying of typ without expanding instances, to
   405  // avoid infinite recursion.
   406  //
   407  // TODO(rfindley): eliminate this function or give it a better name.
   408  func safeUnderlying(typ Type) Type {
   409  	if t, _ := typ.(*Named); t != nil {
   410  		return t.underlying
   411  	}
   412  	return typ.Underlying()
   413  }
   414
View as plain text