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   default:
1477     break;
1478   }
1479   return -1;
1480 }
1481
1482 int
1483 solver_set_flag(Solver *solv, int flag, int value)
1484 {
1485   int old = solver_get_flag(solv, flag);
1486   switch (flag)
1487   {
1488   case SOLVER_FLAG_ALLOW_DOWNGRADE:
1489     solv->allowdowngrade = value;
1490     break;
1491   case SOLVER_FLAG_ALLOW_NAMECHANGE:
1492     solv->allownamechange = value;
1493     break;
1494   case SOLVER_FLAG_ALLOW_ARCHCHANGE:
1495     solv->allowarchchange = value;
1496     break;
1497   case SOLVER_FLAG_ALLOW_VENDORCHANGE:
1498     solv->allowvendorchange = value;
1499     break;
1500   case SOLVER_FLAG_ALLOW_UNINSTALL:
1501     solv->allowuninstall = value;
1502     break;
1503   case SOLVER_FLAG_NO_UPDATEPROVIDE:
1504     solv->noupdateprovide = value;
1505     break;
1506   case SOLVER_FLAG_SPLITPROVIDES:
1507     solv->dosplitprovides = value;
1508     break;
1509   case SOLVER_FLAG_IGNORE_RECOMMENDED:
1510     solv->dontinstallrecommended = value;
1511     break;
1512   case SOLVER_FLAG_ADD_ALREADY_RECOMMENDED:
1513     solv->addalreadyrecommended = value;
1514     break;
1515   case SOLVER_FLAG_NO_INFARCHCHECK:
1516     solv->noinfarchcheck = value;
1517     break;
1518   default:
1519     break;
1520   }
1521   return old;
1522 }
1523
1524 int
1525 cleandeps_check_mistakes(Solver *solv, int level)
1526 {
1527   Pool *pool = solv->pool;
1528   Rule *r;
1529   Id p, *dp;
1530   int i;
1531   int mademistake = 0;
1532
1533   if (!solv->cleandepsmap.size)
1534     return 0;
1535   /* check for mistakes */
1536   for (i = solv->installed->start; i < solv->installed->end; i++)
1537     {
1538       if (!MAPTST(&solv->cleandepsmap, i - solv->installed->start))
1539         continue;
1540       r = solv->rules + solv->featurerules + (i - solv->installed->start);
1541       /* a mistake is when the featurerule is true but the updaterule is false */
1542       if (r->p)
1543         {
1544           FOR_RULELITERALS(p, dp, r)
1545             if (p > 0 && solv->decisionmap[p] > 0)
1546               break;
1547           if (p)
1548             {
1549               r = solv->rules + solv->updaterules + (i - solv->installed->start);
1550               if (!r->p)
1551                 continue;
1552               FOR_RULELITERALS(p, dp, r)
1553                 if (p > 0 && solv->decisionmap[p] > 0)
1554                   break;
1555               if (!p)
1556                 {
1557                   POOL_DEBUG(SOLV_DEBUG_SOLVER, "cleandeps mistake: ");
1558                   solver_printruleclass(solv, SOLV_DEBUG_SOLVER, r);
1559                   POOL_DEBUG(SOLV_DEBUG_SOLVER, "feature rule: ");
1560                   solver_printruleclass(solv, SOLV_DEBUG_SOLVER, solv->rules + solv->featurerules + (i - solv->installed->start));
1561                   if (!solv->cleandeps_mistakes)
1562                     {
1563                       solv->cleandeps_mistakes = solv_calloc(1, sizeof(Queue));
1564                       queue_init(solv->cleandeps_mistakes);
1565                     }
1566                   queue_push(solv->cleandeps_mistakes, i);
1567                   MAPCLR(&solv->cleandepsmap, i - solv->installed->start);
1568                   solver_reenablepolicyrules_cleandeps(solv, i);
1569                   mademistake = 1;
1570                 }
1571             }
1572         }
1573     }
1574   if (mademistake)
1575     solver_reset(solv);
1576   return mademistake;
1577 }
1578
1579 /*-------------------------------------------------------------------
1580  *
1581  * solver_run_sat
1582  *
1583  * all rules have been set up, now actually run the solver
1584  *
1585  */
1586
1587 void
1588 solver_run_sat(Solver *solv, int disablerules, int doweak)
1589 {
1590   Queue dq;             /* local decisionqueue */
1591   Queue dqs;            /* local decisionqueue for supplements */
1592   int systemlevel;
1593   int level, olevel;
1594   Rule *r;
1595   int i, j, n;
1596   Solvable *s;
1597   Pool *pool = solv->pool;
1598   Id p, *dp;
1599   int minimizationsteps;
1600   int installedpos = solv->installed ? solv->installed->start : 0;
1601
1602   IF_POOLDEBUG (SOLV_DEBUG_RULE_CREATION)
1603     {
1604       POOL_DEBUG (SOLV_DEBUG_RULE_CREATION, "number of rules: %d\n", solv->nrules);
1605       for (i = 1; i < solv->nrules; i++)
1606         solver_printruleclass(solv, SOLV_DEBUG_RULE_CREATION, solv->rules + i);
1607     }
1608
1609   POOL_DEBUG(SOLV_DEBUG_SOLVER, "initial decisions: %d\n", solv->decisionq.count);
1610
1611   /* start SAT algorithm */
1612   level = 1;
1613   systemlevel = level + 1;
1614   POOL_DEBUG(SOLV_DEBUG_SOLVER, "solving...\n");
1615
1616   queue_init(&dq);
1617   queue_init(&dqs);
1618
1619   /*
1620    * here's the main loop:
1621    * 1) propagate new decisions (only needed once)
1622    * 2) fulfill jobs
1623    * 3) try to keep installed packages
1624    * 4) fulfill all unresolved rules
1625    * 5) install recommended packages
1626    * 6) minimalize solution if we had choices
1627    * if we encounter a problem, we rewind to a safe level and restart
1628    * with step 1
1629    */
1630
1631   minimizationsteps = 0;
1632   for (;;)
1633     {
1634       /*
1635        * initial propagation of the assertions
1636        */
1637       if (level == 1)
1638         {
1639           POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "propagating (propagate_index: %d;  size decisionq: %d)...\n", solv->propagate_index, solv->decisionq.count);
1640           if ((r = propagate(solv, level)) != 0)
1641             {
1642               if (analyze_unsolvable(solv, r, disablerules))
1643                 continue;
1644               level = 0;
1645               break;    /* unsolvable */
1646             }
1647         }
1648
1649       /*
1650        * resolve jobs first
1651        */
1652      if (level < systemlevel)
1653         {
1654           POOL_DEBUG(SOLV_DEBUG_SOLVER, "resolving job rules\n");
1655           for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++)
1656             {
1657               Id l;
1658               if (r->d < 0)             /* ignore disabled rules */
1659                 continue;
1660               queue_empty(&dq);
1661               FOR_RULELITERALS(l, dp, r)
1662                 {
1663                   if (l < 0)
1664                     {
1665                       if (solv->decisionmap[-l] <= 0)
1666                         break;
1667                     }
1668                   else
1669                     {
1670                       if (solv->decisionmap[l] > 0)
1671                         break;
1672                       if (solv->decisionmap[l] == 0)
1673                         queue_push(&dq, l);
1674                     }
1675                 }
1676               if (l || !dq.count)
1677                 continue;
1678               /* prune to installed if not updating */
1679               if (dq.count > 1 && solv->installed && !solv->updatemap_all)
1680                 {
1681                   int j, k;
1682                   for (j = k = 0; j < dq.count; j++)
1683                     {
1684                       Solvable *s = pool->solvables + dq.elements[j];
1685                       if (s->repo == solv->installed)
1686                         {
1687                           dq.elements[k++] = dq.elements[j];
1688                           if (solv->updatemap.size && MAPTST(&solv->updatemap, dq.elements[j] - solv->installed->start))
1689                             {
1690                               k = 0;    /* package wants to be updated, do not prune */
1691                               break;
1692                             }
1693                         }
1694                     }
1695                   if (k)
1696                     dq.count = k;
1697                 }
1698               olevel = level;
1699               level = selectandinstall(solv, level, &dq, disablerules, i);
1700               if (level == 0)
1701                 break;
1702               if (level <= olevel)
1703                 break;
1704             }
1705           if (level == 0)
1706             break;      /* unsolvable */
1707           systemlevel = level + 1;
1708           if (i < solv->jobrules_end)
1709             continue;
1710           solv->decisioncnt_update = solv->decisionq.count;
1711           solv->decisioncnt_keep = solv->decisionq.count;
1712         }
1713
1714       /*
1715        * installed packages
1716        */
1717       if (level < systemlevel && solv->installed && solv->installed->nsolvables && !solv->installed->disabled)
1718         {
1719           Repo *installed = solv->installed;
1720           int pass;
1721
1722           POOL_DEBUG(SOLV_DEBUG_SOLVER, "resolving installed packages\n");
1723           /* we use two passes if we need to update packages
1724            * to create a better user experience */
1725           for (pass = solv->updatemap.size ? 0 : 1; pass < 2; pass++)
1726             {
1727               int passlevel = level;
1728               if (pass == 1)
1729                 solv->decisioncnt_keep = solv->decisionq.count;
1730               /* start with installedpos, the position that gave us problems last time */
1731               for (i = installedpos, n = installed->start; n < installed->end; i++, n++)
1732                 {
1733                   Rule *rr;
1734                   Id d;
1735
1736                   if (i == installed->end)
1737                     i = installed->start;
1738                   s = pool->solvables + i;
1739                   if (s->repo != installed)
1740                     continue;
1741
1742                   if (solv->decisionmap[i] > 0)
1743                     continue;
1744                   if (!pass && solv->updatemap.size && !MAPTST(&solv->updatemap, i - installed->start))
1745                     continue;           /* updates first */
1746                   r = solv->rules + solv->updaterules + (i - installed->start);
1747                   rr = r;
1748                   if (!rr->p || rr->d < 0)      /* disabled -> look at feature rule */
1749                     rr -= solv->installed->end - solv->installed->start;
1750                   if (!rr->p)           /* identical to update rule? */
1751                     rr = r;
1752                   if (!rr->p)
1753                     continue;           /* orpaned package */
1754
1755                   /* XXX: noupdate check is probably no longer needed, as all jobs should
1756                    * already be satisfied */
1757                   /* Actually we currently still need it because of erase jobs */
1758                   /* if noupdate is set we do not look at update candidates */
1759                   queue_empty(&dq);
1760                   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))
1761                     {
1762                       if (solv->noobsoletes.size && solv->multiversionupdaters
1763                              && (d = solv->multiversionupdaters[i - installed->start]) != 0)
1764                         {
1765                           /* special multiversion handling, make sure best version is chosen */
1766                           queue_push(&dq, i);
1767                           while ((p = pool->whatprovidesdata[d++]) != 0)
1768                             if (solv->decisionmap[p] >= 0)
1769                               queue_push(&dq, p);
1770                           policy_filter_unwanted(solv, &dq, POLICY_MODE_CHOOSE);
1771                           p = dq.elements[0];
1772                           if (p != i && solv->decisionmap[p] == 0)
1773                             {
1774                               rr = solv->rules + solv->featurerules + (i - solv->installed->start);
1775                               if (!rr->p)               /* update rule == feature rule? */
1776                                 rr = rr - solv->featurerules + solv->updaterules;
1777                               dq.count = 1;
1778                             }
1779                           else
1780                             dq.count = 0;
1781                         }
1782                       else
1783                         {
1784                           /* update to best package */
1785                           FOR_RULELITERALS(p, dp, rr)
1786                             {
1787                               if (solv->decisionmap[p] > 0)
1788                                 {
1789                                   dq.count = 0;         /* already fulfilled */
1790                                   break;
1791                                 }
1792                               if (!solv->decisionmap[p])
1793                                 queue_push(&dq, p);
1794                             }
1795                         }
1796                     }
1797                   /* install best version */
1798                   if (dq.count)
1799                     {
1800                       olevel = level;
1801                       level = selectandinstall(solv, level, &dq, disablerules, rr - solv->rules);
1802                       if (level == 0)
1803                         {
1804                           queue_free(&dq);
1805                           queue_free(&dqs);
1806                           return;
1807                         }
1808                       if (level <= olevel)
1809                         {
1810                           if (level == 1 || level < passlevel)
1811                             break;      /* trouble */
1812                           if (level < olevel)
1813                             n = installed->start;       /* redo all */
1814                           i--;
1815                           n--;
1816                           continue;
1817                         }
1818                     }
1819                   /* if still undecided keep package */
1820                   if (solv->decisionmap[i] == 0)
1821                     {
1822                       olevel = level;
1823                       if (solv->cleandepsmap.size && MAPTST(&solv->cleandepsmap, i - installed->start))
1824                         {
1825                           POOL_DEBUG(SOLV_DEBUG_POLICY, "cleandeps erasing %s\n", pool_solvid2str(pool, i));
1826                           level = setpropagatelearn(solv, level, -i, disablerules, 0);
1827                         }
1828                       else
1829                         {
1830                           POOL_DEBUG(SOLV_DEBUG_POLICY, "keeping %s\n", pool_solvid2str(pool, i));
1831                           level = setpropagatelearn(solv, level, i, disablerules, r - solv->rules);
1832                         }
1833                       if (level == 0)
1834                         break;
1835                       if (level <= olevel)
1836                         {
1837                           if (level == 1 || level < passlevel)
1838                             break;      /* trouble */
1839                           if (level < olevel)
1840                             n = installed->start;       /* redo all */
1841                           i--;
1842                           n--;
1843                           continue;     /* retry with learnt rule */
1844                         }
1845                     }
1846                 }
1847               if (n < installed->end)
1848                 {
1849                   installedpos = i;     /* retry problem solvable next time */
1850                   break;                /* ran into trouble */
1851                 }
1852               installedpos = installed->start;  /* reset installedpos */
1853             }
1854           if (level == 0)
1855             break;              /* unsolvable */
1856           systemlevel = level + 1;
1857           if (pass < 2)
1858             continue;           /* had trouble, retry */
1859         }
1860
1861       if (level < systemlevel)
1862         systemlevel = level;
1863
1864       /*
1865        * decide
1866        */
1867       solv->decisioncnt_resolve = solv->decisionq.count;
1868       POOL_DEBUG(SOLV_DEBUG_POLICY, "deciding unresolved rules\n");
1869       for (i = 1, n = 1; n < solv->nrules; i++, n++)
1870         {
1871           if (i == solv->nrules)
1872             i = 1;
1873           r = solv->rules + i;
1874           if (r->d < 0)         /* ignore disabled rules */
1875             continue;
1876           queue_empty(&dq);
1877           if (r->d == 0)
1878             {
1879               /* binary or unary rule */
1880               /* need two positive undecided literals */
1881               if (r->p < 0 || r->w2 <= 0)
1882                 continue;
1883               if (solv->decisionmap[r->p] || solv->decisionmap[r->w2])
1884                 continue;
1885               queue_push(&dq, r->p);
1886               queue_push(&dq, r->w2);
1887             }
1888           else
1889             {
1890               /* make sure that
1891                * all negative literals are installed
1892                * no positive literal is installed
1893                * i.e. the rule is not fulfilled and we
1894                * just need to decide on the positive literals
1895                */
1896               if (r->p < 0)
1897                 {
1898                   if (solv->decisionmap[-r->p] <= 0)
1899                     continue;
1900                 }
1901               else
1902                 {
1903                   if (solv->decisionmap[r->p] > 0)
1904                     continue;
1905                   if (solv->decisionmap[r->p] == 0)
1906                     queue_push(&dq, r->p);
1907                 }
1908               dp = pool->whatprovidesdata + r->d;
1909               while ((p = *dp++) != 0)
1910                 {
1911                   if (p < 0)
1912                     {
1913                       if (solv->decisionmap[-p] <= 0)
1914                         break;
1915                     }
1916                   else
1917                     {
1918                       if (solv->decisionmap[p] > 0)
1919                         break;
1920                       if (solv->decisionmap[p] == 0)
1921                         queue_push(&dq, p);
1922                     }
1923                 }
1924               if (p)
1925                 continue;
1926             }
1927           IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
1928             {
1929               POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "unfulfilled ");
1930               solver_printruleclass(solv, SOLV_DEBUG_PROPAGATE, r);
1931             }
1932           /* dq.count < 2 cannot happen as this means that
1933            * the rule is unit */
1934           assert(dq.count > 1);
1935
1936           olevel = level;
1937           level = selectandinstall(solv, level, &dq, disablerules, r - solv->rules);
1938           if (level == 0)
1939             break;              /* unsolvable */
1940           if (level < systemlevel || level == 1)
1941             break;              /* trouble */
1942           /* something changed, so look at all rules again */
1943           n = 0;
1944         }
1945
1946       if (n != solv->nrules)    /* ran into trouble? */
1947         {
1948           if (level == 0)
1949             break;              /* unsolvable */
1950           continue;             /* start over */
1951         }
1952
1953       /* at this point we have a consistent system. now do the extras... */
1954
1955       solv->decisioncnt_weak = solv->decisionq.count;
1956       if (doweak)
1957         {
1958           int qcount;
1959
1960           POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended packages\n");
1961           queue_empty(&dq);     /* recommended packages */
1962           queue_empty(&dqs);    /* supplemented packages */
1963           for (i = 1; i < pool->nsolvables; i++)
1964             {
1965               if (solv->decisionmap[i] < 0)
1966                 continue;
1967               if (solv->decisionmap[i] > 0)
1968                 {
1969                   /* installed, check for recommends */
1970                   Id *recp, rec, pp, p;
1971                   s = pool->solvables + i;
1972                   if (!solv->addalreadyrecommended && s->repo == solv->installed)
1973                     continue;
1974                   /* XXX need to special case AND ? */
1975                   if (s->recommends)
1976                     {
1977                       recp = s->repo->idarraydata + s->recommends;
1978                       while ((rec = *recp++) != 0)
1979                         {
1980                           qcount = dq.count;
1981                           FOR_PROVIDES(p, pp, rec)
1982                             {
1983                               if (solv->decisionmap[p] > 0)
1984                                 {
1985                                   dq.count = qcount;
1986                                   break;
1987                                 }
1988                               else if (solv->decisionmap[p] == 0)
1989                                 {
1990                                   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))))
1991                                     continue;
1992                                   queue_pushunique(&dq, p);
1993                                 }
1994                             }
1995                         }
1996                     }
1997                 }
1998               else
1999                 {
2000                   s = pool->solvables + i;
2001                   if (!s->supplements)
2002                     continue;
2003                   if (!pool_installable(pool, s))
2004                     continue;
2005                   if (!solver_is_supplementing(solv, s))
2006                     continue;
2007                   if (solv->dupmap_all && solv->installed && s->repo == solv->installed && (solv->droporphanedmap_all || (solv->droporphanedmap.size && MAPTST(&solv->droporphanedmap, i - solv->installed->start))))
2008                     continue;
2009                   queue_push(&dqs, i);
2010                 }
2011             }
2012
2013           /* filter out all packages obsoleted by installed packages */
2014           /* this is no longer needed if we have reverse obsoletes */
2015           if ((dqs.count || dq.count) && solv->installed)
2016             {
2017               Map obsmap;
2018               Id obs, *obsp, po, ppo;
2019
2020               map_init(&obsmap, pool->nsolvables);
2021               for (p = solv->installed->start; p < solv->installed->end; p++)
2022                 {
2023                   s = pool->solvables + p;
2024                   if (s->repo != solv->installed || !s->obsoletes)
2025                     continue;
2026                   if (solv->decisionmap[p] <= 0)
2027                     continue;
2028                   if (solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p))
2029                     continue;
2030                   obsp = s->repo->idarraydata + s->obsoletes;
2031                   /* foreach obsoletes */
2032                   while ((obs = *obsp++) != 0)
2033                     FOR_PROVIDES(po, ppo, obs)
2034                       MAPSET(&obsmap, po);
2035                 }
2036               for (i = j = 0; i < dqs.count; i++)
2037                 if (!MAPTST(&obsmap, dqs.elements[i]))
2038                   dqs.elements[j++] = dqs.elements[i];
2039               dqs.count = j;
2040               for (i = j = 0; i < dq.count; i++)
2041                 if (!MAPTST(&obsmap, dq.elements[i]))
2042                   dq.elements[j++] = dq.elements[i];
2043               dq.count = j;
2044               map_free(&obsmap);
2045             }
2046
2047           /* filter out all already supplemented packages if requested */
2048           if (!solv->addalreadyrecommended && dqs.count)
2049             {
2050               /* turn off all new packages */
2051               for (i = 0; i < solv->decisionq.count; i++)
2052                 {
2053                   p = solv->decisionq.elements[i];
2054                   if (p < 0)
2055                     continue;
2056                   s = pool->solvables + p;
2057                   if (s->repo && s->repo != solv->installed)
2058                     solv->decisionmap[p] = -solv->decisionmap[p];
2059                 }
2060               /* filter out old supplements */
2061               for (i = j = 0; i < dqs.count; i++)
2062                 {
2063                   p = dqs.elements[i];
2064                   s = pool->solvables + p;
2065                   if (!s->supplements)
2066                     continue;
2067                   if (!solver_is_supplementing(solv, s))
2068                     dqs.elements[j++] = p;
2069                 }
2070               dqs.count = j;
2071               /* undo turning off */
2072               for (i = 0; i < solv->decisionq.count; i++)
2073                 {
2074                   p = solv->decisionq.elements[i];
2075                   if (p < 0)
2076                     continue;
2077                   s = pool->solvables + p;
2078                   if (s->repo && s->repo != solv->installed)
2079                     solv->decisionmap[p] = -solv->decisionmap[p];
2080                 }
2081             }
2082
2083           /* multiversion doesn't mix well with supplements.
2084            * filter supplemented packages where we already decided
2085            * to install a different version (see bnc#501088) */
2086           if (dqs.count && solv->noobsoletes.size)
2087             {
2088               for (i = j = 0; i < dqs.count; i++)
2089                 {
2090                   p = dqs.elements[i];
2091                   if (MAPTST(&solv->noobsoletes, p))
2092                     {
2093                       Id p2, pp2;
2094                       s = pool->solvables + p;
2095                       FOR_PROVIDES(p2, pp2, s->name)
2096                         if (solv->decisionmap[p2] > 0 && pool->solvables[p2].name == s->name)
2097                           break;
2098                       if (p2)
2099                         continue;       /* ignore this package */
2100                     }
2101                   dqs.elements[j++] = p;
2102                 }
2103               dqs.count = j;
2104             }
2105
2106           /* make dq contain both recommended and supplemented pkgs */
2107           if (dqs.count)
2108             {
2109               for (i = 0; i < dqs.count; i++)
2110                 queue_pushunique(&dq, dqs.elements[i]);
2111             }
2112
2113           if (dq.count)
2114             {
2115               Map dqmap;
2116               int decisioncount = solv->decisionq.count;
2117
2118               if (dq.count == 1)
2119                 {
2120                   /* simple case, just one package. no need to choose to best version */
2121                   p = dq.elements[0];
2122                   if (dqs.count)
2123                     POOL_DEBUG(SOLV_DEBUG_POLICY, "installing supplemented %s\n", pool_solvid2str(pool, p));
2124                   else
2125                     POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended %s\n", pool_solvid2str(pool, p));
2126                   level = setpropagatelearn(solv, level, p, 0, 0);
2127                   if (level == 0)
2128                     break;
2129                   continue;     /* back to main loop */
2130                 }
2131
2132               /* filter packages, this gives us the best versions */
2133               policy_filter_unwanted(solv, &dq, POLICY_MODE_RECOMMEND);
2134
2135               /* create map of result */
2136               map_init(&dqmap, pool->nsolvables);
2137               for (i = 0; i < dq.count; i++)
2138                 MAPSET(&dqmap, dq.elements[i]);
2139
2140               /* install all supplemented packages */
2141               for (i = 0; i < dqs.count; i++)
2142                 {
2143                   p = dqs.elements[i];
2144                   if (solv->decisionmap[p] || !MAPTST(&dqmap, p))
2145                     continue;
2146                   POOL_DEBUG(SOLV_DEBUG_POLICY, "installing supplemented %s\n", pool_solvid2str(pool, p));
2147                   olevel = level;
2148                   level = setpropagatelearn(solv, level, p, 0, 0);
2149                   if (level <= olevel)
2150                     break;
2151                 }
2152               if (i < dqs.count || solv->decisionq.count < decisioncount)
2153                 {
2154                   map_free(&dqmap);
2155                   if (level == 0)
2156                     break;
2157                   continue;
2158                 }
2159
2160               /* install all recommended packages */
2161               /* more work as we want to created branches if multiple
2162                * choices are valid */
2163               for (i = 0; i < decisioncount; i++)
2164                 {
2165                   Id rec, *recp, pp;
2166                   p = solv->decisionq.elements[i];
2167                   if (p < 0)
2168                     continue;
2169                   s = pool->solvables + p;
2170                   if (!s->repo || (!solv->addalreadyrecommended && s->repo == solv->installed))
2171                     continue;
2172                   if (!s->recommends)
2173                     continue;
2174                   recp = s->repo->idarraydata + s->recommends;
2175                   while ((rec = *recp++) != 0)
2176                     {
2177                       queue_empty(&dq);
2178                       FOR_PROVIDES(p, pp, rec)
2179                         {
2180                           if (solv->decisionmap[p] > 0)
2181                             {
2182                               dq.count = 0;
2183                               break;
2184                             }
2185                           else if (solv->decisionmap[p] == 0 && MAPTST(&dqmap, p))
2186                             queue_pushunique(&dq, p);
2187                         }
2188                       if (!dq.count)
2189                         continue;
2190                       if (dq.count > 1)
2191                         {
2192                           /* multiple candidates, open a branch */
2193                           for (i = 1; i < dq.count; i++)
2194                             queue_push(&solv->branches, dq.elements[i]);
2195                           queue_push(&solv->branches, -level);
2196                         }
2197                       p = dq.elements[0];
2198                       POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended %s\n", pool_solvid2str(pool, p));
2199                       olevel = level;
2200                       level = setpropagatelearn(solv, level, p, 0, 0);
2201                       if (level <= olevel || solv->decisionq.count < decisioncount)
2202                         break;  /* we had to revert some decisions */
2203                     }
2204                   if (rec)
2205                     break;      /* had a problem above, quit loop */
2206                 }
2207               map_free(&dqmap);
2208               if (level == 0)
2209                 break;
2210               continue;         /* back to main loop so that all deps are checked */
2211             }
2212         }
2213
2214       solv->decisioncnt_orphan = solv->decisionq.count;
2215       if (solv->dupmap_all && solv->installed)
2216         {
2217           int installedone = 0;
2218
2219           /* let's see if we can install some unsupported package */
2220           POOL_DEBUG(SOLV_DEBUG_SOLVER, "deciding orphaned packages\n");
2221           for (i = 0; i < solv->orphaned.count; i++)
2222             {
2223               p = solv->orphaned.elements[i];
2224               if (solv->decisionmap[p])
2225                 continue;       /* already decided */
2226               if (solv->droporphanedmap_all)
2227                 continue;
2228               if (solv->droporphanedmap.size && MAPTST(&solv->droporphanedmap, p - solv->installed->start))
2229                 continue;
2230               POOL_DEBUG(SOLV_DEBUG_SOLVER, "keeping orphaned %s\n", pool_solvid2str(pool, p));
2231               olevel = level;
2232               level = setpropagatelearn(solv, level, p, 0, 0);
2233               installedone = 1;
2234               if (level < olevel)
2235                 break;
2236             }
2237           if (installedone || i < solv->orphaned.count)
2238             {
2239               if (level == 0)
2240                 break;
2241               continue;         /* back to main loop */
2242             }
2243           for (i = 0; i < solv->orphaned.count; i++)
2244             {
2245               p = solv->orphaned.elements[i];
2246               if (solv->decisionmap[p])
2247                 continue;       /* already decided */
2248               POOL_DEBUG(SOLV_DEBUG_SOLVER, "removing orphaned %s\n", pool_solvid2str(pool, p));
2249               olevel = level;
2250               level = setpropagatelearn(solv, level, -p, 0, 0);
2251               if (level < olevel)
2252                 break;
2253             }
2254           if (i < solv->orphaned.count)
2255             {
2256               if (level == 0)
2257                 break;
2258               continue;         /* back to main loop */
2259             }
2260         }
2261
2262      if (solv->installed && solv->cleandepsmap.size)
2263         {
2264           if (cleandeps_check_mistakes(solv, level))
2265             {
2266               level = 1;        /* restart from scratch */
2267               continue;
2268             }
2269         }
2270
2271      if (solv->solution_callback)
2272         {
2273           solv->solution_callback(solv, solv->solution_callback_data);
2274           if (solv->branches.count)
2275             {
2276               int i = solv->branches.count - 1;
2277               int l = -solv->branches.elements[i];
2278               Id why;
2279
2280               for (; i > 0; i--)
2281                 if (solv->branches.elements[i - 1] < 0)
2282                   break;
2283               p = solv->branches.elements[i];
2284               POOL_DEBUG(SOLV_DEBUG_SOLVER, "branching with %s\n", pool_solvid2str(pool, p));
2285               queue_empty(&dq);
2286               for (j = i + 1; j < solv->branches.count; j++)
2287                 queue_push(&dq, solv->branches.elements[j]);
2288               solv->branches.count = i;
2289               level = l;
2290               revert(solv, level);
2291               if (dq.count > 1)
2292                 for (j = 0; j < dq.count; j++)
2293                   queue_push(&solv->branches, dq.elements[j]);
2294               olevel = level;
2295               why = -solv->decisionq_why.elements[solv->decisionq_why.count];
2296               assert(why >= 0);
2297               level = setpropagatelearn(solv, level, p, disablerules, why);
2298               if (level == 0)
2299                 break;
2300               continue;
2301             }
2302           /* all branches done, we're finally finished */
2303           break;
2304         }
2305
2306       /* auto-minimization step */
2307      if (solv->branches.count)
2308         {
2309           int l = 0, lasti = -1, lastl = -1;
2310           Id why;
2311
2312           p = 0;
2313           for (i = solv->branches.count - 1; i >= 0; i--)
2314             {
2315               p = solv->branches.elements[i];
2316               if (p < 0)
2317                 l = -p;
2318               else if (p > 0 && solv->decisionmap[p] > l + 1)
2319                 {
2320                   lasti = i;
2321                   lastl = l;
2322                 }
2323             }
2324           if (lasti >= 0)
2325             {
2326               /* kill old solvable so that we do not loop */
2327               p = solv->branches.elements[lasti];
2328               solv->branches.elements[lasti] = 0;
2329               POOL_DEBUG(SOLV_DEBUG_SOLVER, "minimizing %d -> %d with %s\n", solv->decisionmap[p], lastl, pool_solvid2str(pool, p));
2330               minimizationsteps++;
2331
2332               level = lastl;
2333               revert(solv, level);
2334               why = -solv->decisionq_why.elements[solv->decisionq_why.count];
2335               assert(why >= 0);
2336               olevel = level;
2337               level = setpropagatelearn(solv, level, p, disablerules, why);
2338               if (level == 0)
2339                 break;
2340               continue;         /* back to main loop */
2341             }
2342         }
2343       /* no minimization found, we're finally finished! */
2344       break;
2345     }
2346
2347   POOL_DEBUG(SOLV_DEBUG_STATS, "solver statistics: %d learned rules, %d unsolvable, %d minimization steps\n", solv->stats_learned, solv->stats_unsolvable, minimizationsteps);
2348
2349   POOL_DEBUG(SOLV_DEBUG_STATS, "done solving.\n\n");
2350   queue_free(&dq);
2351   queue_free(&dqs);
2352   if (level == 0)
2353     {
2354       /* unsolvable */
2355       solv->decisioncnt_update = solv->decisionq.count;
2356       solv->decisioncnt_keep = solv->decisionq.count;
2357       solv->decisioncnt_resolve = solv->decisionq.count;
2358       solv->decisioncnt_weak = solv->decisionq.count;
2359       solv->decisioncnt_orphan = solv->decisionq.count;
2360     }
2361 #if 0
2362   solver_printdecisionq(solv, SOLV_DEBUG_RESULT);
2363 #endif
2364 }
2365
2366
2367 /*-------------------------------------------------------------------
2368  *
2369  * remove disabled conflicts
2370  *
2371  * purpose: update the decisionmap after some rules were disabled.
2372  * this is used to calculate the suggested/recommended package list.
2373  * Also returns a "removed" list to undo the discisionmap changes.
2374  */
2375
2376 static void
2377 removedisabledconflicts(Solver *solv, Queue *removed)
2378 {
2379   Pool *pool = solv->pool;
2380   int i, n;
2381   Id p, why, *dp;
2382   Id new;
2383   Rule *r;
2384   Id *decisionmap = solv->decisionmap;
2385
2386   queue_empty(removed);
2387   for (i = 0; i < solv->decisionq.count; i++)
2388     {
2389       p = solv->decisionq.elements[i];
2390       if (p > 0)
2391         continue;       /* conflicts only, please */
2392       why = solv->decisionq_why.elements[i];
2393       if (why == 0)
2394         {
2395           /* no rule involved, must be a orphan package drop */
2396           continue;
2397         }
2398       /* we never do conflicts on free decisions, so there
2399        * must have been an unit rule */
2400       assert(why > 0);
2401       r = solv->rules + why;
2402       if (r->d < 0 && decisionmap[-p])
2403         {
2404           /* rule is now disabled, remove from decisionmap */
2405           POOL_DEBUG(SOLV_DEBUG_SOLVER, "removing conflict for package %s[%d]\n", pool_solvid2str(pool, -p), -p);
2406           queue_push(removed, -p);
2407           queue_push(removed, decisionmap[-p]);
2408           decisionmap[-p] = 0;
2409         }
2410     }
2411   if (!removed->count)
2412     return;
2413   /* we removed some confliced packages. some of them might still
2414    * be in conflict, so search for unit rules and re-conflict */
2415   new = 0;
2416   for (i = n = 1, r = solv->rules + i; n < solv->nrules; i++, r++, n++)
2417     {
2418       if (i == solv->nrules)
2419         {
2420           i = 1;
2421           r = solv->rules + i;
2422         }
2423       if (r->d < 0)
2424         continue;
2425       if (!r->w2)
2426         {
2427           if (r->p < 0 && !decisionmap[-r->p])
2428             new = r->p;
2429         }
2430       else if (!r->d)
2431         {
2432           /* binary rule */
2433           if (r->p < 0 && decisionmap[-r->p] == 0 && DECISIONMAP_FALSE(r->w2))
2434             new = r->p;
2435           else if (r->w2 < 0 && decisionmap[-r->w2] == 0 && DECISIONMAP_FALSE(r->p))
2436             new = r->w2;
2437         }
2438       else
2439         {
2440           if (r->p < 0 && decisionmap[-r->p] == 0)
2441             new = r->p;
2442           if (new || DECISIONMAP_FALSE(r->p))
2443             {
2444               dp = pool->whatprovidesdata + r->d;
2445               while ((p = *dp++) != 0)
2446                 {
2447                   if (new && p == new)
2448                     continue;
2449                   if (p < 0 && decisionmap[-p] == 0)
2450                     {
2451                       if (new)
2452                         {
2453                           new = 0;
2454                           break;
2455                         }
2456                       new = p;
2457                     }
2458                   else if (!DECISIONMAP_FALSE(p))
2459                     {
2460                       new = 0;
2461                       break;
2462                     }
2463                 }
2464             }
2465         }
2466       if (new)
2467         {
2468           POOL_DEBUG(SOLV_DEBUG_SOLVER, "re-conflicting package %s[%d]\n", pool_solvid2str(pool, -new), -new);
2469           decisionmap[-new] = -1;
2470           new = 0;
2471           n = 0;        /* redo all rules */
2472         }
2473     }
2474 }
2475
2476 static inline void
2477 undo_removedisabledconflicts(Solver *solv, Queue *removed)
2478 {
2479   int i;
2480   for (i = 0; i < removed->count; i += 2)
2481     solv->decisionmap[removed->elements[i]] = removed->elements[i + 1];
2482 }
2483
2484
2485 /*-------------------------------------------------------------------
2486  *
2487  * weaken solvable dependencies
2488  */
2489
2490 static void
2491 weaken_solvable_deps(Solver *solv, Id p)
2492 {
2493   int i;
2494   Rule *r;
2495
2496   for (i = 1, r = solv->rules + i; i < solv->rpmrules_end; i++, r++)
2497     {
2498       if (r->p != -p)
2499         continue;
2500       if ((r->d == 0 || r->d == -1) && r->w2 < 0)
2501         continue;       /* conflict */
2502       queue_push(&solv->weakruleq, i);
2503     }
2504 }
2505
2506
2507 /********************************************************************/
2508 /* main() */
2509
2510
2511 void
2512 solver_calculate_noobsmap(Pool *pool, Queue *job, Map *noobsmap)
2513 {
2514   int i;
2515   Id how, what, select;
2516   Id p, pp;
2517   for (i = 0; i < job->count; i += 2)
2518     {
2519       how = job->elements[i];
2520       if ((how & SOLVER_JOBMASK) != SOLVER_NOOBSOLETES)
2521         continue;
2522       what = job->elements[i + 1];
2523       select = how & SOLVER_SELECTMASK;
2524       if (!noobsmap->size)
2525         map_grow(noobsmap, pool->nsolvables);
2526       FOR_JOB_SELECT(p, pp, select, what)
2527         MAPSET(noobsmap, p);
2528     }
2529 }
2530
2531 /*
2532  * add a rule created by a job, record job number and weak flag
2533  */
2534 static inline void
2535 solver_addjobrule(Solver *solv, Id p, Id d, Id job, int weak)
2536 {
2537   solver_addrule(solv, p, d);
2538   queue_push(&solv->ruletojob, job);
2539   if (weak)
2540     queue_push(&solv->weakruleq, solv->nrules - 1);
2541 }
2542
2543 /*
2544  *
2545  * solve job queue
2546  *
2547  */
2548
2549 int
2550 solver_solve(Solver *solv, Queue *job)
2551 {
2552   Pool *pool = solv->pool;
2553   Repo *installed = solv->installed;
2554   int i;
2555   int oldnrules;
2556   Map addedmap;                /* '1' == have rpm-rules for solvable */
2557   Map installcandidatemap;
2558   Id how, what, select, name, weak, p, pp, d;
2559   Queue q;
2560   Solvable *s;
2561   Rule *r;
2562   int now, solve_start;
2563   int hasdupjob = 0;
2564
2565   solve_start = solv_timems(0);
2566
2567   /* log solver options */
2568   POOL_DEBUG(SOLV_DEBUG_STATS, "solver started\n");
2569   POOL_DEBUG(SOLV_DEBUG_STATS, "dosplitprovides=%d, noupdateprovide=%d, noinfarchcheck=%d\n", solv->dosplitprovides, solv->noupdateprovide, solv->noinfarchcheck);
2570   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);
2571   POOL_DEBUG(SOLV_DEBUG_STATS, "promoteepoch=%d, forbidselfconflicts=%d\n", pool->promoteepoch, pool->forbidselfconflicts);
2572   POOL_DEBUG(SOLV_DEBUG_STATS, "obsoleteusesprovides=%d, implicitobsoleteusesprovides=%d, obsoleteusescolors=%d\n", pool->obsoleteusesprovides, pool->implicitobsoleteusesprovides, pool->obsoleteusescolors);
2573   POOL_DEBUG(SOLV_DEBUG_STATS, "dontinstallrecommended=%d, addalreadyrecommended=%d\n", solv->dontinstallrecommended, solv->addalreadyrecommended);
2574
2575   /* create whatprovides if not already there */
2576   if (!pool->whatprovides)
2577     pool_createwhatprovides(pool);
2578
2579   /* create obsolete index */
2580   policy_create_obsolete_index(solv);
2581
2582   /* remember job */
2583   queue_free(&solv->job);
2584   queue_init_clone(&solv->job, job);
2585
2586   /*
2587    * create basic rule set of all involved packages
2588    * use addedmap bitmap to make sure we don't create rules twice
2589    */
2590
2591   /* create noobsolete map if needed */
2592   solver_calculate_noobsmap(pool, job, &solv->noobsoletes);
2593
2594   map_init(&addedmap, pool->nsolvables);
2595   MAPSET(&addedmap, SYSTEMSOLVABLE);
2596
2597   map_init(&installcandidatemap, pool->nsolvables);
2598   queue_init(&q);
2599
2600   now = solv_timems(0);
2601   /*
2602    * create rules for all package that could be involved with the solving
2603    * so called: rpm rules
2604    *
2605    */
2606   if (installed)
2607     {
2608       /* check for update/verify jobs as they need to be known early */
2609       for (i = 0; i < job->count; i += 2)
2610         {
2611           how = job->elements[i];
2612           what = job->elements[i + 1];
2613           select = how & SOLVER_SELECTMASK;
2614           switch (how & SOLVER_JOBMASK)
2615             {
2616             case SOLVER_VERIFY:
2617               if (select == SOLVER_SOLVABLE_ALL)
2618                 solv->fixmap_all = 1;
2619               FOR_JOB_SELECT(p, pp, select, what)
2620                 {
2621                   s = pool->solvables + p;
2622                   if (!solv->installed || s->repo != solv->installed)
2623                     continue;
2624                   if (!solv->fixmap.size)
2625                     map_grow(&solv->fixmap, solv->installed->end - solv->installed->start);
2626                   MAPSET(&solv->fixmap, p - solv->installed->start);
2627                 }
2628               break;
2629             case SOLVER_UPDATE:
2630               if (select == SOLVER_SOLVABLE_ALL)
2631                 solv->updatemap_all = 1;
2632               FOR_JOB_SELECT(p, pp, select, what)
2633                 {
2634                   s = pool->solvables + p;
2635                   if (!solv->installed || s->repo != solv->installed)
2636                     continue;
2637                   if (!solv->updatemap.size)
2638                     map_grow(&solv->updatemap, solv->installed->end - solv->installed->start);
2639                   MAPSET(&solv->updatemap, p - solv->installed->start);
2640                 }
2641               break;
2642             default:
2643               break;
2644             }
2645         }
2646
2647       oldnrules = solv->nrules;
2648       FOR_REPO_SOLVABLES(installed, p, s)
2649         solver_addrpmrulesforsolvable(solv, s, &addedmap);
2650       POOL_DEBUG(SOLV_DEBUG_STATS, "added %d rpm rules for installed solvables\n", solv->nrules - oldnrules);
2651       oldnrules = solv->nrules;
2652       FOR_REPO_SOLVABLES(installed, p, s)
2653         solver_addrpmrulesforupdaters(solv, s, &addedmap, 1);
2654       POOL_DEBUG(SOLV_DEBUG_STATS, "added %d rpm rules for updaters of installed solvables\n", solv->nrules - oldnrules);
2655     }
2656
2657   /*
2658    * create rules for all packages involved in the job
2659    * (to be installed or removed)
2660    */
2661
2662   oldnrules = solv->nrules;
2663   for (i = 0; i < job->count; i += 2)
2664     {
2665       how = job->elements[i];
2666       what = job->elements[i + 1];
2667       select = how & SOLVER_SELECTMASK;
2668
2669       switch (how & SOLVER_JOBMASK)
2670         {
2671         case SOLVER_INSTALL:
2672           FOR_JOB_SELECT(p, pp, select, what)
2673             {
2674               MAPSET(&installcandidatemap, p);
2675               solver_addrpmrulesforsolvable(solv, pool->solvables + p, &addedmap);
2676             }
2677           break;
2678         case SOLVER_DISTUPGRADE:
2679           if (select == SOLVER_SOLVABLE_ALL)
2680             {
2681               solv->dupmap_all = 1;
2682               solv->updatemap_all = 1;
2683             }
2684           if (!solv->dupmap_all)
2685             hasdupjob = 1;
2686           break;
2687         default:
2688           break;
2689         }
2690     }
2691   POOL_DEBUG(SOLV_DEBUG_STATS, "added %d rpm rules for packages involved in a job\n", solv->nrules - oldnrules);
2692
2693
2694   /*
2695    * add rules for suggests, enhances
2696    */
2697   oldnrules = solv->nrules;
2698   solver_addrpmrulesforweak(solv, &addedmap);
2699   POOL_DEBUG(SOLV_DEBUG_STATS, "added %d rpm rules because of weak dependencies\n", solv->nrules - oldnrules);
2700
2701   /*
2702    * first pass done, we now have all the rpm rules we need.
2703    * unify existing rules before going over all job rules and
2704    * policy rules.
2705    * at this point the system is always solvable,
2706    * as an empty system (remove all packages) is a valid solution
2707    */
2708
2709   IF_POOLDEBUG (SOLV_DEBUG_STATS)
2710     {
2711       int possible = 0, installable = 0;
2712       for (i = 1; i < pool->nsolvables; i++)
2713         {
2714           if (pool_installable(pool, pool->solvables + i))
2715             installable++;
2716           if (MAPTST(&addedmap, i))
2717             possible++;
2718         }
2719       POOL_DEBUG(SOLV_DEBUG_STATS, "%d of %d installable solvables considered for solving\n", possible, installable);
2720     }
2721
2722   solver_unifyrules(solv);                          /* remove duplicate rpm rules */
2723   solv->rpmrules_end = solv->nrules;              /* mark end of rpm rules */
2724
2725   POOL_DEBUG(SOLV_DEBUG_STATS, "rpm rule memory used: %d K\n", solv->nrules * (int)sizeof(Rule) / 1024);
2726   POOL_DEBUG(SOLV_DEBUG_STATS, "rpm rule creation took %d ms\n", solv_timems(now));
2727
2728   /* create dup maps if needed. We need the maps early to create our
2729    * update rules */
2730   if (hasdupjob)
2731     solver_createdupmaps(solv);
2732
2733   /*
2734    * create feature rules
2735    *
2736    * foreach installed:
2737    *   create assertion (keep installed, if no update available)
2738    *   or
2739    *   create update rule (A|update1(A)|update2(A)|...)
2740    *
2741    * those are used later on to keep a version of the installed packages in
2742    * best effort mode
2743    */
2744
2745   solv->featurerules = solv->nrules;              /* mark start of feature rules */
2746   if (installed)
2747     {
2748       /* foreach possibly installed solvable */
2749       for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
2750         {
2751           if (s->repo != installed)
2752             {
2753               solver_addrule(solv, 0, 0);       /* create dummy rule */
2754               continue;
2755             }
2756           solver_addupdaterule(solv, s, 1);    /* allow s to be updated */
2757         }
2758       /* make sure we accounted for all rules */
2759       assert(solv->nrules - solv->featurerules == installed->end - installed->start);
2760     }
2761   solv->featurerules_end = solv->nrules;
2762
2763     /*
2764      * Add update rules for installed solvables
2765      *
2766      * almost identical to feature rules
2767      * except that downgrades/archchanges/vendorchanges are not allowed
2768      */
2769
2770   solv->updaterules = solv->nrules;
2771
2772   if (installed)
2773     { /* foreach installed solvables */
2774       /* we create all update rules, but disable some later on depending on the job */
2775       for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
2776         {
2777           Rule *sr;
2778
2779           if (s->repo != installed)
2780             {
2781               solver_addrule(solv, 0, 0);       /* create dummy rule */
2782               continue;
2783             }
2784           solver_addupdaterule(solv, s, 0);     /* allowall = 0: downgrades not allowed */
2785           /*
2786            * check for and remove duplicate
2787            */
2788           r = solv->rules + solv->nrules - 1;           /* r: update rule */
2789           sr = r - (installed->end - installed->start); /* sr: feature rule */
2790           /* it's orphaned if there is no feature rule or the feature rule
2791            * consists just of the installed package */
2792           if (!sr->p || (sr->p == i && !sr->d && !sr->w2))
2793             queue_push(&solv->orphaned, i);
2794           if (!r->p)
2795             {
2796               assert(solv->dupmap_all && !sr->p);
2797               continue;
2798             }
2799           if (!solver_samerule(solv, r, sr))
2800             memset(sr, 0, sizeof(*sr));         /* delete unneeded feature rule */
2801           else
2802             solver_disablerule(solv, sr);       /* disable feature rule */
2803         }
2804       /* consistency check: we added a rule for _every_ installed solvable */
2805       assert(solv->nrules - solv->updaterules == installed->end - installed->start);
2806     }
2807   solv->updaterules_end = solv->nrules;
2808
2809
2810   /*
2811    * now add all job rules
2812    */
2813
2814   solv->jobrules = solv->nrules;
2815   if (solv->cleandeps_updatepkgs)
2816     {
2817       queue_free(solv->cleandeps_updatepkgs);
2818       solv->cleandeps_updatepkgs = solv_free(solv->cleandeps_updatepkgs);
2819     }
2820   for (i = 0; i < job->count; i += 2)
2821     {
2822       oldnrules = solv->nrules;
2823
2824       how = job->elements[i];
2825       what = job->elements[i + 1];
2826       weak = how & SOLVER_WEAK;
2827       select = how & SOLVER_SELECTMASK;
2828       switch (how & SOLVER_JOBMASK)
2829         {
2830         case SOLVER_INSTALL:
2831           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sinstall %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
2832           if ((how & SOLVER_CLEANDEPS) != 0 && !solv->cleandepsmap.size && installed)
2833             map_grow(&solv->cleandepsmap, installed->end - installed->start);
2834           if (select == SOLVER_SOLVABLE)
2835             {
2836               p = what;
2837               d = 0;
2838             }
2839           else
2840             {
2841               queue_empty(&q);
2842               FOR_JOB_SELECT(p, pp, select, what)
2843                 queue_push(&q, p);
2844               if (!q.count)
2845                 {
2846                   /* no candidate found, make this an impossible rule */
2847                   queue_push(&q, -SYSTEMSOLVABLE);
2848                 }
2849               p = queue_shift(&q);      /* get first candidate */
2850               d = !q.count ? 0 : pool_queuetowhatprovides(pool, &q);    /* internalize */
2851             }
2852           solver_addjobrule(solv, p, d, i, weak);
2853           break;
2854         case SOLVER_ERASE:
2855           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %s%serase %s\n", weak ? "weak " : "", how & SOLVER_CLEANDEPS ? "clean deps " : "", solver_select2str(pool, select, what));
2856           if ((how & SOLVER_CLEANDEPS) != 0 && !solv->cleandepsmap.size && installed)
2857             map_grow(&solv->cleandepsmap, installed->end - installed->start);
2858           name = (select == SOLVER_SOLVABLE || (select == SOLVER_SOLVABLE_NAME && ISRELDEP(what))) ? 0 : -1;
2859           FOR_JOB_SELECT(p, pp, select, what)
2860             {
2861               s = pool->solvables + p;
2862               if (installed && s->repo == installed)
2863                 name = !name ? s->name : -1;
2864               solver_addjobrule(solv, -p, 0, i, weak);
2865             }
2866           /* special case for "erase a specific solvable": we also
2867            * erase all other solvables with that name, so that they
2868            * don't get picked up as replacement.
2869            * name is > 0 if exactly one installed solvable matched.
2870            */
2871           /* XXX: look also at packages that obsolete this package? */
2872           if (name > 0)
2873             {
2874               int j, k;
2875               k = solv->nrules;
2876               FOR_PROVIDES(p, pp, name)
2877                 {
2878                   s = pool->solvables + p;
2879                   if (s->name != name)
2880                     continue;
2881                   /* keep other versions installed */
2882                   if (s->repo == installed)
2883                     continue;
2884                   /* keep installcandidates of other jobs */
2885                   if (MAPTST(&installcandidatemap, p))
2886                     continue;
2887                   /* don't add the same rule twice */
2888                   for (j = oldnrules; j < k; j++)
2889                     if (solv->rules[j].p == -p)
2890                       break;
2891                   if (j == k)
2892                     solver_addjobrule(solv, -p, 0, i, weak);    /* remove by id */
2893                 }
2894             }
2895           break;
2896
2897         case SOLVER_UPDATE:
2898           if ((how & SOLVER_CLEANDEPS) != 0 && installed)
2899             {
2900               FOR_JOB_SELECT(p, pp, select, what)
2901                 {
2902                   s = pool->solvables + p;
2903                   if (s->repo != installed)
2904                     continue;
2905                   if (!solv->cleandeps_updatepkgs)
2906                     {
2907                       solv->cleandeps_updatepkgs = solv_calloc(1, sizeof(Queue));
2908                       queue_init(solv->cleandeps_updatepkgs);
2909                     }
2910                   queue_pushunique(solv->cleandeps_updatepkgs, p);
2911                   if (!solv->cleandepsmap.size)
2912                     map_grow(&solv->cleandepsmap, installed->end - installed->start);
2913                 }
2914             }
2915           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %supdate %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
2916           break;
2917         case SOLVER_VERIFY:
2918           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sverify %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
2919           break;
2920         case SOLVER_WEAKENDEPS:
2921           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sweaken deps %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
2922           if (select != SOLVER_SOLVABLE)
2923             break;
2924           s = pool->solvables + what;
2925           weaken_solvable_deps(solv, what);
2926           break;
2927         case SOLVER_NOOBSOLETES:
2928           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sno obsolete %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
2929           break;
2930         case SOLVER_LOCK:
2931           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %slock %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
2932           FOR_JOB_SELECT(p, pp, select, what)
2933             {
2934               s = pool->solvables + p;
2935               solver_addjobrule(solv, installed && s->repo == installed ? p : -p, 0, i, weak);
2936             }
2937           break;
2938         case SOLVER_DISTUPGRADE:
2939           POOL_DEBUG(SOLV_DEBUG_JOB, "job: distupgrade %s\n", solver_select2str(pool, select, what));
2940           break;
2941         case SOLVER_DROP_ORPHANED:
2942           POOL_DEBUG(SOLV_DEBUG_JOB, "job: drop orphaned %s\n", solver_select2str(pool, select, what));
2943           if (select == SOLVER_SOLVABLE_ALL)
2944             solv->droporphanedmap_all = 1;
2945           FOR_JOB_SELECT(p, pp, select, what)
2946             {
2947               s = pool->solvables + p;
2948               if (!installed || s->repo != installed)
2949                 continue;
2950               if (!solv->droporphanedmap.size)
2951                 map_grow(&solv->droporphanedmap, installed->end - installed->start);
2952               MAPSET(&solv->droporphanedmap, p - installed->start);
2953             }
2954           break;
2955         case SOLVER_USERINSTALLED:
2956           POOL_DEBUG(SOLV_DEBUG_JOB, "job: user installed %s\n", solver_select2str(pool, select, what));
2957           break;
2958         default:
2959           POOL_DEBUG(SOLV_DEBUG_JOB, "job: unknown job\n");
2960           break;
2961         }
2962
2963         /*
2964          * debug
2965          */
2966
2967       IF_POOLDEBUG (SOLV_DEBUG_JOB)
2968         {
2969           int j;
2970           if (solv->nrules == oldnrules)
2971             POOL_DEBUG(SOLV_DEBUG_JOB, " - no rule created\n");
2972           for (j = oldnrules; j < solv->nrules; j++)
2973             {
2974               POOL_DEBUG(SOLV_DEBUG_JOB, " - job ");
2975               solver_printrule(solv, SOLV_DEBUG_JOB, solv->rules + j);
2976             }
2977         }
2978     }
2979   assert(solv->ruletojob.count == solv->nrules - solv->jobrules);
2980   solv->jobrules_end = solv->nrules;
2981
2982   /* now create infarch and dup rules */
2983   if (!solv->noinfarchcheck)
2984     {
2985       solver_addinfarchrules(solv, &addedmap);
2986       if (pool->obsoleteusescolors)
2987         {
2988           /* currently doesn't work well with infarch rules, so make
2989            * them weak */
2990           for (i = solv->infarchrules; i < solv->infarchrules_end; i++)
2991             queue_push(&solv->weakruleq, i);
2992         }
2993     }
2994   else
2995     solv->infarchrules = solv->infarchrules_end = solv->nrules;
2996
2997   if (hasdupjob)
2998     {
2999       solver_addduprules(solv, &addedmap);
3000       solver_freedupmaps(solv); /* no longer needed */
3001     }
3002   else
3003     solv->duprules = solv->duprules_end = solv->nrules;
3004
3005   if (1)
3006     solver_addchoicerules(solv);
3007   else
3008     solv->choicerules = solv->choicerules_end = solv->nrules;
3009
3010   /* all rules created
3011    * --------------------------------------------------------------
3012    * prepare for solving
3013    */
3014
3015   /* free unneeded memory */
3016   map_free(&addedmap);
3017   map_free(&installcandidatemap);
3018   queue_free(&q);
3019
3020   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);
3021   POOL_DEBUG(SOLV_DEBUG_STATS, "overall rule memory used: %d K\n", solv->nrules * (int)sizeof(Rule) / 1024);
3022
3023   /* create weak map */
3024   map_init(&solv->weakrulemap, solv->nrules);
3025   for (i = 0; i < solv->weakruleq.count; i++)
3026     {
3027       p = solv->weakruleq.elements[i];
3028       MAPSET(&solv->weakrulemap, p);
3029     }
3030
3031   /* all new rules are learnt after this point */
3032   solv->learntrules = solv->nrules;
3033
3034   /* create watches chains */
3035   makewatches(solv);
3036
3037   /* create assertion index. it is only used to speed up
3038    * makeruledecsions() a bit */
3039   for (i = 1, r = solv->rules + i; i < solv->nrules; i++, r++)
3040     if (r->p && !r->w2 && (r->d == 0 || r->d == -1))
3041       queue_push(&solv->ruleassertions, i);
3042
3043   /* disable update rules that conflict with our job */
3044   solver_disablepolicyrules(solv);
3045
3046   /* make initial decisions based on assertion rules */
3047   makeruledecisions(solv);
3048   POOL_DEBUG(SOLV_DEBUG_SOLVER, "problems so far: %d\n", solv->problems.count);
3049
3050   /* no mistakes */
3051   if (solv->cleandeps_mistakes)
3052     {
3053       queue_free(solv->cleandeps_mistakes);
3054       solv->cleandeps_mistakes = solv_free(solv->cleandeps_mistakes);
3055     }
3056
3057   /*
3058    * ********************************************
3059    * solve!
3060    * ********************************************
3061    */
3062
3063   now = solv_timems(0);
3064   solver_run_sat(solv, 1, solv->dontinstallrecommended ? 0 : 1);
3065   POOL_DEBUG(SOLV_DEBUG_STATS, "solver took %d ms\n", solv_timems(now));
3066
3067   /*
3068    * prepare solution queue if there were problems
3069    */
3070   solver_prepare_solutions(solv);
3071
3072   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);
3073   POOL_DEBUG(SOLV_DEBUG_STATS, "solver_solve took %d ms\n", solv_timems(solve_start));
3074
3075   /* return number of problems */
3076   return solv->problems.count ? solv->problems.count / 2 : 0;
3077 }
3078
3079 Transaction *
3080 solver_create_transaction(Solver *solv)
3081 {
3082   return transaction_create_decisionq(solv->pool, &solv->decisionq, &solv->noobsoletes);
3083 }
3084
3085 void solver_get_orphaned(Solver *solv, Queue *orphanedq)
3086 {
3087   queue_free(orphanedq);
3088   queue_init_clone(orphanedq, &solv->orphaned);
3089 }
3090
3091 void solver_get_recommendations(Solver *solv, Queue *recommendationsq, Queue *suggestionsq, int noselected)
3092 {
3093   Pool *pool = solv->pool;
3094   Queue redoq, disabledq;
3095   int goterase, i;
3096   Solvable *s;
3097   Rule *r;
3098   Map obsmap;
3099
3100   if (!recommendationsq && !suggestionsq)
3101     return;
3102
3103   map_init(&obsmap, pool->nsolvables);
3104   if (solv->installed)
3105     {
3106       Id obs, *obsp, p, po, ppo;
3107       for (p = solv->installed->start; p < solv->installed->end; p++)
3108         {
3109           s = pool->solvables + p;
3110           if (s->repo != solv->installed || !s->obsoletes)
3111             continue;
3112           if (solv->decisionmap[p] <= 0)
3113             continue;
3114           if (solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p))
3115             continue;
3116           obsp = s->repo->idarraydata + s->obsoletes;
3117           /* foreach obsoletes */
3118           while ((obs = *obsp++) != 0)
3119             FOR_PROVIDES(po, ppo, obs)
3120               MAPSET(&obsmap, po);
3121         }
3122     }
3123
3124   queue_init(&redoq);
3125   queue_init(&disabledq);
3126   goterase = 0;
3127   /* disable all erase jobs (including weak "keep uninstalled" rules) */
3128   for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++)
3129     {
3130       if (r->d < 0)     /* disabled ? */
3131         continue;
3132       if (r->p >= 0)    /* install job? */
3133         continue;
3134       queue_push(&disabledq, i);
3135       solver_disablerule(solv, r);
3136       goterase++;
3137     }
3138
3139   if (goterase)
3140     {
3141       enabledisablelearntrules(solv);
3142       removedisabledconflicts(solv, &redoq);
3143     }
3144
3145   /*
3146    * find recommended packages
3147    */
3148   if (recommendationsq)
3149     {
3150       Id rec, *recp, p, pp;
3151
3152       queue_empty(recommendationsq);
3153       /* create map of all recommened packages */
3154       solv->recommends_index = -1;
3155       MAPZERO(&solv->recommendsmap);
3156
3157       /* put all packages the solver already chose in the map */
3158       if (solv->decisioncnt_weak)
3159         {
3160           for (i = solv->decisioncnt_weak; i < solv->decisioncnt_orphan; i++)
3161             {
3162               Id why;
3163               why = solv->decisionq_why.elements[i];
3164               if (why)
3165                 continue;       /* forced by unit rule */
3166               p = solv->decisionq.elements[i];
3167               if (p < 0)
3168                 continue;
3169               MAPSET(&solv->recommendsmap, p);
3170             }
3171         }
3172
3173       for (i = 0; i < solv->decisionq.count; i++)
3174         {
3175           p = solv->decisionq.elements[i];
3176           if (p < 0)
3177             continue;
3178           s = pool->solvables + p;
3179           if (s->recommends)
3180             {
3181               recp = s->repo->idarraydata + s->recommends;
3182               while ((rec = *recp++) != 0)
3183                 {
3184                   FOR_PROVIDES(p, pp, rec)
3185                     if (solv->decisionmap[p] > 0)
3186                       break;
3187                   if (p)
3188                     {
3189                       if (!noselected)
3190                         {
3191                           FOR_PROVIDES(p, pp, rec)
3192                             if (solv->decisionmap[p] > 0)
3193                               MAPSET(&solv->recommendsmap, p);
3194                         }
3195                       continue; /* p != 0: already fulfilled */
3196                     }
3197                   FOR_PROVIDES(p, pp, rec)
3198                     MAPSET(&solv->recommendsmap, p);
3199                 }
3200             }
3201         }
3202       for (i = 1; i < pool->nsolvables; i++)
3203         {
3204           if (solv->decisionmap[i] < 0)
3205             continue;
3206           if (solv->decisionmap[i] > 0 && noselected)
3207             continue;
3208           if (MAPTST(&obsmap, i))
3209             continue;
3210           s = pool->solvables + i;
3211           if (!MAPTST(&solv->recommendsmap, i))
3212             {
3213               if (!s->supplements)
3214                 continue;
3215               if (!pool_installable(pool, s))
3216                 continue;
3217               if (!solver_is_supplementing(solv, s))
3218                 continue;
3219             }
3220           queue_push(recommendationsq, i);
3221         }
3222       /* we use MODE_SUGGEST here so that repo prio is ignored */
3223       policy_filter_unwanted(solv, recommendationsq, POLICY_MODE_SUGGEST);
3224     }
3225
3226   /*
3227    * find suggested packages
3228    */
3229
3230   if (suggestionsq)
3231     {
3232       Id sug, *sugp, p, pp;
3233
3234       queue_empty(suggestionsq);
3235       /* create map of all suggests that are still open */
3236       solv->recommends_index = -1;
3237       MAPZERO(&solv->suggestsmap);
3238       for (i = 0; i < solv->decisionq.count; i++)
3239         {
3240           p = solv->decisionq.elements[i];
3241           if (p < 0)
3242             continue;
3243           s = pool->solvables + p;
3244           if (s->suggests)
3245             {
3246               sugp = s->repo->idarraydata + s->suggests;
3247               while ((sug = *sugp++) != 0)
3248                 {
3249                   FOR_PROVIDES(p, pp, sug)
3250                     if (solv->decisionmap[p] > 0)
3251                       break;
3252                   if (p)
3253                     {
3254                       if (!noselected)
3255                         {
3256                           FOR_PROVIDES(p, pp, sug)
3257                             if (solv->decisionmap[p] > 0)
3258                               MAPSET(&solv->suggestsmap, p);
3259                         }
3260                       continue; /* already fulfilled */
3261                     }
3262                   FOR_PROVIDES(p, pp, sug)
3263                     MAPSET(&solv->suggestsmap, p);
3264                 }
3265             }
3266         }
3267       for (i = 1; i < pool->nsolvables; i++)
3268         {
3269           if (solv->decisionmap[i] < 0)
3270             continue;
3271           if (solv->decisionmap[i] > 0 && noselected)
3272             continue;
3273           if (MAPTST(&obsmap, i))
3274             continue;
3275           s = pool->solvables + i;
3276           if (!MAPTST(&solv->suggestsmap, i))
3277             {
3278               if (!s->enhances)
3279                 continue;
3280               if (!pool_installable(pool, s))
3281                 continue;
3282               if (!solver_is_enhancing(solv, s))
3283                 continue;
3284             }
3285           queue_push(suggestionsq, i);
3286         }
3287       policy_filter_unwanted(solv, suggestionsq, POLICY_MODE_SUGGEST);
3288     }
3289
3290   /* undo removedisabledconflicts */
3291   if (redoq.count)
3292     undo_removedisabledconflicts(solv, &redoq);
3293   queue_free(&redoq);
3294
3295   /* undo job rule disabling */
3296   for (i = 0; i < disabledq.count; i++)
3297     solver_enablerule(solv, solv->rules + disabledq.elements[i]);
3298   queue_free(&disabledq);
3299   map_free(&obsmap);
3300 }
3301
3302
3303 /***********************************************************************/
3304 /* disk usage computations */
3305
3306 /*-------------------------------------------------------------------
3307  *
3308  * calculate DU changes
3309  */
3310
3311 void
3312 solver_calc_duchanges(Solver *solv, DUChanges *mps, int nmps)
3313 {
3314   Map installedmap;
3315
3316   solver_create_state_maps(solv, &installedmap, 0);
3317   pool_calc_duchanges(solv->pool, &installedmap, mps, nmps);
3318   map_free(&installedmap);
3319 }
3320
3321
3322 /*-------------------------------------------------------------------
3323  *
3324  * calculate changes in install size
3325  */
3326
3327 int
3328 solver_calc_installsizechange(Solver *solv)
3329 {
3330   Map installedmap;
3331   int change;
3332
3333   solver_create_state_maps(solv, &installedmap, 0);
3334   change = pool_calc_installsizechange(solv->pool, &installedmap);
3335   map_free(&installedmap);
3336   return change;
3337 }
3338
3339 void
3340 solver_create_state_maps(Solver *solv, Map *installedmap, Map *conflictsmap)
3341 {
3342   pool_create_state_maps(solv->pool, &solv->decisionq, installedmap, conflictsmap);
3343 }
3344
3345 void
3346 solver_trivial_installable(Solver *solv, Queue *pkgs, Queue *res)
3347 {
3348   Map installedmap;
3349   pool_create_state_maps(solv->pool,  &solv->decisionq, &installedmap, 0);
3350   pool_trivial_installable_noobsoletesmap(solv->pool, &installedmap, pkgs, res, solv->noobsoletes.size ? &solv->noobsoletes : 0);
3351   map_free(&installedmap);
3352 }
3353
3354 /*-------------------------------------------------------------------
3355  *
3356  * decision introspection
3357  */
3358
3359 int
3360 solver_get_decisionlevel(Solver *solv, Id p)
3361 {
3362   return solv->decisionmap[p];
3363 }
3364
3365 void
3366 solver_get_decisionqueue(Solver *solv, Queue *decisionq)
3367 {
3368   queue_free(decisionq);
3369   queue_init_clone(decisionq, &solv->decisionq);
3370 }
3371
3372 int
3373 solver_get_lastdecisionblocklevel(Solver *solv)
3374 {
3375   Id p;
3376   if (solv->decisionq.count == 0)
3377     return 0;
3378   p = solv->decisionq.elements[solv->decisionq.count - 1];
3379   if (p < 0)
3380     p = -p;
3381   return solv->decisionmap[p] < 0 ? -solv->decisionmap[p] : solv->decisionmap[p];
3382 }
3383
3384 void
3385 solver_get_decisionblock(Solver *solv, int level, Queue *decisionq)
3386 {
3387   Id p;
3388   int i;
3389
3390   queue_empty(decisionq);
3391   for (i = 0; i < solv->decisionq.count; i++)
3392     {
3393       p = solv->decisionq.elements[i];
3394       if (p < 0)
3395         p = -p;
3396       if (solv->decisionmap[p] == level || solv->decisionmap[p] == -level)
3397         break;
3398     }
3399   if (i == solv->decisionq.count)
3400     return;
3401   for (i = 0; i < solv->decisionq.count; i++)
3402     {
3403       p = solv->decisionq.elements[i];
3404       if (p < 0)
3405         p = -p;
3406       if (solv->decisionmap[p] == level || solv->decisionmap[p] == -level)
3407         queue_push(decisionq, p);
3408       else
3409         break;
3410     }
3411 }
3412
3413 int
3414 solver_describe_decision(Solver *solv, Id p, Id *infop)
3415 {
3416   int i;
3417   Id pp, why;
3418
3419   if (infop)
3420     *infop = 0;
3421   if (!solv->decisionmap[p])
3422     return SOLVER_REASON_UNRELATED;
3423   pp = solv->decisionmap[p] < 0 ? -p : p;
3424   for (i = 0; i < solv->decisionq.count; i++)
3425     if (solv->decisionq.elements[i] == pp)
3426       break;
3427   if (i == solv->decisionq.count)       /* just in case... */
3428     return SOLVER_REASON_UNRELATED;
3429   why = solv->decisionq_why.elements[i];
3430   if (why > 0)
3431     {
3432       if (infop)
3433         *infop = why;
3434       return SOLVER_REASON_UNIT_RULE;
3435     }
3436   why = -why;
3437   if (i < solv->decisioncnt_update)
3438     {
3439       if (i == 0)
3440         {
3441           if (infop)
3442             *infop = SYSTEMSOLVABLE;
3443           return SOLVER_REASON_KEEP_INSTALLED;
3444         }
3445       if (infop)
3446         *infop = why;
3447       return SOLVER_REASON_RESOLVE_JOB;
3448     }
3449   if (i < solv->decisioncnt_keep)
3450     {
3451       if (why == 0 && pp < 0)
3452         return SOLVER_REASON_CLEANDEPS_ERASE;
3453       if (infop)
3454         {
3455           if (why >= solv->updaterules && why < solv->updaterules_end)
3456             *infop = why - solv->updaterules;
3457           else if (why >= solv->featurerules && why < solv->featurerules_end)
3458             *infop = why - solv->featurerules;
3459         }
3460       return SOLVER_REASON_UPDATE_INSTALLED;
3461     }
3462   if (i < solv->decisioncnt_resolve)
3463     {
3464       if (why == 0 && pp < 0)
3465         return SOLVER_REASON_CLEANDEPS_ERASE;
3466       if (infop)
3467         {
3468           if (why >= solv->updaterules && why < solv->updaterules_end)
3469             *infop = why - solv->updaterules;
3470           else if (why >= solv->featurerules && why < solv->featurerules_end)
3471             *infop = why - solv->featurerules;
3472         }
3473       return SOLVER_REASON_KEEP_INSTALLED;
3474     }
3475   if (i < solv->decisioncnt_weak)
3476     {
3477       if (infop)
3478         *infop = why;
3479       return SOLVER_REASON_RESOLVE;
3480     }
3481   if (solv->decisionq.count < solv->decisioncnt_orphan)
3482     return SOLVER_REASON_WEAKDEP;
3483   return SOLVER_REASON_RESOLVE_ORPHAN;
3484 }
3485
3486
3487 void
3488 solver_describe_weakdep_decision(Solver *solv, Id p, Queue *whyq)
3489 {
3490   Pool *pool = solv->pool;
3491   int i;
3492   int level = solv->decisionmap[p];
3493   int decisionno;
3494   Solvable *s;
3495
3496   queue_empty(whyq);
3497   if (level < 0)
3498     return;     /* huh? */
3499   for (decisionno = 0; decisionno < solv->decisionq.count; decisionno++)
3500     if (solv->decisionq.elements[decisionno] == p)
3501       break;
3502   if (decisionno == solv->decisionq.count)
3503     return;     /* huh? */
3504   if (decisionno < solv->decisioncnt_weak || decisionno >= solv->decisioncnt_orphan)
3505     return;     /* huh? */
3506
3507   /* 1) list all packages that recommend us */
3508   for (i = 1; i < pool->nsolvables; i++)
3509     {
3510       Id *recp, rec, pp2, p2;
3511       if (solv->decisionmap[i] < 0 || solv->decisionmap[i] >= level)
3512         continue;
3513       s = pool->solvables + i;
3514       if (!s->recommends)
3515         continue;
3516       if (!solv->addalreadyrecommended && s->repo == solv->installed)
3517         continue;
3518       recp = s->repo->idarraydata + s->recommends;
3519       while ((rec = *recp++) != 0)
3520         {
3521           int found = 0;
3522           FOR_PROVIDES(p2, pp2, rec)
3523             {
3524               if (p2 == p)
3525                 found = 1;
3526               else
3527                 {
3528                   /* if p2 is already installed, this recommends is ignored */
3529                   if (solv->decisionmap[p2] > 0 && solv->decisionmap[p2] < level)
3530                     break;
3531                 }
3532             }
3533           if (!p2 && found)
3534             {
3535               queue_push(whyq, SOLVER_REASON_RECOMMENDED);
3536               queue_push2(whyq, p2, rec);
3537             }
3538         }
3539     }
3540   /* 2) list all supplements */
3541   s = pool->solvables + p;
3542   if (s->supplements && level > 0)
3543     {
3544       Id *supp, sup, pp2, p2;
3545       /* this is a hack. to use solver_dep_fulfilled we temporarily clear
3546        * everything above our level in the decisionmap */
3547       for (i = decisionno; i < solv->decisionq.count; i++ )
3548         {
3549           p2 = solv->decisionq.elements[i];
3550           if (p2 > 0)
3551             solv->decisionmap[p2] = -solv->decisionmap[p2];
3552         }
3553       supp = s->repo->idarraydata + s->supplements;
3554       while ((sup = *supp++) != 0)
3555         if (solver_dep_fulfilled(solv, sup))
3556           {
3557             int found = 0;
3558             /* let's see if this is an easy supp */
3559             FOR_PROVIDES(p2, pp2, sup)
3560               {
3561                 if (!solv->addalreadyrecommended && solv->installed)
3562                   {
3563                     if (pool->solvables[p2].repo == solv->installed)
3564                       continue;
3565                   }
3566                 if (solv->decisionmap[p2] > 0 && solv->decisionmap[p2] < level)
3567                   {
3568                     queue_push(whyq, SOLVER_REASON_SUPPLEMENTED);
3569                     queue_push2(whyq, p2, sup);
3570                     found = 1;
3571                   }
3572               }
3573             if (!found)
3574               {
3575                 /* hard case, just note dependency with no package */
3576                 queue_push(whyq, SOLVER_REASON_SUPPLEMENTED);
3577                 queue_push2(whyq, 0, sup);
3578               }
3579           }
3580       for (i = decisionno; i < solv->decisionq.count; i++)
3581         {
3582           p2 = solv->decisionq.elements[i];
3583           if (p2 > 0)
3584             solv->decisionmap[p2] = -solv->decisionmap[p2];
3585         }
3586     }
3587 }