A new version

Part 2: Merging, patches, and pijul

In the last post, I talked about a mathematical framework for a version control system (VCS) without merge conflicts. In this post I’ll explore pijul, which is a VCS based on a similar system. Note that pijul is under heavy development; this post is based on a development snapshot (I almost called it a “git” snapshot by mistake), and might be out of date by the time you read it.

The main goal of this post is to describe how pijul handles what other VCSes call conflicts. We’ll see some examples where pijul’s approach works better than git’s, and I’ll discuss why.

Some basics

I don’t want to write a full pijul tutorial here, but I do need to mention the basic commands if you’re to have any hope of understanding the rest of the post. Fortunately, pijul commands have pretty close analogues in other VCSes.

Dealing with conflicts

As I explained in the last post, pijul differs from other VCSes by not having merge conflicts. Instead, it has (what I call) graggles, which are different from files in that their lines form a directed acyclic graph instead of a totally ordered list. The thing about graggles is that you can’t really work with them (for example, by opening them in an editor), so pijul doesn’t let you actually see the graggles: it stores them as graggles internally, but renders them as files for you to edit. As an example, we’ll create a graggle by asking pijul to perform the following merge:

Here are the pijul commands to do this:

$ pijul init

# Create the initial file and record it.
$ cat > todo.txt << EOF
> to-do
> * work
> EOF
$ pijul add todo.txt
$ pijul record -a -m todo

# Switch to a new branch and add the shoes line.
$ pijul fork --branch=master shoes
$ sed -i '2i* shoes' todo.txt
$ pijul record -a -m shoes

# Switch to a third branch and add the garbage line.
$ pijul fork --branch=master garbage
$ sed -i '2i* garbage' todo.txt
$ pijul record -a -m garbage

# Now merge in the "shoes" change to the "garbage" branch.
$ pijul pull . --from-branch shoes

The first thing to notice after running those commands is that pijul doesn’t complain about any conflicts (this is not intentional; it’s a known issue). Anyway, if you run the above commands then the final, merged version of todo.txt will look like this:

That’s… a little disappointing, maybe, especially since pijul was supposed to free us from merge conflicts, and this looks a lot like a merge conflict. The point, though, is that pijul has to somehow produce a file – one that the operating system and your editor can understand – from the graggle that it maintains internally. The output format just happens to look a bit like what other VCSes output when they need you to resolve a merge conflict.

As it stands, pijul doesn’t have a very user-friendly way to actually see its internal graggles. But with a little effort, you can figure it out. The secret is the command

RUST_LOG="libpijul::backend=debug" pijul info --debug

For every branch, this will create a file named debug_<branchname> which describes, in graphviz’s dot format, the graggles contained in that branch. That file’s a bit hard to read since it doesn’t directly tell you the actual contents of any line; in place of, for example, “to-do”, it just has a giant hex string corresponding to pijul’s internal identifiers for that line. To decode everything, you’ll need to look at the terminal output of that pijul command above. Part of it should look like this:

DEBUG:libpijul::backend::dump: ============= dumping Contents
DEBUG:libpijul::backend::dump: > Key { patch: PatchId 0x0414005c0c2122ca, line: LineId(0x0200000000000000) } Value (0) { value: [Ok("")] }
DEBUG:libpijul::backend::dump: > Key { patch: PatchId 0x0414005c0c2122ca, line: LineId(0x0300000000000000) } Value (12) { value: [Ok("to-do\n")] }

By cross-referencing that output with the contents of debug_<branchname>, you can reconstruct pijul’s internal graggles. Just this once, I’ve done it for you, and the result is exactly as it should be:

What should I do with a conflict?

Since pijul will happily work with graggles internally, you could in principle ignore a conflict and work on other things. That’s probably a bad idea for several reasons (for starters, there are no good tools for working with graggles, and their presence will probably break your build). So here’s my unsolicited opinion: when you have a conflict, you should resolve it ASAP. In the example above, all we need to do is remove the >>> and <<< lines and then record the changes:

$ sed -i 3D;5D todo.txt
$ pijul record -a -m resolve

To back up my recommendation for immediate flattening, I’ll give an example where pijul’s graggle-to-file rendering is lossy. Here are two different graggles:

But pijul renders both in the same way:

This is a perfectly good representation of the graggle on the right, but it loses information from the one on the left (such as the fact that both “home” lines are the same, and the fact that “shop” and “home” don’t have a prescribed order). The good news here is that as long as your graggle came from merging two files, then pijul’s rendering is lossless. That means you can avoid the problem by flattening your graggles to files after every merge (i.e., by resolving your merge conflicts immediately). Like cockroaches, graggles are important for the ecosystem as a whole, but you should still flatten them as soon as they appear.

Part 1: Merging and patches

A recent paper suggested a new mathematical point of view on version control. I first found out about it from pijul, a new version control system (VCS) that is loosely inspired by that paper. But if you poke around the pijul home page, you won’t find many details about what makes it different from existing VCSes. So I did a bit of digging, and this series of blog posts is the result.

In the first part (i.e. this one), I’ll go over some of the theory developed in the paper. In particular, I’ll describe a way to think about patches and merging that is guaranteed to never, ever have a merge conflict. In the second part, I’ll show how pijul puts that theory into action, and in the third part I’ll dig into pijul’s implementation.

Before getting into some patch theory, a quick caveat: any real VCS needs to deal with a lot of tedious details (directories, binary files, file renaming, etc.). In order to get straight to the interesting new ideas, I’ll be skipping all that. For the purposes of these posts, a VCS only needs to keep track of a single file, which you should think of as a list of lines.

Patches

A patch is the difference between two files. Later in this series we’ll be looking at some wild new ideas, so let’s start with something familiar and comforting. The kind of patches we’ll discuss here go back to the early days of Unix:

In order to actually have a useful VCS, you need to be able to delete lines also. But deleting lines turns out to add some complications, so we’ll deal with them later.

For an example, let’s start with a simple file: my to-do list for this morning.

Looking back at the list, I realize that I forgot something important. Here’s the new one:

To go from the original to-do list to the new one, I added the line with the socks. In the format of the original Unix “diff” utility, the patch would look like this:

The “1a2” line is a code saying that we’re going to add something after line 1 of the input file, and the next bit is obviously telling us what to insert.

Since this blog isn’t a command line tool, we’ll represent patches with pretty diagrams instead of flat files. Here’s how we’ll draw the patch above:

Hopefully it’s self-explanatory, but just in case: an arrow goes from left to right to indicate that the line on the right is the same as the one on the left. Lines on the right with no arrow coming in are the ones that got added. Since patches aren’t allowed to re-order the lines, the lines are guaranteed not to cross.

There’s something implicit in our notation that really needs to be said out loud: for us, a patch is tied to a specific input file. This is the first point where we diverge from the classic Unix ways: the classic Unix patch that we produced using “diff” could in principle be applied to any input file, and it would still insert “* put on socks” after the first line. In many cases that wouldn’t be what you want, but sometimes it is.

Merging

The best thing about patches is that they can enable multiple people to edit the same file and then merge their changes afterwards. Let’s suppose that my wife also decides to put things on my to-do list: she takes the original file and adds a line:

Now there are two new versions of my to-do list: mine with the socks, and my wife’s with the garbage. Let’s draw them all together:

This brings us to merging: since I’d prefer to have my to-do list as a single file, I want to merge my wife’s changes and my own. In this example, it’s pretty obvious what the result should be, but let’s look at the general problem of merging. We’ll do this slowly and carefully, and our endpoint might be different from what you’re used to.

Patch composition

First, I need to introduce some notation for an obvious concept: the composition of two patches is the patch that you would get by applying one patch and then applying the other. Since a “patch” for us also includes the original file, you can’t just compose any two old patches. If p is a patch taking the file O to the file A and r is a patch taking A to B, then you can compose the two (but only in one order!) to obtain a patch from O to B. I’ll write this composition as pr: first apply p, then r.

It’s pretty easy to visualize patch composition using our diagrams: to compute the composition of two paths, just “follow the arrows”

to get the (dotted red) patch going from O to B.

Merging as composition

I’m going to define carefully what a merge is in terms of patch composition. I’ll do this in a very math-professor kind of way: I’ll give a precise definition, followed by some examples, and only afterwards will I explain why the definition makes sense. So here’s the definition: if p and q are two different patches taking the file O to the files A and B respectively, a merge of p and q is a pair of patches r and s such that

We can illustrate this definition with a simple diagram, where the capital letters denote files, and the lower-case letters are patches going between them:

Instead of saying that pr = qs, a mathematician (or anyone who wants to sound fancy) would say that the diagram above commutes.

Here is an example of a merge:

And here is an example of something that is not a merge:

This is not a merge because it fails the condition pr = qs: composing the patches along the top path gives

but composing them along the bottom path gives

Specifically, the two patches disagree on which of the shoes in the final list came from the original file. This is the real meaning underlying the condition pr = qs: it means that there will never be any ambiguity about which lines came from where. If you’re used to using blame or annotate commands with your favorite VCS, you can probably imagine why this sort of ambiguity would be bad.

A historical note

Merging patches is an old idea, of course, and so I just want to briefly explain how the presentation above differs from “traditional” merging: traditionally, merging was defined by algorithms (of which there are many). These algorithms would try to automatically find a good merge; if they couldn’t, you would be asked to supply one instead.

We’ll take a different approach: instead of starting with an algorithm, we’ll start with a list of properties that we want a good merge to satisfy. At the end, we’ll find that there’s a unique merge that satisfies all these properties (and fortunately for us, there will also be an efficient algorithm to find it).

Merges aren’t unique

The main problem with merges is that they aren’t unique. This isn’t a huge problem by itself: lots of great things aren’t unique. The problem is that we usually want to merge automatically, and an automatic system needs an unambiguous answer. Eventually, we’ll deal with this by defining a special class of merges (called perfect merges) which will be unique. Before that, we’ll explore the problem with some examples.

A silly example

Let’s start with a silly example, in which our merge tool decides to add some extra nonsense:

No sane merge tool would ever do that, of course, but it’s still a valid merge according to our rule in the last section. Clearly, we’ll have to tighten up the rules to exclude this case.

A serious example

Here is a more difficult situation with two merges that are actually reasonable:

Both of these merges are valid according to our rules above, but you need to actually know what the lines mean in order to decide that the first merge is better (especially if it’s raining outside). Any reasonable automatic merging tool would refuse to choose, instead requiring its user to do the merge manually.

The examples above are pretty simple, but how would you decide in general whether a merge is unambiguous and can be performed automatically? In existing tools, the details depend on the merging algorithm. Since we started off with a non-algorithmic approach, let’s see where that leads: instead of specifying explicitly which merges we can do, we’ll describe the properties that an ideal merge should have.

Perfect merges

The main idea behind the definition I’m about to give is that it will never cause any regrets. That is, no matter what happens in the future, we can always represent the history just as well through the merge as we could using the original branches. Obviously, that’s a nice property to have; personally, I think it’s non-obvious why it’s a good choice as the defining property of the ideal merge, but we’ll get to that later.

Ok, here it comes. Consider a merge:

And now suppose that the original creators of patches p and q continued working on their own personal branches, which merged sometime in the future at the file F:

We say that the merge (r, s) is a perfect merge if for every possible choice of the merge (u, v), there is a unique patch w so that u = rw and v = sw. (In math terms, the diagram commutes.) We’re going to call w a continuation, since it tells us how to continue working from the merged file. To repeat, a merge is perfect if for every possible future, there is a unique continuation.