1// Copyright 2017, The Go Authors. All rights reserved.
2// Use of this source code is governed by a BSD-style
3// license that can be found in the LICENSE.md file.
4
5package cmp
6
7import (
8 "fmt"
9 "reflect"
10 "strings"
11 "unicode"
12 "unicode/utf8"
13)
14
15type (
16 // Path is a list of PathSteps describing the sequence of operations to get
17 // from some root type to the current position in the value tree.
18 // The first Path element is always an operation-less PathStep that exists
19 // simply to identify the initial type.
20 //
21 // When traversing structs with embedded structs, the embedded struct will
22 // always be accessed as a field before traversing the fields of the
23 // embedded struct themselves. That is, an exported field from the
24 // embedded struct will never be accessed directly from the parent struct.
25 Path []PathStep
26
27 // PathStep is a union-type for specific operations to traverse
28 // a value's tree structure. Users of this package never need to implement
29 // these types as values of this type will be returned by this package.
30 PathStep interface {
31 String() string
32 Type() reflect.Type // Resulting type after performing the path step
33 isPathStep()
34 }
35
36 // SliceIndex is an index operation on a slice or array at some index Key.
37 SliceIndex interface {
38 PathStep
39 Key() int // May return -1 if in a split state
40
41 // SplitKeys returns the indexes for indexing into slices in the
42 // x and y values, respectively. These indexes may differ due to the
43 // insertion or removal of an element in one of the slices, causing
44 // all of the indexes to be shifted. If an index is -1, then that
45 // indicates that the element does not exist in the associated slice.
46 //
47 // Key is guaranteed to return -1 if and only if the indexes returned
48 // by SplitKeys are not the same. SplitKeys will never return -1 for
49 // both indexes.
50 SplitKeys() (x int, y int)
51
52 isSliceIndex()
53 }
54 // MapIndex is an index operation on a map at some index Key.
55 MapIndex interface {
56 PathStep
57 Key() reflect.Value
58 isMapIndex()
59 }
60 // TypeAssertion represents a type assertion on an interface.
61 TypeAssertion interface {
62 PathStep
63 isTypeAssertion()
64 }
65 // StructField represents a struct field access on a field called Name.
66 StructField interface {
67 PathStep
68 Name() string
69 Index() int
70 isStructField()
71 }
72 // Indirect represents pointer indirection on the parent type.
73 Indirect interface {
74 PathStep
75 isIndirect()
76 }
77 // Transform is a transformation from the parent type to the current type.
78 Transform interface {
79 PathStep
80 Name() string
81 Func() reflect.Value
82
83 // Option returns the originally constructed Transformer option.
84 // The == operator can be used to detect the exact option used.
85 Option() Option
86
87 isTransform()
88 }
89)
90
91func (pa *Path) push(s PathStep) {
92 *pa = append(*pa, s)
93}
94
95func (pa *Path) pop() {
96 *pa = (*pa)[:len(*pa)-1]
97}
98
99// Last returns the last PathStep in the Path.
100// If the path is empty, this returns a non-nil PathStep that reports a nil Type.
101func (pa Path) Last() PathStep {
102 return pa.Index(-1)
103}
104
105// Index returns the ith step in the Path and supports negative indexing.
106// A negative index starts counting from the tail of the Path such that -1
107// refers to the last step, -2 refers to the second-to-last step, and so on.
108// If index is invalid, this returns a non-nil PathStep that reports a nil Type.
109func (pa Path) Index(i int) PathStep {
110 if i < 0 {
111 i = len(pa) + i
112 }
113 if i < 0 || i >= len(pa) {
114 return pathStep{}
115 }
116 return pa[i]
117}
118
119// String returns the simplified path to a node.
120// The simplified path only contains struct field accesses.
121//
122// For example:
123// MyMap.MySlices.MyField
124func (pa Path) String() string {
125 var ss []string
126 for _, s := range pa {
127 if _, ok := s.(*structField); ok {
128 ss = append(ss, s.String())
129 }
130 }
131 return strings.TrimPrefix(strings.Join(ss, ""), ".")
132}
133
134// GoString returns the path to a specific node using Go syntax.
135//
136// For example:
137// (*root.MyMap["key"].(*mypkg.MyStruct).MySlices)[2][3].MyField
138func (pa Path) GoString() string {
139 var ssPre, ssPost []string
140 var numIndirect int
141 for i, s := range pa {
142 var nextStep PathStep
143 if i+1 < len(pa) {
144 nextStep = pa[i+1]
145 }
146 switch s := s.(type) {
147 case *indirect:
148 numIndirect++
149 pPre, pPost := "(", ")"
150 switch nextStep.(type) {
151 case *indirect:
152 continue // Next step is indirection, so let them batch up
153 case *structField:
154 numIndirect-- // Automatic indirection on struct fields
155 case nil:
156 pPre, pPost = "", "" // Last step; no need for parenthesis
157 }
158 if numIndirect > 0 {
159 ssPre = append(ssPre, pPre+strings.Repeat("*", numIndirect))
160 ssPost = append(ssPost, pPost)
161 }
162 numIndirect = 0
163 continue
164 case *transform:
165 ssPre = append(ssPre, s.trans.name+"(")
166 ssPost = append(ssPost, ")")
167 continue
168 case *typeAssertion:
169 // As a special-case, elide type assertions on anonymous types
170 // since they are typically generated dynamically and can be very
171 // verbose. For example, some transforms return interface{} because
172 // of Go's lack of generics, but typically take in and return the
173 // exact same concrete type.
174 if s.Type().PkgPath() == "" {
175 continue
176 }
177 }
178 ssPost = append(ssPost, s.String())
179 }
180 for i, j := 0, len(ssPre)-1; i < j; i, j = i+1, j-1 {
181 ssPre[i], ssPre[j] = ssPre[j], ssPre[i]
182 }
183 return strings.Join(ssPre, "") + strings.Join(ssPost, "")
184}
185
186type (
187 pathStep struct {
188 typ reflect.Type
189 }
190
191 sliceIndex struct {
192 pathStep
193 xkey, ykey int
194 }
195 mapIndex struct {
196 pathStep
197 key reflect.Value
198 }
199 typeAssertion struct {
200 pathStep
201 }
202 structField struct {
203 pathStep
204 name string
205 idx int
206
207 // These fields are used for forcibly accessing an unexported field.
208 // pvx, pvy, and field are only valid if unexported is true.
209 unexported bool
210 force bool // Forcibly allow visibility
211 pvx, pvy reflect.Value // Parent values
212 field reflect.StructField // Field information
213 }
214 indirect struct {
215 pathStep
216 }
217 transform struct {
218 pathStep
219 trans *transformer
220 }
221)
222
223func (ps pathStep) Type() reflect.Type { return ps.typ }
224func (ps pathStep) String() string {
225 if ps.typ == nil {
226 return "<nil>"
227 }
228 s := ps.typ.String()
229 if s == "" || strings.ContainsAny(s, "{}\n") {
230 return "root" // Type too simple or complex to print
231 }
232 return fmt.Sprintf("{%s}", s)
233}
234
235func (si sliceIndex) String() string {
236 switch {
237 case si.xkey == si.ykey:
238 return fmt.Sprintf("[%d]", si.xkey)
239 case si.ykey == -1:
240 // [5->?] means "I don't know where X[5] went"
241 return fmt.Sprintf("[%d->?]", si.xkey)
242 case si.xkey == -1:
243 // [?->3] means "I don't know where Y[3] came from"
244 return fmt.Sprintf("[?->%d]", si.ykey)
245 default:
246 // [5->3] means "X[5] moved to Y[3]"
247 return fmt.Sprintf("[%d->%d]", si.xkey, si.ykey)
248 }
249}
250func (mi mapIndex) String() string { return fmt.Sprintf("[%#v]", mi.key) }
251func (ta typeAssertion) String() string { return fmt.Sprintf(".(%v)", ta.typ) }
252func (sf structField) String() string { return fmt.Sprintf(".%s", sf.name) }
253func (in indirect) String() string { return "*" }
254func (tf transform) String() string { return fmt.Sprintf("%s()", tf.trans.name) }
255
256func (si sliceIndex) Key() int {
257 if si.xkey != si.ykey {
258 return -1
259 }
260 return si.xkey
261}
262func (si sliceIndex) SplitKeys() (x, y int) { return si.xkey, si.ykey }
263func (mi mapIndex) Key() reflect.Value { return mi.key }
264func (sf structField) Name() string { return sf.name }
265func (sf structField) Index() int { return sf.idx }
266func (tf transform) Name() string { return tf.trans.name }
267func (tf transform) Func() reflect.Value { return tf.trans.fnc }
268func (tf transform) Option() Option { return tf.trans }
269
270func (pathStep) isPathStep() {}
271func (sliceIndex) isSliceIndex() {}
272func (mapIndex) isMapIndex() {}
273func (typeAssertion) isTypeAssertion() {}
274func (structField) isStructField() {}
275func (indirect) isIndirect() {}
276func (transform) isTransform() {}
277
278var (
279 _ SliceIndex = sliceIndex{}
280 _ MapIndex = mapIndex{}
281 _ TypeAssertion = typeAssertion{}
282 _ StructField = structField{}
283 _ Indirect = indirect{}
284 _ Transform = transform{}
285
286 _ PathStep = sliceIndex{}
287 _ PathStep = mapIndex{}
288 _ PathStep = typeAssertion{}
289 _ PathStep = structField{}
290 _ PathStep = indirect{}
291 _ PathStep = transform{}
292)
293
294// isExported reports whether the identifier is exported.
295func isExported(id string) bool {
296 r, _ := utf8.DecodeRuneInString(id)
297 return unicode.IsUpper(r)
298}
299
300// isValid reports whether the identifier is valid.
301// Empty and underscore-only strings are not valid.
302func isValid(id string) bool {
303 ok := id != "" && id != "_"
304 for j, c := range id {
305 ok = ok && (j > 0 || !unicode.IsDigit(c))
306 ok = ok && (c == '_' || unicode.IsLetter(c) || unicode.IsDigit(c))
307 }
308 return ok
309}