Mergiraf – AST-Oriented Tool for Three-Way Merging in Git

The Mergiraf 0.4 project release has been published, introducing a driver for Git to implement three-way merging. Mergiraf supports resolving various types of merge conflicts and can be used with different programming languages and file formats. It can be invoked independently to handle conflicts that arise with standard Git or replace Git’s default merge handler to enhance commands such as merge, revert, rebase, and cherry-pick. The code is distributed under the GPLv3 license. The new version adds support for Python, TOML, Scala, and TypeScript, as well as performance optimizations.

---

Problems Solved by Mergiraf

Software development exemplifies an incredibly complex system. Complex systems share one characteristic: they are inherently challenging to manage, and their desired behavior does not emerge by chance. Instead, such systems evolve over time, step by step, with each change carefully tested. Achieving this requires a well-defined structure and appropriate tools.

The evolution of any complex system can be visualized as a directed tree, where the root represents an empty set of features, and each node—except for the root—represents the result of applying a mutation to its parent.

In the context of software products, each node is called a version, representing a particular set of features and anti-features. Any change to this set is considered a mutation, forming an edge in the directed acyclic graph. These features are inherently abstract; they reflect not the physical systems but the utility that intelligent agents perceive in these systems. To turn these ideas into reality, developers must work with low-level details expressed in programming languages.

Snapshots and Changesets

To gradually refine source code into a state that exhibits the desired behavior, and to document how this is achieved, programmers use snapshots and changesets.

• A snapshot represents a specific state of the product, capturing all low-level details.
• A changeset represents the transition between snapshots.

Typically, snapshots are derived from single changesets, so these terms are often used interchangeably. However, there are exceptions, such as merge commits, which result from multiple transitions. These are notoriously difficult to manage and are usually avoided.

Modern version control systems, like Git, provide basic capabilities for managing development workflows. Developers can organize snapshots as directed acyclic graphs, annotate them with comments, and rearrange their order as needed. This functionality helps developers write semantically meaningful project histories, which are critical for debugging and answering questions like:

• “Why was this low-level detail (e.g., a variable) introduced?”
• “What is my contribution to this project?”
• “Who implemented this feature, and when?”
• “What change caused this bug, even though it shouldn’t have?”

Branching and Collaboration

Version control systems also support branches, which represent continuous pieces of project history. Developers use branches to:

• Implement specific features.
• Test multiple candidate implementations.
• Combine results from various contributors without manually merging everything each time.

A typical workflow involves a main branch representing the official product, with side branches for each feature. Developers synchronize side branches with the main branch regularly (ideally after each commit) to:

• Work with the latest product version.
• Detect issues caused by other developers early.

Challenges with Merging

Combining changes from different snapshots (a process involving finding a common ancestor and applying changes sequentially) can lead to conflicts. Modern VCS tools rely on line-by-line merging algorithms, which treat files as sequences of lines and apply bioinformatics-style algorithms to merge them. While simple and universal, this approach has significant limitations:

1. Content-Agnostic: Line-by-line algorithms ignore the semantics of source code.
2. Inconsistencies: They often produce incorrect merges, requiring developers to manually resolve conflicts.
3. Poor Large-Change Support: Large or trivial changes (e.g., code reformatting) can break these algorithms.

Developers must carefully study both versions of code, resolve inconsistencies, and sometimes even re-examine the entire project. These problems are exacerbated when the algorithm fails to detect conflicts or produces non-working code—for instance, when one developer renames a variable while another uses it in new code.

A Better Approach

The ideal solution involves using a semantic model of the code instead of a line-by-line heuristic. While research in this area has been ongoing for decades, practical open-source implementations only began emerging in the early 2010s, primarily focusing on Java.

• GumTree: A Java-based tool that generates abstract representations of source code changes but does not support merging changes out of the box.
• Difftastic: A Rust-based tool for visualizing diffs in the console but lacks functionality for merging or applying patches.

This is where Mergiraf steps in.

---

What Mergiraf Brings to the Table

Mergiraf is a Rust-based tool that leverages the Tree-sitter parser for context-free grammar parsing. Unlike its predecessors, Mergiraf focuses on automatically resolving merge conflicts rather than merely visualizing diffs.

Key Features

1. Automatic Merge Conflict Resolution:
   • Uses GumTree’s algorithm for patch generation.
   • Adapts Spork’s algorithm for applying changes.
2. Support for Multiple Languages:
   • Python, TOML, Scala, TypeScript, and more.
3. Compact and Efficient:
4. Conflict Visualization:
   • Helps developers understand and resolve unresolved issues.

Limitations

• Patch Serialization:
  • Mergiraf does not yet support serializing patches for later application, though this could be implemented via GumTree’s event logs.
• Global Style Awareness:
  • Lacks support for global styles (e.g., .editorconfig), making it less effective for handling large formatting changes.

Example

Given the following files:

Base File (base.py)

tab_indentation = True

foo = 1

def main():
    print(foo + 2 + 3)

Modified File A (a.py)

from icecream import ic

foo = 1

def main():
    ic(foo + 2 + 3)

class Baz:
    def __init__(self):
        """Baz class"""

Modified File B (b.py)

bar = 1

def main():
    print(bar + 2 + 3)

Execution

./mergiraf merge ./base.py ./a.py ./b.py -x a.py -y b.py -s base.py -o ./res.py

Result

from icecream import ic

bar = 1

def main():
    ic(bar + 2 + 3)

class Baz:
    def __init__(self):
        """Baz class"""

This output resolves the merge conflicts, maintaining changes from both branches while preserving code semantics. However, the mix of tabs and spaces in indentation reveals an area for improvement: Mergiraf should better integrate with .editorconfig or similar tools to enforce global styles.

---

Conclusion

Mergiraf represents a significant step forward in merging tools for Git. By leveraging abstract syntax trees (ASTs), it provides developers with a more reliable way to resolve conflicts, supporting a wide range of languages and workflows. While there are areas for improvement, Mergiraf’s innovations make it a compelling choice for modern software development workflows.