Re: toppological sorting and datastructures
Hi,
>>"Jason" == Jason Gunthorpe <jgg@gpu.srv.ualberta.ca> writes:
Jason> This is unbelivably simple to code! You don't need any lists
Jason> but a single package extension structure containg the colour of
Jason> the package. It's also amazingly fast, the only loop is the
Jason> main one. The other one requires a reverse depends lookup,
Jason> which requires iterating over all packages depending on the
Jason> package, even if it is not a cand.
But please note, each package has to have, in the relations
list, any package that needs to be acted on before it. That includes,
for installation:
a) Anything we predepend on (simple)
b) Anything we depend on (simple)
c) Packages we conflict and replace, which have to be removed before
we are installed. Requires a special case when building dependency
lists, but still simple.
d) packages that recommend us (*) reverse dependency, and should be
marked as a weak link, so that it may be traversed last.
e) Packages that suggest us (*) reverse dependency
This may require 3 passes over the list, one for normal relations,
one for recommends, and one for suggests, which are weaker still.
Or we may take care while building the list, at the cost of
two extra pointers in the linked list header. Normal relatios
are always inserted at the head of the list. Suggests are
always inserted at the tail. recommends are always inserted at
the "middle" pointer, so the ordering on the list is what we
desire.
For removals (this seems simpler, we ignore recommends and suggest?)
a) packages that pre-depend on us (what if they are not marked for
removal?) (*) reverse dependency
b) Packages that depend on us (*) reverse dependency
Jason> However, it's recursive, will the depth cause a problem for us?
Jason> I suppose I should go and calculate the worst case depth of the
Jason> routine (tomorrow I'll write a stats report into dpkg-cache)
From my pkg-order work, it is rare to find a depth worse than
6 in most cases, I have once seen a 10. Most of the dependencies are
on a small number of packages (libc, for example), and once those
nodes are painted black, they are ignored.
>> Provides should satisfy any non versioned dependency (I think
>> provides should only provide virtual packages, but I'm not sure
>> this is ever required anywhere)
Jason> Um, we are implementing enhanced provides, they have versions
Jason> and can match versioned depends with the 'provides'
Jason> version. Tom wants this.
Jason> I guess a provided targeted depends simply effects more than
Jason> one package.
Hmmm. If we implement this, then provides become closer to
first class citizens (less special cases required), but if we don't
parse the versions on provided packages, then they should never match
a versioned relationship. This shall have to have a special case in
dependency determination code.
It is not clear to me how one can actually implement versioned
provides. Take gawk and mawk, which both provide awk. What version to
apply to awk? It'll have to have a policy decicion, and the virtual
package list should also list current versions of all virtual
packages, and the criteria for bumping up a version number. (gawk's
awk can do foo -- so it can provide awk 1.1, mawk still provides awk
1.0) If both awks diverge, we run into problems. If mawk now provides
feature bar, should it get 1.01? or 1.2?
Anyway, I don't have to deal with that right now.
manoj
--
Delta: We're Amtrak with wings. David Letterman
Manoj Srivastava <srivasta@acm.org> <http://www.datasync.com/%7Esrivasta/>
Key C7261095 fingerprint = CB D9 F4 12 68 07 E4 05 CC 2D 27 12 1D F5 E8 6E
Reply to: