// 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.md file.

package cmp

import (

	"fmt"

	"reflect"

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

)

// TODO: Enforce limits?

//	* Enforce maximum number of records to print per node?

//	* Enforce maximum size in bytes allowed?

//	* As a heuristic, use less verbosity for equal nodes than unequal nodes.

// TODO: Enforce unique outputs?

//	* Avoid Stringer methods if it results in same output?

//	* Print pointer address if outputs still equal?

// 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 (opts formatOptions) WithDiffMode(d diffMode) formatOptions {

	opts.DiffMode = d

	return opts

}

func (opts formatOptions) WithTypeMode(t typeMode) formatOptions {

	opts.TypeMode = t

	return opts

}

// FormatDiff converts a valueNode tree into a textNode tree, where the later

// is a textual representation of the differences detected in the former.

func (opts formatOptions) FormatDiff(v *valueNode) textNode {

	// Check whether we have specialized formatting for this node.

	// This is not necessary, but helpful for producing more readable outputs.

	if opts.CanFormatDiffSlice(v) {

		return opts.FormatDiffSlice(v)

	}

	// For leaf nodes, format the value based on the reflect.Values alone.

	if v.MaxDepth == 0 {

		switch opts.DiffMode {

		case diffUnknown, diffIdentical:

			// Format Equal.

			if v.NumDiff == 0 {

				outx := opts.FormatValue(v.ValueX, visitedPointers{})

				outy := opts.FormatValue(v.ValueY, visitedPointers{})

				if v.NumIgnored > 0 && v.NumSame == 0 {

					return textEllipsis

				} else if outx.Len() < outy.Len() {

					return outx

				} else {

					return outy

				}

			}

			// Format unequal.

			assert(opts.DiffMode == diffUnknown)

			var list textList

			outx := opts.WithTypeMode(elideType).FormatValue(v.ValueX, visitedPointers{})

			outy := opts.WithTypeMode(elideType).FormatValue(v.ValueY, visitedPointers{})

			if outx != nil {

				list = append(list, textRecord{Diff: '-', Value: outx})

			}

			if outy != nil {

				list = append(list, textRecord{Diff: '+', Value: outy})

			}

			return opts.WithTypeMode(emitType).FormatType(v.Type, list)

		case diffRemoved:

			return opts.FormatValue(v.ValueX, visitedPointers{})

		case diffInserted:

			return opts.FormatValue(v.ValueY, visitedPointers{})

		default:

			panic("invalid diff mode")

		}

	}

	// Descend into the child value node.

	if v.TransformerName != "" {

		out := opts.WithTypeMode(emitType).FormatDiff(v.Value)

		out = textWrap{"Inverse(" + v.TransformerName + ", ", out, ")"}

		return opts.FormatType(v.Type, out)

	} else {

		switch k := v.Type.Kind(); k {

		case reflect.Struct, reflect.Array, reflect.Slice, reflect.Map:

			return opts.FormatType(v.Type, opts.formatDiffList(v.Records, k))

		case reflect.Ptr:

			return textWrap{"&", opts.FormatDiff(v.Value), ""}

		case reflect.Interface:

			return opts.WithTypeMode(emitType).FormatDiff(v.Value)

		default:

			panic(fmt.Sprintf("%v cannot have children", k))

		}

	}

}

func (opts formatOptions) formatDiffList(recs []reportRecord, k reflect.Kind) textNode {

	// Derive record name based on the data structure kind.

	var name string

	var formatKey func(reflect.Value) string

	switch k {

	case reflect.Struct:

		name = "field"

		opts = opts.WithTypeMode(autoType)

		formatKey = func(v reflect.Value) string { return v.String() }

	case reflect.Slice, reflect.Array:

		name = "element"

		opts = opts.WithTypeMode(elideType)

		formatKey = func(reflect.Value) string { return "" }

	case reflect.Map:

		name = "entry"

		opts = opts.WithTypeMode(elideType)

		formatKey = formatMapKey

	}

	// Handle unification.

	switch opts.DiffMode {

	case diffIdentical, diffRemoved, diffInserted:

		var list textList

		var deferredEllipsis bool // Add final "..." to indicate records were dropped

		for _, r := range recs {

			// Elide struct fields that are zero value.

			if k == reflect.Struct {

				var isZero bool

				switch opts.DiffMode {

				case diffIdentical:

					isZero = value.IsZero(r.Value.ValueX) || value.IsZero(r.Value.ValueY)

				case diffRemoved:

					isZero = value.IsZero(r.Value.ValueX)

				case diffInserted:

					isZero = value.IsZero(r.Value.ValueY)

				}

				if isZero {

					continue

				}

			}

			// Elide ignored nodes.

			if r.Value.NumIgnored > 0 && r.Value.NumSame+r.Value.NumDiff == 0 {

				deferredEllipsis = !(k == reflect.Slice || k == reflect.Array)

				if !deferredEllipsis {

					list.AppendEllipsis(diffStats{})

				}

				continue

			}

			if out := opts.FormatDiff(r.Value); out != nil {

				list = append(list, textRecord{Key: formatKey(r.Key), Value: out})

			}

		}

		if deferredEllipsis {

			list.AppendEllipsis(diffStats{})

		}

		return textWrap{"{", list, "}"}

	case diffUnknown:

	default:

		panic("invalid diff mode")

	}

	// Handle differencing.

	var list textList

	groups := coalesceAdjacentRecords(name, recs)

	for i, ds := range groups {

		// Handle equal records.

		if ds.NumDiff() == 0 {

			// Compute the number of leading and trailing records to print.

			var numLo, numHi int

			numEqual := ds.NumIgnored + ds.NumIdentical

			for numLo < numContextRecords && numLo+numHi < numEqual && i != 0 {

				if r := recs[numLo].Value; r.NumIgnored > 0 && r.NumSame+r.NumDiff == 0 {

					break

				}

				numLo++

			}

			for numHi < numContextRecords && numLo+numHi < numEqual && i != len(groups)-1 {

				if r := recs[numEqual-numHi-1].Value; r.NumIgnored > 0 && r.NumSame+r.NumDiff == 0 {

					break

				}

				numHi++

			}

			if numEqual-(numLo+numHi) == 1 && ds.NumIgnored == 0 {

				numHi++ // Avoid pointless coalescing of a single equal record

			}

			// Format the equal values.

			for _, r := range recs[:numLo] {

				out := opts.WithDiffMode(diffIdentical).FormatDiff(r.Value)

				list = append(list, textRecord{Key: formatKey(r.Key), Value: out})

			}

			if numEqual > numLo+numHi {

				ds.NumIdentical -= numLo + numHi

				list.AppendEllipsis(ds)

			}

			for _, r := range recs[numEqual-numHi : numEqual] {

				out := opts.WithDiffMode(diffIdentical).FormatDiff(r.Value)

				list = append(list, textRecord{Key: formatKey(r.Key), Value: out})

			}

			recs = recs[numEqual:]

			continue

		}

		// Handle unequal records.

		for _, r := range recs[:ds.NumDiff()] {

			switch {

			case opts.CanFormatDiffSlice(r.Value):

				out := opts.FormatDiffSlice(r.Value)

				list = append(list, textRecord{Key: formatKey(r.Key), Value: out})

			case r.Value.NumChildren == r.Value.MaxDepth:

				outx := opts.WithDiffMode(diffRemoved).FormatDiff(r.Value)

				outy := opts.WithDiffMode(diffInserted).FormatDiff(r.Value)

				if outx != nil {

					list = append(list, textRecord{Diff: diffRemoved, Key: formatKey(r.Key), Value: outx})

				}

				if outy != nil {

					list = append(list, textRecord{Diff: diffInserted, Key: formatKey(r.Key), Value: outy})

				}

			default:

				out := opts.FormatDiff(r.Value)

				list = append(list, textRecord{Key: formatKey(r.Key), Value: out})

			}

		}

		recs = recs[ds.NumDiff():]

	}

	assert(len(recs) == 0)

	return textWrap{"{", list, "}"}

}

// coalesceAdjacentRecords coalesces the list of records into groups of

// adjacent equal, or unequal counts.

func coalesceAdjacentRecords(name string, recs []reportRecord) (groups []diffStats) {

	var prevCase int // Arbitrary index into which case last occurred

	lastStats := func(i int) *diffStats {

		if prevCase != i {

			groups = append(groups, diffStats{Name: name})

			prevCase = i

		}

		return &groups[len(groups)-1]

	}

	for _, r := range recs {

		switch rv := r.Value; {

		case rv.NumIgnored > 0 && rv.NumSame+rv.NumDiff == 0:

			lastStats(1).NumIgnored++

		case rv.NumDiff == 0:

			lastStats(1).NumIdentical++

		case rv.NumDiff > 0 && !rv.ValueY.IsValid():

			lastStats(2).NumRemoved++

		case rv.NumDiff > 0 && !rv.ValueX.IsValid():

			lastStats(2).NumInserted++

		default:

			lastStats(2).NumModified++

		}

	}

	return groups

}