go/types, types2: correctly consider ~ (tilde) in constraint type inference

[gostls13.git] / src / cmd / compile / internal / types2 / unify.go

// 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"
        "strings"
)

// 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 bidirectional 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.

const (
        // Upper limit for recursion depth. Used to catch infinite recursions
        // due to implementation issues (e.g., see issues #48619, #48656).
        unificationDepthLimit = 50

        // Whether to panic when unificationDepthLimit is reached. Turn on when
        // investigating infinite recursion.
        panicAtUnificationDepthLimit = false

        // If enableCoreTypeUnification is set, unification will consider
        // the core types, if any, of non-local (unbound) type parameters.
        enableCoreTypeUnification = true

        // If traceInference is set, unification will print a trace of its operation.
        // Interpretation of trace:
        //   x ≡ y    attempt to unify types x and y
        //   p ➞ y    type parameter p is set to type y (p is inferred to be y)
        //   p ⇄ q    type parameters p and q match (p is inferred to be q and vice versa)
        //   x ≢ y    types x and y cannot be unified
        //   [p, q, ...] ➞ [x, y, ...]    mapping from type parameters to types
        traceInference = false
)

// 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
        depth int         // recursion depth during unification
}

// 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.
// TODO(gri) exact is not set anymore by a caller. Consider removing it.
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)
}

func (u *unifier) tracef(format string, args ...interface{}) {
        fmt.Println(strings.Repeat(".  ", u.depth) + sprintf(nil, true, format, args...))
}

// 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
        w := newTypeWriter(&buf, nil)
        w.byte('[')
        for i, tpar := range d.tparams {
                if i > 0 {
                        w.string(", ")
                }
                w.typ(tpar)
                w.string(": ")
                w.typ(d.at(i))
        }
        w.byte(']')
        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 returns false.
func (u *unifier) join(i, j int) bool {
        if traceInference {
                u.tracef("%s ⇄ %s", u.x.tparams[i], u.y.tparams[j])
        }
        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.
                // TODO(gri) Should we check if types are identical? Investigate.
                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 {
        // Once a type parameter is bound its index is >= 0. However, there are some
        // code paths (namely tracing and type hashing) by which it is possible to
        // arrive here with a type parameter that has not been bound, hence the check
        // for 0 <= i below.
        // TODO(rfindley): investigate a better approach for guarding against using
        // unbound type parameters.
        if i := tpar.index; 0 <= i && 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
        if traceInference {
                u.tracef("%s ➞ %s", d.tparams[i], typ)
        }
        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")
        }
}

// unknowns returns the number of type parameters for which no type has been set yet.
func (d *tparamsList) unknowns() int {
        n := 0
        for _, ti := range d.indices {
                if ti <= 0 {
                        n++
                }
        }
        return n
}

// 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.identical. 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) (result bool) {
        if traceInference {
                u.tracef("%s ≡ %s", x, y)
        }

        // Stop gap for cases where unification fails.
        if u.depth >= unificationDepthLimit {
                if traceInference {
                        u.tracef("depth %d >= %d", u.depth, unificationDepthLimit)
                }
                if panicAtUnificationDepthLimit {
                        panic("unification reached recursion depth limit")
                }
                return false
        }
        u.depth++
        defer func() {
                u.depth--
                if traceInference && !result {
                        u.tracef("%s ≢ %s", x, y)
                }
        }()

        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.
                // (We use !hasName to exclude any type with a name, including
                // basic types and type parameters; the rest are unamed types.)
                if nx, _ := x.(*Named); nx != nil && !hasName(y) {
                        if traceInference {
                                u.tracef("under %s ≡ %s", nx, y)
                        }
                        return u.nify(nx.under(), y, p)
                } else if ny, _ := y.(*Named); ny != nil && !hasName(x) {
                        if traceInference {
                                u.tracef("%s ≡ under %s", x, ny)
                        }
                        return u.nify(x, ny.under(), 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
        }

        // If we get here and x or y is a type parameter, they are type parameters
        // from outside our declaration list. Try to unify their core types, if any
        // (see issue #50755 for a test case).
        if enableCoreTypeUnification && !u.exact {
                if isTypeParam(x) && !hasName(y) {
                        // Caution: This may not be correct in light of ~ constraints.
                        //          See issue #51376.
                        // TODO(gri) investigate!
                        //
                        // When considering the type parameter for unification
                        // we look at the adjusted core type (coreTerm).
                        // If the adjusted core type is a named type N; the
                        // corresponding core type is under(N). Since !u.exact
                        // and y doesn't have a name, unification will end up
                        // comparing under(N) to y, so we can just use the core
                        // type instead. Optimization.
                        if cx := coreType(x); cx != nil {
                                if traceInference {
                                        u.tracef("core %s ≡ %s", x, y)
                                }
                                return u.nify(cx, y, p)
                        }
                } else if isTypeParam(y) && !hasName(x) {
                        // see comment above
                        if cy := coreType(y); cy != nil {
                                if traceInference {
                                        u.tracef("%s ≡ core %s", x, y)
                                }
                                return u.nify(x, cy, p)
                        }
                }
        }

        // 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.comparable != yset.comparable {
                                return false
                        }
                        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:
                // TODO(gri) This code differs now from the parallel code in Checker.identical. Investigate.
                if y, ok := y.(*Named); ok {
                        xargs := x.targs.list()
                        yargs := y.targs.list()

                        if len(xargs) != len(yargs) {
                                return false
                        }

                        // TODO(gri) This is not always correct: two types may have the same names
                        //           in the same package if one of them is nested in a function.
                        //           Extremely unlikely but we need an always correct solution.
                        if x.obj.pkg == y.obj.pkg && x.obj.name == y.obj.name {
                                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(sprintf(nil, true, "u.nify(%s, %s), u.x.tparams = %s", x, y, u.x.tparams))
        }

        return false
}