bug#51021: detect loops in module/package graph

[zimoun <zimon.toutoune@gmail.com>]

Hi Ludo,

On Thu, 7 Oct 2021 at 15:34, Ludovic Courtès <ludo@gnu.org> wrote:
> Mark H Weaver <mhw@netris.org> skribis:
> > raingloom <raingloom@riseup.net> 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 <https://bugs.gnu.org/18247>.
> >
> > 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’s
> another story.

What Mark had implemented [1] works for any directed graph.  What do
you mean by "top-level references"?

1: <https://en.wikipedia.org/wiki/Tarjan%27s_strongly_connected_components_algorithm>

> Now, I’m 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: <http://issues.guix.gnu.org/issue/41069>

> Chris Baines proposed a patch a while back to report those, though I
> can’t 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 (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