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       FOR_JOB_SELECT(p, pp, select, what)
2533         MAPSET(noobsmap, p);
2534     }
2535 }
2536
2537 /*
2538  * add a rule created by a job, record job number and weak flag
2539  */
2540 static inline void
2541 solver_addjobrule(Solver *solv, Id p, Id d, Id job, int weak)
2542 {
2543   solver_addrule(solv, p, d);
2544   queue_push(&solv->ruletojob, job);
2545   if (weak)
2546     queue_push(&solv->weakruleq, solv->nrules - 1);
2547 }
2548
2549 /*
2550  *
2551  * solve job queue
2552  *
2553  */
2554
2555 int
2556 solver_solve(Solver *solv, Queue *job)
2557 {
2558   Pool *pool = solv->pool;
2559   Repo *installed = solv->installed;
2560   int i;
2561   int oldnrules;
2562   Map addedmap;                /* '1' == have rpm-rules for solvable */
2563   Map installcandidatemap;
2564   Id how, what, select, name, weak, p, pp, d;
2565   Queue q;
2566   Solvable *s;
2567   Rule *r;
2568   int now, solve_start;
2569   int hasdupjob = 0;
2570
2571   solve_start = solv_timems(0);
2572
2573   /* log solver options */
2574   POOL_DEBUG(SOLV_DEBUG_STATS, "solver started\n");
2575   POOL_DEBUG(SOLV_DEBUG_STATS, "dosplitprovides=%d, noupdateprovide=%d, noinfarchcheck=%d\n", solv->dosplitprovides, solv->noupdateprovide, solv->noinfarchcheck);
2576   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);
2577   POOL_DEBUG(SOLV_DEBUG_STATS, "promoteepoch=%d, forbidselfconflicts=%d\n", pool->promoteepoch, pool->forbidselfconflicts);
2578   POOL_DEBUG(SOLV_DEBUG_STATS, "obsoleteusesprovides=%d, implicitobsoleteusesprovides=%d, obsoleteusescolors=%d\n", pool->obsoleteusesprovides, pool->implicitobsoleteusesprovides, pool->obsoleteusescolors);
2579   POOL_DEBUG(SOLV_DEBUG_STATS, "dontinstallrecommended=%d, addalreadyrecommended=%d\n", solv->dontinstallrecommended, solv->addalreadyrecommended);
2580
2581   /* create whatprovides if not already there */
2582   if (!pool->whatprovides)
2583     pool_createwhatprovides(pool);
2584
2585   /* create obsolete index */
2586   policy_create_obsolete_index(solv);
2587
2588   /* remember job */
2589   queue_free(&solv->job);
2590   queue_init_clone(&solv->job, job);
2591
2592   /*
2593    * create basic rule set of all involved packages
2594    * use addedmap bitmap to make sure we don't create rules twice
2595    */
2596
2597   /* create noobsolete map if needed */
2598   solver_calculate_noobsmap(pool, job, &solv->noobsoletes);
2599
2600   map_init(&addedmap, pool->nsolvables);
2601   MAPSET(&addedmap, SYSTEMSOLVABLE);
2602
2603   map_init(&installcandidatemap, pool->nsolvables);
2604   queue_init(&q);
2605
2606   now = solv_timems(0);
2607   /*
2608    * create rules for all package that could be involved with the solving
2609    * so called: rpm rules
2610    *
2611    */
2612   if (installed)
2613     {
2614       /* check for update/verify jobs as they need to be known early */
2615       for (i = 0; i < job->count; i += 2)
2616         {
2617           how = job->elements[i];
2618           what = job->elements[i + 1];
2619           select = how & SOLVER_SELECTMASK;
2620           switch (how & SOLVER_JOBMASK)
2621             {
2622             case SOLVER_VERIFY:
2623               if (select == SOLVER_SOLVABLE_ALL)
2624                 solv->fixmap_all = 1;
2625               FOR_JOB_SELECT(p, pp, select, what)
2626                 {
2627                   s = pool->solvables + p;
2628                   if (!solv->installed || s->repo != solv->installed)
2629                     continue;
2630                   if (!solv->fixmap.size)
2631                     map_grow(&solv->fixmap, solv->installed->end - solv->installed->start);
2632                   MAPSET(&solv->fixmap, p - solv->installed->start);
2633                 }
2634               break;
2635             case SOLVER_UPDATE:
2636               if (select == SOLVER_SOLVABLE_ALL)
2637                 solv->updatemap_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->updatemap.size)
2644                     map_grow(&solv->updatemap, solv->installed->end - solv->installed->start);
2645                   MAPSET(&solv->updatemap, p - solv->installed->start);
2646                 }
2647               break;
2648             default:
2649               break;
2650             }
2651         }
2652
2653       oldnrules = solv->nrules;
2654       FOR_REPO_SOLVABLES(installed, p, s)
2655         solver_addrpmrulesforsolvable(solv, s, &addedmap);
2656       POOL_DEBUG(SOLV_DEBUG_STATS, "added %d rpm rules for installed solvables\n", solv->nrules - oldnrules);
2657       oldnrules = solv->nrules;
2658       FOR_REPO_SOLVABLES(installed, p, s)
2659         solver_addrpmrulesforupdaters(solv, s, &addedmap, 1);
2660       POOL_DEBUG(SOLV_DEBUG_STATS, "added %d rpm rules for updaters of installed solvables\n", solv->nrules - oldnrules);
2661     }
2662
2663   /*
2664    * create rules for all packages involved in the job
2665    * (to be installed or removed)
2666    */
2667
2668   oldnrules = solv->nrules;
2669   for (i = 0; i < job->count; i += 2)
2670     {
2671       how = job->elements[i];
2672       what = job->elements[i + 1];
2673       select = how & SOLVER_SELECTMASK;
2674
2675       switch (how & SOLVER_JOBMASK)
2676         {
2677         case SOLVER_INSTALL:
2678           FOR_JOB_SELECT(p, pp, select, what)
2679             {
2680               MAPSET(&installcandidatemap, p);
2681               solver_addrpmrulesforsolvable(solv, pool->solvables + p, &addedmap);
2682             }
2683           break;
2684         case SOLVER_DISTUPGRADE:
2685           if (select == SOLVER_SOLVABLE_ALL)
2686             {
2687               solv->dupmap_all = 1;
2688               solv->updatemap_all = 1;
2689             }
2690           if (!solv->dupmap_all)
2691             hasdupjob = 1;
2692           break;
2693         default:
2694           break;
2695         }
2696     }
2697   POOL_DEBUG(SOLV_DEBUG_STATS, "added %d rpm rules for packages involved in a job\n", solv->nrules - oldnrules);
2698
2699
2700   /*
2701    * add rules for suggests, enhances
2702    */
2703   oldnrules = solv->nrules;
2704   solver_addrpmrulesforweak(solv, &addedmap);
2705   POOL_DEBUG(SOLV_DEBUG_STATS, "added %d rpm rules because of weak dependencies\n", solv->nrules - oldnrules);
2706
2707   /*
2708    * first pass done, we now have all the rpm rules we need.
2709    * unify existing rules before going over all job rules and
2710    * policy rules.
2711    * at this point the system is always solvable,
2712    * as an empty system (remove all packages) is a valid solution
2713    */
2714
2715   IF_POOLDEBUG (SOLV_DEBUG_STATS)
2716     {
2717       int possible = 0, installable = 0;
2718       for (i = 1; i < pool->nsolvables; i++)
2719         {
2720           if (pool_installable(pool, pool->solvables + i))
2721             installable++;
2722           if (MAPTST(&addedmap, i))
2723             possible++;
2724         }
2725       POOL_DEBUG(SOLV_DEBUG_STATS, "%d of %d installable solvables considered for solving\n", possible, installable);
2726     }
2727
2728   solver_unifyrules(solv);                          /* remove duplicate rpm rules */
2729   solv->rpmrules_end = solv->nrules;              /* mark end of rpm rules */
2730
2731   POOL_DEBUG(SOLV_DEBUG_STATS, "rpm rule memory used: %d K\n", solv->nrules * (int)sizeof(Rule) / 1024);
2732   POOL_DEBUG(SOLV_DEBUG_STATS, "rpm rule creation took %d ms\n", solv_timems(now));
2733
2734   /* create dup maps if needed. We need the maps early to create our
2735    * update rules */
2736   if (hasdupjob)
2737     solver_createdupmaps(solv);
2738
2739   /*
2740    * create feature rules
2741    *
2742    * foreach installed:
2743    *   create assertion (keep installed, if no update available)
2744    *   or
2745    *   create update rule (A|update1(A)|update2(A)|...)
2746    *
2747    * those are used later on to keep a version of the installed packages in
2748    * best effort mode
2749    */
2750
2751   solv->featurerules = solv->nrules;              /* mark start of feature rules */
2752   if (installed)
2753     {
2754       /* foreach possibly installed solvable */
2755       for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
2756         {
2757           if (s->repo != installed)
2758             {
2759               solver_addrule(solv, 0, 0);       /* create dummy rule */
2760               continue;
2761             }
2762           solver_addupdaterule(solv, s, 1);    /* allow s to be updated */
2763         }
2764       /* make sure we accounted for all rules */
2765       assert(solv->nrules - solv->featurerules == installed->end - installed->start);
2766     }
2767   solv->featurerules_end = solv->nrules;
2768
2769     /*
2770      * Add update rules for installed solvables
2771      *
2772      * almost identical to feature rules
2773      * except that downgrades/archchanges/vendorchanges are not allowed
2774      */
2775
2776   solv->updaterules = solv->nrules;
2777
2778   if (installed)
2779     { /* foreach installed solvables */
2780       /* we create all update rules, but disable some later on depending on the job */
2781       for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
2782         {
2783           Rule *sr;
2784
2785           if (s->repo != installed)
2786             {
2787               solver_addrule(solv, 0, 0);       /* create dummy rule */
2788               continue;
2789             }
2790           solver_addupdaterule(solv, s, 0);     /* allowall = 0: downgrades not allowed */
2791           /*
2792            * check for and remove duplicate
2793            */
2794           r = solv->rules + solv->nrules - 1;           /* r: update rule */
2795           sr = r - (installed->end - installed->start); /* sr: feature rule */
2796           /* it's orphaned if there is no feature rule or the feature rule
2797            * consists just of the installed package */
2798           if (!sr->p || (sr->p == i && !sr->d && !sr->w2))
2799             queue_push(&solv->orphaned, i);
2800           if (!r->p)
2801             {
2802               assert(solv->dupmap_all && !sr->p);
2803               continue;
2804             }
2805           if (!solver_samerule(solv, r, sr))
2806             memset(sr, 0, sizeof(*sr));         /* delete unneeded feature rule */
2807           else
2808             solver_disablerule(solv, sr);       /* disable feature rule */
2809         }
2810       /* consistency check: we added a rule for _every_ installed solvable */
2811       assert(solv->nrules - solv->updaterules == installed->end - installed->start);
2812     }
2813   solv->updaterules_end = solv->nrules;
2814
2815
2816   /*
2817    * now add all job rules
2818    */
2819
2820   solv->jobrules = solv->nrules;
2821   if (solv->cleandeps_updatepkgs)
2822     {
2823       queue_free(solv->cleandeps_updatepkgs);
2824       solv->cleandeps_updatepkgs = solv_free(solv->cleandeps_updatepkgs);
2825     }
2826   for (i = 0; i < job->count; i += 2)
2827     {
2828       oldnrules = solv->nrules;
2829
2830       how = job->elements[i];
2831       what = job->elements[i + 1];
2832       weak = how & SOLVER_WEAK;
2833       select = how & SOLVER_SELECTMASK;
2834       switch (how & SOLVER_JOBMASK)
2835         {
2836         case SOLVER_INSTALL:
2837           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sinstall %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
2838           if ((how & SOLVER_CLEANDEPS) != 0 && !solv->cleandepsmap.size && installed)
2839             map_grow(&solv->cleandepsmap, installed->end - installed->start);
2840           if (select == SOLVER_SOLVABLE)
2841             {
2842               p = what;
2843               d = 0;
2844             }
2845           else
2846             {
2847               queue_empty(&q);
2848               FOR_JOB_SELECT(p, pp, select, what)
2849                 queue_push(&q, p);
2850               if (!q.count)
2851                 {
2852                   /* no candidate found, make this an impossible rule */
2853                   queue_push(&q, -SYSTEMSOLVABLE);
2854                 }
2855               p = queue_shift(&q);      /* get first candidate */
2856               d = !q.count ? 0 : pool_queuetowhatprovides(pool, &q);    /* internalize */
2857             }
2858           solver_addjobrule(solv, p, d, i, weak);
2859           break;
2860         case SOLVER_ERASE:
2861           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %s%serase %s\n", weak ? "weak " : "", how & SOLVER_CLEANDEPS ? "clean deps " : "", solver_select2str(pool, select, what));
2862           if ((how & SOLVER_CLEANDEPS) != 0 && !solv->cleandepsmap.size && installed)
2863             map_grow(&solv->cleandepsmap, installed->end - installed->start);
2864           name = (select == SOLVER_SOLVABLE || (select == SOLVER_SOLVABLE_NAME && ISRELDEP(what))) ? 0 : -1;
2865           FOR_JOB_SELECT(p, pp, select, what)
2866             {
2867               s = pool->solvables + p;
2868               if (installed && s->repo == installed)
2869                 name = !name ? s->name : -1;
2870               solver_addjobrule(solv, -p, 0, i, weak);
2871             }
2872           /* special case for "erase a specific solvable": we also
2873            * erase all other solvables with that name, so that they
2874            * don't get picked up as replacement.
2875            * name is > 0 if exactly one installed solvable matched.
2876            */
2877           /* XXX: look also at packages that obsolete this package? */
2878           if (name > 0)
2879             {
2880               int j, k;
2881               k = solv->nrules;
2882               FOR_PROVIDES(p, pp, name)
2883                 {
2884                   s = pool->solvables + p;
2885                   if (s->name != name)
2886                     continue;
2887                   /* keep other versions installed */
2888                   if (s->repo == installed)
2889                     continue;
2890                   /* keep installcandidates of other jobs */
2891                   if (MAPTST(&installcandidatemap, p))
2892                     continue;
2893                   /* don't add the same rule twice */
2894                   for (j = oldnrules; j < k; j++)
2895                     if (solv->rules[j].p == -p)
2896                       break;
2897                   if (j == k)
2898                     solver_addjobrule(solv, -p, 0, i, weak);    /* remove by id */
2899                 }
2900             }
2901           break;
2902
2903         case SOLVER_UPDATE:
2904           if ((how & SOLVER_CLEANDEPS) != 0 && installed)
2905             {
2906               FOR_JOB_SELECT(p, pp, select, what)
2907                 {
2908                   s = pool->solvables + p;
2909                   if (s->repo != installed)
2910                     continue;
2911                   if (!solv->cleandeps_updatepkgs)
2912                     {
2913                       solv->cleandeps_updatepkgs = solv_calloc(1, sizeof(Queue));
2914                       queue_init(solv->cleandeps_updatepkgs);
2915                     }
2916                   queue_pushunique(solv->cleandeps_updatepkgs, p);
2917                   if (!solv->cleandepsmap.size)
2918                     map_grow(&solv->cleandepsmap, installed->end - installed->start);
2919                 }
2920             }
2921           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %supdate %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
2922           break;
2923         case SOLVER_VERIFY:
2924           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sverify %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
2925           break;
2926         case SOLVER_WEAKENDEPS:
2927           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sweaken deps %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
2928           if (select != SOLVER_SOLVABLE)
2929             break;
2930           s = pool->solvables + what;
2931           weaken_solvable_deps(solv, what);
2932           break;
2933         case SOLVER_NOOBSOLETES:
2934           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sno obsolete %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
2935           break;
2936         case SOLVER_LOCK:
2937           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %slock %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
2938           FOR_JOB_SELECT(p, pp, select, what)
2939             {
2940               s = pool->solvables + p;
2941               solver_addjobrule(solv, installed && s->repo == installed ? p : -p, 0, i, weak);
2942             }
2943           break;
2944         case SOLVER_DISTUPGRADE:
2945           POOL_DEBUG(SOLV_DEBUG_JOB, "job: distupgrade %s\n", solver_select2str(pool, select, what));
2946           break;
2947         case SOLVER_DROP_ORPHANED:
2948           POOL_DEBUG(SOLV_DEBUG_JOB, "job: drop orphaned %s\n", solver_select2str(pool, select, what));
2949           if (select == SOLVER_SOLVABLE_ALL)
2950             solv->droporphanedmap_all = 1;
2951           FOR_JOB_SELECT(p, pp, select, what)
2952             {
2953               s = pool->solvables + p;
2954               if (!installed || s->repo != installed)
2955                 continue;
2956               if (!solv->droporphanedmap.size)
2957                 map_grow(&solv->droporphanedmap, installed->end - installed->start);
2958               MAPSET(&solv->droporphanedmap, p - installed->start);
2959             }
2960           break;
2961         case SOLVER_USERINSTALLED:
2962           POOL_DEBUG(SOLV_DEBUG_JOB, "job: user installed %s\n", solver_select2str(pool, select, what));
2963           break;
2964         default:
2965           POOL_DEBUG(SOLV_DEBUG_JOB, "job: unknown job\n");
2966           break;
2967         }
2968
2969         /*
2970          * debug
2971          */
2972
2973       IF_POOLDEBUG (SOLV_DEBUG_JOB)
2974         {
2975           int j;
2976           if (solv->nrules == oldnrules)
2977             POOL_DEBUG(SOLV_DEBUG_JOB, " - no rule created\n");
2978           for (j = oldnrules; j < solv->nrules; j++)
2979             {
2980               POOL_DEBUG(SOLV_DEBUG_JOB, " - job ");
2981               solver_printrule(solv, SOLV_DEBUG_JOB, solv->rules + j);
2982             }
2983         }
2984     }
2985   assert(solv->ruletojob.count == solv->nrules - solv->jobrules);
2986   solv->jobrules_end = solv->nrules;
2987
2988   /* now create infarch and dup rules */
2989   if (!solv->noinfarchcheck)
2990     {
2991       solver_addinfarchrules(solv, &addedmap);
2992       if (pool->obsoleteusescolors)
2993         {
2994           /* currently doesn't work well with infarch rules, so make
2995            * them weak */
2996           for (i = solv->infarchrules; i < solv->infarchrules_end; i++)
2997             queue_push(&solv->weakruleq, i);
2998         }
2999     }
3000   else
3001     solv->infarchrules = solv->infarchrules_end = solv->nrules;
3002
3003   if (hasdupjob)
3004     {
3005       solver_addduprules(solv, &addedmap);
3006       solver_freedupmaps(solv); /* no longer needed */
3007     }
3008   else
3009     solv->duprules = solv->duprules_end = solv->nrules;
3010
3011   if (1)
3012     solver_addchoicerules(solv);
3013   else
3014     solv->choicerules = solv->choicerules_end = solv->nrules;
3015
3016   /* all rules created
3017    * --------------------------------------------------------------
3018    * prepare for solving
3019    */
3020
3021   /* free unneeded memory */
3022   map_free(&addedmap);
3023   map_free(&installcandidatemap);
3024   queue_free(&q);
3025
3026   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);
3027   POOL_DEBUG(SOLV_DEBUG_STATS, "overall rule memory used: %d K\n", solv->nrules * (int)sizeof(Rule) / 1024);
3028
3029   /* create weak map */
3030   map_init(&solv->weakrulemap, solv->nrules);
3031   for (i = 0; i < solv->weakruleq.count; i++)
3032     {
3033       p = solv->weakruleq.elements[i];
3034       MAPSET(&solv->weakrulemap, p);
3035     }
3036
3037   /* all new rules are learnt after this point */
3038   solv->learntrules = solv->nrules;
3039
3040   /* create watches chains */
3041   makewatches(solv);
3042
3043   /* create assertion index. it is only used to speed up
3044    * makeruledecsions() a bit */
3045   for (i = 1, r = solv->rules + i; i < solv->nrules; i++, r++)
3046     if (r->p && !r->w2 && (r->d == 0 || r->d == -1))
3047       queue_push(&solv->ruleassertions, i);
3048
3049   /* disable update rules that conflict with our job */
3050   solver_disablepolicyrules(solv);
3051
3052   /* make initial decisions based on assertion rules */
3053   makeruledecisions(solv);
3054   POOL_DEBUG(SOLV_DEBUG_SOLVER, "problems so far: %d\n", solv->problems.count);
3055
3056   /* no mistakes */
3057   if (solv->cleandeps_mistakes)
3058     {
3059       queue_free(solv->cleandeps_mistakes);
3060       solv->cleandeps_mistakes = solv_free(solv->cleandeps_mistakes);
3061     }
3062
3063   /*
3064    * ********************************************
3065    * solve!
3066    * ********************************************
3067    */
3068
3069   now = solv_timems(0);
3070   solver_run_sat(solv, 1, solv->dontinstallrecommended ? 0 : 1);
3071   POOL_DEBUG(SOLV_DEBUG_STATS, "solver took %d ms\n", solv_timems(now));
3072
3073   /*
3074    * prepare solution queue if there were problems
3075    */
3076   solver_prepare_solutions(solv);
3077
3078   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);
3079   POOL_DEBUG(SOLV_DEBUG_STATS, "solver_solve took %d ms\n", solv_timems(solve_start));
3080
3081   /* return number of problems */
3082   return solv->problems.count ? solv->problems.count / 2 : 0;
3083 }
3084
3085 Transaction *
3086 solver_create_transaction(Solver *solv)
3087 {
3088   return transaction_create_decisionq(solv->pool, &solv->decisionq, &solv->noobsoletes);
3089 }
3090
3091 void solver_get_orphaned(Solver *solv, Queue *orphanedq)
3092 {
3093   queue_free(orphanedq);
3094   queue_init_clone(orphanedq, &solv->orphaned);
3095 }
3096
3097 void solver_get_recommendations(Solver *solv, Queue *recommendationsq, Queue *suggestionsq, int noselected)
3098 {
3099   Pool *pool = solv->pool;
3100   Queue redoq, disabledq;
3101   int goterase, i;
3102   Solvable *s;
3103   Rule *r;
3104   Map obsmap;
3105
3106   if (!recommendationsq && !suggestionsq)
3107     return;
3108
3109   map_init(&obsmap, pool->nsolvables);
3110   if (solv->installed)
3111     {
3112       Id obs, *obsp, p, po, ppo;
3113       for (p = solv->installed->start; p < solv->installed->end; p++)
3114         {
3115           s = pool->solvables + p;
3116           if (s->repo != solv->installed || !s->obsoletes)
3117             continue;
3118           if (solv->decisionmap[p] <= 0)
3119             continue;
3120           if (solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p))
3121             continue;
3122           obsp = s->repo->idarraydata + s->obsoletes;
3123           /* foreach obsoletes */
3124           while ((obs = *obsp++) != 0)
3125             FOR_PROVIDES(po, ppo, obs)
3126               MAPSET(&obsmap, po);
3127         }
3128     }
3129
3130   queue_init(&redoq);
3131   queue_init(&disabledq);
3132   goterase = 0;
3133   /* disable all erase jobs (including weak "keep uninstalled" rules) */
3134   for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++)
3135     {
3136       if (r->d < 0)     /* disabled ? */
3137         continue;
3138       if (r->p >= 0)    /* install job? */
3139         continue;
3140       queue_push(&disabledq, i);
3141       solver_disablerule(solv, r);
3142       goterase++;
3143     }
3144
3145   if (goterase)
3146     {
3147       enabledisablelearntrules(solv);
3148       removedisabledconflicts(solv, &redoq);
3149     }
3150
3151   /*
3152    * find recommended packages
3153    */
3154   if (recommendationsq)
3155     {
3156       Id rec, *recp, p, pp;
3157
3158       queue_empty(recommendationsq);
3159       /* create map of all recommened packages */
3160       solv->recommends_index = -1;
3161       MAPZERO(&solv->recommendsmap);
3162
3163       /* put all packages the solver already chose in the map */
3164       if (solv->decisioncnt_weak)
3165         {
3166           for (i = solv->decisioncnt_weak; i < solv->decisioncnt_orphan; i++)
3167             {
3168               Id why;
3169               why = solv->decisionq_why.elements[i];
3170               if (why)
3171                 continue;       /* forced by unit rule */
3172               p = solv->decisionq.elements[i];
3173               if (p < 0)
3174                 continue;
3175               MAPSET(&solv->recommendsmap, p);
3176             }
3177         }
3178
3179       for (i = 0; i < solv->decisionq.count; i++)
3180         {
3181           p = solv->decisionq.elements[i];
3182           if (p < 0)
3183             continue;
3184           s = pool->solvables + p;
3185           if (s->recommends)
3186             {
3187               recp = s->repo->idarraydata + s->recommends;
3188               while ((rec = *recp++) != 0)
3189                 {
3190                   FOR_PROVIDES(p, pp, rec)
3191                     if (solv->decisionmap[p] > 0)
3192                       break;
3193                   if (p)
3194                     {
3195                       if (!noselected)
3196                         {
3197                           FOR_PROVIDES(p, pp, rec)
3198                             if (solv->decisionmap[p] > 0)
3199                               MAPSET(&solv->recommendsmap, p);
3200                         }
3201                       continue; /* p != 0: already fulfilled */
3202                     }
3203                   FOR_PROVIDES(p, pp, rec)
3204                     MAPSET(&solv->recommendsmap, p);
3205                 }
3206             }
3207         }
3208       for (i = 1; i < pool->nsolvables; i++)
3209         {
3210           if (solv->decisionmap[i] < 0)
3211             continue;
3212           if (solv->decisionmap[i] > 0 && noselected)
3213             continue;
3214           if (MAPTST(&obsmap, i))
3215             continue;
3216           s = pool->solvables + i;
3217           if (!MAPTST(&solv->recommendsmap, i))
3218             {
3219               if (!s->supplements)
3220                 continue;
3221               if (!pool_installable(pool, s))
3222                 continue;
3223               if (!solver_is_supplementing(solv, s))
3224                 continue;
3225             }
3226           queue_push(recommendationsq, i);
3227         }
3228       /* we use MODE_SUGGEST here so that repo prio is ignored */
3229       policy_filter_unwanted(solv, recommendationsq, POLICY_MODE_SUGGEST);
3230     }
3231
3232   /*
3233    * find suggested packages
3234    */
3235
3236   if (suggestionsq)
3237     {
3238       Id sug, *sugp, p, pp;
3239
3240       queue_empty(suggestionsq);
3241       /* create map of all suggests that are still open */
3242       solv->recommends_index = -1;
3243       MAPZERO(&solv->suggestsmap);
3244       for (i = 0; i < solv->decisionq.count; i++)
3245         {
3246           p = solv->decisionq.elements[i];
3247           if (p < 0)
3248             continue;
3249           s = pool->solvables + p;
3250           if (s->suggests)
3251             {
3252               sugp = s->repo->idarraydata + s->suggests;
3253               while ((sug = *sugp++) != 0)
3254                 {
3255                   FOR_PROVIDES(p, pp, sug)
3256                     if (solv->decisionmap[p] > 0)
3257                       break;
3258                   if (p)
3259                     {
3260                       if (!noselected)
3261                         {
3262                           FOR_PROVIDES(p, pp, sug)
3263                             if (solv->decisionmap[p] > 0)
3264                               MAPSET(&solv->suggestsmap, p);
3265                         }
3266                       continue; /* already fulfilled */
3267                     }
3268                   FOR_PROVIDES(p, pp, sug)
3269                     MAPSET(&solv->suggestsmap, p);
3270                 }
3271             }
3272         }
3273       for (i = 1; i < pool->nsolvables; i++)
3274         {
3275           if (solv->decisionmap[i] < 0)
3276             continue;
3277           if (solv->decisionmap[i] > 0 && noselected)
3278             continue;
3279           if (MAPTST(&obsmap, i))
3280             continue;
3281           s = pool->solvables + i;
3282           if (!MAPTST(&solv->suggestsmap, i))
3283             {
3284               if (!s->enhances)
3285                 continue;
3286               if (!pool_installable(pool, s))
3287                 continue;
3288               if (!solver_is_enhancing(solv, s))
3289                 continue;
3290             }
3291           queue_push(suggestionsq, i);
3292         }
3293       policy_filter_unwanted(solv, suggestionsq, POLICY_MODE_SUGGEST);
3294     }
3295
3296   /* undo removedisabledconflicts */
3297   if (redoq.count)
3298     undo_removedisabledconflicts(solv, &redoq);
3299   queue_free(&redoq);
3300
3301   /* undo job rule disabling */
3302   for (i = 0; i < disabledq.count; i++)
3303     solver_enablerule(solv, solv->rules + disabledq.elements[i]);
3304   queue_free(&disabledq);
3305   map_free(&obsmap);
3306 }
3307
3308
3309 /***********************************************************************/
3310 /* disk usage computations */
3311
3312 /*-------------------------------------------------------------------
3313  *
3314  * calculate DU changes
3315  */
3316
3317 void
3318 solver_calc_duchanges(Solver *solv, DUChanges *mps, int nmps)
3319 {
3320   Map installedmap;
3321
3322   solver_create_state_maps(solv, &installedmap, 0);
3323   pool_calc_duchanges(solv->pool, &installedmap, mps, nmps);
3324   map_free(&installedmap);
3325 }
3326
3327
3328 /*-------------------------------------------------------------------
3329  *
3330  * calculate changes in install size
3331  */
3332
3333 int
3334 solver_calc_installsizechange(Solver *solv)
3335 {
3336   Map installedmap;
3337   int change;
3338
3339   solver_create_state_maps(solv, &installedmap, 0);
3340   change = pool_calc_installsizechange(solv->pool, &installedmap);
3341   map_free(&installedmap);
3342   return change;
3343 }
3344
3345 void
3346 solver_create_state_maps(Solver *solv, Map *installedmap, Map *conflictsmap)
3347 {
3348   pool_create_state_maps(solv->pool, &solv->decisionq, installedmap, conflictsmap);
3349 }
3350
3351 void
3352 solver_trivial_installable(Solver *solv, Queue *pkgs, Queue *res)
3353 {
3354   Map installedmap;
3355   pool_create_state_maps(solv->pool,  &solv->decisionq, &installedmap, 0);
3356   pool_trivial_installable_noobsoletesmap(solv->pool, &installedmap, pkgs, res, solv->noobsoletes.size ? &solv->noobsoletes : 0);
3357   map_free(&installedmap);
3358 }
3359
3360 /*-------------------------------------------------------------------
3361  *
3362  * decision introspection
3363  */
3364
3365 int
3366 solver_get_decisionlevel(Solver *solv, Id p)
3367 {
3368   return solv->decisionmap[p];
3369 }
3370
3371 void
3372 solver_get_decisionqueue(Solver *solv, Queue *decisionq)
3373 {
3374   queue_free(decisionq);
3375   queue_init_clone(decisionq, &solv->decisionq);
3376 }
3377
3378 int
3379 solver_get_lastdecisionblocklevel(Solver *solv)
3380 {
3381   Id p;
3382   if (solv->decisionq.count == 0)
3383     return 0;
3384   p = solv->decisionq.elements[solv->decisionq.count - 1];
3385   if (p < 0)
3386     p = -p;
3387   return solv->decisionmap[p] < 0 ? -solv->decisionmap[p] : solv->decisionmap[p];
3388 }
3389
3390 void
3391 solver_get_decisionblock(Solver *solv, int level, Queue *decisionq)
3392 {
3393   Id p;
3394   int i;
3395
3396   queue_empty(decisionq);
3397   for (i = 0; i < solv->decisionq.count; i++)
3398     {
3399       p = solv->decisionq.elements[i];
3400       if (p < 0)
3401         p = -p;
3402       if (solv->decisionmap[p] == level || solv->decisionmap[p] == -level)
3403         break;
3404     }
3405   if (i == solv->decisionq.count)
3406     return;
3407   for (i = 0; i < solv->decisionq.count; i++)
3408     {
3409       p = solv->decisionq.elements[i];
3410       if (p < 0)
3411         p = -p;
3412       if (solv->decisionmap[p] == level || solv->decisionmap[p] == -level)
3413         queue_push(decisionq, p);
3414       else
3415         break;
3416     }
3417 }
3418
3419 int
3420 solver_describe_decision(Solver *solv, Id p, Id *infop)
3421 {
3422   int i;
3423   Id pp, why;
3424
3425   if (infop)
3426     *infop = 0;
3427   if (!solv->decisionmap[p])
3428     return SOLVER_REASON_UNRELATED;
3429   pp = solv->decisionmap[p] < 0 ? -p : p;
3430   for (i = 0; i < solv->decisionq.count; i++)
3431     if (solv->decisionq.elements[i] == pp)
3432       break;
3433   if (i == solv->decisionq.count)       /* just in case... */
3434     return SOLVER_REASON_UNRELATED;
3435   why = solv->decisionq_why.elements[i];
3436   if (why > 0)
3437     {
3438       if (infop)
3439         *infop = why;
3440       return SOLVER_REASON_UNIT_RULE;
3441     }
3442   why = -why;
3443   if (i < solv->decisioncnt_update)
3444     {
3445       if (i == 0)
3446         {
3447           if (infop)
3448             *infop = SYSTEMSOLVABLE;
3449           return SOLVER_REASON_KEEP_INSTALLED;
3450         }
3451       if (infop)
3452         *infop = why;
3453       return SOLVER_REASON_RESOLVE_JOB;
3454     }
3455   if (i < solv->decisioncnt_keep)
3456     {
3457       if (why == 0 && pp < 0)
3458         return SOLVER_REASON_CLEANDEPS_ERASE;
3459       if (infop)
3460         {
3461           if (why >= solv->updaterules && why < solv->updaterules_end)
3462             *infop = why - solv->updaterules;
3463           else if (why >= solv->featurerules && why < solv->featurerules_end)
3464             *infop = why - solv->featurerules;
3465         }
3466       return SOLVER_REASON_UPDATE_INSTALLED;
3467     }
3468   if (i < solv->decisioncnt_resolve)
3469     {
3470       if (why == 0 && pp < 0)
3471         return SOLVER_REASON_CLEANDEPS_ERASE;
3472       if (infop)
3473         {
3474           if (why >= solv->updaterules && why < solv->updaterules_end)
3475             *infop = why - solv->updaterules;
3476           else if (why >= solv->featurerules && why < solv->featurerules_end)
3477             *infop = why - solv->featurerules;
3478         }
3479       return SOLVER_REASON_KEEP_INSTALLED;
3480     }
3481   if (i < solv->decisioncnt_weak)
3482     {
3483       if (infop)
3484         *infop = why;
3485       return SOLVER_REASON_RESOLVE;
3486     }
3487   if (solv->decisionq.count < solv->decisioncnt_orphan)
3488     return SOLVER_REASON_WEAKDEP;
3489   return SOLVER_REASON_RESOLVE_ORPHAN;
3490 }
3491
3492
3493 void
3494 solver_describe_weakdep_decision(Solver *solv, Id p, Queue *whyq)
3495 {
3496   Pool *pool = solv->pool;
3497   int i;
3498   int level = solv->decisionmap[p];
3499   int decisionno;
3500   Solvable *s;
3501
3502   queue_empty(whyq);
3503   if (level < 0)
3504     return;     /* huh? */
3505   for (decisionno = 0; decisionno < solv->decisionq.count; decisionno++)
3506     if (solv->decisionq.elements[decisionno] == p)
3507       break;
3508   if (decisionno == solv->decisionq.count)
3509     return;     /* huh? */
3510   if (decisionno < solv->decisioncnt_weak || decisionno >= solv->decisioncnt_orphan)
3511     return;     /* huh? */
3512
3513   /* 1) list all packages that recommend us */
3514   for (i = 1; i < pool->nsolvables; i++)
3515     {
3516       Id *recp, rec, pp2, p2;
3517       if (solv->decisionmap[i] < 0 || solv->decisionmap[i] >= level)
3518         continue;
3519       s = pool->solvables + i;
3520       if (!s->recommends)
3521         continue;
3522       if (!solv->addalreadyrecommended && s->repo == solv->installed)
3523         continue;
3524       recp = s->repo->idarraydata + s->recommends;
3525       while ((rec = *recp++) != 0)
3526         {
3527           int found = 0;
3528           FOR_PROVIDES(p2, pp2, rec)
3529             {
3530               if (p2 == p)
3531                 found = 1;
3532               else
3533                 {
3534                   /* if p2 is already installed, this recommends is ignored */
3535                   if (solv->decisionmap[p2] > 0 && solv->decisionmap[p2] < level)
3536                     break;
3537                 }
3538             }
3539           if (!p2 && found)
3540             {
3541               queue_push(whyq, SOLVER_REASON_RECOMMENDED);
3542               queue_push2(whyq, p2, rec);
3543             }
3544         }
3545     }
3546   /* 2) list all supplements */
3547   s = pool->solvables + p;
3548   if (s->supplements && level > 0)
3549     {
3550       Id *supp, sup, pp2, p2;
3551       /* this is a hack. to use solver_dep_fulfilled we temporarily clear
3552        * everything above our level in the decisionmap */
3553       for (i = decisionno; i < solv->decisionq.count; i++ )
3554         {
3555           p2 = solv->decisionq.elements[i];
3556           if (p2 > 0)
3557             solv->decisionmap[p2] = -solv->decisionmap[p2];
3558         }
3559       supp = s->repo->idarraydata + s->supplements;
3560       while ((sup = *supp++) != 0)
3561         if (solver_dep_fulfilled(solv, sup))
3562           {
3563             int found = 0;
3564             /* let's see if this is an easy supp */
3565             FOR_PROVIDES(p2, pp2, sup)
3566               {
3567                 if (!solv->addalreadyrecommended && solv->installed)
3568                   {
3569                     if (pool->solvables[p2].repo == solv->installed)
3570                       continue;
3571                   }
3572                 if (solv->decisionmap[p2] > 0 && solv->decisionmap[p2] < level)
3573                   {
3574                     queue_push(whyq, SOLVER_REASON_SUPPLEMENTED);
3575                     queue_push2(whyq, p2, sup);
3576                     found = 1;
3577                   }
3578               }
3579             if (!found)
3580               {
3581                 /* hard case, just note dependency with no package */
3582                 queue_push(whyq, SOLVER_REASON_SUPPLEMENTED);
3583                 queue_push2(whyq, 0, sup);
3584               }
3585           }
3586       for (i = decisionno; i < solv->decisionq.count; i++)
3587         {
3588           p2 = solv->decisionq.elements[i];
3589           if (p2 > 0)
3590             solv->decisionmap[p2] = -solv->decisionmap[p2];
3591         }
3592     }
3593 }
3594
3595 void
3596 pool_job2solvables(Pool *pool, Queue *pkgs, Id how, Id what)
3597 {
3598   Id p, pp;
3599   how &= SOLVER_SELECTMASK;
3600   queue_empty(pkgs);
3601   if (how == SOLVER_SOLVABLE_ALL)
3602     {
3603       for (p = 2; p < pool->nsolvables; p++)
3604         if (pool->solvables[p].repo)
3605           queue_push(pkgs, p);
3606     }
3607   else if (how == SOLVER_SOLVABLE_REPO)
3608     {
3609       Repo *repo = pool_id2repo(pool, what);
3610       Solvable *s;
3611       if (repo)
3612         FOR_REPO_SOLVABLES(repo, p, s)
3613           queue_push(pkgs, p);
3614     }
3615   else
3616     {
3617       FOR_JOB_SELECT(p, pp, how, what)
3618         queue_push(pkgs, p);
3619     }
3620 }
3621