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