A Build Manager

• Build managers track dependencies between files and update files that are stale.
• Every build rule has a target, some dependencies, and a recipe for updating the target.
• Build rules form a directed graph which must not contain cycles.
• Pattern rules describe the dependencies and recipes for sets of similar files.
• Pattern rules can use automatic variables to specify targets and dependencies in recipes.

Terms defined: affordance, build manager, build recipe, build rule, stale (in build), target (in build), circular dependency, compiled language, cycle, directed acyclic graph, dependency (in build), dry run, link (a program), phony target, stable sort, Template Method pattern, topological order

Suppose that plot.py produces result.svg from collated.csv, that collated.csv is produced from samples.csv and controls.csv by analyze.py, and that samples.csv depends on normalize.py and raw.csv. If raw.csv changes we want to re-run all three programs; if controls.csv changes, on the other hand, we only need to re-run the analysis and plotting programs. If we try to manage this ourselves we will inevitably make mistakes. Instead, we should use a build manager to keep track of which files depend on which and what actions to take to create or update files. This chapter shows how a simple build manager works; along the way, it introduces some algorithms for working with graphs.

Concepts

The first build manager, Make, was written by a student intern at Bell Labs in the 1970s. Many others now exist (such as SCons and Snakemake), but they all perform the same basic operations. If a target is stale with respect to any of its dependencies, the build manager runs a recipe to refresh it.

The build manager runs recipes in an order that respects dependencies, and it only runs each recipe once (if at all). In order for this to be possible, targets and dependencies must form a directed acyclic graph, i.e., there cannot be a cycle of links leading from a node back to itself. The build manager constructs a topological ordering of that graph, i.e., arranges nodes so that each one comes after everything it depends on and then builds what it needs to in that order (Figure 19.1).

Initial Design

Our first step is to decide how we are going to represent build rules. We could invent a special-purpose syntax to fit the problem, but as we said in Chapter 5, the world has enough data formats. Instead, we will represent our recipes as JSON. For example, this file describes two targets A and B and states that the former depends on the latter:

{
  "A": {"depends": ["B"], "rule": "build A"},
  "B": {"depends": [], "rule": "build B"}
}

As in Chapter 10, we will use successive refinement to create our first build manager. Our BuildBase class takes a configuration file as a constructor argument, loads it, creates a topological ordering, and then refreshes each target in order. For now, “refreshing” means “prints the update rule”; we will come back and make this more sophisticated later.

class BuildBase:
    def build(self, config_file):
        config = self._configure(config_file)
        ordered = self._topo_sort(config)
        for node in ordered:
            self._refresh(config, node)

    def _refresh(self, config, node):
        assert node in config, f"Unknown node {node}"
        print(config[node]["rule"])

To load a configuration file, we read in the JSON, build a set of known targets, and then verify each rule using a helper method called _check:

    def _configure(self, config_file):
        with open(config_file, "r") as reader:
            config = json.load(reader)
            known = set(config.keys())
            return {
                n: self._check(n, d, known)
                for n, d in config.items()
            }

To check a rule, we make sure the dictionary that represents it has the required keys and that we have a rule for every dependency it mentions. We also transform the rule’s structure a bit to simplify later processing (Figure 19.2):

    def _check(self, name, details, known):
        assert "rule" in details, f"Missing rule for {name}"
        assert "depends" in details, f"Missing depends for {name}"
        depends = set(details["depends"])
        assert depends.issubset(known), \
            f"Unknown depends for {name}"
        return {"rule": details["rule"], "depends": depends}

Topological Sorting

The next step is to figure out a safe order in which to build things. Figure 19.3 shows how our algorithm works:

1. We find all the nodes in the dependency graph that don’t have any outstanding dependencies.

2. We append those to the result and then remove them from the dependencies of all the other nodes in the graph.

3. If anything is still in the graph, we go back to the first step.

4. If at any point the graph isn’t empty but nothing is available, we have found a circular dependency, so we report the problem and fail.

The code that implements this algorithm is:

    def _topo_sort(self, config):
        graph = {n: config[n]["depends"] for n in config}
        result = []
        while graph:
            available = {n for n in graph if not graph[n]}
            assert available, f"Circular graph {graph.keys()}"
            result.extend(available)
            graph = {
                n: graph[n] - available
                for n in graph
                if n not in available
            }
        return result

With all of this in place, we can run our first test:

{
  "A": {"depends": ["B"], "rule": "build A"},
  "B": {"depends": [], "rule": "build B"}
}

build B
build A

A Better Design

Our implementation works, but we can do better:

1. The configuration might not come directly from a JSON file—for example, it might be embedded in a larger file or generated by another program—so we should modify the constructor to take a configuration as input.

2. Printing actions to the screen isn’t very useful, so we should collect them and return an ordered list of the commands for the build manager.

3. assert isn’t a friendly way to handle user errors; we should raise ValueError (or a custom exception of our own) to indicate a problem.

4. Our topological sort isn’t stable, i.e., there’s no way to predict the order in which two “equal” nodes will be added to the ordering. We will explore the reason for this in the exercises, but for now, we should sort node names when appending to the result list so that our tests can know what to check for.

5. We might want to add other keys to rules, so we should put that check in a separate method that we can override.

The top level of our better build manager looks like this:

class BuildBetter:
    def build(self, config):
        config = self._configure(config)
        ordered = self._topo_sort(config)
        actions = []
        for node in ordered:
            self._refresh(config, node, actions)
        return actions

    def _refresh(self, config, node, actions):
        assert node in config, f"Unknown node {node}"
        actions.append(config[node]["rule"])

    def _must(self, condition, message):
        if not condition:
            raise ValueError(message)

The revised configuration code is:

    def _configure(self, config):
        known = set(config.keys())
        return {n: self._check(n, d, known)
                for n, d in config.items()}

    def _check(self, name, details, known):
        self._check_keys(name, details)
        depends = set(details["depends"])
        self._must(
            depends.issubset(known), f"Unknown depends for {name}"
        )
        result = details.copy()
        result["depends"] = depends
        return result

    def _check_keys(self, name, details):
        self._must("rule" in details, f"Missing rule for {name}")
        self._must(
            "depends" in details, f"Missing depends for {name}"
        )

and the updated topological sorting method is

    def _topo_sort(self, config):
        graph = {n: config[n]["depends"] for n in config}
        result = []
        while graph:
            available = {n for n in graph if not graph[n]}
            self._must(
                available,
                f"Circular graph {list(graph.keys())}",
            )
            result.extend(sorted(available))
            graph = {
                n: graph[n] - available
                for n in graph
                if n not in available
            }
        return result

We can now test that the code detects circularities in the dependency graph:

def test_circular():
    action_A = "build A"
    action_B = "build B"
    config = {
        "A": {"depends": ["B"], "rule": action_A},
        "B": {"depends": ["A"], "rule": action_B},
    }
    try:
        Builder().build(config)
        assert False, "should have had exception"
    except ValueError:
        pass

and that it builds what it’s supposed to:

def test_no_dep():
    action_A = "build A"
    action_B = "build B"
    config = {
        "A": {"depends": [], "rule": action_A},
        "B": {"depends": [], "rule": action_B},
    }
    assert Builder().build(config) == [action_A, action_B]

We can also extend it. For example, suppose we only want to update targets that are older than their dependencies (which is, after all, the whole point of a build manager). If the targets are actual files we can check their timestamps, but for testing purposes we would like to specify pretended times in the configuration:

def test_diamond_dep():
    action_A = "build A"
    action_B = "build B"
    action_C = "build C"
    action_D = "build D"
    config = {
        "A": {"depends": ["B", "C"], "rule": action_A, "time": 0},
        "B": {"depends": ["D"], "rule": action_B, "time": 0},
        "C": {"depends": ["D"], "rule": action_C, "time": 1},
        "D": {"depends": [], "rule": action_D, "time": 1},
    }
    assert Builder().build(config) == [action_B, action_A]

Starting from the class we have written so far, we need to override three methods:

class BuildTime(BuildBetter):
    def _check_keys(self, name, details):
        super()._check_keys(name, details)
        self._must("time" in details, f"No time for {name}")

    def _refresh(self, config, node, actions):
        assert node in config, f"Unknown node {node}"
        if self._needs_update(config, node):
            actions.append(config[node]["rule"])

    def _needs_update(self, config, node):
        return any(
            config[node]["time"] < config[d]["time"]
            for d in config[node]["depends"]
        )

Summary

Figure 19.4 summarizes the ideas introduced in this chapter. Note that the small bubble labelled “graph algorithm” could be expanded to a shelf full of books.

Exercises

Stable Sorting

Recent versions of Python guarantee that the entries in a dict preserve the order in which they were added, but do not make any such guarantee for sets. Explain why this makes it hard to test things that use sets.

Checking Schema

Rewrite the configuration validator to use JSON Schema via the associated Python module.

Handling Failure

1. Modify the build manager so that a configuration file can specify whether its rule should succeed or fail. (This isn’t particularly useful in real life, but it helps with testing.)

2. Modify it so that if a rule fails, other buildable targets are still built (but anything that depends directly or indirectly on the target whose rule failed is not built).

3. Write tests to check that this change works correctly.

Merging Files

1. Modify the build manager so that it can read multiple build files and execute their combined rules.

2. What does your solution do if two or more files specify rules for the same target?

Using Hashes

1. Write a program called build_init.py that calculates a hash for every file mentioned in the build configuration and stores the hash along with the file’s name in build_hash.json.

2. Modify the build manager to compare the current hashes of files with those stored in build_hash.json to determine what is out of date, and to update build_hash.json each time it runs.

Dry Run

A dry run of a build shows the rules that would be executed but doesn’t actually execute them. Modify the build system in this chapter so that it can do dry runs.

Phony Targets

A phony target is one that doesn’t correspond to a file. Developers often put phony targets in build files to give themselves an easy way to re-run tests, check code style, and so on. Modify the build system in this target so that users can mark targets as phony.

Multiple Build Files

1. Modify the tool built in this chapter so that one build file can import definitions and dependencies from another.

2. How does your system prevent circular dependencies?