[utils] New script `check_ninja_deps.py`

[simon_tatham]

Summary

This can be run after a ninja-based build, and analyzes the ninja
build files and dependency database to spot any missing dependencies
in the build scripts.

I wrote it in the course of investigating D82659, and it seems likely
to be useful again.

[thakis]

llvm/utils/check_ninja_deps.py

179

This also means you have to make sure that latter deps for a file overwrite earlier deps for a file, iirc (the old entry might be stale)

[simon_tatham]

llvm/utils/check_ninja_deps.py

179

They do, as far as I can tell: if I change the includes in a source file and re-run ninja, then the result of ninja -t deps includes a stanza showing the new dependencies for the generated object, and no stanza for the old dependencies.

From reading the source comments, it looks as if previous versions of the dependencies for a file might sometimes still exist in the .ninja_deps log on disk, but they're not printed by the deps tool I'm calling here.

llvm/utils/check_ninja_deps.py

+#!/usr/bin/env python3
+#
+# ======- check-ninja-deps - build debugging script ----*- python -*--========#
+#
+# Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
+# See https://llvm.org/LICENSE.txt for license information.
+# SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
+#
+# ==------------------------------------------------------------------------==#
+
+"""Script to find missing formal dependencies in a build.ninja file.
+
+Suppose you have a header file that's autogenerated by (for example) Tablegen.
+If a C++ compilation step needs to include that header, then it must be
+executed after the Tablegen build step that generates the header. So the
+dependency graph in build.ninja should have the Tablegen build step as an
+ancestor of the C++ one. If it does not, then there's a latent build-failure
+bug, because depending on the order that ninja chooses to schedule its build
+steps, the C++ build step could run first, and fail because the header it needs
+does not exist yet.
+
+But because that kind of bug can easily be latent or intermittent, you might
+not notice, if your local test build happens to succeed. What you'd like is a
+way to detect problems of this kind reliably, even if they _didn't_ cause a
+failure on your first test.
+
+This script tries to do that. It's specific to the 'ninja' build tool, because
+ninja has useful auxiliary output modes that produce the necessary data:
+
+ - 'ninja -t graph' emits the full DAG of formal dependencies derived from
+   build.ninja (in Graphviz format)
+
+ - 'ninja -t deps' dumps the database of dependencies discovered at build time
+   by finding out which headers each source file actually included
+
+By cross-checking these two sources of data against each other, you can find
+true dependencies shown by 'deps' that are not reflected as formal dependencies
+in 'graph', i.e. a generated header that is required by a given source file but
+not forced to be built first.
+
+To run it:
+
+ - set up a build directory using ninja as the build tool (cmake -G Ninja)
+
+ - in that build directory, run ninja to perform an actual build (populating
+   the dependency database)
+
+ - then, in the same build directory, run this script. No arguments are needed
+   (but -C and -f are accepted, and propagated to ninja for convenience).
+
+Requirements outside core Python: the 'pygraphviz' module, available via pip or
+as the 'python3-pygraphviz' package in Debian and Ubuntu.
+
+"""
+
+import sys
+import argparse
+import subprocess
+import pygraphviz
+
+def toposort(g):
+    """Topologically sort a graph.
+
+    The input g is a pygraphviz graph object representing a DAG. The function
+    yields the vertices of g in an arbitrary order consistent with the edges,
+    so that for any edge v->w, v is output before w."""
+
+    # Count the number of immediate predecessors *not yet output* for each
+    # vertex. Initially this is simply their in-degrees.
+    ideg = {v: g.in_degree(v) for v in g.nodes_iter()}
+
+    # Set of vertices which can be output next, which is true if they have no
+    # immediate predecessor that has not already been output.
+    ready = {v for v, d in ideg.items() if d == 0}
+
+    # Keep outputting vertices while we have any to output.
+    while len(ready) > 0:
+        v = next(iter(ready))
+        yield v
+        ready.remove(v)
+
+        # Having output v, find each immediate successor w, and decrement its
+        # 'ideg' value by 1, to indicate that one more of its predecessors has
+        # now been output.
+        for w in g.out_neighbors(v):
+            ideg[w] -= 1
+            if ideg[w] == 0:
+                # If that counter reaches zero, w is ready to output.
+                ready.add(w)
+
+def ancestors(g, translate = lambda x: x):
+    """Form the set of ancestors for each vertex of a graph.
+
+    The input g is a pygraphviz graph object representing a DAG. The function
+    yields a sequence of pairs (vertex, set of proper ancestors).
+
+    The vertex names are all mapped through 'translate' before output. This
+    allows us to produce output referring to the label rather than the
+    identifier of every vertex.
+    """
+
+    # Store the set of (translated) ancestors for each vertex so far. a[v]
+    # includes (the translation of) v itself.
+    a = {}
+
+    for v in toposort(g):
+        vm = translate(v)
+
+        # Make up a[v], based on a[predecessors of v].
+        a[v] = {vm} # include v itself
+        for w in g.in_neighbors(v):
+            a[v].update(a[w])
+
+        # Remove v itself from the set before yielding it, so that the caller
+        # doesn't get the trivial dependency of v on itself.
+        yield vm, a[v].difference({vm})
+
+def main():
+    parser = argparse.ArgumentParser(
+        description='Find missing formal dependencies on generated include '
+        'files in a build.ninja file.')
+    parser.add_argument("-C", "--build-dir",
+                        help="Build directory (default cwd)")
+    parser.add_argument("-f", "--build-file",
+                        help="Build directory (default build.ninja)")
+    args = parser.parse_args()
+
+    errs = 0
+
+    ninja_prefix = ["ninja"]
+    if args.build_dir is not None:
+        ninja_prefix.extend(["-C", args.build_dir])
+    if args.build_file is not None:
+        ninja_prefix.extend(["-f", args.build_file])
+
+    # Get the formal dependency graph and decode it using pygraphviz.
+    g = pygraphviz.AGraph(subprocess.check_output(
+        ninja_prefix + ["-t", "graph"]).decode("UTF-8"))
+
+    # Helper function to ask for the label of a vertex, which is where ninja's
+    # Graphviz output keeps the actual file name of the target.
+    label = lambda v: g.get_node(v).attr["label"]
+
+    # Start by making a list of build targets, i.e. generated files. These are
+    # just any graph vertex with at least one predecessor.
+    targets = set(label(v) for v in g.nodes_iter() if g.in_degree(v) > 0)
+
+    # Find the set of ancestors of each graph vertex. We pass in 'label' as a
+    # translation function, so that this gives us the set of ancestor _files_
+    # for a given _file_ rather than arbitrary numeric vertex ids.
+    deps = dict(ancestors(g, label))
+
+    # Fetch the cached dependency data and check it against our formal ancestry
+    # data.
+    currtarget = None
+    for line in (subprocess.check_output(ninja_prefix + ["-t", "deps"])
+                 .decode("UTF-8").splitlines()):
+        # ninja -t deps output consists of stanzas of the following form,
+        # separated by a blank line:
+        #
+        # target: [other information we don't need]
+        #     some_file.cpp
+        #     some_header.h
+        #     other_header.h
+        #
+        # We parse this ad-hoc by detecting the four leading spaces in a
+        # source-file line, and the colon in a target line. 'currtarget' stores
+        # the last target name we saw.
+        if line.startswith("    "):
+            dep = line[4:]
+            assert currtarget is not None, "Source file appeared before target"
+
+            # We're only interested in this dependency if it's a *generated*
+            # file, i.e. it is in our set of targets. Also, we must check that
+            # currtarget is actually a target we know about: the dependency
+            # cache is not cleared when build.ninja changes, so it can contain
+            # stale data from targets that existed only in past builds in the
+            # same directory.
+            if (dep in targets and currtarget in deps and
+                dep not in deps[currtarget]):
+                print("error:", currtarget, "requires", dep,
+                      "but has no dependency on it", file=sys.stderr)
+                errs += 1
+        elif ":" in line:
+            currtarget = line.split(":", 1)[0]
+
+    if errs:
+        sys.exit("{:d} errors found".format(errs))
+
+if __name__ == '__main__':
+    main()