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