对于JSON文件的merge优化
在版本控制系统中跨分支合并文件是一个非常复杂的过程。算法的自动合并对此会有很大帮助，但是算法也有其局限性：
- 一是因为其基础原理可能会导致一些”错误”的合并。
- 二是因为常用的
diff3算法仅适用于分成多行的非结构化文本文档。
对于JSON来说，有没有比diff3更优秀的merge算法呢
非结构化文本diff&merge算法的局限性
常规的合并算法 GNU diff3 适用于分成多行的非结构化文本文档。它对于格式化的源代码和类似文档的效果非常好。但是，当用于JSON或xml或类似的基于树的数据格式时，它的效果不尽如人意。
一是它不了解这些语法结构，可能会导致最终的语法错误，例如JSON中出现多余的{，[等问题；二是不能基于语法结构针对性的对齐需要merge的内容，例如结果中map出现相同的key，结果中不同路径中的内容进行了merge。
想要解决上述问题，可以通过后置的JSON格式检查来发现语法错误；也可以通过JSON内容排序，内容切片来减少路径错误对齐。但是这些方案并不能完全解决问题，同时merge过程中的人力成本也没有减少。
结构化JSON并按照结构化后的对象来merge是更好的方案，可以完美解决上述的语法错误和路径对齐错误。更优秀的冲突解决工具也可以大幅度减少merge过程中的人力成本。
JSON文件的diff&merge算法及冲突解决工具
从可借鉴的JSON patch标准开始
JSON（JavaScript Object Notation）文本本身的序列化和反序列化是个很清晰的过程。需要思考的是如何定义JSON的diff和merge。
JSON PatchRFC 6902和RFC 7396在这个标准中定义了一种patch格式，通常应用在HTTP PATCH方法中。
patch格式中包含多个operation对象，其中每个对象必定包含一个元素op，我们关注的主要有三种动作类型，分别是add、remove、replace；
同时还必须包含一个path元素。该成员的值是一个字符串，其中包含一个 JSON 指针值 [RFC6901]，该值引用目标文档中执行操作的位置。
例如：{ "op": "add", "path": "/a/b/c", "value": "foo" }
| op | arg1 | arg2 |
|---|---|---|
| add | path | value |
| remove | path | null |
| replace | path | value |
但是这个patch标准与上述可应用与其他文件的diff不同，一般的diff格式会同时包含left和right的信息，即从A改成B。这里的patch只有改成B这样的信息。
例如这里的remove和replace都没有移除前或替换前的值，与我们想要的diff还是有点差别。
基于上述patch标准，经过一定的改造，且移除掉其他的不需要的op类型，仅包含add、remove、replace。JSONdiff标准可以下述列表的形式表示：
| op | arg1 | arg2 | arg3 |
|---|---|---|---|
| add | path | new_value | null |
| remove | path | old_value | null |
| replace | path | old_value | new_value |
merge算法
根据以往的经验merge算法会将两个diff融合成一个patch，或者生成冲突信息即可，这部分不再详细叙述。
特别的：如何处理JSON中的array
由于array中存在插入这样的操作，index是可能会有变化的。在处理merge上不如map这样简单：不能简单的考虑将index作为路径的key。在处理中大家一般有两种方案：
- 仅考虑将下标作为路径，在进行array的diff&merge时，只考虑下标相同元素比较后的增删改，不考虑可能出现的插入。例如：
[1,2,3,4]变成[1,1,2,3,4]有四个变更，分别是replace,1,2,1；replace,2,3,2；replace,3,4,3；add,4,4。- 优点：算法简单，无二义性
- 缺点：对于有插入操作的数组可能会非常复杂
- 考虑array中object的内容，使用最长公共子字符串算法生成array的内容diff。例如上述的案例：
[1,2,3,4]变成[1,1,2,3,4]有一个变更，是add,1,1。- 优点：对于插入的情况可以进行识别
- 缺点：算法复杂，不能保证完全正确，主要有最小公共子串算法导致的二义性问题。
考虑到成本和效果，选择方案一成本更低，且在约束了JSON结构的前提下可以有更好的结果。目前选择了方案一。
如何进行冲突解决
diff3 是一个历史悠久的merge算法，冲突信息为包含了冲突块的文本。可以清晰的在文本编辑器，甚至是终端中处理冲突。理论上JSON的冲突处理可以借鉴diff3的冲突信息格式，但是在某些特殊的场景下，对,的处理将是灾难性的。具体的可以查看diff3 Format as XML or JSON
使用交互式图形化界面来解决冲突是一个更好的选择，在这样的界面中，原文、diff、冲突都可以清晰的展示。用户只需要点点手指，就可以处理完冲突。
结论
上述JSON结构化merge算法和冲突解决工具在特定的场景下（array以index作为对齐路径）可以大幅度提升JSON文件merge效率。