VS Code如何实现仅对比两个独立文件的双向Diff算法？

没有共同祖先的双文件对比不存在三向合并里的基准参考，本质就是求解两个文本序列的最长公共子序列（LCS），用最少的增删操作标记出两个文件的差异，VS Code的实现是在通用差分方案基础上做了大量工程和可读性优化，核心逻辑如下：

• 核心算法采用改进版Myers差分
  原生Myers算法是业内双端Diff的常用基础方案，核心是把文本拆成固定粒度单元（默认按行拆分，也支持切换到单词、字符粒度），在编辑距离矩阵中寻找从源文件到目标文件的最短转换路径。VS Code没有直接套用原生实现，做了两个关键性能优化：
  一是首尾公共内容裁剪，对比前先把两个文件头部、尾部完全一致的内容块直接裁掉，不进入差分计算流程，大部分日常改代码的场景下，文件只有中间小部分内容变动，这一步能砍掉绝大多数计算量；
  二是加了计算超时阈值，遇到两个几乎完全不相关的超大文件时，不会无限制耗CPU算最短路径，超过预设计算时长就会退化为粗粒度块匹配，保证编辑器不卡顿。
• 针对人类阅读习惯做差异结果后处理
  原生Myers算法只追求“最少编辑步数”，经常出现反直觉的匹配结果：比如两个不相关的函数里都有空行、闭合大括号，算法会为了凑最短路径把这些无意义的通用行配对，导致差异块碎得离谱，完全不符合开发者的阅读逻辑。VS Code在拿到原始差分结果后会做一轮校正：
  • 给空行、通用语法符号（各种括号、行尾分号之类）加匹配惩罚，这类内容不会被优先作为公共匹配锚点，避免错配无关内容
  • 自动对齐语义块边界，如果检测到差异落在函数、类、条件块这类语法结构范围内，会调整差异块的起止位置，不会把一个完整的逻辑块拆成好几个零散的差异段
  • 增加内容移动检测，如果一段内容只是在文件中换了位置、本身没有修改，会标记为移动块，不会显示成“旧位置删除+新位置新增”的冗余差异
• 动态适配对比粒度
  不会全程固定用行粒度计算：行级对比得到大差异块后，会自动在块内做单词、字符级的二次差分，精准标出一行里具体改动的字符；如果对比的文件体积过大，会自动降低匹配精度，优先保证响应速度。
• 格式差异归一化
  内置了可选的预处理规则，开启后会在计算前先统一换行符格式（CRLF/LF）、忽略空白字符变动（缩进调整、尾部空格增减），不会把这类无实际内容变化的格式调整标记为差异。

要说明的是，因为没有共同祖先作为参照，双文件Diff永远不可能完全还原真实的编辑操作，所有优化本质都是在“最短编辑距离”和“符合人类阅读直觉”之间做权衡。

内容的提问来源于stack exchange，提问作者tristone