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 <gobot@golang.org>
Auto-Submit: Robert Griesemer <gri@google.com>
Run-TryBot: Robert Griesemer <gri@google.com>
Reviewed-by: Robert Griesemer <gri@google.com>
Reviewed-by: Robert Findley <rfindley@google.com>

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)
-			}
 		}
 	}