From 331f0c69769fb856f00c75f29085665f60a7af7b Mon Sep 17 00:00:00 2001 From: Robert Griesemer Date: Thu, 2 Feb 2023 10:14:58 -0800 Subject: [PATCH] go/types, types2: simplify symmetric code Because unification is symmetric, in cases where we have symmetric code for x and y depending on some property we can swap x and y as needed and simplify the code. Also, change u.depth increment/decrement position for slightly nicer tracing ooutput. Change-Id: I2e84570d463d1c32f6556108f3cb54062b57c718 Reviewed-on: https://go-review.googlesource.com/c/go/+/464896 TryBot-Result: Gopher Robot Auto-Submit: Robert Griesemer Run-TryBot: Robert Griesemer Reviewed-by: Robert Griesemer Reviewed-by: Robert Findley --- src/cmd/compile/internal/types2/unify.go | 68 ++++++++++++------------ src/go/types/unify.go | 68 ++++++++++++------------ 2 files changed, 66 insertions(+), 70 deletions(-) diff --git a/src/cmd/compile/internal/types2/unify.go b/src/cmd/compile/internal/types2/unify.go index abf159d5a2..48be5aeaef 100644 --- a/src/cmd/compile/internal/types2/unify.go +++ b/src/cmd/compile/internal/types2/unify.go @@ -209,12 +209,19 @@ func (u *unifier) nifyEq(x, y Type, p *ifacePair) bool { // 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) { + u.depth++ if traceInference { u.tracef("%s ≡ %s", x, y) } + defer func() { + if traceInference && !result { + u.tracef("%s ≢ %s", x, y) + } + u.depth-- + }() // Stop gap for cases where unification fails. - if u.depth >= unificationDepthLimit { + if u.depth > unificationDepthLimit { if traceInference { u.tracef("depth %d >= %d", u.depth, unificationDepthLimit) } @@ -223,36 +230,36 @@ func (u *unifier) nify(x, y Type, p *ifacePair) (result bool) { } return false } - u.depth++ - defer func() { - u.depth-- - if traceInference && !result { - u.tracef("%s ≢ %s", x, y) + + // Unification is symmetric, so we can swap the operands. + // Ensure that if we have at least one + // - defined type, make sure sure one is in y + // - type parameter recorded with u, make sure one is in x + if _, ok := x.(*Named); ok || u.asTypeParam(y) != nil { + if traceInference { + u.tracef("%s ≡ %s (swap)", y, x) } - }() + x, y = y, x + } // 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. + // match a defined type against an unnamed type literal, consider + // the underlying type of the defined type. + // If we have at least one defined type, there is one in y. // (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) - } - x = nx.under() - // Per the spec, a defined type cannot have an underlying type - // that is a type parameter. - assert(!isTypeParam(x)) - } else if ny, _ := y.(*Named); ny != nil && !hasName(x) { + if ny, _ := y.(*Named); ny != nil && !hasName(x) { if traceInference { u.tracef("%s ≡ under %s", x, ny) } y = ny.under() + // Per the spec, a defined type cannot have an underlying type + // that is a type parameter. assert(!isTypeParam(y)) } // Cases where at least one of x or y is a type parameter recorded with u. + // If we have ar least one type parameter, there is one in x. switch px, py := u.asTypeParam(x), u.asTypeParam(y); { case px != nil && py != nil: // both x and y are type parameters @@ -270,21 +277,20 @@ func (u *unifier) nify(x, y Type, p *ifacePair) (result bool) { // otherwise, infer type from y u.set(px, y) return true - - case py != nil: - // y is a type parameter, x is not - if ty := u.at(py); ty != nil { - return u.nifyEq(x, ty, p) - } - // otherwise, infer type from x - u.set(py, 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 go.dev/issue/50755 for a test case). if enableCoreTypeUnification { + // swap x and y as needed + // (the earlier swap checks for _recorded_ type parameters only) + if isTypeParam(y) { + if traceInference { + u.tracef("%s ≡ %s (swap)", y, x) + } + x, y = y, x + } if isTypeParam(x) && !hasName(y) { // When considering the type parameter for unification // we look at the adjusted core term (adjusted core type @@ -303,14 +309,6 @@ func (u *unifier) nify(x, y Type, p *ifacePair) (result bool) { } 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) - } } } diff --git a/src/go/types/unify.go b/src/go/types/unify.go index 886e84183c..e10493897c 100644 --- a/src/go/types/unify.go +++ b/src/go/types/unify.go @@ -211,12 +211,19 @@ func (u *unifier) nifyEq(x, y Type, p *ifacePair) bool { // 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) { + u.depth++ if traceInference { u.tracef("%s ≡ %s", x, y) } + defer func() { + if traceInference && !result { + u.tracef("%s ≢ %s", x, y) + } + u.depth-- + }() // Stop gap for cases where unification fails. - if u.depth >= unificationDepthLimit { + if u.depth > unificationDepthLimit { if traceInference { u.tracef("depth %d >= %d", u.depth, unificationDepthLimit) } @@ -225,36 +232,36 @@ func (u *unifier) nify(x, y Type, p *ifacePair) (result bool) { } return false } - u.depth++ - defer func() { - u.depth-- - if traceInference && !result { - u.tracef("%s ≢ %s", x, y) + + // Unification is symmetric, so we can swap the operands. + // Ensure that if we have at least one + // - defined type, make sure sure one is in y + // - type parameter recorded with u, make sure one is in x + if _, ok := x.(*Named); ok || u.asTypeParam(y) != nil { + if traceInference { + u.tracef("%s ≡ %s (swap)", y, x) } - }() + x, y = y, x + } // 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. + // match a defined type against an unnamed type literal, consider + // the underlying type of the defined type. + // If we have at least one defined type, there is one in y. // (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) - } - x = nx.under() - // Per the spec, a defined type cannot have an underlying type - // that is a type parameter. - assert(!isTypeParam(x)) - } else if ny, _ := y.(*Named); ny != nil && !hasName(x) { + if ny, _ := y.(*Named); ny != nil && !hasName(x) { if traceInference { u.tracef("%s ≡ under %s", x, ny) } y = ny.under() + // Per the spec, a defined type cannot have an underlying type + // that is a type parameter. assert(!isTypeParam(y)) } // Cases where at least one of x or y is a type parameter recorded with u. + // If we have ar least one type parameter, there is one in x. switch px, py := u.asTypeParam(x), u.asTypeParam(y); { case px != nil && py != nil: // both x and y are type parameters @@ -272,21 +279,20 @@ func (u *unifier) nify(x, y Type, p *ifacePair) (result bool) { // otherwise, infer type from y u.set(px, y) return true - - case py != nil: - // y is a type parameter, x is not - if ty := u.at(py); ty != nil { - return u.nifyEq(x, ty, p) - } - // otherwise, infer type from x - u.set(py, 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 go.dev/issue/50755 for a test case). if enableCoreTypeUnification { + // swap x and y as needed + // (the earlier swap checks for _recorded_ type parameters only) + if isTypeParam(y) { + if traceInference { + u.tracef("%s ≡ %s (swap)", y, x) + } + x, y = y, x + } if isTypeParam(x) && !hasName(y) { // When considering the type parameter for unification // we look at the adjusted core term (adjusted core type @@ -305,14 +311,6 @@ func (u *unifier) nify(x, y Type, p *ifacePair) (result bool) { } 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) - } } } -- 2.50.0