forked from samsarahq/thunder
-
Notifications
You must be signed in to change notification settings - Fork 0
/
merge.go
170 lines (149 loc) · 4.1 KB
/
merge.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
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
package merge
import (
"fmt"
"reflect"
"strconv"
)
const indicesReorderedKey = "$"
// Merge merges an update diff into the previous version of a JSON object,
// and returns the updated version.
//
// It effectively reverses the diff algorithm implemented in package diff.
func Merge(prev interface{}, diff interface{}) (interface{}, error) {
d, ok := diff.(map[string]interface{})
if !ok {
return mergeReplaced(diff)
}
switch prev := prev.(type) {
case map[string]interface{}:
return mergeMap(prev, d)
case []interface{}:
return mergeArray(prev, d)
}
return nil, nil
}
// mergeMap applies a delta to a map.
func mergeMap(prev map[string]interface{}, diff map[string]interface{}) (map[string]interface{}, error) {
new := make(map[string]interface{})
// Update existing fields.
for k, v := range prev {
d, ok := diff[k]
if !ok {
// No change.
new[k] = v
} else if !isRemoved(d) {
// Updated, but not removed.
newV, err := Merge(v, d)
if err != nil {
return nil, err
}
new[k] = newV
}
}
// Merge in new fields.
for k, d := range diff {
if _, ok := prev[k]; !ok {
newV, err := mergeReplaced(d)
if err != nil {
return nil, err
}
new[k] = newV
}
}
return new, nil
}
// mergeArray applies a delta to an array.
func mergeArray(prev []interface{}, diff map[string]interface{}) ([]interface{}, error) {
var new []interface{}
// Reorder elements if needed.
if compressedIndices, ok := diff[indicesReorderedKey]; ok {
reorderedIndices, err := uncompressIndices(compressedIndices)
if err != nil {
return nil, err
}
new = make([]interface{}, len(reorderedIndices))
for i, index := range reorderedIndices {
if index != -1 {
new[i] = prev[index]
}
}
} else {
new = make([]interface{}, len(prev))
for i := range prev {
new[i] = prev[i]
}
}
// Update complex elements.
for k := range diff {
if k == indicesReorderedKey {
continue
}
index, err := strconv.Atoi(k)
if err != nil {
return nil, fmt.Errorf("mergeArray: key cannot be converted to an integer. key: %s", k)
}
v := new[index]
newV, err := Merge(v, diff[k])
if err != nil {
return nil, err
}
new[index] = newV
}
return new, nil
}
// mergeReplaced applies a replacement delta of a scalar or complex field.
func mergeReplaced(diff interface{}) (interface{}, error) {
switch diff := diff.(type) {
case bool, int, int8, int16, int32, int64,
uint, uint8, uint16, uint32, uint64,
float32, float64, string:
// Pass through scalar values.
return diff, nil
default:
// Extract all other values.
d, ok := diff.([]interface{})
if !ok || len(d) == 0 {
return nil, fmt.Errorf("mergeReplaced: diff is not an array of length 1: %v", diff)
}
return d[0], nil
}
}
// isRemoved determines if the delta represents a remove;
// removes are represented by an empty array.
func isRemoved(delta interface{}) bool {
d, ok := delta.([]interface{})
return (ok && len(d) == 0)
}
// uncompressIndices uncompresses the compressed representation of reordered indices,
// and returns the expanded new ordering.
func uncompressIndices(indices interface{}) ([]int, error) {
compressedIndices, ok := indices.([]interface{})
if !ok {
return nil, fmt.Errorf("uncompressIndices: indices is not an array: %v", indices)
}
var uncompressedIndices []int
for _, index := range compressedIndices {
switch index := index.(type) {
case []interface{}:
if len(index) != 2 {
return nil, fmt.Errorf("uncompressIndices: unexpected index array length: %v", index)
}
start, ok := index[0].(float64)
if !ok {
return nil, fmt.Errorf("uncompressIndices: index array[0] is not a number: %v", index[0])
}
end, ok := index[1].(float64)
if !ok {
return nil, fmt.Errorf("uncompressIndices: index array[1] is not a number: %v", index[1])
}
for i := start; i <= end; i++ {
uncompressedIndices = append(uncompressedIndices, int(i))
}
case float64:
uncompressedIndices = append(uncompressedIndices, int(index))
default:
return nil, fmt.Errorf("uncompressIndices: unexpected index type: %v", reflect.TypeOf(index))
}
}
return uncompressedIndices, nil
}