Source: report_references.go in package github.com/google/go-cmp/cmp


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 {

				pairedTrunkPtrs[p.pp[0]] = p.pp[1]
				pairedTrunkPtrs[p.pp[1]] = p.pp[0]

Exact pair already seen; do nothing.

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