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
26 #include "solverdebug.h"
30 #define RULES_BLOCK 63
32 /********************************************************************
34 * dependency check helpers
39 solver_splitprovides(Solver *solv, Id dep)
41 Pool *pool = solv->pool;
46 if (!solv->dosplitprovides || !solv->installed)
50 rd = GETRELDEP(pool, dep);
51 if (rd->flags != REL_WITH)
53 FOR_PROVIDES(p, pp, dep)
55 s = pool->solvables + p;
56 if (s->repo == solv->installed && s->name == rd->name)
63 solver_dep_installed(Solver *solv, Id dep)
66 Pool *pool = solv->pool;
71 Reldep *rd = GETRELDEP(pool, dep);
72 if (rd->flags == REL_AND)
74 if (!solver_dep_installed(solv, rd->name))
76 return solver_dep_installed(solv, rd->evr);
78 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
79 return solver_dep_installed(solv, rd->evr);
81 FOR_PROVIDES(p, pp, dep)
83 if (p == SYSTEMSOLVABLE || (solv->installed && pool->solvables[p].repo == solv->installed))
91 /* this mirrors solver_dep_fulfilled but uses map m instead of the decisionmap */
93 dep_possible(Solver *solv, Id dep, Map *m)
95 Pool *pool = solv->pool;
100 Reldep *rd = GETRELDEP(pool, dep);
101 if (rd->flags == REL_AND)
103 if (!dep_possible(solv, rd->name, m))
105 return dep_possible(solv, rd->evr, m);
107 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
108 return solver_splitprovides(solv, rd->evr);
109 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
110 return solver_dep_installed(solv, rd->evr);
112 FOR_PROVIDES(p, pp, dep)
120 /********************************************************************
126 static Pool *unifyrules_sortcmp_data;
129 * compare rules for unification sort
133 unifyrules_sortcmp(const void *ap, const void *bp)
135 Pool *pool = unifyrules_sortcmp_data;
136 Rule *a = (Rule *)ap;
137 Rule *b = (Rule *)bp;
143 return x; /* p differs */
146 if (a->d == 0 && b->d == 0)
147 return a->w2 - b->w2; /* assertion: return w2 diff */
149 if (a->d == 0) /* a is assertion, b not */
151 x = a->w2 - pool->whatprovidesdata[b->d];
155 if (b->d == 0) /* b is assertion, a not */
157 x = pool->whatprovidesdata[a->d] - b->w2;
161 /* compare whatprovidesdata */
162 ad = pool->whatprovidesdata + a->d;
163 bd = pool->whatprovidesdata + b->d;
165 if ((x = *ad++ - *bd++) != 0)
176 unifyrules(Solver *solv)
178 Pool *pool = solv->pool;
182 if (solv->nrules <= 1) /* nothing to unify */
185 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- unifyrules -----\n");
187 /* sort rules first */
188 unifyrules_sortcmp_data = solv->pool;
189 qsort(solv->rules + 1, solv->nrules - 1, sizeof(Rule), unifyrules_sortcmp);
196 for (i = j = 1, ir = solv->rules + i; i < solv->nrules; i++, ir++)
198 if (jr && !unifyrules_sortcmp(ir, jr))
199 continue; /* prune! */
200 jr = solv->rules + j++; /* keep! */
205 /* reduced count from nrules to j rules */
206 POOL_DEBUG(SAT_DEBUG_STATS, "pruned rules from %d to %d\n", solv->nrules, j);
208 /* adapt rule buffer */
210 solv->rules = sat_extend_resize(solv->rules, solv->nrules, sizeof(Rule), RULES_BLOCK);
211 IF_POOLDEBUG (SAT_DEBUG_STATS)
218 for (i = 1; i < solv->nrules; i++)
225 dp = solv->pool->whatprovidesdata + r->d;
230 POOL_DEBUG(SAT_DEBUG_STATS, " binary: %d\n", binr);
231 POOL_DEBUG(SAT_DEBUG_STATS, " normal: %d, %d literals\n", solv->nrules - 1 - binr, lits);
233 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- unifyrules end -----\n");
243 hashrule(Solver *solv, Id p, Id d, int n)
245 unsigned int x = (unsigned int)p;
249 return (x * 37) ^ (unsigned int)d;
250 dp = solv->pool->whatprovidesdata + d;
252 x = (x * 37) ^ (unsigned int)*dp++;
260 * p = direct literal; always < 0 for installed rpm rules
261 * d, if < 0 direct literal, if > 0 offset into whatprovides, if == 0 rule is assertion (look at p only)
264 * A requires b, b provided by B1,B2,B3 => (-A|B1|B2|B3)
266 * p < 0 : pkg id of A
267 * d > 0 : Offset in whatprovidesdata (list of providers of b)
269 * A conflicts b, b provided by B1,B2,B3 => (-A|-B1), (-A|-B2), (-A|-B3)
270 * p < 0 : pkg id of A
271 * d < 0 : Id of solvable (e.g. B1)
273 * d == 0: unary rule, assertion => (A) or (-A)
275 * Install: p > 0, d = 0 (A) user requested install
276 * Remove: p < 0, d = 0 (-A) user requested remove
277 * Requires: p < 0, d > 0 (-A|B1|B2|...) d: <list of providers for requirement of p>
278 * Updates: p > 0, d > 0 (A|B1|B2|...) d: <list of updates for solvable p>
279 * Conflicts: p < 0, d < 0 (-A|-B) either p (conflict issuer) or d (conflict provider) (binary rule)
280 * ? p > 0, d < 0 (A|-B)
281 * No-op ?: p = 0, d = 0 (null) (used as policy rule placeholder)
285 * Direct assertion (no watch needed)( if d <0 ) --> d = 0, w1 = p, w2 = 0
286 * Binary rule: p = first literal, d = 0, w2 = second literal, w1 = p
287 * every other : w1 = p, w2 = whatprovidesdata[d];
288 * Disabled rule: w1 = 0
290 * always returns a rule for non-rpm rules
294 addrule(Solver *solv, Id p, Id d)
296 Pool *pool = solv->pool;
300 int n = 0; /* number of literals in rule - 1
301 0 = direct assertion (single literal)
305 /* it often happenes that requires lead to adding the same rpm rule
306 * multiple times, so we prune those duplicates right away to make
307 * the work for unifyrules a bit easier */
309 if (solv->nrules && !solv->jobrules)
311 r = solv->rules + solv->nrules - 1; /* get the last added rule */
312 if (r->p == p && r->d == d && d != 0) /* identical and not user requested */
318 /* always a binary rule */
320 return 0; /* ignore self conflict */
325 for (dp = pool->whatprovidesdata + d; *dp; dp++, n++)
327 return 0; /* rule is self-fulfilling */
329 d = dp[-1]; /* take single literal */
333 if (n == 0 && !solv->jobrules)
335 /* this is a rpm rule assertion, we do not have to allocate it */
336 /* it can be identified by a level of 1 and a zero reason */
337 /* we must not drop those rules from the decisionq when rewinding! */
339 assert(solv->decisionmap[-p] == 0 || solv->decisionmap[-p] == -1);
340 if (solv->decisionmap[-p])
341 return 0; /* already got that one */
342 queue_push(&solv->decisionq, p);
343 queue_push(&solv->decisionq_why, 0);
344 solv->decisionmap[-p] = -1;
351 /* smallest literal first so we can find dups */
355 n = 1; /* re-set n, was used as temp var */
358 /* check if the last added rule is exactly the same as what we're looking for. */
359 if (r && n == 1 && !r->d && r->p == p && r->w2 == d)
360 return r; /* binary rule */
362 if (r && n > 1 && r->d && r->p == p)
364 /* Rule where d is an offset in whatprovidesdata */
368 dp2 = pool->whatprovidesdata + r->d;
369 for (dp = pool->whatprovidesdata + d; *dp; dp++, dp2++)
380 /* extend rule buffer */
381 solv->rules = sat_extend(solv->rules, solv->nrules, 1, sizeof(Rule), RULES_BLOCK);
382 r = solv->rules + solv->nrules++; /* point to rule space */
387 /* direct assertion, no watch needed */
403 r->w2 = pool->whatprovidesdata[d];
408 IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION)
410 POOL_DEBUG(SAT_DEBUG_RULE_CREATION, " Add rule: ");
411 solver_printrule(solv, SAT_DEBUG_RULE_CREATION, r);
418 disablerule(Solver *solv, Rule *r)
424 enablerule(Solver *solv, Rule *r)
426 if (r->d == 0 || r->w2 != r->p)
429 r->w1 = solv->pool->whatprovidesdata[r->d];
433 /**********************************************************************************/
435 /* a problem is an item on the solver's problem list. It can either be >0, in that
436 * case it is a update rule, or it can be <0, which makes it refer to a job
437 * consisting of multiple job rules.
441 disableproblem(Solver *solv, Id v)
449 disablerule(solv, solv->rules + v);
453 jp = solv->ruletojob.elements;
454 for (i = solv->jobrules, r = solv->rules + i; i < solv->updaterules; i++, r++, jp++)
456 disablerule(solv, r);
460 enableproblem(Solver *solv, Id v)
468 if (v >= solv->featurerules && v < solv->learntrules)
470 /* do not enable feature rule is update rule is enabled */
471 r = solv->rules + v - (solv->installed->end - solv->installed->start);
475 enablerule(solv, solv->rules + v);
476 if (v >= solv->updaterules && v < solv->featurerules)
478 r = solv->rules + v + (solv->installed->end - solv->installed->start);
480 disablerule(solv, r);
485 jp = solv->ruletojob.elements;
486 for (i = solv->jobrules, r = solv->rules + i; i < solv->updaterules; i++, r++, jp++)
492 /************************************************************************/
494 /* go through update and job rules and add direct assertions
495 * to the decisionqueue. If we find a conflict, disable rules and
496 * add them to problem queue.
499 makeruledecisions(Solver *solv)
501 Pool *pool = solv->pool;
507 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- makeruledecisions ; size decisionq: %d -----\n",solv->decisionq.count);
509 decisionstart = solv->decisionq.count;
510 /* rpm rules don't have assertions, so we can start with the job
511 * rules (rpm assertions are not resulting in a rule, but cause a
512 * immediate decision) */
513 /* nowadays they can be weak, so start with rule 1 */
514 for (ri = 1, r = solv->rules + ri; ri < solv->nrules; ri++, r++)
516 if (!r->w1 || r->w2) /* disabled or no assertion */
518 /* do weak rules in phase 2 */
519 if (ri < solv->learntrules && MAPTST(&solv->weakrulemap, ri))
523 if (!solv->decisionmap[vv])
525 queue_push(&solv->decisionq, v);
526 queue_push(&solv->decisionq_why, r - solv->rules);
527 solv->decisionmap[vv] = v > 0 ? 1 : -1;
528 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
530 Solvable *s = solv->pool->solvables + vv;
532 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "conflicting %s (assertion)\n", solvable2str(solv->pool, s));
534 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "installing %s (assertion)\n", solvable2str(solv->pool, s));
538 if (v > 0 && solv->decisionmap[vv] > 0)
540 if (v < 0 && solv->decisionmap[vv] < 0)
542 /* found a conflict! */
543 if (ri >= solv->learntrules)
545 /* conflict with a learnt rule */
546 /* can happen when packages cannot be installed for
547 * multiple reasons. */
548 /* we disable the learnt rule in this case */
549 disablerule(solv, r);
552 /* only job and update rules left in the decisionq */
553 /* find the decision which is the "opposite" of the jobrule */
554 for (i = 0; i < solv->decisionq.count; i++)
555 if (solv->decisionq.elements[i] == -v)
557 assert(i < solv->decisionq.count);
558 if (v == -SYSTEMSOLVABLE) {
559 /* conflict with system solvable */
560 queue_push(&solv->problems, solv->learnt_pool.count);
561 queue_push(&solv->learnt_pool, ri);
562 queue_push(&solv->learnt_pool, 0);
563 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "conflict with system solvable, disabling rule #%d\n", ri);
564 if (ri < solv->updaterules)
565 v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
568 queue_push(&solv->problems, v);
569 queue_push(&solv->problems, 0);
570 disableproblem(solv, v);
573 assert(solv->decisionq_why.elements[i]);
574 if (solv->decisionq_why.elements[i] < solv->jobrules)
576 /* conflict with rpm rule assertion */
577 queue_push(&solv->problems, solv->learnt_pool.count);
578 queue_push(&solv->learnt_pool, ri);
579 queue_push(&solv->learnt_pool, solv->decisionq_why.elements[i]);
580 queue_push(&solv->learnt_pool, 0);
581 assert(v > 0 || v == -SYSTEMSOLVABLE);
582 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "conflict with rpm rule, disabling rule #%d\n", ri);
583 if (ri < solv->updaterules)
584 v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
587 queue_push(&solv->problems, v);
588 queue_push(&solv->problems, 0);
589 disableproblem(solv, v);
593 /* conflict with another job or update rule */
595 queue_push(&solv->problems, solv->learnt_pool.count);
596 queue_push(&solv->learnt_pool, ri);
597 queue_push(&solv->learnt_pool, solv->decisionq_why.elements[i]);
598 queue_push(&solv->learnt_pool, 0);
600 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "conflicting update/job assertions over literal %d\n", vv);
602 /* push all of our rules asserting this literal on the problem stack */
603 for (i = solv->jobrules, rr = solv->rules + i; i < solv->nrules; i++, rr++)
605 if (!rr->w1 || rr->w2)
607 if (rr->p != vv && rr->p != -vv)
609 if (i >= solv->learntrules)
611 if (MAPTST(&solv->weakrulemap, i))
613 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, " - disabling rule #%d\n", i);
615 if (i < solv->updaterules)
616 v = -(solv->ruletojob.elements[i - solv->jobrules] + 1);
617 queue_push(&solv->problems, v);
618 disableproblem(solv, v);
620 queue_push(&solv->problems, 0);
623 while (solv->decisionq.count > decisionstart)
625 v = solv->decisionq.elements[--solv->decisionq.count];
626 --solv->decisionq_why.count;
628 solv->decisionmap[vv] = 0;
630 ri = solv->jobrules - 1;
631 r = solv->rules + ri;
634 /* phase 2: now do the weak assertions */
635 for (ri = 1, r = solv->rules + ri; ri < solv->learntrules; ri++, r++)
637 if (!r->w1 || r->w2) /* disabled or no assertion */
639 if (!MAPTST(&solv->weakrulemap, ri))
643 if (!solv->decisionmap[vv])
645 queue_push(&solv->decisionq, v);
646 queue_push(&solv->decisionq_why, r - solv->rules);
647 solv->decisionmap[vv] = v > 0 ? 1 : -1;
648 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
650 Solvable *s = solv->pool->solvables + vv;
652 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "conflicting %s (weak assertion)\n", solvable2str(solv->pool, s));
654 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "installing %s (weak assertion)\n", solvable2str(solv->pool, s));
658 if (v > 0 && solv->decisionmap[vv] > 0)
660 if (v < 0 && solv->decisionmap[vv] < 0)
662 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "assertion conflict, but I am weak, disabling ");
663 solver_printrule(solv, SAT_DEBUG_UNSOLVABLE, r);
664 disablerule(solv, r);
667 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- makeruledecisions end; size decisionq: %d -----\n",solv->decisionq.count);
671 * we have enabled or disabled some of our rules. We now reenable all
672 * of our learnt rules but the ones that were learnt from rules that
676 enabledisablelearntrules(Solver *solv)
678 Pool *pool = solv->pool;
683 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "enabledisablelearntrules called\n");
684 for (i = solv->learntrules, r = solv->rules + i; i < solv->nrules; i++, r++)
686 whyp = solv->learnt_pool.elements + solv->learnt_why.elements[i - solv->learntrules];
687 while ((why = *whyp++) != 0)
689 assert(why > 0 && why < i);
690 if (!solv->rules[why].w1)
693 /* why != 0: we found a disabled rule, disable the learnt rule */
696 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
698 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "disabling ");
699 solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
701 disablerule(solv, r);
703 else if (!why && !r->w1)
705 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
707 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "re-enabling ");
708 solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
716 enableweakrules(Solver *solv)
721 for (i = solv->jobrules, r = solv->rules + i; i < solv->learntrules; i++, r++)
725 if (!MAPTST(&solv->weakrulemap, i))
732 /* FIXME: bad code ahead, replace as soon as possible */
733 /* FIXME: should probably look at SOLVER_INSTALL_SOLVABLE_ONE_OF */
736 disableupdaterules(Solver *solv, Queue *job, int jobidx)
738 Pool *pool = solv->pool;
740 Id name, how, what, p, *pp;
746 installed = solv->installed;
752 how = job->elements[jobidx] & ~SOLVER_WEAK;
755 case SOLVER_INSTALL_SOLVABLE:
756 case SOLVER_ERASE_SOLVABLE:
757 case SOLVER_ERASE_SOLVABLE_NAME:
758 case SOLVER_ERASE_SOLVABLE_PROVIDES:
764 /* go through all enabled job rules */
765 MAPZERO(&solv->noupdate);
766 for (i = solv->jobrules; i < solv->updaterules; i++)
769 if (!r->w1) /* disabled? */
771 j = solv->ruletojob.elements[i - solv->jobrules];
775 how = job->elements[j] & ~SOLVER_WEAK;
776 what = job->elements[j + 1];
779 case SOLVER_INSTALL_SOLVABLE: /* install specific solvable */
780 s = pool->solvables + what;
781 FOR_PROVIDES(p, pp, s->name)
783 if (pool->solvables[p].name != s->name)
785 if (pool->solvables[p].repo == installed)
786 MAPSET(&solv->noupdate, p - installed->start);
789 case SOLVER_ERASE_SOLVABLE:
790 s = pool->solvables + what;
791 if (s->repo == installed)
792 MAPSET(&solv->noupdate, what - installed->start);
794 case SOLVER_ERASE_SOLVABLE_NAME: /* remove by capability */
795 case SOLVER_ERASE_SOLVABLE_PROVIDES:
796 name = (how == SOLVER_ERASE_SOLVABLE_NAME) ? what : 0;
797 while (ISRELDEP(name))
799 Reldep *rd = GETRELDEP(pool, name);
802 FOR_PROVIDES(p, pp, what)
804 if (name && pool->solvables[p].name != name)
806 if (pool->solvables[p].repo == installed)
807 MAPSET(&solv->noupdate, p - installed->start);
815 /* fixup update rule status */
816 if (solv->allowuninstall)
817 return; /* no update rules at all */
821 /* we just disabled job #jobidx. enable all update rules
822 * that aren't disabled by the remaining job rules */
823 how = job->elements[jobidx] & ~SOLVER_WEAK;
824 what = job->elements[jobidx + 1];
827 case SOLVER_INSTALL_SOLVABLE:
828 s = pool->solvables + what;
829 FOR_PROVIDES(p, pp, s->name)
831 if (pool->solvables[p].name != s->name)
833 if (pool->solvables[p].repo != installed)
835 if (MAPTST(&solv->noupdate, p - installed->start))
837 r = solv->rules + solv->updaterules + (p - installed->start);
841 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
843 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
844 solver_printrule(solv, SAT_DEBUG_SOLUTIONS, r);
848 case SOLVER_ERASE_SOLVABLE:
849 s = pool->solvables + what;
850 if (s->repo != installed)
852 if (MAPTST(&solv->noupdate, what - installed->start))
854 r = solv->rules + solv->updaterules + (what - installed->start);
858 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
860 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
861 solver_printrule(solv, SAT_DEBUG_SOLUTIONS, r);
864 case SOLVER_ERASE_SOLVABLE_NAME: /* remove by capability */
865 case SOLVER_ERASE_SOLVABLE_PROVIDES:
866 name = (how == SOLVER_ERASE_SOLVABLE_NAME) ? what : 0;
867 while (ISRELDEP(name))
869 Reldep *rd = GETRELDEP(pool, name);
872 FOR_PROVIDES(p, pp, what)
874 if (name && pool->solvables[p].name != name)
876 if (pool->solvables[p].repo != installed)
878 if (MAPTST(&solv->noupdate, p - installed->start))
880 r = solv->rules + solv->updaterules + (p - installed->start);
884 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
886 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
887 solver_printrule(solv, SAT_DEBUG_SOLUTIONS, r);
897 for (i = 0; i < installed->nsolvables; i++)
899 r = solv->rules + solv->updaterules + i;
900 if (r->w1 && MAPTST(&solv->noupdate, i))
901 disablerule(solv, r); /* was enabled, need to disable */
902 r = solv->rules + solv->featurerules + i;
903 if (r->w1 && MAPTST(&solv->noupdate, i))
904 disablerule(solv, r); /* was enabled, need to disable */
910 addpatchatomrequires(Solver *solv, Solvable *s, Id *dp, Queue *q, Map *m)
912 Pool *pool = solv->pool;
913 Id fre, *frep, p, *pp, ndp;
919 queue_init_buffer(&fq, qbuf, sizeof(qbuf)/sizeof(*qbuf));
920 queue_push(&fq, -(s - pool->solvables));
922 queue_push(&fq, *dp);
923 ndp = pool_queuetowhatprovides(pool, &fq);
924 frep = s->repo->idarraydata + s->freshens;
925 while ((fre = *frep++) != 0)
927 FOR_PROVIDES(p, pp, fre)
929 ps = pool->solvables + p;
930 addrule(solv, -p, ndp);
938 for (i = 1; i < fq.count; i++)
951 * add (install) rules for solvable
952 * for unfulfilled requirements, conflicts, obsoletes,....
953 * add a negative assertion for solvables that are not installable
957 addrpmrulesforsolvable(Solver *solv, Solvable *s, Map *m)
959 Pool *pool = solv->pool;
960 Repo *installed = solv->installed;
975 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforsolvable -----\n");
977 queue_init_buffer(&q, qbuf, sizeof(qbuf)/sizeof(*qbuf));
978 queue_push(&q, s - pool->solvables); /* push solvable Id */
984 * s: Pointer to solvable
988 if (MAPTST(m, n)) /* continue if already done */
992 s = pool->solvables + n; /* s = Solvable in question */
995 if (installed /* Installed system available */
996 && !solv->fixsystem /* NOT repair errors in rpm dependency graph */
997 && s->repo == installed) /* solvable is installed? */
999 dontfix = 1; /* dont care about broken rpm deps */
1002 if (!dontfix && s->arch != ARCH_SRC && s->arch != ARCH_NOSRC && !pool_installable(pool, s))
1004 POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "package %s [%d] is not installable\n", solvable2str(pool, s), (Id)(s - pool->solvables));
1005 addrule(solv, -n, 0); /* uninstallable */
1009 if (s->freshens && !s->supplements)
1011 const char *name = id2str(pool, s->name);
1012 if (name[0] == 'a' && !strncmp(name, "atom:", 5))
1016 /*-----------------------------------------
1017 * check requires of s
1022 reqp = s->repo->idarraydata + s->requires;
1023 while ((req = *reqp++) != 0) /* go throw all requires */
1025 if (req == SOLVABLE_PREREQMARKER) /* skip the marker */
1028 dp = pool_whatprovides(pool, req);
1030 if (*dp == SYSTEMSOLVABLE) /* always installed */
1036 addpatchatomrequires(solv, s, dp, &q, m);
1042 /* the strategy here is to not insist on dependencies
1043 * that are already broken. so if we find one provider
1044 * that was already installed, we know that the
1045 * dependency was not broken before so we enforce it */
1046 for (i = 0; (p = dp[i]) != 0; i++) /* for all providers */
1048 if (pool->solvables[p].repo == installed)
1049 break; /* provider was installed */
1051 if (!p) /* previously broken dependency */
1053 POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "ignoring broken requires %s of installed package %s\n", dep2str(pool, req), solvable2str(pool, s));
1060 /* nothing provides req! */
1061 POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "package %s [%d] is not installable (%s)\n", solvable2str(pool, s), (Id)(s - pool->solvables), dep2str(pool, req));
1062 addrule(solv, -n, 0); /* mark requestor as uninstallable */
1066 IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION)
1068 POOL_DEBUG(SAT_DEBUG_RULE_CREATION," %s requires %s\n", solvable2str(pool, s), dep2str(pool, req));
1069 for (i = 0; dp[i]; i++)
1070 POOL_DEBUG(SAT_DEBUG_RULE_CREATION, " provided by %s\n", solvable2str(pool, pool->solvables + dp[i]));
1073 /* add 'requires' dependency */
1074 /* rule: (-requestor|provider1|provider2|...|providerN) */
1075 addrule(solv, -n, dp - pool->whatprovidesdata);
1077 /* descend the dependency tree */
1078 for (; *dp; dp++) /* loop through all providers */
1080 if (!MAPTST(m, *dp))
1081 queue_push(&q, *dp);
1084 } /* while, requirements of n */
1086 } /* if, requirements */
1088 /* that's all we check for src packages */
1089 if (s->arch == ARCH_SRC || s->arch == ARCH_NOSRC)
1092 /*-----------------------------------------
1093 * check conflicts of s
1098 conp = s->repo->idarraydata + s->conflicts;
1099 while ((con = *conp++) != 0)
1101 FOR_PROVIDES(p, pp, con)
1103 /* dontfix: dont care about conflicts with already installed packs */
1104 if (dontfix && pool->solvables[p].repo == installed)
1106 if (p == n && !solv->allowselfconflicts)
1107 p = 0; /* make it a negative assertion */
1108 /* rule: -n|-p: either solvable _or_ provider of conflict */
1109 addrule(solv, -n, -p);
1114 /*-----------------------------------------
1115 * check obsoletes if not installed
1117 if (!installed || pool->solvables[n].repo != installed)
1118 { /* not installed */
1121 obsp = s->repo->idarraydata + s->obsoletes;
1122 while ((obs = *obsp++) != 0)
1124 FOR_PROVIDES(p, pp, obs)
1125 addrule(solv, -n, -p);
1128 FOR_PROVIDES(p, pp, s->name)
1130 if (s->name == pool->solvables[p].name)
1131 addrule(solv, -n, -p);
1135 /*-----------------------------------------
1136 * add recommends to the rule list
1140 recp = s->repo->idarraydata + s->recommends;
1141 while ((rec = *recp++) != 0)
1143 FOR_PROVIDES(p, pp, rec)
1150 sugp = s->repo->idarraydata + s->suggests;
1151 while ((sug = *sugp++) != 0)
1153 FOR_PROVIDES(p, pp, sug)
1160 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforsolvable end -----\n");
1164 addrpmrulesforweak(Solver *solv, Map *m)
1166 Pool *pool = solv->pool;
1171 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforweak -----\n");
1172 for (i = n = 1; n < pool->nsolvables; i++, n++)
1174 if (i == pool->nsolvables)
1178 s = pool->solvables + i;
1179 if (!pool_installable(pool, s))
1184 supp = s->repo->idarraydata + s->supplements;
1185 while ((sup = *supp++) != ID_NULL)
1186 if (dep_possible(solv, sup, m))
1189 if (!sup && s->freshens)
1191 supp = s->repo->idarraydata + s->freshens;
1192 while ((sup = *supp++) != ID_NULL)
1193 if (dep_possible(solv, sup, m))
1196 if (!sup && s->enhances)
1198 supp = s->repo->idarraydata + s->enhances;
1199 while ((sup = *supp++) != ID_NULL)
1200 if (dep_possible(solv, sup, m))
1205 addrpmrulesforsolvable(solv, s, m);
1208 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforweak end -----\n");
1212 addrpmrulesforupdaters(Solver *solv, Solvable *s, Map *m, int allowall)
1214 Pool *pool = solv->pool;
1219 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforupdaters -----\n");
1221 queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
1222 policy_findupdatepackages(solv, s, &qs, allowall);
1223 if (!MAPTST(m, s - pool->solvables)) /* add rule for s if not already done */
1224 addrpmrulesforsolvable(solv, s, m);
1225 for (i = 0; i < qs.count; i++)
1226 if (!MAPTST(m, qs.elements[i]))
1227 addrpmrulesforsolvable(solv, pool->solvables + qs.elements[i], m);
1230 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforupdaters -----\n");
1234 * add rule for update
1235 * (A|A1|A2|A3...) An = update candidates for A
1237 * s = (installed) solvable
1241 addupdaterule(Solver *solv, Solvable *s, int allowall)
1243 /* installed packages get a special upgrade allowed rule */
1244 Pool *pool = solv->pool;
1249 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addupdaterule -----\n");
1251 queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
1252 policy_findupdatepackages(solv, s, &qs, allowall);
1253 if (qs.count == 0) /* no updaters found */
1256 d = pool_queuetowhatprovides(pool, &qs); /* intern computed queue */
1258 addrule(solv, s - pool->solvables, d); /* allow update of s */
1259 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addupdaterule end -----\n");
1263 /*-----------------------------------------------------------------*/
1270 * initial setup for all watches
1274 makewatches(Solver *solv)
1278 int nsolvables = solv->pool->nsolvables;
1280 sat_free(solv->watches);
1281 /* lower half for removals, upper half for installs */
1282 solv->watches = sat_calloc(2 * nsolvables, sizeof(Id));
1284 /* do it reverse so rpm rules get triggered first (XXX: obsolete?) */
1285 for (i = 1, r = solv->rules + solv->nrules - 1; i < solv->nrules; i++, r--)
1287 for (i = 1, r = solv->rules + 1; i < solv->nrules; i++, r++)
1290 if (!r->w1 /* rule is disabled */
1291 || !r->w2) /* rule is assertion */
1294 /* see addwatches(solv, r) */
1295 r->n1 = solv->watches[nsolvables + r->w1];
1296 solv->watches[nsolvables + r->w1] = r - solv->rules;
1298 r->n2 = solv->watches[nsolvables + r->w2];
1299 solv->watches[nsolvables + r->w2] = r - solv->rules;
1305 * add watches (for rule)
1309 addwatches(Solver *solv, Rule *r)
1311 int nsolvables = solv->pool->nsolvables;
1313 r->n1 = solv->watches[nsolvables + r->w1];
1314 solv->watches[nsolvables + r->w1] = r - solv->rules;
1316 r->n2 = solv->watches[nsolvables + r->w2];
1317 solv->watches[nsolvables + r->w2] = r - solv->rules;
1321 /*-----------------------------------------------------------------*/
1322 /* rule propagation */
1324 #define DECISIONMAP_TRUE(p) ((p) > 0 ? (decisionmap[p] > 0) : (decisionmap[-p] < 0))
1325 #define DECISIONMAP_FALSE(p) ((p) > 0 ? (decisionmap[p] < 0) : (decisionmap[-p] > 0))
1330 * propagate decision to all rules
1331 * return : 0 = everything is OK
1332 * watched rule = there is a conflict
1336 propagate(Solver *solv, int level)
1338 Pool *pool = solv->pool;
1343 Id *decisionmap = solv->decisionmap;
1344 Id *watches = solv->watches + pool->nsolvables;
1346 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "----- propagate -----\n");
1348 while (solv->propagate_index < solv->decisionq.count)
1350 /* negate because our watches trigger if literal goes FALSE */
1351 pkg = -solv->decisionq.elements[solv->propagate_index++];
1352 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1354 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "propagate for decision %d level %d\n", -pkg, level);
1355 solver_printruleelement(solv, SAT_DEBUG_PROPAGATE, 0, -pkg);
1357 solver_printwatches(solv, SAT_DEBUG_SCHUBI);
1360 for (rp = watches + pkg; *rp; rp = nrp)
1362 r = solv->rules + *rp;
1364 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1366 POOL_DEBUG(SAT_DEBUG_PROPAGATE," watch triggered ");
1367 solver_printrule(solv, SAT_DEBUG_PROPAGATE, r);
1372 ow = r->w2; /* regard the second watchpoint to come to a solution */
1377 ow = r->w1; /* regard the first watchpoint to come to a solution */
1380 /* if clause is TRUE, nothing to do */
1381 if (DECISIONMAP_TRUE(ow))
1386 /* not a binary clause, check if we need to move our watch */
1387 /* search for a literal that is not ow and not false */
1388 /* (true is also ok, in that case the rule is fulfilled) */
1389 if (r->p && r->p != ow && !DECISIONMAP_TRUE(-r->p))
1392 for (dp = pool->whatprovidesdata + r->d; (p = *dp++) != 0;)
1393 if (p != ow && !DECISIONMAP_TRUE(-p))
1397 /* p is free to watch, move watch to p */
1398 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1401 POOL_DEBUG(SAT_DEBUG_PROPAGATE, " -> move w%d to %s\n", (pkg == r->w1 ? 1 : 2), solvable2str(pool, pool->solvables + p));
1403 POOL_DEBUG(SAT_DEBUG_PROPAGATE," -> move w%d to !%s\n", (pkg == r->w1 ? 1 : 2), solvable2str(pool, pool->solvables - p));
1417 watches[p] = r - solv->rules;
1421 /* unit clause found, set other watch to TRUE */
1422 if (DECISIONMAP_TRUE(-ow))
1423 return r; /* eek, a conflict! */
1424 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1426 POOL_DEBUG(SAT_DEBUG_PROPAGATE, " unit ");
1427 solver_printrule(solv, SAT_DEBUG_PROPAGATE, r);
1430 decisionmap[ow] = level;
1432 decisionmap[-ow] = -level;
1433 queue_push(&solv->decisionq, ow);
1434 queue_push(&solv->decisionq_why, r - solv->rules);
1435 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1437 Solvable *s = pool->solvables + (ow > 0 ? ow : -ow);
1439 POOL_DEBUG(SAT_DEBUG_PROPAGATE, " -> decided to install %s\n", solvable2str(pool, s));
1441 POOL_DEBUG(SAT_DEBUG_PROPAGATE, " -> decided to conflict %s\n", solvable2str(pool, s));
1445 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "----- propagate end-----\n");
1447 return 0; /* all is well */
1451 /*-----------------------------------------------------------------*/
1460 analyze(Solver *solv, int level, Rule *c, int *pr, int *dr, int *whyp)
1462 Pool *pool = solv->pool;
1465 Map seen; /* global? */
1468 int num = 0, l1num = 0;
1469 int learnt_why = solv->learnt_pool.count;
1470 Id *decisionmap = solv->decisionmap;
1474 POOL_DEBUG(SAT_DEBUG_ANALYZE, "ANALYZE at %d ----------------------\n", level);
1475 map_init(&seen, pool->nsolvables);
1476 idx = solv->decisionq.count;
1479 IF_POOLDEBUG (SAT_DEBUG_ANALYZE)
1480 solver_printruleclass(solv, SAT_DEBUG_ANALYZE, c);
1481 queue_push(&solv->learnt_pool, c - solv->rules);
1482 dp = c->d ? pool->whatprovidesdata + c->d : 0;
1483 /* go through all literals of the rule */
1495 if (DECISIONMAP_TRUE(v)) /* the one true literal */
1497 vv = v > 0 ? v : -v;
1498 if (MAPTST(&seen, vv))
1500 l = solv->decisionmap[vv];
1505 l1num++; /* need to do this one in level1 pass */
1506 else if (l == level)
1507 num++; /* need to do this one as well */
1510 queue_push(&r, v); /* not level1 or conflict level, add to new rule */
1516 if (!num && !--l1num)
1517 break; /* all level 1 literals done */
1521 v = solv->decisionq.elements[--idx];
1522 vv = v > 0 ? v : -v;
1523 if (MAPTST(&seen, vv))
1527 if (num && --num == 0)
1529 *pr = -v; /* so that v doesn't get lost */
1532 POOL_DEBUG(SAT_DEBUG_ANALYZE, "got %d involved level 1 decisions\n", l1num);
1533 for (i = 0; i < r.count; i++)
1536 MAPCLR(&seen, v > 0 ? v : -v);
1538 /* only level 1 marks left */
1542 why = solv->decisionq_why.elements[idx];
1543 if (!why) /* just in case, maye for SYSTEMSOLVABLE */
1545 c = solv->rules + why;
1551 else if (r.count == 1 && r.elements[0] < 0)
1552 *dr = r.elements[0];
1554 *dr = pool_queuetowhatprovides(pool, &r);
1555 IF_POOLDEBUG (SAT_DEBUG_ANALYZE)
1557 POOL_DEBUG(SAT_DEBUG_ANALYZE, "learned rule for level %d (am %d)\n", rlevel, level);
1558 solver_printruleelement(solv, SAT_DEBUG_ANALYZE, 0, *pr);
1559 for (i = 0; i < r.count; i++)
1560 solver_printruleelement(solv, SAT_DEBUG_ANALYZE, 0, r.elements[i]);
1562 /* push end marker on learnt reasons stack */
1563 queue_push(&solv->learnt_pool, 0);
1572 * reset the solver decisions to right after the rpm rules.
1573 * called after rules have been enabled/disabled
1577 reset_solver(Solver *solv)
1579 Pool *pool = solv->pool;
1583 /* rewind decisions to direct rpm rule assertions */
1584 for (i = solv->decisionq.count - 1; i >= solv->directdecisions; i--)
1586 v = solv->decisionq.elements[i];
1587 solv->decisionmap[v > 0 ? v : -v] = 0;
1590 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "decisions done reduced from %d to %d\n", solv->decisionq.count, solv->directdecisions);
1592 solv->decisionq_why.count = solv->directdecisions;
1593 solv->decisionq.count = solv->directdecisions;
1594 solv->recommends_index = -1;
1595 solv->propagate_index = 0;
1597 /* adapt learnt rule status to new set of enabled/disabled rules */
1598 enabledisablelearntrules(solv);
1600 /* redo all job/update decisions */
1601 makeruledecisions(solv);
1602 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "decisions so far: %d\n", solv->decisionq.count);
1604 /* recreate watch chains */
1610 * analyze_unsolvable_rule
1614 analyze_unsolvable_rule(Solver *solv, Rule *r, Id *lastweakp)
1616 Pool *pool = solv->pool;
1618 Id why = r - solv->rules;
1620 IF_POOLDEBUG (SAT_DEBUG_UNSOLVABLE)
1621 solver_printruleclass(solv, SAT_DEBUG_UNSOLVABLE, r);
1622 if (solv->learntrules && why >= solv->learntrules)
1624 for (i = solv->learnt_why.elements[why - solv->learntrules]; solv->learnt_pool.elements[i]; i++)
1625 if (solv->learnt_pool.elements[i] > 0)
1626 analyze_unsolvable_rule(solv, solv->rules + solv->learnt_pool.elements[i], lastweakp);
1629 if (MAPTST(&solv->weakrulemap, why))
1630 if (!*lastweakp || why > *lastweakp)
1632 /* do not add rpm rules to problem */
1633 if (why < solv->jobrules)
1635 /* turn rule into problem */
1636 if (why >= solv->jobrules && why < solv->updaterules)
1637 why = -(solv->ruletojob.elements[why - solv->jobrules] + 1);
1638 /* return if problem already countains our rule */
1639 if (solv->problems.count)
1641 for (i = solv->problems.count - 1; i >= 0; i--)
1642 if (solv->problems.elements[i] == 0) /* end of last problem reached? */
1644 else if (solv->problems.elements[i] == why)
1647 queue_push(&solv->problems, why);
1652 * analyze_unsolvable
1654 * return: 1 - disabled some rules, try again
1659 analyze_unsolvable(Solver *solv, Rule *cr, int disablerules)
1661 Pool *pool = solv->pool;
1663 Map seen; /* global to speed things up? */
1666 Id *decisionmap = solv->decisionmap;
1667 int oldproblemcount;
1668 int oldlearntpoolcount;
1671 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "ANALYZE UNSOLVABLE ----------------------\n");
1672 oldproblemcount = solv->problems.count;
1673 oldlearntpoolcount = solv->learnt_pool.count;
1675 /* make room for proof index */
1676 /* must update it later, as analyze_unsolvable_rule would confuse
1677 * it with a rule index if we put the real value in already */
1678 queue_push(&solv->problems, 0);
1681 map_init(&seen, pool->nsolvables);
1682 queue_push(&solv->learnt_pool, r - solv->rules);
1684 analyze_unsolvable_rule(solv, r, &lastweak);
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];
1712 queue_push(&solv->learnt_pool, why);
1713 r = solv->rules + why;
1714 analyze_unsolvable_rule(solv, r, &lastweak);
1715 dp = r->d ? pool->whatprovidesdata + r->d : 0;
1726 if (DECISIONMAP_TRUE(v)) /* the one true literal */
1728 vv = v > 0 ? v : -v;
1729 l = solv->decisionmap[vv];
1736 queue_push(&solv->problems, 0); /* mark end of this problem */
1740 /* disable last weak rule */
1741 solv->problems.count = oldproblemcount;
1742 solv->learnt_pool.count = oldlearntpoolcount;
1743 r = solv->rules + lastweak;
1744 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "disabling ");
1745 solver_printruleclass(solv, SAT_DEBUG_UNSOLVABLE, r);
1746 disablerule(solv, r);
1752 queue_push(&solv->learnt_pool, 0);
1753 solv->problems.elements[oldproblemcount] = oldlearntpoolcount;
1757 for (i = oldproblemcount + 1; i < solv->problems.count - 1; i++)
1758 disableproblem(solv, solv->problems.elements[i]);
1759 /* XXX: might want to enable all weak rules again */
1763 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "UNSOLVABLE\n");
1768 /*-----------------------------------------------------------------*/
1769 /* Decision revert */
1773 * revert decision at level
1777 revert(Solver *solv, int level)
1779 Pool *pool = solv->pool;
1781 while (solv->decisionq.count)
1783 v = solv->decisionq.elements[solv->decisionq.count - 1];
1784 vv = v > 0 ? v : -v;
1785 if (solv->decisionmap[vv] <= level && solv->decisionmap[vv] >= -level)
1787 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "reverting decision %d at %d\n", v, solv->decisionmap[vv]);
1788 if (v > 0 && solv->recommendations.count && v == solv->recommendations.elements[solv->recommendations.count - 1])
1789 solv->recommendations.count--;
1790 solv->decisionmap[vv] = 0;
1791 solv->decisionq.count--;
1792 solv->decisionq_why.count--;
1793 solv->propagate_index = solv->decisionq.count;
1795 while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] <= -level)
1797 solv->branches.count--;
1798 while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] >= 0)
1799 solv->branches.count--;
1801 solv->recommends_index = -1;
1806 * watch2onhighest - put watch2 on literal with highest level
1810 watch2onhighest(Solver *solv, Rule *r)
1816 return; /* binary rule, both watches are set */
1817 dp = solv->pool->whatprovidesdata + r->d;
1818 while ((v = *dp++) != 0)
1820 l = solv->decisionmap[v < 0 ? -v : v];
1835 * add free decision to decisionq, increase level and
1836 * propagate decision, return if no conflict.
1837 * in conflict case, analyze conflict rule, add resulting
1838 * rule to learnt rule set, make decision from learnt
1839 * rule (always unit) and re-propagate.
1841 * returns the new solver level or 0 if unsolvable
1846 setpropagatelearn(Solver *solv, int level, Id decision, int disablerules)
1848 Pool *pool = solv->pool;
1857 solv->decisionmap[decision] = level;
1859 solv->decisionmap[-decision] = -level;
1860 queue_push(&solv->decisionq, decision);
1861 queue_push(&solv->decisionq_why, 0);
1865 r = propagate(solv, level);
1869 return analyze_unsolvable(solv, r, disablerules);
1870 POOL_DEBUG(SAT_DEBUG_ANALYZE, "conflict with rule #%d\n", (int)(r - solv->rules));
1871 l = analyze(solv, level, r, &p, &d, &why); /* learnt rule in p and d */
1872 assert(l > 0 && l < level);
1873 POOL_DEBUG(SAT_DEBUG_ANALYZE, "reverting decisions (level %d -> %d)\n", level, l);
1875 revert(solv, level);
1876 r = addrule(solv, p, d); /* p requires d */
1878 assert(solv->learnt_why.count == (r - solv->rules) - solv->learntrules);
1879 queue_push(&solv->learnt_why, why);
1882 /* at least 2 literals, needs watches */
1883 watch2onhighest(solv, r);
1884 addwatches(solv, r);
1886 solv->decisionmap[p > 0 ? p : -p] = p > 0 ? level : -level;
1887 queue_push(&solv->decisionq, p);
1888 queue_push(&solv->decisionq_why, r - solv->rules);
1889 IF_POOLDEBUG (SAT_DEBUG_ANALYZE)
1891 POOL_DEBUG(SAT_DEBUG_ANALYZE, "decision: ");
1892 solver_printruleelement(solv, SAT_DEBUG_ANALYZE, 0, p);
1893 POOL_DEBUG(SAT_DEBUG_ANALYZE, "new rule: ");
1894 solver_printrule(solv, SAT_DEBUG_ANALYZE, r);
1902 * install best package from the queue. We add an extra package, inst, if
1903 * provided. See comment in weak install section.
1905 * returns the new solver level or 0 if unsolvable
1909 selectandinstall(Solver *solv, int level, Queue *dq, Id inst, int disablerules)
1911 Pool *pool = solv->pool;
1915 if (dq->count > 1 || inst)
1916 policy_filter_unwanted(solv, dq, inst, POLICY_MODE_CHOOSE);
1921 /* choose the supplemented one */
1922 for (i = 0; i < dq->count; i++)
1923 if (solver_is_supplementing(solv, pool->solvables + dq->elements[i]))
1927 for (i = 1; i < dq->count; i++)
1928 queue_push(&solv->branches, dq->elements[i]);
1929 queue_push(&solv->branches, -level);
1933 p = dq->elements[i];
1935 POOL_DEBUG(SAT_DEBUG_POLICY, "installing %s\n", solvable2str(pool, pool->solvables + p));
1937 return setpropagatelearn(solv, level, p, disablerules);
1941 /*-----------------------------------------------------------------*/
1942 /* Main solver interface */
1947 * create solver structure
1949 * pool: all available solvables
1950 * installed: installed Solvables
1953 * Upon solving, rules are created to flag the Solvables
1954 * of the 'installed' Repo as installed.
1958 solver_create(Pool *pool, Repo *installed)
1961 solv = (Solver *)sat_calloc(1, sizeof(Solver));
1963 solv->installed = installed;
1965 queue_init(&solv->ruletojob);
1966 queue_init(&solv->decisionq);
1967 queue_init(&solv->decisionq_why);
1968 queue_init(&solv->problems);
1969 queue_init(&solv->suggestions);
1970 queue_init(&solv->recommendations);
1971 queue_init(&solv->learnt_why);
1972 queue_init(&solv->learnt_pool);
1973 queue_init(&solv->branches);
1974 queue_init(&solv->covenantq);
1975 queue_init(&solv->weakruleq);
1977 map_init(&solv->recommendsmap, pool->nsolvables);
1978 map_init(&solv->suggestsmap, pool->nsolvables);
1979 map_init(&solv->noupdate, installed ? installed->end - installed->start : 0);
1980 solv->recommends_index = 0;
1982 solv->decisionmap = (Id *)sat_calloc(pool->nsolvables, sizeof(Id));
1984 solv->rules = sat_extend_resize(solv->rules, solv->nrules, sizeof(Rule), RULES_BLOCK);
1985 memset(solv->rules, 0, sizeof(Rule));
1996 solver_free(Solver *solv)
1998 queue_free(&solv->ruletojob);
1999 queue_free(&solv->decisionq);
2000 queue_free(&solv->decisionq_why);
2001 queue_free(&solv->learnt_why);
2002 queue_free(&solv->learnt_pool);
2003 queue_free(&solv->problems);
2004 queue_free(&solv->suggestions);
2005 queue_free(&solv->recommendations);
2006 queue_free(&solv->branches);
2007 queue_free(&solv->covenantq);
2008 queue_free(&solv->weakruleq);
2010 map_free(&solv->recommendsmap);
2011 map_free(&solv->suggestsmap);
2012 map_free(&solv->noupdate);
2013 map_free(&solv->weakrulemap);
2015 sat_free(solv->decisionmap);
2016 sat_free(solv->rules);
2017 sat_free(solv->watches);
2018 sat_free(solv->obsoletes);
2019 sat_free(solv->obsoletes_data);
2024 /*-------------------------------------------------------*/
2029 * all rules have been set up, now actually run the solver
2034 run_solver(Solver *solv, int disablerules, int doweak)
2042 Pool *pool = solv->pool;
2045 IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION)
2047 POOL_DEBUG (SAT_DEBUG_RULE_CREATION, "number of rules: %d\n", solv->nrules);
2048 for (i = 1; i < solv->nrules; i++)
2049 solver_printruleclass(solv, SAT_DEBUG_RULE_CREATION, solv->rules + i);
2052 POOL_DEBUG(SAT_DEBUG_STATS, "initial decisions: %d\n", solv->decisionq.count);
2054 IF_POOLDEBUG (SAT_DEBUG_SCHUBI)
2055 solver_printdecisions(solv);
2057 /* start SAT algorithm */
2059 systemlevel = level + 1;
2060 POOL_DEBUG(SAT_DEBUG_STATS, "solving...\n");
2065 * here's the main loop:
2066 * 1) propagate new decisions (only needed for level 1)
2067 * 2) try to keep installed packages
2068 * 3) fulfill all unresolved rules
2069 * 4) install recommended packages
2070 * 5) minimalize solution if we had choices
2071 * if we encounter a problem, we rewind to a safe level and restart
2083 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "propagating (propagate_index: %d; size decisionq: %d)...\n", solv->propagate_index, solv->decisionq.count);
2084 if ((r = propagate(solv, level)) != 0)
2086 if (analyze_unsolvable(solv, r, disablerules))
2094 * installed packages
2097 if (level < systemlevel && solv->installed && solv->installed->nsolvables)
2099 if (!solv->updatesystem)
2101 /* try to keep as many packages as possible */
2102 POOL_DEBUG(SAT_DEBUG_STATS, "installing old packages\n");
2103 for (i = solv->installed->start; i < solv->installed->end; i++)
2105 s = pool->solvables + i;
2106 if (s->repo != solv->installed)
2108 if (solv->decisionmap[i] != 0)
2110 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "keeping %s\n", solvable2str(pool, s));
2112 level = setpropagatelearn(solv, level, i, disablerules);
2118 if (level <= olevel)
2121 if (i < solv->installed->end)
2124 POOL_DEBUG(SAT_DEBUG_STATS, "resolving update/feature rules\n");
2125 for (i = solv->installed->start, r = solv->rules + solv->updaterules; i < solv->installed->end; i++, r++)
2128 s = pool->solvables + i;
2129 if (s->repo != solv->installed)
2131 if (solv->decisionmap[i] > 0)
2133 /* noupdate is set if a job is erasing the installed solvable or installing a specific version */
2134 if (MAPTST(&solv->noupdate, i - solv->installed->start))
2137 if (!solv->allowuninstall)
2141 rr += solv->installed->end - solv->installed->start;
2144 rr = solv->rules + solv->featurerules + (i - solv->installed->start);
2147 if (!rr->w2 || solv->decisionmap[rr->w2] > 0)
2149 if (solv->decisionmap[rr->w2] == 0)
2150 queue_push(&dq, rr->w2);
2154 dp = pool->whatprovidesdata + rr->d;
2155 while ((p = *dp++) != 0)
2157 if (solv->decisionmap[p] > 0)
2159 if (solv->decisionmap[p] == 0)
2165 if (!dq.count && solv->decisionmap[i] != 0)
2168 /* FIXME: i is handled a bit different because we do not want
2169 * to have it pruned just because it is not recommened.
2170 * we should not prune installed packages instead */
2171 level = selectandinstall(solv, level, &dq, (solv->decisionmap[i] ? 0 : i), disablerules);
2177 if (level <= olevel)
2180 if (i < solv->installed->end)
2182 systemlevel = level;
2189 POOL_DEBUG(SAT_DEBUG_STATS, "deciding unresolved rules\n");
2190 for (i = 1, n = 1; ; i++, n++)
2192 if (n == solv->nrules)
2194 if (i == solv->nrules)
2196 r = solv->rules + i;
2197 if (!r->w1) /* ignore disabled rules */
2202 /* binary or unary rule */
2203 /* need two positive undecided literals */
2204 if (r->p < 0 || r->w2 <= 0)
2206 if (solv->decisionmap[r->p] || solv->decisionmap[r->w2])
2208 queue_push(&dq, r->p);
2209 queue_push(&dq, r->w2);
2214 * all negative literals are installed
2215 * no positive literal is installed
2216 * i.e. the rule is not fulfilled and we
2217 * just need to decide on the positive literals
2221 if (solv->decisionmap[-r->p] <= 0)
2226 if (solv->decisionmap[r->p] > 0)
2228 if (solv->decisionmap[r->p] == 0)
2229 queue_push(&dq, r->p);
2231 dp = pool->whatprovidesdata + r->d;
2232 while ((p = *dp++) != 0)
2236 if (solv->decisionmap[-p] <= 0)
2241 if (solv->decisionmap[p] > 0)
2243 if (solv->decisionmap[p] == 0)
2250 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
2252 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "unfulfilled ");
2253 solver_printruleclass(solv, SAT_DEBUG_PROPAGATE, r);
2255 /* dq.count < 2 cannot happen as this means that
2256 * the rule is unit */
2257 assert(dq.count > 1);
2260 level = selectandinstall(solv, level, &dq, 0, disablerules);
2266 if (level < systemlevel)
2269 } /* for(), decide */
2271 if (n != solv->nrules) /* continue if level < systemlevel */
2278 POOL_DEBUG(SAT_DEBUG_STATS, "installing recommended packages\n");
2280 for (i = 1; i < pool->nsolvables; i++)
2282 if (solv->decisionmap[i] < 0)
2284 if (solv->decisionmap[i] > 0)
2286 Id *recp, rec, *pp, p;
2287 s = pool->solvables + i;
2288 /* installed, check for recommends */
2289 /* XXX need to special case AND ? */
2292 recp = s->repo->idarraydata + s->recommends;
2293 while ((rec = *recp++) != 0)
2296 FOR_PROVIDES(p, pp, rec)
2298 if (solv->decisionmap[p] > 0)
2303 else if (solv->decisionmap[p] == 0)
2305 queue_pushunique(&dq, p);
2313 s = pool->solvables + i;
2314 if (!s->supplements && !s->freshens)
2316 if (!pool_installable(pool, s))
2318 if (solver_is_supplementing(solv, s))
2319 queue_pushunique(&dq, i);
2325 policy_filter_unwanted(solv, &dq, 0, POLICY_MODE_RECOMMEND);
2327 POOL_DEBUG(SAT_DEBUG_STATS, "installing recommended %s\n", solvable2str(pool, pool->solvables + p));
2328 queue_push(&solv->recommendations, p);
2329 level = setpropagatelearn(solv, level, p, 0);
2334 if (solv->solution_callback)
2336 solv->solution_callback(solv, solv->solution_callback_data);
2337 if (solv->branches.count)
2339 int i = solv->branches.count - 1;
2340 int l = -solv->branches.elements[i];
2342 if (solv->branches.elements[i - 1] < 0)
2344 p = solv->branches.elements[i];
2345 POOL_DEBUG(SAT_DEBUG_STATS, "branching with %s\n", solvable2str(pool, pool->solvables + p));
2347 for (j = i + 1; j < solv->branches.count; j++)
2348 queue_push(&dq, solv->branches.elements[j]);
2349 solv->branches.count = i;
2351 revert(solv, level);
2353 for (j = 0; j < dq.count; j++)
2354 queue_push(&solv->branches, dq.elements[j]);
2356 level = setpropagatelearn(solv, level, p, disablerules);
2364 /* all branches done, we're finally finished */
2368 /* minimization step */
2369 if (solv->branches.count)
2371 int l = 0, lasti = -1, lastl = -1;
2373 for (i = solv->branches.count - 1; i >= 0; i--)
2375 p = solv->branches.elements[i];
2378 else if (p > 0 && solv->decisionmap[p] > l + 1)
2386 /* kill old solvable so that we do not loop */
2387 p = solv->branches.elements[lasti];
2388 solv->branches.elements[lasti] = 0;
2389 POOL_DEBUG(SAT_DEBUG_STATS, "minimizing %d -> %d with %s\n", solv->decisionmap[p], l, solvable2str(pool, pool->solvables + p));
2392 revert(solv, level);
2394 level = setpropagatelearn(solv, level, p, disablerules);
2405 POOL_DEBUG(SAT_DEBUG_STATS, "done solving.\n\n");
2412 * at this point, all rules that led to conflicts are disabled.
2413 * we re-enable all rules of a problem set but rule "sug", then
2414 * continue to disable more rules until there as again a solution.
2417 /* FIXME: think about conflicting assertions */
2420 refine_suggestion(Solver *solv, Queue *job, Id *problem, Id sug, Queue *refined)
2422 Pool *pool = solv->pool;
2428 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
2430 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "refine_suggestion start\n");
2431 for (i = 0; problem[i]; i++)
2433 if (problem[i] == sug)
2434 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "=> ");
2435 solver_printproblem(solv, problem[i]);
2438 queue_init(&disabled);
2439 queue_empty(refined);
2440 queue_push(refined, sug);
2442 /* re-enable all problem rules with the exception of "sug"(gestion) */
2446 for (i = 0; problem[i]; i++)
2447 if (problem[i] != sug)
2448 enableproblem(solv, problem[i]);
2451 disableupdaterules(solv, job, -(sug + 1));
2455 int njob, nfeature, nupdate;
2456 queue_empty(&solv->problems);
2457 enableweakrules(solv);
2458 revert(solv, 1); /* XXX no longer needed? */
2461 if (!solv->problems.count)
2462 run_solver(solv, 0, 0);
2464 if (!solv->problems.count)
2466 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "no more problems!\n");
2467 IF_POOLDEBUG (SAT_DEBUG_SCHUBI)
2468 solver_printdecisions(solv);
2469 break; /* great, no more problems */
2471 disabledcnt = disabled.count;
2472 /* start with 1 to skip over proof index */
2473 njob = nfeature = nupdate = 0;
2474 for (i = 1; i < solv->problems.count - 1; i++)
2476 /* ignore solutions in refined */
2477 v = solv->problems.elements[i];
2479 break; /* end of problem reached */
2480 for (j = 0; problem[j]; j++)
2481 if (problem[j] != sug && problem[j] == v)
2485 if (v >= solv->featurerules && v < solv->learntrules)
2491 queue_push(&disabled, v);
2493 if (disabled.count == disabledcnt)
2495 /* no solution found, this was an invalid suggestion! */
2496 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "no solution found!\n");
2500 if (!njob && nupdate && nfeature)
2502 /* got only update rules, filter out feature rules */
2503 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "throwing away feature rules\n");
2504 for (i = j = disabledcnt; i < disabled.count; i++)
2506 v = disabled.elements[i];
2507 if (v < solv->featurerules || v >= solv->learntrules)
2508 disabled.elements[j++] = v;
2513 if (disabled.count == disabledcnt + 1)
2515 /* just one suggestion, add it to refined list */
2516 v = disabled.elements[disabledcnt];
2518 queue_push(refined, v); /* do not record feature rules */
2519 disableproblem(solv, v);
2520 if (v >= solv->updaterules && v < solv->featurerules)
2522 Rule *r = solv->rules + v + (solv->installed->end - solv->installed->start);
2524 enablerule(solv, r); /* enable corresponding feature rule */
2527 disableupdaterules(solv, job, -(v + 1));
2531 /* more than one solution, disable all */
2532 /* do not push anything on refine list, as we do not know which solution to choose */
2533 /* thus, the user will get another problem if he selects this solution, where he
2534 * can choose the right one */
2535 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
2537 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "more than one solution found:\n");
2538 for (i = disabledcnt; i < disabled.count; i++)
2539 solver_printproblem(solv, disabled.elements[i]);
2541 for (i = disabledcnt; i < disabled.count; i++)
2543 v = disabled.elements[i];
2544 disableproblem(solv, v);
2545 if (v >= solv->updaterules && v < solv->featurerules)
2547 Rule *r = solv->rules + v + (solv->installed->end - solv->installed->start);
2549 enablerule(solv, r);
2554 /* all done, get us back into the same state as before */
2555 /* enable refined rules again */
2556 for (i = 0; i < disabled.count; i++)
2557 enableproblem(solv, disabled.elements[i]);
2558 /* disable problem rules again */
2559 for (i = 0; problem[i]; i++)
2560 disableproblem(solv, problem[i]);
2561 disableupdaterules(solv, job, -1);
2562 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "refine_suggestion end\n");
2566 problems_to_solutions(Solver *solv, Queue *job)
2568 Pool *pool = solv->pool;
2576 if (!solv->problems.count)
2578 queue_clone(&problems, &solv->problems);
2579 queue_init(&solution);
2580 queue_init(&solutions);
2581 /* copy over proof index */
2582 queue_push(&solutions, problems.elements[0]);
2583 problem = problems.elements + 1;
2584 for (i = 1; i < problems.count; i++)
2586 Id v = problems.elements[i];
2589 /* mark end of this problem */
2590 queue_push(&solutions, 0);
2591 queue_push(&solutions, 0);
2592 if (i + 1 == problems.count)
2594 /* copy over proof of next problem */
2595 queue_push(&solutions, problems.elements[i + 1]);
2597 problem = problems.elements + i + 1;
2600 refine_suggestion(solv, job, problem, v, &solution);
2601 if (!solution.count)
2602 continue; /* this solution didn't work out */
2604 for (j = 0; j < solution.count; j++)
2606 why = solution.elements[j];
2607 /* must be either job descriptor or update rule */
2608 assert(why < 0 || (why >= solv->updaterules && why < solv->featurerules));
2610 solver_printproblem(solv, why);
2614 /* job descriptor */
2615 queue_push(&solutions, 0);
2616 queue_push(&solutions, -why);
2620 /* update rule, find replacement package */
2623 p = solv->installed->start + (why - solv->updaterules);
2624 if (solv->decisionmap[p] > 0)
2625 continue; /* false alarm, turned out we can keep the package */
2626 rr = solv->rules + solv->featurerules + (why - solv->updaterules);
2628 rr = solv->rules + why;
2633 if (solv->decisionmap[rr->w2] > 0 && pool->solvables[rr->w2].repo != solv->installed)
2638 Id *dp = pool->whatprovidesdata + rr->d;
2641 if (solv->decisionmap[*dp] > 0 && pool->solvables[*dp].repo != solv->installed)
2649 queue_push(&solutions, p);
2650 queue_push(&solutions, rp);
2653 /* mark end of this solution */
2654 queue_push(&solutions, 0);
2655 queue_push(&solutions, 0);
2657 queue_free(&solution);
2658 queue_free(&problems);
2659 /* copy queue over to solutions */
2660 queue_free(&solv->problems);
2661 queue_clone(&solv->problems, &solutions);
2663 /* bring solver back into problem state */
2664 revert(solv, 1); /* XXX move to reset_solver? */
2667 assert(solv->problems.count == solutions.count);
2668 queue_free(&solutions);
2672 solver_next_problem(Solver *solv, Id problem)
2676 return solv->problems.count ? 1 : 0;
2677 pp = solv->problems.elements + problem;
2678 while (pp[0] || pp[1])
2682 while (pp[0] || pp[1])
2687 problem = pp - solv->problems.elements;
2688 if (problem >= solv->problems.count)
2694 solver_next_solution(Solver *solv, Id problem, Id solution)
2700 pp = solv->problems.elements + solution;
2701 return pp[0] || pp[1] ? solution : 0;
2703 pp = solv->problems.elements + solution;
2704 while (pp[0] || pp[1])
2707 solution = pp - solv->problems.elements;
2708 return pp[0] || pp[1] ? solution : 0;
2712 solver_next_solutionelement(Solver *solv, Id problem, Id solution, Id element, Id *p, Id *rp)
2715 element = element ? element + 2 : solution;
2716 pp = solv->problems.elements + element;
2717 if (!(pp[0] || pp[1]))
2725 /* this is basically the reverse of addrpmrulesforsolvable */
2727 solver_problemruleinfo(Solver *solv, Queue *job, Id rid, Id *depp, Id *sourcep, Id *targetp)
2729 Pool *pool = solv->pool;
2730 Repo *installed = solv->installed;
2734 Id p, *pp, req, *reqp, con, *conp, obs, *obsp, *dp;
2737 if (rid >= solv->updaterules)
2740 *sourcep = solv->installed->start + (rid - solv->updaterules);
2742 return SOLVER_PROBLEM_UPDATE_RULE;
2744 if (rid >= solv->jobrules)
2747 r = solv->rules + rid;
2748 p = solv->ruletojob.elements[rid - solv->jobrules];
2749 *depp = job->elements[p + 1];
2751 *targetp = job->elements[p];
2752 if (r->d == 0 && r->w2 == 0 && r->p == -SYSTEMSOLVABLE && job->elements[p] != SOLVER_INSTALL_SOLVABLE_ONE_OF)
2753 return SOLVER_PROBLEM_JOB_NOTHING_PROVIDES_DEP;
2754 return SOLVER_PROBLEM_JOB_RULE;
2756 r = solv->rules + rid;
2758 if (r->d == 0 && r->w2 == 0)
2760 /* a rpm rule assertion */
2761 s = pool->solvables - r->p;
2762 if (installed && !solv->fixsystem && s->repo == installed)
2764 assert(!dontfix); /* dontfix packages never have a neg assertion */
2767 /* see why the package is not installable */
2768 if (s->arch != ARCH_SRC && s->arch != ARCH_NOSRC && !pool_installable(pool, s))
2771 return SOLVER_PROBLEM_NOT_INSTALLABLE;
2773 /* check requires */
2776 reqp = s->repo->idarraydata + s->requires;
2777 while ((req = *reqp++) != 0)
2779 if (req == SOLVABLE_PREREQMARKER)
2781 dp = pool_whatprovides(pool, req);
2788 return SOLVER_PROBLEM_NOTHING_PROVIDES_DEP;
2791 assert(!solv->allowselfconflicts);
2792 assert(s->conflicts);
2793 conp = s->repo->idarraydata + s->conflicts;
2794 while ((con = *conp++) != 0)
2795 FOR_PROVIDES(p, pp, con)
2799 return SOLVER_PROBLEM_SELF_CONFLICT;
2803 s = pool->solvables - r->p;
2804 if (installed && !solv->fixsystem && s->repo == installed)
2806 if (r->d == 0 && r->w2 < 0)
2808 /* a package conflict */
2809 Solvable *s2 = pool->solvables - r->w2;
2812 if (installed && !solv->fixsystem && s2->repo == installed)
2815 /* if both packages have the same name and at least one of them
2816 * is not installed, they conflict */
2817 if (s->name == s2->name && (!installed || (s->repo != installed || s2->repo != installed)))
2822 return SOLVER_PROBLEM_SAME_NAME;
2825 /* check conflicts in both directions */
2828 conp = s->repo->idarraydata + s->conflicts;
2829 while ((con = *conp++) != 0)
2831 FOR_PROVIDES(p, pp, con)
2833 if (dontfix && pool->solvables[p].repo == installed)
2840 return SOLVER_PROBLEM_PACKAGE_CONFLICT;
2846 conp = s2->repo->idarraydata + s2->conflicts;
2847 while ((con = *conp++) != 0)
2849 FOR_PROVIDES(p, pp, con)
2851 if (dontfix2 && pool->solvables[p].repo == installed)
2858 return SOLVER_PROBLEM_PACKAGE_CONFLICT;
2862 /* check obsoletes in both directions */
2863 if ((!installed || s->repo != installed) && s->obsoletes)
2865 obsp = s->repo->idarraydata + s->obsoletes;
2866 while ((obs = *obsp++) != 0)
2868 FOR_PROVIDES(p, pp, obs)
2875 return SOLVER_PROBLEM_PACKAGE_OBSOLETES;
2879 if ((!installed || s2->repo != installed) && s2->obsoletes)
2881 obsp = s2->repo->idarraydata + s2->obsoletes;
2882 while ((obs = *obsp++) != 0)
2884 FOR_PROVIDES(p, pp, obs)
2891 return SOLVER_PROBLEM_PACKAGE_OBSOLETES;
2895 /* all cases checked, can't happen */
2898 /* simple requires */
2899 assert(s->requires);
2900 reqp = s->repo->idarraydata + s->requires;
2901 while ((req = *reqp++) != 0)
2903 if (req == SOLVABLE_PREREQMARKER)
2905 dp = pool_whatprovides(pool, req);
2908 if (*dp == r->w2 && dp[1] == 0)
2911 else if (dp - pool->whatprovidesdata == r->d)
2918 return SOLVER_PROBLEM_DEP_PROVIDERS_NOT_INSTALLABLE;
2922 findproblemrule_internal(Solver *solv, Id idx, Id *reqrp, Id *conrp, Id *sysrp, Id *jobrp)
2925 Id lreqr, lconr, lsysr, ljobr;
2929 lreqr = lconr = lsysr = ljobr = 0;
2930 while ((rid = solv->learnt_pool.elements[idx++]) != 0)
2933 if (rid >= solv->learntrules)
2934 findproblemrule_internal(solv, solv->learnt_why.elements[rid - solv->learntrules], &lreqr, &lconr, &lsysr, &ljobr);
2935 else if (rid >= solv->updaterules)
2940 else if (rid >= solv->jobrules)
2947 r = solv->rules + rid;
2948 if (!r->d && r->w2 < 0)
2955 if (r->d == 0 && r->w2 == 0 && !reqassert)
2957 /* prefer assertions (XXX: bad idea?) */
2963 else if (solv->installed && r->p < 0 && solv->pool->solvables[-r->p].repo == solv->installed)
2965 /* prefer rules of installed packages */
2966 Id op = *reqrp >= 0 ? solv->rules[*reqrp].p : -*reqrp;
2967 if (op <= 0 || solv->pool->solvables[op].repo != solv->installed)
2973 if (!*reqrp && lreqr)
2975 if (!*conrp && lconr)
2977 if (!*jobrp && ljobr)
2979 if (!*sysrp && lsysr)
2984 * search for a rule that describes the problem to the
2985 * user. A pretty hopeless task, actually. We currently
2986 * prefer simple requires.
2989 solver_findproblemrule(Solver *solv, Id problem)
2991 Id reqr, conr, sysr, jobr;
2992 Id idx = solv->problems.elements[problem - 1];
2993 reqr = conr = sysr = jobr = 0;
2994 findproblemrule_internal(solv, idx, &reqr, &conr, &sysr, &jobr);
3007 /* create reverse obsoletes map for installed solvables
3009 * for each installed solvable find which packages with *different* names
3010 * obsolete the solvable.
3011 * this index is used in policy_findupdatepackages if noupdateprovide is set.
3015 create_obsolete_index(Solver *solv)
3017 Pool *pool = solv->pool;
3019 Repo *installed = solv->installed;
3020 Id p, *pp, obs, *obsp, *obsoletes, *obsoletes_data;
3023 if (!installed || !installed->nsolvables)
3025 solv->obsoletes = obsoletes = sat_calloc(installed->end - installed->start, sizeof(Id));
3026 for (i = 1; i < pool->nsolvables; i++)
3028 s = pool->solvables + i;
3029 if (s->repo == installed)
3033 if (!pool_installable(pool, s))
3035 obsp = s->repo->idarraydata + s->obsoletes;
3036 while ((obs = *obsp++) != 0)
3037 FOR_PROVIDES(p, pp, obs)
3039 if (pool->solvables[p].repo != installed)
3041 if (pool->solvables[p].name == s->name)
3043 obsoletes[p - installed->start]++;
3047 for (i = 0; i < installed->nsolvables; i++)
3050 n += obsoletes[i] + 1;
3053 solv->obsoletes_data = obsoletes_data = sat_calloc(n + 1, sizeof(Id));
3054 POOL_DEBUG(SAT_DEBUG_STATS, "obsoletes data: %d entries\n", n + 1);
3055 for (i = pool->nsolvables - 1; i > 0; i--)
3057 s = pool->solvables + i;
3058 if (s->repo == installed)
3062 if (!pool_installable(pool, s))
3064 obsp = s->repo->idarraydata + s->obsoletes;
3065 while ((obs = *obsp++) != 0)
3066 FOR_PROVIDES(p, pp, obs)
3068 if (pool->solvables[p].repo != installed)
3070 if (pool->solvables[p].name == s->name)
3072 p -= installed->start;
3073 if (obsoletes_data[obsoletes[p]] != i)
3074 obsoletes_data[--obsoletes[p]] = i;
3080 removedisabledconflicts(Solver *solv, Queue *removed)
3082 Pool *pool = solv->pool;
3087 Id *decisionmap = solv->decisionmap;
3089 POOL_DEBUG(SAT_DEBUG_STATS, "removedisabledconflicts\n");
3090 queue_empty(removed);
3091 for (i = 0; i < solv->decisionq.count; i++)
3093 p = solv->decisionq.elements[i];
3096 /* a conflict. we never do conflicts on free decisions, so there
3097 * must have been an unit rule */
3098 why = solv->decisionq_why.elements[i];
3100 r = solv->rules + why;
3101 if (!r->w1 && decisionmap[-p])
3103 /* rule is now disabled, remove from decisionmap */
3104 POOL_DEBUG(SAT_DEBUG_STATS, "removing conflict for package %s[%d]\n", solvable2str(pool, pool->solvables - p), -p);
3105 queue_push(removed, -p);
3106 queue_push(removed, decisionmap[-p]);
3107 decisionmap[-p] = 0;
3110 if (!removed->count)
3112 /* we removed some confliced packages. some of them might still
3113 * be in conflict, so search for unit rules and re-conflict */
3115 for (i = n = 1, r = solv->rules + i; n < solv->nrules; i++, r++, n++)
3117 if (i == solv->nrules)
3120 r = solv->rules + i;
3126 if (r->p < 0 && !decisionmap[-r->p])
3132 if (r->p < 0 && decisionmap[-r->p] == 0 && DECISIONMAP_FALSE(r->w2))
3134 else if (r->w2 < 0 && decisionmap[-r->w2] == 0 && DECISIONMAP_FALSE(r->p))
3139 if (r->p < 0 && decisionmap[-r->p] == 0)
3141 if (new || DECISIONMAP_FALSE(r->p))
3143 dp = pool->whatprovidesdata + r->d;
3144 while ((p = *dp++) != 0)
3146 if (new && p == new)
3148 if (p < 0 && decisionmap[-p] == 0)
3157 else if (!DECISIONMAP_FALSE(p))
3167 POOL_DEBUG(SAT_DEBUG_STATS, "re-conflicting package %s[%d]\n", solvable2str(pool, pool->solvables - new), -new);
3168 decisionmap[-new] = -1;
3170 n = 0; /* redo all rules */
3176 weaken_solvable_deps(Solver *solv, Id p)
3181 for (i = 1, r = solv->rules + i; i < solv->jobrules; i++, r++)
3185 if (r->d == 0 && r->w2 < 0)
3186 continue; /* conflict */
3187 queue_push(&solv->weakruleq, i);
3191 /*-----------------------------------------------------------------*/
3201 solver_solve(Solver *solv, Queue *job)
3203 Pool *pool = solv->pool;
3204 Repo *installed = solv->installed;
3207 Map addedmap; /* '1' == have rpm-rules for solvable */
3208 Id how, what, weak, name, p, *pp, d;
3214 /* create whatprovides if not already there */
3215 if (!pool->whatprovides)
3216 pool_createwhatprovides(pool);
3218 /* create obsolete index if needed */
3219 if (solv->noupdateprovide)
3220 create_obsolete_index(solv);
3223 * create basic rule set of all involved packages
3224 * use addedmap bitmap to make sure we don't create rules twice
3228 map_init(&addedmap, pool->nsolvables);
3232 * always install our system solvable
3234 MAPSET(&addedmap, SYSTEMSOLVABLE);
3235 queue_push(&solv->decisionq, SYSTEMSOLVABLE);
3236 queue_push(&solv->decisionq_why, 0);
3237 solv->decisionmap[SYSTEMSOLVABLE] = 1;
3240 * create rules for all package that could be involved with the solving
3241 * so called: rpm rules
3246 oldnrules = solv->nrules;
3247 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for installed solvables ***\n");
3248 FOR_REPO_SOLVABLES(installed, p, s)
3249 addrpmrulesforsolvable(solv, s, &addedmap);
3250 POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for installed solvables\n", solv->nrules - oldnrules);
3251 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for updaters of installed solvables ***\n");
3252 oldnrules = solv->nrules;
3253 FOR_REPO_SOLVABLES(installed, p, s)
3254 addrpmrulesforupdaters(solv, s, &addedmap, 1);
3255 POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for updaters of installed solvables\n", solv->nrules - oldnrules);
3258 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for packages involved with a job ***\n");
3259 oldnrules = solv->nrules;
3260 for (i = 0; i < job->count; i += 2)
3262 how = job->elements[i] & ~SOLVER_WEAK;
3263 what = job->elements[i + 1];
3267 case SOLVER_INSTALL_SOLVABLE:
3268 addrpmrulesforsolvable(solv, pool->solvables + what, &addedmap);
3270 case SOLVER_INSTALL_SOLVABLE_NAME:
3271 case SOLVER_INSTALL_SOLVABLE_PROVIDES:
3272 name = (how == SOLVER_INSTALL_SOLVABLE_NAME) ? what : 0;
3273 while (ISRELDEP(name))
3275 Reldep *rd = GETRELDEP(pool, name);
3278 FOR_PROVIDES(p, pp, what)
3280 /* if by name, ensure that the name matches */
3281 if (name && pool->solvables[p].name != name)
3283 addrpmrulesforsolvable(solv, pool->solvables + p, &addedmap);
3286 case SOLVER_INSTALL_SOLVABLE_UPDATE:
3287 /* dont allow downgrade */
3288 addrpmrulesforupdaters(solv, pool->solvables + what, &addedmap, 0);
3290 case SOLVER_INSTALL_SOLVABLE_ONE_OF:
3291 pp = pool->whatprovidesdata + what;
3292 while ((p = *pp++) != 0)
3293 addrpmrulesforsolvable(solv, pool->solvables + p, &addedmap);
3297 POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for packages involved in a job\n", solv->nrules - oldnrules);
3299 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for recommended/suggested packages ***\n");
3301 oldnrules = solv->nrules;
3302 addrpmrulesforweak(solv, &addedmap);
3303 POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules because of weak dependencies\n", solv->nrules - oldnrules);
3305 IF_POOLDEBUG (SAT_DEBUG_STATS)
3307 int possible = 0, installable = 0;
3308 for (i = 1; i < pool->nsolvables; i++)
3310 if (pool_installable(pool, pool->solvables + i))
3312 if (MAPTST(&addedmap, i))
3315 POOL_DEBUG(SAT_DEBUG_STATS, "%d of %d installable solvables considered for solving\n", possible, installable);
3319 * first pass done, we now have all the rpm rules we need.
3320 * unify existing rules before going over all job rules and
3322 * at this point the system is always solvable,
3323 * as an empty system (remove all packages) is a valid solution
3326 unifyrules(solv); /* remove duplicate rpm rules */
3327 solv->directdecisions = solv->decisionq.count;
3329 POOL_DEBUG(SAT_DEBUG_STATS, "decisions so far: %d\n", solv->decisionq.count);
3330 IF_POOLDEBUG (SAT_DEBUG_SCHUBI)
3331 solver_printdecisions (solv);
3334 * now add all job rules
3337 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** Add JOB rules ***\n");
3339 solv->jobrules = solv->nrules;
3341 for (i = 0; i < job->count; i += 2)
3343 oldnrules = solv->nrules;
3345 how = job->elements[i] & ~SOLVER_WEAK;
3346 weak = job->elements[i] & SOLVER_WEAK;
3347 what = job->elements[i + 1];
3350 case SOLVER_INSTALL_SOLVABLE: /* install specific solvable */
3351 s = pool->solvables + what;
3352 POOL_DEBUG(SAT_DEBUG_JOB, "job: %sinstall solvable %s\n", weak ? "weak " : "", solvable2str(pool, s));
3353 addrule(solv, what, 0); /* install by Id */
3354 queue_push(&solv->ruletojob, i);
3356 queue_push(&solv->weakruleq, solv->nrules - 1);
3358 case SOLVER_ERASE_SOLVABLE:
3359 s = pool->solvables + what;
3360 POOL_DEBUG(SAT_DEBUG_JOB, "job: %serase solvable %s\n", weak ? "weak " : "", solvable2str(pool, s));
3361 addrule(solv, -what, 0); /* remove by Id */
3362 queue_push(&solv->ruletojob, i);
3364 queue_push(&solv->weakruleq, solv->nrules - 1);
3366 case SOLVER_INSTALL_SOLVABLE_NAME: /* install by capability */
3367 case SOLVER_INSTALL_SOLVABLE_PROVIDES:
3368 if (how == SOLVER_INSTALL_SOLVABLE_NAME)
3369 POOL_DEBUG(SAT_DEBUG_JOB, "job: %sinstall name %s\n", weak ? "weak " : "", dep2str(pool, what));
3370 if (how == SOLVER_INSTALL_SOLVABLE_PROVIDES)
3371 POOL_DEBUG(SAT_DEBUG_JOB, "job: %sinstall provides %s\n", weak ? "weak " : "", dep2str(pool, what));
3373 name = (how == SOLVER_INSTALL_SOLVABLE_NAME) ? what : 0;
3374 while (ISRELDEP(name))
3376 Reldep *rd = GETRELDEP(pool, name);
3379 FOR_PROVIDES(p, pp, what)
3381 /* if by name, ensure that the name matches */
3382 if (name && pool->solvables[p].name != name)
3388 /* no provider, make this an impossible rule */
3389 queue_push(&q, -SYSTEMSOLVABLE);
3392 p = queue_shift(&q); /* get first provider */
3394 d = 0; /* single provider ? -> make assertion */
3396 d = pool_queuetowhatprovides(pool, &q); /* get all providers */
3397 addrule(solv, p, d); /* add 'requires' rule */
3398 queue_push(&solv->ruletojob, i);
3400 queue_push(&solv->weakruleq, solv->nrules - 1);
3402 case SOLVER_ERASE_SOLVABLE_NAME: /* remove by capability */
3403 case SOLVER_ERASE_SOLVABLE_PROVIDES:
3404 if (how == SOLVER_ERASE_SOLVABLE_NAME)
3405 POOL_DEBUG(SAT_DEBUG_JOB, "job: %serase name %s\n", weak ? "weak " : "", dep2str(pool, what));
3406 if (how == SOLVER_ERASE_SOLVABLE_PROVIDES)
3407 POOL_DEBUG(SAT_DEBUG_JOB, "job: %serase provides %s\n", weak ? "weak " : "", dep2str(pool, what));
3408 name = (how == SOLVER_ERASE_SOLVABLE_NAME) ? what : 0;
3409 while (ISRELDEP(name))
3411 Reldep *rd = GETRELDEP(pool, name);
3414 FOR_PROVIDES(p, pp, what)
3416 /* if by name, ensure that the name matches */
3417 if (name && pool->solvables[p].name != name)
3419 addrule(solv, -p, 0); /* add 'remove' rule */
3420 queue_push(&solv->ruletojob, i);
3422 queue_push(&solv->weakruleq, solv->nrules - 1);
3425 case SOLVER_INSTALL_SOLVABLE_UPDATE: /* find update for solvable */
3426 s = pool->solvables + what;
3427 POOL_DEBUG(SAT_DEBUG_JOB, "job: %supdate %s\n", weak ? "weak " : "", solvable2str(pool, s));
3428 addupdaterule(solv, s, 0);
3429 queue_push(&solv->ruletojob, i);
3431 queue_push(&solv->weakruleq, solv->nrules - 1);
3433 case SOLVER_INSTALL_SOLVABLE_ONE_OF:
3434 POOL_DEBUG(SAT_DEBUG_JOB, "job: %sone of\n", weak ? "weak " : "");
3435 for (pp = pool->whatprovidesdata + what; *pp; pp++)
3436 POOL_DEBUG(SAT_DEBUG_JOB, " %s\n", solvable2str(pool, pool->solvables + *pp));
3437 addrule(solv, -SYSTEMSOLVABLE, what);
3438 queue_push(&solv->ruletojob, i);
3440 queue_push(&solv->weakruleq, solv->nrules - 1);
3442 case SOLVER_WEAKEN_SOLVABLE_DEPS:
3443 s = pool->solvables + what;
3444 POOL_DEBUG(SAT_DEBUG_JOB, "job: weaken deps %s\n", solvable2str(pool, s));
3445 weaken_solvable_deps(solv, what);
3448 IF_POOLDEBUG (SAT_DEBUG_JOB)
3451 if (solv->nrules == oldnrules)
3452 POOL_DEBUG(SAT_DEBUG_JOB, " - no rule created\n");
3453 for (j = oldnrules; j < solv->nrules; j++)
3455 POOL_DEBUG(SAT_DEBUG_JOB, " - job ");
3456 solver_printrule(solv, SAT_DEBUG_JOB, solv->rules + j);
3460 assert(solv->ruletojob.count == solv->nrules - solv->jobrules);
3463 * now add update rules
3467 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** Add update rules ***\n");
3472 * create rules for updating installed solvables
3476 solv->updaterules = solv->nrules;
3477 if (installed && !solv->allowuninstall)
3478 { /* loop over all installed solvables */
3479 /* we create all update rules, but disable some later on depending on the job */
3480 for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
3482 /* no update rules for patch atoms */
3483 if (s->freshens && !s->supplements)
3485 const char *name = id2str(pool, s->name);
3486 if (name[0] == 'a' && !strncmp(name, "atom:", 5))
3488 addrule(solv, 0, 0);
3492 if (s->repo == installed)
3493 addupdaterule(solv, s, 0); /* allowall = 0 */
3495 addrule(solv, 0, 0); /* create dummy rule */
3497 /* consistency check: we added a rule for _every_ installed solvable */
3498 assert(solv->nrules - solv->updaterules == installed->end - installed->start);
3501 /* create feature rules */
3502 /* those are used later on to keep a version of the installed packages in
3504 solv->featurerules = solv->nrules;
3507 for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
3509 if (s->freshens && !s->supplements)
3511 const char *name = id2str(pool, s->name);
3512 if (name[0] == 'a' && !strncmp(name, "atom:", 5))
3514 addrule(solv, 0, 0);
3518 if (s->repo == installed)
3521 addupdaterule(solv, s, 1); /* allowall = 0 */
3522 if (solv->allowuninstall)
3524 queue_push(&solv->weakruleq, solv->nrules - 1);
3527 r = solv->rules + solv->nrules - 1;
3528 sr = r - (installed->end - installed->start);
3530 disablerule(solv, r);
3531 if (sr->p && !unifyrules_sortcmp(r, sr))
3533 /* identical rule, kill feature rule */
3534 memset(r, 0, sizeof(*r));
3538 addrule(solv, 0, 0); /* create dummy rule */
3540 assert(solv->nrules - solv->featurerules == installed->end - installed->start);
3543 /* free unneeded memory */
3544 map_free(&addedmap);
3547 /* create weak map */
3548 map_init(&solv->weakrulemap, solv->nrules);
3549 for (i = 0; i < solv->weakruleq.count; i++)
3551 p = solv->weakruleq.elements[i];
3552 MAPSET(&solv->weakrulemap, p);
3555 /* all new rules are learnt after this point */
3556 solv->learntrules = solv->nrules;
3558 /* disable update rules that conflict with our job */
3559 disableupdaterules(solv, job, -1);
3562 /* make decisions based on job/update assertions */
3563 makeruledecisions(solv);
3565 /* create watches chains */
3568 POOL_DEBUG(SAT_DEBUG_STATS, "problems so far: %d\n", solv->problems.count);
3571 run_solver(solv, 1, solv->dontinstallrecommended ? 0 : 1);
3575 /* disable all erase jobs (continuing weak "keep uninstalled" rules) */
3576 for (i = solv->jobrules, r = solv->rules + i; i < solv->updaterules; i++, r++)
3580 if (r->p > 0) /* install job? */
3582 disablerule(solv, r);
3588 enabledisablelearntrules(solv);
3589 removedisabledconflicts(solv, &redoq);
3592 /* find recommended packages */
3593 /* if redoq.count == 0 we already found all recommended in the
3595 if (redoq.count || solv->dontinstallrecommended)
3597 Id rec, *recp, p, *pp;
3599 /* create map of all suggests that are still open */
3600 solv->recommends_index = -1;
3601 MAPZERO(&solv->recommendsmap);
3602 for (i = 0; i < solv->decisionq.count; i++)
3604 p = solv->decisionq.elements[i];
3607 s = pool->solvables + p;
3610 recp = s->repo->idarraydata + s->recommends;
3611 while ((rec = *recp++) != 0)
3613 FOR_PROVIDES(p, pp, rec)
3614 if (solv->decisionmap[p] > 0)
3617 continue; /* p != 0: already fulfilled */
3618 FOR_PROVIDES(p, pp, rec)
3619 MAPSET(&solv->recommendsmap, p);
3623 for (i = 1; i < pool->nsolvables; i++)
3625 if (solv->decisionmap[i] != 0)
3627 s = pool->solvables + i;
3628 if (!MAPTST(&solv->recommendsmap, i))
3630 if (!s->supplements)
3632 if (!pool_installable(pool, s))
3634 if (!solver_is_supplementing(solv, s))
3637 if (solv->dontinstallrecommended)
3638 queue_push(&solv->recommendations, i);
3640 queue_pushunique(&solv->recommendations, i);
3642 /* we use MODE_SUGGEST here so that repo prio is ignored */
3643 policy_filter_unwanted(solv, &solv->recommendations, 0, POLICY_MODE_SUGGEST);
3646 /* find suggested packages */
3649 Id sug, *sugp, p, *pp;
3651 /* create map of all suggests that are still open */
3652 solv->recommends_index = -1;
3653 MAPZERO(&solv->suggestsmap);
3654 for (i = 0; i < solv->decisionq.count; i++)
3656 p = solv->decisionq.elements[i];
3659 s = pool->solvables + p;
3662 sugp = s->repo->idarraydata + s->suggests;
3663 while ((sug = *sugp++) != 0)
3665 FOR_PROVIDES(p, pp, sug)
3666 if (solv->decisionmap[p] > 0)
3669 continue; /* already fulfilled */
3670 FOR_PROVIDES(p, pp, sug)
3671 MAPSET(&solv->suggestsmap, p);
3675 for (i = 1; i < pool->nsolvables; i++)
3677 if (solv->decisionmap[i] != 0)
3679 s = pool->solvables + i;
3680 if (!MAPTST(&solv->suggestsmap, i))
3684 if (!pool_installable(pool, s))
3686 if (!solver_is_enhancing(solv, s))
3689 queue_push(&solv->suggestions, i);
3691 policy_filter_unwanted(solv, &solv->suggestions, 0, POLICY_MODE_SUGGEST);
3696 /* restore decisionmap */
3697 for (i = 0; i < redoq.count; i += 2)
3698 solv->decisionmap[redoq.elements[i]] = redoq.elements[i + 1];
3702 if (solv->problems.count)
3704 int recocount = solv->recommendations.count;
3705 solv->recommendations.count = 0; /* so that revert() doesn't mess with it */
3706 queue_empty(&redoq);
3707 for (i = 0; i < solv->decisionq.count; i++)
3709 Id p = solv->decisionq.elements[i];
3710 queue_push(&redoq, p);
3711 queue_push(&redoq, solv->decisionq_why.elements[i]);
3712 queue_push(&redoq, solv->decisionmap[p > 0 ? p : -p]);
3714 problems_to_solutions(solv, job);
3715 memset(solv->decisionmap, 0, pool->nsolvables * sizeof(Id));
3716 queue_empty(&solv->decisionq);
3717 queue_empty(&solv->decisionq_why);
3718 for (i = 0; i < redoq.count; i += 3)
3720 Id p = redoq.elements[i];
3721 queue_push(&solv->decisionq, p);
3722 queue_push(&solv->decisionq_why, redoq.elements[i + 1]);
3723 solv->decisionmap[p > 0 ? p : -p] = redoq.elements[i + 2];
3725 solv->recommendations.count = recocount;
3730 /***********************************************************************/
3733 solver_calc_duchanges(Solver *solv, DUChanges *mps, int nmps)
3737 solver_create_state_maps(solv, &installedmap, 0);
3738 pool_calc_duchanges(solv->pool, solv->installed, &installedmap, mps, nmps);
3739 map_free(&installedmap);
3743 solver_calc_installsizechange(Solver *solv)
3748 solver_create_state_maps(solv, &installedmap, 0);
3749 change = pool_calc_installsizechange(solv->pool, solv->installed, &installedmap);
3750 map_free(&installedmap);