// 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.md file.
package cmp
import (
"fmt"
"reflect"
"strings"
"unicode"
"unicode/utf8"
)
type (
// 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.
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.
PathStep interface {
String() string
Type() reflect.Type // Resulting type after performing the path step
isPathStep()
}
// 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
// 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.
SplitKeys() (x int, y int)
isSliceIndex()
}
// MapIndex is an index operation on a map at some index Key.
MapIndex interface {
PathStep
Key() reflect.Value
isMapIndex()
}
// TypeAssertion represents a type assertion on an interface.
TypeAssertion interface {
PathStep
isTypeAssertion()
}
// StructField represents a struct field access on a field called Name.
StructField interface {
PathStep
Name() string
Index() int
isStructField()
}
// Indirect represents pointer indirection on the parent type.
Indirect interface {
PathStep
isIndirect()
}
// Transform is a transformation from the parent type to the current type.
Transform interface {
PathStep
Name() string
Func() reflect.Value
// Option returns the originally constructed Transformer option.
// The == operator can be used to detect the exact option used.
Option() Option
isTransform()
}
)
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
case *typeAssertion:
// As a special-case, elide type assertions on anonymous types
// since they are typically generated dynamically and can be very
// verbose. For example, some transforms return interface{} because
// of Go's lack of generics, but typically take in and return the
// exact same concrete type.
if s.Type().PkgPath() == "" {
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
}
sliceIndex struct {
pathStep
xkey, ykey int
}
mapIndex struct {
pathStep
key reflect.Value
}
typeAssertion struct {
pathStep
}
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
force bool // Forcibly allow visibility
pvx, pvy reflect.Value // Parent values
field reflect.StructField // Field information
}
indirect struct {
pathStep
}
transform struct {
pathStep
trans *transformer
}
)
func (ps pathStep) Type() reflect.Type { return ps.typ }
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)
}
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)
}
}
func (mi mapIndex) String() string { return fmt.Sprintf("[%#v]", mi.key) }
func (ta typeAssertion) String() string { return fmt.Sprintf(".(%v)", ta.typ) }
func (sf structField) String() string { return fmt.Sprintf(".%s", sf.name) }
func (in indirect) String() string { return "*" }
func (tf transform) String() string { return fmt.Sprintf("%s()", tf.trans.name) }
func (si sliceIndex) Key() int {
if si.xkey != si.ykey {
return -1
}
return si.xkey
}
func (si sliceIndex) SplitKeys() (x, y int) { return si.xkey, si.ykey }
func (mi mapIndex) Key() reflect.Value { return mi.key }
func (sf structField) Name() string { return sf.name }
func (sf structField) Index() int { return sf.idx }
func (tf transform) Name() string { return tf.trans.name }
func (tf transform) Func() reflect.Value { return tf.trans.fnc }
func (tf transform) Option() Option { return tf.trans }
func (pathStep) isPathStep() {}
func (sliceIndex) isSliceIndex() {}
func (mapIndex) isMapIndex() {}
func (typeAssertion) isTypeAssertion() {}
func (structField) isStructField() {}
func (indirect) isIndirect() {}
func (transform) isTransform() {}
var (
_ SliceIndex = sliceIndex{}
_ MapIndex = mapIndex{}
_ TypeAssertion = typeAssertion{}
_ StructField = structField{}
_ Indirect = indirect{}
_ Transform = transform{}
_ PathStep = sliceIndex{}
_ PathStep = mapIndex{}
_ PathStep = typeAssertion{}
_ PathStep = structField{}
_ PathStep = indirect{}
_ PathStep = transform{}
)
// isExported reports whether the identifier is exported.
func isExported(id string) bool {
r, _ := utf8.DecodeRuneInString(id)
return unicode.IsUpper(r)
}
// isValid reports whether the identifier is valid.
// Empty and underscore-only strings are not valid.
func isValid(id string) bool {
ok := id != "" && id != "_"
for j, c := range id {
ok = ok && (j > 0 || !unicode.IsDigit(c))
ok = ok && (c == '_' || unicode.IsLetter(c) || unicode.IsDigit(c))
}
return ok
}
