The release of the mergiraf project 0.4 has been published, developing a driver for Git with the implementation of three-way merging capabilities. Mergiraf supports resolving various types of merge conflicts and can be used for different programming languages and file formats. It can either be invoked separately for handling conflicts that arise while working with standard Git or replace the merge handler in Git to extend the functionality of 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. <\/p>\n
Below is a detailed description of the issues addressed by mergiraf: <\/p>\n
Software is a prime example of an extremely complex system. Complex systems share one common feature \u2014 they are COMPLEX \u2014 and you cannot expect that the desired complex behavior will arise by itself, by chance. Instead, these systems evolve over time, step by step, and each mutation is carefully checked at every stage. 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 functions, and every node \u2014 except for the root \u2014 is the result of applying a mutation to its parent. <\/p>\n
In the context of products, each node is called a 'version', representing a specific set of functions and anti-functions. Any change to this set is considered a mutation, forming an edge in our directed acyclic graph. These functions are inherently abstract; they do not directly reflect how physical systems operate but rather illustrate how rational agents perceive the usefulness of these systems. To translate ideas into real-world implementations, one must roll up their sleeves and dive into *sufficiently* low-level details, in a language that can express and explain exactly how everything works. In software development, these low-level details are typically represented by source code. <\/p>\n
To gradually bring the source code into a state that exhibits the required behavior and to document how they arrived there, programmers present their work in terms of snapshots and changesets. A snapshot represents a specific state of the product with all low-level details, while a changeset denotes the transition between snapshots. Typically, snapshots are generated from individual changesets to their parents, which is why these snapshots almost always bear the marks of the changesets that created them, making these terms often used interchangeably. <\/p>\n
Sometimes snapshots exist as a result of multiple transitions \u2014 commit merges. These can be difficult to work with, so they are usually avoided. Modern open-source version control systems, such as Git, provide quite basic capabilities for managing development workflows. They allow developers to organize snapshots as directed acyclic graphs, annotate them with comments, and change their order if necessary. <\/p>\n
This functionality allows developers to write a semantically meaningful project history, which is critical for debugging and answering questions like, \"Why was this low-level detail (e.g., variable) introduced?\", \"What percentage is my contribution to this project?\", \"Who was hacked by the backdoor implementation and when?\", \"What low-level change broke this function (even though it shouldn't have, we checked everything!?)\" <\/p>\n
Version control systems complement this with the concept of a branch \u2014 a low-level idea that simply means a continuous fragment of low-level project history, semantically significant for the developer. Branches are typically used for specific feature implementations, sometimes multiple branches are created for different candidates of the same feature implementation. By using branching workflows (which are actually mainstream and the standard of development, used everywhere), each individual developer can effectively manage many conflicting project branches, each differing in readiness or quality. This allows developers to combine the results of their own and others' efforts without having to rewrite everything manually each time. <\/p>\n
Typically, a main branch is created to represent the \"official\" product, from which side branches are made for each feature, which are regularly (ideally \u2014 after each commit) synchronized with the main branch, allowing developers to work with the most up-to-date version of the product while simultaneously incorporating features they are currently developing, detecting issues arising from the actions of other developers as early as possible. <\/p>\n
When trying to combine the functions of various snapshots (which simply means finding a common ancestor and applying the changesets it produces sequentially on top of another, this operation is called rebase; merging, on the other hand, is somewhat like rebase but structures the commit graph differently, making it less convenient to manipulate, which is why merging is usually avoided in favor of rebases), issues arise. Modern version control systems (VCS) use internal algorithms to merge changes that break files down into individual lines, considering each line as a symbol and the files as sequences, and then apply algorithms for their merging that originate from bioinformatics. <\/p>\n
Unfortunately, this line-by-line representation of source code has nothing to do with its content. Its only merit is its simplicity and universality. This mismatch leads to conflicts, being a constant source of headaches for developers. Resolving conflicts requires developers to thoroughly review both versions of the code, not just the portions marked as 'modified' or 'conflicting' by the line-by-line comparison algorithm, but possibly the entire project. <\/p>\n
The developer must understand the changes, manually write the merged code, and eliminate any discrepancies. The number of problems increases significantly when the line-by-line tool misidentifies changes, which often happens during major modifications, including trivial ones like code reformatting. If subsequent changes cannot be applied to the manually merged code, the situation turns into a complete nightmare. Despite the horrific cases, in most instances, the line-by-line algorithm works, especially if developers actively try not to create problems for it. One way to minimize such issues is to require source code to be processed by canonicalization tools, such as black. <\/p>\n
Of course, the right solution for terrifying cases (and generally, not only for them, line-by-line algorithms \u2014 this is a heuristic, and can trivially lead to non-working code. For example, one developer renamed a variable while another wrote new code using that variable. There will be no merge\/rebase conflict, but the result can become non-functional) \u2014 is using the correct internal model. <\/p>\n
Despite the fact that research in this area has been ongoing for about 30 years, leading to the creation of several proprietary commercial products, this research had only recently been transformed into practically applicable products with open source. The majority of FOSS solutions began to develop in the early 2010s and were primarily focused on the Java language. <\/p>\n
The most notable free implementation of that period, GumTree, was created by a researcher with an academic background, written in Java, featuring its own abstract internal representation that precedes treesitter. It has backends that are both based on treesitter and other tools for parsing source code into abstract representations. This system can only generate (in the form of a textual event log, with an API that can be trivially called from any programming language that has bindings to Java) and visualize changes. However, it is not suitable out of the box for merging changes or viewing the generated diff files (though it is likely that loading diffs could be implemented through the API). <\/p>\n
A younger and more practically applicable implementation, difftastic, is written in Rust, based on treesitter, and focuses on generating highlighted diffs in the console. This system aims at visualizing diffs and does not target merging changes or applying patches. <\/p>\n
Recently, the mergiraf project has appeared and is actively developing. This tool, written in Rust (takes up 21 MiB!), is also based on treesitter, which has become just as standard for parsing context-free grammars in development tools as LLVM has for optimizing low-level instruction representations. Unlike its competitors, mergiraf provides features not for generating diffs, but for automatically resolving merge conflicts. Under the hood, mergiraf uses an implementation of the algorithm used in GumTree for generating patches, and for applying \u2014 an implementation of the algorithm used in spork, adapted for treesitter structures. <\/p>\n
Unfortunately, the serialization of patches into files that can later be applied has not been implemented (but it is quite likely that it could be achieved by parsing the event logs generated by GumTree). Another promising way to apply differences could be through LSP servers' refactoring capabilities, which may help in detecting conflicts at the project-wide level. Visualization is only supported for conflicts. <\/p>\n
Example of operation: common ancestor «base.py» (indents with tabs, extra line at the beginning) foo = 1 def main(): print(foo + 2 + 3) «a.py» (tabs still for indenting, 2 extra lines at the beginning instead of one, icecream library used for debugging prints, class «baz» added: from icecream import ic foo = 1 def main(): ic(foo + 2 + 3) class baz: def __init__(self): «»»baz»»» «b.py» (variable «foo» renamed to «bar», processed with «black» after changes, resulting indents \u2014 spaces, and extra lines removed): bar = 1 def main(): print(bar + 2 + 3) Calling .\\\/mergiraf merge .\\\/base.py .\\\/a.py .\\\/b.py -x a.py -y b.py -s base.py -o .\\\/res.py gives the following result from icecream import ic bar = 1 def main(): ic(bar + 2 + 3) class baz: def __init__(self): «»»baz»»» (the icecream library was used for debugging prints, the variable «foo» was renamed to «bar», processed with «black» after changes, resulting in indents as spaces and extra lines removed, a mix of tabs and spaces for indentation, but in an allowed form). <\/p>\n