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 (!dep_installed(solv, rd->name))
45 return dep_installed(solv, rd->evr);
47 if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
48 return dep_installed(solv, rd->evr);
50 FOR_PROVIDES(p, pp, dep)
52 if (p >= solv->installed->start && p < solv->installed->start + solv->installed->nsolvables)
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]);
120 printf(" (disabled)");
130 printrule(Solver *solv, Rule *r)
135 if (r >= solv->rules && r < solv->rules + solv->nrules) /* r is a solver rule */
136 printf("Rule #%d:\n", (int)(r - solv->rules));
138 printf("Rule:\n"); /* r is any rule */
143 else if (r->d == ID_NULL)
150 v = solv->pool->whatprovidesdata[r->d + i - 1];
153 printruleelement(solv, r, v);
155 printf(" next: %d %d\n", r->n1, r->n2);
159 /*-----------------------------------------------------------------*/
165 static Pool *unifyrules_sortcmp_data;
168 * compare rules for unification sort
172 unifyrules_sortcmp(const void *ap, const void *bp)
174 Pool *pool = unifyrules_sortcmp_data;
175 Rule *a = (Rule *)ap;
176 Rule *b = (Rule *)bp;
182 return x; /* p differs */
185 if (a->d == 0 && b->d == 0)
186 return a->w2 - b->w2; /* assertion: return w2 diff */
188 if (a->d == 0) /* a is assertion, b not */
190 x = a->w2 - pool->whatprovidesdata[b->d];
194 if (b->d == 0) /* b is assertion, a not */
196 x = pool->whatprovidesdata[a->d] - b->w2;
200 /* compare whatprovidesdata */
201 ad = pool->whatprovidesdata + a->d;
202 bd = pool->whatprovidesdata + b->d;
204 if ((x = *ad++ - *bd++) != 0)
215 unifyrules(Solver *solv)
220 if (solv->nrules <= 1) /* nothing to unify */
223 if (solv->pool->verbose > 3)
224 printf ("----- unifyrules -----\n");
226 /* sort rules first */
227 unifyrules_sortcmp_data = solv->pool;
228 qsort(solv->rules + 1, solv->nrules - 1, sizeof(Rule), unifyrules_sortcmp);
235 for (i = j = 1, ir = solv->rules + 1; i < solv->nrules; i++, ir++)
237 if (jr && !unifyrules_sortcmp(ir, jr))
238 continue; /* prune! */
239 jr = solv->rules + j++; /* keep! */
244 /* reduced count from nrules to j rules */
245 if (solv->pool->verbose) printf("pruned rules from %d to %d\n", solv->nrules, j);
247 /* adapt rule buffer */
248 solv->rules = (Rule *)xrealloc(solv->rules, ((solv->nrules + RULES_BLOCK) & ~RULES_BLOCK) * sizeof(Rule));
251 if (solv->pool->verbose)
258 for (i = 1; i < solv->nrules; i++)
265 dp = solv->pool->whatprovidesdata + r->d;
270 printf(" binary: %d\n", binr);
271 printf(" normal: %d, %d literals\n", solv->nrules - 1 - binr, lits);
274 if (solv->pool->verbose > 3)
275 printf ("----- unifyrules end -----\n");
285 hashrule(Solver *solv, Id p, Id d, int n)
287 unsigned int x = (unsigned int)p;
291 return (x * 37) ^ (unsigned int)d;
292 dp = solv->pool->whatprovidesdata + d;
294 x = (x * 37) ^ (unsigned int)*dp++;
302 * p = direct literal; > 0 for learnt, < 0 for installed pkg (rpm)
303 * d, if < 0 direct literal, if > 0 offset into whatprovides, if == 0 rule is assertion (look at p only)
306 * A requires b, b provided by B1,B2,B3 => (-A|B1|B2|B3)
308 * p < 0 : rule from rpm (installed pkg)
309 * d > 0 : Offset in whatprovidesdata (list of providers)
311 * A conflicts b, b provided by B1,B2,B3 => (-A|-B1), (-A|-B2), (-A|-B3)
312 * d < 0: Id of solvable (e.g. B1)
314 * d == 0: unary rule, assertion => (A) or (-A)
316 * Install: p > 0, d = 0 (A) user requested install
317 * Remove: p < 0, d = 0 (-A) user requested remove
318 * Requires: p < 0, d > 0 (-A|B1|B2|...) d: <list of providers for requirement of p>
319 * Updates: p > 0, d > 0 (A|B1|B2|...) d: <list of updates for solvable p>
320 * Conflicts: p < 0, d < 0 (-A|-B) either p (conflict issuer) or d (conflict provider)
321 * ? p > 0, d < 0 (A|-B)
322 * No-op ?: p = 0, d = 0 (null) (used as policy rule placeholder)
326 addrule(Solver *solv, Id p, Id d)
331 int n = 0; /* number of literals in rule - 1
332 0 = direct assertion (single literal)
336 /* it often happenes that requires lead to adding the same rpm rule
337 * multiple times, so we prune those duplicates right away to make
338 * the work for unifyrules a bit easier */
340 if (solv->nrules && !solv->jobrules)
342 r = solv->rules + solv->nrules - 1; /* get the last added rule */
343 if (r->p == p && r->d == d && d != 0) /* identical and not user requested */
350 return 0; /* ignore self conflict */
353 else if (d == 0) /* user requested */
357 for (dp = solv->pool->whatprovidesdata + d; *dp; dp++, n++)
359 return 0; /* rule is self-fulfilling */
364 if (n == 0) /* direct assertion */
368 /* this is a rpm rule assertion, we do not have to allocate it */
369 /* it can be identified by a level of 1 and a zero reason */
370 /* we must not drop those rules from the decisionq when rewinding! */
373 if (solv->decisionmap[-p] > 0 || solv->decisionmap[-p] < -1)
375 if (solv->decisionmap[-p])
377 queue_push(&solv->decisionq, p);
378 queue_push(&solv->decisionq_why, 0);
379 solv->decisionmap[-p] = -1;
383 else if (n == 1 && p > d)
385 /* smallest literal first so we can find dups */
389 n = 1; /* re-set n, was used as temp var */
392 /* check if the last added rule is exactly the same as what we're looking for. */
393 if (r && n == 1 && !r->d && r->p == p && r->w2 == d)
396 if (r && n > 1 && r->d && r->p == p)
401 dp2 = solv->pool->whatprovidesdata + r->d;
402 for (dp = solv->pool->whatprovidesdata + d; *dp; dp++, dp2++)
413 /* check and extend rule buffer */
414 if ((solv->nrules & RULES_BLOCK) == 0)
416 solv->rules = (Rule *)xrealloc(solv->rules, (solv->nrules + (RULES_BLOCK + 1)) * sizeof(Rule));
419 r = solv->rules + solv->nrules++; /* point to rule space */
424 /* direct assertion, no watch needed */
440 r->w2 = solv->pool->whatprovidesdata[d];
445 if (solv->pool->verbose > 3)
447 printf (" Add rule: ");
455 disablerule(Solver *solv, Rule *r)
461 enablerule(Solver *solv, Rule *r)
463 if (r->d == 0 || r->w2 != r->p)
466 r->w1 = solv->pool->whatprovidesdata[r->d];
470 /**********************************************************************************/
472 /* a problem is an item on the solver's problem list. It can either be >0, in that
473 * case it is a system (upgrade) rule, or it can be <0, which makes it refer to a job
474 * consisting of multiple job rules.
478 disableproblem(Solver *solv, Id v)
486 disablerule(solv, solv->rules + v);
490 jp = solv->ruletojob.elements;
491 for (i = solv->jobrules, r = solv->rules + i; i < solv->systemrules; i++, r++, jp++)
493 disablerule(solv, r);
497 enableproblem(Solver *solv, Id v)
505 enablerule(solv, solv->rules + v);
509 jp = solv->ruletojob.elements;
510 for (i = solv->jobrules, r = solv->rules + i; i < solv->systemrules; i++, r++, jp++)
516 printproblem(Solver *solv, Id v)
523 printrule(solv, solv->rules + v);
527 printf("JOB %d\n", v);
528 jp = solv->ruletojob.elements;
529 for (i = solv->jobrules, r = solv->rules + i; i < solv->systemrules; i++, r++, jp++)
540 /**********************************************************************************/
542 /* go through system and job rules and add direct assertions
543 * to the decisionqueue. If we find a conflict, disable rules and
544 * add them to problem queue.
547 makeruledecisions(Solver *solv)
554 /* no learnt rules for now */
555 if (solv->learntrules && solv->learntrules != solv->nrules)
558 decisionstart = solv->decisionq.count;
559 /* the loop is over jobrules, system rules and weak rules */
560 for (ri = solv->jobrules, r = solv->rules + ri; ri < solv->nrules; ri++, r++)
566 if (solv->decisionmap[vv] == 0)
568 queue_push(&solv->decisionq, v);
569 queue_push(&solv->decisionq_why, r - solv->rules);
570 solv->decisionmap[vv] = v > 0 ? 1 : -1;
573 if (v > 0 && solv->decisionmap[vv] > 0)
575 if (v < 0 && solv->decisionmap[vv] < 0)
577 /* found a conflict! */
578 /* if we are weak, just disable ourself */
579 if (ri >= solv->weakrules)
581 printf("conflict, but I am weak, disabling ");
586 /* only job and system rules left */
587 for (i = 0; i < solv->decisionq.count; i++)
588 if (solv->decisionq.elements[i] == -v)
590 if (i == solv->decisionq.count)
592 if (solv->decisionq_why.elements[i] == 0)
594 /* conflict with rpm rule, need only disable our rule */
595 printf("conflict with rpm rule, disabling rule #%d\n", ri);
596 if (v < 0 && v != -SYSTEMSOLVABLE)
598 queue_push(&solv->problems, 0);
599 if (v == -SYSTEMSOLVABLE)
600 queue_push(&solv->problems, 0); /* sigh, we don't have a rule for that */
602 queue_push(&solv->problems, -v); /* sigh, we don't have a rule for that */
604 if (ri < solv->systemrules)
605 v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
606 queue_push(&solv->problems, v);
607 disableproblem(solv, v);
608 queue_push(&solv->problems, 0);
611 /* conflict with another job or system rule */
612 /* remove old decision */
613 printf("conflicting system/job rules over literal %d\n", vv);
614 queue_push(&solv->problems, 0);
615 queue_push(&solv->problems, solv->decisionq_why.elements[i]);
616 /* push all of our rules asserting this literal on the problem stack */
617 for (i = solv->jobrules, rr = solv->rules + i; i < solv->nrules; i++, rr++)
619 if (!rr->w1 || rr->w2)
621 if (rr->p != v && rr->p != -v)
623 printf(" - disabling rule #%d\n", i);
625 if (i < solv->systemrules)
626 v = -(solv->ruletojob.elements[i - solv->jobrules] + 1);
627 queue_push(&solv->problems, v);
628 disableproblem(solv, v);
630 queue_push(&solv->problems, 0);
633 while (solv->decisionq.count > decisionstart)
635 v = solv->decisionq.elements[--solv->decisionq.count];
636 --solv->decisionq_why.count;
638 solv->decisionmap[vv] = 0;
640 ri = solv->jobrules - 1;
641 r = solv->rules + ri;
646 /* FIXME: bad code ahead, replace as soon as possible */
648 disableupdaterules(Solver *solv, Queue *job, int jobidx)
650 Pool *pool = solv->pool;
652 Id how, what, p, *pp;
658 installed = solv->installed;
664 how = job->elements[jobidx];
667 case SOLVER_INSTALL_SOLVABLE:
668 case SOLVER_ERASE_SOLVABLE:
669 case SOLVER_ERASE_SOLVABLE_NAME:
670 case SOLVER_ERASE_SOLVABLE_PROVIDES:
676 /* go through all enabled job rules */
677 MAPZERO(&solv->noupdate);
678 for (i = solv->jobrules; i < solv->systemrules; i++)
681 if (!r->w1) /* disabled? */
683 j = solv->ruletojob.elements[i - solv->jobrules];
687 how = job->elements[j];
688 what = job->elements[j + 1];
691 case SOLVER_INSTALL_SOLVABLE: /* install specific solvable */
692 s = pool->solvables + what;
693 FOR_PROVIDES(p, pp, s->name)
695 if (pool->solvables[p].name != s->name)
697 if (p >= installed->start && p < installed->start + installed->nsolvables)
698 MAPSET(&solv->noupdate, p - installed->start);
701 case SOLVER_ERASE_SOLVABLE:
702 if (what >= installed->start && what < installed->start + installed->nsolvables)
703 MAPSET(&solv->noupdate, what - installed->start);
705 case SOLVER_ERASE_SOLVABLE_NAME: /* remove by capability */
706 case SOLVER_ERASE_SOLVABLE_PROVIDES:
707 FOR_PROVIDES(p, pp, what)
709 if (how == SOLVER_ERASE_SOLVABLE_NAME && pool->solvables[p].name != what)
711 if (p >= installed->start && p < installed->start + installed->nsolvables)
712 MAPSET(&solv->noupdate, p - installed->start);
720 /* fixup update rule status */
721 if (solv->allowuninstall)
722 return; /* no update rules at all */
726 /* re just disabled job #jobidx. enable all update rules
727 * that aren't disabled by the remaining job rules */
728 how = job->elements[jobidx];
729 what = job->elements[jobidx + 1];
732 case SOLVER_INSTALL_SOLVABLE:
733 s = pool->solvables + what;
734 FOR_PROVIDES(p, pp, s->name)
736 if (pool->solvables[p].name != s->name)
738 if (p < installed->start || p >= installed->start + installed->nsolvables)
740 if (MAPTST(&solv->noupdate, p - installed->start))
742 r = solv->rules + solv->systemrules + (p - installed->start);
745 if (r->d == 0 || r->w2 != r->p)
748 r->w1 = solv->pool->whatprovidesdata[r->d];
751 printf("@@@ re-enabling ");
756 case SOLVER_ERASE_SOLVABLE:
757 if (what < installed->start || what >= installed->start + installed->nsolvables)
759 if (MAPTST(&solv->noupdate, what - installed->start))
761 r = solv->rules + solv->systemrules + (what - installed->start);
764 if (r->d == 0 || r->w2 != r->p)
767 r->w1 = solv->pool->whatprovidesdata[r->d];
770 printf("@@@ re-enabling ");
774 case SOLVER_ERASE_SOLVABLE_NAME: /* remove by capability */
775 case SOLVER_ERASE_SOLVABLE_PROVIDES:
776 FOR_PROVIDES(p, pp, what)
778 if (how == SOLVER_ERASE_SOLVABLE_NAME && pool->solvables[p].name != what)
780 if (p < installed->start || p >= installed->start + installed->nsolvables)
782 if (MAPTST(&solv->noupdate, p - installed->start))
784 r = solv->rules + solv->systemrules + (p - installed->start);
787 if (r->d == 0 || r->w2 != r->p)
790 r->w1 = solv->pool->whatprovidesdata[r->d];
793 printf("@@@ re-enabling ");
804 for (i = 0; i < installed->nsolvables; i++)
806 r = solv->rules + solv->systemrules + i;
807 if (r->w1 && MAPTST(&solv->noupdate, i))
808 r->w1 = 0; /* was enabled, need to disable */
814 * add (install) rules for solvable
815 * for unfulfilled requirements, conflicts, obsoletes,....
816 * "unflag" a resolvable if it is not installable via "addrule(solv, -n, 0)"
820 addrpmrulesforsolvable(Solver *solv, Solvable *s, Map *m)
822 Pool *pool = solv->pool;
823 Repo *installed = solv->installed;
837 if (solv->pool->verbose > 3)
838 printf ("----- addrpmrulesforsolvable -----\n");
840 queue_init_buffer(&q, qbuf, sizeof(qbuf)/sizeof(*qbuf));
841 queue_push(&q, s - pool->solvables); /* push solvable Id */
847 * s: Pointer to solvable
851 if (MAPTST(m, n)) /* continue if already done */
855 s = pool->solvables + n; /* s = Solvable in question */
858 if (installed /* Installed system available */
859 && !solv->fixsystem /* NOT repair errors in rpm dependency graph */
860 && n >= installed->start /* is it installed? */
861 && n < installed->start + installed->nsolvables)
863 dontfix = 1; /* dont care about broken rpm deps */
866 /*-----------------------------------------
867 * check requires of s
872 reqp = s->repo->idarraydata + s->requires;
873 while ((req = *reqp++) != 0) /* go throw all requires */
875 if (req == SOLVABLE_PREREQMARKER) /* skip the marker */
878 dp = GET_PROVIDESP(req, p); /* get providers of req; p is a dummy only */
880 if (*dp == SYSTEMSOLVABLE) /* always installed */
885 /* the strategy here is to not insist on dependencies
886 * that are already broken. so if we find one provider
887 * that was already installed, we know that the
888 * dependency was not broken before so we enforce it */
889 for (i = 0; dp[i]; i++) /* for all providers */
891 if (dp[i] >= installed->start && dp[i] < installed->start + installed->nsolvables)
892 break; /* provider was installed */
894 if (!dp[i]) /* previously broken dependency */
897 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));
904 /* nothing provides req! */
906 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));
907 addrule(solv, -n, 0); /* mark requestor as uninstallable */
909 printf(">!> !unflag %s-%s.%s[%s]\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch), repo_name(s->repo));
913 if (pool->verbose > 2)
915 printf(" %s-%s.%s requires %s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch), dep2str(pool, req));
916 for (i = 0; dp[i]; i++)
917 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));
920 /* add 'requires' dependency */
921 /* rule: (-requestor|provider1|provider2|...|providerN) */
922 addrule(solv, -n, dp - pool->whatprovidesdata);
924 /* descend the dependency tree */
925 for (; *dp; dp++) /* loop through all providers */
931 } /* while, requirements of n */
933 } /* if, requirements */
936 /*-----------------------------------------
937 * check conflicts of s
942 conp = s->repo->idarraydata + s->conflicts;
943 while ((con = *conp++) != 0)
945 FOR_PROVIDES(p, pp, con)
947 /* dontfix: dont care about conflicts with already installed packs */
948 if (dontfix && p >= installed->start && p < installed->start + installed->nsolvables)
950 /* rule: -n|-p: either solvable _or_ provider of conflict */
951 addrule(solv, -n, -p);
956 /*-----------------------------------------
957 * check obsoletes if not installed
959 if (!installed || n < installed->start || n >= (installed->start + installed->nsolvables))
960 { /* not installed */
963 obsp = s->repo->idarraydata + s->obsoletes;
964 while ((obs = *obsp++) != 0)
966 FOR_PROVIDES(p, pp, obs)
967 addrule(solv, -n, -p);
970 FOR_PROVIDES(p, pp, s->name)
972 if (s->name == pool->solvables[p].name)
973 addrule(solv, -n, -p);
977 /*-----------------------------------------
978 * add recommends to the rule list
982 recp = s->repo->idarraydata + s->recommends;
983 while ((rec = *recp++) != 0)
985 FOR_PROVIDES(p, pp, rec)
992 sugp = s->repo->idarraydata + s->suggests;
993 while ((sug = *sugp++) != 0)
995 FOR_PROVIDES(p, pp, sug)
1005 addrpmrulesforweak(Solver *solv, Map *m)
1007 Pool *pool = solv->pool;
1012 if (pool->verbose) printf("----- addrpmrulesforweak ----- (nrules %d)\n", solv->nrules);
1013 for (i = n = 1; n < pool->nsolvables; i++, n++)
1015 if (i == pool->nsolvables)
1019 s = pool->solvables + i;
1020 if (!pool_installable(pool, s))
1025 supp = s->repo->idarraydata + s->supplements;
1026 while ((sup = *supp++) != ID_NULL)
1027 if (dep_possible(solv, sup, m))
1030 if (!sup && s->freshens)
1032 supp = s->repo->idarraydata + s->freshens;
1033 while ((sup = *supp++) != ID_NULL)
1034 if (dep_possible(solv, sup, m))
1037 if (!sup && s->enhances)
1039 supp = s->repo->idarraydata + s->enhances;
1040 while ((sup = *supp++) != ID_NULL)
1041 if (dep_possible(solv, sup, m))
1046 addrpmrulesforsolvable(solv, s, m);
1049 if (pool->verbose) printf("----- addrpmrulesforweak ----- done. (nrules%d)\n", solv->nrules);
1053 addrpmrulesforupdaters(Solver *solv, Solvable *s, Map *m, int allowall)
1055 Pool *pool = solv->pool;
1060 if (solv->pool->verbose > 3)
1061 printf ("----- addrpmrulesforupdaters -----\n");
1063 queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
1064 policy_findupdatepackages(solv, s, &qs, allowall);
1065 if (!MAPTST(m, s - pool->solvables)) /* add rule for s if not already done */
1066 addrpmrulesforsolvable(solv, s, m);
1067 for (i = 0; i < qs.count; i++)
1068 if (!MAPTST(m, qs.elements[i]))
1069 addrpmrulesforsolvable(solv, pool->solvables + qs.elements[i], m);
1074 * add rule for update
1075 * (A|A1|A2|A3...) An = update candidates for A
1077 * s = (installed) solvable
1081 addupdaterule(Solver *solv, Solvable *s, int allowall)
1083 /* installed packages get a special upgrade allowed rule */
1084 Pool *pool = solv->pool;
1089 if (solv->pool->verbose > 3)
1090 printf ("----- addupdaterule -----\n");
1092 queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
1093 policy_findupdatepackages(solv, s, &qs, allowall);
1094 if (qs.count == 0) /* no updaters found */
1097 d = pool_queuetowhatprovides(pool, &qs); /* intern computed queue */
1099 addrule(solv, s - pool->solvables, d); /* allow update of s */
1103 /*-----------------------------------------------------------------*/
1110 * initial setup for all watches
1114 makewatches(Solver *solv)
1118 int nsolvables = solv->pool->nsolvables;
1120 xfree(solv->watches);
1121 /* lower half for removals, upper half for installs */
1122 solv->watches = (Id *)xcalloc(2 * nsolvables, sizeof(Id));
1124 /* do it reverse so rpm rules get triggered first */
1125 for (i = 1, r = solv->rules + solv->nrules - 1; i < solv->nrules; i++, r--)
1127 for (i = 1, r = solv->rules + 1; i < solv->nrules; i++, r++)
1130 if (!r->w1 /* rule is disabled */
1131 || !r->w2) /* rule is assertion */
1134 /* see addwatches(solv, r) */
1135 r->n1 = solv->watches[nsolvables + r->w1];
1136 solv->watches[nsolvables + r->w1] = r - solv->rules;
1138 r->n2 = solv->watches[nsolvables + r->w2];
1139 solv->watches[nsolvables + r->w2] = r - solv->rules;
1145 * add watches (for rule)
1149 addwatches(Solver *solv, Rule *r)
1151 int nsolvables = solv->pool->nsolvables;
1153 r->n1 = solv->watches[nsolvables + r->w1];
1154 solv->watches[nsolvables + r->w1] = r - solv->rules;
1156 r->n2 = solv->watches[nsolvables + r->w2];
1157 solv->watches[nsolvables + r->w2] = r - solv->rules;
1161 /*-----------------------------------------------------------------*/
1162 /* rule propagation */
1164 #define DECISIONMAP_TRUE(p) ((p) > 0 ? (decisionmap[p] > 0) : (decisionmap[-p] < 0))
1169 * propagate decision to all rules
1173 propagate(Solver *solv, int level)
1175 Pool *pool = solv->pool;
1180 Id *decisionmap = solv->decisionmap;
1181 Id *watches = solv->watches + pool->nsolvables;
1183 while (solv->propagate_index < solv->decisionq.count)
1185 /* negate because our watches trigger if literal goes FALSE */
1186 pkg = -solv->decisionq.elements[solv->propagate_index++];
1187 if (pool->verbose > 3)
1189 printf("popagate for decision %d level %d\n", -pkg, level);
1190 printruleelement(solv, 0, -pkg);
1193 for (rp = watches + pkg; *rp; rp = nrp)
1195 r = solv->rules + *rp;
1197 if (pool->verbose > 3)
1199 printf(" watch triggered ");
1213 /* if clause is TRUE, nothing to do */
1214 if (DECISIONMAP_TRUE(ow))
1219 /* not a binary clause, check if we need to move our watch */
1220 if (r->p && r->p != ow && !DECISIONMAP_TRUE(-r->p))
1223 for (dp = pool->whatprovidesdata + r->d; (p = *dp++) != 0;)
1224 if (p != ow && !DECISIONMAP_TRUE(-p))
1228 /* p is free to watch, move watch to p */
1229 if (pool->verbose > 3)
1232 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));
1234 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));
1248 watches[p] = r - solv->rules;
1252 /* unit clause found, set other watch to TRUE */
1253 if (DECISIONMAP_TRUE(-ow))
1254 return r; /* eek, a conflict! */
1255 if (pool->verbose > 2)
1261 decisionmap[ow] = level;
1263 decisionmap[-ow] = -level;
1264 queue_push(&solv->decisionq, ow);
1265 queue_push(&solv->decisionq_why, r - solv->rules);
1266 if (pool->verbose > 3)
1268 Solvable *s = pool->solvables + (ow > 0 ? ow : -ow);
1270 printf(" -> decided to install %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
1272 printf(" -> decided to conflict %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
1276 return 0; /* all is well */
1280 /*-----------------------------------------------------------------*/
1289 analyze(Solver *solv, int level, Rule *c, int *pr, int *dr, int *why)
1291 Pool *pool = solv->pool;
1294 Map seen; /* global? */
1298 int learnt_why = solv->learnt_pool.count;
1299 Id *decisionmap = solv->decisionmap;
1303 if (pool->verbose > 1) printf("ANALYZE at %d ----------------------\n", level);
1304 map_init(&seen, pool->nsolvables);
1305 idx = solv->decisionq.count;
1308 if (pool->verbose > 1) printrule(solv, c);
1309 queue_push(&solv->learnt_pool, c - solv->rules);
1310 dp = c->d ? pool->whatprovidesdata + c->d : 0;
1321 if (DECISIONMAP_TRUE(v)) /* the one true literal */
1323 vv = v > 0 ? v : -v;
1324 if (MAPTST(&seen, vv))
1326 l = solv->decisionmap[vv];
1333 for (j = 0; j < solv->decisionq.count; j++)
1334 if (solv->decisionq.elements[j] == v)
1336 if (j == solv->decisionq.count)
1338 queue_push(&rulq, -(j + 1));
1340 continue; /* initial setting */
1344 num++; /* need to do this one as well */
1348 if (pool->verbose > 3)
1350 printf("PUSH %d ", v);
1351 printruleelement(solv, 0, v);
1357 if (pool->verbose > 3)
1358 printf("num = %d\n", num);
1363 v = solv->decisionq.elements[--idx];
1364 vv = v > 0 ? v : -v;
1365 if (MAPTST(&seen, vv))
1368 c = solv->rules + solv->decisionq_why.elements[idx];
1376 else if (r.count == 1 && r.elements[0] < 0)
1377 *dr = r.elements[0];
1379 *dr = pool_queuetowhatprovides(pool, &r);
1380 if (pool->verbose > 1)
1382 printf("learned rule for level %d (am %d)\n", rlevel, level);
1383 printruleelement(solv, 0, -v);
1384 for (i = 0; i < r.count; i++)
1387 printruleelement(solv, 0, v);
1391 queue_push(&solv->learnt_pool, 0);
1392 if (pool->verbose > 3)
1394 for (i = learnt_why; solv->learnt_pool.elements[i]; i++)
1396 printf("learnt_why ");
1397 printrule(solv, solv->rules + solv->learnt_pool.elements[i]);
1408 * reset the solver decisions to right after the rpm rules.
1409 * called after rules have been enabled/disabled
1413 reset_solver(Solver *solv)
1418 /* delete all learnt rules */
1419 solv->nrules = solv->learntrules;
1420 queue_empty(&solv->learnt_why);
1421 queue_empty(&solv->learnt_pool);
1423 /* redo all direct rpm rule decisions */
1424 /* we break at the first decision with a why attached, this is
1425 * either a job/system rule assertion or a propagated decision */
1426 for (i = 0; i < solv->decisionq.count; i++)
1428 v = solv->decisionq.elements[i];
1429 solv->decisionmap[v > 0 ? v : -v] = 0;
1431 for (i = 0; i < solv->decisionq_why.count; i++)
1432 if (solv->decisionq_why.elements[i])
1436 v = solv->decisionq.elements[i];
1437 solv->decisionmap[v > 0 ? v : -v] = v > 0 ? 1 : -1;
1440 if (solv->pool->verbose > 1)
1441 printf("decisions done reduced from %d to %d\n", solv->decisionq.count, i);
1443 solv->decisionq_why.count = i;
1444 solv->decisionq.count = i;
1445 solv->recommends_index = -1;
1446 solv->propagate_index = 0;
1448 /* redo all job/system decisions */
1449 makeruledecisions(solv);
1450 if (solv->pool->verbose > 1)
1451 printf("decisions after adding job and system rules: %d\n", solv->decisionq.count);
1452 /* recreate watches */
1458 * analyze_unsolvable_rule
1462 analyze_unsolvable_rule(Solver *solv, Rule *r)
1465 Id why = r - solv->rules;
1466 if (solv->pool->verbose > 1)
1468 if (why >= solv->jobrules && why < solv->systemrules)
1470 if (why >= solv->systemrules && why < solv->weakrules)
1471 printf("SYSTEM %d ", why - solv->systemrules);
1472 if (why >= solv->weakrules && why < solv->learntrules)
1474 if (solv->learntrules && why >= solv->learntrules)
1478 if (solv->learntrules && why >= solv->learntrules)
1480 for (i = solv->learnt_why.elements[why - solv->learntrules]; solv->learnt_pool.elements[i]; i++)
1481 analyze_unsolvable_rule(solv, solv->rules + solv->learnt_pool.elements[i]);
1484 /* do not add rpm rules to problem */
1485 if (why < solv->jobrules)
1487 /* turn rule into problem */
1488 if (why >= solv->jobrules && why < solv->systemrules)
1489 why = -(solv->ruletojob.elements[why - solv->jobrules] + 1);
1490 /* return if problem already countains our rule */
1491 if (solv->problems.count)
1493 for (i = solv->problems.count - 1; i >= 0; i--)
1494 if (solv->problems.elements[i] == 0) /* end of last problem reached? */
1496 else if (solv->problems.elements[i] == why)
1499 queue_push(&solv->problems, why);
1504 * analyze_unsolvable
1506 * return: 1 - disabled some rules, try again
1511 analyze_unsolvable(Solver *solv, Rule *cr, int disablerules)
1513 Pool *pool = solv->pool;
1515 Map seen; /* global to speed things up? */
1518 Id *decisionmap = solv->decisionmap;
1519 int oldproblemcount;
1522 if (pool->verbose > 1)
1523 printf("ANALYZE UNSOLVABLE ----------------------\n");
1524 oldproblemcount = solv->problems.count;
1526 /* make room for conflicting rule */
1527 queue_push(&solv->problems, 0);
1528 queue_push(&solv->problems, 0);
1531 map_init(&seen, pool->nsolvables);
1532 analyze_unsolvable_rule(solv, r);
1533 dp = r->d ? pool->whatprovidesdata + r->d : 0;
1544 if (DECISIONMAP_TRUE(v)) /* the one true literal */
1546 vv = v > 0 ? v : -v;
1547 l = solv->decisionmap[vv];
1552 idx = solv->decisionq.count;
1555 v = solv->decisionq.elements[--idx];
1556 vv = v > 0 ? v : -v;
1557 if (!MAPTST(&seen, vv))
1559 why = solv->decisionq_why.elements[idx];
1562 if (pool->verbose > 3)
1565 printruleelement(solv, 0, v);
1569 r = solv->rules + why;
1570 analyze_unsolvable_rule(solv, r);
1571 dp = r->d ? pool->whatprovidesdata + r->d : 0;
1582 if (DECISIONMAP_TRUE(v)) /* the one true literal */
1584 vv = v > 0 ? v : -v;
1585 l = solv->decisionmap[vv];
1592 queue_push(&solv->problems, 0); /* mark end of this problem */
1595 if (solv->weakrules != solv->learntrules)
1597 for (i = oldproblemcount + 2; i < solv->problems.count - 1; i++)
1599 why = solv->problems.elements[i];
1600 if (why < solv->weakrules || why >= solv->learntrules)
1602 if (!lastweak || lastweak < why)
1608 /* disable last weak rule */
1609 solv->problems.count = oldproblemcount;
1610 r = solv->rules + lastweak;
1611 printf("disabling weak ");
1618 /* patch conflicting rule data */
1619 if (cr - solv->rules >= solv->learntrules)
1621 /* we have to store the rule internals for learnt rules
1622 * as they get freed for every solver run */
1623 solv->problems.elements[oldproblemcount] = cr->p;
1624 solv->problems.elements[oldproblemcount + 1] = cr->d;
1627 solv->problems.elements[oldproblemcount + 1] = cr - solv->rules;
1631 for (i = oldproblemcount + 2; i < solv->problems.count - 1; i++)
1632 disableproblem(solv, solv->problems.elements[i]);
1637 printf("UNSOLVABLE\n");
1642 /*-----------------------------------------------------------------*/
1643 /* Decision revert */
1647 * revert decision at level
1651 revert(Solver *solv, int level)
1654 while (solv->decisionq.count)
1656 v = solv->decisionq.elements[solv->decisionq.count - 1];
1657 vv = v > 0 ? v : -v;
1658 if (solv->decisionmap[vv] <= level && solv->decisionmap[vv] >= -level)
1660 if (solv->pool->verbose > 3)
1661 printf("reverting decision %d at %d\n", v, solv->decisionmap[vv]);
1662 solv->decisionmap[vv] = 0;
1663 solv->decisionq.count--;
1664 solv->decisionq_why.count--;
1665 solv->propagate_index = solv->decisionq.count;
1667 while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] <= -level)
1669 solv->branches.count--;
1670 while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] >= 0)
1671 solv->branches.count--;
1673 solv->recommends_index = -1;
1678 * watch2onhighest - put watch2 on literal with highest level
1682 watch2onhighest(Solver *solv, Rule *r)
1688 return; /* binary rule, both watches are set */
1689 dp = solv->pool->whatprovidesdata + r->d;
1690 while ((v = *dp++) != 0)
1692 l = solv->decisionmap[v < 0 ? -v : v];
1707 * add free decision to decision q, increase level
1708 * propagate decision, return if no conflict.
1709 * in conflict case, analyze conflict rule, add resulting
1710 * rule to learnt rule set, make decision from learnt
1711 * rule (always unit) and re-propagate.
1715 setpropagatelearn(Solver *solv, int level, Id decision, int disablerules)
1725 solv->decisionmap[decision] = level;
1727 solv->decisionmap[-decision] = -level;
1728 queue_push(&solv->decisionq, decision);
1729 queue_push(&solv->decisionq_why, 0);
1733 r = propagate(solv, level);
1737 return analyze_unsolvable(solv, r, disablerules);
1738 printf("conflict with rule #%d\n", (int)(r - solv->rules));
1739 l = analyze(solv, level, r, &p, &d, &why); /* learnt rule in p and d */
1740 if (l >= level || l <= 0)
1742 printf("reverting decisions (level %d -> %d)\n", level, l);
1744 revert(solv, level);
1745 r = addrule(solv, p, d); /* p requires d */
1748 if (solv->learnt_why.count != (r - solv->rules) - solv->learntrules)
1750 printf("%d %d\n", solv->learnt_why.count, (int)(r - solv->rules) - solv->learntrules);
1753 queue_push(&solv->learnt_why, why);
1756 /* at least 2 literals, needs watches */
1757 watch2onhighest(solv, r);
1758 addwatches(solv, r);
1760 solv->decisionmap[p > 0 ? p : -p] = p > 0 ? level : -level;
1761 queue_push(&solv->decisionq, p);
1762 queue_push(&solv->decisionq_why, r - solv->rules);
1763 if (solv->pool->verbose > 1)
1765 printf("decision: ");
1766 printruleelement(solv, 0, p);
1767 printf("new rule: ");
1776 * install best package from the queue. We add an extra package, inst, if
1777 * provided. See comment in weak install section.
1780 selectandinstall(Solver *solv, int level, Queue *dq, Id inst, int disablerules)
1782 Pool *pool = solv->pool;
1786 if (dq->count > 1 || inst)
1787 policy_filter_unwanted(solv, dq, inst, POLICY_MODE_CHOOSE);
1792 /* choose the supplemented one */
1793 for (i = 0; i < dq->count; i++)
1794 if (solver_is_supplementing(solv, pool->solvables + dq->elements[i]))
1798 for (i = 1; i < dq->count; i++)
1799 queue_push(&solv->branches, dq->elements[i]);
1800 queue_push(&solv->branches, -level);
1804 p = dq->elements[i];
1806 if (pool->verbose > 3)
1808 Solvable *s = pool->solvables + p;
1809 printf("installing %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
1812 return setpropagatelearn(solv, level, p, disablerules);
1816 /*-----------------------------------------------------------------*/
1817 /* Main solver interface */
1822 * create solver structure
1824 * pool: all available solvables
1825 * installed: installed Solvables
1828 * Upon solving, rules are created to flag the Solvables
1829 * of the 'installed' Repo as installed.
1833 solver_create(Pool *pool, Repo *installed)
1836 solv = (Solver *)xcalloc(1, sizeof(Solver));
1838 solv->installed = installed;
1840 queue_init(&solv->ruletojob);
1841 queue_init(&solv->decisionq);
1842 queue_init(&solv->decisionq_why);
1843 queue_init(&solv->problems);
1844 queue_init(&solv->suggestions);
1845 queue_init(&solv->learnt_why);
1846 queue_init(&solv->learnt_pool);
1847 queue_init(&solv->branches);
1849 map_init(&solv->recommendsmap, pool->nsolvables);
1850 map_init(&solv->suggestsmap, pool->nsolvables);
1851 map_init(&solv->noupdate, installed ? installed->nsolvables : 0);
1852 solv->recommends_index = 0;
1854 solv->decisionmap = (Id *)xcalloc(pool->nsolvables, sizeof(Id));
1855 solv->rules = (Rule *)xmalloc((solv->nrules + (RULES_BLOCK + 1)) * sizeof(Rule));
1856 memset(solv->rules, 0, sizeof(Rule));
1868 solver_free(Solver *solv)
1870 queue_free(&solv->ruletojob);
1871 queue_free(&solv->decisionq);
1872 queue_free(&solv->decisionq_why);
1873 queue_free(&solv->learnt_why);
1874 queue_free(&solv->learnt_pool);
1875 queue_free(&solv->problems);
1876 queue_free(&solv->suggestions);
1877 queue_free(&solv->branches);
1879 map_free(&solv->recommendsmap);
1880 map_free(&solv->suggestsmap);
1881 map_free(&solv->noupdate);
1882 xfree(solv->decisionmap);
1884 xfree(solv->watches);
1885 xfree(solv->weaksystemrules);
1886 xfree(solv->obsoletes);
1887 xfree(solv->obsoletes_data);
1892 /*-------------------------------------------------------*/
1897 * all rules have been set up, now actually run the solver
1902 run_solver(Solver *solv, int disablerules, int doweak)
1910 Pool *pool = solv->pool;
1913 if (pool->verbose > 3)
1915 printf("number of rules: %d\n", solv->nrules);
1916 for (i = 0; i < solv->nrules; i++)
1917 printrule(solv, solv->rules + i);
1920 /* all new rules are learnt after this point */
1921 solv->learntrules = solv->nrules;
1922 /* crate watches lists */
1925 if (pool->verbose) printf("initial decisions: %d\n", solv->decisionq.count);
1927 /* start SAT algorithm */
1929 systemlevel = level + 1;
1930 if (pool->verbose) printf("solving...\n");
1941 if (pool->verbose) printf("propagating (%d %d)...\n", solv->propagate_index, solv->decisionq.count);
1942 if ((r = propagate(solv, level)) != 0)
1944 if (analyze_unsolvable(solv, r, disablerules))
1952 * installed packages
1955 if (level < systemlevel && solv->installed->nsolvables)
1957 if (!solv->updatesystem)
1959 /* try to keep as many packages as possible */
1960 if (pool->verbose) printf("installing system packages\n");
1961 for (i = solv->installed->start, n = 0; ; i++, n++)
1963 if (n == solv->installed->nsolvables)
1965 if (i == solv->installed->start + solv->installed->nsolvables)
1966 i = solv->installed->start;
1967 s = pool->solvables + i;
1968 if (solv->decisionmap[i] != 0)
1970 if (pool->verbose > 3)
1971 printf("keeping %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
1973 level = setpropagatelearn(solv, level, i, disablerules);
1979 if (level <= olevel)
1983 if (solv->weaksystemrules)
1985 if (pool->verbose) printf("installing weak system packages\n");
1986 for (i = solv->installed->start, n = 0; ; i++, n++)
1988 if (n == solv->installed->nsolvables)
1990 if (solv->decisionmap[i] > 0 || (solv->decisionmap[i] < 0 && solv->weaksystemrules[i - solv->installed->start] == 0))
1992 /* noupdate is set if a job is erasing the installed solvable or installing a specific version */
1993 if (MAPTST(&solv->noupdate, i - solv->installed->start))
1996 if (solv->weaksystemrules[i - solv->installed->start])
1998 dp = pool->whatprovidesdata + solv->weaksystemrules[i - solv->installed->start];
1999 while ((p = *dp++) != 0)
2001 if (solv->decisionmap[p] > 0)
2003 if (solv->decisionmap[p] == 0)
2007 continue; /* update package already installed */
2009 if (!dq.count && solv->decisionmap[i] != 0)
2012 /* FIXME: i is handled a bit different because we do not want
2013 * to have it pruned just because it is not recommened.
2014 * we should not prune installed packages instead */
2015 level = selectandinstall(solv, level, &dq, (solv->decisionmap[i] ? 0 : i), disablerules);
2021 if (level <= olevel)
2027 if (n != solv->installed->nsolvables)
2030 systemlevel = level;
2037 if (pool->verbose) printf("deciding unresolved rules\n");
2038 for (i = 1, n = 1; ; i++, n++)
2040 if (n == solv->nrules)
2042 if (i == solv->nrules)
2044 r = solv->rules + i;
2050 /* binary or unary rule */
2051 /* need two positive undecided literals */
2052 if (r->p < 0 || r->w2 <= 0)
2054 if (solv->decisionmap[r->p] || solv->decisionmap[r->w2])
2056 queue_push(&dq, r->p);
2057 queue_push(&dq, r->w2);
2062 * all negative literals are installed
2063 * no positive literal is installed
2064 * i.e. the rule is not fulfilled and we
2065 * just need to decide on the positive literals
2069 if (solv->decisionmap[-r->p] <= 0)
2074 if (solv->decisionmap[r->p] > 0)
2076 if (solv->decisionmap[r->p] == 0)
2077 queue_push(&dq, r->p);
2079 dp = pool->whatprovidesdata + r->d;
2080 while ((p = *dp++) != 0)
2084 if (solv->decisionmap[-p] <= 0)
2089 if (solv->decisionmap[p] > 0)
2091 if (solv->decisionmap[p] == 0)
2100 /* cannot happen as this means that
2101 * the rule is unit */
2105 if (pool->verbose > 2)
2109 level = selectandinstall(solv, level, &dq, 0, disablerules);
2115 if (level < systemlevel)
2118 } /* for(), decide */
2120 if (n != solv->nrules) /* continue if level < systemlevel */
2123 if (doweak && !solv->problems.count)
2127 if (pool->verbose) printf("installing recommended packages\n");
2129 for (i = 1; i < pool->nsolvables; i++)
2131 if (solv->decisionmap[i] < 0)
2133 if (solv->decisionmap[i] > 0)
2135 Id *recp, rec, *pp, p;
2136 s = pool->solvables + i;
2137 /* installed, check for recommends */
2138 /* XXX need to special case AND ? */
2141 recp = s->repo->idarraydata + s->recommends;
2142 while ((rec = *recp++) != 0)
2145 FOR_PROVIDES(p, pp, rec)
2147 if (solv->decisionmap[p] > 0)
2152 else if (solv->decisionmap[p] == 0)
2154 queue_pushunique(&dq, p);
2162 s = pool->solvables + i;
2163 if (!s->supplements && !s->freshens)
2165 if (!pool_installable(pool, s))
2167 if (solver_is_supplementing(solv, s))
2168 queue_pushunique(&dq, i);
2174 policy_filter_unwanted(solv, &dq, 0, POLICY_MODE_RECOMMEND);
2176 s = pool->solvables + p;
2177 if (pool->verbose > 0)
2178 printf("installing recommended %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2179 level = setpropagatelearn(solv, level, p, 0);
2184 if (solv->solution_callback)
2186 solv->solution_callback(solv, solv->solution_callback_data);
2187 if (solv->branches.count)
2189 int i = solv->branches.count - 1;
2190 int l = -solv->branches.elements[i];
2192 if (solv->branches.elements[i - 1] < 0)
2194 p = solv->branches.elements[i];
2195 if (pool->verbose > 0)
2197 s = pool->solvables + p;
2198 printf("branching with %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2201 for (j = i + 1; j < solv->branches.count; j++)
2202 queue_push(&dq, solv->branches.elements[j]);
2203 solv->branches.count = i;
2205 revert(solv, level);
2207 for (j = 0; j < dq.count; j++)
2208 queue_push(&solv->branches, dq.elements[j]);
2210 level = setpropagatelearn(solv, level, p, disablerules);
2218 /* all branches done, we're finally finished */
2222 /* minimization step */
2223 if (solv->branches.count)
2225 int l = 0, lasti = -1, lastl = -1;
2227 for (i = solv->branches.count - 1; i >= 0; i--)
2229 p = solv->branches.elements[i];
2232 else if (p > 0 && solv->decisionmap[p] > l + 1)
2240 /* kill old solvable so that we do not loop */
2241 p = solv->branches.elements[lasti];
2242 solv->branches.elements[lasti] = 0;
2243 s = pool->solvables + p;
2244 if (pool->verbose > 0)
2245 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));
2248 revert(solv, level);
2250 level = setpropagatelearn(solv, level, p, disablerules);
2267 * at this point, all rules that led to conflicts are disabled.
2268 * we re-enable all rules of a problem set but rule "sug", then
2269 * continue to disable more rules until there as again a solution.
2272 /* FIXME: think about conflicting assertions */
2275 refine_suggestion(Solver *solv, Queue *job, Id *problem, Id sug, Queue *refined)
2277 Pool *pool = solv->pool;
2286 printf("refine_suggestion start\n");
2287 for (i = 0; problem[i]; i++)
2289 if (problem[i] == sug)
2291 printproblem(solv, problem[i]);
2294 queue_init(&disabled);
2295 queue_empty(refined);
2296 queue_push(refined, sug);
2298 /* re-enable all problem rules with the exception of "sug" */
2302 for (i = 0; problem[i]; i++)
2303 if (problem[i] != sug)
2304 enableproblem(solv, problem[i]);
2307 disableupdaterules(solv, job, -(sug + 1));
2311 /* re-enable as many weak rules as possible */
2312 for (i = solv->weakrules; i < solv->learntrules; i++)
2314 r = solv->rules + i;
2316 enablerule(solv, r);
2319 queue_empty(&solv->problems);
2320 revert(solv, 1); /* XXX move to reset_solver? */
2322 run_solver(solv, 0, 0);
2323 if (!solv->problems.count)
2326 printf("no more problems!\n");
2327 if (pool->verbose > 3)
2328 printdecisions(solv);
2329 break; /* great, no more problems */
2331 disabledcnt = disabled.count;
2332 /* skip over problem rule */
2333 for (i = 2; i < solv->problems.count - 1; i++)
2335 /* ignore solutions in refined */
2336 v = solv->problems.elements[i];
2337 for (j = 0; problem[j]; j++)
2338 if (problem[j] != sug && problem[j] == v)
2342 queue_push(&disabled, v);
2344 if (disabled.count == disabledcnt)
2346 /* no solution found, this was an invalid suggestion! */
2348 printf("no solution found!\n");
2352 if (disabled.count == disabledcnt + 1)
2354 /* just one suggestion, add it to refined list */
2355 v = disabled.elements[disabledcnt];
2356 queue_push(refined, v);
2357 disableproblem(solv, v);
2359 disableupdaterules(solv, job, -(v + 1));
2363 /* more than one solution, disable all */
2364 /* do not push anything on refine list */
2365 if (pool->verbose > 1)
2367 printf("more than one solution found:\n");
2368 for (i = disabledcnt; i < disabled.count; i++)
2369 printproblem(solv, disabled.elements[i]);
2371 for (i = disabledcnt; i < disabled.count; i++)
2372 disableproblem(solv, disabled.elements[i]);
2375 /* all done, get us back into the same state as before */
2376 /* enable refined rules again */
2377 for (i = 0; i < disabled.count; i++)
2378 enableproblem(solv, disabled.elements[i]);
2379 /* disable problem rules again */
2380 for (i = 0; problem[i]; i++)
2381 disableproblem(solv, problem[i]);
2383 printf("refine_suggestion end\n");
2387 problems_to_solutions(Solver *solv, Queue *job)
2389 Pool *pool = solv->pool;
2397 if (!solv->problems.count)
2399 queue_clone(&problems, &solv->problems);
2400 queue_init(&solution);
2401 queue_init(&solutions);
2402 /* copy over problem rule */
2403 queue_push(&solutions, problems.elements[0]);
2404 queue_push(&solutions, problems.elements[1]);
2405 problem = problems.elements + 2;
2406 for (i = 2; i < problems.count; i++)
2408 Id v = problems.elements[i];
2411 /* mark end of this problem */
2412 queue_push(&solutions, 0);
2413 queue_push(&solutions, 0);
2414 if (i + 1 == problems.count)
2416 /* copy over problem rule of next problem */
2417 queue_push(&solutions, problems.elements[i + 1]);
2418 queue_push(&solutions, problems.elements[i + 2]);
2420 problem = problems.elements + i + 1;
2423 refine_suggestion(solv, job, problem, v, &solution);
2424 if (!solution.count)
2425 continue; /* this solution didn't work out */
2427 for (j = 0; j < solution.count; j++)
2429 why = solution.elements[j];
2431 printproblem(solv, why);
2435 queue_push(&solutions, 0);
2436 queue_push(&solutions, -why);
2438 else if (why >= solv->systemrules && why < solv->weakrules)
2441 p = solv->installed->start + (why - solv->systemrules);
2442 if (solv->weaksystemrules && solv->weaksystemrules[why - solv->systemrules])
2444 Id *dp = pool->whatprovidesdata + solv->weaksystemrules[why - solv->systemrules];
2447 if (*dp >= solv->installed->start && *dp < solv->installed->start + solv->installed->nsolvables)
2449 if (solv->decisionmap[*dp] > 0)
2456 queue_push(&solutions, p);
2457 queue_push(&solutions, rp);
2462 /* mark end of this solution */
2463 queue_push(&solutions, 0);
2464 queue_push(&solutions, 0);
2466 queue_free(&solution);
2467 queue_free(&problems);
2468 /* copy queue over to solutions */
2469 queue_free(&solv->problems);
2470 queue_clone(&solv->problems, &solutions);
2471 queue_free(&solutions);
2481 id2rc(Solver *solv, Id id)
2484 if (solv->rc_output != 2)
2486 evr = id2str(solv->pool, id);
2487 if (*evr < '0' || *evr > '9')
2489 while (*evr >= '0' && *evr <= '9')
2497 printdecisions(Solver *solv)
2499 Pool *pool = solv->pool;
2500 Id p, *obsoletesmap;
2504 obsoletesmap = (Id *)xcalloc(pool->nsolvables, sizeof(Id));
2505 for (i = 0; i < solv->decisionq.count; i++)
2509 n = solv->decisionq.elements[i];
2512 if (n == SYSTEMSOLVABLE)
2514 if (n >= solv->installed->start && n < solv->installed->start + solv->installed->nsolvables)
2516 s = pool->solvables + n;
2517 FOR_PROVIDES(p, pp, s->name)
2518 if (s->name == pool->solvables[p].name)
2520 if (p >= solv->installed->start && p < solv->installed->start + solv->installed->nsolvables && !obsoletesmap[p])
2522 obsoletesmap[p] = n;
2527 for (i = 0; i < solv->decisionq.count; i++)
2532 n = solv->decisionq.elements[i];
2535 if (n == SYSTEMSOLVABLE)
2537 if (n >= solv->installed->start && n < solv->installed->start + solv->installed->nsolvables)
2539 s = pool->solvables + n;
2542 obsp = s->repo->idarraydata + s->obsoletes;
2543 while ((obs = *obsp++) != 0)
2544 FOR_PROVIDES(p, pp, obs)
2546 if (p >= solv->installed->start && p < solv->installed->start + solv->installed->nsolvables && !obsoletesmap[p])
2548 obsoletesmap[p] = n;
2554 if (solv->rc_output)
2555 printf(">!> Solution #1:\n");
2557 int installs = 0, uninstalls = 0, upgrades = 0;
2559 /* print solvables to be erased */
2561 for (i = solv->installed->start; i < solv->installed->start + solv->installed->nsolvables; i++)
2563 if (solv->decisionmap[i] > 0)
2565 if (obsoletesmap[i])
2567 s = pool->solvables + i;
2568 if (solv->rc_output == 2)
2569 printf(">!> remove %s-%s%s\n", id2str(pool, s->name), id2rc(solv, s->evr), id2str(pool, s->evr));
2570 else if (solv->rc_output)
2571 printf(">!> remove %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2573 printf("erase %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2577 /* print solvables to be installed */
2579 for (i = 0; i < solv->decisionq.count; i++)
2582 p = solv->decisionq.elements[i];
2585 if (p == SYSTEMSOLVABLE)
2587 if (p >= solv->installed->start && p < solv->installed->start + solv->installed->nsolvables)
2589 s = pool->solvables + p;
2591 if (!obsoletesmap[p])
2593 if (solv->rc_output)
2595 printf("install %s-%s%s", id2str(pool, s->name), id2rc(solv, s->evr), id2str(pool, s->evr));
2596 if (solv->rc_output != 2)
2597 printf(".%s", id2str(pool, s->arch));
2600 else if (!solv->rc_output)
2602 printf("update %s-%s.%s (obsoletes", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2603 for (j = solv->installed->start; j < solv->installed->start + solv->installed->nsolvables; j++)
2605 if (obsoletesmap[j] != p)
2607 s = pool->solvables + j;
2608 printf(" %s-%s.%s", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2615 Solvable *f, *fn = 0;
2616 for (j = solv->installed->start; j < solv->installed->start + solv->installed->nsolvables; j++)
2618 if (obsoletesmap[j] != p)
2620 f = pool->solvables + j;
2621 if (fn || f->name != s->name)
2623 if (solv->rc_output == 2)
2624 printf(">!> remove %s-%s%s\n", id2str(pool, f->name), id2rc(solv, f->evr), id2str(pool, f->evr));
2625 else if (solv->rc_output)
2626 printf(">!> remove %s-%s.%s\n", id2str(pool, f->name), id2str(pool, f->evr), id2str(pool, f->arch));
2634 printf(">!> install %s-%s%s", id2str(pool, s->name), id2rc(solv, s->evr), id2str(pool, s->evr));
2635 if (solv->rc_output != 2)
2636 printf(".%s", id2str(pool, s->arch));
2641 if (solv->rc_output == 2)
2642 printf(">!> upgrade %s-%s => %s-%s%s", id2str(pool, fn->name), id2str(pool, fn->evr), id2str(pool, s->name), id2rc(solv, s->evr), id2str(pool, s->evr));
2644 printf(">!> upgrade %s-%s.%s => %s-%s.%s", id2str(pool, fn->name), id2str(pool, fn->evr), id2str(pool, fn->arch), id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2648 if (solv->rc_output)
2650 Repo *repo = s->repo;
2651 if (repo && strcmp(repo_name(repo), "locales"))
2652 printf("[%s]", repo_name(repo));
2657 if (solv->rc_output)
2658 printf(">!> installs=%d, upgrades=%d, uninstalls=%d\n", installs, upgrades, uninstalls);
2660 xfree(obsoletesmap);
2662 if (solv->suggestions.count)
2664 printf("\nsuggested packages:\n");
2665 for (i = 0; i < solv->suggestions.count; i++)
2667 s = pool->solvables + solv->suggestions.elements[i];
2668 printf("- %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2674 printconflicts(Solver *solv, Solvable *s, Id pc)
2676 Pool *pool = solv->pool;
2677 Solvable *sc = pool->solvables + pc;
2678 Id p, *pp, con, *conp, obs, *obsp;
2683 conp = s->repo->idarraydata + s->conflicts;
2684 while ((con = *conp++) != 0)
2686 FOR_PROVIDES(p, pp, con)
2690 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));
2695 if (s->obsoletes && (!solv->installed || s - pool->solvables < solv->installed->start || s - pool->solvables >= solv->installed->start + solv->installed->nsolvables))
2697 obsp = s->repo->idarraydata + s->obsoletes;
2698 while ((obs = *obsp++) != 0)
2700 FOR_PROVIDES(p, pp, obs)
2704 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));
2713 printprobleminfo(Solver *solv, Id p, Id d, Queue *job, Id firstp, Id firstrp)
2715 Pool *pool = solv->pool;
2722 /* learnt rule, ignore for now */
2723 printf("some learnt rule...\n");
2728 /* conflict with system solvable, i.e. could not create rule */
2731 printf("got firstp\n");
2734 what = job->elements[firstrp];
2735 switch (job->elements[firstrp - 1])
2737 case SOLVER_INSTALL_SOLVABLE_NAME:
2738 printf("no solvable exists with name %s\n", dep2str(pool, what));
2740 case SOLVER_INSTALL_SOLVABLE_PROVIDES:
2741 printf("no solvable provides %s\n", dep2str(pool, what));
2744 printf("unknown job\n");
2753 /* conflict with rpm rule, package -d is not installable */
2754 s = pool->solvables + (-d);
2757 reqp = s->repo->idarraydata + s->requires;
2758 while ((req = *reqp++) != 0)
2760 if (req == SOLVABLE_PREREQMARKER)
2762 dp = GET_PROVIDESP(req, p);
2765 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));
2770 printf("package %s-%s.%s is not installable\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2773 if (d >= solv->jobrules)
2775 r = solv->rules + d;
2781 sp = pool->solvables + (-p);
2782 sd = pool->solvables + (-d);
2783 printf("package %s-%s.%s cannot be installed with package %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));
2786 printf("some job rule...\n");
2790 r = solv->rules + d;
2795 if (d == 0 && r->w2 < 0)
2799 sp = pool->solvables + (-p);
2800 sd = pool->solvables + (-d);
2801 if (sp->name == sd->name)
2803 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));
2807 printconflicts(solv, pool->solvables + (-p), -d);
2808 printconflicts(solv, pool->solvables + (-d), -p);
2813 /* find requires of p that corresponds with our rule */
2815 s = pool->solvables + (-p);
2816 reqp = s->repo->idarraydata + s->requires;
2817 while ((req = *reqp++) != 0)
2819 if (req == SOLVABLE_PREREQMARKER)
2821 dp = GET_PROVIDESP(req, p);
2824 if (*dp == r->w2 && dp[1] == 0)
2827 else if (dp - pool->whatprovidesdata == d)
2832 printf("req not found\n");
2835 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));
2840 printsolutions(Solver *solv, Queue *job)
2842 Pool *pool = solv->pool;
2848 printf("Encountered problems! Here are the solutions:\n\n");
2850 for (i = 0; i < solv->problems.count; )
2852 printf("Problem %d:\n", pcnt++);
2853 printf("====================================\n");
2854 p = solv->problems.elements[i++];
2855 d = solv->problems.elements[i++];
2856 printprobleminfo(solv, p, d, job, solv->problems.elements[i], solv->problems.elements[i + 1]);
2860 if (solv->problems.elements[i] == 0 && solv->problems.elements[i + 1] == 0)
2862 /* end of solutions for this problems reached */
2868 p = solv->problems.elements[i];
2869 rp = solv->problems.elements[i + 1];
2871 if (p == 0 && rp == 0)
2873 /* end of this solution reached */
2879 /* job, p is index into job queue */
2880 what = job->elements[rp];
2881 switch (job->elements[rp - 1])
2883 case SOLVER_INSTALL_SOLVABLE:
2884 s = pool->solvables + what;
2885 if (what >= solv->installed->start && what < solv->installed->start + solv->installed->nsolvables)
2886 printf("- do not keep %s-%s.%s installed\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2888 printf("- do not install %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2890 case SOLVER_ERASE_SOLVABLE:
2891 s = pool->solvables + what;
2892 if (what >= solv->installed->start && what < solv->installed->start + solv->installed->nsolvables)
2893 printf("- do not deinstall %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2895 printf("- do not forbid installation of %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2897 case SOLVER_INSTALL_SOLVABLE_NAME:
2898 printf("- do not install %s\n", id2str(pool, what));
2900 case SOLVER_ERASE_SOLVABLE_NAME:
2901 printf("- do not deinstall %s\n", id2str(pool, what));
2903 case SOLVER_INSTALL_SOLVABLE_PROVIDES:
2904 printf("- do not install a solvable providing %s\n", dep2str(pool, what));
2906 case SOLVER_ERASE_SOLVABLE_PROVIDES:
2907 printf("- do not deinstall all solvables providing %s\n", dep2str(pool, what));
2909 case SOLVER_INSTALL_SOLVABLE_UPDATE:
2910 s = pool->solvables + what;
2911 printf("- do not install most recent version of %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool
2915 printf("- do something different\n");
2921 /* policy, replace p with rp */
2922 s = pool->solvables + p;
2923 sd = rp ? pool->solvables + rp : 0;
2927 if (!solv->allowdowngrade && evrcmp(pool, s->evr, sd->evr) > 0)
2929 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));
2932 if (!solv->allowarchchange && s->name == sd->name && s->arch != sd->arch && policy_illegal_archchange(pool, s, sd))
2934 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));
2937 if (!solv->allowvendorchange && s->name == sd->name && s->vendor != sd->vendor && policy_illegal_vendorchange(pool, s, sd))
2940 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));
2942 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));
2946 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));
2950 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));
2960 /* for each installed solvable find which packages with *different* names
2961 * obsolete the solvable.
2962 * this index is used in policy_findupdatepackages if noupdateprovide is set.
2966 create_obsolete_index(Solver *solv)
2968 Pool *pool = solv->pool;
2970 Repo *installed = solv->installed;
2971 Id p, *pp, obs, *obsp, *obsoletes, *obsoletes_data;
2974 /* create reverse obsoletes map for installed solvables */
2975 solv->obsoletes = obsoletes = xcalloc(installed->nsolvables, sizeof(Id));
2976 for (i = 1; i < pool->nsolvables; i++)
2978 s = pool->solvables + i;
2981 if (!pool_installable(pool, s))
2983 obsp = s->repo->idarraydata + s->obsoletes;
2984 while ((obs = *obsp++) != 0)
2985 FOR_PROVIDES(p, pp, obs)
2987 if (p < installed->start || p >= installed->start + installed->nsolvables)
2989 if (pool->solvables[p].name == s->name)
2991 obsoletes[p - installed->start]++;
2995 for (i = 0; i < installed->nsolvables; i++)
2998 n += obsoletes[i] + 1;
3001 solv->obsoletes_data = obsoletes_data = xcalloc(n + 1, sizeof(Id));
3002 if (pool->verbose) printf("obsoletes data: %d entries\n", n + 1);
3003 for (i = pool->nsolvables - 1; i > 0; i--)
3005 s = pool->solvables + i;
3008 if (!pool_installable(pool, s))
3010 obsp = s->repo->idarraydata + s->obsoletes;
3011 while ((obs = *obsp++) != 0)
3012 FOR_PROVIDES(p, pp, obs)
3014 if (p < installed->start || p >= installed->start + installed->nsolvables)
3016 if (pool->solvables[p].name == s->name)
3018 p -= installed->start;
3019 if (obsoletes_data[obsoletes[p]] != i)
3020 obsoletes_data[--obsoletes[p]] = i;
3026 /*-----------------------------------------------------------------*/
3036 solve(Solver *solv, Queue *job)
3038 Pool *pool = solv->pool;
3040 Map addedmap; /* '1' == have rule for solvable */
3041 Id how, what, p, *pp, d;
3045 /* create obsolete index if needed */
3046 if (solv->noupdateprovide && solv->installed->nsolvables)
3047 create_obsolete_index(solv);
3050 * create basic rule set of all involved packages
3051 * use addedmap bitmap to make sure we don't create rules twice
3055 map_init(&addedmap, pool->nsolvables);
3059 * always install our system solvable
3061 MAPSET(&addedmap, SYSTEMSOLVABLE);
3062 queue_push(&solv->decisionq, SYSTEMSOLVABLE);
3063 queue_push(&solv->decisionq_why, 0);
3064 solv->decisionmap[SYSTEMSOLVABLE] = 1;
3067 * create rules for installed solvables -> keep them installed
3068 * so called: rpm rules
3071 if (solv->pool->verbose > 3)
3072 printf ("*** create rules for installed solvables -> keep them installed ***\n");
3073 for (i = solv->installed->start; i < solv->installed->start + solv->installed->nsolvables; i++)
3074 addrpmrulesforsolvable(solv, pool->solvables + i, &addedmap);
3077 * create install rules
3079 * two passes, as we want to keep the rpm rules distinct from the job rules
3085 * process job rules for solvables
3087 if (solv->pool->verbose > 3)
3088 printf ("*** create install rules ***\n");
3090 for (i = 0; i < job->count; i += 2)
3092 how = job->elements[i];
3093 what = job->elements[i + 1];
3097 case SOLVER_INSTALL_SOLVABLE:
3098 addrpmrulesforsolvable(solv, pool->solvables + what, &addedmap);
3100 case SOLVER_INSTALL_SOLVABLE_NAME:
3101 case SOLVER_INSTALL_SOLVABLE_PROVIDES:
3102 FOR_PROVIDES(p, pp, what)
3104 /* if by name, ensure that the name matches */
3105 if (how == SOLVER_INSTALL_SOLVABLE_NAME && pool->solvables[p].name != what)
3107 addrpmrulesforsolvable(solv, pool->solvables + p, &addedmap);
3110 case SOLVER_INSTALL_SOLVABLE_UPDATE:
3111 /* dont allow downgrade */
3112 addrpmrulesforupdaters(solv, pool->solvables + what, &addedmap, 0);
3117 for (i = solv->installed->start; i < solv->installed->start + solv->installed->nsolvables; i++)
3118 addrpmrulesforupdaters(solv, pool->solvables + i, &addedmap, 1);
3120 if (solv->pool->verbose > 3)
3121 printf ("*** Add rules for week dependencies ***\n");
3124 addrpmrulesforweak(solv, &addedmap);
3129 int possible = 0, installable = 0;
3130 for (i = 1; i < pool->nsolvables; i++)
3132 if (pool_installable(pool, pool->solvables + i))
3134 if (MAPTST(&addedmap, i))
3137 printf("%d of %d installable solvables used for solving\n", possible, installable);
3142 * first pass done, we now have all the rpm rules we need.
3143 * unify existing rules before going over all job rules and
3145 * at this point the system is always solvable,
3146 * as an empty system (remove all packages) is a valid solution
3149 unifyrules(solv); /* remove duplicate rpm rules */
3151 if (pool->verbose) printf("Decisions based on %d rpm rules.\n", solv->decisionq.count);
3154 * now add all job rules
3157 if (solv->pool->verbose > 3)
3158 printf ("*** Add JOB rules ***\n");
3160 solv->jobrules = solv->nrules;
3162 for (i = 0; i < job->count; i += 2)
3164 how = job->elements[i];
3165 what = job->elements[i + 1];
3168 case SOLVER_INSTALL_SOLVABLE: /* install specific solvable */
3169 s = pool->solvables + what;
3170 if (solv->rc_output)
3172 printf(">!> Installing %s from channel %s\n", id2str(pool, s->name), repo_name(s->repo));
3175 printf("job: install solvable %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
3176 addrule(solv, what, 0); /* install by Id */
3177 queue_push(&solv->ruletojob, i);
3179 case SOLVER_ERASE_SOLVABLE:
3180 s = pool->solvables + what;
3182 printf("job: erase solvable %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
3183 addrule(solv, -what, 0); /* remove by Id */
3184 queue_push(&solv->ruletojob, i);
3186 case SOLVER_INSTALL_SOLVABLE_NAME: /* install by capability */
3187 case SOLVER_INSTALL_SOLVABLE_PROVIDES:
3188 if (pool->verbose && how == SOLVER_INSTALL_SOLVABLE_NAME)
3189 printf("job: install name %s\n", id2str(pool, what));
3190 if (pool->verbose && how == SOLVER_INSTALL_SOLVABLE_PROVIDES)
3191 printf("job: install provides %s\n", dep2str(pool, what));
3193 FOR_PROVIDES(p, pp, what)
3195 /* if by name, ensure that the name matches */
3196 if (how == SOLVER_INSTALL_SOLVABLE_NAME && pool->solvables[p].name != what)
3202 /* no provider, make this an impossible rule */
3203 queue_push(&q, -SYSTEMSOLVABLE);
3206 p = queue_shift(&q); /* get first provider */
3208 d = 0; /* single provider ? -> make assertion */
3210 d = pool_queuetowhatprovides(pool, &q); /* get all providers */
3211 addrule(solv, p, d); /* add 'requires' rule */
3212 queue_push(&solv->ruletojob, i);
3214 case SOLVER_ERASE_SOLVABLE_NAME: /* remove by capability */
3215 case SOLVER_ERASE_SOLVABLE_PROVIDES:
3216 if (pool->verbose && how == SOLVER_ERASE_SOLVABLE_NAME)
3217 printf("job: erase name %s\n", id2str(pool, what));
3218 if (pool->verbose && how == SOLVER_ERASE_SOLVABLE_PROVIDES)
3219 printf("job: erase provides %s\n", dep2str(pool, what));
3220 FOR_PROVIDES(p, pp, what)
3222 /* if by name, ensure that the name matches */
3223 if (how == SOLVER_ERASE_SOLVABLE_NAME && pool->solvables[p].name != what)
3225 addrule(solv, -p, 0); /* add 'remove' rule */
3226 queue_push(&solv->ruletojob, i);
3229 case SOLVER_INSTALL_SOLVABLE_UPDATE: /* find update for solvable */
3230 s = pool->solvables + what;
3232 printf("job: update %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
3233 addupdaterule(solv, s, 0);
3234 queue_push(&solv->ruletojob, i);
3239 if (solv->ruletojob.count != solv->nrules - solv->jobrules)
3243 * now add system rules
3247 if (solv->pool->verbose > 3)
3248 printf ("*** Add system rules ***\n");
3251 solv->systemrules = solv->nrules;
3254 * create rules for updating installed solvables
3258 if (!solv->allowuninstall)
3259 { /* loop over all installed solvables */
3260 /* we create all update rules, but disable some later on depending on the job */
3261 for (i = solv->installed->start; i < solv->installed->start + solv->installed->nsolvables; i++)
3262 addupdaterule(solv, pool->solvables + i, 0);
3263 /* consistency check: we added a rule for _every_ system solvable */
3264 if (solv->nrules - solv->systemrules != solv->installed->nsolvables)
3268 /* create special weak system rules */
3269 /* those are used later on to keep a version of the installed packages in
3271 if (solv->installed->nsolvables)
3273 solv->weaksystemrules = xcalloc(solv->installed->nsolvables, sizeof(Id));
3274 for (i = 0; i < solv->installed->nsolvables; i++)
3276 policy_findupdatepackages(solv, pool->solvables + solv->installed->start + i, &q, 1);
3278 solv->weaksystemrules[i] = pool_queuetowhatprovides(pool, &q);
3282 /* free unneeded memory */
3283 map_free(&addedmap);
3286 solv->weakrules = solv->nrules;
3288 /* try real hard to keep packages installed */
3291 for (i = 0; i < solv->installed->nsolvables; i++)
3293 /* FIXME: can't work with refine_suggestion! */
3294 /* need to always add the rule but disable it */
3295 if (MAPTST(&solv->noupdate, i))
3297 d = solv->weaksystemrules[i];
3298 addrule(solv, solv->installed->start + i, d);
3307 disableupdaterules(solv, job, -1);
3308 makeruledecisions(solv);
3310 if (pool->verbose) printf("problems so far: %d\n", solv->problems.count);
3312 run_solver(solv, 1, 1);
3314 /* find suggested packages */
3315 if (!solv->problems.count)
3317 Id sug, *sugp, p, *pp;
3319 /* create map of all suggests that are still open */
3320 solv->recommends_index = -1;
3321 MAPZERO(&solv->suggestsmap);
3322 for (i = 0; i < solv->decisionq.count; i++)
3324 p = solv->decisionq.elements[i];
3327 s = pool->solvables + p;
3330 sugp = s->repo->idarraydata + s->suggests;
3331 while ((sug = *sugp++) != 0)
3333 FOR_PROVIDES(p, pp, sug)
3334 if (solv->decisionmap[p] > 0)
3337 continue; /* already fulfilled */
3338 FOR_PROVIDES(p, pp, sug)
3339 MAPSET(&solv->suggestsmap, p);
3343 for (i = 1; i < pool->nsolvables; i++)
3345 if (solv->decisionmap[i] != 0)
3347 s = pool->solvables + i;
3348 if (!MAPTST(&solv->suggestsmap, i))
3352 if (!pool_installable(pool, s))
3354 if (!solver_is_enhancing(solv, s))
3357 queue_push(&solv->suggestions, i);
3359 policy_filter_unwanted(solv, &solv->suggestions, 0, POLICY_MODE_SUGGEST);
3362 if (solv->problems.count)
3363 problems_to_solutions(solv, job);