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 package com.linecorp.centraldogma.internal.jsonpatch;
36
37 import static com.linecorp.centraldogma.internal.jsonpatch.JsonPatchUtil.encodeSegment;
38 import static java.util.Objects.requireNonNull;
39
40 import java.io.IOException;
41 import java.util.HashMap;
42 import java.util.Iterator;
43 import java.util.List;
44 import java.util.Map;
45 import java.util.Set;
46 import java.util.TreeSet;
47
48 import com.fasterxml.jackson.annotation.JsonCreator;
49 import com.fasterxml.jackson.core.JsonGenerator;
50 import com.fasterxml.jackson.core.JsonPointer;
51 import com.fasterxml.jackson.databind.JsonMappingException;
52 import com.fasterxml.jackson.databind.JsonNode;
53 import com.fasterxml.jackson.databind.JsonSerializable;
54 import com.fasterxml.jackson.databind.SerializerProvider;
55 import com.fasterxml.jackson.databind.jsontype.TypeSerializer;
56 import com.fasterxml.jackson.databind.node.ArrayNode;
57 import com.fasterxml.jackson.databind.node.JsonNodeType;
58 import com.fasterxml.jackson.databind.node.ObjectNode;
59 import com.google.common.annotations.VisibleForTesting;
60 import com.google.common.base.Equivalence;
61 import com.google.common.collect.ImmutableList;
62 import com.google.common.collect.Iterators;
63 import com.google.common.collect.Sets;
64
65 import com.linecorp.centraldogma.internal.Jackson;
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 public final class JsonPatch implements JsonSerializable {
124
125 private static final Equivalence<JsonNode> EQUIVALENCE = JsonNumEquals.getInstance();
126 private static final JsonPointer EMPTY_JSON_POINTER = JsonPointer.compile("");
127 private static final JsonPointer END_OF_ARRAY_POINTER = JsonPointer.compile("/-");
128
129
130
131
132
133
134
135
136
137 public static JsonPatch fromJson(final JsonNode node) throws IOException {
138 requireNonNull(node, "node");
139 try {
140 return Jackson.treeToValue(node, JsonPatch.class);
141 } catch (JsonMappingException e) {
142 throw new JsonPatchException("invalid JSON patch", e);
143 }
144 }
145
146
147
148
149
150
151
152
153
154 public static JsonPatch generate(final JsonNode source, final JsonNode target, ReplaceMode replaceMode) {
155 requireNonNull(source, "source");
156 requireNonNull(target, "target");
157 final DiffProcessor processor = new DiffProcessor(replaceMode, () -> unchangedValues(source, target));
158 generateDiffs(processor, EMPTY_JSON_POINTER, source, target);
159 return processor.getPatch();
160 }
161
162 private static void generateDiffs(final DiffProcessor processor, final JsonPointer pointer,
163 final JsonNode source, final JsonNode target) {
164
165 if (EQUIVALENCE.equivalent(source, target)) {
166 return;
167 }
168
169 final JsonNodeType sourceType = source.getNodeType();
170 final JsonNodeType targetType = target.getNodeType();
171
172
173
174
175 if (sourceType != targetType) {
176 processor.valueReplaced(pointer, source, target);
177 return;
178 }
179
180
181
182
183
184
185
186 if (!source.isContainerNode()) {
187 processor.valueReplaced(pointer, source, target);
188 return;
189 }
190
191
192
193
194
195 if (sourceType == JsonNodeType.OBJECT) {
196 generateObjectDiffs(processor, pointer, (ObjectNode) source, (ObjectNode) target);
197 } else {
198
199 generateArrayDiffs(processor, pointer, (ArrayNode) source, (ArrayNode) target);
200 }
201 }
202
203 private static void generateObjectDiffs(final DiffProcessor processor, final JsonPointer pointer,
204 final ObjectNode source, final ObjectNode target) {
205
206 final Set<String> sourceFields = new TreeSet<>();
207 Iterators.addAll(sourceFields, source.fieldNames());
208 final Set<String> targetFields = new TreeSet<>();
209 Iterators.addAll(targetFields, target.fieldNames());
210
211 for (final String field : Sets.difference(sourceFields, targetFields)) {
212 processor.valueRemoved(pointer.append(JsonPointer.valueOf(encodeSegment(field))));
213 }
214
215 for (final String field : Sets.difference(targetFields, sourceFields)) {
216 processor.valueAdded(pointer.append(JsonPointer.valueOf(encodeSegment(field))), target.get(field));
217 }
218
219 for (final String field : Sets.intersection(sourceFields, targetFields)) {
220 generateDiffs(processor, pointer.append(JsonPointer.valueOf(encodeSegment(field))),
221 source.get(field), target.get(field));
222 }
223 }
224
225 private static void generateArrayDiffs(final DiffProcessor processor, final JsonPointer pointer,
226 final ArrayNode source, final ArrayNode target) {
227 final int sourceSize = source.size();
228 final int targetSize = target.size();
229 final int size = Math.min(sourceSize, targetSize);
230
231
232
233
234
235 for (int index = size; index < sourceSize; index++) {
236 processor.valueRemoved(pointer.append(JsonPointer.valueOf("/" + size)));
237 }
238
239 for (int index = 0; index < size; index++) {
240 generateDiffs(processor, pointer.append(JsonPointer.valueOf("/" + index)),
241 source.get(index), target.get(index));
242 }
243
244
245 for (int index = size; index < targetSize; index++) {
246 processor.valueAdded(pointer.append(END_OF_ARRAY_POINTER), target.get(index));
247 }
248 }
249
250 @VisibleForTesting
251 static Map<JsonPointer, JsonNode> unchangedValues(final JsonNode source, final JsonNode target) {
252 final Map<JsonPointer, JsonNode> ret = new HashMap<>();
253 computeUnchanged(ret, EMPTY_JSON_POINTER, source, target);
254 return ret;
255 }
256
257 private static void computeUnchanged(final Map<JsonPointer, JsonNode> ret, final JsonPointer pointer,
258 final JsonNode source, final JsonNode target) {
259 if (EQUIVALENCE.equivalent(source, target)) {
260 ret.put(pointer, target);
261 return;
262 }
263
264 final JsonNodeType sourceType = source.getNodeType();
265 final JsonNodeType targetType = target.getNodeType();
266
267 if (sourceType != targetType) {
268 return;
269 }
270
271
272
273 switch (sourceType) {
274 case OBJECT:
275 computeUnchangedObject(ret, pointer, source, target);
276 break;
277 case ARRAY:
278 computeUnchangedArray(ret, pointer, source, target);
279 break;
280 default:
281
282 }
283 }
284
285 private static void computeUnchangedObject(final Map<JsonPointer, JsonNode> ret, final JsonPointer pointer,
286 final JsonNode source, final JsonNode target) {
287 final Iterator<String> sourceFields = source.fieldNames();
288 while (sourceFields.hasNext()) {
289 final String name = sourceFields.next();
290 if (!target.has(name)) {
291 continue;
292 }
293 computeUnchanged(ret, pointer.append(JsonPointer.valueOf(encodeSegment(name))),
294 source.get(name), target.get(name));
295 }
296 }
297
298 private static void computeUnchangedArray(final Map<JsonPointer, JsonNode> ret, final JsonPointer pointer,
299 final JsonNode source, final JsonNode target) {
300 final int size = Math.min(source.size(), target.size());
301 for (int i = 0; i < size; i++) {
302 computeUnchanged(ret, pointer.append(JsonPointer.valueOf("/" + i)),
303 source.get(i), target.get(i));
304 }
305 }
306
307
308
309
310 private final List<JsonPatchOperation> operations;
311
312
313
314
315
316
317
318 @JsonCreator
319 JsonPatch(final List<JsonPatchOperation> operations) {
320 this.operations = ImmutableList.copyOf(operations);
321 }
322
323
324
325
326 public boolean isEmpty() {
327 return operations.isEmpty();
328 }
329
330
331
332
333 public List<JsonPatchOperation> operations() {
334 return operations;
335 }
336
337
338
339
340
341
342
343
344
345 public JsonNode apply(final JsonNode node) {
346 requireNonNull(node, "node");
347 JsonNode ret = node.deepCopy();
348 for (final JsonPatchOperation operation : operations) {
349 ret = operation.apply(ret);
350 }
351
352 return ret;
353 }
354
355
356
357
358 public ArrayNode toJson() {
359 return (ArrayNode) Jackson.valueToTree(this);
360 }
361
362 @Override
363 public String toString() {
364 return operations.toString();
365 }
366
367 @Override
368 public void serialize(final JsonGenerator jgen, final SerializerProvider provider) throws IOException {
369 jgen.writeStartArray();
370 for (final JsonPatchOperation op : operations) {
371 op.serialize(jgen, provider);
372 }
373 jgen.writeEndArray();
374 }
375
376 @Override
377 public void serializeWithType(final JsonGenerator jgen,
378 final SerializerProvider provider, final TypeSerializer typeSer)
379 throws IOException {
380 serialize(jgen, provider);
381 }
382 }