2 * Copyright (c) 2007, Novell Inc.
4 * This program is licensed under the BSD license, read LICENSE.BSD
5 * for further information
11 * SAT based dependency solver
27 #define RULES_BLOCK 63
28 #define REGARD_RECOMMENDS_OF_INSTALLED_ITEMS 0
32 solver_splitprovides(Solver *solv, Id dep)
34 Pool *pool = solv->pool;
39 if (!solv->dosplitprovides || !solv->installed)
43 rd = GETRELDEP(pool, dep);
44 if (rd->flags != REL_WITH)
46 FOR_PROVIDES(p, pp, dep)
48 s = pool->solvables + p;
49 if (s->repo == solv->installed && s->name == rd->name)
56 solver_dep_installed(Solver *solv, Id dep)
59 Pool *pool = solv->pool;
64 Reldep *rd = GETRELDEP(pool, dep);
65 if (rd->flags == REL_AND)
67 if (!solver_dep_installed(solv, rd->name))
69 return solver_dep_installed(solv, rd->evr);
71 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
72 return solver_dep_installed(solv, rd->evr);
74 FOR_PROVIDES(p, pp, dep)
76 if (p == SYSTEMSOLVABLE || (solv->installed && pool->solvables[p].repo == solv->installed))
84 /* this mirrors solver_dep_fulfilled but uses map m instead of the decisionmap */
86 dep_possible(Solver *solv, Id dep, Map *m)
88 Pool *pool = solv->pool;
93 Reldep *rd = GETRELDEP(pool, dep);
94 if (rd->flags == REL_AND)
96 if (!dep_possible(solv, rd->name, m))
98 return dep_possible(solv, rd->evr, m);
100 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
101 return solver_splitprovides(solv, rd->evr);
102 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
103 return solver_dep_installed(solv, rd->evr);
105 FOR_PROVIDES(p, pp, dep)
113 /*-----------------------------------------------------------------*/
120 printruleelement(Solver *solv, int type, Rule *r, Id v)
122 Pool *pool = solv->pool;
126 s = pool->solvables + -v;
127 POOL_DEBUG(type, " !%s [%d]", solvable2str(pool, s), -v);
131 s = pool->solvables + v;
132 POOL_DEBUG(type, " %s [%d]", solvable2str(pool, s), v);
137 POOL_DEBUG(type, " (w1)");
139 POOL_DEBUG(type, " (w2)");
141 if (solv->decisionmap[s - pool->solvables] > 0)
142 POOL_DEBUG(type, " Install.level%d", solv->decisionmap[s - pool->solvables]);
143 if (solv->decisionmap[s - pool->solvables] < 0)
144 POOL_DEBUG(type, " Conflict.level%d", -solv->decisionmap[s - pool->solvables]);
145 POOL_DEBUG(type, "\n");
154 printrule(Solver *solv, int type, Rule *r)
156 Pool *pool = solv->pool;
160 if (r >= solv->rules && r < solv->rules + solv->nrules) /* r is a solver rule */
161 POOL_DEBUG(type, "Rule #%d:", (int)(r - solv->rules));
163 POOL_DEBUG(type, "Rule:"); /* r is any rule */
165 POOL_DEBUG(type, " (disabled)");
166 POOL_DEBUG(type, "\n");
170 /* print direct literal */
172 else if (r->d == ID_NULL)
176 /* binary rule --> print w2 as second literal */
180 /* every other which is in d */
181 v = solv->pool->whatprovidesdata[r->d + i - 1];
184 printruleelement(solv, type, r, v);
186 POOL_DEBUG(type, " next rules: %d %d\n", r->n1, r->n2);
190 printruleclass(Solver *solv, int type, Rule *r)
192 Pool *pool = solv->pool;
193 if (r - solv->rules >= solv->learntrules)
194 POOL_DEBUG(type, "LEARNT ");
195 else if (r - solv->rules >= solv->weakrules)
196 POOL_DEBUG(type, "WEAK ");
197 else if (r - solv->rules >= solv->systemrules)
198 POOL_DEBUG(type, "SYSTEM ");
199 else if (r - solv->rules >= solv->jobrules)
200 POOL_DEBUG(type, "JOB ");
201 printrule(solv, type, r);
205 /*-----------------------------------------------------------------*/
211 static Pool *unifyrules_sortcmp_data;
214 * compare rules for unification sort
218 unifyrules_sortcmp(const void *ap, const void *bp)
220 Pool *pool = unifyrules_sortcmp_data;
221 Rule *a = (Rule *)ap;
222 Rule *b = (Rule *)bp;
228 return x; /* p differs */
231 if (a->d == 0 && b->d == 0)
232 return a->w2 - b->w2; /* assertion: return w2 diff */
234 if (a->d == 0) /* a is assertion, b not */
236 x = a->w2 - pool->whatprovidesdata[b->d];
240 if (b->d == 0) /* b is assertion, a not */
242 x = pool->whatprovidesdata[a->d] - b->w2;
246 /* compare whatprovidesdata */
247 ad = pool->whatprovidesdata + a->d;
248 bd = pool->whatprovidesdata + b->d;
250 if ((x = *ad++ - *bd++) != 0)
261 unifyrules(Solver *solv)
263 Pool *pool = solv->pool;
267 if (solv->nrules <= 1) /* nothing to unify */
270 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- unifyrules -----\n");
272 /* sort rules first */
273 unifyrules_sortcmp_data = solv->pool;
274 qsort(solv->rules + 1, solv->nrules - 1, sizeof(Rule), unifyrules_sortcmp);
281 for (i = j = 1, ir = solv->rules + 1; i < solv->nrules; i++, ir++)
283 if (jr && !unifyrules_sortcmp(ir, jr))
284 continue; /* prune! */
285 jr = solv->rules + j++; /* keep! */
290 /* reduced count from nrules to j rules */
291 POOL_DEBUG(SAT_DEBUG_STATS, "pruned rules from %d to %d\n", solv->nrules, j);
293 /* adapt rule buffer */
295 solv->rules = (Rule *)sat_realloc(solv->rules, ((solv->nrules + RULES_BLOCK) & ~RULES_BLOCK) * sizeof(Rule));
296 IF_POOLDEBUG (SAT_DEBUG_STATS)
303 for (i = 1; i < solv->nrules; i++)
310 dp = solv->pool->whatprovidesdata + r->d;
315 POOL_DEBUG(SAT_DEBUG_STATS, " binary: %d\n", binr);
316 POOL_DEBUG(SAT_DEBUG_STATS, " normal: %d, %d literals\n", solv->nrules - 1 - binr, lits);
318 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- unifyrules end -----\n");
328 hashrule(Solver *solv, Id p, Id d, int n)
330 unsigned int x = (unsigned int)p;
334 return (x * 37) ^ (unsigned int)d;
335 dp = solv->pool->whatprovidesdata + d;
337 x = (x * 37) ^ (unsigned int)*dp++;
345 * p = direct literal; always < 0 for installed rpm rules
346 * d, if < 0 direct literal, if > 0 offset into whatprovides, if == 0 rule is assertion (look at p only)
349 * A requires b, b provided by B1,B2,B3 => (-A|B1|B2|B3)
351 * p < 0 : pkg id of A
352 * d > 0 : Offset in whatprovidesdata (list of providers of b)
354 * A conflicts b, b provided by B1,B2,B3 => (-A|-B1), (-A|-B2), (-A|-B3)
355 * p < 0 : pkg id of A
356 * d < 0 : Id of solvable (e.g. B1)
358 * d == 0: unary rule, assertion => (A) or (-A)
360 * Install: p > 0, d = 0 (A) user requested install
361 * Remove: p < 0, d = 0 (-A) user requested remove
362 * Requires: p < 0, d > 0 (-A|B1|B2|...) d: <list of providers for requirement of p>
363 * Updates: p > 0, d > 0 (A|B1|B2|...) d: <list of updates for solvable p>
364 * Conflicts: p < 0, d < 0 (-A|-B) either p (conflict issuer) or d (conflict provider) (binary rule)
365 * ? p > 0, d < 0 (A|-B)
366 * No-op ?: p = 0, d = 0 (null) (used as policy rule placeholder)
370 * Direct assertion (no watch needed)( if d <0 ) --> d = 0, w1 = p, w2 = 0
371 * Binary rule: p = first literal, d = 0, w2 = second literal, w1 = p
372 * every other : w1 = p, w2 = whatprovidesdata[d];
373 * Disabled rule: w1 = 0
375 * always returns a rule for non-rpm rules
379 addrule(Solver *solv, Id p, Id d)
381 Pool *pool = solv->pool;
385 int n = 0; /* number of literals in rule - 1
386 0 = direct assertion (single literal)
390 /* it often happenes that requires lead to adding the same rpm rule
391 * multiple times, so we prune those duplicates right away to make
392 * the work for unifyrules a bit easier */
394 if (solv->nrules && !solv->jobrules)
396 r = solv->rules + solv->nrules - 1; /* get the last added rule */
397 if (r->p == p && r->d == d && d != 0) /* identical and not user requested */
403 /* always a binary rule */
405 return 0; /* ignore self conflict */
410 for (dp = pool->whatprovidesdata + d; *dp; dp++, n++)
412 return 0; /* rule is self-fulfilling */
414 d = dp[-1]; /* take single literal */
417 if (n == 0 && !solv->jobrules)
419 /* this is a rpm rule assertion, we do not have to allocate it */
420 /* it can be identified by a level of 1 and a zero reason */
421 /* we must not drop those rules from the decisionq when rewinding! */
423 assert(solv->decisionmap[-p] == 0 || solv->decisionmap[-p] == -1);
424 if (solv->decisionmap[-p])
425 return 0; /* already got that one */
426 queue_push(&solv->decisionq, p);
427 queue_push(&solv->decisionq_why, 0);
428 solv->decisionmap[-p] = -1;
433 /* smallest literal first so we can find dups */
437 n = 1; /* re-set n, was used as temp var */
440 /* check if the last added rule is exactly the same as what we're looking for. */
441 if (r && n == 1 && !r->d && r->p == p && r->w2 == d)
442 return r; /* binary rule */
444 if (r && n > 1 && r->d && r->p == p)
446 /* Rule where d is an offset in whatprovidesdata */
450 dp2 = pool->whatprovidesdata + r->d;
451 for (dp = pool->whatprovidesdata + d; *dp; dp++, dp2++)
462 /* check and extend rule buffer */
463 if ((solv->nrules & RULES_BLOCK) == 0)
465 solv->rules = (Rule *)sat_realloc(solv->rules, (solv->nrules + (RULES_BLOCK + 1)) * sizeof(Rule));
468 r = solv->rules + solv->nrules++; /* point to rule space */
473 /* direct assertion, no watch needed */
489 r->w2 = pool->whatprovidesdata[d];
494 IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION)
496 POOL_DEBUG(SAT_DEBUG_RULE_CREATION, " Add rule: ");
497 printrule(solv, SAT_DEBUG_RULE_CREATION, r);
504 disablerule(Solver *solv, Rule *r)
510 enablerule(Solver *solv, Rule *r)
512 if (r->d == 0 || r->w2 != r->p)
515 r->w1 = solv->pool->whatprovidesdata[r->d];
519 /**********************************************************************************/
521 /* a problem is an item on the solver's problem list. It can either be >0, in that
522 * case it is a system (upgrade) rule, or it can be <0, which makes it refer to a job
523 * consisting of multiple job rules.
527 disableproblem(Solver *solv, Id v)
535 disablerule(solv, solv->rules + v);
539 jp = solv->ruletojob.elements;
540 for (i = solv->jobrules, r = solv->rules + i; i < solv->systemrules; i++, r++, jp++)
542 disablerule(solv, r);
546 enableproblem(Solver *solv, Id v)
554 enablerule(solv, solv->rules + v);
558 jp = solv->ruletojob.elements;
559 for (i = solv->jobrules, r = solv->rules + i; i < solv->systemrules; i++, r++, jp++)
565 printproblem(Solver *solv, Id v)
567 Pool *pool = solv->pool;
573 printrule(solv, SAT_DEBUG_SOLUTIONS, solv->rules + v);
577 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "JOB %d\n", v);
578 jp = solv->ruletojob.elements;
579 for (i = solv->jobrules, r = solv->rules + i; i < solv->systemrules; i++, r++, jp++)
582 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "- ");
583 printrule(solv, SAT_DEBUG_SOLUTIONS, r);
585 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "ENDJOB\n");
591 /************************************************************************/
593 /* go through system and job rules and add direct assertions
594 * to the decisionqueue. If we find a conflict, disable rules and
595 * add them to problem queue.
598 makeruledecisions(Solver *solv)
600 Pool *pool = solv->pool;
606 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- makeruledecisions ; size decisionq: %d -----\n",solv->decisionq.count);
608 decisionstart = solv->decisionq.count;
609 /* rpm rules don't have assertions, so we can start with the job
611 for (ri = solv->jobrules, r = solv->rules + ri; ri < solv->nrules; ri++, r++)
613 if (!r->w1 || r->w2) /* disabled or no assertion */
617 if (solv->decisionmap[vv] == 0)
619 queue_push(&solv->decisionq, v);
620 queue_push(&solv->decisionq_why, r - solv->rules);
621 solv->decisionmap[vv] = v > 0 ? 1 : -1;
622 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
624 Solvable *s = solv->pool->solvables + vv;
626 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "conflicting %s (assertion)\n", solvable2str(solv->pool, s));
628 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "installing %s (assertion)\n", solvable2str(solv->pool, s));
632 if (v > 0 && solv->decisionmap[vv] > 0)
634 if (v < 0 && solv->decisionmap[vv] < 0)
636 /* found a conflict! */
637 /* ri >= learntrules cannot happen, as this would mean that the
638 * problem was not solvable, so we wouldn't have created the
639 * learnt rule at all */
640 assert(ri < solv->learntrules);
641 /* if we are weak, just disable ourself */
642 if (ri >= solv->weakrules)
644 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "assertion conflict, but I am weak, disabling ");
645 printrule(solv, SAT_DEBUG_UNSOLVABLE, r);
646 disablerule(solv, r);
650 /* only job and system rules left in the decisionq*/
651 /* find the decision which is the "opposite" of the jobrule */
652 for (i = 0; i < solv->decisionq.count; i++)
653 if (solv->decisionq.elements[i] == -v)
655 assert(i < solv->decisionq.count);
656 if (solv->decisionq_why.elements[i] == 0)
658 /* conflict with rpm rule, need only disable our rule */
659 assert(v > 0 || v == -SYSTEMSOLVABLE);
661 queue_push(&solv->problems, solv->learnt_pool.count);
662 queue_push(&solv->learnt_pool, ri);
663 queue_push(&solv->learnt_pool, v != -SYSTEMSOLVABLE ? -v : v);
664 queue_push(&solv->learnt_pool, 0);
665 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "conflict with rpm rule, disabling rule #%d\n", ri);
666 if (ri < solv->systemrules)
667 v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
670 queue_push(&solv->problems, v);
671 queue_push(&solv->problems, 0);
672 disableproblem(solv, v);
676 /* conflict with another job or system rule */
678 queue_push(&solv->problems, solv->learnt_pool.count);
679 queue_push(&solv->learnt_pool, ri);
680 queue_push(&solv->learnt_pool, solv->decisionq_why.elements[i]);
681 queue_push(&solv->learnt_pool, 0);
683 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "conflicting system/job assertions over literal %d\n", vv);
684 /* push all of our rules asserting this literal on the problem stack */
685 for (i = solv->jobrules, rr = solv->rules + i; i < solv->nrules; i++, rr++)
687 if (!rr->w1 || rr->w2)
689 if (rr->p != vv && rr->p != -vv)
691 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, " - disabling rule #%d\n", i);
693 if (i < solv->systemrules)
694 v = -(solv->ruletojob.elements[i - solv->jobrules] + 1);
695 queue_push(&solv->problems, v);
696 disableproblem(solv, v);
698 queue_push(&solv->problems, 0);
701 while (solv->decisionq.count > decisionstart)
703 v = solv->decisionq.elements[--solv->decisionq.count];
704 --solv->decisionq_why.count;
706 solv->decisionmap[vv] = 0;
708 ri = solv->jobrules - 1;
709 r = solv->rules + ri;
712 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- makeruledecisions end; size decisionq: %d -----\n",solv->decisionq.count);
716 * we have enabled or disabled some of our rules. We now reenable all
717 * of our learnt rules but the ones that were learnt from rules that
721 enabledisablelearntrules(Solver *solv)
723 Pool *pool = solv->pool;
728 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "enabledisablelearntrules called\n");
729 for (i = solv->learntrules, r = solv->rules + i; i < solv->nrules; i++, r++)
731 whyp = solv->learnt_pool.elements + solv->learnt_why.elements[i - solv->learntrules];
732 while ((why = *whyp++) != 0)
735 continue; /* rpm assertion */
737 if (!solv->rules[why].w1)
740 /* why != 0: we found a disabled rule, disable the learnt rule */
743 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
745 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "disabling learnt ");
746 printrule(solv, SAT_DEBUG_SOLUTIONS, r);
748 disablerule(solv, r);
750 else if (!why && !r->w1)
752 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
754 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "re-enabling learnt ");
755 printrule(solv, SAT_DEBUG_SOLUTIONS, r);
763 /* FIXME: bad code ahead, replace as soon as possible */
765 disableupdaterules(Solver *solv, Queue *job, int jobidx)
767 Pool *pool = solv->pool;
769 Id how, what, p, *pp;
775 installed = solv->installed;
781 how = job->elements[jobidx];
784 case SOLVER_INSTALL_SOLVABLE:
785 case SOLVER_ERASE_SOLVABLE:
786 case SOLVER_ERASE_SOLVABLE_NAME:
787 case SOLVER_ERASE_SOLVABLE_PROVIDES:
793 /* go through all enabled job rules */
794 MAPZERO(&solv->noupdate);
795 for (i = solv->jobrules; i < solv->systemrules; i++)
798 if (!r->w1) /* disabled? */
800 j = solv->ruletojob.elements[i - solv->jobrules];
804 how = job->elements[j];
805 what = job->elements[j + 1];
808 case SOLVER_INSTALL_SOLVABLE: /* install specific solvable */
809 s = pool->solvables + what;
810 FOR_PROVIDES(p, pp, s->name)
812 if (pool->solvables[p].name != s->name)
814 if (pool->solvables[p].repo == installed)
815 MAPSET(&solv->noupdate, p - installed->start);
818 case SOLVER_ERASE_SOLVABLE:
819 s = pool->solvables + what;
820 if (s->repo == installed)
821 MAPSET(&solv->noupdate, what - installed->start);
823 case SOLVER_ERASE_SOLVABLE_NAME: /* remove by capability */
824 case SOLVER_ERASE_SOLVABLE_PROVIDES:
825 FOR_PROVIDES(p, pp, what)
827 if (how == SOLVER_ERASE_SOLVABLE_NAME && pool->solvables[p].name != what)
829 if (pool->solvables[p].repo == installed)
830 MAPSET(&solv->noupdate, p - installed->start);
838 /* fixup update rule status */
839 if (solv->allowuninstall)
840 return; /* no update rules at all */
844 /* we just disabled job #jobidx. enable all update rules
845 * that aren't disabled by the remaining job rules */
846 how = job->elements[jobidx];
847 what = job->elements[jobidx + 1];
850 case SOLVER_INSTALL_SOLVABLE:
851 s = pool->solvables + what;
852 FOR_PROVIDES(p, pp, s->name)
854 if (pool->solvables[p].name != s->name)
856 if (pool->solvables[p].repo != installed)
858 if (MAPTST(&solv->noupdate, p - installed->start))
860 r = solv->rules + solv->systemrules + (p - installed->start);
864 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
866 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
867 printrule(solv, SAT_DEBUG_SOLUTIONS, r);
871 case SOLVER_ERASE_SOLVABLE:
872 s = pool->solvables + what;
873 if (s->repo != installed)
875 if (MAPTST(&solv->noupdate, what - installed->start))
877 r = solv->rules + solv->systemrules + (what - installed->start);
881 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
883 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
884 printrule(solv, SAT_DEBUG_SOLUTIONS, r);
887 case SOLVER_ERASE_SOLVABLE_NAME: /* remove by capability */
888 case SOLVER_ERASE_SOLVABLE_PROVIDES:
889 FOR_PROVIDES(p, pp, what)
891 if (how == SOLVER_ERASE_SOLVABLE_NAME && pool->solvables[p].name != what)
893 if (pool->solvables[p].repo != installed)
895 if (MAPTST(&solv->noupdate, p - installed->start))
897 r = solv->rules + solv->systemrules + (p - installed->start);
901 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
903 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
904 printrule(solv, SAT_DEBUG_SOLUTIONS, r);
914 for (i = 0; i < installed->nsolvables; i++)
916 r = solv->rules + solv->systemrules + i;
917 if (r->w1 && MAPTST(&solv->noupdate, i))
918 disablerule(solv, r); /* was enabled, need to disable */
924 * add (install) rules for solvable
925 * for unfulfilled requirements, conflicts, obsoletes,....
926 * add a negative assertion for solvables that are not installable
930 addrpmrulesforsolvable(Solver *solv, Solvable *s, Map *m)
932 Pool *pool = solv->pool;
933 Repo *installed = solv->installed;
947 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforsolvable -----\n");
949 queue_init_buffer(&q, qbuf, sizeof(qbuf)/sizeof(*qbuf));
950 queue_push(&q, s - pool->solvables); /* push solvable Id */
956 * s: Pointer to solvable
960 if (MAPTST(m, n)) /* continue if already done */
964 s = pool->solvables + n; /* s = Solvable in question */
967 if (installed /* Installed system available */
968 && !solv->fixsystem /* NOT repair errors in rpm dependency graph */
969 && s->repo == installed) /* solvable is installed? */
971 dontfix = 1; /* dont care about broken rpm deps */
974 if (!dontfix && s->arch != ARCH_SRC && s->arch != ARCH_NOSRC && !pool_installable(pool, s))
976 POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "package %s [%d] is not installable\n", solvable2str(pool, s), (Id)(s - pool->solvables));
977 addrule(solv, -n, 0); /* uninstallable */
980 /*-----------------------------------------
981 * check requires of s
986 reqp = s->repo->idarraydata + s->requires;
987 while ((req = *reqp++) != 0) /* go throw all requires */
989 if (req == SOLVABLE_PREREQMARKER) /* skip the marker */
992 dp = pool_whatprovides(pool, req);
994 if (*dp == SYSTEMSOLVABLE) /* always installed */
999 /* the strategy here is to not insist on dependencies
1000 * that are already broken. so if we find one provider
1001 * that was already installed, we know that the
1002 * dependency was not broken before so we enforce it */
1003 for (i = 0; (p = dp[i]) != 0; i++) /* for all providers */
1005 if (pool->solvables[p].repo == installed)
1006 break; /* provider was installed */
1008 if (!p) /* previously broken dependency */
1010 POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "ignoring broken requires %s of installed package %s\n", dep2str(pool, req), solvable2str(pool, s));
1017 /* nothing provides req! */
1018 POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "package %s [%d] is not installable (%s)\n", solvable2str(pool, s), (Id)(s - pool->solvables), dep2str(pool, req));
1019 addrule(solv, -n, 0); /* mark requestor as uninstallable */
1023 IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION)
1025 POOL_DEBUG(SAT_DEBUG_RULE_CREATION," %s requires %s\n", solvable2str(pool, s), dep2str(pool, req));
1026 for (i = 0; dp[i]; i++)
1027 POOL_DEBUG(SAT_DEBUG_RULE_CREATION, " provided by %s\n", solvable2str(pool, pool->solvables + dp[i]));
1030 /* add 'requires' dependency */
1031 /* rule: (-requestor|provider1|provider2|...|providerN) */
1032 addrule(solv, -n, dp - pool->whatprovidesdata);
1034 /* descend the dependency tree */
1035 for (; *dp; dp++) /* loop through all providers */
1037 if (!MAPTST(m, *dp))
1038 queue_push(&q, *dp);
1041 } /* while, requirements of n */
1043 } /* if, requirements */
1045 /* that's all we check for src packages */
1046 if (s->arch == ARCH_SRC || s->arch == ARCH_NOSRC)
1049 /*-----------------------------------------
1050 * check conflicts of s
1055 conp = s->repo->idarraydata + s->conflicts;
1056 while ((con = *conp++) != 0)
1058 FOR_PROVIDES(p, pp, con)
1060 /* dontfix: dont care about conflicts with already installed packs */
1061 if (dontfix && pool->solvables[p].repo == installed)
1063 /* rule: -n|-p: either solvable _or_ provider of conflict */
1064 addrule(solv, -n, -p);
1069 /*-----------------------------------------
1070 * check obsoletes if not installed
1072 if (!installed || pool->solvables[n].repo != installed)
1073 { /* not installed */
1076 obsp = s->repo->idarraydata + s->obsoletes;
1077 while ((obs = *obsp++) != 0)
1079 FOR_PROVIDES(p, pp, obs)
1080 addrule(solv, -n, -p);
1083 FOR_PROVIDES(p, pp, s->name)
1085 if (s->name == pool->solvables[p].name)
1086 addrule(solv, -n, -p);
1090 /*-----------------------------------------
1091 * add recommends to the rule list
1095 recp = s->repo->idarraydata + s->recommends;
1096 while ((rec = *recp++) != 0)
1098 FOR_PROVIDES(p, pp, rec)
1105 sugp = s->repo->idarraydata + s->suggests;
1106 while ((sug = *sugp++) != 0)
1108 FOR_PROVIDES(p, pp, sug)
1115 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforsolvable end -----\n");
1119 addrpmrulesforweak(Solver *solv, Map *m)
1121 Pool *pool = solv->pool;
1126 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforweak -----\n");
1127 for (i = n = 1; n < pool->nsolvables; i++, n++)
1129 if (i == pool->nsolvables)
1133 s = pool->solvables + i;
1134 if (!pool_installable(pool, s))
1139 supp = s->repo->idarraydata + s->supplements;
1140 while ((sup = *supp++) != ID_NULL)
1141 if (dep_possible(solv, sup, m))
1144 if (!sup && s->freshens)
1146 supp = s->repo->idarraydata + s->freshens;
1147 while ((sup = *supp++) != ID_NULL)
1148 if (dep_possible(solv, sup, m))
1151 if (!sup && s->enhances)
1153 supp = s->repo->idarraydata + s->enhances;
1154 while ((sup = *supp++) != ID_NULL)
1155 if (dep_possible(solv, sup, m))
1160 addrpmrulesforsolvable(solv, s, m);
1163 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforweak end -----\n");
1167 addrpmrulesforupdaters(Solver *solv, Solvable *s, Map *m, int allowall)
1169 Pool *pool = solv->pool;
1174 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforupdaters -----\n");
1176 queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
1177 policy_findupdatepackages(solv, s, &qs, allowall);
1178 if (!MAPTST(m, s - pool->solvables)) /* add rule for s if not already done */
1179 addrpmrulesforsolvable(solv, s, m);
1180 for (i = 0; i < qs.count; i++)
1181 if (!MAPTST(m, qs.elements[i]))
1182 addrpmrulesforsolvable(solv, pool->solvables + qs.elements[i], m);
1185 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforupdaters -----\n");
1189 * add rule for update
1190 * (A|A1|A2|A3...) An = update candidates for A
1192 * s = (installed) solvable
1196 addupdaterule(Solver *solv, Solvable *s, int allowall)
1198 /* installed packages get a special upgrade allowed rule */
1199 Pool *pool = solv->pool;
1204 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addupdaterule -----\n");
1206 queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
1207 policy_findupdatepackages(solv, s, &qs, allowall);
1208 if (qs.count == 0) /* no updaters found */
1211 d = pool_queuetowhatprovides(pool, &qs); /* intern computed queue */
1213 addrule(solv, s - pool->solvables, d); /* allow update of s */
1214 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addupdaterule end -----\n");
1218 /*-----------------------------------------------------------------*/
1227 printWatches(Solver *solv, int type)
1229 Pool *pool = solv->pool;
1232 POOL_DEBUG(type, "Watches: \n");
1234 for (counter = -(pool->nsolvables); counter <= pool->nsolvables; counter ++)
1236 POOL_DEBUG(type, " solvable [%d] -- rule [%d]\n", counter, solv->watches[counter+pool->nsolvables]);
1243 * initial setup for all watches
1247 makewatches(Solver *solv)
1251 int nsolvables = solv->pool->nsolvables;
1253 sat_free(solv->watches);
1254 /* lower half for removals, upper half for installs */
1255 solv->watches = sat_calloc(2 * nsolvables, sizeof(Id));
1257 /* do it reverse so rpm rules get triggered first */
1258 for (i = 1, r = solv->rules + solv->nrules - 1; i < solv->nrules; i++, r--)
1260 for (i = 1, r = solv->rules + 1; i < solv->nrules; i++, r++)
1263 if (!r->w1 /* rule is disabled */
1264 || !r->w2) /* rule is assertion */
1267 /* see addwatches(solv, r) */
1268 r->n1 = solv->watches[nsolvables + r->w1];
1269 solv->watches[nsolvables + r->w1] = r - solv->rules;
1271 r->n2 = solv->watches[nsolvables + r->w2];
1272 solv->watches[nsolvables + r->w2] = r - solv->rules;
1278 * add watches (for rule)
1282 addwatches(Solver *solv, Rule *r)
1284 int nsolvables = solv->pool->nsolvables;
1286 r->n1 = solv->watches[nsolvables + r->w1];
1287 solv->watches[nsolvables + r->w1] = r - solv->rules;
1289 r->n2 = solv->watches[nsolvables + r->w2];
1290 solv->watches[nsolvables + r->w2] = r - solv->rules;
1294 /*-----------------------------------------------------------------*/
1295 /* rule propagation */
1297 #define DECISIONMAP_TRUE(p) ((p) > 0 ? (decisionmap[p] > 0) : (decisionmap[-p] < 0))
1302 * propagate decision to all rules
1303 * return : 0 = everything is OK
1304 * watched rule = there is a conflict
1308 propagate(Solver *solv, int level)
1310 Pool *pool = solv->pool;
1315 Id *decisionmap = solv->decisionmap;
1316 Id *watches = solv->watches + pool->nsolvables;
1318 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "----- propagate -----\n");
1320 while (solv->propagate_index < solv->decisionq.count)
1322 /* negate because our watches trigger if literal goes FALSE */
1323 pkg = -solv->decisionq.elements[solv->propagate_index++];
1324 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1326 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "popagate for decision %d level %d\n", -pkg, level);
1327 printruleelement(solv, SAT_DEBUG_PROPAGATE, 0, -pkg);
1328 printWatches(solv, SAT_DEBUG_SCHUBI);
1331 for (rp = watches + pkg; *rp; rp = nrp)
1333 r = solv->rules + *rp;
1335 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1337 POOL_DEBUG(SAT_DEBUG_PROPAGATE," watch triggered ");
1338 printrule(solv, SAT_DEBUG_PROPAGATE, r);
1343 ow = r->w2; /* regard the second watchpoint to come to a solution */
1348 ow = r->w1; /* regard the first watchpoint to come to a solution */
1351 /* if clause is TRUE, nothing to do */
1352 if (DECISIONMAP_TRUE(ow))
1357 /* not a binary clause, check if we need to move our watch */
1358 /* search for a literal that is not ow and not false */
1359 /* (true is also ok, in that case the rule is fulfilled) */
1360 if (r->p && r->p != ow && !DECISIONMAP_TRUE(-r->p))
1363 for (dp = pool->whatprovidesdata + r->d; (p = *dp++) != 0;)
1364 if (p != ow && !DECISIONMAP_TRUE(-p))
1368 /* p is free to watch, move watch to p */
1369 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1372 POOL_DEBUG(SAT_DEBUG_PROPAGATE, " -> move w%d to %s\n", (pkg == r->w1 ? 1 : 2), solvable2str(pool, pool->solvables + p));
1374 POOL_DEBUG(SAT_DEBUG_PROPAGATE," -> move w%d to !%s\n", (pkg == r->w1 ? 1 : 2), solvable2str(pool, pool->solvables - p));
1388 watches[p] = r - solv->rules;
1392 /* unit clause found, set other watch to TRUE */
1393 if (DECISIONMAP_TRUE(-ow))
1394 return r; /* eek, a conflict! */
1395 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1397 POOL_DEBUG(SAT_DEBUG_PROPAGATE, " unit ");
1398 printrule(solv, SAT_DEBUG_PROPAGATE, r);
1401 decisionmap[ow] = level;
1403 decisionmap[-ow] = -level;
1404 queue_push(&solv->decisionq, ow);
1405 queue_push(&solv->decisionq_why, r - solv->rules);
1406 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1408 Solvable *s = pool->solvables + (ow > 0 ? ow : -ow);
1410 POOL_DEBUG(SAT_DEBUG_PROPAGATE, " -> decided to install %s\n", solvable2str(pool, s));
1412 POOL_DEBUG(SAT_DEBUG_PROPAGATE, " -> decided to conflict %s\n", solvable2str(pool, s));
1416 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "----- propagate end-----\n");
1418 return 0; /* all is well */
1422 /*-----------------------------------------------------------------*/
1431 analyze(Solver *solv, int level, Rule *c, int *pr, int *dr, int *whyp)
1433 Pool *pool = solv->pool;
1436 Map seen; /* global? */
1439 int num = 0, l1num = 0;
1440 int learnt_why = solv->learnt_pool.count;
1441 Id *decisionmap = solv->decisionmap;
1445 POOL_DEBUG(SAT_DEBUG_ANALYZE, "ANALYZE at %d ----------------------\n", level);
1446 map_init(&seen, pool->nsolvables);
1447 idx = solv->decisionq.count;
1450 IF_POOLDEBUG (SAT_DEBUG_ANALYZE)
1451 printruleclass(solv, SAT_DEBUG_ANALYZE, c);
1452 queue_push(&solv->learnt_pool, c - solv->rules);
1453 dp = c->d ? pool->whatprovidesdata + c->d : 0;
1454 /* go through all literals of the rule */
1466 if (DECISIONMAP_TRUE(v)) /* the one true literal */
1468 vv = v > 0 ? v : -v;
1469 if (MAPTST(&seen, vv))
1471 l = solv->decisionmap[vv];
1476 /* a level 1 literal, mark it for later */
1477 MAPSET(&seen, vv); /* mark for scanning in level 1 phase */
1483 num++; /* need to do this one as well */
1494 v = solv->decisionq.elements[--idx];
1495 vv = v > 0 ? v : -v;
1496 if (MAPTST(&seen, vv))
1499 c = solv->rules + solv->decisionq_why.elements[idx];
1504 *pr = -v; /* so that v doesn't get lost */
1506 /* add involved level 1 rules */
1509 POOL_DEBUG(SAT_DEBUG_ANALYZE, "got %d involved level 1 decisions\n", l1num);
1513 v = solv->decisionq.elements[--idx];
1514 vv = v > 0 ? v : -v;
1515 if (!MAPTST(&seen, vv))
1517 why = solv->decisionq_why.elements[idx];
1520 queue_push(&solv->learnt_pool, -vv);
1521 IF_POOLDEBUG (SAT_DEBUG_ANALYZE)
1523 POOL_DEBUG(SAT_DEBUG_ANALYZE, "RPM ASSERT Rule:\n");
1524 printruleelement(solv, SAT_DEBUG_ANALYZE, 0, v);
1528 queue_push(&solv->learnt_pool, why);
1529 c = solv->rules + why;
1530 IF_POOLDEBUG (SAT_DEBUG_ANALYZE)
1531 printruleclass(solv, SAT_DEBUG_ANALYZE, c);
1542 if (DECISIONMAP_TRUE(v)) /* the one true literal */
1544 vv = v > 0 ? v : -v;
1545 l = solv->decisionmap[vv];
1546 if (l != 1 && l != -1)
1556 else if (r.count == 1 && r.elements[0] < 0)
1557 *dr = r.elements[0];
1559 *dr = pool_queuetowhatprovides(pool, &r);
1560 IF_POOLDEBUG (SAT_DEBUG_ANALYZE)
1562 POOL_DEBUG(SAT_DEBUG_ANALYZE, "learned rule for level %d (am %d)\n", rlevel, level);
1563 printruleelement(solv, SAT_DEBUG_ANALYZE, 0, *pr);
1564 for (i = 0; i < r.count; i++)
1565 printruleelement(solv, SAT_DEBUG_ANALYZE, 0, r.elements[i]);
1567 /* push end marker on learnt reasons stack */
1568 queue_push(&solv->learnt_pool, 0);
1577 * reset the solver decisions to right after the rpm rules.
1578 * called after rules have been enabled/disabled
1582 reset_solver(Solver *solv)
1584 Pool *pool = solv->pool;
1588 /* rewind decisions to direct rpm rule assertions */
1589 for (i = solv->decisionq.count - 1; i >= solv->directdecisions; i--)
1591 v = solv->decisionq.elements[i];
1592 solv->decisionmap[v > 0 ? v : -v] = 0;
1595 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "decisions done reduced from %d to %d\n", solv->decisionq.count, solv->directdecisions);
1597 solv->decisionq_why.count = solv->directdecisions;
1598 solv->decisionq.count = solv->directdecisions;
1599 solv->recommends_index = -1;
1600 solv->propagate_index = 0;
1602 /* adapt learnt rule status to new set of enabled/disabled rules */
1603 enabledisablelearntrules(solv);
1605 /* redo all job/system decisions */
1606 makeruledecisions(solv);
1607 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "decisions so far: %d\n", solv->decisionq.count);
1609 /* recreate watch chains */
1615 * analyze_unsolvable_rule
1619 analyze_unsolvable_rule(Solver *solv, Rule *r)
1621 Pool *pool = solv->pool;
1623 Id why = r - solv->rules;
1624 IF_POOLDEBUG (SAT_DEBUG_UNSOLVABLE)
1625 printruleclass(solv, SAT_DEBUG_UNSOLVABLE, r);
1626 if (solv->learntrules && why >= solv->learntrules)
1628 for (i = solv->learnt_why.elements[why - solv->learntrules]; solv->learnt_pool.elements[i]; i++)
1629 if (solv->learnt_pool.elements[i] > 0)
1630 analyze_unsolvable_rule(solv, solv->rules + solv->learnt_pool.elements[i]);
1633 /* do not add rpm rules to problem */
1634 if (why < solv->jobrules)
1636 /* turn rule into problem */
1637 if (why >= solv->jobrules && why < solv->systemrules)
1638 why = -(solv->ruletojob.elements[why - solv->jobrules] + 1);
1639 /* return if problem already countains our rule */
1640 if (solv->problems.count)
1642 for (i = solv->problems.count - 1; i >= 0; i--)
1643 if (solv->problems.elements[i] == 0) /* end of last problem reached? */
1645 else if (solv->problems.elements[i] == why)
1648 queue_push(&solv->problems, why);
1653 * analyze_unsolvable
1655 * return: 1 - disabled some rules, try again
1660 analyze_unsolvable(Solver *solv, Rule *cr, int disablerules)
1662 Pool *pool = solv->pool;
1664 Map seen; /* global to speed things up? */
1667 Id *decisionmap = solv->decisionmap;
1668 int oldproblemcount;
1669 int oldlearntpoolcount;
1672 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "ANALYZE UNSOLVABLE ----------------------\n");
1673 oldproblemcount = solv->problems.count;
1674 oldlearntpoolcount = solv->learnt_pool.count;
1676 /* make room for proof index */
1677 /* must update it later, as analyze_unsolvable_rule would confuse
1678 * it with a rule index if we put the real value in already */
1679 queue_push(&solv->problems, 0);
1682 map_init(&seen, pool->nsolvables);
1683 queue_push(&solv->learnt_pool, r - solv->rules);
1684 analyze_unsolvable_rule(solv, r);
1685 dp = r->d ? pool->whatprovidesdata + r->d : 0;
1696 if (DECISIONMAP_TRUE(v)) /* the one true literal */
1698 vv = v > 0 ? v : -v;
1699 l = solv->decisionmap[vv];
1704 idx = solv->decisionq.count;
1707 v = solv->decisionq.elements[--idx];
1708 vv = v > 0 ? v : -v;
1709 if (!MAPTST(&seen, vv))
1711 why = solv->decisionq_why.elements[idx];
1714 /* level 1 and no why, must be an rpm assertion */
1715 IF_POOLDEBUG (SAT_DEBUG_UNSOLVABLE)
1717 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "RPM ");
1718 printruleelement(solv, SAT_DEBUG_UNSOLVABLE, 0, v);
1720 /* this is the only positive rpm assertion */
1721 if (v == SYSTEMSOLVABLE)
1724 queue_push(&solv->learnt_pool, v);
1727 queue_push(&solv->learnt_pool, why);
1728 r = solv->rules + why;
1729 analyze_unsolvable_rule(solv, r);
1730 dp = r->d ? pool->whatprovidesdata + r->d : 0;
1741 if (DECISIONMAP_TRUE(v)) /* the one true literal */
1743 vv = v > 0 ? v : -v;
1744 l = solv->decisionmap[vv];
1751 queue_push(&solv->problems, 0); /* mark end of this problem */
1754 if (solv->weakrules != solv->learntrules)
1756 for (i = oldproblemcount + 1; i < solv->problems.count - 1; i++)
1758 why = solv->problems.elements[i];
1759 if (why < solv->weakrules || why >= solv->learntrules)
1761 if (!lastweak || lastweak < why)
1767 /* disable last weak rule */
1768 solv->problems.count = oldproblemcount;
1769 solv->learnt_pool.count = oldlearntpoolcount;
1770 r = solv->rules + lastweak;
1771 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "disabling weak ");
1772 printrule(solv, SAT_DEBUG_UNSOLVABLE, r);
1773 disablerule(solv, r);
1779 queue_push(&solv->learnt_pool, 0);
1780 solv->problems.elements[oldproblemcount] = oldlearntpoolcount;
1784 for (i = oldproblemcount + 1; i < solv->problems.count - 1; i++)
1785 disableproblem(solv, solv->problems.elements[i]);
1789 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "UNSOLVABLE\n");
1794 /*-----------------------------------------------------------------*/
1795 /* Decision revert */
1799 * revert decision at level
1803 revert(Solver *solv, int level)
1805 Pool *pool = solv->pool;
1807 while (solv->decisionq.count)
1809 v = solv->decisionq.elements[solv->decisionq.count - 1];
1810 vv = v > 0 ? v : -v;
1811 if (solv->decisionmap[vv] <= level && solv->decisionmap[vv] >= -level)
1813 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "reverting decision %d at %d\n", v, solv->decisionmap[vv]);
1814 solv->decisionmap[vv] = 0;
1815 solv->decisionq.count--;
1816 solv->decisionq_why.count--;
1817 solv->propagate_index = solv->decisionq.count;
1819 while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] <= -level)
1821 solv->branches.count--;
1822 while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] >= 0)
1823 solv->branches.count--;
1825 solv->recommends_index = -1;
1830 * watch2onhighest - put watch2 on literal with highest level
1834 watch2onhighest(Solver *solv, Rule *r)
1840 return; /* binary rule, both watches are set */
1841 dp = solv->pool->whatprovidesdata + r->d;
1842 while ((v = *dp++) != 0)
1844 l = solv->decisionmap[v < 0 ? -v : v];
1859 * add free decision to decisionq, increase level and
1860 * propagate decision, return if no conflict.
1861 * in conflict case, analyze conflict rule, add resulting
1862 * rule to learnt rule set, make decision from learnt
1863 * rule (always unit) and re-propagate.
1865 * returns the new solver level or 0 if unsolvable
1870 setpropagatelearn(Solver *solv, int level, Id decision, int disablerules)
1872 Pool *pool = solv->pool;
1881 solv->decisionmap[decision] = level;
1883 solv->decisionmap[-decision] = -level;
1884 queue_push(&solv->decisionq, decision);
1885 queue_push(&solv->decisionq_why, 0);
1889 r = propagate(solv, level);
1893 return analyze_unsolvable(solv, r, disablerules);
1894 POOL_DEBUG(SAT_DEBUG_ANALYZE, "conflict with rule #%d\n", (int)(r - solv->rules));
1895 l = analyze(solv, level, r, &p, &d, &why); /* learnt rule in p and d */
1896 assert(l > 0 && l < level);
1897 POOL_DEBUG(SAT_DEBUG_ANALYZE, "reverting decisions (level %d -> %d)\n", level, l);
1899 revert(solv, level);
1900 r = addrule(solv, p, d); /* p requires d */
1902 assert(solv->learnt_why.count == (r - solv->rules) - solv->learntrules);
1903 queue_push(&solv->learnt_why, why);
1906 /* at least 2 literals, needs watches */
1907 watch2onhighest(solv, r);
1908 addwatches(solv, r);
1910 solv->decisionmap[p > 0 ? p : -p] = p > 0 ? level : -level;
1911 queue_push(&solv->decisionq, p);
1912 queue_push(&solv->decisionq_why, r - solv->rules);
1913 IF_POOLDEBUG (SAT_DEBUG_ANALYZE)
1915 POOL_DEBUG(SAT_DEBUG_ANALYZE, "decision: ");
1916 printruleelement(solv, SAT_DEBUG_ANALYZE, 0, p);
1917 POOL_DEBUG(SAT_DEBUG_ANALYZE, "new rule: ");
1918 printrule(solv, SAT_DEBUG_ANALYZE, r);
1926 * install best package from the queue. We add an extra package, inst, if
1927 * provided. See comment in weak install section.
1929 * returns the new solver level or 0 if unsolvable
1933 selectandinstall(Solver *solv, int level, Queue *dq, Id inst, int disablerules)
1935 Pool *pool = solv->pool;
1939 if (dq->count > 1 || inst)
1940 policy_filter_unwanted(solv, dq, inst, POLICY_MODE_CHOOSE);
1945 /* choose the supplemented one */
1946 for (i = 0; i < dq->count; i++)
1947 if (solver_is_supplementing(solv, pool->solvables + dq->elements[i]))
1951 for (i = 1; i < dq->count; i++)
1952 queue_push(&solv->branches, dq->elements[i]);
1953 queue_push(&solv->branches, -level);
1957 p = dq->elements[i];
1959 POOL_DEBUG(SAT_DEBUG_POLICY, "installing %s\n", solvable2str(pool, pool->solvables + p));
1961 return setpropagatelearn(solv, level, p, disablerules);
1965 /*-----------------------------------------------------------------*/
1966 /* Main solver interface */
1971 * create solver structure
1973 * pool: all available solvables
1974 * installed: installed Solvables
1977 * Upon solving, rules are created to flag the Solvables
1978 * of the 'installed' Repo as installed.
1982 solver_create(Pool *pool, Repo *installed)
1985 solv = (Solver *)sat_calloc(1, sizeof(Solver));
1987 solv->installed = installed;
1989 queue_init(&solv->ruletojob);
1990 queue_init(&solv->decisionq);
1991 queue_init(&solv->decisionq_why);
1992 queue_init(&solv->problems);
1993 queue_init(&solv->suggestions);
1994 queue_init(&solv->learnt_why);
1995 queue_init(&solv->learnt_pool);
1996 queue_init(&solv->branches);
1998 map_init(&solv->recommendsmap, pool->nsolvables);
1999 map_init(&solv->suggestsmap, pool->nsolvables);
2000 map_init(&solv->noupdate, installed ? installed->end - installed->start : 0);
2001 solv->recommends_index = 0;
2003 solv->decisionmap = (Id *)sat_calloc(pool->nsolvables, sizeof(Id));
2004 solv->rules = (Rule *)sat_malloc((solv->nrules + (RULES_BLOCK + 1)) * sizeof(Rule));
2005 memset(solv->rules, 0, sizeof(Rule));
2017 solver_free(Solver *solv)
2019 queue_free(&solv->ruletojob);
2020 queue_free(&solv->decisionq);
2021 queue_free(&solv->decisionq_why);
2022 queue_free(&solv->learnt_why);
2023 queue_free(&solv->learnt_pool);
2024 queue_free(&solv->problems);
2025 queue_free(&solv->suggestions);
2026 queue_free(&solv->branches);
2028 map_free(&solv->recommendsmap);
2029 map_free(&solv->suggestsmap);
2030 map_free(&solv->noupdate);
2032 sat_free(solv->decisionmap);
2033 sat_free(solv->rules);
2034 sat_free(solv->watches);
2035 sat_free(solv->weaksystemrules);
2036 sat_free(solv->obsoletes);
2037 sat_free(solv->obsoletes_data);
2042 /*-------------------------------------------------------*/
2047 * all rules have been set up, now actually run the solver
2052 run_solver(Solver *solv, int disablerules, int doweak)
2060 Pool *pool = solv->pool;
2063 IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION)
2065 POOL_DEBUG (SAT_DEBUG_RULE_CREATION, "number of rules: %d\n", solv->nrules);
2066 for (i = 0; i < solv->nrules; i++)
2067 printrule(solv, SAT_DEBUG_RULE_CREATION, solv->rules + i);
2070 POOL_DEBUG(SAT_DEBUG_STATS, "initial decisions: %d\n", solv->decisionq.count);
2072 IF_POOLDEBUG (SAT_DEBUG_SCHUBI)
2073 printdecisions(solv);
2075 /* start SAT algorithm */
2077 systemlevel = level + 1;
2078 POOL_DEBUG(SAT_DEBUG_STATS, "solving...\n");
2089 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "propagating (propagate_index: %d; size decisionq: %d)...\n", solv->propagate_index, solv->decisionq.count);
2090 if ((r = propagate(solv, level)) != 0)
2092 if (analyze_unsolvable(solv, r, disablerules))
2100 * installed packages
2103 if (level < systemlevel && solv->installed && solv->installed->nsolvables)
2105 if (!solv->updatesystem)
2107 /* try to keep as many packages as possible */
2108 POOL_DEBUG(SAT_DEBUG_STATS, "installing system packages\n");
2109 for (i = solv->installed->start, n = 0; ; i++)
2111 if (n == solv->installed->nsolvables)
2113 if (i == solv->installed->end)
2114 i = solv->installed->start;
2115 s = pool->solvables + i;
2116 if (s->repo != solv->installed)
2119 if (solv->decisionmap[i] != 0)
2121 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "keeping %s\n", solvable2str(pool, s));
2123 level = setpropagatelearn(solv, level, i, disablerules);
2129 if (level <= olevel)
2133 if (solv->weaksystemrules)
2135 POOL_DEBUG(SAT_DEBUG_STATS, "installing weak system packages\n");
2136 for (i = solv->installed->start; i < solv->installed->end; i++)
2138 if (pool->solvables[i].repo != solv->installed)
2140 if (solv->decisionmap[i] > 0 || (solv->decisionmap[i] < 0 && solv->weaksystemrules[i - solv->installed->start] == 0))
2142 /* noupdate is set if a job is erasing the installed solvable or installing a specific version */
2143 if (MAPTST(&solv->noupdate, i - solv->installed->start))
2146 if (solv->weaksystemrules[i - solv->installed->start])
2148 dp = pool->whatprovidesdata + solv->weaksystemrules[i - solv->installed->start];
2149 while ((p = *dp++) != 0)
2151 if (solv->decisionmap[p] > 0)
2153 if (solv->decisionmap[p] == 0)
2157 continue; /* update package already installed */
2159 if (!dq.count && solv->decisionmap[i] != 0)
2162 /* FIXME: i is handled a bit different because we do not want
2163 * to have it pruned just because it is not recommened.
2164 * we should not prune installed packages instead */
2165 level = selectandinstall(solv, level, &dq, (solv->decisionmap[i] ? 0 : i), disablerules);
2171 if (level <= olevel)
2174 if (i < solv->installed->end)
2177 systemlevel = level;
2184 POOL_DEBUG(SAT_DEBUG_STATS, "deciding unresolved rules\n");
2185 for (i = 1, n = 1; ; i++, n++)
2187 if (n == solv->nrules)
2189 if (i == solv->nrules)
2191 r = solv->rules + i;
2192 if (!r->w1) /* ignore disabled rules */
2197 /* binary or unary rule */
2198 /* need two positive undecided literals */
2199 if (r->p < 0 || r->w2 <= 0)
2201 if (solv->decisionmap[r->p] || solv->decisionmap[r->w2])
2203 queue_push(&dq, r->p);
2204 queue_push(&dq, r->w2);
2209 * all negative literals are installed
2210 * no positive literal is installed
2211 * i.e. the rule is not fulfilled and we
2212 * just need to decide on the positive literals
2216 if (solv->decisionmap[-r->p] <= 0)
2221 if (solv->decisionmap[r->p] > 0)
2223 if (solv->decisionmap[r->p] == 0)
2224 queue_push(&dq, r->p);
2226 dp = pool->whatprovidesdata + r->d;
2227 while ((p = *dp++) != 0)
2231 if (solv->decisionmap[-p] <= 0)
2236 if (solv->decisionmap[p] > 0)
2238 if (solv->decisionmap[p] == 0)
2245 /* dq.count < 2 cannot happen as this means that
2246 * the rule is unit */
2247 assert(dq.count > 1);
2248 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
2250 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "unfulfilled ");
2251 printrule(solv, SAT_DEBUG_PROPAGATE, r);
2255 level = selectandinstall(solv, level, &dq, 0, disablerules);
2261 if (level < systemlevel)
2264 } /* for(), decide */
2266 if (n != solv->nrules) /* continue if level < systemlevel */
2269 if (doweak && !solv->problems.count)
2273 POOL_DEBUG(SAT_DEBUG_STATS, "installing recommended packages\n");
2274 if (!REGARD_RECOMMENDS_OF_INSTALLED_ITEMS)
2276 for (i = 0; i < solv->decisionq.count; i++)
2278 p = solv->decisionq.elements[i];
2279 if (p > 0 && pool->solvables[p].repo == solv->installed)
2280 solv->decisionmap[p] = -solv->decisionmap[p];
2284 for (i = 1; i < pool->nsolvables; i++)
2286 if (solv->decisionmap[i] < 0)
2288 if (solv->decisionmap[i] > 0)
2290 Id *recp, rec, *pp, p;
2291 s = pool->solvables + i;
2292 /* installed, check for recommends */
2293 /* XXX need to special case AND ? */
2296 recp = s->repo->idarraydata + s->recommends;
2297 while ((rec = *recp++) != 0)
2300 FOR_PROVIDES(p, pp, rec)
2302 if (solv->decisionmap[p] > 0)
2307 else if (solv->decisionmap[p] == 0)
2309 queue_pushunique(&dq, p);
2317 s = pool->solvables + i;
2318 if (!s->supplements && !s->freshens)
2320 if (!pool_installable(pool, s))
2322 if (solver_is_supplementing(solv, s))
2323 queue_pushunique(&dq, i);
2326 if (!REGARD_RECOMMENDS_OF_INSTALLED_ITEMS)
2328 for (i = 0; i < solv->decisionq.count; i++)
2330 p = solv->decisionq.elements[i];
2331 if (p > 0 && pool->solvables[p].repo == solv->installed)
2332 solv->decisionmap[p] = -solv->decisionmap[p];
2338 policy_filter_unwanted(solv, &dq, 0, POLICY_MODE_RECOMMEND);
2340 POOL_DEBUG(SAT_DEBUG_STATS, "installing recommended %s\n", solvable2str(pool, pool->solvables + p));
2341 level = setpropagatelearn(solv, level, p, 0);
2346 if (solv->solution_callback)
2348 solv->solution_callback(solv, solv->solution_callback_data);
2349 if (solv->branches.count)
2351 int i = solv->branches.count - 1;
2352 int l = -solv->branches.elements[i];
2354 if (solv->branches.elements[i - 1] < 0)
2356 p = solv->branches.elements[i];
2357 POOL_DEBUG(SAT_DEBUG_STATS, "branching with %s\n", solvable2str(pool, pool->solvables + p));
2359 for (j = i + 1; j < solv->branches.count; j++)
2360 queue_push(&dq, solv->branches.elements[j]);
2361 solv->branches.count = i;
2363 revert(solv, level);
2365 for (j = 0; j < dq.count; j++)
2366 queue_push(&solv->branches, dq.elements[j]);
2368 level = setpropagatelearn(solv, level, p, disablerules);
2376 /* all branches done, we're finally finished */
2380 /* minimization step */
2381 if (solv->branches.count)
2383 int l = 0, lasti = -1, lastl = -1;
2385 for (i = solv->branches.count - 1; i >= 0; i--)
2387 p = solv->branches.elements[i];
2390 else if (p > 0 && solv->decisionmap[p] > l + 1)
2398 /* kill old solvable so that we do not loop */
2399 p = solv->branches.elements[lasti];
2400 solv->branches.elements[lasti] = 0;
2401 POOL_DEBUG(SAT_DEBUG_STATS, "minimizing %d -> %d with %s\n", solv->decisionmap[p], l, solvable2str(pool, pool->solvables + p));
2404 revert(solv, level);
2406 level = setpropagatelearn(solv, level, p, disablerules);
2423 * at this point, all rules that led to conflicts are disabled.
2424 * we re-enable all rules of a problem set but rule "sug", then
2425 * continue to disable more rules until there as again a solution.
2428 /* FIXME: think about conflicting assertions */
2431 refine_suggestion(Solver *solv, Queue *job, Id *problem, Id sug, Queue *refined)
2433 Pool *pool = solv->pool;
2440 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
2442 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "refine_suggestion start\n");
2443 for (i = 0; problem[i]; i++)
2445 if (problem[i] == sug)
2446 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "=> ");
2447 printproblem(solv, problem[i]);
2450 queue_init(&disabled);
2451 queue_empty(refined);
2452 queue_push(refined, sug);
2454 /* re-enable all problem rules with the exception of "sug" */
2458 for (i = 0; problem[i]; i++)
2459 if (problem[i] != sug)
2460 enableproblem(solv, problem[i]);
2463 disableupdaterules(solv, job, -(sug + 1));
2467 /* re-enable as many weak rules as possible */
2468 for (i = solv->weakrules; i < solv->learntrules; i++)
2470 r = solv->rules + i;
2472 enablerule(solv, r);
2475 queue_empty(&solv->problems);
2476 revert(solv, 1); /* XXX move to reset_solver? */
2479 if (!solv->problems.count)
2480 run_solver(solv, 0, 0);
2482 if (!solv->problems.count)
2484 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "no more problems!\n");
2485 IF_POOLDEBUG (SAT_DEBUG_SCHUBI)
2486 printdecisions(solv);
2487 break; /* great, no more problems */
2489 disabledcnt = disabled.count;
2490 /* start with 1 to skip over proof index */
2491 for (i = 1; i < solv->problems.count - 1; i++)
2493 /* ignore solutions in refined */
2494 v = solv->problems.elements[i];
2496 break; /* end of problem reached */
2497 for (j = 0; problem[j]; j++)
2498 if (problem[j] != sug && problem[j] == v)
2502 queue_push(&disabled, v);
2504 if (disabled.count == disabledcnt)
2506 /* no solution found, this was an invalid suggestion! */
2507 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "no solution found!\n");
2511 if (disabled.count == disabledcnt + 1)
2513 /* just one suggestion, add it to refined list */
2514 v = disabled.elements[disabledcnt];
2515 queue_push(refined, v);
2516 disableproblem(solv, v);
2518 disableupdaterules(solv, job, -(v + 1));
2522 /* more than one solution, disable all */
2523 /* do not push anything on refine list */
2524 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
2526 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "more than one solution found:\n");
2527 for (i = disabledcnt; i < disabled.count; i++)
2528 printproblem(solv, disabled.elements[i]);
2530 for (i = disabledcnt; i < disabled.count; i++)
2531 disableproblem(solv, disabled.elements[i]);
2534 /* all done, get us back into the same state as before */
2535 /* enable refined rules again */
2536 for (i = 0; i < disabled.count; i++)
2537 enableproblem(solv, disabled.elements[i]);
2538 /* disable problem rules again */
2539 for (i = 0; problem[i]; i++)
2540 disableproblem(solv, problem[i]);
2541 disableupdaterules(solv, job, -1);
2542 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "refine_suggestion end\n");
2546 problems_to_solutions(Solver *solv, Queue *job)
2548 Pool *pool = solv->pool;
2556 if (!solv->problems.count)
2558 queue_clone(&problems, &solv->problems);
2559 queue_init(&solution);
2560 queue_init(&solutions);
2561 /* copy over proof index */
2562 queue_push(&solutions, problems.elements[0]);
2563 problem = problems.elements + 1;
2564 for (i = 1; i < problems.count; i++)
2566 Id v = problems.elements[i];
2569 /* mark end of this problem */
2570 queue_push(&solutions, 0);
2571 queue_push(&solutions, 0);
2572 if (i + 1 == problems.count)
2574 /* copy over proof of next problem */
2575 queue_push(&solutions, problems.elements[i + 1]);
2577 problem = problems.elements + i + 1;
2580 refine_suggestion(solv, job, problem, v, &solution);
2581 if (!solution.count)
2582 continue; /* this solution didn't work out */
2584 for (j = 0; j < solution.count; j++)
2586 why = solution.elements[j];
2587 /* must be either job descriptor or system rule */
2588 assert(why < 0 || (why >= solv->systemrules && why < solv->weakrules));
2590 printproblem(solv, why);
2594 /* job descriptor */
2595 queue_push(&solutions, 0);
2596 queue_push(&solutions, -why);
2600 /* system rule, find replacement package */
2602 p = solv->installed->start + (why - solv->systemrules);
2603 if (solv->weaksystemrules && solv->weaksystemrules[why - solv->systemrules])
2605 Id *dp = pool->whatprovidesdata + solv->weaksystemrules[why - solv->systemrules];
2608 if (*dp >= solv->installed->start && *dp < solv->installed->start + solv->installed->nsolvables)
2610 if (solv->decisionmap[*dp] > 0)
2617 queue_push(&solutions, p);
2618 queue_push(&solutions, rp);
2621 /* mark end of this solution */
2622 queue_push(&solutions, 0);
2623 queue_push(&solutions, 0);
2625 queue_free(&solution);
2626 queue_free(&problems);
2627 /* copy queue over to solutions */
2628 queue_free(&solv->problems);
2629 queue_clone(&solv->problems, &solutions);
2631 /* bring solver back into problem state */
2632 revert(solv, 1); /* XXX move to reset_solver? */
2635 assert(solv->problems.count == solutions.count);
2636 queue_free(&solutions);
2640 solver_next_problem(Solver *solv, Id problem)
2644 return solv->problems.count ? 1 : 0;
2645 pp = solv->problems.elements + problem;
2646 while (pp[0] || pp[1])
2650 while (pp[0] || pp[1])
2655 problem = pp - solv->problems.elements;
2656 if (problem >= solv->problems.count)
2662 solver_next_solution(Solver *solv, Id problem, Id solution)
2668 pp = solv->problems.elements + solution;
2669 return pp[0] || pp[1] ? solution : 0;
2671 pp = solv->problems.elements + solution;
2672 while (pp[0] || pp[1])
2675 solution = pp - solv->problems.elements;
2676 return pp[0] || pp[1] ? solution : 0;
2680 solver_next_solutionelement(Solver *solv, Id problem, Id solution, Id element, Id *p, Id *rp)
2683 element = element ? element + 2 : solution;
2684 pp = solv->problems.elements + element;
2685 if (!(pp[0] || pp[1]))
2694 * create obsoletesmap from solver decisions
2695 * required for decision handling
2699 create_obsoletesmap(Solver *solv)
2701 Pool *pool = solv->pool;
2702 Repo *installed = solv->installed;
2703 Id p, *obsoletesmap = NULL;
2707 obsoletesmap = (Id *)sat_calloc(pool->nsolvables, sizeof(Id));
2710 for (i = 0; i < solv->decisionq.count; i++)
2714 n = solv->decisionq.elements[i];
2717 if (n == SYSTEMSOLVABLE)
2719 s = pool->solvables + n;
2720 if (s->repo == installed) /* obsoletes don't count for already installed packages */
2722 FOR_PROVIDES(p, pp, s->name)
2723 if (s->name == pool->solvables[p].name)
2725 if (pool->solvables[p].repo == installed && !obsoletesmap[p])
2727 obsoletesmap[p] = n;
2732 for (i = 0; i < solv->decisionq.count; i++)
2737 n = solv->decisionq.elements[i];
2740 if (n == SYSTEMSOLVABLE)
2742 s = pool->solvables + n;
2743 if (s->repo == installed) /* obsoletes don't count for already installed packages */
2747 obsp = s->repo->idarraydata + s->obsoletes;
2748 while ((obs = *obsp++) != 0)
2749 FOR_PROVIDES(p, pp, obs)
2751 if (pool->solvables[p].repo == installed && !obsoletesmap[p])
2753 obsoletesmap[p] = n;
2759 return obsoletesmap;
2768 printdecisions(Solver *solv)
2770 Pool *pool = solv->pool;
2771 Repo *installed = solv->installed;
2772 Id p, *obsoletesmap = create_obsoletesmap( solv );
2776 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- Decisions -----\n");
2778 /* print solvables to be erased */
2782 FOR_REPO_SOLVABLES(installed, p, s)
2784 if (solv->decisionmap[p] >= 0)
2786 if (obsoletesmap[p])
2788 POOL_DEBUG(SAT_DEBUG_RESULT, "erase %s\n", solvable2str(pool, s));
2792 /* print solvables to be installed */
2794 for (i = 0; i < solv->decisionq.count; i++)
2797 p = solv->decisionq.elements[i];
2800 IF_POOLDEBUG (SAT_DEBUG_SCHUBI)
2803 s = pool->solvables + p;
2804 POOL_DEBUG(SAT_DEBUG_SCHUBI, "level of %s is %d\n", solvable2str(pool, s), p);
2808 if (p == SYSTEMSOLVABLE)
2810 POOL_DEBUG(SAT_DEBUG_SCHUBI, "SYSTEMSOLVABLE\n");
2813 s = pool->solvables + p;
2814 if (installed && s->repo == installed)
2817 if (!obsoletesmap[p])
2819 POOL_DEBUG(SAT_DEBUG_RESULT, "install %s", solvable2str(pool, s));
2823 POOL_DEBUG(SAT_DEBUG_RESULT, "update %s", solvable2str(pool, s));
2824 POOL_DEBUG(SAT_DEBUG_RESULT, " (obsoletes");
2825 for (j = installed->start; j < installed->end; j++)
2826 if (obsoletesmap[j] == p)
2827 POOL_DEBUG(SAT_DEBUG_RESULT, " %s", solvable2str(pool, pool->solvables + j));
2828 POOL_DEBUG(SAT_DEBUG_RESULT, ")");
2830 POOL_DEBUG(SAT_DEBUG_RESULT, "\n");
2833 sat_free(obsoletesmap);
2835 if (solv->suggestions.count)
2837 POOL_DEBUG(SAT_DEBUG_RESULT, "\nsuggested packages:\n");
2838 for (i = 0; i < solv->suggestions.count; i++)
2840 s = pool->solvables + solv->suggestions.elements[i];
2841 POOL_DEBUG(SAT_DEBUG_RESULT, "- %s\n", solvable2str(pool, s));
2844 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- Decisions end -----\n");
2847 /* this is basically the reverse of addrpmrulesforsolvable */
2849 solver_problemruleinfo(Solver *solv, Queue *job, Id rid, Id *depp, Id *sourcep, Id *targetp)
2851 Pool *pool = solv->pool;
2852 Repo *installed = solv->installed;
2856 Id p, *pp, req, *reqp, con, *conp, obs, *obsp, *dp;
2858 assert(rid < solv->weakrules);
2859 if (rid >= solv->systemrules)
2862 *sourcep = solv->installed->start + (rid - solv->systemrules);
2864 return SOLVER_PROBLEM_UPDATE_RULE;
2866 if (rid >= solv->jobrules)
2869 r = solv->rules + rid;
2870 p = solv->ruletojob.elements[rid - solv->jobrules];
2871 *depp = job->elements[p + 1];
2873 *targetp = job->elements[p];
2874 if (r->d == 0 && r->w2 == 0 && r->p == -SYSTEMSOLVABLE)
2875 return SOLVER_PROBLEM_JOB_NOTHING_PROVIDES_DEP;
2876 return SOLVER_PROBLEM_JOB_RULE;
2880 /* a rpm rule assertion */
2881 assert(rid != -SYSTEMSOLVABLE);
2882 s = pool->solvables - rid;
2883 if (installed && !solv->fixsystem && s->repo == installed)
2885 assert(!dontfix); /* dontfix packages never have a neg assertion */
2886 /* see why the package is not installable */
2887 if (s->arch != ARCH_SRC && s->arch != ARCH_NOSRC && !pool_installable(pool, s))
2888 return SOLVER_PROBLEM_NOT_INSTALLABLE;
2889 /* check requires */
2890 assert(s->requires);
2891 reqp = s->repo->idarraydata + s->requires;
2892 while ((req = *reqp++) != 0)
2894 if (req == SOLVABLE_PREREQMARKER)
2896 dp = pool_whatprovides(pool, req);
2904 return SOLVER_PROBLEM_NOTHING_PROVIDES_DEP;
2906 r = solv->rules + rid;
2908 if (r->d == 0 && r->w2 == 0)
2910 /* an assertion. we don't store them as rpm rules, so
2914 s = pool->solvables - r->p;
2915 if (installed && !solv->fixsystem && s->repo == installed)
2917 if (r->d == 0 && r->w2 < 0)
2919 /* a package conflict */
2920 Solvable *s2 = pool->solvables - r->w2;
2923 if (installed && !solv->fixsystem && s2->repo == installed)
2926 /* if both packages have the same name and at least one of them
2927 * is not installed, they conflict */
2928 if (s->name == s2->name && (!installed || (s->repo != installed || s2->repo != installed)))
2933 return SOLVER_PROBLEM_SAME_NAME;
2936 /* check conflicts in both directions */
2939 conp = s->repo->idarraydata + s->conflicts;
2940 while ((con = *conp++) != 0)
2942 FOR_PROVIDES(p, pp, con)
2944 if (dontfix && pool->solvables[p].repo == installed)
2951 return SOLVER_PROBLEM_PACKAGE_CONFLICT;
2957 conp = s2->repo->idarraydata + s2->conflicts;
2958 while ((con = *conp++) != 0)
2960 FOR_PROVIDES(p, pp, con)
2962 if (dontfix2 && pool->solvables[p].repo == installed)
2969 return SOLVER_PROBLEM_PACKAGE_CONFLICT;
2973 /* check obsoletes in both directions */
2974 if ((!installed || s->repo != installed) && s->obsoletes)
2976 obsp = s->repo->idarraydata + s->obsoletes;
2977 while ((obs = *obsp++) != 0)
2979 FOR_PROVIDES(p, pp, obs)
2986 return SOLVER_PROBLEM_PACKAGE_OBSOLETES;
2990 if ((!installed || s2->repo != installed) && s2->obsoletes)
2992 obsp = s2->repo->idarraydata + s2->obsoletes;
2993 while ((obs = *obsp++) != 0)
2995 FOR_PROVIDES(p, pp, obs)
3002 return SOLVER_PROBLEM_PACKAGE_OBSOLETES;
3006 /* all cases checked, can't happen */
3009 /* simple requires */
3010 assert(s->requires);
3011 reqp = s->repo->idarraydata + s->requires;
3012 while ((req = *reqp++) != 0)
3014 if (req == SOLVABLE_PREREQMARKER)
3016 dp = pool_whatprovides(pool, req);
3019 if (*dp == r->w2 && dp[1] == 0)
3022 else if (dp - pool->whatprovidesdata == r->d)
3029 return SOLVER_PROBLEM_DEP_PROVIDERS_NOT_INSTALLABLE;
3033 findproblemrule_internal(Solver *solv, Id idx, Id *reqrp, Id *conrp, Id *sysrp, Id *jobrp)
3036 Id lreqr, lconr, lsysr, ljobr;
3040 lreqr = lconr = lsysr = ljobr = 0;
3041 while ((rid = solv->learnt_pool.elements[idx++]) != 0)
3043 if (rid >= solv->learntrules)
3044 findproblemrule_internal(solv, solv->learnt_why.elements[rid - solv->learntrules], &lreqr, &lconr, &lsysr, &ljobr);
3045 else if (rid >= solv->systemrules)
3050 else if (rid >= solv->jobrules)
3057 r = solv->rules + rid;
3058 if (!r->d && r->w2 < 0)
3071 /* assertion, counts as require rule */
3072 /* ignore system solvable as we need useful info */
3073 if (rid == -SYSTEMSOLVABLE)
3075 if (!*reqrp || !reqassert)
3082 if (!*reqrp && lreqr)
3084 if (!*conrp && lconr)
3086 if (!*jobrp && ljobr)
3088 if (!*sysrp && lsysr)
3093 solver_findproblemrule(Solver *solv, Id problem)
3095 Id reqr, conr, sysr, jobr;
3096 Id idx = solv->problems.elements[problem - 1];
3097 reqr = conr = sysr = jobr = 0;
3098 findproblemrule_internal(solv, idx, &reqr, &conr, &sysr, &jobr);
3111 printprobleminfo(Solver *solv, Queue *job, Id problem)
3113 Pool *pool = solv->pool;
3115 Id dep, source, target;
3118 probr = solver_findproblemrule(solv, problem);
3119 switch (solver_problemruleinfo(solv, job, probr, &dep, &source, &target))
3121 case SOLVER_PROBLEM_UPDATE_RULE:
3122 s = pool_id2solvable(pool, source);
3123 POOL_DEBUG(SAT_DEBUG_RESULT, "problem with installed package %s\n", solvable2str(pool, s));
3125 case SOLVER_PROBLEM_JOB_RULE:
3126 POOL_DEBUG(SAT_DEBUG_RESULT, "conflicting requests\n");
3128 case SOLVER_PROBLEM_JOB_NOTHING_PROVIDES_DEP:
3129 POOL_DEBUG(SAT_DEBUG_RESULT, "nothing provides requested %s\n", dep2str(pool, dep));
3131 case SOLVER_PROBLEM_NOT_INSTALLABLE:
3132 s = pool_id2solvable(pool, source);
3133 POOL_DEBUG(SAT_DEBUG_RESULT, "package %s is not installable\n", solvable2str(pool, s));
3135 case SOLVER_PROBLEM_NOTHING_PROVIDES_DEP:
3136 s = pool_id2solvable(pool, source);
3137 POOL_DEBUG(SAT_DEBUG_RESULT, "nothing provides %s needed by %s\n", dep2str(pool, dep), solvable2str(pool, s));
3139 case SOLVER_PROBLEM_SAME_NAME:
3140 s = pool_id2solvable(pool, source);
3141 s2 = pool_id2solvable(pool, target);
3142 POOL_DEBUG(SAT_DEBUG_RESULT, "cannot install both %s and %s\n", solvable2str(pool, s), solvable2str(pool, s2));
3144 case SOLVER_PROBLEM_PACKAGE_CONFLICT:
3145 s = pool_id2solvable(pool, source);
3146 s2 = pool_id2solvable(pool, target);
3147 POOL_DEBUG(SAT_DEBUG_RESULT, "package %s conflicts with %s provided by %s\n", solvable2str(pool, s), dep2str(pool, dep), solvable2str(pool, s2));
3149 case SOLVER_PROBLEM_PACKAGE_OBSOLETES:
3150 s = pool_id2solvable(pool, source);
3151 s2 = pool_id2solvable(pool, target);
3152 POOL_DEBUG(SAT_DEBUG_RESULT, "package %s obsoletes %s provided by %s\n", solvable2str(pool, s), dep2str(pool, dep), solvable2str(pool, s2));
3154 case SOLVER_PROBLEM_DEP_PROVIDERS_NOT_INSTALLABLE:
3155 s = pool_id2solvable(pool, source);
3156 POOL_DEBUG(SAT_DEBUG_RESULT, "package %s requires %s, but none of the providers can be installed\n", solvable2str(pool, s), dep2str(pool, dep));
3162 printsolutions(Solver *solv, Queue *job)
3164 Pool *pool = solv->pool;
3167 Id problem, solution, element;
3170 POOL_DEBUG(SAT_DEBUG_RESULT, "Encountered problems! Here are the solutions:\n\n");
3173 while ((problem = solver_next_problem(solv, problem)) != 0)
3175 POOL_DEBUG(SAT_DEBUG_RESULT, "Problem %d:\n", pcnt++);
3176 POOL_DEBUG(SAT_DEBUG_RESULT, "====================================\n");
3177 printprobleminfo(solv, job, problem);
3178 POOL_DEBUG(SAT_DEBUG_RESULT, "\n");
3180 while ((solution = solver_next_solution(solv, problem, solution)) != 0)
3183 while ((element = solver_next_solutionelement(solv, problem, solution, element, &p, &rp)) != 0)
3187 /* job, rp is index into job queue */
3188 what = job->elements[rp];
3189 switch (job->elements[rp - 1])
3191 case SOLVER_INSTALL_SOLVABLE:
3192 s = pool->solvables + what;
3193 if (solv->installed && s->repo == solv->installed)
3194 POOL_DEBUG(SAT_DEBUG_RESULT, "- do not keep %s installed\n", solvable2str(pool, s));
3196 POOL_DEBUG(SAT_DEBUG_RESULT, "- do not install %s\n", solvable2str(pool, s));
3198 case SOLVER_ERASE_SOLVABLE:
3199 s = pool->solvables + what;
3200 if (solv->installed && s->repo == solv->installed)
3201 POOL_DEBUG(SAT_DEBUG_RESULT, "- do not deinstall %s\n", solvable2str(pool, s));
3203 POOL_DEBUG(SAT_DEBUG_RESULT, "- do not forbid installation of %s\n", solvable2str(pool, s));
3205 case SOLVER_INSTALL_SOLVABLE_NAME:
3206 POOL_DEBUG(SAT_DEBUG_RESULT, "- do not install %s\n", id2str(pool, what));
3208 case SOLVER_ERASE_SOLVABLE_NAME:
3209 POOL_DEBUG(SAT_DEBUG_RESULT, "- do not deinstall %s\n", id2str(pool, what));
3211 case SOLVER_INSTALL_SOLVABLE_PROVIDES:
3212 POOL_DEBUG(SAT_DEBUG_RESULT, "- do not install a solvable providing %s\n", dep2str(pool, what));
3214 case SOLVER_ERASE_SOLVABLE_PROVIDES:
3215 POOL_DEBUG(SAT_DEBUG_RESULT, "- do not deinstall all solvables providing %s\n", dep2str(pool, what));
3217 case SOLVER_INSTALL_SOLVABLE_UPDATE:
3218 s = pool->solvables + what;
3219 POOL_DEBUG(SAT_DEBUG_RESULT, "- do not install most recent version of %s\n", solvable2str(pool, s));
3222 POOL_DEBUG(SAT_DEBUG_RESULT, "- do something different\n");
3228 /* policy, replace p with rp */
3229 s = pool->solvables + p;
3230 sd = rp ? pool->solvables + rp : 0;
3234 if (!solv->allowdowngrade && evrcmp(pool, s->evr, sd->evr, EVRCMP_MATCH_RELEASE) > 0)
3236 POOL_DEBUG(SAT_DEBUG_RESULT, "- allow downgrade of %s to %s\n", solvable2str(pool, s), solvable2str(pool, sd));
3239 if (!solv->allowarchchange && s->name == sd->name && s->arch != sd->arch && policy_illegal_archchange(pool, s, sd))
3241 POOL_DEBUG(SAT_DEBUG_RESULT, "- allow architecture change of %s to %s\n", solvable2str(pool, s), solvable2str(pool, sd));
3244 if (!solv->allowvendorchange && s->name == sd->name && s->vendor != sd->vendor && policy_illegal_vendorchange(pool, s, sd))
3247 POOL_DEBUG(SAT_DEBUG_RESULT, "- allow vendor change from '%s' (%s) to '%s' (%s)\n", id2str(pool, s->vendor), solvable2str(pool, s), id2str(pool, sd->vendor), solvable2str(pool, sd));
3249 POOL_DEBUG(SAT_DEBUG_RESULT, "- allow vendor change from '%s' (%s) to no vendor (%s)\n", id2str(pool, s->vendor), solvable2str(pool, s), solvable2str(pool, sd));
3253 POOL_DEBUG(SAT_DEBUG_RESULT, "- allow replacement of %s with %s\n", solvable2str(pool, s), solvable2str(pool, sd));
3257 POOL_DEBUG(SAT_DEBUG_RESULT, "- allow deinstallation of %s\n", solvable2str(pool, s));
3262 POOL_DEBUG(SAT_DEBUG_RESULT, "\n");
3268 /* for each installed solvable find which packages with *different* names
3269 * obsolete the solvable.
3270 * this index is used in policy_findupdatepackages if noupdateprovide is set.
3274 create_obsolete_index(Solver *solv)
3276 Pool *pool = solv->pool;
3278 Repo *installed = solv->installed;
3279 Id p, *pp, obs, *obsp, *obsoletes, *obsoletes_data;
3282 if (!installed || !installed->nsolvables)
3284 /* create reverse obsoletes map for installed solvables */
3285 solv->obsoletes = obsoletes = sat_calloc(installed->end - installed->start, sizeof(Id));
3286 for (i = 1; i < pool->nsolvables; i++)
3288 s = pool->solvables + i;
3289 if (s->repo == installed)
3293 if (!pool_installable(pool, s))
3295 obsp = s->repo->idarraydata + s->obsoletes;
3296 while ((obs = *obsp++) != 0)
3297 FOR_PROVIDES(p, pp, obs)
3299 if (pool->solvables[p].repo != installed)
3301 if (pool->solvables[p].name == s->name)
3303 obsoletes[p - installed->start]++;
3307 for (i = 0; i < installed->nsolvables; i++)
3310 n += obsoletes[i] + 1;
3313 solv->obsoletes_data = obsoletes_data = sat_calloc(n + 1, sizeof(Id));
3314 POOL_DEBUG(SAT_DEBUG_STATS, "obsoletes data: %d entries\n", n + 1);
3315 for (i = pool->nsolvables - 1; i > 0; i--)
3317 s = pool->solvables + i;
3318 if (s->repo == installed)
3322 if (!pool_installable(pool, s))
3324 obsp = s->repo->idarraydata + s->obsoletes;
3325 while ((obs = *obsp++) != 0)
3326 FOR_PROVIDES(p, pp, obs)
3328 if (pool->solvables[p].repo != installed)
3330 if (pool->solvables[p].name == s->name)
3332 p -= installed->start;
3333 if (obsoletes_data[obsoletes[p]] != i)
3334 obsoletes_data[--obsoletes[p]] = i;
3340 /*-----------------------------------------------------------------*/
3350 solver_solve(Solver *solv, Queue *job)
3352 Pool *pool = solv->pool;
3353 Repo *installed = solv->installed;
3356 Map addedmap; /* '1' == have rpm-rules for solvable */
3357 Id how, what, p, *pp, d;
3361 /* create whatprovides if not already there */
3362 if (!pool->whatprovides)
3363 pool_createwhatprovides(pool);
3365 /* create obsolete index if needed */
3366 if (solv->noupdateprovide)
3367 create_obsolete_index(solv);
3370 * create basic rule set of all involved packages
3371 * use addedmap bitmap to make sure we don't create rules twice
3375 map_init(&addedmap, pool->nsolvables);
3379 * always install our system solvable
3381 MAPSET(&addedmap, SYSTEMSOLVABLE);
3382 queue_push(&solv->decisionq, SYSTEMSOLVABLE);
3383 queue_push(&solv->decisionq_why, 0);
3384 solv->decisionmap[SYSTEMSOLVABLE] = 1;
3387 * create rules for all package that could be involved with the solving
3388 * so called: rpm rules
3393 oldnrules = solv->nrules;
3394 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for installed solvables ***\n");
3395 FOR_REPO_SOLVABLES(installed, p, s)
3396 addrpmrulesforsolvable(solv, s, &addedmap);
3397 POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for installed solvables\n", solv->nrules - oldnrules);
3398 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for updaters of installed solvables ***\n");
3399 oldnrules = solv->nrules;
3400 FOR_REPO_SOLVABLES(installed, p, s)
3401 addrpmrulesforupdaters(solv, s, &addedmap, 1);
3402 POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for updaters of installed solvables\n", solv->nrules - oldnrules);
3405 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for packages involved with a job ***\n");
3406 oldnrules = solv->nrules;
3407 for (i = 0; i < job->count; i += 2)
3409 how = job->elements[i];
3410 what = job->elements[i + 1];
3414 case SOLVER_INSTALL_SOLVABLE:
3415 addrpmrulesforsolvable(solv, pool->solvables + what, &addedmap);
3417 case SOLVER_INSTALL_SOLVABLE_NAME:
3418 case SOLVER_INSTALL_SOLVABLE_PROVIDES:
3419 FOR_PROVIDES(p, pp, what)
3421 /* if by name, ensure that the name matches */
3422 if (how == SOLVER_INSTALL_SOLVABLE_NAME && pool->solvables[p].name != what)
3424 addrpmrulesforsolvable(solv, pool->solvables + p, &addedmap);
3427 case SOLVER_INSTALL_SOLVABLE_UPDATE:
3428 /* dont allow downgrade */
3429 addrpmrulesforupdaters(solv, pool->solvables + what, &addedmap, 0);
3433 POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for packages involved in a job\n", solv->nrules - oldnrules);
3435 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for recommended/suggested packages ***\n");
3437 oldnrules = solv->nrules;
3438 addrpmrulesforweak(solv, &addedmap);
3439 POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules because of weak dependencies\n", solv->nrules - oldnrules);
3441 IF_POOLDEBUG (SAT_DEBUG_STATS)
3443 int possible = 0, installable = 0;
3444 for (i = 1; i < pool->nsolvables; i++)
3446 if (pool_installable(pool, pool->solvables + i))
3448 if (MAPTST(&addedmap, i))
3451 POOL_DEBUG(SAT_DEBUG_STATS, "%d of %d installable solvables considered for solving (rules has been generated for)\n", possible, installable);
3455 * first pass done, we now have all the rpm rules we need.
3456 * unify existing rules before going over all job rules and
3458 * at this point the system is always solvable,
3459 * as an empty system (remove all packages) is a valid solution
3462 unifyrules(solv); /* remove duplicate rpm rules */
3463 solv->directdecisions = solv->decisionq.count;
3465 POOL_DEBUG(SAT_DEBUG_STATS, "decisions so far: %d\n", solv->decisionq.count);
3466 IF_POOLDEBUG (SAT_DEBUG_SCHUBI)
3467 printdecisions (solv);
3470 * now add all job rules
3473 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** Add JOB rules ***\n");
3475 solv->jobrules = solv->nrules;
3477 for (i = 0; i < job->count; i += 2)
3479 oldnrules = solv->nrules;
3481 how = job->elements[i];
3482 what = job->elements[i + 1];
3485 case SOLVER_INSTALL_SOLVABLE: /* install specific solvable */
3486 s = pool->solvables + what;
3487 POOL_DEBUG(SAT_DEBUG_JOB, "job: install solvable %s\n", solvable2str(pool, s));
3488 addrule(solv, what, 0); /* install by Id */
3489 queue_push(&solv->ruletojob, i);
3491 case SOLVER_ERASE_SOLVABLE:
3492 s = pool->solvables + what;
3493 POOL_DEBUG(SAT_DEBUG_JOB, "job: erase solvable %s\n", solvable2str(pool, s));
3494 addrule(solv, -what, 0); /* remove by Id */
3495 queue_push(&solv->ruletojob, i);
3497 case SOLVER_INSTALL_SOLVABLE_NAME: /* install by capability */
3498 case SOLVER_INSTALL_SOLVABLE_PROVIDES:
3499 if (how == SOLVER_INSTALL_SOLVABLE_NAME)
3500 POOL_DEBUG(SAT_DEBUG_JOB, "job: install name %s\n", id2str(pool, what));
3501 if (how == SOLVER_INSTALL_SOLVABLE_PROVIDES)
3502 POOL_DEBUG(SAT_DEBUG_JOB, "job: install provides %s\n", dep2str(pool, what));
3504 FOR_PROVIDES(p, pp, what)
3506 /* if by name, ensure that the name matches */
3507 if (how == SOLVER_INSTALL_SOLVABLE_NAME && pool->solvables[p].name != what)
3513 /* no provider, make this an impossible rule */
3514 queue_push(&q, -SYSTEMSOLVABLE);
3517 p = queue_shift(&q); /* get first provider */
3519 d = 0; /* single provider ? -> make assertion */
3521 d = pool_queuetowhatprovides(pool, &q); /* get all providers */
3522 addrule(solv, p, d); /* add 'requires' rule */
3523 queue_push(&solv->ruletojob, i);
3525 case SOLVER_ERASE_SOLVABLE_NAME: /* remove by capability */
3526 case SOLVER_ERASE_SOLVABLE_PROVIDES:
3527 if (how == SOLVER_ERASE_SOLVABLE_NAME)
3528 POOL_DEBUG(SAT_DEBUG_JOB, "job: erase name %s\n", id2str(pool, what));
3529 if (how == SOLVER_ERASE_SOLVABLE_PROVIDES)
3530 POOL_DEBUG(SAT_DEBUG_JOB, "job: erase provides %s\n", dep2str(pool, what));
3531 FOR_PROVIDES(p, pp, what)
3533 /* if by name, ensure that the name matches */
3534 if (how == SOLVER_ERASE_SOLVABLE_NAME && pool->solvables[p].name != what)
3536 addrule(solv, -p, 0); /* add 'remove' rule */
3537 queue_push(&solv->ruletojob, i);
3540 case SOLVER_INSTALL_SOLVABLE_UPDATE: /* find update for solvable */
3541 s = pool->solvables + what;
3542 POOL_DEBUG(SAT_DEBUG_JOB, "job: update %s\n", solvable2str(pool, s));
3543 addupdaterule(solv, s, 0);
3544 queue_push(&solv->ruletojob, i);
3547 IF_POOLDEBUG (SAT_DEBUG_JOB)
3550 if (solv->nrules == oldnrules)
3551 POOL_DEBUG(SAT_DEBUG_JOB, " - no rule created");
3552 for (j = oldnrules; j < solv->nrules; j++)
3554 POOL_DEBUG(SAT_DEBUG_JOB, " - job ");
3555 printrule(solv, SAT_DEBUG_JOB, solv->rules + j);
3559 assert(solv->ruletojob.count == solv->nrules - solv->jobrules);
3562 * now add system rules
3566 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** Add system rules ***\n");
3569 solv->systemrules = solv->nrules;
3572 * create rules for updating installed solvables
3576 if (installed && !solv->allowuninstall)
3577 { /* loop over all installed solvables */
3578 /* we create all update rules, but disable some later on depending on the job */
3579 for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
3580 if (s->repo == installed)
3581 addupdaterule(solv, s, 0); /* allowall = 0 */
3583 addupdaterule(solv, 0, 0); /* create dummy rule; allowall = 0 */
3584 /* consistency check: we added a rule for _every_ system solvable */
3585 assert(solv->nrules - solv->systemrules == installed->end - installed->start);
3588 /* create special weak system rules */
3589 /* those are used later on to keep a version of the installed packages in
3591 if (installed && installed->nsolvables)
3593 solv->weaksystemrules = sat_calloc(installed->end - installed->start, sizeof(Id));
3594 FOR_REPO_SOLVABLES(installed, p, s)
3596 policy_findupdatepackages(solv, s, &q, 1);
3598 solv->weaksystemrules[p - installed->start] = pool_queuetowhatprovides(pool, &q);
3602 /* free unneeded memory */
3603 map_free(&addedmap);
3606 solv->weakrules = solv->nrules;
3608 /* try real hard to keep packages installed */
3611 FOR_REPO_SOLVABLES(installed, p, s)
3613 /* FIXME: can't work with refine_suggestion! */
3614 /* need to always add the rule but disable it */
3615 if (MAPTST(&solv->noupdate, p - installed->start))
3617 d = solv->weaksystemrules[p - installed->start];
3618 addrule(solv, p, d);
3622 /* all new rules are learnt after this point */
3623 solv->learntrules = solv->nrules;
3625 /* disable system rules that conflict with our job */
3626 disableupdaterules(solv, job, -1);
3628 /* make decisions based on job/system assertions */
3629 makeruledecisions(solv);
3631 /* create watches chains */
3634 POOL_DEBUG(SAT_DEBUG_STATS, "problems so far: %d\n", solv->problems.count);
3637 run_solver(solv, 1, 1);
3639 /* find suggested packages */
3640 if (!solv->problems.count)
3642 Id sug, *sugp, p, *pp;
3644 /* create map of all suggests that are still open */
3645 solv->recommends_index = -1;
3646 MAPZERO(&solv->suggestsmap);
3647 for (i = 0; i < solv->decisionq.count; i++)
3649 p = solv->decisionq.elements[i];
3652 s = pool->solvables + p;
3655 sugp = s->repo->idarraydata + s->suggests;
3656 while ((sug = *sugp++) != 0)
3658 FOR_PROVIDES(p, pp, sug)
3659 if (solv->decisionmap[p] > 0)
3662 continue; /* already fulfilled */
3663 FOR_PROVIDES(p, pp, sug)
3664 MAPSET(&solv->suggestsmap, p);
3668 for (i = 1; i < pool->nsolvables; i++)
3670 if (solv->decisionmap[i] != 0)
3672 s = pool->solvables + i;
3673 if (!MAPTST(&solv->suggestsmap, i))
3677 if (!pool_installable(pool, s))
3679 if (!solver_is_enhancing(solv, s))
3682 queue_push(&solv->suggestions, i);
3684 policy_filter_unwanted(solv, &solv->suggestions, 0, POLICY_MODE_SUGGEST);
3687 if (solv->problems.count)
3688 problems_to_solutions(solv, job);