summaryrefslogtreecommitdiff
path: root/libgo/go/reflect/deepequal.go
blob: a50925e51e68151bafb3f13e63a446c7f6118873 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Deep equality test via reflection

package reflect


// During deepValueEqual, must keep track of checks that are
// in progress.  The comparison algorithm assumes that all
// checks in progress are true when it reencounters them.
// Visited are stored in a map indexed by 17 * a1 + a2;
type visit struct {
	a1   uintptr
	a2   uintptr
	typ  Type
	next *visit
}

// Tests for deep equality using reflected types. The map argument tracks
// comparisons that have already been seen, which allows short circuiting on
// recursive types.
func deepValueEqual(v1, v2 Value, visited map[uintptr]*visit, depth int) bool {
	if v1 == nil || v2 == nil {
		return v1 == v2
	}
	if v1.Type() != v2.Type() {
		return false
	}

	// if depth > 10 { panic("deepValueEqual") }	// for debugging

	addr1 := v1.Addr()
	addr2 := v2.Addr()
	if addr1 > addr2 {
		// Canonicalize order to reduce number of entries in visited.
		addr1, addr2 = addr2, addr1
	}

	// Short circuit if references are identical ...
	if addr1 == addr2 {
		return true
	}

	// ... or already seen
	h := 17*addr1 + addr2
	seen := visited[h]
	typ := v1.Type()
	for p := seen; p != nil; p = p.next {
		if p.a1 == addr1 && p.a2 == addr2 && p.typ == typ {
			return true
		}
	}

	// Remember for later.
	visited[h] = &visit{addr1, addr2, typ, seen}

	switch v := v1.(type) {
	case *ArrayValue:
		arr1 := v
		arr2 := v2.(*ArrayValue)
		if arr1.Len() != arr2.Len() {
			return false
		}
		for i := 0; i < arr1.Len(); i++ {
			if !deepValueEqual(arr1.Elem(i), arr2.Elem(i), visited, depth+1) {
				return false
			}
		}
		return true
	case *SliceValue:
		arr1 := v
		arr2 := v2.(*SliceValue)
		if arr1.Len() != arr2.Len() {
			return false
		}
		for i := 0; i < arr1.Len(); i++ {
			if !deepValueEqual(arr1.Elem(i), arr2.Elem(i), visited, depth+1) {
				return false
			}
		}
		return true
	case *InterfaceValue:
		i1 := v.Interface()
		i2 := v2.Interface()
		if i1 == nil || i2 == nil {
			return i1 == i2
		}
		return deepValueEqual(NewValue(i1), NewValue(i2), visited, depth+1)
	case *PtrValue:
		return deepValueEqual(v.Elem(), v2.(*PtrValue).Elem(), visited, depth+1)
	case *StructValue:
		struct1 := v
		struct2 := v2.(*StructValue)
		for i, n := 0, v.NumField(); i < n; i++ {
			if !deepValueEqual(struct1.Field(i), struct2.Field(i), visited, depth+1) {
				return false
			}
		}
		return true
	case *MapValue:
		map1 := v
		map2 := v2.(*MapValue)
		if map1.Len() != map2.Len() {
			return false
		}
		for _, k := range map1.Keys() {
			if !deepValueEqual(map1.Elem(k), map2.Elem(k), visited, depth+1) {
				return false
			}
		}
		return true
	default:
		// Normal equality suffices
		return v1.Interface() == v2.Interface()
	}

	panic("Not reached")
}

// DeepEqual tests for deep equality. It uses normal == equality where possible
// but will scan members of arrays, slices, and fields of structs. It correctly
// handles recursive types.
func DeepEqual(a1, a2 interface{}) bool {
	if a1 == nil || a2 == nil {
		return a1 == a2
	}
	v1 := NewValue(a1)
	v2 := NewValue(a2)
	if v1.Type() != v2.Type() {
		return false
	}
	return deepValueEqual(v1, v2, make(map[uintptr]*visit), 0)
}