← Back to branch summary

~james-page/ubuntu/utopic/gccgo-go/cgo-support

« back to all changes in this revision

Viewing changes to src/pkg/reflect/deepequal.go

  • Committer: Package Import Robot
  • Author(s): James Page
  • Date: 2014-01-27 09:18:55 UTC
  • Revision ID: package-import@ubuntu.com-20140127091855-zxfshmykfsyyw4b2
Tags: upstream-1.2
Import upstream version 1.2

Show diffs side-by-side

added added

removed removed

Lines of Context:
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 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
                if v1.Len() != v2.Len() {
 
66
                        return false
 
67
                }
 
68
                for i := 0; i < v1.Len(); i++ {
 
69
                        if !deepValueEqual(v1.Index(i), v2.Index(i), visited, depth+1) {
 
70
                                return false
 
71
                        }
 
72
                }
 
73
                return true
 
74
        case Slice:
 
75
                if v1.IsNil() != v2.IsNil() {
 
76
                        return false
 
77
                }
 
78
                if v1.Len() != v2.Len() {
 
79
                        return false
 
80
                }
 
81
                if v1.Pointer() == v2.Pointer() {
 
82
                        return true
 
83
                }
 
84
                for i := 0; i < v1.Len(); i++ {
 
85
                        if !deepValueEqual(v1.Index(i), v2.Index(i), visited, depth+1) {
 
86
                                return false
 
87
                        }
 
88
                }
 
89
                return true
 
90
        case Interface:
 
91
                if v1.IsNil() || v2.IsNil() {
 
92
                        return v1.IsNil() == v2.IsNil()
 
93
                }
 
94
                return deepValueEqual(v1.Elem(), v2.Elem(), visited, depth+1)
 
95
        case Ptr:
 
96
                return deepValueEqual(v1.Elem(), v2.Elem(), visited, depth+1)
 
97
        case Struct:
 
98
                for i, n := 0, v1.NumField(); i < n; i++ {
 
99
                        if !deepValueEqual(v1.Field(i), v2.Field(i), visited, depth+1) {
 
100
                                return false
 
101
                        }
 
102
                }
 
103
                return true
 
104
        case Map:
 
105
                if v1.IsNil() != v2.IsNil() {
 
106
                        return false
 
107
                }
 
108
                if v1.Len() != v2.Len() {
 
109
                        return false
 
110
                }
 
111
                if v1.Pointer() == v2.Pointer() {
 
112
                        return true
 
113
                }
 
114
                for _, k := range v1.MapKeys() {
 
115
                        if !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 tests for deep equality. It uses normal == equality where
 
133
// possible but will scan elements of arrays, slices, maps, and fields of
 
134
// structs. In maps, keys are compared with == but elements use deep
 
135
// equality. DeepEqual correctly handles recursive types. Functions are equal
 
136
// only if they are both nil.
 
137
// An empty slice is not equal to a nil slice.
 
138
func DeepEqual(a1, a2 interface{}) bool {
 
139
        if a1 == nil || a2 == nil {
 
140
                return a1 == a2
 
141
        }
 
142
        v1 := ValueOf(a1)
 
143
        v2 := ValueOf(a2)
 
144
        if v1.Type() != v2.Type() {
 
145
                return false
 
146
        }
 
147
        return deepValueEqual(v1, v2, make(map[visit]bool), 0)
 
148
}