report_references.go

Documentation: github.com/google/go-cmp/cmp

     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
View as plain text