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