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.
Below is a detailed description of the issues addressed by mergiraf:
Software is a prime example of an extremely complex system. Complex systems share one common propertyâthey are COMPLEXâand you cannot expect the desired complex behavior to emerge spontaneously or by chance. Instead, these systems evolve over time, step by step, and each mutation is carefully verified at every stage. To achieve this, a well-defined structure and appropriate tools are necessary. The evolution of any complex system can be visualized as a directed tree, where the root represents an empty set of functions, and each nodeâexcept for the rootârepresents the result of applying a mutation to its parent.
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 demonstrate how rational agents perceive the utility 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 precisely how everything works. In software development, these low-level details are typically represented by source code.
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.
Sometimes, there are snapshots resulting from multiple transitions â merging commits. These are difficult to work with, so they are generally avoided. Modern open-source version control systems, such as Git, provide basic capabilities for managing development workflows. They allow developers to organize snapshots in the form of directed acyclic graphs, annotate them with comments, and change their order if necessary.
This functionality enables developers to write a semantically meaningful history of the project, which is crucial for debugging and answering questions like, 'Why was this low-level detail (e.g., variable) introduced?', 'Approximately what percentage is my contribution to this project?', 'Who was compromised by the backdoor implementation and when?', 'What low-level change broke this feature (even though it shouldn't have, we checked everything!?)'
Version control systems complement this concept with branchingâa low-level term that simply denotes a continuous fragment of the project's low-level history, semantically significant to the developer. Branches are typically used for specific feature implementations, and multiple branches may be created for different candidates implementing the same feature. By using branching workflows (which are essentially mainstream and the standard for development, utilized everywhere), each individual developer can effectively manage many conflicting project branches, each varying in terms of readiness or quality. This allows developers to combine the outcomes of their work and others without manually redoing everything each time.
Typically, a main branch is created representing the 'official' product, from which side branches branch off for each feature, which are regularly (ideallyâafter each commit) synchronized with the main branch. This enables developers to work with the most up-to-date version of the product while concurrently integrating the features they are currently developing, detecting issues arising from the actions of other developers as early as possible.
When trying to combine features from various snapshots (which simply means finding a common ancestor and applying the changesets that produce them sequentially on top of another, this operation is called rebase, while merging is almost like rebaseâjust structuring the commit graph differently, making it troublesome to manipulate, hence merges are often avoided in favor of rebases), problems can arise. Modern version control systems (VCS) use internal algorithms to merge changes, which simply break files down into individual lines, treat each line as a symbol, and files as their sequences, then apply algorithms for their merging, which originate from bioinformatics.
Unfortunately, such a line-by-line representation of the source code has nothing to do with its content. Its only advantage is that it is simple and universal. This discrepancy leads to conflicts, serving as a constant source of headaches for developers. Resolving conflicts requires the developer to carefully review both versions of the code, not only the sections marked by the line-by-line comparison algorithm as 'modified' or 'conflicting' but possibly the entire project.
The developer must understand the changes, manually write the merged code, and resolve any discrepancies. The problems increase when the line-by-line tool incorrectly identifies changes, which often occurs with major alterations, including trivial ones like code formatting. If subsequent changes cannot be applied to the manually merged code, the situation becomes a complete nightmare. Despite the alarming cases, in most situations, the line-by-line algorithm works, especially if developers actively try not to create issues for it. One way to minimize such problems is to mandate the processing of sources with canonicalization tools like black.
Of course, the correct solution to these alarming cases (and in general, not just for them, as the line-by-line algorithm is a heuristic, which can trivially lead to non-working code, for example, one developer renamed a variable while another was writing a piece of new code using that variable; there wonât be a merge/rebase conflict, but the result will become non-functional) is to use the right internal model.
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.
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).
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.
Recently, the mergiraf project has emerged and is actively developing. This tool, written in Rust (taking up 21 MiB!), is also based on treesitter, which has become as much a standard for parsers of context-free grammars in development tools as LLVM has for optimizing low-level instruction representations. Unlike its competitors, mergiraf provides functionality not for generating diffs, but for automatic resolution of merge conflicts. Under the hood, mergiraf uses the implementation of the algorithm for generating patches used in GumTree and the implementation for applying them used in spork, adapted for treesitter structures.
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.
Example of operation: the common ancestor «base.py» (tabs for indentation, extra line at the top) foo = 1 def main(): print(foo + 2 + 3) «a.py» (indents still using tabs, 2 extra lines at the top instead of one, for debugging print the icecream library is used, added class «baz»: 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 in spaces for indentation and extra lines cut out): 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»»» (for debugging print the «icecream» library is used, variable «foo» is renamed to «bar», processed with «black» after changes, resulting in spaces for indentation and extra lines cut out, mixed tabs and spaces for indentation, but allowed form).
Here, the drawback of the tool is evident. The document style is usually configured in «.editorconfig» files, and global style changes, such as switching from tabs to spaces and adopting the style of black, as done in «b.py», are typically accompanied by changes in «.editorconfig». Therefore, for a more accurate application of such changes, the tool should have a concept of a global «default» style, and be able to pull settings from «.editorconfig».
Source: opennet.ru
