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 package types 8 9 import ( 10 "bytes" 11 "fmt" 12 "strings" 13 ) 14 15 // The unifier maintains two separate sets of type parameters x and y 16 // which are used to resolve type parameters in the x and y arguments 17 // provided to the unify call. For unidirectional unification, only 18 // one of these sets (say x) is provided, and then type parameters are 19 // only resolved for the x argument passed to unify, not the y argument 20 // (even if that also contains possibly the same type parameters). This 21 // is crucial to infer the type parameters of self-recursive calls: 22 // 23 // func f[P any](a P) { f(a) } 24 // 25 // For the call f(a) we want to infer that the type argument for P is P. 26 // During unification, the parameter type P must be resolved to the type 27 // parameter P ("x" side), but the argument type P must be left alone so 28 // that unification resolves the type parameter P to P. 29 // 30 // For bidirectional unification, both sets are provided. This enables 31 // unification to go from argument to parameter type and vice versa. 32 // For constraint type inference, we use bidirectional unification 33 // where both the x and y type parameters are identical. This is done 34 // by setting up one of them (using init) and then assigning its value 35 // to the other. 36 37 const ( 38 // Upper limit for recursion depth. Used to catch infinite recursions 39 // due to implementation issues (e.g., see issues #48619, #48656). 40 unificationDepthLimit = 50 41 42 // Whether to panic when unificationDepthLimit is reached. 43 // If disabled, a recursion depth overflow results in a (quiet) 44 // unification failure. 45 panicAtUnificationDepthLimit = true 46 47 // If enableCoreTypeUnification is set, unification will consider 48 // the core types, if any, of non-local (unbound) type parameters. 49 enableCoreTypeUnification = true 50 51 // If traceInference is set, unification will print a trace of its operation. 52 // Interpretation of trace: 53 // x ≡ y attempt to unify types x and y 54 // p ➞ y type parameter p is set to type y (p is inferred to be y) 55 // p ⇄ q type parameters p and q match (p is inferred to be q and vice versa) 56 // x ≢ y types x and y cannot be unified 57 // [p, q, ...] ➞ [x, y, ...] mapping from type parameters to types 58 traceInference = false 59 ) 60 61 // A unifier maintains the current type parameters for x and y 62 // and the respective types inferred for each type parameter. 63 // A unifier is created by calling newUnifier. 64 type unifier struct { 65 exact bool 66 x, y tparamsList // x and y must initialized via tparamsList.init 67 types []Type // inferred types, shared by x and y 68 depth int // recursion depth during unification 69 } 70 71 // newUnifier returns a new unifier. 72 // If exact is set, unification requires unified types to match 73 // exactly. If exact is not set, a named type's underlying type 74 // is considered if unification would fail otherwise, and the 75 // direction of channels is ignored. 76 // TODO(gri) exact is not set anymore by a caller. Consider removing it. 77 func newUnifier(exact bool) *unifier { 78 u := &unifier{exact: exact} 79 u.x.unifier = u 80 u.y.unifier = u 81 return u 82 } 83 84 // unify attempts to unify x and y and reports whether it succeeded. 85 func (u *unifier) unify(x, y Type) bool { 86 return u.nify(x, y, nil) 87 } 88 89 func (u *unifier) tracef(format string, args ...interface{}) { 90 fmt.Println(strings.Repeat(". ", u.depth) + sprintf(nil, nil, true, format, args...)) 91 } 92 93 // A tparamsList describes a list of type parameters and the types inferred for them. 94 type tparamsList struct { 95 unifier *unifier 96 tparams []*TypeParam 97 // For each tparams element, there is a corresponding type slot index in indices. 98 // index < 0: unifier.types[-index-1] == nil 99 // index == 0: no type slot allocated yet 100 // index > 0: unifier.types[index-1] == typ 101 // Joined tparams elements share the same type slot and thus have the same index. 102 // By using a negative index for nil types we don't need to check unifier.types 103 // to see if we have a type or not. 104 indices []int // len(d.indices) == len(d.tparams) 105 } 106 107 // String returns a string representation for a tparamsList. For debugging. 108 func (d *tparamsList) String() string { 109 var buf bytes.Buffer 110 w := newTypeWriter(&buf, nil) 111 w.byte('[') 112 for i, tpar := range d.tparams { 113 if i > 0 { 114 w.string(", ") 115 } 116 w.typ(tpar) 117 w.string(": ") 118 w.typ(d.at(i)) 119 } 120 w.byte(']') 121 return buf.String() 122 } 123 124 // init initializes d with the given type parameters. 125 // The type parameters must be in the order in which they appear in their declaration 126 // (this ensures that the tparams indices match the respective type parameter index). 127 func (d *tparamsList) init(tparams []*TypeParam) { 128 if len(tparams) == 0 { 129 return 130 } 131 if debug { 132 for i, tpar := range tparams { 133 assert(i == tpar.index) 134 } 135 } 136 d.tparams = tparams 137 d.indices = make([]int, len(tparams)) 138 } 139 140 // join unifies the i'th type parameter of x with the j'th type parameter of y. 141 // If both type parameters already have a type associated with them and they are 142 // not joined, join fails and returns false. 143 func (u *unifier) join(i, j int) bool { 144 if traceInference { 145 u.tracef("%s ⇄ %s", u.x.tparams[i], u.y.tparams[j]) 146 } 147 ti := u.x.indices[i] 148 tj := u.y.indices[j] 149 switch { 150 case ti == 0 && tj == 0: 151 // Neither type parameter has a type slot associated with them. 152 // Allocate a new joined nil type slot (negative index). 153 u.types = append(u.types, nil) 154 u.x.indices[i] = -len(u.types) 155 u.y.indices[j] = -len(u.types) 156 case ti == 0: 157 // The type parameter for x has no type slot yet. Use slot of y. 158 u.x.indices[i] = tj 159 case tj == 0: 160 // The type parameter for y has no type slot yet. Use slot of x. 161 u.y.indices[j] = ti 162 163 // Both type parameters have a slot: ti != 0 && tj != 0. 164 case ti == tj: 165 // Both type parameters already share the same slot. Nothing to do. 166 break 167 case ti > 0 && tj > 0: 168 // Both type parameters have (possibly different) inferred types. Cannot join. 169 // TODO(gri) Should we check if types are identical? Investigate. 170 return false 171 case ti > 0: 172 // Only the type parameter for x has an inferred type. Use x slot for y. 173 u.y.setIndex(j, ti) 174 // This case is handled like the default case. 175 // case tj > 0: 176 // // Only the type parameter for y has an inferred type. Use y slot for x. 177 // u.x.setIndex(i, tj) 178 default: 179 // Neither type parameter has an inferred type. Use y slot for x 180 // (or x slot for y, it doesn't matter). 181 u.x.setIndex(i, tj) 182 } 183 return true 184 } 185 186 // If typ is a type parameter of d, index returns the type parameter index. 187 // Otherwise, the result is < 0. 188 func (d *tparamsList) index(typ Type) int { 189 if tpar, ok := typ.(*TypeParam); ok { 190 return tparamIndex(d.tparams, tpar) 191 } 192 return -1 193 } 194 195 // If tpar is a type parameter in list, tparamIndex returns the type parameter index. 196 // Otherwise, the result is < 0. tpar must not be nil. 197 func tparamIndex(list []*TypeParam, tpar *TypeParam) int { 198 // Once a type parameter is bound its index is >= 0. However, there are some 199 // code paths (namely tracing and type hashing) by which it is possible to 200 // arrive here with a type parameter that has not been bound, hence the check 201 // for 0 <= i below. 202 // TODO(rfindley): investigate a better approach for guarding against using 203 // unbound type parameters. 204 if i := tpar.index; 0 <= i && i < len(list) && list[i] == tpar { 205 return i 206 } 207 return -1 208 } 209 210 // setIndex sets the type slot index for the i'th type parameter 211 // (and all its joined parameters) to tj. The type parameter 212 // must have a (possibly nil) type slot associated with it. 213 func (d *tparamsList) setIndex(i, tj int) { 214 ti := d.indices[i] 215 assert(ti != 0 && tj != 0) 216 for k, tk := range d.indices { 217 if tk == ti { 218 d.indices[k] = tj 219 } 220 } 221 } 222 223 // at returns the type set for the i'th type parameter; or nil. 224 func (d *tparamsList) at(i int) Type { 225 if ti := d.indices[i]; ti > 0 { 226 return d.unifier.types[ti-1] 227 } 228 return nil 229 } 230 231 // set sets the type typ for the i'th type parameter; 232 // typ must not be nil and it must not have been set before. 233 func (d *tparamsList) set(i int, typ Type) { 234 assert(typ != nil) 235 u := d.unifier 236 if traceInference { 237 u.tracef("%s ➞ %s", d.tparams[i], typ) 238 } 239 switch ti := d.indices[i]; { 240 case ti < 0: 241 u.types[-ti-1] = typ 242 d.setIndex(i, -ti) 243 case ti == 0: 244 u.types = append(u.types, typ) 245 d.indices[i] = len(u.types) 246 default: 247 panic("type already set") 248 } 249 } 250 251 // unknowns returns the number of type parameters for which no type has been set yet. 252 func (d *tparamsList) unknowns() int { 253 n := 0 254 for _, ti := range d.indices { 255 if ti <= 0 { 256 n++ 257 } 258 } 259 return n 260 } 261 262 // types returns the list of inferred types (via unification) for the type parameters 263 // described by d, and an index. If all types were inferred, the returned index is < 0. 264 // Otherwise, it is the index of the first type parameter which couldn't be inferred; 265 // i.e., for which list[index] is nil. 266 func (d *tparamsList) types() (list []Type, index int) { 267 list = make([]Type, len(d.tparams)) 268 index = -1 269 for i := range d.tparams { 270 t := d.at(i) 271 list[i] = t 272 if index < 0 && t == nil { 273 index = i 274 } 275 } 276 return 277 } 278 279 func (u *unifier) nifyEq(x, y Type, p *ifacePair) bool { 280 return x == y || u.nify(x, y, p) 281 } 282 283 // nify implements the core unification algorithm which is an 284 // adapted version of Checker.identical. For changes to that 285 // code the corresponding changes should be made here. 286 // Must not be called directly from outside the unifier. 287 func (u *unifier) nify(x, y Type, p *ifacePair) (result bool) { 288 if traceInference { 289 u.tracef("%s ≡ %s", x, y) 290 } 291 292 // Stop gap for cases where unification fails. 293 if u.depth >= unificationDepthLimit { 294 if traceInference { 295 u.tracef("depth %d >= %d", u.depth, unificationDepthLimit) 296 } 297 if panicAtUnificationDepthLimit { 298 panic("unification reached recursion depth limit") 299 } 300 return false 301 } 302 u.depth++ 303 defer func() { 304 u.depth-- 305 if traceInference && !result { 306 u.tracef("%s ≢ %s", x, y) 307 } 308 }() 309 310 if !u.exact { 311 // If exact unification is known to fail because we attempt to 312 // match a type name against an unnamed type literal, consider 313 // the underlying type of the named type. 314 // (We use !hasName to exclude any type with a name, including 315 // basic types and type parameters; the rest are unamed types.) 316 if nx, _ := x.(*Named); nx != nil && !hasName(y) { 317 if traceInference { 318 u.tracef("under %s ≡ %s", nx, y) 319 } 320 return u.nify(nx.under(), y, p) 321 } else if ny, _ := y.(*Named); ny != nil && !hasName(x) { 322 if traceInference { 323 u.tracef("%s ≡ under %s", x, ny) 324 } 325 return u.nify(x, ny.under(), p) 326 } 327 } 328 329 // Cases where at least one of x or y is a type parameter. 330 switch i, j := u.x.index(x), u.y.index(y); { 331 case i >= 0 && j >= 0: 332 // both x and y are type parameters 333 if u.join(i, j) { 334 return true 335 } 336 // both x and y have an inferred type - they must match 337 return u.nifyEq(u.x.at(i), u.y.at(j), p) 338 339 case i >= 0: 340 // x is a type parameter, y is not 341 if tx := u.x.at(i); tx != nil { 342 return u.nifyEq(tx, y, p) 343 } 344 // otherwise, infer type from y 345 u.x.set(i, y) 346 return true 347 348 case j >= 0: 349 // y is a type parameter, x is not 350 if ty := u.y.at(j); ty != nil { 351 return u.nifyEq(x, ty, p) 352 } 353 // otherwise, infer type from x 354 u.y.set(j, x) 355 return true 356 } 357 358 // If we get here and x or y is a type parameter, they are type parameters 359 // from outside our declaration list. Try to unify their core types, if any 360 // (see issue #50755 for a test case). 361 if enableCoreTypeUnification && !u.exact { 362 if isTypeParam(x) && !hasName(y) { 363 // When considering the type parameter for unification 364 // we look at the adjusted core term (adjusted core type 365 // with tilde information). 366 // If the adjusted core type is a named type N; the 367 // corresponding core type is under(N). Since !u.exact 368 // and y doesn't have a name, unification will end up 369 // comparing under(N) to y, so we can just use the core 370 // type instead. And we can ignore the tilde because we 371 // already look at the underlying types on both sides 372 // and we have known types on both sides. 373 // Optimization. 374 if cx := coreType(x); cx != nil { 375 if traceInference { 376 u.tracef("core %s ≡ %s", x, y) 377 } 378 return u.nify(cx, y, p) 379 } 380 } else if isTypeParam(y) && !hasName(x) { 381 // see comment above 382 if cy := coreType(y); cy != nil { 383 if traceInference { 384 u.tracef("%s ≡ core %s", x, y) 385 } 386 return u.nify(x, cy, p) 387 } 388 } 389 } 390 391 // For type unification, do not shortcut (x == y) for identical 392 // types. Instead keep comparing them element-wise to unify the 393 // matching (and equal type parameter types). A simple test case 394 // where this matters is: func f[P any](a P) { f(a) } . 395 396 switch x := x.(type) { 397 case *Basic: 398 // Basic types are singletons except for the rune and byte 399 // aliases, thus we cannot solely rely on the x == y check 400 // above. See also comment in TypeName.IsAlias. 401 if y, ok := y.(*Basic); ok { 402 return x.kind == y.kind 403 } 404 405 case *Array: 406 // Two array types are identical if they have identical element types 407 // and the same array length. 408 if y, ok := y.(*Array); ok { 409 // If one or both array lengths are unknown (< 0) due to some error, 410 // assume they are the same to avoid spurious follow-on errors. 411 return (x.len < 0 || y.len < 0 || x.len == y.len) && u.nify(x.elem, y.elem, p) 412 } 413 414 case *Slice: 415 // Two slice types are identical if they have identical element types. 416 if y, ok := y.(*Slice); ok { 417 return u.nify(x.elem, y.elem, p) 418 } 419 420 case *Struct: 421 // Two struct types are identical if they have the same sequence of fields, 422 // and if corresponding fields have the same names, and identical types, 423 // and identical tags. Two embedded fields are considered to have the same 424 // name. Lower-case field names from different packages are always different. 425 if y, ok := y.(*Struct); ok { 426 if x.NumFields() == y.NumFields() { 427 for i, f := range x.fields { 428 g := y.fields[i] 429 if f.embedded != g.embedded || 430 x.Tag(i) != y.Tag(i) || 431 !f.sameId(g.pkg, g.name) || 432 !u.nify(f.typ, g.typ, p) { 433 return false 434 } 435 } 436 return true 437 } 438 } 439 440 case *Pointer: 441 // Two pointer types are identical if they have identical base types. 442 if y, ok := y.(*Pointer); ok { 443 return u.nify(x.base, y.base, p) 444 } 445 446 case *Tuple: 447 // Two tuples types are identical if they have the same number of elements 448 // and corresponding elements have identical types. 449 if y, ok := y.(*Tuple); ok { 450 if x.Len() == y.Len() { 451 if x != nil { 452 for i, v := range x.vars { 453 w := y.vars[i] 454 if !u.nify(v.typ, w.typ, p) { 455 return false 456 } 457 } 458 } 459 return true 460 } 461 } 462 463 case *Signature: 464 // Two function types are identical if they have the same number of parameters 465 // and result values, corresponding parameter and result types are identical, 466 // and either both functions are variadic or neither is. Parameter and result 467 // names are not required to match. 468 // TODO(gri) handle type parameters or document why we can ignore them. 469 if y, ok := y.(*Signature); ok { 470 return x.variadic == y.variadic && 471 u.nify(x.params, y.params, p) && 472 u.nify(x.results, y.results, p) 473 } 474 475 case *Interface: 476 // Two interface types are identical if they have the same set of methods with 477 // the same names and identical function types. Lower-case method names from 478 // different packages are always different. The order of the methods is irrelevant. 479 if y, ok := y.(*Interface); ok { 480 xset := x.typeSet() 481 yset := y.typeSet() 482 if xset.comparable != yset.comparable { 483 return false 484 } 485 if !xset.terms.equal(yset.terms) { 486 return false 487 } 488 a := xset.methods 489 b := yset.methods 490 if len(a) == len(b) { 491 // Interface types are the only types where cycles can occur 492 // that are not "terminated" via named types; and such cycles 493 // can only be created via method parameter types that are 494 // anonymous interfaces (directly or indirectly) embedding 495 // the current interface. Example: 496 // 497 // type T interface { 498 // m() interface{T} 499 // } 500 // 501 // If two such (differently named) interfaces are compared, 502 // endless recursion occurs if the cycle is not detected. 503 // 504 // If x and y were compared before, they must be equal 505 // (if they were not, the recursion would have stopped); 506 // search the ifacePair stack for the same pair. 507 // 508 // This is a quadratic algorithm, but in practice these stacks 509 // are extremely short (bounded by the nesting depth of interface 510 // type declarations that recur via parameter types, an extremely 511 // rare occurrence). An alternative implementation might use a 512 // "visited" map, but that is probably less efficient overall. 513 q := &ifacePair{x, y, p} 514 for p != nil { 515 if p.identical(q) { 516 return true // same pair was compared before 517 } 518 p = p.prev 519 } 520 if debug { 521 assertSortedMethods(a) 522 assertSortedMethods(b) 523 } 524 for i, f := range a { 525 g := b[i] 526 if f.Id() != g.Id() || !u.nify(f.typ, g.typ, q) { 527 return false 528 } 529 } 530 return true 531 } 532 } 533 534 case *Map: 535 // Two map types are identical if they have identical key and value types. 536 if y, ok := y.(*Map); ok { 537 return u.nify(x.key, y.key, p) && u.nify(x.elem, y.elem, p) 538 } 539 540 case *Chan: 541 // Two channel types are identical if they have identical value types. 542 if y, ok := y.(*Chan); ok { 543 return (!u.exact || x.dir == y.dir) && u.nify(x.elem, y.elem, p) 544 } 545 546 case *Named: 547 // TODO(gri) This code differs now from the parallel code in Checker.identical. Investigate. 548 if y, ok := y.(*Named); ok { 549 xargs := x.TypeArgs().list() 550 yargs := y.TypeArgs().list() 551 552 if len(xargs) != len(yargs) { 553 return false 554 } 555 556 // TODO(gri) This is not always correct: two types may have the same names 557 // in the same package if one of them is nested in a function. 558 // Extremely unlikely but we need an always correct solution. 559 if x.obj.pkg == y.obj.pkg && x.obj.name == y.obj.name { 560 for i, x := range xargs { 561 if !u.nify(x, yargs[i], p) { 562 return false 563 } 564 } 565 return true 566 } 567 } 568 569 case *TypeParam: 570 // Two type parameters (which are not part of the type parameters of the 571 // enclosing type as those are handled in the beginning of this function) 572 // are identical if they originate in the same declaration. 573 return x == y 574 575 case nil: 576 // avoid a crash in case of nil type 577 578 default: 579 panic(sprintf(nil, nil, true, "u.nify(%s, %s), u.x.tparams = %s", x, y, u.x.tparams)) 580 } 581 582 return false 583 } 584