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.md 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}
265