src/solver.c

   1 /*
   2  * Copyright (c) 2007-2008, Novell Inc.
   3  *
   4  * This program is licensed under the BSD license, read LICENSE.BSD
   5  * for further information
   6  */
   7
   8 /*
   9  * solver.c
  10  *
  11  * SAT based dependency solver
  12  */
  13
  14 #include <stdio.h>
  15 #include <stdlib.h>
  16 #include <unistd.h>
  17 #include <string.h>
  18 #include <assert.h>
  19
  20 #include "solver.h"
  21 #include "solver_private.h"
  22 #include "bitmap.h"
  23 #include "pool.h"
  24 #include "util.h"
  25 #include "policy.h"
  26 #include "poolarch.h"
  27 #include "solverdebug.h"
  28 #include "cplxdeps.h"
  29 #include "linkedpkg.h"
  30
  31 #define RULES_BLOCK 63
  32
  33
  34 static Id
  35 autouninstall(Solver *solv, Id *problem)
  36 {
  37   Pool *pool = solv->pool;
  38   int i;
  39   int lastfeature = 0, lastupdate = 0;
  40   Id v;
  41   Id extraflags = -1;
  42   Map *m = 0;
  43
  44   if (!solv->allowuninstall && !solv->allowuninstall_all)
  45     {
  46       if (!solv->allowuninstallmap.size)
  47         return 0;               /* why did we get called? */
  48       m = &solv->allowuninstallmap;
  49     }
  50   for (i = 0; (v = problem[i]) != 0; i++)
  51     {
  52       if (v < 0)
  53         extraflags &= solv->job.elements[-v - 1];
  54       if (v >= solv->updaterules && v < solv->updaterules_end)
  55         {
  56           Rule *r;
  57           if (m && !MAPTST(m, v - solv->updaterules))
  58             continue;
  59           /* check if identical to feature rule, we don't like that (except for orphans) */
  60           r = solv->rules + solv->featurerules + (v - solv->updaterules);
  61           if (!r->p)
  62             {
  63               /* update rule == feature rule */
  64               if (v > lastfeature)
  65                 lastfeature = v;
  66               /* prefer orphaned packages in dup mode */
  67               if (solv->keep_orphans)
  68                 {
  69                   r = solv->rules + v;
  70                   if (!r->d && !r->w2 && r->p == (solv->installed->start + (v - solv->updaterules)))
  71                     {
  72                       lastfeature = v;
  73                       lastupdate = 0;
  74                       break;
  75                     }
  76                 }
  77               continue;
  78             }
  79           if (v > lastupdate)
  80             lastupdate = v;
  81         }
  82     }
  83   if (!lastupdate && !lastfeature)
  84     return 0;
  85   v = lastupdate ? lastupdate : lastfeature;
  86   POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "allowuninstall disabling ");
  87   solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE, solv->rules + v);
  88   solver_disableproblem(solv, v);
  89   if (extraflags != -1 && (extraflags & SOLVER_CLEANDEPS) != 0 && solv->cleandepsmap.size)
  90     {
  91       /* add the package to the updatepkgs list, this will automatically turn
  92        * on cleandeps mode */
  93       Id p = solv->rules[v].p;
  94       if (!solv->cleandeps_updatepkgs)
  95         {
  96           solv->cleandeps_updatepkgs = solv_calloc(1, sizeof(Queue));
  97           queue_init(solv->cleandeps_updatepkgs);
  98         }
  99       if (p > 0)
 100         {
 101           int oldupdatepkgscnt = solv->cleandeps_updatepkgs->count;
 102           queue_pushunique(solv->cleandeps_updatepkgs, p);
 103           if (solv->cleandeps_updatepkgs->count != oldupdatepkgscnt)
 104             solver_disablepolicyrules(solv);
 105         }
 106     }
 107   return v;
 108 }
 109
 110 /************************************************************************/
 111
 112 /*
 113  * enable/disable learnt rules
 114  *
 115  * we have enabled or disabled some of our rules. We now reenable all
 116  * of our learnt rules except the ones that were learnt from rules that
 117  * are now disabled.
 118  */
 119 static void
 120 enabledisablelearntrules(Solver *solv)
 121 {
 122   Pool *pool = solv->pool;
 123   Rule *r;
 124   Id why, *whyp;
 125   int i;
 126
 127   POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "enabledisablelearntrules called\n");
 128   for (i = solv->learntrules, r = solv->rules + i; i < solv->nrules; i++, r++)
 129     {
 130       whyp = solv->learnt_pool.elements + solv->learnt_why.elements[i - solv->learntrules];
 131       while ((why = *whyp++) != 0)
 132         {
 133           assert(why > 0 && why < i);
 134           if (solv->rules[why].d < 0)
 135             break;
 136         }
 137       /* why != 0: we found a disabled rule, disable the learnt rule */
 138       if (why && r->d >= 0)
 139         {
 140           IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS)
 141             {
 142               POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "disabling ");
 143               solver_printruleclass(solv, SOLV_DEBUG_SOLUTIONS, r);
 144             }
 145           solver_disablerule(solv, r);
 146         }
 147       else if (!why && r->d < 0)
 148         {
 149           IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS)
 150             {
 151               POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "re-enabling ");
 152               solver_printruleclass(solv, SOLV_DEBUG_SOLUTIONS, r);
 153             }
 154           solver_enablerule(solv, r);
 155         }
 156     }
 157 }
 158
 159
 160 /*
 161  * make assertion rules into decisions
 162  *
 163  * Go through rules and add direct assertions to the decisionqueue.
 164  * If we find a conflict, disable rules and add them to problem queue.
 165  */
 166
 167 static void
 168 makeruledecisions(Solver *solv)
 169 {
 170   Pool *pool = solv->pool;
 171   int i, ri, ii;
 172   Rule *r, *rr;
 173   Id v, vv;
 174   int decisionstart;
 175   int record_proof = 1;
 176   int oldproblemcount;
 177   int havedisabled = 0;
 178
 179   /* The system solvable is always installed first */
 180   assert(solv->decisionq.count == 0);
 181   queue_push(&solv->decisionq, SYSTEMSOLVABLE);
 182   queue_push(&solv->decisionq_why, 0);
 183   queue_push2(&solv->decisionq_reason, 0, 0);
 184   solv->decisionmap[SYSTEMSOLVABLE] = 1;        /* installed at level '1' */
 185
 186   decisionstart = solv->decisionq.count;
 187   for (;;)
 188     {
 189       /* if we needed to re-run, back up decisions to decisionstart */
 190       while (solv->decisionq.count > decisionstart)
 191         {
 192           v = solv->decisionq.elements[--solv->decisionq.count];
 193           --solv->decisionq_why.count;
 194           vv = v > 0 ? v : -v;
 195           solv->decisionmap[vv] = 0;
 196         }
 197
 198       /* note that the ruleassertions queue is ordered */
 199       for (ii = 0; ii < solv->ruleassertions.count; ii++)
 200         {
 201           ri = solv->ruleassertions.elements[ii];
 202           r = solv->rules + ri;
 203
 204           if (havedisabled && ri >= solv->learntrules)
 205             {
 206               /* just started with learnt rule assertions. If we have disabled
 207                * some rules, adapt the learnt rule status */
 208               enabledisablelearntrules(solv);
 209               havedisabled = 0;
 210             }
 211
 212           if (r->d < 0 || !r->p || r->w2)       /* disabled, dummy or no assertion */
 213             continue;
 214
 215           /* do weak rules in phase 2 */
 216           if (ri < solv->learntrules && solv->weakrulemap.size && MAPTST(&solv->weakrulemap, ri))
 217             continue;
 218
 219           v = r->p;
 220           vv = v > 0 ? v : -v;
 221
 222           if (!solv->decisionmap[vv])          /* if not yet decided */
 223             {
 224               queue_push(&solv->decisionq, v);
 225               queue_push(&solv->decisionq_why, r - solv->rules);
 226               solv->decisionmap[vv] = v > 0 ? 1 : -1;
 227               IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
 228                 {
 229                   Solvable *s = solv->pool->solvables + vv;
 230                   if (v < 0)
 231                     POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "conflicting %s (assertion)\n", pool_solvable2str(solv->pool, s));
 232                   else
 233                     POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "installing  %s (assertion)\n", pool_solvable2str(solv->pool, s));
 234                 }
 235               continue;
 236             }
 237
 238           /* check against previous decision: is there a conflict? */
 239           if (v > 0 && solv->decisionmap[vv] > 0)    /* ok to install */
 240             continue;
 241           if (v < 0 && solv->decisionmap[vv] < 0)    /* ok to remove */
 242             continue;
 243
 244           /*
 245            * found a conflict!
 246            *
 247            * The rule (r) we're currently processing says something
 248            * different (v = r->p) than a previous decision (decisionmap[abs(v)])
 249            * on this literal
 250            */
 251
 252           if (ri >= solv->learntrules)
 253             {
 254               /* conflict with a learnt rule */
 255               /* can happen when packages cannot be installed for multiple reasons. */
 256               /* we disable the learnt rule in this case */
 257               /* (XXX: we should really call analyze_unsolvable_rule here!) */
 258               solver_disablerule(solv, r);
 259               continue;
 260             }
 261
 262           POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "ANALYZE UNSOLVABLE ASSERTION ----------------------\n");
 263           IF_POOLDEBUG (SOLV_DEBUG_UNSOLVABLE)
 264             solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE, solv->rules + ri);
 265
 266           /*
 267            * find the decision which is the "opposite" of the rule
 268            */
 269           for (i = 0; i < solv->decisionq.count; i++)
 270             if (solv->decisionq.elements[i] == -v)
 271               break;
 272           assert(i < solv->decisionq.count);         /* assert that we found it */
 273           oldproblemcount = solv->problems.count;
 274
 275           /*
 276            * conflict with system solvable ?
 277            */
 278           if (v == -SYSTEMSOLVABLE)
 279             {
 280               if (record_proof)
 281                 {
 282                   queue_push(&solv->problems, solv->learnt_pool.count);
 283                   queue_push(&solv->learnt_pool, ri);
 284                   queue_push(&solv->learnt_pool, 0);
 285                 }
 286               else
 287                 queue_push(&solv->problems, 0);
 288               POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "conflict with system solvable, disabling rule #%d\n", ri);
 289               if  (ri >= solv->jobrules && ri < solv->jobrules_end)
 290                 v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
 291               else
 292                 v = ri;
 293               queue_push(&solv->problems, v);
 294               queue_push(&solv->problems, 0);
 295               if (v >= solv->featurerules && v < solv->updaterules_end)
 296                 {
 297                   if (solv->allowuninstall || solv->allowuninstall_all || solv->allowuninstallmap.size)
 298                     if (autouninstall(solv, solv->problems.elements + oldproblemcount + 1) != 0)
 299                       {
 300                         solv->problems.count = oldproblemcount;
 301                         havedisabled = 1;
 302                         break;  /* start over */
 303                       }
 304                 }
 305               solver_disableproblem(solv, v);
 306               havedisabled = 1;
 307               break;    /* start over */
 308             }
 309
 310           assert(solv->decisionq_why.elements[i] > 0);
 311           IF_POOLDEBUG (SOLV_DEBUG_UNSOLVABLE)
 312             solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE, solv->rules + solv->decisionq_why.elements[i]);
 313
 314           /*
 315            * conflict with a pkg rule ?
 316            */
 317           if (solv->decisionq_why.elements[i] < solv->pkgrules_end)
 318             {
 319               if (record_proof)
 320                 {
 321                   queue_push(&solv->problems, solv->learnt_pool.count);
 322                   queue_push(&solv->learnt_pool, ri);
 323                   queue_push(&solv->learnt_pool, solv->decisionq_why.elements[i]);
 324                   queue_push(&solv->learnt_pool, 0);
 325                 }
 326               else
 327                 queue_push(&solv->problems, 0);
 328               assert(v > 0 || v == -SYSTEMSOLVABLE);
 329               POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "conflict with pkg rule, disabling rule #%d\n", ri);
 330               if (ri >= solv->jobrules && ri < solv->jobrules_end)
 331                 v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
 332               else
 333                 v = ri;
 334               queue_push(&solv->problems, v);
 335               queue_push(&solv->problems, 0);
 336               if (v >= solv->featurerules && v < solv->updaterules_end)
 337                 {
 338                   if (solv->allowuninstall || solv->allowuninstall_all || solv->allowuninstallmap.size)
 339                     if (autouninstall(solv, solv->problems.elements + oldproblemcount + 1) != 0)
 340                       {
 341                         solv->problems.count = oldproblemcount;
 342                         havedisabled = 1;
 343                         break;  /* start over */
 344                       }
 345                 }
 346               solver_disableproblem(solv, v);
 347               havedisabled = 1;
 348               break;    /* start over */
 349             }
 350
 351           /*
 352            * conflict with another job or update/feature rule
 353            */
 354
 355           /* record proof */
 356           if (record_proof)
 357             {
 358               queue_push(&solv->problems, solv->learnt_pool.count);
 359               queue_push(&solv->learnt_pool, ri);
 360               queue_push(&solv->learnt_pool, solv->decisionq_why.elements[i]);
 361               queue_push(&solv->learnt_pool, 0);
 362             }
 363           else
 364             queue_push(&solv->problems, 0);
 365
 366           POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "conflicting update/job assertions over literal %d\n", vv);
 367
 368           /*
 369            * push all of our rules (can only be feature or job rules)
 370            * asserting this literal on the problem stack
 371            */
 372           for (i = solv->featurerules, rr = solv->rules + i; i < solv->learntrules; i++, rr++)
 373             {
 374               if (rr->d < 0                          /* disabled */
 375                   || rr->w2)                         /*  or no assertion */
 376                 continue;
 377               if (rr->p != vv                        /* not affecting the literal */
 378                   && rr->p != -vv)
 379                 continue;
 380               if (solv->weakrulemap.size && MAPTST(&solv->weakrulemap, i))     /* weak: silently ignore */
 381                 continue;
 382
 383               POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, " - disabling rule #%d\n", i);
 384               solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE, solv->rules + i);
 385
 386               v = i;
 387               if (i >= solv->jobrules && i < solv->jobrules_end)
 388                 v = -(solv->ruletojob.elements[i - solv->jobrules] + 1);
 389               queue_push(&solv->problems, v);
 390             }
 391           queue_push(&solv->problems, 0);
 392
 393           if (solv->allowuninstall || solv->allowuninstall_all || solv->allowuninstallmap.size)
 394             if (autouninstall(solv, solv->problems.elements + oldproblemcount + 1) != 0)
 395               {
 396                 solv->problems.count = oldproblemcount;
 397                 havedisabled = 1;
 398                 break;  /* start over */
 399               }
 400
 401           for (i = oldproblemcount + 1; i < solv->problems.count - 1; i++)
 402             solver_disableproblem(solv, solv->problems.elements[i]);
 403           havedisabled = 1;
 404           break;        /* start over */
 405         }
 406       if (ii < solv->ruleassertions.count)
 407         continue;
 408
 409       /*
 410        * phase 2: now do the weak assertions
 411        */
 412       if (!solv->weakrulemap.size)
 413         break;                          /* no weak rules, no phase 2 */
 414       for (ii = 0; ii < solv->ruleassertions.count; ii++)
 415         {
 416           ri = solv->ruleassertions.elements[ii];
 417           r = solv->rules + ri;
 418           if (r->d < 0 || r->w2)                         /* disabled or no assertion */
 419             continue;
 420           if (ri >= solv->learntrules || !MAPTST(&solv->weakrulemap, ri))       /* skip non-weak */
 421             continue;
 422           v = r->p;
 423           vv = v > 0 ? v : -v;
 424
 425           if (!solv->decisionmap[vv])          /* if not yet decided */
 426             {
 427               queue_push(&solv->decisionq, v);
 428               queue_push(&solv->decisionq_why, r - solv->rules);
 429               solv->decisionmap[vv] = v > 0 ? 1 : -1;
 430               IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
 431                 {
 432                   Solvable *s = solv->pool->solvables + vv;
 433                   if (v < 0)
 434                     POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "conflicting %s (weak assertion)\n", pool_solvable2str(solv->pool, s));
 435                   else
 436                     POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "installing  %s (weak assertion)\n", pool_solvable2str(solv->pool, s));
 437                 }
 438               continue;
 439             }
 440           /* check against previous decision: is there a conflict? */
 441           if (v > 0 && solv->decisionmap[vv] > 0)
 442             continue;
 443           if (v < 0 && solv->decisionmap[vv] < 0)
 444             continue;
 445
 446           POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "assertion conflict, but I am weak, disabling ");
 447           solver_printrule(solv, SOLV_DEBUG_UNSOLVABLE, r);
 448
 449           if (ri >= solv->jobrules && ri < solv->jobrules_end)
 450             v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
 451           else
 452             v = ri;
 453           solver_disableproblem(solv, v);
 454           if (v < 0)
 455             solver_reenablepolicyrules(solv, -v);
 456           havedisabled = 1;
 457           break;        /* start over */
 458         }
 459       if (ii == solv->ruleassertions.count)
 460         break;  /* finished! */
 461     }
 462 }
 463
 464
 465 /********************************************************************/
 466 /* watches */
 467
 468
 469 /*-------------------------------------------------------------------
 470  * makewatches
 471  *
 472  * initial setup for all watches
 473  */
 474
 475 static void
 476 makewatches(Solver *solv)
 477 {
 478   Rule *r;
 479   int i;
 480   int nsolvables = solv->pool->nsolvables;
 481
 482   solv_free(solv->watches);
 483   /* lower half for removals, upper half for installs */
 484   solv->watches = solv_calloc(2 * nsolvables, sizeof(Id));
 485   for (i = 1, r = solv->rules + solv->nrules - 1; i < solv->nrules; i++, r--)
 486     {
 487       if (!r->w2)               /* assertions do not need watches */
 488         continue;
 489
 490       /* see addwatches_rule(solv, r) */
 491       r->n1 = solv->watches[nsolvables + r->w1];
 492       solv->watches[nsolvables + r->w1] = r - solv->rules;
 493
 494       r->n2 = solv->watches[nsolvables + r->w2];
 495       solv->watches[nsolvables + r->w2] = r - solv->rules;
 496     }
 497 }
 498
 499
 500 /*-------------------------------------------------------------------
 501  *
 502  * add watches (for a new learned rule)
 503  * sets up watches for a single rule
 504  *
 505  * see also makewatches() above.
 506  */
 507
 508 static inline void
 509 addwatches_rule(Solver *solv, Rule *r)
 510 {
 511   int nsolvables = solv->pool->nsolvables;
 512
 513   r->n1 = solv->watches[nsolvables + r->w1];
 514   solv->watches[nsolvables + r->w1] = r - solv->rules;
 515
 516   r->n2 = solv->watches[nsolvables + r->w2];
 517   solv->watches[nsolvables + r->w2] = r - solv->rules;
 518 }
 519
 520
 521 /********************************************************************/
 522 /*
 523  * rule propagation
 524  */
 525
 526
 527 /* shortcuts to check if a literal (positive or negative) assignment
 528  * evaluates to 'true' or 'false'
 529  */
 530 #define DECISIONMAP_TRUE(p) ((p) > 0 ? (decisionmap[p] > 0) : (decisionmap[-p] < 0))
 531 #define DECISIONMAP_FALSE(p) ((p) > 0 ? (decisionmap[p] < 0) : (decisionmap[-p] > 0))
 532 #define DECISIONMAP_UNDEF(p) (decisionmap[(p) > 0 ? (p) : -(p)] == 0)
 533
 534 /*-------------------------------------------------------------------
 535  *
 536  * propagate
 537  *
 538  * make decision and propagate to all rules
 539  *
 540  * Evaluate each term affected by the decision (linked through watches).
 541  * If we find unit rules we make new decisions based on them.
 542  *
 543  * return : 0 = everything is OK
 544  *          rule = conflict found in this rule
 545  */
 546
 547 static Rule *
 548 propagate(Solver *solv, int level)
 549 {
 550   Pool *pool = solv->pool;
 551   Id *rp, *next_rp;           /* rule pointer, next rule pointer in linked list */
 552   Rule *r;                    /* rule */
 553   Id p, pkg, other_watch;
 554   Id *dp;
 555   Id *decisionmap = solv->decisionmap;
 556   Id *watches = solv->watches + pool->nsolvables;   /* place ptr in middle */
 557
 558   POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "----- propagate -----\n");
 559
 560   /* foreach non-propagated decision */
 561   while (solv->propagate_index < solv->decisionq.count)
 562     {
 563       /*
 564        * 'pkg' was just decided
 565        * negate because our watches trigger if literal goes FALSE
 566        */
 567       pkg = -solv->decisionq.elements[solv->propagate_index++];
 568
 569       IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
 570         {
 571           POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "propagate for decision %d level %d\n", -pkg, level);
 572           solver_printruleelement(solv, SOLV_DEBUG_PROPAGATE, 0, -pkg);
 573         }
 574
 575       /* foreach rule where 'pkg' is now FALSE */
 576       for (rp = watches + pkg; *rp; rp = next_rp)
 577         {
 578           r = solv->rules + *rp;
 579           if (r->d < 0)
 580             {
 581               /* rule is disabled, goto next */
 582               if (pkg == r->w1)
 583                 next_rp = &r->n1;
 584               else
 585                 next_rp = &r->n2;
 586               continue;
 587             }
 588
 589           IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
 590             {
 591               POOL_DEBUG(SOLV_DEBUG_PROPAGATE,"  watch triggered ");
 592               solver_printrule(solv, SOLV_DEBUG_PROPAGATE, r);
 593             }
 594
 595           /*
 596            * 'pkg' was just decided (was set to FALSE), so this rule
 597            * may now be unit.
 598            */
 599           /* find the other watch */
 600           if (pkg == r->w1)
 601             {
 602               other_watch = r->w2;
 603               next_rp = &r->n1;
 604             }
 605           else
 606             {
 607               other_watch = r->w1;
 608               next_rp = &r->n2;
 609             }
 610
 611           /*
 612            * if the other watch is true we have nothing to do
 613            */
 614           if (DECISIONMAP_TRUE(other_watch))
 615             continue;
 616
 617           /*
 618            * The other literal is FALSE or UNDEF
 619            *
 620            */
 621
 622           if (r->d)
 623             {
 624               /* Not a binary clause, try to move our watch.
 625                *
 626                * Go over all literals and find one that is
 627                *   not other_watch
 628                *   and not FALSE
 629                *
 630                * (TRUE is also ok, in that case the rule is fulfilled)
 631                * As speed matters here we do not use the FOR_RULELITERALS
 632                * macro.
 633                */
 634               if (r->p                                /* we have a 'p' */
 635                   && r->p != other_watch              /* which is not watched */
 636                   && !DECISIONMAP_FALSE(r->p))        /* and not FALSE */
 637                 {
 638                   p = r->p;
 639                 }
 640               else                                    /* go find a 'd' to make 'true' */
 641                 {
 642                   /* foreach p in 'd'
 643                      we just iterate sequentially, doing it in another order just changes the order of decisions, not the decisions itself
 644                    */
 645                   for (dp = pool->whatprovidesdata + r->d; (p = *dp++) != 0;)
 646                     {
 647                       if (p != other_watch              /* which is not watched */
 648                           && !DECISIONMAP_FALSE(p))     /* and not FALSE */
 649                         break;
 650                     }
 651                 }
 652
 653               if (p)
 654                 {
 655                   /*
 656                    * if we found some p that is UNDEF or TRUE, move
 657                    * watch to it
 658                    */
 659                   IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
 660                     {
 661                       if (p > 0)
 662                         POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "    -> move w%d to %s\n", (pkg == r->w1 ? 1 : 2), pool_solvid2str(pool, p));
 663                       else
 664                         POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "    -> move w%d to !%s\n", (pkg == r->w1 ? 1 : 2), pool_solvid2str(pool, -p));
 665                     }
 666
 667                   *rp = *next_rp;
 668                   next_rp = rp;
 669
 670                   if (pkg == r->w1)
 671                     {
 672                       r->w1 = p;
 673                       r->n1 = watches[p];
 674                     }
 675                   else
 676                     {
 677                       r->w2 = p;
 678                       r->n2 = watches[p];
 679                     }
 680                   watches[p] = r - solv->rules;
 681                   continue;
 682                 }
 683               /* search failed, thus all unwatched literals are FALSE */
 684
 685             } /* not binary */
 686
 687           /*
 688            * unit clause found, set literal other_watch to TRUE
 689            */
 690
 691           if (DECISIONMAP_FALSE(other_watch))      /* check if literal is FALSE */
 692             return r;                              /* eek, a conflict! */
 693
 694           IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
 695             {
 696               POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "  unit ");
 697               solver_printrule(solv, SOLV_DEBUG_PROPAGATE, r);
 698             }
 699
 700           if (other_watch > 0)
 701             decisionmap[other_watch] = level;    /* install! */
 702           else
 703             decisionmap[-other_watch] = -level;  /* remove! */
 704
 705           queue_push(&solv->decisionq, other_watch);
 706           queue_push(&solv->decisionq_why, r - solv->rules);
 707
 708           IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
 709             {
 710               if (other_watch > 0)
 711                 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "    -> decided to install %s\n", pool_solvid2str(pool, other_watch));
 712               else
 713                 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "    -> decided to conflict %s\n", pool_solvid2str(pool, -other_watch));
 714             }
 715
 716         } /* foreach rule involving 'pkg' */
 717
 718     } /* while we have non-decided decisions */
 719
 720   POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "----- propagate end-----\n");
 721
 722   return 0;     /* all is well */
 723 }
 724
 725
 726 /********************************************************************/
 727 /* Analysis */
 728
 729 /*-------------------------------------------------------------------
 730  *
 731  * revert
 732  * revert decisionq to a level
 733  */
 734
 735 static void
 736 revert(Solver *solv, int level)
 737 {
 738   Pool *pool = solv->pool;
 739   Id v, vv;
 740   while (solv->decisionq.count)
 741     {
 742       v = solv->decisionq.elements[solv->decisionq.count - 1];
 743       vv = v > 0 ? v : -v;
 744       if (solv->decisionmap[vv] <= level && solv->decisionmap[vv] >= -level)
 745         break;
 746       POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "reverting decision %d at %d\n", v, solv->decisionmap[vv]);
 747       solv->decisionmap[vv] = 0;
 748       solv->decisionq.count--;
 749       solv->decisionq_why.count--;
 750       solv->propagate_index = solv->decisionq.count;
 751     }
 752   while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] >= level)
 753     solv->branches.count -= solv->branches.elements[solv->branches.count - 2];
 754   if (solv->recommends_index > solv->decisionq.count)
 755     solv->recommends_index = -1;        /* rebuild recommends/suggests maps */
 756   solv->decisionq_reason.count = level + 1;
 757 }
 758
 759 /*-------------------------------------------------------------------
 760  *
 761  * watch2onhighest - put watch2 on literal with highest level
 762  */
 763
 764 static inline void
 765 watch2onhighest(Solver *solv, Rule *r)
 766 {
 767   int l, wl = 0;
 768   Id d, v, *dp;
 769
 770   d = r->d < 0 ? -r->d - 1 : r->d;
 771   if (!d)
 772     return;     /* binary rule, both watches are set */
 773   dp = solv->pool->whatprovidesdata + d;
 774   while ((v = *dp++) != 0)
 775     {
 776       l = solv->decisionmap[v < 0 ? -v : v];
 777       if (l < 0)
 778         l = -l;
 779       if (l > wl)
 780         {
 781           r->w2 = dp[-1];
 782           wl = l;
 783         }
 784     }
 785 }
 786
 787
 788 /*-------------------------------------------------------------------
 789  *
 790  * analyze
 791  *   and learn
 792  */
 793
 794 static int
 795 analyze(Solver *solv, int level, Rule *c, Rule **lrp)
 796 {
 797   Pool *pool = solv->pool;
 798   Queue q;
 799   Rule *r;
 800   Id q_buf[8];
 801   int rlevel = 1;
 802   Map seen;             /* global? */
 803   Id p = 0, pp, v, vv, why;
 804   int l, i, idx;
 805   int num = 0, l1num = 0;
 806   int learnt_why = solv->learnt_pool.count;
 807   Id *decisionmap = solv->decisionmap;
 808
 809   queue_init_buffer(&q, q_buf, sizeof(q_buf)/sizeof(*q_buf));
 810
 811   POOL_DEBUG(SOLV_DEBUG_ANALYZE, "ANALYZE at %d ----------------------\n", level);
 812   map_init(&seen, pool->nsolvables);
 813   idx = solv->decisionq.count;
 814   for (;;)
 815     {
 816       IF_POOLDEBUG (SOLV_DEBUG_ANALYZE)
 817         solver_printruleclass(solv, SOLV_DEBUG_ANALYZE, c);
 818       queue_push(&solv->learnt_pool, c - solv->rules);
 819       FOR_RULELITERALS(v, pp, c)
 820         {
 821           if (DECISIONMAP_TRUE(v))      /* the one true literal */
 822             continue;
 823           vv = v > 0 ? v : -v;
 824           if (MAPTST(&seen, vv))
 825             continue;
 826           MAPSET(&seen, vv);            /* mark that we also need to look at this literal */
 827           l = solv->decisionmap[vv];
 828           if (l < 0)
 829             l = -l;
 830           if (l == 1)
 831             l1num++;                    /* need to do this one in level1 pass */
 832           else if (l == level)
 833             num++;                      /* need to do this one as well */
 834           else
 835             {
 836               queue_push(&q, v);        /* not level1 or conflict level, add to new rule */
 837               if (l > rlevel)
 838                 rlevel = l;
 839             }
 840         }
 841 l1retry:
 842       if (!num && !--l1num)
 843         break;  /* all literals done */
 844
 845       /* find the next literal to investigate */
 846       /* (as num + l1num > 0, we know that we'll always find one) */
 847       for (;;)
 848         {
 849           assert(idx > 0);
 850           v = solv->decisionq.elements[--idx];
 851           vv = v > 0 ? v : -v;
 852           if (MAPTST(&seen, vv))
 853             break;
 854         }
 855       MAPCLR(&seen, vv);
 856
 857       if (num && --num == 0)
 858         {
 859           /* done with normal literals, now start level 1 literal processing */
 860           p = -v;       /* so that v doesn't get lost */
 861           if (!l1num)
 862             break;
 863           POOL_DEBUG(SOLV_DEBUG_ANALYZE, "got %d involved level 1 decisions\n", l1num);
 864           /* clear non-l1 bits from seen map */
 865           for (i = 0; i < q.count; i++)
 866             {
 867               v = q.elements[i];
 868               MAPCLR(&seen, v > 0 ? v : -v);
 869             }
 870           /* only level 1 marks left in seen map */
 871           l1num++;      /* as l1retry decrements it */
 872           goto l1retry;
 873         }
 874
 875       why = solv->decisionq_why.elements[idx];
 876       if (why <= 0)     /* just in case, maybe for SYSTEMSOLVABLE */
 877         goto l1retry;
 878       c = solv->rules + why;
 879     }
 880   map_free(&seen);
 881   assert(p != 0);
 882   assert(rlevel > 0 && rlevel < level);
 883   IF_POOLDEBUG (SOLV_DEBUG_ANALYZE)
 884     {
 885       POOL_DEBUG(SOLV_DEBUG_ANALYZE, "learned rule for level %d (am %d)\n", rlevel, level);
 886       solver_printruleelement(solv, SOLV_DEBUG_ANALYZE, 0, p);
 887       for (i = 0; i < q.count; i++)
 888         solver_printruleelement(solv, SOLV_DEBUG_ANALYZE, 0, q.elements[i]);
 889     }
 890   /* push end marker on learnt reasons stack */
 891   queue_push(&solv->learnt_pool, 0);
 892   solv->stats_learned++;
 893
 894   POOL_DEBUG(SOLV_DEBUG_ANALYZE, "reverting decisions (level %d -> %d)\n", level, rlevel);
 895   level = rlevel;
 896   revert(solv, level);
 897   if (q.count < 2)
 898     {
 899       Id d = q.count ? q.elements[0] : 0;
 900       queue_free(&q);
 901       r = solver_addrule(solv, p, d, 0);
 902     }
 903   else
 904     {
 905       Id d = pool_queuetowhatprovides(pool, &q);
 906       queue_free(&q);
 907       r = solver_addrule(solv, p, 0, d);
 908     }
 909   assert(solv->learnt_why.count == (r - solv->rules) - solv->learntrules);
 910   queue_push(&solv->learnt_why, learnt_why);
 911   if (r->w2)
 912     {
 913       /* needs watches */
 914       watch2onhighest(solv, r);
 915       addwatches_rule(solv, r);
 916     }
 917   else
 918     {
 919       /* rule is an assertion */
 920       queue_push(&solv->ruleassertions, r - solv->rules);
 921     }
 922   *lrp = r;
 923   return level;
 924 }
 925
 926
 927 /*-------------------------------------------------------------------
 928  *
 929  * solver_reset
 930  *
 931  * reset all solver decisions
 932  * called after rules have been enabled/disabled
 933  */
 934
 935 void
 936 solver_reset(Solver *solv)
 937 {
 938   int i;
 939   Id v;
 940
 941   /* rewind all decisions */
 942   for (i = solv->decisionq.count - 1; i >= 0; i--)
 943     {
 944       v = solv->decisionq.elements[i];
 945       solv->decisionmap[v > 0 ? v : -v] = 0;
 946     }
 947   queue_empty(&solv->decisionq_why);
 948   queue_empty(&solv->decisionq);
 949   queue_empty(&solv->decisionq_reason);
 950   solv->recommends_index = -1;
 951   solv->propagate_index = 0;
 952   queue_empty(&solv->branches);
 953
 954   /* adapt learnt rule status to new set of enabled/disabled rules */
 955   enabledisablelearntrules(solv);
 956 }
 957
 958 static inline int
 959 queue_contains(Queue *q, Id id)
 960 {
 961   int i;
 962   for (i = 0; i < q->count; i++)
 963     if (q->elements[i] == id)
 964       return 1;
 965   return 0;
 966 }
 967
 968 static void
 969 disable_recommendsrules(Solver *solv, Queue *weakq)
 970 {
 971   Pool *pool = solv->pool;
 972   int i;
 973   for (i = 0; i < weakq->count; i++)
 974     {
 975       Rule *r;
 976       if (!queue_contains(solv->recommendsruleq, weakq->elements[i]))
 977         continue;
 978       r = solv->rules + weakq->elements[i];
 979       if (r->d >= 0)
 980         {
 981           POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "disabling ");
 982           solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE, r);
 983           solver_disablerule(solv, r);
 984         }
 985     }
 986 }
 987
 988 /*-------------------------------------------------------------------
 989  *
 990  * analyze_unsolvable_rule
 991  *
 992  * recursion helper used by analyze_unsolvable
 993  */
 994
 995 static void
 996 analyze_unsolvable_rule(Solver *solv, Rule *r, Queue *weakq, Map *rseen)
 997 {
 998   Pool *pool = solv->pool;
 999   int i;
1000   Id why = r - solv->rules;
1001
1002   IF_POOLDEBUG (SOLV_DEBUG_UNSOLVABLE)
1003     solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE, r);
1004   if (solv->learntrules && why >= solv->learntrules)
1005     {
1006       if (MAPTST(rseen, why - solv->learntrules))
1007         return;
1008       MAPSET(rseen, why - solv->learntrules);
1009       for (i = solv->learnt_why.elements[why - solv->learntrules]; solv->learnt_pool.elements[i]; i++)
1010         if (solv->learnt_pool.elements[i] > 0)
1011           analyze_unsolvable_rule(solv, solv->rules + solv->learnt_pool.elements[i], weakq, rseen);
1012       return;
1013     }
1014   if (solv->weakrulemap.size && MAPTST(&solv->weakrulemap, why) && weakq)
1015     queue_push(weakq, why);
1016   /* do not add pkg rules to problem */
1017   if (why < solv->pkgrules_end)
1018     return;
1019   /* turn rule into problem */
1020   if (why >= solv->jobrules && why < solv->jobrules_end)
1021     why = -(solv->ruletojob.elements[why - solv->jobrules] + 1);
1022   /* normalize dup/infarch rules */
1023   if (why > solv->infarchrules && why < solv->infarchrules_end)
1024     {
1025       Id name = pool->solvables[-solv->rules[why].p].name;
1026       while (why > solv->infarchrules && pool->solvables[-solv->rules[why - 1].p].name == name)
1027         why--;
1028     }
1029   if (why > solv->duprules && why < solv->duprules_end)
1030     {
1031       Id name = pool->solvables[-solv->rules[why].p].name;
1032       while (why > solv->duprules && pool->solvables[-solv->rules[why - 1].p].name == name)
1033         why--;
1034     }
1035
1036   /* return if problem already countains our rule */
1037   if (solv->problems.count)
1038     {
1039       for (i = solv->problems.count - 1; i >= 0; i--)
1040         if (solv->problems.elements[i] == 0)    /* end of last problem reached? */
1041           break;
1042         else if (solv->problems.elements[i] == why)
1043           return;
1044     }
1045   queue_push(&solv->problems, why);
1046 }
1047
1048
1049 /*-------------------------------------------------------------------
1050  *
1051  * analyze_unsolvable (called from setpropagatelearn)
1052  *
1053  * We know that the problem is not solvable. Record all involved
1054  * rules (i.e. the "proof") into solv->learnt_pool.
1055  * Record the learnt pool index and all non-pkg rules into
1056  * solv->problems. (Our solutions to fix the problems are to
1057  * disable those rules.)
1058  *
1059  * If the proof contains at least one weak rule, we disable the
1060  * last of them.
1061  *
1062  * Otherwise we return -1 if disablerules is not set or disable
1063  * _all_ of the problem rules and return 0.
1064  *
1065  * return:  0 - disabled some rules, try again
1066  *         -1 - hopeless
1067  */
1068
1069 static int
1070 analyze_unsolvable(Solver *solv, Rule *cr, int disablerules)
1071 {
1072   Pool *pool = solv->pool;
1073   Rule *r;
1074   Map involved;         /* global to speed things up? */
1075   Map rseen;
1076   Queue weakq;
1077   Id pp, v, vv, why;
1078   int i, idx;
1079   Id *decisionmap = solv->decisionmap;
1080   int oldproblemcount;
1081   int oldlearntpoolcount;
1082   int record_proof = 1;
1083
1084   POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "ANALYZE UNSOLVABLE ----------------------\n");
1085   solv->stats_unsolvable++;
1086   oldproblemcount = solv->problems.count;
1087   oldlearntpoolcount = solv->learnt_pool.count;
1088
1089   /* make room for proof index */
1090   /* must update it later, as analyze_unsolvable_rule would confuse
1091    * it with a rule index if we put the real value in already */
1092   queue_push(&solv->problems, 0);
1093
1094   r = cr;
1095   map_init(&involved, pool->nsolvables);
1096   map_init(&rseen, solv->learntrules ? solv->nrules - solv->learntrules : 0);
1097   queue_init(&weakq);
1098   if (record_proof)
1099     queue_push(&solv->learnt_pool, r - solv->rules);
1100   analyze_unsolvable_rule(solv, r, &weakq, &rseen);
1101   FOR_RULELITERALS(v, pp, r)
1102     {
1103       if (DECISIONMAP_TRUE(v))  /* the one true literal */
1104           continue;
1105       vv = v > 0 ? v : -v;
1106       MAPSET(&involved, vv);
1107     }
1108   idx = solv->decisionq.count;
1109   while (idx > 0)
1110     {
1111       v = solv->decisionq.elements[--idx];
1112       vv = v > 0 ? v : -v;
1113       if (!MAPTST(&involved, vv) || vv == SYSTEMSOLVABLE)
1114         continue;
1115       why = solv->decisionq_why.elements[idx];
1116       assert(why > 0);
1117       if (record_proof)
1118         queue_push(&solv->learnt_pool, why);
1119       r = solv->rules + why;
1120       analyze_unsolvable_rule(solv, r, &weakq, &rseen);
1121       FOR_RULELITERALS(v, pp, r)
1122         {
1123           if (DECISIONMAP_TRUE(v))      /* the one true literal */
1124               continue;
1125           vv = v > 0 ? v : -v;
1126           MAPSET(&involved, vv);
1127         }
1128     }
1129   map_free(&involved);
1130   map_free(&rseen);
1131   queue_push(&solv->problems, 0);       /* mark end of this problem */
1132
1133   if (weakq.count)
1134     {
1135       Id lastweak;
1136       /* revert problems */
1137       solv->problems.count = oldproblemcount;
1138       solv->learnt_pool.count = oldlearntpoolcount;
1139       /* find last weak */
1140       lastweak = 0;
1141       for (i = 0; i < weakq.count; i++)
1142         if (weakq.elements[i] > lastweak)
1143           lastweak = weakq.elements[i];
1144       if (lastweak < solv->pkgrules_end && solv->strongrecommends && solv->recommendsruleq && queue_contains(solv->recommendsruleq, lastweak))
1145         {
1146           disable_recommendsrules(solv, &weakq);
1147           queue_free(&weakq);
1148           solver_reset(solv);
1149           return 0;
1150         }
1151       queue_free(&weakq);
1152       if (lastweak >= solv->jobrules && lastweak < solv->jobrules_end)
1153         v = -(solv->ruletojob.elements[lastweak - solv->jobrules] + 1);
1154       else
1155         v = lastweak;
1156       POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "disabling ");
1157       solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE, solv->rules + lastweak);
1158       if (lastweak >= solv->choicerules && lastweak < solv->choicerules_end)
1159         solver_disablechoicerules(solv, solv->rules + lastweak);
1160       solver_disableproblem(solv, v);
1161       if (v < 0)
1162         solver_reenablepolicyrules(solv, -v);
1163       solver_reset(solv);
1164       return 0;
1165     }
1166   queue_free(&weakq);
1167
1168   if (solv->allowuninstall || solv->allowuninstall_all || solv->allowuninstallmap.size)
1169     if (autouninstall(solv, solv->problems.elements + oldproblemcount + 1) != 0)
1170       {
1171         solv->problems.count = oldproblemcount;
1172         solv->learnt_pool.count = oldlearntpoolcount;
1173         solver_reset(solv);
1174         return 0;
1175       }
1176
1177   /* finish proof */
1178   if (record_proof)
1179     {
1180       queue_push(&solv->learnt_pool, 0);
1181       solv->problems.elements[oldproblemcount] = oldlearntpoolcount;
1182     }
1183
1184   /* + 2: index + trailing zero */
1185   if (disablerules && oldproblemcount + 2 < solv->problems.count)
1186     {
1187       for (i = oldproblemcount + 1; i < solv->problems.count - 1; i++)
1188         solver_disableproblem(solv, solv->problems.elements[i]);
1189       /* XXX: might want to enable all weak rules again */
1190       solver_reset(solv);
1191       return 0;
1192     }
1193   POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "UNSOLVABLE\n");
1194   return -1;
1195 }
1196
1197
1198 /*-------------------------------------------------------------------
1199  *
1200  * setpropagatelearn
1201  *
1202  * add free decision (solvable to install) to decisionq
1203  * increase level and propagate decision
1204  * return if no conflict.
1205  *
1206  * in conflict case, analyze conflict rule, add resulting
1207  * rule to learnt rule set, make decision from learnt
1208  * rule (always unit) and re-propagate.
1209  *
1210  * returns the new solver level or -1 if unsolvable
1211  *
1212  */
1213
1214 static int
1215 setpropagatelearn(Solver *solv, int level, Id decision, int disablerules, Id ruleid, Id reason)
1216 {
1217   Pool *pool = solv->pool;
1218   Rule *r, *lr;
1219
1220   if (decision)
1221     {
1222       level++;
1223       if (decision > 0)
1224         solv->decisionmap[decision] = level;
1225       else
1226         solv->decisionmap[-decision] = -level;
1227       queue_push(&solv->decisionq, decision);
1228       queue_push(&solv->decisionq_why, -ruleid);        /* <= 0 -> free decision */
1229       queue_push(&solv->decisionq_reason, reason);
1230     }
1231   assert(ruleid >= 0 && level > 0);
1232   for (;;)
1233     {
1234       r = propagate(solv, level);
1235       if (!r)
1236         break;
1237       if (level == 1)
1238         return analyze_unsolvable(solv, r, disablerules);
1239       POOL_DEBUG(SOLV_DEBUG_ANALYZE, "conflict with rule #%d\n", (int)(r - solv->rules));
1240       level = analyze(solv, level, r, &lr);
1241       /* the new rule is unit by design */
1242       decision = lr->p;
1243       solv->decisionmap[decision > 0 ? decision : -decision] = decision > 0 ? level : -level;
1244       queue_push(&solv->decisionq, decision);
1245       queue_push(&solv->decisionq_why, lr - solv->rules);
1246       IF_POOLDEBUG (SOLV_DEBUG_ANALYZE)
1247         {
1248           POOL_DEBUG(SOLV_DEBUG_ANALYZE, "decision: ");
1249           solver_printruleelement(solv, SOLV_DEBUG_ANALYZE, 0, decision);
1250           POOL_DEBUG(SOLV_DEBUG_ANALYZE, "new rule: ");
1251           solver_printrule(solv, SOLV_DEBUG_ANALYZE, lr);
1252         }
1253     }
1254   return level;
1255 }
1256
1257 static void
1258 reorder_dq_for_future_installed(Solver *solv, int level, Queue *dq)
1259 {
1260   Pool *pool = solv->pool;
1261   int i, j, haveone = 0, dqcount = dq->count;
1262   int decisionqcount = solv->decisionq.count;
1263   Id p;
1264   Solvable *s;
1265
1266   /* at the time we process jobrules the installed packages are not kept yet */
1267   /* reorder so that "future-supplemented" packages come first */
1268   FOR_REPO_SOLVABLES(solv->installed, p, s)
1269     {
1270       if (MAPTST(&solv->noupdate, p - solv->installed->start))
1271         continue;
1272       if (solv->decisionmap[p] == 0)
1273         {
1274           if (s->recommends || s->suggests)
1275             queue_push(&solv->decisionq, p);
1276           solv->decisionmap[p] = level + 1;
1277           haveone = 1;
1278         }
1279     }
1280   if (!haveone)
1281     return;
1282   policy_update_recommendsmap(solv);
1283   for (i = 0; i < dqcount; i++)
1284     {
1285       p = dq->elements[i];
1286       if (!(pool->solvables[p].repo == solv->installed || MAPTST(&solv->suggestsmap, p) || solver_is_enhancing(solv, pool->solvables + p)))
1287         {
1288           queue_push(dq, p);
1289           dq->elements[i] = 0;
1290         }
1291     }
1292   dqcount = dq->count;
1293   for (i = 0; i < dqcount; i++)
1294     {
1295       p = dq->elements[i];
1296       if (p && !(pool->solvables[p].repo == solv->installed || MAPTST(&solv->recommendsmap, p) || solver_is_supplementing(solv, pool->solvables + p)))
1297         {
1298           queue_push(dq, p);
1299           dq->elements[i] = 0;
1300         }
1301     }
1302   for (i = j = 0; i < dq->count; i++)
1303     if (dq->elements[i])
1304       dq->elements[j++] = dq->elements[i];
1305   queue_truncate(dq, j);
1306   FOR_REPO_SOLVABLES(solv->installed, p, s)
1307     if (solv->decisionmap[p] == level + 1)
1308       solv->decisionmap[p] = 0;
1309   if (solv->decisionq.count != decisionqcount)
1310     {
1311       solv->recommends_index = -1;
1312       queue_truncate(&solv->decisionq, decisionqcount);
1313     }
1314   /* but obey favored maps */
1315   policy_prefer_favored(solv, dq);
1316 }
1317
1318 /*-------------------------------------------------------------------
1319  *
1320  * branch handling
1321  */
1322
1323 static void
1324 createbranch(Solver *solv, int level, Queue *dq, Id p, Id data)
1325 {
1326   Pool *pool = solv->pool;
1327   int i;
1328   IF_POOLDEBUG (SOLV_DEBUG_POLICY)
1329     {
1330       POOL_DEBUG (SOLV_DEBUG_POLICY, "creating a branch:\n");
1331       for (i = 0; i < dq->count; i++)
1332         POOL_DEBUG (SOLV_DEBUG_POLICY, "  - %s\n", pool_solvid2str(pool, dq->elements[i]));
1333     }
1334   queue_push(&solv->branches, -dq->elements[0]);
1335   for (i = 1; i < dq->count; i++)
1336     queue_push(&solv->branches, dq->elements[i]);
1337   queue_push2(&solv->branches, p, data);
1338   queue_push2(&solv->branches, dq->count + 4, level);
1339 }
1340
1341 static int
1342 takebranch(Solver *solv, int pos, int end, const char *msg, int disablerules)
1343 {
1344   Pool *pool = solv->pool;
1345   int level;
1346   Id p, why, reason;
1347 #if 0
1348   {
1349     int i;
1350     printf("branch group level %d [%d-%d] %d %d:\n", solv->branches.elements[end - 1], start, end, solv->branches.elements[end - 4], solv->branches.elements[end - 3]);
1351     for (i = end - solv->branches.elements[end - 2]; i < end - 4; i++)
1352       printf("%c %c%s\n", i == pos ? 'x' : ' ', solv->branches.elements[i] >= 0 ? ' ' : '-', pool_solvid2str(pool, solv->branches.elements[i] >= 0 ? solv->branches.elements[i] : -solv->branches.elements[i]));
1353   }
1354 #endif
1355   level = solv->branches.elements[end - 1];
1356   p = solv->branches.elements[pos];
1357   solv->branches.elements[pos] = -p;
1358   POOL_DEBUG(SOLV_DEBUG_SOLVER, "%s %d -> %d with %s\n", msg, solv->decisionmap[p], level, pool_solvid2str(pool, p));
1359   /* hack: set level to zero so that revert does not remove the branch */
1360   solv->branches.elements[end - 1] = 0;
1361   revert(solv, level);
1362   solv->branches.elements[end - 1] = level;
1363   /* hack: revert simply sets the count, so we can still access the reverted elements */
1364   why = -solv->decisionq_why.elements[solv->decisionq_why.count];
1365   assert(why >= 0);
1366   reason = solv->decisionq_reason.elements[level + 1];
1367   return setpropagatelearn(solv, level, p, disablerules, why, reason);
1368 }
1369
1370 /*-------------------------------------------------------------------
1371  *
1372  * select and install
1373  *
1374  * install best package from the queue. We add an extra package, inst, if
1375  * provided. See comment in weak install section.
1376  *
1377  * returns the new solver level or -1 if unsolvable
1378  *
1379  */
1380
1381 static int
1382 selectandinstall(Solver *solv, int level, Queue *dq, int disablerules, Id ruleid, Id reason)
1383 {
1384   Pool *pool = solv->pool;
1385   Id p;
1386
1387   if (dq->count > 1)
1388     policy_filter_unwanted(solv, dq, POLICY_MODE_CHOOSE);
1389   /* if we're resolving rules and didn't resolve the installed packages yet,
1390    * do some special supplements ordering */
1391   if (dq->count > 1 && solv->do_extra_reordering)
1392     reorder_dq_for_future_installed(solv, level, dq);
1393   /* if we have multiple candidates we open a branch */
1394   if (dq->count > 1)
1395     createbranch(solv, level, dq, 0, ruleid);
1396   p = dq->elements[0];
1397   POOL_DEBUG(SOLV_DEBUG_POLICY, "installing %s\n", pool_solvid2str(pool, p));
1398   return setpropagatelearn(solv, level, p, disablerules, ruleid, reason);
1399 }
1400
1401
1402 /********************************************************************/
1403 /* Main solver interface */
1404
1405
1406 /*-------------------------------------------------------------------
1407  *
1408  * solver_create
1409  * create solver structure
1410  *
1411  * pool: all available solvables
1412  * installed: installed Solvables
1413  *
1414  *
1415  * Upon solving, rules are created to flag the Solvables
1416  * of the 'installed' Repo as installed.
1417  */
1418
1419 Solver *
1420 solver_create(Pool *pool)
1421 {
1422   Solver *solv;
1423   solv = (Solver *)solv_calloc(1, sizeof(Solver));
1424   solv->pool = pool;
1425   solv->installed = pool->installed;
1426
1427   solv->allownamechange = 1;
1428
1429   solv->dup_allowdowngrade = 1;
1430   solv->dup_allownamechange = 1;
1431   solv->dup_allowarchchange = 1;
1432   solv->dup_allowvendorchange = 1;
1433
1434   solv->keepexplicitobsoletes = pool->noobsoletesmultiversion ? 0 : 1;
1435
1436   queue_init(&solv->ruletojob);
1437   queue_init(&solv->decisionq);
1438   queue_init(&solv->decisionq_why);
1439   queue_init(&solv->decisionq_reason);
1440   queue_init(&solv->problems);
1441   queue_init(&solv->orphaned);
1442   queue_init(&solv->learnt_why);
1443   queue_init(&solv->learnt_pool);
1444   queue_init(&solv->branches);
1445   queue_init(&solv->weakruleq);
1446   queue_init(&solv->ruleassertions);
1447   queue_init(&solv->addedmap_deduceq);
1448
1449   queue_push(&solv->learnt_pool, 0);    /* so that 0 does not describe a proof */
1450
1451   map_init(&solv->recommendsmap, pool->nsolvables);
1452   map_init(&solv->suggestsmap, pool->nsolvables);
1453   map_init(&solv->noupdate, solv->installed ? solv->installed->end - solv->installed->start : 0);
1454   solv->recommends_index = 0;
1455
1456   solv->decisionmap = (Id *)solv_calloc(pool->nsolvables, sizeof(Id));
1457   solv->nrules = 1;
1458   solv->rules = solv_extend_resize(solv->rules, solv->nrules, sizeof(Rule), RULES_BLOCK);
1459   memset(solv->rules, 0, sizeof(Rule));
1460
1461   return solv;
1462 }
1463
1464
1465
1466 /*-------------------------------------------------------------------
1467  *
1468  * solver_free
1469  */
1470
1471 static inline void
1472 queuep_free(Queue **qp)
1473 {
1474   if (!*qp)
1475     return;
1476   queue_free(*qp);
1477   *qp = solv_free(*qp);
1478 }
1479
1480 static inline void
1481 map_zerosize(Map *m)
1482 {
1483   if (m->size)
1484     {
1485       map_free(m);
1486       map_init(m, 0);
1487     }
1488 }
1489
1490 void
1491 solver_free(Solver *solv)
1492 {
1493   queue_free(&solv->job);
1494   queue_free(&solv->ruletojob);
1495   queue_free(&solv->decisionq);
1496   queue_free(&solv->decisionq_why);
1497   queue_free(&solv->decisionq_reason);
1498   queue_free(&solv->learnt_why);
1499   queue_free(&solv->learnt_pool);
1500   queue_free(&solv->problems);
1501   queue_free(&solv->solutions);
1502   queue_free(&solv->orphaned);
1503   queue_free(&solv->branches);
1504   queue_free(&solv->weakruleq);
1505   queue_free(&solv->ruleassertions);
1506   queue_free(&solv->addedmap_deduceq);
1507   queuep_free(&solv->cleandeps_updatepkgs);
1508   queuep_free(&solv->cleandeps_mistakes);
1509   queuep_free(&solv->update_targets);
1510   queuep_free(&solv->installsuppdepq);
1511   queuep_free(&solv->recommendscplxq);
1512   queuep_free(&solv->suggestscplxq);
1513   queuep_free(&solv->brokenorphanrules);
1514   queuep_free(&solv->favorq);
1515   queuep_free(&solv->recommendsruleq);
1516
1517   map_free(&solv->recommendsmap);
1518   map_free(&solv->suggestsmap);
1519   map_free(&solv->noupdate);
1520   map_free(&solv->weakrulemap);
1521   map_free(&solv->multiversion);
1522
1523   map_free(&solv->updatemap);
1524   map_free(&solv->bestupdatemap);
1525   map_free(&solv->fixmap);
1526   map_free(&solv->dupmap);
1527   map_free(&solv->dupinvolvedmap);
1528   map_free(&solv->droporphanedmap);
1529   map_free(&solv->cleandepsmap);
1530   map_free(&solv->allowuninstallmap);
1531   map_free(&solv->favormap);
1532   map_free(&solv->isdisfavormap);
1533
1534   solv_free(solv->decisionmap);
1535   solv_free(solv->rules);
1536   solv_free(solv->watches);
1537   solv_free(solv->obsoletes);
1538   solv_free(solv->obsoletes_data);
1539   solv_free(solv->specialupdaters);
1540   solv_free(solv->choicerules_ref);
1541   solv_free(solv->bestrules_pkg);
1542   solv_free(solv->yumobsrules_info);
1543   solv_free(solv->instbuddy);
1544   solv_free(solv);
1545 }
1546
1547 int
1548 solver_get_flag(Solver *solv, int flag)
1549 {
1550   switch (flag)
1551   {
1552   case SOLVER_FLAG_ALLOW_DOWNGRADE:
1553     return solv->allowdowngrade;
1554   case SOLVER_FLAG_ALLOW_NAMECHANGE:
1555     return solv->allownamechange;
1556   case SOLVER_FLAG_ALLOW_ARCHCHANGE:
1557     return solv->allowarchchange;
1558   case SOLVER_FLAG_ALLOW_VENDORCHANGE:
1559     return solv->allowvendorchange;
1560   case SOLVER_FLAG_ALLOW_UNINSTALL:
1561     return solv->allowuninstall;
1562   case SOLVER_FLAG_NO_UPDATEPROVIDE:
1563     return solv->noupdateprovide;
1564   case SOLVER_FLAG_SPLITPROVIDES:
1565     return solv->dosplitprovides;
1566   case SOLVER_FLAG_IGNORE_RECOMMENDED:
1567     return solv->dontinstallrecommended;
1568   case SOLVER_FLAG_ADD_ALREADY_RECOMMENDED:
1569     return solv->addalreadyrecommended;
1570   case SOLVER_FLAG_NO_INFARCHCHECK:
1571     return solv->noinfarchcheck;
1572   case SOLVER_FLAG_KEEP_EXPLICIT_OBSOLETES:
1573     return solv->keepexplicitobsoletes;
1574   case SOLVER_FLAG_BEST_OBEY_POLICY:
1575     return solv->bestobeypolicy;
1576   case SOLVER_FLAG_NO_AUTOTARGET:
1577     return solv->noautotarget;
1578   case SOLVER_FLAG_DUP_ALLOW_DOWNGRADE:
1579     return solv->dup_allowdowngrade;
1580   case SOLVER_FLAG_DUP_ALLOW_NAMECHANGE:
1581     return solv->dup_allownamechange;
1582   case SOLVER_FLAG_DUP_ALLOW_ARCHCHANGE:
1583     return solv->dup_allowarchchange;
1584   case SOLVER_FLAG_DUP_ALLOW_VENDORCHANGE:
1585     return solv->dup_allowvendorchange;
1586   case SOLVER_FLAG_KEEP_ORPHANS:
1587     return solv->keep_orphans;
1588   case SOLVER_FLAG_BREAK_ORPHANS:
1589     return solv->break_orphans;
1590   case SOLVER_FLAG_FOCUS_INSTALLED:
1591     return solv->focus_installed;
1592   case SOLVER_FLAG_FOCUS_BEST:
1593     return solv->focus_best;
1594   case SOLVER_FLAG_YUM_OBSOLETES:
1595     return solv->do_yum_obsoletes;
1596   case SOLVER_FLAG_NEED_UPDATEPROVIDE:
1597     return solv->needupdateprovide;
1598   case SOLVER_FLAG_URPM_REORDER:
1599     return solv->urpmreorder;
1600   case SOLVER_FLAG_STRONG_RECOMMENDS:
1601     return solv->strongrecommends;
1602   case SOLVER_FLAG_INSTALL_ALSO_UPDATES:
1603     return solv->install_also_updates;
1604   default:
1605     break;
1606   }
1607   return -1;
1608 }
1609
1610 int
1611 solver_set_flag(Solver *solv, int flag, int value)
1612 {
1613   int old = solver_get_flag(solv, flag);
1614   switch (flag)
1615   {
1616   case SOLVER_FLAG_ALLOW_DOWNGRADE:
1617     solv->allowdowngrade = value;
1618     break;
1619   case SOLVER_FLAG_ALLOW_NAMECHANGE:
1620     solv->allownamechange = value;
1621     break;
1622   case SOLVER_FLAG_ALLOW_ARCHCHANGE:
1623     solv->allowarchchange = value;
1624     break;
1625   case SOLVER_FLAG_ALLOW_VENDORCHANGE:
1626     solv->allowvendorchange = value;
1627     break;
1628   case SOLVER_FLAG_ALLOW_UNINSTALL:
1629     solv->allowuninstall = value;
1630     break;
1631   case SOLVER_FLAG_NO_UPDATEPROVIDE:
1632     solv->noupdateprovide = value;
1633     break;
1634   case SOLVER_FLAG_SPLITPROVIDES:
1635     solv->dosplitprovides = value;
1636     break;
1637   case SOLVER_FLAG_IGNORE_RECOMMENDED:
1638     solv->dontinstallrecommended = value;
1639     break;
1640   case SOLVER_FLAG_ADD_ALREADY_RECOMMENDED:
1641     solv->addalreadyrecommended = value;
1642     break;
1643   case SOLVER_FLAG_NO_INFARCHCHECK:
1644     solv->noinfarchcheck = value;
1645     break;
1646   case SOLVER_FLAG_KEEP_EXPLICIT_OBSOLETES:
1647     solv->keepexplicitobsoletes = value;
1648     break;
1649   case SOLVER_FLAG_BEST_OBEY_POLICY:
1650     solv->bestobeypolicy = value;
1651     break;
1652   case SOLVER_FLAG_NO_AUTOTARGET:
1653     solv->noautotarget = value;
1654     break;
1655   case SOLVER_FLAG_DUP_ALLOW_DOWNGRADE:
1656     solv->dup_allowdowngrade = value;
1657     break;
1658   case SOLVER_FLAG_DUP_ALLOW_NAMECHANGE:
1659     solv->dup_allownamechange = value;
1660     break;
1661   case SOLVER_FLAG_DUP_ALLOW_ARCHCHANGE:
1662     solv->dup_allowarchchange = value;
1663     break;
1664   case SOLVER_FLAG_DUP_ALLOW_VENDORCHANGE:
1665     solv->dup_allowvendorchange = value;
1666     break;
1667   case SOLVER_FLAG_KEEP_ORPHANS:
1668     solv->keep_orphans = value;
1669     break;
1670   case SOLVER_FLAG_BREAK_ORPHANS:
1671     solv->break_orphans = value;
1672     break;
1673   case SOLVER_FLAG_FOCUS_INSTALLED:
1674     solv->focus_installed = value;
1675     break;
1676   case SOLVER_FLAG_FOCUS_BEST:
1677     solv->focus_best = value;
1678     break;
1679   case SOLVER_FLAG_YUM_OBSOLETES:
1680     solv->do_yum_obsoletes = value;
1681     break;
1682   case SOLVER_FLAG_NEED_UPDATEPROVIDE:
1683     solv->needupdateprovide = value;
1684     break;
1685   case SOLVER_FLAG_URPM_REORDER:
1686     solv->urpmreorder = value;
1687     break;
1688   case SOLVER_FLAG_STRONG_RECOMMENDS:
1689     solv->strongrecommends = value;
1690     break;
1691   case SOLVER_FLAG_INSTALL_ALSO_UPDATES:
1692     solv->install_also_updates = value;
1693     break;
1694   default:
1695     break;
1696   }
1697   return old;
1698 }
1699
1700 static int
1701 resolve_jobrules(Solver *solv, int level, int disablerules, Queue *dq)
1702 {
1703   Pool *pool = solv->pool;
1704   int oldlevel = level;
1705   int i, olevel;
1706   Rule *r;
1707
1708   POOL_DEBUG(SOLV_DEBUG_SOLVER, "resolving job rules\n");
1709   for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++)
1710     {
1711       Id l, pp;
1712       if (r->d < 0)             /* ignore disabled rules */
1713         continue;
1714       queue_empty(dq);
1715       FOR_RULELITERALS(l, pp, r)
1716         {
1717           if (l < 0)
1718             {
1719               if (solv->decisionmap[-l] <= 0)
1720                 break;
1721             }
1722           else
1723             {
1724               if (solv->decisionmap[l] > 0)
1725                 break;
1726               if (solv->decisionmap[l] == 0)
1727                 queue_push(dq, l);
1728             }
1729         }
1730       if (l || !dq->count)
1731         continue;
1732       /* prune to installed if not updating */
1733       if (dq->count > 1 && solv->installed && !solv->updatemap_all &&
1734           !solv->install_also_updates &&
1735           !(solv->job.elements[solv->ruletojob.elements[i - solv->jobrules]] & SOLVER_ORUPDATE))
1736         {
1737           int j = dq->count, k;
1738           if (solv->updatemap.size)
1739             {
1740               /* do not prune if an installed package wants to be updated */
1741               for (j = 0; j < dq->count; j++)
1742                 if (pool->solvables[dq->elements[j]].repo == solv->installed
1743                     && MAPTST(&solv->updatemap, dq->elements[j] - solv->installed->start))
1744                   break;
1745             }
1746           if (j == dq->count)
1747             {
1748               for (j = k = 0; j < dq->count; j++)
1749                 if (pool->solvables[dq->elements[j]].repo == solv->installed)
1750                   dq->elements[k++] = dq->elements[j];
1751               if (k)
1752                 dq->count = k;
1753             }
1754         }
1755       olevel = level;
1756       level = selectandinstall(solv, level, dq, disablerules, i, SOLVER_REASON_RESOLVE_JOB);
1757       if (level <= olevel)
1758         {
1759           if (level == olevel)
1760             {
1761               i--;
1762               r--;
1763               continue; /* try something else */
1764             }
1765           if (level < oldlevel)
1766             return level;
1767           /* redo from start of jobrules */
1768           i = solv->jobrules - 1;
1769           r = solv->rules + i;
1770         }
1771     }
1772   return level;
1773 }
1774
1775 static void
1776 prune_to_update_targets(Solver *solv, Id *cp, Queue *q)
1777 {
1778   int i, j;
1779   Id p, *cp2;
1780   for (i = j = 0; i < q->count; i++)
1781     {
1782       p = q->elements[i];
1783       for (cp2 = cp; *cp2; cp2++)
1784         if (*cp2 == p)
1785           {
1786             q->elements[j++] = p;
1787             break;
1788           }
1789     }
1790   queue_truncate(q, j);
1791 }
1792
1793 static int
1794 resolve_installed(Solver *solv, int level, int disablerules, Queue *dq)
1795 {
1796   Pool *pool = solv->pool;
1797   Repo *installed = solv->installed;
1798   int i, n, pass;
1799   int installedpos = solv->installedpos;
1800   Solvable *s;
1801   Id p, pp;
1802   int olevel, origlevel = level;
1803
1804   POOL_DEBUG(SOLV_DEBUG_SOLVER, "resolving installed packages\n");
1805   if (!installedpos)
1806     installedpos = installed->start;
1807   /* we use two passes if we need to update packages
1808    * to create a better user experience */
1809   for (pass = solv->updatemap.size ? 0 : 1; pass < 2; )
1810     {
1811       int passlevel = level;
1812       Id *specialupdaters = solv->specialupdaters;
1813       /* start with installedpos, the position that gave us problems the last time */
1814       for (i = installedpos, n = installed->start; n < installed->end; i++, n++)
1815         {
1816           Rule *r, *rr;
1817           Id d;
1818
1819           if (i == installed->end)
1820             i = installed->start;
1821           s = pool->solvables + i;
1822           if (s->repo != installed)
1823             continue;
1824
1825           if (solv->decisionmap[i] > 0 && (!specialupdaters || !specialupdaters[i - installed->start]))
1826             continue;           /* already decided */
1827           if (!pass && solv->updatemap.size && !MAPTST(&solv->updatemap, i - installed->start))
1828             continue;           /* updates first */
1829           r = solv->rules + solv->updaterules + (i - installed->start);
1830           rr = r;
1831           if (!rr->p || rr->d < 0)      /* disabled -> look at feature rule */
1832             rr -= solv->installed->end - solv->installed->start;
1833           if (!rr->p)           /* identical to update rule? */
1834             rr = r;
1835           if (!rr->p)
1836             continue;           /* orpaned package or pseudo package */
1837
1838           /* check if we should update this package to the latest version
1839            * noupdate is set for erase jobs, in that case we want to deinstall
1840            * the installed package and not replace it with a newer version
1841            * rr->p != i is for dup jobs where the installed package cannot be kept */
1842           if (dq->count)
1843             queue_empty(dq);
1844           if (!MAPTST(&solv->noupdate, i - installed->start) && (solv->decisionmap[i] < 0 || solv->updatemap_all || (solv->updatemap.size && MAPTST(&solv->updatemap, i - installed->start)) || (rr->p && rr->p != i)))
1845             {
1846               if (specialupdaters && (d = specialupdaters[i - installed->start]) != 0)
1847                 {
1848                   /* special multiversion handling, make sure best version is chosen */
1849                   if (rr->p == i && solv->decisionmap[i] >= 0)
1850                     queue_push(dq, i);
1851                   while ((p = pool->whatprovidesdata[d++]) != 0)
1852                     if (solv->decisionmap[p] >= 0)
1853                       queue_push(dq, p);
1854                   if (dq->count && solv->update_targets && solv->update_targets->elements[i - installed->start])
1855                     prune_to_update_targets(solv, solv->update_targets->elements + solv->update_targets->elements[i - installed->start], dq);
1856                   if (dq->count)
1857                     {
1858                       policy_filter_unwanted(solv, dq, POLICY_MODE_CHOOSE);
1859                       p = dq->elements[0];
1860                       if (p != i && solv->decisionmap[p] == 0)
1861                         {
1862                           rr = solv->rules + solv->featurerules + (i - solv->installed->start);
1863                           if (!rr->p)           /* update rule == feature rule? */
1864                             rr = rr - solv->featurerules + solv->updaterules;
1865                           dq->count = 1;
1866                         }
1867                       else
1868                         dq->count = 0;
1869                     }
1870                 }
1871               else
1872                 {
1873                   /* update to best package of the update rule */
1874                   FOR_RULELITERALS(p, pp, rr)
1875                     {
1876                       if (solv->decisionmap[p] > 0)
1877                         {
1878                           dq->count = 0;                /* already fulfilled */
1879                           break;
1880                         }
1881                       if (!solv->decisionmap[p])
1882                         queue_push(dq, p);
1883                     }
1884                 }
1885             }
1886           if (dq->count && solv->update_targets && solv->update_targets->elements[i - installed->start])
1887             prune_to_update_targets(solv, solv->update_targets->elements + solv->update_targets->elements[i - installed->start], dq);
1888           /* install best version */
1889           if (dq->count)
1890             {
1891               olevel = level;
1892               level = selectandinstall(solv, level, dq, disablerules, rr - solv->rules, SOLVER_REASON_UPDATE_INSTALLED);
1893               if (level <= olevel)
1894                 {
1895                   if (level < passlevel)
1896                     break;      /* trouble */
1897                   if (level < olevel)
1898                     n = installed->start;       /* redo all */
1899                   i--;
1900                   n--;
1901                   continue;
1902                 }
1903             }
1904           /* if still undecided keep package */
1905           if (solv->decisionmap[i] == 0)
1906             {
1907               olevel = level;
1908               if (solv->cleandepsmap.size && MAPTST(&solv->cleandepsmap, i - installed->start))
1909                 {
1910 #if 0
1911                   POOL_DEBUG(SOLV_DEBUG_POLICY, "cleandeps erasing %s\n", pool_solvid2str(pool, i));
1912                   level = setpropagatelearn(solv, level, -i, disablerules, 0, SOLVER_REASON_CLEANDEPS_ERASE);
1913 #else
1914                   continue;
1915 #endif
1916                 }
1917               else
1918                 {
1919                   POOL_DEBUG(SOLV_DEBUG_POLICY, "keeping %s\n", pool_solvid2str(pool, i));
1920                   level = setpropagatelearn(solv, level, i, disablerules, r - solv->rules, SOLVER_REASON_KEEP_INSTALLED);
1921                 }
1922               if (level <= olevel)
1923                 {
1924                   if (level < passlevel)
1925                     break;      /* trouble */
1926                   if (level < olevel)
1927                     n = installed->start;       /* redo all */
1928                   i--;
1929                   n--;
1930                   continue;     /* retry with learnt rule */
1931                 }
1932             }
1933         }
1934       if (n < installed->end)
1935         {
1936           installedpos = i;     /* retry problem solvable next time */
1937           if (level < origlevel)
1938             break;              /* ran into trouble */
1939           /* re-run all passes */
1940           pass = solv->updatemap.size ? 0 : 1;
1941           continue;
1942         }
1943       /* reset installedpos, advance to next pass */
1944       installedpos = installed->start;
1945       pass++;
1946     }
1947   solv->installedpos = installedpos;
1948   return level;
1949 }
1950
1951 static int
1952 resolve_dependencies(Solver *solv, int level, int disablerules, Queue *dq)
1953 {
1954   Pool *pool = solv->pool;
1955   int i, j, n;
1956   int postponed;
1957   Rule *r;
1958   int origlevel = level;
1959   Id p, *dp;
1960
1961   /*
1962    * decide
1963    */
1964   POOL_DEBUG(SOLV_DEBUG_POLICY, "deciding unresolved rules\n");
1965   postponed = 0;
1966   for (i = 1, n = 1; ; i++, n++)
1967     {
1968       if (n >= solv->nrules)
1969         {
1970           if (postponed <= 0)
1971             break;
1972           i = postponed;
1973           postponed = -1;
1974           n = 1;
1975         }
1976       if (i == solv->nrules)
1977         i = 1;
1978       r = solv->rules + i;
1979       if (r->d < 0)             /* ignore disabled rules */
1980         continue;
1981       if (r->p < 0)             /* most common cases first */
1982         {
1983           if (r->d == 0 || solv->decisionmap[-r->p] <= 0)
1984             continue;
1985         }
1986       if (dq->count)
1987         queue_empty(dq);
1988       if (r->d == 0)
1989         {
1990           /* binary or unary rule */
1991           /* need two positive undecided literals, r->p already checked above */
1992           if (r->w2 <= 0)
1993             continue;
1994           if (solv->decisionmap[r->p] || solv->decisionmap[r->w2])
1995             continue;
1996           queue_push(dq, r->p);
1997           queue_push(dq, r->w2);
1998         }
1999       else
2000         {
2001           /* make sure that
2002            * all negative literals are installed
2003            * no positive literal is installed
2004            * i.e. the rule is not fulfilled and we
2005            * just need to decide on the positive literals
2006            * (decisionmap[-r->p] for the r->p < 0 case is already checked above)
2007            */
2008           if (r->p >= 0)
2009             {
2010               if (solv->decisionmap[r->p] > 0)
2011                 continue;
2012               if (solv->decisionmap[r->p] == 0)
2013                 queue_push(dq, r->p);
2014             }
2015           dp = pool->whatprovidesdata + r->d;
2016           while ((p = *dp++) != 0)
2017             {
2018               if (p < 0)
2019                 {
2020                   if (solv->decisionmap[-p] <= 0)
2021                     break;
2022                 }
2023               else
2024                 {
2025                   if (solv->decisionmap[p] > 0)
2026                     break;
2027                   if (solv->decisionmap[p] == 0)
2028                     queue_push(dq, p);
2029                 }
2030             }
2031           if (p)
2032             continue;
2033         }
2034       IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
2035         {
2036           POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "unfulfilled ");
2037           solver_printruleclass(solv, SOLV_DEBUG_PROPAGATE, r);
2038         }
2039       /* dq->count < 2 cannot happen as this means that
2040        * the rule is unit */
2041       assert(dq->count > 1);
2042
2043       /* prune to cleandeps packages */
2044       if (solv->cleandepsmap.size && solv->installed)
2045         {
2046           Repo *installed = solv->installed;
2047           for (j = 0; j < dq->count; j++)
2048             if (pool->solvables[dq->elements[j]].repo == installed && MAPTST(&solv->cleandepsmap, dq->elements[j] - installed->start))
2049               break;
2050           if (j < dq->count)
2051             {
2052               dq->elements[0] = dq->elements[j];
2053               queue_truncate(dq, 1);
2054             }
2055         }
2056
2057       if (dq->count > 1 && postponed >= 0)
2058         {
2059           policy_filter_unwanted(solv, dq, POLICY_MODE_CHOOSE_NOREORDER);
2060           if (dq->count > 1)
2061             {
2062               if (!postponed)
2063                 postponed = i;
2064               continue;
2065             }
2066         }
2067
2068       level = selectandinstall(solv, level, dq, disablerules, r - solv->rules, SOLVER_REASON_RESOLVE);
2069       if (level < origlevel)
2070         break;          /* trouble */
2071       /* something changed, so look at all rules again */
2072       n = 0;
2073     }
2074   return level;
2075 }
2076
2077
2078 #ifdef ENABLE_COMPLEX_DEPS
2079
2080 static void
2081 add_complex_recommends(Solver *solv, Id rec, Queue *dq, Map *dqmap)
2082 {
2083   Pool *pool = solv->pool;
2084   int oldcnt = dq->count;
2085   int cutcnt, blkcnt;
2086   Id p;
2087   int i, j;
2088
2089 #if 0
2090   printf("ADD_COMPLEX_RECOMMENDS %s\n", pool_dep2str(pool, rec));
2091 #endif
2092   i = pool_normalize_complex_dep(pool, rec, dq, CPLXDEPS_EXPAND);
2093   if (i == 0 || i == 1)
2094     return;
2095   cutcnt = dq->count;
2096   for (i = oldcnt; i < cutcnt; i++)
2097     {
2098       blkcnt = dq->count;
2099       for (; (p = dq->elements[i]) != 0; i++)
2100         {
2101           if (p < 0)
2102             {
2103               if (solv->decisionmap[-p] <= 0)
2104                 break;
2105               continue;
2106             }
2107           if (solv->decisionmap[p] > 0)
2108             {
2109               queue_truncate(dq, blkcnt);
2110               break;
2111             }
2112           if (dqmap)
2113             {
2114               if (!MAPTST(dqmap, p))
2115                 continue;
2116             }
2117           else
2118             {
2119               if (solv->decisionmap[p] < 0)
2120                 continue;
2121               if (solv->process_orphans && solv->installed && pool->solvables[p].repo == solv->installed && (solv->droporphanedmap_all || (solv->droporphanedmap.size && MAPTST(&solv->droporphanedmap, p - solv->installed->start))))
2122                 continue;
2123             }
2124           queue_push(dq, p);
2125         }
2126       while (dq->elements[i])
2127         i++;
2128     }
2129   queue_deleten(dq, oldcnt, cutcnt - oldcnt);
2130   /* unify */
2131   if (dq->count != oldcnt)
2132     {
2133       for (j = oldcnt; j < dq->count; j++)
2134         {
2135           p = dq->elements[j];
2136           for (i = 0; i < j; i++)
2137             if (dq->elements[i] == p)
2138               {
2139                 dq->elements[j] = 0;
2140                 break;
2141               }
2142         }
2143       for (i = j = oldcnt; j < dq->count; j++)
2144         if (dq->elements[j])
2145           dq->elements[i++] = dq->elements[j];
2146       queue_truncate(dq, i);
2147     }
2148 #if 0
2149   printf("RETURN:\n");
2150   for (i = oldcnt; i < dq->count; i++)
2151     printf("  - %s\n", pool_solvid2str(pool, dq->elements[i]));
2152 #endif
2153 }
2154
2155 static void
2156 do_complex_recommendations(Solver *solv, Id rec, Map *m, int noselected)
2157 {
2158   Pool *pool = solv->pool;
2159   Queue dq;
2160   Id p;
2161   int i, blk;
2162
2163 #if 0
2164   printf("DO_COMPLEX_RECOMMENDATIONS %s\n", pool_dep2str(pool, rec));
2165 #endif
2166   queue_init(&dq);
2167   i = pool_normalize_complex_dep(pool, rec, &dq, CPLXDEPS_EXPAND);
2168   if (i == 0 || i == 1)
2169     {
2170       queue_free(&dq);
2171       return;
2172     }
2173   for (i = 0; i < dq.count; i++)
2174     {
2175       blk = i;
2176       for (; (p = dq.elements[i]) != 0; i++)
2177         {
2178           if (p < 0)
2179             {
2180               if (solv->decisionmap[-p] <= 0)
2181                 break;
2182               continue;
2183             }
2184           if (solv->decisionmap[p] > 0)
2185             {
2186               if (noselected)
2187                 break;
2188               MAPSET(m, p);
2189               for (i++; (p = dq.elements[i]) != 0; i++)
2190                 if (p > 0 && solv->decisionmap[p] > 0)
2191                   MAPSET(m, p);
2192               p = 1;
2193               break;
2194             }
2195         }
2196       if (!p)
2197         {
2198           for (i = blk; (p = dq.elements[i]) != 0; i++)
2199             if (p > 0)
2200               MAPSET(m, p);
2201         }
2202       while (dq.elements[i])
2203         i++;
2204     }
2205   queue_free(&dq);
2206 }
2207
2208 #endif
2209
2210 static void
2211 prune_disfavored(Solver *solv, Queue *plist)
2212 {
2213   int i, j;
2214   if (!solv->isdisfavormap.size)
2215     return;
2216   for (i = j = 0; i < plist->count; i++)
2217     {
2218       Id p = plist->elements[i];
2219       if (!MAPTST(&solv->isdisfavormap, p))
2220         plist->elements[j++] = p;
2221     }
2222   if (i != j)
2223     queue_truncate(plist, j);
2224 }
2225
2226 static int
2227 resolve_weak(Solver *solv, int level, int disablerules, Queue *dq, Queue *dqs, int *rerunp)
2228 {
2229   Pool *pool = solv->pool;
2230   int i, j, qcount;
2231   int olevel;
2232   Solvable *s;
2233   Map dqmap;
2234   int decisioncount;
2235   Id p;
2236
2237   POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended packages\n");
2238   if (dq->count)
2239     queue_empty(dq);    /* recommended packages */
2240   if (dqs->count)
2241     queue_empty(dqs);   /* supplemented packages */
2242   for (i = 1; i < pool->nsolvables; i++)
2243     {
2244       if (solv->decisionmap[i] < 0)
2245         continue;
2246       s = pool->solvables + i;
2247       if (solv->decisionmap[i] > 0)
2248         {
2249           /* installed, check for recommends */
2250           Id *recp, rec, pp, p;
2251           if (!solv->addalreadyrecommended && s->repo == solv->installed)
2252             continue;
2253           /* XXX need to special case AND ? */
2254           if (s->recommends)
2255             {
2256               recp = s->repo->idarraydata + s->recommends;
2257               while ((rec = *recp++) != 0)
2258                 {
2259 #ifdef ENABLE_COMPLEX_DEPS
2260                   if (pool_is_complex_dep(pool, rec))
2261                     {
2262                       add_complex_recommends(solv, rec, dq, 0);
2263                       continue;
2264                     }
2265 #endif
2266                   qcount = dq->count;
2267                   FOR_PROVIDES(p, pp, rec)
2268                     {
2269                       if (solv->decisionmap[p] > 0)
2270                         {
2271                           dq->count = qcount;
2272                           break;
2273                         }
2274                       else if (solv->decisionmap[p] == 0)
2275                         {
2276                           if (solv->process_orphans && solv->installed && pool->solvables[p].repo == solv->installed && (solv->droporphanedmap_all || (solv->droporphanedmap.size && MAPTST(&solv->droporphanedmap, p - solv->installed->start))))
2277                             continue;
2278                           queue_pushunique(dq, p);
2279                         }
2280                     }
2281                 }
2282             }
2283         }
2284       else
2285         {
2286           /* not yet installed, check if supplemented */
2287           if (!s->supplements)
2288             continue;
2289           if (!pool_installable(pool, s))
2290             continue;
2291           if (!solver_is_supplementing(solv, s))
2292             continue;
2293           if (solv->process_orphans && solv->installed && s->repo == solv->installed && (solv->droporphanedmap_all || (solv->droporphanedmap.size && MAPTST(&solv->droporphanedmap, i - solv->installed->start))))
2294             continue;
2295           if (solv->isdisfavormap.size && MAPTST(&solv->isdisfavormap, i))
2296             continue;   /* disfavored supplements, do not install */
2297           queue_push(dqs, i);
2298         }
2299     }
2300
2301   /* filter out disfavored recommended packages */
2302   if (dq->count && solv->isdisfavormap.size)
2303     prune_disfavored(solv, dq);
2304
2305   /* filter out all packages obsoleted by installed packages */
2306   /* this is no longer needed if we have (and trust) reverse obsoletes */
2307   if ((dqs->count || dq->count) && solv->installed)
2308     {
2309       Map obsmap;
2310       Id obs, *obsp, po, ppo;
2311
2312       map_init(&obsmap, pool->nsolvables);
2313       for (p = solv->installed->start; p < solv->installed->end; p++)
2314         {
2315           s = pool->solvables + p;
2316           if (s->repo != solv->installed || !s->obsoletes)
2317             continue;
2318           if (solv->decisionmap[p] <= 0)
2319             continue;
2320           if (!solv->keepexplicitobsoletes && solv->multiversion.size && MAPTST(&solv->multiversion, p))
2321             continue;
2322           obsp = s->repo->idarraydata + s->obsoletes;
2323           /* foreach obsoletes */
2324           while ((obs = *obsp++) != 0)
2325             FOR_PROVIDES(po, ppo, obs)
2326               {
2327                 Solvable *pos = pool->solvables + po;
2328                 if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, pos, obs))
2329                   continue;
2330                 if (pool->obsoleteusescolors && !pool_colormatch(pool, s, pos))
2331                   continue;
2332                 MAPSET(&obsmap, po);
2333               }
2334         }
2335       for (i = j = 0; i < dqs->count; i++)
2336         if (!MAPTST(&obsmap, dqs->elements[i]))
2337           dqs->elements[j++] = dqs->elements[i];
2338       dqs->count = j;
2339       for (i = j = 0; i < dq->count; i++)
2340         if (!MAPTST(&obsmap, dq->elements[i]))
2341           dq->elements[j++] = dq->elements[i];
2342       dq->count = j;
2343       map_free(&obsmap);
2344     }
2345
2346   /* filter out all already supplemented packages if requested */
2347   if (!solv->addalreadyrecommended && dqs->count)
2348     {
2349       /* filter out old supplements */
2350       for (i = j = 0; i < dqs->count; i++)
2351         {
2352           p = dqs->elements[i];
2353           s = pool->solvables + p;
2354           if (s->supplements && solver_is_supplementing_alreadyinstalled(solv, s))
2355             dqs->elements[j++] = p;
2356         }
2357       dqs->count = j;
2358     }
2359
2360   /* multiversion doesn't mix well with supplements.
2361    * filter supplemented packages where we already decided
2362    * to install a different version (see bnc#501088) */
2363   if (dqs->count && solv->multiversion.size)
2364     {
2365       for (i = j = 0; i < dqs->count; i++)
2366         {
2367           p = dqs->elements[i];
2368           if (MAPTST(&solv->multiversion, p))
2369             {
2370               Id p2, pp2;
2371               s = pool->solvables + p;
2372               FOR_PROVIDES(p2, pp2, s->name)
2373                 if (solv->decisionmap[p2] > 0 && pool->solvables[p2].name == s->name)
2374                   break;
2375               if (p2)
2376                 continue;       /* ignore this package */
2377             }
2378           dqs->elements[j++] = p;
2379         }
2380       dqs->count = j;
2381     }
2382
2383   /* implicitobsoleteusescolors doesn't mix well with supplements.
2384    * filter supplemented packages where we already decided
2385    * to install a different architecture */
2386   if (dqs->count && pool->implicitobsoleteusescolors)
2387     {
2388       for (i = j = 0; i < dqs->count; i++)
2389         {
2390           Id p2, pp2;
2391           p = dqs->elements[i];
2392           s = pool->solvables + p;
2393           FOR_PROVIDES(p2, pp2, s->name)
2394             if (solv->decisionmap[p2] > 0 && pool->solvables[p2].name == s->name && pool->solvables[p2].arch != s->arch)
2395               break;
2396           if (p2)
2397             continue;   /* ignore this package */
2398           dqs->elements[j++] = p;
2399         }
2400       dqs->count = j;
2401     }
2402
2403   /* make dq contain both recommended and supplemented pkgs */
2404   if (dqs->count)
2405     {
2406       for (i = 0; i < dqs->count; i++)
2407         queue_pushunique(dq, dqs->elements[i]);
2408     }
2409
2410   if (!dq->count)
2411     return level;
2412   *rerunp = 1;
2413
2414   if (dq->count == 1)
2415     {
2416       /* simple case, just one package. no need to choose to best version */
2417       p = dq->elements[0];
2418       if (dqs->count)
2419         POOL_DEBUG(SOLV_DEBUG_POLICY, "installing supplemented %s\n", pool_solvid2str(pool, p));
2420       else
2421         POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended %s\n", pool_solvid2str(pool, p));
2422       return setpropagatelearn(solv, level, p, 0, 0, SOLVER_REASON_WEAKDEP);
2423     }
2424
2425   /* filter packages, this gives us the best versions */
2426   policy_filter_unwanted(solv, dq, POLICY_MODE_RECOMMEND);
2427
2428   /* create map of result */
2429   map_init(&dqmap, pool->nsolvables);
2430   for (i = 0; i < dq->count; i++)
2431     MAPSET(&dqmap, dq->elements[i]);
2432
2433   /* prune dqs so that it only contains the best versions */
2434   for (i = j = 0; i < dqs->count; i++)
2435     {
2436       p = dqs->elements[i];
2437       if (MAPTST(&dqmap, p))
2438         dqs->elements[j++] = p;
2439     }
2440   dqs->count = j;
2441
2442   /* install all supplemented packages, but order first */
2443   if (dqs->count > 1)
2444     policy_filter_unwanted(solv, dqs, POLICY_MODE_SUPPLEMENT);
2445   decisioncount = solv->decisionq.count;
2446   for (i = 0; i < dqs->count; i++)
2447     {
2448       p = dqs->elements[i];
2449       if (solv->decisionmap[p])
2450         continue;
2451       POOL_DEBUG(SOLV_DEBUG_POLICY, "installing supplemented %s\n", pool_solvid2str(pool, p));
2452       olevel = level;
2453       level = setpropagatelearn(solv, level, p, 0, 0, SOLVER_REASON_WEAKDEP);
2454       if (level <= olevel)
2455         break;
2456     }
2457   if (i < dqs->count || solv->decisionq.count < decisioncount)
2458     {
2459       map_free(&dqmap);
2460       return level;
2461     }
2462
2463   /* install all recommended packages */
2464   /* more work as we want to created branches if multiple
2465    * choices are valid */
2466   for (i = 0; i < decisioncount; i++)
2467     {
2468       Id rec, *recp, pp;
2469       p = solv->decisionq.elements[i];
2470       if (p < 0)
2471         continue;
2472       s = pool->solvables + p;
2473       if (!s->repo || (!solv->addalreadyrecommended && s->repo == solv->installed))
2474         continue;
2475       if (!s->recommends)
2476         continue;
2477       recp = s->repo->idarraydata + s->recommends;
2478       while ((rec = *recp++) != 0)
2479         {
2480           queue_empty(dq);
2481 #ifdef ENABLE_COMPLEX_DEPS
2482           if (pool_is_complex_dep(pool, rec))
2483               add_complex_recommends(solv, rec, dq, &dqmap);
2484           else
2485 #endif
2486           FOR_PROVIDES(p, pp, rec)
2487             {
2488               if (solv->decisionmap[p] > 0)
2489                 {
2490                   dq->count = 0;
2491                   break;
2492                 }
2493               else if (solv->decisionmap[p] == 0 && MAPTST(&dqmap, p))
2494                 queue_push(dq, p);
2495             }
2496           if (!dq->count)
2497             continue;
2498           if (dq->count > 1)
2499             policy_filter_unwanted(solv, dq, POLICY_MODE_CHOOSE);
2500           /* if we have multiple candidates we open a branch */
2501           if (dq->count > 1)
2502               createbranch(solv, level, dq, s - pool->solvables, rec);
2503           p = dq->elements[0];
2504           POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended %s\n", pool_solvid2str(pool, p));
2505           olevel = level;
2506           level = setpropagatelearn(solv, level, p, 0, 0, SOLVER_REASON_WEAKDEP);
2507           if (level <= olevel || solv->decisionq.count < decisioncount)
2508             break;      /* we had to revert some decisions */
2509         }
2510       if (rec)
2511         break;  /* had a problem above, quit loop */
2512     }
2513   map_free(&dqmap);
2514   return level;
2515 }
2516
2517 static int
2518 resolve_cleandeps(Solver *solv, int level, int disablerules, int *rerunp)
2519 {
2520   Pool *pool = solv->pool;
2521   Repo *installed = solv->installed;
2522   int olevel;
2523   Id p;
2524   Solvable *s;
2525
2526   if (!installed || !solv->cleandepsmap.size)
2527     return level;
2528   POOL_DEBUG(SOLV_DEBUG_SOLVER, "deciding cleandeps packages\n");
2529   for (p = installed->start; p < installed->end; p++)
2530     {
2531       s = pool->solvables + p;
2532       if (s->repo != installed)
2533         continue;
2534       if (solv->decisionmap[p] != 0 || !MAPTST(&solv->cleandepsmap, p - installed->start))
2535         continue;
2536       POOL_DEBUG(SOLV_DEBUG_POLICY, "cleandeps erasing %s\n", pool_solvid2str(pool, p));
2537       olevel = level;
2538       level = setpropagatelearn(solv, level, -p, 0, 0, SOLVER_REASON_CLEANDEPS_ERASE);
2539       if (level < olevel)
2540         break;
2541     }
2542   if (p < installed->end)
2543     *rerunp = 1;
2544   return level;
2545 }
2546
2547 static int
2548 resolve_orphaned(Solver *solv, int level, int disablerules, Queue *dq, int *rerunp)
2549 {
2550   Pool *pool = solv->pool;
2551   int i;
2552   Id p;
2553   int installedone = 0;
2554   int olevel;
2555
2556   /* let's see if we can install some unsupported package */
2557   POOL_DEBUG(SOLV_DEBUG_SOLVER, "deciding orphaned packages\n");
2558   for (i = 0; i < solv->orphaned.count; i++)
2559     {
2560       p = solv->orphaned.elements[i];
2561       if (solv->decisionmap[p])
2562         continue;       /* already decided */
2563       if (solv->droporphanedmap_all)
2564         continue;
2565       if (solv->droporphanedmap.size && MAPTST(&solv->droporphanedmap, p - solv->installed->start))
2566         continue;
2567       POOL_DEBUG(SOLV_DEBUG_SOLVER, "keeping orphaned %s\n", pool_solvid2str(pool, p));
2568       olevel = level;
2569       level = setpropagatelearn(solv, level, p, 0, 0, SOLVER_REASON_RESOLVE_ORPHAN);
2570       installedone = 1;
2571       if (level < olevel)
2572         break;
2573     }
2574   if (installedone || i < solv->orphaned.count)
2575     {
2576       *rerunp = 1;
2577       return level;
2578     }
2579   for (i = 0; i < solv->orphaned.count; i++)
2580     {
2581       p = solv->orphaned.elements[i];
2582       if (solv->decisionmap[p])
2583         continue;       /* already decided */
2584       POOL_DEBUG(SOLV_DEBUG_SOLVER, "removing orphaned %s\n", pool_solvid2str(pool, p));
2585       olevel = level;
2586       level = setpropagatelearn(solv, level, -p, 0, 0, SOLVER_REASON_RESOLVE_ORPHAN);
2587       if (level < olevel)
2588         {
2589           *rerunp = 1;
2590           return level;
2591         }
2592     }
2593   if (solv->brokenorphanrules)
2594     {
2595       solver_check_brokenorphanrules(solv, dq);
2596       if (dq->count)
2597         {
2598           policy_filter_unwanted(solv, dq, POLICY_MODE_CHOOSE);
2599           for (i = 0; i < dq->count; i++)
2600             {
2601               p = dq->elements[i];
2602               POOL_DEBUG(SOLV_DEBUG_POLICY, "installing orphaned dep %s\n", pool_solvid2str(pool, p));
2603               olevel = level;
2604               level = setpropagatelearn(solv, level, p, 0, 0, SOLVER_REASON_RESOLVE_ORPHAN);
2605               if (level < olevel)
2606                 break;
2607             }
2608           *rerunp = 1;
2609         }
2610     }
2611   return level;
2612 }
2613
2614 /*-------------------------------------------------------------------
2615  *
2616  * solver_run_sat
2617  *
2618  * all rules have been set up, now actually run the solver
2619  *
2620  */
2621
2622 void
2623 solver_run_sat(Solver *solv, int disablerules, int doweak)
2624 {
2625   Queue dq;             /* local decisionqueue */
2626   Queue dqs;            /* local decisionqueue for supplements */
2627   int systemlevel;
2628   int level, olevel;
2629   Rule *r;
2630   int i;
2631   Solvable *s;
2632   Pool *pool = solv->pool;
2633   Id p;
2634   int minimizationsteps;
2635
2636   IF_POOLDEBUG (SOLV_DEBUG_RULE_CREATION)
2637     {
2638       POOL_DEBUG (SOLV_DEBUG_RULE_CREATION, "number of rules: %d\n", solv->nrules);
2639       for (i = 1; i < solv->nrules; i++)
2640         solver_printruleclass(solv, SOLV_DEBUG_RULE_CREATION, solv->rules + i);
2641     }
2642
2643   /* start SAT algorithm */
2644   level = 0;
2645   systemlevel = level + 1;
2646   POOL_DEBUG(SOLV_DEBUG_SOLVER, "solving...\n");
2647
2648   queue_init(&dq);
2649   queue_init(&dqs);
2650   solv->installedpos = 0;
2651   solv->do_extra_reordering = 0;
2652
2653   /*
2654    * here's the main loop:
2655    * 1) decide assertion rules and propagate
2656    * 2) fulfill jobs
2657    * 3) try to keep installed packages
2658    * 4) fulfill all unresolved rules
2659    * 5) install recommended packages
2660    * 6) minimalize solution if we had choices
2661    * if we encounter a problem, we rewind to a safe level and restart
2662    * with step 1
2663    */
2664
2665   minimizationsteps = 0;
2666   for (;;)
2667     {
2668       /*
2669        * initial propagation of the assertions
2670        */
2671       if (level <= 0)
2672         {
2673           if (level < 0)
2674             break;
2675           makeruledecisions(solv);
2676           level = 1;
2677           if (!disablerules && solv->problems.count)
2678             {
2679               level = -1;
2680               break;
2681             }
2682           POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "initial propagate (propagate_index: %d;  size decisionq: %d)...\n", solv->propagate_index, solv->decisionq.count);
2683           if ((r = propagate(solv, level)) != 0)
2684             {
2685               level = analyze_unsolvable(solv, r, disablerules);
2686               continue;
2687             }
2688           systemlevel = level + 1;
2689         }
2690
2691       /*
2692        * resolve jobs first (unless focus_installed is set)
2693        */
2694      if (level < systemlevel && !solv->focus_installed)
2695         {
2696           if (solv->installed && solv->installed->nsolvables && !solv->installed->disabled)
2697             solv->do_extra_reordering = 1;
2698           olevel = level;
2699           level = resolve_jobrules(solv, level, disablerules, &dq);
2700           solv->do_extra_reordering = 0;
2701           if (level < olevel)
2702             continue;
2703           systemlevel = level + 1;
2704         }
2705
2706       /* resolve job dependencies in the focus_best case */
2707       if (level < systemlevel && solv->focus_best && !solv->focus_installed && solv->installed && solv->installed->nsolvables && !solv->installed->disabled)
2708         {
2709           solv->do_extra_reordering = 1;
2710           olevel = level;
2711           level = resolve_dependencies(solv, level, disablerules, &dq);
2712           solv->do_extra_reordering = 0;
2713           if (level < olevel)
2714             continue;           /* start over */
2715           systemlevel = level + 1;
2716         }
2717
2718       /*
2719        * installed packages
2720        */
2721       if (level < systemlevel && solv->installed && solv->installed->nsolvables && !solv->installed->disabled)
2722         {
2723           olevel = level;
2724           level = resolve_installed(solv, level, disablerules, &dq);
2725           if (level < olevel)
2726             continue;
2727           systemlevel = level + 1;
2728         }
2729
2730      /* resolve jobs in focus_installed case */
2731      if (level < systemlevel && solv->focus_installed)
2732         {
2733           olevel = level;
2734           level = resolve_jobrules(solv, level, disablerules, &dq);
2735           if (level < olevel)
2736             continue;
2737           systemlevel = level + 1;
2738         }
2739
2740       if (level < systemlevel)
2741         systemlevel = level;
2742
2743       /* resolve all dependencies */
2744       olevel = level;
2745       level = resolve_dependencies(solv, level, disablerules, &dq);
2746       if (level < olevel)
2747         continue;               /* start over */
2748
2749       /* decide leftover cleandeps packages */
2750       if (solv->cleandepsmap.size && solv->installed)
2751         {
2752           int rerun = 0;
2753           level = resolve_cleandeps(solv, level, disablerules, &rerun);
2754           if (rerun)
2755             continue;
2756         }
2757
2758       /* at this point we have a consistent system. now do the extras... */
2759
2760       if (doweak)
2761         {
2762           int rerun = 0;
2763           level = resolve_weak(solv, level, disablerules, &dq, &dqs, &rerun);
2764           if (rerun)
2765             continue;
2766         }
2767
2768       if (solv->installed && (solv->orphaned.count || solv->brokenorphanrules))
2769         {
2770           int rerun = 0;
2771           level = resolve_orphaned(solv, level, disablerules, &dq, &rerun);
2772           if (rerun)
2773             continue;
2774         }
2775
2776      /* one final pass to make sure we decided all installed packages */
2777       if (solv->installed)
2778         {
2779           for (p = solv->installed->start; p < solv->installed->end; p++)
2780             {
2781               if (solv->decisionmap[p])
2782                 continue;       /* already decided */
2783               s = pool->solvables + p;
2784               if (s->repo != solv->installed)
2785                 continue;
2786               POOL_DEBUG(SOLV_DEBUG_SOLVER, "removing unwanted %s\n", pool_solvid2str(pool, p));
2787               olevel = level;
2788               level = setpropagatelearn(solv, level, -p, 0, 0, SOLVER_REASON_CLEANDEPS_ERASE);
2789               if (level < olevel)
2790                 break;
2791             }
2792           if (p < solv->installed->end)
2793             continue;           /* back to main loop */
2794         }
2795
2796       if (solv->installed && solv->cleandepsmap.size && solver_check_cleandeps_mistakes(solv))
2797         {
2798           solver_reset(solv);
2799           level = 0;    /* restart from scratch */
2800           continue;
2801         }
2802
2803       if (solv->solution_callback)
2804         {
2805           solv->solution_callback(solv, solv->solution_callback_data);
2806           if (solv->branches.count)
2807             {
2808               int l, endi = 0;
2809               p = l = 0;
2810               for (i = solv->branches.count - 1; i >= 0; i--)
2811                 {
2812                   p = solv->branches.elements[i];
2813                   if (p > 0 && !l)
2814                     {
2815                       endi = i + 1;
2816                       l = p;
2817                       i -= 3;   /* skip: p data count */
2818                     }
2819                   else if (p > 0)
2820                     break;
2821                   else if (p < 0)
2822                     l = 0;
2823                 }
2824               if (i >= 0)
2825                 {
2826                   while (i > 0 && solv->branches.elements[i - 1] > 0)
2827                     i--;
2828                   level = takebranch(solv, i, endi, "branching", disablerules);
2829                   continue;
2830                 }
2831             }
2832           /* all branches done, we're finally finished */
2833           break;
2834         }
2835
2836       /* auto-minimization step */
2837       if (solv->branches.count)
2838         {
2839           int endi, lasti = -1, lastiend = -1;
2840           if (solv->recommends_index < solv->decisionq.count)
2841             policy_update_recommendsmap(solv);
2842           for (endi = solv->branches.count; endi > 0;)
2843             {
2844               int l, lastsi = -1, starti = endi - solv->branches.elements[endi - 2];
2845               l = solv->branches.elements[endi - 1];
2846               for (i = starti; i < endi - 4; i++)
2847                 {
2848                   p = solv->branches.elements[i];
2849                   if (p <= 0)
2850                     continue;
2851                   if (solv->decisionmap[p] > l)
2852                     {
2853                       lasti = i;
2854                       lastiend = endi;
2855                       lastsi = -1;
2856                       break;
2857                     }
2858                   if (solv->isdisfavormap.size && MAPTST(&solv->isdisfavormap, p))
2859                     continue;
2860                   if (lastsi < 0 && (MAPTST(&solv->recommendsmap, p) || solver_is_supplementing(solv, pool->solvables + p)))
2861                     lastsi = i;
2862                 }
2863               if (lastsi >= 0)
2864                 {
2865                   /* we have a recommended package that could not be installed */
2866                   /* take it if our current selection is not recommended */
2867                   for (i = starti; i < endi - 4; i++)
2868                     {
2869                       p = -solv->branches.elements[i];
2870                       if (p <= 0 || solv->decisionmap[p] != l + 1)
2871                         continue;
2872                       if (solv->favormap.size && MAPTST(&solv->favormap, p))
2873                         if (!(solv->isdisfavormap.size && MAPTST(&solv->isdisfavormap, p)))
2874                           continue;     /* current selection is favored */
2875                       if (!(MAPTST(&solv->recommendsmap, p) || solver_is_supplementing(solv, pool->solvables + p)))
2876                         {
2877                           lasti = lastsi;
2878                           lastiend = endi;
2879                           break;
2880                         }
2881                     }
2882                 }
2883               endi = starti;
2884             }
2885           if (lasti >= 0)
2886             {
2887               minimizationsteps++;
2888               level = takebranch(solv, lasti, lastiend, "minimizing", disablerules);
2889               continue;         /* back to main loop */
2890             }
2891         }
2892       /* no minimization found, we're finally finished! */
2893       break;
2894     }
2895   assert(level == -1 || level + 1 == solv->decisionq_reason.count);
2896
2897   POOL_DEBUG(SOLV_DEBUG_STATS, "solver statistics: %d learned rules, %d unsolvable, %d minimization steps\n", solv->stats_learned, solv->stats_unsolvable, minimizationsteps);
2898
2899   POOL_DEBUG(SOLV_DEBUG_STATS, "done solving.\n\n");
2900   queue_free(&dq);
2901   queue_free(&dqs);
2902 #if 0
2903   solver_printdecisionq(solv, SOLV_DEBUG_RESULT);
2904 #endif
2905 }
2906
2907
2908 /*-------------------------------------------------------------------
2909  *
2910  * remove disabled conflicts
2911  *
2912  * purpose: update the decisionmap after some rules were disabled.
2913  * this is used to calculate the suggested/recommended package list.
2914  * Also returns a "removed" list to undo the discisionmap changes.
2915  */
2916
2917 static void
2918 removedisabledconflicts(Solver *solv, Queue *removed)
2919 {
2920   Pool *pool = solv->pool;
2921   int i, n;
2922   Id p, why, *dp;
2923   Id new;
2924   Rule *r;
2925   Id *decisionmap = solv->decisionmap;
2926
2927   queue_empty(removed);
2928   for (i = 0; i < solv->decisionq.count; i++)
2929     {
2930       p = solv->decisionq.elements[i];
2931       if (p > 0)
2932         continue;       /* conflicts only, please */
2933       why = solv->decisionq_why.elements[i];
2934       if (why == 0)
2935         {
2936           /* no rule involved, must be a orphan package drop */
2937           continue;
2938         }
2939       /* we never do conflicts on free decisions, so there
2940        * must have been an unit rule */
2941       assert(why > 0);
2942       r = solv->rules + why;
2943       if (r->d < 0 && decisionmap[-p])
2944         {
2945           /* rule is now disabled, remove from decisionmap */
2946           POOL_DEBUG(SOLV_DEBUG_SOLVER, "removing conflict for package %s[%d]\n", pool_solvid2str(pool, -p), -p);
2947           queue_push(removed, -p);
2948           queue_push(removed, decisionmap[-p]);
2949           decisionmap[-p] = 0;
2950         }
2951     }
2952   if (!removed->count)
2953     return;
2954   /* we removed some confliced packages. some of them might still
2955    * be in conflict, so search for unit rules and re-conflict */
2956   new = 0;
2957   for (i = n = 1, r = solv->rules + i; n < solv->nrules; i++, r++, n++)
2958     {
2959       if (i == solv->nrules)
2960         {
2961           i = 1;
2962           r = solv->rules + i;
2963         }
2964       if (r->d < 0)
2965         continue;
2966       if (!r->w2)
2967         {
2968           if (r->p < 0 && !decisionmap[-r->p])
2969             new = r->p;
2970         }
2971       else if (!r->d)
2972         {
2973           /* binary rule */
2974           if (r->p < 0 && decisionmap[-r->p] == 0 && DECISIONMAP_FALSE(r->w2))
2975             new = r->p;
2976           else if (r->w2 < 0 && decisionmap[-r->w2] == 0 && DECISIONMAP_FALSE(r->p))
2977             new = r->w2;
2978         }
2979       else
2980         {
2981           if (r->p < 0 && decisionmap[-r->p] == 0)
2982             new = r->p;
2983           if (new || DECISIONMAP_FALSE(r->p))
2984             {
2985               dp = pool->whatprovidesdata + r->d;
2986               while ((p = *dp++) != 0)
2987                 {
2988                   if (new && p == new)
2989                     continue;
2990                   if (p < 0 && decisionmap[-p] == 0)
2991                     {
2992                       if (new)
2993                         {
2994                           new = 0;
2995                           break;
2996                         }
2997                       new = p;
2998                     }
2999                   else if (!DECISIONMAP_FALSE(p))
3000                     {
3001                       new = 0;
3002                       break;
3003                     }
3004                 }
3005             }
3006         }
3007       if (new)
3008         {
3009           POOL_DEBUG(SOLV_DEBUG_SOLVER, "re-conflicting package %s[%d]\n", pool_solvid2str(pool, -new), -new);
3010           decisionmap[-new] = -1;
3011           new = 0;
3012           n = 0;        /* redo all rules */
3013         }
3014     }
3015 }
3016
3017 static inline void
3018 undo_removedisabledconflicts(Solver *solv, Queue *removed)
3019 {
3020   int i;
3021   for (i = 0; i < removed->count; i += 2)
3022     solv->decisionmap[removed->elements[i]] = removed->elements[i + 1];
3023 }
3024
3025
3026 /*-------------------------------------------------------------------
3027  *
3028  * weaken solvable dependencies
3029  */
3030
3031 static void
3032 weaken_solvable_deps(Solver *solv, Id p)
3033 {
3034   int i;
3035   Rule *r;
3036
3037   for (i = 1, r = solv->rules + i; i < solv->pkgrules_end; i++, r++)
3038     {
3039       if (r->p != -p)
3040         continue;
3041       if ((r->d == 0 || r->d == -1) && r->w2 < 0)
3042         continue;       /* conflict */
3043       queue_push(&solv->weakruleq, i);
3044     }
3045 }
3046
3047
3048 /********************************************************************/
3049 /* main() */
3050
3051
3052 void
3053 solver_calculate_multiversionmap(Pool *pool, Queue *job, Map *multiversionmap)
3054 {
3055   int i;
3056   Id how, what, select;
3057   Id p, pp;
3058   for (i = 0; i < job->count; i += 2)
3059     {
3060       how = job->elements[i];
3061       if ((how & SOLVER_JOBMASK) != SOLVER_MULTIVERSION)
3062         continue;
3063       what = job->elements[i + 1];
3064       select = how & SOLVER_SELECTMASK;
3065       if (!multiversionmap->size)
3066         map_grow(multiversionmap, pool->nsolvables);
3067       if (select == SOLVER_SOLVABLE_ALL)
3068         {
3069           FOR_POOL_SOLVABLES(p)
3070             MAPSET(multiversionmap, p);
3071         }
3072       else if (select == SOLVER_SOLVABLE_REPO)
3073         {
3074           Solvable *s;
3075           Repo *repo = pool_id2repo(pool, what);
3076           if (repo)
3077             {
3078               FOR_REPO_SOLVABLES(repo, p, s)
3079                 MAPSET(multiversionmap, p);
3080             }
3081         }
3082       FOR_JOB_SELECT(p, pp, select, what)
3083         MAPSET(multiversionmap, p);
3084     }
3085 }
3086
3087 void
3088 solver_calculate_noobsmap(Pool *pool, Queue *job, Map *multiversionmap)
3089 {
3090   solver_calculate_multiversionmap(pool, job, multiversionmap);
3091 }
3092
3093 /*
3094  * add a rule created by a job, record job number and weak flag
3095  */
3096 static inline void
3097 solver_addjobrule(Solver *solv, Id p, Id p2, Id d, Id job, int weak)
3098 {
3099   solver_addrule(solv, p, p2, d);
3100   queue_push(&solv->ruletojob, job);
3101   if (weak)
3102     queue_push(&solv->weakruleq, solv->nrules - 1);
3103 }
3104
3105 static inline void
3106 add_cleandeps_updatepkg(Solver *solv, Id p)
3107 {
3108   if (!solv->cleandeps_updatepkgs)
3109     {
3110       solv->cleandeps_updatepkgs = solv_calloc(1, sizeof(Queue));
3111       queue_init(solv->cleandeps_updatepkgs);
3112     }
3113   queue_pushunique(solv->cleandeps_updatepkgs, p);
3114 }
3115
3116 static void
3117 add_update_target(Solver *solv, Id p, Id how)
3118 {
3119   Pool *pool = solv->pool;
3120   Solvable *s = pool->solvables + p;
3121   Repo *installed = solv->installed;
3122   Id pi, pip;
3123   if (!solv->update_targets)
3124     {
3125       solv->update_targets = solv_calloc(1, sizeof(Queue));
3126       queue_init(solv->update_targets);
3127     }
3128   if (s->repo == installed)
3129     {
3130       queue_push2(solv->update_targets, p, p);
3131       return;
3132     }
3133   FOR_PROVIDES(pi, pip, s->name)
3134     {
3135       Solvable *si = pool->solvables + pi;
3136       if (si->repo != installed || si->name != s->name)
3137         continue;
3138       if (how & SOLVER_FORCEBEST)
3139         {
3140           if (!solv->bestupdatemap.size)
3141             map_grow(&solv->bestupdatemap, installed->end - installed->start);
3142           MAPSET(&solv->bestupdatemap, pi - installed->start);
3143         }
3144       if (how & SOLVER_CLEANDEPS)
3145         add_cleandeps_updatepkg(solv, pi);
3146       queue_push2(solv->update_targets, pi, p);
3147       /* check if it's ok to keep the installed package */
3148       if (s->evr == si->evr && solvable_identical(s, si))
3149         queue_push2(solv->update_targets, pi, pi);
3150     }
3151   if (s->obsoletes)
3152     {
3153       Id obs, *obsp = s->repo->idarraydata + s->obsoletes;
3154       while ((obs = *obsp++) != 0)
3155         {
3156           FOR_PROVIDES(pi, pip, obs)
3157             {
3158               Solvable *si = pool->solvables + pi;
3159               if (si->repo != installed)
3160                 continue;
3161               if (si->name == s->name)
3162                 continue;       /* already handled above */
3163               if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, si, obs))
3164                 continue;
3165               if (pool->obsoleteusescolors && !pool_colormatch(pool, s, si))
3166                 continue;
3167               if (how & SOLVER_FORCEBEST)
3168                 {
3169                   if (!solv->bestupdatemap.size)
3170                     map_grow(&solv->bestupdatemap, installed->end - installed->start);
3171                   MAPSET(&solv->bestupdatemap, pi - installed->start);
3172                 }
3173               if (how & SOLVER_CLEANDEPS)
3174                 add_cleandeps_updatepkg(solv, pi);
3175               queue_push2(solv->update_targets, pi, p);
3176             }
3177         }
3178     }
3179 }
3180
3181 static int
3182 transform_update_targets_sortfn(const void *ap, const void *bp, void *dp)
3183 {
3184   const Id *a = ap;
3185   const Id *b = bp;
3186   if (a[0] - b[0])
3187     return a[0] - b[0];
3188   return a[1] - b[1];
3189 }
3190
3191 static void
3192 transform_update_targets(Solver *solv)
3193 {
3194   Repo *installed = solv->installed;
3195   Queue *update_targets = solv->update_targets;
3196   int i, j;
3197   Id p, q, lastp, lastq;
3198
3199   if (!update_targets->count)
3200     {
3201       queue_free(update_targets);
3202       solv->update_targets = solv_free(update_targets);
3203       return;
3204     }
3205   if (update_targets->count > 2)
3206     solv_sort(update_targets->elements, update_targets->count >> 1, 2 * sizeof(Id), transform_update_targets_sortfn, solv);
3207   queue_insertn(update_targets, 0, installed->end - installed->start, 0);
3208   lastp = lastq = 0;
3209   for (i = j = installed->end - installed->start; i < update_targets->count; i += 2)
3210     {
3211       if ((p = update_targets->elements[i]) != lastp)
3212         {
3213           if (!solv->updatemap.size)
3214             map_grow(&solv->updatemap, installed->end - installed->start);
3215           MAPSET(&solv->updatemap, p - installed->start);
3216           update_targets->elements[j++] = 0;                    /* finish old set */
3217           update_targets->elements[p - installed->start] = j;   /* start new set */
3218           lastp = p;
3219           lastq = 0;
3220         }
3221       if ((q = update_targets->elements[i + 1]) != lastq)
3222         {
3223           update_targets->elements[j++] = q;
3224           lastq = q;
3225         }
3226     }
3227   queue_truncate(update_targets, j);
3228   queue_push(update_targets, 0);        /* finish last set */
3229 }
3230
3231
3232 static void
3233 addedmap2deduceq(Solver *solv, Map *addedmap)
3234 {
3235   Pool *pool = solv->pool;
3236   int i, j;
3237   Id p;
3238   Rule *r;
3239
3240   queue_empty(&solv->addedmap_deduceq);
3241   for (i = 2, j = solv->pkgrules_end - 1; i < pool->nsolvables && j > 0; j--)
3242     {
3243       r = solv->rules + j;
3244       if (r->p >= 0)
3245         continue;
3246       if ((r->d == 0 || r->d == -1) && r->w2 < 0)
3247         continue;
3248       p = -r->p;
3249       if (!MAPTST(addedmap, p))
3250         {
3251           /* should never happen, but... */
3252           if (!solv->addedmap_deduceq.count || solv->addedmap_deduceq.elements[solv->addedmap_deduceq.count - 1] != -p)
3253             queue_push(&solv->addedmap_deduceq, -p);
3254           continue;
3255         }
3256       for (; i < p; i++)
3257         if (MAPTST(addedmap, i))
3258           queue_push(&solv->addedmap_deduceq, i);
3259       if (i == p)
3260         i++;
3261     }
3262   for (; i < pool->nsolvables; i++)
3263     if (MAPTST(addedmap, i))
3264       queue_push(&solv->addedmap_deduceq, i);
3265   j = 0;
3266   for (i = 2; i < pool->nsolvables; i++)
3267     if (MAPTST(addedmap, i))
3268       j++;
3269 }
3270
3271 static void
3272 deduceq2addedmap(Solver *solv, Map *addedmap)
3273 {
3274   int j;
3275   Id p;
3276   Rule *r;
3277   for (j = solv->pkgrules_end - 1; j > 0; j--)
3278     {
3279       r = solv->rules + j;
3280       if (r->d < 0 && r->p)
3281         solver_enablerule(solv, r);
3282       if (r->p >= 0)
3283         continue;
3284       if ((r->d == 0 || r->d == -1) && r->w2 < 0)
3285         continue;
3286       p = -r->p;
3287       MAPSET(addedmap, p);
3288     }
3289   for (j = 0; j < solv->addedmap_deduceq.count; j++)
3290     {
3291       p = solv->addedmap_deduceq.elements[j];
3292       if (p > 0)
3293         MAPSET(addedmap, p);
3294       else
3295         MAPCLR(addedmap, p);
3296     }
3297 }
3298
3299 #ifdef ENABLE_COMPLEX_DEPS
3300 static int
3301 add_complex_jobrules(Solver *solv, Id dep, int flags, int jobidx, int weak)
3302 {
3303   Pool *pool = solv->pool;
3304   Queue bq;
3305   int i, j;
3306
3307   queue_init(&bq);
3308   i = pool_normalize_complex_dep(pool, dep, &bq, flags | CPLXDEPS_EXPAND);
3309   if (i == 0 || i == 1)
3310     {
3311       queue_free(&bq);
3312       if (i == 0)
3313         solver_addjobrule(solv, -SYSTEMSOLVABLE, 0, 0, jobidx, weak);
3314       return 0;
3315     }
3316   for (i = 0; i < bq.count; i++)
3317     {
3318       if (!bq.elements[i])
3319         continue;
3320       for (j = 0; bq.elements[i + j + 1]; j++)
3321         ;
3322       if (j > 1)
3323         solver_addjobrule(solv, bq.elements[i], 0, pool_ids2whatprovides(pool, bq.elements + i + 1, j), jobidx, weak);
3324       else
3325         solver_addjobrule(solv, bq.elements[i], bq.elements[i + 1], 0, jobidx, weak);
3326       i += j + 1;
3327     }
3328   queue_free(&bq);
3329   return 1;
3330 }
3331 #endif
3332
3333 /* sort by package id, last entry wins */
3334 static int
3335 setup_favormaps_cmp(const void *ap, const void *bp, void *dp)
3336 {
3337   const Id *a = ap, *b = bp;
3338   if ((*a - *b) != 0)
3339     return *a - *b;
3340   return (b[1] < 0 ? -b[1] : b[1]) - (a[1] < 0 ? -a[1] : a[1]);
3341 }
3342
3343 static void
3344 setup_favormaps(Solver *solv)
3345 {
3346   Queue *q = solv->favorq;
3347   Pool *pool = solv->pool;
3348   int i;
3349   Id oldp = 0;
3350   if (q->count > 2)
3351     solv_sort(q->elements, q->count / 2, 2 * sizeof(Id), setup_favormaps_cmp, solv);
3352   map_grow(&solv->favormap, pool->nsolvables);
3353   for (i = 0; i < q->count; i += 2)
3354     {
3355       Id p = q->elements[i];
3356       if (p == oldp)
3357         continue;
3358       oldp = p;
3359       MAPSET(&solv->favormap, p);
3360       if (q->elements[i + 1] < 0)
3361         {
3362           if (!solv->isdisfavormap.size)
3363             map_grow(&solv->isdisfavormap, pool->nsolvables);
3364           MAPSET(&solv->isdisfavormap, p);
3365         }
3366     }
3367 }
3368
3369 /*
3370  *
3371  * solve job queue
3372  *
3373  */
3374
3375 int
3376 solver_solve(Solver *solv, Queue *job)
3377 {
3378   Pool *pool = solv->pool;
3379   Repo *installed = solv->installed;
3380   int i;
3381   int oldnrules, initialnrules;
3382   Map addedmap;                /* '1' == have pkg-rules for solvable */
3383   Map installcandidatemap;
3384   Id how, what, select, name, weak, p, pp, d;
3385   Queue q;
3386   Solvable *s, *name_s;
3387   Rule *r;
3388   int now, solve_start;
3389   int needduprules = 0;
3390   int hasbestinstalljob = 0;
3391
3392   solve_start = solv_timems(0);
3393
3394   /* log solver options */
3395   POOL_DEBUG(SOLV_DEBUG_STATS, "solver started\n");
3396   POOL_DEBUG(SOLV_DEBUG_STATS, "dosplitprovides=%d, noupdateprovide=%d, noinfarchcheck=%d\n", solv->dosplitprovides, solv->noupdateprovide, solv->noinfarchcheck);
3397   POOL_DEBUG(SOLV_DEBUG_STATS, "allowuninstall=%d, allowdowngrade=%d, allownamechange=%d, allowarchchange=%d, allowvendorchange=%d\n", solv->allowuninstall, solv->allowdowngrade, solv->allownamechange, solv->allowarchchange, solv->allowvendorchange);
3398   POOL_DEBUG(SOLV_DEBUG_STATS, "promoteepoch=%d, forbidselfconflicts=%d\n", pool->promoteepoch, pool->forbidselfconflicts);
3399   POOL_DEBUG(SOLV_DEBUG_STATS, "obsoleteusesprovides=%d, implicitobsoleteusesprovides=%d, obsoleteusescolors=%d, implicitobsoleteusescolors=%d\n", pool->obsoleteusesprovides, pool->implicitobsoleteusesprovides, pool->obsoleteusescolors, pool->implicitobsoleteusescolors);
3400   POOL_DEBUG(SOLV_DEBUG_STATS, "dontinstallrecommended=%d, addalreadyrecommended=%d\n", solv->dontinstallrecommended, solv->addalreadyrecommended);
3401
3402   /* create whatprovides if not already there */
3403   if (!pool->whatprovides)
3404     pool_createwhatprovides(pool);
3405
3406   /* create obsolete index */
3407   policy_create_obsolete_index(solv);
3408
3409   /* remember job */
3410   queue_free(&solv->job);
3411   queue_init_clone(&solv->job, job);
3412   solv->pooljobcnt = pool->pooljobs.count;
3413   if (pool->pooljobs.count)
3414     queue_insertn(&solv->job, 0, pool->pooljobs.count, pool->pooljobs.elements);
3415   job = &solv->job;
3416
3417   /* free old stuff in case we re-run a solver */
3418   queuep_free(&solv->update_targets);
3419   queuep_free(&solv->cleandeps_updatepkgs);
3420   queue_empty(&solv->ruleassertions);
3421   solv->bestrules_pkg = solv_free(solv->bestrules_pkg);
3422   solv->yumobsrules_info = solv_free(solv->yumobsrules_info);
3423   solv->choicerules_ref = solv_free(solv->choicerules_ref);
3424   if (solv->noupdate.size)
3425     map_empty(&solv->noupdate);
3426   map_zerosize(&solv->multiversion);
3427   solv->updatemap_all = 0;
3428   map_zerosize(&solv->updatemap);
3429   solv->bestupdatemap_all = 0;
3430   map_zerosize(&solv->bestupdatemap);
3431   solv->fixmap_all = 0;
3432   map_zerosize(&solv->fixmap);
3433   map_zerosize(&solv->dupmap);
3434   map_zerosize(&solv->dupinvolvedmap);
3435   solv->process_orphans = 0;
3436   solv->droporphanedmap_all = 0;
3437   map_zerosize(&solv->droporphanedmap);
3438   solv->allowuninstall_all = 0;
3439   map_zerosize(&solv->allowuninstallmap);
3440   map_zerosize(&solv->cleandepsmap);
3441   map_zerosize(&solv->weakrulemap);
3442   map_zerosize(&solv->favormap);
3443   map_zerosize(&solv->isdisfavormap);
3444   queue_empty(&solv->weakruleq);
3445   solv->watches = solv_free(solv->watches);
3446   queue_empty(&solv->ruletojob);
3447   if (solv->decisionq.count)
3448     memset(solv->decisionmap, 0, pool->nsolvables * sizeof(Id));
3449   queue_empty(&solv->decisionq);
3450   queue_empty(&solv->decisionq_why);
3451   queue_empty(&solv->decisionq_reason);
3452   queue_empty(&solv->learnt_why);
3453   queue_empty(&solv->learnt_pool);
3454   queue_empty(&solv->branches);
3455   solv->propagate_index = 0;
3456   queue_empty(&solv->problems);
3457   queue_empty(&solv->solutions);
3458   queue_empty(&solv->orphaned);
3459   solv->stats_learned = solv->stats_unsolvable = 0;
3460   if (solv->recommends_index)
3461     {
3462       map_empty(&solv->recommendsmap);
3463       map_empty(&solv->suggestsmap);
3464       queuep_free(&solv->recommendscplxq);
3465       queuep_free(&solv->suggestscplxq);
3466       solv->recommends_index = 0;
3467     }
3468   queuep_free(&solv->brokenorphanrules);
3469   solv->specialupdaters = solv_free(solv->specialupdaters);
3470
3471
3472   /*
3473    * create basic rule set of all involved packages
3474    * use addedmap bitmap to make sure we don't create rules twice
3475    */
3476
3477   /* create multiversion map if needed */
3478   solver_calculate_multiversionmap(pool, job, &solv->multiversion);
3479
3480   map_init(&addedmap, pool->nsolvables);
3481   MAPSET(&addedmap, SYSTEMSOLVABLE);
3482
3483   map_init(&installcandidatemap, pool->nsolvables);
3484   queue_init(&q);
3485
3486   now = solv_timems(0);
3487   /*
3488    * create rules for all package that could be involved with the solving
3489    * so called: pkg rules
3490    *
3491    */
3492   initialnrules = solv->pkgrules_end ? solv->pkgrules_end : 1;
3493   if (initialnrules > 1)
3494     deduceq2addedmap(solv, &addedmap);
3495   if (solv->nrules != initialnrules)
3496     solver_shrinkrules(solv, initialnrules);
3497   solv->nrules = initialnrules;
3498   solv->lastpkgrule = 0;
3499   solv->pkgrules_end = 0;
3500
3501   if (installed)
3502     {
3503       /* check for update/verify jobs as they need to be known early */
3504       /* also setup the droporphaned map, we need it when creating update rules */
3505       for (i = 0; i < job->count; i += 2)
3506         {
3507           how = job->elements[i];
3508           what = job->elements[i + 1];
3509           select = how & SOLVER_SELECTMASK;
3510           switch (how & SOLVER_JOBMASK)
3511             {
3512             case SOLVER_VERIFY:
3513               if (select == SOLVER_SOLVABLE_ALL || (select == SOLVER_SOLVABLE_REPO && installed && what == installed->repoid))
3514                 solv->fixmap_all = 1;
3515               FOR_JOB_SELECT(p, pp, select, what)
3516                 {
3517                   s = pool->solvables + p;
3518                   if (s->repo != installed)
3519                     continue;
3520                   if (!solv->fixmap.size)
3521                     map_grow(&solv->fixmap, installed->end - installed->start);
3522                   MAPSET(&solv->fixmap, p - installed->start);
3523                 }
3524               break;
3525             case SOLVER_UPDATE:
3526               if (select == SOLVER_SOLVABLE_ALL)
3527                 {
3528                   solv->updatemap_all = 1;
3529                   if (how & SOLVER_FORCEBEST)
3530                     solv->bestupdatemap_all = 1;
3531                   if (how & SOLVER_CLEANDEPS)
3532                     {
3533                       FOR_REPO_SOLVABLES(installed, p, s)
3534                         add_cleandeps_updatepkg(solv, p);
3535                     }
3536                 }
3537               else if (select == SOLVER_SOLVABLE_REPO)
3538                 {
3539                   Repo *repo = pool_id2repo(pool, what);
3540                   if (!repo)
3541                     break;
3542                   if (repo == installed && !(how & SOLVER_TARGETED))
3543                     {
3544                       solv->updatemap_all = 1;
3545                       if (how & SOLVER_FORCEBEST)
3546                         solv->bestupdatemap_all = 1;
3547                       if (how & SOLVER_CLEANDEPS)
3548                         {
3549                           FOR_REPO_SOLVABLES(installed, p, s)
3550                             add_cleandeps_updatepkg(solv, p);
3551                         }
3552                       break;
3553                     }
3554                   if (solv->noautotarget && !(how & SOLVER_TARGETED))
3555                     break;
3556                   /* targeted update */
3557                   FOR_REPO_SOLVABLES(repo, p, s)
3558                     add_update_target(solv, p, how);
3559                 }
3560               else
3561                 {
3562                   if (!(how & SOLVER_TARGETED))
3563                     {
3564                       int targeted = 1;
3565                       FOR_JOB_SELECT(p, pp, select, what)
3566                         {
3567                           s = pool->solvables + p;
3568                           if (s->repo != installed)
3569                             continue;
3570                           if (!solv->updatemap.size)
3571                             map_grow(&solv->updatemap, installed->end - installed->start);
3572                           MAPSET(&solv->updatemap, p - installed->start);
3573                           if (how & SOLVER_FORCEBEST)
3574                             {
3575                               if (!solv->bestupdatemap.size)
3576                                 map_grow(&solv->bestupdatemap, installed->end - installed->start);
3577                               MAPSET(&solv->bestupdatemap, p - installed->start);
3578                             }
3579                           if (how & SOLVER_CLEANDEPS)
3580                             add_cleandeps_updatepkg(solv, p);
3581                           targeted = 0;
3582                         }
3583                       if (!targeted || solv->noautotarget)
3584                         break;
3585                     }
3586                   FOR_JOB_SELECT(p, pp, select, what)
3587                     add_update_target(solv, p, how);
3588                 }
3589               break;
3590             case SOLVER_DROP_ORPHANED:
3591               if (select == SOLVER_SOLVABLE_ALL || (select == SOLVER_SOLVABLE_REPO && what == installed->repoid))
3592                 solv->droporphanedmap_all = 1;
3593               FOR_JOB_SELECT(p, pp, select, what)
3594                 {
3595                   s = pool->solvables + p;
3596                   if (s->repo != installed)
3597                     continue;
3598                   if (!solv->droporphanedmap.size)
3599                     map_grow(&solv->droporphanedmap, installed->end - installed->start);
3600                   MAPSET(&solv->droporphanedmap, p - installed->start);
3601                 }
3602               break;
3603             case SOLVER_ALLOWUNINSTALL:
3604               if (select == SOLVER_SOLVABLE_ALL || (select == SOLVER_SOLVABLE_REPO && installed && what == installed->repoid))
3605                 solv->allowuninstall_all = 1;
3606               FOR_JOB_SELECT(p, pp, select, what)
3607                 {
3608                   s = pool->solvables + p;
3609                   if (s->repo != installed)
3610                     continue;
3611                   if (!solv->allowuninstallmap.size)
3612                     map_grow(&solv->allowuninstallmap, installed->end - installed->start);
3613                   MAPSET(&solv->allowuninstallmap, p - installed->start);
3614                 }
3615               break;
3616             default:
3617               break;
3618             }
3619         }
3620
3621       if (solv->update_targets)
3622         transform_update_targets(solv);
3623
3624       oldnrules = solv->nrules;
3625       FOR_REPO_SOLVABLES(installed, p, s)
3626         solver_addpkgrulesforsolvable(solv, s, &addedmap);
3627       POOL_DEBUG(SOLV_DEBUG_STATS, "added %d pkg rules for installed solvables\n", solv->nrules - oldnrules);
3628       oldnrules = solv->nrules;
3629       FOR_REPO_SOLVABLES(installed, p, s)
3630         solver_addpkgrulesforupdaters(solv, s, &addedmap, 1);
3631       POOL_DEBUG(SOLV_DEBUG_STATS, "added %d pkg rules for updaters of installed solvables\n", solv->nrules - oldnrules);
3632     }
3633
3634   /*
3635    * create rules for all packages involved in the job
3636    * (to be installed or removed)
3637    */
3638
3639   oldnrules = solv->nrules;
3640   for (i = 0; i < job->count; i += 2)
3641     {
3642       how = job->elements[i];
3643       what = job->elements[i + 1];
3644       select = how & SOLVER_SELECTMASK;
3645
3646       switch (how & SOLVER_JOBMASK)
3647         {
3648         case SOLVER_INSTALL:
3649           FOR_JOB_SELECT(p, pp, select, what)
3650             {
3651               MAPSET(&installcandidatemap, p);
3652               solver_addpkgrulesforsolvable(solv, pool->solvables + p, &addedmap);
3653             }
3654           break;
3655         case SOLVER_DISTUPGRADE:
3656           needduprules = 1;
3657           if (select == SOLVER_SOLVABLE_ALL)
3658             solv->process_orphans = 1;
3659           break;
3660         default:
3661           break;
3662         }
3663     }
3664   POOL_DEBUG(SOLV_DEBUG_STATS, "added %d pkg rules for packages involved in a job\n", solv->nrules - oldnrules);
3665
3666
3667   /*
3668    * add rules for suggests, enhances
3669    */
3670   oldnrules = solv->nrules;
3671   solver_addpkgrulesforweak(solv, &addedmap);
3672   POOL_DEBUG(SOLV_DEBUG_STATS, "added %d pkg rules because of weak dependencies\n", solv->nrules - oldnrules);
3673
3674 #ifdef ENABLE_LINKED_PKGS
3675   oldnrules = solv->nrules;
3676   solver_addpkgrulesforlinked(solv, &addedmap);
3677   POOL_DEBUG(SOLV_DEBUG_STATS, "added %d pkg rules because of linked packages\n", solv->nrules - oldnrules);
3678 #endif
3679
3680   /*
3681    * first pass done, we now have all the pkg rules we need.
3682    * unify existing rules before going over all job rules and
3683    * policy rules.
3684    * at this point the system is always solvable,
3685    * as an empty system (remove all packages) is a valid solution
3686    */
3687
3688   IF_POOLDEBUG (SOLV_DEBUG_STATS)
3689     {
3690       int possible = 0, installable = 0;
3691       for (i = 1; i < pool->nsolvables; i++)
3692         {
3693           if (pool_installable(pool, pool->solvables + i))
3694             installable++;
3695           if (MAPTST(&addedmap, i))
3696             possible++;
3697         }
3698       POOL_DEBUG(SOLV_DEBUG_STATS, "%d of %d installable solvables considered for solving\n", possible, installable);
3699     }
3700
3701   if (solv->nrules > initialnrules)
3702     solver_unifyrules(solv);                    /* remove duplicate pkg rules */
3703   solv->pkgrules_end = solv->nrules;            /* mark end of pkg rules */
3704   solv->lastpkgrule = 0;
3705
3706   if (solv->nrules > initialnrules)
3707     addedmap2deduceq(solv, &addedmap);          /* so that we can recreate the addedmap */
3708
3709   POOL_DEBUG(SOLV_DEBUG_STATS, "pkg rule memory used: %d K\n", solv->nrules * (int)sizeof(Rule) / 1024);
3710   POOL_DEBUG(SOLV_DEBUG_STATS, "pkg rule creation took %d ms\n", solv_timems(now));
3711
3712   /* create dup maps if needed. We need the maps early to create our
3713    * update rules */
3714   if (needduprules)
3715     solver_createdupmaps(solv);
3716
3717   /*
3718    * create feature rules
3719    *
3720    * foreach installed:
3721    *   create assertion (keep installed, if no update available)
3722    *   or
3723    *   create update rule (A|update1(A)|update2(A)|...)
3724    *
3725    * those are used later on to keep a version of the installed packages in
3726    * best effort mode
3727    */
3728
3729   solv->featurerules = solv->nrules;              /* mark start of feature rules */
3730   if (installed)
3731     {
3732       /* foreach possibly installed solvable */
3733       for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
3734         {
3735           if (s->repo != installed)
3736             {
3737               solver_addrule(solv, 0, 0, 0);    /* create dummy rule */
3738               continue;
3739             }
3740           solver_addfeaturerule(solv, s);
3741         }
3742       /* make sure we accounted for all rules */
3743       assert(solv->nrules - solv->featurerules == installed->end - installed->start);
3744     }
3745   solv->featurerules_end = solv->nrules;
3746
3747     /*
3748      * Add update rules for installed solvables
3749      *
3750      * almost identical to feature rules
3751      * except that downgrades/archchanges/vendorchanges are not allowed
3752      */
3753
3754   solv->updaterules = solv->nrules;
3755
3756   if (installed)
3757     { /* foreach installed solvables */
3758       /* we create all update rules, but disable some later on depending on the job */
3759       for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
3760         {
3761           Rule *sr;
3762
3763           if (s->repo != installed)
3764             {
3765               solver_addrule(solv, 0, 0, 0);    /* create dummy rule */
3766               continue;
3767             }
3768           solver_addupdaterule(solv, s);
3769           /*
3770            * check for and remove duplicate
3771            */
3772           r = solv->rules + solv->nrules - 1;           /* r: update rule */
3773           sr = r - (installed->end - installed->start); /* sr: feature rule */
3774           if (!r->p)
3775             {
3776               if (sr->p)
3777                 memset(sr, 0, sizeof(*sr));             /* no feature rules without update rules */
3778               continue;
3779             }
3780           /* it's also orphaned if the feature rule consists just of the installed package */
3781           if (!solv->process_orphans && sr->p == i && !sr->d && !sr->w2)
3782             queue_push(&solv->orphaned, i);
3783
3784           if (!solver_rulecmp(solv, r, sr))
3785             memset(sr, 0, sizeof(*sr));         /* delete unneeded feature rule */
3786           else if (sr->p)
3787             solver_disablerule(solv, sr);       /* disable feature rule for now */
3788         }
3789       /* consistency check: we added a rule for _every_ installed solvable */
3790       assert(solv->nrules - solv->updaterules == installed->end - installed->start);
3791     }
3792   solv->updaterules_end = solv->nrules;
3793
3794
3795   /*
3796    * now add all job rules
3797    */
3798
3799   solv->jobrules = solv->nrules;
3800   for (i = 0; i < job->count; i += 2)
3801     {
3802       oldnrules = solv->nrules;
3803
3804       if (i && i == solv->pooljobcnt)
3805         POOL_DEBUG(SOLV_DEBUG_JOB, "end of pool jobs\n");
3806       how = job->elements[i];
3807       what = job->elements[i + 1];
3808       weak = how & SOLVER_WEAK;
3809       select = how & SOLVER_SELECTMASK;
3810       switch (how & SOLVER_JOBMASK)
3811         {
3812         case SOLVER_INSTALL:
3813           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sinstall %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
3814           if ((how & SOLVER_CLEANDEPS) != 0 && !solv->cleandepsmap.size && installed)
3815             map_grow(&solv->cleandepsmap, installed->end - installed->start);
3816           if (select == SOLVER_SOLVABLE)
3817             {
3818               p = what;
3819               d = 0;
3820             }
3821 #ifdef ENABLE_COMPLEX_DEPS
3822           else if ((select == SOLVER_SOLVABLE_PROVIDES || select == SOLVER_SOLVABLE_NAME) && pool_is_complex_dep(pool, what))
3823             {
3824               if (add_complex_jobrules(solv, what, select == SOLVER_SOLVABLE_NAME ? CPLXDEPS_NAME : 0, i, weak))
3825                 if (how & SOLVER_FORCEBEST)
3826                   hasbestinstalljob = 1;
3827               break;
3828             }
3829 #endif
3830           else
3831             {
3832               queue_empty(&q);
3833               FOR_JOB_SELECT(p, pp, select, what)
3834                 queue_push(&q, p);
3835               if (!q.count)
3836                 {
3837                   if (select == SOLVER_SOLVABLE_ONE_OF)
3838                     break;      /* ignore empty installs */
3839                   /* no candidate found or unsupported, make this an impossible rule */
3840                   queue_push(&q, -SYSTEMSOLVABLE);
3841                 }
3842               p = queue_shift(&q);      /* get first candidate */
3843               d = !q.count ? 0 : pool_queuetowhatprovides(pool, &q);    /* internalize */
3844             }
3845           /* force install of namespace supplements hack */
3846           if (select == SOLVER_SOLVABLE_PROVIDES && !d && (p == SYSTEMSOLVABLE || p == -SYSTEMSOLVABLE) && ISRELDEP(what))
3847             {
3848               Reldep *rd = GETRELDEP(pool, what);
3849               if (rd->flags == REL_NAMESPACE)
3850                 {
3851                   p = SYSTEMSOLVABLE;
3852                   if (!solv->installsuppdepq)
3853                     {
3854                       solv->installsuppdepq = solv_calloc(1, sizeof(Queue));
3855                       queue_init(solv->installsuppdepq);
3856                     }
3857                   queue_pushunique(solv->installsuppdepq, rd->evr == 0 ? rd->name : what);
3858                 }
3859             }
3860           solver_addjobrule(solv, p, 0, d, i, weak);
3861           if (how & SOLVER_FORCEBEST)
3862             hasbestinstalljob = 1;
3863           break;
3864         case SOLVER_ERASE:
3865           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %s%serase %s\n", weak ? "weak " : "", how & SOLVER_CLEANDEPS ? "clean deps " : "", solver_select2str(pool, select, what));
3866           if ((how & SOLVER_CLEANDEPS) != 0 && !solv->cleandepsmap.size && installed)
3867             map_grow(&solv->cleandepsmap, installed->end - installed->start);
3868           /* specific solvable: by id or by nevra */
3869           name = (select == SOLVER_SOLVABLE || (select == SOLVER_SOLVABLE_NAME && ISRELDEP(what))) ? 0 : -1;
3870           name_s = 0;
3871           if (select == SOLVER_SOLVABLE_ALL)    /* hmmm ;) */
3872             {
3873               FOR_POOL_SOLVABLES(p)
3874                 solver_addjobrule(solv, -p, 0, 0, i, weak);
3875             }
3876           else if (select == SOLVER_SOLVABLE_REPO)
3877             {
3878               Repo *repo = pool_id2repo(pool, what);
3879               if (repo)
3880                 {
3881                   FOR_REPO_SOLVABLES(repo, p, s)
3882                     solver_addjobrule(solv, -p, 0, 0, i, weak);
3883                 }
3884             }
3885 #ifdef ENABLE_COMPLEX_DEPS
3886           else if ((select == SOLVER_SOLVABLE_PROVIDES || select == SOLVER_SOLVABLE_NAME) && pool_is_complex_dep(pool, what))
3887             {
3888               /* no special "erase a specific solvable" handling? */
3889               add_complex_jobrules(solv, what, select == SOLVER_SOLVABLE_NAME ? (CPLXDEPS_NAME | CPLXDEPS_TODNF | CPLXDEPS_INVERT) : (CPLXDEPS_TODNF | CPLXDEPS_INVERT), i, weak);
3890               break;
3891             }
3892 #endif
3893           FOR_JOB_SELECT(p, pp, select, what)
3894             {
3895               s = pool->solvables + p;
3896               if (installed && s->repo == installed)
3897                 {
3898                   name = !name ? s->name : -1;
3899                   name_s = s;
3900                 }
3901               solver_addjobrule(solv, -p, 0, 0, i, weak);
3902             }
3903           /* special case for "erase a specific solvable": we also
3904            * erase all other solvables with that name, so that they
3905            * don't get picked up as replacement.
3906            * name is > 0 if exactly one installed solvable matched.
3907            */
3908           /* XXX: look also at packages that obsolete this package? */
3909           if (name > 0)
3910             {
3911               int j, k;
3912               k = solv->nrules;
3913               FOR_PROVIDES(p, pp, name)
3914                 {
3915                   s = pool->solvables + p;
3916                   if (s->name != name)
3917                     continue;
3918                   /* keep other versions installed */
3919                   if (s->repo == installed)
3920                     continue;
3921                   /* keep installcandidates of other jobs */
3922                   if (MAPTST(&installcandidatemap, p))
3923                     continue;
3924                   if (pool->implicitobsoleteusescolors && !pool_colormatch(pool, name_s, s))
3925                     continue;
3926                   /* don't add the same rule twice */
3927                   for (j = oldnrules; j < k; j++)
3928                     if (solv->rules[j].p == -p)
3929                       break;
3930                   if (j == k)
3931                     solver_addjobrule(solv, -p, 0, 0, i, weak); /* remove by id */
3932                 }
3933             }
3934           break;
3935
3936         case SOLVER_UPDATE:
3937           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %supdate %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
3938           break;
3939         case SOLVER_VERIFY:
3940           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sverify %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
3941           break;
3942         case SOLVER_WEAKENDEPS:
3943           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sweaken deps %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
3944           if (select != SOLVER_SOLVABLE)
3945             break;
3946           s = pool->solvables + what;
3947           weaken_solvable_deps(solv, what);
3948           break;
3949         case SOLVER_MULTIVERSION:
3950           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %smultiversion %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
3951           break;
3952         case SOLVER_LOCK:
3953           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %slock %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
3954           if (select == SOLVER_SOLVABLE_ALL)
3955             {
3956               FOR_POOL_SOLVABLES(p)
3957                 solver_addjobrule(solv, installed && pool->solvables[p].repo == installed ? p : -p, 0, 0, i, weak);
3958             }
3959           else if (select == SOLVER_SOLVABLE_REPO)
3960             {
3961               Repo *repo = pool_id2repo(pool, what);
3962               if (repo)
3963                 {
3964                   FOR_REPO_SOLVABLES(repo, p, s)
3965                     solver_addjobrule(solv, installed && pool->solvables[p].repo == installed ? p : -p, 0, 0, i, weak);
3966                 }
3967             }
3968           FOR_JOB_SELECT(p, pp, select, what)
3969             solver_addjobrule(solv, installed && pool->solvables[p].repo == installed ? p : -p, 0, 0, i, weak);
3970           break;
3971         case SOLVER_DISTUPGRADE:
3972           POOL_DEBUG(SOLV_DEBUG_JOB, "job: distupgrade %s\n", solver_select2str(pool, select, what));
3973           break;
3974         case SOLVER_DROP_ORPHANED:
3975           POOL_DEBUG(SOLV_DEBUG_JOB, "job: drop orphaned %s\n", solver_select2str(pool, select, what));
3976           break;
3977         case SOLVER_USERINSTALLED:
3978           POOL_DEBUG(SOLV_DEBUG_JOB, "job: user installed %s\n", solver_select2str(pool, select, what));
3979           break;
3980         case SOLVER_ALLOWUNINSTALL:
3981           POOL_DEBUG(SOLV_DEBUG_JOB, "job: allowuninstall %s\n", solver_select2str(pool, select, what));
3982           break;
3983         case SOLVER_FAVOR:
3984         case SOLVER_DISFAVOR:
3985           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %s %s\n", (how & SOLVER_JOBMASK) == SOLVER_FAVOR ? "favor" : "disfavor", solver_select2str(pool, select, what));
3986           FOR_JOB_SELECT(p, pp, select, what)
3987             {
3988               int j;
3989               if (!solv->favorq)
3990                 {
3991                   solv->favorq = solv_calloc(1, sizeof(Queue));
3992                   queue_init(solv->favorq);
3993                 }
3994               j = solv->favorq->count + 1;
3995               queue_push2(solv->favorq, p, (how & SOLVER_JOBMASK) == SOLVER_FAVOR ? j : -j);
3996             }
3997           break;
3998         default:
3999           POOL_DEBUG(SOLV_DEBUG_JOB, "job: unknown job\n");
4000           break;
4001         }
4002
4003       IF_POOLDEBUG (SOLV_DEBUG_JOB)
4004         {
4005           int j;
4006           if (solv->nrules == oldnrules)
4007             POOL_DEBUG(SOLV_DEBUG_JOB, "  - no rule created\n");
4008           for (j = oldnrules; j < solv->nrules; j++)
4009             {
4010               POOL_DEBUG(SOLV_DEBUG_JOB, "  - job ");
4011               solver_printrule(solv, SOLV_DEBUG_JOB, solv->rules + j);
4012             }
4013         }
4014     }
4015   assert(solv->ruletojob.count == solv->nrules - solv->jobrules);
4016   solv->jobrules_end = solv->nrules;
4017
4018   /* transform favorq into two maps */
4019   if (solv->favorq)
4020     setup_favormaps(solv);
4021
4022   /* now create infarch and dup rules */
4023   if (!solv->noinfarchcheck)
4024     {
4025       solver_addinfarchrules(solv, &addedmap);
4026 #if 0
4027       if (pool->implicitobsoleteusescolors)
4028         {
4029           /* currently doesn't work well with infarch rules, so make
4030            * them weak */
4031           for (i = solv->infarchrules; i < solv->infarchrules_end; i++)
4032             queue_push(&solv->weakruleq, i);
4033         }
4034 #endif
4035     }
4036   else
4037     solv->infarchrules = solv->infarchrules_end = solv->nrules;
4038
4039   if (solv->dupinvolvedmap_all || solv->dupinvolvedmap.size)
4040     solver_addduprules(solv, &addedmap);
4041   else
4042     solv->duprules = solv->duprules_end = solv->nrules;
4043
4044 #ifdef ENABLE_LINKED_PKGS
4045   if (solv->instbuddy && solv->updatemap.size)
4046     extend_updatemap_to_buddies(solv);
4047 #endif
4048
4049   if (solv->bestupdatemap_all || solv->bestupdatemap.size || hasbestinstalljob)
4050     solver_addbestrules(solv, hasbestinstalljob);
4051   else
4052     solv->bestrules = solv->bestrules_end = solv->nrules;
4053
4054   if (needduprules)
4055     solver_freedupmaps(solv);   /* no longer needed */
4056
4057   if (solv->do_yum_obsoletes)
4058     solver_addyumobsrules(solv);
4059   else
4060     solv->yumobsrules = solv->yumobsrules_end = solv->nrules;
4061
4062   if (1)
4063     solver_addchoicerules(solv);
4064   else
4065     solv->choicerules = solv->choicerules_end = solv->nrules;
4066
4067   if (0)
4068     {
4069       for (i = solv->featurerules; i < solv->nrules; i++)
4070         solver_printruleclass(solv, SOLV_DEBUG_RESULT, solv->rules + i);
4071     }
4072   /* all rules created
4073    * --------------------------------------------------------------
4074    * prepare for solving
4075    */
4076
4077   /* free unneeded memory */
4078   map_free(&addedmap);
4079   map_free(&installcandidatemap);
4080   queue_free(&q);
4081
4082   POOL_DEBUG(SOLV_DEBUG_STATS, "%d pkg rules, 2 * %d update rules, %d job rules, %d infarch rules, %d dup rules, %d choice rules, %d best rules\n", solv->pkgrules_end - 1, solv->updaterules_end - solv->updaterules, solv->jobrules_end - solv->jobrules, solv->infarchrules_end - solv->infarchrules, solv->duprules_end - solv->duprules, solv->choicerules_end - solv->choicerules, solv->bestrules_end - solv->bestrules);
4083   POOL_DEBUG(SOLV_DEBUG_STATS, "overall rule memory used: %d K\n", solv->nrules * (int)sizeof(Rule) / 1024);
4084
4085   /* create weak map */
4086   if (solv->weakruleq.count || solv->recommendsruleq)
4087     {
4088       map_grow(&solv->weakrulemap, solv->nrules);
4089       for (i = 0; i < solv->weakruleq.count; i++)
4090         {
4091           p = solv->weakruleq.elements[i];
4092           MAPSET(&solv->weakrulemap, p);
4093         }
4094       if (solv->recommendsruleq)
4095         {
4096           for (i = 0; i < solv->recommendsruleq->count; i++)
4097             {
4098               p = solv->recommendsruleq->elements[i];
4099               MAPSET(&solv->weakrulemap, p);
4100             }
4101         }
4102     }
4103
4104   /* enable cleandepsmap creation if we have updatepkgs */
4105   if (solv->cleandeps_updatepkgs && !solv->cleandepsmap.size)
4106     map_grow(&solv->cleandepsmap, installed->end - installed->start);
4107   /* no mistakes */
4108   if (solv->cleandeps_mistakes)
4109     {
4110       queue_free(solv->cleandeps_mistakes);
4111       solv->cleandeps_mistakes = solv_free(solv->cleandeps_mistakes);
4112     }
4113
4114   /* all new rules are learnt after this point */
4115   solv->learntrules = solv->nrules;
4116
4117   /* create watches chains */
4118   makewatches(solv);
4119
4120   /* create assertion index. it is only used to speed up
4121    * makeruledecsions() a bit */
4122   for (i = 1, r = solv->rules + i; i < solv->nrules; i++, r++)
4123     if (r->p && !r->w2 && (r->d == 0 || r->d == -1))
4124       queue_push(&solv->ruleassertions, i);
4125
4126   /* disable update rules that conflict with our job */
4127   solver_disablepolicyrules(solv);
4128
4129   /* break orphans if requested */
4130   if (solv->process_orphans && solv->orphaned.count && solv->break_orphans)
4131     solver_breakorphans(solv);
4132
4133   /*
4134    * ********************************************
4135    * solve!
4136    * ********************************************
4137    */
4138
4139   now = solv_timems(0);
4140   solver_run_sat(solv, 1, solv->dontinstallrecommended ? 0 : 1);
4141   POOL_DEBUG(SOLV_DEBUG_STATS, "solver took %d ms\n", solv_timems(now));
4142
4143   /*
4144    * prepare solution queue if there were problems
4145    */
4146   solver_prepare_solutions(solv);
4147
4148   POOL_DEBUG(SOLV_DEBUG_STATS, "final solver statistics: %d problems, %d learned rules, %d unsolvable\n", solv->problems.count / 2, solv->stats_learned, solv->stats_unsolvable);
4149   POOL_DEBUG(SOLV_DEBUG_STATS, "solver_solve took %d ms\n", solv_timems(solve_start));
4150
4151   /* return number of problems */
4152   return solv->problems.count ? solv->problems.count / 2 : 0;
4153 }
4154
4155 Transaction *
4156 solver_create_transaction(Solver *solv)
4157 {
4158   return transaction_create_decisionq(solv->pool, &solv->decisionq, &solv->multiversion);
4159 }
4160
4161 void solver_get_orphaned(Solver *solv, Queue *orphanedq)
4162 {
4163   queue_free(orphanedq);
4164   queue_init_clone(orphanedq, &solv->orphaned);
4165 }
4166
4167 void solver_get_cleandeps(Solver *solv, Queue *cleandepsq)
4168 {
4169   Pool *pool = solv->pool;
4170   Repo *installed = solv->installed;
4171   Solvable *s;
4172   Rule *r;
4173   Id p, pp, pr;
4174
4175   queue_empty(cleandepsq);
4176   if (!installed || !solv->cleandepsmap.size)
4177     return;
4178   FOR_REPO_SOLVABLES(installed, p, s)
4179     {
4180       if (!MAPTST(&solv->cleandepsmap, p - installed->start) || solv->decisionmap[p] >= 0)
4181         continue;
4182       /* now check the update rule */
4183       r = solv->rules + solv->updaterules + (p - solv->installed->start);
4184       if (r->p)
4185         {
4186           FOR_RULELITERALS(pr, pp, r)
4187             if (solv->decisionmap[pr] > 0)
4188               break;
4189           if (pr)
4190             continue;
4191         }
4192       queue_push(cleandepsq, p);
4193     }
4194 }
4195
4196 void solver_get_recommendations(Solver *solv, Queue *recommendationsq, Queue *suggestionsq, int noselected)
4197 {
4198   Pool *pool = solv->pool;
4199   Queue redoq, disabledq;
4200   int goterase, i;
4201   Solvable *s;
4202   Rule *r;
4203   Map obsmap;
4204
4205   if (!recommendationsq && !suggestionsq)
4206     return;
4207
4208   map_init(&obsmap, pool->nsolvables);
4209   if (solv->installed)
4210     {
4211       Id obs, *obsp, p, po, ppo;
4212       for (p = solv->installed->start; p < solv->installed->end; p++)
4213         {
4214           s = pool->solvables + p;
4215           if (s->repo != solv->installed || !s->obsoletes)
4216             continue;
4217           if (solv->decisionmap[p] <= 0)
4218             continue;
4219           if (solv->multiversion.size && MAPTST(&solv->multiversion, p))
4220             continue;
4221           obsp = s->repo->idarraydata + s->obsoletes;
4222           /* foreach obsoletes */
4223           while ((obs = *obsp++) != 0)
4224             FOR_PROVIDES(po, ppo, obs)
4225               MAPSET(&obsmap, po);
4226         }
4227     }
4228
4229   queue_init(&redoq);
4230   queue_init(&disabledq);
4231   goterase = 0;
4232   /* disable all erase jobs (including weak "keep uninstalled" rules) */
4233   for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++)
4234     {
4235       if (r->d < 0)     /* disabled ? */
4236         continue;
4237       if (r->p >= 0)    /* install job? */
4238         continue;
4239       queue_push(&disabledq, i);
4240       solver_disablerule(solv, r);
4241       goterase++;
4242     }
4243
4244   if (goterase)
4245     {
4246       enabledisablelearntrules(solv);
4247       removedisabledconflicts(solv, &redoq);
4248     }
4249
4250   /*
4251    * find recommended packages
4252    */
4253   if (recommendationsq)
4254     {
4255       Id rec, *recp, p, pp;
4256
4257       queue_empty(recommendationsq);
4258       /* create map of all recommened packages */
4259       solv->recommends_index = -1;
4260       MAPZERO(&solv->recommendsmap);
4261
4262       /* put all packages the solver already chose in the map */
4263       for (i = 1; i < solv->decisionq.count; i++)
4264         if ((p = solv->decisionq.elements[i]) > 0 && solv->decisionq_why.elements[i] == 0)
4265           {
4266             if (solv->decisionq_reason.elements[solv->decisionmap[p]] == SOLVER_REASON_WEAKDEP)
4267               MAPSET(&solv->recommendsmap, p);
4268           }
4269
4270       for (i = 0; i < solv->decisionq.count; i++)
4271         {
4272           p = solv->decisionq.elements[i];
4273           if (p < 0)
4274             continue;
4275           s = pool->solvables + p;
4276           if (s->recommends)
4277             {
4278               recp = s->repo->idarraydata + s->recommends;
4279               while ((rec = *recp++) != 0)
4280                 {
4281 #ifdef ENABLE_COMPLEX_DEPS
4282                   if (pool_is_complex_dep(pool, rec))
4283                     {
4284                       do_complex_recommendations(solv, rec, &solv->recommendsmap, noselected);
4285                       continue;
4286                     }
4287 #endif
4288                   FOR_PROVIDES(p, pp, rec)
4289                     if (solv->decisionmap[p] > 0)
4290                       break;
4291                   if (p)
4292                     {
4293                       if (!noselected)
4294                         {
4295                           FOR_PROVIDES(p, pp, rec)
4296                             if (solv->decisionmap[p] > 0)
4297                               MAPSET(&solv->recommendsmap, p);
4298                         }
4299                       continue; /* p != 0: already fulfilled */
4300                     }
4301                   FOR_PROVIDES(p, pp, rec)
4302                     MAPSET(&solv->recommendsmap, p);
4303                 }
4304             }
4305         }
4306       for (i = 1; i < pool->nsolvables; i++)
4307         {
4308           if (solv->decisionmap[i] < 0)
4309             continue;
4310           if (solv->decisionmap[i] > 0 && noselected)
4311             continue;
4312           if (MAPTST(&obsmap, i))
4313             continue;
4314           s = pool->solvables + i;
4315           if (!MAPTST(&solv->recommendsmap, i))
4316             {
4317               if (!s->supplements)
4318                 continue;
4319               if (!pool_installable(pool, s))
4320                 continue;
4321               if (!solver_is_supplementing(solv, s))
4322                 continue;
4323             }
4324           queue_push(recommendationsq, i);
4325         }
4326       /* we use MODE_SUGGEST here so that repo prio is ignored */
4327       policy_filter_unwanted(solv, recommendationsq, POLICY_MODE_SUGGEST);
4328     }
4329
4330   /*
4331    * find suggested packages
4332    */
4333
4334   if (suggestionsq)
4335     {
4336       Id sug, *sugp, p, pp;
4337
4338       queue_empty(suggestionsq);
4339       /* create map of all suggests that are still open */
4340       solv->recommends_index = -1;
4341       MAPZERO(&solv->suggestsmap);
4342       for (i = 0; i < solv->decisionq.count; i++)
4343         {
4344           p = solv->decisionq.elements[i];
4345           if (p < 0)
4346             continue;
4347           s = pool->solvables + p;
4348           if (s->suggests)
4349             {
4350               sugp = s->repo->idarraydata + s->suggests;
4351               while ((sug = *sugp++) != 0)
4352                 {
4353 #ifdef ENABLE_COMPLEX_DEPS
4354                   if (pool_is_complex_dep(pool, sug))
4355                     {
4356                       do_complex_recommendations(solv, sug, &solv->suggestsmap, noselected);
4357                       continue;
4358                     }
4359 #endif
4360                   FOR_PROVIDES(p, pp, sug)
4361                     if (solv->decisionmap[p] > 0)
4362                       break;
4363                   if (p)
4364                     {
4365                       if (!noselected)
4366                         {
4367                           FOR_PROVIDES(p, pp, sug)
4368                             if (solv->decisionmap[p] > 0)
4369                               MAPSET(&solv->suggestsmap, p);
4370                         }
4371                       continue; /* already fulfilled */
4372                     }
4373                   FOR_PROVIDES(p, pp, sug)
4374                     MAPSET(&solv->suggestsmap, p);
4375                 }
4376             }
4377         }
4378       for (i = 1; i < pool->nsolvables; i++)
4379         {
4380           if (solv->decisionmap[i] < 0)
4381             continue;
4382           if (solv->decisionmap[i] > 0 && noselected)
4383             continue;
4384           if (MAPTST(&obsmap, i))
4385             continue;
4386           s = pool->solvables + i;
4387           if (!MAPTST(&solv->suggestsmap, i))
4388             {
4389               if (!s->enhances)
4390                 continue;
4391               if (!pool_installable(pool, s))
4392                 continue;
4393               if (!solver_is_enhancing(solv, s))
4394                 continue;
4395             }
4396           queue_push(suggestionsq, i);
4397         }
4398       policy_filter_unwanted(solv, suggestionsq, POLICY_MODE_SUGGEST);
4399     }
4400
4401   /* undo removedisabledconflicts */
4402   if (redoq.count)
4403     undo_removedisabledconflicts(solv, &redoq);
4404   queue_free(&redoq);
4405
4406   /* undo job rule disabling */
4407   for (i = 0; i < disabledq.count; i++)
4408     solver_enablerule(solv, solv->rules + disabledq.elements[i]);
4409   queue_free(&disabledq);
4410   map_free(&obsmap);
4411 }
4412
4413
4414 /***********************************************************************/
4415 /* disk usage computations */
4416
4417 /*-------------------------------------------------------------------
4418  *
4419  * calculate DU changes
4420  */
4421
4422 void
4423 solver_calc_duchanges(Solver *solv, DUChanges *mps, int nmps)
4424 {
4425   Map installedmap;
4426
4427   solver_create_state_maps(solv, &installedmap, 0);
4428   pool_calc_duchanges(solv->pool, &installedmap, mps, nmps);
4429   map_free(&installedmap);
4430 }
4431
4432
4433 /*-------------------------------------------------------------------
4434  *
4435  * calculate changes in install size
4436  */
4437
4438 int
4439 solver_calc_installsizechange(Solver *solv)
4440 {
4441   Map installedmap;
4442   int change;
4443
4444   solver_create_state_maps(solv, &installedmap, 0);
4445   change = pool_calc_installsizechange(solv->pool, &installedmap);
4446   map_free(&installedmap);
4447   return change;
4448 }
4449
4450 void
4451 solver_create_state_maps(Solver *solv, Map *installedmap, Map *conflictsmap)
4452 {
4453   pool_create_state_maps(solv->pool, &solv->decisionq, installedmap, conflictsmap);
4454 }
4455
4456 /*-------------------------------------------------------------------
4457  *
4458  * decision introspection
4459  */
4460
4461 int
4462 solver_get_decisionlevel(Solver *solv, Id p)
4463 {
4464   return solv->decisionmap[p];
4465 }
4466
4467 void
4468 solver_get_decisionqueue(Solver *solv, Queue *decisionq)
4469 {
4470   queue_free(decisionq);
4471   queue_init_clone(decisionq, &solv->decisionq);
4472 }
4473
4474 int
4475 solver_get_lastdecisionblocklevel(Solver *solv)
4476 {
4477   Id p;
4478   if (solv->decisionq.count == 0)
4479     return 0;
4480   p = solv->decisionq.elements[solv->decisionq.count - 1];
4481   if (p < 0)
4482     p = -p;
4483   return solv->decisionmap[p] < 0 ? -solv->decisionmap[p] : solv->decisionmap[p];
4484 }
4485
4486 void
4487 solver_get_decisionblock(Solver *solv, int level, Queue *decisionq)
4488 {
4489   Id p;
4490   int i;
4491
4492   queue_empty(decisionq);
4493   for (i = 0; i < solv->decisionq.count; i++)
4494     {
4495       p = solv->decisionq.elements[i];
4496       if (p < 0)
4497         p = -p;
4498       if (solv->decisionmap[p] == level || solv->decisionmap[p] == -level)
4499         break;
4500     }
4501   if (i == solv->decisionq.count)
4502     return;
4503   for (i = 0; i < solv->decisionq.count; i++)
4504     {
4505       p = solv->decisionq.elements[i];
4506       if (p < 0)
4507         p = -p;
4508       if (solv->decisionmap[p] == level || solv->decisionmap[p] == -level)
4509         queue_push(decisionq, p);
4510       else
4511         break;
4512     }
4513 }
4514
4515 int
4516 solver_describe_decision(Solver *solv, Id p, Id *infop)
4517 {
4518   int i;
4519   Id pp, why;
4520
4521   if (infop)
4522     *infop = 0;
4523   if (!solv->decisionmap[p])
4524     return SOLVER_REASON_UNRELATED;
4525   pp = solv->decisionmap[p] < 0 ? -p : p;
4526   for (i = 0; i < solv->decisionq.count; i++)
4527     if (solv->decisionq.elements[i] == pp)
4528       break;
4529   if (i == solv->decisionq.count)       /* just in case... */
4530     return SOLVER_REASON_UNRELATED;
4531   why = solv->decisionq_why.elements[i];
4532   if (infop)
4533     *infop = why > 0 ? why : -why;
4534   if (why > 0)
4535     return SOLVER_REASON_UNIT_RULE;
4536   i = solv->decisionmap[p] >= 0 ? solv->decisionmap[p] : -solv->decisionmap[p];
4537   return solv->decisionq_reason.elements[i];
4538 }
4539
4540
4541 void
4542 solver_describe_weakdep_decision(Solver *solv, Id p, Queue *whyq)
4543 {
4544   Pool *pool = solv->pool;
4545   int i;
4546   int level = solv->decisionmap[p];
4547   int decisionno;
4548   Solvable *s;
4549
4550   queue_empty(whyq);
4551   if (level < 0)
4552     return;     /* huh? */
4553   for (decisionno = 0; decisionno < solv->decisionq.count; decisionno++)
4554     if (solv->decisionq.elements[decisionno] == p)
4555       break;
4556   if (decisionno == solv->decisionq.count)
4557     return;     /* huh? */
4558   i = solv->decisionmap[p] >= 0 ? solv->decisionmap[p] : -solv->decisionmap[p];
4559   if (solv->decisionq_reason.elements[i] != SOLVER_REASON_WEAKDEP)
4560     return;     /* huh? */
4561
4562   /* 1) list all packages that recommend us */
4563   for (i = 1; i < pool->nsolvables; i++)
4564     {
4565       Id *recp, rec, pp2, p2;
4566       if (solv->decisionmap[i] <= 0 || solv->decisionmap[i] >= level)
4567         continue;
4568       s = pool->solvables + i;
4569       if (!s->recommends)
4570         continue;
4571       if (!solv->addalreadyrecommended && s->repo == solv->installed)
4572         continue;
4573       recp = s->repo->idarraydata + s->recommends;
4574       while ((rec = *recp++) != 0)
4575         {
4576           int found = 0;
4577           FOR_PROVIDES(p2, pp2, rec)
4578             {
4579               if (p2 == p)
4580                 found = 1;
4581               else
4582                 {
4583                   /* if p2 is already installed, this recommends is ignored */
4584                   if (solv->decisionmap[p2] > 0 && solv->decisionmap[p2] < level)
4585                     break;
4586                 }
4587             }
4588           if (!p2 && found)
4589             {
4590               queue_push(whyq, SOLVER_REASON_RECOMMENDED);
4591               queue_push2(whyq, i, rec);
4592             }
4593         }
4594     }
4595   /* 2) list all supplements */
4596   s = pool->solvables + p;
4597   if (s->supplements && level > 0)
4598     {
4599       Id *supp, sup, pp2, p2;
4600       /* this is a hack. to use solver_dep_fulfilled we temporarily clear
4601        * everything above our level in the decisionmap */
4602       for (i = decisionno; i < solv->decisionq.count; i++ )
4603         {
4604           p2 = solv->decisionq.elements[i];
4605           if (p2 > 0)
4606             solv->decisionmap[p2] = -solv->decisionmap[p2];
4607         }
4608       supp = s->repo->idarraydata + s->supplements;
4609       while ((sup = *supp++) != 0)
4610         if (solver_dep_fulfilled(solv, sup))
4611           {
4612             int found = 0;
4613             /* let's see if this is an easy supp */
4614             FOR_PROVIDES(p2, pp2, sup)
4615               {
4616                 if (!solv->addalreadyrecommended && solv->installed)
4617                   {
4618                     if (pool->solvables[p2].repo == solv->installed)
4619                       continue;
4620                   }
4621                 if (solv->decisionmap[p2] > 0 && solv->decisionmap[p2] < level)
4622                   {
4623                     queue_push(whyq, SOLVER_REASON_SUPPLEMENTED);
4624                     queue_push2(whyq, p2, sup);
4625                     found = 1;
4626                   }
4627               }
4628             if (!found)
4629               {
4630                 /* hard case, just note dependency with no package */
4631                 queue_push(whyq, SOLVER_REASON_SUPPLEMENTED);
4632                 queue_push2(whyq, 0, sup);
4633               }
4634           }
4635       for (i = decisionno; i < solv->decisionq.count; i++)
4636         {
4637           p2 = solv->decisionq.elements[i];
4638           if (p2 > 0)
4639             solv->decisionmap[p2] = -solv->decisionmap[p2];
4640         }
4641     }
4642 }
4643
4644 void
4645 pool_job2solvables(Pool *pool, Queue *pkgs, Id how, Id what)
4646 {
4647   Id p, pp;
4648   how &= SOLVER_SELECTMASK;
4649   queue_empty(pkgs);
4650   if (how == SOLVER_SOLVABLE_ALL)
4651     {
4652       FOR_POOL_SOLVABLES(p)
4653         queue_push(pkgs, p);
4654     }
4655   else if (how == SOLVER_SOLVABLE_REPO)
4656     {
4657       Repo *repo = pool_id2repo(pool, what);
4658       Solvable *s;
4659       if (repo)
4660         {
4661           FOR_REPO_SOLVABLES(repo, p, s)
4662             queue_push(pkgs, p);
4663         }
4664     }
4665   else
4666     {
4667       FOR_JOB_SELECT(p, pp, how, what)
4668         queue_push(pkgs, p);
4669     }
4670 }
4671
4672 int
4673 pool_isemptyupdatejob(Pool *pool, Id how, Id what)
4674 {
4675   Id p, pp, pi, pip;
4676   Id select = how & SOLVER_SELECTMASK;
4677   if ((how & SOLVER_JOBMASK) != SOLVER_UPDATE)
4678     return 0;
4679   if (select == SOLVER_SOLVABLE_ALL || select == SOLVER_SOLVABLE_REPO)
4680     return 0;
4681   if (!pool->installed)
4682     return 1;
4683   FOR_JOB_SELECT(p, pp, select, what)
4684     if (pool->solvables[p].repo == pool->installed)
4685       return 0;
4686   /* hard work */
4687   FOR_JOB_SELECT(p, pp, select, what)
4688     {
4689       Solvable *s = pool->solvables + p;
4690       FOR_PROVIDES(pi, pip, s->name)
4691         {
4692           Solvable *si = pool->solvables + pi;
4693           if (si->repo != pool->installed || si->name != s->name)
4694             continue;
4695           return 0;
4696         }
4697       if (s->obsoletes)
4698         {
4699           Id obs, *obsp = s->repo->idarraydata + s->obsoletes;
4700           while ((obs = *obsp++) != 0)
4701             {
4702               FOR_PROVIDES(pi, pip, obs)
4703                 {
4704                   Solvable *si = pool->solvables + pi;
4705                   if (si->repo != pool->installed)
4706                     continue;
4707                   if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, si, obs))
4708                     continue;
4709                   if (pool->obsoleteusescolors && !pool_colormatch(pool, s, si))
4710                     continue;
4711                   return 0;
4712                 }
4713             }
4714         }
4715     }
4716   return 1;
4717 }
4718
4719 static int
4720 get_userinstalled_cmp(const void *ap, const void *bp, void *dp)
4721 {
4722   return *(Id *)ap - *(Id *)bp;
4723 }
4724
4725 static int
4726 get_userinstalled_cmp_names(const void *ap, const void *bp, void *dp)
4727 {
4728   Pool *pool = dp;
4729   return strcmp(pool_id2str(pool, *(Id *)ap), pool_id2str(pool, *(Id *)bp));
4730 }
4731
4732 static int
4733 get_userinstalled_cmp_namearch(const void *ap, const void *bp, void *dp)
4734 {
4735   Pool *pool = dp;
4736   int r;
4737   r = strcmp(pool_id2str(pool, ((Id *)ap)[0]), pool_id2str(pool, ((Id *)bp)[0]));
4738   if (r)
4739     return r;
4740   return strcmp(pool_id2str(pool, ((Id *)ap)[1]), pool_id2str(pool, ((Id *)bp)[1]));
4741 }
4742
4743 static void
4744 get_userinstalled_sort_uniq(Pool *pool, Queue *q, int flags)
4745 {
4746   Id lastp = -1, lasta = -1;
4747   int i, j;
4748   if (q->count < ((flags & GET_USERINSTALLED_NAMEARCH) ? 4 : 2))
4749     return;
4750   if ((flags & GET_USERINSTALLED_NAMEARCH) != 0)
4751     solv_sort(q->elements, q->count / 2, 2 * sizeof(Id), get_userinstalled_cmp_namearch, pool);
4752   else if ((flags & GET_USERINSTALLED_NAMES) != 0)
4753     solv_sort(q->elements, q->count, sizeof(Id), get_userinstalled_cmp_names, pool);
4754   else
4755     solv_sort(q->elements, q->count, sizeof(Id), get_userinstalled_cmp, 0);
4756   if ((flags & GET_USERINSTALLED_NAMEARCH) != 0)
4757     {
4758       for (i = j = 0; i < q->count; i += 2)
4759         if (q->elements[i] != lastp || q->elements[i + 1] != lasta)
4760           {
4761             q->elements[j++] = lastp = q->elements[i];
4762             q->elements[j++] = lasta = q->elements[i + 1];
4763           }
4764     }
4765   else
4766     {
4767       for (i = j = 0; i < q->count; i++)
4768         if (q->elements[i] != lastp)
4769           q->elements[j++] = lastp = q->elements[i];
4770     }
4771   queue_truncate(q, j);
4772 }
4773
4774 static void
4775 namearch2solvables(Pool *pool, Queue *q, Queue *qout, int job)
4776 {
4777   int i;
4778   if (!pool->installed)
4779     return;
4780   for (i = 0; i < q->count; i += 2)
4781     {
4782       Id p, pp, name = q->elements[i], arch = q->elements[i + 1];
4783       FOR_PROVIDES(p, pp, name)
4784         {
4785           Solvable *s = pool->solvables + p;
4786           if (s->repo != pool->installed || s->name != name || (arch && s->arch != arch))
4787             continue;
4788           if (job)
4789             queue_push(qout, job);
4790           queue_push(qout, p);
4791         }
4792     }
4793 }
4794
4795 void
4796 solver_get_userinstalled(Solver *solv, Queue *q, int flags)
4797 {
4798   Pool *pool = solv->pool;
4799   Id p, p2, pp;
4800   Solvable *s;
4801   Repo *installed = solv->installed;
4802   int i, j;
4803   Map userinstalled;
4804
4805   map_init(&userinstalled, 0);
4806   queue_empty(q);
4807   /* first process jobs */
4808   for (i = 0; i < solv->job.count; i += 2)
4809     {
4810       Id how = solv->job.elements[i];
4811       Id what, select;
4812       if (installed && (how & SOLVER_JOBMASK) == SOLVER_USERINSTALLED)
4813         {
4814           if (!userinstalled.size)
4815             map_grow(&userinstalled, installed->end - installed->start);
4816           what = solv->job.elements[i + 1];
4817           select = how & SOLVER_SELECTMASK;
4818           if (select == SOLVER_SOLVABLE_ALL || (select == SOLVER_SOLVABLE_REPO && what == installed->repoid))
4819             {
4820               FOR_REPO_SOLVABLES(installed, p, s)
4821                 MAPSET(&userinstalled, p - installed->start);
4822             }
4823           FOR_JOB_SELECT(p, pp, select, what)
4824             if (pool->solvables[p].repo == installed)
4825               MAPSET(&userinstalled, p - installed->start);
4826           continue;
4827         }
4828       if ((how & SOLVER_JOBMASK) != SOLVER_INSTALL)
4829         continue;
4830       if ((how & SOLVER_NOTBYUSER) != 0)
4831         continue;
4832       what = solv->job.elements[i + 1];
4833       select = how & SOLVER_SELECTMASK;
4834       FOR_JOB_SELECT(p, pp, select, what)
4835         if (solv->decisionmap[p] > 0)
4836           {
4837             queue_push(q, p);
4838 #ifdef ENABLE_LINKED_PKGS
4839             if (has_package_link(pool, pool->solvables + p))
4840               {
4841                 int j;
4842                 Queue lq;
4843                 queue_init(&lq);
4844                 find_package_link(pool, pool->solvables + p, 0, &lq, 0, 0);
4845                 for (j = 0; j < lq.count; j++)
4846                   if (solv->decisionmap[lq.elements[j]] > 0)
4847                     queue_push(q, lq.elements[j]);
4848               }
4849 #endif
4850           }
4851     }
4852   /* now process updates of userinstalled packages */
4853   if (installed && userinstalled.size)
4854     {
4855       for (i = 1; i < solv->decisionq.count; i++)
4856         {
4857           p = solv->decisionq.elements[i];
4858           if (p <= 0)
4859             continue;
4860           s = pool->solvables + p;
4861           if (!s->repo)
4862             continue;
4863           if (s->repo == installed)
4864             {
4865               if (MAPTST(&userinstalled, p - installed->start))
4866                 queue_push(q, p);
4867               continue;
4868             }
4869           /* new package, check if we replace a userinstalled one */
4870           FOR_PROVIDES(p2, pp, s->name)
4871             {
4872               Solvable *ps = pool->solvables + p2;
4873               if (p2 == p || ps->repo != installed || !MAPTST(&userinstalled, p2 - installed->start))
4874                 continue;
4875               if (!pool->implicitobsoleteusesprovides && s->name != ps->name)
4876                 continue;
4877               if (pool->implicitobsoleteusescolors && !pool_colormatch(pool, s, ps))
4878                 continue;
4879               queue_push(q, p);
4880               break;
4881             }
4882           if (!p2 && s->repo != installed && s->obsoletes)
4883             {
4884               Id obs, *obsp = s->repo->idarraydata + s->obsoletes;
4885               while ((obs = *obsp++) != 0)
4886                 {
4887                   FOR_PROVIDES(p2, pp, obs)
4888                     {
4889                       Solvable *ps = pool->solvables + p2;
4890                       if (p2 == p || ps->repo != installed || !MAPTST(&userinstalled, p2 - installed->start))
4891                         continue;
4892                       if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
4893                         continue;
4894                       if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
4895                         continue;
4896                       queue_push(q, p);
4897                       break;
4898                     }
4899                   if (p2)
4900                     break;
4901                 }
4902             }
4903         }
4904     }
4905   map_free(&userinstalled);
4906
4907   /* convert to desired output format */
4908   if ((flags & GET_USERINSTALLED_NAMEARCH) != 0)
4909     {
4910       int qcount = q->count;
4911       queue_insertn(q, 0, qcount, 0);
4912       for (i = j = 0; i < qcount; i++)
4913         {
4914           s = pool->solvables + q->elements[i + qcount];
4915           q->elements[j++] = s->name;
4916           q->elements[j++] = s->arch;
4917         }
4918     }
4919   else if ((flags & GET_USERINSTALLED_NAMES) != 0)
4920     {
4921       for (i = 0; i < q->count; i++)
4922         {
4923           s = pool->solvables + q->elements[i];
4924           q->elements[i] = s->name;
4925         }
4926     }
4927   /* sort and unify */
4928   get_userinstalled_sort_uniq(pool, q, flags);
4929
4930   /* invert if asked for */
4931   if ((flags & GET_USERINSTALLED_INVERTED) != 0)
4932     {
4933       /* first generate queue with all installed packages */
4934       Queue invq;
4935       queue_init(&invq);
4936       for (i = 1; i < solv->decisionq.count; i++)
4937         {
4938           p = solv->decisionq.elements[i];
4939           if (p <= 0)
4940             continue;
4941           s = pool->solvables + p;
4942           if (!s->repo)
4943             continue;
4944           if ((flags & GET_USERINSTALLED_NAMEARCH) != 0)
4945             queue_push2(&invq, s->name, s->arch);
4946           else if ((flags & GET_USERINSTALLED_NAMES) != 0)
4947             queue_push(&invq, s->name);
4948           else
4949             queue_push(&invq, p);
4950         }
4951       /* push q on invq, just in case... */
4952       queue_insertn(&invq, invq.count, q->count, q->elements);
4953       get_userinstalled_sort_uniq(pool, &invq, flags);
4954       /* subtract queues (easy as they are sorted and invq is a superset of q) */
4955       if ((flags & GET_USERINSTALLED_NAMEARCH) != 0)
4956         {
4957           if (q->count)
4958             {
4959               for (i = j = 0; i < invq.count; i += 2)
4960                 if (invq.elements[i] == q->elements[j] && invq.elements[i + 1] == q->elements[j + 1])
4961                   {
4962                     invq.elements[i] = invq.elements[i + 1] = 0;
4963                     j += 2;
4964                     if (j >= q->count)
4965                       break;
4966                   }
4967               queue_empty(q);
4968             }
4969           for (i = 0; i < invq.count; i += 2)
4970             if (invq.elements[i])
4971               queue_push2(q, invq.elements[i], invq.elements[i + 1]);
4972         }
4973       else
4974         {
4975           if (q->count)
4976             {
4977               for (i = j = 0; i < invq.count; i++)
4978                 if (invq.elements[i] == q->elements[j])
4979                   {
4980                     invq.elements[i] = 0;
4981                     if (++j >= q->count)
4982                       break;
4983                   }
4984               queue_empty(q);
4985             }
4986           for (i = 0; i < invq.count; i++)
4987             if (invq.elements[i])
4988               queue_push(q, invq.elements[i]);
4989         }
4990       queue_free(&invq);
4991     }
4992 }
4993
4994 void
4995 pool_add_userinstalled_jobs(Pool *pool, Queue *q, Queue *job, int flags)
4996 {
4997   int i;
4998
4999   if ((flags & GET_USERINSTALLED_INVERTED) != 0)
5000     {
5001       Queue invq;
5002       Id p, lastid;
5003       Solvable *s;
5004       int bad;
5005       if (!pool->installed)
5006         return;
5007       queue_init(&invq);
5008       if ((flags & GET_USERINSTALLED_NAMEARCH) != 0)
5009         flags &= ~GET_USERINSTALLED_NAMES;      /* just in case */
5010       FOR_REPO_SOLVABLES(pool->installed, p, s)
5011         queue_push(&invq, flags & GET_USERINSTALLED_NAMES ? s->name : p);
5012       if ((flags & GET_USERINSTALLED_NAMEARCH) != 0)
5013         {
5014           /* for namearch we convert to packages */
5015           namearch2solvables(pool, q, &invq, 0);
5016           get_userinstalled_sort_uniq(pool, &invq, flags);
5017           namearch2solvables(pool, q, &invq, 0);
5018           flags = 0;
5019         }
5020       else
5021         {
5022           queue_insertn(&invq, invq.count, q->count, q->elements);
5023           get_userinstalled_sort_uniq(pool, &invq, flags);
5024           /* now the fun part, add q again, sort, and remove all dups */
5025           queue_insertn(&invq, invq.count, q->count, q->elements);
5026         }
5027       if (invq.count > 1)
5028         {
5029           if ((flags & GET_USERINSTALLED_NAMES) != 0)
5030             solv_sort(invq.elements, invq.count, sizeof(Id), get_userinstalled_cmp_names, pool);
5031           else
5032             solv_sort(invq.elements, invq.count, sizeof(Id), get_userinstalled_cmp, 0);
5033         }
5034       lastid = -1;
5035       bad = 1;
5036       for (i = 0; i < invq.count; i++)
5037         {
5038           if (invq.elements[i] == lastid)
5039             {
5040               bad = 1;
5041               continue;
5042             }
5043           if (!bad)
5044             queue_push2(job, SOLVER_USERINSTALLED | (flags & GET_USERINSTALLED_NAMES ? SOLVER_SOLVABLE_NAME : SOLVER_SOLVABLE), lastid);
5045           bad = 0;
5046           lastid = invq.elements[i];
5047         }
5048       if (!bad)
5049         queue_push2(job, SOLVER_USERINSTALLED | (flags & GET_USERINSTALLED_NAMES ? SOLVER_SOLVABLE_NAME : SOLVER_SOLVABLE), lastid);
5050       queue_free(&invq);
5051     }
5052   else
5053     {
5054       if (flags & GET_USERINSTALLED_NAMEARCH)
5055         namearch2solvables(pool, q, job, SOLVER_USERINSTALLED | SOLVER_SOLVABLE);
5056       else
5057         {
5058           for (i = 0; i < q->count; i++)
5059             queue_push2(job, SOLVER_USERINSTALLED | (flags & GET_USERINSTALLED_NAMES ? SOLVER_SOLVABLE_NAME : SOLVER_SOLVABLE), q->elements[i]);
5060         }
5061     }
5062 }
5063
5064 int
5065 solver_alternatives_count(Solver *solv)
5066 {
5067   Id *elements = solv->branches.elements;
5068   int res, count;
5069   for (res = 0, count = solv->branches.count; count; res++)
5070     count -= elements[count - 2];
5071   return res;
5072 }
5073
5074 int
5075 solver_get_alternative(Solver *solv, Id alternative, Id *idp, Id *fromp, Id *chosenp, Queue *choices, int *levelp)
5076 {
5077   int cnt = solver_alternatives_count(solv);
5078   int count = solv->branches.count;
5079   Id *elements = solv->branches.elements;
5080   if (choices)
5081     queue_empty(choices);
5082   if (alternative <= 0 || alternative > cnt)
5083     return 0;
5084   elements += count;
5085   for (; cnt > alternative; cnt--)
5086     elements -= elements[-2];
5087   if (levelp)
5088     *levelp = elements[-1];
5089   if (fromp)
5090     *fromp = elements[-4];
5091   if (idp)
5092     *idp = elements[-3];
5093   if (chosenp)
5094     {
5095       int i;
5096       *chosenp = 0;
5097       for (i = elements[-2]; i > 4; i--)
5098         {
5099           Id p = -elements[-i];
5100           if (p > 0 && solv->decisionmap[p] == elements[-1] + 1)
5101             {
5102               *chosenp = p;
5103               break;
5104             }
5105         }
5106     }
5107   if (choices)
5108     queue_insertn(choices, 0, elements[-2] - 4, elements - elements[-2]);
5109   return elements[-4] ? SOLVER_ALTERNATIVE_TYPE_RECOMMENDS : SOLVER_ALTERNATIVE_TYPE_RULE;
5110 }
5111
5112 const char *
5113 solver_select2str(Pool *pool, Id select, Id what)
5114 {
5115   const char *s;
5116   char *b;
5117   select &= SOLVER_SELECTMASK;
5118   if (select == SOLVER_SOLVABLE)
5119     return pool_solvid2str(pool, what);
5120   if (select == SOLVER_SOLVABLE_NAME)
5121     return pool_dep2str(pool, what);
5122   if (select == SOLVER_SOLVABLE_PROVIDES)
5123     {
5124       s = pool_dep2str(pool, what);
5125       b = pool_alloctmpspace(pool, 11 + strlen(s));
5126       sprintf(b, "providing %s", s);
5127       return b;
5128     }
5129   if (select == SOLVER_SOLVABLE_ONE_OF)
5130     {
5131       Id p;
5132       b = 0;
5133       while ((p = pool->whatprovidesdata[what++]) != 0)
5134         {
5135           s = pool_solvid2str(pool, p);
5136           if (b)
5137             b = pool_tmpappend(pool, b, ", ", s);
5138           else
5139             b = pool_tmpjoin(pool, s, 0, 0);
5140           pool_freetmpspace(pool, s);
5141         }
5142       return b ? b : "nothing";
5143     }
5144   if (select == SOLVER_SOLVABLE_REPO)
5145     {
5146       b = pool_alloctmpspace(pool, 20);
5147       sprintf(b, "repo #%d", what);
5148       return b;
5149     }
5150   if (select == SOLVER_SOLVABLE_ALL)
5151     return "all packages";
5152   return "unknown job select";
5153 }
5154
5155 const char *
5156 pool_job2str(Pool *pool, Id how, Id what, Id flagmask)
5157 {
5158   Id select = how & SOLVER_SELECTMASK;
5159   const char *strstart = 0, *strend = 0;
5160   char *s;
5161   int o;
5162
5163   switch (how & SOLVER_JOBMASK)
5164     {
5165     case SOLVER_NOOP:
5166       return "do nothing";
5167     case SOLVER_INSTALL:
5168       if (select == SOLVER_SOLVABLE && pool->installed && pool->solvables[what].repo == pool->installed)
5169         strstart = "keep ", strend = " installed";
5170       else if (select == SOLVER_SOLVABLE || select == SOLVER_SOLVABLE_NAME)
5171         strstart = "install ";
5172       else if (select == SOLVER_SOLVABLE_PROVIDES)
5173         strstart = "install a package ";
5174       else
5175         strstart = "install one of ";
5176       break;
5177     case SOLVER_ERASE:
5178       if (select == SOLVER_SOLVABLE && !(pool->installed && pool->solvables[what].repo == pool->installed))
5179         strstart = "keep ", strend = " uninstalled";
5180       else if (select == SOLVER_SOLVABLE_PROVIDES)
5181         strstart = "deinstall all packages ";
5182       else
5183         strstart = "deinstall ";
5184       break;
5185     case SOLVER_UPDATE:
5186       strstart = "update ";
5187       break;
5188     case SOLVER_WEAKENDEPS:
5189       strstart = "weaken deps of ";
5190       break;
5191     case SOLVER_MULTIVERSION:
5192       strstart = "multi version ";
5193       break;
5194     case SOLVER_LOCK:
5195       strstart = "lock ";
5196       break;
5197     case SOLVER_DISTUPGRADE:
5198       strstart = "dist upgrade ";
5199       break;
5200     case SOLVER_VERIFY:
5201       strstart = "verify ";
5202       break;
5203     case SOLVER_DROP_ORPHANED:
5204       strstart = "deinstall ", strend = " if orphaned";
5205       break;
5206     case SOLVER_USERINSTALLED:
5207       strstart = "regard ", strend = " as userinstalled";
5208       break;
5209     case SOLVER_ALLOWUNINSTALL:
5210       strstart = "allow deinstallation of ";
5211       break;
5212     case SOLVER_FAVOR:
5213       strstart = "favor ";
5214       break;
5215     case SOLVER_DISFAVOR:
5216       strstart = "disfavor ";
5217       break;
5218     default:
5219       strstart = "unknown job ";
5220       break;
5221     }
5222   s = pool_tmpjoin(pool, strstart, solver_select2str(pool, select, what), strend);
5223   how &= flagmask;
5224   if ((how & ~(SOLVER_SELECTMASK|SOLVER_JOBMASK)) == 0)
5225     return s;
5226   o = strlen(s);
5227   s = pool_tmpappend(pool, s, " ", 0);
5228   if (how & SOLVER_WEAK)
5229     s = pool_tmpappend(pool, s, ",weak", 0);
5230   if (how & SOLVER_ESSENTIAL)
5231     s = pool_tmpappend(pool, s, ",essential", 0);
5232   if (how & SOLVER_CLEANDEPS)
5233     s = pool_tmpappend(pool, s, ",cleandeps", 0);
5234   if (how & SOLVER_ORUPDATE)
5235     s = pool_tmpappend(pool, s, ",orupdate", 0);
5236   if (how & SOLVER_FORCEBEST)
5237     s = pool_tmpappend(pool, s, ",forcebest", 0);
5238   if (how & SOLVER_TARGETED)
5239     s = pool_tmpappend(pool, s, ",targeted", 0);
5240   if (how & SOLVER_SETEV)
5241     s = pool_tmpappend(pool, s, ",setev", 0);
5242   if (how & SOLVER_SETEVR)
5243     s = pool_tmpappend(pool, s, ",setevr", 0);
5244   if (how & SOLVER_SETARCH)
5245     s = pool_tmpappend(pool, s, ",setarch", 0);
5246   if (how & SOLVER_SETVENDOR)
5247     s = pool_tmpappend(pool, s, ",setvendor", 0);
5248   if (how & SOLVER_SETREPO)
5249     s = pool_tmpappend(pool, s, ",setrepo", 0);
5250   if (how & SOLVER_SETNAME)
5251     s = pool_tmpappend(pool, s, ",setname", 0);
5252   if (how & SOLVER_NOAUTOSET)
5253     s = pool_tmpappend(pool, s, ",noautoset", 0);
5254   if (s[o + 1] != ',')
5255     s = pool_tmpappend(pool, s, ",?", 0);
5256   s[o + 1] = '[';
5257   return pool_tmpappend(pool, s, "]", 0);
5258 }
5259
5260 const char *
5261 solver_alternative2str(Solver *solv, int type, Id id, Id from)
5262 {
5263   Pool *pool = solv->pool;
5264   if (type == SOLVER_ALTERNATIVE_TYPE_RECOMMENDS)
5265     {
5266       const char *s = pool_dep2str(pool, id);
5267       return pool_tmpappend(pool, s, ", recommended by ", pool_solvid2str(pool, from));
5268     }
5269   if (type == SOLVER_ALTERNATIVE_TYPE_RULE)
5270     {
5271       int rtype;
5272       Id depfrom, depto, dep;
5273       char buf[64];
5274       if (solver_ruleclass(solv, id) == SOLVER_RULE_CHOICE)
5275         id = solver_rule2pkgrule(solv, id);
5276       rtype = solver_ruleinfo(solv, id, &depfrom, &depto, &dep);
5277       if ((rtype & SOLVER_RULE_TYPEMASK) == SOLVER_RULE_JOB)
5278         {
5279           if ((depto & SOLVER_SELECTMASK) == SOLVER_SOLVABLE_PROVIDES)
5280             return pool_dep2str(pool, dep);
5281           return solver_select2str(pool, depto & SOLVER_SELECTMASK, dep);
5282         }
5283       if (rtype == SOLVER_RULE_PKG_REQUIRES)
5284         {
5285           const char *s = pool_dep2str(pool, dep);
5286           return pool_tmpappend(pool, s, ", required by ", pool_solvid2str(pool, depfrom));
5287         }
5288       sprintf(buf, "Rule #%d", id);
5289       return pool_tmpjoin(pool, buf, 0, 0);
5290     }
5291   return "unknown alternative type";
5292 }
5293