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
  10 // During deepValueEqual, must keep track of checks that are
  11 // in progress.  The comparison algorithm assumes that all
  12 // checks in progress are true when it reencounters them.
  13 // Visited are stored in a map indexed by 17 * a1 + a2;
  14 type visit struct {
  15         a1   uintptr
  16         a2   uintptr
  17         typ  Type
  18         next *visit
  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[uintptr]*visit, depth int) bool {
  25         if v1 == nil || v2 == nil {
  26                 return v1 == v2
  27         }
  28         if v1.Type() != v2.Type() {
  29                 return false
  30         }
  31
  32         // if depth > 10 { panic("deepValueEqual") }    // for debugging
  33
  34         addr1 := v1.Addr()
  35         addr2 := v2.Addr()
  36         if addr1 > addr2 {
  37                 // Canonicalize order to reduce number of entries in visited.
  38                 addr1, addr2 = addr2, addr1
  39         }
  40
  41         // Short circuit if references are identical ...
  42         if addr1 == addr2 {
  43                 return true
  44         }
  45
  46         // ... or already seen
  47         h := 17*addr1 + addr2
  48         seen := visited[h]
  49         typ := v1.Type()
  50         for p := seen; p != nil; p = p.next {
  51                 if p.a1 == addr1 && p.a2 == addr2 && p.typ == typ {
  52                         return true
  53                 }
  54         }
  55
  56         // Remember for later.
  57         visited[h] = &visit{addr1, addr2, typ, seen}
  58
  59         switch v := v1.(type) {
  60         case *ArrayValue:
  61                 arr1 := v
  62                 arr2 := v2.(*ArrayValue)
  63                 if arr1.Len() != arr2.Len() {
  64                         return false
  65                 }
  66                 for i := 0; i < arr1.Len(); i++ {
  67                         if !deepValueEqual(arr1.Elem(i), arr2.Elem(i), visited, depth+1) {
  68                                 return false
  69                         }
  70                 }
  71                 return true
  72         case *SliceValue:
  73                 arr1 := v
  74                 arr2 := v2.(*SliceValue)
  75                 if arr1.Len() != arr2.Len() {
  76                         return false
  77                 }
  78                 for i := 0; i < arr1.Len(); i++ {
  79                         if !deepValueEqual(arr1.Elem(i), arr2.Elem(i), visited, depth+1) {
  80                                 return false
  81                         }
  82                 }
  83                 return true
  84         case *InterfaceValue:
  85                 i1 := v.Interface()
  86                 i2 := v2.Interface()
  87                 if i1 == nil || i2 == nil {
  88                         return i1 == i2
  89                 }
  90                 return deepValueEqual(NewValue(i1), NewValue(i2), visited, depth+1)
  91         case *PtrValue:
  92                 return deepValueEqual(v.Elem(), v2.(*PtrValue).Elem(), visited, depth+1)
  93         case *StructValue:
  94                 struct1 := v
  95                 struct2 := v2.(*StructValue)
  96                 for i, n := 0, v.NumField(); i < n; i++ {
  97                         if !deepValueEqual(struct1.Field(i), struct2.Field(i), visited, depth+1) {
  98                                 return false
  99                         }
 100                 }
 101                 return true
 102         case *MapValue:
 103                 map1 := v
 104                 map2 := v2.(*MapValue)
 105                 if map1.Len() != map2.Len() {
 106                         return false
 107                 }
 108                 for _, k := range map1.Keys() {
 109                         if !deepValueEqual(map1.Elem(k), map2.Elem(k), visited, depth+1) {
 110                                 return false
 111                         }
 112                 }
 113                 return true
 114         default:
 115                 // Normal equality suffices
 116                 return v1.Interface() == v2.Interface()
 117         }
 118
 119         panic("Not reached")
 120 }
 121
 122 // DeepEqual tests for deep equality. It uses normal == equality where possible
 123 // but will scan members of arrays, slices, and fields of structs. It correctly
 124 // handles recursive types.
 125 func DeepEqual(a1, a2 interface{}) bool {
 126         if a1 == nil || a2 == nil {
 127                 return a1 == a2
 128         }
 129         v1 := NewValue(a1)
 130         v2 := NewValue(a2)
 131         if v1.Type() != v2.Type() {
 132                 return false
 133         }
 134         return deepValueEqual(v1, v2, make(map[uintptr]*visit), 0)
 135 }