1package 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}
384