13.3 Example: Deep Equivalence

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.

gopl.io/ch13/equal
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.

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.
Reset
54.198.146.13