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
5package cmp
6
7import (
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
16const (
17 pointerDelimPrefix = "⟪"
18 pointerDelimSuffix = "⟫"
19)
20
21// formatPointer prints the address of the pointer.
22func 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.
34type pointerReferences [][2]value.Pointer
35
36func (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
55func (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
66func (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.
72type 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.
76type 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).
80type leafReference struct{ p value.Pointer }
81
82func 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}
94func 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}
101func 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.
114func 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
254func formatReference(id uint) string {
255 return fmt.Sprintf("ref#%d", id)
256}
257
258func 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}