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