src/solver.c

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