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 "solverdebug.h"
  27
  28 #define RULES_BLOCK 63
  29
  30 /********************************************************************
  31  *
  32  * dependency check helpers
  33  *
  34  */
  35
  36 /*-------------------------------------------------------------------
  37  * handle split provides
  38  *
  39  * a splitprovides dep looks like
  40  *     namespace:splitprovides(pkg REL_WITH path)
  41  * and is only true if pkg is installed and contains the specified path.
  42  * we also make sure that pkg is selected for an update, otherwise the
  43  * update would always be forced onto the user.
  44  */
  45 int
  46 solver_splitprovides(Solver *solv, Id dep)
  47 {
  48   Pool *pool = solv->pool;
  49   Id p, pp;
  50   Reldep *rd;
  51   Solvable *s;
  52
  53   if (!solv->dosplitprovides || !solv->installed || (!solv->updatemap_all && !solv->updatemap.size))
  54     return 0;
  55   if (!ISRELDEP(dep))
  56     return 0;
  57   rd = GETRELDEP(pool, dep);
  58   if (rd->flags != REL_WITH)
  59     return 0;
  60   FOR_PROVIDES(p, pp, dep)
  61     {
  62       /* here we have packages that provide the correct name and contain the path,
  63        * now do extra filtering */
  64       s = pool->solvables + p;
  65       if (s->repo == solv->installed && s->name == rd->name &&
  66           (solv->updatemap_all || (solv->updatemap.size && MAPTST(&solv->updatemap, p - solv->installed->start))))
  67         return 1;
  68     }
  69   return 0;
  70 }
  71
  72
  73 /*-------------------------------------------------------------------
  74  * solver_dep_installed
  75  */
  76
  77 int
  78 solver_dep_installed(Solver *solv, Id dep)
  79 {
  80 #if 0
  81   Pool *pool = solv->pool;
  82   Id p, pp;
  83
  84   if (ISRELDEP(dep))
  85     {
  86       Reldep *rd = GETRELDEP(pool, dep);
  87       if (rd->flags == REL_AND)
  88         {
  89           if (!solver_dep_installed(solv, rd->name))
  90             return 0;
  91           return solver_dep_installed(solv, rd->evr);
  92         }
  93       if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
  94         return solver_dep_installed(solv, rd->evr);
  95     }
  96   FOR_PROVIDES(p, pp, dep)
  97     {
  98       if (p == SYSTEMSOLVABLE || (solv->installed && pool->solvables[p].repo == solv->installed))
  99         return 1;
 100     }
 101 #endif
 102   return 0;
 103 }
 104
 105
 106 static Id
 107 autouninstall(Solver *solv, Id *problem)
 108 {
 109   Pool *pool = solv->pool;
 110   int i;
 111   int lastfeature = 0, lastupdate = 0;
 112   Id v;
 113   Id extraflags = -1;
 114
 115   for (i = 0; (v = problem[i]) != 0; i++)
 116     {
 117       if (v < 0)
 118         extraflags &= solv->job.elements[-v - 1];
 119       if (v >= solv->featurerules && v < solv->featurerules_end)
 120         if (v > lastfeature)
 121           lastfeature = v;
 122       if (v >= solv->updaterules && v < solv->updaterules_end)
 123         {
 124           /* check if identical to feature rule */
 125           Id p = solv->rules[v].p;
 126           if (p <= 0)
 127             continue;
 128           Rule *r = solv->rules + solv->featurerules + (p - solv->installed->start);
 129           if (!r->p)
 130             {
 131               /* update rule == feature rule */
 132               if (v > lastfeature)
 133                 lastfeature = v;
 134               continue;
 135             }
 136           if (v > lastupdate)
 137             lastupdate = v;
 138         }
 139     }
 140   if (!lastupdate && !lastfeature)
 141     return 0;
 142   v = lastupdate ? lastupdate : lastfeature;
 143   POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "allowuninstall disabling ");
 144   solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE, solv->rules + v);
 145   solver_disableproblem(solv, v);
 146   if (extraflags != -1 && (extraflags & SOLVER_CLEANDEPS) != 0 && solv->cleandepsmap.size)
 147     {
 148       /* add the package to the updatepkgs list, this will automatically turn
 149        * on cleandeps mode */
 150       Id p = solv->rules[v].p;
 151       if (!solv->cleandeps_updatepkgs)
 152         {
 153           solv->cleandeps_updatepkgs = solv_calloc(1, sizeof(Queue));
 154           queue_init(solv->cleandeps_updatepkgs);
 155         }
 156       if (p > 0)
 157         {
 158           int oldupdatepkgscnt = solv->cleandeps_updatepkgs->count;
 159           queue_pushunique(solv->cleandeps_updatepkgs, p);
 160           if (solv->cleandeps_updatepkgs->count != oldupdatepkgscnt)
 161             solver_disablepolicyrules(solv);
 162         }
 163     }
 164   return v;
 165 }
 166
 167 /************************************************************************/
 168
 169 /*
 170  * enable/disable learnt rules
 171  *
 172  * we have enabled or disabled some of our rules. We now reenable all
 173  * of our learnt rules except the ones that were learnt from rules that
 174  * are now disabled.
 175  */
 176 static void
 177 enabledisablelearntrules(Solver *solv)
 178 {
 179   Pool *pool = solv->pool;
 180   Rule *r;
 181   Id why, *whyp;
 182   int i;
 183
 184   POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "enabledisablelearntrules called\n");
 185   for (i = solv->learntrules, r = solv->rules + i; i < solv->nrules; i++, r++)
 186     {
 187       whyp = solv->learnt_pool.elements + solv->learnt_why.elements[i - solv->learntrules];
 188       while ((why = *whyp++) != 0)
 189         {
 190           assert(why > 0 && why < i);
 191           if (solv->rules[why].d < 0)
 192             break;
 193         }
 194       /* why != 0: we found a disabled rule, disable the learnt rule */
 195       if (why && r->d >= 0)
 196         {
 197           IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS)
 198             {
 199               POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "disabling ");
 200               solver_printruleclass(solv, SOLV_DEBUG_SOLUTIONS, r);
 201             }
 202           solver_disablerule(solv, r);
 203         }
 204       else if (!why && r->d < 0)
 205         {
 206           IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS)
 207             {
 208               POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "re-enabling ");
 209               solver_printruleclass(solv, SOLV_DEBUG_SOLUTIONS, r);
 210             }
 211           solver_enablerule(solv, r);
 212         }
 213     }
 214 }
 215
 216
 217 /*
 218  * make assertion rules into decisions
 219  *
 220  * Go through rules and add direct assertions to the decisionqueue.
 221  * If we find a conflict, disable rules and add them to problem queue.
 222  */
 223
 224 static void
 225 makeruledecisions(Solver *solv)
 226 {
 227   Pool *pool = solv->pool;
 228   int i, ri, ii;
 229   Rule *r, *rr;
 230   Id v, vv;
 231   int decisionstart;
 232   int record_proof = 1;
 233   int oldproblemcount;
 234   int havedisabled = 0;
 235
 236   /* The system solvable is always installed first */
 237   assert(solv->decisionq.count == 0);
 238   queue_push(&solv->decisionq, SYSTEMSOLVABLE);
 239   queue_push(&solv->decisionq_why, 0);
 240   solv->decisionmap[SYSTEMSOLVABLE] = 1;        /* installed at level '1' */
 241
 242   decisionstart = solv->decisionq.count;
 243   for (;;)
 244     {
 245       /* if we needed to re-run, back up decisions to decisionstart */
 246       while (solv->decisionq.count > decisionstart)
 247         {
 248           v = solv->decisionq.elements[--solv->decisionq.count];
 249           --solv->decisionq_why.count;
 250           vv = v > 0 ? v : -v;
 251           solv->decisionmap[vv] = 0;
 252         }
 253
 254       /* note that the ruleassertions queue is ordered */
 255       for (ii = 0; ii < solv->ruleassertions.count; ii++)
 256         {
 257           ri = solv->ruleassertions.elements[ii];
 258           r = solv->rules + ri;
 259
 260           if (havedisabled && ri >= solv->learntrules)
 261             {
 262               /* just started with learnt rule assertions. If we have disabled
 263                * some rules, adapt the learnt rule status */
 264               enabledisablelearntrules(solv);
 265               havedisabled = 0;
 266             }
 267
 268           if (r->d < 0 || !r->p || r->w2)       /* disabled, dummy or no assertion */
 269             continue;
 270
 271           /* do weak rules in phase 2 */
 272           if (ri < solv->learntrules && MAPTST(&solv->weakrulemap, ri))
 273             continue;
 274
 275           v = r->p;
 276           vv = v > 0 ? v : -v;
 277
 278           if (!solv->decisionmap[vv])          /* if not yet decided */
 279             {
 280               queue_push(&solv->decisionq, v);
 281               queue_push(&solv->decisionq_why, r - solv->rules);
 282               solv->decisionmap[vv] = v > 0 ? 1 : -1;
 283               IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
 284                 {
 285                   Solvable *s = solv->pool->solvables + vv;
 286                   if (v < 0)
 287                     POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "conflicting %s (assertion)\n", pool_solvable2str(solv->pool, s));
 288                   else
 289                     POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "installing  %s (assertion)\n", pool_solvable2str(solv->pool, s));
 290                 }
 291               continue;
 292             }
 293
 294           /* check against previous decision: is there a conflict? */
 295           if (v > 0 && solv->decisionmap[vv] > 0)    /* ok to install */
 296             continue;
 297           if (v < 0 && solv->decisionmap[vv] < 0)    /* ok to remove */
 298             continue;
 299
 300           /*
 301            * found a conflict!
 302            *
 303            * The rule (r) we're currently processing says something
 304            * different (v = r->p) than a previous decision (decisionmap[abs(v)])
 305            * on this literal
 306            */
 307
 308           if (ri >= solv->learntrules)
 309             {
 310               /* conflict with a learnt rule */
 311               /* can happen when packages cannot be installed for multiple reasons. */
 312               /* we disable the learnt rule in this case */
 313               /* (XXX: we should really call analyze_unsolvable_rule here!) */
 314               solver_disablerule(solv, r);
 315               continue;
 316             }
 317
 318           /*
 319            * find the decision which is the "opposite" of the rule
 320            */
 321           for (i = 0; i < solv->decisionq.count; i++)
 322             if (solv->decisionq.elements[i] == -v)
 323               break;
 324           assert(i < solv->decisionq.count);         /* assert that we found it */
 325           oldproblemcount = solv->problems.count;
 326
 327           /*
 328            * conflict with system solvable ?
 329            */
 330           if (v == -SYSTEMSOLVABLE)
 331             {
 332               if (record_proof)
 333                 {
 334                   queue_push(&solv->problems, solv->learnt_pool.count);
 335                   queue_push(&solv->learnt_pool, ri);
 336                   queue_push(&solv->learnt_pool, 0);
 337                 }
 338               else
 339                 queue_push(&solv->problems, 0);
 340               POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "conflict with system solvable, disabling rule #%d\n", ri);
 341               if  (ri >= solv->jobrules && ri < solv->jobrules_end)
 342                 v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
 343               else
 344                 v = ri;
 345               queue_push(&solv->problems, v);
 346               queue_push(&solv->problems, 0);
 347               if (solv->allowuninstall && v >= solv->featurerules && v < solv->updaterules_end)
 348                 solv->problems.count = oldproblemcount;
 349               solver_disableproblem(solv, v);
 350               havedisabled = 1;
 351               break;    /* start over */
 352             }
 353
 354           assert(solv->decisionq_why.elements[i] > 0);
 355
 356           /*
 357            * conflict with an rpm rule ?
 358            */
 359           if (solv->decisionq_why.elements[i] < solv->rpmrules_end)
 360             {
 361               if (record_proof)
 362                 {
 363                   queue_push(&solv->problems, solv->learnt_pool.count);
 364                   queue_push(&solv->learnt_pool, ri);
 365                   queue_push(&solv->learnt_pool, solv->decisionq_why.elements[i]);
 366                   queue_push(&solv->learnt_pool, 0);
 367                 }
 368               else
 369                 queue_push(&solv->problems, 0);
 370               assert(v > 0 || v == -SYSTEMSOLVABLE);
 371               POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "conflict with rpm rule, disabling rule #%d\n", ri);
 372               if (ri >= solv->jobrules && ri < solv->jobrules_end)
 373                 v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
 374               else
 375                 v = ri;
 376               queue_push(&solv->problems, v);
 377               queue_push(&solv->problems, 0);
 378               if (solv->allowuninstall && v >= solv->featurerules && v < solv->updaterules_end)
 379                 solv->problems.count = oldproblemcount;
 380               solver_disableproblem(solv, v);
 381               havedisabled = 1;
 382               break;    /* start over */
 383             }
 384
 385           /*
 386            * conflict with another job or update/feature rule
 387            */
 388
 389           /* record proof */
 390           if (record_proof)
 391             {
 392               queue_push(&solv->problems, solv->learnt_pool.count);
 393               queue_push(&solv->learnt_pool, ri);
 394               queue_push(&solv->learnt_pool, solv->decisionq_why.elements[i]);
 395               queue_push(&solv->learnt_pool, 0);
 396             }
 397           else
 398             queue_push(&solv->problems, 0);
 399
 400           POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "conflicting update/job assertions over literal %d\n", vv);
 401
 402           /*
 403            * push all of our rules (can only be feature or job rules)
 404            * asserting this literal on the problem stack
 405            */
 406           for (i = solv->featurerules, rr = solv->rules + i; i < solv->learntrules; i++, rr++)
 407             {
 408               if (rr->d < 0                          /* disabled */
 409                   || rr->w2)                         /*  or no assertion */
 410                 continue;
 411               if (rr->p != vv                        /* not affecting the literal */
 412                   && rr->p != -vv)
 413                 continue;
 414               if (MAPTST(&solv->weakrulemap, i))     /* weak: silently ignore */
 415                 continue;
 416
 417               POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, " - disabling rule #%d\n", i);
 418               solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE, solv->rules + i);
 419
 420               v = i;
 421               if (i >= solv->jobrules && i < solv->jobrules_end)
 422                 v = -(solv->ruletojob.elements[i - solv->jobrules] + 1);
 423               queue_push(&solv->problems, v);
 424             }
 425           queue_push(&solv->problems, 0);
 426
 427           if (solv->allowuninstall && (v = autouninstall(solv, solv->problems.elements + oldproblemcount + 1)) != 0)
 428             solv->problems.count = oldproblemcount;
 429
 430           for (i = oldproblemcount + 1; i < solv->problems.count - 1; i++)
 431             solver_disableproblem(solv, solv->problems.elements[i]);
 432           havedisabled = 1;
 433           break;        /* start over */
 434         }
 435       if (ii < solv->ruleassertions.count)
 436         continue;
 437
 438       /*
 439        * phase 2: now do the weak assertions
 440        */
 441       for (ii = 0; ii < solv->ruleassertions.count; ii++)
 442         {
 443           ri = solv->ruleassertions.elements[ii];
 444           r = solv->rules + ri;
 445           if (r->d < 0 || r->w2)                         /* disabled or no assertion */
 446             continue;
 447           if (ri >= solv->learntrules || !MAPTST(&solv->weakrulemap, ri))       /* skip non-weak */
 448             continue;
 449           v = r->p;
 450           vv = v > 0 ? v : -v;
 451
 452           if (!solv->decisionmap[vv])          /* if not yet decided */
 453             {
 454               queue_push(&solv->decisionq, v);
 455               queue_push(&solv->decisionq_why, r - solv->rules);
 456               solv->decisionmap[vv] = v > 0 ? 1 : -1;
 457               IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
 458                 {
 459                   Solvable *s = solv->pool->solvables + vv;
 460                   if (v < 0)
 461                     POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "conflicting %s (weak assertion)\n", pool_solvable2str(solv->pool, s));
 462                   else
 463                     POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "installing  %s (weak assertion)\n", pool_solvable2str(solv->pool, s));
 464                 }
 465               continue;
 466             }
 467           /* check against previous decision: is there a conflict? */
 468           if (v > 0 && solv->decisionmap[vv] > 0)
 469             continue;
 470           if (v < 0 && solv->decisionmap[vv] < 0)
 471             continue;
 472
 473           POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "assertion conflict, but I am weak, disabling ");
 474           solver_printrule(solv, SOLV_DEBUG_UNSOLVABLE, r);
 475
 476           if (ri >= solv->jobrules && ri < solv->jobrules_end)
 477             v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
 478           else
 479             v = ri;
 480           solver_disableproblem(solv, v);
 481           if (v < 0)
 482             solver_reenablepolicyrules(solv, -v);
 483           havedisabled = 1;
 484           break;        /* start over */
 485         }
 486       if (ii == solv->ruleassertions.count)
 487         break;  /* finished! */
 488     }
 489 }
 490
 491
 492 /********************************************************************/
 493 /* watches */
 494
 495
 496 /*-------------------------------------------------------------------
 497  * makewatches
 498  *
 499  * initial setup for all watches
 500  */
 501
 502 static void
 503 makewatches(Solver *solv)
 504 {
 505   Rule *r;
 506   int i;
 507   int nsolvables = solv->pool->nsolvables;
 508
 509   solv_free(solv->watches);
 510                                        /* lower half for removals, upper half for installs */
 511   solv->watches = solv_calloc(2 * nsolvables, sizeof(Id));
 512 #if 1
 513   /* do it reverse so rpm rules get triggered first (XXX: obsolete?) */
 514   for (i = 1, r = solv->rules + solv->nrules - 1; i < solv->nrules; i++, r--)
 515 #else
 516   for (i = 1, r = solv->rules + 1; i < solv->nrules; i++, r++)
 517 #endif
 518     {
 519       if (!r->w2)               /* assertions do not need watches */
 520         continue;
 521
 522       /* see addwatches_rule(solv, r) */
 523       r->n1 = solv->watches[nsolvables + r->w1];
 524       solv->watches[nsolvables + r->w1] = r - solv->rules;
 525
 526       r->n2 = solv->watches[nsolvables + r->w2];
 527       solv->watches[nsolvables + r->w2] = r - solv->rules;
 528     }
 529 }
 530
 531
 532 /*-------------------------------------------------------------------
 533  *
 534  * add watches (for a new learned rule)
 535  * sets up watches for a single rule
 536  *
 537  * see also makewatches() above.
 538  */
 539
 540 static inline void
 541 addwatches_rule(Solver *solv, Rule *r)
 542 {
 543   int nsolvables = solv->pool->nsolvables;
 544
 545   r->n1 = solv->watches[nsolvables + r->w1];
 546   solv->watches[nsolvables + r->w1] = r - solv->rules;
 547
 548   r->n2 = solv->watches[nsolvables + r->w2];
 549   solv->watches[nsolvables + r->w2] = r - solv->rules;
 550 }
 551
 552
 553 /********************************************************************/
 554 /*
 555  * rule propagation
 556  */
 557
 558
 559 /* shortcuts to check if a literal (positive or negative) assignment
 560  * evaluates to 'true' or 'false'
 561  */
 562 #define DECISIONMAP_TRUE(p) ((p) > 0 ? (decisionmap[p] > 0) : (decisionmap[-p] < 0))
 563 #define DECISIONMAP_FALSE(p) ((p) > 0 ? (decisionmap[p] < 0) : (decisionmap[-p] > 0))
 564 #define DECISIONMAP_UNDEF(p) (decisionmap[(p) > 0 ? (p) : -(p)] == 0)
 565
 566 /*-------------------------------------------------------------------
 567  *
 568  * propagate
 569  *
 570  * make decision and propagate to all rules
 571  *
 572  * Evaluate each term affected by the decision (linked through watches).
 573  * If we find unit rules we make new decisions based on them.
 574  *
 575  * return : 0 = everything is OK
 576  *          rule = conflict found in this rule
 577  */
 578
 579 static Rule *
 580 propagate(Solver *solv, int level)
 581 {
 582   Pool *pool = solv->pool;
 583   Id *rp, *next_rp;           /* rule pointer, next rule pointer in linked list */
 584   Rule *r;                    /* rule */
 585   Id p, pkg, other_watch;
 586   Id *dp;
 587   Id *decisionmap = solv->decisionmap;
 588
 589   Id *watches = solv->watches + pool->nsolvables;   /* place ptr in middle */
 590
 591   POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "----- propagate -----\n");
 592
 593   /* foreach non-propagated decision */
 594   while (solv->propagate_index < solv->decisionq.count)
 595     {
 596         /*
 597          * 'pkg' was just decided
 598          * negate because our watches trigger if literal goes FALSE
 599          */
 600       pkg = -solv->decisionq.elements[solv->propagate_index++];
 601
 602       IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
 603         {
 604           POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "propagate for decision %d level %d\n", -pkg, level);
 605           solver_printruleelement(solv, SOLV_DEBUG_PROPAGATE, 0, -pkg);
 606         }
 607
 608       /* foreach rule where 'pkg' is now FALSE */
 609       for (rp = watches + pkg; *rp; rp = next_rp)
 610         {
 611           r = solv->rules + *rp;
 612           if (r->d < 0)
 613             {
 614               /* rule is disabled, goto next */
 615               if (pkg == r->w1)
 616                 next_rp = &r->n1;
 617               else
 618                 next_rp = &r->n2;
 619               continue;
 620             }
 621
 622           IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
 623             {
 624               POOL_DEBUG(SOLV_DEBUG_PROPAGATE,"  watch triggered ");
 625               solver_printrule(solv, SOLV_DEBUG_PROPAGATE, r);
 626             }
 627
 628             /* 'pkg' was just decided (was set to FALSE)
 629              *
 630              *  now find other literal watch, check clause
 631              *   and advance on linked list
 632              */
 633           if (pkg == r->w1)
 634             {
 635               other_watch = r->w2;
 636               next_rp = &r->n1;
 637             }
 638           else
 639             {
 640               other_watch = r->w1;
 641               next_rp = &r->n2;
 642             }
 643
 644             /*
 645              * This term is already true (through the other literal)
 646              * so we have nothing to do
 647              */
 648           if (DECISIONMAP_TRUE(other_watch))
 649             continue;
 650
 651             /*
 652              * The other literal is FALSE or UNDEF
 653              *
 654              */
 655
 656           if (r->d)
 657             {
 658               /* Not a binary clause, try to move our watch.
 659                *
 660                * Go over all literals and find one that is
 661                *   not other_watch
 662                *   and not FALSE
 663                *
 664                * (TRUE is also ok, in that case the rule is fulfilled)
 665                */
 666               if (r->p                                /* we have a 'p' */
 667                   && r->p != other_watch              /* which is not watched */
 668                   && !DECISIONMAP_FALSE(r->p))        /* and not FALSE */
 669                 {
 670                   p = r->p;
 671                 }
 672               else                                    /* go find a 'd' to make 'true' */
 673                 {
 674                   /* foreach p in 'd'
 675                      we just iterate sequentially, doing it in another order just changes the order of decisions, not the decisions itself
 676                    */
 677                   for (dp = pool->whatprovidesdata + r->d; (p = *dp++) != 0;)
 678                     {
 679                       if (p != other_watch              /* which is not watched */
 680                           && !DECISIONMAP_FALSE(p))     /* and not FALSE */
 681                         break;
 682                     }
 683                 }
 684
 685               if (p)
 686                 {
 687                   /*
 688                    * if we found some p that is UNDEF or TRUE, move
 689                    * watch to it
 690                    */
 691                   IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
 692                     {
 693                       if (p > 0)
 694                         POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "    -> move w%d to %s\n", (pkg == r->w1 ? 1 : 2), pool_solvid2str(pool, p));
 695                       else
 696                         POOL_DEBUG(SOLV_DEBUG_PROPAGATE,"    -> move w%d to !%s\n", (pkg == r->w1 ? 1 : 2), pool_solvid2str(pool, -p));
 697                     }
 698
 699                   *rp = *next_rp;
 700                   next_rp = rp;
 701
 702                   if (pkg == r->w1)
 703                     {
 704                       r->w1 = p;
 705                       r->n1 = watches[p];
 706                     }
 707                   else
 708                     {
 709                       r->w2 = p;
 710                       r->n2 = watches[p];
 711                     }
 712                   watches[p] = r - solv->rules;
 713                   continue;
 714                 }
 715               /* search failed, thus all unwatched literals are FALSE */
 716
 717             } /* not binary */
 718
 719           /*
 720            * unit clause found, set literal other_watch to TRUE
 721            */
 722
 723           if (DECISIONMAP_FALSE(other_watch))      /* check if literal is FALSE */
 724             return r;                              /* eek, a conflict! */
 725
 726           IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
 727             {
 728               POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "   unit ");
 729               solver_printrule(solv, SOLV_DEBUG_PROPAGATE, r);
 730             }
 731
 732           if (other_watch > 0)
 733             decisionmap[other_watch] = level;    /* install! */
 734           else
 735             decisionmap[-other_watch] = -level;  /* remove! */
 736
 737           queue_push(&solv->decisionq, other_watch);
 738           queue_push(&solv->decisionq_why, r - solv->rules);
 739
 740           IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
 741             {
 742               if (other_watch > 0)
 743                 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "    -> decided to install %s\n", pool_solvid2str(pool, other_watch));
 744               else
 745                 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "    -> decided to conflict %s\n", pool_solvid2str(pool, -other_watch));
 746             }
 747
 748         } /* foreach rule involving 'pkg' */
 749
 750     } /* while we have non-decided decisions */
 751
 752   POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "----- propagate end-----\n");
 753
 754   return 0;     /* all is well */
 755 }
 756
 757
 758 /********************************************************************/
 759 /* Analysis */
 760
 761 /*-------------------------------------------------------------------
 762  *
 763  * analyze
 764  *   and learn
 765  */
 766
 767 static int
 768 analyze(Solver *solv, int level, Rule *c, int *pr, int *dr, int *whyp)
 769 {
 770   Pool *pool = solv->pool;
 771   Queue r;
 772   Id r_buf[4];
 773   int rlevel = 1;
 774   Map seen;             /* global? */
 775   Id d, v, vv, *dp, why;
 776   int l, i, idx;
 777   int num = 0, l1num = 0;
 778   int learnt_why = solv->learnt_pool.count;
 779   Id *decisionmap = solv->decisionmap;
 780
 781   queue_init_buffer(&r, r_buf, sizeof(r_buf)/sizeof(*r_buf));
 782
 783   POOL_DEBUG(SOLV_DEBUG_ANALYZE, "ANALYZE at %d ----------------------\n", level);
 784   map_init(&seen, pool->nsolvables);
 785   idx = solv->decisionq.count;
 786   for (;;)
 787     {
 788       IF_POOLDEBUG (SOLV_DEBUG_ANALYZE)
 789         solver_printruleclass(solv, SOLV_DEBUG_ANALYZE, c);
 790       queue_push(&solv->learnt_pool, c - solv->rules);
 791       d = c->d < 0 ? -c->d - 1 : c->d;
 792       dp = d ? pool->whatprovidesdata + d : 0;
 793       /* go through all literals of the rule */
 794       for (i = -1; ; i++)
 795         {
 796           if (i == -1)
 797             v = c->p;
 798           else if (d == 0)
 799             v = i ? 0 : c->w2;
 800           else
 801             v = *dp++;
 802           if (v == 0)
 803             break;
 804
 805           if (DECISIONMAP_TRUE(v))      /* the one true literal */
 806             continue;
 807           vv = v > 0 ? v : -v;
 808           if (MAPTST(&seen, vv))
 809             continue;
 810           l = solv->decisionmap[vv];
 811           if (l < 0)
 812             l = -l;
 813           MAPSET(&seen, vv);            /* mark that we also need to look at this literal */
 814           if (l == 1)
 815             l1num++;                    /* need to do this one in level1 pass */
 816           else if (l == level)
 817             num++;                      /* need to do this one as well */
 818           else
 819             {
 820               queue_push(&r, v);        /* not level1 or conflict level, add to new rule */
 821               if (l > rlevel)
 822                 rlevel = l;
 823             }
 824         }
 825 l1retry:
 826       if (!num && !--l1num)
 827         break;  /* all level 1 literals done */
 828
 829       /* find the next literal to investigate */
 830       /* (as num + l1num > 0, we know that we'll always find one) */
 831       for (;;)
 832         {
 833           assert(idx > 0);
 834           v = solv->decisionq.elements[--idx];
 835           vv = v > 0 ? v : -v;
 836           if (MAPTST(&seen, vv))
 837             break;
 838         }
 839       MAPCLR(&seen, vv);
 840
 841       if (num && --num == 0)
 842         {
 843           *pr = -v;     /* so that v doesn't get lost */
 844           if (!l1num)
 845             break;
 846           POOL_DEBUG(SOLV_DEBUG_ANALYZE, "got %d involved level 1 decisions\n", l1num);
 847           /* clear non-l1 bits from seen map */
 848           for (i = 0; i < r.count; i++)
 849             {
 850               v = r.elements[i];
 851               MAPCLR(&seen, v > 0 ? v : -v);
 852             }
 853           /* only level 1 marks left in seen map */
 854           l1num++;      /* as l1retry decrements it */
 855           goto l1retry;
 856         }
 857
 858       why = solv->decisionq_why.elements[idx];
 859       if (why <= 0)     /* just in case, maybe for SYSTEMSOLVABLE */
 860         goto l1retry;
 861       c = solv->rules + why;
 862     }
 863   map_free(&seen);
 864
 865   if (r.count == 0)
 866     *dr = 0;
 867   else if (r.count == 1 && r.elements[0] < 0)
 868     *dr = r.elements[0];
 869   else
 870     *dr = pool_queuetowhatprovides(pool, &r);
 871   IF_POOLDEBUG (SOLV_DEBUG_ANALYZE)
 872     {
 873       POOL_DEBUG(SOLV_DEBUG_ANALYZE, "learned rule for level %d (am %d)\n", rlevel, level);
 874       solver_printruleelement(solv, SOLV_DEBUG_ANALYZE, 0, *pr);
 875       for (i = 0; i < r.count; i++)
 876         solver_printruleelement(solv, SOLV_DEBUG_ANALYZE, 0, r.elements[i]);
 877     }
 878   /* push end marker on learnt reasons stack */
 879   queue_push(&solv->learnt_pool, 0);
 880   if (whyp)
 881     *whyp = learnt_why;
 882   queue_free(&r);
 883   solv->stats_learned++;
 884   return rlevel;
 885 }
 886
 887
 888 /*-------------------------------------------------------------------
 889  *
 890  * solver_reset
 891  *
 892  * reset all solver decisions
 893  * called after rules have been enabled/disabled
 894  */
 895
 896 void
 897 solver_reset(Solver *solv)
 898 {
 899   Pool *pool = solv->pool;
 900   int i;
 901   Id v;
 902
 903   /* rewind all decisions */
 904   for (i = solv->decisionq.count - 1; i >= 0; i--)
 905     {
 906       v = solv->decisionq.elements[i];
 907       solv->decisionmap[v > 0 ? v : -v] = 0;
 908     }
 909   solv->decisionq_why.count = 0;
 910   solv->decisionq.count = 0;
 911   solv->recommends_index = -1;
 912   solv->propagate_index = 0;
 913   solv->branches.count = 0;
 914
 915   /* adapt learnt rule status to new set of enabled/disabled rules */
 916   enabledisablelearntrules(solv);
 917
 918   /* redo all assertion rule decisions */
 919   makeruledecisions(solv);
 920   POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "decisions so far: %d\n", solv->decisionq.count);
 921 }
 922
 923
 924 /*-------------------------------------------------------------------
 925  *
 926  * analyze_unsolvable_rule
 927  *
 928  * recursion helper used by analyze_unsolvable
 929  */
 930
 931 static void
 932 analyze_unsolvable_rule(Solver *solv, Rule *r, Id *lastweakp, Map *rseen)
 933 {
 934   Pool *pool = solv->pool;
 935   int i;
 936   Id why = r - solv->rules;
 937
 938   IF_POOLDEBUG (SOLV_DEBUG_UNSOLVABLE)
 939     solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE, r);
 940   if (solv->learntrules && why >= solv->learntrules)
 941     {
 942       if (MAPTST(rseen, why - solv->learntrules))
 943         return;
 944       MAPSET(rseen, why - solv->learntrules);
 945       for (i = solv->learnt_why.elements[why - solv->learntrules]; solv->learnt_pool.elements[i]; i++)
 946         if (solv->learnt_pool.elements[i] > 0)
 947           analyze_unsolvable_rule(solv, solv->rules + solv->learnt_pool.elements[i], lastweakp, rseen);
 948       return;
 949     }
 950   if (MAPTST(&solv->weakrulemap, why))
 951     if (!*lastweakp || why > *lastweakp)
 952       *lastweakp = why;
 953   /* do not add rpm rules to problem */
 954   if (why < solv->rpmrules_end)
 955     return;
 956   /* turn rule into problem */
 957   if (why >= solv->jobrules && why < solv->jobrules_end)
 958     why = -(solv->ruletojob.elements[why - solv->jobrules] + 1);
 959   /* normalize dup/infarch rules */
 960   if (why > solv->infarchrules && why < solv->infarchrules_end)
 961     {
 962       Id name = pool->solvables[-solv->rules[why].p].name;
 963       while (why > solv->infarchrules && pool->solvables[-solv->rules[why - 1].p].name == name)
 964         why--;
 965     }
 966   if (why > solv->duprules && why < solv->duprules_end)
 967     {
 968       Id name = pool->solvables[-solv->rules[why].p].name;
 969       while (why > solv->duprules && pool->solvables[-solv->rules[why - 1].p].name == name)
 970         why--;
 971     }
 972
 973   /* return if problem already countains our rule */
 974   if (solv->problems.count)
 975     {
 976       for (i = solv->problems.count - 1; i >= 0; i--)
 977         if (solv->problems.elements[i] == 0)    /* end of last problem reached? */
 978           break;
 979         else if (solv->problems.elements[i] == why)
 980           return;
 981     }
 982   queue_push(&solv->problems, why);
 983 }
 984
 985
 986 /*-------------------------------------------------------------------
 987  *
 988  * analyze_unsolvable
 989  *
 990  * We know that the problem is not solvable. Record all involved
 991  * rules (i.e. the "proof") into solv->learnt_pool.
 992  * Record the learnt pool index and all non-rpm rules into
 993  * solv->problems. (Our solutions to fix the problems are to
 994  * disable those rules.)
 995  *
 996  * If the proof contains at least one weak rule, we disable the
 997  * last of them.
 998  *
 999  * Otherwise we return 0 if disablerules is not set or disable
1000  * _all_ of the problem rules and return 1.
1001  *
1002  * return: 1 - disabled some rules, try again
1003  *         0 - hopeless
1004  */
1005
1006 static int
1007 analyze_unsolvable(Solver *solv, Rule *cr, int disablerules)
1008 {
1009   Pool *pool = solv->pool;
1010   Rule *r;
1011   Map seen;             /* global to speed things up? */
1012   Map rseen;
1013   Id d, v, vv, *dp, why;
1014   int l, i, idx;
1015   Id *decisionmap = solv->decisionmap;
1016   int oldproblemcount;
1017   int oldlearntpoolcount;
1018   Id lastweak;
1019   int record_proof = 1;
1020
1021   POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "ANALYZE UNSOLVABLE ----------------------\n");
1022   solv->stats_unsolvable++;
1023   oldproblemcount = solv->problems.count;
1024   oldlearntpoolcount = solv->learnt_pool.count;
1025
1026   /* make room for proof index */
1027   /* must update it later, as analyze_unsolvable_rule would confuse
1028    * it with a rule index if we put the real value in already */
1029   queue_push(&solv->problems, 0);
1030
1031   r = cr;
1032   map_init(&seen, pool->nsolvables);
1033   map_init(&rseen, solv->learntrules ? solv->nrules - solv->learntrules : 0);
1034   if (record_proof)
1035     queue_push(&solv->learnt_pool, r - solv->rules);
1036   lastweak = 0;
1037   analyze_unsolvable_rule(solv, r, &lastweak, &rseen);
1038   d = r->d < 0 ? -r->d - 1 : r->d;
1039   dp = d ? pool->whatprovidesdata + d : 0;
1040   for (i = -1; ; i++)
1041     {
1042       if (i == -1)
1043         v = r->p;
1044       else if (d == 0)
1045         v = i ? 0 : r->w2;
1046       else
1047         v = *dp++;
1048       if (v == 0)
1049         break;
1050       if (DECISIONMAP_TRUE(v))  /* the one true literal */
1051           continue;
1052       vv = v > 0 ? v : -v;
1053       l = solv->decisionmap[vv];
1054       if (l < 0)
1055         l = -l;
1056       MAPSET(&seen, vv);
1057     }
1058   idx = solv->decisionq.count;
1059   while (idx > 0)
1060     {
1061       v = solv->decisionq.elements[--idx];
1062       vv = v > 0 ? v : -v;
1063       if (!MAPTST(&seen, vv))
1064         continue;
1065       why = solv->decisionq_why.elements[idx];
1066       assert(why > 0);
1067       if (record_proof)
1068         queue_push(&solv->learnt_pool, why);
1069       r = solv->rules + why;
1070       analyze_unsolvable_rule(solv, r, &lastweak, &rseen);
1071       d = r->d < 0 ? -r->d - 1 : r->d;
1072       dp = d ? pool->whatprovidesdata + d : 0;
1073       for (i = -1; ; i++)
1074         {
1075           if (i == -1)
1076             v = r->p;
1077           else if (d == 0)
1078             v = i ? 0 : r->w2;
1079           else
1080             v = *dp++;
1081           if (v == 0)
1082             break;
1083           if (DECISIONMAP_TRUE(v))      /* the one true literal */
1084               continue;
1085           vv = v > 0 ? v : -v;
1086           l = solv->decisionmap[vv];
1087           if (l < 0)
1088             l = -l;
1089           MAPSET(&seen, vv);
1090         }
1091     }
1092   map_free(&seen);
1093   map_free(&rseen);
1094   queue_push(&solv->problems, 0);       /* mark end of this problem */
1095
1096   if (lastweak)
1097     {
1098       /* disable last weak rule */
1099       solv->problems.count = oldproblemcount;
1100       solv->learnt_pool.count = oldlearntpoolcount;
1101       if (lastweak >= solv->jobrules && lastweak < solv->jobrules_end)
1102         v = -(solv->ruletojob.elements[lastweak - solv->jobrules] + 1);
1103       else
1104         v = lastweak;
1105       POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "disabling ");
1106       solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE, solv->rules + lastweak);
1107       if (lastweak >= solv->choicerules && lastweak < solv->choicerules_end)
1108         solver_disablechoicerules(solv, solv->rules + lastweak);
1109       solver_disableproblem(solv, v);
1110       if (v < 0)
1111         solver_reenablepolicyrules(solv, -v);
1112       solver_reset(solv);
1113       return 1;
1114     }
1115
1116   if (solv->allowuninstall && (v = autouninstall(solv, solv->problems.elements + oldproblemcount + 1)) != 0)
1117     {
1118       solv->problems.count = oldproblemcount;
1119       solv->learnt_pool.count = oldlearntpoolcount;
1120       solver_reset(solv);
1121       return 1;
1122     }
1123
1124   /* finish proof */
1125   if (record_proof)
1126     {
1127       queue_push(&solv->learnt_pool, 0);
1128       solv->problems.elements[oldproblemcount] = oldlearntpoolcount;
1129     }
1130
1131   /* + 2: index + trailing zero */
1132   if (disablerules && oldproblemcount + 2 < solv->problems.count)
1133     {
1134       for (i = oldproblemcount + 1; i < solv->problems.count - 1; i++)
1135         solver_disableproblem(solv, solv->problems.elements[i]);
1136       /* XXX: might want to enable all weak rules again */
1137       solver_reset(solv);
1138       return 1;
1139     }
1140   POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "UNSOLVABLE\n");
1141   return 0;
1142 }
1143
1144
1145 /********************************************************************/
1146 /* Decision revert */
1147
1148 /*-------------------------------------------------------------------
1149  *
1150  * revert
1151  * revert decisionq to a level
1152  */
1153
1154 static void
1155 revert(Solver *solv, int level)
1156 {
1157   Pool *pool = solv->pool;
1158   Id v, vv;
1159   while (solv->decisionq.count)
1160     {
1161       v = solv->decisionq.elements[solv->decisionq.count - 1];
1162       vv = v > 0 ? v : -v;
1163       if (solv->decisionmap[vv] <= level && solv->decisionmap[vv] >= -level)
1164         break;
1165       POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "reverting decision %d at %d\n", v, solv->decisionmap[vv]);
1166       solv->decisionmap[vv] = 0;
1167       solv->decisionq.count--;
1168       solv->decisionq_why.count--;
1169       solv->propagate_index = solv->decisionq.count;
1170     }
1171   while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] <= -level)
1172     {
1173       solv->branches.count--;
1174       while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] >= 0)
1175         solv->branches.count--;
1176     }
1177   solv->recommends_index = -1;
1178 }
1179
1180
1181 /*-------------------------------------------------------------------
1182  *
1183  * watch2onhighest - put watch2 on literal with highest level
1184  */
1185
1186 static inline void
1187 watch2onhighest(Solver *solv, Rule *r)
1188 {
1189   int l, wl = 0;
1190   Id d, v, *dp;
1191
1192   d = r->d < 0 ? -r->d - 1 : r->d;
1193   if (!d)
1194     return;     /* binary rule, both watches are set */
1195   dp = solv->pool->whatprovidesdata + d;
1196   while ((v = *dp++) != 0)
1197     {
1198       l = solv->decisionmap[v < 0 ? -v : v];
1199       if (l < 0)
1200         l = -l;
1201       if (l > wl)
1202         {
1203           r->w2 = dp[-1];
1204           wl = l;
1205         }
1206     }
1207 }
1208
1209
1210 /*-------------------------------------------------------------------
1211  *
1212  * setpropagatelearn
1213  *
1214  * add free decision (solvable to install) to decisionq
1215  * increase level and propagate decision
1216  * return if no conflict.
1217  *
1218  * in conflict case, analyze conflict rule, add resulting
1219  * rule to learnt rule set, make decision from learnt
1220  * rule (always unit) and re-propagate.
1221  *
1222  * returns the new solver level or 0 if unsolvable
1223  *
1224  */
1225
1226 static int
1227 setpropagatelearn(Solver *solv, int level, Id decision, int disablerules, Id ruleid)
1228 {
1229   Pool *pool = solv->pool;
1230   Rule *r;
1231   Id p = 0, d = 0;
1232   int l, why;
1233
1234   assert(ruleid >= 0);
1235   if (decision)
1236     {
1237       level++;
1238       if (decision > 0)
1239         solv->decisionmap[decision] = level;
1240       else
1241         solv->decisionmap[-decision] = -level;
1242       queue_push(&solv->decisionq, decision);
1243       queue_push(&solv->decisionq_why, -ruleid);        /* <= 0 -> free decision */
1244     }
1245   for (;;)
1246     {
1247       r = propagate(solv, level);
1248       if (!r)
1249         break;
1250       if (level == 1)
1251         return analyze_unsolvable(solv, r, disablerules);
1252       POOL_DEBUG(SOLV_DEBUG_ANALYZE, "conflict with rule #%d\n", (int)(r - solv->rules));
1253       l = analyze(solv, level, r, &p, &d, &why);        /* learnt rule in p and d */
1254       assert(l > 0 && l < level);
1255       POOL_DEBUG(SOLV_DEBUG_ANALYZE, "reverting decisions (level %d -> %d)\n", level, l);
1256       level = l;
1257       revert(solv, level);
1258       r = solver_addrule(solv, p, d);
1259       assert(r);
1260       assert(solv->learnt_why.count == (r - solv->rules) - solv->learntrules);
1261       queue_push(&solv->learnt_why, why);
1262       if (d)
1263         {
1264           /* at least 2 literals, needs watches */
1265           watch2onhighest(solv, r);
1266           addwatches_rule(solv, r);
1267         }
1268       else
1269         {
1270           /* learnt rule is an assertion */
1271           queue_push(&solv->ruleassertions, r - solv->rules);
1272         }
1273       /* the new rule is unit by design */
1274       solv->decisionmap[p > 0 ? p : -p] = p > 0 ? level : -level;
1275       queue_push(&solv->decisionq, p);
1276       queue_push(&solv->decisionq_why, r - solv->rules);
1277       IF_POOLDEBUG (SOLV_DEBUG_ANALYZE)
1278         {
1279           POOL_DEBUG(SOLV_DEBUG_ANALYZE, "decision: ");
1280           solver_printruleelement(solv, SOLV_DEBUG_ANALYZE, 0, p);
1281           POOL_DEBUG(SOLV_DEBUG_ANALYZE, "new rule: ");
1282           solver_printrule(solv, SOLV_DEBUG_ANALYZE, r);
1283         }
1284     }
1285   return level;
1286 }
1287
1288
1289 /*-------------------------------------------------------------------
1290  *
1291  * select and install
1292  *
1293  * install best package from the queue. We add an extra package, inst, if
1294  * provided. See comment in weak install section.
1295  *
1296  * returns the new solver level or 0 if unsolvable
1297  *
1298  */
1299
1300 static int
1301 selectandinstall(Solver *solv, int level, Queue *dq, int disablerules, Id ruleid)
1302 {
1303   Pool *pool = solv->pool;
1304   Id p;
1305   int i;
1306
1307   if (dq->count > 1)
1308     policy_filter_unwanted(solv, dq, POLICY_MODE_CHOOSE);
1309   if (dq->count > 1)
1310     {
1311       /* XXX: didn't we already do that? */
1312       /* XXX: shouldn't we prefer installed packages? */
1313       /* XXX: move to policy.c? */
1314       /* choose the supplemented one */
1315       for (i = 0; i < dq->count; i++)
1316         if (solver_is_supplementing(solv, pool->solvables + dq->elements[i]))
1317           {
1318             dq->elements[0] = dq->elements[i];
1319             dq->count = 1;
1320             break;
1321           }
1322     }
1323   if (dq->count > 1)
1324     {
1325       /* multiple candidates, open a branch */
1326       for (i = 1; i < dq->count; i++)
1327         queue_push(&solv->branches, dq->elements[i]);
1328       queue_push(&solv->branches, -level);
1329     }
1330   p = dq->elements[0];
1331
1332   POOL_DEBUG(SOLV_DEBUG_POLICY, "installing %s\n", pool_solvid2str(pool, p));
1333
1334   return setpropagatelearn(solv, level, p, disablerules, ruleid);
1335 }
1336
1337
1338 /********************************************************************/
1339 /* Main solver interface */
1340
1341
1342 /*-------------------------------------------------------------------
1343  *
1344  * solver_create
1345  * create solver structure
1346  *
1347  * pool: all available solvables
1348  * installed: installed Solvables
1349  *
1350  *
1351  * Upon solving, rules are created to flag the Solvables
1352  * of the 'installed' Repo as installed.
1353  */
1354
1355 Solver *
1356 solver_create(Pool *pool)
1357 {
1358   Solver *solv;
1359   solv = (Solver *)solv_calloc(1, sizeof(Solver));
1360   solv->pool = pool;
1361   solv->installed = pool->installed;
1362
1363   solv->allownamechange = 1;
1364
1365   solv->dup_allowdowngrade = 1;
1366   solv->dup_allownamechange = 1;
1367   solv->dup_allowarchchange = 1;
1368   solv->dup_allowvendorchange = 1;
1369
1370   queue_init(&solv->ruletojob);
1371   queue_init(&solv->decisionq);
1372   queue_init(&solv->decisionq_why);
1373   queue_init(&solv->problems);
1374   queue_init(&solv->orphaned);
1375   queue_init(&solv->learnt_why);
1376   queue_init(&solv->learnt_pool);
1377   queue_init(&solv->branches);
1378   queue_init(&solv->weakruleq);
1379   queue_init(&solv->ruleassertions);
1380
1381   queue_push(&solv->learnt_pool, 0);    /* so that 0 does not describe a proof */
1382
1383   map_init(&solv->recommendsmap, pool->nsolvables);
1384   map_init(&solv->suggestsmap, pool->nsolvables);
1385   map_init(&solv->noupdate, solv->installed ? solv->installed->end - solv->installed->start : 0);
1386   solv->recommends_index = 0;
1387
1388   solv->decisionmap = (Id *)solv_calloc(pool->nsolvables, sizeof(Id));
1389   solv->nrules = 1;
1390   solv->rules = solv_extend_resize(solv->rules, solv->nrules, sizeof(Rule), RULES_BLOCK);
1391   memset(solv->rules, 0, sizeof(Rule));
1392
1393   return solv;
1394 }
1395
1396
1397 /*-------------------------------------------------------------------
1398  *
1399  * solver_free
1400  */
1401
1402 void
1403 solver_free(Solver *solv)
1404 {
1405   queue_free(&solv->job);
1406   queue_free(&solv->ruletojob);
1407   queue_free(&solv->decisionq);
1408   queue_free(&solv->decisionq_why);
1409   queue_free(&solv->learnt_why);
1410   queue_free(&solv->learnt_pool);
1411   queue_free(&solv->problems);
1412   queue_free(&solv->solutions);
1413   queue_free(&solv->orphaned);
1414   queue_free(&solv->branches);
1415   queue_free(&solv->weakruleq);
1416   queue_free(&solv->ruleassertions);
1417   if (solv->cleandeps_updatepkgs)
1418     {
1419       queue_free(solv->cleandeps_updatepkgs);
1420       solv->cleandeps_updatepkgs = solv_free(solv->cleandeps_updatepkgs);
1421     }
1422   if (solv->cleandeps_mistakes)
1423     {
1424       queue_free(solv->cleandeps_mistakes);
1425       solv->cleandeps_mistakes = solv_free(solv->cleandeps_mistakes);
1426     }
1427
1428   map_free(&solv->recommendsmap);
1429   map_free(&solv->suggestsmap);
1430   map_free(&solv->noupdate);
1431   map_free(&solv->weakrulemap);
1432   map_free(&solv->noobsoletes);
1433
1434   map_free(&solv->updatemap);
1435   map_free(&solv->fixmap);
1436   map_free(&solv->dupmap);
1437   map_free(&solv->dupinvolvedmap);
1438   map_free(&solv->droporphanedmap);
1439   map_free(&solv->cleandepsmap);
1440
1441   solv_free(solv->decisionmap);
1442   solv_free(solv->rules);
1443   solv_free(solv->watches);
1444   solv_free(solv->obsoletes);
1445   solv_free(solv->obsoletes_data);
1446   solv_free(solv->multiversionupdaters);
1447   solv_free(solv->choicerules_ref);
1448   solv_free(solv);
1449 }
1450
1451 int
1452 solver_get_flag(Solver *solv, int flag)
1453 {
1454   switch (flag)
1455   {
1456   case SOLVER_FLAG_ALLOW_DOWNGRADE:
1457     return solv->allowdowngrade;
1458   case SOLVER_FLAG_ALLOW_NAMECHANGE:
1459     return solv->allownamechange;
1460   case SOLVER_FLAG_ALLOW_ARCHCHANGE:
1461     return solv->allowarchchange;
1462   case SOLVER_FLAG_ALLOW_VENDORCHANGE:
1463     return solv->allowvendorchange;
1464   case SOLVER_FLAG_ALLOW_UNINSTALL:
1465     return solv->allowuninstall;
1466   case SOLVER_FLAG_NO_UPDATEPROVIDE:
1467     return solv->noupdateprovide;
1468   case SOLVER_FLAG_SPLITPROVIDES:
1469     return solv->dosplitprovides;
1470   case SOLVER_FLAG_IGNORE_RECOMMENDED:
1471     return solv->dontinstallrecommended;
1472   case SOLVER_FLAG_ADD_ALREADY_RECOMMENDED:
1473     return solv->addalreadyrecommended;
1474   case SOLVER_FLAG_NO_INFARCHCHECK:
1475     return solv->noinfarchcheck;
1476   case SOLVER_FLAG_KEEP_EXPLICIT_OBSOLETES:
1477     return solv->keepexplicitobsoletes;
1478   default:
1479     break;
1480   }
1481   return -1;
1482 }
1483
1484 int
1485 solver_set_flag(Solver *solv, int flag, int value)
1486 {
1487   int old = solver_get_flag(solv, flag);
1488   switch (flag)
1489   {
1490   case SOLVER_FLAG_ALLOW_DOWNGRADE:
1491     solv->allowdowngrade = value;
1492     break;
1493   case SOLVER_FLAG_ALLOW_NAMECHANGE:
1494     solv->allownamechange = value;
1495     break;
1496   case SOLVER_FLAG_ALLOW_ARCHCHANGE:
1497     solv->allowarchchange = value;
1498     break;
1499   case SOLVER_FLAG_ALLOW_VENDORCHANGE:
1500     solv->allowvendorchange = value;
1501     break;
1502   case SOLVER_FLAG_ALLOW_UNINSTALL:
1503     solv->allowuninstall = value;
1504     break;
1505   case SOLVER_FLAG_NO_UPDATEPROVIDE:
1506     solv->noupdateprovide = value;
1507     break;
1508   case SOLVER_FLAG_SPLITPROVIDES:
1509     solv->dosplitprovides = value;
1510     break;
1511   case SOLVER_FLAG_IGNORE_RECOMMENDED:
1512     solv->dontinstallrecommended = value;
1513     break;
1514   case SOLVER_FLAG_ADD_ALREADY_RECOMMENDED:
1515     solv->addalreadyrecommended = value;
1516     break;
1517   case SOLVER_FLAG_NO_INFARCHCHECK:
1518     solv->noinfarchcheck = value;
1519     break;
1520   case SOLVER_FLAG_KEEP_EXPLICIT_OBSOLETES:
1521     solv->keepexplicitobsoletes = value;
1522     break;
1523   default:
1524     break;
1525   }
1526   return old;
1527 }
1528
1529 int
1530 cleandeps_check_mistakes(Solver *solv, int level)
1531 {
1532   Pool *pool = solv->pool;
1533   Rule *r;
1534   Id p, *dp;
1535   int i;
1536   int mademistake = 0;
1537
1538   if (!solv->cleandepsmap.size)
1539     return 0;
1540   /* check for mistakes */
1541   for (i = solv->installed->start; i < solv->installed->end; i++)
1542     {
1543       if (!MAPTST(&solv->cleandepsmap, i - solv->installed->start))
1544         continue;
1545       r = solv->rules + solv->featurerules + (i - solv->installed->start);
1546       /* a mistake is when the featurerule is true but the updaterule is false */
1547       if (r->p)
1548         {
1549           FOR_RULELITERALS(p, dp, r)
1550             if (p > 0 && solv->decisionmap[p] > 0)
1551               break;
1552           if (p)
1553             {
1554               r = solv->rules + solv->updaterules + (i - solv->installed->start);
1555               if (!r->p)
1556                 continue;
1557               FOR_RULELITERALS(p, dp, r)
1558                 if (p > 0 && solv->decisionmap[p] > 0)
1559                   break;
1560               if (!p)
1561                 {
1562                   POOL_DEBUG(SOLV_DEBUG_SOLVER, "cleandeps mistake: ");
1563                   solver_printruleclass(solv, SOLV_DEBUG_SOLVER, r);
1564                   POOL_DEBUG(SOLV_DEBUG_SOLVER, "feature rule: ");
1565                   solver_printruleclass(solv, SOLV_DEBUG_SOLVER, solv->rules + solv->featurerules + (i - solv->installed->start));
1566                   if (!solv->cleandeps_mistakes)
1567                     {
1568                       solv->cleandeps_mistakes = solv_calloc(1, sizeof(Queue));
1569                       queue_init(solv->cleandeps_mistakes);
1570                     }
1571                   queue_push(solv->cleandeps_mistakes, i);
1572                   MAPCLR(&solv->cleandepsmap, i - solv->installed->start);
1573                   solver_reenablepolicyrules_cleandeps(solv, i);
1574                   mademistake = 1;
1575                 }
1576             }
1577         }
1578     }
1579   if (mademistake)
1580     solver_reset(solv);
1581   return mademistake;
1582 }
1583
1584 /*-------------------------------------------------------------------
1585  *
1586  * solver_run_sat
1587  *
1588  * all rules have been set up, now actually run the solver
1589  *
1590  */
1591
1592 void
1593 solver_run_sat(Solver *solv, int disablerules, int doweak)
1594 {
1595   Queue dq;             /* local decisionqueue */
1596   Queue dqs;            /* local decisionqueue for supplements */
1597   int systemlevel;
1598   int level, olevel;
1599   Rule *r;
1600   int i, j, n;
1601   Solvable *s;
1602   Pool *pool = solv->pool;
1603   Id p, *dp;
1604   int minimizationsteps;
1605   int installedpos = solv->installed ? solv->installed->start : 0;
1606
1607   IF_POOLDEBUG (SOLV_DEBUG_RULE_CREATION)
1608     {
1609       POOL_DEBUG (SOLV_DEBUG_RULE_CREATION, "number of rules: %d\n", solv->nrules);
1610       for (i = 1; i < solv->nrules; i++)
1611         solver_printruleclass(solv, SOLV_DEBUG_RULE_CREATION, solv->rules + i);
1612     }
1613
1614   POOL_DEBUG(SOLV_DEBUG_SOLVER, "initial decisions: %d\n", solv->decisionq.count);
1615
1616   /* start SAT algorithm */
1617   level = 1;
1618   systemlevel = level + 1;
1619   POOL_DEBUG(SOLV_DEBUG_SOLVER, "solving...\n");
1620
1621   queue_init(&dq);
1622   queue_init(&dqs);
1623
1624   /*
1625    * here's the main loop:
1626    * 1) propagate new decisions (only needed once)
1627    * 2) fulfill jobs
1628    * 3) try to keep installed packages
1629    * 4) fulfill all unresolved rules
1630    * 5) install recommended packages
1631    * 6) minimalize solution if we had choices
1632    * if we encounter a problem, we rewind to a safe level and restart
1633    * with step 1
1634    */
1635
1636   minimizationsteps = 0;
1637   for (;;)
1638     {
1639       /*
1640        * initial propagation of the assertions
1641        */
1642       if (level == 1)
1643         {
1644           POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "propagating (propagate_index: %d;  size decisionq: %d)...\n", solv->propagate_index, solv->decisionq.count);
1645           if ((r = propagate(solv, level)) != 0)
1646             {
1647               if (analyze_unsolvable(solv, r, disablerules))
1648                 continue;
1649               level = 0;
1650               break;    /* unsolvable */
1651             }
1652         }
1653
1654       /*
1655        * resolve jobs first
1656        */
1657      if (level < systemlevel)
1658         {
1659           POOL_DEBUG(SOLV_DEBUG_SOLVER, "resolving job rules\n");
1660           for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++)
1661             {
1662               Id l;
1663               if (r->d < 0)             /* ignore disabled rules */
1664                 continue;
1665               queue_empty(&dq);
1666               FOR_RULELITERALS(l, dp, r)
1667                 {
1668                   if (l < 0)
1669                     {
1670                       if (solv->decisionmap[-l] <= 0)
1671                         break;
1672                     }
1673                   else
1674                     {
1675                       if (solv->decisionmap[l] > 0)
1676                         break;
1677                       if (solv->decisionmap[l] == 0)
1678                         queue_push(&dq, l);
1679                     }
1680                 }
1681               if (l || !dq.count)
1682                 continue;
1683               /* prune to installed if not updating */
1684               if (dq.count > 1 && solv->installed && !solv->updatemap_all)
1685                 {
1686                   int j, k;
1687                   for (j = k = 0; j < dq.count; j++)
1688                     {
1689                       Solvable *s = pool->solvables + dq.elements[j];
1690                       if (s->repo == solv->installed)
1691                         {
1692                           dq.elements[k++] = dq.elements[j];
1693                           if (solv->updatemap.size && MAPTST(&solv->updatemap, dq.elements[j] - solv->installed->start))
1694                             {
1695                               k = 0;    /* package wants to be updated, do not prune */
1696                               break;
1697                             }
1698                         }
1699                     }
1700                   if (k)
1701                     dq.count = k;
1702                 }
1703               olevel = level;
1704               level = selectandinstall(solv, level, &dq, disablerules, i);
1705               if (level == 0)
1706                 break;
1707               if (level <= olevel)
1708                 break;
1709             }
1710           if (level == 0)
1711             break;      /* unsolvable */
1712           systemlevel = level + 1;
1713           if (i < solv->jobrules_end)
1714             continue;
1715           solv->decisioncnt_update = solv->decisionq.count;
1716           solv->decisioncnt_keep = solv->decisionq.count;
1717         }
1718
1719       /*
1720        * installed packages
1721        */
1722       if (level < systemlevel && solv->installed && solv->installed->nsolvables && !solv->installed->disabled)
1723         {
1724           Repo *installed = solv->installed;
1725           int pass;
1726
1727           POOL_DEBUG(SOLV_DEBUG_SOLVER, "resolving installed packages\n");
1728           /* we use two passes if we need to update packages
1729            * to create a better user experience */
1730           for (pass = solv->updatemap.size ? 0 : 1; pass < 2; pass++)
1731             {
1732               int passlevel = level;
1733               if (pass == 1)
1734                 solv->decisioncnt_keep = solv->decisionq.count;
1735               /* start with installedpos, the position that gave us problems last time */
1736               for (i = installedpos, n = installed->start; n < installed->end; i++, n++)
1737                 {
1738                   Rule *rr;
1739                   Id d;
1740
1741                   if (i == installed->end)
1742                     i = installed->start;
1743                   s = pool->solvables + i;
1744                   if (s->repo != installed)
1745                     continue;
1746
1747                   if (solv->decisionmap[i] > 0)
1748                     continue;
1749                   if (!pass && solv->updatemap.size && !MAPTST(&solv->updatemap, i - installed->start))
1750                     continue;           /* updates first */
1751                   r = solv->rules + solv->updaterules + (i - installed->start);
1752                   rr = r;
1753                   if (!rr->p || rr->d < 0)      /* disabled -> look at feature rule */
1754                     rr -= solv->installed->end - solv->installed->start;
1755                   if (!rr->p)           /* identical to update rule? */
1756                     rr = r;
1757                   if (!rr->p)
1758                     continue;           /* orpaned package */
1759
1760                   /* XXX: noupdate check is probably no longer needed, as all jobs should
1761                    * already be satisfied */
1762                   /* Actually we currently still need it because of erase jobs */
1763                   /* if noupdate is set we do not look at update candidates */
1764                   queue_empty(&dq);
1765                   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 != i))
1766                     {
1767                       if (solv->noobsoletes.size && solv->multiversionupdaters
1768                              && (d = solv->multiversionupdaters[i - installed->start]) != 0)
1769                         {
1770                           /* special multiversion handling, make sure best version is chosen */
1771                           queue_push(&dq, i);
1772                           while ((p = pool->whatprovidesdata[d++]) != 0)
1773                             if (solv->decisionmap[p] >= 0)
1774                               queue_push(&dq, p);
1775                           policy_filter_unwanted(solv, &dq, POLICY_MODE_CHOOSE);
1776                           p = dq.elements[0];
1777                           if (p != i && solv->decisionmap[p] == 0)
1778                             {
1779                               rr = solv->rules + solv->featurerules + (i - solv->installed->start);
1780                               if (!rr->p)               /* update rule == feature rule? */
1781                                 rr = rr - solv->featurerules + solv->updaterules;
1782                               dq.count = 1;
1783                             }
1784                           else
1785                             dq.count = 0;
1786                         }
1787                       else
1788                         {
1789                           /* update to best package */
1790                           FOR_RULELITERALS(p, dp, rr)
1791                             {
1792                               if (solv->decisionmap[p] > 0)
1793                                 {
1794                                   dq.count = 0;         /* already fulfilled */
1795                                   break;
1796                                 }
1797                               if (!solv->decisionmap[p])
1798                                 queue_push(&dq, p);
1799                             }
1800                         }
1801                     }
1802                   /* install best version */
1803                   if (dq.count)
1804                     {
1805                       olevel = level;
1806                       level = selectandinstall(solv, level, &dq, disablerules, rr - solv->rules);
1807                       if (level == 0)
1808                         {
1809                           queue_free(&dq);
1810                           queue_free(&dqs);
1811                           return;
1812                         }
1813                       if (level <= olevel)
1814                         {
1815                           if (level == 1 || level < passlevel)
1816                             break;      /* trouble */
1817                           if (level < olevel)
1818                             n = installed->start;       /* redo all */
1819                           i--;
1820                           n--;
1821                           continue;
1822                         }
1823                     }
1824                   /* if still undecided keep package */
1825                   if (solv->decisionmap[i] == 0)
1826                     {
1827                       olevel = level;
1828                       if (solv->cleandepsmap.size && MAPTST(&solv->cleandepsmap, i - installed->start))
1829                         {
1830                           POOL_DEBUG(SOLV_DEBUG_POLICY, "cleandeps erasing %s\n", pool_solvid2str(pool, i));
1831                           level = setpropagatelearn(solv, level, -i, disablerules, 0);
1832                         }
1833                       else
1834                         {
1835                           POOL_DEBUG(SOLV_DEBUG_POLICY, "keeping %s\n", pool_solvid2str(pool, i));
1836                           level = setpropagatelearn(solv, level, i, disablerules, r - solv->rules);
1837                         }
1838                       if (level == 0)
1839                         break;
1840                       if (level <= olevel)
1841                         {
1842                           if (level == 1 || level < passlevel)
1843                             break;      /* trouble */
1844                           if (level < olevel)
1845                             n = installed->start;       /* redo all */
1846                           i--;
1847                           n--;
1848                           continue;     /* retry with learnt rule */
1849                         }
1850                     }
1851                 }
1852               if (n < installed->end)
1853                 {
1854                   installedpos = i;     /* retry problem solvable next time */
1855                   break;                /* ran into trouble */
1856                 }
1857               installedpos = installed->start;  /* reset installedpos */
1858             }
1859           if (level == 0)
1860             break;              /* unsolvable */
1861           systemlevel = level + 1;
1862           if (pass < 2)
1863             continue;           /* had trouble, retry */
1864         }
1865
1866       if (level < systemlevel)
1867         systemlevel = level;
1868
1869       /*
1870        * decide
1871        */
1872       solv->decisioncnt_resolve = solv->decisionq.count;
1873       POOL_DEBUG(SOLV_DEBUG_POLICY, "deciding unresolved rules\n");
1874       for (i = 1, n = 1; n < solv->nrules; i++, n++)
1875         {
1876           if (i == solv->nrules)
1877             i = 1;
1878           r = solv->rules + i;
1879           if (r->d < 0)         /* ignore disabled rules */
1880             continue;
1881           queue_empty(&dq);
1882           if (r->d == 0)
1883             {
1884               /* binary or unary rule */
1885               /* need two positive undecided literals */
1886               if (r->p < 0 || r->w2 <= 0)
1887                 continue;
1888               if (solv->decisionmap[r->p] || solv->decisionmap[r->w2])
1889                 continue;
1890               queue_push(&dq, r->p);
1891               queue_push(&dq, r->w2);
1892             }
1893           else
1894             {
1895               /* make sure that
1896                * all negative literals are installed
1897                * no positive literal is installed
1898                * i.e. the rule is not fulfilled and we
1899                * just need to decide on the positive literals
1900                */
1901               if (r->p < 0)
1902                 {
1903                   if (solv->decisionmap[-r->p] <= 0)
1904                     continue;
1905                 }
1906               else
1907                 {
1908                   if (solv->decisionmap[r->p] > 0)
1909                     continue;
1910                   if (solv->decisionmap[r->p] == 0)
1911                     queue_push(&dq, r->p);
1912                 }
1913               dp = pool->whatprovidesdata + r->d;
1914               while ((p = *dp++) != 0)
1915                 {
1916                   if (p < 0)
1917                     {
1918                       if (solv->decisionmap[-p] <= 0)
1919                         break;
1920                     }
1921                   else
1922                     {
1923                       if (solv->decisionmap[p] > 0)
1924                         break;
1925                       if (solv->decisionmap[p] == 0)
1926                         queue_push(&dq, p);
1927                     }
1928                 }
1929               if (p)
1930                 continue;
1931             }
1932           IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
1933             {
1934               POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "unfulfilled ");
1935               solver_printruleclass(solv, SOLV_DEBUG_PROPAGATE, r);
1936             }
1937           /* dq.count < 2 cannot happen as this means that
1938            * the rule is unit */
1939           assert(dq.count > 1);
1940
1941           olevel = level;
1942           level = selectandinstall(solv, level, &dq, disablerules, r - solv->rules);
1943           if (level == 0)
1944             break;              /* unsolvable */
1945           if (level < systemlevel || level == 1)
1946             break;              /* trouble */
1947           /* something changed, so look at all rules again */
1948           n = 0;
1949         }
1950
1951       if (n != solv->nrules)    /* ran into trouble? */
1952         {
1953           if (level == 0)
1954             break;              /* unsolvable */
1955           continue;             /* start over */
1956         }
1957
1958       /* at this point we have a consistent system. now do the extras... */
1959
1960       solv->decisioncnt_weak = solv->decisionq.count;
1961       if (doweak)
1962         {
1963           int qcount;
1964
1965           POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended packages\n");
1966           queue_empty(&dq);     /* recommended packages */
1967           queue_empty(&dqs);    /* supplemented packages */
1968           for (i = 1; i < pool->nsolvables; i++)
1969             {
1970               if (solv->decisionmap[i] < 0)
1971                 continue;
1972               if (solv->decisionmap[i] > 0)
1973                 {
1974                   /* installed, check for recommends */
1975                   Id *recp, rec, pp, p;
1976                   s = pool->solvables + i;
1977                   if (!solv->addalreadyrecommended && s->repo == solv->installed)
1978                     continue;
1979                   /* XXX need to special case AND ? */
1980                   if (s->recommends)
1981                     {
1982                       recp = s->repo->idarraydata + s->recommends;
1983                       while ((rec = *recp++) != 0)
1984                         {
1985                           qcount = dq.count;
1986                           FOR_PROVIDES(p, pp, rec)
1987                             {
1988                               if (solv->decisionmap[p] > 0)
1989                                 {
1990                                   dq.count = qcount;
1991                                   break;
1992                                 }
1993                               else if (solv->decisionmap[p] == 0)
1994                                 {
1995                                   if (solv->dupmap_all && solv->installed && pool->solvables[p].repo == solv->installed && (solv->droporphanedmap_all || (solv->droporphanedmap.size && MAPTST(&solv->droporphanedmap, p - solv->installed->start))))
1996                                     continue;
1997                                   queue_pushunique(&dq, p);
1998                                 }
1999                             }
2000                         }
2001                     }
2002                 }
2003               else
2004                 {
2005                   s = pool->solvables + i;
2006                   if (!s->supplements)
2007                     continue;
2008                   if (!pool_installable(pool, s))
2009                     continue;
2010                   if (!solver_is_supplementing(solv, s))
2011                     continue;
2012                   if (solv->dupmap_all && solv->installed && s->repo == solv->installed && (solv->droporphanedmap_all || (solv->droporphanedmap.size && MAPTST(&solv->droporphanedmap, i - solv->installed->start))))
2013                     continue;
2014                   queue_push(&dqs, i);
2015                 }
2016             }
2017
2018           /* filter out all packages obsoleted by installed packages */
2019           /* this is no longer needed if we have reverse obsoletes */
2020           if ((dqs.count || dq.count) && solv->installed)
2021             {
2022               Map obsmap;
2023               Id obs, *obsp, po, ppo;
2024
2025               map_init(&obsmap, pool->nsolvables);
2026               for (p = solv->installed->start; p < solv->installed->end; p++)
2027                 {
2028                   s = pool->solvables + p;
2029                   if (s->repo != solv->installed || !s->obsoletes)
2030                     continue;
2031                   if (solv->decisionmap[p] <= 0)
2032                     continue;
2033                   if (solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p))
2034                     continue;
2035                   obsp = s->repo->idarraydata + s->obsoletes;
2036                   /* foreach obsoletes */
2037                   while ((obs = *obsp++) != 0)
2038                     FOR_PROVIDES(po, ppo, obs)
2039                       MAPSET(&obsmap, po);
2040                 }
2041               for (i = j = 0; i < dqs.count; i++)
2042                 if (!MAPTST(&obsmap, dqs.elements[i]))
2043                   dqs.elements[j++] = dqs.elements[i];
2044               dqs.count = j;
2045               for (i = j = 0; i < dq.count; i++)
2046                 if (!MAPTST(&obsmap, dq.elements[i]))
2047                   dq.elements[j++] = dq.elements[i];
2048               dq.count = j;
2049               map_free(&obsmap);
2050             }
2051
2052           /* filter out all already supplemented packages if requested */
2053           if (!solv->addalreadyrecommended && dqs.count)
2054             {
2055               /* turn off all new packages */
2056               for (i = 0; i < solv->decisionq.count; i++)
2057                 {
2058                   p = solv->decisionq.elements[i];
2059                   if (p < 0)
2060                     continue;
2061                   s = pool->solvables + p;
2062                   if (s->repo && s->repo != solv->installed)
2063                     solv->decisionmap[p] = -solv->decisionmap[p];
2064                 }
2065               /* filter out old supplements */
2066               for (i = j = 0; i < dqs.count; i++)
2067                 {
2068                   p = dqs.elements[i];
2069                   s = pool->solvables + p;
2070                   if (!s->supplements)
2071                     continue;
2072                   if (!solver_is_supplementing(solv, s))
2073                     dqs.elements[j++] = p;
2074                 }
2075               dqs.count = j;
2076               /* undo turning off */
2077               for (i = 0; i < solv->decisionq.count; i++)
2078                 {
2079                   p = solv->decisionq.elements[i];
2080                   if (p < 0)
2081                     continue;
2082                   s = pool->solvables + p;
2083                   if (s->repo && s->repo != solv->installed)
2084                     solv->decisionmap[p] = -solv->decisionmap[p];
2085                 }
2086             }
2087
2088           /* multiversion doesn't mix well with supplements.
2089            * filter supplemented packages where we already decided
2090            * to install a different version (see bnc#501088) */
2091           if (dqs.count && solv->noobsoletes.size)
2092             {
2093               for (i = j = 0; i < dqs.count; i++)
2094                 {
2095                   p = dqs.elements[i];
2096                   if (MAPTST(&solv->noobsoletes, p))
2097                     {
2098                       Id p2, pp2;
2099                       s = pool->solvables + p;
2100                       FOR_PROVIDES(p2, pp2, s->name)
2101                         if (solv->decisionmap[p2] > 0 && pool->solvables[p2].name == s->name)
2102                           break;
2103                       if (p2)
2104                         continue;       /* ignore this package */
2105                     }
2106                   dqs.elements[j++] = p;
2107                 }
2108               dqs.count = j;
2109             }
2110
2111           /* make dq contain both recommended and supplemented pkgs */
2112           if (dqs.count)
2113             {
2114               for (i = 0; i < dqs.count; i++)
2115                 queue_pushunique(&dq, dqs.elements[i]);
2116             }
2117
2118           if (dq.count)
2119             {
2120               Map dqmap;
2121               int decisioncount = solv->decisionq.count;
2122
2123               if (dq.count == 1)
2124                 {
2125                   /* simple case, just one package. no need to choose to best version */
2126                   p = dq.elements[0];
2127                   if (dqs.count)
2128                     POOL_DEBUG(SOLV_DEBUG_POLICY, "installing supplemented %s\n", pool_solvid2str(pool, p));
2129                   else
2130                     POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended %s\n", pool_solvid2str(pool, p));
2131                   level = setpropagatelearn(solv, level, p, 0, 0);
2132                   if (level == 0)
2133                     break;
2134                   continue;     /* back to main loop */
2135                 }
2136
2137               /* filter packages, this gives us the best versions */
2138               policy_filter_unwanted(solv, &dq, POLICY_MODE_RECOMMEND);
2139
2140               /* create map of result */
2141               map_init(&dqmap, pool->nsolvables);
2142               for (i = 0; i < dq.count; i++)
2143                 MAPSET(&dqmap, dq.elements[i]);
2144
2145               /* install all supplemented packages */
2146               for (i = 0; i < dqs.count; i++)
2147                 {
2148                   p = dqs.elements[i];
2149                   if (solv->decisionmap[p] || !MAPTST(&dqmap, p))
2150                     continue;
2151                   POOL_DEBUG(SOLV_DEBUG_POLICY, "installing supplemented %s\n", pool_solvid2str(pool, p));
2152                   olevel = level;
2153                   level = setpropagatelearn(solv, level, p, 0, 0);
2154                   if (level <= olevel)
2155                     break;
2156                 }
2157               if (i < dqs.count || solv->decisionq.count < decisioncount)
2158                 {
2159                   map_free(&dqmap);
2160                   if (level == 0)
2161                     break;
2162                   continue;
2163                 }
2164
2165               /* install all recommended packages */
2166               /* more work as we want to created branches if multiple
2167                * choices are valid */
2168               for (i = 0; i < decisioncount; i++)
2169                 {
2170                   Id rec, *recp, pp;
2171                   p = solv->decisionq.elements[i];
2172                   if (p < 0)
2173                     continue;
2174                   s = pool->solvables + p;
2175                   if (!s->repo || (!solv->addalreadyrecommended && s->repo == solv->installed))
2176                     continue;
2177                   if (!s->recommends)
2178                     continue;
2179                   recp = s->repo->idarraydata + s->recommends;
2180                   while ((rec = *recp++) != 0)
2181                     {
2182                       queue_empty(&dq);
2183                       FOR_PROVIDES(p, pp, rec)
2184                         {
2185                           if (solv->decisionmap[p] > 0)
2186                             {
2187                               dq.count = 0;
2188                               break;
2189                             }
2190                           else if (solv->decisionmap[p] == 0 && MAPTST(&dqmap, p))
2191                             queue_pushunique(&dq, p);
2192                         }
2193                       if (!dq.count)
2194                         continue;
2195                       if (dq.count > 1)
2196                         {
2197                           /* multiple candidates, open a branch */
2198                           for (i = 1; i < dq.count; i++)
2199                             queue_push(&solv->branches, dq.elements[i]);
2200                           queue_push(&solv->branches, -level);
2201                         }
2202                       p = dq.elements[0];
2203                       POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended %s\n", pool_solvid2str(pool, p));
2204                       olevel = level;
2205                       level = setpropagatelearn(solv, level, p, 0, 0);
2206                       if (level <= olevel || solv->decisionq.count < decisioncount)
2207                         break;  /* we had to revert some decisions */
2208                     }
2209                   if (rec)
2210                     break;      /* had a problem above, quit loop */
2211                 }
2212               map_free(&dqmap);
2213               if (level == 0)
2214                 break;
2215               continue;         /* back to main loop so that all deps are checked */
2216             }
2217         }
2218
2219       solv->decisioncnt_orphan = solv->decisionq.count;
2220       if (solv->dupmap_all && solv->installed)
2221         {
2222           int installedone = 0;
2223
2224           /* let's see if we can install some unsupported package */
2225           POOL_DEBUG(SOLV_DEBUG_SOLVER, "deciding orphaned packages\n");
2226           for (i = 0; i < solv->orphaned.count; i++)
2227             {
2228               p = solv->orphaned.elements[i];
2229               if (solv->decisionmap[p])
2230                 continue;       /* already decided */
2231               if (solv->droporphanedmap_all)
2232                 continue;
2233               if (solv->droporphanedmap.size && MAPTST(&solv->droporphanedmap, p - solv->installed->start))
2234                 continue;
2235               POOL_DEBUG(SOLV_DEBUG_SOLVER, "keeping orphaned %s\n", pool_solvid2str(pool, p));
2236               olevel = level;
2237               level = setpropagatelearn(solv, level, p, 0, 0);
2238               installedone = 1;
2239               if (level < olevel)
2240                 break;
2241             }
2242           if (installedone || i < solv->orphaned.count)
2243             {
2244               if (level == 0)
2245                 break;
2246               continue;         /* back to main loop */
2247             }
2248           for (i = 0; i < solv->orphaned.count; i++)
2249             {
2250               p = solv->orphaned.elements[i];
2251               if (solv->decisionmap[p])
2252                 continue;       /* already decided */
2253               POOL_DEBUG(SOLV_DEBUG_SOLVER, "removing orphaned %s\n", pool_solvid2str(pool, p));
2254               olevel = level;
2255               level = setpropagatelearn(solv, level, -p, 0, 0);
2256               if (level < olevel)
2257                 break;
2258             }
2259           if (i < solv->orphaned.count)
2260             {
2261               if (level == 0)
2262                 break;
2263               continue;         /* back to main loop */
2264             }
2265         }
2266
2267      if (solv->installed && solv->cleandepsmap.size)
2268         {
2269           if (cleandeps_check_mistakes(solv, level))
2270             {
2271               level = 1;        /* restart from scratch */
2272               continue;
2273             }
2274         }
2275
2276      if (solv->solution_callback)
2277         {
2278           solv->solution_callback(solv, solv->solution_callback_data);
2279           if (solv->branches.count)
2280             {
2281               int i = solv->branches.count - 1;
2282               int l = -solv->branches.elements[i];
2283               Id why;
2284
2285               for (; i > 0; i--)
2286                 if (solv->branches.elements[i - 1] < 0)
2287                   break;
2288               p = solv->branches.elements[i];
2289               POOL_DEBUG(SOLV_DEBUG_SOLVER, "branching with %s\n", pool_solvid2str(pool, p));
2290               queue_empty(&dq);
2291               for (j = i + 1; j < solv->branches.count; j++)
2292                 queue_push(&dq, solv->branches.elements[j]);
2293               solv->branches.count = i;
2294               level = l;
2295               revert(solv, level);
2296               if (dq.count > 1)
2297                 for (j = 0; j < dq.count; j++)
2298                   queue_push(&solv->branches, dq.elements[j]);
2299               olevel = level;
2300               why = -solv->decisionq_why.elements[solv->decisionq_why.count];
2301               assert(why >= 0);
2302               level = setpropagatelearn(solv, level, p, disablerules, why);
2303               if (level == 0)
2304                 break;
2305               continue;
2306             }
2307           /* all branches done, we're finally finished */
2308           break;
2309         }
2310
2311       /* auto-minimization step */
2312      if (solv->branches.count)
2313         {
2314           int l = 0, lasti = -1, lastl = -1;
2315           Id why;
2316
2317           p = 0;
2318           for (i = solv->branches.count - 1; i >= 0; i--)
2319             {
2320               p = solv->branches.elements[i];
2321               if (p < 0)
2322                 l = -p;
2323               else if (p > 0 && solv->decisionmap[p] > l + 1)
2324                 {
2325                   lasti = i;
2326                   lastl = l;
2327                 }
2328             }
2329           if (lasti >= 0)
2330             {
2331               /* kill old solvable so that we do not loop */
2332               p = solv->branches.elements[lasti];
2333               solv->branches.elements[lasti] = 0;
2334               POOL_DEBUG(SOLV_DEBUG_SOLVER, "minimizing %d -> %d with %s\n", solv->decisionmap[p], lastl, pool_solvid2str(pool, p));
2335               minimizationsteps++;
2336
2337               level = lastl;
2338               revert(solv, level);
2339               why = -solv->decisionq_why.elements[solv->decisionq_why.count];
2340               assert(why >= 0);
2341               olevel = level;
2342               level = setpropagatelearn(solv, level, p, disablerules, why);
2343               if (level == 0)
2344                 break;
2345               continue;         /* back to main loop */
2346             }
2347         }
2348       /* no minimization found, we're finally finished! */
2349       break;
2350     }
2351
2352   POOL_DEBUG(SOLV_DEBUG_STATS, "solver statistics: %d learned rules, %d unsolvable, %d minimization steps\n", solv->stats_learned, solv->stats_unsolvable, minimizationsteps);
2353
2354   POOL_DEBUG(SOLV_DEBUG_STATS, "done solving.\n\n");
2355   queue_free(&dq);
2356   queue_free(&dqs);
2357   if (level == 0)
2358     {
2359       /* unsolvable */
2360       solv->decisioncnt_update = solv->decisionq.count;
2361       solv->decisioncnt_keep = solv->decisionq.count;
2362       solv->decisioncnt_resolve = solv->decisionq.count;
2363       solv->decisioncnt_weak = solv->decisionq.count;
2364       solv->decisioncnt_orphan = solv->decisionq.count;
2365     }
2366 #if 0
2367   solver_printdecisionq(solv, SOLV_DEBUG_RESULT);
2368 #endif
2369 }
2370
2371
2372 /*-------------------------------------------------------------------
2373  *
2374  * remove disabled conflicts
2375  *
2376  * purpose: update the decisionmap after some rules were disabled.
2377  * this is used to calculate the suggested/recommended package list.
2378  * Also returns a "removed" list to undo the discisionmap changes.
2379  */
2380
2381 static void
2382 removedisabledconflicts(Solver *solv, Queue *removed)
2383 {
2384   Pool *pool = solv->pool;
2385   int i, n;
2386   Id p, why, *dp;
2387   Id new;
2388   Rule *r;
2389   Id *decisionmap = solv->decisionmap;
2390
2391   queue_empty(removed);
2392   for (i = 0; i < solv->decisionq.count; i++)
2393     {
2394       p = solv->decisionq.elements[i];
2395       if (p > 0)
2396         continue;       /* conflicts only, please */
2397       why = solv->decisionq_why.elements[i];
2398       if (why == 0)
2399         {
2400           /* no rule involved, must be a orphan package drop */
2401           continue;
2402         }
2403       /* we never do conflicts on free decisions, so there
2404        * must have been an unit rule */
2405       assert(why > 0);
2406       r = solv->rules + why;
2407       if (r->d < 0 && decisionmap[-p])
2408         {
2409           /* rule is now disabled, remove from decisionmap */
2410           POOL_DEBUG(SOLV_DEBUG_SOLVER, "removing conflict for package %s[%d]\n", pool_solvid2str(pool, -p), -p);
2411           queue_push(removed, -p);
2412           queue_push(removed, decisionmap[-p]);
2413           decisionmap[-p] = 0;
2414         }
2415     }
2416   if (!removed->count)
2417     return;
2418   /* we removed some confliced packages. some of them might still
2419    * be in conflict, so search for unit rules and re-conflict */
2420   new = 0;
2421   for (i = n = 1, r = solv->rules + i; n < solv->nrules; i++, r++, n++)
2422     {
2423       if (i == solv->nrules)
2424         {
2425           i = 1;
2426           r = solv->rules + i;
2427         }
2428       if (r->d < 0)
2429         continue;
2430       if (!r->w2)
2431         {
2432           if (r->p < 0 && !decisionmap[-r->p])
2433             new = r->p;
2434         }
2435       else if (!r->d)
2436         {
2437           /* binary rule */
2438           if (r->p < 0 && decisionmap[-r->p] == 0 && DECISIONMAP_FALSE(r->w2))
2439             new = r->p;
2440           else if (r->w2 < 0 && decisionmap[-r->w2] == 0 && DECISIONMAP_FALSE(r->p))
2441             new = r->w2;
2442         }
2443       else
2444         {
2445           if (r->p < 0 && decisionmap[-r->p] == 0)
2446             new = r->p;
2447           if (new || DECISIONMAP_FALSE(r->p))
2448             {
2449               dp = pool->whatprovidesdata + r->d;
2450               while ((p = *dp++) != 0)
2451                 {
2452                   if (new && p == new)
2453                     continue;
2454                   if (p < 0 && decisionmap[-p] == 0)
2455                     {
2456                       if (new)
2457                         {
2458                           new = 0;
2459                           break;
2460                         }
2461                       new = p;
2462                     }
2463                   else if (!DECISIONMAP_FALSE(p))
2464                     {
2465                       new = 0;
2466                       break;
2467                     }
2468                 }
2469             }
2470         }
2471       if (new)
2472         {
2473           POOL_DEBUG(SOLV_DEBUG_SOLVER, "re-conflicting package %s[%d]\n", pool_solvid2str(pool, -new), -new);
2474           decisionmap[-new] = -1;
2475           new = 0;
2476           n = 0;        /* redo all rules */
2477         }
2478     }
2479 }
2480
2481 static inline void
2482 undo_removedisabledconflicts(Solver *solv, Queue *removed)
2483 {
2484   int i;
2485   for (i = 0; i < removed->count; i += 2)
2486     solv->decisionmap[removed->elements[i]] = removed->elements[i + 1];
2487 }
2488
2489
2490 /*-------------------------------------------------------------------
2491  *
2492  * weaken solvable dependencies
2493  */
2494
2495 static void
2496 weaken_solvable_deps(Solver *solv, Id p)
2497 {
2498   int i;
2499   Rule *r;
2500
2501   for (i = 1, r = solv->rules + i; i < solv->rpmrules_end; i++, r++)
2502     {
2503       if (r->p != -p)
2504         continue;
2505       if ((r->d == 0 || r->d == -1) && r->w2 < 0)
2506         continue;       /* conflict */
2507       queue_push(&solv->weakruleq, i);
2508     }
2509 }
2510
2511
2512 /********************************************************************/
2513 /* main() */
2514
2515
2516 void
2517 solver_calculate_noobsmap(Pool *pool, Queue *job, Map *noobsmap)
2518 {
2519   int i;
2520   Id how, what, select;
2521   Id p, pp;
2522   for (i = 0; i < job->count; i += 2)
2523     {
2524       how = job->elements[i];
2525       if ((how & SOLVER_JOBMASK) != SOLVER_NOOBSOLETES)
2526         continue;
2527       what = job->elements[i + 1];
2528       select = how & SOLVER_SELECTMASK;
2529       if (!noobsmap->size)
2530         map_grow(noobsmap, pool->nsolvables);
2531       FOR_JOB_SELECT(p, pp, select, what)
2532         MAPSET(noobsmap, p);
2533     }
2534 }
2535
2536 /*
2537  * add a rule created by a job, record job number and weak flag
2538  */
2539 static inline void
2540 solver_addjobrule(Solver *solv, Id p, Id d, Id job, int weak)
2541 {
2542   solver_addrule(solv, p, d);
2543   queue_push(&solv->ruletojob, job);
2544   if (weak)
2545     queue_push(&solv->weakruleq, solv->nrules - 1);
2546 }
2547
2548 /*
2549  *
2550  * solve job queue
2551  *
2552  */
2553
2554 int
2555 solver_solve(Solver *solv, Queue *job)
2556 {
2557   Pool *pool = solv->pool;
2558   Repo *installed = solv->installed;
2559   int i;
2560   int oldnrules;
2561   Map addedmap;                /* '1' == have rpm-rules for solvable */
2562   Map installcandidatemap;
2563   Id how, what, select, name, weak, p, pp, d;
2564   Queue q;
2565   Solvable *s;
2566   Rule *r;
2567   int now, solve_start;
2568   int hasdupjob = 0;
2569
2570   solve_start = solv_timems(0);
2571
2572   /* log solver options */
2573   POOL_DEBUG(SOLV_DEBUG_STATS, "solver started\n");
2574   POOL_DEBUG(SOLV_DEBUG_STATS, "dosplitprovides=%d, noupdateprovide=%d, noinfarchcheck=%d\n", solv->dosplitprovides, solv->noupdateprovide, solv->noinfarchcheck);
2575   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);
2576   POOL_DEBUG(SOLV_DEBUG_STATS, "promoteepoch=%d, forbidselfconflicts=%d\n", pool->promoteepoch, pool->forbidselfconflicts);
2577   POOL_DEBUG(SOLV_DEBUG_STATS, "obsoleteusesprovides=%d, implicitobsoleteusesprovides=%d, obsoleteusescolors=%d\n", pool->obsoleteusesprovides, pool->implicitobsoleteusesprovides, pool->obsoleteusescolors);
2578   POOL_DEBUG(SOLV_DEBUG_STATS, "dontinstallrecommended=%d, addalreadyrecommended=%d\n", solv->dontinstallrecommended, solv->addalreadyrecommended);
2579
2580   /* create whatprovides if not already there */
2581   if (!pool->whatprovides)
2582     pool_createwhatprovides(pool);
2583
2584   /* create obsolete index */
2585   policy_create_obsolete_index(solv);
2586
2587   /* remember job */
2588   queue_free(&solv->job);
2589   queue_init_clone(&solv->job, job);
2590
2591   /*
2592    * create basic rule set of all involved packages
2593    * use addedmap bitmap to make sure we don't create rules twice
2594    */
2595
2596   /* create noobsolete map if needed */
2597   solver_calculate_noobsmap(pool, job, &solv->noobsoletes);
2598
2599   map_init(&addedmap, pool->nsolvables);
2600   MAPSET(&addedmap, SYSTEMSOLVABLE);
2601
2602   map_init(&installcandidatemap, pool->nsolvables);
2603   queue_init(&q);
2604
2605   now = solv_timems(0);
2606   /*
2607    * create rules for all package that could be involved with the solving
2608    * so called: rpm rules
2609    *
2610    */
2611   if (installed)
2612     {
2613       /* check for update/verify jobs as they need to be known early */
2614       for (i = 0; i < job->count; i += 2)
2615         {
2616           how = job->elements[i];
2617           what = job->elements[i + 1];
2618           select = how & SOLVER_SELECTMASK;
2619           switch (how & SOLVER_JOBMASK)
2620             {
2621             case SOLVER_VERIFY:
2622               if (select == SOLVER_SOLVABLE_ALL)
2623                 solv->fixmap_all = 1;
2624               FOR_JOB_SELECT(p, pp, select, what)
2625                 {
2626                   s = pool->solvables + p;
2627                   if (!solv->installed || s->repo != solv->installed)
2628                     continue;
2629                   if (!solv->fixmap.size)
2630                     map_grow(&solv->fixmap, solv->installed->end - solv->installed->start);
2631                   MAPSET(&solv->fixmap, p - solv->installed->start);
2632                 }
2633               break;
2634             case SOLVER_UPDATE:
2635               if (select == SOLVER_SOLVABLE_ALL)
2636                 solv->updatemap_all = 1;
2637               FOR_JOB_SELECT(p, pp, select, what)
2638                 {
2639                   s = pool->solvables + p;
2640                   if (!solv->installed || s->repo != solv->installed)
2641                     continue;
2642                   if (!solv->updatemap.size)
2643                     map_grow(&solv->updatemap, solv->installed->end - solv->installed->start);
2644                   MAPSET(&solv->updatemap, p - solv->installed->start);
2645                 }
2646               break;
2647             default:
2648               break;
2649             }
2650         }
2651
2652       oldnrules = solv->nrules;
2653       FOR_REPO_SOLVABLES(installed, p, s)
2654         solver_addrpmrulesforsolvable(solv, s, &addedmap);
2655       POOL_DEBUG(SOLV_DEBUG_STATS, "added %d rpm rules for installed solvables\n", solv->nrules - oldnrules);
2656       oldnrules = solv->nrules;
2657       FOR_REPO_SOLVABLES(installed, p, s)
2658         solver_addrpmrulesforupdaters(solv, s, &addedmap, 1);
2659       POOL_DEBUG(SOLV_DEBUG_STATS, "added %d rpm rules for updaters of installed solvables\n", solv->nrules - oldnrules);
2660     }
2661
2662   /*
2663    * create rules for all packages involved in the job
2664    * (to be installed or removed)
2665    */
2666
2667   oldnrules = solv->nrules;
2668   for (i = 0; i < job->count; i += 2)
2669     {
2670       how = job->elements[i];
2671       what = job->elements[i + 1];
2672       select = how & SOLVER_SELECTMASK;
2673
2674       switch (how & SOLVER_JOBMASK)
2675         {
2676         case SOLVER_INSTALL:
2677           FOR_JOB_SELECT(p, pp, select, what)
2678             {
2679               MAPSET(&installcandidatemap, p);
2680               solver_addrpmrulesforsolvable(solv, pool->solvables + p, &addedmap);
2681             }
2682           break;
2683         case SOLVER_DISTUPGRADE:
2684           if (select == SOLVER_SOLVABLE_ALL)
2685             {
2686               solv->dupmap_all = 1;
2687               solv->updatemap_all = 1;
2688             }
2689           if (!solv->dupmap_all)
2690             hasdupjob = 1;
2691           break;
2692         default:
2693           break;
2694         }
2695     }
2696   POOL_DEBUG(SOLV_DEBUG_STATS, "added %d rpm rules for packages involved in a job\n", solv->nrules - oldnrules);
2697
2698
2699   /*
2700    * add rules for suggests, enhances
2701    */
2702   oldnrules = solv->nrules;
2703   solver_addrpmrulesforweak(solv, &addedmap);
2704   POOL_DEBUG(SOLV_DEBUG_STATS, "added %d rpm rules because of weak dependencies\n", solv->nrules - oldnrules);
2705
2706   /*
2707    * first pass done, we now have all the rpm rules we need.
2708    * unify existing rules before going over all job rules and
2709    * policy rules.
2710    * at this point the system is always solvable,
2711    * as an empty system (remove all packages) is a valid solution
2712    */
2713
2714   IF_POOLDEBUG (SOLV_DEBUG_STATS)
2715     {
2716       int possible = 0, installable = 0;
2717       for (i = 1; i < pool->nsolvables; i++)
2718         {
2719           if (pool_installable(pool, pool->solvables + i))
2720             installable++;
2721           if (MAPTST(&addedmap, i))
2722             possible++;
2723         }
2724       POOL_DEBUG(SOLV_DEBUG_STATS, "%d of %d installable solvables considered for solving\n", possible, installable);
2725     }
2726
2727   solver_unifyrules(solv);                          /* remove duplicate rpm rules */
2728   solv->rpmrules_end = solv->nrules;              /* mark end of rpm rules */
2729
2730   POOL_DEBUG(SOLV_DEBUG_STATS, "rpm rule memory used: %d K\n", solv->nrules * (int)sizeof(Rule) / 1024);
2731   POOL_DEBUG(SOLV_DEBUG_STATS, "rpm rule creation took %d ms\n", solv_timems(now));
2732
2733   /* create dup maps if needed. We need the maps early to create our
2734    * update rules */
2735   if (hasdupjob)
2736     solver_createdupmaps(solv);
2737
2738   /*
2739    * create feature rules
2740    *
2741    * foreach installed:
2742    *   create assertion (keep installed, if no update available)
2743    *   or
2744    *   create update rule (A|update1(A)|update2(A)|...)
2745    *
2746    * those are used later on to keep a version of the installed packages in
2747    * best effort mode
2748    */
2749
2750   solv->featurerules = solv->nrules;              /* mark start of feature rules */
2751   if (installed)
2752     {
2753       /* foreach possibly installed solvable */
2754       for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
2755         {
2756           if (s->repo != installed)
2757             {
2758               solver_addrule(solv, 0, 0);       /* create dummy rule */
2759               continue;
2760             }
2761           solver_addupdaterule(solv, s, 1);    /* allow s to be updated */
2762         }
2763       /* make sure we accounted for all rules */
2764       assert(solv->nrules - solv->featurerules == installed->end - installed->start);
2765     }
2766   solv->featurerules_end = solv->nrules;
2767
2768     /*
2769      * Add update rules for installed solvables
2770      *
2771      * almost identical to feature rules
2772      * except that downgrades/archchanges/vendorchanges are not allowed
2773      */
2774
2775   solv->updaterules = solv->nrules;
2776
2777   if (installed)
2778     { /* foreach installed solvables */
2779       /* we create all update rules, but disable some later on depending on the job */
2780       for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
2781         {
2782           Rule *sr;
2783
2784           if (s->repo != installed)
2785             {
2786               solver_addrule(solv, 0, 0);       /* create dummy rule */
2787               continue;
2788             }
2789           solver_addupdaterule(solv, s, 0);     /* allowall = 0: downgrades not allowed */
2790           /*
2791            * check for and remove duplicate
2792            */
2793           r = solv->rules + solv->nrules - 1;           /* r: update rule */
2794           sr = r - (installed->end - installed->start); /* sr: feature rule */
2795           /* it's orphaned if there is no feature rule or the feature rule
2796            * consists just of the installed package */
2797           if (!sr->p || (sr->p == i && !sr->d && !sr->w2))
2798             queue_push(&solv->orphaned, i);
2799           if (!r->p)
2800             {
2801               assert(solv->dupmap_all && !sr->p);
2802               continue;
2803             }
2804           if (!solver_samerule(solv, r, sr))
2805             memset(sr, 0, sizeof(*sr));         /* delete unneeded feature rule */
2806           else
2807             solver_disablerule(solv, sr);       /* disable feature rule */
2808         }
2809       /* consistency check: we added a rule for _every_ installed solvable */
2810       assert(solv->nrules - solv->updaterules == installed->end - installed->start);
2811     }
2812   solv->updaterules_end = solv->nrules;
2813
2814
2815   /*
2816    * now add all job rules
2817    */
2818
2819   solv->jobrules = solv->nrules;
2820   if (solv->cleandeps_updatepkgs)
2821     {
2822       queue_free(solv->cleandeps_updatepkgs);
2823       solv->cleandeps_updatepkgs = solv_free(solv->cleandeps_updatepkgs);
2824     }
2825   for (i = 0; i < job->count; i += 2)
2826     {
2827       oldnrules = solv->nrules;
2828
2829       how = job->elements[i];
2830       what = job->elements[i + 1];
2831       weak = how & SOLVER_WEAK;
2832       select = how & SOLVER_SELECTMASK;
2833       switch (how & SOLVER_JOBMASK)
2834         {
2835         case SOLVER_INSTALL:
2836           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sinstall %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
2837           if ((how & SOLVER_CLEANDEPS) != 0 && !solv->cleandepsmap.size && installed)
2838             map_grow(&solv->cleandepsmap, installed->end - installed->start);
2839           if (select == SOLVER_SOLVABLE)
2840             {
2841               p = what;
2842               d = 0;
2843             }
2844           else
2845             {
2846               queue_empty(&q);
2847               FOR_JOB_SELECT(p, pp, select, what)
2848                 queue_push(&q, p);
2849               if (!q.count)
2850                 {
2851                   /* no candidate found, make this an impossible rule */
2852                   queue_push(&q, -SYSTEMSOLVABLE);
2853                 }
2854               p = queue_shift(&q);      /* get first candidate */
2855               d = !q.count ? 0 : pool_queuetowhatprovides(pool, &q);    /* internalize */
2856             }
2857           solver_addjobrule(solv, p, d, i, weak);
2858           break;
2859         case SOLVER_ERASE:
2860           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %s%serase %s\n", weak ? "weak " : "", how & SOLVER_CLEANDEPS ? "clean deps " : "", solver_select2str(pool, select, what));
2861           if ((how & SOLVER_CLEANDEPS) != 0 && !solv->cleandepsmap.size && installed)
2862             map_grow(&solv->cleandepsmap, installed->end - installed->start);
2863           name = (select == SOLVER_SOLVABLE || (select == SOLVER_SOLVABLE_NAME && ISRELDEP(what))) ? 0 : -1;
2864           FOR_JOB_SELECT(p, pp, select, what)
2865             {
2866               s = pool->solvables + p;
2867               if (installed && s->repo == installed)
2868                 name = !name ? s->name : -1;
2869               solver_addjobrule(solv, -p, 0, i, weak);
2870             }
2871           /* special case for "erase a specific solvable": we also
2872            * erase all other solvables with that name, so that they
2873            * don't get picked up as replacement.
2874            * name is > 0 if exactly one installed solvable matched.
2875            */
2876           /* XXX: look also at packages that obsolete this package? */
2877           if (name > 0)
2878             {
2879               int j, k;
2880               k = solv->nrules;
2881               FOR_PROVIDES(p, pp, name)
2882                 {
2883                   s = pool->solvables + p;
2884                   if (s->name != name)
2885                     continue;
2886                   /* keep other versions installed */
2887                   if (s->repo == installed)
2888                     continue;
2889                   /* keep installcandidates of other jobs */
2890                   if (MAPTST(&installcandidatemap, p))
2891                     continue;
2892                   /* don't add the same rule twice */
2893                   for (j = oldnrules; j < k; j++)
2894                     if (solv->rules[j].p == -p)
2895                       break;
2896                   if (j == k)
2897                     solver_addjobrule(solv, -p, 0, i, weak);    /* remove by id */
2898                 }
2899             }
2900           break;
2901
2902         case SOLVER_UPDATE:
2903           if ((how & SOLVER_CLEANDEPS) != 0 && installed)
2904             {
2905               FOR_JOB_SELECT(p, pp, select, what)
2906                 {
2907                   s = pool->solvables + p;
2908                   if (s->repo != installed)
2909                     continue;
2910                   if (!solv->cleandeps_updatepkgs)
2911                     {
2912                       solv->cleandeps_updatepkgs = solv_calloc(1, sizeof(Queue));
2913                       queue_init(solv->cleandeps_updatepkgs);
2914                     }
2915                   queue_pushunique(solv->cleandeps_updatepkgs, p);
2916                   if (!solv->cleandepsmap.size)
2917                     map_grow(&solv->cleandepsmap, installed->end - installed->start);
2918                 }
2919             }
2920           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %supdate %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
2921           break;
2922         case SOLVER_VERIFY:
2923           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sverify %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
2924           break;
2925         case SOLVER_WEAKENDEPS:
2926           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sweaken deps %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
2927           if (select != SOLVER_SOLVABLE)
2928             break;
2929           s = pool->solvables + what;
2930           weaken_solvable_deps(solv, what);
2931           break;
2932         case SOLVER_NOOBSOLETES:
2933           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sno obsolete %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
2934           break;
2935         case SOLVER_LOCK:
2936           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %slock %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
2937           FOR_JOB_SELECT(p, pp, select, what)
2938             {
2939               s = pool->solvables + p;
2940               solver_addjobrule(solv, installed && s->repo == installed ? p : -p, 0, i, weak);
2941             }
2942           break;
2943         case SOLVER_DISTUPGRADE:
2944           POOL_DEBUG(SOLV_DEBUG_JOB, "job: distupgrade %s\n", solver_select2str(pool, select, what));
2945           break;
2946         case SOLVER_DROP_ORPHANED:
2947           POOL_DEBUG(SOLV_DEBUG_JOB, "job: drop orphaned %s\n", solver_select2str(pool, select, what));
2948           if (select == SOLVER_SOLVABLE_ALL)
2949             solv->droporphanedmap_all = 1;
2950           FOR_JOB_SELECT(p, pp, select, what)
2951             {
2952               s = pool->solvables + p;
2953               if (!installed || s->repo != installed)
2954                 continue;
2955               if (!solv->droporphanedmap.size)
2956                 map_grow(&solv->droporphanedmap, installed->end - installed->start);
2957               MAPSET(&solv->droporphanedmap, p - installed->start);
2958             }
2959           break;
2960         case SOLVER_USERINSTALLED:
2961           POOL_DEBUG(SOLV_DEBUG_JOB, "job: user installed %s\n", solver_select2str(pool, select, what));
2962           break;
2963         default:
2964           POOL_DEBUG(SOLV_DEBUG_JOB, "job: unknown job\n");
2965           break;
2966         }
2967
2968         /*
2969          * debug
2970          */
2971
2972       IF_POOLDEBUG (SOLV_DEBUG_JOB)
2973         {
2974           int j;
2975           if (solv->nrules == oldnrules)
2976             POOL_DEBUG(SOLV_DEBUG_JOB, " - no rule created\n");
2977           for (j = oldnrules; j < solv->nrules; j++)
2978             {
2979               POOL_DEBUG(SOLV_DEBUG_JOB, " - job ");
2980               solver_printrule(solv, SOLV_DEBUG_JOB, solv->rules + j);
2981             }
2982         }
2983     }
2984   assert(solv->ruletojob.count == solv->nrules - solv->jobrules);
2985   solv->jobrules_end = solv->nrules;
2986
2987   /* now create infarch and dup rules */
2988   if (!solv->noinfarchcheck)
2989     {
2990       solver_addinfarchrules(solv, &addedmap);
2991       if (pool->obsoleteusescolors)
2992         {
2993           /* currently doesn't work well with infarch rules, so make
2994            * them weak */
2995           for (i = solv->infarchrules; i < solv->infarchrules_end; i++)
2996             queue_push(&solv->weakruleq, i);
2997         }
2998     }
2999   else
3000     solv->infarchrules = solv->infarchrules_end = solv->nrules;
3001
3002   if (hasdupjob)
3003     {
3004       solver_addduprules(solv, &addedmap);
3005       solver_freedupmaps(solv); /* no longer needed */
3006     }
3007   else
3008     solv->duprules = solv->duprules_end = solv->nrules;
3009
3010   if (1)
3011     solver_addchoicerules(solv);
3012   else
3013     solv->choicerules = solv->choicerules_end = solv->nrules;
3014
3015   /* all rules created
3016    * --------------------------------------------------------------
3017    * prepare for solving
3018    */
3019
3020   /* free unneeded memory */
3021   map_free(&addedmap);
3022   map_free(&installcandidatemap);
3023   queue_free(&q);
3024
3025   POOL_DEBUG(SOLV_DEBUG_STATS, "%d rpm rules, 2 * %d update rules, %d job rules, %d infarch rules, %d dup rules, %d choice rules\n", solv->rpmrules_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);
3026   POOL_DEBUG(SOLV_DEBUG_STATS, "overall rule memory used: %d K\n", solv->nrules * (int)sizeof(Rule) / 1024);
3027
3028   /* create weak map */
3029   map_init(&solv->weakrulemap, solv->nrules);
3030   for (i = 0; i < solv->weakruleq.count; i++)
3031     {
3032       p = solv->weakruleq.elements[i];
3033       MAPSET(&solv->weakrulemap, p);
3034     }
3035
3036   /* all new rules are learnt after this point */
3037   solv->learntrules = solv->nrules;
3038
3039   /* create watches chains */
3040   makewatches(solv);
3041
3042   /* create assertion index. it is only used to speed up
3043    * makeruledecsions() a bit */
3044   for (i = 1, r = solv->rules + i; i < solv->nrules; i++, r++)
3045     if (r->p && !r->w2 && (r->d == 0 || r->d == -1))
3046       queue_push(&solv->ruleassertions, i);
3047
3048   /* disable update rules that conflict with our job */
3049   solver_disablepolicyrules(solv);
3050
3051   /* make initial decisions based on assertion rules */
3052   makeruledecisions(solv);
3053   POOL_DEBUG(SOLV_DEBUG_SOLVER, "problems so far: %d\n", solv->problems.count);
3054
3055   /* no mistakes */
3056   if (solv->cleandeps_mistakes)
3057     {
3058       queue_free(solv->cleandeps_mistakes);
3059       solv->cleandeps_mistakes = solv_free(solv->cleandeps_mistakes);
3060     }
3061
3062   /*
3063    * ********************************************
3064    * solve!
3065    * ********************************************
3066    */
3067
3068   now = solv_timems(0);
3069   solver_run_sat(solv, 1, solv->dontinstallrecommended ? 0 : 1);
3070   POOL_DEBUG(SOLV_DEBUG_STATS, "solver took %d ms\n", solv_timems(now));
3071
3072   /*
3073    * prepare solution queue if there were problems
3074    */
3075   solver_prepare_solutions(solv);
3076
3077   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);
3078   POOL_DEBUG(SOLV_DEBUG_STATS, "solver_solve took %d ms\n", solv_timems(solve_start));
3079
3080   /* return number of problems */
3081   return solv->problems.count ? solv->problems.count / 2 : 0;
3082 }
3083
3084 Transaction *
3085 solver_create_transaction(Solver *solv)
3086 {
3087   return transaction_create_decisionq(solv->pool, &solv->decisionq, &solv->noobsoletes);
3088 }
3089
3090 void solver_get_orphaned(Solver *solv, Queue *orphanedq)
3091 {
3092   queue_free(orphanedq);
3093   queue_init_clone(orphanedq, &solv->orphaned);
3094 }
3095
3096 void solver_get_recommendations(Solver *solv, Queue *recommendationsq, Queue *suggestionsq, int noselected)
3097 {
3098   Pool *pool = solv->pool;
3099   Queue redoq, disabledq;
3100   int goterase, i;
3101   Solvable *s;
3102   Rule *r;
3103   Map obsmap;
3104
3105   if (!recommendationsq && !suggestionsq)
3106     return;
3107
3108   map_init(&obsmap, pool->nsolvables);
3109   if (solv->installed)
3110     {
3111       Id obs, *obsp, p, po, ppo;
3112       for (p = solv->installed->start; p < solv->installed->end; p++)
3113         {
3114           s = pool->solvables + p;
3115           if (s->repo != solv->installed || !s->obsoletes)
3116             continue;
3117           if (solv->decisionmap[p] <= 0)
3118             continue;
3119           if (solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p))
3120             continue;
3121           obsp = s->repo->idarraydata + s->obsoletes;
3122           /* foreach obsoletes */
3123           while ((obs = *obsp++) != 0)
3124             FOR_PROVIDES(po, ppo, obs)
3125               MAPSET(&obsmap, po);
3126         }
3127     }
3128
3129   queue_init(&redoq);
3130   queue_init(&disabledq);
3131   goterase = 0;
3132   /* disable all erase jobs (including weak "keep uninstalled" rules) */
3133   for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++)
3134     {
3135       if (r->d < 0)     /* disabled ? */
3136         continue;
3137       if (r->p >= 0)    /* install job? */
3138         continue;
3139       queue_push(&disabledq, i);
3140       solver_disablerule(solv, r);
3141       goterase++;
3142     }
3143
3144   if (goterase)
3145     {
3146       enabledisablelearntrules(solv);
3147       removedisabledconflicts(solv, &redoq);
3148     }
3149
3150   /*
3151    * find recommended packages
3152    */
3153   if (recommendationsq)
3154     {
3155       Id rec, *recp, p, pp;
3156
3157       queue_empty(recommendationsq);
3158       /* create map of all recommened packages */
3159       solv->recommends_index = -1;
3160       MAPZERO(&solv->recommendsmap);
3161
3162       /* put all packages the solver already chose in the map */
3163       if (solv->decisioncnt_weak)
3164         {
3165           for (i = solv->decisioncnt_weak; i < solv->decisioncnt_orphan; i++)
3166             {
3167               Id why;
3168               why = solv->decisionq_why.elements[i];
3169               if (why)
3170                 continue;       /* forced by unit rule */
3171               p = solv->decisionq.elements[i];
3172               if (p < 0)
3173                 continue;
3174               MAPSET(&solv->recommendsmap, p);
3175             }
3176         }
3177
3178       for (i = 0; i < solv->decisionq.count; i++)
3179         {
3180           p = solv->decisionq.elements[i];
3181           if (p < 0)
3182             continue;
3183           s = pool->solvables + p;
3184           if (s->recommends)
3185             {
3186               recp = s->repo->idarraydata + s->recommends;
3187               while ((rec = *recp++) != 0)
3188                 {
3189                   FOR_PROVIDES(p, pp, rec)
3190                     if (solv->decisionmap[p] > 0)
3191                       break;
3192                   if (p)
3193                     {
3194                       if (!noselected)
3195                         {
3196                           FOR_PROVIDES(p, pp, rec)
3197                             if (solv->decisionmap[p] > 0)
3198                               MAPSET(&solv->recommendsmap, p);
3199                         }
3200                       continue; /* p != 0: already fulfilled */
3201                     }
3202                   FOR_PROVIDES(p, pp, rec)
3203                     MAPSET(&solv->recommendsmap, p);
3204                 }
3205             }
3206         }
3207       for (i = 1; i < pool->nsolvables; i++)
3208         {
3209           if (solv->decisionmap[i] < 0)
3210             continue;
3211           if (solv->decisionmap[i] > 0 && noselected)
3212             continue;
3213           if (MAPTST(&obsmap, i))
3214             continue;
3215           s = pool->solvables + i;
3216           if (!MAPTST(&solv->recommendsmap, i))
3217             {
3218               if (!s->supplements)
3219                 continue;
3220               if (!pool_installable(pool, s))
3221                 continue;
3222               if (!solver_is_supplementing(solv, s))
3223                 continue;
3224             }
3225           queue_push(recommendationsq, i);
3226         }
3227       /* we use MODE_SUGGEST here so that repo prio is ignored */
3228       policy_filter_unwanted(solv, recommendationsq, POLICY_MODE_SUGGEST);
3229     }
3230
3231   /*
3232    * find suggested packages
3233    */
3234
3235   if (suggestionsq)
3236     {
3237       Id sug, *sugp, p, pp;
3238
3239       queue_empty(suggestionsq);
3240       /* create map of all suggests that are still open */
3241       solv->recommends_index = -1;
3242       MAPZERO(&solv->suggestsmap);
3243       for (i = 0; i < solv->decisionq.count; i++)
3244         {
3245           p = solv->decisionq.elements[i];
3246           if (p < 0)
3247             continue;
3248           s = pool->solvables + p;
3249           if (s->suggests)
3250             {
3251               sugp = s->repo->idarraydata + s->suggests;
3252               while ((sug = *sugp++) != 0)
3253                 {
3254                   FOR_PROVIDES(p, pp, sug)
3255                     if (solv->decisionmap[p] > 0)
3256                       break;
3257                   if (p)
3258                     {
3259                       if (!noselected)
3260                         {
3261                           FOR_PROVIDES(p, pp, sug)
3262                             if (solv->decisionmap[p] > 0)
3263                               MAPSET(&solv->suggestsmap, p);
3264                         }
3265                       continue; /* already fulfilled */
3266                     }
3267                   FOR_PROVIDES(p, pp, sug)
3268                     MAPSET(&solv->suggestsmap, p);
3269                 }
3270             }
3271         }
3272       for (i = 1; i < pool->nsolvables; i++)
3273         {
3274           if (solv->decisionmap[i] < 0)
3275             continue;
3276           if (solv->decisionmap[i] > 0 && noselected)
3277             continue;
3278           if (MAPTST(&obsmap, i))
3279             continue;
3280           s = pool->solvables + i;
3281           if (!MAPTST(&solv->suggestsmap, i))
3282             {
3283               if (!s->enhances)
3284                 continue;
3285               if (!pool_installable(pool, s))
3286                 continue;
3287               if (!solver_is_enhancing(solv, s))
3288                 continue;
3289             }
3290           queue_push(suggestionsq, i);
3291         }
3292       policy_filter_unwanted(solv, suggestionsq, POLICY_MODE_SUGGEST);
3293     }
3294
3295   /* undo removedisabledconflicts */
3296   if (redoq.count)
3297     undo_removedisabledconflicts(solv, &redoq);
3298   queue_free(&redoq);
3299
3300   /* undo job rule disabling */
3301   for (i = 0; i < disabledq.count; i++)
3302     solver_enablerule(solv, solv->rules + disabledq.elements[i]);
3303   queue_free(&disabledq);
3304   map_free(&obsmap);
3305 }
3306
3307
3308 /***********************************************************************/
3309 /* disk usage computations */
3310
3311 /*-------------------------------------------------------------------
3312  *
3313  * calculate DU changes
3314  */
3315
3316 void
3317 solver_calc_duchanges(Solver *solv, DUChanges *mps, int nmps)
3318 {
3319   Map installedmap;
3320
3321   solver_create_state_maps(solv, &installedmap, 0);
3322   pool_calc_duchanges(solv->pool, &installedmap, mps, nmps);
3323   map_free(&installedmap);
3324 }
3325
3326
3327 /*-------------------------------------------------------------------
3328  *
3329  * calculate changes in install size
3330  */
3331
3332 int
3333 solver_calc_installsizechange(Solver *solv)
3334 {
3335   Map installedmap;
3336   int change;
3337
3338   solver_create_state_maps(solv, &installedmap, 0);
3339   change = pool_calc_installsizechange(solv->pool, &installedmap);
3340   map_free(&installedmap);
3341   return change;
3342 }
3343
3344 void
3345 solver_create_state_maps(Solver *solv, Map *installedmap, Map *conflictsmap)
3346 {
3347   pool_create_state_maps(solv->pool, &solv->decisionq, installedmap, conflictsmap);
3348 }
3349
3350 void
3351 solver_trivial_installable(Solver *solv, Queue *pkgs, Queue *res)
3352 {
3353   Map installedmap;
3354   pool_create_state_maps(solv->pool,  &solv->decisionq, &installedmap, 0);
3355   pool_trivial_installable_noobsoletesmap(solv->pool, &installedmap, pkgs, res, solv->noobsoletes.size ? &solv->noobsoletes : 0);
3356   map_free(&installedmap);
3357 }
3358
3359 /*-------------------------------------------------------------------
3360  *
3361  * decision introspection
3362  */
3363
3364 int
3365 solver_get_decisionlevel(Solver *solv, Id p)
3366 {
3367   return solv->decisionmap[p];
3368 }
3369
3370 void
3371 solver_get_decisionqueue(Solver *solv, Queue *decisionq)
3372 {
3373   queue_free(decisionq);
3374   queue_init_clone(decisionq, &solv->decisionq);
3375 }
3376
3377 int
3378 solver_get_lastdecisionblocklevel(Solver *solv)
3379 {
3380   Id p;
3381   if (solv->decisionq.count == 0)
3382     return 0;
3383   p = solv->decisionq.elements[solv->decisionq.count - 1];
3384   if (p < 0)
3385     p = -p;
3386   return solv->decisionmap[p] < 0 ? -solv->decisionmap[p] : solv->decisionmap[p];
3387 }
3388
3389 void
3390 solver_get_decisionblock(Solver *solv, int level, Queue *decisionq)
3391 {
3392   Id p;
3393   int i;
3394
3395   queue_empty(decisionq);
3396   for (i = 0; i < solv->decisionq.count; i++)
3397     {
3398       p = solv->decisionq.elements[i];
3399       if (p < 0)
3400         p = -p;
3401       if (solv->decisionmap[p] == level || solv->decisionmap[p] == -level)
3402         break;
3403     }
3404   if (i == solv->decisionq.count)
3405     return;
3406   for (i = 0; i < solv->decisionq.count; i++)
3407     {
3408       p = solv->decisionq.elements[i];
3409       if (p < 0)
3410         p = -p;
3411       if (solv->decisionmap[p] == level || solv->decisionmap[p] == -level)
3412         queue_push(decisionq, p);
3413       else
3414         break;
3415     }
3416 }
3417
3418 int
3419 solver_describe_decision(Solver *solv, Id p, Id *infop)
3420 {
3421   int i;
3422   Id pp, why;
3423
3424   if (infop)
3425     *infop = 0;
3426   if (!solv->decisionmap[p])
3427     return SOLVER_REASON_UNRELATED;
3428   pp = solv->decisionmap[p] < 0 ? -p : p;
3429   for (i = 0; i < solv->decisionq.count; i++)
3430     if (solv->decisionq.elements[i] == pp)
3431       break;
3432   if (i == solv->decisionq.count)       /* just in case... */
3433     return SOLVER_REASON_UNRELATED;
3434   why = solv->decisionq_why.elements[i];
3435   if (why > 0)
3436     {
3437       if (infop)
3438         *infop = why;
3439       return SOLVER_REASON_UNIT_RULE;
3440     }
3441   why = -why;
3442   if (i < solv->decisioncnt_update)
3443     {
3444       if (i == 0)
3445         {
3446           if (infop)
3447             *infop = SYSTEMSOLVABLE;
3448           return SOLVER_REASON_KEEP_INSTALLED;
3449         }
3450       if (infop)
3451         *infop = why;
3452       return SOLVER_REASON_RESOLVE_JOB;
3453     }
3454   if (i < solv->decisioncnt_keep)
3455     {
3456       if (why == 0 && pp < 0)
3457         return SOLVER_REASON_CLEANDEPS_ERASE;
3458       if (infop)
3459         {
3460           if (why >= solv->updaterules && why < solv->updaterules_end)
3461             *infop = why - solv->updaterules;
3462           else if (why >= solv->featurerules && why < solv->featurerules_end)
3463             *infop = why - solv->featurerules;
3464         }
3465       return SOLVER_REASON_UPDATE_INSTALLED;
3466     }
3467   if (i < solv->decisioncnt_resolve)
3468     {
3469       if (why == 0 && pp < 0)
3470         return SOLVER_REASON_CLEANDEPS_ERASE;
3471       if (infop)
3472         {
3473           if (why >= solv->updaterules && why < solv->updaterules_end)
3474             *infop = why - solv->updaterules;
3475           else if (why >= solv->featurerules && why < solv->featurerules_end)
3476             *infop = why - solv->featurerules;
3477         }
3478       return SOLVER_REASON_KEEP_INSTALLED;
3479     }
3480   if (i < solv->decisioncnt_weak)
3481     {
3482       if (infop)
3483         *infop = why;
3484       return SOLVER_REASON_RESOLVE;
3485     }
3486   if (solv->decisionq.count < solv->decisioncnt_orphan)
3487     return SOLVER_REASON_WEAKDEP;
3488   return SOLVER_REASON_RESOLVE_ORPHAN;
3489 }
3490
3491
3492 void
3493 solver_describe_weakdep_decision(Solver *solv, Id p, Queue *whyq)
3494 {
3495   Pool *pool = solv->pool;
3496   int i;
3497   int level = solv->decisionmap[p];
3498   int decisionno;
3499   Solvable *s;
3500
3501   queue_empty(whyq);
3502   if (level < 0)
3503     return;     /* huh? */
3504   for (decisionno = 0; decisionno < solv->decisionq.count; decisionno++)
3505     if (solv->decisionq.elements[decisionno] == p)
3506       break;
3507   if (decisionno == solv->decisionq.count)
3508     return;     /* huh? */
3509   if (decisionno < solv->decisioncnt_weak || decisionno >= solv->decisioncnt_orphan)
3510     return;     /* huh? */
3511
3512   /* 1) list all packages that recommend us */
3513   for (i = 1; i < pool->nsolvables; i++)
3514     {
3515       Id *recp, rec, pp2, p2;
3516       if (solv->decisionmap[i] < 0 || solv->decisionmap[i] >= level)
3517         continue;
3518       s = pool->solvables + i;
3519       if (!s->recommends)
3520         continue;
3521       if (!solv->addalreadyrecommended && s->repo == solv->installed)
3522         continue;
3523       recp = s->repo->idarraydata + s->recommends;
3524       while ((rec = *recp++) != 0)
3525         {
3526           int found = 0;
3527           FOR_PROVIDES(p2, pp2, rec)
3528             {
3529               if (p2 == p)
3530                 found = 1;
3531               else
3532                 {
3533                   /* if p2 is already installed, this recommends is ignored */
3534                   if (solv->decisionmap[p2] > 0 && solv->decisionmap[p2] < level)
3535                     break;
3536                 }
3537             }
3538           if (!p2 && found)
3539             {
3540               queue_push(whyq, SOLVER_REASON_RECOMMENDED);
3541               queue_push2(whyq, p2, rec);
3542             }
3543         }
3544     }
3545   /* 2) list all supplements */
3546   s = pool->solvables + p;
3547   if (s->supplements && level > 0)
3548     {
3549       Id *supp, sup, pp2, p2;
3550       /* this is a hack. to use solver_dep_fulfilled we temporarily clear
3551        * everything above our level in the decisionmap */
3552       for (i = decisionno; i < solv->decisionq.count; i++ )
3553         {
3554           p2 = solv->decisionq.elements[i];
3555           if (p2 > 0)
3556             solv->decisionmap[p2] = -solv->decisionmap[p2];
3557         }
3558       supp = s->repo->idarraydata + s->supplements;
3559       while ((sup = *supp++) != 0)
3560         if (solver_dep_fulfilled(solv, sup))
3561           {
3562             int found = 0;
3563             /* let's see if this is an easy supp */
3564             FOR_PROVIDES(p2, pp2, sup)
3565               {
3566                 if (!solv->addalreadyrecommended && solv->installed)
3567                   {
3568                     if (pool->solvables[p2].repo == solv->installed)
3569                       continue;
3570                   }
3571                 if (solv->decisionmap[p2] > 0 && solv->decisionmap[p2] < level)
3572                   {
3573                     queue_push(whyq, SOLVER_REASON_SUPPLEMENTED);
3574                     queue_push2(whyq, p2, sup);
3575                     found = 1;
3576                   }
3577               }
3578             if (!found)
3579               {
3580                 /* hard case, just note dependency with no package */
3581                 queue_push(whyq, SOLVER_REASON_SUPPLEMENTED);
3582                 queue_push2(whyq, 0, sup);
3583               }
3584           }
3585       for (i = decisionno; i < solv->decisionq.count; i++)
3586         {
3587           p2 = solv->decisionq.elements[i];
3588           if (p2 > 0)
3589             solv->decisionmap[p2] = -solv->decisionmap[p2];
3590         }
3591     }
3592 }