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 comparisons are stored in a map indexed by visit.
19 // Tests for deep equality using reflected types. The map argument tracks
20 // comparisons that have already been seen, which allows short circuiting on
22 func deepValueEqual(v1
, v2 Value
, visited
map[visit
]bool, depth
int) bool {
23 if !v1
.IsValid() ||
!v2
.IsValid() {
24 return v1
.IsValid() == v2
.IsValid()
26 if v1
.Type() != v2
.Type() {
30 // if depth > 10 { panic("deepValueEqual") } // for debugging
31 hard
:= func(k Kind
) bool {
33 case Array
, Map
, Slice
, Struct
:
39 if v1
.CanAddr() && v2
.CanAddr() && hard(v1
.Kind()) {
40 addr1
:= v1
.UnsafeAddr()
41 addr2
:= v2
.UnsafeAddr()
43 // Canonicalize order to reduce number of entries in visited.
44 addr1
, addr2
= addr2
, addr1
47 // Short circuit if references are identical ...
52 // ... or already seen
54 v
:= visit
{addr1
, addr2
, typ
}
59 // Remember for later.
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 if v1
.Pointer() == v2
.Pointer() {
81 for i
:= 0; i
< v1
.Len(); i
++ {
82 if !deepValueEqual(v1
.Index(i
), v2
.Index(i
), visited
, depth
+1) {
88 if v1
.IsNil() || v2
.IsNil() {
89 return v1
.IsNil() == v2
.IsNil()
91 return deepValueEqual(v1
.Elem(), v2
.Elem(), visited
, depth
+1)
93 return deepValueEqual(v1
.Elem(), v2
.Elem(), visited
, depth
+1)
95 for i
, n
:= 0, v1
.NumField(); i
< n
; i
++ {
96 if !deepValueEqual(v1
.Field(i
), v2
.Field(i
), visited
, depth
+1) {
102 if v1
.IsNil() != v2
.IsNil() {
105 if v1
.Len() != v2
.Len() {
108 if v1
.Pointer() == v2
.Pointer() {
111 for _
, k
:= range v1
.MapKeys() {
112 if !deepValueEqual(v1
.MapIndex(k
), v2
.MapIndex(k
), visited
, depth
+1) {
118 if v1
.IsNil() && v2
.IsNil() {
121 // Can't do better than this:
124 // Normal equality suffices
125 return valueInterface(v1
, false) == valueInterface(v2
, false)
129 // DeepEqual tests for deep equality. It uses normal == equality where
130 // possible but will scan elements of arrays, slices, maps, and fields of
131 // structs. In maps, keys are compared with == but elements use deep
132 // equality. DeepEqual correctly handles recursive types. Functions are equal
133 // only if they are both nil.
134 // An empty slice is not equal to a nil slice.
135 func DeepEqual(a1
, a2
interface{}) bool {
136 if a1
== nil || a2
== nil {
141 if v1
.Type() != v2
.Type() {
144 return deepValueEqual(v1
, v2
, make(map[visit
]bool), 0)