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 "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 const char *
1030 solver_problemruleinfo2str(Solver *solv, SolverRuleinfo type, Id source, Id target, Id dep)
1031 {
1032   Pool *pool = solv->pool;
1033   char *s;
1034   switch (type)
1035     {
1036     case SOLVER_RULE_DISTUPGRADE:
1037       return pool_tmpjoin(pool, pool_solvid2str(pool, source), " does not belong to a distupgrade repository", 0);
1038     case SOLVER_RULE_INFARCH:
1039       return pool_tmpjoin(pool, pool_solvid2str(pool, source), " has inferior architecture", 0);
1040     case SOLVER_RULE_UPDATE:
1041       return pool_tmpjoin(pool, "problem with installed package ", pool_solvid2str(pool, source), 0);
1042     case SOLVER_RULE_JOB:
1043       return "conflicting requests";
1044     case SOLVER_RULE_JOB_UNSUPPORTED:
1045       return "unsupported request";
1046     case SOLVER_RULE_JOB_NOTHING_PROVIDES_DEP:
1047       return pool_tmpjoin(pool, "nothing provides requested ", pool_dep2str(pool, dep), 0);
1048     case SOLVER_RULE_JOB_UNKNOWN_PACKAGE:
1049       return pool_tmpjoin(pool, "package ", pool_dep2str(pool, dep), " does not exist");
1050     case SOLVER_RULE_JOB_PROVIDED_BY_SYSTEM:
1051       return pool_tmpjoin(pool, pool_dep2str(pool, dep), " is provided by the system", 0);
1052     case SOLVER_RULE_RPM:
1053       return "some dependency problem";
1054     case SOLVER_RULE_RPM_NOT_INSTALLABLE:
1055       return pool_tmpjoin(pool, "package ", pool_solvid2str(pool, source), " is not installable");
1056     case SOLVER_RULE_RPM_NOTHING_PROVIDES_DEP:
1057       s = pool_tmpjoin(pool, "nothing provides ", pool_dep2str(pool, dep), 0);
1058       return pool_tmpappend(pool, s, " needed by ", pool_solvid2str(pool, source));
1059     case SOLVER_RULE_RPM_SAME_NAME:
1060       s = pool_tmpjoin(pool, "cannot install both ", pool_solvid2str(pool, source), 0);
1061       return pool_tmpappend(pool, s, " and ", pool_solvid2str(pool, target));
1062     case SOLVER_RULE_RPM_PACKAGE_CONFLICT:
1063       s = pool_tmpjoin(pool, "package ", pool_solvid2str(pool, source), 0);
1064       s = pool_tmpappend(pool, s, " conflicts with ", pool_dep2str(pool, dep));
1065       return pool_tmpappend(pool, s, " provided by ", pool_solvid2str(pool, target));
1066     case SOLVER_RULE_RPM_PACKAGE_OBSOLETES:
1067       s = pool_tmpjoin(pool, "package ", pool_solvid2str(pool, source), 0);
1068       s = pool_tmpappend(pool, s, " obsoletes ", pool_dep2str(pool, dep));
1069       return pool_tmpappend(pool, s, " provided by ", pool_solvid2str(pool, target));
1070     case SOLVER_RULE_RPM_INSTALLEDPKG_OBSOLETES:
1071       s = pool_tmpjoin(pool, "installed package ", pool_solvid2str(pool, source), 0);
1072       s = pool_tmpappend(pool, s, " obsoletes ", pool_dep2str(pool, dep));
1073       return pool_tmpappend(pool, s, " provided by ", pool_solvid2str(pool, target));
1074     case SOLVER_RULE_RPM_IMPLICIT_OBSOLETES:
1075       s = pool_tmpjoin(pool, "package ", pool_solvid2str(pool, source), 0);
1076       s = pool_tmpappend(pool, s, " implicitly obsoletes ", pool_dep2str(pool, dep));
1077       return pool_tmpappend(pool, s, " provided by ", pool_solvid2str(pool, target));
1078     case SOLVER_RULE_RPM_PACKAGE_REQUIRES:
1079       s = pool_tmpjoin(pool, "package ", pool_solvid2str(pool, source), " requires ");
1080       return pool_tmpappend(pool, s, pool_dep2str(pool, dep), ", but none of the providers can be installed");
1081     case SOLVER_RULE_RPM_SELF_CONFLICT:
1082       s = pool_tmpjoin(pool, "package ", pool_solvid2str(pool, source), " conflicts with ");
1083       return pool_tmpappend(pool, s, pool_dep2str(pool, dep), " provided by itself");
1084     default:
1085       return "bad problem rule type";
1086     }
1087 }
1088
1089 const char *
1090 solver_solutionelement2str(Solver *solv, Id p, Id rp)
1091 {
1092   Pool *pool = solv->pool;
1093   if (p == SOLVER_SOLUTION_JOB || p == SOLVER_SOLUTION_POOLJOB)
1094     {
1095       Id how, what;
1096       if (p == SOLVER_SOLUTION_JOB)
1097         rp += solv->pooljobcnt;
1098       how = solv->job.elements[rp - 1];
1099       what = solv->job.elements[rp];
1100       return pool_tmpjoin(pool, "do not ask to ", pool_job2str(pool, how, what, 0), 0);
1101     }
1102   else if (p == SOLVER_SOLUTION_INFARCH)
1103     {
1104       Solvable *s = pool->solvables + rp;
1105       if (solv->installed && s->repo == solv->installed)
1106         return pool_tmpjoin(pool, "keep ", pool_solvable2str(pool, s), " despite the inferior architecture");
1107       else
1108         return pool_tmpjoin(pool, "install ", pool_solvable2str(pool, s), " despite the inferior architecture");
1109     }
1110   else if (p == SOLVER_SOLUTION_DISTUPGRADE)
1111     {
1112       Solvable *s = pool->solvables + rp;
1113       if (solv->installed && s->repo == solv->installed)
1114         return pool_tmpjoin(pool, "keep obsolete ", pool_solvable2str(pool, s), 0);
1115       else
1116         return pool_tmpjoin(pool, "install ", pool_solvable2str(pool, s), " from excluded repository");
1117     }
1118   else if (p == SOLVER_SOLUTION_BEST)
1119     {
1120       Solvable *s = pool->solvables + rp;
1121       if (solv->installed && s->repo == solv->installed)
1122         return pool_tmpjoin(pool, "keep old ", pool_solvable2str(pool, s), 0);
1123       else
1124         return pool_tmpjoin(pool, "install ", pool_solvable2str(pool, s), " despite the old version");
1125     }
1126   else if (p > 0 && rp == 0)
1127     return pool_tmpjoin(pool, "allow deinstallation of ", pool_solvid2str(pool, p), 0);
1128   else if (p > 0 && rp > 0)
1129     {
1130       const char *sp = pool_solvid2str(pool, p);
1131       const char *srp = pool_solvid2str(pool, rp);
1132       const char *str = pool_tmpjoin(pool, "allow replacement of ", sp, 0);
1133       return pool_tmpappend(pool, str, " with ", srp);
1134     }
1135   else
1136     return "bad solution element";
1137 }
1138