一句话：提出一种线性时间、类型安全的数据类型泛型结构化 diff 算法，最大化共享并提升补丁自动合并率。
版本控制中广泛使用的 UNIX diff 按行比较文件，忽略源码或数据的结构，因此难以对抽象语法树等结构化数据做精确差异与自动合并。本文提出一种数据类型泛型（datatype-generic）的结构化 diff 算法，适用于任意代数数据类型的值：它在保证类型安全的同时最大化源树与目标树之间的共享，且运行时间为线性。作者将该算法实例化到 Lua 抽象语法树，并通过挖掘 GitHub 仓库提交历史进行评估。结果表明，由此生成的补丁常常可以自动合并，即使在现有技术失败的情况下也是如此。
Effectively computing the difference between two version of a source file has become an indispensable part of software development. The de facto standard tool used by most version control systems is the UNIX diff utility, that compares two files on a line-by-line basis without any regard for the structure of the data stored in these files. This paper presents an alternative datatype generic algorithm for computing the difference between two values of any algebraic datatype. This algorithm maximizes sharing between the source and target trees, while still running in linear time. Finally, this paper demonstrates that by instantiating this algorithm to the Lua abstract syntax tree and mining the commit history of repositories found on GitHub, the resulting patches can often be merged automatically, even when existing technology has failed.
@article{paperbot610,
title = {An efficient algorithm for type-safe structural diffing},
author = {Victor Cacciari Miraldo and Wouter Swierstra},
journal = {Proceedings of the ACM on Programming Languages},
volume = {3},
number = {ICFP},
year = {2019},
doi = {10.1145/3341717}
}