Move-optimized source code tree differencing
Open Access
- 25 August 2016
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 660-671
Abstract
When it is necessary to express changes between two source code files as a list of edit actions (an edit script), modern tree differencing algorithms are superior to most text-based approaches because they take code movements into account and express source code changes more accurately. We present 5 general optimizations that can be added to state-of-the-art tree differencing algorithms to shorten the resulting edit scripts. Applied to Gumtree, RTED, JSync, and ChangeDistiller, they lead to shorter scripts for 18-98% of the changes in the histories of 9 open-source software repositories. These optimizations also are parts of our novel Move-optimized Tree DIFFerencing algorithm (MTDIFF) that has a higher accuracy in detecting moved code parts. MTDIFF (which is based on the ideas of ChangeDistiller) further shortens the edit script for another 20% of the changes in the repositories. MTDIFF and all the benchmarks are available under an open-source license.Keywords
This publication has 35 references indexed in Scilit:
- Tree Edit Distance Problems: Algorithms and Applications to BioinformaticsIEICE Transactions on Information and Systems, 2010
- An optimal decomposition algorithm for tree edit distanceACM Transactions on Algorithms, 2009
- A survey on tree edit distance and related problemsTheoretical Computer Science, 2005
- Computing similarity between RNA structuresTheoretical Computer Science, 2002
- Change detection in hierarchically structured informationACM SIGMOD Record, 1996
- AnO(ND) difference algorithm and its variationsAlgorithmica, 1986
- A file comparison programSoftware: Practice and Experience, 1985
- The Tree-to-Tree Correction ProblemJournal of the ACM, 1979
- The Hungarian method for the assignment problemNaval Research Logistics Quarterly, 1955
- X. On the criterion that a given system of deviations from the probable in the case of a correlated system of variables is such that it can be reasonably supposed to have arisen from random samplingJournal of Computers in Education, 1900