libgo/go/reflect/deepequal.go

   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         hard := func(k Kind) bool {
  34                 switch k {
  35                 case Array, Map, Slice, Struct:
  36                         return true
  37                 }
  38                 return false
  39         }
  40
  41         if v1.CanAddr() && v2.CanAddr() && hard(v1.Kind()) {
  42                 addr1 := unsafe.Pointer(v1.UnsafeAddr())
  43                 addr2 := unsafe.Pointer(v2.UnsafeAddr())
  44                 if uintptr(addr1) > uintptr(addr2) {
  45                         // Canonicalize order to reduce number of entries in visited.
  46                         // Assumes non-moving garbage collector.
  47                         addr1, addr2 = addr2, addr1
  48                 }
  49
  50                 // Short circuit if references are already seen.
  51                 typ := v1.Type()
  52                 v := visit{addr1, addr2, typ}
  53                 if visited[v] {
  54                         return true
  55                 }
  56
  57                 // Remember for later.
  58                 visited[v] = true
  59         }
  60
  61         switch v1.Kind() {
  62         case Array:
  63                 for i := 0; i < v1.Len(); i++ {
  64                         if !deepValueEqual(v1.Index(i), v2.Index(i), visited, depth+1) {
  65                                 return false
  66                         }
  67                 }
  68                 return true
  69         case Slice:
  70                 if v1.IsNil() != v2.IsNil() {
  71                         return false
  72                 }
  73                 if v1.Len() != v2.Len() {
  74                         return false
  75                 }
  76                 if v1.Pointer() == v2.Pointer() {
  77                         return true
  78                 }
  79                 for i := 0; i < v1.Len(); i++ {
  80                         if !deepValueEqual(v1.Index(i), v2.Index(i), visited, depth+1) {
  81                                 return false
  82                         }
  83                 }
  84                 return true
  85         case Interface:
  86                 if v1.IsNil() || v2.IsNil() {
  87                         return v1.IsNil() == v2.IsNil()
  88                 }
  89                 return deepValueEqual(v1.Elem(), v2.Elem(), visited, depth+1)
  90         case Ptr:
  91                 if v1.Pointer() == v2.Pointer() {
  92                         return true
  93                 }
  94                 return deepValueEqual(v1.Elem(), v2.Elem(), visited, depth+1)
  95         case Struct:
  96                 for i, n := 0, v1.NumField(); i < n; i++ {
  97                         if !deepValueEqual(v1.Field(i), v2.Field(i), visited, depth+1) {
  98                                 return false
  99                         }
 100                 }
 101                 return true
 102         case Map:
 103                 if v1.IsNil() != v2.IsNil() {
 104                         return false
 105                 }
 106                 if v1.Len() != v2.Len() {
 107                         return false
 108                 }
 109                 if v1.Pointer() == v2.Pointer() {
 110                         return true
 111                 }
 112                 for _, k := range v1.MapKeys() {
 113                         val1 := v1.MapIndex(k)
 114                         val2 := v2.MapIndex(k)
 115                         if !val1.IsValid() || !val2.IsValid() || !deepValueEqual(v1.MapIndex(k), v2.MapIndex(k), visited, depth+1) {
 116                                 return false
 117                         }
 118                 }
 119                 return true
 120         case Func:
 121                 if v1.IsNil() && v2.IsNil() {
 122                         return true
 123                 }
 124                 // Can't do better than this:
 125                 return false
 126         default:
 127                 // Normal equality suffices
 128                 return valueInterface(v1, false) == valueInterface(v2, false)
 129         }
 130 }
 131
 132 // DeepEqual reports whether x and y are ``deeply equal,'' defined as follows.
 133 // Two values of identical type are deeply equal if one of the following cases applies.
 134 // Values of distinct types are never deeply equal.
 135 //
 136 // Array values are deeply equal when their corresponding elements are deeply equal.
 137 //
 138 // Struct values are deeply equal if their corresponding fields,
 139 // both exported and unexported, are deeply equal.
 140 //
 141 // Func values are deeply equal if both are nil; otherwise they are not deeply equal.
 142 //
 143 // Interface values are deeply equal if they hold deeply equal concrete values.
 144 //
 145 // Map values are deeply equal if they are the same map object
 146 // or if they have the same length and their corresponding keys
 147 // (matched using Go equality) map to deeply equal values.
 148 //
 149 // Pointer values are deeply equal if they are equal using Go's == operator
 150 // or if they point to deeply equal values.
 151 //
 152 // Slice values are deeply equal when all of the following are true:
 153 // they are both nil or both non-nil, they have the same length,
 154 // and either they point to the same initial entry of the same underlying array
 155 // (that is, &x[0] == &y[0]) or their corresponding elements (up to length) are deeply equal.
 156 // Note that a non-nil empty slice and a nil slice (for example, []byte{} and []byte(nil))
 157 // are not deeply equal.
 158 //
 159 // Other values - numbers, bools, strings, and channels - are deeply equal
 160 // if they are equal using Go's == operator.
 161 //
 162 // In general DeepEqual is a recursive relaxation of Go's == operator.
 163 // However, this idea is impossible to implement without some inconsistency.
 164 // Specifically, it is possible for a value to be unequal to itself,
 165 // either because it is of func type (uncomparable in general)
 166 // or because it is a floating-point NaN value (not equal to itself in floating-point comparison),
 167 // or because it is an array, struct, or interface containing
 168 // such a value.
 169 // On the other hand, pointer values are always equal to themselves,
 170 // even if they point at or contain such problematic values,
 171 // because they compare equal using Go's == operator, and that
 172 // is a sufficient condition to be deeply equal, regardless of content.
 173 // DeepEqual has been defined so that the same short-cut applies
 174 // to slices and maps: if x and y are the same slice or the same map,
 175 // they are deeply equal regardless of content.
 176 func DeepEqual(x, y interface{}) bool {
 177         if x == nil || y == nil {
 178                 return x == y
 179         }
 180         v1 := ValueOf(x)
 181         v2 := ValueOf(y)
 182         if v1.Type() != v2.Type() {
 183                 return false
 184         }
 185         return deepValueEqual(v1, v2, make(map[visit]bool), 0)
 186 }