Not Forking

From Dan Shearer CV

Not-forking is a technical tool for software development.

Here are some simple ways of explaining what Not-forking can do:

  • Not-forking lets you integrate non-diffable codebases, a bit like patch/sed/diff/cp/mv rolled into one.
  • Not-forking is a machine-readable file format and tool. It answers the question: What is the minimum difference between multiple source trees, and how can this difference be applied as versions change over time?
  • Not-forking avoids duplicating source code. When one project is within another project, and the projects are external to each other, there is often pressure to fork the inner project. Not-forking avoids that.
  • Not-forking helps address the problem of reproducibility. By giving much better control over the input source trees, it is more likely that the output binaries are the same each time.

Not-forking avoids project-level forking by largely automating change management in ways that version control systems such as Fossil, Git, or GitHub cannot. The full documentation goes into much more detail than this overview.

Not-forking was a pre-requisite to LumoSQL, but unlike LumoSQL is fully production-ready. I designed and tested Not-forking, and Claudio Calvelli did most of the coding as can be seen in the commit logs. Whatever becomes of this particular implementation, the design of Not-forking is provoking thought. Maintainers in several software distributions are looking at it, because after decades of amalgamating software in fragile ways, this appears to be a way of respecting both upstream and downstream.

This following diagram shows the simplest case of the problem Not-Forking solves. An external piece of software, here called Upstream, forms a part of a new project called Combined Project. Upstream is not a library provided on your system, because then you could simply link to libupstream. Instead, Upstream is source code that you copy into the Combined Project directory tree like this:


Some questions immediately arise:

  • Should you import Upstream into your source code management system? All source code should be under version management, but having a checkout of an external repository within your local repository feels wrong... and do we want to lose upstream project history?
  • If Upstream makes modifications, how can you pull those modifications into Combined Project safely?
  • If Combined Project has changed files in Upstream, how can you then merge the changes and any new changes made in Upstream?

The developer now has good reasons to separate Upstream project code from its repository and maintain it within the Combined Project tree, because in the short term it is just simpler. But that brings the very big problem of the Reluctant Project Fork. A Reluctant Project Fork, or "vendoring" as the Debian Project calls it, is where Combined Project's version of Upstream starts to drift from the original Upstream. Nobody wants to maintain code that is currently being maintained by its original authors, but it can become complicated to avoid that. Not-Forking makes this a much easier problem to solve.

Not-forking also addresses more complicated scenarios, such as when two unrelated projects are upstream of Combined Project:


In more detail, the problem of project forking includes these cases:

  • Tracking multiple upstreams, each with a different release schedule and version control system. Manual merging is difficult, but failing to merge or only occasionally merging will often result in a hard fork. LumoSQL tracks three upstreams that differ in all these ways
  • Tracking an upstream to which you wish to make changes that are not mergable. Without Not-Forking a manual merge is the only option even if there is only one upstream and even if the patch set is not complicated. An obvious case of this is replacing, deleting or creating whole files
  • Vendoring, where a package copies a library or module into its own tree, avoiding the versioning problems that arise when using system-provided libraries. This then becomes a standalone fork until the next copy is done, which often involves a manual porting task. Not-Forking can stop this problem arising at all
  • Vendoring with version control, for example some of the 132 forks of LibVNC on GitHub are for maintained, shipping products which are up to hundreds of commits behind the original. Seemingly they are manually synced with the original every year or two, but potentially Not-Forking could remove most of this manual work

The following diagram indicates how even more complex scenarios are managed with Not-Forking. Any of the version control systems could be swapped with any other, and production use of Not-Forking today handles up to 50 versions of three upstreams with ease.


Why Not Just Use Git/Fossil/Other VCS?

Git rebase cannot solve the Not-Forking problem space. Neither can Git submodules. Nor Fossil’s merge, nor the quilt approach to combining patches.

A VCS cannot address the Not-Forking class of problems because the decisions required are typically made by humans doing a port or reimplementation where multiple upstreams need to be combined. A patch stream can’t describe what needs to be done, so automating this requires a tangle of fragile one-off code. Not-Forking makes it possible to write a build system without these code tangles.

Examples of the sorts of actions Not-Forking can take:

  • check for new versions of all upstreams, doing comparisons of the human-readable release numbers/letters rather than repo checkins or tags, where human-readable version numbers vary widely in their construction
  • replace foo.c with bar.c in all cases (perhaps because we want to replace a library that has an identical API with a safer implementation)
  • apply this patch to main.c of Upstream 0, but only in the case where we are also pulling in upstream1.c, but not if we are also using upstream2.c
  • apply these non-patch changes to Upstream 0 main.c in the style of sed rather than patch, making it possible to merge trees that a VCS says are unmergable
  • build with upstream1.c version 2, and upstream3.c version 3, both of which are ported to upstream 0’s main.c version 5
  • track changes in all upstreams, which may use arbitrary release mechanisms (Git, tarball, Fossil, other)
  • cache all versions of all upstreams, so that a build system can step through a large matrix of versions of code quickly, perhaps for test/benchmark purposes.