zjsonpatch 比较json字符串源码分析

00.结论

通过代码分析，我们可以看到，使用zjsonpatch比较json是以source字符串为基准，
与最大公共子串进行比较，source多则remove srcNode
与最大公共子串进行比较，source少则add targetNode

以下为简单图例:
️lcs 为target和source两个json字符串的最大公共子串。

01.背景

zjsonpatch是一个对json字符串进行操作的java类库。
zjsonpatch github 地址:zjsonpatch
zjsonpatch json字符串比较注释版本version-1.4.6-with-comment
我们使用zjsonpatch 比较下面两个json字符串
target：

{ "list": [{ "id": 1566191147593281395 }, { "id": 1566196494578281356 }, { "id": 1566197027522281110 }] }

source：

{ "list": [{ "id": 1566196494578281356 }, { "id": 1566197027522281110 }] }

示例代码

EnumSet<DiffFlags> flags = DiffFlags.dontNormalizeOpIntoMoveAndCopy().clone(); JsonNode diffResultNode = JsonDiff.asJson(actualNode, expectNode, flags); Iterator<JsonNode> diffJsonNodeIterator = diffResultNode.iterator(); while (diffJsonNodeIterator.hasNext()) { JsonNode node = diffJsonNodeIterator.next(); String op = node.path("op").asText(); String from = node.path("from").asText(); String path = node.path("path").asText(); JsonNode value = node.get("value"); System.out.println("op:"+op+","+"from:"+from+",path:"+path+",value:"+value); } 

打印结果

op:add,from:,path:/list/0,value:{"id":1566191147593281395}

接下来我们就来分析一下zjsonpatch 如何比较json字符串的。

02.过程分析

zjsonpatch版本

<dependency> <groupId>com.flipkart.zjsonpatch</groupId> <artifactId>zjsonpatch</artifactId> <version>0.4.6</version> </dependency>

我在代码里写了比较详细的注释，有兴趣的朋友可以下载 zjsonpatch json字符串比较注释版本version-1.4.6-with-comment 进行测试。

step 1 比较操作主要通过JsonDiff类的 asJson 方法操作。

public static JsonNode asJson(final JsonNode source, final JsonNode target, EnumSet<DiffFlags> flags) { final List<Diff> diffs = new ArrayList<Diff>(); List<Object> path = new ArrayList<Object>(0); // generating diffs in the order of their occurrence //按照资源的顺序构建不同的内容 generateDiffs(diffs, path, source, target); if (!flags.contains(DiffFlags.OMIT_MOVE_OPERATION)) { // Merging remove & add to move operation compactDiffs(diffs); } if (!flags.contains(DiffFlags.OMIT_COPY_OPERATION)) { // Introduce copy operation introduceCopyOperation(source, target, diffs); } return getJsonNodes(diffs, flags); }

step 2 根据jsonNode的类型是NodeType.ARRAY还是NodeType.OBJECT做不同处理

private static void generateDiffs(List<Diff> diffs, List<Object> path, JsonNode source, JsonNode target) { if (!source.equals(target)) { final NodeType sourceType = NodeType.getNodeType(source); final NodeType targetType = NodeType.getNodeType(target); if (sourceType == NodeType.ARRAY && targetType == NodeType.ARRAY) { //both are arrays compareArray(diffs, path, source, target); } else if (sourceType == NodeType.OBJECT && targetType == NodeType.OBJECT) { //both are json compareObjects(diffs, path, source, target); } else { //can be replaced diffs.add(Diff.generateDiff(Operation.REPLACE, path, source, target)); } } }

step 3 如果是NodeType.OBJECT 类型 比较source 和 target的 key，然后递归处理， 比较简单

private static void compareObjects(List<Diff> diffs, List<Object> path, JsonNode source, JsonNode target) { Iterator<String> keysFromSrc = source.fieldNames(); while (keysFromSrc.hasNext()) { String key = keysFromSrc.next(); if (!target.has(key)) { //remove case List<Object> currPath = getPath(path, key); diffs.add(Diff.generateDiff(Operation.REMOVE, currPath, source.get(key))); continue; } List<Object> currPath = getPath(path, key); //根据jsonNode的类型 ARRAY OBJECT 做不同处理 递归调用 generateDiffs(diffs, currPath, source.get(key), target.get(key)); } Iterator<String> keysFromTarget = target.fieldNames(); while (keysFromTarget.hasNext()) { String key = keysFromTarget.next(); if (!source.has(key)) { //add case List<Object> currPath = getPath(path, key); diffs.add(Diff.generateDiff(Operation.ADD, currPath, target.get(key))); } } }

step 4 如果是NodeType.ARRAY 类型 如何比较 是我们这次分析的重点

private static void compareArray(List<Diff> diffs, List<Object> path, JsonNode source, JsonNode target) { List<JsonNode> lcs = getLCS(source, target); //source 指针 int srcIdx = 0; //target 指针 int targetIdx = 0; //lcs 指针 int lcsIdx = 0; //source 尺寸 int srcSize = source.size(); //target 尺寸 int targetSize = target.size(); //lcs 尺寸 int lcsSize = lcs.size(); //数组里的对象坐标 int pos = 0; while (lcsIdx < lcsSize) { JsonNode lcsNode = lcs.get(lcsIdx); JsonNode srcNode = source.get(srcIdx); JsonNode targetNode = target.get(targetIdx); // Both are same as lcs node, nothing to do here // lcs node 和 src target都相同 则所有指针移动 继续比较 if (lcsNode.equals(srcNode) && lcsNode.equals(targetNode)) { srcIdx++; targetIdx++; lcsIdx++; pos++; } else { // src node is same as lcs, but not targetNode //lcs拿到的值和src node值相同 但是和target node值不同 // 说明target比source多，所以source 需要add 当前targetNode if (lcsNode.equals(srcNode)) { //addition List<Object> currPath = getPath(path, pos); //targetNode 需要add 这个path的 node diffs.add(Diff.generateDiff(Operation.ADD, currPath, targetNode)); //数组里的对象坐标指针移动 pos++; //target指针移动 比较target 下一个node targetIdx++; //targetNode node is same as lcs, but not src //lcs拿到的值和target node值相同 但是和src node值不同 //删除操作 数组里的对象坐标指针不移动 //说明source 比 target多 所以需要source remove 当前srcNode } else if (lcsNode.equals(targetNode)) { //removal, List<Object> currPath = getPath(path, pos); //srcNode 需要remove 这个path的 node diffs.add(Diff.generateDiff(Operation.REMOVE, currPath, srcNode)); //source指针移动 比较source 下一个node srcIdx++; } else { List<Object> currPath = getPath(path, pos); //both are unequal to lcs node //如果srcNode 和 targetNode 和 lcsNode都不同，则继续递归比较 generateDiffs(diffs, currPath, srcNode, targetNode); //指针移动 比较source,target 下一个node srcIdx++; targetIdx++; //数组里的对象坐标指针移动 pos++; } } } //最大公共子串和source，target比较完成后， // 检查source 和 target node节点是否都遍历比较完成 // 如果没有完成 则继续递归调用 while ((srcIdx < srcSize) && (targetIdx < targetSize)) { JsonNode srcNode = source.get(srcIdx); JsonNode targetNode = target.get(targetIdx); List<Object> currPath = getPath(path, pos); generateDiffs(diffs, currPath, srcNode, targetNode); srcIdx++; targetIdx++; pos++; } //处理剩余的target node pos = addRemaining(diffs, path, target, pos, targetIdx, targetSize); //处理剩余的source node removeRemaining(diffs, path, pos, srcIdx, srcSize, source); } 

首先获取最大公共字串 getLCS(source, target)的集合，最大公共字串比较结果受到字符串内容顺序影响。

private static List<JsonNode> getLCS(final JsonNode first, final JsonNode second) { return ListUtils.longestCommonSubsequence(InternalUtils.toList((ArrayNode) first), InternalUtils.toList((ArrayNode) second)); }

处理剩余的target node

private static Integer addRemaining(List<Diff> diffs, List<Object> path, JsonNode target, int pos, int targetIdx, int targetSize) { //比较完成之后，剩余的targetNode 需要 add 这个path的 node while (targetIdx < targetSize) { JsonNode jsonNode = target.get(targetIdx); List<Object> currPath = getPath(path, pos); diffs.add(Diff.generateDiff(Operation.ADD, currPath, jsonNode.deepCopy())); pos++; targetIdx++; } return pos; } 

处理剩余的source node

private static Integer removeRemaining(List<Diff> diffs, List<Object> path, int pos, int srcIdx, int srcSize, JsonNode source) { //比较完成之后 剩余的srcNode 需要remove 这个path的 node while (srcIdx < srcSize) { List<Object> currPath = getPath(path, pos); diffs.add(Diff.generateDiff(Operation.REMOVE, currPath, source.get(srcIdx))); srcIdx++; } return pos; }