/*
 * Copyright (c) 2013-2016 Dave Collins <dave@davec.name>
 *
 * Permission to use, copy, modify, and distribute this software for any
 * purpose with or without fee is hereby granted, provided that the above
 * copyright notice and this permission notice appear in all copies.
 *
 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
 */

package spew

import (
	"bytes"
	"fmt"
	"io"
	"reflect"
	"sort"
	"strconv"
	"time"
)

// Numeric formatting constants.
const (
	decimalBase         = 10
	hexBase             = 16
	hexBufSize          = 18 // max uint64 hex (16 digits) + "0x" prefix
	float32Precision    = 32
	float64Precision    = 64
	complex64Precision  = 32 // real/imag each float32
	complex128Precision = 64 // real/imag each float64
)

// Some constants in the form of bytes to avoid string overhead.  This mirrors
// the technique used in the fmt package.
//
//nolint:gochecknoglobals // immutable byte literals used as write constants
var (
	panicBytes            = []byte("(PANIC=")
	plusBytes             = []byte("+")
	iBytes                = []byte("i")
	trueBytes             = []byte("true")
	falseBytes            = []byte("false")
	interfaceBytes        = []byte("(interface {})")
	commaNewlineBytes     = []byte(",\n")
	newlineBytes          = []byte("\n")
	openBraceBytes        = []byte("{")
	openBraceNewlineBytes = []byte("{\n")
	closeBraceBytes       = []byte("}")
	asteriskBytes         = []byte("*")
	colonBytes            = []byte(":")
	colonSpaceBytes       = []byte(": ")
	openParenBytes        = []byte("(")
	closeParenBytes       = []byte(")")
	spaceBytes            = []byte(" ")
	pointerChainBytes     = []byte("->")
	nilAngleBytes         = []byte("<nil>")
	maxNewlineBytes       = []byte("<max depth reached>\n")
	maxShortBytes         = []byte("<max>")
	circularBytes         = []byte("<already shown>")
	circularShortBytes    = []byte("<shown>")
	invalidAngleBytes     = []byte("<invalid>")
	openBracketBytes      = []byte("[")
	closeBracketBytes     = []byte("]")
	percentBytes          = []byte("%")
	precisionBytes        = []byte(".")
	openAngleBytes        = []byte("<")
	closeAngleBytes       = []byte(">")
	openMapBytes          = []byte("map[")
	closeMapBytes         = []byte("]")
	lenEqualsBytes        = []byte("len=")
	capEqualsBytes        = []byte("cap=")
)

// hexDigits is used to map a decimal value to a hex digit.
var hexDigits = "0123456789abcdef" //nolint:gochecknoglobals // immutable lookup table

// catchPanic handles any panics that might occur during the handleMethods
// calls.
func catchPanic(w io.Writer, v reflect.Value) {
	_ = v // currently we do not render the panic value
	if err := recover(); err != nil {
		_, _ = w.Write(panicBytes)
		_, _ = fmt.Fprintf(w, "%v", err)
		_, _ = w.Write(closeParenBytes)
	}
}

// handleMethods attempts to call the Error and String methods on the underlying
// type the passed reflect.Value represents and outputes the result to Writer w.
//
// It handles panics in any called methods by catching and displaying the error
// as the formatted value.
func handleMethods(cs *ConfigState, w io.Writer, v reflect.Value) (handled bool) {
	// We need an interface to check if the type implements the error or
	// Stringer interface.  However, the reflect package won't give us an
	// interface on certain things like unexported struct fields in order
	// to enforce visibility rules.  We use unsafe, when it's available,
	// to bypass these restrictions since this package does not mutate the
	// values.
	if !v.CanInterface() {
		if UnsafeDisabled {
			return false
		}

		v = unsafeReflectValue(v)
	}

	defer catchPanic(w, v)
	handled, continued := handleErrorOrStringer(cs, w, v)
	if handled {
		// short-circuit: if we can handle directly without trying to convert to a pointer receiver, we're done.
		// This allows avoiding to call unsafeReflectValue() or retrieving the value's address when not necessary.
		return true
	}
	if continued {
		// printed, and wants to return now to continue digging
		return false
	}

	// Choose whether or not to do error and Stringer interface lookups against
	// the base type or a pointer to the base type depending on settings.
	//
	// Technically calling one of these methods with a pointer receiver can
	// mutate the value, however, types which choose to satisfy an error or
	// Stringer interface with a pointer receiver should not be mutating their
	// state inside these interface methods.
	if !cs.DisablePointerMethods && !UnsafeDisabled && !v.CanAddr() {
		// since this is unsafe, there are a few edge cases where it doesn't work well
		v = unsafeReflectValue(v)
	}

	if v.CanAddr() {
		v = v.Addr()
	}

	handled, _ = handleErrorOrStringer(cs, w, v)

	return handled
}

// handleErrorOrString is only called when v.CanInterface().
//
// NOTE: we should prove that unsafReflectValue doesn't alter this property.
func handleErrorOrStringer(cs *ConfigState, w io.Writer, v reflect.Value) (handled, continued bool) {
	// Is it an error or Stringer?
	switch iface := v.Interface().(type) {
	case error:
		if cs.ContinueOnMethod {
			_, _ = w.Write(openParenBytes)
			_, _ = w.Write([]byte(iface.Error()))
			_, _ = w.Write(closeParenBytes)
			_, _ = w.Write(spaceBytes)
			return false, true
		}

		_, _ = w.Write([]byte(iface.Error()))
		return true, false

	case fmt.Stringer:
		if cs.ContinueOnMethod {
			_, _ = w.Write(openParenBytes)
			_, _ = w.Write([]byte(iface.String()))
			_, _ = w.Write(closeParenBytes)
			_, _ = w.Write(spaceBytes)
			return false, true
		}

		_, _ = w.Write([]byte(iface.String()))
		return true, false

	default:
		// is it convertible to time.Time (or *time.Time)?
		converted, ok := isConvertibleToTime(v)
		if !ok {
			// can't handle this value
			return false, false
		}

		// rendering time.Time
		if !converted.CanInterface() {
			return false, false // safeguard: should never be the case
		}

		timeIface := converted.Interface()
		stringer, ok := timeIface.(fmt.Stringer)
		if !ok {
			return false, false // safeguard: should never be the case
		}

		if cs.ContinueOnMethod {
			_, _ = w.Write(openParenBytes)
			_, _ = w.Write([]byte(stringer.String()))
			_, _ = w.Write(closeParenBytes)
			_, _ = w.Write(spaceBytes)
			return false, true
		}

		_, _ = w.Write([]byte(stringer.String()))

		return true, false
	}
}

// printBool outputs a boolean value as true or false to Writer w.
func printBool(w io.Writer, val bool) {
	if val {
		_, _ = w.Write(trueBytes)
	} else {
		_, _ = w.Write(falseBytes)
	}
}

// printInt outputs a signed integer value to Writer w.
func printInt(w io.Writer, val int64, base int) { //nolint: unparam  // we leave base even though it is alway 10, to remain consistent with FormatInt
	_, _ = w.Write([]byte(strconv.FormatInt(val, base)))
}

// printUint outputs an unsigned integer value to Writer w.
func printUint(w io.Writer, val uint64, base int) {
	_, _ = w.Write([]byte(strconv.FormatUint(val, base)))
}

// printFloat outputs a floating point value using the specified precision,
// which is expected to be 32 or 64bit, to Writer w.
func printFloat(w io.Writer, val float64, precision int) {
	_, _ = w.Write([]byte(strconv.FormatFloat(val, 'g', -1, precision)))
}

// printComplex outputs a complex value using the specified float precision
// for the real and imaginary parts to Writer w.
func printComplex(w io.Writer, c complex128, floatPrecision int) {
	r := real(c)
	_, _ = w.Write(openParenBytes)
	_, _ = w.Write([]byte(strconv.FormatFloat(r, 'g', -1, floatPrecision)))
	i := imag(c)
	if i >= 0 {
		_, _ = w.Write(plusBytes)
	}
	_, _ = w.Write([]byte(strconv.FormatFloat(i, 'g', -1, floatPrecision)))
	_, _ = w.Write(iBytes)
	_, _ = w.Write(closeParenBytes)
}

// printHexPtr outputs a uintptr formatted as hexadecimal with a leading '0x'
// prefix to Writer w.
func printHexPtr(w io.Writer, p uintptr) {
	// Null pointer.
	num := uint64(p)
	if num == 0 {
		_, _ = w.Write(nilAngleBytes)
		return
	}

	// Max uint64 is 16 bytes in hex + 2 bytes for '0x' prefix
	buf := make([]byte, hexBufSize)

	// It's simpler to construct the hex string right to left.
	base := uint64(hexBase)
	i := len(buf) - 1
	for num >= base {
		buf[i] = hexDigits[num%base]
		num /= base
		i--
	}
	buf[i] = hexDigits[num]

	// Add '0x' prefix.
	i--
	buf[i] = 'x'
	i--
	buf[i] = '0'

	// Strip unused leading bytes.
	buf = buf[i:]
	_, _ = w.Write(buf)
}

// tryHandleMethods checks whether the value should be handled by its
// Stringer/error methods and invokes them if so. Returns true if the value
// was handled.
func tryHandleMethods(cs *ConfigState, w io.Writer, v reflect.Value, kind reflect.Kind) bool {
	if cs.DisableMethods && (!cs.EnableTimeStringer || !isTime(v, 0)) {
		return false
	}
	if kind == reflect.Invalid || kind == reflect.Interface {
		return false
	}
	return handleMethods(cs, w, v)
}

// ptrResolution holds the result of walking a pointer chain.
type ptrResolution struct {
	value        reflect.Value
	pointerChain []uintptr
	indirects    int
	nilFound     bool
	cycleFound   bool
}

// resolvePtr walks a pointer chain, dereferencing pointers and unpacking
// interfaces while detecting circular references. It returns the final
// resolved value along with metadata about the chain.
func resolvePtr(v reflect.Value, depth int, pointers map[uintptr]int) ptrResolution {
	r := ptrResolution{value: v}

	for r.value.Kind() == reflect.Pointer {
		if r.value.IsNil() {
			r.nilFound = true
			return r
		}

		r.indirects++
		addr := r.value.Pointer()
		r.pointerChain = append(r.pointerChain, addr)
		if pd, ok := pointers[addr]; ok && pd < depth {
			r.cycleFound = true
			r.indirects--
			return r
		}
		pointers[addr] = depth

		r.value = r.value.Elem()
		if r.value.Kind() == reflect.Interface {
			if done := r.unpackInterface(depth, pointers); done {
				return r
			}
		}
	}

	return r
}

// unpackInterface unpacks an interface value found during pointer resolution.
// It returns true if the resolution is complete (nil or cycle found).
func (r *ptrResolution) unpackInterface(depth int, pointers map[uintptr]int) bool {
	if r.value.IsNil() {
		r.nilFound = true
		return true
	}
	r.value = r.value.Elem()

	if r.value.Kind() != reflect.Pointer {
		return false
	}
	if r.value.IsNil() {
		r.nilFound = true
		return true
	}
	addr := r.value.Pointer()
	if pd, ok := pointers[addr]; ok && pd <= depth {
		r.cycleFound = true
		r.indirects--
		return true
	}
	pointers[addr] = depth
	return false
}

// valuesSorter implements sort.Interface to allow a slice of reflect.Value
// elements to be sorted.
type valuesSorter struct {
	values  []reflect.Value
	strings []string // either nil or same len and values
	cs      *ConfigState
}

// newValuesSorter initializes a valuesSorter instance, which holds a set of
// surrogate keys on which the data should be sorted.  It uses flags in
// ConfigState to decide if and how to populate those surrogate keys.
//
// Values that are convertible to a time.Time are compared using [time.Time.Compare()].
// This is safer than sorting their string representation, because the [time.Location]
// may differ.
//
// NOTE: if all values are not of the same underlying type,
// comparison will resort to the default reflect.Value.String() representation.
func newValuesSorter(values []reflect.Value, cs *ConfigState) sort.Interface {
	vs := &valuesSorter{values: values, cs: cs}
	v0 := vs.values[0]
	if canSortSimply(v0.Kind()) || isTime(v0, 0) {
		return vs
	}

	if !vs.cs.DisableMethods {
		vs.strings = make([]string, len(values))
		for i := range vs.values {
			b := bytes.Buffer{}
			if !handleMethods(cs, &b, vs.values[i]) {
				vs.strings = nil
				break
			}
			vs.strings[i] = b.String()
		}
	}

	if vs.strings == nil && cs.SpewKeys {
		vs.strings = make([]string, len(values))
		for i := range vs.values {
			vs.strings[i] = Sprintf("%#v", vs.values[i].Interface())
		}
	}

	return vs
}

// canSortSimply tests whether a reflect.Kind is a primitive that can be sorted
// directly, or whether it should be considered for sorting by surrogate keys
// (if the ConfigState allows it).
func canSortSimply(kind reflect.Kind) bool {
	// This switch parallels valueSortLess, except for the default case.
	switch kind {
	case reflect.Bool:
		return true
	case reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64, reflect.Int:
		return true
	case reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uint:
		return true
	case reflect.Float32, reflect.Float64:
		return true
	case reflect.String:
		return true
	case reflect.Uintptr:
		return true
	case reflect.Array:
		return true
	default:
		return false
	}
}

// Len returns the number of values in the slice.  It is part of the
// sort.Interface implementation.
func (s *valuesSorter) Len() int {
	return len(s.values)
}

// Swap swaps the values at the passed indices.  It is part of the
// sort.Interface implementation.
func (s *valuesSorter) Swap(i, j int) {
	s.values[i], s.values[j] = s.values[j], s.values[i]
	if s.strings != nil {
		s.strings[i], s.strings[j] = s.strings[j], s.strings[i]
	}
}

// Less returns whether the value at index i should sort before the
// value at index j.  It is part of the sort.Interface implementation.
func (s *valuesSorter) Less(i, j int) bool {
	if s.strings == nil {
		return valueSortLess(s.values[i], s.values[j])
	}
	return s.strings[i] < s.strings[j]
}

// valueSortLess returns whether the first value should sort before the second value.
//
// It is used by valueSorter.Less as part of the sort.Interface implementation.
func valueSortLess(a, b reflect.Value) bool {
	switch a.Kind() {
	case reflect.Bool:
		return !a.Bool() && b.Bool()
	case reflect.Int8, reflect.Int16, reflect.Int32, reflect.Int64, reflect.Int:
		return a.Int() < b.Int()
	case reflect.Uint8, reflect.Uint16, reflect.Uint32, reflect.Uint64, reflect.Uint:
		return a.Uint() < b.Uint()
	case reflect.Float32, reflect.Float64:
		return a.Float() < b.Float()
	case reflect.String:
		return a.String() < b.String()
	case reflect.Uintptr:
		return a.Uint() < b.Uint()
	case reflect.Array:
		// Compare the contents of both arrays.
		l := a.Len()
		for i := range l {
			av := a.Index(i)
			bv := b.Index(i)

			if !av.CanInterface() || !bv.CanInterface() {
				// Unexported fields would panic on Interface() call.
				continue
			}

			if av.Interface() == bv.Interface() {
				continue
			}
			return valueSortLess(av, bv)
		}
		fallthrough
	default:
		isTimeA := isTime(a, 0)
		isTimeB := isTime(b, 0)
		if !isTimeA || !isTimeB {
			return a.String() < b.String()
		}

		return timeLess(a, b)
	}
}

// timeLess compare two values that convert to a time.Time.
//
// This handles nil values gracefully.
func timeLess(a, b reflect.Value) bool {
	convertedA, okForA := isConvertibleToTime(a)
	convertedB, okForB := isConvertibleToTime(b)
	if !okForA || !okForB {
		// types can convert, but not values: this means we have at least one nil
		if !okForA { // a =< b because nil =< (any value)
			return true
		}

		return false // b > a
	}

	// time comparison: we need to retrieve the time.Time values from a chain of pointers
	for convertedA.Kind() == reflect.Pointer && convertedA.IsValid() {
		convertedA = reflect.Indirect(convertedA)
	}
	for convertedB.Kind() == reflect.Pointer && convertedB.IsValid() {
		convertedB = reflect.Indirect(convertedB)
	}

	// handle the case when some values are nil, after resolving pointers
	switch {
	case !convertedA.IsValid(): // nil <= (any value)
		return true
	case !convertedB.IsValid(): // (valid) > nil
		return false
	}

	okIfaceA := convertedA.CanInterface()
	okIfaceB := convertedB.CanInterface()

	if !okIfaceA || !okIfaceB {
		// defensive safeguard (should never get there, since we have successfully converted)
		return a.String() < b.String()
	}

	tA, okTimeA := reflect.TypeAssert[time.Time](convertedA)
	tB, okTimeB := reflect.TypeAssert[time.Time](convertedB)

	if !okTimeA || !okTimeB {
		// defensive safeguard (should never get there, since we have successfully indirected and converted)
		return a.String() < b.String()
	}

	return tA.Compare(tB) < 0
}

// sortValues is a sort function that handles both native types and any type that
// can be converted to error or Stringer.  Other inputs are sorted according to
// their Value.String() value to ensure display stability.
func sortValues(values []reflect.Value, cs *ConfigState) {
	if len(values) == 0 {
		return
	}
	sort.Sort(newValuesSorter(values, cs))
}