| 1 |
On 12 May 2004, at 05:02, Andrew Gaffney wrote: |
| 2 |
|
| 3 |
> and then the list of packages to emerge |
| 4 |
|
| 5 |
A topological ordering on the relevant digraph. |
| 6 |
|
| 7 |
The relevant digraph as computed by portage is a 'tree' (note: cycles |
| 8 |
filtered) which is created by performing a (series of) walk(s) in the |
| 9 |
graph (portage "tree"). Dependencies = edges, for each ebuild there are |
| 10 |
2^n (where n = number of USE flags in the ebuilds IUSE) choice nodes in |
| 11 |
the graph. |
| 12 |
|
| 13 |
I believe a DFS and BFS strategy have been suggested for the walk on |
| 14 |
this list, each having their own advantages and disadvantages. The main |
| 15 |
issue with the search strategy used by portage is that the runtime |
| 16 |
complexity explodes when you try to implement stuff like 'package foo |
| 17 |
conflicts with package bar' (the best we can do is without causing the |
| 18 |
explosion is: package foo version X conflicts with package foo version |
| 19 |
Y (same package - different version - 'slot' functionality). Of course |
| 20 |
there are solutions to this problem, but those fall outside the scope |
| 21 |
of your question :-) |
| 22 |
|
| 23 |
Best regards, |
| 24 |
|
| 25 |
Pieter Van den Abeele |
| 26 |
|
| 27 |
|
| 28 |
-- |
| 29 |
gentoo-portage-dev@g.o mailing list |
Archives