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