aboutsummaryrefslogtreecommitdiff
path: root/vendor/github.com/google/go-cmp/cmp/path.go
blob: 3d45c1a47f28072fc0d160792dd2857019e19e84 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
// 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 file.

package cmp

import (
	"fmt"
	"reflect"
	"strings"
	"unicode"
	"unicode/utf8"

	"github.com/google/go-cmp/cmp/internal/value"
)

// 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.
type 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.
//
// Implementations of this interface are
// StructField, SliceIndex, MapIndex, Indirect, TypeAssertion, and Transform.
type PathStep interface {
	String() string

	// Type is the resulting type after performing the path step.
	Type() reflect.Type

	// Values is the resulting values after performing the path step.
	// The type of each valid value is guaranteed to be identical to Type.
	//
	// In some cases, one or both may be invalid or have restrictions:
	//	• For StructField, both are not interface-able if the current field
	//	is unexported and the struct type is not explicitly permitted by
	//	an Exporter to traverse unexported fields.
	//	• For SliceIndex, one may be invalid if an element is missing from
	//	either the x or y slice.
	//	• For MapIndex, one may be invalid if an entry is missing from
	//	either the x or y map.
	//
	// The provided values must not be mutated.
	Values() (vx, vy reflect.Value)
}

var (
	_ PathStep = StructField{}
	_ PathStep = SliceIndex{}
	_ PathStep = MapIndex{}
	_ PathStep = Indirect{}
	_ PathStep = TypeAssertion{}
	_ PathStep = Transform{}
)

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
		}
		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
	vx, vy reflect.Value
}

func (ps pathStep) Type() reflect.Type             { return ps.typ }
func (ps pathStep) Values() (vx, vy reflect.Value) { return ps.vx, ps.vy }
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)
}

// StructField represents a struct field access on a field called Name.
type StructField struct{ *structField }
type 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
	mayForce   bool                // Forcibly allow visibility
	paddr      bool                // Was parent addressable?
	pvx, pvy   reflect.Value       // Parent values (always addressible)
	field      reflect.StructField // Field information
}

func (sf StructField) Type() reflect.Type { return sf.typ }
func (sf StructField) Values() (vx, vy reflect.Value) {
	if !sf.unexported {
		return sf.vx, sf.vy // CanInterface reports true
	}

	// Forcibly obtain read-write access to an unexported struct field.
	if sf.mayForce {
		vx = retrieveUnexportedField(sf.pvx, sf.field, sf.paddr)
		vy = retrieveUnexportedField(sf.pvy, sf.field, sf.paddr)
		return vx, vy // CanInterface reports true
	}
	return sf.vx, sf.vy // CanInterface reports false
}
func (sf StructField) String() string { return fmt.Sprintf(".%s", sf.name) }

// Name is the field name.
func (sf StructField) Name() string { return sf.name }

// Index is the index of the field in the parent struct type.
// See reflect.Type.Field.
func (sf StructField) Index() int { return sf.idx }

// SliceIndex is an index operation on a slice or array at some index Key.
type SliceIndex struct{ *sliceIndex }
type sliceIndex struct {
	pathStep
	xkey, ykey int
	isSlice    bool // False for reflect.Array
}

func (si SliceIndex) Type() reflect.Type             { return si.typ }
func (si SliceIndex) Values() (vx, vy reflect.Value) { return si.vx, si.vy }
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)
	}
}

// Key is the index key; it may return -1 if in a split state
func (si SliceIndex) Key() int {
	if si.xkey != si.ykey {
		return -1
	}
	return si.xkey
}

// SplitKeys are 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.
func (si SliceIndex) SplitKeys() (ix, iy int) { return si.xkey, si.ykey }

// MapIndex is an index operation on a map at some index Key.
type MapIndex struct{ *mapIndex }
type mapIndex struct {
	pathStep
	key reflect.Value
}

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

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

// Indirect represents pointer indirection on the parent type.
type Indirect struct{ *indirect }
type indirect struct {
	pathStep
}

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

// TypeAssertion represents a type assertion on an interface.
type TypeAssertion struct{ *typeAssertion }
type typeAssertion struct {
	pathStep
}

func (ta TypeAssertion) Type() reflect.Type             { return ta.typ }
func (ta TypeAssertion) Values() (vx, vy reflect.Value) { return ta.vx, ta.vy }
func (ta TypeAssertion) String() string                 { return fmt.Sprintf(".(%v)", ta.typ) }

// Transform is a transformation from the parent type to the current type.
type Transform struct{ *transform }
type transform struct {
	pathStep
	trans *transformer
}

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

// Name is the name of the Transformer.
func (tf Transform) Name() string { return tf.trans.name }

// Func is the function pointer to the transformer function.
func (tf Transform) Func() reflect.Value { return tf.trans.fnc }

// Option returns the originally constructed Transformer option.
// The == operator can be used to detect the exact option used.
func (tf Transform) Option() Option { return tf.trans }

// pointerPath represents a dual-stack of pointers encountered when
// recursively traversing the x and y values. This data structure supports
// detection of cycles and determining whether the cycles are equal.
// In Go, cycles can occur via pointers, slices, and maps.
//
// The pointerPath uses a map to represent a stack; where descension into a
// pointer pushes the address onto the stack, and ascension from a pointer
// pops the address from the stack. Thus, when traversing into a pointer from
// reflect.Ptr, reflect.Slice element, or reflect.Map, we can detect cycles
// by checking whether the pointer has already been visited. The cycle detection
// uses a seperate stack for the x and y values.
//
// If a cycle is detected we need to determine whether the two pointers
// should be considered equal. The definition of equality chosen by Equal
// requires two graphs to have the same structure. To determine this, both the
// x and y values must have a cycle where the previous pointers were also
// encountered together as a pair.
//
// Semantically, this is equivalent to augmenting Indirect, SliceIndex, and
// MapIndex with pointer information for the x and y values.
// Suppose px and py are two pointers to compare, we then search the
// Path for whether px was ever encountered in the Path history of x, and
// similarly so with py. If either side has a cycle, the comparison is only
// equal if both px and py have a cycle resulting from the same PathStep.
//
// Using a map as a stack is more performant as we can perform cycle detection
// in O(1) instead of O(N) where N is len(Path).
type pointerPath struct {
	// mx is keyed by x pointers, where the value is the associated y pointer.
	mx map[value.Pointer]value.Pointer
	// my is keyed by y pointers, where the value is the associated x pointer.
	my map[value.Pointer]value.Pointer
}

func (p *pointerPath) Init() {
	p.mx = make(map[value.Pointer]value.Pointer)
	p.my = make(map[value.Pointer]value.Pointer)
}

// Push indicates intent to descend into pointers vx and vy where
// visited reports whether either has been seen before. If visited before,
// equal reports whether both pointers were encountered together.
// Pop must be called if and only if the pointers were never visited.
//
// The pointers vx and vy must be a reflect.Ptr, reflect.Slice, or reflect.Map
// and be non-nil.
func (p pointerPath) Push(vx, vy reflect.Value) (equal, visited bool) {
	px := value.PointerOf(vx)
	py := value.PointerOf(vy)
	_, ok1 := p.mx[px]
	_, ok2 := p.my[py]
	if ok1 || ok2 {
		equal = p.mx[px] == py && p.my[py] == px // Pointers paired together
		return equal, true
	}
	p.mx[px] = py
	p.my[py] = px
	return false, false
}

// Pop ascends from pointers vx and vy.
func (p pointerPath) Pop(vx, vy reflect.Value) {
	delete(p.mx, value.PointerOf(vx))
	delete(p.my, value.PointerOf(vy))
}

// isExported reports whether the identifier is exported.
func isExported(id string) bool {
	r, _ := utf8.DecodeRuneInString(id)
	return unicode.IsUpper(r)
}