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