src/solver.c

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