> On Monday 26 December 2005 21:28, Ciaran McCreesh wrote:
> > On Mon, 26 Dec 2005 21:09:31 +0100 Carsten Lohrke <[EMAIL PROTECTED]>
> > Well, any library that changes ABI should use a different SLOT for each
> > revision. So SLOT depends should be able to replace the need for = and
> > ~ and < and <= dependencies entirely. Which is a good thing, since
> > those atoms make dependency resolution a general-case unsolvable
> > problem.
There's a lot of "should"s that are "aren't"s in there, but in principle that
is a very elegant idea.
On Wednesday 28 December 2005 00:48, Paul de Vrieze wrote:
> Well, it shouldn't be unsolvable. Choosing can be done with the following
> process:
>
> - Get the list of packages with the requested name.
> - Sort the list from the newest version, to the oldest.
> - Iterate over the packages:
> - Apply all restrictions on the package (including exclusions). If the
> package satisfies all, test it's dependencies recursively.
^^^ This step fails. When the set of restrictions cannot be resolved,
you need to backtrack and try a lesser version of a previous
package hence the set of "all restrictions" is constantly in flux.
> - If all dependencies match, this package matches the dependency.
> Continue with the next depend atom.
> - If no match, iterate the next package.
If backtracking was all there was to it, it could be done very quickly of
course. However, it's essentially a brute force method; I'm not very good
with O notation but I think it's O(n^n). I've got an algorithm in my head
that'll do it but it goes into an infinite loop in the cases that Carsten
mentioned. That's why things are taking so long. I should really write it
down...
</plea for help?>
--
Jason Stubbs
--
gentoo-dev@gentoo.org mailing list
