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!