A Differential Testing Approach for Evaluating Abstract Syntax Tree Mapping Algorithms
Authors:
- 1 May 2021
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- No. 15581225,p. 1174-1185
Abstract
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.Keywords
All Related Versions
Funding Information
- Research and Development
This publication has 28 references indexed in Scilit:
- VuRLE: Automatic Vulnerability Detection and Repair by Learning from Examples2017
- Discovering bug patterns in JavaScript2016
- API code recommendation using statistical learning from fine-grained changes2016
- Move-optimized source code tree differencing2016
- Fine-grained and accurate source code differencing2014
- Lase: Locating and applying systematic edits by learning from examples2013
- Program element matching for multi-version program analyses2006
- Change detection in hierarchically structured informationACM SIGMOD Record, 1996
- Algorithms for the Longest Common Subsequence ProblemJournal of the ACM, 1977
- Measuring nominal scale agreement among many raters.Psychological Bulletin, 1971