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