cmp/report_references.go

// Copyright 2020, The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

package cmp

import (
	"fmt"
	"reflect"
	"strings"

	"github.com/google/go-cmp/cmp/internal/flags"
	"github.com/google/go-cmp/cmp/internal/value"
)

const (
	pointerDelimPrefix = "⟪"
	pointerDelimSuffix = "⟫"
)

// formatPointer prints the address of the pointer.
func formatPointer(p value.Pointer, withDelims bool) string {
	v := p.Uintptr()
	if flags.Deterministic {
		v = 0xdeadf00f // Only used for stable testing purposes
	}
	if withDelims {
		return pointerDelimPrefix + formatHex(uint64(v)) + pointerDelimSuffix
	}
	return formatHex(uint64(v))
}

// pointerReferences is a stack of pointers visited so far.
type pointerReferences [][2]value.Pointer

func (ps *pointerReferences) PushPair(vx, vy reflect.Value, d diffMode, deref bool) (pp [2]value.Pointer) {
	if deref && vx.IsValid() {
		vx = vx.Addr()
	}
	if deref && vy.IsValid() {
		vy = vy.Addr()
	}
	switch d {
	case diffUnknown, diffIdentical:
		pp = [2]value.Pointer{value.PointerOf(vx), value.PointerOf(vy)}
	case diffRemoved:
		pp = [2]value.Pointer{value.PointerOf(vx), value.Pointer{}}
	case diffInserted:
		pp = [2]value.Pointer{value.Pointer{}, value.PointerOf(vy)}
	}
	*ps = append(*ps, pp)
	return pp
}

func (ps *pointerReferences) Push(v reflect.Value) (p value.Pointer, seen bool) {
	p = value.PointerOf(v)
	for _, pp := range *ps {
		if p == pp[0] || p == pp[1] {
			return p, true
		}
	}
	*ps = append(*ps, [2]value.Pointer{p, p})
	return p, false
}

func (ps *pointerReferences) Pop() {
	*ps = (*ps)[:len(*ps)-1]
}

// trunkReferences is metadata for a textNode indicating that the sub-tree
// represents the value for either pointer in a pair of references.
type trunkReferences struct{ pp [2]value.Pointer }

// trunkReference is metadata for a textNode indicating that the sub-tree
// represents the value for the given pointer reference.
type trunkReference struct{ p value.Pointer }

// leafReference is metadata for a textNode indicating that the value is
// truncated as it refers to another part of the tree (i.e., a trunk).
type leafReference struct{ p value.Pointer }

func wrapTrunkReferences(pp [2]value.Pointer, s textNode) textNode {
	switch {
	case pp[0].IsNil():
		return &textWrap{Value: s, Metadata: trunkReference{pp[1]}}
	case pp[1].IsNil():
		return &textWrap{Value: s, Metadata: trunkReference{pp[0]}}
	case pp[0] == pp[1]:
		return &textWrap{Value: s, Metadata: trunkReference{pp[0]}}
	default:
		return &textWrap{Value: s, Metadata: trunkReferences{pp}}
	}
}
func wrapTrunkReference(p value.Pointer, printAddress bool, s textNode) textNode {
	var prefix string
	if printAddress {
		prefix = formatPointer(p, true)
	}
	return &textWrap{Prefix: prefix, Value: s, Metadata: trunkReference{p}}
}
func makeLeafReference(p value.Pointer, printAddress bool) textNode {
	out := &textWrap{Prefix: "(", Value: textEllipsis, Suffix: ")"}
	var prefix string
	if printAddress {
		prefix = formatPointer(p, true)
	}
	return &textWrap{Prefix: prefix, Value: out, Metadata: leafReference{p}}
}

// resolveReferences walks the textNode tree searching for any leaf reference
// metadata and resolves each against the corresponding trunk references.
// Since pointer addresses in memory are not particularly readable to the user,
// it replaces each pointer value with an arbitrary and unique reference ID.
func resolveReferences(s textNode) {
	var walkNodes func(textNode, func(textNode))
	walkNodes = func(s textNode, f func(textNode)) {
		f(s)
		switch s := s.(type) {
		case *textWrap:
			walkNodes(s.Value, f)
		case textList:
			for _, r := range s {
				walkNodes(r.Value, f)
			}
		}
	}

	// Collect all trunks and leaves with reference metadata.
	var trunks, leaves []*textWrap
	walkNodes(s, func(s textNode) {
		if s, ok := s.(*textWrap); ok {
			switch s.Metadata.(type) {
			case leafReference:
				leaves = append(leaves, s)
			case trunkReference, trunkReferences:
				trunks = append(trunks, s)
			}
		}
	})

	// No leaf references to resolve.
	if len(leaves) == 0 {
		return
	}

	// Collect the set of all leaf references to resolve.
	leafPtrs := make(map[value.Pointer]bool)
	for _, leaf := range leaves {
		leafPtrs[leaf.Metadata.(leafReference).p] = true
	}

	// Collect the set of trunk pointers that are always paired together.
	// This allows us to assign a single ID to both pointers for brevity.
	// If a pointer in a pair ever occurs by itself or as a different pair,
	// then the pair is broken.
	pairedTrunkPtrs := make(map[value.Pointer]value.Pointer)
	unpair := func(p value.Pointer) {
		if !pairedTrunkPtrs[p].IsNil() {
			pairedTrunkPtrs[pairedTrunkPtrs[p]] = value.Pointer{} // invalidate other half
		}
		pairedTrunkPtrs[p] = value.Pointer{} // invalidate this half
	}
	for _, trunk := range trunks {
		switch p := trunk.Metadata.(type) {
		case trunkReference:
			unpair(p.p) // standalone pointer cannot be part of a pair
		case trunkReferences:
			p0, ok0 := pairedTrunkPtrs[p.pp[0]]
			p1, ok1 := pairedTrunkPtrs[p.pp[1]]
			switch {
			case !ok0 && !ok1:
				// Register the newly seen pair.
				pairedTrunkPtrs[p.pp[0]] = p.pp[1]
				pairedTrunkPtrs[p.pp[1]] = p.pp[0]
			case ok0 && ok1 && p0 == p.pp[1] && p1 == p.pp[0]:
				// Exact pair already seen; do nothing.
			default:
				// Pair conflicts with some other pair; break all pairs.
				unpair(p.pp[0])
				unpair(p.pp[1])
			}
		}
	}

	// Correlate each pointer referenced by leaves to a unique identifier,
	// and print the IDs for each trunk that matches those pointers.
	var nextID uint
	ptrIDs := make(map[value.Pointer]uint)
	newID := func() uint {
		id := nextID
		nextID++
		return id
	}
	for _, trunk := range trunks {
		switch p := trunk.Metadata.(type) {
		case trunkReference:
			if print := leafPtrs[p.p]; print {
				id, ok := ptrIDs[p.p]
				if !ok {
					id = newID()
					ptrIDs[p.p] = id
				}
				trunk.Prefix = updateReferencePrefix(trunk.Prefix, formatReference(id))
			}
		case trunkReferences:
			print0 := leafPtrs[p.pp[0]]
			print1 := leafPtrs[p.pp[1]]
			if print0 || print1 {
				id0, ok0 := ptrIDs[p.pp[0]]
				id1, ok1 := ptrIDs[p.pp[1]]
				isPair := pairedTrunkPtrs[p.pp[0]] == p.pp[1] && pairedTrunkPtrs[p.pp[1]] == p.pp[0]
				if isPair {
					var id uint
					assert(ok0 == ok1) // must be seen together or not at all
					if ok0 {
						assert(id0 == id1) // must have the same ID
						id = id0
					} else {
						id = newID()
						ptrIDs[p.pp[0]] = id
						ptrIDs[p.pp[1]] = id
					}
					trunk.Prefix = updateReferencePrefix(trunk.Prefix, formatReference(id))
				} else {
					if print0 && !ok0 {
						id0 = newID()
						ptrIDs[p.pp[0]] = id0
					}
					if print1 && !ok1 {
						id1 = newID()
						ptrIDs[p.pp[1]] = id1
					}
					switch {
					case print0 && print1:
						trunk.Prefix = updateReferencePrefix(trunk.Prefix, formatReference(id0)+","+formatReference(id1))
					case print0:
						trunk.Prefix = updateReferencePrefix(trunk.Prefix, formatReference(id0))
					case print1:
						trunk.Prefix = updateReferencePrefix(trunk.Prefix, formatReference(id1))
					}
				}
			}
		}
	}

	// Update all leaf references with the unique identifier.
	for _, leaf := range leaves {
		if id, ok := ptrIDs[leaf.Metadata.(leafReference).p]; ok {
			leaf.Prefix = updateReferencePrefix(leaf.Prefix, formatReference(id))
		}
	}
}

func formatReference(id uint) string {
	return fmt.Sprintf("ref#%d", id)
}

func updateReferencePrefix(prefix, ref string) string {
	if prefix == "" {
		return pointerDelimPrefix + ref + pointerDelimSuffix
	}
	suffix := strings.TrimPrefix(prefix, pointerDelimPrefix)
	return pointerDelimPrefix + ref + ": " + suffix
}