src/solver.c

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