// Copyright 2020 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 type unification.

package types

import (
	
	
	
)

// The unifier maintains two separate sets of type parameters x and y
// which are used to resolve type parameters in the x and y arguments
// provided to the unify call. For unidirectional unification, only
// one of these sets (say x) is provided, and then type parameters are
// only resolved for the x argument passed to unify, not the y argument
// (even if that also contains possibly the same type parameters). This
// is crucial to infer the type parameters of self-recursive calls:
//
//	func f[P any](a P) { f(a) }
//
// For the call f(a) we want to infer that the type argument for P is P.
// During unification, the parameter type P must be resolved to the type
// parameter P ("x" side), but the argument type P must be left alone so
// that unification resolves the type parameter P to P.
//
// For bidirectional unification, both sets are provided. This enables
// unification to go from argument to parameter type and vice versa.
// For constraint type inference, we use bidirectional unification
// where both the x and y type parameters are identical. This is done
// by setting up one of them (using init) and then assigning its value
// to the other.

const (
	// Upper limit for recursion depth. Used to catch infinite recursions
	// due to implementation issues (e.g., see issues #48619, #48656).
	unificationDepthLimit = 50

	// Whether to panic when unificationDepthLimit is reached. Turn on when
	// investigating infinite recursion.
	panicAtUnificationDepthLimit = false

	// If enableCoreTypeUnification is set, unification will consider
	// the core types, if any, of non-local (unbound) type parameters.
	enableCoreTypeUnification = true

	// If traceInference is set, unification will print a trace of its operation.
	// Interpretation of trace:
	//   x ≡ y    attempt to unify types x and y
	//   p ➞ y    type parameter p is set to type y (p is inferred to be y)
	//   p ⇄ q    type parameters p and q match (p is inferred to be q and vice versa)
	//   x ≢ y    types x and y cannot be unified
	//   [p, q, ...] ➞ [x, y, ...]    mapping from type parameters to types
	traceInference = false
)

// A unifier maintains the current type parameters for x and y
// and the respective types inferred for each type parameter.
// A unifier is created by calling newUnifier.
type unifier struct {
	exact bool
	x, y  tparamsList // x and y must initialized via tparamsList.init
	types []Type      // inferred types, shared by x and y
	depth int         // recursion depth during unification
}

// newUnifier returns a new unifier.
// If exact is set, unification requires unified types to match
// exactly. If exact is not set, a named type's underlying type
// is considered if unification would fail otherwise, and the
// direction of channels is ignored.
// TODO(gri) exact is not set anymore by a caller. Consider removing it.
func newUnifier( bool) *unifier {
	 := &unifier{exact: }
	.x.unifier = 
	.y.unifier = 
	return 
}

// unify attempts to unify x and y and reports whether it succeeded.
func ( *unifier) (,  Type) bool {
	return .nify(, , nil)
}

func ( *unifier) ( string,  ...interface{}) {
	fmt.Println(strings.Repeat(".  ", .depth) + sprintf(nil, nil, true, , ...))
}

// A tparamsList describes a list of type parameters and the types inferred for them.
type tparamsList struct {
	unifier *unifier
	tparams []*TypeParam
	// For each tparams element, there is a corresponding type slot index in indices.
	// index  < 0: unifier.types[-index-1] == nil
	// index == 0: no type slot allocated yet
	// index  > 0: unifier.types[index-1] == typ
	// Joined tparams elements share the same type slot and thus have the same index.
	// By using a negative index for nil types we don't need to check unifier.types
	// to see if we have a type or not.
	indices []int // len(d.indices) == len(d.tparams)
}

// String returns a string representation for a tparamsList. For debugging.
func ( *tparamsList) () string {
	var  bytes.Buffer
	 := newTypeWriter(&, nil)
	.byte('[')
	for ,  := range .tparams {
		if  > 0 {
			.string(", ")
		}
		.typ()
		.string(": ")
		.typ(.at())
	}
	.byte(']')
	return .String()
}

// init initializes d with the given type parameters.
// The type parameters must be in the order in which they appear in their declaration
// (this ensures that the tparams indices match the respective type parameter index).
func ( *tparamsList) ( []*TypeParam) {
	if len() == 0 {
		return
	}
	if debug {
		for ,  := range  {
			assert( == .index)
		}
	}
	.tparams = 
	.indices = make([]int, len())
}

// join unifies the i'th type parameter of x with the j'th type parameter of y.
// If both type parameters already have a type associated with them and they are
// not joined, join fails and returns false.
func ( *unifier) (,  int) bool {
	if traceInference {
		.tracef("%s ⇄ %s", .x.tparams[], .y.tparams[])
	}
	 := .x.indices[]
	 := .y.indices[]
	switch {
	case  == 0 &&  == 0:
		// Neither type parameter has a type slot associated with them.
		// Allocate a new joined nil type slot (negative index).
		.types = append(.types, nil)
		.x.indices[] = -len(.types)
		.y.indices[] = -len(.types)
	case  == 0:
		// The type parameter for x has no type slot yet. Use slot of y.
		.x.indices[] = 
	case  == 0:
		// The type parameter for y has no type slot yet. Use slot of x.
		.y.indices[] = 

	// Both type parameters have a slot: ti != 0 && tj != 0.
	case  == :
		// Both type parameters already share the same slot. Nothing to do.
		break
	case  > 0 &&  > 0:
		// Both type parameters have (possibly different) inferred types. Cannot join.
		// TODO(gri) Should we check if types are identical? Investigate.
		return false
	case  > 0:
		// Only the type parameter for x has an inferred type. Use x slot for y.
		.y.setIndex(, )
	// This case is handled like the default case.
	// case tj > 0:
	// 	// Only the type parameter for y has an inferred type. Use y slot for x.
	// 	u.x.setIndex(i, tj)
	default:
		// Neither type parameter has an inferred type. Use y slot for x
		// (or x slot for y, it doesn't matter).
		.x.setIndex(, )
	}
	return true
}

// If typ is a type parameter of d, index returns the type parameter index.
// Otherwise, the result is < 0.
func ( *tparamsList) ( Type) int {
	if ,  := .(*TypeParam);  {
		return tparamIndex(.tparams, )
	}
	return -1
}

// If tpar is a type parameter in list, tparamIndex returns the type parameter index.
// Otherwise, the result is < 0. tpar must not be nil.
func tparamIndex( []*TypeParam,  *TypeParam) int {
	// Once a type parameter is bound its index is >= 0. However, there are some
	// code paths (namely tracing and type hashing) by which it is possible to
	// arrive here with a type parameter that has not been bound, hence the check
	// for 0 <= i below.
	// TODO(rfindley): investigate a better approach for guarding against using
	// unbound type parameters.
	if  := .index; 0 <=  &&  < len() && [] ==  {
		return 
	}
	return -1
}

// setIndex sets the type slot index for the i'th type parameter
// (and all its joined parameters) to tj. The type parameter
// must have a (possibly nil) type slot associated with it.
func ( *tparamsList) (,  int) {
	 := .indices[]
	assert( != 0 &&  != 0)
	for ,  := range .indices {
		if  ==  {
			.indices[] = 
		}
	}
}

// at returns the type set for the i'th type parameter; or nil.
func ( *tparamsList) ( int) Type {
	if  := .indices[];  > 0 {
		return .unifier.types[-1]
	}
	return nil
}

// set sets the type typ for the i'th type parameter;
// typ must not be nil and it must not have been set before.
func ( *tparamsList) ( int,  Type) {
	assert( != nil)
	 := .unifier
	if traceInference {
		.tracef("%s ➞ %s", .tparams[], )
	}
	switch  := .indices[]; {
	case  < 0:
		.types[--1] = 
		.setIndex(, -)
	case  == 0:
		.types = append(.types, )
		.indices[] = len(.types)
	default:
		panic("type already set")
	}
}

// unknowns returns the number of type parameters for which no type has been set yet.
func ( *tparamsList) () int {
	 := 0
	for ,  := range .indices {
		if  <= 0 {
			++
		}
	}
	return 
}

// types returns the list of inferred types (via unification) for the type parameters
// described by d, and an index. If all types were inferred, the returned index is < 0.
// Otherwise, it is the index of the first type parameter which couldn't be inferred;
// i.e., for which list[index] is nil.
func ( *tparamsList) () ( []Type,  int) {
	 = make([]Type, len(.tparams))
	 = -1
	for  := range .tparams {
		 := .at()
		[] = 
		if  < 0 &&  == nil {
			 = 
		}
	}
	return
}

func ( *unifier) (,  Type,  *ifacePair) bool {
	return  ==  || .nify(, , )
}

// nify implements the core unification algorithm which is an
// adapted version of Checker.identical. For changes to that
// code the corresponding changes should be made here.
// Must not be called directly from outside the unifier.
func ( *unifier) (,  Type,  *ifacePair) ( bool) {
	if traceInference {
		.tracef("%s ≡ %s", , )
	}

	// Stop gap for cases where unification fails.
	if .depth >= unificationDepthLimit {
		if traceInference {
			.tracef("depth %d >= %d", .depth, unificationDepthLimit)
		}
		if panicAtUnificationDepthLimit {
			panic("unification reached recursion depth limit")
		}
		return false
	}
	.depth++
	defer func() {
		.depth--
		if traceInference && ! {
			.tracef("%s ≢ %s", , )
		}
	}()

	if !.exact {
		// If exact unification is known to fail because we attempt to
		// match a type name against an unnamed type literal, consider
		// the underlying type of the named type.
		// (We use !hasName to exclude any type with a name, including
		// basic types and type parameters; the rest are unamed types.)
		if ,  := .(*Named);  != nil && !hasName() {
			if traceInference {
				.tracef("under %s ≡ %s", , )
			}
			return .(.under(), , )
		} else if ,  := .(*Named);  != nil && !hasName() {
			if traceInference {
				.tracef("%s ≡ under %s", , )
			}
			return .(, .under(), )
		}
	}

	// Cases where at least one of x or y is a type parameter.
	switch ,  := .x.index(), .y.index(); {
	case  >= 0 &&  >= 0:
		// both x and y are type parameters
		if .join(, ) {
			return true
		}
		// both x and y have an inferred type - they must match
		return .nifyEq(.x.at(), .y.at(), )

	case  >= 0:
		// x is a type parameter, y is not
		if  := .x.at();  != nil {
			return .nifyEq(, , )
		}
		// otherwise, infer type from y
		.x.set(, )
		return true

	case  >= 0:
		// y is a type parameter, x is not
		if  := .y.at();  != nil {
			return .nifyEq(, , )
		}
		// otherwise, infer type from x
		.y.set(, )
		return true
	}

	// If we get here and x or y is a type parameter, they are type parameters
	// from outside our declaration list. Try to unify their core types, if any
	// (see issue #50755 for a test case).
	if enableCoreTypeUnification && !.exact {
		if isTypeParam() && !hasName() {
			// When considering the type parameter for unification
			// we look at the adjusted core term (adjusted core type
			// with tilde information).
			// If the adjusted core type is a named type N; the
			// corresponding core type is under(N). Since !u.exact
			// and y doesn't have a name, unification will end up
			// comparing under(N) to y, so we can just use the core
			// type instead. And we can ignore the tilde because we
			// already look at the underlying types on both sides
			// and we have known types on both sides.
			// Optimization.
			if  := coreType();  != nil {
				if traceInference {
					.tracef("core %s ≡ %s", , )
				}
				return .(, , )
			}
		} else if isTypeParam() && !hasName() {
			// see comment above
			if  := coreType();  != nil {
				if traceInference {
					.tracef("%s ≡ core %s", , )
				}
				return .(, , )
			}
		}
	}

	// For type unification, do not shortcut (x == y) for identical
	// types. Instead keep comparing them element-wise to unify the
	// matching (and equal type parameter types). A simple test case
	// where this matters is: func f[P any](a P) { f(a) } .

	switch x := .(type) {
	case *Basic:
		// Basic types are singletons except for the rune and byte
		// aliases, thus we cannot solely rely on the x == y check
		// above. See also comment in TypeName.IsAlias.
		if ,  := .(*Basic);  {
			return .kind == .kind
		}

	case *Array:
		// Two array types are identical if they have identical element types
		// and the same array length.
		if ,  := .(*Array);  {
			// If one or both array lengths are unknown (< 0) due to some error,
			// assume they are the same to avoid spurious follow-on errors.
			return (.len < 0 || .len < 0 || .len == .len) && .(.elem, .elem, )
		}

	case *Slice:
		// Two slice types are identical if they have identical element types.
		if ,  := .(*Slice);  {
			return .(.elem, .elem, )
		}

	case *Struct:
		// Two struct types are identical if they have the same sequence of fields,
		// and if corresponding fields have the same names, and identical types,
		// and identical tags. Two embedded fields are considered to have the same
		// name. Lower-case field names from different packages are always different.
		if ,  := .(*Struct);  {
			if .NumFields() == .NumFields() {
				for ,  := range .fields {
					 := .fields[]
					if .embedded != .embedded ||
						.Tag() != .Tag() ||
						!.sameId(.pkg, .name) ||
						!.(.typ, .typ, ) {
						return false
					}
				}
				return true
			}
		}

	case *Pointer:
		// Two pointer types are identical if they have identical base types.
		if ,  := .(*Pointer);  {
			return .(.base, .base, )
		}

	case *Tuple:
		// Two tuples types are identical if they have the same number of elements
		// and corresponding elements have identical types.
		if ,  := .(*Tuple);  {
			if .Len() == .Len() {
				if  != nil {
					for ,  := range .vars {
						 := .vars[]
						if !.(.typ, .typ, ) {
							return false
						}
					}
				}
				return true
			}
		}

	case *Signature:
		// Two function types are identical if they have the same number of parameters
		// and result values, corresponding parameter and result types are identical,
		// and either both functions are variadic or neither is. Parameter and result
		// names are not required to match.
		// TODO(gri) handle type parameters or document why we can ignore them.
		if ,  := .(*Signature);  {
			return .variadic == .variadic &&
				.(.params, .params, ) &&
				.(.results, .results, )
		}

	case *Interface:
		// Two interface types are identical if they have the same set of methods with
		// the same names and identical function types. Lower-case method names from
		// different packages are always different. The order of the methods is irrelevant.
		if ,  := .(*Interface);  {
			 := .typeSet()
			 := .typeSet()
			if .comparable != .comparable {
				return false
			}
			if !.terms.equal(.terms) {
				return false
			}
			 := .methods
			 := .methods
			if len() == len() {
				// Interface types are the only types where cycles can occur
				// that are not "terminated" via named types; and such cycles
				// can only be created via method parameter types that are
				// anonymous interfaces (directly or indirectly) embedding
				// the current interface. Example:
				//
				//    type T interface {
				//        m() interface{T}
				//    }
				//
				// If two such (differently named) interfaces are compared,
				// endless recursion occurs if the cycle is not detected.
				//
				// If x and y were compared before, they must be equal
				// (if they were not, the recursion would have stopped);
				// search the ifacePair stack for the same pair.
				//
				// This is a quadratic algorithm, but in practice these stacks
				// are extremely short (bounded by the nesting depth of interface
				// type declarations that recur via parameter types, an extremely
				// rare occurrence). An alternative implementation might use a
				// "visited" map, but that is probably less efficient overall.
				 := &ifacePair{, , }
				for  != nil {
					if .identical() {
						return true // same pair was compared before
					}
					 = .prev
				}
				if debug {
					assertSortedMethods()
					assertSortedMethods()
				}
				for ,  := range  {
					 := []
					if .Id() != .Id() || !.(.typ, .typ, ) {
						return false
					}
				}
				return true
			}
		}

	case *Map:
		// Two map types are identical if they have identical key and value types.
		if ,  := .(*Map);  {
			return .(.key, .key, ) && .(.elem, .elem, )
		}

	case *Chan:
		// Two channel types are identical if they have identical value types.
		if ,  := .(*Chan);  {
			return (!.exact || .dir == .dir) && .(.elem, .elem, )
		}

	case *Named:
		// TODO(gri) This code differs now from the parallel code in Checker.identical. Investigate.
		if ,  := .(*Named);  {
			 := .targs.list()
			 := .targs.list()

			if len() != len() {
				return false
			}

			// TODO(gri) This is not always correct: two types may have the same names
			//           in the same package if one of them is nested in a function.
			//           Extremely unlikely but we need an always correct solution.
			if .obj.pkg == .obj.pkg && .obj.name == .obj.name {
				for ,  := range  {
					if !.(, [], ) {
						return false
					}
				}
				return true
			}
		}

	case *TypeParam:
		// Two type parameters (which are not part of the type parameters of the
		// enclosing type as those are handled in the beginning of this function)
		// are identical if they originate in the same declaration.
		return  == 

	case nil:
		// avoid a crash in case of nil type

	default:
		panic(sprintf(nil, nil, true, "u.nify(%s, %s), u.x.tparams = %s", , , .x.tparams))
	}

	return false
}