1 // Code generated by "go test -run=Generate -write=all"; DO NOT EDIT.
3 // Copyright 2020 The Go Authors. All rights reserved.
4 // Use of this source code is governed by a BSD-style
5 // license that can be found in the LICENSE file.
7 // This file implements type unification.
9 // Type unification attempts to make two types x and y structurally
10 // equivalent by determining the types for a given list of (bound)
11 // type parameters which may occur within x and y. If x and y are
12 // structurally different (say []T vs chan T), or conflicting
13 // types are determined for type parameters, unification fails.
14 // If unification succeeds, as a side-effect, the types of the
15 // bound type parameters may be determined.
17 // Unification typically requires multiple calls u.unify(x, y) to
18 // a given unifier u, with various combinations of types x and y.
19 // In each call, additional type parameter types may be determined
20 // as a side effect and recorded in u.
21 // If a call fails (returns false), unification fails.
23 // In the unification context, structural equivalence of two types
24 // ignores the difference between a defined type and its underlying
25 // type if one type is a defined type and the other one is not.
26 // It also ignores the difference between an (external, unbound)
27 // type parameter and its core type.
28 // If two types are not structurally equivalent, they cannot be Go
29 // identical types. On the other hand, if they are structurally
30 // equivalent, they may be Go identical or at least assignable, or
31 // they may be in the type set of a constraint.
32 // Whether they indeed are identical or assignable is determined
33 // upon instantiation and function argument passing.
45 // Upper limit for recursion depth. Used to catch infinite recursions
46 // due to implementation issues (e.g., see issues go.dev/issue/48619, go.dev/issue/48656).
47 unificationDepthLimit = 50
49 // Whether to panic when unificationDepthLimit is reached.
50 // If disabled, a recursion depth overflow results in a (quiet)
51 // unification failure.
52 panicAtUnificationDepthLimit = true
54 // If enableCoreTypeUnification is set, unification will consider
55 // the core types, if any, of non-local (unbound) type parameters.
56 enableCoreTypeUnification = true
58 // If traceInference is set, unification will print a trace of its operation.
59 // Interpretation of trace:
60 // x ≡ y attempt to unify types x and y
61 // p ➞ y type parameter p is set to type y (p is inferred to be y)
62 // p ⇄ q type parameters p and q match (p is inferred to be q and vice versa)
63 // x ≢ y types x and y cannot be unified
64 // [p, q, ...] ➞ [x, y, ...] mapping from type parameters to types
65 traceInference = false
68 // A unifier maintains a list of type parameters and
69 // corresponding types inferred for each type parameter.
70 // A unifier is created by calling newUnifier.
72 // handles maps each type parameter to its inferred type through
73 // an indirection *Type called (inferred type) "handle".
74 // Initially, each type parameter has its own, separate handle,
75 // with a nil (i.e., not yet inferred) type.
76 // After a type parameter P is unified with a type parameter Q,
77 // P and Q share the same handle (and thus type). This ensures
78 // that inferring the type for a given type parameter P will
79 // automatically infer the same type for all other parameters
80 // unified (joined) with P.
81 handles map[*TypeParam]*Type
82 depth int // recursion depth during unification
83 enableInterfaceInference bool // use shared methods for better inference
86 // newUnifier returns a new unifier initialized with the given type parameter
87 // and corresponding type argument lists. The type argument list may be shorter
88 // than the type parameter list, and it may contain nil types. Matching type
89 // parameters and arguments must have the same index.
90 func newUnifier(tparams []*TypeParam, targs []Type, enableInterfaceInference bool) *unifier {
91 assert(len(tparams) >= len(targs))
92 handles := make(map[*TypeParam]*Type, len(tparams))
93 // Allocate all handles up-front: in a correct program, all type parameters
94 // must be resolved and thus eventually will get a handle.
95 // Also, sharing of handles caused by unified type parameters is rare and
96 // so it's ok to not optimize for that case (and delay handle allocation).
97 for i, x := range tparams {
104 return &unifier{handles, 0, enableInterfaceInference}
107 // unifyMode controls the behavior of the unifier.
111 // If assign is set, we are unifying types involved in an assignment:
112 // they may match inexactly at the top, but element types must match
114 assign unifyMode = 1 << iota
116 // If exact is set, types unify if they are identical (or can be
117 // made identical with suitable arguments for type parameters).
118 // Otherwise, a named type and a type literal unify if their
119 // underlying types unify, channel directions are ignored, and
120 // if there is an interface, the other type must implement the
125 func (m unifyMode) String() string {
134 return "assign, exact"
136 return fmt.Sprintf("mode %d", m)
139 // unify attempts to unify x and y and reports whether it succeeded.
140 // As a side-effect, types may be inferred for type parameters.
141 // The mode parameter controls how types are compared.
142 func (u *unifier) unify(x, y Type, mode unifyMode) bool {
143 return u.nify(x, y, mode, nil)
146 func (u *unifier) tracef(format string, args ...interface{}) {
147 fmt.Println(strings.Repeat(". ", u.depth) + sprintf(nil, nil, true, format, args...))
150 // String returns a string representation of the current mapping
151 // from type parameters to types.
152 func (u *unifier) String() string {
153 // sort type parameters for reproducible strings
154 tparams := make(typeParamsById, len(u.handles))
156 for tpar := range u.handles {
163 w := newTypeWriter(&buf, nil)
165 for i, x := range tparams {
177 type typeParamsById []*TypeParam
179 func (s typeParamsById) Len() int { return len(s) }
180 func (s typeParamsById) Less(i, j int) bool { return s[i].id < s[j].id }
181 func (s typeParamsById) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
183 // join unifies the given type parameters x and y.
184 // If both type parameters already have a type associated with them
185 // and they are not joined, join fails and returns false.
186 func (u *unifier) join(x, y *TypeParam) bool {
188 u.tracef("%s ⇄ %s", x, y)
190 switch hx, hy := u.handles[x], u.handles[y]; {
192 // Both type parameters already share the same handle. Nothing to do.
193 case *hx != nil && *hy != nil:
194 // Both type parameters have (possibly different) inferred types. Cannot join.
197 // Only type parameter x has an inferred type. Use handle of x.
199 // This case is treated like the default case.
201 // // Only type parameter y has an inferred type. Use handle of y.
202 // u.setHandle(x, hy)
204 // Neither type parameter has an inferred type. Use handle of y.
210 // asTypeParam returns x.(*TypeParam) if x is a type parameter recorded with u.
211 // Otherwise, the result is nil.
212 func (u *unifier) asTypeParam(x Type) *TypeParam {
213 if x, _ := x.(*TypeParam); x != nil {
214 if _, found := u.handles[x]; found {
221 // setHandle sets the handle for type parameter x
222 // (and all its joined type parameters) to h.
223 func (u *unifier) setHandle(x *TypeParam, h *Type) {
226 for y, hy := range u.handles {
233 // at returns the (possibly nil) type for type parameter x.
234 func (u *unifier) at(x *TypeParam) Type {
238 // set sets the type t for type parameter x;
239 // t must not be nil.
240 func (u *unifier) set(x *TypeParam, t Type) {
243 u.tracef("%s ➞ %s", x, t)
248 // unknowns returns the number of type parameters for which no type has been set yet.
249 func (u *unifier) unknowns() int {
251 for _, h := range u.handles {
259 // inferred returns the list of inferred types for the given type parameter list.
260 // The result is never nil and has the same length as tparams; result types that
261 // could not be inferred are nil. Corresponding type parameters and result types
262 // have identical indices.
263 func (u *unifier) inferred(tparams []*TypeParam) []Type {
264 list := make([]Type, len(tparams))
265 for i, x := range tparams {
271 // asInterface returns the underlying type of x as an interface if
272 // it is a non-type parameter interface. Otherwise it returns nil.
273 func asInterface(x Type) (i *Interface) {
274 if _, ok := x.(*TypeParam); !ok {
275 i, _ = under(x).(*Interface)
280 // nify implements the core unification algorithm which is an
281 // adapted version of Checker.identical. For changes to that
282 // code the corresponding changes should be made here.
283 // Must not be called directly from outside the unifier.
284 func (u *unifier) nify(x, y Type, mode unifyMode, p *ifacePair) (result bool) {
287 u.tracef("%s ≡ %s\t// %s", x, y, mode)
290 if traceInference && !result {
291 u.tracef("%s ≢ %s", x, y)
296 // nothing to do if x == y
301 // Stop gap for cases where unification fails.
302 if u.depth > unificationDepthLimit {
304 u.tracef("depth %d >= %d", u.depth, unificationDepthLimit)
306 if panicAtUnificationDepthLimit {
307 panic("unification reached recursion depth limit")
312 // Unification is symmetric, so we can swap the operands.
313 // Ensure that if we have at least one
314 // - defined type, make sure one is in y
315 // - type parameter recorded with u, make sure one is in x
316 if asNamed(x) != nil || u.asTypeParam(y) != nil {
318 u.tracef("%s ≡ %s\t// swap", y, x)
323 // Unification will fail if we match a defined type against a type literal.
324 // If we are matching types in an assignment, at the top-level, types with
325 // the same type structure are permitted as long as at least one of them
326 // is not a defined type. To accommodate for that possibility, we continue
327 // unification with the underlying type of a defined type if the other type
328 // is a type literal. This is controlled by the exact unification mode.
329 // We also continue if the other type is a basic type because basic types
330 // are valid underlying types and may appear as core types of type constraints.
331 // If we exclude them, inferred defined types for type parameters may not
332 // match against the core types of their constraints (even though they might
333 // correctly match against some of the types in the constraint's type set).
334 // Finally, if unification (incorrectly) succeeds by matching the underlying
335 // type of a defined type against a basic type (because we include basic types
336 // as type literals here), and if that leads to an incorrectly inferred type,
337 // we will fail at function instantiation or argument assignment time.
339 // If we have at least one defined type, there is one in y.
340 if ny := asNamed(y); mode&exact == 0 && ny != nil && isTypeLit(x) && !(u.enableInterfaceInference && IsInterface(x)) {
342 u.tracef("%s ≡ under %s", x, ny)
345 // Per the spec, a defined type cannot have an underlying type
346 // that is a type parameter.
347 assert(!isTypeParam(y))
348 // x and y may be identical now
354 // Cases where at least one of x or y is a type parameter recorded with u.
355 // If we have at least one type parameter, there is one in x.
356 // If we have exactly one type parameter, because it is in x,
357 // isTypeLit(x) is false and y was not changed above. In other
358 // words, if y was a defined type, it is still a defined type
359 // (relevant for the logic below).
360 switch px, py := u.asTypeParam(x), u.asTypeParam(y); {
361 case px != nil && py != nil:
362 // both x and y are type parameters
366 // both x and y have an inferred type - they must match
367 return u.nify(u.at(px), u.at(py), mode, p)
370 // x is a type parameter, y is not
371 if x := u.at(px); x != nil {
372 // x has an inferred type which must match y
373 if u.nify(x, y, mode, p) {
374 // We have a match, possibly through underlying types.
377 xn := asNamed(x) != nil
378 yn := asNamed(y) != nil
379 // If we have two interfaces, what to do depends on
380 // whether they are named and their method sets.
381 if xi != nil && yi != nil {
382 // Both types are interfaces.
383 // If both types are defined types, they must be identical
384 // because unification doesn't know which type has the "right" name.
386 return Identical(x, y)
388 // In all other cases, the method sets must match.
389 // The types unified so we know that corresponding methods
390 // match and we can simply compare the number of methods.
391 // TODO(gri) We may be able to relax this rule and select
392 // the more general interface. But if one of them is a defined
393 // type, it's not clear how to choose and whether we introduce
394 // an order dependency or not. Requiring the same method set
396 if len(xi.typeSet().methods) != len(yi.typeSet().methods) {
399 } else if xi != nil || yi != nil {
400 // One but not both of them are interfaces.
401 // In this case, either x or y could be viable matches for the corresponding
402 // type parameter, which means choosing either introduces an order dependence.
403 // Therefore, we must fail unification (go.dev/issue/60933).
406 // If we have inexact unification and one of x or y is a defined type, select the
407 // defined type. This ensures that in a series of types, all matching against the
408 // same type parameter, we infer a defined type if there is one, independent of
409 // order. Type inference or assignment may fail, which is ok.
410 // Selecting a defined type, if any, ensures that we don't lose the type name;
411 // and since we have inexact unification, a value of equally named or matching
412 // undefined type remains assignable (go.dev/issue/43056).
414 // Similarly, if we have inexact unification and there are no defined types but
415 // channel types, select a directed channel, if any. This ensures that in a series
416 // of unnamed types, all matching against the same type parameter, we infer the
417 // directed channel if there is one, independent of order.
418 // Selecting a directional channel, if any, ensures that a value of another
419 // inexactly unifying channel type remains assignable (go.dev/issue/62157).
421 // If we have multiple defined channel types, they are either identical or we
422 // have assignment conflicts, so we can ignore directionality in this case.
424 // If we have defined and literal channel types, a defined type wins to avoid
425 // order dependencies.
429 // x is a defined type: nothing to do.
431 // x is not a defined type and y is a defined type: select y.
434 // Neither x nor y are defined types.
435 if yc, _ := under(y).(*Chan); yc != nil && yc.dir != SendRecv {
436 // y is a directed channel type: select y.
445 // otherwise, infer type from y
450 // x != y if we get here
453 // If u.EnableInterfaceInference is set and we don't require exact unification,
454 // if both types are interfaces, one interface must have a subset of the
455 // methods of the other and corresponding method signatures must unify.
456 // If only one type is an interface, all its methods must be present in the
457 // other type and corresponding method signatures must unify.
458 if u.enableInterfaceInference && mode&exact == 0 {
459 // One or both interfaces may be defined types.
460 // Look under the name, but not under type parameters (go.dev/issue/60564).
463 // If we have two interfaces, check the type terms for equivalence,
464 // and unify common methods if possible.
465 if xi != nil && yi != nil {
468 if xset.comparable != yset.comparable {
471 // For now we require terms to be equal.
472 // We should be able to relax this as well, eventually.
473 if !xset.terms.equal(yset.terms) {
476 // Interface types are the only types where cycles can occur
477 // that are not "terminated" via named types; and such cycles
478 // can only be created via method parameter types that are
479 // anonymous interfaces (directly or indirectly) embedding
480 // the current interface. Example:
482 // type T interface {
486 // If two such (differently named) interfaces are compared,
487 // endless recursion occurs if the cycle is not detected.
489 // If x and y were compared before, they must be equal
490 // (if they were not, the recursion would have stopped);
491 // search the ifacePair stack for the same pair.
493 // This is a quadratic algorithm, but in practice these stacks
494 // are extremely short (bounded by the nesting depth of interface
495 // type declarations that recur via parameter types, an extremely
496 // rare occurrence). An alternative implementation might use a
497 // "visited" map, but that is probably less efficient overall.
498 q := &ifacePair{xi, yi, p}
501 return true // same pair was compared before
505 // The method set of x must be a subset of the method set
506 // of y or vice versa, and the common methods must unify.
507 xmethods := xset.methods
508 ymethods := yset.methods
509 // The smaller method set must be the subset, if it exists.
510 if len(xmethods) > len(ymethods) {
511 xmethods, ymethods = ymethods, xmethods
513 // len(xmethods) <= len(ymethods)
514 // Collect the ymethods in a map for quick lookup.
515 ymap := make(map[string]*Func, len(ymethods))
516 for _, ym := range ymethods {
519 // All xmethods must exist in ymethods and corresponding signatures must unify.
520 for _, xm := range xmethods {
521 if ym := ymap[xm.Id()]; ym == nil || !u.nify(xm.typ, ym.typ, exact, p) {
528 // We don't have two interfaces. If we have one, make sure it's in xi.
534 // If we have one interface, at a minimum each of the interface methods
535 // must be implemented and thus unify with a corresponding method from
536 // the non-interface type, otherwise unification fails.
538 // All xi methods must exist in y and corresponding signatures must unify.
539 xmethods := xi.typeSet().methods
540 for _, xm := range xmethods {
541 obj, _, _ := LookupFieldOrMethod(y, false, xm.pkg, xm.name)
542 if ym, _ := obj.(*Func); ym == nil || !u.nify(xm.typ, ym.typ, exact, p) {
550 // Unless we have exact unification, neither x nor y are interfaces now.
551 // Except for unbound type parameters (see below), x and y must be structurally
552 // equivalent to unify.
554 // If we get here and x or y is a type parameter, they are unbound
555 // (not recorded with the unifier).
556 // Ensure that if we have at least one type parameter, it is in x
557 // (the earlier swap checks for _recorded_ type parameters only).
558 // This ensures that the switch switches on the type parameter.
560 // TODO(gri) Factor out type parameter handling from the switch.
563 u.tracef("%s ≡ %s\t// swap", y, x)
568 // Type elements (array, slice, etc. elements) use emode for unification.
569 // Element types must match exactly if the types are used in an assignment.
571 if mode&assign != 0 {
575 switch x := x.(type) {
577 // Basic types are singletons except for the rune and byte
578 // aliases, thus we cannot solely rely on the x == y check
579 // above. See also comment in TypeName.IsAlias.
580 if y, ok := y.(*Basic); ok {
581 return x.kind == y.kind
585 // Two array types unify if they have the same array length
586 // and their element types unify.
587 if y, ok := y.(*Array); ok {
588 // If one or both array lengths are unknown (< 0) due to some error,
589 // assume they are the same to avoid spurious follow-on errors.
590 return (x.len < 0 || y.len < 0 || x.len == y.len) && u.nify(x.elem, y.elem, emode, p)
594 // Two slice types unify if their element types unify.
595 if y, ok := y.(*Slice); ok {
596 return u.nify(x.elem, y.elem, emode, p)
600 // Two struct types unify if they have the same sequence of fields,
601 // and if corresponding fields have the same names, their (field) types unify,
602 // and they have identical tags. Two embedded fields are considered to have the same
603 // name. Lower-case field names from different packages are always different.
604 if y, ok := y.(*Struct); ok {
605 if x.NumFields() == y.NumFields() {
606 for i, f := range x.fields {
608 if f.embedded != g.embedded ||
609 x.Tag(i) != y.Tag(i) ||
610 !f.sameId(g.pkg, g.name) ||
611 !u.nify(f.typ, g.typ, emode, p) {
620 // Two pointer types unify if their base types unify.
621 if y, ok := y.(*Pointer); ok {
622 return u.nify(x.base, y.base, emode, p)
626 // Two tuples types unify if they have the same number of elements
627 // and the types of corresponding elements unify.
628 if y, ok := y.(*Tuple); ok {
629 if x.Len() == y.Len() {
631 for i, v := range x.vars {
633 if !u.nify(v.typ, w.typ, mode, p) {
643 // Two function types unify if they have the same number of parameters
644 // and result values, corresponding parameter and result types unify,
645 // and either both functions are variadic or neither is.
646 // Parameter and result names are not required to match.
647 // TODO(gri) handle type parameters or document why we can ignore them.
648 if y, ok := y.(*Signature); ok {
649 return x.variadic == y.variadic &&
650 u.nify(x.params, y.params, emode, p) &&
651 u.nify(x.results, y.results, emode, p)
655 assert(!u.enableInterfaceInference || mode&exact != 0) // handled before this switch
657 // Two interface types unify if they have the same set of methods with
658 // the same names, and corresponding function types unify.
659 // Lower-case method names from different packages are always different.
660 // The order of the methods is irrelevant.
661 if y, ok := y.(*Interface); ok {
664 if xset.comparable != yset.comparable {
667 if !xset.terms.equal(yset.terms) {
672 if len(a) == len(b) {
673 // Interface types are the only types where cycles can occur
674 // that are not "terminated" via named types; and such cycles
675 // can only be created via method parameter types that are
676 // anonymous interfaces (directly or indirectly) embedding
677 // the current interface. Example:
679 // type T interface {
683 // If two such (differently named) interfaces are compared,
684 // endless recursion occurs if the cycle is not detected.
686 // If x and y were compared before, they must be equal
687 // (if they were not, the recursion would have stopped);
688 // search the ifacePair stack for the same pair.
690 // This is a quadratic algorithm, but in practice these stacks
691 // are extremely short (bounded by the nesting depth of interface
692 // type declarations that recur via parameter types, an extremely
693 // rare occurrence). An alternative implementation might use a
694 // "visited" map, but that is probably less efficient overall.
695 q := &ifacePair{x, y, p}
698 return true // same pair was compared before
703 assertSortedMethods(a)
704 assertSortedMethods(b)
706 for i, f := range a {
708 if f.Id() != g.Id() || !u.nify(f.typ, g.typ, exact, q) {
717 // Two map types unify if their key and value types unify.
718 if y, ok := y.(*Map); ok {
719 return u.nify(x.key, y.key, emode, p) && u.nify(x.elem, y.elem, emode, p)
723 // Two channel types unify if their value types unify
724 // and if they have the same direction.
725 // The channel direction is ignored for inexact unification.
726 if y, ok := y.(*Chan); ok {
727 return (mode&exact == 0 || x.dir == y.dir) && u.nify(x.elem, y.elem, emode, p)
731 // Two named types unify if their type names originate in the same type declaration.
732 // If they are instantiated, their type argument lists must unify.
733 if y := asNamed(y); y != nil {
734 // Check type arguments before origins so they unify
735 // even if the origins don't match; for better error
736 // messages (see go.dev/issue/53692).
737 xargs := x.TypeArgs().list()
738 yargs := y.TypeArgs().list()
739 if len(xargs) != len(yargs) {
742 for i, xarg := range xargs {
743 if !u.nify(xarg, yargs[i], mode, p) {
747 return identicalOrigin(x, y)
751 // x must be an unbound type parameter (see comment above).
753 assert(u.asTypeParam(x) == nil)
755 // By definition, a valid type argument must be in the type set of
756 // the respective type constraint. Therefore, the type argument's
757 // underlying type must be in the set of underlying types of that
758 // constraint. If there is a single such underlying type, it's the
759 // constraint's core type. It must match the type argument's under-
760 // lying type, irrespective of whether the actual type argument,
761 // which may be a defined type, is actually in the type set (that
762 // will be determined at instantiation time).
763 // Thus, if we have the core type of an unbound type parameter,
764 // we know the structure of the possible types satisfying such
765 // parameters. Use that core type for further unification
766 // (see go.dev/issue/50755 for a test case).
767 if enableCoreTypeUnification {
768 // Because the core type is always an underlying type,
769 // unification will take care of matching against a
770 // defined or literal type automatically.
771 // If y is also an unbound type parameter, we will end
772 // up here again with x and y swapped, so we don't
773 // need to take care of that case separately.
774 if cx := coreType(x); cx != nil {
776 u.tracef("core %s ≡ %s", x, y)
778 // If y is a defined type, it may not match against cx which
779 // is an underlying type (incl. int, string, etc.). Use assign
780 // mode here so that the unifier automatically takes under(y)
782 return u.nify(cx, y, assign, p)
785 // x != y and there's nothing to do
788 // avoid a crash in case of nil type
791 panic(sprintf(nil, nil, true, "u.nify(%s, %s, %d)", x, y, mode))