about summary refs log tree commit diff
diff options
context:
space:
mode:
-rw-r--r--nix/dependency-analyzer/default.nix254
-rw-r--r--nix/dependency-analyzer/examples/ci-targets.nix12
-rw-r--r--nix/dependency-analyzer/examples/lisp.nix5
-rw-r--r--nix/dependency-analyzer/tests/default.nix36
4 files changed, 307 insertions, 0 deletions
diff --git a/nix/dependency-analyzer/default.nix b/nix/dependency-analyzer/default.nix
new file mode 100644
index 000000000000..4ced173eafab
--- /dev/null
+++ b/nix/dependency-analyzer/default.nix
@@ -0,0 +1,254 @@
+{ lib, depot, pkgs, ... }:
+
+let
+  inherit (builtins) unsafeDiscardStringContext appendContext;
+
+  #
+  # Utilities
+  #
+
+  # Manipulate string context of the given string so that it only carries a
+  # `path` reference to itself (so it needs to be a string representation of
+  # a store path).
+  #
+  # This is intended for use on the `drvPath` attribute of derivations which by
+  # default carries a reference to the corresponding outputs. If we only want to
+  # read from the `drvPath`, having only a `path` reference makes sure we don't
+  # need to realise the derivation first.
+  #
+  # Type: str -> str
+  pathContextDrvPath = drvPath:
+    let
+      drvPath' = unsafeDiscardStringContext drvPath;
+    in
+    appendContext drvPath' { ${drvPath'} = { path = true; }; };
+
+  # Find all quoted references to a derivation path in the specified drv file.
+  # Should correspond to the list of input derivations, but is obviously a big
+  # HACK as we just grep for store paths that look right. This should eventually
+  # be solved properly by parsing the drv file.
+  #
+  # Type: str -> [str]
+  directDrvDeps = drvPath: builtins.concatLists (
+    builtins.filter builtins.isList (
+      builtins.split
+        "\"(${lib.escapeRegex builtins.storeDir}/[[:alnum:]+._?=-]+.drv)\""
+        (builtins.readFile drvPath)
+    )
+  );
+
+  # Maps a list of derivation to the list of corresponding `drvPath`s.
+  #
+  # Type: [drv] -> [str]
+  drvsToPaths = drvs:
+    builtins.map (drv: pathContextDrvPath drv.drvPath) drvs;
+
+  #
+  # Calculate map of direct derivation dependencies
+  #
+
+  # Create the dependency map entry for a given `drvPath` which mainly includes
+  # a list of other `drvPath`s it depends on. Additionally we store whether the
+  # derivation is `known`, i.e. part of the initial list of derivations we start
+  # generating the map from
+  #
+  # Type: bool -> string -> set
+  drvEntry = known: drvPath:
+    let
+      # key may not refer to a store path, …
+      key = unsafeDiscardStringContext drvPath;
+      # but we must read from the .drv file.
+      path = pathContextDrvPath drvPath;
+    in
+    {
+      inherit key;
+      # trick so we can call listToAttrs directly on the result of genericClosure
+      name = key;
+      value = {
+        deps = directDrvDeps path;
+        inherit known;
+      };
+    };
+
+  # Create an attribute set that maps every derivation in the combined
+  # dependency closure of the list of input derivation paths to every of their
+  # direct dependencies. Additionally every entry will have set their `known`
+  # attribute to `true` if it is in the list of input derivation paths.
+  #
+  # Type: [str] -> set
+  plainDrvDepMap = drvPaths:
+    builtins.listToAttrs (
+      builtins.genericClosure {
+        startSet = builtins.map (drvEntry true) drvPaths;
+        operator = { value, ... }: builtins.map (drvEntry false) value.deps;
+      }
+    );
+
+  #
+  # Calculate closest known dependencies in the dependency map
+  #
+
+  inherit (depot.nix.stateMonad)
+    after
+    bind
+    for_
+    get
+    getAttr
+    run
+    setAttr
+    pure
+    ;
+
+  # This is an action in stateMonad which expects the (initial) state to have
+  # been produced by `plainDrvDepMap`. Given a `drvPath`, it calculates a
+  # `knownDeps` list which holds the `drvPath`s of the closest derivation marked
+  # as `known` along every edge. This list is inserted into the dependency map
+  # for `drvPath` and every other derivation in its dependecy closure (unless
+  # the information was already present). This means that the known dependency
+  # information for a derivation never has to be recalculated, as long as they
+  # are part of the same stateful computation.
+  #
+  # The upshot is that after calling `insertKnownDeps drvPath`,
+  # `fmap (builtins.getAttr "knownDeps") (getAttr drvPath)` will always succeed.
+  #
+  # Type: str -> stateMonad drvDepMap null
+  insertKnownDeps = drvPathWithContext:
+    let
+      # We no longer need to read from the store, so context is irrelevant, but
+      # we need to check for attr names which requires the absence of context.
+      drvPath = unsafeDiscardStringContext drvPathWithContext;
+    in
+    bind get (initDepMap:
+      # Get the dependency map's state before we've done anything to obtain the
+      # entry we'll be manipulating later as well as its dependencies.
+      let
+        entryPoint = initDepMap.${drvPath};
+
+        # We don't need to recurse if our direct dependencies either have their
+        # knownDeps list already populated or are known dependencies themselves.
+        depsPrecalculated =
+          builtins.partition
+            (dep:
+              initDepMap.${dep}.known
+              || initDepMap.${dep} ? knownDeps
+            )
+            entryPoint.deps;
+
+        # If a direct dependency is known, it goes right to our known dependency
+        # list. If it is unknown, we can copy its knownDeps list into our own.
+        initiallyKnownDeps =
+          builtins.concatLists (
+            builtins.map
+              (dep:
+                if initDepMap.${dep}.known
+                then [ dep ]
+                else initDepMap.${dep}.knownDeps
+              )
+              depsPrecalculated.right
+          );
+      in
+
+      # If the information was already calculated before, we can exit right away
+      if entryPoint ? knownDeps
+      then pure null
+      else
+        after
+          # For all unknown direct dependencies which don't have a `knownDeps`
+          # list, we call ourselves recursively to populate it. Since this is
+          # done sequentially in the state monad, we avoid recalculating the
+          # list for the same derivation multiple times.
+          (for_
+            depsPrecalculated.wrong
+            insertKnownDeps)
+          # After this we can obtain the updated dependency map which will have
+          # a `knownDeps` list for all our direct dependencies and update the
+          # entry for the input `drvPath`.
+          (bind
+            get
+            (populatedDepMap:
+              (setAttr drvPath (entryPoint // {
+                knownDeps =
+                  lib.unique (
+                    initiallyKnownDeps
+                      ++ builtins.concatLists (
+                      builtins.map
+                        (dep: populatedDepMap.${dep}.knownDeps)
+                        depsPrecalculated.wrong
+                    )
+                  );
+              }))))
+    );
+
+  # This function puts it all together and is exposed via `__functor`.
+  #
+  # For a list of `drvPath`s, calculate an attribute set which maps every
+  # `drvPath` to a set of the following form:
+  #
+  #     {
+  #       known = true /* if it is in the list of input derivation paths */;
+  #       deps = [
+  #         /* list of derivation paths it depends on directly */
+  #       ];
+  #       knownDeps = [
+  #         /* list of the closest derivation paths marked as known this
+  #            derivation depends on.
+  #         */
+  #       ];
+  #     }
+  knownDrvDepMap = knownDrvPaths:
+    run
+      (plainDrvDepMap knownDrvPaths)
+      (after
+        (for_
+          knownDrvPaths
+          insertKnownDeps)
+        get);
+
+  #
+  # Other things based on knownDrvDepMap
+  #
+
+  # Create a SVG visualizing `knownDrvDepMap`. Nodes are identified by derivation
+  # name, so multiple entries can be collapsed if they have the same name.
+  #
+  # Type: [drv] -> drv
+  knownDependencyGraph = name: drvs:
+    let
+      justName = drvPath:
+        builtins.substring
+          (builtins.stringLength builtins.storeDir + 1 + 32 + 1)
+          (builtins.stringLength drvPath)
+          (unsafeDiscardStringContext drvPath);
+
+      gv = pkgs.writeText "${name}-dependency-analysis.gv" ''
+        digraph depot {
+        ${
+          (lib.concatStringsSep "\n"
+          (lib.mapAttrsToList (name: value:
+            if !value.known then ""
+            else lib.concatMapStringsSep "\n"
+              (knownDep: "  \"${justName name}\" -> \"${justName knownDep}\"")
+              value.knownDeps
+          )
+          (depot.nix.dependency-analyzer (
+            drvsToPaths drvs
+          ))))
+        }
+        }
+      '';
+    in
+
+    pkgs.runCommand "${name}-dependency-analysis.svg"
+      {
+        nativeBuildInputs = [
+          pkgs.buildPackages.graphviz
+        ];
+      }
+      "dot -Tsvg < ${gv} > $out";
+in
+
+{
+  __functor = _: knownDrvDepMap;
+
+  inherit knownDependencyGraph plainDrvDepMap drvsToPaths;
+}
diff --git a/nix/dependency-analyzer/examples/ci-targets.nix b/nix/dependency-analyzer/examples/ci-targets.nix
new file mode 100644
index 000000000000..597abd410961
--- /dev/null
+++ b/nix/dependency-analyzer/examples/ci-targets.nix
@@ -0,0 +1,12 @@
+{ depot, lib, ... }:
+
+(
+  depot.nix.dependency-analyzer.knownDependencyGraph
+    "depot"
+    depot.ci.targets
+).overrideAttrs (old: {
+  # Causes an infinite recursion via ci.targets otherwise
+  meta = lib.recursiveUpdate (old.meta or { }) {
+    ci.skip = true;
+  };
+})
diff --git a/nix/dependency-analyzer/examples/lisp.nix b/nix/dependency-analyzer/examples/lisp.nix
new file mode 100644
index 000000000000..775eb9ab573f
--- /dev/null
+++ b/nix/dependency-analyzer/examples/lisp.nix
@@ -0,0 +1,5 @@
+{ depot, lib, ... }:
+
+depot.nix.dependency-analyzer.knownDependencyGraph "3p-lisp" (
+  builtins.filter lib.isDerivation (builtins.attrValues depot.third_party.lisp)
+)
diff --git a/nix/dependency-analyzer/tests/default.nix b/nix/dependency-analyzer/tests/default.nix
new file mode 100644
index 000000000000..79ac127e922f
--- /dev/null
+++ b/nix/dependency-analyzer/tests/default.nix
@@ -0,0 +1,36 @@
+{ depot, lib, ... }:
+
+let
+  inherit (depot.nix.runTestsuite)
+    runTestsuite
+    assertEq
+    it
+    ;
+
+  inherit (depot.nix.dependency-analyzer)
+    plainDrvDepMap
+    drvsToPaths
+    ;
+
+  knownDrvs = drvsToPaths (
+    builtins.filter lib.isDerivation (builtins.attrValues depot.third_party.lisp)
+  );
+  exampleMap = plainDrvDepMap knownDrvs;
+
+  # These will be needed to index into the attribute set which can't have context
+  # in the attribute names.
+  knownDrvsNoContext = builtins.map builtins.unsafeDiscardStringContext knownDrvs;
+in
+
+runTestsuite "dependency-analyzer" [
+  (it "checks plainDrvDepMap properties" [
+    (assertEq "all known drvs are marked known"
+      (builtins.all (drv: exampleMap.${drv}.known) knownDrvsNoContext)
+      true)
+    (assertEq "no unknown drv is marked known"
+      (builtins.all (entry: !entry.known) (
+        builtins.attrValues (builtins.removeAttrs exampleMap knownDrvsNoContext)
+      ))
+      true)
+  ])
+]