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 // 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 }