src/solver.c

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