Software Design by Example 18: Package Manager

Posted

Inspired by the Comprehensive TeX Archive Network, most languages now have an online archive from which developers can download packages. Each package typically has a name and one or more version(s); each version may have a list of dependencies, and the package may specify a version or range of acceptable versions for each dependency.

Finding a consistent set of versions to install is an intrinsically hard problem. Chapter 18 of Software Design by Example therefore explores how to search for something legal. Almost every real package manager uses some sort of SMT solver to do this, but I decided not to use one in this chapter because their documentation is mostly impenetrable. This tutorial on Z3 isn’t bad, for example, but as soon as you need to go deeper, the full documentation seems designed to keep working programmers at bay.

I think that’s a shame: solvers are tremendously powerful tools, and deserve to be much more widely used. The working draft of the Python version of this book re-solves the problem from this chapter using Z3, and goes on to show how it can be used to generate test data as well using an example borrowed from Andreas Zeller’s excellent lecture on academic prototyping. If you’d like to have a look and let me know if it works, please reach out.

Allowable versions
Figure 18.1: Finding allowable combinations of package versions.

Terms defined: backward-compatible, combinatorial explosion, heuristic, manifest, patch, prune, SAT solver, scoring function, seed, semantic versioning.