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, Rule *r, Id v)
96 Pool *pool = solv->pool;
100 s = pool->solvables + -v;
101 printf(" !%s-%s.%s [%d]", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch), -v);
105 s = pool->solvables + v;
106 printf(" %s-%s.%s [%d]", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch), v);
115 if (solv->decisionmap[s - pool->solvables] > 0)
116 printf(" Install.level%d", solv->decisionmap[s - pool->solvables]);
117 if (solv->decisionmap[s - pool->solvables] < 0)
118 printf(" Conflict.level%d", -solv->decisionmap[s - pool->solvables]);
128 printrule(Solver *solv, Rule *r)
133 if (r >= solv->rules && r < solv->rules + solv->nrules) /* r is a solver rule */
134 printf("Rule #%d:", (int)(r - solv->rules));
136 printf("Rule:"); /* r is any rule */
138 printf(" (disabled)");
144 else if (r->d == ID_NULL)
151 v = solv->pool->whatprovidesdata[r->d + i - 1];
154 printruleelement(solv, r, v);
156 printf(" next: %d %d\n", r->n1, r->n2);
160 /*-----------------------------------------------------------------*/
166 static Pool *unifyrules_sortcmp_data;
169 * compare rules for unification sort
173 unifyrules_sortcmp(const void *ap, const void *bp)
175 Pool *pool = unifyrules_sortcmp_data;
176 Rule *a = (Rule *)ap;
177 Rule *b = (Rule *)bp;
183 return x; /* p differs */
186 if (a->d == 0 && b->d == 0)
187 return a->w2 - b->w2; /* assertion: return w2 diff */
189 if (a->d == 0) /* a is assertion, b not */
191 x = a->w2 - pool->whatprovidesdata[b->d];
195 if (b->d == 0) /* b is assertion, a not */
197 x = pool->whatprovidesdata[a->d] - b->w2;
201 /* compare whatprovidesdata */
202 ad = pool->whatprovidesdata + a->d;
203 bd = pool->whatprovidesdata + b->d;
205 if ((x = *ad++ - *bd++) != 0)
216 unifyrules(Solver *solv)
221 if (solv->nrules <= 1) /* nothing to unify */
224 if (solv->pool->verbose > 3)
225 printf ("----- unifyrules -----\n");
227 /* sort rules first */
228 unifyrules_sortcmp_data = solv->pool;
229 qsort(solv->rules + 1, solv->nrules - 1, sizeof(Rule), unifyrules_sortcmp);
236 for (i = j = 1, ir = solv->rules + 1; i < solv->nrules; i++, ir++)
238 if (jr && !unifyrules_sortcmp(ir, jr))
239 continue; /* prune! */
240 jr = solv->rules + j++; /* keep! */
245 /* reduced count from nrules to j rules */
246 if (solv->pool->verbose) printf("pruned rules from %d to %d\n", solv->nrules, j);
248 /* adapt rule buffer */
250 solv->rules = (Rule *)xrealloc(solv->rules, ((solv->nrules + RULES_BLOCK) & ~RULES_BLOCK) * sizeof(Rule));
252 if (solv->pool->verbose)
259 for (i = 1; i < solv->nrules; i++)
266 dp = solv->pool->whatprovidesdata + r->d;
271 printf(" binary: %d\n", binr);
272 printf(" normal: %d, %d literals\n", solv->nrules - 1 - binr, lits);
275 if (solv->pool->verbose > 3)
276 printf ("----- unifyrules end -----\n");
286 hashrule(Solver *solv, Id p, Id d, int n)
288 unsigned int x = (unsigned int)p;
292 return (x * 37) ^ (unsigned int)d;
293 dp = solv->pool->whatprovidesdata + d;
295 x = (x * 37) ^ (unsigned int)*dp++;
303 * p = direct literal; always < 0 for installed rpm rules
304 * d, if < 0 direct literal, if > 0 offset into whatprovides, if == 0 rule is assertion (look at p only)
307 * A requires b, b provided by B1,B2,B3 => (-A|B1|B2|B3)
309 * p < 0 : pkg id of A
310 * d > 0 : Offset in whatprovidesdata (list of providers of b)
312 * A conflicts b, b provided by B1,B2,B3 => (-A|-B1), (-A|-B2), (-A|-B3)
313 * p < 0 : pkg id of A
314 * d < 0 : Id of solvable (e.g. B1)
316 * d == 0: unary rule, assertion => (A) or (-A)
318 * Install: p > 0, d = 0 (A) user requested install
319 * Remove: p < 0, d = 0 (-A) user requested remove
320 * Requires: p < 0, d > 0 (-A|B1|B2|...) d: <list of providers for requirement of p>
321 * Updates: p > 0, d > 0 (A|B1|B2|...) d: <list of updates for solvable p>
322 * Conflicts: p < 0, d < 0 (-A|-B) either p (conflict issuer) or d (conflict provider) (binary rule)
323 * ? p > 0, d < 0 (A|-B)
324 * No-op ?: p = 0, d = 0 (null) (used as policy rule placeholder)
328 * Direct assertion (no watch needed)( if d <0 ) --> d = 0, w1 = p, w2 = 0
329 * Binary rule: p = first literal, d = 0, w2 = second literal, w1 = p
330 * every other : w1 = p, w2 = whatprovidesdata[d];
331 * Disabled rule: w1 = 0
333 * always returns a rule for non-rpm rules
337 addrule(Solver *solv, Id p, Id d)
342 int n = 0; /* number of literals in rule - 1
343 0 = direct assertion (single literal)
347 /* it often happenes that requires lead to adding the same rpm rule
348 * multiple times, so we prune those duplicates right away to make
349 * the work for unifyrules a bit easier */
351 if (solv->nrules && !solv->jobrules)
353 r = solv->rules + solv->nrules - 1; /* get the last added rule */
354 if (r->p == p && r->d == d && d != 0) /* identical and not user requested */
360 /* always a binary rule */
362 return 0; /* ignore self conflict */
367 for (dp = solv->pool->whatprovidesdata + d; *dp; dp++, n++)
369 return 0; /* rule is self-fulfilling */
374 if (n == 0 && !solv->jobrules)
376 /* this is a rpm rule assertion, we do not have to allocate it */
377 /* it can be identified by a level of 1 and a zero reason */
378 /* we must not drop those rules from the decisionq when rewinding! */
381 if (solv->decisionmap[-p] > 0 || solv->decisionmap[-p] < -1)
383 if (solv->decisionmap[-p])
384 return 0; /* already got that one */
385 queue_push(&solv->decisionq, p);
386 queue_push(&solv->decisionq_why, 0);
387 solv->decisionmap[-p] = -1;
392 /* smallest literal first so we can find dups */
396 n = 1; /* re-set n, was used as temp var */
399 /* check if the last added rule is exactly the same as what we're looking for. */
400 if (r && n == 1 && !r->d && r->p == p && r->w2 == d)
403 if (r && n > 1 && r->d && r->p == p)
408 dp2 = solv->pool->whatprovidesdata + r->d;
409 for (dp = solv->pool->whatprovidesdata + d; *dp; dp++, dp2++)
420 /* check and extend rule buffer */
421 if ((solv->nrules & RULES_BLOCK) == 0)
423 solv->rules = (Rule *)xrealloc(solv->rules, (solv->nrules + (RULES_BLOCK + 1)) * sizeof(Rule));
426 r = solv->rules + solv->nrules++; /* point to rule space */
431 /* direct assertion, no watch needed */
447 r->w2 = solv->pool->whatprovidesdata[d];
452 if (solv->pool->verbose > 3)
454 printf (" Add rule: ");
462 disablerule(Solver *solv, Rule *r)
468 enablerule(Solver *solv, Rule *r)
470 if (r->d == 0 || r->w2 != r->p)
473 r->w1 = solv->pool->whatprovidesdata[r->d];
477 /**********************************************************************************/
479 /* a problem is an item on the solver's problem list. It can either be >0, in that
480 * case it is a system (upgrade) rule, or it can be <0, which makes it refer to a job
481 * consisting of multiple job rules.
485 disableproblem(Solver *solv, Id v)
493 disablerule(solv, solv->rules + v);
497 jp = solv->ruletojob.elements;
498 for (i = solv->jobrules, r = solv->rules + i; i < solv->systemrules; i++, r++, jp++)
500 disablerule(solv, r);
504 enableproblem(Solver *solv, Id v)
512 enablerule(solv, solv->rules + v);
516 jp = solv->ruletojob.elements;
517 for (i = solv->jobrules, r = solv->rules + i; i < solv->systemrules; i++, r++, jp++)
523 printproblem(Solver *solv, Id v)
530 printrule(solv, solv->rules + v);
534 printf("JOB %d\n", v);
535 jp = solv->ruletojob.elements;
536 for (i = solv->jobrules, r = solv->rules + i; i < solv->systemrules; i++, r++, jp++)
548 /************************************************************************/
550 /* go through system and job rules and add direct assertions
551 * to the decisionqueue. If we find a conflict, disable rules and
552 * add them to problem queue.
553 * (disablerules is always true for the cases when we get called)
556 makeruledecisions(Solver *solv)
563 if (solv->pool->verbose > 3)
564 printf ("----- makeruledecisions ; size decisionq: %d -----\n",solv->decisionq.count);
566 decisionstart = solv->decisionq.count;
567 /* rpm rules don't have assertions, so we can start with the job
569 for (ri = solv->jobrules, r = solv->rules + ri; ri < solv->nrules; ri++, r++)
571 if (!r->w1 || r->w2) /* disabled or no assertion */
575 if (solv->decisionmap[vv] == 0)
577 queue_push(&solv->decisionq, v);
578 queue_push(&solv->decisionq_why, r - solv->rules);
579 solv->decisionmap[vv] = v > 0 ? 1 : -1;
580 if (solv->pool->verbose > 3)
582 Solvable *s = solv->pool->solvables + vv;
584 printf("removing %s-%s.%s\n", id2str(solv->pool, s->name), id2str(solv->pool, s->evr), id2str(solv->pool, s->arch));
586 printf("installing %s-%s.%s\n", id2str(solv->pool, s->name), id2str(solv->pool, s->evr), id2str(solv->pool, s->arch));
590 if (v > 0 && solv->decisionmap[vv] > 0)
592 if (v < 0 && solv->decisionmap[vv] < 0)
594 /* found a conflict! */
595 if (ri >= solv->learntrules)
597 /* cannot happen, as this would mean that the problem
598 * was not solvable, so we wouldn't have created the
599 * learnt rule at all */
602 /* if we are weak, just disable ourself */
603 if (ri >= solv->weakrules)
605 printf("conflict, but I am weak, disabling ");
607 disablerule(solv, r);
611 /* only job and system rules left */
612 for (i = 0; i < solv->decisionq.count; i++)
613 if (solv->decisionq.elements[i] == -v)
615 if (i == solv->decisionq.count)
617 if (solv->decisionq_why.elements[i] == 0)
619 /* conflict with rpm rule, need only disable our rule */
620 if (v < 0 && v != -SYSTEMSOLVABLE)
623 queue_push(&solv->problems, solv->learnt_pool.count);
624 queue_push(&solv->learnt_pool, ri);
625 queue_push(&solv->learnt_pool, v != -SYSTEMSOLVABLE ? -v : v);
626 queue_push(&solv->learnt_pool, 0);
627 printf("conflict with rpm rule, disabling rule #%d\n", ri);
628 if (ri < solv->systemrules)
629 v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
632 queue_push(&solv->problems, v);
633 disableproblem(solv, v);
634 queue_push(&solv->problems, 0);
638 queue_push(&solv->problems, solv->learnt_pool.count);
639 queue_push(&solv->learnt_pool, ri);
640 queue_push(&solv->learnt_pool, solv->decisionq_why.elements[i]);
641 queue_push(&solv->learnt_pool, 0);
643 /* conflict with another job or system rule */
644 printf("conflicting system/job rules over literal %d\n", vv);
645 /* push all of our rules asserting this literal on the problem stack */
646 for (i = solv->jobrules, rr = solv->rules + i; i < solv->nrules; i++, rr++)
648 if (!rr->w1 || rr->w2)
650 if (rr->p != v && rr->p != -v)
652 printf(" - disabling rule #%d\n", i);
654 if (i < solv->systemrules)
655 v = -(solv->ruletojob.elements[i - solv->jobrules] + 1);
656 queue_push(&solv->problems, v);
657 disableproblem(solv, v);
659 queue_push(&solv->problems, 0);
662 while (solv->decisionq.count > decisionstart)
664 v = solv->decisionq.elements[--solv->decisionq.count];
665 --solv->decisionq_why.count;
667 solv->decisionmap[vv] = 0;
669 ri = solv->jobrules - 1;
670 r = solv->rules + ri;
673 if (solv->pool->verbose > 3)
674 printf ("----- makeruledecisions end; size decisionq: %d -----\n",solv->decisionq.count);
678 * we have enabled or disabled some of our rules. We now reenable all
679 * of our learnt rules but the ones that were learnt from rules that
683 enabledisablelearntrules(Solver *solv)
685 Pool *pool = solv->pool;
691 printf("enabledisablelearntrules called\n");
692 for (i = solv->learntrules, r = solv->rules + i; i < solv->nrules; i++, r++)
694 whyp = solv->learnt_pool.elements + solv->learnt_why.elements[i - solv->learntrules];
695 while ((why = *whyp++) != 0)
697 if (why < 0 || why >= i)
698 abort(); /* cannot reference newer learnt rules */
699 if (!solv->rules[why].w1)
702 /* why != 0: we found a disabled rule, disable the learnt rule */
707 printf("disabling learnt ");
710 disablerule(solv, r);
712 else if (!why && !r->w1)
716 printf("re-enabling learnt ");
725 /* FIXME: bad code ahead, replace as soon as possible */
727 disableupdaterules(Solver *solv, Queue *job, int jobidx)
729 Pool *pool = solv->pool;
731 Id how, what, p, *pp;
737 installed = solv->installed;
743 how = job->elements[jobidx];
746 case SOLVER_INSTALL_SOLVABLE:
747 case SOLVER_ERASE_SOLVABLE:
748 case SOLVER_ERASE_SOLVABLE_NAME:
749 case SOLVER_ERASE_SOLVABLE_PROVIDES:
755 /* go through all enabled job rules */
756 MAPZERO(&solv->noupdate);
757 for (i = solv->jobrules; i < solv->systemrules; i++)
760 if (!r->w1) /* disabled? */
762 j = solv->ruletojob.elements[i - solv->jobrules];
766 how = job->elements[j];
767 what = job->elements[j + 1];
770 case SOLVER_INSTALL_SOLVABLE: /* install specific solvable */
771 s = pool->solvables + what;
772 FOR_PROVIDES(p, pp, s->name)
774 if (pool->solvables[p].name != s->name)
776 if (pool->solvables[p].repo == installed)
777 MAPSET(&solv->noupdate, p - installed->start);
780 case SOLVER_ERASE_SOLVABLE:
781 s = pool->solvables + what;
782 if (s->repo == installed)
783 MAPSET(&solv->noupdate, what - installed->start);
785 case SOLVER_ERASE_SOLVABLE_NAME: /* remove by capability */
786 case SOLVER_ERASE_SOLVABLE_PROVIDES:
787 FOR_PROVIDES(p, pp, what)
789 if (how == SOLVER_ERASE_SOLVABLE_NAME && pool->solvables[p].name != what)
791 if (pool->solvables[p].repo == installed)
792 MAPSET(&solv->noupdate, p - installed->start);
800 /* fixup update rule status */
801 if (solv->allowuninstall)
802 return; /* no update rules at all */
806 /* we just disabled job #jobidx. enable all update rules
807 * that aren't disabled by the remaining job rules */
808 how = job->elements[jobidx];
809 what = job->elements[jobidx + 1];
812 case SOLVER_INSTALL_SOLVABLE:
813 s = pool->solvables + what;
814 FOR_PROVIDES(p, pp, s->name)
816 if (pool->solvables[p].name != s->name)
818 if (pool->solvables[p].repo != installed)
820 if (MAPTST(&solv->noupdate, p - installed->start))
822 r = solv->rules + solv->systemrules + (p - installed->start);
828 printf("@@@ re-enabling ");
833 case SOLVER_ERASE_SOLVABLE:
834 s = pool->solvables + what;
835 if (s->repo != installed)
837 if (MAPTST(&solv->noupdate, what - installed->start))
839 r = solv->rules + solv->systemrules + (what - installed->start);
845 printf("@@@ re-enabling ");
849 case SOLVER_ERASE_SOLVABLE_NAME: /* remove by capability */
850 case SOLVER_ERASE_SOLVABLE_PROVIDES:
851 FOR_PROVIDES(p, pp, what)
853 if (how == SOLVER_ERASE_SOLVABLE_NAME && pool->solvables[p].name != what)
855 if (pool->solvables[p].repo != installed)
857 if (MAPTST(&solv->noupdate, p - installed->start))
859 r = solv->rules + solv->systemrules + (p - installed->start);
865 printf("@@@ re-enabling ");
876 for (i = 0; i < installed->nsolvables; i++)
878 r = solv->rules + solv->systemrules + i;
879 if (r->w1 && MAPTST(&solv->noupdate, i))
880 disablerule(solv, r); /* was enabled, need to disable */
886 * add (install) rules for solvable
887 * for unfulfilled requirements, conflicts, obsoletes,....
888 * add a negative assertion for solvables that are not installable
892 addrpmrulesforsolvable(Solver *solv, Solvable *s, Map *m)
894 Pool *pool = solv->pool;
895 Repo *installed = solv->installed;
909 if (solv->pool->verbose > 3)
910 printf ("----- addrpmrulesforsolvable -----\n");
912 queue_init_buffer(&q, qbuf, sizeof(qbuf)/sizeof(*qbuf));
913 queue_push(&q, s - pool->solvables); /* push solvable Id */
919 * s: Pointer to solvable
923 if (MAPTST(m, n)) /* continue if already done */
927 s = pool->solvables + n; /* s = Solvable in question */
930 if (installed /* Installed system available */
931 && !solv->fixsystem /* NOT repair errors in rpm dependency graph */
932 && s->repo == installed) /* solvable is installed? */
934 dontfix = 1; /* dont care about broken rpm deps */
937 if (!dontfix && s->arch != ARCH_SRC && s->arch != ARCH_NOSRC && !pool_installable(pool, s))
940 printf("package %s-%s.%s [%d] is not installable\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch), (Id)(s - pool->solvables));
941 addrule(solv, -n, 0); /* uninstallable */
944 /*-----------------------------------------
945 * check requires of s
950 reqp = s->repo->idarraydata + s->requires;
951 while ((req = *reqp++) != 0) /* go throw all requires */
953 if (req == SOLVABLE_PREREQMARKER) /* skip the marker */
956 dp = GET_PROVIDESP(req, p); /* get providers of req; p is a dummy only */
958 if (*dp == SYSTEMSOLVABLE) /* always installed */
963 /* the strategy here is to not insist on dependencies
964 * that are already broken. so if we find one provider
965 * that was already installed, we know that the
966 * dependency was not broken before so we enforce it */
967 for (i = 0; (p = dp[i]) != 0; i++) /* for all providers */
969 if (pool->solvables[p].repo == installed)
970 break; /* provider was installed */
972 if (!p) /* previously broken dependency */
975 printf("ignoring broken requires %s of installed package %s-%s.%s\n", dep2str(pool, req), id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
982 /* nothing provides req! */
984 printf("package %s-%s.%s [%d] is not installable (%s)\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch), (Id)(s - pool->solvables), dep2str(pool, req));
985 addrule(solv, -n, 0); /* mark requestor as uninstallable */
989 if (pool->verbose > 2)
991 printf(" %s-%s.%s requires %s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch), dep2str(pool, req));
992 for (i = 0; dp[i]; i++)
993 printf(" provided by %s-%s.%s\n", id2str(pool, pool->solvables[dp[i]].name), id2str(pool, pool->solvables[dp[i]].evr), id2str(pool, pool->solvables[dp[i]].arch));
996 /* add 'requires' dependency */
997 /* rule: (-requestor|provider1|provider2|...|providerN) */
998 addrule(solv, -n, dp - pool->whatprovidesdata);
1000 /* descend the dependency tree */
1001 for (; *dp; dp++) /* loop through all providers */
1003 if (!MAPTST(m, *dp))
1004 queue_push(&q, *dp);
1007 } /* while, requirements of n */
1009 } /* if, requirements */
1011 /* that's all we check for src packages */
1012 if (s->arch == ARCH_SRC || s->arch == ARCH_NOSRC)
1015 /*-----------------------------------------
1016 * check conflicts of s
1021 conp = s->repo->idarraydata + s->conflicts;
1022 while ((con = *conp++) != 0)
1024 FOR_PROVIDES(p, pp, con)
1026 /* dontfix: dont care about conflicts with already installed packs */
1027 if (dontfix && pool->solvables[p].repo == installed)
1029 /* rule: -n|-p: either solvable _or_ provider of conflict */
1030 addrule(solv, -n, -p);
1035 /*-----------------------------------------
1036 * check obsoletes if not installed
1038 if (!installed || pool->solvables[n].repo != installed)
1039 { /* not installed */
1042 obsp = s->repo->idarraydata + s->obsoletes;
1043 while ((obs = *obsp++) != 0)
1045 FOR_PROVIDES(p, pp, obs)
1046 addrule(solv, -n, -p);
1049 FOR_PROVIDES(p, pp, s->name)
1051 if (s->name == pool->solvables[p].name)
1052 addrule(solv, -n, -p);
1056 /*-----------------------------------------
1057 * add recommends to the rule list
1061 recp = s->repo->idarraydata + s->recommends;
1062 while ((rec = *recp++) != 0)
1064 FOR_PROVIDES(p, pp, rec)
1071 sugp = s->repo->idarraydata + s->suggests;
1072 while ((sug = *sugp++) != 0)
1074 FOR_PROVIDES(p, pp, sug)
1081 if (solv->pool->verbose > 3)
1082 printf ("----- addrpmrulesforsolvable end -----\n");
1087 addrpmrulesforweak(Solver *solv, Map *m)
1089 Pool *pool = solv->pool;
1094 if (solv->pool->verbose > 3)
1095 printf ("----- addrpmrulesforweak -----\n");
1096 for (i = n = 1; n < pool->nsolvables; i++, n++)
1098 if (i == pool->nsolvables)
1102 s = pool->solvables + i;
1103 if (!pool_installable(pool, s))
1108 supp = s->repo->idarraydata + s->supplements;
1109 while ((sup = *supp++) != ID_NULL)
1110 if (dep_possible(solv, sup, m))
1113 if (!sup && s->freshens)
1115 supp = s->repo->idarraydata + s->freshens;
1116 while ((sup = *supp++) != ID_NULL)
1117 if (dep_possible(solv, sup, m))
1120 if (!sup && s->enhances)
1122 supp = s->repo->idarraydata + s->enhances;
1123 while ((sup = *supp++) != ID_NULL)
1124 if (dep_possible(solv, sup, m))
1129 addrpmrulesforsolvable(solv, s, m);
1132 if (solv->pool->verbose > 3)
1133 printf ("----- addrpmrulesforweak end -----\n");
1137 addrpmrulesforupdaters(Solver *solv, Solvable *s, Map *m, int allowall)
1139 Pool *pool = solv->pool;
1144 if (solv->pool->verbose > 3)
1145 printf ("----- addrpmrulesforupdaters -----\n");
1147 queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
1148 policy_findupdatepackages(solv, s, &qs, allowall);
1149 if (!MAPTST(m, s - pool->solvables)) /* add rule for s if not already done */
1150 addrpmrulesforsolvable(solv, s, m);
1151 for (i = 0; i < qs.count; i++)
1152 if (!MAPTST(m, qs.elements[i]))
1153 addrpmrulesforsolvable(solv, pool->solvables + qs.elements[i], m);
1156 if (solv->pool->verbose > 3)
1157 printf ("----- addrpmrulesforupdaters -----\n");
1162 * add rule for update
1163 * (A|A1|A2|A3...) An = update candidates for A
1165 * s = (installed) solvable
1169 addupdaterule(Solver *solv, Solvable *s, int allowall)
1171 /* installed packages get a special upgrade allowed rule */
1172 Pool *pool = solv->pool;
1177 if (solv->pool->verbose > 3)
1178 printf ("----- addupdaterule -----\n");
1180 queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
1181 policy_findupdatepackages(solv, s, &qs, allowall);
1182 if (qs.count == 0) /* no updaters found */
1185 d = pool_queuetowhatprovides(pool, &qs); /* intern computed queue */
1187 addrule(solv, s - pool->solvables, d); /* allow update of s */
1188 if (solv->pool->verbose > 3)
1189 printf ("----- 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 if (solv->pool->verbose > 3)
1274 printf ("----- propagate -----\n");
1276 while (solv->propagate_index < solv->decisionq.count)
1278 /* negate because our watches trigger if literal goes FALSE */
1279 pkg = -solv->decisionq.elements[solv->propagate_index++];
1280 if (pool->verbose > 3)
1282 printf("popagate for decision %d level %d\n", -pkg, level);
1283 printruleelement(solv, 0, -pkg);
1286 for (rp = watches + pkg; *rp; rp = nrp)
1288 r = solv->rules + *rp;
1290 if (pool->verbose > 3)
1292 printf(" watch triggered ");
1306 /* if clause is TRUE, nothing to do */
1307 if (DECISIONMAP_TRUE(ow))
1312 /* not a binary clause, check if we need to move our watch */
1313 /* search for a literal that is not ow and not false */
1314 /* (true is also ok, in that case the rule is fulfilled) */
1315 if (r->p && r->p != ow && !DECISIONMAP_TRUE(-r->p))
1318 for (dp = pool->whatprovidesdata + r->d; (p = *dp++) != 0;)
1319 if (p != ow && !DECISIONMAP_TRUE(-p))
1323 /* p is free to watch, move watch to p */
1324 if (pool->verbose > 3)
1327 printf(" -> move w%d to %s-%s.%s\n", (pkg == r->w1 ? 1 : 2), id2str(pool, pool->solvables[p].name), id2str(pool, pool->solvables[p].evr), id2str(pool, pool->solvables[p].arch));
1329 printf(" -> move w%d to !%s-%s.%s\n", (pkg == r->w1 ? 1 : 2), id2str(pool, pool->solvables[-p].name), id2str(pool, pool->solvables[-p].evr), id2str(pool, pool->solvables[-p].arch));
1343 watches[p] = r - solv->rules;
1347 /* unit clause found, set other watch to TRUE */
1348 if (DECISIONMAP_TRUE(-ow))
1349 return r; /* eek, a conflict! */
1350 if (pool->verbose > 2)
1356 decisionmap[ow] = level;
1358 decisionmap[-ow] = -level;
1359 queue_push(&solv->decisionq, ow);
1360 queue_push(&solv->decisionq_why, r - solv->rules);
1361 if (pool->verbose > 3)
1363 Solvable *s = pool->solvables + (ow > 0 ? ow : -ow);
1365 printf(" -> decided to install %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
1367 printf(" -> decided to conflict %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
1371 if (solv->pool->verbose > 3)
1372 printf ("----- propagate end-----\n");
1374 return 0; /* all is well */
1378 /*-----------------------------------------------------------------*/
1387 analyze(Solver *solv, int level, Rule *c, int *pr, int *dr, int *why)
1389 Pool *pool = solv->pool;
1392 Map seen; /* global? */
1396 int learnt_why = solv->learnt_pool.count;
1397 Id *decisionmap = solv->decisionmap;
1401 if (pool->verbose > 1) printf("ANALYZE at %d ----------------------\n", level);
1402 map_init(&seen, pool->nsolvables);
1403 idx = solv->decisionq.count;
1406 if (pool->verbose > 1)
1408 if (c - solv->rules >= solv->learntrules)
1410 else if (c - solv->rules >= solv->weakrules)
1412 else if (c - solv->rules >= solv->systemrules)
1414 else if (c - solv->rules >= solv->jobrules)
1418 queue_push(&solv->learnt_pool, c - solv->rules);
1419 dp = c->d ? pool->whatprovidesdata + c->d : 0;
1430 if (DECISIONMAP_TRUE(v)) /* the one true literal */
1432 vv = v > 0 ? v : -v;
1433 if (MAPTST(&seen, vv))
1435 l = solv->decisionmap[vv];
1442 for (j = 0; j < solv->decisionq.count; j++)
1443 if (solv->decisionq.elements[j] == v)
1445 if (j == solv->decisionq.count)
1447 queue_push(&rulq, -(j + 1));
1449 continue; /* initial setting */
1453 num++; /* need to do this one as well */
1457 if (pool->verbose > 3)
1459 printf("PUSH %d ", v);
1460 printruleelement(solv, 0, v);
1466 if (pool->verbose > 3)
1467 printf("num = %d\n", num);
1472 v = solv->decisionq.elements[--idx];
1473 vv = v > 0 ? v : -v;
1474 if (MAPTST(&seen, vv))
1477 c = solv->rules + solv->decisionq_why.elements[idx];
1485 else if (r.count == 1 && r.elements[0] < 0)
1486 *dr = r.elements[0];
1488 *dr = pool_queuetowhatprovides(pool, &r);
1489 if (pool->verbose > 1)
1491 printf("learned rule for level %d (am %d)\n", rlevel, level);
1492 printruleelement(solv, 0, -v);
1493 for (i = 0; i < r.count; i++)
1496 printruleelement(solv, 0, v);
1500 queue_push(&solv->learnt_pool, 0);
1501 if (pool->verbose > 3)
1503 for (i = learnt_why; solv->learnt_pool.elements[i]; i++)
1505 printf("learnt_why ");
1506 printrule(solv, solv->rules + solv->learnt_pool.elements[i]);
1517 * reset the solver decisions to right after the rpm rules.
1518 * called after rules have been enabled/disabled
1522 reset_solver(Solver *solv)
1527 enabledisablelearntrules(solv);
1529 /* redo all direct rpm rule decisions */
1530 /* we break at the first decision with a why attached, this is
1531 * either a job/system rule assertion or a propagated decision */
1532 for (i = 0; i < solv->decisionq.count; i++)
1534 v = solv->decisionq.elements[i];
1535 solv->decisionmap[v > 0 ? v : -v] = 0;
1537 for (i = 0; i < solv->decisionq_why.count; i++)
1538 if (solv->decisionq_why.elements[i])
1542 v = solv->decisionq.elements[i];
1543 solv->decisionmap[v > 0 ? v : -v] = v > 0 ? 1 : -1;
1546 if (solv->pool->verbose > 1)
1547 printf("decisions done reduced from %d to %d\n", solv->decisionq.count, i);
1549 solv->decisionq_why.count = i;
1550 solv->decisionq.count = i;
1551 solv->recommends_index = -1;
1552 solv->propagate_index = 0;
1554 /* redo all job/system decisions */
1555 makeruledecisions(solv);
1556 if (solv->pool->verbose > 1)
1557 printf("decisions so far: %d\n", solv->decisionq.count);
1558 /* recreate watch chains */
1564 * analyze_unsolvable_rule
1568 analyze_unsolvable_rule(Solver *solv, Rule *r)
1571 Id why = r - solv->rules;
1572 if (solv->pool->verbose > 1)
1574 if (why >= solv->jobrules && why < solv->systemrules)
1576 if (why >= solv->systemrules && why < solv->weakrules)
1577 printf("SYSTEM %d ", why - solv->systemrules);
1578 if (why >= solv->weakrules && why < solv->learntrules)
1580 if (solv->learntrules && why >= solv->learntrules)
1584 if (solv->learntrules && why >= solv->learntrules)
1586 for (i = solv->learnt_why.elements[why - solv->learntrules]; solv->learnt_pool.elements[i]; i++)
1587 analyze_unsolvable_rule(solv, solv->rules + solv->learnt_pool.elements[i]);
1590 /* do not add rpm rules to problem */
1591 if (why < solv->jobrules)
1593 /* turn rule into problem */
1594 if (why >= solv->jobrules && why < solv->systemrules)
1595 why = -(solv->ruletojob.elements[why - solv->jobrules] + 1);
1596 /* return if problem already countains our rule */
1597 if (solv->problems.count)
1599 for (i = solv->problems.count - 1; i >= 0; i--)
1600 if (solv->problems.elements[i] == 0) /* end of last problem reached? */
1602 else if (solv->problems.elements[i] == why)
1605 queue_push(&solv->problems, why);
1610 * analyze_unsolvable
1612 * return: 1 - disabled some rules, try again
1617 analyze_unsolvable(Solver *solv, Rule *cr, int disablerules)
1619 Pool *pool = solv->pool;
1621 Map seen; /* global to speed things up? */
1624 Id *decisionmap = solv->decisionmap;
1625 int oldproblemcount;
1626 int oldlearntpoolcount;
1629 if (pool->verbose > 1)
1630 printf("ANALYZE UNSOLVABLE ----------------------\n");
1631 oldproblemcount = solv->problems.count;
1632 oldlearntpoolcount = solv->learnt_pool.count;
1634 /* make room for proof index */
1635 /* must update it later, as analyze_unsolvable_rule would confuse
1636 * it with a rule index if we put the real value in already */
1637 queue_push(&solv->problems, 0);
1640 map_init(&seen, pool->nsolvables);
1641 queue_push(&solv->learnt_pool, r - solv->rules);
1642 analyze_unsolvable_rule(solv, r);
1643 dp = r->d ? pool->whatprovidesdata + r->d : 0;
1654 if (DECISIONMAP_TRUE(v)) /* the one true literal */
1656 vv = v > 0 ? v : -v;
1657 l = solv->decisionmap[vv];
1662 idx = solv->decisionq.count;
1665 v = solv->decisionq.elements[--idx];
1666 vv = v > 0 ? v : -v;
1667 if (!MAPTST(&seen, vv))
1669 why = solv->decisionq_why.elements[idx];
1672 /* level 1 and no why, must be an rpm assertion */
1673 if (pool->verbose > 3)
1676 printruleelement(solv, 0, v);
1678 /* this is the only positive rpm assertion */
1679 if (v == SYSTEMSOLVABLE)
1683 queue_push(&solv->learnt_pool, v);
1686 r = solv->rules + why;
1687 queue_push(&solv->learnt_pool, why);
1688 analyze_unsolvable_rule(solv, r);
1689 dp = r->d ? pool->whatprovidesdata + r->d : 0;
1700 if (DECISIONMAP_TRUE(v)) /* the one true literal */
1702 vv = v > 0 ? v : -v;
1703 l = solv->decisionmap[vv];
1710 queue_push(&solv->problems, 0); /* mark end of this problem */
1713 if (solv->weakrules != solv->learntrules)
1715 for (i = oldproblemcount + 1; i < solv->problems.count - 1; i++)
1717 why = solv->problems.elements[i];
1718 if (why < solv->weakrules || why >= solv->learntrules)
1720 if (!lastweak || lastweak < why)
1726 /* disable last weak rule */
1727 solv->problems.count = oldproblemcount;
1728 solv->learnt_pool.count = oldlearntpoolcount;
1729 r = solv->rules + lastweak;
1730 printf("disabling weak ");
1732 disablerule(solv, r);
1738 queue_push(&solv->learnt_pool, 0);
1739 solv->problems.elements[oldproblemcount] = oldlearntpoolcount;
1743 for (i = oldproblemcount + 1; i < solv->problems.count - 1; i++)
1744 disableproblem(solv, solv->problems.elements[i]);
1749 printf("UNSOLVABLE\n");
1754 /*-----------------------------------------------------------------*/
1755 /* Decision revert */
1759 * revert decision at level
1763 revert(Solver *solv, int level)
1766 while (solv->decisionq.count)
1768 v = solv->decisionq.elements[solv->decisionq.count - 1];
1769 vv = v > 0 ? v : -v;
1770 if (solv->decisionmap[vv] <= level && solv->decisionmap[vv] >= -level)
1772 if (solv->pool->verbose > 3)
1773 printf("reverting decision %d at %d\n", v, solv->decisionmap[vv]);
1774 solv->decisionmap[vv] = 0;
1775 solv->decisionq.count--;
1776 solv->decisionq_why.count--;
1777 solv->propagate_index = solv->decisionq.count;
1779 while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] <= -level)
1781 solv->branches.count--;
1782 while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] >= 0)
1783 solv->branches.count--;
1785 solv->recommends_index = -1;
1790 * watch2onhighest - put watch2 on literal with highest level
1794 watch2onhighest(Solver *solv, Rule *r)
1800 return; /* binary rule, both watches are set */
1801 dp = solv->pool->whatprovidesdata + r->d;
1802 while ((v = *dp++) != 0)
1804 l = solv->decisionmap[v < 0 ? -v : v];
1819 * add free decision to decision q, increase level
1820 * propagate decision, return if no conflict.
1821 * in conflict case, analyze conflict rule, add resulting
1822 * rule to learnt rule set, make decision from learnt
1823 * rule (always unit) and re-propagate.
1827 setpropagatelearn(Solver *solv, int level, Id decision, int disablerules)
1837 solv->decisionmap[decision] = level;
1839 solv->decisionmap[-decision] = -level;
1840 queue_push(&solv->decisionq, decision);
1841 queue_push(&solv->decisionq_why, 0);
1845 r = propagate(solv, level);
1849 return analyze_unsolvable(solv, r, disablerules);
1850 printf("conflict with rule #%d\n", (int)(r - solv->rules));
1851 l = analyze(solv, level, r, &p, &d, &why); /* learnt rule in p and d */
1852 if (l >= level || l <= 0)
1854 printf("reverting decisions (level %d -> %d)\n", level, l);
1856 revert(solv, level);
1857 r = addrule(solv, p, d); /* p requires d */
1860 if (solv->learnt_why.count != (r - solv->rules) - solv->learntrules)
1862 printf("%d %d\n", solv->learnt_why.count, (int)(r - solv->rules) - solv->learntrules);
1865 queue_push(&solv->learnt_why, why);
1868 /* at least 2 literals, needs watches */
1869 watch2onhighest(solv, r);
1870 addwatches(solv, r);
1872 solv->decisionmap[p > 0 ? p : -p] = p > 0 ? level : -level;
1873 queue_push(&solv->decisionq, p);
1874 queue_push(&solv->decisionq_why, r - solv->rules);
1875 if (solv->pool->verbose > 1)
1877 printf("decision: ");
1878 printruleelement(solv, 0, p);
1879 printf("new rule: ");
1888 * install best package from the queue. We add an extra package, inst, if
1889 * provided. See comment in weak install section.
1892 selectandinstall(Solver *solv, int level, Queue *dq, Id inst, int disablerules)
1894 Pool *pool = solv->pool;
1898 if (dq->count > 1 || inst)
1899 policy_filter_unwanted(solv, dq, inst, POLICY_MODE_CHOOSE);
1904 /* choose the supplemented one */
1905 for (i = 0; i < dq->count; i++)
1906 if (solver_is_supplementing(solv, pool->solvables + dq->elements[i]))
1910 for (i = 1; i < dq->count; i++)
1911 queue_push(&solv->branches, dq->elements[i]);
1912 queue_push(&solv->branches, -level);
1916 p = dq->elements[i];
1918 if (pool->verbose > 3)
1920 Solvable *s = pool->solvables + p;
1921 printf("installing %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
1924 return setpropagatelearn(solv, level, p, disablerules);
1928 /*-----------------------------------------------------------------*/
1929 /* Main solver interface */
1934 * create solver structure
1936 * pool: all available solvables
1937 * installed: installed Solvables
1940 * Upon solving, rules are created to flag the Solvables
1941 * of the 'installed' Repo as installed.
1945 solver_create(Pool *pool, Repo *installed)
1948 solv = (Solver *)xcalloc(1, sizeof(Solver));
1950 solv->installed = installed;
1952 queue_init(&solv->ruletojob);
1953 queue_init(&solv->decisionq);
1954 queue_init(&solv->decisionq_why);
1955 queue_init(&solv->problems);
1956 queue_init(&solv->suggestions);
1957 queue_init(&solv->learnt_why);
1958 queue_init(&solv->learnt_pool);
1959 queue_init(&solv->branches);
1961 map_init(&solv->recommendsmap, pool->nsolvables);
1962 map_init(&solv->suggestsmap, pool->nsolvables);
1963 map_init(&solv->noupdate, installed ? installed->end - installed->start : 0);
1964 solv->recommends_index = 0;
1966 solv->decisionmap = (Id *)xcalloc(pool->nsolvables, sizeof(Id));
1967 solv->rules = (Rule *)xmalloc((solv->nrules + (RULES_BLOCK + 1)) * sizeof(Rule));
1968 memset(solv->rules, 0, sizeof(Rule));
1980 solver_free(Solver *solv)
1982 queue_free(&solv->ruletojob);
1983 queue_free(&solv->decisionq);
1984 queue_free(&solv->decisionq_why);
1985 queue_free(&solv->learnt_why);
1986 queue_free(&solv->learnt_pool);
1987 queue_free(&solv->problems);
1988 queue_free(&solv->suggestions);
1989 queue_free(&solv->branches);
1991 map_free(&solv->recommendsmap);
1992 map_free(&solv->suggestsmap);
1993 map_free(&solv->noupdate);
1994 xfree(solv->decisionmap);
1996 xfree(solv->watches);
1997 xfree(solv->weaksystemrules);
1998 xfree(solv->obsoletes);
1999 xfree(solv->obsoletes_data);
2004 /*-------------------------------------------------------*/
2009 * all rules have been set up, now actually run the solver
2014 run_solver(Solver *solv, int disablerules, int doweak)
2022 Pool *pool = solv->pool;
2025 if (pool->verbose > 3)
2027 printf("number of rules: %d\n", solv->nrules);
2028 for (i = 0; i < solv->nrules; i++)
2029 printrule(solv, solv->rules + i);
2032 /* create watches chains */
2035 if (pool->verbose) printf("initial decisions: %d\n", solv->decisionq.count);
2036 if (pool->verbose > 3)
2037 printdecisions(solv);
2039 /* start SAT algorithm */
2041 systemlevel = level + 1;
2042 if (pool->verbose) printf("solving...\n");
2053 if (pool->verbose) printf("propagating (propagate_index: %d; size decisionq: %d)...\n", solv->propagate_index, solv->decisionq.count);
2054 if ((r = propagate(solv, level)) != 0)
2056 if (analyze_unsolvable(solv, r, disablerules))
2064 * installed packages
2067 if (level < systemlevel && solv->installed && solv->installed->nsolvables)
2069 if (!solv->updatesystem)
2071 /* try to keep as many packages as possible */
2072 if (pool->verbose) printf("installing system packages\n");
2073 for (i = solv->installed->start, n = 0; ; i++)
2075 if (n == solv->installed->nsolvables)
2077 if (i == solv->installed->end)
2078 i = solv->installed->start;
2079 s = pool->solvables + i;
2080 if (s->repo != solv->installed)
2083 if (solv->decisionmap[i] != 0)
2085 if (pool->verbose > 3)
2086 printf("keeping %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2088 level = setpropagatelearn(solv, level, i, disablerules);
2094 if (level <= olevel)
2098 if (solv->weaksystemrules)
2100 if (pool->verbose) printf("installing weak system packages\n");
2101 for (i = solv->installed->start; i < solv->installed->end; i++)
2103 if (pool->solvables[i].repo != solv->installed)
2105 if (solv->decisionmap[i] > 0 || (solv->decisionmap[i] < 0 && solv->weaksystemrules[i - solv->installed->start] == 0))
2107 /* noupdate is set if a job is erasing the installed solvable or installing a specific version */
2108 if (MAPTST(&solv->noupdate, i - solv->installed->start))
2111 if (solv->weaksystemrules[i - solv->installed->start])
2113 dp = pool->whatprovidesdata + solv->weaksystemrules[i - solv->installed->start];
2114 while ((p = *dp++) != 0)
2116 if (solv->decisionmap[p] > 0)
2118 if (solv->decisionmap[p] == 0)
2122 continue; /* update package already installed */
2124 if (!dq.count && solv->decisionmap[i] != 0)
2127 /* FIXME: i is handled a bit different because we do not want
2128 * to have it pruned just because it is not recommened.
2129 * we should not prune installed packages instead */
2130 level = selectandinstall(solv, level, &dq, (solv->decisionmap[i] ? 0 : i), disablerules);
2136 if (level <= olevel)
2139 if (i < solv->installed->end)
2142 systemlevel = level;
2149 if (pool->verbose) printf("deciding unresolved rules\n");
2150 for (i = 1, n = 1; ; i++, n++)
2152 if (n == solv->nrules)
2154 if (i == solv->nrules)
2156 r = solv->rules + i;
2162 /* binary or unary rule */
2163 /* need two positive undecided literals */
2164 if (r->p < 0 || r->w2 <= 0)
2166 if (solv->decisionmap[r->p] || solv->decisionmap[r->w2])
2168 queue_push(&dq, r->p);
2169 queue_push(&dq, r->w2);
2174 * all negative literals are installed
2175 * no positive literal is installed
2176 * i.e. the rule is not fulfilled and we
2177 * just need to decide on the positive literals
2181 if (solv->decisionmap[-r->p] <= 0)
2186 if (solv->decisionmap[r->p] > 0)
2188 if (solv->decisionmap[r->p] == 0)
2189 queue_push(&dq, r->p);
2191 dp = pool->whatprovidesdata + r->d;
2192 while ((p = *dp++) != 0)
2196 if (solv->decisionmap[-p] <= 0)
2201 if (solv->decisionmap[p] > 0)
2203 if (solv->decisionmap[p] == 0)
2212 /* cannot happen as this means that
2213 * the rule is unit */
2217 if (pool->verbose > 2)
2221 level = selectandinstall(solv, level, &dq, 0, disablerules);
2227 if (level < systemlevel)
2230 } /* for(), decide */
2232 if (n != solv->nrules) /* continue if level < systemlevel */
2235 if (doweak && !solv->problems.count)
2239 if (pool->verbose) printf("installing recommended packages\n");
2241 for (i = 1; i < pool->nsolvables; i++)
2243 if (solv->decisionmap[i] < 0)
2245 if (solv->decisionmap[i] > 0)
2247 Id *recp, rec, *pp, p;
2248 s = pool->solvables + i;
2249 /* installed, check for recommends */
2250 /* XXX need to special case AND ? */
2253 recp = s->repo->idarraydata + s->recommends;
2254 while ((rec = *recp++) != 0)
2257 FOR_PROVIDES(p, pp, rec)
2259 if (solv->decisionmap[p] > 0)
2264 else if (solv->decisionmap[p] == 0)
2266 queue_pushunique(&dq, p);
2274 s = pool->solvables + i;
2275 if (!s->supplements && !s->freshens)
2277 if (!pool_installable(pool, s))
2279 if (solver_is_supplementing(solv, s))
2280 queue_pushunique(&dq, i);
2286 policy_filter_unwanted(solv, &dq, 0, POLICY_MODE_RECOMMEND);
2288 s = pool->solvables + p;
2289 if (pool->verbose > 0)
2290 printf("installing recommended %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2291 level = setpropagatelearn(solv, level, p, 0);
2296 if (solv->solution_callback)
2298 solv->solution_callback(solv, solv->solution_callback_data);
2299 if (solv->branches.count)
2301 int i = solv->branches.count - 1;
2302 int l = -solv->branches.elements[i];
2304 if (solv->branches.elements[i - 1] < 0)
2306 p = solv->branches.elements[i];
2307 if (pool->verbose > 0)
2309 s = pool->solvables + p;
2310 printf("branching with %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2313 for (j = i + 1; j < solv->branches.count; j++)
2314 queue_push(&dq, solv->branches.elements[j]);
2315 solv->branches.count = i;
2317 revert(solv, level);
2319 for (j = 0; j < dq.count; j++)
2320 queue_push(&solv->branches, dq.elements[j]);
2322 level = setpropagatelearn(solv, level, p, disablerules);
2330 /* all branches done, we're finally finished */
2334 /* minimization step */
2335 if (solv->branches.count)
2337 int l = 0, lasti = -1, lastl = -1;
2339 for (i = solv->branches.count - 1; i >= 0; i--)
2341 p = solv->branches.elements[i];
2344 else if (p > 0 && solv->decisionmap[p] > l + 1)
2352 /* kill old solvable so that we do not loop */
2353 p = solv->branches.elements[lasti];
2354 solv->branches.elements[lasti] = 0;
2355 s = pool->solvables + p;
2356 if (pool->verbose > 0)
2357 printf("minimizing %d -> %d with %s-%s.%s\n", solv->decisionmap[p], l, id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2360 revert(solv, level);
2362 level = setpropagatelearn(solv, level, p, disablerules);
2379 * at this point, all rules that led to conflicts are disabled.
2380 * we re-enable all rules of a problem set but rule "sug", then
2381 * continue to disable more rules until there as again a solution.
2384 /* FIXME: think about conflicting assertions */
2387 refine_suggestion(Solver *solv, Queue *job, Id *problem, Id sug, Queue *refined)
2389 Pool *pool = solv->pool;
2398 printf("refine_suggestion start\n");
2399 for (i = 0; problem[i]; i++)
2401 if (problem[i] == sug)
2403 printproblem(solv, problem[i]);
2406 queue_init(&disabled);
2407 queue_empty(refined);
2408 queue_push(refined, sug);
2410 /* re-enable all problem rules with the exception of "sug" */
2414 for (i = 0; problem[i]; i++)
2415 if (problem[i] != sug)
2416 enableproblem(solv, problem[i]);
2419 disableupdaterules(solv, job, -(sug + 1));
2423 /* re-enable as many weak rules as possible */
2424 for (i = solv->weakrules; i < solv->learntrules; i++)
2426 r = solv->rules + i;
2428 enablerule(solv, r);
2431 queue_empty(&solv->problems);
2432 revert(solv, 1); /* XXX move to reset_solver? */
2435 run_solver(solv, 0, 0);
2436 if (!solv->problems.count)
2439 printf("no more problems!\n");
2440 if (pool->verbose > 3)
2441 printdecisions(solv);
2442 break; /* great, no more problems */
2444 disabledcnt = disabled.count;
2445 /* skip over proof index */
2446 for (i = 1; i < solv->problems.count - 1; i++)
2448 /* ignore solutions in refined */
2449 v = solv->problems.elements[i];
2451 break; /* end of problem reached */
2452 for (j = 0; problem[j]; j++)
2453 if (problem[j] != sug && problem[j] == v)
2457 queue_push(&disabled, v);
2459 if (disabled.count == disabledcnt)
2461 /* no solution found, this was an invalid suggestion! */
2463 printf("no solution found!\n");
2467 if (disabled.count == disabledcnt + 1)
2469 /* just one suggestion, add it to refined list */
2470 v = disabled.elements[disabledcnt];
2471 queue_push(refined, v);
2472 disableproblem(solv, v);
2474 disableupdaterules(solv, job, -(v + 1));
2478 /* more than one solution, disable all */
2479 /* do not push anything on refine list */
2480 if (pool->verbose > 1)
2482 printf("more than one solution found:\n");
2483 for (i = disabledcnt; i < disabled.count; i++)
2484 printproblem(solv, disabled.elements[i]);
2486 for (i = disabledcnt; i < disabled.count; i++)
2487 disableproblem(solv, disabled.elements[i]);
2490 /* all done, get us back into the same state as before */
2491 /* enable refined rules again */
2492 for (i = 0; i < disabled.count; i++)
2493 enableproblem(solv, disabled.elements[i]);
2494 /* disable problem rules again */
2495 for (i = 0; problem[i]; i++)
2496 disableproblem(solv, problem[i]);
2498 printf("refine_suggestion end\n");
2502 problems_to_solutions(Solver *solv, Queue *job)
2504 Pool *pool = solv->pool;
2512 if (!solv->problems.count)
2514 queue_clone(&problems, &solv->problems);
2515 queue_init(&solution);
2516 queue_init(&solutions);
2517 /* copy over proof index */
2518 queue_push(&solutions, problems.elements[0]);
2519 problem = problems.elements + 1;
2520 for (i = 1; i < problems.count; i++)
2522 Id v = problems.elements[i];
2525 /* mark end of this problem */
2526 queue_push(&solutions, 0);
2527 queue_push(&solutions, 0);
2528 if (i + 1 == problems.count)
2530 /* copy over proof of next problem */
2531 queue_push(&solutions, problems.elements[i + 1]);
2533 problem = problems.elements + i + 1;
2536 refine_suggestion(solv, job, problem, v, &solution);
2537 if (!solution.count)
2538 continue; /* this solution didn't work out */
2540 for (j = 0; j < solution.count; j++)
2542 why = solution.elements[j];
2544 printproblem(solv, why);
2548 queue_push(&solutions, 0);
2549 queue_push(&solutions, -why);
2551 else if (why >= solv->systemrules && why < solv->weakrules)
2554 p = solv->installed->start + (why - solv->systemrules);
2555 if (solv->weaksystemrules && solv->weaksystemrules[why - solv->systemrules])
2557 Id *dp = pool->whatprovidesdata + solv->weaksystemrules[why - solv->systemrules];
2560 if (*dp >= solv->installed->start && *dp < solv->installed->start + solv->installed->nsolvables)
2562 if (solv->decisionmap[*dp] > 0)
2569 queue_push(&solutions, p);
2570 queue_push(&solutions, rp);
2575 /* mark end of this solution */
2576 queue_push(&solutions, 0);
2577 queue_push(&solutions, 0);
2579 queue_free(&solution);
2580 queue_free(&problems);
2581 /* copy queue over to solutions */
2582 queue_free(&solv->problems);
2583 queue_clone(&solv->problems, &solutions);
2584 queue_free(&solutions);
2586 /* bring solver back into problem state */
2587 revert(solv, 1); /* XXX move to reset_solver? */
2592 solver_next_problem(Solver *solv, Id problem)
2596 return solv->problems.count ? 1 : 0;
2597 pp = solv->problems.elements + problem;
2598 while (pp[0] || pp[1])
2602 while (pp[0] || pp[1])
2607 problem = pp - solv->problems.elements;
2608 if (problem >= solv->problems.count)
2614 solver_next_solution(Solver *solv, Id problem, Id solution)
2620 pp = solv->problems.elements + solution;
2621 return pp[0] || pp[1] ? solution : 0;
2623 pp = solv->problems.elements + solution;
2624 while (pp[0] || pp[1])
2627 solution = pp - solv->problems.elements;
2628 return pp[0] || pp[1] ? solution : 0;
2632 solver_next_solutionelement(Solver *solv, Id problem, Id solution, Id element, Id *p, Id *rp)
2635 element = element ? element + 2 : solution;
2636 pp = solv->problems.elements + element;
2637 if (!(pp[0] || pp[1]))
2652 printdecisions(Solver *solv)
2654 Pool *pool = solv->pool;
2655 Repo *installed = solv->installed;
2656 Id p, *obsoletesmap;
2660 obsoletesmap = (Id *)xcalloc(pool->nsolvables, sizeof(Id));
2663 for (i = 0; i < solv->decisionq.count; i++)
2667 n = solv->decisionq.elements[i];
2670 if (n == SYSTEMSOLVABLE)
2672 s = pool->solvables + n;
2673 if (s->repo == installed) /* obsoletes don't count for already installed packages */
2675 FOR_PROVIDES(p, pp, s->name)
2676 if (s->name == pool->solvables[p].name)
2678 if (pool->solvables[p].repo == installed && !obsoletesmap[p])
2680 obsoletesmap[p] = n;
2685 for (i = 0; i < solv->decisionq.count; i++)
2690 n = solv->decisionq.elements[i];
2693 if (n == SYSTEMSOLVABLE)
2695 s = pool->solvables + n;
2696 if (s->repo == installed) /* obsoletes don't count for already installed packages */
2700 obsp = s->repo->idarraydata + s->obsoletes;
2701 while ((obs = *obsp++) != 0)
2702 FOR_PROVIDES(p, pp, obs)
2704 if (pool->solvables[p].repo == installed && !obsoletesmap[p])
2706 obsoletesmap[p] = n;
2713 /* print solvables to be erased */
2717 for (i = installed->start; i < installed->end; i++)
2719 s = pool->solvables + i;
2720 if (s->repo != installed)
2722 if (solv->decisionmap[i] >= 0)
2724 if (obsoletesmap[i])
2726 printf("erase %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2730 /* print solvables to be installed */
2732 for (i = 0; i < solv->decisionq.count; i++)
2735 p = solv->decisionq.elements[i];
2738 if (p == SYSTEMSOLVABLE)
2740 s = pool->solvables + p;
2741 if (installed && s->repo == installed)
2744 if (!obsoletesmap[p])
2746 printf("install %s-%s.%s", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2750 printf("update %s-%s.%s (obsoletes", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2751 for (j = installed->start; j < installed->end; j++)
2753 if (obsoletesmap[j] != p)
2755 s = pool->solvables + j;
2756 printf(" %s-%s.%s", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2763 xfree(obsoletesmap);
2765 if (solv->suggestions.count)
2767 printf("\nsuggested packages:\n");
2768 for (i = 0; i < solv->suggestions.count; i++)
2770 s = pool->solvables + solv->suggestions.elements[i];
2771 printf("- %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2777 printconflicts(Solver *solv, Solvable *s, Id pc)
2779 Pool *pool = solv->pool;
2780 Solvable *sc = pool->solvables + pc;
2781 Id p, *pp, con, *conp, obs, *obsp;
2786 conp = s->repo->idarraydata + s->conflicts;
2787 while ((con = *conp++) != 0)
2789 FOR_PROVIDES(p, pp, con)
2793 printf("packags %s-%s.%s conflicts with %s, which is provided by %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch), dep2str(pool, con), id2str(pool, sc->name), id2str(pool, sc->evr), id2str(pool, sc->arch));
2798 if (s->obsoletes && (!solv->installed || s->repo != solv->installed))
2800 obsp = s->repo->idarraydata + s->obsoletes;
2801 while ((obs = *obsp++) != 0)
2803 FOR_PROVIDES(p, pp, obs)
2807 printf("packags %s-%s.%s obsolets %s, which is provided by %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch), dep2str(pool, obs), id2str(pool, sc->name), id2str(pool, sc->evr), id2str(pool, sc->arch));
2816 printprobleminfo(Solver *solv, Queue *job, Id problem)
2818 Pool *pool = solv->pool;
2822 Id idx = solv->problems.elements[problem - 1];
2824 rn = solv->learnt_pool.elements[idx];
2827 p = rn; /* fake a negative assertion rule */
2832 r = solv->rules + rn;
2836 if (!r || r->w2 == 0)
2842 if (p == -SYSTEMSOLVABLE)
2846 /* we tried to deinstall the system solvable. must be a job. */
2847 if (rn < solv->jobrules || rn >= solv->systemrules)
2849 ji = solv->ruletojob.elements[rn - solv->jobrules];
2850 what = job->elements[ji + 1];
2851 switch (job->elements[ji])
2853 case SOLVER_INSTALL_SOLVABLE_NAME:
2854 printf("no solvable exists with name %s\n", dep2str(pool, what));
2856 case SOLVER_INSTALL_SOLVABLE_PROVIDES:
2857 printf("no solvable provides %s\n", dep2str(pool, what));
2860 printf("unknown job\n");
2865 if (p > 0 && solv->learnt_pool.elements[idx + 1] == -p)
2867 /* we conflicted with a direct rpm assertion */
2868 /* print other rule */
2872 if (rn >= solv->jobrules)
2874 printf("some job/system/learnt rule\n");
2880 /* negative assertion, i.e. package is not installable */
2881 s = pool->solvables + (-p);
2884 reqp = s->repo->idarraydata + s->requires;
2885 while ((req = *reqp++) != 0)
2887 if (req == SOLVABLE_PREREQMARKER)
2889 dp = GET_PROVIDESP(req, p);
2892 printf("package %s-%s.%s requires %s, but no package provides it\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch), dep2str(pool, req));
2897 printf("package %s-%s.%s is not installable\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2901 if (rn >= solv->learntrules)
2903 /* learnt rule, ignore for now */
2904 printf("some learnt rule...\n");
2908 if (rn >= solv->systemrules)
2910 /* system rule, ignore for now */
2911 printf("some system rule...\n");
2915 if (rn >= solv->jobrules)
2917 /* job rule, ignore for now */
2918 printf("some job rule...\n");
2922 /* only rpm rules left... */
2927 if (d == 0 && r->w2 < 0)
2931 sp = pool->solvables + (-p);
2932 sd = pool->solvables + (-d);
2933 if (sp->name == sd->name)
2935 printf("cannot install both %s-%s.%s and %s-%s.%s\n", id2str(pool, sp->name), id2str(pool, sp->evr), id2str(pool, sp->arch), id2str(pool, sd->name), id2str(pool, sd->evr), id2str(pool, sd->arch));
2939 printconflicts(solv, pool->solvables + (-p), -d);
2940 printconflicts(solv, pool->solvables + (-d), -p);
2945 /* find requires of p that corresponds with our rule */
2947 s = pool->solvables + (-p);
2948 reqp = s->repo->idarraydata + s->requires;
2949 while ((req = *reqp++) != 0)
2951 if (req == SOLVABLE_PREREQMARKER)
2953 dp = GET_PROVIDESP(req, p);
2956 if (*dp == r->w2 && dp[1] == 0)
2959 else if (dp - pool->whatprovidesdata == d)
2964 printf("req not found\n");
2967 printf("package %s-%s.%s requires %s, but none of its providers can be installed\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch), dep2str(pool, req));
2972 printsolutions(Solver *solv, Queue *job)
2974 Pool *pool = solv->pool;
2977 Id problem, solution, element;
2980 printf("Encountered problems! Here are the solutions:\n\n");
2983 while ((problem = solver_next_problem(solv, problem)) != 0)
2985 printf("Problem %d:\n", pcnt++);
2986 printf("====================================\n");
2987 printprobleminfo(solv, job, problem);
2990 while ((solution = solver_next_solution(solv, problem, solution)) != 0)
2993 while ((element = solver_next_solutionelement(solv, problem, solution, element, &p, &rp)) != 0)
2997 /* job, rp is index into job queue */
2998 what = job->elements[rp];
2999 switch (job->elements[rp - 1])
3001 case SOLVER_INSTALL_SOLVABLE:
3002 s = pool->solvables + what;
3003 if (solv->installed && s->repo == solv->installed)
3004 printf("- do not keep %s-%s.%s installed\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
3006 printf("- do not install %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
3008 case SOLVER_ERASE_SOLVABLE:
3009 s = pool->solvables + what;
3010 if (solv->installed && s->repo == solv->installed)
3011 printf("- do not deinstall %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
3013 printf("- do not forbid installation of %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
3015 case SOLVER_INSTALL_SOLVABLE_NAME:
3016 printf("- do not install %s\n", id2str(pool, what));
3018 case SOLVER_ERASE_SOLVABLE_NAME:
3019 printf("- do not deinstall %s\n", id2str(pool, what));
3021 case SOLVER_INSTALL_SOLVABLE_PROVIDES:
3022 printf("- do not install a solvable providing %s\n", dep2str(pool, what));
3024 case SOLVER_ERASE_SOLVABLE_PROVIDES:
3025 printf("- do not deinstall all solvables providing %s\n", dep2str(pool, what));
3027 case SOLVER_INSTALL_SOLVABLE_UPDATE:
3028 s = pool->solvables + what;
3029 printf("- do not install most recent version of %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool
3033 printf("- do something different\n");
3039 /* policy, replace p with rp */
3040 s = pool->solvables + p;
3041 sd = rp ? pool->solvables + rp : 0;
3045 if (!solv->allowdowngrade && evrcmp(pool, s->evr, sd->evr) > 0)
3047 printf("- allow downgrade of %s-%s.%s to %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch), id2str(pool, sd->name), id2str(pool, sd->evr), id2str(pool, sd->arch));
3050 if (!solv->allowarchchange && s->name == sd->name && s->arch != sd->arch && policy_illegal_archchange(pool, s, sd))
3052 printf("- allow architecture change of %s-%s.%s to %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch), id2str(pool, sd->name), id2str(pool, sd->evr), id2str(pool, sd->arch));
3055 if (!solv->allowvendorchange && s->name == sd->name && s->vendor != sd->vendor && policy_illegal_vendorchange(pool, s, sd))
3058 printf("- allow vendor change from '%s' (%s-%s.%s) to '%s' (%s-%s.%s)\n", id2str(pool, s->vendor), id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch), id2str(pool, sd->vendor), id2str(pool, sd->name), id2str(pool, sd->evr), id2str(pool, sd->arch));
3060 printf("- allow vendor change from '%s' (%s-%s.%s) to no vendor (%s-%s.%s)\n", id2str(pool, s->vendor), id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch), id2str(pool, sd->name), id2str(pool, sd->evr), id2str(pool, sd->arch));
3064 printf("- allow replacement of %s-%s.%s with %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch), id2str(pool, sd->name), id2str(pool, sd->evr), id2str(pool, sd->arch));
3068 printf("- allow deinstallation of %s-%s.%s [%d]\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch), (Id)(s - pool->solvables));
3079 /* for each installed solvable find which packages with *different* names
3080 * obsolete the solvable.
3081 * this index is used in policy_findupdatepackages if noupdateprovide is set.
3085 create_obsolete_index(Solver *solv)
3087 Pool *pool = solv->pool;
3089 Repo *installed = solv->installed;
3090 Id p, *pp, obs, *obsp, *obsoletes, *obsoletes_data;
3093 if (!installed || !installed->nsolvables)
3095 /* create reverse obsoletes map for installed solvables */
3096 solv->obsoletes = obsoletes = xcalloc(installed->end - installed->start, sizeof(Id));
3097 for (i = 1; i < pool->nsolvables; i++)
3099 s = pool->solvables + i;
3100 if (s->repo == installed)
3104 if (!pool_installable(pool, s))
3106 obsp = s->repo->idarraydata + s->obsoletes;
3107 while ((obs = *obsp++) != 0)
3108 FOR_PROVIDES(p, pp, obs)
3110 if (pool->solvables[p].repo != installed)
3112 if (pool->solvables[p].name == s->name)
3114 obsoletes[p - installed->start]++;
3118 for (i = 0; i < installed->nsolvables; i++)
3121 n += obsoletes[i] + 1;
3124 solv->obsoletes_data = obsoletes_data = xcalloc(n + 1, sizeof(Id));
3125 if (pool->verbose) printf("obsoletes data: %d entries\n", n + 1);
3126 for (i = pool->nsolvables - 1; i > 0; i--)
3128 s = pool->solvables + i;
3129 if (s->repo == installed)
3133 if (!pool_installable(pool, s))
3135 obsp = s->repo->idarraydata + s->obsoletes;
3136 while ((obs = *obsp++) != 0)
3137 FOR_PROVIDES(p, pp, obs)
3139 if (pool->solvables[p].repo != installed)
3141 if (pool->solvables[p].name == s->name)
3143 p -= installed->start;
3144 if (obsoletes_data[obsoletes[p]] != i)
3145 obsoletes_data[--obsoletes[p]] = i;
3151 /*-----------------------------------------------------------------*/
3161 solve(Solver *solv, Queue *job)
3163 Pool *pool = solv->pool;
3164 Repo *installed = solv->installed;
3167 Map addedmap; /* '1' == have rule for solvable */
3168 Id how, what, p, *pp, d;
3172 /* create obsolete index if needed */
3173 if (solv->noupdateprovide)
3174 create_obsolete_index(solv);
3177 * create basic rule set of all involved packages
3178 * use addedmap bitmap to make sure we don't create rules twice
3182 map_init(&addedmap, pool->nsolvables);
3186 * always install our system solvable
3188 MAPSET(&addedmap, SYSTEMSOLVABLE);
3189 queue_push(&solv->decisionq, SYSTEMSOLVABLE);
3190 queue_push(&solv->decisionq_why, 0);
3191 solv->decisionmap[SYSTEMSOLVABLE] = 1;
3194 * create rules for all package that could be involved with the solving
3195 * so called: rpm rules
3200 oldnrules = solv->nrules;
3201 if (pool->verbose > 3)
3202 printf ("*** create rpm rules for installed solvables ***\n");
3203 for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
3204 if (s->repo == installed)
3205 addrpmrulesforsolvable(solv, s, &addedmap);
3207 printf("added %d rpm rules for installed solvables\n", solv->nrules - oldnrules);
3208 if (pool->verbose > 3)
3209 printf ("*** create rpm rules for updaters of installed solvables ***\n");
3210 oldnrules = solv->nrules;
3211 for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
3212 if (s->repo == installed)
3213 addrpmrulesforupdaters(solv, s, &addedmap, 1);
3215 printf("added %d rpm rules for updaters of installed solvables\n", solv->nrules - oldnrules);
3218 if (solv->pool->verbose > 3)
3219 printf ("*** create rpm rules for packages involved with a job ***\n");
3220 oldnrules = solv->nrules;
3221 for (i = 0; i < job->count; i += 2)
3223 how = job->elements[i];
3224 what = job->elements[i + 1];
3228 case SOLVER_INSTALL_SOLVABLE:
3229 addrpmrulesforsolvable(solv, pool->solvables + what, &addedmap);
3231 case SOLVER_INSTALL_SOLVABLE_NAME:
3232 case SOLVER_INSTALL_SOLVABLE_PROVIDES:
3233 FOR_PROVIDES(p, pp, what)
3235 /* if by name, ensure that the name matches */
3236 if (how == SOLVER_INSTALL_SOLVABLE_NAME && pool->solvables[p].name != what)
3238 addrpmrulesforsolvable(solv, pool->solvables + p, &addedmap);
3241 case SOLVER_INSTALL_SOLVABLE_UPDATE:
3242 /* dont allow downgrade */
3243 addrpmrulesforupdaters(solv, pool->solvables + what, &addedmap, 0);
3248 printf("added %d rpm rules for packages involved in a job\n", solv->nrules - oldnrules);
3250 if (solv->pool->verbose > 3)
3251 printf ("*** create rpm rules for recommended/suggested packages ***\n");
3253 oldnrules = solv->nrules;
3254 addrpmrulesforweak(solv, &addedmap);
3256 printf("added %d rpm rules because of weak dependencies\n", solv->nrules - oldnrules);
3261 int possible = 0, installable = 0;
3262 for (i = 1; i < pool->nsolvables; i++)
3264 if (pool_installable(pool, pool->solvables + i))
3266 if (MAPTST(&addedmap, i))
3269 printf("%d of %d installable solvables considered for solving\n", possible, installable);
3274 * first pass done, we now have all the rpm rules we need.
3275 * unify existing rules before going over all job rules and
3277 * at this point the system is always solvable,
3278 * as an empty system (remove all packages) is a valid solution
3281 unifyrules(solv); /* remove duplicate rpm rules */
3283 if (pool->verbose) printf("decisions so far: %d\n", solv->decisionq.count);
3284 if (pool->verbose > 3)
3285 printdecisions (solv);
3288 * now add all job rules
3291 if (solv->pool->verbose > 3)
3292 printf ("*** Add JOB rules ***\n");
3294 solv->jobrules = solv->nrules;
3296 for (i = 0; i < job->count; i += 2)
3298 how = job->elements[i];
3299 what = job->elements[i + 1];
3302 case SOLVER_INSTALL_SOLVABLE: /* install specific solvable */
3303 s = pool->solvables + what;
3305 printf("job: install solvable %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
3306 addrule(solv, what, 0); /* install by Id */
3307 queue_push(&solv->ruletojob, i);
3309 case SOLVER_ERASE_SOLVABLE:
3310 s = pool->solvables + what;
3312 printf("job: erase solvable %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
3313 addrule(solv, -what, 0); /* remove by Id */
3314 queue_push(&solv->ruletojob, i);
3316 case SOLVER_INSTALL_SOLVABLE_NAME: /* install by capability */
3317 case SOLVER_INSTALL_SOLVABLE_PROVIDES:
3318 if (pool->verbose && how == SOLVER_INSTALL_SOLVABLE_NAME)
3319 printf("job: install name %s\n", id2str(pool, what));
3320 if (pool->verbose && how == SOLVER_INSTALL_SOLVABLE_PROVIDES)
3321 printf("job: install provides %s\n", dep2str(pool, what));
3323 FOR_PROVIDES(p, pp, what)
3325 /* if by name, ensure that the name matches */
3326 if (how == SOLVER_INSTALL_SOLVABLE_NAME && pool->solvables[p].name != what)
3332 /* no provider, make this an impossible rule */
3333 queue_push(&q, -SYSTEMSOLVABLE);
3336 p = queue_shift(&q); /* get first provider */
3338 d = 0; /* single provider ? -> make assertion */
3340 d = pool_queuetowhatprovides(pool, &q); /* get all providers */
3341 addrule(solv, p, d); /* add 'requires' rule */
3342 queue_push(&solv->ruletojob, i);
3344 case SOLVER_ERASE_SOLVABLE_NAME: /* remove by capability */
3345 case SOLVER_ERASE_SOLVABLE_PROVIDES:
3346 if (pool->verbose && how == SOLVER_ERASE_SOLVABLE_NAME)
3347 printf("job: erase name %s\n", id2str(pool, what));
3348 if (pool->verbose && how == SOLVER_ERASE_SOLVABLE_PROVIDES)
3349 printf("job: erase provides %s\n", dep2str(pool, what));
3350 FOR_PROVIDES(p, pp, what)
3352 /* if by name, ensure that the name matches */
3353 if (how == SOLVER_ERASE_SOLVABLE_NAME && pool->solvables[p].name != what)
3355 addrule(solv, -p, 0); /* add 'remove' rule */
3356 queue_push(&solv->ruletojob, i);
3359 case SOLVER_INSTALL_SOLVABLE_UPDATE: /* find update for solvable */
3360 s = pool->solvables + what;
3362 printf("job: update %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
3363 addupdaterule(solv, s, 0);
3364 queue_push(&solv->ruletojob, i);
3369 if (solv->ruletojob.count != solv->nrules - solv->jobrules)
3373 * now add system rules
3377 if (solv->pool->verbose > 3)
3378 printf ("*** Add system rules ***\n");
3381 solv->systemrules = solv->nrules;
3384 * create rules for updating installed solvables
3388 if (installed && !solv->allowuninstall)
3389 { /* loop over all installed solvables */
3390 /* we create all update rules, but disable some later on depending on the job */
3391 for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
3392 if (s->repo == installed)
3393 addupdaterule(solv, s, 0); /* allowall = 0 */
3395 addupdaterule(solv, 0, 0); /* create dummy rule; allowall = 0 */
3396 /* consistency check: we added a rule for _every_ system solvable */
3397 if (solv->nrules - solv->systemrules != installed->end - installed->start)
3401 /* create special weak system rules */
3402 /* those are used later on to keep a version of the installed packages in
3404 if (installed && installed->nsolvables)
3406 solv->weaksystemrules = xcalloc(installed->end - installed->start, sizeof(Id));
3407 for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
3408 if (s->repo == installed)
3410 policy_findupdatepackages(solv, s, &q, 1);
3412 solv->weaksystemrules[i - installed->start] = pool_queuetowhatprovides(pool, &q);
3416 /* free unneeded memory */
3417 map_free(&addedmap);
3420 solv->weakrules = solv->nrules;
3422 /* try real hard to keep packages installed */
3425 for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
3426 if (s->repo == installed)
3428 /* FIXME: can't work with refine_suggestion! */
3429 /* need to always add the rule but disable it */
3430 if (MAPTST(&solv->noupdate, i - installed->start))
3432 d = solv->weaksystemrules[i - installed->start];
3433 addrule(solv, i, d);
3437 /* all new rules are learnt after this point */
3438 solv->learntrules = solv->nrules;
3445 disableupdaterules(solv, job, -1);
3446 makeruledecisions(solv);
3448 if (pool->verbose) printf("problems so far: %d\n", solv->problems.count);
3450 run_solver(solv, 1, 1);
3452 /* find suggested packages */
3453 if (!solv->problems.count)
3455 Id sug, *sugp, p, *pp;
3457 /* create map of all suggests that are still open */
3458 solv->recommends_index = -1;
3459 MAPZERO(&solv->suggestsmap);
3460 for (i = 0; i < solv->decisionq.count; i++)
3462 p = solv->decisionq.elements[i];
3465 s = pool->solvables + p;
3468 sugp = s->repo->idarraydata + s->suggests;
3469 while ((sug = *sugp++) != 0)
3471 FOR_PROVIDES(p, pp, sug)
3472 if (solv->decisionmap[p] > 0)
3475 continue; /* already fulfilled */
3476 FOR_PROVIDES(p, pp, sug)
3477 MAPSET(&solv->suggestsmap, p);
3481 for (i = 1; i < pool->nsolvables; i++)
3483 if (solv->decisionmap[i] != 0)
3485 s = pool->solvables + i;
3486 if (!MAPTST(&solv->suggestsmap, i))
3490 if (!pool_installable(pool, s))
3492 if (!solver_is_enhancing(solv, s))
3495 queue_push(&solv->suggestions, i);
3497 policy_filter_unwanted(solv, &solv->suggestions, 0, POLICY_MODE_SUGGEST);
3500 if (solv->problems.count)
3501 problems_to_solutions(solv, job);