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) 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 // We want to avoid putting more in the visited map than we need to. 33 // For any possible reference cycle that might be encountered, 34 // hard(v1, v2) needs to return true for at least one of the types in the cycle, 35 // and it's safe and valid to get Value's internal pointer. 36 hard := func(v1, v2 Value) bool { 37 switch v1.Kind() { 38 case Ptr: 39 if v1.typ.ptrdata == 0 { 40 // go:notinheap pointers can't be cyclic. 41 // At least, all of our current uses of go:notinheap have 42 // that property. The runtime ones aren't cyclic (and we don't use 43 // DeepEqual on them anyway), and the cgo-generated ones are 44 // all empty structs. 45 return false 46 } 47 fallthrough 48 case Map, Slice, Interface: 49 // Nil pointers cannot be cyclic. Avoid putting them in the visited map. 50 return !v1.IsNil() && !v2.IsNil() 51 } 52 return false 53 } 54 55 if hard(v1, v2) { 56 // For a Ptr or Map value, we need to check flagIndir, 57 // which we do by calling the pointer method. 58 // For Slice or Interface, flagIndir is always set, 59 // and using v.ptr suffices. 60 ptrval := func(v Value) unsafe.Pointer { 61 switch v.Kind() { 62 case Ptr, Map: 63 return v.pointer() 64 default: 65 return v.ptr 66 } 67 } 68 addr1 := ptrval(v1) 69 addr2 := ptrval(v2) 70 if uintptr(addr1) > uintptr(addr2) { 71 // Canonicalize order to reduce number of entries in visited. 72 // Assumes non-moving garbage collector. 73 addr1, addr2 = addr2, addr1 74 } 75 76 // Short circuit if references are already seen. 77 typ := v1.Type() 78 v := visit{addr1, addr2, typ} 79 if visited[v] { 80 return true 81 } 82 83 // Remember for later. 84 visited[v] = true 85 } 86 87 switch v1.Kind() { 88 case Array: 89 for i := 0; i < v1.Len(); i++ { 90 if !deepValueEqual(v1.Index(i), v2.Index(i), visited) { 91 return false 92 } 93 } 94 return true 95 case Slice: 96 if v1.IsNil() != v2.IsNil() { 97 return false 98 } 99 if v1.Len() != v2.Len() { 100 return false 101 } 102 if v1.Pointer() == v2.Pointer() { 103 return true 104 } 105 for i := 0; i < v1.Len(); i++ { 106 if !deepValueEqual(v1.Index(i), v2.Index(i), visited) { 107 return false 108 } 109 } 110 return true 111 case Interface: 112 if v1.IsNil() || v2.IsNil() { 113 return v1.IsNil() == v2.IsNil() 114 } 115 return deepValueEqual(v1.Elem(), v2.Elem(), visited) 116 case Ptr: 117 if v1.Pointer() == v2.Pointer() { 118 return true 119 } 120 return deepValueEqual(v1.Elem(), v2.Elem(), visited) 121 case Struct: 122 for i, n := 0, v1.NumField(); i < n; i++ { 123 if !deepValueEqual(v1.Field(i), v2.Field(i), visited) { 124 return false 125 } 126 } 127 return true 128 case Map: 129 if v1.IsNil() != v2.IsNil() { 130 return false 131 } 132 if v1.Len() != v2.Len() { 133 return false 134 } 135 if v1.Pointer() == v2.Pointer() { 136 return true 137 } 138 for _, k := range v1.MapKeys() { 139 val1 := v1.MapIndex(k) 140 val2 := v2.MapIndex(k) 141 if !val1.IsValid() || !val2.IsValid() || !deepValueEqual(val1, val2, visited) { 142 return false 143 } 144 } 145 return true 146 case Func: 147 if v1.IsNil() && v2.IsNil() { 148 return true 149 } 150 // Can't do better than this: 151 return false 152 default: 153 // Normal equality suffices 154 return valueInterface(v1, false) == valueInterface(v2, false) 155 } 156 } 157 158 // DeepEqual reports whether x and y are ``deeply equal,'' defined as follows. 159 // Two values of identical type are deeply equal if one of the following cases applies. 160 // Values of distinct types are never deeply equal. 161 // 162 // Array values are deeply equal when their corresponding elements are deeply equal. 163 // 164 // Struct values are deeply equal if their corresponding fields, 165 // both exported and unexported, are deeply equal. 166 // 167 // Func values are deeply equal if both are nil; otherwise they are not deeply equal. 168 // 169 // Interface values are deeply equal if they hold deeply equal concrete values. 170 // 171 // Map values are deeply equal when all of the following are true: 172 // they are both nil or both non-nil, they have the same length, 173 // and either they are the same map object or their corresponding keys 174 // (matched using Go equality) map to deeply equal values. 175 // 176 // Pointer values are deeply equal if they are equal using Go's == operator 177 // or if they point to deeply equal values. 178 // 179 // Slice values are deeply equal when all of the following are true: 180 // they are both nil or both non-nil, they have the same length, 181 // and either they point to the same initial entry of the same underlying array 182 // (that is, &x[0] == &y[0]) or their corresponding elements (up to length) are deeply equal. 183 // Note that a non-nil empty slice and a nil slice (for example, []byte{} and []byte(nil)) 184 // are not deeply equal. 185 // 186 // Other values - numbers, bools, strings, and channels - are deeply equal 187 // if they are equal using Go's == operator. 188 // 189 // In general DeepEqual is a recursive relaxation of Go's == operator. 190 // However, this idea is impossible to implement without some inconsistency. 191 // Specifically, it is possible for a value to be unequal to itself, 192 // either because it is of func type (uncomparable in general) 193 // or because it is a floating-point NaN value (not equal to itself in floating-point comparison), 194 // or because it is an array, struct, or interface containing 195 // such a value. 196 // On the other hand, pointer values are always equal to themselves, 197 // even if they point at or contain such problematic values, 198 // because they compare equal using Go's == operator, and that 199 // is a sufficient condition to be deeply equal, regardless of content. 200 // DeepEqual has been defined so that the same short-cut applies 201 // to slices and maps: if x and y are the same slice or the same map, 202 // they are deeply equal regardless of content. 203 // 204 // As DeepEqual traverses the data values it may find a cycle. The 205 // second and subsequent times that DeepEqual compares two pointer 206 // values that have been compared before, it treats the values as 207 // equal rather than examining the values to which they point. 208 // This ensures that DeepEqual terminates. 209 func DeepEqual(x, y interface{}) bool { 210 if x == nil || y == nil { 211 return x == y 212 } 213 v1 := ValueOf(x) 214 v2 := ValueOf(y) 215 if v1.Type() != v2.Type() { 216 return false 217 } 218 return deepValueEqual(v1, v2, make(map[visit]bool)) 219 } 220