[pacman-dev] A WIP fix for removing unneeded dependency cycles

[Ashley Whetter]

This is a work in progress patchset. DO NOT MERGE!

I've been looking at a fix for FS#41031 [1].
What I've attempted to do in this prototype is to fix the issue without needing
to calculate the strongly connected components of the dependency graph
to see if I could improve on run time performance or memory consumption.

The way this works is I first perform depth-first cycle detection on the graph.
When a cycle is detected the list of packages in the cycle is added to the
removes list of each package in the cycle.
This marks a package as "in a cycle".
After this preprocessing step a package is determined as removable by
pretending that every other package in the cycle is being removed,
and then determining what or not the package itself is removable as normal.

My thinking from this prototype though is that it isn't as great a solution as
calculating the strongly connected components of the dependency graph.
Doing cycle detection this way means that dependency graphs with packages
belonging to more than one cycle aren't detected.
Although this is a crazy edge case, it's theoretically a potential graph,
and implementing Tarjan's strongly connected components algorithm instead
of the cycle detection used here shouldn't be much more work.
It can still use the removes array and the `_can_remove_cycle` method for
determining whether a cycle is removable;
only the preprocessing step would need to change.
The only way that I think calculating the strongly connected components could
be worse than this prototype is that it requires a list of every vertex in the
dependency graph.
This is easy enough to calculate with a breadth first search but it will use
more memory than simple cycle detection.

So I wanted to see what people's thoughts were on these two solutions and if
there was a preference to one or the other.

Ashley

[1] https://bugs.archlinux.org/task/41031