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