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

Previous Next

Full log

Message #20 received at 37730 <at> debbugs.gnu.org (full text, mbox):

From: Brian Leung <bkleung89 <at> gmail.com>
To: Ludovic Courtès <ludo <at> gnu.org>
Subject: Re: [bug#37730] [PATCH] Topologically sort recursively-imported
 packages
Date: Sun, 8 Dec 2019 10:31:23 -0800

[Message part 1 (text/plain, inline)]

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 <ludo <at> gnu.org> wrote:

> Hi Brian,
>
> Thanks for the updated patch!
>
> Brian Leung <bkleung89 <at> gmail.com> skribis:
>
> > From 915274d493116d063bfe2a953a9e855b8312711e Mon Sep 17 00:00:00 2001
> > From: Brian Leung <leungbk <at> mailfence.com>
> > 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’.
>
>

[Message part 2 (text/html, inline)]

Previous Next

GNU bug tracking system
Copyright (C) 1999 Darren O. Benham, 1997,2003 nCipher Corporation Ltd, 1994-97 Ian Jackson.