From unknown Thu Sep 18 18:06:23 2025 Content-Disposition: inline Content-Transfer-Encoding: quoted-printable MIME-Version: 1.0 X-Mailer: MIME-tools 5.509 (Entity 5.509) Content-Type: text/plain; charset=utf-8 From: bug#51021 <51021@debbugs.gnu.org> To: bug#51021 <51021@debbugs.gnu.org> Subject: Status: detect loops in module/package graph Reply-To: bug#51021 <51021@debbugs.gnu.org> Date: Fri, 19 Sep 2025 01:06:23 +0000 retitle 51021 detect loops in module/package graph reassign 51021 guix submitter 51021 raingloom severity 51021 normal thanks From debbugs-submit-bounces@debbugs.gnu.org Mon Oct 04 20:58:43 2021 Received: (at submit) by debbugs.gnu.org; 5 Oct 2021 00:58:43 +0000 Received: from localhost ([127.0.0.1]:38633 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1mXYn5-0000gZ-1u for submit@debbugs.gnu.org; Mon, 04 Oct 2021 20:58:43 -0400 Received: from lists.gnu.org ([209.51.188.17]:56882) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1mXYn0-0000gM-R8 for submit@debbugs.gnu.org; Mon, 04 Oct 2021 20:58:42 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:33328) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1mXYn0-0006eI-Fl for bug-guix@gnu.org; Mon, 04 Oct 2021 20:58:38 -0400 Received: from mx1.riseup.net ([198.252.153.129]:55980) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1mXYmy-0005e4-Gz for bug-guix@gnu.org; Mon, 04 Oct 2021 20:58:37 -0400 Received: from fews1.riseup.net (fews1-pn.riseup.net [10.0.1.83]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits) key-exchange X25519 server-signature RSA-PSS (2048 bits) server-digest SHA256 client-signature RSA-PSS (2048 bits) client-digest SHA256) (Client CN "mail.riseup.net", Issuer "R3" (not verified)) by mx1.riseup.net (Postfix) with ESMTPS id 4HNfN96BzZzF5gM for ; Mon, 4 Oct 2021 17:58:33 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/simple; d=riseup.net; s=squak; t=1633395513; bh=sZXakluQBwL1KQPw9e2eLLn3fzJbxvUC0GSmK8SMswo=; h=Date:From:To:Subject:From; b=GWJghdHGDmkljs/FYM9ZaWvLit8CJ2/+fcvo4+rUlpeXcbRa55SMYQjWjOO+dCSME JMj05sLbs1ptxJpdBzhs1b8EarLkWD7YUEDY2oxMEDA2zI1HTvPDZR4RbuKq0+6Hdb 5Th23l+Y2AT+CMa0XE2F7n9uWxS73GoK2KJ2MRys= X-Riseup-User-ID: F7591869400046647B7FEA5D331DF5110FD070526394F5567DCE9C2D71859D69 Received: from [127.0.0.1] (localhost [127.0.0.1]) by fews1.riseup.net (Postfix) with ESMTPSA id 4HNfN918xTz5w1x for ; Mon, 4 Oct 2021 17:58:32 -0700 (PDT) Date: Tue, 5 Oct 2021 02:58:19 +0200 From: raingloom To: Guix Bugs Subject: detect loops in module/package graph Message-ID: <20211005025819.3f7756d7@riseup.net> MIME-Version: 1.0 Content-Type: text/plain; charset=US-ASCII Content-Transfer-Encoding: 7bit Received-SPF: pass client-ip=198.252.153.129; envelope-from=raingloom@riseup.net; helo=mx1.riseup.net X-Spam_score_int: -27 X-Spam_score: -2.8 X-Spam_bar: -- X-Spam_report: (-2.8 / 5.0 requ) BAYES_00=-1.9, DKIM_SIGNED=0.1, DKIM_VALID=-0.1, DKIM_VALID_AU=-0.1, DKIM_VALID_EF=-0.1, RCVD_IN_DNSWL_LOW=-0.7, RCVD_IN_MSPIKE_H3=0.001, RCVD_IN_MSPIKE_WL=0.001, SPF_HELO_PASS=-0.001, SPF_PASS=-0.001 autolearn=ham autolearn_force=no X-Spam_action: no action X-Spam-Score: -1.4 (-) X-Debbugs-Envelope-To: submit X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -2.4 (--) I'll be short and blunt, currently it sucks big time whenever you have a loop in your packages. There is no indication other than Guix hanging forever without any output. I don't want to spend my time manually finding loops in graphs, computers are better at that. Sadly I don't know when I'll have time to implement this, so if someone knows of a solution, they should not hesitate with sending a patch and making all our lives easier. From debbugs-submit-bounces@debbugs.gnu.org Tue Oct 05 04:01:03 2021 Received: (at 51021) by debbugs.gnu.org; 5 Oct 2021 08:01:03 +0000 Received: from localhost ([127.0.0.1]:38966 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1mXfNj-0007Ks-UF for submit@debbugs.gnu.org; Tue, 05 Oct 2021 04:01:03 -0400 Received: from world.peace.net ([64.112.178.59]:34562) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1mXfNg-0007KY-3h for 51021@debbugs.gnu.org; Tue, 05 Oct 2021 04:00:59 -0400 Received: from mhw by world.peace.net with esmtpsa (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1mXfNZ-00063Q-65; Tue, 05 Oct 2021 04:00:49 -0400 From: Mark H Weaver To: raingloom , 51021@debbugs.gnu.org Subject: Re: bug#51021: detect loops in module/package graph In-Reply-To: <20211005025819.3f7756d7@riseup.net> References: <20211005025819.3f7756d7@riseup.net> Date: Tue, 05 Oct 2021 03:59:00 -0400 Message-ID: <87czojkilc.fsf@netris.org> MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Spam-Score: 1.8 (+) X-Spam-Report: Spam detection software, running on the system "debbugs.gnu.org", has NOT identified this incoming email as spam. The original message has been attached to this so you can view it or label similar future email. If you have any questions, see the administrator of that system for details. Content preview: Hi, raingloom writes: > I'll be short and blunt, currently it sucks big time whenever you have > a loop in your packages. Agreed. I've been concerned about this problem since the early days of Guix. See . Content analysis details: (1.8 points, 10.0 required) pts rule name description ---- ---------------------- -------------------------------------------------- -0.0 SPF_PASS SPF: sender matches SPF record 0.0 SPF_HELO_NONE SPF: HELO does not publish an SPF Record 1.8 LONGWORDS Long string of long words X-Debbugs-Envelope-To: 51021 X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: 0.8 (/) Hi, raingloom writes: > I'll be short and blunt, currently it sucks big time whenever you have > a loop in your packages. Agreed. I've been concerned about this problem since the early days of Guix. See . Back in August 2014, there was a strongly connected component (SCC) containing 51 package modules: (acl algebra attr avahi base curl cyrus-sasl dejagnu docbook doxygen fltk fontutils gcc gd gdb gettext ghostscript gl glib gnome gnupg gnutls graphviz groff gsasl gstreamer gtk iso-codes lesstif libcanberra linux lisp maths mit-krb5 mpi netpbm openldap pdf pulseaudio rrdtool shishi ssh tcl tcsh texinfo texlive valgrind web xiph xml xorg) Since then, that SCC has grown to 277 package modules: (acl admin aidc algebra apr aspell assembly astronomy attr audio augeas authentication autogen autotools avahi backup base bash bdw-gc bison bittorrent boost build-tools c calendar cdrom certs check cmake code compression cook cpio cpp crates-graphics crates-gtk crates-io cross-base crypto cryptsetup cups curl cyrus-sasl databases datastructures dav debian dejagnu dictionaries disk django djvu dns docbook docker documentation ebook ed elf emacs emacs-xyz enchant enlightenment fabric-management fcitx file-systems finance firmware flex fltk fonts fontutils freedesktop freeipmi ftp game-development gawk gcc gd gdb geo gettext ghostscript gimp gl glib gnome gnome-xyz gnu-doc gnunet gnupg gnuzilla golang gpodder gps graphics graphviz groff groovy gsasl gstreamer gtk guile guile-xyz gv haskell haskell-apps haskell-check haskell-crypto haskell-web haskell-xyz hurd ibus icu4c image image-processing imagemagick inkscape iso-codes java java-compression javascript jemalloc jupyter kde kde-frameworks kde-internet kde-pim kde-plasma kerberos language less lesstif libcanberra libedit libevent libffi libftdi libidn libphidget libreoffice libunistring libusb linphone linux lirc lisp lisp-xyz llvm logging lsof lua mail man markup maths matrix maven maven-parent-pom mcrypt mes messaging mingw monitoring mono mp3 mpd mpi multiprecision music nano ncurses netpbm nettle networking nfs ninja node noweb nss ocaml ocr onc-rpc openbox opencl openldap openstack package-management parallel password-utils patchutils pciutils pcre pdf perl perl-check perl-compression perl-maths perl-web photo php plotutils polkit popt pretty-print protobuf pulseaudio python python-check python-compression python-crypto python-science python-web python-xyz qt rails rdesktop rdf readline rpc rrdtool rsync ruby rust rust-apps samba scanner scheme screen sdl search security-token selinux serialization shells slang speech sphinx spice sqlite ssh sssd suckless swig sync tcl telephony terminals tex texinfo text-editors textutils time tls tor uml upnp valgrind version-control video vim virtualization vpn vulkan w3m web web-browsers webkit wget wine wordnet wxwidgets xdisorg xfig xiph xml xorg) There's also a second, much smaller SCC: (bioconductor bioinformatics cran graph machine-learning statistics) > I don't want to spend my time manually finding loops in graphs, > computers are better at that. > > Sadly I don't know when I'll have time to implement this, so if someone > knows of a solution, they should not hesitate with sending a patch and > making all our lives easier. I've attached a script that I hacked up in 2014 to analyze the Guix package module dependency graph. Note the (chdir "gnu/packages") in the middle of it, so it must be loaded from the top directory of the Guix source code, and the REPL will be in "gnu/packages" after loading it. Here's an example of its use: --8<---------------cut here---------------start------------->8--- mhw@jojen ~/guix$ guile -l cycle-viewer.scm Found the following non-trivial strongly-connected components: (bioconductor bioinformatics cran graph statistics machine-learning) (autotools perl base [=E2=80=A6 272 lines elided =E2=80=A6] libftdi perl-maths) GNU Guile 3.0.2 Copyright (C) 1995-2020 Free Software Foundation, Inc. Guile comes with ABSOLUTELY NO WARRANTY; for details type `,show w'. This program is free software, and you are welcome to redistribute it under certain conditions; type `,show c' for details. Enter `,help' for help. scheme@(guile-user)> (length non-trivial-sccs) $1 =3D 2 scheme@(guile-user)> (map length non-trivial-sccs) $2 =3D (6 277) scheme@(guile-user)> (first non-trivial-sccs) $3 =3D (bioconductor bioinformatics cran graph statistics machine-learning) scheme@(guile-user)> (second non-trivial-sccs) $4 =3D (autotools perl base acl attr gettext check bash compression =E2=80= =A6) scheme@(guile-user)> ,pp (edges-within (first non-trivial-sccs)) $5 =3D ((bioconductor . statistics) (bioconductor . graph) (bioconductor . cran) (bioconductor . bioinformatics) (bioinformatics . statistics) (bioinformatics . machine-learning) (bioinformatics . graph) (bioinformatics . cran) (bioinformatics . bioconductor) (cran . statistics) (cran . machine-learning) (cran . graph) (cran . bioinformatics) (graph . statistics) (graph . cran) (graph . bioinformatics) (graph . bioconductor) (machine-learning . statistics) (machine-learning . cran) (statistics . machine-learning) (statistics . cran)) scheme@(guile-user)> (with-output-to-file "/tmp/BIO-SCC.dot" (lambda () (wr= ite-scc-dot (first non-trivial-sccs)))) scheme@(guile-user)> (with-output-to-file "/tmp/MAIN-SCC.dot" (lambda () (w= rite-scc-dot (second non-trivial-sccs)))) scheme@(guile-user)> ,quit --8<---------------cut here---------------end--------------->8--- If someone would like to polish this into a more usable tool, and possibly integrate it into Guix, please feel free. Mark --=20 Disinformation flourishes because many people care deeply about injustice but very few check the facts. Ask me about . From debbugs-submit-bounces@debbugs.gnu.org Tue Oct 05 04:05:21 2021 Received: (at 51021) by debbugs.gnu.org; 5 Oct 2021 08:05:21 +0000 Received: from localhost ([127.0.0.1]:38980 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1mXfRw-0007SP-GU for submit@debbugs.gnu.org; Tue, 05 Oct 2021 04:05:20 -0400 Received: from world.peace.net ([64.112.178.59]:34568) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1mXfRu-0007SA-QU for 51021@debbugs.gnu.org; Tue, 05 Oct 2021 04:05:19 -0400 Received: from mhw by world.peace.net with esmtpsa (TLS1.3:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.92) (envelope-from ) id 1mXfRo-0006MY-BZ; Tue, 05 Oct 2021 04:05:12 -0400 From: Mark H Weaver To: raingloom , 51021@debbugs.gnu.org Subject: Re: bug#51021: detect loops in module/package graph In-Reply-To: <87czojkilc.fsf@netris.org> References: <20211005025819.3f7756d7@riseup.net> <87czojkilc.fsf@netris.org> Date: Tue, 05 Oct 2021 04:03:24 -0400 Message-ID: <87a6jnkie0.fsf@netris.org> MIME-Version: 1.0 Content-Type: multipart/mixed; boundary="=-=-=" X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: 51021 X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.0 (-) --=-=-= Content-Type: text/plain Earlier, I wrote > I've attached a script that I hacked up in 2014 to analyze the Guix > package module dependency graph. Here's the script: --=-=-= Content-Type: text/plain Content-Disposition: inline; filename=cycle-viewer.scm Content-Description: cycle-viewer.scm ;;; cycle-viewer.scm: a Guix package module dependency graph analyzer ;;; Copyright (C) 2014 Mark H Weaver ;;; ;;; This program is free software: you can redistribute it and/or modify ;;; it under the terms of the GNU General Public License as published by ;;; the Free Software Foundation, either version 3 of the License, or ;;; (at your option) any later version. ;;; ;;; This program is distributed in the hope that it will be useful, ;;; but WITHOUT ANY WARRANTY; without even the implied warranty of ;;; MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the ;;; GNU General Public License for more details. ;;; ;;; You should have received a copy of the GNU General Public License ;;; along with this program. If not, see . (use-modules (srfi srfi-1) (srfi srfi-26) (ice-9 match) (ice-9 ftw) (ice-9 pretty-print)) ;;; ;;; Tarjan's strongly connected components algorithm ;;; ;;; Robert Tarjan, Depth-first search and linear graph algorithms. ;;; SIAM Journal on Computing, 1(2):146-160, 1972. ;;; ;;; ;;; vertices is the list of vertices, which may be any objects that ;;; can be distinguished using 'equal?'. ;;; ;;; edges is the list of edges, where each edge is a pair (w . v) ;;; representing the directed edge w => v, for vertices w and v. ;;; ;;; The return value is a list of the strongly-connected components, ;;; where each strongly-connected component (SCC) is represented as a ;;; list of the vertices it contains. The returned SCCs are sorted in ;;; topological order. ;;; (define (strongly-connected-components vertices edges) (define size (length vertices)) (define vs (iota size)) (define lookup (let ((t (make-hash-table size))) (for-each (cut hash-set! t <> <>) vertices vs) (cut hash-ref t <>))) (define name (let ((t (make-vector size #f))) (for-each (cut vector-set! t <> <>) vs vertices) (cut vector-ref t <>))) (define (vector-update! v i f) (vector-set! v i (f (vector-ref v i)))) (define (compose f g) (lambda (x) (f (g x)))) (define successors (let ((t (make-vector size '()))) (for-each (lambda (v w) (vector-update! t v (cut cons w <>))) (map (compose lookup car) edges) (map (compose lookup cdr) edges)) (cut vector-ref t <>))) (define new-index (let ((i -1)) (lambda () (set! i (+ i 1)) i))) (define index-table (make-vector size #f)) (define index (cut vector-ref index-table <>)) (define set-index! (cut vector-set! index-table <> <>)) (define lowlink-table (make-vector size size)) (define lowlink (cut vector-ref lowlink-table <>)) (define (update-lowlink! v x) (if v (vector-update! lowlink-table v (cut min x <>)))) (define done-table (make-bitvector size #f)) (define done? (cut bitvector-ref done-table <>)) (define done! (cut bitvector-set! done-table <> #t)) (define results '()) (define pending '()) (define (finalize! v) (let loop ((names '()) (p pending)) (done! (car p)) (cond ((eqv? v (car p)) (set! pending (cdr p)) (set! results (cons (cons (name v) names) results))) (else (loop (cons (name (car p)) names) (cdr p)))))) (let loop ((v #f) (ws vs) (stack '())) (cond ((pair? ws) (let ((w (car ws))) (cond ((index w) => (lambda (wi) (if (not (done? w)) (update-lowlink! v wi)) (loop v (cdr ws) stack))) (else (let ((wi (new-index))) (set-index! w wi) (update-lowlink! w wi) (set! pending (cons w pending)) (loop w (successors w) (cons (cons v (cdr ws)) stack))))))) ((pair? stack) (if (and v (= (index v) (lowlink v))) (finalize! v)) (update-lowlink! (caar stack) (lowlink v)) (loop (caar stack) (cdar stack) (cdr stack))) (else results)))) (chdir "gnu/packages") (define files (scandir "." (cut string-suffix? ".scm" <>))) (define headers (map (cut call-with-input-file <> read) files)) (define modules (filter-map (lambda (header) (match header (('define-module ('gnu 'packages name) . _) name) (('define-module module-name . _) (format (current-warning-port) "Warning: found unexpected module name ~S in gnu/packages/*.scm~%" module-name) #f))) headers)) (define dependencies (append-map (lambda (header) (match header (('define-module ('gnu 'packages module) . rest) (let loop ((rest rest) (deps '())) (match rest (() deps) ((#:use-module ('gnu 'packages name) . rest) (loop rest `((,module . ,name) . ,deps))) ((#:use-module (('gnu 'packages name) . _) . rest) (loop rest `((,module . ,name) . ,deps))) ((#:use-module _ . rest) (loop rest deps)) ((#:export _ . rest) (loop rest deps)) ((#:autoload _ _ . rest) (loop rest deps))))) (('define-module module-name . _) '()))) headers)) (define sccs (strongly-connected-components modules dependencies)) (define (non-trivial? scc) (not (= 1 (length scc)))) (define non-trivial-sccs (filter non-trivial? sccs)) (unless (null? non-trivial-sccs) (display "Found the following non-trivial strongly-connected components:") (newline) (for-each (lambda (scc) (pretty-print scc) (newline)) non-trivial-sccs)) (define (edges-within vs) (filter (match-lambda ((a . b) (and (member a vs) (member b vs)))) dependencies)) (define (edges-involving vs) (filter (match-lambda ((a . b) (or (member a vs) (member b vs)))) dependencies)) (define (edges-from vs) (filter (match-lambda ((a . b) (member a vs))) dependencies)) (define (edges-to vs) (filter (match-lambda ((a . b) (member b vs))) dependencies)) (define (module-label module) (symbol->string module)) (define* (write-edges-dot edges #:optional (port (current-output-port))) (display "digraph {\n" port) (for-each (match-lambda ((a . b) (format port " ~S -> ~S;\n" (module-label a) (module-label b)))) edges) (display "}\n" port)) (define* (write-scc-dot scc #:optional (port (current-output-port))) (write-edges-dot (edges-within scc) port)) --=-=-= Content-Type: text/plain -- Disinformation flourishes because many people care deeply about injustice but very few check the facts. Ask me about . --=-=-=-- From debbugs-submit-bounces@debbugs.gnu.org Thu Oct 07 09:28:58 2021 Received: (at 51021) by debbugs.gnu.org; 7 Oct 2021 13:28:58 +0000 Received: from localhost ([127.0.0.1]:46431 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1mYTSE-0001yl-0D for submit@debbugs.gnu.org; Thu, 07 Oct 2021 09:28:58 -0400 Received: from eggs.gnu.org ([209.51.188.92]:59620) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1mYTSB-0001yV-NO for 51021@debbugs.gnu.org; Thu, 07 Oct 2021 09:28:56 -0400 Received: from fencepost.gnu.org ([2001:470:142:3::e]:36584) by eggs.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1mYTS6-0001g1-0K; Thu, 07 Oct 2021 09:28:50 -0400 Received: from 91-160-117-201.subs.proxad.net ([91.160.117.201]:59174 helo=ribbon) by fencepost.gnu.org with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1mYTS5-0004ex-N8; Thu, 07 Oct 2021 09:28:49 -0400 From: =?utf-8?Q?Ludovic_Court=C3=A8s?= To: Mark H Weaver Subject: Re: bug#51021: detect loops in module/package graph References: <20211005025819.3f7756d7@riseup.net> <87czojkilc.fsf@netris.org> Date: Thu, 07 Oct 2021 15:28:48 +0200 In-Reply-To: <87czojkilc.fsf@netris.org> (Mark H. Weaver's message of "Tue, 05 Oct 2021 03:59:00 -0400") Message-ID: <87o881c6b3.fsf@gnu.org> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.2 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 51021 Cc: 51021@debbugs.gnu.org, raingloom X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) Hi Mark, Mark H Weaver skribis: > raingloom writes: >> I'll be short and blunt, currently it sucks big time whenever you have >> a loop in your packages. > > Agreed. I've been concerned about this problem since the early days of > Guix. See . > > Back in August 2014, there was a strongly connected component (SCC) > containing 51 package modules: Thanks for the analysis and for the updated patch! Module cycles are something we allow and even rely on, so finding cycles in itself is not necessarily helpful. What would help is finding cyclic top-level references, which are those that cause problems, but that=E2=80= =99s another story. WDYT? Now, I=E2=80=99m not sure if raingloom was talking about these cycles, or r= ather about cycles in the package dependency graph? Chris Baines proposed a patch a while back to report those, though I can=E2=80=99t find it anymore. IIRC, the difficulty was in making sure cyc= le detection would not be too expensive, and in keeping a readable style. Thanks, Ludo=E2=80=99. From debbugs-submit-bounces@debbugs.gnu.org Mon Oct 11 03:49:22 2021 Received: (at 51021) by debbugs.gnu.org; 11 Oct 2021 07:49:22 +0000 Received: from localhost ([127.0.0.1]:56318 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1mZq3m-0004pp-4U for submit@debbugs.gnu.org; Mon, 11 Oct 2021 03:49:22 -0400 Received: from mail-qv1-f43.google.com ([209.85.219.43]:33449) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1mZq3g-0004pX-Vj for 51021@debbugs.gnu.org; Mon, 11 Oct 2021 03:49:20 -0400 Received: by mail-qv1-f43.google.com with SMTP id u27so1416296qve.0 for <51021@debbugs.gnu.org>; Mon, 11 Oct 2021 00:49:16 -0700 (PDT) DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=gmail.com; s=20210112; h=mime-version:references:in-reply-to:from:date:message-id:subject:to :cc:content-transfer-encoding; bh=tpOMivpvA7Vi9p2bmb7aqCL/DbOwkZufyEOIDdEvJt0=; b=LKvVNB6S1AQKwuGuW1y7919NZKgd/Is7/ThKgV32eeroUTN4VdOSTL7agarD6niaFr +K4pvy4Rqeg8f33aQgMZPqG/jJOE/hbTzssgqgtPBn0wuRH02YICFTd+84nz6c0sWlN8 +9Our8ILWrz8k8q1P71TK1wE8MSxsIGFTmpexPva/L6Y3vcIseYsIBJ5f0e52tzX5fcb E9lkKr+C9caNkdoOE6lLZIhstHPoMC4pdmUbzim431CdCQxHxe/OdG75wrqpkjwH3VJE 3BHl8PEEQlwqUYuBo0rcw213vdAB2w/chLlJZbQRpMIIuSRp4d0wzlsTPsV1xv6epNDg PDig== X-Google-DKIM-Signature: v=1; a=rsa-sha256; c=relaxed/relaxed; d=1e100.net; s=20210112; h=x-gm-message-state:mime-version:references:in-reply-to:from:date :message-id:subject:to:cc:content-transfer-encoding; bh=tpOMivpvA7Vi9p2bmb7aqCL/DbOwkZufyEOIDdEvJt0=; b=wrOoEjAJrf76j56b4IKDXIg1MhsRrs9ooLFZSlKinRxs2Z3/iLgHPGOYZ3nVzmipt1 ff3abdgWWspTR8Ts0ss4SURfE2ibCvPl29Ldc/es7UKMZiEpaefuwzPF0aar9r8C96YQ /C5n/KKGmTA4I8X0R2V8yOXWJDWdaB3hWp/HoOjF6d4yfmQDOmYRZDljc55EzxVCSC5P O3sJ4tM9rFm/fevN5ba2r3Dbd3rz4SvAq+gsibvyFogh23V/Ckrp718oNE29aB3xj414 yv2H5uQMt8pVQQcc9xwTOZKJ189lYd7J6/mDq6toUxG+S0mWyu6T15cqnp85vCuM8W4G Yb8g== X-Gm-Message-State: AOAM532V2/CP+8hEjnMF4/PIbNk96CgvIEQV1ypRJQ3tqbwm7Wxd5Efp +t/sDbtG4oZuWY31YcWBT3DAWOmjxvgXYiXVeaU= X-Google-Smtp-Source: ABdhPJxDpWQ/Or3kn9H1SCzRls3VN9lm9e3IIrR3QCi1gaE1/xpC7ay4yhKG1uDDXPr/UswtdBg29okTvW1Mhyj8KG8= X-Received: by 2002:ad4:5f48:: with SMTP id p8mr21723072qvg.39.1633938551470; Mon, 11 Oct 2021 00:49:11 -0700 (PDT) MIME-Version: 1.0 References: <20211005025819.3f7756d7@riseup.net> <87czojkilc.fsf@netris.org> <87o881c6b3.fsf@gnu.org> In-Reply-To: <87o881c6b3.fsf@gnu.org> From: zimoun Date: Mon, 11 Oct 2021 09:49:00 +0200 Message-ID: Subject: Re: bug#51021: detect loops in module/package graph To: =?UTF-8?Q?Ludovic_Court=C3=A8s?= Content-Type: text/plain; charset="UTF-8" Content-Transfer-Encoding: quoted-printable X-Spam-Score: 0.0 (/) X-Debbugs-Envelope-To: 51021 Cc: Mark H Weaver , 51021@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -1.0 (-) Hi Ludo, On Thu, 7 Oct 2021 at 15:34, Ludovic Court=C3=A8s wrote: > Mark H Weaver skribis: > > raingloom writes: > >> I'll be short and blunt, currently it sucks big time whenever you have > >> a loop in your packages. > > > > Agreed. I've been concerned about this problem since the early days of > > Guix. See . > > > > Back in August 2014, there was a strongly connected component (SCC) > > containing 51 package modules: > > Thanks for the analysis and for the updated patch! > > Module cycles are something we allow and even rely on, so finding cycles > in itself is not necessarily helpful. What would help is finding cyclic > top-level references, which are those that cause problems, but that=E2=80= =99s > another story. What Mark had implemented [1] works for any directed graph. What do you mean by "top-level references"? 1: > Now, I=E2=80=99m not sure if raingloom was talking about these cycles, or= rather > about cycles in the package dependency graph? Probably. ;-) But the way to detect cycle could be applied to any graph that Guix uses. For instance, something totally irrelevant that I would never think of: channels [2]. :-) 2: > Chris Baines proposed a patch a while back to report those, though I > can=E2=80=99t find it anymore. IIRC, the difficulty was in making sure c= ycle > detection would not be too expensive, and in keeping a readable style. >From my memories about Graph Theory, the algorithm Mark is proposing is an efficient way to detect cycles (cycle is strong connected component). BTW, detect cycle is (almost) the same complexity as topological sort; since cycles are obstacle for topological sort to exist, somehow. I remember too the Chris's proposal but I do not remember what they implemented. I do not understand what you mean by "keeping a readable style". All the best, simon From debbugs-submit-bounces@debbugs.gnu.org Tue Oct 12 05:47:50 2021 Received: (at 51021) by debbugs.gnu.org; 12 Oct 2021 09:47:50 +0000 Received: from localhost ([127.0.0.1]:33526 helo=debbugs.gnu.org) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1maENy-0000uB-48 for submit@debbugs.gnu.org; Tue, 12 Oct 2021 05:47:50 -0400 Received: from eggs.gnu.org ([209.51.188.92]:43234) by debbugs.gnu.org with esmtp (Exim 4.84_2) (envelope-from ) id 1maENx-0000th-E7 for 51021@debbugs.gnu.org; Tue, 12 Oct 2021 05:47:49 -0400 Received: from fencepost.gnu.org ([2001:470:142:3::e]:59932) by eggs.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1maENr-00009w-M3; Tue, 12 Oct 2021 05:47:43 -0400 Received: from [2001:660:6102:320:e120:2c8f:8909:cdfe] (port=50950 helo=ribbon) by fencepost.gnu.org with esmtpsa (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1maENo-0002bQ-L5; Tue, 12 Oct 2021 05:47:41 -0400 From: =?utf-8?Q?Ludovic_Court=C3=A8s?= To: zimoun Subject: Re: bug#51021: detect loops in module/package graph References: <20211005025819.3f7756d7@riseup.net> <87czojkilc.fsf@netris.org> <87o881c6b3.fsf@gnu.org> X-URL: http://www.fdn.fr/~lcourtes/ X-Revolutionary-Date: 21 =?utf-8?Q?Vend=C3=A9miaire?= an 230 de la =?utf-8?Q?R=C3=A9volution?= X-PGP-Key-ID: 0x090B11993D9AEBB5 X-PGP-Key: http://www.fdn.fr/~lcourtes/ludovic.asc X-PGP-Fingerprint: 3CE4 6455 8A84 FDC6 9DB4 0CFB 090B 1199 3D9A EBB5 X-OS: x86_64-pc-linux-gnu Date: Tue, 12 Oct 2021 11:47:39 +0200 In-Reply-To: (zimoun's message of "Mon, 11 Oct 2021 09:49:00 +0200") Message-ID: <87czoawp50.fsf@gnu.org> User-Agent: Gnus/5.13 (Gnus v5.13) Emacs/27.2 (gnu/linux) MIME-Version: 1.0 Content-Type: text/plain; charset=utf-8 Content-Transfer-Encoding: quoted-printable X-Spam-Score: -2.3 (--) X-Debbugs-Envelope-To: 51021 Cc: Mark H Weaver , 51021@debbugs.gnu.org X-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list List-Id: List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: debbugs-submit-bounces@debbugs.gnu.org Sender: "Debbugs-submit" X-Spam-Score: -3.3 (---) Hi, zimoun skribis: > What Mark had implemented [1] works for any directed graph. What do > you mean by "top-level references"? Reference to variables coming from one module of an SCC that appear at the top level of another module in the SCC. >> Chris Baines proposed a patch a while back to report those, though I >> can=E2=80=99t find it anymore. IIRC, the difficulty was in making sure = cycle >> detection would not be too expensive, and in keeping a readable style. > > From my memories about Graph Theory, the algorithm Mark is proposing > is an efficient way to detect cycles What I meant is that =E2=80=98package-derivation=E2=80=99 traverses the pac= kage graph, so it=E2=80=99s a natural place to add cycle detection. But since =E2=80=98package-derivation=E2=80=99 is so central, care must be = taken about the performance hit and about its readability. Thanks, Ludo=E2=80=99.