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