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           break;                /* great, no more problems */
 233         }
 234       disabledcnt = disabled.count;
 235       /* start with 1 to skip over proof index */
 236       njob = nfeature = nupdate = 0;
 237       for (i = 1; i < solv->problems.count - 1; i++)
 238         {
 239           /* ignore solutions in refined */
 240           v = solv->problems.elements[i];
 241           if (v == 0)
 242             break;      /* end of problem reached */
 243           for (j = 0; problem[j]; j++)
 244             if (problem[j] != sug && problem[j] == v)
 245               break;
 246           if (problem[j])
 247             continue;
 248           if (v >= solv->featurerules && v < solv->featurerules_end)
 249             nfeature++;
 250           else if (v > 0)
 251             nupdate++;
 252           else
 253             {
 254               if (!essentialok && (solv->job.elements[-v -1] & SOLVER_ESSENTIAL) != 0)
 255                 continue;       /* not that one! */
 256               njob++;
 257             }
 258           queue_push(&disabled, v);
 259         }
 260       if (disabled.count == disabledcnt)
 261         {
 262           /* no solution found, this was an invalid suggestion! */
 263           POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "no solution found!\n");
 264           refined->count = 0;
 265           break;
 266         }
 267       if (!njob && nupdate && nfeature)
 268         {
 269           /* got only update rules, filter out feature rules */
 270           POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "throwing away feature rules\n");
 271           for (i = j = disabledcnt; i < disabled.count; i++)
 272             {
 273               v = disabled.elements[i];
 274               if (v < solv->featurerules || v >= solv->featurerules_end)
 275                 disabled.elements[j++] = v;
 276             }
 277           disabled.count = j;
 278           nfeature = 0;
 279         }
 280       if (disabled.count == disabledcnt + 1)
 281         {
 282           /* just one suggestion, add it to refined list */
 283           v = disabled.elements[disabledcnt];
 284           if (!nfeature)
 285             queue_push(refined, v);     /* do not record feature rules */
 286           solver_disableproblem(solv, v);
 287           if (v >= solv->updaterules && v < solv->updaterules_end)
 288             {
 289               Rule *r = solv->rules + (v - solv->updaterules + solv->featurerules);
 290               if (r->p)
 291                 solver_enablerule(solv, r);     /* enable corresponding feature rule */
 292             }
 293           if (v < 0)
 294             solver_reenablepolicyrules(solv, -(v + 1));
 295         }
 296       else
 297         {
 298           /* more than one solution, disable all */
 299           /* do not push anything on refine list, as we do not know which solution to choose */
 300           /* thus, the user will get another problem if he selects this solution, where he
 301            * can choose the right one */
 302           IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
 303             {
 304               POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "more than one solution found:\n");
 305               for (i = disabledcnt; i < disabled.count; i++)
 306                 solver_printproblem(solv, disabled.elements[i]);
 307             }
 308           for (i = disabledcnt; i < disabled.count; i++)
 309             {
 310               v = disabled.elements[i];
 311               solver_disableproblem(solv, v);
 312               if (v >= solv->updaterules && v < solv->updaterules_end)
 313                 {
 314                   Rule *r = solv->rules + (v - solv->updaterules + solv->featurerules);
 315                   if (r->p)
 316                     solver_enablerule(solv, r);
 317                 }
 318             }
 319         }
 320     }
 321   /* all done, get us back into the same state as before */
 322   /* enable refined rules again */
 323   for (i = 0; i < disabled.count; i++)
 324     solver_enableproblem(solv, disabled.elements[i]);
 325   queue_free(&disabled);
 326   /* reset policy rules */
 327   for (i = 0; problem[i]; i++)
 328     solver_enableproblem(solv, problem[i]);
 329   solver_disablepolicyrules(solv);
 330   /* disable problem rules again */
 331   for (i = 0; problem[i]; i++)
 332     solver_disableproblem(solv, problem[i]);
 333   POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "refine_suggestion end\n");
 334 }
 335
 336
 337 /*-------------------------------------------------------------------
 338  * sorting helper for problems
 339  *
 340  * bring update rules before job rules
 341  * make essential job rules last
 342  */
 343
 344 static int
 345 problems_sortcmp(const void *ap, const void *bp, void *dp)
 346 {
 347   Queue *job = dp;
 348   Id a = *(Id *)ap, b = *(Id *)bp;
 349   if (a < 0 && b > 0)
 350     return 1;
 351   if (a > 0 && b < 0)
 352     return -1;
 353   if (a < 0 && b < 0)
 354     {
 355       int af = job->elements[-a - 1] & SOLVER_ESSENTIAL;
 356       int bf = job->elements[-b - 1] & SOLVER_ESSENTIAL;
 357       int x = af - bf;
 358       if (x)
 359         return x;
 360     }
 361   return a - b;
 362 }
 363
 364 /*
 365  * convert a solution rule into a job modifier
 366  */
 367 static void
 368 convertsolution(Solver *solv, Id why, Queue *solutionq)
 369 {
 370   Pool *pool = solv->pool;
 371   if (why < 0)
 372     {
 373       queue_push(solutionq, 0);
 374       queue_push(solutionq, -why);
 375       return;
 376     }
 377   if (why >= solv->infarchrules && why < solv->infarchrules_end)
 378     {
 379       Id p, name;
 380       /* infarch rule, find replacement */
 381       assert(solv->rules[why].p < 0);
 382       name = pool->solvables[-solv->rules[why].p].name;
 383       while (why > solv->infarchrules && pool->solvables[-solv->rules[why - 1].p].name == name)
 384         why--;
 385       p = 0;
 386       for (; why < solv->infarchrules_end && pool->solvables[-solv->rules[why].p].name == name; why++)
 387         if (solv->decisionmap[-solv->rules[why].p] > 0)
 388           {
 389             p = -solv->rules[why].p;
 390             break;
 391           }
 392       if (!p)
 393         return;         /* false alarm */
 394       queue_push(solutionq, SOLVER_SOLUTION_INFARCH);
 395       queue_push(solutionq, p);
 396       return;
 397     }
 398   if (why >= solv->duprules && why < solv->duprules_end)
 399     {
 400       Id p, name;
 401       /* dist upgrade rule, find replacement */
 402       assert(solv->rules[why].p < 0);
 403       name = pool->solvables[-solv->rules[why].p].name;
 404       while (why > solv->duprules && pool->solvables[-solv->rules[why - 1].p].name == name)
 405         why--;
 406       p = 0;
 407       for (; why < solv->duprules_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_DISTUPGRADE);
 416       queue_push(solutionq, p);
 417       return;
 418     }
 419   if (why >= solv->updaterules && why < solv->updaterules_end)
 420     {
 421       /* update rule, find replacement package */
 422       Id p, *dp, rp = 0;
 423       Rule *rr;
 424
 425       assert(why >= solv->updaterules && why < solv->updaterules_end);
 426       /* check if this is a false positive, i.e. the update rule is fulfilled */
 427       rr = solv->rules + why;
 428       FOR_RULELITERALS(p, dp, rr)
 429         if (p > 0 && solv->decisionmap[p] > 0)
 430           break;
 431       if (p)
 432         return;         /* false alarm */
 433
 434       p = solv->installed->start + (why - solv->updaterules);
 435       rr = solv->rules + solv->featurerules + (why - solv->updaterules);
 436       if (!rr->p)
 437         rr = solv->rules + why;
 438       if (solv->dupmap_all && solv->rules[why].p != p && solv->decisionmap[p] > 0)
 439         {
 440           /* distupgrade case, allow to keep old package */
 441           queue_push(solutionq, SOLVER_SOLUTION_DISTUPGRADE);
 442           queue_push(solutionq, p);
 443           return;
 444         }
 445       if (solv->decisionmap[p] > 0)
 446         return;         /* false alarm, turned out we can keep the package */
 447       if (rr->w2)
 448         {
 449           int mvrp = 0;         /* multi-version replacement */
 450           FOR_RULELITERALS(rp, dp, rr)
 451             {
 452               if (rp > 0 && solv->decisionmap[rp] > 0 && pool->solvables[rp].repo != solv->installed)
 453                 {
 454                   mvrp = rp;
 455                   if (!(solv->noobsoletes.size && MAPTST(&solv->noobsoletes, rp)))
 456                     break;
 457                 }
 458             }
 459           if (!rp && mvrp)
 460             {
 461               /* found only multi-version replacements */
 462               /* have to split solution into two parts */
 463               queue_push(solutionq, p);
 464               queue_push(solutionq, mvrp);
 465             }
 466         }
 467       queue_push(solutionq, p);
 468       queue_push(solutionq, rp);
 469       return;
 470     }
 471 }
 472
 473 /*
 474  * convert problem data into a form usable for refining.
 475  * Returns the number of problems.
 476  */
 477 int
 478 solver_prepare_solutions(Solver *solv)
 479 {
 480   int i, j = 1, idx = 1;
 481
 482   if (!solv->problems.count)
 483     return 0;
 484   queue_push(&solv->solutions, 0);
 485   queue_push(&solv->solutions, -1); /* unrefined */
 486   for (i = 1; i < solv->problems.count; i++)
 487     {
 488       Id p = solv->problems.elements[i];
 489       queue_push(&solv->solutions, p);
 490       if (p)
 491         continue;
 492       solv->problems.elements[j++] = idx;
 493       if (i + 1 >= solv->problems.count)
 494         break;
 495       solv->problems.elements[j++] = solv->problems.elements[++i];  /* copy proofidx */
 496       idx = solv->solutions.count;
 497       queue_push(&solv->solutions, -1);
 498     }
 499   solv->problems.count = j;
 500   return j / 2;
 501 }
 502
 503 /*
 504  * refine the simple solution rule list provided by
 505  * the solver into multiple lists of job modifiers.
 506  */
 507 static void
 508 create_solutions(Solver *solv, int probnr, int solidx)
 509 {
 510   Pool *pool = solv->pool;
 511   Queue redoq;
 512   Queue problem, solution, problems_save;
 513   int i, j, nsol;
 514   int essentialok;
 515   int recocount;
 516   unsigned int now;
 517
 518   now = sat_timems(0);
 519   recocount = solv->recommendations.count;
 520   solv->recommendations.count = 0;      /* so that revert() doesn't mess with it later */
 521   queue_init(&redoq);
 522   /* save decisionq, decisionq_why, decisionmap */
 523   for (i = 0; i < solv->decisionq.count; i++)
 524     {
 525       Id p = solv->decisionq.elements[i];
 526       queue_push(&redoq, p);
 527       queue_push(&redoq, solv->decisionq_why.elements[i]);
 528       queue_push(&redoq, solv->decisionmap[p > 0 ? p : -p]);
 529     }
 530   /* save problems queue */
 531   problems_save = solv->problems;
 532   memset(&solv->problems, 0, sizeof(solv->problems));
 533
 534   /* extract problem from queue */
 535   queue_init(&problem);
 536   for (i = solidx + 1; i < solv->solutions.count; i++)
 537     {
 538       Id v = solv->solutions.elements[i];
 539       if (!v)
 540         break;
 541       queue_push(&problem, v);
 542     }
 543   if (problem.count > 1)
 544     sat_sort(problem.elements, problem.count, sizeof(Id), problems_sortcmp, &solv->job);
 545   queue_push(&problem, 0);      /* mark end for refine_suggestion */
 546   problem.count--;
 547 #if 0
 548   for (i = 0; i < problem.count; i++)
 549     printf("PP %d %d\n", i, problem.elements[i]);
 550 #endif
 551
 552   /* refine each solution element */
 553   nsol = 0;
 554   essentialok = 0;
 555   queue_init(&solution);
 556   for (i = 0; i < problem.count; i++)
 557     {
 558       int solstart = solv->solutions.count;
 559       refine_suggestion(solv, problem.elements, problem.elements[i], &solution, essentialok);
 560       queue_push(&solv->solutions, 0);  /* reserve room for number of elements */
 561       for (j = 0; j < solution.count; j++)
 562         convertsolution(solv, solution.elements[j], &solv->solutions);
 563       if (solv->solutions.count == solstart + 1)
 564         {
 565           solv->solutions.count--;      /* this one did not work out */
 566           if (nsol || i + 1 < problem.count)
 567             continue;                   /* got one or still hope */
 568           if (!essentialok)
 569             {
 570               /* nothing found, start over */
 571               POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "nothing found, re-run with essentialok = 1\n");
 572               essentialok = 1;
 573               i = -1;
 574               continue;
 575             }
 576           /* this is bad, we found no solution */
 577           /* for now just offer a rule */
 578           POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "nothing found, already did essentialok, fake it\n");
 579           queue_push(&solv->solutions, 0);
 580           for (j = 0; j < problem.count; j++)
 581             {
 582               queue_empty(&solution);
 583               queue_push(&solution, problem.elements[j]);
 584               convertsolution(solv, solution.elements[j], &solv->solutions);
 585               if (solv->solutions.count > solstart + 1)
 586                 break;
 587             }
 588           if (solv->solutions.count == solstart + 1)
 589             {
 590               solv->solutions.count--;
 591               continue;         /* sorry */
 592             }
 593         }
 594       /* patch in number of solution elements */
 595       solv->solutions.elements[solstart] = (solv->solutions.count - (solstart + 1)) / 2;
 596       queue_push(&solv->solutions, 0);  /* add end marker */
 597       queue_push(&solv->solutions, 0);  /* add end marker */
 598       solv->solutions.elements[solidx + 1 + nsol++] = solstart;
 599     }
 600   solv->solutions.elements[solidx + 1 + nsol] = 0;      /* end marker */
 601   solv->solutions.elements[solidx] = nsol;
 602   queue_free(&problem);
 603   queue_free(&solution);
 604
 605   /* restore decisions */
 606   memset(solv->decisionmap, 0, pool->nsolvables * sizeof(Id));
 607   queue_empty(&solv->decisionq);
 608   queue_empty(&solv->decisionq_why);
 609   for (i = 0; i < redoq.count; i += 3)
 610     {
 611       Id p = redoq.elements[i];
 612       queue_push(&solv->decisionq, p);
 613       queue_push(&solv->decisionq_why, redoq.elements[i + 1]);
 614       solv->decisionmap[p > 0 ? p : -p] = redoq.elements[i + 2];
 615     }
 616   solv->recommendations.count = recocount;
 617   queue_free(&redoq);
 618   /* restore problems */
 619   queue_free(&solv->problems);
 620   solv->problems = problems_save;
 621   POOL_DEBUG(SAT_DEBUG_STATS, "create_solutions for problem #%d took %d ms\n", probnr, sat_timems(now));
 622 }
 623
 624
 625 /**************************************************************************/
 626
 627 unsigned int
 628 solver_problem_count(Solver *solv)
 629 {
 630   return solv->problems.count / 2;
 631 }
 632
 633 Id
 634 solver_next_problem(Solver *solv, Id problem)
 635 {
 636   if (!problem)
 637     return solv->problems.count ? 1 : 0;
 638   return (problem + 1) * 2 - 1 < solv->problems.count ? problem + 1 : 0;
 639 }
 640
 641 unsigned int
 642 solver_solution_count(Solver *solv, Id problem)
 643 {
 644   Id solidx = solv->problems.elements[problem * 2 - 1];
 645   if (solv->solutions.elements[solidx] < 0)
 646     create_solutions(solv, problem, solidx);
 647   return solv->solutions.elements[solidx];
 648 }
 649
 650 Id
 651 solver_next_solution(Solver *solv, Id problem, Id solution)
 652 {
 653   Id solidx = solv->problems.elements[problem * 2 - 1];
 654   if (solv->solutions.elements[solidx] < 0)
 655     create_solutions(solv, problem, solidx);
 656   return solv->solutions.elements[solidx + solution + 1] ? solution + 1 : 0;
 657 }
 658
 659 unsigned int
 660 solver_solutionelement_count(Solver *solv, Id problem, Id solution)
 661 {
 662   Id solidx = solv->problems.elements[problem * 2 - 1];
 663   solidx = solv->solutions.elements[solidx + solution];
 664   return solv->solutions.elements[solidx];
 665 }
 666
 667
 668 /*
 669  *  return the next item of the proposed solution
 670  *  here are the possibilities for p / rp and what
 671  *  the solver expects the application to do:
 672  *    p                             rp
 673  *  -------------------------------------------------------
 674  *    SOLVER_SOLUTION_INFARCH       pkgid
 675  *    -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job
 676  *    SOLVER_SOLUTION_DISTUPGRADE   pkgid
 677  *    -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job
 678  *    SOLVER_SOLUTION_JOB           jobidx
 679  *    -> remove job (jobidx - 1, jobidx) from job queue
 680  *    pkgid (> 0)                   0
 681  *    -> add (SOLVER_ERASE|SOLVER_SOLVABLE, p) to the job
 682  *    pkgid (> 0)                   pkgid (> 0)
 683  *    -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job
 684  *       (this will replace package p)
 685  *
 686  * Thus, the solver will either ask the application to remove
 687  * a specific job from the job queue, or ask to add an install/erase
 688  * job to it.
 689  *
 690  */
 691
 692 Id
 693 solver_next_solutionelement(Solver *solv, Id problem, Id solution, Id element, Id *p, Id *rp)
 694 {
 695   Id solidx = solv->problems.elements[problem * 2 - 1];
 696   solidx = solv->solutions.elements[solidx + solution];
 697   if (!solidx)
 698     return 0;
 699   solidx += 1 + element * 2;
 700   if (!solv->solutions.elements[solidx] && !solv->solutions.elements[solidx + 1])
 701     return 0;
 702   *p = solv->solutions.elements[solidx];
 703   *rp = solv->solutions.elements[solidx + 1];
 704   return element + 1;
 705 }
 706
 707 void
 708 solver_take_solutionelement(Solver *solv, Id p, Id rp, Queue *job)
 709 {
 710   int i;
 711
 712   if (p == SOLVER_SOLUTION_JOB)
 713     {
 714       job->elements[rp - 1] = SOLVER_NOOP;
 715       job->elements[rp] = 0;
 716       return;
 717     }
 718   if (rp <= 0 && p <= 0)
 719     return;     /* just in case */
 720   if (rp > 0)
 721     p = SOLVER_INSTALL|SOLVER_SOLVABLE;
 722   else
 723     {
 724       rp = p;
 725       p = SOLVER_ERASE|SOLVER_SOLVABLE;
 726     }
 727   for (i = 0; i < job->count; i += 2)
 728     if (job->elements[i] == p && job->elements[i + 1] == rp)
 729       return;
 730   queue_push2(job, p, rp);
 731 }
 732
 733 void
 734 solver_take_solution(Solver *solv, Id problem, Id solution, Queue *job)
 735 {
 736   Id p, rp, element = 0;
 737   while ((element = solver_next_solutionelement(solv, problem, solution, element, &p, &rp)) != 0)
 738     solver_take_solutionelement(solv, p, rp, job);
 739 }
 740
 741
 742 /*-------------------------------------------------------------------
 743  *
 744  * find problem rule
 745  */
 746
 747 static void
 748 findproblemrule_internal(Solver *solv, Id idx, Id *reqrp, Id *conrp, Id *sysrp, Id *jobrp)
 749 {
 750   Id rid, d;
 751   Id lreqr, lconr, lsysr, ljobr;
 752   Rule *r;
 753   Id jobassert = 0;
 754   int i, reqset = 0;    /* 0: unset, 1: installed, 2: jobassert, 3: assert */
 755
 756   /* find us a jobassert rule */
 757   for (i = idx; (rid = solv->learnt_pool.elements[i]) != 0; i++)
 758     {
 759       if (rid < solv->jobrules || rid >= solv->jobrules_end)
 760         continue;
 761       r = solv->rules + rid;
 762       d = r->d < 0 ? -r->d - 1 : r->d;
 763       if (!d && r->w2 == 0 && r->p > 0)
 764         {
 765           jobassert = r->p;
 766           break;
 767         }
 768     }
 769
 770   /* the problem rules are somewhat ordered from "near to the problem" to
 771    * "near to the job" */
 772   lreqr = lconr = lsysr = ljobr = 0;
 773   while ((rid = solv->learnt_pool.elements[idx++]) != 0)
 774     {
 775       assert(rid > 0);
 776       if (rid >= solv->learntrules)
 777         findproblemrule_internal(solv, solv->learnt_why.elements[rid - solv->learntrules], &lreqr, &lconr, &lsysr, &ljobr);
 778       else if ((rid >= solv->jobrules && rid < solv->jobrules_end) || (rid >= solv->infarchrules && rid < solv->infarchrules_end) || (rid >= solv->duprules && rid < solv->duprules_end))
 779         {
 780           if (!*jobrp)
 781             *jobrp = rid;
 782         }
 783       else if (rid >= solv->updaterules && rid < solv->updaterules_end)
 784         {
 785           if (!*sysrp)
 786             *sysrp = rid;
 787         }
 788       else
 789         {
 790           assert(rid < solv->rpmrules_end);
 791           r = solv->rules + rid;
 792           d = r->d < 0 ? -r->d - 1 : r->d;
 793           if (!d && r->w2 < 0)
 794             {
 795               if (!*conrp)
 796                 *conrp = rid;
 797             }
 798           else
 799             {
 800               if (!d && r->w2 == 0 && reqset < 3)
 801                 {
 802                   if (*reqrp > 0 && r->p < -1)
 803                     {
 804                       Id op = -solv->rules[*reqrp].p;
 805                       if (op > 1 && solv->pool->solvables[op].arch != solv->pool->solvables[-r->p].arch)
 806                         continue;       /* different arch, skip */
 807                     }
 808                   /* prefer assertions */
 809                   *reqrp = rid;
 810                   reqset = 3;
 811                 }
 812               else if (jobassert && r->p == -jobassert)
 813                 {
 814                   /* prefer rules of job assertions */
 815                   *reqrp = rid;
 816                   reqset = 2;
 817                 }
 818               else if (solv->installed && r->p < 0 && solv->pool->solvables[-r->p].repo == solv->installed && reqset <= 1)
 819                 {
 820                   /* prefer rules of job installed package so that the user doesn't get confused by strange packages */
 821                   *reqrp = rid;
 822                   reqset = 1;
 823                 }
 824               else if (!*reqrp)
 825                 *reqrp = rid;
 826             }
 827         }
 828     }
 829   if (!*reqrp && lreqr)
 830     *reqrp = lreqr;
 831   if (!*conrp && lconr)
 832     *conrp = lconr;
 833   if (!*jobrp && ljobr)
 834     *jobrp = ljobr;
 835   if (!*sysrp && lsysr)
 836     *sysrp = lsysr;
 837 }
 838
 839 /*
 840  * find problem rule
 841  *
 842  * search for a rule that describes the problem to the
 843  * user. Actually a pretty hopeless task that may leave the user
 844  * puzzled. To get all of the needed information use
 845  * solver_findallproblemrules() instead.
 846  */
 847
 848 Id
 849 solver_findproblemrule(Solver *solv, Id problem)
 850 {
 851   Id reqr, conr, sysr, jobr;
 852   Id idx = solv->problems.elements[2 * problem - 2];
 853   reqr = conr = sysr = jobr = 0;
 854   findproblemrule_internal(solv, idx, &reqr, &conr, &sysr, &jobr);
 855   if (reqr)
 856     return reqr;        /* some requires */
 857   if (conr)
 858     return conr;        /* some conflict */
 859   if (sysr)
 860     return sysr;        /* an update rule */
 861   if (jobr)
 862     return jobr;        /* a user request */
 863   assert(0);
 864 }
 865
 866 /*-------------------------------------------------------------------*/
 867
 868 static void
 869 findallproblemrules_internal(Solver *solv, Id idx, Queue *rules)
 870 {
 871   Id rid;
 872   while ((rid = solv->learnt_pool.elements[idx++]) != 0)
 873     {
 874       if (rid >= solv->learntrules)
 875         {
 876           findallproblemrules_internal(solv, solv->learnt_why.elements[rid - solv->learntrules], rules);
 877           continue;
 878         }
 879       queue_pushunique(rules, rid);
 880     }
 881 }
 882
 883 /*
 884  * find all problem rule
 885  *
 886  * return all rules that lead to the problem. This gives the user
 887  * all of the information to understand the problem, but the result
 888  * can be a large number of rules.
 889  */
 890
 891 void
 892 solver_findallproblemrules(Solver *solv, Id problem, Queue *rules)
 893 {
 894   queue_empty(rules);
 895   findallproblemrules_internal(solv, solv->problems.elements[2 * problem - 2], rules);
 896 }
 897
 898 /* obsolete function */
 899 SolverRuleinfo
 900 solver_problemruleinfo(Solver *solv, Queue *job, Id rid, Id *depp, Id *sourcep, Id *targetp)
 901 {
 902   return solver_ruleinfo(solv, rid, sourcep, targetp, depp);
 903 }
 904
 905 /* EOF */