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

5
package cmp
6

7
import (
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.
26
type 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]
39
type 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

61
var (
62
	_ PathStep = StructField{}
63
	_ PathStep = SliceIndex{}
64
	_ PathStep = MapIndex{}
65
	_ PathStep = Indirect{}
66
	_ PathStep = TypeAssertion{}
67
	_ PathStep = Transform{}
68
)
69

70
func (pa *Path) push(s PathStep) {
71
	*pa = append(*pa, s)
72
}
73

74
func (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].
81
func (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].
90
func (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
106
func (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
121
func (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

160
type pathStep struct {
161
	typ    reflect.Type
162
	vx, vy reflect.Value
163
}
164

165
func (ps pathStep) Type() reflect.Type             { return ps.typ }
166
func (ps pathStep) Values() (vx, vy reflect.Value) { return ps.vx, ps.vy }
167
func (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].
180
type StructField struct{ *structField }
181
type 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

195
func (sf StructField) Type() reflect.Type { return sf.typ }
196
func (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
}
209
func (sf StructField) String() string { return fmt.Sprintf(".%s", sf.name) }
210

211
// Name is the field name.
212
func (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].
216
func (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].
220
type SliceIndex struct{ *sliceIndex }
221
type sliceIndex struct {
222
	pathStep
223
	xkey, ykey int
224
	isSlice    bool // False for reflect.Array
225
}
226

227
func (si SliceIndex) Type() reflect.Type             { return si.typ }
228
func (si SliceIndex) Values() (vx, vy reflect.Value) { return si.vx, si.vy }
229
func (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
246
func (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.
262
func (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.
265
type MapIndex struct{ *mapIndex }
266
type mapIndex struct {
267
	pathStep
268
	key reflect.Value
269
}
270

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

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

278
// Indirect is a [PathStep] that represents pointer indirection on the parent type.
279
type Indirect struct{ *indirect }
280
type indirect struct {
281
	pathStep
282
}
283

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

288
// TypeAssertion is a [PathStep] that represents a type assertion on an interface.
289
type TypeAssertion struct{ *typeAssertion }
290
type typeAssertion struct {
291
	pathStep
292
}
293

294
func (ta TypeAssertion) Type() reflect.Type             { return ta.typ }
295
func (ta TypeAssertion) Values() (vx, vy reflect.Value) { return ta.vx, ta.vy }
296
func (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.
300
type Transform struct{ *transform }
301
type transform struct {
302
	pathStep
303
	trans *transformer
304
}
305

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

310
// Name is the name of the [Transformer].
311
func (tf Transform) Name() string { return tf.trans.name }
312

313
// Func is the function pointer to the transformer function.
314
func (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.
318
func (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).
347
type 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

354
func (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.
366
func (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.
381
func (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.
387
func isExported(id string) bool {
388
	r, _ := utf8.DecodeRuneInString(id)
389
	return unicode.IsUpper(r)
390
}
391

392