1 // Code generated by "go test -run=Generate -write=all"; DO NOT EDIT.
2 // Source: ../../cmd/compile/internal/types2/unify.go
3 4 // Copyright 2020 The Go Authors. All rights reserved.
5 // Use of this source code is governed by a BSD-style
6 // license that can be found in the LICENSE file.
7 8 // This file implements type unification.
9 //
10 // Type unification attempts to make two types x and y structurally
11 // equivalent by determining the types for a given list of (bound)
12 // type parameters which may occur within x and y. If x and y are
13 // structurally different (say []T vs chan T), or conflicting
14 // types are determined for type parameters, unification fails.
15 // If unification succeeds, as a side-effect, the types of the
16 // bound type parameters may be determined.
17 //
18 // Unification typically requires multiple calls u.unify(x, y) to
19 // a given unifier u, with various combinations of types x and y.
20 // In each call, additional type parameter types may be determined
21 // as a side effect and recorded in u.
22 // If a call fails (returns false), unification fails.
23 //
24 // In the unification context, structural equivalence of two types
25 // ignores the difference between a defined type and its underlying
26 // type if one type is a defined type and the other one is not.
27 // It also ignores the difference between an (external, unbound)
28 // type parameter and its core type.
29 // If two types are not structurally equivalent, they cannot be Go
30 // identical types. On the other hand, if they are structurally
31 // equivalent, they may be Go identical or at least assignable, or
32 // they may be in the type set of a constraint.
33 // Whether they indeed are identical or assignable is determined
34 // upon instantiation and function argument passing.
35 36 package types
37 38 import (
39 "bytes"
40 "fmt"
41 "sort"
42 "strings"
43 )
44 45 const (
46 // Upper limit for recursion depth. Used to catch infinite recursions
47 // due to implementation issues (e.g., see issues go.dev/issue/48619, go.dev/issue/48656).
48 unificationDepthLimit = 50
49 50 // Whether to panic when unificationDepthLimit is reached.
51 // If disabled, a recursion depth overflow results in a (quiet)
52 // unification failure.
53 panicAtUnificationDepthLimit = true
54 55 // If enableCoreTypeUnification is set, unification will consider
56 // the core types, if any, of non-local (unbound) type parameters.
57 enableCoreTypeUnification = true
58 59 // If traceInference is set, unification will print a trace of its operation.
60 // Interpretation of trace:
61 // x ≡ y attempt to unify types x and y
62 // p ➞ y type parameter p is set to type y (p is inferred to be y)
63 // p ⇄ q type parameters p and q match (p is inferred to be q and vice versa)
64 // x ≢ y types x and y cannot be unified
65 // [p, q, ...] ➞ [x, y, ...] mapping from type parameters to types
66 traceInference = false
67 )
68 69 // A unifier maintains a list of type parameters and
70 // corresponding types inferred for each type parameter.
71 // A unifier is created by calling newUnifier.
72 type unifier struct {
73 // handles maps each type parameter to its inferred type through
74 // an indirection *Type called (inferred type) "handle".
75 // Initially, each type parameter has its own, separate handle,
76 // with a nil (i.e., not yet inferred) type.
77 // After a type parameter P is unified with a type parameter Q,
78 // P and Q share the same handle (and thus type). This ensures
79 // that inferring the type for a given type parameter P will
80 // automatically infer the same type for all other parameters
81 // unified (joined) with P.
82 handles map[*TypeParam]*Type
83 depth int // recursion depth during unification
84 enableInterfaceInference bool // use shared methods for better inference
85 }
86 87 // newUnifier returns a new unifier initialized with the given type parameter
88 // and corresponding type argument lists. The type argument list may be shorter
89 // than the type parameter list, and it may contain nil types. Matching type
90 // parameters and arguments must have the same index.
91 func newUnifier(tparams []*TypeParam, targs []Type, enableInterfaceInference bool) *unifier {
92 assert(len(tparams) >= len(targs))
93 handles := make(map[*TypeParam]*Type, len(tparams))
94 // Allocate all handles up-front: in a correct program, all type parameters
95 // must be resolved and thus eventually will get a handle.
96 // Also, sharing of handles caused by unified type parameters is rare and
97 // so it's ok to not optimize for that case (and delay handle allocation).
98 for i, x := range tparams {
99 var t Type
100 if i < len(targs) {
101 t = targs[i]
102 }
103 handles[x] = &t
104 }
105 return &unifier{handles, 0, enableInterfaceInference}
106 }
107 108 // unifyMode controls the behavior of the unifier.
109 type unifyMode uint
110 111 const (
112 // If assign is set, we are unifying types involved in an assignment:
113 // they may match inexactly at the top, but element types must match
114 // exactly.
115 assign unifyMode = 1 << iota
116 117 // If exact is set, types unify if they are identical (or can be
118 // made identical with suitable arguments for type parameters).
119 // Otherwise, a named type and a type literal unify if their
120 // underlying types unify, channel directions are ignored, and
121 // if there is an interface, the other type must implement the
122 // interface.
123 exact
124 )
125 126 func (m unifyMode) String() string {
127 switch m {
128 case 0:
129 return "inexact"
130 case assign:
131 return "assign"
132 case exact:
133 return "exact"
134 case assign | exact:
135 return "assign, exact"
136 }
137 return fmt.Sprintf("mode %d", m)
138 }
139 140 // unify attempts to unify x and y and reports whether it succeeded.
141 // As a side-effect, types may be inferred for type parameters.
142 // The mode parameter controls how types are compared.
143 func (u *unifier) unify(x, y Type, mode unifyMode) bool {
144 return u.nify(x, y, mode, nil)
145 }
146 147 func (u *unifier) tracef(format string, args ...interface{}) {
148 fmt.Println(strings.Repeat(". ", u.depth) + sprintf(nil, nil, true, format, args...))
149 }
150 151 // String returns a string representation of the current mapping
152 // from type parameters to types.
153 func (u *unifier) String() string {
154 // sort type parameters for reproducible strings
155 tparams := make(typeParamsById, len(u.handles))
156 i := 0
157 for tpar := range u.handles {
158 tparams[i] = tpar
159 i++
160 }
161 sort.Sort(tparams)
162 163 var buf bytes.Buffer
164 w := newTypeWriter(&buf, nil)
165 w.byte('[')
166 for i, x := range tparams {
167 if i > 0 {
168 w.string(", ")
169 }
170 w.typ(x)
171 w.string(": ")
172 w.typ(u.at(x))
173 }
174 w.byte(']')
175 return buf.String()
176 }
177 178 type typeParamsById []*TypeParam
179 180 func (s typeParamsById) Len() int { return len(s) }
181 func (s typeParamsById) Less(i, j int) bool { return s[i].id < s[j].id }
182 func (s typeParamsById) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
183 184 // join unifies the given type parameters x and y.
185 // If both type parameters already have a type associated with them
186 // and they are not joined, join fails and returns false.
187 func (u *unifier) join(x, y *TypeParam) bool {
188 if traceInference {
189 u.tracef("%s ⇄ %s", x, y)
190 }
191 switch hx, hy := u.handles[x], u.handles[y]; {
192 case hx == hy:
193 // Both type parameters already share the same handle. Nothing to do.
194 case *hx != nil && *hy != nil:
195 // Both type parameters have (possibly different) inferred types. Cannot join.
196 return false
197 case *hx != nil:
198 // Only type parameter x has an inferred type. Use handle of x.
199 u.setHandle(y, hx)
200 // This case is treated like the default case.
201 // case *hy != nil:
202 // // Only type parameter y has an inferred type. Use handle of y.
203 // u.setHandle(x, hy)
204 default:
205 // Neither type parameter has an inferred type. Use handle of y.
206 u.setHandle(x, hy)
207 }
208 return true
209 }
210 211 // asBoundTypeParam returns x.(*TypeParam) if x is a type parameter recorded with u.
212 // Otherwise, the result is nil.
213 func (u *unifier) asBoundTypeParam(x Type) *TypeParam {
214 if x, _ := Unalias(x).(*TypeParam); x != nil {
215 if _, found := u.handles[x]; found {
216 return x
217 }
218 }
219 return nil
220 }
221 222 // setHandle sets the handle for type parameter x
223 // (and all its joined type parameters) to h.
224 func (u *unifier) setHandle(x *TypeParam, h *Type) {
225 hx := u.handles[x]
226 assert(hx != nil)
227 for y, hy := range u.handles {
228 if hy == hx {
229 u.handles[y] = h
230 }
231 }
232 }
233 234 // at returns the (possibly nil) type for type parameter x.
235 func (u *unifier) at(x *TypeParam) Type {
236 return *u.handles[x]
237 }
238 239 // set sets the type t for type parameter x;
240 // t must not be nil.
241 func (u *unifier) set(x *TypeParam, t Type) {
242 assert(t != nil)
243 if traceInference {
244 u.tracef("%s ➞ %s", x, t)
245 }
246 *u.handles[x] = t
247 }
248 249 // unknowns returns the number of type parameters for which no type has been set yet.
250 func (u *unifier) unknowns() int {
251 n := 0
252 for _, h := range u.handles {
253 if *h == nil {
254 n++
255 }
256 }
257 return n
258 }
259 260 // inferred returns the list of inferred types for the given type parameter list.
261 // The result is never nil and has the same length as tparams; result types that
262 // could not be inferred are nil. Corresponding type parameters and result types
263 // have identical indices.
264 func (u *unifier) inferred(tparams []*TypeParam) []Type {
265 list := make([]Type, len(tparams))
266 for i, x := range tparams {
267 list[i] = u.at(x)
268 }
269 return list
270 }
271 272 // asInterface returns the underlying type of x as an interface if
273 // it is a non-type parameter interface. Otherwise it returns nil.
274 func asInterface(x Type) (i *Interface) {
275 if _, ok := Unalias(x).(*TypeParam); !ok {
276 i, _ = under(x).(*Interface)
277 }
278 return i
279 }
280 281 // nify implements the core unification algorithm which is an
282 // adapted version of Checker.identical. For changes to that
283 // code the corresponding changes should be made here.
284 // Must not be called directly from outside the unifier.
285 func (u *unifier) nify(x, y Type, mode unifyMode, p *ifacePair) (result bool) {
286 u.depth++
287 if traceInference {
288 u.tracef("%s ≡ %s\t// %s", x, y, mode)
289 }
290 defer func() {
291 if traceInference && !result {
292 u.tracef("%s ≢ %s", x, y)
293 }
294 u.depth--
295 }()
296 297 // nothing to do if x == y
298 if x == y || Unalias(x) == Unalias(y) {
299 return true
300 }
301 302 // Moxie: string and []byte unify (string=[]byte).
303 if (isString(x) && isByteSlice(y)) || (isByteSlice(x) && isString(y)) {
304 return true
305 }
306 307 // Stop gap for cases where unification fails.
308 if u.depth > unificationDepthLimit {
309 if traceInference {
310 u.tracef("depth %d >= %d", u.depth, unificationDepthLimit)
311 }
312 if panicAtUnificationDepthLimit {
313 panic("unification reached recursion depth limit")
314 }
315 return false
316 }
317 318 // Unification is symmetric, so we can swap the operands.
319 // Ensure that if we have at least one
320 // - defined type, make sure one is in y
321 // - type parameter recorded with u, make sure one is in x
322 if asNamed(x) != nil || u.asBoundTypeParam(y) != nil {
323 if traceInference {
324 u.tracef("%s ≡ %s\t// swap", y, x)
325 }
326 x, y = y, x
327 }
328 329 // Unification will fail if we match a defined type against a type literal.
330 // If we are matching types in an assignment, at the top-level, types with
331 // the same type structure are permitted as long as at least one of them
332 // is not a defined type. To accommodate for that possibility, we continue
333 // unification with the underlying type of a defined type if the other type
334 // is a type literal. This is controlled by the exact unification mode.
335 // We also continue if the other type is a basic type because basic types
336 // are valid underlying types and may appear as core types of type constraints.
337 // If we exclude them, inferred defined types for type parameters may not
338 // match against the core types of their constraints (even though they might
339 // correctly match against some of the types in the constraint's type set).
340 // Finally, if unification (incorrectly) succeeds by matching the underlying
341 // type of a defined type against a basic type (because we include basic types
342 // as type literals here), and if that leads to an incorrectly inferred type,
343 // we will fail at function instantiation or argument assignment time.
344 //
345 // If we have at least one defined type, there is one in y.
346 if ny := asNamed(y); mode&exact == 0 && ny != nil && isTypeLit(x) && !(u.enableInterfaceInference && IsInterface(x)) {
347 if traceInference {
348 u.tracef("%s ≡ under %s", x, ny)
349 }
350 y = ny.under()
351 // Per the spec, a defined type cannot have an underlying type
352 // that is a type parameter.
353 assert(!isTypeParam(y))
354 // x and y may be identical now
355 if x == y || Unalias(x) == Unalias(y) {
356 return true
357 }
358 }
359 360 // Cases where at least one of x or y is a type parameter recorded with u.
361 // If we have at least one type parameter, there is one in x.
362 // If we have exactly one type parameter, because it is in x,
363 // isTypeLit(x) is false and y was not changed above. In other
364 // words, if y was a defined type, it is still a defined type
365 // (relevant for the logic below).
366 switch px, py := u.asBoundTypeParam(x), u.asBoundTypeParam(y); {
367 case px != nil && py != nil:
368 // both x and y are type parameters
369 if u.join(px, py) {
370 return true
371 }
372 // both x and y have an inferred type - they must match
373 return u.nify(u.at(px), u.at(py), mode, p)
374 375 case px != nil:
376 // x is a type parameter, y is not
377 if x := u.at(px); x != nil {
378 // x has an inferred type which must match y
379 if u.nify(x, y, mode, p) {
380 // We have a match, possibly through underlying types.
381 xi := asInterface(x)
382 yi := asInterface(y)
383 xn := asNamed(x) != nil
384 yn := asNamed(y) != nil
385 // If we have two interfaces, what to do depends on
386 // whether they are named and their method sets.
387 if xi != nil && yi != nil {
388 // Both types are interfaces.
389 // If both types are defined types, they must be identical
390 // because unification doesn't know which type has the "right" name.
391 if xn && yn {
392 return Identical(x, y)
393 }
394 // In all other cases, the method sets must match.
395 // The types unified so we know that corresponding methods
396 // match and we can simply compare the number of methods.
397 // TODO(gri) We may be able to relax this rule and select
398 // the more general interface. But if one of them is a defined
399 // type, it's not clear how to choose and whether we introduce
400 // an order dependency or not. Requiring the same method set
401 // is conservative.
402 if len(xi.typeSet().methods) != len(yi.typeSet().methods) {
403 return false
404 }
405 } else if xi != nil || yi != nil {
406 // One but not both of them are interfaces.
407 // In this case, either x or y could be viable matches for the corresponding
408 // type parameter, which means choosing either introduces an order dependence.
409 // Therefore, we must fail unification (go.dev/issue/60933).
410 return false
411 }
412 // If we have inexact unification and one of x or y is a defined type, select the
413 // defined type. This ensures that in a series of types, all matching against the
414 // same type parameter, we infer a defined type if there is one, independent of
415 // order. Type inference or assignment may fail, which is ok.
416 // Selecting a defined type, if any, ensures that we don't lose the type name;
417 // and since we have inexact unification, a value of equally named or matching
418 // undefined type remains assignable (go.dev/issue/43056).
419 //
420 // Similarly, if we have inexact unification and there are no defined types but
421 // channel types, select a directed channel, if any. This ensures that in a series
422 // of unnamed types, all matching against the same type parameter, we infer the
423 // directed channel if there is one, independent of order.
424 // Selecting a directional channel, if any, ensures that a value of another
425 // inexactly unifying channel type remains assignable (go.dev/issue/62157).
426 //
427 // If we have multiple defined channel types, they are either identical or we
428 // have assignment conflicts, so we can ignore directionality in this case.
429 //
430 // If we have defined and literal channel types, a defined type wins to avoid
431 // order dependencies.
432 if mode&exact == 0 {
433 switch {
434 case xn:
435 // x is a defined type: nothing to do.
436 case yn:
437 // x is not a defined type and y is a defined type: select y.
438 u.set(px, y)
439 default:
440 // Neither x nor y are defined types.
441 if yc, _ := under(y).(*Chan); yc != nil && yc.dir != SendRecv {
442 // y is a directed channel type: select y.
443 u.set(px, y)
444 }
445 }
446 }
447 return true
448 }
449 return false
450 }
451 // otherwise, infer type from y
452 u.set(px, y)
453 return true
454 }
455 456 // x != y if we get here
457 assert(x != y && Unalias(x) != Unalias(y))
458 459 // If u.EnableInterfaceInference is set and we don't require exact unification,
460 // if both types are interfaces, one interface must have a subset of the
461 // methods of the other and corresponding method signatures must unify.
462 // If only one type is an interface, all its methods must be present in the
463 // other type and corresponding method signatures must unify.
464 if u.enableInterfaceInference && mode&exact == 0 {
465 // One or both interfaces may be defined types.
466 // Look under the name, but not under type parameters (go.dev/issue/60564).
467 xi := asInterface(x)
468 yi := asInterface(y)
469 // If we have two interfaces, check the type terms for equivalence,
470 // and unify common methods if possible.
471 if xi != nil && yi != nil {
472 xset := xi.typeSet()
473 yset := yi.typeSet()
474 if xset.comparable != yset.comparable {
475 return false
476 }
477 // For now we require terms to be equal.
478 // We should be able to relax this as well, eventually.
479 if !xset.terms.equal(yset.terms) {
480 return false
481 }
482 // Interface types are the only types where cycles can occur
483 // that are not "terminated" via named types; and such cycles
484 // can only be created via method parameter types that are
485 // anonymous interfaces (directly or indirectly) embedding
486 // the current interface. Example:
487 //
488 // type T interface {
489 // m() interface{T}
490 // }
491 //
492 // If two such (differently named) interfaces are compared,
493 // endless recursion occurs if the cycle is not detected.
494 //
495 // If x and y were compared before, they must be equal
496 // (if they were not, the recursion would have stopped);
497 // search the ifacePair stack for the same pair.
498 //
499 // This is a quadratic algorithm, but in practice these stacks
500 // are extremely short (bounded by the nesting depth of interface
501 // type declarations that recur via parameter types, an extremely
502 // rare occurrence). An alternative implementation might use a
503 // "visited" map, but that is probably less efficient overall.
504 q := &ifacePair{xi, yi, p}
505 for p != nil {
506 if p.identical(q) {
507 return true // same pair was compared before
508 }
509 p = p.prev
510 }
511 // The method set of x must be a subset of the method set
512 // of y or vice versa, and the common methods must unify.
513 xmethods := xset.methods
514 ymethods := yset.methods
515 // The smaller method set must be the subset, if it exists.
516 if len(xmethods) > len(ymethods) {
517 xmethods, ymethods = ymethods, xmethods
518 }
519 // len(xmethods) <= len(ymethods)
520 // Collect the ymethods in a map for quick lookup.
521 ymap := make(map[string]*Func, len(ymethods))
522 for _, ym := range ymethods {
523 ymap[ym.Id()] = ym
524 }
525 // All xmethods must exist in ymethods and corresponding signatures must unify.
526 for _, xm := range xmethods {
527 if ym := ymap[xm.Id()]; ym == nil || !u.nify(xm.typ, ym.typ, exact, p) {
528 return false
529 }
530 }
531 return true
532 }
533 534 // We don't have two interfaces. If we have one, make sure it's in xi.
535 if yi != nil {
536 xi = yi
537 y = x
538 }
539 540 // If we have one interface, at a minimum each of the interface methods
541 // must be implemented and thus unify with a corresponding method from
542 // the non-interface type, otherwise unification fails.
543 if xi != nil {
544 // All xi methods must exist in y and corresponding signatures must unify.
545 xmethods := xi.typeSet().methods
546 for _, xm := range xmethods {
547 obj, _, _ := LookupFieldOrMethod(y, false, xm.pkg, xm.name)
548 if ym, _ := obj.(*Func); ym == nil || !u.nify(xm.typ, ym.typ, exact, p) {
549 return false
550 }
551 }
552 return true
553 }
554 }
555 556 // Unless we have exact unification, neither x nor y are interfaces now.
557 // Except for unbound type parameters (see below), x and y must be structurally
558 // equivalent to unify.
559 560 // If we get here and x or y is a type parameter, they are unbound
561 // (not recorded with the unifier).
562 // Ensure that if we have at least one type parameter, it is in x
563 // (the earlier swap checks for _recorded_ type parameters only).
564 // This ensures that the switch switches on the type parameter.
565 //
566 // TODO(gri) Factor out type parameter handling from the switch.
567 if isTypeParam(y) {
568 if traceInference {
569 u.tracef("%s ≡ %s\t// swap", y, x)
570 }
571 x, y = y, x
572 }
573 574 // Type elements (array, slice, etc. elements) use emode for unification.
575 // Element types must match exactly if the types are used in an assignment.
576 emode := mode
577 if mode&assign != 0 {
578 emode |= exact
579 }
580 581 // Continue with unaliased types but don't lose original alias names, if any (go.dev/issue/67628).
582 xorig, x := x, Unalias(x)
583 yorig, y := y, Unalias(y)
584 585 switch x := x.(type) {
586 case *Basic:
587 // Basic types are singletons except for the rune and byte
588 // aliases, thus we cannot solely rely on the x == y check
589 // above. See also comment in TypeName.IsAlias.
590 if y, ok := y.(*Basic); ok {
591 return x.kind == y.kind
592 }
593 594 case *Array:
595 // Two array types unify if they have the same array length
596 // and their element types unify.
597 if y, ok := y.(*Array); ok {
598 // If one or both array lengths are unknown (< 0) due to some error,
599 // assume they are the same to avoid spurious follow-on errors.
600 return (x.len < 0 || y.len < 0 || x.len == y.len) && u.nify(x.elem, y.elem, emode, p)
601 }
602 603 case *Slice:
604 // Two slice types unify if their element types unify.
605 if y, ok := y.(*Slice); ok {
606 return u.nify(x.elem, y.elem, emode, p)
607 }
608 609 case *Struct:
610 // Two struct types unify if they have the same sequence of fields,
611 // and if corresponding fields have the same names, their (field) types unify,
612 // and they have identical tags. Two embedded fields are considered to have the same
613 // name. Lower-case field names from different packages are always different.
614 if y, ok := y.(*Struct); ok {
615 if x.NumFields() == y.NumFields() {
616 for i, f := range x.fields {
617 g := y.fields[i]
618 if f.embedded != g.embedded ||
619 x.Tag(i) != y.Tag(i) ||
620 !f.sameId(g.pkg, g.name, false) ||
621 !u.nify(f.typ, g.typ, emode, p) {
622 return false
623 }
624 }
625 return true
626 }
627 }
628 629 case *Pointer:
630 // Two pointer types unify if their base types unify.
631 if y, ok := y.(*Pointer); ok {
632 return u.nify(x.base, y.base, emode, p)
633 }
634 635 case *Tuple:
636 // Two tuples types unify if they have the same number of elements
637 // and the types of corresponding elements unify.
638 if y, ok := y.(*Tuple); ok {
639 if x.Len() == y.Len() {
640 if x != nil {
641 for i, v := range x.vars {
642 w := y.vars[i]
643 if !u.nify(v.typ, w.typ, mode, p) {
644 return false
645 }
646 }
647 }
648 return true
649 }
650 }
651 652 case *Signature:
653 // Two function types unify if they have the same number of parameters
654 // and result values, corresponding parameter and result types unify,
655 // and either both functions are variadic or neither is.
656 // Parameter and result names are not required to match.
657 // TODO(gri) handle type parameters or document why we can ignore them.
658 if y, ok := y.(*Signature); ok {
659 return x.variadic == y.variadic &&
660 u.nify(x.params, y.params, emode, p) &&
661 u.nify(x.results, y.results, emode, p)
662 }
663 664 case *Interface:
665 assert(!u.enableInterfaceInference || mode&exact != 0) // handled before this switch
666 667 // Two interface types unify if they have the same set of methods with
668 // the same names, and corresponding function types unify.
669 // Lower-case method names from different packages are always different.
670 // The order of the methods is irrelevant.
671 if y, ok := y.(*Interface); ok {
672 xset := x.typeSet()
673 yset := y.typeSet()
674 if xset.comparable != yset.comparable {
675 return false
676 }
677 if !xset.terms.equal(yset.terms) {
678 return false
679 }
680 a := xset.methods
681 b := yset.methods
682 if len(a) == len(b) {
683 // Interface types are the only types where cycles can occur
684 // that are not "terminated" via named types; and such cycles
685 // can only be created via method parameter types that are
686 // anonymous interfaces (directly or indirectly) embedding
687 // the current interface. Example:
688 //
689 // type T interface {
690 // m() interface{T}
691 // }
692 //
693 // If two such (differently named) interfaces are compared,
694 // endless recursion occurs if the cycle is not detected.
695 //
696 // If x and y were compared before, they must be equal
697 // (if they were not, the recursion would have stopped);
698 // search the ifacePair stack for the same pair.
699 //
700 // This is a quadratic algorithm, but in practice these stacks
701 // are extremely short (bounded by the nesting depth of interface
702 // type declarations that recur via parameter types, an extremely
703 // rare occurrence). An alternative implementation might use a
704 // "visited" map, but that is probably less efficient overall.
705 q := &ifacePair{x, y, p}
706 for p != nil {
707 if p.identical(q) {
708 return true // same pair was compared before
709 }
710 p = p.prev
711 }
712 if debug {
713 assertSortedMethods(a)
714 assertSortedMethods(b)
715 }
716 for i, f := range a {
717 g := b[i]
718 if f.Id() != g.Id() || !u.nify(f.typ, g.typ, exact, q) {
719 return false
720 }
721 }
722 return true
723 }
724 }
725 726 case *Map:
727 // Two map types unify if their key and value types unify.
728 if y, ok := y.(*Map); ok {
729 return u.nify(x.key, y.key, emode, p) && u.nify(x.elem, y.elem, emode, p)
730 }
731 732 case *Chan:
733 // Two channel types unify if their value types unify
734 // and if they have the same direction.
735 // The channel direction is ignored for inexact unification.
736 if y, ok := y.(*Chan); ok {
737 return (mode&exact == 0 || x.dir == y.dir) && u.nify(x.elem, y.elem, emode, p)
738 }
739 740 case *Named:
741 // Two named types unify if their type names originate in the same type declaration.
742 // If they are instantiated, their type argument lists must unify.
743 if y := asNamed(y); y != nil {
744 // Check type arguments before origins so they unify
745 // even if the origins don't match; for better error
746 // messages (see go.dev/issue/53692).
747 xargs := x.TypeArgs().list()
748 yargs := y.TypeArgs().list()
749 if len(xargs) != len(yargs) {
750 return false
751 }
752 for i, xarg := range xargs {
753 if !u.nify(xarg, yargs[i], mode, p) {
754 return false
755 }
756 }
757 return identicalOrigin(x, y)
758 }
759 760 case *TypeParam:
761 // x must be an unbound type parameter (see comment above).
762 if debug {
763 assert(u.asBoundTypeParam(x) == nil)
764 }
765 // By definition, a valid type argument must be in the type set of
766 // the respective type constraint. Therefore, the type argument's
767 // underlying type must be in the set of underlying types of that
768 // constraint. If there is a single such underlying type, it's the
769 // constraint's core type. It must match the type argument's under-
770 // lying type, irrespective of whether the actual type argument,
771 // which may be a defined type, is actually in the type set (that
772 // will be determined at instantiation time).
773 // Thus, if we have the core type of an unbound type parameter,
774 // we know the structure of the possible types satisfying such
775 // parameters. Use that core type for further unification
776 // (see go.dev/issue/50755 for a test case).
777 if enableCoreTypeUnification {
778 // Because the core type is always an underlying type,
779 // unification will take care of matching against a
780 // defined or literal type automatically.
781 // If y is also an unbound type parameter, we will end
782 // up here again with x and y swapped, so we don't
783 // need to take care of that case separately.
784 if cx, _ := commonUnder(x, nil); cx != nil {
785 if traceInference {
786 u.tracef("core %s ≡ %s", xorig, yorig)
787 }
788 // If y is a defined type, it may not match against cx which
789 // is an underlying type (incl. int, string, etc.). Use assign
790 // mode here so that the unifier automatically takes under(y)
791 // if necessary.
792 return u.nify(cx, yorig, assign, p)
793 }
794 }
795 // x != y and there's nothing to do
796 797 case nil:
798 // avoid a crash in case of nil type
799 800 default:
801 panic(sprintf(nil, nil, true, "u.nify(%s, %s, %d)", xorig, yorig, mode))
802 }
803 804 return false
805 }
806