blob: 72542e7d2ed88329bed84fd0abd969d631059c6d [file] [log] [blame]
// Copyright 2020 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
// This file implements type unification.
package types2
import (
"bytes"
"fmt"
)
// The unifier maintains two separate sets of type parameters x and y
// which are used to resolve type parameters in the x and y arguments
// provided to the unify call. For unidirectional unification, only
// one of these sets (say x) is provided, and then type parameters are
// only resolved for the x argument passed to unify, not the y argument
// (even if that also contains possibly the same type parameters). This
// is crucial to infer the type parameters of self-recursive calls:
//
// func f[P any](a P) { f(a) }
//
// For the call f(a) we want to infer that the type argument for P is P.
// During unification, the parameter type P must be resolved to the type
// parameter P ("x" side), but the argument type P must be left alone so
// that unification resolves the type parameter P to P.
//
// For bidirection unification, both sets are provided. This enables
// unification to go from argument to parameter type and vice versa.
// For constraint type inference, we use bidirectional unification
// where both the x and y type parameters are identical. This is done
// by setting up one of them (using init) and then assigning its value
// to the other.
// A unifier maintains the current type parameters for x and y
// and the respective types inferred for each type parameter.
// A unifier is created by calling newUnifier.
type unifier struct {
exact bool
x, y tparamsList // x and y must initialized via tparamsList.init
types []Type // inferred types, shared by x and y
}
// newUnifier returns a new unifier.
// If exact is set, unification requires unified types to match
// exactly. If exact is not set, a named type's underlying type
// is considered if unification would fail otherwise, and the
// direction of channels is ignored.
func newUnifier(exact bool) *unifier {
u := &unifier{exact: exact}
u.x.unifier = u
u.y.unifier = u
return u
}
// unify attempts to unify x and y and reports whether it succeeded.
func (u *unifier) unify(x, y Type) bool {
return u.nify(x, y, nil)
}
// A tparamsList describes a list of type parameters and the types inferred for them.
type tparamsList struct {
unifier *unifier
tparams []*TypeParam
// For each tparams element, there is a corresponding type slot index in indices.
// index < 0: unifier.types[-index-1] == nil
// index == 0: no type slot allocated yet
// index > 0: unifier.types[index-1] == typ
// Joined tparams elements share the same type slot and thus have the same index.
// By using a negative index for nil types we don't need to check unifier.types
// to see if we have a type or not.
indices []int // len(d.indices) == len(d.tparams)
}
// String returns a string representation for a tparamsList. For debugging.
func (d *tparamsList) String() string {
var buf bytes.Buffer
buf.WriteByte('[')
for i, tpar := range d.tparams {
if i > 0 {
buf.WriteString(", ")
}
writeType(&buf, tpar, nil, nil)
buf.WriteString(": ")
writeType(&buf, d.at(i), nil, nil)
}
buf.WriteByte(']')
return buf.String()
}
// init initializes d with the given type parameters.
// The type parameters must be in the order in which they appear in their declaration
// (this ensures that the tparams indices match the respective type parameter index).
func (d *tparamsList) init(tparams []*TypeParam) {
if len(tparams) == 0 {
return
}
if debug {
for i, tpar := range tparams {
assert(i == tpar.index)
}
}
d.tparams = tparams
d.indices = make([]int, len(tparams))
}
// join unifies the i'th type parameter of x with the j'th type parameter of y.
// If both type parameters already have a type associated with them and they are
// not joined, join fails and return false.
func (u *unifier) join(i, j int) bool {
ti := u.x.indices[i]
tj := u.y.indices[j]
switch {
case ti == 0 && tj == 0:
// Neither type parameter has a type slot associated with them.
// Allocate a new joined nil type slot (negative index).
u.types = append(u.types, nil)
u.x.indices[i] = -len(u.types)
u.y.indices[j] = -len(u.types)
case ti == 0:
// The type parameter for x has no type slot yet. Use slot of y.
u.x.indices[i] = tj
case tj == 0:
// The type parameter for y has no type slot yet. Use slot of x.
u.y.indices[j] = ti
// Both type parameters have a slot: ti != 0 && tj != 0.
case ti == tj:
// Both type parameters already share the same slot. Nothing to do.
break
case ti > 0 && tj > 0:
// Both type parameters have (possibly different) inferred types. Cannot join.
return false
case ti > 0:
// Only the type parameter for x has an inferred type. Use x slot for y.
u.y.setIndex(j, ti)
// This case is handled like the default case.
// case tj > 0:
// // Only the type parameter for y has an inferred type. Use y slot for x.
// u.x.setIndex(i, tj)
default:
// Neither type parameter has an inferred type. Use y slot for x
// (or x slot for y, it doesn't matter).
u.x.setIndex(i, tj)
}
return true
}
// If typ is a type parameter of d, index returns the type parameter index.
// Otherwise, the result is < 0.
func (d *tparamsList) index(typ Type) int {
if tpar, ok := typ.(*TypeParam); ok {
return tparamIndex(d.tparams, tpar)
}
return -1
}
// If tpar is a type parameter in list, tparamIndex returns the type parameter index.
// Otherwise, the result is < 0. tpar must not be nil.
func tparamIndex(list []*TypeParam, tpar *TypeParam) int {
if i := tpar.index; i < len(list) && list[i] == tpar {
return i
}
return -1
}
// setIndex sets the type slot index for the i'th type parameter
// (and all its joined parameters) to tj. The type parameter
// must have a (possibly nil) type slot associated with it.
func (d *tparamsList) setIndex(i, tj int) {
ti := d.indices[i]
assert(ti != 0 && tj != 0)
for k, tk := range d.indices {
if tk == ti {
d.indices[k] = tj
}
}
}
// at returns the type set for the i'th type parameter; or nil.
func (d *tparamsList) at(i int) Type {
if ti := d.indices[i]; ti > 0 {
return d.unifier.types[ti-1]
}
return nil
}
// set sets the type typ for the i'th type parameter;
// typ must not be nil and it must not have been set before.
func (d *tparamsList) set(i int, typ Type) {
assert(typ != nil)
u := d.unifier
switch ti := d.indices[i]; {
case ti < 0:
u.types[-ti-1] = typ
d.setIndex(i, -ti)
case ti == 0:
u.types = append(u.types, typ)
d.indices[i] = len(u.types)
default:
panic("type already set")
}
}
// types returns the list of inferred types (via unification) for the type parameters
// described by d, and an index. If all types were inferred, the returned index is < 0.
// Otherwise, it is the index of the first type parameter which couldn't be inferred;
// i.e., for which list[index] is nil.
func (d *tparamsList) types() (list []Type, index int) {
list = make([]Type, len(d.tparams))
index = -1
for i := range d.tparams {
t := d.at(i)
list[i] = t
if index < 0 && t == nil {
index = i
}
}
return
}
func (u *unifier) nifyEq(x, y Type, p *ifacePair) bool {
return x == y || u.nify(x, y, p)
}
// nify implements the core unification algorithm which is an
// adapted version of Checker.identical0. For changes to that
// code the corresponding changes should be made here.
// Must not be called directly from outside the unifier.
func (u *unifier) nify(x, y Type, p *ifacePair) bool {
if !u.exact {
// If exact unification is known to fail because we attempt to
// match a type name against an unnamed type literal, consider
// the underlying type of the named type.
// (Subtle: We use isNamed to include any type with a name (incl.
// basic types and type parameters. We use asNamed because we only
// want *Named types.)
switch {
case !isNamed(x) && y != nil && asNamed(y) != nil:
return u.nify(x, under(y), p)
case x != nil && asNamed(x) != nil && !isNamed(y):
return u.nify(under(x), y, p)
}
}
// Cases where at least one of x or y is a type parameter.
switch i, j := u.x.index(x), u.y.index(y); {
case i >= 0 && j >= 0:
// both x and y are type parameters
if u.join(i, j) {
return true
}
// both x and y have an inferred type - they must match
return u.nifyEq(u.x.at(i), u.y.at(j), p)
case i >= 0:
// x is a type parameter, y is not
if tx := u.x.at(i); tx != nil {
return u.nifyEq(tx, y, p)
}
// otherwise, infer type from y
u.x.set(i, y)
return true
case j >= 0:
// y is a type parameter, x is not
if ty := u.y.at(j); ty != nil {
return u.nifyEq(x, ty, p)
}
// otherwise, infer type from x
u.y.set(j, x)
return true
}
// For type unification, do not shortcut (x == y) for identical
// types. Instead keep comparing them element-wise to unify the
// matching (and equal type parameter types). A simple test case
// where this matters is: func f[P any](a P) { f(a) } .
switch x := x.(type) {
case *Basic:
// Basic types are singletons except for the rune and byte
// aliases, thus we cannot solely rely on the x == y check
// above. See also comment in TypeName.IsAlias.
if y, ok := y.(*Basic); ok {
return x.kind == y.kind
}
case *Array:
// Two array types are identical if they have identical element types
// and the same array length.
if y, ok := y.(*Array); ok {
// If one or both array lengths are unknown (< 0) due to some error,
// assume they are the same to avoid spurious follow-on errors.
return (x.len < 0 || y.len < 0 || x.len == y.len) && u.nify(x.elem, y.elem, p)
}
case *Slice:
// Two slice types are identical if they have identical element types.
if y, ok := y.(*Slice); ok {
return u.nify(x.elem, y.elem, p)
}
case *Struct:
// Two struct types are identical if they have the same sequence of fields,
// and if corresponding fields have the same names, and identical types,
// and identical tags. Two embedded fields are considered to have the same
// name. Lower-case field names from different packages are always different.
if y, ok := y.(*Struct); ok {
if x.NumFields() == y.NumFields() {
for i, f := range x.fields {
g := y.fields[i]
if f.embedded != g.embedded ||
x.Tag(i) != y.Tag(i) ||
!f.sameId(g.pkg, g.name) ||
!u.nify(f.typ, g.typ, p) {
return false
}
}
return true
}
}
case *Pointer:
// Two pointer types are identical if they have identical base types.
if y, ok := y.(*Pointer); ok {
return u.nify(x.base, y.base, p)
}
case *Tuple:
// Two tuples types are identical if they have the same number of elements
// and corresponding elements have identical types.
if y, ok := y.(*Tuple); ok {
if x.Len() == y.Len() {
if x != nil {
for i, v := range x.vars {
w := y.vars[i]
if !u.nify(v.typ, w.typ, p) {
return false
}
}
}
return true
}
}
case *Signature:
// Two function types are identical if they have the same number of parameters
// and result values, corresponding parameter and result types are identical,
// and either both functions are variadic or neither is. Parameter and result
// names are not required to match.
// TODO(gri) handle type parameters or document why we can ignore them.
if y, ok := y.(*Signature); ok {
return x.variadic == y.variadic &&
u.nify(x.params, y.params, p) &&
u.nify(x.results, y.results, p)
}
case *Interface:
// Two interface types are identical if they have the same set of methods with
// the same names and identical function types. Lower-case method names from
// different packages are always different. The order of the methods is irrelevant.
if y, ok := y.(*Interface); ok {
xset := x.typeSet()
yset := y.typeSet()
if !xset.terms.equal(yset.terms) {
return false
}
a := xset.methods
b := yset.methods
if len(a) == len(b) {
// Interface types are the only types where cycles can occur
// that are not "terminated" via named types; and such cycles
// can only be created via method parameter types that are
// anonymous interfaces (directly or indirectly) embedding
// the current interface. Example:
//
// type T interface {
// m() interface{T}
// }
//
// If two such (differently named) interfaces are compared,
// endless recursion occurs if the cycle is not detected.
//
// If x and y were compared before, they must be equal
// (if they were not, the recursion would have stopped);
// search the ifacePair stack for the same pair.
//
// This is a quadratic algorithm, but in practice these stacks
// are extremely short (bounded by the nesting depth of interface
// type declarations that recur via parameter types, an extremely
// rare occurrence). An alternative implementation might use a
// "visited" map, but that is probably less efficient overall.
q := &ifacePair{x, y, p}
for p != nil {
if p.identical(q) {
return true // same pair was compared before
}
p = p.prev
}
if debug {
assertSortedMethods(a)
assertSortedMethods(b)
}
for i, f := range a {
g := b[i]
if f.Id() != g.Id() || !u.nify(f.typ, g.typ, q) {
return false
}
}
return true
}
}
case *Map:
// Two map types are identical if they have identical key and value types.
if y, ok := y.(*Map); ok {
return u.nify(x.key, y.key, p) && u.nify(x.elem, y.elem, p)
}
case *Chan:
// Two channel types are identical if they have identical value types.
if y, ok := y.(*Chan); ok {
return (!u.exact || x.dir == y.dir) && u.nify(x.elem, y.elem, p)
}
case *Named:
if y, ok := y.(*Named); ok {
x.expand(nil)
y.expand(nil)
xargs := x.targs.list()
yargs := y.targs.list()
if x.obj.pkg == y.obj.pkg && x.obj.name == y.obj.name {
assert(len(xargs) == len(yargs))
for i, x := range xargs {
if !u.nify(x, yargs[i], p) {
return false
}
}
return true
}
}
case *TypeParam:
// Two type parameters (which are not part of the type parameters of the
// enclosing type as those are handled in the beginning of this function)
// are identical if they originate in the same declaration.
return x == y
case nil:
// avoid a crash in case of nil type
default:
panic(fmt.Sprintf("### u.nify(%s, %s), u.x.tparams = %s", x, y, u.x.tparams))
}
return false
}