一句话：提出基于差分测试的分层比较方法自动评估AST映射算法准确性，发现主流算法在20%–36%的文件修订上产生错误映射。
抽象语法树（AST）映射算法广泛用于源代码变更分析，但其准确性（算法在多大程度上捕捉代码演化）此前缺乏评估。本文观察到程序元素通常只有一个最佳映射元素，据此提出分层差分测试方法，自动比较不同算法映射出的语句与token的相似度，判定算法是否产生不准确映射，并邀请12位专家对200条语句进行标注。结果显示该方法精确率为0.98–1.00、召回率为0.65–0.75。在十个Java项目、263,165个文件修订上的大规模研究发现，GumTree、MTDiff与IJM分别在20%–29%、25%–36%、21%–30%的文件修订上产生不准确映射，说明现有最先进算法仍需改进。
Abstract syntax tree (AST) mapping algorithms are widely used to analyze changes in source code. Despite the foundational role of AST mapping algorithms, little effort has been made to evaluate the accuracy of AST mapping algorithms, i.e., the extent to which an algorithm captures the evolution of code. We observe that a program element often has only one best-mapped program element. Based on this observation, we propose a hierarchical approach to automatically compare the similarity of mapped statements and tokens by different algorithms. By performing the comparison, we determine if each of the compared algorithms generates inaccurate mappings for a statement or its tokens. We invite 12 external experts to determine if three commonly used AST mapping algorithms generate accurate mappings for a statement and its tokens for 200 statements. Based on the experts' feedback, we observe that our approach achieves a precision of 0.98–1.00 and a recall of 0.65–0.75. Furthermore, we conduct a large-scale study with a dataset of ten Java projects containing a total of 263,165 file revisions. Our approach determines that GumTree, MTDiff and IJM generate inaccurate mappings for 20%–29%, 25%–36% and 21%–30% of the file revisions, respectively. Our experimental results show that state-of-the-art AST mapping algorithms still need improvements.
DOI 原文 · arXiv · PDF（开放获取） · DBLP
@inproceedings{Fan00HWL21,
title = {A Differential Testing Approach for Evaluating Abstract Syntax Tree Mapping Algorithms},
author = {Yuanrui Fan and Xin Xia and David Lo and Ahmed E. Hassan and Yuan Wang and Shanping Li},
booktitle = {ICSE},
year = {2021},
doi = {10.1109/icse43902.2021.00108}
}