X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=src%2Fsolver.c;h=e17205b9cff7c846cca39cc47503809fb9cec855;hb=4cd070f32551eb0dd7a2bd355028c346222107d8;hp=ccb1ee2353e7a9afd7cbb4dff404219f6926e547;hpb=8798d822f237f7e71f786553d09787aa812fd2bc;p=platform%2Fupstream%2Flibsolv.git diff --git a/src/solver.c b/src/solver.c index ccb1ee2..e17205b 100644 --- a/src/solver.c +++ b/src/solver.c @@ -1,5 +1,5 @@ /* - * Copyright (c) 2007, Novell Inc. + * Copyright (c) 2007-2008, Novell Inc. * * This program is licensed under the BSD license, read LICENSE.BSD * for further information @@ -21,12 +21,9 @@ #include "bitmap.h" #include "pool.h" #include "util.h" -#include "evr.h" #include "policy.h" #include "solverdebug.h" - - #define RULES_BLOCK 63 /******************************************************************** @@ -35,11 +32,15 @@ * */ +/*------------------------------------------------------------------- + * handle split provides + */ + int solver_splitprovides(Solver *solv, Id dep) { Pool *pool = solv->pool; - Id p, *pp; + Id p, pp; Reldep *rd; Solvable *s; @@ -59,12 +60,17 @@ solver_splitprovides(Solver *solv, Id dep) return 0; } + +/*------------------------------------------------------------------- + * solver_dep_installed + */ + int solver_dep_installed(Solver *solv, Id dep) { #if 0 Pool *pool = solv->pool; - Id p, *pp; + Id p, pp; if (ISRELDEP(dep)) { @@ -88,440 +94,53 @@ solver_dep_installed(Solver *solv, Id dep) } -/* this mirrors solver_dep_fulfilled but uses map m instead of the decisionmap */ -static inline int -dep_possible(Solver *solv, Id dep, Map *m) -{ - Pool *pool = solv->pool; - Id p, *pp; - - if (ISRELDEP(dep)) - { - Reldep *rd = GETRELDEP(pool, dep); - if (rd->flags == REL_AND) - { - if (!dep_possible(solv, rd->name, m)) - return 0; - return dep_possible(solv, rd->evr, m); - } - if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES) - return solver_splitprovides(solv, rd->evr); - if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED) - return solver_dep_installed(solv, rd->evr); - } - FOR_PROVIDES(p, pp, dep) - { - if (MAPTST(m, p)) - return 1; - } - return 0; -} - -/******************************************************************** - * - * Rule handling - * - */ - -static Pool *unifyrules_sortcmp_data; - -/* - * compare rules for unification sort - */ - -static int -unifyrules_sortcmp(const void *ap, const void *bp) -{ - Pool *pool = unifyrules_sortcmp_data; - Rule *a = (Rule *)ap; - Rule *b = (Rule *)bp; - Id *ad, *bd; - int x; - - x = a->p - b->p; - if (x) - return x; /* p differs */ - - /* identical p */ - if (a->d == 0 && b->d == 0) - return a->w2 - b->w2; /* assertion: return w2 diff */ - - if (a->d == 0) /* a is assertion, b not */ - { - x = a->w2 - pool->whatprovidesdata[b->d]; - return x ? x : -1; - } - - if (b->d == 0) /* b is assertion, a not */ - { - x = pool->whatprovidesdata[a->d] - b->w2; - return x ? x : 1; - } - - /* compare whatprovidesdata */ - ad = pool->whatprovidesdata + a->d; - bd = pool->whatprovidesdata + b->d; - while (*bd) - if ((x = *ad++ - *bd++) != 0) - return x; - return *ad; -} - - -/* - * unify rules - */ - -static void -unifyrules(Solver *solv) -{ - Pool *pool = solv->pool; - int i, j; - Rule *ir, *jr; - - if (solv->nrules <= 1) /* nothing to unify */ - return; - - POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- unifyrules -----\n"); - - /* sort rules first */ - unifyrules_sortcmp_data = solv->pool; - qsort(solv->rules + 1, solv->nrules - 1, sizeof(Rule), unifyrules_sortcmp); - - /* prune rules - * i = unpruned - * j = pruned - */ - jr = 0; - for (i = j = 1, ir = solv->rules + i; i < solv->nrules; i++, ir++) - { - if (jr && !unifyrules_sortcmp(ir, jr)) - continue; /* prune! */ - jr = solv->rules + j++; /* keep! */ - if (ir != jr) - *jr = *ir; - } - - /* reduced count from nrules to j rules */ - POOL_DEBUG(SAT_DEBUG_STATS, "pruned rules from %d to %d\n", solv->nrules, j); - - /* adapt rule buffer */ - solv->nrules = j; - solv->rules = sat_extend_resize(solv->rules, solv->nrules, sizeof(Rule), RULES_BLOCK); - IF_POOLDEBUG (SAT_DEBUG_STATS) - { - int binr = 0; - int lits = 0; - Id *dp; - Rule *r; - - for (i = 1; i < solv->nrules; i++) - { - r = solv->rules + i; - if (r->d == 0) - binr++; - else - { - dp = solv->pool->whatprovidesdata + r->d; - while (*dp++) - lits++; - } - } - POOL_DEBUG(SAT_DEBUG_STATS, " binary: %d\n", binr); - POOL_DEBUG(SAT_DEBUG_STATS, " normal: %d, %d literals\n", solv->nrules - 1 - binr, lits); - } - POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- unifyrules end -----\n"); -} - -#if 0 - -/* - * hash rule - */ - -static Hashval -hashrule(Solver *solv, Id p, Id d, int n) -{ - unsigned int x = (unsigned int)p; - int *dp; - - if (n <= 1) - return (x * 37) ^ (unsigned int)d; - dp = solv->pool->whatprovidesdata + d; - while (*dp) - x = (x * 37) ^ (unsigned int)*dp++; - return x; -} -#endif +/************************************************************************/ /* - * add rule - * p = direct literal; always < 0 for installed rpm rules - * d, if < 0 direct literal, if > 0 offset into whatprovides, if == 0 rule is assertion (look at p only) - * - * - * A requires b, b provided by B1,B2,B3 => (-A|B1|B2|B3) - * - * p < 0 : pkg id of A - * d > 0 : Offset in whatprovidesdata (list of providers of b) - * - * A conflicts b, b provided by B1,B2,B3 => (-A|-B1), (-A|-B2), (-A|-B3) - * p < 0 : pkg id of A - * d < 0 : Id of solvable (e.g. B1) - * - * d == 0: unary rule, assertion => (A) or (-A) - * - * Install: p > 0, d = 0 (A) user requested install - * Remove: p < 0, d = 0 (-A) user requested remove - * Requires: p < 0, d > 0 (-A|B1|B2|...) d: - * Updates: p > 0, d > 0 (A|B1|B2|...) d: - * Conflicts: p < 0, d < 0 (-A|-B) either p (conflict issuer) or d (conflict provider) (binary rule) - * ? p > 0, d < 0 (A|-B) - * No-op ?: p = 0, d = 0 (null) (used as policy rule placeholder) - * - * resulting watches: - * ------------------ - * Direct assertion (no watch needed)( if d <0 ) --> d = 0, w1 = p, w2 = 0 - * Binary rule: p = first literal, d = 0, w2 = second literal, w1 = p - * every other : w1 = p, w2 = whatprovidesdata[d]; - * Disabled rule: w1 = 0 - * - * always returns a rule for non-rpm rules - */ - -static Rule * -addrule(Solver *solv, Id p, Id d) -{ - Pool *pool = solv->pool; - Rule *r = 0; - Id *dp = 0; - - int n = 0; /* number of literals in rule - 1 - 0 = direct assertion (single literal) - 1 = binary rule - */ - - /* it often happenes that requires lead to adding the same rpm rule - * multiple times, so we prune those duplicates right away to make - * the work for unifyrules a bit easier */ - - if (solv->nrules && !solv->jobrules) - { - r = solv->rules + solv->nrules - 1; /* get the last added rule */ - if (r->p == p && r->d == d && d != 0) /* identical and not user requested */ - return r; - } - - if (d < 0) - { - /* always a binary rule */ - if (p == d) - return 0; /* ignore self conflict */ - n = 1; - } - else if (d > 0) - { - for (dp = pool->whatprovidesdata + d; *dp; dp++, n++) - if (*dp == -p) - return 0; /* rule is self-fulfilling */ - if (n == 1) - d = dp[-1]; /* take single literal */ - } - -#if 0 - if (n == 0 && !solv->jobrules) - { - /* this is a rpm rule assertion, we do not have to allocate it */ - /* it can be identified by a level of 1 and a zero reason */ - /* we must not drop those rules from the decisionq when rewinding! */ - assert(p < 0); - assert(solv->decisionmap[-p] == 0 || solv->decisionmap[-p] == -1); - if (solv->decisionmap[-p]) - return 0; /* already got that one */ - queue_push(&solv->decisionq, p); - queue_push(&solv->decisionq_why, 0); - solv->decisionmap[-p] = -1; - return 0; - } -#endif - - if (n == 1 && p > d) - { - /* smallest literal first so we can find dups */ - n = p; - p = d; - d = n; - n = 1; /* re-set n, was used as temp var */ - } - - /* check if the last added rule is exactly the same as what we're looking for. */ - if (r && n == 1 && !r->d && r->p == p && r->w2 == d) - return r; /* binary rule */ - - if (r && n > 1 && r->d && r->p == p) - { - /* Rule where d is an offset in whatprovidesdata */ - Id *dp2; - if (d == r->d) - return r; - dp2 = pool->whatprovidesdata + r->d; - for (dp = pool->whatprovidesdata + d; *dp; dp++, dp2++) - if (*dp != *dp2) - break; - if (*dp == *dp2) - return r; - } - - /* - * allocate new rule - */ - - /* extend rule buffer */ - solv->rules = sat_extend(solv->rules, solv->nrules, 1, sizeof(Rule), RULES_BLOCK); - r = solv->rules + solv->nrules++; /* point to rule space */ - - r->p = p; - if (n == 0) - { - /* direct assertion, no watch needed */ - r->d = 0; - r->w1 = p; - r->w2 = 0; - } - else if (n == 1) - { - /* binary rule */ - r->d = 0; - r->w1 = p; - r->w2 = d; - } - else - { - r->d = d; - r->w1 = p; - r->w2 = pool->whatprovidesdata[d]; - } - r->n1 = 0; - r->n2 = 0; - - IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION) - { - POOL_DEBUG(SAT_DEBUG_RULE_CREATION, " Add rule: "); - solver_printrule(solv, SAT_DEBUG_RULE_CREATION, r); - } - - return r; -} - -static inline void -disablerule(Solver *solv, Rule *r) -{ - r->w1 = 0; -} - -static inline void -enablerule(Solver *solv, Rule *r) -{ - if (r->d == 0 || r->w2 != r->p) - r->w1 = r->p; - else - r->w1 = solv->pool->whatprovidesdata[r->d]; -} - - -/**********************************************************************************/ - -/* a problem is an item on the solver's problem list. It can either be >0, in that - * case it is a update rule, or it can be <0, which makes it refer to a job - * consisting of multiple job rules. + * make assertion rules into decisions + * + * Go through rules and add direct assertions to the decisionqueue. + * If we find a conflict, disable rules and add them to problem queue. */ static void -disableproblem(Solver *solv, Id v) -{ - Rule *r; - int i; - Id *jp; - - if (v > 0) - { - disablerule(solv, solv->rules + v); - return; - } - v = -(v + 1); - jp = solv->ruletojob.elements; - for (i = solv->jobrules, r = solv->rules + i; i < solv->updaterules; i++, r++, jp++) - if (*jp == v) - disablerule(solv, r); -} - -static void -enableproblem(Solver *solv, Id v) -{ - Rule *r; - int i; - Id *jp; - - if (v > 0) - { - if (v >= solv->featurerules && v < solv->learntrules) - { - /* do not enable feature rule is update rule is enabled */ - r = solv->rules + v - (solv->installed->end - solv->installed->start); - if (r->w1) - return; - } - enablerule(solv, solv->rules + v); - if (v >= solv->updaterules && v < solv->featurerules) - { - r = solv->rules + v + (solv->installed->end - solv->installed->start); - if (r->p) - disablerule(solv, r); - } - return; - } - v = -(v + 1); - jp = solv->ruletojob.elements; - for (i = solv->jobrules, r = solv->rules + i; i < solv->updaterules; i++, r++, jp++) - if (*jp == v) - enablerule(solv, r); -} - - -/************************************************************************/ - -/* go through update and job rules and add direct assertions - * to the decisionqueue. If we find a conflict, disable rules and - * add them to problem queue. - */ -static void makeruledecisions(Solver *solv) { Pool *pool = solv->pool; - int i, ri; + int i, ri, ii; Rule *r, *rr; Id v, vv; int decisionstart; POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- makeruledecisions ; size decisionq: %d -----\n",solv->decisionq.count); + /* The system solvable is always installed first */ + assert(solv->decisionq.count == 0); + queue_push(&solv->decisionq, SYSTEMSOLVABLE); + queue_push(&solv->decisionq_why, 0); + solv->decisionmap[SYSTEMSOLVABLE] = 1; /* installed at level '1' */ + decisionstart = solv->decisionq.count; - /* rpm rules don't have assertions, so we can start with the job - * rules (rpm assertions are not resulting in a rule, but cause a - * immediate decision) */ - /* nowadays they can be weak, so start with rule 1 */ - for (ri = 1, r = solv->rules + ri; ri < solv->nrules; ri++, r++) + for (ii = 0; ii < solv->ruleassertions.count; ii++) { - if (!r->w1 || r->w2) /* disabled or no assertion */ + ri = solv->ruleassertions.elements[ii]; + r = solv->rules + ri; + + if (r->d < 0 || !r->p || r->w2) /* disabled, dummy or no assertion */ continue; /* do weak rules in phase 2 */ if (ri < solv->learntrules && MAPTST(&solv->weakrulemap, ri)) continue; + v = r->p; vv = v > 0 ? v : -v; - if (!solv->decisionmap[vv]) + + if (!solv->decisionmap[vv]) /* if not yet decided */ { + /* + * decide ! + */ queue_push(&solv->decisionq, v); queue_push(&solv->decisionq_why, r - solv->rules); solv->decisionmap[vv] = v > 0 ? 1 : -1; @@ -535,43 +154,69 @@ makeruledecisions(Solver *solv) } continue; } - if (v > 0 && solv->decisionmap[vv] > 0) + /* + * check previous decision: is it sane ? + */ + + if (v > 0 && solv->decisionmap[vv] > 0) /* ok to install */ continue; - if (v < 0 && solv->decisionmap[vv] < 0) + if (v < 0 && solv->decisionmap[vv] < 0) /* ok to remove */ continue; - /* found a conflict! */ + + /* + * found a conflict! + * + * The rule (r) we're currently processing says something + * different (v = r->p) than a previous decision (decisionmap[abs(v)]) + * on this literal + */ + if (ri >= solv->learntrules) { /* conflict with a learnt rule */ /* can happen when packages cannot be installed for * multiple reasons. */ /* we disable the learnt rule in this case */ - disablerule(solv, r); + solver_disablerule(solv, r); continue; } - /* only job and update rules left in the decisionq */ - /* find the decision which is the "opposite" of the jobrule */ + + /* + * find the decision which is the "opposite" of the rule + */ + for (i = 0; i < solv->decisionq.count; i++) if (solv->decisionq.elements[i] == -v) break; - assert(i < solv->decisionq.count); + assert(i < solv->decisionq.count); /* assert that we found it */ + + /* + * conflict with system solvable ? + */ + if (v == -SYSTEMSOLVABLE) { /* conflict with system solvable */ queue_push(&solv->problems, solv->learnt_pool.count); queue_push(&solv->learnt_pool, ri); queue_push(&solv->learnt_pool, 0); POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "conflict with system solvable, disabling rule #%d\n", ri); - if (ri < solv->updaterules) + if (ri >= solv->jobrules && ri < solv->jobrules_end) v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1); else v = ri; queue_push(&solv->problems, v); queue_push(&solv->problems, 0); - disableproblem(solv, v); + solver_disableproblem(solv, v); continue; } - assert(solv->decisionq_why.elements[i]); - if (solv->decisionq_why.elements[i] < solv->jobrules) + + assert(solv->decisionq_why.elements[i] > 0); + + /* + * conflict with an rpm rule ? + */ + + if (solv->decisionq_why.elements[i] < solv->rpmrules_end) { /* conflict with rpm rule assertion */ queue_push(&solv->problems, solv->learnt_pool.count); @@ -580,17 +225,20 @@ makeruledecisions(Solver *solv) queue_push(&solv->learnt_pool, 0); assert(v > 0 || v == -SYSTEMSOLVABLE); POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "conflict with rpm rule, disabling rule #%d\n", ri); - if (ri < solv->updaterules) + if (ri >= solv->jobrules && ri < solv->jobrules_end) v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1); else v = ri; queue_push(&solv->problems, v); queue_push(&solv->problems, 0); - disableproblem(solv, v); + solver_disableproblem(solv, v); continue; } - /* conflict with another job or update rule */ + /* + * conflict with another job or update/feature rule + */ + /* record proof */ queue_push(&solv->problems, solv->learnt_pool.count); queue_push(&solv->learnt_pool, ri); @@ -599,27 +247,40 @@ makeruledecisions(Solver *solv) POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "conflicting update/job assertions over literal %d\n", vv); - /* push all of our rules asserting this literal on the problem stack */ - for (i = solv->jobrules, rr = solv->rules + i; i < solv->nrules; i++, rr++) + /* + * push all of our rules (can only be feature or job rules) + * asserting this literal on the problem stack + */ + + for (i = solv->featurerules, rr = solv->rules + i; i < solv->learntrules; i++, rr++) { - if (!rr->w1 || rr->w2) + if (rr->d < 0 /* disabled */ + || rr->w2) /* or no assertion */ continue; - if (rr->p != vv && rr->p != -vv) + if (rr->p != vv /* not affecting the literal */ + && rr->p != -vv) continue; - if (i >= solv->learntrules) - continue; - if (MAPTST(&solv->weakrulemap, i)) + if (MAPTST(&solv->weakrulemap, i)) /* weak: silently ignore */ continue; + POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, " - disabling rule #%d\n", i); + + solver_printruleclass(solv, SAT_DEBUG_UNSOLVABLE, solv->rules + i); + v = i; - if (i < solv->updaterules) + /* is is a job rule ? */ + if (i >= solv->jobrules && i < solv->jobrules_end) v = -(solv->ruletojob.elements[i - solv->jobrules] + 1); + queue_push(&solv->problems, v); - disableproblem(solv, v); + solver_disableproblem(solv, v); } queue_push(&solv->problems, 0); - /* start over */ + /* + * start over + * (back up from decisions) + */ while (solv->decisionq.count > decisionstart) { v = solv->decisionq.elements[--solv->decisionq.count]; @@ -627,19 +288,26 @@ makeruledecisions(Solver *solv) vv = v > 0 ? v : -v; solv->decisionmap[vv] = 0; } - ri = solv->jobrules - 1; - r = solv->rules + ri; + ii = -1; /* restarts loop at 0 */ } - /* phase 2: now do the weak assertions */ - for (ri = 1, r = solv->rules + ri; ri < solv->learntrules; ri++, r++) + /* + * phase 2: now do the weak assertions + */ + for (ii = 0; ii < solv->ruleassertions.count; ii++) { - if (!r->w1 || r->w2) /* disabled or no assertion */ + ri = solv->ruleassertions.elements[ii]; + r = solv->rules + ri; + if (r->d < 0 || r->w2) /* disabled or no assertion */ continue; - if (!MAPTST(&solv->weakrulemap, ri)) + if (ri >= solv->learntrules || !MAPTST(&solv->weakrulemap, ri)) /* skip non-weak */ continue; v = r->p; vv = v > 0 ? v : -v; + /* + * decide ! + * (if not yet decided) + */ if (!solv->decisionmap[vv]) { queue_push(&solv->decisionq, v); @@ -655,21 +323,35 @@ makeruledecisions(Solver *solv) } continue; } + /* + * previously decided, sane ? + */ if (v > 0 && solv->decisionmap[vv] > 0) continue; if (v < 0 && solv->decisionmap[vv] < 0) continue; + POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "assertion conflict, but I am weak, disabling "); solver_printrule(solv, SAT_DEBUG_UNSOLVABLE, r); - disablerule(solv, r); + + if (ri >= solv->jobrules && ri < solv->jobrules_end) + v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1); + else + v = ri; + solver_disableproblem(solv, v); + if (v < 0) + solver_reenablepolicyrules(solv, -(v + 1)); } POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- makeruledecisions end; size decisionq: %d -----\n",solv->decisionq.count); } -/* + +/*------------------------------------------------------------------- + * enable/disable learnt rules + * * we have enabled or disabled some of our rules. We now reenable all - * of our learnt rules but the ones that were learnt from rules that + * of our learnt rules except the ones that were learnt from rules that * are now disabled. */ static void @@ -687,628 +369,84 @@ enabledisablelearntrules(Solver *solv) while ((why = *whyp++) != 0) { assert(why > 0 && why < i); - if (!solv->rules[why].w1) + if (solv->rules[why].d < 0) break; } /* why != 0: we found a disabled rule, disable the learnt rule */ - if (why && r->w1) + if (why && r->d >= 0) { IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS) { POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "disabling "); solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r); } - disablerule(solv, r); + solver_disablerule(solv, r); } - else if (!why && !r->w1) + else if (!why && r->d < 0) { IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS) { POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "re-enabling "); solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r); } - enablerule(solv, r); + solver_enablerule(solv, r); } } } -void -enableweakrules(Solver *solv) + +/********************************************************************/ +/* watches */ + + +/*------------------------------------------------------------------- + * makewatches + * + * initial setup for all watches + */ + +static void +makewatches(Solver *solv) { - int i; Rule *r; + int i; + int nsolvables = solv->pool->nsolvables; - for (i = solv->jobrules, r = solv->rules + i; i < solv->learntrules; i++, r++) + sat_free(solv->watches); + /* lower half for removals, upper half for installs */ + solv->watches = sat_calloc(2 * nsolvables, sizeof(Id)); +#if 1 + /* do it reverse so rpm rules get triggered first (XXX: obsolete?) */ + for (i = 1, r = solv->rules + solv->nrules - 1; i < solv->nrules; i++, r--) +#else + for (i = 1, r = solv->rules + 1; i < solv->nrules; i++, r++) +#endif { - if (r->w1) + if (!r->w2) /* assertions do not need watches */ continue; - if (!MAPTST(&solv->weakrulemap, i)) - continue; - enablerule(solv, r); + + /* see addwatches_rule(solv, r) */ + r->n1 = solv->watches[nsolvables + r->w1]; + solv->watches[nsolvables + r->w1] = r - solv->rules; + + r->n2 = solv->watches[nsolvables + r->w2]; + solv->watches[nsolvables + r->w2] = r - solv->rules; } } -/* FIXME: bad code ahead, replace as soon as possible */ -/* FIXME: should probably look at SOLVER_INSTALL_SOLVABLE_ONE_OF */ +/*------------------------------------------------------------------- + * + * add watches (for a new learned rule) + * sets up watches for a single rule + * + * see also makewatches() above. + */ -static void -disableupdaterules(Solver *solv, Queue *job, int jobidx) +static inline void +addwatches_rule(Solver *solv, Rule *r) { - Pool *pool = solv->pool; - int i, j; - Id name, how, what, p, *pp; - Solvable *s; - Repo *installed; - Rule *r; - Id lastjob = -1; - - installed = solv->installed; - if (!installed) - return; - - if (jobidx != -1) - { - how = job->elements[jobidx] & ~SOLVER_WEAK; - switch(how) - { - case SOLVER_INSTALL_SOLVABLE: - case SOLVER_ERASE_SOLVABLE: - case SOLVER_ERASE_SOLVABLE_NAME: - case SOLVER_ERASE_SOLVABLE_PROVIDES: - break; - default: - return; - } - } - /* go through all enabled job rules */ - MAPZERO(&solv->noupdate); - for (i = solv->jobrules; i < solv->updaterules; i++) - { - r = solv->rules + i; - if (!r->w1) /* disabled? */ - continue; - j = solv->ruletojob.elements[i - solv->jobrules]; - if (j == lastjob) - continue; - lastjob = j; - how = job->elements[j] & ~SOLVER_WEAK; - what = job->elements[j + 1]; - switch(how) - { - case SOLVER_INSTALL_SOLVABLE: /* install specific solvable */ - s = pool->solvables + what; - FOR_PROVIDES(p, pp, s->name) - { - if (pool->solvables[p].name != s->name) - continue; - if (pool->solvables[p].repo == installed) - MAPSET(&solv->noupdate, p - installed->start); - } - break; - case SOLVER_ERASE_SOLVABLE: - s = pool->solvables + what; - if (s->repo == installed) - MAPSET(&solv->noupdate, what - installed->start); - break; - case SOLVER_ERASE_SOLVABLE_NAME: /* remove by capability */ - case SOLVER_ERASE_SOLVABLE_PROVIDES: - name = (how == SOLVER_ERASE_SOLVABLE_NAME) ? what : 0; - while (ISRELDEP(name)) - { - Reldep *rd = GETRELDEP(pool, name); - name = rd->name; - } - FOR_PROVIDES(p, pp, what) - { - if (name && pool->solvables[p].name != name) - continue; - if (pool->solvables[p].repo == installed) - MAPSET(&solv->noupdate, p - installed->start); - } - break; - default: - break; - } - } - - /* fixup update rule status */ - if (solv->allowuninstall) - return; /* no update rules at all */ - - if (jobidx != -1) - { - /* we just disabled job #jobidx. enable all update rules - * that aren't disabled by the remaining job rules */ - how = job->elements[jobidx] & ~SOLVER_WEAK; - what = job->elements[jobidx + 1]; - switch(how) - { - case SOLVER_INSTALL_SOLVABLE: - s = pool->solvables + what; - FOR_PROVIDES(p, pp, s->name) - { - if (pool->solvables[p].name != s->name) - continue; - if (pool->solvables[p].repo != installed) - continue; - if (MAPTST(&solv->noupdate, p - installed->start)) - continue; - r = solv->rules + solv->updaterules + (p - installed->start); - if (r->w1) - continue; - enablerule(solv, r); - IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS) - { - POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling "); - solver_printrule(solv, SAT_DEBUG_SOLUTIONS, r); - } - } - break; - case SOLVER_ERASE_SOLVABLE: - s = pool->solvables + what; - if (s->repo != installed) - break; - if (MAPTST(&solv->noupdate, what - installed->start)) - break; - r = solv->rules + solv->updaterules + (what - installed->start); - if (r->w1) - break; - enablerule(solv, r); - IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS) - { - POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling "); - solver_printrule(solv, SAT_DEBUG_SOLUTIONS, r); - } - break; - case SOLVER_ERASE_SOLVABLE_NAME: /* remove by capability */ - case SOLVER_ERASE_SOLVABLE_PROVIDES: - name = (how == SOLVER_ERASE_SOLVABLE_NAME) ? what : 0; - while (ISRELDEP(name)) - { - Reldep *rd = GETRELDEP(pool, name); - name = rd->name; - } - FOR_PROVIDES(p, pp, what) - { - if (name && pool->solvables[p].name != name) - continue; - if (pool->solvables[p].repo != installed) - continue; - if (MAPTST(&solv->noupdate, p - installed->start)) - continue; - r = solv->rules + solv->updaterules + (p - installed->start); - if (r->w1) - continue; - enablerule(solv, r); - IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS) - { - POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling "); - solver_printrule(solv, SAT_DEBUG_SOLUTIONS, r); - } - } - break; - default: - break; - } - return; - } - - for (i = 0; i < installed->nsolvables; i++) - { - r = solv->rules + solv->updaterules + i; - if (r->w1 && MAPTST(&solv->noupdate, i)) - disablerule(solv, r); /* was enabled, need to disable */ - r = solv->rules + solv->featurerules + i; - if (r->w1 && MAPTST(&solv->noupdate, i)) - disablerule(solv, r); /* was enabled, need to disable */ - } -} - -#if 0 -static void -addpatchatomrequires(Solver *solv, Solvable *s, Id *dp, Queue *q, Map *m) -{ - Pool *pool = solv->pool; - Id fre, *frep, p, *pp, ndp; - Solvable *ps; - Queue fq; - Id qbuf[64]; - int i, used = 0; - - queue_init_buffer(&fq, qbuf, sizeof(qbuf)/sizeof(*qbuf)); - queue_push(&fq, -(s - pool->solvables)); - for (; *dp; dp++) - queue_push(&fq, *dp); - ndp = pool_queuetowhatprovides(pool, &fq); - frep = s->repo->idarraydata + s->freshens; - while ((fre = *frep++) != 0) - { - FOR_PROVIDES(p, pp, fre) - { - ps = pool->solvables + p; - addrule(solv, -p, ndp); - used = 1; - if (!MAPTST(m, p)) - queue_push(q, p); - } - } - if (used) - { - for (i = 1; i < fq.count; i++) - { - p = fq.elements[i]; - if (!MAPTST(m, p)) - queue_push(q, p); - } - } - queue_free(&fq); -} -#endif - - -/* - * add (install) rules for solvable - * for unfulfilled requirements, conflicts, obsoletes,.... - * add a negative assertion for solvables that are not installable - */ - -static void -addrpmrulesforsolvable(Solver *solv, Solvable *s, Map *m) -{ - Pool *pool = solv->pool; - Repo *installed = solv->installed; - Queue q; - Id qbuf[64]; - int i; - int dontfix; - int patchatom; - Id req, *reqp; - Id con, *conp; - Id obs, *obsp; - Id rec, *recp; - Id sug, *sugp; - Id p, *pp; - Id *dp; - Id n; - - POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforsolvable -----\n"); - - queue_init_buffer(&q, qbuf, sizeof(qbuf)/sizeof(*qbuf)); - queue_push(&q, s - pool->solvables); /* push solvable Id */ - - while (q.count) - { - /* - * n: Id of solvable - * s: Pointer to solvable - */ - - n = queue_shift(&q); - if (MAPTST(m, n)) /* continue if already done */ - continue; - - MAPSET(m, n); - s = pool->solvables + n; /* s = Solvable in question */ - - dontfix = 0; - if (installed /* Installed system available */ - && !solv->fixsystem /* NOT repair errors in rpm dependency graph */ - && s->repo == installed) /* solvable is installed? */ - { - dontfix = 1; /* dont care about broken rpm deps */ - } - - if (!dontfix && s->arch != ARCH_SRC && s->arch != ARCH_NOSRC && !pool_installable(pool, s)) - { - POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "package %s [%d] is not installable\n", solvable2str(pool, s), (Id)(s - pool->solvables)); - addrule(solv, -n, 0); /* uninstallable */ - } - - patchatom = 0; - if (s->freshens && !s->supplements) - { - const char *name = id2str(pool, s->name); - if (name[0] == 'a' && !strncmp(name, "atom:", 5)) - patchatom = 1; - } - - /*----------------------------------------- - * check requires of s - */ - - if (s->requires) - { - reqp = s->repo->idarraydata + s->requires; - while ((req = *reqp++) != 0) /* go throw all requires */ - { - if (req == SOLVABLE_PREREQMARKER) /* skip the marker */ - continue; - - dp = pool_whatprovides(pool, req); - - if (*dp == SYSTEMSOLVABLE) /* always installed */ - continue; - -#if 0 - if (patchatom) - { - addpatchatomrequires(solv, s, dp, &q, m); - continue; - } -#endif - if (dontfix) - { - /* the strategy here is to not insist on dependencies - * that are already broken. so if we find one provider - * that was already installed, we know that the - * dependency was not broken before so we enforce it */ - for (i = 0; (p = dp[i]) != 0; i++) /* for all providers */ - { - if (pool->solvables[p].repo == installed) - break; /* provider was installed */ - } - if (!p) /* previously broken dependency */ - { - POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "ignoring broken requires %s of installed package %s\n", dep2str(pool, req), solvable2str(pool, s)); - continue; - } - } - - if (!*dp) - { - /* nothing provides req! */ - POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "package %s [%d] is not installable (%s)\n", solvable2str(pool, s), (Id)(s - pool->solvables), dep2str(pool, req)); - addrule(solv, -n, 0); /* mark requestor as uninstallable */ - continue; - } - - IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION) - { - POOL_DEBUG(SAT_DEBUG_RULE_CREATION," %s requires %s\n", solvable2str(pool, s), dep2str(pool, req)); - for (i = 0; dp[i]; i++) - POOL_DEBUG(SAT_DEBUG_RULE_CREATION, " provided by %s\n", solvable2str(pool, pool->solvables + dp[i])); - } - - /* add 'requires' dependency */ - /* rule: (-requestor|provider1|provider2|...|providerN) */ - addrule(solv, -n, dp - pool->whatprovidesdata); - - /* descend the dependency tree */ - for (; *dp; dp++) /* loop through all providers */ - { - if (!MAPTST(m, *dp)) - queue_push(&q, *dp); - } - - } /* while, requirements of n */ - - } /* if, requirements */ - - /* that's all we check for src packages */ - if (s->arch == ARCH_SRC || s->arch == ARCH_NOSRC) - continue; - - /*----------------------------------------- - * check conflicts of s - */ - - if (s->conflicts) - { - conp = s->repo->idarraydata + s->conflicts; - while ((con = *conp++) != 0) - { - FOR_PROVIDES(p, pp, con) - { - /* dontfix: dont care about conflicts with already installed packs */ - if (dontfix && pool->solvables[p].repo == installed) - continue; - if (p == n && !solv->allowselfconflicts) - p = 0; /* make it a negative assertion */ - /* rule: -n|-p: either solvable _or_ provider of conflict */ - addrule(solv, -n, -p); - } - } - } - - /*----------------------------------------- - * check obsoletes if not installed - */ - if (!installed || pool->solvables[n].repo != installed) - { /* not installed */ - if (s->obsoletes) - { - obsp = s->repo->idarraydata + s->obsoletes; - while ((obs = *obsp++) != 0) - { - FOR_PROVIDES(p, pp, obs) - addrule(solv, -n, -p); - } - } - FOR_PROVIDES(p, pp, s->name) - { - if (s->name == pool->solvables[p].name) - addrule(solv, -n, -p); - } - } - - /*----------------------------------------- - * add recommends to the rule list - */ - if (s->recommends) - { - recp = s->repo->idarraydata + s->recommends; - while ((rec = *recp++) != 0) - { - FOR_PROVIDES(p, pp, rec) - if (!MAPTST(m, p)) - queue_push(&q, p); - } - } - if (s->suggests) - { - sugp = s->repo->idarraydata + s->suggests; - while ((sug = *sugp++) != 0) - { - FOR_PROVIDES(p, pp, sug) - if (!MAPTST(m, p)) - queue_push(&q, p); - } - } - } - queue_free(&q); - POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforsolvable end -----\n"); -} - -static void -addrpmrulesforweak(Solver *solv, Map *m) -{ - Pool *pool = solv->pool; - Solvable *s; - Id sup, *supp; - int i, n; - - POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforweak -----\n"); - for (i = n = 1; n < pool->nsolvables; i++, n++) - { - if (i == pool->nsolvables) - i = 1; - if (MAPTST(m, i)) - continue; - s = pool->solvables + i; - if (!pool_installable(pool, s)) - continue; - sup = 0; - if (s->supplements) - { - supp = s->repo->idarraydata + s->supplements; - while ((sup = *supp++) != ID_NULL) - if (dep_possible(solv, sup, m)) - break; - } - if (!sup && s->freshens) - { - supp = s->repo->idarraydata + s->freshens; - while ((sup = *supp++) != ID_NULL) - if (dep_possible(solv, sup, m)) - break; - } - if (!sup && s->enhances) - { - supp = s->repo->idarraydata + s->enhances; - while ((sup = *supp++) != ID_NULL) - if (dep_possible(solv, sup, m)) - break; - } - if (!sup) - continue; - addrpmrulesforsolvable(solv, s, m); - n = 0; - } - POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforweak end -----\n"); -} - -static void -addrpmrulesforupdaters(Solver *solv, Solvable *s, Map *m, int allowall) -{ - Pool *pool = solv->pool; - int i; - Queue qs; - Id qsbuf[64]; - - POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforupdaters -----\n"); - - queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf)); - policy_findupdatepackages(solv, s, &qs, allowall); - if (!MAPTST(m, s - pool->solvables)) /* add rule for s if not already done */ - addrpmrulesforsolvable(solv, s, m); - for (i = 0; i < qs.count; i++) - if (!MAPTST(m, qs.elements[i])) - addrpmrulesforsolvable(solv, pool->solvables + qs.elements[i], m); - queue_free(&qs); - - POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforupdaters -----\n"); -} - -/* - * add rule for update - * (A|A1|A2|A3...) An = update candidates for A - * - * s = (installed) solvable - */ - -static void -addupdaterule(Solver *solv, Solvable *s, int allowall) -{ - /* installed packages get a special upgrade allowed rule */ - Pool *pool = solv->pool; - Id d; - Queue qs; - Id qsbuf[64]; - - POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addupdaterule -----\n"); - - queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf)); - policy_findupdatepackages(solv, s, &qs, allowall); - if (qs.count == 0) /* no updaters found */ - d = 0; - else - d = pool_queuetowhatprovides(pool, &qs); /* intern computed queue */ - queue_free(&qs); - addrule(solv, s - pool->solvables, d); /* allow update of s */ - POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addupdaterule end -----\n"); -} - - -/*-----------------------------------------------------------------*/ -/* watches */ - - -/* - * makewatches - * - * initial setup for all watches - */ - -static void -makewatches(Solver *solv) -{ - Rule *r; - int i; - int nsolvables = solv->pool->nsolvables; - - sat_free(solv->watches); - /* lower half for removals, upper half for installs */ - solv->watches = sat_calloc(2 * nsolvables, sizeof(Id)); -#if 1 - /* do it reverse so rpm rules get triggered first (XXX: obsolete?) */ - for (i = 1, r = solv->rules + solv->nrules - 1; i < solv->nrules; i++, r--) -#else - for (i = 1, r = solv->rules + 1; i < solv->nrules; i++, r++) -#endif - { - if (!r->w1 /* rule is disabled */ - || !r->w2) /* rule is assertion */ - continue; - - /* see addwatches(solv, r) */ - r->n1 = solv->watches[nsolvables + r->w1]; - solv->watches[nsolvables + r->w1] = r - solv->rules; - - r->n2 = solv->watches[nsolvables + r->w2]; - solv->watches[nsolvables + r->w2] = r - solv->rules; - } -} - - -/* - * add watches (for rule) - */ - -static void -addwatches(Solver *solv, Rule *r) -{ - int nsolvables = solv->pool->nsolvables; + int nsolvables = solv->pool->nsolvables; r->n1 = solv->watches[nsolvables + r->w1]; solv->watches[nsolvables + r->w1] = r - solv->rules; @@ -1318,48 +456,77 @@ addwatches(Solver *solv, Rule *r) } -/*-----------------------------------------------------------------*/ -/* rule propagation */ +/********************************************************************/ +/* + * rule propagation + */ + +/* shortcuts to check if a literal (positive or negative) assignment + * evaluates to 'true' or 'false' + */ #define DECISIONMAP_TRUE(p) ((p) > 0 ? (decisionmap[p] > 0) : (decisionmap[-p] < 0)) #define DECISIONMAP_FALSE(p) ((p) > 0 ? (decisionmap[p] < 0) : (decisionmap[-p] > 0)) +#define DECISIONMAP_UNDEF(p) (decisionmap[(p) > 0 ? (p) : -(p)] == 0) -/* +/*------------------------------------------------------------------- + * * propagate * - * propagate decision to all rules + * make decision and propagate to all rules + * + * Evaluate each term affected by the decision (linked through watches) + * If we find unit rules we make new decisions based on them + * + * Everything's fixed there, it's just finding rules that are + * unit. + * * return : 0 = everything is OK - * watched rule = there is a conflict + * rule = conflict found in this rule */ static Rule * propagate(Solver *solv, int level) { Pool *pool = solv->pool; - Id *rp, *nrp; - Rule *r; - Id p, pkg, ow; + Id *rp, *next_rp; /* rule pointer, next rule pointer in linked list */ + Rule *r; /* rule */ + Id p, pkg, other_watch; Id *dp; Id *decisionmap = solv->decisionmap; - Id *watches = solv->watches + pool->nsolvables; + + Id *watches = solv->watches + pool->nsolvables; /* place ptr in middle */ POOL_DEBUG(SAT_DEBUG_PROPAGATE, "----- propagate -----\n"); + /* foreach non-propagated decision */ while (solv->propagate_index < solv->decisionq.count) { - /* negate because our watches trigger if literal goes FALSE */ + /* + * 'pkg' was just decided + * negate because our watches trigger if literal goes FALSE + */ pkg = -solv->decisionq.elements[solv->propagate_index++]; + IF_POOLDEBUG (SAT_DEBUG_PROPAGATE) { POOL_DEBUG(SAT_DEBUG_PROPAGATE, "propagate for decision %d level %d\n", -pkg, level); solver_printruleelement(solv, SAT_DEBUG_PROPAGATE, 0, -pkg); - if (0) - solver_printwatches(solv, SAT_DEBUG_SCHUBI); } - for (rp = watches + pkg; *rp; rp = nrp) + /* foreach rule where 'pkg' is now FALSE */ + for (rp = watches + pkg; *rp; rp = next_rp) { r = solv->rules + *rp; + if (r->d < 0) + { + /* rule is disabled, goto next */ + if (pkg == r->w1) + next_rp = &r->n1; + else + next_rp = &r->n2; + continue; + } IF_POOLDEBUG (SAT_DEBUG_PROPAGATE) { @@ -1367,43 +534,80 @@ propagate(Solver *solv, int level) solver_printrule(solv, SAT_DEBUG_PROPAGATE, r); } + /* 'pkg' was just decided (was set to FALSE) + * + * now find other literal watch, check clause + * and advance on linked list + */ if (pkg == r->w1) { - ow = r->w2; /* regard the second watchpoint to come to a solution */ - nrp = &r->n1; + other_watch = r->w2; + next_rp = &r->n1; } else { - ow = r->w1; /* regard the first watchpoint to come to a solution */ - nrp = &r->n2; + other_watch = r->w1; + next_rp = &r->n2; } - /* if clause is TRUE, nothing to do */ - if (DECISIONMAP_TRUE(ow)) + + /* + * This term is already true (through the other literal) + * so we have nothing to do + */ + if (DECISIONMAP_TRUE(other_watch)) continue; + /* + * The other literal is FALSE or UNDEF + * + */ + if (r->d) { - /* not a binary clause, check if we need to move our watch */ - /* search for a literal that is not ow and not false */ - /* (true is also ok, in that case the rule is fulfilled) */ - if (r->p && r->p != ow && !DECISIONMAP_TRUE(-r->p)) - p = r->p; - else - for (dp = pool->whatprovidesdata + r->d; (p = *dp++) != 0;) - if (p != ow && !DECISIONMAP_TRUE(-p)) - break; + /* Not a binary clause, try to move our watch. + * + * Go over all literals and find one that is + * not other_watch + * and not FALSE + * + * (TRUE is also ok, in that case the rule is fulfilled) + */ + if (r->p /* we have a 'p' */ + && r->p != other_watch /* which is not watched */ + && !DECISIONMAP_FALSE(r->p)) /* and not FALSE */ + { + p = r->p; + } + else /* go find a 'd' to make 'true' */ + { + /* foreach p in 'd' + we just iterate sequentially, doing it in another order just changes the order of decisions, not the decisions itself + */ + for (dp = pool->whatprovidesdata + r->d; (p = *dp++) != 0;) + { + if (p != other_watch /* which is not watched */ + && !DECISIONMAP_FALSE(p)) /* and not FALSE */ + break; + } + } + if (p) { - /* p is free to watch, move watch to p */ + /* + * if we found some p that is UNDEF or TRUE, move + * watch to it + */ IF_POOLDEBUG (SAT_DEBUG_PROPAGATE) { if (p > 0) - POOL_DEBUG(SAT_DEBUG_PROPAGATE, " -> move w%d to %s\n", (pkg == r->w1 ? 1 : 2), solvable2str(pool, pool->solvables + p)); + POOL_DEBUG(SAT_DEBUG_PROPAGATE, " -> move w%d to %s\n", (pkg == r->w1 ? 1 : 2), solvid2str(pool, p)); else - POOL_DEBUG(SAT_DEBUG_PROPAGATE," -> move w%d to !%s\n", (pkg == r->w1 ? 1 : 2), solvable2str(pool, pool->solvables - p)); + POOL_DEBUG(SAT_DEBUG_PROPAGATE," -> move w%d to !%s\n", (pkg == r->w1 ? 1 : 2), solvid2str(pool, -p)); } - *rp = *nrp; - nrp = rp; + + *rp = *next_rp; + next_rp = rp; + if (pkg == r->w1) { r->w1 = p; @@ -1417,41 +621,54 @@ propagate(Solver *solv, int level) watches[p] = r - solv->rules; continue; } - } - /* unit clause found, set other watch to TRUE */ - if (DECISIONMAP_TRUE(-ow)) - return r; /* eek, a conflict! */ + /* search failed, thus all unwatched literals are FALSE */ + + } /* not binary */ + + /* + * unit clause found, set literal other_watch to TRUE + */ + + if (DECISIONMAP_FALSE(other_watch)) /* check if literal is FALSE */ + return r; /* eek, a conflict! */ + IF_POOLDEBUG (SAT_DEBUG_PROPAGATE) { POOL_DEBUG(SAT_DEBUG_PROPAGATE, " unit "); solver_printrule(solv, SAT_DEBUG_PROPAGATE, r); } - if (ow > 0) - decisionmap[ow] = level; + + if (other_watch > 0) + decisionmap[other_watch] = level; /* install! */ else - decisionmap[-ow] = -level; - queue_push(&solv->decisionq, ow); + decisionmap[-other_watch] = -level; /* remove! */ + + queue_push(&solv->decisionq, other_watch); queue_push(&solv->decisionq_why, r - solv->rules); + IF_POOLDEBUG (SAT_DEBUG_PROPAGATE) { - Solvable *s = pool->solvables + (ow > 0 ? ow : -ow); - if (ow > 0) - POOL_DEBUG(SAT_DEBUG_PROPAGATE, " -> decided to install %s\n", solvable2str(pool, s)); + if (other_watch > 0) + POOL_DEBUG(SAT_DEBUG_PROPAGATE, " -> decided to install %s\n", solvid2str(pool, other_watch)); else - POOL_DEBUG(SAT_DEBUG_PROPAGATE, " -> decided to conflict %s\n", solvable2str(pool, s)); + POOL_DEBUG(SAT_DEBUG_PROPAGATE, " -> decided to conflict %s\n", solvid2str(pool, -other_watch)); } - } - } + + } /* foreach rule involving 'pkg' */ + + } /* while we have non-decided decisions */ + POOL_DEBUG(SAT_DEBUG_PROPAGATE, "----- propagate end-----\n"); return 0; /* all is well */ } -/*-----------------------------------------------------------------*/ +/********************************************************************/ /* Analysis */ -/* +/*------------------------------------------------------------------- + * * analyze * and learn */ @@ -1463,7 +680,7 @@ analyze(Solver *solv, int level, Rule *c, int *pr, int *dr, int *whyp) Queue r; int rlevel = 1; Map seen; /* global? */ - Id v, vv, *dp, why; + Id d, v, vv, *dp, why; int l, i, idx; int num = 0, l1num = 0; int learnt_why = solv->learnt_pool.count; @@ -1479,13 +696,14 @@ analyze(Solver *solv, int level, Rule *c, int *pr, int *dr, int *whyp) IF_POOLDEBUG (SAT_DEBUG_ANALYZE) solver_printruleclass(solv, SAT_DEBUG_ANALYZE, c); queue_push(&solv->learnt_pool, c - solv->rules); - dp = c->d ? pool->whatprovidesdata + c->d : 0; + d = c->d < 0 ? -c->d - 1 : c->d; + dp = d ? pool->whatprovidesdata + d : 0; /* go through all literals of the rule */ for (i = -1; ; i++) { if (i == -1) v = c->p; - else if (c->d == 0) + else if (d == 0) v = i ? 0 : c->w2; else v = *dp++; @@ -1540,7 +758,7 @@ l1retry: goto l1retry; } why = solv->decisionq_why.elements[idx]; - if (!why) /* just in case, maye for SYSTEMSOLVABLE */ + if (why <= 0) /* just in case, maybe for SYSTEMSOLVABLE */ goto l1retry; c = solv->rules + why; } @@ -1563,36 +781,38 @@ l1retry: queue_push(&solv->learnt_pool, 0); if (whyp) *whyp = learnt_why; + solv->stats_learned++; return rlevel; } -/* - * reset_solver +/*------------------------------------------------------------------- + * + * solver_reset + * * reset the solver decisions to right after the rpm rules. * called after rules have been enabled/disabled */ -static void -reset_solver(Solver *solv) +void +solver_reset(Solver *solv) { Pool *pool = solv->pool; int i; Id v; - /* rewind decisions to direct rpm rule assertions */ - for (i = solv->decisionq.count - 1; i >= solv->directdecisions; i--) + /* rewind all decisions */ + for (i = solv->decisionq.count - 1; i >= 0; i--) { v = solv->decisionq.elements[i]; solv->decisionmap[v > 0 ? v : -v] = 0; } - - POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "decisions done reduced from %d to %d\n", solv->decisionq.count, solv->directdecisions); - - solv->decisionq_why.count = solv->directdecisions; - solv->decisionq.count = solv->directdecisions; + solv->decisionq_why.count = 0; + solv->decisionq.count = 0; solv->recommends_index = -1; solv->propagate_index = 0; + solv->recommendations.count = 0; + solv->branches.count = 0; /* adapt learnt rule status to new set of enabled/disabled rules */ enabledisablelearntrules(solv); @@ -1600,13 +820,11 @@ reset_solver(Solver *solv) /* redo all job/update decisions */ makeruledecisions(solv); POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "decisions so far: %d\n", solv->decisionq.count); - - /* recreate watch chains */ - makewatches(solv); } -/* +/*------------------------------------------------------------------- + * * analyze_unsolvable_rule */ @@ -1630,11 +848,25 @@ analyze_unsolvable_rule(Solver *solv, Rule *r, Id *lastweakp) if (!*lastweakp || why > *lastweakp) *lastweakp = why; /* do not add rpm rules to problem */ - if (why < solv->jobrules) + if (why < solv->rpmrules_end) return; /* turn rule into problem */ - if (why >= solv->jobrules && why < solv->updaterules) + if (why >= solv->jobrules && why < solv->jobrules_end) why = -(solv->ruletojob.elements[why - solv->jobrules] + 1); + /* normalize dup/infarch rules */ + if (why > solv->infarchrules && why < solv->infarchrules_end) + { + Id name = pool->solvables[-solv->rules[why].p].name; + while (why > solv->infarchrules && pool->solvables[-solv->rules[why - 1].p].name == name) + why--; + } + if (why > solv->duprules && why < solv->duprules_end) + { + Id name = pool->solvables[-solv->rules[why].p].name; + while (why > solv->duprules && pool->solvables[-solv->rules[why - 1].p].name == name) + why--; + } + /* return if problem already countains our rule */ if (solv->problems.count) { @@ -1648,7 +880,8 @@ analyze_unsolvable_rule(Solver *solv, Rule *r, Id *lastweakp) } -/* +/*------------------------------------------------------------------- + * * analyze_unsolvable * * return: 1 - disabled some rules, try again @@ -1661,7 +894,7 @@ analyze_unsolvable(Solver *solv, Rule *cr, int disablerules) Pool *pool = solv->pool; Rule *r; Map seen; /* global to speed things up? */ - Id v, vv, *dp, why; + Id d, v, vv, *dp, why; int l, i, idx; Id *decisionmap = solv->decisionmap; int oldproblemcount; @@ -1669,6 +902,7 @@ analyze_unsolvable(Solver *solv, Rule *cr, int disablerules) Id lastweak; POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "ANALYZE UNSOLVABLE ----------------------\n"); + solv->stats_unsolvable++; oldproblemcount = solv->problems.count; oldlearntpoolcount = solv->learnt_pool.count; @@ -1682,12 +916,13 @@ analyze_unsolvable(Solver *solv, Rule *cr, int disablerules) queue_push(&solv->learnt_pool, r - solv->rules); lastweak = 0; analyze_unsolvable_rule(solv, r, &lastweak); - dp = r->d ? pool->whatprovidesdata + r->d : 0; + d = r->d < 0 ? -r->d - 1 : r->d; + dp = d ? pool->whatprovidesdata + d : 0; for (i = -1; ; i++) { if (i == -1) v = r->p; - else if (r->d == 0) + else if (d == 0) v = i ? 0 : r->w2; else v = *dp++; @@ -1709,15 +944,17 @@ analyze_unsolvable(Solver *solv, Rule *cr, int disablerules) if (!MAPTST(&seen, vv)) continue; why = solv->decisionq_why.elements[idx]; + assert(why > 0); queue_push(&solv->learnt_pool, why); r = solv->rules + why; analyze_unsolvable_rule(solv, r, &lastweak); - dp = r->d ? pool->whatprovidesdata + r->d : 0; + d = r->d < 0 ? -r->d - 1 : r->d; + dp = d ? pool->whatprovidesdata + d : 0; for (i = -1; ; i++) { if (i == -1) v = r->p; - else if (r->d == 0) + else if (d == 0) v = i ? 0 : r->w2; else v = *dp++; @@ -1737,14 +974,20 @@ analyze_unsolvable(Solver *solv, Rule *cr, int disablerules) if (lastweak) { + Id v; /* disable last weak rule */ solv->problems.count = oldproblemcount; solv->learnt_pool.count = oldlearntpoolcount; - r = solv->rules + lastweak; + if (lastweak >= solv->jobrules && lastweak < solv->jobrules_end) + v = -(solv->ruletojob.elements[lastweak - solv->jobrules] + 1); + else + v = lastweak; POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "disabling "); - solver_printruleclass(solv, SAT_DEBUG_UNSOLVABLE, r); - disablerule(solv, r); - reset_solver(solv); + solver_printruleclass(solv, SAT_DEBUG_UNSOLVABLE, solv->rules + lastweak); + solver_disableproblem(solv, v); + if (v < 0) + solver_reenablepolicyrules(solv, -(v + 1)); + solver_reset(solv); return 1; } @@ -1755,9 +998,9 @@ analyze_unsolvable(Solver *solv, Rule *cr, int disablerules) if (disablerules) { for (i = oldproblemcount + 1; i < solv->problems.count - 1; i++) - disableproblem(solv, solv->problems.elements[i]); + solver_disableproblem(solv, solv->problems.elements[i]); /* XXX: might want to enable all weak rules again */ - reset_solver(solv); + solver_reset(solv); return 1; } POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "UNSOLVABLE\n"); @@ -1765,10 +1008,11 @@ analyze_unsolvable(Solver *solv, Rule *cr, int disablerules) } -/*-----------------------------------------------------------------*/ +/********************************************************************/ /* Decision revert */ -/* +/*------------------------------------------------------------------- + * * revert * revert decision at level */ @@ -1802,7 +1046,8 @@ revert(Solver *solv, int level) } -/* +/*------------------------------------------------------------------- + * * watch2onhighest - put watch2 on literal with highest level */ @@ -1810,11 +1055,12 @@ static inline void watch2onhighest(Solver *solv, Rule *r) { int l, wl = 0; - Id v, *dp; + Id d, v, *dp; - if (!r->d) + d = r->d < 0 ? -r->d - 1 : r->d; + if (!d) return; /* binary rule, both watches are set */ - dp = solv->pool->whatprovidesdata + r->d; + dp = solv->pool->whatprovidesdata + d; while ((v = *dp++) != 0) { l = solv->decisionmap[v < 0 ? -v : v]; @@ -1829,11 +1075,14 @@ watch2onhighest(Solver *solv, Rule *r) } -/* +/*------------------------------------------------------------------- + * * setpropagatelearn * - * add free decision to decisionq, increase level and - * propagate decision, return if no conflict. + * add free decision (solvable to install) to decisionq + * increase level and propagate decision + * return if no conflict. + * * in conflict case, analyze conflict rule, add resulting * rule to learnt rule set, make decision from learnt * rule (always unit) and re-propagate. @@ -1843,13 +1092,14 @@ watch2onhighest(Solver *solv, Rule *r) */ static int -setpropagatelearn(Solver *solv, int level, Id decision, int disablerules) +setpropagatelearn(Solver *solv, int level, Id decision, int disablerules, Id ruleid) { Pool *pool = solv->pool; Rule *r; Id p = 0, d = 0; int l, why; + assert(ruleid >= 0); if (decision) { level++; @@ -1858,7 +1108,7 @@ setpropagatelearn(Solver *solv, int level, Id decision, int disablerules) else solv->decisionmap[-decision] = -level; queue_push(&solv->decisionq, decision); - queue_push(&solv->decisionq_why, 0); + queue_push(&solv->decisionq_why, -ruleid); /* <= 0 -> free decision */ } for (;;) { @@ -1873,7 +1123,7 @@ setpropagatelearn(Solver *solv, int level, Id decision, int disablerules) POOL_DEBUG(SAT_DEBUG_ANALYZE, "reverting decisions (level %d -> %d)\n", level, l); level = l; revert(solv, level); - r = addrule(solv, p, d); /* p requires d */ + r = solver_addrule(solv, p, d); assert(r); assert(solv->learnt_why.count == (r - solv->rules) - solv->learntrules); queue_push(&solv->learnt_why, why); @@ -1881,8 +1131,14 @@ setpropagatelearn(Solver *solv, int level, Id decision, int disablerules) { /* at least 2 literals, needs watches */ watch2onhighest(solv, r); - addwatches(solv, r); + addwatches_rule(solv, r); + } + else + { + /* learnt rule is an assertion */ + queue_push(&solv->ruleassertions, r - solv->rules); } + /* the new rule is unit by design */ solv->decisionmap[p > 0 ? p : -p] = p > 0 ? level : -level; queue_push(&solv->decisionq, p); queue_push(&solv->decisionq_why, r - solv->rules); @@ -1898,51 +1154,61 @@ setpropagatelearn(Solver *solv, int level, Id decision, int disablerules) } -/* +/*------------------------------------------------------------------- + * + * select and install + * * install best package from the queue. We add an extra package, inst, if * provided. See comment in weak install section. * * returns the new solver level or 0 if unsolvable * */ + static int -selectandinstall(Solver *solv, int level, Queue *dq, Id inst, int disablerules) +selectandinstall(Solver *solv, int level, Queue *dq, int disablerules, Id ruleid) { Pool *pool = solv->pool; Id p; int i; - if (dq->count > 1 || inst) - policy_filter_unwanted(solv, dq, inst, POLICY_MODE_CHOOSE); - - i = 0; + if (dq->count > 1) + policy_filter_unwanted(solv, dq, POLICY_MODE_CHOOSE); if (dq->count > 1) { + /* XXX: didn't we already do that? */ + /* XXX: shouldn't we prefer installed packages? */ + /* XXX: move to policy.c? */ /* choose the supplemented one */ for (i = 0; i < dq->count; i++) if (solver_is_supplementing(solv, pool->solvables + dq->elements[i])) - break; - if (i == dq->count) - { - for (i = 1; i < dq->count; i++) - queue_push(&solv->branches, dq->elements[i]); - queue_push(&solv->branches, -level); - i = 0; - } + { + dq->elements[0] = dq->elements[i]; + dq->count = 1; + break; + } + } + if (dq->count > 1) + { + /* multiple candidates, open a branch */ + for (i = 1; i < dq->count; i++) + queue_push(&solv->branches, dq->elements[i]); + queue_push(&solv->branches, -level); } - p = dq->elements[i]; + p = dq->elements[0]; - POOL_DEBUG(SAT_DEBUG_POLICY, "installing %s\n", solvable2str(pool, pool->solvables + p)); + POOL_DEBUG(SAT_DEBUG_POLICY, "installing %s\n", solvid2str(pool, p)); - return setpropagatelearn(solv, level, p, disablerules); + return setpropagatelearn(solv, level, p, disablerules, ruleid); } -/*-----------------------------------------------------------------*/ +/********************************************************************/ /* Main solver interface */ -/* +/*------------------------------------------------------------------- + * * solver_create * create solver structure * @@ -1955,28 +1221,32 @@ selectandinstall(Solver *solv, int level, Queue *dq, Id inst, int disablerules) */ Solver * -solver_create(Pool *pool, Repo *installed) +solver_create(Pool *pool) { Solver *solv; solv = (Solver *)sat_calloc(1, sizeof(Solver)); solv->pool = pool; - solv->installed = installed; + solv->installed = pool->installed; + queue_init(&solv->transaction); + queue_init(&solv->transaction_info); queue_init(&solv->ruletojob); queue_init(&solv->decisionq); queue_init(&solv->decisionq_why); queue_init(&solv->problems); queue_init(&solv->suggestions); queue_init(&solv->recommendations); + queue_init(&solv->orphaned); queue_init(&solv->learnt_why); queue_init(&solv->learnt_pool); queue_init(&solv->branches); queue_init(&solv->covenantq); queue_init(&solv->weakruleq); + queue_init(&solv->ruleassertions); map_init(&solv->recommendsmap, pool->nsolvables); map_init(&solv->suggestsmap, pool->nsolvables); - map_init(&solv->noupdate, installed ? installed->end - installed->start : 0); + map_init(&solv->noupdate, solv->installed ? solv->installed->end - solv->installed->start : 0); solv->recommends_index = 0; solv->decisionmap = (Id *)sat_calloc(pool->nsolvables, sizeof(Id)); @@ -1988,52 +1258,66 @@ solver_create(Pool *pool, Repo *installed) } -/* +/*------------------------------------------------------------------- + * * solver_free */ void solver_free(Solver *solv) { + queue_free(&solv->transaction); + queue_free(&solv->transaction_info); + queue_free(&solv->job); queue_free(&solv->ruletojob); queue_free(&solv->decisionq); queue_free(&solv->decisionq_why); queue_free(&solv->learnt_why); queue_free(&solv->learnt_pool); queue_free(&solv->problems); + queue_free(&solv->solutions); queue_free(&solv->suggestions); queue_free(&solv->recommendations); + queue_free(&solv->orphaned); queue_free(&solv->branches); queue_free(&solv->covenantq); queue_free(&solv->weakruleq); + queue_free(&solv->ruleassertions); map_free(&solv->recommendsmap); map_free(&solv->suggestsmap); map_free(&solv->noupdate); map_free(&solv->weakrulemap); + map_free(&solv->noobsoletes); + + map_free(&solv->updatemap); + map_free(&solv->dupmap); + map_free(&solv->dupinvolvedmap); sat_free(solv->decisionmap); sat_free(solv->rules); sat_free(solv->watches); sat_free(solv->obsoletes); sat_free(solv->obsoletes_data); + sat_free(solv->multiversionupdaters); + sat_free(solv->transaction_installed); sat_free(solv); } -/*-------------------------------------------------------*/ - -/* - * run_solver +/*------------------------------------------------------------------- + * + * solver_run_sat * * all rules have been set up, now actually run the solver * */ -static void -run_solver(Solver *solv, int disablerules, int doweak) +void +solver_run_sat(Solver *solv, int disablerules, int doweak) { - Queue dq; + Queue dq; /* local decisionqueue */ + Queue dqs; /* local decisionqueue for supplements */ int systemlevel; int level, olevel; Rule *r; @@ -2041,6 +1325,7 @@ run_solver(Solver *solv, int disablerules, int doweak) Solvable *s; Pool *pool = solv->pool; Id p, *dp; + int minimizationsteps; IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION) { @@ -2060,6 +1345,7 @@ run_solver(Solver *solv, int disablerules, int doweak) POOL_DEBUG(SAT_DEBUG_STATS, "solving...\n"); queue_init(&dq); + queue_init(&dqs); /* * here's the main loop: @@ -2072,6 +1358,7 @@ run_solver(Solver *solv, int disablerules, int doweak) * with step 1 */ + minimizationsteps = 0; for (;;) { /* @@ -2086,107 +1373,186 @@ run_solver(Solver *solv, int disablerules, int doweak) if (analyze_unsolvable(solv, r, disablerules)) continue; queue_free(&dq); + queue_free(&dqs); return; } } - /* - * installed packages - */ - - if (level < systemlevel && solv->installed && solv->installed->nsolvables) + if (level < systemlevel) { - if (!solv->updatesystem) + POOL_DEBUG(SAT_DEBUG_STATS, "resolving job rules\n"); + for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++) { - /* try to keep as many packages as possible */ - POOL_DEBUG(SAT_DEBUG_STATS, "installing old packages\n"); - for (i = solv->installed->start; i < solv->installed->end; i++) + Id l; + if (r->d < 0) /* ignore disabled rules */ + continue; + queue_empty(&dq); + FOR_RULELITERALS(l, dp, r) { - s = pool->solvables + i; - if (s->repo != solv->installed) - continue; - if (solv->decisionmap[i] != 0) - continue; - POOL_DEBUG(SAT_DEBUG_PROPAGATE, "keeping %s\n", solvable2str(pool, s)); - olevel = level; - level = setpropagatelearn(solv, level, i, disablerules); - if (level == 0) + if (l < 0) { - queue_free(&dq); - return; + if (solv->decisionmap[-l] <= 0) + break; + } + else + { + if (solv->decisionmap[l] > 0) + break; + if (solv->decisionmap[l] == 0) + queue_push(&dq, l); } - if (level <= olevel) - break; } - if (i < solv->installed->end) + if (l || !dq.count) continue; - } - POOL_DEBUG(SAT_DEBUG_STATS, "resolving update/feature rules\n"); - for (i = solv->installed->start, r = solv->rules + solv->updaterules; i < solv->installed->end; i++, r++) - { - Rule *rr; - s = pool->solvables + i; - if (s->repo != solv->installed) - continue; - if (solv->decisionmap[i] > 0) - continue; - /* noupdate is set if a job is erasing the installed solvable or installing a specific version */ - if (MAPTST(&solv->noupdate, i - solv->installed->start)) - continue; - queue_empty(&dq); - if (!solv->allowuninstall) - { - rr = r; - if (!rr->w1) - rr += solv->installed->end - solv->installed->start; - } - else - rr = solv->rules + solv->featurerules + (i - solv->installed->start); - if (rr->d == 0) + /* prune to installed if not updating */ + if (!solv->updatesystem && solv->installed && dq.count > 1) { - if (!rr->w2 || solv->decisionmap[rr->w2] > 0) - continue; - if (solv->decisionmap[rr->w2] == 0) - queue_push(&dq, rr->w2); - } - else - { - dp = pool->whatprovidesdata + rr->d; - while ((p = *dp++) != 0) + int j, k; + for (j = k = 0; j < dq.count; j++) { - if (solv->decisionmap[p] > 0) - break; - if (solv->decisionmap[p] == 0) - queue_push(&dq, p); + Solvable *s = pool->solvables + dq.elements[j]; + if (s->repo == solv->installed) + dq.elements[k++] = dq.elements[j]; } - if (p) - continue; + if (k) + dq.count = k; } - if (!dq.count && solv->decisionmap[i] != 0) - continue; olevel = level; - /* FIXME: i is handled a bit different because we do not want - * to have it pruned just because it is not recommened. - * we should not prune installed packages instead */ - level = selectandinstall(solv, level, &dq, (solv->decisionmap[i] ? 0 : i), disablerules); + level = selectandinstall(solv, level, &dq, disablerules, i); if (level == 0) { queue_free(&dq); + queue_free(&dqs); return; } if (level <= olevel) break; } - if (i < solv->installed->end) + systemlevel = level + 1; + if (i < solv->jobrules_end) continue; - systemlevel = level; } + + /* + * installed packages + */ + + if (level < systemlevel && solv->installed && solv->installed->nsolvables) + { + Repo *installed = solv->installed; + int pass; + + /* we use two passes if we need to update packages + * to create a better user experience */ + for (pass = solv->updatemap.size ? 0 : 1; pass < 2; pass++) + { + FOR_REPO_SOLVABLES(installed, i, s) + { + Rule *rr; + Id d; + + /* XXX: noupdate check is probably no longer needed, as all jobs should + * already be satisfied */ + if (MAPTST(&solv->noupdate, i - installed->start)) + continue; + if (solv->decisionmap[i] > 0) + continue; + if (!pass && solv->updatemap.size && !MAPTST(&solv->updatemap, i - installed->start)) + continue; /* updates first */ + r = solv->rules + solv->updaterules + (i - installed->start); + rr = r; + if (!rr->p || rr->d < 0) /* disabled -> look at feature rule */ + rr -= solv->installed->end - solv->installed->start; + if (!rr->p) /* identical to update rule? */ + rr = r; + if (!rr->p) + continue; /* orpaned package */ + + queue_empty(&dq); + if (solv->decisionmap[i] < 0 || solv->updatesystem || (solv->updatemap.size && MAPTST(&solv->updatemap, i - installed->start)) || rr->p != i) + { + if (solv->noobsoletes.size && solv->multiversionupdaters + && (d = solv->multiversionupdaters[i - installed->start]) != 0) + { + /* special multiversion handling, make sure best version is chosen */ + queue_push(&dq, i); + while ((p = pool->whatprovidesdata[d++]) != 0) + if (solv->decisionmap[p] >= 0) + queue_push(&dq, p); + policy_filter_unwanted(solv, &dq, POLICY_MODE_CHOOSE); + p = dq.elements[0]; + if (p != i && solv->decisionmap[p] == 0) + { + rr = solv->rules + solv->featurerules + (i - solv->installed->start); + if (!rr->p) /* update rule == feature rule? */ + rr = rr - solv->featurerules + solv->updaterules; + dq.count = 1; + } + else + dq.count = 0; + } + else + { + /* update to best package */ + FOR_RULELITERALS(p, dp, rr) + { + if (solv->decisionmap[p] > 0) + { + dq.count = 0; /* already fulfilled */ + break; + } + if (!solv->decisionmap[p]) + queue_push(&dq, p); + } + } + } + /* install best version */ + if (dq.count) + { + olevel = level; + level = selectandinstall(solv, level, &dq, disablerules, rr - solv->rules); + if (level == 0) + { + queue_free(&dq); + queue_free(&dqs); + return; + } + if (level <= olevel) + break; + } + /* if still undecided keep package */ + if (solv->decisionmap[i] == 0) + { + olevel = level; + POOL_DEBUG(SAT_DEBUG_POLICY, "keeping %s\n", solvid2str(pool, i)); + level = setpropagatelearn(solv, level, i, disablerules, r - solv->rules); + if (level == 0) + { + queue_free(&dq); + queue_free(&dqs); + return; + } + if (level <= olevel) + break; + } + } + if (i < installed->end) + break; + } + systemlevel = level + 1; + if (pass < 2) + continue; /* had trouble, retry */ + } + + if (level < systemlevel) + systemlevel = level; + /* * decide */ - POOL_DEBUG(SAT_DEBUG_STATS, "deciding unresolved rules\n"); + POOL_DEBUG(SAT_DEBUG_POLICY, "deciding unresolved rules\n"); for (i = 1, n = 1; ; i++, n++) { if (n == solv->nrules) @@ -2194,7 +1560,7 @@ run_solver(Solver *solv, int disablerules, int doweak) if (i == solv->nrules) i = 1; r = solv->rules + i; - if (!r->w1) /* ignore disabled rules */ + if (r->d < 0) /* ignore disabled rules */ continue; queue_empty(&dq); if (r->d == 0) @@ -2257,13 +1623,14 @@ run_solver(Solver *solv, int disablerules, int doweak) assert(dq.count > 1); olevel = level; - level = selectandinstall(solv, level, &dq, 0, disablerules); + level = selectandinstall(solv, level, &dq, disablerules, r - solv->rules); if (level == 0) { queue_free(&dq); + queue_free(&dqs); return; } - if (level < systemlevel) + if (level < systemlevel || level == 1) break; n = 0; } /* for(), decide */ @@ -2275,17 +1642,20 @@ run_solver(Solver *solv, int disablerules, int doweak) { int qcount; - POOL_DEBUG(SAT_DEBUG_STATS, "installing recommended packages\n"); - queue_empty(&dq); + POOL_DEBUG(SAT_DEBUG_POLICY, "installing recommended packages\n"); + queue_empty(&dq); /* recommended packages */ + queue_empty(&dqs); /* supplemented packages */ for (i = 1; i < pool->nsolvables; i++) { if (solv->decisionmap[i] < 0) continue; if (solv->decisionmap[i] > 0) { - Id *recp, rec, *pp, p; - s = pool->solvables + i; /* installed, check for recommends */ + Id *recp, rec, pp, p; + s = pool->solvables + i; + if (solv->ignorealreadyrecommended && s->repo == solv->installed) + continue; /* XXX need to special case AND ? */ if (s->recommends) { @@ -2311,772 +1681,345 @@ run_solver(Solver *solv, int disablerules, int doweak) else { s = pool->solvables + i; - if (!s->supplements && !s->freshens) + if (!s->supplements) continue; if (!pool_installable(pool, s)) continue; - if (solver_is_supplementing(solv, s)) - queue_pushunique(&dq, i); + if (!solver_is_supplementing(solv, s)) + continue; + queue_push(&dqs, i); } } - if (dq.count) - { - if (dq.count > 1) - policy_filter_unwanted(solv, &dq, 0, POLICY_MODE_RECOMMEND); - p = dq.elements[0]; - POOL_DEBUG(SAT_DEBUG_STATS, "installing recommended %s\n", solvable2str(pool, pool->solvables + p)); - queue_push(&solv->recommendations, p); - level = setpropagatelearn(solv, level, p, 0); - continue; - } - } - if (solv->solution_callback) - { - solv->solution_callback(solv, solv->solution_callback_data); - if (solv->branches.count) + /* filter out all packages obsoleted by installed packages */ + /* this is no longer needed if we have reverse obsoletes */ + if ((dqs.count || dq.count) && solv->installed) { - int i = solv->branches.count - 1; - int l = -solv->branches.elements[i]; - for (; i > 0; i--) - if (solv->branches.elements[i - 1] < 0) - break; - p = solv->branches.elements[i]; - POOL_DEBUG(SAT_DEBUG_STATS, "branching with %s\n", solvable2str(pool, pool->solvables + p)); - queue_empty(&dq); - for (j = i + 1; j < solv->branches.count; j++) - queue_push(&dq, solv->branches.elements[j]); - solv->branches.count = i; - level = l; - revert(solv, level); - if (dq.count > 1) - for (j = 0; j < dq.count; j++) - queue_push(&solv->branches, dq.elements[j]); - olevel = level; - level = setpropagatelearn(solv, level, p, disablerules); - if (level == 0) + Map obsmap; + Id obs, *obsp, po, ppo; + + map_init(&obsmap, pool->nsolvables); + for (p = solv->installed->start; p < solv->installed->end; p++) { - queue_free(&dq); - return; + s = pool->solvables + p; + if (s->repo != solv->installed || !s->obsoletes) + continue; + if (solv->decisionmap[p] <= 0) + continue; + if (solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p)) + continue; + obsp = s->repo->idarraydata + s->obsoletes; + /* foreach obsoletes */ + while ((obs = *obsp++) != 0) + FOR_PROVIDES(po, ppo, obs) + MAPSET(&obsmap, po); } - continue; - } - /* all branches done, we're finally finished */ - break; - } - - /* minimization step */ - if (solv->branches.count) - { - int l = 0, lasti = -1, lastl = -1; - p = 0; - for (i = solv->branches.count - 1; i >= 0; i--) - { - p = solv->branches.elements[i]; - if (p < 0) - l = -p; - else if (p > 0 && solv->decisionmap[p] > l + 1) + for (i = j = 0; i < dqs.count; i++) + if (!MAPTST(&obsmap, dqs.elements[i])) + dqs.elements[j++] = dqs.elements[i]; + dqs.count = j; + for (i = j = 0; i < dq.count; i++) + if (!MAPTST(&obsmap, dq.elements[i])) + dq.elements[j++] = dq.elements[i]; + dq.count = j; + map_free(&obsmap); + } + + /* filter out all already supplemented packages if requested */ + if (solv->ignorealreadyrecommended && dqs.count) + { + /* turn off all new packages */ + for (i = 0; i < solv->decisionq.count; i++) { - lasti = i; - lastl = l; + p = solv->decisionq.elements[i]; + if (p < 0) + continue; + s = pool->solvables + p; + if (s->repo && s->repo != solv->installed) + solv->decisionmap[p] = -solv->decisionmap[p]; + } + /* filter out old supplements */ + for (i = j = 0; i < dqs.count; i++) + { + p = dqs.elements[i]; + s = pool->solvables + p; + if (!s->supplements) + continue; + if (!solver_is_supplementing(solv, s)) + dqs.elements[j++] = p; + } + dqs.count = j; + /* undo turning off */ + for (i = 0; i < solv->decisionq.count; i++) + { + p = solv->decisionq.elements[i]; + if (p < 0) + continue; + s = pool->solvables + p; + if (s->repo && s->repo != solv->installed) + solv->decisionmap[p] = -solv->decisionmap[p]; } } - if (lasti >= 0) - { - /* kill old solvable so that we do not loop */ - p = solv->branches.elements[lasti]; - solv->branches.elements[lasti] = 0; - POOL_DEBUG(SAT_DEBUG_STATS, "minimizing %d -> %d with %s\n", solv->decisionmap[p], l, solvable2str(pool, pool->solvables + p)); - level = lastl; - revert(solv, level); - olevel = level; - level = setpropagatelearn(solv, level, p, disablerules); - if (level == 0) + /* multiversion doesn't mix well with supplements. + * filter supplemented packages where we already decided + * to install a different version (see bnc#501088) */ + if (dqs.count && solv->noobsoletes.size) + { + for (i = j = 0; i < dqs.count; i++) { - queue_free(&dq); - return; + p = dqs.elements[i]; + if (MAPTST(&solv->noobsoletes, p)) + { + Id p2, pp2; + s = pool->solvables + p; + FOR_PROVIDES(p2, pp2, s->name) + if (solv->decisionmap[p2] > 0 && pool->solvables[p2].name == s->name) + break; + if (p2) + continue; /* ignore this package */ + } + dqs.elements[j++] = p; } - continue; + dqs.count = j; } - } - break; - } - POOL_DEBUG(SAT_DEBUG_STATS, "done solving.\n\n"); - queue_free(&dq); -} - - -/* - * refine_suggestion - * at this point, all rules that led to conflicts are disabled. - * we re-enable all rules of a problem set but rule "sug", then - * continue to disable more rules until there as again a solution. - */ - -/* FIXME: think about conflicting assertions */ - -static void -refine_suggestion(Solver *solv, Queue *job, Id *problem, Id sug, Queue *refined) -{ - Pool *pool = solv->pool; - int i, j; - Id v; - Queue disabled; - int disabledcnt; - - IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS) - { - POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "refine_suggestion start\n"); - for (i = 0; problem[i]; i++) - { - if (problem[i] == sug) - POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "=> "); - solver_printproblem(solv, problem[i]); - } - } - queue_init(&disabled); - queue_empty(refined); - queue_push(refined, sug); - /* re-enable all problem rules with the exception of "sug"(gestion) */ - revert(solv, 1); - reset_solver(solv); + /* make dq contain both recommended and supplemented pkgs */ + if (dqs.count) + { + for (i = 0; i < dqs.count; i++) + queue_pushunique(&dq, dqs.elements[i]); + } - for (i = 0; problem[i]; i++) - if (problem[i] != sug) - enableproblem(solv, problem[i]); + if (dq.count) + { + Map dqmap; + int decisioncount = solv->decisionq.count; - if (sug < 0) - disableupdaterules(solv, job, -(sug + 1)); + if (dq.count == 1) + { + /* simple case, just one package. no need to choose */ + p = dq.elements[0]; + if (dqs.count) + POOL_DEBUG(SAT_DEBUG_POLICY, "installing supplemented %s\n", solvid2str(pool, p)); + else + POOL_DEBUG(SAT_DEBUG_POLICY, "installing recommended %s\n", solvid2str(pool, p)); + queue_push(&solv->recommendations, p); + level = setpropagatelearn(solv, level, p, 0, 0); + continue; /* back to main loop */ + } - for (;;) - { - int njob, nfeature, nupdate; - queue_empty(&solv->problems); - enableweakrules(solv); - revert(solv, 1); /* XXX no longer needed? */ - reset_solver(solv); + /* filter packages, this gives us the best versions */ + policy_filter_unwanted(solv, &dq, POLICY_MODE_RECOMMEND); - if (!solv->problems.count) - run_solver(solv, 0, 0); + /* create map of result */ + map_init(&dqmap, pool->nsolvables); + for (i = 0; i < dq.count; i++) + MAPSET(&dqmap, dq.elements[i]); - if (!solv->problems.count) - { - POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "no more problems!\n"); - IF_POOLDEBUG (SAT_DEBUG_SCHUBI) - solver_printdecisions(solv); - break; /* great, no more problems */ - } - disabledcnt = disabled.count; - /* start with 1 to skip over proof index */ - njob = nfeature = nupdate = 0; - for (i = 1; i < solv->problems.count - 1; i++) - { - /* ignore solutions in refined */ - v = solv->problems.elements[i]; - if (v == 0) - break; /* end of problem reached */ - for (j = 0; problem[j]; j++) - if (problem[j] != sug && problem[j] == v) - break; - if (problem[j]) - continue; - if (v >= solv->featurerules && v < solv->learntrules) - nfeature++; - else if (v > 0) - nupdate++; - else - njob++; - queue_push(&disabled, v); - } - if (disabled.count == disabledcnt) - { - /* no solution found, this was an invalid suggestion! */ - POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "no solution found!\n"); - refined->count = 0; - break; - } - if (!njob && nupdate && nfeature) - { - /* got only update rules, filter out feature rules */ - POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "throwing away feature rules\n"); - for (i = j = disabledcnt; i < disabled.count; i++) - { - v = disabled.elements[i]; - if (v < solv->featurerules || v >= solv->learntrules) - disabled.elements[j++] = v; - } - disabled.count = j; - nfeature = 0; - } - if (disabled.count == disabledcnt + 1) - { - /* just one suggestion, add it to refined list */ - v = disabled.elements[disabledcnt]; - if (!nfeature) - queue_push(refined, v); /* do not record feature rules */ - disableproblem(solv, v); - if (v >= solv->updaterules && v < solv->featurerules) - { - Rule *r = solv->rules + v + (solv->installed->end - solv->installed->start); - if (r->p) - enablerule(solv, r); /* enable corresponding feature rule */ - } - if (v < 0) - disableupdaterules(solv, job, -(v + 1)); - } - else - { - /* more than one solution, disable all */ - /* do not push anything on refine list, as we do not know which solution to choose */ - /* thus, the user will get another problem if he selects this solution, where he - * can choose the right one */ - IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS) - { - POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "more than one solution found:\n"); - for (i = disabledcnt; i < disabled.count; i++) - solver_printproblem(solv, disabled.elements[i]); - } - for (i = disabledcnt; i < disabled.count; i++) - { - v = disabled.elements[i]; - disableproblem(solv, v); - if (v >= solv->updaterules && v < solv->featurerules) + /* install all supplemented packages */ + for (i = 0; i < dqs.count; i++) { - Rule *r = solv->rules + v + (solv->installed->end - solv->installed->start); - if (r->p) - enablerule(solv, r); + p = dqs.elements[i]; + if (solv->decisionmap[p] || !MAPTST(&dqmap, p)) + continue; + POOL_DEBUG(SAT_DEBUG_POLICY, "installing supplemented %s\n", solvid2str(pool, p)); + queue_push(&solv->recommendations, p); + olevel = level; + level = setpropagatelearn(solv, level, p, 0, 0); + if (level <= olevel) + break; + } + if (i < dqs.count || solv->decisionq.count < decisioncount) + { + map_free(&dqmap); + continue; } - } - } - } - /* all done, get us back into the same state as before */ - /* enable refined rules again */ - for (i = 0; i < disabled.count; i++) - enableproblem(solv, disabled.elements[i]); - /* disable problem rules again */ - for (i = 0; problem[i]; i++) - disableproblem(solv, problem[i]); - disableupdaterules(solv, job, -1); - POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "refine_suggestion end\n"); -} - -static void -problems_to_solutions(Solver *solv, Queue *job) -{ - Pool *pool = solv->pool; - Queue problems; - Queue solution; - Queue solutions; - Id *problem; - Id why; - int i, j; - - if (!solv->problems.count) - return; - queue_clone(&problems, &solv->problems); - queue_init(&solution); - queue_init(&solutions); - /* copy over proof index */ - queue_push(&solutions, problems.elements[0]); - problem = problems.elements + 1; - for (i = 1; i < problems.count; i++) - { - Id v = problems.elements[i]; - if (v == 0) - { - /* mark end of this problem */ - queue_push(&solutions, 0); - queue_push(&solutions, 0); - if (i + 1 == problems.count) - break; - /* copy over proof of next problem */ - queue_push(&solutions, problems.elements[i + 1]); - i++; - problem = problems.elements + i + 1; - continue; - } - refine_suggestion(solv, job, problem, v, &solution); - if (!solution.count) - continue; /* this solution didn't work out */ - for (j = 0; j < solution.count; j++) - { - why = solution.elements[j]; - /* must be either job descriptor or update rule */ - assert(why < 0 || (why >= solv->updaterules && why < solv->featurerules)); -#if 0 - solver_printproblem(solv, why); -#endif - if (why < 0) - { - /* job descriptor */ - queue_push(&solutions, 0); - queue_push(&solutions, -why); - } - else - { - /* update rule, find replacement package */ - Id p, rp = 0; - Rule *rr; - p = solv->installed->start + (why - solv->updaterules); - if (solv->decisionmap[p] > 0) - continue; /* false alarm, turned out we can keep the package */ - rr = solv->rules + solv->featurerules + (why - solv->updaterules); - if (!rr->p) - rr = solv->rules + why; - if (rr->w2) + /* install all recommended packages */ + /* more work as we want to created branches if multiple + * choices are valid */ + for (i = 0; i < decisioncount; i++) { - if (!rr->d) - { - if (solv->decisionmap[rr->w2] > 0 && pool->solvables[rr->w2].repo != solv->installed) - rp = rr->w2; - } - else + Id rec, *recp, pp; + p = solv->decisionq.elements[i]; + if (p < 0) + continue; + s = pool->solvables + p; + if (!s->repo || (solv->ignorealreadyrecommended && s->repo == solv->installed)) + continue; + if (!s->recommends) + continue; + recp = s->repo->idarraydata + s->recommends; + while ((rec = *recp++) != 0) { - Id *dp = pool->whatprovidesdata + rr->d; - for (; *dp; dp++) + queue_empty(&dq); + FOR_PROVIDES(p, pp, rec) { - if (solv->decisionmap[*dp] > 0 && pool->solvables[*dp].repo != solv->installed) + if (solv->decisionmap[p] > 0) { - rp = *dp; + dq.count = 0; break; } + else if (solv->decisionmap[p] == 0 && MAPTST(&dqmap, p)) + queue_pushunique(&dq, p); + } + if (!dq.count) + continue; + if (dq.count > 1) + { + /* multiple candidates, open a branch */ + for (i = 1; i < dq.count; i++) + queue_push(&solv->branches, dq.elements[i]); + queue_push(&solv->branches, -level); } - } + p = dq.elements[0]; + POOL_DEBUG(SAT_DEBUG_POLICY, "installing recommended %s\n", solvid2str(pool, p)); + queue_push(&solv->recommendations, p); + olevel = level; + level = setpropagatelearn(solv, level, p, 0, 0); + if (level <= olevel || solv->decisionq.count < decisioncount) + break; /* we had to revert some decisions */ + } + if (rec) + break; /* had a problem above, quit loop */ } - queue_push(&solutions, p); - queue_push(&solutions, rp); - } - } - /* mark end of this solution */ - queue_push(&solutions, 0); - queue_push(&solutions, 0); - } - queue_free(&solution); - queue_free(&problems); - /* copy queue over to solutions */ - queue_free(&solv->problems); - queue_clone(&solv->problems, &solutions); - - /* bring solver back into problem state */ - revert(solv, 1); /* XXX move to reset_solver? */ - reset_solver(solv); - - assert(solv->problems.count == solutions.count); - queue_free(&solutions); -} - -Id -solver_next_problem(Solver *solv, Id problem) -{ - Id *pp; - if (problem == 0) - return solv->problems.count ? 1 : 0; - pp = solv->problems.elements + problem; - while (pp[0] || pp[1]) - { - /* solution */ - pp += 2; - while (pp[0] || pp[1]) - pp += 2; - pp += 2; - } - pp += 2; - problem = pp - solv->problems.elements; - if (problem >= solv->problems.count) - return 0; - return problem + 1; -} - -Id -solver_next_solution(Solver *solv, Id problem, Id solution) -{ - Id *pp; - if (solution == 0) - { - solution = problem; - pp = solv->problems.elements + solution; - return pp[0] || pp[1] ? solution : 0; - } - pp = solv->problems.elements + solution; - while (pp[0] || pp[1]) - pp += 2; - pp += 2; - solution = pp - solv->problems.elements; - return pp[0] || pp[1] ? solution : 0; -} - -Id -solver_next_solutionelement(Solver *solv, Id problem, Id solution, Id element, Id *p, Id *rp) -{ - Id *pp; - element = element ? element + 2 : solution; - pp = solv->problems.elements + element; - if (!(pp[0] || pp[1])) - return 0; - *p = pp[0]; - *rp = pp[1]; - return element; -} - - -/* this is basically the reverse of addrpmrulesforsolvable */ -SolverProbleminfo -solver_problemruleinfo(Solver *solv, Queue *job, Id rid, Id *depp, Id *sourcep, Id *targetp) -{ - Pool *pool = solv->pool; - Repo *installed = solv->installed; - Rule *r; - Solvable *s; - int dontfix = 0; - Id p, *pp, req, *reqp, con, *conp, obs, *obsp, *dp; - - assert(rid > 0); - if (rid >= solv->updaterules) - { - *depp = 0; - *sourcep = solv->installed->start + (rid - solv->updaterules); - *targetp = 0; - return SOLVER_PROBLEM_UPDATE_RULE; - } - if (rid >= solv->jobrules) - { + map_free(&dqmap); - r = solv->rules + rid; - p = solv->ruletojob.elements[rid - solv->jobrules]; - *depp = job->elements[p + 1]; - *sourcep = p; - *targetp = job->elements[p]; - if (r->d == 0 && r->w2 == 0 && r->p == -SYSTEMSOLVABLE && job->elements[p] != SOLVER_INSTALL_SOLVABLE_ONE_OF) - return SOLVER_PROBLEM_JOB_NOTHING_PROVIDES_DEP; - return SOLVER_PROBLEM_JOB_RULE; - } - r = solv->rules + rid; - assert(r->p < 0); - if (r->d == 0 && r->w2 == 0) - { - /* a rpm rule assertion */ - s = pool->solvables - r->p; - if (installed && !solv->fixsystem && s->repo == installed) - dontfix = 1; - assert(!dontfix); /* dontfix packages never have a neg assertion */ - *sourcep = -r->p; - *targetp = 0; - /* see why the package is not installable */ - if (s->arch != ARCH_SRC && s->arch != ARCH_NOSRC && !pool_installable(pool, s)) - { - *depp = 0; - return SOLVER_PROBLEM_NOT_INSTALLABLE; - } - /* check requires */ - if (s->requires) - { - reqp = s->repo->idarraydata + s->requires; - while ((req = *reqp++) != 0) - { - if (req == SOLVABLE_PREREQMARKER) - continue; - dp = pool_whatprovides(pool, req); - if (*dp == 0) - break; - } - if (req) - { - *depp = req; - return SOLVER_PROBLEM_NOTHING_PROVIDES_DEP; + continue; /* back to main loop */ } } - assert(!solv->allowselfconflicts); - assert(s->conflicts); - conp = s->repo->idarraydata + s->conflicts; - while ((con = *conp++) != 0) - FOR_PROVIDES(p, pp, con) - if (p == -r->p) - { - *depp = con; - return SOLVER_PROBLEM_SELF_CONFLICT; - } - assert(0); - } - s = pool->solvables - r->p; - if (installed && !solv->fixsystem && s->repo == installed) - dontfix = 1; - if (r->d == 0 && r->w2 < 0) - { - /* a package conflict */ - Solvable *s2 = pool->solvables - r->w2; - int dontfix2 = 0; - - if (installed && !solv->fixsystem && s2->repo == installed) - dontfix2 = 1; - /* if both packages have the same name and at least one of them - * is not installed, they conflict */ - if (s->name == s2->name && (!installed || (s->repo != installed || s2->repo != installed))) + if (solv->distupgrade && solv->installed) { - *depp = 0; - *sourcep = -r->p; - *targetp = -r->w2; - return SOLVER_PROBLEM_SAME_NAME; - } + int installedone = 0; - /* check conflicts in both directions */ - if (s->conflicts) - { - conp = s->repo->idarraydata + s->conflicts; - while ((con = *conp++) != 0) - { - FOR_PROVIDES(p, pp, con) + /* let's see if we can install some unsupported package */ + POOL_DEBUG(SAT_DEBUG_STATS, "deciding unsupported packages\n"); + for (i = 0; i < solv->orphaned.count; i++) + { + p = solv->orphaned.elements[i]; + if (solv->decisionmap[p]) + continue; /* already decided */ + olevel = level; + if (solv->distupgrade_removeunsupported) { - if (dontfix && pool->solvables[p].repo == installed) - continue; - if (p != -r->w2) - continue; - *depp = con; - *sourcep = -r->p; - *targetp = p; - return SOLVER_PROBLEM_PACKAGE_CONFLICT; + POOL_DEBUG(SAT_DEBUG_STATS, "removing unsupported %s\n", solvid2str(pool, p)); + level = setpropagatelearn(solv, level, -p, 0, 0); } - } - } - if (s2->conflicts) - { - conp = s2->repo->idarraydata + s2->conflicts; - while ((con = *conp++) != 0) - { - FOR_PROVIDES(p, pp, con) + else { - if (dontfix2 && pool->solvables[p].repo == installed) - continue; - if (p != -r->p) - continue; - *depp = con; - *sourcep = -r->w2; - *targetp = p; - return SOLVER_PROBLEM_PACKAGE_CONFLICT; + POOL_DEBUG(SAT_DEBUG_STATS, "keeping unsupported %s\n", solvid2str(pool, p)); + level = setpropagatelearn(solv, level, p, 0, 0); + installedone = 1; } + if (level < olevel) + break; } + if (installedone || i < solv->orphaned.count) + continue; } - /* check obsoletes in both directions */ - if ((!installed || s->repo != installed) && s->obsoletes) + + if (solv->solution_callback) { - obsp = s->repo->idarraydata + s->obsoletes; - while ((obs = *obsp++) != 0) + solv->solution_callback(solv, solv->solution_callback_data); + if (solv->branches.count) { - FOR_PROVIDES(p, pp, obs) + int i = solv->branches.count - 1; + int l = -solv->branches.elements[i]; + Id why; + + for (; i > 0; i--) + if (solv->branches.elements[i - 1] < 0) + break; + p = solv->branches.elements[i]; + POOL_DEBUG(SAT_DEBUG_STATS, "branching with %s\n", solvid2str(pool, p)); + queue_empty(&dq); + for (j = i + 1; j < solv->branches.count; j++) + queue_push(&dq, solv->branches.elements[j]); + solv->branches.count = i; + level = l; + revert(solv, level); + if (dq.count > 1) + for (j = 0; j < dq.count; j++) + queue_push(&solv->branches, dq.elements[j]); + olevel = level; + why = -solv->decisionq_why.elements[solv->decisionq_why.count]; + assert(why >= 0); + level = setpropagatelearn(solv, level, p, disablerules, why); + if (level == 0) { - if (p != -r->w2) - continue; - *depp = obs; - *sourcep = -r->p; - *targetp = p; - return SOLVER_PROBLEM_PACKAGE_OBSOLETES; + queue_free(&dq); + queue_free(&dqs); + return; } + continue; } + /* all branches done, we're finally finished */ + break; } - if ((!installed || s2->repo != installed) && s2->obsoletes) + + /* minimization step */ + if (solv->branches.count) { - obsp = s2->repo->idarraydata + s2->obsoletes; - while ((obs = *obsp++) != 0) + int l = 0, lasti = -1, lastl = -1; + Id why; + + p = 0; + for (i = solv->branches.count - 1; i >= 0; i--) { - FOR_PROVIDES(p, pp, obs) + p = solv->branches.elements[i]; + if (p < 0) + l = -p; + else if (p > 0 && solv->decisionmap[p] > l + 1) { - if (p != -r->p) - continue; - *depp = obs; - *sourcep = -r->w2; - *targetp = p; - return SOLVER_PROBLEM_PACKAGE_OBSOLETES; + lasti = i; + lastl = l; } } - } - /* all cases checked, can't happen */ - assert(0); - } - /* simple requires */ - assert(s->requires); - reqp = s->repo->idarraydata + s->requires; - while ((req = *reqp++) != 0) - { - if (req == SOLVABLE_PREREQMARKER) - continue; - dp = pool_whatprovides(pool, req); - if (r->d == 0) - { - if (*dp == r->w2 && dp[1] == 0) - break; - } - else if (dp - pool->whatprovidesdata == r->d) - break; - } - assert(req); - *depp = req; - *sourcep = -r->p; - *targetp = 0; - return SOLVER_PROBLEM_DEP_PROVIDERS_NOT_INSTALLABLE; -} - -static void -findproblemrule_internal(Solver *solv, Id idx, Id *reqrp, Id *conrp, Id *sysrp, Id *jobrp) -{ - Id rid; - Id lreqr, lconr, lsysr, ljobr; - Rule *r; - int reqassert = 0; - - lreqr = lconr = lsysr = ljobr = 0; - while ((rid = solv->learnt_pool.elements[idx++]) != 0) - { - assert(rid > 0); - if (rid >= solv->learntrules) - findproblemrule_internal(solv, solv->learnt_why.elements[rid - solv->learntrules], &lreqr, &lconr, &lsysr, &ljobr); - else if (rid >= solv->updaterules) - { - if (!*sysrp) - *sysrp = rid; - } - else if (rid >= solv->jobrules) - { - if (!*jobrp) - *jobrp = rid; - } - else - { - r = solv->rules + rid; - if (!r->d && r->w2 < 0) - { - if (!*conrp) - *conrp = rid; - } - else + if (lasti >= 0) { - if (r->d == 0 && r->w2 == 0 && !reqassert) - { - /* prefer assertions (XXX: bad idea?) */ - *reqrp = rid; - reqassert = 1; - } - if (!*reqrp) - *reqrp = rid; - else if (solv->installed && r->p < 0 && solv->pool->solvables[-r->p].repo == solv->installed) + /* kill old solvable so that we do not loop */ + p = solv->branches.elements[lasti]; + solv->branches.elements[lasti] = 0; + POOL_DEBUG(SAT_DEBUG_STATS, "minimizing %d -> %d with %s\n", solv->decisionmap[p], lastl, solvid2str(pool, p)); + minimizationsteps++; + + level = lastl; + revert(solv, level); + why = -solv->decisionq_why.elements[solv->decisionq_why.count]; + assert(why >= 0); + olevel = level; + level = setpropagatelearn(solv, level, p, disablerules, why); + if (level == 0) { - /* prefer rules of installed packages */ - Id op = *reqrp >= 0 ? solv->rules[*reqrp].p : -*reqrp; - if (op <= 0 || solv->pool->solvables[op].repo != solv->installed) - *reqrp = rid; + queue_free(&dq); + queue_free(&dqs); + return; } + continue; } } + break; } - if (!*reqrp && lreqr) - *reqrp = lreqr; - if (!*conrp && lconr) - *conrp = lconr; - if (!*jobrp && ljobr) - *jobrp = ljobr; - if (!*sysrp && lsysr) - *sysrp = lsysr; -} + POOL_DEBUG(SAT_DEBUG_STATS, "solver statistics: %d learned rules, %d unsolvable, %d minimization steps\n", solv->stats_learned, solv->stats_unsolvable, minimizationsteps); -/* - * search for a rule that describes the problem to the - * user. A pretty hopeless task, actually. We currently - * prefer simple requires. - */ -Id -solver_findproblemrule(Solver *solv, Id problem) -{ - Id reqr, conr, sysr, jobr; - Id idx = solv->problems.elements[problem - 1]; - reqr = conr = sysr = jobr = 0; - findproblemrule_internal(solv, idx, &reqr, &conr, &sysr, &jobr); - if (reqr) - return reqr; - if (conr) - return conr; - if (sysr) - return sysr; - if (jobr) - return jobr; - assert(0); + POOL_DEBUG(SAT_DEBUG_STATS, "done solving.\n\n"); + queue_free(&dq); + queue_free(&dqs); } -/* create reverse obsoletes map for installed solvables +/*------------------------------------------------------------------- + * + * remove disabled conflicts * - * for each installed solvable find which packages with *different* names - * obsolete the solvable. - * this index is used in policy_findupdatepackages if noupdateprovide is set. + * purpose: update the decisionmap after some rules were disabled. + * this is used to calculate the suggested/recommended package list. + * Also returns a "removed" list to undo the discisionmap changes. */ static void -create_obsolete_index(Solver *solv) -{ - Pool *pool = solv->pool; - Solvable *s; - Repo *installed = solv->installed; - Id p, *pp, obs, *obsp, *obsoletes, *obsoletes_data; - int i, n; - - if (!installed || !installed->nsolvables) - return; - solv->obsoletes = obsoletes = sat_calloc(installed->end - installed->start, sizeof(Id)); - for (i = 1; i < pool->nsolvables; i++) - { - s = pool->solvables + i; - if (s->repo == installed) - continue; - if (!s->obsoletes) - continue; - if (!pool_installable(pool, s)) - continue; - obsp = s->repo->idarraydata + s->obsoletes; - while ((obs = *obsp++) != 0) - FOR_PROVIDES(p, pp, obs) - { - if (pool->solvables[p].repo != installed) - continue; - if (pool->solvables[p].name == s->name) - continue; - obsoletes[p - installed->start]++; - } - } - n = 0; - for (i = 0; i < installed->nsolvables; i++) - if (obsoletes[i]) - { - n += obsoletes[i] + 1; - obsoletes[i] = n; - } - solv->obsoletes_data = obsoletes_data = sat_calloc(n + 1, sizeof(Id)); - POOL_DEBUG(SAT_DEBUG_STATS, "obsoletes data: %d entries\n", n + 1); - for (i = pool->nsolvables - 1; i > 0; i--) - { - s = pool->solvables + i; - if (s->repo == installed) - continue; - if (!s->obsoletes) - continue; - if (!pool_installable(pool, s)) - continue; - obsp = s->repo->idarraydata + s->obsoletes; - while ((obs = *obsp++) != 0) - FOR_PROVIDES(p, pp, obs) - { - if (pool->solvables[p].repo != installed) - continue; - if (pool->solvables[p].name == s->name) - continue; - p -= installed->start; - if (obsoletes_data[obsoletes[p]] != i) - obsoletes_data[--obsoletes[p]] = i; - } - } -} - -static void removedisabledconflicts(Solver *solv, Queue *removed) { Pool *pool = solv->pool; @@ -3086,7 +2029,7 @@ removedisabledconflicts(Solver *solv, Queue *removed) Rule *r; Id *decisionmap = solv->decisionmap; - POOL_DEBUG(SAT_DEBUG_STATS, "removedisabledconflicts\n"); + POOL_DEBUG(SAT_DEBUG_SCHUBI, "removedisabledconflicts\n"); queue_empty(removed); for (i = 0; i < solv->decisionq.count; i++) { @@ -3098,10 +2041,10 @@ removedisabledconflicts(Solver *solv, Queue *removed) why = solv->decisionq_why.elements[i]; assert(why > 0); r = solv->rules + why; - if (!r->w1 && decisionmap[-p]) + if (r->d < 0 && decisionmap[-p]) { /* rule is now disabled, remove from decisionmap */ - POOL_DEBUG(SAT_DEBUG_STATS, "removing conflict for package %s[%d]\n", solvable2str(pool, pool->solvables - p), -p); + POOL_DEBUG(SAT_DEBUG_SCHUBI, "removing conflict for package %s[%d]\n", solvid2str(pool, -p), -p); queue_push(removed, -p); queue_push(removed, decisionmap[-p]); decisionmap[-p] = 0; @@ -3119,7 +2062,7 @@ removedisabledconflicts(Solver *solv, Queue *removed) i = 1; r = solv->rules + i; } - if (!r->w1) + if (r->d < 0) continue; if (!r->w2) { @@ -3136,60 +2079,273 @@ removedisabledconflicts(Solver *solv, Queue *removed) } else { - if (r->p < 0 && decisionmap[-r->p] == 0) - new = r->p; - if (new || DECISIONMAP_FALSE(r->p)) + if (r->p < 0 && decisionmap[-r->p] == 0) + new = r->p; + if (new || DECISIONMAP_FALSE(r->p)) + { + dp = pool->whatprovidesdata + r->d; + while ((p = *dp++) != 0) + { + if (new && p == new) + continue; + if (p < 0 && decisionmap[-p] == 0) + { + if (new) + { + new = 0; + break; + } + new = p; + } + else if (!DECISIONMAP_FALSE(p)) + { + new = 0; + break; + } + } + } + } + if (new) + { + POOL_DEBUG(SAT_DEBUG_SCHUBI, "re-conflicting package %s[%d]\n", solvid2str(pool, -new), -new); + decisionmap[-new] = -1; + new = 0; + n = 0; /* redo all rules */ + } + } +} + +static inline void +undo_removedisabledconflicts(Solver *solv, Queue *removed) +{ + int i; + for (i = 0; i < removed->count; i += 2) + solv->decisionmap[removed->elements[i]] = removed->elements[i + 1]; +} + + +/*------------------------------------------------------------------- + * + * weaken solvable dependencies + */ + +static void +weaken_solvable_deps(Solver *solv, Id p) +{ + int i; + Rule *r; + + for (i = 1, r = solv->rules + i; i < solv->rpmrules_end; i++, r++) + { + if (r->p != -p) + continue; + if ((r->d == 0 || r->d == -1) && r->w2 < 0) + continue; /* conflict */ + queue_push(&solv->weakruleq, i); + } +} + + +/********************************************************************/ +/* main() */ + + +static void +findrecommendedsuggested(Solver *solv) +{ + Pool *pool = solv->pool; + Queue redoq, disabledq; + int goterase, i; + Solvable *s; + Rule *r; + Map obsmap; + + map_init(&obsmap, pool->nsolvables); + if (solv->installed) + { + Id obs, *obsp, p, po, ppo; + for (p = solv->installed->start; p < solv->installed->end; p++) + { + s = pool->solvables + p; + if (s->repo != solv->installed || !s->obsoletes) + continue; + if (solv->decisionmap[p] <= 0) + continue; + if (solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p)) + continue; + obsp = s->repo->idarraydata + s->obsoletes; + /* foreach obsoletes */ + while ((obs = *obsp++) != 0) + FOR_PROVIDES(po, ppo, obs) + MAPSET(&obsmap, po); + } + } + + queue_init(&redoq); + queue_init(&disabledq); + goterase = 0; + /* disable all erase jobs (including weak "keep uninstalled" rules) */ + for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++) + { + if (r->d < 0) /* disabled ? */ + continue; + if (r->p >= 0) /* install job? */ + continue; + queue_push(&disabledq, i); + solver_disablerule(solv, r); + goterase++; + } + + if (goterase) + { + enabledisablelearntrules(solv); + removedisabledconflicts(solv, &redoq); + } + + /* + * find recommended packages + */ + + /* if redoq.count == 0 we already found all recommended in the + * solver run */ + if (redoq.count || solv->dontinstallrecommended || !solv->dontshowinstalledrecommended || solv->ignorealreadyrecommended) + { + Id rec, *recp, p, pp; + + /* create map of all recommened packages */ + solv->recommends_index = -1; + MAPZERO(&solv->recommendsmap); + for (i = 0; i < solv->decisionq.count; i++) + { + p = solv->decisionq.elements[i]; + if (p < 0) + continue; + s = pool->solvables + p; + if (s->recommends) + { + recp = s->repo->idarraydata + s->recommends; + while ((rec = *recp++) != 0) + { + FOR_PROVIDES(p, pp, rec) + if (solv->decisionmap[p] > 0) + break; + if (p) + { + if (!solv->dontshowinstalledrecommended) + { + FOR_PROVIDES(p, pp, rec) + if (solv->decisionmap[p] > 0) + MAPSET(&solv->recommendsmap, p); + } + continue; /* p != 0: already fulfilled */ + } + FOR_PROVIDES(p, pp, rec) + MAPSET(&solv->recommendsmap, p); + } + } + } + for (i = 1; i < pool->nsolvables; i++) + { + if (solv->decisionmap[i] < 0) + continue; + if (solv->decisionmap[i] > 0 && solv->dontshowinstalledrecommended) + continue; + if (MAPTST(&obsmap, i)) + continue; + s = pool->solvables + i; + if (!MAPTST(&solv->recommendsmap, i)) + { + if (!s->supplements) + continue; + if (!pool_installable(pool, s)) + continue; + if (!solver_is_supplementing(solv, s)) + continue; + } + if (solv->dontinstallrecommended) + queue_push(&solv->recommendations, i); + else + queue_pushunique(&solv->recommendations, i); + } + /* we use MODE_SUGGEST here so that repo prio is ignored */ + policy_filter_unwanted(solv, &solv->recommendations, POLICY_MODE_SUGGEST); + } + + /* + * find suggested packages + */ + + if (1) + { + Id sug, *sugp, p, pp; + + /* create map of all suggests that are still open */ + solv->recommends_index = -1; + MAPZERO(&solv->suggestsmap); + for (i = 0; i < solv->decisionq.count; i++) + { + p = solv->decisionq.elements[i]; + if (p < 0) + continue; + s = pool->solvables + p; + if (s->suggests) { - dp = pool->whatprovidesdata + r->d; - while ((p = *dp++) != 0) + sugp = s->repo->idarraydata + s->suggests; + while ((sug = *sugp++) != 0) { - if (new && p == new) - continue; - if (p < 0 && decisionmap[-p] == 0) + FOR_PROVIDES(p, pp, sug) + if (solv->decisionmap[p] > 0) + break; + if (p) { - if (new) + if (!solv->dontshowinstalledrecommended) { - new = 0; - break; + FOR_PROVIDES(p, pp, sug) + if (solv->decisionmap[p] > 0) + MAPSET(&solv->suggestsmap, p); } - new = p; - } - else if (!DECISIONMAP_FALSE(p)) - { - new = 0; - break; + continue; /* already fulfilled */ } + FOR_PROVIDES(p, pp, sug) + MAPSET(&solv->suggestsmap, p); } } } - if (new) + for (i = 1; i < pool->nsolvables; i++) { - POOL_DEBUG(SAT_DEBUG_STATS, "re-conflicting package %s[%d]\n", solvable2str(pool, pool->solvables - new), -new); - decisionmap[-new] = -1; - new = 0; - n = 0; /* redo all rules */ + if (solv->decisionmap[i] < 0) + continue; + if (solv->decisionmap[i] > 0 && solv->dontshowinstalledrecommended) + continue; + if (MAPTST(&obsmap, i)) + continue; + s = pool->solvables + i; + if (!MAPTST(&solv->suggestsmap, i)) + { + if (!s->enhances) + continue; + if (!pool_installable(pool, s)) + continue; + if (!solver_is_enhancing(solv, s)) + continue; + } + queue_push(&solv->suggestions, i); } + policy_filter_unwanted(solv, &solv->suggestions, POLICY_MODE_SUGGEST); } -} - -static void -weaken_solvable_deps(Solver *solv, Id p) -{ - int i; - Rule *r; - for (i = 1, r = solv->rules + i; i < solv->jobrules; i++, r++) - { - if (r->p != -p) - continue; - if (r->d == 0 && r->w2 < 0) - continue; /* conflict */ - queue_push(&solv->weakruleq, i); - } + /* undo removedisabledconflicts */ + if (redoq.count) + undo_removedisabledconflicts(solv, &redoq); + queue_free(&redoq); + + /* undo job rule disabling */ + for (i = 0; i < disabledq.count; i++) + solver_enablerule(solv, solv->rules + disabledq.elements[i]); + queue_free(&disabledq); + map_free(&obsmap); } -/*-----------------------------------------------------------------*/ -/* main() */ /* * @@ -3205,37 +2361,62 @@ solver_solve(Solver *solv, Queue *job) int i; int oldnrules; Map addedmap; /* '1' == have rpm-rules for solvable */ - Id how, what, weak, name, p, *pp, d; - Queue q, redoq; + Map installcandidatemap; + Id how, what, select, name, weak, p, pp, d; + Queue q; Solvable *s; - int goterase; Rule *r; + int now, solve_start; + int hasdupjob = 0; + + solve_start = sat_timems(0); + + /* log solver options */ + POOL_DEBUG(SAT_DEBUG_STATS, "solver started\n"); + POOL_DEBUG(SAT_DEBUG_STATS, "fixsystem=%d updatesystem=%d dosplitprovides=%d, noupdateprovide=%d noinfarchcheck=%d\n", solv->fixsystem, solv->updatesystem, solv->dosplitprovides, solv->noupdateprovide, solv->noinfarchcheck); + POOL_DEBUG(SAT_DEBUG_STATS, "distupgrade=%d distupgrade_removeunsupported=%d\n", solv->distupgrade, solv->distupgrade_removeunsupported); + POOL_DEBUG(SAT_DEBUG_STATS, "allowuninstall=%d, allowdowngrade=%d, allowarchchange=%d, allowvendorchange=%d\n", solv->allowuninstall, solv->allowdowngrade, solv->allowarchchange, solv->allowvendorchange); + POOL_DEBUG(SAT_DEBUG_STATS, "promoteepoch=%d, allowvirtualconflicts=%d, allowselfconflicts=%d\n", pool->promoteepoch, solv->allowvirtualconflicts, solv->allowselfconflicts); + POOL_DEBUG(SAT_DEBUG_STATS, "obsoleteusesprovides=%d, implicitobsoleteusesprovides=%d\n", solv->obsoleteusesprovides, solv->implicitobsoleteusesprovides); + POOL_DEBUG(SAT_DEBUG_STATS, "dontinstallrecommended=%d, ignorealreadyrecommended=%d, dontshowinstalledrecommended=%d\n", solv->dontinstallrecommended, solv->ignorealreadyrecommended, solv->dontshowinstalledrecommended); /* create whatprovides if not already there */ if (!pool->whatprovides) pool_createwhatprovides(pool); - /* create obsolete index if needed */ - if (solv->noupdateprovide) - create_obsolete_index(solv); + /* create obsolete index */ + policy_create_obsolete_index(solv); + + /* remember job */ + queue_free(&solv->job); + queue_init_clone(&solv->job, job); /* * create basic rule set of all involved packages * use addedmap bitmap to make sure we don't create rules twice - * */ - map_init(&addedmap, pool->nsolvables); - queue_init(&q); + /* create noobsolete map if needed */ + for (i = 0; i < job->count; i += 2) + { + how = job->elements[i]; + if ((how & SOLVER_JOBMASK) != SOLVER_NOOBSOLETES) + continue; + what = job->elements[i + 1]; + select = how & SOLVER_SELECTMASK; + if (!solv->noobsoletes.size) + map_init(&solv->noobsoletes, pool->nsolvables); + FOR_JOB_SELECT(p, pp, select, what) + MAPSET(&solv->noobsoletes, p); + } - /* - * always install our system solvable - */ + map_init(&addedmap, pool->nsolvables); MAPSET(&addedmap, SYSTEMSOLVABLE); - queue_push(&solv->decisionq, SYSTEMSOLVABLE); - queue_push(&solv->decisionq_why, 0); - solv->decisionmap[SYSTEMSOLVABLE] = 1; + map_init(&installcandidatemap, pool->nsolvables); + queue_init(&q); + + now = sat_timems(0); /* * create rules for all package that could be involved with the solving * so called: rpm rules @@ -3246,62 +2427,64 @@ solver_solve(Solver *solv, Queue *job) oldnrules = solv->nrules; POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for installed solvables ***\n"); FOR_REPO_SOLVABLES(installed, p, s) - addrpmrulesforsolvable(solv, s, &addedmap); + solver_addrpmrulesforsolvable(solv, s, &addedmap); POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for installed solvables\n", solv->nrules - oldnrules); POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for updaters of installed solvables ***\n"); oldnrules = solv->nrules; FOR_REPO_SOLVABLES(installed, p, s) - addrpmrulesforupdaters(solv, s, &addedmap, 1); + solver_addrpmrulesforupdaters(solv, s, &addedmap, 1); POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for updaters of installed solvables\n", solv->nrules - oldnrules); } + /* + * create rules for all packages involved in the job + * (to be installed or removed) + */ + POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for packages involved with a job ***\n"); oldnrules = solv->nrules; for (i = 0; i < job->count; i += 2) { - how = job->elements[i] & ~SOLVER_WEAK; + how = job->elements[i]; what = job->elements[i + 1]; + select = how & SOLVER_SELECTMASK; - switch(how) + switch (how & SOLVER_JOBMASK) { - case SOLVER_INSTALL_SOLVABLE: - addrpmrulesforsolvable(solv, pool->solvables + what, &addedmap); - break; - case SOLVER_INSTALL_SOLVABLE_NAME: - case SOLVER_INSTALL_SOLVABLE_PROVIDES: - name = (how == SOLVER_INSTALL_SOLVABLE_NAME) ? what : 0; - while (ISRELDEP(name)) - { - Reldep *rd = GETRELDEP(pool, name); - name = rd->name; - } - FOR_PROVIDES(p, pp, what) + case SOLVER_INSTALL: + FOR_JOB_SELECT(p, pp, select, what) { - /* if by name, ensure that the name matches */ - if (name && pool->solvables[p].name != name) - continue; - addrpmrulesforsolvable(solv, pool->solvables + p, &addedmap); + MAPSET(&installcandidatemap, p); + solver_addrpmrulesforsolvable(solv, pool->solvables + p, &addedmap); } break; - case SOLVER_INSTALL_SOLVABLE_UPDATE: - /* dont allow downgrade */ - addrpmrulesforupdaters(solv, pool->solvables + what, &addedmap, 0); + case SOLVER_DISTUPGRADE: + if (!solv->distupgrade) + hasdupjob = 1; break; - case SOLVER_INSTALL_SOLVABLE_ONE_OF: - pp = pool->whatprovidesdata + what; - while ((p = *pp++) != 0) - addrpmrulesforsolvable(solv, pool->solvables + p, &addedmap); + default: break; } } POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for packages involved in a job\n", solv->nrules - oldnrules); - POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for recommended/suggested packages ***\n"); - + + /* + * add rules for suggests, enhances + */ + POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for suggested/enhanced packages ***\n"); oldnrules = solv->nrules; - addrpmrulesforweak(solv, &addedmap); + solver_addrpmrulesforweak(solv, &addedmap); POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules because of weak dependencies\n", solv->nrules - oldnrules); + /* + * first pass done, we now have all the rpm rules we need. + * unify existing rules before going over all job rules and + * policy rules. + * at this point the system is always solvable, + * as an empty system (remove all packages) is a valid solution + */ + IF_POOLDEBUG (SAT_DEBUG_STATS) { int possible = 0, installable = 0; @@ -3315,20 +2498,114 @@ solver_solve(Solver *solv, Queue *job) POOL_DEBUG(SAT_DEBUG_STATS, "%d of %d installable solvables considered for solving\n", possible, installable); } + solver_unifyrules(solv); /* remove duplicate rpm rules */ + solv->rpmrules_end = solv->nrules; /* mark end of rpm rules */ + + POOL_DEBUG(SAT_DEBUG_STATS, "rpm rule memory usage: %d K\n", solv->nrules * (int)sizeof(Rule) / 1024); + POOL_DEBUG(SAT_DEBUG_STATS, "rpm rule creation took %d ms\n", sat_timems(now)); + + /* create dup maps if needed. We need the maps early to create our + * update rules */ + if (hasdupjob) + solver_createdupmaps(solv); + /* - * first pass done, we now have all the rpm rules we need. - * unify existing rules before going over all job rules and - * policy rules. - * at this point the system is always solvable, - * as an empty system (remove all packages) is a valid solution + * create feature rules + * + * foreach installed: + * create assertion (keep installed, if no update available) + * or + * create update rule (A|update1(A)|update2(A)|...) + * + * those are used later on to keep a version of the installed packages in + * best effort mode */ + + POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** Add feature rules ***\n"); + solv->featurerules = solv->nrules; /* mark start of feature rules */ + if (installed) + { + /* foreach possibly installed solvable */ + for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++) + { + if (s->repo != installed) + { + solver_addrule(solv, 0, 0); /* create dummy rule */ + continue; + } + solver_addupdaterule(solv, s, 1); /* allow s to be updated */ + } + /* make sure we accounted for all rules */ + assert(solv->nrules - solv->featurerules == installed->end - installed->start); + } + solv->featurerules_end = solv->nrules; + + /* + * Add update rules for installed solvables + * + * almost identical to feature rules + * except that downgrades/archchanges/vendorchanges are not allowed + */ + + POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** Add update rules ***\n"); + solv->updaterules = solv->nrules; - unifyrules(solv); /* remove duplicate rpm rules */ - solv->directdecisions = solv->decisionq.count; + if (installed) + { /* foreach installed solvables */ + /* we create all update rules, but disable some later on depending on the job */ + for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++) + { + Rule *sr; + + if (s->repo != installed) + { + solver_addrule(solv, 0, 0); /* create dummy rule */ + continue; + } + solver_addupdaterule(solv, s, 0); /* allowall = 0: downgrades not allowed */ + /* + * check for and remove duplicate + */ + r = solv->rules + solv->nrules - 1; /* r: update rule */ + sr = r - (installed->end - installed->start); /* sr: feature rule */ + /* it's orphaned if there is no feature rule or the feature rule + * consists just of the installed package */ + if (!sr->p || (sr->p == i && !sr->d && !sr->w2)) + queue_push(&solv->orphaned, i); + if (!r->p) + { + assert(solv->distupgrade && !sr->p); + continue; + } + if (!solver_samerule(solv, r, sr)) + { + /* identical rule, kill unneeded one */ + if (solv->allowuninstall) + { + /* keep feature rule, make it weak */ + memset(r, 0, sizeof(*r)); + queue_push(&solv->weakruleq, sr - solv->rules); + } + else + { + /* keep update rule */ + memset(sr, 0, sizeof(*sr)); + } + } + else if (solv->allowuninstall) + { + /* make both feature and update rule weak */ + queue_push(&solv->weakruleq, r - solv->rules); + queue_push(&solv->weakruleq, sr - solv->rules); + } + else + solver_disablerule(solv, sr); + } + /* consistency check: we added a rule for _every_ installed solvable */ + assert(solv->nrules - solv->updaterules == installed->end - installed->start); + } + solv->updaterules_end = solv->nrules; - POOL_DEBUG(SAT_DEBUG_STATS, "decisions so far: %d\n", solv->decisionq.count); - IF_POOLDEBUG (SAT_DEBUG_SCHUBI) - solver_printdecisions (solv); /* * now add all job rules @@ -3337,213 +2614,167 @@ solver_solve(Solver *solv, Queue *job) POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** Add JOB rules ***\n"); solv->jobrules = solv->nrules; - for (i = 0; i < job->count; i += 2) { oldnrules = solv->nrules; - how = job->elements[i] & ~SOLVER_WEAK; - weak = job->elements[i] & SOLVER_WEAK; + how = job->elements[i]; what = job->elements[i + 1]; - switch(how) + weak = how & SOLVER_WEAK; + select = how & SOLVER_SELECTMASK; + switch (how & SOLVER_JOBMASK) { - case SOLVER_INSTALL_SOLVABLE: /* install specific solvable */ - s = pool->solvables + what; - POOL_DEBUG(SAT_DEBUG_JOB, "job: %sinstall solvable %s\n", weak ? "weak " : "", solvable2str(pool, s)); - addrule(solv, what, 0); /* install by Id */ - queue_push(&solv->ruletojob, i); - if (weak) - queue_push(&solv->weakruleq, solv->nrules - 1); - break; - case SOLVER_ERASE_SOLVABLE: - s = pool->solvables + what; - POOL_DEBUG(SAT_DEBUG_JOB, "job: %serase solvable %s\n", weak ? "weak " : "", solvable2str(pool, s)); - addrule(solv, -what, 0); /* remove by Id */ - queue_push(&solv->ruletojob, i); - if (weak) - queue_push(&solv->weakruleq, solv->nrules - 1); - break; - case SOLVER_INSTALL_SOLVABLE_NAME: /* install by capability */ - case SOLVER_INSTALL_SOLVABLE_PROVIDES: - if (how == SOLVER_INSTALL_SOLVABLE_NAME) - POOL_DEBUG(SAT_DEBUG_JOB, "job: %sinstall name %s\n", weak ? "weak " : "", dep2str(pool, what)); - if (how == SOLVER_INSTALL_SOLVABLE_PROVIDES) - POOL_DEBUG(SAT_DEBUG_JOB, "job: %sinstall provides %s\n", weak ? "weak " : "", dep2str(pool, what)); - queue_empty(&q); - name = (how == SOLVER_INSTALL_SOLVABLE_NAME) ? what : 0; - while (ISRELDEP(name)) - { - Reldep *rd = GETRELDEP(pool, name); - name = rd->name; - } - FOR_PROVIDES(p, pp, what) + case SOLVER_INSTALL: + POOL_DEBUG(SAT_DEBUG_JOB, "job: %sinstall %s\n", weak ? "weak " : "", solver_select2str(solv, select, what)); + if (select == SOLVER_SOLVABLE) { - /* if by name, ensure that the name matches */ - if (name && pool->solvables[p].name != name) - continue; - queue_push(&q, p); + p = what; + d = 0; } - if (!q.count) + else { - /* no provider, make this an impossible rule */ - queue_push(&q, -SYSTEMSOLVABLE); + queue_empty(&q); + FOR_JOB_SELECT(p, pp, select, what) + queue_push(&q, p); + if (!q.count) + { + /* no candidate found, make this an impossible rule */ + queue_push(&q, -SYSTEMSOLVABLE); + } + p = queue_shift(&q); /* get first candidate */ + d = !q.count ? 0 : pool_queuetowhatprovides(pool, &q); /* internalize */ } - - p = queue_shift(&q); /* get first provider */ - if (!q.count) - d = 0; /* single provider ? -> make assertion */ - else - d = pool_queuetowhatprovides(pool, &q); /* get all providers */ - addrule(solv, p, d); /* add 'requires' rule */ + solver_addrule(solv, p, d); /* add install rule */ queue_push(&solv->ruletojob, i); if (weak) queue_push(&solv->weakruleq, solv->nrules - 1); break; - case SOLVER_ERASE_SOLVABLE_NAME: /* remove by capability */ - case SOLVER_ERASE_SOLVABLE_PROVIDES: - if (how == SOLVER_ERASE_SOLVABLE_NAME) - POOL_DEBUG(SAT_DEBUG_JOB, "job: %serase name %s\n", weak ? "weak " : "", dep2str(pool, what)); - if (how == SOLVER_ERASE_SOLVABLE_PROVIDES) - POOL_DEBUG(SAT_DEBUG_JOB, "job: %serase provides %s\n", weak ? "weak " : "", dep2str(pool, what)); - name = (how == SOLVER_ERASE_SOLVABLE_NAME) ? what : 0; - while (ISRELDEP(name)) - { - Reldep *rd = GETRELDEP(pool, name); - name = rd->name; + case SOLVER_ERASE: + POOL_DEBUG(SAT_DEBUG_JOB, "job: %serase %s\n", weak ? "weak " : "", solver_select2str(solv, select, what)); + if (select == SOLVER_SOLVABLE && solv->installed && pool->solvables[what].repo == solv->installed) + { + /* special case for "erase a specific solvable": we also + * erase all other solvables with that name, so that they + * don't get picked up as replacement */ + name = pool->solvables[what].name; + FOR_PROVIDES(p, pp, name) + { + if (p == what) + continue; + s = pool->solvables + p; + if (s->name != name) + continue; + /* keep other versions installed */ + if (s->repo == solv->installed) + continue; + /* keep installcandidates of other jobs */ + if (MAPTST(&installcandidatemap, p)) + continue; + solver_addrule(solv, -p, 0); /* remove by Id */ + queue_push(&solv->ruletojob, i); + if (weak) + queue_push(&solv->weakruleq, solv->nrules - 1); + } } - FOR_PROVIDES(p, pp, what) + FOR_JOB_SELECT(p, pp, select, what) { - /* if by name, ensure that the name matches */ - if (name && pool->solvables[p].name != name) - continue; - addrule(solv, -p, 0); /* add 'remove' rule */ + solver_addrule(solv, -p, 0); queue_push(&solv->ruletojob, i); if (weak) queue_push(&solv->weakruleq, solv->nrules - 1); } break; - case SOLVER_INSTALL_SOLVABLE_UPDATE: /* find update for solvable */ - s = pool->solvables + what; - POOL_DEBUG(SAT_DEBUG_JOB, "job: %supdate %s\n", weak ? "weak " : "", solvable2str(pool, s)); - addupdaterule(solv, s, 0); - queue_push(&solv->ruletojob, i); - if (weak) - queue_push(&solv->weakruleq, solv->nrules - 1); - break; - case SOLVER_INSTALL_SOLVABLE_ONE_OF: - POOL_DEBUG(SAT_DEBUG_JOB, "job: %sone of\n", weak ? "weak " : ""); - for (pp = pool->whatprovidesdata + what; *pp; pp++) - POOL_DEBUG(SAT_DEBUG_JOB, " %s\n", solvable2str(pool, pool->solvables + *pp)); - addrule(solv, -SYSTEMSOLVABLE, what); - queue_push(&solv->ruletojob, i); - if (weak) - queue_push(&solv->weakruleq, solv->nrules - 1); + + case SOLVER_UPDATE: + POOL_DEBUG(SAT_DEBUG_JOB, "job: %supdate %s\n", weak ? "weak " : "", solver_select2str(solv, select, what)); + FOR_JOB_SELECT(p, pp, select, what) + { + s = pool->solvables + p; + if (!solv->installed || s->repo != solv->installed) + continue; + if (!solv->updatemap.size) + map_init(&solv->updatemap, pool->nsolvables); + MAPSET(&solv->updatemap, p); + } break; - case SOLVER_WEAKEN_SOLVABLE_DEPS: + case SOLVER_WEAKENDEPS: + POOL_DEBUG(SAT_DEBUG_JOB, "job: %sweaken deps %s\n", weak ? "weak " : "", solver_select2str(solv, select, what)); + if (select != SOLVER_SOLVABLE) + break; s = pool->solvables + what; - POOL_DEBUG(SAT_DEBUG_JOB, "job: weaken deps %s\n", solvable2str(pool, s)); weaken_solvable_deps(solv, what); break; - } - IF_POOLDEBUG (SAT_DEBUG_JOB) - { - int j; - if (solv->nrules == oldnrules) - POOL_DEBUG(SAT_DEBUG_JOB, " - no rule created\n"); - for (j = oldnrules; j < solv->nrules; j++) - { - POOL_DEBUG(SAT_DEBUG_JOB, " - job "); - solver_printrule(solv, SAT_DEBUG_JOB, solv->rules + j); - } - } - } - assert(solv->ruletojob.count == solv->nrules - solv->jobrules); - - /* - * now add update rules - * - */ - - POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** Add update rules ***\n"); - - - - /* - * create rules for updating installed solvables - * - */ - - solv->updaterules = solv->nrules; - if (installed && !solv->allowuninstall) - { /* loop over all installed solvables */ - /* we create all update rules, but disable some later on depending on the job */ - for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++) - { - /* no update rules for patch atoms */ - if (s->freshens && !s->supplements) - { - const char *name = id2str(pool, s->name); - if (name[0] == 'a' && !strncmp(name, "atom:", 5)) - { - addrule(solv, 0, 0); - continue; - } - } - if (s->repo == installed) - addupdaterule(solv, s, 0); /* allowall = 0 */ - else - addrule(solv, 0, 0); /* create dummy rule */ - } - /* consistency check: we added a rule for _every_ installed solvable */ - assert(solv->nrules - solv->updaterules == installed->end - installed->start); - } - - /* create feature rules */ - /* those are used later on to keep a version of the installed packages in - best effort mode */ - solv->featurerules = solv->nrules; - if (installed) - { - for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++) - { - if (s->freshens && !s->supplements) + case SOLVER_NOOBSOLETES: + POOL_DEBUG(SAT_DEBUG_JOB, "job: %sno obsolete %s\n", weak ? "weak " : "", solver_select2str(solv, select, what)); + break; + case SOLVER_LOCK: + POOL_DEBUG(SAT_DEBUG_JOB, "job: %slock %s\n", weak ? "weak " : "", solver_select2str(solv, select, what)); + FOR_JOB_SELECT(p, pp, select, what) { - const char *name = id2str(pool, s->name); - if (name[0] == 'a' && !strncmp(name, "atom:", 5)) - { - addrule(solv, 0, 0); - continue; - } + s = pool->solvables + p; + if (installed && s->repo == installed) + solver_addrule(solv, p, 0); + else + solver_addrule(solv, -p, 0); + queue_push(&solv->ruletojob, i); + if (weak) + queue_push(&solv->weakruleq, solv->nrules - 1); } - if (s->repo == installed) + break; + case SOLVER_DISTUPGRADE: + POOL_DEBUG(SAT_DEBUG_JOB, "job: distupgrade repo #%d\n", what); + break; + default: + POOL_DEBUG(SAT_DEBUG_JOB, "job: unknown job\n"); + break; + } + + /* + * debug + */ + + IF_POOLDEBUG (SAT_DEBUG_JOB) + { + int j; + if (solv->nrules == oldnrules) + POOL_DEBUG(SAT_DEBUG_JOB, " - no rule created\n"); + for (j = oldnrules; j < solv->nrules; j++) { - Rule *sr; - addupdaterule(solv, s, 1); /* allowall = 0 */ - if (solv->allowuninstall) - { - queue_push(&solv->weakruleq, solv->nrules - 1); - continue; - } - r = solv->rules + solv->nrules - 1; - sr = r - (installed->end - installed->start); - if (sr->p) - disablerule(solv, r); - if (sr->p && !unifyrules_sortcmp(r, sr)) - { - /* identical rule, kill feature rule */ - memset(r, 0, sizeof(*r)); - } + POOL_DEBUG(SAT_DEBUG_JOB, " - job "); + solver_printrule(solv, SAT_DEBUG_JOB, solv->rules + j); } - else - addrule(solv, 0, 0); /* create dummy rule */ } - assert(solv->nrules - solv->featurerules == installed->end - installed->start); } + assert(solv->ruletojob.count == solv->nrules - solv->jobrules); + solv->jobrules_end = solv->nrules; + + /* now create infarch and dup rules */ + if (!solv->noinfarchcheck) + solver_addinfarchrules(solv, &addedmap); + else + solv->infarchrules = solv->infarchrules_end = solv->nrules; + + if (hasdupjob) + { + solver_addduprules(solv, &addedmap); + solver_freedupmaps(solv); /* no longer needed */ + } + else + solv->duprules = solv->duprules_end = solv->nrules; + + /* all rules created + * -------------------------------------------------------------- + * prepare for solving + */ + /* free unneeded memory */ map_free(&addedmap); + map_free(&installcandidatemap); queue_free(&q); + POOL_DEBUG(SAT_DEBUG_STATS, "%d rpm rules, %d job rules, %d infarch rules, %d dup rules\n", solv->rpmrules_end - 1, solv->jobrules_end - solv->jobrules, solv->infarchrules_end - solv->infarchrules, solv->duprules_end - solv->duprules); + /* create weak map */ map_init(&solv->weakrulemap, solv->nrules); for (i = 0; i < solv->weakruleq.count; i++) @@ -3555,199 +2786,327 @@ solver_solve(Solver *solv, Queue *job) /* all new rules are learnt after this point */ solv->learntrules = solv->nrules; - /* disable update rules that conflict with our job */ - disableupdaterules(solv, job, -1); + /* create watches chains */ + makewatches(solv); + + /* create assertion index. it is only used to speed up + * makeruledecsions() a bit */ + for (i = 1, r = solv->rules + i; i < solv->nrules; i++, r++) + if (r->p && !r->w2 && (r->d == 0 || r->d == -1)) + queue_push(&solv->ruleassertions, i); + /* disable update rules that conflict with our job */ + solver_disablepolicyrules(solv); /* make decisions based on job/update assertions */ makeruledecisions(solv); + POOL_DEBUG(SAT_DEBUG_STATS, "problems so far: %d\n", solv->problems.count); - /* create watches chains */ - makewatches(solv); + /* + * ******************************************** + * solve! + * ******************************************** + */ + + now = sat_timems(0); + solver_run_sat(solv, 1, solv->dontinstallrecommended ? 0 : 1); + POOL_DEBUG(SAT_DEBUG_STATS, "solver took %d ms\n", sat_timems(now)); - POOL_DEBUG(SAT_DEBUG_STATS, "problems so far: %d\n", solv->problems.count); + /* + * calculate recommended/suggested packages + */ + findrecommendedsuggested(solv); - /* solve! */ - run_solver(solv, 1, solv->dontinstallrecommended ? 0 : 1); + /* + * prepare solution queue if there were problems + */ + solver_prepare_solutions(solv); - queue_init(&redoq); - goterase = 0; - /* disable all erase jobs (continuing weak "keep uninstalled" rules) */ - for (i = solv->jobrules, r = solv->rules + i; i < solv->updaterules; i++, r++) + /* + * finally prepare transaction info + */ + solver_create_transaction(solv); + + POOL_DEBUG(SAT_DEBUG_STATS, "final solver statistics: %d problems, %d learned rules, %d unsolvable\n", solv->problems.count / 2, solv->stats_learned, solv->stats_unsolvable); + POOL_DEBUG(SAT_DEBUG_STATS, "solver_solve took %d ms\n", sat_timems(solve_start)); +} + +/***********************************************************************/ +/* disk usage computations */ + +/*------------------------------------------------------------------- + * + * calculate DU changes + */ + +void +solver_calc_duchanges(Solver *solv, DUChanges *mps, int nmps) +{ + Map installedmap; + + solver_create_state_maps(solv, &installedmap, 0); + pool_calc_duchanges(solv->pool, &installedmap, mps, nmps); + map_free(&installedmap); +} + + +/*------------------------------------------------------------------- + * + * calculate changes in install size + */ + +int +solver_calc_installsizechange(Solver *solv) +{ + Map installedmap; + int change; + + solver_create_state_maps(solv, &installedmap, 0); + change = pool_calc_installsizechange(solv->pool, &installedmap); + map_free(&installedmap); + return change; +} + +void +solver_trivial_installable(Solver *solv, Queue *pkgs, Queue *res) +{ + Map installedmap; + solver_create_state_maps(solv, &installedmap, 0); + pool_trivial_installable_noobsoletesmap(solv->pool, &installedmap, pkgs, res, solv->noobsoletes.size ? &solv->noobsoletes : 0); + map_free(&installedmap); +} + + +#if 0 +#define FIND_INVOLVED_DEBUG 0 +void +solver_find_involved(Solver *solv, Queue *installedq, Solvable *ts, Queue *q) +{ + Pool *pool = solv->pool; + Map im; + Map installedm; + Solvable *s; + Queue iq; + Queue installedq_internal; + Id tp, ip, p, pp, req, *reqp, sup, *supp; + int i, count; + + tp = ts - pool->solvables; + queue_init(&iq); + queue_init(&installedq_internal); + map_init(&im, pool->nsolvables); + map_init(&installedm, pool->nsolvables); + + if (!installedq) { - if (!r->w1) - continue; - if (r->p > 0) /* install job? */ - continue; - disablerule(solv, r); - goterase++; + installedq = &installedq_internal; + if (solv->installed) + { + for (ip = solv->installed->start; ip < solv->installed->end; ip++) + { + s = pool->solvables + ip; + if (s->repo != solv->installed) + continue; + queue_push(installedq, ip); + } + } } - - if (goterase) + for (i = 0; i < installedq->count; i++) { - enabledisablelearntrules(solv); - removedisabledconflicts(solv, &redoq); + ip = installedq->elements[i]; + MAPSET(&installedm, ip); + MAPSET(&im, ip); } - /* find recommended packages */ - /* if redoq.count == 0 we already found all recommended in the - * solver run */ - if (redoq.count || solv->dontinstallrecommended) + queue_push(&iq, ts - pool->solvables); + while (iq.count) { - Id rec, *recp, p, *pp; - - /* create map of all suggests that are still open */ - solv->recommends_index = -1; - MAPZERO(&solv->recommendsmap); - for (i = 0; i < solv->decisionq.count; i++) + ip = queue_shift(&iq); + if (!MAPTST(&im, ip)) + continue; + if (!MAPTST(&installedm, ip)) + continue; + MAPCLR(&im, ip); + s = pool->solvables + ip; +#if FIND_INVOLVED_DEBUG + printf("hello %s\n", solvable2str(pool, s)); +#endif + if (s->requires) { - p = solv->decisionq.elements[i]; - if (p < 0) - continue; - s = pool->solvables + p; - if (s->recommends) + reqp = s->repo->idarraydata + s->requires; + while ((req = *reqp++) != 0) { - recp = s->repo->idarraydata + s->recommends; - while ((rec = *recp++) != 0) + if (req == SOLVABLE_PREREQMARKER) + continue; + /* count number of installed packages that match */ + count = 0; + FOR_PROVIDES(p, pp, req) + if (MAPTST(&installedm, p)) + count++; + if (count > 1) + continue; + FOR_PROVIDES(p, pp, req) { - FOR_PROVIDES(p, pp, rec) - if (solv->decisionmap[p] > 0) - break; - if (p) - continue; /* p != 0: already fulfilled */ - FOR_PROVIDES(p, pp, rec) - MAPSET(&solv->recommendsmap, p); + if (MAPTST(&im, p)) + { +#if FIND_INVOLVED_DEBUG + printf("%s requires %s\n", solvid2str(pool, ip), solvid2str(pool, p)); +#endif + queue_push(&iq, p); + } } } } - for (i = 1; i < pool->nsolvables; i++) + if (s->recommends) { - if (solv->decisionmap[i] != 0) - continue; - s = pool->solvables + i; - if (!MAPTST(&solv->recommendsmap, i)) + reqp = s->repo->idarraydata + s->recommends; + while ((req = *reqp++) != 0) { - if (!s->supplements) + count = 0; + FOR_PROVIDES(p, pp, req) + if (MAPTST(&installedm, p)) + count++; + if (count > 1) continue; - if (!pool_installable(pool, s)) + FOR_PROVIDES(p, pp, req) + { + if (MAPTST(&im, p)) + { +#if FIND_INVOLVED_DEBUG + printf("%s recommends %s\n", solvid2str(pool, ip), solvid2str(pool, p)); +#endif + queue_push(&iq, p); + } + } + } + } + if (!iq.count) + { + /* supplements pass */ + for (i = 0; i < installedq->count; i++) + { + ip = installedq->elements[i]; + s = pool->solvables + ip; + if (!s->supplements) continue; - if (!solver_is_supplementing(solv, s)) + if (!MAPTST(&im, ip)) continue; + supp = s->repo->idarraydata + s->supplements; + while ((sup = *supp++) != 0) + if (!dep_possible(solv, sup, &im) && dep_possible(solv, sup, &installedm)) + break; + /* no longer supplemented, also erase */ + if (sup) + { +#if FIND_INVOLVED_DEBUG + printf("%s supplemented\n", solvid2str(pool, ip)); +#endif + queue_push(&iq, ip); + } } - if (solv->dontinstallrecommended) - queue_push(&solv->recommendations, i); - else - queue_pushunique(&solv->recommendations, i); } - /* we use MODE_SUGGEST here so that repo prio is ignored */ - policy_filter_unwanted(solv, &solv->recommendations, 0, POLICY_MODE_SUGGEST); } - /* find suggested packages */ - if (1) + for (i = 0; i < installedq->count; i++) { - Id sug, *sugp, p, *pp; + ip = installedq->elements[i]; + if (MAPTST(&im, ip)) + queue_push(&iq, ip); + } - /* create map of all suggests that are still open */ - solv->recommends_index = -1; - MAPZERO(&solv->suggestsmap); - for (i = 0; i < solv->decisionq.count; i++) + while (iq.count) + { + ip = queue_shift(&iq); + if (!MAPTST(&installedm, ip)) + continue; + s = pool->solvables + ip; +#if FIND_INVOLVED_DEBUG + printf("bye %s\n", solvable2str(pool, s)); +#endif + if (s->requires) { - p = solv->decisionq.elements[i]; - if (p < 0) - continue; - s = pool->solvables + p; - if (s->suggests) + reqp = s->repo->idarraydata + s->requires; + while ((req = *reqp++) != 0) { - sugp = s->repo->idarraydata + s->suggests; - while ((sug = *sugp++) != 0) + FOR_PROVIDES(p, pp, req) { - FOR_PROVIDES(p, pp, sug) - if (solv->decisionmap[p] > 0) - break; - if (p) - continue; /* already fulfilled */ - FOR_PROVIDES(p, pp, sug) - MAPSET(&solv->suggestsmap, p); + if (!MAPTST(&im, p)) + { + if (p == tp) + continue; +#if FIND_INVOLVED_DEBUG + printf("%s requires %s\n", solvid2str(pool, ip), solvid2str(pool, p)); +#endif + MAPSET(&im, p); + queue_push(&iq, p); + } } } } - for (i = 1; i < pool->nsolvables; i++) + if (s->recommends) { - if (solv->decisionmap[i] != 0) - continue; - s = pool->solvables + i; - if (!MAPTST(&solv->suggestsmap, i)) + reqp = s->repo->idarraydata + s->recommends; + while ((req = *reqp++) != 0) { - if (!s->enhances) - continue; - if (!pool_installable(pool, s)) + FOR_PROVIDES(p, pp, req) + { + if (!MAPTST(&im, p)) + { + if (p == tp) + continue; +#if FIND_INVOLVED_DEBUG + printf("%s recommends %s\n", solvid2str(pool, ip), solvid2str(pool, p)); +#endif + MAPSET(&im, p); + queue_push(&iq, p); + } + } + } + } + if (!iq.count) + { + /* supplements pass */ + for (i = 0; i < installedq->count; i++) + { + ip = installedq->elements[i]; + if (ip == tp) + continue; + s = pool->solvables + ip; + if (!s->supplements) continue; - if (!solver_is_enhancing(solv, s)) + if (MAPTST(&im, ip)) continue; + supp = s->repo->idarraydata + s->supplements; + while ((sup = *supp++) != 0) + if (dep_possible(solv, sup, &im)) + break; + if (sup) + { +#if FIND_INVOLVED_DEBUG + printf("%s supplemented\n", solvid2str(pool, ip)); +#endif + MAPSET(&im, ip); + queue_push(&iq, ip); + } } - queue_push(&solv->suggestions, i); } - policy_filter_unwanted(solv, &solv->suggestions, 0, POLICY_MODE_SUGGEST); - } - - if (redoq.count) - { - /* restore decisionmap */ - for (i = 0; i < redoq.count; i += 2) - solv->decisionmap[redoq.elements[i]] = redoq.elements[i + 1]; } + + queue_free(&iq); - - if (solv->problems.count) + /* convert map into result */ + for (i = 0; i < installedq->count; i++) { - int recocount = solv->recommendations.count; - solv->recommendations.count = 0; /* so that revert() doesn't mess with it */ - queue_empty(&redoq); - for (i = 0; i < solv->decisionq.count; i++) - { - Id p = solv->decisionq.elements[i]; - queue_push(&redoq, p); - queue_push(&redoq, solv->decisionq_why.elements[i]); - queue_push(&redoq, solv->decisionmap[p > 0 ? p : -p]); - } - problems_to_solutions(solv, job); - memset(solv->decisionmap, 0, pool->nsolvables * sizeof(Id)); - queue_empty(&solv->decisionq); - queue_empty(&solv->decisionq_why); - for (i = 0; i < redoq.count; i += 3) - { - Id p = redoq.elements[i]; - queue_push(&solv->decisionq, p); - queue_push(&solv->decisionq_why, redoq.elements[i + 1]); - solv->decisionmap[p > 0 ? p : -p] = redoq.elements[i + 2]; - } - solv->recommendations.count = recocount; + ip = installedq->elements[i]; + if (MAPTST(&im, ip)) + continue; + if (ip == ts - pool->solvables) + continue; + queue_push(q, ip); } - queue_free(&redoq); -} - -/***********************************************************************/ - -void -solver_calc_duchanges(Solver *solv, DUChanges *mps, int nmps) -{ - Map installedmap; - - solver_create_state_maps(solv, &installedmap, 0); - pool_calc_duchanges(solv->pool, solv->installed, &installedmap, mps, nmps); - map_free(&installedmap); -} - -int -solver_calc_installsizechange(Solver *solv) -{ - Map installedmap; - int change; - - solver_create_state_maps(solv, &installedmap, 0); - change = pool_calc_installsizechange(solv->pool, solv->installed, &installedmap); - map_free(&installedmap); - return change; + map_free(&im); + map_free(&installedm); + queue_free(&installedq_internal); } +#endif