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 }
1436
1437 /*-------------------------------------------------------------------
1438  *
1439  * branch handling
1440  */
1441
1442 static void
1443 createbranch(Solver *solv, int level, Queue *dq, Id p, Id data)
1444 {
1445   Pool *pool = solv->pool;
1446   int i;
1447   IF_POOLDEBUG (SOLV_DEBUG_POLICY)
1448     {
1449       POOL_DEBUG (SOLV_DEBUG_POLICY, "creating a branch:\n");
1450       for (i = 0; i < dq->count; i++)
1451         POOL_DEBUG (SOLV_DEBUG_POLICY, "  - %s\n", pool_solvid2str(pool, dq->elements[i]));
1452     }
1453   queue_push(&solv->branches, -dq->elements[0]);
1454   for (i = 1; i < dq->count; i++)
1455     queue_push(&solv->branches, dq->elements[i]);
1456   queue_push2(&solv->branches, p, data);
1457   queue_push2(&solv->branches, dq->count + 4, level);
1458 }
1459
1460 static int
1461 takebranch(Solver *solv, int pos, int end, const char *msg, int disablerules)
1462 {
1463   Pool *pool = solv->pool;
1464   int level;
1465   Id p, why;
1466 #if 0
1467   {
1468     int i;
1469     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]);
1470     for (i = end - solv->branches.elements[end - 2]; i < end - 4; i++)
1471       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]));
1472   }
1473 #endif
1474   level = solv->branches.elements[end - 1];
1475   p = solv->branches.elements[pos];
1476   solv->branches.elements[pos] = -p;
1477   POOL_DEBUG(SOLV_DEBUG_SOLVER, "%s %d -> %d with %s\n", msg, solv->decisionmap[p], level, pool_solvid2str(pool, p));
1478   /* hack: set level to zero so that revert does not remove the branch */
1479   solv->branches.elements[end - 1] = 0;
1480   revert(solv, level);
1481   solv->branches.elements[end - 1] = level;
1482   /* hack: revert simply sets the count, so we can still access the reverted elements */
1483   why = -solv->decisionq_why.elements[solv->decisionq_why.count];
1484   assert(why >= 0);
1485   return setpropagatelearn(solv, level, p, disablerules, why);
1486 }
1487
1488 /*-------------------------------------------------------------------
1489  *
1490  * select and install
1491  *
1492  * install best package from the queue. We add an extra package, inst, if
1493  * provided. See comment in weak install section.
1494  *
1495  * returns the new solver level or -1 if unsolvable
1496  *
1497  */
1498
1499 static int
1500 selectandinstall(Solver *solv, int level, Queue *dq, int disablerules, Id ruleid)
1501 {
1502   Pool *pool = solv->pool;
1503   Id p;
1504
1505   if (dq->count > 1)
1506     policy_filter_unwanted(solv, dq, POLICY_MODE_CHOOSE);
1507   /* if we're resolving job rules and didn't resolve the installed packages yet,
1508    * do some special supplements ordering */
1509   if (dq->count > 1 && ruleid >= solv->jobrules && ruleid < solv->jobrules_end && solv->installed && !solv->focus_installed)
1510     reorder_dq_for_jobrules(solv, level, dq);
1511   /* if we have multiple candidates we open a branch */
1512   if (dq->count > 1)
1513     createbranch(solv, level, dq, 0, ruleid);
1514   p = dq->elements[0];
1515   POOL_DEBUG(SOLV_DEBUG_POLICY, "installing %s\n", pool_solvid2str(pool, p));
1516   return setpropagatelearn(solv, level, p, disablerules, ruleid);
1517 }
1518
1519
1520 /********************************************************************/
1521 /* Main solver interface */
1522
1523
1524 /*-------------------------------------------------------------------
1525  *
1526  * solver_create
1527  * create solver structure
1528  *
1529  * pool: all available solvables
1530  * installed: installed Solvables
1531  *
1532  *
1533  * Upon solving, rules are created to flag the Solvables
1534  * of the 'installed' Repo as installed.
1535  */
1536
1537 Solver *
1538 solver_create(Pool *pool)
1539 {
1540   Solver *solv;
1541   solv = (Solver *)solv_calloc(1, sizeof(Solver));
1542   solv->pool = pool;
1543   solv->installed = pool->installed;
1544
1545   solv->allownamechange = 1;
1546
1547   solv->dup_allowdowngrade = 1;
1548   solv->dup_allownamechange = 1;
1549   solv->dup_allowarchchange = 1;
1550   solv->dup_allowvendorchange = 1;
1551
1552   solv->keepexplicitobsoletes = pool->noobsoletesmultiversion ? 0 : 1;
1553
1554   queue_init(&solv->ruletojob);
1555   queue_init(&solv->decisionq);
1556   queue_init(&solv->decisionq_why);
1557   queue_init(&solv->problems);
1558   queue_init(&solv->orphaned);
1559   queue_init(&solv->learnt_why);
1560   queue_init(&solv->learnt_pool);
1561   queue_init(&solv->branches);
1562   queue_init(&solv->weakruleq);
1563   queue_init(&solv->ruleassertions);
1564   queue_init(&solv->addedmap_deduceq);
1565
1566   queue_push(&solv->learnt_pool, 0);    /* so that 0 does not describe a proof */
1567
1568   map_init(&solv->recommendsmap, pool->nsolvables);
1569   map_init(&solv->suggestsmap, pool->nsolvables);
1570   map_init(&solv->noupdate, solv->installed ? solv->installed->end - solv->installed->start : 0);
1571   solv->recommends_index = 0;
1572
1573   solv->decisionmap = (Id *)solv_calloc(pool->nsolvables, sizeof(Id));
1574   solv->nrules = 1;
1575   solv->rules = solv_extend_resize(solv->rules, solv->nrules, sizeof(Rule), RULES_BLOCK);
1576   memset(solv->rules, 0, sizeof(Rule));
1577
1578   return solv;
1579 }
1580
1581
1582 static int
1583 resolve_jobrules(Solver *solv, int level, int disablerules, Queue *dq)
1584 {
1585   Pool *pool = solv->pool;
1586   int oldlevel = level;
1587   int i, olevel;
1588   Rule *r;
1589
1590   POOL_DEBUG(SOLV_DEBUG_SOLVER, "resolving job rules\n");
1591   if (!solv->decisioncnt_jobs)
1592     solv->decisioncnt_jobs = solv->decisionq.count;
1593   for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++)
1594     {
1595       Id l, pp;
1596       if (r->d < 0)             /* ignore disabled rules */
1597         continue;
1598       queue_empty(dq);
1599       FOR_RULELITERALS(l, pp, r)
1600         {
1601           if (l < 0)
1602             {
1603               if (solv->decisionmap[-l] <= 0)
1604                 break;
1605             }
1606           else
1607             {
1608               if (solv->decisionmap[l] > 0)
1609                 break;
1610               if (solv->decisionmap[l] == 0)
1611                 queue_push(dq, l);
1612             }
1613         }
1614       if (l || !dq->count)
1615         continue;
1616       /* prune to installed if not updating */
1617       if (dq->count > 1 && solv->installed && !solv->updatemap_all &&
1618           !(solv->job.elements[solv->ruletojob.elements[i - solv->jobrules]] & SOLVER_ORUPDATE))
1619         {
1620           int j, k;
1621           for (j = k = 0; j < dq->count; j++)
1622             {
1623               Solvable *s = pool->solvables + dq->elements[j];
1624               if (s->repo == solv->installed)
1625                 {
1626                   dq->elements[k++] = dq->elements[j];
1627                   if (solv->updatemap.size && MAPTST(&solv->updatemap, dq->elements[j] - solv->installed->start))
1628                     {
1629                       k = 0;    /* package wants to be updated, do not prune */
1630                       break;
1631                     }
1632                 }
1633             }
1634           if (k)
1635             dq->count = k;
1636         }
1637       olevel = level;
1638       level = selectandinstall(solv, level, dq, disablerules, i);
1639       if (level <= olevel)
1640         {
1641           if (level == olevel)
1642             {
1643               i--;
1644               r--;
1645               continue; /* try something else */
1646             }
1647           if (level < oldlevel)
1648             return level;
1649           /* redo from start of jobrules */
1650           i = solv->jobrules - 1;
1651           r = solv->rules + i;
1652         }
1653     }
1654   return level;
1655 }
1656
1657 /*-------------------------------------------------------------------
1658  *
1659  * solver_free
1660  */
1661
1662 static inline void
1663 queuep_free(Queue **qp)
1664 {
1665   if (!*qp)
1666     return;
1667   queue_free(*qp);
1668   *qp = solv_free(*qp);
1669 }
1670
1671 static inline void
1672 map_zerosize(Map *m)
1673 {
1674   if (m->size)
1675     {
1676       map_free(m);
1677       map_init(m, 0);
1678     }
1679 }
1680
1681 void
1682 solver_free(Solver *solv)
1683 {
1684   queue_free(&solv->job);
1685   queue_free(&solv->ruletojob);
1686   queue_free(&solv->decisionq);
1687   queue_free(&solv->decisionq_why);
1688   queue_free(&solv->learnt_why);
1689   queue_free(&solv->learnt_pool);
1690   queue_free(&solv->problems);
1691   queue_free(&solv->solutions);
1692   queue_free(&solv->orphaned);
1693   queue_free(&solv->branches);
1694   queue_free(&solv->weakruleq);
1695   queue_free(&solv->ruleassertions);
1696   queue_free(&solv->addedmap_deduceq);
1697   queuep_free(&solv->cleandeps_updatepkgs);
1698   queuep_free(&solv->cleandeps_mistakes);
1699   queuep_free(&solv->update_targets);
1700   queuep_free(&solv->installsuppdepq);
1701   queuep_free(&solv->recommendscplxq);
1702   queuep_free(&solv->suggestscplxq);
1703   queuep_free(&solv->brokenorphanrules);
1704
1705   map_free(&solv->recommendsmap);
1706   map_free(&solv->suggestsmap);
1707   map_free(&solv->noupdate);
1708   map_free(&solv->weakrulemap);
1709   map_free(&solv->multiversion);
1710
1711   map_free(&solv->updatemap);
1712   map_free(&solv->bestupdatemap);
1713   map_free(&solv->fixmap);
1714   map_free(&solv->dupmap);
1715   map_free(&solv->dupinvolvedmap);
1716   map_free(&solv->droporphanedmap);
1717   map_free(&solv->cleandepsmap);
1718   map_free(&solv->allowuninstallmap);
1719
1720   solv_free(solv->decisionmap);
1721   solv_free(solv->rules);
1722   solv_free(solv->watches);
1723   solv_free(solv->obsoletes);
1724   solv_free(solv->obsoletes_data);
1725   solv_free(solv->specialupdaters);
1726   solv_free(solv->choicerules_ref);
1727   solv_free(solv->bestrules_pkg);
1728   solv_free(solv->yumobsrules_info);
1729   solv_free(solv->instbuddy);
1730   solv_free(solv);
1731 }
1732
1733 int
1734 solver_get_flag(Solver *solv, int flag)
1735 {
1736   switch (flag)
1737   {
1738   case SOLVER_FLAG_ALLOW_DOWNGRADE:
1739     return solv->allowdowngrade;
1740   case SOLVER_FLAG_ALLOW_NAMECHANGE:
1741     return solv->allownamechange;
1742   case SOLVER_FLAG_ALLOW_ARCHCHANGE:
1743     return solv->allowarchchange;
1744   case SOLVER_FLAG_ALLOW_VENDORCHANGE:
1745     return solv->allowvendorchange;
1746   case SOLVER_FLAG_ALLOW_UNINSTALL:
1747     return solv->allowuninstall;
1748   case SOLVER_FLAG_NO_UPDATEPROVIDE:
1749     return solv->noupdateprovide;
1750   case SOLVER_FLAG_SPLITPROVIDES:
1751     return solv->dosplitprovides;
1752   case SOLVER_FLAG_IGNORE_RECOMMENDED:
1753     return solv->dontinstallrecommended;
1754   case SOLVER_FLAG_ADD_ALREADY_RECOMMENDED:
1755     return solv->addalreadyrecommended;
1756   case SOLVER_FLAG_NO_INFARCHCHECK:
1757     return solv->noinfarchcheck;
1758   case SOLVER_FLAG_KEEP_EXPLICIT_OBSOLETES:
1759     return solv->keepexplicitobsoletes;
1760   case SOLVER_FLAG_BEST_OBEY_POLICY:
1761     return solv->bestobeypolicy;
1762   case SOLVER_FLAG_NO_AUTOTARGET:
1763     return solv->noautotarget;
1764   case SOLVER_FLAG_DUP_ALLOW_DOWNGRADE:
1765     return solv->dup_allowdowngrade;
1766   case SOLVER_FLAG_DUP_ALLOW_NAMECHANGE:
1767     return solv->dup_allownamechange;
1768   case SOLVER_FLAG_DUP_ALLOW_ARCHCHANGE:
1769     return solv->dup_allowarchchange;
1770   case SOLVER_FLAG_DUP_ALLOW_VENDORCHANGE:
1771     return solv->dup_allowvendorchange;
1772   case SOLVER_FLAG_KEEP_ORPHANS:
1773     return solv->keep_orphans;
1774   case SOLVER_FLAG_BREAK_ORPHANS:
1775     return solv->break_orphans;
1776   case SOLVER_FLAG_FOCUS_INSTALLED:
1777     return solv->focus_installed;
1778   case SOLVER_FLAG_YUM_OBSOLETES:
1779     return solv->do_yum_obsoletes;
1780   case SOLVER_FLAG_NEED_UPDATEPROVIDE:
1781     return solv->needupdateprovide;
1782   default:
1783     break;
1784   }
1785   return -1;
1786 }
1787
1788 int
1789 solver_set_flag(Solver *solv, int flag, int value)
1790 {
1791   int old = solver_get_flag(solv, flag);
1792   switch (flag)
1793   {
1794   case SOLVER_FLAG_ALLOW_DOWNGRADE:
1795     solv->allowdowngrade = value;
1796     break;
1797   case SOLVER_FLAG_ALLOW_NAMECHANGE:
1798     solv->allownamechange = value;
1799     break;
1800   case SOLVER_FLAG_ALLOW_ARCHCHANGE:
1801     solv->allowarchchange = value;
1802     break;
1803   case SOLVER_FLAG_ALLOW_VENDORCHANGE:
1804     solv->allowvendorchange = value;
1805     break;
1806   case SOLVER_FLAG_ALLOW_UNINSTALL:
1807     solv->allowuninstall = value;
1808     break;
1809   case SOLVER_FLAG_NO_UPDATEPROVIDE:
1810     solv->noupdateprovide = value;
1811     break;
1812   case SOLVER_FLAG_SPLITPROVIDES:
1813     solv->dosplitprovides = value;
1814     break;
1815   case SOLVER_FLAG_IGNORE_RECOMMENDED:
1816     solv->dontinstallrecommended = value;
1817     break;
1818   case SOLVER_FLAG_ADD_ALREADY_RECOMMENDED:
1819     solv->addalreadyrecommended = value;
1820     break;
1821   case SOLVER_FLAG_NO_INFARCHCHECK:
1822     solv->noinfarchcheck = value;
1823     break;
1824   case SOLVER_FLAG_KEEP_EXPLICIT_OBSOLETES:
1825     solv->keepexplicitobsoletes = value;
1826     break;
1827   case SOLVER_FLAG_BEST_OBEY_POLICY:
1828     solv->bestobeypolicy = value;
1829     break;
1830   case SOLVER_FLAG_NO_AUTOTARGET:
1831     solv->noautotarget = value;
1832     break;
1833   case SOLVER_FLAG_DUP_ALLOW_DOWNGRADE:
1834     solv->dup_allowdowngrade = value;
1835     break;
1836   case SOLVER_FLAG_DUP_ALLOW_NAMECHANGE:
1837     solv->dup_allownamechange = value;
1838     break;
1839   case SOLVER_FLAG_DUP_ALLOW_ARCHCHANGE:
1840     solv->dup_allowarchchange = value;
1841     break;
1842   case SOLVER_FLAG_DUP_ALLOW_VENDORCHANGE:
1843     solv->dup_allowvendorchange = value;
1844     break;
1845   case SOLVER_FLAG_KEEP_ORPHANS:
1846     solv->keep_orphans = value;
1847     break;
1848   case SOLVER_FLAG_BREAK_ORPHANS:
1849     solv->break_orphans = value;
1850     break;
1851   case SOLVER_FLAG_FOCUS_INSTALLED:
1852     solv->focus_installed = value;
1853     break;
1854   case SOLVER_FLAG_YUM_OBSOLETES:
1855     solv->do_yum_obsoletes = value;
1856     break;
1857   case SOLVER_FLAG_NEED_UPDATEPROVIDE:
1858     solv->needupdateprovide = value;
1859     break;
1860   default:
1861     break;
1862   }
1863   return old;
1864 }
1865
1866 static int
1867 cleandeps_check_mistakes(Solver *solv)
1868 {
1869   Pool *pool = solv->pool;
1870   Rule *r;
1871   Id p, pp;
1872   int i;
1873   int mademistake = 0;
1874
1875   if (!solv->cleandepsmap.size)
1876     return 0;
1877   /* check for mistakes */
1878   for (i = solv->installed->start; i < solv->installed->end; i++)
1879     {
1880       if (!MAPTST(&solv->cleandepsmap, i - solv->installed->start))
1881         continue;
1882       r = solv->rules + solv->featurerules + (i - solv->installed->start);
1883       /* a mistake is when the featurerule is true but the updaterule is false */
1884       if (!r->p)
1885         continue;
1886       FOR_RULELITERALS(p, pp, r)
1887         if (p > 0 && solv->decisionmap[p] > 0)
1888           break;
1889       if (!p)
1890         continue;       /* feature rule is not true */
1891       r = solv->rules + solv->updaterules + (i - solv->installed->start);
1892       if (!r->p)
1893         continue;
1894       FOR_RULELITERALS(p, pp, r)
1895         if (p > 0 && solv->decisionmap[p] > 0)
1896           break;
1897       if (p)
1898         continue;       /* update rule is true */
1899       POOL_DEBUG(SOLV_DEBUG_SOLVER, "cleandeps mistake: ");
1900       solver_printruleclass(solv, SOLV_DEBUG_SOLVER, r);
1901       POOL_DEBUG(SOLV_DEBUG_SOLVER, "feature rule: ");
1902       solver_printruleclass(solv, SOLV_DEBUG_SOLVER, solv->rules + solv->featurerules + (i - solv->installed->start));
1903       if (!solv->cleandeps_mistakes)
1904         {
1905           solv->cleandeps_mistakes = solv_calloc(1, sizeof(Queue));
1906           queue_init(solv->cleandeps_mistakes);
1907         }
1908       queue_push(solv->cleandeps_mistakes, i);
1909       MAPCLR(&solv->cleandepsmap, i - solv->installed->start);
1910       solver_reenablepolicyrules_cleandeps(solv, i);
1911       mademistake = 1;
1912     }
1913   return mademistake;
1914 }
1915
1916 static void
1917 prune_to_update_targets(Solver *solv, Id *cp, Queue *q)
1918 {
1919   int i, j;
1920   Id p, *cp2;
1921   for (i = j = 0; i < q->count; i++)
1922     {
1923       p = q->elements[i];
1924       for (cp2 = cp; *cp2; cp2++)
1925         if (*cp2 == p)
1926           {
1927             q->elements[j++] = p;
1928             break;
1929           }
1930     }
1931   queue_truncate(q, j);
1932 }
1933
1934 #ifdef ENABLE_COMPLEX_DEPS
1935
1936 static void
1937 add_complex_recommends(Solver *solv, Id rec, Queue *dq, Map *dqmap)
1938 {
1939   Pool *pool = solv->pool;
1940   int oldcnt = dq->count;
1941   int cutcnt, blkcnt;
1942   Id p;
1943   int i, j;
1944
1945 #if 0
1946   printf("ADD_COMPLEX_RECOMMENDS %s\n", pool_dep2str(pool, rec));
1947 #endif
1948   i = pool_normalize_complex_dep(pool, rec, dq, CPLXDEPS_EXPAND);
1949   if (i == 0 || i == 1)
1950     return;
1951   cutcnt = dq->count;
1952   for (i = oldcnt; i < cutcnt; i++)
1953     {
1954       blkcnt = dq->count;
1955       for (; (p = dq->elements[i]) != 0; i++)
1956         {
1957           if (p < 0)
1958             {
1959               if (solv->decisionmap[-p] <= 0)
1960                 break;
1961               continue;
1962             }
1963           if (solv->decisionmap[p] > 0)
1964             {
1965               queue_truncate(dq, blkcnt);
1966               break;
1967             }
1968           if (dqmap)
1969             {
1970               if (!MAPTST(dqmap, p))
1971                 continue;
1972             }
1973           else
1974             {
1975               if (solv->decisionmap[p] < 0)
1976                 continue;
1977               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))))
1978                 continue;
1979             }
1980           queue_push(dq, p);
1981         }
1982       while (dq->elements[i])
1983         i++;
1984     }
1985   queue_deleten(dq, oldcnt, cutcnt - oldcnt);
1986   /* unify */
1987   if (dq->count != oldcnt)
1988     {
1989       for (j = oldcnt; j < dq->count; j++)
1990         {
1991           p = dq->elements[j];
1992           for (i = 0; i < j; i++)
1993             if (dq->elements[i] == p)
1994               {
1995                 dq->elements[j] = 0;
1996                 break;
1997               }
1998         }
1999       for (i = j = oldcnt; j < dq->count; j++)
2000         if (dq->elements[j])
2001           dq->elements[i++] = dq->elements[j];
2002       queue_truncate(dq, i);
2003     }
2004 #if 0
2005   printf("RETURN:\n");
2006   for (i = oldcnt; i < dq->count; i++)
2007     printf("  - %s\n", pool_solvid2str(pool, dq->elements[i]));
2008 #endif
2009 }
2010
2011 static void
2012 do_complex_recommendations(Solver *solv, Id rec, Map *m, int noselected)
2013 {
2014   Pool *pool = solv->pool;
2015   Queue dq;
2016   Id p;
2017   int i, blk;
2018
2019 #if 0
2020   printf("DO_COMPLEX_RECOMMENDATIONS %s\n", pool_dep2str(pool, rec));
2021 #endif
2022   queue_init(&dq);
2023   i = pool_normalize_complex_dep(pool, rec, &dq, CPLXDEPS_EXPAND);
2024   if (i == 0 || i == 1)
2025     {
2026       queue_free(&dq);
2027       return;
2028     }
2029   for (i = 0; i < dq.count; i++)
2030     {
2031       blk = i;
2032       for (; (p = dq.elements[i]) != 0; i++)
2033         {
2034           if (p < 0)
2035             {
2036               if (solv->decisionmap[-p] <= 0)
2037                 break;
2038               continue;
2039             }
2040           if (solv->decisionmap[p] > 0)
2041             {
2042               if (noselected)
2043                 break;
2044               MAPSET(m, p);
2045               for (i++; (p = dq.elements[i]) != 0; i++)
2046                 if (p > 0 && solv->decisionmap[p] > 0)
2047                   MAPSET(m, p);
2048               p = 1;
2049               break;
2050             }
2051         }
2052       if (!p)
2053         {
2054           for (i = blk; (p = dq.elements[i]) != 0; i++)
2055             if (p > 0)
2056               MAPSET(m, p);
2057         }
2058       while (dq.elements[i])
2059         i++;
2060     }
2061   queue_free(&dq);
2062 }
2063
2064 #endif
2065
2066 /*-------------------------------------------------------------------
2067  *
2068  * solver_run_sat
2069  *
2070  * all rules have been set up, now actually run the solver
2071  *
2072  */
2073
2074 void
2075 solver_run_sat(Solver *solv, int disablerules, int doweak)
2076 {
2077   Queue dq;             /* local decisionqueue */
2078   Queue dqs;            /* local decisionqueue for supplements */
2079   int systemlevel;
2080   int level, olevel;
2081   Rule *r;
2082   int i, j, n;
2083   Solvable *s;
2084   Pool *pool = solv->pool;
2085   Id p, pp, *dp, postponed;
2086   int minimizationsteps;
2087   int installedpos = solv->installed ? solv->installed->start : 0;
2088
2089   IF_POOLDEBUG (SOLV_DEBUG_RULE_CREATION)
2090     {
2091       POOL_DEBUG (SOLV_DEBUG_RULE_CREATION, "number of rules: %d\n", solv->nrules);
2092       for (i = 1; i < solv->nrules; i++)
2093         solver_printruleclass(solv, SOLV_DEBUG_RULE_CREATION, solv->rules + i);
2094     }
2095
2096   /* start SAT algorithm */
2097   level = 0;
2098   systemlevel = level + 1;
2099   POOL_DEBUG(SOLV_DEBUG_SOLVER, "solving...\n");
2100
2101   queue_init(&dq);
2102   queue_init(&dqs);
2103
2104   /*
2105    * here's the main loop:
2106    * 1) decide assertion rules and propagate
2107    * 2) fulfill jobs
2108    * 3) try to keep installed packages
2109    * 4) fulfill all unresolved rules
2110    * 5) install recommended packages
2111    * 6) minimalize solution if we had choices
2112    * if we encounter a problem, we rewind to a safe level and restart
2113    * with step 1
2114    */
2115
2116   minimizationsteps = 0;
2117   for (;;)
2118     {
2119       /*
2120        * initial propagation of the assertions
2121        */
2122       if (level <= 0)
2123         {
2124           if (level < 0)
2125             break;
2126           makeruledecisions(solv);
2127           level = 1;
2128           if (!disablerules && solv->problems.count)
2129             {
2130               level = -1;
2131               break;
2132             }
2133           POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "initial propagate (propagate_index: %d;  size decisionq: %d)...\n", solv->propagate_index, solv->decisionq.count);
2134           if ((r = propagate(solv, level)) != 0)
2135             {
2136               level = analyze_unsolvable(solv, r, disablerules);
2137               continue;
2138             }
2139           systemlevel = level + 1;
2140         }
2141
2142       /*
2143        * resolve jobs first (unless focus_installed is set)
2144        */
2145      if (level < systemlevel && !solv->focus_installed)
2146         {
2147           olevel = level;
2148           level = resolve_jobrules(solv, level, disablerules, &dq);
2149           if (level < olevel)
2150             continue;
2151           systemlevel = level + 1;
2152         }
2153
2154
2155       /*
2156        * installed packages
2157        */
2158       if (!solv->decisioncnt_update)
2159         solv->decisioncnt_update = solv->decisionq.count;
2160       if (level < systemlevel && solv->installed && solv->installed->nsolvables && !solv->installed->disabled)
2161         {
2162           Repo *installed = solv->installed;
2163           int pass;
2164
2165           POOL_DEBUG(SOLV_DEBUG_SOLVER, "resolving installed packages\n");
2166           /* we use two passes if we need to update packages
2167            * to create a better user experience */
2168           for (pass = solv->updatemap.size ? 0 : 1; pass < 2; pass++)
2169             {
2170               int passlevel = level;
2171               Id *specialupdaters = solv->specialupdaters;
2172               if (pass == 1 && !solv->decisioncnt_keep)
2173                 solv->decisioncnt_keep = solv->decisionq.count;
2174               /* start with installedpos, the position that gave us problems the last time */
2175               for (i = installedpos, n = installed->start; n < installed->end; i++, n++)
2176                 {
2177                   Rule *rr;
2178                   Id d;
2179
2180                   if (i == installed->end)
2181                     i = installed->start;
2182                   s = pool->solvables + i;
2183                   if (s->repo != installed)
2184                     continue;
2185
2186                   if (solv->decisionmap[i] > 0 && (!specialupdaters || !specialupdaters[i - installed->start]))
2187                     continue;           /* already decided */
2188                   if (!pass && solv->updatemap.size && !MAPTST(&solv->updatemap, i - installed->start))
2189                     continue;           /* updates first */
2190                   r = solv->rules + solv->updaterules + (i - installed->start);
2191                   rr = r;
2192                   if (!rr->p || rr->d < 0)      /* disabled -> look at feature rule */
2193                     rr -= solv->installed->end - solv->installed->start;
2194                   if (!rr->p)           /* identical to update rule? */
2195                     rr = r;
2196                   if (!rr->p)
2197                     continue;           /* orpaned package or pseudo package */
2198
2199                   /* check if we should update this package to the latest version
2200                    * noupdate is set for erase jobs, in that case we want to deinstall
2201                    * the installed package and not replace it with a newer version
2202                    * rr->p != i is for dup jobs where the installed package cannot be kept */
2203                   queue_empty(&dq);
2204                   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)))
2205                     {
2206                       if (specialupdaters && (d = specialupdaters[i - installed->start]) != 0)
2207                         {
2208                           /* special multiversion handling, make sure best version is chosen */
2209                           if (rr->p == i && solv->decisionmap[i] >= 0)
2210                             queue_push(&dq, i);
2211                           while ((p = pool->whatprovidesdata[d++]) != 0)
2212                             if (solv->decisionmap[p] >= 0)
2213                               queue_push(&dq, p);
2214                           if (dq.count && solv->update_targets && solv->update_targets->elements[i - installed->start])
2215                             prune_to_update_targets(solv, solv->update_targets->elements + solv->update_targets->elements[i - installed->start], &dq);
2216                           if (dq.count)
2217                             {
2218                               policy_filter_unwanted(solv, &dq, POLICY_MODE_CHOOSE);
2219                               p = dq.elements[0];
2220                               if (p != i && solv->decisionmap[p] == 0)
2221                                 {
2222                                   rr = solv->rules + solv->featurerules + (i - solv->installed->start);
2223                                   if (!rr->p)           /* update rule == feature rule? */
2224                                     rr = rr - solv->featurerules + solv->updaterules;
2225                                   dq.count = 1;
2226                                 }
2227                               else
2228                                 dq.count = 0;
2229                             }
2230                         }
2231                       else
2232                         {
2233                           /* update to best package of the update rule */
2234                           FOR_RULELITERALS(p, pp, rr)
2235                             {
2236                               if (solv->decisionmap[p] > 0)
2237                                 {
2238                                   dq.count = 0;         /* already fulfilled */
2239                                   break;
2240                                 }
2241                               if (!solv->decisionmap[p])
2242                                 queue_push(&dq, p);
2243                             }
2244                         }
2245                     }
2246                   if (dq.count && solv->update_targets && solv->update_targets->elements[i - installed->start])
2247                     prune_to_update_targets(solv, solv->update_targets->elements + solv->update_targets->elements[i - installed->start], &dq);
2248                   /* install best version */
2249                   if (dq.count)
2250                     {
2251                       olevel = level;
2252                       level = selectandinstall(solv, level, &dq, disablerules, rr - solv->rules);
2253                       if (level <= olevel)
2254                         {
2255                           if (level < passlevel)
2256                             break;      /* trouble */
2257                           if (level < olevel)
2258                             n = installed->start;       /* redo all */
2259                           i--;
2260                           n--;
2261                           continue;
2262                         }
2263                     }
2264                   /* if still undecided keep package */
2265                   if (solv->decisionmap[i] == 0)
2266                     {
2267                       olevel = level;
2268                       if (solv->cleandepsmap.size && MAPTST(&solv->cleandepsmap, i - installed->start))
2269                         {
2270 #if 0
2271                           POOL_DEBUG(SOLV_DEBUG_POLICY, "cleandeps erasing %s\n", pool_solvid2str(pool, i));
2272                           level = setpropagatelearn(solv, level, -i, disablerules, 0);
2273 #else
2274                           continue;
2275 #endif
2276                         }
2277                       else
2278                         {
2279                           POOL_DEBUG(SOLV_DEBUG_POLICY, "keeping %s\n", pool_solvid2str(pool, i));
2280                           level = setpropagatelearn(solv, level, i, disablerules, r - solv->rules);
2281                         }
2282                       if (level <= olevel)
2283                         {
2284                           if (level < passlevel)
2285                             break;      /* trouble */
2286                           if (level < olevel)
2287                             n = installed->start;       /* redo all */
2288                           i--;
2289                           n--;
2290                           continue;     /* retry with learnt rule */
2291                         }
2292                     }
2293                 }
2294               if (n < installed->end)
2295                 {
2296                   installedpos = i;     /* retry problem solvable next time */
2297                   break;                /* ran into trouble */
2298                 }
2299               installedpos = installed->start;  /* reset installedpos */
2300             }
2301           systemlevel = level + 1;
2302           if (pass < 2)
2303             continue;           /* had trouble, retry */
2304         }
2305       if (!solv->decisioncnt_keep)
2306         solv->decisioncnt_keep = solv->decisionq.count;
2307
2308      if (level < systemlevel && solv->focus_installed)
2309         {
2310           olevel = level;
2311           level = resolve_jobrules(solv, level, disablerules, &dq);
2312           if (level < olevel)
2313             continue;
2314           systemlevel = level + 1;
2315         }
2316
2317       if (level < systemlevel)
2318         systemlevel = level;
2319
2320       /*
2321        * decide
2322        */
2323       if (!solv->decisioncnt_resolve)
2324         solv->decisioncnt_resolve = solv->decisionq.count;
2325       POOL_DEBUG(SOLV_DEBUG_POLICY, "deciding unresolved rules\n");
2326       postponed = 0;
2327       for (i = 1, n = 1; ; i++, n++)
2328         {
2329           if (n >= solv->nrules)
2330             {
2331               if (postponed <= 0)
2332                 break;
2333               i = postponed;
2334               postponed = -1;
2335               n = 1;
2336             }
2337           if (i == solv->nrules)
2338             i = 1;
2339           r = solv->rules + i;
2340           if (r->d < 0)         /* ignore disabled rules */
2341             continue;
2342           if (r->p < 0)         /* most common cases first */
2343             {
2344               if (r->d == 0 || solv->decisionmap[-r->p] <= 0)
2345                 continue;
2346             }
2347           if (dq.count)
2348             queue_empty(&dq);
2349           if (r->d == 0)
2350             {
2351               /* binary or unary rule */
2352               /* need two positive undecided literals, r->p already checked above */
2353               if (r->w2 <= 0)
2354                 continue;
2355               if (solv->decisionmap[r->p] || solv->decisionmap[r->w2])
2356                 continue;
2357               queue_push(&dq, r->p);
2358               queue_push(&dq, r->w2);
2359             }
2360           else
2361             {
2362               /* make sure that
2363                * all negative literals are installed
2364                * no positive literal is installed
2365                * i.e. the rule is not fulfilled and we
2366                * just need to decide on the positive literals
2367                * (decisionmap[-r->p] for the r->p < 0 case is already checked above)
2368                */
2369               if (r->p >= 0)
2370                 {
2371                   if (solv->decisionmap[r->p] > 0)
2372                     continue;
2373                   if (solv->decisionmap[r->p] == 0)
2374                     queue_push(&dq, r->p);
2375                 }
2376               dp = pool->whatprovidesdata + r->d;
2377               while ((p = *dp++) != 0)
2378                 {
2379                   if (p < 0)
2380                     {
2381                       if (solv->decisionmap[-p] <= 0)
2382                         break;
2383                     }
2384                   else
2385                     {
2386                       if (solv->decisionmap[p] > 0)
2387                         break;
2388                       if (solv->decisionmap[p] == 0)
2389                         queue_push(&dq, p);
2390                     }
2391                 }
2392               if (p)
2393                 continue;
2394             }
2395           IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
2396             {
2397               POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "unfulfilled ");
2398               solver_printruleclass(solv, SOLV_DEBUG_PROPAGATE, r);
2399             }
2400           /* dq.count < 2 cannot happen as this means that
2401            * the rule is unit */
2402           assert(dq.count > 1);
2403
2404           /* prune to cleandeps packages */
2405           if (solv->cleandepsmap.size && solv->installed)
2406             {
2407               Repo *installed = solv->installed;
2408               for (j = 0; j < dq.count; j++)
2409                 if (pool->solvables[dq.elements[j]].repo == installed && MAPTST(&solv->cleandepsmap, dq.elements[j] - installed->start))
2410                   break;
2411               if (j < dq.count)
2412                 {
2413                   dq.elements[0] = dq.elements[j];
2414                   queue_truncate(&dq, 1);
2415                 }
2416             }
2417
2418           if (dq.count > 1 && postponed >= 0)
2419             {
2420               policy_filter_unwanted(solv, &dq, POLICY_MODE_CHOOSE_NOREORDER);
2421               if (dq.count > 1)
2422                 {
2423                   if (!postponed)
2424                     postponed = i;
2425                   continue;
2426                 }
2427             }
2428
2429           olevel = level;
2430           level = selectandinstall(solv, level, &dq, disablerules, r - solv->rules);
2431           if (level < systemlevel)
2432             break;              /* trouble */
2433           /* something changed, so look at all rules again */
2434           n = 0;
2435         }
2436
2437       if (n < solv->nrules)     /* ran into trouble? */
2438         continue;               /* start over */
2439
2440       /* decide leftover cleandeps packages */
2441       if (solv->cleandepsmap.size && solv->installed)
2442         {
2443           for (p = solv->installed->start; p < solv->installed->end; p++)
2444             {
2445               s = pool->solvables + p;
2446               if (s->repo != solv->installed)
2447                 continue;
2448               if (solv->decisionmap[p] == 0 && MAPTST(&solv->cleandepsmap, p - solv->installed->start))
2449                 {
2450                   POOL_DEBUG(SOLV_DEBUG_POLICY, "cleandeps erasing %s\n", pool_solvid2str(pool, p));
2451                   olevel = level;
2452                   level = setpropagatelearn(solv, level, -p, 0, 0);
2453                   if (level < olevel)
2454                     break;
2455                 }
2456             }
2457           if (p < solv->installed->end)
2458             continue;
2459         }
2460
2461       /* at this point we have a consistent system. now do the extras... */
2462
2463       if (!solv->decisioncnt_weak)
2464         solv->decisioncnt_weak = solv->decisionq.count;
2465       if (doweak)
2466         {
2467           int qcount;
2468
2469           POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended packages\n");
2470           queue_empty(&dq);     /* recommended packages */
2471           queue_empty(&dqs);    /* supplemented packages */
2472           for (i = 1; i < pool->nsolvables; i++)
2473             {
2474               if (solv->decisionmap[i] < 0)
2475                 continue;
2476               if (solv->decisionmap[i] > 0)
2477                 {
2478                   /* installed, check for recommends */
2479                   Id *recp, rec, pp, p;
2480                   s = pool->solvables + i;
2481                   if (!solv->addalreadyrecommended && s->repo == solv->installed)
2482                     continue;
2483                   /* XXX need to special case AND ? */
2484                   if (s->recommends)
2485                     {
2486                       recp = s->repo->idarraydata + s->recommends;
2487                       while ((rec = *recp++) != 0)
2488                         {
2489 #ifdef ENABLE_COMPLEX_DEPS
2490                           if (pool_is_complex_dep(pool, rec))
2491                             {
2492                               add_complex_recommends(solv, rec, &dq, 0);
2493                               continue;
2494                             }
2495 #endif
2496                           qcount = dq.count;
2497                           FOR_PROVIDES(p, pp, rec)
2498                             {
2499                               if (solv->decisionmap[p] > 0)
2500                                 {
2501                                   dq.count = qcount;
2502                                   break;
2503                                 }
2504                               else if (solv->decisionmap[p] == 0)
2505                                 {
2506                                   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))))
2507                                     continue;
2508                                   queue_pushunique(&dq, p);
2509                                 }
2510                             }
2511                         }
2512                     }
2513                 }
2514               else
2515                 {
2516                   s = pool->solvables + i;
2517                   if (!s->supplements)
2518                     continue;
2519                   if (!pool_installable(pool, s))
2520                     continue;
2521                   if (!solver_is_supplementing(solv, s))
2522                     continue;
2523                   if (solv->dupmap_all && solv->installed && s->repo == solv->installed && (solv->droporphanedmap_all || (solv->droporphanedmap.size && MAPTST(&solv->droporphanedmap, i - solv->installed->start))))
2524                     continue;
2525                   queue_push(&dqs, i);
2526                 }
2527             }
2528
2529           /* filter out all packages obsoleted by installed packages */
2530           /* this is no longer needed if we have reverse obsoletes */
2531           if ((dqs.count || dq.count) && solv->installed)
2532             {
2533               Map obsmap;
2534               Id obs, *obsp, po, ppo;
2535
2536               map_init(&obsmap, pool->nsolvables);
2537               for (p = solv->installed->start; p < solv->installed->end; p++)
2538                 {
2539                   s = pool->solvables + p;
2540                   if (s->repo != solv->installed || !s->obsoletes)
2541                     continue;
2542                   if (solv->decisionmap[p] <= 0)
2543                     continue;
2544                   if (!solv->keepexplicitobsoletes && solv->multiversion.size && MAPTST(&solv->multiversion, p))
2545                     continue;
2546                   obsp = s->repo->idarraydata + s->obsoletes;
2547                   /* foreach obsoletes */
2548                   while ((obs = *obsp++) != 0)
2549                     FOR_PROVIDES(po, ppo, obs)
2550                       {
2551                         Solvable *pos = pool->solvables + po;
2552                         if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, pos, obs))
2553                           continue;
2554                         if (pool->obsoleteusescolors && !pool_colormatch(pool, s, pos))
2555                           continue;
2556                         MAPSET(&obsmap, po);
2557                       }
2558                 }
2559               for (i = j = 0; i < dqs.count; i++)
2560                 if (!MAPTST(&obsmap, dqs.elements[i]))
2561                   dqs.elements[j++] = dqs.elements[i];
2562               dqs.count = j;
2563               for (i = j = 0; i < dq.count; i++)
2564                 if (!MAPTST(&obsmap, dq.elements[i]))
2565                   dq.elements[j++] = dq.elements[i];
2566               dq.count = j;
2567               map_free(&obsmap);
2568             }
2569
2570           /* filter out all already supplemented packages if requested */
2571           if (!solv->addalreadyrecommended && dqs.count)
2572             {
2573               /* filter out old supplements */
2574               for (i = j = 0; i < dqs.count; i++)
2575                 {
2576                   p = dqs.elements[i];
2577                   s = pool->solvables + p;
2578                   if (s->supplements && solver_is_supplementing_alreadyinstalled(solv, s))
2579                     dqs.elements[j++] = p;
2580                 }
2581               dqs.count = j;
2582             }
2583
2584           /* multiversion doesn't mix well with supplements.
2585            * filter supplemented packages where we already decided
2586            * to install a different version (see bnc#501088) */
2587           if (dqs.count && solv->multiversion.size)
2588             {
2589               for (i = j = 0; i < dqs.count; i++)
2590                 {
2591                   p = dqs.elements[i];
2592                   if (MAPTST(&solv->multiversion, p))
2593                     {
2594                       Id p2, pp2;
2595                       s = pool->solvables + p;
2596                       FOR_PROVIDES(p2, pp2, s->name)
2597                         if (solv->decisionmap[p2] > 0 && pool->solvables[p2].name == s->name)
2598                           break;
2599                       if (p2)
2600                         continue;       /* ignore this package */
2601                     }
2602                   dqs.elements[j++] = p;
2603                 }
2604               dqs.count = j;
2605             }
2606
2607           /* make dq contain both recommended and supplemented pkgs */
2608           if (dqs.count)
2609             {
2610               for (i = 0; i < dqs.count; i++)
2611                 queue_pushunique(&dq, dqs.elements[i]);
2612             }
2613
2614           if (dq.count)
2615             {
2616               Map dqmap;
2617               int decisioncount = solv->decisionq.count;
2618
2619               if (dq.count == 1)
2620                 {
2621                   /* simple case, just one package. no need to choose to best version */
2622                   p = dq.elements[0];
2623                   if (dqs.count)
2624                     POOL_DEBUG(SOLV_DEBUG_POLICY, "installing supplemented %s\n", pool_solvid2str(pool, p));
2625                   else
2626                     POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended %s\n", pool_solvid2str(pool, p));
2627                   level = setpropagatelearn(solv, level, p, 0, 0);
2628                   continue;     /* back to main loop */
2629                 }
2630
2631               /* filter packages, this gives us the best versions */
2632               policy_filter_unwanted(solv, &dq, POLICY_MODE_RECOMMEND);
2633
2634               /* create map of result */
2635               map_init(&dqmap, pool->nsolvables);
2636               for (i = 0; i < dq.count; i++)
2637                 MAPSET(&dqmap, dq.elements[i]);
2638
2639               /* install all supplemented packages */
2640               for (i = 0; i < dqs.count; i++)
2641                 {
2642                   p = dqs.elements[i];
2643                   if (solv->decisionmap[p] || !MAPTST(&dqmap, p))
2644                     continue;
2645                   POOL_DEBUG(SOLV_DEBUG_POLICY, "installing supplemented %s\n", pool_solvid2str(pool, p));
2646                   olevel = level;
2647                   level = setpropagatelearn(solv, level, p, 0, 0);
2648                   if (level <= olevel)
2649                     break;
2650                 }
2651               if (i < dqs.count || solv->decisionq.count < decisioncount)
2652                 {
2653                   map_free(&dqmap);
2654                   continue;
2655                 }
2656
2657               /* install all recommended packages */
2658               /* more work as we want to created branches if multiple
2659                * choices are valid */
2660               for (i = 0; i < decisioncount; i++)
2661                 {
2662                   Id rec, *recp, pp;
2663                   p = solv->decisionq.elements[i];
2664                   if (p < 0)
2665                     continue;
2666                   s = pool->solvables + p;
2667                   if (!s->repo || (!solv->addalreadyrecommended && s->repo == solv->installed))
2668                     continue;
2669                   if (!s->recommends)
2670                     continue;
2671                   recp = s->repo->idarraydata + s->recommends;
2672                   while ((rec = *recp++) != 0)
2673                     {
2674                       queue_empty(&dq);
2675 #ifdef ENABLE_COMPLEX_DEPS
2676                       if (pool_is_complex_dep(pool, rec))
2677                           add_complex_recommends(solv, rec, &dq, &dqmap);
2678                       else
2679 #endif
2680                       FOR_PROVIDES(p, pp, rec)
2681                         {
2682                           if (solv->decisionmap[p] > 0)
2683                             {
2684                               dq.count = 0;
2685                               break;
2686                             }
2687                           else if (solv->decisionmap[p] == 0 && MAPTST(&dqmap, p))
2688                             queue_push(&dq, p);
2689                         }
2690                       if (!dq.count)
2691                         continue;
2692                       if (dq.count > 1)
2693                         policy_filter_unwanted(solv, &dq, POLICY_MODE_CHOOSE);
2694                       /* if we have multiple candidates we open a branch */
2695                       if (dq.count > 1)
2696                           createbranch(solv, level, &dq, s - pool->solvables, rec);
2697                       p = dq.elements[0];
2698                       POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended %s\n", pool_solvid2str(pool, p));
2699                       olevel = level;
2700                       level = setpropagatelearn(solv, level, p, 0, 0);
2701                       if (level <= olevel || solv->decisionq.count < decisioncount)
2702                         break;  /* we had to revert some decisions */
2703                     }
2704                   if (rec)
2705                     break;      /* had a problem above, quit loop */
2706                 }
2707               map_free(&dqmap);
2708               continue;         /* back to main loop so that all deps are checked */
2709             }
2710         }
2711
2712       if (!solv->decisioncnt_orphan)
2713         solv->decisioncnt_orphan = solv->decisionq.count;
2714       if (solv->installed && (solv->orphaned.count || solv->brokenorphanrules))
2715         {
2716           int installedone = 0;
2717
2718           /* let's see if we can install some unsupported package */
2719           POOL_DEBUG(SOLV_DEBUG_SOLVER, "deciding orphaned packages\n");
2720           for (i = 0; i < solv->orphaned.count; i++)
2721             {
2722               p = solv->orphaned.elements[i];
2723               if (solv->decisionmap[p])
2724                 continue;       /* already decided */
2725               if (solv->droporphanedmap_all)
2726                 continue;
2727               if (solv->droporphanedmap.size && MAPTST(&solv->droporphanedmap, p - solv->installed->start))
2728                 continue;
2729               POOL_DEBUG(SOLV_DEBUG_SOLVER, "keeping orphaned %s\n", pool_solvid2str(pool, p));
2730               olevel = level;
2731               level = setpropagatelearn(solv, level, p, 0, 0);
2732               installedone = 1;
2733               if (level < olevel)
2734                 break;
2735             }
2736           if (installedone || i < solv->orphaned.count)
2737             continue;           /* back to main loop */
2738           for (i = 0; i < solv->orphaned.count; i++)
2739             {
2740               p = solv->orphaned.elements[i];
2741               if (solv->decisionmap[p])
2742                 continue;       /* already decided */
2743               POOL_DEBUG(SOLV_DEBUG_SOLVER, "removing orphaned %s\n", pool_solvid2str(pool, p));
2744               olevel = level;
2745               level = setpropagatelearn(solv, level, -p, 0, 0);
2746               if (level < olevel)
2747                 break;
2748             }
2749           if (i < solv->orphaned.count)
2750             continue;           /* back to main loop */
2751           if (solv->brokenorphanrules)
2752             {
2753               solver_check_brokenorphanrules(solv, &dq);
2754               if (dq.count)
2755                 {
2756                   policy_filter_unwanted(solv, &dq, POLICY_MODE_CHOOSE);
2757                   for (i = 0; i < dq.count; i++)
2758                     {
2759                       p = dq.elements[i];
2760                       POOL_DEBUG(SOLV_DEBUG_POLICY, "installing orphaned dep %s\n", pool_solvid2str(pool, p));
2761                       olevel = level;
2762                       level = setpropagatelearn(solv, level, p, 0, 0);
2763                       if (level < olevel)
2764                         break;
2765                     }
2766                   continue;
2767                 }
2768             }
2769         }
2770
2771      /* one final pass to make sure we decided all installed packages */
2772       if (solv->installed)
2773         {
2774           for (p = solv->installed->start; p < solv->installed->end; p++)
2775             {
2776               if (solv->decisionmap[p])
2777                 continue;       /* already decided */
2778               s = pool->solvables + p;
2779               if (s->repo != solv->installed)
2780                 continue;
2781               POOL_DEBUG(SOLV_DEBUG_SOLVER, "removing unwanted %s\n", pool_solvid2str(pool, p));
2782               olevel = level;
2783               level = setpropagatelearn(solv, level, -p, 0, 0);
2784               if (level < olevel)
2785                 break;
2786             }
2787           if (p < solv->installed->end)
2788             continue;           /* back to main loop */
2789         }
2790
2791       if (solv->installed && solv->cleandepsmap.size && cleandeps_check_mistakes(solv))
2792         {
2793           solver_reset(solv);
2794           level = 0;    /* restart from scratch */
2795           continue;
2796         }
2797
2798       if (solv->solution_callback)
2799         {
2800           solv->solution_callback(solv, solv->solution_callback_data);
2801           if (solv->branches.count)
2802             {
2803               int l, endi = 0;
2804               p = l = 0;
2805               for (i = solv->branches.count - 1; i >= 0; i--)
2806                 {
2807                   p = solv->branches.elements[i];
2808                   if (p > 0 && !l)
2809                     {
2810                       endi = i + 1;
2811                       l = p;
2812                       i -= 3;   /* skip: p data count */
2813                     }
2814                   else if (p > 0)
2815                     break;
2816                   else if (p < 0)
2817                     l = 0;
2818                 }
2819               if (i >= 0)
2820                 {
2821                   while (i > 0 && solv->branches.elements[i - 1] > 0)
2822                     i--;
2823                   level = takebranch(solv, i, endi, "branching", disablerules);
2824                   continue;
2825                 }
2826             }
2827           /* all branches done, we're finally finished */
2828           break;
2829         }
2830
2831       /* auto-minimization step */
2832       if (solv->branches.count)
2833         {
2834           int endi, lasti = -1, lastiend = -1;
2835           if (solv->recommends_index < solv->decisionq.count)
2836             policy_update_recommendsmap(solv);
2837           for (endi = solv->branches.count; endi > 0;)
2838             {
2839               int l, lastsi = -1, starti = endi - solv->branches.elements[endi - 2];
2840               l = solv->branches.elements[endi - 1];
2841               for (i = starti; i < endi - 4; i++)
2842                 {
2843                   p = solv->branches.elements[i];
2844                   if (p <= 0)
2845                     continue;
2846                   if (solv->decisionmap[p] > l)
2847                     {
2848                       lasti = i;
2849                       lastiend = endi;
2850                       lastsi = -1;
2851                       break;
2852                     }
2853                   if (lastsi < 0 && (MAPTST(&solv->recommendsmap, p) || solver_is_supplementing(solv, pool->solvables + p)))
2854                     lastsi = i;
2855                 }
2856               if (lastsi >= 0)
2857                 {
2858                   /* we have a recommended package that could not be installed */
2859                   /* take it if our current selection is not recommended */
2860                   for (i = starti; i < endi - 4; i++)
2861                     {
2862                       p = -solv->branches.elements[i];
2863                       if (p <= 0 || solv->decisionmap[p] != l + 1)
2864                         continue;
2865                       if (!(MAPTST(&solv->recommendsmap, p) || solver_is_supplementing(solv, pool->solvables + p)))
2866                         {
2867                           lasti = lastsi;
2868                           lastiend = endi;
2869                           break;
2870                         }
2871                     }
2872                 }
2873               endi = starti;
2874             }
2875           if (lasti >= 0)
2876             {
2877               minimizationsteps++;
2878               level = takebranch(solv, lasti, lastiend, "minimizing", disablerules);
2879               continue;         /* back to main loop */
2880             }
2881         }
2882       /* no minimization found, we're finally finished! */
2883       break;
2884     }
2885
2886   POOL_DEBUG(SOLV_DEBUG_STATS, "solver statistics: %d learned rules, %d unsolvable, %d minimization steps\n", solv->stats_learned, solv->stats_unsolvable, minimizationsteps);
2887
2888   POOL_DEBUG(SOLV_DEBUG_STATS, "done solving.\n\n");
2889   queue_free(&dq);
2890   queue_free(&dqs);
2891   if (level < 0)
2892     {
2893       /* unsolvable */
2894       solv->decisioncnt_jobs = solv->decisionq.count;
2895       solv->decisioncnt_update = solv->decisionq.count;
2896       solv->decisioncnt_keep = solv->decisionq.count;
2897       solv->decisioncnt_resolve = solv->decisionq.count;
2898       solv->decisioncnt_weak = solv->decisionq.count;
2899       solv->decisioncnt_orphan = solv->decisionq.count;
2900     }
2901 #if 0
2902   solver_printdecisionq(solv, SOLV_DEBUG_RESULT);
2903 #endif
2904 }
2905
2906
2907 /*-------------------------------------------------------------------
2908  *
2909  * remove disabled conflicts
2910  *
2911  * purpose: update the decisionmap after some rules were disabled.
2912  * this is used to calculate the suggested/recommended package list.
2913  * Also returns a "removed" list to undo the discisionmap changes.
2914  */
2915
2916 static void
2917 removedisabledconflicts(Solver *solv, Queue *removed)
2918 {
2919   Pool *pool = solv->pool;
2920   int i, n;
2921   Id p, why, *dp;
2922   Id new;
2923   Rule *r;
2924   Id *decisionmap = solv->decisionmap;
2925
2926   queue_empty(removed);
2927   for (i = 0; i < solv->decisionq.count; i++)
2928     {
2929       p = solv->decisionq.elements[i];
2930       if (p > 0)
2931         continue;       /* conflicts only, please */
2932       why = solv->decisionq_why.elements[i];
2933       if (why == 0)
2934         {
2935           /* no rule involved, must be a orphan package drop */
2936           continue;
2937         }
2938       /* we never do conflicts on free decisions, so there
2939        * must have been an unit rule */
2940       assert(why > 0);
2941       r = solv->rules + why;
2942       if (r->d < 0 && decisionmap[-p])
2943         {
2944           /* rule is now disabled, remove from decisionmap */
2945           POOL_DEBUG(SOLV_DEBUG_SOLVER, "removing conflict for package %s[%d]\n", pool_solvid2str(pool, -p), -p);
2946           queue_push(removed, -p);
2947           queue_push(removed, decisionmap[-p]);
2948           decisionmap[-p] = 0;
2949         }
2950     }
2951   if (!removed->count)
2952     return;
2953   /* we removed some confliced packages. some of them might still
2954    * be in conflict, so search for unit rules and re-conflict */
2955   new = 0;
2956   for (i = n = 1, r = solv->rules + i; n < solv->nrules; i++, r++, n++)
2957     {
2958       if (i == solv->nrules)
2959         {
2960           i = 1;
2961           r = solv->rules + i;
2962         }
2963       if (r->d < 0)
2964         continue;
2965       if (!r->w2)
2966         {
2967           if (r->p < 0 && !decisionmap[-r->p])
2968             new = r->p;
2969         }
2970       else if (!r->d)
2971         {
2972           /* binary rule */
2973           if (r->p < 0 && decisionmap[-r->p] == 0 && DECISIONMAP_FALSE(r->w2))
2974             new = r->p;
2975           else if (r->w2 < 0 && decisionmap[-r->w2] == 0 && DECISIONMAP_FALSE(r->p))
2976             new = r->w2;
2977         }
2978       else
2979         {
2980           if (r->p < 0 && decisionmap[-r->p] == 0)
2981             new = r->p;
2982           if (new || DECISIONMAP_FALSE(r->p))
2983             {
2984               dp = pool->whatprovidesdata + r->d;
2985               while ((p = *dp++) != 0)
2986                 {
2987                   if (new && p == new)
2988                     continue;
2989                   if (p < 0 && decisionmap[-p] == 0)
2990                     {
2991                       if (new)
2992                         {
2993                           new = 0;
2994                           break;
2995                         }
2996                       new = p;
2997                     }
2998                   else if (!DECISIONMAP_FALSE(p))
2999                     {
3000                       new = 0;
3001                       break;
3002                     }
3003                 }
3004             }
3005         }
3006       if (new)
3007         {
3008           POOL_DEBUG(SOLV_DEBUG_SOLVER, "re-conflicting package %s[%d]\n", pool_solvid2str(pool, -new), -new);
3009           decisionmap[-new] = -1;
3010           new = 0;
3011           n = 0;        /* redo all rules */
3012         }
3013     }
3014 }
3015
3016 static inline void
3017 undo_removedisabledconflicts(Solver *solv, Queue *removed)
3018 {
3019   int i;
3020   for (i = 0; i < removed->count; i += 2)
3021     solv->decisionmap[removed->elements[i]] = removed->elements[i + 1];
3022 }
3023
3024
3025 /*-------------------------------------------------------------------
3026  *
3027  * weaken solvable dependencies
3028  */
3029
3030 static void
3031 weaken_solvable_deps(Solver *solv, Id p)
3032 {
3033   int i;
3034   Rule *r;
3035
3036   for (i = 1, r = solv->rules + i; i < solv->pkgrules_end; i++, r++)
3037     {
3038       if (r->p != -p)
3039         continue;
3040       if ((r->d == 0 || r->d == -1) && r->w2 < 0)
3041         continue;       /* conflict */
3042       queue_push(&solv->weakruleq, i);
3043     }
3044 }
3045
3046
3047 /********************************************************************/
3048 /* main() */
3049
3050
3051 void
3052 solver_calculate_multiversionmap(Pool *pool, Queue *job, Map *multiversionmap)
3053 {
3054   int i;
3055   Id how, what, select;
3056   Id p, pp;
3057   for (i = 0; i < job->count; i += 2)
3058     {
3059       how = job->elements[i];
3060       if ((how & SOLVER_JOBMASK) != SOLVER_MULTIVERSION)
3061         continue;
3062       what = job->elements[i + 1];
3063       select = how & SOLVER_SELECTMASK;
3064       if (!multiversionmap->size)
3065         map_grow(multiversionmap, pool->nsolvables);
3066       if (select == SOLVER_SOLVABLE_ALL)
3067         {
3068           FOR_POOL_SOLVABLES(p)
3069             MAPSET(multiversionmap, p);
3070         }
3071       else if (select == SOLVER_SOLVABLE_REPO)
3072         {
3073           Solvable *s;
3074           Repo *repo = pool_id2repo(pool, what);
3075           if (repo)
3076             FOR_REPO_SOLVABLES(repo, p, s)
3077               MAPSET(multiversionmap, p);
3078         }
3079       FOR_JOB_SELECT(p, pp, select, what)
3080         MAPSET(multiversionmap, p);
3081     }
3082 }
3083
3084 void
3085 solver_calculate_noobsmap(Pool *pool, Queue *job, Map *multiversionmap)
3086 {
3087   solver_calculate_multiversionmap(pool, job, multiversionmap);
3088 }
3089
3090 /*
3091  * add a rule created by a job, record job number and weak flag
3092  */
3093 static inline void
3094 solver_addjobrule(Solver *solv, Id p, Id p2, Id d, Id job, int weak)
3095 {
3096   solver_addrule(solv, p, p2, d);
3097   queue_push(&solv->ruletojob, job);
3098   if (weak)
3099     queue_push(&solv->weakruleq, solv->nrules - 1);
3100 }
3101
3102 static inline void
3103 add_cleandeps_package(Solver *solv, Id p)
3104 {
3105   if (!solv->cleandeps_updatepkgs)
3106     {
3107       solv->cleandeps_updatepkgs = solv_calloc(1, sizeof(Queue));
3108       queue_init(solv->cleandeps_updatepkgs);
3109     }
3110   queue_pushunique(solv->cleandeps_updatepkgs, p);
3111 }
3112
3113 static void
3114 add_update_target(Solver *solv, Id p, Id how)
3115 {
3116   Pool *pool = solv->pool;
3117   Solvable *s = pool->solvables + p;
3118   Repo *installed = solv->installed;
3119   Id pi, pip;
3120   if (!solv->update_targets)
3121     {
3122       solv->update_targets = solv_calloc(1, sizeof(Queue));
3123       queue_init(solv->update_targets);
3124     }
3125   if (s->repo == installed)
3126     {
3127       queue_push2(solv->update_targets, p, p);
3128       return;
3129     }
3130   FOR_PROVIDES(pi, pip, s->name)
3131     {
3132       Solvable *si = pool->solvables + pi;
3133       if (si->repo != installed || si->name != s->name)
3134         continue;
3135       if (how & SOLVER_FORCEBEST)
3136         {
3137           if (!solv->bestupdatemap.size)
3138             map_grow(&solv->bestupdatemap, installed->end - installed->start);
3139           MAPSET(&solv->bestupdatemap, pi - installed->start);
3140         }
3141       if (how & SOLVER_CLEANDEPS)
3142         add_cleandeps_package(solv, pi);
3143       queue_push2(solv->update_targets, pi, p);
3144       /* check if it's ok to keep the installed package */
3145       if (s->evr == si->evr && solvable_identical(s, si))
3146         queue_push2(solv->update_targets, pi, pi);
3147     }
3148   if (s->obsoletes)
3149     {
3150       Id obs, *obsp = s->repo->idarraydata + s->obsoletes;
3151       while ((obs = *obsp++) != 0)
3152         {
3153           FOR_PROVIDES(pi, pip, obs)
3154             {
3155               Solvable *si = pool->solvables + pi;
3156               if (si->repo != installed)
3157                 continue;
3158               if (si->name == s->name)
3159                 continue;       /* already handled above */
3160               if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, si, obs))
3161                 continue;
3162               if (pool->obsoleteusescolors && !pool_colormatch(pool, s, si))
3163                 continue;
3164               if (how & SOLVER_FORCEBEST)
3165                 {
3166                   if (!solv->bestupdatemap.size)
3167                     map_grow(&solv->bestupdatemap, installed->end - installed->start);
3168                   MAPSET(&solv->bestupdatemap, pi - installed->start);
3169                 }
3170               if (how & SOLVER_CLEANDEPS)
3171                 add_cleandeps_package(solv, pi);
3172               queue_push2(solv->update_targets, pi, p);
3173             }
3174         }
3175     }
3176 }
3177
3178 static int
3179 transform_update_targets_sortfn(const void *ap, const void *bp, void *dp)
3180 {
3181   const Id *a = ap;
3182   const Id *b = bp;
3183   if (a[0] - b[0])
3184     return a[0] - b[0];
3185   return a[1] - b[1];
3186 }
3187
3188 static void
3189 transform_update_targets(Solver *solv)
3190 {
3191   Repo *installed = solv->installed;
3192   Queue *update_targets = solv->update_targets;
3193   int i, j;
3194   Id p, q, lastp, lastq;
3195
3196   if (!update_targets->count)
3197     {
3198       queue_free(update_targets);
3199       solv->update_targets = solv_free(update_targets);
3200       return;
3201     }
3202   if (update_targets->count > 2)
3203     solv_sort(update_targets->elements, update_targets->count >> 1, 2 * sizeof(Id), transform_update_targets_sortfn, solv);
3204   queue_insertn(update_targets, 0, installed->end - installed->start, 0);
3205   lastp = lastq = 0;
3206   for (i = j = installed->end - installed->start; i < update_targets->count; i += 2)
3207     {
3208       if ((p = update_targets->elements[i]) != lastp)
3209         {
3210           if (!solv->updatemap.size)
3211             map_grow(&solv->updatemap, installed->end - installed->start);
3212           MAPSET(&solv->updatemap, p - installed->start);
3213           update_targets->elements[j++] = 0;                    /* finish old set */
3214           update_targets->elements[p - installed->start] = j;   /* start new set */
3215           lastp = p;
3216           lastq = 0;
3217         }
3218       if ((q = update_targets->elements[i + 1]) != lastq)
3219         {
3220           update_targets->elements[j++] = q;
3221           lastq = q;
3222         }
3223     }
3224   queue_truncate(update_targets, j);
3225   queue_push(update_targets, 0);        /* finish last set */
3226 }
3227
3228
3229 static void
3230 addedmap2deduceq(Solver *solv, Map *addedmap)
3231 {
3232   Pool *pool = solv->pool;
3233   int i, j;
3234   Id p;
3235   Rule *r;
3236
3237   queue_empty(&solv->addedmap_deduceq);
3238   for (i = 2, j = solv->pkgrules_end - 1; i < pool->nsolvables && j > 0; j--)
3239     {
3240       r = solv->rules + j;
3241       if (r->p >= 0)
3242         continue;
3243       if ((r->d == 0 || r->d == -1) && r->w2 < 0)
3244         continue;
3245       p = -r->p;
3246       if (!MAPTST(addedmap, p))
3247         {
3248           /* should never happen, but... */
3249           if (!solv->addedmap_deduceq.count || solv->addedmap_deduceq.elements[solv->addedmap_deduceq.count - 1] != -p)
3250             queue_push(&solv->addedmap_deduceq, -p);
3251           continue;
3252         }
3253       for (; i < p; i++)
3254         if (MAPTST(addedmap, i))
3255           queue_push(&solv->addedmap_deduceq, i);
3256       if (i == p)
3257         i++;
3258     }
3259   for (; i < pool->nsolvables; i++)
3260     if (MAPTST(addedmap, i))
3261       queue_push(&solv->addedmap_deduceq, i);
3262   j = 0;
3263   for (i = 2; i < pool->nsolvables; i++)
3264     if (MAPTST(addedmap, i))
3265       j++;
3266 }
3267
3268 static void
3269 deduceq2addedmap(Solver *solv, Map *addedmap)
3270 {
3271   int j;
3272   Id p;
3273   Rule *r;
3274   for (j = solv->pkgrules_end - 1; j > 0; j--)
3275     {
3276       r = solv->rules + j;
3277       if (r->d < 0 && r->p)
3278         solver_enablerule(solv, r);
3279       if (r->p >= 0)
3280         continue;
3281       if ((r->d == 0 || r->d == -1) && r->w2 < 0)
3282         continue;
3283       p = -r->p;
3284       MAPSET(addedmap, p);
3285     }
3286   for (j = 0; j < solv->addedmap_deduceq.count; j++)
3287     {
3288       p = solv->addedmap_deduceq.elements[j];
3289       if (p > 0)
3290         MAPSET(addedmap, p);
3291       else
3292         MAPCLR(addedmap, p);
3293     }
3294 }
3295
3296 #ifdef ENABLE_COMPLEX_DEPS
3297 static int
3298 add_complex_jobrules(Solver *solv, Id dep, int flags, int jobidx, int weak)
3299 {
3300   Pool *pool = solv->pool;
3301   Queue bq;
3302   int i, j;
3303
3304   queue_init(&bq);
3305   i = pool_normalize_complex_dep(pool, dep, &bq, flags | CPLXDEPS_EXPAND);
3306   if (i == 0 || i == 1)
3307     {
3308       queue_free(&bq);
3309       if (i == 0)
3310         solver_addjobrule(solv, -SYSTEMSOLVABLE, 0, 0, jobidx, weak);
3311       return 0;
3312     }
3313   for (i = 0; i < bq.count; i++)
3314     {
3315       if (!bq.elements[i])
3316         continue;
3317       for (j = 0; bq.elements[i + j + 1]; j++)
3318         ;
3319       if (j > 1)
3320         solver_addjobrule(solv, bq.elements[i], 0, pool_ids2whatprovides(pool, bq.elements + i + 1, j), jobidx, weak);
3321       else
3322         solver_addjobrule(solv, bq.elements[i], bq.elements[i + 1], 0, jobidx, weak);
3323       i += j + 1;
3324     }
3325   queue_free(&bq);
3326   return 1;
3327 }
3328 #endif
3329
3330 /*
3331  *
3332  * solve job queue
3333  *
3334  */
3335
3336 int
3337 solver_solve(Solver *solv, Queue *job)
3338 {
3339   Pool *pool = solv->pool;
3340   Repo *installed = solv->installed;
3341   int i;
3342   int oldnrules, initialnrules;
3343   Map addedmap;                /* '1' == have pkg-rules for solvable */
3344   Map installcandidatemap;
3345   Id how, what, select, name, weak, p, pp, d;
3346   Queue q;
3347   Solvable *s;
3348   Rule *r;
3349   int now, solve_start;
3350   int needduprules = 0;
3351   int hasbestinstalljob = 0;
3352
3353   solve_start = solv_timems(0);
3354
3355   /* log solver options */
3356   POOL_DEBUG(SOLV_DEBUG_STATS, "solver started\n");
3357   POOL_DEBUG(SOLV_DEBUG_STATS, "dosplitprovides=%d, noupdateprovide=%d, noinfarchcheck=%d\n", solv->dosplitprovides, solv->noupdateprovide, solv->noinfarchcheck);
3358   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);
3359   POOL_DEBUG(SOLV_DEBUG_STATS, "promoteepoch=%d, forbidselfconflicts=%d\n", pool->promoteepoch, pool->forbidselfconflicts);
3360   POOL_DEBUG(SOLV_DEBUG_STATS, "obsoleteusesprovides=%d, implicitobsoleteusesprovides=%d, obsoleteusescolors=%d, implicitobsoleteusescolors=%d\n", pool->obsoleteusesprovides, pool->implicitobsoleteusesprovides, pool->obsoleteusescolors, pool->implicitobsoleteusescolors);
3361   POOL_DEBUG(SOLV_DEBUG_STATS, "dontinstallrecommended=%d, addalreadyrecommended=%d\n", solv->dontinstallrecommended, solv->addalreadyrecommended);
3362
3363   /* create whatprovides if not already there */
3364   if (!pool->whatprovides)
3365     pool_createwhatprovides(pool);
3366
3367   /* create obsolete index */
3368   policy_create_obsolete_index(solv);
3369
3370   /* remember job */
3371   queue_free(&solv->job);
3372   queue_init_clone(&solv->job, job);
3373   solv->pooljobcnt = pool->pooljobs.count;
3374   if (pool->pooljobs.count)
3375     queue_insertn(&solv->job, 0, pool->pooljobs.count, pool->pooljobs.elements);
3376   job = &solv->job;
3377
3378   /* free old stuff in jase we re-run a solver */
3379   queuep_free(&solv->update_targets);
3380   queuep_free(&solv->cleandeps_updatepkgs);
3381   queue_empty(&solv->ruleassertions);
3382   solv->bestrules_pkg = solv_free(solv->bestrules_pkg);
3383   solv->yumobsrules_info = solv_free(solv->yumobsrules_info);
3384   solv->choicerules_ref = solv_free(solv->choicerules_ref);
3385   if (solv->noupdate.size)
3386     map_empty(&solv->noupdate);
3387   map_zerosize(&solv->multiversion);
3388   solv->updatemap_all = 0;
3389   map_zerosize(&solv->updatemap);
3390   solv->bestupdatemap_all = 0;
3391   map_zerosize(&solv->bestupdatemap);
3392   solv->fixmap_all = 0;
3393   map_zerosize(&solv->fixmap);
3394   solv->dupmap_all = 0;
3395   map_zerosize(&solv->dupmap);
3396   map_zerosize(&solv->dupinvolvedmap);
3397   solv->droporphanedmap_all = 0;
3398   map_zerosize(&solv->droporphanedmap);
3399   solv->allowuninstall_all = 0;
3400   map_zerosize(&solv->allowuninstallmap);
3401   map_zerosize(&solv->cleandepsmap);
3402   map_zerosize(&solv->weakrulemap);
3403   queue_empty(&solv->weakruleq);
3404   solv->watches = solv_free(solv->watches);
3405   queue_empty(&solv->ruletojob);
3406   if (solv->decisionq.count)
3407     memset(solv->decisionmap, 0, pool->nsolvables * sizeof(Id));
3408   queue_empty(&solv->decisionq);
3409   queue_empty(&solv->decisionq_why);
3410   solv->decisioncnt_jobs = solv->decisioncnt_update = solv->decisioncnt_keep = solv->decisioncnt_resolve = solv->decisioncnt_weak = solv->decisioncnt_orphan = 0;
3411   queue_empty(&solv->learnt_why);
3412   queue_empty(&solv->learnt_pool);
3413   queue_empty(&solv->branches);
3414   solv->propagate_index = 0;
3415   queue_empty(&solv->problems);
3416   queue_empty(&solv->solutions);
3417   queue_empty(&solv->orphaned);
3418   solv->stats_learned = solv->stats_unsolvable = 0;
3419   if (solv->recommends_index)
3420     {
3421       map_empty(&solv->recommendsmap);
3422       map_empty(&solv->suggestsmap);
3423       queuep_free(&solv->recommendscplxq);
3424       queuep_free(&solv->suggestscplxq);
3425       solv->recommends_index = 0;
3426     }
3427   queuep_free(&solv->brokenorphanrules);
3428   solv->specialupdaters = solv_free(solv->specialupdaters);
3429
3430
3431   /*
3432    * create basic rule set of all involved packages
3433    * use addedmap bitmap to make sure we don't create rules twice
3434    */
3435
3436   /* create multiversion map if needed */
3437   solver_calculate_multiversionmap(pool, job, &solv->multiversion);
3438
3439   map_init(&addedmap, pool->nsolvables);
3440   MAPSET(&addedmap, SYSTEMSOLVABLE);
3441
3442   map_init(&installcandidatemap, pool->nsolvables);
3443   queue_init(&q);
3444
3445   now = solv_timems(0);
3446   /*
3447    * create rules for all package that could be involved with the solving
3448    * so called: pkg rules
3449    *
3450    */
3451   initialnrules = solv->pkgrules_end ? solv->pkgrules_end : 1;
3452   if (initialnrules > 1)
3453     deduceq2addedmap(solv, &addedmap);
3454   if (solv->nrules != initialnrules)
3455     solver_shrinkrules(solv, initialnrules);
3456   solv->nrules = initialnrules;
3457   solv->pkgrules_end = 0;
3458
3459   if (installed)
3460     {
3461       /* check for update/verify jobs as they need to be known early */
3462       /* also setup the droporphaned map, we need it when creating update rules */
3463       for (i = 0; i < job->count; i += 2)
3464         {
3465           how = job->elements[i];
3466           what = job->elements[i + 1];
3467           select = how & SOLVER_SELECTMASK;
3468           switch (how & SOLVER_JOBMASK)
3469             {
3470             case SOLVER_VERIFY:
3471               if (select == SOLVER_SOLVABLE_ALL || (select == SOLVER_SOLVABLE_REPO && installed && what == installed->repoid))
3472                 solv->fixmap_all = 1;
3473               FOR_JOB_SELECT(p, pp, select, what)
3474                 {
3475                   s = pool->solvables + p;
3476                   if (s->repo != installed)
3477                     continue;
3478                   if (!solv->fixmap.size)
3479                     map_grow(&solv->fixmap, installed->end - installed->start);
3480                   MAPSET(&solv->fixmap, p - installed->start);
3481                 }
3482               break;
3483             case SOLVER_UPDATE:
3484               if (select == SOLVER_SOLVABLE_ALL)
3485                 {
3486                   solv->updatemap_all = 1;
3487                   if (how & SOLVER_FORCEBEST)
3488                     solv->bestupdatemap_all = 1;
3489                   if (how & SOLVER_CLEANDEPS)
3490                     {
3491                       FOR_REPO_SOLVABLES(installed, p, s)
3492                         add_cleandeps_package(solv, p);
3493                     }
3494                 }
3495               else if (select == SOLVER_SOLVABLE_REPO)
3496                 {
3497                   Repo *repo = pool_id2repo(pool, what);
3498                   if (!repo)
3499                     break;
3500                   if (repo == installed && !(how & SOLVER_TARGETED))
3501                     {
3502                       solv->updatemap_all = 1;
3503                       if (how & SOLVER_FORCEBEST)
3504                         solv->bestupdatemap_all = 1;
3505                       if (how & SOLVER_CLEANDEPS)
3506                         {
3507                           FOR_REPO_SOLVABLES(installed, p, s)
3508                             add_cleandeps_package(solv, p);
3509                         }
3510                       break;
3511                     }
3512                   if (solv->noautotarget && !(how & SOLVER_TARGETED))
3513                     break;
3514                   /* targeted update */
3515                   FOR_REPO_SOLVABLES(repo, p, s)
3516                     add_update_target(solv, p, how);
3517                 }
3518               else
3519                 {
3520                   if (!(how & SOLVER_TARGETED))
3521                     {
3522                       int targeted = 1;
3523                       FOR_JOB_SELECT(p, pp, select, what)
3524                         {
3525                           s = pool->solvables + p;
3526                           if (s->repo != installed)
3527                             continue;
3528                           if (!solv->updatemap.size)
3529                             map_grow(&solv->updatemap, installed->end - installed->start);
3530                           MAPSET(&solv->updatemap, p - installed->start);
3531                           if (how & SOLVER_FORCEBEST)
3532                             {
3533                               if (!solv->bestupdatemap.size)
3534                                 map_grow(&solv->bestupdatemap, installed->end - installed->start);
3535                               MAPSET(&solv->bestupdatemap, p - installed->start);
3536                             }
3537                           if (how & SOLVER_CLEANDEPS)
3538                             add_cleandeps_package(solv, p);
3539                           targeted = 0;
3540                         }
3541                       if (!targeted || solv->noautotarget)
3542                         break;
3543                     }
3544                   FOR_JOB_SELECT(p, pp, select, what)
3545                     add_update_target(solv, p, how);
3546                 }
3547               break;
3548             case SOLVER_DROP_ORPHANED:
3549               if (select == SOLVER_SOLVABLE_ALL || (select == SOLVER_SOLVABLE_REPO && what == installed->repoid))
3550                 solv->droporphanedmap_all = 1;
3551               FOR_JOB_SELECT(p, pp, select, what)
3552                 {
3553                   s = pool->solvables + p;
3554                   if (s->repo != installed)
3555                     continue;
3556                   if (!solv->droporphanedmap.size)
3557                     map_grow(&solv->droporphanedmap, installed->end - installed->start);
3558                   MAPSET(&solv->droporphanedmap, p - installed->start);
3559                 }
3560               break;
3561             case SOLVER_ALLOWUNINSTALL:
3562               if (select == SOLVER_SOLVABLE_ALL || (select == SOLVER_SOLVABLE_REPO && installed && what == installed->repoid))
3563                 solv->allowuninstall_all = 1;
3564               FOR_JOB_SELECT(p, pp, select, what)
3565                 {
3566                   s = pool->solvables + p;
3567                   if (s->repo != installed)
3568                     continue;
3569                   if (!solv->allowuninstallmap.size)
3570                     map_grow(&solv->allowuninstallmap, installed->end - installed->start);
3571                   MAPSET(&solv->allowuninstallmap, p - installed->start);
3572                 }
3573               break;
3574             default:
3575               break;
3576             }
3577         }
3578
3579       if (solv->update_targets)
3580         transform_update_targets(solv);
3581
3582       oldnrules = solv->nrules;
3583       FOR_REPO_SOLVABLES(installed, p, s)
3584         solver_addpkgrulesforsolvable(solv, s, &addedmap);
3585       POOL_DEBUG(SOLV_DEBUG_STATS, "added %d pkg rules for installed solvables\n", solv->nrules - oldnrules);
3586       oldnrules = solv->nrules;
3587       FOR_REPO_SOLVABLES(installed, p, s)
3588         solver_addpkgrulesforupdaters(solv, s, &addedmap, 1);
3589       POOL_DEBUG(SOLV_DEBUG_STATS, "added %d pkg rules for updaters of installed solvables\n", solv->nrules - oldnrules);
3590     }
3591
3592   /*
3593    * create rules for all packages involved in the job
3594    * (to be installed or removed)
3595    */
3596
3597   oldnrules = solv->nrules;
3598   for (i = 0; i < job->count; i += 2)
3599     {
3600       how = job->elements[i];
3601       what = job->elements[i + 1];
3602       select = how & SOLVER_SELECTMASK;
3603
3604       switch (how & SOLVER_JOBMASK)
3605         {
3606         case SOLVER_INSTALL:
3607           FOR_JOB_SELECT(p, pp, select, what)
3608             {
3609               MAPSET(&installcandidatemap, p);
3610               solver_addpkgrulesforsolvable(solv, pool->solvables + p, &addedmap);
3611             }
3612           break;
3613         case SOLVER_DISTUPGRADE:
3614           if (select == SOLVER_SOLVABLE_ALL)
3615             {
3616               solv->dupmap_all = 1;
3617               solv->updatemap_all = 1;
3618               if (how & SOLVER_FORCEBEST)
3619                 solv->bestupdatemap_all = 1;
3620             }
3621           if ((how & SOLVER_TARGETED) != 0)
3622             needduprules = 1;
3623           if (!solv->dupmap_all || solv->allowuninstall || solv->allowuninstall_all || solv->allowuninstallmap.size || solv->keep_orphans)
3624             needduprules = 1;
3625           break;
3626         default:
3627           break;
3628         }
3629     }
3630   POOL_DEBUG(SOLV_DEBUG_STATS, "added %d pkg rules for packages involved in a job\n", solv->nrules - oldnrules);
3631
3632
3633   /*
3634    * add rules for suggests, enhances
3635    */
3636   oldnrules = solv->nrules;
3637   solver_addpkgrulesforweak(solv, &addedmap);
3638   POOL_DEBUG(SOLV_DEBUG_STATS, "added %d pkg rules because of weak dependencies\n", solv->nrules - oldnrules);
3639
3640 #ifdef ENABLE_LINKED_PKGS
3641   oldnrules = solv->nrules;
3642   solver_addpkgrulesforlinked(solv, &addedmap);
3643   POOL_DEBUG(SOLV_DEBUG_STATS, "added %d pkg rules because of linked packages\n", solv->nrules - oldnrules);
3644 #endif
3645
3646   /*
3647    * first pass done, we now have all the pkg rules we need.
3648    * unify existing rules before going over all job rules and
3649    * policy rules.
3650    * at this point the system is always solvable,
3651    * as an empty system (remove all packages) is a valid solution
3652    */
3653
3654   IF_POOLDEBUG (SOLV_DEBUG_STATS)
3655     {
3656       int possible = 0, installable = 0;
3657       for (i = 1; i < pool->nsolvables; i++)
3658         {
3659           if (pool_installable(pool, pool->solvables + i))
3660             installable++;
3661           if (MAPTST(&addedmap, i))
3662             possible++;
3663         }
3664       POOL_DEBUG(SOLV_DEBUG_STATS, "%d of %d installable solvables considered for solving\n", possible, installable);
3665     }
3666
3667   if (solv->nrules > initialnrules)
3668     solver_unifyrules(solv);                    /* remove duplicate pkg rules */
3669   solv->pkgrules_end = solv->nrules;            /* mark end of pkg rules */
3670
3671   if (solv->nrules > initialnrules)
3672     addedmap2deduceq(solv, &addedmap);          /* so that we can recreate the addedmap */
3673
3674   POOL_DEBUG(SOLV_DEBUG_STATS, "pkg rule memory used: %d K\n", solv->nrules * (int)sizeof(Rule) / 1024);
3675   POOL_DEBUG(SOLV_DEBUG_STATS, "pkg rule creation took %d ms\n", solv_timems(now));
3676
3677   /* create dup maps if needed. We need the maps early to create our
3678    * update rules */
3679   if (needduprules)
3680     solver_createdupmaps(solv);
3681
3682   /*
3683    * create feature rules
3684    *
3685    * foreach installed:
3686    *   create assertion (keep installed, if no update available)
3687    *   or
3688    *   create update rule (A|update1(A)|update2(A)|...)
3689    *
3690    * those are used later on to keep a version of the installed packages in
3691    * best effort mode
3692    */
3693
3694   solv->featurerules = solv->nrules;              /* mark start of feature rules */
3695   if (installed)
3696     {
3697       /* foreach possibly installed solvable */
3698       for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
3699         {
3700           if (s->repo != installed)
3701             {
3702               solver_addrule(solv, 0, 0, 0);    /* create dummy rule */
3703               continue;
3704             }
3705           solver_addfeaturerule(solv, s);
3706         }
3707       /* make sure we accounted for all rules */
3708       assert(solv->nrules - solv->featurerules == installed->end - installed->start);
3709     }
3710   solv->featurerules_end = solv->nrules;
3711
3712     /*
3713      * Add update rules for installed solvables
3714      *
3715      * almost identical to feature rules
3716      * except that downgrades/archchanges/vendorchanges are not allowed
3717      */
3718
3719   solv->updaterules = solv->nrules;
3720
3721   if (installed)
3722     { /* foreach installed solvables */
3723       /* we create all update rules, but disable some later on depending on the job */
3724       for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
3725         {
3726           Rule *sr;
3727
3728           if (s->repo != installed)
3729             {
3730               solver_addrule(solv, 0, 0, 0);    /* create dummy rule */
3731               continue;
3732             }
3733           solver_addupdaterule(solv, s);
3734           /*
3735            * check for and remove duplicate
3736            */
3737           r = solv->rules + solv->nrules - 1;           /* r: update rule */
3738           sr = r - (installed->end - installed->start); /* sr: feature rule */
3739           if (!r->p)
3740             {
3741               if (sr->p)
3742                 memset(sr, 0, sizeof(*sr));             /* no feature rules without update rules */
3743               continue;
3744             }
3745           /* it's also orphaned if the feature rule consists just of the installed package */
3746           if (!solv->dupmap_all && sr->p == i && !sr->d && !sr->w2)
3747             queue_push(&solv->orphaned, i);
3748
3749           if (!solver_rulecmp(solv, r, sr))
3750             memset(sr, 0, sizeof(*sr));         /* delete unneeded feature rule */
3751           else if (sr->p)
3752             solver_disablerule(solv, sr);       /* disable feature rule for now */
3753         }
3754       /* consistency check: we added a rule for _every_ installed solvable */
3755       assert(solv->nrules - solv->updaterules == installed->end - installed->start);
3756     }
3757   solv->updaterules_end = solv->nrules;
3758
3759
3760   /*
3761    * now add all job rules
3762    */
3763
3764   solv->jobrules = solv->nrules;
3765   for (i = 0; i < job->count; i += 2)
3766     {
3767       oldnrules = solv->nrules;
3768
3769       if (i && i == solv->pooljobcnt)
3770         POOL_DEBUG(SOLV_DEBUG_JOB, "end of pool jobs\n");
3771       how = job->elements[i];
3772       what = job->elements[i + 1];
3773       weak = how & SOLVER_WEAK;
3774       select = how & SOLVER_SELECTMASK;
3775       switch (how & SOLVER_JOBMASK)
3776         {
3777         case SOLVER_INSTALL:
3778           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sinstall %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
3779           if ((how & SOLVER_CLEANDEPS) != 0 && !solv->cleandepsmap.size && installed)
3780             map_grow(&solv->cleandepsmap, installed->end - installed->start);
3781           if (select == SOLVER_SOLVABLE)
3782             {
3783               p = what;
3784               d = 0;
3785             }
3786 #ifdef ENABLE_COMPLEX_DEPS
3787           else if ((select == SOLVER_SOLVABLE_PROVIDES || select == SOLVER_SOLVABLE_NAME) && pool_is_complex_dep(pool, what))
3788             {
3789               if (add_complex_jobrules(solv, what, select == SOLVER_SOLVABLE_NAME ? CPLXDEPS_NAME : 0, i, weak))
3790                 if (how & SOLVER_FORCEBEST)
3791                   hasbestinstalljob = 1;
3792               break;
3793             }
3794 #endif
3795           else
3796             {
3797               queue_empty(&q);
3798               FOR_JOB_SELECT(p, pp, select, what)
3799                 queue_push(&q, p);
3800               if (!q.count)
3801                 {
3802                   if (select == SOLVER_SOLVABLE_ONE_OF)
3803                     break;      /* ignore empty installs */
3804                   /* no candidate found or unsupported, make this an impossible rule */
3805                   queue_push(&q, -SYSTEMSOLVABLE);
3806                 }
3807               p = queue_shift(&q);      /* get first candidate */
3808               d = !q.count ? 0 : pool_queuetowhatprovides(pool, &q);    /* internalize */
3809             }
3810           /* force install of namespace supplements hack */
3811           if (select == SOLVER_SOLVABLE_PROVIDES && !d && (p == SYSTEMSOLVABLE || p == -SYSTEMSOLVABLE) && ISRELDEP(what))
3812             {
3813               Reldep *rd = GETRELDEP(pool, what);
3814               if (rd->flags == REL_NAMESPACE)
3815                 {
3816                   p = SYSTEMSOLVABLE;
3817                   if (!solv->installsuppdepq)
3818                     {
3819                       solv->installsuppdepq = solv_calloc(1, sizeof(Queue));
3820                       queue_init(solv->installsuppdepq);
3821                     }
3822                   queue_pushunique(solv->installsuppdepq, rd->evr == 0 ? rd->name : what);
3823                 }
3824             }
3825           solver_addjobrule(solv, p, 0, d, i, weak);
3826           if (how & SOLVER_FORCEBEST)
3827             hasbestinstalljob = 1;
3828           break;
3829         case SOLVER_ERASE:
3830           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %s%serase %s\n", weak ? "weak " : "", how & SOLVER_CLEANDEPS ? "clean deps " : "", solver_select2str(pool, select, what));
3831           if ((how & SOLVER_CLEANDEPS) != 0 && !solv->cleandepsmap.size && installed)
3832             map_grow(&solv->cleandepsmap, installed->end - installed->start);
3833           /* specific solvable: by id or by nevra */
3834           name = (select == SOLVER_SOLVABLE || (select == SOLVER_SOLVABLE_NAME && ISRELDEP(what))) ? 0 : -1;
3835           if (select == SOLVER_SOLVABLE_ALL)    /* hmmm ;) */
3836             {
3837               FOR_POOL_SOLVABLES(p)
3838                 solver_addjobrule(solv, -p, 0, 0, i, weak);
3839             }
3840           else if (select == SOLVER_SOLVABLE_REPO)
3841             {
3842               Repo *repo = pool_id2repo(pool, what);
3843               if (repo)
3844                 FOR_REPO_SOLVABLES(repo, p, s)
3845                   solver_addjobrule(solv, -p, 0, 0, i, weak);
3846             }
3847 #ifdef ENABLE_COMPLEX_DEPS
3848           else if ((select == SOLVER_SOLVABLE_PROVIDES || select == SOLVER_SOLVABLE_NAME) && pool_is_complex_dep(pool, what))
3849             {
3850               /* no special "erase a specific solvable" handling? */
3851               add_complex_jobrules(solv, what, select == SOLVER_SOLVABLE_NAME ? (CPLXDEPS_NAME | CPLXDEPS_TODNF | CPLXDEPS_INVERT) : (CPLXDEPS_TODNF | CPLXDEPS_INVERT), i, weak);
3852               break;
3853             }
3854 #endif
3855           FOR_JOB_SELECT(p, pp, select, what)
3856             {
3857               s = pool->solvables + p;
3858               if (installed && s->repo == installed)
3859                 name = !name ? s->name : -1;
3860               solver_addjobrule(solv, -p, 0, 0, i, weak);
3861             }
3862           /* special case for "erase a specific solvable": we also
3863            * erase all other solvables with that name, so that they
3864            * don't get picked up as replacement.
3865            * name is > 0 if exactly one installed solvable matched.
3866            */
3867           /* XXX: look also at packages that obsolete this package? */
3868           if (name > 0)
3869             {
3870               int j, k;
3871               k = solv->nrules;
3872               FOR_PROVIDES(p, pp, name)
3873                 {
3874                   s = pool->solvables + p;
3875                   if (s->name != name)
3876                     continue;
3877                   /* keep other versions installed */
3878                   if (s->repo == installed)
3879                     continue;
3880                   /* keep installcandidates of other jobs */
3881                   if (MAPTST(&installcandidatemap, p))
3882                     continue;
3883                   /* don't add the same rule twice */
3884                   for (j = oldnrules; j < k; j++)
3885                     if (solv->rules[j].p == -p)
3886                       break;
3887                   if (j == k)
3888                     solver_addjobrule(solv, -p, 0, 0, i, weak); /* remove by id */
3889                 }
3890             }
3891           break;
3892
3893         case SOLVER_UPDATE:
3894           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %supdate %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
3895           break;
3896         case SOLVER_VERIFY:
3897           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sverify %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
3898           break;
3899         case SOLVER_WEAKENDEPS:
3900           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sweaken deps %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
3901           if (select != SOLVER_SOLVABLE)
3902             break;
3903           s = pool->solvables + what;
3904           weaken_solvable_deps(solv, what);
3905           break;
3906         case SOLVER_MULTIVERSION:
3907           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %smultiversion %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
3908           break;
3909         case SOLVER_LOCK:
3910           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %slock %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
3911           if (select == SOLVER_SOLVABLE_ALL)
3912             {
3913               FOR_POOL_SOLVABLES(p)
3914                 solver_addjobrule(solv, installed && pool->solvables[p].repo == installed ? p : -p, 0, 0, i, weak);
3915             }
3916           else if (select == SOLVER_SOLVABLE_REPO)
3917             {
3918               Repo *repo = pool_id2repo(pool, what);
3919               if (repo)
3920                 FOR_REPO_SOLVABLES(repo, p, s)
3921                   solver_addjobrule(solv, installed && pool->solvables[p].repo == installed ? p : -p, 0, 0, i, weak);
3922             }
3923           FOR_JOB_SELECT(p, pp, select, what)
3924             solver_addjobrule(solv, installed && pool->solvables[p].repo == installed ? p : -p, 0, 0, i, weak);
3925           break;
3926         case SOLVER_DISTUPGRADE:
3927           POOL_DEBUG(SOLV_DEBUG_JOB, "job: distupgrade %s\n", solver_select2str(pool, select, what));
3928           break;
3929         case SOLVER_DROP_ORPHANED:
3930           POOL_DEBUG(SOLV_DEBUG_JOB, "job: drop orphaned %s\n", solver_select2str(pool, select, what));
3931           break;
3932         case SOLVER_USERINSTALLED:
3933           POOL_DEBUG(SOLV_DEBUG_JOB, "job: user installed %s\n", solver_select2str(pool, select, what));
3934           break;
3935         case SOLVER_ALLOWUNINSTALL:
3936           POOL_DEBUG(SOLV_DEBUG_JOB, "job: allowuninstall %s\n", solver_select2str(pool, select, what));
3937           break;
3938         default:
3939           POOL_DEBUG(SOLV_DEBUG_JOB, "job: unknown job\n");
3940           break;
3941         }
3942
3943       IF_POOLDEBUG (SOLV_DEBUG_JOB)
3944         {
3945           int j;
3946           if (solv->nrules == oldnrules)
3947             POOL_DEBUG(SOLV_DEBUG_JOB, "  - no rule created\n");
3948           for (j = oldnrules; j < solv->nrules; j++)
3949             {
3950               POOL_DEBUG(SOLV_DEBUG_JOB, "  - job ");
3951               solver_printrule(solv, SOLV_DEBUG_JOB, solv->rules + j);
3952             }
3953         }
3954     }
3955   assert(solv->ruletojob.count == solv->nrules - solv->jobrules);
3956   solv->jobrules_end = solv->nrules;
3957
3958   /* now create infarch and dup rules */
3959   if (!solv->noinfarchcheck)
3960     {
3961       solver_addinfarchrules(solv, &addedmap);
3962 #if 0
3963       if (pool->implicitobsoleteusescolors)
3964         {
3965           /* currently doesn't work well with infarch rules, so make
3966            * them weak */
3967           for (i = solv->infarchrules; i < solv->infarchrules_end; i++)
3968             queue_push(&solv->weakruleq, i);
3969         }
3970 #endif
3971     }
3972   else
3973     solv->infarchrules = solv->infarchrules_end = solv->nrules;
3974
3975   if (needduprules)
3976     solver_addduprules(solv, &addedmap);
3977   else
3978     solv->duprules = solv->duprules_end = solv->nrules;
3979
3980 #ifdef ENABLE_LINKED_PKGS
3981   if (solv->instbuddy && solv->updatemap.size)
3982     extend_updatemap_to_buddies(solv);
3983 #endif
3984
3985   if (solv->bestupdatemap_all || solv->bestupdatemap.size || hasbestinstalljob)
3986     solver_addbestrules(solv, hasbestinstalljob);
3987   else
3988     solv->bestrules = solv->bestrules_end = solv->nrules;
3989
3990   if (needduprules)
3991     solver_freedupmaps(solv);   /* no longer needed */
3992
3993   if (solv->do_yum_obsoletes)
3994     solver_addyumobsrules(solv);
3995   else
3996     solv->yumobsrules = solv->yumobsrules_end = solv->nrules;
3997
3998   if (1)
3999     solver_addchoicerules(solv);
4000   else
4001     solv->choicerules = solv->choicerules_end = solv->nrules;
4002
4003   if (0)
4004     {
4005       for (i = solv->featurerules; i < solv->nrules; i++)
4006         solver_printruleclass(solv, SOLV_DEBUG_RESULT, solv->rules + i);
4007     }
4008   /* all rules created
4009    * --------------------------------------------------------------
4010    * prepare for solving
4011    */
4012
4013   /* free unneeded memory */
4014   map_free(&addedmap);
4015   map_free(&installcandidatemap);
4016   queue_free(&q);
4017
4018   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);
4019   POOL_DEBUG(SOLV_DEBUG_STATS, "overall rule memory used: %d K\n", solv->nrules * (int)sizeof(Rule) / 1024);
4020
4021   /* create weak map */
4022   if (solv->weakruleq.count)
4023     {
4024       map_grow(&solv->weakrulemap, solv->nrules);
4025       for (i = 0; i < solv->weakruleq.count; i++)
4026         {
4027           p = solv->weakruleq.elements[i];
4028           MAPSET(&solv->weakrulemap, p);
4029         }
4030     }
4031
4032   /* enable cleandepsmap creation if we have updatepkgs */
4033   if (solv->cleandeps_updatepkgs && !solv->cleandepsmap.size)
4034     map_grow(&solv->cleandepsmap, installed->end - installed->start);
4035   /* no mistakes */
4036   if (solv->cleandeps_mistakes)
4037     {
4038       queue_free(solv->cleandeps_mistakes);
4039       solv->cleandeps_mistakes = solv_free(solv->cleandeps_mistakes);
4040     }
4041
4042   /* all new rules are learnt after this point */
4043   solv->learntrules = solv->nrules;
4044
4045   /* create watches chains */
4046   makewatches(solv);
4047
4048   /* create assertion index. it is only used to speed up
4049    * makeruledecsions() a bit */
4050   for (i = 1, r = solv->rules + i; i < solv->nrules; i++, r++)
4051     if (r->p && !r->w2 && (r->d == 0 || r->d == -1))
4052       queue_push(&solv->ruleassertions, i);
4053
4054   /* disable update rules that conflict with our job */
4055   solver_disablepolicyrules(solv);
4056
4057   /* break orphans if requested */
4058   if (solv->dupmap_all && solv->orphaned.count && solv->break_orphans)
4059     solver_breakorphans(solv);
4060
4061   /*
4062    * ********************************************
4063    * solve!
4064    * ********************************************
4065    */
4066
4067   now = solv_timems(0);
4068   solver_run_sat(solv, 1, solv->dontinstallrecommended ? 0 : 1);
4069   POOL_DEBUG(SOLV_DEBUG_STATS, "solver took %d ms\n", solv_timems(now));
4070
4071   /*
4072    * prepare solution queue if there were problems
4073    */
4074   solver_prepare_solutions(solv);
4075
4076   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);
4077   POOL_DEBUG(SOLV_DEBUG_STATS, "solver_solve took %d ms\n", solv_timems(solve_start));
4078
4079   /* return number of problems */
4080   return solv->problems.count ? solv->problems.count / 2 : 0;
4081 }
4082
4083 Transaction *
4084 solver_create_transaction(Solver *solv)
4085 {
4086   return transaction_create_decisionq(solv->pool, &solv->decisionq, &solv->multiversion);
4087 }
4088
4089 void solver_get_orphaned(Solver *solv, Queue *orphanedq)
4090 {
4091   queue_free(orphanedq);
4092   queue_init_clone(orphanedq, &solv->orphaned);
4093 }
4094
4095 void solver_get_recommendations(Solver *solv, Queue *recommendationsq, Queue *suggestionsq, int noselected)
4096 {
4097   Pool *pool = solv->pool;
4098   Queue redoq, disabledq;
4099   int goterase, i;
4100   Solvable *s;
4101   Rule *r;
4102   Map obsmap;
4103
4104   if (!recommendationsq && !suggestionsq)
4105     return;
4106
4107   map_init(&obsmap, pool->nsolvables);
4108   if (solv->installed)
4109     {
4110       Id obs, *obsp, p, po, ppo;
4111       for (p = solv->installed->start; p < solv->installed->end; p++)
4112         {
4113           s = pool->solvables + p;
4114           if (s->repo != solv->installed || !s->obsoletes)
4115             continue;
4116           if (solv->decisionmap[p] <= 0)
4117             continue;
4118           if (solv->multiversion.size && MAPTST(&solv->multiversion, p))
4119             continue;
4120           obsp = s->repo->idarraydata + s->obsoletes;
4121           /* foreach obsoletes */
4122           while ((obs = *obsp++) != 0)
4123             FOR_PROVIDES(po, ppo, obs)
4124               MAPSET(&obsmap, po);
4125         }
4126     }
4127
4128   queue_init(&redoq);
4129   queue_init(&disabledq);
4130   goterase = 0;
4131   /* disable all erase jobs (including weak "keep uninstalled" rules) */
4132   for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++)
4133     {
4134       if (r->d < 0)     /* disabled ? */
4135         continue;
4136       if (r->p >= 0)    /* install job? */
4137         continue;
4138       queue_push(&disabledq, i);
4139       solver_disablerule(solv, r);
4140       goterase++;
4141     }
4142
4143   if (goterase)
4144     {
4145       enabledisablelearntrules(solv);
4146       removedisabledconflicts(solv, &redoq);
4147     }
4148
4149   /*
4150    * find recommended packages
4151    */
4152   if (recommendationsq)
4153     {
4154       Id rec, *recp, p, pp;
4155
4156       queue_empty(recommendationsq);
4157       /* create map of all recommened packages */
4158       solv->recommends_index = -1;
4159       MAPZERO(&solv->recommendsmap);
4160
4161       /* put all packages the solver already chose in the map */
4162       if (solv->decisioncnt_weak)
4163         {
4164           for (i = solv->decisioncnt_weak; i < solv->decisioncnt_orphan; i++)
4165             {
4166               Id why;
4167               why = solv->decisionq_why.elements[i];
4168               if (why)
4169                 continue;       /* forced by unit rule or dep resolving */
4170               p = solv->decisionq.elements[i];
4171               if (p < 0)
4172                 continue;
4173               MAPSET(&solv->recommendsmap, p);
4174             }
4175         }
4176
4177       for (i = 0; i < solv->decisionq.count; i++)
4178         {
4179           p = solv->decisionq.elements[i];
4180           if (p < 0)
4181             continue;
4182           s = pool->solvables + p;
4183           if (s->recommends)
4184             {
4185               recp = s->repo->idarraydata + s->recommends;
4186               while ((rec = *recp++) != 0)
4187                 {
4188 #ifdef ENABLE_COMPLEX_DEPS
4189                   if (pool_is_complex_dep(pool, rec))
4190                     {
4191                       do_complex_recommendations(solv, rec, &solv->recommendsmap, noselected);
4192                       continue;
4193                     }
4194 #endif
4195                   FOR_PROVIDES(p, pp, rec)
4196                     if (solv->decisionmap[p] > 0)
4197                       break;
4198                   if (p)
4199                     {
4200                       if (!noselected)
4201                         {
4202                           FOR_PROVIDES(p, pp, rec)
4203                             if (solv->decisionmap[p] > 0)
4204                               MAPSET(&solv->recommendsmap, p);
4205                         }
4206                       continue; /* p != 0: already fulfilled */
4207                     }
4208                   FOR_PROVIDES(p, pp, rec)
4209                     MAPSET(&solv->recommendsmap, p);
4210                 }
4211             }
4212         }
4213       for (i = 1; i < pool->nsolvables; i++)
4214         {
4215           if (solv->decisionmap[i] < 0)
4216             continue;
4217           if (solv->decisionmap[i] > 0 && noselected)
4218             continue;
4219           if (MAPTST(&obsmap, i))
4220             continue;
4221           s = pool->solvables + i;
4222           if (!MAPTST(&solv->recommendsmap, i))
4223             {
4224               if (!s->supplements)
4225                 continue;
4226               if (!pool_installable(pool, s))
4227                 continue;
4228               if (!solver_is_supplementing(solv, s))
4229                 continue;
4230             }
4231           queue_push(recommendationsq, i);
4232         }
4233       /* we use MODE_SUGGEST here so that repo prio is ignored */
4234       policy_filter_unwanted(solv, recommendationsq, POLICY_MODE_SUGGEST);
4235     }
4236
4237   /*
4238    * find suggested packages
4239    */
4240
4241   if (suggestionsq)
4242     {
4243       Id sug, *sugp, p, pp;
4244
4245       queue_empty(suggestionsq);
4246       /* create map of all suggests that are still open */
4247       solv->recommends_index = -1;
4248       MAPZERO(&solv->suggestsmap);
4249       for (i = 0; i < solv->decisionq.count; i++)
4250         {
4251           p = solv->decisionq.elements[i];
4252           if (p < 0)
4253             continue;
4254           s = pool->solvables + p;
4255           if (s->suggests)
4256             {
4257               sugp = s->repo->idarraydata + s->suggests;
4258               while ((sug = *sugp++) != 0)
4259                 {
4260 #ifdef ENABLE_COMPLEX_DEPS
4261                   if (pool_is_complex_dep(pool, sug))
4262                     {
4263                       do_complex_recommendations(solv, sug, &solv->suggestsmap, noselected);
4264                       continue;
4265                     }
4266 #endif
4267                   FOR_PROVIDES(p, pp, sug)
4268                     if (solv->decisionmap[p] > 0)
4269                       break;
4270                   if (p)
4271                     {
4272                       if (!noselected)
4273                         {
4274                           FOR_PROVIDES(p, pp, sug)
4275                             if (solv->decisionmap[p] > 0)
4276                               MAPSET(&solv->suggestsmap, p);
4277                         }
4278                       continue; /* already fulfilled */
4279                     }
4280                   FOR_PROVIDES(p, pp, sug)
4281                     MAPSET(&solv->suggestsmap, p);
4282                 }
4283             }
4284         }
4285       for (i = 1; i < pool->nsolvables; i++)
4286         {
4287           if (solv->decisionmap[i] < 0)
4288             continue;
4289           if (solv->decisionmap[i] > 0 && noselected)
4290             continue;
4291           if (MAPTST(&obsmap, i))
4292             continue;
4293           s = pool->solvables + i;
4294           if (!MAPTST(&solv->suggestsmap, i))
4295             {
4296               if (!s->enhances)
4297                 continue;
4298               if (!pool_installable(pool, s))
4299                 continue;
4300               if (!solver_is_enhancing(solv, s))
4301                 continue;
4302             }
4303           queue_push(suggestionsq, i);
4304         }
4305       policy_filter_unwanted(solv, suggestionsq, POLICY_MODE_SUGGEST);
4306     }
4307
4308   /* undo removedisabledconflicts */
4309   if (redoq.count)
4310     undo_removedisabledconflicts(solv, &redoq);
4311   queue_free(&redoq);
4312
4313   /* undo job rule disabling */
4314   for (i = 0; i < disabledq.count; i++)
4315     solver_enablerule(solv, solv->rules + disabledq.elements[i]);
4316   queue_free(&disabledq);
4317   map_free(&obsmap);
4318 }
4319
4320
4321 /***********************************************************************/
4322 /* disk usage computations */
4323
4324 /*-------------------------------------------------------------------
4325  *
4326  * calculate DU changes
4327  */
4328
4329 void
4330 solver_calc_duchanges(Solver *solv, DUChanges *mps, int nmps)
4331 {
4332   Map installedmap;
4333
4334   solver_create_state_maps(solv, &installedmap, 0);
4335   pool_calc_duchanges(solv->pool, &installedmap, mps, nmps);
4336   map_free(&installedmap);
4337 }
4338
4339
4340 /*-------------------------------------------------------------------
4341  *
4342  * calculate changes in install size
4343  */
4344
4345 int
4346 solver_calc_installsizechange(Solver *solv)
4347 {
4348   Map installedmap;
4349   int change;
4350
4351   solver_create_state_maps(solv, &installedmap, 0);
4352   change = pool_calc_installsizechange(solv->pool, &installedmap);
4353   map_free(&installedmap);
4354   return change;
4355 }
4356
4357 void
4358 solver_create_state_maps(Solver *solv, Map *installedmap, Map *conflictsmap)
4359 {
4360   pool_create_state_maps(solv->pool, &solv->decisionq, installedmap, conflictsmap);
4361 }
4362
4363 void
4364 solver_trivial_installable(Solver *solv, Queue *pkgs, Queue *res)
4365 {
4366   Pool *pool = solv->pool;
4367   Map installedmap;
4368   int i;
4369   pool_create_state_maps(pool,  &solv->decisionq, &installedmap, 0);
4370   pool_trivial_installable_multiversionmap(pool, &installedmap, pkgs, res, solv->multiversion.size ? &solv->multiversion : 0);
4371   for (i = 0; i < res->count; i++)
4372     if (res->elements[i] != -1)
4373       {
4374         Solvable *s = pool->solvables + pkgs->elements[i];
4375         if (!strncmp("patch:", pool_id2str(pool, s->name), 6) && solvable_is_irrelevant_patch(s, &installedmap))
4376           res->elements[i] = -1;
4377       }
4378   map_free(&installedmap);
4379 }
4380
4381 /*-------------------------------------------------------------------
4382  *
4383  * decision introspection
4384  */
4385
4386 int
4387 solver_get_decisionlevel(Solver *solv, Id p)
4388 {
4389   return solv->decisionmap[p];
4390 }
4391
4392 void
4393 solver_get_decisionqueue(Solver *solv, Queue *decisionq)
4394 {
4395   queue_free(decisionq);
4396   queue_init_clone(decisionq, &solv->decisionq);
4397 }
4398
4399 int
4400 solver_get_lastdecisionblocklevel(Solver *solv)
4401 {
4402   Id p;
4403   if (solv->decisionq.count == 0)
4404     return 0;
4405   p = solv->decisionq.elements[solv->decisionq.count - 1];
4406   if (p < 0)
4407     p = -p;
4408   return solv->decisionmap[p] < 0 ? -solv->decisionmap[p] : solv->decisionmap[p];
4409 }
4410
4411 void
4412 solver_get_decisionblock(Solver *solv, int level, Queue *decisionq)
4413 {
4414   Id p;
4415   int i;
4416
4417   queue_empty(decisionq);
4418   for (i = 0; i < solv->decisionq.count; i++)
4419     {
4420       p = solv->decisionq.elements[i];
4421       if (p < 0)
4422         p = -p;
4423       if (solv->decisionmap[p] == level || solv->decisionmap[p] == -level)
4424         break;
4425     }
4426   if (i == solv->decisionq.count)
4427     return;
4428   for (i = 0; i < solv->decisionq.count; i++)
4429     {
4430       p = solv->decisionq.elements[i];
4431       if (p < 0)
4432         p = -p;
4433       if (solv->decisionmap[p] == level || solv->decisionmap[p] == -level)
4434         queue_push(decisionq, p);
4435       else
4436         break;
4437     }
4438 }
4439
4440 int
4441 solver_describe_decision(Solver *solv, Id p, Id *infop)
4442 {
4443   int i;
4444   Id pp, why;
4445
4446   if (infop)
4447     *infop = 0;
4448   if (!solv->decisionmap[p])
4449     return SOLVER_REASON_UNRELATED;
4450   pp = solv->decisionmap[p] < 0 ? -p : p;
4451   for (i = 0; i < solv->decisionq.count; i++)
4452     if (solv->decisionq.elements[i] == pp)
4453       break;
4454   if (i == solv->decisionq.count)       /* just in case... */
4455     return SOLVER_REASON_UNRELATED;
4456   why = solv->decisionq_why.elements[i];
4457   if (infop)
4458     *infop = why > 0 ? why : -why;
4459   if (why > 0)
4460     return SOLVER_REASON_UNIT_RULE;
4461   why = -why;
4462   if (i == 0)
4463     return SOLVER_REASON_KEEP_INSTALLED;        /* the systemsolvable */
4464   if (i < solv->decisioncnt_update)
4465     return SOLVER_REASON_RESOLVE_JOB;
4466   if (i < solv->decisioncnt_keep)
4467     {
4468       if (why == 0 && pp < 0)
4469         return SOLVER_REASON_CLEANDEPS_ERASE;
4470       return SOLVER_REASON_UPDATE_INSTALLED;
4471     }
4472   if (i < solv->decisioncnt_resolve)
4473     {
4474       if (solv->focus_installed && i >= solv->decisioncnt_jobs)
4475         return SOLVER_REASON_RESOLVE_JOB;
4476       if (why == 0 && pp < 0)
4477         return SOLVER_REASON_CLEANDEPS_ERASE;
4478       return SOLVER_REASON_KEEP_INSTALLED;
4479     }
4480   if (i < solv->decisioncnt_weak)
4481     {
4482       if (why == 0 && pp < 0)
4483         return SOLVER_REASON_CLEANDEPS_ERASE;
4484     }
4485   if (why > 0)
4486     return SOLVER_REASON_RESOLVE;
4487   /* weak or orphaned */
4488   if (i < solv->decisioncnt_orphan)
4489     return SOLVER_REASON_WEAKDEP;
4490   return SOLVER_REASON_RESOLVE_ORPHAN;
4491 }
4492
4493
4494 void
4495 solver_describe_weakdep_decision(Solver *solv, Id p, Queue *whyq)
4496 {
4497   Pool *pool = solv->pool;
4498   int i;
4499   int level = solv->decisionmap[p];
4500   int decisionno;
4501   Solvable *s;
4502
4503   queue_empty(whyq);
4504   if (level < 0)
4505     return;     /* huh? */
4506   for (decisionno = 0; decisionno < solv->decisionq.count; decisionno++)
4507     if (solv->decisionq.elements[decisionno] == p)
4508       break;
4509   if (decisionno == solv->decisionq.count)
4510     return;     /* huh? */
4511   if (decisionno < solv->decisioncnt_weak || decisionno >= solv->decisioncnt_orphan)
4512     return;     /* huh? */
4513
4514   /* 1) list all packages that recommend us */
4515   for (i = 1; i < pool->nsolvables; i++)
4516     {
4517       Id *recp, rec, pp2, p2;
4518       if (solv->decisionmap[i] < 0 || solv->decisionmap[i] >= level)
4519         continue;
4520       s = pool->solvables + i;
4521       if (!s->recommends)
4522         continue;
4523       if (!solv->addalreadyrecommended && s->repo == solv->installed)
4524         continue;
4525       recp = s->repo->idarraydata + s->recommends;
4526       while ((rec = *recp++) != 0)
4527         {
4528           int found = 0;
4529           FOR_PROVIDES(p2, pp2, rec)
4530             {
4531               if (p2 == p)
4532                 found = 1;
4533               else
4534                 {
4535                   /* if p2 is already installed, this recommends is ignored */
4536                   if (solv->decisionmap[p2] > 0 && solv->decisionmap[p2] < level)
4537                     break;
4538                 }
4539             }
4540           if (!p2 && found)
4541             {
4542               queue_push(whyq, SOLVER_REASON_RECOMMENDED);
4543               queue_push2(whyq, i, rec);
4544             }
4545         }
4546     }
4547   /* 2) list all supplements */
4548   s = pool->solvables + p;
4549   if (s->supplements && level > 0)
4550     {
4551       Id *supp, sup, pp2, p2;
4552       /* this is a hack. to use solver_dep_fulfilled we temporarily clear
4553        * everything above our level in the decisionmap */
4554       for (i = decisionno; i < solv->decisionq.count; i++ )
4555         {
4556           p2 = solv->decisionq.elements[i];
4557           if (p2 > 0)
4558             solv->decisionmap[p2] = -solv->decisionmap[p2];
4559         }
4560       supp = s->repo->idarraydata + s->supplements;
4561       while ((sup = *supp++) != 0)
4562         if (solver_dep_fulfilled(solv, sup))
4563           {
4564             int found = 0;
4565             /* let's see if this is an easy supp */
4566             FOR_PROVIDES(p2, pp2, sup)
4567               {
4568                 if (!solv->addalreadyrecommended && solv->installed)
4569                   {
4570                     if (pool->solvables[p2].repo == solv->installed)
4571                       continue;
4572                   }
4573                 if (solv->decisionmap[p2] > 0 && solv->decisionmap[p2] < level)
4574                   {
4575                     queue_push(whyq, SOLVER_REASON_SUPPLEMENTED);
4576                     queue_push2(whyq, p2, sup);
4577                     found = 1;
4578                   }
4579               }
4580             if (!found)
4581               {
4582                 /* hard case, just note dependency with no package */
4583                 queue_push(whyq, SOLVER_REASON_SUPPLEMENTED);
4584                 queue_push2(whyq, 0, sup);
4585               }
4586           }
4587       for (i = decisionno; i < solv->decisionq.count; i++)
4588         {
4589           p2 = solv->decisionq.elements[i];
4590           if (p2 > 0)
4591             solv->decisionmap[p2] = -solv->decisionmap[p2];
4592         }
4593     }
4594 }
4595
4596 void
4597 pool_job2solvables(Pool *pool, Queue *pkgs, Id how, Id what)
4598 {
4599   Id p, pp;
4600   how &= SOLVER_SELECTMASK;
4601   queue_empty(pkgs);
4602   if (how == SOLVER_SOLVABLE_ALL)
4603     {
4604       FOR_POOL_SOLVABLES(p)
4605         queue_push(pkgs, p);
4606     }
4607   else if (how == SOLVER_SOLVABLE_REPO)
4608     {
4609       Repo *repo = pool_id2repo(pool, what);
4610       Solvable *s;
4611       if (repo)
4612         FOR_REPO_SOLVABLES(repo, p, s)
4613           queue_push(pkgs, p);
4614     }
4615   else
4616     {
4617       FOR_JOB_SELECT(p, pp, how, what)
4618         queue_push(pkgs, p);
4619     }
4620 }
4621
4622 int
4623 pool_isemptyupdatejob(Pool *pool, Id how, Id what)
4624 {
4625   Id p, pp, pi, pip;
4626   Id select = how & SOLVER_SELECTMASK;
4627   if ((how & SOLVER_JOBMASK) != SOLVER_UPDATE)
4628     return 0;
4629   if (select == SOLVER_SOLVABLE_ALL || select == SOLVER_SOLVABLE_REPO)
4630     return 0;
4631   if (!pool->installed)
4632     return 1;
4633   FOR_JOB_SELECT(p, pp, select, what)
4634     if (pool->solvables[p].repo == pool->installed)
4635       return 0;
4636   /* hard work */
4637   FOR_JOB_SELECT(p, pp, select, what)
4638     {
4639       Solvable *s = pool->solvables + p;
4640       FOR_PROVIDES(pi, pip, s->name)
4641         {
4642           Solvable *si = pool->solvables + pi;
4643           if (si->repo != pool->installed || si->name != s->name)
4644             continue;
4645           return 0;
4646         }
4647       if (s->obsoletes)
4648         {
4649           Id obs, *obsp = s->repo->idarraydata + s->obsoletes;
4650           while ((obs = *obsp++) != 0)
4651             {
4652               FOR_PROVIDES(pi, pip, obs)
4653                 {
4654                   Solvable *si = pool->solvables + pi;
4655                   if (si->repo != pool->installed)
4656                     continue;
4657                   if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, si, obs))
4658                     continue;
4659                   if (pool->obsoleteusescolors && !pool_colormatch(pool, s, si))
4660                     continue;
4661                   return 0;
4662                 }
4663             }
4664         }
4665     }
4666   return 1;
4667 }
4668
4669 static int
4670 get_userinstalled_cmp(const void *ap, const void *bp, void *dp)
4671 {
4672   return *(Id *)ap - *(Id *)bp;
4673 }
4674
4675 static int
4676 get_userinstalled_cmp_names(const void *ap, const void *bp, void *dp)
4677 {
4678   Pool *pool = dp;
4679   return strcmp(pool_id2str(pool, *(Id *)ap), pool_id2str(pool, *(Id *)bp));
4680 }
4681
4682 static int
4683 get_userinstalled_cmp_namearch(const void *ap, const void *bp, void *dp)
4684 {
4685   Pool *pool = dp;
4686   int r;
4687   r = strcmp(pool_id2str(pool, ((Id *)ap)[0]), pool_id2str(pool, ((Id *)bp)[0]));
4688   if (r)
4689     return r;
4690   return strcmp(pool_id2str(pool, ((Id *)ap)[1]), pool_id2str(pool, ((Id *)bp)[1]));
4691 }
4692
4693 static void
4694 get_userinstalled_sort_uniq(Pool *pool, Queue *q, int flags)
4695 {
4696   Id lastp = -1, lasta = -1;
4697   int i, j;
4698   if (q->count < ((flags & GET_USERINSTALLED_NAMEARCH) ? 4 : 2))
4699     return;
4700   if ((flags & GET_USERINSTALLED_NAMEARCH) != 0)
4701     solv_sort(q->elements, q->count / 2, 2 * sizeof(Id), get_userinstalled_cmp_namearch, pool);
4702   else if ((flags & GET_USERINSTALLED_NAMES) != 0)
4703     solv_sort(q->elements, q->count, sizeof(Id), get_userinstalled_cmp_names, pool);
4704   else
4705     solv_sort(q->elements, q->count, sizeof(Id), get_userinstalled_cmp, 0);
4706   if ((flags & GET_USERINSTALLED_NAMEARCH) != 0)
4707     {
4708       for (i = j = 0; i < q->count; i += 2)
4709         if (q->elements[i] != lastp || q->elements[i + 1] != lasta)
4710           {
4711             q->elements[j++] = lastp = q->elements[i];
4712             q->elements[j++] = lasta = q->elements[i + 1];
4713           }
4714     }
4715   else
4716     {
4717       for (i = j = 0; i < q->count; i++)
4718         if (q->elements[i] != lastp)
4719           q->elements[j++] = lastp = q->elements[i];
4720     }
4721   queue_truncate(q, j);
4722 }
4723
4724 static void
4725 namearch2solvables(Pool *pool, Queue *q, Queue *qout, int job)
4726 {
4727   int i;
4728   if (!pool->installed)
4729     return;
4730   for (i = 0; i < q->count; i += 2)
4731     {
4732       Id p, pp, name = q->elements[i], arch = q->elements[i + 1];
4733       FOR_PROVIDES(p, pp, name)
4734         {
4735           Solvable *s = pool->solvables + p;
4736           if (s->repo != pool->installed || s->name != name || (arch && s->arch != arch))
4737             continue;
4738           if (job)
4739             queue_push(qout, job);
4740           queue_push(qout, p);
4741         }
4742     }
4743 }
4744
4745 void
4746 solver_get_userinstalled(Solver *solv, Queue *q, int flags)
4747 {
4748   Pool *pool = solv->pool;
4749   Id p, p2, pp;
4750   Solvable *s;
4751   Repo *installed = solv->installed;
4752   int i, j;
4753   Map userinstalled;
4754
4755   map_init(&userinstalled, 0);
4756   queue_empty(q);
4757   /* first process jobs */
4758   for (i = 0; i < solv->job.count; i += 2)
4759     {
4760       Id how = solv->job.elements[i];
4761       Id what, select;
4762       if (installed && (how & SOLVER_JOBMASK) == SOLVER_USERINSTALLED)
4763         {
4764           if (!userinstalled.size)
4765             map_grow(&userinstalled, installed->end - installed->start);
4766           what = solv->job.elements[i + 1];
4767           select = how & SOLVER_SELECTMASK;
4768           if (select == SOLVER_SOLVABLE_ALL || (select == SOLVER_SOLVABLE_REPO && what == installed->repoid))
4769             FOR_REPO_SOLVABLES(installed, p, s)
4770               MAPSET(&userinstalled, p - installed->start);
4771           FOR_JOB_SELECT(p, pp, select, what)
4772             if (pool->solvables[p].repo == installed)
4773               MAPSET(&userinstalled, p - installed->start);
4774           continue;
4775         }
4776       if ((how & SOLVER_JOBMASK) != SOLVER_INSTALL)
4777         continue;
4778       if ((how & SOLVER_NOTBYUSER) != 0)
4779         continue;
4780       what = solv->job.elements[i + 1];
4781       select = how & SOLVER_SELECTMASK;
4782       FOR_JOB_SELECT(p, pp, select, what)
4783         if (solv->decisionmap[p] > 0)
4784           {
4785             queue_push(q, p);
4786 #ifdef ENABLE_LINKED_PKGS
4787             if (has_package_link(pool, pool->solvables + p))
4788               {
4789                 int j;
4790                 Queue lq;
4791                 queue_init(&lq);
4792                 find_package_link(pool, pool->solvables + p, 0, &lq, 0, 0);
4793                 for (j = 0; j < lq.count; j++)
4794                   if (solv->decisionmap[lq.elements[j]] > 0)
4795                     queue_push(q, lq.elements[j]);
4796               }
4797 #endif
4798           }
4799     }
4800   /* now process updates of userinstalled packages */
4801   if (installed && userinstalled.size)
4802     {
4803       for (i = 1; i < solv->decisionq.count; i++)
4804         {
4805           p = solv->decisionq.elements[i];
4806           if (p <= 0)
4807             continue;
4808           s = pool->solvables + p;
4809           if (!s->repo)
4810             continue;
4811           if (s->repo == installed)
4812             {
4813               if (MAPTST(&userinstalled, p - installed->start))
4814                 queue_push(q, p);
4815               continue;
4816             }
4817           /* new package, check if we replace a userinstalled one */
4818           FOR_PROVIDES(p2, pp, s->name)
4819             {
4820               Solvable *ps = pool->solvables + p2;
4821               if (p2 == p || ps->repo != installed || !MAPTST(&userinstalled, p2 - installed->start))
4822                 continue;
4823               if (!pool->implicitobsoleteusesprovides && s->name != ps->name)
4824                 continue;
4825               if (pool->implicitobsoleteusescolors && !pool_colormatch(pool, s, ps))
4826                 continue;
4827               queue_push(q, p);
4828               break;
4829             }
4830           if (!p2 && s->repo != installed && s->obsoletes)
4831             {
4832               Id obs, *obsp = s->repo->idarraydata + s->obsoletes;
4833               while ((obs = *obsp++) != 0)
4834                 {
4835                   FOR_PROVIDES(p2, pp, obs)
4836                     {
4837                       Solvable *ps = pool->solvables + p2;
4838                       if (p2 == p || ps->repo != installed || !MAPTST(&userinstalled, p2 - installed->start))
4839                         continue;
4840                       if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
4841                         continue;
4842                       if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
4843                         continue;
4844                       queue_push(q, p);
4845                       break;
4846                     }
4847                   if (p2)
4848                     break;
4849                 }
4850             }
4851         }
4852     }
4853   map_free(&userinstalled);
4854
4855   /* convert to desired output format */
4856   if ((flags & GET_USERINSTALLED_NAMEARCH) != 0)
4857     {
4858       int qcount = q->count;
4859       queue_insertn(q, 0, qcount, 0);
4860       for (i = j = 0; i < qcount; i++)
4861         {
4862           s = pool->solvables + q->elements[i + qcount];
4863           q->elements[j++] = s->name;
4864           q->elements[j++] = s->arch;
4865         }
4866     }
4867   else if ((flags & GET_USERINSTALLED_NAMES) != 0)
4868     {
4869       for (i = 0; i < q->count; i++)
4870         {
4871           s = pool->solvables + q->elements[i];
4872           q->elements[i] = s->name;
4873         }
4874     }
4875   /* sort and unify */
4876   get_userinstalled_sort_uniq(pool, q, flags);
4877
4878   /* invert if asked for */
4879   if ((flags & GET_USERINSTALLED_INVERTED) != 0)
4880     {
4881       /* first generate queue with all installed packages */
4882       Queue invq;
4883       queue_init(&invq);
4884       for (i = 1; i < solv->decisionq.count; i++)
4885         {
4886           p = solv->decisionq.elements[i];
4887           if (p <= 0)
4888             continue;
4889           s = pool->solvables + p;
4890           if (!s->repo)
4891             continue;
4892           if ((flags & GET_USERINSTALLED_NAMEARCH) != 0)
4893             queue_push2(&invq, s->name, s->arch);
4894           else if ((flags & GET_USERINSTALLED_NAMES) != 0)
4895             queue_push(&invq, s->name);
4896           else
4897             queue_push(&invq, p);
4898         }
4899       /* push q on invq, just in case... */
4900       queue_insertn(&invq, invq.count, q->count, q->elements);
4901       get_userinstalled_sort_uniq(pool, &invq, flags);
4902       /* subtract queues (easy as they are sorted and invq is a superset of q) */
4903       if ((flags & GET_USERINSTALLED_NAMEARCH) != 0)
4904         {
4905           if (q->count)
4906             {
4907               for (i = j = 0; i < invq.count; i += 2)
4908                 if (invq.elements[i] == q->elements[j] && invq.elements[i + 1] == q->elements[j + 1])
4909                   {
4910                     invq.elements[i] = invq.elements[i + 1] = 0;
4911                     j += 2;
4912                     if (j >= q->count)
4913                       break;
4914                   }
4915               queue_empty(q);
4916             }
4917           for (i = 0; i < invq.count; i += 2)
4918             if (invq.elements[i])
4919               queue_push2(q, invq.elements[i], invq.elements[i + 1]);
4920         }
4921       else
4922         {
4923           if (q->count)
4924             {
4925               for (i = j = 0; i < invq.count; i++)
4926                 if (invq.elements[i] == q->elements[j])
4927                   {
4928                     invq.elements[i] = 0;
4929                     if (++j >= q->count)
4930                       break;
4931                   }
4932               queue_empty(q);
4933             }
4934           for (i = 0; i < invq.count; i++)
4935             if (invq.elements[i])
4936               queue_push(q, invq.elements[i]);
4937         }
4938       queue_free(&invq);
4939     }
4940 }
4941
4942 void
4943 pool_add_userinstalled_jobs(Pool *pool, Queue *q, Queue *job, int flags)
4944 {
4945   int i;
4946
4947   if ((flags & GET_USERINSTALLED_INVERTED) != 0)
4948     {
4949       Queue invq;
4950       Id p, lastid;
4951       Solvable *s;
4952       int bad;
4953       if (!pool->installed)
4954         return;
4955       queue_init(&invq);
4956       if ((flags & GET_USERINSTALLED_NAMEARCH) != 0)
4957         flags &= ~GET_USERINSTALLED_NAMES;      /* just in case */
4958       FOR_REPO_SOLVABLES(pool->installed, p, s)
4959         queue_push(&invq, flags & GET_USERINSTALLED_NAMES ? s->name : p);
4960       if ((flags & GET_USERINSTALLED_NAMEARCH) != 0)
4961         {
4962           /* for namearch we convert to packages */
4963           namearch2solvables(pool, q, &invq, 0);
4964           get_userinstalled_sort_uniq(pool, &invq, flags);
4965           namearch2solvables(pool, q, &invq, 0);
4966           flags = 0;
4967         }
4968       else
4969         {
4970           queue_insertn(&invq, invq.count, q->count, q->elements);
4971           get_userinstalled_sort_uniq(pool, &invq, flags);
4972           /* now the fun part, add q again, sort, and remove all dups */
4973           queue_insertn(&invq, invq.count, q->count, q->elements);
4974         }
4975       if (invq.count > 1)
4976         {
4977           if ((flags & GET_USERINSTALLED_NAMES) != 0)
4978             solv_sort(invq.elements, invq.count, sizeof(Id), get_userinstalled_cmp_names, pool);
4979           else
4980             solv_sort(invq.elements, invq.count, sizeof(Id), get_userinstalled_cmp, 0);
4981         }
4982       lastid = -1;
4983       bad = 1;
4984       for (i = 0; i < invq.count; i++)
4985         {
4986           if (invq.elements[i] == lastid)
4987             {
4988               bad = 1;
4989               continue;
4990             }
4991           if (!bad)
4992             queue_push2(job, SOLVER_USERINSTALLED | (flags & GET_USERINSTALLED_NAMES ? SOLVER_SOLVABLE_NAME : SOLVER_SOLVABLE), lastid);
4993           bad = 0;
4994           lastid = invq.elements[i];
4995         }
4996       if (!bad)
4997         queue_push2(job, SOLVER_USERINSTALLED | (flags & GET_USERINSTALLED_NAMES ? SOLVER_SOLVABLE_NAME : SOLVER_SOLVABLE), lastid);
4998       queue_free(&invq);
4999     }
5000   else
5001     {
5002       if (flags & GET_USERINSTALLED_NAMEARCH)
5003         namearch2solvables(pool, q, job, SOLVER_USERINSTALLED | SOLVER_SOLVABLE);
5004       else
5005         {
5006           for (i = 0; i < q->count; i++)
5007             queue_push2(job, SOLVER_USERINSTALLED | (flags & GET_USERINSTALLED_NAMES ? SOLVER_SOLVABLE_NAME : SOLVER_SOLVABLE), q->elements[i]);
5008         }
5009     }
5010 }
5011
5012 int
5013 solver_alternatives_count(Solver *solv)
5014 {
5015   Id *elements = solv->branches.elements;
5016   int res, count;
5017   for (res = 0, count = solv->branches.count; count; res++)
5018     count -= elements[count - 2];
5019   return res;
5020 }
5021
5022 int
5023 solver_get_alternative(Solver *solv, Id alternative, Id *idp, Id *fromp, Id *chosenp, Queue *choices, int *levelp)
5024 {
5025   int cnt = solver_alternatives_count(solv);
5026   int count = solv->branches.count;
5027   Id *elements = solv->branches.elements;
5028   if (choices)
5029     queue_empty(choices);
5030   if (alternative <= 0 || alternative > cnt)
5031     return 0;
5032   elements += count;
5033   for (; cnt > alternative; cnt--)
5034     elements -= elements[-2];
5035   if (levelp)
5036     *levelp = elements[-1];
5037   if (fromp)
5038     *fromp = elements[-4];
5039   if (idp)
5040     *idp = elements[-3];
5041   if (chosenp)
5042     {
5043       int i;
5044       *chosenp = 0;
5045       for (i = elements[-2]; i > 4; i--)
5046         {
5047           Id p = -elements[-i];
5048           if (p > 0 && solv->decisionmap[p] == elements[-1] + 1)
5049             {
5050               *chosenp = p;
5051               break;
5052             }
5053         }
5054     }
5055   if (choices)
5056     queue_insertn(choices, 0, elements[-2] - 4, elements - elements[-2]);
5057   return elements[-4] ? SOLVER_ALTERNATIVE_TYPE_RECOMMENDS : SOLVER_ALTERNATIVE_TYPE_RULE;
5058 }
5059
5060 const char *
5061 solver_select2str(Pool *pool, Id select, Id what)
5062 {
5063   const char *s;
5064   char *b;
5065   select &= SOLVER_SELECTMASK;
5066   if (select == SOLVER_SOLVABLE)
5067     return pool_solvid2str(pool, what);
5068   if (select == SOLVER_SOLVABLE_NAME)
5069     return pool_dep2str(pool, what);
5070   if (select == SOLVER_SOLVABLE_PROVIDES)
5071     {
5072       s = pool_dep2str(pool, what);
5073       b = pool_alloctmpspace(pool, 11 + strlen(s));
5074       sprintf(b, "providing %s", s);
5075       return b;
5076     }
5077   if (select == SOLVER_SOLVABLE_ONE_OF)
5078     {
5079       Id p;
5080       b = 0;
5081       while ((p = pool->whatprovidesdata[what++]) != 0)
5082         {
5083           s = pool_solvid2str(pool, p);
5084           if (b)
5085             b = pool_tmpappend(pool, b, ", ", s);
5086           else
5087             b = pool_tmpjoin(pool, s, 0, 0);
5088           pool_freetmpspace(pool, s);
5089         }
5090       return b ? b : "nothing";
5091     }
5092   if (select == SOLVER_SOLVABLE_REPO)
5093     {
5094       b = pool_alloctmpspace(pool, 20);
5095       sprintf(b, "repo #%d", what);
5096       return b;
5097     }
5098   if (select == SOLVER_SOLVABLE_ALL)
5099     return "all packages";
5100   return "unknown job select";
5101 }
5102
5103 const char *
5104 pool_job2str(Pool *pool, Id how, Id what, Id flagmask)
5105 {
5106   Id select = how & SOLVER_SELECTMASK;
5107   const char *strstart = 0, *strend = 0;
5108   char *s;
5109   int o;
5110
5111   switch (how & SOLVER_JOBMASK)
5112     {
5113     case SOLVER_NOOP:
5114       return "do nothing";
5115     case SOLVER_INSTALL:
5116       if (select == SOLVER_SOLVABLE && pool->installed && pool->solvables[what].repo == pool->installed)
5117         strstart = "keep ", strend = " installed";
5118       else if (select == SOLVER_SOLVABLE || select == SOLVER_SOLVABLE_NAME)
5119         strstart = "install ";
5120       else if (select == SOLVER_SOLVABLE_PROVIDES)
5121         strstart = "install a package ";
5122       else
5123         strstart = "install one of ";
5124       break;
5125     case SOLVER_ERASE:
5126       if (select == SOLVER_SOLVABLE && !(pool->installed && pool->solvables[what].repo == pool->installed))
5127         strstart = "keep ", strend = " uninstalled";
5128       else if (select == SOLVER_SOLVABLE_PROVIDES)
5129         strstart = "deinstall all packages ";
5130       else
5131         strstart = "deinstall ";
5132       break;
5133     case SOLVER_UPDATE:
5134       strstart = "update ";
5135       break;
5136     case SOLVER_WEAKENDEPS:
5137       strstart = "weaken deps of ";
5138       break;
5139     case SOLVER_MULTIVERSION:
5140       strstart = "multi version ";
5141       break;
5142     case SOLVER_LOCK:
5143       strstart = "lock ";
5144       break;
5145     case SOLVER_DISTUPGRADE:
5146       strstart = "dist upgrade ";
5147       break;
5148     case SOLVER_VERIFY:
5149       strstart = "verify ";
5150       break;
5151     case SOLVER_DROP_ORPHANED:
5152       strstart = "deinstall ", strend = " if orphaned";
5153       break;
5154     case SOLVER_USERINSTALLED:
5155       strstart = "regard ", strend = " as userinstalled";
5156       break;
5157     case SOLVER_ALLOWUNINSTALL:
5158       strstart = "allow deinstallation of ";
5159       break;
5160     default:
5161       strstart = "unknown job ";
5162       break;
5163     }
5164   s = pool_tmpjoin(pool, strstart, solver_select2str(pool, select, what), strend);
5165   how &= flagmask;
5166   if ((how & ~(SOLVER_SELECTMASK|SOLVER_JOBMASK)) == 0)
5167     return s;
5168   o = strlen(s);
5169   s = pool_tmpappend(pool, s, " ", 0);
5170   if (how & SOLVER_WEAK)
5171     s = pool_tmpappend(pool, s, ",weak", 0);
5172   if (how & SOLVER_ESSENTIAL)
5173     s = pool_tmpappend(pool, s, ",essential", 0);
5174   if (how & SOLVER_CLEANDEPS)
5175     s = pool_tmpappend(pool, s, ",cleandeps", 0);
5176   if (how & SOLVER_ORUPDATE)
5177     s = pool_tmpappend(pool, s, ",orupdate", 0);
5178   if (how & SOLVER_FORCEBEST)
5179     s = pool_tmpappend(pool, s, ",forcebest", 0);
5180   if (how & SOLVER_TARGETED)
5181     s = pool_tmpappend(pool, s, ",targeted", 0);
5182   if (how & SOLVER_SETEV)
5183     s = pool_tmpappend(pool, s, ",setev", 0);
5184   if (how & SOLVER_SETEVR)
5185     s = pool_tmpappend(pool, s, ",setevr", 0);
5186   if (how & SOLVER_SETARCH)
5187     s = pool_tmpappend(pool, s, ",setarch", 0);
5188   if (how & SOLVER_SETVENDOR)
5189     s = pool_tmpappend(pool, s, ",setvendor", 0);
5190   if (how & SOLVER_SETREPO)
5191     s = pool_tmpappend(pool, s, ",setrepo", 0);
5192   if (how & SOLVER_SETNAME)
5193     s = pool_tmpappend(pool, s, ",setname", 0);
5194   if (how & SOLVER_NOAUTOSET)
5195     s = pool_tmpappend(pool, s, ",noautoset", 0);
5196   if (s[o + 1] != ',')
5197     s = pool_tmpappend(pool, s, ",?", 0);
5198   s[o + 1] = '[';
5199   return pool_tmpappend(pool, s, "]", 0);
5200 }
5201
5202 const char *
5203 solver_alternative2str(Solver *solv, int type, Id id, Id from)
5204 {
5205   Pool *pool = solv->pool;
5206   if (type == SOLVER_ALTERNATIVE_TYPE_RECOMMENDS)
5207     {
5208       const char *s = pool_dep2str(pool, id);
5209       return pool_tmpappend(pool, s, ", recommended by ", pool_solvid2str(pool, from));
5210     }
5211   if (type == SOLVER_ALTERNATIVE_TYPE_RULE)
5212     {
5213       int rtype;
5214       Id depfrom, depto, dep;
5215       char buf[64];
5216       if (solver_ruleclass(solv, id) == SOLVER_RULE_CHOICE)
5217         id = solver_rule2pkgrule(solv, id);
5218       rtype = solver_ruleinfo(solv, id, &depfrom, &depto, &dep);
5219       if ((rtype & SOLVER_RULE_TYPEMASK) == SOLVER_RULE_JOB)
5220         {
5221           if ((depto & SOLVER_SELECTMASK) == SOLVER_SOLVABLE_PROVIDES)
5222             return pool_dep2str(pool, dep);
5223           return solver_select2str(pool, depto & SOLVER_SELECTMASK, dep);
5224         }
5225       if (rtype == SOLVER_RULE_PKG_REQUIRES)
5226         {
5227           const char *s = pool_dep2str(pool, dep);
5228           return pool_tmpappend(pool, s, ", required by ", pool_solvid2str(pool, depfrom));
5229         }
5230       sprintf(buf, "Rule #%d", id);
5231       return pool_tmpjoin(pool, buf, 0, 0);
5232     }
5233   return "unknown alternative type";
5234 }
5235