Reorganizing libpijul

Saturday, April 9, 2016
By Pierre-Étienne Meunier

Now that Sanakirja is in a usable state, the main operation before we can start to use Pijul for other purposes than tests is to plug Sanakirja in. This post describes our strategy for doing this, and the difficulties we’ve had.

Detaching the backend

This is the part I want to blog about, since I’ve had a really hard time figuring out how to do it. The main problem comes from the following patterns we use all the time in Pijul:

Iterating on the database

Using closures: fails

This means doing something for every key and value in increasing order, starting from a particular key and value. When we designed the format of Pijul repositories, we chose the order of edge flags carefully, so that edge flags that are often iterated together are ordered consecutively.

Initially, I wanted to use closures to iterate, as Sanakirja can do this without allocating a single byte on the heap. I had a Backend trait, with the following function (among others):

trait Backend {

  fn iter<'a, F:FnMut(&'a[u8],&'a[u8]) -> bool> (
      &'a self, key0:&[u8], value0:&[u8], mut f:F
  ) {


In other words, my iterator was borrowing the backend for lifetime 'a, and applying function f on slices with the same lifetime. Unfortunately, this is not usable in real cases (at least not in Rust 1.6), since the only thing such a method would be useful for would be to change stuff in its borrowed environment. But then Rust thinks that closure f might outlive the function that called iter.

I’m not sure why this happens, since f must have returned by the end of the call to iter, and it does not implement the Send trait, which would be necessary to move it to another thread.

Using iterators: fails

Then, another design, compatible with the for notation of Rust, is to use iterators. Iterators have another main advantage: they can be used with tons of methods such as take_while or map, which will allow us to simplify the harder parts of our code.

The first drawback is, iterators are stateful, which means that Sanakirja will need to allocate a vector on the heap. Since Sanakirja is also written in Rust, the borrow checker could allow us to perform this allocation only once, and still be safe and usable. In contrast, there’s no way in Rust to use two nested LMDB cursors, as they’re both mutable, and borrow the transaction.

So, I rewrote my trait:

trait Backend {

  type Iter:Iterator;

  fn iter(&self, key0:&[u8], value0:&[u8]) -> Self::Iter {


But then, Iter is not just any iterator, it yields only pairs of byte slices, valid for “at least” the time self is borrowed by iter. Since Rust’s associated types (or type families) do not accept parameters (it’s actually an RFC), the only way this is possible is the following:

trait Backend<'a> {

  type Iter:Iterator <Item = (&'a[u8], &'a[u8])>;

  fn iter(&'a self, key0:&[u8], value0:&[u8]) -> Self::Iter {


This had hit me in other projects before (in particular Coturnix), but now I understand the problem. The issue now, is that this is not usable either. For instance, if I want to iterate and the change the database, I cannot simply do this:

fn test<'a, B:Backend<'a>>(backend:&mut B)
    for (x,y) in backend.iter(b"key", b"value") {
       println!("{:?}", (x,y))
  backend.put(b"bla", b"bli");

Because when I call backend.iter, it has the effect of borrowing backend for lifetime 'a, which is defined beforehand, and can therefore not be the small scope I defined aroudn the for loop. When the borrow checker runs into backend.put, it sees an immutable borrow in lifetime 'a, which is larger than the current scope, and refuses to borrow backend mutably.

Edit: this blog has no comments, but someone posted this post on reddit, and people rightfully commented that “higher ranked lifetimes”, documented here, solve the problem. I didn’t know about these, thanks to dbaupp and bjzaba for the explanation!

However, we can’t use them in Pijul, since child transactions in Sanakirja are implemented with a different type from their parent. This disallows arbitrarily nested transactions, but I couldn’t see any use case, and the implementation of commit is chosen at compile time rather than with an if (for a really tiny performance gain, of course).

Living without traits/typeclasses

Alright then, what if I still want to have both LMDB and Sanakirja as possible backends? Since Sanakirja is not widely used and tested, bugs observed in Pijul might sometimes come from Sanakirja. Changing backends would make the codebase more robust, and force us to define a precise semantics for backend operations.

Then, I decided to do a very Ocamlish thing: using modules as the poor man’s typeclasses. The difference is that the module support in Rust is not as good as in Ocaml (obviously, typeclasses are usually easier to use and less verbose), and hence I believe there’s no way to say “import this module and check it has that signature”.

Anyway, I now have a file called, with the following definitions:

mod backend {
   struct Repository<'environment> { .. }
   impl Repository<'environment> {

Which I can then use by writing the following in

mod lmdb_backend;
pub use lmdb_backend::backend;

And then, from child modules of lib:

use super::backend::*;

What could improve this situation?

For the iterators, it’s probably not a huge problem in Pijul: I can restrict allocations to a constant number per transaction, and there are already heap allocations even in non-mutable transactions, like caches to avoid running into loops (as Pijul generalizes files to something that can contain loops).

For the traits, two things would improve the situation:

Large values

For large values, the Sanakirja API is not as nice as the LMDB one, the main reason being a focus on simplicity and on-disk-compactness rather than ease of use.

In Sanakirja, large values are returned as an iterator over &[u8], whereas LMDB returns a &[u8]. The implications on the file layout are clear: LMDB manages a free pages in a fancy way, which allows it to detect consecutive free pages. Then, when allocating a value spanning on several pages, it finds consecutive free pages, and if there’s none, it expands the file. The consequence of this is that the file might become relatively scarce when many large values are allocated.

Sanakirja has a different tradeoff, where all values are always returned as an iterator. In the future, we might introduce new methods that return a single slice and panic on large values.

This repeats all the problems we’ve had with iterators. The solution is the same: embed an Iter type in the backend module, and verify manually that all backends have the same module signature.

Splitting modules

Then, we’re also undertaking the important task of splitting the 3000 lines of the main file in libpijul into smaller modules. So far, the structure and interdependencies were not easy to understand from the source.

For my defense, I will argue that code based on theory is highly likely to be of this form in the early versions, since the things you can explain in five minutes and two drawings on a whiteboard can sometimes take five lines, sometimes five hundred lines, to write efficiently.

Anyway, now our module structure looks like:

 ├── mod fs_representation
 ├── mod lmdb_backend
     └── mod backend
 ├── mod file_operations
 ├── mod patch
 ├── mod graph
 ├── mod diff
 ├── mod record
 ├── mod output_repository
 └── mod apply