BDiff: Block-aware and Accurate Text-based Code Differencing
Preprint
Abstract
Code differencing is a fundamental technique in software engineering practice and research. While researchers have proposed text-based differencing techniques capable of identifying line changes over the past decade, existing methods exhibit a notable limitation in identifying edit actions (EAs) that operate on text blocks spanning multiple lines. Such EAs are common in developers' practice, such as moving a code block for conditional branching or duplicating a method definition block for overloading. Existing tools represent such block-level operations as discrete sequences of line-level EAs, compelling developers to manually correlate them and thereby substantially impeding the efficiency of change comprehension. To address this issue, we propose BDiff, a text-based differencing algorithm capable of identifying two types of block-level EAs and five types of line-level EAs. Building on traditional differencing algorithms, we first construct a candidate set containing all possible line mappings and block mappings. Leveraging the Kuhn-Munkres algorithm, we then compute the optimal mapping set that can minimize the size of the edit script (ES) while closely aligning with the original developer's intent. To validate the effectiveness of BDiff, we selected five state-of-the-art tools, including large language models (LLMs), as baselines and adopted a combined qualitative and quantitative approach to evaluate their performance in terms of ES size, result quality, and running time. Experimental results show that BDiff produces higher-quality differencing results than baseline tools while maintaining competitive runtime performance. Our experiments also show the unreliability of LLMs in code differencing tasks regarding result quality and their infeasibility in terms of runtime efficiency. We have implemented a web-based visual differencing tool.Keywords
All Related Versions
This publication has 24 references indexed in Scilit:
- An empirical study on the use of SZZ for identifying inducing changes of non-functional bugsEmpirical Software Engineering, 2021
- A Differential Testing Approach for Evaluating Abstract Syntax Tree Mapping Algorithms2021
- How different are different diff algorithms in Git?Empirical Software Engineering, 2019
- cregit: Token-level blame information in git version control repositoriesEmpirical Software Engineering, 2019
- Internal quality assurance for external contributions in GitHub: An empirical investigationJournal of Software: Evolution and Process, 2017
- LHDiff: A Language-Independent Hybrid Approach for Tracking Source Code Lines2013
- Detection and analysis of near-miss software clones2009
- Discovering and representing systematic code changes2009
- Tracking Your Changes: A Language-Independent ApproachIEEE Software, 2009
- AnO(ND) difference algorithm and its variationsAlgorithmica, 1986