derivations: Use sets for 'derivations-prerequisites'.

This yields a 46% improvement in 'derivation-prerequisites' invocations
on the Emacs derivation.

* guix/derivations.scm (derivation-prerequisites): Add 'input-set'
  variable, and use it in iterations.

1 files changed, 12 insertions, 9 deletions

diff --git a/guix/derivations.scm b/guix/derivations.scm
index ec438e833c..2f015089a3 100644
--- a/guix/derivations.scm
+++ b/guix/derivations.scm
@@ -31,6 +31,7 @@
   #:use-module (guix hash)
   #:use-module (guix base32)
   #:use-module (guix records)
+  #:use-module (guix sets)
   #:export (<derivation>
             derivation?
             derivation-outputs
@@ -162,16 +163,18 @@ download with a fixed hash (aka. `fetchurl')."
 
 (define (derivation-prerequisites drv)
   "Return the list of derivation-inputs required to build DRV, recursively."
-  (let loop ((drv    drv)
-             (result '()))
-    (let ((inputs (remove (cut member <> result)  ; XXX: quadratic
+  (let loop ((drv       drv)
+             (result    '())
+             (input-set (set)))
+    (let ((inputs (remove (cut set-contains? input-set <>)
                           (derivation-inputs drv))))
-      (fold loop
-            (append inputs result)
-            (map (lambda (i)
-                   (call-with-input-file (derivation-input-path i)
-                     read-derivation))
-                 inputs)))))
+      (fold2 loop
+             (append inputs result)
+             (fold set-insert input-set inputs)
+             (map (lambda (i)
+                    (call-with-input-file (derivation-input-path i)
+                      read-derivation))
+                  inputs)))))
 
 (define (offloadable-derivation? drv)
   "Return true if DRV can be offloaded, false otherwise."