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.
7 // Type unification attempts to make two types x and y structurally
8 // identical 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 // are 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.
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. If a call fails (returns false), unification
21 // In the unification context, structural identity ignores the
22 // difference between a defined type and its underlying type.
23 // It also ignores the difference between an (external, unbound)
24 // type parameter and its core type.
25 // If two types are not structurally identical, they cannot be Go
26 // identical types. On the other hand, if they are structurally
27 // identical, they may be Go identical or at least assignable, or
28 // they may be in the type set of a constraint.
29 // Whether they indeed are identical or assignable is determined
30 // upon instantiation and function argument passing.
42 // Upper limit for recursion depth. Used to catch infinite recursions
43 // due to implementation issues (e.g., see issues go.dev/issue/48619, go.dev/issue/48656).
44 unificationDepthLimit = 50
46 // Whether to panic when unificationDepthLimit is reached.
47 // If disabled, a recursion depth overflow results in a (quiet)
48 // unification failure.
49 panicAtUnificationDepthLimit = true
51 // If enableCoreTypeUnification is set, unification will consider
52 // the core types, if any, of non-local (unbound) type parameters.
53 enableCoreTypeUnification = true
55 // If traceInference is set, unification will print a trace of its operation.
56 // Interpretation of trace:
57 // x ≡ y attempt to unify types x and y
58 // p ➞ y type parameter p is set to type y (p is inferred to be y)
59 // p ⇄ q type parameters p and q match (p is inferred to be q and vice versa)
60 // x ≢ y types x and y cannot be unified
61 // [p, q, ...] ➞ [x, y, ...] mapping from type parameters to types
62 traceInference = false
65 // A unifier maintains a list of type parameters and
66 // corresponding types inferred for each type parameter.
67 // A unifier is created by calling newUnifier.
69 // handles maps each type parameter to its inferred type through
70 // an indirection *Type called (inferred type) "handle".
71 // Initially, each type parameter has its own, separate handle,
72 // with a nil (i.e., not yet inferred) type.
73 // After a type parameter P is unified with a type parameter Q,
74 // P and Q share the same handle (and thus type). This ensures
75 // that inferring the type for a given type parameter P will
76 // automatically infer the same type for all other parameters
77 // unified (joined) with P.
78 handles map[*TypeParam]*Type
79 depth int // recursion depth during unification
82 // newUnifier returns a new unifier initialized with the given type parameter
83 // and corresponding type argument lists. The type argument list may be shorter
84 // than the type parameter list, and it may contain nil types. Matching type
85 // parameters and arguments must have the same index.
86 func newUnifier(tparams []*TypeParam, targs []Type) *unifier {
87 assert(len(tparams) >= len(targs))
88 handles := make(map[*TypeParam]*Type, len(tparams))
89 // Allocate all handles up-front: in a correct program, all type parameters
90 // must be resolved and thus eventually will get a handle.
91 // Also, sharing of handles caused by unified type parameters is rare and
92 // so it's ok to not optimize for that case (and delay handle allocation).
93 for i, x := range tparams {
100 return &unifier{handles, 0}
103 // unify attempts to unify x and y and reports whether it succeeded.
104 // As a side-effect, types may be inferred for type parameters.
105 func (u *unifier) unify(x, y Type) bool {
106 return u.nify(x, y, nil)
109 func (u *unifier) tracef(format string, args ...interface{}) {
110 fmt.Println(strings.Repeat(". ", u.depth) + sprintf(nil, true, format, args...))
113 // String returns a string representation of the current mapping
114 // from type parameters to types.
115 func (u *unifier) String() string {
116 // sort type parameters for reproducible strings
117 tparams := make(typeParamsById, len(u.handles))
119 for tpar := range u.handles {
126 w := newTypeWriter(&buf, nil)
128 for i, x := range tparams {
140 type typeParamsById []*TypeParam
142 func (s typeParamsById) Len() int { return len(s) }
143 func (s typeParamsById) Less(i, j int) bool { return s[i].id < s[j].id }
144 func (s typeParamsById) Swap(i, j int) { s[i], s[j] = s[j], s[i] }
146 // join unifies the given type parameters x and y.
147 // If both type parameters already have a type associated with them
148 // and they are not joined, join fails and returns false.
149 func (u *unifier) join(x, y *TypeParam) bool {
151 u.tracef("%s ⇄ %s", x, y)
153 switch hx, hy := u.handles[x], u.handles[y]; {
155 // Both type parameters already share the same handle. Nothing to do.
156 case *hx != nil && *hy != nil:
157 // Both type parameters have (possibly different) inferred types. Cannot join.
160 // Only type parameter x has an inferred type. Use handle of x.
162 // This case is treated like the default case.
164 // // Only type parameter y has an inferred type. Use handle of y.
165 // u.setHandle(x, hy)
167 // Neither type parameter has an inferred type. Use handle of y.
173 // asTypeParam returns x.(*TypeParam) if x is a type parameter recorded with u.
174 // Otherwise, the result is nil.
175 func (u *unifier) asTypeParam(x Type) *TypeParam {
176 if x, _ := x.(*TypeParam); x != nil {
177 if _, found := u.handles[x]; found {
184 // setHandle sets the handle for type parameter x
185 // (and all its joined type parameters) to h.
186 func (u *unifier) setHandle(x *TypeParam, h *Type) {
189 for y, hy := range u.handles {
196 // at returns the (possibly nil) type for type parameter x.
197 func (u *unifier) at(x *TypeParam) Type {
201 // set sets the type t for type parameter x;
202 // t must not be nil.
203 func (u *unifier) set(x *TypeParam, t Type) {
206 u.tracef("%s ➞ %s", x, t)
211 // unknowns returns the number of type parameters for which no type has been set yet.
212 func (u *unifier) unknowns() int {
214 for _, h := range u.handles {
222 // inferred returns the list of inferred types for the given type parameter list.
223 // The result is never nil and has the same length as tparams; result types that
224 // could not be inferred are nil. Corresponding type parameters and result types
225 // have identical indices.
226 func (u *unifier) inferred(tparams []*TypeParam) []Type {
227 list := make([]Type, len(tparams))
228 for i, x := range tparams {
234 // nify implements the core unification algorithm which is an
235 // adapted version of Checker.identical. For changes to that
236 // code the corresponding changes should be made here.
237 // Must not be called directly from outside the unifier.
238 func (u *unifier) nify(x, y Type, p *ifacePair) (result bool) {
241 u.tracef("%s ≡ %s", x, y)
244 if traceInference && !result {
245 u.tracef("%s ≢ %s", x, y)
250 // nothing to do if x == y
255 // Stop gap for cases where unification fails.
256 if u.depth > unificationDepthLimit {
258 u.tracef("depth %d >= %d", u.depth, unificationDepthLimit)
260 if panicAtUnificationDepthLimit {
261 panic("unification reached recursion depth limit")
266 // Unification is symmetric, so we can swap the operands.
267 // Ensure that if we have at least one
268 // - defined type, make sure one is in y
269 // - type parameter recorded with u, make sure one is in x
270 if _, ok := x.(*Named); ok || u.asTypeParam(y) != nil {
272 u.tracef("%s ≡ %s (swap)", y, x)
277 // Unification will fail if we match a defined type against a type literal.
278 // Per the (spec) assignment rules, assignments of values to variables with
279 // the same type structure are permitted as long as at least one of them
280 // is not a defined type. To accomodate for that possibility, we continue
281 // unification with the underlying type of a defined type if the other type
282 // is a type literal.
283 // We also continue if the other type is a basic type because basic types
284 // are valid underlying types and may appear as core types of type constraints.
285 // If we exclude them, inferred defined types for type parameters may not
286 // match against the core types of their constraints (even though they might
287 // correctly match against some of the types in the constraint's type set).
288 // Finally, if unification (incorrectly) succeeds by matching the underlying
289 // type of a defined type against a basic type (because we include basic types
290 // as type literals here), and if that leads to an incorrectly inferred type,
291 // we will fail at function instantiation or argument assignment time.
293 // If we have at least one defined type, there is one in y.
294 if ny, _ := y.(*Named); ny != nil && isTypeLit(x) {
296 u.tracef("%s ≡ under %s", x, ny)
299 // Per the spec, a defined type cannot have an underlying type
300 // that is a type parameter.
301 assert(!isTypeParam(y))
302 // x and y may be identical now
308 // Cases where at least one of x or y is a type parameter recorded with u.
309 // If we have at least one type parameter, there is one in x.
310 // If we have exactly one type parameter, because it is in x,
311 // isTypeLit(x) is false and y was not changed above. In other
312 // words, if y was a defined type, it is still a defined type
313 // (relevant for the logic below).
314 switch px, py := u.asTypeParam(x), u.asTypeParam(y); {
315 case px != nil && py != nil:
316 // both x and y are type parameters
320 // both x and y have an inferred type - they must match
321 return u.nify(u.at(px), u.at(py), p)
324 // x is a type parameter, y is not
325 if x := u.at(px); x != nil {
326 // x has an inferred type which must match y
328 // If we have a match, possibly through underlying types,
329 // and y is a defined type, make sure we record that type
330 // for type parameter x, which may have until now only
331 // recorded an underlying type (go.dev/issue/43056).
332 if _, ok := y.(*Named); ok {
339 // otherwise, infer type from y
344 // If we get here and x or y is a type parameter, they are unbound
345 // (not recorded with the unifier).
346 // By definition, a valid type argument must be in the type set of
347 // the respective type constraint. Therefore, the type argument's
348 // underlying type must be in the set of underlying types of that
349 // constraint. If there is a single such underlying type, it's the
350 // constraint's core type. It must match the type argument's under-
351 // lying type, irrespective of whether the actual type argument,
352 // which may be a defined type, is actually in the type set (that
353 // will be determined at instantiation time).
354 // Thus, if we have the core type of an unbound type parameter,
355 // we know the structure of the possible types satisfying such
356 // parameters. Use that core type for further unification
357 // (see go.dev/issue/50755 for a test case).
358 if enableCoreTypeUnification {
359 // swap x and y as needed
360 // (the earlier swap checks for _recorded_ type parameters only)
363 u.tracef("%s ≡ %s (swap)", y, x)
368 // When considering the type parameter for unification
369 // we look at the core type.
370 // Because the core type is always an underlying type,
371 // unification will take care of matching against a
372 // defined or literal type automatically.
373 // If y is also an unbound type parameter, we will end
374 // up here again with x and y swapped, so we don't
375 // need to take care of that case separately.
376 if cx := coreType(x); cx != nil {
378 u.tracef("core %s ≡ %s", x, y)
380 return u.nify(cx, y, p)
385 // x != y if we reach here
388 switch x := x.(type) {
390 // Basic types are singletons except for the rune and byte
391 // aliases, thus we cannot solely rely on the x == y check
392 // above. See also comment in TypeName.IsAlias.
393 if y, ok := y.(*Basic); ok {
394 return x.kind == y.kind
398 // Two array types are identical if they have identical element types
399 // and the same array length.
400 if y, ok := y.(*Array); ok {
401 // If one or both array lengths are unknown (< 0) due to some error,
402 // assume they are the same to avoid spurious follow-on errors.
403 return (x.len < 0 || y.len < 0 || x.len == y.len) && u.nify(x.elem, y.elem, p)
407 // Two slice types are identical if they have identical element types.
408 if y, ok := y.(*Slice); ok {
409 return u.nify(x.elem, y.elem, p)
413 // Two struct types are identical if they have the same sequence of fields,
414 // and if corresponding fields have the same names, and identical types,
415 // and identical tags. Two embedded fields are considered to have the same
416 // name. Lower-case field names from different packages are always different.
417 if y, ok := y.(*Struct); ok {
418 if x.NumFields() == y.NumFields() {
419 for i, f := range x.fields {
421 if f.embedded != g.embedded ||
422 x.Tag(i) != y.Tag(i) ||
423 !f.sameId(g.pkg, g.name) ||
424 !u.nify(f.typ, g.typ, p) {
433 // Two pointer types are identical if they have identical base types.
434 if y, ok := y.(*Pointer); ok {
435 return u.nify(x.base, y.base, p)
439 // Two tuples types are identical if they have the same number of elements
440 // and corresponding elements have identical types.
441 if y, ok := y.(*Tuple); ok {
442 if x.Len() == y.Len() {
444 for i, v := range x.vars {
446 if !u.nify(v.typ, w.typ, p) {
456 // Two function types are identical if they have the same number of parameters
457 // and result values, corresponding parameter and result types are identical,
458 // and either both functions are variadic or neither is. Parameter and result
459 // names are not required to match.
460 // TODO(gri) handle type parameters or document why we can ignore them.
461 if y, ok := y.(*Signature); ok {
462 return x.variadic == y.variadic &&
463 u.nify(x.params, y.params, p) &&
464 u.nify(x.results, y.results, p)
468 // Two interface types are identical if they have the same set of methods with
469 // the same names and identical function types. Lower-case method names from
470 // different packages are always different. The order of the methods is irrelevant.
471 if y, ok := y.(*Interface); ok {
474 if xset.comparable != yset.comparable {
477 if !xset.terms.equal(yset.terms) {
482 if len(a) == len(b) {
483 // Interface types are the only types where cycles can occur
484 // that are not "terminated" via named types; and such cycles
485 // can only be created via method parameter types that are
486 // anonymous interfaces (directly or indirectly) embedding
487 // the current interface. Example:
489 // type T interface {
493 // If two such (differently named) interfaces are compared,
494 // endless recursion occurs if the cycle is not detected.
496 // If x and y were compared before, they must be equal
497 // (if they were not, the recursion would have stopped);
498 // search the ifacePair stack for the same pair.
500 // This is a quadratic algorithm, but in practice these stacks
501 // are extremely short (bounded by the nesting depth of interface
502 // type declarations that recur via parameter types, an extremely
503 // rare occurrence). An alternative implementation might use a
504 // "visited" map, but that is probably less efficient overall.
505 q := &ifacePair{x, y, p}
508 return true // same pair was compared before
513 assertSortedMethods(a)
514 assertSortedMethods(b)
516 for i, f := range a {
518 if f.Id() != g.Id() || !u.nify(f.typ, g.typ, q) {
527 // Two map types are identical if they have identical key and value types.
528 if y, ok := y.(*Map); ok {
529 return u.nify(x.key, y.key, p) && u.nify(x.elem, y.elem, p)
533 // Two channel types are identical if they have identical value types.
534 if y, ok := y.(*Chan); ok {
535 return u.nify(x.elem, y.elem, p)
539 // TODO(gri) This code differs now from the parallel code in Checker.identical. Investigate.
540 if y, ok := y.(*Named); ok {
541 xargs := x.TypeArgs().list()
542 yargs := y.TypeArgs().list()
544 if len(xargs) != len(yargs) {
548 // TODO(gri) This is not always correct: two types may have the same names
549 // in the same package if one of them is nested in a function.
550 // Extremely unlikely but we need an always correct solution.
551 if x.obj.pkg == y.obj.pkg && x.obj.name == y.obj.name {
552 for i, x := range xargs {
553 if !u.nify(x, yargs[i], p) {
562 // nothing to do - we know x != y
565 // avoid a crash in case of nil type
568 panic(sprintf(nil, true, "u.nify(%s, %s)", x, y))