From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mp0 ([2001:41d0:2:bcc0::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by ms0.migadu.com with LMTPS id WHzZKacGXGFh3gAAgWs5BA (envelope-from ) for ; Tue, 05 Oct 2021 10:02:47 +0200 Received: from aspmx1.migadu.com ([2001:41d0:2:bcc0::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by mp0 with LMTPS id wC2hJacGXGH9FAAA1q6Kng (envelope-from ) for ; Tue, 05 Oct 2021 08:02:47 +0000 Received: from lists.gnu.org (lists.gnu.org [209.51.188.17]) (using TLSv1.2 with cipher ECDHE-RSA-AES256-GCM-SHA384 (256/256 bits)) (No client certificate requested) by aspmx1.migadu.com (Postfix) with ESMTPS id 258E212825 for ; Tue, 5 Oct 2021 10:02:47 +0200 (CEST) Received: from localhost ([::1]:39214 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1mXfPR-0000o3-CB for larch@yhetil.org; Tue, 05 Oct 2021 04:02:45 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:44352) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1mXfOl-0000na-6E for bug-guix@gnu.org; Tue, 05 Oct 2021 04:02:03 -0400 Received: from debbugs.gnu.org ([209.51.188.43]:55654) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1mXfOk-0000hn-QQ for bug-guix@gnu.org; Tue, 05 Oct 2021 04:02:02 -0400 Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1mXfOk-0007Mt-JJ for bug-guix@gnu.org; Tue, 05 Oct 2021 04:02:02 -0400 X-Loop: help-debbugs@gnu.org Subject: bug#51021: detect loops in module/package graph Resent-From: Mark H Weaver Original-Sender: "Debbugs-submit" Resent-CC: bug-guix@gnu.org Resent-Date: Tue, 05 Oct 2021 08:02:02 +0000 Resent-Message-ID: Resent-Sender: help-debbugs@gnu.org X-GNU-PR-Message: followup 51021 X-GNU-PR-Package: guix X-GNU-PR-Keywords: To: raingloom , 51021@debbugs.gnu.org Received: via spool by 51021-submit@debbugs.gnu.org id=B51021.163342086328237 (code B ref 51021); Tue, 05 Oct 2021 08:02:02 +0000 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 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-BeenThere: debbugs-submit@debbugs.gnu.org X-Mailman-Version: 2.1.18 Precedence: list X-BeenThere: bug-guix@gnu.org List-Id: Bug reports for GNU Guix List-Unsubscribe: , List-Archive: List-Post: List-Help: List-Subscribe: , Errors-To: bug-guix-bounces+larch=yhetil.org@gnu.org Sender: "bug-Guix" X-Migadu-Flow: FLOW_IN ARC-Message-Signature: i=1; a=rsa-sha256; c=relaxed/relaxed; d=yhetil.org; s=key1; t=1633420967; h=from:from:sender:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc:mime-version:mime-version: content-type:content-type: content-transfer-encoding:content-transfer-encoding:resent-cc: resent-from:resent-sender:resent-message-id:in-reply-to:in-reply-to: references:references:list-id:list-help:list-unsubscribe: list-subscribe:list-post; bh=sqF4vv7N48q2e4nOx9ErJeNiJQZq0j3U+0X6Dc7NK/E=; b=CK5T1Rnn8R9Lv5Muwmq+IO8W2+wnolN+FTWATMD9mWZne03zM27WihFzUD/BdjtPUDzHR+ DPhWedLeJ4AQlkbS56uhoaVV+8GLTzDXgS1QRpShVQ7Lf15lnRWvlKAVGY5DolmhLp636m 3Vj8FHrRldYuj6h69LqEZDa2lHGDaUWJ7R/Zbd1jQ8L9VKsUW29kLH2iunmRn5DmyHkhSq jRltVho333Oje0PXgdT40ptTlyWEOb2mnk/kigMMKXIIDaoAo/qxbNnATR6PGjJ5SqVjyG 7mZrvGkBcdwbMcCWSoWIoHNQx546BrngWa16XqE/w7WMSi/y2aPaB9IDbbYliw== ARC-Seal: i=1; s=key1; d=yhetil.org; t=1633420967; a=rsa-sha256; cv=none; b=qG4C1foFP96JXb84POJA5R4RB8vLwVg37phf5GjRkMnH/clMusaTtoR8QBbVkFMJELBekX tIHK5jJWgB3SAvD89oL3r9atuEwjG2urZeHlUTlR0CotACAytnWfZKxCnera6Ux3nt+trQ ZGeLI9QPxiKkdIj628c+iFZ1fooyUu8PskA27OrvrwfBSAZT8sT4eEp3jij1WZoxfNolK0 zUmX30Qf1c+3CK9DnosNdjBMwzgLJSRaDcYpzPGhTVE0kOi/QvqLGNAkiWrukjMHYctup+ +/EhwHTJmobrACCaNA5+ckqcOxOHqP+ZTTbFOv9bxB57s2dc5hgyNDkRndlEQw== ARC-Authentication-Results: i=1; aspmx1.migadu.com; dkim=none; spf=pass (aspmx1.migadu.com: domain of bug-guix-bounces@gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=bug-guix-bounces@gnu.org X-Migadu-Spam-Score: -2.81 Authentication-Results: aspmx1.migadu.com; dkim=none; dmarc=none; spf=pass (aspmx1.migadu.com: domain of bug-guix-bounces@gnu.org designates 209.51.188.17 as permitted sender) smtp.mailfrom=bug-guix-bounces@gnu.org X-Migadu-Queue-Id: 258E212825 X-Spam-Score: -2.81 X-Migadu-Scanner: scn1.migadu.com X-TUID: Hl1HnruyiLl8 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 .