Add support for comparing graphs (#85)

Previously, trying to call Equal on a graph would result in a stack-overflow
due to infinite recursion traversing cycles on a graph.
While a vast majority of Go values are trees or acyclic graphs, there exist
a small number of cases where graph equality is required.

As such, we add cycle detection to Equal and define what it means for two graphs
to be equal. Contrary to reflect.DeepEqual, which declares two graphs to be
equal so long any cycle were encountered, we require two graphs to have
equivalent graph structures.

Mathematically speaking, a graph G is a tuple (V, E) consisting of the set of
vertices and edges in that graph. Graphs G1 and G2 are equal if V1 == V2,
E1 == E2, and both have the same root vertex (entry point into the graph).
When traversing G1 and G2, we remember a stack of previously visited edges
ES1 and ES2. If the current edge e1 is in ES1 or e2 is in ES2, then we know that
a cycle exists. The graphs have the same structure when the previously
encountered edge ep1 and ep2 were encountered together.
Note that edges and vertices unreachable from the root vertex are ignored.

Appreciation goes to Eyal Posener (@posener), who proposed a different
(but semantically equivalent) approach in #79, which served as inspiration.

Fixes #74

1 files changed, 45 insertions, 8 deletions

diff --git a/cmp/compare.go b/cmp/compare.go
index 8419fcc..c9a63ce 100644
--- a/cmp/compare.go
+++ b/cmp/compare.go
@@ -80,6 +80,11 @@ import (
 // Pointers and interfaces are equal if they are both nil or both non-nil,
 // where they have the same underlying concrete type and recursively
 // calling Equal on the underlying values reports equal.
+//
+// Before recursing into a pointer, slice element, or map, the current path
+// is checked to detect whether the address has already been visited.
+// If there is a cycle, then the pointed at values are considered equal
+// only if both addresses were previously visited in the same path step.
 func Equal(x, y interface{}, opts ...Option) bool {
 	vx := reflect.ValueOf(x)
 	vy := reflect.ValueOf(y)
@@ -137,6 +142,7 @@ type state struct {
 	// Calling statelessCompare must not result in observable changes to these.
 	result    diff.Result // The current result of comparison
 	curPath   Path        // The current path in the value tree
+	curPtrs   pointerPath // The current set of visited pointers
 	reporters []reporter  // Optional reporters
 
 	// recChecker checks for infinite cycles applying the same set of
@@ -155,6 +161,7 @@ type state struct {
 func newState(opts []Option) *state {
 	// Always ensure a validator option exists to validate the inputs.
 	s := &state{opts: Options{validator{}}}
+	s.curPtrs.Init()
 	s.processOption(Options(opts))
 	return s
 }
@@ -187,9 +194,9 @@ func (s *state) processOption(opt Option) {
 // This function is stateless in that it does not alter the current result,
 // or output to any registered reporters.
 func (s *state) statelessCompare(step PathStep) diff.Result {
-	// We do not save and restore the curPath because all of the compareX
-	// methods should properly push and pop from the path.
-	// It is an implementation bug if the contents of curPath differs from
+	// We do not save and restore curPath and curPtrs because all of the
+	// compareX methods should properly push and pop from them.
+	// It is an implementation bug if the contents of the paths differ from
 	// when calling this function to when returning from it.
 
 	oldResult, oldReporters := s.result, s.reporters
@@ -211,9 +218,17 @@ func (s *state) compareAny(step PathStep) {
 	}
 	s.recChecker.Check(s.curPath)
 
-	// Obtain the current type and values.
+	// Cycle-detection for slice elements (see NOTE in compareSlice).
 	t := step.Type()
 	vx, vy := step.Values()
+	if si, ok := step.(SliceIndex); ok && si.isSlice && vx.IsValid() && vy.IsValid() {
+		px, py := vx.Addr(), vy.Addr()
+		if eq, visited := s.curPtrs.Push(px, py); visited {
+			s.report(eq, reportByCycle)
+			return
+		}
+		defer s.curPtrs.Pop(px, py)
+	}
 
 	// Rule 1: Check whether an option applies on this node in the value tree.
 	if s.tryOptions(t, vx, vy) {
@@ -393,9 +408,21 @@ func (s *state) compareSlice(t reflect.Type, vx, vy reflect.Value) {
 		return
 	}
 
-	// TODO: Support cyclic data structures.
+	// NOTE: It is incorrect to call curPtrs.Push on the slice header pointer
+	// since slices represents a list of pointers, rather than a single pointer.
+	// The pointer checking logic must be handled on a per-element basis
+	// in compareAny.
+	//
+	// A slice header (see reflect.SliceHeader) in Go is a tuple of a starting
+	// pointer P, a length N, and a capacity C. Supposing each slice element has
+	// a memory size of M, then the slice is equivalent to the list of pointers:
+	//	[P+i*M for i in range(N)]
+	//
+	// For example, v[:0] and v[:1] are slices with the same starting pointer,
+	// but they are clearly different values. Using the slice pointer alone
+	// violates the assumption that equal pointers implies equal values.
 
-	step := SliceIndex{&sliceIndex{pathStep: pathStep{typ: t.Elem()}}}
+	step := SliceIndex{&sliceIndex{pathStep: pathStep{typ: t.Elem()}, isSlice: isSlice}}
 	withIndexes := func(ix, iy int) SliceIndex {
 		if ix >= 0 {
 			step.vx, step.xkey = vx.Index(ix), ix
@@ -472,7 +499,12 @@ func (s *state) compareMap(t reflect.Type, vx, vy reflect.Value) {
 		return
 	}
 
-	// TODO: Support cyclic data structures.
+	// Cycle-detection for maps.
+	if eq, visited := s.curPtrs.Push(vx, vy); visited {
+		s.report(eq, reportByCycle)
+		return
+	}
+	defer s.curPtrs.Pop(vx, vy)
 
 	// We combine and sort the two map keys so that we can perform the
 	// comparisons in a deterministic order.
@@ -509,7 +541,12 @@ func (s *state) comparePtr(t reflect.Type, vx, vy reflect.Value) {
 		return
 	}
 
-	// TODO: Support cyclic data structures.
+	// Cycle-detection for pointers.
+	if eq, visited := s.curPtrs.Push(vx, vy); visited {
+		s.report(eq, reportByCycle)
+		return
+	}
+	defer s.curPtrs.Pop(vx, vy)
 
 	vx, vy = vx.Elem(), vy.Elem()
 	s.compareAny(Indirect{&indirect{pathStep{t.Elem(), vx, vy}}})