What is a build system, anyway?

Summary

Andrew Nesbitt recently wrote a post titled What is a Package Manager? This post attempts to do the same for build systems. big picture At a high level, build systems are tools or libraries that provide a way to define and execute a series of transformations from input data to output data that are memoized by caching them in an object store. Transformations are called steps or rules and define how to execute a task that generates zero or more outputs from zero or more inputs. A rule is usually the unit of caching; i.e. the cache points are the outputs of a rule, and cache invalidations must happen on the inputs of a rule. Rules can have dependencies on previous outputs, forming a directed graph called a dependency graph. Dependencies that form a cyclic graph are called circular dependencies and are usually banned. Outputs that are only used by other rules, but not “interesting” to the end-user, are called intermediate outputs. A output is outdated, dirty, or stale if one of its dependencies is modified, or, transitively, if one of its dependencies is outdated. Stale outputs invalidate the cache and require the outputs to be rebuilt. An output that is cached and not dirty is up-to-date. Rules are outdated if any of their outputs are outdated. If a rule has no outputs, it is always outdated. Each invocation of the build tool is called a build. A full build or clean build occurs when the cache is empty and all transformations are executed as a batch job. A cache is full if all its rules are up-to-date. An incremental build occurs when the cache is partially full but some outputs are outdated and need to be rebuilt. Deleting the cache is called cleaning. A build is correct or sound if all possible incremental builds have the same result as a full build. A build is minimal (occasionally optimal) if rules are rerun at most once per build, and only run if necessary for soundness (Build Systems à la Carte, Pluto). In order for a build to be sound, all possible cache invalid...