This post is part 3/4 of a series about build systems. The next post and last post is I want a better build executor.

As someone who ends up getting the ping on "my build is weird" after it has gone through a round of "poke it with a stick", I would really appreciate the mechanisms for [correct dependency edges] rolling out sooner rather than later.

mathstuf

what does "action graph" mean?

In a previous post, I talked about various approaches in the design space of build systems. In this post, I want to zero in on one particular area: action graphs.

First, let me define "action graph". If you've ever used CMake, you may know that there are two steps involved: A "configure" step (cmake -B build-dir) and a build step (make or cmake --build). What I am interested here is what cmake -B generates, the Makefiles it has created. As the creator of ninja writes, this is a serialization of all build steps at a given moment in time, with the ability to regenerate the graph by rerunning the configure step.

This post explores that design space, with the goal of sketching a format that improves on the current state while also enabling incremental adoption. When I say "design space", I mean a serialization format where files are machine-generated by a configure step, and have few enough and restricted enough features that it's possible to make a fast build executor.

who uses an action graph?

Not all build systems serialize their action graph. bazel and buck2 run persistent servers that store it in memory and allow querying it, but never serialize it to disk. For large graphs, this requires a lot of memory; blaze has actually started serializing parts of its graph to reduce memory usage and startup time.

The nix evaluator doesn’t allow querying its graph at all; nix has a very strange model where it never rebuilds because each change to your source files is a new “input-addressed derivation” and therefore requires a reconfigure. This is the main reason it’s only used to package software, not as an “inner” build system, because that reconfigure can be very slow.

Tools that do serialize their graph include CMake, Meson, and the Chrome build system (GN).

Generally, serializing the graph comes in handy when:

  • You don’t have a persistent server to store it in memory. When you don’t have a server, serializing makes your startup times much faster, because you don’t have to rerun the configure step each time.
  • You don’t have a remote build cache. When you have a remote cache, the rules for loading that cache can be rather complicated because they involve network queries 1. When you have a local cache, loading it doesn’t require special support because it’s just opening a file.
  • You want to support querying, process spawning, and progress updates without rewriting the logic yourself for every OS (i.e. you don't want to write your own build executor).

design goals

In the last post I talked about 4 things one might want from a build system:

  1. a "real" language in the configuration step
  2. reflection (querying the build graph)
  3. file watching
  4. support for discovering incorrect dependency edges

For a serialization format, we have slightly different constraints.

  • We care about it being simple and unambiguous to load the graph from the file, so we get fast incremental rebuild speed and graph queries. In particular, we want to touch the filesystem as little as possible while loading.
  • We care about supporting "weird" dependency edges, like dynamic dependencies and the depfiles emitted by a compiler after the first run, so that we're able to support more kinds of builds.
  • And finally, we care about minimizing reconfigurations: we want to be able to express as many things as possible in the action graph so we don't have the pay the cost of rerunning the configure step. This tends to be at odds with fast graph loading; adding features at this level of the stack is very expensive!

Throughout this post, I'll dive into detail on how these 3 overarching goals apply to the serialization format, and how well various serializations achieve that goal.

existing serializations

The first one we'll look at, because it's the default for CMake, is make and Makefiles. Make is truly in the Unix spirit: easy to implement2, very hard to use correctly. Make is ambiguous, complicated, and makes it very easy to implicitly do a bunch of file system lookups. It supports running shell commands at the top-level, which makes even loading the graph very expensive. It does do pretty well on minimizing reconfigurations, since the language is quite flexible.

Ninja is the other generator supported by CMake. Ninja is explicitly intended to work on a serialized action graph; it's the only tool I'm aware of that is. It solves a lot of the problems of Make: it removes many of the ambiguities; it doesn't have any form of globbing; and generally it's a much simpler and smaller language. Unfortunately, Ninja's build file format still has some limitations.

First, it has no support for checksums. It's possible to work around that by using restat = true and having a wrapper script that doesn't overwrite files unless they've changed, but that's a lot of extra work and is annoying to make portable between operating systems.

Ninja files also have trouble expressing correct dependency edges. Let's look at a few examples, one by one. In each of these cases, we either have to reconfigure more often than we wish, or we have no way at all of expressing the dependency edge.

dependency edge issues with ninja

negative dependencies

See my previous post about negative dependencies. The short version is that build files need to specify not just the files they expect to exist, but also the files they expect not to exist. There's no way to express this in a ninja file, short of reconfiguring every time a directory that might contain a negative dependency is modified, which itself has a lot of downsides.

renamed files

Say that you have a C project with just a main.c. You rename it to project.c and ninja gives you an error that main.c no longer exists. Annoyed of editing ninja files by hand, you decide to write a generator3 :

# build.py
import ninja_syntax
import os
import sys
from os.path import basename, splitext

writer = ninja_syntax.Writer(sys.stdout)
writer.rule("python", "python $in > $out")
writer.build("build.ninja", "python", "build.py", implicit=["."])

writer.rule("cc", "cc $in -o $out")
for path in os.listdir('.'):
    base, ext = splitext(path)
    if ext == '.c':
        writer.build(base, "cc", path)

Note this that this registers an implicit dependency on the current directory. This should automatically detect that you renamed your file and rebuild for you.

$ ninja
[1/1] python build.py > build.ninja
[1/2] python build.py > build.ninja
[1/3] python build.py > build.ninja
[1/4] python build.py > build.ninja
[1/5] python build.py > build.ninja
[1/6] python build.py > build.ninja
...
[1/100] python build.py > build.ninja
ninja: error: manifest 'build.ninja' still dirty after 100 tries, perhaps system time is not set

Oh. Right. Generating build.ninja also modifies the current directory, which creates an infinite loop.

It's possible to work around this by putting your C file in a source directory:

# build.py
writer.build("build.ninja", "python", "build.py", implicit=["src"])
for path in os.listdir('src'):
    base, ext = splitext(path)
    if ext == '.c':
        writer.build('src/'+base, "cc", 'src/'+path)

$ tree
.
├── build.ninja
├── build.py
├── main.c
├── ninja_syntax.py
└── src
    └── main.c
$ ninja
[1/1] python build.py > build.ninja
[1/2] cc src/main.c -o src/main
$ mv src/{main,project}.c
$ ninja
[1/1] python build.py > build.ninja
[1/2] cc src/project.c -o src/project

There's still a problem here, though—did you notice it?

$ ls src
main  project  project.c

Our old main target is still lying around. Ninja actually has enough information recorded to fix this: ninja -t cleandead. But it's not run automatically.

The other problem is that this approach rebuilds far too often. In this case, we wanted to support renames, so in Ninja's model we need to depend on the whole directory. But that's not what we really depended on—we only care about .c files. I would like to see a action graph format that has an event-based system, where it says "this file was created, make any changes to the action graph necessary", and cuts the build short if the graph wasn't changed.

optional file dependencies

For flower, I want to go further and support deletions: source files and targets that are optional, that should not fail the build if they aren't present, but should cause a rebuild if they are created, modified, or deleted. Ninja has no way of expressing this.

environment variables

Ninja has no way to express “this node becomes dirty when an environment variable changes”. The closest you can get is hacks with set and the checksum wrapper/restat hack, but it’s a pain to express and it gets much worse if you want to depend on multiple variables.

designing a new action graph

At this point, we have a list of constraints for our file format:

  1. Negative dependencies
  2. File rename dependencies
  3. Optional file dependencies
  1. Optional checksums to reduce false positives
  2. Environment variable dependencies
  3. "all the features of ninja" (depfiles, monadic builds through dyndeps4, a generator statement, order-only dependencies)

Ideally, it would even be possible to mechanically translate existing .ninja files to this new format.

a first try

This sketches out a new format that could improve over Ninja files. It could look something like this:

  • A very very small clojure subset (just def, let, EDN, and function calls) for the text itself, no need to make loading the graph harder than necessary 5. If people really want an equivalent of include or subninja I suppose this could learn support for ns and require, but it would have much simpler rules than Clojure's classpath. It would not have support for looping constructs, nor most of clojure's standard library.
  • redo-inspired dependency edges: ifwritten (for changes in file attributes), ifchanged (for changes in the checksum), ifcreate (for optional dependencies), always; plus our new ifdeleted edge.
  • A dyndeps input function that can be used anywhere a file path can (e.g. in calls to ifwritten) so that the kind of edge does not depend on whether the path is known in advance or not.
  • Runtime functions that determine whether the configure step needs to be re-run based on file watch events6. Whether there is actually a file watcher or the build system just calculates a diff on its next invocation is an implementation detail; ideally, one that's easy to slot in and out.
  • “phony” targets would be replaced by a group statement. Groups are sets of targets. Groups cannot be used to avoid “input not found” errors; that niche is filled by ifcreated.

I’d call this language Magma, since it’s the simplest kind of set with closure.

Here's a sample action graph in Magma:

; In Magma, rules are simple functions.
; For each `action` that uses a rule, the function will be called with a list
; of attributes for that action.
; It returns a description of how to execute the build.
; Supported descriptions are:
; - `:command` (process spawning)
; - `:write` (writes data directly from memory to disk), and
; - `:read` (reads data directly from disk to memory), and
; - `:transform` (runs a clojure function on data in memory).
(defn cc [vars]
  {:command ["cc" (:inputs vars)
             "-MD" "-MF" (:depfile vars)
             "-o" (:out vars)]})

; `action`s define a build target (here, the file `main`).
; They must have a `:rule` that states how to execute the build,
; a set  of `:inputs` that must be built before this action is run,
; and a list of `:outputs` that will be created by the `:rule`.
; They may declare a dependency on `:env`ironment variables.
; Like in ninja, a `:depfile` may integrate with the compiler to lazily register
; a dependency on header files.
(action :outputs ["main"]
  :rule cc
  ; Unlike in ninja, all inputs must state under which conditions the input causes a rerun.
  ; `:ifwritten` means whenever the file metadata changes.
  :inputs {:ifwritten ["main.c", "helper.c"]}
  ; Like in ninja, `:implicit` is exactly the same as `:inputs`,
  ; but allows the `:rule` to distinguish which files should be passed to the command.
  :implicit {:ifwritten ["helper.h"]}
  :env ["LIBRARY_PATH", "C_INCLUDE_PATH"]
  :depfile "main.c.d")

; Actions that don't create a file on disk are allowed.
; This is similar to a "Phony" target in Make, except that you can choose to not always rerun it.
; Since there's no output, we manually specify the name of the action so other actions can depend on it.
(action :name "docker-image"
  :outputs []
  ; Rules don't have to be defined separately from actions.
  :rule (fn [_vars] {:command ["docker" "build" "."]})
  ; We choose to trust docker's own caching here.
  ; We could instead use `:implicit {:ifwritten [...]}`, but we don't.
  :implicit :always)

; A function that filters out paths ending with a trailing slash.
(defn files [paths]
  (filter #(not (str/ends-with? % "/")) paths))

; Just a normal clojure variable. We'll use this as an input later.
(def tarfile {:ifwritten ["example.tar"]})

; This rule lists all files (excluding directories) inside of a tarfile.
(defn list-tar-files [vars]
  ; `:rule` can be a list to run multiple rules in a row within the same action.
  [{:command ["tar" "-tf" (:inputs vars)]
    ; This is like a shell redirect, but saves the output to a string in memory instead of to a file.
    ; The string will be passed to the next rule in the list.
    :stdout :string}
   ; This filters for files, then passes the string to the next rule.
   {:transformer (fn [paths] (str/join "\n" (files (str/split #"\n" paths))))}
   ; Finally, write the transformed data out to disk.
   {:write (:outputs vars)}])

; Generate a list of all files that will be created by extracting the tarfile.
(action :outputs ["example.tar.dd"]
  :rule list-tar-files
  :inputs tarfile)

; `dynout` returns a future which `action` will resolve.
(def tar-outputs
  (dynout
    ; Recalculate the dependencies whenever our .dd file changes.
    ; Note that unlike `ifwritten`, `ifchanged` calculates a checksum, it doesn't use file metadata.
    :inputs {:ifchanged ["example.tar.dd"]}
    :rule (fn [vars] [{:read (:inputs vars)}
                      ; Our future resolves to a list of file paths.
                      {:transformer #(str/split % #"\n")}])))

; Dynamically add the outputs from the tarfile to the action graph.
; This schedules the action to run only after the `dynout` future is resolved.
(action :outputs tar-outputs
  :inputs tarfile
  :rule (fn [vars] {:command ["tar" "-xf" (:inputs vars)]}))

; Group together many different actions.
; This can be called from the command line as if it were its own action.
(group "all" (concat ["main" docker-image] tar-outputs))

; Specify that the configure script shold rerun whenever a `.c` file is created or deleted.
(defn should-rerun [event]
  (and (ends-with? (:path event) ".c")
       (not= :modified (:kind event))))

(action :outputs ["build.magma"]
  :rule {:command ["python" "configure.py"]}
  ; Indicate that these outputs shouldn't be deleted by `clean` rules.
  :generator true
  :env ["CFLAGS", "LDFLAGS"]
  ; Register a function that will run on each change to the current directory
  ; and instruct whether or not the input should cause a rebuild.
  :inputs {:watch {"." should-rerun}})

Note some things about Magma:

  • Command spawning is specified as an array 7. No more dependency on shell quoting rules. If people want shell scripts they can put that in their configure script.
  • Redirecting stdout no longer requires bash syntax, it's supported natively with the :stdout parameter of :rule.
  • Build parameters can be referred to in rules through the vars argument.
  • dynout is a thunk; it only registers an intent to add edges in the future, it does not eagerly require example.tar.dd to exist.
  • Our watch input edge is generalized and can apply to any rule, not just to the configure step. It executes when a file is modified (or if the tool doesn’t support file watching, on each file in the calculated diff in the next tool invocation).
  • Our watch edge provides the file event type, but not the file contents. This allows ronin to automatically map true results to one of the three edge kinds: :ifwritten, :ifcreated, :ifdeleted. :always and :ifchanged are not available through this API.
  • We naturally distinguish between “phony targets” and files because the former are groups and the latter are actions. No more accidentally failing to build if an all file is created. 8
  • We naturally distinguish between “groups of targets” and “commands that always need to be rerun”; the latter just uses :inputs :always.
  • Data can be transformed in memory using clojure functions without needing a separate process invocation. No more need to use sed in your build system.

"did you just reinvent starlark?"

Kinda. Magma itself has a lot in common with starlark: it's deterministic, hermetic, immutable, and can be evaluated in parallel. But the APIs are very different, because Magma files are a build target, not a build input. In particular they only describe dependencies between files and process executions; they cannot be used as libraries and do not have support for selecting between multiple configurations.

The main difference between the languages themselves is that clojure has :keywords (equivalent to sympy symbolic variables) and python doesn't. Some of these could be rewritten to keyword arguments, and others could be rewritten to structs, or string keys for a hashmap, or enums; but I'm not sure how much benefit there is to literally using Starlark when these files are being generated by a configure step in any case. Probably it's possible to make a 1-1 mapping between the two in any case.

runners

Buck2 has support for RunInfo metadata that describes how to execute a built artifact. I think this is really interesting; cargo run --bin xyz -- args is a much nicer interface than make ARGS='args' xyz, partly because of shell quoting and word splitting issues, and partly just because it's more discoverable.

I don't have a clean idea for how to fit this into a serialization layer. "Don't put it there and use a Justfile instead" works, but makes it hard to do things like allow the build graph to say that an artifact needs LD_LIBRARY_PATH set or something like that, you end up duplicating the info in both files. Perhaps one option could be to attach a :run key/value pair to actions.

"are you just piling a bunch of features on top of ninja?"

Well, yes and no. Yes, in that this has basically all the features of ninja and then some. But no, because the rules here are all carefully constrained to avoid needing to do expensive file I/O to load the build graph. The most expensive new feature is watch, and it's intended to avoid an even more expensive step (rerunning the configuration step). It's also limited to changed files; it can't do arbitrary globbing on the contents of the directory the way that Make pattern rules can.

Note that this also removes some features in ninja: shell commands are gone, process spawning is much less ambiguous, dyndep files are no longer parsed automatically. And because this embeds a clojure interpreter, many things that were hard-coded in ninja can instead be library functions: rule, response files, msvc_deps_prefix, in_newline.

next steps

In this post, we have learned some downsides of Make and Ninja's build file formats, sketched out how they could possibly be fixed, and designed a language called Magma that has those characteristics. In the next post, I'll describe the features and design of a tool that evaluates and queries this language.

  1. see e.g. this description of how it works in buck2 ↩

  2. at least a basic version—although several of the features of GNU Make get rather complicated. ↩

  3. ninja_syntax.py is https://github.com/ninja-build/ninja/blob/231db65ccf5427b16ff85b3a390a663f3c8a479f/misc/ninja_syntax.py. ↩

  4. technically these aren't true monadic builds because they're constrained a lot more than e.g. Shake rules, they can't fabricate new rules from whole cloth. but they still allow you to add more outputs to the graph at runtime. ↩

  5. This goes all the way around the configuration complexity clock and skips the "DSL" phase to simply give you a real language. ↩

  6. This is totally based and not at all a terrible idea. ↩

  7. This has a whole bunch of problems on Windows, where arguments are passed as a single string instead of an array, and each command has to reimplement its own parsing. But it will work “most” of the time, and at least avoids having to deal with Powershell or CMD quoting. ↩

  8. To make it possible to distinguish the two on the command line, :all could unambiguously refer to the group, like in Bazel. ↩