[bug#37730] [PATCH] Topologically sort recursively-imported packages

["Ludovic Courtès" <ludo@gnu.org>]

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’.