-
Notifications
You must be signed in to change notification settings - Fork 16
/
subset.go
125 lines (115 loc) · 3.67 KB
/
subset.go
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
package akkacluster
import (
"reflect"
"unsafe"
)
// Problem statement: we have a baseline Kubernetes resource, and a live resource, and need
// to decide if they are out of sync, meaning the live resource doesn't match our baseline.
// The live resource has timestamps, uids, and other downstream ephemera that we want to ignore
// for purposes of deciding "is the live resource the same as the baseline?" We want the subset.
//
// Alternative approach to this problem is to convert objects to JSON--getting their exported
// and normalized form--and compare those. A challenge with that approach is dealing with
// default values which may be hard to detect once converted, like time.Time.
// SubsetEqual (A,B) returns true if A is a subset of B.
// This allows us to focus on a smaller set of required fields and ignore other fields
// that have downstream mutations to objects like creationTimestamp, uid, resourceVersion.
// The algorithm here is similar to reflect.DeepCopy, in that we use reflection to walk
// a potentially recursive tree. For comparison, we ignore empty or zero value fields in A.
func SubsetEqual(subset, superset interface{}) bool {
t := newTreeWalk()
return t.subsetValueEqual(reflect.ValueOf(subset), reflect.ValueOf(superset))
}
type treeWalk struct {
matches int
visited map[node]bool
}
func newTreeWalk() *treeWalk {
t := treeWalk{}
t.visited = make(map[node]bool)
return &t
}
// track visited nodes to short circuit recursion
type node struct {
a1 unsafe.Pointer
a2 unsafe.Pointer
typ reflect.Type
}
// Tests for subset equality using reflected types.
func (t *treeWalk) subsetValueEqual(subset, superset reflect.Value) bool {
// if subset side is undefined, then nothing to compare
if !subset.IsValid() {
return true
}
// sanity check, rest of code assume same type on both sides
if !superset.IsValid() {
return false
}
if subset.Type() != superset.Type() {
return false
}
// short circuit references already seen
isRef := func(k reflect.Kind) bool {
switch k {
case reflect.Map, reflect.Slice, reflect.Ptr, reflect.Interface:
return true
}
return false
}
if subset.CanAddr() && superset.CanAddr() && isRef(subset.Kind()) {
n := node{
unsafe.Pointer(subset.UnsafeAddr()),
unsafe.Pointer(superset.UnsafeAddr()),
subset.Type(),
}
if t.visited[n] {
return true
}
t.visited[n] = true
}
// walk tree
switch subset.Kind() {
case reflect.Array, reflect.Slice:
// recursive subset: superset may have extra elements at the end, only the subset members must match
if superset.Len() < subset.Len() {
return false
}
for i := 0; i < subset.Len(); i++ {
if !t.subsetValueEqual(subset.Index(i), superset.Index(i)) {
return false
}
}
return true
case reflect.Interface, reflect.Ptr:
return t.subsetValueEqual(subset.Elem(), superset.Elem())
case reflect.Struct:
for i, n := 0, subset.NumField(); i < n; i++ {
if !t.subsetValueEqual(subset.Field(i), superset.Field(i)) {
return false
}
}
return true
case reflect.Map:
for _, k := range subset.MapKeys() {
if !t.subsetValueEqual(subset.MapIndex(k), superset.MapIndex(k)) {
return false
}
}
return true
default:
// Leaf node: if exported, non-default value, compare subset with superset.
if subset.CanInterface() {
// Ignore default values, like empty string, bool false, zero int... :-|
// If needed, could be more selective in the kinds of zeros ignored.
if subset.Interface() == reflect.Zero(subset.Type()).Interface() {
return true
}
if subset.Interface() == superset.Interface() {
t.matches++
return true
}
return false
}
return true // Ignore non-exported opaque internal fields, like time.Time{}.
}
}