// 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 (
	
	
	

	
	
)

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

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

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

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

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

func ( *pointerReferences) () {
	* = (*)[:len(*)-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( [2]value.Pointer,  textNode) textNode {
	switch {
	case [0].IsNil():
		return &textWrap{Value: , Metadata: trunkReference{[1]}}
	case [1].IsNil():
		return &textWrap{Value: , Metadata: trunkReference{[0]}}
	case [0] == [1]:
		return &textWrap{Value: , Metadata: trunkReference{[0]}}
	default:
		return &textWrap{Value: , Metadata: trunkReferences{}}
	}
}
func wrapTrunkReference( value.Pointer,  bool,  textNode) textNode {
	var  string
	if  {
		 = formatPointer(, true)
	}
	return &textWrap{Prefix: , Value: , Metadata: trunkReference{}}
}
func makeLeafReference( value.Pointer,  bool) textNode {
	 := &textWrap{Prefix: "(", Value: textEllipsis, Suffix: ")"}
	var  string
	if  {
		 = formatPointer(, true)
	}
	return &textWrap{Prefix: , Value: , Metadata: leafReference{}}
}

// 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( textNode) {
	var  func(textNode, func(textNode))
	 = func( textNode,  func(textNode)) {
		()
		switch s := .(type) {
		case *textWrap:
			(.Value, )
		case textList:
			for ,  := range  {
				(.Value, )
			}
		}
	}

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

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

	// Collect the set of all leaf references to resolve.
	 := make(map[value.Pointer]bool)
	for ,  := range  {
		[.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.
	 := make(map[value.Pointer]value.Pointer)
	 := func( value.Pointer) {
		if ![].IsNil() {
			[[]] = value.Pointer{} // invalidate other half
		}
		[] = value.Pointer{} // invalidate this half
	}
	for ,  := range  {
		switch p := .Metadata.(type) {
		case trunkReference:
			(.p) // standalone pointer cannot be part of a pair
		case trunkReferences:
			,  := [.pp[0]]
			,  := [.pp[1]]
			switch {
			case ! && !:
				// Register the newly seen pair.
				[.pp[0]] = .pp[1]
				[.pp[1]] = .pp[0]
			case  &&  &&  == .pp[1] &&  == .pp[0]:
				// Exact pair already seen; do nothing.
			default:
				// Pair conflicts with some other pair; break all pairs.
				(.pp[0])
				(.pp[1])
			}
		}
	}

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

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

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

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