Transactional Versioning

Software versioning and managing software dependencies is hard. Unfortunately it is also an unavoidable problem. Rarely do we build software in isolation from the rest of the world. Hoping to stand on the shoulders rather than the toes of giants, we build software which depends upon other software. We make use of libraries; we make assumptions about platforms and run times.

In order to develop, build and deploy software in a consistent and repeatable manner these dependencies on artifacts we did not write are things which we must manage. Otherwise we fall into unrepeatable builds and inconsistent deployments where the behavior of software varies from machine to machine and debugging is hard.

Traditionally we have tracked dependencies by assigning a tuple (name, version) to every artifact. By writing out all the (name, version) tuples which we used when developing some software, we can tell users what it is that we expect them to have and imply how to provision their systems.

And that mostly works. We deploy the artifact along with its dependency list. When we want to run the artifact, we have to resolve the dependencies (which themselves provide dependency lists and soforth) using tool such as Maven or any other package manager. These package managers can pull down one dependency, resolve its dependencies and recursively pull down dependencies until all requirements are satisfied and the artifacts are ready to go.

Unfortunately this model has a clear failing: what happens when you have a conflict between dependencies? That is, what happens when dependency a requires (c, 3) that is artifact c at version 3, and dependency b requires (c, 4)?

Most programming systems conflate the idea of a name with the idea of an identity, especially when it comes to library code. Multiple entities with the same name cannot be “loaded” at once and so a choice between (c, 3) and (c, 4) must be made. This is called a version conflict.

Who wins?

We want to take (c, 3) and (c, 4), discover that (c, 4) is “fully featured” with respect to (c, 3) so we can just use (c, 4).

This means we need to pick on some notion of compatibility of artifacts.

But how to do this? “Versions” come in a huge number of formats, so there isn’t an obvious way to compare them, and many formats encode different information. Some artifacts use a “build number”, being literally the count of builds done to date. Other artifacts use the git hash from which the artifact was built. These two just tell the developers what was built and how to rebuild it. The Linux Kernel and other projects use “numbers” with several decimal places where each one is a counter with the leftmost being the most significant and the each one somehow mapping to the feature set and / or patch number of the program.

No version management tool knows about all of these schemes, or can - given two version identifiers - generally decide if one can be exchanged for the other. Although perhaps one could build an extensible build system where artifacts can contain programs to compare themselves.

The Semantic Versioning scheme, better known as semver, defines a seemingly simple version scheme which clearly defines the relationship between artifact versions. Semver versions are tripples (major, minor, patch). Patch changes aren’t supposed to add anything, although they may, but they cannot remove any user visible part of the artifact. This means that a build (major, minor, patch) should interchange with any other build (major, minor, patch'), although a higher patch number is expected to imply improvements and bugfixes. Minor versions are intended to denote feature checkpoints and user visible additions. So the (1 2 0) is supposed to superset the (1 1 0) release in terms of features visible to users, and this version sorts as greater than any patch number on an earlier minor version. Finally the major version is used to denote significant changes to the public API offered by an artifact. Deletions of user visible symbols can only occur here.

These properties ensure that, if respected by the developers, a user may safely and blindly upgrade through arbitrarily many patches and minor versions since nothing on which they rely may be removed. Upgrading across major versions however may require arbitrarily much work if the API changed or some depended on symbol was removed. This is perfect for resolving version conflicts. Given two versions in conflict, the dependency resolution system simply chooses the higher version one so long as it is in the same major version family. If the two are not in the same major version family, then we cannot automatically resolve the dependencies and the user or developer must take action.

However we want to minimize the set of circumstances under which the users must call upon the developers and under which the developers must take action. Consider a major release which adds a whole new API but removes nothing. This is a legal version under the semver scheme. Unfortunately as a major version bump denotes that deletions may have occurred, our dependency resolution engine can do nothing even though the new version commutes with the old one.

We can deal with this particular case by modifying the semver scheme, consider the following “reidver” specification.

Note that a “rename” encompasses both the meaning of a symbol changed and the literal name of the symbol changed (a deletion and an addition).

But even this has its failures, since if a symbol which is not used in any dependency is deleted, that is still a breaking change which we cannot automatically upgrade across.

Superior as it is, even something like this is ultimately futile. We as programmers are awful about tracking what constitutes a breaking change compared to what constitutes an invisible bugfix. “releases” are often large, often incorperating multiple changes. Unless a strict discipline of single changes and small commits is enforced reviewing the change history may be difficult. Forgetting that you refactored a single symbol or changed a signature is an easy mistake to make, and one which is absolutely fatal to the semantics of something like semver or reidver.

If we back up and consider this from a set theoretic standpoint, really we can freely upgrade across versions so long as the reached subset of the used artifact(s) hasn’t changed. That is, for every artifact upon which we depend we can consider the subset of the public API defined in that artifact which are reached by any other artifact. So long as none of these sets experience negative changes between versions, we can feely upgrade. If a deletion occurs, then in the general case there is nothing we can do and the programmer(s) must take action. Really what we want is not even this “reidver” thing, but rather some set theoretic or transactional view of the contents of an artifact from which we can make exactly this decision about whether two artifacts do commute.

Language support for something like this is essential, as programmers simply canot be trusted to maintain the requisite semantics. The version system can never be allowed to lie. Otherwise all hell breaks loose and we’re back in our current tarpit with with dependencies which cannot be updated or worse nonrepeatable builds.

Given that, this could actually work. It solves all the above issues with resolving replacements, and also makes forking easier since it exposes to the dependency resolution engine that one artifact is derived from another. The version comparision system, representing what is classically the whole change history of the artifact clearly encodes that the fork is a superset of the base version. It just requires a very different view of verisoning than that currently in practice and language participation in the versioning scheme. Something like a Datomic code loading server & VM.

Disclaimer: This is not a novel idea. I rediscovered this with some hints from Chas Emeric who got there first. I just wrote the essay.