2 * Copyright (c) 2007, Novell Inc.
4 * This program is licensed under the BSD license, read LICENSE.BSD
5 * for further information
11 * SAT based dependency solver
26 #define RULES_BLOCK 63
30 solver_dep_installed(Solver *solv, Id dep)
32 /* disable for now, splitprovides don't work anyway and it breaks
35 Pool *pool = solv->pool;
40 Reldep *rd = GETRELDEP(pool, dep);
41 if (rd->flags == REL_AND)
43 if (!solver_dep_installed(solv, rd->name))
45 return solver_dep_installed(solv, rd->evr);
47 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
48 return solver_dep_installed(solv, rd->evr);
50 FOR_PROVIDES(p, pp, dep)
52 if (p == SYSTEMSOLVABLE || (solv->installed && pool->solvables[p].repo == solv->installed))
60 /* this mirrors solver_dep_fulfilled but uses map m instead of the decisionmap */
62 dep_possible(Solver *solv, Id dep, Map *m)
64 Pool *pool = solv->pool;
69 Reldep *rd = GETRELDEP(pool, dep);
70 if (rd->flags == REL_AND)
72 if (!dep_possible(solv, rd->name, m))
74 return dep_possible(solv, rd->evr, m);
76 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
77 return solver_dep_installed(solv, rd->evr);
79 FOR_PROVIDES(p, pp, dep)
87 /*-----------------------------------------------------------------*/
94 printruleelement(Solver *solv, int type, Rule *r, Id v)
96 Pool *pool = solv->pool;
100 s = pool->solvables + -v;
101 POOL_DEBUG(type, " !%s [%d]", solvable2str(pool, s), -v);
105 s = pool->solvables + v;
106 POOL_DEBUG(type, " %s [%d]", solvable2str(pool, s), v);
111 POOL_DEBUG(type, " (w1)");
113 POOL_DEBUG(type, " (w2)");
115 if (solv->decisionmap[s - pool->solvables] > 0)
116 POOL_DEBUG(type, " Install.level%d", solv->decisionmap[s - pool->solvables]);
117 if (solv->decisionmap[s - pool->solvables] < 0)
118 POOL_DEBUG(type, " Conflict.level%d", -solv->decisionmap[s - pool->solvables]);
119 POOL_DEBUG(type, "\n");
128 printrule(Solver *solv, int type, Rule *r)
130 Pool *pool = solv->pool;
134 if (r >= solv->rules && r < solv->rules + solv->nrules) /* r is a solver rule */
135 POOL_DEBUG(type, "Rule #%d:", (int)(r - solv->rules));
137 POOL_DEBUG(type, "Rule:"); /* r is any rule */
139 POOL_DEBUG(type, " (disabled)");
140 POOL_DEBUG(type, "\n");
145 else if (r->d == ID_NULL)
152 v = solv->pool->whatprovidesdata[r->d + i - 1];
155 printruleelement(solv, type, r, v);
157 POOL_DEBUG(type, " next: %d %d\n", r->n1, r->n2);
161 printruleclass(Solver *solv, int type, Rule *r)
163 Pool *pool = solv->pool;
164 if (r - solv->rules >= solv->learntrules)
165 POOL_DEBUG(type, "LEARNT ");
166 else if (r - solv->rules >= solv->weakrules)
167 POOL_DEBUG(type, "WEAK ");
168 else if (r - solv->rules >= solv->systemrules)
169 POOL_DEBUG(type, "SYSTEM ");
170 else if (r - solv->rules >= solv->jobrules)
171 POOL_DEBUG(type, "JOB ");
172 printrule(solv, type, r);
176 /*-----------------------------------------------------------------*/
182 static Pool *unifyrules_sortcmp_data;
185 * compare rules for unification sort
189 unifyrules_sortcmp(const void *ap, const void *bp)
191 Pool *pool = unifyrules_sortcmp_data;
192 Rule *a = (Rule *)ap;
193 Rule *b = (Rule *)bp;
199 return x; /* p differs */
202 if (a->d == 0 && b->d == 0)
203 return a->w2 - b->w2; /* assertion: return w2 diff */
205 if (a->d == 0) /* a is assertion, b not */
207 x = a->w2 - pool->whatprovidesdata[b->d];
211 if (b->d == 0) /* b is assertion, a not */
213 x = pool->whatprovidesdata[a->d] - b->w2;
217 /* compare whatprovidesdata */
218 ad = pool->whatprovidesdata + a->d;
219 bd = pool->whatprovidesdata + b->d;
221 if ((x = *ad++ - *bd++) != 0)
232 unifyrules(Solver *solv)
234 Pool *pool = solv->pool;
238 if (solv->nrules <= 1) /* nothing to unify */
241 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- unifyrules -----\n");
243 /* sort rules first */
244 unifyrules_sortcmp_data = solv->pool;
245 qsort(solv->rules + 1, solv->nrules - 1, sizeof(Rule), unifyrules_sortcmp);
252 for (i = j = 1, ir = solv->rules + 1; i < solv->nrules; i++, ir++)
254 if (jr && !unifyrules_sortcmp(ir, jr))
255 continue; /* prune! */
256 jr = solv->rules + j++; /* keep! */
261 /* reduced count from nrules to j rules */
262 POOL_DEBUG(SAT_DEBUG_STATS, "pruned rules from %d to %d\n", solv->nrules, j);
264 /* adapt rule buffer */
266 solv->rules = (Rule *)xrealloc(solv->rules, ((solv->nrules + RULES_BLOCK) & ~RULES_BLOCK) * sizeof(Rule));
267 IF_POOLDEBUG (SAT_DEBUG_STATS)
274 for (i = 1; i < solv->nrules; i++)
281 dp = solv->pool->whatprovidesdata + r->d;
286 POOL_DEBUG(SAT_DEBUG_STATS, " binary: %d\n", binr);
287 POOL_DEBUG(SAT_DEBUG_STATS, " normal: %d, %d literals\n", solv->nrules - 1 - binr, lits);
289 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- unifyrules end -----\n");
299 hashrule(Solver *solv, Id p, Id d, int n)
301 unsigned int x = (unsigned int)p;
305 return (x * 37) ^ (unsigned int)d;
306 dp = solv->pool->whatprovidesdata + d;
308 x = (x * 37) ^ (unsigned int)*dp++;
316 * p = direct literal; always < 0 for installed rpm rules
317 * d, if < 0 direct literal, if > 0 offset into whatprovides, if == 0 rule is assertion (look at p only)
320 * A requires b, b provided by B1,B2,B3 => (-A|B1|B2|B3)
322 * p < 0 : pkg id of A
323 * d > 0 : Offset in whatprovidesdata (list of providers of b)
325 * A conflicts b, b provided by B1,B2,B3 => (-A|-B1), (-A|-B2), (-A|-B3)
326 * p < 0 : pkg id of A
327 * d < 0 : Id of solvable (e.g. B1)
329 * d == 0: unary rule, assertion => (A) or (-A)
331 * Install: p > 0, d = 0 (A) user requested install
332 * Remove: p < 0, d = 0 (-A) user requested remove
333 * Requires: p < 0, d > 0 (-A|B1|B2|...) d: <list of providers for requirement of p>
334 * Updates: p > 0, d > 0 (A|B1|B2|...) d: <list of updates for solvable p>
335 * Conflicts: p < 0, d < 0 (-A|-B) either p (conflict issuer) or d (conflict provider) (binary rule)
336 * ? p > 0, d < 0 (A|-B)
337 * No-op ?: p = 0, d = 0 (null) (used as policy rule placeholder)
341 * Direct assertion (no watch needed)( if d <0 ) --> d = 0, w1 = p, w2 = 0
342 * Binary rule: p = first literal, d = 0, w2 = second literal, w1 = p
343 * every other : w1 = p, w2 = whatprovidesdata[d];
344 * Disabled rule: w1 = 0
346 * always returns a rule for non-rpm rules
350 addrule(Solver *solv, Id p, Id d)
352 Pool *pool = solv->pool;
356 int n = 0; /* number of literals in rule - 1
357 0 = direct assertion (single literal)
361 /* it often happenes that requires lead to adding the same rpm rule
362 * multiple times, so we prune those duplicates right away to make
363 * the work for unifyrules a bit easier */
365 if (solv->nrules && !solv->jobrules)
367 r = solv->rules + solv->nrules - 1; /* get the last added rule */
368 if (r->p == p && r->d == d && d != 0) /* identical and not user requested */
374 /* always a binary rule */
376 return 0; /* ignore self conflict */
381 for (dp = pool->whatprovidesdata + d; *dp; dp++, n++)
383 return 0; /* rule is self-fulfilling */
388 if (n == 0 && !solv->jobrules)
390 /* this is a rpm rule assertion, we do not have to allocate it */
391 /* it can be identified by a level of 1 and a zero reason */
392 /* we must not drop those rules from the decisionq when rewinding! */
395 if (solv->decisionmap[-p] > 0 || solv->decisionmap[-p] < -1)
397 if (solv->decisionmap[-p])
398 return 0; /* already got that one */
399 queue_push(&solv->decisionq, p);
400 queue_push(&solv->decisionq_why, 0);
401 solv->decisionmap[-p] = -1;
406 /* smallest literal first so we can find dups */
410 n = 1; /* re-set n, was used as temp var */
413 /* check if the last added rule is exactly the same as what we're looking for. */
414 if (r && n == 1 && !r->d && r->p == p && r->w2 == d)
417 if (r && n > 1 && r->d && r->p == p)
422 dp2 = pool->whatprovidesdata + r->d;
423 for (dp = pool->whatprovidesdata + d; *dp; dp++, dp2++)
434 /* check and extend rule buffer */
435 if ((solv->nrules & RULES_BLOCK) == 0)
437 solv->rules = (Rule *)xrealloc(solv->rules, (solv->nrules + (RULES_BLOCK + 1)) * sizeof(Rule));
440 r = solv->rules + solv->nrules++; /* point to rule space */
445 /* direct assertion, no watch needed */
461 r->w2 = pool->whatprovidesdata[d];
466 IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION)
468 POOL_DEBUG(SAT_DEBUG_RULE_CREATION, " Add rule: ");
469 printrule(solv, SAT_DEBUG_RULE_CREATION, r);
476 disablerule(Solver *solv, Rule *r)
482 enablerule(Solver *solv, Rule *r)
484 if (r->d == 0 || r->w2 != r->p)
487 r->w1 = solv->pool->whatprovidesdata[r->d];
491 /**********************************************************************************/
493 /* a problem is an item on the solver's problem list. It can either be >0, in that
494 * case it is a system (upgrade) rule, or it can be <0, which makes it refer to a job
495 * consisting of multiple job rules.
499 disableproblem(Solver *solv, Id v)
507 disablerule(solv, solv->rules + v);
511 jp = solv->ruletojob.elements;
512 for (i = solv->jobrules, r = solv->rules + i; i < solv->systemrules; i++, r++, jp++)
514 disablerule(solv, r);
518 enableproblem(Solver *solv, Id v)
526 enablerule(solv, solv->rules + v);
530 jp = solv->ruletojob.elements;
531 for (i = solv->jobrules, r = solv->rules + i; i < solv->systemrules; i++, r++, jp++)
537 printproblem(Solver *solv, Id v)
539 Pool *pool = solv->pool;
545 printrule(solv, SAT_DEBUG_SOLUTIONS, solv->rules + v);
549 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "JOB %d\n", v);
550 jp = solv->ruletojob.elements;
551 for (i = solv->jobrules, r = solv->rules + i; i < solv->systemrules; i++, r++, jp++)
554 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "- ");
555 printrule(solv, SAT_DEBUG_SOLUTIONS, r);
557 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "ENDJOB\n");
563 /************************************************************************/
565 /* go through system and job rules and add direct assertions
566 * to the decisionqueue. If we find a conflict, disable rules and
567 * add them to problem queue.
568 * (disablerules is always true for the cases when we get called)
571 makeruledecisions(Solver *solv)
573 Pool *pool = solv->pool;
579 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- makeruledecisions ; size decisionq: %d -----\n",solv->decisionq.count);
581 decisionstart = solv->decisionq.count;
582 /* rpm rules don't have assertions, so we can start with the job
584 for (ri = solv->jobrules, r = solv->rules + ri; ri < solv->nrules; ri++, r++)
586 if (!r->w1 || r->w2) /* disabled or no assertion */
590 if (solv->decisionmap[vv] == 0)
592 queue_push(&solv->decisionq, v);
593 queue_push(&solv->decisionq_why, r - solv->rules);
594 solv->decisionmap[vv] = v > 0 ? 1 : -1;
595 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
597 Solvable *s = solv->pool->solvables + vv;
599 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "conflicting %s (assertion)\n", solvable2str(solv->pool, s));
601 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "installing %s (assertion)\n", solvable2str(solv->pool, s));
605 if (v > 0 && solv->decisionmap[vv] > 0)
607 if (v < 0 && solv->decisionmap[vv] < 0)
609 /* found a conflict! */
610 if (ri >= solv->learntrules)
612 /* cannot happen, as this would mean that the problem
613 * was not solvable, so we wouldn't have created the
614 * learnt rule at all */
617 /* if we are weak, just disable ourself */
618 if (ri >= solv->weakrules)
620 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "assertion conflict, but I am weak, disabling ");
621 printrule(solv, SAT_DEBUG_UNSOLVABLE, r);
622 disablerule(solv, r);
626 /* only job and system rules left */
627 for (i = 0; i < solv->decisionq.count; i++)
628 if (solv->decisionq.elements[i] == -v)
630 if (i == solv->decisionq.count)
632 if (solv->decisionq_why.elements[i] == 0)
634 /* conflict with rpm rule, need only disable our rule */
635 if (v < 0 && v != -SYSTEMSOLVABLE)
638 queue_push(&solv->problems, solv->learnt_pool.count);
639 queue_push(&solv->learnt_pool, ri);
640 queue_push(&solv->learnt_pool, v != -SYSTEMSOLVABLE ? -v : v);
641 queue_push(&solv->learnt_pool, 0);
642 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "conflict with rpm rule, disabling rule #%d\n", ri);
643 if (ri < solv->systemrules)
644 v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
647 queue_push(&solv->problems, v);
648 disableproblem(solv, v);
649 queue_push(&solv->problems, 0);
653 queue_push(&solv->problems, solv->learnt_pool.count);
654 queue_push(&solv->learnt_pool, ri);
655 queue_push(&solv->learnt_pool, solv->decisionq_why.elements[i]);
656 queue_push(&solv->learnt_pool, 0);
658 /* conflict with another job or system rule */
659 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "conflicting system/job assertions over literal %d\n", vv);
660 /* push all of our rules asserting this literal on the problem stack */
661 for (i = solv->jobrules, rr = solv->rules + i; i < solv->nrules; i++, rr++)
663 if (!rr->w1 || rr->w2)
665 if (rr->p != vv && rr->p != -vv)
667 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, " - disabling rule #%d\n", i);
669 if (i < solv->systemrules)
670 v = -(solv->ruletojob.elements[i - solv->jobrules] + 1);
671 queue_push(&solv->problems, v);
672 disableproblem(solv, v);
674 queue_push(&solv->problems, 0);
677 while (solv->decisionq.count > decisionstart)
679 v = solv->decisionq.elements[--solv->decisionq.count];
680 --solv->decisionq_why.count;
682 solv->decisionmap[vv] = 0;
684 ri = solv->jobrules - 1;
685 r = solv->rules + ri;
688 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- makeruledecisions end; size decisionq: %d -----\n",solv->decisionq.count);
692 * we have enabled or disabled some of our rules. We now reenable all
693 * of our learnt rules but the ones that were learnt from rules that
697 enabledisablelearntrules(Solver *solv)
699 Pool *pool = solv->pool;
704 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "enabledisablelearntrules called\n");
705 for (i = solv->learntrules, r = solv->rules + i; i < solv->nrules; i++, r++)
707 whyp = solv->learnt_pool.elements + solv->learnt_why.elements[i - solv->learntrules];
708 while ((why = *whyp++) != 0)
710 if (why < 0 || why >= i)
711 abort(); /* cannot reference newer learnt rules */
712 if (!solv->rules[why].w1)
715 /* why != 0: we found a disabled rule, disable the learnt rule */
718 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
720 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "disabling learnt ");
721 printrule(solv, SAT_DEBUG_SOLUTIONS, r);
723 disablerule(solv, r);
725 else if (!why && !r->w1)
727 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
729 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "re-enabling learnt ");
730 printrule(solv, SAT_DEBUG_SOLUTIONS, r);
738 /* FIXME: bad code ahead, replace as soon as possible */
740 disableupdaterules(Solver *solv, Queue *job, int jobidx)
742 Pool *pool = solv->pool;
744 Id how, what, p, *pp;
750 installed = solv->installed;
756 how = job->elements[jobidx];
759 case SOLVER_INSTALL_SOLVABLE:
760 case SOLVER_ERASE_SOLVABLE:
761 case SOLVER_ERASE_SOLVABLE_NAME:
762 case SOLVER_ERASE_SOLVABLE_PROVIDES:
768 /* go through all enabled job rules */
769 MAPZERO(&solv->noupdate);
770 for (i = solv->jobrules; i < solv->systemrules; i++)
773 if (!r->w1) /* disabled? */
775 j = solv->ruletojob.elements[i - solv->jobrules];
779 how = job->elements[j];
780 what = job->elements[j + 1];
783 case SOLVER_INSTALL_SOLVABLE: /* install specific solvable */
784 s = pool->solvables + what;
785 FOR_PROVIDES(p, pp, s->name)
787 if (pool->solvables[p].name != s->name)
789 if (pool->solvables[p].repo == installed)
790 MAPSET(&solv->noupdate, p - installed->start);
793 case SOLVER_ERASE_SOLVABLE:
794 s = pool->solvables + what;
795 if (s->repo == installed)
796 MAPSET(&solv->noupdate, what - installed->start);
798 case SOLVER_ERASE_SOLVABLE_NAME: /* remove by capability */
799 case SOLVER_ERASE_SOLVABLE_PROVIDES:
800 FOR_PROVIDES(p, pp, what)
802 if (how == SOLVER_ERASE_SOLVABLE_NAME && pool->solvables[p].name != what)
804 if (pool->solvables[p].repo == installed)
805 MAPSET(&solv->noupdate, p - installed->start);
813 /* fixup update rule status */
814 if (solv->allowuninstall)
815 return; /* no update rules at all */
819 /* we just disabled job #jobidx. enable all update rules
820 * that aren't disabled by the remaining job rules */
821 how = job->elements[jobidx];
822 what = job->elements[jobidx + 1];
825 case SOLVER_INSTALL_SOLVABLE:
826 s = pool->solvables + what;
827 FOR_PROVIDES(p, pp, s->name)
829 if (pool->solvables[p].name != s->name)
831 if (pool->solvables[p].repo != installed)
833 if (MAPTST(&solv->noupdate, p - installed->start))
835 r = solv->rules + solv->systemrules + (p - installed->start);
839 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
841 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
842 printrule(solv, SAT_DEBUG_SOLUTIONS, r);
846 case SOLVER_ERASE_SOLVABLE:
847 s = pool->solvables + what;
848 if (s->repo != installed)
850 if (MAPTST(&solv->noupdate, what - installed->start))
852 r = solv->rules + solv->systemrules + (what - installed->start);
856 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
858 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
859 printrule(solv, SAT_DEBUG_SOLUTIONS, r);
862 case SOLVER_ERASE_SOLVABLE_NAME: /* remove by capability */
863 case SOLVER_ERASE_SOLVABLE_PROVIDES:
864 FOR_PROVIDES(p, pp, what)
866 if (how == SOLVER_ERASE_SOLVABLE_NAME && pool->solvables[p].name != what)
868 if (pool->solvables[p].repo != installed)
870 if (MAPTST(&solv->noupdate, p - installed->start))
872 r = solv->rules + solv->systemrules + (p - installed->start);
876 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
878 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
879 printrule(solv, SAT_DEBUG_SOLUTIONS, r);
889 for (i = 0; i < installed->nsolvables; i++)
891 r = solv->rules + solv->systemrules + i;
892 if (r->w1 && MAPTST(&solv->noupdate, i))
893 disablerule(solv, r); /* was enabled, need to disable */
899 * add (install) rules for solvable
900 * for unfulfilled requirements, conflicts, obsoletes,....
901 * add a negative assertion for solvables that are not installable
905 addrpmrulesforsolvable(Solver *solv, Solvable *s, Map *m)
907 Pool *pool = solv->pool;
908 Repo *installed = solv->installed;
922 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforsolvable -----\n");
924 queue_init_buffer(&q, qbuf, sizeof(qbuf)/sizeof(*qbuf));
925 queue_push(&q, s - pool->solvables); /* push solvable Id */
931 * s: Pointer to solvable
935 if (MAPTST(m, n)) /* continue if already done */
939 s = pool->solvables + n; /* s = Solvable in question */
942 if (installed /* Installed system available */
943 && !solv->fixsystem /* NOT repair errors in rpm dependency graph */
944 && s->repo == installed) /* solvable is installed? */
946 dontfix = 1; /* dont care about broken rpm deps */
949 if (!dontfix && s->arch != ARCH_SRC && s->arch != ARCH_NOSRC && !pool_installable(pool, s))
951 POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "package %s [%d] is not installable\n", solvable2str(pool, s), (Id)(s - pool->solvables));
952 addrule(solv, -n, 0); /* uninstallable */
955 /*-----------------------------------------
956 * check requires of s
961 reqp = s->repo->idarraydata + s->requires;
962 while ((req = *reqp++) != 0) /* go throw all requires */
964 if (req == SOLVABLE_PREREQMARKER) /* skip the marker */
967 dp = pool_whatprovides(pool, req);
969 if (*dp == SYSTEMSOLVABLE) /* always installed */
974 /* the strategy here is to not insist on dependencies
975 * that are already broken. so if we find one provider
976 * that was already installed, we know that the
977 * dependency was not broken before so we enforce it */
978 for (i = 0; (p = dp[i]) != 0; i++) /* for all providers */
980 if (pool->solvables[p].repo == installed)
981 break; /* provider was installed */
983 if (!p) /* previously broken dependency */
985 POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "ignoring broken requires %s of installed package %s\n", dep2str(pool, req), solvable2str(pool, s));
992 /* nothing provides req! */
993 POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "package %s [%d] is not installable (%s)\n", solvable2str(pool, s), (Id)(s - pool->solvables), dep2str(pool, req));
994 addrule(solv, -n, 0); /* mark requestor as uninstallable */
998 IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION)
1000 POOL_DEBUG(SAT_DEBUG_RULE_CREATION," %s requires %s\n", solvable2str(pool, s), dep2str(pool, req));
1001 for (i = 0; dp[i]; i++)
1002 POOL_DEBUG(SAT_DEBUG_RULE_CREATION, " provided by %s\n", solvable2str(pool, pool->solvables + dp[i]));
1005 /* add 'requires' dependency */
1006 /* rule: (-requestor|provider1|provider2|...|providerN) */
1007 addrule(solv, -n, dp - pool->whatprovidesdata);
1009 /* descend the dependency tree */
1010 for (; *dp; dp++) /* loop through all providers */
1012 if (!MAPTST(m, *dp))
1013 queue_push(&q, *dp);
1016 } /* while, requirements of n */
1018 } /* if, requirements */
1020 /* that's all we check for src packages */
1021 if (s->arch == ARCH_SRC || s->arch == ARCH_NOSRC)
1024 /*-----------------------------------------
1025 * check conflicts of s
1030 conp = s->repo->idarraydata + s->conflicts;
1031 while ((con = *conp++) != 0)
1033 FOR_PROVIDES(p, pp, con)
1035 /* dontfix: dont care about conflicts with already installed packs */
1036 if (dontfix && pool->solvables[p].repo == installed)
1038 /* rule: -n|-p: either solvable _or_ provider of conflict */
1039 addrule(solv, -n, -p);
1044 /*-----------------------------------------
1045 * check obsoletes if not installed
1047 if (!installed || pool->solvables[n].repo != installed)
1048 { /* not installed */
1051 obsp = s->repo->idarraydata + s->obsoletes;
1052 while ((obs = *obsp++) != 0)
1054 FOR_PROVIDES(p, pp, obs)
1055 addrule(solv, -n, -p);
1058 FOR_PROVIDES(p, pp, s->name)
1060 if (s->name == pool->solvables[p].name)
1061 addrule(solv, -n, -p);
1065 /*-----------------------------------------
1066 * add recommends to the rule list
1070 recp = s->repo->idarraydata + s->recommends;
1071 while ((rec = *recp++) != 0)
1073 FOR_PROVIDES(p, pp, rec)
1080 sugp = s->repo->idarraydata + s->suggests;
1081 while ((sug = *sugp++) != 0)
1083 FOR_PROVIDES(p, pp, sug)
1090 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforsolvable end -----\n");
1094 addrpmrulesforweak(Solver *solv, Map *m)
1096 Pool *pool = solv->pool;
1101 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforweak -----\n");
1102 for (i = n = 1; n < pool->nsolvables; i++, n++)
1104 if (i == pool->nsolvables)
1108 s = pool->solvables + i;
1109 if (!pool_installable(pool, s))
1114 supp = s->repo->idarraydata + s->supplements;
1115 while ((sup = *supp++) != ID_NULL)
1116 if (dep_possible(solv, sup, m))
1119 if (!sup && s->freshens)
1121 supp = s->repo->idarraydata + s->freshens;
1122 while ((sup = *supp++) != ID_NULL)
1123 if (dep_possible(solv, sup, m))
1126 if (!sup && s->enhances)
1128 supp = s->repo->idarraydata + s->enhances;
1129 while ((sup = *supp++) != ID_NULL)
1130 if (dep_possible(solv, sup, m))
1135 addrpmrulesforsolvable(solv, s, m);
1138 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforweak end -----\n");
1142 addrpmrulesforupdaters(Solver *solv, Solvable *s, Map *m, int allowall)
1144 Pool *pool = solv->pool;
1149 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforupdaters -----\n");
1151 queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
1152 policy_findupdatepackages(solv, s, &qs, allowall);
1153 if (!MAPTST(m, s - pool->solvables)) /* add rule for s if not already done */
1154 addrpmrulesforsolvable(solv, s, m);
1155 for (i = 0; i < qs.count; i++)
1156 if (!MAPTST(m, qs.elements[i]))
1157 addrpmrulesforsolvable(solv, pool->solvables + qs.elements[i], m);
1160 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforupdaters -----\n");
1164 * add rule for update
1165 * (A|A1|A2|A3...) An = update candidates for A
1167 * s = (installed) solvable
1171 addupdaterule(Solver *solv, Solvable *s, int allowall)
1173 /* installed packages get a special upgrade allowed rule */
1174 Pool *pool = solv->pool;
1179 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addupdaterule -----\n");
1181 queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
1182 policy_findupdatepackages(solv, s, &qs, allowall);
1183 if (qs.count == 0) /* no updaters found */
1186 d = pool_queuetowhatprovides(pool, &qs); /* intern computed queue */
1188 addrule(solv, s - pool->solvables, d); /* allow update of s */
1189 POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addupdaterule end -----\n");
1193 /*-----------------------------------------------------------------*/
1200 * initial setup for all watches
1204 makewatches(Solver *solv)
1208 int nsolvables = solv->pool->nsolvables;
1210 xfree(solv->watches);
1211 /* lower half for removals, upper half for installs */
1212 solv->watches = (Id *)xcalloc(2 * nsolvables, sizeof(Id));
1214 /* do it reverse so rpm rules get triggered first */
1215 for (i = 1, r = solv->rules + solv->nrules - 1; i < solv->nrules; i++, r--)
1217 for (i = 1, r = solv->rules + 1; i < solv->nrules; i++, r++)
1220 if (!r->w1 /* rule is disabled */
1221 || !r->w2) /* rule is assertion */
1224 /* see addwatches(solv, r) */
1225 r->n1 = solv->watches[nsolvables + r->w1];
1226 solv->watches[nsolvables + r->w1] = r - solv->rules;
1228 r->n2 = solv->watches[nsolvables + r->w2];
1229 solv->watches[nsolvables + r->w2] = r - solv->rules;
1235 * add watches (for rule)
1239 addwatches(Solver *solv, Rule *r)
1241 int nsolvables = solv->pool->nsolvables;
1243 r->n1 = solv->watches[nsolvables + r->w1];
1244 solv->watches[nsolvables + r->w1] = r - solv->rules;
1246 r->n2 = solv->watches[nsolvables + r->w2];
1247 solv->watches[nsolvables + r->w2] = r - solv->rules;
1251 /*-----------------------------------------------------------------*/
1252 /* rule propagation */
1254 #define DECISIONMAP_TRUE(p) ((p) > 0 ? (decisionmap[p] > 0) : (decisionmap[-p] < 0))
1259 * propagate decision to all rules
1263 propagate(Solver *solv, int level)
1265 Pool *pool = solv->pool;
1270 Id *decisionmap = solv->decisionmap;
1271 Id *watches = solv->watches + pool->nsolvables;
1273 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "----- propagate -----\n");
1275 while (solv->propagate_index < solv->decisionq.count)
1277 /* negate because our watches trigger if literal goes FALSE */
1278 pkg = -solv->decisionq.elements[solv->propagate_index++];
1279 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1281 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "popagate for decision %d level %d\n", -pkg, level);
1282 printruleelement(solv, SAT_DEBUG_PROPAGATE, 0, -pkg);
1285 for (rp = watches + pkg; *rp; rp = nrp)
1287 r = solv->rules + *rp;
1289 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1291 POOL_DEBUG(SAT_DEBUG_PROPAGATE," watch triggered ");
1292 printrule(solv, SAT_DEBUG_PROPAGATE, r);
1305 /* if clause is TRUE, nothing to do */
1306 if (DECISIONMAP_TRUE(ow))
1311 /* not a binary clause, check if we need to move our watch */
1312 /* search for a literal that is not ow and not false */
1313 /* (true is also ok, in that case the rule is fulfilled) */
1314 if (r->p && r->p != ow && !DECISIONMAP_TRUE(-r->p))
1317 for (dp = pool->whatprovidesdata + r->d; (p = *dp++) != 0;)
1318 if (p != ow && !DECISIONMAP_TRUE(-p))
1322 /* p is free to watch, move watch to p */
1323 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1326 POOL_DEBUG(SAT_DEBUG_PROPAGATE, " -> move w%d to %s\n", (pkg == r->w1 ? 1 : 2), solvable2str(pool, pool->solvables + p));
1328 POOL_DEBUG(SAT_DEBUG_PROPAGATE," -> move w%d to !%s\n", (pkg == r->w1 ? 1 : 2), solvable2str(pool, pool->solvables - p));
1342 watches[p] = r - solv->rules;
1346 /* unit clause found, set other watch to TRUE */
1347 if (DECISIONMAP_TRUE(-ow))
1348 return r; /* eek, a conflict! */
1349 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1351 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "unit ");
1352 printrule(solv, SAT_DEBUG_PROPAGATE, r);
1355 decisionmap[ow] = level;
1357 decisionmap[-ow] = -level;
1358 queue_push(&solv->decisionq, ow);
1359 queue_push(&solv->decisionq_why, r - solv->rules);
1360 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1362 Solvable *s = pool->solvables + (ow > 0 ? ow : -ow);
1364 POOL_DEBUG(SAT_DEBUG_PROPAGATE, " -> decided to install %s\n", solvable2str(pool, s));
1366 POOL_DEBUG(SAT_DEBUG_PROPAGATE, " -> decided to conflict %s\n", solvable2str(pool, s));
1370 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "----- propagate end-----\n");
1372 return 0; /* all is well */
1376 /*-----------------------------------------------------------------*/
1385 analyze(Solver *solv, int level, Rule *c, int *pr, int *dr, int *why)
1387 Pool *pool = solv->pool;
1390 Map seen; /* global? */
1394 int learnt_why = solv->learnt_pool.count;
1395 Id *decisionmap = solv->decisionmap;
1399 POOL_DEBUG(SAT_DEBUG_ANALYZE, "ANALYZE at %d ----------------------\n", level);
1400 map_init(&seen, pool->nsolvables);
1401 idx = solv->decisionq.count;
1404 IF_POOLDEBUG (SAT_DEBUG_ANALYZE)
1405 printruleclass(solv, SAT_DEBUG_ANALYZE, c);
1406 queue_push(&solv->learnt_pool, c - solv->rules);
1407 dp = c->d ? pool->whatprovidesdata + c->d : 0;
1418 if (DECISIONMAP_TRUE(v)) /* the one true literal */
1420 vv = v > 0 ? v : -v;
1421 if (MAPTST(&seen, vv))
1423 l = solv->decisionmap[vv];
1430 for (j = 0; j < solv->decisionq.count; j++)
1431 if (solv->decisionq.elements[j] == v)
1433 if (j == solv->decisionq.count)
1435 queue_push(&rulq, -(j + 1));
1437 continue; /* initial setting */
1441 num++; /* need to do this one as well */
1453 v = solv->decisionq.elements[--idx];
1454 vv = v > 0 ? v : -v;
1455 if (MAPTST(&seen, vv))
1458 c = solv->rules + solv->decisionq_why.elements[idx];
1466 else if (r.count == 1 && r.elements[0] < 0)
1467 *dr = r.elements[0];
1469 *dr = pool_queuetowhatprovides(pool, &r);
1470 IF_POOLDEBUG (SAT_DEBUG_ANALYZE)
1472 POOL_DEBUG(SAT_DEBUG_ANALYZE, "learned rule for level %d (am %d)\n", rlevel, level);
1473 printruleelement(solv, SAT_DEBUG_ANALYZE, 0, -v);
1474 for (i = 0; i < r.count; i++)
1475 printruleelement(solv, SAT_DEBUG_ANALYZE, 0, r.elements[i]);
1478 /* push end marker on learnt reasons stack */
1479 queue_push(&solv->learnt_pool, 0);
1480 IF_POOLDEBUG (SAT_DEBUG_ANALYZE)
1482 for (i = learnt_why; solv->learnt_pool.elements[i]; i++)
1484 POOL_DEBUG(SAT_DEBUG_ANALYZE, "learnt_why ");
1485 printrule(solv, SAT_DEBUG_ANALYZE, solv->rules + solv->learnt_pool.elements[i]);
1496 * reset the solver decisions to right after the rpm rules.
1497 * called after rules have been enabled/disabled
1501 reset_solver(Solver *solv)
1503 Pool *pool = solv->pool;
1507 enabledisablelearntrules(solv);
1509 /* redo all direct rpm rule decisions */
1510 /* we break at the first decision with a why attached, this is
1511 * either a job/system rule assertion or a propagated decision */
1512 for (i = 0; i < solv->decisionq.count; i++)
1514 v = solv->decisionq.elements[i];
1515 solv->decisionmap[v > 0 ? v : -v] = 0;
1517 for (i = 0; i < solv->decisionq_why.count; i++)
1518 if (solv->decisionq_why.elements[i])
1522 v = solv->decisionq.elements[i];
1523 solv->decisionmap[v > 0 ? v : -v] = v > 0 ? 1 : -1;
1526 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "decisions done reduced from %d to %d\n", solv->decisionq.count, i);
1528 solv->decisionq_why.count = i;
1529 solv->decisionq.count = i;
1530 solv->recommends_index = -1;
1531 solv->propagate_index = 0;
1533 /* redo all job/system decisions */
1534 makeruledecisions(solv);
1535 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "decisions so far: %d\n", solv->decisionq.count);
1536 /* recreate watch chains */
1542 * analyze_unsolvable_rule
1546 analyze_unsolvable_rule(Solver *solv, Rule *r)
1548 Pool *pool = solv->pool;
1550 Id why = r - solv->rules;
1551 IF_POOLDEBUG (SAT_DEBUG_UNSOLVABLE)
1552 printruleclass(solv, SAT_DEBUG_UNSOLVABLE, r);
1553 if (solv->learntrules && why >= solv->learntrules)
1555 for (i = solv->learnt_why.elements[why - solv->learntrules]; solv->learnt_pool.elements[i]; i++)
1556 analyze_unsolvable_rule(solv, solv->rules + solv->learnt_pool.elements[i]);
1559 /* do not add rpm rules to problem */
1560 if (why < solv->jobrules)
1562 /* turn rule into problem */
1563 if (why >= solv->jobrules && why < solv->systemrules)
1564 why = -(solv->ruletojob.elements[why - solv->jobrules] + 1);
1565 /* return if problem already countains our rule */
1566 if (solv->problems.count)
1568 for (i = solv->problems.count - 1; i >= 0; i--)
1569 if (solv->problems.elements[i] == 0) /* end of last problem reached? */
1571 else if (solv->problems.elements[i] == why)
1574 queue_push(&solv->problems, why);
1579 * analyze_unsolvable
1581 * return: 1 - disabled some rules, try again
1586 analyze_unsolvable(Solver *solv, Rule *cr, int disablerules)
1588 Pool *pool = solv->pool;
1590 Map seen; /* global to speed things up? */
1593 Id *decisionmap = solv->decisionmap;
1594 int oldproblemcount;
1595 int oldlearntpoolcount;
1598 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "ANALYZE UNSOLVABLE ----------------------\n");
1599 oldproblemcount = solv->problems.count;
1600 oldlearntpoolcount = solv->learnt_pool.count;
1602 /* make room for proof index */
1603 /* must update it later, as analyze_unsolvable_rule would confuse
1604 * it with a rule index if we put the real value in already */
1605 queue_push(&solv->problems, 0);
1608 map_init(&seen, pool->nsolvables);
1609 queue_push(&solv->learnt_pool, r - solv->rules);
1610 analyze_unsolvable_rule(solv, r);
1611 dp = r->d ? pool->whatprovidesdata + r->d : 0;
1622 if (DECISIONMAP_TRUE(v)) /* the one true literal */
1624 vv = v > 0 ? v : -v;
1625 l = solv->decisionmap[vv];
1630 idx = solv->decisionq.count;
1633 v = solv->decisionq.elements[--idx];
1634 vv = v > 0 ? v : -v;
1635 if (!MAPTST(&seen, vv))
1637 why = solv->decisionq_why.elements[idx];
1640 /* level 1 and no why, must be an rpm assertion */
1641 IF_POOLDEBUG (SAT_DEBUG_UNSOLVABLE)
1643 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "RPM ");
1644 printruleelement(solv, SAT_DEBUG_UNSOLVABLE, 0, v);
1646 /* this is the only positive rpm assertion */
1647 if (v == SYSTEMSOLVABLE)
1651 queue_push(&solv->learnt_pool, v);
1654 r = solv->rules + why;
1655 queue_push(&solv->learnt_pool, why);
1656 analyze_unsolvable_rule(solv, r);
1657 dp = r->d ? pool->whatprovidesdata + r->d : 0;
1668 if (DECISIONMAP_TRUE(v)) /* the one true literal */
1670 vv = v > 0 ? v : -v;
1671 l = solv->decisionmap[vv];
1678 queue_push(&solv->problems, 0); /* mark end of this problem */
1681 if (solv->weakrules != solv->learntrules)
1683 for (i = oldproblemcount + 1; i < solv->problems.count - 1; i++)
1685 why = solv->problems.elements[i];
1686 if (why < solv->weakrules || why >= solv->learntrules)
1688 if (!lastweak || lastweak < why)
1694 /* disable last weak rule */
1695 solv->problems.count = oldproblemcount;
1696 solv->learnt_pool.count = oldlearntpoolcount;
1697 r = solv->rules + lastweak;
1698 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "disabling weak ");
1699 printrule(solv, SAT_DEBUG_UNSOLVABLE, r);
1700 disablerule(solv, r);
1706 queue_push(&solv->learnt_pool, 0);
1707 solv->problems.elements[oldproblemcount] = oldlearntpoolcount;
1711 for (i = oldproblemcount + 1; i < solv->problems.count - 1; i++)
1712 disableproblem(solv, solv->problems.elements[i]);
1716 POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "UNSOLVABLE\n");
1721 /*-----------------------------------------------------------------*/
1722 /* Decision revert */
1726 * revert decision at level
1730 revert(Solver *solv, int level)
1732 Pool *pool = solv->pool;
1734 while (solv->decisionq.count)
1736 v = solv->decisionq.elements[solv->decisionq.count - 1];
1737 vv = v > 0 ? v : -v;
1738 if (solv->decisionmap[vv] <= level && solv->decisionmap[vv] >= -level)
1740 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "reverting decision %d at %d\n", v, solv->decisionmap[vv]);
1741 solv->decisionmap[vv] = 0;
1742 solv->decisionq.count--;
1743 solv->decisionq_why.count--;
1744 solv->propagate_index = solv->decisionq.count;
1746 while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] <= -level)
1748 solv->branches.count--;
1749 while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] >= 0)
1750 solv->branches.count--;
1752 solv->recommends_index = -1;
1757 * watch2onhighest - put watch2 on literal with highest level
1761 watch2onhighest(Solver *solv, Rule *r)
1767 return; /* binary rule, both watches are set */
1768 dp = solv->pool->whatprovidesdata + r->d;
1769 while ((v = *dp++) != 0)
1771 l = solv->decisionmap[v < 0 ? -v : v];
1786 * add free decision to decision q, increase level
1787 * propagate decision, return if no conflict.
1788 * in conflict case, analyze conflict rule, add resulting
1789 * rule to learnt rule set, make decision from learnt
1790 * rule (always unit) and re-propagate.
1794 setpropagatelearn(Solver *solv, int level, Id decision, int disablerules)
1796 Pool *pool = solv->pool;
1805 solv->decisionmap[decision] = level;
1807 solv->decisionmap[-decision] = -level;
1808 queue_push(&solv->decisionq, decision);
1809 queue_push(&solv->decisionq_why, 0);
1813 r = propagate(solv, level);
1817 return analyze_unsolvable(solv, r, disablerules);
1818 POOL_DEBUG(SAT_DEBUG_ANALYZE, "conflict with rule #%d\n", (int)(r - solv->rules));
1819 l = analyze(solv, level, r, &p, &d, &why); /* learnt rule in p and d */
1820 if (l >= level || l <= 0)
1822 POOL_DEBUG(SAT_DEBUG_ANALYZE, "reverting decisions (level %d -> %d)\n", level, l);
1824 revert(solv, level);
1825 r = addrule(solv, p, d); /* p requires d */
1828 if (solv->learnt_why.count != (r - solv->rules) - solv->learntrules)
1830 queue_push(&solv->learnt_why, why);
1833 /* at least 2 literals, needs watches */
1834 watch2onhighest(solv, r);
1835 addwatches(solv, r);
1837 solv->decisionmap[p > 0 ? p : -p] = p > 0 ? level : -level;
1838 queue_push(&solv->decisionq, p);
1839 queue_push(&solv->decisionq_why, r - solv->rules);
1840 IF_POOLDEBUG (SAT_DEBUG_ANALYZE)
1842 POOL_DEBUG(SAT_DEBUG_ANALYZE, "decision: ");
1843 printruleelement(solv, SAT_DEBUG_ANALYZE, 0, p);
1844 POOL_DEBUG(SAT_DEBUG_ANALYZE, "new rule: ");
1845 printrule(solv, SAT_DEBUG_ANALYZE, r);
1853 * install best package from the queue. We add an extra package, inst, if
1854 * provided. See comment in weak install section.
1857 selectandinstall(Solver *solv, int level, Queue *dq, Id inst, int disablerules)
1859 Pool *pool = solv->pool;
1863 if (dq->count > 1 || inst)
1864 policy_filter_unwanted(solv, dq, inst, POLICY_MODE_CHOOSE);
1869 /* choose the supplemented one */
1870 for (i = 0; i < dq->count; i++)
1871 if (solver_is_supplementing(solv, pool->solvables + dq->elements[i]))
1875 for (i = 1; i < dq->count; i++)
1876 queue_push(&solv->branches, dq->elements[i]);
1877 queue_push(&solv->branches, -level);
1881 p = dq->elements[i];
1883 POOL_DEBUG(SAT_DEBUG_POLICY, "installing %s\n", solvable2str(pool, pool->solvables + p));
1885 return setpropagatelearn(solv, level, p, disablerules);
1889 /*-----------------------------------------------------------------*/
1890 /* Main solver interface */
1895 * create solver structure
1897 * pool: all available solvables
1898 * installed: installed Solvables
1901 * Upon solving, rules are created to flag the Solvables
1902 * of the 'installed' Repo as installed.
1906 solver_create(Pool *pool, Repo *installed)
1909 solv = (Solver *)xcalloc(1, sizeof(Solver));
1911 solv->installed = installed;
1913 queue_init(&solv->ruletojob);
1914 queue_init(&solv->decisionq);
1915 queue_init(&solv->decisionq_why);
1916 queue_init(&solv->problems);
1917 queue_init(&solv->suggestions);
1918 queue_init(&solv->learnt_why);
1919 queue_init(&solv->learnt_pool);
1920 queue_init(&solv->branches);
1922 map_init(&solv->recommendsmap, pool->nsolvables);
1923 map_init(&solv->suggestsmap, pool->nsolvables);
1924 map_init(&solv->noupdate, installed ? installed->end - installed->start : 0);
1925 solv->recommends_index = 0;
1927 solv->decisionmap = (Id *)xcalloc(pool->nsolvables, sizeof(Id));
1928 solv->rules = (Rule *)xmalloc((solv->nrules + (RULES_BLOCK + 1)) * sizeof(Rule));
1929 memset(solv->rules, 0, sizeof(Rule));
1941 solver_free(Solver *solv)
1943 queue_free(&solv->ruletojob);
1944 queue_free(&solv->decisionq);
1945 queue_free(&solv->decisionq_why);
1946 queue_free(&solv->learnt_why);
1947 queue_free(&solv->learnt_pool);
1948 queue_free(&solv->problems);
1949 queue_free(&solv->suggestions);
1950 queue_free(&solv->branches);
1952 map_free(&solv->recommendsmap);
1953 map_free(&solv->suggestsmap);
1954 map_free(&solv->noupdate);
1955 xfree(solv->decisionmap);
1957 xfree(solv->watches);
1958 xfree(solv->weaksystemrules);
1959 xfree(solv->obsoletes);
1960 xfree(solv->obsoletes_data);
1965 /*-------------------------------------------------------*/
1970 * all rules have been set up, now actually run the solver
1975 run_solver(Solver *solv, int disablerules, int doweak)
1983 Pool *pool = solv->pool;
1986 IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION)
1988 POOL_DEBUG (SAT_DEBUG_RULE_CREATION, "number of rules: %d\n", solv->nrules);
1989 for (i = 0; i < solv->nrules; i++)
1990 printrule(solv, SAT_DEBUG_RULE_CREATION, solv->rules + i);
1993 /* create watches chains */
1996 POOL_DEBUG(SAT_DEBUG_STATS, "initial decisions: %d\n", solv->decisionq.count);
1998 IF_POOLDEBUG (SAT_DEBUG_SCHUBI)
1999 printdecisions(solv);
2001 /* start SAT algorithm */
2003 systemlevel = level + 1;
2004 POOL_DEBUG(SAT_DEBUG_STATS, "solving...\n");
2015 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "propagating (propagate_index: %d; size decisionq: %d)...\n", solv->propagate_index, solv->decisionq.count);
2016 if ((r = propagate(solv, level)) != 0)
2018 if (analyze_unsolvable(solv, r, disablerules))
2026 * installed packages
2029 if (level < systemlevel && solv->installed && solv->installed->nsolvables)
2031 if (!solv->updatesystem)
2033 /* try to keep as many packages as possible */
2034 POOL_DEBUG(SAT_DEBUG_STATS, "installing system packages\n");
2035 for (i = solv->installed->start, n = 0; ; i++)
2037 if (n == solv->installed->nsolvables)
2039 if (i == solv->installed->end)
2040 i = solv->installed->start;
2041 s = pool->solvables + i;
2042 if (s->repo != solv->installed)
2045 if (solv->decisionmap[i] != 0)
2047 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "keeping %s\n", solvable2str(pool, s));
2049 level = setpropagatelearn(solv, level, i, disablerules);
2055 if (level <= olevel)
2059 if (solv->weaksystemrules)
2061 POOL_DEBUG(SAT_DEBUG_STATS, "installing weak system packages\n");
2062 for (i = solv->installed->start; i < solv->installed->end; i++)
2064 if (pool->solvables[i].repo != solv->installed)
2066 if (solv->decisionmap[i] > 0 || (solv->decisionmap[i] < 0 && solv->weaksystemrules[i - solv->installed->start] == 0))
2068 /* noupdate is set if a job is erasing the installed solvable or installing a specific version */
2069 if (MAPTST(&solv->noupdate, i - solv->installed->start))
2072 if (solv->weaksystemrules[i - solv->installed->start])
2074 dp = pool->whatprovidesdata + solv->weaksystemrules[i - solv->installed->start];
2075 while ((p = *dp++) != 0)
2077 if (solv->decisionmap[p] > 0)
2079 if (solv->decisionmap[p] == 0)
2083 continue; /* update package already installed */
2085 if (!dq.count && solv->decisionmap[i] != 0)
2088 /* FIXME: i is handled a bit different because we do not want
2089 * to have it pruned just because it is not recommened.
2090 * we should not prune installed packages instead */
2091 level = selectandinstall(solv, level, &dq, (solv->decisionmap[i] ? 0 : i), disablerules);
2097 if (level <= olevel)
2100 if (i < solv->installed->end)
2103 systemlevel = level;
2110 POOL_DEBUG(SAT_DEBUG_STATS, "deciding unresolved rules\n");
2111 for (i = 1, n = 1; ; i++, n++)
2113 if (n == solv->nrules)
2115 if (i == solv->nrules)
2117 r = solv->rules + i;
2123 /* binary or unary rule */
2124 /* need two positive undecided literals */
2125 if (r->p < 0 || r->w2 <= 0)
2127 if (solv->decisionmap[r->p] || solv->decisionmap[r->w2])
2129 queue_push(&dq, r->p);
2130 queue_push(&dq, r->w2);
2135 * all negative literals are installed
2136 * no positive literal is installed
2137 * i.e. the rule is not fulfilled and we
2138 * just need to decide on the positive literals
2142 if (solv->decisionmap[-r->p] <= 0)
2147 if (solv->decisionmap[r->p] > 0)
2149 if (solv->decisionmap[r->p] == 0)
2150 queue_push(&dq, r->p);
2152 dp = pool->whatprovidesdata + r->d;
2153 while ((p = *dp++) != 0)
2157 if (solv->decisionmap[-p] <= 0)
2162 if (solv->decisionmap[p] > 0)
2164 if (solv->decisionmap[p] == 0)
2173 /* cannot happen as this means that
2174 * the rule is unit */
2175 printrule(solv, SAT_FATAL, r);
2178 IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
2180 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "unfulfilled ");
2181 printrule(solv, SAT_DEBUG_PROPAGATE, r);
2185 level = selectandinstall(solv, level, &dq, 0, disablerules);
2191 if (level < systemlevel)
2194 } /* for(), decide */
2196 if (n != solv->nrules) /* continue if level < systemlevel */
2199 if (doweak && !solv->problems.count)
2203 POOL_DEBUG(SAT_DEBUG_STATS, "installing recommended packages\n");
2206 for (i = 0; i < solv->decisionq.count; i++)
2208 p = solv->decisionq.elements[i];
2209 if (p > 0 && pool->solvables[p].repo == solv->installed)
2210 solv->decisionmap[p] = -solv->decisionmap[p];
2214 for (i = 1; i < pool->nsolvables; i++)
2216 if (solv->decisionmap[i] < 0)
2218 if (solv->decisionmap[i] > 0)
2220 Id *recp, rec, *pp, p;
2221 s = pool->solvables + i;
2222 /* installed, check for recommends */
2223 /* XXX need to special case AND ? */
2226 recp = s->repo->idarraydata + s->recommends;
2227 while ((rec = *recp++) != 0)
2230 FOR_PROVIDES(p, pp, rec)
2232 if (solv->decisionmap[p] > 0)
2237 else if (solv->decisionmap[p] == 0)
2239 queue_pushunique(&dq, p);
2247 s = pool->solvables + i;
2248 if (!s->supplements && !s->freshens)
2250 if (!pool_installable(pool, s))
2252 if (solver_is_supplementing(solv, s))
2253 queue_pushunique(&dq, i);
2258 for (i = 0; i < solv->decisionq.count; i++)
2260 p = solv->decisionq.elements[i];
2261 if (p > 0 && pool->solvables[p].repo == solv->installed)
2262 solv->decisionmap[p] = -solv->decisionmap[p];
2268 policy_filter_unwanted(solv, &dq, 0, POLICY_MODE_RECOMMEND);
2270 POOL_DEBUG(SAT_DEBUG_STATS, "installing recommended %s\n", solvable2str(pool, pool->solvables + p));
2271 level = setpropagatelearn(solv, level, p, 0);
2276 if (solv->solution_callback)
2278 solv->solution_callback(solv, solv->solution_callback_data);
2279 if (solv->branches.count)
2281 int i = solv->branches.count - 1;
2282 int l = -solv->branches.elements[i];
2284 if (solv->branches.elements[i - 1] < 0)
2286 p = solv->branches.elements[i];
2287 POOL_DEBUG(SAT_DEBUG_STATS, "branching with %s\n", solvable2str(pool, pool->solvables + p));
2289 for (j = i + 1; j < solv->branches.count; j++)
2290 queue_push(&dq, solv->branches.elements[j]);
2291 solv->branches.count = i;
2293 revert(solv, level);
2295 for (j = 0; j < dq.count; j++)
2296 queue_push(&solv->branches, dq.elements[j]);
2298 level = setpropagatelearn(solv, level, p, disablerules);
2306 /* all branches done, we're finally finished */
2310 /* minimization step */
2311 if (solv->branches.count)
2313 int l = 0, lasti = -1, lastl = -1;
2315 for (i = solv->branches.count - 1; i >= 0; i--)
2317 p = solv->branches.elements[i];
2320 else if (p > 0 && solv->decisionmap[p] > l + 1)
2328 /* kill old solvable so that we do not loop */
2329 p = solv->branches.elements[lasti];
2330 solv->branches.elements[lasti] = 0;
2331 POOL_DEBUG(SAT_DEBUG_STATS, "minimizing %d -> %d with %s\n", solv->decisionmap[p], l, solvable2str(pool, pool->solvables + p));
2334 revert(solv, level);
2336 level = setpropagatelearn(solv, level, p, disablerules);
2353 * at this point, all rules that led to conflicts are disabled.
2354 * we re-enable all rules of a problem set but rule "sug", then
2355 * continue to disable more rules until there as again a solution.
2358 /* FIXME: think about conflicting assertions */
2361 refine_suggestion(Solver *solv, Queue *job, Id *problem, Id sug, Queue *refined)
2363 Pool *pool = solv->pool;
2370 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
2372 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "refine_suggestion start\n");
2373 for (i = 0; problem[i]; i++)
2375 if (problem[i] == sug)
2376 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "=> ");
2377 printproblem(solv, problem[i]);
2380 queue_init(&disabled);
2381 queue_empty(refined);
2382 queue_push(refined, sug);
2384 /* re-enable all problem rules with the exception of "sug" */
2388 for (i = 0; problem[i]; i++)
2389 if (problem[i] != sug)
2390 enableproblem(solv, problem[i]);
2393 disableupdaterules(solv, job, -(sug + 1));
2397 /* re-enable as many weak rules as possible */
2398 for (i = solv->weakrules; i < solv->learntrules; i++)
2400 r = solv->rules + i;
2402 enablerule(solv, r);
2405 queue_empty(&solv->problems);
2406 revert(solv, 1); /* XXX move to reset_solver? */
2409 run_solver(solv, 0, 0);
2410 if (!solv->problems.count)
2412 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "no more problems!\n");
2413 IF_POOLDEBUG (SAT_DEBUG_SCHUBI)
2414 printdecisions(solv);
2415 break; /* great, no more problems */
2417 disabledcnt = disabled.count;
2418 /* skip over proof index */
2419 for (i = 1; i < solv->problems.count - 1; i++)
2421 /* ignore solutions in refined */
2422 v = solv->problems.elements[i];
2424 break; /* end of problem reached */
2425 for (j = 0; problem[j]; j++)
2426 if (problem[j] != sug && problem[j] == v)
2430 queue_push(&disabled, v);
2432 if (disabled.count == disabledcnt)
2434 /* no solution found, this was an invalid suggestion! */
2435 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "no solution found!\n");
2439 if (disabled.count == disabledcnt + 1)
2441 /* just one suggestion, add it to refined list */
2442 v = disabled.elements[disabledcnt];
2443 queue_push(refined, v);
2444 disableproblem(solv, v);
2446 disableupdaterules(solv, job, -(v + 1));
2450 /* more than one solution, disable all */
2451 /* do not push anything on refine list */
2452 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
2454 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "more than one solution found:\n");
2455 for (i = disabledcnt; i < disabled.count; i++)
2456 printproblem(solv, disabled.elements[i]);
2458 for (i = disabledcnt; i < disabled.count; i++)
2459 disableproblem(solv, disabled.elements[i]);
2462 /* all done, get us back into the same state as before */
2463 /* enable refined rules again */
2464 for (i = 0; i < disabled.count; i++)
2465 enableproblem(solv, disabled.elements[i]);
2466 /* disable problem rules again */
2467 for (i = 0; problem[i]; i++)
2468 disableproblem(solv, problem[i]);
2469 disableupdaterules(solv, job, -1);
2470 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "refine_suggestion end\n");
2474 problems_to_solutions(Solver *solv, Queue *job)
2476 Pool *pool = solv->pool;
2484 if (!solv->problems.count)
2486 queue_clone(&problems, &solv->problems);
2487 queue_init(&solution);
2488 queue_init(&solutions);
2489 /* copy over proof index */
2490 queue_push(&solutions, problems.elements[0]);
2491 problem = problems.elements + 1;
2492 for (i = 1; i < problems.count; i++)
2494 Id v = problems.elements[i];
2497 /* mark end of this problem */
2498 queue_push(&solutions, 0);
2499 queue_push(&solutions, 0);
2500 if (i + 1 == problems.count)
2502 /* copy over proof of next problem */
2503 queue_push(&solutions, problems.elements[i + 1]);
2505 problem = problems.elements + i + 1;
2508 refine_suggestion(solv, job, problem, v, &solution);
2509 if (!solution.count)
2510 continue; /* this solution didn't work out */
2512 for (j = 0; j < solution.count; j++)
2514 why = solution.elements[j];
2516 printproblem(solv, why);
2520 queue_push(&solutions, 0);
2521 queue_push(&solutions, -why);
2523 else if (why >= solv->systemrules && why < solv->weakrules)
2526 p = solv->installed->start + (why - solv->systemrules);
2527 if (solv->weaksystemrules && solv->weaksystemrules[why - solv->systemrules])
2529 Id *dp = pool->whatprovidesdata + solv->weaksystemrules[why - solv->systemrules];
2532 if (*dp >= solv->installed->start && *dp < solv->installed->start + solv->installed->nsolvables)
2534 if (solv->decisionmap[*dp] > 0)
2541 queue_push(&solutions, p);
2542 queue_push(&solutions, rp);
2547 /* mark end of this solution */
2548 queue_push(&solutions, 0);
2549 queue_push(&solutions, 0);
2551 queue_free(&solution);
2552 queue_free(&problems);
2553 /* copy queue over to solutions */
2554 queue_free(&solv->problems);
2555 queue_clone(&solv->problems, &solutions);
2557 /* bring solver back into problem state */
2558 revert(solv, 1); /* XXX move to reset_solver? */
2561 if (solv->problems.count != solutions.count)
2563 queue_free(&solutions);
2567 solver_next_problem(Solver *solv, Id problem)
2571 return solv->problems.count ? 1 : 0;
2572 pp = solv->problems.elements + problem;
2573 while (pp[0] || pp[1])
2577 while (pp[0] || pp[1])
2582 problem = pp - solv->problems.elements;
2583 if (problem >= solv->problems.count)
2589 solver_next_solution(Solver *solv, Id problem, Id solution)
2595 pp = solv->problems.elements + solution;
2596 return pp[0] || pp[1] ? solution : 0;
2598 pp = solv->problems.elements + solution;
2599 while (pp[0] || pp[1])
2602 solution = pp - solv->problems.elements;
2603 return pp[0] || pp[1] ? solution : 0;
2607 solver_next_solutionelement(Solver *solv, Id problem, Id solution, Id element, Id *p, Id *rp)
2610 element = element ? element + 2 : solution;
2611 pp = solv->problems.elements + element;
2612 if (!(pp[0] || pp[1]))
2627 printdecisions(Solver *solv)
2629 Pool *pool = solv->pool;
2630 Repo *installed = solv->installed;
2631 Id p, *obsoletesmap;
2635 obsoletesmap = (Id *)xcalloc(pool->nsolvables, sizeof(Id));
2638 for (i = 0; i < solv->decisionq.count; i++)
2642 n = solv->decisionq.elements[i];
2645 if (n == SYSTEMSOLVABLE)
2647 s = pool->solvables + n;
2648 if (s->repo == installed) /* obsoletes don't count for already installed packages */
2650 FOR_PROVIDES(p, pp, s->name)
2651 if (s->name == pool->solvables[p].name)
2653 if (pool->solvables[p].repo == installed && !obsoletesmap[p])
2655 obsoletesmap[p] = n;
2660 for (i = 0; i < solv->decisionq.count; i++)
2665 n = solv->decisionq.elements[i];
2668 if (n == SYSTEMSOLVABLE)
2670 s = pool->solvables + n;
2671 if (s->repo == installed) /* obsoletes don't count for already installed packages */
2675 obsp = s->repo->idarraydata + s->obsoletes;
2676 while ((obs = *obsp++) != 0)
2677 FOR_PROVIDES(p, pp, obs)
2679 if (pool->solvables[p].repo == installed && !obsoletesmap[p])
2681 obsoletesmap[p] = n;
2688 /* print solvables to be erased */
2692 FOR_REPO_SOLVABLES(installed, p, s)
2694 if (solv->decisionmap[p] >= 0)
2696 if (obsoletesmap[p])
2698 POOL_DEBUG(SAT_DEBUG_RESULT, "erase %s\n", solvable2str(pool, s));
2702 /* print solvables to be installed */
2704 for (i = 0; i < solv->decisionq.count; i++)
2707 p = solv->decisionq.elements[i];
2710 if (p == SYSTEMSOLVABLE)
2712 s = pool->solvables + p;
2713 if (installed && s->repo == installed)
2716 if (!obsoletesmap[p])
2718 POOL_DEBUG(SAT_DEBUG_RESULT, "install %s", solvable2str(pool, s));
2722 POOL_DEBUG(SAT_DEBUG_RESULT, "update %s", solvable2str(pool, s));
2723 POOL_DEBUG(SAT_DEBUG_RESULT, " (obsoletes");
2724 for (j = installed->start; j < installed->end; j++)
2725 if (obsoletesmap[j] == p)
2726 POOL_DEBUG(SAT_DEBUG_RESULT, " %s", solvable2str(pool, pool->solvables + j));
2727 POOL_DEBUG(SAT_DEBUG_RESULT, ")");
2729 POOL_DEBUG(SAT_DEBUG_RESULT, "\n");
2732 xfree(obsoletesmap);
2734 if (solv->suggestions.count)
2736 POOL_DEBUG(SAT_DEBUG_RESULT, "\nsuggested packages:\n");
2737 for (i = 0; i < solv->suggestions.count; i++)
2739 s = pool->solvables + solv->suggestions.elements[i];
2740 POOL_DEBUG(SAT_DEBUG_RESULT, "- %s\n", solvable2str(pool, s));
2746 printconflicts(Solver *solv, Solvable *s, Id pc)
2748 Pool *pool = solv->pool;
2749 Solvable *sc = pool->solvables + pc;
2750 Id p, *pp, con, *conp, obs, *obsp;
2755 conp = s->repo->idarraydata + s->conflicts;
2756 while ((con = *conp++) != 0)
2758 FOR_PROVIDES(p, pp, con)
2762 POOL_DEBUG(SAT_DEBUG_RESULT, "packags %s conflicts with %s, which is provided by %s\n", solvable2str(pool, s), dep2str(pool, con), solvable2str(pool, sc));
2767 if (s->obsoletes && (!solv->installed || s->repo != solv->installed))
2769 obsp = s->repo->idarraydata + s->obsoletes;
2770 while ((obs = *obsp++) != 0)
2772 FOR_PROVIDES(p, pp, obs)
2776 POOL_DEBUG(SAT_DEBUG_RESULT, "packags %s obsolets %s, which is provided by %s\n", solvable2str(pool, s), dep2str(pool, obs), solvable2str(pool, sc));
2785 printprobleminfo(Solver *solv, Queue *job, Id problem)
2787 Pool *pool = solv->pool;
2791 Id idx = solv->problems.elements[problem - 1];
2793 rn = solv->learnt_pool.elements[idx];
2796 p = rn; /* fake a negative assertion rule */
2801 r = solv->rules + rn;
2805 if (!r || r->w2 == 0)
2811 if (p == -SYSTEMSOLVABLE)
2815 /* we tried to deinstall the system solvable. must be a job. */
2816 if (rn < solv->jobrules || rn >= solv->systemrules)
2818 ji = solv->ruletojob.elements[rn - solv->jobrules];
2819 what = job->elements[ji + 1];
2820 switch (job->elements[ji])
2822 case SOLVER_INSTALL_SOLVABLE_NAME:
2823 POOL_DEBUG(SAT_DEBUG_RESULT, "no solvable exists with name %s\n", dep2str(pool, what));
2825 case SOLVER_INSTALL_SOLVABLE_PROVIDES:
2826 POOL_DEBUG(SAT_DEBUG_RESULT, "no solvable provides %s\n", dep2str(pool, what));
2829 pool_debug(pool, SAT_FATAL, "unknown job\n");
2834 if (p > 0 && solv->learnt_pool.elements[idx + 1] == -p)
2836 /* we conflicted with a direct rpm assertion */
2837 /* print other rule */
2841 if (rn >= solv->jobrules)
2843 POOL_DEBUG(SAT_DEBUG_RESULT, "some job/system/learnt rule\n");
2844 printrule(solv, SAT_DEBUG_RESULT, r);
2849 /* negative assertion, i.e. package is not installable */
2850 s = pool->solvables + (-p);
2853 reqp = s->repo->idarraydata + s->requires;
2854 while ((req = *reqp++) != 0)
2856 if (req == SOLVABLE_PREREQMARKER)
2858 dp = pool_whatprovides(pool, req);
2861 POOL_DEBUG(SAT_DEBUG_RESULT, "package %s requires %s, but no package provides it\n", solvable2str(pool, s), dep2str(pool, req));
2866 POOL_DEBUG(SAT_DEBUG_RESULT, "package %s is not installable\n", solvable2str(pool, s));
2870 if (rn >= solv->learntrules)
2872 /* learnt rule, ignore for now */
2873 POOL_DEBUG(SAT_DEBUG_RESULT, "some learnt rule...\n");
2874 printrule(solv, SAT_DEBUG_RESULT, r);
2877 if (rn >= solv->systemrules)
2879 /* system rule, ignore for now */
2880 POOL_DEBUG(SAT_DEBUG_RESULT, "some system rule...\n");
2881 printrule(solv, SAT_DEBUG_RESULT, r);
2884 if (rn >= solv->jobrules)
2886 /* job rule, ignore for now */
2887 POOL_DEBUG(SAT_DEBUG_RESULT, "some job rule...\n");
2888 printrule(solv, SAT_DEBUG_RESULT, r);
2891 /* only rpm rules left... */
2896 if (d == 0 && r->w2 < 0)
2900 sp = pool->solvables + (-p);
2901 sd = pool->solvables + (-d);
2902 if (sp->name == sd->name)
2904 POOL_DEBUG(SAT_DEBUG_RESULT, "cannot install both %s and %s\n", solvable2str(pool, sp), solvable2str(pool, sd));
2908 printconflicts(solv, pool->solvables + (-p), -d);
2909 printconflicts(solv, pool->solvables + (-d), -p);
2914 /* find requires of p that corresponds with our rule */
2916 s = pool->solvables + (-p);
2917 reqp = s->repo->idarraydata + s->requires;
2918 while ((req = *reqp++) != 0)
2920 if (req == SOLVABLE_PREREQMARKER)
2922 dp = pool_whatprovides(pool, req);
2925 if (*dp == r->w2 && dp[1] == 0)
2928 else if (dp - pool->whatprovidesdata == d)
2933 pool_debug(pool, SAT_FATAL, "req not found\n");
2936 POOL_DEBUG(SAT_DEBUG_RESULT, "package %s requires %s, but none of its providers can be installed\n", solvable2str(pool, s), dep2str(pool, req));
2941 printsolutions(Solver *solv, Queue *job)
2943 Pool *pool = solv->pool;
2946 Id problem, solution, element;
2949 POOL_DEBUG(SAT_DEBUG_RESULT, "Encountered problems! Here are the solutions:\n\n");
2952 while ((problem = solver_next_problem(solv, problem)) != 0)
2954 POOL_DEBUG(SAT_DEBUG_RESULT, "Problem %d:\n", pcnt++);
2955 POOL_DEBUG(SAT_DEBUG_RESULT, "====================================\n");
2956 printprobleminfo(solv, job, problem);
2957 POOL_DEBUG(SAT_DEBUG_RESULT, "\n");
2959 while ((solution = solver_next_solution(solv, problem, solution)) != 0)
2962 while ((element = solver_next_solutionelement(solv, problem, solution, element, &p, &rp)) != 0)
2966 /* job, rp is index into job queue */
2967 what = job->elements[rp];
2968 switch (job->elements[rp - 1])
2970 case SOLVER_INSTALL_SOLVABLE:
2971 s = pool->solvables + what;
2972 if (solv->installed && s->repo == solv->installed)
2973 POOL_DEBUG(SAT_DEBUG_RESULT, "- do not keep %s installed\n", solvable2str(pool, s));
2975 POOL_DEBUG(SAT_DEBUG_RESULT, "- do not install %s\n", solvable2str(pool, s));
2977 case SOLVER_ERASE_SOLVABLE:
2978 s = pool->solvables + what;
2979 if (solv->installed && s->repo == solv->installed)
2980 POOL_DEBUG(SAT_DEBUG_RESULT, "- do not deinstall %s\n", solvable2str(pool, s));
2982 POOL_DEBUG(SAT_DEBUG_RESULT, "- do not forbid installation of %s\n", solvable2str(pool, s));
2984 case SOLVER_INSTALL_SOLVABLE_NAME:
2985 POOL_DEBUG(SAT_DEBUG_RESULT, "- do not install %s\n", id2str(pool, what));
2987 case SOLVER_ERASE_SOLVABLE_NAME:
2988 POOL_DEBUG(SAT_DEBUG_RESULT, "- do not deinstall %s\n", id2str(pool, what));
2990 case SOLVER_INSTALL_SOLVABLE_PROVIDES:
2991 POOL_DEBUG(SAT_DEBUG_RESULT, "- do not install a solvable providing %s\n", dep2str(pool, what));
2993 case SOLVER_ERASE_SOLVABLE_PROVIDES:
2994 POOL_DEBUG(SAT_DEBUG_RESULT, "- do not deinstall all solvables providing %s\n", dep2str(pool, what));
2996 case SOLVER_INSTALL_SOLVABLE_UPDATE:
2997 s = pool->solvables + what;
2998 POOL_DEBUG(SAT_DEBUG_RESULT, "- do not install most recent version of %s\n", solvable2str(pool, s));
3001 POOL_DEBUG(SAT_DEBUG_RESULT, "- do something different\n");
3007 /* policy, replace p with rp */
3008 s = pool->solvables + p;
3009 sd = rp ? pool->solvables + rp : 0;
3013 if (!solv->allowdowngrade && evrcmp(pool, s->evr, sd->evr) > 0)
3015 POOL_DEBUG(SAT_DEBUG_RESULT, "- allow downgrade of %s to %s\n", solvable2str(pool, s), solvable2str(pool, sd));
3018 if (!solv->allowarchchange && s->name == sd->name && s->arch != sd->arch && policy_illegal_archchange(pool, s, sd))
3020 POOL_DEBUG(SAT_DEBUG_RESULT, "- allow architecture change of %s to %s\n", solvable2str(pool, s), solvable2str(pool, sd));
3023 if (!solv->allowvendorchange && s->name == sd->name && s->vendor != sd->vendor && policy_illegal_vendorchange(pool, s, sd))
3026 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));
3028 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));
3032 POOL_DEBUG(SAT_DEBUG_RESULT, "- allow replacement of %s with %s\n", solvable2str(pool, s), solvable2str(pool, sd));
3036 POOL_DEBUG(SAT_DEBUG_RESULT, "- allow deinstallation of %s\n", solvable2str(pool, s));
3041 POOL_DEBUG(SAT_DEBUG_RESULT, "\n");
3047 /* for each installed solvable find which packages with *different* names
3048 * obsolete the solvable.
3049 * this index is used in policy_findupdatepackages if noupdateprovide is set.
3053 create_obsolete_index(Solver *solv)
3055 Pool *pool = solv->pool;
3057 Repo *installed = solv->installed;
3058 Id p, *pp, obs, *obsp, *obsoletes, *obsoletes_data;
3061 if (!installed || !installed->nsolvables)
3063 /* create reverse obsoletes map for installed solvables */
3064 solv->obsoletes = obsoletes = xcalloc(installed->end - installed->start, sizeof(Id));
3065 for (i = 1; i < pool->nsolvables; i++)
3067 s = pool->solvables + i;
3068 if (s->repo == installed)
3072 if (!pool_installable(pool, s))
3074 obsp = s->repo->idarraydata + s->obsoletes;
3075 while ((obs = *obsp++) != 0)
3076 FOR_PROVIDES(p, pp, obs)
3078 if (pool->solvables[p].repo != installed)
3080 if (pool->solvables[p].name == s->name)
3082 obsoletes[p - installed->start]++;
3086 for (i = 0; i < installed->nsolvables; i++)
3089 n += obsoletes[i] + 1;
3092 solv->obsoletes_data = obsoletes_data = xcalloc(n + 1, sizeof(Id));
3093 POOL_DEBUG(SAT_DEBUG_STATS, "obsoletes data: %d entries\n", n + 1);
3094 for (i = pool->nsolvables - 1; i > 0; i--)
3096 s = pool->solvables + i;
3097 if (s->repo == installed)
3101 if (!pool_installable(pool, s))
3103 obsp = s->repo->idarraydata + s->obsoletes;
3104 while ((obs = *obsp++) != 0)
3105 FOR_PROVIDES(p, pp, obs)
3107 if (pool->solvables[p].repo != installed)
3109 if (pool->solvables[p].name == s->name)
3111 p -= installed->start;
3112 if (obsoletes_data[obsoletes[p]] != i)
3113 obsoletes_data[--obsoletes[p]] = i;
3119 /*-----------------------------------------------------------------*/
3129 solver_solve(Solver *solv, Queue *job)
3131 Pool *pool = solv->pool;
3132 Repo *installed = solv->installed;
3135 Map addedmap; /* '1' == have rule for solvable */
3136 Id how, what, p, *pp, d;
3140 /* create obsolete index if needed */
3141 if (solv->noupdateprovide)
3142 create_obsolete_index(solv);
3145 * create basic rule set of all involved packages
3146 * use addedmap bitmap to make sure we don't create rules twice
3150 map_init(&addedmap, pool->nsolvables);
3154 * always install our system solvable
3156 MAPSET(&addedmap, SYSTEMSOLVABLE);
3157 queue_push(&solv->decisionq, SYSTEMSOLVABLE);
3158 queue_push(&solv->decisionq_why, 0);
3159 solv->decisionmap[SYSTEMSOLVABLE] = 1;
3162 * create rules for all package that could be involved with the solving
3163 * so called: rpm rules
3168 oldnrules = solv->nrules;
3169 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for installed solvables ***\n");
3170 FOR_REPO_SOLVABLES(installed, p, s)
3171 addrpmrulesforsolvable(solv, s, &addedmap);
3172 POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for installed solvables\n", solv->nrules - oldnrules);
3173 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for updaters of installed solvables ***\n");
3174 oldnrules = solv->nrules;
3175 FOR_REPO_SOLVABLES(installed, p, s)
3176 addrpmrulesforupdaters(solv, s, &addedmap, 1);
3177 POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for updaters of installed solvables\n", solv->nrules - oldnrules);
3180 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for packages involved with a job ***\n");
3181 oldnrules = solv->nrules;
3182 for (i = 0; i < job->count; i += 2)
3184 how = job->elements[i];
3185 what = job->elements[i + 1];
3189 case SOLVER_INSTALL_SOLVABLE:
3190 addrpmrulesforsolvable(solv, pool->solvables + what, &addedmap);
3192 case SOLVER_INSTALL_SOLVABLE_NAME:
3193 case SOLVER_INSTALL_SOLVABLE_PROVIDES:
3194 FOR_PROVIDES(p, pp, what)
3196 /* if by name, ensure that the name matches */
3197 if (how == SOLVER_INSTALL_SOLVABLE_NAME && pool->solvables[p].name != what)
3199 addrpmrulesforsolvable(solv, pool->solvables + p, &addedmap);
3202 case SOLVER_INSTALL_SOLVABLE_UPDATE:
3203 /* dont allow downgrade */
3204 addrpmrulesforupdaters(solv, pool->solvables + what, &addedmap, 0);
3208 POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for packages involved in a job\n", solv->nrules - oldnrules);
3210 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for recommended/suggested packages ***\n");
3212 oldnrules = solv->nrules;
3213 addrpmrulesforweak(solv, &addedmap);
3214 POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules because of weak dependencies\n", solv->nrules - oldnrules);
3216 IF_POOLDEBUG (SAT_DEBUG_STATS)
3218 int possible = 0, installable = 0;
3219 for (i = 1; i < pool->nsolvables; i++)
3221 if (pool_installable(pool, pool->solvables + i))
3223 if (MAPTST(&addedmap, i))
3226 POOL_DEBUG(SAT_DEBUG_STATS, "%d of %d installable solvables considered for solving\n", possible, installable);
3230 * first pass done, we now have all the rpm rules we need.
3231 * unify existing rules before going over all job rules and
3233 * at this point the system is always solvable,
3234 * as an empty system (remove all packages) is a valid solution
3237 unifyrules(solv); /* remove duplicate rpm rules */
3239 POOL_DEBUG(SAT_DEBUG_STATS, "decisions so far: %d\n", solv->decisionq.count);
3240 IF_POOLDEBUG (SAT_DEBUG_SCHUBI)
3241 printdecisions (solv);
3244 * now add all job rules
3247 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** Add JOB rules ***\n");
3249 solv->jobrules = solv->nrules;
3251 for (i = 0; i < job->count; i += 2)
3253 int oldnrules = solv->nrules;
3255 how = job->elements[i];
3256 what = job->elements[i + 1];
3259 case SOLVER_INSTALL_SOLVABLE: /* install specific solvable */
3260 s = pool->solvables + what;
3261 POOL_DEBUG(SAT_DEBUG_JOB, "job: install solvable %s\n", solvable2str(pool, s));
3262 addrule(solv, what, 0); /* install by Id */
3263 queue_push(&solv->ruletojob, i);
3265 case SOLVER_ERASE_SOLVABLE:
3266 s = pool->solvables + what;
3267 POOL_DEBUG(SAT_DEBUG_JOB, "job: erase solvable %s\n", solvable2str(pool, s));
3268 addrule(solv, -what, 0); /* remove by Id */
3269 queue_push(&solv->ruletojob, i);
3271 case SOLVER_INSTALL_SOLVABLE_NAME: /* install by capability */
3272 case SOLVER_INSTALL_SOLVABLE_PROVIDES:
3273 if (how == SOLVER_INSTALL_SOLVABLE_NAME)
3274 POOL_DEBUG(SAT_DEBUG_JOB, "job: install name %s\n", id2str(pool, what));
3275 if (how == SOLVER_INSTALL_SOLVABLE_PROVIDES)
3276 POOL_DEBUG(SAT_DEBUG_JOB, "job: install provides %s\n", dep2str(pool, what));
3278 FOR_PROVIDES(p, pp, what)
3280 /* if by name, ensure that the name matches */
3281 if (how == SOLVER_INSTALL_SOLVABLE_NAME && pool->solvables[p].name != what)
3287 /* no provider, make this an impossible rule */
3288 queue_push(&q, -SYSTEMSOLVABLE);
3291 p = queue_shift(&q); /* get first provider */
3293 d = 0; /* single provider ? -> make assertion */
3295 d = pool_queuetowhatprovides(pool, &q); /* get all providers */
3296 addrule(solv, p, d); /* add 'requires' rule */
3297 queue_push(&solv->ruletojob, i);
3299 case SOLVER_ERASE_SOLVABLE_NAME: /* remove by capability */
3300 case SOLVER_ERASE_SOLVABLE_PROVIDES:
3301 if (how == SOLVER_ERASE_SOLVABLE_NAME)
3302 POOL_DEBUG(SAT_DEBUG_JOB, "job: erase name %s\n", id2str(pool, what));
3303 if (how == SOLVER_ERASE_SOLVABLE_PROVIDES)
3304 POOL_DEBUG(SAT_DEBUG_JOB, "job: erase provides %s\n", dep2str(pool, what));
3305 FOR_PROVIDES(p, pp, what)
3307 /* if by name, ensure that the name matches */
3308 if (how == SOLVER_ERASE_SOLVABLE_NAME && pool->solvables[p].name != what)
3310 addrule(solv, -p, 0); /* add 'remove' rule */
3311 queue_push(&solv->ruletojob, i);
3314 case SOLVER_INSTALL_SOLVABLE_UPDATE: /* find update for solvable */
3315 s = pool->solvables + what;
3316 POOL_DEBUG(SAT_DEBUG_JOB, "job: update %s\n", solvable2str(pool, s));
3317 addupdaterule(solv, s, 0);
3318 queue_push(&solv->ruletojob, i);
3321 IF_POOLDEBUG (SAT_DEBUG_JOB)
3324 if (solv->nrules == oldnrules)
3325 POOL_DEBUG(SAT_DEBUG_JOB, " - no rule created");
3326 for (j = oldnrules; j < solv->nrules; j++)
3328 POOL_DEBUG(SAT_DEBUG_JOB, " - job ");
3329 printrule(solv, SAT_DEBUG_JOB, solv->rules + j);
3334 if (solv->ruletojob.count != solv->nrules - solv->jobrules)
3338 * now add system rules
3342 POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** Add system rules ***\n");
3345 solv->systemrules = solv->nrules;
3348 * create rules for updating installed solvables
3352 if (installed && !solv->allowuninstall)
3353 { /* loop over all installed solvables */
3354 /* we create all update rules, but disable some later on depending on the job */
3355 for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
3356 if (s->repo == installed)
3357 addupdaterule(solv, s, 0); /* allowall = 0 */
3359 addupdaterule(solv, 0, 0); /* create dummy rule; allowall = 0 */
3360 /* consistency check: we added a rule for _every_ system solvable */
3361 if (solv->nrules - solv->systemrules != installed->end - installed->start)
3365 /* create special weak system rules */
3366 /* those are used later on to keep a version of the installed packages in
3368 if (installed && installed->nsolvables)
3370 solv->weaksystemrules = xcalloc(installed->end - installed->start, sizeof(Id));
3371 FOR_REPO_SOLVABLES(installed, p, s)
3373 policy_findupdatepackages(solv, s, &q, 1);
3375 solv->weaksystemrules[p - installed->start] = pool_queuetowhatprovides(pool, &q);
3379 /* free unneeded memory */
3380 map_free(&addedmap);
3383 solv->weakrules = solv->nrules;
3385 /* try real hard to keep packages installed */
3388 FOR_REPO_SOLVABLES(installed, p, s)
3390 /* FIXME: can't work with refine_suggestion! */
3391 /* need to always add the rule but disable it */
3392 if (MAPTST(&solv->noupdate, p - installed->start))
3394 d = solv->weaksystemrules[p - installed->start];
3395 addrule(solv, p, d);
3399 /* all new rules are learnt after this point */
3400 solv->learntrules = solv->nrules;
3407 disableupdaterules(solv, job, -1);
3408 makeruledecisions(solv);
3410 POOL_DEBUG(SAT_DEBUG_STATS, "problems so far: %d\n", solv->problems.count);
3412 run_solver(solv, 1, 1);
3414 /* find suggested packages */
3415 if (!solv->problems.count)
3417 Id sug, *sugp, p, *pp;
3419 /* create map of all suggests that are still open */
3420 solv->recommends_index = -1;
3421 MAPZERO(&solv->suggestsmap);
3422 for (i = 0; i < solv->decisionq.count; i++)
3424 p = solv->decisionq.elements[i];
3427 s = pool->solvables + p;
3430 sugp = s->repo->idarraydata + s->suggests;
3431 while ((sug = *sugp++) != 0)
3433 FOR_PROVIDES(p, pp, sug)
3434 if (solv->decisionmap[p] > 0)
3437 continue; /* already fulfilled */
3438 FOR_PROVIDES(p, pp, sug)
3439 MAPSET(&solv->suggestsmap, p);
3443 for (i = 1; i < pool->nsolvables; i++)
3445 if (solv->decisionmap[i] != 0)
3447 s = pool->solvables + i;
3448 if (!MAPTST(&solv->suggestsmap, i))
3452 if (!pool_installable(pool, s))
3454 if (!solver_is_enhancing(solv, s))
3457 queue_push(&solv->suggestions, i);
3459 policy_filter_unwanted(solv, &solv->suggestions, 0, POLICY_MODE_SUGGEST);
3462 if (solv->problems.count)
3463 problems_to_solutions(solv, job);