satsolver 0.16.3
|
00001 /* 00002 * Copyright (c) 2007-2009, Novell Inc. 00003 * 00004 * This program is licensed under the BSD license, read LICENSE.BSD 00005 * for further information 00006 */ 00007 00008 /* 00009 * problems.c 00010 * 00011 */ 00012 00013 #include <stdio.h> 00014 #include <stdlib.h> 00015 #include <unistd.h> 00016 #include <string.h> 00017 #include <assert.h> 00018 00019 #include "solver.h" 00020 #include "bitmap.h" 00021 #include "pool.h" 00022 #include "util.h" 00023 #include "evr.h" 00024 #include "solverdebug.h" 00025 00026 00027 /**********************************************************************************/ 00028 00029 /* a problem is an item on the solver's problem list. It can either be >0, in that 00030 * case it is a update/infarch/dup rule, or it can be <0, which makes it refer to a job 00031 * consisting of multiple job rules. 00032 */ 00033 00034 void 00035 solver_disableproblem(Solver *solv, Id v) 00036 { 00037 Rule *r; 00038 int i; 00039 Id *jp; 00040 00041 if (v > 0) 00042 { 00043 if (v >= solv->infarchrules && v < solv->infarchrules_end) 00044 { 00045 Pool *pool = solv->pool; 00046 Id name = pool->solvables[-solv->rules[v].p].name; 00047 while (v > solv->infarchrules && pool->solvables[-solv->rules[v - 1].p].name == name) 00048 v--; 00049 for (; v < solv->infarchrules_end && pool->solvables[-solv->rules[v].p].name == name; v++) 00050 solver_disablerule(solv, solv->rules + v); 00051 return; 00052 } 00053 if (v >= solv->duprules && v < solv->duprules_end) 00054 { 00055 Pool *pool = solv->pool; 00056 Id name = pool->solvables[-solv->rules[v].p].name; 00057 while (v > solv->duprules && pool->solvables[-solv->rules[v - 1].p].name == name) 00058 v--; 00059 for (; v < solv->duprules_end && pool->solvables[-solv->rules[v].p].name == name; v++) 00060 solver_disablerule(solv, solv->rules + v); 00061 return; 00062 } 00063 solver_disablerule(solv, solv->rules + v); 00064 #if 0 00065 /* XXX: doesn't work */ 00066 if (v >= solv->updaterules && v < solv->updaterules_end) 00067 { 00068 /* enable feature rule if we disabled the update rule */ 00069 r = solv->rules + (v - solv->updaterules + solv->featurerules); 00070 if (r->p) 00071 solver_enablerule(solv, r); 00072 } 00073 #endif 00074 return; 00075 } 00076 v = -(v + 1); 00077 jp = solv->ruletojob.elements; 00078 for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++, jp++) 00079 if (*jp == v) 00080 solver_disablerule(solv, r); 00081 } 00082 00083 /*------------------------------------------------------------------- 00084 * enableproblem 00085 */ 00086 00087 void 00088 solver_enableproblem(Solver *solv, Id v) 00089 { 00090 Rule *r; 00091 int i; 00092 Id *jp; 00093 00094 if (v > 0) 00095 { 00096 if (v >= solv->infarchrules && v < solv->infarchrules_end) 00097 { 00098 Pool *pool = solv->pool; 00099 Id name = pool->solvables[-solv->rules[v].p].name; 00100 while (v > solv->infarchrules && pool->solvables[-solv->rules[v - 1].p].name == name) 00101 v--; 00102 for (; v < solv->infarchrules_end && pool->solvables[-solv->rules[v].p].name == name; v++) 00103 solver_enablerule(solv, solv->rules + v); 00104 return; 00105 } 00106 if (v >= solv->duprules && v < solv->duprules_end) 00107 { 00108 Pool *pool = solv->pool; 00109 Id name = pool->solvables[-solv->rules[v].p].name; 00110 while (v > solv->duprules && pool->solvables[-solv->rules[v - 1].p].name == name) 00111 v--; 00112 for (; v < solv->duprules_end && pool->solvables[-solv->rules[v].p].name == name; v++) 00113 solver_enablerule(solv, solv->rules + v); 00114 return; 00115 } 00116 if (v >= solv->featurerules && v < solv->featurerules_end) 00117 { 00118 /* do not enable feature rule if update rule is enabled */ 00119 r = solv->rules + (v - solv->featurerules + solv->updaterules); 00120 if (r->d >= 0) 00121 return; 00122 } 00123 solver_enablerule(solv, solv->rules + v); 00124 if (v >= solv->updaterules && v < solv->updaterules_end) 00125 { 00126 /* disable feature rule when enabling update rule */ 00127 r = solv->rules + (v - solv->updaterules + solv->featurerules); 00128 if (r->p) 00129 solver_disablerule(solv, r); 00130 } 00131 return; 00132 } 00133 v = -(v + 1); 00134 jp = solv->ruletojob.elements; 00135 for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++, jp++) 00136 if (*jp == v) 00137 solver_enablerule(solv, r); 00138 } 00139 00140 00141 /*------------------------------------------------------------------- 00142 * enable weak rules 00143 * 00144 * Reenable all disabled weak rules (marked in weakrulemap) 00145 * 00146 */ 00147 00148 static void 00149 enableweakrules(Solver *solv) 00150 { 00151 int i; 00152 Rule *r; 00153 00154 for (i = 1, r = solv->rules + i; i < solv->learntrules; i++, r++) 00155 { 00156 if (r->d >= 0) /* already enabled? */ 00157 continue; 00158 if (!MAPTST(&solv->weakrulemap, i)) 00159 continue; 00160 solver_enablerule(solv, r); 00161 } 00162 } 00163 00164 00165 /*------------------------------------------------------------------- 00166 * 00167 * refine_suggestion 00168 * 00169 * at this point, all rules that led to conflicts are disabled. 00170 * we re-enable all rules of a problem set but rule "sug", then 00171 * continue to disable more rules until there as again a solution. 00172 */ 00173 00174 /* FIXME: think about conflicting assertions */ 00175 00176 static void 00177 refine_suggestion(Solver *solv, Id *problem, Id sug, Queue *refined, int essentialok) 00178 { 00179 Pool *pool = solv->pool; 00180 int i, j; 00181 Id v; 00182 Queue disabled; 00183 int disabledcnt; 00184 00185 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS) 00186 { 00187 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "refine_suggestion start\n"); 00188 for (i = 0; problem[i]; i++) 00189 { 00190 if (problem[i] == sug) 00191 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "=> "); 00192 solver_printproblem(solv, problem[i]); 00193 } 00194 } 00195 queue_empty(refined); 00196 if (!essentialok && sug < 0 && (solv->job.elements[-sug - 1] & SOLVER_ESSENTIAL) != 0) 00197 return; 00198 queue_init(&disabled); 00199 queue_push(refined, sug); 00200 00201 /* re-enable all problem rules with the exception of "sug"(gestion) */ 00202 solver_reset(solv); 00203 00204 for (i = 0; problem[i]; i++) 00205 if (problem[i] != sug) 00206 solver_enableproblem(solv, problem[i]); 00207 00208 if (sug < 0) 00209 solver_reenablepolicyrules(solv, -(sug + 1)); 00210 else if (sug >= solv->updaterules && sug < solv->updaterules_end) 00211 { 00212 /* enable feature rule */ 00213 Rule *r = solv->rules + solv->featurerules + (sug - solv->updaterules); 00214 if (r->p) 00215 solver_enablerule(solv, r); 00216 } 00217 00218 enableweakrules(solv); 00219 00220 for (;;) 00221 { 00222 int njob, nfeature, nupdate, pass; 00223 queue_empty(&solv->problems); 00224 solver_reset(solv); 00225 00226 if (!solv->problems.count) 00227 solver_run_sat(solv, 0, 0); 00228 00229 if (!solv->problems.count) 00230 { 00231 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "no more problems!\n"); 00232 IF_POOLDEBUG (SAT_DEBUG_SCHUBI) 00233 solver_printdecisions(solv); 00234 break; /* great, no more problems */ 00235 } 00236 disabledcnt = disabled.count; 00237 /* start with 1 to skip over proof index */ 00238 njob = nfeature = nupdate = 0; 00239 for (pass = 0; pass < 2; pass++) 00240 { 00241 for (i = 1; i < solv->problems.count - 1; i++) 00242 { 00243 /* ignore solutions in refined */ 00244 v = solv->problems.elements[i]; 00245 if (v == 0) 00246 break; /* end of problem reached */ 00247 if (sug != v) 00248 { 00249 /* check if v is in the given problems list 00250 * we allow disabling all problem rules *after* sug in 00251 * pass 2, to prevent getting the same solution twice */ 00252 for (j = 0; problem[j]; j++) 00253 if (problem[j] == v || (pass && problem[j] == sug)) 00254 break; 00255 if (problem[j] == v) 00256 continue; 00257 } 00258 if (v >= solv->featurerules && v < solv->featurerules_end) 00259 nfeature++; 00260 else if (v > 0) 00261 nupdate++; 00262 else 00263 { 00264 if (!essentialok && (solv->job.elements[-v -1] & SOLVER_ESSENTIAL) != 0) 00265 continue; /* not that one! */ 00266 njob++; 00267 } 00268 queue_push(&disabled, v); 00269 } 00270 if (disabled.count != disabledcnt) 00271 break; 00272 } 00273 if (disabled.count == disabledcnt) 00274 { 00275 /* no solution found, this was an invalid suggestion! */ 00276 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "no solution found!\n"); 00277 refined->count = 0; 00278 break; 00279 } 00280 if (!njob && nupdate && nfeature) 00281 { 00282 /* got only update rules, filter out feature rules */ 00283 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "throwing away feature rules\n"); 00284 for (i = j = disabledcnt; i < disabled.count; i++) 00285 { 00286 v = disabled.elements[i]; 00287 if (v < solv->featurerules || v >= solv->featurerules_end) 00288 disabled.elements[j++] = v; 00289 } 00290 disabled.count = j; 00291 nfeature = 0; 00292 } 00293 if (disabled.count == disabledcnt + 1) 00294 { 00295 /* just one suggestion, add it to refined list */ 00296 v = disabled.elements[disabledcnt]; 00297 if (!nfeature) 00298 queue_push(refined, v); /* do not record feature rules */ 00299 solver_disableproblem(solv, v); 00300 if (v >= solv->updaterules && v < solv->updaterules_end) 00301 { 00302 Rule *r = solv->rules + (v - solv->updaterules + solv->featurerules); 00303 if (r->p) 00304 solver_enablerule(solv, r); /* enable corresponding feature rule */ 00305 } 00306 if (v < 0) 00307 solver_reenablepolicyrules(solv, -(v + 1)); 00308 } 00309 else 00310 { 00311 /* more than one solution, disable all */ 00312 /* do not push anything on refine list, as we do not know which solution to choose */ 00313 /* thus, the user will get another problem if he selects this solution, where he 00314 * can choose the right one */ 00315 IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS) 00316 { 00317 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "more than one solution found:\n"); 00318 for (i = disabledcnt; i < disabled.count; i++) 00319 solver_printproblem(solv, disabled.elements[i]); 00320 } 00321 for (i = disabledcnt; i < disabled.count; i++) 00322 { 00323 v = disabled.elements[i]; 00324 solver_disableproblem(solv, v); 00325 if (v >= solv->updaterules && v < solv->updaterules_end) 00326 { 00327 Rule *r = solv->rules + (v - solv->updaterules + solv->featurerules); 00328 if (r->p) 00329 solver_enablerule(solv, r); 00330 } 00331 } 00332 } 00333 } 00334 /* all done, get us back into the same state as before */ 00335 /* enable refined rules again */ 00336 for (i = 0; i < disabled.count; i++) 00337 solver_enableproblem(solv, disabled.elements[i]); 00338 queue_free(&disabled); 00339 /* reset policy rules */ 00340 for (i = 0; problem[i]; i++) 00341 solver_enableproblem(solv, problem[i]); 00342 solver_disablepolicyrules(solv); 00343 /* disable problem rules again */ 00344 for (i = 0; problem[i]; i++) 00345 solver_disableproblem(solv, problem[i]); 00346 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "refine_suggestion end\n"); 00347 } 00348 00349 00350 /*------------------------------------------------------------------- 00351 * sorting helper for problems 00352 * 00353 * bring update rules before job rules 00354 * make essential job rules last 00355 */ 00356 00357 static int 00358 problems_sortcmp(const void *ap, const void *bp, void *dp) 00359 { 00360 Queue *job = dp; 00361 Id a = *(Id *)ap, b = *(Id *)bp; 00362 if (a < 0 && b > 0) 00363 return 1; 00364 if (a > 0 && b < 0) 00365 return -1; 00366 if (a < 0 && b < 0) 00367 { 00368 int af = job->elements[-a - 1] & SOLVER_ESSENTIAL; 00369 int bf = job->elements[-b - 1] & SOLVER_ESSENTIAL; 00370 int x = af - bf; 00371 if (x) 00372 return x; 00373 } 00374 return a - b; 00375 } 00376 00377 /* 00378 * convert a solution rule into a job modifier 00379 */ 00380 static void 00381 convertsolution(Solver *solv, Id why, Queue *solutionq) 00382 { 00383 Pool *pool = solv->pool; 00384 if (why < 0) 00385 { 00386 queue_push(solutionq, 0); 00387 queue_push(solutionq, -why); 00388 return; 00389 } 00390 if (why >= solv->infarchrules && why < solv->infarchrules_end) 00391 { 00392 Id p, name; 00393 /* infarch rule, find replacement */ 00394 assert(solv->rules[why].p < 0); 00395 name = pool->solvables[-solv->rules[why].p].name; 00396 while (why > solv->infarchrules && pool->solvables[-solv->rules[why - 1].p].name == name) 00397 why--; 00398 p = 0; 00399 for (; why < solv->infarchrules_end && pool->solvables[-solv->rules[why].p].name == name; why++) 00400 if (solv->decisionmap[-solv->rules[why].p] > 0) 00401 { 00402 p = -solv->rules[why].p; 00403 break; 00404 } 00405 if (!p) 00406 return; /* false alarm */ 00407 queue_push(solutionq, SOLVER_SOLUTION_INFARCH); 00408 queue_push(solutionq, p); 00409 return; 00410 } 00411 if (why >= solv->duprules && why < solv->duprules_end) 00412 { 00413 Id p, name; 00414 /* dist upgrade rule, find replacement */ 00415 assert(solv->rules[why].p < 0); 00416 name = pool->solvables[-solv->rules[why].p].name; 00417 while (why > solv->duprules && pool->solvables[-solv->rules[why - 1].p].name == name) 00418 why--; 00419 p = 0; 00420 for (; why < solv->duprules_end && pool->solvables[-solv->rules[why].p].name == name; why++) 00421 if (solv->decisionmap[-solv->rules[why].p] > 0) 00422 { 00423 p = -solv->rules[why].p; 00424 break; 00425 } 00426 if (!p) 00427 return; /* false alarm */ 00428 queue_push(solutionq, SOLVER_SOLUTION_DISTUPGRADE); 00429 queue_push(solutionq, p); 00430 return; 00431 } 00432 if (why >= solv->updaterules && why < solv->updaterules_end) 00433 { 00434 /* update rule, find replacement package */ 00435 Id p, *dp, rp = 0; 00436 Rule *rr; 00437 00438 assert(why >= solv->updaterules && why < solv->updaterules_end); 00439 /* check if this is a false positive, i.e. the update rule is fulfilled */ 00440 rr = solv->rules + why; 00441 FOR_RULELITERALS(p, dp, rr) 00442 if (p > 0 && solv->decisionmap[p] > 0) 00443 break; 00444 if (p) 00445 return; /* false alarm */ 00446 00447 p = solv->installed->start + (why - solv->updaterules); 00448 rr = solv->rules + solv->featurerules + (why - solv->updaterules); 00449 if (!rr->p) 00450 rr = solv->rules + why; 00451 if (solv->dupmap_all && solv->rules[why].p != p && solv->decisionmap[p] > 0) 00452 { 00453 /* distupgrade case, allow to keep old package */ 00454 queue_push(solutionq, SOLVER_SOLUTION_DISTUPGRADE); 00455 queue_push(solutionq, p); 00456 return; 00457 } 00458 if (solv->decisionmap[p] > 0) 00459 return; /* false alarm, turned out we can keep the package */ 00460 if (rr->w2) 00461 { 00462 int mvrp = 0; /* multi-version replacement */ 00463 FOR_RULELITERALS(rp, dp, rr) 00464 { 00465 if (rp > 0 && solv->decisionmap[rp] > 0 && pool->solvables[rp].repo != solv->installed) 00466 { 00467 mvrp = rp; 00468 if (!(solv->noobsoletes.size && MAPTST(&solv->noobsoletes, rp))) 00469 break; 00470 } 00471 } 00472 if (!rp && mvrp) 00473 { 00474 /* found only multi-version replacements */ 00475 /* have to split solution into two parts */ 00476 queue_push(solutionq, p); 00477 queue_push(solutionq, mvrp); 00478 } 00479 } 00480 queue_push(solutionq, p); 00481 queue_push(solutionq, rp); 00482 return; 00483 } 00484 } 00485 00486 /* 00487 * convert problem data into a form usable for refining. 00488 * Returns the number of problems. 00489 */ 00490 int 00491 solver_prepare_solutions(Solver *solv) 00492 { 00493 int i, j = 1, idx = 1; 00494 00495 if (!solv->problems.count) 00496 return 0; 00497 queue_push(&solv->solutions, 0); 00498 queue_push(&solv->solutions, -1); /* unrefined */ 00499 for (i = 1; i < solv->problems.count; i++) 00500 { 00501 Id p = solv->problems.elements[i]; 00502 queue_push(&solv->solutions, p); 00503 if (p) 00504 continue; 00505 solv->problems.elements[j++] = idx; 00506 if (i + 1 >= solv->problems.count) 00507 break; 00508 solv->problems.elements[j++] = solv->problems.elements[++i]; /* copy proofidx */ 00509 idx = solv->solutions.count; 00510 queue_push(&solv->solutions, -1); 00511 } 00512 solv->problems.count = j; 00513 return j / 2; 00514 } 00515 00516 /* 00517 * refine the simple solution rule list provided by 00518 * the solver into multiple lists of job modifiers. 00519 */ 00520 static void 00521 create_solutions(Solver *solv, int probnr, int solidx) 00522 { 00523 Pool *pool = solv->pool; 00524 Queue redoq; 00525 Queue problem, solution, problems_save; 00526 int i, j, nsol; 00527 int essentialok; 00528 int recocount; 00529 unsigned int now; 00530 00531 now = sat_timems(0); 00532 recocount = solv->recommendations.count; 00533 solv->recommendations.count = 0; /* so that revert() doesn't mess with it later */ 00534 queue_init(&redoq); 00535 /* save decisionq, decisionq_why, decisionmap */ 00536 for (i = 0; i < solv->decisionq.count; i++) 00537 { 00538 Id p = solv->decisionq.elements[i]; 00539 queue_push(&redoq, p); 00540 queue_push(&redoq, solv->decisionq_why.elements[i]); 00541 queue_push(&redoq, solv->decisionmap[p > 0 ? p : -p]); 00542 } 00543 /* save problems queue */ 00544 problems_save = solv->problems; 00545 memset(&solv->problems, 0, sizeof(solv->problems)); 00546 00547 /* extract problem from queue */ 00548 queue_init(&problem); 00549 for (i = solidx + 1; i < solv->solutions.count; i++) 00550 { 00551 Id v = solv->solutions.elements[i]; 00552 if (!v) 00553 break; 00554 queue_push(&problem, v); 00555 } 00556 if (problem.count > 1) 00557 sat_sort(problem.elements, problem.count, sizeof(Id), problems_sortcmp, &solv->job); 00558 queue_push(&problem, 0); /* mark end for refine_suggestion */ 00559 problem.count--; 00560 #if 0 00561 for (i = 0; i < problem.count; i++) 00562 printf("PP %d %d\n", i, problem.elements[i]); 00563 #endif 00564 00565 /* refine each solution element */ 00566 nsol = 0; 00567 essentialok = 0; 00568 queue_init(&solution); 00569 for (i = 0; i < problem.count; i++) 00570 { 00571 int solstart = solv->solutions.count; 00572 refine_suggestion(solv, problem.elements, problem.elements[i], &solution, essentialok); 00573 queue_push(&solv->solutions, 0); /* reserve room for number of elements */ 00574 for (j = 0; j < solution.count; j++) 00575 convertsolution(solv, solution.elements[j], &solv->solutions); 00576 if (solv->solutions.count == solstart + 1) 00577 { 00578 solv->solutions.count--; /* this one did not work out */ 00579 if (nsol || i + 1 < problem.count) 00580 continue; /* got one or still hope */ 00581 if (!essentialok) 00582 { 00583 /* nothing found, start over */ 00584 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "nothing found, re-run with essentialok = 1\n"); 00585 essentialok = 1; 00586 i = -1; 00587 continue; 00588 } 00589 /* this is bad, we found no solution */ 00590 /* for now just offer a rule */ 00591 POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "nothing found, already did essentialok, fake it\n"); 00592 queue_push(&solv->solutions, 0); 00593 for (j = 0; j < problem.count; j++) 00594 { 00595 convertsolution(solv, problem.elements[j], &solv->solutions); 00596 if (solv->solutions.count > solstart + 1) 00597 break; 00598 } 00599 if (solv->solutions.count == solstart + 1) 00600 { 00601 solv->solutions.count--; 00602 continue; /* sorry */ 00603 } 00604 } 00605 /* patch in number of solution elements */ 00606 solv->solutions.elements[solstart] = (solv->solutions.count - (solstart + 1)) / 2; 00607 queue_push(&solv->solutions, 0); /* add end marker */ 00608 queue_push(&solv->solutions, 0); /* add end marker */ 00609 solv->solutions.elements[solidx + 1 + nsol++] = solstart; 00610 } 00611 solv->solutions.elements[solidx + 1 + nsol] = 0; /* end marker */ 00612 solv->solutions.elements[solidx] = nsol; 00613 queue_free(&problem); 00614 queue_free(&solution); 00615 00616 /* restore decisions */ 00617 memset(solv->decisionmap, 0, pool->nsolvables * sizeof(Id)); 00618 queue_empty(&solv->decisionq); 00619 queue_empty(&solv->decisionq_why); 00620 for (i = 0; i < redoq.count; i += 3) 00621 { 00622 Id p = redoq.elements[i]; 00623 queue_push(&solv->decisionq, p); 00624 queue_push(&solv->decisionq_why, redoq.elements[i + 1]); 00625 solv->decisionmap[p > 0 ? p : -p] = redoq.elements[i + 2]; 00626 } 00627 solv->recommendations.count = recocount; 00628 queue_free(&redoq); 00629 /* restore problems */ 00630 queue_free(&solv->problems); 00631 solv->problems = problems_save; 00632 POOL_DEBUG(SAT_DEBUG_STATS, "create_solutions for problem #%d took %d ms\n", probnr, sat_timems(now)); 00633 } 00634 00635 00636 /**************************************************************************/ 00637 00638 unsigned int 00639 solver_problem_count(Solver *solv) 00640 { 00641 return solv->problems.count / 2; 00642 } 00643 00644 Id 00645 solver_next_problem(Solver *solv, Id problem) 00646 { 00647 if (!problem) 00648 return solv->problems.count ? 1 : 0; 00649 return (problem + 1) * 2 - 1 < solv->problems.count ? problem + 1 : 0; 00650 } 00651 00652 unsigned int 00653 solver_solution_count(Solver *solv, Id problem) 00654 { 00655 Id solidx = solv->problems.elements[problem * 2 - 1]; 00656 if (solv->solutions.elements[solidx] < 0) 00657 create_solutions(solv, problem, solidx); 00658 return solv->solutions.elements[solidx]; 00659 } 00660 00661 Id 00662 solver_next_solution(Solver *solv, Id problem, Id solution) 00663 { 00664 Id solidx = solv->problems.elements[problem * 2 - 1]; 00665 if (solv->solutions.elements[solidx] < 0) 00666 create_solutions(solv, problem, solidx); 00667 return solv->solutions.elements[solidx + solution + 1] ? solution + 1 : 0; 00668 } 00669 00670 unsigned int 00671 solver_solutionelement_count(Solver *solv, Id problem, Id solution) 00672 { 00673 Id solidx = solv->problems.elements[problem * 2 - 1]; 00674 solidx = solv->solutions.elements[solidx + solution]; 00675 return solv->solutions.elements[solidx]; 00676 } 00677 00678 00679 /* 00680 * return the next item of the proposed solution 00681 * here are the possibilities for p / rp and what 00682 * the solver expects the application to do: 00683 * p rp 00684 * ------------------------------------------------------- 00685 * SOLVER_SOLUTION_INFARCH pkgid 00686 * -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job 00687 * SOLVER_SOLUTION_DISTUPGRADE pkgid 00688 * -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job 00689 * SOLVER_SOLUTION_JOB jobidx 00690 * -> remove job (jobidx - 1, jobidx) from job queue 00691 * pkgid (> 0) 0 00692 * -> add (SOLVER_ERASE|SOLVER_SOLVABLE, p) to the job 00693 * pkgid (> 0) pkgid (> 0) 00694 * -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job 00695 * (this will replace package p) 00696 * 00697 * Thus, the solver will either ask the application to remove 00698 * a specific job from the job queue, or ask to add an install/erase 00699 * job to it. 00700 * 00701 */ 00702 00703 Id 00704 solver_next_solutionelement(Solver *solv, Id problem, Id solution, Id element, Id *p, Id *rp) 00705 { 00706 Id solidx = solv->problems.elements[problem * 2 - 1]; 00707 solidx = solv->solutions.elements[solidx + solution]; 00708 if (!solidx) 00709 return 0; 00710 solidx += 1 + element * 2; 00711 if (!solv->solutions.elements[solidx] && !solv->solutions.elements[solidx + 1]) 00712 return 0; 00713 *p = solv->solutions.elements[solidx]; 00714 *rp = solv->solutions.elements[solidx + 1]; 00715 return element + 1; 00716 } 00717 00718 void 00719 solver_take_solutionelement(Solver *solv, Id p, Id rp, Queue *job) 00720 { 00721 int i; 00722 00723 if (p == SOLVER_SOLUTION_JOB) 00724 { 00725 job->elements[rp - 1] = SOLVER_NOOP; 00726 job->elements[rp] = 0; 00727 return; 00728 } 00729 if (rp <= 0 && p <= 0) 00730 return; /* just in case */ 00731 if (rp > 0) 00732 p = SOLVER_INSTALL|SOLVER_SOLVABLE; 00733 else 00734 { 00735 rp = p; 00736 p = SOLVER_ERASE|SOLVER_SOLVABLE; 00737 } 00738 for (i = 0; i < job->count; i += 2) 00739 if (job->elements[i] == p && job->elements[i + 1] == rp) 00740 return; 00741 queue_push2(job, p, rp); 00742 } 00743 00744 void 00745 solver_take_solution(Solver *solv, Id problem, Id solution, Queue *job) 00746 { 00747 Id p, rp, element = 0; 00748 while ((element = solver_next_solutionelement(solv, problem, solution, element, &p, &rp)) != 0) 00749 solver_take_solutionelement(solv, p, rp, job); 00750 } 00751 00752 00753 /*------------------------------------------------------------------- 00754 * 00755 * find problem rule 00756 */ 00757 00758 static void 00759 findproblemrule_internal(Solver *solv, Id idx, Id *reqrp, Id *conrp, Id *sysrp, Id *jobrp) 00760 { 00761 Id rid, d; 00762 Id lreqr, lconr, lsysr, ljobr; 00763 Rule *r; 00764 Id jobassert = 0; 00765 int i, reqset = 0; /* 0: unset, 1: installed, 2: jobassert, 3: assert */ 00766 00767 /* find us a jobassert rule */ 00768 for (i = idx; (rid = solv->learnt_pool.elements[i]) != 0; i++) 00769 { 00770 if (rid < solv->jobrules || rid >= solv->jobrules_end) 00771 continue; 00772 r = solv->rules + rid; 00773 d = r->d < 0 ? -r->d - 1 : r->d; 00774 if (!d && r->w2 == 0 && r->p > 0) 00775 { 00776 jobassert = r->p; 00777 break; 00778 } 00779 } 00780 00781 /* the problem rules are somewhat ordered from "near to the problem" to 00782 * "near to the job" */ 00783 lreqr = lconr = lsysr = ljobr = 0; 00784 while ((rid = solv->learnt_pool.elements[idx++]) != 0) 00785 { 00786 assert(rid > 0); 00787 if (rid >= solv->learntrules) 00788 findproblemrule_internal(solv, solv->learnt_why.elements[rid - solv->learntrules], &lreqr, &lconr, &lsysr, &ljobr); 00789 else if ((rid >= solv->jobrules && rid < solv->jobrules_end) || (rid >= solv->infarchrules && rid < solv->infarchrules_end) || (rid >= solv->duprules && rid < solv->duprules_end)) 00790 { 00791 if (!*jobrp) 00792 *jobrp = rid; 00793 } 00794 else if (rid >= solv->updaterules && rid < solv->updaterules_end) 00795 { 00796 if (!*sysrp) 00797 *sysrp = rid; 00798 } 00799 else 00800 { 00801 assert(rid < solv->rpmrules_end); 00802 r = solv->rules + rid; 00803 d = r->d < 0 ? -r->d - 1 : r->d; 00804 if (!d && r->w2 < 0) 00805 { 00806 if (!*conrp) 00807 *conrp = rid; 00808 } 00809 else 00810 { 00811 if (!d && r->w2 == 0 && reqset < 3) 00812 { 00813 if (*reqrp > 0 && r->p < -1) 00814 { 00815 Id op = -solv->rules[*reqrp].p; 00816 if (op > 1 && solv->pool->solvables[op].arch != solv->pool->solvables[-r->p].arch) 00817 continue; /* different arch, skip */ 00818 } 00819 /* prefer assertions */ 00820 *reqrp = rid; 00821 reqset = 3; 00822 } 00823 else if (jobassert && r->p == -jobassert) 00824 { 00825 /* prefer rules of job assertions */ 00826 *reqrp = rid; 00827 reqset = 2; 00828 } 00829 else if (solv->installed && r->p < 0 && solv->pool->solvables[-r->p].repo == solv->installed && reqset <= 1) 00830 { 00831 /* prefer rules of job installed package so that the user doesn't get confused by strange packages */ 00832 *reqrp = rid; 00833 reqset = 1; 00834 } 00835 else if (!*reqrp) 00836 *reqrp = rid; 00837 } 00838 } 00839 } 00840 if (!*reqrp && lreqr) 00841 *reqrp = lreqr; 00842 if (!*conrp && lconr) 00843 *conrp = lconr; 00844 if (!*jobrp && ljobr) 00845 *jobrp = ljobr; 00846 if (!*sysrp && lsysr) 00847 *sysrp = lsysr; 00848 } 00849 00850 /* 00851 * find problem rule 00852 * 00853 * search for a rule that describes the problem to the 00854 * user. Actually a pretty hopeless task that may leave the user 00855 * puzzled. To get all of the needed information use 00856 * solver_findallproblemrules() instead. 00857 */ 00858 00859 Id 00860 solver_findproblemrule(Solver *solv, Id problem) 00861 { 00862 Id reqr, conr, sysr, jobr; 00863 Id idx = solv->problems.elements[2 * problem - 2]; 00864 reqr = conr = sysr = jobr = 0; 00865 findproblemrule_internal(solv, idx, &reqr, &conr, &sysr, &jobr); 00866 if (reqr) 00867 return reqr; /* some requires */ 00868 if (conr) 00869 return conr; /* some conflict */ 00870 if (sysr) 00871 return sysr; /* an update rule */ 00872 if (jobr) 00873 return jobr; /* a user request */ 00874 assert(0); 00875 } 00876 00877 /*-------------------------------------------------------------------*/ 00878 00879 static void 00880 findallproblemrules_internal(Solver *solv, Id idx, Queue *rules) 00881 { 00882 Id rid; 00883 while ((rid = solv->learnt_pool.elements[idx++]) != 0) 00884 { 00885 if (rid >= solv->learntrules) 00886 { 00887 findallproblemrules_internal(solv, solv->learnt_why.elements[rid - solv->learntrules], rules); 00888 continue; 00889 } 00890 queue_pushunique(rules, rid); 00891 } 00892 } 00893 00894 /* 00895 * find all problem rule 00896 * 00897 * return all rules that lead to the problem. This gives the user 00898 * all of the information to understand the problem, but the result 00899 * can be a large number of rules. 00900 */ 00901 00902 void 00903 solver_findallproblemrules(Solver *solv, Id problem, Queue *rules) 00904 { 00905 queue_empty(rules); 00906 findallproblemrules_internal(solv, solv->problems.elements[2 * problem - 2], rules); 00907 } 00908 00909 /* obsolete function */ 00910 SolverRuleinfo 00911 solver_problemruleinfo(Solver *solv, Queue *job, Id rid, Id *depp, Id *sourcep, Id *targetp) 00912 { 00913 return solver_ruleinfo(solv, rid, sourcep, targetp, depp); 00914 } 00915 00916 /* EOF */