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

[Brian Leung]

Hi Ludo,

> If that’s fine with you, I’d be willing to apply this patch, and then
> apply other bits of your patch (the tests and stream removal) on top of
> it.  How does that sound?

Sure, your patch seems clearer to me.

Thanks,

Brian

On Sun, Dec 8, 2019 at 9:09 AM Ludovic Courtès <address@hidden> wrote:

Hi Brian,

Thanks for the updated patch!

Brian Leung <address@hidden> skribis:

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

[...]

> +  (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))

I found this to be relatively complex (and part of this complexity was
already there before the patch) and quite different from the other
graph-walking procedures we have in different places, which got me
thinking why that is.

After a bit of researching and trying, I found that the attached patch
expresses the same thing, including topological sorting, in a hopefully
clearer way, or at least more consistent with other graph-walking
procedures in the code.  WDYT?

If that’s fine with you, I’d be willing to apply this patch, and then
apply other bits of your patch (the tests and stream removal) on top of
it.  How does that sound?

Returning a topologically-sorted set of packages means that nothing is
output until we’ve walked the whole dependency graph, so we indeed have
to get rid of streams.  I guess it’s a tradeoff.  Ricardo, how do you
feel about this change?

Thanks!

Ludo’.