vendor/github.com/google/go-cmp/cmp/path.go - bbsim - Gitiles

 // Copyright 2017, 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 file.

 package cmp

 import (
 	"fmt"
 	"reflect"
 	"strings"
 	"unicode"
 	"unicode/utf8"

 	"github.com/google/go-cmp/cmp/internal/value"
 )

 // Path is a list of PathSteps describing the sequence of operations to get
 // from some root type to the current position in the value tree.
 // The first Path element is always an operation-less PathStep that exists
 // simply to identify the initial type.
 //
 // When traversing structs with embedded structs, the embedded struct will
 // always be accessed as a field before traversing the fields of the
 // embedded struct themselves. That is, an exported field from the
 // embedded struct will never be accessed directly from the parent struct.
 type Path []PathStep

 // PathStep is a union-type for specific operations to traverse
 // a value's tree structure. Users of this package never need to implement
 // these types as values of this type will be returned by this package.
 //
 // Implementations of this interface are
 // StructField, SliceIndex, MapIndex, Indirect, TypeAssertion, and Transform.
 type PathStep interface {
 	String() string

 	// 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
 	//	an Exporter 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)
 }

 var (
 	_ PathStep = StructField{}
 	_ PathStep = SliceIndex{}
 	_ PathStep = MapIndex{}
 	_ PathStep = Indirect{}
 	_ PathStep = TypeAssertion{}
 	_ PathStep = Transform{}
 )

 func (pa *Path) push(s PathStep) {
 	*pa = append(*pa, s)
 }

 func (pa *Path) pop() {
 	*pa = (*pa)[:len(*pa)-1]
 }

 // Last returns the last PathStep in the Path.
 // If the path is empty, this returns a non-nil PathStep that reports a nil Type.
 func (pa Path) Last() PathStep {
 	return pa.Index(-1)
 }

 // Index returns the ith step in the Path and supports negative indexing.
 // A negative index starts counting from the tail of the Path such that -1
 // refers to the last step, -2 refers to the second-to-last step, and so on.
 // If index is invalid, this returns a non-nil PathStep that reports a nil Type.
 func (pa Path) Index(i int) PathStep {
 	if i < 0 {
 		i = len(pa) + i
 	}
 	if i < 0 || i >= len(pa) {
 		return pathStep{}
 	}
 	return pa[i]
 }

 // String returns the simplified path to a node.
 // The simplified path only contains struct field accesses.
 //
 // For example:
 //	MyMap.MySlices.MyField
 func (pa Path) String() string {
 	var ss []string
 	for _, s := range pa {
 		if _, ok := s.(StructField); ok {
 			ss = append(ss, s.String())
 		}
 	}
 	return strings.TrimPrefix(strings.Join(ss, ""), ".")
 }

 // GoString returns the path to a specific node using Go syntax.
 //
 // For example:
 //	(*root.MyMap["key"].(*mypkg.MyStruct).MySlices)[2][3].MyField
 func (pa Path) GoString() string {
 	var ssPre, ssPost []string
 	var numIndirect int
 	for i, s := range pa {
 		var nextStep PathStep
 		if i+1 < len(pa) {
 			nextStep = pa[i+1]
 		}
 		switch s := s.(type) {
 		case Indirect:
 			numIndirect++
 			pPre, pPost := "(", ")"
 			switch nextStep.(type) {
 			case Indirect:
 				continue // Next step is indirection, so let them batch up
 			case StructField:
 				numIndirect-- // Automatic indirection on struct fields
 			case nil:
 				pPre, pPost = "", "" // Last step; no need for parenthesis
 			}
 			if numIndirect > 0 {
 				ssPre = append(ssPre, pPre+strings.Repeat("*", numIndirect))
 				ssPost = append(ssPost, pPost)
 			}
 			numIndirect = 0
 			continue
 		case Transform:
 			ssPre = append(ssPre, s.trans.name+"(")
 			ssPost = append(ssPost, ")")
 			continue
 		}
 		ssPost = append(ssPost, s.String())
 	}
 	for i, j := 0, len(ssPre)-1; i < j; i, j = i+1, j-1 {
 		ssPre[i], ssPre[j] = ssPre[j], ssPre[i]
 	}
 	return strings.Join(ssPre, "") + strings.Join(ssPost, "")
 }

 type pathStep struct {
 	typ    reflect.Type
 	vx, vy reflect.Value
 }

 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>"
 	}
 	s := ps.typ.String()
 	if s == "" || strings.ContainsAny(s, "{}\n") {
 		return "root" // Type too simple or complex to print
 	}
 	return fmt.Sprintf("{%s}", s)
 }

 // StructField represents a struct field access on a field called Name.
 type StructField struct{ *structField }
 type structField struct {
 	pathStep
 	name string
 	idx  int

 	// These fields are used for forcibly accessing an unexported field.
 	// pvx, pvy, and field are only valid if unexported is true.
 	unexported bool
 	mayForce   bool                // Forcibly allow visibility
 	paddr      bool                // Was parent addressable?
 	pvx, pvy   reflect.Value       // Parent values (always addressible)
 	field      reflect.StructField // Field information
 }

 func (sf StructField) Type() reflect.Type { return sf.typ }
 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, sf.paddr)
 		vy = retrieveUnexportedField(sf.pvy, sf.field, sf.paddr)
 		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) }

 // Name is the field name.
 func (sf StructField) Name() string { return sf.name }

 // Index is the index of the field in the parent struct type.
 // See reflect.Type.Field.
 func (sf StructField) Index() int { return sf.idx }

 // SliceIndex is an index operation on a slice or array at some index Key.
 type SliceIndex struct{ *sliceIndex }
 type sliceIndex struct {
 	pathStep
 	xkey, ykey int
 	isSlice    bool // False for reflect.Array
 }

 func (si SliceIndex) Type() reflect.Type             { return si.typ }
 func (si SliceIndex) Values() (vx, vy reflect.Value) { return si.vx, si.vy }
 func (si SliceIndex) String() string {
 	switch {
 	case si.xkey == si.ykey:
 		return fmt.Sprintf("[%d]", si.xkey)
 	case si.ykey == -1:
 		// [5->?] means "I don't know where X[5] went"
 		return fmt.Sprintf("[%d->?]", si.xkey)
 	case si.xkey == -1:
 		// [?->3] means "I don't know where Y[3] came from"
 		return fmt.Sprintf("[?->%d]", si.ykey)
 	default:
 		// [5->3] means "X[5] moved to Y[3]"
 		return fmt.Sprintf("[%d->%d]", si.xkey, si.ykey)
 	}
 }

 // Key is the index key; it may return -1 if in a split state
 func (si SliceIndex) Key() int {
 	if si.xkey != si.ykey {
 		return -1
 	}
 	return si.xkey
 }

 // 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
 // indicates that the element does not exist in the associated slice.
 //
 // 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.
 func (si SliceIndex) SplitKeys() (ix, iy int) { return si.xkey, si.ykey }

 // MapIndex is an index operation on a map at some index Key.
 type MapIndex struct{ *mapIndex }
 type mapIndex struct {
 	pathStep
 	key reflect.Value
 }

 func (mi MapIndex) Type() reflect.Type             { return mi.typ }
 func (mi MapIndex) Values() (vx, vy reflect.Value) { return mi.vx, mi.vy }
 func (mi MapIndex) String() string                 { return fmt.Sprintf("[%#v]", mi.key) }

 // Key is the value of the map key.
 func (mi MapIndex) Key() reflect.Value { return mi.key }

 // Indirect represents pointer indirection on the parent type.
 type Indirect struct{ *indirect }
 type indirect struct {
 	pathStep
 }

 func (in Indirect) Type() reflect.Type             { return in.typ }
 func (in Indirect) Values() (vx, vy reflect.Value) { return in.vx, in.vy }
 func (in Indirect) String() string                 { return "*" }

 // TypeAssertion represents a type assertion on an interface.
 type TypeAssertion struct{ *typeAssertion }
 type typeAssertion struct {
 	pathStep
 }

 func (ta TypeAssertion) Type() reflect.Type             { return ta.typ }
 func (ta TypeAssertion) Values() (vx, vy reflect.Value) { return ta.vx, ta.vy }
 func (ta TypeAssertion) String() string                 { return fmt.Sprintf(".(%v)", ta.typ) }

 // Transform is a transformation from the parent type to the current type.
 type Transform struct{ *transform }
 type transform struct {
 	pathStep
 	trans *transformer
 }

 func (tf Transform) Type() reflect.Type             { return tf.typ }
 func (tf Transform) Values() (vx, vy reflect.Value) { return tf.vx, tf.vy }
 func (tf Transform) String() string                 { return fmt.Sprintf("%s()", tf.trans.name) }

 // Name is the name of the Transformer.
 func (tf Transform) Name() string { return tf.trans.name }

 // Func is the function pointer to the transformer function.
 func (tf Transform) Func() reflect.Value { return tf.trans.fnc }

 // Option returns the originally constructed Transformer option.
 // The == operator can be used to detect the exact option used.
 func (tf Transform) Option() Option { return tf.trans }

 // pointerPath represents a dual-stack of pointers encountered when
 // recursively traversing the x and y values. This data structure supports
 // detection of cycles and determining whether the cycles are equal.
 // In Go, cycles can occur via pointers, slices, and maps.
 //
 // The pointerPath uses a map to represent a stack; where descension into a
 // pointer pushes the address onto the stack, and ascension from a pointer
 // pops the address from the stack. Thus, when traversing into a pointer from
 // reflect.Ptr, reflect.Slice element, or reflect.Map, we can detect cycles
 // by checking whether the pointer has already been visited. The cycle detection
 // uses a seperate stack for the x and y values.
 //
 // If a cycle is detected we need to determine whether the two pointers
 // should be considered equal. The definition of equality chosen by Equal
 // requires two graphs to have the same structure. To determine this, both the
 // x and y values must have a cycle where the previous pointers were also
 // encountered together as a pair.
 //
 // Semantically, this is equivalent to augmenting Indirect, SliceIndex, and
 // MapIndex with pointer information for the x and y values.
 // Suppose px and py are two pointers to compare, we then search the
 // Path for whether px was ever encountered in the Path history of x, and
 // similarly so with py. If either side has a cycle, the comparison is only
 // equal if both px and py have a cycle resulting from the same PathStep.
 //
 // Using a map as a stack is more performant as we can perform cycle detection
 // in O(1) instead of O(N) where N is len(Path).
 type pointerPath struct {
 	// mx is keyed by x pointers, where the value is the associated y pointer.
 	mx map[value.Pointer]value.Pointer
 	// my is keyed by y pointers, where the value is the associated x pointer.
 	my map[value.Pointer]value.Pointer
 }

 func (p *pointerPath) Init() {
 	p.mx = make(map[value.Pointer]value.Pointer)
 	p.my = make(map[value.Pointer]value.Pointer)
 }

 // Push indicates intent to descend into pointers vx and vy where
 // visited reports whether either has been seen before. If visited before,
 // equal reports whether both pointers were encountered together.
 // Pop must be called if and only if the pointers were never visited.
 //
 // The pointers vx and vy must be a reflect.Ptr, reflect.Slice, or reflect.Map
 // and be non-nil.
 func (p pointerPath) Push(vx, vy reflect.Value) (equal, visited bool) {
 	px := value.PointerOf(vx)
 	py := value.PointerOf(vy)
 	_, ok1 := p.mx[px]
 	_, ok2 := p.my[py]
 	if ok1 || ok2 {
 		equal = p.mx[px] == py && p.my[py] == px // Pointers paired together
 		return equal, true
 	}
 	p.mx[px] = py
 	p.my[py] = px
 	return false, false
 }

 // Pop ascends from pointers vx and vy.
 func (p pointerPath) Pop(vx, vy reflect.Value) {
 	delete(p.mx, value.PointerOf(vx))
 	delete(p.my, value.PointerOf(vy))
 }

 // isExported reports whether the identifier is exported.
 func isExported(id string) bool {
 	r, _ := utf8.DecodeRuneInString(id)
 	return unicode.IsUpper(r)
 }
	// Copyright 2017, 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 file.

	package cmp

	import (
	"fmt"
	"reflect"
	"strings"
	"unicode"
	"unicode/utf8"

	"github.com/google/go-cmp/cmp/internal/value"
	)

	// Path is a list of PathSteps describing the sequence of operations to get
	// from some root type to the current position in the value tree.
	// The first Path element is always an operation-less PathStep that exists
	// simply to identify the initial type.
	//
	// When traversing structs with embedded structs, the embedded struct will
	// always be accessed as a field before traversing the fields of the
	// embedded struct themselves. That is, an exported field from the
	// embedded struct will never be accessed directly from the parent struct.
	type Path []PathStep

	// PathStep is a union-type for specific operations to traverse
	// a value's tree structure. Users of this package never need to implement
	// these types as values of this type will be returned by this package.
	//
	// Implementations of this interface are
	// StructField, SliceIndex, MapIndex, Indirect, TypeAssertion, and Transform.
	type PathStep interface {
	String() string

	// 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
	// an Exporter 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)
	}

	var (
	_ PathStep = StructField{}
	_ PathStep = SliceIndex{}
	_ PathStep = MapIndex{}
	_ PathStep = Indirect{}
	_ PathStep = TypeAssertion{}
	_ PathStep = Transform{}
	)

	func (pa *Path) push(s PathStep) {
	pa = append(pa, s)
	}

	func (pa *Path) pop() {
	pa = (pa)[:len(*pa)-1]
	}

	// Last returns the last PathStep in the Path.
	// If the path is empty, this returns a non-nil PathStep that reports a nil Type.
	func (pa Path) Last() PathStep {
	return pa.Index(-1)
	}

	// Index returns the ith step in the Path and supports negative indexing.
	// A negative index starts counting from the tail of the Path such that -1
	// refers to the last step, -2 refers to the second-to-last step, and so on.
	// If index is invalid, this returns a non-nil PathStep that reports a nil Type.
	func (pa Path) Index(i int) PathStep {
	if i < 0 {
	i = len(pa) + i
	}
	if i < 0 \|\| i >= len(pa) {
	return pathStep{}
	}
	return pa[i]
	}

	// String returns the simplified path to a node.
	// The simplified path only contains struct field accesses.
	//
	// For example:
	// MyMap.MySlices.MyField
	func (pa Path) String() string {
	var ss []string
	for _, s := range pa {
	if _, ok := s.(StructField); ok {
	ss = append(ss, s.String())
	}
	}
	return strings.TrimPrefix(strings.Join(ss, ""), ".")
	}

	// GoString returns the path to a specific node using Go syntax.
	//
	// For example:
	// (root.MyMap["key"].(mypkg.MyStruct).MySlices)[2][3].MyField
	func (pa Path) GoString() string {
	var ssPre, ssPost []string
	var numIndirect int
	for i, s := range pa {
	var nextStep PathStep
	if i+1 < len(pa) {
	nextStep = pa[i+1]
	}
	switch s := s.(type) {
	case Indirect:
	numIndirect++
	pPre, pPost := "(", ")"
	switch nextStep.(type) {
	case Indirect:
	continue // Next step is indirection, so let them batch up
	case StructField:
	numIndirect-- // Automatic indirection on struct fields
	case nil:
	pPre, pPost = "", "" // Last step; no need for parenthesis
	}
	if numIndirect > 0 {
	ssPre = append(ssPre, pPre+strings.Repeat("*", numIndirect))
	ssPost = append(ssPost, pPost)
	}
	numIndirect = 0
	continue
	case Transform:
	ssPre = append(ssPre, s.trans.name+"(")
	ssPost = append(ssPost, ")")
	continue
	}
	ssPost = append(ssPost, s.String())
	}
	for i, j := 0, len(ssPre)-1; i < j; i, j = i+1, j-1 {
	ssPre[i], ssPre[j] = ssPre[j], ssPre[i]
	}
	return strings.Join(ssPre, "") + strings.Join(ssPost, "")
	}

	type pathStep struct {
	typ reflect.Type
	vx, vy reflect.Value
	}

	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>"
	}
	s := ps.typ.String()
	if s == "" \|\| strings.ContainsAny(s, "{}\n") {
	return "root" // Type too simple or complex to print
	}
	return fmt.Sprintf("{%s}", s)
	}

	// StructField represents a struct field access on a field called Name.
	type StructField struct{ *structField }
	type structField struct {
	pathStep
	name string
	idx int

	// These fields are used for forcibly accessing an unexported field.
	// pvx, pvy, and field are only valid if unexported is true.
	unexported bool
	mayForce bool // Forcibly allow visibility
	paddr bool // Was parent addressable?
	pvx, pvy reflect.Value // Parent values (always addressible)
	field reflect.StructField // Field information
	}

	func (sf StructField) Type() reflect.Type { return sf.typ }
	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, sf.paddr)
	vy = retrieveUnexportedField(sf.pvy, sf.field, sf.paddr)
	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) }

	// Name is the field name.
	func (sf StructField) Name() string { return sf.name }

	// Index is the index of the field in the parent struct type.
	// See reflect.Type.Field.
	func (sf StructField) Index() int { return sf.idx }

	// SliceIndex is an index operation on a slice or array at some index Key.
	type SliceIndex struct{ *sliceIndex }
	type sliceIndex struct {
	pathStep
	xkey, ykey int
	isSlice bool // False for reflect.Array
	}

	func (si SliceIndex) Type() reflect.Type { return si.typ }
	func (si SliceIndex) Values() (vx, vy reflect.Value) { return si.vx, si.vy }
	func (si SliceIndex) String() string {
	switch {
	case si.xkey == si.ykey:
	return fmt.Sprintf("[%d]", si.xkey)
	case si.ykey == -1:
	// [5->?] means "I don't know where X[5] went"
	return fmt.Sprintf("[%d->?]", si.xkey)
	case si.xkey == -1:
	// [?->3] means "I don't know where Y[3] came from"
	return fmt.Sprintf("[?->%d]", si.ykey)
	default:
	// [5->3] means "X[5] moved to Y[3]"
	return fmt.Sprintf("[%d->%d]", si.xkey, si.ykey)
	}
	}

	// Key is the index key; it may return -1 if in a split state
	func (si SliceIndex) Key() int {
	if si.xkey != si.ykey {
	return -1
	}
	return si.xkey
	}

	// 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
	// indicates that the element does not exist in the associated slice.
	//
	// 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.
	func (si SliceIndex) SplitKeys() (ix, iy int) { return si.xkey, si.ykey }

	// MapIndex is an index operation on a map at some index Key.
	type MapIndex struct{ *mapIndex }
	type mapIndex struct {
	pathStep
	key reflect.Value
	}

	func (mi MapIndex) Type() reflect.Type { return mi.typ }
	func (mi MapIndex) Values() (vx, vy reflect.Value) { return mi.vx, mi.vy }
	func (mi MapIndex) String() string { return fmt.Sprintf("[%#v]", mi.key) }

	// Key is the value of the map key.
	func (mi MapIndex) Key() reflect.Value { return mi.key }

	// Indirect represents pointer indirection on the parent type.
	type Indirect struct{ *indirect }
	type indirect struct {
	pathStep
	}

	func (in Indirect) Type() reflect.Type { return in.typ }
	func (in Indirect) Values() (vx, vy reflect.Value) { return in.vx, in.vy }
	func (in Indirect) String() string { return "*" }

	// TypeAssertion represents a type assertion on an interface.
	type TypeAssertion struct{ *typeAssertion }
	type typeAssertion struct {
	pathStep
	}

	func (ta TypeAssertion) Type() reflect.Type { return ta.typ }
	func (ta TypeAssertion) Values() (vx, vy reflect.Value) { return ta.vx, ta.vy }
	func (ta TypeAssertion) String() string { return fmt.Sprintf(".(%v)", ta.typ) }

	// Transform is a transformation from the parent type to the current type.
	type Transform struct{ *transform }
	type transform struct {
	pathStep
	trans *transformer
	}

	func (tf Transform) Type() reflect.Type { return tf.typ }
	func (tf Transform) Values() (vx, vy reflect.Value) { return tf.vx, tf.vy }
	func (tf Transform) String() string { return fmt.Sprintf("%s()", tf.trans.name) }

	// Name is the name of the Transformer.
	func (tf Transform) Name() string { return tf.trans.name }

	// Func is the function pointer to the transformer function.
	func (tf Transform) Func() reflect.Value { return tf.trans.fnc }

	// Option returns the originally constructed Transformer option.
	// The == operator can be used to detect the exact option used.
	func (tf Transform) Option() Option { return tf.trans }

	// pointerPath represents a dual-stack of pointers encountered when
	// recursively traversing the x and y values. This data structure supports
	// detection of cycles and determining whether the cycles are equal.
	// In Go, cycles can occur via pointers, slices, and maps.
	//
	// The pointerPath uses a map to represent a stack; where descension into a
	// pointer pushes the address onto the stack, and ascension from a pointer
	// pops the address from the stack. Thus, when traversing into a pointer from
	// reflect.Ptr, reflect.Slice element, or reflect.Map, we can detect cycles
	// by checking whether the pointer has already been visited. The cycle detection
	// uses a seperate stack for the x and y values.
	//
	// If a cycle is detected we need to determine whether the two pointers
	// should be considered equal. The definition of equality chosen by Equal
	// requires two graphs to have the same structure. To determine this, both the
	// x and y values must have a cycle where the previous pointers were also
	// encountered together as a pair.
	//
	// Semantically, this is equivalent to augmenting Indirect, SliceIndex, and
	// MapIndex with pointer information for the x and y values.
	// Suppose px and py are two pointers to compare, we then search the
	// Path for whether px was ever encountered in the Path history of x, and
	// similarly so with py. If either side has a cycle, the comparison is only
	// equal if both px and py have a cycle resulting from the same PathStep.
	//
	// Using a map as a stack is more performant as we can perform cycle detection
	// in O(1) instead of O(N) where N is len(Path).
	type pointerPath struct {
	// mx is keyed by x pointers, where the value is the associated y pointer.
	mx map[value.Pointer]value.Pointer
	// my is keyed by y pointers, where the value is the associated x pointer.
	my map[value.Pointer]value.Pointer
	}

	func (p *pointerPath) Init() {
	p.mx = make(map[value.Pointer]value.Pointer)
	p.my = make(map[value.Pointer]value.Pointer)
	}

	// Push indicates intent to descend into pointers vx and vy where
	// visited reports whether either has been seen before. If visited before,
	// equal reports whether both pointers were encountered together.
	// Pop must be called if and only if the pointers were never visited.
	//
	// The pointers vx and vy must be a reflect.Ptr, reflect.Slice, or reflect.Map
	// and be non-nil.
	func (p pointerPath) Push(vx, vy reflect.Value) (equal, visited bool) {
	px := value.PointerOf(vx)
	py := value.PointerOf(vy)
	_, ok1 := p.mx[px]
	_, ok2 := p.my[py]
	if ok1 \|\| ok2 {
	equal = p.mx[px] == py && p.my[py] == px // Pointers paired together
	return equal, true
	}
	p.mx[px] = py
	p.my[py] = px
	return false, false
	}

	// Pop ascends from pointers vx and vy.
	func (p pointerPath) Pop(vx, vy reflect.Value) {
	delete(p.mx, value.PointerOf(vx))
	delete(p.my, value.PointerOf(vy))
	}

	// isExported reports whether the identifier is exported.
	func isExported(id string) bool {
	r, _ := utf8.DecodeRuneInString(id)
	return unicode.IsUpper(r)
	}