MergeResolver

Automatic Merge Conflict Resolution from GrammaTech
MergeResolver is not currently available for public use.

What is MergeResolver?

MergeResolver is a new GitHub app that automates resolving merge conflicts — but leaves developers in control.

Currently MergeResolver only supports JavaScript projects.

How MergeResolver Works

When you install MergeResolver on a repository, it waits for a conflict to happen. Conflicts can happen with new pull requests, or when a new commit to master conflicts with one or more open pull requests.

Step 1: AST merging

If a conflict happens, MergeResolver clones your repository and gets to work. First, it tries to avoid the conflict by retrying the merge, but on the Abstract Syntax Tree (AST) level.

Screenshot of an AST merge

By treating code as ASTs rather than simply a string of characters, MergeResolver recognizes code's structure and semantics. This ensures all potential conflict resolutions will parse as valid code, and in some cases cleanly reconciles changes that would conflict under Git's built-in, line-oriented merge algorithms (as in the above example).

Screenshot of a MergeResolver check in progress.

Step 2: Auto-merging

If AST merging fails, things get more interesting. MergeResolver understands different strategies for reconciling merge conflicts – strategies mined from large datasets of real-world merge conflict resolutions (see On the nature of merge conflicts). With this knowledge it can generate possible conflict resolutions.

But how does it know which generated conflict resolutions are viable? MergeResolver relies on the only source of truth about a program's requirements: its test suite. MergeResolver finds a viable resolution by looking for a resolution that passes your program's test suite.

Step 3: Presenting the results

Once MergeResolver finds a resolution that passes your test suite, it uses GitHub's Checks API to provide a button (under the Checks tab on the pull request) that can be used to accept the resolution.

Screenshot of a successful merge with a prompt to accept it.

If you want to inspect the conflict resolution before accepting it, a link is provided to a diff of the merge resolution commit.

FAQ

Isn't it dangerous to let a robot commit code?

MergeResolver just suggests a change. You have the opportunity to review it before accepting, and it's up to you to choose whether or not to apply it. Think of it as a fast junior engineer whose work needs to be double checked.

Are changes like semicolons or whitespace diffed with the AST?

Yes. For example, diffing

var x = 1; var y = 2

vs.

var x = 1
var y = 2

results in an AST diff:

var x = 1[-;-]{+
+}[- -]var y = 2

How did you test this? How do you know it works?

We cloned a large number of the top JavaScript repositories from GitHub, programmatically identified every merge commit, selected those that conflicted when reproduced, and then applied our tool to those.

Who is behind this?

MergeResolver is a product of GrammaTech's Research Division, funded largely by DARPA.

Installing MergeResolver

MergeResolver is currently available for direct installation. It is free for open-source projects to try. You can add MergeResolver to your Node-based JavaScript repository here.

Note that MergeResolver currently targets JavaScript, which means that your repository needs to have a package.json file. This is necessary so MergeResolver can run your test suite.

Support

Support is available through a dedicated support repository. If you have a problem with MergeResolver, or an idea for improvement, please open an issue there.

Let us know what works well or not for you, and we'll strive to make MergeResolver useful enough that it becomes a staple of your team's development workflow.


This material is based upon work supported by the Defense Advanced Research Projects Agency (DARPA) under Contract No. D17PC00096. Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the Defense Advanced Research Projects Agency (DARPA); or its Contracting Agent, the U.S. Department of the Interior, Interior Business Center, Acquisition Services Directorate, Division III.