src/solver.c

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