instantiate.go

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