1
// Copyright 2020, 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

12
	"github.com/google/go-cmp/cmp/internal/flags"
13
	"github.com/google/go-cmp/cmp/internal/value"
14
)
15

16
const (
17
	pointerDelimPrefix = "⟪"
18
	pointerDelimSuffix = "⟫"
19
)
20

21
// formatPointer prints the address of the pointer.
22
func formatPointer(p value.Pointer, withDelims bool) string {
23
	v := p.Uintptr()
24
	if flags.Deterministic {
25
		v = 0xdeadf00f // Only used for stable testing purposes
26
	}
27
	if withDelims {
28
		return pointerDelimPrefix + formatHex(uint64(v)) + pointerDelimSuffix
29
	}
30
	return formatHex(uint64(v))
31
}
32

33
// pointerReferences is a stack of pointers visited so far.
34
type pointerReferences [][2]value.Pointer
35

36
func (ps *pointerReferences) PushPair(vx, vy reflect.Value, d diffMode, deref bool) (pp [2]value.Pointer) {
37
	if deref && vx.IsValid() {
38
		vx = vx.Addr()
39
	}
40
	if deref && vy.IsValid() {
41
		vy = vy.Addr()
42
	}
43
	switch d {
44
	case diffUnknown, diffIdentical:
45
		pp = [2]value.Pointer{value.PointerOf(vx), value.PointerOf(vy)}
46
	case diffRemoved:
47
		pp = [2]value.Pointer{value.PointerOf(vx), value.Pointer{}}
48
	case diffInserted:
49
		pp = [2]value.Pointer{value.Pointer{}, value.PointerOf(vy)}
50
	}
51
	*ps = append(*ps, pp)
52
	return pp
53
}
54

55
func (ps *pointerReferences) Push(v reflect.Value) (p value.Pointer, seen bool) {
56
	p = value.PointerOf(v)
57
	for _, pp := range *ps {
58
		if p == pp[0] || p == pp[1] {
59
			return p, true
60
		}
61
	}
62
	*ps = append(*ps, [2]value.Pointer{p, p})
63
	return p, false
64
}
65

66
func (ps *pointerReferences) Pop() {
67
	*ps = (*ps)[:len(*ps)-1]
68
}
69

70
// trunkReferences is metadata for a textNode indicating that the sub-tree
71
// represents the value for either pointer in a pair of references.
72
type trunkReferences struct{ pp [2]value.Pointer }
73

74
// trunkReference is metadata for a textNode indicating that the sub-tree
75
// represents the value for the given pointer reference.
76
type trunkReference struct{ p value.Pointer }
77

78
// leafReference is metadata for a textNode indicating that the value is
79
// truncated as it refers to another part of the tree (i.e., a trunk).
80
type leafReference struct{ p value.Pointer }
81

82
func wrapTrunkReferences(pp [2]value.Pointer, s textNode) textNode {
83
	switch {
84
	case pp[0].IsNil():
85
		return &textWrap{Value: s, Metadata: trunkReference{pp[1]}}
86
	case pp[1].IsNil():
87
		return &textWrap{Value: s, Metadata: trunkReference{pp[0]}}
88
	case pp[0] == pp[1]:
89
		return &textWrap{Value: s, Metadata: trunkReference{pp[0]}}
90
	default:
91
		return &textWrap{Value: s, Metadata: trunkReferences{pp}}
92
	}
93
}
94
func wrapTrunkReference(p value.Pointer, printAddress bool, s textNode) textNode {
95
	var prefix string
96
	if printAddress {
97
		prefix = formatPointer(p, true)
98
	}
99
	return &textWrap{Prefix: prefix, Value: s, Metadata: trunkReference{p}}
100
}
101
func makeLeafReference(p value.Pointer, printAddress bool) textNode {
102
	out := &textWrap{Prefix: "(", Value: textEllipsis, Suffix: ")"}
103
	var prefix string
104
	if printAddress {
105
		prefix = formatPointer(p, true)
106
	}
107
	return &textWrap{Prefix: prefix, Value: out, Metadata: leafReference{p}}
108
}
109

110
// resolveReferences walks the textNode tree searching for any leaf reference
111
// metadata and resolves each against the corresponding trunk references.
112
// Since pointer addresses in memory are not particularly readable to the user,
113
// it replaces each pointer value with an arbitrary and unique reference ID.
114
func resolveReferences(s textNode) {
115
	var walkNodes func(textNode, func(textNode))
116
	walkNodes = func(s textNode, f func(textNode)) {
117
		f(s)
118
		switch s := s.(type) {
119
		case *textWrap:
120
			walkNodes(s.Value, f)
121
		case textList:
122
			for _, r := range s {
123
				walkNodes(r.Value, f)
124
			}
125
		}
126
	}
127

128
	// Collect all trunks and leaves with reference metadata.
129
	var trunks, leaves []*textWrap
130
	walkNodes(s, func(s textNode) {
131
		if s, ok := s.(*textWrap); ok {
132
			switch s.Metadata.(type) {
133
			case leafReference:
134
				leaves = append(leaves, s)
135
			case trunkReference, trunkReferences:
136
				trunks = append(trunks, s)
137
			}
138
		}
139
	})
140

141
	// No leaf references to resolve.
142
	if len(leaves) == 0 {
143
		return
144
	}
145

146
	// Collect the set of all leaf references to resolve.
147
	leafPtrs := make(map[value.Pointer]bool)
148
	for _, leaf := range leaves {
149
		leafPtrs[leaf.Metadata.(leafReference).p] = true
150
	}
151

152
	// Collect the set of trunk pointers that are always paired together.
153
	// This allows us to assign a single ID to both pointers for brevity.
154
	// If a pointer in a pair ever occurs by itself or as a different pair,
155
	// then the pair is broken.
156
	pairedTrunkPtrs := make(map[value.Pointer]value.Pointer)
157
	unpair := func(p value.Pointer) {
158
		if !pairedTrunkPtrs[p].IsNil() {
159
			pairedTrunkPtrs[pairedTrunkPtrs[p]] = value.Pointer{} // invalidate other half
160
		}
161
		pairedTrunkPtrs[p] = value.Pointer{} // invalidate this half
162
	}
163
	for _, trunk := range trunks {
164
		switch p := trunk.Metadata.(type) {
165
		case trunkReference:
166
			unpair(p.p) // standalone pointer cannot be part of a pair
167
		case trunkReferences:
168
			p0, ok0 := pairedTrunkPtrs[p.pp[0]]
169
			p1, ok1 := pairedTrunkPtrs[p.pp[1]]
170
			switch {
171
			case !ok0 && !ok1:
172
				// Register the newly seen pair.
173
				pairedTrunkPtrs[p.pp[0]] = p.pp[1]
174
				pairedTrunkPtrs[p.pp[1]] = p.pp[0]
175
			case ok0 && ok1 && p0 == p.pp[1] && p1 == p.pp[0]:
176
				// Exact pair already seen; do nothing.
177
			default:
178
				// Pair conflicts with some other pair; break all pairs.
179
				unpair(p.pp[0])
180
				unpair(p.pp[1])
181
			}
182
		}
183
	}
184

185
	// Correlate each pointer referenced by leaves to a unique identifier,
186
	// and print the IDs for each trunk that matches those pointers.
187
	var nextID uint
188
	ptrIDs := make(map[value.Pointer]uint)
189
	newID := func() uint {
190
		id := nextID
191
		nextID++
192
		return id
193
	}
194
	for _, trunk := range trunks {
195
		switch p := trunk.Metadata.(type) {
196
		case trunkReference:
197
			if print := leafPtrs[p.p]; print {
198
				id, ok := ptrIDs[p.p]
199
				if !ok {
200
					id = newID()
201
					ptrIDs[p.p] = id
202
				}
203
				trunk.Prefix = updateReferencePrefix(trunk.Prefix, formatReference(id))
204
			}
205
		case trunkReferences:
206
			print0 := leafPtrs[p.pp[0]]
207
			print1 := leafPtrs[p.pp[1]]
208
			if print0 || print1 {
209
				id0, ok0 := ptrIDs[p.pp[0]]
210
				id1, ok1 := ptrIDs[p.pp[1]]
211
				isPair := pairedTrunkPtrs[p.pp[0]] == p.pp[1] && pairedTrunkPtrs[p.pp[1]] == p.pp[0]
212
				if isPair {
213
					var id uint
214
					assert(ok0 == ok1) // must be seen together or not at all
215
					if ok0 {
216
						assert(id0 == id1) // must have the same ID
217
						id = id0
218
					} else {
219
						id = newID()
220
						ptrIDs[p.pp[0]] = id
221
						ptrIDs[p.pp[1]] = id
222
					}
223
					trunk.Prefix = updateReferencePrefix(trunk.Prefix, formatReference(id))
224
				} else {
225
					if print0 && !ok0 {
226
						id0 = newID()
227
						ptrIDs[p.pp[0]] = id0
228
					}
229
					if print1 && !ok1 {
230
						id1 = newID()
231
						ptrIDs[p.pp[1]] = id1
232
					}
233
					switch {
234
					case print0 && print1:
235
						trunk.Prefix = updateReferencePrefix(trunk.Prefix, formatReference(id0)+","+formatReference(id1))
236
					case print0:
237
						trunk.Prefix = updateReferencePrefix(trunk.Prefix, formatReference(id0))
238
					case print1:
239
						trunk.Prefix = updateReferencePrefix(trunk.Prefix, formatReference(id1))
240
					}
241
				}
242
			}
243
		}
244
	}
245

246
	// Update all leaf references with the unique identifier.
247
	for _, leaf := range leaves {
248
		if id, ok := ptrIDs[leaf.Metadata.(leafReference).p]; ok {
249
			leaf.Prefix = updateReferencePrefix(leaf.Prefix, formatReference(id))
250
		}
251
	}
252
}
253

254
func formatReference(id uint) string {
255
	return fmt.Sprintf("ref#%d", id)
256
}
257

258
func updateReferencePrefix(prefix, ref string) string {
259
	if prefix == "" {
260
		return pointerDelimPrefix + ref + pointerDelimSuffix
261
	}
262
	suffix := strings.TrimPrefix(prefix, pointerDelimPrefix)
263
	return pointerDelimPrefix + ref + ": " + suffix
264
}
265

266