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.
5 // This file implements type unification.
11 // The unifier maintains two separate sets of type parameters x and y
12 // which are used to resolve type parameters in the x and y arguments
13 // provided to the unify call. For unidirectional unification, only
14 // one of these sets (say x) is provided, and then type parameters are
15 // only resolved for the x argument passed to unify, not the y argument
16 // (even if that also contains possibly the same type parameters). This
17 // is crucial to infer the type parameters of self-recursive calls:
19 // func f[P any](a P) { f(a) }
21 // For the call f(a) we want to infer that the type argument for P is P.
22 // During unification, the parameter type P must be resolved to the type
23 // parameter P ("x" side), but the argument type P must be left alone so
24 // that unification resolves the type parameter P to P.
26 // For bidirection unification, both sets are provided. This enables
27 // unification to go from argument to parameter type and vice versa.
28 // For constraint type inference, we use bidirectional unification
29 // where both the x and y type parameters are identical. This is done
30 // by setting up one of them (using init) and then assigning its value
33 // A unifier maintains the current type parameters for x and y
34 // and the respective types inferred for each type parameter.
35 // A unifier is created by calling newUnifier.
39 x, y tparamsList // x and y must initialized via tparamsList.init
40 types []Type // inferred types, shared by x and y
43 // newUnifier returns a new unifier.
44 // If exact is set, unification requires unified types to match
45 // exactly. If exact is not set, a named type's underlying type
46 // is considered if unification would fail otherwise, and the
47 // direction of channels is ignored.
48 func newUnifier(check *Checker, exact bool) *unifier {
49 u := &unifier{check: check, exact: exact}
55 // unify attempts to unify x and y and reports whether it succeeded.
56 func (u *unifier) unify(x, y Type) bool {
57 return u.nify(x, y, nil)
60 // A tparamsList describes a list of type parameters and the types inferred for them.
61 type tparamsList struct {
64 // For each tparams element, there is a corresponding type slot index in indices.
65 // index < 0: unifier.types[-index-1] == nil
66 // index == 0: no type slot allocated yet
67 // index > 0: unifier.types[index-1] == typ
68 // Joined tparams elements share the same type slot and thus have the same index.
69 // By using a negative index for nil types we don't need to check unifier.types
70 // to see if we have a type or not.
71 indices []int // len(d.indices) == len(d.tparams)
74 // String returns a string representation for a tparamsList. For debugging.
75 func (d *tparamsList) String() string {
78 for i, tname := range d.tparams {
82 writeType(&buf, tname.typ, nil, nil)
84 writeType(&buf, d.at(i), nil, nil)
90 // init initializes d with the given type parameters.
91 // The type parameters must be in the order in which they appear in their declaration
92 // (this ensures that the tparams indices match the respective type parameter index).
93 func (d *tparamsList) init(tparams []*TypeName) {
94 if len(tparams) == 0 {
98 for i, tpar := range tparams {
99 assert(i == tpar.typ.(*TypeParam).index)
103 d.indices = make([]int, len(tparams))
106 // join unifies the i'th type parameter of x with the j'th type parameter of y.
107 // If both type parameters already have a type associated with them and they are
108 // not joined, join fails and return false.
109 func (u *unifier) join(i, j int) bool {
113 case ti == 0 && tj == 0:
114 // Neither type parameter has a type slot associated with them.
115 // Allocate a new joined nil type slot (negative index).
116 u.types = append(u.types, nil)
117 u.x.indices[i] = -len(u.types)
118 u.y.indices[j] = -len(u.types)
120 // The type parameter for x has no type slot yet. Use slot of y.
123 // The type parameter for y has no type slot yet. Use slot of x.
126 // Both type parameters have a slot: ti != 0 && tj != 0.
128 // Both type parameters already share the same slot. Nothing to do.
130 case ti > 0 && tj > 0:
131 // Both type parameters have (possibly different) inferred types. Cannot join.
134 // Only the type parameter for x has an inferred type. Use x slot for y.
136 // This case is handled like the default case.
138 // // Only the type parameter for y has an inferred type. Use y slot for x.
139 // u.x.setIndex(i, tj)
141 // Neither type parameter has an inferred type. Use y slot for x
142 // (or x slot for y, it doesn't matter).
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 {
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) {
164 assert(ti != 0 && tj != 0)
165 for k, tk := range d.indices {
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]
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) {
185 switch ti := d.indices[i]; {
190 u.types = append(u.types, typ)
191 d.indices[i] = len(u.types)
193 panic("type already set")
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))
204 for i := range d.tparams {
207 if index < 0 && t == nil {
214 func (u *unifier) nifyEq(x, y Type, p *ifacePair) bool {
215 return x == y || u.nify(x, y, p)
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
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.)
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)
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
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)
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)
257 // otherwise, infer type from y
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)
266 // otherwise, infer type from x
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) } .
276 switch x := x.(type) {
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
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)
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)
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 {
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) {
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)
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() {
332 for i, v := range x.vars {
334 if !u.nify(v.typ, w.typ, p) {
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)
356 // This should not happen with the current internal use of union types.
357 panic("type inference across union types not implemented")
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.
369 u.check.completeInterface(nopos, x)
370 u.check.completeInterface(nopos, y)
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:
381 // type T interface {
385 // If two such (differently named) interfaces are compared,
386 // endless recursion occurs if the cycle is not detected.
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.
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}
400 return true // same pair was compared before
405 assertSortedMethods(a)
406 assertSortedMethods(b)
408 for i, f := range a {
410 if f.Id() != g.Id() || !u.nify(f.typ, g.typ, q) {
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)
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)
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
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) {
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.
458 // unreachable since types are expanded
461 // avoid a crash in case of nil type
464 u.check.dump("### u.nify(%s, %s), u.x.tparams = %s", x, y, u.x.tparams)