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
35 autouninstall(Solver *solv, Id *problem)
37 Pool *pool = solv->pool;
39 int lastfeature = 0, lastupdate = 0;
44 if (!solv->allowuninstall && !solv->allowuninstall_all)
46 if (!solv->allowuninstallmap.size)
47 return 0; /* why did we get called? */
48 m = &solv->allowuninstallmap;
50 for (i = 0; (v = problem[i]) != 0; i++)
53 extraflags &= solv->job.elements[-v - 1];
54 if (v >= solv->updaterules && v < solv->updaterules_end)
57 if (m && !MAPTST(m, v - solv->updaterules))
59 /* check if identical to feature rule, we don't like that (except for orphans) */
60 r = solv->rules + solv->featurerules + (v - solv->updaterules);
63 /* update rule == feature rule */
66 /* prefer orphaned packages in dup mode */
67 if (solv->keep_orphans)
70 if (!r->d && !r->w2 && r->p == (solv->installed->start + (v - solv->updaterules)))
83 if (!lastupdate && !lastfeature)
85 v = lastupdate ? lastupdate : lastfeature;
86 POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "allowuninstall disabling ");
87 solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE, solv->rules + v);
88 solver_disableproblem(solv, v);
89 if (extraflags != -1 && (extraflags & SOLVER_CLEANDEPS) != 0 && solv->cleandepsmap.size)
91 /* add the package to the updatepkgs list, this will automatically turn
92 * on cleandeps mode */
93 Id p = solv->rules[v].p;
94 if (!solv->cleandeps_updatepkgs)
96 solv->cleandeps_updatepkgs = solv_calloc(1, sizeof(Queue));
97 queue_init(solv->cleandeps_updatepkgs);
101 int oldupdatepkgscnt = solv->cleandeps_updatepkgs->count;
102 queue_pushunique(solv->cleandeps_updatepkgs, p);
103 if (solv->cleandeps_updatepkgs->count != oldupdatepkgscnt)
104 solver_disablepolicyrules(solv);
110 /************************************************************************/
113 * enable/disable learnt rules
115 * we have enabled or disabled some of our rules. We now reenable all
116 * of our learnt rules except the ones that were learnt from rules that
120 enabledisablelearntrules(Solver *solv)
122 Pool *pool = solv->pool;
127 POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "enabledisablelearntrules called\n");
128 for (i = solv->learntrules, r = solv->rules + i; i < solv->nrules; i++, r++)
130 whyp = solv->learnt_pool.elements + solv->learnt_why.elements[i - solv->learntrules];
131 while ((why = *whyp++) != 0)
133 assert(why > 0 && why < i);
134 if (solv->rules[why].d < 0)
137 /* why != 0: we found a disabled rule, disable the learnt rule */
138 if (why && r->d >= 0)
140 IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS)
142 POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "disabling ");
143 solver_printruleclass(solv, SOLV_DEBUG_SOLUTIONS, r);
145 solver_disablerule(solv, r);
147 else if (!why && r->d < 0)
149 IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS)
151 POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "re-enabling ");
152 solver_printruleclass(solv, SOLV_DEBUG_SOLUTIONS, r);
154 solver_enablerule(solv, r);
161 * make assertion rules into decisions
163 * Go through rules and add direct assertions to the decisionqueue.
164 * If we find a conflict, disable rules and add them to problem queue.
168 makeruledecisions(Solver *solv)
170 Pool *pool = solv->pool;
175 int record_proof = 1;
177 int havedisabled = 0;
179 /* The system solvable is always installed first */
180 assert(solv->decisionq.count == 0);
181 queue_push(&solv->decisionq, SYSTEMSOLVABLE);
182 queue_push(&solv->decisionq_why, 0);
183 queue_push2(&solv->decisionq_reason, 0, 0);
184 solv->decisionmap[SYSTEMSOLVABLE] = 1; /* installed at level '1' */
186 decisionstart = solv->decisionq.count;
189 /* if we needed to re-run, back up decisions to decisionstart */
190 while (solv->decisionq.count > decisionstart)
192 v = solv->decisionq.elements[--solv->decisionq.count];
193 --solv->decisionq_why.count;
195 solv->decisionmap[vv] = 0;
198 /* note that the ruleassertions queue is ordered */
199 for (ii = 0; ii < solv->ruleassertions.count; ii++)
201 ri = solv->ruleassertions.elements[ii];
202 r = solv->rules + ri;
204 if (havedisabled && ri >= solv->learntrules)
206 /* just started with learnt rule assertions. If we have disabled
207 * some rules, adapt the learnt rule status */
208 enabledisablelearntrules(solv);
212 if (r->d < 0 || !r->p || r->w2) /* disabled, dummy or no assertion */
215 /* do weak rules in phase 2 */
216 if (ri < solv->learntrules && solv->weakrulemap.size && MAPTST(&solv->weakrulemap, ri))
222 if (!solv->decisionmap[vv]) /* if not yet decided */
224 queue_push(&solv->decisionq, v);
225 queue_push(&solv->decisionq_why, r - solv->rules);
226 solv->decisionmap[vv] = v > 0 ? 1 : -1;
227 IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
229 Solvable *s = solv->pool->solvables + vv;
231 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "conflicting %s (assertion)\n", pool_solvable2str(solv->pool, s));
233 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "installing %s (assertion)\n", pool_solvable2str(solv->pool, s));
238 /* check against previous decision: is there a conflict? */
239 if (v > 0 && solv->decisionmap[vv] > 0) /* ok to install */
241 if (v < 0 && solv->decisionmap[vv] < 0) /* ok to remove */
247 * The rule (r) we're currently processing says something
248 * different (v = r->p) than a previous decision (decisionmap[abs(v)])
252 if (ri >= solv->learntrules)
254 /* conflict with a learnt rule */
255 /* can happen when packages cannot be installed for multiple reasons. */
256 /* we disable the learnt rule in this case */
257 /* (XXX: we should really call analyze_unsolvable_rule here!) */
258 solver_disablerule(solv, r);
262 POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "ANALYZE UNSOLVABLE ASSERTION ----------------------\n");
263 IF_POOLDEBUG (SOLV_DEBUG_UNSOLVABLE)
264 solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE, solv->rules + ri);
267 * find the decision which is the "opposite" of the rule
269 for (i = 0; i < solv->decisionq.count; i++)
270 if (solv->decisionq.elements[i] == -v)
272 assert(i < solv->decisionq.count); /* assert that we found it */
273 oldproblemcount = solv->problems.count;
276 * conflict with system solvable ?
278 if (v == -SYSTEMSOLVABLE)
282 queue_push(&solv->problems, solv->learnt_pool.count);
283 queue_push(&solv->learnt_pool, ri);
284 queue_push(&solv->learnt_pool, 0);
287 queue_push(&solv->problems, 0);
288 POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "conflict with system solvable, disabling rule #%d\n", ri);
289 if (ri >= solv->jobrules && ri < solv->jobrules_end)
290 v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
293 queue_push(&solv->problems, v);
294 queue_push(&solv->problems, 0);
295 if (v >= solv->featurerules && v < solv->updaterules_end)
297 if (solv->allowuninstall || solv->allowuninstall_all || solv->allowuninstallmap.size)
298 if (autouninstall(solv, solv->problems.elements + oldproblemcount + 1) != 0)
300 solv->problems.count = oldproblemcount;
302 break; /* start over */
305 solver_disableproblem(solv, v);
307 break; /* start over */
310 assert(solv->decisionq_why.elements[i] > 0);
311 IF_POOLDEBUG (SOLV_DEBUG_UNSOLVABLE)
312 solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE, solv->rules + solv->decisionq_why.elements[i]);
315 * conflict with a pkg rule ?
317 if (solv->decisionq_why.elements[i] < solv->pkgrules_end)
321 queue_push(&solv->problems, solv->learnt_pool.count);
322 queue_push(&solv->learnt_pool, ri);
323 queue_push(&solv->learnt_pool, solv->decisionq_why.elements[i]);
324 queue_push(&solv->learnt_pool, 0);
327 queue_push(&solv->problems, 0);
328 assert(v > 0 || v == -SYSTEMSOLVABLE);
329 POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "conflict with pkg rule, disabling rule #%d\n", ri);
330 if (ri >= solv->jobrules && ri < solv->jobrules_end)
331 v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
334 queue_push(&solv->problems, v);
335 queue_push(&solv->problems, 0);
336 if (v >= solv->featurerules && v < solv->updaterules_end)
338 if (solv->allowuninstall || solv->allowuninstall_all || solv->allowuninstallmap.size)
339 if (autouninstall(solv, solv->problems.elements + oldproblemcount + 1) != 0)
341 solv->problems.count = oldproblemcount;
343 break; /* start over */
346 solver_disableproblem(solv, v);
348 break; /* start over */
352 * conflict with another job or update/feature rule
358 queue_push(&solv->problems, solv->learnt_pool.count);
359 queue_push(&solv->learnt_pool, ri);
360 queue_push(&solv->learnt_pool, solv->decisionq_why.elements[i]);
361 queue_push(&solv->learnt_pool, 0);
364 queue_push(&solv->problems, 0);
366 POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "conflicting update/job assertions over literal %d\n", vv);
369 * push all of our rules (can only be feature or job rules)
370 * asserting this literal on the problem stack
372 for (i = solv->featurerules, rr = solv->rules + i; i < solv->learntrules; i++, rr++)
374 if (rr->d < 0 /* disabled */
375 || rr->w2) /* or no assertion */
377 if (rr->p != vv /* not affecting the literal */
380 if (solv->weakrulemap.size && MAPTST(&solv->weakrulemap, i)) /* weak: silently ignore */
383 POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, " - disabling rule #%d\n", i);
384 solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE, solv->rules + i);
387 if (i >= solv->jobrules && i < solv->jobrules_end)
388 v = -(solv->ruletojob.elements[i - solv->jobrules] + 1);
389 queue_push(&solv->problems, v);
391 queue_push(&solv->problems, 0);
393 if (solv->allowuninstall || solv->allowuninstall_all || solv->allowuninstallmap.size)
394 if (autouninstall(solv, solv->problems.elements + oldproblemcount + 1) != 0)
396 solv->problems.count = oldproblemcount;
398 break; /* start over */
401 for (i = oldproblemcount + 1; i < solv->problems.count - 1; i++)
402 solver_disableproblem(solv, solv->problems.elements[i]);
404 break; /* start over */
406 if (ii < solv->ruleassertions.count)
410 * phase 2: now do the weak assertions
412 if (!solv->weakrulemap.size)
413 break; /* no weak rules, no phase 2 */
414 for (ii = 0; ii < solv->ruleassertions.count; ii++)
416 ri = solv->ruleassertions.elements[ii];
417 r = solv->rules + ri;
418 if (r->d < 0 || r->w2) /* disabled or no assertion */
420 if (ri >= solv->learntrules || !MAPTST(&solv->weakrulemap, ri)) /* skip non-weak */
425 if (!solv->decisionmap[vv]) /* if not yet decided */
427 queue_push(&solv->decisionq, v);
428 queue_push(&solv->decisionq_why, r - solv->rules);
429 solv->decisionmap[vv] = v > 0 ? 1 : -1;
430 IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
432 Solvable *s = solv->pool->solvables + vv;
434 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "conflicting %s (weak assertion)\n", pool_solvable2str(solv->pool, s));
436 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "installing %s (weak assertion)\n", pool_solvable2str(solv->pool, s));
440 /* check against previous decision: is there a conflict? */
441 if (v > 0 && solv->decisionmap[vv] > 0)
443 if (v < 0 && solv->decisionmap[vv] < 0)
446 POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "assertion conflict, but I am weak, disabling ");
447 solver_printrule(solv, SOLV_DEBUG_UNSOLVABLE, r);
449 if (ri >= solv->jobrules && ri < solv->jobrules_end)
450 v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
453 solver_disableproblem(solv, v);
455 solver_reenablepolicyrules(solv, -v);
457 break; /* start over */
459 if (ii == solv->ruleassertions.count)
460 break; /* finished! */
465 /********************************************************************/
469 /*-------------------------------------------------------------------
472 * initial setup for all watches
476 makewatches(Solver *solv)
480 int nsolvables = solv->pool->nsolvables;
482 solv_free(solv->watches);
483 /* lower half for removals, upper half for installs */
484 solv->watches = solv_calloc(2 * nsolvables, sizeof(Id));
485 for (i = 1, r = solv->rules + solv->nrules - 1; i < solv->nrules; i++, r--)
487 if (!r->w2) /* assertions do not need watches */
490 /* see addwatches_rule(solv, r) */
491 r->n1 = solv->watches[nsolvables + r->w1];
492 solv->watches[nsolvables + r->w1] = r - solv->rules;
494 r->n2 = solv->watches[nsolvables + r->w2];
495 solv->watches[nsolvables + r->w2] = r - solv->rules;
500 /*-------------------------------------------------------------------
502 * add watches (for a new learned rule)
503 * sets up watches for a single rule
505 * see also makewatches() above.
509 addwatches_rule(Solver *solv, Rule *r)
511 int nsolvables = solv->pool->nsolvables;
513 r->n1 = solv->watches[nsolvables + r->w1];
514 solv->watches[nsolvables + r->w1] = r - solv->rules;
516 r->n2 = solv->watches[nsolvables + r->w2];
517 solv->watches[nsolvables + r->w2] = r - solv->rules;
521 /********************************************************************/
527 /* shortcuts to check if a literal (positive or negative) assignment
528 * evaluates to 'true' or 'false'
530 #define DECISIONMAP_TRUE(p) ((p) > 0 ? (decisionmap[p] > 0) : (decisionmap[-p] < 0))
531 #define DECISIONMAP_FALSE(p) ((p) > 0 ? (decisionmap[p] < 0) : (decisionmap[-p] > 0))
532 #define DECISIONMAP_UNDEF(p) (decisionmap[(p) > 0 ? (p) : -(p)] == 0)
534 /*-------------------------------------------------------------------
538 * make decision and propagate to all rules
540 * Evaluate each term affected by the decision (linked through watches).
541 * If we find unit rules we make new decisions based on them.
543 * return : 0 = everything is OK
544 * rule = conflict found in this rule
548 propagate(Solver *solv, int level)
550 Pool *pool = solv->pool;
551 Id *rp, *next_rp; /* rule pointer, next rule pointer in linked list */
553 Id p, pkg, other_watch;
555 Id *decisionmap = solv->decisionmap;
556 Id *watches = solv->watches + pool->nsolvables; /* place ptr in middle */
558 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "----- propagate -----\n");
560 /* foreach non-propagated decision */
561 while (solv->propagate_index < solv->decisionq.count)
564 * 'pkg' was just decided
565 * negate because our watches trigger if literal goes FALSE
567 pkg = -solv->decisionq.elements[solv->propagate_index++];
569 IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
571 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "propagate for decision %d level %d\n", -pkg, level);
572 solver_printruleelement(solv, SOLV_DEBUG_PROPAGATE, 0, -pkg);
575 /* foreach rule where 'pkg' is now FALSE */
576 for (rp = watches + pkg; *rp; rp = next_rp)
578 r = solv->rules + *rp;
581 /* rule is disabled, goto next */
589 IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
591 POOL_DEBUG(SOLV_DEBUG_PROPAGATE," watch triggered ");
592 solver_printrule(solv, SOLV_DEBUG_PROPAGATE, r);
596 * 'pkg' was just decided (was set to FALSE), so this rule
599 /* find the other watch */
612 * if the other watch is true we have nothing to do
614 if (DECISIONMAP_TRUE(other_watch))
618 * The other literal is FALSE or UNDEF
624 /* Not a binary clause, try to move our watch.
626 * Go over all literals and find one that is
630 * (TRUE is also ok, in that case the rule is fulfilled)
631 * As speed matters here we do not use the FOR_RULELITERALS
634 if (r->p /* we have a 'p' */
635 && r->p != other_watch /* which is not watched */
636 && !DECISIONMAP_FALSE(r->p)) /* and not FALSE */
640 else /* go find a 'd' to make 'true' */
643 we just iterate sequentially, doing it in another order just changes the order of decisions, not the decisions itself
645 for (dp = pool->whatprovidesdata + r->d; (p = *dp++) != 0;)
647 if (p != other_watch /* which is not watched */
648 && !DECISIONMAP_FALSE(p)) /* and not FALSE */
656 * if we found some p that is UNDEF or TRUE, move
659 IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
662 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, " -> move w%d to %s\n", (pkg == r->w1 ? 1 : 2), pool_solvid2str(pool, p));
664 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, " -> move w%d to !%s\n", (pkg == r->w1 ? 1 : 2), pool_solvid2str(pool, -p));
680 watches[p] = r - solv->rules;
683 /* search failed, thus all unwatched literals are FALSE */
688 * unit clause found, set literal other_watch to TRUE
691 if (DECISIONMAP_FALSE(other_watch)) /* check if literal is FALSE */
692 return r; /* eek, a conflict! */
694 IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
696 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, " unit ");
697 solver_printrule(solv, SOLV_DEBUG_PROPAGATE, r);
701 decisionmap[other_watch] = level; /* install! */
703 decisionmap[-other_watch] = -level; /* remove! */
705 queue_push(&solv->decisionq, other_watch);
706 queue_push(&solv->decisionq_why, r - solv->rules);
708 IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
711 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, " -> decided to install %s\n", pool_solvid2str(pool, other_watch));
713 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, " -> decided to conflict %s\n", pool_solvid2str(pool, -other_watch));
716 } /* foreach rule involving 'pkg' */
718 } /* while we have non-decided decisions */
720 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "----- propagate end-----\n");
722 return 0; /* all is well */
726 /********************************************************************/
729 /*-------------------------------------------------------------------
732 * revert decisionq to a level
736 revert(Solver *solv, int level)
738 Pool *pool = solv->pool;
740 while (solv->decisionq.count)
742 v = solv->decisionq.elements[solv->decisionq.count - 1];
744 if (solv->decisionmap[vv] <= level && solv->decisionmap[vv] >= -level)
746 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "reverting decision %d at %d\n", v, solv->decisionmap[vv]);
747 solv->decisionmap[vv] = 0;
748 solv->decisionq.count--;
749 solv->decisionq_why.count--;
750 solv->propagate_index = solv->decisionq.count;
752 while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] >= level)
753 solv->branches.count -= solv->branches.elements[solv->branches.count - 2];
754 if (solv->recommends_index > solv->decisionq.count)
755 solv->recommends_index = -1; /* rebuild recommends/suggests maps */
756 solv->decisionq_reason.count = level + 1;
759 /*-------------------------------------------------------------------
761 * watch2onhighest - put watch2 on literal with highest level
765 watch2onhighest(Solver *solv, Rule *r)
770 d = r->d < 0 ? -r->d - 1 : r->d;
772 return; /* binary rule, both watches are set */
773 dp = solv->pool->whatprovidesdata + d;
774 while ((v = *dp++) != 0)
776 l = solv->decisionmap[v < 0 ? -v : v];
788 /*-------------------------------------------------------------------
795 analyze(Solver *solv, int level, Rule *c, Rule **lrp)
797 Pool *pool = solv->pool;
802 Map seen; /* global? */
803 Id p = 0, pp, v, vv, why;
805 int num = 0, l1num = 0;
806 int learnt_why = solv->learnt_pool.count;
807 Id *decisionmap = solv->decisionmap;
809 queue_init_buffer(&q, q_buf, sizeof(q_buf)/sizeof(*q_buf));
811 POOL_DEBUG(SOLV_DEBUG_ANALYZE, "ANALYZE at %d ----------------------\n", level);
812 map_init(&seen, pool->nsolvables);
813 idx = solv->decisionq.count;
816 IF_POOLDEBUG (SOLV_DEBUG_ANALYZE)
817 solver_printruleclass(solv, SOLV_DEBUG_ANALYZE, c);
818 queue_push(&solv->learnt_pool, c - solv->rules);
819 FOR_RULELITERALS(v, pp, c)
821 if (DECISIONMAP_TRUE(v)) /* the one true literal */
824 if (MAPTST(&seen, vv))
826 MAPSET(&seen, vv); /* mark that we also need to look at this literal */
827 l = solv->decisionmap[vv];
831 l1num++; /* need to do this one in level1 pass */
833 num++; /* need to do this one as well */
836 queue_push(&q, v); /* not level1 or conflict level, add to new rule */
842 if (!num && !--l1num)
843 break; /* all literals done */
845 /* find the next literal to investigate */
846 /* (as num + l1num > 0, we know that we'll always find one) */
850 v = solv->decisionq.elements[--idx];
852 if (MAPTST(&seen, vv))
857 if (num && --num == 0)
859 /* done with normal literals, now start level 1 literal processing */
860 p = -v; /* so that v doesn't get lost */
863 POOL_DEBUG(SOLV_DEBUG_ANALYZE, "got %d involved level 1 decisions\n", l1num);
864 /* clear non-l1 bits from seen map */
865 for (i = 0; i < q.count; i++)
868 MAPCLR(&seen, v > 0 ? v : -v);
870 /* only level 1 marks left in seen map */
871 l1num++; /* as l1retry decrements it */
875 why = solv->decisionq_why.elements[idx];
876 if (why <= 0) /* just in case, maybe for SYSTEMSOLVABLE */
878 c = solv->rules + why;
882 assert(rlevel > 0 && rlevel < level);
883 IF_POOLDEBUG (SOLV_DEBUG_ANALYZE)
885 POOL_DEBUG(SOLV_DEBUG_ANALYZE, "learned rule for level %d (am %d)\n", rlevel, level);
886 solver_printruleelement(solv, SOLV_DEBUG_ANALYZE, 0, p);
887 for (i = 0; i < q.count; i++)
888 solver_printruleelement(solv, SOLV_DEBUG_ANALYZE, 0, q.elements[i]);
890 /* push end marker on learnt reasons stack */
891 queue_push(&solv->learnt_pool, 0);
892 solv->stats_learned++;
894 POOL_DEBUG(SOLV_DEBUG_ANALYZE, "reverting decisions (level %d -> %d)\n", level, rlevel);
899 Id d = q.count ? q.elements[0] : 0;
901 r = solver_addrule(solv, p, d, 0);
905 Id d = pool_queuetowhatprovides(pool, &q);
907 r = solver_addrule(solv, p, 0, d);
909 assert(solv->learnt_why.count == (r - solv->rules) - solv->learntrules);
910 queue_push(&solv->learnt_why, learnt_why);
914 watch2onhighest(solv, r);
915 addwatches_rule(solv, r);
919 /* rule is an assertion */
920 queue_push(&solv->ruleassertions, r - solv->rules);
927 /*-------------------------------------------------------------------
931 * reset all solver decisions
932 * called after rules have been enabled/disabled
936 solver_reset(Solver *solv)
941 /* rewind all decisions */
942 for (i = solv->decisionq.count - 1; i >= 0; i--)
944 v = solv->decisionq.elements[i];
945 solv->decisionmap[v > 0 ? v : -v] = 0;
947 queue_empty(&solv->decisionq_why);
948 queue_empty(&solv->decisionq);
949 queue_empty(&solv->decisionq_reason);
950 solv->recommends_index = -1;
951 solv->propagate_index = 0;
952 queue_empty(&solv->branches);
954 /* adapt learnt rule status to new set of enabled/disabled rules */
955 enabledisablelearntrules(solv);
959 queue_contains(Queue *q, Id id)
962 for (i = 0; i < q->count; i++)
963 if (q->elements[i] == id)
969 disable_recommendsrules(Solver *solv, Queue *weakq)
971 Pool *pool = solv->pool;
973 for (i = 0; i < weakq->count; i++)
976 if (!queue_contains(solv->recommendsruleq, weakq->elements[i]))
978 r = solv->rules + weakq->elements[i];
981 POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "disabling ");
982 solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE, r);
983 solver_disablerule(solv, r);
988 /*-------------------------------------------------------------------
990 * analyze_unsolvable_rule
992 * recursion helper used by analyze_unsolvable
996 analyze_unsolvable_rule(Solver *solv, Rule *r, Queue *weakq, Map *rseen)
998 Pool *pool = solv->pool;
1000 Id why = r - solv->rules;
1002 IF_POOLDEBUG (SOLV_DEBUG_UNSOLVABLE)
1003 solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE, r);
1004 if (solv->learntrules && why >= solv->learntrules)
1006 if (MAPTST(rseen, why - solv->learntrules))
1008 MAPSET(rseen, why - solv->learntrules);
1009 for (i = solv->learnt_why.elements[why - solv->learntrules]; solv->learnt_pool.elements[i]; i++)
1010 if (solv->learnt_pool.elements[i] > 0)
1011 analyze_unsolvable_rule(solv, solv->rules + solv->learnt_pool.elements[i], weakq, rseen);
1014 if (solv->weakrulemap.size && MAPTST(&solv->weakrulemap, why) && weakq)
1015 queue_push(weakq, why);
1016 /* do not add pkg rules to problem */
1017 if (why < solv->pkgrules_end)
1019 /* turn rule into problem */
1020 if (why >= solv->jobrules && why < solv->jobrules_end)
1021 why = -(solv->ruletojob.elements[why - solv->jobrules] + 1);
1022 /* normalize dup/infarch rules */
1023 if (why > solv->infarchrules && why < solv->infarchrules_end)
1025 Id name = pool->solvables[-solv->rules[why].p].name;
1026 while (why > solv->infarchrules && pool->solvables[-solv->rules[why - 1].p].name == name)
1029 if (why > solv->duprules && why < solv->duprules_end)
1031 Id name = pool->solvables[-solv->rules[why].p].name;
1032 while (why > solv->duprules && pool->solvables[-solv->rules[why - 1].p].name == name)
1036 /* return if problem already countains our rule */
1037 if (solv->problems.count)
1039 for (i = solv->problems.count - 1; i >= 0; i--)
1040 if (solv->problems.elements[i] == 0) /* end of last problem reached? */
1042 else if (solv->problems.elements[i] == why)
1045 queue_push(&solv->problems, why);
1049 /*-------------------------------------------------------------------
1051 * analyze_unsolvable (called from setpropagatelearn)
1053 * We know that the problem is not solvable. Record all involved
1054 * rules (i.e. the "proof") into solv->learnt_pool.
1055 * Record the learnt pool index and all non-pkg rules into
1056 * solv->problems. (Our solutions to fix the problems are to
1057 * disable those rules.)
1059 * If the proof contains at least one weak rule, we disable the
1062 * Otherwise we return -1 if disablerules is not set or disable
1063 * _all_ of the problem rules and return 0.
1065 * return: 0 - disabled some rules, try again
1070 analyze_unsolvable(Solver *solv, Rule *cr, int disablerules)
1072 Pool *pool = solv->pool;
1074 Map involved; /* global to speed things up? */
1079 Id *decisionmap = solv->decisionmap;
1080 int oldproblemcount;
1081 int oldlearntpoolcount;
1082 int record_proof = 1;
1084 POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "ANALYZE UNSOLVABLE ----------------------\n");
1085 solv->stats_unsolvable++;
1086 oldproblemcount = solv->problems.count;
1087 oldlearntpoolcount = solv->learnt_pool.count;
1089 /* make room for proof index */
1090 /* must update it later, as analyze_unsolvable_rule would confuse
1091 * it with a rule index if we put the real value in already */
1092 queue_push(&solv->problems, 0);
1095 map_init(&involved, pool->nsolvables);
1096 map_init(&rseen, solv->learntrules ? solv->nrules - solv->learntrules : 0);
1099 queue_push(&solv->learnt_pool, r - solv->rules);
1100 analyze_unsolvable_rule(solv, r, &weakq, &rseen);
1101 FOR_RULELITERALS(v, pp, r)
1103 if (DECISIONMAP_TRUE(v)) /* the one true literal */
1105 vv = v > 0 ? v : -v;
1106 MAPSET(&involved, vv);
1108 idx = solv->decisionq.count;
1111 v = solv->decisionq.elements[--idx];
1112 vv = v > 0 ? v : -v;
1113 if (!MAPTST(&involved, vv) || vv == SYSTEMSOLVABLE)
1115 why = solv->decisionq_why.elements[idx];
1118 queue_push(&solv->learnt_pool, why);
1119 r = solv->rules + why;
1120 analyze_unsolvable_rule(solv, r, &weakq, &rseen);
1121 FOR_RULELITERALS(v, pp, r)
1123 if (DECISIONMAP_TRUE(v)) /* the one true literal */
1125 vv = v > 0 ? v : -v;
1126 MAPSET(&involved, vv);
1129 map_free(&involved);
1131 queue_push(&solv->problems, 0); /* mark end of this problem */
1136 /* revert problems */
1137 solv->problems.count = oldproblemcount;
1138 solv->learnt_pool.count = oldlearntpoolcount;
1139 /* find last weak */
1141 for (i = 0; i < weakq.count; i++)
1142 if (weakq.elements[i] > lastweak)
1143 lastweak = weakq.elements[i];
1144 if (lastweak < solv->pkgrules_end && solv->strongrecommends && solv->recommendsruleq && queue_contains(solv->recommendsruleq, lastweak))
1146 disable_recommendsrules(solv, &weakq);
1152 if (lastweak >= solv->jobrules && lastweak < solv->jobrules_end)
1153 v = -(solv->ruletojob.elements[lastweak - solv->jobrules] + 1);
1156 POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "disabling ");
1157 solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE, solv->rules + lastweak);
1158 if (lastweak >= solv->choicerules && lastweak < solv->choicerules_end)
1159 solver_disablechoicerules(solv, solv->rules + lastweak);
1160 solver_disableproblem(solv, v);
1162 solver_reenablepolicyrules(solv, -v);
1168 if (solv->allowuninstall || solv->allowuninstall_all || solv->allowuninstallmap.size)
1169 if (autouninstall(solv, solv->problems.elements + oldproblemcount + 1) != 0)
1171 solv->problems.count = oldproblemcount;
1172 solv->learnt_pool.count = oldlearntpoolcount;
1180 queue_push(&solv->learnt_pool, 0);
1181 solv->problems.elements[oldproblemcount] = oldlearntpoolcount;
1184 /* + 2: index + trailing zero */
1185 if (disablerules && oldproblemcount + 2 < solv->problems.count)
1187 for (i = oldproblemcount + 1; i < solv->problems.count - 1; i++)
1188 solver_disableproblem(solv, solv->problems.elements[i]);
1189 /* XXX: might want to enable all weak rules again */
1193 POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "UNSOLVABLE\n");
1198 /*-------------------------------------------------------------------
1202 * add free decision (solvable to install) to decisionq
1203 * increase level and propagate decision
1204 * return if no conflict.
1206 * in conflict case, analyze conflict rule, add resulting
1207 * rule to learnt rule set, make decision from learnt
1208 * rule (always unit) and re-propagate.
1210 * returns the new solver level or -1 if unsolvable
1215 setpropagatelearn(Solver *solv, int level, Id decision, int disablerules, Id ruleid, Id reason)
1217 Pool *pool = solv->pool;
1224 solv->decisionmap[decision] = level;
1226 solv->decisionmap[-decision] = -level;
1227 queue_push(&solv->decisionq, decision);
1228 queue_push(&solv->decisionq_why, -ruleid); /* <= 0 -> free decision */
1229 queue_push(&solv->decisionq_reason, reason);
1231 assert(ruleid >= 0 && level > 0);
1234 r = propagate(solv, level);
1238 return analyze_unsolvable(solv, r, disablerules);
1239 POOL_DEBUG(SOLV_DEBUG_ANALYZE, "conflict with rule #%d\n", (int)(r - solv->rules));
1240 level = analyze(solv, level, r, &lr);
1241 /* the new rule is unit by design */
1243 solv->decisionmap[decision > 0 ? decision : -decision] = decision > 0 ? level : -level;
1244 queue_push(&solv->decisionq, decision);
1245 queue_push(&solv->decisionq_why, lr - solv->rules);
1246 IF_POOLDEBUG (SOLV_DEBUG_ANALYZE)
1248 POOL_DEBUG(SOLV_DEBUG_ANALYZE, "decision: ");
1249 solver_printruleelement(solv, SOLV_DEBUG_ANALYZE, 0, decision);
1250 POOL_DEBUG(SOLV_DEBUG_ANALYZE, "new rule: ");
1251 solver_printrule(solv, SOLV_DEBUG_ANALYZE, lr);
1258 reorder_dq_for_future_installed(Solver *solv, int level, Queue *dq)
1260 Pool *pool = solv->pool;
1261 int i, j, haveone = 0, dqcount = dq->count;
1262 int decisionqcount = solv->decisionq.count;
1266 /* at the time we process jobrules the installed packages are not kept yet */
1267 /* reorder so that "future-supplemented" packages come first */
1268 FOR_REPO_SOLVABLES(solv->installed, p, s)
1270 if (MAPTST(&solv->noupdate, p - solv->installed->start))
1272 if (solv->decisionmap[p] == 0)
1274 if (s->recommends || s->suggests)
1275 queue_push(&solv->decisionq, p);
1276 solv->decisionmap[p] = level + 1;
1282 policy_update_recommendsmap(solv);
1283 for (i = 0; i < dqcount; i++)
1285 p = dq->elements[i];
1286 if (!(pool->solvables[p].repo == solv->installed || MAPTST(&solv->suggestsmap, p) || solver_is_enhancing(solv, pool->solvables + p)))
1289 dq->elements[i] = 0;
1292 dqcount = dq->count;
1293 for (i = 0; i < dqcount; i++)
1295 p = dq->elements[i];
1296 if (p && !(pool->solvables[p].repo == solv->installed || MAPTST(&solv->recommendsmap, p) || solver_is_supplementing(solv, pool->solvables + p)))
1299 dq->elements[i] = 0;
1302 for (i = j = 0; i < dq->count; i++)
1303 if (dq->elements[i])
1304 dq->elements[j++] = dq->elements[i];
1305 queue_truncate(dq, j);
1306 FOR_REPO_SOLVABLES(solv->installed, p, s)
1307 if (solv->decisionmap[p] == level + 1)
1308 solv->decisionmap[p] = 0;
1309 if (solv->decisionq.count != decisionqcount)
1311 solv->recommends_index = -1;
1312 queue_truncate(&solv->decisionq, decisionqcount);
1314 /* but obey favored maps */
1315 policy_prefer_favored(solv, dq);
1318 /*-------------------------------------------------------------------
1324 createbranch(Solver *solv, int level, Queue *dq, Id p, Id data)
1326 Pool *pool = solv->pool;
1328 IF_POOLDEBUG (SOLV_DEBUG_POLICY)
1330 POOL_DEBUG (SOLV_DEBUG_POLICY, "creating a branch:\n");
1331 for (i = 0; i < dq->count; i++)
1332 POOL_DEBUG (SOLV_DEBUG_POLICY, " - %s\n", pool_solvid2str(pool, dq->elements[i]));
1334 queue_push(&solv->branches, -dq->elements[0]);
1335 for (i = 1; i < dq->count; i++)
1336 queue_push(&solv->branches, dq->elements[i]);
1337 queue_push2(&solv->branches, p, data);
1338 queue_push2(&solv->branches, dq->count + 4, level);
1342 takebranch(Solver *solv, int pos, int end, const char *msg, int disablerules)
1344 Pool *pool = solv->pool;
1350 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]);
1351 for (i = end - solv->branches.elements[end - 2]; i < end - 4; i++)
1352 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]));
1355 level = solv->branches.elements[end - 1];
1356 p = solv->branches.elements[pos];
1357 solv->branches.elements[pos] = -p;
1358 POOL_DEBUG(SOLV_DEBUG_SOLVER, "%s %d -> %d with %s\n", msg, solv->decisionmap[p], level, pool_solvid2str(pool, p));
1359 /* hack: set level to zero so that revert does not remove the branch */
1360 solv->branches.elements[end - 1] = 0;
1361 revert(solv, level);
1362 solv->branches.elements[end - 1] = level;
1363 /* hack: revert simply sets the count, so we can still access the reverted elements */
1364 why = -solv->decisionq_why.elements[solv->decisionq_why.count];
1366 reason = solv->decisionq_reason.elements[level + 1];
1367 return setpropagatelearn(solv, level, p, disablerules, why, reason);
1370 /*-------------------------------------------------------------------
1372 * select and install
1374 * install best package from the queue. We add an extra package, inst, if
1375 * provided. See comment in weak install section.
1377 * returns the new solver level or -1 if unsolvable
1382 selectandinstall(Solver *solv, int level, Queue *dq, int disablerules, Id ruleid, Id reason)
1384 Pool *pool = solv->pool;
1388 policy_filter_unwanted(solv, dq, POLICY_MODE_CHOOSE);
1389 /* if we're resolving rules and didn't resolve the installed packages yet,
1390 * do some special supplements ordering */
1391 if (dq->count > 1 && solv->do_extra_reordering)
1392 reorder_dq_for_future_installed(solv, level, dq);
1393 /* if we have multiple candidates we open a branch */
1395 createbranch(solv, level, dq, 0, ruleid);
1396 p = dq->elements[0];
1397 POOL_DEBUG(SOLV_DEBUG_POLICY, "installing %s\n", pool_solvid2str(pool, p));
1398 return setpropagatelearn(solv, level, p, disablerules, ruleid, reason);
1402 /********************************************************************/
1403 /* Main solver interface */
1406 /*-------------------------------------------------------------------
1409 * create solver structure
1411 * pool: all available solvables
1412 * installed: installed Solvables
1415 * Upon solving, rules are created to flag the Solvables
1416 * of the 'installed' Repo as installed.
1420 solver_create(Pool *pool)
1423 solv = (Solver *)solv_calloc(1, sizeof(Solver));
1425 solv->installed = pool->installed;
1427 solv->allownamechange = 1;
1429 solv->dup_allowdowngrade = 1;
1430 solv->dup_allownamechange = 1;
1431 solv->dup_allowarchchange = 1;
1432 solv->dup_allowvendorchange = 1;
1434 solv->keepexplicitobsoletes = pool->noobsoletesmultiversion ? 0 : 1;
1436 queue_init(&solv->ruletojob);
1437 queue_init(&solv->decisionq);
1438 queue_init(&solv->decisionq_why);
1439 queue_init(&solv->decisionq_reason);
1440 queue_init(&solv->problems);
1441 queue_init(&solv->orphaned);
1442 queue_init(&solv->learnt_why);
1443 queue_init(&solv->learnt_pool);
1444 queue_init(&solv->branches);
1445 queue_init(&solv->weakruleq);
1446 queue_init(&solv->ruleassertions);
1447 queue_init(&solv->addedmap_deduceq);
1449 queue_push(&solv->learnt_pool, 0); /* so that 0 does not describe a proof */
1451 map_init(&solv->recommendsmap, pool->nsolvables);
1452 map_init(&solv->suggestsmap, pool->nsolvables);
1453 map_init(&solv->noupdate, solv->installed ? solv->installed->end - solv->installed->start : 0);
1454 solv->recommends_index = 0;
1456 solv->decisionmap = (Id *)solv_calloc(pool->nsolvables, sizeof(Id));
1458 solv->rules = solv_extend_resize(solv->rules, solv->nrules, sizeof(Rule), RULES_BLOCK);
1459 memset(solv->rules, 0, sizeof(Rule));
1466 /*-------------------------------------------------------------------
1472 queuep_free(Queue **qp)
1477 *qp = solv_free(*qp);
1481 map_zerosize(Map *m)
1491 solver_free(Solver *solv)
1493 queue_free(&solv->job);
1494 queue_free(&solv->ruletojob);
1495 queue_free(&solv->decisionq);
1496 queue_free(&solv->decisionq_why);
1497 queue_free(&solv->decisionq_reason);
1498 queue_free(&solv->learnt_why);
1499 queue_free(&solv->learnt_pool);
1500 queue_free(&solv->problems);
1501 queue_free(&solv->solutions);
1502 queue_free(&solv->orphaned);
1503 queue_free(&solv->branches);
1504 queue_free(&solv->weakruleq);
1505 queue_free(&solv->ruleassertions);
1506 queue_free(&solv->addedmap_deduceq);
1507 queuep_free(&solv->cleandeps_updatepkgs);
1508 queuep_free(&solv->cleandeps_mistakes);
1509 queuep_free(&solv->update_targets);
1510 queuep_free(&solv->installsuppdepq);
1511 queuep_free(&solv->recommendscplxq);
1512 queuep_free(&solv->suggestscplxq);
1513 queuep_free(&solv->brokenorphanrules);
1514 queuep_free(&solv->favorq);
1515 queuep_free(&solv->recommendsruleq);
1517 map_free(&solv->recommendsmap);
1518 map_free(&solv->suggestsmap);
1519 map_free(&solv->noupdate);
1520 map_free(&solv->weakrulemap);
1521 map_free(&solv->multiversion);
1523 map_free(&solv->updatemap);
1524 map_free(&solv->bestupdatemap);
1525 map_free(&solv->fixmap);
1526 map_free(&solv->dupmap);
1527 map_free(&solv->dupinvolvedmap);
1528 map_free(&solv->droporphanedmap);
1529 map_free(&solv->cleandepsmap);
1530 map_free(&solv->allowuninstallmap);
1531 map_free(&solv->favormap);
1532 map_free(&solv->isdisfavormap);
1534 solv_free(solv->decisionmap);
1535 solv_free(solv->rules);
1536 solv_free(solv->watches);
1537 solv_free(solv->obsoletes);
1538 solv_free(solv->obsoletes_data);
1539 solv_free(solv->specialupdaters);
1540 solv_free(solv->choicerules_ref);
1541 solv_free(solv->bestrules_pkg);
1542 solv_free(solv->yumobsrules_info);
1543 solv_free(solv->instbuddy);
1548 solver_get_flag(Solver *solv, int flag)
1552 case SOLVER_FLAG_ALLOW_DOWNGRADE:
1553 return solv->allowdowngrade;
1554 case SOLVER_FLAG_ALLOW_NAMECHANGE:
1555 return solv->allownamechange;
1556 case SOLVER_FLAG_ALLOW_ARCHCHANGE:
1557 return solv->allowarchchange;
1558 case SOLVER_FLAG_ALLOW_VENDORCHANGE:
1559 return solv->allowvendorchange;
1560 case SOLVER_FLAG_ALLOW_UNINSTALL:
1561 return solv->allowuninstall;
1562 case SOLVER_FLAG_NO_UPDATEPROVIDE:
1563 return solv->noupdateprovide;
1564 case SOLVER_FLAG_SPLITPROVIDES:
1565 return solv->dosplitprovides;
1566 case SOLVER_FLAG_IGNORE_RECOMMENDED:
1567 return solv->dontinstallrecommended;
1568 case SOLVER_FLAG_ADD_ALREADY_RECOMMENDED:
1569 return solv->addalreadyrecommended;
1570 case SOLVER_FLAG_NO_INFARCHCHECK:
1571 return solv->noinfarchcheck;
1572 case SOLVER_FLAG_KEEP_EXPLICIT_OBSOLETES:
1573 return solv->keepexplicitobsoletes;
1574 case SOLVER_FLAG_BEST_OBEY_POLICY:
1575 return solv->bestobeypolicy;
1576 case SOLVER_FLAG_NO_AUTOTARGET:
1577 return solv->noautotarget;
1578 case SOLVER_FLAG_DUP_ALLOW_DOWNGRADE:
1579 return solv->dup_allowdowngrade;
1580 case SOLVER_FLAG_DUP_ALLOW_NAMECHANGE:
1581 return solv->dup_allownamechange;
1582 case SOLVER_FLAG_DUP_ALLOW_ARCHCHANGE:
1583 return solv->dup_allowarchchange;
1584 case SOLVER_FLAG_DUP_ALLOW_VENDORCHANGE:
1585 return solv->dup_allowvendorchange;
1586 case SOLVER_FLAG_KEEP_ORPHANS:
1587 return solv->keep_orphans;
1588 case SOLVER_FLAG_BREAK_ORPHANS:
1589 return solv->break_orphans;
1590 case SOLVER_FLAG_FOCUS_INSTALLED:
1591 return solv->focus_installed;
1592 case SOLVER_FLAG_FOCUS_BEST:
1593 return solv->focus_best;
1594 case SOLVER_FLAG_YUM_OBSOLETES:
1595 return solv->do_yum_obsoletes;
1596 case SOLVER_FLAG_NEED_UPDATEPROVIDE:
1597 return solv->needupdateprovide;
1598 case SOLVER_FLAG_URPM_REORDER:
1599 return solv->urpmreorder;
1600 case SOLVER_FLAG_STRONG_RECOMMENDS:
1601 return solv->strongrecommends;
1602 case SOLVER_FLAG_INSTALL_ALSO_UPDATES:
1603 return solv->install_also_updates;
1611 solver_set_flag(Solver *solv, int flag, int value)
1613 int old = solver_get_flag(solv, flag);
1616 case SOLVER_FLAG_ALLOW_DOWNGRADE:
1617 solv->allowdowngrade = value;
1619 case SOLVER_FLAG_ALLOW_NAMECHANGE:
1620 solv->allownamechange = value;
1622 case SOLVER_FLAG_ALLOW_ARCHCHANGE:
1623 solv->allowarchchange = value;
1625 case SOLVER_FLAG_ALLOW_VENDORCHANGE:
1626 solv->allowvendorchange = value;
1628 case SOLVER_FLAG_ALLOW_UNINSTALL:
1629 solv->allowuninstall = value;
1631 case SOLVER_FLAG_NO_UPDATEPROVIDE:
1632 solv->noupdateprovide = value;
1634 case SOLVER_FLAG_SPLITPROVIDES:
1635 solv->dosplitprovides = value;
1637 case SOLVER_FLAG_IGNORE_RECOMMENDED:
1638 solv->dontinstallrecommended = value;
1640 case SOLVER_FLAG_ADD_ALREADY_RECOMMENDED:
1641 solv->addalreadyrecommended = value;
1643 case SOLVER_FLAG_NO_INFARCHCHECK:
1644 solv->noinfarchcheck = value;
1646 case SOLVER_FLAG_KEEP_EXPLICIT_OBSOLETES:
1647 solv->keepexplicitobsoletes = value;
1649 case SOLVER_FLAG_BEST_OBEY_POLICY:
1650 solv->bestobeypolicy = value;
1652 case SOLVER_FLAG_NO_AUTOTARGET:
1653 solv->noautotarget = value;
1655 case SOLVER_FLAG_DUP_ALLOW_DOWNGRADE:
1656 solv->dup_allowdowngrade = value;
1658 case SOLVER_FLAG_DUP_ALLOW_NAMECHANGE:
1659 solv->dup_allownamechange = value;
1661 case SOLVER_FLAG_DUP_ALLOW_ARCHCHANGE:
1662 solv->dup_allowarchchange = value;
1664 case SOLVER_FLAG_DUP_ALLOW_VENDORCHANGE:
1665 solv->dup_allowvendorchange = value;
1667 case SOLVER_FLAG_KEEP_ORPHANS:
1668 solv->keep_orphans = value;
1670 case SOLVER_FLAG_BREAK_ORPHANS:
1671 solv->break_orphans = value;
1673 case SOLVER_FLAG_FOCUS_INSTALLED:
1674 solv->focus_installed = value;
1676 case SOLVER_FLAG_FOCUS_BEST:
1677 solv->focus_best = value;
1679 case SOLVER_FLAG_YUM_OBSOLETES:
1680 solv->do_yum_obsoletes = value;
1682 case SOLVER_FLAG_NEED_UPDATEPROVIDE:
1683 solv->needupdateprovide = value;
1685 case SOLVER_FLAG_URPM_REORDER:
1686 solv->urpmreorder = value;
1688 case SOLVER_FLAG_STRONG_RECOMMENDS:
1689 solv->strongrecommends = value;
1691 case SOLVER_FLAG_INSTALL_ALSO_UPDATES:
1692 solv->install_also_updates = value;
1701 resolve_jobrules(Solver *solv, int level, int disablerules, Queue *dq)
1703 Pool *pool = solv->pool;
1704 int oldlevel = level;
1708 POOL_DEBUG(SOLV_DEBUG_SOLVER, "resolving job rules\n");
1709 for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++)
1712 if (r->d < 0) /* ignore disabled rules */
1715 FOR_RULELITERALS(l, pp, r)
1719 if (solv->decisionmap[-l] <= 0)
1724 if (solv->decisionmap[l] > 0)
1726 if (solv->decisionmap[l] == 0)
1730 if (l || !dq->count)
1732 /* prune to installed if not updating */
1733 if (dq->count > 1 && solv->installed && !solv->updatemap_all &&
1734 !solv->install_also_updates &&
1735 !(solv->job.elements[solv->ruletojob.elements[i - solv->jobrules]] & SOLVER_ORUPDATE))
1737 int j = dq->count, k;
1738 if (solv->updatemap.size)
1740 /* do not prune if an installed package wants to be updated */
1741 for (j = 0; j < dq->count; j++)
1742 if (pool->solvables[dq->elements[j]].repo == solv->installed
1743 && MAPTST(&solv->updatemap, dq->elements[j] - solv->installed->start))
1748 for (j = k = 0; j < dq->count; j++)
1749 if (pool->solvables[dq->elements[j]].repo == solv->installed)
1750 dq->elements[k++] = dq->elements[j];
1756 level = selectandinstall(solv, level, dq, disablerules, i, SOLVER_REASON_RESOLVE_JOB);
1757 if (level <= olevel)
1759 if (level == olevel)
1763 continue; /* try something else */
1765 if (level < oldlevel)
1767 /* redo from start of jobrules */
1768 i = solv->jobrules - 1;
1769 r = solv->rules + i;
1776 prune_to_update_targets(Solver *solv, Id *cp, Queue *q)
1780 for (i = j = 0; i < q->count; i++)
1783 for (cp2 = cp; *cp2; cp2++)
1786 q->elements[j++] = p;
1790 queue_truncate(q, j);
1794 resolve_installed(Solver *solv, int level, int disablerules, Queue *dq)
1796 Pool *pool = solv->pool;
1797 Repo *installed = solv->installed;
1799 int installedpos = solv->installedpos;
1802 int olevel, origlevel = level;
1804 POOL_DEBUG(SOLV_DEBUG_SOLVER, "resolving installed packages\n");
1806 installedpos = installed->start;
1807 /* we use two passes if we need to update packages
1808 * to create a better user experience */
1809 for (pass = solv->updatemap.size ? 0 : 1; pass < 2; )
1811 int passlevel = level;
1812 Id *specialupdaters = solv->specialupdaters;
1813 /* start with installedpos, the position that gave us problems the last time */
1814 for (i = installedpos, n = installed->start; n < installed->end; i++, n++)
1819 if (i == installed->end)
1820 i = installed->start;
1821 s = pool->solvables + i;
1822 if (s->repo != installed)
1825 if (solv->decisionmap[i] > 0 && (!specialupdaters || !specialupdaters[i - installed->start]))
1826 continue; /* already decided */
1827 if (!pass && solv->updatemap.size && !MAPTST(&solv->updatemap, i - installed->start))
1828 continue; /* updates first */
1829 r = solv->rules + solv->updaterules + (i - installed->start);
1831 if (!rr->p || rr->d < 0) /* disabled -> look at feature rule */
1832 rr -= solv->installed->end - solv->installed->start;
1833 if (!rr->p) /* identical to update rule? */
1836 continue; /* orpaned package or pseudo package */
1838 /* check if we should update this package to the latest version
1839 * noupdate is set for erase jobs, in that case we want to deinstall
1840 * the installed package and not replace it with a newer version
1841 * rr->p != i is for dup jobs where the installed package cannot be kept */
1844 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)))
1846 if (specialupdaters && (d = specialupdaters[i - installed->start]) != 0)
1848 /* special multiversion handling, make sure best version is chosen */
1849 if (rr->p == i && solv->decisionmap[i] >= 0)
1851 while ((p = pool->whatprovidesdata[d++]) != 0)
1852 if (solv->decisionmap[p] >= 0)
1854 if (dq->count && solv->update_targets && solv->update_targets->elements[i - installed->start])
1855 prune_to_update_targets(solv, solv->update_targets->elements + solv->update_targets->elements[i - installed->start], dq);
1858 policy_filter_unwanted(solv, dq, POLICY_MODE_CHOOSE);
1859 p = dq->elements[0];
1860 if (p != i && solv->decisionmap[p] == 0)
1862 rr = solv->rules + solv->featurerules + (i - solv->installed->start);
1863 if (!rr->p) /* update rule == feature rule? */
1864 rr = rr - solv->featurerules + solv->updaterules;
1873 /* update to best package of the update rule */
1874 FOR_RULELITERALS(p, pp, rr)
1876 if (solv->decisionmap[p] > 0)
1878 dq->count = 0; /* already fulfilled */
1881 if (!solv->decisionmap[p])
1886 if (dq->count && solv->update_targets && solv->update_targets->elements[i - installed->start])
1887 prune_to_update_targets(solv, solv->update_targets->elements + solv->update_targets->elements[i - installed->start], dq);
1888 /* install best version */
1892 level = selectandinstall(solv, level, dq, disablerules, rr - solv->rules, SOLVER_REASON_UPDATE_INSTALLED);
1893 if (level <= olevel)
1895 if (level < passlevel)
1896 break; /* trouble */
1898 n = installed->start; /* redo all */
1904 /* if still undecided keep package */
1905 if (solv->decisionmap[i] == 0)
1908 if (solv->cleandepsmap.size && MAPTST(&solv->cleandepsmap, i - installed->start))
1911 POOL_DEBUG(SOLV_DEBUG_POLICY, "cleandeps erasing %s\n", pool_solvid2str(pool, i));
1912 level = setpropagatelearn(solv, level, -i, disablerules, 0, SOLVER_REASON_CLEANDEPS_ERASE);
1919 POOL_DEBUG(SOLV_DEBUG_POLICY, "keeping %s\n", pool_solvid2str(pool, i));
1920 level = setpropagatelearn(solv, level, i, disablerules, r - solv->rules, SOLVER_REASON_KEEP_INSTALLED);
1922 if (level <= olevel)
1924 if (level < passlevel)
1925 break; /* trouble */
1927 n = installed->start; /* redo all */
1930 continue; /* retry with learnt rule */
1934 if (n < installed->end)
1936 installedpos = i; /* retry problem solvable next time */
1937 if (level < origlevel)
1938 break; /* ran into trouble */
1939 /* re-run all passes */
1940 pass = solv->updatemap.size ? 0 : 1;
1943 /* reset installedpos, advance to next pass */
1944 installedpos = installed->start;
1947 solv->installedpos = installedpos;
1952 resolve_dependencies(Solver *solv, int level, int disablerules, Queue *dq)
1954 Pool *pool = solv->pool;
1958 int origlevel = level;
1964 POOL_DEBUG(SOLV_DEBUG_POLICY, "deciding unresolved rules\n");
1966 for (i = 1, n = 1; ; i++, n++)
1968 if (n >= solv->nrules)
1976 if (i == solv->nrules)
1978 r = solv->rules + i;
1979 if (r->d < 0) /* ignore disabled rules */
1981 if (r->p < 0) /* most common cases first */
1983 if (r->d == 0 || solv->decisionmap[-r->p] <= 0)
1990 /* binary or unary rule */
1991 /* need two positive undecided literals, r->p already checked above */
1994 if (solv->decisionmap[r->p] || solv->decisionmap[r->w2])
1996 queue_push(dq, r->p);
1997 queue_push(dq, r->w2);
2002 * all negative literals are installed
2003 * no positive literal is installed
2004 * i.e. the rule is not fulfilled and we
2005 * just need to decide on the positive literals
2006 * (decisionmap[-r->p] for the r->p < 0 case is already checked above)
2010 if (solv->decisionmap[r->p] > 0)
2012 if (solv->decisionmap[r->p] == 0)
2013 queue_push(dq, r->p);
2015 dp = pool->whatprovidesdata + r->d;
2016 while ((p = *dp++) != 0)
2020 if (solv->decisionmap[-p] <= 0)
2025 if (solv->decisionmap[p] > 0)
2027 if (solv->decisionmap[p] == 0)
2034 IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
2036 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "unfulfilled ");
2037 solver_printruleclass(solv, SOLV_DEBUG_PROPAGATE, r);
2039 /* dq->count < 2 cannot happen as this means that
2040 * the rule is unit */
2041 assert(dq->count > 1);
2043 /* prune to cleandeps packages */
2044 if (solv->cleandepsmap.size && solv->installed)
2046 Repo *installed = solv->installed;
2047 for (j = 0; j < dq->count; j++)
2048 if (pool->solvables[dq->elements[j]].repo == installed && MAPTST(&solv->cleandepsmap, dq->elements[j] - installed->start))
2052 dq->elements[0] = dq->elements[j];
2053 queue_truncate(dq, 1);
2057 if (dq->count > 1 && postponed >= 0)
2059 policy_filter_unwanted(solv, dq, POLICY_MODE_CHOOSE_NOREORDER);
2068 level = selectandinstall(solv, level, dq, disablerules, r - solv->rules, SOLVER_REASON_RESOLVE);
2069 if (level < origlevel)
2070 break; /* trouble */
2071 /* something changed, so look at all rules again */
2078 #ifdef ENABLE_COMPLEX_DEPS
2081 add_complex_recommends(Solver *solv, Id rec, Queue *dq, Map *dqmap)
2083 Pool *pool = solv->pool;
2084 int oldcnt = dq->count;
2090 printf("ADD_COMPLEX_RECOMMENDS %s\n", pool_dep2str(pool, rec));
2092 i = pool_normalize_complex_dep(pool, rec, dq, CPLXDEPS_EXPAND);
2093 if (i == 0 || i == 1)
2096 for (i = oldcnt; i < cutcnt; i++)
2099 for (; (p = dq->elements[i]) != 0; i++)
2103 if (solv->decisionmap[-p] <= 0)
2107 if (solv->decisionmap[p] > 0)
2109 queue_truncate(dq, blkcnt);
2114 if (!MAPTST(dqmap, p))
2119 if (solv->decisionmap[p] < 0)
2121 if (solv->process_orphans && solv->installed && pool->solvables[p].repo == solv->installed && (solv->droporphanedmap_all || (solv->droporphanedmap.size && MAPTST(&solv->droporphanedmap, p - solv->installed->start))))
2126 while (dq->elements[i])
2129 queue_deleten(dq, oldcnt, cutcnt - oldcnt);
2131 if (dq->count != oldcnt)
2133 for (j = oldcnt; j < dq->count; j++)
2135 p = dq->elements[j];
2136 for (i = 0; i < j; i++)
2137 if (dq->elements[i] == p)
2139 dq->elements[j] = 0;
2143 for (i = j = oldcnt; j < dq->count; j++)
2144 if (dq->elements[j])
2145 dq->elements[i++] = dq->elements[j];
2146 queue_truncate(dq, i);
2149 printf("RETURN:\n");
2150 for (i = oldcnt; i < dq->count; i++)
2151 printf(" - %s\n", pool_solvid2str(pool, dq->elements[i]));
2156 do_complex_recommendations(Solver *solv, Id rec, Map *m, int noselected)
2158 Pool *pool = solv->pool;
2164 printf("DO_COMPLEX_RECOMMENDATIONS %s\n", pool_dep2str(pool, rec));
2167 i = pool_normalize_complex_dep(pool, rec, &dq, CPLXDEPS_EXPAND);
2168 if (i == 0 || i == 1)
2173 for (i = 0; i < dq.count; i++)
2176 for (; (p = dq.elements[i]) != 0; i++)
2180 if (solv->decisionmap[-p] <= 0)
2184 if (solv->decisionmap[p] > 0)
2189 for (i++; (p = dq.elements[i]) != 0; i++)
2190 if (p > 0 && solv->decisionmap[p] > 0)
2198 for (i = blk; (p = dq.elements[i]) != 0; i++)
2202 while (dq.elements[i])
2211 prune_disfavored(Solver *solv, Queue *plist)
2214 if (!solv->isdisfavormap.size)
2216 for (i = j = 0; i < plist->count; i++)
2218 Id p = plist->elements[i];
2219 if (!MAPTST(&solv->isdisfavormap, p))
2220 plist->elements[j++] = p;
2223 queue_truncate(plist, j);
2227 resolve_weak(Solver *solv, int level, int disablerules, Queue *dq, Queue *dqs, int *rerunp)
2229 Pool *pool = solv->pool;
2237 POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended packages\n");
2239 queue_empty(dq); /* recommended packages */
2241 queue_empty(dqs); /* supplemented packages */
2242 for (i = 1; i < pool->nsolvables; i++)
2244 if (solv->decisionmap[i] < 0)
2246 s = pool->solvables + i;
2247 if (solv->decisionmap[i] > 0)
2249 /* installed, check for recommends */
2250 Id *recp, rec, pp, p;
2251 if (!solv->addalreadyrecommended && s->repo == solv->installed)
2253 /* XXX need to special case AND ? */
2256 recp = s->repo->idarraydata + s->recommends;
2257 while ((rec = *recp++) != 0)
2259 #ifdef ENABLE_COMPLEX_DEPS
2260 if (pool_is_complex_dep(pool, rec))
2262 add_complex_recommends(solv, rec, dq, 0);
2267 FOR_PROVIDES(p, pp, rec)
2269 if (solv->decisionmap[p] > 0)
2274 else if (solv->decisionmap[p] == 0)
2276 if (solv->process_orphans && solv->installed && pool->solvables[p].repo == solv->installed && (solv->droporphanedmap_all || (solv->droporphanedmap.size && MAPTST(&solv->droporphanedmap, p - solv->installed->start))))
2278 queue_pushunique(dq, p);
2286 /* not yet installed, check if supplemented */
2287 if (!s->supplements)
2289 if (!pool_installable(pool, s))
2291 if (!solver_is_supplementing(solv, s))
2293 if (solv->process_orphans && solv->installed && s->repo == solv->installed && (solv->droporphanedmap_all || (solv->droporphanedmap.size && MAPTST(&solv->droporphanedmap, i - solv->installed->start))))
2295 if (solv->isdisfavormap.size && MAPTST(&solv->isdisfavormap, i))
2296 continue; /* disfavored supplements, do not install */
2301 /* filter out disfavored recommended packages */
2302 if (dq->count && solv->isdisfavormap.size)
2303 prune_disfavored(solv, dq);
2305 /* filter out all packages obsoleted by installed packages */
2306 /* this is no longer needed if we have (and trust) reverse obsoletes */
2307 if ((dqs->count || dq->count) && solv->installed)
2310 Id obs, *obsp, po, ppo;
2312 map_init(&obsmap, pool->nsolvables);
2313 for (p = solv->installed->start; p < solv->installed->end; p++)
2315 s = pool->solvables + p;
2316 if (s->repo != solv->installed || !s->obsoletes)
2318 if (solv->decisionmap[p] <= 0)
2320 if (!solv->keepexplicitobsoletes && solv->multiversion.size && MAPTST(&solv->multiversion, p))
2322 obsp = s->repo->idarraydata + s->obsoletes;
2323 /* foreach obsoletes */
2324 while ((obs = *obsp++) != 0)
2325 FOR_PROVIDES(po, ppo, obs)
2327 Solvable *pos = pool->solvables + po;
2328 if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, pos, obs))
2330 if (pool->obsoleteusescolors && !pool_colormatch(pool, s, pos))
2332 MAPSET(&obsmap, po);
2335 for (i = j = 0; i < dqs->count; i++)
2336 if (!MAPTST(&obsmap, dqs->elements[i]))
2337 dqs->elements[j++] = dqs->elements[i];
2339 for (i = j = 0; i < dq->count; i++)
2340 if (!MAPTST(&obsmap, dq->elements[i]))
2341 dq->elements[j++] = dq->elements[i];
2346 /* filter out all already supplemented packages if requested */
2347 if (!solv->addalreadyrecommended && dqs->count)
2349 /* filter out old supplements */
2350 for (i = j = 0; i < dqs->count; i++)
2352 p = dqs->elements[i];
2353 s = pool->solvables + p;
2354 if (s->supplements && solver_is_supplementing_alreadyinstalled(solv, s))
2355 dqs->elements[j++] = p;
2360 /* multiversion doesn't mix well with supplements.
2361 * filter supplemented packages where we already decided
2362 * to install a different version (see bnc#501088) */
2363 if (dqs->count && solv->multiversion.size)
2365 for (i = j = 0; i < dqs->count; i++)
2367 p = dqs->elements[i];
2368 if (MAPTST(&solv->multiversion, p))
2371 s = pool->solvables + p;
2372 FOR_PROVIDES(p2, pp2, s->name)
2373 if (solv->decisionmap[p2] > 0 && pool->solvables[p2].name == s->name)
2376 continue; /* ignore this package */
2378 dqs->elements[j++] = p;
2383 /* implicitobsoleteusescolors doesn't mix well with supplements.
2384 * filter supplemented packages where we already decided
2385 * to install a different architecture */
2386 if (dqs->count && pool->implicitobsoleteusescolors)
2388 for (i = j = 0; i < dqs->count; i++)
2391 p = dqs->elements[i];
2392 s = pool->solvables + p;
2393 FOR_PROVIDES(p2, pp2, s->name)
2394 if (solv->decisionmap[p2] > 0 && pool->solvables[p2].name == s->name && pool->solvables[p2].arch != s->arch)
2397 continue; /* ignore this package */
2398 dqs->elements[j++] = p;
2403 /* make dq contain both recommended and supplemented pkgs */
2406 for (i = 0; i < dqs->count; i++)
2407 queue_pushunique(dq, dqs->elements[i]);
2416 /* simple case, just one package. no need to choose to best version */
2417 p = dq->elements[0];
2419 POOL_DEBUG(SOLV_DEBUG_POLICY, "installing supplemented %s\n", pool_solvid2str(pool, p));
2421 POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended %s\n", pool_solvid2str(pool, p));
2422 return setpropagatelearn(solv, level, p, 0, 0, SOLVER_REASON_WEAKDEP);
2425 /* filter packages, this gives us the best versions */
2426 policy_filter_unwanted(solv, dq, POLICY_MODE_RECOMMEND);
2428 /* create map of result */
2429 map_init(&dqmap, pool->nsolvables);
2430 for (i = 0; i < dq->count; i++)
2431 MAPSET(&dqmap, dq->elements[i]);
2433 /* prune dqs so that it only contains the best versions */
2434 for (i = j = 0; i < dqs->count; i++)
2436 p = dqs->elements[i];
2437 if (MAPTST(&dqmap, p))
2438 dqs->elements[j++] = p;
2442 /* install all supplemented packages, but order first */
2444 policy_filter_unwanted(solv, dqs, POLICY_MODE_SUPPLEMENT);
2445 decisioncount = solv->decisionq.count;
2446 for (i = 0; i < dqs->count; i++)
2448 p = dqs->elements[i];
2449 if (solv->decisionmap[p])
2451 POOL_DEBUG(SOLV_DEBUG_POLICY, "installing supplemented %s\n", pool_solvid2str(pool, p));
2453 level = setpropagatelearn(solv, level, p, 0, 0, SOLVER_REASON_WEAKDEP);
2454 if (level <= olevel)
2457 if (i < dqs->count || solv->decisionq.count < decisioncount)
2463 /* install all recommended packages */
2464 /* more work as we want to created branches if multiple
2465 * choices are valid */
2466 for (i = 0; i < decisioncount; i++)
2469 p = solv->decisionq.elements[i];
2472 s = pool->solvables + p;
2473 if (!s->repo || (!solv->addalreadyrecommended && s->repo == solv->installed))
2477 recp = s->repo->idarraydata + s->recommends;
2478 while ((rec = *recp++) != 0)
2481 #ifdef ENABLE_COMPLEX_DEPS
2482 if (pool_is_complex_dep(pool, rec))
2483 add_complex_recommends(solv, rec, dq, &dqmap);
2486 FOR_PROVIDES(p, pp, rec)
2488 if (solv->decisionmap[p] > 0)
2493 else if (solv->decisionmap[p] == 0 && MAPTST(&dqmap, p))
2499 policy_filter_unwanted(solv, dq, POLICY_MODE_CHOOSE);
2500 /* if we have multiple candidates we open a branch */
2502 createbranch(solv, level, dq, s - pool->solvables, rec);
2503 p = dq->elements[0];
2504 POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended %s\n", pool_solvid2str(pool, p));
2506 level = setpropagatelearn(solv, level, p, 0, 0, SOLVER_REASON_WEAKDEP);
2507 if (level <= olevel || solv->decisionq.count < decisioncount)
2508 break; /* we had to revert some decisions */
2511 break; /* had a problem above, quit loop */
2518 resolve_cleandeps(Solver *solv, int level, int disablerules, int *rerunp)
2520 Pool *pool = solv->pool;
2521 Repo *installed = solv->installed;
2526 if (!installed || !solv->cleandepsmap.size)
2528 POOL_DEBUG(SOLV_DEBUG_SOLVER, "deciding cleandeps packages\n");
2529 for (p = installed->start; p < installed->end; p++)
2531 s = pool->solvables + p;
2532 if (s->repo != installed)
2534 if (solv->decisionmap[p] != 0 || !MAPTST(&solv->cleandepsmap, p - installed->start))
2536 POOL_DEBUG(SOLV_DEBUG_POLICY, "cleandeps erasing %s\n", pool_solvid2str(pool, p));
2538 level = setpropagatelearn(solv, level, -p, 0, 0, SOLVER_REASON_CLEANDEPS_ERASE);
2542 if (p < installed->end)
2548 resolve_orphaned(Solver *solv, int level, int disablerules, Queue *dq, int *rerunp)
2550 Pool *pool = solv->pool;
2553 int installedone = 0;
2556 /* let's see if we can install some unsupported package */
2557 POOL_DEBUG(SOLV_DEBUG_SOLVER, "deciding orphaned packages\n");
2558 for (i = 0; i < solv->orphaned.count; i++)
2560 p = solv->orphaned.elements[i];
2561 if (solv->decisionmap[p])
2562 continue; /* already decided */
2563 if (solv->droporphanedmap_all)
2565 if (solv->droporphanedmap.size && MAPTST(&solv->droporphanedmap, p - solv->installed->start))
2567 POOL_DEBUG(SOLV_DEBUG_SOLVER, "keeping orphaned %s\n", pool_solvid2str(pool, p));
2569 level = setpropagatelearn(solv, level, p, 0, 0, SOLVER_REASON_RESOLVE_ORPHAN);
2574 if (installedone || i < solv->orphaned.count)
2579 for (i = 0; i < solv->orphaned.count; i++)
2581 p = solv->orphaned.elements[i];
2582 if (solv->decisionmap[p])
2583 continue; /* already decided */
2584 POOL_DEBUG(SOLV_DEBUG_SOLVER, "removing orphaned %s\n", pool_solvid2str(pool, p));
2586 level = setpropagatelearn(solv, level, -p, 0, 0, SOLVER_REASON_RESOLVE_ORPHAN);
2593 if (solv->brokenorphanrules)
2595 solver_check_brokenorphanrules(solv, dq);
2598 policy_filter_unwanted(solv, dq, POLICY_MODE_CHOOSE);
2599 for (i = 0; i < dq->count; i++)
2601 p = dq->elements[i];
2602 POOL_DEBUG(SOLV_DEBUG_POLICY, "installing orphaned dep %s\n", pool_solvid2str(pool, p));
2604 level = setpropagatelearn(solv, level, p, 0, 0, SOLVER_REASON_RESOLVE_ORPHAN);
2614 /*-------------------------------------------------------------------
2618 * all rules have been set up, now actually run the solver
2623 solver_run_sat(Solver *solv, int disablerules, int doweak)
2625 Queue dq; /* local decisionqueue */
2626 Queue dqs; /* local decisionqueue for supplements */
2632 Pool *pool = solv->pool;
2634 int minimizationsteps;
2636 IF_POOLDEBUG (SOLV_DEBUG_RULE_CREATION)
2638 POOL_DEBUG (SOLV_DEBUG_RULE_CREATION, "number of rules: %d\n", solv->nrules);
2639 for (i = 1; i < solv->nrules; i++)
2640 solver_printruleclass(solv, SOLV_DEBUG_RULE_CREATION, solv->rules + i);
2643 /* start SAT algorithm */
2645 systemlevel = level + 1;
2646 POOL_DEBUG(SOLV_DEBUG_SOLVER, "solving...\n");
2650 solv->installedpos = 0;
2651 solv->do_extra_reordering = 0;
2654 * here's the main loop:
2655 * 1) decide assertion rules and propagate
2657 * 3) try to keep installed packages
2658 * 4) fulfill all unresolved rules
2659 * 5) install recommended packages
2660 * 6) minimalize solution if we had choices
2661 * if we encounter a problem, we rewind to a safe level and restart
2665 minimizationsteps = 0;
2669 * initial propagation of the assertions
2675 makeruledecisions(solv);
2677 if (!disablerules && solv->problems.count)
2682 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "initial propagate (propagate_index: %d; size decisionq: %d)...\n", solv->propagate_index, solv->decisionq.count);
2683 if ((r = propagate(solv, level)) != 0)
2685 level = analyze_unsolvable(solv, r, disablerules);
2688 systemlevel = level + 1;
2692 * resolve jobs first (unless focus_installed is set)
2694 if (level < systemlevel && !solv->focus_installed)
2696 if (solv->installed && solv->installed->nsolvables && !solv->installed->disabled)
2697 solv->do_extra_reordering = 1;
2699 level = resolve_jobrules(solv, level, disablerules, &dq);
2700 solv->do_extra_reordering = 0;
2703 systemlevel = level + 1;
2706 /* resolve job dependencies in the focus_best case */
2707 if (level < systemlevel && solv->focus_best && !solv->focus_installed && solv->installed && solv->installed->nsolvables && !solv->installed->disabled)
2709 solv->do_extra_reordering = 1;
2711 level = resolve_dependencies(solv, level, disablerules, &dq);
2712 solv->do_extra_reordering = 0;
2714 continue; /* start over */
2715 systemlevel = level + 1;
2719 * installed packages
2721 if (level < systemlevel && solv->installed && solv->installed->nsolvables && !solv->installed->disabled)
2724 level = resolve_installed(solv, level, disablerules, &dq);
2727 systemlevel = level + 1;
2730 /* resolve jobs in focus_installed case */
2731 if (level < systemlevel && solv->focus_installed)
2734 level = resolve_jobrules(solv, level, disablerules, &dq);
2737 systemlevel = level + 1;
2740 if (level < systemlevel)
2741 systemlevel = level;
2743 /* resolve all dependencies */
2745 level = resolve_dependencies(solv, level, disablerules, &dq);
2747 continue; /* start over */
2749 /* decide leftover cleandeps packages */
2750 if (solv->cleandepsmap.size && solv->installed)
2753 level = resolve_cleandeps(solv, level, disablerules, &rerun);
2758 /* at this point we have a consistent system. now do the extras... */
2763 level = resolve_weak(solv, level, disablerules, &dq, &dqs, &rerun);
2768 if (solv->installed && (solv->orphaned.count || solv->brokenorphanrules))
2771 level = resolve_orphaned(solv, level, disablerules, &dq, &rerun);
2776 /* one final pass to make sure we decided all installed packages */
2777 if (solv->installed)
2779 for (p = solv->installed->start; p < solv->installed->end; p++)
2781 if (solv->decisionmap[p])
2782 continue; /* already decided */
2783 s = pool->solvables + p;
2784 if (s->repo != solv->installed)
2786 POOL_DEBUG(SOLV_DEBUG_SOLVER, "removing unwanted %s\n", pool_solvid2str(pool, p));
2788 level = setpropagatelearn(solv, level, -p, 0, 0, SOLVER_REASON_CLEANDEPS_ERASE);
2792 if (p < solv->installed->end)
2793 continue; /* back to main loop */
2796 if (solv->installed && solv->cleandepsmap.size && solver_check_cleandeps_mistakes(solv))
2799 level = 0; /* restart from scratch */
2803 if (solv->solution_callback)
2805 solv->solution_callback(solv, solv->solution_callback_data);
2806 if (solv->branches.count)
2810 for (i = solv->branches.count - 1; i >= 0; i--)
2812 p = solv->branches.elements[i];
2817 i -= 3; /* skip: p data count */
2826 while (i > 0 && solv->branches.elements[i - 1] > 0)
2828 level = takebranch(solv, i, endi, "branching", disablerules);
2832 /* all branches done, we're finally finished */
2836 /* auto-minimization step */
2837 if (solv->branches.count)
2839 int endi, lasti = -1, lastiend = -1;
2840 if (solv->recommends_index < solv->decisionq.count)
2841 policy_update_recommendsmap(solv);
2842 for (endi = solv->branches.count; endi > 0;)
2844 int l, lastsi = -1, starti = endi - solv->branches.elements[endi - 2];
2845 l = solv->branches.elements[endi - 1];
2846 for (i = starti; i < endi - 4; i++)
2848 p = solv->branches.elements[i];
2851 if (solv->decisionmap[p] > l)
2858 if (solv->isdisfavormap.size && MAPTST(&solv->isdisfavormap, p))
2860 if (lastsi < 0 && (MAPTST(&solv->recommendsmap, p) || solver_is_supplementing(solv, pool->solvables + p)))
2865 /* we have a recommended package that could not be installed */
2866 /* take it if our current selection is not recommended */
2867 for (i = starti; i < endi - 4; i++)
2869 p = -solv->branches.elements[i];
2870 if (p <= 0 || solv->decisionmap[p] != l + 1)
2872 if (solv->favormap.size && MAPTST(&solv->favormap, p))
2873 if (!(solv->isdisfavormap.size && MAPTST(&solv->isdisfavormap, p)))
2874 continue; /* current selection is favored */
2875 if (!(MAPTST(&solv->recommendsmap, p) || solver_is_supplementing(solv, pool->solvables + p)))
2887 minimizationsteps++;
2888 level = takebranch(solv, lasti, lastiend, "minimizing", disablerules);
2889 continue; /* back to main loop */
2892 /* no minimization found, we're finally finished! */
2895 assert(level == -1 || level + 1 == solv->decisionq_reason.count);
2897 POOL_DEBUG(SOLV_DEBUG_STATS, "solver statistics: %d learned rules, %d unsolvable, %d minimization steps\n", solv->stats_learned, solv->stats_unsolvable, minimizationsteps);
2899 POOL_DEBUG(SOLV_DEBUG_STATS, "done solving.\n\n");
2903 solver_printdecisionq(solv, SOLV_DEBUG_RESULT);
2908 /*-------------------------------------------------------------------
2910 * remove disabled conflicts
2912 * purpose: update the decisionmap after some rules were disabled.
2913 * this is used to calculate the suggested/recommended package list.
2914 * Also returns a "removed" list to undo the discisionmap changes.
2918 removedisabledconflicts(Solver *solv, Queue *removed)
2920 Pool *pool = solv->pool;
2925 Id *decisionmap = solv->decisionmap;
2927 queue_empty(removed);
2928 for (i = 0; i < solv->decisionq.count; i++)
2930 p = solv->decisionq.elements[i];
2932 continue; /* conflicts only, please */
2933 why = solv->decisionq_why.elements[i];
2936 /* no rule involved, must be a orphan package drop */
2939 /* we never do conflicts on free decisions, so there
2940 * must have been an unit rule */
2942 r = solv->rules + why;
2943 if (r->d < 0 && decisionmap[-p])
2945 /* rule is now disabled, remove from decisionmap */
2946 POOL_DEBUG(SOLV_DEBUG_SOLVER, "removing conflict for package %s[%d]\n", pool_solvid2str(pool, -p), -p);
2947 queue_push(removed, -p);
2948 queue_push(removed, decisionmap[-p]);
2949 decisionmap[-p] = 0;
2952 if (!removed->count)
2954 /* we removed some confliced packages. some of them might still
2955 * be in conflict, so search for unit rules and re-conflict */
2957 for (i = n = 1, r = solv->rules + i; n < solv->nrules; i++, r++, n++)
2959 if (i == solv->nrules)
2962 r = solv->rules + i;
2968 if (r->p < 0 && !decisionmap[-r->p])
2974 if (r->p < 0 && decisionmap[-r->p] == 0 && DECISIONMAP_FALSE(r->w2))
2976 else if (r->w2 < 0 && decisionmap[-r->w2] == 0 && DECISIONMAP_FALSE(r->p))
2981 if (r->p < 0 && decisionmap[-r->p] == 0)
2983 if (new || DECISIONMAP_FALSE(r->p))
2985 dp = pool->whatprovidesdata + r->d;
2986 while ((p = *dp++) != 0)
2988 if (new && p == new)
2990 if (p < 0 && decisionmap[-p] == 0)
2999 else if (!DECISIONMAP_FALSE(p))
3009 POOL_DEBUG(SOLV_DEBUG_SOLVER, "re-conflicting package %s[%d]\n", pool_solvid2str(pool, -new), -new);
3010 decisionmap[-new] = -1;
3012 n = 0; /* redo all rules */
3018 undo_removedisabledconflicts(Solver *solv, Queue *removed)
3021 for (i = 0; i < removed->count; i += 2)
3022 solv->decisionmap[removed->elements[i]] = removed->elements[i + 1];
3026 /*-------------------------------------------------------------------
3028 * weaken solvable dependencies
3032 weaken_solvable_deps(Solver *solv, Id p)
3037 for (i = 1, r = solv->rules + i; i < solv->pkgrules_end; i++, r++)
3041 if ((r->d == 0 || r->d == -1) && r->w2 < 0)
3042 continue; /* conflict */
3043 queue_push(&solv->weakruleq, i);
3048 /********************************************************************/
3053 solver_calculate_multiversionmap(Pool *pool, Queue *job, Map *multiversionmap)
3056 Id how, what, select;
3058 for (i = 0; i < job->count; i += 2)
3060 how = job->elements[i];
3061 if ((how & SOLVER_JOBMASK) != SOLVER_MULTIVERSION)
3063 what = job->elements[i + 1];
3064 select = how & SOLVER_SELECTMASK;
3065 if (!multiversionmap->size)
3066 map_grow(multiversionmap, pool->nsolvables);
3067 if (select == SOLVER_SOLVABLE_ALL)
3069 FOR_POOL_SOLVABLES(p)
3070 MAPSET(multiversionmap, p);
3072 else if (select == SOLVER_SOLVABLE_REPO)
3075 Repo *repo = pool_id2repo(pool, what);
3078 FOR_REPO_SOLVABLES(repo, p, s)
3079 MAPSET(multiversionmap, p);
3082 FOR_JOB_SELECT(p, pp, select, what)
3083 MAPSET(multiversionmap, p);
3088 solver_calculate_noobsmap(Pool *pool, Queue *job, Map *multiversionmap)
3090 solver_calculate_multiversionmap(pool, job, multiversionmap);
3094 * add a rule created by a job, record job number and weak flag
3097 solver_addjobrule(Solver *solv, Id p, Id p2, Id d, Id job, int weak)
3099 solver_addrule(solv, p, p2, d);
3100 queue_push(&solv->ruletojob, job);
3102 queue_push(&solv->weakruleq, solv->nrules - 1);
3106 add_cleandeps_updatepkg(Solver *solv, Id p)
3108 if (!solv->cleandeps_updatepkgs)
3110 solv->cleandeps_updatepkgs = solv_calloc(1, sizeof(Queue));
3111 queue_init(solv->cleandeps_updatepkgs);
3113 queue_pushunique(solv->cleandeps_updatepkgs, p);
3117 add_update_target(Solver *solv, Id p, Id how)
3119 Pool *pool = solv->pool;
3120 Solvable *s = pool->solvables + p;
3121 Repo *installed = solv->installed;
3123 if (!solv->update_targets)
3125 solv->update_targets = solv_calloc(1, sizeof(Queue));
3126 queue_init(solv->update_targets);
3128 if (s->repo == installed)
3130 queue_push2(solv->update_targets, p, p);
3133 FOR_PROVIDES(pi, pip, s->name)
3135 Solvable *si = pool->solvables + pi;
3136 if (si->repo != installed || si->name != s->name)
3138 if (how & SOLVER_FORCEBEST)
3140 if (!solv->bestupdatemap.size)
3141 map_grow(&solv->bestupdatemap, installed->end - installed->start);
3142 MAPSET(&solv->bestupdatemap, pi - installed->start);
3144 if (how & SOLVER_CLEANDEPS)
3145 add_cleandeps_updatepkg(solv, pi);
3146 queue_push2(solv->update_targets, pi, p);
3147 /* check if it's ok to keep the installed package */
3148 if (s->evr == si->evr && solvable_identical(s, si))
3149 queue_push2(solv->update_targets, pi, pi);
3153 Id obs, *obsp = s->repo->idarraydata + s->obsoletes;
3154 while ((obs = *obsp++) != 0)
3156 FOR_PROVIDES(pi, pip, obs)
3158 Solvable *si = pool->solvables + pi;
3159 if (si->repo != installed)
3161 if (si->name == s->name)
3162 continue; /* already handled above */
3163 if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, si, obs))
3165 if (pool->obsoleteusescolors && !pool_colormatch(pool, s, si))
3167 if (how & SOLVER_FORCEBEST)
3169 if (!solv->bestupdatemap.size)
3170 map_grow(&solv->bestupdatemap, installed->end - installed->start);
3171 MAPSET(&solv->bestupdatemap, pi - installed->start);
3173 if (how & SOLVER_CLEANDEPS)
3174 add_cleandeps_updatepkg(solv, pi);
3175 queue_push2(solv->update_targets, pi, p);
3182 transform_update_targets_sortfn(const void *ap, const void *bp, void *dp)
3192 transform_update_targets(Solver *solv)
3194 Repo *installed = solv->installed;
3195 Queue *update_targets = solv->update_targets;
3197 Id p, q, lastp, lastq;
3199 if (!update_targets->count)
3201 queue_free(update_targets);
3202 solv->update_targets = solv_free(update_targets);
3205 if (update_targets->count > 2)
3206 solv_sort(update_targets->elements, update_targets->count >> 1, 2 * sizeof(Id), transform_update_targets_sortfn, solv);
3207 queue_insertn(update_targets, 0, installed->end - installed->start, 0);
3209 for (i = j = installed->end - installed->start; i < update_targets->count; i += 2)
3211 if ((p = update_targets->elements[i]) != lastp)
3213 if (!solv->updatemap.size)
3214 map_grow(&solv->updatemap, installed->end - installed->start);
3215 MAPSET(&solv->updatemap, p - installed->start);
3216 update_targets->elements[j++] = 0; /* finish old set */
3217 update_targets->elements[p - installed->start] = j; /* start new set */
3221 if ((q = update_targets->elements[i + 1]) != lastq)
3223 update_targets->elements[j++] = q;
3227 queue_truncate(update_targets, j);
3228 queue_push(update_targets, 0); /* finish last set */
3233 addedmap2deduceq(Solver *solv, Map *addedmap)
3235 Pool *pool = solv->pool;
3240 queue_empty(&solv->addedmap_deduceq);
3241 for (i = 2, j = solv->pkgrules_end - 1; i < pool->nsolvables && j > 0; j--)
3243 r = solv->rules + j;
3246 if ((r->d == 0 || r->d == -1) && r->w2 < 0)
3249 if (!MAPTST(addedmap, p))
3251 /* should never happen, but... */
3252 if (!solv->addedmap_deduceq.count || solv->addedmap_deduceq.elements[solv->addedmap_deduceq.count - 1] != -p)
3253 queue_push(&solv->addedmap_deduceq, -p);
3257 if (MAPTST(addedmap, i))
3258 queue_push(&solv->addedmap_deduceq, i);
3262 for (; i < pool->nsolvables; i++)
3263 if (MAPTST(addedmap, i))
3264 queue_push(&solv->addedmap_deduceq, i);
3266 for (i = 2; i < pool->nsolvables; i++)
3267 if (MAPTST(addedmap, i))
3272 deduceq2addedmap(Solver *solv, Map *addedmap)
3277 for (j = solv->pkgrules_end - 1; j > 0; j--)
3279 r = solv->rules + j;
3280 if (r->d < 0 && r->p)
3281 solver_enablerule(solv, r);
3284 if ((r->d == 0 || r->d == -1) && r->w2 < 0)
3287 MAPSET(addedmap, p);
3289 for (j = 0; j < solv->addedmap_deduceq.count; j++)
3291 p = solv->addedmap_deduceq.elements[j];
3293 MAPSET(addedmap, p);
3295 MAPCLR(addedmap, p);
3299 #ifdef ENABLE_COMPLEX_DEPS
3301 add_complex_jobrules(Solver *solv, Id dep, int flags, int jobidx, int weak)
3303 Pool *pool = solv->pool;
3308 i = pool_normalize_complex_dep(pool, dep, &bq, flags | CPLXDEPS_EXPAND);
3309 if (i == 0 || i == 1)
3313 solver_addjobrule(solv, -SYSTEMSOLVABLE, 0, 0, jobidx, weak);
3316 for (i = 0; i < bq.count; i++)
3318 if (!bq.elements[i])
3320 for (j = 0; bq.elements[i + j + 1]; j++)
3323 solver_addjobrule(solv, bq.elements[i], 0, pool_ids2whatprovides(pool, bq.elements + i + 1, j), jobidx, weak);
3325 solver_addjobrule(solv, bq.elements[i], bq.elements[i + 1], 0, jobidx, weak);
3333 /* sort by package id, last entry wins */
3335 setup_favormaps_cmp(const void *ap, const void *bp, void *dp)
3337 const Id *a = ap, *b = bp;
3340 return (b[1] < 0 ? -b[1] : b[1]) - (a[1] < 0 ? -a[1] : a[1]);
3344 setup_favormaps(Solver *solv)
3346 Queue *q = solv->favorq;
3347 Pool *pool = solv->pool;
3351 solv_sort(q->elements, q->count / 2, 2 * sizeof(Id), setup_favormaps_cmp, solv);
3352 map_grow(&solv->favormap, pool->nsolvables);
3353 for (i = 0; i < q->count; i += 2)
3355 Id p = q->elements[i];
3359 MAPSET(&solv->favormap, p);
3360 if (q->elements[i + 1] < 0)
3362 if (!solv->isdisfavormap.size)
3363 map_grow(&solv->isdisfavormap, pool->nsolvables);
3364 MAPSET(&solv->isdisfavormap, p);
3376 solver_solve(Solver *solv, Queue *job)
3378 Pool *pool = solv->pool;
3379 Repo *installed = solv->installed;
3381 int oldnrules, initialnrules;
3382 Map addedmap; /* '1' == have pkg-rules for solvable */
3383 Map installcandidatemap;
3384 Id how, what, select, name, weak, p, pp, d;
3386 Solvable *s, *name_s;
3388 int now, solve_start;
3389 int needduprules = 0;
3390 int hasbestinstalljob = 0;
3392 solve_start = solv_timems(0);
3394 /* log solver options */
3395 POOL_DEBUG(SOLV_DEBUG_STATS, "solver started\n");
3396 POOL_DEBUG(SOLV_DEBUG_STATS, "dosplitprovides=%d, noupdateprovide=%d, noinfarchcheck=%d\n", solv->dosplitprovides, solv->noupdateprovide, solv->noinfarchcheck);
3397 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);
3398 POOL_DEBUG(SOLV_DEBUG_STATS, "promoteepoch=%d, forbidselfconflicts=%d\n", pool->promoteepoch, pool->forbidselfconflicts);
3399 POOL_DEBUG(SOLV_DEBUG_STATS, "obsoleteusesprovides=%d, implicitobsoleteusesprovides=%d, obsoleteusescolors=%d, implicitobsoleteusescolors=%d\n", pool->obsoleteusesprovides, pool->implicitobsoleteusesprovides, pool->obsoleteusescolors, pool->implicitobsoleteusescolors);
3400 POOL_DEBUG(SOLV_DEBUG_STATS, "dontinstallrecommended=%d, addalreadyrecommended=%d\n", solv->dontinstallrecommended, solv->addalreadyrecommended);
3402 /* create whatprovides if not already there */
3403 if (!pool->whatprovides)
3404 pool_createwhatprovides(pool);
3406 /* create obsolete index */
3407 policy_create_obsolete_index(solv);
3410 queue_free(&solv->job);
3411 queue_init_clone(&solv->job, job);
3412 solv->pooljobcnt = pool->pooljobs.count;
3413 if (pool->pooljobs.count)
3414 queue_insertn(&solv->job, 0, pool->pooljobs.count, pool->pooljobs.elements);
3417 /* free old stuff in case we re-run a solver */
3418 queuep_free(&solv->update_targets);
3419 queuep_free(&solv->cleandeps_updatepkgs);
3420 queue_empty(&solv->ruleassertions);
3421 solv->bestrules_pkg = solv_free(solv->bestrules_pkg);
3422 solv->yumobsrules_info = solv_free(solv->yumobsrules_info);
3423 solv->choicerules_ref = solv_free(solv->choicerules_ref);
3424 if (solv->noupdate.size)
3425 map_empty(&solv->noupdate);
3426 map_zerosize(&solv->multiversion);
3427 solv->updatemap_all = 0;
3428 map_zerosize(&solv->updatemap);
3429 solv->bestupdatemap_all = 0;
3430 map_zerosize(&solv->bestupdatemap);
3431 solv->fixmap_all = 0;
3432 map_zerosize(&solv->fixmap);
3433 map_zerosize(&solv->dupmap);
3434 map_zerosize(&solv->dupinvolvedmap);
3435 solv->process_orphans = 0;
3436 solv->droporphanedmap_all = 0;
3437 map_zerosize(&solv->droporphanedmap);
3438 solv->allowuninstall_all = 0;
3439 map_zerosize(&solv->allowuninstallmap);
3440 map_zerosize(&solv->cleandepsmap);
3441 map_zerosize(&solv->weakrulemap);
3442 map_zerosize(&solv->favormap);
3443 map_zerosize(&solv->isdisfavormap);
3444 queue_empty(&solv->weakruleq);
3445 solv->watches = solv_free(solv->watches);
3446 queue_empty(&solv->ruletojob);
3447 if (solv->decisionq.count)
3448 memset(solv->decisionmap, 0, pool->nsolvables * sizeof(Id));
3449 queue_empty(&solv->decisionq);
3450 queue_empty(&solv->decisionq_why);
3451 queue_empty(&solv->decisionq_reason);
3452 queue_empty(&solv->learnt_why);
3453 queue_empty(&solv->learnt_pool);
3454 queue_empty(&solv->branches);
3455 solv->propagate_index = 0;
3456 queue_empty(&solv->problems);
3457 queue_empty(&solv->solutions);
3458 queue_empty(&solv->orphaned);
3459 solv->stats_learned = solv->stats_unsolvable = 0;
3460 if (solv->recommends_index)
3462 map_empty(&solv->recommendsmap);
3463 map_empty(&solv->suggestsmap);
3464 queuep_free(&solv->recommendscplxq);
3465 queuep_free(&solv->suggestscplxq);
3466 solv->recommends_index = 0;
3468 queuep_free(&solv->brokenorphanrules);
3469 solv->specialupdaters = solv_free(solv->specialupdaters);
3473 * create basic rule set of all involved packages
3474 * use addedmap bitmap to make sure we don't create rules twice
3477 /* create multiversion map if needed */
3478 solver_calculate_multiversionmap(pool, job, &solv->multiversion);
3480 map_init(&addedmap, pool->nsolvables);
3481 MAPSET(&addedmap, SYSTEMSOLVABLE);
3483 map_init(&installcandidatemap, pool->nsolvables);
3486 now = solv_timems(0);
3488 * create rules for all package that could be involved with the solving
3489 * so called: pkg rules
3492 initialnrules = solv->pkgrules_end ? solv->pkgrules_end : 1;
3493 if (initialnrules > 1)
3494 deduceq2addedmap(solv, &addedmap);
3495 if (solv->nrules != initialnrules)
3496 solver_shrinkrules(solv, initialnrules);
3497 solv->nrules = initialnrules;
3498 solv->lastpkgrule = 0;
3499 solv->pkgrules_end = 0;
3503 /* check for update/verify jobs as they need to be known early */
3504 /* also setup the droporphaned map, we need it when creating update rules */
3505 for (i = 0; i < job->count; i += 2)
3507 how = job->elements[i];
3508 what = job->elements[i + 1];
3509 select = how & SOLVER_SELECTMASK;
3510 switch (how & SOLVER_JOBMASK)
3513 if (select == SOLVER_SOLVABLE_ALL || (select == SOLVER_SOLVABLE_REPO && installed && what == installed->repoid))
3514 solv->fixmap_all = 1;
3515 FOR_JOB_SELECT(p, pp, select, what)
3517 s = pool->solvables + p;
3518 if (s->repo != installed)
3520 if (!solv->fixmap.size)
3521 map_grow(&solv->fixmap, installed->end - installed->start);
3522 MAPSET(&solv->fixmap, p - installed->start);
3526 if (select == SOLVER_SOLVABLE_ALL)
3528 solv->updatemap_all = 1;
3529 if (how & SOLVER_FORCEBEST)
3530 solv->bestupdatemap_all = 1;
3531 if (how & SOLVER_CLEANDEPS)
3533 FOR_REPO_SOLVABLES(installed, p, s)
3534 add_cleandeps_updatepkg(solv, p);
3537 else if (select == SOLVER_SOLVABLE_REPO)
3539 Repo *repo = pool_id2repo(pool, what);
3542 if (repo == installed && !(how & SOLVER_TARGETED))
3544 solv->updatemap_all = 1;
3545 if (how & SOLVER_FORCEBEST)
3546 solv->bestupdatemap_all = 1;
3547 if (how & SOLVER_CLEANDEPS)
3549 FOR_REPO_SOLVABLES(installed, p, s)
3550 add_cleandeps_updatepkg(solv, p);
3554 if (solv->noautotarget && !(how & SOLVER_TARGETED))
3556 /* targeted update */
3557 FOR_REPO_SOLVABLES(repo, p, s)
3558 add_update_target(solv, p, how);
3562 if (!(how & SOLVER_TARGETED))
3565 FOR_JOB_SELECT(p, pp, select, what)
3567 s = pool->solvables + p;
3568 if (s->repo != installed)
3570 if (!solv->updatemap.size)
3571 map_grow(&solv->updatemap, installed->end - installed->start);
3572 MAPSET(&solv->updatemap, p - installed->start);
3573 if (how & SOLVER_FORCEBEST)
3575 if (!solv->bestupdatemap.size)
3576 map_grow(&solv->bestupdatemap, installed->end - installed->start);
3577 MAPSET(&solv->bestupdatemap, p - installed->start);
3579 if (how & SOLVER_CLEANDEPS)
3580 add_cleandeps_updatepkg(solv, p);
3583 if (!targeted || solv->noautotarget)
3586 FOR_JOB_SELECT(p, pp, select, what)
3587 add_update_target(solv, p, how);
3590 case SOLVER_DROP_ORPHANED:
3591 if (select == SOLVER_SOLVABLE_ALL || (select == SOLVER_SOLVABLE_REPO && what == installed->repoid))
3592 solv->droporphanedmap_all = 1;
3593 FOR_JOB_SELECT(p, pp, select, what)
3595 s = pool->solvables + p;
3596 if (s->repo != installed)
3598 if (!solv->droporphanedmap.size)
3599 map_grow(&solv->droporphanedmap, installed->end - installed->start);
3600 MAPSET(&solv->droporphanedmap, p - installed->start);
3603 case SOLVER_ALLOWUNINSTALL:
3604 if (select == SOLVER_SOLVABLE_ALL || (select == SOLVER_SOLVABLE_REPO && installed && what == installed->repoid))
3605 solv->allowuninstall_all = 1;
3606 FOR_JOB_SELECT(p, pp, select, what)
3608 s = pool->solvables + p;
3609 if (s->repo != installed)
3611 if (!solv->allowuninstallmap.size)
3612 map_grow(&solv->allowuninstallmap, installed->end - installed->start);
3613 MAPSET(&solv->allowuninstallmap, p - installed->start);
3621 if (solv->update_targets)
3622 transform_update_targets(solv);
3624 oldnrules = solv->nrules;
3625 FOR_REPO_SOLVABLES(installed, p, s)
3626 solver_addpkgrulesforsolvable(solv, s, &addedmap);
3627 POOL_DEBUG(SOLV_DEBUG_STATS, "added %d pkg rules for installed solvables\n", solv->nrules - oldnrules);
3628 oldnrules = solv->nrules;
3629 FOR_REPO_SOLVABLES(installed, p, s)
3630 solver_addpkgrulesforupdaters(solv, s, &addedmap, 1);
3631 POOL_DEBUG(SOLV_DEBUG_STATS, "added %d pkg rules for updaters of installed solvables\n", solv->nrules - oldnrules);
3635 * create rules for all packages involved in the job
3636 * (to be installed or removed)
3639 oldnrules = solv->nrules;
3640 for (i = 0; i < job->count; i += 2)
3642 how = job->elements[i];
3643 what = job->elements[i + 1];
3644 select = how & SOLVER_SELECTMASK;
3646 switch (how & SOLVER_JOBMASK)
3648 case SOLVER_INSTALL:
3649 FOR_JOB_SELECT(p, pp, select, what)
3651 MAPSET(&installcandidatemap, p);
3652 solver_addpkgrulesforsolvable(solv, pool->solvables + p, &addedmap);
3655 case SOLVER_DISTUPGRADE:
3657 if (select == SOLVER_SOLVABLE_ALL)
3658 solv->process_orphans = 1;
3664 POOL_DEBUG(SOLV_DEBUG_STATS, "added %d pkg rules for packages involved in a job\n", solv->nrules - oldnrules);
3668 * add rules for suggests, enhances
3670 oldnrules = solv->nrules;
3671 solver_addpkgrulesforweak(solv, &addedmap);
3672 POOL_DEBUG(SOLV_DEBUG_STATS, "added %d pkg rules because of weak dependencies\n", solv->nrules - oldnrules);
3674 #ifdef ENABLE_LINKED_PKGS
3675 oldnrules = solv->nrules;
3676 solver_addpkgrulesforlinked(solv, &addedmap);
3677 POOL_DEBUG(SOLV_DEBUG_STATS, "added %d pkg rules because of linked packages\n", solv->nrules - oldnrules);
3681 * first pass done, we now have all the pkg rules we need.
3682 * unify existing rules before going over all job rules and
3684 * at this point the system is always solvable,
3685 * as an empty system (remove all packages) is a valid solution
3688 IF_POOLDEBUG (SOLV_DEBUG_STATS)
3690 int possible = 0, installable = 0;
3691 for (i = 1; i < pool->nsolvables; i++)
3693 if (pool_installable(pool, pool->solvables + i))
3695 if (MAPTST(&addedmap, i))
3698 POOL_DEBUG(SOLV_DEBUG_STATS, "%d of %d installable solvables considered for solving\n", possible, installable);
3701 if (solv->nrules > initialnrules)
3702 solver_unifyrules(solv); /* remove duplicate pkg rules */
3703 solv->pkgrules_end = solv->nrules; /* mark end of pkg rules */
3704 solv->lastpkgrule = 0;
3706 if (solv->nrules > initialnrules)
3707 addedmap2deduceq(solv, &addedmap); /* so that we can recreate the addedmap */
3709 POOL_DEBUG(SOLV_DEBUG_STATS, "pkg rule memory used: %d K\n", solv->nrules * (int)sizeof(Rule) / 1024);
3710 POOL_DEBUG(SOLV_DEBUG_STATS, "pkg rule creation took %d ms\n", solv_timems(now));
3712 /* create dup maps if needed. We need the maps early to create our
3715 solver_createdupmaps(solv);
3718 * create feature rules
3720 * foreach installed:
3721 * create assertion (keep installed, if no update available)
3723 * create update rule (A|update1(A)|update2(A)|...)
3725 * those are used later on to keep a version of the installed packages in
3729 solv->featurerules = solv->nrules; /* mark start of feature rules */
3732 /* foreach possibly installed solvable */
3733 for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
3735 if (s->repo != installed)
3737 solver_addrule(solv, 0, 0, 0); /* create dummy rule */
3740 solver_addfeaturerule(solv, s);
3742 /* make sure we accounted for all rules */
3743 assert(solv->nrules - solv->featurerules == installed->end - installed->start);
3745 solv->featurerules_end = solv->nrules;
3748 * Add update rules for installed solvables
3750 * almost identical to feature rules
3751 * except that downgrades/archchanges/vendorchanges are not allowed
3754 solv->updaterules = solv->nrules;
3757 { /* foreach installed solvables */
3758 /* we create all update rules, but disable some later on depending on the job */
3759 for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
3763 if (s->repo != installed)
3765 solver_addrule(solv, 0, 0, 0); /* create dummy rule */
3768 solver_addupdaterule(solv, s);
3770 * check for and remove duplicate
3772 r = solv->rules + solv->nrules - 1; /* r: update rule */
3773 sr = r - (installed->end - installed->start); /* sr: feature rule */
3777 memset(sr, 0, sizeof(*sr)); /* no feature rules without update rules */
3780 /* it's also orphaned if the feature rule consists just of the installed package */
3781 if (!solv->process_orphans && sr->p == i && !sr->d && !sr->w2)
3782 queue_push(&solv->orphaned, i);
3784 if (!solver_rulecmp(solv, r, sr))
3785 memset(sr, 0, sizeof(*sr)); /* delete unneeded feature rule */
3787 solver_disablerule(solv, sr); /* disable feature rule for now */
3789 /* consistency check: we added a rule for _every_ installed solvable */
3790 assert(solv->nrules - solv->updaterules == installed->end - installed->start);
3792 solv->updaterules_end = solv->nrules;
3796 * now add all job rules
3799 solv->jobrules = solv->nrules;
3800 for (i = 0; i < job->count; i += 2)
3802 oldnrules = solv->nrules;
3804 if (i && i == solv->pooljobcnt)
3805 POOL_DEBUG(SOLV_DEBUG_JOB, "end of pool jobs\n");
3806 how = job->elements[i];
3807 what = job->elements[i + 1];
3808 weak = how & SOLVER_WEAK;
3809 select = how & SOLVER_SELECTMASK;
3810 switch (how & SOLVER_JOBMASK)
3812 case SOLVER_INSTALL:
3813 POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sinstall %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
3814 if ((how & SOLVER_CLEANDEPS) != 0 && !solv->cleandepsmap.size && installed)
3815 map_grow(&solv->cleandepsmap, installed->end - installed->start);
3816 if (select == SOLVER_SOLVABLE)
3821 #ifdef ENABLE_COMPLEX_DEPS
3822 else if ((select == SOLVER_SOLVABLE_PROVIDES || select == SOLVER_SOLVABLE_NAME) && pool_is_complex_dep(pool, what))
3824 if (add_complex_jobrules(solv, what, select == SOLVER_SOLVABLE_NAME ? CPLXDEPS_NAME : 0, i, weak))
3825 if (how & SOLVER_FORCEBEST)
3826 hasbestinstalljob = 1;
3833 FOR_JOB_SELECT(p, pp, select, what)
3837 if (select == SOLVER_SOLVABLE_ONE_OF)
3838 break; /* ignore empty installs */
3839 /* no candidate found or unsupported, make this an impossible rule */
3840 queue_push(&q, -SYSTEMSOLVABLE);
3842 p = queue_shift(&q); /* get first candidate */
3843 d = !q.count ? 0 : pool_queuetowhatprovides(pool, &q); /* internalize */
3845 /* force install of namespace supplements hack */
3846 if (select == SOLVER_SOLVABLE_PROVIDES && !d && (p == SYSTEMSOLVABLE || p == -SYSTEMSOLVABLE) && ISRELDEP(what))
3848 Reldep *rd = GETRELDEP(pool, what);
3849 if (rd->flags == REL_NAMESPACE)
3852 if (!solv->installsuppdepq)
3854 solv->installsuppdepq = solv_calloc(1, sizeof(Queue));
3855 queue_init(solv->installsuppdepq);
3857 queue_pushunique(solv->installsuppdepq, rd->evr == 0 ? rd->name : what);
3860 solver_addjobrule(solv, p, 0, d, i, weak);
3861 if (how & SOLVER_FORCEBEST)
3862 hasbestinstalljob = 1;
3865 POOL_DEBUG(SOLV_DEBUG_JOB, "job: %s%serase %s\n", weak ? "weak " : "", how & SOLVER_CLEANDEPS ? "clean deps " : "", solver_select2str(pool, select, what));
3866 if ((how & SOLVER_CLEANDEPS) != 0 && !solv->cleandepsmap.size && installed)
3867 map_grow(&solv->cleandepsmap, installed->end - installed->start);
3868 /* specific solvable: by id or by nevra */
3869 name = (select == SOLVER_SOLVABLE || (select == SOLVER_SOLVABLE_NAME && ISRELDEP(what))) ? 0 : -1;
3871 if (select == SOLVER_SOLVABLE_ALL) /* hmmm ;) */
3873 FOR_POOL_SOLVABLES(p)
3874 solver_addjobrule(solv, -p, 0, 0, i, weak);
3876 else if (select == SOLVER_SOLVABLE_REPO)
3878 Repo *repo = pool_id2repo(pool, what);
3881 FOR_REPO_SOLVABLES(repo, p, s)
3882 solver_addjobrule(solv, -p, 0, 0, i, weak);
3885 #ifdef ENABLE_COMPLEX_DEPS
3886 else if ((select == SOLVER_SOLVABLE_PROVIDES || select == SOLVER_SOLVABLE_NAME) && pool_is_complex_dep(pool, what))
3888 /* no special "erase a specific solvable" handling? */
3889 add_complex_jobrules(solv, what, select == SOLVER_SOLVABLE_NAME ? (CPLXDEPS_NAME | CPLXDEPS_TODNF | CPLXDEPS_INVERT) : (CPLXDEPS_TODNF | CPLXDEPS_INVERT), i, weak);
3893 FOR_JOB_SELECT(p, pp, select, what)
3895 s = pool->solvables + p;
3896 if (installed && s->repo == installed)
3898 name = !name ? s->name : -1;
3901 solver_addjobrule(solv, -p, 0, 0, i, weak);
3903 /* special case for "erase a specific solvable": we also
3904 * erase all other solvables with that name, so that they
3905 * don't get picked up as replacement.
3906 * name is > 0 if exactly one installed solvable matched.
3908 /* XXX: look also at packages that obsolete this package? */
3913 FOR_PROVIDES(p, pp, name)
3915 s = pool->solvables + p;
3916 if (s->name != name)
3918 /* keep other versions installed */
3919 if (s->repo == installed)
3921 /* keep installcandidates of other jobs */
3922 if (MAPTST(&installcandidatemap, p))
3924 if (pool->implicitobsoleteusescolors && !pool_colormatch(pool, name_s, s))
3926 /* don't add the same rule twice */
3927 for (j = oldnrules; j < k; j++)
3928 if (solv->rules[j].p == -p)
3931 solver_addjobrule(solv, -p, 0, 0, i, weak); /* remove by id */
3937 POOL_DEBUG(SOLV_DEBUG_JOB, "job: %supdate %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
3940 POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sverify %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
3942 case SOLVER_WEAKENDEPS:
3943 POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sweaken deps %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
3944 if (select != SOLVER_SOLVABLE)
3946 s = pool->solvables + what;
3947 weaken_solvable_deps(solv, what);
3949 case SOLVER_MULTIVERSION:
3950 POOL_DEBUG(SOLV_DEBUG_JOB, "job: %smultiversion %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
3953 POOL_DEBUG(SOLV_DEBUG_JOB, "job: %slock %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
3954 if (select == SOLVER_SOLVABLE_ALL)
3956 FOR_POOL_SOLVABLES(p)
3957 solver_addjobrule(solv, installed && pool->solvables[p].repo == installed ? p : -p, 0, 0, i, weak);
3959 else if (select == SOLVER_SOLVABLE_REPO)
3961 Repo *repo = pool_id2repo(pool, what);
3964 FOR_REPO_SOLVABLES(repo, p, s)
3965 solver_addjobrule(solv, installed && pool->solvables[p].repo == installed ? p : -p, 0, 0, i, weak);
3968 FOR_JOB_SELECT(p, pp, select, what)
3969 solver_addjobrule(solv, installed && pool->solvables[p].repo == installed ? p : -p, 0, 0, i, weak);
3971 case SOLVER_DISTUPGRADE:
3972 POOL_DEBUG(SOLV_DEBUG_JOB, "job: distupgrade %s\n", solver_select2str(pool, select, what));
3974 case SOLVER_DROP_ORPHANED:
3975 POOL_DEBUG(SOLV_DEBUG_JOB, "job: drop orphaned %s\n", solver_select2str(pool, select, what));
3977 case SOLVER_USERINSTALLED:
3978 POOL_DEBUG(SOLV_DEBUG_JOB, "job: user installed %s\n", solver_select2str(pool, select, what));
3980 case SOLVER_ALLOWUNINSTALL:
3981 POOL_DEBUG(SOLV_DEBUG_JOB, "job: allowuninstall %s\n", solver_select2str(pool, select, what));
3984 case SOLVER_DISFAVOR:
3985 POOL_DEBUG(SOLV_DEBUG_JOB, "job: %s %s\n", (how & SOLVER_JOBMASK) == SOLVER_FAVOR ? "favor" : "disfavor", solver_select2str(pool, select, what));
3986 FOR_JOB_SELECT(p, pp, select, what)
3991 solv->favorq = solv_calloc(1, sizeof(Queue));
3992 queue_init(solv->favorq);
3994 j = solv->favorq->count + 1;
3995 queue_push2(solv->favorq, p, (how & SOLVER_JOBMASK) == SOLVER_FAVOR ? j : -j);
3999 POOL_DEBUG(SOLV_DEBUG_JOB, "job: unknown job\n");
4003 IF_POOLDEBUG (SOLV_DEBUG_JOB)
4006 if (solv->nrules == oldnrules)
4007 POOL_DEBUG(SOLV_DEBUG_JOB, " - no rule created\n");
4008 for (j = oldnrules; j < solv->nrules; j++)
4010 POOL_DEBUG(SOLV_DEBUG_JOB, " - job ");
4011 solver_printrule(solv, SOLV_DEBUG_JOB, solv->rules + j);
4015 assert(solv->ruletojob.count == solv->nrules - solv->jobrules);
4016 solv->jobrules_end = solv->nrules;
4018 /* transform favorq into two maps */
4020 setup_favormaps(solv);
4022 /* now create infarch and dup rules */
4023 if (!solv->noinfarchcheck)
4025 solver_addinfarchrules(solv, &addedmap);
4027 if (pool->implicitobsoleteusescolors)
4029 /* currently doesn't work well with infarch rules, so make
4031 for (i = solv->infarchrules; i < solv->infarchrules_end; i++)
4032 queue_push(&solv->weakruleq, i);
4037 solv->infarchrules = solv->infarchrules_end = solv->nrules;
4039 if (solv->dupinvolvedmap_all || solv->dupinvolvedmap.size)
4040 solver_addduprules(solv, &addedmap);
4042 solv->duprules = solv->duprules_end = solv->nrules;
4044 #ifdef ENABLE_LINKED_PKGS
4045 if (solv->instbuddy && solv->updatemap.size)
4046 extend_updatemap_to_buddies(solv);
4049 if (solv->bestupdatemap_all || solv->bestupdatemap.size || hasbestinstalljob)
4050 solver_addbestrules(solv, hasbestinstalljob);
4052 solv->bestrules = solv->bestrules_end = solv->nrules;
4055 solver_freedupmaps(solv); /* no longer needed */
4057 if (solv->do_yum_obsoletes)
4058 solver_addyumobsrules(solv);
4060 solv->yumobsrules = solv->yumobsrules_end = solv->nrules;
4063 solver_addchoicerules(solv);
4065 solv->choicerules = solv->choicerules_end = solv->nrules;
4069 for (i = solv->featurerules; i < solv->nrules; i++)
4070 solver_printruleclass(solv, SOLV_DEBUG_RESULT, solv->rules + i);
4072 /* all rules created
4073 * --------------------------------------------------------------
4074 * prepare for solving
4077 /* free unneeded memory */
4078 map_free(&addedmap);
4079 map_free(&installcandidatemap);
4082 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);
4083 POOL_DEBUG(SOLV_DEBUG_STATS, "overall rule memory used: %d K\n", solv->nrules * (int)sizeof(Rule) / 1024);
4085 /* create weak map */
4086 if (solv->weakruleq.count || solv->recommendsruleq)
4088 map_grow(&solv->weakrulemap, solv->nrules);
4089 for (i = 0; i < solv->weakruleq.count; i++)
4091 p = solv->weakruleq.elements[i];
4092 MAPSET(&solv->weakrulemap, p);
4094 if (solv->recommendsruleq)
4096 for (i = 0; i < solv->recommendsruleq->count; i++)
4098 p = solv->recommendsruleq->elements[i];
4099 MAPSET(&solv->weakrulemap, p);
4104 /* enable cleandepsmap creation if we have updatepkgs */
4105 if (solv->cleandeps_updatepkgs && !solv->cleandepsmap.size)
4106 map_grow(&solv->cleandepsmap, installed->end - installed->start);
4108 if (solv->cleandeps_mistakes)
4110 queue_free(solv->cleandeps_mistakes);
4111 solv->cleandeps_mistakes = solv_free(solv->cleandeps_mistakes);
4114 /* all new rules are learnt after this point */
4115 solv->learntrules = solv->nrules;
4117 /* create watches chains */
4120 /* create assertion index. it is only used to speed up
4121 * makeruledecsions() a bit */
4122 for (i = 1, r = solv->rules + i; i < solv->nrules; i++, r++)
4123 if (r->p && !r->w2 && (r->d == 0 || r->d == -1))
4124 queue_push(&solv->ruleassertions, i);
4126 /* disable update rules that conflict with our job */
4127 solver_disablepolicyrules(solv);
4129 /* break orphans if requested */
4130 if (solv->process_orphans && solv->orphaned.count && solv->break_orphans)
4131 solver_breakorphans(solv);
4134 * ********************************************
4136 * ********************************************
4139 now = solv_timems(0);
4140 solver_run_sat(solv, 1, solv->dontinstallrecommended ? 0 : 1);
4141 POOL_DEBUG(SOLV_DEBUG_STATS, "solver took %d ms\n", solv_timems(now));
4144 * prepare solution queue if there were problems
4146 solver_prepare_solutions(solv);
4148 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);
4149 POOL_DEBUG(SOLV_DEBUG_STATS, "solver_solve took %d ms\n", solv_timems(solve_start));
4151 /* return number of problems */
4152 return solv->problems.count ? solv->problems.count / 2 : 0;
4156 solver_create_transaction(Solver *solv)
4158 return transaction_create_decisionq(solv->pool, &solv->decisionq, &solv->multiversion);
4161 void solver_get_orphaned(Solver *solv, Queue *orphanedq)
4163 queue_free(orphanedq);
4164 queue_init_clone(orphanedq, &solv->orphaned);
4167 void solver_get_cleandeps(Solver *solv, Queue *cleandepsq)
4169 Pool *pool = solv->pool;
4170 Repo *installed = solv->installed;
4175 queue_empty(cleandepsq);
4176 if (!installed || !solv->cleandepsmap.size)
4178 FOR_REPO_SOLVABLES(installed, p, s)
4180 if (!MAPTST(&solv->cleandepsmap, p - installed->start) || solv->decisionmap[p] >= 0)
4182 /* now check the update rule */
4183 r = solv->rules + solv->updaterules + (p - solv->installed->start);
4186 FOR_RULELITERALS(pr, pp, r)
4187 if (solv->decisionmap[pr] > 0)
4192 queue_push(cleandepsq, p);
4196 void solver_get_recommendations(Solver *solv, Queue *recommendationsq, Queue *suggestionsq, int noselected)
4198 Pool *pool = solv->pool;
4199 Queue redoq, disabledq;
4205 if (!recommendationsq && !suggestionsq)
4208 map_init(&obsmap, pool->nsolvables);
4209 if (solv->installed)
4211 Id obs, *obsp, p, po, ppo;
4212 for (p = solv->installed->start; p < solv->installed->end; p++)
4214 s = pool->solvables + p;
4215 if (s->repo != solv->installed || !s->obsoletes)
4217 if (solv->decisionmap[p] <= 0)
4219 if (solv->multiversion.size && MAPTST(&solv->multiversion, p))
4221 obsp = s->repo->idarraydata + s->obsoletes;
4222 /* foreach obsoletes */
4223 while ((obs = *obsp++) != 0)
4224 FOR_PROVIDES(po, ppo, obs)
4225 MAPSET(&obsmap, po);
4230 queue_init(&disabledq);
4232 /* disable all erase jobs (including weak "keep uninstalled" rules) */
4233 for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++)
4235 if (r->d < 0) /* disabled ? */
4237 if (r->p >= 0) /* install job? */
4239 queue_push(&disabledq, i);
4240 solver_disablerule(solv, r);
4246 enabledisablelearntrules(solv);
4247 removedisabledconflicts(solv, &redoq);
4251 * find recommended packages
4253 if (recommendationsq)
4255 Id rec, *recp, p, pp;
4257 queue_empty(recommendationsq);
4258 /* create map of all recommened packages */
4259 solv->recommends_index = -1;
4260 MAPZERO(&solv->recommendsmap);
4262 /* put all packages the solver already chose in the map */
4263 for (i = 1; i < solv->decisionq.count; i++)
4264 if ((p = solv->decisionq.elements[i]) > 0 && solv->decisionq_why.elements[i] == 0)
4266 if (solv->decisionq_reason.elements[solv->decisionmap[p]] == SOLVER_REASON_WEAKDEP)
4267 MAPSET(&solv->recommendsmap, p);
4270 for (i = 0; i < solv->decisionq.count; i++)
4272 p = solv->decisionq.elements[i];
4275 s = pool->solvables + p;
4278 recp = s->repo->idarraydata + s->recommends;
4279 while ((rec = *recp++) != 0)
4281 #ifdef ENABLE_COMPLEX_DEPS
4282 if (pool_is_complex_dep(pool, rec))
4284 do_complex_recommendations(solv, rec, &solv->recommendsmap, noselected);
4288 FOR_PROVIDES(p, pp, rec)
4289 if (solv->decisionmap[p] > 0)
4295 FOR_PROVIDES(p, pp, rec)
4296 if (solv->decisionmap[p] > 0)
4297 MAPSET(&solv->recommendsmap, p);
4299 continue; /* p != 0: already fulfilled */
4301 FOR_PROVIDES(p, pp, rec)
4302 MAPSET(&solv->recommendsmap, p);
4306 for (i = 1; i < pool->nsolvables; i++)
4308 if (solv->decisionmap[i] < 0)
4310 if (solv->decisionmap[i] > 0 && noselected)
4312 if (MAPTST(&obsmap, i))
4314 s = pool->solvables + i;
4315 if (!MAPTST(&solv->recommendsmap, i))
4317 if (!s->supplements)
4319 if (!pool_installable(pool, s))
4321 if (!solver_is_supplementing(solv, s))
4324 queue_push(recommendationsq, i);
4326 /* we use MODE_SUGGEST here so that repo prio is ignored */
4327 policy_filter_unwanted(solv, recommendationsq, POLICY_MODE_SUGGEST);
4331 * find suggested packages
4336 Id sug, *sugp, p, pp;
4338 queue_empty(suggestionsq);
4339 /* create map of all suggests that are still open */
4340 solv->recommends_index = -1;
4341 MAPZERO(&solv->suggestsmap);
4342 for (i = 0; i < solv->decisionq.count; i++)
4344 p = solv->decisionq.elements[i];
4347 s = pool->solvables + p;
4350 sugp = s->repo->idarraydata + s->suggests;
4351 while ((sug = *sugp++) != 0)
4353 #ifdef ENABLE_COMPLEX_DEPS
4354 if (pool_is_complex_dep(pool, sug))
4356 do_complex_recommendations(solv, sug, &solv->suggestsmap, noselected);
4360 FOR_PROVIDES(p, pp, sug)
4361 if (solv->decisionmap[p] > 0)
4367 FOR_PROVIDES(p, pp, sug)
4368 if (solv->decisionmap[p] > 0)
4369 MAPSET(&solv->suggestsmap, p);
4371 continue; /* already fulfilled */
4373 FOR_PROVIDES(p, pp, sug)
4374 MAPSET(&solv->suggestsmap, p);
4378 for (i = 1; i < pool->nsolvables; i++)
4380 if (solv->decisionmap[i] < 0)
4382 if (solv->decisionmap[i] > 0 && noselected)
4384 if (MAPTST(&obsmap, i))
4386 s = pool->solvables + i;
4387 if (!MAPTST(&solv->suggestsmap, i))
4391 if (!pool_installable(pool, s))
4393 if (!solver_is_enhancing(solv, s))
4396 queue_push(suggestionsq, i);
4398 policy_filter_unwanted(solv, suggestionsq, POLICY_MODE_SUGGEST);
4401 /* undo removedisabledconflicts */
4403 undo_removedisabledconflicts(solv, &redoq);
4406 /* undo job rule disabling */
4407 for (i = 0; i < disabledq.count; i++)
4408 solver_enablerule(solv, solv->rules + disabledq.elements[i]);
4409 queue_free(&disabledq);
4414 /***********************************************************************/
4415 /* disk usage computations */
4417 /*-------------------------------------------------------------------
4419 * calculate DU changes
4423 solver_calc_duchanges(Solver *solv, DUChanges *mps, int nmps)
4427 solver_create_state_maps(solv, &installedmap, 0);
4428 pool_calc_duchanges(solv->pool, &installedmap, mps, nmps);
4429 map_free(&installedmap);
4433 /*-------------------------------------------------------------------
4435 * calculate changes in install size
4439 solver_calc_installsizechange(Solver *solv)
4444 solver_create_state_maps(solv, &installedmap, 0);
4445 change = pool_calc_installsizechange(solv->pool, &installedmap);
4446 map_free(&installedmap);
4451 solver_create_state_maps(Solver *solv, Map *installedmap, Map *conflictsmap)
4453 pool_create_state_maps(solv->pool, &solv->decisionq, installedmap, conflictsmap);
4456 /*-------------------------------------------------------------------
4458 * decision introspection
4462 solver_get_decisionlevel(Solver *solv, Id p)
4464 return solv->decisionmap[p];
4468 solver_get_decisionqueue(Solver *solv, Queue *decisionq)
4470 queue_free(decisionq);
4471 queue_init_clone(decisionq, &solv->decisionq);
4475 solver_get_lastdecisionblocklevel(Solver *solv)
4478 if (solv->decisionq.count == 0)
4480 p = solv->decisionq.elements[solv->decisionq.count - 1];
4483 return solv->decisionmap[p] < 0 ? -solv->decisionmap[p] : solv->decisionmap[p];
4487 solver_get_decisionblock(Solver *solv, int level, Queue *decisionq)
4492 queue_empty(decisionq);
4493 for (i = 0; i < solv->decisionq.count; i++)
4495 p = solv->decisionq.elements[i];
4498 if (solv->decisionmap[p] == level || solv->decisionmap[p] == -level)
4501 if (i == solv->decisionq.count)
4503 for (i = 0; i < solv->decisionq.count; i++)
4505 p = solv->decisionq.elements[i];
4508 if (solv->decisionmap[p] == level || solv->decisionmap[p] == -level)
4509 queue_push(decisionq, p);
4516 solver_describe_decision(Solver *solv, Id p, Id *infop)
4523 if (!solv->decisionmap[p])
4524 return SOLVER_REASON_UNRELATED;
4525 pp = solv->decisionmap[p] < 0 ? -p : p;
4526 for (i = 0; i < solv->decisionq.count; i++)
4527 if (solv->decisionq.elements[i] == pp)
4529 if (i == solv->decisionq.count) /* just in case... */
4530 return SOLVER_REASON_UNRELATED;
4531 why = solv->decisionq_why.elements[i];
4533 *infop = why > 0 ? why : -why;
4535 return SOLVER_REASON_UNIT_RULE;
4536 i = solv->decisionmap[p] >= 0 ? solv->decisionmap[p] : -solv->decisionmap[p];
4537 return solv->decisionq_reason.elements[i];
4542 solver_describe_weakdep_decision(Solver *solv, Id p, Queue *whyq)
4544 Pool *pool = solv->pool;
4546 int level = solv->decisionmap[p];
4553 for (decisionno = 0; decisionno < solv->decisionq.count; decisionno++)
4554 if (solv->decisionq.elements[decisionno] == p)
4556 if (decisionno == solv->decisionq.count)
4558 i = solv->decisionmap[p] >= 0 ? solv->decisionmap[p] : -solv->decisionmap[p];
4559 if (solv->decisionq_reason.elements[i] != SOLVER_REASON_WEAKDEP)
4562 /* 1) list all packages that recommend us */
4563 for (i = 1; i < pool->nsolvables; i++)
4565 Id *recp, rec, pp2, p2;
4566 if (solv->decisionmap[i] <= 0 || solv->decisionmap[i] >= level)
4568 s = pool->solvables + i;
4571 if (!solv->addalreadyrecommended && s->repo == solv->installed)
4573 recp = s->repo->idarraydata + s->recommends;
4574 while ((rec = *recp++) != 0)
4577 FOR_PROVIDES(p2, pp2, rec)
4583 /* if p2 is already installed, this recommends is ignored */
4584 if (solv->decisionmap[p2] > 0 && solv->decisionmap[p2] < level)
4590 queue_push(whyq, SOLVER_REASON_RECOMMENDED);
4591 queue_push2(whyq, i, rec);
4595 /* 2) list all supplements */
4596 s = pool->solvables + p;
4597 if (s->supplements && level > 0)
4599 Id *supp, sup, pp2, p2;
4600 /* this is a hack. to use solver_dep_fulfilled we temporarily clear
4601 * everything above our level in the decisionmap */
4602 for (i = decisionno; i < solv->decisionq.count; i++ )
4604 p2 = solv->decisionq.elements[i];
4606 solv->decisionmap[p2] = -solv->decisionmap[p2];
4608 supp = s->repo->idarraydata + s->supplements;
4609 while ((sup = *supp++) != 0)
4610 if (solver_dep_fulfilled(solv, sup))
4613 /* let's see if this is an easy supp */
4614 FOR_PROVIDES(p2, pp2, sup)
4616 if (!solv->addalreadyrecommended && solv->installed)
4618 if (pool->solvables[p2].repo == solv->installed)
4621 if (solv->decisionmap[p2] > 0 && solv->decisionmap[p2] < level)
4623 queue_push(whyq, SOLVER_REASON_SUPPLEMENTED);
4624 queue_push2(whyq, p2, sup);
4630 /* hard case, just note dependency with no package */
4631 queue_push(whyq, SOLVER_REASON_SUPPLEMENTED);
4632 queue_push2(whyq, 0, sup);
4635 for (i = decisionno; i < solv->decisionq.count; i++)
4637 p2 = solv->decisionq.elements[i];
4639 solv->decisionmap[p2] = -solv->decisionmap[p2];
4645 pool_job2solvables(Pool *pool, Queue *pkgs, Id how, Id what)
4648 how &= SOLVER_SELECTMASK;
4650 if (how == SOLVER_SOLVABLE_ALL)
4652 FOR_POOL_SOLVABLES(p)
4653 queue_push(pkgs, p);
4655 else if (how == SOLVER_SOLVABLE_REPO)
4657 Repo *repo = pool_id2repo(pool, what);
4661 FOR_REPO_SOLVABLES(repo, p, s)
4662 queue_push(pkgs, p);
4667 FOR_JOB_SELECT(p, pp, how, what)
4668 queue_push(pkgs, p);
4673 pool_isemptyupdatejob(Pool *pool, Id how, Id what)
4676 Id select = how & SOLVER_SELECTMASK;
4677 if ((how & SOLVER_JOBMASK) != SOLVER_UPDATE)
4679 if (select == SOLVER_SOLVABLE_ALL || select == SOLVER_SOLVABLE_REPO)
4681 if (!pool->installed)
4683 FOR_JOB_SELECT(p, pp, select, what)
4684 if (pool->solvables[p].repo == pool->installed)
4687 FOR_JOB_SELECT(p, pp, select, what)
4689 Solvable *s = pool->solvables + p;
4690 FOR_PROVIDES(pi, pip, s->name)
4692 Solvable *si = pool->solvables + pi;
4693 if (si->repo != pool->installed || si->name != s->name)
4699 Id obs, *obsp = s->repo->idarraydata + s->obsoletes;
4700 while ((obs = *obsp++) != 0)
4702 FOR_PROVIDES(pi, pip, obs)
4704 Solvable *si = pool->solvables + pi;
4705 if (si->repo != pool->installed)
4707 if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, si, obs))
4709 if (pool->obsoleteusescolors && !pool_colormatch(pool, s, si))
4720 get_userinstalled_cmp(const void *ap, const void *bp, void *dp)
4722 return *(Id *)ap - *(Id *)bp;
4726 get_userinstalled_cmp_names(const void *ap, const void *bp, void *dp)
4729 return strcmp(pool_id2str(pool, *(Id *)ap), pool_id2str(pool, *(Id *)bp));
4733 get_userinstalled_cmp_namearch(const void *ap, const void *bp, void *dp)
4737 r = strcmp(pool_id2str(pool, ((Id *)ap)[0]), pool_id2str(pool, ((Id *)bp)[0]));
4740 return strcmp(pool_id2str(pool, ((Id *)ap)[1]), pool_id2str(pool, ((Id *)bp)[1]));
4744 get_userinstalled_sort_uniq(Pool *pool, Queue *q, int flags)
4746 Id lastp = -1, lasta = -1;
4748 if (q->count < ((flags & GET_USERINSTALLED_NAMEARCH) ? 4 : 2))
4750 if ((flags & GET_USERINSTALLED_NAMEARCH) != 0)
4751 solv_sort(q->elements, q->count / 2, 2 * sizeof(Id), get_userinstalled_cmp_namearch, pool);
4752 else if ((flags & GET_USERINSTALLED_NAMES) != 0)
4753 solv_sort(q->elements, q->count, sizeof(Id), get_userinstalled_cmp_names, pool);
4755 solv_sort(q->elements, q->count, sizeof(Id), get_userinstalled_cmp, 0);
4756 if ((flags & GET_USERINSTALLED_NAMEARCH) != 0)
4758 for (i = j = 0; i < q->count; i += 2)
4759 if (q->elements[i] != lastp || q->elements[i + 1] != lasta)
4761 q->elements[j++] = lastp = q->elements[i];
4762 q->elements[j++] = lasta = q->elements[i + 1];
4767 for (i = j = 0; i < q->count; i++)
4768 if (q->elements[i] != lastp)
4769 q->elements[j++] = lastp = q->elements[i];
4771 queue_truncate(q, j);
4775 namearch2solvables(Pool *pool, Queue *q, Queue *qout, int job)
4778 if (!pool->installed)
4780 for (i = 0; i < q->count; i += 2)
4782 Id p, pp, name = q->elements[i], arch = q->elements[i + 1];
4783 FOR_PROVIDES(p, pp, name)
4785 Solvable *s = pool->solvables + p;
4786 if (s->repo != pool->installed || s->name != name || (arch && s->arch != arch))
4789 queue_push(qout, job);
4790 queue_push(qout, p);
4796 solver_get_userinstalled(Solver *solv, Queue *q, int flags)
4798 Pool *pool = solv->pool;
4801 Repo *installed = solv->installed;
4805 map_init(&userinstalled, 0);
4807 /* first process jobs */
4808 for (i = 0; i < solv->job.count; i += 2)
4810 Id how = solv->job.elements[i];
4812 if (installed && (how & SOLVER_JOBMASK) == SOLVER_USERINSTALLED)
4814 if (!userinstalled.size)
4815 map_grow(&userinstalled, installed->end - installed->start);
4816 what = solv->job.elements[i + 1];
4817 select = how & SOLVER_SELECTMASK;
4818 if (select == SOLVER_SOLVABLE_ALL || (select == SOLVER_SOLVABLE_REPO && what == installed->repoid))
4820 FOR_REPO_SOLVABLES(installed, p, s)
4821 MAPSET(&userinstalled, p - installed->start);
4823 FOR_JOB_SELECT(p, pp, select, what)
4824 if (pool->solvables[p].repo == installed)
4825 MAPSET(&userinstalled, p - installed->start);
4828 if ((how & SOLVER_JOBMASK) != SOLVER_INSTALL)
4830 if ((how & SOLVER_NOTBYUSER) != 0)
4832 what = solv->job.elements[i + 1];
4833 select = how & SOLVER_SELECTMASK;
4834 FOR_JOB_SELECT(p, pp, select, what)
4835 if (solv->decisionmap[p] > 0)
4838 #ifdef ENABLE_LINKED_PKGS
4839 if (has_package_link(pool, pool->solvables + p))
4844 find_package_link(pool, pool->solvables + p, 0, &lq, 0, 0);
4845 for (j = 0; j < lq.count; j++)
4846 if (solv->decisionmap[lq.elements[j]] > 0)
4847 queue_push(q, lq.elements[j]);
4852 /* now process updates of userinstalled packages */
4853 if (installed && userinstalled.size)
4855 for (i = 1; i < solv->decisionq.count; i++)
4857 p = solv->decisionq.elements[i];
4860 s = pool->solvables + p;
4863 if (s->repo == installed)
4865 if (MAPTST(&userinstalled, p - installed->start))
4869 /* new package, check if we replace a userinstalled one */
4870 FOR_PROVIDES(p2, pp, s->name)
4872 Solvable *ps = pool->solvables + p2;
4873 if (p2 == p || ps->repo != installed || !MAPTST(&userinstalled, p2 - installed->start))
4875 if (!pool->implicitobsoleteusesprovides && s->name != ps->name)
4877 if (pool->implicitobsoleteusescolors && !pool_colormatch(pool, s, ps))
4882 if (!p2 && s->repo != installed && s->obsoletes)
4884 Id obs, *obsp = s->repo->idarraydata + s->obsoletes;
4885 while ((obs = *obsp++) != 0)
4887 FOR_PROVIDES(p2, pp, obs)
4889 Solvable *ps = pool->solvables + p2;
4890 if (p2 == p || ps->repo != installed || !MAPTST(&userinstalled, p2 - installed->start))
4892 if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
4894 if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
4905 map_free(&userinstalled);
4907 /* convert to desired output format */
4908 if ((flags & GET_USERINSTALLED_NAMEARCH) != 0)
4910 int qcount = q->count;
4911 queue_insertn(q, 0, qcount, 0);
4912 for (i = j = 0; i < qcount; i++)
4914 s = pool->solvables + q->elements[i + qcount];
4915 q->elements[j++] = s->name;
4916 q->elements[j++] = s->arch;
4919 else if ((flags & GET_USERINSTALLED_NAMES) != 0)
4921 for (i = 0; i < q->count; i++)
4923 s = pool->solvables + q->elements[i];
4924 q->elements[i] = s->name;
4927 /* sort and unify */
4928 get_userinstalled_sort_uniq(pool, q, flags);
4930 /* invert if asked for */
4931 if ((flags & GET_USERINSTALLED_INVERTED) != 0)
4933 /* first generate queue with all installed packages */
4936 for (i = 1; i < solv->decisionq.count; i++)
4938 p = solv->decisionq.elements[i];
4941 s = pool->solvables + p;
4944 if ((flags & GET_USERINSTALLED_NAMEARCH) != 0)
4945 queue_push2(&invq, s->name, s->arch);
4946 else if ((flags & GET_USERINSTALLED_NAMES) != 0)
4947 queue_push(&invq, s->name);
4949 queue_push(&invq, p);
4951 /* push q on invq, just in case... */
4952 queue_insertn(&invq, invq.count, q->count, q->elements);
4953 get_userinstalled_sort_uniq(pool, &invq, flags);
4954 /* subtract queues (easy as they are sorted and invq is a superset of q) */
4955 if ((flags & GET_USERINSTALLED_NAMEARCH) != 0)
4959 for (i = j = 0; i < invq.count; i += 2)
4960 if (invq.elements[i] == q->elements[j] && invq.elements[i + 1] == q->elements[j + 1])
4962 invq.elements[i] = invq.elements[i + 1] = 0;
4969 for (i = 0; i < invq.count; i += 2)
4970 if (invq.elements[i])
4971 queue_push2(q, invq.elements[i], invq.elements[i + 1]);
4977 for (i = j = 0; i < invq.count; i++)
4978 if (invq.elements[i] == q->elements[j])
4980 invq.elements[i] = 0;
4981 if (++j >= q->count)
4986 for (i = 0; i < invq.count; i++)
4987 if (invq.elements[i])
4988 queue_push(q, invq.elements[i]);
4995 pool_add_userinstalled_jobs(Pool *pool, Queue *q, Queue *job, int flags)
4999 if ((flags & GET_USERINSTALLED_INVERTED) != 0)
5005 if (!pool->installed)
5008 if ((flags & GET_USERINSTALLED_NAMEARCH) != 0)
5009 flags &= ~GET_USERINSTALLED_NAMES; /* just in case */
5010 FOR_REPO_SOLVABLES(pool->installed, p, s)
5011 queue_push(&invq, flags & GET_USERINSTALLED_NAMES ? s->name : p);
5012 if ((flags & GET_USERINSTALLED_NAMEARCH) != 0)
5014 /* for namearch we convert to packages */
5015 namearch2solvables(pool, q, &invq, 0);
5016 get_userinstalled_sort_uniq(pool, &invq, flags);
5017 namearch2solvables(pool, q, &invq, 0);
5022 queue_insertn(&invq, invq.count, q->count, q->elements);
5023 get_userinstalled_sort_uniq(pool, &invq, flags);
5024 /* now the fun part, add q again, sort, and remove all dups */
5025 queue_insertn(&invq, invq.count, q->count, q->elements);
5029 if ((flags & GET_USERINSTALLED_NAMES) != 0)
5030 solv_sort(invq.elements, invq.count, sizeof(Id), get_userinstalled_cmp_names, pool);
5032 solv_sort(invq.elements, invq.count, sizeof(Id), get_userinstalled_cmp, 0);
5036 for (i = 0; i < invq.count; i++)
5038 if (invq.elements[i] == lastid)
5044 queue_push2(job, SOLVER_USERINSTALLED | (flags & GET_USERINSTALLED_NAMES ? SOLVER_SOLVABLE_NAME : SOLVER_SOLVABLE), lastid);
5046 lastid = invq.elements[i];
5049 queue_push2(job, SOLVER_USERINSTALLED | (flags & GET_USERINSTALLED_NAMES ? SOLVER_SOLVABLE_NAME : SOLVER_SOLVABLE), lastid);
5054 if (flags & GET_USERINSTALLED_NAMEARCH)
5055 namearch2solvables(pool, q, job, SOLVER_USERINSTALLED | SOLVER_SOLVABLE);
5058 for (i = 0; i < q->count; i++)
5059 queue_push2(job, SOLVER_USERINSTALLED | (flags & GET_USERINSTALLED_NAMES ? SOLVER_SOLVABLE_NAME : SOLVER_SOLVABLE), q->elements[i]);
5065 solver_alternatives_count(Solver *solv)
5067 Id *elements = solv->branches.elements;
5069 for (res = 0, count = solv->branches.count; count; res++)
5070 count -= elements[count - 2];
5075 solver_get_alternative(Solver *solv, Id alternative, Id *idp, Id *fromp, Id *chosenp, Queue *choices, int *levelp)
5077 int cnt = solver_alternatives_count(solv);
5078 int count = solv->branches.count;
5079 Id *elements = solv->branches.elements;
5081 queue_empty(choices);
5082 if (alternative <= 0 || alternative > cnt)
5085 for (; cnt > alternative; cnt--)
5086 elements -= elements[-2];
5088 *levelp = elements[-1];
5090 *fromp = elements[-4];
5092 *idp = elements[-3];
5097 for (i = elements[-2]; i > 4; i--)
5099 Id p = -elements[-i];
5100 if (p > 0 && solv->decisionmap[p] == elements[-1] + 1)
5108 queue_insertn(choices, 0, elements[-2] - 4, elements - elements[-2]);
5109 return elements[-4] ? SOLVER_ALTERNATIVE_TYPE_RECOMMENDS : SOLVER_ALTERNATIVE_TYPE_RULE;
5113 solver_select2str(Pool *pool, Id select, Id what)
5117 select &= SOLVER_SELECTMASK;
5118 if (select == SOLVER_SOLVABLE)
5119 return pool_solvid2str(pool, what);
5120 if (select == SOLVER_SOLVABLE_NAME)
5121 return pool_dep2str(pool, what);
5122 if (select == SOLVER_SOLVABLE_PROVIDES)
5124 s = pool_dep2str(pool, what);
5125 b = pool_alloctmpspace(pool, 11 + strlen(s));
5126 sprintf(b, "providing %s", s);
5129 if (select == SOLVER_SOLVABLE_ONE_OF)
5133 while ((p = pool->whatprovidesdata[what++]) != 0)
5135 s = pool_solvid2str(pool, p);
5137 b = pool_tmpappend(pool, b, ", ", s);
5139 b = pool_tmpjoin(pool, s, 0, 0);
5140 pool_freetmpspace(pool, s);
5142 return b ? b : "nothing";
5144 if (select == SOLVER_SOLVABLE_REPO)
5146 b = pool_alloctmpspace(pool, 20);
5147 sprintf(b, "repo #%d", what);
5150 if (select == SOLVER_SOLVABLE_ALL)
5151 return "all packages";
5152 return "unknown job select";
5156 pool_job2str(Pool *pool, Id how, Id what, Id flagmask)
5158 Id select = how & SOLVER_SELECTMASK;
5159 const char *strstart = 0, *strend = 0;
5163 switch (how & SOLVER_JOBMASK)
5166 return "do nothing";
5167 case SOLVER_INSTALL:
5168 if (select == SOLVER_SOLVABLE && pool->installed && pool->solvables[what].repo == pool->installed)
5169 strstart = "keep ", strend = " installed";
5170 else if (select == SOLVER_SOLVABLE || select == SOLVER_SOLVABLE_NAME)
5171 strstart = "install ";
5172 else if (select == SOLVER_SOLVABLE_PROVIDES)
5173 strstart = "install a package ";
5175 strstart = "install one of ";
5178 if (select == SOLVER_SOLVABLE && !(pool->installed && pool->solvables[what].repo == pool->installed))
5179 strstart = "keep ", strend = " uninstalled";
5180 else if (select == SOLVER_SOLVABLE_PROVIDES)
5181 strstart = "deinstall all packages ";
5183 strstart = "deinstall ";
5186 strstart = "update ";
5188 case SOLVER_WEAKENDEPS:
5189 strstart = "weaken deps of ";
5191 case SOLVER_MULTIVERSION:
5192 strstart = "multi version ";
5197 case SOLVER_DISTUPGRADE:
5198 strstart = "dist upgrade ";
5201 strstart = "verify ";
5203 case SOLVER_DROP_ORPHANED:
5204 strstart = "deinstall ", strend = " if orphaned";
5206 case SOLVER_USERINSTALLED:
5207 strstart = "regard ", strend = " as userinstalled";
5209 case SOLVER_ALLOWUNINSTALL:
5210 strstart = "allow deinstallation of ";
5213 strstart = "favor ";
5215 case SOLVER_DISFAVOR:
5216 strstart = "disfavor ";
5219 strstart = "unknown job ";
5222 s = pool_tmpjoin(pool, strstart, solver_select2str(pool, select, what), strend);
5224 if ((how & ~(SOLVER_SELECTMASK|SOLVER_JOBMASK)) == 0)
5227 s = pool_tmpappend(pool, s, " ", 0);
5228 if (how & SOLVER_WEAK)
5229 s = pool_tmpappend(pool, s, ",weak", 0);
5230 if (how & SOLVER_ESSENTIAL)
5231 s = pool_tmpappend(pool, s, ",essential", 0);
5232 if (how & SOLVER_CLEANDEPS)
5233 s = pool_tmpappend(pool, s, ",cleandeps", 0);
5234 if (how & SOLVER_ORUPDATE)
5235 s = pool_tmpappend(pool, s, ",orupdate", 0);
5236 if (how & SOLVER_FORCEBEST)
5237 s = pool_tmpappend(pool, s, ",forcebest", 0);
5238 if (how & SOLVER_TARGETED)
5239 s = pool_tmpappend(pool, s, ",targeted", 0);
5240 if (how & SOLVER_SETEV)
5241 s = pool_tmpappend(pool, s, ",setev", 0);
5242 if (how & SOLVER_SETEVR)
5243 s = pool_tmpappend(pool, s, ",setevr", 0);
5244 if (how & SOLVER_SETARCH)
5245 s = pool_tmpappend(pool, s, ",setarch", 0);
5246 if (how & SOLVER_SETVENDOR)
5247 s = pool_tmpappend(pool, s, ",setvendor", 0);
5248 if (how & SOLVER_SETREPO)
5249 s = pool_tmpappend(pool, s, ",setrepo", 0);
5250 if (how & SOLVER_SETNAME)
5251 s = pool_tmpappend(pool, s, ",setname", 0);
5252 if (how & SOLVER_NOAUTOSET)
5253 s = pool_tmpappend(pool, s, ",noautoset", 0);
5254 if (s[o + 1] != ',')
5255 s = pool_tmpappend(pool, s, ",?", 0);
5257 return pool_tmpappend(pool, s, "]", 0);
5261 solver_alternative2str(Solver *solv, int type, Id id, Id from)
5263 Pool *pool = solv->pool;
5264 if (type == SOLVER_ALTERNATIVE_TYPE_RECOMMENDS)
5266 const char *s = pool_dep2str(pool, id);
5267 return pool_tmpappend(pool, s, ", recommended by ", pool_solvid2str(pool, from));
5269 if (type == SOLVER_ALTERNATIVE_TYPE_RULE)
5272 Id depfrom, depto, dep;
5274 if (solver_ruleclass(solv, id) == SOLVER_RULE_CHOICE)
5275 id = solver_rule2pkgrule(solv, id);
5276 rtype = solver_ruleinfo(solv, id, &depfrom, &depto, &dep);
5277 if ((rtype & SOLVER_RULE_TYPEMASK) == SOLVER_RULE_JOB)
5279 if ((depto & SOLVER_SELECTMASK) == SOLVER_SOLVABLE_PROVIDES)
5280 return pool_dep2str(pool, dep);
5281 return solver_select2str(pool, depto & SOLVER_SELECTMASK, dep);
5283 if (rtype == SOLVER_RULE_PKG_REQUIRES)
5285 const char *s = pool_dep2str(pool, dep);
5286 return pool_tmpappend(pool, s, ", required by ", pool_solvid2str(pool, depfrom));
5288 sprintf(buf, "Rule #%d", id);
5289 return pool_tmpjoin(pool, buf, 0, 0);
5291 return "unknown alternative type";