1 // Copyright 2009 The Go Authors. All rights reserved.
2 // Use of this source code is governed by a BSD-style
3 // license that can be found in the LICENSE file.
5 // Deep equality test via reflection
9 // During deepValueEqual, must keep track of checks that are
10 // in progress. The comparison algorithm assumes that all
11 // checks in progress are true when it reencounters them.
12 // Visited are stored in a map indexed by 17 * a1 + a2;
20 // Tests for deep equality using reflected types. The map argument tracks
21 // comparisons that have already been seen, which allows short circuiting on
23 func deepValueEqual(v1, v2 Value, visited map[uintptr]*visit, depth int) (b bool) {
24 if !v1.IsValid() || !v2.IsValid() {
25 return v1.IsValid() == v2.IsValid()
27 if v1.Type() != v2.Type() {
31 // if depth > 10 { panic("deepValueEqual") } // for debugging
33 if v1.CanAddr() && v2.CanAddr() {
34 addr1 := v1.UnsafeAddr()
35 addr2 := v2.UnsafeAddr()
37 // Canonicalize order to reduce number of entries in visited.
38 addr1, addr2 = addr2, addr1
41 // Short circuit if references are identical ...
46 // ... or already seen
50 for p := seen; p != nil; p = p.next {
51 if p.a1 == addr1 && p.a2 == addr2 && p.typ == typ {
56 // Remember for later.
57 visited[h] = &visit{addr1, addr2, typ, seen}
62 if v1.Len() != v2.Len() {
65 for i := 0; i < v1.Len(); i++ {
66 if !deepValueEqual(v1.Index(i), v2.Index(i), visited, depth+1) {
72 if v1.IsNil() != v2.IsNil() {
75 if v1.Len() != v2.Len() {
78 for i := 0; i < v1.Len(); i++ {
79 if !deepValueEqual(v1.Index(i), v2.Index(i), visited, depth+1) {
85 if v1.IsNil() || v2.IsNil() {
86 return v1.IsNil() == v2.IsNil()
88 return deepValueEqual(v1.Elem(), v2.Elem(), visited, depth+1)
90 return deepValueEqual(v1.Elem(), v2.Elem(), visited, depth+1)
92 for i, n := 0, v1.NumField(); i < n; i++ {
93 if !deepValueEqual(v1.Field(i), v2.Field(i), visited, depth+1) {
99 if v1.IsNil() != v2.IsNil() {
102 if v1.Len() != v2.Len() {
105 for _, k := range v1.MapKeys() {
106 if !deepValueEqual(v1.MapIndex(k), v2.MapIndex(k), visited, depth+1) {
112 if v1.IsNil() && v2.IsNil() {
115 // Can't do better than this:
118 // Normal equality suffices
119 return valueInterface(v1, false) == valueInterface(v2, false)
125 // DeepEqual tests for deep equality. It uses normal == equality where
126 // possible but will scan elements of arrays, slices, maps, and fields of
127 // structs. In maps, keys are compared with == but elements use deep
128 // equality. DeepEqual correctly handles recursive types. Functions are equal
129 // only if they are both nil.
130 // An empty slice is not equal to a nil slice.
131 func DeepEqual(a1, a2 interface{}) bool {
132 if a1 == nil || a2 == nil {
137 if v1.Type() != v2.Type() {
140 return deepValueEqual(v1, v2, make(map[uintptr]*visit), 0)