AutoMerge
Resolve merge conflicts that cannot be handled by existing structured merge approaches, in an automated way.
What is AutoMerge?
AutoMerge aims to resolve merge conflicts that cannot be resolved by existing structured merge approaches. It is built on the top of JDime, a state-of-the-art structured merger. It employs the power of version space algebra and the basic rules of three-way merge.
Conflicts, Again
Unstructured merge is applicable to a wide range of real-world software projects, while being language-independent and efficient. In unstructured merge, source code is regarded as a sequence of plain text. Apparently, it has low precision. Later, structural information such as the context-free and context-sensitive syntax are employed during the merge process. In structured merge, programs are treated as abstract syntax trees. Experiments show that structured merge is more precise than unstructured merge.
In a typical three-way merge scenario, there are basic rules that the merge algorithm shall follow. When concurrent changes contradict each other, both structured merge and unstructured merge cannot solve the conflict.
Resolve Conflicts, Automatically
When a developer is reported of a conflict, in order to resolve it, it is usually unnecessary to compare the whole program. Instead, one usually compares the conflicting sections merely, and form a resolution by "combining" them in a rearranged way. These combinations form a program space and each of them stands for a resolution candidate.
Since the program space is possibly very large, to be practical, we need a compact and efficient representation for the entire program space. Version space algebra (VSA) is a data structure to represent it succinctly. We then rely on user interaction for identifying a suitable resolution from the program space. For fast convergence, we also need a ranking mechanism for "sorting" the candidate resolutions and top ones should be very likely to meet the developer's expectation.
Take a Closer Look!
OOPSLA'18 Paper: Conflict Resolution for Structured Merge via Version Space Algebra
Video talk with slides