Jean-Rémy Falleri, Floréal Morandat, Xavier Blanc, Matias Martinez, and Martin Monperrus. 2014. Fine-grained and accurate source code differencing. In Proceedings of the 29th ACM/IEEE international conference on Automated software engineering (ASE ‘14). ACM, New York, NY, USA, 313-324. DOI=http://dx.doi.org/10.1145/2642937.2642982
目的
在 AST 上做代码差别比较, 相对于基于行差分的 diff, 细粒度的展现代码变化.
AST 差分之前也有, 这篇文章主要是
- 除了增加删除结点, 还考虑的结点的移动
- 提升算法效率
- 自称 “目的不是找到算法上最优的 edit script, 而是找到反映开发者改动意图的 edit script”. 这就是你算法里面一堆工程 hack 的理由么.
概念
-
edit script: 代码片段 A 经过怎么样的变化到了代码片段 B, 经过的变化就是 edit script.
-
AST: 有序多叉树, 每个节点 \( v \) 有一个 \( label(v) \) (可以视为结点类型), 以及 \( val(v) \) (一个字符串). 结点的位置唯一地由其父亲是谁, 以及该结点是其父亲的第几个儿子决定.
-
AST 子树同构: 对应位置 \(label\) 和 \(val\) 相等. 如果 \(T_1\) 和 \(T_2\) 同构, 显然那么在同一位置的后代也同构. 利用 Hash 码在 \(O(1)\) 时间内判定.
-
节点映射: \( M \in T_1 \times T_2 \), 而且不会有同一个 \( t_1 \in T_1 \) 和多个 \( t_2 \in T_2 \) 有关系或者倒过来的情况.
算法
考虑差分 \( T_1 \) 和 \( T_2 \), 分两步
- 在 \( T_1 \), \( T_2 \) 相似的结点间建立 mapping (注意 mapping 并不是完全同构的结点, 而是相似的结点)
- 通过 mapping 生成 edit script. 这个已经有前人算法.
基本思想
论文自称模仿资深程序员的行为, 首先寻找大块的未变化代码, 以此为基准, 找到代码块的对应, 然后再去仔细看每个部分有那些细微的变化.
分为三步
- top-down, (从大到小的顺序) 寻找所谓 anchor mapping
- bottom-up, 寻找所谓的 container mapping
- bottom-up, 寻找所谓的 recovery mapping
dice 函数
\(dice(t_1, t_2, M) = \frac{2 |M|}{|t_1| + |t_2|} \in [0, 1]\)
用来衡量两个 AST 子树的在我们的相似映射 \( M\) 下的相似程度.
Anchor Mapping
寻找大块的同构子树 i.e. 大块的没有变化的代码块.
它只考虑高度不小于 \(minHeight\) 的子树, 一般要取 \(minHeight\) 大于 1 不然 int 之类的到处匹配非常尴尬.
- 如果 \( (t_1, t_2) \) 同构, 而且 \( t_1 \) 只和 \( t_2 \) 同构, 反过来也是, 那么 \( M \) 里面加入 \( (t_1, t_2) \)
- 如果有多个, 那么取上下文最相似的, 也就是 \( dice(parent(t_1), parent(t_2), M) \) 最大的.
Container Mapping
寻找包含 anchor mapping 的更大块的对应.
\( (t_1, t_2) \) 形成 container mapping 的条件是
- 没有已经在 anchor mapping 中
- 他们有后代在 anchor mapping 中
满足这两个条件就可能形成一个 container mapping.
因此直接对于每一个可能在 container mapping 中的 \( t_1 \) , 选择的 \( t_2 \) 使得上述条件满足, 而且最大化子树 \( t_1\) 和 \(t_2\) 的相似度 \( dice(t_1, t_2, M) \).
当然如果最大的 \( dice(t_1, t_2, M) \) 都很小, 那就不用记录 \( (t_1, t_2) \) 到 \( M \) 中.
Recovery Mapping
recovery mapping 是指 container mapping 中, 没有被映射的其他部分. 这部分可能包含细微的修改.
对于 container mapping 中每一对 \( (t_1, t_2) \), 使用一个 opt 算法
在不考虑 move 的情况下 求出 recovery mappings.
opt 是 \(O(n^3)\) 的, 所以实际中只有在 \( t_1, t_2\) 都比较小的时候才用 opt.
另外, 论文中说
The mappings induced from this edit script [by opt] are added in M if they involve nodes with identical labels.
但是难道作为一个寻找同构的算法 opt 还能弄成 \( label \) 不同?!
依赖的前人工作
Hash 码完成 \(O(1)\) 同构判定:
M. Chilowicz, E. Duris, and G. Roussel. Syntax tree fingerprinting for source code similarity detection. In The 17th International Conference on Program Comprehension, pages 243–247. IEEE Computer Society, 2009.
这里只考虑原文中的同构判定. 考虑子树 \(s\) 的 hash \(H(s)\), 假设 \( s\)的儿子是 \(\langle t_1, t_2 \ldots t_n\rangle \), 那么有 \(H(s) = f(K, H(t_1), H(t_2), \ldots H(t_n))\) 其中 \(f\) 是哈希函数, 通常是 md5 或者 sha1 之类的. \(K\) 是 \(s\) 根节点的结点 hash, 由根结点的类型等决定.
不考虑 move 操作的树差分 (opt)
M. Pawlik and N. Augsten. RTED: a robust algorithm for the tree edit distance. PVLDB, 5(4):334–345, 2011.
安装
主要是 cgum 比较坑. 如果只需要对 java 代码做 diff 那么没有那么麻烦了, 直接从 gumtree 的仓库里下一个编译好的版本运行就好了.
为了安装 cgum (gumtree 的 C parser), 真是闹腾, 又是看已经关闭好久的 issue 又是检查 Dockerfile 终于弄好了.
安装 cgum 可以直接
$ sudo apt install ocaml ocaml-native-compilers
$ git clone https://github.com/GumTreeDiff/cgum.git
$ cd cgum
$ make clean
$ make depend
$ make
$ export PATH=$PATH:`pwd`
之后下载 gumtree 已经编译好的版本, 解压.
$ bin/gumtree webdiff FILE1 FILE2
gumtree 有几个简单的测试例子