On Feb 1, 2011, at 12:46 PM, Per Øyvind Karlsen wrote:
> I've tried to make a first attempt at resolving dependency loops using
> the specific dependency type as hint for ordering.
>
> The patch attached will try attempt resolving the loops by removing
> one kind of dependency type (based on what seems likely to be the
> most important kind of dependency wrt. ordering, correctness is
> probably not 100% here), then rescanning for still existing loops,
> then remove next kind of dependency, then rescan and on...
>
The mathematics of topological sort need to be studied first imho.
Knuth V1 pg 271 (iirc). Truly its a simple algorithm.
You have one degree of freedom which you are gonna attempt to
use as "priority". That's perfectly OK, just there's ate least
4-5 other competing implementations to use that same one
degree of freedom available in a topological sort.
> Dunno if this seems like a sane enough approach or not (or whether
> implemented in the correct place or not), but it seems like a step in
> the right direction at least. :)
>
> WDYT?
>
I think you're crazy attempting prioritized package ordering. ;-)
But let's back up and get the design goals in place.
Can you state in words what you are trying to achieve first? The above
is a healthy start, but your "priority" needs to be integrated with the
other details which include:
using the no. of incoming edges as "priority"
synthesizing "install-before-erase" as an implicitly added tsort
relation
augmenting existing package dependencies with parentdir/linkto relations
The parentdir/linkto dependencies are already a DAG as in a set of
relations that have no LOOP:'s. Yes there's the slim possibility that
linktos can loop just like symlinks can. But the incidence of symlink
induced LOOP's is vanishingly small when compared to the number of
LOOP's that Mandriva is *deliberately* adding to *.rpm packaging.
I dunno and don't care what your patch does yet. I'm sure
the patch does something reasonable. But until I hear more aboute
what problem you are trying to solve and the goals of the patch, I
haven't really a clue ...
73 de Jeff
______________________________________________________________________
RPM Package Manager http://rpm5.org
Developer Communication List rpm-devel@rpm5.org
