import: utils: 'recursive-import' returns packages in topological order.

* guix/import/utils.scm (topological-sort): New procedure.
(recursive-import): Rewrite to use it.
* tests/import-utils.scm ("recursive-import"): New test.
* guix/import/cran.scm (cran->guix-package): Always return two values.
* guix/scripts/import/cran.scm (guix-import-cran): Remove 'reverse' call
on 'cran-recursive-import' result.
* guix/scripts/import/crate.scm (guix-import-crate): Likewise.
* guix/scripts/import/elpa.scm (guix-import-elpa): Likewise.
* guix/scripts/import/gem.scm (guix-import-gem): Likewise.
* guix/scripts/import/hackage.scm (guix-import-hackage): Likewise.
* guix/scripts/import/opam.scm (guix-import-opam): Likewise.
* guix/scripts/import/pypi.scm (guix-import-pypi): Likewise.
* guix/scripts/import/stackage.scm (guix-import-stackage): Likewise.
* tests/gem.scm ("gem-recursive-import"): Change the order of package
expressions accordingly.

12 files changed, 105 insertions, 74 deletions

diff --git a/guix/import/cran.scm b/guix/import/cran.scm
index e47aff2b12..d9018cc7da 100644
--- a/guix/import/cran.scm
+++ b/guix/import/cran.scm
@@ -1,6 +1,6 @@
 ;;; GNU Guix --- Functional package management for GNU
 ;;; Copyright © 2015, 2016, 2017, 2018, 2019 Ricardo Wurmus <rekado@elephly.net>
-;;; Copyright © 2015, 2016, 2017 Ludovic Courtès <ludo@gnu.org>
+;;; Copyright © 2015, 2016, 2017, 2019 Ludovic Courtès <ludo@gnu.org>
 ;;; Copyright © 2017 Mathieu Othacehe <m.othacehe@gmail.com>
 ;;;
 ;;; This file is part of GNU Guix.
@@ -505,7 +505,7 @@ s-expression corresponding to that package, or #f on failure."
              ((bioconductor)
               ;; Retry import from CRAN
               (cran->guix-package package-name 'cran))
-             (else #f)))))))
+             (else (values #f '()))))))))
 
 (define* (cran-recursive-import package-name #:optional (repo 'cran))
   (recursive-import package-name repo
diff --git a/guix/import/utils.scm b/guix/import/utils.scm
index 4694b6e7ef..ef7c13259d 100644
--- a/guix/import/utils.scm
+++ b/guix/import/utils.scm
@@ -34,12 +34,14 @@
   #:use-module (guix gexp)
   #:use-module (guix store)
   #:use-module (guix download)
+  #:use-module (guix sets)
   #:use-module (gnu packages)
   #:use-module (ice-9 match)
   #:use-module (ice-9 rdelim)
   #:use-module (ice-9 receive)
   #:use-module (ice-9 regex)
   #:use-module (srfi srfi-1)
+  #:use-module (srfi srfi-9)
   #:use-module (srfi srfi-11)
   #:use-module (srfi srfi-26)
   #:use-module (srfi srfi-41)
@@ -377,40 +379,54 @@ separated by PRED."
                                       (chr (char-downcase chr)))
                                     name)))
 
+(define (topological-sort nodes
+                          node-dependencies
+                          node-name)
+  "Perform a breadth-first traversal of the graph rooted at NODES, a list of
+nodes, and return the list of nodes sorted in topological order.  Call
+NODE-DEPENDENCIES to obtain the dependencies of a node, and NODE-NAME to
+obtain a node's uniquely identifying \"key\"."
+  (let loop ((nodes nodes)
+             (result '())
+             (visited (set)))
+    (match nodes
+      (()
+       result)
+      ((head . tail)
+       (if (set-contains? visited (node-name head))
+           (loop tail result visited)
+           (let ((dependencies (node-dependencies head)))
+             (loop (append dependencies tail)
+                   (cons head result)
+                   (set-insert (node-name head) visited))))))))
+
 (define* (recursive-import package-name repo
                            #:key repo->guix-package guix-name
                            #:allow-other-keys)
-  "Generate a stream of package expressions for PACKAGE-NAME and all its
-dependencies."
-  (define (exists? dependency)
-    (not (null? (find-packages-by-name (guix-name dependency)))))
-  (define initial-state (list #f (list package-name) (list)))
-  (define (step state)
-    (match state
-      ((prev (next . rest) done)
-       (define (handle? dep)
-         (and
-           (not (equal? dep next))
-           (not (member dep done))
-           (not (exists? dep))))
-       (receive (package . dependencies) (repo->guix-package next repo)
-         (list
-           (if package package '()) ;; default #f on failure would interrupt
-           (if package
-             (lset-union equal? rest (filter handle? (car dependencies)))
-             rest)
-           (cons next done))))
-      ((prev '() done)
-       (list #f '() done))))
-
-  ;; Generate a lazy stream of package expressions for all unknown
-  ;; dependencies in the graph.
-  (stream-unfold
-    ;; map: produce a stream element
-    (match-lambda ((latest queue done) latest))
-    ;; predicate
-    (match-lambda ((latest queue done) latest))
-    ;; generator: update the queue
-    step
-    ;; initial state
-    (step initial-state)))
+  "Return a stream of package expressions for PACKAGE-NAME and all its
+dependencies, sorted in topological order.  For each package,
+call (REPO->GUIX-PACKAGE NAME REPO), which should return a package expression
+and a list of dependencies; call (GUIX-NAME NAME) to obtain the Guix package
+name corresponding to the upstream name."
+  (define-record-type <node>
+    (make-node name package dependencies)
+    node?
+    (name         node-name)
+    (package      node-package)
+    (dependencies node-dependencies))
+
+  (define (exists? name)
+    (not (null? (find-packages-by-name (guix-name name)))))
+
+  (define (lookup-node name)
+    (receive (package dependencies) (repo->guix-package name repo)
+      (make-node name package dependencies)))
+
+  (list->stream                                   ;TODO: remove streams
+   (map node-package
+        (topological-sort (list (lookup-node package-name))
+                          (lambda (node)
+                            (map lookup-node
+                                 (remove exists?
+                                         (node-dependencies node))))
+                          node-name))))
diff --git a/guix/scripts/import/cran.scm b/guix/scripts/import/cran.scm
index b6592f78a9..d47be584ae 100644
--- a/guix/scripts/import/cran.scm
+++ b/guix/scripts/import/cran.scm
@@ -98,10 +98,9 @@ Import and convert the CRAN package for PACKAGE-NAME.\n"))
        (if (assoc-ref opts 'recursive)
            ;; Recursive import
            (map package->definition
-                (reverse
-                 (stream->list
-                  (cran-recursive-import package-name
-                                         (or (assoc-ref opts 'repo) 'cran)))))
+                (stream->list
+                 (cran-recursive-import package-name
+                                        (or (assoc-ref opts 'repo) 'cran))))
            ;; Single import
            (let ((sexp (cran->guix-package package-name
                                            (or (assoc-ref opts 'repo) 'cran))))
diff --git a/guix/scripts/import/crate.scm b/guix/scripts/import/crate.scm
index 4690cceb4d..a388dc368d 100644
--- a/guix/scripts/import/crate.scm
+++ b/guix/scripts/import/crate.scm
@@ -101,9 +101,8 @@ Import and convert the crate.io package for PACKAGE-NAME.\n"))
                    `(define-public ,(string->symbol name)
                       ,pkg))
                   (_ #f))
-                (reverse
-                 (stream->list
-                  (crate-recursive-import name))))
+                (stream->list
+                 (crate-recursive-import name)))
            (let ((sexp (crate->guix-package name version)))
              (unless sexp
                (leave (G_ "failed to download meta-data for package '~a'~%")
diff --git a/guix/scripts/import/elpa.scm b/guix/scripts/import/elpa.scm
index f1ed5016ba..3cdb49eae4 100644
--- a/guix/scripts/import/elpa.scm
+++ b/guix/scripts/import/elpa.scm
@@ -101,10 +101,9 @@ Import the latest package named PACKAGE-NAME from an ELPA repository.\n"))
                    `(define-public ,(string->symbol name)
                       ,pkg))
                   (_ #f))
-                (reverse
-                 (stream->list
-                  (elpa-recursive-import package-name
-                                         (or (assoc-ref opts 'repo) 'gnu)))))
+                (stream->list
+                 (elpa-recursive-import package-name
+                                        (or (assoc-ref opts 'repo) 'gnu))))
            (let ((sexp (elpa->guix-package package-name (assoc-ref opts 'repo))))
              (unless sexp
                (leave (G_ "failed to download package '~a'~%") package-name))
diff --git a/guix/scripts/import/gem.scm b/guix/scripts/import/gem.scm
index b6d9ccaae4..afd7bf6d3e 100644
--- a/guix/scripts/import/gem.scm
+++ b/guix/scripts/import/gem.scm
@@ -95,9 +95,8 @@ Import and convert the RubyGems package for PACKAGE-NAME.\n"))
                    `(define-public ,(string->symbol name)
                       ,pkg))
                   (_ #f))
-                (reverse
-                 (stream->list
-                  (gem-recursive-import package-name 'rubygems))))
+                (stream->list
+                 (gem-recursive-import package-name 'rubygems)))
            (let ((sexp (gem->guix-package package-name)))
              (unless sexp
                (leave (G_ "failed to download meta-data for package '~a'~%")
diff --git a/guix/scripts/import/hackage.scm b/guix/scripts/import/hackage.scm
index f4aac61078..023cc1e700 100644
--- a/guix/scripts/import/hackage.scm
+++ b/guix/scripts/import/hackage.scm
@@ -130,9 +130,8 @@ version.\n"))
                              `(define-public ,(string->symbol name)
                                 ,pkg))
                             (_ #f))
-                          (reverse
-                           (stream->list
-                            (apply hackage-recursive-import arguments))))
+                          (stream->list
+                           (apply hackage-recursive-import arguments)))
                      ;; Single import
                      (apply hackage->guix-package arguments))))
       (unless sexp (error-fn))
diff --git a/guix/scripts/import/opam.scm b/guix/scripts/import/opam.scm
index 2d249a213f..10410f714d 100644
--- a/guix/scripts/import/opam.scm
+++ b/guix/scripts/import/opam.scm
@@ -94,9 +94,8 @@ Import and convert the opam package for PACKAGE-NAME.\n"))
                    `(define-public ,(string->symbol name)
                       ,pkg))
                   (_ #f))
-                (reverse
-                 (stream->list
-                  (opam-recursive-import package-name))))
+                (stream->list
+                 (opam-recursive-import package-name)))
            ;; Single import
            (let ((sexp (opam->guix-package package-name)))
              (unless sexp
diff --git a/guix/scripts/import/pypi.scm b/guix/scripts/import/pypi.scm
index 7bd83818ba..f5f34b3c1b 100644
--- a/guix/scripts/import/pypi.scm
+++ b/guix/scripts/import/pypi.scm
@@ -95,9 +95,8 @@ Import and convert the PyPI package for PACKAGE-NAME.\n"))
                    `(define-public ,(string->symbol name)
                       ,pkg))
                   (_ #f))
-                (reverse
-                 (stream->list
-                  (pypi-recursive-import package-name))))
+                (stream->list
+                 (pypi-recursive-import package-name)))
            ;; Single import
            (let ((sexp (pypi->guix-package package-name)))
              (unless sexp
diff --git a/guix/scripts/import/stackage.scm b/guix/scripts/import/stackage.scm
index b4b12581bf..9325341c84 100644
--- a/guix/scripts/import/stackage.scm
+++ b/guix/scripts/import/stackage.scm
@@ -110,9 +110,8 @@ Import and convert the LTS Stackage package for PACKAGE-NAME.\n"))
                              `(define-public ,(string->symbol name)
                                 ,pkg))
                             (_ #f))
-                          (reverse
-                           (stream->list
-                            (apply stackage-recursive-import arguments))))
+                          (stream->list
+                           (apply stackage-recursive-import arguments)))
                      ;; Single import
                      (apply stackage->guix-package arguments))))
       (unless sexp (error-fn))
diff --git a/tests/gem.scm b/tests/gem.scm
index a12edb294c..82b2c3cea1 100644
--- a/tests/gem.scm
+++ b/tests/gem.scm
@@ -123,22 +123,21 @@
              (_ (error "Unexpected URL: " url)))))
         (match (stream->list (gem-recursive-import "foo"))
           ((('package
-              ('name "ruby-foo")
+              ('name "ruby-bar")
               ('version "1.0.0")
               ('source
                ('origin
                  ('method 'url-fetch)
-                 ('uri ('rubygems-uri "foo" 'version))
+                 ('uri ('rubygems-uri "bar" 'version))
                  ('sha256
                   ('base32
                    "1a270mlajhrmpqbhxcqjqypnvgrq4pgixpv3w9gwp1wrrapnwrzk"))))
               ('build-system 'ruby-build-system)
               ('propagated-inputs
                ('quasiquote
-                (("bundler" ('unquote 'bundler))
-                 ("ruby-bar" ('unquote 'ruby-bar)))))
-              ('synopsis "A cool gem")
-              ('description "This package provides a cool gem")
+                (('"bundler" ('unquote 'bundler)))))
+              ('synopsis "Another cool gem")
+              ('description "Another cool gem")
               ('home-page "https://example.com")
               ('license ('list 'license:expat 'license:asl2.0)))
             ('package
@@ -157,21 +156,22 @@
               ('home-page "https://bundler.io/")
               ('license 'license:expat))
             ('package
-              ('name "ruby-bar")
+              ('name "ruby-foo")
               ('version "1.0.0")
               ('source
                ('origin
                  ('method 'url-fetch)
-                 ('uri ('rubygems-uri "bar" 'version))
+                 ('uri ('rubygems-uri "foo" 'version))
                  ('sha256
                   ('base32
                    "1a270mlajhrmpqbhxcqjqypnvgrq4pgixpv3w9gwp1wrrapnwrzk"))))
               ('build-system 'ruby-build-system)
               ('propagated-inputs
                ('quasiquote
-                (('"bundler" ('unquote 'bundler)))))
-              ('synopsis "Another cool gem")
-              ('description "Another cool gem")
+                (("bundler" ('unquote 'bundler))
+                 ("ruby-bar" ('unquote 'ruby-bar)))))
+              ('synopsis "A cool gem")
+              ('description "This package provides a cool gem")
               ('home-page "https://example.com")
               ('license ('list 'license:expat 'license:asl2.0))))
            #t)
diff --git a/tests/import-utils.scm b/tests/import-utils.scm
index c3ab25d788..3400433bbb 100644
--- a/tests/import-utils.scm
+++ b/tests/import-utils.scm
@@ -24,7 +24,9 @@
   #:use-module (guix packages)
   #:use-module (guix build-system)
   #:use-module (gnu packages)
-  #:use-module (srfi srfi-64))
+  #:use-module (srfi srfi-41)
+  #:use-module (srfi srfi-64)
+  #:use-module (ice-9 match))
 
 (test-begin "import-utils")
 
@@ -41,6 +43,27 @@
   'license:lgpl2.0
   (license->symbol license:lgpl2.0))
 
+(test-equal "recursive-import"
+  '((package                         ;package expressions in topological order
+      (name "bar"))
+    (package
+      (name "foo")
+      (inputs `(("bar" ,bar)))))
+  (stream->list
+   (recursive-import "foo" 'repo
+                     #:repo->guix-package
+                     (match-lambda*
+                       (("foo" 'repo)
+                        (values '(package
+                                   (name "foo")
+                                   (inputs `(("bar" ,bar))))
+                                '("bar")))
+                       (("bar" 'repo)
+                        (values '(package
+                                   (name "bar"))
+                                '())))
+                     #:guix-name identity)))
+
 (test-assert "alist->package with simple source"
   (let* ((meta '(("name" . "hello")
                  ("version" . "2.10")