Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
Fetching contributors…

Cannot retrieve contributors at this time

1221 lines (1144 sloc) 38.304 kb
/*
* Copyright (c) 2007-2009, Novell Inc.
*
* This program is licensed under the BSD license, read LICENSE.BSD
* for further information
*/
/*
* problems.c
*
*/
#include <stdio.h>
#include <stdlib.h>
#include <unistd.h>
#include <string.h>
#include <assert.h>
#include "solver.h"
#include "solver_private.h"
#include "bitmap.h"
#include "pool.h"
#include "util.h"
#include "evr.h"
#include "solverdebug.h"
/**********************************************************************************/
/* a problem is an item on the solver's problem list. It can either be >0, in that
* case it is a update/infarch/dup rule, or it can be <0, which makes it refer to a job
* consisting of multiple job rules.
*/
void
solver_disableproblem(Solver *solv, Id v)
{
Rule *r;
int i;
Id *jp;
if (v > 0)
{
if (v >= solv->infarchrules && v < solv->infarchrules_end)
{
Pool *pool = solv->pool;
Id name = pool->solvables[-solv->rules[v].p].name;
while (v > solv->infarchrules && pool->solvables[-solv->rules[v - 1].p].name == name)
v--;
for (; v < solv->infarchrules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
solver_disablerule(solv, solv->rules + v);
return;
}
if (v >= solv->duprules && v < solv->duprules_end)
{
Pool *pool = solv->pool;
Id name = pool->solvables[-solv->rules[v].p].name;
while (v > solv->duprules && pool->solvables[-solv->rules[v - 1].p].name == name)
v--;
for (; v < solv->duprules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
solver_disablerule(solv, solv->rules + v);
return;
}
solver_disablerule(solv, solv->rules + v);
#if 0
/* XXX: doesn't work */
if (v >= solv->updaterules && v < solv->updaterules_end)
{
/* enable feature rule if we disabled the update rule */
r = solv->rules + (v - solv->updaterules + solv->featurerules);
if (r->p)
solver_enablerule(solv, r);
}
#endif
return;
}
v = -(v + 1);
jp = solv->ruletojob.elements;
for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++, jp++)
if (*jp == v)
solver_disablerule(solv, r);
}
/*-------------------------------------------------------------------
* enableproblem
*/
void
solver_enableproblem(Solver *solv, Id v)
{
Rule *r;
int i;
Id *jp;
if (v > 0)
{
if (v >= solv->infarchrules && v < solv->infarchrules_end)
{
Pool *pool = solv->pool;
Id name = pool->solvables[-solv->rules[v].p].name;
while (v > solv->infarchrules && pool->solvables[-solv->rules[v - 1].p].name == name)
v--;
for (; v < solv->infarchrules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
solver_enablerule(solv, solv->rules + v);
return;
}
if (v >= solv->duprules && v < solv->duprules_end)
{
Pool *pool = solv->pool;
Id name = pool->solvables[-solv->rules[v].p].name;
while (v > solv->duprules && pool->solvables[-solv->rules[v - 1].p].name == name)
v--;
for (; v < solv->duprules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
solver_enablerule(solv, solv->rules + v);
return;
}
if (v >= solv->featurerules && v < solv->featurerules_end)
{
/* do not enable feature rule if update rule is enabled */
r = solv->rules + (v - solv->featurerules + solv->updaterules);
if (r->d >= 0)
return;
}
solver_enablerule(solv, solv->rules + v);
if (v >= solv->updaterules && v < solv->updaterules_end)
{
/* disable feature rule when enabling update rule */
r = solv->rules + (v - solv->updaterules + solv->featurerules);
if (r->p)
solver_disablerule(solv, r);
}
return;
}
v = -(v + 1);
jp = solv->ruletojob.elements;
for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++, jp++)
if (*jp == v)
solver_enablerule(solv, r);
}
/*-------------------------------------------------------------------
* enable weak rules
*
* Reenable all disabled weak rules (marked in weakrulemap)
*
*/
static void
enableweakrules(Solver *solv)
{
int i;
Rule *r;
for (i = 1, r = solv->rules + i; i < solv->learntrules; i++, r++)
{
if (r->d >= 0) /* already enabled? */
continue;
if (!MAPTST(&solv->weakrulemap, i))
continue;
solver_enablerule(solv, r);
}
/* make sure broken orphan rules stay disabled */
if (solv->brokenorphanrules)
for (i = 0; i < solv->brokenorphanrules->count; i++)
solver_disablerule(solv, solv->rules + solv->brokenorphanrules->elements[i]);
}
/*-------------------------------------------------------------------
*
* refine_suggestion
*
* at this point, all rules that led to conflicts are disabled.
* we re-enable all rules of a problem set but rule "sug", then
* continue to disable more rules until there as again a solution.
*/
/* FIXME: think about conflicting assertions */
static void
refine_suggestion(Solver *solv, Id *problem, Id sug, Queue *refined, int essentialok)
{
Pool *pool = solv->pool;
int i, j;
Id v;
Queue disabled;
int disabledcnt;
IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS)
{
POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "refine_suggestion start\n");
for (i = 0; problem[i]; i++)
{
if (problem[i] == sug)
POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "=> ");
solver_printproblem(solv, problem[i]);
}
}
queue_empty(refined);
if (!essentialok && sug < 0 && (solv->job.elements[-sug - 1] & SOLVER_ESSENTIAL) != 0)
return;
queue_init(&disabled);
queue_push(refined, sug);
/* re-enable all problem rules with the exception of "sug"(gestion) */
solver_reset(solv);
for (i = 0; problem[i]; i++)
if (problem[i] != sug)
solver_enableproblem(solv, problem[i]);
if (sug < 0)
solver_reenablepolicyrules(solv, -sug);
else if (sug >= solv->updaterules && sug < solv->updaterules_end)
{
/* enable feature rule */
Rule *r = solv->rules + solv->featurerules + (sug - solv->updaterules);
if (r->p)
solver_enablerule(solv, r);
}
enableweakrules(solv);
for (;;)
{
int njob, nfeature, nupdate, pass;
queue_empty(&solv->problems);
solver_reset(solv);
if (!solv->problems.count)
solver_run_sat(solv, 0, 0);
if (!solv->problems.count)
{
POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "no more problems!\n");
break; /* great, no more problems */
}
disabledcnt = disabled.count;
/* start with 1 to skip over proof index */
njob = nfeature = nupdate = 0;
for (pass = 0; pass < 2; pass++)
{
for (i = 1; i < solv->problems.count - 1; i++)
{
/* ignore solutions in refined */
v = solv->problems.elements[i];
if (v == 0)
break; /* end of problem reached */
if (sug != v)
{
/* check if v is in the given problems list
* we allow disabling all problem rules *after* sug in
* pass 2, to prevent getting the same solution twice */
for (j = 0; problem[j]; j++)
if (problem[j] == v || (pass && problem[j] == sug))
break;
if (problem[j] == v)
continue;
}
if (v >= solv->featurerules && v < solv->featurerules_end)
nfeature++;
else if (v > 0)
nupdate++;
else
{
if (!essentialok && (solv->job.elements[-v - 1] & SOLVER_ESSENTIAL) != 0)
continue; /* not that one! */
njob++;
}
queue_push(&disabled, v);
}
if (disabled.count != disabledcnt)
break;
}
if (disabled.count == disabledcnt)
{
/* no solution found, this was an invalid suggestion! */
POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "no solution found!\n");
refined->count = 0;
break;
}
if (!njob && nupdate && nfeature)
{
/* got only update rules, filter out feature rules */
POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "throwing away feature rules\n");
for (i = j = disabledcnt; i < disabled.count; i++)
{
v = disabled.elements[i];
if (v < solv->featurerules || v >= solv->featurerules_end)
disabled.elements[j++] = v;
}
disabled.count = j;
nfeature = 0;
}
if (disabled.count == disabledcnt + 1)
{
/* just one suggestion, add it to refined list */
v = disabled.elements[disabledcnt];
if (!nfeature && v != sug)
queue_push(refined, v); /* do not record feature rules */
solver_disableproblem(solv, v);
if (v >= solv->updaterules && v < solv->updaterules_end)
{
Rule *r = solv->rules + (v - solv->updaterules + solv->featurerules);
if (r->p)
solver_enablerule(solv, r); /* enable corresponding feature rule */
}
if (v < 0)
solver_reenablepolicyrules(solv, -v);
}
else
{
/* more than one solution, disable all */
/* do not push anything on refine list, as we do not know which solution to choose */
/* thus, the user will get another problem if he selects this solution, where he
* can choose the right one */
IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS)
{
POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "more than one solution found:\n");
for (i = disabledcnt; i < disabled.count; i++)
solver_printproblem(solv, disabled.elements[i]);
}
for (i = disabledcnt; i < disabled.count; i++)
{
v = disabled.elements[i];
solver_disableproblem(solv, v);
if (v >= solv->updaterules && v < solv->updaterules_end)
{
Rule *r = solv->rules + (v - solv->updaterules + solv->featurerules);
if (r->p)
solver_enablerule(solv, r);
}
}
}
}
/* all done, get us back into the same state as before */
/* enable refined rules again */
for (i = 0; i < disabled.count; i++)
solver_enableproblem(solv, disabled.elements[i]);
queue_free(&disabled);
/* reset policy rules */
for (i = 0; problem[i]; i++)
solver_enableproblem(solv, problem[i]);
solver_disablepolicyrules(solv);
/* disable problem rules again */
for (i = 0; problem[i]; i++)
solver_disableproblem(solv, problem[i]);
POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "refine_suggestion end\n");
}
/*-------------------------------------------------------------------
* sorting helper for problems
*
* bring update rules before job rules
* make essential job rules last
*/
static int
problems_sortcmp(const void *ap, const void *bp, void *dp)
{
Queue *job = dp;
Id a = *(Id *)ap, b = *(Id *)bp;
if (a < 0 && b > 0)
return 1;
if (a > 0 && b < 0)
return -1;
if (a < 0 && b < 0)
{
int af = job->elements[-a - 1] & SOLVER_ESSENTIAL;
int bf = job->elements[-b - 1] & SOLVER_ESSENTIAL;
int x = af - bf;
if (x)
return x;
}
return a - b;
}
/*
* convert a solution rule into a job modifier
*/
static void
convertsolution(Solver *solv, Id why, Queue *solutionq)
{
Pool *pool = solv->pool;
if (why < 0)
{
why = -why;
if (why < solv->pooljobcnt)
{
queue_push(solutionq, SOLVER_SOLUTION_POOLJOB);
queue_push(solutionq, why);
}
else
{
queue_push(solutionq, SOLVER_SOLUTION_JOB);
queue_push(solutionq, why - solv->pooljobcnt);
}
return;
}
if (why >= solv->infarchrules && why < solv->infarchrules_end)
{
Id p, name;
/* infarch rule, find replacement */
assert(solv->rules[why].p < 0);
name = pool->solvables[-solv->rules[why].p].name;
while (why > solv->infarchrules && pool->solvables[-solv->rules[why - 1].p].name == name)
why--;
p = 0;
for (; why < solv->infarchrules_end && pool->solvables[-solv->rules[why].p].name == name; why++)
if (solv->decisionmap[-solv->rules[why].p] > 0)
{
p = -solv->rules[why].p;
break;
}
if (!p)
return; /* false alarm */
queue_push(solutionq, SOLVER_SOLUTION_INFARCH);
queue_push(solutionq, p);
return;
}
if (why >= solv->duprules && why < solv->duprules_end)
{
Id p, name;
/* dist upgrade rule, find replacement */
assert(solv->rules[why].p < 0);
name = pool->solvables[-solv->rules[why].p].name;
while (why > solv->duprules && pool->solvables[-solv->rules[why - 1].p].name == name)
why--;
p = 0;
for (; why < solv->duprules_end && pool->solvables[-solv->rules[why].p].name == name; why++)
if (solv->decisionmap[-solv->rules[why].p] > 0)
{
p = -solv->rules[why].p;
break;
}
if (!p)
return; /* false alarm */
queue_push(solutionq, SOLVER_SOLUTION_DISTUPGRADE);
queue_push(solutionq, p);
return;
}
if (why >= solv->updaterules && why < solv->updaterules_end)
{
/* update rule, find replacement package */
Id p, pp, rp = 0;
Rule *rr;
/* check if this is a false positive, i.e. the update rule is fulfilled */
rr = solv->rules + why;
FOR_RULELITERALS(p, pp, rr)
if (p > 0 && solv->decisionmap[p] > 0)
return; /* false alarm */
p = solv->installed->start + (why - solv->updaterules);
if (solv->dupmap_all && solv->rules[why].p != p && solv->decisionmap[p] > 0)
{
/* distupgrade case, allow to keep old package */
queue_push(solutionq, SOLVER_SOLUTION_DISTUPGRADE);
queue_push(solutionq, p);
return;
}
if (solv->decisionmap[p] > 0)
return; /* false alarm, turned out we can keep the package */
rr = solv->rules + solv->featurerules + (why - solv->updaterules);
if (!rr->p)
rr = solv->rules + why;
if (rr->w2)
{
int mvrp = 0; /* multi-version replacement */
FOR_RULELITERALS(rp, pp, rr)
{
if (rp > 0 && solv->decisionmap[rp] > 0 && pool->solvables[rp].repo != solv->installed)
{
mvrp = rp;
if (!(solv->multiversion.size && MAPTST(&solv->multiversion, rp)))
break;
}
}
if (!rp && mvrp)
{
/* found only multi-version replacements */
/* have to split solution into two parts */
queue_push(solutionq, p);
queue_push(solutionq, mvrp);
}
}
queue_push(solutionq, p);
queue_push(solutionq, rp);
return;
}
if (why >= solv->bestrules && why < solv->bestrules_end)
{
int mvrp;
Id p, pp, rp = 0;
Rule *rr;
/* check false positive */
rr = solv->rules + why;
FOR_RULELITERALS(p, pp, rr)
if (p > 0 && solv->decisionmap[p] > 0)
return; /* false alarm */
/* check update/feature rule */
p = solv->bestrules_pkg[why - solv->bestrules];
if (p < 0)
{
/* install job */
queue_push(solutionq, 0);
queue_push(solutionq, solv->ruletojob.elements[-p - solv->jobrules] + 1);
return;
}
if (solv->decisionmap[p] > 0)
{
/* disable best rule by keeping the old package */
queue_push(solutionq, SOLVER_SOLUTION_BEST);
queue_push(solutionq, p);
return;
}
rr = solv->rules + solv->featurerules + (p - solv->installed->start);
if (!rr->p)
rr = solv->rules + solv->updaterules + (p - solv->installed->start);
mvrp = 0; /* multi-version replacement */
FOR_RULELITERALS(rp, pp, rr)
if (rp > 0 && solv->decisionmap[rp] > 0 && pool->solvables[rp].repo != solv->installed)
{
mvrp = rp;
if (!(solv->multiversion.size && MAPTST(&solv->multiversion, rp)))
break;
}
if (!rp && mvrp)
{
queue_push(solutionq, SOLVER_SOLUTION_BEST); /* split, see above */
queue_push(solutionq, mvrp);
queue_push(solutionq, p);
queue_push(solutionq, 0);
return;
}
if (rp)
{
queue_push(solutionq, SOLVER_SOLUTION_BEST);
queue_push(solutionq, rp);
}
return;
}
}
/*
* convert problem data into a form usable for refining.
* Returns the number of problems.
*/
int
solver_prepare_solutions(Solver *solv)
{
int i, j = 1, idx;
if (!solv->problems.count)
return 0;
queue_empty(&solv->solutions);
queue_push(&solv->solutions, 0); /* dummy so idx is always nonzero */
idx = solv->solutions.count;
queue_push(&solv->solutions, -1); /* unrefined */
/* proofidx stays in position, thus we start with 1 */
for (i = 1; i < solv->problems.count; i++)
{
Id p = solv->problems.elements[i];
queue_push(&solv->solutions, p);
if (p)
continue;
/* end of problem reached */
solv->problems.elements[j++] = idx;
if (i + 1 >= solv->problems.count)
break;
/* start another problem */
solv->problems.elements[j++] = solv->problems.elements[++i]; /* copy proofidx */
idx = solv->solutions.count;
queue_push(&solv->solutions, -1); /* unrefined */
}
solv->problems.count = j;
return j / 2;
}
/*
* refine the simple solution rule list provided by
* the solver into multiple lists of job modifiers.
*/
static void
create_solutions(Solver *solv, int probnr, int solidx)
{
Pool *pool = solv->pool;
Queue redoq;
Queue problem, solution, problems_save, branches_save;
int i, j, nsol;
int essentialok;
unsigned int now;
int oldmistakes = solv->cleandeps_mistakes ? solv->cleandeps_mistakes->count : 0;
Id extraflags = -1;
int decisioncnt_update;
int decisioncnt_keep;
int decisioncnt_resolve;
int decisioncnt_weak;
int decisioncnt_orphan;
now = solv_timems(0);
queue_init(&redoq);
/* save decisionq, decisionq_why, decisionmap, and decisioncnt */
for (i = 0; i < solv->decisionq.count; i++)
{
Id p = solv->decisionq.elements[i];
queue_push(&redoq, p);
queue_push(&redoq, solv->decisionq_why.elements[i]);
queue_push(&redoq, solv->decisionmap[p > 0 ? p : -p]);
}
decisioncnt_update = solv->decisioncnt_update;
decisioncnt_keep = solv->decisioncnt_keep;
decisioncnt_resolve = solv->decisioncnt_resolve;
decisioncnt_weak = solv->decisioncnt_weak;
decisioncnt_orphan = solv->decisioncnt_orphan;
/* save problems queue */
problems_save = solv->problems;
memset(&solv->problems, 0, sizeof(solv->problems));
/* save branches queue */
branches_save = solv->problems;
memset(&solv->branches, 0, sizeof(solv->branches));
/* extract problem from queue */
queue_init(&problem);
for (i = solidx + 1; i < solv->solutions.count; i++)
{
Id v = solv->solutions.elements[i];
if (!v)
break;
queue_push(&problem, v);
if (v < 0)
extraflags &= solv->job.elements[-v - 1];
}
if (extraflags == -1)
extraflags = 0;
if (problem.count > 1)
solv_sort(problem.elements, problem.count, sizeof(Id), problems_sortcmp, &solv->job);
queue_push(&problem, 0); /* mark end for refine_suggestion */
problem.count--;
#if 0
for (i = 0; i < problem.count; i++)
printf("PP %d %d\n", i, problem.elements[i]);
#endif
/* refine each solution element */
nsol = 0;
essentialok = 0;
queue_init(&solution);
for (i = 0; i < problem.count; i++)
{
int solstart = solv->solutions.count;
refine_suggestion(solv, problem.elements, problem.elements[i], &solution, essentialok);
queue_push(&solv->solutions, 0); /* reserve room for number of elements */
for (j = 0; j < solution.count; j++)
convertsolution(solv, solution.elements[j], &solv->solutions);
if (solv->solutions.count == solstart + 1)
{
solv->solutions.count--; /* this one did not work out */
if (nsol || i + 1 < problem.count)
continue; /* got one or still hope */
if (!essentialok)
{
/* nothing found, start over */
POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "nothing found, re-run with essentialok = 1\n");
essentialok = 1;
i = -1;
continue;
}
/* this is bad, we found no solution */
/* for now just offer a rule */
POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "nothing found, already did essentialok, fake it\n");
queue_push(&solv->solutions, 0);
for (j = 0; j < problem.count; j++)
{
convertsolution(solv, problem.elements[j], &solv->solutions);
if (solv->solutions.count > solstart + 1)
break;
}
if (solv->solutions.count == solstart + 1)
{
solv->solutions.count--;
continue; /* sorry */
}
}
/* patch in number of solution elements */
solv->solutions.elements[solstart] = (solv->solutions.count - (solstart + 1)) / 2;
queue_push(&solv->solutions, 0); /* add end marker */
queue_push(&solv->solutions, 0); /* add end marker */
queue_push(&solv->solutions, problem.elements[i]); /* just for bookkeeping */
queue_push(&solv->solutions, extraflags & SOLVER_CLEANDEPS); /* our extraflags */
solv->solutions.elements[solidx + 1 + nsol++] = solstart;
}
solv->solutions.elements[solidx + 1 + nsol] = 0; /* end marker */
solv->solutions.elements[solidx] = nsol;
queue_free(&problem);
queue_free(&solution);
/* restore decisions */
memset(solv->decisionmap, 0, pool->nsolvables * sizeof(Id));
queue_empty(&solv->decisionq);
queue_empty(&solv->decisionq_why);
for (i = 0; i < redoq.count; i += 3)
{
Id p = redoq.elements[i];
queue_push(&solv->decisionq, p);
queue_push(&solv->decisionq_why, redoq.elements[i + 1]);
solv->decisionmap[p > 0 ? p : -p] = redoq.elements[i + 2];
}
queue_free(&redoq);
solv->decisioncnt_update = decisioncnt_update;
solv->decisioncnt_keep = decisioncnt_keep;
solv->decisioncnt_resolve = decisioncnt_resolve;
solv->decisioncnt_weak = decisioncnt_weak;
solv->decisioncnt_orphan = decisioncnt_orphan;
/* restore problems */
queue_free(&solv->problems);
solv->problems = problems_save;
/* restore branches */
queue_free(&solv->branches);
solv->branches = branches_save;
if (solv->cleandeps_mistakes)
{
if (oldmistakes)
queue_truncate(solv->cleandeps_mistakes, oldmistakes);
else
{
queue_free(solv->cleandeps_mistakes);
solv->cleandeps_mistakes = solv_free(solv->cleandeps_mistakes);
}
}
POOL_DEBUG(SOLV_DEBUG_STATS, "create_solutions for problem #%d took %d ms\n", probnr, solv_timems(now));
}
/**************************************************************************/
unsigned int
solver_problem_count(Solver *solv)
{
return solv->problems.count / 2;
}
Id
solver_next_problem(Solver *solv, Id problem)
{
if (!problem)
return solv->problems.count ? 1 : 0;
return (problem + 1) * 2 - 1 < solv->problems.count ? problem + 1 : 0;
}
unsigned int
solver_solution_count(Solver *solv, Id problem)
{
Id solidx = solv->problems.elements[problem * 2 - 1];
if (solv->solutions.elements[solidx] < 0)
create_solutions(solv, problem, solidx);
return solv->solutions.elements[solidx];
}
Id
solver_next_solution(Solver *solv, Id problem, Id solution)
{
Id solidx = solv->problems.elements[problem * 2 - 1];
if (solv->solutions.elements[solidx] < 0)
create_solutions(solv, problem, solidx);
return solv->solutions.elements[solidx + solution + 1] ? solution + 1 : 0;
}
unsigned int
solver_solutionelement_count(Solver *solv, Id problem, Id solution)
{
Id solidx = solv->problems.elements[problem * 2 - 1];
solidx = solv->solutions.elements[solidx + solution];
return solv->solutions.elements[solidx];
}
Id
solver_solutionelement_internalid(Solver *solv, Id problem, Id solution)
{
Id solidx = solv->problems.elements[problem * 2 - 1];
solidx = solv->solutions.elements[solidx + solution];
return solv->solutions.elements[solidx + 2 * solv->solutions.elements[solidx] + 3];
}
Id
solver_solutionelement_extrajobflags(Solver *solv, Id problem, Id solution)
{
Id solidx = solv->problems.elements[problem * 2 - 1];
solidx = solv->solutions.elements[solidx + solution];
return solv->solutions.elements[solidx + 2 * solv->solutions.elements[solidx] + 4];
}
/*
* return the next item of the proposed solution
* here are the possibilities for p / rp and what
* the solver expects the application to do:
* p rp
* -------------------------------------------------------
* SOLVER_SOLUTION_INFARCH pkgid
* -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job
* SOLVER_SOLUTION_DISTUPGRADE pkgid
* -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job
* SOLVER_SOLUTION_BEST pkgid
* -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job
* SOLVER_SOLUTION_JOB jobidx
* -> remove job (jobidx - 1, jobidx) from job queue
* SOLVER_SOLUTION_POOLJOB jobidx
* -> remove job (jobidx - 1, jobidx) from pool job queue
* pkgid (> 0) 0
* -> add (SOLVER_ERASE|SOLVER_SOLVABLE, p) to the job
* pkgid (> 0) pkgid (> 0)
* -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job
* (this will replace package p)
*
* Thus, the solver will either ask the application to remove
* a specific job from the job queue, or ask to add an install/erase
* job to it.
*
*/
Id
solver_next_solutionelement(Solver *solv, Id problem, Id solution, Id element, Id *p, Id *rp)
{
Id solidx = solv->problems.elements[problem * 2 - 1];
solidx = solv->solutions.elements[solidx + solution];
if (!solidx)
return 0;
solidx += 1 + element * 2;
if (!solv->solutions.elements[solidx] && !solv->solutions.elements[solidx + 1])
return 0;
*p = solv->solutions.elements[solidx];
*rp = solv->solutions.elements[solidx + 1];
return element + 1;
}
void
solver_take_solutionelement(Solver *solv, Id p, Id rp, Id extrajobflags, Queue *job)
{
int i;
if (p == SOLVER_SOLUTION_POOLJOB)
{
solv->pool->pooljobs.elements[rp - 1] = SOLVER_NOOP;
solv->pool->pooljobs.elements[rp] = 0;
return;
}
if (p == SOLVER_SOLUTION_JOB)
{
job->elements[rp - 1] = SOLVER_NOOP;
job->elements[rp] = 0;
return;
}
if (rp <= 0 && p <= 0)
return; /* just in case */
if (rp > 0)
p = SOLVER_INSTALL|SOLVER_SOLVABLE|SOLVER_NOTBYUSER|extrajobflags;
else
{
rp = p;
p = SOLVER_ERASE|SOLVER_SOLVABLE|extrajobflags;
}
for (i = 0; i < job->count; i += 2)
if (job->elements[i] == p && job->elements[i + 1] == rp)
return;
queue_push2(job, p, rp);
}
void
solver_take_solution(Solver *solv, Id problem, Id solution, Queue *job)
{
Id p, rp, element = 0;
Id extrajobflags = solver_solutionelement_extrajobflags(solv, problem, solution);
while ((element = solver_next_solutionelement(solv, problem, solution, element, &p, &rp)) != 0)
solver_take_solutionelement(solv, p, rp, extrajobflags, job);
}
/*-------------------------------------------------------------------
*
* find problem rule
*/
static void
findproblemrule_internal(Solver *solv, Id idx, Id *reqrp, Id *conrp, Id *sysrp, Id *jobrp, Map *rseen)
{
Id rid, d;
Id lreqr, lconr, lsysr, ljobr;
Rule *r;
Id jobassert = 0;
int i, reqset = 0; /* 0: unset, 1: installed, 2: jobassert, 3: assert */
int conset = 0; /* 0: unset, 1: installed */
/* find us a jobassert rule */
for (i = idx; (rid = solv->learnt_pool.elements[i]) != 0; i++)
{
if (rid < solv->jobrules || rid >= solv->jobrules_end)
continue;
r = solv->rules + rid;
d = r->d < 0 ? -r->d - 1 : r->d;
if (!d && r->w2 == 0 && r->p > 0)
{
jobassert = r->p;
break;
}
}
/* the problem rules are somewhat ordered from "near to the problem" to
* "near to the job" */
lreqr = lconr = lsysr = ljobr = 0;
while ((rid = solv->learnt_pool.elements[idx++]) != 0)
{
assert(rid > 0);
if (rid >= solv->learntrules)
{
if (MAPTST(rseen, rid - solv->learntrules))
continue;
MAPSET(rseen, rid - solv->learntrules);
findproblemrule_internal(solv, solv->learnt_why.elements[rid - solv->learntrules], &lreqr, &lconr, &lsysr, &ljobr, rseen);
}
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))
{
if (!*jobrp)
*jobrp = rid;
}
else if (rid >= solv->updaterules && rid < solv->updaterules_end)
{
if (!*sysrp)
*sysrp = rid;
}
else
{
assert(rid < solv->pkgrules_end);
r = solv->rules + rid;
d = r->d < 0 ? -r->d - 1 : r->d;
if (!d && r->w2 < 0)
{
/* prefer conflicts of installed packages */
if (solv->installed && !conset)
{
if (r->p < 0 && (solv->pool->solvables[-r->p].repo == solv->installed ||
solv->pool->solvables[-r->w2].repo == solv->installed))
{
*conrp = rid;
conset = 1;
}
}
if (!*conrp)
*conrp = rid;
}
else
{
if (!d && r->w2 == 0 && reqset < 3)
{
if (*reqrp > 0 && r->p < -1)
{
Id op = -solv->rules[*reqrp].p;
if (op > 1 && solv->pool->solvables[op].arch != solv->pool->solvables[-r->p].arch)
continue; /* different arch, skip */
}
/* prefer assertions */
*reqrp = rid;
reqset = 3;
}
else if (jobassert && r->p == -jobassert)
{
/* prefer rules of job assertions */
*reqrp = rid;
reqset = 2;
}
else if (solv->installed && r->p < 0 && solv->pool->solvables[-r->p].repo == solv->installed && reqset <= 1)
{
/* prefer rules of job installed package so that the user doesn't get confused by strange packages */
*reqrp = rid;
reqset = 1;
}
else if (!*reqrp)
*reqrp = rid;
}
}
}
if (!*reqrp && lreqr)
*reqrp = lreqr;
if (!*conrp && lconr)
*conrp = lconr;
if (!*jobrp && ljobr)
*jobrp = ljobr;
if (!*sysrp && lsysr)
*sysrp = lsysr;
}
/*
* find problem rule
*
* search for a rule that describes the problem to the
* user. Actually a pretty hopeless task that may leave the user
* puzzled. To get all of the needed information use
* solver_findallproblemrules() instead.
*/
Id
solver_findproblemrule(Solver *solv, Id problem)
{
Id reqr, conr, sysr, jobr;
Id idx = solv->problems.elements[2 * problem - 2];
Map rseen;
reqr = conr = sysr = jobr = 0;
map_init(&rseen, solv->learntrules ? solv->nrules - solv->learntrules : 0);
findproblemrule_internal(solv, idx, &reqr, &conr, &sysr, &jobr, &rseen);
map_free(&rseen);
/* check if the request is about a not-installed package requiring a installed
* package conflicting with the non-installed package. In that case return the conflict */
if (reqr && conr && solv->installed && solv->rules[reqr].p < 0 && solv->rules[conr].p < 0 && solv->rules[conr].w2 < 0)
{
Pool *pool = solv->pool;
Solvable *s = pool->solvables - solv->rules[reqr].p;
Solvable *s1 = pool->solvables - solv->rules[conr].p;
Solvable *s2 = pool->solvables - solv->rules[conr].w2;
Id cp = 0;
if (s == s1 && s2->repo == solv->installed)
cp = -solv->rules[conr].w2;
else if (s == s2 && s1->repo == solv->installed)
cp = -solv->rules[conr].p;
if (cp && s1->name != s2->name && s->repo != solv->installed)
{
Id p, pp;
Rule *r = solv->rules + reqr;
FOR_RULELITERALS(p, pp, r)
if (p == cp)
return conr;
}
}
if (reqr)
return reqr; /* some requires */
if (conr)
return conr; /* some conflict */
if (sysr)
return sysr; /* an update rule */
if (jobr)
return jobr; /* a user request */
assert(0);
return 0;
}
/*-------------------------------------------------------------------*/
static void
findallproblemrules_internal(Solver *solv, Id idx, Queue *rules, Map *rseen)
{
Id rid;
while ((rid = solv->learnt_pool.elements[idx++]) != 0)
{
if (rid >= solv->learntrules)
{
if (MAPTST(rseen, rid - solv->learntrules))
continue;
MAPSET(rseen, rid - solv->learntrules);
findallproblemrules_internal(solv, solv->learnt_why.elements[rid - solv->learntrules], rules, rseen);
continue;
}
queue_pushunique(rules, rid);
}
}
/*
* find all problem rule
*
* return all rules that lead to the problem. This gives the user
* all of the information to understand the problem, but the result
* can be a large number of rules.
*/
void
solver_findallproblemrules(Solver *solv, Id problem, Queue *rules)
{
Map rseen;
queue_empty(rules);
map_init(&rseen, solv->learntrules ? solv->nrules - solv->learntrules : 0);
findallproblemrules_internal(solv, solv->problems.elements[2 * problem - 2], rules, &rseen);
map_free(&rseen);
}
const char *
solver_problemruleinfo2str(Solver *solv, SolverRuleinfo type, Id source, Id target, Id dep)
{
Pool *pool = solv->pool;
char *s;
switch (type)
{
case SOLVER_RULE_DISTUPGRADE:
return pool_tmpjoin(pool, pool_solvid2str(pool, source), " does not belong to a distupgrade repository", 0);
case SOLVER_RULE_INFARCH:
return pool_tmpjoin(pool, pool_solvid2str(pool, source), " has inferior architecture", 0);
case SOLVER_RULE_UPDATE:
return pool_tmpjoin(pool, "problem with installed package ", pool_solvid2str(pool, source), 0);
case SOLVER_RULE_JOB:
return "conflicting requests";
case SOLVER_RULE_JOB_UNSUPPORTED:
return "unsupported request";
case SOLVER_RULE_JOB_NOTHING_PROVIDES_DEP:
return pool_tmpjoin(pool, "nothing provides requested ", pool_dep2str(pool, dep), 0);
case SOLVER_RULE_JOB_UNKNOWN_PACKAGE:
return pool_tmpjoin(pool, "package ", pool_dep2str(pool, dep), " does not exist");
case SOLVER_RULE_JOB_PROVIDED_BY_SYSTEM:
return pool_tmpjoin(pool, pool_dep2str(pool, dep), " is provided by the system", 0);
case SOLVER_RULE_PKG:
return "some dependency problem";
case SOLVER_RULE_BEST:
if (source > 0)
return pool_tmpjoin(pool, "cannot install the best update candidate for package ", pool_solvid2str(pool, source), 0);
return "cannot install the best candidate for the job";
case SOLVER_RULE_PKG_NOT_INSTALLABLE:
return pool_tmpjoin(pool, "package ", pool_solvid2str(pool, source), " is not installable");
case SOLVER_RULE_PKG_NOTHING_PROVIDES_DEP:
s = pool_tmpjoin(pool, "nothing provides ", pool_dep2str(pool, dep), 0);
return pool_tmpappend(pool, s, " needed by ", pool_solvid2str(pool, source));
case SOLVER_RULE_PKG_SAME_NAME:
s = pool_tmpjoin(pool, "cannot install both ", pool_solvid2str(pool, source), 0);
return pool_tmpappend(pool, s, " and ", pool_solvid2str(pool, target));
case SOLVER_RULE_PKG_CONFLICTS:
s = pool_tmpjoin(pool, "package ", pool_solvid2str(pool, source), 0);
s = pool_tmpappend(pool, s, " conflicts with ", pool_dep2str(pool, dep));
return pool_tmpappend(pool, s, " provided by ", pool_solvid2str(pool, target));
case SOLVER_RULE_PKG_OBSOLETES:
s = pool_tmpjoin(pool, "package ", pool_solvid2str(pool, source), 0);
s = pool_tmpappend(pool, s, " obsoletes ", pool_dep2str(pool, dep));
return pool_tmpappend(pool, s, " provided by ", pool_solvid2str(pool, target));
case SOLVER_RULE_PKG_INSTALLED_OBSOLETES:
s = pool_tmpjoin(pool, "installed package ", pool_solvid2str(pool, source), 0);
s = pool_tmpappend(pool, s, " obsoletes ", pool_dep2str(pool, dep));
return pool_tmpappend(pool, s, " provided by ", pool_solvid2str(pool, target));
case SOLVER_RULE_PKG_IMPLICIT_OBSOLETES:
s = pool_tmpjoin(pool, "package ", pool_solvid2str(pool, source), 0);
s = pool_tmpappend(pool, s, " implicitly obsoletes ", pool_dep2str(pool, dep));
return pool_tmpappend(pool, s, " provided by ", pool_solvid2str(pool, target));
case SOLVER_RULE_PKG_REQUIRES:
s = pool_tmpjoin(pool, "package ", pool_solvid2str(pool, source), " requires ");
return pool_tmpappend(pool, s, pool_dep2str(pool, dep), ", but none of the providers can be installed");
case SOLVER_RULE_PKG_SELF_CONFLICT:
s = pool_tmpjoin(pool, "package ", pool_solvid2str(pool, source), " conflicts with ");
return pool_tmpappend(pool, s, pool_dep2str(pool, dep), " provided by itself");
case SOLVER_RULE_YUMOBS:
s = pool_tmpjoin(pool, "both package ", pool_solvid2str(pool, source), " and ");
s = pool_tmpjoin(pool, s, pool_solvid2str(pool, target), " obsolete ");
return pool_tmpappend(pool, s, pool_dep2str(pool, dep), 0);
default:
return "bad problem rule type";
}
}
/* convenience function */
const char *
solver_problem2str(Solver *solv, Id problem)
{
Id type, source, target, dep;
Id r = solver_findproblemrule(solv, problem);
if (!r)
return "no problem rule?";
type = solver_ruleinfo(solv, r, &source, &target, &dep);
return solver_problemruleinfo2str(solv, type, source, target, dep);
}
const char *
solver_solutionelement2str(Solver *solv, Id p, Id rp)
{
Pool *pool = solv->pool;
if (p == SOLVER_SOLUTION_JOB || p == SOLVER_SOLUTION_POOLJOB)
{
Id how, what;
if (p == SOLVER_SOLUTION_JOB)
rp += solv->pooljobcnt;
how = solv->job.elements[rp - 1];
what = solv->job.elements[rp];
return pool_tmpjoin(pool, "do not ask to ", pool_job2str(pool, how, what, 0), 0);
}
else if (p == SOLVER_SOLUTION_INFARCH)
{
Solvable *s = pool->solvables + rp;
if (solv->installed && s->repo == solv->installed)
return pool_tmpjoin(pool, "keep ", pool_solvable2str(pool, s), " despite the inferior architecture");
else
return pool_tmpjoin(pool, "install ", pool_solvable2str(pool, s), " despite the inferior architecture");
}
else if (p == SOLVER_SOLUTION_DISTUPGRADE)
{
Solvable *s = pool->solvables + rp;
if (solv->installed && s->repo == solv->installed)
return pool_tmpjoin(pool, "keep obsolete ", pool_solvable2str(pool, s), 0);
else
return pool_tmpjoin(pool, "install ", pool_solvable2str(pool, s), " from excluded repository");
}
else if (p == SOLVER_SOLUTION_BEST)
{
Solvable *s = pool->solvables + rp;
if (solv->installed && s->repo == solv->installed)
return pool_tmpjoin(pool, "keep old ", pool_solvable2str(pool, s), 0);
else
return pool_tmpjoin(pool, "install ", pool_solvable2str(pool, s), " despite the old version");
}
else if (p > 0 && rp == 0)
return pool_tmpjoin(pool, "allow deinstallation of ", pool_solvid2str(pool, p), 0);
else if (p > 0 && rp > 0)
{
const char *sp = pool_solvid2str(pool, p);
const char *srp = pool_solvid2str(pool, rp);
const char *str = pool_tmpjoin(pool, "allow replacement of ", sp, 0);
return pool_tmpappend(pool, str, " with ", srp);
}
else
return "bad solution element";
}
Jump to Line
Something went wrong with that request. Please try again.