Beyond Package Version Policies

When I read the announcement of the latest GHC release candidate, I did not feel excitement but rather annoyance. The reason is that now I have to go and check all my packages' dependency specifications and see if they require a version bump. I was not the only one. In the following I sketch an approach that I think could take out most of the pain we currently experience in Hackage ecosystem.

The Problem

The reason for this annoyance is the rather strict Hackage package versioning policy (PVP). The PVP specifies the format of the version number of a Hackage package as a sequence of four integers separated by dots:

majorA.majorB.minor.patchlevel

The top two digits denote the major version number, and must be incremented if a potentially breaking change is introduced in a new package release. The minor number must be incremented if new functionality was added, but the package is otherwise still compatible with the previous version. Finally, a patchlevel increment is necessary if the API is unchanged and only bugfixes or non-functional changes (e.g., documentation) were made. This sounds fairly reasonable and is basically the same as what is used for shared libraries in the C world.

When specifying dependencies on other packages, authors are strongly encouraged to specify upper bounds on the major version. This is intended to avoid breaking the package if a new major version of the dependency is released (Cabal-install always tries to use the latest possible version of a dependency). If the package also works with a newer version of the dependency, then the author is expected to release a new version of his/her library with an increased upper bound for the dependency version.

 In Haskell, unfortunately, this system doesn't work too well for a number of reasons:

1. Say, my package P depends on package A-1.0 and I now want to test if it works with the newly released version A-1.1. My package also depends on package B-0.5 which in turn also depends on A-1.0. GHC currently cannot link two versions of the same package into the same executable, so we must pick one version that works with both -- in this case that's A-1.0. D'oh!
   I now have two options: (a) wait for the author of package B to test it against A-1.1, or (b) do it myself. If I choose option (b) I also have to send my patch to the author of B, wait for him/her to upload the new version to Hackage and only then can I upload my new version to Hackage. The problem is multiplied by the number of (transitive) dependencies of my package and the number of different authors of these packages. This process takes time (usually months) and the fast release rate of GHC (or many other Haskell packages, for that matter) doesn't make it any easier.
2. Packages get major-version upgrades rather frequently. One reason is that many Haskell libraries are still in flux. Another is that if a package adds a new instance, a major version upgrade is required. We can protect against new functions/types being added to a package because we can use explicit import lists. New instances are imported automatically, and there's no way to hide them when importing a module.
3. A package version is a very crude and conservative approximation that a dependent package might break.

Generally, I think it's a good thing that Haskell packages are updated frequently and improved upon. The problem is that the current package infrastructure and tools don't work well with it. The PVP is too conservative.

A Better Approach

The key notion is to track dependencies at the level of individual functions, types, etc. rather than at the level of whole packages.

When a package P depends on another package A it usually doesn't depend on the whole package. Most of the time P just depends on a few functions and types. If some other part of A is changed, that shouldn't affect P. We have so much static information available to us, it's a shame we're not taking advantage of it. Consider the following system:

1. When I compile my code, the compiler knows exactly which functions, types, etc. my program uses and from which packages they come from. The compiler (or some other tool) writes this information to a file (preferably in a human-readable format). Let's call this file: dependencies.manifest
2. Additionally, the compiler/tool also generates a list of all the functions, types, etc. defined by code in my package. Let's call that file: exports.manifest. I believe GHC's ABI versioning already does something very similar to this, although it just reduces this all to a hash.

The first use of this information is to decide whether a package is compatible with an expected dependency. So, if my package's "dependency.manifest" contained (for example)

type System.FilePath.Posix.FilePath = Data.String.String
System.FilePath.Posix.takeBaseName :: System.FilePath.Posix.FilePath -> System.FilePath.Posix.FilePath

then it is compatible with any future (or past) version of the filepath package that preserves this API and that defines FilePath as a type synonym for Strings.

Of course, this only checks for API name and type compatibility, not actual semantic compatibility. This requires some hints from the package authors, as described below. Together with annotations from the package author about semantic changes, the only information we need to check if a newer package is a compatible dependency are the versions the original versions of the dependencies used and the manifest of the new package.

For example, let's say version 0.1 of my package looks as follows:

module Gravity where
bigG :: Double -- N * (m / kg)^2
bigG = 6.674e-11
force :: Double -> Double -> Double -> Double -- N
force m1 m2 r = (bigG * m1 * m2) / (r * r)

Its manifest will look something like this:

Gravity.bigG :: Double, 0.1
Gravity.force :: Double -> Double -> Double -> Double, 0.1

The version of each item is the version of the package at which it was introduced or changed its semantics.

Now I add a new function in version 0.1.1:

standardGravity :: Double -- m/s^2
standardGravity = 9.80665

The manifest for version 0.1.1 now will be

Gravity.bigG :: Double, 0.1
Gravity.force :: Double -> Double -> Double -> Double, 0.1
Gravity.standardGravity :: Double, 0.1.1

Now, let's say I want to improve the accuracy of bigG in version 0.2:

bigG = 6.67384

Since bigG was changed and force depended upon it, by default the new manifest would be:

Gravity.bigG :: Double, 0.2
Gravity.force :: Double -> Double -> Double -> Double, 0.2
Gravity.standardGravity :: Double, 0.1.1

However, one could argue that this is a backwards compatible change, hence the manifest would be adjusted by the author (with the help of tools) to:

Gravity.bigG :: Double, 0.1
Gravity.force :: Double -> Double -> Double -> Double, 0.1
Gravity.standardGravity :: Double, 0.1.1

That is the same manifest as version 0.1.1, thus 0.2 is 100% compatible with all users of 0.1.1 (according to the package author), and even all users of 0.1 because no functionality has been removed.

Even if manifests didn't include the version number (for now) I believe just the API information is precise enough for most cases. It will still be necessary to constrain the allowed range of package dependencies, but that should be the rare exception (e.g., a performance regressions) rather than the current state where dependencies need to be adjusted every few months.

Upgrade Automation

This mechanism alone only helps with being less conservative when checking whether a package can work with an updated dependency. The other issue is that Haskell package APIs are often moving quickly and thus breaking code is unavoidable. If a package only has a few dependents this may not be such a big deal, but it becomes a problem for widely used packages. For example, during the discussions for including the vector package into the Haskell Platform some reviewers asked for functions to be moved from one module into the other. Roman, vector's maintainer, argued against this noting it would break many dependencies -- a valid concern. Even if this was only a small issue, fear of breaking dependent packages can slow down improvements in package APIs.

The Go programming language project has a tool called "gofix", which can automatically rewrite code for simple API changes and generates warnings for places that require human attention. Haskell has so much static information, that such a tool is quite feasible (e.g., HaRe can already do most of the important bits).

So, I imagine that a newly-released package specifies up to two additional pieces of information:

• An annotated manifest indicating where semantic changes were made while retaining the same API. This can be seen as bumping the version of a single function/type, rather than of the whole API. To avoid the impact of human error this, too, should be tool supported. For example, if we compute an ABI hash for each function, we can detect which functions were modified. The package author can then decide if that was just a refactoring or an actual semantic change.
  (This has to be done with the help of tools. Imagine we refactor a frequently used internal utility function. Then all functions that use it would potentially have changed semantics. However, as soon that function is marked as backwards compatible, so will all its users. So it's important that a tool asks the package author for compatibility by starting with the leaf nodes.)
• Optionally, the author may specify an upgrade recipe to be used by an automated tool or even just a user of the library. This could include simple instructions like renaming of functions (which includes items moved between modules or even packages), or more complicated things like a definition of a removed function in terms of newly-added functions. For more complicated changes a textual description of the changes can give higher-level instructions for how to manually upgrade. Since this should be human-readable anyway, we may as well specify this upgrade recipe in a (formally defined) format that looks like a Changelog file.

Summary

The PVP doesn't work well because it is too conservative and too coarse-grained. Haskell contains enough static information to accurately track dependencies at the level of functions and types. We should take advantage of this information.

The ideas presented above certainly require refinement, but even if we have to be conservative in a few places (e.g., potentially conflicting instance imports), I think it will still be much less painful than the current system.

Comments and constructive critiques welcome!