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  	. "internal/types/errors"
    15  )
    16  
    17  // Instantiate instantiates the type orig with the given type arguments targs.
    18  // orig must be a *Named or a *Signature type. If there is no error, the
    19  // resulting Type is an instantiated type of the same kind (either a *Named or
    20  // a *Signature). Methods attached to a *Named type are also instantiated, and
    21  // associated with a new *Func that has the same position as the original
    22  // method, but nil function scope.
    23  //
    24  // If ctxt is non-nil, it may be used to de-duplicate the instance against
    25  // previous instances with the same identity. As a special case, generic
    26  // *Signature origin types are only considered identical if they are pointer
    27  // equivalent, so that instantiating distinct (but possibly identical)
    28  // signatures will yield different instances. The use of a shared context does
    29  // not guarantee that identical instances are deduplicated in all cases.
    30  //
    31  // If validate is set, Instantiate verifies that the number of type arguments
    32  // and parameters match, and that the type arguments satisfy their
    33  // corresponding type constraints. If verification fails, the resulting error
    34  // may wrap an *ArgumentError indicating which type argument did not satisfy
    35  // its corresponding type parameter constraint, and why.
    36  //
    37  // If validate is not set, Instantiate does not verify the type argument count
    38  // or whether the type arguments satisfy their constraints. Instantiate is
    39  // guaranteed to not return an error, but may panic. Specifically, for
    40  // *Signature types, Instantiate will panic immediately if the type argument
    41  // count is incorrect; for *Named types, a panic may occur later inside the
    42  // *Named API.
    43  func Instantiate(ctxt *Context, orig Type, targs []Type, validate bool) (Type, error) {
    44  	if ctxt == nil {
    45  		ctxt = NewContext()
    46  	}
    47  	if validate {
    48  		var tparams []*TypeParam
    49  		switch t := orig.(type) {
    50  		case *Named:
    51  			tparams = t.TypeParams().list()
    52  		case *Signature:
    53  			tparams = t.TypeParams().list()
    54  		}
    55  		if len(targs) != len(tparams) {
    56  			return nil, fmt.Errorf("got %d type arguments but %s has %d type parameters", len(targs), orig, len(tparams))
    57  		}
    58  		if i, err := (*Checker)(nil).verify(nopos, tparams, targs, ctxt); err != nil {
    59  			return nil, &ArgumentError{i, err}
    60  		}
    61  	}
    62  
    63  	inst := (*Checker)(nil).instance(nopos, orig, targs, nil, ctxt)
    64  	return inst, nil
    65  }
    66  
    67  // instance instantiates the given original (generic) function or type with the
    68  // provided type arguments and returns the resulting instance. If an identical
    69  // instance exists already in the given contexts, it returns that instance,
    70  // otherwise it creates a new one.
    71  //
    72  // If expanding is non-nil, it is the Named instance type currently being
    73  // expanded. If ctxt is non-nil, it is the context associated with the current
    74  // type-checking pass or call to Instantiate. At least one of expanding or ctxt
    75  // must be non-nil.
    76  //
    77  // For Named types the resulting instance may be unexpanded.
    78  func (check *Checker) instance(pos syntax.Pos, orig Type, targs []Type, expanding *Named, ctxt *Context) (res Type) {
    79  	// The order of the contexts below matters: we always prefer instances in the
    80  	// expanding instance context in order to preserve reference cycles.
    81  	//
    82  	// Invariant: if expanding != nil, the returned instance will be the instance
    83  	// recorded in expanding.inst.ctxt.
    84  	var ctxts []*Context
    85  	if expanding != nil {
    86  		ctxts = append(ctxts, expanding.inst.ctxt)
    87  	}
    88  	if ctxt != nil {
    89  		ctxts = append(ctxts, ctxt)
    90  	}
    91  	assert(len(ctxts) > 0)
    92  
    93  	// Compute all hashes; hashes may differ across contexts due to different
    94  	// unique IDs for Named types within the hasher.
    95  	hashes := make([]string, len(ctxts))
    96  	for i, ctxt := range ctxts {
    97  		hashes[i] = ctxt.instanceHash(orig, targs)
    98  	}
    99  
   100  	// If local is non-nil, updateContexts return the type recorded in
   101  	// local.
   102  	updateContexts := func(res Type) Type {
   103  		for i := len(ctxts) - 1; i >= 0; i-- {
   104  			res = ctxts[i].update(hashes[i], orig, targs, res)
   105  		}
   106  		return res
   107  	}
   108  
   109  	// typ may already have been instantiated with identical type arguments. In
   110  	// that case, re-use the existing instance.
   111  	for i, ctxt := range ctxts {
   112  		if inst := ctxt.lookup(hashes[i], orig, targs); inst != nil {
   113  			return updateContexts(inst)
   114  		}
   115  	}
   116  
   117  	switch orig := orig.(type) {
   118  	case *Named:
   119  		res = check.newNamedInstance(pos, orig, targs, expanding) // substituted lazily
   120  
   121  	case *Signature:
   122  		assert(expanding == nil) // function instances cannot be reached from Named types
   123  
   124  		tparams := orig.TypeParams()
   125  		// TODO(gri) investigate if this is needed (type argument and parameter count seem to be correct here)
   126  		if !check.validateTArgLen(pos, orig.String(), tparams.Len(), len(targs)) {
   127  			return Typ[Invalid]
   128  		}
   129  		if tparams.Len() == 0 {
   130  			return orig // nothing to do (minor optimization)
   131  		}
   132  		sig := check.subst(pos, orig, makeSubstMap(tparams.list(), targs), nil, ctxt).(*Signature)
   133  		// If the signature doesn't use its type parameters, subst
   134  		// will not make a copy. In that case, make a copy now (so
   135  		// we can set tparams to nil w/o causing side-effects).
   136  		if sig == orig {
   137  			copy := *sig
   138  			sig = &copy
   139  		}
   140  		// After instantiating a generic signature, it is not generic
   141  		// anymore; we need to set tparams to nil.
   142  		sig.tparams = nil
   143  		res = sig
   144  
   145  	default:
   146  		// only types and functions can be generic
   147  		panic(fmt.Sprintf("%v: cannot instantiate %v", pos, orig))
   148  	}
   149  
   150  	// Update all contexts; it's possible that we've lost a race.
   151  	return updateContexts(res)
   152  }
   153  
   154  // validateTArgLen checks that the number of type arguments (got) matches the
   155  // number of type parameters (want); if they don't match an error is reported.
   156  // If validation fails and check is nil, validateTArgLen panics.
   157  func (check *Checker) validateTArgLen(pos syntax.Pos, name string, want, got int) bool {
   158  	var qual string
   159  	switch {
   160  	case got < want:
   161  		qual = "not enough"
   162  	case got > want:
   163  		qual = "too many"
   164  	default:
   165  		return true
   166  	}
   167  
   168  	msg := check.sprintf("%s type arguments for type %s: have %d, want %d", qual, name, got, want)
   169  	if check != nil {
   170  		check.error(atPos(pos), WrongTypeArgCount, msg)
   171  		return false
   172  	}
   173  
   174  	panic(fmt.Sprintf("%v: %s", pos, msg))
   175  }
   176  
   177  func (check *Checker) verify(pos syntax.Pos, tparams []*TypeParam, targs []Type, ctxt *Context) (int, error) {
   178  	smap := makeSubstMap(tparams, targs)
   179  	for i, tpar := range tparams {
   180  		// Ensure that we have a (possibly implicit) interface as type bound (go.dev/issue/51048).
   181  		tpar.iface()
   182  		// The type parameter bound is parameterized with the same type parameters
   183  		// as the instantiated type; before we can use it for bounds checking we
   184  		// need to instantiate it with the type arguments with which we instantiated
   185  		// the parameterized type.
   186  		bound := check.subst(pos, tpar.bound, smap, nil, ctxt)
   187  		var cause string
   188  		if !check.implements(pos, targs[i], bound, true, &cause) {
   189  			return i, errors.New(cause)
   190  		}
   191  	}
   192  	return -1, nil
   193  }
   194  
   195  // implements checks if V implements T. The receiver may be nil if implements
   196  // is called through an exported API call such as AssignableTo. If constraint
   197  // is set, T is a type constraint.
   198  //
   199  // If the provided cause is non-nil, it may be set to an error string
   200  // explaining why V does not implement (or satisfy, for constraints) T.
   201  func (check *Checker) implements(pos syntax.Pos, V, T Type, constraint bool, cause *string) bool {
   202  	Vu := under(V)
   203  	Tu := under(T)
   204  	if !isValid(Vu) || !isValid(Tu) {
   205  		return true // avoid follow-on errors
   206  	}
   207  	if p, _ := Vu.(*Pointer); p != nil && !isValid(under(p.base)) {
   208  		return true // avoid follow-on errors (see go.dev/issue/49541 for an example)
   209  	}
   210  
   211  	verb := "implement"
   212  	if constraint {
   213  		verb = "satisfy"
   214  	}
   215  
   216  	Ti, _ := Tu.(*Interface)
   217  	if Ti == nil {
   218  		if cause != nil {
   219  			var detail string
   220  			if isInterfacePtr(Tu) {
   221  				detail = check.sprintf("type %s is pointer to interface, not interface", T)
   222  			} else {
   223  				detail = check.sprintf("%s is not an interface", T)
   224  			}
   225  			*cause = check.sprintf("%s does not %s %s (%s)", V, verb, T, detail)
   226  		}
   227  		return false
   228  	}
   229  
   230  	// Every type satisfies the empty interface.
   231  	if Ti.Empty() {
   232  		return true
   233  	}
   234  	// T is not the empty interface (i.e., the type set of T is restricted)
   235  
   236  	// An interface V with an empty type set satisfies any interface.
   237  	// (The empty set is a subset of any set.)
   238  	Vi, _ := Vu.(*Interface)
   239  	if Vi != nil && Vi.typeSet().IsEmpty() {
   240  		return true
   241  	}
   242  	// type set of V is not empty
   243  
   244  	// No type with non-empty type set satisfies the empty type set.
   245  	if Ti.typeSet().IsEmpty() {
   246  		if cause != nil {
   247  			*cause = check.sprintf("cannot %s %s (empty type set)", verb, T)
   248  		}
   249  		return false
   250  	}
   251  
   252  	// V must implement T's methods, if any.
   253  	if m, _ := check.missingMethod(V, T, true, Identical, cause); m != nil /* !Implements(V, T) */ {
   254  		if cause != nil {
   255  			*cause = check.sprintf("%s does not %s %s %s", V, verb, T, *cause)
   256  		}
   257  		return false
   258  	}
   259  
   260  	// Only check comparability if we don't have a more specific error.
   261  	checkComparability := func() bool {
   262  		if !Ti.IsComparable() {
   263  			return true
   264  		}
   265  		// If T is comparable, V must be comparable.
   266  		// If V is strictly comparable, we're done.
   267  		if comparable(V, false /* strict comparability */, nil, nil) {
   268  			return true
   269  		}
   270  		// For constraint satisfaction, use dynamic (spec) comparability
   271  		// so that ordinary, non-type parameter interfaces implement comparable.
   272  		if constraint && comparable(V, true /* spec comparability */, nil, nil) {
   273  			// V is comparable if we are at Go 1.20 or higher.
   274  			if check == nil || check.allowVersion(check.pkg, atPos(pos), go1_20) { // atPos needed so that go/types generate passes
   275  				return true
   276  			}
   277  			if cause != nil {
   278  				*cause = check.sprintf("%s to %s comparable requires go1.20 or later", V, verb)
   279  			}
   280  			return false
   281  		}
   282  		if cause != nil {
   283  			*cause = check.sprintf("%s does not %s comparable", V, verb)
   284  		}
   285  		return false
   286  	}
   287  
   288  	// V must also be in the set of types of T, if any.
   289  	// Constraints with empty type sets were already excluded above.
   290  	if !Ti.typeSet().hasTerms() {
   291  		return checkComparability() // nothing to do
   292  	}
   293  
   294  	// If V is itself an interface, each of its possible types must be in the set
   295  	// of T types (i.e., the V type set must be a subset of the T type set).
   296  	// Interfaces V with empty type sets were already excluded above.
   297  	if Vi != nil {
   298  		if !Vi.typeSet().subsetOf(Ti.typeSet()) {
   299  			// TODO(gri) report which type is missing
   300  			if cause != nil {
   301  				*cause = check.sprintf("%s does not %s %s", V, verb, T)
   302  			}
   303  			return false
   304  		}
   305  		return checkComparability()
   306  	}
   307  
   308  	// Otherwise, V's type must be included in the iface type set.
   309  	var alt Type
   310  	if Ti.typeSet().is(func(t *term) bool {
   311  		if !t.includes(V) {
   312  			// If V ∉ t.typ but V ∈ ~t.typ then remember this type
   313  			// so we can suggest it as an alternative in the error
   314  			// message.
   315  			if alt == nil && !t.tilde && Identical(t.typ, under(t.typ)) {
   316  				tt := *t
   317  				tt.tilde = true
   318  				if tt.includes(V) {
   319  					alt = t.typ
   320  				}
   321  			}
   322  			return true
   323  		}
   324  		return false
   325  	}) {
   326  		if cause != nil {
   327  			var detail string
   328  			switch {
   329  			case alt != nil:
   330  				detail = check.sprintf("possibly missing ~ for %s in %s", alt, T)
   331  			case mentions(Ti, V):
   332  				detail = check.sprintf("%s mentions %s, but %s is not in the type set of %s", T, V, V, T)
   333  			default:
   334  				detail = check.sprintf("%s missing in %s", V, Ti.typeSet().terms)
   335  			}
   336  			*cause = check.sprintf("%s does not %s %s (%s)", V, verb, T, detail)
   337  		}
   338  		return false
   339  	}
   340  
   341  	return checkComparability()
   342  }
   343  
   344  // mentions reports whether type T "mentions" typ in an (embedded) element or term
   345  // of T (whether typ is in the type set of T or not). For better error messages.
   346  func mentions(T, typ Type) bool {
   347  	switch T := T.(type) {
   348  	case *Interface:
   349  		for _, e := range T.embeddeds {
   350  			if mentions(e, typ) {
   351  				return true
   352  			}
   353  		}
   354  	case *Union:
   355  		for _, t := range T.terms {
   356  			if mentions(t.typ, typ) {
   357  				return true
   358  			}
   359  		}
   360  	default:
   361  		if Identical(T, typ) {
   362  			return true
   363  		}
   364  	}
   365  	return false
   366  }
   367
View as plain text