Spork : Move-enabled structured merge for Java with GumTree and 3DM

Abstract: With software development becoming an increasingly parallel process in which branching lines of development is common, the shortcomings of unstructured merge techniques are becoming more tangible. In particular, merge conflicts occur frequently and often unnecessarily. Structured merge techniques typically operate on abstract syntax trees instead of raw text, and present major improvements over unstructured merge in terms of avoiding unnecessary conflicts. Structured merge can however be prone to slow execution, has problems dealing with refactorings such as renamings and moves of code blocks, and is often poor at preserving source code formatting. In this thesis, we implement and evaluate spork, a structured merge tool for the java programming language. spork is built using move-enabled diff and merge algorithms that can resolve refactoring-related conflicts automatically. The algorithms used are highly efficient, making spork scale well with larger merges. spork also has features for reusing the original source code of the input files in a merge, leading to improved preservation of source code formatting. We compare spork to the state of the art structured merge tool jdime in an empirical evaluation on 890 merge scenarios from 119 different open source java projects, comprising a total of 1740 file merges. spork and jdime tend to be equally fast in the median case, with median running times of 1.45 and 1.48 seconds per file merge, respectively. jdime is the faster tool below the median running time, but spork is faster above the median, indicating that spork scales better with larger merges. Additionally, spork produces fewer but slightly larger conflicts, mostly due to known issues. We also find no statistically significant difference between spork’s and jdime’s abilities to produce correct merges. In some cases, spork’s move-enabled algorithms allows it to automatically resolve merges with renamings that cause conflicts for jdime. In conjunction, these results constitute strong evidence that move-enabled merge is feasible for use in a structured merge tool for the java programming language. spork is also more than 4 times better than jdime at preserving formatting in the median case. Although the results are promising, there are unresolved issues with conflicts related to moves and deletes that reduce spork’s performance and reliability, necessitating further work.