about summary refs log tree commit diff
path: root/nix/dependency-analyzer/default.nix
diff options
context:
space:
mode:
Diffstat (limited to 'nix/dependency-analyzer/default.nix')
-rw-r--r--nix/dependency-analyzer/default.nix258
1 files changed, 258 insertions, 0 deletions
diff --git a/nix/dependency-analyzer/default.nix b/nix/dependency-analyzer/default.nix
new file mode 100644
index 000000000000..54ff72912ea8
--- /dev/null
+++ b/nix/dependency-analyzer/default.nix
@@ -0,0 +1,258 @@
+{ lib, depot, pkgs, ... }:
+
+let
+  inherit (builtins) unsafeDiscardStringContext appendContext;
+
+  #
+  # Utilities
+  #
+
+  # Determine all paths a derivation depends on, i.e. input derivations and
+  # files imported into the Nix store.
+  #
+  # Implementation for Nix < 2.6 is quite hacky at the moment.
+  #
+  # Type: str -> [str]
+  #
+  # TODO(sterni): clean this up and expose it
+  directDrvDeps =
+    if lib.versionAtLeast builtins.nixVersion "2.6"
+    then
+    # Since https://github.com/NixOS/nix/pull/1643, Nix apparently »preserves
+    # string context« through a readFile invocation. This has the side effect
+    # that it becomes possible to query the actual references a store path has.
+    # Not a 100% sure this is intended, but _very_ convenient for us here.
+      drvPath:
+      # if the passed path is not a derivation we can't necessarily get its
+      # dependencies, since it may not be representable as a Nix string due to
+      # NUL bytes, e.g. compressed patch files imported into the Nix store.
+      if builtins.match "^.+\\.drv$" drvPath == null
+      then [ ]
+      else builtins.attrNames (builtins.getContext (builtins.readFile drvPath))
+    else
+    # For Nix < 2.6 we have to rely on HACK, namely grepping for quoted store
+    # path references in the file. In the future this should be replaced by
+    # a proper derivation parser.
+      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: builtins.unsafeDiscardOutputDependency 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 = builtins.unsafeDiscardOutputDependency 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;
+}