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 import "unsafe" 10 11 // During deepValueEqual, must keep track of checks that are 12 // in progress. The comparison algorithm assumes that all 13 // checks in progress are true when it reencounters them. 14 // Visited comparisons are stored in a map indexed by visit. 15 type visit struct { 16 a1 unsafe.Pointer 17 a2 unsafe.Pointer 18 typ Type 19 } 20 21 // Tests for deep equality using reflected types. The map argument tracks 22 // comparisons that have already been seen, which allows short circuiting on 23 // recursive types. 24 func deepValueEqual(v1, v2 Value, visited map[visit]bool, depth int) bool { 25 if !v1.IsValid() || !v2.IsValid() { 26 return v1.IsValid() == v2.IsValid() 27 } 28 if v1.Type() != v2.Type() { 29 return false 30 } 31 32 // if depth > 10 { panic("deepValueEqual") } // for debugging 33 34 // We want to avoid putting more in the visited map than we need to. 35 // For any possible reference cycle that might be encountered, 36 // hard(t) needs to return true for at least one of the types in the cycle. 37 hard := func(k Kind) bool { 38 switch k { 39 case Map, Slice, Ptr, Interface: 40 return true 41 } 42 return false 43 } 44 45 if v1.CanAddr() && v2.CanAddr() && hard(v1.Kind()) { 46 addr1 := unsafe.Pointer(v1.UnsafeAddr()) 47 addr2 := unsafe.Pointer(v2.UnsafeAddr()) 48 if uintptr(addr1) > uintptr(addr2) { 49 // Canonicalize order to reduce number of entries in visited. 50 // Assumes non-moving garbage collector. 51 addr1, addr2 = addr2, addr1 52 } 53 54 // Short circuit if references are already seen. 55 typ := v1.Type() 56 v := visit{addr1, addr2, typ} 57 if visited[v] { 58 return true 59 } 60 61 // Remember for later. 62 visited[v] = true 63 } 64 65 switch v1.Kind() { 66 case Array: 67 for i := 0; i < v1.Len(); i++ { 68 if !deepValueEqual(v1.Index(i), v2.Index(i), visited, depth+1) { 69 return false 70 } 71 } 72 return true 73 case Slice: 74 if v1.IsNil() != v2.IsNil() { 75 return false 76 } 77 if v1.Len() != v2.Len() { 78 return false 79 } 80 if v1.Pointer() == v2.Pointer() { 81 return true 82 } 83 for i := 0; i < v1.Len(); i++ { 84 if !deepValueEqual(v1.Index(i), v2.Index(i), visited, depth+1) { 85 return false 86 } 87 } 88 return true 89 case Interface: 90 if v1.IsNil() || v2.IsNil() { 91 return v1.IsNil() == v2.IsNil() 92 } 93 return deepValueEqual(v1.Elem(), v2.Elem(), visited, depth+1) 94 case Ptr: 95 if v1.Pointer() == v2.Pointer() { 96 return true 97 } 98 return deepValueEqual(v1.Elem(), v2.Elem(), visited, depth+1) 99 case Struct: 100 for i, n := 0, v1.NumField(); i < n; i++ { 101 if !deepValueEqual(v1.Field(i), v2.Field(i), visited, depth+1) { 102 return false 103 } 104 } 105 return true 106 case Map: 107 if v1.IsNil() != v2.IsNil() { 108 return false 109 } 110 if v1.Len() != v2.Len() { 111 return false 112 } 113 if v1.Pointer() == v2.Pointer() { 114 return true 115 } 116 for _, k := range v1.MapKeys() { 117 val1 := v1.MapIndex(k) 118 val2 := v2.MapIndex(k) 119 if !val1.IsValid() || !val2.IsValid() || !deepValueEqual(val1, val2, visited, depth+1) { 120 return false 121 } 122 } 123 return true 124 case Func: 125 if v1.IsNil() && v2.IsNil() { 126 return true 127 } 128 // Can't do better than this: 129 return false 130 default: 131 // Normal equality suffices 132 return valueInterface(v1, false) == valueInterface(v2, false) 133 } 134 } 135 136 // DeepEqual reports whether x and y are ``deeply equal,'' defined as follows. 137 // Two values of identical type are deeply equal if one of the following cases applies. 138 // Values of distinct types are never deeply equal. 139 // 140 // Array values are deeply equal when their corresponding elements are deeply equal. 141 // 142 // Struct values are deeply equal if their corresponding fields, 143 // both exported and unexported, are deeply equal. 144 // 145 // Func values are deeply equal if both are nil; otherwise they are not deeply equal. 146 // 147 // Interface values are deeply equal if they hold deeply equal concrete values. 148 // 149 // Map values are deeply equal when all of the following are true: 150 // they are both nil or both non-nil, they have the same length, 151 // and either they are the same map object or their corresponding keys 152 // (matched using Go equality) map to deeply equal values. 153 // 154 // Pointer values are deeply equal if they are equal using Go's == operator 155 // or if they point to deeply equal values. 156 // 157 // Slice values are deeply equal when all of the following are true: 158 // they are both nil or both non-nil, they have the same length, 159 // and either they point to the same initial entry of the same underlying array 160 // (that is, &x[0] == &y[0]) or their corresponding elements (up to length) are deeply equal. 161 // Note that a non-nil empty slice and a nil slice (for example, []byte{} and []byte(nil)) 162 // are not deeply equal. 163 // 164 // Other values - numbers, bools, strings, and channels - are deeply equal 165 // if they are equal using Go's == operator. 166 // 167 // In general DeepEqual is a recursive relaxation of Go's == operator. 168 // However, this idea is impossible to implement without some inconsistency. 169 // Specifically, it is possible for a value to be unequal to itself, 170 // either because it is of func type (uncomparable in general) 171 // or because it is a floating-point NaN value (not equal to itself in floating-point comparison), 172 // or because it is an array, struct, or interface containing 173 // such a value. 174 // On the other hand, pointer values are always equal to themselves, 175 // even if they point at or contain such problematic values, 176 // because they compare equal using Go's == operator, and that 177 // is a sufficient condition to be deeply equal, regardless of content. 178 // DeepEqual has been defined so that the same short-cut applies 179 // to slices and maps: if x and y are the same slice or the same map, 180 // they are deeply equal regardless of content. 181 // 182 // As DeepEqual traverses the data values it may find a cycle. The 183 // second and subsequent times that DeepEqual compares two pointer 184 // values that have been compared before, it treats the values as 185 // equal rather than examining the values to which they point. 186 // This ensures that DeepEqual terminates. 187 func DeepEqual(x, y interface{}) bool { 188 if x == nil || y == nil { 189 return x == y 190 } 191 v1 := ValueOf(x) 192 v2 := ValueOf(y) 193 if v1.Type() != v2.Type() { 194 return false 195 } 196 return deepValueEqual(v1, v2, make(map[visit]bool), 0) 197 } 198