// Whether to panic when unificationDepthLimit is reached.
// If disabled, a recursion depth overflow results in a (quiet)
// unification failure.
- panicAtUnificationDepthLimit = false // go.dev/issue/59740
+ panicAtUnificationDepthLimit = true
// If enableCoreTypeUnification is set, unification will consider
// the core types, if any, of non-local (unbound) type parameters.
// corresponding types inferred for each type parameter.
// A unifier is created by calling newUnifier.
type unifier struct {
- check *Checker
// 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,
// 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
+ 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 (check *Checker) newUnifier(tparams []*TypeParam, targs []Type) *unifier {
+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
}
handles[x] = &t
}
- return &unifier{check, handles, 0}
+ return &unifier{handles, 0, enableInterfaceInference}
+}
+
+// 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.
// 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)
+// 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)
}
func (u *unifier) tracef(format string, args ...interface{}) {
return list
}
+// 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.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) {
+func (u *unifier) nify(x, y Type, mode unifyMode, p *ifacePair) (result bool) {
u.depth++
if traceInference {
- u.tracef("%s ≡ %s", x, y)
+ u.tracef("%s ≡ %s\t// %s", x, y, mode)
}
defer func() {
if traceInference && !result {
u.depth--
}()
+ x = Unalias(x)
+ y = Unalias(y)
+
// nothing to do if x == y
if x == y {
return true
// 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 _, ok := x.(*Named); ok || u.asTypeParam(y) != nil {
+ if asNamed(x) != nil || u.asTypeParam(y) != nil {
if traceInference {
- u.tracef("%s ≡ %s (swap)", y, x)
+ 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.
- // Per the (spec) assignment rules, assignments of values to variables with
+ // 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. However, if the type literal is an interface and we
- // set EnableInterfaceInference, we continue with the defined type because
- // otherwise we may lose its methods.
+ // 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
// 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, _ := y.(*Named); ny != nil && isTypeLit(x) && !(u.check.conf.EnableInterfaceInference && IsInterface(x)) {
+ if ny := asNamed(y); mode&exact == 0 && ny != nil && isTypeLit(x) && !(u.enableInterfaceInference && IsInterface(x)) {
if traceInference {
u.tracef("%s ≡ under %s", x, ny)
}
return true
}
// both x and y have an inferred type - they must match
- return u.nify(u.at(px), u.at(py), p)
+ return u.nify(u.at(px), u.at(py), mode, p)
case px != nil:
// x is a type parameter, y is not
if x := u.at(px); x != nil {
// x has an inferred type which must match y
- if u.nify(x, y, p) {
- // If we have a match, possibly through underlying types,
- // and y is a defined type, make sure we record that type
- // for type parameter x, which may have until now only
- // recorded an underlying type (go.dev/issue/43056).
- if _, ok := y.(*Named); ok {
- u.set(px, 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
}
// x != y if we get here
assert(x != y)
- // 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).
- if isTypeParam(y) {
- if traceInference {
- u.tracef("%s ≡ %s (swap)", y, x)
- }
- x, y = y, x
- }
-
- // If EnableInterfaceInference is set and both types are interfaces, one
- // interface must have a subset of the methods of the other and corresponding
- // method signatures must unify.
+ // 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.check.conf.EnableInterfaceInference {
- xi, _ := x.(*Interface)
- yi, _ := y.(*Interface)
+ 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 {
}
// 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, p) {
+ if ym := ymap[xm.Id()]; ym == nil || !u.nify(xm.typ, ym.typ, exact, p) {
return false
}
}
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, p) {
+ if ym, _ := obj.(*Func); ym == nil || !u.nify(xm.typ, ym.typ, exact, p) {
return false
}
}
return true
}
+ }
+
+ // 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
+ }
- // Neither x nor y are interface types.
- // They must be structurally equivalent to unify.
+ // 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) {
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 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:
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 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:
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
}
}
// 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 *Interface:
- assert(!u.check.conf.EnableInterfaceInference) // handled before this switch
+ 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.
}
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 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 unify if their value types unify.
+ // 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.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 defined types unify if their type names originate
- // in the same type declaration. If they are instantiated,
- // their type argument lists must unify.
- if y, ok := y.(*Named); ok {
- sameOrig := indenticalOrigin(x, y)
- if u.check.conf.EnableInterfaceInference {
- xu := x.under()
- yu := y.under()
- xi, _ := xu.(*Interface)
- yi, _ := yu.(*Interface)
- // If one or both defined types are interfaces, use interface unification,
- // unless they originated in the same type declaration.
- if xi != nil && yi != nil {
- // If both interfaces originate in the same declaration,
- // their methods unify if the type parameters unify.
- // Unify the type parameters rather than the methods in
- // case the type parameters are not used in the methods
- // (and to preserve existing behavior in this case).
- if sameOrig {
- xargs := x.TypeArgs().list()
- yargs := y.TypeArgs().list()
- assert(len(xargs) == len(yargs))
- for i, xarg := range xargs {
- if !u.nify(xarg, yargs[i], p) {
- return false
- }
- }
- return true
- }
- return u.nify(xu, yu, p)
- }
- // We don't have two interfaces. If we have one, make sure it's in xi.
- if yi != nil {
- xi = yi
- y = x
- }
- // If xi is an interface, use interface unification.
- if xi != nil {
- return u.nify(xi, y, p)
- }
- // In all other cases, the type arguments and origins must match.
- }
-
+ // 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).
return false
}
for i, xarg := range xargs {
- if !u.nify(xarg, yargs[i], p) {
+ if !u.nify(xarg, yargs[i], mode, p) {
return false
}
}
- return sameOrig
+ return identicalOrigin(x, y)
}
case *TypeParam:
if traceInference {
u.tracef("core %s ≡ %s", x, y)
}
- return u.nify(cx, y, p)
+ // 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
// avoid a crash in case of nil type
default:
- panic(sprintf(nil, true, "u.nify(%s, %s)", x, y))
+ panic(sprintf(nil, true, "u.nify(%s, %s, %d)", x, y, mode))
}
return false