X-Git-Url: http://review.tizen.org/git/?a=blobdiff_plain;f=src%2Fsolver.c;h=f5517311777a404c984b7292c5269e2183ced1fa;hb=1a93853889c819ac2d3c8e83e856f4775e664b00;hp=b0f1bce795a86e6d7cebf95d9c98dfaba80ab056;hpb=04b192f26d73bd4394451b2b9faacad3c11d5163;p=platform%2Fupstream%2Flibsolv.git diff --git a/src/solver.c b/src/solver.c index b0f1bce..f551731 100644 --- a/src/solver.c +++ b/src/solver.c @@ -30,6 +30,7 @@ #define RULES_BLOCK 63 + /******************************************************************** * * dependency check helpers @@ -44,16 +45,34 @@ * 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; Reldep *rd; Solvable *s; - if (!solv->dosplitprovides || !solv->installed || (!solv->updatemap_all && !solv->updatemap.size)) + if (!solv->dosplitprovides || !solv->installed) return 0; if (!ISRELDEP(dep)) return 0; @@ -76,101 +95,76 @@ solver_splitprovides(Solver *solv, Id dep) /* 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 && - (solv->updatemap_all || (solv->updatemap.size && MAPTST(&solv->updatemap, p - solv->installed->start)))) + 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) -{ -#if 0 - Pool *pool = solv->pool; - Id p, pp; - - if (ISRELDEP(dep)) - { - Reldep *rd = GETRELDEP(pool, dep); - if (rd->flags == REL_AND) - { - if (!solver_dep_installed(solv, rd->name)) - 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; -} - -/* mirrors solver_dep_installed, but returns 2 if a - * dependency listed in solv->installsuppdepq was involved */ +/* mirrors solver_dep_fulfilled, but returns 2 if a new package + * was involved */ static int -solver_check_installsuppdepq_dep(Solver *solv, Id dep) +solver_dep_fulfilled_alreadyinstalled(Solver *solv, Id dep) { Pool *pool = solv->pool; Id p, pp; - Queue *q; + int r; if (ISRELDEP(dep)) { Reldep *rd = GETRELDEP(pool, dep); if (rd->flags == REL_AND) { - int r2, r1 = solver_check_installsuppdepq_dep(solv, rd->name); + int r2, r1 = solver_dep_fulfilled_alreadyinstalled(solv, rd->name); if (!r1) return 0; - r2 = solver_check_installsuppdepq_dep(solv, rd->evr); + r2 = solver_dep_fulfilled_alreadyinstalled(solv, rd->evr); if (!r2) return 0; return r1 == 2 || r2 == 2 ? 2 : 1; } if (rd->flags == REL_OR) { - int r2, r1 = solver_check_installsuppdepq_dep(solv, rd->name); - r2 = solver_check_installsuppdepq_dep(solv, rd->evr); + int r2, r1 = solver_dep_fulfilled_alreadyinstalled(solv, rd->name); + r2 = solver_dep_fulfilled_alreadyinstalled(solv, rd->evr); if (!r1 && !r2) return 0; 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); - if (rd->flags == REL_NAMESPACE && (q = solv->installsuppdepq) != 0) + 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 (solv->decisionmap[p] > 0) - return 1; - return 0; + { + Solvable *s = pool->solvables + p; + if (s->repo && s->repo != solv->installed) + return 2; + r = 1; + } + return r; } static int -solver_check_installsuppdepq(Solver *solv, Solvable *s) +solver_is_supplementing_alreadyinstalled(Solver *solv, Solvable *s) { Id sup, *supp; supp = s->repo->idarraydata + s->supplements; while ((sup = *supp++) != 0) - if (solver_check_installsuppdepq_dep(solv, sup) == 2) + if (solver_dep_fulfilled_alreadyinstalled(solv, sup) == 2) return 1; return 0; } @@ -188,17 +182,10 @@ autouninstall(Solver *solv, Id *problem) { if (v < 0) extraflags &= solv->job.elements[-v - 1]; - if (v >= solv->featurerules && v < solv->featurerules_end) - if (v > lastfeature) - lastfeature = v; if (v >= solv->updaterules && v < solv->updaterules_end) { - /* check if identical to feature rule */ - Id p = solv->rules[v].p; - Rule *r; - if (p <= 0) - continue; - r = solv->rules + solv->featurerules + (p - solv->installed->start); + /* 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 */ @@ -342,7 +329,7 @@ makeruledecisions(Solver *solv) continue; /* do weak rules in phase 2 */ - if (ri < solv->learntrules && MAPTST(&solv->weakrulemap, ri)) + if (ri < solv->learntrules && solv->weakrulemap.size && MAPTST(&solv->weakrulemap, ri)) continue; v = r->p; @@ -427,9 +414,9 @@ makeruledecisions(Solver *solv) assert(solv->decisionq_why.elements[i] > 0); /* - * conflict with an rpm rule ? + * conflict with a pkg rule ? */ - if (solv->decisionq_why.elements[i] < solv->rpmrules_end) + if (solv->decisionq_why.elements[i] < solv->pkgrules_end) { if (record_proof) { @@ -441,7 +428,7 @@ makeruledecisions(Solver *solv) else queue_push(&solv->problems, 0); assert(v > 0 || v == -SYSTEMSOLVABLE); - POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "conflict with rpm rule, disabling rule #%d\n", ri); + 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 @@ -484,7 +471,7 @@ makeruledecisions(Solver *solv) if (rr->p != vv /* not affecting the literal */ && rr->p != -vv) continue; - if (MAPTST(&solv->weakrulemap, i)) /* weak: silently ignore */ + if (solv->weakrulemap.size && MAPTST(&solv->weakrulemap, i)) /* weak: silently ignore */ continue; POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, " - disabling rule #%d\n", i); @@ -511,6 +498,8 @@ makeruledecisions(Solver *solv) /* * phase 2: now do the weak assertions */ + if (!solv->weakrulemap.size) + break; /* no weak rules, no phase 2 */ for (ii = 0; ii < solv->ruleassertions.count; ii++) { ri = solv->ruleassertions.elements[ii]; @@ -580,14 +569,9 @@ makewatches(Solver *solv) int nsolvables = solv->pool->nsolvables; solv_free(solv->watches); - /* lower half for removals, upper half for installs */ + /* lower half for removals, upper half for installs */ solv->watches = solv_calloc(2 * nsolvables, sizeof(Id)); -#if 1 - /* do it reverse so rpm rules get triggered first (XXX: obsolete?) */ for (i = 1, r = solv->rules + solv->nrules - 1; i < solv->nrules; i++, r--) -#else - for (i = 1, r = solv->rules + 1; i < solv->nrules; i++, r++) -#endif { if (!r->w2) /* assertions do not need watches */ continue; @@ -658,7 +642,6 @@ 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(SOLV_DEBUG_PROPAGATE, "----- propagate -----\n"); @@ -666,10 +649,10 @@ propagate(Solver *solv, int level) /* 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 (SOLV_DEBUG_PROPAGATE) @@ -698,11 +681,11 @@ propagate(Solver *solv, int level) 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; @@ -714,17 +697,16 @@ propagate(Solver *solv, int level) 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) { @@ -735,6 +717,8 @@ propagate(Solver *solv, int level) * 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 */ @@ -766,7 +750,7 @@ propagate(Solver *solv, int level) if (p > 0) POOL_DEBUG(SOLV_DEBUG_PROPAGATE, " -> move w%d to %s\n", (pkg == r->w1 ? 1 : 2), pool_solvid2str(pool, p)); else - POOL_DEBUG(SOLV_DEBUG_PROPAGATE," -> move w%d to !%s\n", (pkg == r->w1 ? 1 : 2), pool_solvid2str(pool, -p)); + POOL_DEBUG(SOLV_DEBUG_PROPAGATE, " -> move w%d to !%s\n", (pkg == r->w1 ? 1 : 2), pool_solvid2str(pool, -p)); } *rp = *next_rp; @@ -833,25 +817,96 @@ propagate(Solver *solv, int level) /*------------------------------------------------------------------- * + * 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; - Id r_buf[4]; + 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_buffer(&r, r_buf, sizeof(r_buf)/sizeof(*r_buf)); + queue_init_buffer(&q, q_buf, sizeof(q_buf)/sizeof(*q_buf)); POOL_DEBUG(SOLV_DEBUG_ANALYZE, "ANALYZE at %d ----------------------\n", level); map_init(&seen, pool->nsolvables); @@ -861,43 +916,31 @@ analyze(Solver *solv, int level, Rule *c, int *pr, int *dr, int *whyp) 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); /* mark that we also need to look at this literal */ 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) */ @@ -913,14 +956,15 @@ l1retry: 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(SOLV_DEBUG_ANALYZE, "got %d involved level 1 decisions\n", l1num); /* clear non-l1 bits from seen map */ - for (i = 0; i < r.count; i++) + 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 in seen map */ @@ -934,27 +978,49 @@ 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); + assert(p != 0); + assert(rlevel > 0 && rlevel < level); IF_POOLDEBUG (SOLV_DEBUG_ANALYZE) { POOL_DEBUG(SOLV_DEBUG_ANALYZE, "learned rule for level %d (am %d)\n", rlevel, level); - solver_printruleelement(solv, SOLV_DEBUG_ANALYZE, 0, *pr); - for (i = 0; i < r.count; i++) - solver_printruleelement(solv, SOLV_DEBUG_ANALYZE, 0, r.elements[i]); + 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; - queue_free(&r); 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; } @@ -969,7 +1035,6 @@ l1retry: void solver_reset(Solver *solv) { - Pool *pool = solv->pool; int i; Id v; @@ -988,10 +1053,6 @@ solver_reset(Solver *solv) /* adapt learnt rule status to new set of enabled/disabled rules */ enabledisablelearntrules(solv); - - /* redo all assertion rule decisions */ - makeruledecisions(solv); - POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "decisions so far: %d\n", solv->decisionq.count); } @@ -1021,11 +1082,11 @@ analyze_unsolvable_rule(Solver *solv, Rule *r, Id *lastweakp, Map *rseen) 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) @@ -1059,22 +1120,22 @@ analyze_unsolvable_rule(Solver *solv, Rule *r, Id *lastweakp, Map *rseen) /*------------------------------------------------------------------- * - * analyze_unsolvable + * 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-rpm rules into + * 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 0 if disablerules is not set or disable - * _all_ of the problem rules and return 1. + * Otherwise we return -1 if disablerules is not set or disable + * _all_ of the problem rules and return 0. * - * return: 1 - disabled some rules, try again - * 0 - hopeless + * return: 0 - disabled some rules, try again + * -1 - hopeless */ static int @@ -1082,10 +1143,10 @@ analyze_unsolvable(Solver *solv, Rule *cr, int disablerules) { Pool *pool = solv->pool; Rule *r; - Map seen; /* global to speed things up? */ + Map involved; /* global to speed things up? */ Map rseen; - Id d, v, vv, *dp, why; - int l, i, idx; + Id pp, v, vv, why; + int i, idx; Id *decisionmap = solv->decisionmap; int oldproblemcount; int oldlearntpoolcount; @@ -1103,38 +1164,25 @@ analyze_unsolvable(Solver *solv, Rule *cr, int disablerules) queue_push(&solv->problems, 0); r = cr; - map_init(&seen, pool->nsolvables); + 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, &rseen); - d = r->d < 0 ? -r->d - 1 : r->d; - dp = d ? pool->whatprovidesdata + d : 0; - for (i = -1; ; i++) + 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) || vv == SYSTEMSOLVABLE) + if (!MAPTST(&involved, vv) || vv == SYSTEMSOLVABLE) continue; why = solv->decisionq_why.elements[idx]; assert(why > 0); @@ -1142,28 +1190,15 @@ analyze_unsolvable(Solver *solv, Rule *cr, int disablerules) queue_push(&solv->learnt_pool, why); r = solv->rules + why; analyze_unsolvable_rule(solv, r, &lastweak, &rseen); - d = r->d < 0 ? -r->d - 1 : r->d; - dp = d ? pool->whatprovidesdata + d : 0; - for (i = -1; ; i++) + 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 */ @@ -1184,7 +1219,7 @@ analyze_unsolvable(Solver *solv, Rule *cr, int disablerules) if (v < 0) solver_reenablepolicyrules(solv, -v); solver_reset(solv); - return 1; + return 0; } if (solv->allowuninstall && (v = autouninstall(solv, solv->problems.elements + oldproblemcount + 1)) != 0) @@ -1192,7 +1227,7 @@ analyze_unsolvable(Solver *solv, Rule *cr, int disablerules) solv->problems.count = oldproblemcount; solv->learnt_pool.count = oldlearntpoolcount; solver_reset(solv); - return 1; + return 0; } /* finish proof */ @@ -1209,90 +1244,10 @@ analyze_unsolvable(Solver *solv, Rule *cr, int disablerules) solver_disableproblem(solv, solv->problems.elements[i]); /* XXX: might want to enable all weak rules again */ solver_reset(solv); - return 1; + return 0; } POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "UNSOLVABLE\n"); - return 0; -} - - -/********************************************************************/ -/* Decision revert */ - -/*------------------------------------------------------------------- - * - * 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--; - while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] >= 0) - solv->branches.count--; - while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] < 0) - solv->branches.count--; - } - 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; - } - } + return -1; } @@ -1308,7 +1263,7 @@ 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 * */ @@ -1316,11 +1271,8 @@ static int 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; - assert(ruleid >= 0); if (decision) { level++; @@ -1331,6 +1283,7 @@ setpropagatelearn(Solver *solv, int level, Id decision, int disablerules, Id rul queue_push(&solv->decisionq, decision); queue_push(&solv->decisionq_why, -ruleid); /* <= 0 -> free decision */ } + assert(ruleid >= 0 && level > 0); for (;;) { r = propagate(solv, level); @@ -1339,36 +1292,18 @@ setpropagatelearn(Solver *solv, int level, Id decision, int disablerules, Id rul if (level == 1) return analyze_unsolvable(solv, r, disablerules); POOL_DEBUG(SOLV_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(SOLV_DEBUG_ANALYZE, "reverting decisions (level %d -> %d)\n", level, l); - level = l; - revert(solv, level); - r = solver_addrule(solv, p, 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 - { - /* learnt rule is an assertion */ - queue_push(&solv->ruleassertions, r - solv->rules); - } + level = analyze(solv, level, r, &lr); /* the new rule is unit by design */ - solv->decisionmap[p > 0 ? p : -p] = p > 0 ? level : -level; - queue_push(&solv->decisionq, p); - queue_push(&solv->decisionq_why, r - solv->rules); + 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) { POOL_DEBUG(SOLV_DEBUG_ANALYZE, "decision: "); - solver_printruleelement(solv, SOLV_DEBUG_ANALYZE, 0, p); + solver_printruleelement(solv, SOLV_DEBUG_ANALYZE, 0, decision); POOL_DEBUG(SOLV_DEBUG_ANALYZE, "new rule: "); - solver_printrule(solv, SOLV_DEBUG_ANALYZE, r); + solver_printrule(solv, SOLV_DEBUG_ANALYZE, lr); } } return level; @@ -1379,6 +1314,7 @@ 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; @@ -1390,32 +1326,97 @@ reorder_dq_for_jobrules(Solver *solv, int level, Queue *dq) continue; if (solv->decisionmap[p] == 0) { - solv->decisionmap[p] = level; + if (s->recommends || s->suggests) + queue_push(&solv->decisionq, p); + solv->decisionmap[p] = level + 1; haveone = 1; } } if (!haveone) return; + policy_update_recommendsmap(solv); for (i = 0; i < dqcount; i++) - if (!solver_is_enhancing(solv, pool->solvables + dq->elements[i])) - { - queue_push(dq, dq->elements[i]); - dq->elements[i] = 0; - } + { + 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++) - if (dq->elements[i] && !solver_is_supplementing(solv, pool->solvables + dq->elements[i])) - { - queue_push(dq, dq->elements[i]); - dq->elements[i] = 0; - } + { + 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) + 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); } /*------------------------------------------------------------------- @@ -1425,7 +1426,7 @@ reorder_dq_for_jobrules(Solver *solv, int level, Queue *dq) * 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 * */ @@ -1434,40 +1435,18 @@ selectandinstall(Solver *solv, int level, Queue *dq, int disablerules, Id ruleid { Pool *pool = solv->pool; Id p; - int i; if (dq->count > 1) policy_filter_unwanted(solv, dq, POLICY_MODE_CHOOSE); - if (dq->count > 1) - { - /* XXX: didn't we already do that? */ - /* XXX: shouldn't we prefer installed packages? */ - /* XXX: move to policy.c? */ - /* choose the supplemented one */ - for (i = 0; i < dq->count; i++) - if (solver_is_supplementing(solv, pool->solvables + dq->elements[i])) - { - dq->elements[0] = dq->elements[i]; - dq->count = 1; - break; - } - } /* 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) - { - /* multiple candidates, open a branch */ - queue_push(&solv->branches, -dq->elements[0]); - for (i = 1; i < dq->count; i++) - queue_push(&solv->branches, dq->elements[i]); - queue_push(&solv->branches, level); - } + 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); } @@ -1593,8 +1572,6 @@ resolve_jobrules(Solver *solv, int level, int disablerules, Queue *dq) level = selectandinstall(solv, level, dq, disablerules, i); if (level <= olevel) { - if (level == 0) - return 0; /* unsolvable */ if (level == olevel) { i--; @@ -1681,6 +1658,7 @@ solver_free(Solver *solv) 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); } @@ -1730,6 +1708,10 @@ solver_get_flag(Solver *solv, int flag) 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; } @@ -1802,14 +1784,20 @@ solver_set_flag(Solver *solv, int flag, int value) 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; } -int -cleandeps_check_mistakes(Solver *solv, int level) +static int +cleandeps_check_mistakes(Solver *solv) { Pool *pool = solv->pool; Rule *r; @@ -1855,8 +1843,6 @@ cleandeps_check_mistakes(Solver *solv, int level) solver_reenablepolicyrules_cleandeps(solv, i); mademistake = 1; } - if (mademistake) - solver_reset(solv); return mademistake; } @@ -2029,7 +2015,7 @@ solver_run_sat(Solver *solv, int disablerules, int doweak) int i, j, n; Solvable *s; Pool *pool = solv->pool; - Id p, pp, *dp; + Id p, pp, *dp, postponed; int minimizationsteps; int installedpos = solv->installed ? solv->installed->start : 0; @@ -2040,10 +2026,8 @@ solver_run_sat(Solver *solv, int disablerules, int doweak) solver_printruleclass(solv, SOLV_DEBUG_RULE_CREATION, solv->rules + i); } - POOL_DEBUG(SOLV_DEBUG_SOLVER, "initial decisions: %d\n", solv->decisionq.count); - /* start SAT algorithm */ - level = 1; + level = 0; systemlevel = level + 1; POOL_DEBUG(SOLV_DEBUG_SOLVER, "solving...\n"); @@ -2052,7 +2036,7 @@ solver_run_sat(Solver *solv, int disablerules, int doweak) /* * here's the main loop: - * 1) propagate new decisions (only needed once) + * 1) decide assertion rules and propagate * 2) fulfill jobs * 3) try to keep installed packages * 4) fulfill all unresolved rules @@ -2068,16 +2052,24 @@ solver_run_sat(Solver *solv, int disablerules, int doweak) /* * initial propagation of the assertions */ - if (level == 1) + if (level <= 0) { - POOL_DEBUG(SOLV_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; - level = 0; - break; /* unsolvable */ + level = analyze_unsolvable(solv, r, disablerules); + continue; } + systemlevel = level + 1; } /* @@ -2088,11 +2080,7 @@ solver_run_sat(Solver *solv, int disablerules, int doweak) olevel = level; level = resolve_jobrules(solv, level, disablerules, &dq); if (level < olevel) - { - if (level == 0) - break; /* unsolvable */ - continue; - } + continue; systemlevel = level + 1; } @@ -2209,15 +2197,9 @@ solver_run_sat(Solver *solv, int disablerules, int doweak) { olevel = level; level = selectandinstall(solv, level, &dq, disablerules, rr - solv->rules); - if (level == 0) - { - queue_free(&dq); - queue_free(&dqs); - return; - } if (level <= olevel) { - if (level == 1 || level < passlevel) + if (level < passlevel) break; /* trouble */ if (level < olevel) n = installed->start; /* redo all */ @@ -2244,11 +2226,9 @@ solver_run_sat(Solver *solv, int disablerules, int doweak) POOL_DEBUG(SOLV_DEBUG_POLICY, "keeping %s\n", pool_solvid2str(pool, i)); level = setpropagatelearn(solv, level, i, disablerules, r - solv->rules); } - if (level == 0) - break; if (level <= olevel) { - if (level == 1 || level < passlevel) + if (level < passlevel) break; /* trouble */ if (level < olevel) n = installed->start; /* redo all */ @@ -2265,8 +2245,6 @@ solver_run_sat(Solver *solv, int disablerules, int doweak) } installedpos = installed->start; /* reset installedpos */ } - if (level == 0) - break; /* unsolvable */ systemlevel = level + 1; if (pass < 2) continue; /* had trouble, retry */ @@ -2279,11 +2257,7 @@ solver_run_sat(Solver *solv, int disablerules, int doweak) olevel = level; level = resolve_jobrules(solv, level, disablerules, &dq); if (level < olevel) - { - if (level == 0) - break; /* unsolvable */ - continue; - } + continue; systemlevel = level + 1; } @@ -2296,8 +2270,17 @@ solver_run_sat(Solver *solv, int disablerules, int doweak) if (!solv->decisioncnt_resolve) solv->decisioncnt_resolve = solv->decisionq.count; POOL_DEBUG(SOLV_DEBUG_POLICY, "deciding unresolved rules\n"); - for (i = 1, n = 1; n < solv->nrules; i++, n++) + postponed = 0; + for (i = 1, n = 1; ; i++, n++) { + if (n >= solv->nrules) + { + if (postponed <= 0) + break; + i = postponed; + postponed = -1; + n = 1; + } if (i == solv->nrules) i = 1; r = solv->rules + i; @@ -2379,22 +2362,27 @@ solver_run_sat(Solver *solv, int disablerules, int doweak) } } + if (dq.count > 1 && postponed >= 0) + { + policy_filter_unwanted(solv, &dq, POLICY_MODE_CHOOSE_NOREORDER); + if (dq.count > 1) + { + if (!postponed) + postponed = i; + continue; + } + } + olevel = level; level = selectandinstall(solv, level, &dq, disablerules, r - solv->rules); - if (level == 0) - break; /* unsolvable */ - if (level < systemlevel || level == 1) + if (level < systemlevel) break; /* trouble */ /* something changed, so look at all rules again */ n = 0; } - if (n != solv->nrules) /* ran into trouble? */ - { - if (level == 0) - break; /* unsolvable */ - continue; /* start over */ - } + if (n < solv->nrules) /* ran into trouble? */ + continue; /* start over */ /* decide leftover cleandeps packages */ if (solv->cleandepsmap.size && solv->installed) @@ -2522,42 +2510,15 @@ solver_run_sat(Solver *solv, int disablerules, int doweak) /* filter out all already supplemented packages if requested */ if (!solv->addalreadyrecommended && dqs.count) { - int dosplitprovides_old = solv->dosplitprovides; - /* 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]; - } - solv->dosplitprovides = 0; /* filter out old supplements */ for (i = j = 0; i < dqs.count; i++) { p = dqs.elements[i]; s = pool->solvables + p; - if (!s->supplements) - continue; - if (!solver_is_supplementing(solv, s)) - dqs.elements[j++] = p; - else if (solv->installsuppdepq && solver_check_installsuppdepq(solv, s)) + if (s->supplements && solver_is_supplementing_alreadyinstalled(solv, s)) dqs.elements[j++] = p; } dqs.count = j; - /* undo turning off */ - for (i = 0; i < solv->decisionq.count; i++) - { - p = solv->decisionq.elements[i]; - if (p < 0) - continue; - s = pool->solvables + p; - if (s->repo && s->repo != solv->installed) - solv->decisionmap[p] = -solv->decisionmap[p]; - } - solv->dosplitprovides = dosplitprovides_old; } /* multiversion doesn't mix well with supplements. @@ -2604,8 +2565,6 @@ solver_run_sat(Solver *solv, int disablerules, int doweak) else POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended %s\n", pool_solvid2str(pool, p)); level = setpropagatelearn(solv, level, p, 0, 0); - if (level == 0) - break; continue; /* back to main loop */ } @@ -2632,8 +2591,6 @@ solver_run_sat(Solver *solv, int disablerules, int doweak) if (i < dqs.count || solv->decisionq.count < decisioncount) { map_free(&dqmap); - if (level == 0) - break; continue; } @@ -2673,13 +2630,10 @@ solver_run_sat(Solver *solv, int disablerules, int doweak) if (!dq.count) continue; if (dq.count > 1) - { - /* multiple candidates, open a branch */ - queue_push(&solv->branches, -dq.elements[0]); - for (i = 1; i < dq.count; i++) - queue_push(&solv->branches, dq.elements[i]); - queue_push(&solv->branches, level); - } + 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; @@ -2691,8 +2645,6 @@ solver_run_sat(Solver *solv, int disablerules, int doweak) break; /* had a problem above, quit loop */ } map_free(&dqmap); - if (level == 0) - break; continue; /* back to main loop so that all deps are checked */ } } @@ -2722,11 +2674,7 @@ solver_run_sat(Solver *solv, int disablerules, int doweak) break; } if (installedone || i < solv->orphaned.count) - { - if (level == 0) - break; - continue; /* back to main loop */ - } + continue; /* back to main loop */ for (i = 0; i < solv->orphaned.count; i++) { p = solv->orphaned.elements[i]; @@ -2739,11 +2687,7 @@ solver_run_sat(Solver *solv, int disablerules, int doweak) break; } if (i < solv->orphaned.count) - { - if (level == 0) - break; - continue; /* back to main loop */ - } + continue; /* back to main loop */ if (solv->brokenorphanrules) { solver_check_brokenorphanrules(solv, &dq); @@ -2759,8 +2703,6 @@ solver_run_sat(Solver *solv, int disablerules, int doweak) if (level < olevel) break; } - if (level == 0) - break; continue; } } @@ -2783,21 +2725,14 @@ solver_run_sat(Solver *solv, int disablerules, int doweak) break; } if (p < solv->installed->end) - { - if (level == 0) - break; - continue; /* back to main loop */ - } + continue; /* back to main loop */ } - if (solv->installed && solv->cleandepsmap.size) + if (solv->installed && solv->cleandepsmap.size && cleandeps_check_mistakes(solv)) { - if (cleandeps_check_mistakes(solv, level)) - { - level = 1; /* restart from scratch */ - systemlevel = level + 1; - continue; - } + solver_reset(solv); + level = 0; /* restart from scratch */ + continue; } if (solv->solution_callback) @@ -2806,7 +2741,6 @@ solver_run_sat(Solver *solv, int disablerules, int doweak) if (solv->branches.count) { int l, endi = 0; - Id why; p = l = 0; for (i = solv->branches.count - 1; i >= 0; i--) { @@ -2815,6 +2749,7 @@ solver_run_sat(Solver *solv, int disablerules, int doweak) { endi = i + 1; l = p; + i -= 3; /* skip: p data count */ } else if (p > 0) break; @@ -2825,23 +2760,7 @@ solver_run_sat(Solver *solv, int disablerules, int doweak) { while (i > 0 && solv->branches.elements[i - 1] > 0) i--; - p = solv->branches.elements[i]; - solv->branches.elements[i] = -p; - while (i > 0 && solv->branches.elements[i - 1] < 0) - i--; - POOL_DEBUG(SOLV_DEBUG_SOLVER, "branching with %s\n", pool_solvid2str(pool, p)); - queue_empty(&dq); - queue_insertn(&dq, 0, endi - i, solv->branches.elements + i); - level = l; - revert(solv, level); - queue_insertn(&solv->branches, solv->branches.count, dq.count, dq.elements); - /* 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); - olevel = level; - level = setpropagatelearn(solv, level, p, disablerules, why); - if (level == 0) - break; + level = takebranch(solv, i, endi, "branching", disablerules); continue; } } @@ -2852,84 +2771,51 @@ solver_run_sat(Solver *solv, int disablerules, int doweak) /* auto-minimization step */ if (solv->branches.count) { - int l = 0, lasti = -1, lastsi = -1, endi = 0; - Id why; - p = l = 0; + int endi, lasti = -1, lastiend = -1; if (solv->recommends_index < solv->decisionq.count) policy_update_recommendsmap(solv); - for (i = solv->branches.count - 1; i >= 0; i--) + for (endi = solv->branches.count; endi > 0;) { - p = solv->branches.elements[i]; - if (p > 0 && !l) - { - l = p; - endi = i + 1; - lastsi = -1; - } - else if (p > 0) + int l, lastsi = -1, starti = endi - solv->branches.elements[endi - 2]; + l = solv->branches.elements[endi - 1]; + for (i = starti; i < endi - 4; i++) { - if (solv->decisionmap[p] > l + 1) - lasti = i; - else + p = solv->branches.elements[i]; + if (p <= 0) + continue; + if (solv->decisionmap[p] > l) { - if (MAPTST(&solv->recommendsmap, p) || solver_is_supplementing(solv, pool->solvables + p)) - { - lastsi = p; - } + lasti = i; + lastiend = endi; + lastsi = -1; + break; } + if (lastsi < 0 && (MAPTST(&solv->recommendsmap, p) || solver_is_supplementing(solv, pool->solvables + p))) + lastsi = i; } - else if (p < 0) + if (lastsi >= 0) { - l = 0; - 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 = -p; - if (solv->decisionmap[p] == l) + 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))) { - if (!(MAPTST(&solv->recommendsmap, p) || solver_is_supplementing(solv, pool->solvables + p))) - lasti = lastsi; + lasti = lastsi; + lastiend = endi; + break; } } } + endi = starti; } if (lasti >= 0) { - int starti; - /* find start of branch */ - for (i = lasti; i && solv->branches.elements[i] >= 0; ) - i--; - while (i > 0 && solv->branches.elements[i] < 0) - i--; - starti = i ? i + 1 : 0; -#if 0 - printf("minimization group level %d [%d-%d]:\n", solv->branches.elements[endi - 1], starti, endi); - for (i = starti; i < endi - 1; i++) - printf("%c %c%s\n", i == lasti ? 'x' : ' ', solv->branches.elements[i] >= 0 ? ' ' : '-', pool_solvid2str(pool, solv->branches.elements[i] >= 0 ? solv->branches.elements[i] : -solv->branches.elements[i])); -#endif - l = solv->branches.elements[endi - 1]; - p = solv->branches.elements[lasti]; - solv->branches.elements[lasti] = -p; - POOL_DEBUG(SOLV_DEBUG_SOLVER, "minimizing %d -> %d with %s\n", solv->decisionmap[p], l, pool_solvid2str(pool, p)); minimizationsteps++; - queue_empty(&dq); - for (i = starti; i < endi - 1; i++) - if (solv->branches.elements[i] < 0) - queue_push(&dq, solv->branches.elements[i]); - for (i = starti; i < endi; i++) - if (solv->branches.elements[i] > 0) - queue_push(&dq, solv->branches.elements[i]); - if (dq.elements[dq.count - 2] <= 0) - queue_empty(&dq); - level = l; - revert(solv, level); - queue_insertn(&solv->branches, solv->branches.count, dq.count, dq.elements); - /* 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); - olevel = level; - level = setpropagatelearn(solv, level, p, disablerules, why); - if (level == 0) - break; + level = takebranch(solv, lasti, lastiend, "minimizing", disablerules); continue; /* back to main loop */ } } @@ -2942,7 +2828,7 @@ solver_run_sat(Solver *solv, int disablerules, int doweak) POOL_DEBUG(SOLV_DEBUG_STATS, "done solving.\n\n"); queue_free(&dq); queue_free(&dqs); - if (level == 0) + if (level < 0) { /* unsolvable */ solv->decisioncnt_jobs = solv->decisionq.count; @@ -3087,7 +2973,7 @@ weaken_solvable_deps(Solver *solv, Id p) int i; Rule *r; - for (i = 1, r = solv->rules + i; i < solv->rpmrules_end; i++, r++) + for (i = 1, r = solv->rules + i; i < solv->pkgrules_end; i++, r++) { if (r->p != -p) continue; @@ -3145,9 +3031,9 @@ solver_calculate_noobsmap(Pool *pool, Queue *job, Map *multiversionmap) * add a rule created by a job, record job number and weak flag */ static inline void -solver_addjobrule(Solver *solv, Id p, Id d, Id job, int weak) +solver_addjobrule(Solver *solv, Id p, Id p2, Id d, Id job, int weak) { - solver_addrule(solv, p, d); + solver_addrule(solv, p, p2, d); queue_push(&solv->ruletojob, job); if (weak) queue_push(&solv->weakruleq, solv->nrules - 1); @@ -3289,7 +3175,7 @@ addedmap2deduceq(Solver *solv, Map *addedmap) Rule *r; queue_empty(&solv->addedmap_deduceq); - for (i = 2, j = solv->rpmrules_end - 1; i < pool->nsolvables && j > 0; j--) + for (i = 2, j = solv->pkgrules_end - 1; i < pool->nsolvables && j > 0; j--) { r = solv->rules + j; if (r->p >= 0) @@ -3325,7 +3211,7 @@ deduceq2addedmap(Solver *solv, Map *addedmap) int j; Id p; Rule *r; - for (j = solv->rpmrules_end - 1; j > 0; j--) + for (j = solv->pkgrules_end - 1; j > 0; j--) { r = solv->rules + j; if (r->d < 0 && r->p) @@ -3347,6 +3233,39 @@ deduceq2addedmap(Solver *solv, Map *addedmap) } } +#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 /* * @@ -3361,7 +3280,7 @@ solver_solve(Solver *solv, Queue *job) Repo *installed = solv->installed; int i; int oldnrules, initialnrules; - Map addedmap; /* '1' == have rpm-rules for solvable */ + Map addedmap; /* '1' == have pkg-rules for solvable */ Map installcandidatemap; Id how, what, select, name, weak, p, pp, d; Queue q; @@ -3401,6 +3320,7 @@ solver_solve(Solver *solv, Queue *job) 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); @@ -3463,16 +3383,16 @@ solver_solve(Solver *solv, Queue *job) 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->rpmrules_end ? solv->rpmrules_end : 1; + 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->rpmrules_end = 0; + solv->pkgrules_end = 0; if (installed) { @@ -3586,12 +3506,12 @@ solver_solve(Solver *solv, Queue *job) oldnrules = solv->nrules; FOR_REPO_SOLVABLES(installed, p, s) - solver_addrpmrulesforsolvable(solv, s, &addedmap); - POOL_DEBUG(SOLV_DEBUG_STATS, "added %d rpm rules for installed solvables\n", solv->nrules - oldnrules); + 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) - solver_addrpmrulesforupdaters(solv, s, &addedmap, 1); - POOL_DEBUG(SOLV_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); } /* @@ -3612,7 +3532,7 @@ solver_solve(Solver *solv, Queue *job) FOR_JOB_SELECT(p, pp, select, what) { MAPSET(&installcandidatemap, p); - solver_addrpmrulesforsolvable(solv, pool->solvables + p, &addedmap); + solver_addpkgrulesforsolvable(solv, pool->solvables + p, &addedmap); } break; case SOLVER_DISTUPGRADE: @@ -3623,31 +3543,31 @@ solver_solve(Solver *solv, Queue *job) if (how & SOLVER_FORCEBEST) solv->bestupdatemap_all = 1; } - if (!solv->dupmap_all) + if (!solv->dupmap_all || solv->allowuninstall) hasdupjob = 1; break; default: break; } } - POOL_DEBUG(SOLV_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); /* * add rules for suggests, enhances */ oldnrules = solv->nrules; - solver_addrpmrulesforweak(solv, &addedmap); - POOL_DEBUG(SOLV_DEBUG_STATS, "added %d rpm rules because of weak dependencies\n", solv->nrules - oldnrules); + 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; - solver_addrpmrulesforlinked(solv, &addedmap); - POOL_DEBUG(SOLV_DEBUG_STATS, "added %d rpm rules because of linked packages\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 rpm rules we need. + * 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, @@ -3668,14 +3588,14 @@ solver_solve(Solver *solv, Queue *job) } if (solv->nrules > initialnrules) - solver_unifyrules(solv); /* remove duplicate rpm rules */ - solv->rpmrules_end = solv->nrules; /* mark end of rpm rules */ + solver_unifyrules(solv); /* remove duplicate pkg rules */ + solv->pkgrules_end = solv->nrules; /* mark end of pkg rules */ if (solv->nrules > initialnrules) addedmap2deduceq(solv, &addedmap); /* so that we can recreate the addedmap */ - POOL_DEBUG(SOLV_DEBUG_STATS, "rpm rule memory used: %d K\n", solv->nrules * (int)sizeof(Rule) / 1024); - POOL_DEBUG(SOLV_DEBUG_STATS, "rpm rule creation took %d ms\n", solv_timems(now)); + 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)); /* create dup maps if needed. We need the maps early to create our * update rules */ @@ -3702,7 +3622,7 @@ solver_solve(Solver *solv, Queue *job) { if (s->repo != installed) { - solver_addrule(solv, 0, 0); /* create dummy rule */ + solver_addrule(solv, 0, 0, 0); /* create dummy rule */ continue; } solver_addupdaterule(solv, s, 1); /* allow s to be updated */ @@ -3730,7 +3650,7 @@ solver_solve(Solver *solv, Queue *job) if (s->repo != installed) { - solver_addrule(solv, 0, 0); /* create dummy rule */ + solver_addrule(solv, 0, 0, 0); /* create dummy rule */ continue; } solver_addupdaterule(solv, s, 0); /* allowall = 0: downgrades not allowed */ @@ -3781,6 +3701,15 @@ solver_solve(Solver *solv, Queue *job) 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); @@ -3811,7 +3740,7 @@ solver_solve(Solver *solv, Queue *job) queue_pushunique(solv->installsuppdepq, rd->evr == 0 ? rd->name : what); } } - solver_addjobrule(solv, p, d, i, weak); + solver_addjobrule(solv, p, 0, d, i, weak); if (how & SOLVER_FORCEBEST) hasbestinstalljob = 1; break; @@ -3824,21 +3753,29 @@ solver_solve(Solver *solv, Queue *job) if (select == SOLVER_SOLVABLE_ALL) /* hmmm ;) */ { FOR_POOL_SOLVABLES(p) - solver_addjobrule(solv, -p, 0, i, weak); + 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, i, weak); + 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, i, weak); + 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 @@ -3866,7 +3803,7 @@ solver_solve(Solver *solv, Queue *job) if (solv->rules[j].p == -p) break; if (j == k) - solver_addjobrule(solv, -p, 0, i, weak); /* remove by id */ + solver_addjobrule(solv, -p, 0, 0, i, weak); /* remove by id */ } } break; @@ -3892,17 +3829,17 @@ solver_solve(Solver *solv, Queue *job) if (select == SOLVER_SOLVABLE_ALL) { FOR_POOL_SOLVABLES(p) - solver_addjobrule(solv, installed && pool->solvables[p].repo == installed ? p : -p, 0, i, weak); + 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, i, weak); + 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, i, weak); + 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)); @@ -3963,6 +3900,11 @@ solver_solve(Solver *solv, Queue *job) 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 @@ -3983,15 +3925,18 @@ solver_solve(Solver *solv, Queue *job) map_free(&installcandidatemap); queue_free(&q); - POOL_DEBUG(SOLV_DEBUG_STATS, "%d rpm rules, 2 * %d update rules, %d job rules, %d infarch rules, %d dup rules, %d choice rules, %d best rules\n", solv->rpmrules_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, "%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) { - p = solv->weakruleq.elements[i]; - MAPSET(&solv->weakrulemap, p); + 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 */ @@ -4023,10 +3968,6 @@ solver_solve(Solver *solv, Queue *job) if (solv->dupmap_all && solv->orphaned.count && solv->break_orphans) solver_breakorphans(solv); - /* make initial decisions based on assertion rules */ - makeruledecisions(solv); - POOL_DEBUG(SOLV_DEBUG_SOLVER, "problems so far: %d\n", solv->problems.count); - /* * ******************************************** * solve! @@ -4643,21 +4584,69 @@ get_userinstalled_cmp_names(const void *ap, const void *bp, void *dp) return strcmp(pool_id2str(pool, *(Id *)ap), pool_id2str(pool, *(Id *)bp)); } +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])); +} + static void get_userinstalled_sort_uniq(Pool *pool, Queue *q, int flags) { - Id lastp = -1; + Id lastp = -1, lasta = -1; int i, j; - if ((flags & GET_USERINSTALLED_NAMES) != 0) + 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); - for (i = j = 0; i < q->count; i++) - if (q->elements[i] != lastp) - q->elements[j++] = lastp = q->elements[i]; + 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); } +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); + } + } +} + void solver_get_userinstalled(Solver *solv, Queue *q, int flags) { @@ -4767,8 +4756,20 @@ solver_get_userinstalled(Solver *solv, Queue *q, int flags) } } map_free(&userinstalled); - /* convert to names if asked */ - if ((flags & GET_USERINSTALLED_NAMES) != 0) + + /* 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++) { @@ -4777,9 +4778,9 @@ solver_get_userinstalled(Solver *solv, Queue *q, int flags) } } /* sort and unify */ - if (q->count > 1) - get_userinstalled_sort_uniq(pool, q, flags); - /* invert if asked */ + get_userinstalled_sort_uniq(pool, q, flags); + + /* invert if asked for */ if ((flags & GET_USERINSTALLED_INVERTED) != 0) { /* first generate queue with all installed packages */ @@ -4793,30 +4794,52 @@ solver_get_userinstalled(Solver *solv, Queue *q, int flags) s = pool->solvables + p; if (!s->repo) continue; - if ((flags & GET_USERINSTALLED_NAMES) != 0) + 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); - if (invq.count > 1) - get_userinstalled_sort_uniq(pool, &invq, flags); + get_userinstalled_sort_uniq(pool, &invq, flags); /* subtract queues (easy as they are sorted and invq is a superset of q) */ - if (q->count) + if ((flags & GET_USERINSTALLED_NAMEARCH) != 0) { - 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); + if (q->count) + { + 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]); + } + else + { + if (q->count) + { + 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]); } - for (i = j = 0; i < invq.count; i++) - if (invq.elements[i]) - queue_push(q, invq.elements[i]); queue_free(&invq); } } @@ -4826,7 +4849,7 @@ pool_add_userinstalled_jobs(Pool *pool, Queue *q, Queue *job, int flags) { int i; - if (flags & GET_USERINSTALLED_INVERTED) + if ((flags & GET_USERINSTALLED_INVERTED) != 0) { Queue invq; Id p, lastid; @@ -4835,13 +4858,25 @@ pool_add_userinstalled_jobs(Pool *pool, Queue *q, Queue *job, int flags) 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); - queue_insertn(&invq, invq.count, q->count, q->elements); - if (invq.count > 1) - 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 ((flags & GET_USERINSTALLED_NAMEARCH) != 0) + { + /* 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; + } + 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) @@ -4869,9 +4904,62 @@ pool_add_userinstalled_jobs(Pool *pool, Queue *q, Queue *job, int flags) } 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 (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]); + } + } +} + +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--) + { + Id p = -elements[-i]; + if (p > 0 && solv->decisionmap[p] == elements[-1] + 1) + { + *chosenp = p; + break; + } + } } + if (choices) + queue_insertn(choices, 0, elements[-2] - 4, elements - elements[-2]); + return elements[-4] ? SOLVER_ALTERNATIVE_TYPE_RECOMMENDS : SOLVER_ALTERNATIVE_TYPE_RULE; } const char * @@ -5013,3 +5101,37 @@ pool_job2str(Pool *pool, Id how, Id what, Id flagmask) 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); + } + return "unknown alternative type"; +} +