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
29 #define RULES_BLOCK 63
30 #define REGARD_RECOMMENDS_OF_INSTALLED_ITEMS 0
34 solver_splitprovides(Solver *solv, Id dep)
36 Pool *pool = solv->pool;
41 if (!solv->dosplitprovides || !solv->installed)
45 rd = GETRELDEP(pool, dep);
46 if (rd->flags != REL_WITH)
48 FOR_PROVIDES(p, pp, dep)
50 s = pool->solvables + p;
51 if (s->repo == solv->installed && s->name == rd->name)
58 solver_dep_installed(Solver *solv, Id dep)
61 Pool *pool = solv->pool;
66 Reldep *rd = GETRELDEP(pool, dep);
67 if (rd->flags == REL_AND)
69 if (!solver_dep_installed(solv, rd->name))
71 return solver_dep_installed(solv, rd->evr);
73 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
74 return solver_dep_installed(solv, rd->evr);
76 FOR_PROVIDES(p, pp, dep)
78 if (p == SYSTEMSOLVABLE || (solv->installed && pool->solvables[p].repo == solv->installed))
86 /* this mirrors solver_dep_fulfilled but uses map m instead of the decisionmap */
88 dep_possible(Solver *solv, Id dep, Map *m)
90 Pool *pool = solv->pool;
95 Reldep *rd = GETRELDEP(pool, dep);
96 if (rd->flags == REL_AND)
98 if (!dep_possible(solv, rd->name, m))
100 return dep_possible(solv, rd->evr, m);
102 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
103 return solver_splitprovides(solv, rd->evr);
104 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
105 return solver_dep_installed(solv, rd->evr);
107 FOR_PROVIDES(p, pp, dep)
115 /*-----------------------------------------------------------------*/
122 printruleelement(Solver *solv, int type, Rule *r, Id v)
124 Pool *pool = solv->pool;
128 s = pool->solvables + -v;
129 POOL_DEBUG(type, " !%s [%d]", solvable2str(pool, s), -v);
133 s = pool->solvables + v;
134 POOL_DEBUG(type, " %s [%d]", solvable2str(pool, s), v);
139 POOL_DEBUG(type, " (w1)");
141 POOL_DEBUG(type, " (w2)");
143 if (solv->decisionmap[s - pool->solvables] > 0)
144 POOL_DEBUG(type, " Install.level%d", solv->decisionmap[s - pool->solvables]);
145 if (solv->decisionmap[s - pool->solvables] < 0)
146 POOL_DEBUG(type, " Conflict.level%d", -solv->decisionmap[s - pool->solvables]);
147 POOL_DEBUG(type, "\n");
156 printrule(Solver *solv, int type, Rule *r)
158 Pool *pool = solv->pool;
162 if (r >= solv->rules && r < solv->rules + solv->nrules) /* r is a solver rule */
163 POOL_DEBUG(type, "Rule #%d:", (int)(r - solv->rules));
165 POOL_DEBUG(type, "Rule:"); /* r is any rule */
167 POOL_DEBUG(type, " (disabled)");
168 POOL_DEBUG(type, "\n");
172 /* print direct literal */
174 else if (r->d == ID_NULL)
178 /* binary rule --> print w2 as second literal */
182 /* every other which is in d */
183 v = solv->pool->whatprovidesdata[r->d + i - 1];
186 printruleelement(solv, type, r, v);
188 POOL_DEBUG(type, " next rules: %d %d\n", r->n1, r->n2);
192 printruleclass(Solver *solv, int type, Rule *r)
194 Pool *pool = solv->pool;
195 if (r - solv->rules >= solv->learntrules)
196 POOL_DEBUG(type, "LEARNT ");
197 else if (r - solv->rules >= solv->weakrules)
198 POOL_DEBUG(type, "WEAK ");
199 else if (r - solv->rules >= solv->systemrules)
200 POOL_DEBUG(type, "SYSTEM ");
201 else if (r - solv->rules >= solv->jobrules)
202 POOL_DEBUG(type, "JOB ");
203 printrule(solv, type, r);
207 /*-----------------------------------------------------------------*/
213 static Pool *unifyrules_sortcmp_data;
216 * compare rules for unification sort
220 unifyrules_sortcmp(const void *ap, const void *bp)
222 Pool *pool = unifyrules_sortcmp_data;
223 Rule *a = (Rule *)ap;
224 Rule *b = (Rule *)bp;
230 return x; /* p differs */
233 if (a->d == 0 && b->d == 0)
234 return a->w2 - b->w2; /* assertion: return w2 diff */
236 if (a->d == 0) /* a is assertion, b not */
238 x = a->w2 - pool->whatprovidesdata[b->d];
242 if (b->d == 0) /* b is assertion, a not */
244 x = pool->whatprovidesdata[a->d] - b->w2;
248 /* compare whatprovidesdata */
249 ad = pool->whatprovidesdata + a->d;
250 bd = pool->whatprovidesdata + b->d;
252 if ((x = *ad++ - *bd++) != 0)
263 unifyrules(Solver *solv)
265 Pool *pool = solv->pool;
269 if (solv->nrules <= 1) /* nothing to unify */
272 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- unifyrules -----\n");
274 /* sort rules first */
275 unifyrules_sortcmp_data = solv->pool;
276 qsort(solv->rules + 1, solv->nrules - 1, sizeof(Rule), unifyrules_sortcmp);
283 for (i = j = 1, ir = solv->rules + 1; i < solv->nrules; i++, ir++)
285 if (jr && !unifyrules_sortcmp(ir, jr))
286 continue; /* prune! */
287 jr = solv->rules + j++; /* keep! */
292 /* reduced count from nrules to j rules */
293 POOL_DEBUG(SAT_DEBUG_STATS, "pruned rules from %d to %d\n", solv->nrules, j);
295 /* adapt rule buffer */
297 solv->rules = sat_extend_resize(solv->rules, solv->nrules, sizeof(Rule), RULES_BLOCK);
298 IF_POOLDEBUG (SAT_DEBUG_STATS)
305 for (i = 1; i < solv->nrules; i++)
312 dp = solv->pool->whatprovidesdata + r->d;
317 POOL_DEBUG(SAT_DEBUG_STATS, " binary: %d\n", binr);
318 POOL_DEBUG(SAT_DEBUG_STATS, " normal: %d, %d literals\n", solv->nrules - 1 - binr, lits);
320 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- unifyrules end -----\n");
330 hashrule(Solver *solv, Id p, Id d, int n)
332 unsigned int x = (unsigned int)p;
336 return (x * 37) ^ (unsigned int)d;
337 dp = solv->pool->whatprovidesdata + d;
339 x = (x * 37) ^ (unsigned int)*dp++;
347 * p = direct literal; always < 0 for installed rpm rules
348 * d, if < 0 direct literal, if > 0 offset into whatprovides, if == 0 rule is assertion (look at p only)
351 * A requires b, b provided by B1,B2,B3 => (-A|B1|B2|B3)
353 * p < 0 : pkg id of A
354 * d > 0 : Offset in whatprovidesdata (list of providers of b)
356 * A conflicts b, b provided by B1,B2,B3 => (-A|-B1), (-A|-B2), (-A|-B3)
357 * p < 0 : pkg id of A
358 * d < 0 : Id of solvable (e.g. B1)
360 * d == 0: unary rule, assertion => (A) or (-A)
362 * Install: p > 0, d = 0 (A) user requested install
363 * Remove: p < 0, d = 0 (-A) user requested remove
364 * Requires: p < 0, d > 0 (-A|B1|B2|...) d: <list of providers for requirement of p>
365 * Updates: p > 0, d > 0 (A|B1|B2|...) d: <list of updates for solvable p>
366 * Conflicts: p < 0, d < 0 (-A|-B) either p (conflict issuer) or d (conflict provider) (binary rule)
367 * ? p > 0, d < 0 (A|-B)
368 * No-op ?: p = 0, d = 0 (null) (used as policy rule placeholder)
372 * Direct assertion (no watch needed)( if d <0 ) --> d = 0, w1 = p, w2 = 0
373 * Binary rule: p = first literal, d = 0, w2 = second literal, w1 = p
374 * every other : w1 = p, w2 = whatprovidesdata[d];
375 * Disabled rule: w1 = 0
377 * always returns a rule for non-rpm rules
381 addrule(Solver *solv, Id p, Id d)
383 Pool *pool = solv->pool;
387 int n = 0; /* number of literals in rule - 1
388 0 = direct assertion (single literal)
392 /* it often happenes that requires lead to adding the same rpm rule
393 * multiple times, so we prune those duplicates right away to make
394 * the work for unifyrules a bit easier */
396 if (solv->nrules && !solv->jobrules)
398 r = solv->rules + solv->nrules - 1; /* get the last added rule */
399 if (r->p == p && r->d == d && d != 0) /* identical and not user requested */
405 /* always a binary rule */
407 return 0; /* ignore self conflict */
412 for (dp = pool->whatprovidesdata + d; *dp; dp++, n++)
414 return 0; /* rule is self-fulfilling */
416 d = dp[-1]; /* take single literal */
419 if (n == 0 && !solv->jobrules)
421 /* this is a rpm rule assertion, we do not have to allocate it */
422 /* it can be identified by a level of 1 and a zero reason */
423 /* we must not drop those rules from the decisionq when rewinding! */
425 assert(solv->decisionmap[-p] == 0 || solv->decisionmap[-p] == -1);
426 if (solv->decisionmap[-p])
427 return 0; /* already got that one */
428 queue_push(&solv->decisionq, p);
429 queue_push(&solv->decisionq_why, 0);
430 solv->decisionmap[-p] = -1;
435 /* smallest literal first so we can find dups */
439 n = 1; /* re-set n, was used as temp var */
442 /* check if the last added rule is exactly the same as what we're looking for. */
443 if (r && n == 1 && !r->d && r->p == p && r->w2 == d)
444 return r; /* binary rule */
446 if (r && n > 1 && r->d && r->p == p)
448 /* Rule where d is an offset in whatprovidesdata */
452 dp2 = pool->whatprovidesdata + r->d;
453 for (dp = pool->whatprovidesdata + d; *dp; dp++, dp2++)
464 /* extend rule buffer */
465 solv->rules = sat_extend(solv->rules, solv->nrules, 1, sizeof(Rule), RULES_BLOCK);
466 r = solv->rules + solv->nrules++; /* point to rule space */
471 /* direct assertion, no watch needed */
487 r->w2 = pool->whatprovidesdata[d];
492 IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION)
494 POOL_DEBUG(SAT_DEBUG_RULE_CREATION, " Add rule: ");
495 printrule(solv, SAT_DEBUG_RULE_CREATION, r);
502 disablerule(Solver *solv, Rule *r)
508 enablerule(Solver *solv, Rule *r)
510 if (r->d == 0 || r->w2 != r->p)
513 r->w1 = solv->pool->whatprovidesdata[r->d];
517 /**********************************************************************************/
519 /* a problem is an item on the solver's problem list. It can either be >0, in that
520 * case it is a system (upgrade) rule, or it can be <0, which makes it refer to a job
521 * consisting of multiple job rules.
525 disableproblem(Solver *solv, Id v)
533 disablerule(solv, solv->rules + v);
537 jp = solv->ruletojob.elements;
538 for (i = solv->jobrules, r = solv->rules + i; i < solv->systemrules; i++, r++, jp++)
540 disablerule(solv, r);
544 enableproblem(Solver *solv, Id v)
552 enablerule(solv, solv->rules + v);
556 jp = solv->ruletojob.elements;
557 for (i = solv->jobrules, r = solv->rules + i; i < solv->systemrules; i++, r++, jp++)
563 printproblem(Solver *solv, Id v)
565 Pool *pool = solv->pool;
571 printrule(solv, SAT_DEBUG_SOLUTIONS, solv->rules + v);
575 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "JOB %d\n", v);
576 jp = solv->ruletojob.elements;
577 for (i = solv->jobrules, r = solv->rules + i; i < solv->systemrules; i++, r++, jp++)
580 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "- ");
581 printrule(solv, SAT_DEBUG_SOLUTIONS, r);
583 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "ENDJOB\n");
589 /************************************************************************/
591 /* go through system and job rules and add direct assertions
592 * to the decisionqueue. If we find a conflict, disable rules and
593 * add them to problem queue.
596 makeruledecisions(Solver *solv)
598 Pool *pool = solv->pool;
604 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- makeruledecisions ; size decisionq: %d -----\n",solv->decisionq.count);
606 decisionstart = solv->decisionq.count;
608 /* FIXME: For the time being we first need to assert what we can get
609 from learned rules. Currently it can happen that we learn a unit
610 rule (i.e. assertion) in direct conflict with e.g. a job unit rule. The
611 input problem was unsolvable, but we can't deal with this situation
612 of two conflicting assertions (see also FIXME at refine_suggestion).
614 What normally would happen (without this loop), we would first see the
615 job rule (and let's say decide to install A), and later see the learned
616 rule (which says don't install A), have a conflict, and assert, because
617 we don't ever expect to see conflicts with learned rules.
619 So we gather assertions from learned rules first. This then leads
620 to a conflict with a job rule, which is dealt with (mostly). We note
621 that job rule as a problem (and don't remember the learned rule as a
622 problem like we would normally do, as even other code doesn't expect to
623 see learned rules in problem descriptions.
625 We need to deal with this situation in a better way, preferably by
626 never learning unit rules in conflicts with any other unit rule. */
628 for (ri = solv->learntrules, r = solv->rules + ri; ri < solv->nrules; ri++, r++)
630 if (!r->w1 || r->w2) /* disabled or no assertion */
634 if (solv->decisionmap[vv] == 0)
636 queue_push(&solv->decisionq, v);
637 queue_push(&solv->decisionq_why, r - solv->rules);
638 solv->decisionmap[vv] = v > 0 ? 1 : -1;
639 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
641 Solvable *s = solv->pool->solvables + vv;
643 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "conflicting %s (assertion)\n", solvable2str(solv->pool, s));
645 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "installing %s (assertion)\n", solvable2str(solv->pool, s));
649 if (v > 0 && solv->decisionmap[vv] > 0)
651 if (v < 0 && solv->decisionmap[vv] < 0)
653 /* found a conflict, which can't happen with learned rules. */
657 /* rpm rules don't have assertions, so we can start with the job
659 for (ri = solv->jobrules, r = solv->rules + ri; ri < solv->nrules; ri++, r++)
661 if (!r->w1 || r->w2) /* disabled or no assertion */
665 if (solv->decisionmap[vv] == 0)
667 queue_push(&solv->decisionq, v);
668 queue_push(&solv->decisionq_why, r - solv->rules);
669 solv->decisionmap[vv] = v > 0 ? 1 : -1;
670 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
672 Solvable *s = solv->pool->solvables + vv;
674 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "conflicting %s (assertion)\n", solvable2str(solv->pool, s));
676 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "installing %s (assertion)\n", solvable2str(solv->pool, s));
680 if (v > 0 && solv->decisionmap[vv] > 0)
682 if (v < 0 && solv->decisionmap[vv] < 0)
684 /* found a conflict! */
685 /* ri >= learntrules cannot happen, as this would mean that the
686 * problem was not solvable, so we wouldn't have created the
687 * learnt rule at all */
688 assert(ri < solv->learntrules);
689 /* if we are weak, just disable ourself */
690 if (ri >= solv->weakrules)
692 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "assertion conflict, but I am weak, disabling ");
693 printrule(solv, SAT_DEBUG_UNSOLVABLE, r);
694 disablerule(solv, r);
698 /* only job and system rules left in the decisionq*/
699 /* find the decision which is the "opposite" of the jobrule */
700 for (i = 0; i < solv->decisionq.count; i++)
701 if (solv->decisionq.elements[i] == -v)
703 assert(i < solv->decisionq.count);
704 if (solv->decisionq_why.elements[i] == 0)
706 /* conflict with rpm rule, need only disable our rule */
707 assert(v > 0 || v == -SYSTEMSOLVABLE);
709 queue_push(&solv->problems, solv->learnt_pool.count);
710 queue_push(&solv->learnt_pool, ri);
711 queue_push(&solv->learnt_pool, v != -SYSTEMSOLVABLE ? -v : v);
712 queue_push(&solv->learnt_pool, 0);
713 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "conflict with rpm rule, disabling rule #%d\n", ri);
714 if (ri < solv->systemrules)
715 v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
718 queue_push(&solv->problems, v);
719 queue_push(&solv->problems, 0);
720 disableproblem(solv, v);
724 /* conflict with another job or system rule */
726 queue_push(&solv->problems, solv->learnt_pool.count);
727 queue_push(&solv->learnt_pool, ri);
728 queue_push(&solv->learnt_pool, solv->decisionq_why.elements[i]);
729 queue_push(&solv->learnt_pool, 0);
731 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "conflicting system/job assertions over literal %d\n", vv);
732 /* push all of our rules asserting this literal on the problem stack */
733 for (i = solv->jobrules, rr = solv->rules + i; i < solv->nrules; i++, rr++)
735 if (!rr->w1 || rr->w2)
737 if (rr->p != vv && rr->p != -vv)
739 /* See the large comment in front of the very first loop in this
740 function at FIXME. */
741 if (i >= solv->learntrules)
743 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, " - disabling rule #%d\n", i);
745 if (i < solv->systemrules)
746 v = -(solv->ruletojob.elements[i - solv->jobrules] + 1);
747 queue_push(&solv->problems, v);
748 disableproblem(solv, v);
750 queue_push(&solv->problems, 0);
753 while (solv->decisionq.count > decisionstart)
755 v = solv->decisionq.elements[--solv->decisionq.count];
756 --solv->decisionq_why.count;
758 solv->decisionmap[vv] = 0;
760 ri = solv->jobrules - 1;
761 r = solv->rules + ri;
764 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- makeruledecisions end; size decisionq: %d -----\n",solv->decisionq.count);
768 * we have enabled or disabled some of our rules. We now reenable all
769 * of our learnt rules but the ones that were learnt from rules that
773 enabledisablelearntrules(Solver *solv)
775 Pool *pool = solv->pool;
780 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "enabledisablelearntrules called\n");
781 for (i = solv->learntrules, r = solv->rules + i; i < solv->nrules; i++, r++)
783 whyp = solv->learnt_pool.elements + solv->learnt_why.elements[i - solv->learntrules];
784 while ((why = *whyp++) != 0)
787 continue; /* rpm assertion */
789 if (!solv->rules[why].w1)
792 /* why != 0: we found a disabled rule, disable the learnt rule */
795 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
797 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "disabling learnt ");
798 printrule(solv, SAT_DEBUG_SOLUTIONS, r);
800 disablerule(solv, r);
802 else if (!why && !r->w1)
804 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
806 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "re-enabling learnt ");
807 printrule(solv, SAT_DEBUG_SOLUTIONS, r);
815 /* FIXME: bad code ahead, replace as soon as possible */
817 disableupdaterules(Solver *solv, Queue *job, int jobidx)
819 Pool *pool = solv->pool;
821 Id how, what, p, *pp;
827 installed = solv->installed;
833 how = job->elements[jobidx];
836 case SOLVER_INSTALL_SOLVABLE:
837 case SOLVER_ERASE_SOLVABLE:
838 case SOLVER_ERASE_SOLVABLE_NAME:
839 case SOLVER_ERASE_SOLVABLE_PROVIDES:
845 /* go through all enabled job rules */
846 MAPZERO(&solv->noupdate);
847 for (i = solv->jobrules; i < solv->systemrules; i++)
850 if (!r->w1) /* disabled? */
852 j = solv->ruletojob.elements[i - solv->jobrules];
856 how = job->elements[j];
857 what = job->elements[j + 1];
860 case SOLVER_INSTALL_SOLVABLE: /* install specific solvable */
861 s = pool->solvables + what;
862 FOR_PROVIDES(p, pp, s->name)
864 if (pool->solvables[p].name != s->name)
866 if (pool->solvables[p].repo == installed)
867 MAPSET(&solv->noupdate, p - installed->start);
870 case SOLVER_ERASE_SOLVABLE:
871 s = pool->solvables + what;
872 if (s->repo == installed)
873 MAPSET(&solv->noupdate, what - installed->start);
875 case SOLVER_ERASE_SOLVABLE_NAME: /* remove by capability */
876 case SOLVER_ERASE_SOLVABLE_PROVIDES:
877 FOR_PROVIDES(p, pp, what)
879 if (how == SOLVER_ERASE_SOLVABLE_NAME && pool->solvables[p].name != what)
881 if (pool->solvables[p].repo == installed)
882 MAPSET(&solv->noupdate, p - installed->start);
890 /* fixup update rule status */
891 if (solv->allowuninstall)
892 return; /* no update rules at all */
896 /* we just disabled job #jobidx. enable all update rules
897 * that aren't disabled by the remaining job rules */
898 how = job->elements[jobidx];
899 what = job->elements[jobidx + 1];
902 case SOLVER_INSTALL_SOLVABLE:
903 s = pool->solvables + what;
904 FOR_PROVIDES(p, pp, s->name)
906 if (pool->solvables[p].name != s->name)
908 if (pool->solvables[p].repo != installed)
910 if (MAPTST(&solv->noupdate, p - installed->start))
912 r = solv->rules + solv->systemrules + (p - installed->start);
916 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
918 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
919 printrule(solv, SAT_DEBUG_SOLUTIONS, r);
923 case SOLVER_ERASE_SOLVABLE:
924 s = pool->solvables + what;
925 if (s->repo != installed)
927 if (MAPTST(&solv->noupdate, what - installed->start))
929 r = solv->rules + solv->systemrules + (what - installed->start);
933 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
935 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
936 printrule(solv, SAT_DEBUG_SOLUTIONS, r);
939 case SOLVER_ERASE_SOLVABLE_NAME: /* remove by capability */
940 case SOLVER_ERASE_SOLVABLE_PROVIDES:
941 FOR_PROVIDES(p, pp, what)
943 if (how == SOLVER_ERASE_SOLVABLE_NAME && pool->solvables[p].name != what)
945 if (pool->solvables[p].repo != installed)
947 if (MAPTST(&solv->noupdate, p - installed->start))
949 r = solv->rules + solv->systemrules + (p - installed->start);
953 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
955 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
956 printrule(solv, SAT_DEBUG_SOLUTIONS, r);
966 for (i = 0; i < installed->nsolvables; i++)
968 r = solv->rules + solv->systemrules + i;
969 if (r->w1 && MAPTST(&solv->noupdate, i))
970 disablerule(solv, r); /* was enabled, need to disable */
976 addpatchatomrequires(Solver *solv, Solvable *s, Id *dp, Queue *q, Map *m)
978 Pool *pool = solv->pool;
979 Id fre, *frep, p, *pp, ndp;
985 queue_init_buffer(&fq, qbuf, sizeof(qbuf)/sizeof(*qbuf));
986 queue_push(&fq, -(s - pool->solvables));
988 queue_push(&fq, *dp);
989 ndp = pool_queuetowhatprovides(pool, &fq);
990 frep = s->repo->idarraydata + s->freshens;
991 while ((fre = *frep++) != 0)
993 FOR_PROVIDES(p, pp, fre)
995 ps = pool->solvables + p;
996 addrule(solv, -p, ndp);
1004 for (i = 1; i < fq.count; i++)
1016 * add (install) rules for solvable
1017 * for unfulfilled requirements, conflicts, obsoletes,....
1018 * add a negative assertion for solvables that are not installable
1022 addrpmrulesforsolvable(Solver *solv, Solvable *s, Map *m)
1024 Pool *pool = solv->pool;
1025 Repo *installed = solv->installed;
1040 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforsolvable -----\n");
1042 queue_init_buffer(&q, qbuf, sizeof(qbuf)/sizeof(*qbuf));
1043 queue_push(&q, s - pool->solvables); /* push solvable Id */
1049 * s: Pointer to solvable
1052 n = queue_shift(&q);
1053 if (MAPTST(m, n)) /* continue if already done */
1057 s = pool->solvables + n; /* s = Solvable in question */
1060 if (installed /* Installed system available */
1061 && !solv->fixsystem /* NOT repair errors in rpm dependency graph */
1062 && s->repo == installed) /* solvable is installed? */
1064 dontfix = 1; /* dont care about broken rpm deps */
1067 if (!dontfix && s->arch != ARCH_SRC && s->arch != ARCH_NOSRC && !pool_installable(pool, s))
1069 POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "package %s [%d] is not installable\n", solvable2str(pool, s), (Id)(s - pool->solvables));
1070 addrule(solv, -n, 0); /* uninstallable */
1074 if (s->freshens && !s->supplements)
1076 const char *name = id2str(pool, s->name);
1077 if (name[0] == 'a' && !strncmp(name, "atom:", 5))
1081 /*-----------------------------------------
1082 * check requires of s
1087 reqp = s->repo->idarraydata + s->requires;
1088 while ((req = *reqp++) != 0) /* go throw all requires */
1090 if (req == SOLVABLE_PREREQMARKER) /* skip the marker */
1093 dp = pool_whatprovides(pool, req);
1095 if (*dp == SYSTEMSOLVABLE) /* always installed */
1101 addpatchatomrequires(solv, s, dp, &q, m);
1107 /* the strategy here is to not insist on dependencies
1108 * that are already broken. so if we find one provider
1109 * that was already installed, we know that the
1110 * dependency was not broken before so we enforce it */
1111 for (i = 0; (p = dp[i]) != 0; i++) /* for all providers */
1113 if (pool->solvables[p].repo == installed)
1114 break; /* provider was installed */
1116 if (!p) /* previously broken dependency */
1118 POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "ignoring broken requires %s of installed package %s\n", dep2str(pool, req), solvable2str(pool, s));
1125 /* nothing provides req! */
1126 POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "package %s [%d] is not installable (%s)\n", solvable2str(pool, s), (Id)(s - pool->solvables), dep2str(pool, req));
1127 addrule(solv, -n, 0); /* mark requestor as uninstallable */
1131 IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION)
1133 POOL_DEBUG(SAT_DEBUG_RULE_CREATION," %s requires %s\n", solvable2str(pool, s), dep2str(pool, req));
1134 for (i = 0; dp[i]; i++)
1135 POOL_DEBUG(SAT_DEBUG_RULE_CREATION, " provided by %s\n", solvable2str(pool, pool->solvables + dp[i]));
1138 /* add 'requires' dependency */
1139 /* rule: (-requestor|provider1|provider2|...|providerN) */
1140 addrule(solv, -n, dp - pool->whatprovidesdata);
1142 /* descend the dependency tree */
1143 for (; *dp; dp++) /* loop through all providers */
1145 if (!MAPTST(m, *dp))
1146 queue_push(&q, *dp);
1149 } /* while, requirements of n */
1151 } /* if, requirements */
1153 /* that's all we check for src packages */
1154 if (s->arch == ARCH_SRC || s->arch == ARCH_NOSRC)
1157 /*-----------------------------------------
1158 * check conflicts of s
1163 conp = s->repo->idarraydata + s->conflicts;
1164 while ((con = *conp++) != 0)
1166 FOR_PROVIDES(p, pp, con)
1168 /* dontfix: dont care about conflicts with already installed packs */
1169 if (dontfix && pool->solvables[p].repo == installed)
1171 /* rule: -n|-p: either solvable _or_ provider of conflict */
1172 addrule(solv, -n, -p);
1177 /*-----------------------------------------
1178 * check obsoletes if not installed
1180 if (!installed || pool->solvables[n].repo != installed)
1181 { /* not installed */
1184 obsp = s->repo->idarraydata + s->obsoletes;
1185 while ((obs = *obsp++) != 0)
1187 FOR_PROVIDES(p, pp, obs)
1188 addrule(solv, -n, -p);
1191 FOR_PROVIDES(p, pp, s->name)
1193 if (s->name == pool->solvables[p].name)
1194 addrule(solv, -n, -p);
1198 /*-----------------------------------------
1199 * add recommends to the rule list
1203 recp = s->repo->idarraydata + s->recommends;
1204 while ((rec = *recp++) != 0)
1206 FOR_PROVIDES(p, pp, rec)
1213 sugp = s->repo->idarraydata + s->suggests;
1214 while ((sug = *sugp++) != 0)
1216 FOR_PROVIDES(p, pp, sug)
1223 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforsolvable end -----\n");
1227 addrpmrulesforweak(Solver *solv, Map *m)
1229 Pool *pool = solv->pool;
1234 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforweak -----\n");
1235 for (i = n = 1; n < pool->nsolvables; i++, n++)
1237 if (i == pool->nsolvables)
1241 s = pool->solvables + i;
1242 if (!pool_installable(pool, s))
1247 supp = s->repo->idarraydata + s->supplements;
1248 while ((sup = *supp++) != ID_NULL)
1249 if (dep_possible(solv, sup, m))
1252 if (!sup && s->freshens)
1254 supp = s->repo->idarraydata + s->freshens;
1255 while ((sup = *supp++) != ID_NULL)
1256 if (dep_possible(solv, sup, m))
1259 if (!sup && s->enhances)
1261 supp = s->repo->idarraydata + s->enhances;
1262 while ((sup = *supp++) != ID_NULL)
1263 if (dep_possible(solv, sup, m))
1268 addrpmrulesforsolvable(solv, s, m);
1271 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforweak end -----\n");
1275 addrpmrulesforupdaters(Solver *solv, Solvable *s, Map *m, int allowall)
1277 Pool *pool = solv->pool;
1282 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforupdaters -----\n");
1284 queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
1285 policy_findupdatepackages(solv, s, &qs, allowall);
1286 if (!MAPTST(m, s - pool->solvables)) /* add rule for s if not already done */
1287 addrpmrulesforsolvable(solv, s, m);
1288 for (i = 0; i < qs.count; i++)
1289 if (!MAPTST(m, qs.elements[i]))
1290 addrpmrulesforsolvable(solv, pool->solvables + qs.elements[i], m);
1293 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforupdaters -----\n");
1297 * add rule for update
1298 * (A|A1|A2|A3...) An = update candidates for A
1300 * s = (installed) solvable
1304 addupdaterule(Solver *solv, Solvable *s, int allowall)
1306 /* installed packages get a special upgrade allowed rule */
1307 Pool *pool = solv->pool;
1312 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addupdaterule -----\n");
1314 queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
1315 policy_findupdatepackages(solv, s, &qs, allowall);
1316 if (qs.count == 0) /* no updaters found */
1319 d = pool_queuetowhatprovides(pool, &qs); /* intern computed queue */
1321 addrule(solv, s - pool->solvables, d); /* allow update of s */
1322 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addupdaterule end -----\n");
1326 /*-----------------------------------------------------------------*/
1335 printWatches(Solver *solv, int type)
1337 Pool *pool = solv->pool;
1340 POOL_DEBUG(type, "Watches: \n");
1342 for (counter = -(pool->nsolvables); counter <= pool->nsolvables; counter ++)
1344 POOL_DEBUG(type, " solvable [%d] -- rule [%d]\n", counter, solv->watches[counter+pool->nsolvables]);
1351 * initial setup for all watches
1355 makewatches(Solver *solv)
1359 int nsolvables = solv->pool->nsolvables;
1361 sat_free(solv->watches);
1362 /* lower half for removals, upper half for installs */
1363 solv->watches = sat_calloc(2 * nsolvables, sizeof(Id));
1365 /* do it reverse so rpm rules get triggered first */
1366 for (i = 1, r = solv->rules + solv->nrules - 1; i < solv->nrules; i++, r--)
1368 for (i = 1, r = solv->rules + 1; i < solv->nrules; i++, r++)
1371 if (!r->w1 /* rule is disabled */
1372 || !r->w2) /* rule is assertion */
1375 /* see addwatches(solv, r) */
1376 r->n1 = solv->watches[nsolvables + r->w1];
1377 solv->watches[nsolvables + r->w1] = r - solv->rules;
1379 r->n2 = solv->watches[nsolvables + r->w2];
1380 solv->watches[nsolvables + r->w2] = r - solv->rules;
1386 * add watches (for rule)
1390 addwatches(Solver *solv, Rule *r)
1392 int nsolvables = solv->pool->nsolvables;
1394 r->n1 = solv->watches[nsolvables + r->w1];
1395 solv->watches[nsolvables + r->w1] = r - solv->rules;
1397 r->n2 = solv->watches[nsolvables + r->w2];
1398 solv->watches[nsolvables + r->w2] = r - solv->rules;
1402 /*-----------------------------------------------------------------*/
1403 /* rule propagation */
1405 #define DECISIONMAP_TRUE(p) ((p) > 0 ? (decisionmap[p] > 0) : (decisionmap[-p] < 0))
1410 * propagate decision to all rules
1411 * return : 0 = everything is OK
1412 * watched rule = there is a conflict
1416 propagate(Solver *solv, int level)
1418 Pool *pool = solv->pool;
1423 Id *decisionmap = solv->decisionmap;
1424 Id *watches = solv->watches + pool->nsolvables;
1426 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "----- propagate -----\n");
1428 while (solv->propagate_index < solv->decisionq.count)
1430 /* negate because our watches trigger if literal goes FALSE */
1431 pkg = -solv->decisionq.elements[solv->propagate_index++];
1432 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1434 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "popagate for decision %d level %d\n", -pkg, level);
1435 printruleelement(solv, SAT_DEBUG_PROPAGATE, 0, -pkg);
1437 printWatches(solv, SAT_DEBUG_SCHUBI);
1440 for (rp = watches + pkg; *rp; rp = nrp)
1442 r = solv->rules + *rp;
1444 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1446 POOL_DEBUG(SAT_DEBUG_PROPAGATE," watch triggered ");
1447 printrule(solv, SAT_DEBUG_PROPAGATE, r);
1452 ow = r->w2; /* regard the second watchpoint to come to a solution */
1457 ow = r->w1; /* regard the first watchpoint to come to a solution */
1460 /* if clause is TRUE, nothing to do */
1461 if (DECISIONMAP_TRUE(ow))
1466 /* not a binary clause, check if we need to move our watch */
1467 /* search for a literal that is not ow and not false */
1468 /* (true is also ok, in that case the rule is fulfilled) */
1469 if (r->p && r->p != ow && !DECISIONMAP_TRUE(-r->p))
1472 for (dp = pool->whatprovidesdata + r->d; (p = *dp++) != 0;)
1473 if (p != ow && !DECISIONMAP_TRUE(-p))
1477 /* p is free to watch, move watch to p */
1478 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1481 POOL_DEBUG(SAT_DEBUG_PROPAGATE, " -> move w%d to %s\n", (pkg == r->w1 ? 1 : 2), solvable2str(pool, pool->solvables + p));
1483 POOL_DEBUG(SAT_DEBUG_PROPAGATE," -> move w%d to !%s\n", (pkg == r->w1 ? 1 : 2), solvable2str(pool, pool->solvables - p));
1497 watches[p] = r - solv->rules;
1501 /* unit clause found, set other watch to TRUE */
1502 if (DECISIONMAP_TRUE(-ow))
1503 return r; /* eek, a conflict! */
1504 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1506 POOL_DEBUG(SAT_DEBUG_PROPAGATE, " unit ");
1507 printrule(solv, SAT_DEBUG_PROPAGATE, r);
1510 decisionmap[ow] = level;
1512 decisionmap[-ow] = -level;
1513 queue_push(&solv->decisionq, ow);
1514 queue_push(&solv->decisionq_why, r - solv->rules);
1515 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1517 Solvable *s = pool->solvables + (ow > 0 ? ow : -ow);
1519 POOL_DEBUG(SAT_DEBUG_PROPAGATE, " -> decided to install %s\n", solvable2str(pool, s));
1521 POOL_DEBUG(SAT_DEBUG_PROPAGATE, " -> decided to conflict %s\n", solvable2str(pool, s));
1525 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "----- propagate end-----\n");
1527 return 0; /* all is well */
1531 /*-----------------------------------------------------------------*/
1540 analyze(Solver *solv, int level, Rule *c, int *pr, int *dr, int *whyp)
1542 Pool *pool = solv->pool;
1545 Map seen; /* global? */
1548 int num = 0, l1num = 0;
1549 int learnt_why = solv->learnt_pool.count;
1550 Id *decisionmap = solv->decisionmap;
1554 POOL_DEBUG(SAT_DEBUG_ANALYZE, "ANALYZE at %d ----------------------\n", level);
1555 map_init(&seen, pool->nsolvables);
1556 idx = solv->decisionq.count;
1559 IF_POOLDEBUG (SAT_DEBUG_ANALYZE)
1560 printruleclass(solv, SAT_DEBUG_ANALYZE, c);
1561 queue_push(&solv->learnt_pool, c - solv->rules);
1562 dp = c->d ? pool->whatprovidesdata + c->d : 0;
1563 /* go through all literals of the rule */
1575 if (DECISIONMAP_TRUE(v)) /* the one true literal */
1577 vv = v > 0 ? v : -v;
1578 if (MAPTST(&seen, vv))
1580 l = solv->decisionmap[vv];
1585 /* a level 1 literal, mark it for later */
1586 MAPSET(&seen, vv); /* mark for scanning in level 1 phase */
1592 num++; /* need to do this one as well */
1603 v = solv->decisionq.elements[--idx];
1604 vv = v > 0 ? v : -v;
1605 if (MAPTST(&seen, vv))
1608 c = solv->rules + solv->decisionq_why.elements[idx];
1613 *pr = -v; /* so that v doesn't get lost */
1615 /* add involved level 1 rules */
1618 POOL_DEBUG(SAT_DEBUG_ANALYZE, "got %d involved level 1 decisions\n", l1num);
1622 v = solv->decisionq.elements[--idx];
1623 vv = v > 0 ? v : -v;
1624 if (!MAPTST(&seen, vv))
1626 why = solv->decisionq_why.elements[idx];
1629 queue_push(&solv->learnt_pool, -vv);
1630 IF_POOLDEBUG (SAT_DEBUG_ANALYZE)
1632 POOL_DEBUG(SAT_DEBUG_ANALYZE, "RPM ASSERT Rule:\n");
1633 printruleelement(solv, SAT_DEBUG_ANALYZE, 0, v);
1637 queue_push(&solv->learnt_pool, why);
1638 c = solv->rules + why;
1639 dp = c->d ? pool->whatprovidesdata + c->d : 0;
1640 IF_POOLDEBUG (SAT_DEBUG_ANALYZE)
1641 printruleclass(solv, SAT_DEBUG_ANALYZE, c);
1652 if (DECISIONMAP_TRUE(v)) /* the one true literal */
1654 vv = v > 0 ? v : -v;
1655 l = solv->decisionmap[vv];
1656 if (l != 1 && l != -1)
1666 else if (r.count == 1 && r.elements[0] < 0)
1667 *dr = r.elements[0];
1669 *dr = pool_queuetowhatprovides(pool, &r);
1670 IF_POOLDEBUG (SAT_DEBUG_ANALYZE)
1672 POOL_DEBUG(SAT_DEBUG_ANALYZE, "learned rule for level %d (am %d)\n", rlevel, level);
1673 printruleelement(solv, SAT_DEBUG_ANALYZE, 0, *pr);
1674 for (i = 0; i < r.count; i++)
1675 printruleelement(solv, SAT_DEBUG_ANALYZE, 0, r.elements[i]);
1677 /* push end marker on learnt reasons stack */
1678 queue_push(&solv->learnt_pool, 0);
1687 * reset the solver decisions to right after the rpm rules.
1688 * called after rules have been enabled/disabled
1692 reset_solver(Solver *solv)
1694 Pool *pool = solv->pool;
1698 /* rewind decisions to direct rpm rule assertions */
1699 for (i = solv->decisionq.count - 1; i >= solv->directdecisions; i--)
1701 v = solv->decisionq.elements[i];
1702 solv->decisionmap[v > 0 ? v : -v] = 0;
1705 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "decisions done reduced from %d to %d\n", solv->decisionq.count, solv->directdecisions);
1707 solv->decisionq_why.count = solv->directdecisions;
1708 solv->decisionq.count = solv->directdecisions;
1709 solv->recommends_index = -1;
1710 solv->propagate_index = 0;
1712 /* adapt learnt rule status to new set of enabled/disabled rules */
1713 enabledisablelearntrules(solv);
1715 /* redo all job/system decisions */
1716 makeruledecisions(solv);
1717 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "decisions so far: %d\n", solv->decisionq.count);
1719 /* recreate watch chains */
1725 * analyze_unsolvable_rule
1729 analyze_unsolvable_rule(Solver *solv, Rule *r)
1731 Pool *pool = solv->pool;
1733 Id why = r - solv->rules;
1734 IF_POOLDEBUG (SAT_DEBUG_UNSOLVABLE)
1735 printruleclass(solv, SAT_DEBUG_UNSOLVABLE, r);
1736 if (solv->learntrules && why >= solv->learntrules)
1738 for (i = solv->learnt_why.elements[why - solv->learntrules]; solv->learnt_pool.elements[i]; i++)
1739 if (solv->learnt_pool.elements[i] > 0)
1740 analyze_unsolvable_rule(solv, solv->rules + solv->learnt_pool.elements[i]);
1743 /* do not add rpm rules to problem */
1744 if (why < solv->jobrules)
1746 /* turn rule into problem */
1747 if (why >= solv->jobrules && why < solv->systemrules)
1748 why = -(solv->ruletojob.elements[why - solv->jobrules] + 1);
1749 /* return if problem already countains our rule */
1750 if (solv->problems.count)
1752 for (i = solv->problems.count - 1; i >= 0; i--)
1753 if (solv->problems.elements[i] == 0) /* end of last problem reached? */
1755 else if (solv->problems.elements[i] == why)
1758 queue_push(&solv->problems, why);
1763 * analyze_unsolvable
1765 * return: 1 - disabled some rules, try again
1770 analyze_unsolvable(Solver *solv, Rule *cr, int disablerules)
1772 Pool *pool = solv->pool;
1774 Map seen; /* global to speed things up? */
1777 Id *decisionmap = solv->decisionmap;
1778 int oldproblemcount;
1779 int oldlearntpoolcount;
1782 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "ANALYZE UNSOLVABLE ----------------------\n");
1783 oldproblemcount = solv->problems.count;
1784 oldlearntpoolcount = solv->learnt_pool.count;
1786 /* make room for proof index */
1787 /* must update it later, as analyze_unsolvable_rule would confuse
1788 * it with a rule index if we put the real value in already */
1789 queue_push(&solv->problems, 0);
1792 map_init(&seen, pool->nsolvables);
1793 queue_push(&solv->learnt_pool, r - solv->rules);
1794 analyze_unsolvable_rule(solv, r);
1795 dp = r->d ? pool->whatprovidesdata + r->d : 0;
1806 if (DECISIONMAP_TRUE(v)) /* the one true literal */
1808 vv = v > 0 ? v : -v;
1809 l = solv->decisionmap[vv];
1814 idx = solv->decisionq.count;
1817 v = solv->decisionq.elements[--idx];
1818 vv = v > 0 ? v : -v;
1819 if (!MAPTST(&seen, vv))
1821 why = solv->decisionq_why.elements[idx];
1824 /* level 1 and no why, must be an rpm assertion */
1825 IF_POOLDEBUG (SAT_DEBUG_UNSOLVABLE)
1827 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "RPM ");
1828 printruleelement(solv, SAT_DEBUG_UNSOLVABLE, 0, v);
1830 /* this is the only positive rpm assertion */
1831 if (v == SYSTEMSOLVABLE)
1834 queue_push(&solv->learnt_pool, v);
1837 queue_push(&solv->learnt_pool, why);
1838 r = solv->rules + why;
1839 analyze_unsolvable_rule(solv, r);
1840 dp = r->d ? pool->whatprovidesdata + r->d : 0;
1851 if (DECISIONMAP_TRUE(v)) /* the one true literal */
1853 vv = v > 0 ? v : -v;
1854 l = solv->decisionmap[vv];
1861 queue_push(&solv->problems, 0); /* mark end of this problem */
1864 if (solv->weakrules != solv->learntrules)
1866 for (i = oldproblemcount + 1; i < solv->problems.count - 1; i++)
1868 why = solv->problems.elements[i];
1869 if (why < solv->weakrules || why >= solv->learntrules)
1871 if (!lastweak || lastweak < why)
1877 /* disable last weak rule */
1878 solv->problems.count = oldproblemcount;
1879 solv->learnt_pool.count = oldlearntpoolcount;
1880 r = solv->rules + lastweak;
1881 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "disabling weak ");
1882 printrule(solv, SAT_DEBUG_UNSOLVABLE, r);
1883 disablerule(solv, r);
1889 queue_push(&solv->learnt_pool, 0);
1890 solv->problems.elements[oldproblemcount] = oldlearntpoolcount;
1894 for (i = oldproblemcount + 1; i < solv->problems.count - 1; i++)
1895 disableproblem(solv, solv->problems.elements[i]);
1899 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "UNSOLVABLE\n");
1904 /*-----------------------------------------------------------------*/
1905 /* Decision revert */
1909 * revert decision at level
1913 revert(Solver *solv, int level)
1915 Pool *pool = solv->pool;
1917 while (solv->decisionq.count)
1919 v = solv->decisionq.elements[solv->decisionq.count - 1];
1920 vv = v > 0 ? v : -v;
1921 if (solv->decisionmap[vv] <= level && solv->decisionmap[vv] >= -level)
1923 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "reverting decision %d at %d\n", v, solv->decisionmap[vv]);
1924 solv->decisionmap[vv] = 0;
1925 solv->decisionq.count--;
1926 solv->decisionq_why.count--;
1927 solv->propagate_index = solv->decisionq.count;
1929 while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] <= -level)
1931 solv->branches.count--;
1932 while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] >= 0)
1933 solv->branches.count--;
1935 solv->recommends_index = -1;
1940 * watch2onhighest - put watch2 on literal with highest level
1944 watch2onhighest(Solver *solv, Rule *r)
1950 return; /* binary rule, both watches are set */
1951 dp = solv->pool->whatprovidesdata + r->d;
1952 while ((v = *dp++) != 0)
1954 l = solv->decisionmap[v < 0 ? -v : v];
1969 * add free decision to decisionq, increase level and
1970 * propagate decision, return if no conflict.
1971 * in conflict case, analyze conflict rule, add resulting
1972 * rule to learnt rule set, make decision from learnt
1973 * rule (always unit) and re-propagate.
1975 * returns the new solver level or 0 if unsolvable
1980 setpropagatelearn(Solver *solv, int level, Id decision, int disablerules)
1982 Pool *pool = solv->pool;
1991 solv->decisionmap[decision] = level;
1993 solv->decisionmap[-decision] = -level;
1994 queue_push(&solv->decisionq, decision);
1995 queue_push(&solv->decisionq_why, 0);
1999 r = propagate(solv, level);
2003 return analyze_unsolvable(solv, r, disablerules);
2004 POOL_DEBUG(SAT_DEBUG_ANALYZE, "conflict with rule #%d\n", (int)(r - solv->rules));
2005 l = analyze(solv, level, r, &p, &d, &why); /* learnt rule in p and d */
2006 assert(l > 0 && l < level);
2007 POOL_DEBUG(SAT_DEBUG_ANALYZE, "reverting decisions (level %d -> %d)\n", level, l);
2009 revert(solv, level);
2010 r = addrule(solv, p, d); /* p requires d */
2012 assert(solv->learnt_why.count == (r - solv->rules) - solv->learntrules);
2013 queue_push(&solv->learnt_why, why);
2016 /* at least 2 literals, needs watches */
2017 watch2onhighest(solv, r);
2018 addwatches(solv, r);
2020 solv->decisionmap[p > 0 ? p : -p] = p > 0 ? level : -level;
2021 queue_push(&solv->decisionq, p);
2022 queue_push(&solv->decisionq_why, r - solv->rules);
2023 IF_POOLDEBUG (SAT_DEBUG_ANALYZE)
2025 POOL_DEBUG(SAT_DEBUG_ANALYZE, "decision: ");
2026 printruleelement(solv, SAT_DEBUG_ANALYZE, 0, p);
2027 POOL_DEBUG(SAT_DEBUG_ANALYZE, "new rule: ");
2028 printrule(solv, SAT_DEBUG_ANALYZE, r);
2036 * install best package from the queue. We add an extra package, inst, if
2037 * provided. See comment in weak install section.
2039 * returns the new solver level or 0 if unsolvable
2043 selectandinstall(Solver *solv, int level, Queue *dq, Id inst, int disablerules)
2045 Pool *pool = solv->pool;
2049 if (dq->count > 1 || inst)
2050 policy_filter_unwanted(solv, dq, inst, POLICY_MODE_CHOOSE);
2055 /* choose the supplemented one */
2056 for (i = 0; i < dq->count; i++)
2057 if (solver_is_supplementing(solv, pool->solvables + dq->elements[i]))
2061 for (i = 1; i < dq->count; i++)
2062 queue_push(&solv->branches, dq->elements[i]);
2063 queue_push(&solv->branches, -level);
2067 p = dq->elements[i];
2069 POOL_DEBUG(SAT_DEBUG_POLICY, "installing %s\n", solvable2str(pool, pool->solvables + p));
2071 return setpropagatelearn(solv, level, p, disablerules);
2075 /*-----------------------------------------------------------------*/
2076 /* Main solver interface */
2081 * create solver structure
2083 * pool: all available solvables
2084 * installed: installed Solvables
2087 * Upon solving, rules are created to flag the Solvables
2088 * of the 'installed' Repo as installed.
2092 solver_create(Pool *pool, Repo *installed)
2095 solv = (Solver *)sat_calloc(1, sizeof(Solver));
2097 solv->installed = installed;
2099 queue_init(&solv->ruletojob);
2100 queue_init(&solv->decisionq);
2101 queue_init(&solv->decisionq_why);
2102 queue_init(&solv->problems);
2103 queue_init(&solv->suggestions);
2104 queue_init(&solv->learnt_why);
2105 queue_init(&solv->learnt_pool);
2106 queue_init(&solv->branches);
2107 queue_init(&solv->covenantq);
2109 map_init(&solv->recommendsmap, pool->nsolvables);
2110 map_init(&solv->suggestsmap, pool->nsolvables);
2111 map_init(&solv->noupdate, installed ? installed->end - installed->start : 0);
2112 solv->recommends_index = 0;
2114 solv->decisionmap = (Id *)sat_calloc(pool->nsolvables, sizeof(Id));
2116 solv->rules = sat_extend_resize(solv->rules, solv->nrules, sizeof(Rule), RULES_BLOCK);
2117 memset(solv->rules, 0, sizeof(Rule));
2119 /* cannot be zero by default since zero corresponds to KIND_PACKAGE
2120 * so we initialize it with _KIND_MAX to denote 'all kinds'
2121 * if the application sets this to a specific KIND_, the value is
2122 * incremented by 1 at solver start to make 'if (limittokind)' checks easy
2124 * A sure candidate for a more clever implementation
2127 solv->limittokind = _KIND_MAX;
2138 solver_free(Solver *solv)
2140 queue_free(&solv->ruletojob);
2141 queue_free(&solv->decisionq);
2142 queue_free(&solv->decisionq_why);
2143 queue_free(&solv->learnt_why);
2144 queue_free(&solv->learnt_pool);
2145 queue_free(&solv->problems);
2146 queue_free(&solv->suggestions);
2147 queue_free(&solv->branches);
2148 queue_free(&solv->covenantq);
2150 map_free(&solv->recommendsmap);
2151 map_free(&solv->suggestsmap);
2152 map_free(&solv->noupdate);
2154 sat_free(solv->decisionmap);
2155 sat_free(solv->rules);
2156 sat_free(solv->watches);
2157 sat_free(solv->weaksystemrules);
2158 sat_free(solv->obsoletes);
2159 sat_free(solv->obsoletes_data);
2164 /*-------------------------------------------------------*/
2169 * all rules have been set up, now actually run the solver
2174 run_solver(Solver *solv, int disablerules, int doweak)
2182 Pool *pool = solv->pool;
2185 IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION)
2187 POOL_DEBUG (SAT_DEBUG_RULE_CREATION, "number of rules: %d\n", solv->nrules);
2188 for (i = 0; i < solv->nrules; i++)
2189 printrule(solv, SAT_DEBUG_RULE_CREATION, solv->rules + i);
2192 POOL_DEBUG(SAT_DEBUG_STATS, "initial decisions: %d\n", solv->decisionq.count);
2194 IF_POOLDEBUG (SAT_DEBUG_SCHUBI)
2195 printdecisions(solv);
2197 /* start SAT algorithm */
2199 systemlevel = level + 1;
2200 POOL_DEBUG(SAT_DEBUG_STATS, "solving...\n");
2211 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "propagating (propagate_index: %d; size decisionq: %d)...\n", solv->propagate_index, solv->decisionq.count);
2212 if ((r = propagate(solv, level)) != 0)
2214 if (analyze_unsolvable(solv, r, disablerules))
2222 * installed packages
2225 if (level < systemlevel && solv->installed && solv->installed->nsolvables)
2227 if (!solv->updatesystem)
2229 /* try to keep as many packages as possible */
2230 POOL_DEBUG(SAT_DEBUG_STATS, "installing system packages\n");
2231 for (i = solv->installed->start, n = 0; ; i++)
2233 if (n == solv->installed->nsolvables)
2235 if (i == solv->installed->end)
2236 i = solv->installed->start;
2237 s = pool->solvables + i;
2238 if (s->repo != solv->installed)
2241 if (solv->decisionmap[i] != 0)
2243 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "keeping %s\n", solvable2str(pool, s));
2245 level = setpropagatelearn(solv, level, i, disablerules);
2251 if (level <= olevel)
2255 if (solv->weaksystemrules)
2257 POOL_DEBUG(SAT_DEBUG_STATS, "installing weak system packages\n");
2258 for (i = solv->installed->start; i < solv->installed->end; i++)
2260 if (pool->solvables[i].repo != solv->installed)
2262 if (solv->decisionmap[i] > 0 || (solv->decisionmap[i] < 0 && solv->weaksystemrules[i - solv->installed->start] == 0))
2264 /* noupdate is set if a job is erasing the installed solvable or installing a specific version */
2265 if (MAPTST(&solv->noupdate, i - solv->installed->start))
2268 if (solv->weaksystemrules[i - solv->installed->start])
2270 dp = pool->whatprovidesdata + solv->weaksystemrules[i - solv->installed->start];
2271 while ((p = *dp++) != 0)
2273 if (solv->decisionmap[p] > 0)
2275 if (solv->decisionmap[p] == 0)
2279 continue; /* update package already installed */
2281 if (!dq.count && solv->decisionmap[i] != 0)
2284 /* FIXME: i is handled a bit different because we do not want
2285 * to have it pruned just because it is not recommened.
2286 * we should not prune installed packages instead */
2287 level = selectandinstall(solv, level, &dq, (solv->decisionmap[i] ? 0 : i), disablerules);
2293 if (level <= olevel)
2296 if (i < solv->installed->end)
2299 systemlevel = level;
2306 POOL_DEBUG(SAT_DEBUG_STATS, "deciding unresolved rules\n");
2307 for (i = 1, n = 1; ; i++, n++)
2309 if (n == solv->nrules)
2311 if (i == solv->nrules)
2313 r = solv->rules + i;
2314 if (!r->w1) /* ignore disabled rules */
2319 /* binary or unary rule */
2320 /* need two positive undecided literals */
2321 if (r->p < 0 || r->w2 <= 0)
2323 if (solv->decisionmap[r->p] || solv->decisionmap[r->w2])
2325 queue_push(&dq, r->p);
2326 queue_push(&dq, r->w2);
2331 * all negative literals are installed
2332 * no positive literal is installed
2333 * i.e. the rule is not fulfilled and we
2334 * just need to decide on the positive literals
2338 if (solv->decisionmap[-r->p] <= 0)
2343 if (solv->decisionmap[r->p] > 0)
2345 if (solv->decisionmap[r->p] == 0)
2346 queue_push(&dq, r->p);
2348 dp = pool->whatprovidesdata + r->d;
2349 while ((p = *dp++) != 0)
2353 if (solv->decisionmap[-p] <= 0)
2358 if (solv->decisionmap[p] > 0)
2360 if (solv->decisionmap[p] == 0)
2367 /* dq.count < 2 cannot happen as this means that
2368 * the rule is unit */
2369 assert(dq.count > 1);
2370 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
2372 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "unfulfilled ");
2373 printrule(solv, SAT_DEBUG_PROPAGATE, r);
2377 level = selectandinstall(solv, level, &dq, 0, disablerules);
2383 if (level < systemlevel)
2386 } /* for(), decide */
2388 if (n != solv->nrules) /* continue if level < systemlevel */
2391 if (doweak && !solv->problems.count)
2395 POOL_DEBUG(SAT_DEBUG_STATS, "installing recommended packages\n");
2396 if (!solv->dosplitprovides && !REGARD_RECOMMENDS_OF_INSTALLED_ITEMS)
2398 for (i = 1; i < solv->decisionq.count; i++)
2400 p = solv->decisionq.elements[i];
2401 if (p > 0 && pool->solvables[p].repo == solv->installed)
2402 solv->decisionmap[p] = -solv->decisionmap[p];
2406 for (i = 1; i < pool->nsolvables; i++)
2408 if (solv->decisionmap[i] < 0)
2410 if (solv->decisionmap[i] > 0)
2412 Id *recp, rec, *pp, p;
2413 s = pool->solvables + i;
2414 /* installed, check for recommends */
2415 /* XXX need to special case AND ? */
2418 recp = s->repo->idarraydata + s->recommends;
2419 while ((rec = *recp++) != 0)
2422 FOR_PROVIDES(p, pp, rec)
2424 if (solv->decisionmap[p] > 0)
2429 else if (solv->decisionmap[p] == 0)
2431 queue_pushunique(&dq, p);
2439 s = pool->solvables + i;
2440 if (!s->supplements && !s->freshens)
2442 if (!pool_installable(pool, s))
2444 if (solver_is_supplementing(solv, s))
2445 queue_pushunique(&dq, i);
2448 if (!solv->dosplitprovides && !REGARD_RECOMMENDS_OF_INSTALLED_ITEMS)
2450 for (i = 1; i < solv->decisionq.count; i++)
2452 p = solv->decisionq.elements[i];
2453 if (p > 0 && pool->solvables[p].repo == solv->installed)
2454 solv->decisionmap[p] = -solv->decisionmap[p];
2460 policy_filter_unwanted(solv, &dq, 0, POLICY_MODE_RECOMMEND);
2462 POOL_DEBUG(SAT_DEBUG_STATS, "installing recommended %s\n", solvable2str(pool, pool->solvables + p));
2463 level = setpropagatelearn(solv, level, p, 0);
2468 if (solv->solution_callback)
2470 solv->solution_callback(solv, solv->solution_callback_data);
2471 if (solv->branches.count)
2473 int i = solv->branches.count - 1;
2474 int l = -solv->branches.elements[i];
2476 if (solv->branches.elements[i - 1] < 0)
2478 p = solv->branches.elements[i];
2479 POOL_DEBUG(SAT_DEBUG_STATS, "branching with %s\n", solvable2str(pool, pool->solvables + p));
2481 for (j = i + 1; j < solv->branches.count; j++)
2482 queue_push(&dq, solv->branches.elements[j]);
2483 solv->branches.count = i;
2485 revert(solv, level);
2487 for (j = 0; j < dq.count; j++)
2488 queue_push(&solv->branches, dq.elements[j]);
2490 level = setpropagatelearn(solv, level, p, disablerules);
2498 /* all branches done, we're finally finished */
2502 /* minimization step */
2503 if (solv->branches.count)
2505 int l = 0, lasti = -1, lastl = -1;
2507 for (i = solv->branches.count - 1; i >= 0; i--)
2509 p = solv->branches.elements[i];
2512 else if (p > 0 && solv->decisionmap[p] > l + 1)
2520 /* kill old solvable so that we do not loop */
2521 p = solv->branches.elements[lasti];
2522 solv->branches.elements[lasti] = 0;
2523 POOL_DEBUG(SAT_DEBUG_STATS, "minimizing %d -> %d with %s\n", solv->decisionmap[p], l, solvable2str(pool, pool->solvables + p));
2526 revert(solv, level);
2528 level = setpropagatelearn(solv, level, p, disablerules);
2545 * at this point, all rules that led to conflicts are disabled.
2546 * we re-enable all rules of a problem set but rule "sug", then
2547 * continue to disable more rules until there as again a solution.
2550 /* FIXME: think about conflicting assertions */
2553 refine_suggestion(Solver *solv, Queue *job, Id *problem, Id sug, Queue *refined)
2555 Pool *pool = solv->pool;
2562 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
2564 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "refine_suggestion start\n");
2565 for (i = 0; problem[i]; i++)
2567 if (problem[i] == sug)
2568 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "=> ");
2569 printproblem(solv, problem[i]);
2572 queue_init(&disabled);
2573 queue_empty(refined);
2574 queue_push(refined, sug);
2576 /* re-enable all problem rules with the exception of "sug"(gests) */
2580 for (i = 0; problem[i]; i++)
2581 if (problem[i] != sug)
2582 enableproblem(solv, problem[i]);
2585 disableupdaterules(solv, job, -(sug + 1));
2589 /* re-enable as many weak rules as possible */
2590 for (i = solv->weakrules; i < solv->learntrules; i++)
2592 r = solv->rules + i;
2594 enablerule(solv, r);
2597 queue_empty(&solv->problems);
2598 revert(solv, 1); /* XXX move to reset_solver? */
2601 if (!solv->problems.count)
2602 run_solver(solv, 0, 0);
2604 if (!solv->problems.count)
2606 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "no more problems!\n");
2607 IF_POOLDEBUG (SAT_DEBUG_SCHUBI)
2608 printdecisions(solv);
2609 break; /* great, no more problems */
2611 disabledcnt = disabled.count;
2612 /* start with 1 to skip over proof index */
2613 for (i = 1; i < solv->problems.count - 1; i++)
2615 /* ignore solutions in refined */
2616 v = solv->problems.elements[i];
2618 break; /* end of problem reached */
2619 for (j = 0; problem[j]; j++)
2620 if (problem[j] != sug && problem[j] == v)
2624 queue_push(&disabled, v);
2626 if (disabled.count == disabledcnt)
2628 /* no solution found, this was an invalid suggestion! */
2629 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "no solution found!\n");
2633 if (disabled.count == disabledcnt + 1)
2635 /* just one suggestion, add it to refined list */
2636 v = disabled.elements[disabledcnt];
2637 queue_push(refined, v);
2638 disableproblem(solv, v);
2640 disableupdaterules(solv, job, -(v + 1));
2644 /* more than one solution, disable all */
2645 /* do not push anything on refine list */
2646 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
2648 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "more than one solution found:\n");
2649 for (i = disabledcnt; i < disabled.count; i++)
2650 printproblem(solv, disabled.elements[i]);
2652 for (i = disabledcnt; i < disabled.count; i++)
2653 disableproblem(solv, disabled.elements[i]);
2656 /* all done, get us back into the same state as before */
2657 /* enable refined rules again */
2658 for (i = 0; i < disabled.count; i++)
2659 enableproblem(solv, disabled.elements[i]);
2660 /* disable problem rules again */
2661 for (i = 0; problem[i]; i++)
2662 disableproblem(solv, problem[i]);
2663 disableupdaterules(solv, job, -1);
2664 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "refine_suggestion end\n");
2668 problems_to_solutions(Solver *solv, Queue *job)
2670 Pool *pool = solv->pool;
2678 if (!solv->problems.count)
2680 queue_clone(&problems, &solv->problems);
2681 queue_init(&solution);
2682 queue_init(&solutions);
2683 /* copy over proof index */
2684 queue_push(&solutions, problems.elements[0]);
2685 problem = problems.elements + 1;
2686 for (i = 1; i < problems.count; i++)
2688 Id v = problems.elements[i];
2691 /* mark end of this problem */
2692 queue_push(&solutions, 0);
2693 queue_push(&solutions, 0);
2694 if (i + 1 == problems.count)
2696 /* copy over proof of next problem */
2697 queue_push(&solutions, problems.elements[i + 1]);
2699 problem = problems.elements + i + 1;
2702 refine_suggestion(solv, job, problem, v, &solution);
2703 if (!solution.count)
2704 continue; /* this solution didn't work out */
2706 for (j = 0; j < solution.count; j++)
2708 why = solution.elements[j];
2709 /* must be either job descriptor or system rule */
2710 assert(why < 0 || (why >= solv->systemrules && why < solv->weakrules));
2712 printproblem(solv, why);
2716 /* job descriptor */
2717 queue_push(&solutions, 0);
2718 queue_push(&solutions, -why);
2722 /* system rule, find replacement package */
2724 p = solv->installed->start + (why - solv->systemrules);
2725 if (solv->weaksystemrules && solv->weaksystemrules[why - solv->systemrules])
2727 Id *dp = pool->whatprovidesdata + solv->weaksystemrules[why - solv->systemrules];
2730 if (*dp >= solv->installed->start && *dp < solv->installed->start + solv->installed->nsolvables)
2732 if (solv->decisionmap[*dp] > 0)
2739 queue_push(&solutions, p);
2740 queue_push(&solutions, rp);
2743 /* mark end of this solution */
2744 queue_push(&solutions, 0);
2745 queue_push(&solutions, 0);
2747 queue_free(&solution);
2748 queue_free(&problems);
2749 /* copy queue over to solutions */
2750 queue_free(&solv->problems);
2751 queue_clone(&solv->problems, &solutions);
2753 /* bring solver back into problem state */
2754 revert(solv, 1); /* XXX move to reset_solver? */
2757 assert(solv->problems.count == solutions.count);
2758 queue_free(&solutions);
2762 solver_next_problem(Solver *solv, Id problem)
2766 return solv->problems.count ? 1 : 0;
2767 pp = solv->problems.elements + problem;
2768 while (pp[0] || pp[1])
2772 while (pp[0] || pp[1])
2777 problem = pp - solv->problems.elements;
2778 if (problem >= solv->problems.count)
2784 solver_next_solution(Solver *solv, Id problem, Id solution)
2790 pp = solv->problems.elements + solution;
2791 return pp[0] || pp[1] ? solution : 0;
2793 pp = solv->problems.elements + solution;
2794 while (pp[0] || pp[1])
2797 solution = pp - solv->problems.elements;
2798 return pp[0] || pp[1] ? solution : 0;
2802 solver_next_solutionelement(Solver *solv, Id problem, Id solution, Id element, Id *p, Id *rp)
2805 element = element ? element + 2 : solution;
2806 pp = solv->problems.elements + element;
2807 if (!(pp[0] || pp[1]))
2816 * create obsoletesmap from solver decisions
2817 * required for decision handling
2821 create_decisions_obsoletesmap(Solver *solv)
2823 Pool *pool = solv->pool;
2824 Repo *installed = solv->installed;
2825 Id p, *obsoletesmap = NULL;
2829 obsoletesmap = (Id *)sat_calloc(pool->nsolvables, sizeof(Id));
2832 for (i = 0; i < solv->decisionq.count; i++)
2836 n = solv->decisionq.elements[i];
2839 if (n == SYSTEMSOLVABLE)
2841 s = pool->solvables + n;
2842 if (s->repo == installed) /* obsoletes don't count for already installed packages */
2844 FOR_PROVIDES(p, pp, s->name)
2845 if (s->name == pool->solvables[p].name)
2847 if (pool->solvables[p].repo == installed && !obsoletesmap[p])
2849 obsoletesmap[p] = n;
2854 for (i = 0; i < solv->decisionq.count; i++)
2859 n = solv->decisionq.elements[i];
2862 if (n == SYSTEMSOLVABLE)
2864 s = pool->solvables + n;
2865 if (s->repo == installed) /* obsoletes don't count for already installed packages */
2869 obsp = s->repo->idarraydata + s->obsoletes;
2870 while ((obs = *obsp++) != 0)
2871 FOR_PROVIDES(p, pp, obs)
2873 if (pool->solvables[p].repo == installed && !obsoletesmap[p])
2875 obsoletesmap[p] = n;
2881 return obsoletesmap;
2890 printdecisions(Solver *solv)
2892 Pool *pool = solv->pool;
2893 Repo *installed = solv->installed;
2894 Id p, *obsoletesmap = create_decisions_obsoletesmap( solv );
2898 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- Decisions -----\n");
2900 /* print solvables to be erased */
2904 FOR_REPO_SOLVABLES(installed, p, s)
2906 if (solv->decisionmap[p] >= 0)
2908 if (obsoletesmap[p])
2910 POOL_DEBUG(SAT_DEBUG_RESULT, "erase %s\n", solvable2str(pool, s));
2914 /* print solvables to be installed */
2916 for (i = 0; i < solv->decisionq.count; i++)
2919 p = solv->decisionq.elements[i];
2922 IF_POOLDEBUG (SAT_DEBUG_SCHUBI)
2925 s = pool->solvables + p;
2926 POOL_DEBUG(SAT_DEBUG_SCHUBI, "level of %s is %d\n", solvable2str(pool, s), p);
2930 if (p == SYSTEMSOLVABLE)
2932 POOL_DEBUG(SAT_DEBUG_SCHUBI, "SYSTEMSOLVABLE\n");
2935 s = pool->solvables + p;
2936 if (installed && s->repo == installed)
2939 if (!obsoletesmap[p])
2941 POOL_DEBUG(SAT_DEBUG_RESULT, "install %s", solvable2str(pool, s));
2945 POOL_DEBUG(SAT_DEBUG_RESULT, "update %s", solvable2str(pool, s));
2946 POOL_DEBUG(SAT_DEBUG_RESULT, " (obsoletes");
2947 for (j = installed->start; j < installed->end; j++)
2948 if (obsoletesmap[j] == p)
2949 POOL_DEBUG(SAT_DEBUG_RESULT, " %s", solvable2str(pool, pool->solvables + j));
2950 POOL_DEBUG(SAT_DEBUG_RESULT, ")");
2952 POOL_DEBUG(SAT_DEBUG_RESULT, "\n");
2955 sat_free(obsoletesmap);
2957 if (solv->suggestions.count)
2959 POOL_DEBUG(SAT_DEBUG_RESULT, "\nsuggested packages:\n");
2960 for (i = 0; i < solv->suggestions.count; i++)
2962 s = pool->solvables + solv->suggestions.elements[i];
2963 POOL_DEBUG(SAT_DEBUG_RESULT, "- %s\n", solvable2str(pool, s));
2966 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- Decisions end -----\n");
2969 /* this is basically the reverse of addrpmrulesforsolvable */
2971 solver_problemruleinfo(Solver *solv, Queue *job, Id rid, Id *depp, Id *sourcep, Id *targetp)
2973 Pool *pool = solv->pool;
2974 Repo *installed = solv->installed;
2978 Id p, *pp, req, *reqp, con, *conp, obs, *obsp, *dp;
2980 assert(rid < solv->weakrules);
2981 if (rid >= solv->systemrules)
2984 *sourcep = solv->installed->start + (rid - solv->systemrules);
2986 return SOLVER_PROBLEM_UPDATE_RULE;
2988 if (rid >= solv->jobrules)
2991 r = solv->rules + rid;
2992 p = solv->ruletojob.elements[rid - solv->jobrules];
2993 *depp = job->elements[p + 1];
2995 *targetp = job->elements[p];
2996 if (r->d == 0 && r->w2 == 0 && r->p == -SYSTEMSOLVABLE)
2997 return SOLVER_PROBLEM_JOB_NOTHING_PROVIDES_DEP;
2998 return SOLVER_PROBLEM_JOB_RULE;
3002 /* a rpm rule assertion */
3003 assert(rid != -SYSTEMSOLVABLE);
3004 s = pool->solvables - rid;
3005 if (installed && !solv->fixsystem && s->repo == installed)
3007 assert(!dontfix); /* dontfix packages never have a neg assertion */
3008 /* see why the package is not installable */
3009 if (s->arch != ARCH_SRC && s->arch != ARCH_NOSRC && !pool_installable(pool, s))
3010 return SOLVER_PROBLEM_NOT_INSTALLABLE;
3011 /* check requires */
3012 assert(s->requires);
3013 reqp = s->repo->idarraydata + s->requires;
3014 while ((req = *reqp++) != 0)
3016 if (req == SOLVABLE_PREREQMARKER)
3018 dp = pool_whatprovides(pool, req);
3026 return SOLVER_PROBLEM_NOTHING_PROVIDES_DEP;
3028 r = solv->rules + rid;
3030 if (r->d == 0 && r->w2 == 0)
3032 /* an assertion. we don't store them as rpm rules, so
3036 s = pool->solvables - r->p;
3037 if (installed && !solv->fixsystem && s->repo == installed)
3039 if (r->d == 0 && r->w2 < 0)
3041 /* a package conflict */
3042 Solvable *s2 = pool->solvables - r->w2;
3045 if (installed && !solv->fixsystem && s2->repo == installed)
3048 /* if both packages have the same name and at least one of them
3049 * is not installed, they conflict */
3050 if (s->name == s2->name && (!installed || (s->repo != installed || s2->repo != installed)))
3055 return SOLVER_PROBLEM_SAME_NAME;
3058 /* check conflicts in both directions */
3061 conp = s->repo->idarraydata + s->conflicts;
3062 while ((con = *conp++) != 0)
3064 FOR_PROVIDES(p, pp, con)
3066 if (dontfix && pool->solvables[p].repo == installed)
3073 return SOLVER_PROBLEM_PACKAGE_CONFLICT;
3079 conp = s2->repo->idarraydata + s2->conflicts;
3080 while ((con = *conp++) != 0)
3082 FOR_PROVIDES(p, pp, con)
3084 if (dontfix2 && pool->solvables[p].repo == installed)
3091 return SOLVER_PROBLEM_PACKAGE_CONFLICT;
3095 /* check obsoletes in both directions */
3096 if ((!installed || s->repo != installed) && s->obsoletes)
3098 obsp = s->repo->idarraydata + s->obsoletes;
3099 while ((obs = *obsp++) != 0)
3101 FOR_PROVIDES(p, pp, obs)
3108 return SOLVER_PROBLEM_PACKAGE_OBSOLETES;
3112 if ((!installed || s2->repo != installed) && s2->obsoletes)
3114 obsp = s2->repo->idarraydata + s2->obsoletes;
3115 while ((obs = *obsp++) != 0)
3117 FOR_PROVIDES(p, pp, obs)
3124 return SOLVER_PROBLEM_PACKAGE_OBSOLETES;
3128 /* all cases checked, can't happen */
3131 /* simple requires */
3132 assert(s->requires);
3133 reqp = s->repo->idarraydata + s->requires;
3134 while ((req = *reqp++) != 0)
3136 if (req == SOLVABLE_PREREQMARKER)
3138 dp = pool_whatprovides(pool, req);
3141 if (*dp == r->w2 && dp[1] == 0)
3144 else if (dp - pool->whatprovidesdata == r->d)
3151 return SOLVER_PROBLEM_DEP_PROVIDERS_NOT_INSTALLABLE;
3155 findproblemrule_internal(Solver *solv, Id idx, Id *reqrp, Id *conrp, Id *sysrp, Id *jobrp)
3158 Id lreqr, lconr, lsysr, ljobr;
3162 lreqr = lconr = lsysr = ljobr = 0;
3163 while ((rid = solv->learnt_pool.elements[idx++]) != 0)
3165 if (rid >= solv->learntrules)
3166 findproblemrule_internal(solv, solv->learnt_why.elements[rid - solv->learntrules], &lreqr, &lconr, &lsysr, &ljobr);
3167 else if (rid >= solv->systemrules)
3172 else if (rid >= solv->jobrules)
3179 r = solv->rules + rid;
3180 if (!r->d && r->w2 < 0)
3193 /* assertion, counts as require rule */
3194 /* ignore system solvable as we need useful info */
3195 if (rid == -SYSTEMSOLVABLE)
3197 if (!*reqrp || !reqassert)
3204 if (!*reqrp && lreqr)
3206 if (!*conrp && lconr)
3208 if (!*jobrp && ljobr)
3210 if (!*sysrp && lsysr)
3215 solver_findproblemrule(Solver *solv, Id problem)
3217 Id reqr, conr, sysr, jobr;
3218 Id idx = solv->problems.elements[problem - 1];
3219 reqr = conr = sysr = jobr = 0;
3220 findproblemrule_internal(solv, idx, &reqr, &conr, &sysr, &jobr);
3233 printprobleminfo(Solver *solv, Queue *job, Id problem)
3235 Pool *pool = solv->pool;
3237 Id dep, source, target;
3240 probr = solver_findproblemrule(solv, problem);
3241 switch (solver_problemruleinfo(solv, job, probr, &dep, &source, &target))
3243 case SOLVER_PROBLEM_UPDATE_RULE:
3244 s = pool_id2solvable(pool, source);
3245 POOL_DEBUG(SAT_DEBUG_RESULT, "problem with installed package %s\n", solvable2str(pool, s));
3247 case SOLVER_PROBLEM_JOB_RULE:
3248 POOL_DEBUG(SAT_DEBUG_RESULT, "conflicting requests\n");
3250 case SOLVER_PROBLEM_JOB_NOTHING_PROVIDES_DEP:
3251 POOL_DEBUG(SAT_DEBUG_RESULT, "nothing provides requested %s\n", dep2str(pool, dep));
3253 case SOLVER_PROBLEM_NOT_INSTALLABLE:
3254 s = pool_id2solvable(pool, source);
3255 POOL_DEBUG(SAT_DEBUG_RESULT, "package %s is not installable\n", solvable2str(pool, s));
3257 case SOLVER_PROBLEM_NOTHING_PROVIDES_DEP:
3258 s = pool_id2solvable(pool, source);
3259 POOL_DEBUG(SAT_DEBUG_RESULT, "nothing provides %s needed by %s\n", dep2str(pool, dep), solvable2str(pool, s));
3261 case SOLVER_PROBLEM_SAME_NAME:
3262 s = pool_id2solvable(pool, source);
3263 s2 = pool_id2solvable(pool, target);
3264 POOL_DEBUG(SAT_DEBUG_RESULT, "cannot install both %s and %s\n", solvable2str(pool, s), solvable2str(pool, s2));
3266 case SOLVER_PROBLEM_PACKAGE_CONFLICT:
3267 s = pool_id2solvable(pool, source);
3268 s2 = pool_id2solvable(pool, target);
3269 POOL_DEBUG(SAT_DEBUG_RESULT, "package %s conflicts with %s provided by %s\n", solvable2str(pool, s), dep2str(pool, dep), solvable2str(pool, s2));
3271 case SOLVER_PROBLEM_PACKAGE_OBSOLETES:
3272 s = pool_id2solvable(pool, source);
3273 s2 = pool_id2solvable(pool, target);
3274 POOL_DEBUG(SAT_DEBUG_RESULT, "package %s obsoletes %s provided by %s\n", solvable2str(pool, s), dep2str(pool, dep), solvable2str(pool, s2));
3276 case SOLVER_PROBLEM_DEP_PROVIDERS_NOT_INSTALLABLE:
3277 s = pool_id2solvable(pool, source);
3278 POOL_DEBUG(SAT_DEBUG_RESULT, "package %s requires %s, but none of the providers can be installed\n", solvable2str(pool, s), dep2str(pool, dep));
3284 printsolutions(Solver *solv, Queue *job)
3286 Pool *pool = solv->pool;
3289 Id problem, solution, element;
3292 POOL_DEBUG(SAT_DEBUG_RESULT, "Encountered problems! Here are the solutions:\n\n");
3295 while ((problem = solver_next_problem(solv, problem)) != 0)
3297 POOL_DEBUG(SAT_DEBUG_RESULT, "Problem %d:\n", pcnt++);
3298 POOL_DEBUG(SAT_DEBUG_RESULT, "====================================\n");
3299 printprobleminfo(solv, job, problem);
3300 POOL_DEBUG(SAT_DEBUG_RESULT, "\n");
3302 while ((solution = solver_next_solution(solv, problem, solution)) != 0)
3305 while ((element = solver_next_solutionelement(solv, problem, solution, element, &p, &rp)) != 0)
3309 /* job, rp is index into job queue */
3310 what = job->elements[rp];
3311 switch (job->elements[rp - 1])
3313 case SOLVER_INSTALL_SOLVABLE:
3314 s = pool->solvables + what;
3315 if (solv->installed && s->repo == solv->installed)
3316 POOL_DEBUG(SAT_DEBUG_RESULT, "- do not keep %s installed\n", solvable2str(pool, s));
3318 POOL_DEBUG(SAT_DEBUG_RESULT, "- do not install %s\n", solvable2str(pool, s));
3320 case SOLVER_ERASE_SOLVABLE:
3321 s = pool->solvables + what;
3322 if (solv->installed && s->repo == solv->installed)
3323 POOL_DEBUG(SAT_DEBUG_RESULT, "- do not deinstall %s\n", solvable2str(pool, s));
3325 POOL_DEBUG(SAT_DEBUG_RESULT, "- do not forbid installation of %s\n", solvable2str(pool, s));
3327 case SOLVER_INSTALL_SOLVABLE_NAME:
3328 POOL_DEBUG(SAT_DEBUG_RESULT, "- do not install %s\n", id2str(pool, what));
3330 case SOLVER_ERASE_SOLVABLE_NAME:
3331 POOL_DEBUG(SAT_DEBUG_RESULT, "- do not deinstall %s\n", id2str(pool, what));
3333 case SOLVER_INSTALL_SOLVABLE_PROVIDES:
3334 POOL_DEBUG(SAT_DEBUG_RESULT, "- do not install a solvable providing %s\n", dep2str(pool, what));
3336 case SOLVER_ERASE_SOLVABLE_PROVIDES:
3337 POOL_DEBUG(SAT_DEBUG_RESULT, "- do not deinstall all solvables providing %s\n", dep2str(pool, what));
3339 case SOLVER_INSTALL_SOLVABLE_UPDATE:
3340 s = pool->solvables + what;
3341 POOL_DEBUG(SAT_DEBUG_RESULT, "- do not install most recent version of %s\n", solvable2str(pool, s));
3344 POOL_DEBUG(SAT_DEBUG_RESULT, "- do something different\n");
3350 /* policy, replace p with rp */
3351 s = pool->solvables + p;
3352 sd = rp ? pool->solvables + rp : 0;
3356 if (!solv->allowdowngrade && evrcmp(pool, s->evr, sd->evr, EVRCMP_MATCH_RELEASE) > 0)
3358 POOL_DEBUG(SAT_DEBUG_RESULT, "- allow downgrade of %s to %s\n", solvable2str(pool, s), solvable2str(pool, sd));
3361 if (!solv->allowarchchange && s->name == sd->name && s->arch != sd->arch && policy_illegal_archchange(solv, s, sd))
3363 POOL_DEBUG(SAT_DEBUG_RESULT, "- allow architecture change of %s to %s\n", solvable2str(pool, s), solvable2str(pool, sd));
3366 if (!solv->allowvendorchange && s->name == sd->name && s->vendor != sd->vendor && policy_illegal_vendorchange(solv, s, sd))
3369 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));
3371 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));
3375 POOL_DEBUG(SAT_DEBUG_RESULT, "- allow replacement of %s with %s\n", solvable2str(pool, s), solvable2str(pool, sd));
3379 POOL_DEBUG(SAT_DEBUG_RESULT, "- allow deinstallation of %s\n", solvable2str(pool, s));
3384 POOL_DEBUG(SAT_DEBUG_RESULT, "\n");
3390 /* create reverse obsoletes map for installed solvables
3392 * for each installed solvable find which packages with *different* names
3393 * obsolete the solvable.
3394 * this index is used in policy_findupdatepackages if noupdateprovide is set.
3398 create_obsolete_index(Solver *solv)
3400 Pool *pool = solv->pool;
3402 Repo *installed = solv->installed;
3403 Id p, *pp, obs, *obsp, *obsoletes, *obsoletes_data;
3406 if (!installed || !installed->nsolvables)
3408 solv->obsoletes = obsoletes = sat_calloc(installed->end - installed->start, sizeof(Id));
3409 for (i = 1; i < pool->nsolvables; i++)
3411 s = pool->solvables + i;
3412 if (s->repo == installed)
3416 if (!pool_installable(pool, s))
3418 obsp = s->repo->idarraydata + s->obsoletes;
3419 while ((obs = *obsp++) != 0)
3420 FOR_PROVIDES(p, pp, obs)
3422 if (pool->solvables[p].repo != installed)
3424 if (pool->solvables[p].name == s->name)
3426 obsoletes[p - installed->start]++;
3430 for (i = 0; i < installed->nsolvables; i++)
3433 n += obsoletes[i] + 1;
3436 solv->obsoletes_data = obsoletes_data = sat_calloc(n + 1, sizeof(Id));
3437 POOL_DEBUG(SAT_DEBUG_STATS, "obsoletes data: %d entries\n", n + 1);
3438 for (i = pool->nsolvables - 1; i > 0; i--)
3440 s = pool->solvables + i;
3441 if (s->repo == installed)
3445 if (!pool_installable(pool, s))
3447 obsp = s->repo->idarraydata + s->obsoletes;
3448 while ((obs = *obsp++) != 0)
3449 FOR_PROVIDES(p, pp, obs)
3451 if (pool->solvables[p].repo != installed)
3453 if (pool->solvables[p].name == s->name)
3455 p -= installed->start;
3456 if (obsoletes_data[obsoletes[p]] != i)
3457 obsoletes_data[--obsoletes[p]] = i;
3463 /*-----------------------------------------------------------------*/
3473 solver_solve(Solver *solv, Queue *job)
3475 Pool *pool = solv->pool;
3476 Repo *installed = solv->installed;
3479 Map addedmap; /* '1' == have rpm-rules for solvable */
3480 Id how, what, p, *pp, d;
3484 if (solv->limittokind != _KIND_MAX) /* if application wants to limit, make it non-zero */
3485 solv->limittokind += 1;
3487 solv->limittokind = 0;
3489 /* create whatprovides if not already there */
3490 if (!pool->whatprovides)
3491 pool_createwhatprovides(pool);
3493 /* create obsolete index if needed */
3494 if (solv->noupdateprovide)
3495 create_obsolete_index(solv);
3498 * create basic rule set of all involved packages
3499 * use addedmap bitmap to make sure we don't create rules twice
3503 map_init(&addedmap, pool->nsolvables);
3507 * always install our system solvable
3509 MAPSET(&addedmap, SYSTEMSOLVABLE);
3510 queue_push(&solv->decisionq, SYSTEMSOLVABLE);
3511 queue_push(&solv->decisionq_why, 0);
3512 solv->decisionmap[SYSTEMSOLVABLE] = 1;
3515 * create rules for all package that could be involved with the solving
3516 * so called: rpm rules
3521 oldnrules = solv->nrules;
3522 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for installed solvables ***\n");
3523 FOR_REPO_SOLVABLES(installed, p, s)
3524 addrpmrulesforsolvable(solv, s, &addedmap);
3525 POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for installed solvables\n", solv->nrules - oldnrules);
3526 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for updaters of installed solvables ***\n");
3527 oldnrules = solv->nrules;
3528 FOR_REPO_SOLVABLES(installed, p, s)
3529 addrpmrulesforupdaters(solv, s, &addedmap, 1);
3530 POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for updaters of installed solvables\n", solv->nrules - oldnrules);
3533 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for packages involved with a job ***\n");
3534 oldnrules = solv->nrules;
3535 for (i = 0; i < job->count; i += 2)
3537 how = job->elements[i];
3538 what = job->elements[i + 1];
3542 case SOLVER_INSTALL_SOLVABLE:
3543 addrpmrulesforsolvable(solv, pool->solvables + what, &addedmap);
3545 case SOLVER_INSTALL_SOLVABLE_NAME:
3546 case SOLVER_INSTALL_SOLVABLE_PROVIDES:
3547 FOR_PROVIDES(p, pp, what)
3549 /* if by name, ensure that the name matches */
3550 if (how == SOLVER_INSTALL_SOLVABLE_NAME && pool->solvables[p].name != what)
3552 addrpmrulesforsolvable(solv, pool->solvables + p, &addedmap);
3555 case SOLVER_INSTALL_SOLVABLE_UPDATE:
3556 /* dont allow downgrade */
3557 addrpmrulesforupdaters(solv, pool->solvables + what, &addedmap, 0);
3561 POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for packages involved in a job\n", solv->nrules - oldnrules);
3563 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for recommended/suggested packages ***\n");
3565 oldnrules = solv->nrules;
3566 addrpmrulesforweak(solv, &addedmap);
3567 POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules because of weak dependencies\n", solv->nrules - oldnrules);
3569 IF_POOLDEBUG (SAT_DEBUG_STATS)
3571 int possible = 0, installable = 0;
3572 for (i = 1; i < pool->nsolvables; i++)
3574 if (pool_installable(pool, pool->solvables + i))
3576 if (MAPTST(&addedmap, i))
3579 POOL_DEBUG(SAT_DEBUG_STATS, "%d of %d installable solvables considered for solving (rules has been generated for)\n", possible, installable);
3583 * first pass done, we now have all the rpm rules we need.
3584 * unify existing rules before going over all job rules and
3586 * at this point the system is always solvable,
3587 * as an empty system (remove all packages) is a valid solution
3590 unifyrules(solv); /* remove duplicate rpm rules */
3591 solv->directdecisions = solv->decisionq.count;
3593 POOL_DEBUG(SAT_DEBUG_STATS, "decisions so far: %d\n", solv->decisionq.count);
3594 IF_POOLDEBUG (SAT_DEBUG_SCHUBI)
3595 printdecisions (solv);
3598 * now add all job rules
3601 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** Add JOB rules ***\n");
3603 solv->jobrules = solv->nrules;
3605 for (i = 0; i < job->count; i += 2)
3607 oldnrules = solv->nrules;
3609 how = job->elements[i];
3610 what = job->elements[i + 1];
3613 case SOLVER_INSTALL_SOLVABLE: /* install specific solvable */
3614 s = pool->solvables + what;
3615 POOL_DEBUG(SAT_DEBUG_JOB, "job: install solvable %s\n", solvable2str(pool, s));
3616 addrule(solv, what, 0); /* install by Id */
3617 queue_push(&solv->ruletojob, i);
3619 case SOLVER_ERASE_SOLVABLE:
3620 s = pool->solvables + what;
3621 POOL_DEBUG(SAT_DEBUG_JOB, "job: erase solvable %s\n", solvable2str(pool, s));
3622 addrule(solv, -what, 0); /* remove by Id */
3623 queue_push(&solv->ruletojob, i);
3625 case SOLVER_INSTALL_SOLVABLE_NAME: /* install by capability */
3626 case SOLVER_INSTALL_SOLVABLE_PROVIDES:
3627 if (how == SOLVER_INSTALL_SOLVABLE_NAME)
3628 POOL_DEBUG(SAT_DEBUG_JOB, "job: install name %s\n", id2str(pool, what));
3629 if (how == SOLVER_INSTALL_SOLVABLE_PROVIDES)
3630 POOL_DEBUG(SAT_DEBUG_JOB, "job: install provides %s\n", dep2str(pool, what));
3632 FOR_PROVIDES(p, pp, what)
3634 /* if by name, ensure that the name matches */
3635 if (how == SOLVER_INSTALL_SOLVABLE_NAME && pool->solvables[p].name != what)
3641 /* no provider, make this an impossible rule */
3642 queue_push(&q, -SYSTEMSOLVABLE);
3645 p = queue_shift(&q); /* get first provider */
3647 d = 0; /* single provider ? -> make assertion */
3649 d = pool_queuetowhatprovides(pool, &q); /* get all providers */
3650 addrule(solv, p, d); /* add 'requires' rule */
3651 queue_push(&solv->ruletojob, i);
3653 case SOLVER_ERASE_SOLVABLE_NAME: /* remove by capability */
3654 case SOLVER_ERASE_SOLVABLE_PROVIDES:
3655 if (how == SOLVER_ERASE_SOLVABLE_NAME)
3656 POOL_DEBUG(SAT_DEBUG_JOB, "job: erase name %s\n", id2str(pool, what));
3657 if (how == SOLVER_ERASE_SOLVABLE_PROVIDES)
3658 POOL_DEBUG(SAT_DEBUG_JOB, "job: erase provides %s\n", dep2str(pool, what));
3659 FOR_PROVIDES(p, pp, what)
3661 /* if by name, ensure that the name matches */
3662 if (how == SOLVER_ERASE_SOLVABLE_NAME && pool->solvables[p].name != what)
3664 addrule(solv, -p, 0); /* add 'remove' rule */
3665 queue_push(&solv->ruletojob, i);
3668 case SOLVER_INSTALL_SOLVABLE_UPDATE: /* find update for solvable */
3669 s = pool->solvables + what;
3670 POOL_DEBUG(SAT_DEBUG_JOB, "job: update %s\n", solvable2str(pool, s));
3671 addupdaterule(solv, s, 0);
3672 queue_push(&solv->ruletojob, i);
3675 IF_POOLDEBUG (SAT_DEBUG_JOB)
3678 if (solv->nrules == oldnrules)
3679 POOL_DEBUG(SAT_DEBUG_JOB, " - no rule created");
3680 for (j = oldnrules; j < solv->nrules; j++)
3682 POOL_DEBUG(SAT_DEBUG_JOB, " - job ");
3683 printrule(solv, SAT_DEBUG_JOB, solv->rules + j);
3687 assert(solv->ruletojob.count == solv->nrules - solv->jobrules);
3690 * now add system rules
3694 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** Add system rules ***\n");
3697 solv->systemrules = solv->nrules;
3700 * create rules for updating installed solvables
3704 if (installed && !solv->allowuninstall)
3705 { /* loop over all installed solvables */
3706 /* we create all update rules, but disable some later on depending on the job */
3707 for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
3709 /* no system rules for patch atoms */
3710 if (s->freshens && !s->supplements)
3712 const char *name = id2str(pool, s->name);
3713 if (name[0] == 'a' && !strncmp(name, "atom:", 5))
3715 addrule(solv, 0, 0);
3719 if (s->repo == installed)
3720 addupdaterule(solv, s, 0); /* allowall = 0 */
3722 addrule(solv, 0, 0); /* create dummy rule */
3724 /* consistency check: we added a rule for _every_ system solvable */
3725 assert(solv->nrules - solv->systemrules == installed->end - installed->start);
3728 /* create special weak system rules */
3729 /* those are used later on to keep a version of the installed packages in
3731 if (installed && installed->nsolvables)
3733 solv->weaksystemrules = sat_calloc(installed->end - installed->start, sizeof(Id));
3734 FOR_REPO_SOLVABLES(installed, p, s)
3736 policy_findupdatepackages(solv, s, &q, 1);
3738 solv->weaksystemrules[p - installed->start] = pool_queuetowhatprovides(pool, &q);
3742 /* free unneeded memory */
3743 map_free(&addedmap);
3746 solv->weakrules = solv->nrules;
3748 /* try real hard to keep packages installed */
3751 FOR_REPO_SOLVABLES(installed, p, s)
3753 /* FIXME: can't work with refine_suggestion! */
3754 /* need to always add the rule but disable it */
3755 if (MAPTST(&solv->noupdate, p - installed->start))
3757 d = solv->weaksystemrules[p - installed->start];
3758 addrule(solv, p, d);
3762 /* all new rules are learnt after this point */
3763 solv->learntrules = solv->nrules;
3765 /* disable system rules that conflict with our job */
3766 disableupdaterules(solv, job, -1);
3768 /* make decisions based on job/system assertions */
3769 makeruledecisions(solv);
3771 /* create watches chains */
3774 POOL_DEBUG(SAT_DEBUG_STATS, "problems so far: %d\n", solv->problems.count);
3777 run_solver(solv, 1, 1);
3779 /* find suggested packages */
3780 if (!solv->problems.count)
3782 Id sug, *sugp, p, *pp;
3784 /* create map of all suggests that are still open */
3785 solv->recommends_index = -1;
3786 MAPZERO(&solv->suggestsmap);
3787 for (i = 0; i < solv->decisionq.count; i++)
3789 p = solv->decisionq.elements[i];
3792 s = pool->solvables + p;
3795 sugp = s->repo->idarraydata + s->suggests;
3796 while ((sug = *sugp++) != 0)
3798 FOR_PROVIDES(p, pp, sug)
3799 if (solv->decisionmap[p] > 0)
3802 continue; /* already fulfilled */
3803 FOR_PROVIDES(p, pp, sug)
3804 MAPSET(&solv->suggestsmap, p);
3808 for (i = 1; i < pool->nsolvables; i++)
3810 if (solv->decisionmap[i] != 0)
3812 s = pool->solvables + i;
3813 if (!MAPTST(&solv->suggestsmap, i))
3817 if (!pool_installable(pool, s))
3819 if (!solver_is_enhancing(solv, s))
3822 queue_push(&solv->suggestions, i);
3824 policy_filter_unwanted(solv, &solv->suggestions, 0, POLICY_MODE_SUGGEST);
3827 if (solv->problems.count)
3828 problems_to_solutions(solv, job);