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 #include "cplxdeps.h"
  29 #include "linkedpkg.h"
  30
  31 #define RULES_BLOCK 63
  32
  33
  34 /********************************************************************
  35  *
  36  * dependency check helpers
  37  *
  38  */
  39
  40 /*-------------------------------------------------------------------
  41  * handle split provides
  42  *
  43  * a splitprovides dep looks like
  44  *     namespace:splitprovides(pkg REL_WITH path)
  45  * and is only true if pkg is installed and contains the specified path.
  46  * we also make sure that pkg is selected for an update, otherwise the
  47  * update would always be forced onto the user.
  48  * Map m is the map used when called from dep_possible.
  49  */
  50
  51 static int
  52 solver_is_updating(Solver *solv, Id p)
  53 {
  54   /* check if the update rule is true */
  55   Pool *pool = solv->pool;
  56   Rule *r;
  57   Id l, pp;
  58   if (solv->decisionmap[p] >= 0)
  59     return 0;   /* old package stayed */
  60   r = solv->rules + solv->updaterules + (p - solv->installed->start);
  61   FOR_RULELITERALS(l, pp, r)
  62     if (l > 0 && l != p && solv->decisionmap[l] > 0)
  63       return 1;
  64   return 0;
  65 }
  66
  67 int
  68 solver_splitprovides(Solver *solv, Id dep, Map *m)
  69 {
  70   Pool *pool = solv->pool;
  71   Id p, pp;
  72   Reldep *rd;
  73   Solvable *s;
  74
  75   if (!solv->dosplitprovides || !solv->installed)
  76     return 0;
  77   if (!ISRELDEP(dep))
  78     return 0;
  79   rd = GETRELDEP(pool, dep);
  80   if (rd->flags != REL_WITH)
  81     return 0;
  82   /*
  83    * things are a bit tricky here if pool->addedprovides == 1, because most split-provides are in
  84    * a non-standard location. If we simply call pool_whatprovides, we'll drag in the complete
  85    * file list. Instead we rely on pool_addfileprovides ignoring the addfileprovidesfiltered flag
  86    * for installed packages and check the lazywhatprovidesq (ignoring the REL_WITH part, but
  87    * we filter the package name further down anyway).
  88    */
  89   if (pool->addedfileprovides == 1 && !ISRELDEP(rd->evr) && !pool->whatprovides[rd->evr])
  90     pp = pool_searchlazywhatprovidesq(pool, rd->evr);
  91   else
  92     pp = pool_whatprovides(pool, dep);
  93   while ((p = pool->whatprovidesdata[pp++]) != 0)
  94     {
  95       /* here we have packages that provide the correct name and contain the path,
  96        * now do extra filtering */
  97       s = pool->solvables + p;
  98       if (s->repo != solv->installed || s->name != rd->name)
  99         continue;
 100       /* check if the package is updated. if m is set, we're called from dep_possible */
 101       if (m || solver_is_updating(solv, p))
 102         return 1;
 103     }
 104   return 0;
 105 }
 106
 107
 108 /* mirrors solver_dep_fulfilled, but returns 2 if a new package
 109  * was involved */
 110 static int
 111 solver_dep_fulfilled_alreadyinstalled(Solver *solv, Id dep)
 112 {
 113   Pool *pool = solv->pool;
 114   Id p, pp;
 115   int r;
 116
 117   if (ISRELDEP(dep))
 118     {
 119       Reldep *rd = GETRELDEP(pool, dep);
 120       if (rd->flags == REL_COND)
 121         {
 122           int r1, r2;
 123           if (ISRELDEP(rd->evr))
 124             {
 125               Reldep *rd2 = GETRELDEP(pool, rd->evr);
 126               if (rd2->flags == REL_ELSE)
 127                 {
 128                   r1 = solver_dep_fulfilled_alreadyinstalled(solv, rd2->name);
 129                   if (r1)
 130                     {
 131                       r2 = solver_dep_fulfilled_alreadyinstalled(solv, rd->name);
 132                       return r2 && r1 == 2 ? 2 : r2;
 133                     }
 134                   return solver_dep_fulfilled_alreadyinstalled(solv, rd2->evr);
 135                 }
 136             }
 137           r1 = solver_dep_fulfilled_alreadyinstalled(solv, rd->name);
 138           r2 = !solver_dep_fulfilled_alreadyinstalled(solv, rd->evr);
 139           if (!r1 && !r2)
 140             return 0;
 141           return r1 == 2 ? 2 : 1;
 142         }
 143       if (rd->flags == REL_AND)
 144         {
 145           int r2, r1 = solver_dep_fulfilled_alreadyinstalled(solv, rd->name);
 146           if (!r1)
 147             return 0;
 148           r2 = solver_dep_fulfilled_alreadyinstalled(solv, rd->evr);
 149           if (!r2)
 150             return 0;
 151           return r1 == 2 || r2 == 2 ? 2 : 1;
 152         }
 153       if (rd->flags == REL_OR)
 154         {
 155           int r2, r1 = solver_dep_fulfilled_alreadyinstalled(solv, rd->name);
 156           r2 = solver_dep_fulfilled_alreadyinstalled(solv, rd->evr);
 157           if (!r1 && !r2)
 158             return 0;
 159           return r1 == 2 || r2 == 2 ? 2 : 1;
 160         }
 161       if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
 162         return solver_splitprovides(solv, rd->evr, 0);
 163       if (rd->flags == REL_NAMESPACE && solv->installsuppdepq)
 164         {
 165           Queue *q = solv->installsuppdepq;
 166           int i;
 167           for (i = 0; i < q->count; i++)
 168             if (q->elements[i] == dep || q->elements[i] == rd->name)
 169               return 2;
 170         }
 171     }
 172   r = 0;
 173   FOR_PROVIDES(p, pp, dep)
 174     if (solv->decisionmap[p] > 0)
 175       {
 176         Solvable *s = pool->solvables + p;
 177         if (s->repo && s->repo != solv->installed)
 178           return 2;
 179         r = 1;
 180       }
 181   return r;
 182 }
 183
 184 static int
 185 solver_is_supplementing_alreadyinstalled(Solver *solv, Solvable *s)
 186 {
 187   Id sup, *supp;
 188   supp = s->repo->idarraydata + s->supplements;
 189   while ((sup = *supp++) != 0)
 190     if (solver_dep_fulfilled_alreadyinstalled(solv, sup) == 2)
 191       return 1;
 192   return 0;
 193 }
 194
 195 static Id
 196 autouninstall(Solver *solv, Id *problem)
 197 {
 198   Pool *pool = solv->pool;
 199   int i;
 200   int lastfeature = 0, lastupdate = 0;
 201   Id v;
 202   Id extraflags = -1;
 203   Map *m = 0;
 204
 205   if (!solv->allowuninstall && !solv->allowuninstall_all)
 206     {
 207       if (!solv->allowuninstallmap.size)
 208         return 0;               /* why did we get called? */
 209       m = &solv->allowuninstallmap;
 210     }
 211   for (i = 0; (v = problem[i]) != 0; i++)
 212     {
 213       if (v < 0)
 214         extraflags &= solv->job.elements[-v - 1];
 215       if (v >= solv->updaterules && v < solv->updaterules_end)
 216         {
 217           Rule *r;
 218           if (m && !MAPTST(m, v - solv->updaterules))
 219             continue;
 220           /* check if identical to feature rule, we don't like that (except for orphans) */
 221           r = solv->rules + solv->featurerules + (v - solv->updaterules);
 222           if (!r->p)
 223             {
 224               /* update rule == feature rule */
 225               if (v > lastfeature)
 226                 lastfeature = v;
 227               /* prefer orphaned packages in dup mode */
 228               if (solv->keep_orphans)
 229                 {
 230                   r = solv->rules + v;
 231                   if (!r->d && !r->w2 && r->p == (solv->installed->start + (v - solv->updaterules)))
 232                     {
 233                       lastfeature = v;
 234                       lastupdate = 0;
 235                       break;
 236                     }
 237                 }
 238               continue;
 239             }
 240           if (v > lastupdate)
 241             lastupdate = v;
 242         }
 243     }
 244   if (!lastupdate && !lastfeature)
 245     return 0;
 246   v = lastupdate ? lastupdate : lastfeature;
 247   POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "allowuninstall disabling ");
 248   solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE, solv->rules + v);
 249   solver_disableproblem(solv, v);
 250   if (extraflags != -1 && (extraflags & SOLVER_CLEANDEPS) != 0 && solv->cleandepsmap.size)
 251     {
 252       /* add the package to the updatepkgs list, this will automatically turn
 253        * on cleandeps mode */
 254       Id p = solv->rules[v].p;
 255       if (!solv->cleandeps_updatepkgs)
 256         {
 257           solv->cleandeps_updatepkgs = solv_calloc(1, sizeof(Queue));
 258           queue_init(solv->cleandeps_updatepkgs);
 259         }
 260       if (p > 0)
 261         {
 262           int oldupdatepkgscnt = solv->cleandeps_updatepkgs->count;
 263           queue_pushunique(solv->cleandeps_updatepkgs, p);
 264           if (solv->cleandeps_updatepkgs->count != oldupdatepkgscnt)
 265             solver_disablepolicyrules(solv);
 266         }
 267     }
 268   return v;
 269 }
 270
 271 /************************************************************************/
 272
 273 /*
 274  * enable/disable learnt rules
 275  *
 276  * we have enabled or disabled some of our rules. We now reenable all
 277  * of our learnt rules except the ones that were learnt from rules that
 278  * are now disabled.
 279  */
 280 static void
 281 enabledisablelearntrules(Solver *solv)
 282 {
 283   Pool *pool = solv->pool;
 284   Rule *r;
 285   Id why, *whyp;
 286   int i;
 287
 288   POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "enabledisablelearntrules called\n");
 289   for (i = solv->learntrules, r = solv->rules + i; i < solv->nrules; i++, r++)
 290     {
 291       whyp = solv->learnt_pool.elements + solv->learnt_why.elements[i - solv->learntrules];
 292       while ((why = *whyp++) != 0)
 293         {
 294           assert(why > 0 && why < i);
 295           if (solv->rules[why].d < 0)
 296             break;
 297         }
 298       /* why != 0: we found a disabled rule, disable the learnt rule */
 299       if (why && r->d >= 0)
 300         {
 301           IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS)
 302             {
 303               POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "disabling ");
 304               solver_printruleclass(solv, SOLV_DEBUG_SOLUTIONS, r);
 305             }
 306           solver_disablerule(solv, r);
 307         }
 308       else if (!why && r->d < 0)
 309         {
 310           IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS)
 311             {
 312               POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "re-enabling ");
 313               solver_printruleclass(solv, SOLV_DEBUG_SOLUTIONS, r);
 314             }
 315           solver_enablerule(solv, r);
 316         }
 317     }
 318 }
 319
 320
 321 /*
 322  * make assertion rules into decisions
 323  *
 324  * Go through rules and add direct assertions to the decisionqueue.
 325  * If we find a conflict, disable rules and add them to problem queue.
 326  */
 327
 328 static void
 329 makeruledecisions(Solver *solv)
 330 {
 331   Pool *pool = solv->pool;
 332   int i, ri, ii;
 333   Rule *r, *rr;
 334   Id v, vv;
 335   int decisionstart;
 336   int record_proof = 1;
 337   int oldproblemcount;
 338   int havedisabled = 0;
 339
 340   /* The system solvable is always installed first */
 341   assert(solv->decisionq.count == 0);
 342   queue_push(&solv->decisionq, SYSTEMSOLVABLE);
 343   queue_push(&solv->decisionq_why, 0);
 344   queue_push2(&solv->decisionq_reason, 0, 0);
 345   solv->decisionmap[SYSTEMSOLVABLE] = 1;        /* installed at level '1' */
 346
 347   decisionstart = solv->decisionq.count;
 348   for (;;)
 349     {
 350       /* if we needed to re-run, back up decisions to decisionstart */
 351       while (solv->decisionq.count > decisionstart)
 352         {
 353           v = solv->decisionq.elements[--solv->decisionq.count];
 354           --solv->decisionq_why.count;
 355           vv = v > 0 ? v : -v;
 356           solv->decisionmap[vv] = 0;
 357         }
 358
 359       /* note that the ruleassertions queue is ordered */
 360       for (ii = 0; ii < solv->ruleassertions.count; ii++)
 361         {
 362           ri = solv->ruleassertions.elements[ii];
 363           r = solv->rules + ri;
 364
 365           if (havedisabled && ri >= solv->learntrules)
 366             {
 367               /* just started with learnt rule assertions. If we have disabled
 368                * some rules, adapt the learnt rule status */
 369               enabledisablelearntrules(solv);
 370               havedisabled = 0;
 371             }
 372
 373           if (r->d < 0 || !r->p || r->w2)       /* disabled, dummy or no assertion */
 374             continue;
 375
 376           /* do weak rules in phase 2 */
 377           if (ri < solv->learntrules && solv->weakrulemap.size && MAPTST(&solv->weakrulemap, ri))
 378             continue;
 379
 380           v = r->p;
 381           vv = v > 0 ? v : -v;
 382
 383           if (!solv->decisionmap[vv])          /* if not yet decided */
 384             {
 385               queue_push(&solv->decisionq, v);
 386               queue_push(&solv->decisionq_why, r - solv->rules);
 387               solv->decisionmap[vv] = v > 0 ? 1 : -1;
 388               IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
 389                 {
 390                   Solvable *s = solv->pool->solvables + vv;
 391                   if (v < 0)
 392                     POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "conflicting %s (assertion)\n", pool_solvable2str(solv->pool, s));
 393                   else
 394                     POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "installing  %s (assertion)\n", pool_solvable2str(solv->pool, s));
 395                 }
 396               continue;
 397             }
 398
 399           /* check against previous decision: is there a conflict? */
 400           if (v > 0 && solv->decisionmap[vv] > 0)    /* ok to install */
 401             continue;
 402           if (v < 0 && solv->decisionmap[vv] < 0)    /* ok to remove */
 403             continue;
 404
 405           /*
 406            * found a conflict!
 407            *
 408            * The rule (r) we're currently processing says something
 409            * different (v = r->p) than a previous decision (decisionmap[abs(v)])
 410            * on this literal
 411            */
 412
 413           if (ri >= solv->learntrules)
 414             {
 415               /* conflict with a learnt rule */
 416               /* can happen when packages cannot be installed for multiple reasons. */
 417               /* we disable the learnt rule in this case */
 418               /* (XXX: we should really call analyze_unsolvable_rule here!) */
 419               solver_disablerule(solv, r);
 420               continue;
 421             }
 422
 423           /*
 424            * find the decision which is the "opposite" of the rule
 425            */
 426           for (i = 0; i < solv->decisionq.count; i++)
 427             if (solv->decisionq.elements[i] == -v)
 428               break;
 429           assert(i < solv->decisionq.count);         /* assert that we found it */
 430           oldproblemcount = solv->problems.count;
 431
 432           /*
 433            * conflict with system solvable ?
 434            */
 435           if (v == -SYSTEMSOLVABLE)
 436             {
 437               if (record_proof)
 438                 {
 439                   queue_push(&solv->problems, solv->learnt_pool.count);
 440                   queue_push(&solv->learnt_pool, ri);
 441                   queue_push(&solv->learnt_pool, 0);
 442                 }
 443               else
 444                 queue_push(&solv->problems, 0);
 445               POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "conflict with system solvable, disabling rule #%d\n", ri);
 446               if  (ri >= solv->jobrules && ri < solv->jobrules_end)
 447                 v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
 448               else
 449                 v = ri;
 450               queue_push(&solv->problems, v);
 451               queue_push(&solv->problems, 0);
 452               if (v >= solv->featurerules && v < solv->updaterules_end)
 453                 {
 454                   if (solv->allowuninstall || solv->allowuninstall_all || solv->allowuninstallmap.size)
 455                     if (autouninstall(solv, solv->problems.elements + oldproblemcount + 1) != 0)
 456                       {
 457                         solv->problems.count = oldproblemcount;
 458                         havedisabled = 1;
 459                         break;  /* start over */
 460                       }
 461                 }
 462               solver_disableproblem(solv, v);
 463               havedisabled = 1;
 464               break;    /* start over */
 465             }
 466
 467           assert(solv->decisionq_why.elements[i] > 0);
 468
 469           /*
 470            * conflict with a pkg rule ?
 471            */
 472           if (solv->decisionq_why.elements[i] < solv->pkgrules_end)
 473             {
 474               if (record_proof)
 475                 {
 476                   queue_push(&solv->problems, solv->learnt_pool.count);
 477                   queue_push(&solv->learnt_pool, ri);
 478                   queue_push(&solv->learnt_pool, solv->decisionq_why.elements[i]);
 479                   queue_push(&solv->learnt_pool, 0);
 480                 }
 481               else
 482                 queue_push(&solv->problems, 0);
 483               assert(v > 0 || v == -SYSTEMSOLVABLE);
 484               POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "conflict with pkg rule, disabling rule #%d\n", ri);
 485               if (ri >= solv->jobrules && ri < solv->jobrules_end)
 486                 v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
 487               else
 488                 v = ri;
 489               queue_push(&solv->problems, v);
 490               queue_push(&solv->problems, 0);
 491               if (v >= solv->featurerules && v < solv->updaterules_end)
 492                 {
 493                   if (solv->allowuninstall || solv->allowuninstall_all || solv->allowuninstallmap.size)
 494                     if (autouninstall(solv, solv->problems.elements + oldproblemcount + 1) != 0)
 495                       {
 496                         solv->problems.count = oldproblemcount;
 497                         havedisabled = 1;
 498                         break;  /* start over */
 499                       }
 500                 }
 501               solver_disableproblem(solv, v);
 502               havedisabled = 1;
 503               break;    /* start over */
 504             }
 505
 506           /*
 507            * conflict with another job or update/feature rule
 508            */
 509
 510           /* record proof */
 511           if (record_proof)
 512             {
 513               queue_push(&solv->problems, solv->learnt_pool.count);
 514               queue_push(&solv->learnt_pool, ri);
 515               queue_push(&solv->learnt_pool, solv->decisionq_why.elements[i]);
 516               queue_push(&solv->learnt_pool, 0);
 517             }
 518           else
 519             queue_push(&solv->problems, 0);
 520
 521           POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "conflicting update/job assertions over literal %d\n", vv);
 522
 523           /*
 524            * push all of our rules (can only be feature or job rules)
 525            * asserting this literal on the problem stack
 526            */
 527           for (i = solv->featurerules, rr = solv->rules + i; i < solv->learntrules; i++, rr++)
 528             {
 529               if (rr->d < 0                          /* disabled */
 530                   || rr->w2)                         /*  or no assertion */
 531                 continue;
 532               if (rr->p != vv                        /* not affecting the literal */
 533                   && rr->p != -vv)
 534                 continue;
 535               if (solv->weakrulemap.size && MAPTST(&solv->weakrulemap, i))     /* weak: silently ignore */
 536                 continue;
 537
 538               POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, " - disabling rule #%d\n", i);
 539               solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE, solv->rules + i);
 540
 541               v = i;
 542               if (i >= solv->jobrules && i < solv->jobrules_end)
 543                 v = -(solv->ruletojob.elements[i - solv->jobrules] + 1);
 544               queue_push(&solv->problems, v);
 545             }
 546           queue_push(&solv->problems, 0);
 547
 548           if (solv->allowuninstall || solv->allowuninstall_all || solv->allowuninstallmap.size)
 549             if (autouninstall(solv, solv->problems.elements + oldproblemcount + 1) != 0)
 550               {
 551                 solv->problems.count = oldproblemcount;
 552                 havedisabled = 1;
 553                 break;  /* start over */
 554               }
 555
 556           for (i = oldproblemcount + 1; i < solv->problems.count - 1; i++)
 557             solver_disableproblem(solv, solv->problems.elements[i]);
 558           havedisabled = 1;
 559           break;        /* start over */
 560         }
 561       if (ii < solv->ruleassertions.count)
 562         continue;
 563
 564       /*
 565        * phase 2: now do the weak assertions
 566        */
 567       if (!solv->weakrulemap.size)
 568         break;                          /* no weak rules, no phase 2 */
 569       for (ii = 0; ii < solv->ruleassertions.count; ii++)
 570         {
 571           ri = solv->ruleassertions.elements[ii];
 572           r = solv->rules + ri;
 573           if (r->d < 0 || r->w2)                         /* disabled or no assertion */
 574             continue;
 575           if (ri >= solv->learntrules || !MAPTST(&solv->weakrulemap, ri))       /* skip non-weak */
 576             continue;
 577           v = r->p;
 578           vv = v > 0 ? v : -v;
 579
 580           if (!solv->decisionmap[vv])          /* if not yet decided */
 581             {
 582               queue_push(&solv->decisionq, v);
 583               queue_push(&solv->decisionq_why, r - solv->rules);
 584               solv->decisionmap[vv] = v > 0 ? 1 : -1;
 585               IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
 586                 {
 587                   Solvable *s = solv->pool->solvables + vv;
 588                   if (v < 0)
 589                     POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "conflicting %s (weak assertion)\n", pool_solvable2str(solv->pool, s));
 590                   else
 591                     POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "installing  %s (weak assertion)\n", pool_solvable2str(solv->pool, s));
 592                 }
 593               continue;
 594             }
 595           /* check against previous decision: is there a conflict? */
 596           if (v > 0 && solv->decisionmap[vv] > 0)
 597             continue;
 598           if (v < 0 && solv->decisionmap[vv] < 0)
 599             continue;
 600
 601           POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "assertion conflict, but I am weak, disabling ");
 602           solver_printrule(solv, SOLV_DEBUG_UNSOLVABLE, r);
 603
 604           if (ri >= solv->jobrules && ri < solv->jobrules_end)
 605             v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
 606           else
 607             v = ri;
 608           solver_disableproblem(solv, v);
 609           if (v < 0)
 610             solver_reenablepolicyrules(solv, -v);
 611           havedisabled = 1;
 612           break;        /* start over */
 613         }
 614       if (ii == solv->ruleassertions.count)
 615         break;  /* finished! */
 616     }
 617 }
 618
 619
 620 /********************************************************************/
 621 /* watches */
 622
 623
 624 /*-------------------------------------------------------------------
 625  * makewatches
 626  *
 627  * initial setup for all watches
 628  */
 629
 630 static void
 631 makewatches(Solver *solv)
 632 {
 633   Rule *r;
 634   int i;
 635   int nsolvables = solv->pool->nsolvables;
 636
 637   solv_free(solv->watches);
 638   /* lower half for removals, upper half for installs */
 639   solv->watches = solv_calloc(2 * nsolvables, sizeof(Id));
 640   for (i = 1, r = solv->rules + solv->nrules - 1; i < solv->nrules; i++, r--)
 641     {
 642       if (!r->w2)               /* assertions do not need watches */
 643         continue;
 644
 645       /* see addwatches_rule(solv, r) */
 646       r->n1 = solv->watches[nsolvables + r->w1];
 647       solv->watches[nsolvables + r->w1] = r - solv->rules;
 648
 649       r->n2 = solv->watches[nsolvables + r->w2];
 650       solv->watches[nsolvables + r->w2] = r - solv->rules;
 651     }
 652 }
 653
 654
 655 /*-------------------------------------------------------------------
 656  *
 657  * add watches (for a new learned rule)
 658  * sets up watches for a single rule
 659  *
 660  * see also makewatches() above.
 661  */
 662
 663 static inline void
 664 addwatches_rule(Solver *solv, Rule *r)
 665 {
 666   int nsolvables = solv->pool->nsolvables;
 667
 668   r->n1 = solv->watches[nsolvables + r->w1];
 669   solv->watches[nsolvables + r->w1] = r - solv->rules;
 670
 671   r->n2 = solv->watches[nsolvables + r->w2];
 672   solv->watches[nsolvables + r->w2] = r - solv->rules;
 673 }
 674
 675
 676 /********************************************************************/
 677 /*
 678  * rule propagation
 679  */
 680
 681
 682 /* shortcuts to check if a literal (positive or negative) assignment
 683  * evaluates to 'true' or 'false'
 684  */
 685 #define DECISIONMAP_TRUE(p) ((p) > 0 ? (decisionmap[p] > 0) : (decisionmap[-p] < 0))
 686 #define DECISIONMAP_FALSE(p) ((p) > 0 ? (decisionmap[p] < 0) : (decisionmap[-p] > 0))
 687 #define DECISIONMAP_UNDEF(p) (decisionmap[(p) > 0 ? (p) : -(p)] == 0)
 688
 689 /*-------------------------------------------------------------------
 690  *
 691  * propagate
 692  *
 693  * make decision and propagate to all rules
 694  *
 695  * Evaluate each term affected by the decision (linked through watches).
 696  * If we find unit rules we make new decisions based on them.
 697  *
 698  * return : 0 = everything is OK
 699  *          rule = conflict found in this rule
 700  */
 701
 702 static Rule *
 703 propagate(Solver *solv, int level)
 704 {
 705   Pool *pool = solv->pool;
 706   Id *rp, *next_rp;           /* rule pointer, next rule pointer in linked list */
 707   Rule *r;                    /* rule */
 708   Id p, pkg, other_watch;
 709   Id *dp;
 710   Id *decisionmap = solv->decisionmap;
 711   Id *watches = solv->watches + pool->nsolvables;   /* place ptr in middle */
 712
 713   POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "----- propagate -----\n");
 714
 715   /* foreach non-propagated decision */
 716   while (solv->propagate_index < solv->decisionq.count)
 717     {
 718       /*
 719        * 'pkg' was just decided
 720        * negate because our watches trigger if literal goes FALSE
 721        */
 722       pkg = -solv->decisionq.elements[solv->propagate_index++];
 723
 724       IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
 725         {
 726           POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "propagate for decision %d level %d\n", -pkg, level);
 727           solver_printruleelement(solv, SOLV_DEBUG_PROPAGATE, 0, -pkg);
 728         }
 729
 730       /* foreach rule where 'pkg' is now FALSE */
 731       for (rp = watches + pkg; *rp; rp = next_rp)
 732         {
 733           r = solv->rules + *rp;
 734           if (r->d < 0)
 735             {
 736               /* rule is disabled, goto next */
 737               if (pkg == r->w1)
 738                 next_rp = &r->n1;
 739               else
 740                 next_rp = &r->n2;
 741               continue;
 742             }
 743
 744           IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
 745             {
 746               POOL_DEBUG(SOLV_DEBUG_PROPAGATE,"  watch triggered ");
 747               solver_printrule(solv, SOLV_DEBUG_PROPAGATE, r);
 748             }
 749
 750           /*
 751            * 'pkg' was just decided (was set to FALSE), so this rule
 752            * may now be unit.
 753            */
 754           /* find the other watch */
 755           if (pkg == r->w1)
 756             {
 757               other_watch = r->w2;
 758               next_rp = &r->n1;
 759             }
 760           else
 761             {
 762               other_watch = r->w1;
 763               next_rp = &r->n2;
 764             }
 765
 766           /*
 767            * if the other watch is true we have nothing to do
 768            */
 769           if (DECISIONMAP_TRUE(other_watch))
 770             continue;
 771
 772           /*
 773            * The other literal is FALSE or UNDEF
 774            *
 775            */
 776
 777           if (r->d)
 778             {
 779               /* Not a binary clause, try to move our watch.
 780                *
 781                * Go over all literals and find one that is
 782                *   not other_watch
 783                *   and not FALSE
 784                *
 785                * (TRUE is also ok, in that case the rule is fulfilled)
 786                * As speed matters here we do not use the FOR_RULELITERALS
 787                * macro.
 788                */
 789               if (r->p                                /* we have a 'p' */
 790                   && r->p != other_watch              /* which is not watched */
 791                   && !DECISIONMAP_FALSE(r->p))        /* and not FALSE */
 792                 {
 793                   p = r->p;
 794                 }
 795               else                                    /* go find a 'd' to make 'true' */
 796                 {
 797                   /* foreach p in 'd'
 798                      we just iterate sequentially, doing it in another order just changes the order of decisions, not the decisions itself
 799                    */
 800                   for (dp = pool->whatprovidesdata + r->d; (p = *dp++) != 0;)
 801                     {
 802                       if (p != other_watch              /* which is not watched */
 803                           && !DECISIONMAP_FALSE(p))     /* and not FALSE */
 804                         break;
 805                     }
 806                 }
 807
 808               if (p)
 809                 {
 810                   /*
 811                    * if we found some p that is UNDEF or TRUE, move
 812                    * watch to it
 813                    */
 814                   IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
 815                     {
 816                       if (p > 0)
 817                         POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "    -> move w%d to %s\n", (pkg == r->w1 ? 1 : 2), pool_solvid2str(pool, p));
 818                       else
 819                         POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "    -> move w%d to !%s\n", (pkg == r->w1 ? 1 : 2), pool_solvid2str(pool, -p));
 820                     }
 821
 822                   *rp = *next_rp;
 823                   next_rp = rp;
 824
 825                   if (pkg == r->w1)
 826                     {
 827                       r->w1 = p;
 828                       r->n1 = watches[p];
 829                     }
 830                   else
 831                     {
 832                       r->w2 = p;
 833                       r->n2 = watches[p];
 834                     }
 835                   watches[p] = r - solv->rules;
 836                   continue;
 837                 }
 838               /* search failed, thus all unwatched literals are FALSE */
 839
 840             } /* not binary */
 841
 842           /*
 843            * unit clause found, set literal other_watch to TRUE
 844            */
 845
 846           if (DECISIONMAP_FALSE(other_watch))      /* check if literal is FALSE */
 847             return r;                              /* eek, a conflict! */
 848
 849           IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
 850             {
 851               POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "  unit ");
 852               solver_printrule(solv, SOLV_DEBUG_PROPAGATE, r);
 853             }
 854
 855           if (other_watch > 0)
 856             decisionmap[other_watch] = level;    /* install! */
 857           else
 858             decisionmap[-other_watch] = -level;  /* remove! */
 859
 860           queue_push(&solv->decisionq, other_watch);
 861           queue_push(&solv->decisionq_why, r - solv->rules);
 862
 863           IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
 864             {
 865               if (other_watch > 0)
 866                 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "    -> decided to install %s\n", pool_solvid2str(pool, other_watch));
 867               else
 868                 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "    -> decided to conflict %s\n", pool_solvid2str(pool, -other_watch));
 869             }
 870
 871         } /* foreach rule involving 'pkg' */
 872
 873     } /* while we have non-decided decisions */
 874
 875   POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "----- propagate end-----\n");
 876
 877   return 0;     /* all is well */
 878 }
 879
 880
 881 /********************************************************************/
 882 /* Analysis */
 883
 884 /*-------------------------------------------------------------------
 885  *
 886  * revert
 887  * revert decisionq to a level
 888  */
 889
 890 static void
 891 revert(Solver *solv, int level)
 892 {
 893   Pool *pool = solv->pool;
 894   Id v, vv;
 895   while (solv->decisionq.count)
 896     {
 897       v = solv->decisionq.elements[solv->decisionq.count - 1];
 898       vv = v > 0 ? v : -v;
 899       if (solv->decisionmap[vv] <= level && solv->decisionmap[vv] >= -level)
 900         break;
 901       POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "reverting decision %d at %d\n", v, solv->decisionmap[vv]);
 902       solv->decisionmap[vv] = 0;
 903       solv->decisionq.count--;
 904       solv->decisionq_why.count--;
 905       solv->propagate_index = solv->decisionq.count;
 906     }
 907   while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] >= level)
 908     solv->branches.count -= solv->branches.elements[solv->branches.count - 2];
 909   if (solv->recommends_index > solv->decisionq.count)
 910     solv->recommends_index = -1;        /* rebuild recommends/suggests maps */
 911   solv->decisionq_reason.count = level + 1;
 912 }
 913
 914 /*-------------------------------------------------------------------
 915  *
 916  * watch2onhighest - put watch2 on literal with highest level
 917  */
 918
 919 static inline void
 920 watch2onhighest(Solver *solv, Rule *r)
 921 {
 922   int l, wl = 0;
 923   Id d, v, *dp;
 924
 925   d = r->d < 0 ? -r->d - 1 : r->d;
 926   if (!d)
 927     return;     /* binary rule, both watches are set */
 928   dp = solv->pool->whatprovidesdata + d;
 929   while ((v = *dp++) != 0)
 930     {
 931       l = solv->decisionmap[v < 0 ? -v : v];
 932       if (l < 0)
 933         l = -l;
 934       if (l > wl)
 935         {
 936           r->w2 = dp[-1];
 937           wl = l;
 938         }
 939     }
 940 }
 941
 942
 943 /*-------------------------------------------------------------------
 944  *
 945  * analyze
 946  *   and learn
 947  */
 948
 949 static int
 950 analyze(Solver *solv, int level, Rule *c, Rule **lrp)
 951 {
 952   Pool *pool = solv->pool;
 953   Queue q;
 954   Rule *r;
 955   Id q_buf[8];
 956   int rlevel = 1;
 957   Map seen;             /* global? */
 958   Id p = 0, pp, v, vv, why;
 959   int l, i, idx;
 960   int num = 0, l1num = 0;
 961   int learnt_why = solv->learnt_pool.count;
 962   Id *decisionmap = solv->decisionmap;
 963
 964   queue_init_buffer(&q, q_buf, sizeof(q_buf)/sizeof(*q_buf));
 965
 966   POOL_DEBUG(SOLV_DEBUG_ANALYZE, "ANALYZE at %d ----------------------\n", level);
 967   map_init(&seen, pool->nsolvables);
 968   idx = solv->decisionq.count;
 969   for (;;)
 970     {
 971       IF_POOLDEBUG (SOLV_DEBUG_ANALYZE)
 972         solver_printruleclass(solv, SOLV_DEBUG_ANALYZE, c);
 973       queue_push(&solv->learnt_pool, c - solv->rules);
 974       FOR_RULELITERALS(v, pp, c)
 975         {
 976           if (DECISIONMAP_TRUE(v))      /* the one true literal */
 977             continue;
 978           vv = v > 0 ? v : -v;
 979           if (MAPTST(&seen, vv))
 980             continue;
 981           MAPSET(&seen, vv);            /* mark that we also need to look at this literal */
 982           l = solv->decisionmap[vv];
 983           if (l < 0)
 984             l = -l;
 985           if (l == 1)
 986             l1num++;                    /* need to do this one in level1 pass */
 987           else if (l == level)
 988             num++;                      /* need to do this one as well */
 989           else
 990             {
 991               queue_push(&q, v);        /* not level1 or conflict level, add to new rule */
 992               if (l > rlevel)
 993                 rlevel = l;
 994             }
 995         }
 996 l1retry:
 997       if (!num && !--l1num)
 998         break;  /* all literals done */
 999
1000       /* find the next literal to investigate */
1001       /* (as num + l1num > 0, we know that we'll always find one) */
1002       for (;;)
1003         {
1004           assert(idx > 0);
1005           v = solv->decisionq.elements[--idx];
1006           vv = v > 0 ? v : -v;
1007           if (MAPTST(&seen, vv))
1008             break;
1009         }
1010       MAPCLR(&seen, vv);
1011
1012       if (num && --num == 0)
1013         {
1014           /* done with normal literals, now start level 1 literal processing */
1015           p = -v;       /* so that v doesn't get lost */
1016           if (!l1num)
1017             break;
1018           POOL_DEBUG(SOLV_DEBUG_ANALYZE, "got %d involved level 1 decisions\n", l1num);
1019           /* clear non-l1 bits from seen map */
1020           for (i = 0; i < q.count; i++)
1021             {
1022               v = q.elements[i];
1023               MAPCLR(&seen, v > 0 ? v : -v);
1024             }
1025           /* only level 1 marks left in seen map */
1026           l1num++;      /* as l1retry decrements it */
1027           goto l1retry;
1028         }
1029
1030       why = solv->decisionq_why.elements[idx];
1031       if (why <= 0)     /* just in case, maybe for SYSTEMSOLVABLE */
1032         goto l1retry;
1033       c = solv->rules + why;
1034     }
1035   map_free(&seen);
1036   assert(p != 0);
1037   assert(rlevel > 0 && rlevel < level);
1038   IF_POOLDEBUG (SOLV_DEBUG_ANALYZE)
1039     {
1040       POOL_DEBUG(SOLV_DEBUG_ANALYZE, "learned rule for level %d (am %d)\n", rlevel, level);
1041       solver_printruleelement(solv, SOLV_DEBUG_ANALYZE, 0, p);
1042       for (i = 0; i < q.count; i++)
1043         solver_printruleelement(solv, SOLV_DEBUG_ANALYZE, 0, q.elements[i]);
1044     }
1045   /* push end marker on learnt reasons stack */
1046   queue_push(&solv->learnt_pool, 0);
1047   solv->stats_learned++;
1048
1049   POOL_DEBUG(SOLV_DEBUG_ANALYZE, "reverting decisions (level %d -> %d)\n", level, rlevel);
1050   level = rlevel;
1051   revert(solv, level);
1052   if (q.count < 2)
1053     {
1054       Id d = q.count ? q.elements[0] : 0;
1055       queue_free(&q);
1056       r = solver_addrule(solv, p, d, 0);
1057     }
1058   else
1059     {
1060       Id d = pool_queuetowhatprovides(pool, &q);
1061       queue_free(&q);
1062       r = solver_addrule(solv, p, 0, d);
1063     }
1064   assert(solv->learnt_why.count == (r - solv->rules) - solv->learntrules);
1065   queue_push(&solv->learnt_why, learnt_why);
1066   if (r->w2)
1067     {
1068       /* needs watches */
1069       watch2onhighest(solv, r);
1070       addwatches_rule(solv, r);
1071     }
1072   else
1073     {
1074       /* rule is an assertion */
1075       queue_push(&solv->ruleassertions, r - solv->rules);
1076     }
1077   *lrp = r;
1078   return level;
1079 }
1080
1081
1082 /*-------------------------------------------------------------------
1083  *
1084  * solver_reset
1085  *
1086  * reset all solver decisions
1087  * called after rules have been enabled/disabled
1088  */
1089
1090 void
1091 solver_reset(Solver *solv)
1092 {
1093   int i;
1094   Id v;
1095
1096   /* rewind all decisions */
1097   for (i = solv->decisionq.count - 1; i >= 0; i--)
1098     {
1099       v = solv->decisionq.elements[i];
1100       solv->decisionmap[v > 0 ? v : -v] = 0;
1101     }
1102   queue_empty(&solv->decisionq_why);
1103   queue_empty(&solv->decisionq);
1104   queue_empty(&solv->decisionq_reason);
1105   solv->recommends_index = -1;
1106   solv->propagate_index = 0;
1107   queue_empty(&solv->branches);
1108
1109   /* adapt learnt rule status to new set of enabled/disabled rules */
1110   enabledisablelearntrules(solv);
1111 }
1112
1113
1114 /*-------------------------------------------------------------------
1115  *
1116  * analyze_unsolvable_rule
1117  *
1118  * recursion helper used by analyze_unsolvable
1119  */
1120
1121 static void
1122 analyze_unsolvable_rule(Solver *solv, Rule *r, Id *lastweakp, Map *rseen)
1123 {
1124   Pool *pool = solv->pool;
1125   int i;
1126   Id why = r - solv->rules;
1127
1128   IF_POOLDEBUG (SOLV_DEBUG_UNSOLVABLE)
1129     solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE, r);
1130   if (solv->learntrules && why >= solv->learntrules)
1131     {
1132       if (MAPTST(rseen, why - solv->learntrules))
1133         return;
1134       MAPSET(rseen, why - solv->learntrules);
1135       for (i = solv->learnt_why.elements[why - solv->learntrules]; solv->learnt_pool.elements[i]; i++)
1136         if (solv->learnt_pool.elements[i] > 0)
1137           analyze_unsolvable_rule(solv, solv->rules + solv->learnt_pool.elements[i], lastweakp, rseen);
1138       return;
1139     }
1140   if (solv->weakrulemap.size && MAPTST(&solv->weakrulemap, why))
1141     if (!*lastweakp || why > *lastweakp)
1142       *lastweakp = why;
1143   /* do not add pkg rules to problem */
1144   if (why < solv->pkgrules_end)
1145     return;
1146   /* turn rule into problem */
1147   if (why >= solv->jobrules && why < solv->jobrules_end)
1148     why = -(solv->ruletojob.elements[why - solv->jobrules] + 1);
1149   /* normalize dup/infarch rules */
1150   if (why > solv->infarchrules && why < solv->infarchrules_end)
1151     {
1152       Id name = pool->solvables[-solv->rules[why].p].name;
1153       while (why > solv->infarchrules && pool->solvables[-solv->rules[why - 1].p].name == name)
1154         why--;
1155     }
1156   if (why > solv->duprules && why < solv->duprules_end)
1157     {
1158       Id name = pool->solvables[-solv->rules[why].p].name;
1159       while (why > solv->duprules && pool->solvables[-solv->rules[why - 1].p].name == name)
1160         why--;
1161     }
1162
1163   /* return if problem already countains our rule */
1164   if (solv->problems.count)
1165     {
1166       for (i = solv->problems.count - 1; i >= 0; i--)
1167         if (solv->problems.elements[i] == 0)    /* end of last problem reached? */
1168           break;
1169         else if (solv->problems.elements[i] == why)
1170           return;
1171     }
1172   queue_push(&solv->problems, why);
1173 }
1174
1175
1176 /*-------------------------------------------------------------------
1177  *
1178  * analyze_unsolvable (called from setpropagatelearn)
1179  *
1180  * We know that the problem is not solvable. Record all involved
1181  * rules (i.e. the "proof") into solv->learnt_pool.
1182  * Record the learnt pool index and all non-pkg rules into
1183  * solv->problems. (Our solutions to fix the problems are to
1184  * disable those rules.)
1185  *
1186  * If the proof contains at least one weak rule, we disable the
1187  * last of them.
1188  *
1189  * Otherwise we return -1 if disablerules is not set or disable
1190  * _all_ of the problem rules and return 0.
1191  *
1192  * return:  0 - disabled some rules, try again
1193  *         -1 - hopeless
1194  */
1195
1196 static int
1197 analyze_unsolvable(Solver *solv, Rule *cr, int disablerules)
1198 {
1199   Pool *pool = solv->pool;
1200   Rule *r;
1201   Map involved;         /* global to speed things up? */
1202   Map rseen;
1203   Id pp, v, vv, why;
1204   int i, idx;
1205   Id *decisionmap = solv->decisionmap;
1206   int oldproblemcount;
1207   int oldlearntpoolcount;
1208   Id lastweak;
1209   int record_proof = 1;
1210
1211   POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "ANALYZE UNSOLVABLE ----------------------\n");
1212   solv->stats_unsolvable++;
1213   oldproblemcount = solv->problems.count;
1214   oldlearntpoolcount = solv->learnt_pool.count;
1215
1216   /* make room for proof index */
1217   /* must update it later, as analyze_unsolvable_rule would confuse
1218    * it with a rule index if we put the real value in already */
1219   queue_push(&solv->problems, 0);
1220
1221   r = cr;
1222   map_init(&involved, pool->nsolvables);
1223   map_init(&rseen, solv->learntrules ? solv->nrules - solv->learntrules : 0);
1224   if (record_proof)
1225     queue_push(&solv->learnt_pool, r - solv->rules);
1226   lastweak = 0;
1227   analyze_unsolvable_rule(solv, r, &lastweak, &rseen);
1228   FOR_RULELITERALS(v, pp, r)
1229     {
1230       if (DECISIONMAP_TRUE(v))  /* the one true literal */
1231           continue;
1232       vv = v > 0 ? v : -v;
1233       MAPSET(&involved, vv);
1234     }
1235   idx = solv->decisionq.count;
1236   while (idx > 0)
1237     {
1238       v = solv->decisionq.elements[--idx];
1239       vv = v > 0 ? v : -v;
1240       if (!MAPTST(&involved, vv) || vv == SYSTEMSOLVABLE)
1241         continue;
1242       why = solv->decisionq_why.elements[idx];
1243       assert(why > 0);
1244       if (record_proof)
1245         queue_push(&solv->learnt_pool, why);
1246       r = solv->rules + why;
1247       analyze_unsolvable_rule(solv, r, &lastweak, &rseen);
1248       FOR_RULELITERALS(v, pp, r)
1249         {
1250           if (DECISIONMAP_TRUE(v))      /* the one true literal */
1251               continue;
1252           vv = v > 0 ? v : -v;
1253           MAPSET(&involved, vv);
1254         }
1255     }
1256   map_free(&involved);
1257   map_free(&rseen);
1258   queue_push(&solv->problems, 0);       /* mark end of this problem */
1259
1260   if (lastweak)
1261     {
1262       /* disable last weak rule */
1263       solv->problems.count = oldproblemcount;
1264       solv->learnt_pool.count = oldlearntpoolcount;
1265       if (lastweak >= solv->jobrules && lastweak < solv->jobrules_end)
1266         v = -(solv->ruletojob.elements[lastweak - solv->jobrules] + 1);
1267       else
1268         v = lastweak;
1269       POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "disabling ");
1270       solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE, solv->rules + lastweak);
1271       if (lastweak >= solv->choicerules && lastweak < solv->choicerules_end)
1272         solver_disablechoicerules(solv, solv->rules + lastweak);
1273       solver_disableproblem(solv, v);
1274       if (v < 0)
1275         solver_reenablepolicyrules(solv, -v);
1276       solver_reset(solv);
1277       return 0;
1278     }
1279
1280   if (solv->allowuninstall || solv->allowuninstall_all || solv->allowuninstallmap.size)
1281     if (autouninstall(solv, solv->problems.elements + oldproblemcount + 1) != 0)
1282       {
1283         solv->problems.count = oldproblemcount;
1284         solv->learnt_pool.count = oldlearntpoolcount;
1285         solver_reset(solv);
1286         return 0;
1287       }
1288
1289   /* finish proof */
1290   if (record_proof)
1291     {
1292       queue_push(&solv->learnt_pool, 0);
1293       solv->problems.elements[oldproblemcount] = oldlearntpoolcount;
1294     }
1295
1296   /* + 2: index + trailing zero */
1297   if (disablerules && oldproblemcount + 2 < solv->problems.count)
1298     {
1299       for (i = oldproblemcount + 1; i < solv->problems.count - 1; i++)
1300         solver_disableproblem(solv, solv->problems.elements[i]);
1301       /* XXX: might want to enable all weak rules again */
1302       solver_reset(solv);
1303       return 0;
1304     }
1305   POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "UNSOLVABLE\n");
1306   return -1;
1307 }
1308
1309
1310 /*-------------------------------------------------------------------
1311  *
1312  * setpropagatelearn
1313  *
1314  * add free decision (solvable to install) to decisionq
1315  * increase level and propagate decision
1316  * return if no conflict.
1317  *
1318  * in conflict case, analyze conflict rule, add resulting
1319  * rule to learnt rule set, make decision from learnt
1320  * rule (always unit) and re-propagate.
1321  *
1322  * returns the new solver level or -1 if unsolvable
1323  *
1324  */
1325
1326 static int
1327 setpropagatelearn(Solver *solv, int level, Id decision, int disablerules, Id ruleid, Id reason)
1328 {
1329   Pool *pool = solv->pool;
1330   Rule *r, *lr;
1331
1332   if (decision)
1333     {
1334       level++;
1335       if (decision > 0)
1336         solv->decisionmap[decision] = level;
1337       else
1338         solv->decisionmap[-decision] = -level;
1339       queue_push(&solv->decisionq, decision);
1340       queue_push(&solv->decisionq_why, -ruleid);        /* <= 0 -> free decision */
1341       queue_push(&solv->decisionq_reason, reason);
1342     }
1343   assert(ruleid >= 0 && level > 0);
1344   for (;;)
1345     {
1346       r = propagate(solv, level);
1347       if (!r)
1348         break;
1349       if (level == 1)
1350         return analyze_unsolvable(solv, r, disablerules);
1351       POOL_DEBUG(SOLV_DEBUG_ANALYZE, "conflict with rule #%d\n", (int)(r - solv->rules));
1352       level = analyze(solv, level, r, &lr);
1353       /* the new rule is unit by design */
1354       decision = lr->p;
1355       solv->decisionmap[decision > 0 ? decision : -decision] = decision > 0 ? level : -level;
1356       queue_push(&solv->decisionq, decision);
1357       queue_push(&solv->decisionq_why, lr - solv->rules);
1358       IF_POOLDEBUG (SOLV_DEBUG_ANALYZE)
1359         {
1360           POOL_DEBUG(SOLV_DEBUG_ANALYZE, "decision: ");
1361           solver_printruleelement(solv, SOLV_DEBUG_ANALYZE, 0, decision);
1362           POOL_DEBUG(SOLV_DEBUG_ANALYZE, "new rule: ");
1363           solver_printrule(solv, SOLV_DEBUG_ANALYZE, lr);
1364         }
1365     }
1366   return level;
1367 }
1368
1369 static void
1370 reorder_dq_for_future_installed(Solver *solv, int level, Queue *dq)
1371 {
1372   Pool *pool = solv->pool;
1373   int i, j, haveone = 0, dqcount = dq->count;
1374   int decisionqcount = solv->decisionq.count;
1375   Id p;
1376   Solvable *s;
1377
1378   /* at the time we process jobrules the installed packages are not kept yet */
1379   /* reorder so that "future-supplemented" packages come first */
1380   FOR_REPO_SOLVABLES(solv->installed, p, s)
1381     {
1382       if (MAPTST(&solv->noupdate, p - solv->installed->start))
1383         continue;
1384       if (solv->decisionmap[p] == 0)
1385         {
1386           if (s->recommends || s->suggests)
1387             queue_push(&solv->decisionq, p);
1388           solv->decisionmap[p] = level + 1;
1389           haveone = 1;
1390         }
1391     }
1392   if (!haveone)
1393     return;
1394   policy_update_recommendsmap(solv);
1395   for (i = 0; i < dqcount; i++)
1396     {
1397       p = dq->elements[i];
1398       if (!(pool->solvables[p].repo == solv->installed || MAPTST(&solv->suggestsmap, p) || solver_is_enhancing(solv, pool->solvables + p)))
1399         {
1400           queue_push(dq, p);
1401           dq->elements[i] = 0;
1402         }
1403     }
1404   dqcount = dq->count;
1405   for (i = 0; i < dqcount; i++)
1406     {
1407       p = dq->elements[i];
1408       if (p && !(pool->solvables[p].repo == solv->installed || MAPTST(&solv->recommendsmap, p) || solver_is_supplementing(solv, pool->solvables + p)))
1409         {
1410           queue_push(dq, p);
1411           dq->elements[i] = 0;
1412         }
1413     }
1414   for (i = j = 0; i < dq->count; i++)
1415     if (dq->elements[i])
1416       dq->elements[j++] = dq->elements[i];
1417   queue_truncate(dq, j);
1418   FOR_REPO_SOLVABLES(solv->installed, p, s)
1419     if (solv->decisionmap[p] == level + 1)
1420       solv->decisionmap[p] = 0;
1421   if (solv->decisionq.count != decisionqcount)
1422     {
1423       solv->recommends_index = -1;
1424       queue_truncate(&solv->decisionq, decisionqcount);
1425     }
1426   /* but obey favored maps */
1427   policy_prefer_favored(solv, dq);
1428 }
1429
1430 /*-------------------------------------------------------------------
1431  *
1432  * branch handling
1433  */
1434
1435 static void
1436 createbranch(Solver *solv, int level, Queue *dq, Id p, Id data)
1437 {
1438   Pool *pool = solv->pool;
1439   int i;
1440   IF_POOLDEBUG (SOLV_DEBUG_POLICY)
1441     {
1442       POOL_DEBUG (SOLV_DEBUG_POLICY, "creating a branch:\n");
1443       for (i = 0; i < dq->count; i++)
1444         POOL_DEBUG (SOLV_DEBUG_POLICY, "  - %s\n", pool_solvid2str(pool, dq->elements[i]));
1445     }
1446   queue_push(&solv->branches, -dq->elements[0]);
1447   for (i = 1; i < dq->count; i++)
1448     queue_push(&solv->branches, dq->elements[i]);
1449   queue_push2(&solv->branches, p, data);
1450   queue_push2(&solv->branches, dq->count + 4, level);
1451 }
1452
1453 static int
1454 takebranch(Solver *solv, int pos, int end, const char *msg, int disablerules)
1455 {
1456   Pool *pool = solv->pool;
1457   int level;
1458   Id p, why, reason;
1459 #if 0
1460   {
1461     int i;
1462     printf("branch group level %d [%d-%d] %d %d:\n", solv->branches.elements[end - 1], start, end, solv->branches.elements[end - 4], solv->branches.elements[end - 3]);
1463     for (i = end - solv->branches.elements[end - 2]; i < end - 4; i++)
1464       printf("%c %c%s\n", i == pos ? 'x' : ' ', solv->branches.elements[i] >= 0 ? ' ' : '-', pool_solvid2str(pool, solv->branches.elements[i] >= 0 ? solv->branches.elements[i] : -solv->branches.elements[i]));
1465   }
1466 #endif
1467   level = solv->branches.elements[end - 1];
1468   p = solv->branches.elements[pos];
1469   solv->branches.elements[pos] = -p;
1470   POOL_DEBUG(SOLV_DEBUG_SOLVER, "%s %d -> %d with %s\n", msg, solv->decisionmap[p], level, pool_solvid2str(pool, p));
1471   /* hack: set level to zero so that revert does not remove the branch */
1472   solv->branches.elements[end - 1] = 0;
1473   revert(solv, level);
1474   solv->branches.elements[end - 1] = level;
1475   /* hack: revert simply sets the count, so we can still access the reverted elements */
1476   why = -solv->decisionq_why.elements[solv->decisionq_why.count];
1477   assert(why >= 0);
1478   reason = solv->decisionq_reason.elements[level + 1];
1479   return setpropagatelearn(solv, level, p, disablerules, why, reason);
1480 }
1481
1482 /*-------------------------------------------------------------------
1483  *
1484  * select and install
1485  *
1486  * install best package from the queue. We add an extra package, inst, if
1487  * provided. See comment in weak install section.
1488  *
1489  * returns the new solver level or -1 if unsolvable
1490  *
1491  */
1492
1493 static int
1494 selectandinstall(Solver *solv, int level, Queue *dq, int disablerules, Id ruleid, Id reason)
1495 {
1496   Pool *pool = solv->pool;
1497   Id p;
1498
1499   if (dq->count > 1)
1500     policy_filter_unwanted(solv, dq, POLICY_MODE_CHOOSE);
1501   /* if we're resolving rules and didn't resolve the installed packages yet,
1502    * do some special supplements ordering */
1503   if (dq->count > 1 && solv->do_extra_reordering)
1504     reorder_dq_for_future_installed(solv, level, dq);
1505   /* if we have multiple candidates we open a branch */
1506   if (dq->count > 1)
1507     createbranch(solv, level, dq, 0, ruleid);
1508   p = dq->elements[0];
1509   POOL_DEBUG(SOLV_DEBUG_POLICY, "installing %s\n", pool_solvid2str(pool, p));
1510   return setpropagatelearn(solv, level, p, disablerules, ruleid, reason);
1511 }
1512
1513
1514 /********************************************************************/
1515 /* Main solver interface */
1516
1517
1518 /*-------------------------------------------------------------------
1519  *
1520  * solver_create
1521  * create solver structure
1522  *
1523  * pool: all available solvables
1524  * installed: installed Solvables
1525  *
1526  *
1527  * Upon solving, rules are created to flag the Solvables
1528  * of the 'installed' Repo as installed.
1529  */
1530
1531 Solver *
1532 solver_create(Pool *pool)
1533 {
1534   Solver *solv;
1535   solv = (Solver *)solv_calloc(1, sizeof(Solver));
1536   solv->pool = pool;
1537   solv->installed = pool->installed;
1538
1539   solv->allownamechange = 1;
1540
1541   solv->dup_allowdowngrade = 1;
1542   solv->dup_allownamechange = 1;
1543   solv->dup_allowarchchange = 1;
1544   solv->dup_allowvendorchange = 1;
1545
1546   solv->keepexplicitobsoletes = pool->noobsoletesmultiversion ? 0 : 1;
1547
1548   queue_init(&solv->ruletojob);
1549   queue_init(&solv->decisionq);
1550   queue_init(&solv->decisionq_why);
1551   queue_init(&solv->decisionq_reason);
1552   queue_init(&solv->problems);
1553   queue_init(&solv->orphaned);
1554   queue_init(&solv->learnt_why);
1555   queue_init(&solv->learnt_pool);
1556   queue_init(&solv->branches);
1557   queue_init(&solv->weakruleq);
1558   queue_init(&solv->ruleassertions);
1559   queue_init(&solv->addedmap_deduceq);
1560
1561   queue_push(&solv->learnt_pool, 0);    /* so that 0 does not describe a proof */
1562
1563   map_init(&solv->recommendsmap, pool->nsolvables);
1564   map_init(&solv->suggestsmap, pool->nsolvables);
1565   map_init(&solv->noupdate, solv->installed ? solv->installed->end - solv->installed->start : 0);
1566   solv->recommends_index = 0;
1567
1568   solv->decisionmap = (Id *)solv_calloc(pool->nsolvables, sizeof(Id));
1569   solv->nrules = 1;
1570   solv->rules = solv_extend_resize(solv->rules, solv->nrules, sizeof(Rule), RULES_BLOCK);
1571   memset(solv->rules, 0, sizeof(Rule));
1572
1573   return solv;
1574 }
1575
1576
1577
1578 /*-------------------------------------------------------------------
1579  *
1580  * solver_free
1581  */
1582
1583 static inline void
1584 queuep_free(Queue **qp)
1585 {
1586   if (!*qp)
1587     return;
1588   queue_free(*qp);
1589   *qp = solv_free(*qp);
1590 }
1591
1592 static inline void
1593 map_zerosize(Map *m)
1594 {
1595   if (m->size)
1596     {
1597       map_free(m);
1598       map_init(m, 0);
1599     }
1600 }
1601
1602 void
1603 solver_free(Solver *solv)
1604 {
1605   queue_free(&solv->job);
1606   queue_free(&solv->ruletojob);
1607   queue_free(&solv->decisionq);
1608   queue_free(&solv->decisionq_why);
1609   queue_free(&solv->decisionq_reason);
1610   queue_free(&solv->learnt_why);
1611   queue_free(&solv->learnt_pool);
1612   queue_free(&solv->problems);
1613   queue_free(&solv->solutions);
1614   queue_free(&solv->orphaned);
1615   queue_free(&solv->branches);
1616   queue_free(&solv->weakruleq);
1617   queue_free(&solv->ruleassertions);
1618   queue_free(&solv->addedmap_deduceq);
1619   queuep_free(&solv->cleandeps_updatepkgs);
1620   queuep_free(&solv->cleandeps_mistakes);
1621   queuep_free(&solv->update_targets);
1622   queuep_free(&solv->installsuppdepq);
1623   queuep_free(&solv->recommendscplxq);
1624   queuep_free(&solv->suggestscplxq);
1625   queuep_free(&solv->brokenorphanrules);
1626   queuep_free(&solv->favorq);
1627
1628   map_free(&solv->recommendsmap);
1629   map_free(&solv->suggestsmap);
1630   map_free(&solv->noupdate);
1631   map_free(&solv->weakrulemap);
1632   map_free(&solv->multiversion);
1633
1634   map_free(&solv->updatemap);
1635   map_free(&solv->bestupdatemap);
1636   map_free(&solv->fixmap);
1637   map_free(&solv->dupmap);
1638   map_free(&solv->dupinvolvedmap);
1639   map_free(&solv->droporphanedmap);
1640   map_free(&solv->cleandepsmap);
1641   map_free(&solv->allowuninstallmap);
1642   map_free(&solv->favormap);
1643   map_free(&solv->isdisfavormap);
1644
1645   solv_free(solv->decisionmap);
1646   solv_free(solv->rules);
1647   solv_free(solv->watches);
1648   solv_free(solv->obsoletes);
1649   solv_free(solv->obsoletes_data);
1650   solv_free(solv->specialupdaters);
1651   solv_free(solv->choicerules_ref);
1652   solv_free(solv->bestrules_pkg);
1653   solv_free(solv->yumobsrules_info);
1654   solv_free(solv->instbuddy);
1655   solv_free(solv);
1656 }
1657
1658 int
1659 solver_get_flag(Solver *solv, int flag)
1660 {
1661   switch (flag)
1662   {
1663   case SOLVER_FLAG_ALLOW_DOWNGRADE:
1664     return solv->allowdowngrade;
1665   case SOLVER_FLAG_ALLOW_NAMECHANGE:
1666     return solv->allownamechange;
1667   case SOLVER_FLAG_ALLOW_ARCHCHANGE:
1668     return solv->allowarchchange;
1669   case SOLVER_FLAG_ALLOW_VENDORCHANGE:
1670     return solv->allowvendorchange;
1671   case SOLVER_FLAG_ALLOW_UNINSTALL:
1672     return solv->allowuninstall;
1673   case SOLVER_FLAG_NO_UPDATEPROVIDE:
1674     return solv->noupdateprovide;
1675   case SOLVER_FLAG_SPLITPROVIDES:
1676     return solv->dosplitprovides;
1677   case SOLVER_FLAG_IGNORE_RECOMMENDED:
1678     return solv->dontinstallrecommended;
1679   case SOLVER_FLAG_ADD_ALREADY_RECOMMENDED:
1680     return solv->addalreadyrecommended;
1681   case SOLVER_FLAG_NO_INFARCHCHECK:
1682     return solv->noinfarchcheck;
1683   case SOLVER_FLAG_KEEP_EXPLICIT_OBSOLETES:
1684     return solv->keepexplicitobsoletes;
1685   case SOLVER_FLAG_BEST_OBEY_POLICY:
1686     return solv->bestobeypolicy;
1687   case SOLVER_FLAG_NO_AUTOTARGET:
1688     return solv->noautotarget;
1689   case SOLVER_FLAG_DUP_ALLOW_DOWNGRADE:
1690     return solv->dup_allowdowngrade;
1691   case SOLVER_FLAG_DUP_ALLOW_NAMECHANGE:
1692     return solv->dup_allownamechange;
1693   case SOLVER_FLAG_DUP_ALLOW_ARCHCHANGE:
1694     return solv->dup_allowarchchange;
1695   case SOLVER_FLAG_DUP_ALLOW_VENDORCHANGE:
1696     return solv->dup_allowvendorchange;
1697   case SOLVER_FLAG_KEEP_ORPHANS:
1698     return solv->keep_orphans;
1699   case SOLVER_FLAG_BREAK_ORPHANS:
1700     return solv->break_orphans;
1701   case SOLVER_FLAG_FOCUS_INSTALLED:
1702     return solv->focus_installed;
1703   case SOLVER_FLAG_FOCUS_BEST:
1704     return solv->focus_best;
1705   case SOLVER_FLAG_YUM_OBSOLETES:
1706     return solv->do_yum_obsoletes;
1707   case SOLVER_FLAG_NEED_UPDATEPROVIDE:
1708     return solv->needupdateprovide;
1709   case SOLVER_FLAG_URPM_REORDER:
1710     return solv->urpmreorder;
1711   default:
1712     break;
1713   }
1714   return -1;
1715 }
1716
1717 int
1718 solver_set_flag(Solver *solv, int flag, int value)
1719 {
1720   int old = solver_get_flag(solv, flag);
1721   switch (flag)
1722   {
1723   case SOLVER_FLAG_ALLOW_DOWNGRADE:
1724     solv->allowdowngrade = value;
1725     break;
1726   case SOLVER_FLAG_ALLOW_NAMECHANGE:
1727     solv->allownamechange = value;
1728     break;
1729   case SOLVER_FLAG_ALLOW_ARCHCHANGE:
1730     solv->allowarchchange = value;
1731     break;
1732   case SOLVER_FLAG_ALLOW_VENDORCHANGE:
1733     solv->allowvendorchange = value;
1734     break;
1735   case SOLVER_FLAG_ALLOW_UNINSTALL:
1736     solv->allowuninstall = value;
1737     break;
1738   case SOLVER_FLAG_NO_UPDATEPROVIDE:
1739     solv->noupdateprovide = value;
1740     break;
1741   case SOLVER_FLAG_SPLITPROVIDES:
1742     solv->dosplitprovides = value;
1743     break;
1744   case SOLVER_FLAG_IGNORE_RECOMMENDED:
1745     solv->dontinstallrecommended = value;
1746     break;
1747   case SOLVER_FLAG_ADD_ALREADY_RECOMMENDED:
1748     solv->addalreadyrecommended = value;
1749     break;
1750   case SOLVER_FLAG_NO_INFARCHCHECK:
1751     solv->noinfarchcheck = value;
1752     break;
1753   case SOLVER_FLAG_KEEP_EXPLICIT_OBSOLETES:
1754     solv->keepexplicitobsoletes = value;
1755     break;
1756   case SOLVER_FLAG_BEST_OBEY_POLICY:
1757     solv->bestobeypolicy = value;
1758     break;
1759   case SOLVER_FLAG_NO_AUTOTARGET:
1760     solv->noautotarget = value;
1761     break;
1762   case SOLVER_FLAG_DUP_ALLOW_DOWNGRADE:
1763     solv->dup_allowdowngrade = value;
1764     break;
1765   case SOLVER_FLAG_DUP_ALLOW_NAMECHANGE:
1766     solv->dup_allownamechange = value;
1767     break;
1768   case SOLVER_FLAG_DUP_ALLOW_ARCHCHANGE:
1769     solv->dup_allowarchchange = value;
1770     break;
1771   case SOLVER_FLAG_DUP_ALLOW_VENDORCHANGE:
1772     solv->dup_allowvendorchange = value;
1773     break;
1774   case SOLVER_FLAG_KEEP_ORPHANS:
1775     solv->keep_orphans = value;
1776     break;
1777   case SOLVER_FLAG_BREAK_ORPHANS:
1778     solv->break_orphans = value;
1779     break;
1780   case SOLVER_FLAG_FOCUS_INSTALLED:
1781     solv->focus_installed = value;
1782     break;
1783   case SOLVER_FLAG_FOCUS_BEST:
1784     solv->focus_best = value;
1785     break;
1786   case SOLVER_FLAG_YUM_OBSOLETES:
1787     solv->do_yum_obsoletes = value;
1788     break;
1789   case SOLVER_FLAG_NEED_UPDATEPROVIDE:
1790     solv->needupdateprovide = value;
1791     break;
1792   case SOLVER_FLAG_URPM_REORDER:
1793     solv->urpmreorder = value;
1794     break;
1795   default:
1796     break;
1797   }
1798   return old;
1799 }
1800
1801 static int
1802 resolve_jobrules(Solver *solv, int level, int disablerules, Queue *dq)
1803 {
1804   Pool *pool = solv->pool;
1805   int oldlevel = level;
1806   int i, olevel;
1807   Rule *r;
1808
1809   POOL_DEBUG(SOLV_DEBUG_SOLVER, "resolving job rules\n");
1810   for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++)
1811     {
1812       Id l, pp;
1813       if (r->d < 0)             /* ignore disabled rules */
1814         continue;
1815       queue_empty(dq);
1816       FOR_RULELITERALS(l, pp, r)
1817         {
1818           if (l < 0)
1819             {
1820               if (solv->decisionmap[-l] <= 0)
1821                 break;
1822             }
1823           else
1824             {
1825               if (solv->decisionmap[l] > 0)
1826                 break;
1827               if (solv->decisionmap[l] == 0)
1828                 queue_push(dq, l);
1829             }
1830         }
1831       if (l || !dq->count)
1832         continue;
1833       /* prune to installed if not updating */
1834       if (dq->count > 1 && solv->installed && !solv->updatemap_all &&
1835           !(solv->job.elements[solv->ruletojob.elements[i - solv->jobrules]] & SOLVER_ORUPDATE))
1836         {
1837           int j, k;
1838           for (j = k = 0; j < dq->count; j++)
1839             {
1840               Solvable *s = pool->solvables + dq->elements[j];
1841               if (s->repo == solv->installed)
1842                 {
1843                   dq->elements[k++] = dq->elements[j];
1844                   if (solv->updatemap.size && MAPTST(&solv->updatemap, dq->elements[j] - solv->installed->start))
1845                     {
1846                       k = 0;    /* package wants to be updated, do not prune */
1847                       break;
1848                     }
1849                 }
1850             }
1851           if (k)
1852             dq->count = k;
1853         }
1854       olevel = level;
1855       level = selectandinstall(solv, level, dq, disablerules, i, SOLVER_REASON_RESOLVE_JOB);
1856       if (level <= olevel)
1857         {
1858           if (level == olevel)
1859             {
1860               i--;
1861               r--;
1862               continue; /* try something else */
1863             }
1864           if (level < oldlevel)
1865             return level;
1866           /* redo from start of jobrules */
1867           i = solv->jobrules - 1;
1868           r = solv->rules + i;
1869         }
1870     }
1871   return level;
1872 }
1873
1874 static int
1875 cleandeps_check_mistakes(Solver *solv)
1876 {
1877   Pool *pool = solv->pool;
1878   Rule *r;
1879   Id p, pp;
1880   int i;
1881   int mademistake = 0;
1882
1883   if (!solv->cleandepsmap.size)
1884     return 0;
1885   /* check for mistakes */
1886   for (i = solv->installed->start; i < solv->installed->end; i++)
1887     {
1888       if (!MAPTST(&solv->cleandepsmap, i - solv->installed->start))
1889         continue;
1890       r = solv->rules + solv->featurerules + (i - solv->installed->start);
1891       /* a mistake is when the featurerule is true but the updaterule is false */
1892       if (!r->p)
1893         continue;
1894       FOR_RULELITERALS(p, pp, r)
1895         if (p > 0 && solv->decisionmap[p] > 0)
1896           break;
1897       if (!p)
1898         continue;       /* feature rule is not true */
1899       r = solv->rules + solv->updaterules + (i - solv->installed->start);
1900       if (!r->p)
1901         continue;
1902       FOR_RULELITERALS(p, pp, r)
1903         if (p > 0 && solv->decisionmap[p] > 0)
1904           break;
1905       if (p)
1906         continue;       /* update rule is true */
1907       POOL_DEBUG(SOLV_DEBUG_SOLVER, "cleandeps mistake: ");
1908       solver_printruleclass(solv, SOLV_DEBUG_SOLVER, r);
1909       POOL_DEBUG(SOLV_DEBUG_SOLVER, "feature rule: ");
1910       solver_printruleclass(solv, SOLV_DEBUG_SOLVER, solv->rules + solv->featurerules + (i - solv->installed->start));
1911       if (!solv->cleandeps_mistakes)
1912         {
1913           solv->cleandeps_mistakes = solv_calloc(1, sizeof(Queue));
1914           queue_init(solv->cleandeps_mistakes);
1915         }
1916       queue_push(solv->cleandeps_mistakes, i);
1917       MAPCLR(&solv->cleandepsmap, i - solv->installed->start);
1918       solver_reenablepolicyrules_cleandeps(solv, i);
1919       mademistake = 1;
1920     }
1921   return mademistake;
1922 }
1923
1924 static void
1925 prune_to_update_targets(Solver *solv, Id *cp, Queue *q)
1926 {
1927   int i, j;
1928   Id p, *cp2;
1929   for (i = j = 0; i < q->count; i++)
1930     {
1931       p = q->elements[i];
1932       for (cp2 = cp; *cp2; cp2++)
1933         if (*cp2 == p)
1934           {
1935             q->elements[j++] = p;
1936             break;
1937           }
1938     }
1939   queue_truncate(q, j);
1940 }
1941
1942 static int
1943 resolve_installed(Solver *solv, int level, int disablerules, Queue *dq)
1944 {
1945   Pool *pool = solv->pool;
1946   Repo *installed = solv->installed;
1947   int i, n, pass;
1948   int installedpos = solv->installedpos;
1949   Solvable *s;
1950   Id p, pp;
1951   int olevel, origlevel = level;
1952
1953   POOL_DEBUG(SOLV_DEBUG_SOLVER, "resolving installed packages\n");
1954   if (!installedpos)
1955     installedpos = installed->start;
1956   /* we use two passes if we need to update packages
1957    * to create a better user experience */
1958   for (pass = solv->updatemap.size ? 0 : 1; pass < 2; )
1959     {
1960       int passlevel = level;
1961       Id *specialupdaters = solv->specialupdaters;
1962       /* start with installedpos, the position that gave us problems the last time */
1963       for (i = installedpos, n = installed->start; n < installed->end; i++, n++)
1964         {
1965           Rule *r, *rr;
1966           Id d;
1967
1968           if (i == installed->end)
1969             i = installed->start;
1970           s = pool->solvables + i;
1971           if (s->repo != installed)
1972             continue;
1973
1974           if (solv->decisionmap[i] > 0 && (!specialupdaters || !specialupdaters[i - installed->start]))
1975             continue;           /* already decided */
1976           if (!pass && solv->updatemap.size && !MAPTST(&solv->updatemap, i - installed->start))
1977             continue;           /* updates first */
1978           r = solv->rules + solv->updaterules + (i - installed->start);
1979           rr = r;
1980           if (!rr->p || rr->d < 0)      /* disabled -> look at feature rule */
1981             rr -= solv->installed->end - solv->installed->start;
1982           if (!rr->p)           /* identical to update rule? */
1983             rr = r;
1984           if (!rr->p)
1985             continue;           /* orpaned package or pseudo package */
1986
1987           /* check if we should update this package to the latest version
1988            * noupdate is set for erase jobs, in that case we want to deinstall
1989            * the installed package and not replace it with a newer version
1990            * rr->p != i is for dup jobs where the installed package cannot be kept */
1991           if (dq->count)
1992             queue_empty(dq);
1993           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 && rr->p != i)))
1994             {
1995               if (specialupdaters && (d = specialupdaters[i - installed->start]) != 0)
1996                 {
1997                   /* special multiversion handling, make sure best version is chosen */
1998                   if (rr->p == i && solv->decisionmap[i] >= 0)
1999                     queue_push(dq, i);
2000                   while ((p = pool->whatprovidesdata[d++]) != 0)
2001                     if (solv->decisionmap[p] >= 0)
2002                       queue_push(dq, p);
2003                   if (dq->count && solv->update_targets && solv->update_targets->elements[i - installed->start])
2004                     prune_to_update_targets(solv, solv->update_targets->elements + solv->update_targets->elements[i - installed->start], dq);
2005                   if (dq->count)
2006                     {
2007                       policy_filter_unwanted(solv, dq, POLICY_MODE_CHOOSE);
2008                       p = dq->elements[0];
2009                       if (p != i && solv->decisionmap[p] == 0)
2010                         {
2011                           rr = solv->rules + solv->featurerules + (i - solv->installed->start);
2012                           if (!rr->p)           /* update rule == feature rule? */
2013                             rr = rr - solv->featurerules + solv->updaterules;
2014                           dq->count = 1;
2015                         }
2016                       else
2017                         dq->count = 0;
2018                     }
2019                 }
2020               else
2021                 {
2022                   /* update to best package of the update rule */
2023                   FOR_RULELITERALS(p, pp, rr)
2024                     {
2025                       if (solv->decisionmap[p] > 0)
2026                         {
2027                           dq->count = 0;                /* already fulfilled */
2028                           break;
2029                         }
2030                       if (!solv->decisionmap[p])
2031                         queue_push(dq, p);
2032                     }
2033                 }
2034             }
2035           if (dq->count && solv->update_targets && solv->update_targets->elements[i - installed->start])
2036             prune_to_update_targets(solv, solv->update_targets->elements + solv->update_targets->elements[i - installed->start], dq);
2037           /* install best version */
2038           if (dq->count)
2039             {
2040               olevel = level;
2041               level = selectandinstall(solv, level, dq, disablerules, rr - solv->rules, SOLVER_REASON_UPDATE_INSTALLED);
2042               if (level <= olevel)
2043                 {
2044                   if (level < passlevel)
2045                     break;      /* trouble */
2046                   if (level < olevel)
2047                     n = installed->start;       /* redo all */
2048                   i--;
2049                   n--;
2050                   continue;
2051                 }
2052             }
2053           /* if still undecided keep package */
2054           if (solv->decisionmap[i] == 0)
2055             {
2056               olevel = level;
2057               if (solv->cleandepsmap.size && MAPTST(&solv->cleandepsmap, i - installed->start))
2058                 {
2059 #if 0
2060                   POOL_DEBUG(SOLV_DEBUG_POLICY, "cleandeps erasing %s\n", pool_solvid2str(pool, i));
2061                   level = setpropagatelearn(solv, level, -i, disablerules, 0, SOLVER_REASON_CLEANDEPS_ERASE);
2062 #else
2063                   continue;
2064 #endif
2065                 }
2066               else
2067                 {
2068                   POOL_DEBUG(SOLV_DEBUG_POLICY, "keeping %s\n", pool_solvid2str(pool, i));
2069                   level = setpropagatelearn(solv, level, i, disablerules, r - solv->rules, SOLVER_REASON_KEEP_INSTALLED);
2070                 }
2071               if (level <= olevel)
2072                 {
2073                   if (level < passlevel)
2074                     break;      /* trouble */
2075                   if (level < olevel)
2076                     n = installed->start;       /* redo all */
2077                   i--;
2078                   n--;
2079                   continue;     /* retry with learnt rule */
2080                 }
2081             }
2082         }
2083       if (n < installed->end)
2084         {
2085           installedpos = i;     /* retry problem solvable next time */
2086           if (level < origlevel)
2087             break;              /* ran into trouble */
2088           /* re-run all passes */
2089           pass = solv->updatemap.size ? 0 : 1;
2090           continue;
2091         }
2092       /* reset installedpos, advance to next pass */
2093       installedpos = installed->start;
2094       pass++;
2095     }
2096   solv->installedpos = installedpos;
2097   return level;
2098 }
2099
2100 static int
2101 resolve_dependencies(Solver *solv, int level, int disablerules, Queue *dq)
2102 {
2103   Pool *pool = solv->pool;
2104   int i, j, n;
2105   int postponed;
2106   Rule *r;
2107   int origlevel = level;
2108   Id p, *dp;
2109
2110   /*
2111    * decide
2112    */
2113   POOL_DEBUG(SOLV_DEBUG_POLICY, "deciding unresolved rules\n");
2114   postponed = 0;
2115   for (i = 1, n = 1; ; i++, n++)
2116     {
2117       if (n >= solv->nrules)
2118         {
2119           if (postponed <= 0)
2120             break;
2121           i = postponed;
2122           postponed = -1;
2123           n = 1;
2124         }
2125       if (i == solv->nrules)
2126         i = 1;
2127       r = solv->rules + i;
2128       if (r->d < 0)             /* ignore disabled rules */
2129         continue;
2130       if (r->p < 0)             /* most common cases first */
2131         {
2132           if (r->d == 0 || solv->decisionmap[-r->p] <= 0)
2133             continue;
2134         }
2135       if (dq->count)
2136         queue_empty(dq);
2137       if (r->d == 0)
2138         {
2139           /* binary or unary rule */
2140           /* need two positive undecided literals, r->p already checked above */
2141           if (r->w2 <= 0)
2142             continue;
2143           if (solv->decisionmap[r->p] || solv->decisionmap[r->w2])
2144             continue;
2145           queue_push(dq, r->p);
2146           queue_push(dq, r->w2);
2147         }
2148       else
2149         {
2150           /* make sure that
2151            * all negative literals are installed
2152            * no positive literal is installed
2153            * i.e. the rule is not fulfilled and we
2154            * just need to decide on the positive literals
2155            * (decisionmap[-r->p] for the r->p < 0 case is already checked above)
2156            */
2157           if (r->p >= 0)
2158             {
2159               if (solv->decisionmap[r->p] > 0)
2160                 continue;
2161               if (solv->decisionmap[r->p] == 0)
2162                 queue_push(dq, r->p);
2163             }
2164           dp = pool->whatprovidesdata + r->d;
2165           while ((p = *dp++) != 0)
2166             {
2167               if (p < 0)
2168                 {
2169                   if (solv->decisionmap[-p] <= 0)
2170                     break;
2171                 }
2172               else
2173                 {
2174                   if (solv->decisionmap[p] > 0)
2175                     break;
2176                   if (solv->decisionmap[p] == 0)
2177                     queue_push(dq, p);
2178                 }
2179             }
2180           if (p)
2181             continue;
2182         }
2183       IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
2184         {
2185           POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "unfulfilled ");
2186           solver_printruleclass(solv, SOLV_DEBUG_PROPAGATE, r);
2187         }
2188       /* dq->count < 2 cannot happen as this means that
2189        * the rule is unit */
2190       assert(dq->count > 1);
2191
2192       /* prune to cleandeps packages */
2193       if (solv->cleandepsmap.size && solv->installed)
2194         {
2195           Repo *installed = solv->installed;
2196           for (j = 0; j < dq->count; j++)
2197             if (pool->solvables[dq->elements[j]].repo == installed && MAPTST(&solv->cleandepsmap, dq->elements[j] - installed->start))
2198               break;
2199           if (j < dq->count)
2200             {
2201               dq->elements[0] = dq->elements[j];
2202               queue_truncate(dq, 1);
2203             }
2204         }
2205
2206       if (dq->count > 1 && postponed >= 0)
2207         {
2208           policy_filter_unwanted(solv, dq, POLICY_MODE_CHOOSE_NOREORDER);
2209           if (dq->count > 1)
2210             {
2211               if (!postponed)
2212                 postponed = i;
2213               continue;
2214             }
2215         }
2216
2217       level = selectandinstall(solv, level, dq, disablerules, r - solv->rules, SOLVER_REASON_RESOLVE);
2218       if (level < origlevel)
2219         break;          /* trouble */
2220       /* something changed, so look at all rules again */
2221       n = 0;
2222     }
2223   return level;
2224 }
2225
2226
2227 #ifdef ENABLE_COMPLEX_DEPS
2228
2229 static void
2230 add_complex_recommends(Solver *solv, Id rec, Queue *dq, Map *dqmap)
2231 {
2232   Pool *pool = solv->pool;
2233   int oldcnt = dq->count;
2234   int cutcnt, blkcnt;
2235   Id p;
2236   int i, j;
2237
2238 #if 0
2239   printf("ADD_COMPLEX_RECOMMENDS %s\n", pool_dep2str(pool, rec));
2240 #endif
2241   i = pool_normalize_complex_dep(pool, rec, dq, CPLXDEPS_EXPAND);
2242   if (i == 0 || i == 1)
2243     return;
2244   cutcnt = dq->count;
2245   for (i = oldcnt; i < cutcnt; i++)
2246     {
2247       blkcnt = dq->count;
2248       for (; (p = dq->elements[i]) != 0; i++)
2249         {
2250           if (p < 0)
2251             {
2252               if (solv->decisionmap[-p] <= 0)
2253                 break;
2254               continue;
2255             }
2256           if (solv->decisionmap[p] > 0)
2257             {
2258               queue_truncate(dq, blkcnt);
2259               break;
2260             }
2261           if (dqmap)
2262             {
2263               if (!MAPTST(dqmap, p))
2264                 continue;
2265             }
2266           else
2267             {
2268               if (solv->decisionmap[p] < 0)
2269                 continue;
2270               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))))
2271                 continue;
2272             }
2273           queue_push(dq, p);
2274         }
2275       while (dq->elements[i])
2276         i++;
2277     }
2278   queue_deleten(dq, oldcnt, cutcnt - oldcnt);
2279   /* unify */
2280   if (dq->count != oldcnt)
2281     {
2282       for (j = oldcnt; j < dq->count; j++)
2283         {
2284           p = dq->elements[j];
2285           for (i = 0; i < j; i++)
2286             if (dq->elements[i] == p)
2287               {
2288                 dq->elements[j] = 0;
2289                 break;
2290               }
2291         }
2292       for (i = j = oldcnt; j < dq->count; j++)
2293         if (dq->elements[j])
2294           dq->elements[i++] = dq->elements[j];
2295       queue_truncate(dq, i);
2296     }
2297 #if 0
2298   printf("RETURN:\n");
2299   for (i = oldcnt; i < dq->count; i++)
2300     printf("  - %s\n", pool_solvid2str(pool, dq->elements[i]));
2301 #endif
2302 }
2303
2304 static void
2305 do_complex_recommendations(Solver *solv, Id rec, Map *m, int noselected)
2306 {
2307   Pool *pool = solv->pool;
2308   Queue dq;
2309   Id p;
2310   int i, blk;
2311
2312 #if 0
2313   printf("DO_COMPLEX_RECOMMENDATIONS %s\n", pool_dep2str(pool, rec));
2314 #endif
2315   queue_init(&dq);
2316   i = pool_normalize_complex_dep(pool, rec, &dq, CPLXDEPS_EXPAND);
2317   if (i == 0 || i == 1)
2318     {
2319       queue_free(&dq);
2320       return;
2321     }
2322   for (i = 0; i < dq.count; i++)
2323     {
2324       blk = i;
2325       for (; (p = dq.elements[i]) != 0; i++)
2326         {
2327           if (p < 0)
2328             {
2329               if (solv->decisionmap[-p] <= 0)
2330                 break;
2331               continue;
2332             }
2333           if (solv->decisionmap[p] > 0)
2334             {
2335               if (noselected)
2336                 break;
2337               MAPSET(m, p);
2338               for (i++; (p = dq.elements[i]) != 0; i++)
2339                 if (p > 0 && solv->decisionmap[p] > 0)
2340                   MAPSET(m, p);
2341               p = 1;
2342               break;
2343             }
2344         }
2345       if (!p)
2346         {
2347           for (i = blk; (p = dq.elements[i]) != 0; i++)
2348             if (p > 0)
2349               MAPSET(m, p);
2350         }
2351       while (dq.elements[i])
2352         i++;
2353     }
2354   queue_free(&dq);
2355 }
2356
2357 #endif
2358
2359 static void
2360 prune_disfavored(Solver *solv, Queue *plist)
2361 {
2362   int i, j;
2363   if (!solv->isdisfavormap.size)
2364     return;
2365   for (i = j = 0; i < plist->count; i++)
2366     {
2367       Id p = plist->elements[i];
2368       if (!MAPTST(&solv->isdisfavormap, p))
2369         plist->elements[j++] = p;
2370     }
2371   if (i != j)
2372     queue_truncate(plist, j);
2373 }
2374
2375 static int
2376 resolve_weak(Solver *solv, int level, int disablerules, Queue *dq, Queue *dqs, int *rerunp)
2377 {
2378   Pool *pool = solv->pool;
2379   int i, j, qcount;
2380   int olevel;
2381   Solvable *s;
2382   Map dqmap;
2383   int decisioncount;
2384   Id p;
2385
2386   POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended packages\n");
2387   if (dq->count)
2388     queue_empty(dq);    /* recommended packages */
2389   if (dqs->count)
2390     queue_empty(dqs);   /* supplemented packages */
2391   for (i = 1; i < pool->nsolvables; i++)
2392     {
2393       if (solv->decisionmap[i] < 0)
2394         continue;
2395       s = pool->solvables + i;
2396       if (solv->decisionmap[i] > 0)
2397         {
2398           /* installed, check for recommends */
2399           Id *recp, rec, pp, p;
2400           if (!solv->addalreadyrecommended && s->repo == solv->installed)
2401             continue;
2402           /* XXX need to special case AND ? */
2403           if (s->recommends)
2404             {
2405               recp = s->repo->idarraydata + s->recommends;
2406               while ((rec = *recp++) != 0)
2407                 {
2408 #ifdef ENABLE_COMPLEX_DEPS
2409                   if (pool_is_complex_dep(pool, rec))
2410                     {
2411                       add_complex_recommends(solv, rec, dq, 0);
2412                       continue;
2413                     }
2414 #endif
2415                   qcount = dq->count;
2416                   FOR_PROVIDES(p, pp, rec)
2417                     {
2418                       if (solv->decisionmap[p] > 0)
2419                         {
2420                           dq->count = qcount;
2421                           break;
2422                         }
2423                       else if (solv->decisionmap[p] == 0)
2424                         {
2425                           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))))
2426                             continue;
2427                           queue_pushunique(dq, p);
2428                         }
2429                     }
2430                 }
2431             }
2432         }
2433       else
2434         {
2435           /* not yet installed, check if supplemented */
2436           if (!s->supplements)
2437             continue;
2438           if (!pool_installable(pool, s))
2439             continue;
2440           if (!solver_is_supplementing(solv, s))
2441             continue;
2442           if (solv->dupmap_all && solv->installed && s->repo == solv->installed && (solv->droporphanedmap_all || (solv->droporphanedmap.size && MAPTST(&solv->droporphanedmap, i - solv->installed->start))))
2443             continue;
2444           if (solv->isdisfavormap.size && MAPTST(&solv->isdisfavormap, i))
2445             continue;   /* disfavored supplements, do not install */
2446           queue_push(dqs, i);
2447         }
2448     }
2449
2450   /* filter out disfavored recommended packages */
2451   if (dq->count && solv->isdisfavormap.size)
2452     prune_disfavored(solv, dq);
2453
2454   /* filter out all packages obsoleted by installed packages */
2455   /* this is no longer needed if we have (and trust) reverse obsoletes */
2456   if ((dqs->count || dq->count) && solv->installed)
2457     {
2458       Map obsmap;
2459       Id obs, *obsp, po, ppo;
2460
2461       map_init(&obsmap, pool->nsolvables);
2462       for (p = solv->installed->start; p < solv->installed->end; p++)
2463         {
2464           s = pool->solvables + p;
2465           if (s->repo != solv->installed || !s->obsoletes)
2466             continue;
2467           if (solv->decisionmap[p] <= 0)
2468             continue;
2469           if (!solv->keepexplicitobsoletes && solv->multiversion.size && MAPTST(&solv->multiversion, p))
2470             continue;
2471           obsp = s->repo->idarraydata + s->obsoletes;
2472           /* foreach obsoletes */
2473           while ((obs = *obsp++) != 0)
2474             FOR_PROVIDES(po, ppo, obs)
2475               {
2476                 Solvable *pos = pool->solvables + po;
2477                 if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, pos, obs))
2478                   continue;
2479                 if (pool->obsoleteusescolors && !pool_colormatch(pool, s, pos))
2480                   continue;
2481                 MAPSET(&obsmap, po);
2482               }
2483         }
2484       for (i = j = 0; i < dqs->count; i++)
2485         if (!MAPTST(&obsmap, dqs->elements[i]))
2486           dqs->elements[j++] = dqs->elements[i];
2487       dqs->count = j;
2488       for (i = j = 0; i < dq->count; i++)
2489         if (!MAPTST(&obsmap, dq->elements[i]))
2490           dq->elements[j++] = dq->elements[i];
2491       dq->count = j;
2492       map_free(&obsmap);
2493     }
2494
2495   /* filter out all already supplemented packages if requested */
2496   if (!solv->addalreadyrecommended && dqs->count)
2497     {
2498       /* filter out old supplements */
2499       for (i = j = 0; i < dqs->count; i++)
2500         {
2501           p = dqs->elements[i];
2502           s = pool->solvables + p;
2503           if (s->supplements && solver_is_supplementing_alreadyinstalled(solv, s))
2504             dqs->elements[j++] = p;
2505         }
2506       dqs->count = j;
2507     }
2508
2509   /* multiversion doesn't mix well with supplements.
2510    * filter supplemented packages where we already decided
2511    * to install a different version (see bnc#501088) */
2512   if (dqs->count && solv->multiversion.size)
2513     {
2514       for (i = j = 0; i < dqs->count; i++)
2515         {
2516           p = dqs->elements[i];
2517           if (MAPTST(&solv->multiversion, p))
2518             {
2519               Id p2, pp2;
2520               s = pool->solvables + p;
2521               FOR_PROVIDES(p2, pp2, s->name)
2522                 if (solv->decisionmap[p2] > 0 && pool->solvables[p2].name == s->name)
2523                   break;
2524               if (p2)
2525                 continue;       /* ignore this package */
2526             }
2527           dqs->elements[j++] = p;
2528         }
2529       dqs->count = j;
2530     }
2531
2532   /* implicitobsoleteusescolors doesn't mix well with supplements.
2533    * filter supplemented packages where we already decided
2534    * to install a different architecture */
2535   if (dqs->count && pool->implicitobsoleteusescolors)
2536     {
2537       for (i = j = 0; i < dqs->count; i++)
2538         {
2539           Id p2, pp2;
2540           p = dqs->elements[i];
2541           s = pool->solvables + p;
2542           FOR_PROVIDES(p2, pp2, s->name)
2543             if (solv->decisionmap[p2] > 0 && pool->solvables[p2].name == s->name && pool->solvables[p2].arch != s->arch)
2544               break;
2545           if (p2)
2546             continue;   /* ignore this package */
2547           dqs->elements[j++] = p;
2548         }
2549       dqs->count = j;
2550     }
2551
2552   /* make dq contain both recommended and supplemented pkgs */
2553   if (dqs->count)
2554     {
2555       for (i = 0; i < dqs->count; i++)
2556         queue_pushunique(dq, dqs->elements[i]);
2557     }
2558
2559   if (!dq->count)
2560     return level;
2561   *rerunp = 1;
2562
2563   if (dq->count == 1)
2564     {
2565       /* simple case, just one package. no need to choose to best version */
2566       p = dq->elements[0];
2567       if (dqs->count)
2568         POOL_DEBUG(SOLV_DEBUG_POLICY, "installing supplemented %s\n", pool_solvid2str(pool, p));
2569       else
2570         POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended %s\n", pool_solvid2str(pool, p));
2571       return setpropagatelearn(solv, level, p, 0, 0, SOLVER_REASON_WEAKDEP);
2572     }
2573
2574   /* filter packages, this gives us the best versions */
2575   policy_filter_unwanted(solv, dq, POLICY_MODE_RECOMMEND);
2576
2577   /* create map of result */
2578   map_init(&dqmap, pool->nsolvables);
2579   for (i = 0; i < dq->count; i++)
2580     MAPSET(&dqmap, dq->elements[i]);
2581
2582   /* prune dqs so that it only contains the best versions */
2583   for (i = j = 0; i < dqs->count; i++)
2584     {
2585       p = dqs->elements[i];
2586       if (MAPTST(&dqmap, p))
2587         dqs->elements[j++] = p;
2588     }
2589   dqs->count = j;
2590
2591   /* install all supplemented packages, but order first */
2592   if (dqs->count > 1)
2593     policy_filter_unwanted(solv, dqs, POLICY_MODE_SUPPLEMENT);
2594   decisioncount = solv->decisionq.count;
2595   for (i = 0; i < dqs->count; i++)
2596     {
2597       p = dqs->elements[i];
2598       if (solv->decisionmap[p])
2599         continue;
2600       POOL_DEBUG(SOLV_DEBUG_POLICY, "installing supplemented %s\n", pool_solvid2str(pool, p));
2601       olevel = level;
2602       level = setpropagatelearn(solv, level, p, 0, 0, SOLVER_REASON_WEAKDEP);
2603       if (level <= olevel)
2604         break;
2605     }
2606   if (i < dqs->count || solv->decisionq.count < decisioncount)
2607     {
2608       map_free(&dqmap);
2609       return level;
2610     }
2611
2612   /* install all recommended packages */
2613   /* more work as we want to created branches if multiple
2614    * choices are valid */
2615   for (i = 0; i < decisioncount; i++)
2616     {
2617       Id rec, *recp, pp;
2618       p = solv->decisionq.elements[i];
2619       if (p < 0)
2620         continue;
2621       s = pool->solvables + p;
2622       if (!s->repo || (!solv->addalreadyrecommended && s->repo == solv->installed))
2623         continue;
2624       if (!s->recommends)
2625         continue;
2626       recp = s->repo->idarraydata + s->recommends;
2627       while ((rec = *recp++) != 0)
2628         {
2629           queue_empty(dq);
2630 #ifdef ENABLE_COMPLEX_DEPS
2631           if (pool_is_complex_dep(pool, rec))
2632               add_complex_recommends(solv, rec, dq, &dqmap);
2633           else
2634 #endif
2635           FOR_PROVIDES(p, pp, rec)
2636             {
2637               if (solv->decisionmap[p] > 0)
2638                 {
2639                   dq->count = 0;
2640                   break;
2641                 }
2642               else if (solv->decisionmap[p] == 0 && MAPTST(&dqmap, p))
2643                 queue_push(dq, p);
2644             }
2645           if (!dq->count)
2646             continue;
2647           if (dq->count > 1)
2648             policy_filter_unwanted(solv, dq, POLICY_MODE_CHOOSE);
2649           /* if we have multiple candidates we open a branch */
2650           if (dq->count > 1)
2651               createbranch(solv, level, dq, s - pool->solvables, rec);
2652           p = dq->elements[0];
2653           POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended %s\n", pool_solvid2str(pool, p));
2654           olevel = level;
2655           level = setpropagatelearn(solv, level, p, 0, 0, SOLVER_REASON_WEAKDEP);
2656           if (level <= olevel || solv->decisionq.count < decisioncount)
2657             break;      /* we had to revert some decisions */
2658         }
2659       if (rec)
2660         break;  /* had a problem above, quit loop */
2661     }
2662   map_free(&dqmap);
2663   return level;
2664 }
2665
2666
2667 static int
2668 resolve_orphaned(Solver *solv, int level, int disablerules, Queue *dq, int *rerunp)
2669 {
2670   Pool *pool = solv->pool;
2671   int i;
2672   Id p;
2673   int installedone = 0;
2674   int olevel;
2675
2676   /* let's see if we can install some unsupported package */
2677   POOL_DEBUG(SOLV_DEBUG_SOLVER, "deciding orphaned packages\n");
2678   for (i = 0; i < solv->orphaned.count; i++)
2679     {
2680       p = solv->orphaned.elements[i];
2681       if (solv->decisionmap[p])
2682         continue;       /* already decided */
2683       if (solv->droporphanedmap_all)
2684         continue;
2685       if (solv->droporphanedmap.size && MAPTST(&solv->droporphanedmap, p - solv->installed->start))
2686         continue;
2687       POOL_DEBUG(SOLV_DEBUG_SOLVER, "keeping orphaned %s\n", pool_solvid2str(pool, p));
2688       olevel = level;
2689       level = setpropagatelearn(solv, level, p, 0, 0, SOLVER_REASON_RESOLVE_ORPHAN);
2690       installedone = 1;
2691       if (level < olevel)
2692         break;
2693     }
2694   if (installedone || i < solv->orphaned.count)
2695     {
2696       *rerunp = 1;
2697       return level;
2698     }
2699   for (i = 0; i < solv->orphaned.count; i++)
2700     {
2701       p = solv->orphaned.elements[i];
2702       if (solv->decisionmap[p])
2703         continue;       /* already decided */
2704       POOL_DEBUG(SOLV_DEBUG_SOLVER, "removing orphaned %s\n", pool_solvid2str(pool, p));
2705       olevel = level;
2706       level = setpropagatelearn(solv, level, -p, 0, 0, SOLVER_REASON_RESOLVE_ORPHAN);
2707       if (level < olevel)
2708         {
2709           *rerunp = 1;
2710           return level;
2711         }
2712     }
2713   if (solv->brokenorphanrules)
2714     {
2715       solver_check_brokenorphanrules(solv, dq);
2716       if (dq->count)
2717         {
2718           policy_filter_unwanted(solv, dq, POLICY_MODE_CHOOSE);
2719           for (i = 0; i < dq->count; i++)
2720             {
2721               p = dq->elements[i];
2722               POOL_DEBUG(SOLV_DEBUG_POLICY, "installing orphaned dep %s\n", pool_solvid2str(pool, p));
2723               olevel = level;
2724               level = setpropagatelearn(solv, level, p, 0, 0, SOLVER_REASON_RESOLVE_ORPHAN);
2725               if (level < olevel)
2726                 break;
2727             }
2728           *rerunp = 1;
2729         }
2730     }
2731   return level;
2732 }
2733
2734 /*-------------------------------------------------------------------
2735  *
2736  * solver_run_sat
2737  *
2738  * all rules have been set up, now actually run the solver
2739  *
2740  */
2741
2742 void
2743 solver_run_sat(Solver *solv, int disablerules, int doweak)
2744 {
2745   Queue dq;             /* local decisionqueue */
2746   Queue dqs;            /* local decisionqueue for supplements */
2747   int systemlevel;
2748   int level, olevel;
2749   Rule *r;
2750   int i;
2751   Solvable *s;
2752   Pool *pool = solv->pool;
2753   Id p;
2754   int minimizationsteps;
2755
2756   IF_POOLDEBUG (SOLV_DEBUG_RULE_CREATION)
2757     {
2758       POOL_DEBUG (SOLV_DEBUG_RULE_CREATION, "number of rules: %d\n", solv->nrules);
2759       for (i = 1; i < solv->nrules; i++)
2760         solver_printruleclass(solv, SOLV_DEBUG_RULE_CREATION, solv->rules + i);
2761     }
2762
2763   /* start SAT algorithm */
2764   level = 0;
2765   systemlevel = level + 1;
2766   POOL_DEBUG(SOLV_DEBUG_SOLVER, "solving...\n");
2767
2768   queue_init(&dq);
2769   queue_init(&dqs);
2770   solv->installedpos = 0;
2771   solv->do_extra_reordering = 0;
2772
2773   /*
2774    * here's the main loop:
2775    * 1) decide assertion rules and propagate
2776    * 2) fulfill jobs
2777    * 3) try to keep installed packages
2778    * 4) fulfill all unresolved rules
2779    * 5) install recommended packages
2780    * 6) minimalize solution if we had choices
2781    * if we encounter a problem, we rewind to a safe level and restart
2782    * with step 1
2783    */
2784
2785   minimizationsteps = 0;
2786   for (;;)
2787     {
2788       /*
2789        * initial propagation of the assertions
2790        */
2791       if (level <= 0)
2792         {
2793           if (level < 0)
2794             break;
2795           makeruledecisions(solv);
2796           level = 1;
2797           if (!disablerules && solv->problems.count)
2798             {
2799               level = -1;
2800               break;
2801             }
2802           POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "initial propagate (propagate_index: %d;  size decisionq: %d)...\n", solv->propagate_index, solv->decisionq.count);
2803           if ((r = propagate(solv, level)) != 0)
2804             {
2805               level = analyze_unsolvable(solv, r, disablerules);
2806               continue;
2807             }
2808           systemlevel = level + 1;
2809         }
2810
2811       /*
2812        * resolve jobs first (unless focus_installed is set)
2813        */
2814      if (level < systemlevel && !solv->focus_installed)
2815         {
2816           if (solv->installed && solv->installed->nsolvables && !solv->installed->disabled)
2817             solv->do_extra_reordering = 1;
2818           olevel = level;
2819           level = resolve_jobrules(solv, level, disablerules, &dq);
2820           solv->do_extra_reordering = 0;
2821           if (level < olevel)
2822             continue;
2823           systemlevel = level + 1;
2824         }
2825
2826       /* resolve job dependencies in the focus_best case */
2827       if (level < systemlevel && solv->focus_best && !solv->focus_installed && solv->installed && solv->installed->nsolvables && !solv->installed->disabled)
2828         {
2829           solv->do_extra_reordering = 1;
2830           olevel = level;
2831           level = resolve_dependencies(solv, level, disablerules, &dq);
2832           solv->do_extra_reordering = 0;
2833           if (level < olevel)
2834             continue;           /* start over */
2835           systemlevel = level + 1;
2836         }
2837
2838       /*
2839        * installed packages
2840        */
2841       if (level < systemlevel && solv->installed && solv->installed->nsolvables && !solv->installed->disabled)
2842         {
2843           olevel = level;
2844           level = resolve_installed(solv, level, disablerules, &dq);
2845           if (level < olevel)
2846             continue;
2847           systemlevel = level + 1;
2848         }
2849
2850      /* resolve jobs in focus_installed case */
2851      if (level < systemlevel && solv->focus_installed)
2852         {
2853           olevel = level;
2854           level = resolve_jobrules(solv, level, disablerules, &dq);
2855           if (level < olevel)
2856             continue;
2857           systemlevel = level + 1;
2858         }
2859
2860       if (level < systemlevel)
2861         systemlevel = level;
2862
2863       /* resolve all dependencies */
2864       olevel = level;
2865       level = resolve_dependencies(solv, level, disablerules, &dq);
2866       if (level < olevel)
2867         continue;               /* start over */
2868
2869       /* decide leftover cleandeps packages */
2870       if (solv->cleandepsmap.size && solv->installed)
2871        {
2872          for (p = solv->installed->start; p < solv->installed->end; p++)
2873            {
2874              s = pool->solvables + p;
2875              if (s->repo != solv->installed)
2876                continue;
2877              if (solv->decisionmap[p] == 0 && MAPTST(&solv->cleandepsmap, p - solv->installed->start))
2878                {
2879                  POOL_DEBUG(SOLV_DEBUG_POLICY, "cleandeps erasing %s\n", pool_solvid2str(pool, p));
2880                  olevel = level;
2881                  level = setpropagatelearn(solv, level, -p, 0, 0, SOLVER_REASON_CLEANDEPS_ERASE);
2882                  if (level < olevel)
2883                    break;
2884                }
2885            }
2886          if (p < solv->installed->end)
2887            continue;
2888        }
2889
2890       /* at this point we have a consistent system. now do the extras... */
2891
2892       if (doweak)
2893         {
2894           int rerun = 0;
2895           level = resolve_weak(solv, level, disablerules, &dq, &dqs, &rerun);
2896           if (rerun)
2897             continue;
2898         }
2899
2900       if (solv->installed && (solv->orphaned.count || solv->brokenorphanrules))
2901         {
2902           int rerun = 0;
2903           level = resolve_orphaned(solv, level, disablerules, &dq, &rerun);
2904           if (rerun)
2905             continue;
2906         }
2907
2908      /* one final pass to make sure we decided all installed packages */
2909       if (solv->installed)
2910         {
2911           for (p = solv->installed->start; p < solv->installed->end; p++)
2912             {
2913               if (solv->decisionmap[p])
2914                 continue;       /* already decided */
2915               s = pool->solvables + p;
2916               if (s->repo != solv->installed)
2917                 continue;
2918               POOL_DEBUG(SOLV_DEBUG_SOLVER, "removing unwanted %s\n", pool_solvid2str(pool, p));
2919               olevel = level;
2920               level = setpropagatelearn(solv, level, -p, 0, 0, SOLVER_REASON_CLEANDEPS_ERASE);
2921               if (level < olevel)
2922                 break;
2923             }
2924           if (p < solv->installed->end)
2925             continue;           /* back to main loop */
2926         }
2927
2928       if (solv->installed && solv->cleandepsmap.size && cleandeps_check_mistakes(solv))
2929         {
2930           solver_reset(solv);
2931           level = 0;    /* restart from scratch */
2932           continue;
2933         }
2934
2935       if (solv->solution_callback)
2936         {
2937           solv->solution_callback(solv, solv->solution_callback_data);
2938           if (solv->branches.count)
2939             {
2940               int l, endi = 0;
2941               p = l = 0;
2942               for (i = solv->branches.count - 1; i >= 0; i--)
2943                 {
2944                   p = solv->branches.elements[i];
2945                   if (p > 0 && !l)
2946                     {
2947                       endi = i + 1;
2948                       l = p;
2949                       i -= 3;   /* skip: p data count */
2950                     }
2951                   else if (p > 0)
2952                     break;
2953                   else if (p < 0)
2954                     l = 0;
2955                 }
2956               if (i >= 0)
2957                 {
2958                   while (i > 0 && solv->branches.elements[i - 1] > 0)
2959                     i--;
2960                   level = takebranch(solv, i, endi, "branching", disablerules);
2961                   continue;
2962                 }
2963             }
2964           /* all branches done, we're finally finished */
2965           break;
2966         }
2967
2968       /* auto-minimization step */
2969       if (solv->branches.count)
2970         {
2971           int endi, lasti = -1, lastiend = -1;
2972           if (solv->recommends_index < solv->decisionq.count)
2973             policy_update_recommendsmap(solv);
2974           for (endi = solv->branches.count; endi > 0;)
2975             {
2976               int l, lastsi = -1, starti = endi - solv->branches.elements[endi - 2];
2977               l = solv->branches.elements[endi - 1];
2978               for (i = starti; i < endi - 4; i++)
2979                 {
2980                   p = solv->branches.elements[i];
2981                   if (p <= 0)
2982                     continue;
2983                   if (solv->decisionmap[p] > l)
2984                     {
2985                       lasti = i;
2986                       lastiend = endi;
2987                       lastsi = -1;
2988                       break;
2989                     }
2990                   if (solv->isdisfavormap.size && MAPTST(&solv->isdisfavormap, p))
2991                     continue;
2992                   if (lastsi < 0 && (MAPTST(&solv->recommendsmap, p) || solver_is_supplementing(solv, pool->solvables + p)))
2993                     lastsi = i;
2994                 }
2995               if (lastsi >= 0)
2996                 {
2997                   /* we have a recommended package that could not be installed */
2998                   /* take it if our current selection is not recommended */
2999                   for (i = starti; i < endi - 4; i++)
3000                     {
3001                       p = -solv->branches.elements[i];
3002                       if (p <= 0 || solv->decisionmap[p] != l + 1)
3003                         continue;
3004                       if (solv->favormap.size && MAPTST(&solv->favormap, p))
3005                         if (!(solv->isdisfavormap.size && MAPTST(&solv->isdisfavormap, p)))
3006                           continue;     /* current selection is favored */
3007                       if (!(MAPTST(&solv->recommendsmap, p) || solver_is_supplementing(solv, pool->solvables + p)))
3008                         {
3009                           lasti = lastsi;
3010                           lastiend = endi;
3011                           break;
3012                         }
3013                     }
3014                 }
3015               endi = starti;
3016             }
3017           if (lasti >= 0)
3018             {
3019               minimizationsteps++;
3020               level = takebranch(solv, lasti, lastiend, "minimizing", disablerules);
3021               continue;         /* back to main loop */
3022             }
3023         }
3024       /* no minimization found, we're finally finished! */
3025       break;
3026     }
3027   assert(level == -1 || level + 1 == solv->decisionq_reason.count);
3028
3029   POOL_DEBUG(SOLV_DEBUG_STATS, "solver statistics: %d learned rules, %d unsolvable, %d minimization steps\n", solv->stats_learned, solv->stats_unsolvable, minimizationsteps);
3030
3031   POOL_DEBUG(SOLV_DEBUG_STATS, "done solving.\n\n");
3032   queue_free(&dq);
3033   queue_free(&dqs);
3034 #if 0
3035   solver_printdecisionq(solv, SOLV_DEBUG_RESULT);
3036 #endif
3037 }
3038
3039
3040 /*-------------------------------------------------------------------
3041  *
3042  * remove disabled conflicts
3043  *
3044  * purpose: update the decisionmap after some rules were disabled.
3045  * this is used to calculate the suggested/recommended package list.
3046  * Also returns a "removed" list to undo the discisionmap changes.
3047  */
3048
3049 static void
3050 removedisabledconflicts(Solver *solv, Queue *removed)
3051 {
3052   Pool *pool = solv->pool;
3053   int i, n;
3054   Id p, why, *dp;
3055   Id new;
3056   Rule *r;
3057   Id *decisionmap = solv->decisionmap;
3058
3059   queue_empty(removed);
3060   for (i = 0; i < solv->decisionq.count; i++)
3061     {
3062       p = solv->decisionq.elements[i];
3063       if (p > 0)
3064         continue;       /* conflicts only, please */
3065       why = solv->decisionq_why.elements[i];
3066       if (why == 0)
3067         {
3068           /* no rule involved, must be a orphan package drop */
3069           continue;
3070         }
3071       /* we never do conflicts on free decisions, so there
3072        * must have been an unit rule */
3073       assert(why > 0);
3074       r = solv->rules + why;
3075       if (r->d < 0 && decisionmap[-p])
3076         {
3077           /* rule is now disabled, remove from decisionmap */
3078           POOL_DEBUG(SOLV_DEBUG_SOLVER, "removing conflict for package %s[%d]\n", pool_solvid2str(pool, -p), -p);
3079           queue_push(removed, -p);
3080           queue_push(removed, decisionmap[-p]);
3081           decisionmap[-p] = 0;
3082         }
3083     }
3084   if (!removed->count)
3085     return;
3086   /* we removed some confliced packages. some of them might still
3087    * be in conflict, so search for unit rules and re-conflict */
3088   new = 0;
3089   for (i = n = 1, r = solv->rules + i; n < solv->nrules; i++, r++, n++)
3090     {
3091       if (i == solv->nrules)
3092         {
3093           i = 1;
3094           r = solv->rules + i;
3095         }
3096       if (r->d < 0)
3097         continue;
3098       if (!r->w2)
3099         {
3100           if (r->p < 0 && !decisionmap[-r->p])
3101             new = r->p;
3102         }
3103       else if (!r->d)
3104         {
3105           /* binary rule */
3106           if (r->p < 0 && decisionmap[-r->p] == 0 && DECISIONMAP_FALSE(r->w2))
3107             new = r->p;
3108           else if (r->w2 < 0 && decisionmap[-r->w2] == 0 && DECISIONMAP_FALSE(r->p))
3109             new = r->w2;
3110         }
3111       else
3112         {
3113           if (r->p < 0 && decisionmap[-r->p] == 0)
3114             new = r->p;
3115           if (new || DECISIONMAP_FALSE(r->p))
3116             {
3117               dp = pool->whatprovidesdata + r->d;
3118               while ((p = *dp++) != 0)
3119                 {
3120                   if (new && p == new)
3121                     continue;
3122                   if (p < 0 && decisionmap[-p] == 0)
3123                     {
3124                       if (new)
3125                         {
3126                           new = 0;
3127                           break;
3128                         }
3129                       new = p;
3130                     }
3131                   else if (!DECISIONMAP_FALSE(p))
3132                     {
3133                       new = 0;
3134                       break;
3135                     }
3136                 }
3137             }
3138         }
3139       if (new)
3140         {
3141           POOL_DEBUG(SOLV_DEBUG_SOLVER, "re-conflicting package %s[%d]\n", pool_solvid2str(pool, -new), -new);
3142           decisionmap[-new] = -1;
3143           new = 0;
3144           n = 0;        /* redo all rules */
3145         }
3146     }
3147 }
3148
3149 static inline void
3150 undo_removedisabledconflicts(Solver *solv, Queue *removed)
3151 {
3152   int i;
3153   for (i = 0; i < removed->count; i += 2)
3154     solv->decisionmap[removed->elements[i]] = removed->elements[i + 1];
3155 }
3156
3157
3158 /*-------------------------------------------------------------------
3159  *
3160  * weaken solvable dependencies
3161  */
3162
3163 static void
3164 weaken_solvable_deps(Solver *solv, Id p)
3165 {
3166   int i;
3167   Rule *r;
3168
3169   for (i = 1, r = solv->rules + i; i < solv->pkgrules_end; i++, r++)
3170     {
3171       if (r->p != -p)
3172         continue;
3173       if ((r->d == 0 || r->d == -1) && r->w2 < 0)
3174         continue;       /* conflict */
3175       queue_push(&solv->weakruleq, i);
3176     }
3177 }
3178
3179
3180 /********************************************************************/
3181 /* main() */
3182
3183
3184 void
3185 solver_calculate_multiversionmap(Pool *pool, Queue *job, Map *multiversionmap)
3186 {
3187   int i;
3188   Id how, what, select;
3189   Id p, pp;
3190   for (i = 0; i < job->count; i += 2)
3191     {
3192       how = job->elements[i];
3193       if ((how & SOLVER_JOBMASK) != SOLVER_MULTIVERSION)
3194         continue;
3195       what = job->elements[i + 1];
3196       select = how & SOLVER_SELECTMASK;
3197       if (!multiversionmap->size)
3198         map_grow(multiversionmap, pool->nsolvables);
3199       if (select == SOLVER_SOLVABLE_ALL)
3200         {
3201           FOR_POOL_SOLVABLES(p)
3202             MAPSET(multiversionmap, p);
3203         }
3204       else if (select == SOLVER_SOLVABLE_REPO)
3205         {
3206           Solvable *s;
3207           Repo *repo = pool_id2repo(pool, what);
3208           if (repo)
3209             {
3210               FOR_REPO_SOLVABLES(repo, p, s)
3211                 MAPSET(multiversionmap, p);
3212             }
3213         }
3214       FOR_JOB_SELECT(p, pp, select, what)
3215         MAPSET(multiversionmap, p);
3216     }
3217 }
3218
3219 void
3220 solver_calculate_noobsmap(Pool *pool, Queue *job, Map *multiversionmap)
3221 {
3222   solver_calculate_multiversionmap(pool, job, multiversionmap);
3223 }
3224
3225 /*
3226  * add a rule created by a job, record job number and weak flag
3227  */
3228 static inline void
3229 solver_addjobrule(Solver *solv, Id p, Id p2, Id d, Id job, int weak)
3230 {
3231   solver_addrule(solv, p, p2, d);
3232   queue_push(&solv->ruletojob, job);
3233   if (weak)
3234     queue_push(&solv->weakruleq, solv->nrules - 1);
3235 }
3236
3237 static inline void
3238 add_cleandeps_package(Solver *solv, Id p)
3239 {
3240   if (!solv->cleandeps_updatepkgs)
3241     {
3242       solv->cleandeps_updatepkgs = solv_calloc(1, sizeof(Queue));
3243       queue_init(solv->cleandeps_updatepkgs);
3244     }
3245   queue_pushunique(solv->cleandeps_updatepkgs, p);
3246 }
3247
3248 static void
3249 add_update_target(Solver *solv, Id p, Id how)
3250 {
3251   Pool *pool = solv->pool;
3252   Solvable *s = pool->solvables + p;
3253   Repo *installed = solv->installed;
3254   Id pi, pip;
3255   if (!solv->update_targets)
3256     {
3257       solv->update_targets = solv_calloc(1, sizeof(Queue));
3258       queue_init(solv->update_targets);
3259     }
3260   if (s->repo == installed)
3261     {
3262       queue_push2(solv->update_targets, p, p);
3263       return;
3264     }
3265   FOR_PROVIDES(pi, pip, s->name)
3266     {
3267       Solvable *si = pool->solvables + pi;
3268       if (si->repo != installed || si->name != s->name)
3269         continue;
3270       if (how & SOLVER_FORCEBEST)
3271         {
3272           if (!solv->bestupdatemap.size)
3273             map_grow(&solv->bestupdatemap, installed->end - installed->start);
3274           MAPSET(&solv->bestupdatemap, pi - installed->start);
3275         }
3276       if (how & SOLVER_CLEANDEPS)
3277         add_cleandeps_package(solv, pi);
3278       queue_push2(solv->update_targets, pi, p);
3279       /* check if it's ok to keep the installed package */
3280       if (s->evr == si->evr && solvable_identical(s, si))
3281         queue_push2(solv->update_targets, pi, pi);
3282     }
3283   if (s->obsoletes)
3284     {
3285       Id obs, *obsp = s->repo->idarraydata + s->obsoletes;
3286       while ((obs = *obsp++) != 0)
3287         {
3288           FOR_PROVIDES(pi, pip, obs)
3289             {
3290               Solvable *si = pool->solvables + pi;
3291               if (si->repo != installed)
3292                 continue;
3293               if (si->name == s->name)
3294                 continue;       /* already handled above */
3295               if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, si, obs))
3296                 continue;
3297               if (pool->obsoleteusescolors && !pool_colormatch(pool, s, si))
3298                 continue;
3299               if (how & SOLVER_FORCEBEST)
3300                 {
3301                   if (!solv->bestupdatemap.size)
3302                     map_grow(&solv->bestupdatemap, installed->end - installed->start);
3303                   MAPSET(&solv->bestupdatemap, pi - installed->start);
3304                 }
3305               if (how & SOLVER_CLEANDEPS)
3306                 add_cleandeps_package(solv, pi);
3307               queue_push2(solv->update_targets, pi, p);
3308             }
3309         }
3310     }
3311 }
3312
3313 static int
3314 transform_update_targets_sortfn(const void *ap, const void *bp, void *dp)
3315 {
3316   const Id *a = ap;
3317   const Id *b = bp;
3318   if (a[0] - b[0])
3319     return a[0] - b[0];
3320   return a[1] - b[1];
3321 }
3322
3323 static void
3324 transform_update_targets(Solver *solv)
3325 {
3326   Repo *installed = solv->installed;
3327   Queue *update_targets = solv->update_targets;
3328   int i, j;
3329   Id p, q, lastp, lastq;
3330
3331   if (!update_targets->count)
3332     {
3333       queue_free(update_targets);
3334       solv->update_targets = solv_free(update_targets);
3335       return;
3336     }
3337   if (update_targets->count > 2)
3338     solv_sort(update_targets->elements, update_targets->count >> 1, 2 * sizeof(Id), transform_update_targets_sortfn, solv);
3339   queue_insertn(update_targets, 0, installed->end - installed->start, 0);
3340   lastp = lastq = 0;
3341   for (i = j = installed->end - installed->start; i < update_targets->count; i += 2)
3342     {
3343       if ((p = update_targets->elements[i]) != lastp)
3344         {
3345           if (!solv->updatemap.size)
3346             map_grow(&solv->updatemap, installed->end - installed->start);
3347           MAPSET(&solv->updatemap, p - installed->start);
3348           update_targets->elements[j++] = 0;                    /* finish old set */
3349           update_targets->elements[p - installed->start] = j;   /* start new set */
3350           lastp = p;
3351           lastq = 0;
3352         }
3353       if ((q = update_targets->elements[i + 1]) != lastq)
3354         {
3355           update_targets->elements[j++] = q;
3356           lastq = q;
3357         }
3358     }
3359   queue_truncate(update_targets, j);
3360   queue_push(update_targets, 0);        /* finish last set */
3361 }
3362
3363
3364 static void
3365 addedmap2deduceq(Solver *solv, Map *addedmap)
3366 {
3367   Pool *pool = solv->pool;
3368   int i, j;
3369   Id p;
3370   Rule *r;
3371
3372   queue_empty(&solv->addedmap_deduceq);
3373   for (i = 2, j = solv->pkgrules_end - 1; i < pool->nsolvables && j > 0; j--)
3374     {
3375       r = solv->rules + j;
3376       if (r->p >= 0)
3377         continue;
3378       if ((r->d == 0 || r->d == -1) && r->w2 < 0)
3379         continue;
3380       p = -r->p;
3381       if (!MAPTST(addedmap, p))
3382         {
3383           /* should never happen, but... */
3384           if (!solv->addedmap_deduceq.count || solv->addedmap_deduceq.elements[solv->addedmap_deduceq.count - 1] != -p)
3385             queue_push(&solv->addedmap_deduceq, -p);
3386           continue;
3387         }
3388       for (; i < p; i++)
3389         if (MAPTST(addedmap, i))
3390           queue_push(&solv->addedmap_deduceq, i);
3391       if (i == p)
3392         i++;
3393     }
3394   for (; i < pool->nsolvables; i++)
3395     if (MAPTST(addedmap, i))
3396       queue_push(&solv->addedmap_deduceq, i);
3397   j = 0;
3398   for (i = 2; i < pool->nsolvables; i++)
3399     if (MAPTST(addedmap, i))
3400       j++;
3401 }
3402
3403 static void
3404 deduceq2addedmap(Solver *solv, Map *addedmap)
3405 {
3406   int j;
3407   Id p;
3408   Rule *r;
3409   for (j = solv->pkgrules_end - 1; j > 0; j--)
3410     {
3411       r = solv->rules + j;
3412       if (r->d < 0 && r->p)
3413         solver_enablerule(solv, r);
3414       if (r->p >= 0)
3415         continue;
3416       if ((r->d == 0 || r->d == -1) && r->w2 < 0)
3417         continue;
3418       p = -r->p;
3419       MAPSET(addedmap, p);
3420     }
3421   for (j = 0; j < solv->addedmap_deduceq.count; j++)
3422     {
3423       p = solv->addedmap_deduceq.elements[j];
3424       if (p > 0)
3425         MAPSET(addedmap, p);
3426       else
3427         MAPCLR(addedmap, p);
3428     }
3429 }
3430
3431 #ifdef ENABLE_COMPLEX_DEPS
3432 static int
3433 add_complex_jobrules(Solver *solv, Id dep, int flags, int jobidx, int weak)
3434 {
3435   Pool *pool = solv->pool;
3436   Queue bq;
3437   int i, j;
3438
3439   queue_init(&bq);
3440   i = pool_normalize_complex_dep(pool, dep, &bq, flags | CPLXDEPS_EXPAND);
3441   if (i == 0 || i == 1)
3442     {
3443       queue_free(&bq);
3444       if (i == 0)
3445         solver_addjobrule(solv, -SYSTEMSOLVABLE, 0, 0, jobidx, weak);
3446       return 0;
3447     }
3448   for (i = 0; i < bq.count; i++)
3449     {
3450       if (!bq.elements[i])
3451         continue;
3452       for (j = 0; bq.elements[i + j + 1]; j++)
3453         ;
3454       if (j > 1)
3455         solver_addjobrule(solv, bq.elements[i], 0, pool_ids2whatprovides(pool, bq.elements + i + 1, j), jobidx, weak);
3456       else
3457         solver_addjobrule(solv, bq.elements[i], bq.elements[i + 1], 0, jobidx, weak);
3458       i += j + 1;
3459     }
3460   queue_free(&bq);
3461   return 1;
3462 }
3463 #endif
3464
3465 /* sort by package id, last entry wins */
3466 static int
3467 setup_favormaps_cmp(const void *ap, const void *bp, void *dp)
3468 {
3469   const Id *a = ap, *b = bp;
3470   if ((*a - *b) != 0)
3471     return *a - *b;
3472   return (b[1] < 0 ? -b[1] : b[1]) - (a[1] < 0 ? -a[1] : a[1]);
3473 }
3474
3475 static void
3476 setup_favormaps(Solver *solv)
3477 {
3478   Queue *q = solv->favorq;
3479   Pool *pool = solv->pool;
3480   int i;
3481   Id oldp = 0;
3482   if (q->count > 2)
3483     solv_sort(q->elements, q->count / 2, 2 * sizeof(Id), setup_favormaps_cmp, solv);
3484   map_grow(&solv->favormap, pool->nsolvables);
3485   for (i = 0; i < q->count; i += 2)
3486     {
3487       Id p = q->elements[i];
3488       if (p == oldp)
3489         continue;
3490       oldp = p;
3491       MAPSET(&solv->favormap, p);
3492       if (q->elements[i + 1] < 0)
3493         {
3494           if (!solv->isdisfavormap.size)
3495             map_grow(&solv->isdisfavormap, pool->nsolvables);
3496           MAPSET(&solv->isdisfavormap, p);
3497         }
3498     }
3499 }
3500
3501 /*
3502  *
3503  * solve job queue
3504  *
3505  */
3506
3507 int
3508 solver_solve(Solver *solv, Queue *job)
3509 {
3510   Pool *pool = solv->pool;
3511   Repo *installed = solv->installed;
3512   int i;
3513   int oldnrules, initialnrules;
3514   Map addedmap;                /* '1' == have pkg-rules for solvable */
3515   Map installcandidatemap;
3516   Id how, what, select, name, weak, p, pp, d;
3517   Queue q;
3518   Solvable *s;
3519   Rule *r;
3520   int now, solve_start;
3521   int needduprules = 0;
3522   int hasbestinstalljob = 0;
3523
3524   solve_start = solv_timems(0);
3525
3526   /* log solver options */
3527   POOL_DEBUG(SOLV_DEBUG_STATS, "solver started\n");
3528   POOL_DEBUG(SOLV_DEBUG_STATS, "dosplitprovides=%d, noupdateprovide=%d, noinfarchcheck=%d\n", solv->dosplitprovides, solv->noupdateprovide, solv->noinfarchcheck);
3529   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);
3530   POOL_DEBUG(SOLV_DEBUG_STATS, "promoteepoch=%d, forbidselfconflicts=%d\n", pool->promoteepoch, pool->forbidselfconflicts);
3531   POOL_DEBUG(SOLV_DEBUG_STATS, "obsoleteusesprovides=%d, implicitobsoleteusesprovides=%d, obsoleteusescolors=%d, implicitobsoleteusescolors=%d\n", pool->obsoleteusesprovides, pool->implicitobsoleteusesprovides, pool->obsoleteusescolors, pool->implicitobsoleteusescolors);
3532   POOL_DEBUG(SOLV_DEBUG_STATS, "dontinstallrecommended=%d, addalreadyrecommended=%d\n", solv->dontinstallrecommended, solv->addalreadyrecommended);
3533
3534   /* create whatprovides if not already there */
3535   if (!pool->whatprovides)
3536     pool_createwhatprovides(pool);
3537
3538   /* create obsolete index */
3539   policy_create_obsolete_index(solv);
3540
3541   /* remember job */
3542   queue_free(&solv->job);
3543   queue_init_clone(&solv->job, job);
3544   solv->pooljobcnt = pool->pooljobs.count;
3545   if (pool->pooljobs.count)
3546     queue_insertn(&solv->job, 0, pool->pooljobs.count, pool->pooljobs.elements);
3547   job = &solv->job;
3548
3549   /* free old stuff in jase we re-run a solver */
3550   queuep_free(&solv->update_targets);
3551   queuep_free(&solv->cleandeps_updatepkgs);
3552   queue_empty(&solv->ruleassertions);
3553   solv->bestrules_pkg = solv_free(solv->bestrules_pkg);
3554   solv->yumobsrules_info = solv_free(solv->yumobsrules_info);
3555   solv->choicerules_ref = solv_free(solv->choicerules_ref);
3556   if (solv->noupdate.size)
3557     map_empty(&solv->noupdate);
3558   map_zerosize(&solv->multiversion);
3559   solv->updatemap_all = 0;
3560   map_zerosize(&solv->updatemap);
3561   solv->bestupdatemap_all = 0;
3562   map_zerosize(&solv->bestupdatemap);
3563   solv->fixmap_all = 0;
3564   map_zerosize(&solv->fixmap);
3565   solv->dupmap_all = 0;
3566   map_zerosize(&solv->dupmap);
3567   map_zerosize(&solv->dupinvolvedmap);
3568   solv->droporphanedmap_all = 0;
3569   map_zerosize(&solv->droporphanedmap);
3570   solv->allowuninstall_all = 0;
3571   map_zerosize(&solv->allowuninstallmap);
3572   map_zerosize(&solv->cleandepsmap);
3573   map_zerosize(&solv->weakrulemap);
3574   map_zerosize(&solv->favormap);
3575   map_zerosize(&solv->isdisfavormap);
3576   queue_empty(&solv->weakruleq);
3577   solv->watches = solv_free(solv->watches);
3578   queue_empty(&solv->ruletojob);
3579   if (solv->decisionq.count)
3580     memset(solv->decisionmap, 0, pool->nsolvables * sizeof(Id));
3581   queue_empty(&solv->decisionq);
3582   queue_empty(&solv->decisionq_why);
3583   queue_empty(&solv->decisionq_reason);
3584   queue_empty(&solv->learnt_why);
3585   queue_empty(&solv->learnt_pool);
3586   queue_empty(&solv->branches);
3587   solv->propagate_index = 0;
3588   queue_empty(&solv->problems);
3589   queue_empty(&solv->solutions);
3590   queue_empty(&solv->orphaned);
3591   solv->stats_learned = solv->stats_unsolvable = 0;
3592   if (solv->recommends_index)
3593     {
3594       map_empty(&solv->recommendsmap);
3595       map_empty(&solv->suggestsmap);
3596       queuep_free(&solv->recommendscplxq);
3597       queuep_free(&solv->suggestscplxq);
3598       solv->recommends_index = 0;
3599     }
3600   queuep_free(&solv->brokenorphanrules);
3601   solv->specialupdaters = solv_free(solv->specialupdaters);
3602
3603
3604   /*
3605    * create basic rule set of all involved packages
3606    * use addedmap bitmap to make sure we don't create rules twice
3607    */
3608
3609   /* create multiversion map if needed */
3610   solver_calculate_multiversionmap(pool, job, &solv->multiversion);
3611
3612   map_init(&addedmap, pool->nsolvables);
3613   MAPSET(&addedmap, SYSTEMSOLVABLE);
3614
3615   map_init(&installcandidatemap, pool->nsolvables);
3616   queue_init(&q);
3617
3618   now = solv_timems(0);
3619   /*
3620    * create rules for all package that could be involved with the solving
3621    * so called: pkg rules
3622    *
3623    */
3624   initialnrules = solv->pkgrules_end ? solv->pkgrules_end : 1;
3625   if (initialnrules > 1)
3626     deduceq2addedmap(solv, &addedmap);
3627   if (solv->nrules != initialnrules)
3628     solver_shrinkrules(solv, initialnrules);
3629   solv->nrules = initialnrules;
3630   solv->pkgrules_end = 0;
3631
3632   if (installed)
3633     {
3634       /* check for update/verify jobs as they need to be known early */
3635       /* also setup the droporphaned map, we need it when creating update rules */
3636       for (i = 0; i < job->count; i += 2)
3637         {
3638           how = job->elements[i];
3639           what = job->elements[i + 1];
3640           select = how & SOLVER_SELECTMASK;
3641           switch (how & SOLVER_JOBMASK)
3642             {
3643             case SOLVER_VERIFY:
3644               if (select == SOLVER_SOLVABLE_ALL || (select == SOLVER_SOLVABLE_REPO && installed && what == installed->repoid))
3645                 solv->fixmap_all = 1;
3646               FOR_JOB_SELECT(p, pp, select, what)
3647                 {
3648                   s = pool->solvables + p;
3649                   if (s->repo != installed)
3650                     continue;
3651                   if (!solv->fixmap.size)
3652                     map_grow(&solv->fixmap, installed->end - installed->start);
3653                   MAPSET(&solv->fixmap, p - installed->start);
3654                 }
3655               break;
3656             case SOLVER_UPDATE:
3657               if (select == SOLVER_SOLVABLE_ALL)
3658                 {
3659                   solv->updatemap_all = 1;
3660                   if (how & SOLVER_FORCEBEST)
3661                     solv->bestupdatemap_all = 1;
3662                   if (how & SOLVER_CLEANDEPS)
3663                     {
3664                       FOR_REPO_SOLVABLES(installed, p, s)
3665                         add_cleandeps_package(solv, p);
3666                     }
3667                 }
3668               else if (select == SOLVER_SOLVABLE_REPO)
3669                 {
3670                   Repo *repo = pool_id2repo(pool, what);
3671                   if (!repo)
3672                     break;
3673                   if (repo == installed && !(how & SOLVER_TARGETED))
3674                     {
3675                       solv->updatemap_all = 1;
3676                       if (how & SOLVER_FORCEBEST)
3677                         solv->bestupdatemap_all = 1;
3678                       if (how & SOLVER_CLEANDEPS)
3679                         {
3680                           FOR_REPO_SOLVABLES(installed, p, s)
3681                             add_cleandeps_package(solv, p);
3682                         }
3683                       break;
3684                     }
3685                   if (solv->noautotarget && !(how & SOLVER_TARGETED))
3686                     break;
3687                   /* targeted update */
3688                   FOR_REPO_SOLVABLES(repo, p, s)
3689                     add_update_target(solv, p, how);
3690                 }
3691               else
3692                 {
3693                   if (!(how & SOLVER_TARGETED))
3694                     {
3695                       int targeted = 1;
3696                       FOR_JOB_SELECT(p, pp, select, what)
3697                         {
3698                           s = pool->solvables + p;
3699                           if (s->repo != installed)
3700                             continue;
3701                           if (!solv->updatemap.size)
3702                             map_grow(&solv->updatemap, installed->end - installed->start);
3703                           MAPSET(&solv->updatemap, p - installed->start);
3704                           if (how & SOLVER_FORCEBEST)
3705                             {
3706                               if (!solv->bestupdatemap.size)
3707                                 map_grow(&solv->bestupdatemap, installed->end - installed->start);
3708                               MAPSET(&solv->bestupdatemap, p - installed->start);
3709                             }
3710                           if (how & SOLVER_CLEANDEPS)
3711                             add_cleandeps_package(solv, p);
3712                           targeted = 0;
3713                         }
3714                       if (!targeted || solv->noautotarget)
3715                         break;
3716                     }
3717                   FOR_JOB_SELECT(p, pp, select, what)
3718                     add_update_target(solv, p, how);
3719                 }
3720               break;
3721             case SOLVER_DROP_ORPHANED:
3722               if (select == SOLVER_SOLVABLE_ALL || (select == SOLVER_SOLVABLE_REPO && what == installed->repoid))
3723                 solv->droporphanedmap_all = 1;
3724               FOR_JOB_SELECT(p, pp, select, what)
3725                 {
3726                   s = pool->solvables + p;
3727                   if (s->repo != installed)
3728                     continue;
3729                   if (!solv->droporphanedmap.size)
3730                     map_grow(&solv->droporphanedmap, installed->end - installed->start);
3731                   MAPSET(&solv->droporphanedmap, p - installed->start);
3732                 }
3733               break;
3734             case SOLVER_ALLOWUNINSTALL:
3735               if (select == SOLVER_SOLVABLE_ALL || (select == SOLVER_SOLVABLE_REPO && installed && what == installed->repoid))
3736                 solv->allowuninstall_all = 1;
3737               FOR_JOB_SELECT(p, pp, select, what)
3738                 {
3739                   s = pool->solvables + p;
3740                   if (s->repo != installed)
3741                     continue;
3742                   if (!solv->allowuninstallmap.size)
3743                     map_grow(&solv->allowuninstallmap, installed->end - installed->start);
3744                   MAPSET(&solv->allowuninstallmap, p - installed->start);
3745                 }
3746               break;
3747             default:
3748               break;
3749             }
3750         }
3751
3752       if (solv->update_targets)
3753         transform_update_targets(solv);
3754
3755       oldnrules = solv->nrules;
3756       FOR_REPO_SOLVABLES(installed, p, s)
3757         solver_addpkgrulesforsolvable(solv, s, &addedmap);
3758       POOL_DEBUG(SOLV_DEBUG_STATS, "added %d pkg rules for installed solvables\n", solv->nrules - oldnrules);
3759       oldnrules = solv->nrules;
3760       FOR_REPO_SOLVABLES(installed, p, s)
3761         solver_addpkgrulesforupdaters(solv, s, &addedmap, 1);
3762       POOL_DEBUG(SOLV_DEBUG_STATS, "added %d pkg rules for updaters of installed solvables\n", solv->nrules - oldnrules);
3763     }
3764
3765   /*
3766    * create rules for all packages involved in the job
3767    * (to be installed or removed)
3768    */
3769
3770   oldnrules = solv->nrules;
3771   for (i = 0; i < job->count; i += 2)
3772     {
3773       how = job->elements[i];
3774       what = job->elements[i + 1];
3775       select = how & SOLVER_SELECTMASK;
3776
3777       switch (how & SOLVER_JOBMASK)
3778         {
3779         case SOLVER_INSTALL:
3780           FOR_JOB_SELECT(p, pp, select, what)
3781             {
3782               MAPSET(&installcandidatemap, p);
3783               solver_addpkgrulesforsolvable(solv, pool->solvables + p, &addedmap);
3784             }
3785           break;
3786         case SOLVER_DISTUPGRADE:
3787           if (select == SOLVER_SOLVABLE_ALL)
3788             {
3789               solv->dupmap_all = 1;
3790               solv->updatemap_all = 1;
3791               if (how & SOLVER_FORCEBEST)
3792                 solv->bestupdatemap_all = 1;
3793             }
3794           if ((how & SOLVER_TARGETED) != 0)
3795             needduprules = 1;
3796           if (!solv->dupmap_all || solv->allowuninstall || solv->allowuninstall_all || solv->allowuninstallmap.size || solv->keep_orphans)
3797             needduprules = 1;
3798           break;
3799         default:
3800           break;
3801         }
3802     }
3803   POOL_DEBUG(SOLV_DEBUG_STATS, "added %d pkg rules for packages involved in a job\n", solv->nrules - oldnrules);
3804
3805
3806   /*
3807    * add rules for suggests, enhances
3808    */
3809   oldnrules = solv->nrules;
3810   solver_addpkgrulesforweak(solv, &addedmap);
3811   POOL_DEBUG(SOLV_DEBUG_STATS, "added %d pkg rules because of weak dependencies\n", solv->nrules - oldnrules);
3812
3813 #ifdef ENABLE_LINKED_PKGS
3814   oldnrules = solv->nrules;
3815   solver_addpkgrulesforlinked(solv, &addedmap);
3816   POOL_DEBUG(SOLV_DEBUG_STATS, "added %d pkg rules because of linked packages\n", solv->nrules - oldnrules);
3817 #endif
3818
3819   /*
3820    * first pass done, we now have all the pkg rules we need.
3821    * unify existing rules before going over all job rules and
3822    * policy rules.
3823    * at this point the system is always solvable,
3824    * as an empty system (remove all packages) is a valid solution
3825    */
3826
3827   IF_POOLDEBUG (SOLV_DEBUG_STATS)
3828     {
3829       int possible = 0, installable = 0;
3830       for (i = 1; i < pool->nsolvables; i++)
3831         {
3832           if (pool_installable(pool, pool->solvables + i))
3833             installable++;
3834           if (MAPTST(&addedmap, i))
3835             possible++;
3836         }
3837       POOL_DEBUG(SOLV_DEBUG_STATS, "%d of %d installable solvables considered for solving\n", possible, installable);
3838     }
3839
3840   if (solv->nrules > initialnrules)
3841     solver_unifyrules(solv);                    /* remove duplicate pkg rules */
3842   solv->pkgrules_end = solv->nrules;            /* mark end of pkg rules */
3843
3844   if (solv->nrules > initialnrules)
3845     addedmap2deduceq(solv, &addedmap);          /* so that we can recreate the addedmap */
3846
3847   POOL_DEBUG(SOLV_DEBUG_STATS, "pkg rule memory used: %d K\n", solv->nrules * (int)sizeof(Rule) / 1024);
3848   POOL_DEBUG(SOLV_DEBUG_STATS, "pkg rule creation took %d ms\n", solv_timems(now));
3849
3850   /* create dup maps if needed. We need the maps early to create our
3851    * update rules */
3852   if (needduprules)
3853     solver_createdupmaps(solv);
3854
3855   /*
3856    * create feature rules
3857    *
3858    * foreach installed:
3859    *   create assertion (keep installed, if no update available)
3860    *   or
3861    *   create update rule (A|update1(A)|update2(A)|...)
3862    *
3863    * those are used later on to keep a version of the installed packages in
3864    * best effort mode
3865    */
3866
3867   solv->featurerules = solv->nrules;              /* mark start of feature rules */
3868   if (installed)
3869     {
3870       /* foreach possibly installed solvable */
3871       for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
3872         {
3873           if (s->repo != installed)
3874             {
3875               solver_addrule(solv, 0, 0, 0);    /* create dummy rule */
3876               continue;
3877             }
3878           solver_addfeaturerule(solv, s);
3879         }
3880       /* make sure we accounted for all rules */
3881       assert(solv->nrules - solv->featurerules == installed->end - installed->start);
3882     }
3883   solv->featurerules_end = solv->nrules;
3884
3885     /*
3886      * Add update rules for installed solvables
3887      *
3888      * almost identical to feature rules
3889      * except that downgrades/archchanges/vendorchanges are not allowed
3890      */
3891
3892   solv->updaterules = solv->nrules;
3893
3894   if (installed)
3895     { /* foreach installed solvables */
3896       /* we create all update rules, but disable some later on depending on the job */
3897       for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
3898         {
3899           Rule *sr;
3900
3901           if (s->repo != installed)
3902             {
3903               solver_addrule(solv, 0, 0, 0);    /* create dummy rule */
3904               continue;
3905             }
3906           solver_addupdaterule(solv, s);
3907           /*
3908            * check for and remove duplicate
3909            */
3910           r = solv->rules + solv->nrules - 1;           /* r: update rule */
3911           sr = r - (installed->end - installed->start); /* sr: feature rule */
3912           if (!r->p)
3913             {
3914               if (sr->p)
3915                 memset(sr, 0, sizeof(*sr));             /* no feature rules without update rules */
3916               continue;
3917             }
3918           /* it's also orphaned if the feature rule consists just of the installed package */
3919           if (!solv->dupmap_all && sr->p == i && !sr->d && !sr->w2)
3920             queue_push(&solv->orphaned, i);
3921
3922           if (!solver_rulecmp(solv, r, sr))
3923             memset(sr, 0, sizeof(*sr));         /* delete unneeded feature rule */
3924           else if (sr->p)
3925             solver_disablerule(solv, sr);       /* disable feature rule for now */
3926         }
3927       /* consistency check: we added a rule for _every_ installed solvable */
3928       assert(solv->nrules - solv->updaterules == installed->end - installed->start);
3929     }
3930   solv->updaterules_end = solv->nrules;
3931
3932
3933   /*
3934    * now add all job rules
3935    */
3936
3937   solv->jobrules = solv->nrules;
3938   for (i = 0; i < job->count; i += 2)
3939     {
3940       oldnrules = solv->nrules;
3941
3942       if (i && i == solv->pooljobcnt)
3943         POOL_DEBUG(SOLV_DEBUG_JOB, "end of pool jobs\n");
3944       how = job->elements[i];
3945       what = job->elements[i + 1];
3946       weak = how & SOLVER_WEAK;
3947       select = how & SOLVER_SELECTMASK;
3948       switch (how & SOLVER_JOBMASK)
3949         {
3950         case SOLVER_INSTALL:
3951           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sinstall %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
3952           if ((how & SOLVER_CLEANDEPS) != 0 && !solv->cleandepsmap.size && installed)
3953             map_grow(&solv->cleandepsmap, installed->end - installed->start);
3954           if (select == SOLVER_SOLVABLE)
3955             {
3956               p = what;
3957               d = 0;
3958             }
3959 #ifdef ENABLE_COMPLEX_DEPS
3960           else if ((select == SOLVER_SOLVABLE_PROVIDES || select == SOLVER_SOLVABLE_NAME) && pool_is_complex_dep(pool, what))
3961             {
3962               if (add_complex_jobrules(solv, what, select == SOLVER_SOLVABLE_NAME ? CPLXDEPS_NAME : 0, i, weak))
3963                 if (how & SOLVER_FORCEBEST)
3964                   hasbestinstalljob = 1;
3965               break;
3966             }
3967 #endif
3968           else
3969             {
3970               queue_empty(&q);
3971               FOR_JOB_SELECT(p, pp, select, what)
3972                 queue_push(&q, p);
3973               if (!q.count)
3974                 {
3975                   if (select == SOLVER_SOLVABLE_ONE_OF)
3976                     break;      /* ignore empty installs */
3977                   /* no candidate found or unsupported, make this an impossible rule */
3978                   queue_push(&q, -SYSTEMSOLVABLE);
3979                 }
3980               p = queue_shift(&q);      /* get first candidate */
3981               d = !q.count ? 0 : pool_queuetowhatprovides(pool, &q);    /* internalize */
3982             }
3983           /* force install of namespace supplements hack */
3984           if (select == SOLVER_SOLVABLE_PROVIDES && !d && (p == SYSTEMSOLVABLE || p == -SYSTEMSOLVABLE) && ISRELDEP(what))
3985             {
3986               Reldep *rd = GETRELDEP(pool, what);
3987               if (rd->flags == REL_NAMESPACE)
3988                 {
3989                   p = SYSTEMSOLVABLE;
3990                   if (!solv->installsuppdepq)
3991                     {
3992                       solv->installsuppdepq = solv_calloc(1, sizeof(Queue));
3993                       queue_init(solv->installsuppdepq);
3994                     }
3995                   queue_pushunique(solv->installsuppdepq, rd->evr == 0 ? rd->name : what);
3996                 }
3997             }
3998           solver_addjobrule(solv, p, 0, d, i, weak);
3999           if (how & SOLVER_FORCEBEST)
4000             hasbestinstalljob = 1;
4001           break;
4002         case SOLVER_ERASE:
4003           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %s%serase %s\n", weak ? "weak " : "", how & SOLVER_CLEANDEPS ? "clean deps " : "", solver_select2str(pool, select, what));
4004           if ((how & SOLVER_CLEANDEPS) != 0 && !solv->cleandepsmap.size && installed)
4005             map_grow(&solv->cleandepsmap, installed->end - installed->start);
4006           /* specific solvable: by id or by nevra */
4007           name = (select == SOLVER_SOLVABLE || (select == SOLVER_SOLVABLE_NAME && ISRELDEP(what))) ? 0 : -1;
4008           if (select == SOLVER_SOLVABLE_ALL)    /* hmmm ;) */
4009             {
4010               FOR_POOL_SOLVABLES(p)
4011                 solver_addjobrule(solv, -p, 0, 0, i, weak);
4012             }
4013           else if (select == SOLVER_SOLVABLE_REPO)
4014             {
4015               Repo *repo = pool_id2repo(pool, what);
4016               if (repo)
4017                 {
4018                   FOR_REPO_SOLVABLES(repo, p, s)
4019                     solver_addjobrule(solv, -p, 0, 0, i, weak);
4020                 }
4021             }
4022 #ifdef ENABLE_COMPLEX_DEPS
4023           else if ((select == SOLVER_SOLVABLE_PROVIDES || select == SOLVER_SOLVABLE_NAME) && pool_is_complex_dep(pool, what))
4024             {
4025               /* no special "erase a specific solvable" handling? */
4026               add_complex_jobrules(solv, what, select == SOLVER_SOLVABLE_NAME ? (CPLXDEPS_NAME | CPLXDEPS_TODNF | CPLXDEPS_INVERT) : (CPLXDEPS_TODNF | CPLXDEPS_INVERT), i, weak);
4027               break;
4028             }
4029 #endif
4030           FOR_JOB_SELECT(p, pp, select, what)
4031             {
4032               s = pool->solvables + p;
4033               if (installed && s->repo == installed)
4034                 name = !name ? s->name : -1;
4035               solver_addjobrule(solv, -p, 0, 0, i, weak);
4036             }
4037           /* special case for "erase a specific solvable": we also
4038            * erase all other solvables with that name, so that they
4039            * don't get picked up as replacement.
4040            * name is > 0 if exactly one installed solvable matched.
4041            */
4042           /* XXX: look also at packages that obsolete this package? */
4043           if (name > 0)
4044             {
4045               int j, k;
4046               k = solv->nrules;
4047               FOR_PROVIDES(p, pp, name)
4048                 {
4049                   s = pool->solvables + p;
4050                   if (s->name != name)
4051                     continue;
4052                   /* keep other versions installed */
4053                   if (s->repo == installed)
4054                     continue;
4055                   /* keep installcandidates of other jobs */
4056                   if (MAPTST(&installcandidatemap, p))
4057                     continue;
4058                   /* don't add the same rule twice */
4059                   for (j = oldnrules; j < k; j++)
4060                     if (solv->rules[j].p == -p)
4061                       break;
4062                   if (j == k)
4063                     solver_addjobrule(solv, -p, 0, 0, i, weak); /* remove by id */
4064                 }
4065             }
4066           break;
4067
4068         case SOLVER_UPDATE:
4069           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %supdate %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
4070           break;
4071         case SOLVER_VERIFY:
4072           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sverify %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
4073           break;
4074         case SOLVER_WEAKENDEPS:
4075           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sweaken deps %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
4076           if (select != SOLVER_SOLVABLE)
4077             break;
4078           s = pool->solvables + what;
4079           weaken_solvable_deps(solv, what);
4080           break;
4081         case SOLVER_MULTIVERSION:
4082           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %smultiversion %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
4083           break;
4084         case SOLVER_LOCK:
4085           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %slock %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
4086           if (select == SOLVER_SOLVABLE_ALL)
4087             {
4088               FOR_POOL_SOLVABLES(p)
4089                 solver_addjobrule(solv, installed && pool->solvables[p].repo == installed ? p : -p, 0, 0, i, weak);
4090             }
4091           else if (select == SOLVER_SOLVABLE_REPO)
4092             {
4093               Repo *repo = pool_id2repo(pool, what);
4094               if (repo)
4095                 {
4096                   FOR_REPO_SOLVABLES(repo, p, s)
4097                     solver_addjobrule(solv, installed && pool->solvables[p].repo == installed ? p : -p, 0, 0, i, weak);
4098                 }
4099             }
4100           FOR_JOB_SELECT(p, pp, select, what)
4101             solver_addjobrule(solv, installed && pool->solvables[p].repo == installed ? p : -p, 0, 0, i, weak);
4102           break;
4103         case SOLVER_DISTUPGRADE:
4104           POOL_DEBUG(SOLV_DEBUG_JOB, "job: distupgrade %s\n", solver_select2str(pool, select, what));
4105           break;
4106         case SOLVER_DROP_ORPHANED:
4107           POOL_DEBUG(SOLV_DEBUG_JOB, "job: drop orphaned %s\n", solver_select2str(pool, select, what));
4108           break;
4109         case SOLVER_USERINSTALLED:
4110           POOL_DEBUG(SOLV_DEBUG_JOB, "job: user installed %s\n", solver_select2str(pool, select, what));
4111           break;
4112         case SOLVER_ALLOWUNINSTALL:
4113           POOL_DEBUG(SOLV_DEBUG_JOB, "job: allowuninstall %s\n", solver_select2str(pool, select, what));
4114           break;
4115         case SOLVER_FAVOR:
4116         case SOLVER_DISFAVOR:
4117           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %s %s\n", (how & SOLVER_JOBMASK) == SOLVER_FAVOR ? "favor" : "disfavor", solver_select2str(pool, select, what));
4118           FOR_JOB_SELECT(p, pp, select, what)
4119             {
4120               int j;
4121               if (!solv->favorq)
4122                 {
4123                   solv->favorq = solv_calloc(1, sizeof(Queue));
4124                   queue_init(solv->favorq);
4125                 }
4126               j = solv->favorq->count + 1;
4127               queue_push2(solv->favorq, p, (how & SOLVER_JOBMASK) == SOLVER_FAVOR ? j : -j);
4128             }
4129           break;
4130         default:
4131           POOL_DEBUG(SOLV_DEBUG_JOB, "job: unknown job\n");
4132           break;
4133         }
4134
4135       IF_POOLDEBUG (SOLV_DEBUG_JOB)
4136         {
4137           int j;
4138           if (solv->nrules == oldnrules)
4139             POOL_DEBUG(SOLV_DEBUG_JOB, "  - no rule created\n");
4140           for (j = oldnrules; j < solv->nrules; j++)
4141             {
4142               POOL_DEBUG(SOLV_DEBUG_JOB, "  - job ");
4143               solver_printrule(solv, SOLV_DEBUG_JOB, solv->rules + j);
4144             }
4145         }
4146     }
4147   assert(solv->ruletojob.count == solv->nrules - solv->jobrules);
4148   solv->jobrules_end = solv->nrules;
4149
4150   /* transform favorq into two maps */
4151   if (solv->favorq)
4152     setup_favormaps(solv);
4153
4154   /* now create infarch and dup rules */
4155   if (!solv->noinfarchcheck)
4156     {
4157       solver_addinfarchrules(solv, &addedmap);
4158 #if 0
4159       if (pool->implicitobsoleteusescolors)
4160         {
4161           /* currently doesn't work well with infarch rules, so make
4162            * them weak */
4163           for (i = solv->infarchrules; i < solv->infarchrules_end; i++)
4164             queue_push(&solv->weakruleq, i);
4165         }
4166 #endif
4167     }
4168   else
4169     solv->infarchrules = solv->infarchrules_end = solv->nrules;
4170
4171   if (needduprules)
4172     solver_addduprules(solv, &addedmap);
4173   else
4174     solv->duprules = solv->duprules_end = solv->nrules;
4175
4176 #ifdef ENABLE_LINKED_PKGS
4177   if (solv->instbuddy && solv->updatemap.size)
4178     extend_updatemap_to_buddies(solv);
4179 #endif
4180
4181   if (solv->bestupdatemap_all || solv->bestupdatemap.size || hasbestinstalljob)
4182     solver_addbestrules(solv, hasbestinstalljob);
4183   else
4184     solv->bestrules = solv->bestrules_end = solv->nrules;
4185
4186   if (needduprules)
4187     solver_freedupmaps(solv);   /* no longer needed */
4188
4189   if (solv->do_yum_obsoletes)
4190     solver_addyumobsrules(solv);
4191   else
4192     solv->yumobsrules = solv->yumobsrules_end = solv->nrules;
4193
4194   if (1)
4195     solver_addchoicerules(solv);
4196   else
4197     solv->choicerules = solv->choicerules_end = solv->nrules;
4198
4199   if (0)
4200     {
4201       for (i = solv->featurerules; i < solv->nrules; i++)
4202         solver_printruleclass(solv, SOLV_DEBUG_RESULT, solv->rules + i);
4203     }
4204   /* all rules created
4205    * --------------------------------------------------------------
4206    * prepare for solving
4207    */
4208
4209   /* free unneeded memory */
4210   map_free(&addedmap);
4211   map_free(&installcandidatemap);
4212   queue_free(&q);
4213
4214   POOL_DEBUG(SOLV_DEBUG_STATS, "%d pkg rules, 2 * %d update rules, %d job rules, %d infarch rules, %d dup rules, %d choice rules, %d best rules\n", solv->pkgrules_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);
4215   POOL_DEBUG(SOLV_DEBUG_STATS, "overall rule memory used: %d K\n", solv->nrules * (int)sizeof(Rule) / 1024);
4216
4217   /* create weak map */
4218   if (solv->weakruleq.count)
4219     {
4220       map_grow(&solv->weakrulemap, solv->nrules);
4221       for (i = 0; i < solv->weakruleq.count; i++)
4222         {
4223           p = solv->weakruleq.elements[i];
4224           MAPSET(&solv->weakrulemap, p);
4225         }
4226     }
4227
4228   /* enable cleandepsmap creation if we have updatepkgs */
4229   if (solv->cleandeps_updatepkgs && !solv->cleandepsmap.size)
4230     map_grow(&solv->cleandepsmap, installed->end - installed->start);
4231   /* no mistakes */
4232   if (solv->cleandeps_mistakes)
4233     {
4234       queue_free(solv->cleandeps_mistakes);
4235       solv->cleandeps_mistakes = solv_free(solv->cleandeps_mistakes);
4236     }
4237
4238   /* all new rules are learnt after this point */
4239   solv->learntrules = solv->nrules;
4240
4241   /* create watches chains */
4242   makewatches(solv);
4243
4244   /* create assertion index. it is only used to speed up
4245    * makeruledecsions() a bit */
4246   for (i = 1, r = solv->rules + i; i < solv->nrules; i++, r++)
4247     if (r->p && !r->w2 && (r->d == 0 || r->d == -1))
4248       queue_push(&solv->ruleassertions, i);
4249
4250   /* disable update rules that conflict with our job */
4251   solver_disablepolicyrules(solv);
4252
4253   /* break orphans if requested */
4254   if (solv->dupmap_all && solv->orphaned.count && solv->break_orphans)
4255     solver_breakorphans(solv);
4256
4257   /*
4258    * ********************************************
4259    * solve!
4260    * ********************************************
4261    */
4262
4263   now = solv_timems(0);
4264   solver_run_sat(solv, 1, solv->dontinstallrecommended ? 0 : 1);
4265   POOL_DEBUG(SOLV_DEBUG_STATS, "solver took %d ms\n", solv_timems(now));
4266
4267   /*
4268    * prepare solution queue if there were problems
4269    */
4270   solver_prepare_solutions(solv);
4271
4272   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);
4273   POOL_DEBUG(SOLV_DEBUG_STATS, "solver_solve took %d ms\n", solv_timems(solve_start));
4274
4275   /* return number of problems */
4276   return solv->problems.count ? solv->problems.count / 2 : 0;
4277 }
4278
4279 Transaction *
4280 solver_create_transaction(Solver *solv)
4281 {
4282   return transaction_create_decisionq(solv->pool, &solv->decisionq, &solv->multiversion);
4283 }
4284
4285 void solver_get_orphaned(Solver *solv, Queue *orphanedq)
4286 {
4287   queue_free(orphanedq);
4288   queue_init_clone(orphanedq, &solv->orphaned);
4289 }
4290
4291 void solver_get_recommendations(Solver *solv, Queue *recommendationsq, Queue *suggestionsq, int noselected)
4292 {
4293   Pool *pool = solv->pool;
4294   Queue redoq, disabledq;
4295   int goterase, i;
4296   Solvable *s;
4297   Rule *r;
4298   Map obsmap;
4299
4300   if (!recommendationsq && !suggestionsq)
4301     return;
4302
4303   map_init(&obsmap, pool->nsolvables);
4304   if (solv->installed)
4305     {
4306       Id obs, *obsp, p, po, ppo;
4307       for (p = solv->installed->start; p < solv->installed->end; p++)
4308         {
4309           s = pool->solvables + p;
4310           if (s->repo != solv->installed || !s->obsoletes)
4311             continue;
4312           if (solv->decisionmap[p] <= 0)
4313             continue;
4314           if (solv->multiversion.size && MAPTST(&solv->multiversion, p))
4315             continue;
4316           obsp = s->repo->idarraydata + s->obsoletes;
4317           /* foreach obsoletes */
4318           while ((obs = *obsp++) != 0)
4319             FOR_PROVIDES(po, ppo, obs)
4320               MAPSET(&obsmap, po);
4321         }
4322     }
4323
4324   queue_init(&redoq);
4325   queue_init(&disabledq);
4326   goterase = 0;
4327   /* disable all erase jobs (including weak "keep uninstalled" rules) */
4328   for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++)
4329     {
4330       if (r->d < 0)     /* disabled ? */
4331         continue;
4332       if (r->p >= 0)    /* install job? */
4333         continue;
4334       queue_push(&disabledq, i);
4335       solver_disablerule(solv, r);
4336       goterase++;
4337     }
4338
4339   if (goterase)
4340     {
4341       enabledisablelearntrules(solv);
4342       removedisabledconflicts(solv, &redoq);
4343     }
4344
4345   /*
4346    * find recommended packages
4347    */
4348   if (recommendationsq)
4349     {
4350       Id rec, *recp, p, pp;
4351
4352       queue_empty(recommendationsq);
4353       /* create map of all recommened packages */
4354       solv->recommends_index = -1;
4355       MAPZERO(&solv->recommendsmap);
4356
4357       /* put all packages the solver already chose in the map */
4358       for (i = 1; i < solv->decisionq.count; i++)
4359         if ((p = solv->decisionq.elements[i]) > 0 && solv->decisionq_why.elements[i] == 0)
4360           {
4361             if (solv->decisionq_reason.elements[solv->decisionmap[p]] == SOLVER_REASON_WEAKDEP)
4362               MAPSET(&solv->recommendsmap, p);
4363           }
4364
4365       for (i = 0; i < solv->decisionq.count; i++)
4366         {
4367           p = solv->decisionq.elements[i];
4368           if (p < 0)
4369             continue;
4370           s = pool->solvables + p;
4371           if (s->recommends)
4372             {
4373               recp = s->repo->idarraydata + s->recommends;
4374               while ((rec = *recp++) != 0)
4375                 {
4376 #ifdef ENABLE_COMPLEX_DEPS
4377                   if (pool_is_complex_dep(pool, rec))
4378                     {
4379                       do_complex_recommendations(solv, rec, &solv->recommendsmap, noselected);
4380                       continue;
4381                     }
4382 #endif
4383                   FOR_PROVIDES(p, pp, rec)
4384                     if (solv->decisionmap[p] > 0)
4385                       break;
4386                   if (p)
4387                     {
4388                       if (!noselected)
4389                         {
4390                           FOR_PROVIDES(p, pp, rec)
4391                             if (solv->decisionmap[p] > 0)
4392                               MAPSET(&solv->recommendsmap, p);
4393                         }
4394                       continue; /* p != 0: already fulfilled */
4395                     }
4396                   FOR_PROVIDES(p, pp, rec)
4397                     MAPSET(&solv->recommendsmap, p);
4398                 }
4399             }
4400         }
4401       for (i = 1; i < pool->nsolvables; i++)
4402         {
4403           if (solv->decisionmap[i] < 0)
4404             continue;
4405           if (solv->decisionmap[i] > 0 && noselected)
4406             continue;
4407           if (MAPTST(&obsmap, i))
4408             continue;
4409           s = pool->solvables + i;
4410           if (!MAPTST(&solv->recommendsmap, i))
4411             {
4412               if (!s->supplements)
4413                 continue;
4414               if (!pool_installable(pool, s))
4415                 continue;
4416               if (!solver_is_supplementing(solv, s))
4417                 continue;
4418             }
4419           queue_push(recommendationsq, i);
4420         }
4421       /* we use MODE_SUGGEST here so that repo prio is ignored */
4422       policy_filter_unwanted(solv, recommendationsq, POLICY_MODE_SUGGEST);
4423     }
4424
4425   /*
4426    * find suggested packages
4427    */
4428
4429   if (suggestionsq)
4430     {
4431       Id sug, *sugp, p, pp;
4432
4433       queue_empty(suggestionsq);
4434       /* create map of all suggests that are still open */
4435       solv->recommends_index = -1;
4436       MAPZERO(&solv->suggestsmap);
4437       for (i = 0; i < solv->decisionq.count; i++)
4438         {
4439           p = solv->decisionq.elements[i];
4440           if (p < 0)
4441             continue;
4442           s = pool->solvables + p;
4443           if (s->suggests)
4444             {
4445               sugp = s->repo->idarraydata + s->suggests;
4446               while ((sug = *sugp++) != 0)
4447                 {
4448 #ifdef ENABLE_COMPLEX_DEPS
4449                   if (pool_is_complex_dep(pool, sug))
4450                     {
4451                       do_complex_recommendations(solv, sug, &solv->suggestsmap, noselected);
4452                       continue;
4453                     }
4454 #endif
4455                   FOR_PROVIDES(p, pp, sug)
4456                     if (solv->decisionmap[p] > 0)
4457                       break;
4458                   if (p)
4459                     {
4460                       if (!noselected)
4461                         {
4462                           FOR_PROVIDES(p, pp, sug)
4463                             if (solv->decisionmap[p] > 0)
4464                               MAPSET(&solv->suggestsmap, p);
4465                         }
4466                       continue; /* already fulfilled */
4467                     }
4468                   FOR_PROVIDES(p, pp, sug)
4469                     MAPSET(&solv->suggestsmap, p);
4470                 }
4471             }
4472         }
4473       for (i = 1; i < pool->nsolvables; i++)
4474         {
4475           if (solv->decisionmap[i] < 0)
4476             continue;
4477           if (solv->decisionmap[i] > 0 && noselected)
4478             continue;
4479           if (MAPTST(&obsmap, i))
4480             continue;
4481           s = pool->solvables + i;
4482           if (!MAPTST(&solv->suggestsmap, i))
4483             {
4484               if (!s->enhances)
4485                 continue;
4486               if (!pool_installable(pool, s))
4487                 continue;
4488               if (!solver_is_enhancing(solv, s))
4489                 continue;
4490             }
4491           queue_push(suggestionsq, i);
4492         }
4493       policy_filter_unwanted(solv, suggestionsq, POLICY_MODE_SUGGEST);
4494     }
4495
4496   /* undo removedisabledconflicts */
4497   if (redoq.count)
4498     undo_removedisabledconflicts(solv, &redoq);
4499   queue_free(&redoq);
4500
4501   /* undo job rule disabling */
4502   for (i = 0; i < disabledq.count; i++)
4503     solver_enablerule(solv, solv->rules + disabledq.elements[i]);
4504   queue_free(&disabledq);
4505   map_free(&obsmap);
4506 }
4507
4508
4509 /***********************************************************************/
4510 /* disk usage computations */
4511
4512 /*-------------------------------------------------------------------
4513  *
4514  * calculate DU changes
4515  */
4516
4517 void
4518 solver_calc_duchanges(Solver *solv, DUChanges *mps, int nmps)
4519 {
4520   Map installedmap;
4521
4522   solver_create_state_maps(solv, &installedmap, 0);
4523   pool_calc_duchanges(solv->pool, &installedmap, mps, nmps);
4524   map_free(&installedmap);
4525 }
4526
4527
4528 /*-------------------------------------------------------------------
4529  *
4530  * calculate changes in install size
4531  */
4532
4533 int
4534 solver_calc_installsizechange(Solver *solv)
4535 {
4536   Map installedmap;
4537   int change;
4538
4539   solver_create_state_maps(solv, &installedmap, 0);
4540   change = pool_calc_installsizechange(solv->pool, &installedmap);
4541   map_free(&installedmap);
4542   return change;
4543 }
4544
4545 void
4546 solver_create_state_maps(Solver *solv, Map *installedmap, Map *conflictsmap)
4547 {
4548   pool_create_state_maps(solv->pool, &solv->decisionq, installedmap, conflictsmap);
4549 }
4550
4551 /*-------------------------------------------------------------------
4552  *
4553  * decision introspection
4554  */
4555
4556 int
4557 solver_get_decisionlevel(Solver *solv, Id p)
4558 {
4559   return solv->decisionmap[p];
4560 }
4561
4562 void
4563 solver_get_decisionqueue(Solver *solv, Queue *decisionq)
4564 {
4565   queue_free(decisionq);
4566   queue_init_clone(decisionq, &solv->decisionq);
4567 }
4568
4569 int
4570 solver_get_lastdecisionblocklevel(Solver *solv)
4571 {
4572   Id p;
4573   if (solv->decisionq.count == 0)
4574     return 0;
4575   p = solv->decisionq.elements[solv->decisionq.count - 1];
4576   if (p < 0)
4577     p = -p;
4578   return solv->decisionmap[p] < 0 ? -solv->decisionmap[p] : solv->decisionmap[p];
4579 }
4580
4581 void
4582 solver_get_decisionblock(Solver *solv, int level, Queue *decisionq)
4583 {
4584   Id p;
4585   int i;
4586
4587   queue_empty(decisionq);
4588   for (i = 0; i < solv->decisionq.count; i++)
4589     {
4590       p = solv->decisionq.elements[i];
4591       if (p < 0)
4592         p = -p;
4593       if (solv->decisionmap[p] == level || solv->decisionmap[p] == -level)
4594         break;
4595     }
4596   if (i == solv->decisionq.count)
4597     return;
4598   for (i = 0; i < solv->decisionq.count; i++)
4599     {
4600       p = solv->decisionq.elements[i];
4601       if (p < 0)
4602         p = -p;
4603       if (solv->decisionmap[p] == level || solv->decisionmap[p] == -level)
4604         queue_push(decisionq, p);
4605       else
4606         break;
4607     }
4608 }
4609
4610 int
4611 solver_describe_decision(Solver *solv, Id p, Id *infop)
4612 {
4613   int i;
4614   Id pp, why;
4615
4616   if (infop)
4617     *infop = 0;
4618   if (!solv->decisionmap[p])
4619     return SOLVER_REASON_UNRELATED;
4620   pp = solv->decisionmap[p] < 0 ? -p : p;
4621   for (i = 0; i < solv->decisionq.count; i++)
4622     if (solv->decisionq.elements[i] == pp)
4623       break;
4624   if (i == solv->decisionq.count)       /* just in case... */
4625     return SOLVER_REASON_UNRELATED;
4626   why = solv->decisionq_why.elements[i];
4627   if (infop)
4628     *infop = why > 0 ? why : -why;
4629   if (why > 0)
4630     return SOLVER_REASON_UNIT_RULE;
4631   i = solv->decisionmap[p] >= 0 ? solv->decisionmap[p] : -solv->decisionmap[p];
4632   return solv->decisionq_reason.elements[i];
4633 }
4634
4635
4636 void
4637 solver_describe_weakdep_decision(Solver *solv, Id p, Queue *whyq)
4638 {
4639   Pool *pool = solv->pool;
4640   int i;
4641   int level = solv->decisionmap[p];
4642   int decisionno;
4643   Solvable *s;
4644
4645   queue_empty(whyq);
4646   if (level < 0)
4647     return;     /* huh? */
4648   for (decisionno = 0; decisionno < solv->decisionq.count; decisionno++)
4649     if (solv->decisionq.elements[decisionno] == p)
4650       break;
4651   if (decisionno == solv->decisionq.count)
4652     return;     /* huh? */
4653   i = solv->decisionmap[p] >= 0 ? solv->decisionmap[p] : -solv->decisionmap[p];
4654   if (solv->decisionq_reason.elements[i] != SOLVER_REASON_WEAKDEP)
4655     return;     /* huh? */
4656
4657   /* 1) list all packages that recommend us */
4658   for (i = 1; i < pool->nsolvables; i++)
4659     {
4660       Id *recp, rec, pp2, p2;
4661       if (solv->decisionmap[i] < 0 || solv->decisionmap[i] >= level)
4662         continue;
4663       s = pool->solvables + i;
4664       if (!s->recommends)
4665         continue;
4666       if (!solv->addalreadyrecommended && s->repo == solv->installed)
4667         continue;
4668       recp = s->repo->idarraydata + s->recommends;
4669       while ((rec = *recp++) != 0)
4670         {
4671           int found = 0;
4672           FOR_PROVIDES(p2, pp2, rec)
4673             {
4674               if (p2 == p)
4675                 found = 1;
4676               else
4677                 {
4678                   /* if p2 is already installed, this recommends is ignored */
4679                   if (solv->decisionmap[p2] > 0 && solv->decisionmap[p2] < level)
4680                     break;
4681                 }
4682             }
4683           if (!p2 && found)
4684             {
4685               queue_push(whyq, SOLVER_REASON_RECOMMENDED);
4686               queue_push2(whyq, i, rec);
4687             }
4688         }
4689     }
4690   /* 2) list all supplements */
4691   s = pool->solvables + p;
4692   if (s->supplements && level > 0)
4693     {
4694       Id *supp, sup, pp2, p2;
4695       /* this is a hack. to use solver_dep_fulfilled we temporarily clear
4696        * everything above our level in the decisionmap */
4697       for (i = decisionno; i < solv->decisionq.count; i++ )
4698         {
4699           p2 = solv->decisionq.elements[i];
4700           if (p2 > 0)
4701             solv->decisionmap[p2] = -solv->decisionmap[p2];
4702         }
4703       supp = s->repo->idarraydata + s->supplements;
4704       while ((sup = *supp++) != 0)
4705         if (solver_dep_fulfilled(solv, sup))
4706           {
4707             int found = 0;
4708             /* let's see if this is an easy supp */
4709             FOR_PROVIDES(p2, pp2, sup)
4710               {
4711                 if (!solv->addalreadyrecommended && solv->installed)
4712                   {
4713                     if (pool->solvables[p2].repo == solv->installed)
4714                       continue;
4715                   }
4716                 if (solv->decisionmap[p2] > 0 && solv->decisionmap[p2] < level)
4717                   {
4718                     queue_push(whyq, SOLVER_REASON_SUPPLEMENTED);
4719                     queue_push2(whyq, p2, sup);
4720                     found = 1;
4721                   }
4722               }
4723             if (!found)
4724               {
4725                 /* hard case, just note dependency with no package */
4726                 queue_push(whyq, SOLVER_REASON_SUPPLEMENTED);
4727                 queue_push2(whyq, 0, sup);
4728               }
4729           }
4730       for (i = decisionno; i < solv->decisionq.count; i++)
4731         {
4732           p2 = solv->decisionq.elements[i];
4733           if (p2 > 0)
4734             solv->decisionmap[p2] = -solv->decisionmap[p2];
4735         }
4736     }
4737 }
4738
4739 void
4740 pool_job2solvables(Pool *pool, Queue *pkgs, Id how, Id what)
4741 {
4742   Id p, pp;
4743   how &= SOLVER_SELECTMASK;
4744   queue_empty(pkgs);
4745   if (how == SOLVER_SOLVABLE_ALL)
4746     {
4747       FOR_POOL_SOLVABLES(p)
4748         queue_push(pkgs, p);
4749     }
4750   else if (how == SOLVER_SOLVABLE_REPO)
4751     {
4752       Repo *repo = pool_id2repo(pool, what);
4753       Solvable *s;
4754       if (repo)
4755         {
4756           FOR_REPO_SOLVABLES(repo, p, s)
4757             queue_push(pkgs, p);
4758         }
4759     }
4760   else
4761     {
4762       FOR_JOB_SELECT(p, pp, how, what)
4763         queue_push(pkgs, p);
4764     }
4765 }
4766
4767 int
4768 pool_isemptyupdatejob(Pool *pool, Id how, Id what)
4769 {
4770   Id p, pp, pi, pip;
4771   Id select = how & SOLVER_SELECTMASK;
4772   if ((how & SOLVER_JOBMASK) != SOLVER_UPDATE)
4773     return 0;
4774   if (select == SOLVER_SOLVABLE_ALL || select == SOLVER_SOLVABLE_REPO)
4775     return 0;
4776   if (!pool->installed)
4777     return 1;
4778   FOR_JOB_SELECT(p, pp, select, what)
4779     if (pool->solvables[p].repo == pool->installed)
4780       return 0;
4781   /* hard work */
4782   FOR_JOB_SELECT(p, pp, select, what)
4783     {
4784       Solvable *s = pool->solvables + p;
4785       FOR_PROVIDES(pi, pip, s->name)
4786         {
4787           Solvable *si = pool->solvables + pi;
4788           if (si->repo != pool->installed || si->name != s->name)
4789             continue;
4790           return 0;
4791         }
4792       if (s->obsoletes)
4793         {
4794           Id obs, *obsp = s->repo->idarraydata + s->obsoletes;
4795           while ((obs = *obsp++) != 0)
4796             {
4797               FOR_PROVIDES(pi, pip, obs)
4798                 {
4799                   Solvable *si = pool->solvables + pi;
4800                   if (si->repo != pool->installed)
4801                     continue;
4802                   if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, si, obs))
4803                     continue;
4804                   if (pool->obsoleteusescolors && !pool_colormatch(pool, s, si))
4805                     continue;
4806                   return 0;
4807                 }
4808             }
4809         }
4810     }
4811   return 1;
4812 }
4813
4814 static int
4815 get_userinstalled_cmp(const void *ap, const void *bp, void *dp)
4816 {
4817   return *(Id *)ap - *(Id *)bp;
4818 }
4819
4820 static int
4821 get_userinstalled_cmp_names(const void *ap, const void *bp, void *dp)
4822 {
4823   Pool *pool = dp;
4824   return strcmp(pool_id2str(pool, *(Id *)ap), pool_id2str(pool, *(Id *)bp));
4825 }
4826
4827 static int
4828 get_userinstalled_cmp_namearch(const void *ap, const void *bp, void *dp)
4829 {
4830   Pool *pool = dp;
4831   int r;
4832   r = strcmp(pool_id2str(pool, ((Id *)ap)[0]), pool_id2str(pool, ((Id *)bp)[0]));
4833   if (r)
4834     return r;
4835   return strcmp(pool_id2str(pool, ((Id *)ap)[1]), pool_id2str(pool, ((Id *)bp)[1]));
4836 }
4837
4838 static void
4839 get_userinstalled_sort_uniq(Pool *pool, Queue *q, int flags)
4840 {
4841   Id lastp = -1, lasta = -1;
4842   int i, j;
4843   if (q->count < ((flags & GET_USERINSTALLED_NAMEARCH) ? 4 : 2))
4844     return;
4845   if ((flags & GET_USERINSTALLED_NAMEARCH) != 0)
4846     solv_sort(q->elements, q->count / 2, 2 * sizeof(Id), get_userinstalled_cmp_namearch, pool);
4847   else if ((flags & GET_USERINSTALLED_NAMES) != 0)
4848     solv_sort(q->elements, q->count, sizeof(Id), get_userinstalled_cmp_names, pool);
4849   else
4850     solv_sort(q->elements, q->count, sizeof(Id), get_userinstalled_cmp, 0);
4851   if ((flags & GET_USERINSTALLED_NAMEARCH) != 0)
4852     {
4853       for (i = j = 0; i < q->count; i += 2)
4854         if (q->elements[i] != lastp || q->elements[i + 1] != lasta)
4855           {
4856             q->elements[j++] = lastp = q->elements[i];
4857             q->elements[j++] = lasta = q->elements[i + 1];
4858           }
4859     }
4860   else
4861     {
4862       for (i = j = 0; i < q->count; i++)
4863         if (q->elements[i] != lastp)
4864           q->elements[j++] = lastp = q->elements[i];
4865     }
4866   queue_truncate(q, j);
4867 }
4868
4869 static void
4870 namearch2solvables(Pool *pool, Queue *q, Queue *qout, int job)
4871 {
4872   int i;
4873   if (!pool->installed)
4874     return;
4875   for (i = 0; i < q->count; i += 2)
4876     {
4877       Id p, pp, name = q->elements[i], arch = q->elements[i + 1];
4878       FOR_PROVIDES(p, pp, name)
4879         {
4880           Solvable *s = pool->solvables + p;
4881           if (s->repo != pool->installed || s->name != name || (arch && s->arch != arch))
4882             continue;
4883           if (job)
4884             queue_push(qout, job);
4885           queue_push(qout, p);
4886         }
4887     }
4888 }
4889
4890 void
4891 solver_get_userinstalled(Solver *solv, Queue *q, int flags)
4892 {
4893   Pool *pool = solv->pool;
4894   Id p, p2, pp;
4895   Solvable *s;
4896   Repo *installed = solv->installed;
4897   int i, j;
4898   Map userinstalled;
4899
4900   map_init(&userinstalled, 0);
4901   queue_empty(q);
4902   /* first process jobs */
4903   for (i = 0; i < solv->job.count; i += 2)
4904     {
4905       Id how = solv->job.elements[i];
4906       Id what, select;
4907       if (installed && (how & SOLVER_JOBMASK) == SOLVER_USERINSTALLED)
4908         {
4909           if (!userinstalled.size)
4910             map_grow(&userinstalled, installed->end - installed->start);
4911           what = solv->job.elements[i + 1];
4912           select = how & SOLVER_SELECTMASK;
4913           if (select == SOLVER_SOLVABLE_ALL || (select == SOLVER_SOLVABLE_REPO && what == installed->repoid))
4914             {
4915               FOR_REPO_SOLVABLES(installed, p, s)
4916                 MAPSET(&userinstalled, p - installed->start);
4917             }
4918           FOR_JOB_SELECT(p, pp, select, what)
4919             if (pool->solvables[p].repo == installed)
4920               MAPSET(&userinstalled, p - installed->start);
4921           continue;
4922         }
4923       if ((how & SOLVER_JOBMASK) != SOLVER_INSTALL)
4924         continue;
4925       if ((how & SOLVER_NOTBYUSER) != 0)
4926         continue;
4927       what = solv->job.elements[i + 1];
4928       select = how & SOLVER_SELECTMASK;
4929       FOR_JOB_SELECT(p, pp, select, what)
4930         if (solv->decisionmap[p] > 0)
4931           {
4932             queue_push(q, p);
4933 #ifdef ENABLE_LINKED_PKGS
4934             if (has_package_link(pool, pool->solvables + p))
4935               {
4936                 int j;
4937                 Queue lq;
4938                 queue_init(&lq);
4939                 find_package_link(pool, pool->solvables + p, 0, &lq, 0, 0);
4940                 for (j = 0; j < lq.count; j++)
4941                   if (solv->decisionmap[lq.elements[j]] > 0)
4942                     queue_push(q, lq.elements[j]);
4943               }
4944 #endif
4945           }
4946     }
4947   /* now process updates of userinstalled packages */
4948   if (installed && userinstalled.size)
4949     {
4950       for (i = 1; i < solv->decisionq.count; i++)
4951         {
4952           p = solv->decisionq.elements[i];
4953           if (p <= 0)
4954             continue;
4955           s = pool->solvables + p;
4956           if (!s->repo)
4957             continue;
4958           if (s->repo == installed)
4959             {
4960               if (MAPTST(&userinstalled, p - installed->start))
4961                 queue_push(q, p);
4962               continue;
4963             }
4964           /* new package, check if we replace a userinstalled one */
4965           FOR_PROVIDES(p2, pp, s->name)
4966             {
4967               Solvable *ps = pool->solvables + p2;
4968               if (p2 == p || ps->repo != installed || !MAPTST(&userinstalled, p2 - installed->start))
4969                 continue;
4970               if (!pool->implicitobsoleteusesprovides && s->name != ps->name)
4971                 continue;
4972               if (pool->implicitobsoleteusescolors && !pool_colormatch(pool, s, ps))
4973                 continue;
4974               queue_push(q, p);
4975               break;
4976             }
4977           if (!p2 && s->repo != installed && s->obsoletes)
4978             {
4979               Id obs, *obsp = s->repo->idarraydata + s->obsoletes;
4980               while ((obs = *obsp++) != 0)
4981                 {
4982                   FOR_PROVIDES(p2, pp, obs)
4983                     {
4984                       Solvable *ps = pool->solvables + p2;
4985                       if (p2 == p || ps->repo != installed || !MAPTST(&userinstalled, p2 - installed->start))
4986                         continue;
4987                       if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
4988                         continue;
4989                       if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
4990                         continue;
4991                       queue_push(q, p);
4992                       break;
4993                     }
4994                   if (p2)
4995                     break;
4996                 }
4997             }
4998         }
4999     }
5000   map_free(&userinstalled);
5001
5002   /* convert to desired output format */
5003   if ((flags & GET_USERINSTALLED_NAMEARCH) != 0)
5004     {
5005       int qcount = q->count;
5006       queue_insertn(q, 0, qcount, 0);
5007       for (i = j = 0; i < qcount; i++)
5008         {
5009           s = pool->solvables + q->elements[i + qcount];
5010           q->elements[j++] = s->name;
5011           q->elements[j++] = s->arch;
5012         }
5013     }
5014   else if ((flags & GET_USERINSTALLED_NAMES) != 0)
5015     {
5016       for (i = 0; i < q->count; i++)
5017         {
5018           s = pool->solvables + q->elements[i];
5019           q->elements[i] = s->name;
5020         }
5021     }
5022   /* sort and unify */
5023   get_userinstalled_sort_uniq(pool, q, flags);
5024
5025   /* invert if asked for */
5026   if ((flags & GET_USERINSTALLED_INVERTED) != 0)
5027     {
5028       /* first generate queue with all installed packages */
5029       Queue invq;
5030       queue_init(&invq);
5031       for (i = 1; i < solv->decisionq.count; i++)
5032         {
5033           p = solv->decisionq.elements[i];
5034           if (p <= 0)
5035             continue;
5036           s = pool->solvables + p;
5037           if (!s->repo)
5038             continue;
5039           if ((flags & GET_USERINSTALLED_NAMEARCH) != 0)
5040             queue_push2(&invq, s->name, s->arch);
5041           else if ((flags & GET_USERINSTALLED_NAMES) != 0)
5042             queue_push(&invq, s->name);
5043           else
5044             queue_push(&invq, p);
5045         }
5046       /* push q on invq, just in case... */
5047       queue_insertn(&invq, invq.count, q->count, q->elements);
5048       get_userinstalled_sort_uniq(pool, &invq, flags);
5049       /* subtract queues (easy as they are sorted and invq is a superset of q) */
5050       if ((flags & GET_USERINSTALLED_NAMEARCH) != 0)
5051         {
5052           if (q->count)
5053             {
5054               for (i = j = 0; i < invq.count; i += 2)
5055                 if (invq.elements[i] == q->elements[j] && invq.elements[i + 1] == q->elements[j + 1])
5056                   {
5057                     invq.elements[i] = invq.elements[i + 1] = 0;
5058                     j += 2;
5059                     if (j >= q->count)
5060                       break;
5061                   }
5062               queue_empty(q);
5063             }
5064           for (i = 0; i < invq.count; i += 2)
5065             if (invq.elements[i])
5066               queue_push2(q, invq.elements[i], invq.elements[i + 1]);
5067         }
5068       else
5069         {
5070           if (q->count)
5071             {
5072               for (i = j = 0; i < invq.count; i++)
5073                 if (invq.elements[i] == q->elements[j])
5074                   {
5075                     invq.elements[i] = 0;
5076                     if (++j >= q->count)
5077                       break;
5078                   }
5079               queue_empty(q);
5080             }
5081           for (i = 0; i < invq.count; i++)
5082             if (invq.elements[i])
5083               queue_push(q, invq.elements[i]);
5084         }
5085       queue_free(&invq);
5086     }
5087 }
5088
5089 void
5090 pool_add_userinstalled_jobs(Pool *pool, Queue *q, Queue *job, int flags)
5091 {
5092   int i;
5093
5094   if ((flags & GET_USERINSTALLED_INVERTED) != 0)
5095     {
5096       Queue invq;
5097       Id p, lastid;
5098       Solvable *s;
5099       int bad;
5100       if (!pool->installed)
5101         return;
5102       queue_init(&invq);
5103       if ((flags & GET_USERINSTALLED_NAMEARCH) != 0)
5104         flags &= ~GET_USERINSTALLED_NAMES;      /* just in case */
5105       FOR_REPO_SOLVABLES(pool->installed, p, s)
5106         queue_push(&invq, flags & GET_USERINSTALLED_NAMES ? s->name : p);
5107       if ((flags & GET_USERINSTALLED_NAMEARCH) != 0)
5108         {
5109           /* for namearch we convert to packages */
5110           namearch2solvables(pool, q, &invq, 0);
5111           get_userinstalled_sort_uniq(pool, &invq, flags);
5112           namearch2solvables(pool, q, &invq, 0);
5113           flags = 0;
5114         }
5115       else
5116         {
5117           queue_insertn(&invq, invq.count, q->count, q->elements);
5118           get_userinstalled_sort_uniq(pool, &invq, flags);
5119           /* now the fun part, add q again, sort, and remove all dups */
5120           queue_insertn(&invq, invq.count, q->count, q->elements);
5121         }
5122       if (invq.count > 1)
5123         {
5124           if ((flags & GET_USERINSTALLED_NAMES) != 0)
5125             solv_sort(invq.elements, invq.count, sizeof(Id), get_userinstalled_cmp_names, pool);
5126           else
5127             solv_sort(invq.elements, invq.count, sizeof(Id), get_userinstalled_cmp, 0);
5128         }
5129       lastid = -1;
5130       bad = 1;
5131       for (i = 0; i < invq.count; i++)
5132         {
5133           if (invq.elements[i] == lastid)
5134             {
5135               bad = 1;
5136               continue;
5137             }
5138           if (!bad)
5139             queue_push2(job, SOLVER_USERINSTALLED | (flags & GET_USERINSTALLED_NAMES ? SOLVER_SOLVABLE_NAME : SOLVER_SOLVABLE), lastid);
5140           bad = 0;
5141           lastid = invq.elements[i];
5142         }
5143       if (!bad)
5144         queue_push2(job, SOLVER_USERINSTALLED | (flags & GET_USERINSTALLED_NAMES ? SOLVER_SOLVABLE_NAME : SOLVER_SOLVABLE), lastid);
5145       queue_free(&invq);
5146     }
5147   else
5148     {
5149       if (flags & GET_USERINSTALLED_NAMEARCH)
5150         namearch2solvables(pool, q, job, SOLVER_USERINSTALLED | SOLVER_SOLVABLE);
5151       else
5152         {
5153           for (i = 0; i < q->count; i++)
5154             queue_push2(job, SOLVER_USERINSTALLED | (flags & GET_USERINSTALLED_NAMES ? SOLVER_SOLVABLE_NAME : SOLVER_SOLVABLE), q->elements[i]);
5155         }
5156     }
5157 }
5158
5159 int
5160 solver_alternatives_count(Solver *solv)
5161 {
5162   Id *elements = solv->branches.elements;
5163   int res, count;
5164   for (res = 0, count = solv->branches.count; count; res++)
5165     count -= elements[count - 2];
5166   return res;
5167 }
5168
5169 int
5170 solver_get_alternative(Solver *solv, Id alternative, Id *idp, Id *fromp, Id *chosenp, Queue *choices, int *levelp)
5171 {
5172   int cnt = solver_alternatives_count(solv);
5173   int count = solv->branches.count;
5174   Id *elements = solv->branches.elements;
5175   if (choices)
5176     queue_empty(choices);
5177   if (alternative <= 0 || alternative > cnt)
5178     return 0;
5179   elements += count;
5180   for (; cnt > alternative; cnt--)
5181     elements -= elements[-2];
5182   if (levelp)
5183     *levelp = elements[-1];
5184   if (fromp)
5185     *fromp = elements[-4];
5186   if (idp)
5187     *idp = elements[-3];
5188   if (chosenp)
5189     {
5190       int i;
5191       *chosenp = 0;
5192       for (i = elements[-2]; i > 4; i--)
5193         {
5194           Id p = -elements[-i];
5195           if (p > 0 && solv->decisionmap[p] == elements[-1] + 1)
5196             {
5197               *chosenp = p;
5198               break;
5199             }
5200         }
5201     }
5202   if (choices)
5203     queue_insertn(choices, 0, elements[-2] - 4, elements - elements[-2]);
5204   return elements[-4] ? SOLVER_ALTERNATIVE_TYPE_RECOMMENDS : SOLVER_ALTERNATIVE_TYPE_RULE;
5205 }
5206
5207 const char *
5208 solver_select2str(Pool *pool, Id select, Id what)
5209 {
5210   const char *s;
5211   char *b;
5212   select &= SOLVER_SELECTMASK;
5213   if (select == SOLVER_SOLVABLE)
5214     return pool_solvid2str(pool, what);
5215   if (select == SOLVER_SOLVABLE_NAME)
5216     return pool_dep2str(pool, what);
5217   if (select == SOLVER_SOLVABLE_PROVIDES)
5218     {
5219       s = pool_dep2str(pool, what);
5220       b = pool_alloctmpspace(pool, 11 + strlen(s));
5221       sprintf(b, "providing %s", s);
5222       return b;
5223     }
5224   if (select == SOLVER_SOLVABLE_ONE_OF)
5225     {
5226       Id p;
5227       b = 0;
5228       while ((p = pool->whatprovidesdata[what++]) != 0)
5229         {
5230           s = pool_solvid2str(pool, p);
5231           if (b)
5232             b = pool_tmpappend(pool, b, ", ", s);
5233           else
5234             b = pool_tmpjoin(pool, s, 0, 0);
5235           pool_freetmpspace(pool, s);
5236         }
5237       return b ? b : "nothing";
5238     }
5239   if (select == SOLVER_SOLVABLE_REPO)
5240     {
5241       b = pool_alloctmpspace(pool, 20);
5242       sprintf(b, "repo #%d", what);
5243       return b;
5244     }
5245   if (select == SOLVER_SOLVABLE_ALL)
5246     return "all packages";
5247   return "unknown job select";
5248 }
5249
5250 const char *
5251 pool_job2str(Pool *pool, Id how, Id what, Id flagmask)
5252 {
5253   Id select = how & SOLVER_SELECTMASK;
5254   const char *strstart = 0, *strend = 0;
5255   char *s;
5256   int o;
5257
5258   switch (how & SOLVER_JOBMASK)
5259     {
5260     case SOLVER_NOOP:
5261       return "do nothing";
5262     case SOLVER_INSTALL:
5263       if (select == SOLVER_SOLVABLE && pool->installed && pool->solvables[what].repo == pool->installed)
5264         strstart = "keep ", strend = " installed";
5265       else if (select == SOLVER_SOLVABLE || select == SOLVER_SOLVABLE_NAME)
5266         strstart = "install ";
5267       else if (select == SOLVER_SOLVABLE_PROVIDES)
5268         strstart = "install a package ";
5269       else
5270         strstart = "install one of ";
5271       break;
5272     case SOLVER_ERASE:
5273       if (select == SOLVER_SOLVABLE && !(pool->installed && pool->solvables[what].repo == pool->installed))
5274         strstart = "keep ", strend = " uninstalled";
5275       else if (select == SOLVER_SOLVABLE_PROVIDES)
5276         strstart = "deinstall all packages ";
5277       else
5278         strstart = "deinstall ";
5279       break;
5280     case SOLVER_UPDATE:
5281       strstart = "update ";
5282       break;
5283     case SOLVER_WEAKENDEPS:
5284       strstart = "weaken deps of ";
5285       break;
5286     case SOLVER_MULTIVERSION:
5287       strstart = "multi version ";
5288       break;
5289     case SOLVER_LOCK:
5290       strstart = "lock ";
5291       break;
5292     case SOLVER_DISTUPGRADE:
5293       strstart = "dist upgrade ";
5294       break;
5295     case SOLVER_VERIFY:
5296       strstart = "verify ";
5297       break;
5298     case SOLVER_DROP_ORPHANED:
5299       strstart = "deinstall ", strend = " if orphaned";
5300       break;
5301     case SOLVER_USERINSTALLED:
5302       strstart = "regard ", strend = " as userinstalled";
5303       break;
5304     case SOLVER_ALLOWUNINSTALL:
5305       strstart = "allow deinstallation of ";
5306       break;
5307     case SOLVER_FAVOR:
5308       strstart = "favor ";
5309       break;
5310     case SOLVER_DISFAVOR:
5311       strstart = "disfavor ";
5312       break;
5313     default:
5314       strstart = "unknown job ";
5315       break;
5316     }
5317   s = pool_tmpjoin(pool, strstart, solver_select2str(pool, select, what), strend);
5318   how &= flagmask;
5319   if ((how & ~(SOLVER_SELECTMASK|SOLVER_JOBMASK)) == 0)
5320     return s;
5321   o = strlen(s);
5322   s = pool_tmpappend(pool, s, " ", 0);
5323   if (how & SOLVER_WEAK)
5324     s = pool_tmpappend(pool, s, ",weak", 0);
5325   if (how & SOLVER_ESSENTIAL)
5326     s = pool_tmpappend(pool, s, ",essential", 0);
5327   if (how & SOLVER_CLEANDEPS)
5328     s = pool_tmpappend(pool, s, ",cleandeps", 0);
5329   if (how & SOLVER_ORUPDATE)
5330     s = pool_tmpappend(pool, s, ",orupdate", 0);
5331   if (how & SOLVER_FORCEBEST)
5332     s = pool_tmpappend(pool, s, ",forcebest", 0);
5333   if (how & SOLVER_TARGETED)
5334     s = pool_tmpappend(pool, s, ",targeted", 0);
5335   if (how & SOLVER_SETEV)
5336     s = pool_tmpappend(pool, s, ",setev", 0);
5337   if (how & SOLVER_SETEVR)
5338     s = pool_tmpappend(pool, s, ",setevr", 0);
5339   if (how & SOLVER_SETARCH)
5340     s = pool_tmpappend(pool, s, ",setarch", 0);
5341   if (how & SOLVER_SETVENDOR)
5342     s = pool_tmpappend(pool, s, ",setvendor", 0);
5343   if (how & SOLVER_SETREPO)
5344     s = pool_tmpappend(pool, s, ",setrepo", 0);
5345   if (how & SOLVER_SETNAME)
5346     s = pool_tmpappend(pool, s, ",setname", 0);
5347   if (how & SOLVER_NOAUTOSET)
5348     s = pool_tmpappend(pool, s, ",noautoset", 0);
5349   if (s[o + 1] != ',')
5350     s = pool_tmpappend(pool, s, ",?", 0);
5351   s[o + 1] = '[';
5352   return pool_tmpappend(pool, s, "]", 0);
5353 }
5354
5355 const char *
5356 solver_alternative2str(Solver *solv, int type, Id id, Id from)
5357 {
5358   Pool *pool = solv->pool;
5359   if (type == SOLVER_ALTERNATIVE_TYPE_RECOMMENDS)
5360     {
5361       const char *s = pool_dep2str(pool, id);
5362       return pool_tmpappend(pool, s, ", recommended by ", pool_solvid2str(pool, from));
5363     }
5364   if (type == SOLVER_ALTERNATIVE_TYPE_RULE)
5365     {
5366       int rtype;
5367       Id depfrom, depto, dep;
5368       char buf[64];
5369       if (solver_ruleclass(solv, id) == SOLVER_RULE_CHOICE)
5370         id = solver_rule2pkgrule(solv, id);
5371       rtype = solver_ruleinfo(solv, id, &depfrom, &depto, &dep);
5372       if ((rtype & SOLVER_RULE_TYPEMASK) == SOLVER_RULE_JOB)
5373         {
5374           if ((depto & SOLVER_SELECTMASK) == SOLVER_SOLVABLE_PROVIDES)
5375             return pool_dep2str(pool, dep);
5376           return solver_select2str(pool, depto & SOLVER_SELECTMASK, dep);
5377         }
5378       if (rtype == SOLVER_RULE_PKG_REQUIRES)
5379         {
5380           const char *s = pool_dep2str(pool, dep);
5381           return pool_tmpappend(pool, s, ", required by ", pool_solvid2str(pool, depfrom));
5382         }
5383       sprintf(buf, "Rule #%d", id);
5384       return pool_tmpjoin(pool, buf, 0, 0);
5385     }
5386   return "unknown alternative type";
5387 }
5388