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 "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 // asTypeParam returns x.(*TypeParam) if x is a type parameter recorded with u. 212 // Otherwise, the result is nil. 213 func (u *unifier) asTypeParam(x Type) *TypeParam { 214 if x, _ := 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 := 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 x = Unalias(x) 298 y = Unalias(y) 299 300 // nothing to do if x == y 301 if x == y { 302 return true 303 } 304 305 // Stop gap for cases where unification fails. 306 if u.depth > unificationDepthLimit { 307 if traceInference { 308 u.tracef("depth %d >= %d", u.depth, unificationDepthLimit) 309 } 310 if panicAtUnificationDepthLimit { 311 panic("unification reached recursion depth limit") 312 } 313 return false 314 } 315 316 // Unification is symmetric, so we can swap the operands. 317 // Ensure that if we have at least one 318 // - defined type, make sure one is in y 319 // - type parameter recorded with u, make sure one is in x 320 if asNamed(x) != nil || u.asTypeParam(y) != nil { 321 if traceInference { 322 u.tracef("%s ≡ %s\t// swap", y, x) 323 } 324 x, y = y, x 325 } 326 327 // Unification will fail if we match a defined type against a type literal. 328 // If we are matching types in an assignment, at the top-level, types with 329 // the same type structure are permitted as long as at least one of them 330 // is not a defined type. To accommodate for that possibility, we continue 331 // unification with the underlying type of a defined type if the other type 332 // is a type literal. This is controlled by the exact unification mode. 333 // We also continue if the other type is a basic type because basic types 334 // are valid underlying types and may appear as core types of type constraints. 335 // If we exclude them, inferred defined types for type parameters may not 336 // match against the core types of their constraints (even though they might 337 // correctly match against some of the types in the constraint's type set). 338 // Finally, if unification (incorrectly) succeeds by matching the underlying 339 // type of a defined type against a basic type (because we include basic types 340 // as type literals here), and if that leads to an incorrectly inferred type, 341 // we will fail at function instantiation or argument assignment time. 342 // 343 // If we have at least one defined type, there is one in y. 344 if ny := asNamed(y); mode&exact == 0 && ny != nil && isTypeLit(x) && !(u.enableInterfaceInference && IsInterface(x)) { 345 if traceInference { 346 u.tracef("%s ≡ under %s", x, ny) 347 } 348 y = ny.under() 349 // Per the spec, a defined type cannot have an underlying type 350 // that is a type parameter. 351 assert(!isTypeParam(y)) 352 // x and y may be identical now 353 if x == y { 354 return true 355 } 356 } 357 358 // Cases where at least one of x or y is a type parameter recorded with u. 359 // If we have at least one type parameter, there is one in x. 360 // If we have exactly one type parameter, because it is in x, 361 // isTypeLit(x) is false and y was not changed above. In other 362 // words, if y was a defined type, it is still a defined type 363 // (relevant for the logic below). 364 switch px, py := u.asTypeParam(x), u.asTypeParam(y); { 365 case px != nil && py != nil: 366 // both x and y are type parameters 367 if u.join(px, py) { 368 return true 369 } 370 // both x and y have an inferred type - they must match 371 return u.nify(u.at(px), u.at(py), mode, p) 372 373 case px != nil: 374 // x is a type parameter, y is not 375 if x := u.at(px); x != nil { 376 // x has an inferred type which must match y 377 if u.nify(x, y, mode, p) { 378 // We have a match, possibly through underlying types. 379 xi := asInterface(x) 380 yi := asInterface(y) 381 xn := asNamed(x) != nil 382 yn := asNamed(y) != nil 383 // If we have two interfaces, what to do depends on 384 // whether they are named and their method sets. 385 if xi != nil && yi != nil { 386 // Both types are interfaces. 387 // If both types are defined types, they must be identical 388 // because unification doesn't know which type has the "right" name. 389 if xn && yn { 390 return Identical(x, y) 391 } 392 // In all other cases, the method sets must match. 393 // The types unified so we know that corresponding methods 394 // match and we can simply compare the number of methods. 395 // TODO(gri) We may be able to relax this rule and select 396 // the more general interface. But if one of them is a defined 397 // type, it's not clear how to choose and whether we introduce 398 // an order dependency or not. Requiring the same method set 399 // is conservative. 400 if len(xi.typeSet().methods) != len(yi.typeSet().methods) { 401 return false 402 } 403 } else if xi != nil || yi != nil { 404 // One but not both of them are interfaces. 405 // In this case, either x or y could be viable matches for the corresponding 406 // type parameter, which means choosing either introduces an order dependence. 407 // Therefore, we must fail unification (go.dev/issue/60933). 408 return false 409 } 410 // If we have inexact unification and one of x or y is a defined type, select the 411 // defined type. This ensures that in a series of types, all matching against the 412 // same type parameter, we infer a defined type if there is one, independent of 413 // order. Type inference or assignment may fail, which is ok. 414 // Selecting a defined type, if any, ensures that we don't lose the type name; 415 // and since we have inexact unification, a value of equally named or matching 416 // undefined type remains assignable (go.dev/issue/43056). 417 // 418 // Similarly, if we have inexact unification and there are no defined types but 419 // channel types, select a directed channel, if any. This ensures that in a series 420 // of unnamed types, all matching against the same type parameter, we infer the 421 // directed channel if there is one, independent of order. 422 // Selecting a directional channel, if any, ensures that a value of another 423 // inexactly unifying channel type remains assignable (go.dev/issue/62157). 424 // 425 // If we have multiple defined channel types, they are either identical or we 426 // have assignment conflicts, so we can ignore directionality in this case. 427 // 428 // If we have defined and literal channel types, a defined type wins to avoid 429 // order dependencies. 430 if mode&exact == 0 { 431 switch { 432 case xn: 433 // x is a defined type: nothing to do. 434 case yn: 435 // x is not a defined type and y is a defined type: select y. 436 u.set(px, y) 437 default: 438 // Neither x nor y are defined types. 439 if yc, _ := under(y).(*Chan); yc != nil && yc.dir != SendRecv { 440 // y is a directed channel type: select y. 441 u.set(px, y) 442 } 443 } 444 } 445 return true 446 } 447 return false 448 } 449 // otherwise, infer type from y 450 u.set(px, y) 451 return true 452 } 453 454 // x != y if we get here 455 assert(x != y) 456 457 // If u.EnableInterfaceInference is set and we don't require exact unification, 458 // if both types are interfaces, one interface must have a subset of the 459 // methods of the other and corresponding method signatures must unify. 460 // If only one type is an interface, all its methods must be present in the 461 // other type and corresponding method signatures must unify. 462 if u.enableInterfaceInference && mode&exact == 0 { 463 // One or both interfaces may be defined types. 464 // Look under the name, but not under type parameters (go.dev/issue/60564). 465 xi := asInterface(x) 466 yi := asInterface(y) 467 // If we have two interfaces, check the type terms for equivalence, 468 // and unify common methods if possible. 469 if xi != nil && yi != nil { 470 xset := xi.typeSet() 471 yset := yi.typeSet() 472 if xset.comparable != yset.comparable { 473 return false 474 } 475 // For now we require terms to be equal. 476 // We should be able to relax this as well, eventually. 477 if !xset.terms.equal(yset.terms) { 478 return false 479 } 480 // Interface types are the only types where cycles can occur 481 // that are not "terminated" via named types; and such cycles 482 // can only be created via method parameter types that are 483 // anonymous interfaces (directly or indirectly) embedding 484 // the current interface. Example: 485 // 486 // type T interface { 487 // m() interface{T} 488 // } 489 // 490 // If two such (differently named) interfaces are compared, 491 // endless recursion occurs if the cycle is not detected. 492 // 493 // If x and y were compared before, they must be equal 494 // (if they were not, the recursion would have stopped); 495 // search the ifacePair stack for the same pair. 496 // 497 // This is a quadratic algorithm, but in practice these stacks 498 // are extremely short (bounded by the nesting depth of interface 499 // type declarations that recur via parameter types, an extremely 500 // rare occurrence). An alternative implementation might use a 501 // "visited" map, but that is probably less efficient overall. 502 q := &ifacePair{xi, yi, p} 503 for p != nil { 504 if p.identical(q) { 505 return true // same pair was compared before 506 } 507 p = p.prev 508 } 509 // The method set of x must be a subset of the method set 510 // of y or vice versa, and the common methods must unify. 511 xmethods := xset.methods 512 ymethods := yset.methods 513 // The smaller method set must be the subset, if it exists. 514 if len(xmethods) > len(ymethods) { 515 xmethods, ymethods = ymethods, xmethods 516 } 517 // len(xmethods) <= len(ymethods) 518 // Collect the ymethods in a map for quick lookup. 519 ymap := make(map[string]*Func, len(ymethods)) 520 for _, ym := range ymethods { 521 ymap[ym.Id()] = ym 522 } 523 // All xmethods must exist in ymethods and corresponding signatures must unify. 524 for _, xm := range xmethods { 525 if ym := ymap[xm.Id()]; ym == nil || !u.nify(xm.typ, ym.typ, exact, p) { 526 return false 527 } 528 } 529 return true 530 } 531 532 // We don't have two interfaces. If we have one, make sure it's in xi. 533 if yi != nil { 534 xi = yi 535 y = x 536 } 537 538 // If we have one interface, at a minimum each of the interface methods 539 // must be implemented and thus unify with a corresponding method from 540 // the non-interface type, otherwise unification fails. 541 if xi != nil { 542 // All xi methods must exist in y and corresponding signatures must unify. 543 xmethods := xi.typeSet().methods 544 for _, xm := range xmethods { 545 obj, _, _ := LookupFieldOrMethod(y, false, xm.pkg, xm.name) 546 if ym, _ := obj.(*Func); ym == nil || !u.nify(xm.typ, ym.typ, exact, p) { 547 return false 548 } 549 } 550 return true 551 } 552 } 553 554 // Unless we have exact unification, neither x nor y are interfaces now. 555 // Except for unbound type parameters (see below), x and y must be structurally 556 // equivalent to unify. 557 558 // If we get here and x or y is a type parameter, they are unbound 559 // (not recorded with the unifier). 560 // Ensure that if we have at least one type parameter, it is in x 561 // (the earlier swap checks for _recorded_ type parameters only). 562 // This ensures that the switch switches on the type parameter. 563 // 564 // TODO(gri) Factor out type parameter handling from the switch. 565 if isTypeParam(y) { 566 if traceInference { 567 u.tracef("%s ≡ %s\t// swap", y, x) 568 } 569 x, y = y, x 570 } 571 572 // Type elements (array, slice, etc. elements) use emode for unification. 573 // Element types must match exactly if the types are used in an assignment. 574 emode := mode 575 if mode&assign != 0 { 576 emode |= exact 577 } 578 579 switch x := x.(type) { 580 case *Basic: 581 // Basic types are singletons except for the rune and byte 582 // aliases, thus we cannot solely rely on the x == y check 583 // above. See also comment in TypeName.IsAlias. 584 if y, ok := y.(*Basic); ok { 585 return x.kind == y.kind 586 } 587 588 case *Array: 589 // Two array types unify if they have the same array length 590 // and their element types unify. 591 if y, ok := y.(*Array); ok { 592 // If one or both array lengths are unknown (< 0) due to some error, 593 // assume they are the same to avoid spurious follow-on errors. 594 return (x.len < 0 || y.len < 0 || x.len == y.len) && u.nify(x.elem, y.elem, emode, p) 595 } 596 597 case *Slice: 598 // Two slice types unify if their element types unify. 599 if y, ok := y.(*Slice); ok { 600 return u.nify(x.elem, y.elem, emode, p) 601 } 602 603 case *Struct: 604 // Two struct types unify if they have the same sequence of fields, 605 // and if corresponding fields have the same names, their (field) types unify, 606 // and they have identical tags. Two embedded fields are considered to have the same 607 // name. Lower-case field names from different packages are always different. 608 if y, ok := y.(*Struct); ok { 609 if x.NumFields() == y.NumFields() { 610 for i, f := range x.fields { 611 g := y.fields[i] 612 if f.embedded != g.embedded || 613 x.Tag(i) != y.Tag(i) || 614 !f.sameId(g.pkg, g.name, false) || 615 !u.nify(f.typ, g.typ, emode, p) { 616 return false 617 } 618 } 619 return true 620 } 621 } 622 623 case *Pointer: 624 // Two pointer types unify if their base types unify. 625 if y, ok := y.(*Pointer); ok { 626 return u.nify(x.base, y.base, emode, p) 627 } 628 629 case *Tuple: 630 // Two tuples types unify if they have the same number of elements 631 // and the types of corresponding elements unify. 632 if y, ok := y.(*Tuple); ok { 633 if x.Len() == y.Len() { 634 if x != nil { 635 for i, v := range x.vars { 636 w := y.vars[i] 637 if !u.nify(v.typ, w.typ, mode, p) { 638 return false 639 } 640 } 641 } 642 return true 643 } 644 } 645 646 case *Signature: 647 // Two function types unify if they have the same number of parameters 648 // and result values, corresponding parameter and result types unify, 649 // and either both functions are variadic or neither is. 650 // Parameter and result names are not required to match. 651 // TODO(gri) handle type parameters or document why we can ignore them. 652 if y, ok := y.(*Signature); ok { 653 return x.variadic == y.variadic && 654 u.nify(x.params, y.params, emode, p) && 655 u.nify(x.results, y.results, emode, p) 656 } 657 658 case *Interface: 659 assert(!u.enableInterfaceInference || mode&exact != 0) // handled before this switch 660 661 // Two interface types unify if they have the same set of methods with 662 // the same names, and corresponding function types unify. 663 // Lower-case method names from different packages are always different. 664 // The order of the methods is irrelevant. 665 if y, ok := y.(*Interface); ok { 666 xset := x.typeSet() 667 yset := y.typeSet() 668 if xset.comparable != yset.comparable { 669 return false 670 } 671 if !xset.terms.equal(yset.terms) { 672 return false 673 } 674 a := xset.methods 675 b := yset.methods 676 if len(a) == len(b) { 677 // Interface types are the only types where cycles can occur 678 // that are not "terminated" via named types; and such cycles 679 // can only be created via method parameter types that are 680 // anonymous interfaces (directly or indirectly) embedding 681 // the current interface. Example: 682 // 683 // type T interface { 684 // m() interface{T} 685 // } 686 // 687 // If two such (differently named) interfaces are compared, 688 // endless recursion occurs if the cycle is not detected. 689 // 690 // If x and y were compared before, they must be equal 691 // (if they were not, the recursion would have stopped); 692 // search the ifacePair stack for the same pair. 693 // 694 // This is a quadratic algorithm, but in practice these stacks 695 // are extremely short (bounded by the nesting depth of interface 696 // type declarations that recur via parameter types, an extremely 697 // rare occurrence). An alternative implementation might use a 698 // "visited" map, but that is probably less efficient overall. 699 q := &ifacePair{x, y, p} 700 for p != nil { 701 if p.identical(q) { 702 return true // same pair was compared before 703 } 704 p = p.prev 705 } 706 if debug { 707 assertSortedMethods(a) 708 assertSortedMethods(b) 709 } 710 for i, f := range a { 711 g := b[i] 712 if f.Id() != g.Id() || !u.nify(f.typ, g.typ, exact, q) { 713 return false 714 } 715 } 716 return true 717 } 718 } 719 720 case *Map: 721 // Two map types unify if their key and value types unify. 722 if y, ok := y.(*Map); ok { 723 return u.nify(x.key, y.key, emode, p) && u.nify(x.elem, y.elem, emode, p) 724 } 725 726 case *Chan: 727 // Two channel types unify if their value types unify 728 // and if they have the same direction. 729 // The channel direction is ignored for inexact unification. 730 if y, ok := y.(*Chan); ok { 731 return (mode&exact == 0 || x.dir == y.dir) && u.nify(x.elem, y.elem, emode, p) 732 } 733 734 case *Named: 735 // Two named types unify if their type names originate in the same type declaration. 736 // If they are instantiated, their type argument lists must unify. 737 if y := asNamed(y); y != nil { 738 // Check type arguments before origins so they unify 739 // even if the origins don't match; for better error 740 // messages (see go.dev/issue/53692). 741 xargs := x.TypeArgs().list() 742 yargs := y.TypeArgs().list() 743 if len(xargs) != len(yargs) { 744 return false 745 } 746 for i, xarg := range xargs { 747 if !u.nify(xarg, yargs[i], mode, p) { 748 return false 749 } 750 } 751 return identicalOrigin(x, y) 752 } 753 754 case *TypeParam: 755 // x must be an unbound type parameter (see comment above). 756 if debug { 757 assert(u.asTypeParam(x) == nil) 758 } 759 // By definition, a valid type argument must be in the type set of 760 // the respective type constraint. Therefore, the type argument's 761 // underlying type must be in the set of underlying types of that 762 // constraint. If there is a single such underlying type, it's the 763 // constraint's core type. It must match the type argument's under- 764 // lying type, irrespective of whether the actual type argument, 765 // which may be a defined type, is actually in the type set (that 766 // will be determined at instantiation time). 767 // Thus, if we have the core type of an unbound type parameter, 768 // we know the structure of the possible types satisfying such 769 // parameters. Use that core type for further unification 770 // (see go.dev/issue/50755 for a test case). 771 if enableCoreTypeUnification { 772 // Because the core type is always an underlying type, 773 // unification will take care of matching against a 774 // defined or literal type automatically. 775 // If y is also an unbound type parameter, we will end 776 // up here again with x and y swapped, so we don't 777 // need to take care of that case separately. 778 if cx := coreType(x); cx != nil { 779 if traceInference { 780 u.tracef("core %s ≡ %s", x, y) 781 } 782 // If y is a defined type, it may not match against cx which 783 // is an underlying type (incl. int, string, etc.). Use assign 784 // mode here so that the unifier automatically takes under(y) 785 // if necessary. 786 return u.nify(cx, y, assign, p) 787 } 788 } 789 // x != y and there's nothing to do 790 791 case nil: 792 // avoid a crash in case of nil type 793 794 default: 795 panic(sprintf(nil, nil, true, "u.nify(%s, %s, %d)", x, y, mode)) 796 } 797 798 return false 799 } 800