Source file src/pkg/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 case Func: 112 if v1.IsNil() && v2.IsNil() { 113 return true 114 } 115 // Can't do better than this: 116 return false 117 default: 118 // Normal equality suffices 119 return valueInterface(v1, false) == valueInterface(v2, false) 120 } 121 122 panic("Not reached") 123 } 124 125 // DeepEqual tests for deep equality. It uses normal == equality where possible 126 // but will scan members of arrays, slices, maps, and fields of structs. It correctly 127 // handles recursive types. Functions are equal only if they are both nil. 128 func DeepEqual(a1, a2 interface{}) bool { 129 if a1 == nil || a2 == nil { 130 return a1 == a2 131 } 132 v1 := ValueOf(a1) 133 v2 := ValueOf(a2) 134 if v1.Type() != v2.Type() { 135 return false 136 } 137 return deepValueEqual(v1, v2, make(map[uintptr]*visit), 0) 138 }