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