feat(nix/sparseTree): get a directory with only selected children r/2830

Given a path (which points to a directory and a list of paths which
are below that path, build a “sparse” version of that directory, so
that it only contains the listed paths (and their children):

    $ nix-build -E 'with import ./. {}; nix.sparseTree ./. [
        ./default.nix
        ./nix/readTree
        ./nix/buildLisp
        ./third_party/nixpkgs
        ./third_party/overlays
      ]'
    /nix/store/0ynj0gc613fs6mfp9snqcvdj5gfxbdzg-sparse-depot
    $ lr -t 'type == d' result/
    result/
    result/nix
    result/nix/buildLisp
    result/nix/buildLisp/example
    result/nix/readTree
    result/nix/readTree/tests
    […]
    result/third_party
    result/third_party/nixpkgs
    result/third_party/overlays
    result/third_party/overlays/haskell
    result/third_party/overlays/haskell/patches
    result/third_party/overlays/patches

This is useful if a derivation depends on depot.path (e. g. if it wants
to import depot at runtime). Usually this means that on every depot
commit (or even worse, every change of .git on a local machine), this
derivation has to be rebuild. By using sparseTree you can instead depend
on a stripped down version of depot which only contains the bits you
actually depend on, avoiding unrelated rebuilds.

Change-Id: I127b108c8b177c657fb46786d0a6256516fd2c52
Reviewed-on: https://cl.tvl.fyi/c/depot/+/3503
Tested-by: BuildkiteCI
Reviewed-by: tazjin <mail@tazj.in>

2 files changed, 65 insertions, 0 deletions

diff --git a/nix/sparseTree/OWNERS b/nix/sparseTree/OWNERS
new file mode 100644
index 000000000000..fdf6d7204051
--- /dev/null
+++ b/nix/sparseTree/OWNERS
@@ -0,0 +1,3 @@
+inherited: true
+owners:
+  - sterni
\ No newline at end of file
diff --git a/nix/sparseTree/default.nix b/nix/sparseTree/default.nix
new file mode 100644
index 000000000000..569b9834b305
--- /dev/null
+++ b/nix/sparseTree/default.nix
@@ -0,0 +1,62 @@
+# Build a “sparse” version of a given directory, only including contained files
+# and directories if they are listed in a supplied list:
+#
+# # A very minimal depot
+# sparseTree ./depot [
+#   ./default.nix
+#   ./depot/nix/readTree/default.nix
+#   ./third_party/nixpkgs
+#   ./third_party/overlays
+# ]
+{ pkgs, lib, ... }:
+
+# root path to use as a reference point
+root:
+# list of paths below `root` that should be
+# included in the resulting directory
+paths:
+
+let
+  rootLength = builtins.stringLength (toString root);
+
+  # Count slashes in a path.
+  #
+  # Type: path -> int
+  depth = path: lib.pipe path [
+    toString
+    (builtins.split "/")
+    (builtins.filter builtins.isList)
+    builtins.length
+  ];
+
+  # (Parent) directories will be created from deepest to shallowest
+  # which should mean no conflicts are caused unless both a child
+  # and its parent directory are in the list of paths.
+  # TODO(sterni): improve error messages in such cases
+  fromDeepest = lib.sort (a: b: depth a < depth b) paths;
+
+  # Create a set which contains the source path to copy / symlink and
+  # it's destination, so the path below the destination root including
+  # a leading slash. Additionally some sanity checking is done.
+  makeSymlink = path:
+    let
+      strPath = toString path;
+      contextPath = "${path}";
+      belowRoot = builtins.substring rootLength (-1) strPath;
+      prefix = builtins.substring 0 rootLength strPath;
+    in assert toString root == prefix; {
+      src = contextPath;
+      dst = belowRoot;
+    };
+
+  symlinks = builtins.map makeSymlink fromDeepest;
+in
+
+# TODO(sterni): teach readTree to also read symlinked directories,
+# so we ln -sT instead of cp -aT.
+pkgs.runCommandNoCC "sparse-${builtins.baseNameOf root}" {} (
+  lib.concatMapStrings ({ src, dst }: ''
+    mkdir -p "$(dirname "$out${dst}")"
+    cp -aT --reflink=auto "${src}" "$out${dst}"
+  '') symlinks
+)