1 /* 2 * Copyright (c) 2007-2009, Novell Inc. 3 * 4 * This program is licensed under the BSD license, read LICENSE.BSD 5 * for further information 6 */ 7 8 /* 9 * problems.c 10 * 11 */ 12 13 #include <stdio.h> 14 #include <stdlib.h> 15 #include <unistd.h> 16 #include <string.h> 17 #include <assert.h> 18 19 #include "solver.h" 20 #include "solver_private.h" 21 #include "bitmap.h" 22 #include "pool.h" 23 #include "util.h" 24 #include "evr.h" 25 #include "solverdebug.h" 26 27 28 /**********************************************************************************/ 29 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. 33 */ 34 35 void 36 solver_disableproblem(Solver *solv, Id v) 37 { 38 Rule *r; 39 int i; 40 Id *jp; 41 42 if (v > 0) 43 { 44 if (v >= solv->infarchrules && v < solv->infarchrules_end) 45 { 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) 49 v--; 50 for (; v < solv->infarchrules_end && pool->solvables[-solv->rules[v].p].name == name; v++) 51 solver_disablerule(solv, solv->rules + v); 52 return; 53 } 54 if (v >= solv->duprules && v < solv->duprules_end) 55 { 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) 59 v--; 60 for (; v < solv->duprules_end && pool->solvables[-solv->rules[v].p].name == name; v++) 61 solver_disablerule(solv, solv->rules + v); 62 return; 63 } 64 solver_disablerule(solv, solv->rules + v); 65 #if 0 66 /* XXX: doesn't work */ 67 if (v >= solv->updaterules && v < solv->updaterules_end) 68 { 69 /* enable feature rule if we disabled the update rule */ 70 r = solv->rules + (v - solv->updaterules + solv->featurerules); 71 if (r->p) 72 solver_enablerule(solv, r); 73 } 74 #endif 75 return; 76 } 77 v = -(v + 1); 78 jp = solv->ruletojob.elements; 79 for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++, jp++) 80 if (*jp == v) 81 solver_disablerule(solv, r); 82 } 83 84 /*------------------------------------------------------------------- 85 * enableproblem 86 */ 87 88 void 89 solver_enableproblem(Solver *solv, Id v) 90 { 91 Rule *r; 92 int i; 93 Id *jp; 94 95 if (v > 0) 96 { 97 if (v >= solv->infarchrules && v < solv->infarchrules_end) 98 { 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) 102 v--; 103 for (; v < solv->infarchrules_end && pool->solvables[-solv->rules[v].p].name == name; v++) 104 solver_enablerule(solv, solv->rules + v); 105 return; 106 } 107 if (v >= solv->duprules && v < solv->duprules_end) 108 { 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) 112 v--; 113 for (; v < solv->duprules_end && pool->solvables[-solv->rules[v].p].name == name; v++) 114 solver_enablerule(solv, solv->rules + v); 115 return; 116 } 117 if (v >= solv->featurerules && v < solv->featurerules_end) 118 { 119 /* do not enable feature rule if update rule is enabled */ 120 r = solv->rules + (v - solv->featurerules + solv->updaterules); 121 if (r->d >= 0) 122 return; 123 } 124 solver_enablerule(solv, solv->rules + v); 125 if (v >= solv->updaterules && v < solv->updaterules_end) 126 { 127 /* disable feature rule when enabling update rule */ 128 r = solv->rules + (v - solv->updaterules + solv->featurerules); 129 if (r->p) 130 solver_disablerule(solv, r); 131 } 132 return; 133 } 134 v = -(v + 1); 135 jp = solv->ruletojob.elements; 136 for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++, jp++) 137 if (*jp == v) 138 solver_enablerule(solv, r); 139 } 140 141 142 /*------------------------------------------------------------------- 143 * enable weak rules 144 * 145 * Reenable all disabled weak rules (marked in weakrulemap) 146 * 147 */ 148 149 static void 150 enableweakrules(Solver *solv) 151 { 152 int i; 153 Rule *r; 154 155 for (i = 1, r = solv->rules + i; i < solv->learntrules; i++, r++) 156 { 157 if (r->d >= 0) /* already enabled? */ 158 continue; 159 if (!MAPTST(&solv->weakrulemap, i)) 160 continue; 161 solver_enablerule(solv, r); 162 } 163 } 164 165 166 /*------------------------------------------------------------------- 167 * 168 * refine_suggestion 169 * 170 * at this point, all rules that led to conflicts are disabled. 171 * we re-enable all rules of a problem set but rule "sug", then 172 * continue to disable more rules until there as again a solution. 173 */ 174 175 /* FIXME: think about conflicting assertions */ 176 177 static void 178 refine_suggestion(Solver *solv, Id *problem, Id sug, Queue *refined, int essentialok) 179 { 180 Pool *pool = solv->pool; 181 int i, j; 182 Id v; 183 Queue disabled; 184 int disabledcnt; 185 186 IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS) 187 { 188 POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "refine_suggestion start\n"); 189 for (i = 0; problem[i]; i++) 190 { 191 if (problem[i] == sug) 192 POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "=> "); 193 solver_printproblem(solv, problem[i]); 194 } 195 } 196 queue_empty(refined); 197 if (!essentialok && sug < 0 && (solv->job.elements[-sug - 1] & SOLVER_ESSENTIAL) != 0) 198 return; 199 queue_init(&disabled); 200 queue_push(refined, sug); 201 202 /* re-enable all problem rules with the exception of "sug"(gestion) */ 203 solver_reset(solv); 204 205 for (i = 0; problem[i]; i++) 206 if (problem[i] != sug) 207 solver_enableproblem(solv, problem[i]); 208 209 if (sug < 0) 210 solver_reenablepolicyrules(solv, -sug); 211 else if (sug >= solv->updaterules && sug < solv->updaterules_end) 212 { 213 /* enable feature rule */ 214 Rule *r = solv->rules + solv->featurerules + (sug - solv->updaterules); 215 if (r->p) 216 solver_enablerule(solv, r); 217 } 218 219 enableweakrules(solv); 220 221 for (;;) 222 { 223 int njob, nfeature, nupdate, pass; 224 queue_empty(&solv->problems); 225 solver_reset(solv); 226 227 if (!solv->problems.count) 228 solver_run_sat(solv, 0, 0); 229 230 if (!solv->problems.count) 231 { 232 POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "no more problems!\n"); 233 break; /* great, no more problems */ 234 } 235 disabledcnt = disabled.count; 236 /* start with 1 to skip over proof index */ 237 njob = nfeature = nupdate = 0; 238 for (pass = 0; pass < 2; pass++) 239 { 240 for (i = 1; i < solv->problems.count - 1; i++) 241 { 242 /* ignore solutions in refined */ 243 v = solv->problems.elements[i]; 244 if (v == 0) 245 break; /* end of problem reached */ 246 if (sug != v) 247 { 248 /* check if v is in the given problems list 249 * we allow disabling all problem rules *after* sug in 250 * pass 2, to prevent getting the same solution twice */ 251 for (j = 0; problem[j]; j++) 252 if (problem[j] == v || (pass && problem[j] == sug)) 253 break; 254 if (problem[j] == v) 255 continue; 256 } 257 if (v >= solv->featurerules && v < solv->featurerules_end) 258 nfeature++; 259 else if (v > 0) 260 nupdate++; 261 else 262 { 263 if (!essentialok && (solv->job.elements[-v - 1] & SOLVER_ESSENTIAL) != 0) 264 continue; /* not that one! */ 265 njob++; 266 } 267 queue_push(&disabled, v); 268 } 269 if (disabled.count != disabledcnt) 270 break; 271 } 272 if (disabled.count == disabledcnt) 273 { 274 /* no solution found, this was an invalid suggestion! */ 275 POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "no solution found!\n"); 276 refined->count = 0; 277 break; 278 } 279 if (!njob && nupdate && nfeature) 280 { 281 /* got only update rules, filter out feature rules */ 282 POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "throwing away feature rules\n"); 283 for (i = j = disabledcnt; i < disabled.count; i++) 284 { 285 v = disabled.elements[i]; 286 if (v < solv->featurerules || v >= solv->featurerules_end) 287 disabled.elements[j++] = v; 288 } 289 disabled.count = j; 290 nfeature = 0; 291 } 292 if (disabled.count == disabledcnt + 1) 293 { 294 /* just one suggestion, add it to refined list */ 295 v = disabled.elements[disabledcnt]; 296 if (!nfeature && v != sug) 297 queue_push(refined, v); /* do not record feature rules */ 298 solver_disableproblem(solv, v); 299 if (v >= solv->updaterules && v < solv->updaterules_end) 300 { 301 Rule *r = solv->rules + (v - solv->updaterules + solv->featurerules); 302 if (r->p) 303 solver_enablerule(solv, r); /* enable corresponding feature rule */ 304 } 305 if (v < 0) 306 solver_reenablepolicyrules(solv, -v); 307 } 308 else 309 { 310 /* more than one solution, disable all */ 311 /* do not push anything on refine list, as we do not know which solution to choose */ 312 /* thus, the user will get another problem if he selects this solution, where he 313 * can choose the right one */ 314 IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS) 315 { 316 POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "more than one solution found:\n"); 317 for (i = disabledcnt; i < disabled.count; i++) 318 solver_printproblem(solv, disabled.elements[i]); 319 } 320 for (i = disabledcnt; i < disabled.count; i++) 321 { 322 v = disabled.elements[i]; 323 solver_disableproblem(solv, v); 324 if (v >= solv->updaterules && v < solv->updaterules_end) 325 { 326 Rule *r = solv->rules + (v - solv->updaterules + solv->featurerules); 327 if (r->p) 328 solver_enablerule(solv, r); 329 } 330 } 331 } 332 } 333 /* all done, get us back into the same state as before */ 334 /* enable refined rules again */ 335 for (i = 0; i < disabled.count; i++) 336 solver_enableproblem(solv, disabled.elements[i]); 337 queue_free(&disabled); 338 /* reset policy rules */ 339 for (i = 0; problem[i]; i++) 340 solver_enableproblem(solv, problem[i]); 341 solver_disablepolicyrules(solv); 342 /* disable problem rules again */ 343 for (i = 0; problem[i]; i++) 344 solver_disableproblem(solv, problem[i]); 345 POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "refine_suggestion end\n"); 346 } 347 348 349 /*------------------------------------------------------------------- 350 * sorting helper for problems 351 * 352 * bring update rules before job rules 353 * make essential job rules last 354 */ 355 356 static int 357 problems_sortcmp(const void *ap, const void *bp, void *dp) 358 { 359 Queue *job = dp; 360 Id a = *(Id *)ap, b = *(Id *)bp; 361 if (a < 0 && b > 0) 362 return 1; 363 if (a > 0 && b < 0) 364 return -1; 365 if (a < 0 && b < 0) 366 { 367 int af = job->elements[-a - 1] & SOLVER_ESSENTIAL; 368 int bf = job->elements[-b - 1] & SOLVER_ESSENTIAL; 369 int x = af - bf; 370 if (x) 371 return x; 372 } 373 return a - b; 374 } 375 376 /* 377 * convert a solution rule into a job modifier 378 */ 379 static void 380 convertsolution(Solver *solv, Id why, Queue *solutionq) 381 { 382 Pool *pool = solv->pool; 383 if (why < 0) 384 { 385 why = -why; 386 if (why < solv->pooljobcnt) 387 { 388 queue_push(solutionq, SOLVER_SOLUTION_POOLJOB); 389 queue_push(solutionq, why); 390 } 391 else 392 { 393 queue_push(solutionq, SOLVER_SOLUTION_JOB); 394 queue_push(solutionq, why - solv->pooljobcnt); 395 } 396 return; 397 } 398 if (why >= solv->infarchrules && why < solv->infarchrules_end) 399 { 400 Id p, name; 401 /* infarch rule, find replacement */ 402 assert(solv->rules[why].p < 0); 403 name = pool->solvables[-solv->rules[why].p].name; 404 while (why > solv->infarchrules && pool->solvables[-solv->rules[why - 1].p].name == name) 405 why--; 406 p = 0; 407 for (; why < solv->infarchrules_end && pool->solvables[-solv->rules[why].p].name == name; why++) 408 if (solv->decisionmap[-solv->rules[why].p] > 0) 409 { 410 p = -solv->rules[why].p; 411 break; 412 } 413 if (!p) 414 return; /* false alarm */ 415 queue_push(solutionq, SOLVER_SOLUTION_INFARCH); 416 queue_push(solutionq, p); 417 return; 418 } 419 if (why >= solv->duprules && why < solv->duprules_end) 420 { 421 Id p, name; 422 /* dist upgrade rule, find replacement */ 423 assert(solv->rules[why].p < 0); 424 name = pool->solvables[-solv->rules[why].p].name; 425 while (why > solv->duprules && pool->solvables[-solv->rules[why - 1].p].name == name) 426 why--; 427 p = 0; 428 for (; why < solv->duprules_end && pool->solvables[-solv->rules[why].p].name == name; why++) 429 if (solv->decisionmap[-solv->rules[why].p] > 0) 430 { 431 p = -solv->rules[why].p; 432 break; 433 } 434 if (!p) 435 return; /* false alarm */ 436 queue_push(solutionq, SOLVER_SOLUTION_DISTUPGRADE); 437 queue_push(solutionq, p); 438 return; 439 } 440 if (why >= solv->updaterules && why < solv->updaterules_end) 441 { 442 /* update rule, find replacement package */ 443 Id p, pp, rp = 0; 444 Rule *rr; 445 446 /* check if this is a false positive, i.e. the update rule is fulfilled */ 447 rr = solv->rules + why; 448 FOR_RULELITERALS(p, pp, rr) 449 if (p > 0 && solv->decisionmap[p] > 0) 450 return; /* false alarm */ 451 452 p = solv->installed->start + (why - solv->updaterules); 453 if (solv->dupmap_all && solv->rules[why].p != p && solv->decisionmap[p] > 0) 454 { 455 /* distupgrade case, allow to keep old package */ 456 queue_push(solutionq, SOLVER_SOLUTION_DISTUPGRADE); 457 queue_push(solutionq, p); 458 return; 459 } 460 if (solv->decisionmap[p] > 0) 461 return; /* false alarm, turned out we can keep the package */ 462 rr = solv->rules + solv->featurerules + (why - solv->updaterules); 463 if (!rr->p) 464 rr = solv->rules + why; 465 if (rr->w2) 466 { 467 int mvrp = 0; /* multi-version replacement */ 468 FOR_RULELITERALS(rp, pp, rr) 469 { 470 if (rp > 0 && solv->decisionmap[rp] > 0 && pool->solvables[rp].repo != solv->installed) 471 { 472 mvrp = rp; 473 if (!(solv->multiversion.size && MAPTST(&solv->multiversion, rp))) 474 break; 475 } 476 } 477 if (!rp && mvrp) 478 { 479 /* found only multi-version replacements */ 480 /* have to split solution into two parts */ 481 queue_push(solutionq, p); 482 queue_push(solutionq, mvrp); 483 } 484 } 485 queue_push(solutionq, p); 486 queue_push(solutionq, rp); 487 return; 488 } 489 if (why >= solv->bestrules && why < solv->bestrules_end) 490 { 491 int mvrp; 492 Id p, pp, rp = 0; 493 Rule *rr; 494 /* check false positive */ 495 rr = solv->rules + why; 496 FOR_RULELITERALS(p, pp, rr) 497 if (p > 0 && solv->decisionmap[p] > 0) 498 return; /* false alarm */ 499 /* check update/feature rule */ 500 p = solv->bestrules_pkg[why - solv->bestrules]; 501 if (p < 0) 502 { 503 /* install job */ 504 queue_push(solutionq, 0); 505 queue_push(solutionq, solv->ruletojob.elements[-p - solv->jobrules] + 1); 506 return; 507 } 508 if (solv->decisionmap[p] > 0) 509 { 510 /* disable best rule by keeping the old package */ 511 queue_push(solutionq, SOLVER_SOLUTION_BEST); 512 queue_push(solutionq, p); 513 return; 514 } 515 rr = solv->rules + solv->featurerules + (p - solv->installed->start); 516 if (!rr->p) 517 rr = solv->rules + solv->updaterules + (p - solv->installed->start); 518 mvrp = 0; /* multi-version replacement */ 519 FOR_RULELITERALS(rp, pp, rr) 520 if (rp > 0 && solv->decisionmap[rp] > 0 && pool->solvables[rp].repo != solv->installed) 521 { 522 mvrp = rp; 523 if (!(solv->multiversion.size && MAPTST(&solv->multiversion, rp))) 524 break; 525 } 526 if (!rp && mvrp) 527 { 528 queue_push(solutionq, SOLVER_SOLUTION_BEST); /* split, see above */ 529 queue_push(solutionq, mvrp); 530 queue_push(solutionq, p); 531 queue_push(solutionq, 0); 532 return; 533 } 534 if (rp) 535 { 536 queue_push(solutionq, SOLVER_SOLUTION_BEST); 537 queue_push(solutionq, rp); 538 } 539 return; 540 } 541 } 542 543 /* 544 * convert problem data into a form usable for refining. 545 * Returns the number of problems. 546 */ 547 int 548 solver_prepare_solutions(Solver *solv) 549 { 550 int i, j = 1, idx; 551 552 if (!solv->problems.count) 553 return 0; 554 queue_empty(&solv->solutions); 555 queue_push(&solv->solutions, 0); /* dummy so idx is always nonzero */ 556 idx = solv->solutions.count; 557 queue_push(&solv->solutions, -1); /* unrefined */ 558 /* proofidx stays in position, thus we start with 1 */ 559 for (i = 1; i < solv->problems.count; i++) 560 { 561 Id p = solv->problems.elements[i]; 562 queue_push(&solv->solutions, p); 563 if (p) 564 continue; 565 /* end of problem reached */ 566 solv->problems.elements[j++] = idx; 567 if (i + 1 >= solv->problems.count) 568 break; 569 /* start another problem */ 570 solv->problems.elements[j++] = solv->problems.elements[++i]; /* copy proofidx */ 571 idx = solv->solutions.count; 572 queue_push(&solv->solutions, -1); /* unrefined */ 573 } 574 solv->problems.count = j; 575 return j / 2; 576 } 577 578 /* 579 * refine the simple solution rule list provided by 580 * the solver into multiple lists of job modifiers. 581 */ 582 static void 583 create_solutions(Solver *solv, int probnr, int solidx) 584 { 585 Pool *pool = solv->pool; 586 Queue redoq; 587 Queue problem, solution, problems_save; 588 int i, j, nsol; 589 int essentialok; 590 unsigned int now; 591 int oldmistakes = solv->cleandeps_mistakes ? solv->cleandeps_mistakes->count : 0; 592 Id extraflags = -1; 593 594 now = solv_timems(0); 595 queue_init(&redoq); 596 /* save decisionq, decisionq_why, decisionmap */ 597 for (i = 0; i < solv->decisionq.count; i++) 598 { 599 Id p = solv->decisionq.elements[i]; 600 queue_push(&redoq, p); 601 queue_push(&redoq, solv->decisionq_why.elements[i]); 602 queue_push(&redoq, solv->decisionmap[p > 0 ? p : -p]); 603 } 604 /* save problems queue */ 605 problems_save = solv->problems; 606 memset(&solv->problems, 0, sizeof(solv->problems)); 607 608 /* extract problem from queue */ 609 queue_init(&problem); 610 for (i = solidx + 1; i < solv->solutions.count; i++) 611 { 612 Id v = solv->solutions.elements[i]; 613 if (!v) 614 break; 615 queue_push(&problem, v); 616 if (v < 0) 617 extraflags &= solv->job.elements[-v - 1]; 618 } 619 if (extraflags == -1) 620 extraflags = 0; 621 if (problem.count > 1) 622 solv_sort(problem.elements, problem.count, sizeof(Id), problems_sortcmp, &solv->job); 623 queue_push(&problem, 0); /* mark end for refine_suggestion */ 624 problem.count--; 625 #if 0 626 for (i = 0; i < problem.count; i++) 627 printf("PP %d %d\n", i, problem.elements[i]); 628 #endif 629 630 /* refine each solution element */ 631 nsol = 0; 632 essentialok = 0; 633 queue_init(&solution); 634 for (i = 0; i < problem.count; i++) 635 { 636 int solstart = solv->solutions.count; 637 refine_suggestion(solv, problem.elements, problem.elements[i], &solution, essentialok); 638 queue_push(&solv->solutions, 0); /* reserve room for number of elements */ 639 for (j = 0; j < solution.count; j++) 640 convertsolution(solv, solution.elements[j], &solv->solutions); 641 if (solv->solutions.count == solstart + 1) 642 { 643 solv->solutions.count--; /* this one did not work out */ 644 if (nsol || i + 1 < problem.count) 645 continue; /* got one or still hope */ 646 if (!essentialok) 647 { 648 /* nothing found, start over */ 649 POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "nothing found, re-run with essentialok = 1\n"); 650 essentialok = 1; 651 i = -1; 652 continue; 653 } 654 /* this is bad, we found no solution */ 655 /* for now just offer a rule */ 656 POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "nothing found, already did essentialok, fake it\n"); 657 queue_push(&solv->solutions, 0); 658 for (j = 0; j < problem.count; j++) 659 { 660 convertsolution(solv, problem.elements[j], &solv->solutions); 661 if (solv->solutions.count > solstart + 1) 662 break; 663 } 664 if (solv->solutions.count == solstart + 1) 665 { 666 solv->solutions.count--; 667 continue; /* sorry */ 668 } 669 } 670 /* patch in number of solution elements */ 671 solv->solutions.elements[solstart] = (solv->solutions.count - (solstart + 1)) / 2; 672 queue_push(&solv->solutions, 0); /* add end marker */ 673 queue_push(&solv->solutions, 0); /* add end marker */ 674 queue_push(&solv->solutions, problem.elements[i]); /* just for bookkeeping */ 675 queue_push(&solv->solutions, extraflags & SOLVER_CLEANDEPS); /* our extraflags */ 676 solv->solutions.elements[solidx + 1 + nsol++] = solstart; 677 } 678 solv->solutions.elements[solidx + 1 + nsol] = 0; /* end marker */ 679 solv->solutions.elements[solidx] = nsol; 680 queue_free(&problem); 681 queue_free(&solution); 682 683 /* restore decisions */ 684 memset(solv->decisionmap, 0, pool->nsolvables * sizeof(Id)); 685 queue_empty(&solv->decisionq); 686 queue_empty(&solv->decisionq_why); 687 for (i = 0; i < redoq.count; i += 3) 688 { 689 Id p = redoq.elements[i]; 690 queue_push(&solv->decisionq, p); 691 queue_push(&solv->decisionq_why, redoq.elements[i + 1]); 692 solv->decisionmap[p > 0 ? p : -p] = redoq.elements[i + 2]; 693 } 694 queue_free(&redoq); 695 /* restore problems */ 696 queue_free(&solv->problems); 697 solv->problems = problems_save; 698 699 if (solv->cleandeps_mistakes) 700 { 701 if (oldmistakes) 702 queue_truncate(solv->cleandeps_mistakes, oldmistakes); 703 else 704 { 705 queue_free(solv->cleandeps_mistakes); 706 solv->cleandeps_mistakes = solv_free(solv->cleandeps_mistakes); 707 } 708 } 709 710 POOL_DEBUG(SOLV_DEBUG_STATS, "create_solutions for problem #%d took %d ms\n", probnr, solv_timems(now)); 711 } 712 713 714 /**************************************************************************/ 715 716 unsigned int 717 solver_problem_count(Solver *solv) 718 { 719 return solv->problems.count / 2; 720 } 721 722 Id 723 solver_next_problem(Solver *solv, Id problem) 724 { 725 if (!problem) 726 return solv->problems.count ? 1 : 0; 727 return (problem + 1) * 2 - 1 < solv->problems.count ? problem + 1 : 0; 728 } 729 730 unsigned int 731 solver_solution_count(Solver *solv, Id problem) 732 { 733 Id solidx = solv->problems.elements[problem * 2 - 1]; 734 if (solv->solutions.elements[solidx] < 0) 735 create_solutions(solv, problem, solidx); 736 return solv->solutions.elements[solidx]; 737 } 738 739 Id 740 solver_next_solution(Solver *solv, Id problem, Id solution) 741 { 742 Id solidx = solv->problems.elements[problem * 2 - 1]; 743 if (solv->solutions.elements[solidx] < 0) 744 create_solutions(solv, problem, solidx); 745 return solv->solutions.elements[solidx + solution + 1] ? solution + 1 : 0; 746 } 747 748 unsigned int 749 solver_solutionelement_count(Solver *solv, Id problem, Id solution) 750 { 751 Id solidx = solv->problems.elements[problem * 2 - 1]; 752 solidx = solv->solutions.elements[solidx + solution]; 753 return solv->solutions.elements[solidx]; 754 } 755 756 Id 757 solver_solutionelement_internalid(Solver *solv, Id problem, Id solution) 758 { 759 Id solidx = solv->problems.elements[problem * 2 - 1]; 760 solidx = solv->solutions.elements[solidx + solution]; 761 return solv->solutions.elements[solidx + 2 * solv->solutions.elements[solidx] + 3]; 762 } 763 764 Id 765 solver_solutionelement_extrajobflags(Solver *solv, Id problem, Id solution) 766 { 767 Id solidx = solv->problems.elements[problem * 2 - 1]; 768 solidx = solv->solutions.elements[solidx + solution]; 769 return solv->solutions.elements[solidx + 2 * solv->solutions.elements[solidx] + 4]; 770 } 771 772 773 /* 774 * return the next item of the proposed solution 775 * here are the possibilities for p / rp and what 776 * the solver expects the application to do: 777 * p rp 778 * ------------------------------------------------------- 779 * SOLVER_SOLUTION_INFARCH pkgid 780 * -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job 781 * SOLVER_SOLUTION_DISTUPGRADE pkgid 782 * -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job 783 * SOLVER_SOLUTION_BEST pkgid 784 * -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job 785 * SOLVER_SOLUTION_JOB jobidx 786 * -> remove job (jobidx - 1, jobidx) from job queue 787 * SOLVER_SOLUTION_POOLJOB jobidx 788 * -> remove job (jobidx - 1, jobidx) from pool job queue 789 * pkgid (> 0) 0 790 * -> add (SOLVER_ERASE|SOLVER_SOLVABLE, p) to the job 791 * pkgid (> 0) pkgid (> 0) 792 * -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job 793 * (this will replace package p) 794 * 795 * Thus, the solver will either ask the application to remove 796 * a specific job from the job queue, or ask to add an install/erase 797 * job to it. 798 * 799 */ 800 801 Id 802 solver_next_solutionelement(Solver *solv, Id problem, Id solution, Id element, Id *p, Id *rp) 803 { 804 Id solidx = solv->problems.elements[problem * 2 - 1]; 805 solidx = solv->solutions.elements[solidx + solution]; 806 if (!solidx) 807 return 0; 808 solidx += 1 + element * 2; 809 if (!solv->solutions.elements[solidx] && !solv->solutions.elements[solidx + 1]) 810 return 0; 811 *p = solv->solutions.elements[solidx]; 812 *rp = solv->solutions.elements[solidx + 1]; 813 return element + 1; 814 } 815 816 void 817 solver_take_solutionelement(Solver *solv, Id p, Id rp, Id extrajobflags, Queue *job) 818 { 819 int i; 820 821 if (p == SOLVER_SOLUTION_POOLJOB) 822 { 823 solv->pool->pooljobs.elements[rp - 1] = SOLVER_NOOP; 824 solv->pool->pooljobs.elements[rp] = 0; 825 return; 826 } 827 if (p == SOLVER_SOLUTION_JOB) 828 { 829 job->elements[rp - 1] = SOLVER_NOOP; 830 job->elements[rp] = 0; 831 return; 832 } 833 if (rp <= 0 && p <= 0) 834 return; /* just in case */ 835 if (rp > 0) 836 p = SOLVER_INSTALL|SOLVER_SOLVABLE|extrajobflags; 837 else 838 { 839 rp = p; 840 p = SOLVER_ERASE|SOLVER_SOLVABLE|extrajobflags; 841 } 842 for (i = 0; i < job->count; i += 2) 843 if (job->elements[i] == p && job->elements[i + 1] == rp) 844 return; 845 queue_push2(job, p, rp); 846 } 847 848 void 849 solver_take_solution(Solver *solv, Id problem, Id solution, Queue *job) 850 { 851 Id p, rp, element = 0; 852 Id extrajobflags = solver_solutionelement_extrajobflags(solv, problem, solution); 853 while ((element = solver_next_solutionelement(solv, problem, solution, element, &p, &rp)) != 0) 854 solver_take_solutionelement(solv, p, rp, extrajobflags, job); 855 } 856 857 858 /*------------------------------------------------------------------- 859 * 860 * find problem rule 861 */ 862 863 static void 864 findproblemrule_internal(Solver *solv, Id idx, Id *reqrp, Id *conrp, Id *sysrp, Id *jobrp, Map *rseen) 865 { 866 Id rid, d; 867 Id lreqr, lconr, lsysr, ljobr; 868 Rule *r; 869 Id jobassert = 0; 870 int i, reqset = 0; /* 0: unset, 1: installed, 2: jobassert, 3: assert */ 871 872 /* find us a jobassert rule */ 873 for (i = idx; (rid = solv->learnt_pool.elements[i]) != 0; i++) 874 { 875 if (rid < solv->jobrules || rid >= solv->jobrules_end) 876 continue; 877 r = solv->rules + rid; 878 d = r->d < 0 ? -r->d - 1 : r->d; 879 if (!d && r->w2 == 0 && r->p > 0) 880 { 881 jobassert = r->p; 882 break; 883 } 884 } 885 886 /* the problem rules are somewhat ordered from "near to the problem" to 887 * "near to the job" */ 888 lreqr = lconr = lsysr = ljobr = 0; 889 while ((rid = solv->learnt_pool.elements[idx++]) != 0) 890 { 891 assert(rid > 0); 892 if (rid >= solv->learntrules) 893 { 894 if (MAPTST(rseen, rid - solv->learntrules)) 895 continue; 896 MAPSET(rseen, rid - solv->learntrules); 897 findproblemrule_internal(solv, solv->learnt_why.elements[rid - solv->learntrules], &lreqr, &lconr, &lsysr, &ljobr, rseen); 898 } 899 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)) 900 { 901 if (!*jobrp) 902 *jobrp = rid; 903 } 904 else if (rid >= solv->updaterules && rid < solv->updaterules_end) 905 { 906 if (!*sysrp) 907 *sysrp = rid; 908 } 909 else 910 { 911 assert(rid < solv->rpmrules_end); 912 r = solv->rules + rid; 913 d = r->d < 0 ? -r->d - 1 : r->d; 914 if (!d && r->w2 < 0) 915 { 916 if (!*conrp) 917 *conrp = rid; 918 } 919 else 920 { 921 if (!d && r->w2 == 0 && reqset < 3) 922 { 923 if (*reqrp > 0 && r->p < -1) 924 { 925 Id op = -solv->rules[*reqrp].p; 926 if (op > 1 && solv->pool->solvables[op].arch != solv->pool->solvables[-r->p].arch) 927 continue; /* different arch, skip */ 928 } 929 /* prefer assertions */ 930 *reqrp = rid; 931 reqset = 3; 932 } 933 else if (jobassert && r->p == -jobassert) 934 { 935 /* prefer rules of job assertions */ 936 *reqrp = rid; 937 reqset = 2; 938 } 939 else if (solv->installed && r->p < 0 && solv->pool->solvables[-r->p].repo == solv->installed && reqset <= 1) 940 { 941 /* prefer rules of job installed package so that the user doesn't get confused by strange packages */ 942 *reqrp = rid; 943 reqset = 1; 944 } 945 else if (!*reqrp) 946 *reqrp = rid; 947 } 948 } 949 } 950 if (!*reqrp && lreqr) 951 *reqrp = lreqr; 952 if (!*conrp && lconr) 953 *conrp = lconr; 954 if (!*jobrp && ljobr) 955 *jobrp = ljobr; 956 if (!*sysrp && lsysr) 957 *sysrp = lsysr; 958 } 959 960 /* 961 * find problem rule 962 * 963 * search for a rule that describes the problem to the 964 * user. Actually a pretty hopeless task that may leave the user 965 * puzzled. To get all of the needed information use 966 * solver_findallproblemrules() instead. 967 */ 968 969 Id 970 solver_findproblemrule(Solver *solv, Id problem) 971 { 972 Id reqr, conr, sysr, jobr; 973 Id idx = solv->problems.elements[2 * problem - 2]; 974 Map rseen; 975 reqr = conr = sysr = jobr = 0; 976 map_init(&rseen, solv->learntrules ? solv->nrules - solv->learntrules : 0); 977 findproblemrule_internal(solv, idx, &reqr, &conr, &sysr, &jobr, &rseen); 978 map_free(&rseen); 979 if (reqr) 980 return reqr; /* some requires */ 981 if (conr) 982 return conr; /* some conflict */ 983 if (sysr) 984 return sysr; /* an update rule */ 985 if (jobr) 986 return jobr; /* a user request */ 987 assert(0); 988 return 0; 989 } 990 991 /*-------------------------------------------------------------------*/ 992 993 static void 994 findallproblemrules_internal(Solver *solv, Id idx, Queue *rules, Map *rseen) 995 { 996 Id rid; 997 while ((rid = solv->learnt_pool.elements[idx++]) != 0) 998 { 999 if (rid >= solv->learntrules) 1000 { 1001 if (MAPTST(rseen, rid - solv->learntrules)) 1002 continue; 1003 MAPSET(rseen, rid - solv->learntrules); 1004 findallproblemrules_internal(solv, solv->learnt_why.elements[rid - solv->learntrules], rules, rseen); 1005 continue; 1006 } 1007 queue_pushunique(rules, rid); 1008 } 1009 } 1010 1011 /* 1012 * find all problem rule 1013 * 1014 * return all rules that lead to the problem. This gives the user 1015 * all of the information to understand the problem, but the result 1016 * can be a large number of rules. 1017 */ 1018 1019 void 1020 solver_findallproblemrules(Solver *solv, Id problem, Queue *rules) 1021 { 1022 Map rseen; 1023 queue_empty(rules); 1024 map_init(&rseen, solv->learntrules ? solv->nrules - solv->learntrules : 0); 1025 findallproblemrules_internal(solv, solv->problems.elements[2 * problem - 2], rules, &rseen); 1026 map_free(&rseen); 1027 } 1028 1029 /* EOF */ 1030