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