// Copyright 2019, 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 (
	
	
)

// numContextRecords is the number of surrounding equal records to print.
const numContextRecords = 2

type diffMode byte

const (
	diffUnknown   diffMode = 0
	diffIdentical diffMode = ' '
	diffRemoved   diffMode = '-'
	diffInserted  diffMode = '+'
)

type typeMode int

const (
	// emitType always prints the type.
	emitType typeMode = iota
	// elideType never prints the type.
	elideType
	// autoType prints the type only for composite kinds
	// (i.e., structs, slices, arrays, and maps).
	autoType
)

type formatOptions struct {
	// DiffMode controls the output mode of FormatDiff.
	//
	// If diffUnknown,   then produce a diff of the x and y values.
	// If diffIdentical, then emit values as if they were equal.
	// If diffRemoved,   then only emit x values (ignoring y values).
	// If diffInserted,  then only emit y values (ignoring x values).
	DiffMode diffMode

	// TypeMode controls whether to print the type for the current node.
	//
	// As a general rule of thumb, we always print the type of the next node
	// after an interface, and always elide the type of the next node after
	// a slice or map node.
	TypeMode typeMode

	// formatValueOptions are options specific to printing reflect.Values.
	formatValueOptions
}

func ( formatOptions) ( diffMode) formatOptions {
	.DiffMode = 
	return 
}
func ( formatOptions) ( typeMode) formatOptions {
	.TypeMode = 
	return 
}
func ( formatOptions) ( int) formatOptions {
	.VerbosityLevel = 
	.LimitVerbosity = true
	return 
}
func ( formatOptions) () uint {
	switch {
	case .VerbosityLevel < 0:
		return 0
	case .VerbosityLevel > 16:
		return 16 // some reasonable maximum to avoid shift overflow
	default:
		return uint(.VerbosityLevel)
	}
}

const maxVerbosityPreset = 6

// verbosityPreset modifies the verbosity settings given an index
// between 0 and maxVerbosityPreset, inclusive.
func verbosityPreset( formatOptions,  int) formatOptions {
	.VerbosityLevel = int(.verbosity()) + 2*
	if  > 0 {
		.AvoidStringer = true
	}
	if  >= maxVerbosityPreset {
		.PrintAddresses = true
		.QualifiedNames = true
	}
	return 
}

// FormatDiff converts a valueNode tree into a textNode tree, where the later
// is a textual representation of the differences detected in the former.
func ( formatOptions) ( *valueNode,  *pointerReferences) ( textNode) {
	if .DiffMode == diffIdentical {
		 = .WithVerbosity(1)
	} else if .verbosity() < 3 {
		 = .WithVerbosity(3)
	}

	// Check whether we have specialized formatting for this node.
	// This is not necessary, but helpful for producing more readable outputs.
	if .CanFormatDiffSlice() {
		return .FormatDiffSlice()
	}

	var  reflect.Kind
	if .parent != nil && .parent.TransformerName == "" {
		 = .parent.Type.Kind()
	}

	// For leaf nodes, format the value based on the reflect.Values alone.
	// As a special case, treat equal []byte as a leaf nodes.
	 := .Type.Kind() == reflect.Slice && .Type.Elem() == byteType
	 :=  && .NumDiff+.NumIgnored+.NumTransformed == 0
	if .MaxDepth == 0 ||  {
		switch .DiffMode {
		case diffUnknown, diffIdentical:
			// Format Equal.
			if .NumDiff == 0 {
				 := .FormatValue(.ValueX, , )
				 := .FormatValue(.ValueY, , )
				if .NumIgnored > 0 && .NumSame == 0 {
					return textEllipsis
				} else if .Len() < .Len() {
					return 
				} else {
					return 
				}
			}

			// Format unequal.
			assert(.DiffMode == diffUnknown)
			var  textList
			 := .WithTypeMode(elideType).FormatValue(.ValueX, , )
			 := .WithTypeMode(elideType).FormatValue(.ValueY, , )
			for  := 0;  <= maxVerbosityPreset &&  != nil &&  != nil && .Equal(); ++ {
				 := verbosityPreset(, ).WithTypeMode(elideType)
				 = .FormatValue(.ValueX, , )
				 = .FormatValue(.ValueY, , )
			}
			if  != nil {
				 = append(, textRecord{Diff: '-', Value: })
			}
			if  != nil {
				 = append(, textRecord{Diff: '+', Value: })
			}
			return .WithTypeMode(emitType).FormatType(.Type, )
		case diffRemoved:
			return .FormatValue(.ValueX, , )
		case diffInserted:
			return .FormatValue(.ValueY, , )
		default:
			panic("invalid diff mode")
		}
	}

	// Register slice element to support cycle detection.
	if  == reflect.Slice {
		 := .PushPair(.ValueX, .ValueY, .DiffMode, true)
		defer .Pop()
		defer func() {  = wrapTrunkReferences(, ) }()
	}

	// Descend into the child value node.
	if .TransformerName != "" {
		 := .WithTypeMode(emitType).(.Value, )
		 = &textWrap{Prefix: "Inverse(" + .TransformerName + ", ", Value: , Suffix: ")"}
		return .FormatType(.Type, )
	} else {
		switch  := .Type.Kind();  {
		case reflect.Struct, reflect.Array, reflect.Slice:
			 = .formatDiffList(.Records, , )
			 = .FormatType(.Type, )
		case reflect.Map:
			// Register map to support cycle detection.
			 := .PushPair(.ValueX, .ValueY, .DiffMode, false)
			defer .Pop()

			 = .formatDiffList(.Records, , )
			 = wrapTrunkReferences(, )
			 = .FormatType(.Type, )
		case reflect.Ptr:
			// Register pointer to support cycle detection.
			 := .PushPair(.ValueX, .ValueY, .DiffMode, false)
			defer .Pop()

			 = .(.Value, )
			 = wrapTrunkReferences(, )
			 = &textWrap{Prefix: "&", Value: }
		case reflect.Interface:
			 = .WithTypeMode(emitType).(.Value, )
		default:
			panic(fmt.Sprintf("%v cannot have children", ))
		}
		return 
	}
}

func ( formatOptions) ( []reportRecord,  reflect.Kind,  *pointerReferences) textNode {
	// Derive record name based on the data structure kind.
	var  string
	var  func(reflect.Value) string
	switch  {
	case reflect.Struct:
		 = "field"
		 = .WithTypeMode(autoType)
		 = func( reflect.Value) string { return .String() }
	case reflect.Slice, reflect.Array:
		 = "element"
		 = .WithTypeMode(elideType)
		 = func(reflect.Value) string { return "" }
	case reflect.Map:
		 = "entry"
		 = .WithTypeMode(elideType)
		 = func( reflect.Value) string { return formatMapKey(, false, ) }
	}

	 := -1
	if .LimitVerbosity {
		if .DiffMode == diffIdentical {
			 = ((1 << .verbosity()) >> 1) << 2 // 0, 4, 8, 16, 32, etc...
		} else {
			 = (1 << .verbosity()) << 1 // 2, 4, 8, 16, 32, 64, etc...
		}
		.VerbosityLevel--
	}

	// Handle unification.
	switch .DiffMode {
	case diffIdentical, diffRemoved, diffInserted:
		var  textList
		var  bool // Add final "..." to indicate records were dropped
		for ,  := range  {
			if len() ==  {
				 = true
				break
			}

			// Elide struct fields that are zero value.
			if  == reflect.Struct {
				var  bool
				switch .DiffMode {
				case diffIdentical:
					 = .Value.ValueX.IsZero() || .Value.ValueY.IsZero()
				case diffRemoved:
					 = .Value.ValueX.IsZero()
				case diffInserted:
					 = .Value.ValueY.IsZero()
				}
				if  {
					continue
				}
			}
			// Elide ignored nodes.
			if .Value.NumIgnored > 0 && .Value.NumSame+.Value.NumDiff == 0 {
				 = !( == reflect.Slice ||  == reflect.Array)
				if ! {
					.AppendEllipsis(diffStats{})
				}
				continue
			}
			if  := .FormatDiff(.Value, );  != nil {
				 = append(, textRecord{Key: (.Key), Value: })
			}
		}
		if  {
			.AppendEllipsis(diffStats{})
		}
		return &textWrap{Prefix: "{", Value: , Suffix: "}"}
	case diffUnknown:
	default:
		panic("invalid diff mode")
	}

	// Handle differencing.
	var  int
	var  textList
	var  []reflect.Value // invariant: len(list) == len(keys)
	 := coalesceAdjacentRecords(, )
	 := diffStats{Name: }
	for ,  := range  {
		if  >= 0 &&  >=  {
			 = .Append()
			continue
		}

		// Handle equal records.
		if .NumDiff() == 0 {
			// Compute the number of leading and trailing records to print.
			var ,  int
			 := .NumIgnored + .NumIdentical
			for  < numContextRecords && + <  &&  != 0 {
				if  := [].Value; .NumIgnored > 0 && .NumSame+.NumDiff == 0 {
					break
				}
				++
			}
			for  < numContextRecords && + <  &&  != len()-1 {
				if  := [--1].Value; .NumIgnored > 0 && .NumSame+.NumDiff == 0 {
					break
				}
				++
			}
			if -(+) == 1 && .NumIgnored == 0 {
				++ // Avoid pointless coalescing of a single equal record
			}

			// Format the equal values.
			for ,  := range [:] {
				 := .WithDiffMode(diffIdentical).FormatDiff(.Value, )
				 = append(, textRecord{Key: (.Key), Value: })
				 = append(, .Key)
			}
			if  > + {
				.NumIdentical -=  + 
				.AppendEllipsis()
				for len() < len() {
					 = append(, reflect.Value{})
				}
			}
			for ,  := range [- : ] {
				 := .WithDiffMode(diffIdentical).FormatDiff(.Value, )
				 = append(, textRecord{Key: (.Key), Value: })
				 = append(, .Key)
			}
			 = [:]
			continue
		}

		// Handle unequal records.
		for ,  := range [:.NumDiff()] {
			switch {
			case .CanFormatDiffSlice(.Value):
				 := .FormatDiffSlice(.Value)
				 = append(, textRecord{Key: (.Key), Value: })
				 = append(, .Key)
			case .Value.NumChildren == .Value.MaxDepth:
				 := .WithDiffMode(diffRemoved).FormatDiff(.Value, )
				 := .WithDiffMode(diffInserted).FormatDiff(.Value, )
				for  := 0;  <= maxVerbosityPreset &&  != nil &&  != nil && .Equal(); ++ {
					 := verbosityPreset(, )
					 = .WithDiffMode(diffRemoved).FormatDiff(.Value, )
					 = .WithDiffMode(diffInserted).FormatDiff(.Value, )
				}
				if  != nil {
					 = append(, textRecord{Diff: diffRemoved, Key: (.Key), Value: })
					 = append(, .Key)
				}
				if  != nil {
					 = append(, textRecord{Diff: diffInserted, Key: (.Key), Value: })
					 = append(, .Key)
				}
			default:
				 := .FormatDiff(.Value, )
				 = append(, textRecord{Key: (.Key), Value: })
				 = append(, .Key)
			}
		}
		 = [.NumDiff():]
		 += .NumDiff()
	}
	if .IsZero() {
		assert(len() == 0)
	} else {
		.AppendEllipsis()
		for len() < len() {
			 = append(, reflect.Value{})
		}
	}
	assert(len() == len())

	// For maps, the default formatting logic uses fmt.Stringer which may
	// produce ambiguous output. Avoid calling String to disambiguate.
	if  == reflect.Map {
		var  bool
		 := map[string]reflect.Value{}
		for ,  := range  {
			if .IsValid() {
				 := [].Key
				,  := []
				if  && .CanInterface() && .CanInterface() {
					 = .Interface() != .Interface()
					if  {
						break
					}
				}
				[] = 
			}
		}
		if  {
			for ,  := range  {
				if .IsValid() {
					[].Key = formatMapKey(, true, )
				}
			}
		}
	}

	return &textWrap{Prefix: "{", Value: , Suffix: "}"}
}

// coalesceAdjacentRecords coalesces the list of records into groups of
// adjacent equal, or unequal counts.
func coalesceAdjacentRecords( string,  []reportRecord) ( []diffStats) {
	var  int // Arbitrary index into which case last occurred
	 := func( int) *diffStats {
		if  !=  {
			 = append(, diffStats{Name: })
			 = 
		}
		return &[len()-1]
	}
	for ,  := range  {
		switch  := .Value; {
		case .NumIgnored > 0 && .NumSame+.NumDiff == 0:
			(1).NumIgnored++
		case .NumDiff == 0:
			(1).NumIdentical++
		case .NumDiff > 0 && !.ValueY.IsValid():
			(2).NumRemoved++
		case .NumDiff > 0 && !.ValueX.IsValid():
			(2).NumInserted++
		default:
			(2).NumModified++
		}
	}
	return 
}