// 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 types2

import (
	"bytes"
	"fmt"
	"strings"
)

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.
	// If disabled, a recursion depth overflow results in a (quiet)
	// unification failure.
	panicAtUnificationDepthLimit = true

	// 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

	// If exactUnification is set, unification requires (named) types
	// to match exactly. If it is not set, the underlying types are
	// considered when unification is known to fail otherwise.
	exactUnification = false
)

// A unifier maintains a list of type parameters and
// corresponding types inferred for each type parameter.
// A unifier is created by calling newUnifier.
type unifier struct {
	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(indices) == len(tparams)
	types   []Type // inferred types, shared by x and y
	depth   int    // recursion depth during unification
}

// newUnifier returns a new unifier initialized 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 newUnifier(tparams []*TypeParam) *unifier {
	if debug {
		for i, tpar := range tparams {
			assert(i == tpar.index)
		}
	}
	return &unifier{
		tparams: tparams,
		indices: make([]int, len(tparams)),
	}
}

// unify attempts to unify x and y and reports whether it succeeded.
// As a side-effect, types may be inferred for type parameters.
func (u *unifier) unify(x, y Type) bool {
	return u.nify(x, y, nil)
}

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

// String returns a string representation of the mapping from
// type parameters to types.
func (u *unifier) String() string {
	var buf bytes.Buffer
	w := newTypeWriter(&buf, nil)
	w.byte('[')
	for i, tpar := range u.tparams {
		if i > 0 {
			w.string(", ")
		}
		w.typ(tpar)
		w.string(": ")
		w.typ(u.at(i))
	}
	w.byte(']')
	return buf.String()
}

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

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

// If typ is a type parameter recorded with u, index returns the type parameter index.
// Otherwise, the result is < 0.
func (u *unifier) index(typ Type) int {
	if tpar, ok := typ.(*TypeParam); ok {
		return tparamIndex(u.tparams, tpar)
	}
	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 (u *unifier) setIndex(i, tj int) {
	ti := u.indices[i]
	assert(ti != 0 && tj != 0)
	for k, tk := range u.indices {
		if tk == ti {
			u.indices[k] = tj
		}
	}
}

// at returns the type set for the i'th type parameter; or nil.
func (u *unifier) at(i int) Type {
	if ti := u.indices[i]; ti > 0 {
		return u.types[ti-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 (u *unifier) set(i int, typ Type) {
	assert(typ != nil)
	if traceInference {
		u.tracef("%s ➞ %s", u.tparams[i], typ)
	}
	switch ti := u.indices[i]; {
	case ti < 0:
		u.types[-ti-1] = typ
		u.setIndex(i, -ti)
	case ti == 0:
		u.types = append(u.types, typ)
		u.indices[i] = len(u.types)
	default:
		panic("type already set")
	}
}

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

// inferred returns the list of inferred types (via unification) for the type parameters
// recorded with u, 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 (u *unifier) inferred() (list []Type, index int) {
	list = make([]Type, len(u.tparams))
	index = -1
	for i := range u.tparams {
		t := u.at(i)
		list[i] = t
		if index < 0 && t == nil {
			index = i
		}
	}
	return
}

func (u *unifier) nifyEq(x, y Type, p *ifacePair) bool {
	return x == y || u.nify(x, y, p)
}

// 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 (u *unifier) nify(x, y Type, p *ifacePair) (result bool) {
	if traceInference {
		u.tracef("%s ≡ %s", x, y)
	}

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

	if !exactUnification {
		// 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 nx, _ := x.(*Named); nx != nil && !hasName(y) {
			if traceInference {
				u.tracef("under %s ≡ %s", nx, y)
			}
			return u.nify(nx.under(), y, p)
		} else if ny, _ := y.(*Named); ny != nil && !hasName(x) {
			if traceInference {
				u.tracef("%s ≡ under %s", x, ny)
			}
			return u.nify(x, ny.under(), p)
		}
	}

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

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

	case j >= 0:
		// y is a type parameter, x is not
		if ty := u.at(j); ty != nil {
			return u.nifyEq(x, ty, p)
		}
		// otherwise, infer type from x
		u.set(j, x)
		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 go.dev/issue/50755 for a test case).
	if enableCoreTypeUnification && !exactUnification {
		if isTypeParam(x) && !hasName(y) {
			// 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 !exactUnification
			// 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 cx := coreType(x); cx != nil {
				if traceInference {
					u.tracef("core %s ≡ %s", x, y)
				}
				return u.nify(cx, y, p)
			}
		} else if isTypeParam(y) && !hasName(x) {
			// see comment above
			if cy := coreType(y); cy != nil {
				if traceInference {
					u.tracef("%s ≡ core %s", x, y)
				}
				return u.nify(x, cy, p)
			}
		}
	}

	// 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 := 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 y, ok := y.(*Basic); ok {
			return x.kind == y.kind
		}

	case *Array:
		// Two array types are identical if they have identical element types
		// and the same array length.
		if y, ok := y.(*Array); ok {
			// 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 (x.len < 0 || y.len < 0 || x.len == y.len) && u.nify(x.elem, y.elem, p)
		}

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

	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 y, ok := y.(*Struct); ok {
			if x.NumFields() == y.NumFields() {
				for i, f := range x.fields {
					g := y.fields[i]
					if f.embedded != g.embedded ||
						x.Tag(i) != y.Tag(i) ||
						!f.sameId(g.pkg, g.name) ||
						!u.nify(f.typ, g.typ, p) {
						return false
					}
				}
				return true
			}
		}

	case *Pointer:
		// Two pointer types are identical if they have identical base types.
		if y, ok := y.(*Pointer); ok {
			return u.nify(x.base, y.base, p)
		}

	case *Tuple:
		// Two tuples types are identical if they have the same number of elements
		// and corresponding elements have identical types.
		if y, ok := y.(*Tuple); ok {
			if x.Len() == y.Len() {
				if x != nil {
					for i, v := range x.vars {
						w := y.vars[i]
						if !u.nify(v.typ, w.typ, p) {
							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 y, ok := y.(*Signature); ok {
			return x.variadic == y.variadic &&
				u.nify(x.params, y.params, p) &&
				u.nify(x.results, y.results, p)
		}

	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 y, ok := y.(*Interface); ok {
			xset := x.typeSet()
			yset := y.typeSet()
			if xset.comparable != yset.comparable {
				return false
			}
			if !xset.terms.equal(yset.terms) {
				return false
			}
			a := xset.methods
			b := yset.methods
			if len(a) == len(b) {
				// 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.
				q := &ifacePair{x, y, p}
				for p != nil {
					if p.identical(q) {
						return true // same pair was compared before
					}
					p = p.prev
				}
				if debug {
					assertSortedMethods(a)
					assertSortedMethods(b)
				}
				for i, f := range a {
					g := b[i]
					if f.Id() != g.Id() || !u.nify(f.typ, g.typ, q) {
						return false
					}
				}
				return true
			}
		}

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

	case *Chan:
		// Two channel types are identical if they have identical value types.
		if y, ok := y.(*Chan); ok {
			return (!exactUnification || x.dir == y.dir) && u.nify(x.elem, y.elem, p)
		}

	case *Named:
		// TODO(gri) This code differs now from the parallel code in Checker.identical. Investigate.
		if y, ok := y.(*Named); ok {
			xargs := x.TypeArgs().list()
			yargs := y.TypeArgs().list()

			if len(xargs) != len(yargs) {
				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 x.obj.pkg == y.obj.pkg && x.obj.name == y.obj.name {
				for i, x := range xargs {
					if !u.nify(x, yargs[i], p) {
						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 x == y

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

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

	return false
}