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
26 #include "solverdebug.h"
28 #define RULES_BLOCK 63
30 static void reenablepolicyrules(Solver *solv, Queue *job, int jobidx);
31 static void addrpmruleinfo(Solver *solv, Id p, Id d, int type, Id dep);
33 /********************************************************************
35 * dependency check helpers
39 /*-------------------------------------------------------------------
40 * handle split provides
44 solver_splitprovides(Solver *solv, Id dep)
46 Pool *pool = solv->pool;
51 if (!solv->dosplitprovides || !solv->installed)
55 rd = GETRELDEP(pool, dep);
56 if (rd->flags != REL_WITH)
58 FOR_PROVIDES(p, pp, dep)
60 s = pool->solvables + p;
61 if (s->repo == solv->installed && s->name == rd->name)
68 /*-------------------------------------------------------------------
69 * solver_dep_installed
73 solver_dep_installed(Solver *solv, Id dep)
76 Pool *pool = solv->pool;
81 Reldep *rd = GETRELDEP(pool, dep);
82 if (rd->flags == REL_AND)
84 if (!solver_dep_installed(solv, rd->name))
86 return solver_dep_installed(solv, rd->evr);
88 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
89 return solver_dep_installed(solv, rd->evr);
91 FOR_PROVIDES(p, pp, dep)
93 if (p == SYSTEMSOLVABLE || (solv->installed && pool->solvables[p].repo == solv->installed))
101 /*-------------------------------------------------------------------
102 * Check if dependenc is possible
104 * this mirrors solver_dep_fulfilled
105 * but uses map m instead of the decisionmap
109 dep_possible(Solver *solv, Id dep, Map *m)
111 Pool *pool = solv->pool;
116 Reldep *rd = GETRELDEP(pool, dep);
117 if (rd->flags == REL_AND)
119 if (!dep_possible(solv, rd->name, m))
121 return dep_possible(solv, rd->evr, m);
123 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
124 return solver_splitprovides(solv, rd->evr);
125 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
126 return solver_dep_installed(solv, rd->evr);
128 FOR_PROVIDES(p, pp, dep)
136 /********************************************************************
140 * - unify rules, remove duplicates
143 /*-------------------------------------------------------------------
145 * compare rules for unification sort
150 unifyrules_sortcmp(const void *ap, const void *bp, void *dp)
153 Rule *a = (Rule *)ap;
154 Rule *b = (Rule *)bp;
160 return x; /* p differs */
163 if (a->d == 0 && b->d == 0)
164 return a->w2 - b->w2; /* assertion: return w2 diff */
166 if (a->d == 0) /* a is assertion, b not */
168 x = a->w2 - pool->whatprovidesdata[b->d];
172 if (b->d == 0) /* b is assertion, a not */
174 x = pool->whatprovidesdata[a->d] - b->w2;
178 /* compare whatprovidesdata */
179 ad = pool->whatprovidesdata + a->d;
180 bd = pool->whatprovidesdata + b->d;
182 if ((x = *ad++ - *bd++) != 0)
188 /*-------------------------------------------------------------------
191 * go over all rules and remove duplicates
195 unifyrules(Solver *solv)
197 Pool *pool = solv->pool;
201 if (solv->nrules <= 1) /* nothing to unify */
204 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- unifyrules -----\n");
206 /* sort rules first */
207 sat_sort(solv->rules + 1, solv->nrules - 1, sizeof(Rule), unifyrules_sortcmp, solv->pool);
214 for (i = j = 1, ir = solv->rules + i; i < solv->nrules; i++, ir++)
216 if (jr && !unifyrules_sortcmp(ir, jr, pool))
217 continue; /* prune! */
218 jr = solv->rules + j++; /* keep! */
223 /* reduced count from nrules to j rules */
224 POOL_DEBUG(SAT_DEBUG_STATS, "pruned rules from %d to %d\n", solv->nrules, j);
226 /* adapt rule buffer */
228 solv->rules = sat_extend_resize(solv->rules, solv->nrules, sizeof(Rule), RULES_BLOCK);
232 IF_POOLDEBUG (SAT_DEBUG_STATS)
239 for (i = 1; i < solv->nrules; i++)
246 dp = solv->pool->whatprovidesdata + r->d;
251 POOL_DEBUG(SAT_DEBUG_STATS, " binary: %d\n", binr);
252 POOL_DEBUG(SAT_DEBUG_STATS, " normal: %d, %d literals\n", solv->nrules - 1 - binr, lits);
254 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- unifyrules end -----\n");
264 hashrule(Solver *solv, Id p, Id d, int n)
266 unsigned int x = (unsigned int)p;
270 return (x * 37) ^ (unsigned int)d;
271 dp = solv->pool->whatprovidesdata + d;
273 x = (x * 37) ^ (unsigned int)*dp++;
279 /*-------------------------------------------------------------------
285 * p = direct literal; always < 0 for installed rpm rules
286 * d, if < 0 direct literal, if > 0 offset into whatprovides, if == 0 rule is assertion (look at p only)
289 * A requires b, b provided by B1,B2,B3 => (-A|B1|B2|B3)
291 * p < 0 : pkg id of A
292 * d > 0 : Offset in whatprovidesdata (list of providers of b)
294 * A conflicts b, b provided by B1,B2,B3 => (-A|-B1), (-A|-B2), (-A|-B3)
295 * p < 0 : pkg id of A
296 * d < 0 : Id of solvable (e.g. B1)
298 * d == 0: unary rule, assertion => (A) or (-A)
300 * Install: p > 0, d = 0 (A) user requested install
301 * Remove: p < 0, d = 0 (-A) user requested remove (also: uninstallable)
302 * Requires: p < 0, d > 0 (-A|B1|B2|...) d: <list of providers for requirement of p>
303 * Updates: p > 0, d > 0 (A|B1|B2|...) d: <list of updates for solvable p>
304 * Conflicts: p < 0, d < 0 (-A|-B) either p (conflict issuer) or d (conflict provider) (binary rule)
305 * also used for obsoletes
306 * ?: p > 0, d < 0 (A|-B)
307 * No-op ?: p = 0, d = 0 (null) (used as policy rule placeholder)
311 * Direct assertion (no watch needed)( if d <0 ) --> d = 0, w1 = p, w2 = 0
312 * Binary rule: p = first literal, d = 0, w2 = second literal, w1 = p
313 * every other : w1 = p, w2 = whatprovidesdata[d];
314 * Disabled rule: w1 = 0
316 * always returns a rule for non-rpm rules
320 addrule(Solver *solv, Id p, Id d)
322 Pool *pool = solv->pool;
326 int n = 0; /* number of literals in rule - 1
327 0 = direct assertion (single literal)
332 /* it often happenes that requires lead to adding the same rpm rule
333 * multiple times, so we prune those duplicates right away to make
334 * the work for unifyrules a bit easier */
336 if (solv->nrules /* we already have rules */
337 && !solv->rpmrules_end) /* but are not done with rpm rules */
339 r = solv->rules + solv->nrules - 1; /* get the last added rule */
340 if (r->p == p && r->d == d && d != 0) /* identical and not user requested */
345 * compute number of literals (n) in rule
350 /* always a binary rule */
352 return 0; /* ignore self conflict */
357 for (dp = pool->whatprovidesdata + d; *dp; dp++, n++)
359 return 0; /* rule is self-fulfilling */
361 if (n == 1) /* have single provider */
362 d = dp[-1]; /* take single literal */
365 if (n == 1 && p > d && !solv->rpmrules_end)
367 /* smallest literal first so we can find dups */
368 n = p; p = d; d = n; /* p <-> d */
369 n = 1; /* re-set n, was used as temp var */
373 * check for duplicate
376 /* check if the last added rule (r) is exactly the same as what we're looking for. */
377 if (r && n == 1 && !r->d && r->p == p && r->w2 == d)
378 return r; /* binary rule */
380 /* have n-ary rule with same first literal, check other literals */
381 if (r && n > 1 && r->d && r->p == p)
383 /* Rule where d is an offset in whatprovidesdata */
387 dp2 = pool->whatprovidesdata + r->d;
388 for (dp = pool->whatprovidesdata + d; *dp; dp++, dp2++)
399 /* extend rule buffer */
400 solv->rules = sat_extend(solv->rules, solv->nrules, 1, sizeof(Rule), RULES_BLOCK);
401 r = solv->rules + solv->nrules++; /* point to rule space */
410 /* direct assertion, no watch needed */
426 r->w2 = pool->whatprovidesdata[d];
431 IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION)
433 POOL_DEBUG(SAT_DEBUG_RULE_CREATION, " Add rule: ");
434 solver_printrule(solv, SAT_DEBUG_RULE_CREATION, r);
440 /*-------------------------------------------------------------------
445 disablerule(Solver *solv, Rule *r)
451 /*-------------------------------------------------------------------
456 enablerule(Solver *solv, Rule *r)
463 /**********************************************************************************/
465 /* a problem is an item on the solver's problem list. It can either be >0, in that
466 * case it is a update rule, or it can be <0, which makes it refer to a job
467 * consisting of multiple job rules.
471 disableproblem(Solver *solv, Id v)
479 if (v >= solv->infarchrules && v < solv->infarchrules_end)
481 Pool *pool = solv->pool;
482 Id name = pool->solvables[-solv->rules[v].p].name;
483 while (v > solv->infarchrules && pool->solvables[-solv->rules[v - 1].p].name == name)
485 for (; v < solv->infarchrules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
486 disablerule(solv, solv->rules + v);
489 if (v >= solv->duprules && v < solv->duprules_end)
491 Pool *pool = solv->pool;
492 Id name = pool->solvables[-solv->rules[v].p].name;
493 while (v > solv->duprules && pool->solvables[-solv->rules[v - 1].p].name == name)
495 for (; v < solv->duprules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
496 disablerule(solv, solv->rules + v);
499 disablerule(solv, solv->rules + v);
503 jp = solv->ruletojob.elements;
504 for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++, jp++)
506 disablerule(solv, r);
509 /*-------------------------------------------------------------------
514 enableproblem(Solver *solv, Id v)
522 if (v >= solv->infarchrules && v < solv->infarchrules_end)
524 Pool *pool = solv->pool;
525 Id name = pool->solvables[-solv->rules[v].p].name;
526 while (v > solv->infarchrules && pool->solvables[-solv->rules[v - 1].p].name == name)
528 for (; v < solv->infarchrules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
529 enablerule(solv, solv->rules + v);
532 if (v >= solv->duprules && v < solv->duprules_end)
534 Pool *pool = solv->pool;
535 Id name = pool->solvables[-solv->rules[v].p].name;
536 while (v > solv->duprules && pool->solvables[-solv->rules[v - 1].p].name == name)
538 for (; v < solv->duprules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
539 enablerule(solv, solv->rules + v);
542 if (v >= solv->featurerules && v < solv->featurerules_end)
544 /* do not enable feature rule if update rule is enabled */
545 r = solv->rules + (v - solv->featurerules + solv->updaterules);
549 enablerule(solv, solv->rules + v);
550 if (v >= solv->updaterules && v < solv->updaterules_end)
552 /* disable feature rule when enabling update rule */
553 r = solv->rules + (v - solv->updaterules + solv->featurerules);
555 disablerule(solv, r);
560 jp = solv->ruletojob.elements;
561 for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++, jp++)
567 /************************************************************************/
570 * make assertion rules into decisions
572 * Go through rules and add direct assertions to the decisionqueue.
573 * If we find a conflict, disable rules and add them to problem queue.
577 makeruledecisions(Solver *solv)
579 Pool *pool = solv->pool;
585 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- makeruledecisions ; size decisionq: %d -----\n",solv->decisionq.count);
587 /* The system solvable is always installed first */
588 assert(solv->decisionq.count == 0);
589 queue_push(&solv->decisionq, SYSTEMSOLVABLE);
590 queue_push(&solv->decisionq_why, 0);
591 solv->decisionmap[SYSTEMSOLVABLE] = 1; /* installed at level '1' */
593 decisionstart = solv->decisionq.count;
594 for (ii = 0; ii < solv->ruleassertions.count; ii++)
596 ri = solv->ruleassertions.elements[ii];
597 r = solv->rules + ri;
599 if (r->d < 0 || !r->p || r->w2) /* disabled, dummy or no assertion */
601 /* do weak rules in phase 2 */
602 if (ri < solv->learntrules && MAPTST(&solv->weakrulemap, ri))
608 if (!solv->decisionmap[vv]) /* if not yet decided */
613 queue_push(&solv->decisionq, v);
614 queue_push(&solv->decisionq_why, r - solv->rules);
615 solv->decisionmap[vv] = v > 0 ? 1 : -1;
616 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
618 Solvable *s = solv->pool->solvables + vv;
620 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "conflicting %s (assertion)\n", solvable2str(solv->pool, s));
622 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "installing %s (assertion)\n", solvable2str(solv->pool, s));
627 * check previous decision: is it sane ?
630 if (v > 0 && solv->decisionmap[vv] > 0) /* ok to install */
632 if (v < 0 && solv->decisionmap[vv] < 0) /* ok to remove */
638 * The rule (r) we're currently processing says something
639 * different (v = r->p) than a previous decision (decisionmap[abs(v)])
643 if (ri >= solv->learntrules)
645 /* conflict with a learnt rule */
646 /* can happen when packages cannot be installed for
647 * multiple reasons. */
648 /* we disable the learnt rule in this case */
649 disablerule(solv, r);
654 * find the decision which is the "opposite" of the rule
657 for (i = 0; i < solv->decisionq.count; i++)
658 if (solv->decisionq.elements[i] == -v)
660 assert(i < solv->decisionq.count); /* assert that we found it */
663 * conflict with system solvable ?
666 if (v == -SYSTEMSOLVABLE) {
667 /* conflict with system solvable */
668 queue_push(&solv->problems, solv->learnt_pool.count);
669 queue_push(&solv->learnt_pool, ri);
670 queue_push(&solv->learnt_pool, 0);
671 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "conflict with system solvable, disabling rule #%d\n", ri);
672 if (ri >= solv->jobrules && ri < solv->jobrules_end)
673 v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
676 queue_push(&solv->problems, v);
677 queue_push(&solv->problems, 0);
678 disableproblem(solv, v);
682 assert(solv->decisionq_why.elements[i] > 0);
685 * conflict with an rpm rule ?
688 if (solv->decisionq_why.elements[i] < solv->rpmrules_end)
690 /* conflict with rpm rule assertion */
691 queue_push(&solv->problems, solv->learnt_pool.count);
692 queue_push(&solv->learnt_pool, ri);
693 queue_push(&solv->learnt_pool, solv->decisionq_why.elements[i]);
694 queue_push(&solv->learnt_pool, 0);
695 assert(v > 0 || v == -SYSTEMSOLVABLE);
696 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "conflict with rpm rule, disabling rule #%d\n", ri);
697 if (ri >= solv->jobrules && ri < solv->jobrules_end)
698 v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
701 queue_push(&solv->problems, v);
702 queue_push(&solv->problems, 0);
703 disableproblem(solv, v);
708 * conflict with another job or update/feature rule
712 queue_push(&solv->problems, solv->learnt_pool.count);
713 queue_push(&solv->learnt_pool, ri);
714 queue_push(&solv->learnt_pool, solv->decisionq_why.elements[i]);
715 queue_push(&solv->learnt_pool, 0);
717 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "conflicting update/job assertions over literal %d\n", vv);
720 * push all of our rules (can only be feature or job rules)
721 * asserting this literal on the problem stack
724 for (i = solv->featurerules, rr = solv->rules + i; i < solv->learntrules; i++, rr++)
726 if (rr->d < 0 /* disabled */
727 || rr->w2) /* or no assertion */
729 if (rr->p != vv /* not affecting the literal */
732 if (MAPTST(&solv->weakrulemap, i)) /* weak: silently ignore */
735 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, " - disabling rule #%d\n", i);
737 solver_printruleclass(solv, SAT_DEBUG_UNSOLVABLE, solv->rules + i);
740 /* is is a job rule ? */
741 if (i >= solv->jobrules && i < solv->jobrules_end)
742 v = -(solv->ruletojob.elements[i - solv->jobrules] + 1);
744 queue_push(&solv->problems, v);
745 disableproblem(solv, v);
747 queue_push(&solv->problems, 0);
751 * (back up from decisions)
753 while (solv->decisionq.count > decisionstart)
755 v = solv->decisionq.elements[--solv->decisionq.count];
756 --solv->decisionq_why.count;
758 solv->decisionmap[vv] = 0;
760 ii = -1; /* restarts loop at 0 */
764 * phase 2: now do the weak assertions
766 for (ii = 0; ii < solv->ruleassertions.count; ii++)
768 ri = solv->ruleassertions.elements[ii];
769 r = solv->rules + ri;
770 if (r->d < 0 || r->w2) /* disabled or no assertion */
772 if (ri >= solv->learntrules || !MAPTST(&solv->weakrulemap, ri)) /* skip non-weak */
778 * (if not yet decided)
780 if (!solv->decisionmap[vv])
782 queue_push(&solv->decisionq, v);
783 queue_push(&solv->decisionq_why, r - solv->rules);
784 solv->decisionmap[vv] = v > 0 ? 1 : -1;
785 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
787 Solvable *s = solv->pool->solvables + vv;
789 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "conflicting %s (weak assertion)\n", solvable2str(solv->pool, s));
791 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "installing %s (weak assertion)\n", solvable2str(solv->pool, s));
796 * previously decided, sane ?
798 if (v > 0 && solv->decisionmap[vv] > 0)
800 if (v < 0 && solv->decisionmap[vv] < 0)
803 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "assertion conflict, but I am weak, disabling ");
804 solver_printrule(solv, SAT_DEBUG_UNSOLVABLE, r);
806 if (ri >= solv->jobrules && ri < solv->jobrules_end)
807 v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
810 disableproblem(solv, v);
812 reenablepolicyrules(solv, &solv->job, -(v + 1));
815 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- makeruledecisions end; size decisionq: %d -----\n",solv->decisionq.count);
819 /*-------------------------------------------------------------------
820 * enable/disable learnt rules
822 * we have enabled or disabled some of our rules. We now reenable all
823 * of our learnt rules except the ones that were learnt from rules that
827 enabledisablelearntrules(Solver *solv)
829 Pool *pool = solv->pool;
834 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "enabledisablelearntrules called\n");
835 for (i = solv->learntrules, r = solv->rules + i; i < solv->nrules; i++, r++)
837 whyp = solv->learnt_pool.elements + solv->learnt_why.elements[i - solv->learntrules];
838 while ((why = *whyp++) != 0)
840 assert(why > 0 && why < i);
841 if (solv->rules[why].d < 0)
844 /* why != 0: we found a disabled rule, disable the learnt rule */
845 if (why && r->d >= 0)
847 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
849 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "disabling ");
850 solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
852 disablerule(solv, r);
854 else if (!why && r->d < 0)
856 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
858 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "re-enabling ");
859 solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
867 /*-------------------------------------------------------------------
870 * Enable all rules, except learnt rules, which are
871 * - disabled and weak (set in weakrulemap)
876 enableweakrules(Solver *solv)
881 for (i = 1, r = solv->rules + i; i < solv->learntrules; i++, r++)
883 if (r->d >= 0) /* already enabled? */
885 if (!MAPTST(&solv->weakrulemap, i))
892 /*-------------------------------------------------------------------
893 * policy rule enabling/disabling
895 * we need to disable policy rules that conflict with our job list, and
896 * also reenable such rules with the job was changed due to solution generation
901 disableinfarchrule(Solver *solv, Id name)
903 Pool *pool = solv->pool;
906 for (i = solv->infarchrules, r = solv->rules + i; i < solv->infarchrules_end; i++, r++)
908 if (r->p < 0 && r->d >= 0 && pool->solvables[-r->p].name == name)
909 disablerule(solv, r);
914 reenableinfarchrule(Solver *solv, Id name)
916 Pool *pool = solv->pool;
919 for (i = solv->infarchrules, r = solv->rules + i; i < solv->infarchrules_end; i++, r++)
921 if (r->p < 0 && r->d < 0 && pool->solvables[-r->p].name == name)
924 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
926 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
927 solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
934 disableduprule(Solver *solv, Id name)
936 Pool *pool = solv->pool;
939 for (i = solv->duprules, r = solv->rules + i; i < solv->duprules_end; i++, r++)
941 if (r->p < 0 && r->d >= 0 && pool->solvables[-r->p].name == name)
942 disablerule(solv, r);
947 reenableduprule(Solver *solv, Id name)
949 Pool *pool = solv->pool;
952 for (i = solv->duprules, r = solv->rules + i; i < solv->duprules_end; i++, r++)
954 if (r->p < 0 && r->d < 0 && pool->solvables[-r->p].name == name)
957 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
959 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
960 solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
967 disableupdaterule(Solver *solv, Id p)
971 MAPSET(&solv->noupdate, p - solv->installed->start);
972 r = solv->rules + solv->updaterules + (p - solv->installed->start);
973 if (r->p && r->d >= 0)
974 disablerule(solv, r);
975 r = solv->rules + solv->featurerules + (p - solv->installed->start);
976 if (r->p && r->d >= 0)
977 disablerule(solv, r);
981 reenableupdaterule(Solver *solv, Id p)
983 Pool *pool = solv->pool;
986 MAPCLR(&solv->noupdate, p - solv->installed->start);
987 r = solv->rules + solv->updaterules + (p - solv->installed->start);
993 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
995 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
996 solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
1000 r = solv->rules + solv->featurerules + (p - solv->installed->start);
1001 if (r->p && r->d < 0)
1003 enablerule(solv, r);
1004 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
1006 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
1007 solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
1012 #define DISABLE_UPDATE 1
1013 #define DISABLE_INFARCH 2
1014 #define DISABLE_DUP 3
1017 jobtodisablelist(Solver *solv, Id how, Id what, Queue *q)
1019 Pool *pool = solv->pool;
1025 installed = solv->installed;
1026 select = how & SOLVER_SELECTMASK;
1027 switch (how & SOLVER_JOBMASK)
1029 case SOLVER_INSTALL:
1030 if ((select == SOLVER_SOLVABLE_NAME || select == SOLVER_SOLVABLE_PROVIDES) && solv->infarchrules != solv->infarchrules_end && ISRELDEP(what))
1032 Reldep *rd = GETRELDEP(pool, what);
1033 if (rd->flags == REL_ARCH)
1035 int qcnt = q->count;
1036 FOR_JOB_SELECT(p, pp, select, what)
1038 s = pool->solvables + p;
1040 for (i = qcnt; i < q->count; i += 2)
1041 if (q->elements[i + 1] == s->name)
1045 queue_push(q, DISABLE_INFARCH);
1046 queue_push(q, s->name);
1050 if (select != SOLVER_SOLVABLE)
1052 s = pool->solvables + what;
1053 if (solv->infarchrules != solv->infarchrules_end)
1055 queue_push(q, DISABLE_INFARCH);
1056 queue_push(q, s->name);
1058 if (solv->duprules != solv->duprules_end)
1060 queue_push(q, DISABLE_DUP);
1061 queue_push(q, s->name);
1065 if (solv->noobsoletes.size && MAPTST(&solv->noobsoletes, what))
1067 if (s->repo == installed)
1069 queue_push(q, DISABLE_UPDATE);
1070 queue_push(q, what);
1076 obsp = s->repo->idarraydata + s->obsoletes;
1077 while ((obs = *obsp++) != 0)
1078 FOR_PROVIDES(p, pp, obs)
1080 Solvable *ps = pool->solvables + p;
1081 if (ps->repo != installed)
1083 if (!solv->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
1085 queue_push(q, DISABLE_UPDATE);
1089 FOR_PROVIDES(p, pp, s->name)
1091 Solvable *ps = pool->solvables + p;
1092 if (ps->repo != installed)
1094 if (!solv->implicitobsoleteusesprovides && ps->name != s->name)
1096 queue_push(q, DISABLE_UPDATE);
1103 FOR_JOB_SELECT(p, pp, select, what)
1104 if (pool->solvables[p].repo == installed)
1106 queue_push(q, DISABLE_UPDATE);
1115 /* disable all policy rules that are in conflict with our job list */
1117 disablepolicyrules(Solver *solv, Queue *job)
1125 queue_init_buffer(&allq, allqbuf, sizeof(allqbuf)/sizeof(*allqbuf));
1127 for (i = solv->jobrules; i < solv->jobrules_end; i++)
1129 r = solv->rules + i;
1130 if (r->d < 0) /* disabled? */
1132 j = solv->ruletojob.elements[i - solv->jobrules];
1136 jobtodisablelist(solv, job->elements[j], job->elements[j + 1], &allq);
1138 MAPZERO(&solv->noupdate);
1139 for (i = 0; i < allq.count; i += 2)
1141 Id type = allq.elements[i], arg = allq.elements[i + 1];
1144 case DISABLE_UPDATE:
1145 disableupdaterule(solv, arg);
1147 case DISABLE_INFARCH:
1148 disableinfarchrule(solv, arg);
1151 disableduprule(solv, arg);
1160 /* we just disabled job #jobidx, now reenable all policy rules that were
1161 * disabled because of this job */
1163 reenablepolicyrules(Solver *solv, Queue *job, int jobidx)
1169 Id qbuf[32], allqbuf[128];
1171 queue_init_buffer(&q, qbuf, sizeof(qbuf)/sizeof(*qbuf));
1172 queue_init_buffer(&allq, allqbuf, sizeof(allqbuf)/sizeof(*allqbuf));
1173 jobtodisablelist(solv, job->elements[jobidx], job->elements[jobidx + 1], &q);
1176 for (i = solv->jobrules; i < solv->jobrules_end; i++)
1178 r = solv->rules + i;
1179 if (r->d < 0) /* disabled? */
1181 j = solv->ruletojob.elements[i - solv->jobrules];
1185 jobtodisablelist(solv, job->elements[j], job->elements[j + 1], &allq);
1187 for (j = 0; j < q.count; j += 2)
1189 Id type = q.elements[j], arg = q.elements[j + 1];
1190 for (i = 0; i < allq.count; i += 2)
1191 if (allq.elements[i] == type && allq.elements[i + 1] == arg)
1194 continue; /* still disabled */
1197 case DISABLE_UPDATE:
1198 reenableupdaterule(solv, arg);
1200 case DISABLE_INFARCH:
1201 reenableinfarchrule(solv, arg);
1204 reenableduprule(solv, arg);
1212 /*-------------------------------------------------------------------
1218 * special multiversion patch conflict handling:
1219 * a patch conflict is also satisfied, if some other
1220 * version with the same name/arch that doesn't conflict
1221 * get's installed. The generated rule is thus:
1222 * -patch|-cpack|opack1|opack2|...
1225 makemultiversionconflict(Solver *solv, Id n, Id con)
1227 Pool *pool = solv->pool;
1232 sn = pool->solvables + n;
1233 queue_init_buffer(&q, qbuf, sizeof(qbuf)/sizeof(*qbuf));
1235 FOR_PROVIDES(p, pp, sn->name)
1237 s = pool->solvables + p;
1238 if (s->name != sn->name || s->arch != sn->arch)
1240 if (!MAPTST(&solv->noobsoletes, p))
1242 if (pool_match_nevr(pool, pool->solvables + p, con))
1244 /* here we have a multiversion solvable that doesn't conflict */
1245 /* thus we're not in conflict if it is installed */
1249 return -n; /* no other package found, generate normal conflict */
1250 return pool_queuetowhatprovides(pool, &q);
1254 addrpmrule(Solver *solv, Id p, Id d, int type, Id dep)
1256 if (!solv->ruleinfoq)
1257 addrule(solv, p, d);
1259 addrpmruleinfo(solv, p, d, type, dep);
1262 /*-------------------------------------------------------------------
1264 * add (install) rules for solvable
1266 * s: Solvable for which to add rules
1267 * m: m[s] = 1 for solvables which have rules, prevent rule duplication
1269 * Algorithm: 'visit all nodes of a graph'. The graph nodes are
1270 * solvables, the edges their dependencies.
1271 * Starting from an installed solvable, this will create all rules
1272 * representing the graph created by the solvables dependencies.
1274 * for unfulfilled requirements, conflicts, obsoletes,....
1275 * add a negative assertion for solvables that are not installable
1277 * It will also create rules for all solvables referenced by 's'
1278 * i.e. descend to all providers of requirements of 's'
1283 addrpmrulesforsolvable(Solver *solv, Solvable *s, Map *m)
1285 Pool *pool = solv->pool;
1286 Repo *installed = solv->installed;
1288 /* 'work' queue. keeps Ids of solvables we still have to work on.
1289 And buffer for it. */
1294 /* if to add rules for broken deps ('rpm -V' functionality)
1298 /* Id var and pointer for each dependency
1299 * (not used in parallel)
1306 Id p, pp; /* whatprovides loops */
1307 Id *dp; /* ptr to 'whatprovides' */
1308 Id n; /* Id for current solvable 's' */
1310 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforsolvable -----\n");
1312 queue_init_buffer(&workq, workqbuf, sizeof(workqbuf)/sizeof(*workqbuf));
1313 queue_push(&workq, s - pool->solvables); /* push solvable Id to work queue */
1315 /* loop until there's no more work left */
1320 * s: Pointer to solvable
1323 n = queue_shift(&workq); /* 'pop' next solvable to work on from queue */
1326 if (MAPTST(m, n)) /* continue if already visited */
1328 MAPSET(m, n); /* mark as visited */
1331 s = pool->solvables + n; /* s = Solvable in question */
1334 if (installed /* Installed system available */
1335 && !solv->fixsystem /* NOT repair errors in rpm dependency graph */
1336 && s->repo == installed) /* solvable is installed? */
1338 dontfix = 1; /* dont care about broken rpm deps */
1342 && s->arch != ARCH_SRC
1343 && s->arch != ARCH_NOSRC
1344 && !pool_installable(pool, s))
1346 POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "package %s [%d] is not installable\n", solvable2str(pool, s), (Id)(s - pool->solvables));
1347 addrpmrule(solv, -n, 0, SOLVER_RULE_RPM_NOT_INSTALLABLE, 0);
1350 /* yet another SUSE hack, sigh */
1351 if (pool->nscallback && !strncmp("product:", id2str(pool, s->name), 8))
1353 Id buddy = pool->nscallback(pool, pool->nscallbackdata, NAMESPACE_PRODUCTBUDDY, n);
1354 if (buddy > 0 && buddy != SYSTEMSOLVABLE && buddy != n && buddy < pool->nsolvables)
1356 addrpmrule(solv, n, -buddy, SOLVER_RULE_RPM_PACKAGE_REQUIRES, solvable_selfprovidedep(pool->solvables + n));
1357 addrpmrule(solv, buddy, -n, SOLVER_RULE_RPM_PACKAGE_REQUIRES, solvable_selfprovidedep(pool->solvables + buddy));
1358 if (m && !MAPTST(m, buddy))
1359 queue_push(&workq, buddy);
1363 /*-----------------------------------------
1364 * check requires of s
1369 reqp = s->repo->idarraydata + s->requires;
1370 while ((req = *reqp++) != 0) /* go through all requires */
1372 if (req == SOLVABLE_PREREQMARKER) /* skip the marker */
1375 /* find list of solvables providing 'req' */
1376 dp = pool_whatprovides_ptr(pool, req);
1378 if (*dp == SYSTEMSOLVABLE) /* always installed */
1383 /* the strategy here is to not insist on dependencies
1384 * that are already broken. so if we find one provider
1385 * that was already installed, we know that the
1386 * dependency was not broken before so we enforce it */
1388 /* check if any of the providers for 'req' is installed */
1389 for (i = 0; (p = dp[i]) != 0; i++)
1391 if (pool->solvables[p].repo == installed)
1392 break; /* provider was installed */
1394 /* didn't find an installed provider: previously broken dependency */
1397 POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "ignoring broken requires %s of installed package %s\n", dep2str(pool, req), solvable2str(pool, s));
1404 /* nothing provides req! */
1405 POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "package %s [%d] is not installable (%s)\n", solvable2str(pool, s), (Id)(s - pool->solvables), dep2str(pool, req));
1406 addrpmrule(solv, -n, 0, SOLVER_RULE_RPM_NOTHING_PROVIDES_DEP, req);
1410 IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION)
1412 POOL_DEBUG(SAT_DEBUG_RULE_CREATION," %s requires %s\n", solvable2str(pool, s), dep2str(pool, req));
1413 for (i = 0; dp[i]; i++)
1414 POOL_DEBUG(SAT_DEBUG_RULE_CREATION, " provided by %s\n", solvid2str(pool, dp[i]));
1417 /* add 'requires' dependency */
1418 /* rule: (-requestor|provider1|provider2|...|providerN) */
1419 addrpmrule(solv, -n, dp - pool->whatprovidesdata, SOLVER_RULE_RPM_PACKAGE_REQUIRES, req);
1421 /* descend the dependency tree
1422 push all non-visited providers on the work queue */
1427 if (!MAPTST(m, *dp))
1428 queue_push(&workq, *dp);
1432 } /* while, requirements of n */
1434 } /* if, requirements */
1436 /* that's all we check for src packages */
1437 if (s->arch == ARCH_SRC || s->arch == ARCH_NOSRC)
1440 /*-----------------------------------------
1441 * check conflicts of s
1448 /* we treat conflicts in patches a bit differen:
1450 * - multiversion handling
1451 * XXX: we should really handle this different, looking
1452 * at the name is a bad hack
1454 if (!strncmp("patch:", id2str(pool, s->name), 6))
1456 conp = s->repo->idarraydata + s->conflicts;
1457 /* foreach conflicts of 's' */
1458 while ((con = *conp++) != 0)
1460 /* foreach providers of a conflict of 's' */
1461 FOR_PROVIDES(p, pp, con)
1463 if (ispatch && !pool_match_nevr(pool, pool->solvables + p, con))
1465 /* dontfix: dont care about conflicts with already installed packs */
1466 if (dontfix && pool->solvables[p].repo == installed)
1468 /* p == n: self conflict */
1469 if (p == n && !solv->allowselfconflicts)
1473 Reldep *rd = GETRELDEP(pool, con);
1474 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_OTHERPROVIDERS)
1477 p = 0; /* make it a negative assertion, aka 'uninstallable' */
1479 if (p && ispatch && solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p) && ISRELDEP(con))
1481 /* our patch conflicts with a noobsoletes (aka multiversion) package */
1482 p = -makemultiversionconflict(solv, p, con);
1484 /* rule: -n|-p: either solvable _or_ provider of conflict */
1485 addrpmrule(solv, -n, -p, p ? SOLVER_RULE_RPM_PACKAGE_CONFLICT : SOLVER_RULE_RPM_SELF_CONFLICT, con);
1490 /*-----------------------------------------
1491 * check obsoletes if not installed
1492 * (only installation will trigger the obsoletes in rpm)
1494 if (!installed || pool->solvables[n].repo != installed)
1495 { /* not installed */
1496 int noobs = solv->noobsoletes.size && MAPTST(&solv->noobsoletes, n);
1497 if (s->obsoletes && !noobs)
1499 obsp = s->repo->idarraydata + s->obsoletes;
1500 /* foreach obsoletes */
1501 while ((obs = *obsp++) != 0)
1503 /* foreach provider of an obsoletes of 's' */
1504 FOR_PROVIDES(p, pp, obs)
1506 if (!solv->obsoleteusesprovides /* obsoletes are matched names, not provides */
1507 && !pool_match_nevr(pool, pool->solvables + p, obs))
1509 addrpmrule(solv, -n, -p, SOLVER_RULE_RPM_PACKAGE_OBSOLETES, obs);
1513 FOR_PROVIDES(p, pp, s->name)
1515 Solvable *ps = pool->solvables + p;
1516 /* we still obsolete packages with same nevra, like rpm does */
1517 /* (actually, rpm mixes those packages. yuck...) */
1518 if (noobs && (s->name != ps->name || s->evr != ps->evr || s->arch != ps->arch))
1520 if (!solv->implicitobsoleteusesprovides && s->name != ps->name)
1522 if (s->name == ps->name)
1523 addrpmrule(solv, -n, -p, SOLVER_RULE_RPM_SAME_NAME, 0);
1525 addrpmrule(solv, -n, -p, SOLVER_RULE_RPM_IMPLICIT_OBSOLETES, s->name);
1529 /*-----------------------------------------
1530 * add recommends to the work queue
1532 if (s->recommends && m)
1534 recp = s->repo->idarraydata + s->recommends;
1535 while ((rec = *recp++) != 0)
1537 FOR_PROVIDES(p, pp, rec)
1539 queue_push(&workq, p);
1542 if (s->suggests && m)
1544 sugp = s->repo->idarraydata + s->suggests;
1545 while ((sug = *sugp++) != 0)
1547 FOR_PROVIDES(p, pp, sug)
1549 queue_push(&workq, p);
1554 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforsolvable end -----\n");
1558 /*-------------------------------------------------------------------
1560 * Add package rules for weak rules
1562 * m: visited solvables
1566 addrpmrulesforweak(Solver *solv, Map *m)
1568 Pool *pool = solv->pool;
1573 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforweak -----\n");
1574 /* foreach solvable in pool */
1575 for (i = n = 1; n < pool->nsolvables; i++, n++)
1577 if (i == pool->nsolvables) /* wrap i */
1579 if (MAPTST(m, i)) /* been there */
1582 s = pool->solvables + i;
1583 if (!pool_installable(pool, s)) /* only look at installable ones */
1589 /* find possible supplements */
1590 supp = s->repo->idarraydata + s->supplements;
1591 while ((sup = *supp++) != ID_NULL)
1592 if (dep_possible(solv, sup, m))
1596 /* if nothing found, check for enhances */
1597 if (!sup && s->enhances)
1599 supp = s->repo->idarraydata + s->enhances;
1600 while ((sup = *supp++) != ID_NULL)
1601 if (dep_possible(solv, sup, m))
1604 /* if nothing found, goto next solvables */
1607 addrpmrulesforsolvable(solv, s, m);
1608 n = 0; /* check all solvables again */
1610 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforweak end -----\n");
1614 /*-------------------------------------------------------------------
1616 * add package rules for possible updates
1619 * m: map of already visited solvables
1620 * allow_all: 0 = dont allow downgrades, 1 = allow all candidates
1624 addrpmrulesforupdaters(Solver *solv, Solvable *s, Map *m, int allow_all)
1626 Pool *pool = solv->pool;
1628 /* queue and buffer for it */
1632 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforupdaters -----\n");
1634 queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
1635 /* find update candidates for 's' */
1636 policy_findupdatepackages(solv, s, &qs, allow_all);
1637 /* add rule for 's' if not already done */
1638 if (!MAPTST(m, s - pool->solvables))
1639 addrpmrulesforsolvable(solv, s, m);
1640 /* foreach update candidate, add rule if not already done */
1641 for (i = 0; i < qs.count; i++)
1642 if (!MAPTST(m, qs.elements[i]))
1643 addrpmrulesforsolvable(solv, pool->solvables + qs.elements[i], m);
1646 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforupdaters -----\n");
1650 finddistupgradepackages(Solver *solv, Solvable *s, Queue *qs, int allow_all)
1652 Pool *pool = solv->pool;
1655 policy_findupdatepackages(solv, s, qs, allow_all);
1659 return 0; /* orphaned, don't create feature rule */
1660 /* check if this is an orphaned package */
1661 policy_findupdatepackages(solv, s, qs, 1);
1663 return 0; /* orphaned, don't create update rule */
1665 return -SYSTEMSOLVABLE; /* supported but not installable */
1668 return s - pool->solvables;
1669 /* check if it is ok to keep the installed package */
1670 for (i = 0; i < qs->count; i++)
1672 Solvable *ns = pool->solvables + qs->elements[i];
1673 if (s->evr == ns->evr && solvable_identical(s, ns))
1674 return s - pool->solvables;
1676 /* nope, it must be some other package */
1677 return -SYSTEMSOLVABLE;
1680 /* add packages from the dup repositories to the update candidates
1681 * this isn't needed for the global dup mode as all packages are
1682 * from dup repos in that case */
1684 addduppackages(Solver *solv, Solvable *s, Queue *qs)
1689 int oldnoupdateprovide = solv->noupdateprovide;
1691 queue_init_buffer(&dupqs, dupqsbuf, sizeof(dupqsbuf)/sizeof(*dupqsbuf));
1692 solv->noupdateprovide = 1;
1693 policy_findupdatepackages(solv, s, &dupqs, 2);
1694 solv->noupdateprovide = oldnoupdateprovide;
1695 for (i = 0; i < dupqs.count; i++)
1697 p = dupqs.elements[i];
1698 if (MAPTST(&solv->dupmap, p))
1699 queue_pushunique(qs, p);
1704 /*-------------------------------------------------------------------
1706 * add rule for update
1707 * (A|A1|A2|A3...) An = update candidates for A
1709 * s = (installed) solvable
1713 addupdaterule(Solver *solv, Solvable *s, int allow_all)
1715 /* installed packages get a special upgrade allowed rule */
1716 Pool *pool = solv->pool;
1721 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addupdaterule -----\n");
1722 queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
1723 p = s - pool->solvables;
1724 /* find update candidates for 's' */
1725 if (solv->distupgrade)
1726 p = finddistupgradepackages(solv, s, &qs, allow_all);
1728 policy_findupdatepackages(solv, s, &qs, allow_all);
1729 if (!allow_all && !solv->distupgrade && solv->dupinvolvedmap.size && MAPTST(&solv->dupinvolvedmap, p))
1730 addduppackages(solv, s, &qs);
1732 if (!allow_all && qs.count && solv->noobsoletes.size)
1736 d = pool_queuetowhatprovides(pool, &qs);
1737 /* filter out all noobsoletes packages as they don't update */
1738 for (i = j = 0; i < qs.count; i++)
1740 if (MAPTST(&solv->noobsoletes, qs.elements[i]))
1742 /* it's ok if they have same nevra */
1743 Solvable *ps = pool->solvables + qs.elements[i];
1744 if (ps->name != s->name || ps->evr != s->evr || ps->arch != s->arch)
1747 qs.elements[j++] = qs.elements[i];
1749 if (j == 0 && p == -SYSTEMSOLVABLE && solv->distupgrade)
1751 queue_push(&solv->orphaned, s - pool->solvables); /* treat as orphaned */
1756 if (d && solv->updatesystem && solv->installed && s->repo == solv->installed)
1758 if (!solv->multiversionupdaters)
1759 solv->multiversionupdaters = sat_calloc(solv->installed->end - solv->installed->start, sizeof(Id));
1760 solv->multiversionupdaters[s - pool->solvables - solv->installed->start] = d;
1765 if (qs.count && p == -SYSTEMSOLVABLE)
1766 p = queue_shift(&qs);
1767 d = qs.count ? pool_queuetowhatprovides(pool, &qs) : 0;
1769 addrule(solv, p, d); /* allow update of s */
1770 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addupdaterule end -----\n");
1774 /********************************************************************/
1778 /*-------------------------------------------------------------------
1781 * initial setup for all watches
1785 makewatches(Solver *solv)
1789 int nsolvables = solv->pool->nsolvables;
1791 sat_free(solv->watches);
1792 /* lower half for removals, upper half for installs */
1793 solv->watches = sat_calloc(2 * nsolvables, sizeof(Id));
1795 /* do it reverse so rpm rules get triggered first (XXX: obsolete?) */
1796 for (i = 1, r = solv->rules + solv->nrules - 1; i < solv->nrules; i++, r--)
1798 for (i = 1, r = solv->rules + 1; i < solv->nrules; i++, r++)
1801 if (!r->w2) /* assertions do not need watches */
1804 /* see addwatches_rule(solv, r) */
1805 r->n1 = solv->watches[nsolvables + r->w1];
1806 solv->watches[nsolvables + r->w1] = r - solv->rules;
1808 r->n2 = solv->watches[nsolvables + r->w2];
1809 solv->watches[nsolvables + r->w2] = r - solv->rules;
1814 /*-------------------------------------------------------------------
1816 * add watches (for a new learned rule)
1817 * sets up watches for a single rule
1819 * see also makewatches() above.
1823 addwatches_rule(Solver *solv, Rule *r)
1825 int nsolvables = solv->pool->nsolvables;
1827 r->n1 = solv->watches[nsolvables + r->w1];
1828 solv->watches[nsolvables + r->w1] = r - solv->rules;
1830 r->n2 = solv->watches[nsolvables + r->w2];
1831 solv->watches[nsolvables + r->w2] = r - solv->rules;
1835 /********************************************************************/
1841 /* shortcuts to check if a literal (positive or negative) assignment
1842 * evaluates to 'true' or 'false'
1844 #define DECISIONMAP_TRUE(p) ((p) > 0 ? (decisionmap[p] > 0) : (decisionmap[-p] < 0))
1845 #define DECISIONMAP_FALSE(p) ((p) > 0 ? (decisionmap[p] < 0) : (decisionmap[-p] > 0))
1846 #define DECISIONMAP_UNDEF(p) (decisionmap[(p) > 0 ? (p) : -(p)] == 0)
1848 /*-------------------------------------------------------------------
1852 * make decision and propagate to all rules
1854 * Evaluate each term affected by the decision (linked through watches)
1855 * If we find unit rules we make new decisions based on them
1857 * Everything's fixed there, it's just finding rules that are
1860 * return : 0 = everything is OK
1861 * rule = conflict found in this rule
1865 propagate(Solver *solv, int level)
1867 Pool *pool = solv->pool;
1868 Id *rp, *next_rp; /* rule pointer, next rule pointer in linked list */
1870 Id p, pkg, other_watch;
1872 Id *decisionmap = solv->decisionmap;
1874 Id *watches = solv->watches + pool->nsolvables; /* place ptr in middle */
1876 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "----- propagate -----\n");
1878 /* foreach non-propagated decision */
1879 while (solv->propagate_index < solv->decisionq.count)
1882 * 'pkg' was just decided
1883 * negate because our watches trigger if literal goes FALSE
1885 pkg = -solv->decisionq.elements[solv->propagate_index++];
1887 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1889 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "propagate for decision %d level %d\n", -pkg, level);
1890 solver_printruleelement(solv, SAT_DEBUG_PROPAGATE, 0, -pkg);
1893 /* foreach rule where 'pkg' is now FALSE */
1894 for (rp = watches + pkg; *rp; rp = next_rp)
1896 r = solv->rules + *rp;
1899 /* rule is disabled, goto next */
1907 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1909 POOL_DEBUG(SAT_DEBUG_PROPAGATE," watch triggered ");
1910 solver_printrule(solv, SAT_DEBUG_PROPAGATE, r);
1913 /* 'pkg' was just decided (was set to FALSE)
1915 * now find other literal watch, check clause
1916 * and advance on linked list
1920 other_watch = r->w2;
1925 other_watch = r->w1;
1930 * This term is already true (through the other literal)
1931 * so we have nothing to do
1933 if (DECISIONMAP_TRUE(other_watch))
1937 * The other literal is FALSE or UNDEF
1943 /* Not a binary clause, try to move our watch.
1945 * Go over all literals and find one that is
1949 * (TRUE is also ok, in that case the rule is fulfilled)
1951 if (r->p /* we have a 'p' */
1952 && r->p != other_watch /* which is not watched */
1953 && !DECISIONMAP_FALSE(r->p)) /* and not FALSE */
1957 else /* go find a 'd' to make 'true' */
1960 we just iterate sequentially, doing it in another order just changes the order of decisions, not the decisions itself
1962 for (dp = pool->whatprovidesdata + r->d; (p = *dp++) != 0;)
1964 if (p != other_watch /* which is not watched */
1965 && !DECISIONMAP_FALSE(p)) /* and not FALSE */
1973 * if we found some p that is UNDEF or TRUE, move
1976 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1979 POOL_DEBUG(SAT_DEBUG_PROPAGATE, " -> move w%d to %s\n", (pkg == r->w1 ? 1 : 2), solvid2str(pool, p));
1981 POOL_DEBUG(SAT_DEBUG_PROPAGATE," -> move w%d to !%s\n", (pkg == r->w1 ? 1 : 2), solvid2str(pool, -p));
1997 watches[p] = r - solv->rules;
2000 /* search failed, thus all unwatched literals are FALSE */
2005 * unit clause found, set literal other_watch to TRUE
2008 if (DECISIONMAP_FALSE(other_watch)) /* check if literal is FALSE */
2009 return r; /* eek, a conflict! */
2011 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
2013 POOL_DEBUG(SAT_DEBUG_PROPAGATE, " unit ");
2014 solver_printrule(solv, SAT_DEBUG_PROPAGATE, r);
2017 if (other_watch > 0)
2018 decisionmap[other_watch] = level; /* install! */
2020 decisionmap[-other_watch] = -level; /* remove! */
2022 queue_push(&solv->decisionq, other_watch);
2023 queue_push(&solv->decisionq_why, r - solv->rules);
2025 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
2027 if (other_watch > 0)
2028 POOL_DEBUG(SAT_DEBUG_PROPAGATE, " -> decided to install %s\n", solvid2str(pool, other_watch));
2030 POOL_DEBUG(SAT_DEBUG_PROPAGATE, " -> decided to conflict %s\n", solvid2str(pool, -other_watch));
2033 } /* foreach rule involving 'pkg' */
2035 } /* while we have non-decided decisions */
2037 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "----- propagate end-----\n");
2039 return 0; /* all is well */
2043 /********************************************************************/
2046 /*-------------------------------------------------------------------
2053 analyze(Solver *solv, int level, Rule *c, int *pr, int *dr, int *whyp)
2055 Pool *pool = solv->pool;
2058 Map seen; /* global? */
2059 Id d, v, vv, *dp, why;
2061 int num = 0, l1num = 0;
2062 int learnt_why = solv->learnt_pool.count;
2063 Id *decisionmap = solv->decisionmap;
2067 POOL_DEBUG(SAT_DEBUG_ANALYZE, "ANALYZE at %d ----------------------\n", level);
2068 map_init(&seen, pool->nsolvables);
2069 idx = solv->decisionq.count;
2072 IF_POOLDEBUG (SAT_DEBUG_ANALYZE)
2073 solver_printruleclass(solv, SAT_DEBUG_ANALYZE, c);
2074 queue_push(&solv->learnt_pool, c - solv->rules);
2075 d = c->d < 0 ? -c->d - 1 : c->d;
2076 dp = d ? pool->whatprovidesdata + d : 0;
2077 /* go through all literals of the rule */
2089 if (DECISIONMAP_TRUE(v)) /* the one true literal */
2091 vv = v > 0 ? v : -v;
2092 if (MAPTST(&seen, vv))
2094 l = solv->decisionmap[vv];
2099 l1num++; /* need to do this one in level1 pass */
2100 else if (l == level)
2101 num++; /* need to do this one as well */
2104 queue_push(&r, v); /* not level1 or conflict level, add to new rule */
2110 if (!num && !--l1num)
2111 break; /* all level 1 literals done */
2115 v = solv->decisionq.elements[--idx];
2116 vv = v > 0 ? v : -v;
2117 if (MAPTST(&seen, vv))
2121 if (num && --num == 0)
2123 *pr = -v; /* so that v doesn't get lost */
2126 POOL_DEBUG(SAT_DEBUG_ANALYZE, "got %d involved level 1 decisions\n", l1num);
2127 for (i = 0; i < r.count; i++)
2130 MAPCLR(&seen, v > 0 ? v : -v);
2132 /* only level 1 marks left */
2136 why = solv->decisionq_why.elements[idx];
2137 if (why <= 0) /* just in case, maybe for SYSTEMSOLVABLE */
2139 c = solv->rules + why;
2145 else if (r.count == 1 && r.elements[0] < 0)
2146 *dr = r.elements[0];
2148 *dr = pool_queuetowhatprovides(pool, &r);
2149 IF_POOLDEBUG (SAT_DEBUG_ANALYZE)
2151 POOL_DEBUG(SAT_DEBUG_ANALYZE, "learned rule for level %d (am %d)\n", rlevel, level);
2152 solver_printruleelement(solv, SAT_DEBUG_ANALYZE, 0, *pr);
2153 for (i = 0; i < r.count; i++)
2154 solver_printruleelement(solv, SAT_DEBUG_ANALYZE, 0, r.elements[i]);
2156 /* push end marker on learnt reasons stack */
2157 queue_push(&solv->learnt_pool, 0);
2160 solv->stats_learned++;
2165 /*-------------------------------------------------------------------
2169 * reset the solver decisions to right after the rpm rules.
2170 * called after rules have been enabled/disabled
2174 reset_solver(Solver *solv)
2176 Pool *pool = solv->pool;
2180 /* rewind all decisions */
2181 for (i = solv->decisionq.count - 1; i >= 0; i--)
2183 v = solv->decisionq.elements[i];
2184 solv->decisionmap[v > 0 ? v : -v] = 0;
2186 solv->decisionq_why.count = 0;
2187 solv->decisionq.count = 0;
2188 solv->recommends_index = -1;
2189 solv->propagate_index = 0;
2191 /* adapt learnt rule status to new set of enabled/disabled rules */
2192 enabledisablelearntrules(solv);
2194 /* redo all job/update decisions */
2195 makeruledecisions(solv);
2196 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "decisions so far: %d\n", solv->decisionq.count);
2200 /*-------------------------------------------------------------------
2202 * analyze_unsolvable_rule
2206 analyze_unsolvable_rule(Solver *solv, Rule *r, Id *lastweakp)
2208 Pool *pool = solv->pool;
2210 Id why = r - solv->rules;
2212 IF_POOLDEBUG (SAT_DEBUG_UNSOLVABLE)
2213 solver_printruleclass(solv, SAT_DEBUG_UNSOLVABLE, r);
2214 if (solv->learntrules && why >= solv->learntrules)
2216 for (i = solv->learnt_why.elements[why - solv->learntrules]; solv->learnt_pool.elements[i]; i++)
2217 if (solv->learnt_pool.elements[i] > 0)
2218 analyze_unsolvable_rule(solv, solv->rules + solv->learnt_pool.elements[i], lastweakp);
2221 if (MAPTST(&solv->weakrulemap, why))
2222 if (!*lastweakp || why > *lastweakp)
2224 /* do not add rpm rules to problem */
2225 if (why < solv->rpmrules_end)
2227 /* turn rule into problem */
2228 if (why >= solv->jobrules && why < solv->jobrules_end)
2229 why = -(solv->ruletojob.elements[why - solv->jobrules] + 1);
2230 /* normalize dup/infarch rules */
2231 if (why > solv->infarchrules && why < solv->infarchrules_end)
2233 Id name = pool->solvables[-solv->rules[why].p].name;
2234 while (why > solv->infarchrules && pool->solvables[-solv->rules[why - 1].p].name == name)
2237 if (why > solv->duprules && why < solv->duprules_end)
2239 Id name = pool->solvables[-solv->rules[why].p].name;
2240 while (why > solv->duprules && pool->solvables[-solv->rules[why - 1].p].name == name)
2244 /* return if problem already countains our rule */
2245 if (solv->problems.count)
2247 for (i = solv->problems.count - 1; i >= 0; i--)
2248 if (solv->problems.elements[i] == 0) /* end of last problem reached? */
2250 else if (solv->problems.elements[i] == why)
2253 queue_push(&solv->problems, why);
2257 /*-------------------------------------------------------------------
2259 * analyze_unsolvable
2261 * return: 1 - disabled some rules, try again
2266 analyze_unsolvable(Solver *solv, Rule *cr, int disablerules)
2268 Pool *pool = solv->pool;
2270 Map seen; /* global to speed things up? */
2271 Id d, v, vv, *dp, why;
2273 Id *decisionmap = solv->decisionmap;
2274 int oldproblemcount;
2275 int oldlearntpoolcount;
2278 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "ANALYZE UNSOLVABLE ----------------------\n");
2279 solv->stats_unsolvable++;
2280 oldproblemcount = solv->problems.count;
2281 oldlearntpoolcount = solv->learnt_pool.count;
2283 /* make room for proof index */
2284 /* must update it later, as analyze_unsolvable_rule would confuse
2285 * it with a rule index if we put the real value in already */
2286 queue_push(&solv->problems, 0);
2289 map_init(&seen, pool->nsolvables);
2290 queue_push(&solv->learnt_pool, r - solv->rules);
2292 analyze_unsolvable_rule(solv, r, &lastweak);
2293 d = r->d < 0 ? -r->d - 1 : r->d;
2294 dp = d ? pool->whatprovidesdata + d : 0;
2305 if (DECISIONMAP_TRUE(v)) /* the one true literal */
2307 vv = v > 0 ? v : -v;
2308 l = solv->decisionmap[vv];
2313 idx = solv->decisionq.count;
2316 v = solv->decisionq.elements[--idx];
2317 vv = v > 0 ? v : -v;
2318 if (!MAPTST(&seen, vv))
2320 why = solv->decisionq_why.elements[idx];
2322 queue_push(&solv->learnt_pool, why);
2323 r = solv->rules + why;
2324 analyze_unsolvable_rule(solv, r, &lastweak);
2325 d = r->d < 0 ? -r->d - 1 : r->d;
2326 dp = d ? pool->whatprovidesdata + d : 0;
2337 if (DECISIONMAP_TRUE(v)) /* the one true literal */
2339 vv = v > 0 ? v : -v;
2340 l = solv->decisionmap[vv];
2347 queue_push(&solv->problems, 0); /* mark end of this problem */
2352 /* disable last weak rule */
2353 solv->problems.count = oldproblemcount;
2354 solv->learnt_pool.count = oldlearntpoolcount;
2355 if (lastweak >= solv->jobrules && lastweak < solv->jobrules_end)
2356 v = -(solv->ruletojob.elements[lastweak - solv->jobrules] + 1);
2359 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "disabling ");
2360 solver_printruleclass(solv, SAT_DEBUG_UNSOLVABLE, solv->rules + lastweak);
2361 disableproblem(solv, v);
2363 reenablepolicyrules(solv, &solv->job, -(v + 1));
2369 queue_push(&solv->learnt_pool, 0);
2370 solv->problems.elements[oldproblemcount] = oldlearntpoolcount;
2374 for (i = oldproblemcount + 1; i < solv->problems.count - 1; i++)
2375 disableproblem(solv, solv->problems.elements[i]);
2376 /* XXX: might want to enable all weak rules again */
2380 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "UNSOLVABLE\n");
2385 /********************************************************************/
2386 /* Decision revert */
2388 /*-------------------------------------------------------------------
2391 * revert decision at level
2395 revert(Solver *solv, int level)
2397 Pool *pool = solv->pool;
2399 while (solv->decisionq.count)
2401 v = solv->decisionq.elements[solv->decisionq.count - 1];
2402 vv = v > 0 ? v : -v;
2403 if (solv->decisionmap[vv] <= level && solv->decisionmap[vv] >= -level)
2405 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "reverting decision %d at %d\n", v, solv->decisionmap[vv]);
2406 if (v > 0 && solv->recommendations.count && v == solv->recommendations.elements[solv->recommendations.count - 1])
2407 solv->recommendations.count--;
2408 solv->decisionmap[vv] = 0;
2409 solv->decisionq.count--;
2410 solv->decisionq_why.count--;
2411 solv->propagate_index = solv->decisionq.count;
2413 while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] <= -level)
2415 solv->branches.count--;
2416 while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] >= 0)
2417 solv->branches.count--;
2419 solv->recommends_index = -1;
2423 /*-------------------------------------------------------------------
2425 * watch2onhighest - put watch2 on literal with highest level
2429 watch2onhighest(Solver *solv, Rule *r)
2434 d = r->d < 0 ? -r->d - 1 : r->d;
2436 return; /* binary rule, both watches are set */
2437 dp = solv->pool->whatprovidesdata + d;
2438 while ((v = *dp++) != 0)
2440 l = solv->decisionmap[v < 0 ? -v : v];
2452 /*-------------------------------------------------------------------
2456 * add free decision (solvable to install) to decisionq
2457 * increase level and propagate decision
2458 * return if no conflict.
2460 * in conflict case, analyze conflict rule, add resulting
2461 * rule to learnt rule set, make decision from learnt
2462 * rule (always unit) and re-propagate.
2464 * returns the new solver level or 0 if unsolvable
2469 setpropagatelearn(Solver *solv, int level, Id decision, int disablerules, Id ruleid)
2471 Pool *pool = solv->pool;
2476 assert(ruleid >= 0);
2481 solv->decisionmap[decision] = level;
2483 solv->decisionmap[-decision] = -level;
2484 queue_push(&solv->decisionq, decision);
2485 queue_push(&solv->decisionq_why, -ruleid); /* <= 0 -> free decision */
2489 r = propagate(solv, level);
2493 return analyze_unsolvable(solv, r, disablerules);
2494 POOL_DEBUG(SAT_DEBUG_ANALYZE, "conflict with rule #%d\n", (int)(r - solv->rules));
2495 l = analyze(solv, level, r, &p, &d, &why); /* learnt rule in p and d */
2496 assert(l > 0 && l < level);
2497 POOL_DEBUG(SAT_DEBUG_ANALYZE, "reverting decisions (level %d -> %d)\n", level, l);
2499 revert(solv, level);
2500 r = addrule(solv, p, d);
2502 assert(solv->learnt_why.count == (r - solv->rules) - solv->learntrules);
2503 queue_push(&solv->learnt_why, why);
2506 /* at least 2 literals, needs watches */
2507 watch2onhighest(solv, r);
2508 addwatches_rule(solv, r);
2512 /* learnt rule is an assertion */
2513 queue_push(&solv->ruleassertions, r - solv->rules);
2515 /* the new rule is unit by design */
2516 solv->decisionmap[p > 0 ? p : -p] = p > 0 ? level : -level;
2517 queue_push(&solv->decisionq, p);
2518 queue_push(&solv->decisionq_why, r - solv->rules);
2519 IF_POOLDEBUG (SAT_DEBUG_ANALYZE)
2521 POOL_DEBUG(SAT_DEBUG_ANALYZE, "decision: ");
2522 solver_printruleelement(solv, SAT_DEBUG_ANALYZE, 0, p);
2523 POOL_DEBUG(SAT_DEBUG_ANALYZE, "new rule: ");
2524 solver_printrule(solv, SAT_DEBUG_ANALYZE, r);
2531 /*-------------------------------------------------------------------
2533 * select and install
2535 * install best package from the queue. We add an extra package, inst, if
2536 * provided. See comment in weak install section.
2538 * returns the new solver level or 0 if unsolvable
2543 selectandinstall(Solver *solv, int level, Queue *dq, int disablerules, Id ruleid)
2545 Pool *pool = solv->pool;
2550 policy_filter_unwanted(solv, dq, POLICY_MODE_CHOOSE);
2553 /* XXX: didn't we already do that? */
2554 /* XXX: shouldn't we prefer installed packages? */
2555 /* XXX: move to policy.c? */
2556 /* choose the supplemented one */
2557 for (i = 0; i < dq->count; i++)
2558 if (solver_is_supplementing(solv, pool->solvables + dq->elements[i]))
2560 dq->elements[0] = dq->elements[i];
2567 /* multiple candidates, open a branch */
2568 for (i = 1; i < dq->count; i++)
2569 queue_push(&solv->branches, dq->elements[i]);
2570 queue_push(&solv->branches, -level);
2572 p = dq->elements[0];
2574 POOL_DEBUG(SAT_DEBUG_POLICY, "installing %s\n", solvid2str(pool, p));
2576 return setpropagatelearn(solv, level, p, disablerules, ruleid);
2580 /********************************************************************/
2581 /* Main solver interface */
2584 /*-------------------------------------------------------------------
2587 * create solver structure
2589 * pool: all available solvables
2590 * installed: installed Solvables
2593 * Upon solving, rules are created to flag the Solvables
2594 * of the 'installed' Repo as installed.
2598 solver_create(Pool *pool)
2601 solv = (Solver *)sat_calloc(1, sizeof(Solver));
2603 solv->installed = pool->installed;
2605 queue_init(&solv->transaction);
2606 queue_init(&solv->transaction_info);
2607 queue_init(&solv->ruletojob);
2608 queue_init(&solv->decisionq);
2609 queue_init(&solv->decisionq_why);
2610 queue_init(&solv->problems);
2611 queue_init(&solv->suggestions);
2612 queue_init(&solv->recommendations);
2613 queue_init(&solv->orphaned);
2614 queue_init(&solv->learnt_why);
2615 queue_init(&solv->learnt_pool);
2616 queue_init(&solv->branches);
2617 queue_init(&solv->covenantq);
2618 queue_init(&solv->weakruleq);
2619 queue_init(&solv->ruleassertions);
2621 map_init(&solv->recommendsmap, pool->nsolvables);
2622 map_init(&solv->suggestsmap, pool->nsolvables);
2623 map_init(&solv->noupdate, solv->installed ? solv->installed->end - solv->installed->start : 0);
2624 solv->recommends_index = 0;
2626 solv->decisionmap = (Id *)sat_calloc(pool->nsolvables, sizeof(Id));
2628 solv->rules = sat_extend_resize(solv->rules, solv->nrules, sizeof(Rule), RULES_BLOCK);
2629 memset(solv->rules, 0, sizeof(Rule));
2635 /*-------------------------------------------------------------------
2641 solver_free(Solver *solv)
2643 queue_free(&solv->transaction);
2644 queue_free(&solv->transaction_info);
2645 queue_free(&solv->job);
2646 queue_free(&solv->ruletojob);
2647 queue_free(&solv->decisionq);
2648 queue_free(&solv->decisionq_why);
2649 queue_free(&solv->learnt_why);
2650 queue_free(&solv->learnt_pool);
2651 queue_free(&solv->problems);
2652 queue_free(&solv->solutions);
2653 queue_free(&solv->suggestions);
2654 queue_free(&solv->recommendations);
2655 queue_free(&solv->orphaned);
2656 queue_free(&solv->branches);
2657 queue_free(&solv->covenantq);
2658 queue_free(&solv->weakruleq);
2659 queue_free(&solv->ruleassertions);
2661 map_free(&solv->recommendsmap);
2662 map_free(&solv->suggestsmap);
2663 map_free(&solv->noupdate);
2664 map_free(&solv->weakrulemap);
2665 map_free(&solv->noobsoletes);
2667 map_free(&solv->updatemap);
2668 map_free(&solv->dupmap);
2669 map_free(&solv->dupinvolvedmap);
2671 sat_free(solv->decisionmap);
2672 sat_free(solv->rules);
2673 sat_free(solv->watches);
2674 sat_free(solv->obsoletes);
2675 sat_free(solv->obsoletes_data);
2676 sat_free(solv->multiversionupdaters);
2677 sat_free(solv->transaction_installed);
2682 /*-------------------------------------------------------------------
2686 * all rules have been set up, now actually run the solver
2691 run_solver(Solver *solv, int disablerules, int doweak)
2693 Queue dq; /* local decisionqueue */
2694 Queue dqs; /* local decisionqueue for supplements */
2700 Pool *pool = solv->pool;
2702 int minimizationsteps;
2704 IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION)
2706 POOL_DEBUG (SAT_DEBUG_RULE_CREATION, "number of rules: %d\n", solv->nrules);
2707 for (i = 1; i < solv->nrules; i++)
2708 solver_printruleclass(solv, SAT_DEBUG_RULE_CREATION, solv->rules + i);
2711 POOL_DEBUG(SAT_DEBUG_STATS, "initial decisions: %d\n", solv->decisionq.count);
2713 IF_POOLDEBUG (SAT_DEBUG_SCHUBI)
2714 solver_printdecisions(solv);
2716 /* start SAT algorithm */
2718 systemlevel = level + 1;
2719 POOL_DEBUG(SAT_DEBUG_STATS, "solving...\n");
2725 * here's the main loop:
2726 * 1) propagate new decisions (only needed for level 1)
2727 * 2) try to keep installed packages
2728 * 3) fulfill all unresolved rules
2729 * 4) install recommended packages
2730 * 5) minimalize solution if we had choices
2731 * if we encounter a problem, we rewind to a safe level and restart
2735 minimizationsteps = 0;
2744 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "propagating (propagate_index: %d; size decisionq: %d)...\n", solv->propagate_index, solv->decisionq.count);
2745 if ((r = propagate(solv, level)) != 0)
2747 if (analyze_unsolvable(solv, r, disablerules))
2755 if (level < systemlevel)
2757 POOL_DEBUG(SAT_DEBUG_STATS, "resolving job rules\n");
2758 for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++)
2761 if (r->d < 0) /* ignore disabled rules */
2764 FOR_RULELITERALS(l, dp, r)
2768 if (solv->decisionmap[-l] <= 0)
2773 if (solv->decisionmap[l] > 0)
2775 if (solv->decisionmap[l] == 0)
2781 /* prune to installed if not updating */
2782 if (!solv->updatesystem && solv->installed && dq.count > 1)
2785 for (j = k = 0; j < dq.count; j++)
2787 Solvable *s = pool->solvables + dq.elements[j];
2788 if (s->repo == solv->installed)
2789 dq.elements[k++] = dq.elements[j];
2795 level = selectandinstall(solv, level, &dq, disablerules, i);
2802 if (level <= olevel)
2805 systemlevel = level + 1;
2806 if (i < solv->jobrules_end)
2812 * installed packages
2815 if (level < systemlevel && solv->installed && solv->installed->nsolvables)
2817 Repo *installed = solv->installed;
2820 /* we use two passes if we need to update packages
2821 * to create a better user experience */
2822 for (pass = solv->updatemap.size ? 0 : 1; pass < 2; pass++)
2824 FOR_REPO_SOLVABLES(installed, i, s)
2829 /* XXX: noupdate check is probably no longer needed, as all jobs should
2830 * already be satisfied */
2831 if (MAPTST(&solv->noupdate, i - installed->start))
2833 if (solv->decisionmap[i] > 0)
2835 if (!pass && solv->updatemap.size && !MAPTST(&solv->updatemap, i - installed->start))
2836 continue; /* updates first */
2837 r = solv->rules + solv->updaterules + (i - installed->start);
2839 if (!rr->p || rr->d < 0) /* disabled -> look at feature rule */
2840 rr -= solv->installed->end - solv->installed->start;
2841 if (!rr->p) /* identical to update rule? */
2844 continue; /* orpaned package */
2847 if (solv->decisionmap[i] < 0 || solv->updatesystem || (solv->updatemap.size && MAPTST(&solv->updatemap, i - installed->start)) || rr->p != i)
2849 if (solv->noobsoletes.size && solv->multiversionupdaters
2850 && (d = solv->multiversionupdaters[i - installed->start]) != 0)
2852 /* special multiversion handling, make sure best version is chosen */
2854 while ((p = pool->whatprovidesdata[d++]) != 0)
2855 if (solv->decisionmap[p] >= 0)
2857 policy_filter_unwanted(solv, &dq, POLICY_MODE_CHOOSE);
2859 if (p != i && solv->decisionmap[p] == 0)
2861 rr = solv->rules + solv->featurerules + (i - solv->installed->start);
2862 if (!rr->p) /* update rule == feature rule? */
2863 rr = rr - solv->featurerules + solv->updaterules;
2871 /* update to best package */
2872 FOR_RULELITERALS(p, dp, rr)
2874 if (solv->decisionmap[p] > 0)
2876 dq.count = 0; /* already fulfilled */
2879 if (!solv->decisionmap[p])
2884 /* install best version */
2888 level = selectandinstall(solv, level, &dq, disablerules, rr - solv->rules);
2895 if (level <= olevel)
2898 /* if still undecided keep package */
2899 if (solv->decisionmap[i] == 0)
2902 POOL_DEBUG(SAT_DEBUG_POLICY, "keeping %s\n", solvid2str(pool, i));
2903 level = setpropagatelearn(solv, level, i, disablerules, r - solv->rules);
2910 if (level <= olevel)
2914 if (i < installed->end)
2917 systemlevel = level + 1;
2919 continue; /* had trouble, retry */
2922 if (level < systemlevel)
2923 systemlevel = level;
2929 POOL_DEBUG(SAT_DEBUG_POLICY, "deciding unresolved rules\n");
2930 for (i = 1, n = 1; ; i++, n++)
2932 if (n == solv->nrules)
2934 if (i == solv->nrules)
2936 r = solv->rules + i;
2937 if (r->d < 0) /* ignore disabled rules */
2942 /* binary or unary rule */
2943 /* need two positive undecided literals */
2944 if (r->p < 0 || r->w2 <= 0)
2946 if (solv->decisionmap[r->p] || solv->decisionmap[r->w2])
2948 queue_push(&dq, r->p);
2949 queue_push(&dq, r->w2);
2954 * all negative literals are installed
2955 * no positive literal is installed
2956 * i.e. the rule is not fulfilled and we
2957 * just need to decide on the positive literals
2961 if (solv->decisionmap[-r->p] <= 0)
2966 if (solv->decisionmap[r->p] > 0)
2968 if (solv->decisionmap[r->p] == 0)
2969 queue_push(&dq, r->p);
2971 dp = pool->whatprovidesdata + r->d;
2972 while ((p = *dp++) != 0)
2976 if (solv->decisionmap[-p] <= 0)
2981 if (solv->decisionmap[p] > 0)
2983 if (solv->decisionmap[p] == 0)
2990 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
2992 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "unfulfilled ");
2993 solver_printruleclass(solv, SAT_DEBUG_PROPAGATE, r);
2995 /* dq.count < 2 cannot happen as this means that
2996 * the rule is unit */
2997 assert(dq.count > 1);
3000 level = selectandinstall(solv, level, &dq, disablerules, r - solv->rules);
3007 if (level < systemlevel || level == 1)
3010 } /* for(), decide */
3012 if (n != solv->nrules) /* continue if level < systemlevel */
3019 POOL_DEBUG(SAT_DEBUG_POLICY, "installing recommended packages\n");
3020 queue_empty(&dq); /* recommended packages */
3021 queue_empty(&dqs); /* supplemented packages */
3022 for (i = 1; i < pool->nsolvables; i++)
3024 if (solv->decisionmap[i] < 0)
3026 if (solv->decisionmap[i] > 0)
3028 /* installed, check for recommends */
3029 Id *recp, rec, pp, p;
3030 s = pool->solvables + i;
3031 if (solv->ignorealreadyrecommended && s->repo == solv->installed)
3033 /* XXX need to special case AND ? */
3036 recp = s->repo->idarraydata + s->recommends;
3037 while ((rec = *recp++) != 0)
3040 FOR_PROVIDES(p, pp, rec)
3042 if (solv->decisionmap[p] > 0)
3047 else if (solv->decisionmap[p] == 0)
3049 queue_pushunique(&dq, p);
3057 s = pool->solvables + i;
3058 if (!s->supplements)
3060 if (!pool_installable(pool, s))
3062 if (!solver_is_supplementing(solv, s))
3064 queue_push(&dqs, i);
3068 /* filter out all packages obsoleted by installed packages */
3069 /* this is no longer needed if we have reverse obsoletes */
3070 if ((dqs.count || dq.count) && solv->installed)
3073 Id obs, *obsp, po, ppo;
3075 map_init(&obsmap, pool->nsolvables);
3076 for (p = solv->installed->start; p < solv->installed->end; p++)
3078 s = pool->solvables + p;
3079 if (s->repo != solv->installed || !s->obsoletes)
3081 if (solv->decisionmap[p] <= 0)
3083 if (solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p))
3085 obsp = s->repo->idarraydata + s->obsoletes;
3086 /* foreach obsoletes */
3087 while ((obs = *obsp++) != 0)
3088 FOR_PROVIDES(po, ppo, obs)
3089 MAPSET(&obsmap, po);
3091 for (i = j = 0; i < dqs.count; i++)
3092 if (!MAPTST(&obsmap, dqs.elements[i]))
3093 dqs.elements[j++] = dqs.elements[i];
3095 for (i = j = 0; i < dq.count; i++)
3096 if (!MAPTST(&obsmap, dq.elements[i]))
3097 dq.elements[j++] = dq.elements[i];
3102 /* filter out all already supplemented packages if requested */
3103 if (solv->ignorealreadyrecommended && dqs.count)
3105 /* turn off all new packages */
3106 for (i = 0; i < solv->decisionq.count; i++)
3108 p = solv->decisionq.elements[i];
3111 s = pool->solvables + p;
3112 if (s->repo && s->repo != solv->installed)
3113 solv->decisionmap[p] = -solv->decisionmap[p];
3115 /* filter out old supplements */
3116 for (i = j = 0; i < dqs.count; i++)
3118 p = dqs.elements[i];
3119 s = pool->solvables + p;
3120 if (!s->supplements)
3122 if (!solver_is_supplementing(solv, s))
3123 dqs.elements[j++] = p;
3126 /* undo turning off */
3127 for (i = 0; i < solv->decisionq.count; i++)
3129 p = solv->decisionq.elements[i];
3132 s = pool->solvables + p;
3133 if (s->repo && s->repo != solv->installed)
3134 solv->decisionmap[p] = -solv->decisionmap[p];
3138 /* multiversion doesn't mix well with supplements.
3139 * filter supplemented packages where we already decided
3140 * to install a different version (see bnc#501088) */
3141 if (dqs.count && solv->noobsoletes.size)
3143 for (i = j = 0; i < dqs.count; i++)
3145 p = dqs.elements[i];
3146 if (MAPTST(&solv->noobsoletes, p))
3149 s = pool->solvables + p;
3150 FOR_PROVIDES(p2, pp2, s->name)
3151 if (solv->decisionmap[p2] > 0 && pool->solvables[p2].name == s->name)
3154 continue; /* ignore this package */
3156 dqs.elements[j++] = p;
3161 /* make dq contain both recommended and supplemented pkgs */
3164 for (i = 0; i < dqs.count; i++)
3165 queue_pushunique(&dq, dqs.elements[i]);
3171 int decisioncount = solv->decisionq.count;
3175 /* simple case, just one package. no need to choose */
3178 POOL_DEBUG(SAT_DEBUG_POLICY, "installing supplemented %s\n", solvid2str(pool, p));
3180 POOL_DEBUG(SAT_DEBUG_POLICY, "installing recommended %s\n", solvid2str(pool, p));
3181 queue_push(&solv->recommendations, p);
3182 level = setpropagatelearn(solv, level, p, 0, 0);
3183 continue; /* back to main loop */
3186 /* filter packages, this gives us the best versions */
3187 policy_filter_unwanted(solv, &dq, POLICY_MODE_RECOMMEND);
3189 /* create map of result */
3190 map_init(&dqmap, pool->nsolvables);
3191 for (i = 0; i < dq.count; i++)
3192 MAPSET(&dqmap, dq.elements[i]);
3194 /* install all supplemented packages */
3195 for (i = 0; i < dqs.count; i++)
3197 p = dqs.elements[i];
3198 if (solv->decisionmap[p] || !MAPTST(&dqmap, p))
3200 POOL_DEBUG(SAT_DEBUG_POLICY, "installing supplemented %s\n", solvid2str(pool, p));
3201 queue_push(&solv->recommendations, p);
3203 level = setpropagatelearn(solv, level, p, 0, 0);
3204 if (level <= olevel)
3207 if (i < dqs.count || solv->decisionq.count < decisioncount)
3213 /* install all recommended packages */
3214 /* more work as we want to created branches if multiple
3215 * choices are valid */
3216 for (i = 0; i < decisioncount; i++)
3219 p = solv->decisionq.elements[i];
3222 s = pool->solvables + p;
3223 if (!s->repo || (solv->ignorealreadyrecommended && s->repo == solv->installed))
3227 recp = s->repo->idarraydata + s->recommends;
3228 while ((rec = *recp++) != 0)
3231 FOR_PROVIDES(p, pp, rec)
3233 if (solv->decisionmap[p] > 0)
3238 else if (solv->decisionmap[p] == 0 && MAPTST(&dqmap, p))
3239 queue_pushunique(&dq, p);
3245 /* multiple candidates, open a branch */
3246 for (i = 1; i < dq.count; i++)
3247 queue_push(&solv->branches, dq.elements[i]);
3248 queue_push(&solv->branches, -level);
3251 POOL_DEBUG(SAT_DEBUG_POLICY, "installing recommended %s\n", solvid2str(pool, p));
3252 queue_push(&solv->recommendations, p);
3254 level = setpropagatelearn(solv, level, p, 0, 0);
3255 if (level <= olevel || solv->decisionq.count < decisioncount)
3256 break; /* we had to revert some decisions */
3259 break; /* had a problem above, quit loop */
3263 continue; /* back to main loop */
3267 if (solv->distupgrade && solv->installed)
3269 int installedone = 0;
3271 /* let's see if we can install some unsupported package */
3272 POOL_DEBUG(SAT_DEBUG_STATS, "deciding unsupported packages\n");
3273 for (i = 0; i < solv->orphaned.count; i++)
3275 p = solv->orphaned.elements[i];
3276 if (solv->decisionmap[p])
3277 continue; /* already decided */
3279 if (solv->distupgrade_removeunsupported)
3281 POOL_DEBUG(SAT_DEBUG_STATS, "removing unsupported %s\n", solvid2str(pool, p));
3282 level = setpropagatelearn(solv, level, -p, 0, 0);
3286 POOL_DEBUG(SAT_DEBUG_STATS, "keeping unsupported %s\n", solvid2str(pool, p));
3287 level = setpropagatelearn(solv, level, p, 0, 0);
3293 if (installedone || i < solv->orphaned.count)
3297 if (solv->solution_callback)
3299 solv->solution_callback(solv, solv->solution_callback_data);
3300 if (solv->branches.count)
3302 int i = solv->branches.count - 1;
3303 int l = -solv->branches.elements[i];
3307 if (solv->branches.elements[i - 1] < 0)
3309 p = solv->branches.elements[i];
3310 POOL_DEBUG(SAT_DEBUG_STATS, "branching with %s\n", solvid2str(pool, p));
3312 for (j = i + 1; j < solv->branches.count; j++)
3313 queue_push(&dq, solv->branches.elements[j]);
3314 solv->branches.count = i;
3316 revert(solv, level);
3318 for (j = 0; j < dq.count; j++)
3319 queue_push(&solv->branches, dq.elements[j]);
3321 why = -solv->decisionq_why.elements[solv->decisionq_why.count];
3323 level = setpropagatelearn(solv, level, p, disablerules, why);
3332 /* all branches done, we're finally finished */
3336 /* minimization step */
3337 if (solv->branches.count)
3339 int l = 0, lasti = -1, lastl = -1;
3343 for (i = solv->branches.count - 1; i >= 0; i--)
3345 p = solv->branches.elements[i];
3348 else if (p > 0 && solv->decisionmap[p] > l + 1)
3356 /* kill old solvable so that we do not loop */
3357 p = solv->branches.elements[lasti];
3358 solv->branches.elements[lasti] = 0;
3359 POOL_DEBUG(SAT_DEBUG_STATS, "minimizing %d -> %d with %s\n", solv->decisionmap[p], lastl, solvid2str(pool, p));
3360 minimizationsteps++;
3363 revert(solv, level);
3364 why = -solv->decisionq_why.elements[solv->decisionq_why.count];
3367 level = setpropagatelearn(solv, level, p, disablerules, why);
3379 POOL_DEBUG(SAT_DEBUG_STATS, "solver statistics: %d learned rules, %d unsolvable, %d minimization steps\n", solv->stats_learned, solv->stats_unsolvable, minimizationsteps);
3381 POOL_DEBUG(SAT_DEBUG_STATS, "done solving.\n\n");
3387 /*-------------------------------------------------------------------
3391 * at this point, all rules that led to conflicts are disabled.
3392 * we re-enable all rules of a problem set but rule "sug", then
3393 * continue to disable more rules until there as again a solution.
3396 /* FIXME: think about conflicting assertions */
3399 refine_suggestion(Solver *solv, Queue *job, Id *problem, Id sug, Queue *refined, int essentialok)
3401 Pool *pool = solv->pool;
3407 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
3409 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "refine_suggestion start\n");
3410 for (i = 0; problem[i]; i++)
3412 if (problem[i] == sug)
3413 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "=> ");
3414 solver_printproblem(solv, problem[i]);
3417 queue_empty(refined);
3418 if (!essentialok && sug < 0 && (job->elements[-sug - 1] & SOLVER_ESSENTIAL) != 0)
3420 queue_init(&disabled);
3421 queue_push(refined, sug);
3423 /* re-enable all problem rules with the exception of "sug"(gestion) */
3427 for (i = 0; problem[i]; i++)
3428 if (problem[i] != sug)
3429 enableproblem(solv, problem[i]);
3432 reenablepolicyrules(solv, job, -(sug + 1));
3433 else if (sug >= solv->updaterules && sug < solv->updaterules_end)
3435 /* enable feature rule */
3436 Rule *r = solv->rules + solv->featurerules + (sug - solv->updaterules);
3438 enablerule(solv, r);
3441 enableweakrules(solv);
3445 int njob, nfeature, nupdate;
3446 queue_empty(&solv->problems);
3447 revert(solv, 1); /* XXX no longer needed? */
3450 if (!solv->problems.count)
3451 run_solver(solv, 0, 0);
3453 if (!solv->problems.count)
3455 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "no more problems!\n");
3456 IF_POOLDEBUG (SAT_DEBUG_SCHUBI)
3457 solver_printdecisions(solv);
3458 break; /* great, no more problems */
3460 disabledcnt = disabled.count;
3461 /* start with 1 to skip over proof index */
3462 njob = nfeature = nupdate = 0;
3463 for (i = 1; i < solv->problems.count - 1; i++)
3465 /* ignore solutions in refined */
3466 v = solv->problems.elements[i];
3468 break; /* end of problem reached */
3469 for (j = 0; problem[j]; j++)
3470 if (problem[j] != sug && problem[j] == v)
3474 if (v >= solv->featurerules && v < solv->featurerules_end)
3480 if (!essentialok && (job->elements[-v -1] & SOLVER_ESSENTIAL) != 0)
3481 continue; /* not that one! */
3484 queue_push(&disabled, v);
3486 if (disabled.count == disabledcnt)
3488 /* no solution found, this was an invalid suggestion! */
3489 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "no solution found!\n");
3493 if (!njob && nupdate && nfeature)
3495 /* got only update rules, filter out feature rules */
3496 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "throwing away feature rules\n");
3497 for (i = j = disabledcnt; i < disabled.count; i++)
3499 v = disabled.elements[i];
3500 if (v < solv->featurerules || v >= solv->featurerules_end)
3501 disabled.elements[j++] = v;
3506 if (disabled.count == disabledcnt + 1)
3508 /* just one suggestion, add it to refined list */
3509 v = disabled.elements[disabledcnt];
3511 queue_push(refined, v); /* do not record feature rules */
3512 disableproblem(solv, v);
3513 if (v >= solv->updaterules && v < solv->updaterules_end)
3515 Rule *r = solv->rules + (v - solv->updaterules + solv->featurerules);
3517 enablerule(solv, r); /* enable corresponding feature rule */
3520 reenablepolicyrules(solv, job, -(v + 1));
3524 /* more than one solution, disable all */
3525 /* do not push anything on refine list, as we do not know which solution to choose */
3526 /* thus, the user will get another problem if he selects this solution, where he
3527 * can choose the right one */
3528 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
3530 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "more than one solution found:\n");
3531 for (i = disabledcnt; i < disabled.count; i++)
3532 solver_printproblem(solv, disabled.elements[i]);
3534 for (i = disabledcnt; i < disabled.count; i++)
3536 v = disabled.elements[i];
3537 disableproblem(solv, v);
3538 if (v >= solv->updaterules && v < solv->updaterules_end)
3540 Rule *r = solv->rules + (v - solv->updaterules + solv->featurerules);
3542 enablerule(solv, r);
3547 /* all done, get us back into the same state as before */
3548 /* enable refined rules again */
3549 for (i = 0; i < disabled.count; i++)
3550 enableproblem(solv, disabled.elements[i]);
3551 queue_free(&disabled);
3552 /* reset policy rules */
3553 for (i = 0; problem[i]; i++)
3554 enableproblem(solv, problem[i]);
3555 disablepolicyrules(solv, job);
3556 /* disable problem rules again */
3557 for (i = 0; problem[i]; i++)
3558 disableproblem(solv, problem[i]);
3559 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "refine_suggestion end\n");
3563 /*-------------------------------------------------------------------
3564 * sorting helper for problems
3566 * bring update rules before job rules
3567 * make essential job rules last
3571 problems_sortcmp(const void *ap, const void *bp, void *dp)
3574 Id a = *(Id *)ap, b = *(Id *)bp;
3581 int af = job->elements[-a - 1] & SOLVER_ESSENTIAL;
3582 int bf = job->elements[-b - 1] & SOLVER_ESSENTIAL;
3591 * convert a solution rule into a job modifier
3594 convertsolution(Solver *solv, Id why, Queue *solutionq)
3596 Pool *pool = solv->pool;
3599 queue_push(solutionq, 0);
3600 queue_push(solutionq, -why);
3603 if (why >= solv->infarchrules && why < solv->infarchrules_end)
3606 /* infarch rule, find replacement */
3607 assert(solv->rules[why].p < 0);
3608 name = pool->solvables[-solv->rules[why].p].name;
3609 while (why > solv->infarchrules && pool->solvables[-solv->rules[why - 1].p].name == name)
3612 for (; why < solv->infarchrules_end && pool->solvables[-solv->rules[why].p].name == name; why++)
3613 if (solv->decisionmap[-solv->rules[why].p] > 0)
3615 p = -solv->rules[why].p;
3619 p = -solv->rules[why].p; /* XXX: what to do here? */
3620 queue_push(solutionq, SOLVER_SOLUTION_INFARCH);
3621 queue_push(solutionq, p);
3624 if (why >= solv->duprules && why < solv->duprules_end)
3627 /* dist upgrade rule, find replacement */
3628 assert(solv->rules[why].p < 0);
3629 name = pool->solvables[-solv->rules[why].p].name;
3630 while (why > solv->duprules && pool->solvables[-solv->rules[why - 1].p].name == name)
3633 for (; why < solv->duprules_end && pool->solvables[-solv->rules[why].p].name == name; why++)
3634 if (solv->decisionmap[-solv->rules[why].p] > 0)
3636 p = -solv->rules[why].p;
3640 p = -solv->rules[why].p; /* XXX: what to do here? */
3641 queue_push(solutionq, SOLVER_SOLUTION_DISTUPGRADE);
3642 queue_push(solutionq, p);
3645 if (why >= solv->updaterules && why < solv->updaterules_end)
3647 /* update rule, find replacement package */
3651 assert(why >= solv->updaterules && why < solv->updaterules_end);
3652 /* check if this is a false positive, i.e. the update rule is fulfilled */
3653 rr = solv->rules + why;
3654 FOR_RULELITERALS(p, dp, rr)
3655 if (p > 0 && solv->decisionmap[p] > 0)
3658 return; /* false alarm */
3660 p = solv->installed->start + (why - solv->updaterules);
3661 rr = solv->rules + solv->featurerules + (why - solv->updaterules);
3663 rr = solv->rules + why;
3664 if (solv->distupgrade && solv->rules[why].p != p && solv->decisionmap[p] > 0)
3666 /* distupgrade case, allow to keep old package */
3667 queue_push(solutionq, p);
3668 queue_push(solutionq, p);
3671 if (solv->decisionmap[p] > 0)
3672 return; /* false alarm, turned out we can keep the package */
3675 int mvrp = 0; /* multi-version replacement */
3676 FOR_RULELITERALS(rp, dp, rr)
3678 if (rp > 0 && solv->decisionmap[rp] > 0 && pool->solvables[rp].repo != solv->installed)
3681 if (!(solv->noobsoletes.size && MAPTST(&solv->noobsoletes, rp)))
3687 /* found only multi-version replacements */
3688 /* have to split solution into two parts */
3689 queue_push(solutionq, p);
3690 queue_push(solutionq, mvrp);
3693 queue_push(solutionq, p);
3694 queue_push(solutionq, rp);
3700 * convert problem data into a form usable for refining.
3701 * Returns the number of problems.
3704 prepare_solutions(Solver *solv)
3706 int i, j = 1, idx = 1;
3708 if (!solv->problems.count)
3710 queue_push(&solv->solutions, 0);
3711 queue_push(&solv->solutions, -1); /* unrefined */
3712 for (i = 1; i < solv->problems.count; i++)
3714 Id p = solv->problems.elements[i];
3715 queue_push(&solv->solutions, p);
3718 solv->problems.elements[j++] = idx;
3719 if (i + 1 >= solv->problems.count)
3721 solv->problems.elements[j++] = solv->problems.elements[++i]; /* copy proofidx */
3722 idx = solv->solutions.count;
3723 queue_push(&solv->solutions, -1);
3725 solv->problems.count = j;
3730 * refine the simple solution rule list provided by
3731 * the solver into multiple lists of job modifiers.
3734 create_solutions(Solver *solv, int probnr, int solidx)
3736 Pool *pool = solv->pool;
3738 Queue problem, solution, problems_save;
3744 now = sat_timems(0);
3745 recocount = solv->recommendations.count;
3746 solv->recommendations.count = 0; /* so that revert() doesn't mess with it */
3748 /* save decisionq, decisionq_why, decisionmap */
3749 for (i = 0; i < solv->decisionq.count; i++)
3751 Id p = solv->decisionq.elements[i];
3752 queue_push(&redoq, p);
3753 queue_push(&redoq, solv->decisionq_why.elements[i]);
3754 queue_push(&redoq, solv->decisionmap[p > 0 ? p : -p]);
3756 /* save problems queue */
3757 problems_save = solv->problems;
3758 memset(&solv->problems, 0, sizeof(solv->problems));
3760 /* extract problem from queue */
3761 queue_init(&problem);
3762 for (i = solidx + 1; i < solv->solutions.count; i++)
3764 Id v = solv->solutions.elements[i];
3767 queue_push(&problem, v);
3769 if (problem.count > 1)
3770 sat_sort(problem.elements, problem.count, sizeof(Id), problems_sortcmp, &solv->job);
3771 queue_push(&problem, 0); /* mark end for refine_suggestion */
3774 for (i = 0; i < problem.count; i++)
3775 printf("PP %d %d\n", i, problem.elements[i]);
3778 /* refine each solution element */
3781 queue_init(&solution);
3782 for (i = 0; i < problem.count; i++)
3784 int solstart = solv->solutions.count;
3785 refine_suggestion(solv, &solv->job, problem.elements, problem.elements[i], &solution, essentialok);
3786 queue_push(&solv->solutions, 0); /* reserve room for number of elements */
3787 for (j = 0; j < solution.count; j++)
3788 convertsolution(solv, solution.elements[j], &solv->solutions);
3789 if (solv->solutions.count == solstart + 1)
3791 solv->solutions.count--;
3792 if (!essentialok && i + 1 == problem.count)
3794 /* nothing found, start over */
3800 /* patch in number of solution elements */
3801 solv->solutions.elements[solstart] = (solv->solutions.count - (solstart + 1)) / 2;
3802 queue_push(&solv->solutions, 0); /* add end marker */
3803 queue_push(&solv->solutions, 0); /* add end marker */
3804 solv->solutions.elements[solidx + 1 + nsol++] = solstart;
3806 solv->solutions.elements[solidx + 1 + nsol] = 0; /* end marker */
3807 solv->solutions.elements[solidx] = nsol;
3808 queue_free(&problem);
3809 queue_free(&solution);
3811 /* restore decisions */
3812 memset(solv->decisionmap, 0, pool->nsolvables * sizeof(Id));
3813 queue_empty(&solv->decisionq);
3814 queue_empty(&solv->decisionq_why);
3815 for (i = 0; i < redoq.count; i += 3)
3817 Id p = redoq.elements[i];
3818 queue_push(&solv->decisionq, p);
3819 queue_push(&solv->decisionq_why, redoq.elements[i + 1]);
3820 solv->decisionmap[p > 0 ? p : -p] = redoq.elements[i + 2];
3822 solv->recommendations.count = recocount;
3824 /* restore problems */
3825 queue_free(&solv->problems);
3826 solv->problems = problems_save;
3827 POOL_DEBUG(SAT_DEBUG_STATS, "create_solutions for problem #%d took %d ms\n", probnr, sat_timems(now));
3831 /**************************************************************************/
3834 solver_problem_count(Solver *solv)
3836 return solv->problems.count / 2;
3840 solver_next_problem(Solver *solv, Id problem)
3843 return solv->problems.count ? 1 : 0;
3844 return (problem + 1) * 2 - 1 < solv->problems.count ? problem + 1 : 0;
3848 solver_solution_count(Solver *solv, Id problem)
3850 Id solidx = solv->problems.elements[problem * 2 - 1];
3851 if (solv->solutions.elements[solidx] < 0)
3852 create_solutions(solv, problem, solidx);
3853 return solv->solutions.elements[solidx];
3857 solver_next_solution(Solver *solv, Id problem, Id solution)
3859 Id solidx = solv->problems.elements[problem * 2 - 1];
3860 if (solv->solutions.elements[solidx] < 0)
3861 create_solutions(solv, problem, solidx);
3862 return solv->solutions.elements[solidx + solution + 1] ? solution + 1 : 0;
3866 solver_solutionelement_count(Solver *solv, Id problem, Id solution)
3868 Id solidx = solv->problems.elements[problem * 2 - 1];
3869 solidx = solv->solutions.elements[solidx + solution];
3870 return solv->solutions.elements[solidx];
3875 * return the next item of the proposed solution
3876 * here are the possibilities for p / rp and what
3877 * the solver expects the application to do:
3879 * -------------------------------------------------------
3880 * SOLVER_SOLUTION_INFARCH pkgid
3881 * -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job
3882 * SOLVER_SOLUTION_DISTUPGRADE pkgid
3883 * -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job
3884 * SOLVER_SOLUTION_JOB jobidx
3885 * -> remove job (jobidx - 1, jobidx) from job queue
3887 * -> add (SOLVER_ERASE|SOLVER_SOLVABLE, p) to the job
3888 * pkgid (> 0) pkgid (> 0)
3889 * -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job
3890 * (this will replace package p)
3892 * Thus, the solver will either ask the application to remove
3893 * a specific job from the job queue, or ask to add an install/erase
3899 solver_next_solutionelement(Solver *solv, Id problem, Id solution, Id element, Id *p, Id *rp)
3901 Id solidx = solv->problems.elements[problem * 2 - 1];
3902 solidx = solv->solutions.elements[solidx + solution];
3905 solidx += 1 + element * 2;
3906 if (!solv->solutions.elements[solidx] && !solv->solutions.elements[solidx + 1])
3908 *p = solv->solutions.elements[solidx];
3909 *rp = solv->solutions.elements[solidx + 1];
3913 /*-------------------------------------------------------------------
3919 findproblemrule_internal(Solver *solv, Id idx, Id *reqrp, Id *conrp, Id *sysrp, Id *jobrp)
3922 Id lreqr, lconr, lsysr, ljobr;
3926 lreqr = lconr = lsysr = ljobr = 0;
3927 while ((rid = solv->learnt_pool.elements[idx++]) != 0)
3930 if (rid >= solv->learntrules)
3931 findproblemrule_internal(solv, solv->learnt_why.elements[rid - solv->learntrules], &lreqr, &lconr, &lsysr, &ljobr);
3932 else if ((rid >= solv->jobrules && rid < solv->jobrules_end) || (rid >= solv->infarchrules && rid < solv->infarchrules_end) || (rid >= solv->duprules && rid < solv->duprules_end))
3937 else if (rid >= solv->updaterules && rid < solv->updaterules_end)
3944 assert(rid < solv->rpmrules_end);
3945 r = solv->rules + rid;
3946 d = r->d < 0 ? -r->d - 1 : r->d;
3947 if (!d && r->w2 < 0)
3954 if (!d && r->w2 == 0 && !reqassert)
3956 if (*reqrp > 0 && r->p < -1)
3958 Id op = -solv->rules[*reqrp].p;
3959 if (op > 1 && solv->pool->solvables[op].arch != solv->pool->solvables[-r->p].arch)
3960 continue; /* different arch, skip */
3962 /* prefer assertions */
3968 else if (solv->installed && r->p < 0 && solv->pool->solvables[-r->p].repo == solv->installed && !reqassert)
3970 /* prefer rules of installed packages */
3976 if (!*reqrp && lreqr)
3978 if (!*conrp && lconr)
3980 if (!*jobrp && ljobr)
3982 if (!*sysrp && lsysr)
3989 * search for a rule that describes the problem to the
3990 * user. Actually a pretty hopeless task that may leave the user
3991 * puzzled. To get all of the needed information use
3992 * solver_findallproblemrules() instead.
3996 solver_findproblemrule(Solver *solv, Id problem)
3998 Id reqr, conr, sysr, jobr;
3999 Id idx = solv->problems.elements[2 * problem - 2];
4000 reqr = conr = sysr = jobr = 0;
4001 findproblemrule_internal(solv, idx, &reqr, &conr, &sysr, &jobr);
4003 return reqr; /* some requires */
4005 return conr; /* some conflict */
4007 return sysr; /* an update rule */
4009 return jobr; /* a user request */
4013 /*-------------------------------------------------------------------*/
4016 findallproblemrules_internal(Solver *solv, Id idx, Queue *rules)
4019 while ((rid = solv->learnt_pool.elements[idx++]) != 0)
4021 if (rid >= solv->learntrules)
4023 findallproblemrules_internal(solv, solv->learnt_why.elements[rid - solv->learntrules], rules);
4026 queue_pushunique(rules, rid);
4031 * find all problem rule
4033 * return all rules that lead to the problem. This gives the user
4034 * all of the information to understand the problem, but the result
4035 * can be a large number of rules.
4039 solver_findallproblemrules(Solver *solv, Id problem, Queue *rules)
4042 findallproblemrules_internal(solv, solv->problems.elements[2 * problem - 2], rules);
4046 /*-------------------------------------------------------------------
4048 * remove disabled conflicts
4050 * purpose: update the decisionmap after some rules were disabled.
4051 * this is used to calculate the suggested/recommended package list.
4052 * Also returns a "removed" list to undo the discisionmap changes.
4056 removedisabledconflicts(Solver *solv, Queue *removed)
4058 Pool *pool = solv->pool;
4063 Id *decisionmap = solv->decisionmap;
4065 POOL_DEBUG(SAT_DEBUG_SCHUBI, "removedisabledconflicts\n");
4066 queue_empty(removed);
4067 for (i = 0; i < solv->decisionq.count; i++)
4069 p = solv->decisionq.elements[i];
4072 /* a conflict. we never do conflicts on free decisions, so there
4073 * must have been an unit rule */
4074 why = solv->decisionq_why.elements[i];
4076 r = solv->rules + why;
4077 if (r->d < 0 && decisionmap[-p])
4079 /* rule is now disabled, remove from decisionmap */
4080 POOL_DEBUG(SAT_DEBUG_SCHUBI, "removing conflict for package %s[%d]\n", solvid2str(pool, -p), -p);
4081 queue_push(removed, -p);
4082 queue_push(removed, decisionmap[-p]);
4083 decisionmap[-p] = 0;
4086 if (!removed->count)
4088 /* we removed some confliced packages. some of them might still
4089 * be in conflict, so search for unit rules and re-conflict */
4091 for (i = n = 1, r = solv->rules + i; n < solv->nrules; i++, r++, n++)
4093 if (i == solv->nrules)
4096 r = solv->rules + i;
4102 if (r->p < 0 && !decisionmap[-r->p])
4108 if (r->p < 0 && decisionmap[-r->p] == 0 && DECISIONMAP_FALSE(r->w2))
4110 else if (r->w2 < 0 && decisionmap[-r->w2] == 0 && DECISIONMAP_FALSE(r->p))
4115 if (r->p < 0 && decisionmap[-r->p] == 0)
4117 if (new || DECISIONMAP_FALSE(r->p))
4119 dp = pool->whatprovidesdata + r->d;
4120 while ((p = *dp++) != 0)
4122 if (new && p == new)
4124 if (p < 0 && decisionmap[-p] == 0)
4133 else if (!DECISIONMAP_FALSE(p))
4143 POOL_DEBUG(SAT_DEBUG_SCHUBI, "re-conflicting package %s[%d]\n", solvid2str(pool, -new), -new);
4144 decisionmap[-new] = -1;
4146 n = 0; /* redo all rules */
4152 undo_removedisabledconflicts(Solver *solv, Queue *removed)
4155 for (i = 0; i < removed->count; i += 2)
4156 solv->decisionmap[removed->elements[i]] = removed->elements[i + 1];
4160 /*-------------------------------------------------------------------
4162 * weaken solvable dependencies
4166 weaken_solvable_deps(Solver *solv, Id p)
4171 for (i = 1, r = solv->rules + i; i < solv->rpmrules_end; i++, r++)
4175 if ((r->d == 0 || r->d == -1) && r->w2 < 0)
4176 continue; /* conflict */
4177 queue_push(&solv->weakruleq, i);
4182 /********************************************************************/
4187 addinfarchrules(Solver *solv, Map *addedmap)
4189 Pool *pool = solv->pool;
4191 Id p, pp, a, aa, bestarch;
4192 Solvable *s, *ps, *bests;
4193 Queue badq, allowedarchs;
4196 queue_init(&allowedarchs);
4197 solv->infarchrules = solv->nrules;
4198 for (i = 1; i < pool->nsolvables; i++)
4200 if (i == SYSTEMSOLVABLE || !MAPTST(addedmap, i))
4202 s = pool->solvables + i;
4206 queue_empty(&allowedarchs);
4207 FOR_PROVIDES(p, pp, s->name)
4209 ps = pool->solvables + p;
4210 if (ps->name != s->name || !MAPTST(addedmap, p))
4217 a = (a <= pool->lastarch) ? pool->id2arch[a] : 0;
4218 if (a != 1 && pool->installed && ps->repo == pool->installed)
4220 if (!solv->distupgrade)
4221 queue_pushunique(&allowedarchs, ps->arch); /* also ok to keep this architecture */
4222 continue; /* ignore installed solvables when calculating the best arch */
4224 if (a && a != 1 && (!bestarch || a < bestarch))
4232 /* speed up common case where installed package already has best arch */
4233 if (allowedarchs.count == 1 && bests && allowedarchs.elements[0] == bests->arch)
4234 allowedarchs.count--; /* installed arch is best */
4236 FOR_PROVIDES(p, pp, s->name)
4238 ps = pool->solvables + p;
4239 if (ps->name != s->name || !MAPTST(addedmap, p))
4242 a = (a <= pool->lastarch) ? pool->id2arch[a] : 0;
4243 if (a != 1 && bestarch && ((a ^ bestarch) & 0xffff0000) != 0)
4245 for (j = 0; j < allowedarchs.count; j++)
4247 aa = allowedarchs.elements[j];
4250 aa = (aa <= pool->lastarch) ? pool->id2arch[aa] : 0;
4251 if (aa && ((a ^ aa) & 0xffff0000) == 0)
4252 break; /* compatible */
4254 if (j == allowedarchs.count)
4255 queue_push(&badq, p);
4260 /* block all solvables in the badq! */
4261 for (j = 0; j < badq.count; j++)
4263 p = badq.elements[j];
4264 addrule(solv, -p, 0);
4268 queue_free(&allowedarchs);
4269 solv->infarchrules_end = solv->nrules;
4273 createdupmaps(Solver *solv, Queue *job)
4275 Pool *pool = solv->pool;
4277 Id how, what, p, pi, pp, obs, *obsp;
4281 map_init(&solv->dupmap, pool->nsolvables);
4282 map_init(&solv->dupinvolvedmap, pool->nsolvables);
4283 for (i = 0; i < job->count; i += 2)
4285 how = job->elements[i];
4286 what = job->elements[i + 1];
4287 switch (how & SOLVER_JOBMASK)
4289 case SOLVER_DISTUPGRADE:
4290 if (what < 0 || what > pool->nrepos)
4292 repo = pool->repos[what];
4293 FOR_REPO_SOLVABLES(repo, p, s)
4295 MAPSET(&solv->dupmap, p);
4296 FOR_PROVIDES(pi, pp, s->name)
4298 ps = pool->solvables + pi;
4299 if (ps->name != s->name)
4301 MAPSET(&solv->dupinvolvedmap, pi);
4305 /* FIXME: check obsoletes/provides combination */
4306 obsp = s->repo->idarraydata + s->obsoletes;
4307 while ((obs = *obsp++) != 0)
4309 FOR_PROVIDES(pi, pp, obs)
4311 if (!solv->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + pi, obs))
4313 MAPSET(&solv->dupinvolvedmap, pi);
4323 MAPCLR(&solv->dupinvolvedmap, SYSTEMSOLVABLE);
4327 freedupmaps(Solver *solv)
4329 map_free(&solv->dupmap);
4330 map_free(&solv->dupinvolvedmap);
4334 addduprules(Solver *solv, Map *addedmap)
4336 Pool *pool = solv->pool;
4341 solv->duprules = solv->nrules;
4342 for (i = 1; i < pool->nsolvables; i++)
4344 if (i == SYSTEMSOLVABLE || !MAPTST(addedmap, i))
4346 s = pool->solvables + i;
4348 FOR_PROVIDES(p, pp, s->name)
4350 ps = pool->solvables + p;
4351 if (ps->name != s->name || !MAPTST(addedmap, p))
4357 if (!MAPTST(&solv->dupinvolvedmap, p))
4359 if (solv->installed && ps->repo == solv->installed)
4361 if (!solv->updatemap.size)
4362 map_init(&solv->updatemap, pool->nsolvables);
4363 MAPSET(&solv->updatemap, p);
4364 if (!MAPTST(&solv->dupmap, p))
4367 /* is installed identical to a good one? */
4368 FOR_PROVIDES(ip, ipp, s->name)
4370 Solvable *is = pool->solvables + ip;
4371 if (!MAPTST(&solv->dupmap, ip))
4373 if (is->evr == s->evr && solvable_identical(s, is))
4377 addrule(solv, -p, 0); /* no match, sorry */
4380 else if (!MAPTST(&solv->dupmap, p))
4381 addrule(solv, -p, 0);
4384 solv->duprules_end = solv->nrules;
4389 findrecommendedsuggested(Solver *solv)
4391 Pool *pool = solv->pool;
4392 Queue redoq, disabledq;
4398 map_init(&obsmap, pool->nsolvables);
4399 if (solv->installed)
4401 Id obs, *obsp, p, po, ppo;
4402 for (p = solv->installed->start; p < solv->installed->end; p++)
4404 s = pool->solvables + p;
4405 if (s->repo != solv->installed || !s->obsoletes)
4407 if (solv->decisionmap[p] <= 0)
4409 if (solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p))
4411 obsp = s->repo->idarraydata + s->obsoletes;
4412 /* foreach obsoletes */
4413 while ((obs = *obsp++) != 0)
4414 FOR_PROVIDES(po, ppo, obs)
4415 MAPSET(&obsmap, po);
4420 queue_init(&disabledq);
4422 /* disable all erase jobs (including weak "keep uninstalled" rules) */
4423 for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++)
4425 if (r->d < 0) /* disabled ? */
4427 if (r->p >= 0) /* install job? */
4429 queue_push(&disabledq, i);
4430 disablerule(solv, r);
4436 enabledisablelearntrules(solv);
4437 removedisabledconflicts(solv, &redoq);
4441 * find recommended packages
4444 /* if redoq.count == 0 we already found all recommended in the
4446 if (redoq.count || solv->dontinstallrecommended || !solv->dontshowinstalledrecommended || solv->ignorealreadyrecommended)
4448 Id rec, *recp, p, pp;
4450 /* create map of all recommened packages */
4451 solv->recommends_index = -1;
4452 MAPZERO(&solv->recommendsmap);
4453 for (i = 0; i < solv->decisionq.count; i++)
4455 p = solv->decisionq.elements[i];
4458 s = pool->solvables + p;
4461 recp = s->repo->idarraydata + s->recommends;
4462 while ((rec = *recp++) != 0)
4464 FOR_PROVIDES(p, pp, rec)
4465 if (solv->decisionmap[p] > 0)
4469 if (!solv->dontshowinstalledrecommended)
4471 FOR_PROVIDES(p, pp, rec)
4472 if (solv->decisionmap[p] > 0)
4473 MAPSET(&solv->recommendsmap, p);
4475 continue; /* p != 0: already fulfilled */
4477 FOR_PROVIDES(p, pp, rec)
4478 MAPSET(&solv->recommendsmap, p);
4482 for (i = 1; i < pool->nsolvables; i++)
4484 if (solv->decisionmap[i] < 0)
4486 if (solv->decisionmap[i] > 0 && solv->dontshowinstalledrecommended)
4488 if (MAPTST(&obsmap, i))
4490 s = pool->solvables + i;
4491 if (!MAPTST(&solv->recommendsmap, i))
4493 if (!s->supplements)
4495 if (!pool_installable(pool, s))
4497 if (!solver_is_supplementing(solv, s))
4500 if (solv->dontinstallrecommended)
4501 queue_push(&solv->recommendations, i);
4503 queue_pushunique(&solv->recommendations, i);
4505 /* we use MODE_SUGGEST here so that repo prio is ignored */
4506 policy_filter_unwanted(solv, &solv->recommendations, POLICY_MODE_SUGGEST);
4510 * find suggested packages
4515 Id sug, *sugp, p, pp;
4517 /* create map of all suggests that are still open */
4518 solv->recommends_index = -1;
4519 MAPZERO(&solv->suggestsmap);
4520 for (i = 0; i < solv->decisionq.count; i++)
4522 p = solv->decisionq.elements[i];
4525 s = pool->solvables + p;
4528 sugp = s->repo->idarraydata + s->suggests;
4529 while ((sug = *sugp++) != 0)
4531 FOR_PROVIDES(p, pp, sug)
4532 if (solv->decisionmap[p] > 0)
4536 if (!solv->dontshowinstalledrecommended)
4538 FOR_PROVIDES(p, pp, sug)
4539 if (solv->decisionmap[p] > 0)
4540 MAPSET(&solv->suggestsmap, p);
4542 continue; /* already fulfilled */
4544 FOR_PROVIDES(p, pp, sug)
4545 MAPSET(&solv->suggestsmap, p);
4549 for (i = 1; i < pool->nsolvables; i++)
4551 if (solv->decisionmap[i] < 0)
4553 if (solv->decisionmap[i] > 0 && solv->dontshowinstalledrecommended)
4555 if (MAPTST(&obsmap, i))
4557 s = pool->solvables + i;
4558 if (!MAPTST(&solv->suggestsmap, i))
4562 if (!pool_installable(pool, s))
4564 if (!solver_is_enhancing(solv, s))
4567 queue_push(&solv->suggestions, i);
4569 policy_filter_unwanted(solv, &solv->suggestions, POLICY_MODE_SUGGEST);
4572 /* undo removedisabledconflicts */
4574 undo_removedisabledconflicts(solv, &redoq);
4577 /* undo job rule disabling */
4578 for (i = 0; i < disabledq.count; i++)
4579 enablerule(solv, solv->rules + disabledq.elements[i]);
4580 queue_free(&disabledq);
4592 solver_solve(Solver *solv, Queue *job)
4594 Pool *pool = solv->pool;
4595 Repo *installed = solv->installed;
4598 Map addedmap; /* '1' == have rpm-rules for solvable */
4599 Map installcandidatemap;
4600 Id how, what, select, name, weak, p, pp, d;
4604 int now, solve_start;
4607 solve_start = sat_timems(0);
4609 /* log solver options */
4610 POOL_DEBUG(SAT_DEBUG_STATS, "solver started\n");
4611 POOL_DEBUG(SAT_DEBUG_STATS, "fixsystem=%d updatesystem=%d dosplitprovides=%d, noupdateprovide=%d noinfarchcheck=%d\n", solv->fixsystem, solv->updatesystem, solv->dosplitprovides, solv->noupdateprovide, solv->noinfarchcheck);
4612 POOL_DEBUG(SAT_DEBUG_STATS, "distupgrade=%d distupgrade_removeunsupported=%d\n", solv->distupgrade, solv->distupgrade_removeunsupported);
4613 POOL_DEBUG(SAT_DEBUG_STATS, "allowuninstall=%d, allowdowngrade=%d, allowarchchange=%d, allowvendorchange=%d\n", solv->allowuninstall, solv->allowdowngrade, solv->allowarchchange, solv->allowvendorchange);
4614 POOL_DEBUG(SAT_DEBUG_STATS, "promoteepoch=%d, allowvirtualconflicts=%d, allowselfconflicts=%d\n", pool->promoteepoch, solv->allowvirtualconflicts, solv->allowselfconflicts);
4615 POOL_DEBUG(SAT_DEBUG_STATS, "obsoleteusesprovides=%d, implicitobsoleteusesprovides=%d\n", solv->obsoleteusesprovides, solv->implicitobsoleteusesprovides);
4616 POOL_DEBUG(SAT_DEBUG_STATS, "dontinstallrecommended=%d, ignorealreadyrecommended=%d, dontshowinstalledrecommended=%d\n", solv->dontinstallrecommended, solv->ignorealreadyrecommended, solv->dontshowinstalledrecommended);
4618 /* create whatprovides if not already there */
4619 if (!pool->whatprovides)
4620 pool_createwhatprovides(pool);
4622 /* create obsolete index */
4623 policy_create_obsolete_index(solv);
4626 queue_free(&solv->job);
4627 queue_clone(&solv->job, job);
4630 * create basic rule set of all involved packages
4631 * use addedmap bitmap to make sure we don't create rules twice
4634 /* create noobsolete map if needed */
4635 for (i = 0; i < job->count; i += 2)
4637 how = job->elements[i] & ~SOLVER_WEAK;
4638 if ((how & SOLVER_JOBMASK) != SOLVER_NOOBSOLETES)
4640 what = job->elements[i + 1];
4641 select = how & SOLVER_SELECTMASK;
4642 if (!solv->noobsoletes.size)
4643 map_init(&solv->noobsoletes, pool->nsolvables);
4644 FOR_JOB_SELECT(p, pp, select, what)
4645 MAPSET(&solv->noobsoletes, p);
4648 map_init(&addedmap, pool->nsolvables);
4649 MAPSET(&addedmap, SYSTEMSOLVABLE);
4651 map_init(&installcandidatemap, pool->nsolvables);
4654 now = sat_timems(0);
4656 * create rules for all package that could be involved with the solving
4657 * so called: rpm rules
4662 oldnrules = solv->nrules;
4663 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for installed solvables ***\n");
4664 FOR_REPO_SOLVABLES(installed, p, s)
4665 addrpmrulesforsolvable(solv, s, &addedmap);
4666 POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for installed solvables\n", solv->nrules - oldnrules);
4667 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for updaters of installed solvables ***\n");
4668 oldnrules = solv->nrules;
4669 FOR_REPO_SOLVABLES(installed, p, s)
4670 addrpmrulesforupdaters(solv, s, &addedmap, 1);
4671 POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for updaters of installed solvables\n", solv->nrules - oldnrules);
4675 * create rules for all packages involved in the job
4676 * (to be installed or removed)
4679 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for packages involved with a job ***\n");
4680 oldnrules = solv->nrules;
4681 for (i = 0; i < job->count; i += 2)
4683 how = job->elements[i];
4684 what = job->elements[i + 1];
4685 select = how & SOLVER_SELECTMASK;
4687 switch (how & SOLVER_JOBMASK)
4689 case SOLVER_INSTALL:
4690 FOR_JOB_SELECT(p, pp, select, what)
4692 MAPSET(&installcandidatemap, p);
4693 addrpmrulesforsolvable(solv, pool->solvables + p, &addedmap);
4696 case SOLVER_DISTUPGRADE:
4697 if (!solv->distupgrade)
4704 POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for packages involved in a job\n", solv->nrules - oldnrules);
4706 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for recommended/suggested packages ***\n");
4708 oldnrules = solv->nrules;
4711 * add rules for suggests, enhances
4713 addrpmrulesforweak(solv, &addedmap);
4714 POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules because of weak dependencies\n", solv->nrules - oldnrules);
4716 IF_POOLDEBUG (SAT_DEBUG_STATS)
4718 int possible = 0, installable = 0;
4719 for (i = 1; i < pool->nsolvables; i++)
4721 if (pool_installable(pool, pool->solvables + i))
4723 if (MAPTST(&addedmap, i))
4726 POOL_DEBUG(SAT_DEBUG_STATS, "%d of %d installable solvables considered for solving\n", possible, installable);
4730 * first pass done, we now have all the rpm rules we need.
4731 * unify existing rules before going over all job rules and
4733 * at this point the system is always solvable,
4734 * as an empty system (remove all packages) is a valid solution
4737 unifyrules(solv); /* remove duplicate rpm rules */
4739 solv->rpmrules_end = solv->nrules; /* mark end of rpm rules */
4741 POOL_DEBUG(SAT_DEBUG_STATS, "rpm rule memory usage: %d K\n", solv->nrules * (int)sizeof(Rule) / 1024);
4742 POOL_DEBUG(SAT_DEBUG_STATS, "rpm rule creation took %d ms\n", sat_timems(now));
4744 /* create dup maps if needed. We need the maps early to create our
4747 createdupmaps(solv, job);
4750 * create feature rules
4752 * foreach installed:
4753 * create assertion (keep installed, if no update available)
4755 * create update rule (A|update1(A)|update2(A)|...)
4757 * those are used later on to keep a version of the installed packages in
4761 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** Add feature rules ***\n");
4762 solv->featurerules = solv->nrules; /* mark start of feature rules */
4765 /* foreach possibly installed solvable */
4766 for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
4768 if (s->repo != installed)
4770 addrule(solv, 0, 0); /* create dummy rule */
4773 addupdaterule(solv, s, 1); /* allow s to be updated */
4776 * assert one rule per installed solvable,
4777 * either an assertion (A)
4778 * or a possible update (A|update1(A)|update2(A)|...)
4780 assert(solv->nrules - solv->featurerules == installed->end - installed->start);
4782 solv->featurerules_end = solv->nrules;
4785 * Add update rules for installed solvables
4787 * almost identical to feature rules
4788 * except that downgrades/archchanges/vendorchanges are not allowed
4791 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** Add update rules ***\n");
4792 solv->updaterules = solv->nrules;
4795 { /* foreach installed solvables */
4796 /* we create all update rules, but disable some later on depending on the job */
4797 for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
4801 if (s->repo != installed)
4803 addrule(solv, 0, 0); /* create dummy rule */
4806 addupdaterule(solv, s, 0); /* allowall = 0: downgrades not allowed */
4808 * check for and remove duplicate
4810 r = solv->rules + solv->nrules - 1; /* r: update rule */
4811 sr = r - (installed->end - installed->start); /* sr: feature rule */
4812 /* it's orphaned if there is no feature rule or the feature rule
4813 * consists just of the installed package */
4814 if (!sr->p || (sr->p == i && !sr->d && !sr->w2))
4815 queue_push(&solv->orphaned, i);
4818 assert(solv->distupgrade && !sr->p);
4821 if (!unifyrules_sortcmp(r, sr, pool))
4823 /* identical rule, kill unneeded one */
4824 if (solv->allowuninstall)
4826 /* keep feature rule, make it weak */
4827 memset(r, 0, sizeof(*r));
4828 queue_push(&solv->weakruleq, sr - solv->rules);
4832 /* keep update rule */
4833 memset(sr, 0, sizeof(*sr));
4836 else if (solv->allowuninstall)
4838 /* make both feature and update rule weak */
4839 queue_push(&solv->weakruleq, r - solv->rules);
4840 queue_push(&solv->weakruleq, sr - solv->rules);
4843 disablerule(solv, sr);
4845 /* consistency check: we added a rule for _every_ installed solvable */
4846 assert(solv->nrules - solv->updaterules == installed->end - installed->start);
4848 solv->updaterules_end = solv->nrules;
4852 * now add all job rules
4855 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** Add JOB rules ***\n");
4857 solv->jobrules = solv->nrules;
4858 for (i = 0; i < job->count; i += 2)
4860 oldnrules = solv->nrules;
4862 how = job->elements[i];
4863 what = job->elements[i + 1];
4864 weak = how & SOLVER_WEAK;
4865 select = how & SOLVER_SELECTMASK;
4866 switch (how & SOLVER_JOBMASK)
4868 case SOLVER_INSTALL:
4869 POOL_DEBUG(SAT_DEBUG_JOB, "job: %sinstall %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
4870 if (select == SOLVER_SOLVABLE)
4878 FOR_JOB_SELECT(p, pp, select, what)
4882 /* no candidate found, make this an impossible rule */
4883 queue_push(&q, -SYSTEMSOLVABLE);
4885 p = queue_shift(&q); /* get first candidate */
4886 d = !q.count ? 0 : pool_queuetowhatprovides(pool, &q); /* internalize */
4888 addrule(solv, p, d); /* add install rule */
4889 queue_push(&solv->ruletojob, i);
4891 queue_push(&solv->weakruleq, solv->nrules - 1);
4894 POOL_DEBUG(SAT_DEBUG_JOB, "job: %serase %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
4895 if (select == SOLVER_SOLVABLE && solv->installed && pool->solvables[what].repo == solv->installed)
4897 /* special case for "erase a specific solvable": we also
4898 * erase all other solvables with that name, so that they
4899 * don't get picked up as replacement */
4900 name = pool->solvables[what].name;
4901 FOR_PROVIDES(p, pp, name)
4905 s = pool->solvables + p;
4906 if (s->name != name)
4908 /* keep other versions installed */
4909 if (s->repo == solv->installed)
4911 /* keep installcandidates of other jobs */
4912 if (MAPTST(&installcandidatemap, p))
4914 addrule(solv, -p, 0); /* remove by Id */
4915 queue_push(&solv->ruletojob, i);
4917 queue_push(&solv->weakruleq, solv->nrules - 1);
4920 FOR_JOB_SELECT(p, pp, select, what)
4922 addrule(solv, -p, 0);
4923 queue_push(&solv->ruletojob, i);
4925 queue_push(&solv->weakruleq, solv->nrules - 1);
4930 POOL_DEBUG(SAT_DEBUG_JOB, "job: %supdate %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
4931 FOR_JOB_SELECT(p, pp, select, what)
4933 s = pool->solvables + p;
4934 if (!solv->installed || s->repo != solv->installed)
4936 if (!solv->updatemap.size)
4937 map_init(&solv->updatemap, pool->nsolvables);
4938 MAPSET(&solv->updatemap, p);
4941 case SOLVER_WEAKENDEPS:
4942 POOL_DEBUG(SAT_DEBUG_JOB, "job: %sweaken deps %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
4943 if (select != SOLVER_SOLVABLE)
4945 s = pool->solvables + what;
4946 weaken_solvable_deps(solv, what);
4948 case SOLVER_NOOBSOLETES:
4949 POOL_DEBUG(SAT_DEBUG_JOB, "job: %sno obsolete %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
4952 POOL_DEBUG(SAT_DEBUG_JOB, "job: %slock %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
4953 FOR_JOB_SELECT(p, pp, select, what)
4955 s = pool->solvables + p;
4956 if (installed && s->repo == installed)
4957 addrule(solv, p, 0);
4959 addrule(solv, -p, 0);
4960 queue_push(&solv->ruletojob, i);
4962 queue_push(&solv->weakruleq, solv->nrules - 1);
4965 case SOLVER_DISTUPGRADE:
4966 POOL_DEBUG(SAT_DEBUG_JOB, "job: distupgrade repo #%d\n", what);
4969 POOL_DEBUG(SAT_DEBUG_JOB, "job: unknown job\n");
4977 IF_POOLDEBUG (SAT_DEBUG_JOB)
4980 if (solv->nrules == oldnrules)
4981 POOL_DEBUG(SAT_DEBUG_JOB, " - no rule created\n");
4982 for (j = oldnrules; j < solv->nrules; j++)
4984 POOL_DEBUG(SAT_DEBUG_JOB, " - job ");
4985 solver_printrule(solv, SAT_DEBUG_JOB, solv->rules + j);
4989 assert(solv->ruletojob.count == solv->nrules - solv->jobrules);
4990 solv->jobrules_end = solv->nrules;
4992 /* now create infarch and dup rules */
4993 if (!solv->noinfarchcheck)
4994 addinfarchrules(solv, &addedmap);
4996 solv->infarchrules = solv->infarchrules_end = solv->nrules;
5000 addduprules(solv, &addedmap);
5001 freedupmaps(solv); /* no longer needed */
5004 solv->duprules = solv->duprules_end = solv->nrules;
5007 /* all rules created
5008 * --------------------------------------------------------------
5009 * prepare for solving
5012 /* free unneeded memory */
5013 map_free(&addedmap);
5014 map_free(&installcandidatemap);
5017 POOL_DEBUG(SAT_DEBUG_STATS, "%d rpm rules, %d job rules, %d infarch rules, %d dup rules\n", solv->rpmrules_end - 1, solv->jobrules_end - solv->jobrules, solv->infarchrules_end - solv->infarchrules, solv->duprules_end - solv->duprules);
5019 /* create weak map */
5020 map_init(&solv->weakrulemap, solv->nrules);
5021 for (i = 0; i < solv->weakruleq.count; i++)
5023 p = solv->weakruleq.elements[i];
5024 MAPSET(&solv->weakrulemap, p);
5027 /* all new rules are learnt after this point */
5028 solv->learntrules = solv->nrules;
5030 /* create watches chains */
5033 /* create assertion index. it is only used to speed up
5034 * makeruledecsions() a bit */
5035 for (i = 1, r = solv->rules + i; i < solv->nrules; i++, r++)
5036 if (r->p && !r->w2 && (r->d == 0 || r->d == -1))
5037 queue_push(&solv->ruleassertions, i);
5039 /* disable update rules that conflict with our job */
5040 disablepolicyrules(solv, job);
5042 /* make decisions based on job/update assertions */
5043 makeruledecisions(solv);
5044 POOL_DEBUG(SAT_DEBUG_STATS, "problems so far: %d\n", solv->problems.count);
5047 * ********************************************
5049 * ********************************************
5052 now = sat_timems(0);
5053 run_solver(solv, 1, solv->dontinstallrecommended ? 0 : 1);
5054 POOL_DEBUG(SAT_DEBUG_STATS, "solver took %d ms\n", sat_timems(now));
5057 * calculate recommended/suggested packages
5059 findrecommendedsuggested(solv);
5062 * prepare solution queue if there were problems
5064 prepare_solutions(solv);
5067 * finally prepare transaction info
5069 solver_create_transaction(solv);
5071 POOL_DEBUG(SAT_DEBUG_STATS, "final solver statistics: %d problems, %d learned rules, %d unsolvable\n", solv->problems.count / 2, solv->stats_learned, solv->stats_unsolvable);
5072 POOL_DEBUG(SAT_DEBUG_STATS, "solver_solve took %d ms\n", sat_timems(solve_start));
5075 /***********************************************************************/
5076 /* disk usage computations */
5078 /*-------------------------------------------------------------------
5080 * calculate DU changes
5084 solver_calc_duchanges(Solver *solv, DUChanges *mps, int nmps)
5088 solver_create_state_maps(solv, &installedmap, 0);
5089 pool_calc_duchanges(solv->pool, &installedmap, mps, nmps);
5090 map_free(&installedmap);
5094 /*-------------------------------------------------------------------
5096 * calculate changes in install size
5100 solver_calc_installsizechange(Solver *solv)
5105 solver_create_state_maps(solv, &installedmap, 0);
5106 change = pool_calc_installsizechange(solv->pool, &installedmap);
5107 map_free(&installedmap);
5112 solver_trivial_installable(Solver *solv, Queue *pkgs, Queue *res)
5115 solver_create_state_maps(solv, &installedmap, 0);
5116 pool_trivial_installable_noobsoletesmap(solv->pool, &installedmap, pkgs, res, solv->noobsoletes.size ? &solv->noobsoletes : 0);
5117 map_free(&installedmap);
5121 #define FIND_INVOLVED_DEBUG 0
5123 solver_find_involved(Solver *solv, Queue *installedq, Solvable *ts, Queue *q)
5125 Pool *pool = solv->pool;
5130 Queue installedq_internal;
5131 Id tp, ip, p, pp, req, *reqp, sup, *supp;
5134 tp = ts - pool->solvables;
5136 queue_init(&installedq_internal);
5137 map_init(&im, pool->nsolvables);
5138 map_init(&installedm, pool->nsolvables);
5142 installedq = &installedq_internal;
5143 if (solv->installed)
5145 for (ip = solv->installed->start; ip < solv->installed->end; ip++)
5147 s = pool->solvables + ip;
5148 if (s->repo != solv->installed)
5150 queue_push(installedq, ip);
5154 for (i = 0; i < installedq->count; i++)
5156 ip = installedq->elements[i];
5157 MAPSET(&installedm, ip);
5161 queue_push(&iq, ts - pool->solvables);
5164 ip = queue_shift(&iq);
5165 if (!MAPTST(&im, ip))
5167 if (!MAPTST(&installedm, ip))
5170 s = pool->solvables + ip;
5171 #if FIND_INVOLVED_DEBUG
5172 printf("hello %s\n", solvable2str(pool, s));
5176 reqp = s->repo->idarraydata + s->requires;
5177 while ((req = *reqp++) != 0)
5179 if (req == SOLVABLE_PREREQMARKER)
5181 /* count number of installed packages that match */
5183 FOR_PROVIDES(p, pp, req)
5184 if (MAPTST(&installedm, p))
5188 FOR_PROVIDES(p, pp, req)
5192 #if FIND_INVOLVED_DEBUG
5193 printf("%s requires %s\n", solvid2str(pool, ip), solvid2str(pool, p));
5202 reqp = s->repo->idarraydata + s->recommends;
5203 while ((req = *reqp++) != 0)
5206 FOR_PROVIDES(p, pp, req)
5207 if (MAPTST(&installedm, p))
5211 FOR_PROVIDES(p, pp, req)
5215 #if FIND_INVOLVED_DEBUG
5216 printf("%s recommends %s\n", solvid2str(pool, ip), solvid2str(pool, p));
5225 /* supplements pass */
5226 for (i = 0; i < installedq->count; i++)
5228 ip = installedq->elements[i];
5229 s = pool->solvables + ip;
5230 if (!s->supplements)
5232 if (!MAPTST(&im, ip))
5234 supp = s->repo->idarraydata + s->supplements;
5235 while ((sup = *supp++) != 0)
5236 if (!dep_possible(solv, sup, &im) && dep_possible(solv, sup, &installedm))
5238 /* no longer supplemented, also erase */
5241 #if FIND_INVOLVED_DEBUG
5242 printf("%s supplemented\n", solvid2str(pool, ip));
5244 queue_push(&iq, ip);
5250 for (i = 0; i < installedq->count; i++)
5252 ip = installedq->elements[i];
5253 if (MAPTST(&im, ip))
5254 queue_push(&iq, ip);
5259 ip = queue_shift(&iq);
5260 if (!MAPTST(&installedm, ip))
5262 s = pool->solvables + ip;
5263 #if FIND_INVOLVED_DEBUG
5264 printf("bye %s\n", solvable2str(pool, s));
5268 reqp = s->repo->idarraydata + s->requires;
5269 while ((req = *reqp++) != 0)
5271 FOR_PROVIDES(p, pp, req)
5273 if (!MAPTST(&im, p))
5277 #if FIND_INVOLVED_DEBUG
5278 printf("%s requires %s\n", solvid2str(pool, ip), solvid2str(pool, p));
5288 reqp = s->repo->idarraydata + s->recommends;
5289 while ((req = *reqp++) != 0)
5291 FOR_PROVIDES(p, pp, req)
5293 if (!MAPTST(&im, p))
5297 #if FIND_INVOLVED_DEBUG
5298 printf("%s recommends %s\n", solvid2str(pool, ip), solvid2str(pool, p));
5308 /* supplements pass */
5309 for (i = 0; i < installedq->count; i++)
5311 ip = installedq->elements[i];
5314 s = pool->solvables + ip;
5315 if (!s->supplements)
5317 if (MAPTST(&im, ip))
5319 supp = s->repo->idarraydata + s->supplements;
5320 while ((sup = *supp++) != 0)
5321 if (dep_possible(solv, sup, &im))
5325 #if FIND_INVOLVED_DEBUG
5326 printf("%s supplemented\n", solvid2str(pool, ip));
5329 queue_push(&iq, ip);
5337 /* convert map into result */
5338 for (i = 0; i < installedq->count; i++)
5340 ip = installedq->elements[i];
5341 if (MAPTST(&im, ip))
5343 if (ip == ts - pool->solvables)
5348 map_free(&installedm);
5349 queue_free(&installedq_internal);
5354 addrpmruleinfo(Solver *solv, Id p, Id d, int type, Id dep)
5356 Pool *pool = solv->pool;
5360 /* check if this creates the rule we're searching for */
5361 r = solv->rules + solv->ruleinfoq->elements[0];
5363 od = r->d < 0 ? -r->d - 1 : r->d;
5368 if (p < 0 && d > 0 && (!pool->whatprovidesdata[d] || !pool->whatprovidesdata[d + 1]))
5370 w2 = pool->whatprovidesdata[d];
5374 if (p > 0 && d < 0) /* this hack is used for buddy deps */
5386 Id *dp = pool->whatprovidesdata + d;
5387 Id *odp = pool->whatprovidesdata + od;
5389 if (*dp++ != *odp++)
5395 /* handle multiversion conflict rules */
5396 if (p < 0 && pool->whatprovidesdata[d] < 0)
5398 w2 = pool->whatprovidesdata[d];
5399 /* XXX: free memory */
5409 if (w2 != op || p != ow2)
5414 if (p != op || w2 != ow2)
5418 /* yep, rule matches. record info */
5419 queue_push(solv->ruleinfoq, type);
5420 if (type == SOLVER_RULE_RPM_SAME_NAME)
5422 /* we normalize same name order */
5423 queue_push(solv->ruleinfoq, op < 0 ? -op : 0);
5424 queue_push(solv->ruleinfoq, ow2 < 0 ? -ow2 : 0);
5428 queue_push(solv->ruleinfoq, p < 0 ? -p : 0);
5429 queue_push(solv->ruleinfoq, w2 < 0 ? -w2 : 0);
5431 queue_push(solv->ruleinfoq, dep);
5435 solver_allruleinfos_cmp(const void *ap, const void *bp, void *dp)
5437 const Id *a = ap, *b = bp;
5456 solver_allruleinfos(Solver *solv, Id rid, Queue *rq)
5458 Pool *pool = solv->pool;
5459 Rule *r = solv->rules + rid;
5463 if (rid <= 0 || rid >= solv->rpmrules_end)
5465 Id type, from, to, dep;
5466 type = solver_ruleinfo(solv, rid, &from, &to, &dep);
5467 queue_push(rq, type);
5468 queue_push(rq, from);
5470 queue_push(rq, dep);
5475 queue_push(rq, rid);
5476 solv->ruleinfoq = rq;
5477 addrpmrulesforsolvable(solv, pool->solvables - r->p, 0);
5478 /* also try reverse direction for conflicts */
5479 if ((r->d == 0 || r->d == -1) && r->w2 < 0)
5480 addrpmrulesforsolvable(solv, pool->solvables - r->w2, 0);
5481 solv->ruleinfoq = 0;
5483 /* now sort & unify em */
5486 sat_sort(rq->elements, rq->count / 4, 4 * sizeof(Id), solver_allruleinfos_cmp, 0);
5487 /* throw out identical entries */
5488 for (i = j = 0; i < rq->count; i += 4)
5492 if (rq->elements[i] == rq->elements[j - 4] &&
5493 rq->elements[i + 1] == rq->elements[j - 3] &&
5494 rq->elements[i + 2] == rq->elements[j - 2] &&
5495 rq->elements[i + 3] == rq->elements[j - 1])
5498 rq->elements[j++] = rq->elements[i];
5499 rq->elements[j++] = rq->elements[i + 1];
5500 rq->elements[j++] = rq->elements[i + 2];
5501 rq->elements[j++] = rq->elements[i + 3];
5508 solver_ruleinfo(Solver *solv, Id rid, Id *fromp, Id *top, Id *depp)
5510 Pool *pool = solv->pool;
5511 Rule *r = solv->rules + rid;
5512 SolverRuleinfo type = SOLVER_RULE_UNKNOWN;
5520 if (rid > 0 && rid < solv->rpmrules_end)
5526 return SOLVER_RULE_RPM;
5530 queue_push(&rq, rid);
5531 solv->ruleinfoq = &rq;
5532 addrpmrulesforsolvable(solv, pool->solvables - r->p, 0);
5533 /* also try reverse direction for conflicts */
5534 if ((r->d == 0 || r->d == -1) && r->w2 < 0)
5535 addrpmrulesforsolvable(solv, pool->solvables - r->w2, 0);
5536 solv->ruleinfoq = 0;
5537 type = SOLVER_RULE_RPM;
5538 for (i = 1; i < rq.count; i += 4)
5541 qt = rq.elements[i];
5542 qp = rq.elements[i + 1];
5543 qo = rq.elements[i + 2];
5544 qd = rq.elements[i + 3];
5545 if (type == SOLVER_RULE_RPM || type > qt)
5559 if (rid >= solv->jobrules && rid < solv->jobrules_end)
5561 Id jidx = solv->ruletojob.elements[rid - solv->jobrules];
5565 *top = solv->job.elements[jidx];
5567 *depp = solv->job.elements[jidx + 1];
5568 if ((r->d == 0 || r->d == -1) && r->w2 == 0 && r->p == -SYSTEMSOLVABLE && (solv->job.elements[jidx] & SOLVER_SELECTMASK) != SOLVER_SOLVABLE_ONE_OF)
5569 return SOLVER_RULE_JOB_NOTHING_PROVIDES_DEP;
5570 return SOLVER_RULE_JOB;
5572 if (rid >= solv->updaterules && rid < solv->updaterules_end)
5575 *fromp = solv->installed->start + (rid - solv->updaterules);
5576 return SOLVER_RULE_UPDATE;
5578 if (rid >= solv->featurerules && rid < solv->featurerules_end)
5581 *fromp = solv->installed->start + (rid - solv->featurerules);
5582 return SOLVER_RULE_FEATURE;
5584 if (rid >= solv->duprules && rid < solv->duprules_end)
5589 *depp = pool->solvables[-r->p].name;
5590 return SOLVER_RULE_DISTUPGRADE;
5592 if (rid >= solv->infarchrules && rid < solv->infarchrules_end)
5597 *depp = pool->solvables[-r->p].name;
5598 return SOLVER_RULE_INFARCH;
5600 if (rid >= solv->learntrules)
5602 return SOLVER_RULE_LEARNT;
5604 return SOLVER_RULE_UNKNOWN;
5607 /* obsolete function */
5609 solver_problemruleinfo(Solver *solv, Queue *job, Id rid, Id *depp, Id *sourcep, Id *targetp)
5611 return solver_ruleinfo(solv, rid, sourcep, targetp, depp);