// license that can be found in the LICENSE file.
// This file implements type unification.
-
-package types2
-
-import "bytes"
-
-// 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) }
+// Type unification attempts to make two types x and y structurally
+// equivalent by determining the types for a given list of (bound)
+// type parameters which may occur within x and y. If x and y are
+// structurally different (say []T vs chan T), or conflicting
+// types are determined for type parameters, unification fails.
+// If unification succeeds, as a side-effect, the types of the
+// bound type parameters may be determined.
//
-// 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.
+// Unification typically requires multiple calls u.unify(x, y) to
+// a given unifier u, with various combinations of types x and y.
+// In each call, additional type parameter types may be determined
+// as a side effect and recorded in u.
+// If a call fails (returns false), unification fails.
//
-// For bidirection 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.
-
-// A unifier maintains the current type parameters for x and y
-// and the respective types inferred for each type parameter.
+// In the unification context, structural equivalence of two types
+// ignores the difference between a defined type and its underlying
+// type if one type is a defined type and the other one is not.
+// It also ignores the difference between an (external, unbound)
+// type parameter and its core type.
+// If two types are not structurally equivalent, they cannot be Go
+// identical types. On the other hand, if they are structurally
+// equivalent, they may be Go identical or at least assignable, or
+// they may be in the type set of a constraint.
+// Whether they indeed are identical or assignable is determined
+// upon instantiation and function argument passing.
+
+package types2
+
+import (
+ "bytes"
+ "fmt"
+ "sort"
+ "strings"
+)
+
+const (
+ // Upper limit for recursion depth. Used to catch infinite recursions
+ // due to implementation issues (e.g., see issues go.dev/issue/48619, go.dev/issue/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
+)
+
+// 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 {
- check *Checker
- exact bool
- x, y tparamsList // x and y must initialized via tparamsList.init
- types []Type // inferred types, shared by x and y
+ // handles maps each type parameter to its inferred type through
+ // an indirection *Type called (inferred type) "handle".
+ // Initially, each type parameter has its own, separate handle,
+ // with a nil (i.e., not yet inferred) type.
+ // After a type parameter P is unified with a type parameter Q,
+ // P and Q share the same handle (and thus type). This ensures
+ // that inferring the type for a given type parameter P will
+ // automatically infer the same type for all other parameters
+ // unified (joined) with P.
+ handles map[*TypeParam]*Type
+ depth int // recursion depth during unification
+ enableInterfaceInference bool // use shared methods for better inference
+}
+
+// newUnifier returns a new unifier initialized with the given type parameter
+// and corresponding type argument lists. The type argument list may be shorter
+// than the type parameter list, and it may contain nil types. Matching type
+// parameters and arguments must have the same index.
+func newUnifier(tparams []*TypeParam, targs []Type, enableInterfaceInference bool) *unifier {
+ assert(len(tparams) >= len(targs))
+ handles := make(map[*TypeParam]*Type, len(tparams))
+ // Allocate all handles up-front: in a correct program, all type parameters
+ // must be resolved and thus eventually will get a handle.
+ // Also, sharing of handles caused by unified type parameters is rare and
+ // so it's ok to not optimize for that case (and delay handle allocation).
+ for i, x := range tparams {
+ var t Type
+ if i < len(targs) {
+ t = targs[i]
+ }
+ handles[x] = &t
+ }
+ return &unifier{handles, 0, enableInterfaceInference}
}
-// 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.
-func newUnifier(check *Checker, exact bool) *unifier {
- u := &unifier{check: check, exact: exact}
- u.x.unifier = u
- u.y.unifier = u
- return u
+// unifyMode controls the behavior of the unifier.
+type unifyMode uint
+
+const (
+ // If assign is set, we are unifying types involved in an assignment:
+ // they may match inexactly at the top, but element types must match
+ // exactly.
+ assign unifyMode = 1 << iota
+
+ // If exact is set, types unify if they are identical (or can be
+ // made identical with suitable arguments for type parameters).
+ // Otherwise, a named type and a type literal unify if their
+ // underlying types unify, channel directions are ignored, and
+ // if there is an interface, the other type must implement the
+ // interface.
+ exact
+)
+
+func (m unifyMode) String() string {
+ switch m {
+ case 0:
+ return "inexact"
+ case assign:
+ return "assign"
+ case exact:
+ return "exact"
+ case assign | exact:
+ return "assign, exact"
+ }
+ return fmt.Sprintf("mode %d", m)
}
// unify attempts to unify x and y and reports whether it succeeded.
-func (u *unifier) unify(x, y Type) bool {
- return u.nify(x, y, nil)
+// As a side-effect, types may be inferred for type parameters.
+// The mode parameter controls how types are compared.
+func (u *unifier) unify(x, y Type, mode unifyMode) bool {
+ return u.nify(x, y, mode, nil)
}
-// A tparamsList describes a list of type parameters and the types inferred for them.
-type tparamsList struct {
- unifier *unifier
- tparams []*TypeName
- // 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)
+func (u *unifier) tracef(format string, args ...interface{}) {
+ fmt.Println(strings.Repeat(". ", u.depth) + sprintf(nil, true, format, args...))
}
-// String returns a string representation for a tparamsList. For debugging.
-func (d *tparamsList) String() string {
+// String returns a string representation of the current mapping
+// from type parameters to types.
+func (u *unifier) String() string {
+ // sort type parameters for reproducible strings
+ tparams := make(typeParamsById, len(u.handles))
+ i := 0
+ for tpar := range u.handles {
+ tparams[i] = tpar
+ i++
+ }
+ sort.Sort(tparams)
+
var buf bytes.Buffer
- buf.WriteByte('[')
- for i, tname := range d.tparams {
+ w := newTypeWriter(&buf, nil)
+ w.byte('[')
+ for i, x := range tparams {
if i > 0 {
- buf.WriteString(", ")
+ w.string(", ")
}
- writeType(&buf, tname.typ, nil, nil)
- buf.WriteString(": ")
- writeType(&buf, d.at(i), nil, nil)
+ w.typ(x)
+ w.string(": ")
+ w.typ(u.at(x))
}
- buf.WriteByte(']')
+ w.byte(']')
return buf.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 (d *tparamsList) init(tparams []*TypeName) {
- if len(tparams) == 0 {
- return
- }
- if debug {
- for i, tpar := range tparams {
- assert(i == tpar.typ.(*TypeParam).index)
- }
- }
- d.tparams = tparams
- d.indices = make([]int, len(tparams))
-}
+type typeParamsById []*TypeParam
-// 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 return false.
-func (u *unifier) join(i, j int) bool {
- ti := u.x.indices[i]
- tj := u.y.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.x.indices[i] = -len(u.types)
- u.y.indices[j] = -len(u.types)
- case ti == 0:
- // The type parameter for x has no type slot yet. Use slot of y.
- u.x.indices[i] = tj
- case tj == 0:
- // The type parameter for y has no type slot yet. Use slot of x.
- u.y.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:
+func (s typeParamsById) Len() int { return len(s) }
+func (s typeParamsById) Less(i, j int) bool { return s[i].id < s[j].id }
+func (s typeParamsById) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
+
+// join unifies the given type parameters x and y.
+// 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(x, y *TypeParam) bool {
+ if traceInference {
+ u.tracef("%s ⇄ %s", x, y)
+ }
+ switch hx, hy := u.handles[x], u.handles[y]; {
+ case hx == hy:
+ // Both type parameters already share the same handle. Nothing to do.
+ case *hx != nil && *hy != nil:
// Both type parameters have (possibly different) inferred types. Cannot join.
return false
- case ti > 0:
- // Only the type parameter for x has an inferred type. Use x slot for y.
- u.y.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.x.setIndex(i, tj)
+ case *hx != nil:
+ // Only type parameter x has an inferred type. Use handle of x.
+ u.setHandle(y, hx)
+ // This case is treated like the default case.
+ // case *hy != nil:
+ // // Only type parameter y has an inferred type. Use handle of y.
+ // u.setHandle(x, hy)
default:
- // Neither type parameter has an inferred type. Use y slot for x
- // (or x slot for y, it doesn't matter).
- u.x.setIndex(i, tj)
+ // Neither type parameter has an inferred type. Use handle of y.
+ u.setHandle(x, hy)
}
return true
}
-// If typ is a type parameter of d, index returns the type parameter index.
-// Otherwise, the result is < 0.
-func (d *tparamsList) index(typ Type) int {
- if t, ok := typ.(*TypeParam); ok {
- if i := t.index; i < len(d.tparams) && d.tparams[i].typ == t {
- return i
+// asTypeParam returns x.(*TypeParam) if x is a type parameter recorded with u.
+// Otherwise, the result is nil.
+func (u *unifier) asTypeParam(x Type) *TypeParam {
+ if x, _ := x.(*TypeParam); x != nil {
+ if _, found := u.handles[x]; found {
+ return x
}
}
- return -1
+ return nil
}
-// 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 (d *tparamsList) setIndex(i, tj int) {
- ti := d.indices[i]
- assert(ti != 0 && tj != 0)
- for k, tk := range d.indices {
- if tk == ti {
- d.indices[k] = tj
+// setHandle sets the handle for type parameter x
+// (and all its joined type parameters) to h.
+func (u *unifier) setHandle(x *TypeParam, h *Type) {
+ hx := u.handles[x]
+ assert(hx != nil)
+ for y, hy := range u.handles {
+ if hy == hx {
+ u.handles[y] = h
}
}
}
-// at returns the type set for the i'th type parameter; or nil.
-func (d *tparamsList) at(i int) Type {
- if ti := d.indices[i]; ti > 0 {
- return d.unifier.types[ti-1]
- }
- return nil
+// at returns the (possibly nil) type for type parameter x.
+func (u *unifier) at(x *TypeParam) Type {
+ return *u.handles[x]
}
-// 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 (d *tparamsList) set(i int, typ Type) {
- assert(typ != nil)
- u := d.unifier
- switch ti := d.indices[i]; {
- case ti < 0:
- u.types[-ti-1] = typ
- d.setIndex(i, -ti)
- case ti == 0:
- u.types = append(u.types, typ)
- d.indices[i] = len(u.types)
- default:
- panic("type already set")
+// set sets the type t for type parameter x;
+// t must not be nil.
+func (u *unifier) set(x *TypeParam, t Type) {
+ assert(t != nil)
+ if traceInference {
+ u.tracef("%s ➞ %s", x, t)
}
+ *u.handles[x] = t
}
-// 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 (d *tparamsList) types() (list []Type, index int) {
- list = make([]Type, len(d.tparams))
- index = -1
- for i := range d.tparams {
- t := d.at(i)
- list[i] = t
- if index < 0 && t == nil {
- index = i
+// unknowns returns the number of type parameters for which no type has been set yet.
+func (u *unifier) unknowns() int {
+ n := 0
+ for _, h := range u.handles {
+ if *h == nil {
+ n++
}
}
- return
+ return n
+}
+
+// inferred returns the list of inferred types for the given type parameter list.
+// The result is never nil and has the same length as tparams; result types that
+// could not be inferred are nil. Corresponding type parameters and result types
+// have identical indices.
+func (u *unifier) inferred(tparams []*TypeParam) []Type {
+ list := make([]Type, len(tparams))
+ for i, x := range tparams {
+ list[i] = u.at(x)
+ }
+ return list
}
-func (u *unifier) nifyEq(x, y Type, p *ifacePair) bool {
- return x == y || u.nify(x, y, p)
+// asInterface returns the underlying type of x as an interface if
+// it is a non-type parameter interface. Otherwise it returns nil.
+func asInterface(x Type) (i *Interface) {
+ if _, ok := x.(*TypeParam); !ok {
+ i, _ = under(x).(*Interface)
+ }
+ return i
}
// nify implements the core unification algorithm which is an
-// adapted version of Checker.identical0. For changes to that
+// 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) bool {
- // types must be expanded for comparison
- x = expand(x)
- y = expand(y)
-
- if !u.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.
- // (Subtle: We use isNamed to include any type with a name (incl.
- // basic types and type parameters. We use asNamed because we only
- // want *Named types.)
- switch {
- case !isNamed(x) && y != nil && asNamed(y) != nil:
- return u.nify(x, under(y), p)
- case x != nil && asNamed(x) != nil && !isNamed(y):
- return u.nify(under(x), y, p)
+func (u *unifier) nify(x, y Type, mode unifyMode, p *ifacePair) (result bool) {
+ u.depth++
+ if traceInference {
+ u.tracef("%s ≡ %s\t// %s", x, y, mode)
+ }
+ defer func() {
+ if traceInference && !result {
+ u.tracef("%s ≢ %s", x, y)
}
+ u.depth--
+ }()
+
+ x = Unalias(x)
+ y = Unalias(y)
+
+ // nothing to do if x == y
+ if x == y {
+ return true
}
- // Cases where at least one of x or y is a type parameter.
- switch i, j := u.x.index(x), u.y.index(y); {
- case i >= 0 && j >= 0:
+ // 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
+ }
+
+ // Unification is symmetric, so we can swap the operands.
+ // Ensure that if we have at least one
+ // - defined type, make sure one is in y
+ // - type parameter recorded with u, make sure one is in x
+ if asNamed(x) != nil || u.asTypeParam(y) != nil {
+ if traceInference {
+ u.tracef("%s ≡ %s\t// swap", y, x)
+ }
+ x, y = y, x
+ }
+
+ // Unification will fail if we match a defined type against a type literal.
+ // If we are matching types in an assignment, at the top-level, types with
+ // the same type structure are permitted as long as at least one of them
+ // is not a defined type. To accommodate for that possibility, we continue
+ // unification with the underlying type of a defined type if the other type
+ // is a type literal. This is controlled by the exact unification mode.
+ // We also continue if the other type is a basic type because basic types
+ // are valid underlying types and may appear as core types of type constraints.
+ // If we exclude them, inferred defined types for type parameters may not
+ // match against the core types of their constraints (even though they might
+ // correctly match against some of the types in the constraint's type set).
+ // Finally, if unification (incorrectly) succeeds by matching the underlying
+ // type of a defined type against a basic type (because we include basic types
+ // as type literals here), and if that leads to an incorrectly inferred type,
+ // we will fail at function instantiation or argument assignment time.
+ //
+ // If we have at least one defined type, there is one in y.
+ if ny := asNamed(y); mode&exact == 0 && ny != nil && isTypeLit(x) && !(u.enableInterfaceInference && IsInterface(x)) {
+ if traceInference {
+ u.tracef("%s ≡ under %s", x, ny)
+ }
+ y = ny.under()
+ // Per the spec, a defined type cannot have an underlying type
+ // that is a type parameter.
+ assert(!isTypeParam(y))
+ // x and y may be identical now
+ if x == y {
+ return true
+ }
+ }
+
+ // Cases where at least one of x or y is a type parameter recorded with u.
+ // If we have at least one type parameter, there is one in x.
+ // If we have exactly one type parameter, because it is in x,
+ // isTypeLit(x) is false and y was not changed above. In other
+ // words, if y was a defined type, it is still a defined type
+ // (relevant for the logic below).
+ switch px, py := u.asTypeParam(x), u.asTypeParam(y); {
+ case px != nil && py != nil:
// both x and y are type parameters
- if u.join(i, j) {
+ if u.join(px, py) {
return true
}
// both x and y have an inferred type - they must match
- return u.nifyEq(u.x.at(i), u.y.at(j), p)
+ return u.nify(u.at(px), u.at(py), mode, p)
- case i >= 0:
+ case px != nil:
// x is a type parameter, y is not
- if tx := u.x.at(i); tx != nil {
- return u.nifyEq(tx, y, p)
+ if x := u.at(px); x != nil {
+ // x has an inferred type which must match y
+ if u.nify(x, y, mode, p) {
+ // We have a match, possibly through underlying types.
+ xi := asInterface(x)
+ yi := asInterface(y)
+ xn := asNamed(x) != nil
+ yn := asNamed(y) != nil
+ // If we have two interfaces, what to do depends on
+ // whether they are named and their method sets.
+ if xi != nil && yi != nil {
+ // Both types are interfaces.
+ // If both types are defined types, they must be identical
+ // because unification doesn't know which type has the "right" name.
+ if xn && yn {
+ return Identical(x, y)
+ }
+ // In all other cases, the method sets must match.
+ // The types unified so we know that corresponding methods
+ // match and we can simply compare the number of methods.
+ // TODO(gri) We may be able to relax this rule and select
+ // the more general interface. But if one of them is a defined
+ // type, it's not clear how to choose and whether we introduce
+ // an order dependency or not. Requiring the same method set
+ // is conservative.
+ if len(xi.typeSet().methods) != len(yi.typeSet().methods) {
+ return false
+ }
+ } else if xi != nil || yi != nil {
+ // One but not both of them are interfaces.
+ // In this case, either x or y could be viable matches for the corresponding
+ // type parameter, which means choosing either introduces an order dependence.
+ // Therefore, we must fail unification (go.dev/issue/60933).
+ return false
+ }
+ // If we have inexact unification and one of x or y is a defined type, select the
+ // defined type. This ensures that in a series of types, all matching against the
+ // same type parameter, we infer a defined type if there is one, independent of
+ // order. Type inference or assignment may fail, which is ok.
+ // Selecting a defined type, if any, ensures that we don't lose the type name;
+ // and since we have inexact unification, a value of equally named or matching
+ // undefined type remains assignable (go.dev/issue/43056).
+ //
+ // Similarly, if we have inexact unification and there are no defined types but
+ // channel types, select a directed channel, if any. This ensures that in a series
+ // of unnamed types, all matching against the same type parameter, we infer the
+ // directed channel if there is one, independent of order.
+ // Selecting a directional channel, if any, ensures that a value of another
+ // inexactly unifying channel type remains assignable (go.dev/issue/62157).
+ //
+ // If we have multiple defined channel types, they are either identical or we
+ // have assignment conflicts, so we can ignore directionality in this case.
+ //
+ // If we have defined and literal channel types, a defined type wins to avoid
+ // order dependencies.
+ if mode&exact == 0 {
+ switch {
+ case xn:
+ // x is a defined type: nothing to do.
+ case yn:
+ // x is not a defined type and y is a defined type: select y.
+ u.set(px, y)
+ default:
+ // Neither x nor y are defined types.
+ if yc, _ := under(y).(*Chan); yc != nil && yc.dir != SendRecv {
+ // y is a directed channel type: select y.
+ u.set(px, y)
+ }
+ }
+ }
+ return true
+ }
+ return false
}
// otherwise, infer type from y
- u.x.set(i, y)
+ u.set(px, y)
return true
+ }
- case j >= 0:
- // y is a type parameter, x is not
- if ty := u.y.at(j); ty != nil {
- return u.nifyEq(x, ty, p)
+ // x != y if we get here
+ assert(x != y)
+
+ // If u.EnableInterfaceInference is set and we don't require exact unification,
+ // if both types are interfaces, one interface must have a subset of the
+ // methods of the other and corresponding method signatures must unify.
+ // If only one type is an interface, all its methods must be present in the
+ // other type and corresponding method signatures must unify.
+ if u.enableInterfaceInference && mode&exact == 0 {
+ // One or both interfaces may be defined types.
+ // Look under the name, but not under type parameters (go.dev/issue/60564).
+ xi := asInterface(x)
+ yi := asInterface(y)
+ // If we have two interfaces, check the type terms for equivalence,
+ // and unify common methods if possible.
+ if xi != nil && yi != nil {
+ xset := xi.typeSet()
+ yset := yi.typeSet()
+ if xset.comparable != yset.comparable {
+ return false
+ }
+ // For now we require terms to be equal.
+ // We should be able to relax this as well, eventually.
+ if !xset.terms.equal(yset.terms) {
+ return false
+ }
+ // 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{xi, yi, p}
+ for p != nil {
+ if p.identical(q) {
+ return true // same pair was compared before
+ }
+ p = p.prev
+ }
+ // The method set of x must be a subset of the method set
+ // of y or vice versa, and the common methods must unify.
+ xmethods := xset.methods
+ ymethods := yset.methods
+ // The smaller method set must be the subset, if it exists.
+ if len(xmethods) > len(ymethods) {
+ xmethods, ymethods = ymethods, xmethods
+ }
+ // len(xmethods) <= len(ymethods)
+ // Collect the ymethods in a map for quick lookup.
+ ymap := make(map[string]*Func, len(ymethods))
+ for _, ym := range ymethods {
+ ymap[ym.Id()] = ym
+ }
+ // All xmethods must exist in ymethods and corresponding signatures must unify.
+ for _, xm := range xmethods {
+ if ym := ymap[xm.Id()]; ym == nil || !u.nify(xm.typ, ym.typ, exact, p) {
+ return false
+ }
+ }
+ return true
+ }
+
+ // We don't have two interfaces. If we have one, make sure it's in xi.
+ if yi != nil {
+ xi = yi
+ y = x
+ }
+
+ // If we have one interface, at a minimum each of the interface methods
+ // must be implemented and thus unify with a corresponding method from
+ // the non-interface type, otherwise unification fails.
+ if xi != nil {
+ // All xi methods must exist in y and corresponding signatures must unify.
+ xmethods := xi.typeSet().methods
+ for _, xm := range xmethods {
+ obj, _, _ := LookupFieldOrMethod(y, false, xm.pkg, xm.name)
+ if ym, _ := obj.(*Func); ym == nil || !u.nify(xm.typ, ym.typ, exact, p) {
+ return false
+ }
+ }
+ return true
}
- // otherwise, infer type from x
- u.y.set(j, x)
- return true
}
- // 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) } .
+ // Unless we have exact unification, neither x nor y are interfaces now.
+ // Except for unbound type parameters (see below), x and y must be structurally
+ // equivalent to unify.
+
+ // If we get here and x or y is a type parameter, they are unbound
+ // (not recorded with the unifier).
+ // Ensure that if we have at least one type parameter, it is in x
+ // (the earlier swap checks for _recorded_ type parameters only).
+ // This ensures that the switch switches on the type parameter.
+ //
+ // TODO(gri) Factor out type parameter handling from the switch.
+ if isTypeParam(y) {
+ if traceInference {
+ u.tracef("%s ≡ %s\t// swap", y, x)
+ }
+ x, y = y, x
+ }
+
+ // Type elements (array, slice, etc. elements) use emode for unification.
+ // Element types must match exactly if the types are used in an assignment.
+ emode := mode
+ if mode&assign != 0 {
+ emode |= exact
+ }
switch x := x.(type) {
case *Basic:
}
case *Array:
- // Two array types are identical if they have identical element types
- // and the same array length.
+ // Two array types unify if they have the same array length
+ // and their element types unify.
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)
+ return (x.len < 0 || y.len < 0 || x.len == y.len) && u.nify(x.elem, y.elem, emode, p)
}
case *Slice:
- // Two slice types are identical if they have identical element types.
+ // Two slice types unify if their element types unify.
if y, ok := y.(*Slice); ok {
- return u.nify(x.elem, y.elem, p)
+ return u.nify(x.elem, y.elem, emode, 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
+ // Two struct types unify if they have the same sequence of fields,
+ // and if corresponding fields have the same names, their (field) types unify,
+ // and they have 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() {
if f.embedded != g.embedded ||
x.Tag(i) != y.Tag(i) ||
!f.sameId(g.pkg, g.name) ||
- !u.nify(f.typ, g.typ, p) {
+ !u.nify(f.typ, g.typ, emode, p) {
return false
}
}
}
case *Pointer:
- // Two pointer types are identical if they have identical base types.
+ // Two pointer types unify if their base types unify.
if y, ok := y.(*Pointer); ok {
- return u.nify(x.base, y.base, p)
+ return u.nify(x.base, y.base, emode, p)
}
case *Tuple:
- // Two tuples types are identical if they have the same number of elements
- // and corresponding elements have identical types.
+ // Two tuples types unify if they have the same number of elements
+ // and the types of corresponding elements unify.
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) {
+ if !u.nify(v.typ, w.typ, mode, p) {
return false
}
}
}
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.
+ // Two function types unify if they have the same number of parameters
+ // and result values, corresponding parameter and result types unify,
+ // 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)
+ u.nify(x.params, y.params, emode, p) &&
+ u.nify(x.results, y.results, emode, p)
}
- case *Union:
- // This should not happen with the current internal use of union types.
- panic("type inference across union types not implemented")
-
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.
+ assert(!u.enableInterfaceInference || mode&exact != 0) // handled before this switch
+
+ // Two interface types unify if they have the same set of methods with
+ // the same names, and corresponding function types unify.
+ // Lower-case method names from different packages are always different.
+ // The order of the methods is irrelevant.
if y, ok := y.(*Interface); ok {
- // If identical0 is called (indirectly) via an external API entry point
- // (such as Identical, IdenticalIgnoreTags, etc.), check is nil. But in
- // that case, interfaces are expected to be complete and lazy completion
- // here is not needed.
- if u.check != nil {
- u.check.completeInterface(nopos, x)
- u.check.completeInterface(nopos, y)
+ xset := x.typeSet()
+ yset := y.typeSet()
+ if xset.comparable != yset.comparable {
+ return false
+ }
+ if !xset.terms.equal(yset.terms) {
+ return false
}
- a := x.allMethods
- b := y.allMethods
+ 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
}
for i, f := range a {
g := b[i]
- if f.Id() != g.Id() || !u.nify(f.typ, g.typ, q) {
+ if f.Id() != g.Id() || !u.nify(f.typ, g.typ, exact, q) {
return false
}
}
}
case *Map:
- // Two map types are identical if they have identical key and value types.
+ // Two map types unify if their key and value types unify.
if y, ok := y.(*Map); ok {
- return u.nify(x.key, y.key, p) && u.nify(x.elem, y.elem, p)
+ return u.nify(x.key, y.key, emode, p) && u.nify(x.elem, y.elem, emode, p)
}
case *Chan:
- // Two channel types are identical if they have identical value types.
+ // Two channel types unify if their value types unify
+ // and if they have the same direction.
+ // The channel direction is ignored for inexact unification.
if y, ok := y.(*Chan); ok {
- return (!u.exact || x.dir == y.dir) && u.nify(x.elem, y.elem, p)
+ return (mode&exact == 0 || x.dir == y.dir) && u.nify(x.elem, y.elem, emode, p)
}
case *Named:
- // Two named types are identical if their type names originate
- // in the same type declaration.
- // if y, ok := y.(*Named); ok {
- // return x.obj == y.obj
- // }
- if y, ok := y.(*Named); ok {
- // 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 {
- assert(len(x.targs) == len(y.targs))
- for i, x := range x.targs {
- if !u.nify(x, y.targs[i], p) {
- return false
- }
+ // Two named types unify if their type names originate in the same type declaration.
+ // If they are instantiated, their type argument lists must unify.
+ if y := asNamed(y); y != nil {
+ // Check type arguments before origins so they unify
+ // even if the origins don't match; for better error
+ // messages (see go.dev/issue/53692).
+ xargs := x.TypeArgs().list()
+ yargs := y.TypeArgs().list()
+ if len(xargs) != len(yargs) {
+ return false
+ }
+ for i, xarg := range xargs {
+ if !u.nify(xarg, yargs[i], mode, p) {
+ return false
}
- return true
}
+ return identicalOrigin(x, y)
}
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 *instance:
- // unreachable since types are expanded
+ // x must be an unbound type parameter (see comment above).
+ if debug {
+ assert(u.asTypeParam(x) == nil)
+ }
+ // By definition, a valid type argument must be in the type set of
+ // the respective type constraint. Therefore, the type argument's
+ // underlying type must be in the set of underlying types of that
+ // constraint. If there is a single such underlying type, it's the
+ // constraint's core type. It must match the type argument's under-
+ // lying type, irrespective of whether the actual type argument,
+ // which may be a defined type, is actually in the type set (that
+ // will be determined at instantiation time).
+ // Thus, if we have the core type of an unbound type parameter,
+ // we know the structure of the possible types satisfying such
+ // parameters. Use that core type for further unification
+ // (see go.dev/issue/50755 for a test case).
+ if enableCoreTypeUnification {
+ // Because the core type is always an underlying type,
+ // unification will take care of matching against a
+ // defined or literal type automatically.
+ // If y is also an unbound type parameter, we will end
+ // up here again with x and y swapped, so we don't
+ // need to take care of that case separately.
+ if cx := coreType(x); cx != nil {
+ if traceInference {
+ u.tracef("core %s ≡ %s", x, y)
+ }
+ // If y is a defined type, it may not match against cx which
+ // is an underlying type (incl. int, string, etc.). Use assign
+ // mode here so that the unifier automatically takes under(y)
+ // if necessary.
+ return u.nify(cx, y, assign, p)
+ }
+ }
+ // x != y and there's nothing to do
case nil:
// avoid a crash in case of nil type
default:
- u.check.dump("### u.nify(%s, %s), u.x.tparams = %s", x, y, u.x.tparams)
- unreachable()
+ panic(sprintf(nil, true, "u.nify(%s, %s, %d)", x, y, mode))
}
return false