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