lib.closePropagation: Remove the quadratic behavior in lib.closePropagation

The code of `lib.closePropagation` was internally using a
recursion on the dependencies and returns all the derivation directly or
indirectly referenced by buildInputs.

`lib.closeProgation` is implemented in pure nix and uses an unique
function for list which is quadratic and does "true" equality, which
needs deep set comparison.

Instead, we use the `builtins.genericClosure` which is implemented as a
builtin and uses a more efficient sorting feature.

Note that `genericClosure` needs a `key` to discriminate the values, we
used the `outPath` which is unique and orderable.

On benchmarks, it performs up to 15x time faster on a benchmark related
to haskellPackages.ghcWithPackages.

1 files changed, 30 insertions, 1 deletions

diff --git a/lib/deprecated.nix b/lib/deprecated.nix
index ddce69f160ccd..ed14e04bbd68d 100644
--- a/lib/deprecated.nix
+++ b/lib/deprecated.nix
@@ -157,7 +157,36 @@ rec {
                                 }
                       );
 
-  closePropagation = list: (uniqList {inputList = (innerClosePropagation [] list);});
+  closePropagationSlow = list: (uniqList {inputList = (innerClosePropagation [] list);});
+
+  # This is an optimisation of lib.closePropagation which avoids the O(n^2) behavior
+  # Using a list of derivations, it generates the full closure of the propagatedXXXBuildInputs
+  # The ordering / sorting / comparison is done based on the `outPath`
+  # attribute of each derivation.
+  # On some benchmarks, it performs up to 15 times faster than lib.closePropagation.
+  # See https://github.com/NixOS/nixpkgs/pull/194391 for details.
+  closePropagationFast = list:
+    builtins.map (x: x.val) (builtins.genericClosure {
+      startSet = builtins.map (x: {
+        key = x.outPath;
+        val = x;
+      }) (builtins.filter (x: x != null) list);
+      operator = item:
+        if !builtins.isAttrs item.val then
+          [ ]
+        else
+          builtins.concatMap (x:
+            if x != null then [{
+              key = x.outPath;
+              val = x;
+            }] else
+              [ ]) ((item.val.propagatedBuildInputs or [ ])
+                ++ (item.val.propagatedNativeBuildInputs or [ ]));
+    });
+
+  closePropagation = if builtins ? genericClosure
+    then closePropagationFast
+    else closePropagationSlow;
 
   # calls a function (f attr value ) for each record item. returns a list
   mapAttrsFlatten = f: r: map (attr: f attr r.${attr}) (attrNames r);