| Age | Commit message (Collapse) | Author | Files | Lines |
|---|
|
|
|
The dependency matters, since the deferral condition can depend on
which dependency was followed.
|
|
and score.
This set isn't accessed often, so efficiency shouldn't be too much of a
concern. This change will support handling the retraction of user
constraints in a reasonably clean way, and it also makes room in the
design for incrementally handling other changes that alter the
resolver's conclusions (e.g., changes to package states and scores).
|
|
resolver.
I don't normally commit broken code, but this is a huge rewrite, and
I'd hate to lose it if my hard drive blew up.
|
|
of the resolver.
|
|
It's not as well separated as I'd like, but it's a start as far as
creating some internal structure.
|
|
|
|
|
|
per step *doubles* the resolver's footprint in a large search).
|
|
solution in a tier got deferred or dropped.
The problem was that the deferral and drop branches were executing
"continue" statements and bypassing the rest of the loop body,
including the stanza that advanced to the next tier if necessary.
This commit causes them to execute through the rest of the loop body,
just bypassing the part of the code that actually processes a solution.
|
|
information from it to *all* of its parents.
|
|
|
|
We were also throwing away the already-generated-solution tier; oops!
|
|
One of the log messages I chose conflicts with the "processing" line
emitted at the start of a search step, so I had to tweak the regular
expression the log parser uses to recognize search steps.
|
|
soft dependency is added.
Unfortunately, this is pretty obviously necessary for correct behavior.
Approving a version can cause another version to become legal (it's OK
to "avoid" an approved version by installing another approved version),
so we have to figure out which of the previously deferred solutions are
"really" deferred.
This would be a good excuse to write that code that tracks the reason
for each deferral and strips out only the information that might have
to go. Most of the time there should not be a need to throw out
deferral information, but we don't have any way of knowing this right
now.
|
|
instead of referring to *i repeatedly.
|
|
steps.
All the deferral propagations are thrown out at the beginning of this
routine, so as we find things that are still deferred, we have to attach
those deferrals to the search graph in order for backpropagation to be
able to pick up on them.
|
|
into the search tree.
|
|
processed when backpropagating promotions to parent steps.
|
|
same install as long as it was done for the same dependency, and use them to inject promotions related to approval user constraints.
Approvals are violated by search steps that choose a different solution
to a dependency than the approved one. So to represent these in the
condition of a promotion, we have to be able to match installing a
particular version *but only if the install was for a particular dep*.
In other words, install_version choices now have four levels of
specificity:
(no dep) -> (unscoped) -> (dep-scoped) -> (from-dep-source)
Choices with no dep "contain" any other choice that installs the same
version, and so do choices that are unscoped (but have a dep). Choices
that are dep-scoped "contain" choices that have the same dep (so no-dep
choices are out, but some unscoped choices can match). Choices in the
from-dep-source category "contain" choices that have the same dep and
that are also from-dep-source.
This commit adds the code necessary to represent these extra types
of choices, to manipulate them in the resolver, and to parse them in
the log analyzer. It also uses these new abilities to generate
promotions to the "defer" tier when successors violate a user
constraint.
|
|
promotion objects to the step graph for backpropagation.
|
|
actually processed, incorporate it into the backpropagation network.
|
|
|
|
|
|
version it installs, add a corresponding promotion in the search graph.
This lets the backpropagator build stronger conflict sets; without
this, any solution with a child that was promoted past the search
horizon but that wasn't a conflict won't be able to have
backpropagated promotions (since that child is never visited, so it
won't get a promotion, even though it clearly has one).
|
|
promotion, not the step itself.
Since child steps rarely generate new promotions through
backpropagation, this basically meant that hardly anything was getting
propagated around.
|
|
of a node.
If a potential sub-node triggers a promotion, then we need to remove
the choice made at that sub-node when generalizing the promotion to the
parent. Without this, higher-level promotions can never be formed
properly (they always end up containing too many choices).
|
|
break dependency resolution).
|
|
I apparently forgot to actually increase the tier in the result
promotion. Oops. :-(
|
|
|
|
Apparently I forgot to write this line of code when I replaced conflicts
with promotions. Oops. The resolver should stop sucking again.
|
|
net against exponential blowup and all the utility functions that will be needed.
|
|
The main conceptual error in the first draft was a failure to recognize
the fact that a step can have more than one promotion associated with
it. Based on a small handful of traces I've looked at, exploiting all
the promotion information we can get our hands on is a good idea. So
this second draft actually takes every single promotion from each child
and combines it with all the promotions from the other children. In
practice, usually only one child will have promotions and most nodes
generate only a few promotions (I think, anyway). However, before this
approach can be practical I need to implement some safety measures --
basically an arbitrary limit on how many promotions can accumulate at a
single node. That should avoid an exponential blowup of the number of
promotions.
|
|
This is in preparation for backpropagating conflict/promotion
information, and in fact much of the code for that is already
implemented in this commit (just not activated yet). I decided to
use integer references into a deque to keep things a little more
compact instead of having a huge number of structures on the heap: the
resolver is already memory-hungry enough, no need to make things even
worse.
|
|
|
|
version tiers.
|
|
tier first and then by score.
This avoids a nasty problem: future ticks could advance to a new tier
and start producing solutions in it; if those solutions had a higher
score than the solutions at the lower tier, they'd come out first!
Now they can't.
|
|
spin trying to process it over and over.
|
|
|
|
|
|
|
|
plain integers.
This allows us to classify solutions in a more fine-grained way. In
particular, it provides a not-horrible way to integrate apt pin
priorities into the resolver's decisions, by making them a subordinate
level of ranking to the main tiering system.
The current plan is that the first level of tiering is the only one the
user sees (by default) and the only one that can be directly configured.
The subordinate levels are filled in automatically (pin priorities are
all I have in mind now, but I don't discount the possibility of
introducing more levels in the future).
|
|
|
|
The other part of jumps.
|
|
package replacement.
In practice, jumps will exist from the removal version of a package
that has replacements to every version that replaces that package.
Jumps have some similarities to soft dependencies, and they could be
represented by them, but there are important semantic differences. The
biggest one is that a dependency is a constraint and a jump is not.
Instead, a jump is a rule that tells the solver how to structure its
search: whenever it places a particular version into the solution, it
should split the search to consider several other versions as well.
Among other things, this distinction means that the resolver will not
attempt to spontaneously install replacements for packages that aren't
installed; it will only add replacements to the solution when the
solution also contains the removal version.
|
|
choice_sets, rather than manually storing the different types of choices in the solution object.
This has two beneficial effects. First, it should make it a bit easier
to add a new choice type, although many parts of the program will still
have to be touched. Perhaps more importantly, this provides a cleaner
conceptual model of what the resolver does: it finds "choice points"
(that is to say, dependencies that need to be solved) and makes choices
at them.
This commit sneaks in a few optimizations that I came across in the
process of rewiring all the resolver logic. The big one is that testing
whether a solution violates a user constraint now requires steps
proportional to the size of the solution, not to the number of user
constraints. (each step is logarithmic in the number of constraints,
but that's still a big improvement)
|
|
|
|
of each step are.
This way, the message that a successor is being generated is right next
to the message about *why* it's being generated, so it's easy to link
those facts together.
|
|
Choices are now exactly the same as actions, except that they're
a bit more self-contained, explicitly separate from the solution, and
have a type tag. So I'm going in circles a little more than I'd like.
Still, I think this will clean up the code a little and will
particularly make it easier to introduce a new choice type.
|
|
This is in preparation for replacing solution actions (which need an ID
to be placed in a "logical" order) with choices. In some parts of the
resolver code, I'm assigning a dummy value (-1) to the ID as an interim
measure until that happens. That will change once everything is hooked
up (but -1 will still be used in tests where I don't care about the
ID).
|
