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