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 are stored in a map indexed by 17 * a1 + a2;
  13 type visit struct {
  14         a1   uintptr
  15         a2   uintptr
  16         typ  Type
  17         next *visit
  18 }
  19
  20 // Tests for deep equality using reflected types. The map argument tracks
  21 // comparisons that have already been seen, which allows short circuiting on
  22 // recursive types.
  23 func deepValueEqual(v1, v2 Value, visited map[uintptr]*visit, depth int) (b bool) {
  24         if !v1.IsValid() || !v2.IsValid() {
  25                 return v1.IsValid() == v2.IsValid()
  26         }
  27         if v1.Type() != v2.Type() {
  28                 return false
  29         }
  30
  31         // if depth > 10 { panic("deepValueEqual") }    // for debugging
  32
  33         if v1.CanAddr() && v2.CanAddr() {
  34                 addr1 := v1.UnsafeAddr()
  35                 addr2 := v2.UnsafeAddr()
  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
  60         switch v1.Kind() {
  61         case Array:
  62                 if v1.Len() != v2.Len() {
  63                         return false
  64                 }
  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                 for i := 0; i < v1.Len(); i++ {
  79                         if !deepValueEqual(v1.Index(i), v2.Index(i), visited, depth+1) {
  80                                 return false
  81                         }
  82                 }
  83                 return true
  84         case Interface:
  85                 if v1.IsNil() || v2.IsNil() {
  86                         return v1.IsNil() == v2.IsNil()
  87                 }
  88                 return deepValueEqual(v1.Elem(), v2.Elem(), visited, depth+1)
  89         case Ptr:
  90                 return deepValueEqual(v1.Elem(), v2.Elem(), visited, depth+1)
  91         case Struct:
  92                 for i, n := 0, v1.NumField(); i < n; i++ {
  93                         if !deepValueEqual(v1.Field(i), v2.Field(i), visited, depth+1) {
  94                                 return false
  95                         }
  96                 }
  97                 return true
  98         case Map:
  99                 if v1.IsNil() != v2.IsNil() {
 100                         return false
 101                 }
 102                 if v1.Len() != v2.Len() {
 103                         return false
 104                 }
 105                 for _, k := range v1.MapKeys() {
 106                         if !deepValueEqual(v1.MapIndex(k), v2.MapIndex(k), visited, depth+1) {
 107                                 return false
 108                         }
 109                 }
 110                 return true
 111         default:
 112                 // Normal equality suffices
 113                 return valueInterface(v1, false) == valueInterface(v2, false)
 114         }
 115
 116         panic("Not reached")
 117 }
 118
 119 // DeepEqual tests for deep equality. It uses normal == equality where possible
 120 // but will scan members of arrays, slices, and fields of structs. It correctly
 121 // handles recursive types.
 122 func DeepEqual(a1, a2 interface{}) bool {
 123         if a1 == nil || a2 == nil {
 124                 return a1 == a2
 125         }
 126         v1 := ValueOf(a1)
 127         v2 := ValueOf(a2)
 128         if v1.Type() != v2.Type() {
 129                 return false
 130         }
 131         return deepValueEqual(v1, v2, make(map[uintptr]*visit), 0)
 132 }