The DeepEqual function from the reflect package reports
whether two values are “deeply” equal.
DeepEqual compares basic values as if by the built-in ==
operator; for composite values, it traverses them recursively,
comparing corresponding elements.
Because it works for any pair of values, even ones that are not
comparable with ==, it finds widespread use in tests.
The following test uses DeepEqual to compare two []string values:
func TestSplit(t *testing.T) {
got := strings.Split("a:b:c", ":")
want := []string{"a", "b", "c"};
if !reflect.DeepEqual(got, want) { /* ... */ }
}
Although DeepEqual is convenient, its distinctions can seem arbitrary.
For example, it doesn’t consider a nil map equal to a non-nil empty
map, nor a nil slice equal to a non-nil empty one:
var a, b []string = nil, []string{}
fmt.Println(reflect.DeepEqual(a, b)) // "false"
var c, d map[string]int = nil, make(map[string]int)
fmt.Println(reflect.DeepEqual(c, d)) // "false"
In this section we’ll define a function Equal that compares
arbitrary values.
Like DeepEqual, it compares slices and maps based on their
elements, but unlike DeepEqual, it considers a nil slice (or
map) equal to a non-nil empty one.
The basic recursion over the arguments can be done with reflection,
using a similar approach to the Display program
we saw in Section 12.3.
As usual, we define an unexported function, equal, for the
recursion. Don’t worry about the seen parameter just yet.
For each pair of values x and y to be compared,
equal checks that both (or neither) are valid and checks
that they have the same type.
The result of the function is defined as a set of switch cases that
compare two values of the same type.
For reasons of space, we’ve omitted several cases since the pattern
should be familiar by now.
func equal(x, y reflect.Value, seen map[comparison]bool) bool {
if !x.IsValid() || !y.IsValid() {
return x.IsValid() == y.IsValid()
}
if x.Type() != y.Type() {
return false
}
// ...cycle check omitted (shown later)...
switch x.Kind() {
case reflect.Bool:
return x.Bool() == y.Bool()
case reflect.String:
return x.String() == y.String()
// ...numeric cases omitted for brevity...
case reflect.Chan, reflect.UnsafePointer, reflect.Func:
return x.Pointer() == y.Pointer()
case reflect.Ptr, reflect.Interface:
return equal(x.Elem(), y.Elem(), seen)
case reflect.Array, reflect.Slice:
if x.Len() != y.Len() {
return false
}
for i := 0; i < x.Len(); i++ {
if !equal(x.Index(i), y.Index(i), seen) {
return false
}
}
return true
// ...struct and map cases omitted for brevity...
}
panic("unreachable")
}
As usual, we don’t expose the use of reflection in the API, so the
exported function Equal must call reflect.ValueOf on
its arguments:
// Equal reports whether x and y are deeply equal.
func Equal(x, y interface{}) bool {
seen := make(map[comparison]bool)
return equal(reflect.ValueOf(x), reflect.ValueOf(y), seen)
}
type comparison struct {
x, y unsafe.Pointer
t reflect.Type
}
To ensure that the algorithm terminates even for cyclic data
structures, it must record which pairs of variables it has already
compared and avoid comparing them a second time.
Equal allocates a set of comparison structs, each
holding the address of two variables (represented as
unsafe.Pointer values) and the type of the comparison.
We need to record the type in addition to the addresses because
different variables can have the same address.
For example, if x and y are both arrays, x and
x[0] have the same address, as do y and y[0], and
it is important to distinguish whether we have compared x and
y or x[0] and y[0].
Once equal has established that its arguments have the same
type, and before it executes the switch, it checks whether it is
comparing two variables it has already seen and, if so, terminates the
recursion.
// cycle check
if x.CanAddr() && y.CanAddr() {
xptr := unsafe.Pointer(x.UnsafeAddr())
yptr := unsafe.Pointer(y.UnsafeAddr())
if xptr == yptr {
return true // identical references
}
c := comparison{xptr, yptr, x.Type()}
if seen[c] {
return true // already seen
}
seen[c] = true
}
Here’s our Equal function in action:
fmt.Println(Equal([]int{1, 2, 3}, []int{1, 2, 3})) // "true"
fmt.Println(Equal([]string{"foo"}, []string{"bar"})) // "false"
fmt.Println(Equal([]string(nil), []string{})) // "true"
fmt.Println(Equal(map[string]int(nil), map[string]int{})) // "true"
It even works on cyclic inputs similar to the one
that caused the Display function from
Section 12.3 to get stuck in a loop:
// Circular linked lists a -> b -> a and c -> c.
type link struct {
value string
tail *link
}
a, b, c := &link{value: "a"}, &link{value: "b"}, &link{value: "c"}
a.tail, b.tail, c.tail = b, a, c
fmt.Println(Equal(a, a)) // "true"
fmt.Println(Equal(b, b)) // "true"
fmt.Println(Equal(c, c)) // "true"
fmt.Println(Equal(a, b)) // "false"
fmt.Println(Equal(a, c)) // "false"
Exercise 13.1: Define a deep comparison function that considers numbers (of any type) equal if they differ by less than one part in a billion.
Exercise 13.2: Write a function that reports whether its argument is a cyclic data structure.