On Feb 1, 2011, at 2:13 PM, Jeff Johnson wrote:
>
> Just FYI: The eventual "forward" looking solution @rpm5.org is gonna
> be to just scrap rpmtsOrder() and replace with an incremental topological
> sort done as a side effect of adding an install/erase package to a
> transaction, and with LOOP detection and other problems available
> immediately, not when a depsolver chooses to call rpmtsOrder().
> But that will take some time/care to implement, nooone frigging cares
> about RPM as long as RPM Just Works. Ditto rpmtsCheck(), which
> also needs to be done incrementally as a side effect of adding an
> install/erase
> element, not as a distinguished method. So rpmtsCHeck() is also destined
> to be scrapped, just like rpmtsOrder(), @rpm5.org.
>
I should perhaps state clearly what the problem is, its very not obvious.
The existing implementation of topological sort (straight from Knuth v1 p271),
and the existing LOOP adjusting (also from Knuth in a worked problem) is
perfectly OK.
The problem is -- that no matter what "priority" scheme one chooses --
is that the LOOP detection occurs only when the algorithm stalls.
One cannot fix anything by introducing additional heuristics in zapRelation()
with RPMSENSE_FOO contextual markers or any other heuristic one chooses.
IT'S ALREADY TOO LATE TO FIX ANYTHING WHEN zapRelation() IS CALLED.
(apologies for YELLING ;-)
That is why an incremental approach (my @rpm5.org choice) or LOOP removal first
(the @rpm.org Tarjan choice) is needed. No amount of additional heuristics
and bells and whistles will ever solve the fundamental design flaw:
Knuth's topological sort undertakes LOOP removal only
when the one-degree-of-freedom queue runs to empty but
there are additional packages to be ordered.
This is the fundamental semantic issue that leads to packages being
ordered too late for "real world" distro usage cases.
hth
73 de Jeff
______________________________________________________________________
RPM Package Manager http://rpm5.org
Developer Communication List rpm-devel@rpm5.org
