instantiate.go

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