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 "go/token" 12 "sort" 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 bidirection 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 // A unifier maintains the current type parameters for x and y 38 // and the respective types inferred for each type parameter. 39 // A unifier is created by calling newUnifier. 40 type unifier struct { 41 check *Checker 42 exact bool 43 x, y tparamsList // x and y must initialized via tparamsList.init 44 types []Type // inferred types, shared by x and y 45 } 46 47 // newUnifier returns a new unifier. 48 // If exact is set, unification requires unified types to match 49 // exactly. If exact is not set, a named type's underlying type 50 // is considered if unification would fail otherwise, and the 51 // direction of channels is ignored. 52 func newUnifier(check *Checker, exact bool) *unifier { 53 u := &unifier{check: check, exact: exact} 54 u.x.unifier = u 55 u.y.unifier = u 56 return u 57 } 58 59 // unify attempts to unify x and y and reports whether it succeeded. 60 func (u *unifier) unify(x, y Type) bool { 61 return u.nify(x, y, nil) 62 } 63 64 // A tparamsList describes a list of type parameters and the types inferred for them. 65 type tparamsList struct { 66 unifier *unifier 67 tparams []*TypeName 68 // For each tparams element, there is a corresponding type slot index in indices. 69 // index < 0: unifier.types[-index-1] == nil 70 // index == 0: no type slot allocated yet 71 // index > 0: unifier.types[index-1] == typ 72 // Joined tparams elements share the same type slot and thus have the same index. 73 // By using a negative index for nil types we don't need to check unifier.types 74 // to see if we have a type or not. 75 indices []int // len(d.indices) == len(d.tparams) 76 } 77 78 // String returns a string representation for a tparamsList. For debugging. 79 func (d *tparamsList) String() string { 80 var buf bytes.Buffer 81 buf.WriteByte('[') 82 for i, tname := range d.tparams { 83 if i > 0 { 84 buf.WriteString(", ") 85 } 86 writeType(&buf, tname.typ, nil, nil) 87 buf.WriteString(": ") 88 writeType(&buf, d.at(i), nil, nil) 89 } 90 buf.WriteByte(']') 91 return buf.String() 92 } 93 94 // init initializes d with the given type parameters. 95 // The type parameters must be in the order in which they appear in their declaration 96 // (this ensures that the tparams indices match the respective type parameter index). 97 func (d *tparamsList) init(tparams []*TypeName) { 98 if len(tparams) == 0 { 99 return 100 } 101 if debug { 102 for i, tpar := range tparams { 103 assert(i == tpar.typ.(*_TypeParam).index) 104 } 105 } 106 d.tparams = tparams 107 d.indices = make([]int, len(tparams)) 108 } 109 110 // join unifies the i'th type parameter of x with the j'th type parameter of y. 111 // If both type parameters already have a type associated with them and they are 112 // not joined, join fails and return false. 113 func (u *unifier) join(i, j int) bool { 114 ti := u.x.indices[i] 115 tj := u.y.indices[j] 116 switch { 117 case ti == 0 && tj == 0: 118 // Neither type parameter has a type slot associated with them. 119 // Allocate a new joined nil type slot (negative index). 120 u.types = append(u.types, nil) 121 u.x.indices[i] = -len(u.types) 122 u.y.indices[j] = -len(u.types) 123 case ti == 0: 124 // The type parameter for x has no type slot yet. Use slot of y. 125 u.x.indices[i] = tj 126 case tj == 0: 127 // The type parameter for y has no type slot yet. Use slot of x. 128 u.y.indices[j] = ti 129 130 // Both type parameters have a slot: ti != 0 && tj != 0. 131 case ti == tj: 132 // Both type parameters already share the same slot. Nothing to do. 133 break 134 case ti > 0 && tj > 0: 135 // Both type parameters have (possibly different) inferred types. Cannot join. 136 return false 137 case ti > 0: 138 // Only the type parameter for x has an inferred type. Use x slot for y. 139 u.y.setIndex(j, ti) 140 default: 141 // Either the type parameter for y has an inferred type, or neither type 142 // parameter has an inferred type. In either case, use y slot for x. 143 u.x.setIndex(i, tj) 144 } 145 return true 146 } 147 148 // If typ is a type parameter of d, index returns the type parameter index. 149 // Otherwise, the result is < 0. 150 func (d *tparamsList) index(typ Type) int { 151 if t, ok := typ.(*_TypeParam); ok { 152 if i := t.index; i < len(d.tparams) && d.tparams[i].typ == t { 153 return i 154 } 155 } 156 return -1 157 } 158 159 // setIndex sets the type slot index for the i'th type parameter 160 // (and all its joined parameters) to tj. The type parameter 161 // must have a (possibly nil) type slot associated with it. 162 func (d *tparamsList) setIndex(i, tj int) { 163 ti := d.indices[i] 164 assert(ti != 0 && tj != 0) 165 for k, tk := range d.indices { 166 if tk == ti { 167 d.indices[k] = tj 168 } 169 } 170 } 171 172 // at returns the type set for the i'th type parameter; or nil. 173 func (d *tparamsList) at(i int) Type { 174 if ti := d.indices[i]; ti > 0 { 175 return d.unifier.types[ti-1] 176 } 177 return nil 178 } 179 180 // set sets the type typ for the i'th type parameter; 181 // typ must not be nil and it must not have been set before. 182 func (d *tparamsList) set(i int, typ Type) { 183 assert(typ != nil) 184 u := d.unifier 185 switch ti := d.indices[i]; { 186 case ti < 0: 187 u.types[-ti-1] = typ 188 d.setIndex(i, -ti) 189 case ti == 0: 190 u.types = append(u.types, typ) 191 d.indices[i] = len(u.types) 192 default: 193 panic("type already set") 194 } 195 } 196 197 // types returns the list of inferred types (via unification) for the type parameters 198 // described by d, and an index. If all types were inferred, the returned index is < 0. 199 // Otherwise, it is the index of the first type parameter which couldn't be inferred; 200 // i.e., for which list[index] is nil. 201 func (d *tparamsList) types() (list []Type, index int) { 202 list = make([]Type, len(d.tparams)) 203 index = -1 204 for i := range d.tparams { 205 t := d.at(i) 206 list[i] = t 207 if index < 0 && t == nil { 208 index = i 209 } 210 } 211 return 212 } 213 214 func (u *unifier) nifyEq(x, y Type, p *ifacePair) bool { 215 return x == y || u.nify(x, y, p) 216 } 217 218 // nify implements the core unification algorithm which is an 219 // adapted version of Checker.identical0. For changes to that 220 // code the corresponding changes should be made here. 221 // Must not be called directly from outside the unifier. 222 func (u *unifier) nify(x, y Type, p *ifacePair) bool { 223 // types must be expanded for comparison 224 x = expand(x) 225 y = expand(y) 226 227 if !u.exact { 228 // If exact unification is known to fail because we attempt to 229 // match a type name against an unnamed type literal, consider 230 // the underlying type of the named type. 231 // (Subtle: We use isNamed to include any type with a name (incl. 232 // basic types and type parameters. We use asNamed() because we only 233 // want *Named types.) 234 switch { 235 case !isNamed(x) && y != nil && asNamed(y) != nil: 236 return u.nify(x, under(y), p) 237 case x != nil && asNamed(x) != nil && !isNamed(y): 238 return u.nify(under(x), y, p) 239 } 240 } 241 242 // Cases where at least one of x or y is a type parameter. 243 switch i, j := u.x.index(x), u.y.index(y); { 244 case i >= 0 && j >= 0: 245 // both x and y are type parameters 246 if u.join(i, j) { 247 return true 248 } 249 // both x and y have an inferred type - they must match 250 return u.nifyEq(u.x.at(i), u.y.at(j), p) 251 252 case i >= 0: 253 // x is a type parameter, y is not 254 if tx := u.x.at(i); tx != nil { 255 return u.nifyEq(tx, y, p) 256 } 257 // otherwise, infer type from y 258 u.x.set(i, y) 259 return true 260 261 case j >= 0: 262 // y is a type parameter, x is not 263 if ty := u.y.at(j); ty != nil { 264 return u.nifyEq(x, ty, p) 265 } 266 // otherwise, infer type from x 267 u.y.set(j, x) 268 return true 269 } 270 271 // For type unification, do not shortcut (x == y) for identical 272 // types. Instead keep comparing them element-wise to unify the 273 // matching (and equal type parameter types). A simple test case 274 // where this matters is: func f[P any](a P) { f(a) } . 275 276 switch x := x.(type) { 277 case *Basic: 278 // Basic types are singletons except for the rune and byte 279 // aliases, thus we cannot solely rely on the x == y check 280 // above. See also comment in TypeName.IsAlias. 281 if y, ok := y.(*Basic); ok { 282 return x.kind == y.kind 283 } 284 285 case *Array: 286 // Two array types are identical if they have identical element types 287 // and the same array length. 288 if y, ok := y.(*Array); ok { 289 // If one or both array lengths are unknown (< 0) due to some error, 290 // assume they are the same to avoid spurious follow-on errors. 291 return (x.len < 0 || y.len < 0 || x.len == y.len) && u.nify(x.elem, y.elem, p) 292 } 293 294 case *Slice: 295 // Two slice types are identical if they have identical element types. 296 if y, ok := y.(*Slice); ok { 297 return u.nify(x.elem, y.elem, p) 298 } 299 300 case *Struct: 301 // Two struct types are identical if they have the same sequence of fields, 302 // and if corresponding fields have the same names, and identical types, 303 // and identical tags. Two embedded fields are considered to have the same 304 // name. Lower-case field names from different packages are always different. 305 if y, ok := y.(*Struct); ok { 306 if x.NumFields() == y.NumFields() { 307 for i, f := range x.fields { 308 g := y.fields[i] 309 if f.embedded != g.embedded || 310 x.Tag(i) != y.Tag(i) || 311 !f.sameId(g.pkg, g.name) || 312 !u.nify(f.typ, g.typ, p) { 313 return false 314 } 315 } 316 return true 317 } 318 } 319 320 case *Pointer: 321 // Two pointer types are identical if they have identical base types. 322 if y, ok := y.(*Pointer); ok { 323 return u.nify(x.base, y.base, p) 324 } 325 326 case *Tuple: 327 // Two tuples types are identical if they have the same number of elements 328 // and corresponding elements have identical types. 329 if y, ok := y.(*Tuple); ok { 330 if x.Len() == y.Len() { 331 if x != nil { 332 for i, v := range x.vars { 333 w := y.vars[i] 334 if !u.nify(v.typ, w.typ, p) { 335 return false 336 } 337 } 338 } 339 return true 340 } 341 } 342 343 case *Signature: 344 // Two function types are identical if they have the same number of parameters 345 // and result values, corresponding parameter and result types are identical, 346 // and either both functions are variadic or neither is. Parameter and result 347 // names are not required to match. 348 // TODO(gri) handle type parameters or document why we can ignore them. 349 if y, ok := y.(*Signature); ok { 350 return x.variadic == y.variadic && 351 u.nify(x.params, y.params, p) && 352 u.nify(x.results, y.results, p) 353 } 354 355 case *_Sum: 356 // This should not happen with the current internal use of sum types. 357 panic("type inference across sum types not implemented") 358 359 case *Interface: 360 // Two interface types are identical if they have the same set of methods with 361 // the same names and identical function types. Lower-case method names from 362 // different packages are always different. The order of the methods is irrelevant. 363 if y, ok := y.(*Interface); ok { 364 // If identical0 is called (indirectly) via an external API entry point 365 // (such as Identical, IdenticalIgnoreTags, etc.), check is nil. But in 366 // that case, interfaces are expected to be complete and lazy completion 367 // here is not needed. 368 if u.check != nil { 369 u.check.completeInterface(token.NoPos, x) 370 u.check.completeInterface(token.NoPos, y) 371 } 372 a := x.allMethods 373 b := y.allMethods 374 if len(a) == len(b) { 375 // Interface types are the only types where cycles can occur 376 // that are not "terminated" via named types; and such cycles 377 // can only be created via method parameter types that are 378 // anonymous interfaces (directly or indirectly) embedding 379 // the current interface. Example: 380 // 381 // type T interface { 382 // m() interface{T} 383 // } 384 // 385 // If two such (differently named) interfaces are compared, 386 // endless recursion occurs if the cycle is not detected. 387 // 388 // If x and y were compared before, they must be equal 389 // (if they were not, the recursion would have stopped); 390 // search the ifacePair stack for the same pair. 391 // 392 // This is a quadratic algorithm, but in practice these stacks 393 // are extremely short (bounded by the nesting depth of interface 394 // type declarations that recur via parameter types, an extremely 395 // rare occurrence). An alternative implementation might use a 396 // "visited" map, but that is probably less efficient overall. 397 q := &ifacePair{x, y, p} 398 for p != nil { 399 if p.identical(q) { 400 return true // same pair was compared before 401 } 402 p = p.prev 403 } 404 if debug { 405 assert(sort.IsSorted(byUniqueMethodName(a))) 406 assert(sort.IsSorted(byUniqueMethodName(b))) 407 } 408 for i, f := range a { 409 g := b[i] 410 if f.Id() != g.Id() || !u.nify(f.typ, g.typ, q) { 411 return false 412 } 413 } 414 return true 415 } 416 } 417 418 case *Map: 419 // Two map types are identical if they have identical key and value types. 420 if y, ok := y.(*Map); ok { 421 return u.nify(x.key, y.key, p) && u.nify(x.elem, y.elem, p) 422 } 423 424 case *Chan: 425 // Two channel types are identical if they have identical value types. 426 if y, ok := y.(*Chan); ok { 427 return (!u.exact || x.dir == y.dir) && u.nify(x.elem, y.elem, p) 428 } 429 430 case *Named: 431 // Two named types are identical if their type names originate 432 // in the same type declaration. 433 // if y, ok := y.(*Named); ok { 434 // return x.obj == y.obj 435 // } 436 if y, ok := y.(*Named); ok { 437 // TODO(gri) This is not always correct: two types may have the same names 438 // in the same package if one of them is nested in a function. 439 // Extremely unlikely but we need an always correct solution. 440 if x.obj.pkg == y.obj.pkg && x.obj.name == y.obj.name { 441 assert(len(x.targs) == len(y.targs)) 442 for i, x := range x.targs { 443 if !u.nify(x, y.targs[i], p) { 444 return false 445 } 446 } 447 return true 448 } 449 } 450 451 case *_TypeParam: 452 // Two type parameters (which are not part of the type parameters of the 453 // enclosing type as those are handled in the beginning of this function) 454 // are identical if they originate in the same declaration. 455 return x == y 456 457 // case *instance: 458 // unreachable since types are expanded 459 460 case nil: 461 // avoid a crash in case of nil type 462 463 default: 464 u.check.dump("### u.nify(%s, %s), u.x.tparams = %s", x, y, u.x.tparams) 465 unreachable() 466 } 467 468 return false 469 } 470