.config/coc/extensions/coc-go-data/tools/pkg/mod/github.com/google/go-cmp@v0.5.1/cmp/report_references.go

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