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));
2128 solver_free(Solver *solv)
2130 queue_free(&solv->ruletojob);
2131 queue_free(&solv->decisionq);
2132 queue_free(&solv->decisionq_why);
2133 queue_free(&solv->learnt_why);
2134 queue_free(&solv->learnt_pool);
2135 queue_free(&solv->problems);
2136 queue_free(&solv->suggestions);
2137 queue_free(&solv->branches);
2138 queue_free(&solv->covenantq);
2140 map_free(&solv->recommendsmap);
2141 map_free(&solv->suggestsmap);
2142 map_free(&solv->noupdate);
2144 sat_free(solv->decisionmap);
2145 sat_free(solv->rules);
2146 sat_free(solv->watches);
2147 sat_free(solv->weaksystemrules);
2148 sat_free(solv->obsoletes);
2149 sat_free(solv->obsoletes_data);
2154 /*-------------------------------------------------------*/
2159 * all rules have been set up, now actually run the solver
2164 run_solver(Solver *solv, int disablerules, int doweak)
2172 Pool *pool = solv->pool;
2175 IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION)
2177 POOL_DEBUG (SAT_DEBUG_RULE_CREATION, "number of rules: %d\n", solv->nrules);
2178 for (i = 0; i < solv->nrules; i++)
2179 printrule(solv, SAT_DEBUG_RULE_CREATION, solv->rules + i);
2182 POOL_DEBUG(SAT_DEBUG_STATS, "initial decisions: %d\n", solv->decisionq.count);
2184 IF_POOLDEBUG (SAT_DEBUG_SCHUBI)
2185 printdecisions(solv);
2187 /* start SAT algorithm */
2189 systemlevel = level + 1;
2190 POOL_DEBUG(SAT_DEBUG_STATS, "solving...\n");
2201 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "propagating (propagate_index: %d; size decisionq: %d)...\n", solv->propagate_index, solv->decisionq.count);
2202 if ((r = propagate(solv, level)) != 0)
2204 if (analyze_unsolvable(solv, r, disablerules))
2212 * installed packages
2215 if (level < systemlevel && solv->installed && solv->installed->nsolvables)
2217 if (!solv->updatesystem)
2219 /* try to keep as many packages as possible */
2220 POOL_DEBUG(SAT_DEBUG_STATS, "installing system packages\n");
2221 for (i = solv->installed->start, n = 0; ; i++)
2223 if (n == solv->installed->nsolvables)
2225 if (i == solv->installed->end)
2226 i = solv->installed->start;
2227 s = pool->solvables + i;
2228 if (s->repo != solv->installed)
2231 if (solv->decisionmap[i] != 0)
2233 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "keeping %s\n", solvable2str(pool, s));
2235 level = setpropagatelearn(solv, level, i, disablerules);
2241 if (level <= olevel)
2245 if (solv->weaksystemrules)
2247 POOL_DEBUG(SAT_DEBUG_STATS, "installing weak system packages\n");
2248 for (i = solv->installed->start; i < solv->installed->end; i++)
2250 if (pool->solvables[i].repo != solv->installed)
2252 if (solv->decisionmap[i] > 0 || (solv->decisionmap[i] < 0 && solv->weaksystemrules[i - solv->installed->start] == 0))
2254 /* noupdate is set if a job is erasing the installed solvable or installing a specific version */
2255 if (MAPTST(&solv->noupdate, i - solv->installed->start))
2258 if (solv->weaksystemrules[i - solv->installed->start])
2260 dp = pool->whatprovidesdata + solv->weaksystemrules[i - solv->installed->start];
2261 while ((p = *dp++) != 0)
2263 if (solv->decisionmap[p] > 0)
2265 if (solv->decisionmap[p] == 0)
2269 continue; /* update package already installed */
2271 if (!dq.count && solv->decisionmap[i] != 0)
2274 /* FIXME: i is handled a bit different because we do not want
2275 * to have it pruned just because it is not recommened.
2276 * we should not prune installed packages instead */
2277 level = selectandinstall(solv, level, &dq, (solv->decisionmap[i] ? 0 : i), disablerules);
2283 if (level <= olevel)
2286 if (i < solv->installed->end)
2289 systemlevel = level;
2296 POOL_DEBUG(SAT_DEBUG_STATS, "deciding unresolved rules\n");
2297 for (i = 1, n = 1; ; i++, n++)
2299 if (n == solv->nrules)
2301 if (i == solv->nrules)
2303 r = solv->rules + i;
2304 if (!r->w1) /* ignore disabled rules */
2309 /* binary or unary rule */
2310 /* need two positive undecided literals */
2311 if (r->p < 0 || r->w2 <= 0)
2313 if (solv->decisionmap[r->p] || solv->decisionmap[r->w2])
2315 queue_push(&dq, r->p);
2316 queue_push(&dq, r->w2);
2321 * all negative literals are installed
2322 * no positive literal is installed
2323 * i.e. the rule is not fulfilled and we
2324 * just need to decide on the positive literals
2328 if (solv->decisionmap[-r->p] <= 0)
2333 if (solv->decisionmap[r->p] > 0)
2335 if (solv->decisionmap[r->p] == 0)
2336 queue_push(&dq, r->p);
2338 dp = pool->whatprovidesdata + r->d;
2339 while ((p = *dp++) != 0)
2343 if (solv->decisionmap[-p] <= 0)
2348 if (solv->decisionmap[p] > 0)
2350 if (solv->decisionmap[p] == 0)
2357 /* dq.count < 2 cannot happen as this means that
2358 * the rule is unit */
2359 assert(dq.count > 1);
2360 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
2362 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "unfulfilled ");
2363 printrule(solv, SAT_DEBUG_PROPAGATE, r);
2367 level = selectandinstall(solv, level, &dq, 0, disablerules);
2373 if (level < systemlevel)
2376 } /* for(), decide */
2378 if (n != solv->nrules) /* continue if level < systemlevel */
2381 if (doweak && !solv->problems.count)
2385 POOL_DEBUG(SAT_DEBUG_STATS, "installing recommended packages\n");
2386 if (!solv->dosplitprovides && !REGARD_RECOMMENDS_OF_INSTALLED_ITEMS)
2388 for (i = 1; i < solv->decisionq.count; i++)
2390 p = solv->decisionq.elements[i];
2391 if (p > 0 && pool->solvables[p].repo == solv->installed)
2392 solv->decisionmap[p] = -solv->decisionmap[p];
2396 for (i = 1; i < pool->nsolvables; i++)
2398 if (solv->decisionmap[i] < 0)
2400 if (solv->decisionmap[i] > 0)
2402 Id *recp, rec, *pp, p;
2403 s = pool->solvables + i;
2404 /* installed, check for recommends */
2405 /* XXX need to special case AND ? */
2408 recp = s->repo->idarraydata + s->recommends;
2409 while ((rec = *recp++) != 0)
2412 FOR_PROVIDES(p, pp, rec)
2414 if (solv->decisionmap[p] > 0)
2419 else if (solv->decisionmap[p] == 0)
2421 queue_pushunique(&dq, p);
2429 s = pool->solvables + i;
2430 if (!s->supplements && !s->freshens)
2432 if (!pool_installable(pool, s))
2434 if (solver_is_supplementing(solv, s))
2435 queue_pushunique(&dq, i);
2438 if (!solv->dosplitprovides && !REGARD_RECOMMENDS_OF_INSTALLED_ITEMS)
2440 for (i = 1; i < solv->decisionq.count; i++)
2442 p = solv->decisionq.elements[i];
2443 if (p > 0 && pool->solvables[p].repo == solv->installed)
2444 solv->decisionmap[p] = -solv->decisionmap[p];
2450 policy_filter_unwanted(solv, &dq, 0, POLICY_MODE_RECOMMEND);
2452 POOL_DEBUG(SAT_DEBUG_STATS, "installing recommended %s\n", solvable2str(pool, pool->solvables + p));
2453 level = setpropagatelearn(solv, level, p, 0);
2458 if (solv->solution_callback)
2460 solv->solution_callback(solv, solv->solution_callback_data);
2461 if (solv->branches.count)
2463 int i = solv->branches.count - 1;
2464 int l = -solv->branches.elements[i];
2466 if (solv->branches.elements[i - 1] < 0)
2468 p = solv->branches.elements[i];
2469 POOL_DEBUG(SAT_DEBUG_STATS, "branching with %s\n", solvable2str(pool, pool->solvables + p));
2471 for (j = i + 1; j < solv->branches.count; j++)
2472 queue_push(&dq, solv->branches.elements[j]);
2473 solv->branches.count = i;
2475 revert(solv, level);
2477 for (j = 0; j < dq.count; j++)
2478 queue_push(&solv->branches, dq.elements[j]);
2480 level = setpropagatelearn(solv, level, p, disablerules);
2488 /* all branches done, we're finally finished */
2492 /* minimization step */
2493 if (solv->branches.count)
2495 int l = 0, lasti = -1, lastl = -1;
2497 for (i = solv->branches.count - 1; i >= 0; i--)
2499 p = solv->branches.elements[i];
2502 else if (p > 0 && solv->decisionmap[p] > l + 1)
2510 /* kill old solvable so that we do not loop */
2511 p = solv->branches.elements[lasti];
2512 solv->branches.elements[lasti] = 0;
2513 POOL_DEBUG(SAT_DEBUG_STATS, "minimizing %d -> %d with %s\n", solv->decisionmap[p], l, solvable2str(pool, pool->solvables + p));
2516 revert(solv, level);
2518 level = setpropagatelearn(solv, level, p, disablerules);
2535 * at this point, all rules that led to conflicts are disabled.
2536 * we re-enable all rules of a problem set but rule "sug", then
2537 * continue to disable more rules until there as again a solution.
2540 /* FIXME: think about conflicting assertions */
2543 refine_suggestion(Solver *solv, Queue *job, Id *problem, Id sug, Queue *refined)
2545 Pool *pool = solv->pool;
2552 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
2554 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "refine_suggestion start\n");
2555 for (i = 0; problem[i]; i++)
2557 if (problem[i] == sug)
2558 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "=> ");
2559 printproblem(solv, problem[i]);
2562 queue_init(&disabled);
2563 queue_empty(refined);
2564 queue_push(refined, sug);
2566 /* re-enable all problem rules with the exception of "sug" */
2570 for (i = 0; problem[i]; i++)
2571 if (problem[i] != sug)
2572 enableproblem(solv, problem[i]);
2575 disableupdaterules(solv, job, -(sug + 1));
2579 /* re-enable as many weak rules as possible */
2580 for (i = solv->weakrules; i < solv->learntrules; i++)
2582 r = solv->rules + i;
2584 enablerule(solv, r);
2587 queue_empty(&solv->problems);
2588 revert(solv, 1); /* XXX move to reset_solver? */
2591 if (!solv->problems.count)
2592 run_solver(solv, 0, 0);
2594 if (!solv->problems.count)
2596 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "no more problems!\n");
2597 IF_POOLDEBUG (SAT_DEBUG_SCHUBI)
2598 printdecisions(solv);
2599 break; /* great, no more problems */
2601 disabledcnt = disabled.count;
2602 /* start with 1 to skip over proof index */
2603 for (i = 1; i < solv->problems.count - 1; i++)
2605 /* ignore solutions in refined */
2606 v = solv->problems.elements[i];
2608 break; /* end of problem reached */
2609 for (j = 0; problem[j]; j++)
2610 if (problem[j] != sug && problem[j] == v)
2614 queue_push(&disabled, v);
2616 if (disabled.count == disabledcnt)
2618 /* no solution found, this was an invalid suggestion! */
2619 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "no solution found!\n");
2623 if (disabled.count == disabledcnt + 1)
2625 /* just one suggestion, add it to refined list */
2626 v = disabled.elements[disabledcnt];
2627 queue_push(refined, v);
2628 disableproblem(solv, v);
2630 disableupdaterules(solv, job, -(v + 1));
2634 /* more than one solution, disable all */
2635 /* do not push anything on refine list */
2636 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
2638 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "more than one solution found:\n");
2639 for (i = disabledcnt; i < disabled.count; i++)
2640 printproblem(solv, disabled.elements[i]);
2642 for (i = disabledcnt; i < disabled.count; i++)
2643 disableproblem(solv, disabled.elements[i]);
2646 /* all done, get us back into the same state as before */
2647 /* enable refined rules again */
2648 for (i = 0; i < disabled.count; i++)
2649 enableproblem(solv, disabled.elements[i]);
2650 /* disable problem rules again */
2651 for (i = 0; problem[i]; i++)
2652 disableproblem(solv, problem[i]);
2653 disableupdaterules(solv, job, -1);
2654 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "refine_suggestion end\n");
2658 problems_to_solutions(Solver *solv, Queue *job)
2660 Pool *pool = solv->pool;
2668 if (!solv->problems.count)
2670 queue_clone(&problems, &solv->problems);
2671 queue_init(&solution);
2672 queue_init(&solutions);
2673 /* copy over proof index */
2674 queue_push(&solutions, problems.elements[0]);
2675 problem = problems.elements + 1;
2676 for (i = 1; i < problems.count; i++)
2678 Id v = problems.elements[i];
2681 /* mark end of this problem */
2682 queue_push(&solutions, 0);
2683 queue_push(&solutions, 0);
2684 if (i + 1 == problems.count)
2686 /* copy over proof of next problem */
2687 queue_push(&solutions, problems.elements[i + 1]);
2689 problem = problems.elements + i + 1;
2692 refine_suggestion(solv, job, problem, v, &solution);
2693 if (!solution.count)
2694 continue; /* this solution didn't work out */
2696 for (j = 0; j < solution.count; j++)
2698 why = solution.elements[j];
2699 /* must be either job descriptor or system rule */
2700 assert(why < 0 || (why >= solv->systemrules && why < solv->weakrules));
2702 printproblem(solv, why);
2706 /* job descriptor */
2707 queue_push(&solutions, 0);
2708 queue_push(&solutions, -why);
2712 /* system rule, find replacement package */
2714 p = solv->installed->start + (why - solv->systemrules);
2715 if (solv->weaksystemrules && solv->weaksystemrules[why - solv->systemrules])
2717 Id *dp = pool->whatprovidesdata + solv->weaksystemrules[why - solv->systemrules];
2720 if (*dp >= solv->installed->start && *dp < solv->installed->start + solv->installed->nsolvables)
2722 if (solv->decisionmap[*dp] > 0)
2729 queue_push(&solutions, p);
2730 queue_push(&solutions, rp);
2733 /* mark end of this solution */
2734 queue_push(&solutions, 0);
2735 queue_push(&solutions, 0);
2737 queue_free(&solution);
2738 queue_free(&problems);
2739 /* copy queue over to solutions */
2740 queue_free(&solv->problems);
2741 queue_clone(&solv->problems, &solutions);
2743 /* bring solver back into problem state */
2744 revert(solv, 1); /* XXX move to reset_solver? */
2747 assert(solv->problems.count == solutions.count);
2748 queue_free(&solutions);
2752 solver_next_problem(Solver *solv, Id problem)
2756 return solv->problems.count ? 1 : 0;
2757 pp = solv->problems.elements + problem;
2758 while (pp[0] || pp[1])
2762 while (pp[0] || pp[1])
2767 problem = pp - solv->problems.elements;
2768 if (problem >= solv->problems.count)
2774 solver_next_solution(Solver *solv, Id problem, Id solution)
2780 pp = solv->problems.elements + solution;
2781 return pp[0] || pp[1] ? solution : 0;
2783 pp = solv->problems.elements + solution;
2784 while (pp[0] || pp[1])
2787 solution = pp - solv->problems.elements;
2788 return pp[0] || pp[1] ? solution : 0;
2792 solver_next_solutionelement(Solver *solv, Id problem, Id solution, Id element, Id *p, Id *rp)
2795 element = element ? element + 2 : solution;
2796 pp = solv->problems.elements + element;
2797 if (!(pp[0] || pp[1]))
2806 * create obsoletesmap from solver decisions
2807 * required for decision handling
2811 create_decisions_obsoletesmap(Solver *solv)
2813 Pool *pool = solv->pool;
2814 Repo *installed = solv->installed;
2815 Id p, *obsoletesmap = NULL;
2819 obsoletesmap = (Id *)sat_calloc(pool->nsolvables, sizeof(Id));
2822 for (i = 0; i < solv->decisionq.count; i++)
2826 n = solv->decisionq.elements[i];
2829 if (n == SYSTEMSOLVABLE)
2831 s = pool->solvables + n;
2832 if (s->repo == installed) /* obsoletes don't count for already installed packages */
2834 FOR_PROVIDES(p, pp, s->name)
2835 if (s->name == pool->solvables[p].name)
2837 if (pool->solvables[p].repo == installed && !obsoletesmap[p])
2839 obsoletesmap[p] = n;
2844 for (i = 0; i < solv->decisionq.count; i++)
2849 n = solv->decisionq.elements[i];
2852 if (n == SYSTEMSOLVABLE)
2854 s = pool->solvables + n;
2855 if (s->repo == installed) /* obsoletes don't count for already installed packages */
2859 obsp = s->repo->idarraydata + s->obsoletes;
2860 while ((obs = *obsp++) != 0)
2861 FOR_PROVIDES(p, pp, obs)
2863 if (pool->solvables[p].repo == installed && !obsoletesmap[p])
2865 obsoletesmap[p] = n;
2871 return obsoletesmap;
2880 printdecisions(Solver *solv)
2882 Pool *pool = solv->pool;
2883 Repo *installed = solv->installed;
2884 Id p, *obsoletesmap = create_decisions_obsoletesmap( solv );
2888 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- Decisions -----\n");
2890 /* print solvables to be erased */
2894 FOR_REPO_SOLVABLES(installed, p, s)
2896 if (solv->decisionmap[p] >= 0)
2898 if (obsoletesmap[p])
2900 POOL_DEBUG(SAT_DEBUG_RESULT, "erase %s\n", solvable2str(pool, s));
2904 /* print solvables to be installed */
2906 for (i = 0; i < solv->decisionq.count; i++)
2909 p = solv->decisionq.elements[i];
2912 IF_POOLDEBUG (SAT_DEBUG_SCHUBI)
2915 s = pool->solvables + p;
2916 POOL_DEBUG(SAT_DEBUG_SCHUBI, "level of %s is %d\n", solvable2str(pool, s), p);
2920 if (p == SYSTEMSOLVABLE)
2922 POOL_DEBUG(SAT_DEBUG_SCHUBI, "SYSTEMSOLVABLE\n");
2925 s = pool->solvables + p;
2926 if (installed && s->repo == installed)
2929 if (!obsoletesmap[p])
2931 POOL_DEBUG(SAT_DEBUG_RESULT, "install %s", solvable2str(pool, s));
2935 POOL_DEBUG(SAT_DEBUG_RESULT, "update %s", solvable2str(pool, s));
2936 POOL_DEBUG(SAT_DEBUG_RESULT, " (obsoletes");
2937 for (j = installed->start; j < installed->end; j++)
2938 if (obsoletesmap[j] == p)
2939 POOL_DEBUG(SAT_DEBUG_RESULT, " %s", solvable2str(pool, pool->solvables + j));
2940 POOL_DEBUG(SAT_DEBUG_RESULT, ")");
2942 POOL_DEBUG(SAT_DEBUG_RESULT, "\n");
2945 sat_free(obsoletesmap);
2947 if (solv->suggestions.count)
2949 POOL_DEBUG(SAT_DEBUG_RESULT, "\nsuggested packages:\n");
2950 for (i = 0; i < solv->suggestions.count; i++)
2952 s = pool->solvables + solv->suggestions.elements[i];
2953 POOL_DEBUG(SAT_DEBUG_RESULT, "- %s\n", solvable2str(pool, s));
2956 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- Decisions end -----\n");
2959 /* this is basically the reverse of addrpmrulesforsolvable */
2961 solver_problemruleinfo(Solver *solv, Queue *job, Id rid, Id *depp, Id *sourcep, Id *targetp)
2963 Pool *pool = solv->pool;
2964 Repo *installed = solv->installed;
2968 Id p, *pp, req, *reqp, con, *conp, obs, *obsp, *dp;
2970 assert(rid < solv->weakrules);
2971 if (rid >= solv->systemrules)
2974 *sourcep = solv->installed->start + (rid - solv->systemrules);
2976 return SOLVER_PROBLEM_UPDATE_RULE;
2978 if (rid >= solv->jobrules)
2981 r = solv->rules + rid;
2982 p = solv->ruletojob.elements[rid - solv->jobrules];
2983 *depp = job->elements[p + 1];
2985 *targetp = job->elements[p];
2986 if (r->d == 0 && r->w2 == 0 && r->p == -SYSTEMSOLVABLE)
2987 return SOLVER_PROBLEM_JOB_NOTHING_PROVIDES_DEP;
2988 return SOLVER_PROBLEM_JOB_RULE;
2992 /* a rpm rule assertion */
2993 assert(rid != -SYSTEMSOLVABLE);
2994 s = pool->solvables - rid;
2995 if (installed && !solv->fixsystem && s->repo == installed)
2997 assert(!dontfix); /* dontfix packages never have a neg assertion */
2998 /* see why the package is not installable */
2999 if (s->arch != ARCH_SRC && s->arch != ARCH_NOSRC && !pool_installable(pool, s))
3000 return SOLVER_PROBLEM_NOT_INSTALLABLE;
3001 /* check requires */
3002 assert(s->requires);
3003 reqp = s->repo->idarraydata + s->requires;
3004 while ((req = *reqp++) != 0)
3006 if (req == SOLVABLE_PREREQMARKER)
3008 dp = pool_whatprovides(pool, req);
3016 return SOLVER_PROBLEM_NOTHING_PROVIDES_DEP;
3018 r = solv->rules + rid;
3020 if (r->d == 0 && r->w2 == 0)
3022 /* an assertion. we don't store them as rpm rules, so
3026 s = pool->solvables - r->p;
3027 if (installed && !solv->fixsystem && s->repo == installed)
3029 if (r->d == 0 && r->w2 < 0)
3031 /* a package conflict */
3032 Solvable *s2 = pool->solvables - r->w2;
3035 if (installed && !solv->fixsystem && s2->repo == installed)
3038 /* if both packages have the same name and at least one of them
3039 * is not installed, they conflict */
3040 if (s->name == s2->name && (!installed || (s->repo != installed || s2->repo != installed)))
3045 return SOLVER_PROBLEM_SAME_NAME;
3048 /* check conflicts in both directions */
3051 conp = s->repo->idarraydata + s->conflicts;
3052 while ((con = *conp++) != 0)
3054 FOR_PROVIDES(p, pp, con)
3056 if (dontfix && pool->solvables[p].repo == installed)
3063 return SOLVER_PROBLEM_PACKAGE_CONFLICT;
3069 conp = s2->repo->idarraydata + s2->conflicts;
3070 while ((con = *conp++) != 0)
3072 FOR_PROVIDES(p, pp, con)
3074 if (dontfix2 && pool->solvables[p].repo == installed)
3081 return SOLVER_PROBLEM_PACKAGE_CONFLICT;
3085 /* check obsoletes in both directions */
3086 if ((!installed || s->repo != installed) && s->obsoletes)
3088 obsp = s->repo->idarraydata + s->obsoletes;
3089 while ((obs = *obsp++) != 0)
3091 FOR_PROVIDES(p, pp, obs)
3098 return SOLVER_PROBLEM_PACKAGE_OBSOLETES;
3102 if ((!installed || s2->repo != installed) && s2->obsoletes)
3104 obsp = s2->repo->idarraydata + s2->obsoletes;
3105 while ((obs = *obsp++) != 0)
3107 FOR_PROVIDES(p, pp, obs)
3114 return SOLVER_PROBLEM_PACKAGE_OBSOLETES;
3118 /* all cases checked, can't happen */
3121 /* simple requires */
3122 assert(s->requires);
3123 reqp = s->repo->idarraydata + s->requires;
3124 while ((req = *reqp++) != 0)
3126 if (req == SOLVABLE_PREREQMARKER)
3128 dp = pool_whatprovides(pool, req);
3131 if (*dp == r->w2 && dp[1] == 0)
3134 else if (dp - pool->whatprovidesdata == r->d)
3141 return SOLVER_PROBLEM_DEP_PROVIDERS_NOT_INSTALLABLE;
3145 findproblemrule_internal(Solver *solv, Id idx, Id *reqrp, Id *conrp, Id *sysrp, Id *jobrp)
3148 Id lreqr, lconr, lsysr, ljobr;
3152 lreqr = lconr = lsysr = ljobr = 0;
3153 while ((rid = solv->learnt_pool.elements[idx++]) != 0)
3155 if (rid >= solv->learntrules)
3156 findproblemrule_internal(solv, solv->learnt_why.elements[rid - solv->learntrules], &lreqr, &lconr, &lsysr, &ljobr);
3157 else if (rid >= solv->systemrules)
3162 else if (rid >= solv->jobrules)
3169 r = solv->rules + rid;
3170 if (!r->d && r->w2 < 0)
3183 /* assertion, counts as require rule */
3184 /* ignore system solvable as we need useful info */
3185 if (rid == -SYSTEMSOLVABLE)
3187 if (!*reqrp || !reqassert)
3194 if (!*reqrp && lreqr)
3196 if (!*conrp && lconr)
3198 if (!*jobrp && ljobr)
3200 if (!*sysrp && lsysr)
3205 solver_findproblemrule(Solver *solv, Id problem)
3207 Id reqr, conr, sysr, jobr;
3208 Id idx = solv->problems.elements[problem - 1];
3209 reqr = conr = sysr = jobr = 0;
3210 findproblemrule_internal(solv, idx, &reqr, &conr, &sysr, &jobr);
3223 printprobleminfo(Solver *solv, Queue *job, Id problem)
3225 Pool *pool = solv->pool;
3227 Id dep, source, target;
3230 probr = solver_findproblemrule(solv, problem);
3231 switch (solver_problemruleinfo(solv, job, probr, &dep, &source, &target))
3233 case SOLVER_PROBLEM_UPDATE_RULE:
3234 s = pool_id2solvable(pool, source);
3235 POOL_DEBUG(SAT_DEBUG_RESULT, "problem with installed package %s\n", solvable2str(pool, s));
3237 case SOLVER_PROBLEM_JOB_RULE:
3238 POOL_DEBUG(SAT_DEBUG_RESULT, "conflicting requests\n");
3240 case SOLVER_PROBLEM_JOB_NOTHING_PROVIDES_DEP:
3241 POOL_DEBUG(SAT_DEBUG_RESULT, "nothing provides requested %s\n", dep2str(pool, dep));
3243 case SOLVER_PROBLEM_NOT_INSTALLABLE:
3244 s = pool_id2solvable(pool, source);
3245 POOL_DEBUG(SAT_DEBUG_RESULT, "package %s is not installable\n", solvable2str(pool, s));
3247 case SOLVER_PROBLEM_NOTHING_PROVIDES_DEP:
3248 s = pool_id2solvable(pool, source);
3249 POOL_DEBUG(SAT_DEBUG_RESULT, "nothing provides %s needed by %s\n", dep2str(pool, dep), solvable2str(pool, s));
3251 case SOLVER_PROBLEM_SAME_NAME:
3252 s = pool_id2solvable(pool, source);
3253 s2 = pool_id2solvable(pool, target);
3254 POOL_DEBUG(SAT_DEBUG_RESULT, "cannot install both %s and %s\n", solvable2str(pool, s), solvable2str(pool, s2));
3256 case SOLVER_PROBLEM_PACKAGE_CONFLICT:
3257 s = pool_id2solvable(pool, source);
3258 s2 = pool_id2solvable(pool, target);
3259 POOL_DEBUG(SAT_DEBUG_RESULT, "package %s conflicts with %s provided by %s\n", solvable2str(pool, s), dep2str(pool, dep), solvable2str(pool, s2));
3261 case SOLVER_PROBLEM_PACKAGE_OBSOLETES:
3262 s = pool_id2solvable(pool, source);
3263 s2 = pool_id2solvable(pool, target);
3264 POOL_DEBUG(SAT_DEBUG_RESULT, "package %s obsoletes %s provided by %s\n", solvable2str(pool, s), dep2str(pool, dep), solvable2str(pool, s2));
3266 case SOLVER_PROBLEM_DEP_PROVIDERS_NOT_INSTALLABLE:
3267 s = pool_id2solvable(pool, source);
3268 POOL_DEBUG(SAT_DEBUG_RESULT, "package %s requires %s, but none of the providers can be installed\n", solvable2str(pool, s), dep2str(pool, dep));
3274 printsolutions(Solver *solv, Queue *job)
3276 Pool *pool = solv->pool;
3279 Id problem, solution, element;
3282 POOL_DEBUG(SAT_DEBUG_RESULT, "Encountered problems! Here are the solutions:\n\n");
3285 while ((problem = solver_next_problem(solv, problem)) != 0)
3287 POOL_DEBUG(SAT_DEBUG_RESULT, "Problem %d:\n", pcnt++);
3288 POOL_DEBUG(SAT_DEBUG_RESULT, "====================================\n");
3289 printprobleminfo(solv, job, problem);
3290 POOL_DEBUG(SAT_DEBUG_RESULT, "\n");
3292 while ((solution = solver_next_solution(solv, problem, solution)) != 0)
3295 while ((element = solver_next_solutionelement(solv, problem, solution, element, &p, &rp)) != 0)
3299 /* job, rp is index into job queue */
3300 what = job->elements[rp];
3301 switch (job->elements[rp - 1])
3303 case SOLVER_INSTALL_SOLVABLE:
3304 s = pool->solvables + what;
3305 if (solv->installed && s->repo == solv->installed)
3306 POOL_DEBUG(SAT_DEBUG_RESULT, "- do not keep %s installed\n", solvable2str(pool, s));
3308 POOL_DEBUG(SAT_DEBUG_RESULT, "- do not install %s\n", solvable2str(pool, s));
3310 case SOLVER_ERASE_SOLVABLE:
3311 s = pool->solvables + what;
3312 if (solv->installed && s->repo == solv->installed)
3313 POOL_DEBUG(SAT_DEBUG_RESULT, "- do not deinstall %s\n", solvable2str(pool, s));
3315 POOL_DEBUG(SAT_DEBUG_RESULT, "- do not forbid installation of %s\n", solvable2str(pool, s));
3317 case SOLVER_INSTALL_SOLVABLE_NAME:
3318 POOL_DEBUG(SAT_DEBUG_RESULT, "- do not install %s\n", id2str(pool, what));
3320 case SOLVER_ERASE_SOLVABLE_NAME:
3321 POOL_DEBUG(SAT_DEBUG_RESULT, "- do not deinstall %s\n", id2str(pool, what));
3323 case SOLVER_INSTALL_SOLVABLE_PROVIDES:
3324 POOL_DEBUG(SAT_DEBUG_RESULT, "- do not install a solvable providing %s\n", dep2str(pool, what));
3326 case SOLVER_ERASE_SOLVABLE_PROVIDES:
3327 POOL_DEBUG(SAT_DEBUG_RESULT, "- do not deinstall all solvables providing %s\n", dep2str(pool, what));
3329 case SOLVER_INSTALL_SOLVABLE_UPDATE:
3330 s = pool->solvables + what;
3331 POOL_DEBUG(SAT_DEBUG_RESULT, "- do not install most recent version of %s\n", solvable2str(pool, s));
3334 POOL_DEBUG(SAT_DEBUG_RESULT, "- do something different\n");
3340 /* policy, replace p with rp */
3341 s = pool->solvables + p;
3342 sd = rp ? pool->solvables + rp : 0;
3346 if (!solv->allowdowngrade && evrcmp(pool, s->evr, sd->evr, EVRCMP_MATCH_RELEASE) > 0)
3348 POOL_DEBUG(SAT_DEBUG_RESULT, "- allow downgrade of %s to %s\n", solvable2str(pool, s), solvable2str(pool, sd));
3351 if (!solv->allowarchchange && s->name == sd->name && s->arch != sd->arch && policy_illegal_archchange(solv, s, sd))
3353 POOL_DEBUG(SAT_DEBUG_RESULT, "- allow architecture change of %s to %s\n", solvable2str(pool, s), solvable2str(pool, sd));
3356 if (!solv->allowvendorchange && s->name == sd->name && s->vendor != sd->vendor && policy_illegal_vendorchange(solv, s, sd))
3359 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));
3361 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));
3365 POOL_DEBUG(SAT_DEBUG_RESULT, "- allow replacement of %s with %s\n", solvable2str(pool, s), solvable2str(pool, sd));
3369 POOL_DEBUG(SAT_DEBUG_RESULT, "- allow deinstallation of %s\n", solvable2str(pool, s));
3374 POOL_DEBUG(SAT_DEBUG_RESULT, "\n");
3380 /* create reverse obsoletes map for installed solvables
3382 * for each installed solvable find which packages with *different* names
3383 * obsolete the solvable.
3384 * this index is used in policy_findupdatepackages if noupdateprovide is set.
3388 create_obsolete_index(Solver *solv)
3390 Pool *pool = solv->pool;
3392 Repo *installed = solv->installed;
3393 Id p, *pp, obs, *obsp, *obsoletes, *obsoletes_data;
3396 if (!installed || !installed->nsolvables)
3398 solv->obsoletes = obsoletes = sat_calloc(installed->end - installed->start, sizeof(Id));
3399 for (i = 1; i < pool->nsolvables; i++)
3401 s = pool->solvables + i;
3402 if (s->repo == installed)
3406 if (!pool_installable(pool, s))
3408 obsp = s->repo->idarraydata + s->obsoletes;
3409 while ((obs = *obsp++) != 0)
3410 FOR_PROVIDES(p, pp, obs)
3412 if (pool->solvables[p].repo != installed)
3414 if (pool->solvables[p].name == s->name)
3416 obsoletes[p - installed->start]++;
3420 for (i = 0; i < installed->nsolvables; i++)
3423 n += obsoletes[i] + 1;
3426 solv->obsoletes_data = obsoletes_data = sat_calloc(n + 1, sizeof(Id));
3427 POOL_DEBUG(SAT_DEBUG_STATS, "obsoletes data: %d entries\n", n + 1);
3428 for (i = pool->nsolvables - 1; i > 0; i--)
3430 s = pool->solvables + i;
3431 if (s->repo == installed)
3435 if (!pool_installable(pool, s))
3437 obsp = s->repo->idarraydata + s->obsoletes;
3438 while ((obs = *obsp++) != 0)
3439 FOR_PROVIDES(p, pp, obs)
3441 if (pool->solvables[p].repo != installed)
3443 if (pool->solvables[p].name == s->name)
3445 p -= installed->start;
3446 if (obsoletes_data[obsoletes[p]] != i)
3447 obsoletes_data[--obsoletes[p]] = i;
3453 /*-----------------------------------------------------------------*/
3463 solver_solve(Solver *solv, Queue *job)
3465 Pool *pool = solv->pool;
3466 Repo *installed = solv->installed;
3469 Map addedmap; /* '1' == have rpm-rules for solvable */
3470 Id how, what, p, *pp, d;
3474 /* create whatprovides if not already there */
3475 if (!pool->whatprovides)
3476 pool_createwhatprovides(pool);
3478 /* create obsolete index if needed */
3479 if (solv->noupdateprovide)
3480 create_obsolete_index(solv);
3483 * create basic rule set of all involved packages
3484 * use addedmap bitmap to make sure we don't create rules twice
3488 map_init(&addedmap, pool->nsolvables);
3492 * always install our system solvable
3494 MAPSET(&addedmap, SYSTEMSOLVABLE);
3495 queue_push(&solv->decisionq, SYSTEMSOLVABLE);
3496 queue_push(&solv->decisionq_why, 0);
3497 solv->decisionmap[SYSTEMSOLVABLE] = 1;
3500 * create rules for all package that could be involved with the solving
3501 * so called: rpm rules
3506 oldnrules = solv->nrules;
3507 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for installed solvables ***\n");
3508 FOR_REPO_SOLVABLES(installed, p, s)
3509 addrpmrulesforsolvable(solv, s, &addedmap);
3510 POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for installed solvables\n", solv->nrules - oldnrules);
3511 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for updaters of installed solvables ***\n");
3512 oldnrules = solv->nrules;
3513 FOR_REPO_SOLVABLES(installed, p, s)
3514 addrpmrulesforupdaters(solv, s, &addedmap, 1);
3515 POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for updaters of installed solvables\n", solv->nrules - oldnrules);
3518 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for packages involved with a job ***\n");
3519 oldnrules = solv->nrules;
3520 for (i = 0; i < job->count; i += 2)
3522 how = job->elements[i];
3523 what = job->elements[i + 1];
3527 case SOLVER_INSTALL_SOLVABLE:
3528 addrpmrulesforsolvable(solv, pool->solvables + what, &addedmap);
3530 case SOLVER_INSTALL_SOLVABLE_NAME:
3531 case SOLVER_INSTALL_SOLVABLE_PROVIDES:
3532 FOR_PROVIDES(p, pp, what)
3534 /* if by name, ensure that the name matches */
3535 if (how == SOLVER_INSTALL_SOLVABLE_NAME && pool->solvables[p].name != what)
3537 addrpmrulesforsolvable(solv, pool->solvables + p, &addedmap);
3540 case SOLVER_INSTALL_SOLVABLE_UPDATE:
3541 /* dont allow downgrade */
3542 addrpmrulesforupdaters(solv, pool->solvables + what, &addedmap, 0);
3546 POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for packages involved in a job\n", solv->nrules - oldnrules);
3548 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for recommended/suggested packages ***\n");
3550 oldnrules = solv->nrules;
3551 addrpmrulesforweak(solv, &addedmap);
3552 POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules because of weak dependencies\n", solv->nrules - oldnrules);
3554 IF_POOLDEBUG (SAT_DEBUG_STATS)
3556 int possible = 0, installable = 0;
3557 for (i = 1; i < pool->nsolvables; i++)
3559 if (pool_installable(pool, pool->solvables + i))
3561 if (MAPTST(&addedmap, i))
3564 POOL_DEBUG(SAT_DEBUG_STATS, "%d of %d installable solvables considered for solving (rules has been generated for)\n", possible, installable);
3568 * first pass done, we now have all the rpm rules we need.
3569 * unify existing rules before going over all job rules and
3571 * at this point the system is always solvable,
3572 * as an empty system (remove all packages) is a valid solution
3575 unifyrules(solv); /* remove duplicate rpm rules */
3576 solv->directdecisions = solv->decisionq.count;
3578 POOL_DEBUG(SAT_DEBUG_STATS, "decisions so far: %d\n", solv->decisionq.count);
3579 IF_POOLDEBUG (SAT_DEBUG_SCHUBI)
3580 printdecisions (solv);
3583 * now add all job rules
3586 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** Add JOB rules ***\n");
3588 solv->jobrules = solv->nrules;
3590 for (i = 0; i < job->count; i += 2)
3592 oldnrules = solv->nrules;
3594 how = job->elements[i];
3595 what = job->elements[i + 1];
3598 case SOLVER_INSTALL_SOLVABLE: /* install specific solvable */
3599 s = pool->solvables + what;
3600 POOL_DEBUG(SAT_DEBUG_JOB, "job: install solvable %s\n", solvable2str(pool, s));
3601 addrule(solv, what, 0); /* install by Id */
3602 queue_push(&solv->ruletojob, i);
3604 case SOLVER_ERASE_SOLVABLE:
3605 s = pool->solvables + what;
3606 POOL_DEBUG(SAT_DEBUG_JOB, "job: erase solvable %s\n", solvable2str(pool, s));
3607 addrule(solv, -what, 0); /* remove by Id */
3608 queue_push(&solv->ruletojob, i);
3610 case SOLVER_INSTALL_SOLVABLE_NAME: /* install by capability */
3611 case SOLVER_INSTALL_SOLVABLE_PROVIDES:
3612 if (how == SOLVER_INSTALL_SOLVABLE_NAME)
3613 POOL_DEBUG(SAT_DEBUG_JOB, "job: install name %s\n", id2str(pool, what));
3614 if (how == SOLVER_INSTALL_SOLVABLE_PROVIDES)
3615 POOL_DEBUG(SAT_DEBUG_JOB, "job: install provides %s\n", dep2str(pool, what));
3617 FOR_PROVIDES(p, pp, what)
3619 /* if by name, ensure that the name matches */
3620 if (how == SOLVER_INSTALL_SOLVABLE_NAME && pool->solvables[p].name != what)
3626 /* no provider, make this an impossible rule */
3627 queue_push(&q, -SYSTEMSOLVABLE);
3630 p = queue_shift(&q); /* get first provider */
3632 d = 0; /* single provider ? -> make assertion */
3634 d = pool_queuetowhatprovides(pool, &q); /* get all providers */
3635 addrule(solv, p, d); /* add 'requires' rule */
3636 queue_push(&solv->ruletojob, i);
3638 case SOLVER_ERASE_SOLVABLE_NAME: /* remove by capability */
3639 case SOLVER_ERASE_SOLVABLE_PROVIDES:
3640 if (how == SOLVER_ERASE_SOLVABLE_NAME)
3641 POOL_DEBUG(SAT_DEBUG_JOB, "job: erase name %s\n", id2str(pool, what));
3642 if (how == SOLVER_ERASE_SOLVABLE_PROVIDES)
3643 POOL_DEBUG(SAT_DEBUG_JOB, "job: erase provides %s\n", dep2str(pool, what));
3644 FOR_PROVIDES(p, pp, what)
3646 /* if by name, ensure that the name matches */
3647 if (how == SOLVER_ERASE_SOLVABLE_NAME && pool->solvables[p].name != what)
3649 addrule(solv, -p, 0); /* add 'remove' rule */
3650 queue_push(&solv->ruletojob, i);
3653 case SOLVER_INSTALL_SOLVABLE_UPDATE: /* find update for solvable */
3654 s = pool->solvables + what;
3655 POOL_DEBUG(SAT_DEBUG_JOB, "job: update %s\n", solvable2str(pool, s));
3656 addupdaterule(solv, s, 0);
3657 queue_push(&solv->ruletojob, i);
3660 IF_POOLDEBUG (SAT_DEBUG_JOB)
3663 if (solv->nrules == oldnrules)
3664 POOL_DEBUG(SAT_DEBUG_JOB, " - no rule created");
3665 for (j = oldnrules; j < solv->nrules; j++)
3667 POOL_DEBUG(SAT_DEBUG_JOB, " - job ");
3668 printrule(solv, SAT_DEBUG_JOB, solv->rules + j);
3672 assert(solv->ruletojob.count == solv->nrules - solv->jobrules);
3675 * now add system rules
3679 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** Add system rules ***\n");
3682 solv->systemrules = solv->nrules;
3685 * create rules for updating installed solvables
3689 if (installed && !solv->allowuninstall)
3690 { /* loop over all installed solvables */
3691 /* we create all update rules, but disable some later on depending on the job */
3692 for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
3694 /* no system rules for patch atoms */
3695 if (s->freshens && !s->supplements)
3697 const char *name = id2str(pool, s->name);
3698 if (name[0] == 'a' && !strncmp(name, "atom:", 5))
3700 addrule(solv, 0, 0);
3704 if (s->repo == installed)
3705 addupdaterule(solv, s, 0); /* allowall = 0 */
3707 addrule(solv, 0, 0); /* create dummy rule */
3709 /* consistency check: we added a rule for _every_ system solvable */
3710 assert(solv->nrules - solv->systemrules == installed->end - installed->start);
3713 /* create special weak system rules */
3714 /* those are used later on to keep a version of the installed packages in
3716 if (installed && installed->nsolvables)
3718 solv->weaksystemrules = sat_calloc(installed->end - installed->start, sizeof(Id));
3719 FOR_REPO_SOLVABLES(installed, p, s)
3721 policy_findupdatepackages(solv, s, &q, 1);
3723 solv->weaksystemrules[p - installed->start] = pool_queuetowhatprovides(pool, &q);
3727 /* free unneeded memory */
3728 map_free(&addedmap);
3731 solv->weakrules = solv->nrules;
3733 /* try real hard to keep packages installed */
3736 FOR_REPO_SOLVABLES(installed, p, s)
3738 /* FIXME: can't work with refine_suggestion! */
3739 /* need to always add the rule but disable it */
3740 if (MAPTST(&solv->noupdate, p - installed->start))
3742 d = solv->weaksystemrules[p - installed->start];
3743 addrule(solv, p, d);
3747 /* all new rules are learnt after this point */
3748 solv->learntrules = solv->nrules;
3750 /* disable system rules that conflict with our job */
3751 disableupdaterules(solv, job, -1);
3753 /* make decisions based on job/system assertions */
3754 makeruledecisions(solv);
3756 /* create watches chains */
3759 POOL_DEBUG(SAT_DEBUG_STATS, "problems so far: %d\n", solv->problems.count);
3762 run_solver(solv, 1, 1);
3764 /* find suggested packages */
3765 if (!solv->problems.count)
3767 Id sug, *sugp, p, *pp;
3769 /* create map of all suggests that are still open */
3770 solv->recommends_index = -1;
3771 MAPZERO(&solv->suggestsmap);
3772 for (i = 0; i < solv->decisionq.count; i++)
3774 p = solv->decisionq.elements[i];
3777 s = pool->solvables + p;
3780 sugp = s->repo->idarraydata + s->suggests;
3781 while ((sug = *sugp++) != 0)
3783 FOR_PROVIDES(p, pp, sug)
3784 if (solv->decisionmap[p] > 0)
3787 continue; /* already fulfilled */
3788 FOR_PROVIDES(p, pp, sug)
3789 MAPSET(&solv->suggestsmap, p);
3793 for (i = 1; i < pool->nsolvables; i++)
3795 if (solv->decisionmap[i] != 0)
3797 s = pool->solvables + i;
3798 if (!MAPTST(&solv->suggestsmap, i))
3802 if (!pool_installable(pool, s))
3804 if (!solver_is_enhancing(solv, s))
3807 queue_push(&solv->suggestions, i);
3809 policy_filter_unwanted(solv, &solv->suggestions, 0, POLICY_MODE_SUGGEST);
3812 if (solv->problems.count)
3813 problems_to_solutions(solv, job);