Implement a unified difference reporter (#124)

The previous implementation of the reporter simply listed all differences,
each qualified by the full path to the difference.
This method of reporting is exact, but difficult for humans to parse.
It is one of the more common sources of complaints by users and a significant
reason why cmp is not preferred over competing libraries.

This change reimplements the reporter to format the output as a
structured literal in pseudo-Go syntax. The output resembles literals that
the user would likely have in their test code. Differences between the
x and y values are denoted by a '-' or '+' prefix at the start of the line.

An overview of the new implementation is as follows:

* report.go: The defaultReporter type implements the Reporter interface.

* report_value: Through the PushStep/PopStep API, the defaultReporter is able
to contruct an in-memory valueNode tree representing the comparison of
x and y as cmp.Equal walks the sub-values.

* report_compare.go: After report_value.go constructs an AST-representation
of the compared values, report_compare.go formats the valueNode tree as a
textNode tree, which is the textual output in a tree form.
Some relevant design decisions include:
	* The format logic goes through effort to avoid printing ignored nodes.
	* Some number of surrounding equal (but not ignored) struct fields,
	slice elements, or map entries are printed for context.
	* cmp.Equal may declare two sub-reflect.Values to be equal, but are
	different values when printed. In order to present a unified view on
	this "equal" node, the logic formats both values and arbitrarily choses
	the one with the shorter string.
	* Transformed nodes are formatted with the pseudo-Go syntax of:
		Inverse(TransformerName, OutputType{...})
	where Inverse is some magical pseudo-function that inverts the
	transformation referred to by TransformerName. The OutputType literal
	is the output of the transformation.

* report_reflect.go: This contains logic to pretty-print reflect.Values and
is relied upon by report_compare.go to format the leaves of the tree.
Note that the leaves of the tree can be any arbitrary Go type and value
(including cyclic data structures).

* report_text.go: This contains logic for purely lexicographical formatting
and is depended upon by the other report_*.go files.

Advantages:
* The output is more familiar as it uses pseudo-Go syntax for literals
* It provides context about surrounding struct fields, slice elements, or
map entries that were equal
* Inserted and removed elements in a slice are easier to visualize
* Related diffs lie on the same indentation
* For diffs in a deeply nested value, the output is easier to visualize
than having a list of all the full paths to the diff.

Disadvantages:
* The implementation is drastically more complex.
* In most cases, the output is longer (though more sparse)

1 files changed, 120 insertions, 0 deletions

diff --git a/cmp/report_value.go b/cmp/report_value.go
new file mode 100644
index 0000000..fcff486
--- /dev/null
+++ b/cmp/report_value.go
@@ -0,0 +1,120 @@
+// Copyright 2019, The Go Authors. All rights reserved.
+// Use of this source code is governed by a BSD-style
+// license that can be found in the LICENSE.md file.
+
+package cmp
+
+import "reflect"
+
+// valueNode represents a single node within a report, which is a
+// structured representation of the value tree, containing information
+// regarding which nodes are equal or not.
+type valueNode struct {
+	parent *valueNode
+
+	Type   reflect.Type
+	ValueX reflect.Value
+	ValueY reflect.Value
+
+	// NumSame is the number of leaf nodes that are equal.
+	// All descendants are equal only if NumDiff is 0.
+	NumSame int
+	// NumDiff is the number of leaf nodes that are not equal.
+	NumDiff int
+	// NumIgnored is the number of leaf nodes that are ignored.
+	NumIgnored int
+	// NumCompared is the number of leaf nodes that were compared
+	// using an Equal method or Comparer function.
+	NumCompared int
+	// NumTransformed is the number of non-leaf nodes that were transformed.
+	NumTransformed int
+	// NumChildren is the number of transitive descendants of this node.
+	// This counts from zero; thus, leaf nodes have no descendants.
+	NumChildren int
+	// MaxDepth is the maximum depth of the tree. This counts from zero;
+	// thus, leaf nodes have a depth of zero.
+	MaxDepth int
+
+	// Records is a list of struct fields, slice elements, or map entries.
+	Records []reportRecord // If populated, implies Value is not populated
+
+	// Value is the result of a transformation, pointer indirect, of
+	// type assertion.
+	Value *valueNode // If populated, implies Records is not populated
+
+	// TransformerName is the name of the transformer.
+	TransformerName string // If non-empty, implies Value is populated
+}
+type reportRecord struct {
+	Key   reflect.Value // Invalid for slice element
+	Value *valueNode
+}
+
+func (parent *valueNode) PushStep(ps PathStep) (child *valueNode) {
+	vx, vy := ps.Values()
+	child = &valueNode{parent: parent, Type: ps.Type(), ValueX: vx, ValueY: vy}
+	switch s := ps.(type) {
+	case StructField:
+		assert(parent.Value == nil)
+		parent.Records = append(parent.Records, reportRecord{Key: reflect.ValueOf(s.Name()), Value: child})
+	case SliceIndex:
+		assert(parent.Value == nil)
+		parent.Records = append(parent.Records, reportRecord{Value: child})
+	case MapIndex:
+		assert(parent.Value == nil)
+		parent.Records = append(parent.Records, reportRecord{Key: s.Key(), Value: child})
+	case Indirect:
+		assert(parent.Value == nil && parent.Records == nil)
+		parent.Value = child
+	case TypeAssertion:
+		assert(parent.Value == nil && parent.Records == nil)
+		parent.Value = child
+	case Transform:
+		assert(parent.Value == nil && parent.Records == nil)
+		parent.Value = child
+		parent.TransformerName = s.Name()
+		parent.NumTransformed++
+	default:
+		assert(parent == nil) // Must be the root step
+	}
+	return child
+}
+
+func (r *valueNode) Report(f reportFlags) {
+	assert(r.MaxDepth == 0) // May only be called on leaf nodes
+
+	if f&reportEqual > 0 {
+		r.NumSame++
+	}
+	if f&reportUnequal > 0 {
+		r.NumDiff++
+	}
+	if f&reportIgnored > 0 {
+		r.NumIgnored++
+	}
+	assert(r.NumSame+r.NumDiff+r.NumIgnored == 1)
+
+	if f&reportByMethod > 0 {
+		r.NumCompared++
+	}
+	if f&reportByFunc > 0 {
+		r.NumCompared++
+	}
+	assert(r.NumCompared <= 1)
+}
+
+func (child *valueNode) PopStep() (parent *valueNode) {
+	parent = child.parent
+	if parent != nil {
+		parent.NumSame += child.NumSame
+		parent.NumDiff += child.NumDiff
+		parent.NumIgnored += child.NumIgnored
+		parent.NumCompared += child.NumCompared
+		parent.NumTransformed += child.NumTransformed
+		parent.NumChildren += child.NumChildren + 1
+		if parent.MaxDepth < child.MaxDepth+1 {
+			parent.MaxDepth = child.MaxDepth + 1
+		}
+	}
+	return parent
+}