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