DiffFix: Incrementally Fixing AST Diffs via Context and Type Information

The abstract syntax tree differencing (ASTDiff) technique aims to capture syntactic code changes through comparing the differences between a pair of ASTs of a program, which has been widely used in various program analysis or testing tasks, such as code review, clone detection, and regression testing. A key issue for ASTDiff lies in the accurate mappings between nodes of two ASTs. However, most existing approaches often fail to generate such perfect diffs due to the gap between diverse code changes and unsound node matching heuristics. Our in-depth investigation reveals that most inaccurate mappings are caused by the ignorance of context- and/or type-specific constraints. Accordingly, we propose an AST diff fixing approach DiffFix that leverages both the node’s context and type constraints to iteratively and incrementally fix imperfect diffs. Comprehensive experiments have been conducted to evaluate the effectiveness of DiffFix through its application to fix diffs generated by five state-of-the-art ASTDiff techniques. The experimental results demonstrate that DiffFix can improve the perfect diff rate of these baseline techniques by 5.25% to 51.12% with negligible time overhead.