assert: add smart implementation for func Equal

4 files changed, 413 insertions, 5 deletions

diff --git a/assert/equal.go b/assert/equal.go
index 1222ecf..122520b 100644
--- a/assert/equal.go
+++ b/assert/equal.go
@@ -3,14 +3,235 @@
 
 package assert
 
-import "reflect"
+import (
+	"fmt"
+	"reflect"
+	"slices"
+
+	"go.xyrillian.de/gg/internal/path"
+)
 
 // Equal checks whether both supplied values are equal according to the rules of [reflect.DeepEqual].
+//
+// If there is a difference within a structured data type,
+// this function will try to be smart about reporting only the most specific pieces that differ,
+// but this is done on a best-effort basis.
+// The error messages produced by this assertion should be expected to change between releases
+// as additional effort is expended to establish a new level of best effort.
 func Equal[V any](t TestingTB, actual, expected V) bool {
 	if reflect.DeepEqual(actual, expected) {
 		return true
 	}
 	t.Helper()
-	t.Errorf("expected %#v, but got %#v", expected, actual)
+
+	// NOTE: consider the warning in the docstring of [path.Path]
+	p := path.NewPath()
+	result := findInequalities(p, reflect.ValueOf(actual), reflect.ValueOf(expected))
+
+	// serialize results into strings first in order to print in sorted order (for deterministic behavior in this package's own tests)
+	errors := make([]string, len(result))
+	for idx, ineq := range result {
+		if ineq.Pointer == "actual" {
+			errors[idx] = fmt.Sprintf("expected %s, but got %s", ineq.Expected, ineq.Actual)
+		} else {
+			errors[idx] = fmt.Sprintf("at %s: expected %s, but got %s", ineq.Pointer, ineq.Expected, ineq.Actual)
+		}
+	}
+	slices.Sort(errors)
+	for _, err := range errors {
+		t.Error(err)
+	}
+
 	return false
 }
+
+// NOTE: Several notes on the implementation of Equal().
+//
+// - All findInequalities...() functions assume that `actual` and `expected` are definitely unequal,
+//   and so may only be called if reflect.Equal() on these same arguments has returned false.
+//
+// - All findInequalities...() functions further assume that `actual.Type() == expected.Type()`.
+//   This is ensured at the API boundary through the type signature of assert.Equal(),
+//   and then only needs to be re-established when recursing into values of kind Interface.
+//
+// - When nonempty diffs are generated, running a full DeepEqual() at each level is indeed extremely inefficient.
+//   However, reflect.DeepEqual() is more likely to handle bizarre corner cases
+//   and new type system features better than our implementation,
+//   so we rely on it as a source of ground truth.
+//
+//   Furthermore, in the vastly more important case of an empty diff (i.e. a passing test),
+//   reflect.DeepEqual() is likely to be more efficient than what we do because of
+//   having both been around and scrutinized for much longer than our implementation,
+//   so doing it first will usually be faster.
+
+type inequality struct {
+	Pointer  string
+	Actual   string
+	Expected string
+}
+
+func formatValue(v reflect.Value) string {
+	return fmt.Sprintf("%#v", v)
+}
+
+func findInequalities(p path.Path, actual, expected reflect.Value) (result []inequality) {
+	// try to recurse into structured type to find the specific location of the inequality
+	// (thus producing a more succinct error message esp. with large and deeply nested structures)
+	switch actual.Kind() { //nolint:exhaustive
+	case reflect.Array, reflect.Slice:
+		result = findInequalitiesInArrayOrSlice(p, actual, expected)
+	case reflect.Map:
+		result = findInequalitiesInMap(p, actual, expected)
+	case reflect.Struct:
+		result = findInequalitiesInStruct(p, actual, expected)
+	case reflect.Pointer:
+		result = findInequalitiesInPointer(p, actual, expected)
+	case reflect.Interface:
+		if !actual.IsNil() && !expected.IsNil() {
+			// can only recurse if the invariant of this function is upheld: both sides must be of equal types
+			actualElem := actual.Elem()
+			expectedElem := expected.Elem()
+			if actualElem.Type() == expectedElem.Type() {
+				subpath := append(p, path.TypeCastElement(fmt.Sprintf("%T", actualElem.Interface())))
+				result = findInequalities(subpath, actualElem, expectedElem)
+			}
+		}
+	}
+
+	// if we do not have a recursion method for the type in question,
+	// or if our own implementation somehow fails to find the inequality,
+	// the safe fallback is to report the entire value as unequal
+	if len(result) == 0 {
+		return []inequality{{p.AsGoExpression("actual"), formatValue(actual), formatValue(expected)}}
+	}
+	return result
+}
+
+func findInequalitiesInArrayOrSlice(p path.Path, actual, expected reflect.Value) (result []inequality) {
+	// recurse into all elements
+	for idx := range max(actual.Len(), expected.Len()) {
+		subpath := append(p, path.IndexElement(idx))
+		switch {
+		case idx >= actual.Len():
+			result = append(result, inequality{
+				Pointer:  subpath.AsGoExpression("actual"),
+				Actual:   "<missing>",
+				Expected: formatValue(expected.Index(idx)),
+			})
+		case idx >= expected.Len():
+			result = append(result, inequality{
+				Pointer:  subpath.AsGoExpression("actual"),
+				Actual:   formatValue(actual.Index(idx)),
+				Expected: "<missing>",
+			})
+		default:
+			actualElem := actual.Index(idx)
+			expectedElem := expected.Index(idx)
+			if !reflect.DeepEqual(actualElem.Interface(), expectedElem.Interface()) {
+				result = append(result, findInequalities(subpath, actualElem, expectedElem)...)
+			}
+		}
+	}
+
+	// if multiple elements differ, check if reporting the whole slice as different is more compact
+	// (this helps with slices of simple types, e.g. []int,
+	// but will not be used for large records where only a single field differs in all of them)
+	if len(result) > 4 {
+		overallTextLength := 0
+		for _, ineq := range result {
+			overallTextLength += len(ineq.Pointer) + len(ineq.Actual) + len(ineq.Expected)
+		}
+		ineq := inequality{
+			Pointer:  p.AsGoExpression("actual"),
+			Actual:   formatValue(actual),
+			Expected: formatValue(expected),
+		}
+		if len(ineq.Pointer)+len(ineq.Actual)+len(ineq.Expected) < overallTextLength {
+			return []inequality{ineq}
+		}
+	}
+
+	return result
+}
+
+func findInequalitiesInMap(p path.Path, actual, expected reflect.Value) (result []inequality) {
+	// recurse into all keys of `actual`
+	iter := actual.MapRange()
+	for iter.Next() {
+		key, actualElem := iter.Key(), iter.Value()
+		subpath := append(p, path.MapKeyElement(key.Interface()))
+		expectedElem := expected.MapIndex(key)
+		if expectedElem.IsValid() {
+			if !reflect.DeepEqual(actualElem.Interface(), expectedElem.Interface()) {
+				result = append(result, findInequalities(subpath, actualElem, expectedElem)...)
+			}
+		} else {
+			result = append(result, inequality{
+				Pointer:  subpath.AsGoExpression("actual"),
+				Actual:   formatValue(actualElem),
+				Expected: "<missing>",
+			})
+		}
+	}
+
+	// recurse into all keys of `expected` (but consider only those missing in `actual` to avoid duplicate reports)
+	iter = expected.MapRange()
+	for iter.Next() {
+		key, expectedElem := iter.Key(), iter.Value()
+		subpath := append(p, path.MapKeyElement(key.Interface()))
+		if !actual.MapIndex(key).IsValid() {
+			result = append(result, inequality{
+				Pointer:  subpath.AsGoExpression("actual"),
+				Actual:   "<missing>",
+				Expected: formatValue(expectedElem),
+			})
+		}
+	}
+
+	return result
+}
+
+func findInequalitiesInStruct(p path.Path, actual, expected reflect.Value) (result []inequality) {
+	// recurse into all addressable fields
+	//
+	// If only values in unexported fields differ, this function will return nothing,
+	// but that's fine because of the fallback behavior in findInequalities().
+	for field := range actual.Type().Fields() {
+		if !field.IsExported() {
+			continue
+		}
+		subpath := append(p, path.KeyElement(field.Name))
+		actualElem := actual.FieldByIndex(field.Index)
+		expectedElem := expected.FieldByIndex(field.Index)
+		if !reflect.DeepEqual(actualElem.Interface(), expectedElem.Interface()) {
+			result = append(result, findInequalities(subpath, actualElem, expectedElem)...)
+		}
+	}
+	return result
+}
+
+func findInequalitiesInPointer(p path.Path, actual, expected reflect.Value) []inequality {
+	if actual.IsNil() {
+		if expected.IsNil() {
+			// defense in depth: should not be reachable -> use the fallback behavior in findInequalities()
+			return nil
+		} else {
+			return []inequality{{
+				Pointer:  p.AsGoExpression("actual"),
+				Actual:   "nil",
+				Expected: "pointer to " + formatValue(expected.Elem()),
+			}}
+		}
+	} else {
+		if expected.IsNil() {
+			return []inequality{{
+				Pointer:  p.AsGoExpression("actual"),
+				Actual:   "pointer to " + formatValue(actual.Elem()),
+				Expected: "nil",
+			}}
+		} else {
+			subpath := append(p, path.DereferenceElement())
+			return findInequalities(subpath, actual.Elem(), expected.Elem())
+		}
+	}
+}
diff --git a/assert/equal_test.go b/assert/equal_test.go
index c710cea..f325916 100644
--- a/assert/equal_test.go
+++ b/assert/equal_test.go
@@ -24,8 +24,143 @@ func expectErrors(t *testing.T, test func(assert.TestingTB), expected string) {
 }
 
 func TestEqual(t *testing.T) {
+	// basic test for scalars
 	assert.Equal(t, true, true)
 	expectErrors(t, func(t assert.TestingTB) {
 		assert.Equal(t, false, true)
 	}, `expected true, but got false`)
+
+	// basic test for slices
+	correctSlice := []int{1, 2, 3}
+	wrongSlice := []int{1, 42, 3}
+	assert.Equal(t, correctSlice, correctSlice)
+	expectErrors(t, func(t assert.TestingTB) {
+		assert.Equal(t, wrongSlice, correctSlice)
+	}, `at actual[1]: expected 2, but got 42`)
+
+	// slices: report the entire slice if it comes out more compact than reporting each different element
+	expectErrors(t, func(t assert.TestingTB) {
+		var (
+			expected = []int{1, 2, 3, 4, 5, 6, 7, 8}
+			actual   = []int{2, 3, 4, 5, 6, 7, 8, 9}
+		)
+		assert.Equal(t, actual, expected)
+	}, `expected []int{1, 2, 3, 4, 5, 6, 7, 8}, but got []int{2, 3, 4, 5, 6, 7, 8, 9}`)
+	expectErrors(t, func(t assert.TestingTB) {
+		var (
+			expected = make([]map[string]int, 6)
+			actual   = make([]map[string]int, 6)
+		)
+		for idx := range expected {
+			expected[idx] = map[string]int{"foo": 1 + idx, "bar": 2 + idx}
+			actual[idx] = map[string]int{"foo": 1 + idx, "bar": 3 + idx}
+		}
+		assert.Equal(t, actual, expected)
+	}, `
+		at actual[0]["bar"]: expected 2, but got 3
+		at actual[1]["bar"]: expected 3, but got 4
+		at actual[2]["bar"]: expected 4, but got 5
+		at actual[3]["bar"]: expected 5, but got 6
+		at actual[4]["bar"]: expected 6, but got 7
+		at actual[5]["bar"]: expected 7, but got 8
+	`)
+
+	// basic test for maps
+	correctMap := map[string]int{
+		"one":   1,
+		"two":   2,
+		"three": 3,
+	}
+	wrongMap := map[string]int{
+		"one":  1,
+		"two":  23,
+		"four": 4,
+	}
+	assert.Equal(t, correctMap, correctMap)
+	expectErrors(t, func(t assert.TestingTB) {
+		assert.Equal(t, wrongMap, correctMap)
+	}, `
+		at actual["four"]: expected <missing>, but got 4
+		at actual["three"]: expected 3, but got <missing>
+		at actual["two"]: expected 2, but got 23
+	`)
+
+	// basic test for structs
+	type record struct {
+		ID      int
+		Name    string
+		private bool
+	}
+	correctStruct := record{1, "Alice", false}
+	wrongStruct1 := record{2, "Bob", false}
+	assert.Equal(t, correctStruct, correctStruct)
+	expectErrors(t, func(t assert.TestingTB) {
+		assert.Equal(t, wrongStruct1, correctStruct)
+	}, `
+		at actual.ID: expected 1, but got 2
+		at actual.Name: expected "Alice", but got "Bob"
+	`)
+
+	// test for structs: diff in private field (we cannot Interface() the values in such fields, so we have to report the entire struct)
+	wrongStruct2 := record{1, "Alice", true}
+	expectErrors(t, func(t assert.TestingTB) {
+		assert.Equal(t, wrongStruct2, correctStruct)
+	}, `expected assert_test.record{ID:1, Name:"Alice", private:false}, but got assert_test.record{ID:1, Name:"Alice", private:true}`)
+
+	// basic test for pointers
+	assert.Equal(t, (*bool)(nil), (*bool)(nil))
+	assert.Equal(t, new(true), new(true))
+	expectErrors(t, func(t assert.TestingTB) {
+		assert.Equal(t, new(false), new(true))
+	}, `at (*actual): expected true, but got false`)
+	expectErrors(t, func(t assert.TestingTB) {
+		assert.Equal(t, nil, new(true))
+	}, `expected pointer to true, but got nil`)
+	expectErrors(t, func(t assert.TestingTB) {
+		assert.Equal(t, new(false), nil)
+	}, `expected nil, but got pointer to false`)
+
+	// basic test for interfaces
+	type slot struct {
+		Value any
+	}
+	correctSlot := slot{[]int{1, 2, 3}}
+	wrongSlot := slot{[]int{1, 42, 3}}
+	mistypedSlot := slot{42}
+	assert.Equal(t, correctSlot, correctSlot)
+	expectErrors(t, func(t assert.TestingTB) {
+		assert.Equal(t, wrongSlot, correctSlot)
+	}, `at actual.Value.([]int)[1]: expected 2, but got 42`)
+	expectErrors(t, func(t assert.TestingTB) {
+		assert.Equal(t, mistypedSlot, correctSlot)
+	}, `at actual.Value: expected []int{1, 2, 3}, but got 42`)
+
+	// check that derefences are elided from reported paths, but only if possible
+	expectErrors(t, func(t assert.TestingTB) {
+		var (
+			expected = map[string]*[]int{"foo": {1, 2, 3}}
+			actual   = map[string]*[]int{"foo": {1, 42, 3}}
+		)
+		assert.Equal(t, actual, expected)
+	}, `at (*actual["foo"])[1]: expected 2, but got 42`)
+	expectErrors(t, func(t assert.TestingTB) {
+		var (
+			expected = []*map[string]int{{"foo": 1, "bar": 2}}
+			actual   = []*map[string]int{{"foo": 1}}
+		)
+		assert.Equal(t, actual, expected)
+	}, `at (*actual[0])["bar"]: expected 2, but got <missing>`)
+	expectErrors(t, func(t assert.TestingTB) {
+		var (
+			expected = []*record{{1, "Alice", false}}
+			actual   = []*record{{2, "Bob", false}}
+		)
+		assert.Equal(t, actual, expected)
+	}, `
+		at actual[0].ID: expected 1, but got 2
+		at actual[0].Name: expected "Alice", but got "Bob"
+	`)
 }
+
+// TODO: check coverage
+// TODO: implement special case for ~[]byte containing valid UTF-8
diff --git a/internal/path/path.go b/internal/path/path.go
index 30a94d2..333b3b2 100644
--- a/internal/path/path.go
+++ b/internal/path/path.go
@@ -5,6 +5,7 @@ package path
 
 import (
 	"encoding/json"
+	"fmt"
 	"strconv"
 	"strings"
 
@@ -36,15 +37,30 @@ func NewPath() Path {
 
 // Element occurs in type [Path]. Only one of both fields is set per instance.
 type Element struct {
+	// used by both package jsonmatch and package assert
 	Key   Option[string]
 	Index int
+
+	// only used by package assert (panics when used with AsJSONPointer())
+	MapKey      Option[any] // holds a value of type K for traversing into types ~map[K]V
+	TypeCast    string      // holds a %T formatting of a type
+	Dereference bool        // marks when a pointer is dereferenced
 }
 
 // KeyElement is a shorthand for constructing an Element with the Key field set.
-func KeyElement(key string) Element { return Element{Some(key), 0} }
+func KeyElement(key string) Element { return Element{Key: Some(key)} }
 
 // IndexElement is a shorthand for constructing an Element with the Index field set.
-func IndexElement(idx int) Element { return Element{None[string](), idx} }
+func IndexElement(idx int) Element { return Element{Index: idx} }
+
+// MapKeyElement is a shorthand for constructing an Element with the MapKey field set.
+func MapKeyElement(key any) Element { return Element{MapKey: Some(key)} }
+
+// TypeCastElement is a shorthand for constructing an Element with the TypeCast field set.
+func TypeCastElement(typeStr string) Element { return Element{TypeCast: typeStr} }
+
+// DereferenceElement is a shorthand for constructing an Element with the Dereference field set.
+func DereferenceElement() Element { return Element{Dereference: true} }
 
 // AsJSONPointer serializes p as a JSON pointer (RFC 6901).
 func (p Path) AsJSONPointer() string {
@@ -54,6 +70,15 @@ func (p Path) AsJSONPointer() string {
 	fragments := make([]string, len(p)+1)
 	fragments[0] = ""
 	for idx, elem := range p {
+		if elem.Dereference {
+			panic("Dereference elements cannot be used with AsJSONPointer()")
+		}
+		if elem.TypeCast != "" {
+			panic("TypeCast elements cannot be used with AsJSONPointer()")
+		}
+		if elem.MapKey.IsSome() {
+			panic("MapKey elements cannot be used with AsJSONPointer()")
+		}
 		if key, ok := elem.Key.Unpack(); ok {
 			fragments[idx+1] = keyIntoPointerFragment(key)
 		} else {
@@ -72,3 +97,29 @@ func keyIntoPointerFragment(key string) string {
 	s = strings.ReplaceAll(s, "/", "~1")
 	return s
 }
+
+// AsGoExpression serializes p as a partial Go expression like `value.Objects["foo.txt"].Lines[42]`.
+func (p Path) AsGoExpression(baseVariable string) string {
+	b := &strings.Builder{}
+	fmt.Fprint(b, baseVariable)
+	for idx, elem := range p {
+		if elem.Dereference {
+			if idx != len(p)-1 && p[idx+1].Key.IsSome() {
+				// simplify `(*foo).Bar` to `foo.Bar`
+				continue
+			}
+			str := b.String()
+			b = &strings.Builder{}
+			fmt.Fprintf(b, "(*%s)", str)
+		} else if elem.TypeCast != "" {
+			fmt.Fprintf(b, `.(%s)`, elem.TypeCast)
+		} else if mapKey, ok := elem.MapKey.Unpack(); ok {
+			fmt.Fprintf(b, `[%#v]`, mapKey)
+		} else if key, ok := elem.Key.Unpack(); ok {
+			fmt.Fprintf(b, `.%s`, key)
+		} else {
+			fmt.Fprintf(b, `[%d]`, elem.Index)
+		}
+	}
+	return b.String()
+}
diff --git a/option/option_test.go b/option/option_test.go
index 7ba50d9..43d114e 100644
--- a/option/option_test.go
+++ b/option/option_test.go
@@ -1,7 +1,7 @@
 // SPDX-FileCopyrightText: 2025 Stefan Majewsky <majewsky@gmx.net>
 // SPDX-License-Identifier: Apache-2.0
 
-package option
+package option_test
 
 import (
 	"encoding/json"
@@ -10,6 +10,7 @@ import (
 	"testing"
 
 	"go.xyrillian.de/gg/assert"
+	. "go.xyrillian.de/gg/option"
 )
 
 func TestZeroValue(t *testing.T) {