src/solver.c

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