X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=src%2Fsolver.c;h=f188026d7d547f4bfa51734382ae13c49064684c;hb=1a93853889c819ac2d3c8e83e856f4775e664b00;hp=efda5044a6d7066c7853e35bebe745715b2cc2c0;hpb=f41acbdf08531db1bad1064091efaf199f00a453;p=platform%2Fupstream%2Flibsolv.git diff --git a/src/solver.c b/src/solver.c index efda504..f551731 100644 --- a/src/solver.c +++ b/src/solver.c @@ -18,15 +18,19 @@ #include #include "solver.h" +#include "solver_private.h" #include "bitmap.h" #include "pool.h" #include "util.h" -#include "evr.h" #include "policy.h" +#include "poolarch.h" #include "solverdebug.h" +#include "cplxdeps.h" +#include "linkedpkg.h" #define RULES_BLOCK 63 + /******************************************************************** * * dependency check helpers @@ -35,10 +39,33 @@ /*------------------------------------------------------------------- * handle split provides + * + * a splitprovides dep looks like + * namespace:splitprovides(pkg REL_WITH path) + * and is only true if pkg is installed and contains the specified path. + * we also make sure that pkg is selected for an update, otherwise the + * update would always be forced onto the user. + * Map m is the map used when called from dep_possible. */ +static int +solver_is_updating(Solver *solv, Id p) +{ + /* check if the update rule is true */ + Pool *pool = solv->pool; + Rule *r; + Id l, pp; + if (solv->decisionmap[p] >= 0) + return 0; /* old package stayed */ + r = solv->rules + solv->updaterules + (p - solv->installed->start); + FOR_RULELITERALS(l, pp, r) + if (l > 0 && l != p && solv->decisionmap[l] > 0) + return 1; + return 0; +} + int -solver_splitprovides(Solver *solv, Id dep) +solver_splitprovides(Solver *solv, Id dep, Map *m) { Pool *pool = solv->pool; Id p, pp; @@ -52,1474 +79,475 @@ solver_splitprovides(Solver *solv, Id dep) rd = GETRELDEP(pool, dep); if (rd->flags != REL_WITH) return 0; - FOR_PROVIDES(p, pp, dep) + /* + * things are a bit tricky here if pool->addedprovides == 1, because most split-provides are in + * a non-standard location. If we simply call pool_whatprovides, we'll drag in the complete + * file list. Instead we rely on pool_addfileprovides ignoring the addfileprovidesfiltered flag + * for installed packages and check the lazywhatprovidesq (ignoring the REL_WITH part, but + * we filter the package name further down anyway). + */ + if (pool->addedfileprovides == 1 && !ISRELDEP(rd->evr) && !pool->whatprovides[rd->evr]) + pp = pool_searchlazywhatprovidesq(pool, rd->evr); + else + pp = pool_whatprovides(pool, dep); + while ((p = pool->whatprovidesdata[pp++]) != 0) { + /* here we have packages that provide the correct name and contain the path, + * now do extra filtering */ s = pool->solvables + p; - if (s->repo == solv->installed && s->name == rd->name) + if (s->repo != solv->installed || s->name != rd->name) + continue; + /* check if the package is updated. if m is set, we're called from dep_possible */ + if (m || solver_is_updating(solv, p)) return 1; } return 0; } -/*------------------------------------------------------------------- - * solver_dep_installed - */ - -int -solver_dep_installed(Solver *solv, Id dep) +/* mirrors solver_dep_fulfilled, but returns 2 if a new package + * was involved */ +static int +solver_dep_fulfilled_alreadyinstalled(Solver *solv, Id dep) { -#if 0 Pool *pool = solv->pool; Id p, pp; + int r; if (ISRELDEP(dep)) { Reldep *rd = GETRELDEP(pool, dep); if (rd->flags == REL_AND) - { - if (!solver_dep_installed(solv, rd->name)) + { + int r2, r1 = solver_dep_fulfilled_alreadyinstalled(solv, rd->name); + if (!r1) + return 0; + r2 = solver_dep_fulfilled_alreadyinstalled(solv, rd->evr); + if (!r2) return 0; - return solver_dep_installed(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 (p == SYSTEMSOLVABLE || (solv->installed && pool->solvables[p].repo == solv->installed)) - return 1; - } -#endif - return 0; -} - - -/*------------------------------------------------------------------- - * Check if dependenc is possible - * - * 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) + return r1 == 2 || r2 == 2 ? 2 : 1; + } + if (rd->flags == REL_OR) { - if (!dep_possible(solv, rd->name, m)) + int r2, r1 = solver_dep_fulfilled_alreadyinstalled(solv, rd->name); + r2 = solver_dep_fulfilled_alreadyinstalled(solv, rd->evr); + if (!r1 && !r2) return 0; - return dep_possible(solv, rd->evr, m); + return r1 == 2 || r2 == 2 ? 2 : 1; } 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); + return solver_splitprovides(solv, rd->evr, 0); + if (rd->flags == REL_NAMESPACE && solv->installsuppdepq) + { + Queue *q = solv->installsuppdepq; + int i; + for (i = 0; i < q->count; i++) + if (q->elements[i] == dep || q->elements[i] == rd->name) + return 2; + } } + r = 0; FOR_PROVIDES(p, pp, dep) - { - if (MAPTST(m, p)) - return 1; - } - return 0; + if (solv->decisionmap[p] > 0) + { + Solvable *s = pool->solvables + p; + if (s->repo && s->repo != solv->installed) + return 2; + r = 1; + } + return r; } -/******************************************************************** - * - * Rule handling - * - * - unify rules, remove duplicates - */ - -static Pool *unifyrules_sortcmp_data; - -/*------------------------------------------------------------------- - * - * compare rules for unification sort - * - */ - static int -unifyrules_sortcmp(const void *ap, const void *bp) +solver_is_supplementing_alreadyinstalled(Solver *solv, Solvable *s) { - 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 */ + Id sup, *supp; + supp = s->repo->idarraydata + s->supplements; + while ((sup = *supp++) != 0) + if (solver_dep_fulfilled_alreadyinstalled(solv, sup) == 2) + return 1; + return 0; +} - /* identical p */ - if (a->d == 0 && b->d == 0) - return a->w2 - b->w2; /* assertion: return w2 diff */ +static Id +autouninstall(Solver *solv, Id *problem) +{ + Pool *pool = solv->pool; + int i; + int lastfeature = 0, lastupdate = 0; + Id v; + Id extraflags = -1; - if (a->d == 0) /* a is assertion, b not */ + for (i = 0; (v = problem[i]) != 0; i++) { - x = a->w2 - pool->whatprovidesdata[b->d]; - return x ? x : -1; + if (v < 0) + extraflags &= solv->job.elements[-v - 1]; + if (v >= solv->updaterules && v < solv->updaterules_end) + { + /* check if identical to feature rule, we don't like that */ + Rule *r = solv->rules + solv->featurerules + (v - solv->updaterules); + if (!r->p) + { + /* update rule == feature rule */ + if (v > lastfeature) + lastfeature = v; + continue; + } + if (v > lastupdate) + lastupdate = v; + } } - - if (b->d == 0) /* b is assertion, a not */ + if (!lastupdate && !lastfeature) + return 0; + v = lastupdate ? lastupdate : lastfeature; + POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "allowuninstall disabling "); + solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE, solv->rules + v); + solver_disableproblem(solv, v); + if (extraflags != -1 && (extraflags & SOLVER_CLEANDEPS) != 0 && solv->cleandepsmap.size) { - x = pool->whatprovidesdata[a->d] - b->w2; - return x ? x : 1; + /* add the package to the updatepkgs list, this will automatically turn + * on cleandeps mode */ + Id p = solv->rules[v].p; + if (!solv->cleandeps_updatepkgs) + { + solv->cleandeps_updatepkgs = solv_calloc(1, sizeof(Queue)); + queue_init(solv->cleandeps_updatepkgs); + } + if (p > 0) + { + int oldupdatepkgscnt = solv->cleandeps_updatepkgs->count; + queue_pushunique(solv->cleandeps_updatepkgs, p); + if (solv->cleandeps_updatepkgs->count != oldupdatepkgscnt) + solver_disablepolicyrules(solv); + } } - - /* compare whatprovidesdata */ - ad = pool->whatprovidesdata + a->d; - bd = pool->whatprovidesdata + b->d; - while (*bd) - if ((x = *ad++ - *bd++) != 0) - return x; - return *ad; + return v; } +/************************************************************************/ -/*------------------------------------------------------------------- +/* + * enable/disable learnt rules * - * unify rules - * go over all rules and remove duplicates + * we have enabled or disabled some of our rules. We now reenable all + * of our learnt rules except the ones that were learnt from rules that + * are now disabled. */ - static void -unifyrules(Solver *solv) +enabledisablelearntrules(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); + Rule *r; + Id why, *whyp; + int i; - /* adapt rule buffer */ - solv->nrules = j; - solv->rules = sat_extend_resize(solv->rules, solv->nrules, sizeof(Rule), RULES_BLOCK); - /* - * debug: statistics - */ - IF_POOLDEBUG (SAT_DEBUG_STATS) + POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "enabledisablelearntrules called\n"); + for (i = solv->learntrules, r = solv->rules + i; i < solv->nrules; i++, r++) { - int binr = 0; - int lits = 0; - Id *dp; - Rule *r; - - for (i = 1; i < solv->nrules; i++) + whyp = solv->learnt_pool.elements + solv->learnt_why.elements[i - solv->learntrules]; + while ((why = *whyp++) != 0) { - r = solv->rules + i; - if (r->d == 0) - binr++; - else + assert(why > 0 && why < i); + if (solv->rules[why].d < 0) + break; + } + /* why != 0: we found a disabled rule, disable the learnt rule */ + if (why && r->d >= 0) + { + IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS) + { + POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "disabling "); + solver_printruleclass(solv, SOLV_DEBUG_SOLUTIONS, r); + } + solver_disablerule(solv, r); + } + else if (!why && r->d < 0) + { + IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS) { - dp = solv->pool->whatprovidesdata + r->d; - while (*dp++) - lits++; + POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "re-enabling "); + solver_printruleclass(solv, SOLV_DEBUG_SOLUTIONS, r); } + solver_enablerule(solv, r); } - 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 + * make assertion rules into decisions * - * always returns a rule for non-rpm rules + * Go through rules and add direct assertions to the decisionqueue. + * If we find a conflict, disable rules and add them to problem queue. */ -static Rule * -addrule(Solver *solv, Id p, Id d) +static void +makeruledecisions(Solver *solv) { 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 - >1 = - */ + int i, ri, ii; + Rule *r, *rr; + Id v, vv; + int decisionstart; + int record_proof = 1; + int oldproblemcount; + int havedisabled = 0; - /* 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 */ + /* 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' */ - if (solv->nrules /* we already have rules */ - && !solv->rpmrules_end) /* but are not done with rpm rules */ + decisionstart = solv->decisionq.count; + for (;;) { - 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 we needed to re-run, back up decisions to decisionstart */ + while (solv->decisionq.count > decisionstart) + { + v = solv->decisionq.elements[--solv->decisionq.count]; + --solv->decisionq_why.count; + vv = v > 0 ? v : -v; + solv->decisionmap[vv] = 0; + } - /* - * compute number of literals (n) in rule - */ - - 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) /* have single provider */ - d = dp[-1]; /* take single literal */ - } + /* note that the ruleassertions queue is ordered */ + for (ii = 0; ii < solv->ruleassertions.count; ii++) + { + ri = solv->ruleassertions.elements[ii]; + r = solv->rules + ri; -#if 0 - if (n == 0 && !solv->rpmrules_end) - { - /* 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 (havedisabled && ri >= solv->learntrules) + { + /* just started with learnt rule assertions. If we have disabled + * some rules, adapt the learnt rule status */ + enabledisablelearntrules(solv); + havedisabled = 0; + } - if (n == 1 && p > d && !solv->rpmrules_end) - { - /* smallest literal first so we can find dups */ - n = p; p = d; d = n; /* p <-> d */ - n = 1; /* re-set n, was used as temp var */ - } + if (r->d < 0 || !r->p || r->w2) /* disabled, dummy or no assertion */ + continue; - /* - * check for duplicate - */ - - /* check if the last added rule (r) 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 */ + /* do weak rules in phase 2 */ + if (ri < solv->learntrules && solv->weakrulemap.size && MAPTST(&solv->weakrulemap, ri)) + continue; - /* have n-ary rule with same first literal, check other literals */ - 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; - } + v = r->p; + vv = v > 0 ? v : -v; - /* - * allocate new rule - */ + if (!solv->decisionmap[vv]) /* if not yet decided */ + { + queue_push(&solv->decisionq, v); + queue_push(&solv->decisionq_why, r - solv->rules); + solv->decisionmap[vv] = v > 0 ? 1 : -1; + IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE) + { + Solvable *s = solv->pool->solvables + vv; + if (v < 0) + POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "conflicting %s (assertion)\n", pool_solvable2str(solv->pool, s)); + else + POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "installing %s (assertion)\n", pool_solvable2str(solv->pool, s)); + } + continue; + } - /* 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 */ + /* check against previous decision: is there a conflict? */ + if (v > 0 && solv->decisionmap[vv] > 0) /* ok to install */ + continue; + if (v < 0 && solv->decisionmap[vv] < 0) /* ok to remove */ + continue; - /* - * r = new rule - */ - - 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; + /* + * 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_POOLDEBUG (SAT_DEBUG_RULE_CREATION) - { - POOL_DEBUG(SAT_DEBUG_RULE_CREATION, " Add rule: "); - solver_printrule(solv, SAT_DEBUG_RULE_CREATION, r); - } + 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 */ + /* (XXX: we should really call analyze_unsolvable_rule here!) */ + solver_disablerule(solv, r); + continue; + } - return r; -} + /* + * 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 that we found it */ + oldproblemcount = solv->problems.count; -/*------------------------------------------------------------------- - * disable rule - */ + /* + * conflict with system solvable ? + */ + if (v == -SYSTEMSOLVABLE) + { + if (record_proof) + { + queue_push(&solv->problems, solv->learnt_pool.count); + queue_push(&solv->learnt_pool, ri); + queue_push(&solv->learnt_pool, 0); + } + else + queue_push(&solv->problems, 0); + POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "conflict with system solvable, disabling rule #%d\n", ri); + 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); + if (solv->allowuninstall && v >= solv->featurerules && v < solv->updaterules_end) + solv->problems.count = oldproblemcount; + solver_disableproblem(solv, v); + havedisabled = 1; + break; /* start over */ + } -static inline void -disablerule(Solver *solv, Rule *r) -{ - if (r->d >= 0) - r->d = -r->d - 1; -} + assert(solv->decisionq_why.elements[i] > 0); -/*------------------------------------------------------------------- - * enable rule - */ + /* + * conflict with a pkg rule ? + */ + if (solv->decisionq_why.elements[i] < solv->pkgrules_end) + { + if (record_proof) + { + queue_push(&solv->problems, solv->learnt_pool.count); + queue_push(&solv->learnt_pool, ri); + queue_push(&solv->learnt_pool, solv->decisionq_why.elements[i]); + queue_push(&solv->learnt_pool, 0); + } + else + queue_push(&solv->problems, 0); + assert(v > 0 || v == -SYSTEMSOLVABLE); + POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "conflict with pkg rule, disabling rule #%d\n", ri); + 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); + if (solv->allowuninstall && v >= solv->featurerules && v < solv->updaterules_end) + solv->problems.count = oldproblemcount; + solver_disableproblem(solv, v); + havedisabled = 1; + break; /* start over */ + } -static inline void -enablerule(Solver *solv, Rule *r) -{ - if (r->d < 0) - r->d = -r->d - 1; -} + /* + * conflict with another job or update/feature rule + */ + /* record proof */ + if (record_proof) + { + queue_push(&solv->problems, solv->learnt_pool.count); + queue_push(&solv->learnt_pool, ri); + queue_push(&solv->learnt_pool, solv->decisionq_why.elements[i]); + queue_push(&solv->learnt_pool, 0); + } + else + queue_push(&solv->problems, 0); -/**********************************************************************************/ + POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "conflicting update/job assertions over literal %d\n", vv); -/* 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. - */ - -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->jobrules_end; i++, r++, jp++) - if (*jp == v) - disablerule(solv, r); -} - -/*------------------------------------------------------------------- - * enableproblem - */ - -static void -enableproblem(Solver *solv, Id v) -{ - Rule *r; - int i; - Id *jp; - - if (v > 0) - { - if (v >= solv->featurerules && v < solv->featurerules_end) - { - /* do not enable feature rule if update rule is enabled */ - r = solv->rules + (v - solv->featurerules + solv->updaterules); - if (r->d >= 0) - return; - } - enablerule(solv, solv->rules + v); - if (v >= solv->updaterules && v < solv->updaterules_end) - { - /* disable feature rule when enabling update rule */ - r = solv->rules + (v - solv->updaterules + solv->featurerules); - if (r->p) - disablerule(solv, r); - } - return; - } - v = -(v + 1); - jp = solv->ruletojob.elements; - for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++, jp++) - if (*jp == v) - enablerule(solv, r); -} - - -/************************************************************************/ - -/* - * make assertion rules into decisions - * - * 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, ii; - Rule *r, *rr; - Id v, vv; - int decisionstart; - - POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- makeruledecisions ; size decisionq: %d -----\n",solv->decisionq.count); - - decisionstart = solv->decisionq.count; - for (ii = 0; ii < solv->ruleassertions.count; ii++) - { - 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 not yet decided */ - { - /* - * decide ! - */ - queue_push(&solv->decisionq, v); - queue_push(&solv->decisionq_why, r - solv->rules); - solv->decisionmap[vv] = v > 0 ? 1 : -1; - IF_POOLDEBUG (SAT_DEBUG_PROPAGATE) - { - Solvable *s = solv->pool->solvables + vv; - if (v < 0) - POOL_DEBUG(SAT_DEBUG_PROPAGATE, "conflicting %s (assertion)\n", solvable2str(solv->pool, s)); - else - POOL_DEBUG(SAT_DEBUG_PROPAGATE, "installing %s (assertion)\n", solvable2str(solv->pool, s)); - } - continue; - } - /* - * check previous decision: is it sane ? - */ - - if (v > 0 && solv->decisionmap[vv] > 0) /* ok to install */ - continue; - if (v < 0 && solv->decisionmap[vv] < 0) /* ok to remove */ - continue; - - /* - * 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); - continue; - } - - /* - * 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 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->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); - continue; - } - - assert(solv->decisionq_why.elements[i]); - - /* - * 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); - queue_push(&solv->learnt_pool, ri); - queue_push(&solv->learnt_pool, solv->decisionq_why.elements[i]); - 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->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); - continue; - } - - /* - * conflict with another job or update/feature rule - */ - - /* record proof */ - queue_push(&solv->problems, solv->learnt_pool.count); - queue_push(&solv->learnt_pool, ri); - queue_push(&solv->learnt_pool, solv->decisionq_why.elements[i]); - queue_push(&solv->learnt_pool, 0); - - POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "conflicting update/job assertions over literal %d\n", vv); - - /* - * 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->d < 0 /* disabled */ - || rr->w2) /* or no assertion */ - continue; - if (rr->p != vv /* not affecting the literal */ - && rr->p != -vv) - continue; - 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; - /* 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); - } - queue_push(&solv->problems, 0); - - /* - * start over - * (back up from decisions) - */ - while (solv->decisionq.count > decisionstart) - { - v = solv->decisionq.elements[--solv->decisionq.count]; - --solv->decisionq_why.count; - vv = v > 0 ? v : -v; - solv->decisionmap[vv] = 0; - } - ii = -1; /* restarts loop at 0 */ - } - - /* - * phase 2: now do the weak assertions - */ - for (ii = 0; ii < solv->ruleassertions.count; ii++) - { - 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)) /* 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); - queue_push(&solv->decisionq_why, r - solv->rules); - solv->decisionmap[vv] = v > 0 ? 1 : -1; - IF_POOLDEBUG (SAT_DEBUG_PROPAGATE) - { - Solvable *s = solv->pool->solvables + vv; - if (v < 0) - POOL_DEBUG(SAT_DEBUG_PROPAGATE, "conflicting %s (weak assertion)\n", solvable2str(solv->pool, s)); - else - POOL_DEBUG(SAT_DEBUG_PROPAGATE, "installing %s (weak assertion)\n", solvable2str(solv->pool, s)); - } - 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); - } - - 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 - * are now disabled. - */ -static void -enabledisablelearntrules(Solver *solv) -{ - Pool *pool = solv->pool; - Rule *r; - Id why, *whyp; - int i; - - POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "enabledisablelearntrules called\n"); - for (i = solv->learntrules, r = solv->rules + i; i < solv->nrules; i++, r++) - { - whyp = solv->learnt_pool.elements + solv->learnt_why.elements[i - solv->learntrules]; - while ((why = *whyp++) != 0) - { - assert(why > 0 && why < i); - if (solv->rules[why].d < 0) - break; - } - /* why != 0: we found a disabled rule, disable the learnt rule */ - 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); - } - 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); - } - } -} - - -/*------------------------------------------------------------------- - * enable weak rules - * - * Enable all rules, except learnt rules, which are - * - disabled and weak (set in weakrulemap) - * - */ - -static void -enableweakrules(Solver *solv) -{ - int i; - Rule *r; - - for (i = 1, r = solv->rules + i; i < solv->learntrules; i++, r++) - { - if (r->d >= 0) /* skip non-direct literals */ - continue; - if (!MAPTST(&solv->weakrulemap, i)) - continue; - enablerule(solv, r); - } -} - - -/* FIXME: bad code ahead, replace as soon as possible */ -/* FIXME: should probably look at SOLVER_INSTALL|SOLVABLE_ONE_OF */ - -/*------------------------------------------------------------------- - * disable update rules - */ - -static void -disableupdaterules(Solver *solv, Queue *job, int jobidx) -{ - Pool *pool = solv->pool; - int i, j; - Id how, select, 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]; - select = how & SOLVER_SELECTMASK; - switch (how & SOLVER_JOBMASK) - { - case SOLVER_ERASE: - break; - case SOLVER_INSTALL: - if (select != SOLVER_SOLVABLE) - return; - break; - default: - return; - } - } - /* go through all enabled job rules */ - MAPZERO(&solv->noupdate); - for (i = solv->jobrules; i < solv->jobrules_end; i++) - { - r = solv->rules + i; - if (r->d < 0) /* disabled? */ - continue; - j = solv->ruletojob.elements[i - solv->jobrules]; - if (j == lastjob) - continue; - lastjob = j; - how = job->elements[j]; - what = job->elements[j + 1]; - select = how & SOLVER_SELECTMASK; - switch (how & SOLVER_JOBMASK) - { - case SOLVER_INSTALL: - if (select != SOLVER_SOLVABLE) - break; - s = pool->solvables + what; - if (solv->noobsoletes.size && MAPTST(&solv->noobsoletes, what)) - break; - if (s->repo == installed) - { - MAPSET(&solv->noupdate, what - installed->start); - break; - } - if (s->obsoletes) - { - Id obs, *obsp; - obsp = s->repo->idarraydata + s->obsoletes; - while ((obs = *obsp++) != 0) - FOR_PROVIDES(p, pp, obs) - { - if (pool->solvables[p].repo != installed) - continue; - if (!solv->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p, obs)) - continue; - MAPSET(&solv->noupdate, p - installed->start); - } - } - FOR_PROVIDES(p, pp, s->name) - { - if (!solv->implicitobsoleteusesprovides && pool->solvables[p].name != s->name) - continue; - if (pool->solvables[p].repo == installed) - MAPSET(&solv->noupdate, p - installed->start); - } - break; - case SOLVER_ERASE: - FOR_JOB_SELECT(p, pp, select, what) - if (pool->solvables[p].repo == installed) - MAPSET(&solv->noupdate, p - installed->start); - break; - default: - break; - } - } - - /* fixup update rule status */ - 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]; - what = job->elements[jobidx + 1]; - select = how & SOLVER_SELECTMASK; - switch (how & SOLVER_JOBMASK) - { - case SOLVER_INSTALL: - if (select != SOLVER_SOLVABLE) - break; - s = pool->solvables + what; - if (s->repo == installed) - { - r = solv->rules + solv->updaterules + (what - installed->start); - if (r->d >= 0) - break; - enablerule(solv, r); - IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS) - { - POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling "); - solver_printrule(solv, SAT_DEBUG_SOLUTIONS, r); - } - break; - } - if (s->obsoletes) - { - Id obs, *obsp; - obsp = s->repo->idarraydata + s->obsoletes; - while ((obs = *obsp++) != 0) - FOR_PROVIDES(p, pp, obs) - { - if (pool->solvables[p].repo != installed) - continue; - if (!solv->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p, obs)) - continue; - if (MAPTST(&solv->noupdate, p - installed->start)) - continue; - r = solv->rules + solv->updaterules + (p - installed->start); - if (r->d >= 0) - continue; - enablerule(solv, r); - IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS) - { - POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling "); - solver_printrule(solv, SAT_DEBUG_SOLUTIONS, r); - } - } - } - FOR_PROVIDES(p, pp, s->name) - { - if (!solv->implicitobsoleteusesprovides && 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->d >= 0) - 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: - FOR_JOB_SELECT(p, pp, select, what) + /* + * 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 (pool->solvables[p].repo != installed) + if (rr->d < 0 /* disabled */ + || rr->w2) /* or no assertion */ continue; - if (MAPTST(&solv->noupdate, p - installed->start)) + if (rr->p != vv /* not affecting the literal */ + && rr->p != -vv) continue; - r = solv->rules + solv->updaterules + (p - installed->start); - if (r->d >= 0) + if (solv->weakrulemap.size && MAPTST(&solv->weakrulemap, i)) /* weak: silently ignore */ continue; - enablerule(solv, r); - IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS) - { - POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling "); - solver_printrule(solv, SAT_DEBUG_SOLUTIONS, r); - } + + POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, " - disabling rule #%d\n", i); + solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE, solv->rules + i); + + v = i; + if (i >= solv->jobrules && i < solv->jobrules_end) + v = -(solv->ruletojob.elements[i - solv->jobrules] + 1); + queue_push(&solv->problems, v); } - break; - default: - break; - } - return; - } - - for (i = 0; i < installed->nsolvables; i++) - { - r = solv->rules + solv->updaterules + i; - if (r->d >= 0 && MAPTST(&solv->noupdate, i)) - disablerule(solv, r); /* was enabled, need to disable */ - r = solv->rules + solv->featurerules + i; - if (r->d >= 0 && MAPTST(&solv->noupdate, i)) - disablerule(solv, r); /* was enabled, need to disable */ - } -} - - -/* - * special multiversion patch conflict handling: - * a patch conflict is also satisfied, if some other - * version with the same name/arch that doesn't conflict - * get's installed. The generated rule is thus: - * -patch|-cpack|opack1|opack2|... - */ -Id -makemultiversionconflict(Solver *solv, Id n, Id con) -{ - Pool *pool = solv->pool; - Solvable *s, *sn; - Queue q; - Id p, pp, qbuf[64]; - - sn = pool->solvables + n; - queue_init_buffer(&q, qbuf, sizeof(qbuf)/sizeof(*qbuf)); - queue_push(&q, -n); - FOR_PROVIDES(p, pp, sn->name) - { - s = pool->solvables + p; - if (s->name != sn->name || s->arch != sn->arch) - continue; - if (!MAPTST(&solv->noobsoletes, p)) - continue; - if (pool_match_nevr(pool, pool->solvables + p, con)) - continue; - /* here we have a multiversion solvable that doesn't conflict */ - /* thus we're not in conflict if it is installed */ - queue_push(&q, p); - } - if (q.count == 1) - return -n; /* no other package found, generate normal conflict */ - return pool_queuetowhatprovides(pool, &q); -} - - -/*------------------------------------------------------------------- - * - * add (install) rules for solvable - * - * s: Solvable for which to add rules - * m: m[s] = 1 for solvables which have rules, prevent rule duplication - * - * Algorithm: 'visit all nodes of a graph'. The graph nodes are - * solvables, the edges their dependencies. - * Starting from an installed solvable, this will create all rules - * representing the graph created by the solvables dependencies. - * - * for unfulfilled requirements, conflicts, obsoletes,.... - * add a negative assertion for solvables that are not installable - * - * It will also create rules for all solvables referenced by 's' - * i.e. descend to all providers of requirements of 's' - * - */ - -static void -addrpmrulesforsolvable(Solver *solv, Solvable *s, Map *m) -{ - Pool *pool = solv->pool; - Repo *installed = solv->installed; - - /* 'work' queue. keeps Ids of solvables we still have to work on. - And buffer for it. */ - Queue workq; - Id workqbuf[64]; - - int i; - /* if to add rules for broken deps ('rpm -V' functionality) - * 0 = yes, 1 = no - */ - int dontfix; - /* Id var and pointer for each dependency - * (not used in parallel) - */ - Id req, *reqp; - Id con, *conp; - Id obs, *obsp; - Id rec, *recp; - Id sug, *sugp; - /* var and ptr for loops */ - Id p, pp; - /* ptr to 'whatprovides' */ - Id *dp; - /* Id for current solvable 's' */ - Id n; - - POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforsolvable -----\n"); - - queue_init_buffer(&workq, workqbuf, sizeof(workqbuf)/sizeof(*workqbuf)); - queue_push(&workq, s - pool->solvables); /* push solvable Id to work queue */ - - /* loop until there's no more work left */ - while (workq.count) - { - /* - * n: Id of solvable - * s: Pointer to solvable - */ - - n = queue_shift(&workq); /* 'pop' next solvable to work on from queue */ - if (MAPTST(m, n)) /* continue if already visited */ - continue; - - MAPSET(m, n); /* mark as visited */ - s = pool->solvables + n; /* s = Solvable in question */ + queue_push(&solv->problems, 0); - 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 (solv->allowuninstall && (v = autouninstall(solv, solv->problems.elements + oldproblemcount + 1)) != 0) + solv->problems.count = oldproblemcount; - 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 */ + for (i = oldproblemcount + 1; i < solv->problems.count - 1; i++) + solver_disableproblem(solv, solv->problems.elements[i]); + havedisabled = 1; + break; /* start over */ } - - /*----------------------------------------- - * check requires of s - */ - - if (s->requires) - { - reqp = s->repo->idarraydata + s->requires; - while ((req = *reqp++) != 0) /* go through all requires */ - { - if (req == SOLVABLE_PREREQMARKER) /* skip the marker */ - continue; - - /* find list of solvables providing 'req' */ - dp = pool->whatprovidesdata + pool_whatprovides(pool, req); - - if (*dp == SYSTEMSOLVABLE) /* always installed */ - continue; - - 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 */ - - /* check if any of the providers for 'req' is installed */ - for (i = 0; (p = dp[i]) != 0; i++) - { - if (pool->solvables[p].repo == installed) - break; /* provider was installed */ - } - /* didn't find an installed provider: previously broken dependency */ - if (!p) - { - 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 - push all non-visited providers on the work queue */ - for (; *dp; dp++) - { - if (!MAPTST(m, *dp)) - queue_push(&workq, *dp); - } - - } /* while, requirements of n */ - - } /* if, requirements */ - - /* that's all we check for src packages */ - if (s->arch == ARCH_SRC || s->arch == ARCH_NOSRC) + if (ii < solv->ruleassertions.count) continue; - /*----------------------------------------- - * check conflicts of s + /* + * phase 2: now do the weak assertions */ - - if (s->conflicts) + if (!solv->weakrulemap.size) + break; /* no weak rules, no phase 2 */ + for (ii = 0; ii < solv->ruleassertions.count; ii++) { - int ispatch = 0; - - /* we treat conflicts in patches a bit differen: - * - nevr matching - * - multiversion handling - * XXX: we should really handle this different, looking - * at the name is a bad hack - */ - if (!strncmp("patch:", id2str(pool, s->name), 6)) - ispatch = 1; - conp = s->repo->idarraydata + s->conflicts; - /* foreach conflicts of 's' */ - while ((con = *conp++) != 0) - { - /* foreach providers of a conflict of 's' */ - FOR_PROVIDES(p, pp, con) - { - if (ispatch && !pool_match_nevr(pool, pool->solvables + p, con)) - continue; - /* dontfix: dont care about conflicts with already installed packs */ - if (dontfix && pool->solvables[p].repo == installed) - continue; - /* p == n: self conflict */ - if (p == n && !solv->allowselfconflicts) - { - if (ISRELDEP(con)) - { - Reldep *rd = GETRELDEP(pool, con); - if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_OTHERPROVIDERS) - continue; - } - p = 0; /* make it a negative assertion, aka 'uninstallable' */ - } - if (p && ispatch && solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p) && ISRELDEP(con)) - { - /* our patch conflicts with a noobsoletes (aka multiversion) package */ - p = -makemultiversionconflict(solv, p, con); - } - /* rule: -n|-p: either solvable _or_ provider of conflict */ - addrule(solv, -n, -p); - } - } - } + ri = solv->ruleassertions.elements[ii]; + r = solv->rules + ri; + if (r->d < 0 || r->w2) /* disabled or no assertion */ + continue; + if (ri >= solv->learntrules || !MAPTST(&solv->weakrulemap, ri)) /* skip non-weak */ + continue; + v = r->p; + vv = v > 0 ? v : -v; - /*----------------------------------------- - * check obsoletes if not installed - * (only installation will trigger the obsoletes in rpm) - */ - if (!installed || pool->solvables[n].repo != installed) - { /* not installed */ - int noobs = solv->noobsoletes.size && MAPTST(&solv->noobsoletes, n); - if (s->obsoletes && !noobs) + if (!solv->decisionmap[vv]) /* if not yet decided */ { - obsp = s->repo->idarraydata + s->obsoletes; - /* foreach obsoletes */ - while ((obs = *obsp++) != 0) + queue_push(&solv->decisionq, v); + queue_push(&solv->decisionq_why, r - solv->rules); + solv->decisionmap[vv] = v > 0 ? 1 : -1; + IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE) { - /* foreach provider of an obsoletes of 's' */ - FOR_PROVIDES(p, pp, obs) - { - if (!solv->obsoleteusesprovides /* obsoletes are matched names, not provides */ - && !pool_match_nevr(pool, pool->solvables + p, obs)) - continue; - addrule(solv, -n, -p); - } - } - } - FOR_PROVIDES(p, pp, s->name) - { - Solvable *ps = pool->solvables + p; - /* we still obsolete packages with same nevra, like rpm does */ - /* (actually, rpm mixes those packages. yuck...) */ - if (noobs && (s->name != ps->name || s->evr != ps->evr || s->arch != ps->arch)) - continue; - if (!solv->implicitobsoleteusesprovides && s->name != ps->name) - continue; - addrule(solv, -n, -p); - } - } - - /*----------------------------------------- - * add recommends to the work queue - */ - if (s->recommends) - { - recp = s->repo->idarraydata + s->recommends; - while ((rec = *recp++) != 0) - { - FOR_PROVIDES(p, pp, rec) - if (!MAPTST(m, p)) - queue_push(&workq, 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(&workq, p); - } - } - } - queue_free(&workq); - POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforsolvable end -----\n"); -} - - -/*------------------------------------------------------------------- - * - * Add package rules for weak rules - * - * m: visited solvables - */ - -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"); - /* foreach solvable in pool */ - for (i = n = 1; n < pool->nsolvables; i++, n++) - { - if (i == pool->nsolvables) /* wrap i */ - i = 1; - if (MAPTST(m, i)) /* been there */ - continue; - - s = pool->solvables + i; - if (!pool_installable(pool, s)) /* only look at installable ones */ - continue; - - sup = 0; - if (s->supplements) - { - /* find possible supplements */ - supp = s->repo->idarraydata + s->supplements; - while ((sup = *supp++) != ID_NULL) - if (dep_possible(solv, sup, m)) - break; - } - - /* if nothing found, check for enhances */ - if (!sup && s->enhances) - { - supp = s->repo->idarraydata + s->enhances; - while ((sup = *supp++) != ID_NULL) - if (dep_possible(solv, sup, m)) - break; - } - /* if nothing found, goto next solvables */ - if (!sup) - continue; - addrpmrulesforsolvable(solv, s, m); - n = 0; - } - POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforweak end -----\n"); -} - - -/*------------------------------------------------------------------- - * - * add package rules for possible updates - * - * s: solvable - * m: map of already visited solvables - * allow_all: 0 = dont allow downgrades, 1 = allow all candidates - */ - -static void -addrpmrulesforupdaters(Solver *solv, Solvable *s, Map *m, int allow_all) -{ - Pool *pool = solv->pool; - int i; - /* queue and buffer for it */ - Queue qs; - Id qsbuf[64]; - - POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforupdaters -----\n"); - - queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf)); - /* find update candidates for 's' */ - policy_findupdatepackages(solv, s, &qs, allow_all); - /* add rule for 's' if not already done */ - if (!MAPTST(m, s - pool->solvables)) - addrpmrulesforsolvable(solv, s, m); - /* foreach update candidate, add rule if not already done */ - 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"); -} - -static Id -finddistupgradepackages(Solver *solv, Solvable *s, Queue *qs, int allow_all) -{ - Pool *pool = solv->pool; - int i; - - policy_findupdatepackages(solv, s, qs, allow_all); - if (!qs->count) - { - if (allow_all) - return 0; - policy_findupdatepackages(solv, s, qs, 1); - if (!qs->count) - return 0; - qs->count = 0; - return -SYSTEMSOLVABLE; - } - if (allow_all) - return s - pool->solvables; - /* check if it is ok to keep the installed package */ - for (i = 0; i < qs->count; i++) - { - Solvable *ns = pool->solvables + qs->elements[i]; - if (s->evr == ns->evr && solvable_identical(pool, s, ns)) - return s - pool->solvables; - } - /* nope, it must be some other package */ - return queue_shift(qs); -} + Solvable *s = solv->pool->solvables + vv; + if (v < 0) + POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "conflicting %s (weak assertion)\n", pool_solvable2str(solv->pool, s)); + else + POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "installing %s (weak assertion)\n", pool_solvable2str(solv->pool, s)); + } + continue; + } + /* check against previous decision: is there a conflict? */ + if (v > 0 && solv->decisionmap[vv] > 0) + continue; + if (v < 0 && solv->decisionmap[vv] < 0) + continue; -/*------------------------------------------------------------------- - * - * add rule for update - * (A|A1|A2|A3...) An = update candidates for A - * - * s = (installed) solvable - */ + POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "assertion conflict, but I am weak, disabling "); + solver_printrule(solv, SOLV_DEBUG_UNSOLVABLE, r); -static void -addupdaterule(Solver *solv, Solvable *s, int allow_all) -{ - /* installed packages get a special upgrade allowed rule */ - Pool *pool = solv->pool; - Id p, d; - Queue qs; - Id qsbuf[64]; - - POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addupdaterule -----\n"); - queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf)); - p = s - pool->solvables; - /* find update candidates for 's' */ - if (solv->distupgrade) - p = finddistupgradepackages(solv, s, &qs, allow_all); - else - policy_findupdatepackages(solv, s, &qs, allow_all); - d = qs.count ? pool_queuetowhatprovides(pool, &qs) : 0; - queue_free(&qs); - addrule(solv, p, d); /* allow update of s */ - POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addupdaterule end -----\n"); + 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); + havedisabled = 1; + break; /* start over */ + } + if (ii == solv->ruleassertions.count) + break; /* finished! */ + } } @@ -1540,15 +568,10 @@ makewatches(Solver *solv) 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?) */ + solv_free(solv->watches); + /* lower half for removals, upper half for installs */ + solv->watches = solv_calloc(2 * nsolvables, sizeof(Id)); 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->w2) /* assertions do not need watches */ continue; @@ -1565,10 +588,10 @@ makewatches(Solver *solv) /*------------------------------------------------------------------- * - * add watches (for rule) + * add watches (for a new learned rule) * sets up watches for a single rule - * - * see also makewatches() + * + * see also makewatches() above. */ static inline void @@ -1598,17 +621,14 @@ addwatches_rule(Solver *solv, Rule *r) #define DECISIONMAP_UNDEF(p) (decisionmap[(p) > 0 ? (p) : -(p)] == 0) /*------------------------------------------------------------------- - * + * * propagate * * 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. - * + * + * Evaluate each term affected by the decision (linked through watches). + * If we find unit rules we make new decisions based on them. + * * return : 0 = everything is OK * rule = conflict found in this rule */ @@ -1622,24 +642,23 @@ propagate(Solver *solv, int level) Id p, pkg, other_watch; Id *dp; Id *decisionmap = solv->decisionmap; - Id *watches = solv->watches + pool->nsolvables; /* place ptr in middle */ - POOL_DEBUG(SAT_DEBUG_PROPAGATE, "----- propagate -----\n"); + POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "----- propagate -----\n"); /* foreach non-propagated decision */ while (solv->propagate_index < solv->decisionq.count) { - /* - * 'pkg' was just decided - * 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) + IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE) { - POOL_DEBUG(SAT_DEBUG_PROPAGATE, "propagate for decision %d level %d\n", -pkg, level); - solver_printruleelement(solv, SAT_DEBUG_PROPAGATE, 0, -pkg); + POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "propagate for decision %d level %d\n", -pkg, level); + solver_printruleelement(solv, SOLV_DEBUG_PROPAGATE, 0, -pkg); } /* foreach rule where 'pkg' is now FALSE */ @@ -1656,17 +675,17 @@ propagate(Solver *solv, int level) continue; } - IF_POOLDEBUG (SAT_DEBUG_PROPAGATE) + IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE) { - POOL_DEBUG(SAT_DEBUG_PROPAGATE," watch triggered "); - solver_printrule(solv, SAT_DEBUG_PROPAGATE, r); + POOL_DEBUG(SOLV_DEBUG_PROPAGATE," watch triggered "); + solver_printrule(solv, SOLV_DEBUG_PROPAGATE, r); } - /* 'pkg' was just decided (was set to FALSE) - * - * now find other literal watch, check clause - * and advance on linked list - */ + /* + * 'pkg' was just decided (was set to FALSE), so this rule + * may now be unit. + */ + /* find the other watch */ if (pkg == r->w1) { other_watch = r->w2; @@ -1677,28 +696,29 @@ propagate(Solver *solv, int level) other_watch = r->w1; next_rp = &r->n2; } - - /* - * This term is already true (through the other literal) - * so we have nothing to do - */ + + /* + * if the other watch is true we have nothing to do + */ if (DECISIONMAP_TRUE(other_watch)) continue; - /* - * The other literal is FALSE or UNDEF - * - */ - + /* + * The other literal is FALSE or UNDEF + * + */ + if (r->d) { /* 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) + * As speed matters here we do not use the FOR_RULELITERALS + * macro. */ if (r->p /* we have a 'p' */ && r->p != other_watch /* which is not watched */ @@ -1725,17 +745,17 @@ propagate(Solver *solv, int level) * if we found some p that is UNDEF or TRUE, move * watch to it */ - IF_POOLDEBUG (SAT_DEBUG_PROPAGATE) + IF_POOLDEBUG (SOLV_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(SOLV_DEBUG_PROPAGATE, " -> move w%d to %s\n", (pkg == r->w1 ? 1 : 2), pool_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(SOLV_DEBUG_PROPAGATE, " -> move w%d to !%s\n", (pkg == r->w1 ? 1 : 2), pool_solvid2str(pool, -p)); } - + *rp = *next_rp; next_rp = rp; - + if (pkg == r->w1) { r->w1 = p; @@ -1752,42 +772,41 @@ propagate(Solver *solv, int level) /* search failed, thus all unwatched literals are FALSE */ } /* not binary */ - - /* - * unit clause found, set literal other_watch to TRUE - */ + + /* + * 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) + + IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE) { - POOL_DEBUG(SAT_DEBUG_PROPAGATE, " unit "); - solver_printrule(solv, SAT_DEBUG_PROPAGATE, r); + POOL_DEBUG(SOLV_DEBUG_PROPAGATE, " unit "); + solver_printrule(solv, SOLV_DEBUG_PROPAGATE, r); } if (other_watch > 0) decisionmap[other_watch] = level; /* install! */ else decisionmap[-other_watch] = -level; /* remove! */ - + queue_push(&solv->decisionq, other_watch); queue_push(&solv->decisionq_why, r - solv->rules); - IF_POOLDEBUG (SAT_DEBUG_PROPAGATE) + IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE) { - Solvable *s = pool->solvables + (other_watch > 0 ? other_watch : -other_watch); if (other_watch > 0) - POOL_DEBUG(SAT_DEBUG_PROPAGATE, " -> decided to install %s\n", solvable2str(pool, s)); + POOL_DEBUG(SOLV_DEBUG_PROPAGATE, " -> decided to install %s\n", pool_solvid2str(pool, other_watch)); else - POOL_DEBUG(SAT_DEBUG_PROPAGATE, " -> decided to conflict %s\n", solvable2str(pool, s)); + POOL_DEBUG(SOLV_DEBUG_PROPAGATE, " -> decided to conflict %s\n", pool_solvid2str(pool, -other_watch)); } - + } /* foreach rule involving 'pkg' */ } /* while we have non-decided decisions */ - - POOL_DEBUG(SAT_DEBUG_PROPAGATE, "----- propagate end-----\n"); + + POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "----- propagate end-----\n"); return 0; /* all is well */ } @@ -1797,71 +816,134 @@ propagate(Solver *solv, int level) /* Analysis */ /*------------------------------------------------------------------- - * + * + * revert + * revert decisionq to a level + */ + +static void +revert(Solver *solv, int level) +{ + Pool *pool = solv->pool; + Id v, vv; + while (solv->decisionq.count) + { + v = solv->decisionq.elements[solv->decisionq.count - 1]; + vv = v > 0 ? v : -v; + if (solv->decisionmap[vv] <= level && solv->decisionmap[vv] >= -level) + break; + POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "reverting decision %d at %d\n", v, solv->decisionmap[vv]); + solv->decisionmap[vv] = 0; + solv->decisionq.count--; + solv->decisionq_why.count--; + solv->propagate_index = solv->decisionq.count; + } + while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] >= level) + solv->branches.count -= solv->branches.elements[solv->branches.count - 2]; + if (solv->recommends_index > solv->decisionq.count) + solv->recommends_index = -1; /* rebuild recommends/suggests maps */ + if (solv->decisionq.count < solv->decisioncnt_jobs) + solv->decisioncnt_jobs = 0; + if (solv->decisionq.count < solv->decisioncnt_update) + solv->decisioncnt_update = 0; + if (solv->decisionq.count < solv->decisioncnt_keep) + solv->decisioncnt_keep = 0; + if (solv->decisionq.count < solv->decisioncnt_resolve) + solv->decisioncnt_resolve = 0; + if (solv->decisionq.count < solv->decisioncnt_weak) + solv->decisioncnt_weak= 0; + if (solv->decisionq.count < solv->decisioncnt_orphan) + solv->decisioncnt_orphan = 0; +} + +/*------------------------------------------------------------------- + * + * watch2onhighest - put watch2 on literal with highest level + */ + +static inline void +watch2onhighest(Solver *solv, Rule *r) +{ + int l, wl = 0; + Id d, v, *dp; + + d = r->d < 0 ? -r->d - 1 : r->d; + if (!d) + return; /* binary rule, both watches are set */ + dp = solv->pool->whatprovidesdata + d; + while ((v = *dp++) != 0) + { + l = solv->decisionmap[v < 0 ? -v : v]; + if (l < 0) + l = -l; + if (l > wl) + { + r->w2 = dp[-1]; + wl = l; + } + } +} + + +/*------------------------------------------------------------------- + * * analyze * and learn */ static int -analyze(Solver *solv, int level, Rule *c, int *pr, int *dr, int *whyp) +analyze(Solver *solv, int level, Rule *c, Rule **lrp) { Pool *pool = solv->pool; - Queue r; + Queue q; + Rule *r; + Id q_buf[8]; int rlevel = 1; Map seen; /* global? */ - Id d, v, vv, *dp, why; + Id p = 0, pp, v, vv, why; int l, i, idx; int num = 0, l1num = 0; int learnt_why = solv->learnt_pool.count; Id *decisionmap = solv->decisionmap; - queue_init(&r); + queue_init_buffer(&q, q_buf, sizeof(q_buf)/sizeof(*q_buf)); - POOL_DEBUG(SAT_DEBUG_ANALYZE, "ANALYZE at %d ----------------------\n", level); + POOL_DEBUG(SOLV_DEBUG_ANALYZE, "ANALYZE at %d ----------------------\n", level); map_init(&seen, pool->nsolvables); idx = solv->decisionq.count; for (;;) { - IF_POOLDEBUG (SAT_DEBUG_ANALYZE) - solver_printruleclass(solv, SAT_DEBUG_ANALYZE, c); + IF_POOLDEBUG (SOLV_DEBUG_ANALYZE) + solver_printruleclass(solv, SOLV_DEBUG_ANALYZE, c); queue_push(&solv->learnt_pool, c - solv->rules); - 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++) + FOR_RULELITERALS(v, pp, c) { - if (i == -1) - v = c->p; - else if (d == 0) - v = i ? 0 : c->w2; - else - v = *dp++; - if (v == 0) - break; - if (DECISIONMAP_TRUE(v)) /* the one true literal */ continue; vv = v > 0 ? v : -v; if (MAPTST(&seen, vv)) continue; + MAPSET(&seen, vv); /* mark that we also need to look at this literal */ l = solv->decisionmap[vv]; if (l < 0) l = -l; - MAPSET(&seen, vv); if (l == 1) l1num++; /* need to do this one in level1 pass */ else if (l == level) num++; /* need to do this one as well */ else { - queue_push(&r, v); /* not level1 or conflict level, add to new rule */ + queue_push(&q, v); /* not level1 or conflict level, add to new rule */ if (l > rlevel) rlevel = l; } } l1retry: if (!num && !--l1num) - break; /* all level 1 literals done */ + break; /* all literals done */ + + /* find the next literal to investigate */ + /* (as num + l1num > 0, we know that we'll always find one) */ for (;;) { assert(idx > 0); @@ -1871,118 +953,158 @@ l1retry: break; } MAPCLR(&seen, vv); + if (num && --num == 0) { - *pr = -v; /* so that v doesn't get lost */ + /* done with normal literals, now start level 1 literal processing */ + p = -v; /* so that v doesn't get lost */ if (!l1num) break; - POOL_DEBUG(SAT_DEBUG_ANALYZE, "got %d involved level 1 decisions\n", l1num); - for (i = 0; i < r.count; i++) + POOL_DEBUG(SOLV_DEBUG_ANALYZE, "got %d involved level 1 decisions\n", l1num); + /* clear non-l1 bits from seen map */ + for (i = 0; i < q.count; i++) { - v = r.elements[i]; + v = q.elements[i]; MAPCLR(&seen, v > 0 ? v : -v); } - /* only level 1 marks left */ - l1num++; + /* only level 1 marks left in seen map */ + l1num++; /* as l1retry decrements it */ goto l1retry; } + why = solv->decisionq_why.elements[idx]; - if (!why) /* just in case, maybe for SYSTEMSOLVABLE */ + if (why <= 0) /* just in case, maybe for SYSTEMSOLVABLE */ goto l1retry; c = solv->rules + why; } map_free(&seen); - - if (r.count == 0) - *dr = 0; - else if (r.count == 1 && r.elements[0] < 0) - *dr = r.elements[0]; - else - *dr = pool_queuetowhatprovides(pool, &r); - IF_POOLDEBUG (SAT_DEBUG_ANALYZE) + assert(p != 0); + assert(rlevel > 0 && rlevel < level); + IF_POOLDEBUG (SOLV_DEBUG_ANALYZE) { - POOL_DEBUG(SAT_DEBUG_ANALYZE, "learned rule for level %d (am %d)\n", rlevel, level); - solver_printruleelement(solv, SAT_DEBUG_ANALYZE, 0, *pr); - for (i = 0; i < r.count; i++) - solver_printruleelement(solv, SAT_DEBUG_ANALYZE, 0, r.elements[i]); + POOL_DEBUG(SOLV_DEBUG_ANALYZE, "learned rule for level %d (am %d)\n", rlevel, level); + solver_printruleelement(solv, SOLV_DEBUG_ANALYZE, 0, p); + for (i = 0; i < q.count; i++) + solver_printruleelement(solv, SOLV_DEBUG_ANALYZE, 0, q.elements[i]); } /* push end marker on learnt reasons stack */ queue_push(&solv->learnt_pool, 0); - if (whyp) - *whyp = learnt_why; solv->stats_learned++; - return rlevel; + + POOL_DEBUG(SOLV_DEBUG_ANALYZE, "reverting decisions (level %d -> %d)\n", level, rlevel); + level = rlevel; + revert(solv, level); + if (q.count < 2) + { + Id d = q.count ? q.elements[0] : 0; + queue_free(&q); + r = solver_addrule(solv, p, d, 0); + } + else + { + Id d = pool_queuetowhatprovides(pool, &q); + queue_free(&q); + r = solver_addrule(solv, p, 0, d); + } + assert(solv->learnt_why.count == (r - solv->rules) - solv->learntrules); + queue_push(&solv->learnt_why, learnt_why); + if (r->w2) + { + /* needs watches */ + watch2onhighest(solv, r); + addwatches_rule(solv, r); + } + else + { + /* rule is an assertion */ + queue_push(&solv->ruleassertions, r - solv->rules); + } + *lrp = r; + return level; } /*------------------------------------------------------------------- - * - * reset_solver - * - * reset the solver decisions to right after the rpm rules. + * + * solver_reset + * + * reset all solver decisions * 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; + queue_empty(&solv->decisionq_why); + queue_empty(&solv->decisionq); solv->recommends_index = -1; solv->propagate_index = 0; + solv->decisioncnt_update = solv->decisioncnt_keep = solv->decisioncnt_resolve = solv->decisioncnt_weak = solv->decisioncnt_orphan = 0; + queue_empty(&solv->branches); /* adapt learnt rule status to new set of enabled/disabled rules */ enabledisablelearntrules(solv); - - /* redo all job/update decisions */ - makeruledecisions(solv); - POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "decisions so far: %d\n", solv->decisionq.count); } /*------------------------------------------------------------------- - * + * * analyze_unsolvable_rule + * + * recursion helper used by analyze_unsolvable */ static void -analyze_unsolvable_rule(Solver *solv, Rule *r, Id *lastweakp) +analyze_unsolvable_rule(Solver *solv, Rule *r, Id *lastweakp, Map *rseen) { Pool *pool = solv->pool; int i; Id why = r - solv->rules; - IF_POOLDEBUG (SAT_DEBUG_UNSOLVABLE) - solver_printruleclass(solv, SAT_DEBUG_UNSOLVABLE, r); + IF_POOLDEBUG (SOLV_DEBUG_UNSOLVABLE) + solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE, r); if (solv->learntrules && why >= solv->learntrules) { + if (MAPTST(rseen, why - solv->learntrules)) + return; + MAPSET(rseen, why - solv->learntrules); for (i = solv->learnt_why.elements[why - solv->learntrules]; solv->learnt_pool.elements[i]; i++) if (solv->learnt_pool.elements[i] > 0) - analyze_unsolvable_rule(solv, solv->rules + solv->learnt_pool.elements[i], lastweakp); + analyze_unsolvable_rule(solv, solv->rules + solv->learnt_pool.elements[i], lastweakp, rseen); return; } - if (MAPTST(&solv->weakrulemap, why)) + if (solv->weakrulemap.size && MAPTST(&solv->weakrulemap, why)) if (!*lastweakp || why > *lastweakp) *lastweakp = why; - /* do not add rpm rules to problem */ - if (why < solv->rpmrules_end) + /* do not add pkg rules to problem */ + if (why < solv->pkgrules_end) return; /* turn rule into problem */ 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) { @@ -1997,11 +1119,23 @@ analyze_unsolvable_rule(Solver *solv, Rule *r, Id *lastweakp) /*------------------------------------------------------------------- - * - * analyze_unsolvable * - * return: 1 - disabled some rules, try again - * 0 - hopeless + * analyze_unsolvable (called from setpropagatelearn) + * + * We know that the problem is not solvable. Record all involved + * rules (i.e. the "proof") into solv->learnt_pool. + * Record the learnt pool index and all non-pkg rules into + * solv->problems. (Our solutions to fix the problems are to + * disable those rules.) + * + * If the proof contains at least one weak rule, we disable the + * last of them. + * + * Otherwise we return -1 if disablerules is not set or disable + * _all_ of the problem rules and return 0. + * + * return: 0 - disabled some rules, try again + * -1 - hopeless */ static int @@ -2009,15 +1143,17 @@ analyze_unsolvable(Solver *solv, Rule *cr, int disablerules) { Pool *pool = solv->pool; Rule *r; - Map seen; /* global to speed things up? */ - Id d, v, vv, *dp, why; - int l, i, idx; + Map involved; /* global to speed things up? */ + Map rseen; + Id pp, v, vv, why; + int i, idx; Id *decisionmap = solv->decisionmap; int oldproblemcount; int oldlearntpoolcount; Id lastweak; + int record_proof = 1; - POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "ANALYZE UNSOLVABLE ----------------------\n"); + POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "ANALYZE UNSOLVABLE ----------------------\n"); solv->stats_unsolvable++; oldproblemcount = solv->problems.count; oldlearntpoolcount = solv->learnt_pool.count; @@ -2028,63 +1164,42 @@ analyze_unsolvable(Solver *solv, Rule *cr, int disablerules) queue_push(&solv->problems, 0); r = cr; - map_init(&seen, pool->nsolvables); - queue_push(&solv->learnt_pool, r - solv->rules); + map_init(&involved, pool->nsolvables); + map_init(&rseen, solv->learntrules ? solv->nrules - solv->learntrules : 0); + if (record_proof) + queue_push(&solv->learnt_pool, r - solv->rules); lastweak = 0; - analyze_unsolvable_rule(solv, r, &lastweak); - d = r->d < 0 ? -r->d - 1 : r->d; - dp = d ? pool->whatprovidesdata + d : 0; - for (i = -1; ; i++) + analyze_unsolvable_rule(solv, r, &lastweak, &rseen); + FOR_RULELITERALS(v, pp, r) { - if (i == -1) - v = r->p; - else if (d == 0) - v = i ? 0 : r->w2; - else - v = *dp++; - if (v == 0) - break; if (DECISIONMAP_TRUE(v)) /* the one true literal */ continue; vv = v > 0 ? v : -v; - l = solv->decisionmap[vv]; - if (l < 0) - l = -l; - MAPSET(&seen, vv); + MAPSET(&involved, vv); } idx = solv->decisionq.count; while (idx > 0) { v = solv->decisionq.elements[--idx]; vv = v > 0 ? v : -v; - if (!MAPTST(&seen, vv)) + if (!MAPTST(&involved, vv) || vv == SYSTEMSOLVABLE) continue; why = solv->decisionq_why.elements[idx]; - queue_push(&solv->learnt_pool, why); + assert(why > 0); + if (record_proof) + queue_push(&solv->learnt_pool, why); r = solv->rules + why; - analyze_unsolvable_rule(solv, r, &lastweak); - d = r->d < 0 ? -r->d - 1 : r->d; - dp = d ? pool->whatprovidesdata + d : 0; - for (i = -1; ; i++) + analyze_unsolvable_rule(solv, r, &lastweak, &rseen); + FOR_RULELITERALS(v, pp, r) { - if (i == -1) - v = r->p; - else if (d == 0) - v = i ? 0 : r->w2; - else - v = *dp++; - if (v == 0) - break; if (DECISIONMAP_TRUE(v)) /* the one true literal */ continue; vv = v > 0 ? v : -v; - l = solv->decisionmap[vv]; - if (l < 0) - l = -l; - MAPSET(&seen, vv); + MAPSET(&involved, vv); } } - map_free(&seen); + map_free(&involved); + map_free(&rseen); queue_push(&solv->problems, 0); /* mark end of this problem */ if (lastweak) @@ -2092,100 +1207,52 @@ analyze_unsolvable(Solver *solv, Rule *cr, int disablerules) /* disable last weak rule */ solv->problems.count = oldproblemcount; solv->learnt_pool.count = oldlearntpoolcount; - r = solv->rules + lastweak; - POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "disabling "); - solver_printruleclass(solv, SAT_DEBUG_UNSOLVABLE, r); - disablerule(solv, r); - reset_solver(solv); - return 1; + if (lastweak >= solv->jobrules && lastweak < solv->jobrules_end) + v = -(solv->ruletojob.elements[lastweak - solv->jobrules] + 1); + else + v = lastweak; + POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "disabling "); + solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE, solv->rules + lastweak); + if (lastweak >= solv->choicerules && lastweak < solv->choicerules_end) + solver_disablechoicerules(solv, solv->rules + lastweak); + solver_disableproblem(solv, v); + if (v < 0) + solver_reenablepolicyrules(solv, -v); + solver_reset(solv); + return 0; } - /* finish proof */ - queue_push(&solv->learnt_pool, 0); - solv->problems.elements[oldproblemcount] = oldlearntpoolcount; - - if (disablerules) + if (solv->allowuninstall && (v = autouninstall(solv, solv->problems.elements + oldproblemcount + 1)) != 0) { - for (i = oldproblemcount + 1; i < solv->problems.count - 1; i++) - disableproblem(solv, solv->problems.elements[i]); - /* XXX: might want to enable all weak rules again */ - reset_solver(solv); - return 1; + solv->problems.count = oldproblemcount; + solv->learnt_pool.count = oldlearntpoolcount; + solver_reset(solv); + return 0; } - POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "UNSOLVABLE\n"); - return 0; -} - - -/********************************************************************/ -/* Decision revert */ - -/*------------------------------------------------------------------- - * - * revert - * revert decision at level - */ -static void -revert(Solver *solv, int level) -{ - Pool *pool = solv->pool; - Id v, vv; - while (solv->decisionq.count) - { - v = solv->decisionq.elements[solv->decisionq.count - 1]; - vv = v > 0 ? v : -v; - if (solv->decisionmap[vv] <= level && solv->decisionmap[vv] >= -level) - break; - POOL_DEBUG(SAT_DEBUG_PROPAGATE, "reverting decision %d at %d\n", v, solv->decisionmap[vv]); - if (v > 0 && solv->recommendations.count && v == solv->recommendations.elements[solv->recommendations.count - 1]) - solv->recommendations.count--; - solv->decisionmap[vv] = 0; - solv->decisionq.count--; - solv->decisionq_why.count--; - solv->propagate_index = solv->decisionq.count; - } - while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] <= -level) + /* finish proof */ + if (record_proof) { - solv->branches.count--; - while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] >= 0) - solv->branches.count--; + queue_push(&solv->learnt_pool, 0); + solv->problems.elements[oldproblemcount] = oldlearntpoolcount; } - solv->recommends_index = -1; -} - - -/*------------------------------------------------------------------- - * - * watch2onhighest - put watch2 on literal with highest level - */ - -static inline void -watch2onhighest(Solver *solv, Rule *r) -{ - int l, wl = 0; - Id d, v, *dp; - d = r->d < 0 ? -r->d - 1 : r->d; - if (!d) - return; /* binary rule, both watches are set */ - dp = solv->pool->whatprovidesdata + d; - while ((v = *dp++) != 0) + /* + 2: index + trailing zero */ + if (disablerules && oldproblemcount + 2 < solv->problems.count) { - l = solv->decisionmap[v < 0 ? -v : v]; - if (l < 0) - l = -l; - if (l > wl) - { - r->w2 = dp[-1]; - wl = l; - } + for (i = oldproblemcount + 1; i < solv->problems.count - 1; i++) + solver_disableproblem(solv, solv->problems.elements[i]); + /* XXX: might want to enable all weak rules again */ + solver_reset(solv); + return 0; } + POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "UNSOLVABLE\n"); + return -1; } /*------------------------------------------------------------------- - * + * * setpropagatelearn * * add free decision (solvable to install) to decisionq @@ -2196,17 +1263,15 @@ watch2onhighest(Solver *solv, Rule *r) * rule to learnt rule set, make decision from learnt * rule (always unit) and re-propagate. * - * returns the new solver level or 0 if unsolvable + * returns the new solver level or -1 if unsolvable * */ 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; + Rule *r, *lr; if (decision) { @@ -2216,8 +1281,9 @@ 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 */ } + assert(ruleid >= 0 && level > 0); for (;;) { r = propagate(solv, level); @@ -2225,94 +1291,163 @@ setpropagatelearn(Solver *solv, int level, Id decision, int disablerules) break; if (level == 1) return analyze_unsolvable(solv, r, disablerules); - POOL_DEBUG(SAT_DEBUG_ANALYZE, "conflict with rule #%d\n", (int)(r - solv->rules)); - l = analyze(solv, level, r, &p, &d, &why); /* learnt rule in p and d */ - assert(l > 0 && l < level); - 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 */ - assert(r); - assert(solv->learnt_why.count == (r - solv->rules) - solv->learntrules); - queue_push(&solv->learnt_why, why); - if (d) - { - /* at least 2 literals, needs watches */ - watch2onhighest(solv, r); - addwatches_rule(solv, r); - } - else + POOL_DEBUG(SOLV_DEBUG_ANALYZE, "conflict with rule #%d\n", (int)(r - solv->rules)); + level = analyze(solv, level, r, &lr); + /* the new rule is unit by design */ + decision = lr->p; + solv->decisionmap[decision > 0 ? decision : -decision] = decision > 0 ? level : -level; + queue_push(&solv->decisionq, decision); + queue_push(&solv->decisionq_why, lr - solv->rules); + IF_POOLDEBUG (SOLV_DEBUG_ANALYZE) { - /* learnt rule is an assertion */ - queue_push(&solv->ruleassertions, r - solv->rules); + POOL_DEBUG(SOLV_DEBUG_ANALYZE, "decision: "); + solver_printruleelement(solv, SOLV_DEBUG_ANALYZE, 0, decision); + POOL_DEBUG(SOLV_DEBUG_ANALYZE, "new rule: "); + solver_printrule(solv, SOLV_DEBUG_ANALYZE, lr); } - solv->decisionmap[p > 0 ? p : -p] = p > 0 ? level : -level; - queue_push(&solv->decisionq, p); - queue_push(&solv->decisionq_why, r - solv->rules); - IF_POOLDEBUG (SAT_DEBUG_ANALYZE) + } + return level; +} + +static void +reorder_dq_for_jobrules(Solver *solv, int level, Queue *dq) +{ + Pool *pool = solv->pool; + int i, j, haveone = 0, dqcount = dq->count; + int decisionqcount = solv->decisionq.count; + Id p; + Solvable *s; + + /* at the time we process jobrules the installed packages are not kept yet */ + /* reorder so that "future-supplemented" packages come first */ + FOR_REPO_SOLVABLES(solv->installed, p, s) + { + if (MAPTST(&solv->noupdate, p - solv->installed->start)) + continue; + if (solv->decisionmap[p] == 0) { - POOL_DEBUG(SAT_DEBUG_ANALYZE, "decision: "); - solver_printruleelement(solv, SAT_DEBUG_ANALYZE, 0, p); - POOL_DEBUG(SAT_DEBUG_ANALYZE, "new rule: "); - solver_printrule(solv, SAT_DEBUG_ANALYZE, r); + if (s->recommends || s->suggests) + queue_push(&solv->decisionq, p); + solv->decisionmap[p] = level + 1; + haveone = 1; } } - return level; + if (!haveone) + return; + policy_update_recommendsmap(solv); + for (i = 0; i < dqcount; i++) + { + p = dq->elements[i]; + if (!(pool->solvables[p].repo == solv->installed || MAPTST(&solv->suggestsmap, p) || solver_is_enhancing(solv, pool->solvables + p))) + { + queue_push(dq, p); + dq->elements[i] = 0; + } + } + dqcount = dq->count; + for (i = 0; i < dqcount; i++) + { + p = dq->elements[i]; + if (p && !(pool->solvables[p].repo == solv->installed || MAPTST(&solv->recommendsmap, p) || solver_is_supplementing(solv, pool->solvables + p))) + { + queue_push(dq, p); + dq->elements[i] = 0; + } + } + for (i = j = 0; i < dq->count; i++) + if (dq->elements[i]) + dq->elements[j++] = dq->elements[i]; + queue_truncate(dq, j); + FOR_REPO_SOLVABLES(solv->installed, p, s) + if (solv->decisionmap[p] == level + 1) + solv->decisionmap[p] = 0; + if (solv->decisionq.count != decisionqcount) + { + solv->recommends_index = -1; + queue_truncate(&solv->decisionq, decisionqcount); + } +} + +/*------------------------------------------------------------------- + * + * branch handling + */ + +static void +createbranch(Solver *solv, int level, Queue *dq, Id p, Id data) +{ + Pool *pool = solv->pool; + int i; + IF_POOLDEBUG (SOLV_DEBUG_POLICY) + { + POOL_DEBUG (SOLV_DEBUG_POLICY, "creating a branch:\n"); + for (i = 0; i < dq->count; i++) + POOL_DEBUG (SOLV_DEBUG_POLICY, " - %s\n", pool_solvid2str(pool, dq->elements[i])); + } + queue_push(&solv->branches, -dq->elements[0]); + for (i = 1; i < dq->count; i++) + queue_push(&solv->branches, dq->elements[i]); + queue_push2(&solv->branches, p, data); + queue_push2(&solv->branches, dq->count + 4, level); } +static int +takebranch(Solver *solv, int pos, int end, const char *msg, int disablerules) +{ + Pool *pool = solv->pool; + int level; + Id p, why; +#if 0 + { + int i; + printf("branch group level %d [%d-%d] %d %d:\n", solv->branches.elements[end - 1], start, end, solv->branches.elements[end - 4], solv->branches.elements[end - 3]); + for (i = end - solv->branches.elements[end - 2]; i < end - 4; i++) + printf("%c %c%s\n", i == pos ? 'x' : ' ', solv->branches.elements[i] >= 0 ? ' ' : '-', pool_solvid2str(pool, solv->branches.elements[i] >= 0 ? solv->branches.elements[i] : -solv->branches.elements[i])); + } +#endif + level = solv->branches.elements[end - 1]; + p = solv->branches.elements[pos]; + solv->branches.elements[pos] = -p; + POOL_DEBUG(SOLV_DEBUG_SOLVER, "%s %d -> %d with %s\n", msg, solv->decisionmap[p], level, pool_solvid2str(pool, p)); + /* hack: set level to zero so that revert does not remove the branch */ + solv->branches.elements[end - 1] = 0; + revert(solv, level); + solv->branches.elements[end - 1] = level; + /* hack: revert simply sets the count, so we can still access the reverted elements */ + why = -solv->decisionq_why.elements[solv->decisionq_why.count]; + assert(why >= 0); + return setpropagatelearn(solv, level, p, disablerules, why); +} /*------------------------------------------------------------------- - * + * * 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 + * returns the new solver level or -1 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; - - /* FIXME: do we really need that inst handling? */ - if (solv->distupgrade && inst && dq->count) - { - policy_filter_unwanted(solv, dq, 0, POLICY_MODE_CHOOSE); - for (i = 0; i < dq->count; i++) - if (solvable_identical(pool, pool->solvables + inst, pool->solvables + dq->elements[i])) - dq->elements[i] = inst; - } - else - { - if (dq->count > 1 || inst) - policy_filter_unwanted(solv, dq, inst, POLICY_MODE_CHOOSE); - } - i = 0; if (dq->count > 1) - { - /* 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; - } - } - p = dq->elements[i]; - - POOL_DEBUG(SAT_DEBUG_POLICY, "installing %s\n", solvable2str(pool, pool->solvables + p)); - - return setpropagatelearn(solv, level, p, disablerules); + policy_filter_unwanted(solv, dq, POLICY_MODE_CHOOSE); + /* if we're resolving job rules and didn't resolve the installed packages yet, + * do some special supplements ordering */ + if (dq->count > 1 && ruleid >= solv->jobrules && ruleid < solv->jobrules_end && solv->installed && !solv->focus_installed) + reorder_dq_for_jobrules(solv, level, dq); + /* if we have multiple candidates we open a branch */ + if (dq->count > 1) + createbranch(solv, level, dq, 0, ruleid); + p = dq->elements[0]; + POOL_DEBUG(SOLV_DEBUG_POLICY, "installing %s\n", pool_solvid2str(pool, p)); + return setpropagatelearn(solv, level, p, disablerules, ruleid); } @@ -2321,7 +1456,7 @@ selectandinstall(Solver *solv, int level, Queue *dq, Id inst, int disablerules) /*------------------------------------------------------------------- - * + * * solver_create * create solver structure * @@ -2337,85 +1472,540 @@ Solver * solver_create(Pool *pool) { Solver *solv; - solv = (Solver *)sat_calloc(1, sizeof(Solver)); + solv = (Solver *)solv_calloc(1, sizeof(Solver)); solv->pool = pool; solv->installed = pool->installed; + solv->allownamechange = 1; + + solv->dup_allowdowngrade = 1; + solv->dup_allownamechange = 1; + solv->dup_allowarchchange = 1; + solv->dup_allowvendorchange = 1; + + solv->keepexplicitobsoletes = pool->noobsoletesmultiversion ? 0 : 1; + 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); + queue_init(&solv->addedmap_deduceq); + + queue_push(&solv->learnt_pool, 0); /* so that 0 does not describe a proof */ map_init(&solv->recommendsmap, pool->nsolvables); map_init(&solv->suggestsmap, pool->nsolvables); 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)); + solv->decisionmap = (Id *)solv_calloc(pool->nsolvables, sizeof(Id)); solv->nrules = 1; - solv->rules = sat_extend_resize(solv->rules, solv->nrules, sizeof(Rule), RULES_BLOCK); + solv->rules = solv_extend_resize(solv->rules, solv->nrules, sizeof(Rule), RULES_BLOCK); memset(solv->rules, 0, sizeof(Rule)); return solv; } +static int +resolve_jobrules(Solver *solv, int level, int disablerules, Queue *dq) +{ + Pool *pool = solv->pool; + int oldlevel = level; + int i, olevel; + Rule *r; + + POOL_DEBUG(SOLV_DEBUG_SOLVER, "resolving job rules\n"); + if (!solv->decisioncnt_jobs) + solv->decisioncnt_jobs = solv->decisionq.count; + for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++) + { + Id l, pp; + if (r->d < 0) /* ignore disabled rules */ + continue; + queue_empty(dq); + FOR_RULELITERALS(l, pp, r) + { + if (l < 0) + { + if (solv->decisionmap[-l] <= 0) + break; + } + else + { + if (solv->decisionmap[l] > 0) + break; + if (solv->decisionmap[l] == 0) + queue_push(dq, l); + } + } + if (l || !dq->count) + continue; + /* prune to installed if not updating */ + if (dq->count > 1 && solv->installed && !solv->updatemap_all && + !(solv->job.elements[solv->ruletojob.elements[i - solv->jobrules]] & SOLVER_ORUPDATE)) + { + int j, k; + for (j = k = 0; j < dq->count; j++) + { + Solvable *s = pool->solvables + dq->elements[j]; + if (s->repo == solv->installed) + { + dq->elements[k++] = dq->elements[j]; + if (solv->updatemap.size && MAPTST(&solv->updatemap, dq->elements[j] - solv->installed->start)) + { + k = 0; /* package wants to be updated, do not prune */ + break; + } + } + } + if (k) + dq->count = k; + } + olevel = level; + level = selectandinstall(solv, level, dq, disablerules, i); + if (level <= olevel) + { + if (level == olevel) + { + i--; + r--; + continue; /* try something else */ + } + if (level < oldlevel) + return level; + /* redo from start of jobrules */ + i = solv->jobrules - 1; + r = solv->rules + i; + } + } + return level; +} + /*------------------------------------------------------------------- - * + * * solver_free */ +static inline void +queuep_free(Queue **qp) +{ + if (!*qp) + return; + queue_free(*qp); + *qp = solv_free(*qp); +} + +static inline void +map_zerosize(Map *m) +{ + if (m->size) + { + map_free(m); + map_init(m, 0); + } +} + void solver_free(Solver *solv) { + 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->suggestions); - queue_free(&solv->recommendations); + queue_free(&solv->solutions); queue_free(&solv->orphaned); queue_free(&solv->branches); - queue_free(&solv->covenantq); queue_free(&solv->weakruleq); queue_free(&solv->ruleassertions); + queue_free(&solv->addedmap_deduceq); + queuep_free(&solv->cleandeps_updatepkgs); + queuep_free(&solv->cleandeps_mistakes); + queuep_free(&solv->update_targets); + queuep_free(&solv->installsuppdepq); + queuep_free(&solv->recommendscplxq); + queuep_free(&solv->suggestscplxq); + queuep_free(&solv->brokenorphanrules); map_free(&solv->recommendsmap); map_free(&solv->suggestsmap); map_free(&solv->noupdate); map_free(&solv->weakrulemap); - map_free(&solv->noobsoletes); - - sat_free(solv->decisionmap); - sat_free(solv->rules); - sat_free(solv->watches); - sat_free(solv->obsoletes); - sat_free(solv->obsoletes_data); - sat_free(solv); + map_free(&solv->multiversion); + + map_free(&solv->updatemap); + map_free(&solv->bestupdatemap); + map_free(&solv->fixmap); + map_free(&solv->dupmap); + map_free(&solv->dupinvolvedmap); + map_free(&solv->droporphanedmap); + map_free(&solv->cleandepsmap); + + solv_free(solv->decisionmap); + solv_free(solv->rules); + solv_free(solv->watches); + solv_free(solv->obsoletes); + solv_free(solv->obsoletes_data); + solv_free(solv->specialupdaters); + solv_free(solv->choicerules_ref); + solv_free(solv->bestrules_pkg); + solv_free(solv->yumobsrules_info); + solv_free(solv->instbuddy); + solv_free(solv); +} + +int +solver_get_flag(Solver *solv, int flag) +{ + switch (flag) + { + case SOLVER_FLAG_ALLOW_DOWNGRADE: + return solv->allowdowngrade; + case SOLVER_FLAG_ALLOW_NAMECHANGE: + return solv->allownamechange; + case SOLVER_FLAG_ALLOW_ARCHCHANGE: + return solv->allowarchchange; + case SOLVER_FLAG_ALLOW_VENDORCHANGE: + return solv->allowvendorchange; + case SOLVER_FLAG_ALLOW_UNINSTALL: + return solv->allowuninstall; + case SOLVER_FLAG_NO_UPDATEPROVIDE: + return solv->noupdateprovide; + case SOLVER_FLAG_SPLITPROVIDES: + return solv->dosplitprovides; + case SOLVER_FLAG_IGNORE_RECOMMENDED: + return solv->dontinstallrecommended; + case SOLVER_FLAG_ADD_ALREADY_RECOMMENDED: + return solv->addalreadyrecommended; + case SOLVER_FLAG_NO_INFARCHCHECK: + return solv->noinfarchcheck; + case SOLVER_FLAG_KEEP_EXPLICIT_OBSOLETES: + return solv->keepexplicitobsoletes; + case SOLVER_FLAG_BEST_OBEY_POLICY: + return solv->bestobeypolicy; + case SOLVER_FLAG_NO_AUTOTARGET: + return solv->noautotarget; + case SOLVER_FLAG_DUP_ALLOW_DOWNGRADE: + return solv->dup_allowdowngrade; + case SOLVER_FLAG_DUP_ALLOW_NAMECHANGE: + return solv->dup_allownamechange; + case SOLVER_FLAG_DUP_ALLOW_ARCHCHANGE: + return solv->dup_allowarchchange; + case SOLVER_FLAG_DUP_ALLOW_VENDORCHANGE: + return solv->dup_allowvendorchange; + case SOLVER_FLAG_KEEP_ORPHANS: + return solv->keep_orphans; + case SOLVER_FLAG_BREAK_ORPHANS: + return solv->break_orphans; + case SOLVER_FLAG_FOCUS_INSTALLED: + return solv->focus_installed; + case SOLVER_FLAG_YUM_OBSOLETES: + return solv->do_yum_obsoletes; + case SOLVER_FLAG_NEED_UPDATEPROVIDE: + return solv->needupdateprovide; + default: + break; + } + return -1; +} + +int +solver_set_flag(Solver *solv, int flag, int value) +{ + int old = solver_get_flag(solv, flag); + switch (flag) + { + case SOLVER_FLAG_ALLOW_DOWNGRADE: + solv->allowdowngrade = value; + break; + case SOLVER_FLAG_ALLOW_NAMECHANGE: + solv->allownamechange = value; + break; + case SOLVER_FLAG_ALLOW_ARCHCHANGE: + solv->allowarchchange = value; + break; + case SOLVER_FLAG_ALLOW_VENDORCHANGE: + solv->allowvendorchange = value; + break; + case SOLVER_FLAG_ALLOW_UNINSTALL: + solv->allowuninstall = value; + break; + case SOLVER_FLAG_NO_UPDATEPROVIDE: + solv->noupdateprovide = value; + break; + case SOLVER_FLAG_SPLITPROVIDES: + solv->dosplitprovides = value; + break; + case SOLVER_FLAG_IGNORE_RECOMMENDED: + solv->dontinstallrecommended = value; + break; + case SOLVER_FLAG_ADD_ALREADY_RECOMMENDED: + solv->addalreadyrecommended = value; + break; + case SOLVER_FLAG_NO_INFARCHCHECK: + solv->noinfarchcheck = value; + break; + case SOLVER_FLAG_KEEP_EXPLICIT_OBSOLETES: + solv->keepexplicitobsoletes = value; + break; + case SOLVER_FLAG_BEST_OBEY_POLICY: + solv->bestobeypolicy = value; + break; + case SOLVER_FLAG_NO_AUTOTARGET: + solv->noautotarget = value; + break; + case SOLVER_FLAG_DUP_ALLOW_DOWNGRADE: + solv->dup_allowdowngrade = value; + break; + case SOLVER_FLAG_DUP_ALLOW_NAMECHANGE: + solv->dup_allownamechange = value; + break; + case SOLVER_FLAG_DUP_ALLOW_ARCHCHANGE: + solv->dup_allowarchchange = value; + break; + case SOLVER_FLAG_DUP_ALLOW_VENDORCHANGE: + solv->dup_allowvendorchange = value; + break; + case SOLVER_FLAG_KEEP_ORPHANS: + solv->keep_orphans = value; + break; + case SOLVER_FLAG_BREAK_ORPHANS: + solv->break_orphans = value; + break; + case SOLVER_FLAG_FOCUS_INSTALLED: + solv->focus_installed = value; + break; + case SOLVER_FLAG_YUM_OBSOLETES: + solv->do_yum_obsoletes = value; + break; + case SOLVER_FLAG_NEED_UPDATEPROVIDE: + solv->needupdateprovide = value; + break; + default: + break; + } + return old; +} + +static int +cleandeps_check_mistakes(Solver *solv) +{ + Pool *pool = solv->pool; + Rule *r; + Id p, pp; + int i; + int mademistake = 0; + + if (!solv->cleandepsmap.size) + return 0; + /* check for mistakes */ + for (i = solv->installed->start; i < solv->installed->end; i++) + { + if (!MAPTST(&solv->cleandepsmap, i - solv->installed->start)) + continue; + r = solv->rules + solv->featurerules + (i - solv->installed->start); + /* a mistake is when the featurerule is true but the updaterule is false */ + if (!r->p) + continue; + FOR_RULELITERALS(p, pp, r) + if (p > 0 && solv->decisionmap[p] > 0) + break; + if (!p) + continue; /* feature rule is not true */ + r = solv->rules + solv->updaterules + (i - solv->installed->start); + if (!r->p) + continue; + FOR_RULELITERALS(p, pp, r) + if (p > 0 && solv->decisionmap[p] > 0) + break; + if (p) + continue; /* update rule is true */ + POOL_DEBUG(SOLV_DEBUG_SOLVER, "cleandeps mistake: "); + solver_printruleclass(solv, SOLV_DEBUG_SOLVER, r); + POOL_DEBUG(SOLV_DEBUG_SOLVER, "feature rule: "); + solver_printruleclass(solv, SOLV_DEBUG_SOLVER, solv->rules + solv->featurerules + (i - solv->installed->start)); + if (!solv->cleandeps_mistakes) + { + solv->cleandeps_mistakes = solv_calloc(1, sizeof(Queue)); + queue_init(solv->cleandeps_mistakes); + } + queue_push(solv->cleandeps_mistakes, i); + MAPCLR(&solv->cleandepsmap, i - solv->installed->start); + solver_reenablepolicyrules_cleandeps(solv, i); + mademistake = 1; + } + return mademistake; +} + +static void +prune_to_update_targets(Solver *solv, Id *cp, Queue *q) +{ + int i, j; + Id p, *cp2; + for (i = j = 0; i < q->count; i++) + { + p = q->elements[i]; + for (cp2 = cp; *cp2; cp2++) + if (*cp2 == p) + { + q->elements[j++] = p; + break; + } + } + queue_truncate(q, j); +} + +#ifdef ENABLE_COMPLEX_DEPS + +static void +add_complex_recommends(Solver *solv, Id rec, Queue *dq, Map *dqmap) +{ + Pool *pool = solv->pool; + int oldcnt = dq->count; + int cutcnt, blkcnt; + Id p; + int i, j; + +#if 0 + printf("ADD_COMPLEX_RECOMMENDS %s\n", pool_dep2str(pool, rec)); +#endif + i = pool_normalize_complex_dep(pool, rec, dq, CPLXDEPS_EXPAND); + if (i == 0 || i == 1) + return; + cutcnt = dq->count; + for (i = oldcnt; i < cutcnt; i++) + { + blkcnt = dq->count; + for (; (p = dq->elements[i]) != 0; i++) + { + if (p < 0) + { + if (solv->decisionmap[-p] <= 0) + break; + continue; + } + if (solv->decisionmap[p] > 0) + { + queue_truncate(dq, blkcnt); + break; + } + if (dqmap) + { + if (!MAPTST(dqmap, p)) + continue; + } + else + { + if (solv->decisionmap[p] < 0) + continue; + if (solv->dupmap_all && solv->installed && pool->solvables[p].repo == solv->installed && (solv->droporphanedmap_all || (solv->droporphanedmap.size && MAPTST(&solv->droporphanedmap, p - solv->installed->start)))) + continue; + } + queue_push(dq, p); + } + while (dq->elements[i]) + i++; + } + queue_deleten(dq, oldcnt, cutcnt - oldcnt); + /* unify */ + if (dq->count != oldcnt) + { + for (j = oldcnt; j < dq->count; j++) + { + p = dq->elements[j]; + for (i = 0; i < j; i++) + if (dq->elements[i] == p) + { + dq->elements[j] = 0; + break; + } + } + for (i = j = oldcnt; j < dq->count; j++) + if (dq->elements[j]) + dq->elements[i++] = dq->elements[j]; + queue_truncate(dq, i); + } +#if 0 + printf("RETURN:\n"); + for (i = oldcnt; i < dq->count; i++) + printf(" - %s\n", pool_solvid2str(pool, dq->elements[i])); +#endif +} + +static void +do_complex_recommendations(Solver *solv, Id rec, Map *m, int noselected) +{ + Pool *pool = solv->pool; + Queue dq; + Id p; + int i, blk; + +#if 0 + printf("DO_COMPLEX_RECOMMENDATIONS %s\n", pool_dep2str(pool, rec)); +#endif + queue_init(&dq); + i = pool_normalize_complex_dep(pool, rec, &dq, CPLXDEPS_EXPAND); + if (i == 0 || i == 1) + { + queue_free(&dq); + return; + } + for (i = 0; i < dq.count; i++) + { + blk = i; + for (; (p = dq.elements[i]) != 0; i++) + { + if (p < 0) + { + if (solv->decisionmap[-p] <= 0) + break; + continue; + } + if (solv->decisionmap[p] > 0) + { + if (noselected) + break; + MAPSET(m, p); + for (i++; (p = dq.elements[i]) != 0; i++) + if (p > 0 && solv->decisionmap[p] > 0) + MAPSET(m, p); + p = 1; + break; + } + } + if (!p) + { + for (i = blk; (p = dq.elements[i]) != 0; i++) + if (p > 0) + MAPSET(m, p); + } + while (dq.elements[i]) + i++; + } + queue_free(&dq); } +#endif /*------------------------------------------------------------------- - * - * 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; /* local decisionqueue */ Queue dqs; /* local decisionqueue for supplements */ @@ -2425,214 +2015,250 @@ run_solver(Solver *solv, int disablerules, int doweak) int i, j, n; Solvable *s; Pool *pool = solv->pool; - Id p, *dp; + Id p, pp, *dp, postponed; + int minimizationsteps; + int installedpos = solv->installed ? solv->installed->start : 0; - IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION) + IF_POOLDEBUG (SOLV_DEBUG_RULE_CREATION) { - POOL_DEBUG (SAT_DEBUG_RULE_CREATION, "number of rules: %d\n", solv->nrules); + POOL_DEBUG (SOLV_DEBUG_RULE_CREATION, "number of rules: %d\n", solv->nrules); for (i = 1; i < solv->nrules; i++) - solver_printruleclass(solv, SAT_DEBUG_RULE_CREATION, solv->rules + i); + solver_printruleclass(solv, SOLV_DEBUG_RULE_CREATION, solv->rules + i); } - POOL_DEBUG(SAT_DEBUG_STATS, "initial decisions: %d\n", solv->decisionq.count); - - IF_POOLDEBUG (SAT_DEBUG_SCHUBI) - solver_printdecisions(solv); - /* start SAT algorithm */ - level = 1; + level = 0; systemlevel = level + 1; - POOL_DEBUG(SAT_DEBUG_STATS, "solving...\n"); + POOL_DEBUG(SOLV_DEBUG_SOLVER, "solving...\n"); queue_init(&dq); queue_init(&dqs); /* * here's the main loop: - * 1) propagate new decisions (only needed for level 1) - * 2) try to keep installed packages - * 3) fulfill all unresolved rules - * 4) install recommended packages - * 5) minimalize solution if we had choices + * 1) decide assertion rules and propagate + * 2) fulfill jobs + * 3) try to keep installed packages + * 4) fulfill all unresolved rules + * 5) install recommended packages + * 6) minimalize solution if we had choices * if we encounter a problem, we rewind to a safe level and restart * with step 1 */ - + + minimizationsteps = 0; for (;;) { /* - * propagate + * initial propagation of the assertions */ - - if (level == 1) + if (level <= 0) { - POOL_DEBUG(SAT_DEBUG_PROPAGATE, "propagating (propagate_index: %d; size decisionq: %d)...\n", solv->propagate_index, solv->decisionq.count); + if (level < 0) + break; + makeruledecisions(solv); + level = 1; + if (!disablerules && solv->problems.count) + { + level = -1; + break; + } + POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "initial propagate (propagate_index: %d; size decisionq: %d)...\n", solv->propagate_index, solv->decisionq.count); if ((r = propagate(solv, level)) != 0) { - if (analyze_unsolvable(solv, r, disablerules)) - continue; - queue_free(&dq); - return; + level = analyze_unsolvable(solv, r, disablerules); + continue; } + systemlevel = level + 1; + } + + /* + * resolve jobs first (unless focus_installed is set) + */ + if (level < systemlevel && !solv->focus_installed) + { + olevel = level; + level = resolve_jobrules(solv, level, disablerules, &dq); + if (level < olevel) + continue; + systemlevel = level + 1; } - if (level < systemlevel) + + /* + * installed packages + */ + if (!solv->decisioncnt_update) + solv->decisioncnt_update = solv->decisionq.count; + if (level < systemlevel && solv->installed && solv->installed->nsolvables && !solv->installed->disabled) { - POOL_DEBUG(SAT_DEBUG_STATS, "resolving job rules\n"); - for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++) + Repo *installed = solv->installed; + int pass; + + POOL_DEBUG(SOLV_DEBUG_SOLVER, "resolving installed packages\n"); + /* 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++) { - Id l; - if (r->d < 0) /* ignore disabled rules */ - continue; - queue_empty(&dq); - FOR_RULELITERALS(l, dp, r) + int passlevel = level; + Id *specialupdaters = solv->specialupdaters; + if (pass == 1 && !solv->decisioncnt_keep) + solv->decisioncnt_keep = solv->decisionq.count; + /* start with installedpos, the position that gave us problems the last time */ + for (i = installedpos, n = installed->start; n < installed->end; i++, n++) { - if (l < 0) + Rule *rr; + Id d; + + if (i == installed->end) + i = installed->start; + s = pool->solvables + i; + if (s->repo != installed) + continue; + + if (solv->decisionmap[i] > 0 && (!specialupdaters || !specialupdaters[i - installed->start])) + continue; /* already decided */ + 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 && !(specialupdaters && specialupdaters[i - installed->start])) + continue; /* orpaned package */ + + /* check if we should update this package to the latest version + * noupdate is set for erase jobs, in that case we want to deinstall + * the installed package and not replace it with a newer version + * rr->p != i is for dup jobs where the installed package cannot be kept */ + queue_empty(&dq); + if (!MAPTST(&solv->noupdate, i - installed->start) && (solv->decisionmap[i] < 0 || solv->updatemap_all || (solv->updatemap.size && MAPTST(&solv->updatemap, i - installed->start)) || (rr->p && rr->p != i))) { - if (solv->decisionmap[-l] <= 0) - break; + if (!rr->p) + { + /* specialupdater with no update/feature rule */ + for (d = specialupdaters[i - installed->start]; (p = pool->whatprovidesdata[d++]) != 0; ) + { + if (solv->decisionmap[p] > 0) + { + dq.count = 0; + break; + } + if (!solv->decisionmap[p]) + queue_push(&dq, p); + } + } + else if (specialupdaters && (d = specialupdaters[i - installed->start]) != 0) + { + /* special multiversion handling, make sure best version is chosen */ + if (rr->p == i && solv->decisionmap[i] >= 0) + queue_push(&dq, i); + while ((p = pool->whatprovidesdata[d++]) != 0) + if (solv->decisionmap[p] >= 0) + queue_push(&dq, p); + if (dq.count && solv->update_targets && solv->update_targets->elements[i - installed->start]) + prune_to_update_targets(solv, solv->update_targets->elements + solv->update_targets->elements[i - installed->start], &dq); + if (dq.count) + { + 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 of the update rule */ + FOR_RULELITERALS(p, pp, rr) + { + if (solv->decisionmap[p] > 0) + { + dq.count = 0; /* already fulfilled */ + break; + } + if (!solv->decisionmap[p]) + queue_push(&dq, p); + } + } } - else + if (dq.count && solv->update_targets && solv->update_targets->elements[i - installed->start]) + prune_to_update_targets(solv, solv->update_targets->elements + solv->update_targets->elements[i - installed->start], &dq); + /* install best version */ + if (dq.count) { - if (solv->decisionmap[l] > 0) - break; - if (solv->decisionmap[l] == 0) - queue_push(&dq, l); + olevel = level; + level = selectandinstall(solv, level, &dq, disablerules, rr - solv->rules); + if (level <= olevel) + { + if (level < passlevel) + break; /* trouble */ + if (level < olevel) + n = installed->start; /* redo all */ + i--; + n--; + continue; + } } - } - if (l || !dq.count) - continue; - /* prune to installed if not updating */ - if (!solv->updatesystem && solv->installed && dq.count > 1) - { - int j, k; - for (j = k = 0; j < dq.count; j++) + /* if still undecided keep package */ + if (solv->decisionmap[i] == 0) { - Solvable *s = pool->solvables + dq.elements[j]; - if (s->repo == solv->installed) - dq.elements[k++] = dq.elements[j]; + olevel = level; + if (solv->cleandepsmap.size && MAPTST(&solv->cleandepsmap, i - installed->start)) + { +#if 0 + POOL_DEBUG(SOLV_DEBUG_POLICY, "cleandeps erasing %s\n", pool_solvid2str(pool, i)); + level = setpropagatelearn(solv, level, -i, disablerules, 0); +#else + continue; +#endif + } + else + { + POOL_DEBUG(SOLV_DEBUG_POLICY, "keeping %s\n", pool_solvid2str(pool, i)); + level = setpropagatelearn(solv, level, i, disablerules, r - solv->rules); + } + if (level <= olevel) + { + if (level < passlevel) + break; /* trouble */ + if (level < olevel) + n = installed->start; /* redo all */ + i--; + n--; + continue; /* retry with learnt rule */ + } } - if (k) - dq.count = k; } - olevel = level; - level = selectandinstall(solv, level, &dq, 0, disablerules); - if (level == 0) + if (n < installed->end) { - queue_free(&dq); - return; + installedpos = i; /* retry problem solvable next time */ + break; /* ran into trouble */ } - if (level <= olevel) - break; + installedpos = installed->start; /* reset installedpos */ } systemlevel = level + 1; - if (i < solv->jobrules_end) - continue; + if (pass < 2) + continue; /* had trouble, retry */ } + if (!solv->decisioncnt_keep) + solv->decisioncnt_keep = solv->decisionq.count; - - /* - * installed packages - */ - - if (level < systemlevel && solv->installed && solv->installed->nsolvables) + if (level < systemlevel && solv->focus_installed) { - if (!solv->updatesystem) - { - /* - * Normal run (non-updating) - * Keep as many packages installed as possible - */ - POOL_DEBUG(SAT_DEBUG_STATS, "installing old packages\n"); - - for (i = solv->installed->start; i < solv->installed->end; i++) - { - s = pool->solvables + i; - - /* skip if not installed */ - if (s->repo != solv->installed) - continue; - - /* skip if already decided */ - 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) /* unsolvable */ - { - queue_free(&dq); - return; - } - if (level <= olevel) - break; - } - if (i < solv->installed->end) - 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; - Id inst; - s = pool->solvables + i; - - /* skip if not installed (can't update) */ - if (s->repo != solv->installed) - continue; - /* skip if already decided */ - 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); - - rr = r; - if (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 <= 0) - continue; - - FOR_RULELITERALS(p, dp, rr) - { - if (solv->decisionmap[p] > 0) - break; - if (solv->decisionmap[p] == 0) - queue_push(&dq, p); - } - if (p || !dq.count) /* already fulfilled or empty */ - continue; - if (dq.elements[0] == i) - inst = queue_shift(&dq); - else - inst = 0; - olevel = level; - /* FIXME: it 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, inst, disablerules); - if (level == 0) - { - queue_free(&dq); - return; - } - if (level <= olevel) - break; - } - systemlevel = level + 1; - if (i < solv->installed->end) + olevel = level; + level = resolve_jobrules(solv, level, disablerules, &dq); + if (level < olevel) continue; + systemlevel = level + 1; } if (level < systemlevel) @@ -2641,23 +2267,37 @@ run_solver(Solver *solv, int disablerules, int doweak) /* * decide */ - - POOL_DEBUG(SAT_DEBUG_POLICY, "deciding unresolved rules\n"); + if (!solv->decisioncnt_resolve) + solv->decisioncnt_resolve = solv->decisionq.count; + POOL_DEBUG(SOLV_DEBUG_POLICY, "deciding unresolved rules\n"); + postponed = 0; for (i = 1, n = 1; ; i++, n++) { - if (n == solv->nrules) - break; + if (n >= solv->nrules) + { + if (postponed <= 0) + break; + i = postponed; + postponed = -1; + n = 1; + } if (i == solv->nrules) i = 1; r = solv->rules + i; if (r->d < 0) /* ignore disabled rules */ continue; - queue_empty(&dq); + if (r->p < 0) /* most common cases first */ + { + if (r->d == 0 || solv->decisionmap[-r->p] <= 0) + continue; + } + if (dq.count) + queue_empty(&dq); if (r->d == 0) { /* binary or unary rule */ - /* need two positive undecided literals */ - if (r->p < 0 || r->w2 <= 0) + /* need two positive undecided literals, r->p already checked above */ + if (r->w2 <= 0) continue; if (solv->decisionmap[r->p] || solv->decisionmap[r->w2]) continue; @@ -2671,13 +2311,9 @@ run_solver(Solver *solv, int disablerules, int doweak) * no positive literal is installed * i.e. the rule is not fulfilled and we * just need to decide on the positive literals + * (decisionmap[-r->p] for the r->p < 0 case is already checked above) */ - if (r->p < 0) - { - if (solv->decisionmap[-r->p] <= 0) - continue; - } - else + if (r->p >= 0) { if (solv->decisionmap[r->p] > 0) continue; @@ -2703,1132 +2339,518 @@ run_solver(Solver *solv, int disablerules, int doweak) if (p) continue; } - IF_POOLDEBUG (SAT_DEBUG_PROPAGATE) + IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE) { - POOL_DEBUG(SAT_DEBUG_PROPAGATE, "unfulfilled "); - solver_printruleclass(solv, SAT_DEBUG_PROPAGATE, r); + POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "unfulfilled "); + solver_printruleclass(solv, SOLV_DEBUG_PROPAGATE, r); } /* dq.count < 2 cannot happen as this means that * the rule is unit */ - assert(dq.count > 1); - - olevel = level; - level = selectandinstall(solv, level, &dq, 0, disablerules); - if (level == 0) - { - queue_free(&dq); - return; - } - if (level < systemlevel) - break; - n = 0; - } /* for(), decide */ - - if (n != solv->nrules) /* continue if level < systemlevel */ - continue; - - if (doweak) - { - int qcount; - - POOL_DEBUG(SAT_DEBUG_POLICY, "installing recommended packages\n"); - queue_empty(&dq); - queue_empty(&dqs); - for (i = 1; i < pool->nsolvables; i++) - { - if (solv->decisionmap[i] < 0) - continue; - if (solv->decisionmap[i] > 0) - { - /* 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) - { - recp = s->repo->idarraydata + s->recommends; - while ((rec = *recp++) != 0) - { - qcount = dq.count; - FOR_PROVIDES(p, pp, rec) - { - if (solv->decisionmap[p] > 0) - { - dq.count = qcount; - break; - } - else if (solv->decisionmap[p] == 0) - { - queue_pushunique(&dq, p); - } - } - } - } - } - else - { - s = pool->solvables + i; - if (!s->supplements) - continue; - if (!pool_installable(pool, s)) - continue; - if (!solver_is_supplementing(solv, s)) - continue; - if (solv->ignorealreadyrecommended && solv->installed) - queue_pushunique(&dqs, i); /* needs filter */ - else - queue_pushunique(&dq, i); - } - } - if (solv->ignorealreadyrecommended && dqs.count) - { - /* turn off all new packages */ - 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]; - } - /* filter out old supplements */ - for (i = 0; i < dqs.count; i++) - { - p = dqs.elements[i]; - s = pool->solvables + p; - if (!s->supplements) - continue; - if (!solver_is_supplementing(solv, s)) - queue_pushunique(&dq, p); - } - /* 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 (dq.count) - { - if (dq.count > 1) - policy_filter_unwanted(solv, &dq, 0, POLICY_MODE_RECOMMEND); - p = dq.elements[0]; - POOL_DEBUG(SAT_DEBUG_POLICY, "installing recommended %s\n", solvable2str(pool, pool->solvables + p)); - queue_push(&solv->recommendations, p); - level = setpropagatelearn(solv, level, p, 0); - continue; - } - } - - if (solv->distupgrade && solv->installed) - { - /* let's see if we can install some unsupported package */ - int ri; - POOL_DEBUG(SAT_DEBUG_STATS, "deciding unsupported packages\n"); - for (i = solv->installed->start, ri = 0; i < solv->installed->end; i++, ri++) - { - s = pool->solvables + i; - if (s->repo != solv->installed) - continue; - if (solv->decisionmap[i]) - continue; - if (!solv->rules[solv->updaterules + ri].p && !solv->rules[solv->featurerules + ri].p) - break; - } - if (i < solv->installed->end) - { - if (solv->distupgrade_removeunsupported) - { - POOL_DEBUG(SAT_DEBUG_STATS, "removing unsupported %s\n", solvable2str(pool, pool->solvables + i)); - level = setpropagatelearn(solv, level, -i, 0); - } - else - { - POOL_DEBUG(SAT_DEBUG_STATS, "keeping unsupported %s\n", solvable2str(pool, pool->solvables + i)); - level = setpropagatelearn(solv, level, i, 0); - } - continue; - } - } - - if (solv->solution_callback) - { - solv->solution_callback(solv, solv->solution_callback_data); - if (solv->branches.count) - { - 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) - { - queue_free(&dq); - return; - } - 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) - { - lasti = i; - lastl = l; - } - } - 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) - { - queue_free(&dq); - return; - } - continue; - } - } - break; - } - POOL_DEBUG(SAT_DEBUG_STATS, "solver statistics: %d learned rules, %d unsolvable\n", solv->stats_learned, solv->stats_unsolvable); - - POOL_DEBUG(SAT_DEBUG_STATS, "done solving.\n\n"); - queue_free(&dq); - queue_free(&dqs); -} - - -/*------------------------------------------------------------------- - * - * 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); - - for (i = 0; problem[i]; i++) - if (problem[i] != sug) - enableproblem(solv, problem[i]); - - if (sug < 0) - disableupdaterules(solv, job, -(sug + 1)); - else if (sug >= solv->updaterules && sug < solv->updaterules_end) - { - /* enable feature rule */ - Rule *r = solv->rules + solv->featurerules + (sug - solv->updaterules); - if (r->p) - enablerule(solv, r); - } - - enableweakrules(solv); - - for (;;) - { - int njob, nfeature, nupdate; - queue_empty(&solv->problems); - revert(solv, 1); /* XXX no longer needed? */ - reset_solver(solv); - - if (!solv->problems.count) - run_solver(solv, 0, 0); - - 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->featurerules_end) - nfeature++; - else if (v > 0) - nupdate++; - else - { - if ((job->elements[-v -1] & SOLVER_ESSENTIAL) != 0) - continue; /* not that one! */ - 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->featurerules_end) - 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->updaterules_end) - { - Rule *r = solv->rules + (v - solv->updaterules + solv->featurerules); - 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) + assert(dq.count > 1); + + /* prune to cleandeps packages */ + if (solv->cleandepsmap.size && solv->installed) { - POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "more than one solution found:\n"); - for (i = disabledcnt; i < disabled.count; i++) - solver_printproblem(solv, disabled.elements[i]); + Repo *installed = solv->installed; + for (j = 0; j < dq.count; j++) + if (pool->solvables[dq.elements[j]].repo == installed && MAPTST(&solv->cleandepsmap, dq.elements[j] - installed->start)) + break; + if (j < dq.count) + { + dq.elements[0] = dq.elements[j]; + queue_truncate(&dq, 1); + } } - for (i = disabledcnt; i < disabled.count; i++) + + if (dq.count > 1 && postponed >= 0) { - v = disabled.elements[i]; - disableproblem(solv, v); - if (v >= solv->updaterules && v < solv->updaterules_end) + policy_filter_unwanted(solv, &dq, POLICY_MODE_CHOOSE_NOREORDER); + if (dq.count > 1) { - Rule *r = solv->rules + (v - solv->updaterules + solv->featurerules); - if (r->p) - enablerule(solv, r); + if (!postponed) + postponed = i; + 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 */ - - /* FIXME! */ - for (i = 0; problem[i]; i++) - enableproblem(solv, problem[i]); - disableupdaterules(solv, job, -1); - - /* disable problem rules again */ - for (i = 0; problem[i]; i++) - disableproblem(solv, problem[i]); - POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "refine_suggestion end\n"); -} - - -/*------------------------------------------------------------------- - * sorting helper for problems - * - * bring update rules before job rules - * make essential job rules last - */ - -Queue *problems_sort_data; - -static int -problems_sortcmp(const void *ap, const void *bp) -{ - Id a = *(Id *)ap, b = *(Id *)bp; - if (a < 0 && b > 0) - return 1; - if (a > 0 && b < 0) - return -1; - if (a < 0 && b < 0) - { - Queue *job = problems_sort_data; - int af = job->elements[-a - 1] & SOLVER_ESSENTIAL; - int bf = job->elements[-a - 1] & SOLVER_ESSENTIAL; - int x = bf - af; - if (x) - return x; - } - return a - b; -} + olevel = level; + level = selectandinstall(solv, level, &dq, disablerules, r - solv->rules); + if (level < systemlevel) + break; /* trouble */ + /* something changed, so look at all rules again */ + n = 0; + } -/*------------------------------------------------------------------- - * sort problems - */ + if (n < solv->nrules) /* ran into trouble? */ + continue; /* start over */ -static void -problems_sort(Solver *solv, Queue *job) -{ - int i, j; - if (!solv->problems.count) - return; - for (i = j = 1; i < solv->problems.count; i++) - { - if (!solv->problems.elements[i]) + /* decide leftover cleandeps packages */ + if (solv->cleandepsmap.size && solv->installed) { - if (i > j + 1) + for (p = solv->installed->start; p < solv->installed->end; p++) { - problems_sort_data = job; - qsort(solv->problems.elements + j, i - j, sizeof(Id), problems_sortcmp); + s = pool->solvables + p; + if (s->repo != solv->installed) + continue; + if (solv->decisionmap[p] == 0 && MAPTST(&solv->cleandepsmap, p - solv->installed->start)) + { + POOL_DEBUG(SOLV_DEBUG_POLICY, "cleandeps erasing %s\n", pool_solvid2str(pool, p)); + olevel = level; + level = setpropagatelearn(solv, level, -p, 0, 0); + if (level < olevel) + break; + } } - if (++i == solv->problems.count) - break; - j = i + 1; + if (p < solv->installed->end) + continue; } - } -} + /* at this point we have a consistent system. now do the extras... */ -/*------------------------------------------------------------------- - * convert problems to solutions - */ - -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, nsol, probsolved; - unsigned int now, refnow; - - if (!solv->problems.count) - return; - now = sat_timems(0); - problems_sort(solv, job); - 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; - probsolved = 0; - refnow = sat_timems(0); - 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); - POOL_DEBUG(SAT_DEBUG_STATS, "refining took %d ms\n", sat_timems(refnow)); - 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; - refnow = sat_timems(0); - probsolved = 0; - continue; - } - if (v < 0 && (job->elements[-v - 1] & SOLVER_ESSENTIAL)) + if (!solv->decisioncnt_weak) + solv->decisioncnt_weak = solv->decisionq.count; + if (doweak) { - /* essential job, skip if we already have a solution */ - if (probsolved) - continue; - } - refine_suggestion(solv, job, problem, v, &solution); - if (!solution.count) - continue; /* this solution didn't work out */ + int qcount; - nsol = 0; - 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->updaterules_end)); -#if 0 - solver_printproblem(solv, why); -#endif - if (why < 0) - { - /* job descriptor */ - queue_push(&solutions, 0); - queue_push(&solutions, -why); - } - else + POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended packages\n"); + queue_empty(&dq); /* recommended packages */ + queue_empty(&dqs); /* supplemented packages */ + for (i = 1; i < pool->nsolvables; i++) { - /* update rule, find replacement package */ - Id p, d, *dp, rp = 0; - Rule *rr; - p = solv->installed->start + (why - solv->updaterules); - rr = solv->rules + solv->featurerules + (why - solv->updaterules); - if (!rr->p) - rr = solv->rules + why; - if (solv->distupgrade && solv->rules[why].p != p && solv->decisionmap[p] > 0) - { - /* distupgrade case, allow to keep old package */ - queue_push(&solutions, p); - queue_push(&solutions, p); - nsol++; - continue; - } - if (solv->decisionmap[p] > 0) - continue; /* false alarm, turned out we can keep the package */ - if (rr->w2) + if (solv->decisionmap[i] < 0) + continue; + if (solv->decisionmap[i] > 0) { - d = rr->d < 0 ? -rr->d - 1 : rr->d; - if (!d) - { - if (solv->decisionmap[rr->w2] > 0 && pool->solvables[rr->w2].repo != solv->installed) - rp = rr->w2; - } - else + /* installed, check for recommends */ + Id *recp, rec, pp, p; + s = pool->solvables + i; + if (!solv->addalreadyrecommended && s->repo == solv->installed) + continue; + /* XXX need to special case AND ? */ + if (s->recommends) { - for (dp = pool->whatprovidesdata + d; *dp; dp++) + recp = s->repo->idarraydata + s->recommends; + while ((rec = *recp++) != 0) { - if (solv->decisionmap[*dp] > 0 && pool->solvables[*dp].repo != solv->installed) +#ifdef ENABLE_COMPLEX_DEPS + if (pool_is_complex_dep(pool, rec)) { - rp = *dp; - break; + add_complex_recommends(solv, rec, &dq, 0); + continue; + } +#endif + qcount = dq.count; + FOR_PROVIDES(p, pp, rec) + { + if (solv->decisionmap[p] > 0) + { + dq.count = qcount; + break; + } + else if (solv->decisionmap[p] == 0) + { + if (solv->dupmap_all && solv->installed && pool->solvables[p].repo == solv->installed && (solv->droporphanedmap_all || (solv->droporphanedmap.size && MAPTST(&solv->droporphanedmap, p - solv->installed->start)))) + continue; + queue_pushunique(&dq, p); + } } } - } + } + } + else + { + s = pool->solvables + i; + if (!s->supplements) + continue; + if (!pool_installable(pool, s)) + continue; + if (!solver_is_supplementing(solv, s)) + continue; + if (solv->dupmap_all && solv->installed && s->repo == solv->installed && (solv->droporphanedmap_all || (solv->droporphanedmap.size && MAPTST(&solv->droporphanedmap, i - solv->installed->start)))) + continue; + queue_push(&dqs, i); } - queue_push(&solutions, p); - queue_push(&solutions, rp); } - nsol++; - } - /* mark end of this solution */ - if (nsol) - { - probsolved = 1; - queue_push(&solutions, 0); - queue_push(&solutions, 0); - } - else - { - POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "Oops, everything was fine?\n"); - } - } - 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); - POOL_DEBUG(SAT_DEBUG_STATS, "problems_to_solutions took %d ms\n", sat_timems(now)); -} - - -/*------------------------------------------------------------------- - * - * problem iterator - * - * advance to next problem - */ -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; -} - - -/*------------------------------------------------------------------- - * - * solution iterator - */ - -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; -} - - -/*------------------------------------------------------------------- - * - * solution element iterator - */ - -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; -} - - -/*------------------------------------------------------------------- - * - * Retrieve information about a problematic rule - * - * 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, d, w2, pp, req, *reqp, con, *conp, obs, *obsp, *dp; + /* 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) + { + Map obsmap; + Id obs, *obsp, po, ppo; - assert(rid > 0); - if (rid >= solv->jobrules && rid < solv->jobrules_end) - { + map_init(&obsmap, pool->nsolvables); + 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->multiversion.size && MAPTST(&solv->multiversion, p)) + continue; + obsp = s->repo->idarraydata + s->obsoletes; + /* foreach obsoletes */ + while ((obs = *obsp++) != 0) + FOR_PROVIDES(po, ppo, obs) + MAPSET(&obsmap, po); + } + 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); + } - r = solv->rules + rid; - p = solv->ruletojob.elements[rid - solv->jobrules]; - *depp = job->elements[p + 1]; - *sourcep = p; - *targetp = job->elements[p]; - d = r->d < 0 ? -r->d - 1 : r->d; - if (d == 0 && r->w2 == 0 && r->p == -SYSTEMSOLVABLE && (job->elements[p] & SOLVER_SELECTMASK) != SOLVER_SOLVABLE_ONE_OF) - return SOLVER_PROBLEM_JOB_NOTHING_PROVIDES_DEP; - return SOLVER_PROBLEM_JOB_RULE; - } - if (rid >= solv->updaterules && rid < solv->updaterules_end) - { - *depp = 0; - *sourcep = solv->installed->start + (rid - solv->updaterules); - *targetp = 0; - return SOLVER_PROBLEM_UPDATE_RULE; - } - assert(rid < solv->rpmrules_end); - r = solv->rules + rid; - assert(r->p < 0); - d = r->d < 0 ? -r->d - 1 : r->d; - if (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) + /* filter out all already supplemented packages if requested */ + if (!solv->addalreadyrecommended && dqs.count) { - if (req == SOLVABLE_PREREQMARKER) - continue; - dp = pool->whatprovidesdata + pool_whatprovides(pool, req); - if (*dp == 0) - break; + /* filter out old supplements */ + for (i = j = 0; i < dqs.count; i++) + { + p = dqs.elements[i]; + s = pool->solvables + p; + if (s->supplements && solver_is_supplementing_alreadyinstalled(solv, s)) + dqs.elements[j++] = p; + } + dqs.count = j; } - if (req) + + /* 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->multiversion.size) { - *depp = req; - return SOLVER_PROBLEM_NOTHING_PROVIDES_DEP; - } - } - if (!solv->allowselfconflicts && s->conflicts) - { - conp = s->repo->idarraydata + s->conflicts; - while ((con = *conp++) != 0) - FOR_PROVIDES(p, pp, con) - if (p == -r->p) + for (i = j = 0; i < dqs.count; i++) { - *depp = con; - return SOLVER_PROBLEM_SELF_CONFLICT; + p = dqs.elements[i]; + if (MAPTST(&solv->multiversion, 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; } - } - /* should never happen */ - *depp = 0; - return SOLVER_PROBLEM_RPM_RULE; - } - s = pool->solvables - r->p; - if (installed && !solv->fixsystem && s->repo == installed) - dontfix = 1; - w2 = r->w2; - if (d && pool->whatprovidesdata[d] < 0) - { - /* rule looks like -p|-c|x|x|x..., we only create this for patches with multiversion */ - /* reduce it to -p|-c case */ - w2 = pool->whatprovidesdata[d]; - } - if (d == 0 && w2 < 0) - { - /* a package conflict */ - Solvable *s2 = pool->solvables - w2; - int dontfix2 = 0; - - if (installed && !solv->fixsystem && s2->repo == installed) - dontfix2 = 1; + dqs.count = j; + } - /* 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)) - { - /* also check noobsoletes map */ - if ((s->evr == s2->evr && s->arch == s2->arch) || !solv->noobsoletes.size - || ((!installed || s->repo != installed) && !MAPTST(&solv->noobsoletes, -r->p)) - || ((!installed || s2->repo != installed) && !MAPTST(&solv->noobsoletes, -w2))) + /* make dq contain both recommended and supplemented pkgs */ + if (dqs.count) { - *depp = 0; - *sourcep = -r->p; - *targetp = -w2; - return SOLVER_PROBLEM_SAME_NAME; + for (i = 0; i < dqs.count; i++) + queue_pushunique(&dq, dqs.elements[i]); } - } - /* check conflicts in both directions */ - if (s->conflicts) - { - conp = s->repo->idarraydata + s->conflicts; - while ((con = *conp++) != 0) - { - FOR_PROVIDES(p, pp, con) + if (dq.count) + { + Map dqmap; + int decisioncount = solv->decisionq.count; + + if (dq.count == 1) { - if (dontfix && pool->solvables[p].repo == installed) - continue; - if (p != -w2) - continue; - *depp = con; - *sourcep = -r->p; - *targetp = p; - return SOLVER_PROBLEM_PACKAGE_CONFLICT; + /* simple case, just one package. no need to choose to best version */ + p = dq.elements[0]; + if (dqs.count) + POOL_DEBUG(SOLV_DEBUG_POLICY, "installing supplemented %s\n", pool_solvid2str(pool, p)); + else + POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended %s\n", pool_solvid2str(pool, p)); + level = setpropagatelearn(solv, level, p, 0, 0); + continue; /* back to main loop */ } - } - } - if (s2->conflicts) - { - conp = s2->repo->idarraydata + s2->conflicts; - while ((con = *conp++) != 0) - { - FOR_PROVIDES(p, pp, con) + + /* filter packages, this gives us the best versions */ + policy_filter_unwanted(solv, &dq, POLICY_MODE_RECOMMEND); + + /* create map of result */ + map_init(&dqmap, pool->nsolvables); + for (i = 0; i < dq.count; i++) + MAPSET(&dqmap, dq.elements[i]); + + /* install all supplemented packages */ + for (i = 0; i < dqs.count; i++) { - if (dontfix2 && pool->solvables[p].repo == installed) - continue; - if (p != -r->p) + p = dqs.elements[i]; + if (solv->decisionmap[p] || !MAPTST(&dqmap, p)) continue; - *depp = con; - *sourcep = -w2; - *targetp = p; - return SOLVER_PROBLEM_PACKAGE_CONFLICT; + POOL_DEBUG(SOLV_DEBUG_POLICY, "installing supplemented %s\n", pool_solvid2str(pool, p)); + olevel = level; + level = setpropagatelearn(solv, level, p, 0, 0); + if (level <= olevel) + break; } - } - } - /* check obsoletes in both directions */ - if ((!installed || s->repo != installed) && s->obsoletes && !(solv->noobsoletes.size && MAPTST(&solv->noobsoletes, -r->p))) - { - obsp = s->repo->idarraydata + s->obsoletes; - while ((obs = *obsp++) != 0) - { - FOR_PROVIDES(p, pp, obs) + if (i < dqs.count || solv->decisionq.count < decisioncount) { - if (p != -w2) - continue; - if (!solv->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p, obs)) - continue; - *depp = obs; - *sourcep = -r->p; - *targetp = p; - return SOLVER_PROBLEM_PACKAGE_OBSOLETES; + map_free(&dqmap); + continue; } - } - } - if ((!installed || s2->repo != installed) && s2->obsoletes && !(solv->noobsoletes.size && MAPTST(&solv->noobsoletes, -w2))) - { - obsp = s2->repo->idarraydata + s2->obsoletes; - while ((obs = *obsp++) != 0) - { - FOR_PROVIDES(p, pp, obs) + + /* install all recommended packages */ + /* more work as we want to created branches if multiple + * choices are valid */ + for (i = 0; i < decisioncount; i++) { - if (p != -r->p) + Id rec, *recp, pp; + p = solv->decisionq.elements[i]; + if (p < 0) + continue; + s = pool->solvables + p; + if (!s->repo || (!solv->addalreadyrecommended && s->repo == solv->installed)) continue; - if (!solv->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p, obs)) + if (!s->recommends) continue; - *depp = obs; - *sourcep = -w2; - *targetp = p; - return SOLVER_PROBLEM_PACKAGE_OBSOLETES; + recp = s->repo->idarraydata + s->recommends; + while ((rec = *recp++) != 0) + { + queue_empty(&dq); +#ifdef ENABLE_COMPLEX_DEPS + if (pool_is_complex_dep(pool, rec)) + add_complex_recommends(solv, rec, &dq, &dqmap); + else +#endif + FOR_PROVIDES(p, pp, rec) + { + if (solv->decisionmap[p] > 0) + { + dq.count = 0; + break; + } + else if (solv->decisionmap[p] == 0 && MAPTST(&dqmap, p)) + queue_push(&dq, p); + } + if (!dq.count) + continue; + if (dq.count > 1) + policy_filter_unwanted(solv, &dq, POLICY_MODE_CHOOSE); + /* if we have multiple candidates we open a branch */ + if (dq.count > 1) + createbranch(solv, level, &dq, s - pool->solvables, rec); + p = dq.elements[0]; + POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended %s\n", pool_solvid2str(pool, 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 */ } + map_free(&dqmap); + continue; /* back to main loop so that all deps are checked */ } } - if (solv->implicitobsoleteusesprovides && (!installed || s->repo != installed) && !(solv->noobsoletes.size && MAPTST(&solv->noobsoletes, -r->p))) - { - FOR_PROVIDES(p, pp, s->name) - { - if (p != -w2) - continue; - *depp = s->name; - *sourcep = -r->p; - *targetp = p; - return SOLVER_PROBLEM_PACKAGE_OBSOLETES; - } - } - if (solv->implicitobsoleteusesprovides && (!installed || s2->repo != installed) && !(solv->noobsoletes.size && MAPTST(&solv->noobsoletes, -w2))) + + if (!solv->decisioncnt_orphan) + solv->decisioncnt_orphan = solv->decisionq.count; + if (solv->dupmap_all && solv->installed) { - FOR_PROVIDES(p, pp, s2->name) + int installedone = 0; + + /* let's see if we can install some unsupported package */ + POOL_DEBUG(SOLV_DEBUG_SOLVER, "deciding orphaned packages\n"); + for (i = 0; i < solv->orphaned.count; i++) { - if (p != -r->p) + p = solv->orphaned.elements[i]; + if (solv->decisionmap[p]) + continue; /* already decided */ + if (solv->droporphanedmap_all) + continue; + if (solv->droporphanedmap.size && MAPTST(&solv->droporphanedmap, p - solv->installed->start)) continue; - *depp = s2->name; - *sourcep = -w2; - *targetp = p; - return SOLVER_PROBLEM_PACKAGE_OBSOLETES; + POOL_DEBUG(SOLV_DEBUG_SOLVER, "keeping orphaned %s\n", pool_solvid2str(pool, p)); + olevel = level; + level = setpropagatelearn(solv, level, p, 0, 0); + installedone = 1; + if (level < olevel) + break; } - } - /* all cases checked, can't happen */ - *depp = 0; - *sourcep = -r->p; - *targetp = 0; - return SOLVER_PROBLEM_RPM_RULE; - } - /* simple requires */ - if (s->requires) - { - reqp = s->repo->idarraydata + s->requires; - while ((req = *reqp++) != 0) - { - if (req == SOLVABLE_PREREQMARKER) - continue; - dp = pool->whatprovidesdata + pool_whatprovides(pool, req); - if (d == 0) + if (installedone || i < solv->orphaned.count) + continue; /* back to main loop */ + for (i = 0; i < solv->orphaned.count; i++) { - if (*dp == r->w2 && dp[1] == 0) + p = solv->orphaned.elements[i]; + if (solv->decisionmap[p]) + continue; /* already decided */ + POOL_DEBUG(SOLV_DEBUG_SOLVER, "removing orphaned %s\n", pool_solvid2str(pool, p)); + olevel = level; + level = setpropagatelearn(solv, level, -p, 0, 0); + if (level < olevel) break; } - else if (dp - pool->whatprovidesdata == d) - break; - } - if (req) - { - *depp = req; - *sourcep = -r->p; - *targetp = 0; - return SOLVER_PROBLEM_DEP_PROVIDERS_NOT_INSTALLABLE; + if (i < solv->orphaned.count) + continue; /* back to main loop */ + if (solv->brokenorphanrules) + { + solver_check_brokenorphanrules(solv, &dq); + if (dq.count) + { + policy_filter_unwanted(solv, &dq, POLICY_MODE_CHOOSE); + for (i = 0; i < dq.count; i++) + { + p = dq.elements[i]; + POOL_DEBUG(SOLV_DEBUG_POLICY, "installing orphaned dep %s\n", pool_solvid2str(pool, p)); + olevel = level; + level = setpropagatelearn(solv, level, p, 0, 0); + if (level < olevel) + break; + } + continue; + } + } } - } - /* all cases checked, can't happen */ - *depp = 0; - *sourcep = -r->p; - *targetp = 0; - return SOLVER_PROBLEM_RPM_RULE; -} - - -/*------------------------------------------------------------------- - * - * find problem rule - */ - -static void -findproblemrule_internal(Solver *solv, Id idx, Id *reqrp, Id *conrp, Id *sysrp, Id *jobrp) -{ - Id rid, d; - 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->jobrules && rid < solv->jobrules_end) + /* one final pass to make sure we decided all installed packages */ + if (solv->installed) { - if (!*jobrp) - *jobrp = rid; + for (p = solv->installed->start; p < solv->installed->end; p++) + { + if (solv->decisionmap[p]) + continue; /* already decided */ + s = pool->solvables + p; + if (s->repo != solv->installed) + continue; + POOL_DEBUG(SOLV_DEBUG_SOLVER, "removing unwanted %s\n", pool_solvid2str(pool, p)); + olevel = level; + level = setpropagatelearn(solv, level, -p, 0, 0); + if (level < olevel) + break; + } + if (p < solv->installed->end) + continue; /* back to main loop */ } - else if (rid >= solv->updaterules && rid < solv->updaterules_end) + + if (solv->installed && solv->cleandepsmap.size && cleandeps_check_mistakes(solv)) { - if (!*sysrp) - *sysrp = rid; + solver_reset(solv); + level = 0; /* restart from scratch */ + continue; } - else + + if (solv->solution_callback) { - assert(rid < solv->rpmrules_end); - r = solv->rules + rid; - d = r->d < 0 ? -r->d - 1 : r->d; - if (!d && r->w2 < 0) - { - if (!*conrp) - *conrp = rid; - } - else + solv->solution_callback(solv, solv->solution_callback_data); + if (solv->branches.count) { - if (!d && r->w2 == 0 && !reqassert) + int l, endi = 0; + p = l = 0; + for (i = solv->branches.count - 1; i >= 0; i--) { - /* prefer assertions (XXX: bad idea?) */ - *reqrp = rid; - reqassert = 1; + p = solv->branches.elements[i]; + if (p > 0 && !l) + { + endi = i + 1; + l = p; + i -= 3; /* skip: p data count */ + } + else if (p > 0) + break; + else if (p < 0) + l = 0; } - if (!*reqrp) - *reqrp = rid; - else if (solv->installed && r->p < 0 && solv->pool->solvables[-r->p].repo == solv->installed) + if (i >= 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; + while (i > 0 && solv->branches.elements[i - 1] > 0) + i--; + level = takebranch(solv, i, endi, "branching", disablerules); + continue; } } + /* all branches done, we're finally finished */ + break; } - } - if (!*reqrp && lreqr) - *reqrp = lreqr; - if (!*conrp && lconr) - *conrp = lconr; - if (!*jobrp && ljobr) - *jobrp = ljobr; - if (!*sysrp && lsysr) - *sysrp = lsysr; -} - - -/*------------------------------------------------------------------- - * - * find problem rule - * - * 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); -} - - -/*------------------------------------------------------------------- - * - * create reverse obsoletes map for installed solvables - * - * for each installed solvable find which packages with *different* names - * obsolete the solvable. - * this index is used in policy_findupdatepackages if noupdateprovide is set. - */ - -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->obsoletes) - continue; - if (!pool_installable(pool, s)) - continue; - obsp = s->repo->idarraydata + s->obsoletes; - while ((obs = *obsp++) != 0) + /* auto-minimization step */ + if (solv->branches.count) { - FOR_PROVIDES(p, pp, obs) + int endi, lasti = -1, lastiend = -1; + if (solv->recommends_index < solv->decisionq.count) + policy_update_recommendsmap(solv); + for (endi = solv->branches.count; endi > 0;) { - if (pool->solvables[p].repo != installed) - continue; - if (pool->solvables[p].name == s->name) - continue; - if (!solv->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p, obs)) - continue; - obsoletes[p - installed->start]++; + int l, lastsi = -1, starti = endi - solv->branches.elements[endi - 2]; + l = solv->branches.elements[endi - 1]; + for (i = starti; i < endi - 4; i++) + { + p = solv->branches.elements[i]; + if (p <= 0) + continue; + if (solv->decisionmap[p] > l) + { + lasti = i; + lastiend = endi; + lastsi = -1; + break; + } + if (lastsi < 0 && (MAPTST(&solv->recommendsmap, p) || solver_is_supplementing(solv, pool->solvables + p))) + lastsi = i; + } + if (lastsi >= 0) + { + /* we have a recommended package that could not be installed */ + /* take it if our current selection is not recommended */ + for (i = starti; i < endi - 4; i++) + { + p = -solv->branches.elements[i]; + if (p <= 0 || solv->decisionmap[p] != l + 1) + continue; + if (!(MAPTST(&solv->recommendsmap, p) || solver_is_supplementing(solv, pool->solvables + p))) + { + lasti = lastsi; + lastiend = endi; + break; + } + } + } + endi = starti; } - } - } - 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->obsoletes) - continue; - if (!pool_installable(pool, s)) - continue; - obsp = s->repo->idarraydata + s->obsoletes; - while ((obs = *obsp++) != 0) - { - FOR_PROVIDES(p, pp, obs) + if (lasti >= 0) { - if (pool->solvables[p].repo != installed) - continue; - if (pool->solvables[p].name == s->name) - continue; - if (!solv->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p, obs)) - continue; - p -= installed->start; - if (obsoletes_data[obsoletes[p]] != i) - obsoletes_data[--obsoletes[p]] = i; + minimizationsteps++; + level = takebranch(solv, lasti, lastiend, "minimizing", disablerules); + continue; /* back to main loop */ } } + /* no minimization found, we're finally finished! */ + break; + } + + POOL_DEBUG(SOLV_DEBUG_STATS, "solver statistics: %d learned rules, %d unsolvable, %d minimization steps\n", solv->stats_learned, solv->stats_unsolvable, minimizationsteps); + + POOL_DEBUG(SOLV_DEBUG_STATS, "done solving.\n\n"); + queue_free(&dq); + queue_free(&dqs); + if (level < 0) + { + /* unsolvable */ + solv->decisioncnt_jobs = solv->decisionq.count; + solv->decisioncnt_update = solv->decisionq.count; + solv->decisioncnt_keep = solv->decisionq.count; + solv->decisioncnt_resolve = solv->decisionq.count; + solv->decisioncnt_weak = solv->decisionq.count; + solv->decisioncnt_orphan = solv->decisionq.count; } +#if 0 + solver_printdecisionq(solv, SOLV_DEBUG_RESULT); +#endif } /*------------------------------------------------------------------- - * + * * remove disabled conflicts + * + * 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 @@ -3841,22 +2863,26 @@ removedisabledconflicts(Solver *solv, Queue *removed) Rule *r; Id *decisionmap = solv->decisionmap; - POOL_DEBUG(SAT_DEBUG_SCHUBI, "removedisabledconflicts\n"); queue_empty(removed); for (i = 0; i < solv->decisionq.count; i++) { p = solv->decisionq.elements[i]; if (p > 0) - continue; - /* a conflict. we never do conflicts on free decisions, so there - * must have been an unit rule */ + continue; /* conflicts only, please */ why = solv->decisionq_why.elements[i]; + if (why == 0) + { + /* no rule involved, must be a orphan package drop */ + continue; + } + /* we never do conflicts on free decisions, so there + * must have been an unit rule */ assert(why > 0); r = solv->rules + why; if (r->d < 0 && decisionmap[-p]) { /* rule is now disabled, remove from decisionmap */ - POOL_DEBUG(SAT_DEBUG_SCHUBI, "removing conflict for package %s[%d]\n", solvable2str(pool, pool->solvables - p), -p); + POOL_DEBUG(SOLV_DEBUG_SOLVER, "removing conflict for package %s[%d]\n", pool_solvid2str(pool, -p), -p); queue_push(removed, -p); queue_push(removed, decisionmap[-p]); decisionmap[-p] = 0; @@ -3876,81 +2902,370 @@ removedisabledconflicts(Solver *solv, Queue *removed) } if (r->d < 0) continue; - if (!r->w2) - { - if (r->p < 0 && !decisionmap[-r->p]) - new = r->p; - } - else if (!r->d) + if (!r->w2) + { + if (r->p < 0 && !decisionmap[-r->p]) + new = r->p; + } + else if (!r->d) + { + /* binary rule */ + if (r->p < 0 && decisionmap[-r->p] == 0 && DECISIONMAP_FALSE(r->w2)) + new = r->p; + else if (r->w2 < 0 && decisionmap[-r->w2] == 0 && DECISIONMAP_FALSE(r->p)) + new = r->w2; + } + else + { + 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(SOLV_DEBUG_SOLVER, "re-conflicting package %s[%d]\n", pool_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->pkgrules_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() */ + + +void +solver_calculate_multiversionmap(Pool *pool, Queue *job, Map *multiversionmap) +{ + int i; + Id how, what, select; + Id p, pp; + for (i = 0; i < job->count; i += 2) + { + how = job->elements[i]; + if ((how & SOLVER_JOBMASK) != SOLVER_MULTIVERSION) + continue; + what = job->elements[i + 1]; + select = how & SOLVER_SELECTMASK; + if (!multiversionmap->size) + map_grow(multiversionmap, pool->nsolvables); + if (select == SOLVER_SOLVABLE_ALL) + { + FOR_POOL_SOLVABLES(p) + MAPSET(multiversionmap, p); + } + else if (select == SOLVER_SOLVABLE_REPO) + { + Solvable *s; + Repo *repo = pool_id2repo(pool, what); + if (repo) + FOR_REPO_SOLVABLES(repo, p, s) + MAPSET(multiversionmap, p); + } + FOR_JOB_SELECT(p, pp, select, what) + MAPSET(multiversionmap, p); + } +} + +void +solver_calculate_noobsmap(Pool *pool, Queue *job, Map *multiversionmap) +{ + solver_calculate_multiversionmap(pool, job, multiversionmap); +} + +/* + * add a rule created by a job, record job number and weak flag + */ +static inline void +solver_addjobrule(Solver *solv, Id p, Id p2, Id d, Id job, int weak) +{ + solver_addrule(solv, p, p2, d); + queue_push(&solv->ruletojob, job); + if (weak) + queue_push(&solv->weakruleq, solv->nrules - 1); +} + +static inline void +add_cleandeps_package(Solver *solv, Id p) +{ + if (!solv->cleandeps_updatepkgs) + { + solv->cleandeps_updatepkgs = solv_calloc(1, sizeof(Queue)); + queue_init(solv->cleandeps_updatepkgs); + } + queue_pushunique(solv->cleandeps_updatepkgs, p); +} + +static void +add_update_target(Solver *solv, Id p, Id how) +{ + Pool *pool = solv->pool; + Solvable *s = pool->solvables + p; + Repo *installed = solv->installed; + Id pi, pip; + if (!solv->update_targets) + { + solv->update_targets = solv_calloc(1, sizeof(Queue)); + queue_init(solv->update_targets); + } + if (s->repo == installed) + { + queue_push2(solv->update_targets, p, p); + return; + } + FOR_PROVIDES(pi, pip, s->name) + { + Solvable *si = pool->solvables + pi; + if (si->repo != installed || si->name != s->name) + continue; + if (how & SOLVER_FORCEBEST) { - /* binary rule */ - if (r->p < 0 && decisionmap[-r->p] == 0 && DECISIONMAP_FALSE(r->w2)) - new = r->p; - else if (r->w2 < 0 && decisionmap[-r->w2] == 0 && DECISIONMAP_FALSE(r->p)) - new = r->w2; + if (!solv->bestupdatemap.size) + map_grow(&solv->bestupdatemap, installed->end - installed->start); + MAPSET(&solv->bestupdatemap, pi - installed->start); } - else + if (how & SOLVER_CLEANDEPS) + add_cleandeps_package(solv, pi); + queue_push2(solv->update_targets, pi, p); + /* check if it's ok to keep the installed package */ + if (s->evr == si->evr && solvable_identical(s, si)) + queue_push2(solv->update_targets, pi, pi); + } + if (s->obsoletes) + { + Id obs, *obsp = s->repo->idarraydata + s->obsoletes; + while ((obs = *obsp++) != 0) { - if (r->p < 0 && decisionmap[-r->p] == 0) - new = r->p; - if (new || DECISIONMAP_FALSE(r->p)) + FOR_PROVIDES(pi, pip, obs) { - dp = pool->whatprovidesdata + r->d; - while ((p = *dp++) != 0) + Solvable *si = pool->solvables + pi; + if (si->repo != installed) + continue; + if (si->name == s->name) + continue; /* already handled above */ + if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, si, obs)) + continue; + if (pool->obsoleteusescolors && !pool_colormatch(pool, s, si)) + continue; + if (how & SOLVER_FORCEBEST) { - 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 (!solv->bestupdatemap.size) + map_grow(&solv->bestupdatemap, installed->end - installed->start); + MAPSET(&solv->bestupdatemap, pi - installed->start); } + if (how & SOLVER_CLEANDEPS) + add_cleandeps_package(solv, pi); + queue_push2(solv->update_targets, pi, p); } } - if (new) + } +} + +static int +transform_update_targets_sortfn(const void *ap, const void *bp, void *dp) +{ + const Id *a = ap; + const Id *b = bp; + if (a[0] - b[0]) + return a[0] - b[0]; + return a[1] - b[1]; +} + +static void +transform_update_targets(Solver *solv) +{ + Repo *installed = solv->installed; + Queue *update_targets = solv->update_targets; + int i, j; + Id p, q, lastp, lastq; + + if (!update_targets->count) + { + queue_free(update_targets); + solv->update_targets = solv_free(update_targets); + return; + } + if (update_targets->count > 2) + solv_sort(update_targets->elements, update_targets->count >> 1, 2 * sizeof(Id), transform_update_targets_sortfn, solv); + queue_insertn(update_targets, 0, installed->end - installed->start, 0); + lastp = lastq = 0; + for (i = j = installed->end - installed->start; i < update_targets->count; i += 2) + { + if ((p = update_targets->elements[i]) != lastp) { - POOL_DEBUG(SAT_DEBUG_SCHUBI, "re-conflicting package %s[%d]\n", solvable2str(pool, pool->solvables - new), -new); - decisionmap[-new] = -1; - new = 0; - n = 0; /* redo all rules */ + if (!solv->updatemap.size) + map_grow(&solv->updatemap, installed->end - installed->start); + MAPSET(&solv->updatemap, p - installed->start); + update_targets->elements[j++] = 0; /* finish old set */ + update_targets->elements[p - installed->start] = j; /* start new set */ + lastp = p; + lastq = 0; + } + if ((q = update_targets->elements[i + 1]) != lastq) + { + update_targets->elements[j++] = q; + lastq = q; } } + queue_truncate(update_targets, j); + queue_push(update_targets, 0); /* finish last set */ } -/*------------------------------------------------------------------- - * - * weaken solvable dependencies - */ - static void -weaken_solvable_deps(Solver *solv, Id p) +addedmap2deduceq(Solver *solv, Map *addedmap) { - int i; + Pool *pool = solv->pool; + int i, j; + Id p; Rule *r; - for (i = 1, r = solv->rules + i; i < solv->rpmrules_end; i++, r++) + queue_empty(&solv->addedmap_deduceq); + for (i = 2, j = solv->pkgrules_end - 1; i < pool->nsolvables && j > 0; j--) { - if (r->p != -p) + r = solv->rules + j; + if (r->p >= 0) continue; if ((r->d == 0 || r->d == -1) && r->w2 < 0) - continue; /* conflict */ - queue_push(&solv->weakruleq, i); + continue; + p = -r->p; + if (!MAPTST(addedmap, p)) + { + /* should never happen, but... */ + if (!solv->addedmap_deduceq.count || solv->addedmap_deduceq.elements[solv->addedmap_deduceq.count - 1] != -p) + queue_push(&solv->addedmap_deduceq, -p); + continue; + } + for (; i < p; i++) + if (MAPTST(addedmap, i)) + queue_push(&solv->addedmap_deduceq, i); + if (i == p) + i++; } + for (; i < pool->nsolvables; i++) + if (MAPTST(addedmap, i)) + queue_push(&solv->addedmap_deduceq, i); + j = 0; + for (i = 2; i < pool->nsolvables; i++) + if (MAPTST(addedmap, i)) + j++; } -/********************************************************************/ -/* main() */ +static void +deduceq2addedmap(Solver *solv, Map *addedmap) +{ + int j; + Id p; + Rule *r; + for (j = solv->pkgrules_end - 1; j > 0; j--) + { + r = solv->rules + j; + if (r->d < 0 && r->p) + solver_enablerule(solv, r); + if (r->p >= 0) + continue; + if ((r->d == 0 || r->d == -1) && r->w2 < 0) + continue; + p = -r->p; + MAPSET(addedmap, p); + } + for (j = 0; j < solv->addedmap_deduceq.count; j++) + { + p = solv->addedmap_deduceq.elements[j]; + if (p > 0) + MAPSET(addedmap, p); + else + MAPCLR(addedmap, p); + } +} + +#ifdef ENABLE_COMPLEX_DEPS +static int +add_complex_jobrules(Solver *solv, Id dep, int flags, int jobidx, int weak) +{ + Pool *pool = solv->pool; + Queue bq; + int i, j; + + queue_init(&bq); + i = pool_normalize_complex_dep(pool, dep, &bq, flags | CPLXDEPS_EXPAND); + if (i == 0 || i == 1) + { + queue_free(&bq); + if (i == 0) + solver_addjobrule(solv, -SYSTEMSOLVABLE, 0, 0, jobidx, weak); + return 0; + } + for (i = 0; i < bq.count; i++) + { + if (!bq.elements[i]) + continue; + for (j = 0; bq.elements[i + j + 1]; j++) + ; + if (j > 1) + solver_addjobrule(solv, bq.elements[i], 0, pool_ids2whatprovides(pool, bq.elements + i + 1, j), jobidx, weak); + else + solver_addjobrule(solv, bq.elements[i], bq.elements[i + 1], 0, jobidx, weak); + i += j + 1; + } + queue_free(&bq); + return 1; +} +#endif /* * @@ -3958,95 +3273,252 @@ weaken_solvable_deps(Solver *solv, Id p) * */ -void +int solver_solve(Solver *solv, Queue *job) { Pool *pool = solv->pool; Repo *installed = solv->installed; int i; - int oldnrules; - Map addedmap; /* '1' == have rpm-rules for solvable */ + int oldnrules, initialnrules; + Map addedmap; /* '1' == have pkg-rules for solvable */ Map installcandidatemap; Id how, what, select, name, weak, p, pp, d; - Queue q, redoq; + Queue q; Solvable *s; - int goterase; Rule *r; int now, solve_start; + int hasdupjob = 0; + int hasbestinstalljob = 0; + + solve_start = solv_timems(0); + + /* log solver options */ + POOL_DEBUG(SOLV_DEBUG_STATS, "solver started\n"); + POOL_DEBUG(SOLV_DEBUG_STATS, "dosplitprovides=%d, noupdateprovide=%d, noinfarchcheck=%d\n", solv->dosplitprovides, solv->noupdateprovide, solv->noinfarchcheck); + POOL_DEBUG(SOLV_DEBUG_STATS, "allowuninstall=%d, allowdowngrade=%d, allownamechange=%d, allowarchchange=%d, allowvendorchange=%d\n", solv->allowuninstall, solv->allowdowngrade, solv->allownamechange, solv->allowarchchange, solv->allowvendorchange); + POOL_DEBUG(SOLV_DEBUG_STATS, "promoteepoch=%d, forbidselfconflicts=%d\n", pool->promoteepoch, pool->forbidselfconflicts); + POOL_DEBUG(SOLV_DEBUG_STATS, "obsoleteusesprovides=%d, implicitobsoleteusesprovides=%d, obsoleteusescolors=%d, implicitobsoleteusescolors=%d\n", pool->obsoleteusesprovides, pool->implicitobsoleteusesprovides, pool->obsoleteusescolors, pool->implicitobsoleteusescolors); + POOL_DEBUG(SOLV_DEBUG_STATS, "dontinstallrecommended=%d, addalreadyrecommended=%d\n", solv->dontinstallrecommended, solv->addalreadyrecommended); - solve_start = sat_timems(0); - POOL_DEBUG(SAT_DEBUG_STATS, "solver started\n"); - POOL_DEBUG(SAT_DEBUG_STATS, "fixsystem=%d updatesystem=%d dosplitprovides=%d, noupdateprovide=%d\n", solv->fixsystem, solv->updatesystem, solv->dosplitprovides, solv->noupdateprovide); - 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 */ - create_obsolete_index(solv); + /* create obsolete index */ + policy_create_obsolete_index(solv); + + /* remember job */ + queue_free(&solv->job); + queue_init_clone(&solv->job, job); + solv->pooljobcnt = pool->pooljobs.count; + if (pool->pooljobs.count) + queue_insertn(&solv->job, 0, pool->pooljobs.count, pool->pooljobs.elements); + job = &solv->job; + + /* free old stuff in jase we re-run a solver */ + queuep_free(&solv->update_targets); + queuep_free(&solv->cleandeps_updatepkgs); + queue_empty(&solv->ruleassertions); + solv->bestrules_pkg = solv_free(solv->bestrules_pkg); + solv->yumobsrules_info = solv_free(solv->yumobsrules_info); + solv->choicerules_ref = solv_free(solv->choicerules_ref); + if (solv->noupdate.size) + map_empty(&solv->noupdate); + map_zerosize(&solv->multiversion); + solv->updatemap_all = 0; + map_zerosize(&solv->updatemap); + solv->bestupdatemap_all = 0; + map_zerosize(&solv->bestupdatemap); + solv->fixmap_all = 0; + map_zerosize(&solv->fixmap); + solv->dupmap_all = 0; + map_zerosize(&solv->dupmap); + map_zerosize(&solv->dupinvolvedmap); + solv->droporphanedmap_all = 0; + map_zerosize(&solv->droporphanedmap); + map_zerosize(&solv->cleandepsmap); + map_zerosize(&solv->weakrulemap); + queue_empty(&solv->weakruleq); + solv->watches = solv_free(solv->watches); + queue_empty(&solv->ruletojob); + if (solv->decisionq.count) + memset(solv->decisionmap, 0, pool->nsolvables * sizeof(Id)); + queue_empty(&solv->decisionq); + queue_empty(&solv->decisionq_why); + solv->decisioncnt_jobs = solv->decisioncnt_update = solv->decisioncnt_keep = solv->decisioncnt_resolve = solv->decisioncnt_weak = solv->decisioncnt_orphan = 0; + queue_empty(&solv->learnt_why); + queue_empty(&solv->learnt_pool); + queue_empty(&solv->branches); + solv->propagate_index = 0; + queue_empty(&solv->problems); + queue_empty(&solv->solutions); + queue_empty(&solv->orphaned); + solv->stats_learned = solv->stats_unsolvable = 0; + if (solv->recommends_index) + { + map_empty(&solv->recommendsmap); + map_empty(&solv->suggestsmap); + queuep_free(&solv->recommendscplxq); + queuep_free(&solv->suggestscplxq); + solv->recommends_index = 0; + } + queuep_free(&solv->brokenorphanrules); + solv->specialupdaters = solv_free(solv->specialupdaters); + /* * create basic rule set of all involved packages * use addedmap bitmap to make sure we don't create rules twice - * */ - /* create noobsolete map if needed */ - for (i = 0; i < job->count; i += 2) - { - how = job->elements[i] & ~SOLVER_WEAK; - 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); - } + /* create multiversion map if needed */ + solver_calculate_multiversionmap(pool, job, &solv->multiversion); map_init(&addedmap, pool->nsolvables); + MAPSET(&addedmap, SYSTEMSOLVABLE); + map_init(&installcandidatemap, pool->nsolvables); queue_init(&q); - /* - * always install our system solvable - */ - MAPSET(&addedmap, SYSTEMSOLVABLE); - queue_push(&solv->decisionq, SYSTEMSOLVABLE); - queue_push(&solv->decisionq_why, 0); - solv->decisionmap[SYSTEMSOLVABLE] = 1; /* installed at level '1' */ - - now = sat_timems(0); + now = solv_timems(0); /* * create rules for all package that could be involved with the solving - * so called: rpm rules + * so called: pkg rules * */ + initialnrules = solv->pkgrules_end ? solv->pkgrules_end : 1; + if (initialnrules > 1) + deduceq2addedmap(solv, &addedmap); + if (solv->nrules != initialnrules) + solver_shrinkrules(solv, initialnrules); + solv->nrules = initialnrules; + solv->pkgrules_end = 0; + if (installed) { + /* check for update/verify jobs as they need to be known early */ + /* also setup the droporphaned map, we need it when creating update rules */ + for (i = 0; i < job->count; i += 2) + { + how = job->elements[i]; + what = job->elements[i + 1]; + select = how & SOLVER_SELECTMASK; + switch (how & SOLVER_JOBMASK) + { + case SOLVER_VERIFY: + if (select == SOLVER_SOLVABLE_ALL || (select == SOLVER_SOLVABLE_REPO && installed && what == installed->repoid)) + solv->fixmap_all = 1; + FOR_JOB_SELECT(p, pp, select, what) + { + s = pool->solvables + p; + if (s->repo != installed) + continue; + if (!solv->fixmap.size) + map_grow(&solv->fixmap, installed->end - installed->start); + MAPSET(&solv->fixmap, p - installed->start); + } + break; + case SOLVER_UPDATE: + if (select == SOLVER_SOLVABLE_ALL) + { + solv->updatemap_all = 1; + if (how & SOLVER_FORCEBEST) + solv->bestupdatemap_all = 1; + if (how & SOLVER_CLEANDEPS) + { + FOR_REPO_SOLVABLES(installed, p, s) + add_cleandeps_package(solv, p); + } + } + else if (select == SOLVER_SOLVABLE_REPO) + { + Repo *repo = pool_id2repo(pool, what); + if (!repo) + break; + if (repo == installed && !(how & SOLVER_TARGETED)) + { + solv->updatemap_all = 1; + if (how & SOLVER_FORCEBEST) + solv->bestupdatemap_all = 1; + if (how & SOLVER_CLEANDEPS) + { + FOR_REPO_SOLVABLES(installed, p, s) + add_cleandeps_package(solv, p); + } + break; + } + if (solv->noautotarget && !(how & SOLVER_TARGETED)) + break; + /* targeted update */ + FOR_REPO_SOLVABLES(repo, p, s) + add_update_target(solv, p, how); + } + else + { + if (!(how & SOLVER_TARGETED)) + { + int targeted = 1; + FOR_JOB_SELECT(p, pp, select, what) + { + s = pool->solvables + p; + if (s->repo != installed) + continue; + if (!solv->updatemap.size) + map_grow(&solv->updatemap, installed->end - installed->start); + MAPSET(&solv->updatemap, p - installed->start); + if (how & SOLVER_FORCEBEST) + { + if (!solv->bestupdatemap.size) + map_grow(&solv->bestupdatemap, installed->end - installed->start); + MAPSET(&solv->bestupdatemap, p - installed->start); + } + if (how & SOLVER_CLEANDEPS) + add_cleandeps_package(solv, p); + targeted = 0; + } + if (!targeted || solv->noautotarget) + break; + } + FOR_JOB_SELECT(p, pp, select, what) + add_update_target(solv, p, how); + } + break; + case SOLVER_DROP_ORPHANED: + if (select == SOLVER_SOLVABLE_ALL || (select == SOLVER_SOLVABLE_REPO && what == installed->repoid)) + solv->droporphanedmap_all = 1; + FOR_JOB_SELECT(p, pp, select, what) + { + s = pool->solvables + p; + if (s->repo != installed) + continue; + if (!solv->droporphanedmap.size) + map_grow(&solv->droporphanedmap, installed->end - installed->start); + MAPSET(&solv->droporphanedmap, p - installed->start); + } + break; + default: + break; + } + } + + if (solv->update_targets) + transform_update_targets(solv); + 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); - 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"); + solver_addpkgrulesforsolvable(solv, s, &addedmap); + POOL_DEBUG(SOLV_DEBUG_STATS, "added %d pkg rules for installed solvables\n", solv->nrules - oldnrules); oldnrules = solv->nrules; FOR_REPO_SOLVABLES(installed, p, s) - addrpmrulesforupdaters(solv, s, &addedmap, 1); - POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for updaters of installed solvables\n", solv->nrules - oldnrules); + solver_addpkgrulesforupdaters(solv, s, &addedmap, 1); + POOL_DEBUG(SOLV_DEBUG_STATS, "added %d pkg 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) { @@ -4060,29 +3532,49 @@ solver_solve(Solver *solv, Queue *job) FOR_JOB_SELECT(p, pp, select, what) { MAPSET(&installcandidatemap, p); - addrpmrulesforsolvable(solv, pool->solvables + p, &addedmap); + solver_addpkgrulesforsolvable(solv, pool->solvables + p, &addedmap); } break; - case SOLVER_UPDATE: - /* FIXME: semantics? */ - FOR_JOB_SELECT(p, pp, select, what) - addrpmrulesforupdaters(solv, pool->solvables + what, &addedmap, 0); + case SOLVER_DISTUPGRADE: + if (select == SOLVER_SOLVABLE_ALL) + { + solv->dupmap_all = 1; + solv->updatemap_all = 1; + if (how & SOLVER_FORCEBEST) + solv->bestupdatemap_all = 1; + } + if (!solv->dupmap_all || solv->allowuninstall) + hasdupjob = 1; + break; + default: break; } } - POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for packages involved in a job\n", solv->nrules - oldnrules); + POOL_DEBUG(SOLV_DEBUG_STATS, "added %d pkg 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 + */ + oldnrules = solv->nrules; + solver_addpkgrulesforweak(solv, &addedmap); + POOL_DEBUG(SOLV_DEBUG_STATS, "added %d pkg rules because of weak dependencies\n", solv->nrules - oldnrules); + +#ifdef ENABLE_LINKED_PKGS oldnrules = solv->nrules; - - /* - * add rules for suggests, enhances - */ - addrpmrulesforweak(solv, &addedmap); - POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules because of weak dependencies\n", solv->nrules - oldnrules); + solver_addpkgrulesforlinked(solv, &addedmap); + POOL_DEBUG(SOLV_DEBUG_STATS, "added %d pkg rules because of linked packages\n", solv->nrules - oldnrules); +#endif + + /* + * first pass done, we now have all the pkg 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) + IF_POOLDEBUG (SOLV_DEBUG_STATS) { int possible = 0, installable = 0; for (i = 1; i < pool->nsolvables; i++) @@ -4092,69 +3584,61 @@ solver_solve(Solver *solv, Queue *job) if (MAPTST(&addedmap, i)) possible++; } - POOL_DEBUG(SAT_DEBUG_STATS, "%d of %d installable solvables considered for solving\n", possible, installable); + POOL_DEBUG(SOLV_DEBUG_STATS, "%d of %d installable solvables considered for solving\n", possible, installable); } - /* - * 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 (solv->nrules > initialnrules) + solver_unifyrules(solv); /* remove duplicate pkg rules */ + solv->pkgrules_end = solv->nrules; /* mark end of pkg rules */ - unifyrules(solv); /* remove duplicate rpm rules */ + if (solv->nrules > initialnrules) + addedmap2deduceq(solv, &addedmap); /* so that we can recreate the addedmap */ - solv->rpmrules_end = solv->nrules; /* mark end of rpm rules */ + POOL_DEBUG(SOLV_DEBUG_STATS, "pkg rule memory used: %d K\n", solv->nrules * (int)sizeof(Rule) / 1024); + POOL_DEBUG(SOLV_DEBUG_STATS, "pkg rule creation took %d ms\n", solv_timems(now)); - solv->directdecisions = solv->decisionq.count; - POOL_DEBUG(SAT_DEBUG_STATS, "rpm rule memory usage: %d K\n", solv->nrules * (int)sizeof(Rule) / 1024); - POOL_DEBUG(SAT_DEBUG_STATS, "decisions so far: %d\n", solv->decisionq.count); - 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); /* * 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 */ + /* foreach possibly installed solvable */ for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++) { if (s->repo != installed) { - addrule(solv, 0, 0); /* create dummy rule */ + solver_addrule(solv, 0, 0, 0); /* create dummy rule */ continue; } - addupdaterule(solv, s, 1); /* allow s to be updated */ + solver_addupdaterule(solv, s, 1); /* allow s to be updated */ } - /* - * assert one rule per installed solvable, - * either an assertion (A) - * or a possible update (A|update1(A)|update2(A)|...) - */ + /* 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; if (installed) @@ -4166,48 +3650,24 @@ solver_solve(Solver *solv, Queue *job) if (s->repo != installed) { - addrule(solv, 0, 0); /* create dummy rule */ + solver_addrule(solv, 0, 0, 0); /* create dummy rule */ continue; } - addupdaterule(solv, s, 0); /* allowall = 0: downgrades not allowed */ - /* - * check for and remove duplicate - */ + solver_addupdaterule(solv, s, 0); /* allowall = 0: downgrades not allowed */ + /* + * check for and remove duplicate + */ r = solv->rules + solv->nrules - 1; /* r: update rule */ + if (!r->p) + continue; 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)) + /* it's also orphaned if the feature rule consists just of the installed package */ + if (!solv->dupmap_all && sr->p == i && !sr->d && !sr->w2) queue_push(&solv->orphaned, i); - if (!r->p) - { - assert(!sr->p); /* can't have feature rule and no update rule */ - continue; - } - unifyrules_sortcmp_data = pool; - if (!unifyrules_sortcmp(r, sr)) - { - /* identical rule, kill unneeded rule */ - 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); - } + if (!solver_rulecmp(solv, r, sr)) + memset(sr, 0, sizeof(*sr)); /* delete unneeded feature rule */ else - disablerule(solv, sr); + solver_disablerule(solv, sr); /* disable feature rule for now */ } /* consistency check: we added a rule for _every_ installed solvable */ assert(solv->nrules - solv->updaterules == installed->end - installed->start); @@ -4219,13 +3679,13 @@ solver_solve(Solver *solv, Queue *job) * now add all job rules */ - POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** Add JOB rules ***\n"); - solv->jobrules = solv->nrules; for (i = 0; i < job->count; i += 2) { oldnrules = solv->nrules; + if (i && i == solv->pooljobcnt) + POOL_DEBUG(SOLV_DEBUG_JOB, "end of pool jobs\n"); how = job->elements[i]; what = job->elements[i + 1]; weak = how & SOLVER_WEAK; @@ -4233,12 +3693,23 @@ solver_solve(Solver *solv, Queue *job) switch (how & SOLVER_JOBMASK) { case SOLVER_INSTALL: - POOL_DEBUG(SAT_DEBUG_JOB, "job: %sinstall %s\n", weak ? "weak " : "", solver_select2str(solv, select, what)); + POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sinstall %s\n", weak ? "weak " : "", solver_select2str(pool, select, what)); + if ((how & SOLVER_CLEANDEPS) != 0 && !solv->cleandepsmap.size && installed) + map_grow(&solv->cleandepsmap, installed->end - installed->start); if (select == SOLVER_SOLVABLE) { p = what; d = 0; } +#ifdef ENABLE_COMPLEX_DEPS + else if ((select == SOLVER_SOLVABLE_PROVIDES || select == SOLVER_SOLVABLE_NAME) && pool_is_complex_dep(pool, what)) + { + if (add_complex_jobrules(solv, what, select == SOLVER_SOLVABLE_NAME ? CPLXDEPS_NAME : 0, i, weak)) + if (how & SOLVER_FORCEBEST) + hasbestinstalljob = 1; + break; + } +#endif else { queue_empty(&q); @@ -4246,133 +3717,244 @@ solver_solve(Solver *solv, Queue *job) queue_push(&q, p); if (!q.count) { - /* no candidate found, make this an impossible rule */ + if (select == SOLVER_SOLVABLE_ONE_OF) + break; /* ignore empty installs */ + /* no candidate found or unsupported, 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 */ } - addrule(solv, p, d); /* add install rule */ - queue_push(&solv->ruletojob, i); - if (weak) - queue_push(&solv->weakruleq, solv->nrules - 1); + /* force install of namespace supplements hack */ + if (select == SOLVER_SOLVABLE_PROVIDES && !d && (p == SYSTEMSOLVABLE || p == -SYSTEMSOLVABLE) && ISRELDEP(what)) + { + Reldep *rd = GETRELDEP(pool, what); + if (rd->flags == REL_NAMESPACE) + { + p = SYSTEMSOLVABLE; + if (!solv->installsuppdepq) + { + solv->installsuppdepq = solv_calloc(1, sizeof(Queue)); + queue_init(solv->installsuppdepq); + } + queue_pushunique(solv->installsuppdepq, rd->evr == 0 ? rd->name : what); + } + } + solver_addjobrule(solv, p, 0, d, i, weak); + if (how & SOLVER_FORCEBEST) + hasbestinstalljob = 1; break; 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) + POOL_DEBUG(SOLV_DEBUG_JOB, "job: %s%serase %s\n", weak ? "weak " : "", how & SOLVER_CLEANDEPS ? "clean deps " : "", solver_select2str(pool, select, what)); + if ((how & SOLVER_CLEANDEPS) != 0 && !solv->cleandepsmap.size && installed) + map_grow(&solv->cleandepsmap, installed->end - installed->start); + /* specific solvable: by id or by nevra */ + name = (select == SOLVER_SOLVABLE || (select == SOLVER_SOLVABLE_NAME && ISRELDEP(what))) ? 0 : -1; + if (select == SOLVER_SOLVABLE_ALL) /* hmmm ;) */ + { + FOR_POOL_SOLVABLES(p) + solver_addjobrule(solv, -p, 0, 0, i, weak); + } + else if (select == SOLVER_SOLVABLE_REPO) + { + Repo *repo = pool_id2repo(pool, what); + if (repo) + FOR_REPO_SOLVABLES(repo, p, s) + solver_addjobrule(solv, -p, 0, 0, i, weak); + } +#ifdef ENABLE_COMPLEX_DEPS + else if ((select == SOLVER_SOLVABLE_PROVIDES || select == SOLVER_SOLVABLE_NAME) && pool_is_complex_dep(pool, what)) + { + /* no special "erase a specific solvable" handling? */ + add_complex_jobrules(solv, what, select == SOLVER_SOLVABLE_NAME ? (CPLXDEPS_NAME | CPLXDEPS_TODNF | CPLXDEPS_INVERT) : (CPLXDEPS_TODNF | CPLXDEPS_INVERT), i, weak); + break; + } +#endif + FOR_JOB_SELECT(p, pp, select, what) + { + s = pool->solvables + p; + if (installed && s->repo == installed) + name = !name ? s->name : -1; + solver_addjobrule(solv, -p, 0, 0, i, weak); + } + /* 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 is > 0 if exactly one installed solvable matched. + */ + /* XXX: look also at packages that obsolete this package? */ + if (name > 0) { - /* 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; + int j, k; + k = solv->nrules; 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) + if (s->repo == installed) continue; /* keep installcandidates of other jobs */ if (MAPTST(&installcandidatemap, p)) continue; - addrule(solv, -p, 0); /* remove by Id */ - queue_push(&solv->ruletojob, i); - if (weak) - queue_push(&solv->weakruleq, solv->nrules - 1); + /* don't add the same rule twice */ + for (j = oldnrules; j < k; j++) + if (solv->rules[j].p == -p) + break; + if (j == k) + solver_addjobrule(solv, -p, 0, 0, i, weak); /* remove by id */ } } - FOR_JOB_SELECT(p, pp, select, what) - { - addrule(solv, -p, 0); - queue_push(&solv->ruletojob, i); - if (weak) - queue_push(&solv->weakruleq, solv->nrules - 1); - } break; case SOLVER_UPDATE: - POOL_DEBUG(SAT_DEBUG_JOB, "job: %supdate %s\n", weak ? "weak " : "", solver_select2str(solv, select, what)); - if (select != SOLVER_SOLVABLE) - break; - 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); + POOL_DEBUG(SOLV_DEBUG_JOB, "job: %supdate %s\n", weak ? "weak " : "", solver_select2str(pool, select, what)); + break; + case SOLVER_VERIFY: + POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sverify %s\n", weak ? "weak " : "", solver_select2str(pool, select, what)); break; case SOLVER_WEAKENDEPS: - POOL_DEBUG(SAT_DEBUG_JOB, "job: %sweaken deps %s\n", weak ? "weak " : "", solver_select2str(solv, select, what)); + POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sweaken deps %s\n", weak ? "weak " : "", solver_select2str(pool, select, what)); if (select != SOLVER_SOLVABLE) break; s = pool->solvables + what; weaken_solvable_deps(solv, what); break; - case SOLVER_NOOBSOLETES: - POOL_DEBUG(SAT_DEBUG_JOB, "job: %sno obsolete %s\n", weak ? "weak " : "", solver_select2str(solv, select, what)); + case SOLVER_MULTIVERSION: + POOL_DEBUG(SOLV_DEBUG_JOB, "job: %smultiversion %s\n", weak ? "weak " : "", solver_select2str(pool, 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) + POOL_DEBUG(SOLV_DEBUG_JOB, "job: %slock %s\n", weak ? "weak " : "", solver_select2str(pool, select, what)); + if (select == SOLVER_SOLVABLE_ALL) { - s = pool->solvables + p; - if (installed && s->repo == installed) - addrule(solv, p, 0); - else - addrule(solv, -p, 0); - queue_push(&solv->ruletojob, i); - if (weak) - queue_push(&solv->weakruleq, solv->nrules - 1); + FOR_POOL_SOLVABLES(p) + solver_addjobrule(solv, installed && pool->solvables[p].repo == installed ? p : -p, 0, 0, i, weak); } + else if (select == SOLVER_SOLVABLE_REPO) + { + Repo *repo = pool_id2repo(pool, what); + if (repo) + FOR_REPO_SOLVABLES(repo, p, s) + solver_addjobrule(solv, installed && pool->solvables[p].repo == installed ? p : -p, 0, 0, i, weak); + } + FOR_JOB_SELECT(p, pp, select, what) + solver_addjobrule(solv, installed && pool->solvables[p].repo == installed ? p : -p, 0, 0, i, weak); + break; + case SOLVER_DISTUPGRADE: + POOL_DEBUG(SOLV_DEBUG_JOB, "job: distupgrade %s\n", solver_select2str(pool, select, what)); + break; + case SOLVER_DROP_ORPHANED: + POOL_DEBUG(SOLV_DEBUG_JOB, "job: drop orphaned %s\n", solver_select2str(pool, select, what)); + break; + case SOLVER_USERINSTALLED: + POOL_DEBUG(SOLV_DEBUG_JOB, "job: user installed %s\n", solver_select2str(pool, select, what)); break; default: - POOL_DEBUG(SAT_DEBUG_JOB, "job: unknown job\n"); + POOL_DEBUG(SOLV_DEBUG_JOB, "job: unknown job\n"); break; } - /* - * debug - */ - - IF_POOLDEBUG (SAT_DEBUG_JOB) + IF_POOLDEBUG (SOLV_DEBUG_JOB) { int j; if (solv->nrules == oldnrules) - POOL_DEBUG(SAT_DEBUG_JOB, " - no rule created\n"); + POOL_DEBUG(SOLV_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); + POOL_DEBUG(SOLV_DEBUG_JOB, " - job "); + solver_printrule(solv, SOLV_DEBUG_JOB, solv->rules + j); } } } assert(solv->ruletojob.count == solv->nrules - solv->jobrules); solv->jobrules_end = solv->nrules; - /* all rules created - * -------------------------------------------------------------- - * prepare for solving - */ - + /* now create infarch and dup rules */ + if (!solv->noinfarchcheck) + { + solver_addinfarchrules(solv, &addedmap); +#if 0 + if (pool->implicitobsoleteusescolors) + { + /* currently doesn't work well with infarch rules, so make + * them weak */ + for (i = solv->infarchrules; i < solv->infarchrules_end; i++) + queue_push(&solv->weakruleq, i); + } +#endif + } + else + solv->infarchrules = solv->infarchrules_end = solv->nrules; + + if (hasdupjob) + solver_addduprules(solv, &addedmap); + else + solv->duprules = solv->duprules_end = solv->nrules; + + if (solv->bestupdatemap_all || solv->bestupdatemap.size || hasbestinstalljob) + solver_addbestrules(solv, hasbestinstalljob); + else + solv->bestrules = solv->bestrules_end = solv->nrules; + + if (hasdupjob) + solver_freedupmaps(solv); /* no longer needed */ + + if (solv->do_yum_obsoletes) + solver_addyumobsrules(solv); + else + solv->yumobsrules = solv->yumobsrules_end = solv->nrules; + + if (1) + solver_addchoicerules(solv); + else + solv->choicerules = solv->choicerules_end = solv->nrules; + + if (0) + { + for (i = solv->featurerules; i < solv->nrules; i++) + solver_printruleclass(solv, SOLV_DEBUG_RESULT, solv->rules + i); + } + /* all rules created + * -------------------------------------------------------------- + * prepare for solving + */ + /* free unneeded memory */ map_free(&addedmap); map_free(&installcandidatemap); queue_free(&q); + POOL_DEBUG(SOLV_DEBUG_STATS, "%d pkg rules, 2 * %d update rules, %d job rules, %d infarch rules, %d dup rules, %d choice rules, %d best rules\n", solv->pkgrules_end - 1, solv->updaterules_end - solv->updaterules, solv->jobrules_end - solv->jobrules, solv->infarchrules_end - solv->infarchrules, solv->duprules_end - solv->duprules, solv->choicerules_end - solv->choicerules, solv->bestrules_end - solv->bestrules); + POOL_DEBUG(SOLV_DEBUG_STATS, "overall rule memory used: %d K\n", solv->nrules * (int)sizeof(Rule) / 1024); + /* create weak map */ - map_init(&solv->weakrulemap, solv->nrules); - for (i = 0; i < solv->weakruleq.count; i++) + if (solv->weakruleq.count) + { + map_grow(&solv->weakrulemap, solv->nrules); + for (i = 0; i < solv->weakruleq.count; i++) + { + p = solv->weakruleq.elements[i]; + MAPSET(&solv->weakrulemap, p); + } + } + + /* enable cleandepsmap creation if we have updatepkgs */ + if (solv->cleandeps_updatepkgs && !solv->cleandepsmap.size) + map_grow(&solv->cleandepsmap, installed->end - installed->start); + /* no mistakes */ + if (solv->cleandeps_mistakes) { - p = solv->weakruleq.elements[i]; - MAPSET(&solv->weakrulemap, p); + queue_free(solv->cleandeps_mistakes); + solv->cleandeps_mistakes = solv_free(solv->cleandeps_mistakes); } /* all new rules are learnt after this point */ solv->learntrules = solv->nrules; + /* 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++) @@ -4380,39 +3962,94 @@ solver_solve(Solver *solv, Queue *job) queue_push(&solv->ruleassertions, i); /* disable update rules that conflict with our job */ - disableupdaterules(solv, job, -1); - - /* make decisions based on job/update assertions */ - makeruledecisions(solv); + solver_disablepolicyrules(solv); - /* create watches chains */ - makewatches(solv); - - POOL_DEBUG(SAT_DEBUG_STATS, "problems so far: %d\n", solv->problems.count); + /* break orphans if requested */ + if (solv->dupmap_all && solv->orphaned.count && solv->break_orphans) + solver_breakorphans(solv); /* * ******************************************** * solve! * ******************************************** */ - - now = sat_timems(0); - run_solver(solv, 1, solv->dontinstallrecommended ? 0 : 1); - POOL_DEBUG(SAT_DEBUG_STATS, "solver took %d ms\n", sat_timems(now)); + + now = solv_timems(0); + solver_run_sat(solv, 1, solv->dontinstallrecommended ? 0 : 1); + POOL_DEBUG(SOLV_DEBUG_STATS, "solver took %d ms\n", solv_timems(now)); + + /* + * prepare solution queue if there were problems + */ + solver_prepare_solutions(solv); + + POOL_DEBUG(SOLV_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(SOLV_DEBUG_STATS, "solver_solve took %d ms\n", solv_timems(solve_start)); + + /* return number of problems */ + return solv->problems.count ? solv->problems.count / 2 : 0; +} + +Transaction * +solver_create_transaction(Solver *solv) +{ + return transaction_create_decisionq(solv->pool, &solv->decisionq, &solv->multiversion); +} + +void solver_get_orphaned(Solver *solv, Queue *orphanedq) +{ + queue_free(orphanedq); + queue_init_clone(orphanedq, &solv->orphaned); +} + +void solver_get_recommendations(Solver *solv, Queue *recommendationsq, Queue *suggestionsq, int noselected) +{ + Pool *pool = solv->pool; + Queue redoq, disabledq; + int goterase, i; + Solvable *s; + Rule *r; + Map obsmap; + + if (!recommendationsq && !suggestionsq) + return; + + 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->multiversion.size && MAPTST(&solv->multiversion, 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->learntrules; i++, r++) + 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? */ + if (r->p >= 0) /* install job? */ continue; - disablerule(solv, r); + queue_push(&disabledq, i); + solver_disablerule(solv, r); goterase++; } - + if (goterase) { enabledisablelearntrules(solv); @@ -4422,16 +4059,31 @@ solver_solve(Solver *solv, Queue *job) /* * 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) + if (recommendationsq) { Id rec, *recp, p, pp; + queue_empty(recommendationsq); /* create map of all recommened packages */ solv->recommends_index = -1; MAPZERO(&solv->recommendsmap); + + /* put all packages the solver already chose in the map */ + if (solv->decisioncnt_weak) + { + for (i = solv->decisioncnt_weak; i < solv->decisioncnt_orphan; i++) + { + Id why; + why = solv->decisionq_why.elements[i]; + if (why) + continue; /* forced by unit rule or dep resolving */ + p = solv->decisionq.elements[i]; + if (p < 0) + continue; + MAPSET(&solv->recommendsmap, p); + } + } + for (i = 0; i < solv->decisionq.count; i++) { p = solv->decisionq.elements[i]; @@ -4443,12 +4095,19 @@ solver_solve(Solver *solv, Queue *job) recp = s->repo->idarraydata + s->recommends; while ((rec = *recp++) != 0) { +#ifdef ENABLE_COMPLEX_DEPS + if (pool_is_complex_dep(pool, rec)) + { + do_complex_recommendations(solv, rec, &solv->recommendsmap, noselected); + continue; + } +#endif FOR_PROVIDES(p, pp, rec) if (solv->decisionmap[p] > 0) break; if (p) { - if (!solv->dontshowinstalledrecommended) + if (!noselected) { FOR_PROVIDES(p, pp, rec) if (solv->decisionmap[p] > 0) @@ -4465,7 +4124,9 @@ solver_solve(Solver *solv, Queue *job) { if (solv->decisionmap[i] < 0) continue; - if (solv->decisionmap[i] > 0 && solv->dontshowinstalledrecommended) + if (solv->decisionmap[i] > 0 && noselected) + continue; + if (MAPTST(&obsmap, i)) continue; s = pool->solvables + i; if (!MAPTST(&solv->recommendsmap, i)) @@ -4477,23 +4138,21 @@ solver_solve(Solver *solv, Queue *job) if (!solver_is_supplementing(solv, s)) continue; } - if (solv->dontinstallrecommended) - queue_push(&solv->recommendations, i); - else - queue_pushunique(&solv->recommendations, i); + queue_push(recommendationsq, i); } /* we use MODE_SUGGEST here so that repo prio is ignored */ - policy_filter_unwanted(solv, &solv->recommendations, 0, POLICY_MODE_SUGGEST); + policy_filter_unwanted(solv, recommendationsq, POLICY_MODE_SUGGEST); } /* * find suggested packages */ - - if (1) + + if (suggestionsq) { Id sug, *sugp, p, pp; + queue_empty(suggestionsq); /* create map of all suggests that are still open */ solv->recommends_index = -1; MAPZERO(&solv->suggestsmap); @@ -4508,12 +4167,19 @@ solver_solve(Solver *solv, Queue *job) sugp = s->repo->idarraydata + s->suggests; while ((sug = *sugp++) != 0) { +#ifdef ENABLE_COMPLEX_DEPS + if (pool_is_complex_dep(pool, sug)) + { + do_complex_recommendations(solv, sug, &solv->suggestsmap, noselected); + continue; + } +#endif FOR_PROVIDES(p, pp, sug) if (solv->decisionmap[p] > 0) break; if (p) { - if (!solv->dontshowinstalledrecommended) + if (!noselected) { FOR_PROVIDES(p, pp, sug) if (solv->decisionmap[p] > 0) @@ -4530,7 +4196,9 @@ solver_solve(Solver *solv, Queue *job) { if (solv->decisionmap[i] < 0) continue; - if (solv->decisionmap[i] > 0 && solv->dontshowinstalledrecommended) + if (solv->decisionmap[i] > 0 && noselected) + continue; + if (MAPTST(&obsmap, i)) continue; s = pool->solvables + i; if (!MAPTST(&solv->suggestsmap, i)) @@ -4542,318 +4210,928 @@ solver_solve(Solver *solv, Queue *job) if (!solver_is_enhancing(solv, s)) continue; } - queue_push(&solv->suggestions, i); + queue_push(suggestionsq, i); + } + policy_filter_unwanted(solv, suggestionsq, POLICY_MODE_SUGGEST); + } + + /* 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); +} + + +/***********************************************************************/ +/* 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_create_state_maps(Solver *solv, Map *installedmap, Map *conflictsmap) +{ + pool_create_state_maps(solv->pool, &solv->decisionq, installedmap, conflictsmap); +} + +void +solver_trivial_installable(Solver *solv, Queue *pkgs, Queue *res) +{ + Pool *pool = solv->pool; + Map installedmap; + int i; + pool_create_state_maps(pool, &solv->decisionq, &installedmap, 0); + pool_trivial_installable_multiversionmap(pool, &installedmap, pkgs, res, solv->multiversion.size ? &solv->multiversion : 0); + for (i = 0; i < res->count; i++) + if (res->elements[i] != -1) + { + Solvable *s = pool->solvables + pkgs->elements[i]; + if (!strncmp("patch:", pool_id2str(pool, s->name), 6) && solvable_is_irrelevant_patch(s, &installedmap)) + res->elements[i] = -1; + } + map_free(&installedmap); +} + +/*------------------------------------------------------------------- + * + * decision introspection + */ + +int +solver_get_decisionlevel(Solver *solv, Id p) +{ + return solv->decisionmap[p]; +} + +void +solver_get_decisionqueue(Solver *solv, Queue *decisionq) +{ + queue_free(decisionq); + queue_init_clone(decisionq, &solv->decisionq); +} + +int +solver_get_lastdecisionblocklevel(Solver *solv) +{ + Id p; + if (solv->decisionq.count == 0) + return 0; + p = solv->decisionq.elements[solv->decisionq.count - 1]; + if (p < 0) + p = -p; + return solv->decisionmap[p] < 0 ? -solv->decisionmap[p] : solv->decisionmap[p]; +} + +void +solver_get_decisionblock(Solver *solv, int level, Queue *decisionq) +{ + Id p; + int i; + + queue_empty(decisionq); + for (i = 0; i < solv->decisionq.count; i++) + { + p = solv->decisionq.elements[i]; + if (p < 0) + p = -p; + if (solv->decisionmap[p] == level || solv->decisionmap[p] == -level) + break; + } + if (i == solv->decisionq.count) + return; + for (i = 0; i < solv->decisionq.count; i++) + { + p = solv->decisionq.elements[i]; + if (p < 0) + p = -p; + if (solv->decisionmap[p] == level || solv->decisionmap[p] == -level) + queue_push(decisionq, p); + else + break; + } +} + +int +solver_describe_decision(Solver *solv, Id p, Id *infop) +{ + int i; + Id pp, why; + + if (infop) + *infop = 0; + if (!solv->decisionmap[p]) + return SOLVER_REASON_UNRELATED; + pp = solv->decisionmap[p] < 0 ? -p : p; + for (i = 0; i < solv->decisionq.count; i++) + if (solv->decisionq.elements[i] == pp) + break; + if (i == solv->decisionq.count) /* just in case... */ + return SOLVER_REASON_UNRELATED; + why = solv->decisionq_why.elements[i]; + if (infop) + *infop = why > 0 ? why : -why; + if (why > 0) + return SOLVER_REASON_UNIT_RULE; + why = -why; + if (i == 0) + return SOLVER_REASON_KEEP_INSTALLED; /* the systemsolvable */ + if (i < solv->decisioncnt_update) + return SOLVER_REASON_RESOLVE_JOB; + if (i < solv->decisioncnt_keep) + { + if (why == 0 && pp < 0) + return SOLVER_REASON_CLEANDEPS_ERASE; + return SOLVER_REASON_UPDATE_INSTALLED; + } + if (i < solv->decisioncnt_resolve) + { + if (solv->focus_installed && i >= solv->decisioncnt_jobs) + return SOLVER_REASON_RESOLVE_JOB; + if (why == 0 && pp < 0) + return SOLVER_REASON_CLEANDEPS_ERASE; + return SOLVER_REASON_KEEP_INSTALLED; + } + if (why > 0) + return SOLVER_REASON_RESOLVE; + /* weak or orphaned */ + if (i < solv->decisioncnt_orphan) + return SOLVER_REASON_WEAKDEP; + return SOLVER_REASON_RESOLVE_ORPHAN; +} + + +void +solver_describe_weakdep_decision(Solver *solv, Id p, Queue *whyq) +{ + Pool *pool = solv->pool; + int i; + int level = solv->decisionmap[p]; + int decisionno; + Solvable *s; + + queue_empty(whyq); + if (level < 0) + return; /* huh? */ + for (decisionno = 0; decisionno < solv->decisionq.count; decisionno++) + if (solv->decisionq.elements[decisionno] == p) + break; + if (decisionno == solv->decisionq.count) + return; /* huh? */ + if (decisionno < solv->decisioncnt_weak || decisionno >= solv->decisioncnt_orphan) + return; /* huh? */ + + /* 1) list all packages that recommend us */ + for (i = 1; i < pool->nsolvables; i++) + { + Id *recp, rec, pp2, p2; + if (solv->decisionmap[i] < 0 || solv->decisionmap[i] >= level) + continue; + s = pool->solvables + i; + if (!s->recommends) + continue; + if (!solv->addalreadyrecommended && s->repo == solv->installed) + continue; + recp = s->repo->idarraydata + s->recommends; + while ((rec = *recp++) != 0) + { + int found = 0; + FOR_PROVIDES(p2, pp2, rec) + { + if (p2 == p) + found = 1; + else + { + /* if p2 is already installed, this recommends is ignored */ + if (solv->decisionmap[p2] > 0 && solv->decisionmap[p2] < level) + break; + } + } + if (!p2 && found) + { + queue_push(whyq, SOLVER_REASON_RECOMMENDED); + queue_push2(whyq, i, rec); + } + } + } + /* 2) list all supplements */ + s = pool->solvables + p; + if (s->supplements && level > 0) + { + Id *supp, sup, pp2, p2; + /* this is a hack. to use solver_dep_fulfilled we temporarily clear + * everything above our level in the decisionmap */ + for (i = decisionno; i < solv->decisionq.count; i++ ) + { + p2 = solv->decisionq.elements[i]; + if (p2 > 0) + solv->decisionmap[p2] = -solv->decisionmap[p2]; + } + supp = s->repo->idarraydata + s->supplements; + while ((sup = *supp++) != 0) + if (solver_dep_fulfilled(solv, sup)) + { + int found = 0; + /* let's see if this is an easy supp */ + FOR_PROVIDES(p2, pp2, sup) + { + if (!solv->addalreadyrecommended && solv->installed) + { + if (pool->solvables[p2].repo == solv->installed) + continue; + } + if (solv->decisionmap[p2] > 0 && solv->decisionmap[p2] < level) + { + queue_push(whyq, SOLVER_REASON_SUPPLEMENTED); + queue_push2(whyq, p2, sup); + found = 1; + } + } + if (!found) + { + /* hard case, just note dependency with no package */ + queue_push(whyq, SOLVER_REASON_SUPPLEMENTED); + queue_push2(whyq, 0, sup); + } + } + for (i = decisionno; i < solv->decisionq.count; i++) + { + p2 = solv->decisionq.elements[i]; + if (p2 > 0) + solv->decisionmap[p2] = -solv->decisionmap[p2]; } - policy_filter_unwanted(solv, &solv->suggestions, 0, POLICY_MODE_SUGGEST); } - - if (redoq.count) +} + +void +pool_job2solvables(Pool *pool, Queue *pkgs, Id how, Id what) +{ + Id p, pp; + how &= SOLVER_SELECTMASK; + queue_empty(pkgs); + if (how == SOLVER_SOLVABLE_ALL) + { + FOR_POOL_SOLVABLES(p) + queue_push(pkgs, p); + } + else if (how == SOLVER_SOLVABLE_REPO) { - /* restore decisionmap */ - for (i = 0; i < redoq.count; i += 2) - solv->decisionmap[redoq.elements[i]] = redoq.elements[i + 1]; + Repo *repo = pool_id2repo(pool, what); + Solvable *s; + if (repo) + FOR_REPO_SOLVABLES(repo, p, s) + queue_push(pkgs, p); } + else + { + FOR_JOB_SELECT(p, pp, how, what) + queue_push(pkgs, p); + } +} - /* - * if unsolvable, prepare solutions - */ - - if (solv->problems.count) +int +pool_isemptyupdatejob(Pool *pool, Id how, Id what) +{ + Id p, pp, pi, pip; + Id select = how & SOLVER_SELECTMASK; + if ((how & SOLVER_JOBMASK) != SOLVER_UPDATE) + return 0; + if (select == SOLVER_SOLVABLE_ALL || select == SOLVER_SOLVABLE_REPO) + return 0; + if (!pool->installed) + return 1; + FOR_JOB_SELECT(p, pp, select, what) + if (pool->solvables[p].repo == pool->installed) + return 0; + /* hard work */ + FOR_JOB_SELECT(p, pp, select, what) { - 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++) + Solvable *s = pool->solvables + p; + FOR_PROVIDES(pi, pip, s->name) { - 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]); + Solvable *si = pool->solvables + pi; + if (si->repo != pool->installed || si->name != s->name) + continue; + return 0; } - 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) + if (s->obsoletes) { - 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]; + Id obs, *obsp = s->repo->idarraydata + s->obsoletes; + while ((obs = *obsp++) != 0) + { + FOR_PROVIDES(pi, pip, obs) + { + Solvable *si = pool->solvables + pi; + if (si->repo != pool->installed) + continue; + if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, si, obs)) + continue; + if (pool->obsoleteusescolors && !pool_colormatch(pool, s, si)) + continue; + return 0; + } + } } - solv->recommendations.count = recocount; } - - queue_free(&redoq); - POOL_DEBUG(SAT_DEBUG_STATS, "final solver statistics: %d learned rules, %d unsolvable\n", solv->stats_learned, solv->stats_unsolvable); - POOL_DEBUG(SAT_DEBUG_STATS, "solver_solve took %d ms\n", sat_timems(solve_start)); + return 1; } -/***********************************************************************/ -/* disk usage computations */ - -/*------------------------------------------------------------------- - * - * calculate DU changes - */ - -void -solver_calc_duchanges(Solver *solv, DUChanges *mps, int nmps) +static int +get_userinstalled_cmp(const void *ap, const void *bp, void *dp) { - Map installedmap; - - solver_create_state_maps(solv, &installedmap, 0); - pool_calc_duchanges(solv->pool, &installedmap, mps, nmps); - map_free(&installedmap); + return *(Id *)ap - *(Id *)bp; } +static int +get_userinstalled_cmp_names(const void *ap, const void *bp, void *dp) +{ + Pool *pool = dp; + return strcmp(pool_id2str(pool, *(Id *)ap), pool_id2str(pool, *(Id *)bp)); +} -/*------------------------------------------------------------------- - * - * calculate changes in install size - */ +static int +get_userinstalled_cmp_namearch(const void *ap, const void *bp, void *dp) +{ + Pool *pool = dp; + int r; + r = strcmp(pool_id2str(pool, ((Id *)ap)[0]), pool_id2str(pool, ((Id *)bp)[0])); + if (r) + return r; + return strcmp(pool_id2str(pool, ((Id *)ap)[1]), pool_id2str(pool, ((Id *)bp)[1])); +} -int -solver_calc_installsizechange(Solver *solv) +static void +get_userinstalled_sort_uniq(Pool *pool, Queue *q, int flags) { - Map installedmap; - int change; + Id lastp = -1, lasta = -1; + int i, j; + if (q->count < ((flags & GET_USERINSTALLED_NAMEARCH) ? 4 : 2)) + return; + if ((flags & GET_USERINSTALLED_NAMEARCH) != 0) + solv_sort(q->elements, q->count / 2, 2 * sizeof(Id), get_userinstalled_cmp_namearch, pool); + else if ((flags & GET_USERINSTALLED_NAMES) != 0) + solv_sort(q->elements, q->count, sizeof(Id), get_userinstalled_cmp_names, pool); + else + solv_sort(q->elements, q->count, sizeof(Id), get_userinstalled_cmp, 0); + if ((flags & GET_USERINSTALLED_NAMEARCH) != 0) + { + for (i = j = 0; i < q->count; i += 2) + if (q->elements[i] != lastp || q->elements[i + 1] != lasta) + { + q->elements[j++] = lastp = q->elements[i]; + q->elements[j++] = lasta = q->elements[i + 1]; + } + } + else + { + for (i = j = 0; i < q->count; i++) + if (q->elements[i] != lastp) + q->elements[j++] = lastp = q->elements[i]; + } + queue_truncate(q, j); +} - solver_create_state_maps(solv, &installedmap, 0); - change = pool_calc_installsizechange(solv->pool, &installedmap); - map_free(&installedmap); - return change; +static void +namearch2solvables(Pool *pool, Queue *q, Queue *qout, int job) +{ + int i; + if (!pool->installed) + return; + for (i = 0; i < q->count; i += 2) + { + Id p, pp, name = q->elements[i], arch = q->elements[i + 1]; + FOR_PROVIDES(p, pp, name) + { + Solvable *s = pool->solvables + p; + if (s->repo != pool->installed || s->name != name || (arch && s->arch != arch)) + continue; + if (job) + queue_push(qout, job); + queue_push(qout, p); + } + } } -#define FIND_INVOLVED_DEBUG 0 void -solver_find_involved(Solver *solv, Queue *installedq, Solvable *ts, Queue *q) +solver_get_userinstalled(Solver *solv, Queue *q, int flags) { Pool *pool = solv->pool; - Map im; - Map installedm; + Id p, p2, pp; 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) + Repo *installed = solv->installed; + int i, j; + Map userinstalled; + + map_init(&userinstalled, 0); + queue_empty(q); + /* first process jobs */ + for (i = 0; i < solv->job.count; i += 2) { - installedq = &installedq_internal; - if (solv->installed) + Id how = solv->job.elements[i]; + Id what, select; + if (installed && (how & SOLVER_JOBMASK) == SOLVER_USERINSTALLED) { - 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 (!userinstalled.size) + map_grow(&userinstalled, installed->end - installed->start); + what = solv->job.elements[i + 1]; + select = how & SOLVER_SELECTMASK; + if (select == SOLVER_SOLVABLE_ALL || (select == SOLVER_SOLVABLE_REPO && what == installed->repoid)) + FOR_REPO_SOLVABLES(installed, p, s) + MAPSET(&userinstalled, p - installed->start); + FOR_JOB_SELECT(p, pp, select, what) + if (pool->solvables[p].repo == installed) + MAPSET(&userinstalled, p - installed->start); + continue; } - } - for (i = 0; i < installedq->count; i++) - { - ip = installedq->elements[i]; - MAPSET(&installedm, ip); - MAPSET(&im, ip); - } - - queue_push(&iq, ts - pool->solvables); - while (iq.count) - { - ip = queue_shift(&iq); - if (!MAPTST(&im, ip)) + if ((how & SOLVER_JOBMASK) != SOLVER_INSTALL) continue; - if (!MAPTST(&installedm, ip)) + if ((how & SOLVER_NOTBYUSER) != 0) continue; - MAPCLR(&im, ip); - s = pool->solvables + ip; -#if FIND_INVOLVED_DEBUG - printf("hello %s\n", solvable2str(pool, s)); + what = solv->job.elements[i + 1]; + select = how & SOLVER_SELECTMASK; + FOR_JOB_SELECT(p, pp, select, what) + if (solv->decisionmap[p] > 0) + { + queue_push(q, p); +#ifdef ENABLE_LINKED_PKGS + if (has_package_link(pool, pool->solvables + p)) + { + int j; + Queue lq; + queue_init(&lq); + find_package_link(pool, pool->solvables + p, 0, &lq, 0, 0); + for (j = 0; j < lq.count; j++) + if (solv->decisionmap[lq.elements[j]] > 0) + queue_push(q, lq.elements[j]); + } #endif - if (s->requires) + } + } + /* now process updates of userinstalled packages */ + if (installed && userinstalled.size) + { + for (i = 1; i < solv->decisionq.count; i++) { - reqp = s->repo->idarraydata + s->requires; - while ((req = *reqp++) != 0) + p = solv->decisionq.elements[i]; + if (p <= 0) + continue; + s = pool->solvables + p; + if (!s->repo) + continue; + if (s->repo == installed) + { + if (MAPTST(&userinstalled, p - installed->start)) + queue_push(q, p); + continue; + } + /* new package, check if we replace a userinstalled one */ + FOR_PROVIDES(p2, pp, s->name) { - if (req == SOLVABLE_PREREQMARKER) + Solvable *ps = pool->solvables + p2; + if (p2 == p || ps->repo != installed || !MAPTST(&userinstalled, p2 - installed->start)) continue; - /* count number of installed packages that match */ - count = 0; - FOR_PROVIDES(p, pp, req) - if (MAPTST(&installedm, p)) - count++; - if (count > 1) + if (!pool->implicitobsoleteusesprovides && s->name != ps->name) continue; - FOR_PROVIDES(p, pp, req) + if (pool->implicitobsoleteusescolors && !pool_colormatch(pool, s, ps)) + continue; + queue_push(q, p); + break; + } + if (!p2 && s->repo != installed && s->obsoletes) + { + Id obs, *obsp = s->repo->idarraydata + s->obsoletes; + while ((obs = *obsp++) != 0) { - if (MAPTST(&im, p)) + FOR_PROVIDES(p2, pp, obs) { -#if FIND_INVOLVED_DEBUG - printf("%s requires %s\n", solvable2str(pool, pool->solvables + ip), solvable2str(pool, pool->solvables + p)); -#endif - queue_push(&iq, p); + Solvable *ps = pool->solvables + p2; + if (p2 == p || ps->repo != installed || !MAPTST(&userinstalled, p2 - installed->start)) + continue; + if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs)) + continue; + if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps)) + continue; + queue_push(q, p); + break; } + if (p2) + break; } } } - if (s->recommends) + } + map_free(&userinstalled); + + /* convert to desired output format */ + if ((flags & GET_USERINSTALLED_NAMEARCH) != 0) + { + int qcount = q->count; + queue_insertn(q, 0, qcount, 0); + for (i = j = 0; i < qcount; i++) + { + s = pool->solvables + q->elements[i + qcount]; + q->elements[j++] = s->name; + q->elements[j++] = s->arch; + } + } + else if ((flags & GET_USERINSTALLED_NAMES) != 0) + { + for (i = 0; i < q->count; i++) + { + s = pool->solvables + q->elements[i]; + q->elements[i] = s->name; + } + } + /* sort and unify */ + get_userinstalled_sort_uniq(pool, q, flags); + + /* invert if asked for */ + if ((flags & GET_USERINSTALLED_INVERTED) != 0) + { + /* first generate queue with all installed packages */ + Queue invq; + queue_init(&invq); + for (i = 1; i < solv->decisionq.count; i++) + { + p = solv->decisionq.elements[i]; + if (p <= 0) + continue; + s = pool->solvables + p; + if (!s->repo) + continue; + if ((flags & GET_USERINSTALLED_NAMEARCH) != 0) + queue_push2(&invq, s->name, s->arch); + else if ((flags & GET_USERINSTALLED_NAMES) != 0) + queue_push(&invq, s->name); + else + queue_push(&invq, p); + } + /* push q on invq, just in case... */ + queue_insertn(&invq, invq.count, q->count, q->elements); + get_userinstalled_sort_uniq(pool, &invq, flags); + /* subtract queues (easy as they are sorted and invq is a superset of q) */ + if ((flags & GET_USERINSTALLED_NAMEARCH) != 0) { - reqp = s->repo->idarraydata + s->recommends; - while ((req = *reqp++) != 0) + if (q->count) { - count = 0; - FOR_PROVIDES(p, pp, req) - if (MAPTST(&installedm, p)) - count++; - if (count > 1) - continue; - FOR_PROVIDES(p, pp, req) - { - if (MAPTST(&im, p)) - { -#if FIND_INVOLVED_DEBUG - printf("%s recommends %s\n", solvable2str(pool, pool->solvables + ip), solvable2str(pool, pool->solvables + p)); -#endif - queue_push(&iq, p); - } - } + for (i = j = 0; i < invq.count; i += 2) + if (invq.elements[i] == q->elements[j] && invq.elements[i + 1] == q->elements[j + 1]) + { + invq.elements[i] = invq.elements[i + 1] = 0; + j += 2; + if (j >= q->count) + break; + } + queue_empty(q); } + for (i = 0; i < invq.count; i += 2) + if (invq.elements[i]) + queue_push2(q, invq.elements[i], invq.elements[i + 1]); } - if (!iq.count) + else { - /* supplements pass */ - for (i = 0; i < installedq->count; i++) + if (q->count) { - ip = installedq->elements[i]; - s = pool->solvables + ip; - if (!s->supplements) - continue; - 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", solvable2str(pool, pool->solvables + ip)); -#endif - queue_push(&iq, ip); - } + for (i = j = 0; i < invq.count; i++) + if (invq.elements[i] == q->elements[j]) + { + invq.elements[i] = 0; + if (++j >= q->count) + break; + } + queue_empty(q); } + for (i = 0; i < invq.count; i++) + if (invq.elements[i]) + queue_push(q, invq.elements[i]); } + queue_free(&invq); } +} - for (i = 0; i < installedq->count; i++) - { - ip = installedq->elements[i]; - if (MAPTST(&im, ip)) - queue_push(&iq, ip); - } +void +pool_add_userinstalled_jobs(Pool *pool, Queue *q, Queue *job, int flags) +{ + int i; - while (iq.count) + if ((flags & GET_USERINSTALLED_INVERTED) != 0) { - 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) + Queue invq; + Id p, lastid; + Solvable *s; + int bad; + if (!pool->installed) + return; + queue_init(&invq); + if ((flags & GET_USERINSTALLED_NAMEARCH) != 0) + flags &= ~GET_USERINSTALLED_NAMES; /* just in case */ + FOR_REPO_SOLVABLES(pool->installed, p, s) + queue_push(&invq, flags & GET_USERINSTALLED_NAMES ? s->name : p); + if ((flags & GET_USERINSTALLED_NAMEARCH) != 0) { - reqp = s->repo->idarraydata + s->requires; - while ((req = *reqp++) != 0) - { - FOR_PROVIDES(p, pp, req) - { - if (!MAPTST(&im, p)) - { - if (p == tp) - continue; -#if FIND_INVOLVED_DEBUG - printf("%s requires %s\n", solvable2str(pool, pool->solvables + ip), solvable2str(pool, pool->solvables + p)); -#endif - MAPSET(&im, p); - queue_push(&iq, p); - } - } - } + /* for namearch we convert to packages */ + namearch2solvables(pool, q, &invq, 0); + get_userinstalled_sort_uniq(pool, &invq, flags); + namearch2solvables(pool, q, &invq, 0); + flags = 0; } - if (s->recommends) + else + { + queue_insertn(&invq, invq.count, q->count, q->elements); + get_userinstalled_sort_uniq(pool, &invq, flags); + /* now the fun part, add q again, sort, and remove all dups */ + queue_insertn(&invq, invq.count, q->count, q->elements); + } + if (invq.count > 1) + { + if ((flags & GET_USERINSTALLED_NAMES) != 0) + solv_sort(invq.elements, invq.count, sizeof(Id), get_userinstalled_cmp_names, pool); + else + solv_sort(invq.elements, invq.count, sizeof(Id), get_userinstalled_cmp, 0); + } + lastid = -1; + bad = 1; + for (i = 0; i < invq.count; i++) { - reqp = s->repo->idarraydata + s->recommends; - while ((req = *reqp++) != 0) + if (invq.elements[i] == lastid) { - FOR_PROVIDES(p, pp, req) - { - if (!MAPTST(&im, p)) - { - if (p == tp) - continue; -#if FIND_INVOLVED_DEBUG - printf("%s recommends %s\n", solvable2str(pool, pool->solvables + ip), solvable2str(pool, pool->solvables + p)); -#endif - MAPSET(&im, p); - queue_push(&iq, p); - } - } + bad = 1; + continue; } + if (!bad) + queue_push2(job, SOLVER_USERINSTALLED | (flags & GET_USERINSTALLED_NAMES ? SOLVER_SOLVABLE_NAME : SOLVER_SOLVABLE), lastid); + bad = 0; + lastid = invq.elements[i]; + } + if (!bad) + queue_push2(job, SOLVER_USERINSTALLED | (flags & GET_USERINSTALLED_NAMES ? SOLVER_SOLVABLE_NAME : SOLVER_SOLVABLE), lastid); + queue_free(&invq); + } + else + { + if (flags & GET_USERINSTALLED_NAMEARCH) + namearch2solvables(pool, q, job, SOLVER_USERINSTALLED | SOLVER_SOLVABLE); + else + { + for (i = 0; i < q->count; i++) + queue_push2(job, SOLVER_USERINSTALLED | (flags & GET_USERINSTALLED_NAMES ? SOLVER_SOLVABLE_NAME : SOLVER_SOLVABLE), q->elements[i]); } - if (!iq.count) + } +} + +int +solver_alternatives_count(Solver *solv) +{ + Id *elements = solv->branches.elements; + int res, count; + for (res = 0, count = solv->branches.count; count; res++) + count -= elements[count - 2]; + return res; +} + +int +solver_get_alternative(Solver *solv, Id alternative, Id *idp, Id *fromp, Id *chosenp, Queue *choices, int *levelp) +{ + int cnt = solver_alternatives_count(solv); + int count = solv->branches.count; + Id *elements = solv->branches.elements; + if (choices) + queue_empty(choices); + if (alternative <= 0 || alternative > cnt) + return 0; + elements += count; + for (; cnt > alternative; cnt--) + elements -= elements[-2]; + if (levelp) + *levelp = elements[-1]; + if (fromp) + *fromp = elements[-4]; + if (idp) + *idp = elements[-3]; + if (chosenp) + { + int i; + *chosenp = 0; + for (i = elements[-2]; i > 4; i--) { - /* supplements pass */ - for (i = 0; i < installedq->count; i++) + Id p = -elements[-i]; + if (p > 0 && solv->decisionmap[p] == elements[-1] + 1) { - ip = installedq->elements[i]; - if (ip == tp) - continue; - s = pool->solvables + ip; - if (!s->supplements) - continue; - 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", solvable2str(pool, pool->solvables + ip)); -#endif - MAPSET(&im, ip); - queue_push(&iq, ip); - } + *chosenp = p; + break; } } } - - queue_free(&iq); + if (choices) + queue_insertn(choices, 0, elements[-2] - 4, elements - elements[-2]); + return elements[-4] ? SOLVER_ALTERNATIVE_TYPE_RECOMMENDS : SOLVER_ALTERNATIVE_TYPE_RULE; +} - /* convert map into result */ - for (i = 0; i < installedq->count; i++) +const char * +solver_select2str(Pool *pool, Id select, Id what) +{ + const char *s; + char *b; + select &= SOLVER_SELECTMASK; + if (select == SOLVER_SOLVABLE) + return pool_solvid2str(pool, what); + if (select == SOLVER_SOLVABLE_NAME) + return pool_dep2str(pool, what); + if (select == SOLVER_SOLVABLE_PROVIDES) { - ip = installedq->elements[i]; - if (MAPTST(&im, ip)) - continue; - if (ip == ts - pool->solvables) - continue; - queue_push(q, ip); + s = pool_dep2str(pool, what); + b = pool_alloctmpspace(pool, 11 + strlen(s)); + sprintf(b, "providing %s", s); + return b; + } + if (select == SOLVER_SOLVABLE_ONE_OF) + { + Id p; + b = 0; + while ((p = pool->whatprovidesdata[what++]) != 0) + { + s = pool_solvid2str(pool, p); + if (b) + b = pool_tmpappend(pool, b, ", ", s); + else + b = pool_tmpjoin(pool, s, 0, 0); + pool_freetmpspace(pool, s); + } + return b ? b : "nothing"; + } + if (select == SOLVER_SOLVABLE_REPO) + { + b = pool_alloctmpspace(pool, 20); + sprintf(b, "repo #%d", what); + return b; + } + if (select == SOLVER_SOLVABLE_ALL) + return "all packages"; + return "unknown job select"; +} + +const char * +pool_job2str(Pool *pool, Id how, Id what, Id flagmask) +{ + Id select = how & SOLVER_SELECTMASK; + const char *strstart = 0, *strend = 0; + char *s; + int o; + + switch (how & SOLVER_JOBMASK) + { + case SOLVER_NOOP: + return "do nothing"; + case SOLVER_INSTALL: + if (select == SOLVER_SOLVABLE && pool->installed && pool->solvables[what].repo == pool->installed) + strstart = "keep ", strend = " installed"; + else if (select == SOLVER_SOLVABLE || select == SOLVER_SOLVABLE_NAME) + strstart = "install "; + else if (select == SOLVER_SOLVABLE_PROVIDES) + strstart = "install a package "; + else + strstart = "install one of "; + break; + case SOLVER_ERASE: + if (select == SOLVER_SOLVABLE && !(pool->installed && pool->solvables[what].repo == pool->installed)) + strstart = "keep ", strend = " uninstalled"; + else if (select == SOLVER_SOLVABLE_PROVIDES) + strstart = "deinstall all packages "; + else + strstart = "deinstall "; + break; + case SOLVER_UPDATE: + strstart = "update "; + break; + case SOLVER_WEAKENDEPS: + strstart = "weaken deps of "; + break; + case SOLVER_MULTIVERSION: + strstart = "multi version "; + break; + case SOLVER_LOCK: + strstart = "lock "; + break; + case SOLVER_DISTUPGRADE: + strstart = "dist upgrade "; + break; + case SOLVER_VERIFY: + strstart = "verify "; + break; + case SOLVER_DROP_ORPHANED: + strstart = "deinstall ", strend = " if orphaned"; + break; + case SOLVER_USERINSTALLED: + strstart = "regard ", strend = " as userinstalled"; + break; + default: + strstart = "unknown job "; + break; + } + s = pool_tmpjoin(pool, strstart, solver_select2str(pool, select, what), strend); + how &= flagmask; + if ((how & ~(SOLVER_SELECTMASK|SOLVER_JOBMASK)) == 0) + return s; + o = strlen(s); + s = pool_tmpappend(pool, s, " ", 0); + if (how & SOLVER_WEAK) + s = pool_tmpappend(pool, s, ",weak", 0); + if (how & SOLVER_ESSENTIAL) + s = pool_tmpappend(pool, s, ",essential", 0); + if (how & SOLVER_CLEANDEPS) + s = pool_tmpappend(pool, s, ",cleandeps", 0); + if (how & SOLVER_ORUPDATE) + s = pool_tmpappend(pool, s, ",orupdate", 0); + if (how & SOLVER_FORCEBEST) + s = pool_tmpappend(pool, s, ",forcebest", 0); + if (how & SOLVER_TARGETED) + s = pool_tmpappend(pool, s, ",targeted", 0); + if (how & SOLVER_SETEV) + s = pool_tmpappend(pool, s, ",setev", 0); + if (how & SOLVER_SETEVR) + s = pool_tmpappend(pool, s, ",setevr", 0); + if (how & SOLVER_SETARCH) + s = pool_tmpappend(pool, s, ",setarch", 0); + if (how & SOLVER_SETVENDOR) + s = pool_tmpappend(pool, s, ",setvendor", 0); + if (how & SOLVER_SETREPO) + s = pool_tmpappend(pool, s, ",setrepo", 0); + if (how & SOLVER_SETNAME) + s = pool_tmpappend(pool, s, ",setname", 0); + if (how & SOLVER_NOAUTOSET) + s = pool_tmpappend(pool, s, ",noautoset", 0); + if (s[o + 1] != ',') + s = pool_tmpappend(pool, s, ",?", 0); + s[o + 1] = '['; + return pool_tmpappend(pool, s, "]", 0); +} + +const char * +solver_alternative2str(Solver *solv, int type, Id id, Id from) +{ + Pool *pool = solv->pool; + if (type == SOLVER_ALTERNATIVE_TYPE_RECOMMENDS) + { + const char *s = pool_dep2str(pool, id); + return pool_tmpappend(pool, s, ", recommended by ", pool_solvid2str(pool, from)); + } + if (type == SOLVER_ALTERNATIVE_TYPE_RULE) + { + int rtype; + Id depfrom, depto, dep; + char buf[64]; + if (solver_ruleclass(solv, id) == SOLVER_RULE_CHOICE) + id = solver_rule2pkgrule(solv, id); + rtype = solver_ruleinfo(solv, id, &depfrom, &depto, &dep); + if ((rtype & SOLVER_RULE_TYPEMASK) == SOLVER_RULE_JOB) + { + if ((depto & SOLVER_SELECTMASK) == SOLVER_SOLVABLE_PROVIDES) + return pool_dep2str(pool, dep); + return solver_select2str(pool, depto & SOLVER_SELECTMASK, dep); + } + if (rtype == SOLVER_RULE_PKG_REQUIRES) + { + const char *s = pool_dep2str(pool, dep); + return pool_tmpappend(pool, s, ", required by ", pool_solvid2str(pool, depfrom)); + } + sprintf(buf, "Rule #%d", id); + return pool_tmpjoin(pool, buf, 0, 0); } - map_free(&im); - map_free(&installedm); - queue_free(&installedq_internal); + return "unknown alternative type"; } -/* EOF */