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