blob: 6806c4c200b4548f91698e09b2cb489c71d075d3 [file] [log] [blame]
Matthias Andreas Benkard832a54e2019-01-29 09:27:38 +01001package jsonpatch
2
3import (
4 "bytes"
5 "encoding/json"
6 "fmt"
7 "reflect"
8)
9
10func merge(cur, patch *lazyNode, mergeMerge bool) *lazyNode {
11 curDoc, err := cur.intoDoc()
12
13 if err != nil {
14 pruneNulls(patch)
15 return patch
16 }
17
18 patchDoc, err := patch.intoDoc()
19
20 if err != nil {
21 return patch
22 }
23
24 mergeDocs(curDoc, patchDoc, mergeMerge)
25
26 return cur
27}
28
29func mergeDocs(doc, patch *partialDoc, mergeMerge bool) {
30 for k, v := range *patch {
31 if v == nil {
32 if mergeMerge {
33 (*doc)[k] = nil
34 } else {
35 delete(*doc, k)
36 }
37 } else {
38 cur, ok := (*doc)[k]
39
40 if !ok || cur == nil {
41 pruneNulls(v)
42 (*doc)[k] = v
43 } else {
44 (*doc)[k] = merge(cur, v, mergeMerge)
45 }
46 }
47 }
48}
49
50func pruneNulls(n *lazyNode) {
51 sub, err := n.intoDoc()
52
53 if err == nil {
54 pruneDocNulls(sub)
55 } else {
56 ary, err := n.intoAry()
57
58 if err == nil {
59 pruneAryNulls(ary)
60 }
61 }
62}
63
64func pruneDocNulls(doc *partialDoc) *partialDoc {
65 for k, v := range *doc {
66 if v == nil {
67 delete(*doc, k)
68 } else {
69 pruneNulls(v)
70 }
71 }
72
73 return doc
74}
75
76func pruneAryNulls(ary *partialArray) *partialArray {
77 newAry := []*lazyNode{}
78
79 for _, v := range *ary {
80 if v != nil {
81 pruneNulls(v)
82 newAry = append(newAry, v)
83 }
84 }
85
86 *ary = newAry
87
88 return ary
89}
90
91var errBadJSONDoc = fmt.Errorf("Invalid JSON Document")
92var errBadJSONPatch = fmt.Errorf("Invalid JSON Patch")
93var errBadMergeTypes = fmt.Errorf("Mismatched JSON Documents")
94
95// MergeMergePatches merges two merge patches together, such that
96// applying this resulting merged merge patch to a document yields the same
97// as merging each merge patch to the document in succession.
98func MergeMergePatches(patch1Data, patch2Data []byte) ([]byte, error) {
99 return doMergePatch(patch1Data, patch2Data, true)
100}
101
102// MergePatch merges the patchData into the docData.
103func MergePatch(docData, patchData []byte) ([]byte, error) {
104 return doMergePatch(docData, patchData, false)
105}
106
107func doMergePatch(docData, patchData []byte, mergeMerge bool) ([]byte, error) {
108 doc := &partialDoc{}
109
110 docErr := json.Unmarshal(docData, doc)
111
112 patch := &partialDoc{}
113
114 patchErr := json.Unmarshal(patchData, patch)
115
116 if _, ok := docErr.(*json.SyntaxError); ok {
117 return nil, errBadJSONDoc
118 }
119
120 if _, ok := patchErr.(*json.SyntaxError); ok {
121 return nil, errBadJSONPatch
122 }
123
124 if docErr == nil && *doc == nil {
125 return nil, errBadJSONDoc
126 }
127
128 if patchErr == nil && *patch == nil {
129 return nil, errBadJSONPatch
130 }
131
132 if docErr != nil || patchErr != nil {
133 // Not an error, just not a doc, so we turn straight into the patch
134 if patchErr == nil {
135 if mergeMerge {
136 doc = patch
137 } else {
138 doc = pruneDocNulls(patch)
139 }
140 } else {
141 patchAry := &partialArray{}
142 patchErr = json.Unmarshal(patchData, patchAry)
143
144 if patchErr != nil {
145 return nil, errBadJSONPatch
146 }
147
148 pruneAryNulls(patchAry)
149
150 out, patchErr := json.Marshal(patchAry)
151
152 if patchErr != nil {
153 return nil, errBadJSONPatch
154 }
155
156 return out, nil
157 }
158 } else {
159 mergeDocs(doc, patch, mergeMerge)
160 }
161
162 return json.Marshal(doc)
163}
164
165// resemblesJSONArray indicates whether the byte-slice "appears" to be
166// a JSON array or not.
167// False-positives are possible, as this function does not check the internal
168// structure of the array. It only checks that the outer syntax is present and
169// correct.
170func resemblesJSONArray(input []byte) bool {
171 input = bytes.TrimSpace(input)
172
173 hasPrefix := bytes.HasPrefix(input, []byte("["))
174 hasSuffix := bytes.HasSuffix(input, []byte("]"))
175
176 return hasPrefix && hasSuffix
177}
178
179// CreateMergePatch will return a merge patch document capable of converting
180// the original document(s) to the modified document(s).
181// The parameters can be bytes of either two JSON Documents, or two arrays of
182// JSON documents.
183// The merge patch returned follows the specification defined at http://tools.ietf.org/html/draft-ietf-appsawg-json-merge-patch-07
184func CreateMergePatch(originalJSON, modifiedJSON []byte) ([]byte, error) {
185 originalResemblesArray := resemblesJSONArray(originalJSON)
186 modifiedResemblesArray := resemblesJSONArray(modifiedJSON)
187
188 // Do both byte-slices seem like JSON arrays?
189 if originalResemblesArray && modifiedResemblesArray {
190 return createArrayMergePatch(originalJSON, modifiedJSON)
191 }
192
193 // Are both byte-slices are not arrays? Then they are likely JSON objects...
194 if !originalResemblesArray && !modifiedResemblesArray {
195 return createObjectMergePatch(originalJSON, modifiedJSON)
196 }
197
198 // None of the above? Then return an error because of mismatched types.
199 return nil, errBadMergeTypes
200}
201
202// createObjectMergePatch will return a merge-patch document capable of
203// converting the original document to the modified document.
204func createObjectMergePatch(originalJSON, modifiedJSON []byte) ([]byte, error) {
205 originalDoc := map[string]interface{}{}
206 modifiedDoc := map[string]interface{}{}
207
208 err := json.Unmarshal(originalJSON, &originalDoc)
209 if err != nil {
210 return nil, errBadJSONDoc
211 }
212
213 err = json.Unmarshal(modifiedJSON, &modifiedDoc)
214 if err != nil {
215 return nil, errBadJSONDoc
216 }
217
218 dest, err := getDiff(originalDoc, modifiedDoc)
219 if err != nil {
220 return nil, err
221 }
222
223 return json.Marshal(dest)
224}
225
226// createArrayMergePatch will return an array of merge-patch documents capable
227// of converting the original document to the modified document for each
228// pair of JSON documents provided in the arrays.
229// Arrays of mismatched sizes will result in an error.
230func createArrayMergePatch(originalJSON, modifiedJSON []byte) ([]byte, error) {
231 originalDocs := []json.RawMessage{}
232 modifiedDocs := []json.RawMessage{}
233
234 err := json.Unmarshal(originalJSON, &originalDocs)
235 if err != nil {
236 return nil, errBadJSONDoc
237 }
238
239 err = json.Unmarshal(modifiedJSON, &modifiedDocs)
240 if err != nil {
241 return nil, errBadJSONDoc
242 }
243
244 total := len(originalDocs)
245 if len(modifiedDocs) != total {
246 return nil, errBadJSONDoc
247 }
248
249 result := []json.RawMessage{}
250 for i := 0; i < len(originalDocs); i++ {
251 original := originalDocs[i]
252 modified := modifiedDocs[i]
253
254 patch, err := createObjectMergePatch(original, modified)
255 if err != nil {
256 return nil, err
257 }
258
259 result = append(result, json.RawMessage(patch))
260 }
261
262 return json.Marshal(result)
263}
264
265// Returns true if the array matches (must be json types).
266// As is idiomatic for go, an empty array is not the same as a nil array.
267func matchesArray(a, b []interface{}) bool {
268 if len(a) != len(b) {
269 return false
270 }
271 if (a == nil && b != nil) || (a != nil && b == nil) {
272 return false
273 }
274 for i := range a {
275 if !matchesValue(a[i], b[i]) {
276 return false
277 }
278 }
279 return true
280}
281
282// Returns true if the values matches (must be json types)
283// The types of the values must match, otherwise it will always return false
284// If two map[string]interface{} are given, all elements must match.
285func matchesValue(av, bv interface{}) bool {
286 if reflect.TypeOf(av) != reflect.TypeOf(bv) {
287 return false
288 }
289 switch at := av.(type) {
290 case string:
291 bt := bv.(string)
292 if bt == at {
293 return true
294 }
295 case float64:
296 bt := bv.(float64)
297 if bt == at {
298 return true
299 }
300 case bool:
301 bt := bv.(bool)
302 if bt == at {
303 return true
304 }
305 case nil:
306 // Both nil, fine.
307 return true
308 case map[string]interface{}:
309 bt := bv.(map[string]interface{})
310 for key := range at {
311 if !matchesValue(at[key], bt[key]) {
312 return false
313 }
314 }
315 for key := range bt {
316 if !matchesValue(at[key], bt[key]) {
317 return false
318 }
319 }
320 return true
321 case []interface{}:
322 bt := bv.([]interface{})
323 return matchesArray(at, bt)
324 }
325 return false
326}
327
328// getDiff returns the (recursive) difference between a and b as a map[string]interface{}.
329func getDiff(a, b map[string]interface{}) (map[string]interface{}, error) {
330 into := map[string]interface{}{}
331 for key, bv := range b {
332 av, ok := a[key]
333 // value was added
334 if !ok {
335 into[key] = bv
336 continue
337 }
338 // If types have changed, replace completely
339 if reflect.TypeOf(av) != reflect.TypeOf(bv) {
340 into[key] = bv
341 continue
342 }
343 // Types are the same, compare values
344 switch at := av.(type) {
345 case map[string]interface{}:
346 bt := bv.(map[string]interface{})
347 dst := make(map[string]interface{}, len(bt))
348 dst, err := getDiff(at, bt)
349 if err != nil {
350 return nil, err
351 }
352 if len(dst) > 0 {
353 into[key] = dst
354 }
355 case string, float64, bool:
356 if !matchesValue(av, bv) {
357 into[key] = bv
358 }
359 case []interface{}:
360 bt := bv.([]interface{})
361 if !matchesArray(at, bt) {
362 into[key] = bv
363 }
364 case nil:
365 switch bv.(type) {
366 case nil:
367 // Both nil, fine.
368 default:
369 into[key] = bv
370 }
371 default:
372 panic(fmt.Sprintf("Unknown type:%T in key %s", av, key))
373 }
374 }
375 // Now add all deleted values as nil
376 for key := range a {
377 _, found := b[key]
378 if !found {
379 into[key] = nil
380 }
381 }
382 return into, nil
383}