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 file.
4
5package cmp
6
7import (
8 "fmt"
9 "reflect"
10 "strings"
11 "unicode"
12 "unicode/utf8"
13
14 "github.com/google/go-cmp/cmp/internal/value"
15)
16
17// Path is a list of [PathStep] describing the sequence of operations to get
18// from some root type to the current position in the value tree.
19// The first Path element is always an operation-less [PathStep] that exists
20// simply to identify the initial type.
21//
22// When traversing structs with embedded structs, the embedded struct will
23// always be accessed as a field before traversing the fields of the
24// embedded struct themselves. That is, an exported field from the
25// embedded struct will never be accessed directly from the parent struct.
26type Path []PathStep
27
28// PathStep is a union-type for specific operations to traverse
29// a value's tree structure. Users of this package never need to implement
30// these types as values of this type will be returned by this package.
31//
32// Implementations of this interface:
33// - [StructField]
34// - [SliceIndex]
35// - [MapIndex]
36// - [Indirect]
37// - [TypeAssertion]
38// - [Transform]
39type PathStep interface {
40 String() string
41
42 // Type is the resulting type after performing the path step.
43 Type() reflect.Type
44
45 // Values is the resulting values after performing the path step.
46 // The type of each valid value is guaranteed to be identical to Type.
47 //
48 // In some cases, one or both may be invalid or have restrictions:
49 // - For StructField, both are not interface-able if the current field
50 // is unexported and the struct type is not explicitly permitted by
51 // an Exporter to traverse unexported fields.
52 // - For SliceIndex, one may be invalid if an element is missing from
53 // either the x or y slice.
54 // - For MapIndex, one may be invalid if an entry is missing from
55 // either the x or y map.
56 //
57 // The provided values must not be mutated.
58 Values() (vx, vy reflect.Value)
59}
60
61var (
62 _ PathStep = StructField{}
63 _ PathStep = SliceIndex{}
64 _ PathStep = MapIndex{}
65 _ PathStep = Indirect{}
66 _ PathStep = TypeAssertion{}
67 _ PathStep = Transform{}
68)
69
70func (pa *Path) push(s PathStep) {
71 *pa = append(*pa, s)
72}
73
74func (pa *Path) pop() {
75 *pa = (*pa)[:len(*pa)-1]
76}
77
78// Last returns the last [PathStep] in the Path.
79// If the path is empty, this returns a non-nil [PathStep]
80// that reports a nil [PathStep.Type].
81func (pa Path) Last() PathStep {
82 return pa.Index(-1)
83}
84
85// Index returns the ith step in the Path and supports negative indexing.
86// A negative index starts counting from the tail of the Path such that -1
87// refers to the last step, -2 refers to the second-to-last step, and so on.
88// If index is invalid, this returns a non-nil [PathStep]
89// that reports a nil [PathStep.Type].
90func (pa Path) Index(i int) PathStep {
91 if i < 0 {
92 i = len(pa) + i
93 }
94 if i < 0 || i >= len(pa) {
95 return pathStep{}
96 }
97 return pa[i]
98}
99
100// String returns the simplified path to a node.
101// The simplified path only contains struct field accesses.
102//
103// For example:
104//
105// MyMap.MySlices.MyField
106func (pa Path) String() string {
107 var ss []string
108 for _, s := range pa {
109 if _, ok := s.(StructField); ok {
110 ss = append(ss, s.String())
111 }
112 }
113 return strings.TrimPrefix(strings.Join(ss, ""), ".")
114}
115
116// GoString returns the path to a specific node using Go syntax.
117//
118// For example:
119//
120// (*root.MyMap["key"].(*mypkg.MyStruct).MySlices)[2][3].MyField
121func (pa Path) GoString() string {
122 var ssPre, ssPost []string
123 var numIndirect int
124 for i, s := range pa {
125 var nextStep PathStep
126 if i+1 < len(pa) {
127 nextStep = pa[i+1]
128 }
129 switch s := s.(type) {
130 case Indirect:
131 numIndirect++
132 pPre, pPost := "(", ")"
133 switch nextStep.(type) {
134 case Indirect:
135 continue // Next step is indirection, so let them batch up
136 case StructField:
137 numIndirect-- // Automatic indirection on struct fields
138 case nil:
139 pPre, pPost = "", "" // Last step; no need for parenthesis
140 }
141 if numIndirect > 0 {
142 ssPre = append(ssPre, pPre+strings.Repeat("*", numIndirect))
143 ssPost = append(ssPost, pPost)
144 }
145 numIndirect = 0
146 continue
147 case Transform:
148 ssPre = append(ssPre, s.trans.name+"(")
149 ssPost = append(ssPost, ")")
150 continue
151 }
152 ssPost = append(ssPost, s.String())
153 }
154 for i, j := 0, len(ssPre)-1; i < j; i, j = i+1, j-1 {
155 ssPre[i], ssPre[j] = ssPre[j], ssPre[i]
156 }
157 return strings.Join(ssPre, "") + strings.Join(ssPost, "")
158}
159
160type pathStep struct {
161 typ reflect.Type
162 vx, vy reflect.Value
163}
164
165func (ps pathStep) Type() reflect.Type { return ps.typ }
166func (ps pathStep) Values() (vx, vy reflect.Value) { return ps.vx, ps.vy }
167func (ps pathStep) String() string {
168 if ps.typ == nil {
169 return "<nil>"
170 }
171 s := value.TypeString(ps.typ, false)
172 if s == "" || strings.ContainsAny(s, "{}\n") {
173 return "root" // Type too simple or complex to print
174 }
175 return fmt.Sprintf("{%s}", s)
176}
177
178// StructField is a [PathStep] that represents a struct field access
179// on a field called [StructField.Name].
180type StructField struct{ *structField }
181type structField struct {
182 pathStep
183 name string
184 idx int
185
186 // These fields are used for forcibly accessing an unexported field.
187 // pvx, pvy, and field are only valid if unexported is true.
188 unexported bool
189 mayForce bool // Forcibly allow visibility
190 paddr bool // Was parent addressable?
191 pvx, pvy reflect.Value // Parent values (always addressable)
192 field reflect.StructField // Field information
193}
194
195func (sf StructField) Type() reflect.Type { return sf.typ }
196func (sf StructField) Values() (vx, vy reflect.Value) {
197 if !sf.unexported {
198 return sf.vx, sf.vy // CanInterface reports true
199 }
200
201 // Forcibly obtain read-write access to an unexported struct field.
202 if sf.mayForce {
203 vx = retrieveUnexportedField(sf.pvx, sf.field, sf.paddr)
204 vy = retrieveUnexportedField(sf.pvy, sf.field, sf.paddr)
205 return vx, vy // CanInterface reports true
206 }
207 return sf.vx, sf.vy // CanInterface reports false
208}
209func (sf StructField) String() string { return fmt.Sprintf(".%s", sf.name) }
210
211// Name is the field name.
212func (sf StructField) Name() string { return sf.name }
213
214// Index is the index of the field in the parent struct type.
215// See [reflect.Type.Field].
216func (sf StructField) Index() int { return sf.idx }
217
218// SliceIndex is a [PathStep] that represents an index operation on
219// a slice or array at some index [SliceIndex.Key].
220type SliceIndex struct{ *sliceIndex }
221type sliceIndex struct {
222 pathStep
223 xkey, ykey int
224 isSlice bool // False for reflect.Array
225}
226
227func (si SliceIndex) Type() reflect.Type { return si.typ }
228func (si SliceIndex) Values() (vx, vy reflect.Value) { return si.vx, si.vy }
229func (si SliceIndex) String() string {
230 switch {
231 case si.xkey == si.ykey:
232 return fmt.Sprintf("[%d]", si.xkey)
233 case si.ykey == -1:
234 // [5->?] means "I don't know where X[5] went"
235 return fmt.Sprintf("[%d->?]", si.xkey)
236 case si.xkey == -1:
237 // [?->3] means "I don't know where Y[3] came from"
238 return fmt.Sprintf("[?->%d]", si.ykey)
239 default:
240 // [5->3] means "X[5] moved to Y[3]"
241 return fmt.Sprintf("[%d->%d]", si.xkey, si.ykey)
242 }
243}
244
245// Key is the index key; it may return -1 if in a split state
246func (si SliceIndex) Key() int {
247 if si.xkey != si.ykey {
248 return -1
249 }
250 return si.xkey
251}
252
253// SplitKeys are the indexes for indexing into slices in the
254// x and y values, respectively. These indexes may differ due to the
255// insertion or removal of an element in one of the slices, causing
256// all of the indexes to be shifted. If an index is -1, then that
257// indicates that the element does not exist in the associated slice.
258//
259// [SliceIndex.Key] is guaranteed to return -1 if and only if the indexes
260// returned by SplitKeys are not the same. SplitKeys will never return -1 for
261// both indexes.
262func (si SliceIndex) SplitKeys() (ix, iy int) { return si.xkey, si.ykey }
263
264// MapIndex is a [PathStep] that represents an index operation on a map at some index Key.
265type MapIndex struct{ *mapIndex }
266type mapIndex struct {
267 pathStep
268 key reflect.Value
269}
270
271func (mi MapIndex) Type() reflect.Type { return mi.typ }
272func (mi MapIndex) Values() (vx, vy reflect.Value) { return mi.vx, mi.vy }
273func (mi MapIndex) String() string { return fmt.Sprintf("[%#v]", mi.key) }
274
275// Key is the value of the map key.
276func (mi MapIndex) Key() reflect.Value { return mi.key }
277
278// Indirect is a [PathStep] that represents pointer indirection on the parent type.
279type Indirect struct{ *indirect }
280type indirect struct {
281 pathStep
282}
283
284func (in Indirect) Type() reflect.Type { return in.typ }
285func (in Indirect) Values() (vx, vy reflect.Value) { return in.vx, in.vy }
286func (in Indirect) String() string { return "*" }
287
288// TypeAssertion is a [PathStep] that represents a type assertion on an interface.
289type TypeAssertion struct{ *typeAssertion }
290type typeAssertion struct {
291 pathStep
292}
293
294func (ta TypeAssertion) Type() reflect.Type { return ta.typ }
295func (ta TypeAssertion) Values() (vx, vy reflect.Value) { return ta.vx, ta.vy }
296func (ta TypeAssertion) String() string { return fmt.Sprintf(".(%v)", value.TypeString(ta.typ, false)) }
297
298// Transform is a [PathStep] that represents a transformation
299// from the parent type to the current type.
300type Transform struct{ *transform }
301type transform struct {
302 pathStep
303 trans *transformer
304}
305
306func (tf Transform) Type() reflect.Type { return tf.typ }
307func (tf Transform) Values() (vx, vy reflect.Value) { return tf.vx, tf.vy }
308func (tf Transform) String() string { return fmt.Sprintf("%s()", tf.trans.name) }
309
310// Name is the name of the [Transformer].
311func (tf Transform) Name() string { return tf.trans.name }
312
313// Func is the function pointer to the transformer function.
314func (tf Transform) Func() reflect.Value { return tf.trans.fnc }
315
316// Option returns the originally constructed [Transformer] option.
317// The == operator can be used to detect the exact option used.
318func (tf Transform) Option() Option { return tf.trans }
319
320// pointerPath represents a dual-stack of pointers encountered when
321// recursively traversing the x and y values. This data structure supports
322// detection of cycles and determining whether the cycles are equal.
323// In Go, cycles can occur via pointers, slices, and maps.
324//
325// The pointerPath uses a map to represent a stack; where descension into a
326// pointer pushes the address onto the stack, and ascension from a pointer
327// pops the address from the stack. Thus, when traversing into a pointer from
328// reflect.Ptr, reflect.Slice element, or reflect.Map, we can detect cycles
329// by checking whether the pointer has already been visited. The cycle detection
330// uses a separate stack for the x and y values.
331//
332// If a cycle is detected we need to determine whether the two pointers
333// should be considered equal. The definition of equality chosen by Equal
334// requires two graphs to have the same structure. To determine this, both the
335// x and y values must have a cycle where the previous pointers were also
336// encountered together as a pair.
337//
338// Semantically, this is equivalent to augmenting Indirect, SliceIndex, and
339// MapIndex with pointer information for the x and y values.
340// Suppose px and py are two pointers to compare, we then search the
341// Path for whether px was ever encountered in the Path history of x, and
342// similarly so with py. If either side has a cycle, the comparison is only
343// equal if both px and py have a cycle resulting from the same PathStep.
344//
345// Using a map as a stack is more performant as we can perform cycle detection
346// in O(1) instead of O(N) where N is len(Path).
347type pointerPath struct {
348 // mx is keyed by x pointers, where the value is the associated y pointer.
349 mx map[value.Pointer]value.Pointer
350 // my is keyed by y pointers, where the value is the associated x pointer.
351 my map[value.Pointer]value.Pointer
352}
353
354func (p *pointerPath) Init() {
355 p.mx = make(map[value.Pointer]value.Pointer)
356 p.my = make(map[value.Pointer]value.Pointer)
357}
358
359// Push indicates intent to descend into pointers vx and vy where
360// visited reports whether either has been seen before. If visited before,
361// equal reports whether both pointers were encountered together.
362// Pop must be called if and only if the pointers were never visited.
363//
364// The pointers vx and vy must be a reflect.Ptr, reflect.Slice, or reflect.Map
365// and be non-nil.
366func (p pointerPath) Push(vx, vy reflect.Value) (equal, visited bool) {
367 px := value.PointerOf(vx)
368 py := value.PointerOf(vy)
369 _, ok1 := p.mx[px]
370 _, ok2 := p.my[py]
371 if ok1 || ok2 {
372 equal = p.mx[px] == py && p.my[py] == px // Pointers paired together
373 return equal, true
374 }
375 p.mx[px] = py
376 p.my[py] = px
377 return false, false
378}
379
380// Pop ascends from pointers vx and vy.
381func (p pointerPath) Pop(vx, vy reflect.Value) {
382 delete(p.mx, value.PointerOf(vx))
383 delete(p.my, value.PointerOf(vy))
384}
385
386// isExported reports whether the identifier is exported.
387func isExported(id string) bool {
388 r, _ := utf8.DecodeRuneInString(id)
389 return unicode.IsUpper(r)
390}