Re: [gentoo-portage-dev] building dependency tree

[Pieter Van den Abeele <pvdabeel@gentoo.org>]

On 12 May 2004, at 05:02, Andrew Gaffney wrote:

> and then the list of packages to emerge

A topological ordering on the relevant digraph.

The relevant digraph as computed by portage is a 'tree' (note: cycles 
filtered) which is created by performing a (series of) walk(s) in the 
graph (portage "tree"). Dependencies = edges, for each ebuild there are 
2^n (where n = number of USE flags in the ebuilds IUSE) choice nodes in 
the graph.

I believe a DFS and BFS strategy have been suggested for the walk on 
this list, each having their own advantages and disadvantages. The main 
issue with the search strategy used by portage is that the runtime 
complexity explodes when you try to implement stuff like 'package foo 
conflicts with package bar' (the best we can do is without causing the 
explosion is: package foo version X conflicts with package foo version 
Y (same package - different version - 'slot' functionality). Of course 
there are solutions to this problem, but those fall outside the scope 
of your question :-)

Best regards,

Pieter Van den Abeele


--
gentoo-portage-dev@gentoo.org mailing list