Add Values method to PathStep (#119)

Some of the value information is already in the path (e.g., MapIndex.Key
and SliceIndex.Key), which seems to suggest that all of the value information
should be in the Path. Doing so has several benefits:
	* It simplifies the comparison logic
	* It paves the way for FilterPath to be able to ignore missing
	slice elements or map entries
	* It allows for a simpler API for custom reporters

One regression introduced by this change is the removal of batching for
slices when sufficient number of elements differ. This logic was added
as a hack in the past to keep the reporter output small in such cases.
However, this batching functionality should be the responsibility of the
reporter logic, not the comparer logic. A future change will refactor
the reporter logic to reintroduce that feature.

6 files changed, 301 insertions, 216 deletions

diff --git a/cmp/compare.go b/cmp/compare.go
index fda1670..8502c6b 100644
--- a/cmp/compare.go
+++ b/cmp/compare.go
@@ -36,14 +36,9 @@ import (
 	"github.com/google/go-cmp/cmp/internal/value"
 )
 
-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:
 //
-// • If two values are not of the same type, then they are never equal
-// and the overall result is false.
-//
 // • Let S be the set of all Ignore, Transformer, and Comparer options that
 // remain after applying all path filters, value filters, and type filters.
 // If at least one Ignore exists in S, then the comparison is ignored.
@@ -56,26 +51,34 @@ var nothing = reflect.Value{}
 //
 // • If the values have an Equal method of the form "(T) Equal(T) bool" or
 // "(T) Equal(I) bool" where T is assignable to I, then use the result of
-// x.Equal(y) even if x or y is nil.
-// Otherwise, no such method exists and evaluation proceeds to the next rule.
+// x.Equal(y) even if x or y is nil. Otherwise, no such method exists and
+// evaluation proceeds to the next rule.
 //
 // • Lastly, try to compare x and y based on their basic kinds.
 // Simple kinds like booleans, integers, floats, complex numbers, strings, and
 // channels are compared using the equivalent of the == operator in Go.
 // Functions are only equal if they are both nil, otherwise they are unequal.
-// Pointers are equal if the underlying values they point to are also equal.
-// Interfaces are equal if their underlying concrete values are also equal.
 //
-// Structs are equal if all of their fields are equal. If a struct contains
-// unexported fields, Equal panics unless the AllowUnexported option is used or
-// an Ignore option (e.g., cmpopts.IgnoreUnexported) ignores that field.
+// Structs are equal if recursively calling Equal on all fields report equal.
+// If a struct contains unexported fields, Equal panics unless an Ignore option
+// (e.g., cmpopts.IgnoreUnexported) ignores that field or the AllowUnexported
+// option explicitly permits comparing the unexported field.
+//
+// Slices are equal if they are both nil or both non-nil, where recursively
+// calling Equal on all slice or array elements report equal.
+// Empty non-nil slices and nil slices are not equal; to equate empty slices,
+// consider using cmpopts.EquateEmpty.
 //
-// Arrays, slices, and maps are equal if they are both nil or both non-nil
-// with the same length and the elements at each index or key are equal.
-// Note that a non-nil empty slice and a nil slice are not equal.
-// To equate empty slices and maps, consider using cmpopts.EquateEmpty.
+// Maps are equal if they are both nil or both non-nil, where recursively
+// calling Equal on all map entries report equal.
 // Map keys are equal according to the == operator.
 // To use custom comparisons for map keys, consider using cmpopts.SortMaps.
+// Empty non-nil maps and nil maps are not equal; to equate empty maps,
+// consider using cmpopts.EquateEmpty.
+//
+// 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.
 func Equal(x, y interface{}, opts ...Option) bool {
 	vx := reflect.ValueOf(x)
 	vy := reflect.ValueOf(y)
@@ -100,9 +103,7 @@ func Equal(x, y interface{}, opts ...Option) bool {
 	}
 
 	s := newState(opts)
-	s.pushStep(&pathStep{typ: t}, vx, vy)
-	s.compareAny(vx, vy)
-	s.popStep()
+	s.compareAny(&pathStep{t, vx, vy})
 	return s.result.Equal()
 }
 
@@ -184,7 +185,7 @@ func (s *state) processOption(opt Option) {
 // statelessCompare compares two values and returns the result.
 // This function is stateless in that it does not alter the current result,
 // or output to any registered reporters.
-func (s *state) statelessCompare(vx, vy reflect.Value) diff.Result {
+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
@@ -193,35 +194,42 @@ func (s *state) statelessCompare(vx, vy reflect.Value) diff.Result {
 	oldResult, oldReporters := s.result, s.reporters
 	s.result = diff.Result{} // Reset result
 	s.reporters = nil        // Remove reporters to avoid spurious printouts
-	s.compareAny(vx, vy)
+	s.compareAny(step)
 	res := s.result
 	s.result, s.reporters = oldResult, oldReporters
 	return res
 }
 
-func (s *state) compareAny(vx, vy reflect.Value) {
+func (s *state) compareAny(step PathStep) {
 	// TODO: Support cyclic data structures.
+
+	// Update the path stack.
+	s.curPath.push(step)
+	defer s.curPath.pop()
+	for _, r := range s.reporters {
+		r.PushStep(step)
+		defer r.PopStep()
+	}
 	s.recChecker.Check(s.curPath)
 
-	// Rule 0: Differing types are never equal.
+	// Obtain the current type and values.
+	t := step.Type()
+	vx, vy := step.Values()
+
+	// TODO: Removing this check allows us FilterPath to operate on missing
+	// slice elements and map entries.
 	if !vx.IsValid() || !vy.IsValid() {
 		s.report(vx.IsValid() == vy.IsValid())
 		return
 	}
-	if vx.Type() != vy.Type() {
-		s.report(false)
-		return
-	}
-	t := vx.Type()
-	vx, vy = s.tryExporting(vx, vy)
 
 	// Rule 1: Check whether an option applies on this node in the value tree.
-	if s.tryOptions(vx, vy, t) {
+	if s.tryOptions(t, vx, vy) {
 		return
 	}
 
 	// Rule 2: Check whether the type has a valid Equal method.
-	if s.tryMethod(vx, vy, t) {
+	if s.tryMethod(t, vx, vy) {
 		return
 	}
 
@@ -252,7 +260,7 @@ func (s *state) compareAny(vx, vy reflect.Value) {
 		s.report(vx.IsNil() && vy.IsNil())
 		return
 	case reflect.Struct:
-		s.compareStruct(vx, vy, t)
+		s.compareStruct(t, vx, vy)
 		return
 	case reflect.Slice:
 		if vx.IsNil() || vy.IsNil() {
@@ -261,10 +269,10 @@ func (s *state) compareAny(vx, vy reflect.Value) {
 		}
 		fallthrough
 	case reflect.Array:
-		s.compareSlice(vx, vy, t)
+		s.compareSlice(t, vx, vy)
 		return
 	case reflect.Map:
-		s.compareMap(vx, vy, t)
+		s.compareMap(t, vx, vy)
 		return
 	case reflect.Ptr:
 		if vx.IsNil() || vy.IsNil() {
@@ -272,9 +280,7 @@ func (s *state) compareAny(vx, vy reflect.Value) {
 			return
 		}
 		vx, vy = vx.Elem(), vy.Elem()
-		s.pushStep(&indirect{pathStep{t.Elem()}}, vx, vy)
-		s.compareAny(vx, vy)
-		s.popStep()
+		s.compareAny(&indirect{pathStep{t.Elem(), vx, vy}})
 		return
 	case reflect.Interface:
 		if vx.IsNil() || vy.IsNil() {
@@ -286,49 +292,31 @@ func (s *state) compareAny(vx, vy reflect.Value) {
 			s.report(false)
 			return
 		}
-		s.pushStep(&typeAssertion{pathStep{vx.Type()}}, vx, vy)
-		s.compareAny(vx, vy)
-		s.popStep()
+		s.compareAny(&typeAssertion{pathStep{vx.Type(), vx, vy}})
 		return
 	default:
 		panic(fmt.Sprintf("%v kind not handled", t.Kind()))
 	}
 }
 
-func (s *state) tryExporting(vx, vy reflect.Value) (reflect.Value, reflect.Value) {
-	if sf, ok := s.curPath[len(s.curPath)-1].(*structField); ok && sf.unexported {
-		if sf.force {
-			// Forcibly obtain read-write access to an unexported struct field.
-			vx = retrieveUnexportedField(sf.pvx, sf.field)
-			vy = retrieveUnexportedField(sf.pvy, sf.field)
-		} else {
-			// We are not allowed to export the value, so invalidate them
-			// so that tryOptions can panic later if not explicitly ignored.
-			vx = nothing
-			vy = nothing
-		}
-	}
-	return vx, vy
-}
-
-func (s *state) tryOptions(vx, vy reflect.Value, t reflect.Type) bool {
+func (s *state) tryOptions(t reflect.Type, vx, vy reflect.Value) bool {
 	// If there were no FilterValues, we will not detect invalid inputs,
-	// so manually check for them and append invalid if necessary.
+	// so manually check for them and append a validator if necessary.
 	// We still evaluate the options since an ignore can override invalid.
 	opts := s.opts
-	if !vx.IsValid() || !vy.IsValid() {
-		opts = Options{opts, invalid{}}
+	if !vx.IsValid() || !vx.CanInterface() || !vy.IsValid() || !vy.CanInterface() {
+		opts = Options{opts, validator{}}
 	}
 
 	// Evaluate all filters and apply the remaining options.
-	if opt := opts.filter(s, vx, vy, t); opt != nil {
+	if opt := opts.filter(s, t, vx, vy); opt != nil {
 		opt.apply(s, vx, vy)
 		return true
 	}
 	return false
 }
 
-func (s *state) tryMethod(vx, vy reflect.Value, t reflect.Type) bool {
+func (s *state) tryMethod(t reflect.Type, vx, vy reflect.Value) bool {
 	// Check if this type even has an Equal method.
 	m, ok := t.MethodByName("Equal")
 	if !ok || !function.IsType(m.Type, function.EqualAssignable) {
@@ -340,7 +328,7 @@ func (s *state) tryMethod(vx, vy reflect.Value, t reflect.Type) bool {
 	return true
 }
 
-func (s *state) callTRFunc(f, v reflect.Value) reflect.Value {
+func (s *state) callTRFunc(f, v reflect.Value, step *transform) reflect.Value {
 	v = sanitizeValue(v, f.Type().In(0))
 	if !s.dynChecker.Next() {
 		return f.Call([]reflect.Value{v})[0]
@@ -351,11 +339,12 @@ func (s *state) callTRFunc(f, v reflect.Value) reflect.Value {
 	// unsafe mutations to the input.
 	c := make(chan reflect.Value)
 	go detectRaces(c, f, v)
+	got := <-c
 	want := f.Call([]reflect.Value{v})[0]
-	if got := <-c; !s.statelessCompare(got, want).Equal() {
+	if step.vx, step.vy = got, want; !s.statelessCompare(step).Equal() {
 		// To avoid false-positives with non-reflexive equality operations,
 		// we sanity check whether a value is equal to itself.
-		if !s.statelessCompare(want, want).Equal() {
+		if step.vx, step.vy = want, want; !s.statelessCompare(step).Equal() {
 			return want
 		}
 		panic(fmt.Sprintf("non-deterministic function detected: %s", function.NameOf(f)))
@@ -376,8 +365,9 @@ func (s *state) callTTBFunc(f, x, y reflect.Value) bool {
 	// unsafe mutations to the input.
 	c := make(chan reflect.Value)
 	go detectRaces(c, f, y, x)
+	got := <-c
 	want := f.Call([]reflect.Value{x, y})[0].Bool()
-	if got := <-c; !got.IsValid() || got.Bool() != want {
+	if !got.IsValid() || got.Bool() != want {
 		panic(fmt.Sprintf("non-deterministic or non-symmetric function detected: %s", function.NameOf(f)))
 	}
 	return want
@@ -405,13 +395,14 @@ func sanitizeValue(v reflect.Value, t reflect.Type) reflect.Value {
 	return v
 }
 
-func (s *state) compareStruct(vx, vy reflect.Value, t reflect.Type) {
+func (s *state) compareStruct(t reflect.Type, vx, vy reflect.Value) {
 	var vax, vay reflect.Value // Addressable versions of vx and vy
 
 	step := &structField{}
 	for i := 0; i < t.NumField(); i++ {
-		vvx, vvy := vx.Field(i), vy.Field(i)
 		step.typ = t.Field(i).Type
+		step.vx = vx.Field(i)
+		step.vy = vy.Field(i)
 		step.name = t.Field(i).Name
 		step.idx = i
 		step.unexported = !isExported(step.name)
@@ -428,71 +419,48 @@ func (s *state) compareStruct(vx, vy reflect.Value, t reflect.Type) {
 				vax = makeAddressable(vx)
 				vay = makeAddressable(vy)
 			}
-			step.force = s.exporters[t]
+			step.mayForce = s.exporters[t]
 			step.pvx = vax
 			step.pvy = vay
 			step.field = t.Field(i)
 		}
-		s.pushStep(step, vvx, vvy)
-		s.compareAny(vvx, vvy)
-		s.popStep()
+		s.compareAny(step)
 	}
 }
 
-func (s *state) compareSlice(vx, vy reflect.Value, t reflect.Type) {
-	step := &sliceIndex{pathStep{t.Elem()}, 0, 0}
+func (s *state) compareSlice(t reflect.Type, vx, vy reflect.Value) {
+	step := &sliceIndex{pathStep: pathStep{typ: t.Elem()}}
+	withIndexes := func(ix, iy int) *sliceIndex {
+		if ix >= 0 {
+			step.vx, step.xkey = vx.Index(ix), ix
+		} else {
+			step.vx, step.xkey = reflect.Value{}, -1
+		}
+		if iy >= 0 {
+			step.vy, step.ykey = vy.Index(iy), iy
+		} else {
+			step.vy, step.ykey = reflect.Value{}, -1
+		}
+		return 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
-		s.curPath.push(step)
-		ret := s.statelessCompare(vx.Index(ix), vy.Index(iy))
-		s.curPath.pop()
-		return ret
+	edits := diff.Difference(vx.Len(), vy.Len(), func(ix, iy int) diff.Result {
+		return s.statelessCompare(withIndexes(ix, iy))
 	})
 
-	// Report the entire slice as is if the arrays are of primitive kind,
-	// and the arrays are different enough.
-	isPrimitive := false
-	switch t.Elem().Kind() {
-	case reflect.Int, reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64,
-		reflect.Uint, reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uintptr,
-		reflect.Bool, reflect.Float32, reflect.Float64, reflect.Complex64, reflect.Complex128:
-		isPrimitive = true
-	}
-	if isPrimitive && es.Dist() > (vx.Len()+vy.Len())/4 {
-		s.report(false)
-		return
-	}
-
 	// Replay the edit-script.
 	var ix, iy int
-	for _, e := range es {
+	for _, e := range edits {
 		switch e {
 		case diff.UniqueX:
-			step.xkey, step.ykey = ix, -1
-			vvx := vx.Index(ix)
-			s.pushStep(step, vvx, nothing)
-			s.report(false)
-			s.popStep()
+			s.compareAny(withIndexes(ix, -1))
 			ix++
 		case diff.UniqueY:
-			step.xkey, step.ykey = -1, iy
-			vvy := vy.Index(iy)
-			s.pushStep(step, nothing, vvy)
-			s.report(false)
-			s.popStep()
+			s.compareAny(withIndexes(-1, iy))
 			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)
-			} else {
-				s.compareAny(vvx, vvy)
-			}
-			s.popStep()
+			s.compareAny(withIndexes(ix, iy))
 			ix++
 			iy++
 		}
@@ -500,7 +468,7 @@ func (s *state) compareSlice(vx, vy reflect.Value, t reflect.Type) {
 	return
 }
 
-func (s *state) compareMap(vx, vy reflect.Value, t reflect.Type) {
+func (s *state) compareMap(t reflect.Type, vx, vy reflect.Value) {
 	if vx.IsNil() || vy.IsNil() {
 		s.report(vx.IsNil() && vy.IsNil())
 		return
@@ -508,20 +476,13 @@ func (s *state) compareMap(vx, vy reflect.Value, t reflect.Type) {
 
 	// 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()}}
+	step := &mapIndex{pathStep: pathStep{typ: t.Elem()}}
 	for _, k := range value.SortKeys(append(vx.MapKeys(), vy.MapKeys()...)) {
+		step.vx = vx.MapIndex(k)
+		step.vy = vy.MapIndex(k)
 		step.key = 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)
-		case !vvx.IsValid() && vvy.IsValid():
-			s.report(false)
-		default:
-			// It is possible for both vvx and vvy to be invalid if the
+		if !step.vx.IsValid() && !step.vy.IsValid() {
+			// It is possible for both vx and vy to be invalid if the
 			// key contained a NaN value in it.
 			//
 			// Even with the ability to retrieve NaN keys in Go 1.12,
@@ -538,21 +499,7 @@ 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()
-	}
-}
-
-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()
+		s.compareAny(step)
 	}
 }
 
diff --git a/cmp/compare_test.go b/cmp/compare_test.go
index 0a850f9..d7a8f9b 100644
--- a/cmp/compare_test.go
+++ b/cmp/compare_test.go
@@ -14,6 +14,7 @@ import (
 	"math/rand"
 	"reflect"
 	"regexp"
+	"runtime"
 	"sort"
 	"strings"
 	"sync"
@@ -125,6 +126,10 @@ func comparerTests() []test {
 
 	return []test{{
 		label: label,
+		x:     nil,
+		y:     nil,
+	}, {
+		label: label,
 		x:     1,
 		y:     1,
 	}, {
@@ -327,9 +332,57 @@ root:
 		x:     md5.Sum([]byte{'a'}),
 		y:     md5.Sum([]byte{'b'}),
 		wantDiff: `
-{[16]uint8}:
-	-: [16]uint8{0x0c, 0xc1, 0x75, 0xb9, 0xc0, 0xf1, 0xb6, 0xa8, 0x31, 0xc3, 0x99, 0xe2, 0x69, 0x77, 0x26, 0x61}
-	+: [16]uint8{0x92, 0xeb, 0x5f, 0xfe, 0xe6, 0xae, 0x2f, 0xec, 0x3a, 0xd7, 0x1c, 0x77, 0x75, 0x31, 0x57, 0x8f}`,
+{[16]uint8}[0]:
+	-: 0x0c
+	+: 0x92
+{[16]uint8}[1]:
+	-: 0xc1
+	+: 0xeb
+{[16]uint8}[2]:
+	-: 0x75
+	+: 0x5f
+{[16]uint8}[3]:
+	-: 0xb9
+	+: 0xfe
+{[16]uint8}[4]:
+	-: 0xc0
+	+: 0xe6
+{[16]uint8}[5]:
+	-: 0xf1
+	+: 0xae
+{[16]uint8}[6]:
+	-: 0xb6
+	+: 0x2f
+{[16]uint8}[7]:
+	-: 0xa8
+	+: 0xec
+{[16]uint8}[8]:
+	-: 0x31
+	+: 0x3a
+{[16]uint8}[9]:
+	-: 0xc3
+	+: 0xd7
+{[16]uint8}[10]:
+	-: 0x99
+	+: 0x1c
+{[16]uint8}[11->?]:
+	-: 0xe2
+	+: <non-existent>
+{[16]uint8}[12->?]:
+	-: 0x69
+	+: <non-existent>
+{[16]uint8}[?->12]:
+	-: <non-existent>
+	+: 0x75
+{[16]uint8}[?->13]:
+	-: <non-existent>
+	+: 0x31
+{[16]uint8}[14]:
+	-: 0x26
+	+: 0x57
+{[16]uint8}[15]:
+	-: 0x61
+	+: 0x8f`,
 	}, {
 		label: label,
 		x:     new(fmt.Stringer),
@@ -410,9 +463,36 @@ root:
 			}),
 		},
 		wantDiff: `
-{[]int}:
-	-: []int{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
-	+: []int{0, 0, 0, 0, 0, 0, 0, 0, 0, 0}`,
+λ({[]int}[0]):
+	-: float64(NaN)
+	+: float64(NaN)
+λ({[]int}[1]):
+	-: float64(NaN)
+	+: float64(NaN)
+λ({[]int}[2]):
+	-: float64(NaN)
+	+: float64(NaN)
+λ({[]int}[3]):
+	-: float64(NaN)
+	+: float64(NaN)
+λ({[]int}[4]):
+	-: float64(NaN)
+	+: float64(NaN)
+λ({[]int}[5]):
+	-: float64(NaN)
+	+: float64(NaN)
+λ({[]int}[6]):
+	-: float64(NaN)
+	+: float64(NaN)
+λ({[]int}[7]):
+	-: float64(NaN)
+	+: float64(NaN)
+λ({[]int}[8]):
+	-: float64(NaN)
+	+: float64(NaN)
+λ({[]int}[9]):
+	-: float64(NaN)
+	+: float64(NaN)`,
 	}, {
 		// Ensure reasonable Stringer formatting of map keys.
 		label: label,
@@ -729,6 +809,16 @@ func embeddedTests() []test {
 		return s
 	}
 
+	// TODO(dsnet): Workaround for reflect bug (https://golang.org/issue/21122).
+	// The upstream fix landed in Go1.10, so we can remove this when dropping
+	// support for Go1.9 and below.
+	wantPanicNotGo110 := func(s string) string {
+		if v := runtime.Version(); strings.HasPrefix(v, "go1.8") || strings.HasPrefix(v, "go1.9") {
+			return ""
+		}
+		return s
+	}
+
 	return []test{{
 		label:     label + "ParentStructA",
 		x:         ts.ParentStructA{},
@@ -1041,7 +1131,7 @@ func embeddedTests() []test {
 		label:     label + "ParentStructG",
 		x:         ts.ParentStructG{},
 		y:         ts.ParentStructG{},
-		wantPanic: "cannot handle unexported field",
+		wantPanic: wantPanicNotGo110("cannot handle unexported field"),
 	}, {
 		label: label + "ParentStructG",
 		x:     ts.ParentStructG{},
@@ -1127,7 +1217,7 @@ func embeddedTests() []test {
 		label:     label + "ParentStructI",
 		x:         ts.ParentStructI{},
 		y:         ts.ParentStructI{},
-		wantPanic: "cannot handle unexported field",
+		wantPanic: wantPanicNotGo110("cannot handle unexported field"),
 	}, {
 		label: label + "ParentStructI",
 		x:     ts.ParentStructI{},
diff --git a/cmp/options.go b/cmp/options.go
index a8307dc..964cf81 100644
--- a/cmp/options.go
+++ b/cmp/options.go
@@ -29,11 +29,11 @@ type Option interface {
 	// An Options is returned only if multiple comparers or transformers
 	// can apply simultaneously and will only contain values of those types
 	// or sub-Options containing values of those types.
-	filter(s *state, vx, vy reflect.Value, t reflect.Type) applicableOption
+	filter(s *state, t reflect.Type, vx, vy reflect.Value) applicableOption
 }
 
 // applicableOption represents the following types:
-//	Fundamental: ignore | invalid | *comparer | *transformer
+//	Fundamental: ignore | validator | *comparer | *transformer
 //	Grouping:    Options
 type applicableOption interface {
 	Option
@@ -43,7 +43,7 @@ type applicableOption interface {
 }
 
 // coreOption represents the following types:
-//	Fundamental: ignore | invalid | *comparer | *transformer
+//	Fundamental: ignore | validator | *comparer | *transformer
 //	Filters:     *pathFilter | *valuesFilter
 type coreOption interface {
 	Option
@@ -63,19 +63,19 @@ func (core) isCore() {}
 // on all individual options held within.
 type Options []Option
 
-func (opts Options) filter(s *state, vx, vy reflect.Value, t reflect.Type) (out applicableOption) {
+func (opts Options) filter(s *state, t reflect.Type, vx, vy reflect.Value) (out applicableOption) {
 	for _, opt := range opts {
-		switch opt := opt.filter(s, vx, vy, t); opt.(type) {
+		switch opt := opt.filter(s, t, vx, vy); opt.(type) {
 		case ignore:
 			return ignore{} // Only ignore can short-circuit evaluation
-		case invalid:
-			out = invalid{} // Takes precedence over comparer or transformer
+		case validator:
+			out = validator{} // Takes precedence over comparer or transformer
 		case *comparer, *transformer, Options:
 			switch out.(type) {
 			case nil:
 				out = opt
-			case invalid:
-				// Keep invalid
+			case validator:
+				// Keep validator
 			case *comparer, *transformer, Options:
 				out = Options{out, opt} // Conflicting comparers or transformers
 			}
@@ -124,9 +124,9 @@ type pathFilter struct {
 	opt Option
 }
 
-func (f pathFilter) filter(s *state, vx, vy reflect.Value, t reflect.Type) applicableOption {
+func (f pathFilter) filter(s *state, t reflect.Type, vx, vy reflect.Value) applicableOption {
 	if f.fnc(s.curPath) {
-		return f.opt.filter(s, vx, vy, t)
+		return f.opt.filter(s, t, vx, vy)
 	}
 	return nil
 }
@@ -137,8 +137,9 @@ func (f pathFilter) String() string {
 
 // FilterValues returns a new Option where opt is only evaluated if filter f,
 // which is a function of the form "func(T, T) bool", returns true for the
-// current pair of values being compared. If the type of the values is not
-// assignable to T, then this filter implicitly returns false.
+// current pair of values being compared. If either value is invalid or
+// the type of the values is not assignable to T, then this filter implicitly
+// returns false.
 //
 // The filter function must be
 // symmetric (i.e., agnostic to the order of the inputs) and
@@ -170,12 +171,12 @@ type valuesFilter struct {
 	opt Option
 }
 
-func (f valuesFilter) filter(s *state, vx, vy reflect.Value, t reflect.Type) applicableOption {
-	if !vx.IsValid() || !vy.IsValid() {
-		return invalid{}
+func (f valuesFilter) filter(s *state, t reflect.Type, vx, vy reflect.Value) applicableOption {
+	if !vx.IsValid() || !vx.CanInterface() || !vy.IsValid() || !vy.CanInterface() {
+		return validator{}
 	}
 	if (f.typ == nil || t.AssignableTo(f.typ)) && s.callTTBFunc(f.fnc, vx, vy) {
-		return f.opt.filter(s, vx, vy, t)
+		return f.opt.filter(s, t, vx, vy)
 	}
 	return nil
 }
@@ -192,18 +193,27 @@ func Ignore() Option { return ignore{} }
 type ignore struct{ core }
 
 func (ignore) isFiltered() bool                                                     { return false }
-func (ignore) filter(_ *state, _, _ reflect.Value, _ reflect.Type) applicableOption { return ignore{} }
+func (ignore) filter(_ *state, _ reflect.Type, _, _ reflect.Value) applicableOption { return ignore{} }
 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
-// be evaluated due to unexported fields.
-type invalid struct{ core }
+// validator is a sentinel Option type to indicate that some options could not
+// be evaluated due to unexported fields, missing slice elements, or
+// missing map entries. Both values are validator only for unexported fields.
+type validator struct{ core }
 
-func (invalid) filter(_ *state, _, _ reflect.Value, _ reflect.Type) applicableOption { return invalid{} }
-func (invalid) apply(s *state, _, _ reflect.Value) {
-	const help = "consider using AllowUnexported or cmpopts.IgnoreUnexported"
-	panic(fmt.Sprintf("cannot handle unexported field: %#v\n%s", s.curPath, help))
+func (validator) filter(_ *state, _ reflect.Type, _, _ reflect.Value) applicableOption {
+	return validator{}
+}
+func (validator) apply(s *state, vx, vy reflect.Value) {
+	// Unable to Interface implies unexported field without visibility access.
+	if (vx.IsValid() && !vx.CanInterface()) || (vy.IsValid() && !vy.CanInterface()) {
+		const help = "consider using AllowUnexported or cmpopts.IgnoreUnexported"
+		panic(fmt.Sprintf("cannot handle unexported field: %#v\n%s", s.curPath, help))
+	}
+
+	// Implies missing slice element or map entry.
+	s.report(vx.IsValid() == vy.IsValid())
 }
 
 // identRx represents a valid identifier according to the Go specification.
@@ -260,7 +270,7 @@ type transformer struct {
 
 func (tr *transformer) isFiltered() bool { return tr.typ != nil }
 
-func (tr *transformer) filter(s *state, _, _ reflect.Value, t reflect.Type) applicableOption {
+func (tr *transformer) filter(s *state, t reflect.Type, _, _ reflect.Value) applicableOption {
 	for i := len(s.curPath) - 1; i >= 0; i-- {
 		if t, ok := s.curPath[i].(*transform); !ok {
 			break // Hit most recent non-Transform step
@@ -275,17 +285,11 @@ 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.
-	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()
+	step := &transform{pathStep{typ: tr.fnc.Type().Out(0)}, tr}
+	vvx := s.callTRFunc(tr.fnc, vx, step)
+	vvy := s.callTRFunc(tr.fnc, vy, step)
+	step.vx, step.vy = vvx, vvy
+	s.compareAny(step)
 }
 
 func (tr transformer) String() string {
@@ -324,7 +328,7 @@ type comparer struct {
 
 func (cm *comparer) isFiltered() bool { return cm.typ != nil }
 
-func (cm *comparer) filter(_ *state, _, _ reflect.Value, t reflect.Type) applicableOption {
+func (cm *comparer) filter(_ *state, t reflect.Type, _, _ reflect.Value) applicableOption {
 	if cm.typ == nil || t.AssignableTo(cm.typ) {
 		return cm
 	}
@@ -383,7 +387,7 @@ func AllowUnexported(types ...interface{}) Option {
 
 type visibleStructs map[reflect.Type]bool
 
-func (visibleStructs) filter(_ *state, _, _ reflect.Value, _ reflect.Type) applicableOption {
+func (visibleStructs) filter(_ *state, _ reflect.Type, _, _ reflect.Value) applicableOption {
 	panic("not implemented")
 }
 
@@ -411,14 +415,15 @@ const (
 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.
+	// PushStep is called when a tree-traversal operation is performed.
+	// The PathStep itself is only valid until the step is popped.
+	// The PathStep.Values are valid for the duration of the entire traversal.
+	//
+	// Equal always call PushStep at the start to provide an operation-less
+	// PathStep used to report the root values.
 	//
-	// 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)
+	// The entries of a map are iterated through in an unspecified order.
+	PushStep(PathStep)
 
 	// Report is called at exactly once on leaf nodes to report whether the
 	// comparison identified the node as equal, unequal, or ignored.
@@ -435,12 +440,12 @@ func reporter(r interface {
 
 type reporterOption struct{ reporterIface }
 type reporterIface interface {
-	PushStep(PathStep, reflect.Value, reflect.Value)
+	PushStep(PathStep)
 	Report(reportFlags)
 	PopStep()
 }
 
-func (reporterOption) filter(_ *state, _, _ reflect.Value, _ reflect.Type) applicableOption {
+func (reporterOption) filter(_ *state, _ reflect.Type, _, _ reflect.Value) applicableOption {
 	panic("not implemented")
 }
 
diff --git a/cmp/path.go b/cmp/path.go
index 49b622b..ad6c0f5 100644
--- a/cmp/path.go
+++ b/cmp/path.go
@@ -29,23 +29,47 @@ type (
 	// these types as values of this type will be returned by this package.
 	PathStep interface {
 		String() string
-		Type() reflect.Type // Resulting type after performing the path step
-		isPathStep()
+
+		// Type is the resulting type after performing the path step.
+		Type() reflect.Type
+
+		// Values is the resulting values after performing the path step.
+		// The type of each valid value is guaranteed to be identical to Type.
+		//
+		// In some cases, one or both may be invalid or have restrictions:
+		//	• For StructField, both are not interface-able if the current field
+		//	is unexported and the struct type is not explicitly permitted by
+		//	AllowUnexported to traverse unexported fields.
+		//	• For SliceIndex, one may be invalid if an element is missing from
+		//	either the x or y slice.
+		//	• For MapIndex, one may be invalid if an entry is missing from
+		//	either the x or y map.
+		//
+		// The provided values must not be mutated.
+		Values() (vx, vy reflect.Value)
 	}
 
 	// StructField represents a struct field access on a field called Name.
 	StructField interface {
 		PathStep
+
+		// Name is the field name.
 		Name() string
+
+		// Index is the index of the field in the parent struct type.
+		// See reflect.Type.Field.
 		Index() int
+
 		isStructField()
 	}
 	// SliceIndex is an index operation on a slice or array at some index Key.
 	SliceIndex interface {
 		PathStep
-		Key() int // May return -1 if in a split state
 
-		// SplitKeys returns the indexes for indexing into slices in the
+		// Key is the index key; it may return -1 if in a split state
+		Key() int
+
+		// SplitKeys are the indexes for indexing into slices in the
 		// x and y values, respectively. These indexes may differ due to the
 		// insertion or removal of an element in one of the slices, causing
 		// all of the indexes to be shifted. If an index is -1, then that
@@ -54,30 +78,39 @@ type (
 		// Key is guaranteed to return -1 if and only if the indexes returned
 		// by SplitKeys are not the same. SplitKeys will never return -1 for
 		// both indexes.
-		SplitKeys() (x int, y int)
+		SplitKeys() (ix, iy int)
 
 		isSliceIndex()
 	}
 	// MapIndex is an index operation on a map at some index Key.
 	MapIndex interface {
 		PathStep
+
+		// Key is the value of the map key.
 		Key() reflect.Value
+
 		isMapIndex()
 	}
 	// Indirect represents pointer indirection on the parent type.
 	Indirect interface {
 		PathStep
+
 		isIndirect()
 	}
 	// TypeAssertion represents a type assertion on an interface.
 	TypeAssertion interface {
 		PathStep
+
 		isTypeAssertion()
 	}
 	// Transform is a transformation from the parent type to the current type.
 	Transform interface {
 		PathStep
+
+		// Name is the name of the Transformer.
 		Name() string
+
+		// Func is the function pointer to the transformer function.
 		Func() reflect.Value
 
 		// Option returns the originally constructed Transformer option.
@@ -185,7 +218,8 @@ func (pa Path) GoString() string {
 
 type (
 	pathStep struct {
-		typ reflect.Type
+		typ    reflect.Type
+		vx, vy reflect.Value
 	}
 
 	structField struct {
@@ -196,7 +230,7 @@ type (
 		// These fields are used for forcibly accessing an unexported field.
 		// pvx, pvy, and field are only valid if unexported is true.
 		unexported bool
-		force      bool                // Forcibly allow visibility
+		mayForce   bool                // Forcibly allow visibility
 		pvx, pvy   reflect.Value       // Parent values
 		field      reflect.StructField // Field information
 	}
@@ -220,7 +254,8 @@ type (
 	}
 )
 
-func (ps pathStep) Type() reflect.Type { return ps.typ }
+func (ps pathStep) Type() reflect.Type             { return ps.typ }
+func (ps pathStep) Values() (vx, vy reflect.Value) { return ps.vx, ps.vy }
 func (ps pathStep) String() string {
 	if ps.typ == nil {
 		return "<nil>"
@@ -233,6 +268,19 @@ func (ps pathStep) String() string {
 }
 func (ps pathStep) isPathStep() {}
 
+func (sf structField) Values() (vx, vy reflect.Value) {
+	if !sf.unexported {
+		return sf.vx, sf.vy // CanInterface reports true
+	}
+
+	// Forcibly obtain read-write access to an unexported struct field.
+	if sf.mayForce {
+		vx = retrieveUnexportedField(sf.pvx, sf.field)
+		vy = retrieveUnexportedField(sf.pvy, sf.field)
+		return vx, vy // CanInterface reports true
+	}
+	return sf.vx, sf.vy // CanInterface reports false
+}
 func (sf structField) String() string { return fmt.Sprintf(".%s", sf.name) }
 func (sf structField) Name() string   { return sf.name }
 func (sf structField) Index() int     { return sf.idx }
@@ -259,8 +307,8 @@ func (si sliceIndex) Key() int {
 	}
 	return si.xkey
 }
-func (si sliceIndex) SplitKeys() (x, y int) { return si.xkey, si.ykey }
-func (si sliceIndex) isSliceIndex()         {}
+func (si sliceIndex) SplitKeys() (ix, iy int) { return si.xkey, si.ykey }
+func (si sliceIndex) isSliceIndex()           {}
 
 func (mi mapIndex) String() string     { return fmt.Sprintf("[%#v]", mi.key) }
 func (mi mapIndex) Key() reflect.Value { return mi.key }
diff --git a/cmp/report.go b/cmp/report.go
index 327f332..d3e4b28 100644
--- a/cmp/report.go
+++ b/cmp/report.go
@@ -16,7 +16,6 @@ type defaultReporter struct {
 	Option
 
 	curPath Path
-	curVals [][2]reflect.Value
 
 	diffs  []string // List of differences, possibly truncated
 	ndiffs int      // Total number of differences
@@ -24,19 +23,17 @@ type defaultReporter struct {
 	nlines int      // Number of lines in diffs
 }
 
-func (r *defaultReporter) PushStep(ps PathStep, x, y reflect.Value) {
+func (r *defaultReporter) PushStep(ps PathStep) {
 	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)
+		vx, vy := r.curPath.Last().Values()
+		r.report(vx, vy, 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) {
diff --git a/go.mod b/go.mod
index 6c0e40e..aa2daba 100644
--- a/go.mod
+++ b/go.mod
@@ -1,3 +1 @@
 module github.com/google/go-cmp
-
-go 1.8