On Mon, Feb 09, 2009 at 12:59:49PM +0100, kc.ubuntu...@centrum.cz was heard to
say:
> I would like to ask you a little bit controversal question. As a user I miss
> a package manager based on powerfull dependency solver. Using APT in
> DEB-based distributions, I can easilly create some kind of problem, APT is
> unable to solve. This is because the APT is the worst dependency solver
> almost ever invented. Proof can be found here:
The biggest problem with apt's dependency solver is that it can't
conceive of anything other than the current and candidate versions.
That alone renders it useless for anything but trivial circumstances.
Unfortunately, because it's all heuristic, you need to throw the
resolver out and rewrite from scratch to lift that restriction.
> http://www.mancoosi.org/edos/manager.html
The claim that aptitude can't handle this is utter bunk. Out of
curiosity, I typed the first one on that page down in the minimalist
syntax I use to test the aptitude resolver. (attached) It passed:
dan...@emurlahn:~/programming/aptitude/post-lenny/src/generic/problemresolver$
./test testcarglass.txt
(snip lots of cruft)
--- Found solution <door:=v2, engine:=v2, tyre:=v2, wheel:=v3,
window:=v0>;[];460
Would eliminate stupid, but stupid elimination is disabled.
Inserting conflict {engine := engine v2, wheel := wheel v3, tyre := tyre v2,
door := door v2, window := window v0}
*** Converged after 7 steps.
--- Found solution <door:=v2, engine:=v2, glass:=v1, tyre:=v2, wheel:=v3,
window:=v1>;[];470
Would eliminate stupid, but stupid elimination is disabled.
Inserting conflict {engine := engine v2, wheel := wheel v3, tyre := tyre v2,
door := door v2, window := window v1, glass := glass v1}
*** Converged after 2 steps.
--- Found solution <door:=v2, engine:=v2, glass:=v2, tyre:=v1, wheel:=v3,
window:=v2>;[];470
Would eliminate stupid, but stupid elimination is disabled.
Inserting conflict {engine := engine v2, wheel := wheel v3, tyre := tyre v1,
door := door v2, window := window v2, glass := glass v2}
*** Converged after 3 steps.
It didn't find the most "optimal" answer first because, as far as I
can tell, it considered the precursor to the "optimal" answer to be
equivalent to a "less optimal" answer, and preferred immediately
returning a result vs continuing to search in the hope of finding a
better one. Which reminds me, I have a feature request to keep
running for a "few" (maybe 50) steps past the first answer in search
of a better one...
Anyway, I don't consider that a big deal. One of the design decisions
I made early on was not to fetishize arbitrary "optimality" definitions,
because you can end up chasing phantoms that way. "Optimal" solutions
are not necessarily best. They are good for academic projects, though,
because you can easily "grade" yourself on whether you're doing a good
job and write papers about what a good job you did. ;-) (please note
that I say that only half-mockingly; I'd love to be paid to work on
this stuff, and playing the academia game seems to be one route these
days; this stuff wasn't taken seriously when I was in school because it
was "just for hobbyists" :-( )
Single-criterion tests like this are also a problem because for big
and complicated problems like this, you really need an overall picture
of what sort of results you're getting on a wide variety of inputs. At
my paid job, one of my projects was working on code to match input text
blocks against a database of postal addresses. You might think that
would be easy, but when you get to 30 million addresses it gets a bit
tricky...
Anyway, one thing you learn quickly is that you can make a change to
fix one address that's sitting in front of you, and 50 other addresses
suddenly go from producing a correct answer to producing a wrong answer.
It's like trying to flatten a bumpy rug -- push it down in one place
and three more pop up. You won't make any progress unless you have a
broad picture of whether you're actually doing better or not. Package
management is a lot like that, and I prefer to go by the fact that I
only have a handful of bug reports telling me that aptitude totally
failed on some inputs or others.
BTW, did you read this note at the bottom of the page?
> The content of this chapter should in no way be construed as a
> criticism of the tools we analysed: they do try to solve a much
> harder problem than ours, and they really try their best at it,
> handling all the added complexity of the extra bits of metadata
> associated to package management: we know of no satisfactory
> solution for this problem up to now, and our tools are not a
> replacement for Apt, Protage, Urpmi, Smart and the like.
> I made some personal test, to compare the solver capabilities myself. I add
> KDE 4.2 repository to SUSE and Ubuntu, and made an upgrade from 4.1.3 to 4.2.
> After that i disabled KDE 4.2 repositories and delete one of the KDE 4.2
> packages. This lead to inconsistent state, because KDE 4.2 repository was
> unavailable to repaire the dependency. The solution is obvious. Donwgrade
> somepackages back to KDE 4.1.3, to make dependencies OK because all 4.1.3
> packages are available.
The one case I know of where aptitude can totally fail is when you
have a large, complicated set of packages with interrelated
dependencies and you're trying to make all the packages consistent with
a single downgrade (it generally behaves OK if you have most of the
packages at the right version to start). I doubt it would be hard too
track this problem down, but it's an unusual edge case IMO, and I prefer
to spend my scarce free time on parts of the program that are more
deficient.
Daniel
UNIVERSE [
PACKAGE car < v1 > v1
PACKAGE engine < v1 v2 UNINST > UNINST
PACKAGE turbo < v1 UNINST > v1
PACKAGE wheel < v2 v3 UNINST > UNINST
PACKAGE tyre < v1 v2 UNINST > UNINST
PACKAGE door < v1 v2 UNINST > UNINST
PACKAGE window < v0 v1 v2 UNINST > UNINST
PACKAGE glass < v1 v2 UNINST > UNINST
DEP car v1 -> < engine v1 engine v2 >
DEP car v1 -> < wheel v2 wheel v3 >
DEP car v1 -> < door v1 door v2 >
DEP wheel v3 -> < tyre v1 tyre v2 >
DEP door v2 -> < window v0 window v1 window v2 >
DEP window v1 -> < glass v1 >
DEP window v2 -> < glass v2 >
DEP tyre v2 -> < glass v1 glass UNINST >
]
TEST 10 10 -1000 10000 10 {
SCORE engine < v2 100 >
SCORE wheel < v3 100 >
SCORE tyre < v2 100 >
SCORE door < v2 100 >
SCORE window < v2 100 >
} EXPECT ( 10000 ANY 10000 ANY 10000 ANY )
