2 files changed, 144 insertions, 0 deletions
diff --git a/nix/readTree/README.md b/nix/readTree/README.md
new file mode 100644
index 000000000000..c93cf2bfdd61
--- /dev/null
+++ b/nix/readTree/README.md
@@ -0,0 +1,81 @@
+readTree
+========
+
+This is a Nix program that builds up an attribute set tree for a large
+repository based on the filesystem layout.
+
+It is in fact the tool that lays out the attribute set of this repository.
+
+As an example, consider a root (`.`) of a repository and a layout such as:
+
+```
+.
+├── third_party
+│   ├── default.nix
+│   └── rustpkgs
+│       ├── aho-corasick.nix
+│       └── serde.nix
+└── tools
+    ├── cheddar
+    │   └── default.nix
+    └── roquefort.nix
+```
+
+When `readTree` is called on that tree, it will construct an attribute set with
+this shape:
+
+```nix
+{
+    tools = {
+        cheddar = ...;
+        roquefort = ...;
+    };
+
+    third_party = {
+        # the `default.nix` of this folder might have had arbitrary other
+        # attributes here, such as this:
+        favouriteColour = "orange";
+
+        rustpkgs = {
+            aho-corasick = ...;
+            serde = ...;
+        };
+    };
+}
+```
+
+Every imported Nix file that yields an attribute set will have a `__readTree =
+true;` attribute merged into it.
+
+## Traversal logic
+
+`readTree` will follow any subdirectories of a tree and import all Nix files,
+with some exceptions:
+
+* A folder can declare that its children are off-limit by containing a
+  `.skip-subtree` file. Since the content of the file is not checked, it can be
+  useful to leave a note for a human in the file.
+* If a folder contains a `default.nix` file, no *sibling* Nix files will be
+  imported - however children are traversed as normal.
+* If a folder contains a `default.nix` it is loaded and, if it evaluates to a
+  set, *merged* with the children. If it evaluates to anything else the children
+  are *not traversed*.
+
+Traversal is lazy, `readTree` will only build up the tree as requested. This
+currently has the downside that directories with no importable files end up in
+the tree as empty nodes (`{}`).
+
+## Import structure
+
+`readTree` is called with two parameters: The arguments to pass to all imports,
+and the initial path at which to start the traversal.
+
+The package headers in this repository follow the form `{ pkgs, ... }:` where
+`pkgs` is a fixed-point of the entire package tree (see the `default.nix` at the
+root of the depot).
+
+In theory `readTree` can pass arguments of different shapes, but I have found
+this to be a good solution for the most part.
+
+Note that `readTree` does not currently make functions overridable, though it is
+feasible that it could do that in the future.
diff --git a/nix/readTree/default.nix b/nix/readTree/default.nix
new file mode 100644
index 000000000000..c48928ee19e4
--- /dev/null
+++ b/nix/readTree/default.nix
@@ -0,0 +1,63 @@
+{ ... }:
+
+args: initPath:
+
+let
+  inherit (builtins)
+    attrNames
+    baseNameOf
+    filter
+    hasAttr
+    head
+    length
+    listToAttrs
+    map
+    match
+    isAttrs
+    readDir;
+
+  argsWithPath = parts: args // {
+    locatedAt = parts;
+  };
+
+  # The marker is added to every set that was imported directly by
+  # readTree.
+  importWithMark = path: parts:
+    let imported = import path (argsWithPath parts);
+    in if (isAttrs imported)
+      then imported // { __readTree = true; }
+      else imported;
+
+  nixFileName = file:
+    let res = match "(.*)\.nix" file;
+    in if res == null then null else head res;
+
+  readTree = path: parts:
+    let
+      dir = readDir path;
+      self = importWithMark path parts;
+      joinChild = c: path + ("/" + c);
+
+      # Import subdirectories of the current one, unless the special
+      # `.skip-subtree` file exists which makes readTree ignore the
+      # children.
+      #
+      # This file can optionally contain information on why the tree
+      # should be ignored, but its content is not inspected by
+      # readTree
+      filterDir = f: dir."${f}" == "directory";
+      children = if hasAttr ".skip-subtree" dir then [] else map (c: {
+        name = c;
+        value = readTree (joinChild c) (parts ++ [ c ]);
+      }) (filter filterDir (attrNames dir));
+
+      # Import Nix files
+      nixFiles = filter (f: f != null) (map nixFileName (attrNames dir));
+      nixChildren = map (c: let p = joinChild (c + ".nix"); in {
+        name = c;
+        value = importWithMark p (parts ++ [ c ]);
+      }) nixFiles;
+    in if dir ? "default.nix"
+      then (if isAttrs self then self // (listToAttrs children) else self)
+      else listToAttrs (nixChildren ++ children);
+in readTree initPath [ (baseNameOf initPath) ]