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