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. 4 5 // Deep equality test via reflection 6 7 package reflect 8 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. 13 type visit struct { 14 a1 uintptr 15 a2 uintptr 16 typ Type 17 } 18 19 // Tests for deep equality using reflected types. The map argument tracks 20 // comparisons that have already been seen, which allows short circuiting on 21 // recursive types. 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() 25 } 26 if v1.Type() != v2.Type() { 27 return false 28 } 29 30 // if depth > 10 { panic("deepValueEqual") } // for debugging 31 hard := func(k Kind) bool { 32 switch k { 33 case Array, Map, Slice, Struct: 34 return true 35 } 36 return false 37 } 38 39 if v1.CanAddr() && v2.CanAddr() && hard(v1.Kind()) { 40 addr1 := v1.UnsafeAddr() 41 addr2 := v2.UnsafeAddr() 42 if addr1 > addr2 { 43 // Canonicalize order to reduce number of entries in visited. 44 addr1, addr2 = addr2, addr1 45 } 46 47 // Short circuit if references are identical ... 48 if addr1 == addr2 { 49 return true 50 } 51 52 // ... or already seen 53 typ := v1.Type() 54 v := visit{addr1, addr2, typ} 55 if visited[v] { 56 return true 57 } 58 59 // Remember for later. 60 visited[v] = true 61 } 62 63 switch v1.Kind() { 64 case Array: 65 for i := 0; i < v1.Len(); i++ { 66 if !deepValueEqual(v1.Index(i), v2.Index(i), visited, depth+1) { 67 return false 68 } 69 } 70 return true 71 case Slice: 72 if v1.IsNil() != v2.IsNil() { 73 return false 74 } 75 if v1.Len() != v2.Len() { 76 return false 77 } 78 if v1.Pointer() == v2.Pointer() { 79 return true 80 } 81 for i := 0; i < v1.Len(); i++ { 82 if !deepValueEqual(v1.Index(i), v2.Index(i), visited, depth+1) { 83 return false 84 } 85 } 86 return true 87 case Interface: 88 if v1.IsNil() || v2.IsNil() { 89 return v1.IsNil() == v2.IsNil() 90 } 91 return deepValueEqual(v1.Elem(), v2.Elem(), visited, depth+1) 92 case Ptr: 93 return deepValueEqual(v1.Elem(), v2.Elem(), visited, depth+1) 94 case Struct: 95 for i, n := 0, v1.NumField(); i < n; i++ { 96 if !deepValueEqual(v1.Field(i), v2.Field(i), visited, depth+1) { 97 return false 98 } 99 } 100 return true 101 case Map: 102 if v1.IsNil() != v2.IsNil() { 103 return false 104 } 105 if v1.Len() != v2.Len() { 106 return false 107 } 108 if v1.Pointer() == v2.Pointer() { 109 return true 110 } 111 for _, k := range v1.MapKeys() { 112 if !deepValueEqual(v1.MapIndex(k), v2.MapIndex(k), visited, depth+1) { 113 return false 114 } 115 } 116 return true 117 case Func: 118 if v1.IsNil() && v2.IsNil() { 119 return true 120 } 121 // Can't do better than this: 122 return false 123 default: 124 // Normal equality suffices 125 return valueInterface(v1, false) == valueInterface(v2, false) 126 } 127 } 128 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 { 137 return a1 == a2 138 } 139 v1 := ValueOf(a1) 140 v2 := ValueOf(a2) 141 if v1.Type() != v2.Type() { 142 return false 143 } 144 return deepValueEqual(v1, v2, make(map[visit]bool), 0) 145 } 146
