From mboxrd@z Thu Jan 1 00:00:00 1970 Return-Path: Received: from mp2 ([2001:41d0:2:bcc0::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by ms0.migadu.com with LMTPS id sPSHANLsY2HZvQAAgWs5BA (envelope-from ) for ; Mon, 11 Oct 2021 09:50:42 +0200 Received: from aspmx1.migadu.com ([2001:41d0:2:bcc0::]) (using TLSv1.3 with cipher TLS_AES_256_GCM_SHA384 (256/256 bits)) by mp2 with LMTPS id WC8AN9HsY2GTFgAAB5/wlQ (envelope-from ) for ; Mon, 11 Oct 2021 07:50:41 +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 864973790C for ; Mon, 11 Oct 2021 09:50:41 +0200 (CEST) Received: from localhost ([::1]:38006 helo=lists1p.gnu.org) by lists.gnu.org with esmtp (Exim 4.90_1) (envelope-from ) id 1mZq51-0007fs-Kf for larch@yhetil.org; Mon, 11 Oct 2021 03:50:39 -0400 Received: from eggs.gnu.org ([2001:470:142:3::10]:42994) by lists.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_256_GCM_SHA384:256) (Exim 4.90_1) (envelope-from ) id 1mZq4Q-0007fi-Im for bug-guix@gnu.org; Mon, 11 Oct 2021 03:50:04 -0400 Received: from debbugs.gnu.org ([209.51.188.43]:44772) by eggs.gnu.org with esmtps (TLS1.2:ECDHE_RSA_AES_128_GCM_SHA256:128) (Exim 4.90_1) (envelope-from ) id 1mZq4Q-0005LF-9o for bug-guix@gnu.org; Mon, 11 Oct 2021 03:50:02 -0400 Received: from Debian-debbugs by debbugs.gnu.org with local (Exim 4.84_2) (envelope-from ) id 1mZq4P-0004qp-ST for bug-guix@gnu.org; Mon, 11 Oct 2021 03:50:01 -0400 X-Loop: help-debbugs@gnu.org Subject: bug#51021: detect loops in module/package graph Resent-From: zimoun Original-Sender: "Debbugs-submit" Resent-CC: bug-guix@gnu.org Resent-Date: Mon, 11 Oct 2021 07:50:01 +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: Ludovic =?UTF-8?Q?Court=C3=A8s?= Received: via spool by 51021-submit@debbugs.gnu.org id=B51021.163393856218593 (code B ref 51021); Mon, 11 Oct 2021 07:50:01 +0000 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: 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: , Cc: 51021@debbugs.gnu.org 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=1633938641; h=from:from:sender:sender:reply-to:subject:subject:date:date: message-id:message-id:to:to:cc: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:dkim-signature; bh=tpOMivpvA7Vi9p2bmb7aqCL/DbOwkZufyEOIDdEvJt0=; b=DEWA0tBoQ7BKWmW/yLWkXoOXr25zmO2yHL1CHGE3iAipCJ1OfDokAIMT1WPvnbZ3hS8pJk AESZ+4edFWKD6U+4WUr1BAzY17pUERWSvmoA/3ZDbs2OBXmNb+NBLI6mSzcYKz/H7Vcuny 01ImyMt+Ub2p8PvNVUrpUb4Sg+oqw4QawHRUJHpG46jlQlhNnTDgYmXTRQvMAiWKgoXcil QClV6psBPSA3GwrEYpwLqNJ8sA1KfCEpELIj2iDSUxLP6VUrAFZWzfavW+sfcXRcu5Fvl0 NhesKvP3qZYZnLFu/pVncYHme2wd62OPWdvd3gJdRXeDagZ/eC7pkvx4EcPUhQ== ARC-Seal: i=1; s=key1; d=yhetil.org; t=1633938641; a=rsa-sha256; cv=none; b=sg0Z71W8wL3nkjqdzLG34FGjjI74ed6viEkk4UjWCY/Grn+2HM4V+OLNnxKfMfxy8XoFAn 1ImvC37x/c2G+PzShQD7aEerw/lcrdkBc+Gr36DHpiFOASpdnsrBJXTX77Ok4T3zmsQxOg KzSiA+6QjISpEFOKNrJQpyMwvVdIN4lMcxpwv1CNIM5MeFFenRQsuLXDvVqxIoLfopJMGF OEP6Stax56Sx/nW7jwUD9ybihYlkydgSP0GF1vfPtmA7hfld3wa4ur9bxJ9GFNeuM8BU52 lvzBlPylNG9j6xjbZxyOmxr5oz6f1Aq5sgY3gdhkHWGoYyQtFfUxN2aefJdApQ== ARC-Authentication-Results: i=1; aspmx1.migadu.com; dkim=fail ("headers rsa verify failed") header.d=gmail.com header.s=20210112 header.b=LKvVNB6S; dmarc=fail reason="SPF not aligned (relaxed)" header.from=gmail.com (policy=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: -1.71 Authentication-Results: aspmx1.migadu.com; dkim=fail ("headers rsa verify failed") header.d=gmail.com header.s=20210112 header.b=LKvVNB6S; dmarc=fail reason="SPF not aligned (relaxed)" header.from=gmail.com (policy=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: 864973790C X-Spam-Score: -1.71 X-Migadu-Scanner: scn1.migadu.com X-TUID: syHqjw+IB1F7 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