Are you held back by conflicts? Then meet

Mergiraf

Mergiraf can solve a wide range of Git merge conflicts. That's because it's aware of the trees in your files! Thanks to its understanding of your language, it can often reconcile the needs of both sides.

You can teach Mergiraf a new language in a completely declarative way. It's a nonviolent animal, so it prefers that over imperatives.

Demo

Configure Git to use Mergiraf instead of its default merge heuristics. This will enhance git merge, revert, rebase, cherry-pick and more.

You can also keep Git's original behaviour and manually invoke Mergiraf after encountering conflicts.

Figure 1: Two git users making inadequate use of blame, push and pull to resolve a conflict

Ready to give it a try?

Head to the installation page and start merging nonviolently today!

Aspirations

Mergiraf is designed with your needs in mind. Its goals are:

Don't sweep conflicts under the rug

Syntax-aware merging heuristics can sometimes be a bit too optimistic in considering a conflict resolved. Mergiraf does its best to err on the side of caution and retain conflict markers in the file when encountering suspicious cases.

If it manages to resolve all conflicts on its own, it encourages you to review its mediation work via the mergiraf review command. If a merge looks faulty, you can report it easily.

Be fast enough for interactive use

Figure 2: Mergiraf offers to mediate

Did you know that giraffes can run as fast as 60 kilometers per hour? Anyways. The operation of merging diverging versions of files happens routinely when working on a code base, often without you noticing as long as there aren't any conflicts. So Mergiraf tries to be quick so as not to interrupt you in your tasks.

Be open to other methods

In many cases, line-based merging works just great and there is no need for tree-munging business. If a line-based merge is conflict-free, then Mergiraf just returns that merge (which is very quick). One exception to this rule is when line-based merging creates duplicate keys. In such a case, Mergiraf does a bit more work to resolve the issue or highlight it to you with conflict markers.

Figure 3: Harmony and peace reign on Earth

Illustrations by Freya F-T, CC-BY 4.0.

Installation

You can download Mergiraf from Codeberg. Choose the archive that matches your device's architecture and place the extracted binary in your PATH.

If you have Rust installed, you can also install Mergiraf from source by cloning its repository and running cargo install --path . in it. Or download and build Mergiraf on crates.io with Cargo by running: cargo install --locked mergiraf.

Once Mergiraf is installed, you can then configure Git to use Mergiraf.

Pssst! Why don't you install Difftastic too?

Difftastic is a fantastic structural diff tool which works great in combination with Mergiraf.

Usage

There are two ways to use Mergiraf.

1. You can register it as a merge driver in Git so that Mergiraf is directly used during the merge process.
2. Or you can invoke it after a merge conflict, for it to attempt to solve the conflict.

The first way is recommended as it avoids interrupting your workflow with spurious conflicts. The second way can be useful for more occasional uses or when changes to Git's configuration are not possible.

Registration as a Git merge driver

Registering Mergiraf in Git will enable you to benefit from its conflict solving when merging and various other operations, such as rebasing, cherry-picking or even reverting. For best results, use Git v2.44.0 or newer.

First, add the following section in your ~/.gitconfig file:

[merge "mergiraf"]
    name = mergiraf
    driver = mergiraf merge --git %O %A %B -s %S -x %X -y %Y -p %P

# if you haven't got a global gitattributes file yet
[core]
	attributesfile = ~/.gitattributes

Or run:

$ git config --global merge.mergiraf.name mergiraf
$ git config --global merge.mergiraf.driver 'mergiraf merge --git %O %A %B -s %S -x %X -y %Y -p %P'
$ git config --global core.attributesfile ~/.gitattributes

Then, you also need to specify for which sorts of files this merge driver should be used. Add the following lines to your global ~/.gitattributes file:

*.java merge=mergiraf
*.rs merge=mergiraf
*.go merge=mergiraf
*.js merge=mergiraf
*.jsx merge=mergiraf
*.json merge=mergiraf
*.yml merge=mergiraf
*.yaml merge=mergiraf
*.html merge=mergiraf
*.htm merge=mergiraf
*.xhtml merge=mergiraf
*.xml merge=mergiraf
*.c merge=mergiraf
*.cc merge=mergiraf
*.h merge=mergiraf
*.cpp merge=mergiraf
*.hpp merge=mergiraf
*.cs merge=mergiraf
*.dart merge=mergiraf

Or run:

$ mergiraf languages --gitattributes >> ~/.gitattributes

This is the complete list of all supported formats - you can of course keep only the ones you need. If you want to enable Mergiraf only in a certain repository, add the lines above in the .gitattributes file at the root of that repository instead, or in .git/info/attributes if you don't want it to be tracked in the repository.

Trying it out

An example repository is available for you to try out Mergiraf on simple examples:

$ git clone https://codeberg.org/mergiraf/example-repo
$ cd example-repo
$ git merge other-branch

Reviewing Mergiraf's work

When Git invokes Mergiraf to merge a file, it can either:

• successfully merge the file as a line-based merge, just like normal Git would do,
• encounter conflicts in the line-based merge, which it completely solves via its syntax-aware heuristics. In this case it invites you to review its work via the mergiraf review command,
• encounter conflicts it cannot solve. In this case, it lets you merge the file manually by leaving conflict markers behind.

If it turns out that Mergiraf's output is unsatisfactory and you would rather use the built-in merge algorithms, abort the operation (such as with git merge --abort) and start again with Mergiraf disabled.

Temporarily disabling Mergiraf

You can disable Mergiraf by defining the MERGIRAF_DISABLE environment variable:

$ MERGIRAF_DISABLE=1 git rebase origin/master

This will fall back on Git's regular merge heuristics, without requiring changes to your configuration.

Reporting a bad merge

If the output of a merge looks odd, you are encouraged to report it as a bug. The mergiraf report command generates an archive containing all necessary information to reproduce the faulty merge.

If the merge did not produce any conflicts, use the merge id (identical to what mergiraf review accepts) in Git's output:

$ git rebase origin/master
INFO Mergiraf: Solved 2 conflicts. Review with: mergiraf review geolocation.cpp_o0i2JL8B
Successfully rebased and updated refs/heads/my_branch.
$ mergiraf review geolocation.cpp_o0i2JL8B
$ mergiraf report geolocation.cpp_xyuSMcme
Bug report archive created:

mergiraf_report_6weNKAXO.zip

Please submit it to https://codeberg.org/mergiraf/mergiraf/issues if you are happy with its contents being published,
or reach out privately to a contributor if not.
Thank you for helping Mergiraf improve!

If the merge to report has conflicts, use the path to the file instead:

$ mergiraf report src/lib/geolocation.cpp

Compact conflict presentation

By default, Mergiraf aligns the conflicts it outputs to line boundaries to ease their resolution in existing merge tools:

<<<<<<< HEAD
<div class="vocab-panel" id="main-panel">
||||||| 15b798c
<div class="vocab-panel">
=======
<div class="vocab-panel" id="root-panel">
>>>>>>> origin/main

Because merging is done on syntax trees, it is often able to highlight narrower conflicts. The option --compact (or -c) of the mergiraf merge command enables a more compact presentation of conflicts which highlights mismatching parts only:

<div class="vocab-panel" id=
<<<<<<< HEAD
"main-panel"
||||||| 15b798c
=======
"root-panel"
>>>>>>> origin/main
>

The main downside of this mode is that reformatting is often required after resolving conflicts.

Interactive use after encountering a merge conflict

Say you have encountered a conflict during merge:

$ git merge origin/main
Auto-merging config.yml
CONFLICT (content): Merge conflict in config.yml
Automatic merge failed; fix conflicts and then commit the result.
$ cat config.yml
<<<<<<< HEAD
restaurant:
  tasks:
    plates: 1
    bowls: 2
||||||| 15b798c
tasks:
  plates: 1
  bowls: 2
=======
tasks:
  plates: 1
  bowls: 4
>>>>>>> origin/main

You can then run Mergiraf to attempt to solve the conflicts automatically:

$ mergiraf solve config.yml
Solved 1 conflict(s)

You can then inspect the result again:

restaurant:
  tasks:
    plates: 1
    bowls: 4

You can then mark the conflict as solved with git add and continue merging with git merge --continue.

Conflicts solved

This page gives an overview of the sorts of conflicts that Mergiraf is able to handle and which ones are left for the user to solve.

Changes to independent syntax elements

Consider the following situation:

void notify_attendees(long status_code);

void notify_attendees(int status_code);

int notify_attendees(int status_code);

The left side changes the type of the argument of this C function while the right side changes its return type. Both changes can be done independently, so this is resolved to:

int notify_attendees(long status_code);

Neighbouring insertions and deletions of elements whose order does not matter

Another example:

class Bird {
    String species;
    int weight;
}

class Bird {
    String species;
}

class Bird {
    String species;
    double wingspan;
}

The left and right sides add different attributes to the same Java class. The order of declaration of those attributes does not matter, so the conflict can be resolved to:

class Bird {
    String species;
    int weight;
    double wingspan;
}

In contrast to this, conflicting additions of instructions in a block, or conflicting additions of arguments to a function declaration are not automatically resolved as above, given that the order in which they are inserted matters.

while (true) {
    mowTheLawn();
    rechargeBatteries();
}

while (true) {
    mowTheLawn();
}

while (true) {
    mowTheLawn();
    returnToHomeBase();
}

In this example, human intervention is needed to decide in which order the rechargeBatteries() and returnToHomeBase() statements should be inserted, so a conflict is created.

This type of conflict resolution is enabled for a set of syntactic contexts (called "commutative parents") configured on a per-language basis. To enable the resolution above, we mark field_declaration_list nodes in Java to be commutative parents. Similarly, the order of attributes in an HTML tag is irrelevant, so given the following revisions

<input type="text" autocomplete="off" />

<input type="text" />

<input type="text" value="hello" />

Mergiraf will output the following, since self_closing_tag is marked as a commutative parent in HTML:

<input type="text" autocomplete="off" value="hello" />

Conflicting formatting and content changes

When one side reformats the file and the other makes changes to its contents, Mergiraf attempts to retain both the new formatting and the new contents.

In the following example, the left side reformats a function declaration and the right side changes the type of one of its arguments.

fn plan_route(
    start: &Location,
    end: &Location,
    settings: &RouteSettings,
) -> Route {
    todo!();
}

fn plan_route(start: &Location, end: &Location, settings: &RouteSettings) -> Route {
    todo!();
}

fn plan_route(start: &Location, end: &Location, settings: Option<&RouteSettings>) -> Route {
    todo!();
}

In this case, Mergiraf produces the following merge:

fn plan_route(
    start: &Location,
    end: &Location,
    settings: Option<&RouteSettings>,
) -> Route {
    todo!();
}

Moving edited elements

Mergiraf can detect that a particular section of source code has been moved in one revision and has been modified by the other revision. In this case, the changes on the latter branch are replayed at the new location. Consider this example:

impl Lawnmower {
    fn find_home_station(&self) -> Option<&Station> {
        self.neighbouring_stations()
            .iter()
            .find(|station| self.is_suitable_home(station))
    }

    fn is_suitable_home(&self, station: &Station) -> bool {
        station.id == self.home_station_id
            && !station.occupied
            && station.color == StationColor::Red
    }
}

impl Lawnmower {
    fn find_home_station(&self) -> Option<&Station> {
        self.neighbouring_stations().iter().find(|station| {
            station.id == "home"
                && !station.occupied
                && station.color == StationColor::Red
        })
    }
}

impl Lawnmower {
    fn find_home_station(&self) -> Option<&Station> {
        self.neighbouring_stations().iter().find(|station| {
            station.id == "home"
                && !station.occupied
                && station.color == StationColor::Blue
        })
    }
}

The left revision extracts the boolean condition out of the closure to turn it into a method, making some changes to it in the same go. The right revision makes some other changes to the boolean expression (turning Red into Blue). In such a case, Mergiraf is able to replay the changes of the right branch onto the new location of the boolean expression in the left branch, which gives the following result:

impl Lawnmower {
    fn find_home_station(&self) -> Option<&Station> {
        self.neighbouring_stations()
            .iter()
            .find(|station| self.is_suitable_home(station))
    }

    fn is_suitable_home(&self, station: &Station) -> bool {
        station.id == self.home_station_id
            && !station.occupied
            && station.color == StationColor::Blue
    }
}

Line-based merges

In addition to the above, if the files merge cleanly using Git's usual line-based merging algorithm, so will they with Mergiraf. There is however one notable exception. Consider the following situation:

{
    "new_letter": "left value",
    "alpha": "α",
    "beta": "β",
    "gamma": "γ",
    "delta": "δ"
}

{
    "alpha": "α",
    "beta": "β",
    "gamma": "γ",
    "delta": "δ"
}

{
    "alpha": "α",
    "beta": "β",
    "gamma": "γ",
    "delta": "δ",
    "new_letter": "right value",
}

Git's line-based merging algorithm happily merges those revisions into:

{
    "new_letter": "left value",
    "alpha": "α",
    "beta": "β",
    "gamma": "γ",
    "delta": "δ",
    "new_letter": "right value"
}

This is a problem, as the "new_letter" key appears twice. In such a situation, Mergiraf outputs a conflict:

{
<<<<<<< Left
    "new_letter": "left value",
||||||| Base
=======
    "new_letter": "right value",
>>>>>>> Right
    "alpha": "α",
    "beta": "β",
    "gamma": "γ",
    "delta": "δ"
}

This works by defining so-called "signatures" for certain children of commutative parents. A signature defines how to build a key for a syntactic element, child of a commutative parent. Such keys should be unique among all children of a given commutative parent. Beyond this example in JSON, this mechanism is used to ensure the uniqueness of import statements, method signatures, struct fields and many other syntactic constructs in various languages. For more details about how they are defined, see the tutorial to teach Mergiraf a new language.

And what about human conflicts?

Have you ever heard of nonviolent communication, also known as giraffe language? It's an interesting framework, suggesting which communication patterns to use or avoid when tensions arise. Check it out!

Supported languages

Mergiraf currently supports the following programming languages:

• Java (*.java)
• Rust (*.rs)
• Go (*.go)
• Javascript (*.js, *.jsx)
• C/C++ (*.c, *.h, *.cc, *.cpp, *.hpp)
• C# (*.cs)
• Dart (*.dart)

and the following declarative file formats:

• JSON (*.json)
• HTML (*.html, *.htm)
• XML (*.xml, *.xhtml)
• YAML (*.yml, *.yaml)

This list can also be obtained with the mergiraf languages command.

Is your favorite language missing? Check out the tutorial to add support for a new language!

Adding a language

In this tutorial, we will go through all the steps required to add support for a new language in Mergiraf, with C# as an example. As a prerequisite, we assume that you have cloned Mergiraf's git repository and have installed Rust.

Get a parser

The first step is to find a tree-sitter parser for this language. The corresponding Rust crate needs to be added to Mergiraf's Cargo.toml file:

[dependencies]
tree-sitter-csharp = "0.21.3"

The version of the parser must be selected so that it is compatible with the version of tree-sitter that Mergiraf currently uses.

Create a language profile

Then, go to src/supported_langs.rs and add a profile for the language. You can start with a minimal one, such as:

LangProfile {
    name: "C#", // only used for logging purposes so far
    extensions: vec![".cs"], // all file extensions for this language
    language: tree_sitter_c_sharp::LANGUAGE.into(), // the tree-sitter parser
    // optional settings, explained below
    atomic_nodes: vec![],
    commutative_parents: vec![],
    signatures: vec![],
},

You can compile your new version of Mergiraf with:

$ cargo build

You'll find the binary in ./target/debug/mergiraf, which supports your language.

That's all you need to get basic support for this language in Mergiraf. It already enables syntax-aware merging which should already give better results than line-based merging.

Add commutative parents

You can improve conflict resolution for this language by defining "commutative parents". A node in a syntax tree is a commutative parent when the order of its children is unimportant. This knowledge allows Mergiraf to automatically solve most conflicts involving insertion or deletion of children of such a parent.

Identifying which node types should commutative is easier with some familiarity with the semantics of the language, but there are usual suspects you can consider:

• import statements (such as import in Java or Go, use in Rust…)
• field or method declarations in classes (as in most object-oriented programming languages)
• declarations of sum-types (such as union in C or functional programming languages)
• dictionary or set objects (such as JSON objects, struct instantiations in C/C++…)
• declarative annotations of various sorts (such as annotation parameters in Java, trait bounds in Rust, tag attributes in XML / HTML…)

For instance, C# has import statements called using declarations and some IDEs seem to allow sorting them alphabetically. This is a good sign that their order is semantically irrelevant, as in many languages, so let's declare that.

First, write a small sample file which contains the syntactic elements you are interested in, such as:

using System;
using System.Collections.Generic;
using System.IO;

namespace HelloWorld {

    public class SomeName {

    }
}

You can inspect how this file is parsed with, either with the Syntax Tree Playground if the language is supported there, or directly via Mergiraf:

$ cargo run --bin mgf_dev parse test_file.cs

which gives:

└compilation_unit
  ├using_directive
  │ ├using
  │ ├identifier System
  │ └;
  ├using_directive
  │ ├using
  │ ├qualified_name
  │ │ ├qualifier: qualified_name
  │ │ │ ├qualifier: identifier System
  │ │ │ ├.
  │ │ │ └name: identifier Collections
  │ │ ├.
  │ │ └name: identifier Generic
  │ └;
  ├using_directive
  │ ├using
  │ ├qualified_name
  │ │ ├qualifier: identifier System
  │ │ ├.
  │ │ └name: identifier IO
  │ └;
  └namespace_declaration
    ├namespace
    ├name: identifier HelloWorld
    └body: declaration_list
      ├{
      ├class_declaration
      │ ├modifier
      │ │ └public
      │ ├class
      │ ├name: identifier SomeName
      │ └body: declaration_list
      │   ├{
      │   └}
      └}

This shows us how our source code is parsed into a tree. We see that the using statements are parsed as using_directive nodes in the tree.

To let Mergiraf reorder using statements to fix conflicts, we actually need to specify that they can be reordered with any of their siblings (any other child of their parent in the syntax tree). In this example, their parent is the root of the tree (with type compilation_unit), which means that we'll allow reordering using statements with other top-level elements, such as the namespace declaration.

This might feel a little odd, given that using statements will almost invariably appear at the top of the file, and we definitely don't want to have Mergiraf move them to the end of the file when merging for instance. However, Mergiraf only relies on commutative parents to solve conflicts, such as inserting two elements at the same place. It keeps the order of other existing elements. C# being an object-oriented language, it does not allow for top-level instructions (everything happens inside classes, whose declaration order does not matter either), so in this case it is appropriate to declare compilation_unit as a commutative parent.

We can do so in the language profile:

LangProfile {
    commutative_parents: vec![
        CommutativeParent::without_delimiters("compilation_unit", "\n"),
    ],
    ..
},

A commutative parent is not only defined by a type of node, but also:

• the expected separator between its children (here, a newline: "\n")
• any delimiters at the beginning and end of the list of children. Here, there are none, but in many cases, such lists start and end with characters such as ( and ) or { and }.

For instance, to declare that a JSON object is a commutative parent, we do so with

CommutativeRoot::new("object", "{", ", ", "}")

Note how we use the separator is ", " and not simply ",". The separators and delimiters should come with sensible default whitespace around them. This whitespace is used as last resort, as Mergiraf attempts to imitate the surrounding style by reusing similar whitespace and indentation settings as existing delimiters and separators.

After having added our commutative parent definition, we can compile it again with cargo build. The resulting binary in target/debug/mergiraf will now accept to resolve conflicts like the following one:

using System;
using System.Collections.Generic;

using System;

using System;
using System.IO;

This will be merged to include all three using statements. When inspecting how a file is parsed with cargo run --bin mgf_dev parse test_file.cs, commutative parents are highlighted in the tree, which also helps validate our definitions.

We can add other commutative parent definitions in the language profile. For instance, the declarations in the body of a class (such as field_declaration or method_declaration) can be freely reordered. This can be modeled by marking declaration_list nodes as being commutative parents:

CommutativeRoot::new("declaration_list", "{", "\n\n", "}")

and so on. While it is useful to identify as many commutative parent types as possible, not being exhaustive is not a problem as it will only prevent the automated resolution of certain conflicts, but should not otherwise degrade the quality of merges.

Add signatures

One piece of knowledge we have not encoded yet is the fact that using statements should be unique: there is no point in importing the same thing twice. This is specified using so-called signatures, which associate keys to the children of commutative parents. Those keys are then required to be unique among the children of a particular commutative parent. This mechanism can be used to define such keys for a lot of other elements. For instance, class fields are keyed by their name only, given that field names should be unique in a given class, regardless of their type. Keys can also be generated for methods, which not only includes their name but also the types of the arguments the function takes, as C# supports method overloading.

To define a signature, we need to provide two pieces of information:

• the type of node we want to generate a key for, such as field_declaration
• a list of paths from the element being keyed to the descendant(s) making up its key. A path is itself a list of steps leading from the element to the descendant.

For instance:

signature("using_directive", vec![vec![]]),
signature("field_declaration", vec![vec![Field("name")]]),
signature("method_declaration", vec![
    vec![Field("name")],
    vec![Field("parameters"), ChildType("parameter"), Field("type")]
]),

Let's unpack what this all means.

• for using_directive, we supply a list containing a single path: the empty one. The empty path goes from the element being keyed to itself.
• for field_declaration, we supply again a list containing a single path, which has one step. This step fetches the name field of the element being keyed.
• for method_declaration, we have this time a list of two paths. The first one fetches the name, the second selects the types of the parameters in three steps.

This gives rise to the following signatures:

Again, this can be checked with cargo run --bin mgf_dev parse test_file.cs, which shows the computed signatures in the tree.

To understand the difference between Field and ChildType in the signature definition for method_declaration, consider the structure of a method declaration as parsed by tree-sitter:

 └method_declaration
  ├type: predefined_type void
  ├name: identifier Run
  ├parameters: parameter_list
  │ ├(
  │ ├parameter
  │ │ ├type: predefined_type int
  │ │ └name: identifier times
  │ ├,
  │ ├parameter
  │ │ ├type: predefined_type bool
  │ │ └name: identifier fast
  │ └)
  └body: block
    ├{
    └}

Notice that some nodes have two labels attached to them:

• the field name, such as name, indicating which field of its parent node it belongs to. It is optional: some nodes like parameter ones are not associated to any field.
• the grammar name, such as identifier, which is the type of AST node. Every node has one (for separators or keywords, the source text is the grammar name)

In general, when descending into a single predetermined child of a given node, one should use a Field. If the number of children is variable then we expect to select them by grammar name using ChildType.

The grammar of a tree-sitter parser is defined in a grammar.js file and reading it directly can be useful, for instance to understand what are the possible children or parent of a given type of node. Note that node types starting with _ are private, meaning that they are not exposed to Mergiraf. In case of doubt, just parse some small example to check.

Atomic nodes

Sometimes, the parser analyzes certain constructs with a granularity that is finer than what we need for structured merging. To treat a particular type of node as atomic and ignore any further structure in it, one can add its type to the atomic_nodes field.

This is also useful to work around certain issues with parsers which don't expose the contents of certain string literals in the syntax trees.

Add tests

We didn't write any code, just declarative things, but it's still worth checking that the merging that they enable works as expected, and that it keeps doing so in the future.

You can add test cases to the end-to-end suite by following the directory structure of other such test cases. Create a directory of the form:

examples/csharp/working/add_imports

The naming of the csharp directory does not matter, nor does add_imports which describes the test case we are about to write. In this directory go the following files:

Base.cs
Left.cs
Right.cs
Expected.cs

All files should have an extension which matches what you defined in the language profile, for them to be parsed correctly. The Base, Left and Right files contain the contents of a sample file at all three revisions, and Expected contains the expected merge output of the tool (including any conflict markers).

To run an individual test, you can use a helper:

$ helpers/inspect.sh examples/csharp/working/add_imports

This will show any differences between the expected output of the merge and the actual one. It also saves the result of some intermediate stages of the merging process in the debug directory, such as the matchings between the three trees as Dotty graphs. Those can be viewed as SVG files by running helpers/generate_svg.sh.

To run a test with a debugger, you can use the test defined in tests/integration_tests.rs:

// use this test to debug a specific test case by changing the path in it.
#[rstest]
fn debug_test() {
    run_test_from_dir(&PathBuf::from("examples/go/working/remove_and_add_imports"))
}

You can then use an IDE (such as Codium with Rust-analyzer) to set up breakpoints to inspect the execution of the test.

Add documentation

The list of supported languages can be updated in doc/src/languages.md and at the end of doc/src/usage.md.

Mergiraf excitedly awaits your pull request!

Architecture

Mergiraf broadly follows the architecture of spork, which is itself documented in the corresponding article. Without requiring familiarity with that article, this page gives an overview of the different steps involved in merging files:

• Parsing the base, left and right revisions with tree-sitter
• Creating matchings between all three pairs of syntax trees with the GumTree classic algorithm
• Creating a class mapping out of the three matchings
• Converting trees to PCS triples
• Merging the set of PCS triples together
• Building the merged tree out of the PCS triples
• Checking for delete/modify conflicts
• Checking for duplicate signatures and marking such as conflicts
• Rendering the merged tree to a text file with conflicts

Those steps represent the core of the structured merge algorithm in Mergiraf. This algorithm is used together with traditional line-based merging to implement the fast mode. Beyond the introduction of this fast mode, Mergiraf differs from Spork in other important ways.

Steps of structured merging

Parsing

Before parsing, line endings are normalized to line-feed characters (if another style of line ending was used, it will be restored at the very end on the merged result). The contents of all three revisions (base, left and right) are then parsed with tree-sitter after detecting their common language based on the file extension. After parsing, leaf nodes which span over multiple lines (such as multi-line comments or string literals) are split into lines, making up new subnodes. This ensures that they are not treated as atomic tokens but are instead merged line-by-line later on.

If a parsing error occurs in any of the three revisions, the algorithm aborts and falls back on line-based merging.

Matching

A matching between two syntax trees is a one-to-one correspondence between nodes of the trees. This includes both internal nodes and leaves. Two nodes are matched when they are similar enough to assume that they correspond to the same content. For instance, two subtrees that are isomorphic (meaning that they have the exact same structure, including the same content in their leaves) are likely to correspond to the same content which is unchanged in both revisions.

For instance, consider the following two revisions:

struct MyStruct {
    first: usize
}

struct MyStruct {
    first: usize,
    other: bool,
}

Their syntax trees are matched as follows, with the added content in the "Left" revision not matched (and highlighted below):

The heuristic we use to produce matchings between syntax trees is the GumTree classic algorithm. For a detailed explanation of the algorithm we recommend reading the associated paper, but we give here a high-level summary. The algorithm works in two phases:

• match all pairs of isomorphic subtrees on both sides, assuming they are sufficiently deep and that they are unique within the revision where they appear. This phase is done in a top-down fashion, meaning that larger subtrees get matched first.
• infer additional matches by inspecting at the ancestors of already matched pairs and matching them if they are deemed similar enough. Similarity is measured by looking at the proportion of their common matched descendants. This phase is done in a bottom-up fashion, by inferring additional matches from the leaves first.

This algorithm is used to match all three pairs of revisions:

• base and left
• base and right
• left and right

When the base revision is involved, the matching heuristic matches additional elements, first by using less conservative parameters for the heurstic above, but also by using the tree edit distance algorithm to infer additional matches between descendants of nodes matched in the second phase.

The reason for using a different heuristic to match the left and right revisions is that any false positive in this matching can have quite detrimental effects on the merged result. Furthermore, this matching only plays a role when the left and right revisions happen to do similar changes on top of the base revision, which is relatively rare in practice.

Class-mapping

Once all pairs of revisions are matched, we create a notion of node identity across all three revisions by considering equivalence classes of the union of all matchings. In other words, if any two nodes are matched, they are considered to be the same. Two nodes are also considered the same if they are both matched to a common node in the third revision.

To simplify the rest of the algorithm, we pick a so-called "leader" among mutually matched nodes, which is used to represent the group. This leader is picked by preference over revisions: the base has priority over the left, which has priority over the right.

The class-mapping retains the correspondence between leaders and their class members, making it possible to look up which node corresponds to a leader in a given revision.

Converting to PCS triples

Each tree is then encoded as a set of "Parent-Child-Successor" (PCS) triples. A triple (p,c,s) means that node p is the parent of both c and s, and that s immediately follows c in the list of children of p. Each node is represented by its leader in its equivalence class. Sentinel nodes are added at the beginning and end of each child list, denoted by ⊣ and ⊢ respectively. Additionally, a virtual root ⊥ is added, also to identify the original root in the tree.

For instance, consider the following tree.

Assuming those nodes readily represent the leaders in their equivalence classes, such a tree will be converted to a set of PCS triples as follows:

(⊥, ⊣, source_file)
(⊥, source_file, ⊢)
(source_file, ⊣, struct_item)
(source_file, struct_item, ⊢)
(struct_item, ⊣, "struct")
(struct_item, "struct", "MyStruct")
(struct_item, "MyStruct", field_declaration_list)
(struct_item, field_declaration_list, ⊢)
(field_declaration_list, ⊣, "{")
(field_declaration_list, "{", field_declaration)
(field_declaration_list, field_declaration, "}")
(field_declaration_list, "}", ⊢)
(field_declaration, ⊣, "first")
(field_declaration, "first", ":")
(field_declaration, ":", "usize")
(field_declaration, "usize", ⊢)

A set of PCS triples is called a "changeset".

Merging PCS triples

Once each revision has been mapped to a changeset, we merge all of the changesets together. To do so, we tag each triple with the revision it came from, obtaining a quadruplet such as (field_declaration, "usize", ⊢, L).

By taking the union of all sets of quadruplets, we create a set of triples which is potentially inconsistent: for instance, it is possible to have quadruplets (p,c,s1,B) and (p,c,s2,L), if the successor of c is not the same in the base and left revision.

We eliminate all quadruplets coming from the base revision which are inconsistent with a triple from the left or right revision. Two quadruplets are inconsistent when:

• they have the same parent and child component, but the successor differs
• they have the same parent and successor component, but the child (predecessor) differs
• one of the child and successor of the first is equal to one of the child and successor of the second, but the parents are different

This pass eliminates some inconsistencies in the set, but not all of them. The remaining ones are handled during the construction of the merged result, where they might be turned into conflicts or resolved on the fly.

Building the merged result

The creation of the merge output is done by attempting to reconstruct a tree out of the merged changesets. It is done recursively, starting from the virtual root, and attempting to read a consistent list of children from the PCS triples.

At this stage, different sorts of inconsistencies can be detected. The article about Spork offers a good overview of those different types in section 3.4.

In many of those situations (such as when conflicting deletions happen on both sides), we simply give up by falling back on a local line-based merge. This is done by obtaining the original source of the parent being reconstructed in all three revisions and merging those using the standard diff3 algorithm.

When the parent node being reconstructed is known to be a commutative parent, we are able to solve more types of conflicts without falling back on line-based merge. When such a conflict happens, we extract the lists of children on all three revisions, and merge them by:

• computing the set of children that the right revision deletes (compared to the base revision)
• computing the set of children that the right revision adds
• finally, taking the list of children on the left, removing those that the right revision removes and appending the ones that it adds

A merged tree is therefore made of the following types of nodes:

• ExactTree: A node that is identical to an original node in the AST of some revision(s). The set of revisions which it can be printed from is a subset of the set of revisions present in this equivalence class (since the tree may not be isomorphic in all such revisions)
• Conflict: A node which represents a conflict, with contents for all three revisions. Those contents are nodes from the ASTs of the original revisions.
• LineBasedMerge: A node which contains text obtained by running classic line-based merging on the sources of an AST node on the three revisions. The original AST node equivalence class is retained.
• MixedTree: An internal node of the merged tree, containing a list of other nodes as children
• CommutativeChildSeparator: A piece of text which does not belong to any of the original revisions. It is inserted between children of a commutative parent if they need separating.

Checking for delete/modify conflicts

Sometimes, one revision makes changes to an element that the other revision deletes:

dismountTire(&wheel);
applyGlueAroundPuncture(&wheel.innerTube);
wait(Duration::minutes(5)); // better wait a bit longer
applyPatch(&wheel.innerTube);

dismountTire(&wheel);
applyGlueAroundPuncture(&wheel.innerTube);
wait(Duration::minutes(2));
applyPatch(&wheel.innerTube);

dismountTire(&wheel);
wheel.innerTube = InnerTube::new(); // otherwise I'll be late to pick up the kids

In such a case, reconstructing the tree out of PCS triples will just give the right revision back, regardless of the fact that the left revision made some changes to elements that the right revision deleted. While this could be the right thing to do in this case, in general we want to avoid this behaviour, because it could be that the deleted elements have actually been moved elsewhere (possibly in a different file), so the user should know that they need to transfer such changes there. The lack of conflict in this case is a known issue of the 3DM merge algorithm.

To make sure that we do emit a conflict, we keep track of deleted nodes as we build the merged tree out of the PCS triples. At the end of the algorithm, we check if any of those nodes has been modified in the other revision. If that is the case, we try to compute a covering of the changes inside the element (let's call it E). This means finding a set of descendants D of the element, such that:

• all descendants in D are present in the deleting revision (meaning that they have been moved elsewhere in the file)
• the changes to E in the modifying revision are all happening within the subtrees rooted in D If we are able to find such a covering, then we conclude that all changes inside E are reflected in the merged file, so we don't need to flag this as a conflict. Otherwise, we modify the merged tree to insert a conflict (by computing a line-based merge for the parent of E).

Checking for duplicate signatures

It is possible that the merged tree contains elements with duplicate signatures. This can happen when the two revisions insert elements with identical signatures without them being in conflicting locations, or if somehow applying changes from both sides made two existing elements get the same signature.

We make one pass over the merged tree and for each commutative parent we encounter, we check if any children have identical signatures. If this is the case, we group them together at the location of the first such element and replace them by a conflict.

Rendering

The merged tree then needs to be converted to a text file. This comes with essentially two challenges:

1. Which whitespace to insert between various parts of the merged tree? In most cases, whitespace is not syntactically significant and is therefore not represented in the AST. However, displaying appropriate whitespace is crucial to make sure the merged output is faithful to the original revisions.
2. How to render conflicts? Because Mergiraf is able to generate granular conflicts, for instance around a binary operator or a single argument of a function call, the boundaries of those conflicts may not match line boundaries. However, the traditional merge conflict markers used by Git (and relied on by many other tools) assume that conflicts are line-based.

The first step of rendering is to convert the merged tree to a stream, consisting of a mixture of successfully merged strings and conflicts (containing all three conflict sides). During this step, whitespace between those tokens is computed by imitating the whitespace from the original revisions, as well as adapting the indentation in case some sections of the source code changed indentation levels.

Then, this stream is further processed to render the conflicts. There are two modes to do so:

• the default mode, which positions conflict markers around the lines containing granular conflicts (giving an experience similar to Git's own behaviour)
• the compact mode, which attempts to display smaller conflicts, potentially by introducing conflict markers inside a line (splitting it onto multiple lines). While this makes for smaller conflicts, it interferes with the formatting of the merged tree. This mode can be enabled with --compact.

Fast mode

By design, Mergiraf first attempts a line-based merge of its input files before running the more costly structured merge algorithm described above. If the line-based merge succeeds without any conflicts, it is returned as merge output.

When conflicts are present in the line-based merge, we do not discard this output either. Instead, we reconstruct fictional base, left and right revisions from the merged file, by selecting each part of the conflicts appropriately. Those fictional revisions are generally not identical to the original revisions we started with, as it is possible that some of the changes got merged without conflicts. Because those fictional revisions come from the same merged file, we are able to pre-compute matchings between all three pairs of revisions, by matching any syntactical element whose extent lies exclusively in a merged area, without any conflicts. This initial matching is fed into the tree matching algorithm, speeding it up significantly as many nodes are readily matched. The rest of the structured merging algorithm is then run unchanged.

This algorithm is also the basis of Mergiraf's interactive mode which attempts to resolve conflicts solely based on a failed line-based merge, without access to the original revisions.

It is worth noting that some conflicts cannot be solved in the fast mode. This is primarily the case when moving edited elements.

Figure 1: Early blueprint of the original architecture

Related work

There are many different approaches to merging diverging files. The awesome-merge-driver list keeps track of implementations that can be used as Git merge drivers. Some of them are flat, meaning that they break down the files as stream of lines or tokens (such as git's native diff3 algorithm). Others (like Mergiraf) are structured, representing the files as abstract syntax trees and merging those trees using dedicated heuristics. We focus on the structured ones here.

There has also been some research around using machine-learning techniques or large language models to solve conflicts. We do not cover those, as none of them appear to be open source so far.

Among structured approaches focused on merging source code, we are aware of the following systems:

Also worth noting is IntelliMerge, which merges sets of files (instead of individual files, as is the case for all systems above).

Overview of the differences with Spork

In this section we list the main ways in which Mergiraf differs from Spork, the existing system it is most similar to.

Applicability to languages beyond Java

Spork is explicitly restricted to Java. This lies primarily in its reliance on Spoon, a Java parser, but also on some heuristics (such as detection of Java methods with identical signatures as an additional post-processing step). Instead, Mergiraf supports a wider range of languages, similarly to FSTMerge.

Better faithfulness to existing syntax

In certain cases, Spork normalizes some syntactic elements (such as adding brackets around sub-expressions or grouping together declarations of local variables of the same type). This can happen even if the elements are not involved in conflicting changes and seems to be due to the Spoon parser.

In contrast to this, Mergiraf sticks to the original syntax (by the simple fact that it does not embed the language-specific knowledge to carry out such normalizations).

Support for delete/modify conflicts

A delete/modify conflict is a situation where one side deletes an element while the other side makes changes to it. In such cases, Spork does not emit a conflict and just deletes the element. This can be a problem as the changes made by the other side are lost. In certain cases, those changes should instead be replayed elsewhere (for instance, in a different file). For this reason, Mergiraf emits a conflict in such a case.

Speed

Being a Java application, Spork is not well suited for use as a git merge driver. Such uses spawn one process per file to be merged, which causes a Java Virtual Machine to boot up each time. Attempts to bundle it as a native executable have been inconclusive. In contrast to this, Mergiraf is a binary with much smaller start-up times, and its overall runtime is closer to that of Git's embedded merge algorithms.