Skip to content

Commit 2388525

Browse files
fgefge
committed
Diff: Add unchanged path detection
The principle is to harvest the structure common to the source and destination JSON trees. As paths to these JSON values will not change, it will be safe to reuse these values in copy operations.
1 parent b3c3343 commit 2388525

3 files changed

Lines changed: 262 additions & 0 deletions

File tree

‎src/main/java/com/github/fge/jsonpatch/diff2/JsonDiff.java‎

Lines changed: 141 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,141 @@
1+
/*
2+
* Copyright (c) 2014, Francis Galiegue (fgaliegue@gmail.com)
3+
*
4+
* This software is dual-licensed under:
5+
*
6+
* - the Lesser General Public License (LGPL) version 3.0 or, at your option, any
7+
* later version;
8+
* - the Apache Software License (ASL) version 2.0.
9+
*
10+
* The text of this file and of both licenses is available at the root of this
11+
* project or, if you have the jar distribution, in directory META-INF/, under
12+
* the names LGPL-3.0.txt and ASL-2.0.txt respectively.
13+
*
14+
* Direct link to the sources:
15+
*
16+
* - LGPL 3.0: https://www.gnu.org/licenses/lgpl-3.0.txt
17+
* - ASL 2.0: http://www.apache.org/licenses/LICENSE-2.0.txt
18+
*/
19+
20+
package com.github.fge.jsonpatch.diff2;
21+
22+
import com.fasterxml.jackson.core.type.TypeReference;
23+
import com.fasterxml.jackson.databind.JsonNode;
24+
import com.fasterxml.jackson.databind.ObjectMapper;
25+
import com.fasterxml.jackson.databind.node.JsonNodeFactory;
26+
import com.github.fge.jackson.JacksonUtils;
27+
import com.github.fge.jackson.JsonNumEquals;
28+
import com.github.fge.jackson.NodeType;
29+
import com.github.fge.jackson.jsonpointer.JsonPointer;
30+
import com.github.fge.jsonpatch.MoveOperation;
31+
import com.google.common.annotations.VisibleForTesting;
32+
import com.google.common.base.Equivalence;
33+
import com.google.common.collect.ImmutableMap;
34+
import com.google.common.collect.Maps;
35+
36+
import javax.annotation.ParametersAreNonnullByDefault;
37+
import java.io.IOException;
38+
import java.util.Iterator;
39+
import java.util.Map;
40+
41+
@ParametersAreNonnullByDefault
42+
public final class JsonDiff
43+
{
44+
private static final Equivalence<JsonNode> EQUIVALENCE
45+
= JsonNumEquals.getInstance();
46+
47+
private JsonDiff()
48+
{
49+
}
50+
51+
@VisibleForTesting
52+
static Map<JsonPointer, JsonNode> getUnchangedValues(final JsonNode first,
53+
final JsonNode second)
54+
{
55+
final Map<JsonPointer, JsonNode> ret = Maps.newHashMap();
56+
computeUnchanged(ret, JsonPointer.empty(), first, second);
57+
return ret;
58+
}
59+
60+
private static void computeUnchanged(final Map<JsonPointer, JsonNode> ret,
61+
final JsonPointer pointer, final JsonNode first, final JsonNode second)
62+
{
63+
if (EQUIVALENCE.equivalent(first, second)) {
64+
ret.put(pointer, second);
65+
return;
66+
}
67+
68+
final NodeType firstType = NodeType.getNodeType(first);
69+
final NodeType secondType = NodeType.getNodeType(second);
70+
71+
if (firstType != secondType)
72+
return; // nothing in common
73+
74+
// We know they are both the same type, so...
75+
76+
switch (firstType) {
77+
case OBJECT:
78+
computeObject(ret, pointer, first, second);
79+
break;
80+
case ARRAY:
81+
computeArray(ret, pointer, first, second);
82+
default:
83+
/* nothing */
84+
}
85+
}
86+
87+
private static void computeObject(final Map<JsonPointer, JsonNode> ret,
88+
final JsonPointer pointer, final JsonNode first, final JsonNode second)
89+
{
90+
final Iterator<String> firstFields = first.fieldNames();
91+
92+
String name;
93+
94+
while (firstFields.hasNext()) {
95+
name = firstFields.next();
96+
if (!second.has(name))
97+
continue;
98+
computeUnchanged(ret, pointer.append(name), first.get(name),
99+
second.get(name));
100+
}
101+
}
102+
103+
private static void computeArray(final Map<JsonPointer, JsonNode> ret,
104+
final JsonPointer pointer, final JsonNode first, final JsonNode second)
105+
{
106+
final int size = Math.min(first.size(), second.size());
107+
108+
for (int i = 0; i < size; i++)
109+
computeUnchanged(ret, pointer.append(i), first.get(i),
110+
second.get(i));
111+
}
112+
113+
public static void main(final String... args)
114+
throws IOException
115+
{
116+
final ImmutableMap.Builder<JsonPointer, JsonNode> builder
117+
= ImmutableMap.builder();
118+
119+
builder.put(JsonPointer.of("a"), JsonNodeFactory.instance.arrayNode());
120+
121+
final ImmutableMap<JsonPointer, JsonNode> map = builder.build();
122+
123+
final ObjectMapper mapper = JacksonUtils.newMapper();
124+
125+
final JsonNode node = mapper.convertValue(map, JsonNode.class);
126+
System.out.println(node);
127+
128+
final TypeReference<Map<JsonPointer, JsonNode>> typeRef
129+
= new TypeReference<Map<JsonPointer, JsonNode>>()
130+
{
131+
};
132+
133+
final Map<JsonPointer, JsonNode> map2
134+
= mapper.readValue(node.traverse(), typeRef);
135+
136+
System.out.println(map2);
137+
138+
System.out.println(mapper.writeValueAsString(new MoveOperation
139+
(JsonPointer.of("a"), JsonPointer.of("b"))));
140+
}
141+
}

‎src/test/java/com/github/fge/jsonpatch/diff2/UnchangedTest.java‎

Lines changed: 78 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,78 @@
1+
/*
2+
* Copyright (c) 2014, Francis Galiegue (fgaliegue@gmail.com)
3+
*
4+
* This software is dual-licensed under:
5+
*
6+
* - the Lesser General Public License (LGPL) version 3.0 or, at your option, any
7+
* later version;
8+
* - the Apache Software License (ASL) version 2.0.
9+
*
10+
* The text of this file and of both licenses is available at the root of this
11+
* project or, if you have the jar distribution, in directory META-INF/, under
12+
* the names LGPL-3.0.txt and ASL-2.0.txt respectively.
13+
*
14+
* Direct link to the sources:
15+
*
16+
* - LGPL 3.0: https://www.gnu.org/licenses/lgpl-3.0.txt
17+
* - ASL 2.0: http://www.apache.org/licenses/LICENSE-2.0.txt
18+
*/
19+
20+
package com.github.fge.jsonpatch.diff2;
21+
22+
import com.fasterxml.jackson.core.type.TypeReference;
23+
import com.fasterxml.jackson.databind.JsonNode;
24+
import com.fasterxml.jackson.databind.ObjectMapper;
25+
import com.github.fge.jackson.JacksonUtils;
26+
import com.github.fge.jackson.JsonLoader;
27+
import com.github.fge.jackson.jsonpointer.JsonPointer;
28+
import com.google.common.collect.Lists;
29+
import org.testng.annotations.DataProvider;
30+
import org.testng.annotations.Test;
31+
32+
import java.io.IOException;
33+
import java.util.Iterator;
34+
import java.util.List;
35+
import java.util.Map;
36+
37+
import static org.testng.Assert.assertEquals;
38+
39+
public final class UnchangedTest
40+
{
41+
private static final ObjectMapper MAPPER = JacksonUtils.newMapper();
42+
private static final TypeReference<Map<JsonPointer, JsonNode>> TYPE_REF
43+
= new TypeReference<Map<JsonPointer, JsonNode>>()
44+
{
45+
};
46+
47+
private final JsonNode testData;
48+
49+
public UnchangedTest()
50+
throws IOException
51+
{
52+
final String resource = "/jsonpatch/diff2/unchanged.json";
53+
testData = JsonLoader.fromResource(resource);
54+
}
55+
56+
@DataProvider
57+
public Iterator<Object[]> getTestData()
58+
throws IOException
59+
{
60+
final List<Object[]> list = Lists.newArrayList();
61+
62+
for (final JsonNode node: testData)
63+
list.add(new Object[] { node.get("first"), node.get("second"),
64+
MAPPER.readValue(node.get("unchanged").traverse(), TYPE_REF)});
65+
66+
return list.iterator();
67+
}
68+
69+
@Test(dataProvider = "getTestData")
70+
public void computeUnchangedValuesWorks(final JsonNode first,
71+
final JsonNode second, final Map<JsonPointer, JsonNode> expected)
72+
{
73+
final Map<JsonPointer, JsonNode> actual
74+
= JsonDiff.getUnchangedValues(first, second);
75+
76+
assertEquals(actual, expected);
77+
}
78+
}

‎src/test/resources/jsonpatch/diff2/unchanged.json‎

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
[
2+
{
3+
"first": 1,
4+
"second": null,
5+
"unchanged": {}
6+
},
7+
{
8+
"first": "hello",
9+
"second": "hello",
10+
"unchanged": { "": "hello" }
11+
},
12+
{
13+
"first": { "a": "b", "c": "d" },
14+
"second": { "a": "x", "c": "d" },
15+
"unchanged": { "/c": "d" }
16+
},
17+
{
18+
"first": [ "hello", "world", 31 ],
19+
"second": [ "goodbye", "world", 31 ],
20+
"unchanged": {
21+
"/1": "world",
22+
"/2": 31
23+
}
24+
},
25+
{
26+
"first": { "a": { "b": "c", "d": [ 1, 2 ] } },
27+
"second": { "a": { "b": "c", "d": [ 0, 2 ] } },
28+
"unchanged": { "/a/b": "c", "/a/d/1": 2 }
29+
},
30+
{
31+
"first": [ 1, 2, { "a": "b", "x": 3 } ],
32+
"second": [ 1, "ooo", { "a": 1, "x": 3 } ],
33+
"unchanged": {
34+
"/0": 1,
35+
"/2/x": 3
36+
}
37+
},
38+
{
39+
"first": [ "a", "b", "c" ],
40+
"second": [ "a", "b", "c" ],
41+
"unchanged": { "": [ "a", "b", "c" ] }
42+
}
43+
]

0 commit comments

Comments
 (0)