Enhancing Precision of Structured Merge by Proper Tree Matching

Abstract

Recently, structured merge has shown its advantage in improving the merge precision over conventional line-based, unstructured merge. A typical structured merge algorithm consists of matching and amalgamation on abstract syntax trees. Existing tree matching techniques aim to figure out optimal matches by maximizing the number of matched nodes. From real-world codebases, however, we find that many of the reported conflicts are unnecessary. We propose a new objective function for defining a proper tree matching, with which the overall conflicting rate can be greatly reduced. We conducted experiments on 3,687 merge scenarios extracted from 18 open-source projects. Results show significant merge precision enhancement of our approach.