Refactor reporter implementation (#112)

Switch the internal interface for reporting to use a push-pop mechanism.
This API is strictly more flexible than the previous Report-only API since it
enables the reporter to re-construct the entire value tree.

This change is done in preparation for a major overhaul of reporter logic.

4 files changed, 196 insertions, 93 deletions

diff --git a/cmp/compare.go b/cmp/compare.go
index a7bcaab..654f46a 100644
--- a/cmp/compare.go
+++ b/cmp/compare.go
@@ -77,8 +77,32 @@ var nothing = reflect.Value{}
 // Map keys are equal according to the == operator.
 // To use custom comparisons for map keys, consider using cmpopts.SortMaps.
 func Equal(x, y interface{}, opts ...Option) bool {
+	vx := reflect.ValueOf(x)
+	vy := reflect.ValueOf(y)
+
+	// If the inputs are different types, auto-wrap them in an empty interface
+	// so that they have the same parent type.
+	var t reflect.Type
+	if !vx.IsValid() || !vy.IsValid() || vx.Type() != vy.Type() {
+		t = reflect.TypeOf((*interface{})(nil)).Elem()
+		if vx.IsValid() {
+			vvx := reflect.New(t).Elem()
+			vvx.Set(vx)
+			vx = vvx
+		}
+		if vy.IsValid() {
+			vvy := reflect.New(t).Elem()
+			vvy.Set(vy)
+			vy = vvy
+		}
+	} else {
+		t = vx.Type()
+	}
+
 	s := newState(opts)
-	s.compareAny(reflect.ValueOf(x), reflect.ValueOf(y))
+	s.pushStep(&pathStep{typ: t}, vx, vy)
+	s.compareAny(vx, vy)
+	s.popStep()
 	return s.result.Equal()
 }
 
@@ -91,7 +115,7 @@ func Equal(x, y interface{}, opts ...Option) bool {
 // Do not depend on this output being stable.
 func Diff(x, y interface{}, opts ...Option) string {
 	r := new(defaultReporter)
-	opts = Options{Options(opts), r}
+	opts = Options{Options(opts), reporter(r)}
 	eq := Equal(x, y, opts...)
 	d := r.String()
 	if (d == "") != eq {
@@ -103,9 +127,9 @@ func Diff(x, y interface{}, opts ...Option) string {
 type state struct {
 	// These fields represent the "comparison state".
 	// 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
-	reporter reporter    // Optional reporter used for difference formatting
+	result    diff.Result      // The current result of comparison
+	curPath   Path             // The current path in the value tree
+	reporters []reporterOption // Optional reporters
 
 	// recChecker checks for infinite cycles applying the same set of
 	// transformers upon the output of itself.
@@ -150,11 +174,8 @@ func (s *state) processOption(opt Option) {
 		for t := range opt {
 			s.exporters[t] = true
 		}
-	case reporter:
-		if s.reporter != nil {
-			panic("difference reporter already registered")
-		}
-		s.reporter = opt
+	case reporterOption:
+		s.reporters = append(s.reporters, opt)
 	default:
 		panic(fmt.Sprintf("unknown option %T", opt))
 	}
@@ -169,12 +190,12 @@ func (s *state) statelessCompare(vx, vy reflect.Value) diff.Result {
 	// It is an implementation bug if the contents of curPath differs from
 	// when calling this function to when returning from it.
 
-	oldResult, oldReporter := s.result, s.reporter
+	oldResult, oldReporters := s.result, s.reporters
 	s.result = diff.Result{} // Reset result
-	s.reporter = nil         // Remove reporter to avoid spurious printouts
+	s.reporters = nil        // Remove reporters to avoid spurious printouts
 	s.compareAny(vx, vy)
 	res := s.result
-	s.result, s.reporter = oldResult, oldReporter
+	s.result, s.reporters = oldResult, oldReporters
 	return res
 }
 
@@ -184,18 +205,14 @@ func (s *state) compareAny(vx, vy reflect.Value) {
 
 	// Rule 0: Differing types are never equal.
 	if !vx.IsValid() || !vy.IsValid() {
-		s.report(vx.IsValid() == vy.IsValid(), vx, vy)
+		s.report(vx.IsValid() == vy.IsValid())
 		return
 	}
 	if vx.Type() != vy.Type() {
-		s.report(false, vx, vy) // Possible for path to be empty
+		s.report(false)
 		return
 	}
 	t := vx.Type()
-	if len(s.curPath) == 0 {
-		s.curPath.push(&pathStep{typ: t})
-		defer s.curPath.pop()
-	}
 	vx, vy = s.tryExporting(vx, vy)
 
 	// Rule 1: Check whether an option applies on this node in the value tree.
@@ -211,35 +228,35 @@ func (s *state) compareAny(vx, vy reflect.Value) {
 	// Rule 3: Recursively descend into each value's underlying kind.
 	switch t.Kind() {
 	case reflect.Bool:
-		s.report(vx.Bool() == vy.Bool(), vx, vy)
+		s.report(vx.Bool() == vy.Bool())
 		return
 	case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64:
-		s.report(vx.Int() == vy.Int(), vx, vy)
+		s.report(vx.Int() == vy.Int())
 		return
 	case reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr:
-		s.report(vx.Uint() == vy.Uint(), vx, vy)
+		s.report(vx.Uint() == vy.Uint())
 		return
 	case reflect.Float32, reflect.Float64:
-		s.report(vx.Float() == vy.Float(), vx, vy)
+		s.report(vx.Float() == vy.Float())
 		return
 	case reflect.Complex64, reflect.Complex128:
-		s.report(vx.Complex() == vy.Complex(), vx, vy)
+		s.report(vx.Complex() == vy.Complex())
 		return
 	case reflect.String:
-		s.report(vx.String() == vy.String(), vx, vy)
+		s.report(vx.String() == vy.String())
 		return
 	case reflect.Chan, reflect.UnsafePointer:
-		s.report(vx.Pointer() == vy.Pointer(), vx, vy)
+		s.report(vx.Pointer() == vy.Pointer())
 		return
 	case reflect.Func:
-		s.report(vx.IsNil() && vy.IsNil(), vx, vy)
+		s.report(vx.IsNil() && vy.IsNil())
 		return
 	case reflect.Struct:
 		s.compareStruct(vx, vy, t)
 		return
 	case reflect.Slice:
 		if vx.IsNil() || vy.IsNil() {
-			s.report(vx.IsNil() && vy.IsNil(), vx, vy)
+			s.report(vx.IsNil() && vy.IsNil())
 			return
 		}
 		fallthrough
@@ -251,25 +268,27 @@ func (s *state) compareAny(vx, vy reflect.Value) {
 		return
 	case reflect.Ptr:
 		if vx.IsNil() || vy.IsNil() {
-			s.report(vx.IsNil() && vy.IsNil(), vx, vy)
+			s.report(vx.IsNil() && vy.IsNil())
 			return
 		}
-		s.curPath.push(&indirect{pathStep{t.Elem()}})
-		defer s.curPath.pop()
-		s.compareAny(vx.Elem(), vy.Elem())
+		vx, vy = vx.Elem(), vy.Elem()
+		s.pushStep(&indirect{pathStep{t.Elem()}}, vx, vy)
+		s.compareAny(vx, vy)
+		s.popStep()
 		return
 	case reflect.Interface:
 		if vx.IsNil() || vy.IsNil() {
-			s.report(vx.IsNil() && vy.IsNil(), vx, vy)
+			s.report(vx.IsNil() && vy.IsNil())
 			return
 		}
-		if vx.Elem().Type() != vy.Elem().Type() {
-			s.report(false, vx.Elem(), vy.Elem())
+		vx, vy = vx.Elem(), vy.Elem()
+		if vx.Type() != vy.Type() {
+			s.report(false)
 			return
 		}
-		s.curPath.push(&typeAssertion{pathStep{vx.Elem().Type()}})
-		defer s.curPath.pop()
-		s.compareAny(vx.Elem(), vy.Elem())
+		s.pushStep(&typeAssertion{pathStep{vx.Type()}}, vx, vy)
+		s.compareAny(vx, vy)
+		s.popStep()
 		return
 	default:
 		panic(fmt.Sprintf("%v kind not handled", t.Kind()))
@@ -318,7 +337,7 @@ func (s *state) tryMethod(vx, vy reflect.Value, t reflect.Type) bool {
 	}
 
 	eq := s.callTTBFunc(m.Func, vx, vy)
-	s.report(eq, vx, vy)
+	s.report(eq)
 	return true
 }
 
@@ -391,11 +410,8 @@ func (s *state) compareStruct(vx, vy reflect.Value, t reflect.Type) {
 	var vax, vay reflect.Value // Addressable versions of vx and vy
 
 	step := &structField{}
-	s.curPath.push(step)
-	defer s.curPath.pop()
 	for i := 0; i < t.NumField(); i++ {
-		vvx := vx.Field(i)
-		vvy := vy.Field(i)
+		vvx, vvy := vx.Field(i), vy.Field(i)
 		step.typ = t.Field(i).Type
 		step.name = t.Field(i).Name
 		step.idx = i
@@ -418,18 +434,22 @@ func (s *state) compareStruct(vx, vy reflect.Value, t reflect.Type) {
 			step.pvy = vay
 			step.field = t.Field(i)
 		}
+		s.pushStep(step, vvx, vvy)
 		s.compareAny(vvx, vvy)
+		s.popStep()
 	}
 }
 
 func (s *state) compareSlice(vx, vy reflect.Value, t reflect.Type) {
 	step := &sliceIndex{pathStep{t.Elem()}, 0, 0}
-	s.curPath.push(step)
 
 	// Compute an edit-script for slices vx and vy.
 	es := diff.Difference(vx.Len(), vy.Len(), func(ix, iy int) diff.Result {
 		step.xkey, step.ykey = ix, iy
-		return s.statelessCompare(vx.Index(ix), vy.Index(iy))
+		s.curPath.push(step)
+		ret := s.statelessCompare(vx.Index(ix), vy.Index(iy))
+		s.curPath.pop()
+		return ret
 	})
 
 	// Report the entire slice as is if the arrays are of primitive kind,
@@ -442,8 +462,7 @@ func (s *state) compareSlice(vx, vy reflect.Value, t reflect.Type) {
 		isPrimitive = true
 	}
 	if isPrimitive && es.Dist() > (vx.Len()+vy.Len())/4 {
-		s.curPath.pop() // Pop first since we are reporting the whole slice
-		s.report(false, vx, vy)
+		s.report(false)
 		return
 	}
 
@@ -453,49 +472,55 @@ func (s *state) compareSlice(vx, vy reflect.Value, t reflect.Type) {
 		switch e {
 		case diff.UniqueX:
 			step.xkey, step.ykey = ix, -1
-			s.report(false, vx.Index(ix), nothing)
+			vvx := vx.Index(ix)
+			s.pushStep(step, vvx, nothing)
+			s.report(false)
+			s.popStep()
 			ix++
 		case diff.UniqueY:
 			step.xkey, step.ykey = -1, iy
-			s.report(false, nothing, vy.Index(iy))
+			vvy := vy.Index(iy)
+			s.pushStep(step, nothing, vvy)
+			s.report(false)
+			s.popStep()
 			iy++
 		default:
 			step.xkey, step.ykey = ix, iy
+			vvx, vvy := vx.Index(ix), vy.Index(iy)
+			s.pushStep(step, vvx, vvy)
 			if e == diff.Identity {
-				s.report(true, vx.Index(ix), vy.Index(iy))
+				s.report(true)
 			} else {
-				s.compareAny(vx.Index(ix), vy.Index(iy))
+				s.compareAny(vvx, vvy)
 			}
+			s.popStep()
 			ix++
 			iy++
 		}
 	}
-	s.curPath.pop()
 	return
 }
 
 func (s *state) compareMap(vx, vy reflect.Value, t reflect.Type) {
 	if vx.IsNil() || vy.IsNil() {
-		s.report(vx.IsNil() && vy.IsNil(), vx, vy)
+		s.report(vx.IsNil() && vy.IsNil())
 		return
 	}
 
 	// We combine and sort the two map keys so that we can perform the
 	// comparisons in a deterministic order.
 	step := &mapIndex{pathStep: pathStep{t.Elem()}}
-	s.curPath.push(step)
-	defer s.curPath.pop()
 	for _, k := range value.SortKeys(append(vx.MapKeys(), vy.MapKeys()...)) {
 		step.key = k
-		vvx := vx.MapIndex(k)
-		vvy := vy.MapIndex(k)
+		vvx, vvy := vx.MapIndex(k), vy.MapIndex(k)
+		s.pushStep(step, vvx, vvy)
 		switch {
 		case vvx.IsValid() && vvy.IsValid():
 			s.compareAny(vvx, vvy)
 		case vvx.IsValid() && !vvy.IsValid():
-			s.report(false, vvx, nothing)
+			s.report(false)
 		case !vvx.IsValid() && vvy.IsValid():
-			s.report(false, nothing, vvy)
+			s.report(false)
 		default:
 			// It is possible for both vvx and vvy to be invalid if the
 			// key contained a NaN value in it.
@@ -514,19 +539,42 @@ func (s *state) compareMap(vx, vy reflect.Value, t reflect.Type) {
 			const help = "consider providing a Comparer to compare the map"
 			panic(fmt.Sprintf("%#v has map key with NaNs\n%s", s.curPath, help))
 		}
+		s.popStep()
 	}
 }
 
-// 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) {
+func (s *state) pushStep(ps PathStep, x, y reflect.Value) {
+	s.curPath.push(ps)
+	for _, r := range s.reporters {
+		r.PushStep(ps, x, y)
+	}
+}
+
+func (s *state) popStep() {
+	s.curPath.pop()
+	for _, r := range s.reporters {
+		r.PopStep()
+	}
+}
+
+func (s *state) report(eq bool) {
 	if eq {
 		s.result.NSame++
 	} else {
 		s.result.NDiff++
 	}
-	if s.reporter != nil {
-		s.reporter.Report(vx, vy, eq, s.curPath)
+	for _, r := range s.reporters {
+		if eq {
+			r.Report(reportEqual)
+		} else {
+			r.Report(reportUnequal)
+		}
+	}
+}
+
+func (s *state) reportIgnore() {
+	for _, r := range s.reporters {
+		r.Report(reportIgnore)
 	}
 }
 
diff --git a/cmp/compare_test.go b/cmp/compare_test.go
index c98b088..0a850f9 100644
--- a/cmp/compare_test.go
+++ b/cmp/compare_test.go
@@ -335,7 +335,7 @@ root:
 		x:     new(fmt.Stringer),
 		y:     nil,
 		wantDiff: `
-:
+root:
 	-: &<nil>
 	+: <non-existent>`,
 	}, {
@@ -426,7 +426,7 @@ root:
 		// Ensure Stringer avoids double-quote escaping if possible.
 		label:    label,
 		x:        []*pb.Stringer{{`multi\nline\nline\nline`}},
-		wantDiff: ":\n\t-: []*testprotos.Stringer{s`multi\\nline\\nline\\nline`}\n\t+: <non-existent>",
+		wantDiff: "root:\n\t-: []*testprotos.Stringer{s`multi\\nline\\nline\\nline`}\n\t+: <non-existent>",
 	}, {
 		label: label,
 		x:     struct{ I Iface2 }{},
diff --git a/cmp/options.go b/cmp/options.go
index a9306b4..a8307dc 100644
--- a/cmp/options.go
+++ b/cmp/options.go
@@ -193,7 +193,7 @@ type ignore struct{ core }
 
 func (ignore) isFiltered() bool                                                     { return false }
 func (ignore) filter(_ *state, _, _ reflect.Value, _ reflect.Type) applicableOption { return ignore{} }
-func (ignore) apply(_ *state, _, _ reflect.Value)                                   { return }
+func (ignore) apply(s *state, _, _ reflect.Value)                                   { s.reportIgnore() }
 func (ignore) String() string                                                       { return "Ignore()" }
 
 // invalid is a sentinel Option type to indicate that some options could not
@@ -277,12 +277,15 @@ func (tr *transformer) filter(s *state, _, _ reflect.Value, t reflect.Type) appl
 func (tr *transformer) apply(s *state, vx, vy reflect.Value) {
 	// Update path before calling the Transformer so that dynamic checks
 	// will use the updated path.
-	s.curPath.push(&transform{pathStep{tr.fnc.Type().Out(0)}, tr})
-	defer s.curPath.pop()
-
-	vx = s.callTRFunc(tr.fnc, vx)
-	vy = s.callTRFunc(tr.fnc, vy)
-	s.compareAny(vx, vy)
+	step := &transform{pathStep{tr.fnc.Type().Out(0)}, tr}
+	s.curPath.push(step)
+	vvx := s.callTRFunc(tr.fnc, vx)
+	vvy := s.callTRFunc(tr.fnc, vy)
+	s.curPath.pop()
+
+	s.pushStep(step, vvx, vvy)
+	s.compareAny(vvx, vvy)
+	s.popStep()
 }
 
 func (tr transformer) String() string {
@@ -330,7 +333,7 @@ func (cm *comparer) filter(_ *state, _, _ reflect.Value, t reflect.Type) applica
 
 func (cm *comparer) apply(s *state, vx, vy reflect.Value) {
 	eq := s.callTTBFunc(cm.fnc, vx, vy)
-	s.report(eq, vx, vy)
+	s.report(eq)
 }
 
 func (cm comparer) String() string {
@@ -384,23 +387,61 @@ func (visibleStructs) filter(_ *state, _, _ reflect.Value, _ reflect.Type) appli
 	panic("not implemented")
 }
 
-// reporter is an Option that configures how differences are reported.
-type reporter interface {
-	// TODO: Not exported yet.
+type reportFlags uint64
+
+const (
+	_ reportFlags = (1 << iota) / 2
+
+	// reportEqual reports whether the node is equal.
+	// It may not be issued with reportIgnore or reportUnequal.
+	reportEqual
+	// reportUnequal reports whether the node is not equal.
+	// It may not be issued with reportIgnore or reportEqual.
+	reportUnequal
+	// reportIgnore reports whether the node was ignored.
+	// It may not be issued with reportEqual or reportUnequal.
+	reportIgnore
+)
+
+// reporter is an Option that can be passed to Equal. When Equal traverses
+// the value trees, it calls PushStep as it descends into each node in the
+// tree and PopStep as it ascend out of the node. The leaves of the tree are
+// either compared (determined to be equal or not equal) or ignored and reported
+// as such by calling the Report method.
+func reporter(r interface {
+	// TODO: Export this option.
+
+	// PushStep is called when a tree-traversal operation is performed
+	// and provides the sub-values of x and y after applying the operation.
+	// The PathStep is valid until the step is popped, while the reflect.Values
+	// are valid while the entire tree is still being traversed.
 	//
-	// Perhaps add PushStep and PopStep and change Report to only accept
-	// a PathStep instead of the full-path? Adding a PushStep and PopStep makes
-	// it clear that we are traversing the value tree in a depth-first-search
-	// manner, which has an effect on how values are printed.
+	// Equal and Diff always call PushStep at the start to provide an
+	// operation-less PathStep used to report the root values.
+	PushStep(ps PathStep, x, y reflect.Value)
+
+	// Report is called at exactly once on leaf nodes to report whether the
+	// comparison identified the node as equal, unequal, or ignored.
+	// A leaf node is one that is immediately preceded by and followed by
+	// a pair of PushStep and PopStep calls.
+	Report(reportFlags)
+
+	// PopStep ascends back up the value tree.
+	// There is always a matching pop call for every push call.
+	PopStep()
+}) Option {
+	return reporterOption{r}
+}
 
-	Option
+type reporterOption struct{ reporterIface }
+type reporterIface interface {
+	PushStep(PathStep, reflect.Value, reflect.Value)
+	Report(reportFlags)
+	PopStep()
+}
 
-	// Report is called for every comparison made and will be provided with
-	// the two values being compared, the equality result, and the
-	// current path in the value tree. It is possible for x or y to be an
-	// invalid reflect.Value if one of the values is non-existent;
-	// which is possible with maps and slices.
-	Report(x, y reflect.Value, eq bool, p Path)
+func (reporterOption) filter(_ *state, _, _ reflect.Value, _ reflect.Type) applicableOption {
+	panic("not implemented")
 }
 
 // normalizeOption normalizes the input options such that all Options groups
diff --git a/cmp/reporter.go b/cmp/report.go
index 20e9f18..327f332 100644
--- a/cmp/reporter.go
+++ b/cmp/report.go
@@ -14,18 +14,32 @@ import (
 
 type defaultReporter struct {
 	Option
+
+	curPath Path
+	curVals [][2]reflect.Value
+
 	diffs  []string // List of differences, possibly truncated
 	ndiffs int      // Total number of differences
 	nbytes int      // Number of bytes in diffs
 	nlines int      // Number of lines in diffs
 }
 
-var _ reporter = (*defaultReporter)(nil)
-
-func (r *defaultReporter) Report(x, y reflect.Value, eq bool, p Path) {
-	if eq {
-		return // Ignore equal results
+func (r *defaultReporter) PushStep(ps PathStep, x, y reflect.Value) {
+	r.curPath.push(ps)
+	r.curVals = append(r.curVals, [2]reflect.Value{x, y})
+}
+func (r *defaultReporter) Report(f reportFlags) {
+	if f == reportUnequal {
+		vs := r.curVals[len(r.curVals)-1]
+		r.report(vs[0], vs[1], r.curPath)
 	}
+}
+func (r *defaultReporter) PopStep() {
+	r.curPath.pop()
+	r.curVals = r.curVals[:len(r.curVals)-1]
+}
+
+func (r *defaultReporter) report(x, y reflect.Value, p Path) {
 	const maxBytes = 4096
 	const maxLines = 256
 	r.ndiffs++