2 * Copyright (c) 2007-2008, Novell Inc.
4 * This program is licensed under the BSD license, read LICENSE.BSD
5 * for further information
11 * SAT based dependency solver
21 #include "solver_private.h"
27 #include "solverdebug.h"
29 #include "linkedpkg.h"
31 #define RULES_BLOCK 63
33 /********************************************************************
35 * dependency check helpers
39 /*-------------------------------------------------------------------
40 * handle split provides
42 * a splitprovides dep looks like
43 * namespace:splitprovides(pkg REL_WITH path)
44 * and is only true if pkg is installed and contains the specified path.
45 * we also make sure that pkg is selected for an update, otherwise the
46 * update would always be forced onto the user.
47 * Map m is the map used when called from dep_possible.
51 solver_is_updating(Solver *solv, Id p)
53 /* check if the update rule is true */
54 Pool *pool = solv->pool;
57 if (solv->decisionmap[p] >= 0)
58 return 0; /* old package stayed */
59 r = solv->rules + solv->updaterules + (p - solv->installed->start);
60 FOR_RULELITERALS(l, pp, r)
61 if (l > 0 && l != p && solv->decisionmap[l] > 0)
67 solver_splitprovides(Solver *solv, Id dep, Map *m)
69 Pool *pool = solv->pool;
74 if (!solv->dosplitprovides || !solv->installed)
78 rd = GETRELDEP(pool, dep);
79 if (rd->flags != REL_WITH)
82 * things are a bit tricky here if pool->addedprovides == 1, because most split-provides are in
83 * a non-standard location. If we simply call pool_whatprovides, we'll drag in the complete
84 * file list. Instead we rely on pool_addfileprovides ignoring the addfileprovidesfiltered flag
85 * for installed packages and check the lazywhatprovidesq (ignoring the REL_WITH part, but
86 * we filter the package name further down anyway).
88 if (pool->addedfileprovides == 1 && !ISRELDEP(rd->evr) && !pool->whatprovides[rd->evr])
89 pp = pool_searchlazywhatprovidesq(pool, rd->evr);
91 pp = pool_whatprovides(pool, dep);
92 while ((p = pool->whatprovidesdata[pp++]) != 0)
94 /* here we have packages that provide the correct name and contain the path,
95 * now do extra filtering */
96 s = pool->solvables + p;
97 if (s->repo != solv->installed || s->name != rd->name)
99 /* check if the package is updated. if m is set, we're called from dep_possible */
100 if (m || solver_is_updating(solv, p))
107 /*-------------------------------------------------------------------
108 * solver_dep_installed
112 solver_dep_installed(Solver *solv, Id dep)
115 Pool *pool = solv->pool;
120 Reldep *rd = GETRELDEP(pool, dep);
121 if (rd->flags == REL_AND)
123 if (!solver_dep_installed(solv, rd->name))
125 return solver_dep_installed(solv, rd->evr);
127 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
128 return solver_dep_installed(solv, rd->evr);
130 FOR_PROVIDES(p, pp, dep)
132 if (p == SYSTEMSOLVABLE || (solv->installed && pool->solvables[p].repo == solv->installed))
139 /* mirrors solver_dep_installed, but returns 2 if a
140 * dependency listed in solv->installsuppdepq was involved */
142 solver_check_installsuppdepq_dep(Solver *solv, Id dep)
144 Pool *pool = solv->pool;
150 Reldep *rd = GETRELDEP(pool, dep);
151 if (rd->flags == REL_AND)
153 int r2, r1 = solver_check_installsuppdepq_dep(solv, rd->name);
156 r2 = solver_check_installsuppdepq_dep(solv, rd->evr);
159 return r1 == 2 || r2 == 2 ? 2 : 1;
161 if (rd->flags == REL_OR)
163 int r2, r1 = solver_check_installsuppdepq_dep(solv, rd->name);
164 r2 = solver_check_installsuppdepq_dep(solv, rd->evr);
167 return r1 == 2 || r2 == 2 ? 2 : 1;
169 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
170 return solver_splitprovides(solv, rd->evr, 0);
171 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
172 return solver_dep_installed(solv, rd->evr);
173 if (rd->flags == REL_NAMESPACE && (q = solv->installsuppdepq) != 0)
176 for (i = 0; i < q->count; i++)
177 if (q->elements[i] == dep || q->elements[i] == rd->name)
181 FOR_PROVIDES(p, pp, dep)
182 if (solv->decisionmap[p] > 0)
188 solver_check_installsuppdepq(Solver *solv, Solvable *s)
191 supp = s->repo->idarraydata + s->supplements;
192 while ((sup = *supp++) != 0)
193 if (solver_check_installsuppdepq_dep(solv, sup) == 2)
199 autouninstall(Solver *solv, Id *problem)
201 Pool *pool = solv->pool;
203 int lastfeature = 0, lastupdate = 0;
207 for (i = 0; (v = problem[i]) != 0; i++)
210 extraflags &= solv->job.elements[-v - 1];
211 if (v >= solv->featurerules && v < solv->featurerules_end)
214 if (v >= solv->updaterules && v < solv->updaterules_end)
216 /* check if identical to feature rule */
217 Id p = solv->rules[v].p;
221 r = solv->rules + solv->featurerules + (p - solv->installed->start);
224 /* update rule == feature rule */
233 if (!lastupdate && !lastfeature)
235 v = lastupdate ? lastupdate : lastfeature;
236 POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "allowuninstall disabling ");
237 solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE, solv->rules + v);
238 solver_disableproblem(solv, v);
239 if (extraflags != -1 && (extraflags & SOLVER_CLEANDEPS) != 0 && solv->cleandepsmap.size)
241 /* add the package to the updatepkgs list, this will automatically turn
242 * on cleandeps mode */
243 Id p = solv->rules[v].p;
244 if (!solv->cleandeps_updatepkgs)
246 solv->cleandeps_updatepkgs = solv_calloc(1, sizeof(Queue));
247 queue_init(solv->cleandeps_updatepkgs);
251 int oldupdatepkgscnt = solv->cleandeps_updatepkgs->count;
252 queue_pushunique(solv->cleandeps_updatepkgs, p);
253 if (solv->cleandeps_updatepkgs->count != oldupdatepkgscnt)
254 solver_disablepolicyrules(solv);
260 /************************************************************************/
263 * enable/disable learnt rules
265 * we have enabled or disabled some of our rules. We now reenable all
266 * of our learnt rules except the ones that were learnt from rules that
270 enabledisablelearntrules(Solver *solv)
272 Pool *pool = solv->pool;
277 POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "enabledisablelearntrules called\n");
278 for (i = solv->learntrules, r = solv->rules + i; i < solv->nrules; i++, r++)
280 whyp = solv->learnt_pool.elements + solv->learnt_why.elements[i - solv->learntrules];
281 while ((why = *whyp++) != 0)
283 assert(why > 0 && why < i);
284 if (solv->rules[why].d < 0)
287 /* why != 0: we found a disabled rule, disable the learnt rule */
288 if (why && r->d >= 0)
290 IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS)
292 POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "disabling ");
293 solver_printruleclass(solv, SOLV_DEBUG_SOLUTIONS, r);
295 solver_disablerule(solv, r);
297 else if (!why && r->d < 0)
299 IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS)
301 POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "re-enabling ");
302 solver_printruleclass(solv, SOLV_DEBUG_SOLUTIONS, r);
304 solver_enablerule(solv, r);
311 * make assertion rules into decisions
313 * Go through rules and add direct assertions to the decisionqueue.
314 * If we find a conflict, disable rules and add them to problem queue.
318 makeruledecisions(Solver *solv)
320 Pool *pool = solv->pool;
325 int record_proof = 1;
327 int havedisabled = 0;
329 /* The system solvable is always installed first */
330 assert(solv->decisionq.count == 0);
331 queue_push(&solv->decisionq, SYSTEMSOLVABLE);
332 queue_push(&solv->decisionq_why, 0);
333 solv->decisionmap[SYSTEMSOLVABLE] = 1; /* installed at level '1' */
335 decisionstart = solv->decisionq.count;
338 /* if we needed to re-run, back up decisions to decisionstart */
339 while (solv->decisionq.count > decisionstart)
341 v = solv->decisionq.elements[--solv->decisionq.count];
342 --solv->decisionq_why.count;
344 solv->decisionmap[vv] = 0;
347 /* note that the ruleassertions queue is ordered */
348 for (ii = 0; ii < solv->ruleassertions.count; ii++)
350 ri = solv->ruleassertions.elements[ii];
351 r = solv->rules + ri;
353 if (havedisabled && ri >= solv->learntrules)
355 /* just started with learnt rule assertions. If we have disabled
356 * some rules, adapt the learnt rule status */
357 enabledisablelearntrules(solv);
361 if (r->d < 0 || !r->p || r->w2) /* disabled, dummy or no assertion */
364 /* do weak rules in phase 2 */
365 if (ri < solv->learntrules && MAPTST(&solv->weakrulemap, ri))
371 if (!solv->decisionmap[vv]) /* if not yet decided */
373 queue_push(&solv->decisionq, v);
374 queue_push(&solv->decisionq_why, r - solv->rules);
375 solv->decisionmap[vv] = v > 0 ? 1 : -1;
376 IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
378 Solvable *s = solv->pool->solvables + vv;
380 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "conflicting %s (assertion)\n", pool_solvable2str(solv->pool, s));
382 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "installing %s (assertion)\n", pool_solvable2str(solv->pool, s));
387 /* check against previous decision: is there a conflict? */
388 if (v > 0 && solv->decisionmap[vv] > 0) /* ok to install */
390 if (v < 0 && solv->decisionmap[vv] < 0) /* ok to remove */
396 * The rule (r) we're currently processing says something
397 * different (v = r->p) than a previous decision (decisionmap[abs(v)])
401 if (ri >= solv->learntrules)
403 /* conflict with a learnt rule */
404 /* can happen when packages cannot be installed for multiple reasons. */
405 /* we disable the learnt rule in this case */
406 /* (XXX: we should really call analyze_unsolvable_rule here!) */
407 solver_disablerule(solv, r);
412 * find the decision which is the "opposite" of the rule
414 for (i = 0; i < solv->decisionq.count; i++)
415 if (solv->decisionq.elements[i] == -v)
417 assert(i < solv->decisionq.count); /* assert that we found it */
418 oldproblemcount = solv->problems.count;
421 * conflict with system solvable ?
423 if (v == -SYSTEMSOLVABLE)
427 queue_push(&solv->problems, solv->learnt_pool.count);
428 queue_push(&solv->learnt_pool, ri);
429 queue_push(&solv->learnt_pool, 0);
432 queue_push(&solv->problems, 0);
433 POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "conflict with system solvable, disabling rule #%d\n", ri);
434 if (ri >= solv->jobrules && ri < solv->jobrules_end)
435 v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
438 queue_push(&solv->problems, v);
439 queue_push(&solv->problems, 0);
440 if (solv->allowuninstall && v >= solv->featurerules && v < solv->updaterules_end)
441 solv->problems.count = oldproblemcount;
442 solver_disableproblem(solv, v);
444 break; /* start over */
447 assert(solv->decisionq_why.elements[i] > 0);
450 * conflict with a pkg rule ?
452 if (solv->decisionq_why.elements[i] < solv->pkgrules_end)
456 queue_push(&solv->problems, solv->learnt_pool.count);
457 queue_push(&solv->learnt_pool, ri);
458 queue_push(&solv->learnt_pool, solv->decisionq_why.elements[i]);
459 queue_push(&solv->learnt_pool, 0);
462 queue_push(&solv->problems, 0);
463 assert(v > 0 || v == -SYSTEMSOLVABLE);
464 POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "conflict with pkg rule, disabling rule #%d\n", ri);
465 if (ri >= solv->jobrules && ri < solv->jobrules_end)
466 v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
469 queue_push(&solv->problems, v);
470 queue_push(&solv->problems, 0);
471 if (solv->allowuninstall && v >= solv->featurerules && v < solv->updaterules_end)
472 solv->problems.count = oldproblemcount;
473 solver_disableproblem(solv, v);
475 break; /* start over */
479 * conflict with another job or update/feature rule
485 queue_push(&solv->problems, solv->learnt_pool.count);
486 queue_push(&solv->learnt_pool, ri);
487 queue_push(&solv->learnt_pool, solv->decisionq_why.elements[i]);
488 queue_push(&solv->learnt_pool, 0);
491 queue_push(&solv->problems, 0);
493 POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "conflicting update/job assertions over literal %d\n", vv);
496 * push all of our rules (can only be feature or job rules)
497 * asserting this literal on the problem stack
499 for (i = solv->featurerules, rr = solv->rules + i; i < solv->learntrules; i++, rr++)
501 if (rr->d < 0 /* disabled */
502 || rr->w2) /* or no assertion */
504 if (rr->p != vv /* not affecting the literal */
507 if (MAPTST(&solv->weakrulemap, i)) /* weak: silently ignore */
510 POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, " - disabling rule #%d\n", i);
511 solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE, solv->rules + i);
514 if (i >= solv->jobrules && i < solv->jobrules_end)
515 v = -(solv->ruletojob.elements[i - solv->jobrules] + 1);
516 queue_push(&solv->problems, v);
518 queue_push(&solv->problems, 0);
520 if (solv->allowuninstall && (v = autouninstall(solv, solv->problems.elements + oldproblemcount + 1)) != 0)
521 solv->problems.count = oldproblemcount;
523 for (i = oldproblemcount + 1; i < solv->problems.count - 1; i++)
524 solver_disableproblem(solv, solv->problems.elements[i]);
526 break; /* start over */
528 if (ii < solv->ruleassertions.count)
532 * phase 2: now do the weak assertions
534 for (ii = 0; ii < solv->ruleassertions.count; ii++)
536 ri = solv->ruleassertions.elements[ii];
537 r = solv->rules + ri;
538 if (r->d < 0 || r->w2) /* disabled or no assertion */
540 if (ri >= solv->learntrules || !MAPTST(&solv->weakrulemap, ri)) /* skip non-weak */
545 if (!solv->decisionmap[vv]) /* if not yet decided */
547 queue_push(&solv->decisionq, v);
548 queue_push(&solv->decisionq_why, r - solv->rules);
549 solv->decisionmap[vv] = v > 0 ? 1 : -1;
550 IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
552 Solvable *s = solv->pool->solvables + vv;
554 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "conflicting %s (weak assertion)\n", pool_solvable2str(solv->pool, s));
556 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "installing %s (weak assertion)\n", pool_solvable2str(solv->pool, s));
560 /* check against previous decision: is there a conflict? */
561 if (v > 0 && solv->decisionmap[vv] > 0)
563 if (v < 0 && solv->decisionmap[vv] < 0)
566 POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "assertion conflict, but I am weak, disabling ");
567 solver_printrule(solv, SOLV_DEBUG_UNSOLVABLE, r);
569 if (ri >= solv->jobrules && ri < solv->jobrules_end)
570 v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
573 solver_disableproblem(solv, v);
575 solver_reenablepolicyrules(solv, -v);
577 break; /* start over */
579 if (ii == solv->ruleassertions.count)
580 break; /* finished! */
585 /********************************************************************/
589 /*-------------------------------------------------------------------
592 * initial setup for all watches
596 makewatches(Solver *solv)
600 int nsolvables = solv->pool->nsolvables;
602 solv_free(solv->watches);
603 /* lower half for removals, upper half for installs */
604 solv->watches = solv_calloc(2 * nsolvables, sizeof(Id));
606 /* do it reverse so pkg rules get triggered first (XXX: obsolete?) */
607 for (i = 1, r = solv->rules + solv->nrules - 1; i < solv->nrules; i++, r--)
609 for (i = 1, r = solv->rules + 1; i < solv->nrules; i++, r++)
612 if (!r->w2) /* assertions do not need watches */
615 /* see addwatches_rule(solv, r) */
616 r->n1 = solv->watches[nsolvables + r->w1];
617 solv->watches[nsolvables + r->w1] = r - solv->rules;
619 r->n2 = solv->watches[nsolvables + r->w2];
620 solv->watches[nsolvables + r->w2] = r - solv->rules;
625 /*-------------------------------------------------------------------
627 * add watches (for a new learned rule)
628 * sets up watches for a single rule
630 * see also makewatches() above.
634 addwatches_rule(Solver *solv, Rule *r)
636 int nsolvables = solv->pool->nsolvables;
638 r->n1 = solv->watches[nsolvables + r->w1];
639 solv->watches[nsolvables + r->w1] = r - solv->rules;
641 r->n2 = solv->watches[nsolvables + r->w2];
642 solv->watches[nsolvables + r->w2] = r - solv->rules;
646 /********************************************************************/
652 /* shortcuts to check if a literal (positive or negative) assignment
653 * evaluates to 'true' or 'false'
655 #define DECISIONMAP_TRUE(p) ((p) > 0 ? (decisionmap[p] > 0) : (decisionmap[-p] < 0))
656 #define DECISIONMAP_FALSE(p) ((p) > 0 ? (decisionmap[p] < 0) : (decisionmap[-p] > 0))
657 #define DECISIONMAP_UNDEF(p) (decisionmap[(p) > 0 ? (p) : -(p)] == 0)
659 /*-------------------------------------------------------------------
663 * make decision and propagate to all rules
665 * Evaluate each term affected by the decision (linked through watches).
666 * If we find unit rules we make new decisions based on them.
668 * return : 0 = everything is OK
669 * rule = conflict found in this rule
673 propagate(Solver *solv, int level)
675 Pool *pool = solv->pool;
676 Id *rp, *next_rp; /* rule pointer, next rule pointer in linked list */
678 Id p, pkg, other_watch;
680 Id *decisionmap = solv->decisionmap;
682 Id *watches = solv->watches + pool->nsolvables; /* place ptr in middle */
684 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "----- propagate -----\n");
686 /* foreach non-propagated decision */
687 while (solv->propagate_index < solv->decisionq.count)
690 * 'pkg' was just decided
691 * negate because our watches trigger if literal goes FALSE
693 pkg = -solv->decisionq.elements[solv->propagate_index++];
695 IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
697 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "propagate for decision %d level %d\n", -pkg, level);
698 solver_printruleelement(solv, SOLV_DEBUG_PROPAGATE, 0, -pkg);
701 /* foreach rule where 'pkg' is now FALSE */
702 for (rp = watches + pkg; *rp; rp = next_rp)
704 r = solv->rules + *rp;
707 /* rule is disabled, goto next */
715 IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
717 POOL_DEBUG(SOLV_DEBUG_PROPAGATE," watch triggered ");
718 solver_printrule(solv, SOLV_DEBUG_PROPAGATE, r);
721 /* 'pkg' was just decided (was set to FALSE)
723 * now find other literal watch, check clause
724 * and advance on linked list
738 * This term is already true (through the other literal)
739 * so we have nothing to do
741 if (DECISIONMAP_TRUE(other_watch))
745 * The other literal is FALSE or UNDEF
751 /* Not a binary clause, try to move our watch.
753 * Go over all literals and find one that is
757 * (TRUE is also ok, in that case the rule is fulfilled)
759 if (r->p /* we have a 'p' */
760 && r->p != other_watch /* which is not watched */
761 && !DECISIONMAP_FALSE(r->p)) /* and not FALSE */
765 else /* go find a 'd' to make 'true' */
768 we just iterate sequentially, doing it in another order just changes the order of decisions, not the decisions itself
770 for (dp = pool->whatprovidesdata + r->d; (p = *dp++) != 0;)
772 if (p != other_watch /* which is not watched */
773 && !DECISIONMAP_FALSE(p)) /* and not FALSE */
781 * if we found some p that is UNDEF or TRUE, move
784 IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
787 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, " -> move w%d to %s\n", (pkg == r->w1 ? 1 : 2), pool_solvid2str(pool, p));
789 POOL_DEBUG(SOLV_DEBUG_PROPAGATE," -> move w%d to !%s\n", (pkg == r->w1 ? 1 : 2), pool_solvid2str(pool, -p));
805 watches[p] = r - solv->rules;
808 /* search failed, thus all unwatched literals are FALSE */
813 * unit clause found, set literal other_watch to TRUE
816 if (DECISIONMAP_FALSE(other_watch)) /* check if literal is FALSE */
817 return r; /* eek, a conflict! */
819 IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
821 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, " unit ");
822 solver_printrule(solv, SOLV_DEBUG_PROPAGATE, r);
826 decisionmap[other_watch] = level; /* install! */
828 decisionmap[-other_watch] = -level; /* remove! */
830 queue_push(&solv->decisionq, other_watch);
831 queue_push(&solv->decisionq_why, r - solv->rules);
833 IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
836 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, " -> decided to install %s\n", pool_solvid2str(pool, other_watch));
838 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, " -> decided to conflict %s\n", pool_solvid2str(pool, -other_watch));
841 } /* foreach rule involving 'pkg' */
843 } /* while we have non-decided decisions */
845 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "----- propagate end-----\n");
847 return 0; /* all is well */
851 /********************************************************************/
854 /*-------------------------------------------------------------------
861 analyze(Solver *solv, int level, Rule *c, int *pr, int *dr, int *whyp)
863 Pool *pool = solv->pool;
867 Map seen; /* global? */
868 Id d, v, vv, *dp, why;
870 int num = 0, l1num = 0;
871 int learnt_why = solv->learnt_pool.count;
872 Id *decisionmap = solv->decisionmap;
874 queue_init_buffer(&r, r_buf, sizeof(r_buf)/sizeof(*r_buf));
876 POOL_DEBUG(SOLV_DEBUG_ANALYZE, "ANALYZE at %d ----------------------\n", level);
877 map_init(&seen, pool->nsolvables);
878 idx = solv->decisionq.count;
881 IF_POOLDEBUG (SOLV_DEBUG_ANALYZE)
882 solver_printruleclass(solv, SOLV_DEBUG_ANALYZE, c);
883 queue_push(&solv->learnt_pool, c - solv->rules);
884 d = c->d < 0 ? -c->d - 1 : c->d;
885 dp = d ? pool->whatprovidesdata + d : 0;
886 /* go through all literals of the rule */
898 if (DECISIONMAP_TRUE(v)) /* the one true literal */
901 if (MAPTST(&seen, vv))
903 l = solv->decisionmap[vv];
906 MAPSET(&seen, vv); /* mark that we also need to look at this literal */
908 l1num++; /* need to do this one in level1 pass */
910 num++; /* need to do this one as well */
913 queue_push(&r, v); /* not level1 or conflict level, add to new rule */
919 if (!num && !--l1num)
920 break; /* all level 1 literals done */
922 /* find the next literal to investigate */
923 /* (as num + l1num > 0, we know that we'll always find one) */
927 v = solv->decisionq.elements[--idx];
929 if (MAPTST(&seen, vv))
934 if (num && --num == 0)
936 *pr = -v; /* so that v doesn't get lost */
939 POOL_DEBUG(SOLV_DEBUG_ANALYZE, "got %d involved level 1 decisions\n", l1num);
940 /* clear non-l1 bits from seen map */
941 for (i = 0; i < r.count; i++)
944 MAPCLR(&seen, v > 0 ? v : -v);
946 /* only level 1 marks left in seen map */
947 l1num++; /* as l1retry decrements it */
951 why = solv->decisionq_why.elements[idx];
952 if (why <= 0) /* just in case, maybe for SYSTEMSOLVABLE */
954 c = solv->rules + why;
960 else if (r.count == 1 && r.elements[0] < 0)
963 *dr = pool_queuetowhatprovides(pool, &r);
964 IF_POOLDEBUG (SOLV_DEBUG_ANALYZE)
966 POOL_DEBUG(SOLV_DEBUG_ANALYZE, "learned rule for level %d (am %d)\n", rlevel, level);
967 solver_printruleelement(solv, SOLV_DEBUG_ANALYZE, 0, *pr);
968 for (i = 0; i < r.count; i++)
969 solver_printruleelement(solv, SOLV_DEBUG_ANALYZE, 0, r.elements[i]);
971 /* push end marker on learnt reasons stack */
972 queue_push(&solv->learnt_pool, 0);
976 solv->stats_learned++;
981 /*-------------------------------------------------------------------
985 * reset all solver decisions
986 * called after rules have been enabled/disabled
990 solver_reset(Solver *solv)
992 Pool *pool = solv->pool;
996 /* rewind all decisions */
997 for (i = solv->decisionq.count - 1; i >= 0; i--)
999 v = solv->decisionq.elements[i];
1000 solv->decisionmap[v > 0 ? v : -v] = 0;
1002 queue_empty(&solv->decisionq_why);
1003 queue_empty(&solv->decisionq);
1004 solv->recommends_index = -1;
1005 solv->propagate_index = 0;
1006 solv->decisioncnt_update = solv->decisioncnt_keep = solv->decisioncnt_resolve = solv->decisioncnt_weak = solv->decisioncnt_orphan = 0;
1007 queue_empty(&solv->branches);
1009 /* adapt learnt rule status to new set of enabled/disabled rules */
1010 enabledisablelearntrules(solv);
1012 /* redo all assertion rule decisions */
1013 makeruledecisions(solv);
1014 POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "decisions so far: %d\n", solv->decisionq.count);
1018 /*-------------------------------------------------------------------
1020 * analyze_unsolvable_rule
1022 * recursion helper used by analyze_unsolvable
1026 analyze_unsolvable_rule(Solver *solv, Rule *r, Id *lastweakp, Map *rseen)
1028 Pool *pool = solv->pool;
1030 Id why = r - solv->rules;
1032 IF_POOLDEBUG (SOLV_DEBUG_UNSOLVABLE)
1033 solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE, r);
1034 if (solv->learntrules && why >= solv->learntrules)
1036 if (MAPTST(rseen, why - solv->learntrules))
1038 MAPSET(rseen, why - solv->learntrules);
1039 for (i = solv->learnt_why.elements[why - solv->learntrules]; solv->learnt_pool.elements[i]; i++)
1040 if (solv->learnt_pool.elements[i] > 0)
1041 analyze_unsolvable_rule(solv, solv->rules + solv->learnt_pool.elements[i], lastweakp, rseen);
1044 if (MAPTST(&solv->weakrulemap, why))
1045 if (!*lastweakp || why > *lastweakp)
1047 /* do not add pkg rules to problem */
1048 if (why < solv->pkgrules_end)
1050 /* turn rule into problem */
1051 if (why >= solv->jobrules && why < solv->jobrules_end)
1052 why = -(solv->ruletojob.elements[why - solv->jobrules] + 1);
1053 /* normalize dup/infarch rules */
1054 if (why > solv->infarchrules && why < solv->infarchrules_end)
1056 Id name = pool->solvables[-solv->rules[why].p].name;
1057 while (why > solv->infarchrules && pool->solvables[-solv->rules[why - 1].p].name == name)
1060 if (why > solv->duprules && why < solv->duprules_end)
1062 Id name = pool->solvables[-solv->rules[why].p].name;
1063 while (why > solv->duprules && pool->solvables[-solv->rules[why - 1].p].name == name)
1067 /* return if problem already countains our rule */
1068 if (solv->problems.count)
1070 for (i = solv->problems.count - 1; i >= 0; i--)
1071 if (solv->problems.elements[i] == 0) /* end of last problem reached? */
1073 else if (solv->problems.elements[i] == why)
1076 queue_push(&solv->problems, why);
1080 /*-------------------------------------------------------------------
1082 * analyze_unsolvable
1084 * We know that the problem is not solvable. Record all involved
1085 * rules (i.e. the "proof") into solv->learnt_pool.
1086 * Record the learnt pool index and all non-pkg rules into
1087 * solv->problems. (Our solutions to fix the problems are to
1088 * disable those rules.)
1090 * If the proof contains at least one weak rule, we disable the
1093 * Otherwise we return 0 if disablerules is not set or disable
1094 * _all_ of the problem rules and return 1.
1096 * return: 1 - disabled some rules, try again
1101 analyze_unsolvable(Solver *solv, Rule *cr, int disablerules)
1103 Pool *pool = solv->pool;
1105 Map seen; /* global to speed things up? */
1107 Id d, v, vv, *dp, why;
1109 Id *decisionmap = solv->decisionmap;
1110 int oldproblemcount;
1111 int oldlearntpoolcount;
1113 int record_proof = 1;
1115 POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "ANALYZE UNSOLVABLE ----------------------\n");
1116 solv->stats_unsolvable++;
1117 oldproblemcount = solv->problems.count;
1118 oldlearntpoolcount = solv->learnt_pool.count;
1120 /* make room for proof index */
1121 /* must update it later, as analyze_unsolvable_rule would confuse
1122 * it with a rule index if we put the real value in already */
1123 queue_push(&solv->problems, 0);
1126 map_init(&seen, pool->nsolvables);
1127 map_init(&rseen, solv->learntrules ? solv->nrules - solv->learntrules : 0);
1129 queue_push(&solv->learnt_pool, r - solv->rules);
1131 analyze_unsolvable_rule(solv, r, &lastweak, &rseen);
1132 d = r->d < 0 ? -r->d - 1 : r->d;
1133 dp = d ? pool->whatprovidesdata + d : 0;
1144 if (DECISIONMAP_TRUE(v)) /* the one true literal */
1146 vv = v > 0 ? v : -v;
1147 l = solv->decisionmap[vv];
1152 idx = solv->decisionq.count;
1155 v = solv->decisionq.elements[--idx];
1156 vv = v > 0 ? v : -v;
1157 if (!MAPTST(&seen, vv) || vv == SYSTEMSOLVABLE)
1159 why = solv->decisionq_why.elements[idx];
1162 queue_push(&solv->learnt_pool, why);
1163 r = solv->rules + why;
1164 analyze_unsolvable_rule(solv, r, &lastweak, &rseen);
1165 d = r->d < 0 ? -r->d - 1 : r->d;
1166 dp = d ? pool->whatprovidesdata + d : 0;
1177 if (DECISIONMAP_TRUE(v)) /* the one true literal */
1179 vv = v > 0 ? v : -v;
1180 l = solv->decisionmap[vv];
1188 queue_push(&solv->problems, 0); /* mark end of this problem */
1192 /* disable last weak rule */
1193 solv->problems.count = oldproblemcount;
1194 solv->learnt_pool.count = oldlearntpoolcount;
1195 if (lastweak >= solv->jobrules && lastweak < solv->jobrules_end)
1196 v = -(solv->ruletojob.elements[lastweak - solv->jobrules] + 1);
1199 POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "disabling ");
1200 solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE, solv->rules + lastweak);
1201 if (lastweak >= solv->choicerules && lastweak < solv->choicerules_end)
1202 solver_disablechoicerules(solv, solv->rules + lastweak);
1203 solver_disableproblem(solv, v);
1205 solver_reenablepolicyrules(solv, -v);
1210 if (solv->allowuninstall && (v = autouninstall(solv, solv->problems.elements + oldproblemcount + 1)) != 0)
1212 solv->problems.count = oldproblemcount;
1213 solv->learnt_pool.count = oldlearntpoolcount;
1221 queue_push(&solv->learnt_pool, 0);
1222 solv->problems.elements[oldproblemcount] = oldlearntpoolcount;
1225 /* + 2: index + trailing zero */
1226 if (disablerules && oldproblemcount + 2 < solv->problems.count)
1228 for (i = oldproblemcount + 1; i < solv->problems.count - 1; i++)
1229 solver_disableproblem(solv, solv->problems.elements[i]);
1230 /* XXX: might want to enable all weak rules again */
1234 POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "UNSOLVABLE\n");
1239 /********************************************************************/
1240 /* Decision revert */
1242 /*-------------------------------------------------------------------
1245 * revert decisionq to a level
1249 revert(Solver *solv, int level)
1251 Pool *pool = solv->pool;
1253 while (solv->decisionq.count)
1255 v = solv->decisionq.elements[solv->decisionq.count - 1];
1256 vv = v > 0 ? v : -v;
1257 if (solv->decisionmap[vv] <= level && solv->decisionmap[vv] >= -level)
1259 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "reverting decision %d at %d\n", v, solv->decisionmap[vv]);
1260 solv->decisionmap[vv] = 0;
1261 solv->decisionq.count--;
1262 solv->decisionq_why.count--;
1263 solv->propagate_index = solv->decisionq.count;
1265 while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] >= level)
1266 solv->branches.count -= solv->branches.elements[solv->branches.count - 2];
1267 if (solv->recommends_index > solv->decisionq.count)
1268 solv->recommends_index = -1; /* rebuild recommends/suggests maps */
1269 if (solv->decisionq.count < solv->decisioncnt_jobs)
1270 solv->decisioncnt_jobs = 0;
1271 if (solv->decisionq.count < solv->decisioncnt_update)
1272 solv->decisioncnt_update = 0;
1273 if (solv->decisionq.count < solv->decisioncnt_keep)
1274 solv->decisioncnt_keep = 0;
1275 if (solv->decisionq.count < solv->decisioncnt_resolve)
1276 solv->decisioncnt_resolve = 0;
1277 if (solv->decisionq.count < solv->decisioncnt_weak)
1278 solv->decisioncnt_weak= 0;
1279 if (solv->decisionq.count < solv->decisioncnt_orphan)
1280 solv->decisioncnt_orphan = 0;
1284 /*-------------------------------------------------------------------
1286 * watch2onhighest - put watch2 on literal with highest level
1290 watch2onhighest(Solver *solv, Rule *r)
1295 d = r->d < 0 ? -r->d - 1 : r->d;
1297 return; /* binary rule, both watches are set */
1298 dp = solv->pool->whatprovidesdata + d;
1299 while ((v = *dp++) != 0)
1301 l = solv->decisionmap[v < 0 ? -v : v];
1313 /*-------------------------------------------------------------------
1317 * add free decision (solvable to install) to decisionq
1318 * increase level and propagate decision
1319 * return if no conflict.
1321 * in conflict case, analyze conflict rule, add resulting
1322 * rule to learnt rule set, make decision from learnt
1323 * rule (always unit) and re-propagate.
1325 * returns the new solver level or 0 if unsolvable
1330 setpropagatelearn(Solver *solv, int level, Id decision, int disablerules, Id ruleid)
1332 Pool *pool = solv->pool;
1337 assert(ruleid >= 0);
1342 solv->decisionmap[decision] = level;
1344 solv->decisionmap[-decision] = -level;
1345 queue_push(&solv->decisionq, decision);
1346 queue_push(&solv->decisionq_why, -ruleid); /* <= 0 -> free decision */
1350 r = propagate(solv, level);
1354 return analyze_unsolvable(solv, r, disablerules);
1355 POOL_DEBUG(SOLV_DEBUG_ANALYZE, "conflict with rule #%d\n", (int)(r - solv->rules));
1356 l = analyze(solv, level, r, &p, &d, &why); /* learnt rule in p and d */
1357 assert(l > 0 && l < level);
1358 POOL_DEBUG(SOLV_DEBUG_ANALYZE, "reverting decisions (level %d -> %d)\n", level, l);
1360 revert(solv, level);
1361 r = solver_addrule(solv, p, d);
1363 assert(solv->learnt_why.count == (r - solv->rules) - solv->learntrules);
1364 queue_push(&solv->learnt_why, why);
1367 /* at least 2 literals, needs watches */
1368 watch2onhighest(solv, r);
1369 addwatches_rule(solv, r);
1373 /* learnt rule is an assertion */
1374 queue_push(&solv->ruleassertions, r - solv->rules);
1376 /* the new rule is unit by design */
1377 solv->decisionmap[p > 0 ? p : -p] = p > 0 ? level : -level;
1378 queue_push(&solv->decisionq, p);
1379 queue_push(&solv->decisionq_why, r - solv->rules);
1380 IF_POOLDEBUG (SOLV_DEBUG_ANALYZE)
1382 POOL_DEBUG(SOLV_DEBUG_ANALYZE, "decision: ");
1383 solver_printruleelement(solv, SOLV_DEBUG_ANALYZE, 0, p);
1384 POOL_DEBUG(SOLV_DEBUG_ANALYZE, "new rule: ");
1385 solver_printrule(solv, SOLV_DEBUG_ANALYZE, r);
1392 reorder_dq_for_jobrules(Solver *solv, int level, Queue *dq)
1394 Pool *pool = solv->pool;
1395 int i, j, haveone = 0, dqcount = dq->count;
1396 int decisionqcount = solv->decisionq.count;
1400 /* at the time we process jobrules the installed packages are not kept yet */
1401 /* reorder so that "future-supplemented" packages come first */
1402 FOR_REPO_SOLVABLES(solv->installed, p, s)
1404 if (MAPTST(&solv->noupdate, p - solv->installed->start))
1406 if (solv->decisionmap[p] == 0)
1408 if (s->recommends || s->suggests)
1409 queue_push(&solv->decisionq, p);
1410 solv->decisionmap[p] = level + 1;
1416 policy_update_recommendsmap(solv);
1417 for (i = 0; i < dqcount; i++)
1419 p = dq->elements[i];
1420 if (!(pool->solvables[p].repo == solv->installed || MAPTST(&solv->suggestsmap, p) || solver_is_enhancing(solv, pool->solvables + p)))
1423 dq->elements[i] = 0;
1426 dqcount = dq->count;
1427 for (i = 0; i < dqcount; i++)
1429 p = dq->elements[i];
1430 if (p && !(pool->solvables[p].repo == solv->installed || MAPTST(&solv->recommendsmap, p) || solver_is_supplementing(solv, pool->solvables + p)))
1433 dq->elements[i] = 0;
1436 for (i = j = 0; i < dq->count; i++)
1437 if (dq->elements[i])
1438 dq->elements[j++] = dq->elements[i];
1439 queue_truncate(dq, j);
1440 FOR_REPO_SOLVABLES(solv->installed, p, s)
1441 if (solv->decisionmap[p] == level + 1)
1442 solv->decisionmap[p] = 0;
1443 if (solv->decisionq.count != decisionqcount)
1445 solv->recommends_index = -1;
1446 queue_truncate(&solv->decisionq, decisionqcount);
1450 /*-------------------------------------------------------------------
1456 createbranch(Solver *solv, int level, Queue *dq, Id p, Id data)
1458 Pool *pool = solv->pool;
1460 IF_POOLDEBUG (SOLV_DEBUG_POLICY)
1462 POOL_DEBUG (SOLV_DEBUG_POLICY, "creating a branch:\n");
1463 for (i = 0; i < dq->count; i++)
1464 POOL_DEBUG (SOLV_DEBUG_POLICY, " - %s\n", pool_solvid2str(pool, dq->elements[i]));
1466 queue_push(&solv->branches, -dq->elements[0]);
1467 for (i = 1; i < dq->count; i++)
1468 queue_push(&solv->branches, dq->elements[i]);
1469 queue_push2(&solv->branches, p, data);
1470 queue_push2(&solv->branches, dq->count + 4, level);
1474 takebranch(Solver *solv, int pos, int end, const char *msg, int disablerules)
1476 Pool *pool = solv->pool;
1482 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]);
1483 for (i = end - solv->branches.elements[end - 2]; i < end - 4; i++)
1484 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]));
1487 level = solv->branches.elements[end - 1];
1488 p = solv->branches.elements[pos];
1489 solv->branches.elements[pos] = -p;
1490 POOL_DEBUG(SOLV_DEBUG_SOLVER, "%s %d -> %d with %s\n", msg, solv->decisionmap[p], level, pool_solvid2str(pool, p));
1491 /* hack: set level to zero so that revert does not remove the branch */
1492 solv->branches.elements[end - 1] = 0;
1493 revert(solv, level);
1494 solv->branches.elements[end - 1] = level;
1495 /* hack: revert simply sets the count, so we can still access the reverted elements */
1496 why = -solv->decisionq_why.elements[solv->decisionq_why.count];
1498 return setpropagatelearn(solv, level, p, disablerules, why);
1501 /*-------------------------------------------------------------------
1503 * select and install
1505 * install best package from the queue. We add an extra package, inst, if
1506 * provided. See comment in weak install section.
1508 * returns the new solver level or 0 if unsolvable
1513 selectandinstall(Solver *solv, int level, Queue *dq, int disablerules, Id ruleid)
1515 Pool *pool = solv->pool;
1519 policy_filter_unwanted(solv, dq, POLICY_MODE_CHOOSE);
1520 /* if we're resolving job rules and didn't resolve the installed packages yet,
1521 * do some special supplements ordering */
1522 if (dq->count > 1 && ruleid >= solv->jobrules && ruleid < solv->jobrules_end && solv->installed && !solv->focus_installed)
1523 reorder_dq_for_jobrules(solv, level, dq);
1524 /* if we have multiple candidates we open a branch */
1526 createbranch(solv, level, dq, 0, ruleid);
1527 p = dq->elements[0];
1528 POOL_DEBUG(SOLV_DEBUG_POLICY, "installing %s\n", pool_solvid2str(pool, p));
1529 return setpropagatelearn(solv, level, p, disablerules, ruleid);
1533 /********************************************************************/
1534 /* Main solver interface */
1537 /*-------------------------------------------------------------------
1540 * create solver structure
1542 * pool: all available solvables
1543 * installed: installed Solvables
1546 * Upon solving, rules are created to flag the Solvables
1547 * of the 'installed' Repo as installed.
1551 solver_create(Pool *pool)
1554 solv = (Solver *)solv_calloc(1, sizeof(Solver));
1556 solv->installed = pool->installed;
1558 solv->allownamechange = 1;
1560 solv->dup_allowdowngrade = 1;
1561 solv->dup_allownamechange = 1;
1562 solv->dup_allowarchchange = 1;
1563 solv->dup_allowvendorchange = 1;
1565 solv->keepexplicitobsoletes = pool->noobsoletesmultiversion ? 0 : 1;
1567 queue_init(&solv->ruletojob);
1568 queue_init(&solv->decisionq);
1569 queue_init(&solv->decisionq_why);
1570 queue_init(&solv->problems);
1571 queue_init(&solv->orphaned);
1572 queue_init(&solv->learnt_why);
1573 queue_init(&solv->learnt_pool);
1574 queue_init(&solv->branches);
1575 queue_init(&solv->weakruleq);
1576 queue_init(&solv->ruleassertions);
1577 queue_init(&solv->addedmap_deduceq);
1579 queue_push(&solv->learnt_pool, 0); /* so that 0 does not describe a proof */
1581 map_init(&solv->recommendsmap, pool->nsolvables);
1582 map_init(&solv->suggestsmap, pool->nsolvables);
1583 map_init(&solv->noupdate, solv->installed ? solv->installed->end - solv->installed->start : 0);
1584 solv->recommends_index = 0;
1586 solv->decisionmap = (Id *)solv_calloc(pool->nsolvables, sizeof(Id));
1588 solv->rules = solv_extend_resize(solv->rules, solv->nrules, sizeof(Rule), RULES_BLOCK);
1589 memset(solv->rules, 0, sizeof(Rule));
1596 resolve_jobrules(Solver *solv, int level, int disablerules, Queue *dq)
1598 Pool *pool = solv->pool;
1599 int oldlevel = level;
1603 POOL_DEBUG(SOLV_DEBUG_SOLVER, "resolving job rules\n");
1604 if (!solv->decisioncnt_jobs)
1605 solv->decisioncnt_jobs = solv->decisionq.count;
1606 for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++)
1609 if (r->d < 0) /* ignore disabled rules */
1612 FOR_RULELITERALS(l, pp, r)
1616 if (solv->decisionmap[-l] <= 0)
1621 if (solv->decisionmap[l] > 0)
1623 if (solv->decisionmap[l] == 0)
1627 if (l || !dq->count)
1629 /* prune to installed if not updating */
1630 if (dq->count > 1 && solv->installed && !solv->updatemap_all &&
1631 !(solv->job.elements[solv->ruletojob.elements[i - solv->jobrules]] & SOLVER_ORUPDATE))
1634 for (j = k = 0; j < dq->count; j++)
1636 Solvable *s = pool->solvables + dq->elements[j];
1637 if (s->repo == solv->installed)
1639 dq->elements[k++] = dq->elements[j];
1640 if (solv->updatemap.size && MAPTST(&solv->updatemap, dq->elements[j] - solv->installed->start))
1642 k = 0; /* package wants to be updated, do not prune */
1651 level = selectandinstall(solv, level, dq, disablerules, i);
1652 if (level <= olevel)
1655 return 0; /* unsolvable */
1656 if (level == olevel)
1660 continue; /* try something else */
1662 if (level < oldlevel)
1664 /* redo from start of jobrules */
1665 i = solv->jobrules - 1;
1666 r = solv->rules + i;
1672 /*-------------------------------------------------------------------
1678 queuep_free(Queue **qp)
1683 *qp = solv_free(*qp);
1687 map_zerosize(Map *m)
1697 solver_free(Solver *solv)
1699 queue_free(&solv->job);
1700 queue_free(&solv->ruletojob);
1701 queue_free(&solv->decisionq);
1702 queue_free(&solv->decisionq_why);
1703 queue_free(&solv->learnt_why);
1704 queue_free(&solv->learnt_pool);
1705 queue_free(&solv->problems);
1706 queue_free(&solv->solutions);
1707 queue_free(&solv->orphaned);
1708 queue_free(&solv->branches);
1709 queue_free(&solv->weakruleq);
1710 queue_free(&solv->ruleassertions);
1711 queue_free(&solv->addedmap_deduceq);
1712 queuep_free(&solv->cleandeps_updatepkgs);
1713 queuep_free(&solv->cleandeps_mistakes);
1714 queuep_free(&solv->update_targets);
1715 queuep_free(&solv->installsuppdepq);
1716 queuep_free(&solv->recommendscplxq);
1717 queuep_free(&solv->suggestscplxq);
1718 queuep_free(&solv->brokenorphanrules);
1720 map_free(&solv->recommendsmap);
1721 map_free(&solv->suggestsmap);
1722 map_free(&solv->noupdate);
1723 map_free(&solv->weakrulemap);
1724 map_free(&solv->multiversion);
1726 map_free(&solv->updatemap);
1727 map_free(&solv->bestupdatemap);
1728 map_free(&solv->fixmap);
1729 map_free(&solv->dupmap);
1730 map_free(&solv->dupinvolvedmap);
1731 map_free(&solv->droporphanedmap);
1732 map_free(&solv->cleandepsmap);
1734 solv_free(solv->decisionmap);
1735 solv_free(solv->rules);
1736 solv_free(solv->watches);
1737 solv_free(solv->obsoletes);
1738 solv_free(solv->obsoletes_data);
1739 solv_free(solv->specialupdaters);
1740 solv_free(solv->choicerules_ref);
1741 solv_free(solv->bestrules_pkg);
1742 solv_free(solv->yumobsrules_info);
1743 solv_free(solv->instbuddy);
1748 solver_get_flag(Solver *solv, int flag)
1752 case SOLVER_FLAG_ALLOW_DOWNGRADE:
1753 return solv->allowdowngrade;
1754 case SOLVER_FLAG_ALLOW_NAMECHANGE:
1755 return solv->allownamechange;
1756 case SOLVER_FLAG_ALLOW_ARCHCHANGE:
1757 return solv->allowarchchange;
1758 case SOLVER_FLAG_ALLOW_VENDORCHANGE:
1759 return solv->allowvendorchange;
1760 case SOLVER_FLAG_ALLOW_UNINSTALL:
1761 return solv->allowuninstall;
1762 case SOLVER_FLAG_NO_UPDATEPROVIDE:
1763 return solv->noupdateprovide;
1764 case SOLVER_FLAG_SPLITPROVIDES:
1765 return solv->dosplitprovides;
1766 case SOLVER_FLAG_IGNORE_RECOMMENDED:
1767 return solv->dontinstallrecommended;
1768 case SOLVER_FLAG_ADD_ALREADY_RECOMMENDED:
1769 return solv->addalreadyrecommended;
1770 case SOLVER_FLAG_NO_INFARCHCHECK:
1771 return solv->noinfarchcheck;
1772 case SOLVER_FLAG_KEEP_EXPLICIT_OBSOLETES:
1773 return solv->keepexplicitobsoletes;
1774 case SOLVER_FLAG_BEST_OBEY_POLICY:
1775 return solv->bestobeypolicy;
1776 case SOLVER_FLAG_NO_AUTOTARGET:
1777 return solv->noautotarget;
1778 case SOLVER_FLAG_DUP_ALLOW_DOWNGRADE:
1779 return solv->dup_allowdowngrade;
1780 case SOLVER_FLAG_DUP_ALLOW_NAMECHANGE:
1781 return solv->dup_allownamechange;
1782 case SOLVER_FLAG_DUP_ALLOW_ARCHCHANGE:
1783 return solv->dup_allowarchchange;
1784 case SOLVER_FLAG_DUP_ALLOW_VENDORCHANGE:
1785 return solv->dup_allowvendorchange;
1786 case SOLVER_FLAG_KEEP_ORPHANS:
1787 return solv->keep_orphans;
1788 case SOLVER_FLAG_BREAK_ORPHANS:
1789 return solv->break_orphans;
1790 case SOLVER_FLAG_FOCUS_INSTALLED:
1791 return solv->focus_installed;
1792 case SOLVER_FLAG_YUM_OBSOLETES:
1793 return solv->do_yum_obsoletes;
1801 solver_set_flag(Solver *solv, int flag, int value)
1803 int old = solver_get_flag(solv, flag);
1806 case SOLVER_FLAG_ALLOW_DOWNGRADE:
1807 solv->allowdowngrade = value;
1809 case SOLVER_FLAG_ALLOW_NAMECHANGE:
1810 solv->allownamechange = value;
1812 case SOLVER_FLAG_ALLOW_ARCHCHANGE:
1813 solv->allowarchchange = value;
1815 case SOLVER_FLAG_ALLOW_VENDORCHANGE:
1816 solv->allowvendorchange = value;
1818 case SOLVER_FLAG_ALLOW_UNINSTALL:
1819 solv->allowuninstall = value;
1821 case SOLVER_FLAG_NO_UPDATEPROVIDE:
1822 solv->noupdateprovide = value;
1824 case SOLVER_FLAG_SPLITPROVIDES:
1825 solv->dosplitprovides = value;
1827 case SOLVER_FLAG_IGNORE_RECOMMENDED:
1828 solv->dontinstallrecommended = value;
1830 case SOLVER_FLAG_ADD_ALREADY_RECOMMENDED:
1831 solv->addalreadyrecommended = value;
1833 case SOLVER_FLAG_NO_INFARCHCHECK:
1834 solv->noinfarchcheck = value;
1836 case SOLVER_FLAG_KEEP_EXPLICIT_OBSOLETES:
1837 solv->keepexplicitobsoletes = value;
1839 case SOLVER_FLAG_BEST_OBEY_POLICY:
1840 solv->bestobeypolicy = value;
1842 case SOLVER_FLAG_NO_AUTOTARGET:
1843 solv->noautotarget = value;
1845 case SOLVER_FLAG_DUP_ALLOW_DOWNGRADE:
1846 solv->dup_allowdowngrade = value;
1848 case SOLVER_FLAG_DUP_ALLOW_NAMECHANGE:
1849 solv->dup_allownamechange = value;
1851 case SOLVER_FLAG_DUP_ALLOW_ARCHCHANGE:
1852 solv->dup_allowarchchange = value;
1854 case SOLVER_FLAG_DUP_ALLOW_VENDORCHANGE:
1855 solv->dup_allowvendorchange = value;
1857 case SOLVER_FLAG_KEEP_ORPHANS:
1858 solv->keep_orphans = value;
1860 case SOLVER_FLAG_BREAK_ORPHANS:
1861 solv->break_orphans = value;
1863 case SOLVER_FLAG_FOCUS_INSTALLED:
1864 solv->focus_installed = value;
1866 case SOLVER_FLAG_YUM_OBSOLETES:
1867 solv->do_yum_obsoletes = value;
1876 cleandeps_check_mistakes(Solver *solv, int level)
1878 Pool *pool = solv->pool;
1882 int mademistake = 0;
1884 if (!solv->cleandepsmap.size)
1886 /* check for mistakes */
1887 for (i = solv->installed->start; i < solv->installed->end; i++)
1889 if (!MAPTST(&solv->cleandepsmap, i - solv->installed->start))
1891 r = solv->rules + solv->featurerules + (i - solv->installed->start);
1892 /* a mistake is when the featurerule is true but the updaterule is false */
1895 FOR_RULELITERALS(p, pp, r)
1896 if (p > 0 && solv->decisionmap[p] > 0)
1899 continue; /* feature rule is not true */
1900 r = solv->rules + solv->updaterules + (i - solv->installed->start);
1903 FOR_RULELITERALS(p, pp, r)
1904 if (p > 0 && solv->decisionmap[p] > 0)
1907 continue; /* update rule is true */
1908 POOL_DEBUG(SOLV_DEBUG_SOLVER, "cleandeps mistake: ");
1909 solver_printruleclass(solv, SOLV_DEBUG_SOLVER, r);
1910 POOL_DEBUG(SOLV_DEBUG_SOLVER, "feature rule: ");
1911 solver_printruleclass(solv, SOLV_DEBUG_SOLVER, solv->rules + solv->featurerules + (i - solv->installed->start));
1912 if (!solv->cleandeps_mistakes)
1914 solv->cleandeps_mistakes = solv_calloc(1, sizeof(Queue));
1915 queue_init(solv->cleandeps_mistakes);
1917 queue_push(solv->cleandeps_mistakes, i);
1918 MAPCLR(&solv->cleandepsmap, i - solv->installed->start);
1919 solver_reenablepolicyrules_cleandeps(solv, i);
1928 prune_to_update_targets(Solver *solv, Id *cp, Queue *q)
1932 for (i = j = 0; i < q->count; i++)
1935 for (cp2 = cp; *cp2; cp2++)
1938 q->elements[j++] = p;
1942 queue_truncate(q, j);
1945 #ifdef ENABLE_COMPLEX_DEPS
1948 add_complex_recommends(Solver *solv, Id rec, Queue *dq, Map *dqmap)
1950 Pool *pool = solv->pool;
1951 int oldcnt = dq->count;
1957 printf("ADD_COMPLEX_RECOMMENDS %s\n", pool_dep2str(pool, rec));
1959 i = pool_normalize_complex_dep(pool, rec, dq, CPLXDEPS_EXPAND);
1960 if (i == 0 || i == 1)
1963 for (i = oldcnt; i < cutcnt; i++)
1966 for (; (p = dq->elements[i]) != 0; i++)
1970 if (solv->decisionmap[-p] <= 0)
1974 if (solv->decisionmap[p] > 0)
1976 queue_truncate(dq, blkcnt);
1981 if (!MAPTST(dqmap, p))
1986 if (solv->decisionmap[p] < 0)
1988 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))))
1993 while (dq->elements[i])
1996 queue_deleten(dq, oldcnt, cutcnt - oldcnt);
1998 if (dq->count != oldcnt)
2000 for (j = oldcnt; j < dq->count; j++)
2002 p = dq->elements[j];
2003 for (i = 0; i < j; i++)
2004 if (dq->elements[i] == p)
2006 dq->elements[j] = 0;
2010 for (i = j = oldcnt; j < dq->count; j++)
2011 if (dq->elements[j])
2012 dq->elements[i++] = dq->elements[j];
2013 queue_truncate(dq, i);
2016 printf("RETURN:\n");
2017 for (i = oldcnt; i < dq->count; i++)
2018 printf(" - %s\n", pool_solvid2str(pool, dq->elements[i]));
2023 do_complex_recommendations(Solver *solv, Id rec, Map *m, int noselected)
2025 Pool *pool = solv->pool;
2031 printf("DO_COMPLEX_RECOMMENDATIONS %s\n", pool_dep2str(pool, rec));
2034 i = pool_normalize_complex_dep(pool, rec, &dq, CPLXDEPS_EXPAND);
2035 if (i == 0 || i == 1)
2040 for (i = 0; i < dq.count; i++)
2043 for (; (p = dq.elements[i]) != 0; i++)
2047 if (solv->decisionmap[-p] <= 0)
2051 if (solv->decisionmap[p] > 0)
2056 for (i++; (p = dq.elements[i]) != 0; i++)
2057 if (p > 0 && solv->decisionmap[p] > 0)
2065 for (i = blk; (p = dq.elements[i]) != 0; i++)
2069 while (dq.elements[i])
2077 /*-------------------------------------------------------------------
2081 * all rules have been set up, now actually run the solver
2086 solver_run_sat(Solver *solv, int disablerules, int doweak)
2088 Queue dq; /* local decisionqueue */
2089 Queue dqs; /* local decisionqueue for supplements */
2095 Pool *pool = solv->pool;
2097 int minimizationsteps;
2098 int installedpos = solv->installed ? solv->installed->start : 0;
2100 IF_POOLDEBUG (SOLV_DEBUG_RULE_CREATION)
2102 POOL_DEBUG (SOLV_DEBUG_RULE_CREATION, "number of rules: %d\n", solv->nrules);
2103 for (i = 1; i < solv->nrules; i++)
2104 solver_printruleclass(solv, SOLV_DEBUG_RULE_CREATION, solv->rules + i);
2107 POOL_DEBUG(SOLV_DEBUG_SOLVER, "initial decisions: %d\n", solv->decisionq.count);
2109 /* start SAT algorithm */
2111 systemlevel = level + 1;
2112 POOL_DEBUG(SOLV_DEBUG_SOLVER, "solving...\n");
2118 * here's the main loop:
2119 * 1) propagate new decisions (only needed once)
2121 * 3) try to keep installed packages
2122 * 4) fulfill all unresolved rules
2123 * 5) install recommended packages
2124 * 6) minimalize solution if we had choices
2125 * if we encounter a problem, we rewind to a safe level and restart
2129 minimizationsteps = 0;
2133 * initial propagation of the assertions
2137 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "propagating (propagate_index: %d; size decisionq: %d)...\n", solv->propagate_index, solv->decisionq.count);
2138 if ((r = propagate(solv, level)) != 0)
2140 if (analyze_unsolvable(solv, r, disablerules))
2143 break; /* unsolvable */
2148 * resolve jobs first (unless focus_installed is set)
2150 if (level < systemlevel && !solv->focus_installed)
2153 level = resolve_jobrules(solv, level, disablerules, &dq);
2157 break; /* unsolvable */
2160 systemlevel = level + 1;
2165 * installed packages
2167 if (!solv->decisioncnt_update)
2168 solv->decisioncnt_update = solv->decisionq.count;
2169 if (level < systemlevel && solv->installed && solv->installed->nsolvables && !solv->installed->disabled)
2171 Repo *installed = solv->installed;
2174 POOL_DEBUG(SOLV_DEBUG_SOLVER, "resolving installed packages\n");
2175 /* we use two passes if we need to update packages
2176 * to create a better user experience */
2177 for (pass = solv->updatemap.size ? 0 : 1; pass < 2; pass++)
2179 int passlevel = level;
2180 Id *specialupdaters = solv->specialupdaters;
2181 if (pass == 1 && !solv->decisioncnt_keep)
2182 solv->decisioncnt_keep = solv->decisionq.count;
2183 /* start with installedpos, the position that gave us problems the last time */
2184 for (i = installedpos, n = installed->start; n < installed->end; i++, n++)
2189 if (i == installed->end)
2190 i = installed->start;
2191 s = pool->solvables + i;
2192 if (s->repo != installed)
2195 if (solv->decisionmap[i] > 0 && (!specialupdaters || !specialupdaters[i - installed->start]))
2196 continue; /* already decided */
2197 if (!pass && solv->updatemap.size && !MAPTST(&solv->updatemap, i - installed->start))
2198 continue; /* updates first */
2199 r = solv->rules + solv->updaterules + (i - installed->start);
2201 if (!rr->p || rr->d < 0) /* disabled -> look at feature rule */
2202 rr -= solv->installed->end - solv->installed->start;
2203 if (!rr->p) /* identical to update rule? */
2205 if (!rr->p && !(specialupdaters && specialupdaters[i - installed->start]))
2206 continue; /* orpaned package */
2208 /* check if we should update this package to the latest version
2209 * noupdate is set for erase jobs, in that case we want to deinstall
2210 * the installed package and not replace it with a newer version
2211 * rr->p != i is for dup jobs where the installed package cannot be kept */
2213 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)))
2217 /* specialupdater with no update/feature rule */
2218 for (d = specialupdaters[i - installed->start]; (p = pool->whatprovidesdata[d++]) != 0; )
2220 if (solv->decisionmap[p] > 0)
2225 if (!solv->decisionmap[p])
2229 else if (specialupdaters && (d = specialupdaters[i - installed->start]) != 0)
2231 /* special multiversion handling, make sure best version is chosen */
2232 if (rr->p == i && solv->decisionmap[i] >= 0)
2234 while ((p = pool->whatprovidesdata[d++]) != 0)
2235 if (solv->decisionmap[p] >= 0)
2237 if (dq.count && solv->update_targets && solv->update_targets->elements[i - installed->start])
2238 prune_to_update_targets(solv, solv->update_targets->elements + solv->update_targets->elements[i - installed->start], &dq);
2241 policy_filter_unwanted(solv, &dq, POLICY_MODE_CHOOSE);
2243 if (p != i && solv->decisionmap[p] == 0)
2245 rr = solv->rules + solv->featurerules + (i - solv->installed->start);
2246 if (!rr->p) /* update rule == feature rule? */
2247 rr = rr - solv->featurerules + solv->updaterules;
2256 /* update to best package of the update rule */
2257 FOR_RULELITERALS(p, pp, rr)
2259 if (solv->decisionmap[p] > 0)
2261 dq.count = 0; /* already fulfilled */
2264 if (!solv->decisionmap[p])
2269 if (dq.count && solv->update_targets && solv->update_targets->elements[i - installed->start])
2270 prune_to_update_targets(solv, solv->update_targets->elements + solv->update_targets->elements[i - installed->start], &dq);
2271 /* install best version */
2275 level = selectandinstall(solv, level, &dq, disablerules, rr - solv->rules);
2282 if (level <= olevel)
2284 if (level == 1 || level < passlevel)
2285 break; /* trouble */
2287 n = installed->start; /* redo all */
2293 /* if still undecided keep package */
2294 if (solv->decisionmap[i] == 0)
2297 if (solv->cleandepsmap.size && MAPTST(&solv->cleandepsmap, i - installed->start))
2300 POOL_DEBUG(SOLV_DEBUG_POLICY, "cleandeps erasing %s\n", pool_solvid2str(pool, i));
2301 level = setpropagatelearn(solv, level, -i, disablerules, 0);
2308 POOL_DEBUG(SOLV_DEBUG_POLICY, "keeping %s\n", pool_solvid2str(pool, i));
2309 level = setpropagatelearn(solv, level, i, disablerules, r - solv->rules);
2313 if (level <= olevel)
2315 if (level == 1 || level < passlevel)
2316 break; /* trouble */
2318 n = installed->start; /* redo all */
2321 continue; /* retry with learnt rule */
2325 if (n < installed->end)
2327 installedpos = i; /* retry problem solvable next time */
2328 break; /* ran into trouble */
2330 installedpos = installed->start; /* reset installedpos */
2333 break; /* unsolvable */
2334 systemlevel = level + 1;
2336 continue; /* had trouble, retry */
2338 if (!solv->decisioncnt_keep)
2339 solv->decisioncnt_keep = solv->decisionq.count;
2341 if (level < systemlevel && solv->focus_installed)
2344 level = resolve_jobrules(solv, level, disablerules, &dq);
2348 break; /* unsolvable */
2351 systemlevel = level + 1;
2354 if (level < systemlevel)
2355 systemlevel = level;
2360 if (!solv->decisioncnt_resolve)
2361 solv->decisioncnt_resolve = solv->decisionq.count;
2362 POOL_DEBUG(SOLV_DEBUG_POLICY, "deciding unresolved rules\n");
2363 for (i = 1, n = 1; n < solv->nrules; i++, n++)
2365 if (i == solv->nrules)
2367 r = solv->rules + i;
2368 if (r->d < 0) /* ignore disabled rules */
2370 if (r->p < 0) /* most common cases first */
2372 if (r->d == 0 || solv->decisionmap[-r->p] <= 0)
2379 /* binary or unary rule */
2380 /* need two positive undecided literals, r->p already checked above */
2383 if (solv->decisionmap[r->p] || solv->decisionmap[r->w2])
2385 queue_push(&dq, r->p);
2386 queue_push(&dq, r->w2);
2391 * all negative literals are installed
2392 * no positive literal is installed
2393 * i.e. the rule is not fulfilled and we
2394 * just need to decide on the positive literals
2395 * (decisionmap[-r->p] for the r->p < 0 case is already checked above)
2399 if (solv->decisionmap[r->p] > 0)
2401 if (solv->decisionmap[r->p] == 0)
2402 queue_push(&dq, r->p);
2404 dp = pool->whatprovidesdata + r->d;
2405 while ((p = *dp++) != 0)
2409 if (solv->decisionmap[-p] <= 0)
2414 if (solv->decisionmap[p] > 0)
2416 if (solv->decisionmap[p] == 0)
2423 IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
2425 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "unfulfilled ");
2426 solver_printruleclass(solv, SOLV_DEBUG_PROPAGATE, r);
2428 /* dq.count < 2 cannot happen as this means that
2429 * the rule is unit */
2430 assert(dq.count > 1);
2432 /* prune to cleandeps packages */
2433 if (solv->cleandepsmap.size && solv->installed)
2435 Repo *installed = solv->installed;
2436 for (j = 0; j < dq.count; j++)
2437 if (pool->solvables[dq.elements[j]].repo == installed && MAPTST(&solv->cleandepsmap, dq.elements[j] - installed->start))
2441 dq.elements[0] = dq.elements[j];
2442 queue_truncate(&dq, 1);
2447 level = selectandinstall(solv, level, &dq, disablerules, r - solv->rules);
2449 break; /* unsolvable */
2450 if (level < systemlevel || level == 1)
2451 break; /* trouble */
2452 /* something changed, so look at all rules again */
2456 if (n != solv->nrules) /* ran into trouble? */
2459 break; /* unsolvable */
2460 continue; /* start over */
2463 /* decide leftover cleandeps packages */
2464 if (solv->cleandepsmap.size && solv->installed)
2466 for (p = solv->installed->start; p < solv->installed->end; p++)
2468 s = pool->solvables + p;
2469 if (s->repo != solv->installed)
2471 if (solv->decisionmap[p] == 0 && MAPTST(&solv->cleandepsmap, p - solv->installed->start))
2473 POOL_DEBUG(SOLV_DEBUG_POLICY, "cleandeps erasing %s\n", pool_solvid2str(pool, p));
2475 level = setpropagatelearn(solv, level, -p, 0, 0);
2480 if (p < solv->installed->end)
2484 /* at this point we have a consistent system. now do the extras... */
2486 if (!solv->decisioncnt_weak)
2487 solv->decisioncnt_weak = solv->decisionq.count;
2492 POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended packages\n");
2493 queue_empty(&dq); /* recommended packages */
2494 queue_empty(&dqs); /* supplemented packages */
2495 for (i = 1; i < pool->nsolvables; i++)
2497 if (solv->decisionmap[i] < 0)
2499 if (solv->decisionmap[i] > 0)
2501 /* installed, check for recommends */
2502 Id *recp, rec, pp, p;
2503 s = pool->solvables + i;
2504 if (!solv->addalreadyrecommended && s->repo == solv->installed)
2506 /* XXX need to special case AND ? */
2509 recp = s->repo->idarraydata + s->recommends;
2510 while ((rec = *recp++) != 0)
2512 #ifdef ENABLE_COMPLEX_DEPS
2513 if (pool_is_complex_dep(pool, rec))
2515 add_complex_recommends(solv, rec, &dq, 0);
2520 FOR_PROVIDES(p, pp, rec)
2522 if (solv->decisionmap[p] > 0)
2527 else if (solv->decisionmap[p] == 0)
2529 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))))
2531 queue_pushunique(&dq, p);
2539 s = pool->solvables + i;
2540 if (!s->supplements)
2542 if (!pool_installable(pool, s))
2544 if (!solver_is_supplementing(solv, s))
2546 if (solv->dupmap_all && solv->installed && s->repo == solv->installed && (solv->droporphanedmap_all || (solv->droporphanedmap.size && MAPTST(&solv->droporphanedmap, i - solv->installed->start))))
2548 queue_push(&dqs, i);
2552 /* filter out all packages obsoleted by installed packages */
2553 /* this is no longer needed if we have reverse obsoletes */
2554 if ((dqs.count || dq.count) && solv->installed)
2557 Id obs, *obsp, po, ppo;
2559 map_init(&obsmap, pool->nsolvables);
2560 for (p = solv->installed->start; p < solv->installed->end; p++)
2562 s = pool->solvables + p;
2563 if (s->repo != solv->installed || !s->obsoletes)
2565 if (solv->decisionmap[p] <= 0)
2567 if (solv->multiversion.size && MAPTST(&solv->multiversion, p))
2569 obsp = s->repo->idarraydata + s->obsoletes;
2570 /* foreach obsoletes */
2571 while ((obs = *obsp++) != 0)
2572 FOR_PROVIDES(po, ppo, obs)
2573 MAPSET(&obsmap, po);
2575 for (i = j = 0; i < dqs.count; i++)
2576 if (!MAPTST(&obsmap, dqs.elements[i]))
2577 dqs.elements[j++] = dqs.elements[i];
2579 for (i = j = 0; i < dq.count; i++)
2580 if (!MAPTST(&obsmap, dq.elements[i]))
2581 dq.elements[j++] = dq.elements[i];
2586 /* filter out all already supplemented packages if requested */
2587 if (!solv->addalreadyrecommended && dqs.count)
2589 /* turn off all new packages */
2590 for (i = 0; i < solv->decisionq.count; i++)
2592 p = solv->decisionq.elements[i];
2595 s = pool->solvables + p;
2596 if (s->repo && s->repo != solv->installed)
2597 solv->decisionmap[p] = -solv->decisionmap[p];
2599 /* filter out old supplements */
2600 for (i = j = 0; i < dqs.count; i++)
2602 p = dqs.elements[i];
2603 s = pool->solvables + p;
2604 if (!s->supplements)
2606 if (!solver_is_supplementing(solv, s))
2607 dqs.elements[j++] = p;
2608 else if (solv->installsuppdepq && solver_check_installsuppdepq(solv, s))
2609 dqs.elements[j++] = p;
2612 /* undo turning off */
2613 for (i = 0; i < solv->decisionq.count; i++)
2615 p = solv->decisionq.elements[i];
2618 s = pool->solvables + p;
2619 if (s->repo && s->repo != solv->installed)
2620 solv->decisionmap[p] = -solv->decisionmap[p];
2624 /* multiversion doesn't mix well with supplements.
2625 * filter supplemented packages where we already decided
2626 * to install a different version (see bnc#501088) */
2627 if (dqs.count && solv->multiversion.size)
2629 for (i = j = 0; i < dqs.count; i++)
2631 p = dqs.elements[i];
2632 if (MAPTST(&solv->multiversion, p))
2635 s = pool->solvables + p;
2636 FOR_PROVIDES(p2, pp2, s->name)
2637 if (solv->decisionmap[p2] > 0 && pool->solvables[p2].name == s->name)
2640 continue; /* ignore this package */
2642 dqs.elements[j++] = p;
2647 /* make dq contain both recommended and supplemented pkgs */
2650 for (i = 0; i < dqs.count; i++)
2651 queue_pushunique(&dq, dqs.elements[i]);
2657 int decisioncount = solv->decisionq.count;
2661 /* simple case, just one package. no need to choose to best version */
2664 POOL_DEBUG(SOLV_DEBUG_POLICY, "installing supplemented %s\n", pool_solvid2str(pool, p));
2666 POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended %s\n", pool_solvid2str(pool, p));
2667 level = setpropagatelearn(solv, level, p, 0, 0);
2670 continue; /* back to main loop */
2673 /* filter packages, this gives us the best versions */
2674 policy_filter_unwanted(solv, &dq, POLICY_MODE_RECOMMEND);
2676 /* create map of result */
2677 map_init(&dqmap, pool->nsolvables);
2678 for (i = 0; i < dq.count; i++)
2679 MAPSET(&dqmap, dq.elements[i]);
2681 /* install all supplemented packages */
2682 for (i = 0; i < dqs.count; i++)
2684 p = dqs.elements[i];
2685 if (solv->decisionmap[p] || !MAPTST(&dqmap, p))
2687 POOL_DEBUG(SOLV_DEBUG_POLICY, "installing supplemented %s\n", pool_solvid2str(pool, p));
2689 level = setpropagatelearn(solv, level, p, 0, 0);
2690 if (level <= olevel)
2693 if (i < dqs.count || solv->decisionq.count < decisioncount)
2701 /* install all recommended packages */
2702 /* more work as we want to created branches if multiple
2703 * choices are valid */
2704 for (i = 0; i < decisioncount; i++)
2707 p = solv->decisionq.elements[i];
2710 s = pool->solvables + p;
2711 if (!s->repo || (!solv->addalreadyrecommended && s->repo == solv->installed))
2715 recp = s->repo->idarraydata + s->recommends;
2716 while ((rec = *recp++) != 0)
2719 #ifdef ENABLE_COMPLEX_DEPS
2720 if (pool_is_complex_dep(pool, rec))
2721 add_complex_recommends(solv, rec, &dq, &dqmap);
2724 FOR_PROVIDES(p, pp, rec)
2726 if (solv->decisionmap[p] > 0)
2731 else if (solv->decisionmap[p] == 0 && MAPTST(&dqmap, p))
2737 policy_filter_unwanted(solv, &dq, POLICY_MODE_CHOOSE);
2738 /* if we have multiple candidates we open a branch */
2740 createbranch(solv, level, &dq, s - pool->solvables, rec);
2742 POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended %s\n", pool_solvid2str(pool, p));
2744 level = setpropagatelearn(solv, level, p, 0, 0);
2745 if (level <= olevel || solv->decisionq.count < decisioncount)
2746 break; /* we had to revert some decisions */
2749 break; /* had a problem above, quit loop */
2754 continue; /* back to main loop so that all deps are checked */
2758 if (!solv->decisioncnt_orphan)
2759 solv->decisioncnt_orphan = solv->decisionq.count;
2760 if (solv->dupmap_all && solv->installed)
2762 int installedone = 0;
2764 /* let's see if we can install some unsupported package */
2765 POOL_DEBUG(SOLV_DEBUG_SOLVER, "deciding orphaned packages\n");
2766 for (i = 0; i < solv->orphaned.count; i++)
2768 p = solv->orphaned.elements[i];
2769 if (solv->decisionmap[p])
2770 continue; /* already decided */
2771 if (solv->droporphanedmap_all)
2773 if (solv->droporphanedmap.size && MAPTST(&solv->droporphanedmap, p - solv->installed->start))
2775 POOL_DEBUG(SOLV_DEBUG_SOLVER, "keeping orphaned %s\n", pool_solvid2str(pool, p));
2777 level = setpropagatelearn(solv, level, p, 0, 0);
2782 if (installedone || i < solv->orphaned.count)
2786 continue; /* back to main loop */
2788 for (i = 0; i < solv->orphaned.count; i++)
2790 p = solv->orphaned.elements[i];
2791 if (solv->decisionmap[p])
2792 continue; /* already decided */
2793 POOL_DEBUG(SOLV_DEBUG_SOLVER, "removing orphaned %s\n", pool_solvid2str(pool, p));
2795 level = setpropagatelearn(solv, level, -p, 0, 0);
2799 if (i < solv->orphaned.count)
2803 continue; /* back to main loop */
2805 if (solv->brokenorphanrules)
2807 solver_check_brokenorphanrules(solv, &dq);
2810 policy_filter_unwanted(solv, &dq, POLICY_MODE_CHOOSE);
2811 for (i = 0; i < dq.count; i++)
2814 POOL_DEBUG(SOLV_DEBUG_POLICY, "installing orphaned dep %s\n", pool_solvid2str(pool, p));
2816 level = setpropagatelearn(solv, level, p, 0, 0);
2827 /* one final pass to make sure we decided all installed packages */
2828 if (solv->installed)
2830 for (p = solv->installed->start; p < solv->installed->end; p++)
2832 if (solv->decisionmap[p])
2833 continue; /* already decided */
2834 s = pool->solvables + p;
2835 if (s->repo != solv->installed)
2837 POOL_DEBUG(SOLV_DEBUG_SOLVER, "removing unwanted %s\n", pool_solvid2str(pool, p));
2839 level = setpropagatelearn(solv, level, -p, 0, 0);
2843 if (p < solv->installed->end)
2847 continue; /* back to main loop */
2851 if (solv->installed && solv->cleandepsmap.size)
2853 if (cleandeps_check_mistakes(solv, level))
2855 level = 1; /* restart from scratch */
2856 systemlevel = level + 1;
2861 if (solv->solution_callback)
2863 solv->solution_callback(solv, solv->solution_callback_data);
2864 if (solv->branches.count)
2868 for (i = solv->branches.count - 1; i >= 0; i--)
2870 p = solv->branches.elements[i];
2875 i -= 3; /* skip: p data count */
2884 while (i > 0 && solv->branches.elements[i - 1] > 0)
2886 level = takebranch(solv, i, endi, "branching", disablerules);
2892 /* all branches done, we're finally finished */
2896 /* auto-minimization step */
2897 if (solv->branches.count)
2899 int endi, lasti = -1, lastiend = -1;
2900 if (solv->recommends_index < solv->decisionq.count)
2901 policy_update_recommendsmap(solv);
2902 for (endi = solv->branches.count; endi > 0;)
2904 int l, lastsi = -1, starti = endi - solv->branches.elements[endi - 2];
2905 l = solv->branches.elements[endi - 1];
2906 for (i = starti; i < endi - 4; i++)
2908 p = solv->branches.elements[i];
2911 if (solv->decisionmap[p] > l)
2918 if (lastsi < 0 && (MAPTST(&solv->recommendsmap, p) || solver_is_supplementing(solv, pool->solvables + p)))
2923 /* we have a recommended package that could not be installed */
2924 /* take it if our current selection is not recommended */
2925 for (i = starti; i < endi - 4; i++)
2927 p = -solv->branches.elements[i];
2928 if (p <= 0 || solv->decisionmap[p] != l + 1)
2930 if (!(MAPTST(&solv->recommendsmap, p) || solver_is_supplementing(solv, pool->solvables + p)))
2942 minimizationsteps++;
2943 level = takebranch(solv, lasti, lastiend, "minimizing", disablerules);
2946 continue; /* back to main loop */
2949 /* no minimization found, we're finally finished! */
2953 POOL_DEBUG(SOLV_DEBUG_STATS, "solver statistics: %d learned rules, %d unsolvable, %d minimization steps\n", solv->stats_learned, solv->stats_unsolvable, minimizationsteps);
2955 POOL_DEBUG(SOLV_DEBUG_STATS, "done solving.\n\n");
2961 solv->decisioncnt_jobs = solv->decisionq.count;
2962 solv->decisioncnt_update = solv->decisionq.count;
2963 solv->decisioncnt_keep = solv->decisionq.count;
2964 solv->decisioncnt_resolve = solv->decisionq.count;
2965 solv->decisioncnt_weak = solv->decisionq.count;
2966 solv->decisioncnt_orphan = solv->decisionq.count;
2969 solver_printdecisionq(solv, SOLV_DEBUG_RESULT);
2974 /*-------------------------------------------------------------------
2976 * remove disabled conflicts
2978 * purpose: update the decisionmap after some rules were disabled.
2979 * this is used to calculate the suggested/recommended package list.
2980 * Also returns a "removed" list to undo the discisionmap changes.
2984 removedisabledconflicts(Solver *solv, Queue *removed)
2986 Pool *pool = solv->pool;
2991 Id *decisionmap = solv->decisionmap;
2993 queue_empty(removed);
2994 for (i = 0; i < solv->decisionq.count; i++)
2996 p = solv->decisionq.elements[i];
2998 continue; /* conflicts only, please */
2999 why = solv->decisionq_why.elements[i];
3002 /* no rule involved, must be a orphan package drop */
3005 /* we never do conflicts on free decisions, so there
3006 * must have been an unit rule */
3008 r = solv->rules + why;
3009 if (r->d < 0 && decisionmap[-p])
3011 /* rule is now disabled, remove from decisionmap */
3012 POOL_DEBUG(SOLV_DEBUG_SOLVER, "removing conflict for package %s[%d]\n", pool_solvid2str(pool, -p), -p);
3013 queue_push(removed, -p);
3014 queue_push(removed, decisionmap[-p]);
3015 decisionmap[-p] = 0;
3018 if (!removed->count)
3020 /* we removed some confliced packages. some of them might still
3021 * be in conflict, so search for unit rules and re-conflict */
3023 for (i = n = 1, r = solv->rules + i; n < solv->nrules; i++, r++, n++)
3025 if (i == solv->nrules)
3028 r = solv->rules + i;
3034 if (r->p < 0 && !decisionmap[-r->p])
3040 if (r->p < 0 && decisionmap[-r->p] == 0 && DECISIONMAP_FALSE(r->w2))
3042 else if (r->w2 < 0 && decisionmap[-r->w2] == 0 && DECISIONMAP_FALSE(r->p))
3047 if (r->p < 0 && decisionmap[-r->p] == 0)
3049 if (new || DECISIONMAP_FALSE(r->p))
3051 dp = pool->whatprovidesdata + r->d;
3052 while ((p = *dp++) != 0)
3054 if (new && p == new)
3056 if (p < 0 && decisionmap[-p] == 0)
3065 else if (!DECISIONMAP_FALSE(p))
3075 POOL_DEBUG(SOLV_DEBUG_SOLVER, "re-conflicting package %s[%d]\n", pool_solvid2str(pool, -new), -new);
3076 decisionmap[-new] = -1;
3078 n = 0; /* redo all rules */
3084 undo_removedisabledconflicts(Solver *solv, Queue *removed)
3087 for (i = 0; i < removed->count; i += 2)
3088 solv->decisionmap[removed->elements[i]] = removed->elements[i + 1];
3092 /*-------------------------------------------------------------------
3094 * weaken solvable dependencies
3098 weaken_solvable_deps(Solver *solv, Id p)
3103 for (i = 1, r = solv->rules + i; i < solv->pkgrules_end; i++, r++)
3107 if ((r->d == 0 || r->d == -1) && r->w2 < 0)
3108 continue; /* conflict */
3109 queue_push(&solv->weakruleq, i);
3114 /********************************************************************/
3119 solver_calculate_multiversionmap(Pool *pool, Queue *job, Map *multiversionmap)
3122 Id how, what, select;
3124 for (i = 0; i < job->count; i += 2)
3126 how = job->elements[i];
3127 if ((how & SOLVER_JOBMASK) != SOLVER_MULTIVERSION)
3129 what = job->elements[i + 1];
3130 select = how & SOLVER_SELECTMASK;
3131 if (!multiversionmap->size)
3132 map_grow(multiversionmap, pool->nsolvables);
3133 if (select == SOLVER_SOLVABLE_ALL)
3135 FOR_POOL_SOLVABLES(p)
3136 MAPSET(multiversionmap, p);
3138 else if (select == SOLVER_SOLVABLE_REPO)
3141 Repo *repo = pool_id2repo(pool, what);
3143 FOR_REPO_SOLVABLES(repo, p, s)
3144 MAPSET(multiversionmap, p);
3146 FOR_JOB_SELECT(p, pp, select, what)
3147 MAPSET(multiversionmap, p);
3152 solver_calculate_noobsmap(Pool *pool, Queue *job, Map *multiversionmap)
3154 solver_calculate_multiversionmap(pool, job, multiversionmap);
3158 * add a rule created by a job, record job number and weak flag
3161 solver_addjobrule(Solver *solv, Id p, Id d, Id job, int weak)
3163 solver_addrule(solv, p, d);
3164 queue_push(&solv->ruletojob, job);
3166 queue_push(&solv->weakruleq, solv->nrules - 1);
3170 add_cleandeps_package(Solver *solv, Id p)
3172 if (!solv->cleandeps_updatepkgs)
3174 solv->cleandeps_updatepkgs = solv_calloc(1, sizeof(Queue));
3175 queue_init(solv->cleandeps_updatepkgs);
3177 queue_pushunique(solv->cleandeps_updatepkgs, p);
3181 add_update_target(Solver *solv, Id p, Id how)
3183 Pool *pool = solv->pool;
3184 Solvable *s = pool->solvables + p;
3185 Repo *installed = solv->installed;
3187 if (!solv->update_targets)
3189 solv->update_targets = solv_calloc(1, sizeof(Queue));
3190 queue_init(solv->update_targets);
3192 if (s->repo == installed)
3194 queue_push2(solv->update_targets, p, p);
3197 FOR_PROVIDES(pi, pip, s->name)
3199 Solvable *si = pool->solvables + pi;
3200 if (si->repo != installed || si->name != s->name)
3202 if (how & SOLVER_FORCEBEST)
3204 if (!solv->bestupdatemap.size)
3205 map_grow(&solv->bestupdatemap, installed->end - installed->start);
3206 MAPSET(&solv->bestupdatemap, pi - installed->start);
3208 if (how & SOLVER_CLEANDEPS)
3209 add_cleandeps_package(solv, pi);
3210 queue_push2(solv->update_targets, pi, p);
3211 /* check if it's ok to keep the installed package */
3212 if (s->evr == si->evr && solvable_identical(s, si))
3213 queue_push2(solv->update_targets, pi, pi);
3217 Id obs, *obsp = s->repo->idarraydata + s->obsoletes;
3218 while ((obs = *obsp++) != 0)
3220 FOR_PROVIDES(pi, pip, obs)
3222 Solvable *si = pool->solvables + pi;
3223 if (si->repo != installed)
3225 if (si->name == s->name)
3226 continue; /* already handled above */
3227 if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, si, obs))
3229 if (pool->obsoleteusescolors && !pool_colormatch(pool, s, si))
3231 if (how & SOLVER_FORCEBEST)
3233 if (!solv->bestupdatemap.size)
3234 map_grow(&solv->bestupdatemap, installed->end - installed->start);
3235 MAPSET(&solv->bestupdatemap, pi - installed->start);
3237 if (how & SOLVER_CLEANDEPS)
3238 add_cleandeps_package(solv, pi);
3239 queue_push2(solv->update_targets, pi, p);
3246 transform_update_targets_sortfn(const void *ap, const void *bp, void *dp)
3256 transform_update_targets(Solver *solv)
3258 Repo *installed = solv->installed;
3259 Queue *update_targets = solv->update_targets;
3261 Id p, q, lastp, lastq;
3263 if (!update_targets->count)
3265 queue_free(update_targets);
3266 solv->update_targets = solv_free(update_targets);
3269 if (update_targets->count > 2)
3270 solv_sort(update_targets->elements, update_targets->count >> 1, 2 * sizeof(Id), transform_update_targets_sortfn, solv);
3271 queue_insertn(update_targets, 0, installed->end - installed->start, 0);
3273 for (i = j = installed->end - installed->start; i < update_targets->count; i += 2)
3275 if ((p = update_targets->elements[i]) != lastp)
3277 if (!solv->updatemap.size)
3278 map_grow(&solv->updatemap, installed->end - installed->start);
3279 MAPSET(&solv->updatemap, p - installed->start);
3280 update_targets->elements[j++] = 0; /* finish old set */
3281 update_targets->elements[p - installed->start] = j; /* start new set */
3285 if ((q = update_targets->elements[i + 1]) != lastq)
3287 update_targets->elements[j++] = q;
3291 queue_truncate(update_targets, j);
3292 queue_push(update_targets, 0); /* finish last set */
3297 addedmap2deduceq(Solver *solv, Map *addedmap)
3299 Pool *pool = solv->pool;
3304 queue_empty(&solv->addedmap_deduceq);
3305 for (i = 2, j = solv->pkgrules_end - 1; i < pool->nsolvables && j > 0; j--)
3307 r = solv->rules + j;
3310 if ((r->d == 0 || r->d == -1) && r->w2 < 0)
3313 if (!MAPTST(addedmap, p))
3315 /* should never happen, but... */
3316 if (!solv->addedmap_deduceq.count || solv->addedmap_deduceq.elements[solv->addedmap_deduceq.count - 1] != -p)
3317 queue_push(&solv->addedmap_deduceq, -p);
3321 if (MAPTST(addedmap, i))
3322 queue_push(&solv->addedmap_deduceq, i);
3326 for (; i < pool->nsolvables; i++)
3327 if (MAPTST(addedmap, i))
3328 queue_push(&solv->addedmap_deduceq, i);
3330 for (i = 2; i < pool->nsolvables; i++)
3331 if (MAPTST(addedmap, i))
3336 deduceq2addedmap(Solver *solv, Map *addedmap)
3341 for (j = solv->pkgrules_end - 1; j > 0; j--)
3343 r = solv->rules + j;
3344 if (r->d < 0 && r->p)
3345 solver_enablerule(solv, r);
3348 if ((r->d == 0 || r->d == -1) && r->w2 < 0)
3351 MAPSET(addedmap, p);
3353 for (j = 0; j < solv->addedmap_deduceq.count; j++)
3355 p = solv->addedmap_deduceq.elements[j];
3357 MAPSET(addedmap, p);
3359 MAPCLR(addedmap, p);
3371 solver_solve(Solver *solv, Queue *job)
3373 Pool *pool = solv->pool;
3374 Repo *installed = solv->installed;
3376 int oldnrules, initialnrules;
3377 Map addedmap; /* '1' == have pkg-rules for solvable */
3378 Map installcandidatemap;
3379 Id how, what, select, name, weak, p, pp, d;
3383 int now, solve_start;
3385 int hasbestinstalljob = 0;
3387 solve_start = solv_timems(0);
3389 /* log solver options */
3390 POOL_DEBUG(SOLV_DEBUG_STATS, "solver started\n");
3391 POOL_DEBUG(SOLV_DEBUG_STATS, "dosplitprovides=%d, noupdateprovide=%d, noinfarchcheck=%d\n", solv->dosplitprovides, solv->noupdateprovide, solv->noinfarchcheck);
3392 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);
3393 POOL_DEBUG(SOLV_DEBUG_STATS, "promoteepoch=%d, forbidselfconflicts=%d\n", pool->promoteepoch, pool->forbidselfconflicts);
3394 POOL_DEBUG(SOLV_DEBUG_STATS, "obsoleteusesprovides=%d, implicitobsoleteusesprovides=%d, obsoleteusescolors=%d, implicitobsoleteusescolors=%d\n", pool->obsoleteusesprovides, pool->implicitobsoleteusesprovides, pool->obsoleteusescolors, pool->implicitobsoleteusescolors);
3395 POOL_DEBUG(SOLV_DEBUG_STATS, "dontinstallrecommended=%d, addalreadyrecommended=%d\n", solv->dontinstallrecommended, solv->addalreadyrecommended);
3397 /* create whatprovides if not already there */
3398 if (!pool->whatprovides)
3399 pool_createwhatprovides(pool);
3401 /* create obsolete index */
3402 policy_create_obsolete_index(solv);
3405 queue_free(&solv->job);
3406 queue_init_clone(&solv->job, job);
3407 solv->pooljobcnt = pool->pooljobs.count;
3408 if (pool->pooljobs.count)
3409 queue_insertn(&solv->job, 0, pool->pooljobs.count, pool->pooljobs.elements);
3412 /* free old stuff in jase we re-run a solver */
3413 queuep_free(&solv->update_targets);
3414 queuep_free(&solv->cleandeps_updatepkgs);
3415 queue_empty(&solv->ruleassertions);
3416 solv->bestrules_pkg = solv_free(solv->bestrules_pkg);
3417 solv->yumobsrules_info = solv_free(solv->yumobsrules_info);
3418 solv->choicerules_ref = solv_free(solv->choicerules_ref);
3419 if (solv->noupdate.size)
3420 map_empty(&solv->noupdate);
3421 map_zerosize(&solv->multiversion);
3422 solv->updatemap_all = 0;
3423 map_zerosize(&solv->updatemap);
3424 solv->bestupdatemap_all = 0;
3425 map_zerosize(&solv->bestupdatemap);
3426 solv->fixmap_all = 0;
3427 map_zerosize(&solv->fixmap);
3428 solv->dupmap_all = 0;
3429 map_zerosize(&solv->dupmap);
3430 map_zerosize(&solv->dupinvolvedmap);
3431 solv->droporphanedmap_all = 0;
3432 map_zerosize(&solv->droporphanedmap);
3433 map_zerosize(&solv->cleandepsmap);
3434 map_zerosize(&solv->weakrulemap);
3435 queue_empty(&solv->weakruleq);
3436 solv->watches = solv_free(solv->watches);
3437 queue_empty(&solv->ruletojob);
3438 if (solv->decisionq.count)
3439 memset(solv->decisionmap, 0, pool->nsolvables * sizeof(Id));
3440 queue_empty(&solv->decisionq);
3441 queue_empty(&solv->decisionq_why);
3442 solv->decisioncnt_jobs = solv->decisioncnt_update = solv->decisioncnt_keep = solv->decisioncnt_resolve = solv->decisioncnt_weak = solv->decisioncnt_orphan = 0;
3443 queue_empty(&solv->learnt_why);
3444 queue_empty(&solv->learnt_pool);
3445 queue_empty(&solv->branches);
3446 solv->propagate_index = 0;
3447 queue_empty(&solv->problems);
3448 queue_empty(&solv->solutions);
3449 queue_empty(&solv->orphaned);
3450 solv->stats_learned = solv->stats_unsolvable = 0;
3451 if (solv->recommends_index)
3453 map_empty(&solv->recommendsmap);
3454 map_empty(&solv->suggestsmap);
3455 queuep_free(&solv->recommendscplxq);
3456 queuep_free(&solv->suggestscplxq);
3457 solv->recommends_index = 0;
3459 queuep_free(&solv->brokenorphanrules);
3460 solv->specialupdaters = solv_free(solv->specialupdaters);
3464 * create basic rule set of all involved packages
3465 * use addedmap bitmap to make sure we don't create rules twice
3468 /* create multiversion map if needed */
3469 solver_calculate_multiversionmap(pool, job, &solv->multiversion);
3471 map_init(&addedmap, pool->nsolvables);
3472 MAPSET(&addedmap, SYSTEMSOLVABLE);
3474 map_init(&installcandidatemap, pool->nsolvables);
3477 now = solv_timems(0);
3479 * create rules for all package that could be involved with the solving
3480 * so called: pkg rules
3483 initialnrules = solv->pkgrules_end ? solv->pkgrules_end : 1;
3484 if (initialnrules > 1)
3485 deduceq2addedmap(solv, &addedmap);
3486 if (solv->nrules != initialnrules)
3487 solver_shrinkrules(solv, initialnrules);
3488 solv->nrules = initialnrules;
3489 solv->pkgrules_end = 0;
3493 /* check for update/verify jobs as they need to be known early */
3494 /* also setup the droporphaned map, we need it when creating update rules */
3495 for (i = 0; i < job->count; i += 2)
3497 how = job->elements[i];
3498 what = job->elements[i + 1];
3499 select = how & SOLVER_SELECTMASK;
3500 switch (how & SOLVER_JOBMASK)
3503 if (select == SOLVER_SOLVABLE_ALL || (select == SOLVER_SOLVABLE_REPO && installed && what == installed->repoid))
3504 solv->fixmap_all = 1;
3505 FOR_JOB_SELECT(p, pp, select, what)
3507 s = pool->solvables + p;
3508 if (s->repo != installed)
3510 if (!solv->fixmap.size)
3511 map_grow(&solv->fixmap, installed->end - installed->start);
3512 MAPSET(&solv->fixmap, p - installed->start);
3516 if (select == SOLVER_SOLVABLE_ALL)
3518 solv->updatemap_all = 1;
3519 if (how & SOLVER_FORCEBEST)
3520 solv->bestupdatemap_all = 1;
3521 if (how & SOLVER_CLEANDEPS)
3523 FOR_REPO_SOLVABLES(installed, p, s)
3524 add_cleandeps_package(solv, p);
3527 else if (select == SOLVER_SOLVABLE_REPO)
3529 Repo *repo = pool_id2repo(pool, what);
3532 if (repo == installed && !(how & SOLVER_TARGETED))
3534 solv->updatemap_all = 1;
3535 if (how & SOLVER_FORCEBEST)
3536 solv->bestupdatemap_all = 1;
3537 if (how & SOLVER_CLEANDEPS)
3539 FOR_REPO_SOLVABLES(installed, p, s)
3540 add_cleandeps_package(solv, p);
3544 if (solv->noautotarget && !(how & SOLVER_TARGETED))
3546 /* targeted update */
3547 FOR_REPO_SOLVABLES(repo, p, s)
3548 add_update_target(solv, p, how);
3552 if (!(how & SOLVER_TARGETED))
3555 FOR_JOB_SELECT(p, pp, select, what)
3557 s = pool->solvables + p;
3558 if (s->repo != installed)
3560 if (!solv->updatemap.size)
3561 map_grow(&solv->updatemap, installed->end - installed->start);
3562 MAPSET(&solv->updatemap, p - installed->start);
3563 if (how & SOLVER_FORCEBEST)
3565 if (!solv->bestupdatemap.size)
3566 map_grow(&solv->bestupdatemap, installed->end - installed->start);
3567 MAPSET(&solv->bestupdatemap, p - installed->start);
3569 if (how & SOLVER_CLEANDEPS)
3570 add_cleandeps_package(solv, p);
3573 if (!targeted || solv->noautotarget)
3576 FOR_JOB_SELECT(p, pp, select, what)
3577 add_update_target(solv, p, how);
3580 case SOLVER_DROP_ORPHANED:
3581 if (select == SOLVER_SOLVABLE_ALL || (select == SOLVER_SOLVABLE_REPO && what == installed->repoid))
3582 solv->droporphanedmap_all = 1;
3583 FOR_JOB_SELECT(p, pp, select, what)
3585 s = pool->solvables + p;
3586 if (s->repo != installed)
3588 if (!solv->droporphanedmap.size)
3589 map_grow(&solv->droporphanedmap, installed->end - installed->start);
3590 MAPSET(&solv->droporphanedmap, p - installed->start);
3598 if (solv->update_targets)
3599 transform_update_targets(solv);
3601 oldnrules = solv->nrules;
3602 FOR_REPO_SOLVABLES(installed, p, s)
3603 solver_addpkgrulesforsolvable(solv, s, &addedmap);
3604 POOL_DEBUG(SOLV_DEBUG_STATS, "added %d pkg rules for installed solvables\n", solv->nrules - oldnrules);
3605 oldnrules = solv->nrules;
3606 FOR_REPO_SOLVABLES(installed, p, s)
3607 solver_addpkgrulesforupdaters(solv, s, &addedmap, 1);
3608 POOL_DEBUG(SOLV_DEBUG_STATS, "added %d pkg rules for updaters of installed solvables\n", solv->nrules - oldnrules);
3612 * create rules for all packages involved in the job
3613 * (to be installed or removed)
3616 oldnrules = solv->nrules;
3617 for (i = 0; i < job->count; i += 2)
3619 how = job->elements[i];
3620 what = job->elements[i + 1];
3621 select = how & SOLVER_SELECTMASK;
3623 switch (how & SOLVER_JOBMASK)
3625 case SOLVER_INSTALL:
3626 FOR_JOB_SELECT(p, pp, select, what)
3628 MAPSET(&installcandidatemap, p);
3629 solver_addpkgrulesforsolvable(solv, pool->solvables + p, &addedmap);
3632 case SOLVER_DISTUPGRADE:
3633 if (select == SOLVER_SOLVABLE_ALL)
3635 solv->dupmap_all = 1;
3636 solv->updatemap_all = 1;
3637 if (how & SOLVER_FORCEBEST)
3638 solv->bestupdatemap_all = 1;
3640 if (!solv->dupmap_all)
3647 POOL_DEBUG(SOLV_DEBUG_STATS, "added %d pkg rules for packages involved in a job\n", solv->nrules - oldnrules);
3651 * add rules for suggests, enhances
3653 oldnrules = solv->nrules;
3654 if (hasdupjob && !solv->updatemap_all && solv->dosplitprovides && solv->installed)
3655 solver_addpkgrulesforweak(solv, &addedmap);
3657 solver_addpkgrulesforweak(solv, &addedmap);
3658 POOL_DEBUG(SOLV_DEBUG_STATS, "added %d pkg rules because of weak dependencies\n", solv->nrules - oldnrules);
3660 #ifdef ENABLE_LINKED_PKGS
3661 oldnrules = solv->nrules;
3662 solver_addpkgrulesforlinked(solv, &addedmap);
3663 POOL_DEBUG(SOLV_DEBUG_STATS, "added %d pkg rules because of linked packages\n", solv->nrules - oldnrules);
3667 * first pass done, we now have all the pkg rules we need.
3668 * unify existing rules before going over all job rules and
3670 * at this point the system is always solvable,
3671 * as an empty system (remove all packages) is a valid solution
3674 IF_POOLDEBUG (SOLV_DEBUG_STATS)
3676 int possible = 0, installable = 0;
3677 for (i = 1; i < pool->nsolvables; i++)
3679 if (pool_installable(pool, pool->solvables + i))
3681 if (MAPTST(&addedmap, i))
3684 POOL_DEBUG(SOLV_DEBUG_STATS, "%d of %d installable solvables considered for solving\n", possible, installable);
3687 if (solv->nrules > initialnrules)
3688 solver_unifyrules(solv); /* remove duplicate pkg rules */
3689 solv->pkgrules_end = solv->nrules; /* mark end of pkg rules */
3691 if (solv->nrules > initialnrules)
3692 addedmap2deduceq(solv, &addedmap); /* so that we can recreate the addedmap */
3694 POOL_DEBUG(SOLV_DEBUG_STATS, "pkg rule memory used: %d K\n", solv->nrules * (int)sizeof(Rule) / 1024);
3695 POOL_DEBUG(SOLV_DEBUG_STATS, "pkg rule creation took %d ms\n", solv_timems(now));
3697 /* create dup maps if needed. We need the maps early to create our
3700 solver_createdupmaps(solv);
3703 * create feature rules
3705 * foreach installed:
3706 * create assertion (keep installed, if no update available)
3708 * create update rule (A|update1(A)|update2(A)|...)
3710 * those are used later on to keep a version of the installed packages in
3714 solv->featurerules = solv->nrules; /* mark start of feature rules */
3717 /* foreach possibly installed solvable */
3718 for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
3720 if (s->repo != installed)
3722 solver_addrule(solv, 0, 0); /* create dummy rule */
3725 solver_addupdaterule(solv, s, 1); /* allow s to be updated */
3727 /* make sure we accounted for all rules */
3728 assert(solv->nrules - solv->featurerules == installed->end - installed->start);
3730 solv->featurerules_end = solv->nrules;
3733 * Add update rules for installed solvables
3735 * almost identical to feature rules
3736 * except that downgrades/archchanges/vendorchanges are not allowed
3739 solv->updaterules = solv->nrules;
3742 { /* foreach installed solvables */
3743 /* we create all update rules, but disable some later on depending on the job */
3744 for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
3748 if (s->repo != installed)
3750 solver_addrule(solv, 0, 0); /* create dummy rule */
3753 solver_addupdaterule(solv, s, 0); /* allowall = 0: downgrades not allowed */
3755 * check for and remove duplicate
3757 r = solv->rules + solv->nrules - 1; /* r: update rule */
3760 sr = r - (installed->end - installed->start); /* sr: feature rule */
3761 /* it's also orphaned if the feature rule consists just of the installed package */
3762 if (!solv->dupmap_all && sr->p == i && !sr->d && !sr->w2)
3763 queue_push(&solv->orphaned, i);
3764 if (!solver_rulecmp(solv, r, sr))
3765 memset(sr, 0, sizeof(*sr)); /* delete unneeded feature rule */
3767 solver_disablerule(solv, sr); /* disable feature rule for now */
3769 /* consistency check: we added a rule for _every_ installed solvable */
3770 assert(solv->nrules - solv->updaterules == installed->end - installed->start);
3772 solv->updaterules_end = solv->nrules;
3776 * now add all job rules
3779 solv->jobrules = solv->nrules;
3780 for (i = 0; i < job->count; i += 2)
3782 oldnrules = solv->nrules;
3784 if (i && i == solv->pooljobcnt)
3785 POOL_DEBUG(SOLV_DEBUG_JOB, "end of pool jobs\n");
3786 how = job->elements[i];
3787 what = job->elements[i + 1];
3788 weak = how & SOLVER_WEAK;
3789 select = how & SOLVER_SELECTMASK;
3790 switch (how & SOLVER_JOBMASK)
3792 case SOLVER_INSTALL:
3793 POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sinstall %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
3794 if ((how & SOLVER_CLEANDEPS) != 0 && !solv->cleandepsmap.size && installed)
3795 map_grow(&solv->cleandepsmap, installed->end - installed->start);
3796 if (select == SOLVER_SOLVABLE)
3804 FOR_JOB_SELECT(p, pp, select, what)
3808 if (select == SOLVER_SOLVABLE_ONE_OF)
3809 break; /* ignore empty installs */
3810 /* no candidate found or unsupported, make this an impossible rule */
3811 queue_push(&q, -SYSTEMSOLVABLE);
3813 p = queue_shift(&q); /* get first candidate */
3814 d = !q.count ? 0 : pool_queuetowhatprovides(pool, &q); /* internalize */
3816 /* force install of namespace supplements hack */
3817 if (select == SOLVER_SOLVABLE_PROVIDES && !d && (p == SYSTEMSOLVABLE || p == -SYSTEMSOLVABLE) && ISRELDEP(what))
3819 Reldep *rd = GETRELDEP(pool, what);
3820 if (rd->flags == REL_NAMESPACE)
3823 if (!solv->installsuppdepq)
3825 solv->installsuppdepq = solv_calloc(1, sizeof(Queue));
3826 queue_init(solv->installsuppdepq);
3828 queue_pushunique(solv->installsuppdepq, rd->evr == 0 ? rd->name : what);
3831 solver_addjobrule(solv, p, d, i, weak);
3832 if (how & SOLVER_FORCEBEST)
3833 hasbestinstalljob = 1;
3836 POOL_DEBUG(SOLV_DEBUG_JOB, "job: %s%serase %s\n", weak ? "weak " : "", how & SOLVER_CLEANDEPS ? "clean deps " : "", solver_select2str(pool, select, what));
3837 if ((how & SOLVER_CLEANDEPS) != 0 && !solv->cleandepsmap.size && installed)
3838 map_grow(&solv->cleandepsmap, installed->end - installed->start);
3839 /* specific solvable: by id or by nevra */
3840 name = (select == SOLVER_SOLVABLE || (select == SOLVER_SOLVABLE_NAME && ISRELDEP(what))) ? 0 : -1;
3841 if (select == SOLVER_SOLVABLE_ALL) /* hmmm ;) */
3843 FOR_POOL_SOLVABLES(p)
3844 solver_addjobrule(solv, -p, 0, i, weak);
3846 else if (select == SOLVER_SOLVABLE_REPO)
3848 Repo *repo = pool_id2repo(pool, what);
3850 FOR_REPO_SOLVABLES(repo, p, s)
3851 solver_addjobrule(solv, -p, 0, i, weak);
3853 FOR_JOB_SELECT(p, pp, select, what)
3855 s = pool->solvables + p;
3856 if (installed && s->repo == installed)
3857 name = !name ? s->name : -1;
3858 solver_addjobrule(solv, -p, 0, i, weak);
3860 /* special case for "erase a specific solvable": we also
3861 * erase all other solvables with that name, so that they
3862 * don't get picked up as replacement.
3863 * name is > 0 if exactly one installed solvable matched.
3865 /* XXX: look also at packages that obsolete this package? */
3870 FOR_PROVIDES(p, pp, name)
3872 s = pool->solvables + p;
3873 if (s->name != name)
3875 /* keep other versions installed */
3876 if (s->repo == installed)
3878 /* keep installcandidates of other jobs */
3879 if (MAPTST(&installcandidatemap, p))
3881 /* don't add the same rule twice */
3882 for (j = oldnrules; j < k; j++)
3883 if (solv->rules[j].p == -p)
3886 solver_addjobrule(solv, -p, 0, i, weak); /* remove by id */
3892 POOL_DEBUG(SOLV_DEBUG_JOB, "job: %supdate %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
3895 POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sverify %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
3897 case SOLVER_WEAKENDEPS:
3898 POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sweaken deps %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
3899 if (select != SOLVER_SOLVABLE)
3901 s = pool->solvables + what;
3902 weaken_solvable_deps(solv, what);
3904 case SOLVER_MULTIVERSION:
3905 POOL_DEBUG(SOLV_DEBUG_JOB, "job: %smultiversion %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
3908 POOL_DEBUG(SOLV_DEBUG_JOB, "job: %slock %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
3909 if (select == SOLVER_SOLVABLE_ALL)
3911 FOR_POOL_SOLVABLES(p)
3912 solver_addjobrule(solv, installed && pool->solvables[p].repo == installed ? p : -p, 0, i, weak);
3914 else if (select == SOLVER_SOLVABLE_REPO)
3916 Repo *repo = pool_id2repo(pool, what);
3918 FOR_REPO_SOLVABLES(repo, p, s)
3919 solver_addjobrule(solv, installed && pool->solvables[p].repo == installed ? p : -p, 0, i, weak);
3921 FOR_JOB_SELECT(p, pp, select, what)
3922 solver_addjobrule(solv, installed && pool->solvables[p].repo == installed ? p : -p, 0, i, weak);
3924 case SOLVER_DISTUPGRADE:
3925 POOL_DEBUG(SOLV_DEBUG_JOB, "job: distupgrade %s\n", solver_select2str(pool, select, what));
3927 case SOLVER_DROP_ORPHANED:
3928 POOL_DEBUG(SOLV_DEBUG_JOB, "job: drop orphaned %s\n", solver_select2str(pool, select, what));
3930 case SOLVER_USERINSTALLED:
3931 POOL_DEBUG(SOLV_DEBUG_JOB, "job: user installed %s\n", solver_select2str(pool, select, what));
3934 POOL_DEBUG(SOLV_DEBUG_JOB, "job: unknown job\n");
3938 IF_POOLDEBUG (SOLV_DEBUG_JOB)
3941 if (solv->nrules == oldnrules)
3942 POOL_DEBUG(SOLV_DEBUG_JOB, " - no rule created\n");
3943 for (j = oldnrules; j < solv->nrules; j++)
3945 POOL_DEBUG(SOLV_DEBUG_JOB, " - job ");
3946 solver_printrule(solv, SOLV_DEBUG_JOB, solv->rules + j);
3950 assert(solv->ruletojob.count == solv->nrules - solv->jobrules);
3951 solv->jobrules_end = solv->nrules;
3953 /* now create infarch and dup rules */
3954 if (!solv->noinfarchcheck)
3956 solver_addinfarchrules(solv, &addedmap);
3958 if (pool->implicitobsoleteusescolors)
3960 /* currently doesn't work well with infarch rules, so make
3962 for (i = solv->infarchrules; i < solv->infarchrules_end; i++)
3963 queue_push(&solv->weakruleq, i);
3968 solv->infarchrules = solv->infarchrules_end = solv->nrules;
3971 solver_addduprules(solv, &addedmap);
3973 solv->duprules = solv->duprules_end = solv->nrules;
3975 if (solv->bestupdatemap_all || solv->bestupdatemap.size || hasbestinstalljob)
3976 solver_addbestrules(solv, hasbestinstalljob);
3978 solv->bestrules = solv->bestrules_end = solv->nrules;
3981 solver_freedupmaps(solv); /* no longer needed */
3983 if (solv->do_yum_obsoletes)
3984 solver_addyumobsrules(solv);
3986 solv->yumobsrules = solv->yumobsrules_end = solv->nrules;
3989 solver_addchoicerules(solv);
3991 solv->choicerules = solv->choicerules_end = solv->nrules;
3995 for (i = solv->featurerules; i < solv->nrules; i++)
3996 solver_printruleclass(solv, SOLV_DEBUG_RESULT, solv->rules + i);
3998 /* all rules created
3999 * --------------------------------------------------------------
4000 * prepare for solving
4003 /* free unneeded memory */
4004 map_free(&addedmap);
4005 map_free(&installcandidatemap);
4008 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);
4009 POOL_DEBUG(SOLV_DEBUG_STATS, "overall rule memory used: %d K\n", solv->nrules * (int)sizeof(Rule) / 1024);
4011 /* create weak map */
4012 map_init(&solv->weakrulemap, solv->nrules);
4013 for (i = 0; i < solv->weakruleq.count; i++)
4015 p = solv->weakruleq.elements[i];
4016 MAPSET(&solv->weakrulemap, p);
4019 /* enable cleandepsmap creation if we have updatepkgs */
4020 if (solv->cleandeps_updatepkgs && !solv->cleandepsmap.size)
4021 map_grow(&solv->cleandepsmap, installed->end - installed->start);
4023 if (solv->cleandeps_mistakes)
4025 queue_free(solv->cleandeps_mistakes);
4026 solv->cleandeps_mistakes = solv_free(solv->cleandeps_mistakes);
4029 /* all new rules are learnt after this point */
4030 solv->learntrules = solv->nrules;
4032 /* create watches chains */
4035 /* create assertion index. it is only used to speed up
4036 * makeruledecsions() a bit */
4037 for (i = 1, r = solv->rules + i; i < solv->nrules; i++, r++)
4038 if (r->p && !r->w2 && (r->d == 0 || r->d == -1))
4039 queue_push(&solv->ruleassertions, i);
4041 /* disable update rules that conflict with our job */
4042 solver_disablepolicyrules(solv);
4044 /* break orphans if requested */
4045 if (solv->dupmap_all && solv->orphaned.count && solv->break_orphans)
4046 solver_breakorphans(solv);
4048 /* make initial decisions based on assertion rules */
4049 makeruledecisions(solv);
4050 POOL_DEBUG(SOLV_DEBUG_SOLVER, "problems so far: %d\n", solv->problems.count);
4053 * ********************************************
4055 * ********************************************
4058 now = solv_timems(0);
4059 solver_run_sat(solv, 1, solv->dontinstallrecommended ? 0 : 1);
4060 POOL_DEBUG(SOLV_DEBUG_STATS, "solver took %d ms\n", solv_timems(now));
4063 * prepare solution queue if there were problems
4065 solver_prepare_solutions(solv);
4067 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);
4068 POOL_DEBUG(SOLV_DEBUG_STATS, "solver_solve took %d ms\n", solv_timems(solve_start));
4070 /* return number of problems */
4071 return solv->problems.count ? solv->problems.count / 2 : 0;
4075 solver_create_transaction(Solver *solv)
4077 return transaction_create_decisionq(solv->pool, &solv->decisionq, &solv->multiversion);
4080 void solver_get_orphaned(Solver *solv, Queue *orphanedq)
4082 queue_free(orphanedq);
4083 queue_init_clone(orphanedq, &solv->orphaned);
4086 void solver_get_recommendations(Solver *solv, Queue *recommendationsq, Queue *suggestionsq, int noselected)
4088 Pool *pool = solv->pool;
4089 Queue redoq, disabledq;
4095 if (!recommendationsq && !suggestionsq)
4098 map_init(&obsmap, pool->nsolvables);
4099 if (solv->installed)
4101 Id obs, *obsp, p, po, ppo;
4102 for (p = solv->installed->start; p < solv->installed->end; p++)
4104 s = pool->solvables + p;
4105 if (s->repo != solv->installed || !s->obsoletes)
4107 if (solv->decisionmap[p] <= 0)
4109 if (solv->multiversion.size && MAPTST(&solv->multiversion, p))
4111 obsp = s->repo->idarraydata + s->obsoletes;
4112 /* foreach obsoletes */
4113 while ((obs = *obsp++) != 0)
4114 FOR_PROVIDES(po, ppo, obs)
4115 MAPSET(&obsmap, po);
4120 queue_init(&disabledq);
4122 /* disable all erase jobs (including weak "keep uninstalled" rules) */
4123 for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++)
4125 if (r->d < 0) /* disabled ? */
4127 if (r->p >= 0) /* install job? */
4129 queue_push(&disabledq, i);
4130 solver_disablerule(solv, r);
4136 enabledisablelearntrules(solv);
4137 removedisabledconflicts(solv, &redoq);
4141 * find recommended packages
4143 if (recommendationsq)
4145 Id rec, *recp, p, pp;
4147 queue_empty(recommendationsq);
4148 /* create map of all recommened packages */
4149 solv->recommends_index = -1;
4150 MAPZERO(&solv->recommendsmap);
4152 /* put all packages the solver already chose in the map */
4153 if (solv->decisioncnt_weak)
4155 for (i = solv->decisioncnt_weak; i < solv->decisioncnt_orphan; i++)
4158 why = solv->decisionq_why.elements[i];
4160 continue; /* forced by unit rule or dep resolving */
4161 p = solv->decisionq.elements[i];
4164 MAPSET(&solv->recommendsmap, p);
4168 for (i = 0; i < solv->decisionq.count; i++)
4170 p = solv->decisionq.elements[i];
4173 s = pool->solvables + p;
4176 recp = s->repo->idarraydata + s->recommends;
4177 while ((rec = *recp++) != 0)
4179 #ifdef ENABLE_COMPLEX_DEPS
4180 if (pool_is_complex_dep(pool, rec))
4182 do_complex_recommendations(solv, rec, &solv->recommendsmap, noselected);
4186 FOR_PROVIDES(p, pp, rec)
4187 if (solv->decisionmap[p] > 0)
4193 FOR_PROVIDES(p, pp, rec)
4194 if (solv->decisionmap[p] > 0)
4195 MAPSET(&solv->recommendsmap, p);
4197 continue; /* p != 0: already fulfilled */
4199 FOR_PROVIDES(p, pp, rec)
4200 MAPSET(&solv->recommendsmap, p);
4204 for (i = 1; i < pool->nsolvables; i++)
4206 if (solv->decisionmap[i] < 0)
4208 if (solv->decisionmap[i] > 0 && noselected)
4210 if (MAPTST(&obsmap, i))
4212 s = pool->solvables + i;
4213 if (!MAPTST(&solv->recommendsmap, i))
4215 if (!s->supplements)
4217 if (!pool_installable(pool, s))
4219 if (!solver_is_supplementing(solv, s))
4222 queue_push(recommendationsq, i);
4224 /* we use MODE_SUGGEST here so that repo prio is ignored */
4225 policy_filter_unwanted(solv, recommendationsq, POLICY_MODE_SUGGEST);
4229 * find suggested packages
4234 Id sug, *sugp, p, pp;
4236 queue_empty(suggestionsq);
4237 /* create map of all suggests that are still open */
4238 solv->recommends_index = -1;
4239 MAPZERO(&solv->suggestsmap);
4240 for (i = 0; i < solv->decisionq.count; i++)
4242 p = solv->decisionq.elements[i];
4245 s = pool->solvables + p;
4248 sugp = s->repo->idarraydata + s->suggests;
4249 while ((sug = *sugp++) != 0)
4251 #ifdef ENABLE_COMPLEX_DEPS
4252 if (pool_is_complex_dep(pool, sug))
4254 do_complex_recommendations(solv, sug, &solv->suggestsmap, noselected);
4258 FOR_PROVIDES(p, pp, sug)
4259 if (solv->decisionmap[p] > 0)
4265 FOR_PROVIDES(p, pp, sug)
4266 if (solv->decisionmap[p] > 0)
4267 MAPSET(&solv->suggestsmap, p);
4269 continue; /* already fulfilled */
4271 FOR_PROVIDES(p, pp, sug)
4272 MAPSET(&solv->suggestsmap, p);
4276 for (i = 1; i < pool->nsolvables; i++)
4278 if (solv->decisionmap[i] < 0)
4280 if (solv->decisionmap[i] > 0 && noselected)
4282 if (MAPTST(&obsmap, i))
4284 s = pool->solvables + i;
4285 if (!MAPTST(&solv->suggestsmap, i))
4289 if (!pool_installable(pool, s))
4291 if (!solver_is_enhancing(solv, s))
4294 queue_push(suggestionsq, i);
4296 policy_filter_unwanted(solv, suggestionsq, POLICY_MODE_SUGGEST);
4299 /* undo removedisabledconflicts */
4301 undo_removedisabledconflicts(solv, &redoq);
4304 /* undo job rule disabling */
4305 for (i = 0; i < disabledq.count; i++)
4306 solver_enablerule(solv, solv->rules + disabledq.elements[i]);
4307 queue_free(&disabledq);
4312 /***********************************************************************/
4313 /* disk usage computations */
4315 /*-------------------------------------------------------------------
4317 * calculate DU changes
4321 solver_calc_duchanges(Solver *solv, DUChanges *mps, int nmps)
4325 solver_create_state_maps(solv, &installedmap, 0);
4326 pool_calc_duchanges(solv->pool, &installedmap, mps, nmps);
4327 map_free(&installedmap);
4331 /*-------------------------------------------------------------------
4333 * calculate changes in install size
4337 solver_calc_installsizechange(Solver *solv)
4342 solver_create_state_maps(solv, &installedmap, 0);
4343 change = pool_calc_installsizechange(solv->pool, &installedmap);
4344 map_free(&installedmap);
4349 solver_create_state_maps(Solver *solv, Map *installedmap, Map *conflictsmap)
4351 pool_create_state_maps(solv->pool, &solv->decisionq, installedmap, conflictsmap);
4355 solver_trivial_installable(Solver *solv, Queue *pkgs, Queue *res)
4357 Pool *pool = solv->pool;
4360 pool_create_state_maps(pool, &solv->decisionq, &installedmap, 0);
4361 pool_trivial_installable_multiversionmap(pool, &installedmap, pkgs, res, solv->multiversion.size ? &solv->multiversion : 0);
4362 for (i = 0; i < res->count; i++)
4363 if (res->elements[i] != -1)
4365 Solvable *s = pool->solvables + pkgs->elements[i];
4366 if (!strncmp("patch:", pool_id2str(pool, s->name), 6) && solvable_is_irrelevant_patch(s, &installedmap))
4367 res->elements[i] = -1;
4369 map_free(&installedmap);
4372 /*-------------------------------------------------------------------
4374 * decision introspection
4378 solver_get_decisionlevel(Solver *solv, Id p)
4380 return solv->decisionmap[p];
4384 solver_get_decisionqueue(Solver *solv, Queue *decisionq)
4386 queue_free(decisionq);
4387 queue_init_clone(decisionq, &solv->decisionq);
4391 solver_get_lastdecisionblocklevel(Solver *solv)
4394 if (solv->decisionq.count == 0)
4396 p = solv->decisionq.elements[solv->decisionq.count - 1];
4399 return solv->decisionmap[p] < 0 ? -solv->decisionmap[p] : solv->decisionmap[p];
4403 solver_get_decisionblock(Solver *solv, int level, Queue *decisionq)
4408 queue_empty(decisionq);
4409 for (i = 0; i < solv->decisionq.count; i++)
4411 p = solv->decisionq.elements[i];
4414 if (solv->decisionmap[p] == level || solv->decisionmap[p] == -level)
4417 if (i == solv->decisionq.count)
4419 for (i = 0; i < solv->decisionq.count; i++)
4421 p = solv->decisionq.elements[i];
4424 if (solv->decisionmap[p] == level || solv->decisionmap[p] == -level)
4425 queue_push(decisionq, p);
4432 solver_describe_decision(Solver *solv, Id p, Id *infop)
4439 if (!solv->decisionmap[p])
4440 return SOLVER_REASON_UNRELATED;
4441 pp = solv->decisionmap[p] < 0 ? -p : p;
4442 for (i = 0; i < solv->decisionq.count; i++)
4443 if (solv->decisionq.elements[i] == pp)
4445 if (i == solv->decisionq.count) /* just in case... */
4446 return SOLVER_REASON_UNRELATED;
4447 why = solv->decisionq_why.elements[i];
4449 *infop = why > 0 ? why : -why;
4451 return SOLVER_REASON_UNIT_RULE;
4454 return SOLVER_REASON_KEEP_INSTALLED; /* the systemsolvable */
4455 if (i < solv->decisioncnt_update)
4456 return SOLVER_REASON_RESOLVE_JOB;
4457 if (i < solv->decisioncnt_keep)
4459 if (why == 0 && pp < 0)
4460 return SOLVER_REASON_CLEANDEPS_ERASE;
4461 return SOLVER_REASON_UPDATE_INSTALLED;
4463 if (i < solv->decisioncnt_resolve)
4465 if (solv->focus_installed && i >= solv->decisioncnt_jobs)
4466 return SOLVER_REASON_RESOLVE_JOB;
4467 if (why == 0 && pp < 0)
4468 return SOLVER_REASON_CLEANDEPS_ERASE;
4469 return SOLVER_REASON_KEEP_INSTALLED;
4472 return SOLVER_REASON_RESOLVE;
4473 /* weak or orphaned */
4474 if (i < solv->decisioncnt_orphan)
4475 return SOLVER_REASON_WEAKDEP;
4476 return SOLVER_REASON_RESOLVE_ORPHAN;
4481 solver_describe_weakdep_decision(Solver *solv, Id p, Queue *whyq)
4483 Pool *pool = solv->pool;
4485 int level = solv->decisionmap[p];
4492 for (decisionno = 0; decisionno < solv->decisionq.count; decisionno++)
4493 if (solv->decisionq.elements[decisionno] == p)
4495 if (decisionno == solv->decisionq.count)
4497 if (decisionno < solv->decisioncnt_weak || decisionno >= solv->decisioncnt_orphan)
4500 /* 1) list all packages that recommend us */
4501 for (i = 1; i < pool->nsolvables; i++)
4503 Id *recp, rec, pp2, p2;
4504 if (solv->decisionmap[i] < 0 || solv->decisionmap[i] >= level)
4506 s = pool->solvables + i;
4509 if (!solv->addalreadyrecommended && s->repo == solv->installed)
4511 recp = s->repo->idarraydata + s->recommends;
4512 while ((rec = *recp++) != 0)
4515 FOR_PROVIDES(p2, pp2, rec)
4521 /* if p2 is already installed, this recommends is ignored */
4522 if (solv->decisionmap[p2] > 0 && solv->decisionmap[p2] < level)
4528 queue_push(whyq, SOLVER_REASON_RECOMMENDED);
4529 queue_push2(whyq, i, rec);
4533 /* 2) list all supplements */
4534 s = pool->solvables + p;
4535 if (s->supplements && level > 0)
4537 Id *supp, sup, pp2, p2;
4538 /* this is a hack. to use solver_dep_fulfilled we temporarily clear
4539 * everything above our level in the decisionmap */
4540 for (i = decisionno; i < solv->decisionq.count; i++ )
4542 p2 = solv->decisionq.elements[i];
4544 solv->decisionmap[p2] = -solv->decisionmap[p2];
4546 supp = s->repo->idarraydata + s->supplements;
4547 while ((sup = *supp++) != 0)
4548 if (solver_dep_fulfilled(solv, sup))
4551 /* let's see if this is an easy supp */
4552 FOR_PROVIDES(p2, pp2, sup)
4554 if (!solv->addalreadyrecommended && solv->installed)
4556 if (pool->solvables[p2].repo == solv->installed)
4559 if (solv->decisionmap[p2] > 0 && solv->decisionmap[p2] < level)
4561 queue_push(whyq, SOLVER_REASON_SUPPLEMENTED);
4562 queue_push2(whyq, p2, sup);
4568 /* hard case, just note dependency with no package */
4569 queue_push(whyq, SOLVER_REASON_SUPPLEMENTED);
4570 queue_push2(whyq, 0, sup);
4573 for (i = decisionno; i < solv->decisionq.count; i++)
4575 p2 = solv->decisionq.elements[i];
4577 solv->decisionmap[p2] = -solv->decisionmap[p2];
4583 pool_job2solvables(Pool *pool, Queue *pkgs, Id how, Id what)
4586 how &= SOLVER_SELECTMASK;
4588 if (how == SOLVER_SOLVABLE_ALL)
4590 FOR_POOL_SOLVABLES(p)
4591 queue_push(pkgs, p);
4593 else if (how == SOLVER_SOLVABLE_REPO)
4595 Repo *repo = pool_id2repo(pool, what);
4598 FOR_REPO_SOLVABLES(repo, p, s)
4599 queue_push(pkgs, p);
4603 FOR_JOB_SELECT(p, pp, how, what)
4604 queue_push(pkgs, p);
4609 pool_isemptyupdatejob(Pool *pool, Id how, Id what)
4612 Id select = how & SOLVER_SELECTMASK;
4613 if ((how & SOLVER_JOBMASK) != SOLVER_UPDATE)
4615 if (select == SOLVER_SOLVABLE_ALL || select == SOLVER_SOLVABLE_REPO)
4617 if (!pool->installed)
4619 FOR_JOB_SELECT(p, pp, select, what)
4620 if (pool->solvables[p].repo == pool->installed)
4623 FOR_JOB_SELECT(p, pp, select, what)
4625 Solvable *s = pool->solvables + p;
4626 FOR_PROVIDES(pi, pip, s->name)
4628 Solvable *si = pool->solvables + pi;
4629 if (si->repo != pool->installed || si->name != s->name)
4635 Id obs, *obsp = s->repo->idarraydata + s->obsoletes;
4636 while ((obs = *obsp++) != 0)
4638 FOR_PROVIDES(pi, pip, obs)
4640 Solvable *si = pool->solvables + pi;
4641 if (si->repo != pool->installed)
4643 if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, si, obs))
4645 if (pool->obsoleteusescolors && !pool_colormatch(pool, s, si))
4656 get_userinstalled_cmp(const void *ap, const void *bp, void *dp)
4658 return *(Id *)ap - *(Id *)bp;
4662 get_userinstalled_cmp_names(const void *ap, const void *bp, void *dp)
4665 return strcmp(pool_id2str(pool, *(Id *)ap), pool_id2str(pool, *(Id *)bp));
4669 get_userinstalled_sort_uniq(Pool *pool, Queue *q, int flags)
4673 if ((flags & GET_USERINSTALLED_NAMES) != 0)
4674 solv_sort(q->elements, q->count, sizeof(Id), get_userinstalled_cmp_names, pool);
4676 solv_sort(q->elements, q->count, sizeof(Id), get_userinstalled_cmp, 0);
4677 for (i = j = 0; i < q->count; i++)
4678 if (q->elements[i] != lastp)
4679 q->elements[j++] = lastp = q->elements[i];
4680 queue_truncate(q, j);
4684 solver_get_userinstalled(Solver *solv, Queue *q, int flags)
4686 Pool *pool = solv->pool;
4689 Repo *installed = solv->installed;
4693 map_init(&userinstalled, 0);
4695 /* first process jobs */
4696 for (i = 0; i < solv->job.count; i += 2)
4698 Id how = solv->job.elements[i];
4700 if (installed && (how & SOLVER_JOBMASK) == SOLVER_USERINSTALLED)
4702 if (!userinstalled.size)
4703 map_grow(&userinstalled, installed->end - installed->start);
4704 what = solv->job.elements[i + 1];
4705 select = how & SOLVER_SELECTMASK;
4706 if (select == SOLVER_SOLVABLE_ALL || (select == SOLVER_SOLVABLE_REPO && what == installed->repoid))
4707 FOR_REPO_SOLVABLES(installed, p, s)
4708 MAPSET(&userinstalled, p - installed->start);
4709 FOR_JOB_SELECT(p, pp, select, what)
4710 if (pool->solvables[p].repo == installed)
4711 MAPSET(&userinstalled, p - installed->start);
4714 if ((how & SOLVER_JOBMASK) != SOLVER_INSTALL)
4716 if ((how & SOLVER_NOTBYUSER) != 0)
4718 what = solv->job.elements[i + 1];
4719 select = how & SOLVER_SELECTMASK;
4720 FOR_JOB_SELECT(p, pp, select, what)
4721 if (solv->decisionmap[p] > 0)
4724 #ifdef ENABLE_LINKED_PKGS
4725 if (has_package_link(pool, pool->solvables + p))
4730 find_package_link(pool, pool->solvables + p, 0, &lq, 0, 0);
4731 for (j = 0; j < lq.count; j++)
4732 if (solv->decisionmap[lq.elements[j]] > 0)
4733 queue_push(q, lq.elements[j]);
4738 /* now process updates of userinstalled packages */
4739 if (installed && userinstalled.size)
4741 for (i = 1; i < solv->decisionq.count; i++)
4743 p = solv->decisionq.elements[i];
4746 s = pool->solvables + p;
4749 if (s->repo == installed)
4751 if (MAPTST(&userinstalled, p - installed->start))
4755 /* new package, check if we replace a userinstalled one */
4756 FOR_PROVIDES(p2, pp, s->name)
4758 Solvable *ps = pool->solvables + p2;
4759 if (p2 == p || ps->repo != installed || !MAPTST(&userinstalled, p2 - installed->start))
4761 if (!pool->implicitobsoleteusesprovides && s->name != ps->name)
4763 if (pool->implicitobsoleteusescolors && !pool_colormatch(pool, s, ps))
4768 if (!p2 && s->repo != installed && s->obsoletes)
4770 Id obs, *obsp = s->repo->idarraydata + s->obsoletes;
4771 while ((obs = *obsp++) != 0)
4773 FOR_PROVIDES(p2, pp, obs)
4775 Solvable *ps = pool->solvables + p2;
4776 if (p2 == p || ps->repo != installed || !MAPTST(&userinstalled, p2 - installed->start))
4778 if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
4780 if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
4791 map_free(&userinstalled);
4792 /* convert to names if asked */
4793 if ((flags & GET_USERINSTALLED_NAMES) != 0)
4795 for (i = 0; i < q->count; i++)
4797 s = pool->solvables + q->elements[i];
4798 q->elements[i] = s->name;
4801 /* sort and unify */
4803 get_userinstalled_sort_uniq(pool, q, flags);
4804 /* invert if asked */
4805 if ((flags & GET_USERINSTALLED_INVERTED) != 0)
4807 /* first generate queue with all installed packages */
4810 for (i = 1; i < solv->decisionq.count; i++)
4812 p = solv->decisionq.elements[i];
4815 s = pool->solvables + p;
4818 if ((flags & GET_USERINSTALLED_NAMES) != 0)
4819 queue_push(&invq, s->name);
4821 queue_push(&invq, p);
4823 /* push q on invq, just in case... */
4824 queue_insertn(&invq, invq.count, q->count, q->elements);
4826 get_userinstalled_sort_uniq(pool, &invq, flags);
4827 /* subtract queues (easy as they are sorted and invq is a superset of q) */
4830 for (i = j = 0; i < invq.count; i++)
4831 if (invq.elements[i] == q->elements[j])
4833 invq.elements[i] = 0;
4834 if (++j >= q->count)
4839 for (i = j = 0; i < invq.count; i++)
4840 if (invq.elements[i])
4841 queue_push(q, invq.elements[i]);
4847 pool_add_userinstalled_jobs(Pool *pool, Queue *q, Queue *job, int flags)
4851 if (flags & GET_USERINSTALLED_INVERTED)
4857 if (!pool->installed)
4860 FOR_REPO_SOLVABLES(pool->installed, p, s)
4861 queue_push(&invq, flags & GET_USERINSTALLED_NAMES ? s->name : p);
4862 queue_insertn(&invq, invq.count, q->count, q->elements);
4864 get_userinstalled_sort_uniq(pool, &invq, flags);
4865 /* now the fun part, add q again, sort, and remove all dups */
4866 queue_insertn(&invq, invq.count, q->count, q->elements);
4869 if ((flags & GET_USERINSTALLED_NAMES) != 0)
4870 solv_sort(invq.elements, invq.count, sizeof(Id), get_userinstalled_cmp_names, pool);
4872 solv_sort(invq.elements, invq.count, sizeof(Id), get_userinstalled_cmp, 0);
4876 for (i = 0; i < invq.count; i++)
4878 if (invq.elements[i] == lastid)
4884 queue_push2(job, SOLVER_USERINSTALLED | (flags & GET_USERINSTALLED_NAMES ? SOLVER_SOLVABLE_NAME : SOLVER_SOLVABLE), lastid);
4886 lastid = invq.elements[i];
4889 queue_push2(job, SOLVER_USERINSTALLED | (flags & GET_USERINSTALLED_NAMES ? SOLVER_SOLVABLE_NAME : SOLVER_SOLVABLE), lastid);
4894 for (i = 0; i < q->count; i++)
4895 queue_push2(job, SOLVER_USERINSTALLED | (flags & GET_USERINSTALLED_NAMES ? SOLVER_SOLVABLE_NAME : SOLVER_SOLVABLE), q->elements[i]);
4900 solver_alternatives_count(Solver *solv)
4902 Id *elements = solv->branches.elements;
4904 for (res = 0, count = solv->branches.count; count; res++)
4905 count -= elements[count - 2];
4910 solver_get_alternative(Solver *solv, Id alternative, Id *idp, Id *fromp, Id *chosenp, Queue *choices, int *levelp)
4912 int cnt = solver_alternatives_count(solv);
4913 int count = solv->branches.count;
4914 Id *elements = solv->branches.elements;
4916 queue_empty(choices);
4917 if (alternative <= 0 || alternative > cnt)
4920 for (; cnt > alternative; cnt--)
4921 elements -= elements[-2];
4923 *levelp = elements[-1];
4925 *fromp = elements[-4];
4927 *idp = elements[-3];
4932 for (i = elements[-2]; i > 4; i--)
4934 Id p = -elements[-i];
4935 if (p > 0 && solv->decisionmap[p] == elements[-1] + 1)
4943 queue_insertn(choices, 0, elements[-2] - 4, elements - elements[-2]);
4944 return elements[-4] ? SOLVER_ALTERNATIVE_TYPE_RECOMMENDS : SOLVER_ALTERNATIVE_TYPE_RULE;
4948 solver_select2str(Pool *pool, Id select, Id what)
4952 select &= SOLVER_SELECTMASK;
4953 if (select == SOLVER_SOLVABLE)
4954 return pool_solvid2str(pool, what);
4955 if (select == SOLVER_SOLVABLE_NAME)
4956 return pool_dep2str(pool, what);
4957 if (select == SOLVER_SOLVABLE_PROVIDES)
4959 s = pool_dep2str(pool, what);
4960 b = pool_alloctmpspace(pool, 11 + strlen(s));
4961 sprintf(b, "providing %s", s);
4964 if (select == SOLVER_SOLVABLE_ONE_OF)
4968 while ((p = pool->whatprovidesdata[what++]) != 0)
4970 s = pool_solvid2str(pool, p);
4972 b = pool_tmpappend(pool, b, ", ", s);
4974 b = pool_tmpjoin(pool, s, 0, 0);
4975 pool_freetmpspace(pool, s);
4977 return b ? b : "nothing";
4979 if (select == SOLVER_SOLVABLE_REPO)
4981 b = pool_alloctmpspace(pool, 20);
4982 sprintf(b, "repo #%d", what);
4985 if (select == SOLVER_SOLVABLE_ALL)
4986 return "all packages";
4987 return "unknown job select";
4991 pool_job2str(Pool *pool, Id how, Id what, Id flagmask)
4993 Id select = how & SOLVER_SELECTMASK;
4994 const char *strstart = 0, *strend = 0;
4998 switch (how & SOLVER_JOBMASK)
5001 return "do nothing";
5002 case SOLVER_INSTALL:
5003 if (select == SOLVER_SOLVABLE && pool->installed && pool->solvables[what].repo == pool->installed)
5004 strstart = "keep ", strend = " installed";
5005 else if (select == SOLVER_SOLVABLE || select == SOLVER_SOLVABLE_NAME)
5006 strstart = "install ";
5007 else if (select == SOLVER_SOLVABLE_PROVIDES)
5008 strstart = "install a package ";
5010 strstart = "install one of ";
5013 if (select == SOLVER_SOLVABLE && !(pool->installed && pool->solvables[what].repo == pool->installed))
5014 strstart = "keep ", strend = " uninstalled";
5015 else if (select == SOLVER_SOLVABLE_PROVIDES)
5016 strstart = "deinstall all packages ";
5018 strstart = "deinstall ";
5021 strstart = "update ";
5023 case SOLVER_WEAKENDEPS:
5024 strstart = "weaken deps of ";
5026 case SOLVER_MULTIVERSION:
5027 strstart = "multi version ";
5032 case SOLVER_DISTUPGRADE:
5033 strstart = "dist upgrade ";
5036 strstart = "verify ";
5038 case SOLVER_DROP_ORPHANED:
5039 strstart = "deinstall ", strend = " if orphaned";
5041 case SOLVER_USERINSTALLED:
5042 strstart = "regard ", strend = " as userinstalled";
5045 strstart = "unknown job ";
5048 s = pool_tmpjoin(pool, strstart, solver_select2str(pool, select, what), strend);
5050 if ((how & ~(SOLVER_SELECTMASK|SOLVER_JOBMASK)) == 0)
5053 s = pool_tmpappend(pool, s, " ", 0);
5054 if (how & SOLVER_WEAK)
5055 s = pool_tmpappend(pool, s, ",weak", 0);
5056 if (how & SOLVER_ESSENTIAL)
5057 s = pool_tmpappend(pool, s, ",essential", 0);
5058 if (how & SOLVER_CLEANDEPS)
5059 s = pool_tmpappend(pool, s, ",cleandeps", 0);
5060 if (how & SOLVER_ORUPDATE)
5061 s = pool_tmpappend(pool, s, ",orupdate", 0);
5062 if (how & SOLVER_FORCEBEST)
5063 s = pool_tmpappend(pool, s, ",forcebest", 0);
5064 if (how & SOLVER_TARGETED)
5065 s = pool_tmpappend(pool, s, ",targeted", 0);
5066 if (how & SOLVER_SETEV)
5067 s = pool_tmpappend(pool, s, ",setev", 0);
5068 if (how & SOLVER_SETEVR)
5069 s = pool_tmpappend(pool, s, ",setevr", 0);
5070 if (how & SOLVER_SETARCH)
5071 s = pool_tmpappend(pool, s, ",setarch", 0);
5072 if (how & SOLVER_SETVENDOR)
5073 s = pool_tmpappend(pool, s, ",setvendor", 0);
5074 if (how & SOLVER_SETREPO)
5075 s = pool_tmpappend(pool, s, ",setrepo", 0);
5076 if (how & SOLVER_SETNAME)
5077 s = pool_tmpappend(pool, s, ",setname", 0);
5078 if (how & SOLVER_NOAUTOSET)
5079 s = pool_tmpappend(pool, s, ",noautoset", 0);
5080 if (s[o + 1] != ',')
5081 s = pool_tmpappend(pool, s, ",?", 0);
5083 return pool_tmpappend(pool, s, "]", 0);
5087 solver_alternative2str(Solver *solv, int type, Id id, Id from)
5089 Pool *pool = solv->pool;
5090 if (type == SOLVER_ALTERNATIVE_TYPE_RECOMMENDS)
5092 const char *s = pool_dep2str(pool, id);
5093 return pool_tmpappend(pool, s, ", recommended by ", pool_solvid2str(pool, from));
5095 if (type == SOLVER_ALTERNATIVE_TYPE_RULE)
5098 Id depfrom, depto, dep;
5100 if (solver_ruleclass(solv, id) == SOLVER_RULE_CHOICE)
5101 id = solver_rule2pkgrule(solv, id);
5102 rtype = solver_ruleinfo(solv, id, &depfrom, &depto, &dep);
5103 if ((rtype & SOLVER_RULE_TYPEMASK) == SOLVER_RULE_JOB)
5105 if ((depto & SOLVER_SELECTMASK) == SOLVER_SOLVABLE_PROVIDES)
5106 return pool_dep2str(pool, dep);
5107 return solver_select2str(pool, depto & SOLVER_SELECTMASK, dep);
5109 if (rtype == SOLVER_RULE_PKG_REQUIRES)
5111 const char *s = pool_dep2str(pool, dep);
5112 return pool_tmpappend(pool, s, ", required by ", pool_solvid2str(pool, depfrom));
5114 sprintf(buf, "Rule #%d", id);
5115 return pool_tmpjoin(pool, buf, 0, 0);
5117 return "unknown alternative type";