1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
|
// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.
// Deep equality test via reflection
package reflect
// During deepValueEqual, must keep track of checks that are
// in progress. The comparison algorithm assumes that all
// checks in progress are true when it reencounters them.
// Visited are stored in a map indexed by 17 * a1 + a2;
type visit struct {
a1 uintptr
a2 uintptr
typ Type
next *visit
}
// Tests for deep equality using reflected types. The map argument tracks
// comparisons that have already been seen, which allows short circuiting on
// recursive types.
func deepValueEqual(v1, v2 Value, visited map[uintptr]*visit, depth int) (b bool) {
if !v1.IsValid() || !v2.IsValid() {
return v1.IsValid() == v2.IsValid()
}
if v1.Type() != v2.Type() {
return false
}
// if depth > 10 { panic("deepValueEqual") } // for debugging
if v1.CanAddr() && v2.CanAddr() {
addr1 := v1.UnsafeAddr()
addr2 := v2.UnsafeAddr()
if addr1 > addr2 {
// Canonicalize order to reduce number of entries in visited.
addr1, addr2 = addr2, addr1
}
// Short circuit if references are identical ...
if addr1 == addr2 {
return true
}
// ... or already seen
h := 17*addr1 + addr2
seen := visited[h]
typ := v1.Type()
for p := seen; p != nil; p = p.next {
if p.a1 == addr1 && p.a2 == addr2 && p.typ == typ {
return true
}
}
// Remember for later.
visited[h] = &visit{addr1, addr2, typ, seen}
}
switch v1.Kind() {
case Array:
if v1.Len() != v2.Len() {
return false
}
for i := 0; i < v1.Len(); i++ {
if !deepValueEqual(v1.Index(i), v2.Index(i), visited, depth+1) {
return false
}
}
return true
case Slice:
if v1.IsNil() != v2.IsNil() {
return false
}
if v1.Len() != v2.Len() {
return false
}
for i := 0; i < v1.Len(); i++ {
if !deepValueEqual(v1.Index(i), v2.Index(i), visited, depth+1) {
return false
}
}
return true
case Interface:
if v1.IsNil() || v2.IsNil() {
return v1.IsNil() == v2.IsNil()
}
return deepValueEqual(v1.Elem(), v2.Elem(), visited, depth+1)
case Ptr:
return deepValueEqual(v1.Elem(), v2.Elem(), visited, depth+1)
case Struct:
for i, n := 0, v1.NumField(); i < n; i++ {
if !deepValueEqual(v1.Field(i), v2.Field(i), visited, depth+1) {
return false
}
}
return true
case Map:
if v1.IsNil() != v2.IsNil() {
return false
}
if v1.Len() != v2.Len() {
return false
}
for _, k := range v1.MapKeys() {
if !deepValueEqual(v1.MapIndex(k), v2.MapIndex(k), visited, depth+1) {
return false
}
}
return true
case Func:
if v1.IsNil() && v2.IsNil() {
return true
}
// Can't do better than this:
return false
default:
// Normal equality suffices
return valueInterface(v1, false) == valueInterface(v2, false)
}
}
// DeepEqual tests for deep equality. It uses normal == equality where
// possible but will scan elements of arrays, slices, maps, and fields of
// structs. In maps, keys are compared with == but elements use deep
// equality. DeepEqual correctly handles recursive types. Functions are equal
// only if they are both nil.
// An empty slice is not equal to a nil slice.
func DeepEqual(a1, a2 interface{}) bool {
if a1 == nil || a2 == nil {
return a1 == a2
}
v1 := ValueOf(a1)
v2 := ValueOf(a2)
if v1.Type() != v2.Type() {
return false
}
return deepValueEqual(v1, v2, make(map[uintptr]*visit), 0)
}
|