Change diff.Difference to always return an edit-script (#45)

Rather than performing the heuristic for whether two slices are
"too different" in the diff package, just return the full edit-script
and move the heuristic logic into the cmp package.

The main adjustment to the heuristic is that we only print the
full slice if it is composed of a slice of primitive types (e.g., []byte)
and the difference between the two slices is sufficiently great enough.

Fixes #44

2 files changed, 21 insertions, 37 deletions

diff --git a/cmp/internal/diff/diff.go b/cmp/internal/diff/diff.go
index baa41fd..260befe 100644
--- a/cmp/internal/diff/diff.go
+++ b/cmp/internal/diff/diff.go
@@ -106,9 +106,9 @@ func (r Result) Similar() bool {
 // Difference reports whether two lists of lengths nx and ny are equal
 // given the definition of equality provided as f.
 //
-// This function may return a edit-script, which is a sequence of operations
-// needed to convert one list into the other. If non-nil, the following
-// invariants for the edit-script are maintained:
+// This function returns an edit-script, which is a sequence of operations
+// needed to convert one list into the other. The following invariants for
+// the edit-script are maintained:
 //	• eq == (es.Dist()==0)
 //	• nx == es.LenX()
 //	• ny == es.LenY()
@@ -117,17 +117,7 @@ func (r Result) Similar() bool {
 // produces an edit-script with a minimal Levenshtein distance). This algorithm
 // favors performance over optimality. The exact output is not guaranteed to
 // be stable and may change over time.
-func Difference(nx, ny int, f EqualFunc) (eq bool, es EditScript) {
-	es = searchGraph(nx, ny, f)
-	st := es.stats()
-	eq = len(es) == st.NI
-	if !eq && st.NI < (nx+ny)/4 {
-		return eq, nil // Edit-script more distracting than helpful
-	}
-	return eq, es
-}
-
-func searchGraph(nx, ny int, f EqualFunc) EditScript {
+func Difference(nx, ny int, f EqualFunc) (es EditScript) {
 	// This algorithm is based on traversing what is known as an "edit-graph".
 	// See Figure 1 from "An O(ND) Difference Algorithm and Its Variations"
 	// by Eugene W. Myers. Since D can be as large as N itself, this is
diff --git a/cmp/internal/diff/diff_test.go b/cmp/internal/diff/diff_test.go
index 5996ea2..6399509 100644
--- a/cmp/internal/diff/diff_test.go
+++ b/cmp/internal/diff/diff_test.go
@@ -228,14 +228,17 @@ func TestDifference(t *testing.T) {
 		y:    " 1234567890",
 		want: "X.........Y",
 	}, {
-		x: "0123456789",
-		y: "9876543210",
+		x:    "0 1 2 3 45 6 7 8 9 ",
+		y:    " 9 8 7 6 54 3 2 1 0",
+		want: "XYXYXYXYX.YXYXYXYXY",
 	}, {
-		x: "0123456789",
-		y: "6725819034",
+		x:    "0 1 2345678 9   ",
+		y:    " 6 72  5  819034",
+		want: "XYXY.XX.XX.Y.YYY",
 	}, {
-		x: "FBQMOIGTLN72X90E4SP651HKRJUDA83CVZW",
-		y: "5WHXO10R9IVKZLCTAJ8P3NSEQM472G6UBDF",
+		x:    "F B Q M O    I G T L       N72X90 E  4S P  651HKRJU DA 83CVZW",
+		y:    " 5 W H XO10R9IV K ZLCTAJ8P3N     SEQM4 7 2G6      UBD F      ",
+		want: "XYXYXYXY.YYYY.YXYXY.YYYYYYY.XXXXXY.YY.XYXYY.XXXXXX.Y.XYXXXXXX",
 	}}
 
 	for _, tt := range tests {
@@ -333,26 +336,17 @@ func generateStrings(n int, px, py, pm float32, seed int64) (string, string) {
 }
 
 func testStrings(t *testing.T, x, y string) EditScript {
-	wantEq := x == y
-	eq, es := Difference(len(x), len(y), func(ix, iy int) Result {
+	es := Difference(len(x), len(y), func(ix, iy int) Result {
 		return compareByte(x[ix], y[iy])
 	})
-	if eq != wantEq {
-		t.Errorf("equality mismatch: got %v, want %v", eq, wantEq)
+	if es.LenX() != len(x) {
+		t.Errorf("es.LenX = %d, want %d", es.LenX(), len(x))
 	}
-	if es != nil {
-		if es.LenX() != len(x) {
-			t.Errorf("es.LenX = %d, want %d", es.LenX(), len(x))
-		}
-		if es.LenY() != len(y) {
-			t.Errorf("es.LenY = %d, want %d", es.LenY(), len(y))
-		}
-		if got := (es.Dist() == 0); got != wantEq {
-			t.Errorf("violation of equality invariant: got %v, want %v", got, wantEq)
-		}
-		if !validateScript(x, y, es) {
-			t.Errorf("invalid edit script: %v", es)
-		}
+	if es.LenY() != len(y) {
+		t.Errorf("es.LenY = %d, want %d", es.LenY(), len(y))
+	}
+	if !validateScript(x, y, es) {
+		t.Errorf("invalid edit script: %v", es)
 	}
 	return es
 }