Add diffing abilities to reporting (#9)

This adds an internal package with the following API:
    func Difference(nx, ny int, f EqualFunc) (eq bool, es EditScript)
    type EditScript []EditType
    type EditType int8
        const Identity EditType = iota ...
    type EqualFunc func(ix int, iy int) Result
    type Result struct{ ... }

The cmp.SliceIndex type has a new method SplitKeys to indicate that
elements are being compared in x and y are in different indexes.

The debug visualizer can be run:
	go test -tags=debug -v github.com/google/go-cmp/cmp/internal/diff

Reviewed-By: kevlar@google.com

1 files changed, 58 insertions, 26 deletions

diff --git a/cmp/compare.go b/cmp/compare.go
index 694a933..2294579 100644
--- a/cmp/compare.go
+++ b/cmp/compare.go
@@ -29,6 +29,8 @@ package cmp
 import (
 	"fmt"
 	"reflect"
+
+	"github.com/google/go-cmp/cmp/internal/diff"
 )
 
 // BUG: Maps with keys containing NaN values cannot be properly compared due to
@@ -37,6 +39,8 @@ import (
 //
 // See https://golang.org/issue/11104 for more details.
 
+var nothing = reflect.Value{}
+
 // Equal reports whether x and y are equal by recursively applying the
 // following rules in the given order to x and y and all of their sub-values:
 //
@@ -79,7 +83,7 @@ import (
 func Equal(x, y interface{}, opts ...Option) bool {
 	s := newState(opts)
 	s.compareAny(reflect.ValueOf(x), reflect.ValueOf(y))
-	return s.eq
+	return s.result.Equal()
 }
 
 // Diff returns a human-readable report of the differences between two values.
@@ -101,8 +105,8 @@ func Diff(x, y interface{}, opts ...Option) string {
 }
 
 type state struct {
-	eq      bool // Current result of comparison
-	curPath Path // The current path in the value tree
+	result  diff.Result // The current result of comparison
+	curPath Path        // The current path in the value tree
 
 	// dsCheck tracks the state needed to periodically perform checks that
 	// user provided func(T, T) bool functions are symmetric and deterministic.
@@ -123,7 +127,7 @@ type state struct {
 }
 
 func newState(opts []Option) *state {
-	s := &state{eq: true}
+	s := new(state)
 	for _, opt := range opts {
 		s.processOption(opt)
 	}
@@ -184,6 +188,7 @@ func (s *state) compareAny(vx, vy reflect.Value) {
 	t := vx.Type()
 	if len(s.curPath) == 0 {
 		s.curPath.push(&pathStep{typ: t})
+		defer s.curPath.pop()
 	}
 
 	// Rule 1: Check whether an option applies on this node in the value tree.
@@ -378,29 +383,52 @@ func (s *state) callFunc(f, x, y reflect.Value) bool {
 }
 
 func (s *state) compareArray(vx, vy reflect.Value, t reflect.Type) {
-	step := &sliceIndex{pathStep{t.Elem()}, 0}
+	step := &sliceIndex{pathStep{t.Elem()}, 0, 0}
 	s.curPath.push(step)
-	defer s.curPath.pop()
 
-	// Regardless of the lengths, we always try to compare the elements.
-	// If one slice is longer, we will report the elements of the longer
-	// slice as different (relative to an invalid reflect.Value).
-	nmin := vx.Len()
-	if nmin > vy.Len() {
-		nmin = vy.Len()
-	}
-	for i := 0; i < nmin; i++ {
-		step.key = i
-		s.compareAny(vx.Index(i), vy.Index(i))
-	}
-	for i := nmin; i < vx.Len(); i++ {
-		step.key = i
-		s.report(false, vx.Index(i), reflect.Value{})
+	// Compute an edit-script for slices vx and vy.
+	oldResult, oldReporter := s.result, s.reporter
+	s.reporter = nil // Remove reporter to avoid spurious printouts
+	eq, es := diff.Difference(vx.Len(), vy.Len(), func(ix, iy int) diff.Result {
+		step.xkey, step.ykey = ix, iy
+		s.result = diff.Result{} // Reset result
+		s.compareAny(vx.Index(ix), vy.Index(iy))
+		return s.result
+	})
+	s.result, s.reporter = oldResult, oldReporter
+
+	// Equal or no edit-script, so report entire slices as is.
+	if eq || es == nil {
+		s.curPath.pop() // Pop first since we are reporting the whole slice
+		s.report(eq, vx, vy)
+		return
 	}
-	for i := nmin; i < vy.Len(); i++ {
-		step.key = i
-		s.report(false, reflect.Value{}, vy.Index(i))
+
+	// Replay the edit-script.
+	var ix, iy int
+	for _, e := range es {
+		switch e {
+		case diff.UniqueX:
+			step.xkey, step.ykey = ix, -1
+			s.report(false, vx.Index(ix), nothing)
+			ix++
+		case diff.UniqueY:
+			step.xkey, step.ykey = -1, iy
+			s.report(false, nothing, vy.Index(iy))
+			iy++
+		default:
+			step.xkey, step.ykey = ix, iy
+			if e == diff.Identity {
+				s.report(true, vx.Index(ix), vy.Index(iy))
+			} else {
+				s.compareAny(vx.Index(ix), vy.Index(iy))
+			}
+			ix++
+			iy++
+		}
 	}
+	s.curPath.pop()
+	return
 }
 
 func (s *state) compareMap(vx, vy reflect.Value, t reflect.Type) {
@@ -422,9 +450,9 @@ func (s *state) compareMap(vx, vy reflect.Value, t reflect.Type) {
 		case vvx.IsValid() && vvy.IsValid():
 			s.compareAny(vvx, vvy)
 		case vvx.IsValid() && !vvy.IsValid():
-			s.report(false, vvx, reflect.Value{})
+			s.report(false, vvx, nothing)
 		case !vvx.IsValid() && vvy.IsValid():
-			s.report(false, reflect.Value{}, vvy)
+			s.report(false, nothing, vvy)
 		default:
 			// It is possible for both vvx and vvy to be invalid if the
 			// key contained a NaN value in it. There is no way in
@@ -470,7 +498,11 @@ func (s *state) compareStruct(vx, vy reflect.Value, t reflect.Type) {
 // report records the result of a single comparison.
 // It also calls Report if any reporter is registered.
 func (s *state) report(eq bool, vx, vy reflect.Value) {
-	s.eq = s.eq && eq
+	if eq {
+		s.result.NSame++
+	} else {
+		s.result.NDiff++
+	}
 	if s.reporter != nil {
 		s.reporter.Report(vx, vy, eq, s.curPath)
 	}