2 * Copyright (c) 2007-2009, Novell Inc.
4 * This program is licensed under the BSD license, read LICENSE.BSD
5 * for further information
20 #include "solver_private.h"
25 #include "solverdebug.h"
28 /**********************************************************************************/
30 /* a problem is an item on the solver's problem list. It can either be >0, in that
31 * case it is a update/infarch/dup rule, or it can be <0, which makes it refer to a job
32 * consisting of multiple job rules.
36 solver_disableproblem(Solver *solv, Id v)
44 if (v >= solv->infarchrules && v < solv->infarchrules_end)
46 Pool *pool = solv->pool;
47 Id name = pool->solvables[-solv->rules[v].p].name;
48 while (v > solv->infarchrules && pool->solvables[-solv->rules[v - 1].p].name == name)
50 for (; v < solv->infarchrules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
51 solver_disablerule(solv, solv->rules + v);
54 if (v >= solv->duprules && v < solv->duprules_end)
56 Pool *pool = solv->pool;
57 Id name = pool->solvables[-solv->rules[v].p].name;
58 while (v > solv->duprules && pool->solvables[-solv->rules[v - 1].p].name == name)
60 for (; v < solv->duprules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
61 solver_disablerule(solv, solv->rules + v);
64 solver_disablerule(solv, solv->rules + v);
66 /* XXX: doesn't work */
67 if (v >= solv->updaterules && v < solv->updaterules_end)
69 /* enable feature rule if we disabled the update rule */
70 r = solv->rules + (v - solv->updaterules + solv->featurerules);
72 solver_enablerule(solv, r);
78 jp = solv->ruletojob.elements;
79 for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++, jp++)
81 solver_disablerule(solv, r);
84 /*-------------------------------------------------------------------
89 solver_enableproblem(Solver *solv, Id v)
97 if (v >= solv->infarchrules && v < solv->infarchrules_end)
99 Pool *pool = solv->pool;
100 Id name = pool->solvables[-solv->rules[v].p].name;
101 while (v > solv->infarchrules && pool->solvables[-solv->rules[v - 1].p].name == name)
103 for (; v < solv->infarchrules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
104 solver_enablerule(solv, solv->rules + v);
107 if (v >= solv->duprules && v < solv->duprules_end)
109 Pool *pool = solv->pool;
110 Id name = pool->solvables[-solv->rules[v].p].name;
111 while (v > solv->duprules && pool->solvables[-solv->rules[v - 1].p].name == name)
113 for (; v < solv->duprules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
114 solver_enablerule(solv, solv->rules + v);
117 if (v >= solv->featurerules && v < solv->featurerules_end)
119 /* do not enable feature rule if update rule is enabled */
120 r = solv->rules + (v - solv->featurerules + solv->updaterules);
124 solver_enablerule(solv, solv->rules + v);
125 if (v >= solv->updaterules && v < solv->updaterules_end)
127 /* disable feature rule when enabling update rule */
128 r = solv->rules + (v - solv->updaterules + solv->featurerules);
130 solver_disablerule(solv, r);
135 jp = solv->ruletojob.elements;
136 for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++, jp++)
138 solver_enablerule(solv, r);
142 /*-------------------------------------------------------------------
145 * Reenable all disabled weak rules (marked in weakrulemap)
150 enableweakrules(Solver *solv)
155 if (!solv->weakrulemap.size)
157 for (i = 1, r = solv->rules + i; i < solv->learntrules; i++, r++)
159 if (r->d >= 0) /* already enabled? */
161 if (!MAPTST(&solv->weakrulemap, i))
163 solver_enablerule(solv, r);
165 /* make sure broken orphan rules stay disabled */
166 if (solv->brokenorphanrules)
167 for (i = 0; i < solv->brokenorphanrules->count; i++)
168 solver_disablerule(solv, solv->rules + solv->brokenorphanrules->elements[i]);
172 /*-------------------------------------------------------------------
176 * at this point, all rules that led to conflicts are disabled.
177 * we re-enable all rules of a problem set but rule "sug", then
178 * continue to disable more rules until there as again a solution.
181 /* FIXME: think about conflicting assertions */
184 refine_suggestion(Solver *solv, Id *problem, Id sug, Queue *refined, int essentialok)
186 Pool *pool = solv->pool;
192 IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS)
194 POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "refine_suggestion start\n");
195 for (i = 0; problem[i]; i++)
197 if (problem[i] == sug)
198 POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "=> ");
199 solver_printproblem(solv, problem[i]);
202 queue_empty(refined);
203 if (!essentialok && sug < 0 && (solv->job.elements[-sug - 1] & SOLVER_ESSENTIAL) != 0)
205 queue_init(&disabled);
206 queue_push(refined, sug);
208 /* re-enable all problem rules with the exception of "sug"(gestion) */
211 for (i = 0; problem[i]; i++)
212 if (problem[i] != sug)
213 solver_enableproblem(solv, problem[i]);
216 solver_reenablepolicyrules(solv, -sug);
217 else if (sug >= solv->updaterules && sug < solv->updaterules_end)
219 /* enable feature rule */
220 Rule *r = solv->rules + solv->featurerules + (sug - solv->updaterules);
222 solver_enablerule(solv, r);
225 enableweakrules(solv);
229 int njob, nfeature, nupdate, pass;
230 queue_empty(&solv->problems);
232 solver_run_sat(solv, 0, 0);
234 if (!solv->problems.count)
236 POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "no more problems!\n");
237 break; /* great, no more problems */
239 disabledcnt = disabled.count;
240 /* start with 1 to skip over proof index */
241 njob = nfeature = nupdate = 0;
242 for (pass = 0; pass < 2; pass++)
244 for (i = 1; i < solv->problems.count - 1; i++)
246 /* ignore solutions in refined */
247 v = solv->problems.elements[i];
249 break; /* end of problem reached */
252 /* check if v is in the given problems list
253 * we allow disabling all problem rules *after* sug in
254 * pass 2, to prevent getting the same solution twice */
255 for (j = 0; problem[j]; j++)
256 if (problem[j] == v || (pass && problem[j] == sug))
261 if (v >= solv->featurerules && v < solv->featurerules_end)
267 if (!essentialok && (solv->job.elements[-v - 1] & SOLVER_ESSENTIAL) != 0)
268 continue; /* not that one! */
271 queue_push(&disabled, v);
273 if (disabled.count != disabledcnt)
276 if (disabled.count == disabledcnt)
278 /* no solution found, this was an invalid suggestion! */
279 POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "no solution found!\n");
283 if (!njob && nupdate && nfeature)
285 /* got only update rules, filter out feature rules */
286 POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "throwing away feature rules\n");
287 for (i = j = disabledcnt; i < disabled.count; i++)
289 v = disabled.elements[i];
290 if (v < solv->featurerules || v >= solv->featurerules_end)
291 disabled.elements[j++] = v;
296 if (disabled.count == disabledcnt + 1)
298 /* just one suggestion, add it to refined list */
299 v = disabled.elements[disabledcnt];
300 if (!nfeature && v != sug)
301 queue_push(refined, v); /* do not record feature rules */
302 solver_disableproblem(solv, v);
303 if (v >= solv->updaterules && v < solv->updaterules_end)
305 Rule *r = solv->rules + (v - solv->updaterules + solv->featurerules);
307 solver_enablerule(solv, r); /* enable corresponding feature rule */
310 solver_reenablepolicyrules(solv, -v);
314 /* more than one solution, disable all */
315 /* do not push anything on refine list, as we do not know which solution to choose */
316 /* thus, the user will get another problem if he selects this solution, where he
317 * can choose the right one */
318 IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS)
320 POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "more than one solution found:\n");
321 for (i = disabledcnt; i < disabled.count; i++)
322 solver_printproblem(solv, disabled.elements[i]);
324 for (i = disabledcnt; i < disabled.count; i++)
326 v = disabled.elements[i];
327 solver_disableproblem(solv, v);
328 if (v >= solv->updaterules && v < solv->updaterules_end)
330 Rule *r = solv->rules + (v - solv->updaterules + solv->featurerules);
332 solver_enablerule(solv, r);
337 /* all done, get us back into the same state as before */
338 /* enable refined rules again */
339 for (i = 0; i < disabled.count; i++)
340 solver_enableproblem(solv, disabled.elements[i]);
341 queue_free(&disabled);
342 /* reset policy rules */
343 for (i = 0; problem[i]; i++)
344 solver_enableproblem(solv, problem[i]);
345 solver_disablepolicyrules(solv);
346 /* disable problem rules again */
347 for (i = 0; problem[i]; i++)
348 solver_disableproblem(solv, problem[i]);
349 POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "refine_suggestion end\n");
353 /*-------------------------------------------------------------------
354 * sorting helper for problems
356 * bring update rules before job rules
357 * make essential job rules last
361 problems_sortcmp(const void *ap, const void *bp, void *dp)
364 Id a = *(Id *)ap, b = *(Id *)bp;
371 int af = job->elements[-a - 1] & SOLVER_ESSENTIAL;
372 int bf = job->elements[-b - 1] & SOLVER_ESSENTIAL;
381 * convert a solution rule into a job modifier
384 convertsolution(Solver *solv, Id why, Queue *solutionq)
386 Pool *pool = solv->pool;
390 if (why < solv->pooljobcnt)
392 queue_push(solutionq, SOLVER_SOLUTION_POOLJOB);
393 queue_push(solutionq, why);
397 queue_push(solutionq, SOLVER_SOLUTION_JOB);
398 queue_push(solutionq, why - solv->pooljobcnt);
402 if (why >= solv->infarchrules && why < solv->infarchrules_end)
405 /* infarch rule, find replacement */
406 assert(solv->rules[why].p < 0);
407 name = pool->solvables[-solv->rules[why].p].name;
408 while (why > solv->infarchrules && pool->solvables[-solv->rules[why - 1].p].name == name)
411 for (; why < solv->infarchrules_end && pool->solvables[-solv->rules[why].p].name == name; why++)
412 if (solv->decisionmap[-solv->rules[why].p] > 0)
414 p = -solv->rules[why].p;
418 return; /* false alarm */
419 queue_push(solutionq, SOLVER_SOLUTION_INFARCH);
420 queue_push(solutionq, p);
423 if (why >= solv->duprules && why < solv->duprules_end)
426 /* dist upgrade rule, find replacement */
427 assert(solv->rules[why].p < 0);
428 name = pool->solvables[-solv->rules[why].p].name;
429 while (why > solv->duprules && pool->solvables[-solv->rules[why - 1].p].name == name)
432 for (; why < solv->duprules_end && pool->solvables[-solv->rules[why].p].name == name; why++)
433 if (solv->decisionmap[-solv->rules[why].p] > 0)
435 p = -solv->rules[why].p;
439 return; /* false alarm */
440 queue_push(solutionq, SOLVER_SOLUTION_DISTUPGRADE);
441 queue_push(solutionq, p);
444 if (why >= solv->updaterules && why < solv->updaterules_end)
446 /* update rule, find replacement package */
450 /* check if this is a false positive, i.e. the update rule is fulfilled */
451 rr = solv->rules + why;
452 FOR_RULELITERALS(p, pp, rr)
453 if (p > 0 && solv->decisionmap[p] > 0)
454 return; /* false alarm */
456 p = solv->installed->start + (why - solv->updaterules);
457 if (solv->dupmap_all && solv->rules[why].p != p && solv->decisionmap[p] > 0)
459 /* distupgrade case, allow to keep old package */
460 queue_push(solutionq, SOLVER_SOLUTION_DISTUPGRADE);
461 queue_push(solutionq, p);
464 if (solv->decisionmap[p] > 0)
465 return; /* false alarm, turned out we can keep the package */
466 rr = solv->rules + solv->featurerules + (why - solv->updaterules);
468 rr = solv->rules + why;
471 int mvrp = 0; /* multi-version replacement */
472 FOR_RULELITERALS(rp, pp, rr)
474 if (rp > 0 && solv->decisionmap[rp] > 0 && pool->solvables[rp].repo != solv->installed)
477 if (!(solv->multiversion.size && MAPTST(&solv->multiversion, rp)))
483 /* found only multi-version replacements */
484 /* have to split solution into two parts */
485 queue_push(solutionq, p);
486 queue_push(solutionq, mvrp);
489 queue_push(solutionq, p);
490 queue_push(solutionq, rp);
493 if (why >= solv->bestrules && why < solv->bestrules_end)
498 /* check false positive */
499 rr = solv->rules + why;
500 FOR_RULELITERALS(p, pp, rr)
501 if (p > 0 && solv->decisionmap[p] > 0)
502 return; /* false alarm */
503 /* check update/feature rule */
504 p = solv->bestrules_pkg[why - solv->bestrules];
508 queue_push(solutionq, 0);
509 queue_push(solutionq, solv->ruletojob.elements[-p - solv->jobrules] + 1);
512 if (solv->decisionmap[p] > 0)
514 /* disable best rule by keeping the old package */
515 queue_push(solutionq, SOLVER_SOLUTION_BEST);
516 queue_push(solutionq, p);
519 rr = solv->rules + solv->featurerules + (p - solv->installed->start);
521 rr = solv->rules + solv->updaterules + (p - solv->installed->start);
522 mvrp = 0; /* multi-version replacement */
523 FOR_RULELITERALS(rp, pp, rr)
524 if (rp > 0 && solv->decisionmap[rp] > 0 && pool->solvables[rp].repo != solv->installed)
527 if (!(solv->multiversion.size && MAPTST(&solv->multiversion, rp)))
532 queue_push(solutionq, SOLVER_SOLUTION_BEST); /* split, see above */
533 queue_push(solutionq, mvrp);
534 queue_push(solutionq, p);
535 queue_push(solutionq, 0);
540 queue_push(solutionq, SOLVER_SOLUTION_BEST);
541 queue_push(solutionq, rp);
548 * convert problem data into a form usable for refining.
549 * Returns the number of problems.
552 solver_prepare_solutions(Solver *solv)
556 if (!solv->problems.count)
558 queue_empty(&solv->solutions);
559 queue_push(&solv->solutions, 0); /* dummy so idx is always nonzero */
560 idx = solv->solutions.count;
561 queue_push(&solv->solutions, -1); /* unrefined */
562 /* proofidx stays in position, thus we start with 1 */
563 for (i = 1; i < solv->problems.count; i++)
565 Id p = solv->problems.elements[i];
566 queue_push(&solv->solutions, p);
569 /* end of problem reached */
570 solv->problems.elements[j++] = idx;
571 if (i + 1 >= solv->problems.count)
573 /* start another problem */
574 solv->problems.elements[j++] = solv->problems.elements[++i]; /* copy proofidx */
575 idx = solv->solutions.count;
576 queue_push(&solv->solutions, -1); /* unrefined */
578 solv->problems.count = j;
583 * refine the simple solution rule list provided by
584 * the solver into multiple lists of job modifiers.
587 create_solutions(Solver *solv, int probnr, int solidx)
589 Pool *pool = solv->pool;
591 Queue problem, solution, problems_save, branches_save;
595 int oldmistakes = solv->cleandeps_mistakes ? solv->cleandeps_mistakes->count : 0;
597 int decisioncnt_update;
598 int decisioncnt_keep;
599 int decisioncnt_resolve;
600 int decisioncnt_weak;
601 int decisioncnt_orphan;
603 now = solv_timems(0);
605 /* save decisionq, decisionq_why, decisionmap, and decisioncnt */
606 for (i = 0; i < solv->decisionq.count; i++)
608 Id p = solv->decisionq.elements[i];
609 queue_push(&redoq, p);
610 queue_push(&redoq, solv->decisionq_why.elements[i]);
611 queue_push(&redoq, solv->decisionmap[p > 0 ? p : -p]);
613 decisioncnt_update = solv->decisioncnt_update;
614 decisioncnt_keep = solv->decisioncnt_keep;
615 decisioncnt_resolve = solv->decisioncnt_resolve;
616 decisioncnt_weak = solv->decisioncnt_weak;
617 decisioncnt_orphan = solv->decisioncnt_orphan;
619 /* save problems queue */
620 problems_save = solv->problems;
621 memset(&solv->problems, 0, sizeof(solv->problems));
623 /* save branches queue */
624 branches_save = solv->problems;
625 memset(&solv->branches, 0, sizeof(solv->branches));
627 /* extract problem from queue */
628 queue_init(&problem);
629 for (i = solidx + 1; i < solv->solutions.count; i++)
631 Id v = solv->solutions.elements[i];
634 queue_push(&problem, v);
636 extraflags &= solv->job.elements[-v - 1];
638 if (extraflags == -1)
640 if (problem.count > 1)
641 solv_sort(problem.elements, problem.count, sizeof(Id), problems_sortcmp, &solv->job);
642 queue_push(&problem, 0); /* mark end for refine_suggestion */
645 for (i = 0; i < problem.count; i++)
646 printf("PP %d %d\n", i, problem.elements[i]);
649 /* refine each solution element */
652 queue_init(&solution);
653 for (i = 0; i < problem.count; i++)
655 int solstart = solv->solutions.count;
656 refine_suggestion(solv, problem.elements, problem.elements[i], &solution, essentialok);
657 queue_push(&solv->solutions, 0); /* reserve room for number of elements */
658 for (j = 0; j < solution.count; j++)
659 convertsolution(solv, solution.elements[j], &solv->solutions);
660 if (solv->solutions.count == solstart + 1)
662 solv->solutions.count--; /* this one did not work out */
663 if (nsol || i + 1 < problem.count)
664 continue; /* got one or still hope */
667 /* nothing found, start over */
668 POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "nothing found, re-run with essentialok = 1\n");
673 /* this is bad, we found no solution */
674 /* for now just offer a rule */
675 POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "nothing found, already did essentialok, fake it\n");
676 queue_push(&solv->solutions, 0);
677 for (j = 0; j < problem.count; j++)
679 convertsolution(solv, problem.elements[j], &solv->solutions);
680 if (solv->solutions.count > solstart + 1)
683 if (solv->solutions.count == solstart + 1)
685 solv->solutions.count--;
686 continue; /* sorry */
689 /* patch in number of solution elements */
690 solv->solutions.elements[solstart] = (solv->solutions.count - (solstart + 1)) / 2;
691 queue_push(&solv->solutions, 0); /* add end marker */
692 queue_push(&solv->solutions, 0); /* add end marker */
693 queue_push(&solv->solutions, problem.elements[i]); /* just for bookkeeping */
694 queue_push(&solv->solutions, extraflags & SOLVER_CLEANDEPS); /* our extraflags */
695 solv->solutions.elements[solidx + 1 + nsol++] = solstart;
697 solv->solutions.elements[solidx + 1 + nsol] = 0; /* end marker */
698 solv->solutions.elements[solidx] = nsol;
699 queue_free(&problem);
700 queue_free(&solution);
702 /* restore decisions */
703 memset(solv->decisionmap, 0, pool->nsolvables * sizeof(Id));
704 queue_empty(&solv->decisionq);
705 queue_empty(&solv->decisionq_why);
706 for (i = 0; i < redoq.count; i += 3)
708 Id p = redoq.elements[i];
709 queue_push(&solv->decisionq, p);
710 queue_push(&solv->decisionq_why, redoq.elements[i + 1]);
711 solv->decisionmap[p > 0 ? p : -p] = redoq.elements[i + 2];
714 solv->decisioncnt_update = decisioncnt_update;
715 solv->decisioncnt_keep = decisioncnt_keep;
716 solv->decisioncnt_resolve = decisioncnt_resolve;
717 solv->decisioncnt_weak = decisioncnt_weak;
718 solv->decisioncnt_orphan = decisioncnt_orphan;
720 /* restore problems */
721 queue_free(&solv->problems);
722 solv->problems = problems_save;
724 /* restore branches */
725 queue_free(&solv->branches);
726 solv->branches = branches_save;
728 if (solv->cleandeps_mistakes)
731 queue_truncate(solv->cleandeps_mistakes, oldmistakes);
734 queue_free(solv->cleandeps_mistakes);
735 solv->cleandeps_mistakes = solv_free(solv->cleandeps_mistakes);
739 POOL_DEBUG(SOLV_DEBUG_STATS, "create_solutions for problem #%d took %d ms\n", probnr, solv_timems(now));
743 /**************************************************************************/
746 solver_problem_count(Solver *solv)
748 return solv->problems.count / 2;
752 solver_next_problem(Solver *solv, Id problem)
755 return solv->problems.count ? 1 : 0;
756 return (problem + 1) * 2 - 1 < solv->problems.count ? problem + 1 : 0;
760 solver_solution_count(Solver *solv, Id problem)
762 Id solidx = solv->problems.elements[problem * 2 - 1];
763 if (solv->solutions.elements[solidx] < 0)
764 create_solutions(solv, problem, solidx);
765 return solv->solutions.elements[solidx];
769 solver_next_solution(Solver *solv, Id problem, Id solution)
771 Id solidx = solv->problems.elements[problem * 2 - 1];
772 if (solv->solutions.elements[solidx] < 0)
773 create_solutions(solv, problem, solidx);
774 return solv->solutions.elements[solidx + solution + 1] ? solution + 1 : 0;
778 solver_solutionelement_count(Solver *solv, Id problem, Id solution)
780 Id solidx = solv->problems.elements[problem * 2 - 1];
781 solidx = solv->solutions.elements[solidx + solution];
782 return solv->solutions.elements[solidx];
786 solver_solutionelement_internalid(Solver *solv, Id problem, Id solution)
788 Id solidx = solv->problems.elements[problem * 2 - 1];
789 solidx = solv->solutions.elements[solidx + solution];
790 return solv->solutions.elements[solidx + 2 * solv->solutions.elements[solidx] + 3];
794 solver_solutionelement_extrajobflags(Solver *solv, Id problem, Id solution)
796 Id solidx = solv->problems.elements[problem * 2 - 1];
797 solidx = solv->solutions.elements[solidx + solution];
798 return solv->solutions.elements[solidx + 2 * solv->solutions.elements[solidx] + 4];
803 * return the next item of the proposed solution
804 * here are the possibilities for p / rp and what
805 * the solver expects the application to do:
807 * -------------------------------------------------------
808 * SOLVER_SOLUTION_INFARCH pkgid
809 * -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job
810 * SOLVER_SOLUTION_DISTUPGRADE pkgid
811 * -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job
812 * SOLVER_SOLUTION_BEST pkgid
813 * -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job
814 * SOLVER_SOLUTION_JOB jobidx
815 * -> remove job (jobidx - 1, jobidx) from job queue
816 * SOLVER_SOLUTION_POOLJOB jobidx
817 * -> remove job (jobidx - 1, jobidx) from pool job queue
819 * -> add (SOLVER_ERASE|SOLVER_SOLVABLE, p) to the job
820 * pkgid (> 0) pkgid (> 0)
821 * -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job
822 * (this will replace package p)
824 * Thus, the solver will either ask the application to remove
825 * a specific job from the job queue, or ask to add an install/erase
831 solver_next_solutionelement(Solver *solv, Id problem, Id solution, Id element, Id *p, Id *rp)
833 Id solidx = solv->problems.elements[problem * 2 - 1];
834 solidx = solv->solutions.elements[solidx + solution];
837 solidx += 1 + element * 2;
838 if (!solv->solutions.elements[solidx] && !solv->solutions.elements[solidx + 1])
840 *p = solv->solutions.elements[solidx];
841 *rp = solv->solutions.elements[solidx + 1];
846 solver_take_solutionelement(Solver *solv, Id p, Id rp, Id extrajobflags, Queue *job)
850 if (p == SOLVER_SOLUTION_POOLJOB)
852 solv->pool->pooljobs.elements[rp - 1] = SOLVER_NOOP;
853 solv->pool->pooljobs.elements[rp] = 0;
856 if (p == SOLVER_SOLUTION_JOB)
858 job->elements[rp - 1] = SOLVER_NOOP;
859 job->elements[rp] = 0;
862 if (rp <= 0 && p <= 0)
863 return; /* just in case */
865 p = SOLVER_INSTALL|SOLVER_SOLVABLE|SOLVER_NOTBYUSER|extrajobflags;
869 p = SOLVER_ERASE|SOLVER_SOLVABLE|extrajobflags;
871 for (i = 0; i < job->count; i += 2)
872 if (job->elements[i] == p && job->elements[i + 1] == rp)
874 queue_push2(job, p, rp);
878 solver_take_solution(Solver *solv, Id problem, Id solution, Queue *job)
880 Id p, rp, element = 0;
881 Id extrajobflags = solver_solutionelement_extrajobflags(solv, problem, solution);
882 while ((element = solver_next_solutionelement(solv, problem, solution, element, &p, &rp)) != 0)
883 solver_take_solutionelement(solv, p, rp, extrajobflags, job);
887 /*-------------------------------------------------------------------
893 findproblemrule_internal(Solver *solv, Id idx, Id *reqrp, Id *conrp, Id *sysrp, Id *jobrp, Map *rseen)
896 Id lreqr, lconr, lsysr, ljobr;
899 int i, reqset = 0; /* 0: unset, 1: installed, 2: jobassert, 3: assert */
900 int conset = 0; /* 0: unset, 1: installed */
902 /* find us a jobassert rule */
903 for (i = idx; (rid = solv->learnt_pool.elements[i]) != 0; i++)
905 if (rid < solv->jobrules || rid >= solv->jobrules_end)
907 r = solv->rules + rid;
908 d = r->d < 0 ? -r->d - 1 : r->d;
909 if (!d && r->w2 == 0 && r->p > 0)
916 /* the problem rules are somewhat ordered from "near to the problem" to
917 * "near to the job" */
918 lreqr = lconr = lsysr = ljobr = 0;
919 while ((rid = solv->learnt_pool.elements[idx++]) != 0)
922 if (rid >= solv->learntrules)
924 if (MAPTST(rseen, rid - solv->learntrules))
926 MAPSET(rseen, rid - solv->learntrules);
927 findproblemrule_internal(solv, solv->learnt_why.elements[rid - solv->learntrules], &lreqr, &lconr, &lsysr, &ljobr, rseen);
929 else if ((rid >= solv->jobrules && rid < solv->jobrules_end) || (rid >= solv->infarchrules && rid < solv->infarchrules_end) || (rid >= solv->duprules && rid < solv->duprules_end) || (rid >= solv->bestrules && rid < solv->bestrules_end) || (rid >= solv->yumobsrules && rid <= solv->yumobsrules_end))
934 else if (rid >= solv->updaterules && rid < solv->updaterules_end)
941 assert(rid < solv->pkgrules_end);
942 r = solv->rules + rid;
943 d = r->d < 0 ? -r->d - 1 : r->d;
946 /* prefer conflicts of installed packages */
947 if (solv->installed && !conset)
949 if (r->p < 0 && (solv->pool->solvables[-r->p].repo == solv->installed ||
950 solv->pool->solvables[-r->w2].repo == solv->installed))
961 if (!d && r->w2 == 0 && reqset < 3)
963 if (*reqrp > 0 && r->p < -1)
965 Id op = -solv->rules[*reqrp].p;
966 if (op > 1 && solv->pool->solvables[op].arch != solv->pool->solvables[-r->p].arch)
967 continue; /* different arch, skip */
969 /* prefer assertions */
973 else if (jobassert && r->p == -jobassert)
975 /* prefer rules of job assertions */
979 else if (solv->installed && r->p < 0 && solv->pool->solvables[-r->p].repo == solv->installed && reqset <= 1)
981 /* prefer rules of job installed package so that the user doesn't get confused by strange packages */
990 if (!*reqrp && lreqr)
992 if (!*conrp && lconr)
994 if (!*jobrp && ljobr)
996 if (!*sysrp && lsysr)
1003 * search for a rule that describes the problem to the
1004 * user. Actually a pretty hopeless task that may leave the user
1005 * puzzled. To get all of the needed information use
1006 * solver_findallproblemrules() instead.
1010 solver_findproblemrule(Solver *solv, Id problem)
1012 Id reqr, conr, sysr, jobr;
1013 Id idx = solv->problems.elements[2 * problem - 2];
1015 reqr = conr = sysr = jobr = 0;
1016 map_init(&rseen, solv->learntrules ? solv->nrules - solv->learntrules : 0);
1017 findproblemrule_internal(solv, idx, &reqr, &conr, &sysr, &jobr, &rseen);
1019 /* check if the request is about a not-installed package requiring a installed
1020 * package conflicting with the non-installed package. In that case return the conflict */
1021 if (reqr && conr && solv->installed && solv->rules[reqr].p < 0 && solv->rules[conr].p < 0 && solv->rules[conr].w2 < 0)
1023 Pool *pool = solv->pool;
1024 Solvable *s = pool->solvables - solv->rules[reqr].p;
1025 Solvable *s1 = pool->solvables - solv->rules[conr].p;
1026 Solvable *s2 = pool->solvables - solv->rules[conr].w2;
1028 if (s == s1 && s2->repo == solv->installed)
1029 cp = -solv->rules[conr].w2;
1030 else if (s == s2 && s1->repo == solv->installed)
1031 cp = -solv->rules[conr].p;
1032 if (cp && s1->name != s2->name && s->repo != solv->installed)
1035 Rule *r = solv->rules + reqr;
1036 FOR_RULELITERALS(p, pp, r)
1042 return reqr; /* some requires */
1044 return conr; /* some conflict */
1046 return sysr; /* an update rule */
1048 return jobr; /* a user request */
1053 /*-------------------------------------------------------------------*/
1056 findallproblemrules_internal(Solver *solv, Id idx, Queue *rules, Map *rseen)
1059 while ((rid = solv->learnt_pool.elements[idx++]) != 0)
1061 if (rid >= solv->learntrules)
1063 if (MAPTST(rseen, rid - solv->learntrules))
1065 MAPSET(rseen, rid - solv->learntrules);
1066 findallproblemrules_internal(solv, solv->learnt_why.elements[rid - solv->learntrules], rules, rseen);
1069 queue_pushunique(rules, rid);
1074 * find all problem rule
1076 * return all rules that lead to the problem. This gives the user
1077 * all of the information to understand the problem, but the result
1078 * can be a large number of rules.
1082 solver_findallproblemrules(Solver *solv, Id problem, Queue *rules)
1086 map_init(&rseen, solv->learntrules ? solv->nrules - solv->learntrules : 0);
1087 findallproblemrules_internal(solv, solv->problems.elements[2 * problem - 2], rules, &rseen);
1092 solver_problemruleinfo2str(Solver *solv, SolverRuleinfo type, Id source, Id target, Id dep)
1094 Pool *pool = solv->pool;
1098 case SOLVER_RULE_DISTUPGRADE:
1099 return pool_tmpjoin(pool, pool_solvid2str(pool, source), " does not belong to a distupgrade repository", 0);
1100 case SOLVER_RULE_INFARCH:
1101 return pool_tmpjoin(pool, pool_solvid2str(pool, source), " has inferior architecture", 0);
1102 case SOLVER_RULE_UPDATE:
1103 return pool_tmpjoin(pool, "problem with installed package ", pool_solvid2str(pool, source), 0);
1104 case SOLVER_RULE_JOB:
1105 return "conflicting requests";
1106 case SOLVER_RULE_JOB_UNSUPPORTED:
1107 return "unsupported request";
1108 case SOLVER_RULE_JOB_NOTHING_PROVIDES_DEP:
1109 return pool_tmpjoin(pool, "nothing provides requested ", pool_dep2str(pool, dep), 0);
1110 case SOLVER_RULE_JOB_UNKNOWN_PACKAGE:
1111 return pool_tmpjoin(pool, "package ", pool_dep2str(pool, dep), " does not exist");
1112 case SOLVER_RULE_JOB_PROVIDED_BY_SYSTEM:
1113 return pool_tmpjoin(pool, pool_dep2str(pool, dep), " is provided by the system", 0);
1114 case SOLVER_RULE_PKG:
1115 return "some dependency problem";
1116 case SOLVER_RULE_BEST:
1118 return pool_tmpjoin(pool, "cannot install the best update candidate for package ", pool_solvid2str(pool, source), 0);
1119 return "cannot install the best candidate for the job";
1120 case SOLVER_RULE_PKG_NOT_INSTALLABLE:
1121 return pool_tmpjoin(pool, "package ", pool_solvid2str(pool, source), " is not installable");
1122 case SOLVER_RULE_PKG_NOTHING_PROVIDES_DEP:
1123 s = pool_tmpjoin(pool, "nothing provides ", pool_dep2str(pool, dep), 0);
1124 return pool_tmpappend(pool, s, " needed by ", pool_solvid2str(pool, source));
1125 case SOLVER_RULE_PKG_SAME_NAME:
1126 s = pool_tmpjoin(pool, "cannot install both ", pool_solvid2str(pool, source), 0);
1127 return pool_tmpappend(pool, s, " and ", pool_solvid2str(pool, target));
1128 case SOLVER_RULE_PKG_CONFLICTS:
1129 s = pool_tmpjoin(pool, "package ", pool_solvid2str(pool, source), 0);
1130 s = pool_tmpappend(pool, s, " conflicts with ", pool_dep2str(pool, dep));
1131 return pool_tmpappend(pool, s, " provided by ", pool_solvid2str(pool, target));
1132 case SOLVER_RULE_PKG_OBSOLETES:
1133 s = pool_tmpjoin(pool, "package ", pool_solvid2str(pool, source), 0);
1134 s = pool_tmpappend(pool, s, " obsoletes ", pool_dep2str(pool, dep));
1135 return pool_tmpappend(pool, s, " provided by ", pool_solvid2str(pool, target));
1136 case SOLVER_RULE_PKG_INSTALLED_OBSOLETES:
1137 s = pool_tmpjoin(pool, "installed package ", pool_solvid2str(pool, source), 0);
1138 s = pool_tmpappend(pool, s, " obsoletes ", pool_dep2str(pool, dep));
1139 return pool_tmpappend(pool, s, " provided by ", pool_solvid2str(pool, target));
1140 case SOLVER_RULE_PKG_IMPLICIT_OBSOLETES:
1141 s = pool_tmpjoin(pool, "package ", pool_solvid2str(pool, source), 0);
1142 s = pool_tmpappend(pool, s, " implicitly obsoletes ", pool_dep2str(pool, dep));
1143 return pool_tmpappend(pool, s, " provided by ", pool_solvid2str(pool, target));
1144 case SOLVER_RULE_PKG_REQUIRES:
1145 s = pool_tmpjoin(pool, "package ", pool_solvid2str(pool, source), " requires ");
1146 return pool_tmpappend(pool, s, pool_dep2str(pool, dep), ", but none of the providers can be installed");
1147 case SOLVER_RULE_PKG_SELF_CONFLICT:
1148 s = pool_tmpjoin(pool, "package ", pool_solvid2str(pool, source), " conflicts with ");
1149 return pool_tmpappend(pool, s, pool_dep2str(pool, dep), " provided by itself");
1150 case SOLVER_RULE_YUMOBS:
1151 s = pool_tmpjoin(pool, "both package ", pool_solvid2str(pool, source), " and ");
1152 s = pool_tmpjoin(pool, s, pool_solvid2str(pool, target), " obsolete ");
1153 return pool_tmpappend(pool, s, pool_dep2str(pool, dep), 0);
1155 return "bad problem rule type";
1159 /* convenience function */
1161 solver_problem2str(Solver *solv, Id problem)
1163 Id type, source, target, dep;
1164 Id r = solver_findproblemrule(solv, problem);
1166 return "no problem rule?";
1167 type = solver_ruleinfo(solv, r, &source, &target, &dep);
1168 return solver_problemruleinfo2str(solv, type, source, target, dep);
1172 solver_solutionelement2str(Solver *solv, Id p, Id rp)
1174 Pool *pool = solv->pool;
1175 if (p == SOLVER_SOLUTION_JOB || p == SOLVER_SOLUTION_POOLJOB)
1178 if (p == SOLVER_SOLUTION_JOB)
1179 rp += solv->pooljobcnt;
1180 how = solv->job.elements[rp - 1];
1181 what = solv->job.elements[rp];
1182 return pool_tmpjoin(pool, "do not ask to ", pool_job2str(pool, how, what, 0), 0);
1184 else if (p == SOLVER_SOLUTION_INFARCH)
1186 Solvable *s = pool->solvables + rp;
1187 if (solv->installed && s->repo == solv->installed)
1188 return pool_tmpjoin(pool, "keep ", pool_solvable2str(pool, s), " despite the inferior architecture");
1190 return pool_tmpjoin(pool, "install ", pool_solvable2str(pool, s), " despite the inferior architecture");
1192 else if (p == SOLVER_SOLUTION_DISTUPGRADE)
1194 Solvable *s = pool->solvables + rp;
1195 if (solv->installed && s->repo == solv->installed)
1196 return pool_tmpjoin(pool, "keep obsolete ", pool_solvable2str(pool, s), 0);
1198 return pool_tmpjoin(pool, "install ", pool_solvable2str(pool, s), " from excluded repository");
1200 else if (p == SOLVER_SOLUTION_BEST)
1202 Solvable *s = pool->solvables + rp;
1203 if (solv->installed && s->repo == solv->installed)
1204 return pool_tmpjoin(pool, "keep old ", pool_solvable2str(pool, s), 0);
1206 return pool_tmpjoin(pool, "install ", pool_solvable2str(pool, s), " despite the old version");
1208 else if (p > 0 && rp == 0)
1209 return pool_tmpjoin(pool, "allow deinstallation of ", pool_solvid2str(pool, p), 0);
1210 else if (p > 0 && rp > 0)
1212 const char *sp = pool_solvid2str(pool, p);
1213 const char *srp = pool_solvid2str(pool, rp);
1214 const char *str = pool_tmpjoin(pool, "allow replacement of ", sp, 0);
1215 return pool_tmpappend(pool, str, " with ", srp);
1218 return "bad solution element";