src/problems.c

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