Re: [gentoo-dev] Multiple Repo Support

[Jason Stubbs]

> On Monday 26 December 2005 21:28, Ciaran McCreesh wrote:
> > On Mon, 26 Dec 2005 21:09:31 +0100 Carsten Lohrke <carlo@g.o>
> > 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@g.o mailing list