// Copyright 2021 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// This file implements instantiation of generic types
// through substitution of type parameters by type arguments.

package types

import (
	
	
	
	. 
)

// Instantiate instantiates the type orig with the given type arguments targs.
// orig must be a *Named or a *Signature type. If there is no error, the
// resulting Type is an instantiated type of the same kind (either a *Named or
// a *Signature). Methods attached to a *Named type are also instantiated, and
// associated with a new *Func that has the same position as the original
// method, but nil function scope.
//
// If ctxt is non-nil, it may be used to de-duplicate the instance against
// previous instances with the same identity. As a special case, generic
// *Signature origin types are only considered identical if they are pointer
// equivalent, so that instantiating distinct (but possibly identical)
// signatures will yield different instances. The use of a shared context does
// not guarantee that identical instances are deduplicated in all cases.
//
// If validate is set, Instantiate verifies that the number of type arguments
// and parameters match, and that the type arguments satisfy their
// corresponding type constraints. If verification fails, the resulting error
// may wrap an *ArgumentError indicating which type argument did not satisfy
// its corresponding type parameter constraint, and why.
//
// If validate is not set, Instantiate does not verify the type argument count
// or whether the type arguments satisfy their constraints. Instantiate is
// guaranteed to not return an error, but may panic. Specifically, for
// *Signature types, Instantiate will panic immediately if the type argument
// count is incorrect; for *Named types, a panic may occur later inside the
// *Named API.
func ( *Context,  Type,  []Type,  bool) (Type, error) {
	if  == nil {
		 = NewContext()
	}
	if  {
		var  []*TypeParam
		switch t := .(type) {
		case *Named:
			 = .TypeParams().list()
		case *Signature:
			 = .TypeParams().list()
		}
		if len() != len() {
			return nil, fmt.Errorf("got %d type arguments but %s has %d type parameters", len(), , len())
		}
		if ,  := (*Checker)(nil).verify(token.NoPos, , , );  != nil {
			return nil, &ArgumentError{, }
		}
	}

	 := (*Checker)(nil).instance(token.NoPos, , , nil, )
	return , nil
}

// instance instantiates the given original (generic) function or type with the
// provided type arguments and returns the resulting instance. If an identical
// instance exists already in the given contexts, it returns that instance,
// otherwise it creates a new one.
//
// If expanding is non-nil, it is the Named instance type currently being
// expanded. If ctxt is non-nil, it is the context associated with the current
// type-checking pass or call to Instantiate. At least one of expanding or ctxt
// must be non-nil.
//
// For Named types the resulting instance may be unexpanded.
func ( *Checker) ( token.Pos,  Type,  []Type,  *Named,  *Context) ( Type) {
	// The order of the contexts below matters: we always prefer instances in the
	// expanding instance context in order to preserve reference cycles.
	//
	// Invariant: if expanding != nil, the returned instance will be the instance
	// recorded in expanding.inst.ctxt.
	var  []*Context
	if  != nil {
		 = append(, .inst.ctxt)
	}
	if  != nil {
		 = append(, )
	}
	assert(len() > 0)

	// Compute all hashes; hashes may differ across contexts due to different
	// unique IDs for Named types within the hasher.
	 := make([]string, len())
	for ,  := range  {
		[] = .instanceHash(, )
	}

	// If local is non-nil, updateContexts return the type recorded in
	// local.
	 := func( Type) Type {
		for  := len() - 1;  >= 0; -- {
			 = [].update([], , , )
		}
		return 
	}

	// typ may already have been instantiated with identical type arguments. In
	// that case, re-use the existing instance.
	for ,  := range  {
		if  := .lookup([], , );  != nil {
			return ()
		}
	}

	switch orig := .(type) {
	case *Named:
		 = .newNamedInstance(, , , ) // substituted lazily

	case *Signature:
		assert( == nil) // function instances cannot be reached from Named types

		 := .TypeParams()
		if !.validateTArgLen(, .Len(), len()) {
			return Typ[Invalid]
		}
		if .Len() == 0 {
			return  // nothing to do (minor optimization)
		}
		 := .subst(, , makeSubstMap(.list(), ), nil, ).(*Signature)
		// If the signature doesn't use its type parameters, subst
		// will not make a copy. In that case, make a copy now (so
		// we can set tparams to nil w/o causing side-effects).
		if  ==  {
			 := *
			 = &
		}
		// After instantiating a generic signature, it is not generic
		// anymore; we need to set tparams to nil.
		.tparams = nil
		 = 

	default:
		// only types and functions can be generic
		panic(fmt.Sprintf("%v: cannot instantiate %v", , ))
	}

	// Update all contexts; it's possible that we've lost a race.
	return ()
}

// validateTArgLen verifies that the length of targs and tparams matches,
// reporting an error if not. If validation fails and check is nil,
// validateTArgLen panics.
func ( *Checker) ( token.Pos, ,  int) bool {
	if  !=  {
		// TODO(gri) provide better error message
		if  != nil {
			.errorf(atPos(), WrongTypeArgCount, "got %d arguments but %d type parameters", , )
			return false
		}
		panic(fmt.Sprintf("%v: got %d arguments but %d type parameters", , , ))
	}
	return true
}

func ( *Checker) ( token.Pos,  []*TypeParam,  []Type,  *Context) (int, error) {
	 := makeSubstMap(, )
	for ,  := range  {
		// Ensure that we have a (possibly implicit) interface as type bound (issue #51048).
		.iface()
		// The type parameter bound is parameterized with the same type parameters
		// as the instantiated type; before we can use it for bounds checking we
		// need to instantiate it with the type arguments with which we instantiated
		// the parameterized type.
		 := .subst(, .bound, , nil, )
		var  string
		if !.implements([], , true, &) {
			return , errors.New()
		}
	}
	return -1, nil
}

// implements checks if V implements T. The receiver may be nil if implements
// is called through an exported API call such as AssignableTo. If constraint
// is set, T is a type constraint.
//
// If the provided cause is non-nil, it may be set to an error string
// explaining why V does not implement T.
func ( *Checker) (,  Type,  bool,  *string) bool {
	 := under()
	 := under()
	if  == Typ[Invalid] ||  == Typ[Invalid] {
		return true // avoid follow-on errors
	}
	if ,  := .(*Pointer);  != nil && under(.base) == Typ[Invalid] {
		return true // avoid follow-on errors (see issue #49541 for an example)
	}

	,  := .(*Interface)
	if  == nil {
		if  != nil {
			var  string
			if isInterfacePtr() {
				 = .sprintf("type %s is pointer to interface, not interface", )
			} else {
				 = .sprintf("%s is not an interface", )
			}
			* = .sprintf("%s does not implement %s (%s)", , , )
		}
		return false
	}

	// Every type satisfies the empty interface.
	if .Empty() {
		return true
	}
	// T is not the empty interface (i.e., the type set of T is restricted)

	// An interface V with an empty type set satisfies any interface.
	// (The empty set is a subset of any set.)
	,  := .(*Interface)
	if  != nil && .typeSet().IsEmpty() {
		return true
	}
	// type set of V is not empty

	// No type with non-empty type set satisfies the empty type set.
	if .typeSet().IsEmpty() {
		if  != nil {
			* = .sprintf("cannot implement %s (empty type set)", )
		}
		return false
	}

	// V must implement T's methods, if any.
	if ,  := .missingMethod(, , true);  != nil /* !Implements(V, Ti) */ {
		if  != nil {
			* = .sprintf("%s does not implement %s %s", , , .missingMethodCause(, , , ))
		}
		return false
	}

	// Only check comparability if we don't have a more specific error.
	 := func() bool {
		if !.IsComparable() {
			return true
		}
		// If T is comparable, V must be comparable.
		// If V is strictly comparable, we're done.
		if comparable(, false /* strict comparability */, nil, nil) {
			return true
		}
		// If check.conf.OldComparableSemantics is set (by the compiler or
		// a test), we only consider strict comparability and we're done.
		// TODO(gri) remove this check for Go 1.21
		if  != nil && .conf.oldComparableSemantics {
			if  != nil {
				* = .sprintf("%s does not implement comparable", )
			}
			return false
		}
		// For constraint satisfaction, use dynamic (spec) comparability
		// so that ordinary, non-type parameter interfaces implement comparable.
		if  && comparable(, true /* spec comparability */, nil, nil) {
			// V is comparable if we are at Go 1.20 or higher.
			if  == nil || .allowVersion(.pkg, 1, 20) {
				return true
			}
			if  != nil {
				* = .sprintf("%s to implement comparable requires go1.20 or later", )
			}
			return false
		}
		if  != nil {
			* = .sprintf("%s does not implement comparable", )
		}
		return false
	}

	// V must also be in the set of types of T, if any.
	// Constraints with empty type sets were already excluded above.
	if !.typeSet().hasTerms() {
		return () // nothing to do
	}

	// If V is itself an interface, each of its possible types must be in the set
	// of T types (i.e., the V type set must be a subset of the T type set).
	// Interfaces V with empty type sets were already excluded above.
	if  != nil {
		if !.typeSet().subsetOf(.typeSet()) {
			// TODO(gri) report which type is missing
			if  != nil {
				* = .sprintf("%s does not implement %s", , )
			}
			return false
		}
		return ()
	}

	// Otherwise, V's type must be included in the iface type set.
	var  Type
	if .typeSet().is(func( *term) bool {
		if !.includes() {
			// If V ∉ t.typ but V ∈ ~t.typ then remember this type
			// so we can suggest it as an alternative in the error
			// message.
			if  == nil && !.tilde && Identical(.typ, under(.typ)) {
				 := *
				.tilde = true
				if .includes() {
					 = .typ
				}
			}
			return true
		}
		return false
	}) {
		if  != nil {
			if  != nil {
				* = .sprintf("%s does not implement %s (possibly missing ~ for %s in constraint %s)", , , , )
			} else {
				* = .sprintf("%s does not implement %s (%s missing in %s)", , , , .typeSet().terms)
			}
		}
		return false
	}

	return ()
}