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);
32 /********************************************************************
34 * dependency check helpers
38 /*-------------------------------------------------------------------
39 * handle split provides
43 solver_splitprovides(Solver *solv, Id dep)
45 Pool *pool = solv->pool;
50 if (!solv->dosplitprovides || !solv->installed)
54 rd = GETRELDEP(pool, dep);
55 if (rd->flags != REL_WITH)
57 FOR_PROVIDES(p, pp, dep)
59 s = pool->solvables + p;
60 if (s->repo == solv->installed && s->name == rd->name)
67 /*-------------------------------------------------------------------
68 * solver_dep_installed
72 solver_dep_installed(Solver *solv, Id dep)
75 Pool *pool = solv->pool;
80 Reldep *rd = GETRELDEP(pool, dep);
81 if (rd->flags == REL_AND)
83 if (!solver_dep_installed(solv, rd->name))
85 return solver_dep_installed(solv, rd->evr);
87 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
88 return solver_dep_installed(solv, rd->evr);
90 FOR_PROVIDES(p, pp, dep)
92 if (p == SYSTEMSOLVABLE || (solv->installed && pool->solvables[p].repo == solv->installed))
100 /*-------------------------------------------------------------------
101 * Check if dependenc is possible
103 * this mirrors solver_dep_fulfilled
104 * but uses map m instead of the decisionmap
108 dep_possible(Solver *solv, Id dep, Map *m)
110 Pool *pool = solv->pool;
115 Reldep *rd = GETRELDEP(pool, dep);
116 if (rd->flags == REL_AND)
118 if (!dep_possible(solv, rd->name, m))
120 return dep_possible(solv, rd->evr, m);
122 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
123 return solver_splitprovides(solv, rd->evr);
124 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
125 return solver_dep_installed(solv, rd->evr);
127 FOR_PROVIDES(p, pp, dep)
135 /********************************************************************
139 * - unify rules, remove duplicates
142 static Pool *unifyrules_sortcmp_data;
144 /*-------------------------------------------------------------------
146 * compare rules for unification sort
151 unifyrules_sortcmp(const void *ap, const void *bp)
153 Pool *pool = unifyrules_sortcmp_data;
154 Rule *a = (Rule *)ap;
155 Rule *b = (Rule *)bp;
161 return x; /* p differs */
164 if (a->d == 0 && b->d == 0)
165 return a->w2 - b->w2; /* assertion: return w2 diff */
167 if (a->d == 0) /* a is assertion, b not */
169 x = a->w2 - pool->whatprovidesdata[b->d];
173 if (b->d == 0) /* b is assertion, a not */
175 x = pool->whatprovidesdata[a->d] - b->w2;
179 /* compare whatprovidesdata */
180 ad = pool->whatprovidesdata + a->d;
181 bd = pool->whatprovidesdata + b->d;
183 if ((x = *ad++ - *bd++) != 0)
189 /*-------------------------------------------------------------------
192 * go over all rules and remove duplicates
196 unifyrules(Solver *solv)
198 Pool *pool = solv->pool;
202 if (solv->nrules <= 1) /* nothing to unify */
205 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- unifyrules -----\n");
207 /* sort rules first */
208 unifyrules_sortcmp_data = solv->pool;
209 qsort(solv->rules + 1, solv->nrules - 1, sizeof(Rule), unifyrules_sortcmp);
216 for (i = j = 1, ir = solv->rules + i; i < solv->nrules; i++, ir++)
218 if (jr && !unifyrules_sortcmp(ir, jr))
219 continue; /* prune! */
220 jr = solv->rules + j++; /* keep! */
225 /* reduced count from nrules to j rules */
226 POOL_DEBUG(SAT_DEBUG_STATS, "pruned rules from %d to %d\n", solv->nrules, j);
228 /* adapt rule buffer */
230 solv->rules = sat_extend_resize(solv->rules, solv->nrules, sizeof(Rule), RULES_BLOCK);
234 IF_POOLDEBUG (SAT_DEBUG_STATS)
241 for (i = 1; i < solv->nrules; i++)
248 dp = solv->pool->whatprovidesdata + r->d;
253 POOL_DEBUG(SAT_DEBUG_STATS, " binary: %d\n", binr);
254 POOL_DEBUG(SAT_DEBUG_STATS, " normal: %d, %d literals\n", solv->nrules - 1 - binr, lits);
256 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- unifyrules end -----\n");
266 hashrule(Solver *solv, Id p, Id d, int n)
268 unsigned int x = (unsigned int)p;
272 return (x * 37) ^ (unsigned int)d;
273 dp = solv->pool->whatprovidesdata + d;
275 x = (x * 37) ^ (unsigned int)*dp++;
281 /*-------------------------------------------------------------------
287 * p = direct literal; always < 0 for installed rpm rules
288 * d, if < 0 direct literal, if > 0 offset into whatprovides, if == 0 rule is assertion (look at p only)
291 * A requires b, b provided by B1,B2,B3 => (-A|B1|B2|B3)
293 * p < 0 : pkg id of A
294 * d > 0 : Offset in whatprovidesdata (list of providers of b)
296 * A conflicts b, b provided by B1,B2,B3 => (-A|-B1), (-A|-B2), (-A|-B3)
297 * p < 0 : pkg id of A
298 * d < 0 : Id of solvable (e.g. B1)
300 * d == 0: unary rule, assertion => (A) or (-A)
302 * Install: p > 0, d = 0 (A) user requested install
303 * Remove: p < 0, d = 0 (-A) user requested remove (also: uninstallable)
304 * Requires: p < 0, d > 0 (-A|B1|B2|...) d: <list of providers for requirement of p>
305 * Updates: p > 0, d > 0 (A|B1|B2|...) d: <list of updates for solvable p>
306 * Conflicts: p < 0, d < 0 (-A|-B) either p (conflict issuer) or d (conflict provider) (binary rule)
307 * also used for obsoletes
308 * ?: p > 0, d < 0 (A|-B)
309 * No-op ?: p = 0, d = 0 (null) (used as policy rule placeholder)
313 * Direct assertion (no watch needed)( if d <0 ) --> d = 0, w1 = p, w2 = 0
314 * Binary rule: p = first literal, d = 0, w2 = second literal, w1 = p
315 * every other : w1 = p, w2 = whatprovidesdata[d];
316 * Disabled rule: w1 = 0
318 * always returns a rule for non-rpm rules
322 addrule(Solver *solv, Id p, Id d)
324 Pool *pool = solv->pool;
328 int n = 0; /* number of literals in rule - 1
329 0 = direct assertion (single literal)
334 /* it often happenes that requires lead to adding the same rpm rule
335 * multiple times, so we prune those duplicates right away to make
336 * the work for unifyrules a bit easier */
338 if (solv->nrules /* we already have rules */
339 && !solv->rpmrules_end) /* but are not done with rpm rules */
341 r = solv->rules + solv->nrules - 1; /* get the last added rule */
342 if (r->p == p && r->d == d && d != 0) /* identical and not user requested */
347 * compute number of literals (n) in rule
352 /* always a binary rule */
354 return 0; /* ignore self conflict */
359 for (dp = pool->whatprovidesdata + d; *dp; dp++, n++)
361 return 0; /* rule is self-fulfilling */
363 if (n == 1) /* have single provider */
364 d = dp[-1]; /* take single literal */
367 if (n == 1 && p > d && !solv->rpmrules_end)
369 /* smallest literal first so we can find dups */
370 n = p; p = d; d = n; /* p <-> d */
371 n = 1; /* re-set n, was used as temp var */
375 * check for duplicate
378 /* check if the last added rule (r) is exactly the same as what we're looking for. */
379 if (r && n == 1 && !r->d && r->p == p && r->w2 == d)
380 return r; /* binary rule */
382 /* have n-ary rule with same first literal, check other literals */
383 if (r && n > 1 && r->d && r->p == p)
385 /* Rule where d is an offset in whatprovidesdata */
389 dp2 = pool->whatprovidesdata + r->d;
390 for (dp = pool->whatprovidesdata + d; *dp; dp++, dp2++)
401 /* extend rule buffer */
402 solv->rules = sat_extend(solv->rules, solv->nrules, 1, sizeof(Rule), RULES_BLOCK);
403 r = solv->rules + solv->nrules++; /* point to rule space */
412 /* direct assertion, no watch needed */
428 r->w2 = pool->whatprovidesdata[d];
433 IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION)
435 POOL_DEBUG(SAT_DEBUG_RULE_CREATION, " Add rule: ");
436 solver_printrule(solv, SAT_DEBUG_RULE_CREATION, r);
442 /*-------------------------------------------------------------------
447 disablerule(Solver *solv, Rule *r)
453 /*-------------------------------------------------------------------
458 enablerule(Solver *solv, Rule *r)
465 /**********************************************************************************/
467 /* a problem is an item on the solver's problem list. It can either be >0, in that
468 * case it is a update rule, or it can be <0, which makes it refer to a job
469 * consisting of multiple job rules.
473 disableproblem(Solver *solv, Id v)
481 if (v >= solv->infarchrules && v < solv->infarchrules_end)
483 Pool *pool = solv->pool;
484 Id name = pool->solvables[-solv->rules[v].p].name;
485 while (v > solv->infarchrules && pool->solvables[-solv->rules[v - 1].p].name == name)
487 for (; v < solv->infarchrules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
488 disablerule(solv, solv->rules + v);
491 if (v >= solv->duprules && v < solv->duprules_end)
493 Pool *pool = solv->pool;
494 Id name = pool->solvables[-solv->rules[v].p].name;
495 while (v > solv->duprules && pool->solvables[-solv->rules[v - 1].p].name == name)
497 for (; v < solv->duprules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
498 disablerule(solv, solv->rules + v);
501 disablerule(solv, solv->rules + v);
505 jp = solv->ruletojob.elements;
506 for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++, jp++)
508 disablerule(solv, r);
511 /*-------------------------------------------------------------------
516 enableproblem(Solver *solv, Id v)
524 if (v >= solv->infarchrules && v < solv->infarchrules_end)
526 Pool *pool = solv->pool;
527 Id name = pool->solvables[-solv->rules[v].p].name;
528 while (v > solv->infarchrules && pool->solvables[-solv->rules[v - 1].p].name == name)
530 for (; v < solv->infarchrules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
531 enablerule(solv, solv->rules + v);
534 if (v >= solv->duprules && v < solv->duprules_end)
536 Pool *pool = solv->pool;
537 Id name = pool->solvables[-solv->rules[v].p].name;
538 while (v > solv->duprules && pool->solvables[-solv->rules[v - 1].p].name == name)
540 for (; v < solv->duprules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
541 enablerule(solv, solv->rules + v);
544 if (v >= solv->featurerules && v < solv->featurerules_end)
546 /* do not enable feature rule if update rule is enabled */
547 r = solv->rules + (v - solv->featurerules + solv->updaterules);
551 enablerule(solv, solv->rules + v);
552 if (v >= solv->updaterules && v < solv->updaterules_end)
554 /* disable feature rule when enabling update rule */
555 r = solv->rules + (v - solv->updaterules + solv->featurerules);
557 disablerule(solv, r);
562 jp = solv->ruletojob.elements;
563 for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++, jp++)
569 /************************************************************************/
572 * make assertion rules into decisions
574 * go through update and job rules and add direct assertions
575 * to the decisionqueue. If we find a conflict, disable rules and
576 * add them to problem queue.
580 makeruledecisions(Solver *solv)
582 Pool *pool = solv->pool;
588 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- makeruledecisions ; size decisionq: %d -----\n",solv->decisionq.count);
590 decisionstart = solv->decisionq.count;
591 for (ii = 0; ii < solv->ruleassertions.count; ii++)
593 ri = solv->ruleassertions.elements[ii];
594 r = solv->rules + ri;
596 if (r->d < 0 || !r->p || r->w2) /* disabled, dummy or no assertion */
598 /* do weak rules in phase 2 */
599 if (ri < solv->learntrules && MAPTST(&solv->weakrulemap, ri))
605 if (!solv->decisionmap[vv]) /* if not yet decided */
610 queue_push(&solv->decisionq, v);
611 queue_push(&solv->decisionq_why, r - solv->rules);
612 solv->decisionmap[vv] = v > 0 ? 1 : -1;
613 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
615 Solvable *s = solv->pool->solvables + vv;
617 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "conflicting %s (assertion)\n", solvable2str(solv->pool, s));
619 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "installing %s (assertion)\n", solvable2str(solv->pool, s));
624 * check previous decision: is it sane ?
627 if (v > 0 && solv->decisionmap[vv] > 0) /* ok to install */
629 if (v < 0 && solv->decisionmap[vv] < 0) /* ok to remove */
635 * The rule (r) we're currently processing says something
636 * different (v = r->p) than a previous decision (decisionmap[abs(v)])
640 if (ri >= solv->learntrules)
642 /* conflict with a learnt rule */
643 /* can happen when packages cannot be installed for
644 * multiple reasons. */
645 /* we disable the learnt rule in this case */
646 disablerule(solv, r);
651 * find the decision which is the "opposite" of the rule
654 for (i = 0; i < solv->decisionq.count; i++)
655 if (solv->decisionq.elements[i] == -v)
657 assert(i < solv->decisionq.count); /* assert that we found it */
660 * conflict with system solvable ?
663 if (v == -SYSTEMSOLVABLE) {
664 /* conflict with system solvable */
665 queue_push(&solv->problems, solv->learnt_pool.count);
666 queue_push(&solv->learnt_pool, ri);
667 queue_push(&solv->learnt_pool, 0);
668 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "conflict with system solvable, disabling rule #%d\n", ri);
669 if (ri >= solv->jobrules && ri < solv->jobrules_end)
670 v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
673 queue_push(&solv->problems, v);
674 queue_push(&solv->problems, 0);
675 disableproblem(solv, v);
679 assert(solv->decisionq_why.elements[i] > 0);
682 * conflict with an rpm rule ?
685 if (solv->decisionq_why.elements[i] < solv->rpmrules_end)
687 /* conflict with rpm rule assertion */
688 queue_push(&solv->problems, solv->learnt_pool.count);
689 queue_push(&solv->learnt_pool, ri);
690 queue_push(&solv->learnt_pool, solv->decisionq_why.elements[i]);
691 queue_push(&solv->learnt_pool, 0);
692 assert(v > 0 || v == -SYSTEMSOLVABLE);
693 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "conflict with rpm rule, disabling rule #%d\n", ri);
694 if (ri >= solv->jobrules && ri < solv->jobrules_end)
695 v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
698 queue_push(&solv->problems, v);
699 queue_push(&solv->problems, 0);
700 disableproblem(solv, v);
705 * conflict with another job or update/feature rule
709 queue_push(&solv->problems, solv->learnt_pool.count);
710 queue_push(&solv->learnt_pool, ri);
711 queue_push(&solv->learnt_pool, solv->decisionq_why.elements[i]);
712 queue_push(&solv->learnt_pool, 0);
714 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "conflicting update/job assertions over literal %d\n", vv);
717 * push all of our rules (can only be feature or job rules)
718 * asserting this literal on the problem stack
721 for (i = solv->featurerules, rr = solv->rules + i; i < solv->learntrules; i++, rr++)
723 if (rr->d < 0 /* disabled */
724 || rr->w2) /* or no assertion */
726 if (rr->p != vv /* not affecting the literal */
729 if (MAPTST(&solv->weakrulemap, i)) /* weak: silently ignore */
732 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, " - disabling rule #%d\n", i);
734 solver_printruleclass(solv, SAT_DEBUG_UNSOLVABLE, solv->rules + i);
737 /* is is a job rule ? */
738 if (i >= solv->jobrules && i < solv->jobrules_end)
739 v = -(solv->ruletojob.elements[i - solv->jobrules] + 1);
741 queue_push(&solv->problems, v);
742 disableproblem(solv, v);
744 queue_push(&solv->problems, 0);
748 * (back up from decisions)
750 while (solv->decisionq.count > decisionstart)
752 v = solv->decisionq.elements[--solv->decisionq.count];
753 --solv->decisionq_why.count;
755 solv->decisionmap[vv] = 0;
757 ii = -1; /* restarts loop at 0 */
761 * phase 2: now do the weak assertions
763 for (ii = 0; ii < solv->ruleassertions.count; ii++)
765 ri = solv->ruleassertions.elements[ii];
766 r = solv->rules + ri;
767 if (r->d < 0 || r->w2) /* disabled or no assertion */
769 if (ri >= solv->learntrules || !MAPTST(&solv->weakrulemap, ri)) /* skip non-weak */
775 * (if not yet decided)
777 if (!solv->decisionmap[vv])
779 queue_push(&solv->decisionq, v);
780 queue_push(&solv->decisionq_why, r - solv->rules);
781 solv->decisionmap[vv] = v > 0 ? 1 : -1;
782 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
784 Solvable *s = solv->pool->solvables + vv;
786 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "conflicting %s (weak assertion)\n", solvable2str(solv->pool, s));
788 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "installing %s (weak assertion)\n", solvable2str(solv->pool, s));
793 * previously decided, sane ?
795 if (v > 0 && solv->decisionmap[vv] > 0)
797 if (v < 0 && solv->decisionmap[vv] < 0)
800 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "assertion conflict, but I am weak, disabling ");
801 solver_printrule(solv, SAT_DEBUG_UNSOLVABLE, r);
803 if (ri >= solv->jobrules && ri < solv->jobrules_end)
804 v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
807 disableproblem(solv, v);
809 reenablepolicyrules(solv, solv->job, -(v + 1));
812 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- makeruledecisions end; size decisionq: %d -----\n",solv->decisionq.count);
816 /*-------------------------------------------------------------------
817 * enable/disable learnt rules
819 * we have enabled or disabled some of our rules. We now reenable all
820 * of our learnt rules except the ones that were learnt from rules that
824 enabledisablelearntrules(Solver *solv)
826 Pool *pool = solv->pool;
831 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "enabledisablelearntrules called\n");
832 for (i = solv->learntrules, r = solv->rules + i; i < solv->nrules; i++, r++)
834 whyp = solv->learnt_pool.elements + solv->learnt_why.elements[i - solv->learntrules];
835 while ((why = *whyp++) != 0)
837 assert(why > 0 && why < i);
838 if (solv->rules[why].d < 0)
841 /* why != 0: we found a disabled rule, disable the learnt rule */
842 if (why && r->d >= 0)
844 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
846 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "disabling ");
847 solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
849 disablerule(solv, r);
851 else if (!why && r->d < 0)
853 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
855 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "re-enabling ");
856 solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
864 /*-------------------------------------------------------------------
867 * Enable all rules, except learnt rules, which are
868 * - disabled and weak (set in weakrulemap)
873 enableweakrules(Solver *solv)
878 for (i = 1, r = solv->rules + i; i < solv->learntrules; i++, r++)
880 if (r->d >= 0) /* already enabled? */
882 if (!MAPTST(&solv->weakrulemap, i))
889 /*-------------------------------------------------------------------
890 * policy rule enabling/disabling
892 * we need to disable policy rules that conflict with our job list, and
893 * also reenable such rules with the job was changed due to solution generation
898 disableinfarchrule(Solver *solv, Id name)
900 Pool *pool = solv->pool;
903 for (i = solv->infarchrules, r = solv->rules + i; i < solv->infarchrules_end; i++, r++)
905 if (r->p < 0 && r->d >= 0 && pool->solvables[-r->p].name == name)
906 disablerule(solv, r);
911 reenableinfarchrule(Solver *solv, Id name)
913 Pool *pool = solv->pool;
916 for (i = solv->infarchrules, r = solv->rules + i; i < solv->infarchrules_end; i++, r++)
918 if (r->p < 0 && r->d < 0 && pool->solvables[-r->p].name == name)
921 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
923 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
924 solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
931 disableduprule(Solver *solv, Id name)
933 Pool *pool = solv->pool;
936 for (i = solv->duprules, r = solv->rules + i; i < solv->duprules_end; i++, r++)
938 if (r->p < 0 && r->d >= 0 && pool->solvables[-r->p].name == name)
939 disablerule(solv, r);
944 reenableduprule(Solver *solv, Id name)
946 Pool *pool = solv->pool;
949 for (i = solv->duprules, r = solv->rules + i; i < solv->duprules_end; i++, r++)
951 if (r->p < 0 && r->d < 0 && pool->solvables[-r->p].name == name)
954 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
956 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
957 solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
964 disableupdaterule(Solver *solv, Id p)
968 MAPSET(&solv->noupdate, p - solv->installed->start);
969 r = solv->rules + solv->updaterules + (p - solv->installed->start);
970 if (r->p && r->d >= 0)
971 disablerule(solv, r);
972 r = solv->rules + solv->featurerules + (p - solv->installed->start);
973 if (r->p && r->d >= 0)
974 disablerule(solv, r);
978 reenableupdaterule(Solver *solv, Id p)
980 Pool *pool = solv->pool;
983 MAPCLR(&solv->noupdate, p - solv->installed->start);
984 r = solv->rules + solv->updaterules + (p - solv->installed->start);
990 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
992 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
993 solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
997 r = solv->rules + solv->featurerules + (p - solv->installed->start);
998 if (r->p && r->d < 0)
1000 enablerule(solv, r);
1001 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
1003 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
1004 solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
1009 #define DISABLE_UPDATE 1
1010 #define DISABLE_INFARCH 2
1011 #define DISABLE_DUP 3
1014 jobtodisablelist(Solver *solv, Id how, Id what, Queue *q)
1016 Pool *pool = solv->pool;
1022 installed = solv->installed;
1023 select = how & SOLVER_SELECTMASK;
1024 switch (how & SOLVER_JOBMASK)
1026 case SOLVER_INSTALL:
1027 if ((select == SOLVER_SOLVABLE_NAME || select == SOLVER_SOLVABLE_PROVIDES) && solv->infarchrules != solv->infarchrules_end && ISRELDEP(what))
1029 Reldep *rd = GETRELDEP(pool, what);
1030 if (rd->flags == REL_ARCH)
1032 int qcnt = q->count;
1033 FOR_JOB_SELECT(p, pp, select, what)
1035 s = pool->solvables + p;
1037 for (i = qcnt; i < q->count; i += 2)
1038 if (q->elements[i + 1] == s->name)
1042 queue_push(q, DISABLE_INFARCH);
1043 queue_push(q, s->name);
1047 if (select != SOLVER_SOLVABLE)
1049 s = pool->solvables + what;
1050 if (solv->infarchrules != solv->infarchrules_end)
1052 queue_push(q, DISABLE_INFARCH);
1053 queue_push(q, s->name);
1055 if (solv->duprules != solv->duprules_end)
1057 queue_push(q, DISABLE_DUP);
1058 queue_push(q, s->name);
1062 if (solv->noobsoletes.size && MAPTST(&solv->noobsoletes, what))
1064 if (s->repo == installed)
1066 queue_push(q, DISABLE_UPDATE);
1067 queue_push(q, what);
1073 obsp = s->repo->idarraydata + s->obsoletes;
1074 while ((obs = *obsp++) != 0)
1075 FOR_PROVIDES(p, pp, obs)
1077 Solvable *ps = pool->solvables + p;
1078 if (ps->repo != installed)
1080 if (!solv->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
1082 queue_push(q, DISABLE_UPDATE);
1086 FOR_PROVIDES(p, pp, s->name)
1088 Solvable *ps = pool->solvables + p;
1089 if (ps->repo != installed)
1091 if (!solv->implicitobsoleteusesprovides && ps->name != s->name)
1093 queue_push(q, DISABLE_UPDATE);
1100 FOR_JOB_SELECT(p, pp, select, what)
1101 if (pool->solvables[p].repo == installed)
1103 queue_push(q, DISABLE_UPDATE);
1112 /* disable all policy rules that are in conflict with our job list */
1114 disablepolicyrules(Solver *solv, Queue *job)
1122 queue_init_buffer(&allq, allqbuf, sizeof(allqbuf)/sizeof(*allqbuf));
1124 for (i = solv->jobrules; i < solv->jobrules_end; i++)
1126 r = solv->rules + i;
1127 if (r->d < 0) /* disabled? */
1129 j = solv->ruletojob.elements[i - solv->jobrules];
1133 jobtodisablelist(solv, job->elements[j], job->elements[j + 1], &allq);
1135 MAPZERO(&solv->noupdate);
1136 for (i = 0; i < allq.count; i += 2)
1138 Id type = allq.elements[i], arg = allq.elements[i + 1];
1141 case DISABLE_UPDATE:
1142 disableupdaterule(solv, arg);
1144 case DISABLE_INFARCH:
1145 disableinfarchrule(solv, arg);
1148 disableduprule(solv, arg);
1157 /* we just disabled job #jobidx, now reenable all policy rules that were
1158 * disabled because of this job */
1160 reenablepolicyrules(Solver *solv, Queue *job, int jobidx)
1166 Id qbuf[32], allqbuf[128];
1168 queue_init_buffer(&q, qbuf, sizeof(qbuf)/sizeof(*qbuf));
1169 queue_init_buffer(&allq, allqbuf, sizeof(allqbuf)/sizeof(*allqbuf));
1170 jobtodisablelist(solv, job->elements[jobidx], job->elements[jobidx + 1], &q);
1173 for (i = solv->jobrules; i < solv->jobrules_end; i++)
1175 r = solv->rules + i;
1176 if (r->d < 0) /* disabled? */
1178 j = solv->ruletojob.elements[i - solv->jobrules];
1182 jobtodisablelist(solv, job->elements[j], job->elements[j + 1], &allq);
1184 for (j = 0; j < q.count; j += 2)
1186 Id type = q.elements[j], arg = q.elements[j + 1];
1187 for (i = 0; i < allq.count; i += 2)
1188 if (allq.elements[i] == type && allq.elements[i + 1] == arg)
1191 continue; /* still disabled */
1194 case DISABLE_UPDATE:
1195 reenableupdaterule(solv, arg);
1197 case DISABLE_INFARCH:
1198 reenableinfarchrule(solv, arg);
1201 reenableduprule(solv, arg);
1209 /*-------------------------------------------------------------------
1215 * special multiversion patch conflict handling:
1216 * a patch conflict is also satisfied, if some other
1217 * version with the same name/arch that doesn't conflict
1218 * get's installed. The generated rule is thus:
1219 * -patch|-cpack|opack1|opack2|...
1222 makemultiversionconflict(Solver *solv, Id n, Id con)
1224 Pool *pool = solv->pool;
1229 sn = pool->solvables + n;
1230 queue_init_buffer(&q, qbuf, sizeof(qbuf)/sizeof(*qbuf));
1232 FOR_PROVIDES(p, pp, sn->name)
1234 s = pool->solvables + p;
1235 if (s->name != sn->name || s->arch != sn->arch)
1237 if (!MAPTST(&solv->noobsoletes, p))
1239 if (pool_match_nevr(pool, pool->solvables + p, con))
1241 /* here we have a multiversion solvable that doesn't conflict */
1242 /* thus we're not in conflict if it is installed */
1246 return -n; /* no other package found, generate normal conflict */
1247 return pool_queuetowhatprovides(pool, &q);
1251 /*-------------------------------------------------------------------
1253 * add (install) rules for solvable
1255 * s: Solvable for which to add rules
1256 * m: m[s] = 1 for solvables which have rules, prevent rule duplication
1258 * Algorithm: 'visit all nodes of a graph'. The graph nodes are
1259 * solvables, the edges their dependencies.
1260 * Starting from an installed solvable, this will create all rules
1261 * representing the graph created by the solvables dependencies.
1263 * for unfulfilled requirements, conflicts, obsoletes,....
1264 * add a negative assertion for solvables that are not installable
1266 * It will also create rules for all solvables referenced by 's'
1267 * i.e. descend to all providers of requirements of 's'
1272 addrpmrulesforsolvable(Solver *solv, Solvable *s, Map *m)
1274 Pool *pool = solv->pool;
1275 Repo *installed = solv->installed;
1277 /* 'work' queue. keeps Ids of solvables we still have to work on.
1278 And buffer for it. */
1283 /* if to add rules for broken deps ('rpm -V' functionality)
1287 /* Id var and pointer for each dependency
1288 * (not used in parallel)
1295 /* var and ptr for loops */
1297 /* ptr to 'whatprovides' */
1299 /* Id for current solvable 's' */
1302 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforsolvable -----\n");
1304 queue_init_buffer(&workq, workqbuf, sizeof(workqbuf)/sizeof(*workqbuf));
1305 queue_push(&workq, s - pool->solvables); /* push solvable Id to work queue */
1307 /* loop until there's no more work left */
1312 * s: Pointer to solvable
1315 n = queue_shift(&workq); /* 'pop' next solvable to work on from queue */
1316 if (MAPTST(m, n)) /* continue if already visited */
1319 MAPSET(m, n); /* mark as visited */
1320 s = pool->solvables + n; /* s = Solvable in question */
1323 if (installed /* Installed system available */
1324 && !solv->fixsystem /* NOT repair errors in rpm dependency graph */
1325 && s->repo == installed) /* solvable is installed? */
1327 dontfix = 1; /* dont care about broken rpm deps */
1331 && s->arch != ARCH_SRC
1332 && s->arch != ARCH_NOSRC
1333 && !pool_installable(pool, s))
1335 POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "package %s [%d] is not installable\n", solvable2str(pool, s), (Id)(s - pool->solvables));
1336 addrule(solv, -n, 0); /* uninstallable */
1339 /* yet another SUSE hack, sigh */
1340 if (pool->nscallback && !strncmp("product:", id2str(pool, s->name), 8))
1342 Id buddy = pool->nscallback(pool, pool->nscallbackdata, NAMESPACE_PRODUCTBUDDY, n);
1343 if (buddy > 0 && buddy != SYSTEMSOLVABLE && buddy != n && buddy < pool->nsolvables)
1345 addrule(solv, n, -buddy);
1346 addrule(solv, buddy, -n);
1347 if (!MAPTST(m, buddy))
1348 queue_push(&workq, buddy);
1352 /*-----------------------------------------
1353 * check requires of s
1358 reqp = s->repo->idarraydata + s->requires;
1359 while ((req = *reqp++) != 0) /* go through all requires */
1361 if (req == SOLVABLE_PREREQMARKER) /* skip the marker */
1364 /* find list of solvables providing 'req' */
1365 dp = pool_whatprovides_ptr(pool, req);
1367 if (*dp == SYSTEMSOLVABLE) /* always installed */
1372 /* the strategy here is to not insist on dependencies
1373 * that are already broken. so if we find one provider
1374 * that was already installed, we know that the
1375 * dependency was not broken before so we enforce it */
1377 /* check if any of the providers for 'req' is installed */
1378 for (i = 0; (p = dp[i]) != 0; i++)
1380 if (pool->solvables[p].repo == installed)
1381 break; /* provider was installed */
1383 /* didn't find an installed provider: previously broken dependency */
1386 POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "ignoring broken requires %s of installed package %s\n", dep2str(pool, req), solvable2str(pool, s));
1393 /* nothing provides req! */
1394 POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "package %s [%d] is not installable (%s)\n", solvable2str(pool, s), (Id)(s - pool->solvables), dep2str(pool, req));
1395 addrule(solv, -n, 0); /* mark requestor as uninstallable */
1399 IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION)
1401 POOL_DEBUG(SAT_DEBUG_RULE_CREATION," %s requires %s\n", solvable2str(pool, s), dep2str(pool, req));
1402 for (i = 0; dp[i]; i++)
1403 POOL_DEBUG(SAT_DEBUG_RULE_CREATION, " provided by %s\n", solvable2str(pool, pool->solvables + dp[i]));
1406 /* add 'requires' dependency */
1407 /* rule: (-requestor|provider1|provider2|...|providerN) */
1408 addrule(solv, -n, dp - pool->whatprovidesdata);
1410 /* descend the dependency tree
1411 push all non-visited providers on the work queue */
1414 if (!MAPTST(m, *dp))
1415 queue_push(&workq, *dp);
1418 } /* while, requirements of n */
1420 } /* if, requirements */
1422 /* that's all we check for src packages */
1423 if (s->arch == ARCH_SRC || s->arch == ARCH_NOSRC)
1426 /*-----------------------------------------
1427 * check conflicts of s
1434 /* we treat conflicts in patches a bit differen:
1436 * - multiversion handling
1437 * XXX: we should really handle this different, looking
1438 * at the name is a bad hack
1440 if (!strncmp("patch:", id2str(pool, s->name), 6))
1442 conp = s->repo->idarraydata + s->conflicts;
1443 /* foreach conflicts of 's' */
1444 while ((con = *conp++) != 0)
1446 /* foreach providers of a conflict of 's' */
1447 FOR_PROVIDES(p, pp, con)
1449 if (ispatch && !pool_match_nevr(pool, pool->solvables + p, con))
1451 /* dontfix: dont care about conflicts with already installed packs */
1452 if (dontfix && pool->solvables[p].repo == installed)
1454 /* p == n: self conflict */
1455 if (p == n && !solv->allowselfconflicts)
1459 Reldep *rd = GETRELDEP(pool, con);
1460 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_OTHERPROVIDERS)
1463 p = 0; /* make it a negative assertion, aka 'uninstallable' */
1465 if (p && ispatch && solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p) && ISRELDEP(con))
1467 /* our patch conflicts with a noobsoletes (aka multiversion) package */
1468 p = -makemultiversionconflict(solv, p, con);
1470 /* rule: -n|-p: either solvable _or_ provider of conflict */
1471 addrule(solv, -n, -p);
1476 /*-----------------------------------------
1477 * check obsoletes if not installed
1478 * (only installation will trigger the obsoletes in rpm)
1480 if (!installed || pool->solvables[n].repo != installed)
1481 { /* not installed */
1482 int noobs = solv->noobsoletes.size && MAPTST(&solv->noobsoletes, n);
1483 if (s->obsoletes && !noobs)
1485 obsp = s->repo->idarraydata + s->obsoletes;
1486 /* foreach obsoletes */
1487 while ((obs = *obsp++) != 0)
1489 /* foreach provider of an obsoletes of 's' */
1490 FOR_PROVIDES(p, pp, obs)
1492 if (!solv->obsoleteusesprovides /* obsoletes are matched names, not provides */
1493 && !pool_match_nevr(pool, pool->solvables + p, obs))
1495 addrule(solv, -n, -p);
1499 FOR_PROVIDES(p, pp, s->name)
1501 Solvable *ps = pool->solvables + p;
1502 /* we still obsolete packages with same nevra, like rpm does */
1503 /* (actually, rpm mixes those packages. yuck...) */
1504 if (noobs && (s->name != ps->name || s->evr != ps->evr || s->arch != ps->arch))
1506 if (!solv->implicitobsoleteusesprovides && s->name != ps->name)
1508 addrule(solv, -n, -p);
1512 /*-----------------------------------------
1513 * add recommends to the work queue
1517 recp = s->repo->idarraydata + s->recommends;
1518 while ((rec = *recp++) != 0)
1520 FOR_PROVIDES(p, pp, rec)
1522 queue_push(&workq, p);
1527 sugp = s->repo->idarraydata + s->suggests;
1528 while ((sug = *sugp++) != 0)
1530 FOR_PROVIDES(p, pp, sug)
1532 queue_push(&workq, p);
1537 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforsolvable end -----\n");
1541 /*-------------------------------------------------------------------
1543 * Add package rules for weak rules
1545 * m: visited solvables
1549 addrpmrulesforweak(Solver *solv, Map *m)
1551 Pool *pool = solv->pool;
1556 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforweak -----\n");
1557 /* foreach solvable in pool */
1558 for (i = n = 1; n < pool->nsolvables; i++, n++)
1560 if (i == pool->nsolvables) /* wrap i */
1562 if (MAPTST(m, i)) /* been there */
1565 s = pool->solvables + i;
1566 if (!pool_installable(pool, s)) /* only look at installable ones */
1572 /* find possible supplements */
1573 supp = s->repo->idarraydata + s->supplements;
1574 while ((sup = *supp++) != ID_NULL)
1575 if (dep_possible(solv, sup, m))
1579 /* if nothing found, check for enhances */
1580 if (!sup && s->enhances)
1582 supp = s->repo->idarraydata + s->enhances;
1583 while ((sup = *supp++) != ID_NULL)
1584 if (dep_possible(solv, sup, m))
1587 /* if nothing found, goto next solvables */
1590 addrpmrulesforsolvable(solv, s, m);
1593 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforweak end -----\n");
1597 /*-------------------------------------------------------------------
1599 * add package rules for possible updates
1602 * m: map of already visited solvables
1603 * allow_all: 0 = dont allow downgrades, 1 = allow all candidates
1607 addrpmrulesforupdaters(Solver *solv, Solvable *s, Map *m, int allow_all)
1609 Pool *pool = solv->pool;
1611 /* queue and buffer for it */
1615 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforupdaters -----\n");
1617 queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
1618 /* find update candidates for 's' */
1619 policy_findupdatepackages(solv, s, &qs, allow_all);
1620 /* add rule for 's' if not already done */
1621 if (!MAPTST(m, s - pool->solvables))
1622 addrpmrulesforsolvable(solv, s, m);
1623 /* foreach update candidate, add rule if not already done */
1624 for (i = 0; i < qs.count; i++)
1625 if (!MAPTST(m, qs.elements[i]))
1626 addrpmrulesforsolvable(solv, pool->solvables + qs.elements[i], m);
1629 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforupdaters -----\n");
1633 finddistupgradepackages(Solver *solv, Solvable *s, Queue *qs, int allow_all)
1635 Pool *pool = solv->pool;
1638 policy_findupdatepackages(solv, s, qs, allow_all);
1642 return 0; /* orphaned, don't create feature rule */
1643 /* check if this is an orphaned package */
1644 policy_findupdatepackages(solv, s, qs, 1);
1646 return 0; /* orphaned, don't create update rule */
1648 return -SYSTEMSOLVABLE; /* supported but not installable */
1651 return s - pool->solvables;
1652 /* check if it is ok to keep the installed package */
1653 for (i = 0; i < qs->count; i++)
1655 Solvable *ns = pool->solvables + qs->elements[i];
1656 if (s->evr == ns->evr && solvable_identical(s, ns))
1657 return s - pool->solvables;
1659 /* nope, it must be some other package */
1660 return -SYSTEMSOLVABLE;
1663 /* add packages from the dup repositories to the update candidates
1664 * this isn't needed for the global dup mode as all packages are
1665 * from dup repos in that case */
1667 addduppackages(Solver *solv, Solvable *s, Queue *qs)
1672 int oldnoupdateprovide = solv->noupdateprovide;
1674 queue_init_buffer(&dupqs, dupqsbuf, sizeof(dupqsbuf)/sizeof(*dupqsbuf));
1675 solv->noupdateprovide = 1;
1676 policy_findupdatepackages(solv, s, &dupqs, 2);
1677 solv->noupdateprovide = oldnoupdateprovide;
1678 for (i = 0; i < dupqs.count; i++)
1680 p = dupqs.elements[i];
1681 if (MAPTST(&solv->dupmap, p))
1682 queue_pushunique(qs, p);
1687 /*-------------------------------------------------------------------
1689 * add rule for update
1690 * (A|A1|A2|A3...) An = update candidates for A
1692 * s = (installed) solvable
1696 addupdaterule(Solver *solv, Solvable *s, int allow_all)
1698 /* installed packages get a special upgrade allowed rule */
1699 Pool *pool = solv->pool;
1704 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addupdaterule -----\n");
1705 queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
1706 p = s - pool->solvables;
1707 /* find update candidates for 's' */
1708 if (solv->distupgrade)
1709 p = finddistupgradepackages(solv, s, &qs, allow_all);
1711 policy_findupdatepackages(solv, s, &qs, allow_all);
1712 if (!allow_all && !solv->distupgrade && solv->dupinvolvedmap.size && MAPTST(&solv->dupinvolvedmap, p))
1713 addduppackages(solv, s, &qs);
1715 if (!allow_all && qs.count && solv->noobsoletes.size)
1719 d = pool_queuetowhatprovides(pool, &qs);
1720 /* filter out all noobsoletes packages as they don't update */
1721 for (i = j = 0; i < qs.count; i++)
1723 if (MAPTST(&solv->noobsoletes, qs.elements[i]))
1725 /* it's ok if they have same nevra */
1726 Solvable *ps = pool->solvables + qs.elements[i];
1727 if (ps->name != s->name || ps->evr != s->evr || ps->arch != s->arch)
1730 qs.elements[j++] = qs.elements[i];
1732 if (j == 0 && p == -SYSTEMSOLVABLE && solv->distupgrade)
1734 queue_push(&solv->orphaned, s - pool->solvables); /* treat as orphaned */
1739 if (d && solv->updatesystem && solv->installed && s->repo == solv->installed)
1741 if (!solv->multiversionupdaters)
1742 solv->multiversionupdaters = sat_calloc(solv->installed->end - solv->installed->start, sizeof(Id));
1743 solv->multiversionupdaters[s - pool->solvables - solv->installed->start] = d;
1748 if (qs.count && p == -SYSTEMSOLVABLE)
1749 p = queue_shift(&qs);
1750 d = qs.count ? pool_queuetowhatprovides(pool, &qs) : 0;
1752 addrule(solv, p, d); /* allow update of s */
1753 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addupdaterule end -----\n");
1757 /********************************************************************/
1761 /*-------------------------------------------------------------------
1764 * initial setup for all watches
1768 makewatches(Solver *solv)
1772 int nsolvables = solv->pool->nsolvables;
1774 sat_free(solv->watches);
1775 /* lower half for removals, upper half for installs */
1776 solv->watches = sat_calloc(2 * nsolvables, sizeof(Id));
1778 /* do it reverse so rpm rules get triggered first (XXX: obsolete?) */
1779 for (i = 1, r = solv->rules + solv->nrules - 1; i < solv->nrules; i++, r--)
1781 for (i = 1, r = solv->rules + 1; i < solv->nrules; i++, r++)
1784 if (!r->w2) /* assertions do not need watches */
1787 /* see addwatches_rule(solv, r) */
1788 r->n1 = solv->watches[nsolvables + r->w1];
1789 solv->watches[nsolvables + r->w1] = r - solv->rules;
1791 r->n2 = solv->watches[nsolvables + r->w2];
1792 solv->watches[nsolvables + r->w2] = r - solv->rules;
1797 /*-------------------------------------------------------------------
1799 * add watches (for rule)
1800 * sets up watches for a single rule
1802 * see also makewatches()
1806 addwatches_rule(Solver *solv, Rule *r)
1808 int nsolvables = solv->pool->nsolvables;
1810 r->n1 = solv->watches[nsolvables + r->w1];
1811 solv->watches[nsolvables + r->w1] = r - solv->rules;
1813 r->n2 = solv->watches[nsolvables + r->w2];
1814 solv->watches[nsolvables + r->w2] = r - solv->rules;
1818 /********************************************************************/
1824 /* shortcuts to check if a literal (positive or negative) assignment
1825 * evaluates to 'true' or 'false'
1827 #define DECISIONMAP_TRUE(p) ((p) > 0 ? (decisionmap[p] > 0) : (decisionmap[-p] < 0))
1828 #define DECISIONMAP_FALSE(p) ((p) > 0 ? (decisionmap[p] < 0) : (decisionmap[-p] > 0))
1829 #define DECISIONMAP_UNDEF(p) (decisionmap[(p) > 0 ? (p) : -(p)] == 0)
1831 /*-------------------------------------------------------------------
1835 * make decision and propagate to all rules
1837 * Evaluate each term affected by the decision (linked through watches)
1838 * If we find unit rules we make new decisions based on them
1840 * Everything's fixed there, it's just finding rules that are
1843 * return : 0 = everything is OK
1844 * rule = conflict found in this rule
1848 propagate(Solver *solv, int level)
1850 Pool *pool = solv->pool;
1851 Id *rp, *next_rp; /* rule pointer, next rule pointer in linked list */
1853 Id p, pkg, other_watch;
1855 Id *decisionmap = solv->decisionmap;
1857 Id *watches = solv->watches + pool->nsolvables; /* place ptr in middle */
1859 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "----- propagate -----\n");
1861 /* foreach non-propagated decision */
1862 while (solv->propagate_index < solv->decisionq.count)
1865 * 'pkg' was just decided
1866 * negate because our watches trigger if literal goes FALSE
1868 pkg = -solv->decisionq.elements[solv->propagate_index++];
1870 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1872 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "propagate for decision %d level %d\n", -pkg, level);
1873 solver_printruleelement(solv, SAT_DEBUG_PROPAGATE, 0, -pkg);
1876 /* foreach rule where 'pkg' is now FALSE */
1877 for (rp = watches + pkg; *rp; rp = next_rp)
1879 r = solv->rules + *rp;
1882 /* rule is disabled, goto next */
1890 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1892 POOL_DEBUG(SAT_DEBUG_PROPAGATE," watch triggered ");
1893 solver_printrule(solv, SAT_DEBUG_PROPAGATE, r);
1896 /* 'pkg' was just decided (was set to FALSE)
1898 * now find other literal watch, check clause
1899 * and advance on linked list
1903 other_watch = r->w2;
1908 other_watch = r->w1;
1913 * This term is already true (through the other literal)
1914 * so we have nothing to do
1916 if (DECISIONMAP_TRUE(other_watch))
1920 * The other literal is FALSE or UNDEF
1926 /* Not a binary clause, try to move our watch.
1928 * Go over all literals and find one that is
1932 * (TRUE is also ok, in that case the rule is fulfilled)
1934 if (r->p /* we have a 'p' */
1935 && r->p != other_watch /* which is not watched */
1936 && !DECISIONMAP_FALSE(r->p)) /* and not FALSE */
1940 else /* go find a 'd' to make 'true' */
1943 we just iterate sequentially, doing it in another order just changes the order of decisions, not the decisions itself
1945 for (dp = pool->whatprovidesdata + r->d; (p = *dp++) != 0;)
1947 if (p != other_watch /* which is not watched */
1948 && !DECISIONMAP_FALSE(p)) /* and not FALSE */
1956 * if we found some p that is UNDEF or TRUE, move
1959 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1962 POOL_DEBUG(SAT_DEBUG_PROPAGATE, " -> move w%d to %s\n", (pkg == r->w1 ? 1 : 2), solvable2str(pool, pool->solvables + p));
1964 POOL_DEBUG(SAT_DEBUG_PROPAGATE," -> move w%d to !%s\n", (pkg == r->w1 ? 1 : 2), solvable2str(pool, pool->solvables - p));
1980 watches[p] = r - solv->rules;
1983 /* search failed, thus all unwatched literals are FALSE */
1988 * unit clause found, set literal other_watch to TRUE
1991 if (DECISIONMAP_FALSE(other_watch)) /* check if literal is FALSE */
1992 return r; /* eek, a conflict! */
1994 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1996 POOL_DEBUG(SAT_DEBUG_PROPAGATE, " unit ");
1997 solver_printrule(solv, SAT_DEBUG_PROPAGATE, r);
2000 if (other_watch > 0)
2001 decisionmap[other_watch] = level; /* install! */
2003 decisionmap[-other_watch] = -level; /* remove! */
2005 queue_push(&solv->decisionq, other_watch);
2006 queue_push(&solv->decisionq_why, r - solv->rules);
2008 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
2010 Solvable *s = pool->solvables + (other_watch > 0 ? other_watch : -other_watch);
2011 if (other_watch > 0)
2012 POOL_DEBUG(SAT_DEBUG_PROPAGATE, " -> decided to install %s\n", solvable2str(pool, s));
2014 POOL_DEBUG(SAT_DEBUG_PROPAGATE, " -> decided to conflict %s\n", solvable2str(pool, s));
2017 } /* foreach rule involving 'pkg' */
2019 } /* while we have non-decided decisions */
2021 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "----- propagate end-----\n");
2023 return 0; /* all is well */
2027 /********************************************************************/
2030 /*-------------------------------------------------------------------
2037 analyze(Solver *solv, int level, Rule *c, int *pr, int *dr, int *whyp)
2039 Pool *pool = solv->pool;
2042 Map seen; /* global? */
2043 Id d, v, vv, *dp, why;
2045 int num = 0, l1num = 0;
2046 int learnt_why = solv->learnt_pool.count;
2047 Id *decisionmap = solv->decisionmap;
2051 POOL_DEBUG(SAT_DEBUG_ANALYZE, "ANALYZE at %d ----------------------\n", level);
2052 map_init(&seen, pool->nsolvables);
2053 idx = solv->decisionq.count;
2056 IF_POOLDEBUG (SAT_DEBUG_ANALYZE)
2057 solver_printruleclass(solv, SAT_DEBUG_ANALYZE, c);
2058 queue_push(&solv->learnt_pool, c - solv->rules);
2059 d = c->d < 0 ? -c->d - 1 : c->d;
2060 dp = d ? pool->whatprovidesdata + d : 0;
2061 /* go through all literals of the rule */
2073 if (DECISIONMAP_TRUE(v)) /* the one true literal */
2075 vv = v > 0 ? v : -v;
2076 if (MAPTST(&seen, vv))
2078 l = solv->decisionmap[vv];
2083 l1num++; /* need to do this one in level1 pass */
2084 else if (l == level)
2085 num++; /* need to do this one as well */
2088 queue_push(&r, v); /* not level1 or conflict level, add to new rule */
2094 if (!num && !--l1num)
2095 break; /* all level 1 literals done */
2099 v = solv->decisionq.elements[--idx];
2100 vv = v > 0 ? v : -v;
2101 if (MAPTST(&seen, vv))
2105 if (num && --num == 0)
2107 *pr = -v; /* so that v doesn't get lost */
2110 POOL_DEBUG(SAT_DEBUG_ANALYZE, "got %d involved level 1 decisions\n", l1num);
2111 for (i = 0; i < r.count; i++)
2114 MAPCLR(&seen, v > 0 ? v : -v);
2116 /* only level 1 marks left */
2120 why = solv->decisionq_why.elements[idx];
2121 if (why <= 0) /* just in case, maybe for SYSTEMSOLVABLE */
2123 c = solv->rules + why;
2129 else if (r.count == 1 && r.elements[0] < 0)
2130 *dr = r.elements[0];
2132 *dr = pool_queuetowhatprovides(pool, &r);
2133 IF_POOLDEBUG (SAT_DEBUG_ANALYZE)
2135 POOL_DEBUG(SAT_DEBUG_ANALYZE, "learned rule for level %d (am %d)\n", rlevel, level);
2136 solver_printruleelement(solv, SAT_DEBUG_ANALYZE, 0, *pr);
2137 for (i = 0; i < r.count; i++)
2138 solver_printruleelement(solv, SAT_DEBUG_ANALYZE, 0, r.elements[i]);
2140 /* push end marker on learnt reasons stack */
2141 queue_push(&solv->learnt_pool, 0);
2144 solv->stats_learned++;
2149 /*-------------------------------------------------------------------
2153 * reset the solver decisions to right after the rpm rules.
2154 * called after rules have been enabled/disabled
2158 reset_solver(Solver *solv)
2160 Pool *pool = solv->pool;
2164 /* rewind decisions to direct rpm rule assertions */
2165 for (i = solv->decisionq.count - 1; i >= solv->directdecisions; i--)
2167 v = solv->decisionq.elements[i];
2168 solv->decisionmap[v > 0 ? v : -v] = 0;
2171 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "decisions done reduced from %d to %d\n", solv->decisionq.count, solv->directdecisions);
2173 solv->decisionq_why.count = solv->directdecisions;
2174 solv->decisionq.count = solv->directdecisions;
2175 solv->recommends_index = -1;
2176 solv->propagate_index = 0;
2178 /* adapt learnt rule status to new set of enabled/disabled rules */
2179 enabledisablelearntrules(solv);
2181 /* redo all job/update decisions */
2182 makeruledecisions(solv);
2183 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "decisions so far: %d\n", solv->decisionq.count);
2187 /*-------------------------------------------------------------------
2189 * analyze_unsolvable_rule
2193 analyze_unsolvable_rule(Solver *solv, Rule *r, Id *lastweakp)
2195 Pool *pool = solv->pool;
2197 Id why = r - solv->rules;
2199 IF_POOLDEBUG (SAT_DEBUG_UNSOLVABLE)
2200 solver_printruleclass(solv, SAT_DEBUG_UNSOLVABLE, r);
2201 if (solv->learntrules && why >= solv->learntrules)
2203 for (i = solv->learnt_why.elements[why - solv->learntrules]; solv->learnt_pool.elements[i]; i++)
2204 if (solv->learnt_pool.elements[i] > 0)
2205 analyze_unsolvable_rule(solv, solv->rules + solv->learnt_pool.elements[i], lastweakp);
2208 if (MAPTST(&solv->weakrulemap, why))
2209 if (!*lastweakp || why > *lastweakp)
2211 /* do not add rpm rules to problem */
2212 if (why < solv->rpmrules_end)
2214 /* turn rule into problem */
2215 if (why >= solv->jobrules && why < solv->jobrules_end)
2216 why = -(solv->ruletojob.elements[why - solv->jobrules] + 1);
2217 /* normalize dup/infarch rules */
2218 if (why > solv->infarchrules && why < solv->infarchrules_end)
2220 Id name = pool->solvables[-solv->rules[why].p].name;
2221 while (why > solv->infarchrules && pool->solvables[-solv->rules[why - 1].p].name == name)
2224 if (why > solv->duprules && why < solv->duprules_end)
2226 Id name = pool->solvables[-solv->rules[why].p].name;
2227 while (why > solv->duprules && pool->solvables[-solv->rules[why - 1].p].name == name)
2231 /* return if problem already countains our rule */
2232 if (solv->problems.count)
2234 for (i = solv->problems.count - 1; i >= 0; i--)
2235 if (solv->problems.elements[i] == 0) /* end of last problem reached? */
2237 else if (solv->problems.elements[i] == why)
2240 queue_push(&solv->problems, why);
2244 /*-------------------------------------------------------------------
2246 * analyze_unsolvable
2248 * return: 1 - disabled some rules, try again
2253 analyze_unsolvable(Solver *solv, Rule *cr, int disablerules)
2255 Pool *pool = solv->pool;
2257 Map seen; /* global to speed things up? */
2258 Id d, v, vv, *dp, why;
2260 Id *decisionmap = solv->decisionmap;
2261 int oldproblemcount;
2262 int oldlearntpoolcount;
2265 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "ANALYZE UNSOLVABLE ----------------------\n");
2266 solv->stats_unsolvable++;
2267 oldproblemcount = solv->problems.count;
2268 oldlearntpoolcount = solv->learnt_pool.count;
2270 /* make room for proof index */
2271 /* must update it later, as analyze_unsolvable_rule would confuse
2272 * it with a rule index if we put the real value in already */
2273 queue_push(&solv->problems, 0);
2276 map_init(&seen, pool->nsolvables);
2277 queue_push(&solv->learnt_pool, r - solv->rules);
2279 analyze_unsolvable_rule(solv, r, &lastweak);
2280 d = r->d < 0 ? -r->d - 1 : r->d;
2281 dp = d ? pool->whatprovidesdata + d : 0;
2292 if (DECISIONMAP_TRUE(v)) /* the one true literal */
2294 vv = v > 0 ? v : -v;
2295 l = solv->decisionmap[vv];
2300 idx = solv->decisionq.count;
2303 v = solv->decisionq.elements[--idx];
2304 vv = v > 0 ? v : -v;
2305 if (!MAPTST(&seen, vv))
2307 why = solv->decisionq_why.elements[idx];
2309 queue_push(&solv->learnt_pool, why);
2310 r = solv->rules + why;
2311 analyze_unsolvable_rule(solv, r, &lastweak);
2312 d = r->d < 0 ? -r->d - 1 : r->d;
2313 dp = d ? pool->whatprovidesdata + d : 0;
2324 if (DECISIONMAP_TRUE(v)) /* the one true literal */
2326 vv = v > 0 ? v : -v;
2327 l = solv->decisionmap[vv];
2334 queue_push(&solv->problems, 0); /* mark end of this problem */
2339 /* disable last weak rule */
2340 solv->problems.count = oldproblemcount;
2341 solv->learnt_pool.count = oldlearntpoolcount;
2342 if (lastweak >= solv->jobrules && lastweak < solv->jobrules_end)
2343 v = -(solv->ruletojob.elements[lastweak - solv->jobrules] + 1);
2346 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "disabling ");
2347 solver_printruleclass(solv, SAT_DEBUG_UNSOLVABLE, solv->rules + lastweak);
2348 disableproblem(solv, v);
2350 reenablepolicyrules(solv, solv->job, -(v + 1));
2356 queue_push(&solv->learnt_pool, 0);
2357 solv->problems.elements[oldproblemcount] = oldlearntpoolcount;
2361 for (i = oldproblemcount + 1; i < solv->problems.count - 1; i++)
2362 disableproblem(solv, solv->problems.elements[i]);
2363 /* XXX: might want to enable all weak rules again */
2367 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "UNSOLVABLE\n");
2372 /********************************************************************/
2373 /* Decision revert */
2375 /*-------------------------------------------------------------------
2378 * revert decision at level
2382 revert(Solver *solv, int level)
2384 Pool *pool = solv->pool;
2386 while (solv->decisionq.count)
2388 v = solv->decisionq.elements[solv->decisionq.count - 1];
2389 vv = v > 0 ? v : -v;
2390 if (solv->decisionmap[vv] <= level && solv->decisionmap[vv] >= -level)
2392 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "reverting decision %d at %d\n", v, solv->decisionmap[vv]);
2393 if (v > 0 && solv->recommendations.count && v == solv->recommendations.elements[solv->recommendations.count - 1])
2394 solv->recommendations.count--;
2395 solv->decisionmap[vv] = 0;
2396 solv->decisionq.count--;
2397 solv->decisionq_why.count--;
2398 solv->propagate_index = solv->decisionq.count;
2400 while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] <= -level)
2402 solv->branches.count--;
2403 while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] >= 0)
2404 solv->branches.count--;
2406 solv->recommends_index = -1;
2410 /*-------------------------------------------------------------------
2412 * watch2onhighest - put watch2 on literal with highest level
2416 watch2onhighest(Solver *solv, Rule *r)
2421 d = r->d < 0 ? -r->d - 1 : r->d;
2423 return; /* binary rule, both watches are set */
2424 dp = solv->pool->whatprovidesdata + d;
2425 while ((v = *dp++) != 0)
2427 l = solv->decisionmap[v < 0 ? -v : v];
2439 /*-------------------------------------------------------------------
2443 * add free decision (solvable to install) to decisionq
2444 * increase level and propagate decision
2445 * return if no conflict.
2447 * in conflict case, analyze conflict rule, add resulting
2448 * rule to learnt rule set, make decision from learnt
2449 * rule (always unit) and re-propagate.
2451 * returns the new solver level or 0 if unsolvable
2456 setpropagatelearn(Solver *solv, int level, Id decision, int disablerules, Id ruleid)
2458 Pool *pool = solv->pool;
2463 assert(ruleid >= 0);
2468 solv->decisionmap[decision] = level;
2470 solv->decisionmap[-decision] = -level;
2471 queue_push(&solv->decisionq, decision);
2472 queue_push(&solv->decisionq_why, -ruleid); /* <= 0 -> free decision */
2476 r = propagate(solv, level);
2480 return analyze_unsolvable(solv, r, disablerules);
2481 POOL_DEBUG(SAT_DEBUG_ANALYZE, "conflict with rule #%d\n", (int)(r - solv->rules));
2482 l = analyze(solv, level, r, &p, &d, &why); /* learnt rule in p and d */
2483 assert(l > 0 && l < level);
2484 POOL_DEBUG(SAT_DEBUG_ANALYZE, "reverting decisions (level %d -> %d)\n", level, l);
2486 revert(solv, level);
2487 r = addrule(solv, p, d);
2489 assert(solv->learnt_why.count == (r - solv->rules) - solv->learntrules);
2490 queue_push(&solv->learnt_why, why);
2493 /* at least 2 literals, needs watches */
2494 watch2onhighest(solv, r);
2495 addwatches_rule(solv, r);
2499 /* learnt rule is an assertion */
2500 queue_push(&solv->ruleassertions, r - solv->rules);
2502 solv->decisionmap[p > 0 ? p : -p] = p > 0 ? level : -level;
2503 queue_push(&solv->decisionq, p);
2504 queue_push(&solv->decisionq_why, r - solv->rules);
2505 IF_POOLDEBUG (SAT_DEBUG_ANALYZE)
2507 POOL_DEBUG(SAT_DEBUG_ANALYZE, "decision: ");
2508 solver_printruleelement(solv, SAT_DEBUG_ANALYZE, 0, p);
2509 POOL_DEBUG(SAT_DEBUG_ANALYZE, "new rule: ");
2510 solver_printrule(solv, SAT_DEBUG_ANALYZE, r);
2517 /*-------------------------------------------------------------------
2519 * select and install
2521 * install best package from the queue. We add an extra package, inst, if
2522 * provided. See comment in weak install section.
2524 * returns the new solver level or 0 if unsolvable
2529 selectandinstall(Solver *solv, int level, Queue *dq, int disablerules, Id ruleid)
2531 Pool *pool = solv->pool;
2536 policy_filter_unwanted(solv, dq, POLICY_MODE_CHOOSE);
2539 /* XXX: didn't we already do that? */
2540 /* XXX: shouldn't we prefer installed packages? */
2541 /* XXX: move to policy.c? */
2542 /* choose the supplemented one */
2543 for (i = 0; i < dq->count; i++)
2544 if (solver_is_supplementing(solv, pool->solvables + dq->elements[i]))
2546 dq->elements[0] = dq->elements[i];
2553 /* multiple candidates, open a branch */
2554 for (i = 1; i < dq->count; i++)
2555 queue_push(&solv->branches, dq->elements[i]);
2556 queue_push(&solv->branches, -level);
2558 p = dq->elements[0];
2560 POOL_DEBUG(SAT_DEBUG_POLICY, "installing %s\n", solvable2str(pool, pool->solvables + p));
2562 return setpropagatelearn(solv, level, p, disablerules, ruleid);
2566 /********************************************************************/
2567 /* Main solver interface */
2570 /*-------------------------------------------------------------------
2573 * create solver structure
2575 * pool: all available solvables
2576 * installed: installed Solvables
2579 * Upon solving, rules are created to flag the Solvables
2580 * of the 'installed' Repo as installed.
2584 solver_create(Pool *pool)
2587 solv = (Solver *)sat_calloc(1, sizeof(Solver));
2589 solv->installed = pool->installed;
2591 queue_init(&solv->ruletojob);
2592 queue_init(&solv->decisionq);
2593 queue_init(&solv->decisionq_why);
2594 queue_init(&solv->problems);
2595 queue_init(&solv->suggestions);
2596 queue_init(&solv->recommendations);
2597 queue_init(&solv->orphaned);
2598 queue_init(&solv->learnt_why);
2599 queue_init(&solv->learnt_pool);
2600 queue_init(&solv->branches);
2601 queue_init(&solv->covenantq);
2602 queue_init(&solv->weakruleq);
2603 queue_init(&solv->ruleassertions);
2605 map_init(&solv->recommendsmap, pool->nsolvables);
2606 map_init(&solv->suggestsmap, pool->nsolvables);
2607 map_init(&solv->noupdate, solv->installed ? solv->installed->end - solv->installed->start : 0);
2608 solv->recommends_index = 0;
2610 solv->decisionmap = (Id *)sat_calloc(pool->nsolvables, sizeof(Id));
2612 solv->rules = sat_extend_resize(solv->rules, solv->nrules, sizeof(Rule), RULES_BLOCK);
2613 memset(solv->rules, 0, sizeof(Rule));
2619 /*-------------------------------------------------------------------
2625 solver_free(Solver *solv)
2627 queue_free(&solv->ruletojob);
2628 queue_free(&solv->decisionq);
2629 queue_free(&solv->decisionq_why);
2630 queue_free(&solv->learnt_why);
2631 queue_free(&solv->learnt_pool);
2632 queue_free(&solv->problems);
2633 queue_free(&solv->suggestions);
2634 queue_free(&solv->recommendations);
2635 queue_free(&solv->orphaned);
2636 queue_free(&solv->branches);
2637 queue_free(&solv->covenantq);
2638 queue_free(&solv->weakruleq);
2639 queue_free(&solv->ruleassertions);
2641 map_free(&solv->recommendsmap);
2642 map_free(&solv->suggestsmap);
2643 map_free(&solv->noupdate);
2644 map_free(&solv->weakrulemap);
2645 map_free(&solv->noobsoletes);
2647 map_free(&solv->updatemap);
2648 map_free(&solv->dupmap);
2649 map_free(&solv->dupinvolvedmap);
2651 sat_free(solv->decisionmap);
2652 sat_free(solv->rules);
2653 sat_free(solv->watches);
2654 sat_free(solv->obsoletes);
2655 sat_free(solv->obsoletes_data);
2656 sat_free(solv->multiversionupdaters);
2661 /*-------------------------------------------------------------------
2665 * all rules have been set up, now actually run the solver
2670 run_solver(Solver *solv, int disablerules, int doweak)
2672 Queue dq; /* local decisionqueue */
2673 Queue dqs; /* local decisionqueue for supplements */
2679 Pool *pool = solv->pool;
2681 int minimizationsteps;
2683 IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION)
2685 POOL_DEBUG (SAT_DEBUG_RULE_CREATION, "number of rules: %d\n", solv->nrules);
2686 for (i = 1; i < solv->nrules; i++)
2687 solver_printruleclass(solv, SAT_DEBUG_RULE_CREATION, solv->rules + i);
2690 POOL_DEBUG(SAT_DEBUG_STATS, "initial decisions: %d\n", solv->decisionq.count);
2692 IF_POOLDEBUG (SAT_DEBUG_SCHUBI)
2693 solver_printdecisions(solv);
2695 /* start SAT algorithm */
2697 systemlevel = level + 1;
2698 POOL_DEBUG(SAT_DEBUG_STATS, "solving...\n");
2704 * here's the main loop:
2705 * 1) propagate new decisions (only needed for level 1)
2706 * 2) try to keep installed packages
2707 * 3) fulfill all unresolved rules
2708 * 4) install recommended packages
2709 * 5) minimalize solution if we had choices
2710 * if we encounter a problem, we rewind to a safe level and restart
2714 minimizationsteps = 0;
2723 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "propagating (propagate_index: %d; size decisionq: %d)...\n", solv->propagate_index, solv->decisionq.count);
2724 if ((r = propagate(solv, level)) != 0)
2726 if (analyze_unsolvable(solv, r, disablerules))
2734 if (level < systemlevel)
2736 POOL_DEBUG(SAT_DEBUG_STATS, "resolving job rules\n");
2737 for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++)
2740 if (r->d < 0) /* ignore disabled rules */
2743 FOR_RULELITERALS(l, dp, r)
2747 if (solv->decisionmap[-l] <= 0)
2752 if (solv->decisionmap[l] > 0)
2754 if (solv->decisionmap[l] == 0)
2760 /* prune to installed if not updating */
2761 if (!solv->updatesystem && solv->installed && dq.count > 1)
2764 for (j = k = 0; j < dq.count; j++)
2766 Solvable *s = pool->solvables + dq.elements[j];
2767 if (s->repo == solv->installed)
2768 dq.elements[k++] = dq.elements[j];
2774 level = selectandinstall(solv, level, &dq, disablerules, i);
2781 if (level <= olevel)
2784 systemlevel = level + 1;
2785 if (i < solv->jobrules_end)
2791 * installed packages
2794 if (level < systemlevel && solv->installed && solv->installed->nsolvables)
2796 Repo *installed = solv->installed;
2799 /* we use two passes if we need to update packages
2800 * to create a better user experience */
2801 for (pass = solv->updatemap.size ? 0 : 1; pass < 2; pass++)
2803 FOR_REPO_SOLVABLES(installed, i, s)
2808 /* XXX: noupdate check is probably no longer needed, as all jobs should
2809 * already be satisfied */
2810 if (MAPTST(&solv->noupdate, i - installed->start))
2812 if (solv->decisionmap[i] > 0)
2814 if (!pass && solv->updatemap.size && !MAPTST(&solv->updatemap, i - installed->start))
2815 continue; /* updates first */
2816 r = solv->rules + solv->updaterules + (i - installed->start);
2818 if (!rr->p || rr->d < 0) /* disabled -> look at feature rule */
2819 rr -= solv->installed->end - solv->installed->start;
2820 if (!rr->p) /* identical to update rule? */
2823 continue; /* orpaned package */
2826 if (solv->decisionmap[i] < 0 || solv->updatesystem || (solv->updatemap.size && MAPTST(&solv->updatemap, i - installed->start)) || rr->p != i)
2828 if (solv->noobsoletes.size && solv->multiversionupdaters
2829 && (d = solv->multiversionupdaters[i - installed->start]) != 0)
2831 /* special multiversion handling, make sure best version is chosen */
2833 while ((p = pool->whatprovidesdata[d++]) != 0)
2834 if (solv->decisionmap[p] >= 0)
2836 policy_filter_unwanted(solv, &dq, POLICY_MODE_CHOOSE);
2838 if (p != i && solv->decisionmap[p] == 0)
2840 rr = solv->rules + solv->featurerules + (i - solv->installed->start);
2841 if (!rr->p) /* update rule == feature rule? */
2842 rr = rr - solv->featurerules + solv->updaterules;
2850 /* update to best package */
2851 FOR_RULELITERALS(p, dp, rr)
2853 if (solv->decisionmap[p] > 0)
2855 dq.count = 0; /* already fulfilled */
2858 if (!solv->decisionmap[p])
2863 /* install best version */
2867 level = selectandinstall(solv, level, &dq, disablerules, rr - solv->rules);
2874 if (level <= olevel)
2877 /* if still undecided keep package */
2878 if (solv->decisionmap[i] == 0)
2881 POOL_DEBUG(SAT_DEBUG_POLICY, "keeping %s\n", solvable2str(pool, pool->solvables + i));
2882 level = setpropagatelearn(solv, level, i, disablerules, r - solv->rules);
2889 if (level <= olevel)
2893 if (i < installed->end)
2896 systemlevel = level + 1;
2898 continue; /* had trouble, retry */
2901 if (level < systemlevel)
2902 systemlevel = level;
2908 POOL_DEBUG(SAT_DEBUG_POLICY, "deciding unresolved rules\n");
2909 for (i = 1, n = 1; ; i++, n++)
2911 if (n == solv->nrules)
2913 if (i == solv->nrules)
2915 r = solv->rules + i;
2916 if (r->d < 0) /* ignore disabled rules */
2921 /* binary or unary rule */
2922 /* need two positive undecided literals */
2923 if (r->p < 0 || r->w2 <= 0)
2925 if (solv->decisionmap[r->p] || solv->decisionmap[r->w2])
2927 queue_push(&dq, r->p);
2928 queue_push(&dq, r->w2);
2933 * all negative literals are installed
2934 * no positive literal is installed
2935 * i.e. the rule is not fulfilled and we
2936 * just need to decide on the positive literals
2940 if (solv->decisionmap[-r->p] <= 0)
2945 if (solv->decisionmap[r->p] > 0)
2947 if (solv->decisionmap[r->p] == 0)
2948 queue_push(&dq, r->p);
2950 dp = pool->whatprovidesdata + r->d;
2951 while ((p = *dp++) != 0)
2955 if (solv->decisionmap[-p] <= 0)
2960 if (solv->decisionmap[p] > 0)
2962 if (solv->decisionmap[p] == 0)
2969 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
2971 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "unfulfilled ");
2972 solver_printruleclass(solv, SAT_DEBUG_PROPAGATE, r);
2974 /* dq.count < 2 cannot happen as this means that
2975 * the rule is unit */
2976 assert(dq.count > 1);
2979 level = selectandinstall(solv, level, &dq, disablerules, r - solv->rules);
2986 if (level < systemlevel)
2989 } /* for(), decide */
2991 if (n != solv->nrules) /* continue if level < systemlevel */
2998 POOL_DEBUG(SAT_DEBUG_POLICY, "installing recommended packages\n");
2999 queue_empty(&dq); /* recommended packages */
3000 queue_empty(&dqs); /* supplemented packages */
3001 for (i = 1; i < pool->nsolvables; i++)
3003 if (solv->decisionmap[i] < 0)
3005 if (solv->decisionmap[i] > 0)
3007 /* installed, check for recommends */
3008 Id *recp, rec, pp, p;
3009 s = pool->solvables + i;
3010 if (solv->ignorealreadyrecommended && s->repo == solv->installed)
3012 /* XXX need to special case AND ? */
3015 recp = s->repo->idarraydata + s->recommends;
3016 while ((rec = *recp++) != 0)
3019 FOR_PROVIDES(p, pp, rec)
3021 if (solv->decisionmap[p] > 0)
3026 else if (solv->decisionmap[p] == 0)
3028 queue_pushunique(&dq, p);
3036 s = pool->solvables + i;
3037 if (!s->supplements)
3039 if (!pool_installable(pool, s))
3041 if (!solver_is_supplementing(solv, s))
3043 queue_push(&dqs, i);
3047 /* filter out all packages obsoleted by installed packages */
3048 /* this is no longer needed if we have reverse obsoletes */
3049 if ((dqs.count || dq.count) && solv->installed)
3052 Id obs, *obsp, po, ppo;
3054 map_init(&obsmap, pool->nsolvables);
3055 for (p = solv->installed->start; p < solv->installed->end; p++)
3057 s = pool->solvables + p;
3058 if (s->repo != solv->installed || !s->obsoletes)
3060 if (solv->decisionmap[p] <= 0)
3062 if (solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p))
3064 obsp = s->repo->idarraydata + s->obsoletes;
3065 /* foreach obsoletes */
3066 while ((obs = *obsp++) != 0)
3067 FOR_PROVIDES(po, ppo, obs)
3068 MAPSET(&obsmap, po);
3070 for (i = j = 0; i < dqs.count; i++)
3071 if (!MAPTST(&obsmap, dqs.elements[i]))
3072 dqs.elements[j++] = dqs.elements[i];
3074 for (i = j = 0; i < dq.count; i++)
3075 if (!MAPTST(&obsmap, dq.elements[i]))
3076 dq.elements[j++] = dq.elements[i];
3081 /* filter out all already supplemented packages if requested */
3082 if (solv->ignorealreadyrecommended && dqs.count)
3084 /* turn off all new packages */
3085 for (i = 0; i < solv->decisionq.count; i++)
3087 p = solv->decisionq.elements[i];
3090 s = pool->solvables + p;
3091 if (s->repo && s->repo != solv->installed)
3092 solv->decisionmap[p] = -solv->decisionmap[p];
3094 /* filter out old supplements */
3095 for (i = j = 0; i < dqs.count; i++)
3097 p = dqs.elements[i];
3098 s = pool->solvables + p;
3099 if (!s->supplements)
3101 if (!solver_is_supplementing(solv, s))
3102 dqs.elements[j++] = p;
3105 /* undo turning off */
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];
3117 /* make dq contain both recommended and supplemented pkgs */
3120 for (i = 0; i < dqs.count; i++)
3121 queue_pushunique(&dq, dqs.elements[i]);
3128 int decisioncount = solv->decisionq.count;
3132 /* simple case, just one package. no need to choose */
3135 POOL_DEBUG(SAT_DEBUG_POLICY, "installing supplemented %s\n", solvable2str(pool, pool->solvables + p));
3137 POOL_DEBUG(SAT_DEBUG_POLICY, "installing recommended %s\n", solvable2str(pool, pool->solvables + p));
3138 queue_push(&solv->recommendations, p);
3139 level = setpropagatelearn(solv, level, p, 0, 0);
3143 /* filter and create a map of result */
3144 policy_filter_unwanted(solv, &dq, POLICY_MODE_RECOMMEND);
3145 map_init(&dqmap, pool->nsolvables);
3146 for (i = 0; i < dq.count; i++)
3147 MAPSET(&dqmap, dq.elements[i]);
3149 /* install all supplemented packages */
3150 for (i = 0; i < dqs.count; i++)
3152 p = dqs.elements[i];
3153 if (solv->decisionmap[p] || !MAPTST(&dqmap, p))
3155 POOL_DEBUG(SAT_DEBUG_POLICY, "installing supplemented %s\n", solvable2str(pool, pool->solvables + p));
3156 queue_push(&solv->recommendations, p);
3158 level = setpropagatelearn(solv, level, p, 0, 0);
3159 if (level <= olevel)
3162 if (i < dqs.count || solv->decisionq.count < decisioncount)
3168 /* install all recommended packages */
3169 /* more work as we want to created branches if multiple
3170 * choices are valid */
3171 for (i = 0; i < decisioncount; i++)
3174 p = solv->decisionq.elements[i];
3177 s = pool->solvables + p;
3178 if (!s->repo || (solv->ignorealreadyrecommended && s->repo == solv->installed))
3182 recp = s->repo->idarraydata + s->recommends;
3183 while ((rec = *recp++) != 0)
3186 FOR_PROVIDES(p, pp, rec)
3188 if (solv->decisionmap[p] > 0)
3193 else if (solv->decisionmap[p] == 0 && MAPTST(&dqmap, p))
3194 queue_pushunique(&dq, p);
3200 /* multiple candidates, open a branch */
3201 for (i = 1; i < dq.count; i++)
3202 queue_push(&solv->branches, dq.elements[i]);
3203 queue_push(&solv->branches, -level);
3206 POOL_DEBUG(SAT_DEBUG_POLICY, "installing recommended %s\n", solvable2str(pool, pool->solvables + p));
3207 queue_push(&solv->recommendations, p);
3209 level = setpropagatelearn(solv, level, p, 0, 0);
3210 if (level <= olevel || solv->decisionq.count < decisioncount)
3214 break; /* had a problem above, quit loop */
3223 policy_filter_unwanted(solv, &dq, POLICY_MODE_RECOMMEND);
3225 /* prefer recommended patterns (bnc#450226) */
3226 /* real fix is to minimize recommended packages as well */
3227 for (i = 0; i < dq.count; i++)
3228 if (!strncmp(id2str(pool, pool->solvables[dq.elements[i]].name), "pattern:", 8))
3233 POOL_DEBUG(SAT_DEBUG_POLICY, "installing recommended %s\n", solvable2str(pool, pool->solvables + p));
3234 queue_push(&solv->recommendations, p);
3235 level = setpropagatelearn(solv, level, p, 0, 0);
3241 if (solv->distupgrade && solv->installed)
3243 int installedone = 0;
3245 /* let's see if we can install some unsupported package */
3246 POOL_DEBUG(SAT_DEBUG_STATS, "deciding unsupported packages\n");
3247 for (i = 0; i < solv->orphaned.count; i++)
3249 p = solv->orphaned.elements[i];
3250 if (solv->decisionmap[p])
3251 continue; /* already decided */
3253 if (solv->distupgrade_removeunsupported)
3255 POOL_DEBUG(SAT_DEBUG_STATS, "removing unsupported %s\n", solvable2str(pool, pool->solvables + p));
3256 level = setpropagatelearn(solv, level, -p, 0, 0);
3260 POOL_DEBUG(SAT_DEBUG_STATS, "keeping unsupported %s\n", solvable2str(pool, pool->solvables + p));
3261 level = setpropagatelearn(solv, level, p, 0, 0);
3267 if (installedone || i < solv->orphaned.count)
3271 if (solv->solution_callback)
3273 solv->solution_callback(solv, solv->solution_callback_data);
3274 if (solv->branches.count)
3276 int i = solv->branches.count - 1;
3277 int l = -solv->branches.elements[i];
3281 if (solv->branches.elements[i - 1] < 0)
3283 p = solv->branches.elements[i];
3284 POOL_DEBUG(SAT_DEBUG_STATS, "branching with %s\n", solvable2str(pool, pool->solvables + p));
3286 for (j = i + 1; j < solv->branches.count; j++)
3287 queue_push(&dq, solv->branches.elements[j]);
3288 solv->branches.count = i;
3290 revert(solv, level);
3292 for (j = 0; j < dq.count; j++)
3293 queue_push(&solv->branches, dq.elements[j]);
3295 why = -solv->decisionq_why.elements[solv->decisionq_why.count];
3297 level = setpropagatelearn(solv, level, p, disablerules, why);
3306 /* all branches done, we're finally finished */
3310 /* minimization step */
3311 if (solv->branches.count)
3313 int l = 0, lasti = -1, lastl = -1;
3317 for (i = solv->branches.count - 1; i >= 0; i--)
3319 p = solv->branches.elements[i];
3322 else if (p > 0 && solv->decisionmap[p] > l + 1)
3330 /* kill old solvable so that we do not loop */
3331 p = solv->branches.elements[lasti];
3332 solv->branches.elements[lasti] = 0;
3333 POOL_DEBUG(SAT_DEBUG_STATS, "minimizing %d -> %d with %s\n", solv->decisionmap[p], lastl, solvable2str(pool, pool->solvables + p));
3334 minimizationsteps++;
3337 revert(solv, level);
3338 why = -solv->decisionq_why.elements[solv->decisionq_why.count];
3341 level = setpropagatelearn(solv, level, p, disablerules, why);
3353 POOL_DEBUG(SAT_DEBUG_STATS, "solver statistics: %d learned rules, %d unsolvable, %d minimization steps\n", solv->stats_learned, solv->stats_unsolvable, minimizationsteps);
3355 POOL_DEBUG(SAT_DEBUG_STATS, "done solving.\n\n");
3361 /*-------------------------------------------------------------------
3365 * at this point, all rules that led to conflicts are disabled.
3366 * we re-enable all rules of a problem set but rule "sug", then
3367 * continue to disable more rules until there as again a solution.
3370 /* FIXME: think about conflicting assertions */
3373 refine_suggestion(Solver *solv, Queue *job, Id *problem, Id sug, Queue *refined)
3375 Pool *pool = solv->pool;
3381 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
3383 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "refine_suggestion start\n");
3384 for (i = 0; problem[i]; i++)
3386 if (problem[i] == sug)
3387 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "=> ");
3388 solver_printproblem(solv, problem[i]);
3391 queue_init(&disabled);
3392 queue_empty(refined);
3393 queue_push(refined, sug);
3395 /* re-enable all problem rules with the exception of "sug"(gestion) */
3399 for (i = 0; problem[i]; i++)
3400 if (problem[i] != sug)
3401 enableproblem(solv, problem[i]);
3404 reenablepolicyrules(solv, job, -(sug + 1));
3405 else if (sug >= solv->updaterules && sug < solv->updaterules_end)
3407 /* enable feature rule */
3408 Rule *r = solv->rules + solv->featurerules + (sug - solv->updaterules);
3410 enablerule(solv, r);
3413 enableweakrules(solv);
3417 int njob, nfeature, nupdate;
3418 queue_empty(&solv->problems);
3419 revert(solv, 1); /* XXX no longer needed? */
3422 if (!solv->problems.count)
3423 run_solver(solv, 0, 0);
3425 if (!solv->problems.count)
3427 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "no more problems!\n");
3428 IF_POOLDEBUG (SAT_DEBUG_SCHUBI)
3429 solver_printdecisions(solv);
3430 break; /* great, no more problems */
3432 disabledcnt = disabled.count;
3433 /* start with 1 to skip over proof index */
3434 njob = nfeature = nupdate = 0;
3435 for (i = 1; i < solv->problems.count - 1; i++)
3437 /* ignore solutions in refined */
3438 v = solv->problems.elements[i];
3440 break; /* end of problem reached */
3441 for (j = 0; problem[j]; j++)
3442 if (problem[j] != sug && problem[j] == v)
3446 if (v >= solv->featurerules && v < solv->featurerules_end)
3452 if ((job->elements[-v -1] & SOLVER_ESSENTIAL) != 0)
3453 continue; /* not that one! */
3456 queue_push(&disabled, v);
3458 if (disabled.count == disabledcnt)
3460 /* no solution found, this was an invalid suggestion! */
3461 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "no solution found!\n");
3465 if (!njob && nupdate && nfeature)
3467 /* got only update rules, filter out feature rules */
3468 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "throwing away feature rules\n");
3469 for (i = j = disabledcnt; i < disabled.count; i++)
3471 v = disabled.elements[i];
3472 if (v < solv->featurerules || v >= solv->featurerules_end)
3473 disabled.elements[j++] = v;
3478 if (disabled.count == disabledcnt + 1)
3480 /* just one suggestion, add it to refined list */
3481 v = disabled.elements[disabledcnt];
3483 queue_push(refined, v); /* do not record feature rules */
3484 disableproblem(solv, v);
3485 if (v >= solv->updaterules && v < solv->updaterules_end)
3487 Rule *r = solv->rules + (v - solv->updaterules + solv->featurerules);
3489 enablerule(solv, r); /* enable corresponding feature rule */
3492 reenablepolicyrules(solv, job, -(v + 1));
3496 /* more than one solution, disable all */
3497 /* do not push anything on refine list, as we do not know which solution to choose */
3498 /* thus, the user will get another problem if he selects this solution, where he
3499 * can choose the right one */
3500 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
3502 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "more than one solution found:\n");
3503 for (i = disabledcnt; i < disabled.count; i++)
3504 solver_printproblem(solv, disabled.elements[i]);
3506 for (i = disabledcnt; i < disabled.count; i++)
3508 v = disabled.elements[i];
3509 disableproblem(solv, v);
3510 if (v >= solv->updaterules && v < solv->updaterules_end)
3512 Rule *r = solv->rules + (v - solv->updaterules + solv->featurerules);
3514 enablerule(solv, r);
3519 /* all done, get us back into the same state as before */
3520 /* enable refined rules again */
3521 for (i = 0; i < disabled.count; i++)
3522 enableproblem(solv, disabled.elements[i]);
3523 queue_free(&disabled);
3524 /* reset policy rules */
3525 for (i = 0; problem[i]; i++)
3526 enableproblem(solv, problem[i]);
3527 disablepolicyrules(solv, job);
3528 /* disable problem rules again */
3529 for (i = 0; problem[i]; i++)
3530 disableproblem(solv, problem[i]);
3531 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "refine_suggestion end\n");
3535 /*-------------------------------------------------------------------
3536 * sorting helper for problems
3538 * bring update rules before job rules
3539 * make essential job rules last
3542 Queue *problems_sort_data;
3545 problems_sortcmp(const void *ap, const void *bp)
3547 Id a = *(Id *)ap, b = *(Id *)bp;
3554 Queue *job = problems_sort_data;
3555 int af = job->elements[-a - 1] & SOLVER_ESSENTIAL;
3556 int bf = job->elements[-b - 1] & SOLVER_ESSENTIAL;
3565 /*-------------------------------------------------------------------
3570 problems_sort(Solver *solv, Queue *job)
3573 if (!solv->problems.count)
3575 for (i = j = 1; i < solv->problems.count; i++)
3577 if (!solv->problems.elements[i])
3581 problems_sort_data = job;
3582 qsort(solv->problems.elements + j, i - j, sizeof(Id), problems_sortcmp);
3584 if (++i == solv->problems.count)
3592 /*-------------------------------------------------------------------
3593 * convert problems to solutions
3597 problems_to_solutions(Solver *solv, Queue *job)
3599 Pool *pool = solv->pool;
3605 int i, j, nsol, probsolved;
3606 unsigned int now, refnow;
3608 if (!solv->problems.count)
3610 now = sat_timems(0);
3611 problems_sort(solv, job);
3612 queue_clone(&problems, &solv->problems);
3613 queue_init(&solution);
3614 queue_init(&solutions);
3615 /* copy over proof index */
3616 queue_push(&solutions, problems.elements[0]);
3617 problem = problems.elements + 1;
3619 refnow = sat_timems(0);
3620 for (i = 1; i < problems.count; i++)
3622 Id v = problems.elements[i];
3625 /* mark end of this problem */
3626 queue_push(&solutions, 0);
3627 queue_push(&solutions, 0);
3628 POOL_DEBUG(SAT_DEBUG_STATS, "refining took %d ms\n", sat_timems(refnow));
3629 if (i + 1 == problems.count)
3631 /* copy over proof of next problem */
3632 queue_push(&solutions, problems.elements[i + 1]);
3634 problem = problems.elements + i + 1;
3635 refnow = sat_timems(0);
3639 if (v < 0 && (job->elements[-v - 1] & SOLVER_ESSENTIAL))
3641 /* essential job, skip if we already have a non-essential
3645 probsolved = -1; /* show all solutions */
3647 refine_suggestion(solv, job, problem, v, &solution);
3648 if (!solution.count)
3649 continue; /* this solution didn't work out */
3652 for (j = 0; j < solution.count; j++)
3654 why = solution.elements[j];
3655 /* must be either job descriptor or update rule */
3657 solver_printproblem(solv, why);
3661 /* job descriptor */
3662 queue_push(&solutions, 0);
3663 queue_push(&solutions, -why);
3665 else if (why >= solv->infarchrules && why < solv->infarchrules_end)
3668 /* infarch rule, find replacement */
3669 assert(solv->rules[why].p < 0);
3670 name = pool->solvables[-solv->rules[why].p].name;
3671 while (why > solv->infarchrules && pool->solvables[-solv->rules[why - 1].p].name == name)
3674 for (; why < solv->infarchrules_end && pool->solvables[-solv->rules[why].p].name == name; why++)
3675 if (solv->decisionmap[-solv->rules[why].p] > 0)
3677 p = -solv->rules[why].p;
3681 p = -solv->rules[why].p; /* XXX: what to do here? */
3682 queue_push(&solutions, SOLVER_SOLUTION_INFARCH);
3683 queue_push(&solutions, p);
3685 else if (why >= solv->duprules && why < solv->duprules_end)
3688 /* dist upgrade rule, find replacement */
3689 assert(solv->rules[why].p < 0);
3690 name = pool->solvables[-solv->rules[why].p].name;
3691 while (why > solv->duprules && pool->solvables[-solv->rules[why - 1].p].name == name)
3694 for (; why < solv->duprules_end && pool->solvables[-solv->rules[why].p].name == name; why++)
3695 if (solv->decisionmap[-solv->rules[why].p] > 0)
3697 p = -solv->rules[why].p;
3701 p = -solv->rules[why].p; /* XXX: what to do here? */
3702 queue_push(&solutions, SOLVER_SOLUTION_DISTUPGRADE);
3703 queue_push(&solutions, p);
3707 /* update rule, find replacement package */
3711 assert(why >= solv->updaterules && why < solv->updaterules_end);
3712 /* check if this is a false positive, i.e. the update rule is fulfilled */
3713 rr = solv->rules + why;
3714 FOR_RULELITERALS(p, dp, rr)
3715 if (p > 0 && solv->decisionmap[p] > 0)
3718 continue; /* false alarm */
3720 p = solv->installed->start + (why - solv->updaterules);
3721 rr = solv->rules + solv->featurerules + (why - solv->updaterules);
3723 rr = solv->rules + why;
3724 if (solv->distupgrade && solv->rules[why].p != p && solv->decisionmap[p] > 0)
3726 /* distupgrade case, allow to keep old package */
3727 queue_push(&solutions, p);
3728 queue_push(&solutions, p);
3732 if (solv->decisionmap[p] > 0)
3733 continue; /* false alarm, turned out we can keep the package */
3736 int mvrp = 0; /* multi-version replacement */
3737 FOR_RULELITERALS(rp, dp, rr)
3739 if (rp > 0 && solv->decisionmap[rp] > 0 && pool->solvables[rp].repo != solv->installed)
3742 if (!(solv->noobsoletes.size && MAPTST(&solv->noobsoletes, rp)))
3748 /* found only multi-version replacements */
3749 /* have to split solution into two parts */
3750 queue_push(&solutions, p);
3751 queue_push(&solutions, mvrp);
3755 queue_push(&solutions, p);
3756 queue_push(&solutions, rp);
3760 /* mark end of this solution */
3765 queue_push(&solutions, 0);
3766 queue_push(&solutions, 0);
3770 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "Oops, everything was fine?\n");
3773 queue_free(&solution);
3774 queue_free(&problems);
3775 /* copy queue over to solutions */
3776 queue_free(&solv->problems);
3777 queue_clone(&solv->problems, &solutions);
3779 /* bring solver back into problem state */
3780 revert(solv, 1); /* XXX move to reset_solver? */
3783 assert(solv->problems.count == solutions.count);
3784 queue_free(&solutions);
3785 POOL_DEBUG(SAT_DEBUG_STATS, "problems_to_solutions took %d ms\n", sat_timems(now));
3789 /*-------------------------------------------------------------------
3793 * advance to next problem
3797 solver_next_problem(Solver *solv, Id problem)
3801 return solv->problems.count ? 1 : 0;
3802 pp = solv->problems.elements + problem;
3803 while (pp[0] || pp[1])
3807 while (pp[0] || pp[1])
3812 problem = pp - solv->problems.elements;
3813 if (problem >= solv->problems.count)
3819 /*-------------------------------------------------------------------
3825 solver_next_solution(Solver *solv, Id problem, Id solution)
3831 pp = solv->problems.elements + solution;
3832 return pp[0] || pp[1] ? solution : 0;
3834 pp = solv->problems.elements + solution;
3835 while (pp[0] || pp[1])
3838 solution = pp - solv->problems.elements;
3839 return pp[0] || pp[1] ? solution : 0;
3843 /*-------------------------------------------------------------------
3845 * solution element iterator
3849 solver_next_solutionelement(Solver *solv, Id problem, Id solution, Id element, Id *p, Id *rp)
3852 element = element ? element + 2 : solution;
3853 pp = solv->problems.elements + element;
3854 if (!(pp[0] || pp[1]))
3862 /*-------------------------------------------------------------------
3864 * Retrieve information about a problematic rule
3866 * this is basically the reverse of addrpmrulesforsolvable
3870 solver_problemruleinfo(Solver *solv, Queue *job, Id rid, Id *depp, Id *sourcep, Id *targetp)
3872 Pool *pool = solv->pool;
3873 Repo *installed = solv->installed;
3877 Id p, d, w2, pp, req, *reqp, con, *conp, obs, *obsp, *dp;
3880 if (rid >= solv->infarchrules && rid < solv->infarchrules_end)
3882 r = solv->rules + rid;
3883 *depp = r->p < 0 ? pool->solvables[-r->p].name : 0;
3884 *sourcep = r->p < 0 ? -r->p : 0;
3886 return SOLVER_PROBLEM_INFARCH_RULE;
3888 if (rid >= solv->duprules && rid < solv->duprules_end)
3890 r = solv->rules + rid;
3891 *depp = r->p < 0 ? pool->solvables[-r->p].name : 0;
3892 *sourcep = r->p < 0 ? -r->p : 0;
3894 return SOLVER_PROBLEM_DISTUPGRADE_RULE;
3896 if (rid >= solv->jobrules && rid < solv->jobrules_end)
3899 r = solv->rules + rid;
3900 p = solv->ruletojob.elements[rid - solv->jobrules];
3901 *depp = job->elements[p + 1];
3903 *targetp = job->elements[p];
3904 d = r->d < 0 ? -r->d - 1 : r->d;
3905 if (d == 0 && r->w2 == 0 && r->p == -SYSTEMSOLVABLE && (job->elements[p] & SOLVER_SELECTMASK) != SOLVER_SOLVABLE_ONE_OF)
3906 return SOLVER_PROBLEM_JOB_NOTHING_PROVIDES_DEP;
3907 return SOLVER_PROBLEM_JOB_RULE;
3909 if (rid >= solv->updaterules && rid < solv->updaterules_end)
3912 *sourcep = solv->installed->start + (rid - solv->updaterules);
3914 return SOLVER_PROBLEM_UPDATE_RULE;
3916 assert(rid < solv->rpmrules_end);
3917 r = solv->rules + rid;
3919 d = r->d < 0 ? -r->d - 1 : r->d;
3920 if (d == 0 && r->w2 == 0)
3922 /* a rpm rule assertion */
3923 s = pool->solvables - r->p;
3924 if (installed && !solv->fixsystem && s->repo == installed)
3926 assert(!dontfix); /* dontfix packages never have a neg assertion */
3929 /* see why the package is not installable */
3930 if (s->arch != ARCH_SRC && s->arch != ARCH_NOSRC && !pool_installable(pool, s))
3933 return SOLVER_PROBLEM_NOT_INSTALLABLE;
3935 /* check requires */
3938 reqp = s->repo->idarraydata + s->requires;
3939 while ((req = *reqp++) != 0)
3941 if (req == SOLVABLE_PREREQMARKER)
3943 dp = pool_whatprovides_ptr(pool, req);
3950 return SOLVER_PROBLEM_NOTHING_PROVIDES_DEP;
3953 if (!solv->allowselfconflicts && s->conflicts)
3955 conp = s->repo->idarraydata + s->conflicts;
3956 while ((con = *conp++) != 0)
3957 FOR_PROVIDES(p, pp, con)
3961 return SOLVER_PROBLEM_SELF_CONFLICT;
3964 /* should never happen */
3966 return SOLVER_PROBLEM_RPM_RULE;
3968 s = pool->solvables - r->p;
3969 if (installed && !solv->fixsystem && s->repo == installed)
3972 if (d && pool->whatprovidesdata[d] < 0)
3974 /* rule looks like -p|-c|x|x|x..., we only create this for patches with multiversion */
3975 /* reduce it to -p|-c case */
3977 w2 = pool->whatprovidesdata[d];
3979 if (d == 0 && w2 < 0)
3981 /* a package conflict */
3982 Solvable *s2 = pool->solvables - w2;
3985 if (installed && !solv->fixsystem && s2->repo == installed)
3988 /* if both packages have the same name and at least one of them
3989 * is not installed, they conflict */
3990 if (s->name == s2->name && !(installed && s->repo == installed && s2->repo == installed))
3992 /* also check noobsoletes map */
3993 if ((s->evr == s2->evr && s->arch == s2->arch) || !solv->noobsoletes.size
3994 || ((!installed || s->repo != installed) && !MAPTST(&solv->noobsoletes, -r->p))
3995 || ((!installed || s2->repo != installed) && !MAPTST(&solv->noobsoletes, -w2)))
4000 return SOLVER_PROBLEM_SAME_NAME;
4004 /* check conflicts in both directions */
4007 conp = s->repo->idarraydata + s->conflicts;
4008 while ((con = *conp++) != 0)
4010 FOR_PROVIDES(p, pp, con)
4012 if (dontfix && pool->solvables[p].repo == installed)
4019 return SOLVER_PROBLEM_PACKAGE_CONFLICT;
4025 conp = s2->repo->idarraydata + s2->conflicts;
4026 while ((con = *conp++) != 0)
4028 FOR_PROVIDES(p, pp, con)
4030 if (dontfix2 && pool->solvables[p].repo == installed)
4037 return SOLVER_PROBLEM_PACKAGE_CONFLICT;
4041 /* check obsoletes in both directions */
4042 if ((!installed || s->repo != installed) && s->obsoletes && !(solv->noobsoletes.size && MAPTST(&solv->noobsoletes, -r->p)))
4044 obsp = s->repo->idarraydata + s->obsoletes;
4045 while ((obs = *obsp++) != 0)
4047 FOR_PROVIDES(p, pp, obs)
4051 if (!solv->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p, obs))
4056 return SOLVER_PROBLEM_PACKAGE_OBSOLETES;
4060 if ((!installed || s2->repo != installed) && s2->obsoletes && !(solv->noobsoletes.size && MAPTST(&solv->noobsoletes, -w2)))
4062 obsp = s2->repo->idarraydata + s2->obsoletes;
4063 while ((obs = *obsp++) != 0)
4065 FOR_PROVIDES(p, pp, obs)
4069 if (!solv->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p, obs))
4074 return SOLVER_PROBLEM_PACKAGE_OBSOLETES;
4078 if (solv->implicitobsoleteusesprovides && (!installed || s->repo != installed) && !(solv->noobsoletes.size && MAPTST(&solv->noobsoletes, -r->p)))
4080 FOR_PROVIDES(p, pp, s->name)
4087 return SOLVER_PROBLEM_PACKAGE_OBSOLETES;
4090 if (solv->implicitobsoleteusesprovides && (!installed || s2->repo != installed) && !(solv->noobsoletes.size && MAPTST(&solv->noobsoletes, -w2)))
4092 FOR_PROVIDES(p, pp, s2->name)
4099 return SOLVER_PROBLEM_PACKAGE_OBSOLETES;
4102 /* all cases checked, can't happen */
4106 return SOLVER_PROBLEM_RPM_RULE;
4108 /* simple requires */
4111 reqp = s->repo->idarraydata + s->requires;
4112 while ((req = *reqp++) != 0)
4114 if (req == SOLVABLE_PREREQMARKER)
4116 dp = pool_whatprovides_ptr(pool, req);
4119 if (*dp == r->w2 && dp[1] == 0)
4122 else if (dp - pool->whatprovidesdata == d)
4130 return SOLVER_PROBLEM_DEP_PROVIDERS_NOT_INSTALLABLE;
4134 /* check for product buddy requires */
4135 if (d == 0 && w2 > 0 && pool->nscallback)
4138 s = pool->solvables - r->p;
4139 if (!strncmp("product:", id2str(pool, s->name), 8))
4141 buddy = pool->nscallback(pool, pool->nscallbackdata, NAMESPACE_PRODUCTBUDDY, -r->p);
4147 s = pool->solvables + w2;
4148 if (!strncmp("product:", id2str(pool, s->name), 8))
4150 buddy = pool->nscallback(pool, pool->nscallbackdata, NAMESPACE_PRODUCTBUDDY, w2);
4157 /* have buddy relation, now fake requires */
4158 s = pool->solvables + w2;
4160 if (s->repo && s->provides)
4163 provp = s->repo->idarraydata + s->provides;
4164 while ((prov = *provp++) != 0)
4166 if (!ISRELDEP(prov))
4168 rd = GETRELDEP(pool, prov);
4169 if (rd->name == s->name && rd->evr == s->evr && rd->flags == REL_EQ)
4174 return SOLVER_PROBLEM_DEP_PROVIDERS_NOT_INSTALLABLE;
4181 return SOLVER_PROBLEM_DEP_PROVIDERS_NOT_INSTALLABLE;
4185 /* all cases checked, can't happen */
4189 return SOLVER_PROBLEM_RPM_RULE;
4193 /*-------------------------------------------------------------------
4199 findproblemrule_internal(Solver *solv, Id idx, Id *reqrp, Id *conrp, Id *sysrp, Id *jobrp)
4202 Id lreqr, lconr, lsysr, ljobr;
4206 lreqr = lconr = lsysr = ljobr = 0;
4207 while ((rid = solv->learnt_pool.elements[idx++]) != 0)
4210 if (rid >= solv->learntrules)
4211 findproblemrule_internal(solv, solv->learnt_why.elements[rid - solv->learntrules], &lreqr, &lconr, &lsysr, &ljobr);
4212 else if ((rid >= solv->jobrules && rid < solv->jobrules_end) || (rid >= solv->infarchrules && rid < solv->infarchrules_end) || (rid >= solv->duprules && rid < solv->duprules_end))
4217 else if (rid >= solv->updaterules && rid < solv->updaterules_end)
4224 assert(rid < solv->rpmrules_end);
4225 r = solv->rules + rid;
4226 d = r->d < 0 ? -r->d - 1 : r->d;
4227 if (!d && r->w2 < 0)
4234 if (!d && r->w2 == 0 && !reqassert)
4236 if (*reqrp > 0 && r->p < -1)
4238 Id op = -solv->rules[*reqrp].p;
4239 if (op > 1 && solv->pool->solvables[op].arch != solv->pool->solvables[-r->p].arch)
4240 continue; /* different arch, skip */
4242 /* prefer assertions */
4248 else if (solv->installed && r->p < 0 && solv->pool->solvables[-r->p].repo == solv->installed && !reqassert)
4250 /* prefer rules of installed packages */
4256 if (!*reqrp && lreqr)
4258 if (!*conrp && lconr)
4260 if (!*jobrp && ljobr)
4262 if (!*sysrp && lsysr)
4267 /*-------------------------------------------------------------------
4271 * search for a rule that describes the problem to the
4272 * user. A pretty hopeless task, actually. We currently
4273 * prefer simple requires.
4277 solver_findproblemrule(Solver *solv, Id problem)
4279 Id reqr, conr, sysr, jobr;
4280 Id idx = solv->problems.elements[problem - 1];
4281 reqr = conr = sysr = jobr = 0;
4282 findproblemrule_internal(solv, idx, &reqr, &conr, &sysr, &jobr);
4295 findallproblemrules_internal(Solver *solv, Id idx, Queue *rules)
4298 while ((rid = solv->learnt_pool.elements[idx++]) != 0)
4300 if (rid >= solv->learntrules)
4302 findallproblemrules_internal(solv, solv->learnt_why.elements[rid - solv->learntrules], rules);
4305 queue_pushunique(rules, rid);
4310 solver_findallproblemrules(Solver *solv, Id problem, Queue *rules)
4313 findallproblemrules_internal(solv, solv->problems.elements[problem - 1], rules);
4317 /*-------------------------------------------------------------------
4319 * create reverse obsoletes map for installed solvables
4321 * for each installed solvable find which packages with *different* names
4322 * obsolete the solvable.
4323 * this index is used in policy_findupdatepackages if noupdateprovide is set.
4327 create_obsolete_index(Solver *solv)
4329 Pool *pool = solv->pool;
4331 Repo *installed = solv->installed;
4332 Id p, pp, obs, *obsp, *obsoletes, *obsoletes_data;
4335 if (!installed || !installed->nsolvables)
4337 solv->obsoletes = obsoletes = sat_calloc(installed->end - installed->start, sizeof(Id));
4338 for (i = 1; i < pool->nsolvables; i++)
4340 s = pool->solvables + i;
4343 if (!pool_installable(pool, s))
4345 obsp = s->repo->idarraydata + s->obsoletes;
4346 while ((obs = *obsp++) != 0)
4348 FOR_PROVIDES(p, pp, obs)
4350 if (pool->solvables[p].repo != installed)
4352 if (pool->solvables[p].name == s->name)
4354 if (!solv->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p, obs))
4356 obsoletes[p - installed->start]++;
4361 for (i = 0; i < installed->nsolvables; i++)
4364 n += obsoletes[i] + 1;
4367 solv->obsoletes_data = obsoletes_data = sat_calloc(n + 1, sizeof(Id));
4368 POOL_DEBUG(SAT_DEBUG_STATS, "obsoletes data: %d entries\n", n + 1);
4369 for (i = pool->nsolvables - 1; i > 0; i--)
4371 s = pool->solvables + i;
4374 if (!pool_installable(pool, s))
4376 obsp = s->repo->idarraydata + s->obsoletes;
4377 while ((obs = *obsp++) != 0)
4379 FOR_PROVIDES(p, pp, obs)
4381 if (pool->solvables[p].repo != installed)
4383 if (pool->solvables[p].name == s->name)
4385 if (!solv->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p, obs))
4387 p -= installed->start;
4388 if (obsoletes_data[obsoletes[p]] != i)
4389 obsoletes_data[--obsoletes[p]] = i;
4396 /*-------------------------------------------------------------------
4398 * remove disabled conflicts
4402 removedisabledconflicts(Solver *solv, Queue *removed)
4404 Pool *pool = solv->pool;
4409 Id *decisionmap = solv->decisionmap;
4411 POOL_DEBUG(SAT_DEBUG_SCHUBI, "removedisabledconflicts\n");
4412 queue_empty(removed);
4413 for (i = 0; i < solv->decisionq.count; i++)
4415 p = solv->decisionq.elements[i];
4418 /* a conflict. we never do conflicts on free decisions, so there
4419 * must have been an unit rule */
4420 why = solv->decisionq_why.elements[i];
4422 r = solv->rules + why;
4423 if (r->d < 0 && decisionmap[-p])
4425 /* rule is now disabled, remove from decisionmap */
4426 POOL_DEBUG(SAT_DEBUG_SCHUBI, "removing conflict for package %s[%d]\n", solvable2str(pool, pool->solvables - p), -p);
4427 queue_push(removed, -p);
4428 queue_push(removed, decisionmap[-p]);
4429 decisionmap[-p] = 0;
4432 if (!removed->count)
4434 /* we removed some confliced packages. some of them might still
4435 * be in conflict, so search for unit rules and re-conflict */
4437 for (i = n = 1, r = solv->rules + i; n < solv->nrules; i++, r++, n++)
4439 if (i == solv->nrules)
4442 r = solv->rules + i;
4448 if (r->p < 0 && !decisionmap[-r->p])
4454 if (r->p < 0 && decisionmap[-r->p] == 0 && DECISIONMAP_FALSE(r->w2))
4456 else if (r->w2 < 0 && decisionmap[-r->w2] == 0 && DECISIONMAP_FALSE(r->p))
4461 if (r->p < 0 && decisionmap[-r->p] == 0)
4463 if (new || DECISIONMAP_FALSE(r->p))
4465 dp = pool->whatprovidesdata + r->d;
4466 while ((p = *dp++) != 0)
4468 if (new && p == new)
4470 if (p < 0 && decisionmap[-p] == 0)
4479 else if (!DECISIONMAP_FALSE(p))
4489 POOL_DEBUG(SAT_DEBUG_SCHUBI, "re-conflicting package %s[%d]\n", solvable2str(pool, pool->solvables - new), -new);
4490 decisionmap[-new] = -1;
4492 n = 0; /* redo all rules */
4498 /*-------------------------------------------------------------------
4500 * weaken solvable dependencies
4504 weaken_solvable_deps(Solver *solv, Id p)
4509 for (i = 1, r = solv->rules + i; i < solv->rpmrules_end; i++, r++)
4513 if ((r->d == 0 || r->d == -1) && r->w2 < 0)
4514 continue; /* conflict */
4515 queue_push(&solv->weakruleq, i);
4519 /********************************************************************/
4524 addinfarchrules(Solver *solv, Map *addedmap)
4526 Pool *pool = solv->pool;
4528 Id p, pp, a, aa, bestarch;
4529 Solvable *s, *ps, *bests;
4530 Queue badq, allowedarchs;
4533 queue_init(&allowedarchs);
4534 solv->infarchrules = solv->nrules;
4535 for (i = 1; i < pool->nsolvables; i++)
4537 if (i == SYSTEMSOLVABLE || !MAPTST(addedmap, i))
4539 s = pool->solvables + i;
4543 queue_empty(&allowedarchs);
4544 FOR_PROVIDES(p, pp, s->name)
4546 ps = pool->solvables + p;
4547 if (ps->name != s->name || !MAPTST(addedmap, p))
4554 a = (a <= pool->lastarch) ? pool->id2arch[a] : 0;
4555 if (a != 1 && pool->installed && ps->repo == pool->installed && !solv->distupgrade)
4557 queue_pushunique(&allowedarchs, ps->arch); /* also ok to keep this architecture */
4558 continue; /* ignore installed solvables when calculating the best arch */
4560 if (a && a != 1 && (!bestarch || a < bestarch))
4568 /* speed up common case where installed package already has best arch */
4569 if (allowedarchs.count == 1 && bests && allowedarchs.elements[0] == bests->arch)
4570 allowedarchs.count--; /* installed arch is best */
4572 FOR_PROVIDES(p, pp, s->name)
4574 ps = pool->solvables + p;
4575 if (ps->name != s->name || !MAPTST(addedmap, p))
4578 a = (a <= pool->lastarch) ? pool->id2arch[a] : 0;
4579 if (a != 1 && bestarch && ((a ^ bestarch) & 0xffff0000) != 0)
4581 for (j = 0; j < allowedarchs.count; j++)
4583 aa = allowedarchs.elements[j];
4586 aa = (aa <= pool->lastarch) ? pool->id2arch[aa] : 0;
4587 if (aa && ((a ^ aa) & 0xffff0000) == 0)
4588 break; /* compatible */
4590 if (j == allowedarchs.count)
4591 queue_push(&badq, p);
4596 /* block all solvables in the badq! */
4597 for (j = 0; j < badq.count; j++)
4599 p = badq.elements[j];
4600 addrule(solv, -p, 0);
4604 queue_free(&allowedarchs);
4605 solv->infarchrules_end = solv->nrules;
4609 createdupmaps(Solver *solv, Queue *job)
4611 Pool *pool = solv->pool;
4613 Id how, what, p, pi, pp, obs, *obsp;
4617 map_init(&solv->dupmap, pool->nsolvables);
4618 map_init(&solv->dupinvolvedmap, pool->nsolvables);
4619 for (i = 0; i < job->count; i += 2)
4621 how = job->elements[i];
4622 what = job->elements[i + 1];
4623 switch (how & SOLVER_JOBMASK)
4625 case SOLVER_DISTUPGRADE:
4626 if (what < 0 || what > pool->nrepos)
4628 repo = pool->repos[what];
4629 FOR_REPO_SOLVABLES(repo, p, s)
4631 MAPSET(&solv->dupmap, p);
4632 FOR_PROVIDES(pi, pp, s->name)
4634 ps = pool->solvables + pi;
4635 if (ps->name != s->name)
4637 MAPSET(&solv->dupinvolvedmap, pi);
4641 /* FIXME: check obsoletes/provides combination */
4642 obsp = s->repo->idarraydata + s->obsoletes;
4643 while ((obs = *obsp++) != 0)
4645 FOR_PROVIDES(pi, pp, obs)
4647 if (!solv->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + pi, obs))
4649 MAPSET(&solv->dupinvolvedmap, pi);
4659 MAPCLR(&solv->dupinvolvedmap, SYSTEMSOLVABLE);
4663 freedupmaps(Solver *solv)
4665 map_free(&solv->dupmap);
4666 map_free(&solv->dupinvolvedmap);
4670 addduprules(Solver *solv, Map *addedmap)
4672 Pool *pool = solv->pool;
4677 solv->duprules = solv->nrules;
4678 for (i = 1; i < pool->nsolvables; i++)
4680 if (i == SYSTEMSOLVABLE || !MAPTST(addedmap, i))
4682 s = pool->solvables + i;
4684 FOR_PROVIDES(p, pp, s->name)
4686 ps = pool->solvables + p;
4687 if (ps->name != s->name || !MAPTST(addedmap, p))
4693 if (!MAPTST(&solv->dupinvolvedmap, p))
4695 if (solv->installed && ps->repo == solv->installed)
4697 if (!solv->updatemap.size)
4698 map_init(&solv->updatemap, pool->nsolvables);
4699 MAPSET(&solv->updatemap, p);
4700 if (!MAPTST(&solv->dupmap, p))
4703 /* is installed identical to a good one? */
4704 FOR_PROVIDES(ip, ipp, s->name)
4706 Solvable *is = pool->solvables + ip;
4707 if (!MAPTST(&solv->dupmap, ip))
4709 if (is->evr == s->evr && solvable_identical(s, is))
4713 addrule(solv, -p, 0); /* no match, sorry */
4716 else if (!MAPTST(&solv->dupmap, p))
4717 addrule(solv, -p, 0);
4720 solv->duprules_end = solv->nrules;
4730 solver_solve(Solver *solv, Queue *job)
4732 Pool *pool = solv->pool;
4733 Repo *installed = solv->installed;
4736 Map addedmap; /* '1' == have rpm-rules for solvable */
4737 Map installcandidatemap;
4738 Id how, what, select, name, weak, p, pp, d;
4743 int now, solve_start;
4746 solve_start = sat_timems(0);
4747 POOL_DEBUG(SAT_DEBUG_STATS, "solver started\n");
4748 POOL_DEBUG(SAT_DEBUG_STATS, "fixsystem=%d updatesystem=%d dosplitprovides=%d, noupdateprovide=%d\n", solv->fixsystem, solv->updatesystem, solv->dosplitprovides, solv->noupdateprovide);
4749 POOL_DEBUG(SAT_DEBUG_STATS, "distupgrade=%d distupgrade_removeunsupported=%d\n", solv->distupgrade, solv->distupgrade_removeunsupported);
4750 POOL_DEBUG(SAT_DEBUG_STATS, "allowuninstall=%d, allowdowngrade=%d, allowarchchange=%d, allowvendorchange=%d\n", solv->allowuninstall, solv->allowdowngrade, solv->allowarchchange, solv->allowvendorchange);
4751 POOL_DEBUG(SAT_DEBUG_STATS, "promoteepoch=%d, allowvirtualconflicts=%d, allowselfconflicts=%d\n", pool->promoteepoch, solv->allowvirtualconflicts, solv->allowselfconflicts);
4752 POOL_DEBUG(SAT_DEBUG_STATS, "obsoleteusesprovides=%d, implicitobsoleteusesprovides=%d\n", solv->obsoleteusesprovides, solv->implicitobsoleteusesprovides);
4753 POOL_DEBUG(SAT_DEBUG_STATS, "dontinstallrecommended=%d, ignorealreadyrecommended=%d, dontshowinstalledrecommended=%d\n", solv->dontinstallrecommended, solv->ignorealreadyrecommended, solv->dontshowinstalledrecommended);
4754 /* create whatprovides if not already there */
4755 if (!pool->whatprovides)
4756 pool_createwhatprovides(pool);
4758 /* create obsolete index */
4759 create_obsolete_index(solv);
4765 * create basic rule set of all involved packages
4766 * use addedmap bitmap to make sure we don't create rules twice
4770 /* create noobsolete map if needed */
4771 for (i = 0; i < job->count; i += 2)
4773 how = job->elements[i] & ~SOLVER_WEAK;
4774 if ((how & SOLVER_JOBMASK) != SOLVER_NOOBSOLETES)
4776 what = job->elements[i + 1];
4777 select = how & SOLVER_SELECTMASK;
4778 if (!solv->noobsoletes.size)
4779 map_init(&solv->noobsoletes, pool->nsolvables);
4780 FOR_JOB_SELECT(p, pp, select, what)
4781 MAPSET(&solv->noobsoletes, p);
4784 map_init(&addedmap, pool->nsolvables);
4785 map_init(&installcandidatemap, pool->nsolvables);
4789 * always install our system solvable
4791 MAPSET(&addedmap, SYSTEMSOLVABLE);
4792 queue_push(&solv->decisionq, SYSTEMSOLVABLE);
4793 queue_push(&solv->decisionq_why, 0);
4794 solv->decisionmap[SYSTEMSOLVABLE] = 1; /* installed at level '1' */
4796 now = sat_timems(0);
4798 * create rules for all package that could be involved with the solving
4799 * so called: rpm rules
4804 oldnrules = solv->nrules;
4805 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for installed solvables ***\n");
4806 FOR_REPO_SOLVABLES(installed, p, s)
4807 addrpmrulesforsolvable(solv, s, &addedmap);
4808 POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for installed solvables\n", solv->nrules - oldnrules);
4809 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for updaters of installed solvables ***\n");
4810 oldnrules = solv->nrules;
4811 FOR_REPO_SOLVABLES(installed, p, s)
4812 addrpmrulesforupdaters(solv, s, &addedmap, 1);
4813 POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for updaters of installed solvables\n", solv->nrules - oldnrules);
4817 * create rules for all packages involved in the job
4818 * (to be installed or removed)
4821 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for packages involved with a job ***\n");
4822 oldnrules = solv->nrules;
4823 for (i = 0; i < job->count; i += 2)
4825 how = job->elements[i];
4826 what = job->elements[i + 1];
4827 select = how & SOLVER_SELECTMASK;
4829 switch (how & SOLVER_JOBMASK)
4831 case SOLVER_INSTALL:
4832 FOR_JOB_SELECT(p, pp, select, what)
4834 MAPSET(&installcandidatemap, p);
4835 addrpmrulesforsolvable(solv, pool->solvables + p, &addedmap);
4838 case SOLVER_DISTUPGRADE:
4839 if (!solv->distupgrade)
4846 POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for packages involved in a job\n", solv->nrules - oldnrules);
4848 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for recommended/suggested packages ***\n");
4850 oldnrules = solv->nrules;
4853 * add rules for suggests, enhances
4855 addrpmrulesforweak(solv, &addedmap);
4856 POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules because of weak dependencies\n", solv->nrules - oldnrules);
4858 IF_POOLDEBUG (SAT_DEBUG_STATS)
4860 int possible = 0, installable = 0;
4861 for (i = 1; i < pool->nsolvables; i++)
4863 if (pool_installable(pool, pool->solvables + i))
4865 if (MAPTST(&addedmap, i))
4868 POOL_DEBUG(SAT_DEBUG_STATS, "%d of %d installable solvables considered for solving\n", possible, installable);
4872 * first pass done, we now have all the rpm rules we need.
4873 * unify existing rules before going over all job rules and
4875 * at this point the system is always solvable,
4876 * as an empty system (remove all packages) is a valid solution
4879 unifyrules(solv); /* remove duplicate rpm rules */
4881 solv->rpmrules_end = solv->nrules; /* mark end of rpm rules */
4883 solv->directdecisions = solv->decisionq.count;
4884 POOL_DEBUG(SAT_DEBUG_STATS, "rpm rule memory usage: %d K\n", solv->nrules * (int)sizeof(Rule) / 1024);
4885 POOL_DEBUG(SAT_DEBUG_STATS, "decisions so far: %d\n", solv->decisionq.count);
4886 POOL_DEBUG(SAT_DEBUG_STATS, "rpm rule creation took %d ms\n", sat_timems(now));
4888 /* create dup maps if needed. We need the maps to create our
4891 createdupmaps(solv, job);
4894 * create feature rules
4896 * foreach installed:
4897 * create assertion (keep installed, if no update available)
4899 * create update rule (A|update1(A)|update2(A)|...)
4901 * those are used later on to keep a version of the installed packages in
4905 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** Add feature rules ***\n");
4906 solv->featurerules = solv->nrules; /* mark start of feature rules */
4909 /* foreach possibly installed solvable */
4910 for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
4912 if (s->repo != installed)
4914 addrule(solv, 0, 0); /* create dummy rule */
4917 addupdaterule(solv, s, 1); /* allow s to be updated */
4920 * assert one rule per installed solvable,
4921 * either an assertion (A)
4922 * or a possible update (A|update1(A)|update2(A)|...)
4924 assert(solv->nrules - solv->featurerules == installed->end - installed->start);
4926 solv->featurerules_end = solv->nrules;
4929 * Add update rules for installed solvables
4931 * almost identical to feature rules
4932 * except that downgrades/archchanges/vendorchanges are not allowed
4935 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** Add update rules ***\n");
4936 solv->updaterules = solv->nrules;
4939 { /* foreach installed solvables */
4940 /* we create all update rules, but disable some later on depending on the job */
4941 for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
4945 if (s->repo != installed)
4947 addrule(solv, 0, 0); /* create dummy rule */
4950 addupdaterule(solv, s, 0); /* allowall = 0: downgrades not allowed */
4952 * check for and remove duplicate
4954 r = solv->rules + solv->nrules - 1; /* r: update rule */
4955 sr = r - (installed->end - installed->start); /* sr: feature rule */
4956 /* it's orphaned if there is no feature rule or the feature rule
4957 * consists just of the installed package */
4958 if (!sr->p || (sr->p == i && !sr->d && !sr->w2))
4959 queue_push(&solv->orphaned, i);
4962 assert(solv->distupgrade && !sr->p);
4965 unifyrules_sortcmp_data = pool;
4966 if (!unifyrules_sortcmp(r, sr))
4968 /* identical rule, kill unneeded one */
4969 if (solv->allowuninstall)
4971 /* keep feature rule, make it weak */
4972 memset(r, 0, sizeof(*r));
4973 queue_push(&solv->weakruleq, sr - solv->rules);
4977 /* keep update rule */
4978 memset(sr, 0, sizeof(*sr));
4981 else if (solv->allowuninstall)
4983 /* make both feature and update rule weak */
4984 queue_push(&solv->weakruleq, r - solv->rules);
4985 queue_push(&solv->weakruleq, sr - solv->rules);
4988 disablerule(solv, sr);
4990 /* consistency check: we added a rule for _every_ installed solvable */
4991 assert(solv->nrules - solv->updaterules == installed->end - installed->start);
4993 solv->updaterules_end = solv->nrules;
4997 * now add all job rules
5000 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** Add JOB rules ***\n");
5002 solv->jobrules = solv->nrules;
5003 for (i = 0; i < job->count; i += 2)
5005 oldnrules = solv->nrules;
5007 how = job->elements[i];
5008 what = job->elements[i + 1];
5009 weak = how & SOLVER_WEAK;
5010 select = how & SOLVER_SELECTMASK;
5011 switch (how & SOLVER_JOBMASK)
5013 case SOLVER_INSTALL:
5014 POOL_DEBUG(SAT_DEBUG_JOB, "job: %sinstall %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
5015 if (select == SOLVER_SOLVABLE)
5023 FOR_JOB_SELECT(p, pp, select, what)
5027 /* no candidate found, make this an impossible rule */
5028 queue_push(&q, -SYSTEMSOLVABLE);
5030 p = queue_shift(&q); /* get first candidate */
5031 d = !q.count ? 0 : pool_queuetowhatprovides(pool, &q); /* internalize */
5033 addrule(solv, p, d); /* add install rule */
5034 queue_push(&solv->ruletojob, i);
5036 queue_push(&solv->weakruleq, solv->nrules - 1);
5039 POOL_DEBUG(SAT_DEBUG_JOB, "job: %serase %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
5040 if (select == SOLVER_SOLVABLE && solv->installed && pool->solvables[what].repo == solv->installed)
5042 /* special case for "erase a specific solvable": we also
5043 * erase all other solvables with that name, so that they
5044 * don't get picked up as replacement */
5045 name = pool->solvables[what].name;
5046 FOR_PROVIDES(p, pp, name)
5050 s = pool->solvables + p;
5051 if (s->name != name)
5053 /* keep other versions installed */
5054 if (s->repo == solv->installed)
5056 /* keep installcandidates of other jobs */
5057 if (MAPTST(&installcandidatemap, p))
5059 addrule(solv, -p, 0); /* remove by Id */
5060 queue_push(&solv->ruletojob, i);
5062 queue_push(&solv->weakruleq, solv->nrules - 1);
5065 FOR_JOB_SELECT(p, pp, select, what)
5067 addrule(solv, -p, 0);
5068 queue_push(&solv->ruletojob, i);
5070 queue_push(&solv->weakruleq, solv->nrules - 1);
5075 POOL_DEBUG(SAT_DEBUG_JOB, "job: %supdate %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
5076 FOR_JOB_SELECT(p, pp, select, what)
5078 s = pool->solvables + p;
5079 if (!solv->installed || s->repo != solv->installed)
5081 if (!solv->updatemap.size)
5082 map_init(&solv->updatemap, pool->nsolvables);
5083 MAPSET(&solv->updatemap, p);
5086 case SOLVER_WEAKENDEPS:
5087 POOL_DEBUG(SAT_DEBUG_JOB, "job: %sweaken deps %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
5088 if (select != SOLVER_SOLVABLE)
5090 s = pool->solvables + what;
5091 weaken_solvable_deps(solv, what);
5093 case SOLVER_NOOBSOLETES:
5094 POOL_DEBUG(SAT_DEBUG_JOB, "job: %sno obsolete %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
5097 POOL_DEBUG(SAT_DEBUG_JOB, "job: %slock %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
5098 FOR_JOB_SELECT(p, pp, select, what)
5100 s = pool->solvables + p;
5101 if (installed && s->repo == installed)
5102 addrule(solv, p, 0);
5104 addrule(solv, -p, 0);
5105 queue_push(&solv->ruletojob, i);
5107 queue_push(&solv->weakruleq, solv->nrules - 1);
5110 case SOLVER_DISTUPGRADE:
5111 POOL_DEBUG(SAT_DEBUG_JOB, "job: distupgrade repo #%d\n", what);
5114 POOL_DEBUG(SAT_DEBUG_JOB, "job: unknown job\n");
5122 IF_POOLDEBUG (SAT_DEBUG_JOB)
5125 if (solv->nrules == oldnrules)
5126 POOL_DEBUG(SAT_DEBUG_JOB, " - no rule created\n");
5127 for (j = oldnrules; j < solv->nrules; j++)
5129 POOL_DEBUG(SAT_DEBUG_JOB, " - job ");
5130 solver_printrule(solv, SAT_DEBUG_JOB, solv->rules + j);
5134 assert(solv->ruletojob.count == solv->nrules - solv->jobrules);
5135 solv->jobrules_end = solv->nrules;
5137 /* now create infarch and dup rules */
5138 addinfarchrules(solv, &addedmap);
5141 addduprules(solv, &addedmap);
5142 freedupmaps(solv); /* no longer needed */
5145 solv->duprules = solv->duprules_end = solv->nrules;
5147 /* all rules created
5148 * --------------------------------------------------------------
5149 * prepare for solving
5152 /* free unneeded memory */
5153 map_free(&addedmap);
5154 map_free(&installcandidatemap);
5157 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);
5159 /* create weak map */
5160 map_init(&solv->weakrulemap, solv->nrules);
5161 for (i = 0; i < solv->weakruleq.count; i++)
5163 p = solv->weakruleq.elements[i];
5164 MAPSET(&solv->weakrulemap, p);
5167 /* all new rules are learnt after this point */
5168 solv->learntrules = solv->nrules;
5170 /* create assertion index. it is only used to speed up
5171 * makeruledecsions() a bit */
5172 for (i = 1, r = solv->rules + i; i < solv->nrules; i++, r++)
5173 if (r->p && !r->w2 && (r->d == 0 || r->d == -1))
5174 queue_push(&solv->ruleassertions, i);
5176 /* disable update rules that conflict with our job */
5177 disablepolicyrules(solv, job);
5179 /* make decisions based on job/update assertions */
5180 makeruledecisions(solv);
5182 /* create watches chains */
5185 POOL_DEBUG(SAT_DEBUG_STATS, "problems so far: %d\n", solv->problems.count);
5188 * ********************************************
5190 * ********************************************
5193 now = sat_timems(0);
5194 run_solver(solv, 1, solv->dontinstallrecommended ? 0 : 1);
5195 POOL_DEBUG(SAT_DEBUG_STATS, "solver took %d ms\n", sat_timems(now));
5199 /* disable all erase jobs (including weak "keep uninstalled" rules) */
5200 for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++)
5202 if (r->d < 0) /* disabled ? */
5204 if (r->p > 0) /* install job? */
5206 disablerule(solv, r);
5212 enabledisablelearntrules(solv);
5213 removedisabledconflicts(solv, &redoq);
5217 * find recommended packages
5220 /* if redoq.count == 0 we already found all recommended in the
5222 if (redoq.count || solv->dontinstallrecommended || !solv->dontshowinstalledrecommended || solv->ignorealreadyrecommended)
5224 Id rec, *recp, p, pp;
5226 /* create map of all recommened packages */
5227 solv->recommends_index = -1;
5228 MAPZERO(&solv->recommendsmap);
5229 for (i = 0; i < solv->decisionq.count; i++)
5231 p = solv->decisionq.elements[i];
5234 s = pool->solvables + p;
5237 recp = s->repo->idarraydata + s->recommends;
5238 while ((rec = *recp++) != 0)
5240 FOR_PROVIDES(p, pp, rec)
5241 if (solv->decisionmap[p] > 0)
5245 if (!solv->dontshowinstalledrecommended)
5247 FOR_PROVIDES(p, pp, rec)
5248 if (solv->decisionmap[p] > 0)
5249 MAPSET(&solv->recommendsmap, p);
5251 continue; /* p != 0: already fulfilled */
5253 FOR_PROVIDES(p, pp, rec)
5254 MAPSET(&solv->recommendsmap, p);
5258 for (i = 1; i < pool->nsolvables; i++)
5260 if (solv->decisionmap[i] < 0)
5262 if (solv->decisionmap[i] > 0 && solv->dontshowinstalledrecommended)
5264 s = pool->solvables + i;
5265 if (!MAPTST(&solv->recommendsmap, i))
5267 if (!s->supplements)
5269 if (!pool_installable(pool, s))
5271 if (!solver_is_supplementing(solv, s))
5274 if (solv->dontinstallrecommended)
5275 queue_push(&solv->recommendations, i);
5277 queue_pushunique(&solv->recommendations, i);
5279 /* we use MODE_SUGGEST here so that repo prio is ignored */
5280 policy_filter_unwanted(solv, &solv->recommendations, POLICY_MODE_SUGGEST);
5284 * find suggested packages
5289 Id sug, *sugp, p, pp;
5291 /* create map of all suggests that are still open */
5292 solv->recommends_index = -1;
5293 MAPZERO(&solv->suggestsmap);
5294 for (i = 0; i < solv->decisionq.count; i++)
5296 p = solv->decisionq.elements[i];
5299 s = pool->solvables + p;
5302 sugp = s->repo->idarraydata + s->suggests;
5303 while ((sug = *sugp++) != 0)
5305 FOR_PROVIDES(p, pp, sug)
5306 if (solv->decisionmap[p] > 0)
5310 if (!solv->dontshowinstalledrecommended)
5312 FOR_PROVIDES(p, pp, sug)
5313 if (solv->decisionmap[p] > 0)
5314 MAPSET(&solv->suggestsmap, p);
5316 continue; /* already fulfilled */
5318 FOR_PROVIDES(p, pp, sug)
5319 MAPSET(&solv->suggestsmap, p);
5323 for (i = 1; i < pool->nsolvables; i++)
5325 if (solv->decisionmap[i] < 0)
5327 if (solv->decisionmap[i] > 0 && solv->dontshowinstalledrecommended)
5329 s = pool->solvables + i;
5330 if (!MAPTST(&solv->suggestsmap, i))
5334 if (!pool_installable(pool, s))
5336 if (!solver_is_enhancing(solv, s))
5339 queue_push(&solv->suggestions, i);
5341 policy_filter_unwanted(solv, &solv->suggestions, POLICY_MODE_SUGGEST);
5346 /* restore decisionmap */
5347 for (i = 0; i < redoq.count; i += 2)
5348 solv->decisionmap[redoq.elements[i]] = redoq.elements[i + 1];
5352 * if unsolvable, prepare solutions
5355 if (solv->problems.count)
5357 int recocount = solv->recommendations.count;
5358 solv->recommendations.count = 0; /* so that revert() doesn't mess with it */
5359 queue_empty(&redoq);
5360 for (i = 0; i < solv->decisionq.count; i++)
5362 Id p = solv->decisionq.elements[i];
5363 queue_push(&redoq, p);
5364 queue_push(&redoq, solv->decisionq_why.elements[i]);
5365 queue_push(&redoq, solv->decisionmap[p > 0 ? p : -p]);
5367 problems_to_solutions(solv, job);
5368 memset(solv->decisionmap, 0, pool->nsolvables * sizeof(Id));
5369 queue_empty(&solv->decisionq);
5370 queue_empty(&solv->decisionq_why);
5371 for (i = 0; i < redoq.count; i += 3)
5373 Id p = redoq.elements[i];
5374 queue_push(&solv->decisionq, p);
5375 queue_push(&solv->decisionq_why, redoq.elements[i + 1]);
5376 solv->decisionmap[p > 0 ? p : -p] = redoq.elements[i + 2];
5378 solv->recommendations.count = recocount;
5382 POOL_DEBUG(SAT_DEBUG_STATS, "final solver statistics: %d learned rules, %d unsolvable\n", solv->stats_learned, solv->stats_unsolvable);
5383 POOL_DEBUG(SAT_DEBUG_STATS, "solver_solve took %d ms\n", sat_timems(solve_start));
5387 /***********************************************************************/
5388 /* disk usage computations */
5390 /*-------------------------------------------------------------------
5392 * calculate DU changes
5396 solver_calc_duchanges(Solver *solv, DUChanges *mps, int nmps)
5400 solver_create_state_maps(solv, &installedmap, 0);
5401 pool_calc_duchanges(solv->pool, &installedmap, mps, nmps);
5402 map_free(&installedmap);
5406 /*-------------------------------------------------------------------
5408 * calculate changes in install size
5412 solver_calc_installsizechange(Solver *solv)
5417 solver_create_state_maps(solv, &installedmap, 0);
5418 change = pool_calc_installsizechange(solv->pool, &installedmap);
5419 map_free(&installedmap);
5424 solver_trivial_installable(Solver *solv, Queue *pkgs, Queue *res)
5427 solver_create_state_maps(solv, &installedmap, 0);
5428 pool_trivial_installable_noobsoletesmap(solv->pool, &installedmap, pkgs, res, solv->noobsoletes.size ? &solv->noobsoletes : 0);
5429 map_free(&installedmap);
5433 #define FIND_INVOLVED_DEBUG 0
5435 solver_find_involved(Solver *solv, Queue *installedq, Solvable *ts, Queue *q)
5437 Pool *pool = solv->pool;
5442 Queue installedq_internal;
5443 Id tp, ip, p, pp, req, *reqp, sup, *supp;
5446 tp = ts - pool->solvables;
5448 queue_init(&installedq_internal);
5449 map_init(&im, pool->nsolvables);
5450 map_init(&installedm, pool->nsolvables);
5454 installedq = &installedq_internal;
5455 if (solv->installed)
5457 for (ip = solv->installed->start; ip < solv->installed->end; ip++)
5459 s = pool->solvables + ip;
5460 if (s->repo != solv->installed)
5462 queue_push(installedq, ip);
5466 for (i = 0; i < installedq->count; i++)
5468 ip = installedq->elements[i];
5469 MAPSET(&installedm, ip);
5473 queue_push(&iq, ts - pool->solvables);
5476 ip = queue_shift(&iq);
5477 if (!MAPTST(&im, ip))
5479 if (!MAPTST(&installedm, ip))
5482 s = pool->solvables + ip;
5483 #if FIND_INVOLVED_DEBUG
5484 printf("hello %s\n", solvable2str(pool, s));
5488 reqp = s->repo->idarraydata + s->requires;
5489 while ((req = *reqp++) != 0)
5491 if (req == SOLVABLE_PREREQMARKER)
5493 /* count number of installed packages that match */
5495 FOR_PROVIDES(p, pp, req)
5496 if (MAPTST(&installedm, p))
5500 FOR_PROVIDES(p, pp, req)
5504 #if FIND_INVOLVED_DEBUG
5505 printf("%s requires %s\n", solvable2str(pool, pool->solvables + ip), solvable2str(pool, pool->solvables + p));
5514 reqp = s->repo->idarraydata + s->recommends;
5515 while ((req = *reqp++) != 0)
5518 FOR_PROVIDES(p, pp, req)
5519 if (MAPTST(&installedm, p))
5523 FOR_PROVIDES(p, pp, req)
5527 #if FIND_INVOLVED_DEBUG
5528 printf("%s recommends %s\n", solvable2str(pool, pool->solvables + ip), solvable2str(pool, pool->solvables + p));
5537 /* supplements pass */
5538 for (i = 0; i < installedq->count; i++)
5540 ip = installedq->elements[i];
5541 s = pool->solvables + ip;
5542 if (!s->supplements)
5544 if (!MAPTST(&im, ip))
5546 supp = s->repo->idarraydata + s->supplements;
5547 while ((sup = *supp++) != 0)
5548 if (!dep_possible(solv, sup, &im) && dep_possible(solv, sup, &installedm))
5550 /* no longer supplemented, also erase */
5553 #if FIND_INVOLVED_DEBUG
5554 printf("%s supplemented\n", solvable2str(pool, pool->solvables + ip));
5556 queue_push(&iq, ip);
5562 for (i = 0; i < installedq->count; i++)
5564 ip = installedq->elements[i];
5565 if (MAPTST(&im, ip))
5566 queue_push(&iq, ip);
5571 ip = queue_shift(&iq);
5572 if (!MAPTST(&installedm, ip))
5574 s = pool->solvables + ip;
5575 #if FIND_INVOLVED_DEBUG
5576 printf("bye %s\n", solvable2str(pool, s));
5580 reqp = s->repo->idarraydata + s->requires;
5581 while ((req = *reqp++) != 0)
5583 FOR_PROVIDES(p, pp, req)
5585 if (!MAPTST(&im, p))
5589 #if FIND_INVOLVED_DEBUG
5590 printf("%s requires %s\n", solvable2str(pool, pool->solvables + ip), solvable2str(pool, pool->solvables + p));
5600 reqp = s->repo->idarraydata + s->recommends;
5601 while ((req = *reqp++) != 0)
5603 FOR_PROVIDES(p, pp, req)
5605 if (!MAPTST(&im, p))
5609 #if FIND_INVOLVED_DEBUG
5610 printf("%s recommends %s\n", solvable2str(pool, pool->solvables + ip), solvable2str(pool, pool->solvables + p));
5620 /* supplements pass */
5621 for (i = 0; i < installedq->count; i++)
5623 ip = installedq->elements[i];
5626 s = pool->solvables + ip;
5627 if (!s->supplements)
5629 if (MAPTST(&im, ip))
5631 supp = s->repo->idarraydata + s->supplements;
5632 while ((sup = *supp++) != 0)
5633 if (dep_possible(solv, sup, &im))
5637 #if FIND_INVOLVED_DEBUG
5638 printf("%s supplemented\n", solvable2str(pool, pool->solvables + ip));
5641 queue_push(&iq, ip);
5649 /* convert map into result */
5650 for (i = 0; i < installedq->count; i++)
5652 ip = installedq->elements[i];
5653 if (MAPTST(&im, ip))
5655 if (ip == ts - pool->solvables)
5660 map_free(&installedm);
5661 queue_free(&installedq_internal);