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 /* 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 static void
  35 solver_disableproblem(Solver *solv, Id v)
  36 {
  37   int i;
  38   Id *jp;
  39
  40   if (v > 0)
  41     {
  42       if (v >= solv->infarchrules && v < solv->infarchrules_end)
  43         {
  44           Pool *pool = solv->pool;
  45           Id name = pool->solvables[-solv->rules[v].p].name;
  46           while (v > solv->infarchrules && pool->solvables[-solv->rules[v - 1].p].name == name)
  47             v--;
  48           for (; v < solv->infarchrules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
  49             solver_disablerule(solv, solv->rules + v);
  50           return;
  51         }
  52       if (v >= solv->duprules && v < solv->duprules_end)
  53         {
  54           Pool *pool = solv->pool;
  55           Id name = pool->solvables[-solv->rules[v].p].name;
  56           while (v > solv->duprules && pool->solvables[-solv->rules[v - 1].p].name == name)
  57             v--;
  58           for (; v < solv->duprules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
  59             solver_disablerule(solv, solv->rules + v);
  60           return;
  61         }
  62       solver_disablerule(solv, solv->rules + v);
  63       return;
  64     }
  65   v = -(v + 1);
  66   jp = solv->ruletojob.elements;
  67   if (solv->bestrules_info)
  68     {
  69       int ni = solv->bestrules_up - solv->bestrules;
  70       for (i = 0; i < ni; i++)
  71         {
  72           int j = solv->bestrules_info[i];
  73           if (j < 0 && jp[-j - solv->jobrules] == v)
  74             solver_disablerule(solv, solv->rules + solv->bestrules + i);
  75         }
  76     }
  77   for (i = solv->jobrules; i < solv->jobrules_end; i++, jp++)
  78     if (*jp == v)
  79       solver_disablerule(solv, solv->rules + i);
  80 }
  81
  82 /*-------------------------------------------------------------------
  83  * enableproblem
  84  */
  85
  86 static void
  87 solver_enableproblem(Solver *solv, Id v)
  88 {
  89   Rule *r;
  90   int i;
  91   Id *jp;
  92
  93   if (v > 0)
  94     {
  95       if (v >= solv->infarchrules && v < solv->infarchrules_end)
  96         {
  97           Pool *pool = solv->pool;
  98           Id name = pool->solvables[-solv->rules[v].p].name;
  99           while (v > solv->infarchrules && pool->solvables[-solv->rules[v - 1].p].name == name)
 100             v--;
 101           for (; v < solv->infarchrules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
 102             solver_enablerule(solv, solv->rules + v);
 103           return;
 104         }
 105       if (v >= solv->duprules && v < solv->duprules_end)
 106         {
 107           Pool *pool = solv->pool;
 108           Id name = pool->solvables[-solv->rules[v].p].name;
 109           while (v > solv->duprules && pool->solvables[-solv->rules[v - 1].p].name == name)
 110             v--;
 111           for (; v < solv->duprules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
 112             solver_enablerule(solv, solv->rules + v);
 113           return;
 114         }
 115       if (v >= solv->featurerules && v < solv->featurerules_end)
 116         {
 117           /* do not enable feature rule if update rule is enabled */
 118           r = solv->rules + (v - solv->featurerules + solv->updaterules);
 119           if (r->d >= 0)
 120             return;
 121         }
 122       solver_enablerule(solv, solv->rules + v);
 123       if (v >= solv->updaterules && v < solv->updaterules_end)
 124         {
 125           /* disable feature rule when enabling update rule */
 126           r = solv->rules + (v - solv->updaterules + solv->featurerules);
 127           if (r->p)
 128             solver_disablerule(solv, r);
 129         }
 130       return;
 131     }
 132   v = -(v + 1);
 133   jp = solv->ruletojob.elements;
 134   if (solv->bestrules_info)
 135     {
 136       int ni = solv->bestrules_up - solv->bestrules;
 137       for (i = 0; i < ni; i++)
 138         {
 139           int j = solv->bestrules_info[i];
 140           if (j < 0 && jp[-j - solv->jobrules] == v)
 141             solver_enablerule(solv, solv->rules + solv->bestrules + i);
 142         }
 143     }
 144   for (i = solv->jobrules; i < solv->jobrules_end; i++, jp++)
 145     if (*jp == v)
 146       solver_enablerule(solv, solv->rules + i);
 147 }
 148
 149
 150 /*-------------------------------------------------------------------
 151  * turn a problem rule into a problem id by normalizing it
 152  */
 153 static Id
 154 solver_ruletoproblem(Solver *solv, Id rid)
 155 {
 156   if (rid >= solv->jobrules && rid < solv->jobrules_end)
 157     rid = -(solv->ruletojob.elements[rid - solv->jobrules] + 1);
 158   else if (rid >= solv->bestrules && rid < solv->bestrules_up && solv->bestrules_info[rid - solv->bestrules] < 0)
 159     rid = -(solv->ruletojob.elements[-solv->bestrules_info[rid - solv->bestrules] - solv->jobrules] + 1);
 160   else if (rid > solv->infarchrules && rid < solv->infarchrules_end)
 161     {
 162       Pool *pool = solv->pool;
 163       Id name = pool->solvables[-solv->rules[rid].p].name;
 164       while (rid > solv->infarchrules && pool->solvables[-solv->rules[rid - 1].p].name == name)
 165         rid--;
 166     }
 167   else if (rid > solv->duprules && rid < solv->duprules_end)
 168     {
 169       Pool *pool = solv->pool;
 170       Id name = pool->solvables[-solv->rules[rid].p].name;
 171       while (rid > solv->duprules && pool->solvables[-solv->rules[rid - 1].p].name == name)
 172         rid--;
 173     }
 174   return rid;
 175 }
 176
 177 /*-------------------------------------------------------------------
 178  * when the solver runs into a problem, it needs to disable all
 179  * involved non-pkg rules and record the rules for solution
 180  * generation.
 181  */
 182 void
 183 solver_recordproblem(Solver *solv, Id rid)
 184 {
 185   Id v = solver_ruletoproblem(solv, rid);
 186   /* return if problem already countains our rule */
 187   if (solv->problems.count)
 188     {
 189       int i;
 190       for (i = solv->problems.count - 1; i >= 0; i--)
 191         if (solv->problems.elements[i] == 0)    /* end of last problem reached? */
 192           break;
 193         else if (solv->problems.elements[i] == v)
 194           return;
 195     }
 196   queue_push(&solv->problems, v);
 197 }
 198
 199 /*-------------------------------------------------------------------
 200  * this is called when a problem is solved by disabling a rule.
 201  * It calls disableproblem and then re-enables policy rules
 202  */
 203 void
 204 solver_fixproblem(Solver *solv, Id rid)
 205 {
 206   Id v = solver_ruletoproblem(solv, rid);
 207   solver_disableproblem(solv, v);
 208   if (v < 0)
 209     solver_reenablepolicyrules(solv, -v);
 210 }
 211
 212 /*-------------------------------------------------------------------
 213  * disable a set of problems
 214  */
 215 void
 216 solver_disableproblemset(Solver *solv, int start)
 217 {
 218   int i;
 219   for (i = start + 1; i < solv->problems.count - 1; i++)
 220     solver_disableproblem(solv, solv->problems.elements[i]);
 221 }
 222
 223 /*-------------------------------------------------------------------
 224  * try to fix a problem by auto-uninstalling packages
 225  */
 226 Id
 227 solver_autouninstall(Solver *solv, int start)
 228 {
 229   Pool *pool = solv->pool;
 230   int i;
 231   int lastfeature = 0, lastupdate = 0;
 232   Id v;
 233   Id extraflags = -1;
 234   Map *m = 0;
 235
 236   if (!solv->allowuninstall && !solv->allowuninstall_all)
 237     {
 238       if (!solv->allowuninstallmap.size)
 239         return 0;               /* why did we get called? */
 240       m = &solv->allowuninstallmap;
 241     }
 242   for (i = start + 1; i < solv->problems.count - 1; i++)
 243     {
 244       v = solv->problems.elements[i];
 245       if (v < 0)
 246         extraflags &= solv->job.elements[-v - 1];
 247       if (v >= solv->updaterules && v < solv->updaterules_end)
 248         {
 249           Rule *r;
 250           Id p = solv->installed->start + (v - solv->updaterules);
 251           if (m && !MAPTST(m, v - solv->updaterules))
 252             continue;
 253           if (pool->considered && !MAPTST(pool->considered, p))
 254             continue;   /* do not uninstalled disabled packages */
 255           if (solv->bestrules_info && solv->bestrules_end > solv->bestrules)
 256             {
 257               int j;
 258               for (j = start + 1; j < solv->problems.count - 1; j++)
 259                 {
 260                   Id vv = solv->problems.elements[j];
 261                   if (vv >= solv->bestrules && vv < solv->bestrules_end && solv->bestrules_info[vv - solv->bestrules] == p)
 262                     break;
 263                 }
 264               if (j < solv->problems.count - 1)
 265                 continue;       /* best rule involved, do not uninstall */
 266             }
 267           /* check if identical to feature rule, we don't like that (except for orphans) */
 268           r = solv->rules + solv->featurerules + (v - solv->updaterules);
 269           if (!r->p)
 270             {
 271               /* update rule == feature rule */
 272               if (v > lastfeature)
 273                 lastfeature = v;
 274               /* prefer orphaned packages in dup mode */
 275               if (solv->keep_orphans)
 276                 {
 277                   r = solv->rules + v;
 278                   if (!r->d && !r->w2 && r->p == p)
 279                     {
 280                       lastfeature = v;
 281                       lastupdate = 0;
 282                       break;
 283                     }
 284                 }
 285               continue;
 286             }
 287           if (v > lastupdate)
 288             lastupdate = v;
 289         }
 290     }
 291   if (!lastupdate && !lastfeature)
 292     return 0;
 293   v = lastupdate ? lastupdate : lastfeature;
 294   POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "allowuninstall disabling ");
 295   solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE, solv->rules + v);
 296   /* should really be solver_fixproblem, but we know v is an update/feature rule */
 297   solver_disableproblem(solv, v);
 298   if (extraflags != -1 && (extraflags & SOLVER_CLEANDEPS) != 0 && solv->cleandepsmap.size)
 299     {
 300       /* add the package to the updatepkgs list, this will automatically turn
 301        * on cleandeps mode */
 302       Id p = solv->rules[v].p;
 303       if (!solv->cleandeps_updatepkgs)
 304         {
 305           solv->cleandeps_updatepkgs = solv_calloc(1, sizeof(Queue));
 306           queue_init(solv->cleandeps_updatepkgs);
 307         }
 308       if (p > 0)
 309         {
 310           int oldupdatepkgscnt = solv->cleandeps_updatepkgs->count;
 311           queue_pushunique(solv->cleandeps_updatepkgs, p);
 312           if (solv->cleandeps_updatepkgs->count != oldupdatepkgscnt)
 313             solver_disablepolicyrules(solv);
 314         }
 315     }
 316   return v;
 317 }
 318
 319
 320 /*-------------------------------------------------------------------
 321  * enable weak rules
 322  *
 323  * Reenable all disabled weak rules (marked in weakrulemap)
 324  *
 325  */
 326
 327 static void
 328 enableweakrules(Solver *solv)
 329 {
 330   int i;
 331   Rule *r;
 332
 333   if (!solv->weakrulemap.size)
 334     return;
 335   for (i = 1, r = solv->rules + i; i < solv->learntrules; i++, r++)
 336     {
 337       if (r->d >= 0) /* already enabled? */
 338         continue;
 339       if (!MAPTST(&solv->weakrulemap, i))
 340         continue;
 341       solver_enablerule(solv, r);
 342     }
 343   /* make sure broken orphan rules stay disabled */
 344   if (solv->brokenorphanrules)
 345     for (i = 0; i < solv->brokenorphanrules->count; i++)
 346       solver_disablerule(solv, solv->rules + solv->brokenorphanrules->elements[i]);
 347 }
 348
 349
 350 /*-------------------------------------------------------------------
 351  *
 352  * refine_suggestion
 353  *
 354  * at this point, all rules that led to conflicts are disabled.
 355  * we re-enable all rules of a problem set but rule "sug", then
 356  * continue to disable more rules until there as again a solution.
 357  */
 358
 359 /* FIXME: think about conflicting assertions */
 360
 361 static void
 362 refine_suggestion(Solver *solv, Id *problem, Id sug, Queue *refined, int essentialok)
 363 {
 364   Pool *pool = solv->pool;
 365   int i, j;
 366   Id v;
 367   Queue disabled;
 368   int disabledcnt;
 369
 370   IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS)
 371     {
 372       POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "refine_suggestion start\n");
 373       for (i = 0; problem[i]; i++)
 374         {
 375           if (problem[i] == sug)
 376             POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "=> ");
 377           solver_printproblem(solv, problem[i]);
 378         }
 379     }
 380   queue_empty(refined);
 381   if (!essentialok && sug < 0 && (solv->job.elements[-sug - 1] & SOLVER_ESSENTIAL) != 0)
 382     return;
 383   queue_push(refined, sug);
 384
 385   /* re-enable all problem rules with the exception of "sug"(gestion) */
 386   solver_reset(solv);
 387
 388   for (i = 0; problem[i]; i++)
 389     if (problem[i] != sug)
 390       solver_enableproblem(solv, problem[i]);
 391   if (sug < 0)
 392     solver_reenablepolicyrules(solv, -sug);
 393
 394   /* here is where the feature rules come into play: if we disabled an
 395    * update rule, we enable the corresponding feature rule if there is
 396    * one. We do this to make the solver downgrade packages instead of
 397    * deinstalling them */
 398   if (sug >= solv->updaterules && sug < solv->updaterules_end)
 399     {
 400       /* enable feature rule */
 401       Rule *r = solv->rules + solv->featurerules + (sug - solv->updaterules);
 402       if (r->p)
 403         solver_enablerule(solv, r);
 404     }
 405
 406   enableweakrules(solv);
 407
 408   /* disabled contains all of the rules we disabled in the refinement process */
 409   queue_init(&disabled);
 410   for (;;)
 411     {
 412       int nother, nfeature, nupdate, pass;
 413       queue_empty(&solv->problems);
 414       solver_reset(solv);
 415       /* we set disablerules to zero because we are only interested in
 416        * the first problem and we don't want the solver to disable the problems */
 417       solver_run_sat(solv, 0, 0);
 418
 419       if (!solv->problems.count)
 420         {
 421           POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "no more problems!\n");
 422           break;                /* great, no more problems */
 423         }
 424       disabledcnt = disabled.count;
 425       nother = nfeature = nupdate = 0;
 426       for (pass = 0; pass < 2; pass++)
 427         {
 428           /* start with 1 to skip over proof index */
 429           for (i = 1; i < solv->problems.count - 1; i++)
 430             {
 431               /* ignore solutions in refined */
 432               v = solv->problems.elements[i];
 433               if (v == 0)
 434                 break;  /* end of problem reached */
 435               if (!essentialok && v < 0 && (solv->job.elements[-v - 1] & SOLVER_ESSENTIAL) != 0)
 436                 continue;       /* not that one! */
 437               if (sug != v)
 438                 {
 439                   /* check if v is in the given problems list
 440                    * we allow disabling all problem rules *after* sug in
 441                    * pass 2, to prevent getting the same solution twice */
 442                   for (j = 0; problem[j]; j++)
 443                     if (problem[j] == v || (pass && problem[j] == sug))
 444                       break;
 445                   if (problem[j] == v)
 446                     continue;
 447                 }
 448               if (v >= solv->featurerules && v < solv->featurerules_end)
 449                 nfeature++;
 450               else if (v > solv->updaterules && v < solv->updaterules_end)
 451                 nupdate++;
 452               else
 453                 nother++;
 454               queue_push(&disabled, v);
 455             }
 456           if (disabled.count != disabledcnt)
 457             break;
 458         }
 459       if (disabled.count == disabledcnt)
 460         {
 461           /* no solution found, this was an invalid suggestion! */
 462           POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "no solution found!\n");
 463           refined->count = 0;
 464           break;
 465         }
 466       if (!nother && nupdate && nfeature)
 467         {
 468           /* got only update rules, filter out feature rules */
 469           POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "throwing away feature rules\n");
 470           for (i = j = disabledcnt; i < disabled.count; i++)
 471             {
 472               v = disabled.elements[i];
 473               if (v < solv->featurerules || v >= solv->featurerules_end)
 474                 disabled.elements[j++] = v;
 475             }
 476           disabled.count = j;
 477           nfeature = 0;
 478         }
 479       if (disabled.count == disabledcnt + 1)
 480         {
 481           /* just one suggestion, add it to refined list */
 482           v = disabled.elements[disabledcnt];
 483           if (!nfeature && v != sug)
 484             queue_push(refined, v);     /* do not record feature rules */
 485           solver_disableproblem(solv, v);
 486           if (v < 0)
 487             solver_reenablepolicyrules(solv, -v);
 488           if (v >= solv->updaterules && v < solv->updaterules_end)
 489             {
 490               Rule *r = solv->rules + (v - solv->updaterules + solv->featurerules);
 491               if (r->p)
 492                 solver_enablerule(solv, r);     /* enable corresponding feature rule */
 493             }
 494         }
 495       else
 496         {
 497           /* more than one solution, disable all */
 498           /* do not push anything on refine list, as we do not know which solution to choose */
 499           /* thus, the user will get another problem if he selects this solution, where he
 500            * can choose the right one */
 501           IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS)
 502             {
 503               POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "more than one solution found:\n");
 504               for (i = disabledcnt; i < disabled.count; i++)
 505                 solver_printproblem(solv, disabled.elements[i]);
 506             }
 507           for (i = disabledcnt; i < disabled.count; i++)
 508             {
 509               v = disabled.elements[i];
 510               solver_disableproblem(solv, v);
 511               if (v >= solv->updaterules && v < solv->updaterules_end)
 512                 {
 513                   Rule *r = solv->rules + (v - solv->updaterules + solv->featurerules);
 514                   if (r->p)
 515                     solver_enablerule(solv, r);
 516                 }
 517             }
 518         }
 519     }
 520   /* all done, get us back into the same state as before */
 521   /* enable refined rules again */
 522   for (i = 0; i < disabled.count; i++)
 523     solver_enableproblem(solv, disabled.elements[i]);
 524   queue_free(&disabled);
 525
 526   /* reset policy rules */
 527   for (i = 0; problem[i]; i++)
 528     solver_enableproblem(solv, problem[i]);
 529   solver_disablepolicyrules(solv);
 530   /* disable problem rules again */
 531   for (i = 0; problem[i]; i++)
 532     solver_disableproblem(solv, problem[i]);
 533   POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "refine_suggestion end\n");
 534 }
 535
 536
 537 /*-------------------------------------------------------------------
 538  * sorting helper for problems
 539  *
 540  * bring update rules before job rules
 541  * make essential job rules last
 542  */
 543
 544 static int
 545 problems_sortcmp(const void *ap, const void *bp, void *dp)
 546 {
 547   Queue *job = dp;
 548   Id a = *(Id *)ap, b = *(Id *)bp;
 549   if (a < 0 && b > 0)
 550     return 1;
 551   if (a > 0 && b < 0)
 552     return -1;
 553   if (a < 0 && b < 0)
 554     {
 555       int af = job->elements[-a - 1] & SOLVER_ESSENTIAL;
 556       int bf = job->elements[-b - 1] & SOLVER_ESSENTIAL;
 557       int x = af - bf;
 558       if (x)
 559         return x;
 560     }
 561   return a - b;
 562 }
 563
 564 /*
 565  * convert a solution rule into a job modifier
 566  */
 567 static void
 568 convertsolution(Solver *solv, Id why, Queue *solutionq)
 569 {
 570   Pool *pool = solv->pool;
 571   if (why < 0)
 572     {
 573       why = -why;
 574       if (why < solv->pooljobcnt)
 575         {
 576           queue_push(solutionq, SOLVER_SOLUTION_POOLJOB);
 577           queue_push(solutionq, why);
 578         }
 579       else
 580         {
 581           queue_push(solutionq, SOLVER_SOLUTION_JOB);
 582           queue_push(solutionq, why - solv->pooljobcnt);
 583         }
 584       return;
 585     }
 586   if (why >= solv->infarchrules && why < solv->infarchrules_end)
 587     {
 588       Id p, name;
 589       /* infarch rule, find replacement */
 590       assert(solv->rules[why].p < 0);
 591       name = pool->solvables[-solv->rules[why].p].name;
 592       while (why > solv->infarchrules && pool->solvables[-solv->rules[why - 1].p].name == name)
 593         why--;
 594       p = 0;
 595       for (; why < solv->infarchrules_end && pool->solvables[-solv->rules[why].p].name == name; why++)
 596         if (solv->decisionmap[-solv->rules[why].p] > 0)
 597           {
 598             p = -solv->rules[why].p;
 599             break;
 600           }
 601       if (!p)
 602         return;         /* false alarm */
 603       queue_push(solutionq, SOLVER_SOLUTION_INFARCH);
 604       queue_push(solutionq, p);
 605       return;
 606     }
 607   if (why >= solv->duprules && why < solv->duprules_end)
 608     {
 609       Id p, name;
 610       /* dist upgrade rule, find replacement */
 611       assert(solv->rules[why].p < 0);
 612       name = pool->solvables[-solv->rules[why].p].name;
 613       while (why > solv->duprules && pool->solvables[-solv->rules[why - 1].p].name == name)
 614         why--;
 615       p = 0;
 616       for (; why < solv->duprules_end && pool->solvables[-solv->rules[why].p].name == name; why++)
 617         if (solv->decisionmap[-solv->rules[why].p] > 0)
 618           {
 619             p = -solv->rules[why].p;
 620             break;
 621           }
 622       if (!p)
 623         return;         /* false alarm */
 624       queue_push(solutionq, SOLVER_SOLUTION_DISTUPGRADE);
 625       queue_push(solutionq, p);
 626       return;
 627     }
 628   if (why >= solv->updaterules && why < solv->updaterules_end)
 629     {
 630       /* update rule, find replacement package */
 631       Id p, pp, rp = 0;
 632       Rule *rr;
 633
 634       /* check if this is a false positive, i.e. the update rule is fulfilled */
 635       rr = solv->rules + why;
 636       FOR_RULELITERALS(p, pp, rr)
 637         if (p > 0 && solv->decisionmap[p] > 0)
 638           return;       /* false alarm */
 639
 640       p = solv->installed->start + (why - solv->updaterules);
 641       if (solv->decisionmap[p] > 0)
 642         return;         /* false alarm, turned out we can keep the package */
 643       rr = solv->rules + solv->featurerules + (why - solv->updaterules);
 644       if (!rr->p)
 645         rr = solv->rules + why;
 646       if (rr->w2)
 647         {
 648           int mvrp = 0;         /* multi-version replacement */
 649           FOR_RULELITERALS(rp, pp, rr)
 650             {
 651               if (rp > 0 && solv->decisionmap[rp] > 0 && pool->solvables[rp].repo != solv->installed)
 652                 {
 653                   mvrp = rp;
 654                   if (!(solv->multiversion.size && MAPTST(&solv->multiversion, rp)))
 655                     break;
 656                 }
 657             }
 658           if (!rp && mvrp)
 659             {
 660               /* found only multi-version replacements */
 661               /* have to split solution into two parts */
 662               queue_push(solutionq, p);
 663               queue_push(solutionq, mvrp);
 664             }
 665         }
 666       queue_push(solutionq, p);
 667       queue_push(solutionq, rp);
 668       return;
 669     }
 670   if (why >= solv->bestrules && why < solv->bestrules_end)
 671     {
 672       int mvrp;
 673       Id p, pp, rp = 0;
 674       Rule *rr;
 675       /* check false positive */
 676       rr = solv->rules + why;
 677       FOR_RULELITERALS(p, pp, rr)
 678         if (p > 0 && solv->decisionmap[p] > 0)
 679           return;       /* false alarm */
 680       /* check update/feature rule */
 681       p = solv->bestrules_info[why - solv->bestrules];
 682       if (p < 0)
 683         {
 684           /* install job */
 685           queue_push(solutionq, 0);
 686           queue_push(solutionq, solv->ruletojob.elements[-p - solv->jobrules] + 1);
 687           return;
 688         }
 689       if (solv->decisionmap[p] > 0)
 690         {
 691           /* disable best rule by keeping the old package */
 692           queue_push(solutionq, SOLVER_SOLUTION_BEST);
 693           queue_push(solutionq, p);
 694           return;
 695         }
 696       rr = solv->rules + solv->featurerules + (p - solv->installed->start);
 697       if (!rr->p)
 698         rr = solv->rules + solv->updaterules + (p - solv->installed->start);
 699       mvrp = 0;         /* multi-version replacement */
 700       FOR_RULELITERALS(rp, pp, rr)
 701         if (rp > 0 && solv->decisionmap[rp] > 0 && pool->solvables[rp].repo != solv->installed)
 702           {
 703             mvrp = rp;
 704             if (!(solv->multiversion.size && MAPTST(&solv->multiversion, rp)))
 705               break;
 706           }
 707       if (!rp && mvrp)
 708         {
 709           queue_push(solutionq, SOLVER_SOLUTION_BEST);  /* split, see above */
 710           queue_push(solutionq, mvrp);
 711           queue_push(solutionq, p);
 712           queue_push(solutionq, 0);
 713           return;
 714         }
 715       if (rp)
 716         {
 717           queue_push(solutionq, SOLVER_SOLUTION_BEST);
 718           queue_push(solutionq, rp);
 719         }
 720       return;
 721     }
 722   if (why >= solv->blackrules && why < solv->blackrules_end)
 723     {
 724       queue_push(solutionq, SOLVER_SOLUTION_BLACK);
 725       assert(solv->rules[why].p < 0);
 726       queue_push(solutionq, -solv->rules[why].p);
 727     }
 728   if (why >= solv->strictrepopriorules && why < solv->strictrepopriorules_end)
 729     {
 730       queue_push(solutionq, SOLVER_SOLUTION_STRICTREPOPRIORITY);
 731       assert(solv->rules[why].p < 0);
 732       queue_push(solutionq, -solv->rules[why].p);
 733     }
 734 }
 735
 736 /*
 737  * convert problem data into a form usable for refining.
 738  * Returns the number of problems.
 739  */
 740 int
 741 solver_prepare_solutions(Solver *solv)
 742 {
 743   int i, j = 1, idx;
 744
 745   if (!solv->problems.count)
 746     return 0;
 747   queue_empty(&solv->solutions);
 748   queue_push(&solv->solutions, 0);      /* dummy so idx is always nonzero */
 749   idx = solv->solutions.count;
 750   queue_push(&solv->solutions, -1);     /* unrefined */
 751   /* proofidx stays in position, thus we start with 1 */
 752   for (i = 1; i < solv->problems.count; i++)
 753     {
 754       Id p = solv->problems.elements[i];
 755       queue_push(&solv->solutions, p);
 756       if (p)
 757         continue;
 758       /* end of problem reached */
 759       solv->problems.elements[j++] = idx;
 760       if (i + 1 >= solv->problems.count)
 761         break;
 762       /* start another problem */
 763       solv->problems.elements[j++] = solv->problems.elements[++i];  /* copy proofidx */
 764       idx = solv->solutions.count;
 765       queue_push(&solv->solutions, -1); /* unrefined */
 766     }
 767   solv->problems.count = j;
 768   return j / 2;
 769 }
 770
 771 /*
 772  * refine the simple solution rule list provided by
 773  * the solver into multiple lists of job modifiers.
 774  */
 775 static void
 776 create_solutions(Solver *solv, int probnr, int solidx)
 777 {
 778   Pool *pool = solv->pool;
 779   Queue redoq;
 780   Queue problem, solution, problems_save, branches_save, decisionq_reason_save;
 781   int i, j, nsol;
 782   int essentialok;
 783   unsigned int now;
 784   int oldmistakes = solv->cleandeps_mistakes ? solv->cleandeps_mistakes->count : 0;
 785   Id extraflags = -1;
 786
 787   now = solv_timems(0);
 788   queue_init(&redoq);
 789   /* save decisionq, decisionq_why, decisionmap, and decisioncnt */
 790   for (i = 0; i < solv->decisionq.count; i++)
 791     {
 792       Id p = solv->decisionq.elements[i];
 793       queue_push(&redoq, p);
 794       queue_push(&redoq, solv->decisionq_why.elements[i]);
 795       queue_push(&redoq, solv->decisionmap[p > 0 ? p : -p]);
 796     }
 797
 798   /* save problems queue */
 799   problems_save = solv->problems;
 800   memset(&solv->problems, 0, sizeof(solv->problems));
 801
 802   /* save branches queue */
 803   branches_save = solv->branches;
 804   memset(&solv->branches, 0, sizeof(solv->branches));
 805
 806   /* save decisionq_reason */
 807   decisionq_reason_save = solv->decisionq_reason;
 808   memset(&solv->decisionq_reason, 0, sizeof(solv->decisionq_reason));
 809
 810   /* extract problem from queue */
 811   queue_init(&problem);
 812   for (i = solidx + 1; i < solv->solutions.count; i++)
 813     {
 814       Id v = solv->solutions.elements[i];
 815       if (!v)
 816         break;
 817       queue_push(&problem, v);
 818       if (v < 0)
 819         extraflags &= solv->job.elements[-v - 1];
 820     }
 821   if (extraflags == -1)
 822     extraflags = 0;
 823   if (problem.count > 1)
 824     solv_sort(problem.elements, problem.count, sizeof(Id), problems_sortcmp, &solv->job);
 825   queue_push(&problem, 0);      /* mark end for refine_suggestion */
 826   problem.count--;
 827 #if 0
 828   for (i = 0; i < problem.count; i++)
 829     printf("PP %d %d\n", i, problem.elements[i]);
 830 #endif
 831
 832   /* refine each solution element */
 833   nsol = 0;
 834   essentialok = 0;
 835   queue_init(&solution);
 836   for (i = 0; i < problem.count; i++)
 837     {
 838       int solstart = solv->solutions.count;
 839       refine_suggestion(solv, problem.elements, problem.elements[i], &solution, essentialok);
 840       queue_push(&solv->solutions, 0);  /* reserve room for number of elements */
 841       for (j = 0; j < solution.count; j++)
 842         convertsolution(solv, solution.elements[j], &solv->solutions);
 843       if (solv->solutions.count == solstart + 1)
 844         {
 845           solv->solutions.count--;      /* this one did not work out */
 846           if (nsol || i + 1 < problem.count)
 847             continue;                   /* got one or still hope */
 848           if (!essentialok)
 849             {
 850               /* nothing found, start over */
 851               POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "nothing found, re-run with essentialok = 1\n");
 852               essentialok = 1;
 853               i = -1;
 854               continue;
 855             }
 856           /* this is bad, we found no solution */
 857           /* for now just offer a rule */
 858           POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "nothing found, already did essentialok, fake it\n");
 859           queue_push(&solv->solutions, 0);
 860           for (j = 0; j < problem.count; j++)
 861             {
 862               convertsolution(solv, problem.elements[j], &solv->solutions);
 863               if (solv->solutions.count > solstart + 1)
 864                 break;
 865             }
 866           if (solv->solutions.count == solstart + 1)
 867             {
 868               solv->solutions.count--;
 869               continue;         /* sorry */
 870             }
 871         }
 872       /* patch in number of solution elements */
 873       solv->solutions.elements[solstart] = (solv->solutions.count - (solstart + 1)) / 2;
 874       queue_push(&solv->solutions, 0);  /* add end marker */
 875       queue_push(&solv->solutions, 0);  /* add end marker */
 876       queue_push(&solv->solutions, problem.elements[i]);        /* just for bookkeeping */
 877       queue_push(&solv->solutions, extraflags & SOLVER_CLEANDEPS);      /* our extraflags */
 878       solv->solutions.elements[solidx + 1 + nsol++] = solstart;
 879     }
 880   solv->solutions.elements[solidx + 1 + nsol] = 0;      /* end marker */
 881   solv->solutions.elements[solidx] = nsol;
 882   queue_free(&problem);
 883   queue_free(&solution);
 884
 885   /* restore decisions */
 886   memset(solv->decisionmap, 0, pool->nsolvables * sizeof(Id));
 887   queue_empty(&solv->decisionq);
 888   queue_empty(&solv->decisionq_why);
 889   for (i = 0; i < redoq.count; i += 3)
 890     {
 891       Id p = redoq.elements[i];
 892       queue_push(&solv->decisionq, p);
 893       queue_push(&solv->decisionq_why, redoq.elements[i + 1]);
 894       solv->decisionmap[p > 0 ? p : -p] = redoq.elements[i + 2];
 895     }
 896   queue_free(&redoq);
 897
 898   /* restore decision reasons */
 899   queue_free(&solv->decisionq_reason);
 900   solv->decisionq_reason = decisionq_reason_save;
 901
 902   /* restore problems */
 903   queue_free(&solv->problems);
 904   solv->problems = problems_save;
 905
 906   /* restore branches */
 907   queue_free(&solv->branches);
 908   solv->branches = branches_save;
 909
 910   if (solv->cleandeps_mistakes)
 911     {
 912       if (oldmistakes)
 913         queue_truncate(solv->cleandeps_mistakes, oldmistakes);
 914       else
 915         {
 916           queue_free(solv->cleandeps_mistakes);
 917           solv->cleandeps_mistakes = solv_free(solv->cleandeps_mistakes);
 918         }
 919     }
 920
 921   POOL_DEBUG(SOLV_DEBUG_STATS, "create_solutions for problem #%d took %d ms\n", probnr, solv_timems(now));
 922 }
 923
 924
 925 /**************************************************************************/
 926
 927 unsigned int
 928 solver_problem_count(Solver *solv)
 929 {
 930   return solv->problems.count / 2;
 931 }
 932
 933 Id
 934 solver_next_problem(Solver *solv, Id problem)
 935 {
 936   if (!problem)
 937     return solv->problems.count ? 1 : 0;
 938   return (problem + 1) * 2 - 1 < solv->problems.count ? problem + 1 : 0;
 939 }
 940
 941 unsigned int
 942 solver_solution_count(Solver *solv, Id problem)
 943 {
 944   Id solidx = solv->problems.elements[problem * 2 - 1];
 945   if (solv->solutions.elements[solidx] < 0)
 946     create_solutions(solv, problem, solidx);
 947   return solv->solutions.elements[solidx];
 948 }
 949
 950 Id
 951 solver_next_solution(Solver *solv, Id problem, Id solution)
 952 {
 953   Id solidx = solv->problems.elements[problem * 2 - 1];
 954   if (solv->solutions.elements[solidx] < 0)
 955     create_solutions(solv, problem, solidx);
 956   return solv->solutions.elements[solidx + solution + 1] ? solution + 1 : 0;
 957 }
 958
 959 unsigned int
 960 solver_solutionelement_count(Solver *solv, Id problem, Id solution)
 961 {
 962   Id solidx = solv->problems.elements[problem * 2 - 1];
 963   solidx = solv->solutions.elements[solidx + solution];
 964   return solv->solutions.elements[solidx];
 965 }
 966
 967 Id
 968 solver_solutionelement_internalid(Solver *solv, Id problem, Id solution)
 969 {
 970   Id solidx = solv->problems.elements[problem * 2 - 1];
 971   solidx = solv->solutions.elements[solidx + solution];
 972   return solv->solutions.elements[solidx + 2 * solv->solutions.elements[solidx] + 3];
 973 }
 974
 975 Id
 976 solver_solutionelement_extrajobflags(Solver *solv, Id problem, Id solution)
 977 {
 978   Id solidx = solv->problems.elements[problem * 2 - 1];
 979   solidx = solv->solutions.elements[solidx + solution];
 980   return solv->solutions.elements[solidx + 2 * solv->solutions.elements[solidx] + 4];
 981 }
 982
 983
 984 /*
 985  *  return the next item of the proposed solution
 986  *  here are the possibilities for p / rp and what
 987  *  the solver expects the application to do:
 988  *    p                             rp
 989  *  -------------------------------------------------------
 990  *    SOLVER_SOLUTION_INFARCH       pkgid
 991  *    -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job
 992  *    SOLVER_SOLUTION_DISTUPGRADE   pkgid
 993  *    -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job
 994  *    SOLVER_SOLUTION_BEST          pkgid
 995  *    -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job
 996  *    SOLVER_SOLUTION_BLACK         pkgid
 997  *    -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job
 998  *    SOLVER_SOLUTION_JOB           jobidx
 999  *    -> remove job (jobidx - 1, jobidx) from job queue
1000  *    SOLVER_SOLUTION_POOLJOB       jobidx
1001  *    -> remove job (jobidx - 1, jobidx) from pool job queue
1002  *    pkgid (> 0)                   0
1003  *    -> add (SOLVER_ERASE|SOLVER_SOLVABLE, p) to the job
1004  *    pkgid (> 0)                   pkgid (> 0)
1005  *    -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job
1006  *       (this will replace package p)
1007  *
1008  * Thus, the solver will either ask the application to remove
1009  * a specific job from the job queue, or ask to add an install/erase
1010  * job to it.
1011  *
1012  */
1013
1014 Id
1015 solver_next_solutionelement(Solver *solv, Id problem, Id solution, Id element, Id *p, Id *rp)
1016 {
1017   Id solidx = solv->problems.elements[problem * 2 - 1];
1018   solidx = solv->solutions.elements[solidx + solution];
1019   if (!solidx)
1020     return 0;
1021   solidx += 1 + element * 2;
1022   if (!solv->solutions.elements[solidx] && !solv->solutions.elements[solidx + 1])
1023     return 0;
1024   *p = solv->solutions.elements[solidx];
1025   *rp = solv->solutions.elements[solidx + 1];
1026   return element + 1;
1027 }
1028
1029 void
1030 solver_take_solutionelement(Solver *solv, Id p, Id rp, Id extrajobflags, Queue *job)
1031 {
1032   int i;
1033
1034   if (p == SOLVER_SOLUTION_POOLJOB)
1035     {
1036       solv->pool->pooljobs.elements[rp - 1] = SOLVER_NOOP;
1037       solv->pool->pooljobs.elements[rp] = 0;
1038       return;
1039     }
1040   if (p == SOLVER_SOLUTION_JOB)
1041     {
1042       job->elements[rp - 1] = SOLVER_NOOP;
1043       job->elements[rp] = 0;
1044       return;
1045     }
1046   if (rp <= 0 && p <= 0)
1047     return;     /* just in case */
1048   if (rp > 0)
1049     p = SOLVER_INSTALL|SOLVER_SOLVABLE|SOLVER_NOTBYUSER|extrajobflags;
1050   else
1051     {
1052       rp = p;
1053       p = SOLVER_ERASE|SOLVER_SOLVABLE|extrajobflags;
1054     }
1055   for (i = 0; i < job->count; i += 2)
1056     if (job->elements[i] == p && job->elements[i + 1] == rp)
1057       return;
1058   queue_push2(job, p, rp);
1059 }
1060
1061 void
1062 solver_take_solution(Solver *solv, Id problem, Id solution, Queue *job)
1063 {
1064   Id p, rp, element = 0;
1065   Id extrajobflags = solver_solutionelement_extrajobflags(solv, problem, solution);
1066   while ((element = solver_next_solutionelement(solv, problem, solution, element, &p, &rp)) != 0)
1067     solver_take_solutionelement(solv, p, rp, extrajobflags, job);
1068 }
1069
1070
1071 /*-------------------------------------------------------------------
1072  *
1073  * find problem rule
1074  */
1075
1076 static void
1077 findproblemrule_internal(Solver *solv, Id idx, Id *reqrp, Id *conrp, Id *sysrp, Id *jobrp, Id *blkrp, Id *scprp, Map *rseen)
1078 {
1079   Id rid, d;
1080   Id lreqr, lconr, lsysr, ljobr, lblkr, lscpr;
1081   Rule *r;
1082   Id jobassert = 0;
1083   int i, reqset = 0;    /* 0: unset, 1: installed, 2: jobassert, 3: assert */
1084   int conset = 0;       /* 0: unset, 1: installed */
1085
1086   /* find us a jobassert rule */
1087   for (i = idx; (rid = solv->learnt_pool.elements[i]) != 0; i++)
1088     {
1089       if (rid < solv->jobrules || rid >= solv->jobrules_end)
1090         continue;
1091       r = solv->rules + rid;
1092       d = r->d < 0 ? -r->d - 1 : r->d;
1093       if (!d && r->w2 == 0 && r->p > 0)
1094         {
1095           jobassert = r->p;
1096           break;
1097         }
1098     }
1099
1100   /* the problem rules are somewhat ordered from "near to the problem" to
1101    * "near to the job" */
1102   lreqr = lconr = lsysr = ljobr = lblkr = lscpr = 0;
1103   while ((rid = solv->learnt_pool.elements[idx++]) != 0)
1104     {
1105       assert(rid > 0);
1106       if (rid >= solv->learntrules)
1107         {
1108           if (MAPTST(rseen, rid - solv->learntrules))
1109             continue;
1110           MAPSET(rseen, rid - solv->learntrules);
1111           findproblemrule_internal(solv, solv->learnt_why.elements[rid - solv->learntrules], &lreqr, &lconr, &lsysr, &ljobr, &lblkr, &lscpr, rseen);
1112         }
1113       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) || (rid >= solv->yumobsrules && rid < solv->yumobsrules_end))
1114         {
1115           if (!*jobrp)
1116             *jobrp = rid;
1117         }
1118       else if (rid >= solv->updaterules && rid < solv->updaterules_end)
1119         {
1120           if (!*sysrp)
1121             *sysrp = rid;
1122         }
1123       else if (rid >= solv->blackrules && rid < solv->blackrules_end)
1124         {
1125           if (!*blkrp)
1126             *blkrp = rid;
1127         }
1128       else if (rid >= solv->strictrepopriorules && rid < solv->strictrepopriorules_end)
1129         {
1130           if (!*scprp)
1131             *scprp = rid;
1132         }
1133       else
1134         {
1135           assert(rid < solv->pkgrules_end);
1136           r = solv->rules + rid;
1137           d = r->d < 0 ? -r->d - 1 : r->d;
1138           if (!d && r->w2 < 0)
1139             {
1140               /* prefer conflicts of installed packages */
1141               if (solv->installed && !conset)
1142                 {
1143                   if (r->p < 0 && (solv->pool->solvables[-r->p].repo == solv->installed ||
1144                                   solv->pool->solvables[-r->w2].repo == solv->installed))
1145                     {
1146                       *conrp = rid;
1147                       conset = 1;
1148                     }
1149                 }
1150               if (!*conrp)
1151                 *conrp = rid;
1152             }
1153           else
1154             {
1155               if (!d && r->w2 == 0 && reqset < 3)
1156                 {
1157                   if (*reqrp > 0 && r->p < -1)
1158                     {
1159                       Pool *pool = solv->pool;
1160                       Id op = -solv->rules[*reqrp].p;
1161                       if (op > 1 && pool->solvables[op].arch != pool->solvables[-r->p].arch &&
1162                           pool->solvables[-r->p].arch != pool->noarchid)
1163                         continue;       /* different arch, skip */
1164                     }
1165                   /* prefer assertions */
1166                   *reqrp = rid;
1167                   reqset = 3;
1168                 }
1169               else if (jobassert && r->p == -jobassert)
1170                 {
1171                   /* prefer rules of job assertions */
1172                   *reqrp = rid;
1173                   reqset = 2;
1174                 }
1175               else if (solv->installed && r->p < 0 && solv->pool->solvables[-r->p].repo == solv->installed && reqset <= 1)
1176                 {
1177                   /* prefer rules of job installed package so that the user doesn't get confused by strange packages */
1178                   *reqrp = rid;
1179                   reqset = 1;
1180                 }
1181               else if (!*reqrp)
1182                 *reqrp = rid;
1183             }
1184         }
1185     }
1186   if (!*reqrp && lreqr)
1187     *reqrp = lreqr;
1188   if (!*conrp && lconr)
1189     *conrp = lconr;
1190   if (!*jobrp && ljobr)
1191     *jobrp = ljobr;
1192   if (!*sysrp && lsysr)
1193     *sysrp = lsysr;
1194   if (!*blkrp && lblkr)
1195     *blkrp = lblkr;
1196   if (!*scprp && lscpr)
1197     *scprp = lscpr;
1198 }
1199
1200 /*
1201  * find problem rule
1202  *
1203  * search for a rule that describes the problem to the
1204  * user. Actually a pretty hopeless task that may leave the user
1205  * puzzled. To get all of the needed information use
1206  * solver_findallproblemrules() instead.
1207  */
1208
1209 Id
1210 solver_findproblemrule(Solver *solv, Id problem)
1211 {
1212   Id reqr, conr, sysr, jobr, blkr, srpr;
1213   Id idx = solv->problems.elements[2 * problem - 2];
1214   Map rseen;
1215   reqr = conr = sysr = jobr = blkr = srpr = 0;
1216   map_init(&rseen, solv->learntrules ? solv->nrules - solv->learntrules : 0);
1217   findproblemrule_internal(solv, idx, &reqr, &conr, &sysr, &jobr, &blkr, &srpr, &rseen);
1218   map_free(&rseen);
1219   /* check if the request is about a not-installed package requiring a installed
1220    * package conflicting with the non-installed package. In that case return the conflict */
1221   if (reqr && conr && solv->installed && solv->rules[reqr].p < 0 && solv->rules[conr].p < 0 && solv->rules[conr].w2 < 0)
1222     {
1223       Pool *pool = solv->pool;
1224       Solvable *s  = pool->solvables - solv->rules[reqr].p;
1225       Solvable *s1 = pool->solvables - solv->rules[conr].p;
1226       Solvable *s2 = pool->solvables - solv->rules[conr].w2;
1227       Id cp = 0;
1228       if (s == s1 && s2->repo == solv->installed)
1229         cp = -solv->rules[conr].w2;
1230       else if (s == s2 && s1->repo == solv->installed)
1231         cp = -solv->rules[conr].p;
1232       if (cp && s1->name != s2->name && s->repo != solv->installed)
1233         {
1234           Id p, pp;
1235           Rule *r = solv->rules + reqr;
1236           FOR_RULELITERALS(p, pp, r)
1237             if (p == cp)
1238               return conr;
1239         }
1240     }
1241   if (reqr)
1242     return reqr;        /* some requires */
1243   if (conr)
1244     return conr;        /* some conflict */
1245   if (blkr)
1246     return blkr;        /* a blacklisted package */
1247   if (srpr)
1248     return srpr;        /* a strict repo priority */
1249   if (sysr)
1250     return sysr;        /* an update rule */
1251   if (jobr)
1252     return jobr;        /* a user request */
1253   assert(0);
1254   return 0;
1255 }
1256
1257 /*-------------------------------------------------------------------*/
1258
1259 static void
1260 findallproblemrules_internal(Solver *solv, Id idx, Queue *rules, Map *rseen)
1261 {
1262   Id rid;
1263   while ((rid = solv->learnt_pool.elements[idx++]) != 0)
1264     {
1265       if (rid >= solv->learntrules)
1266         {
1267           if (MAPTST(rseen, rid - solv->learntrules))
1268             continue;
1269           MAPSET(rseen, rid - solv->learntrules);
1270           findallproblemrules_internal(solv, solv->learnt_why.elements[rid - solv->learntrules], rules, rseen);
1271           continue;
1272         }
1273       queue_pushunique(rules, rid);
1274     }
1275 }
1276
1277 /*
1278  * find all problem rule
1279  *
1280  * return all rules that lead to the problem. This gives the user
1281  * all of the information to understand the problem, but the result
1282  * can be a large number of rules.
1283  */
1284
1285 void
1286 solver_findallproblemrules(Solver *solv, Id problem, Queue *rules)
1287 {
1288   Map rseen;
1289   queue_empty(rules);
1290   map_init(&rseen, solv->learntrules ? solv->nrules - solv->learntrules : 0);
1291   findallproblemrules_internal(solv, solv->problems.elements[2 * problem - 2], rules, &rseen);
1292   map_free(&rseen);
1293 }
1294
1295 const char *
1296 solver_problemruleinfo2str(Solver *solv, SolverRuleinfo type, Id source, Id target, Id dep)
1297 {
1298   Pool *pool = solv->pool;
1299   char *s;
1300   Solvable *ss;
1301   switch (type)
1302     {
1303     case SOLVER_RULE_DISTUPGRADE:
1304       return pool_tmpjoin(pool, pool_solvid2str(pool, source), " does not belong to a distupgrade repository", 0);
1305     case SOLVER_RULE_INFARCH:
1306       return pool_tmpjoin(pool, pool_solvid2str(pool, source), " has inferior architecture", 0);
1307     case SOLVER_RULE_UPDATE:
1308       return pool_tmpjoin(pool, "problem with installed package ", pool_solvid2str(pool, source), 0);
1309     case SOLVER_RULE_JOB:
1310       return "conflicting requests";
1311     case SOLVER_RULE_JOB_UNSUPPORTED:
1312       return "unsupported request";
1313     case SOLVER_RULE_JOB_NOTHING_PROVIDES_DEP:
1314       return pool_tmpjoin(pool, "nothing provides requested ", pool_dep2str(pool, dep), 0);
1315     case SOLVER_RULE_JOB_UNKNOWN_PACKAGE:
1316       return pool_tmpjoin(pool, "package ", pool_dep2str(pool, dep), " does not exist");
1317     case SOLVER_RULE_JOB_PROVIDED_BY_SYSTEM:
1318       return pool_tmpjoin(pool, pool_dep2str(pool, dep), " is provided by the system", 0);
1319     case SOLVER_RULE_PKG:
1320       return "some dependency problem";
1321     case SOLVER_RULE_BEST:
1322       if (source > 0)
1323         return pool_tmpjoin(pool, "cannot install the best update candidate for package ", pool_solvid2str(pool, source), 0);
1324      return "cannot install the best candidate for the job";
1325     case SOLVER_RULE_PKG_NOT_INSTALLABLE:
1326       ss = pool->solvables + source;
1327       if (pool_disabled_solvable(pool, ss))
1328         return pool_tmpjoin(pool, "package ", pool_solvid2str(pool, source), " is disabled");
1329       if (ss->arch && ss->arch != ARCH_SRC && ss->arch != ARCH_NOSRC &&
1330           pool->id2arch && pool_arch2score(pool, ss->arch) == 0)
1331         return pool_tmpjoin(pool, "package ", pool_solvid2str(pool, source), " does not have a compatible architecture");
1332       return pool_tmpjoin(pool, "package ", pool_solvid2str(pool, source), " is not installable");
1333     case SOLVER_RULE_PKG_NOTHING_PROVIDES_DEP:
1334       s = pool_tmpjoin(pool, "nothing provides ", pool_dep2str(pool, dep), 0);
1335       return pool_tmpappend(pool, s, " needed by ", pool_solvid2str(pool, source));
1336     case SOLVER_RULE_PKG_SAME_NAME:
1337       s = pool_tmpjoin(pool, "cannot install both ", pool_solvid2str(pool, source), 0);
1338       return pool_tmpappend(pool, s, " and ", pool_solvid2str(pool, target));
1339     case SOLVER_RULE_PKG_CONFLICTS:
1340       s = pool_tmpjoin(pool, "package ", pool_solvid2str(pool, source), 0);
1341       s = pool_tmpappend(pool, s, " conflicts with ", pool_dep2str(pool, dep));
1342       return pool_tmpappend(pool, s, " provided by ", pool_solvid2str(pool, target));
1343     case SOLVER_RULE_PKG_OBSOLETES:
1344       s = pool_tmpjoin(pool, "package ", pool_solvid2str(pool, source), 0);
1345       s = pool_tmpappend(pool, s, " obsoletes ", pool_dep2str(pool, dep));
1346       return pool_tmpappend(pool, s, " provided by ", pool_solvid2str(pool, target));
1347     case SOLVER_RULE_PKG_INSTALLED_OBSOLETES:
1348       s = pool_tmpjoin(pool, "installed package ", pool_solvid2str(pool, source), 0);
1349       s = pool_tmpappend(pool, s, " obsoletes ", pool_dep2str(pool, dep));
1350       return pool_tmpappend(pool, s, " provided by ", pool_solvid2str(pool, target));
1351     case SOLVER_RULE_PKG_IMPLICIT_OBSOLETES:
1352       s = pool_tmpjoin(pool, "package ", pool_solvid2str(pool, source), 0);
1353       s = pool_tmpappend(pool, s, " implicitly obsoletes ", pool_dep2str(pool, dep));
1354       return pool_tmpappend(pool, s, " provided by ", pool_solvid2str(pool, target));
1355     case SOLVER_RULE_PKG_REQUIRES:
1356       s = pool_tmpjoin(pool, "package ", pool_solvid2str(pool, source), " requires ");
1357       return pool_tmpappend(pool, s, pool_dep2str(pool, dep), ", but none of the providers can be installed");
1358     case SOLVER_RULE_PKG_SELF_CONFLICT:
1359       s = pool_tmpjoin(pool, "package ", pool_solvid2str(pool, source), " conflicts with ");
1360       return pool_tmpappend(pool, s, pool_dep2str(pool, dep), " provided by itself");
1361     case SOLVER_RULE_YUMOBS:
1362       s = pool_tmpjoin(pool, "both package ", pool_solvid2str(pool, source), " and ");
1363       s = pool_tmpjoin(pool, s, pool_solvid2str(pool, target), " obsolete ");
1364       return pool_tmpappend(pool, s, pool_dep2str(pool, dep), 0);
1365     case SOLVER_RULE_BLACK:
1366       return pool_tmpjoin(pool, "package ", pool_solvid2str(pool, source), " can only be installed by a direct request");
1367     case SOLVER_RULE_STRICT_REPO_PRIORITY:
1368       return pool_tmpjoin(pool, "package ", pool_solvid2str(pool, source), " is excluded by strict repo priority");
1369     case SOLVER_RULE_PKG_CONSTRAINS:
1370       s = pool_tmpjoin(pool, "package ", pool_solvid2str(pool, source), 0);
1371       s = pool_tmpappend(pool, s, " has constraint ", pool_dep2str(pool, dep));
1372       return pool_tmpappend(pool, s, " conflicting with ", pool_solvid2str(pool, target));
1373     default:
1374       return "bad problem rule type";
1375     }
1376 }
1377
1378 /* convenience function */
1379 const char *
1380 solver_problem2str(Solver *solv, Id problem)
1381 {
1382   Id type, source, target, dep;
1383   Id r = solver_findproblemrule(solv, problem);
1384   if (!r)
1385     return "no problem rule?";
1386   type = solver_ruleinfo(solv, r, &source, &target, &dep);
1387   return solver_problemruleinfo2str(solv, type, source, target, dep);
1388 }
1389
1390 const char *
1391 solver_solutionelement2str(Solver *solv, Id p, Id rp)
1392 {
1393   Pool *pool = solv->pool;
1394   if (p == SOLVER_SOLUTION_JOB || p == SOLVER_SOLUTION_POOLJOB)
1395     {
1396       Id how, what;
1397       if (p == SOLVER_SOLUTION_JOB)
1398         rp += solv->pooljobcnt;
1399       how = solv->job.elements[rp - 1];
1400       what = solv->job.elements[rp];
1401       return pool_tmpjoin(pool, "do not ask to ", pool_job2str(pool, how, what, 0), 0);
1402     }
1403   else if (p == SOLVER_SOLUTION_INFARCH)
1404     {
1405       Solvable *s = pool->solvables + rp;
1406       if (solv->installed && s->repo == solv->installed)
1407         return pool_tmpjoin(pool, "keep ", pool_solvable2str(pool, s), " despite the inferior architecture");
1408       else
1409         return pool_tmpjoin(pool, "install ", pool_solvable2str(pool, s), " despite the inferior architecture");
1410     }
1411   else if (p == SOLVER_SOLUTION_DISTUPGRADE)
1412     {
1413       Solvable *s = pool->solvables + rp;
1414       if (solv->installed && s->repo == solv->installed)
1415         return pool_tmpjoin(pool, "keep obsolete ", pool_solvable2str(pool, s), 0);
1416       else
1417         return pool_tmpjoin(pool, "install ", pool_solvable2str(pool, s), " from excluded repository");
1418     }
1419   else if (p == SOLVER_SOLUTION_BEST)
1420     {
1421       Solvable *s = pool->solvables + rp;
1422       if (solv->installed && s->repo == solv->installed)
1423         return pool_tmpjoin(pool, "keep old ", pool_solvable2str(pool, s), 0);
1424       else
1425         return pool_tmpjoin(pool, "install ", pool_solvable2str(pool, s), " despite the old version");
1426     }
1427   else if (p == SOLVER_SOLUTION_BLACK)
1428     {
1429       Solvable *s = pool->solvables + rp;
1430       return pool_tmpjoin(pool, "install ", pool_solvable2str(pool, s), 0);
1431     }
1432   else if (p > 0 && rp == 0)
1433     return pool_tmpjoin(pool, "allow deinstallation of ", pool_solvid2str(pool, p), 0);
1434   else if (p == SOLVER_SOLUTION_STRICTREPOPRIORITY)
1435     {
1436       Solvable *s = pool->solvables + rp;
1437       return pool_tmpjoin(pool, "install ", pool_solvable2str(pool, s), " despite the repo priority");
1438     }
1439   else if (p > 0 && rp > 0)
1440     {
1441       const char *sp = pool_solvid2str(pool, p);
1442       const char *srp = pool_solvid2str(pool, rp);
1443       const char *str = pool_tmpjoin(pool, "allow replacement of ", sp, 0);
1444       return pool_tmpappend(pool, str, " with ", srp);
1445     }
1446   else
1447     return "bad solution element";
1448 }
1449