From mboxrd@z Thu Jan 1 00:00:00 1970 Received: from eggs.gnu.org ([2001:470:142:3::10]:46722) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1iLOc7-0002XO-VP for guix-patches@gnu.org; Fri, 18 Oct 2019 05:32:05 -0400 Received: from Debian-exim by eggs.gnu.org with spam-scanned (Exim 4.71) (envelope-from ) id 1iLOc6-00074F-NS for guix-patches@gnu.org; Fri, 18 Oct 2019 05:32:03 -0400 Received: from debbugs.gnu.org ([209.51.188.43]:40563) by eggs.gnu.org with esmtps (TLS1.0:RSA_AES_128_CBC_SHA1:16) (Exim 4.71) (envelope-from ) id 1iLOc6-000749-K0 for guix-patches@gnu.org; Fri, 18 Oct 2019 05:32:02 -0400 Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1iLOc6-0003qF-Ee for guix-patches@gnu.org; Fri, 18 Oct 2019 05:32:02 -0400 Subject: [bug#37730] [PATCH] Topologically sort recursively-imported packages Resent-Message-ID: From: Ludovic =?UTF-8?Q?Court=C3=A8s?= References: Date: Fri, 18 Oct 2019 11:31:26 +0200 In-Reply-To: (Brian Leung's message of "Sun, 13 Oct 2019 00:37:59 -0700") Message-ID: <87lfti5rip.fsf@gnu.org> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: guix-patches-bounces+kyle=kyleam.com@gnu.org Sender: "Guix-patches" To: Brian Leung Cc: 37730@debbugs.gnu.org Hi Brian, Brian Leung skribis: > From 6fec6a72a7938753307ccf3b7bdad8bff72e47f9 Mon Sep 17 00:00:00 2001 > From: Brian Leung > Date: Fri, 11 Oct 2019 23:18:03 -0700 > Subject: [PATCH] guix: utils: Topologically sort recursively-imported rec= ipes. > > This output order, when it is well-defined, facilitates the process of > deciding what to upstream next for a package with a large dependency clos= ure. That=E2=80=99s a great idea! > * guix/import/utils.scm (recursive-import): Enforce topological sort. > Remove dependency on srfi-41. Reverse output here instead of in individ= ual > importers. > * guix/scripts/import/cran.scm (guix-import-cran): Unstreamify and don't > reverse here. Remove dependency on srfi-41. Instead of =E2=80=9CUnstreamify=E2=80=9D, please write precisely what has c= hanged, like =E2=80=9CRemove call to =E2=80=98stream-fold=E2=80=99 and call =E2=80=98foo= bar=E2=80=99 directly.=E2=80=9D, =E2=80=9CRemove call to =E2=80=98stream->list=E2=80=99.=E2=80=9D, 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 =E2=80=98match=E2=80=99 = instead of =E2=80=98cdr=E2=80=99 & 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=E2=80=99.