Track papers across labs, topics, and trends.
Search papers, labs, and topics across Lattice.
This paper introduces a new structural merge tool that evaluates merge results based on syntactic criteria, specifically requiring that the output is both parsable and universal. Through extensive testing on 43,774 file merge scenarios from 76 open-source Java projects, the authors found that existing tools, including the Git companion merge tool, produced incorrect results, while their tool reported none. The findings highlight the necessity for rigorous correctness criteria in merge tools, paving the way for more reliable software development practices.
Existing merge tools are prone to errors, but a new structural merge tool achieves perfect accuracy in handling complex merge scenarios.
Three-way merge tools play crucial roles in modern software development, where a developer forks a branch to make local modifications and requests it to be merged into the main branch via a "pull request." Despite its importance, the task has traditionally been defined in an intuitive manner, and the results of merge tools are often accepted without scrutiny. In this paper, we present a new structural merge tool in comparison with existing tools based on the syntactic criteria we propose for evaluating the merge results. We require the merge result to be both parsable and universal. Being parsable means that the result is syntactically valid according to the grammar of the programming language. Being universal means that the result incorporates all and only the edit operations occurring in each branch while ensuring that edits common to both branches are applied only once. This requirement can be precisely defined using the notion of pushouts in category theory. In a large-scale experiment involving 43,774 file merge scenarios from 76 open-source Java projects, we found a number of incorrect results reported by existing tools such as the Git companion merge tool, whereas our tool reports none. We further compared d3j’s results with 2,582 developer-resolved merges and with 2,459 merge scenarios involving 21 refactoring types. These experiments revealed both the strengths and current limitations of structural merge, and underscore the importance of clear correctness criteria. We expect that the proposed criterion will provide a foundation for developing more reliable and principled merge tools.