// 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.
//
// 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  {
		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, , , )
	return , nil
}

// instance creates a type or function instance using the given original type
// typ and arguments targs. For Named types the resulting instance will be
// unexpanded.
func ( *Checker) ( token.Pos,  Type,  []Type,  *Context) ( Type) {
	var  string
	if  != nil {
		 = .instanceHash(, )
		// typ may already have been instantiated with identical type arguments. In
		// that case, re-use the existing instance.
		if  := .lookup(, , );  != nil {
			return 
		}
	}

	switch orig := .(type) {
	case *Named:
		 := NewTypeName(, .obj.pkg, .obj.name, nil)
		 := .newNamed(, , nil, nil, nil) // underlying, tparams, and methods are set when named is resolved
		.targs = newTypeList()
		.resolver = func( *Context,  *Named) (*TypeParamList, Type, *methodList) {
			return expandNamed(, , )
		}
		 = 

	case *Signature:
		 := .TypeParams()
		if !.validateTArgLen(, .Len(), len()) {
			return Typ[Invalid]
		}
		if .Len() == 0 {
			return  // nothing to do (minor optimization)
		}
		 := .subst(, , makeSubstMap(.list(), ), ).(*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", , ))
	}

	if  != nil {
		// It's possible that we've lost a race to add named to the context.
		// In this case, use whichever instance is recorded in the context.
		 = .update(, , , )
	}

	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) (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)
		if  := .implements([], );  != nil {
			return , 
		}
	}
	return -1, nil
}

// implements checks if V implements T and reports an error if it doesn't.
// The receiver may be nil if implements is called through an exported
// API call such as AssignableTo.
func ( *Checker) (,  Type) error {
	 := under()
	 := under()
	if  == Typ[Invalid] ||  == Typ[Invalid] {
		return nil // avoid follow-on errors
	}
	if ,  := .(*Pointer);  != nil && under(.base) == Typ[Invalid] {
		return nil // avoid follow-on errors (see issue #49541 for an example)
	}

	 := func( string,  ...any) error {
		return errors.New(.sprintf(, ...))
	}

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

	// Every type satisfies the empty interface.
	if .Empty() {
		return nil
	}
	// 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 nil
	}
	// type set of V is not empty

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

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

	// If T is comparable, V must be comparable.
	// Remember as a pending error and report only if we don't have a more specific error.
	var  error
	if .IsComparable() && !comparable(, false, nil, nil) {
		 = ("%s does not implement comparable", )
	}

	// 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
			return ("%s does not implement %s", , )
		}
		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 {
			return ("%s does not implement %s (possibly missing ~ for %s in constraint %s)", , , , )
		} else {
			return ("%s does not implement %s", , )
		}
	}

	return 
}