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;
    }