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