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