Check for probable infinite recursive cycles (#84)

After some hard-coded limit, check the path for recursive transformers.
Note that detecting an infinite cycle of recursive transformers
would be equivalent to solving the halting problem,
so we could misdiagnose a valid recursion as infinite.

For this reason, the check only triggers after some minimum stack size
so that correctness is not compromised for nearly all situations.
However, the threshold is low enough to trigger before the Go runtime
panics with a stack overflow (which is not recoverable).

Example panic message:
<<<
panic: recursive set of Transformers detected:
	Transformer(T1, main.main.func1): complex64 => complex128
	Transformer(T2, main.main.func2): complex128 => [2]float64
	Transformer(T3, main.main.func3): float64 => complex64
consider using cmpopts.AcyclicTransformer
>>>

Updates #77

1 files changed, 45 insertions, 0 deletions

diff --git a/cmp/compare.go b/cmp/compare.go
index 1260603..b56d634 100644
--- a/cmp/compare.go
+++ b/cmp/compare.go
@@ -29,6 +29,7 @@ package cmp
 import (
 	"fmt"
 	"reflect"
+	"strings"
 
 	"github.com/google/go-cmp/cmp/internal/diff"
 	"github.com/google/go-cmp/cmp/internal/function"
@@ -112,6 +113,10 @@ type state struct {
 	curPath  Path        // The current path in the value tree
 	reporter reporter    // Optional reporter used for difference formatting
 
+	// recChecker checks for infinite cycles applying the same set of
+	// transformers upon the output of itself.
+	recChecker recChecker
+
 	// dynChecker triggers pseudo-random checks for option correctness.
 	// It is safe for statelessCompare to mutate this value.
 	dynChecker dynChecker
@@ -181,6 +186,7 @@ func (s *state) statelessCompare(vx, vy reflect.Value) diff.Result {
 
 func (s *state) compareAny(vx, vy reflect.Value) {
 	// TODO: Support cyclic data structures.
+	s.recChecker.Check(s.curPath)
 
 	// Rule 0: Differing types are never equal.
 	if !vx.IsValid() || !vy.IsValid() {
@@ -518,6 +524,45 @@ func (s *state) report(eq bool, vx, vy reflect.Value) {
 	}
 }
 
+// recChecker tracks the state needed to periodically perform checks that
+// user provided transformers are not stuck in an infinitely recursive cycle.
+type recChecker struct{ next int }
+
+// Check scans the Path for any recursive transformers and panics when any
+// recursive transformers are detected. Note that the presence of a
+// recursive Transformer does not necessarily imply an infinite cycle.
+// As such, this check only activates after some minimal number of path steps.
+func (rc *recChecker) Check(p Path) {
+	const minLen = 1 << 16
+	if rc.next == 0 {
+		rc.next = minLen
+	}
+	if len(p) < rc.next {
+		return
+	}
+	rc.next <<= 1
+
+	// Check whether the same transformer has appeared at least twice.
+	var ss []string
+	m := map[Option]int{}
+	for _, ps := range p {
+		if t, ok := ps.(Transform); ok {
+			t := t.Option()
+			if m[t] == 1 { // Transformer was used exactly once before
+				tf := t.(*transformer).fnc.Type()
+				ss = append(ss, fmt.Sprintf("%v: %v => %v", t, tf.In(0), tf.Out(0)))
+			}
+			m[t]++
+		}
+	}
+	if len(ss) > 0 {
+		const warning = "recursive set of Transformers detected"
+		const help = "consider using cmpopts.AcyclicTransformer"
+		set := strings.Join(ss, "\n\t")
+		panic(fmt.Sprintf("%s:\n\t%s\n%s", warning, set, help))
+	}
+}
+
 // dynChecker tracks the state needed to periodically perform checks that
 // user provided functions are symmetric and deterministic.
 // The zero value is safe for immediate use.