From 42f00b0f81834d61893165bf2486ee2771fe2446 Mon Sep 17 00:00:00 2001 From: Michael Schroeder Date: Mon, 25 May 2009 16:29:00 +0200 Subject: [PATCH] - move create_obsolete_index to policy.c - add (unused) pool_match_dep function - add multiversion supplements workaround (bnc#501088) - move systemsolvable decision to makeruledecisions to make the code easier to understand --- src/policy.c | 79 +++++++++++++++++++ src/policy.h | 2 + src/pool.c | 57 ++++++++++++++ src/pool.h | 1 + src/solver.c | 243 ++++++++++++++++++++--------------------------------------- src/solver.h | 1 - 6 files changed, 220 insertions(+), 163 deletions(-) diff --git a/src/policy.c b/src/policy.c index fe5c570..64274ec 100644 --- a/src/policy.c +++ b/src/policy.c @@ -433,6 +433,85 @@ policy_illegal_vendorchange(Solver *solv, Solvable *s1, Solvable *s2) } +/*------------------------------------------------------------------- + * + * 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() below. + */ +void +policy_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, cnt; + + if (!installed || installed->start == installed->end) + return; + cnt = installed->end - installed->start; + solv->obsoletes = obsoletes = sat_calloc(cnt, 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) + { + FOR_PROVIDES(p, pp, obs) + { + 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]++; + } + } + } + n = 0; + for (i = 0; i < cnt; 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 (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; + } + } + } +} + + /* * find update candidates * diff --git a/src/policy.h b/src/policy.h index 5574572..4c69177 100644 --- a/src/policy.h +++ b/src/policy.h @@ -63,3 +63,5 @@ extern void policy_findupdatepackages(Solver *solv, Queue *qs, int allowall); /* do not regard policies for vendor,architecuture,... change */ +extern void policy_create_obsolete_index(Solver *solv); + diff --git a/src/pool.c b/src/pool.c index 49cc911..e375b91 100644 --- a/src/pool.c +++ b/src/pool.c @@ -457,8 +457,65 @@ pool_match_nevr_rel(Pool *pool, Solvable *s, Id d) return 1; if (flags != 2 && flags != 5) flags ^= 5; +#ifdef DEBIAN_SEMANTICS + if ((flags & (1 << (1 + evrcmp(pool, s->evr, evr, EVRCMP_COMPARE)))) != 0) + return 1; +#else if ((flags & (1 << (1 + evrcmp(pool, s->evr, evr, EVRCMP_MATCH_RELEASE)))) != 0) return 1; +#endif + return 0; +} + +/* match two dependencies */ + +int +pool_match_dep(Pool *pool, Id d1, Id d2) +{ + Reldep *rd1, *rd2; + int pflags, flags; + + if (d1 == d2) + return 1; + if (!ISRELDEP(d1)) + { + if (!ISRELDEP(d2)) + return 0; + rd2 = GETRELDEP(pool, d2); + return pool_match_dep(pool, d1, rd2->name); + } + rd1 = GETRELDEP(pool, d1); + if (!ISRELDEP(d2)) + { + return pool_match_dep(pool, rd1->name, d2); + } + rd2 = GETRELDEP(pool, d2); + if (!pool_match_dep(pool, rd1->name, rd2->name)) + return 0; + pflags = rd1->flags; + flags = rd2->flags; + if (!pflags || !flags || pflags >= 8 || flags >= 8) + return 0; + if (flags == 7 || pflags == 7) + return 1; + if ((pflags & flags & 5) != 0) + return 1; + if (rd1->evr == rd2->evr) + { + if ((pflags & flags & 2) != 0) + return 1; + } + else + { + int f = flags == 5 ? 5 : flags == 2 ? pflags : (flags ^ 5) & (pflags | 5); +#ifdef DEBIAN_SEMANTICS + if ((f & (1 << (1 + evrcmp(pool, rd1->evr, rd2->evr, EVRCMP_COMPARE)))) != 0) + return 1; +#else + if ((f & (1 << (1 + evrcmp(pool, rd1->evr, rd2->evr, EVRCMP_MATCH_RELEASE)))) != 0) + return 1; +#endif + } return 0; } diff --git a/src/pool.h b/src/pool.h index 55c047b..4766fb0 100644 --- a/src/pool.h +++ b/src/pool.h @@ -207,6 +207,7 @@ int solvable_trivial_installable_queue(Solvable *s, Queue *installed); void pool_create_state_maps(Pool *pool, Queue *installed, Map *installedmap, Map *conflictsmap); int pool_match_nevr_rel(Pool *pool, Solvable *s, Id d); +int pool_match_dep(Pool *pool, Id d1, Id d2); static inline int pool_match_nevr(Pool *pool, Solvable *s, Id d) { diff --git a/src/solver.c b/src/solver.c index 460432d..7ba6449 100644 --- a/src/solver.c +++ b/src/solver.c @@ -369,9 +369,9 @@ addrule(Solver *solv, Id p, Id d) n = 1; /* re-set n, was used as temp var */ } - /* - * check for duplicate - */ + /* + * 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) @@ -392,9 +392,9 @@ addrule(Solver *solv, Id p, Id d) return r; } - /* - * allocate new rule - */ + /* + * allocate new rule + */ /* extend rule buffer */ solv->rules = sat_extend(solv->rules, solv->nrules, 1, sizeof(Rule), RULES_BLOCK); @@ -569,9 +569,8 @@ enableproblem(Solver *solv, Id v) /* * 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. + * Go through rules and add direct assertions to the decisionqueue. + * If we find a conflict, disable rules and add them to problem queue. */ static void @@ -585,6 +584,12 @@ makeruledecisions(Solver *solv) POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- makeruledecisions ; size decisionq: %d -----\n",solv->decisionq.count); + /* The system solvable is always installed first */ + assert(solv->decisionq.count == 0); + queue_push(&solv->decisionq, SYSTEMSOLVABLE); + queue_push(&solv->decisionq_why, 0); + solv->decisionmap[SYSTEMSOLVABLE] = 1; /* installed at level '1' */ + decisionstart = solv->decisionq.count; for (ii = 0; ii < solv->ruleassertions.count; ii++) { @@ -654,9 +659,9 @@ makeruledecisions(Solver *solv) break; assert(i < solv->decisionq.count); /* assert that we found it */ - /* - * conflict with system solvable ? - */ + /* + * conflict with system solvable ? + */ if (v == -SYSTEMSOLVABLE) { /* conflict with system solvable */ @@ -676,9 +681,9 @@ makeruledecisions(Solver *solv) assert(solv->decisionq_why.elements[i] > 0); - /* - * conflict with an rpm rule ? - */ + /* + * conflict with an rpm rule ? + */ if (solv->decisionq_why.elements[i] < solv->rpmrules_end) { @@ -699,9 +704,9 @@ makeruledecisions(Solver *solv) continue; } - /* - * conflict with another job or update/feature rule - */ + /* + * conflict with another job or update/feature rule + */ /* record proof */ queue_push(&solv->problems, solv->learnt_pool.count); @@ -741,10 +746,10 @@ makeruledecisions(Solver *solv) } queue_push(&solv->problems, 0); - /* - * start over - * (back up from decisions) - */ + /* + * start over + * (back up from decisions) + */ while (solv->decisionq.count > decisionstart) { v = solv->decisionq.elements[--solv->decisionq.count]; @@ -755,9 +760,9 @@ makeruledecisions(Solver *solv) ii = -1; /* restarts loop at 0 */ } - /* - * phase 2: now do the weak assertions - */ + /* + * phase 2: now do the weak assertions + */ for (ii = 0; ii < solv->ruleassertions.count; ii++) { ri = solv->ruleassertions.elements[ii]; @@ -768,10 +773,10 @@ makeruledecisions(Solver *solv) continue; v = r->p; vv = v > 0 ? v : -v; - /* - * decide ! - * (if not yet decided) - */ + /* + * decide ! + * (if not yet decided) + */ if (!solv->decisionmap[vv]) { queue_push(&solv->decisionq, v); @@ -787,9 +792,9 @@ makeruledecisions(Solver *solv) } continue; } - /* - * previously decided, sane ? - */ + /* + * previously decided, sane ? + */ if (v > 0 && solv->decisionmap[vv] > 0) continue; if (v < 0 && solv->decisionmap[vv] < 0) @@ -1808,10 +1813,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 @@ -2172,17 +2177,14 @@ reset_solver(Solver *solv) int i; Id v; - /* rewind decisions to direct rpm rule assertions */ - for (i = solv->decisionq.count - 1; i >= solv->directdecisions; i--) + /* rewind all decisions */ + for (i = solv->decisionq.count - 1; i >= 0; i--) { v = solv->decisionq.elements[i]; solv->decisionmap[v > 0 ? v : -v] = 0; } - - POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "decisions done reduced from %d to %d\n", solv->decisionq.count, solv->directdecisions); - - solv->decisionq_why.count = solv->directdecisions; - solv->decisionq.count = solv->directdecisions; + solv->decisionq_why.count = 0; + solv->decisionq.count = 0; solv->recommends_index = -1; solv->propagate_index = 0; @@ -2510,6 +2512,7 @@ setpropagatelearn(Solver *solv, int level, Id decision, int disablerules, Id rul /* learnt rule is an assertion */ queue_push(&solv->ruleassertions, r - solv->rules); } + /* the new rule is unit by design */ solv->decisionmap[p > 0 ? p : -p] = p > 0 ? level : -level; queue_push(&solv->decisionq, p); queue_push(&solv->decisionq_why, r - solv->rules); @@ -3132,6 +3135,29 @@ run_solver(Solver *solv, int disablerules, int doweak) } } + /* multiversion doesn't mix well with supplements. + * filter supplemented packages where we already decided + * to install a different version (see bnc#501088) */ + if (dqs.count && solv->noobsoletes.size) + { + for (i = j = 0; i < dqs.count; i++) + { + p = dqs.elements[i]; + if (MAPTST(&solv->noobsoletes, p)) + { + Id p2, pp2; + s = pool->solvables + p; + FOR_PROVIDES(p2, pp2, s->name) + if (solv->decisionmap[p2] > 0 && pool->solvables[p2].name == s->name) + break; + if (p2) + continue; /* ignore this package */ + } + dqs.elements[j++] = p; + } + dqs.count = j; + } + /* make dq contain both recommended and supplemented pkgs */ if (dqs.count) { @@ -3139,7 +3165,6 @@ run_solver(Solver *solv, int disablerules, int doweak) queue_pushunique(&dq, dqs.elements[i]); } -#if 1 if (dq.count) { Map dqmap; @@ -3155,11 +3180,13 @@ run_solver(Solver *solv, int disablerules, int doweak) POOL_DEBUG(SAT_DEBUG_POLICY, "installing recommended %s\n", solvid2str(pool, p)); queue_push(&solv->recommendations, p); level = setpropagatelearn(solv, level, p, 0, 0); - continue; + continue; /* back to main loop */ } - /* filter and create a map of result */ + /* 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]); @@ -3226,34 +3253,15 @@ run_solver(Solver *solv, int disablerules, int doweak) olevel = level; level = setpropagatelearn(solv, level, p, 0, 0); if (level <= olevel || solv->decisionq.count < decisioncount) - break; + break; /* we had to revert some decisions */ } if (rec) break; /* had a problem above, quit loop */ } map_free(&dqmap); - continue; - } -#else - if (dq.count) - { - if (dq.count > 1) - policy_filter_unwanted(solv, &dq, POLICY_MODE_RECOMMEND); - p = dq.elements[0]; - /* prefer recommended patterns (bnc#450226) */ - /* real fix is to minimize recommended packages as well */ - for (i = 0; i < dq.count; i++) - if (!strncmp(id2str(pool, pool->solvables[dq.elements[i]].name), "pattern:", 8)) - { - p = dq.elements[i]; - break; - } - POOL_DEBUG(SAT_DEBUG_POLICY, "installing recommended %s\n", solvid2str(pool, p)); - queue_push(&solv->recommendations, p); - level = setpropagatelearn(solv, level, p, 0, 0); - continue; + + continue; /* back to main loop */ } -#endif } if (solv->distupgrade && solv->installed) @@ -4037,87 +4045,6 @@ solver_findallproblemrules(Solver *solv, Id problem, Queue *rules) /*------------------------------------------------------------------- * - * 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, cnt; - - if (!installed || installed->start == installed->end) - return; - cnt = installed->end - installed->start; - solv->obsoletes = obsoletes = sat_calloc(cnt, 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) - { - FOR_PROVIDES(p, pp, obs) - { - 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]++; - } - } - } - n = 0; - for (i = 0; i < cnt; 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 (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; - } - } - } -} - - -/*------------------------------------------------------------------- - * * remove disabled conflicts * * purpose: update the decisionmap after some rules were disabled. @@ -4251,6 +4178,7 @@ weaken_solvable_deps(Solver *solv, Id p) } } + /********************************************************************/ /* main() */ @@ -4692,7 +4620,7 @@ solver_solve(Solver *solv, Queue *job) pool_createwhatprovides(pool); /* create obsolete index */ - create_obsolete_index(solv); + policy_create_obsolete_index(solv); /* remember job */ queue_free(&solv->job); @@ -4718,17 +4646,11 @@ solver_solve(Solver *solv, Queue *job) } 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); /* * create rules for all package that could be involved with the solving @@ -4816,9 +4738,7 @@ solver_solve(Solver *solv, Queue *job) solv->rpmrules_end = solv->nrules; /* mark end of rpm rules */ - 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 @@ -5107,6 +5027,9 @@ solver_solve(Solver *solv, Queue *job) /* 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++) @@ -5118,10 +5041,6 @@ solver_solve(Solver *solv, Queue *job) /* make decisions based on job/update assertions */ makeruledecisions(solv); - - /* create watches chains */ - makewatches(solv); - POOL_DEBUG(SAT_DEBUG_STATS, "problems so far: %d\n", solv->problems.count); /* diff --git a/src/solver.h b/src/solver.h index 5330d3a..2c2a2b1 100644 --- a/src/solver.h +++ b/src/solver.h @@ -120,7 +120,6 @@ typedef struct _Solver { /* our decisions: */ Queue decisionq; /* >0:install, <0:remove/conflict */ Queue decisionq_why; /* index of rule, Offset into rules */ - int directdecisions; /* number of decisions with no rule */ Id *decisionmap; /* map for all available solvables, * = 0: undecided -- 2.7.4