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

Previous Next

Full log

View this message in rfc822 format

From: Brian Leung <bkleung89 <at> gmail.com>
To: Ludovic Courtès <ludo <at> gnu.org>,  Efraim Flashner <efraim <at> flashner.co.il>
Subject: [bug#37730] [PATCH] Topologically sort recursively-imported packages
Date: Tue, 3 Dec 2019 15:06:51 -0800

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

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 <at> 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 <at> gnu.org> wrote:
>
>> Hi Brian,
>>
>> Brian Leung <bkleung89 <at> gmail.com> skribis:
>>
>> > From 6fec6a72a7938753307ccf3b7bdad8bff72e47f9 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.
>> >
>> > 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’.
>>
>

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

[0001-guix-utils-Topologically-sort-recursively-imported-r.patch (text/x-patch, attachment)]

Previous Next

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