diff mbox series

[bug#37730] Topologically sort recursively-imported packages

Message ID CAAc=MEwpYfW5OdgNv6Xm-db2LoKo=hnEE+70Q5DHu+23K19WMw@mail.gmail.com
State Accepted
Headers show
Series [bug#37730] Topologically sort recursively-imported packages | expand

Commit Message

Brian Leung Dec. 3, 2019, 11:06 p.m. UTC
Attached is a small edit to clarify the shape of something and rename
accordingly.

On Tue, Dec 3, 2019 at 2:03 PM Brian Leung <bkleung89@gmail.com> wrote:

> Hi Ludo,
>
> Sorry for putting this off; my Guix installation got corrupted and I
> wasn't able to roll back. I'm writing this from within VirtualBox.
>
> In the attached patch I've addressed most of your concerns, except for
> this one:
>
> > Regarding tests, you could make the topological sort code above a
> > separate procedure, and write a couple of tests that call it.
>
> I don't see how this would help. We would have to pass it the
> `repo->guix-package` function and the `repo` variable as an arguments that
> remain the same across all the tail-recursive invocations of `topo-sort`,
> which would make it harder to read. And we'd have to come up with some
> custom `repo->guix-package` function, when we already have one for the
> (say) Crate test.
>
> Efraim: I recall you mentioning a while back that topologically sorted
> output would be nice to have. Please confirm this patch works as expected
> for you.
>
> Thanks,
> Brian
>
> On Fri, Oct 18, 2019 at 2:31 AM Ludovic Courtès <ludo@gnu.org> wrote:
>
>> Hi Brian,
>>
>> Brian Leung <bkleung89@gmail.com> skribis:
>>
>> > From 6fec6a72a7938753307ccf3b7bdad8bff72e47f9 Mon Sep 17 00:00:00 2001
>> > From: Brian Leung <leungbk@mailfence.com>
>> > Date: Fri, 11 Oct 2019 23:18:03 -0700
>> > Subject: [PATCH] guix: utils: Topologically sort recursively-imported
>> recipes.
>> >
>> > This output order, when it is well-defined, facilitates the process of
>> > deciding what to upstream next for a package with a large dependency
>> closure.
>>
>> That’s a great idea!
>>
>> > * guix/import/utils.scm (recursive-import): Enforce topological sort.
>> >   Remove dependency on srfi-41. Reverse output here instead of in
>> individual
>> >   importers.
>> > * guix/scripts/import/cran.scm (guix-import-cran): Unstreamify and don't
>> >   reverse here. Remove dependency on srfi-41.
>>
>> Instead of “Unstreamify”, please write precisely what has changed, like
>> “Remove call to ‘stream-fold’ and call ‘foobar’ directly.”, “Remove call
>> to ‘stream->list’.”, etc.
>>
>> > +  (define graph (make-hash-table))
>> > +  (define recipe-map (make-hash-table))
>> > +  (define stack (list package-name))
>> > +  (define accum '())
>> > +
>> > +  (while (not (null? stack))
>> > +    (let ((package-name (car stack)))
>> > +      (match (hash-ref graph package-name)
>> > +        ('()
>> > +         (set! stack (cdr stack))
>> > +         (set! accum (cons (hash-ref recipe-map package-name) accum)))
>> > +        ((dep . rest)
>> > +         (define (handle? dep)
>> > +           (and
>> > +            (not (equal? dep package-name))
>> > +            (not (hash-ref recipe-map dep))
>> > +            (not (exists? dep))))
>> > +         (hash-set! graph package-name rest)
>> > +         (when (handle? dep)
>> > +           (set! stack (cons dep stack))))
>> > +        (#f
>> > +         (receive (package-recipe . dependencies)
>> > +             (repo->guix-package package-name repo)
>> > +           (hash-set! graph package-name
>> > +                      (or (and (not (null? dependencies))
>> > +                               (car dependencies))
>> > +                          '()))
>> > +           (hash-set! recipe-map package-name
>> > +                      (or package-recipe '())))))))
>> > +
>> > +  (reverse accum))
>>
>> Do you think you could rewrite this (1) in a functional style (you can
>> use vhashes instead of hash tables), and (2) using ‘match’ instead of
>> ‘cdr’ & co.?
>>
>> That would more closely match our conventions (info "(guix) Coding
>> Style") and would also probably allow for easier testing.
>>
>> Regarding tests, you could make the topological sort code above a
>> separate procedure, and write a couple of tests that call it.
>>
>> WDYT?
>>
>> The rest LGTM.
>>
>> Thank you!
>>
>> Ludo’.
>>
>
diff mbox series

Patch

From 915274d493116d063bfe2a953a9e855b8312711e Mon Sep 17 00:00:00 2001
From: Brian Leung <leungbk@mailfence.com>
Date: Fri, 11 Oct 2019 23:18:03 -0700
Subject: [PATCH] guix: utils: Topologically sort recursively imported recipes.

This output order, when it is well-defined, facilitates the process of
deciding what to upstream next for a package with a large dependency closure.

* guix/import/utils.scm (recursive-import): Enforce topological sort. Remove
dependency on srfi-41. Import vlist module. Reverse output here instead of in
individual importers.
* guix/scripts/import/cran.scm (guix-import-cran): Remove calls to
stream->list and reverse. Remove dependency on srfi-41.
* guix/scripts/import/crate.scm (guix-import-crate): Remove calls to
stream->list and reverse. Remove dependency on srfi-41.
* guix/scripts/import/elpa.scm (guix-import-elpa): Remove calls to
stream->list and reverse. Remove dependency on srfi-41.
* guix/scripts/import/gem.scm (guix-import-gem): Remove calls to stream->list
and reverse. Remove dependency on srfi-41.
* guix/scripts/import/hackage.scm (guix-import-hackage): Remove calls to
stream->list and reverse. Remove dependency on srfi-41.
* guix/scripts/import/opam.scm (guix-import-opam): Remove calls to
stream->list and reverse. Remove dependency on srfi-41.
* guix/scripts/import/pypi.scm (guix-import-pypi): Remove calls to
stream->list and reverse. Remove dependency on srfi-41.
* guix/scripts/import/stackage.scm (guix-import-stackage): Remove calls to
stream->list and reverse. Remove dependency on srfi-41.
* tests/crate.scm (cargo-recursive-import): Add test.
* tests/gem.scm (gem-recursive-import): Update to reflect the fact that the
reversing of the list now takes place in the recursive importer. Remove
dependency on srfi-41.
---
 guix/import/utils.scm            |  86 +++++---
 guix/scripts/import/cran.scm     |   7 +-
 guix/scripts/import/crate.scm    |   5 +-
 guix/scripts/import/elpa.scm     |   7 +-
 guix/scripts/import/gem.scm      |   5 +-
 guix/scripts/import/hackage.scm  |   5 +-
 guix/scripts/import/opam.scm     |   5 +-
 guix/scripts/import/pypi.scm     |   5 +-
 guix/scripts/import/stackage.scm |   5 +-
 guix/scripts/import/texlive.scm  |   1 -
 tests/crate.scm                  | 334 ++++++++++++++++++++++++++++++-
 tests/gem.scm                    |  41 ++--
 12 files changed, 413 insertions(+), 93 deletions(-)

diff --git a/guix/import/utils.scm b/guix/import/utils.scm
index 4694b6e7ef..0d9e5fbfdd 100644
--- a/guix/import/utils.scm
+++ b/guix/import/utils.scm
@@ -39,10 +39,10 @@ 
   #:use-module (ice-9 rdelim)
   #:use-module (ice-9 receive)
   #:use-module (ice-9 regex)
+  #:use-module (ice-9 vlist)
   #:use-module (srfi srfi-1)
   #:use-module (srfi srfi-11)
   #:use-module (srfi srfi-26)
-  #:use-module (srfi srfi-41)
   #:export (factorize-uri
 
             flatten
@@ -380,37 +380,57 @@  separated by PRED."
 (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."
+  "Generate a list of package expressions for PACKAGE-NAME and all its
+dependencies.  The list will be in a topological ordering, if one exists."
   (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)))
+
+  (define graph vlist-null)
+  (define recipe-map vlist-null)
+  (define stack (list package-name))
+  (define accum '())
+
+  (define (topo-sort stack graph recipe-map accum)
+    (if (null? stack)
+        (reverse accum)
+        (let ((head-package (car stack)))
+          (match (vhash-assoc head-package graph)
+            ((key . '())
+             (let ((next-stack (cdr stack))
+                   (next-accum (cons (cdr (vhash-assoc head-package recipe-map))
+                                     accum)))
+               (topo-sort next-stack
+                          graph
+                          recipe-map
+                          next-accum)))
+            ((key . (dep . rest))
+             (define (handle? dep)
+               (and
+                (not (equal? dep head-package))
+                (not (vhash-assoc dep recipe-map))
+                (not (exists? dep))))
+             (let* ((next-stack (if (handle? dep)
+                                    (cons dep stack)
+                                    stack))
+                    (next-graph (vhash-cons key rest graph)))
+               (topo-sort next-stack
+                          next-graph
+                          recipe-map
+                          accum)))
+            (#f
+             (receive (package-recipe . dependencies) (repo->guix-package head-package repo)
+               (let ((next-graph (vhash-cons head-package
+                                             ;; dependencies has shape '(("package-a" "package-b" ...))
+                                             (car dependencies)
+                                             graph))
+                     (next-recipe-map (vhash-cons head-package
+                                                  (or
+                                                   package-recipe
+                                                   '())
+                                                  recipe-map)))
+                 (topo-sort stack
+                            next-graph
+                            next-recipe-map
+                            accum))))))))
+
+  (topo-sort stack graph recipe-map accum))
diff --git a/guix/scripts/import/cran.scm b/guix/scripts/import/cran.scm
index b6592f78a9..d6f371ef3a 100644
--- a/guix/scripts/import/cran.scm
+++ b/guix/scripts/import/cran.scm
@@ -27,7 +27,6 @@ 
   #:use-module (srfi srfi-1)
   #:use-module (srfi srfi-11)
   #:use-module (srfi srfi-37)
-  #:use-module (srfi srfi-41)
   #:use-module (ice-9 match)
   #:use-module (ice-9 format)
   #:export (guix-import-cran))
@@ -98,10 +97,8 @@  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)))))
+                (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..92034dab3c 100644
--- a/guix/scripts/import/crate.scm
+++ b/guix/scripts/import/crate.scm
@@ -28,7 +28,6 @@ 
   #:use-module (srfi srfi-1)
   #:use-module (srfi srfi-11)
   #:use-module (srfi srfi-37)
-  #:use-module (srfi srfi-41)
   #:use-module (ice-9 match)
   #:use-module (ice-9 format)
   #:export (guix-import-crate))
@@ -101,9 +100,7 @@  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))))
+                (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..d270d2b4bc 100644
--- a/guix/scripts/import/elpa.scm
+++ b/guix/scripts/import/elpa.scm
@@ -27,7 +27,6 @@ 
   #:use-module (srfi srfi-1)
   #:use-module (srfi srfi-11)
   #:use-module (srfi srfi-37)
-  #:use-module (srfi srfi-41)
   #:use-module (ice-9 match)
   #:use-module (ice-9 format)
   #:export (guix-import-elpa))
@@ -101,10 +100,8 @@  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)))))
+                (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..c64596b514 100644
--- a/guix/scripts/import/gem.scm
+++ b/guix/scripts/import/gem.scm
@@ -26,7 +26,6 @@ 
   #:use-module (srfi srfi-1)
   #:use-module (srfi srfi-11)
   #:use-module (srfi srfi-37)
-  #:use-module (srfi srfi-41)
   #:use-module (ice-9 match)
   #:use-module (ice-9 format)
   #:export (guix-import-gem))
@@ -95,9 +94,7 @@  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))))
+                (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..710e786a79 100644
--- a/guix/scripts/import/hackage.scm
+++ b/guix/scripts/import/hackage.scm
@@ -27,7 +27,6 @@ 
   #:use-module (srfi srfi-1)
   #:use-module (srfi srfi-11)
   #:use-module (srfi srfi-37)
-  #:use-module (srfi srfi-41)
   #:use-module (ice-9 match)
   #:use-module (ice-9 format)
   #:export (guix-import-hackage))
@@ -130,9 +129,7 @@  version.\n"))
                              `(define-public ,(string->symbol name)
                                 ,pkg))
                             (_ #f))
-                          (reverse
-                           (stream->list
-                            (apply hackage-recursive-import arguments))))
+                          (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..20da1437fe 100644
--- a/guix/scripts/import/opam.scm
+++ b/guix/scripts/import/opam.scm
@@ -25,7 +25,6 @@ 
   #:use-module (srfi srfi-1)
   #:use-module (srfi srfi-11)
   #:use-module (srfi srfi-37)
-  #:use-module (srfi srfi-41)
   #:use-module (ice-9 match)
   #:use-module (ice-9 format)
   #:export (guix-import-opam))
@@ -94,9 +93,7 @@  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))))
+                (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..33167174e2 100644
--- a/guix/scripts/import/pypi.scm
+++ b/guix/scripts/import/pypi.scm
@@ -26,7 +26,6 @@ 
   #:use-module (srfi srfi-1)
   #:use-module (srfi srfi-11)
   #:use-module (srfi srfi-37)
-  #:use-module (srfi srfi-41)
   #:use-module (ice-9 match)
   #:use-module (ice-9 format)
   #:export (guix-import-pypi))
@@ -95,9 +94,7 @@  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))))
+                (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..d77328dcbf 100644
--- a/guix/scripts/import/stackage.scm
+++ b/guix/scripts/import/stackage.scm
@@ -27,7 +27,6 @@ 
   #:use-module (srfi srfi-1)
   #:use-module (srfi srfi-11)
   #:use-module (srfi srfi-37)
-  #:use-module (srfi srfi-41)
   #:use-module (ice-9 match)
   #:use-module (ice-9 format)
   #:export (guix-import-stackage))
@@ -110,9 +109,7 @@  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))))
+                          (apply stackage-recursive-import arguments))
                      ;; Single import
                      (apply stackage->guix-package arguments))))
       (unless sexp (error-fn))
diff --git a/guix/scripts/import/texlive.scm b/guix/scripts/import/texlive.scm
index 1cceee7051..e31c56d0ce 100644
--- a/guix/scripts/import/texlive.scm
+++ b/guix/scripts/import/texlive.scm
@@ -25,7 +25,6 @@ 
   #:use-module (srfi srfi-1)
   #:use-module (srfi srfi-11)
   #:use-module (srfi srfi-37)
-  #:use-module (srfi srfi-41)
   #:use-module (ice-9 match)
   #:use-module (ice-9 format)
   #:export (guix-import-texlive))
diff --git a/tests/crate.scm b/tests/crate.scm
index c14862ad9f..d55c814bcf 100644
--- a/tests/crate.scm
+++ b/tests/crate.scm
@@ -28,7 +28,7 @@ 
   #:use-module (ice-9 match)
   #:use-module (srfi srfi-64))
 
-(define test-crate
+(define test-foo-crate
   "{
   \"crate\": {
     \"max_version\": \"1.0.0\",
@@ -50,7 +50,7 @@ 
   }
 }")
 
-(define test-dependencies
+(define test-foo-dependencies
   "{
   \"dependencies\": [
      {
@@ -60,6 +60,176 @@ 
   ]
 }")
 
+(define test-root-crate
+  "{
+  \"crate\": {
+    \"max_version\": \"1.0.0\",
+    \"name\": \"root\",
+    \"description\": \"summary\",
+    \"homepage\": \"http://example.com\",
+    \"repository\": \"http://example.com\",
+    \"keywords\": [\"dummy\" \"test\"],
+    \"categories\": [\"test\"]
+    \"actual_versions\": [
+      { \"id\": \"foo\",
+        \"num\": \"1.0.0\",
+        \"license\": \"MIT OR Apache-2.0\",
+        \"links\": {
+          \"dependencies\": \"/api/v1/crates/root/1.0.0/dependencies\"
+        }
+      }
+    ]
+  }
+}")
+
+(define test-root-dependencies
+  "{
+  \"dependencies\": [
+     {
+       \"crate_id\": \"intermediate-1\",
+       \"kind\": \"normal\",
+     },
+     {
+       \"crate_id\": \"intermediate-2\",
+       \"kind\": \"normal\",
+     }
+     {
+       \"crate_id\": \"leaf-alice\",
+       \"kind\": \"normal\",
+     },
+     {
+       \"crate_id\": \"leaf-bob\",
+       \"kind\": \"normal\",
+     },
+  ]
+}")
+
+(define test-intermediate-1-crate
+  "{
+  \"crate\": {
+    \"max_version\": \"1.0.0\",
+    \"name\": \"intermediate-1\",
+    \"description\": \"summary\",
+    \"homepage\": \"http://example.com\",
+    \"repository\": \"http://example.com\",
+    \"keywords\": [\"dummy\" \"test\"],
+    \"categories\": [\"test\"]
+    \"actual_versions\": [
+      { \"id\": \"intermediate-1\",
+        \"num\": \"1.0.0\",
+        \"license\": \"MIT OR Apache-2.0\",
+        \"links\": {
+          \"dependencies\": \"/api/v1/crates/intermediate-1/1.0.0/dependencies\"
+        }
+      }
+    ]
+  }
+}")
+
+(define test-intermediate-1-dependencies
+  "{
+  \"dependencies\": [
+     {
+       \"crate_id\": \"intermediate-2\",
+       \"kind\": \"normal\",
+     },
+     {
+       \"crate_id\": \"leaf-alice\",
+       \"kind\": \"normal\",
+     },
+     {
+       \"crate_id\": \"leaf-bob\",
+       \"kind\": \"normal\",
+     }
+  ]
+}")
+
+(define test-intermediate-2-crate
+  "{
+  \"crate\": {
+    \"max_version\": \"1.0.0\",
+    \"name\": \"intermediate-2\",
+    \"description\": \"summary\",
+    \"homepage\": \"http://example.com\",
+    \"repository\": \"http://example.com\",
+    \"keywords\": [\"dummy\" \"test\"],
+    \"categories\": [\"test\"]
+    \"actual_versions\": [
+      { \"id\": \"intermediate-2\",
+        \"num\": \"1.0.0\",
+        \"license\": \"MIT OR Apache-2.0\",
+        \"links\": {
+          \"dependencies\": \"/api/v1/crates/intermediate-2/1.0.0/dependencies\"
+        }
+      }
+    ]
+  }
+}")
+
+(define test-intermediate-2-dependencies
+  "{
+  \"dependencies\": [
+     {
+       \"crate_id\": \"leaf-bob\",
+       \"kind\": \"normal\",
+     },
+  ]
+}")
+
+(define test-leaf-alice-crate
+  "{
+  \"crate\": {
+    \"max_version\": \"1.0.0\",
+    \"name\": \"leaf-alice\",
+    \"description\": \"summary\",
+    \"homepage\": \"http://example.com\",
+    \"repository\": \"http://example.com\",
+    \"keywords\": [\"dummy\" \"test\"],
+    \"categories\": [\"test\"]
+    \"actual_versions\": [
+      { \"id\": \"leaf-alice\",
+        \"num\": \"1.0.0\",
+        \"license\": \"MIT OR Apache-2.0\",
+        \"links\": {
+          \"dependencies\": \"/api/v1/crates/leaf-alice/1.0.0/dependencies\"
+        }
+      }
+    ]
+  }
+}")
+
+(define test-leaf-alice-dependencies
+  "{
+  \"dependencies\": []
+}")
+
+(define test-leaf-bob-crate
+  "{
+  \"crate\": {
+    \"max_version\": \"1.0.0\",
+    \"name\": \"leaf-bob\",
+    \"description\": \"summary\",
+    \"homepage\": \"http://example.com\",
+    \"repository\": \"http://example.com\",
+    \"keywords\": [\"dummy\" \"test\"],
+    \"categories\": [\"test\"]
+    \"actual_versions\": [
+      { \"id\": \"leaf-bob\",
+        \"num\": \"1.0.0\",
+        \"license\": \"MIT OR Apache-2.0\",
+        \"links\": {
+          \"dependencies\": \"/api/v1/crates/leaf-bob/1.0.0/dependencies\"
+        }
+      }
+    ]
+  }
+}")
+
+(define test-leaf-bob-dependencies
+  "{
+  \"dependencies\": []
+}")
+
 (define test-source-hash
   "")
 
@@ -79,14 +249,14 @@ 
          (lambda (url . rest)
            (match url
              ("https://crates.io/api/v1/crates/foo"
-              (open-input-string test-crate))
+              (open-input-string test-foo-crate))
              ("https://crates.io/api/v1/crates/foo/1.0.0/download"
               (set! test-source-hash
                 (bytevector->nix-base32-string
                  (sha256 (string->bytevector "empty file\n" "utf-8"))))
               (open-input-string "empty file\n"))
              ("https://crates.io/api/v1/crates/foo/1.0.0/dependencies"
-              (open-input-string test-dependencies))
+              (open-input-string test-foo-dependencies))
              (_ (error "Unexpected URL: " url)))))
     (match (crate->guix-package "foo")
       (('package
@@ -111,4 +281,160 @@ 
       (x
        (pk 'fail x #f)))))
 
+(test-assert "cargo-recursive-import"
+  ;; Replace network resources with sample data.
+  (mock ((guix http-client) http-fetch
+         (lambda (url . rest)
+           (match url
+             ("https://crates.io/api/v1/crates/root"
+              (open-input-string test-root-crate))
+             ("https://crates.io/api/v1/crates/root/1.0.0/download"
+              (set! test-source-hash
+                    (bytevector->nix-base32-string
+                     (sha256 (string->bytevector "empty file\n" "utf-8"))))
+              (open-input-string "empty file\n"))
+             ("https://crates.io/api/v1/crates/root/1.0.0/dependencies"
+              (open-input-string test-root-dependencies))
+             ("https://crates.io/api/v1/crates/intermediate-1"
+              (open-input-string test-intermediate-1-crate))
+             ("https://crates.io/api/v1/crates/intermediate-1/1.0.0/download"
+              (set! test-source-hash
+                    (bytevector->nix-base32-string
+                     (sha256 (string->bytevector "empty file\n" "utf-8"))))
+              (open-input-string "empty file\n"))
+             ("https://crates.io/api/v1/crates/intermediate-1/1.0.0/dependencies"
+              (open-input-string test-intermediate-1-dependencies))
+             ("https://crates.io/api/v1/crates/intermediate-2"
+              (open-input-string test-intermediate-2-crate))
+             ("https://crates.io/api/v1/crates/intermediate-2/1.0.0/download"
+              (set! test-source-hash
+                    (bytevector->nix-base32-string
+                     (sha256 (string->bytevector "empty file\n" "utf-8"))))
+              (open-input-string "empty file\n"))
+             ("https://crates.io/api/v1/crates/intermediate-2/1.0.0/dependencies"
+              (open-input-string test-intermediate-2-dependencies))
+             ("https://crates.io/api/v1/crates/leaf-alice"
+              (open-input-string test-leaf-alice-crate))
+             ("https://crates.io/api/v1/crates/leaf-alice/1.0.0/download"
+              (set! test-source-hash
+                    (bytevector->nix-base32-string
+                     (sha256 (string->bytevector "empty file\n" "utf-8"))))
+              (open-input-string "empty file\n"))
+             ("https://crates.io/api/v1/crates/leaf-alice/1.0.0/dependencies"
+              (open-input-string test-leaf-alice-dependencies))
+             ("https://crates.io/api/v1/crates/leaf-bob"
+              (open-input-string test-leaf-bob-crate))
+             ("https://crates.io/api/v1/crates/leaf-bob/1.0.0/download"
+              (set! test-source-hash
+                    (bytevector->nix-base32-string
+                     (sha256 (string->bytevector "empty file\n" "utf-8"))))
+              (open-input-string "empty file\n"))
+             ("https://crates.io/api/v1/crates/leaf-bob/1.0.0/dependencies"
+              (open-input-string test-leaf-bob-dependencies))
+             (_ (error "Unexpected URL: " url)))))
+        (match (crate-recursive-import "root")
+          ;; rust-intermediate-2 has no dependency on the rust-leaf-alice package, so this is a valid ordering
+          ((('package
+              ('name "rust-leaf-bob")
+              ('version (? string? ver))
+              ('source
+               ('origin
+                 ('method 'url-fetch)
+                 ('uri ('crate-uri "leaf-bob" 'version))
+                 ('file-name
+                  ('string-append 'name "-" 'version ".tar.gz"))
+                 ('sha256
+                  ('base32
+                   (? string? hash)))))
+              ('build-system 'cargo-build-system)
+              ('home-page "http://example.com")
+              ('synopsis "summary")
+              ('description "summary")
+              ('license ('list 'license:expat 'license:asl2.0)))
+            ('package
+              ('name "rust-intermediate-2")
+              ('version (? string? ver))
+              ('source
+               ('origin
+                 ('method 'url-fetch)
+                 ('uri ('crate-uri "intermediate-2" 'version))
+                 ('file-name
+                  ('string-append 'name "-" 'version ".tar.gz"))
+                 ('sha256
+                  ('base32
+                   (? string? hash)))))
+              ('build-system 'cargo-build-system)
+              ('arguments
+               ('quasiquote
+                ('#:cargo-inputs (("rust-leaf-bob" ('unquote rust-leaf-bob))))))
+              ('home-page "http://example.com")
+              ('synopsis "summary")
+              ('description "summary")
+              ('license ('list 'license:expat 'license:asl2.0)))
+            ('package
+              ('name "rust-leaf-alice")
+              ('version (? string? ver))
+              ('source
+               ('origin
+                 ('method 'url-fetch)
+                 ('uri ('crate-uri "leaf-alice" 'version))
+                 ('file-name
+                  ('string-append 'name "-" 'version ".tar.gz"))
+                 ('sha256
+                  ('base32
+                   (? string? hash)))))
+              ('build-system 'cargo-build-system)
+              ('home-page "http://example.com")
+              ('synopsis "summary")
+              ('description "summary")
+              ('license ('list 'license:expat 'license:asl2.0)))
+            ('package
+              ('name "rust-intermediate-1")
+              ('version (? string? ver))
+              ('source
+               ('origin
+                 ('method 'url-fetch)
+                 ('uri ('crate-uri "intermediate-1" 'version))
+                 ('file-name
+                  ('string-append 'name "-" 'version ".tar.gz"))
+                 ('sha256
+                  ('base32
+                   (? string? hash)))))
+              ('build-system 'cargo-build-system)
+              ('arguments
+               ('quasiquote
+                ('#:cargo-inputs (("rust-intermediate-2" ('unquote rust-intermediate-2))
+                                  ("rust-leaf-alice" ('unquote rust-leaf-alice))
+                                  ("rust-leaf-bob" ('unquote rust-leaf-bob))))))
+              ('home-page "http://example.com")
+              ('synopsis "summary")
+              ('description "summary")
+              ('license ('list 'license:expat 'license:asl2.0)))
+            ('package
+              ('name "rust-root")
+              ('version (? string? ver))
+              ('source
+               ('origin
+                 ('method 'url-fetch)
+                 ('uri ('crate-uri "root" 'version))
+                 ('file-name
+                  ('string-append 'name "-" 'version ".tar.gz"))
+                 ('sha256
+                  ('base32
+                   (? string? hash)))))
+              ('build-system 'cargo-build-system)
+              ('arguments
+               ('quasiquote
+                ('#:cargo-inputs (("rust-intermediate-1" ('unquote rust-intermediate-1))
+                                  ("rust-intermediate-2" ('unquote rust-intermediate-2))
+                                  ("rust-leaf-alice" ('unquote rust-leaf-alice))
+                                  ("rust-leaf-bob" ('unquote rust-leaf-bob))))))
+              ('home-page "http://example.com")
+              ('synopsis "summary")
+              ('description "summary")
+              ('license ('list 'license:expat 'license:asl2.0))))
+           #t)
+          (x
+           (pk 'fail x #f)))))
+
 (test-end "crate")
diff --git a/tests/gem.scm b/tests/gem.scm
index a12edb294c..01ae8a4470 100644
--- a/tests/gem.scm
+++ b/tests/gem.scm
@@ -24,7 +24,6 @@ 
   #:use-module (gcrypt hash)
   #:use-module (guix tests)
   #:use-module ((guix build utils) #:select (delete-file-recursively))
-  #:use-module (srfi srfi-41)
   #:use-module (srfi srfi-64)
   #:use-module (ice-9 match))
 
@@ -121,27 +120,8 @@ 
               (values (open-input-string test-bundler-json)
                       (string-length test-bundler-json)))
              (_ (error "Unexpected URL: " url)))))
-        (match (stream->list (gem-recursive-import "foo"))
+        (match (gem-recursive-import "foo")
           ((('package
-              ('name "ruby-foo")
-              ('version "1.0.0")
-              ('source
-               ('origin
-                 ('method 'url-fetch)
-                 ('uri ('rubygems-uri "foo" '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")
-              ('home-page "https://example.com")
-              ('license ('list 'license:expat 'license:asl2.0)))
-            ('package
               ('name "ruby-bundler")
               ('version "1.14.2")
               ('source
@@ -173,6 +153,25 @@ 
               ('synopsis "Another cool gem")
               ('description "Another cool gem")
               ('home-page "https://example.com")
+              ('license ('list 'license:expat 'license:asl2.0)))
+            ('package
+              ('name "ruby-foo")
+              ('version "1.0.0")
+              ('source
+               ('origin
+                 ('method 'url-fetch)
+                 ('uri ('rubygems-uri "foo" '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")
+              ('home-page "https://example.com")
               ('license ('list 'license:expat 'license:asl2.0))))
            #t)
           (x
-- 
2.24.0