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