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