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