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   queue_empty(&solv->branches);
 985
 986   /* adapt learnt rule status to new set of enabled/disabled rules */
 987   enabledisablelearntrules(solv);
 988
 989   /* redo all assertion rule decisions */
 990   makeruledecisions(solv);
 991   POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "decisions so far: %d\n", solv->decisionq.count);
 992 }
 993
 994
 995 /*-------------------------------------------------------------------
 996  *
 997  * analyze_unsolvable_rule
 998  *
 999  * recursion helper used by analyze_unsolvable
1000  */
1001
1002 static void
1003 analyze_unsolvable_rule(Solver *solv, Rule *r, Id *lastweakp, Map *rseen)
1004 {
1005   Pool *pool = solv->pool;
1006   int i;
1007   Id why = r - solv->rules;
1008
1009   IF_POOLDEBUG (SOLV_DEBUG_UNSOLVABLE)
1010     solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE, r);
1011   if (solv->learntrules && why >= solv->learntrules)
1012     {
1013       if (MAPTST(rseen, why - solv->learntrules))
1014         return;
1015       MAPSET(rseen, why - solv->learntrules);
1016       for (i = solv->learnt_why.elements[why - solv->learntrules]; solv->learnt_pool.elements[i]; i++)
1017         if (solv->learnt_pool.elements[i] > 0)
1018           analyze_unsolvable_rule(solv, solv->rules + solv->learnt_pool.elements[i], lastweakp, rseen);
1019       return;
1020     }
1021   if (MAPTST(&solv->weakrulemap, why))
1022     if (!*lastweakp || why > *lastweakp)
1023       *lastweakp = why;
1024   /* do not add rpm rules to problem */
1025   if (why < solv->rpmrules_end)
1026     return;
1027   /* turn rule into problem */
1028   if (why >= solv->jobrules && why < solv->jobrules_end)
1029     why = -(solv->ruletojob.elements[why - solv->jobrules] + 1);
1030   /* normalize dup/infarch rules */
1031   if (why > solv->infarchrules && why < solv->infarchrules_end)
1032     {
1033       Id name = pool->solvables[-solv->rules[why].p].name;
1034       while (why > solv->infarchrules && pool->solvables[-solv->rules[why - 1].p].name == name)
1035         why--;
1036     }
1037   if (why > solv->duprules && why < solv->duprules_end)
1038     {
1039       Id name = pool->solvables[-solv->rules[why].p].name;
1040       while (why > solv->duprules && pool->solvables[-solv->rules[why - 1].p].name == name)
1041         why--;
1042     }
1043
1044   /* return if problem already countains our rule */
1045   if (solv->problems.count)
1046     {
1047       for (i = solv->problems.count - 1; i >= 0; i--)
1048         if (solv->problems.elements[i] == 0)    /* end of last problem reached? */
1049           break;
1050         else if (solv->problems.elements[i] == why)
1051           return;
1052     }
1053   queue_push(&solv->problems, why);
1054 }
1055
1056
1057 /*-------------------------------------------------------------------
1058  *
1059  * analyze_unsolvable
1060  *
1061  * We know that the problem is not solvable. Record all involved
1062  * rules (i.e. the "proof") into solv->learnt_pool.
1063  * Record the learnt pool index and all non-rpm rules into
1064  * solv->problems. (Our solutions to fix the problems are to
1065  * disable those rules.)
1066  *
1067  * If the proof contains at least one weak rule, we disable the
1068  * last of them.
1069  *
1070  * Otherwise we return 0 if disablerules is not set or disable
1071  * _all_ of the problem rules and return 1.
1072  *
1073  * return: 1 - disabled some rules, try again
1074  *         0 - hopeless
1075  */
1076
1077 static int
1078 analyze_unsolvable(Solver *solv, Rule *cr, int disablerules)
1079 {
1080   Pool *pool = solv->pool;
1081   Rule *r;
1082   Map seen;             /* global to speed things up? */
1083   Map rseen;
1084   Id d, v, vv, *dp, why;
1085   int l, i, idx;
1086   Id *decisionmap = solv->decisionmap;
1087   int oldproblemcount;
1088   int oldlearntpoolcount;
1089   Id lastweak;
1090   int record_proof = 1;
1091
1092   POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "ANALYZE UNSOLVABLE ----------------------\n");
1093   solv->stats_unsolvable++;
1094   oldproblemcount = solv->problems.count;
1095   oldlearntpoolcount = solv->learnt_pool.count;
1096
1097   /* make room for proof index */
1098   /* must update it later, as analyze_unsolvable_rule would confuse
1099    * it with a rule index if we put the real value in already */
1100   queue_push(&solv->problems, 0);
1101
1102   r = cr;
1103   map_init(&seen, pool->nsolvables);
1104   map_init(&rseen, solv->learntrules ? solv->nrules - solv->learntrules : 0);
1105   if (record_proof)
1106     queue_push(&solv->learnt_pool, r - solv->rules);
1107   lastweak = 0;
1108   analyze_unsolvable_rule(solv, r, &lastweak, &rseen);
1109   d = r->d < 0 ? -r->d - 1 : r->d;
1110   dp = d ? pool->whatprovidesdata + d : 0;
1111   for (i = -1; ; i++)
1112     {
1113       if (i == -1)
1114         v = r->p;
1115       else if (d == 0)
1116         v = i ? 0 : r->w2;
1117       else
1118         v = *dp++;
1119       if (v == 0)
1120         break;
1121       if (DECISIONMAP_TRUE(v))  /* the one true literal */
1122           continue;
1123       vv = v > 0 ? v : -v;
1124       l = solv->decisionmap[vv];
1125       if (l < 0)
1126         l = -l;
1127       MAPSET(&seen, vv);
1128     }
1129   idx = solv->decisionq.count;
1130   while (idx > 0)
1131     {
1132       v = solv->decisionq.elements[--idx];
1133       vv = v > 0 ? v : -v;
1134       if (!MAPTST(&seen, vv))
1135         continue;
1136       why = solv->decisionq_why.elements[idx];
1137       assert(why > 0);
1138       if (record_proof)
1139         queue_push(&solv->learnt_pool, why);
1140       r = solv->rules + why;
1141       analyze_unsolvable_rule(solv, r, &lastweak, &rseen);
1142       d = r->d < 0 ? -r->d - 1 : r->d;
1143       dp = d ? pool->whatprovidesdata + d : 0;
1144       for (i = -1; ; i++)
1145         {
1146           if (i == -1)
1147             v = r->p;
1148           else if (d == 0)
1149             v = i ? 0 : r->w2;
1150           else
1151             v = *dp++;
1152           if (v == 0)
1153             break;
1154           if (DECISIONMAP_TRUE(v))      /* the one true literal */
1155               continue;
1156           vv = v > 0 ? v : -v;
1157           l = solv->decisionmap[vv];
1158           if (l < 0)
1159             l = -l;
1160           MAPSET(&seen, vv);
1161         }
1162     }
1163   map_free(&seen);
1164   map_free(&rseen);
1165   queue_push(&solv->problems, 0);       /* mark end of this problem */
1166
1167   if (lastweak)
1168     {
1169       /* disable last weak rule */
1170       solv->problems.count = oldproblemcount;
1171       solv->learnt_pool.count = oldlearntpoolcount;
1172       if (lastweak >= solv->jobrules && lastweak < solv->jobrules_end)
1173         v = -(solv->ruletojob.elements[lastweak - solv->jobrules] + 1);
1174       else
1175         v = lastweak;
1176       POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "disabling ");
1177       solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE, solv->rules + lastweak);
1178       if (lastweak >= solv->choicerules && lastweak < solv->choicerules_end)
1179         solver_disablechoicerules(solv, solv->rules + lastweak);
1180       solver_disableproblem(solv, v);
1181       if (v < 0)
1182         solver_reenablepolicyrules(solv, -v);
1183       solver_reset(solv);
1184       return 1;
1185     }
1186
1187   if (solv->allowuninstall && (v = autouninstall(solv, solv->problems.elements + oldproblemcount + 1)) != 0)
1188     {
1189       solv->problems.count = oldproblemcount;
1190       solv->learnt_pool.count = oldlearntpoolcount;
1191       solver_reset(solv);
1192       return 1;
1193     }
1194
1195   /* finish proof */
1196   if (record_proof)
1197     {
1198       queue_push(&solv->learnt_pool, 0);
1199       solv->problems.elements[oldproblemcount] = oldlearntpoolcount;
1200     }
1201
1202   /* + 2: index + trailing zero */
1203   if (disablerules && oldproblemcount + 2 < solv->problems.count)
1204     {
1205       for (i = oldproblemcount + 1; i < solv->problems.count - 1; i++)
1206         solver_disableproblem(solv, solv->problems.elements[i]);
1207       /* XXX: might want to enable all weak rules again */
1208       solver_reset(solv);
1209       return 1;
1210     }
1211   POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "UNSOLVABLE\n");
1212   return 0;
1213 }
1214
1215
1216 /********************************************************************/
1217 /* Decision revert */
1218
1219 /*-------------------------------------------------------------------
1220  *
1221  * revert
1222  * revert decisionq to a level
1223  */
1224
1225 static void
1226 revert(Solver *solv, int level)
1227 {
1228   Pool *pool = solv->pool;
1229   Id v, vv;
1230   while (solv->decisionq.count)
1231     {
1232       v = solv->decisionq.elements[solv->decisionq.count - 1];
1233       vv = v > 0 ? v : -v;
1234       if (solv->decisionmap[vv] <= level && solv->decisionmap[vv] >= -level)
1235         break;
1236       POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "reverting decision %d at %d\n", v, solv->decisionmap[vv]);
1237       solv->decisionmap[vv] = 0;
1238       solv->decisionq.count--;
1239       solv->decisionq_why.count--;
1240       solv->propagate_index = solv->decisionq.count;
1241     }
1242   while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] <= -level)
1243     {
1244       solv->branches.count--;
1245       while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] >= 0)
1246         solv->branches.count--;
1247     }
1248   solv->recommends_index = -1;
1249 }
1250
1251
1252 /*-------------------------------------------------------------------
1253  *
1254  * watch2onhighest - put watch2 on literal with highest level
1255  */
1256
1257 static inline void
1258 watch2onhighest(Solver *solv, Rule *r)
1259 {
1260   int l, wl = 0;
1261   Id d, v, *dp;
1262
1263   d = r->d < 0 ? -r->d - 1 : r->d;
1264   if (!d)
1265     return;     /* binary rule, both watches are set */
1266   dp = solv->pool->whatprovidesdata + d;
1267   while ((v = *dp++) != 0)
1268     {
1269       l = solv->decisionmap[v < 0 ? -v : v];
1270       if (l < 0)
1271         l = -l;
1272       if (l > wl)
1273         {
1274           r->w2 = dp[-1];
1275           wl = l;
1276         }
1277     }
1278 }
1279
1280
1281 /*-------------------------------------------------------------------
1282  *
1283  * setpropagatelearn
1284  *
1285  * add free decision (solvable to install) to decisionq
1286  * increase level and propagate decision
1287  * return if no conflict.
1288  *
1289  * in conflict case, analyze conflict rule, add resulting
1290  * rule to learnt rule set, make decision from learnt
1291  * rule (always unit) and re-propagate.
1292  *
1293  * returns the new solver level or 0 if unsolvable
1294  *
1295  */
1296
1297 static int
1298 setpropagatelearn(Solver *solv, int level, Id decision, int disablerules, Id ruleid)
1299 {
1300   Pool *pool = solv->pool;
1301   Rule *r;
1302   Id p = 0, d = 0;
1303   int l, why;
1304
1305   assert(ruleid >= 0);
1306   if (decision)
1307     {
1308       level++;
1309       if (decision > 0)
1310         solv->decisionmap[decision] = level;
1311       else
1312         solv->decisionmap[-decision] = -level;
1313       queue_push(&solv->decisionq, decision);
1314       queue_push(&solv->decisionq_why, -ruleid);        /* <= 0 -> free decision */
1315     }
1316   for (;;)
1317     {
1318       r = propagate(solv, level);
1319       if (!r)
1320         break;
1321       if (level == 1)
1322         return analyze_unsolvable(solv, r, disablerules);
1323       POOL_DEBUG(SOLV_DEBUG_ANALYZE, "conflict with rule #%d\n", (int)(r - solv->rules));
1324       l = analyze(solv, level, r, &p, &d, &why);        /* learnt rule in p and d */
1325       assert(l > 0 && l < level);
1326       POOL_DEBUG(SOLV_DEBUG_ANALYZE, "reverting decisions (level %d -> %d)\n", level, l);
1327       level = l;
1328       revert(solv, level);
1329       r = solver_addrule(solv, p, d);
1330       assert(r);
1331       assert(solv->learnt_why.count == (r - solv->rules) - solv->learntrules);
1332       queue_push(&solv->learnt_why, why);
1333       if (d)
1334         {
1335           /* at least 2 literals, needs watches */
1336           watch2onhighest(solv, r);
1337           addwatches_rule(solv, r);
1338         }
1339       else
1340         {
1341           /* learnt rule is an assertion */
1342           queue_push(&solv->ruleassertions, r - solv->rules);
1343         }
1344       /* the new rule is unit by design */
1345       solv->decisionmap[p > 0 ? p : -p] = p > 0 ? level : -level;
1346       queue_push(&solv->decisionq, p);
1347       queue_push(&solv->decisionq_why, r - solv->rules);
1348       IF_POOLDEBUG (SOLV_DEBUG_ANALYZE)
1349         {
1350           POOL_DEBUG(SOLV_DEBUG_ANALYZE, "decision: ");
1351           solver_printruleelement(solv, SOLV_DEBUG_ANALYZE, 0, p);
1352           POOL_DEBUG(SOLV_DEBUG_ANALYZE, "new rule: ");
1353           solver_printrule(solv, SOLV_DEBUG_ANALYZE, r);
1354         }
1355     }
1356   return level;
1357 }
1358
1359
1360 /*-------------------------------------------------------------------
1361  *
1362  * select and install
1363  *
1364  * install best package from the queue. We add an extra package, inst, if
1365  * provided. See comment in weak install section.
1366  *
1367  * returns the new solver level or 0 if unsolvable
1368  *
1369  */
1370
1371 static int
1372 selectandinstall(Solver *solv, int level, Queue *dq, int disablerules, Id ruleid)
1373 {
1374   Pool *pool = solv->pool;
1375   Id p;
1376   int i;
1377
1378   if (dq->count > 1)
1379     policy_filter_unwanted(solv, dq, POLICY_MODE_CHOOSE);
1380   if (dq->count > 1)
1381     {
1382       /* XXX: didn't we already do that? */
1383       /* XXX: shouldn't we prefer installed packages? */
1384       /* XXX: move to policy.c? */
1385       /* choose the supplemented one */
1386       for (i = 0; i < dq->count; i++)
1387         if (solver_is_supplementing(solv, pool->solvables + dq->elements[i]))
1388           {
1389             dq->elements[0] = dq->elements[i];
1390             dq->count = 1;
1391             break;
1392           }
1393     }
1394   if (dq->count > 1)
1395     {
1396       /* multiple candidates, open a branch */
1397       for (i = 1; i < dq->count; i++)
1398         queue_push(&solv->branches, dq->elements[i]);
1399       queue_push(&solv->branches, -level);
1400     }
1401   p = dq->elements[0];
1402
1403   POOL_DEBUG(SOLV_DEBUG_POLICY, "installing %s\n", pool_solvid2str(pool, p));
1404
1405   return setpropagatelearn(solv, level, p, disablerules, ruleid);
1406 }
1407
1408
1409 /********************************************************************/
1410 /* Main solver interface */
1411
1412
1413 /*-------------------------------------------------------------------
1414  *
1415  * solver_create
1416  * create solver structure
1417  *
1418  * pool: all available solvables
1419  * installed: installed Solvables
1420  *
1421  *
1422  * Upon solving, rules are created to flag the Solvables
1423  * of the 'installed' Repo as installed.
1424  */
1425
1426 Solver *
1427 solver_create(Pool *pool)
1428 {
1429   Solver *solv;
1430   solv = (Solver *)solv_calloc(1, sizeof(Solver));
1431   solv->pool = pool;
1432   solv->installed = pool->installed;
1433
1434   solv->allownamechange = 1;
1435
1436   solv->dup_allowdowngrade = 1;
1437   solv->dup_allownamechange = 1;
1438   solv->dup_allowarchchange = 1;
1439   solv->dup_allowvendorchange = 1;
1440
1441   solv->keepexplicitobsoletes = pool->noobsoletesmultiversion ? 0 : 1;
1442
1443   queue_init(&solv->ruletojob);
1444   queue_init(&solv->decisionq);
1445   queue_init(&solv->decisionq_why);
1446   queue_init(&solv->problems);
1447   queue_init(&solv->orphaned);
1448   queue_init(&solv->learnt_why);
1449   queue_init(&solv->learnt_pool);
1450   queue_init(&solv->branches);
1451   queue_init(&solv->weakruleq);
1452   queue_init(&solv->ruleassertions);
1453   queue_init(&solv->addedmap_deduceq);
1454
1455   queue_push(&solv->learnt_pool, 0);    /* so that 0 does not describe a proof */
1456
1457   map_init(&solv->recommendsmap, pool->nsolvables);
1458   map_init(&solv->suggestsmap, pool->nsolvables);
1459   map_init(&solv->noupdate, solv->installed ? solv->installed->end - solv->installed->start : 0);
1460   solv->recommends_index = 0;
1461
1462   solv->decisionmap = (Id *)solv_calloc(pool->nsolvables, sizeof(Id));
1463   solv->nrules = 1;
1464   solv->rules = solv_extend_resize(solv->rules, solv->nrules, sizeof(Rule), RULES_BLOCK);
1465   memset(solv->rules, 0, sizeof(Rule));
1466
1467   return solv;
1468 }
1469
1470
1471 /*-------------------------------------------------------------------
1472  *
1473  * solver_free
1474  */
1475
1476 void
1477 solver_free(Solver *solv)
1478 {
1479   queue_free(&solv->job);
1480   queue_free(&solv->ruletojob);
1481   queue_free(&solv->decisionq);
1482   queue_free(&solv->decisionq_why);
1483   queue_free(&solv->learnt_why);
1484   queue_free(&solv->learnt_pool);
1485   queue_free(&solv->problems);
1486   queue_free(&solv->solutions);
1487   queue_free(&solv->orphaned);
1488   queue_free(&solv->branches);
1489   queue_free(&solv->weakruleq);
1490   queue_free(&solv->ruleassertions);
1491   queue_free(&solv->addedmap_deduceq);
1492   if (solv->cleandeps_updatepkgs)
1493     {
1494       queue_free(solv->cleandeps_updatepkgs);
1495       solv->cleandeps_updatepkgs = solv_free(solv->cleandeps_updatepkgs);
1496     }
1497   if (solv->cleandeps_mistakes)
1498     {
1499       queue_free(solv->cleandeps_mistakes);
1500       solv->cleandeps_mistakes = solv_free(solv->cleandeps_mistakes);
1501     }
1502   if (solv->update_targets)
1503     {
1504       queue_free(solv->update_targets);
1505       solv->update_targets = solv_free(solv->update_targets);
1506     }
1507   if (solv->installsuppdepq)
1508     {
1509       queue_free(solv->installsuppdepq);
1510       solv->installsuppdepq = solv_free(solv->installsuppdepq);
1511     }
1512
1513   map_free(&solv->recommendsmap);
1514   map_free(&solv->suggestsmap);
1515   map_free(&solv->noupdate);
1516   map_free(&solv->weakrulemap);
1517   map_free(&solv->multiversion);
1518
1519   map_free(&solv->updatemap);
1520   map_free(&solv->bestupdatemap);
1521   map_free(&solv->fixmap);
1522   map_free(&solv->dupmap);
1523   map_free(&solv->dupinvolvedmap);
1524   map_free(&solv->droporphanedmap);
1525   map_free(&solv->cleandepsmap);
1526
1527   solv_free(solv->decisionmap);
1528   solv_free(solv->rules);
1529   solv_free(solv->watches);
1530   solv_free(solv->obsoletes);
1531   solv_free(solv->obsoletes_data);
1532   solv_free(solv->multiversionupdaters);
1533   solv_free(solv->choicerules_ref);
1534   solv_free(solv->bestrules_pkg);
1535   solv_free(solv);
1536 }
1537
1538 int
1539 solver_get_flag(Solver *solv, int flag)
1540 {
1541   switch (flag)
1542   {
1543   case SOLVER_FLAG_ALLOW_DOWNGRADE:
1544     return solv->allowdowngrade;
1545   case SOLVER_FLAG_ALLOW_NAMECHANGE:
1546     return solv->allownamechange;
1547   case SOLVER_FLAG_ALLOW_ARCHCHANGE:
1548     return solv->allowarchchange;
1549   case SOLVER_FLAG_ALLOW_VENDORCHANGE:
1550     return solv->allowvendorchange;
1551   case SOLVER_FLAG_ALLOW_UNINSTALL:
1552     return solv->allowuninstall;
1553   case SOLVER_FLAG_NO_UPDATEPROVIDE:
1554     return solv->noupdateprovide;
1555   case SOLVER_FLAG_SPLITPROVIDES:
1556     return solv->dosplitprovides;
1557   case SOLVER_FLAG_IGNORE_RECOMMENDED:
1558     return solv->dontinstallrecommended;
1559   case SOLVER_FLAG_ADD_ALREADY_RECOMMENDED:
1560     return solv->addalreadyrecommended;
1561   case SOLVER_FLAG_NO_INFARCHCHECK:
1562     return solv->noinfarchcheck;
1563   case SOLVER_FLAG_KEEP_EXPLICIT_OBSOLETES:
1564     return solv->keepexplicitobsoletes;
1565   case SOLVER_FLAG_BEST_OBEY_POLICY:
1566     return solv->bestobeypolicy;
1567   case SOLVER_FLAG_NO_AUTOTARGET:
1568     return solv->noautotarget;
1569   default:
1570     break;
1571   }
1572   return -1;
1573 }
1574
1575 int
1576 solver_set_flag(Solver *solv, int flag, int value)
1577 {
1578   int old = solver_get_flag(solv, flag);
1579   switch (flag)
1580   {
1581   case SOLVER_FLAG_ALLOW_DOWNGRADE:
1582     solv->allowdowngrade = value;
1583     break;
1584   case SOLVER_FLAG_ALLOW_NAMECHANGE:
1585     solv->allownamechange = value;
1586     break;
1587   case SOLVER_FLAG_ALLOW_ARCHCHANGE:
1588     solv->allowarchchange = value;
1589     break;
1590   case SOLVER_FLAG_ALLOW_VENDORCHANGE:
1591     solv->allowvendorchange = value;
1592     break;
1593   case SOLVER_FLAG_ALLOW_UNINSTALL:
1594     solv->allowuninstall = value;
1595     break;
1596   case SOLVER_FLAG_NO_UPDATEPROVIDE:
1597     solv->noupdateprovide = value;
1598     break;
1599   case SOLVER_FLAG_SPLITPROVIDES:
1600     solv->dosplitprovides = value;
1601     break;
1602   case SOLVER_FLAG_IGNORE_RECOMMENDED:
1603     solv->dontinstallrecommended = value;
1604     break;
1605   case SOLVER_FLAG_ADD_ALREADY_RECOMMENDED:
1606     solv->addalreadyrecommended = value;
1607     break;
1608   case SOLVER_FLAG_NO_INFARCHCHECK:
1609     solv->noinfarchcheck = value;
1610     break;
1611   case SOLVER_FLAG_KEEP_EXPLICIT_OBSOLETES:
1612     solv->keepexplicitobsoletes = value;
1613     break;
1614   case SOLVER_FLAG_BEST_OBEY_POLICY:
1615     solv->bestobeypolicy = value;
1616     break;
1617   case SOLVER_FLAG_NO_AUTOTARGET:
1618     solv->noautotarget = value;
1619     break;
1620   default:
1621     break;
1622   }
1623   return old;
1624 }
1625
1626 int
1627 cleandeps_check_mistakes(Solver *solv, int level)
1628 {
1629   Pool *pool = solv->pool;
1630   Rule *r;
1631   Id p, pp;
1632   int i;
1633   int mademistake = 0;
1634
1635   if (!solv->cleandepsmap.size)
1636     return 0;
1637   /* check for mistakes */
1638   for (i = solv->installed->start; i < solv->installed->end; i++)
1639     {
1640       if (!MAPTST(&solv->cleandepsmap, i - solv->installed->start))
1641         continue;
1642       r = solv->rules + solv->featurerules + (i - solv->installed->start);
1643       /* a mistake is when the featurerule is true but the updaterule is false */
1644       if (!r->p)
1645         continue;
1646       FOR_RULELITERALS(p, pp, r)
1647         if (p > 0 && solv->decisionmap[p] > 0)
1648           break;
1649       if (!p)
1650         continue;       /* feature rule is not true */
1651       r = solv->rules + solv->updaterules + (i - solv->installed->start);
1652       if (!r->p)
1653         continue;
1654       FOR_RULELITERALS(p, pp, r)
1655         if (p > 0 && solv->decisionmap[p] > 0)
1656           break;
1657       if (p)
1658         continue;       /* update rule is true */
1659       POOL_DEBUG(SOLV_DEBUG_SOLVER, "cleandeps mistake: ");
1660       solver_printruleclass(solv, SOLV_DEBUG_SOLVER, r);
1661       POOL_DEBUG(SOLV_DEBUG_SOLVER, "feature rule: ");
1662       solver_printruleclass(solv, SOLV_DEBUG_SOLVER, solv->rules + solv->featurerules + (i - solv->installed->start));
1663       if (!solv->cleandeps_mistakes)
1664         {
1665           solv->cleandeps_mistakes = solv_calloc(1, sizeof(Queue));
1666           queue_init(solv->cleandeps_mistakes);
1667         }
1668       queue_push(solv->cleandeps_mistakes, i);
1669       MAPCLR(&solv->cleandepsmap, i - solv->installed->start);
1670       solver_reenablepolicyrules_cleandeps(solv, i);
1671       mademistake = 1;
1672     }
1673   if (mademistake)
1674     solver_reset(solv);
1675   return mademistake;
1676 }
1677
1678 static void
1679 prune_to_update_targets(Solver *solv, Id *cp, Queue *q)
1680 {
1681   int i, j;
1682   Id p, *cp2;
1683   for (i = j = 0; i < q->count; i++)
1684     {
1685       p = q->elements[i];
1686       for (cp2 = cp; *cp2; cp2++)
1687         if (*cp2 == p)
1688           {
1689             q->elements[j++] = p;
1690             break;
1691           }
1692     }
1693   queue_truncate(q, j);
1694 }
1695
1696 /*-------------------------------------------------------------------
1697  *
1698  * solver_run_sat
1699  *
1700  * all rules have been set up, now actually run the solver
1701  *
1702  */
1703
1704 void
1705 solver_run_sat(Solver *solv, int disablerules, int doweak)
1706 {
1707   Queue dq;             /* local decisionqueue */
1708   Queue dqs;            /* local decisionqueue for supplements */
1709   int systemlevel;
1710   int level, olevel;
1711   Rule *r;
1712   int i, j, n;
1713   Solvable *s;
1714   Pool *pool = solv->pool;
1715   Id p, pp, *dp;
1716   int minimizationsteps;
1717   int installedpos = solv->installed ? solv->installed->start : 0;
1718
1719   IF_POOLDEBUG (SOLV_DEBUG_RULE_CREATION)
1720     {
1721       POOL_DEBUG (SOLV_DEBUG_RULE_CREATION, "number of rules: %d\n", solv->nrules);
1722       for (i = 1; i < solv->nrules; i++)
1723         solver_printruleclass(solv, SOLV_DEBUG_RULE_CREATION, solv->rules + i);
1724     }
1725
1726   POOL_DEBUG(SOLV_DEBUG_SOLVER, "initial decisions: %d\n", solv->decisionq.count);
1727
1728   /* start SAT algorithm */
1729   level = 1;
1730   systemlevel = level + 1;
1731   POOL_DEBUG(SOLV_DEBUG_SOLVER, "solving...\n");
1732
1733   queue_init(&dq);
1734   queue_init(&dqs);
1735
1736   /*
1737    * here's the main loop:
1738    * 1) propagate new decisions (only needed once)
1739    * 2) fulfill jobs
1740    * 3) try to keep installed packages
1741    * 4) fulfill all unresolved rules
1742    * 5) install recommended packages
1743    * 6) minimalize solution if we had choices
1744    * if we encounter a problem, we rewind to a safe level and restart
1745    * with step 1
1746    */
1747
1748   minimizationsteps = 0;
1749   for (;;)
1750     {
1751       /*
1752        * initial propagation of the assertions
1753        */
1754       if (level == 1)
1755         {
1756           POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "propagating (propagate_index: %d;  size decisionq: %d)...\n", solv->propagate_index, solv->decisionq.count);
1757           if ((r = propagate(solv, level)) != 0)
1758             {
1759               if (analyze_unsolvable(solv, r, disablerules))
1760                 continue;
1761               level = 0;
1762               break;    /* unsolvable */
1763             }
1764         }
1765
1766       /*
1767        * resolve jobs first
1768        */
1769      if (level < systemlevel)
1770         {
1771           POOL_DEBUG(SOLV_DEBUG_SOLVER, "resolving job rules\n");
1772           for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++)
1773             {
1774               Id l;
1775               if (r->d < 0)             /* ignore disabled rules */
1776                 continue;
1777               queue_empty(&dq);
1778               FOR_RULELITERALS(l, pp, r)
1779                 {
1780                   if (l < 0)
1781                     {
1782                       if (solv->decisionmap[-l] <= 0)
1783                         break;
1784                     }
1785                   else
1786                     {
1787                       if (solv->decisionmap[l] > 0)
1788                         break;
1789                       if (solv->decisionmap[l] == 0)
1790                         queue_push(&dq, l);
1791                     }
1792                 }
1793               if (l || !dq.count)
1794                 continue;
1795               /* prune to installed if not updating */
1796               if (dq.count > 1 && solv->installed && !solv->updatemap_all &&
1797                   !(solv->job.elements[solv->ruletojob.elements[i - solv->jobrules]] & SOLVER_ORUPDATE))
1798                 {
1799                   int j, k;
1800                   for (j = k = 0; j < dq.count; j++)
1801                     {
1802                       Solvable *s = pool->solvables + dq.elements[j];
1803                       if (s->repo == solv->installed)
1804                         {
1805                           dq.elements[k++] = dq.elements[j];
1806                           if (solv->updatemap.size && MAPTST(&solv->updatemap, dq.elements[j] - solv->installed->start))
1807                             {
1808                               k = 0;    /* package wants to be updated, do not prune */
1809                               break;
1810                             }
1811                         }
1812                     }
1813                   if (k)
1814                     dq.count = k;
1815                 }
1816               olevel = level;
1817               level = selectandinstall(solv, level, &dq, disablerules, i);
1818               if (level == 0)
1819                 break;
1820               if (level <= olevel)
1821                 break;
1822             }
1823           if (level == 0)
1824             break;      /* unsolvable */
1825           systemlevel = level + 1;
1826           if (i < solv->jobrules_end)
1827             continue;
1828           solv->decisioncnt_update = solv->decisionq.count;
1829           solv->decisioncnt_keep = solv->decisionq.count;
1830         }
1831
1832       /*
1833        * installed packages
1834        */
1835       if (level < systemlevel && solv->installed && solv->installed->nsolvables && !solv->installed->disabled)
1836         {
1837           Repo *installed = solv->installed;
1838           int pass;
1839
1840           POOL_DEBUG(SOLV_DEBUG_SOLVER, "resolving installed packages\n");
1841           /* we use two passes if we need to update packages
1842            * to create a better user experience */
1843           for (pass = solv->updatemap.size ? 0 : 1; pass < 2; pass++)
1844             {
1845               int passlevel = level;
1846               Id *multiversionupdaters = solv->multiversion.size ? solv->multiversionupdaters : 0;
1847               if (pass == 1)
1848                 solv->decisioncnt_keep = solv->decisionq.count;
1849               /* start with installedpos, the position that gave us problems the last time */
1850               for (i = installedpos, n = installed->start; n < installed->end; i++, n++)
1851                 {
1852                   Rule *rr;
1853                   Id d;
1854
1855                   if (i == installed->end)
1856                     i = installed->start;
1857                   s = pool->solvables + i;
1858                   if (s->repo != installed)
1859                     continue;
1860
1861                   if (solv->decisionmap[i] > 0 && (!multiversionupdaters || !multiversionupdaters[i - installed->start]))
1862                     continue;           /* already decided */
1863                   if (!pass && solv->updatemap.size && !MAPTST(&solv->updatemap, i - installed->start))
1864                     continue;           /* updates first */
1865                   r = solv->rules + solv->updaterules + (i - installed->start);
1866                   rr = r;
1867                   if (!rr->p || rr->d < 0)      /* disabled -> look at feature rule */
1868                     rr -= solv->installed->end - solv->installed->start;
1869                   if (!rr->p)           /* identical to update rule? */
1870                     rr = r;
1871                   if (!rr->p)
1872                     continue;           /* orpaned package */
1873
1874                   /* check if we should update this package to the latest version
1875                    * noupdate is set for erase jobs, in that case we want to deinstall
1876                    * the installed package and not replace it with a newer version */
1877                   queue_empty(&dq);
1878                   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 != i))
1879                     {
1880                       if (multiversionupdaters && (d = multiversionupdaters[i - installed->start]) != 0)
1881                         {
1882                           /* special multiversion handling, make sure best version is chosen */
1883                           if (rr->p == i && solv->decisionmap[i] >= 0)
1884                             queue_push(&dq, i);
1885                           while ((p = pool->whatprovidesdata[d++]) != 0)
1886                             if (solv->decisionmap[p] >= 0)
1887                               queue_push(&dq, p);
1888                           if (dq.count && solv->update_targets && solv->update_targets->elements[i - installed->start])
1889                             prune_to_update_targets(solv, solv->update_targets->elements + solv->update_targets->elements[i - installed->start], &dq);
1890                           if (dq.count)
1891                             {
1892                               policy_filter_unwanted(solv, &dq, POLICY_MODE_CHOOSE);
1893                               p = dq.elements[0];
1894                               if (p != i && solv->decisionmap[p] == 0)
1895                                 {
1896                                   rr = solv->rules + solv->featurerules + (i - solv->installed->start);
1897                                   if (!rr->p)           /* update rule == feature rule? */
1898                                     rr = rr - solv->featurerules + solv->updaterules;
1899                                   dq.count = 1;
1900                                 }
1901                               else
1902                                 dq.count = 0;
1903                             }
1904                         }
1905                       else
1906                         {
1907                           /* update to best package of the update rule */
1908                           FOR_RULELITERALS(p, pp, rr)
1909                             {
1910                               if (solv->decisionmap[p] > 0)
1911                                 {
1912                                   dq.count = 0;         /* already fulfilled */
1913                                   break;
1914                                 }
1915                               if (!solv->decisionmap[p])
1916                                 queue_push(&dq, p);
1917                             }
1918                         }
1919                     }
1920                   if (dq.count && solv->update_targets && solv->update_targets->elements[i - installed->start])
1921                     prune_to_update_targets(solv, solv->update_targets->elements + solv->update_targets->elements[i - installed->start], &dq);
1922                   /* install best version */
1923                   if (dq.count)
1924                     {
1925                       olevel = level;
1926                       level = selectandinstall(solv, level, &dq, disablerules, rr - solv->rules);
1927                       if (level == 0)
1928                         {
1929                           queue_free(&dq);
1930                           queue_free(&dqs);
1931                           return;
1932                         }
1933                       if (level <= olevel)
1934                         {
1935                           if (level == 1 || level < passlevel)
1936                             break;      /* trouble */
1937                           if (level < olevel)
1938                             n = installed->start;       /* redo all */
1939                           i--;
1940                           n--;
1941                           continue;
1942                         }
1943                     }
1944                   /* if still undecided keep package */
1945                   if (solv->decisionmap[i] == 0)
1946                     {
1947                       olevel = level;
1948                       if (solv->cleandepsmap.size && MAPTST(&solv->cleandepsmap, i - installed->start))
1949                         {
1950 #if 0
1951                           POOL_DEBUG(SOLV_DEBUG_POLICY, "cleandeps erasing %s\n", pool_solvid2str(pool, i));
1952                           level = setpropagatelearn(solv, level, -i, disablerules, 0);
1953 #else
1954                           continue;
1955 #endif
1956                         }
1957                       else
1958                         {
1959                           POOL_DEBUG(SOLV_DEBUG_POLICY, "keeping %s\n", pool_solvid2str(pool, i));
1960                           level = setpropagatelearn(solv, level, i, disablerules, r - solv->rules);
1961                         }
1962                       if (level == 0)
1963                         break;
1964                       if (level <= olevel)
1965                         {
1966                           if (level == 1 || level < passlevel)
1967                             break;      /* trouble */
1968                           if (level < olevel)
1969                             n = installed->start;       /* redo all */
1970                           i--;
1971                           n--;
1972                           continue;     /* retry with learnt rule */
1973                         }
1974                     }
1975                 }
1976               if (n < installed->end)
1977                 {
1978                   installedpos = i;     /* retry problem solvable next time */
1979                   break;                /* ran into trouble */
1980                 }
1981               installedpos = installed->start;  /* reset installedpos */
1982             }
1983           if (level == 0)
1984             break;              /* unsolvable */
1985           systemlevel = level + 1;
1986           if (pass < 2)
1987             continue;           /* had trouble, retry */
1988         }
1989
1990       if (level < systemlevel)
1991         systemlevel = level;
1992
1993       /*
1994        * decide
1995        */
1996       solv->decisioncnt_resolve = solv->decisionq.count;
1997       POOL_DEBUG(SOLV_DEBUG_POLICY, "deciding unresolved rules\n");
1998       for (i = 1, n = 1; n < solv->nrules; i++, n++)
1999         {
2000           if (i == solv->nrules)
2001             i = 1;
2002           r = solv->rules + i;
2003           if (r->d < 0)         /* ignore disabled rules */
2004             continue;
2005           queue_empty(&dq);
2006           if (r->d == 0)
2007             {
2008               /* binary or unary rule */
2009               /* need two positive undecided literals */
2010               if (r->p < 0 || r->w2 <= 0)
2011                 continue;
2012               if (solv->decisionmap[r->p] || solv->decisionmap[r->w2])
2013                 continue;
2014               queue_push(&dq, r->p);
2015               queue_push(&dq, r->w2);
2016             }
2017           else
2018             {
2019               /* make sure that
2020                * all negative literals are installed
2021                * no positive literal is installed
2022                * i.e. the rule is not fulfilled and we
2023                * just need to decide on the positive literals
2024                */
2025               if (r->p < 0)
2026                 {
2027                   if (solv->decisionmap[-r->p] <= 0)
2028                     continue;
2029                 }
2030               else
2031                 {
2032                   if (solv->decisionmap[r->p] > 0)
2033                     continue;
2034                   if (solv->decisionmap[r->p] == 0)
2035                     queue_push(&dq, r->p);
2036                 }
2037               dp = pool->whatprovidesdata + r->d;
2038               while ((p = *dp++) != 0)
2039                 {
2040                   if (p < 0)
2041                     {
2042                       if (solv->decisionmap[-p] <= 0)
2043                         break;
2044                     }
2045                   else
2046                     {
2047                       if (solv->decisionmap[p] > 0)
2048                         break;
2049                       if (solv->decisionmap[p] == 0)
2050                         queue_push(&dq, p);
2051                     }
2052                 }
2053               if (p)
2054                 continue;
2055             }
2056           IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
2057             {
2058               POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "unfulfilled ");
2059               solver_printruleclass(solv, SOLV_DEBUG_PROPAGATE, r);
2060             }
2061           /* dq.count < 2 cannot happen as this means that
2062            * the rule is unit */
2063           assert(dq.count > 1);
2064
2065           /* prune to cleandeps packages */
2066           if (solv->cleandepsmap.size && solv->installed)
2067             {
2068               Repo *installed = solv->installed;
2069               for (j = 0; j < dq.count; j++)
2070                 if (pool->solvables[dq.elements[j]].repo == installed && MAPTST(&solv->cleandepsmap, dq.elements[j] - installed->start))
2071                   break;
2072               if (j < dq.count)
2073                 {
2074                   dq.elements[0] = dq.elements[j];
2075                   queue_truncate(&dq, 1);
2076                 }
2077             }
2078
2079           olevel = level;
2080           level = selectandinstall(solv, level, &dq, disablerules, r - solv->rules);
2081           if (level == 0)
2082             break;              /* unsolvable */
2083           if (level < systemlevel || level == 1)
2084             break;              /* trouble */
2085           /* something changed, so look at all rules again */
2086           n = 0;
2087         }
2088
2089       if (n != solv->nrules)    /* ran into trouble? */
2090         {
2091           if (level == 0)
2092             break;              /* unsolvable */
2093           continue;             /* start over */
2094         }
2095
2096       /* at this point we have a consistent system. now do the extras... */
2097
2098       /* first decide leftover cleandeps packages */
2099       if (solv->cleandepsmap.size && solv->installed)
2100         {
2101           for (p = solv->installed->start; p < solv->installed->end; p++)
2102             {
2103               s = pool->solvables + p;
2104               if (s->repo != solv->installed)
2105                 continue;
2106               if (solv->decisionmap[p] == 0 && MAPTST(&solv->cleandepsmap, p - solv->installed->start))
2107                 {
2108                   POOL_DEBUG(SOLV_DEBUG_POLICY, "cleandeps erasing %s\n", pool_solvid2str(pool, p));
2109                   olevel = level;
2110                   level = setpropagatelearn(solv, level, -p, 0, 0);
2111                   if (level < olevel)
2112                     break;
2113                 }
2114             }
2115           if (p < solv->installed->end)
2116             continue;
2117         }
2118
2119       solv->decisioncnt_weak = solv->decisionq.count;
2120       if (doweak)
2121         {
2122           int qcount;
2123
2124           POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended packages\n");
2125           queue_empty(&dq);     /* recommended packages */
2126           queue_empty(&dqs);    /* supplemented packages */
2127           for (i = 1; i < pool->nsolvables; i++)
2128             {
2129               if (solv->decisionmap[i] < 0)
2130                 continue;
2131               if (solv->decisionmap[i] > 0)
2132                 {
2133                   /* installed, check for recommends */
2134                   Id *recp, rec, pp, p;
2135                   s = pool->solvables + i;
2136                   if (!solv->addalreadyrecommended && s->repo == solv->installed)
2137                     continue;
2138                   /* XXX need to special case AND ? */
2139                   if (s->recommends)
2140                     {
2141                       recp = s->repo->idarraydata + s->recommends;
2142                       while ((rec = *recp++) != 0)
2143                         {
2144                           qcount = dq.count;
2145                           FOR_PROVIDES(p, pp, rec)
2146                             {
2147                               if (solv->decisionmap[p] > 0)
2148                                 {
2149                                   dq.count = qcount;
2150                                   break;
2151                                 }
2152                               else if (solv->decisionmap[p] == 0)
2153                                 {
2154                                   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))))
2155                                     continue;
2156                                   queue_pushunique(&dq, p);
2157                                 }
2158                             }
2159                         }
2160                     }
2161                 }
2162               else
2163                 {
2164                   s = pool->solvables + i;
2165                   if (!s->supplements)
2166                     continue;
2167                   if (!pool_installable(pool, s))
2168                     continue;
2169                   if (!solver_is_supplementing(solv, s))
2170                     continue;
2171                   if (solv->dupmap_all && solv->installed && s->repo == solv->installed && (solv->droporphanedmap_all || (solv->droporphanedmap.size && MAPTST(&solv->droporphanedmap, i - solv->installed->start))))
2172                     continue;
2173                   queue_push(&dqs, i);
2174                 }
2175             }
2176
2177           /* filter out all packages obsoleted by installed packages */
2178           /* this is no longer needed if we have reverse obsoletes */
2179           if ((dqs.count || dq.count) && solv->installed)
2180             {
2181               Map obsmap;
2182               Id obs, *obsp, po, ppo;
2183
2184               map_init(&obsmap, pool->nsolvables);
2185               for (p = solv->installed->start; p < solv->installed->end; p++)
2186                 {
2187                   s = pool->solvables + p;
2188                   if (s->repo != solv->installed || !s->obsoletes)
2189                     continue;
2190                   if (solv->decisionmap[p] <= 0)
2191                     continue;
2192                   if (solv->multiversion.size && MAPTST(&solv->multiversion, p))
2193                     continue;
2194                   obsp = s->repo->idarraydata + s->obsoletes;
2195                   /* foreach obsoletes */
2196                   while ((obs = *obsp++) != 0)
2197                     FOR_PROVIDES(po, ppo, obs)
2198                       MAPSET(&obsmap, po);
2199                 }
2200               for (i = j = 0; i < dqs.count; i++)
2201                 if (!MAPTST(&obsmap, dqs.elements[i]))
2202                   dqs.elements[j++] = dqs.elements[i];
2203               dqs.count = j;
2204               for (i = j = 0; i < dq.count; i++)
2205                 if (!MAPTST(&obsmap, dq.elements[i]))
2206                   dq.elements[j++] = dq.elements[i];
2207               dq.count = j;
2208               map_free(&obsmap);
2209             }
2210
2211           /* filter out all already supplemented packages if requested */
2212           if (!solv->addalreadyrecommended && dqs.count)
2213             {
2214               int dosplitprovides_old = solv->dosplitprovides;
2215               /* turn off all new packages */
2216               for (i = 0; i < solv->decisionq.count; i++)
2217                 {
2218                   p = solv->decisionq.elements[i];
2219                   if (p < 0)
2220                     continue;
2221                   s = pool->solvables + p;
2222                   if (s->repo && s->repo != solv->installed)
2223                     solv->decisionmap[p] = -solv->decisionmap[p];
2224                 }
2225               solv->dosplitprovides = 0;
2226               /* filter out old supplements */
2227               for (i = j = 0; i < dqs.count; i++)
2228                 {
2229                   p = dqs.elements[i];
2230                   s = pool->solvables + p;
2231                   if (!s->supplements)
2232                     continue;
2233                   if (!solver_is_supplementing(solv, s))
2234                     dqs.elements[j++] = p;
2235                   else if (solv->installsuppdepq && solver_check_installsuppdepq(solv, s))
2236                     dqs.elements[j++] = p;
2237                 }
2238               dqs.count = j;
2239               /* undo turning off */
2240               for (i = 0; i < solv->decisionq.count; i++)
2241                 {
2242                   p = solv->decisionq.elements[i];
2243                   if (p < 0)
2244                     continue;
2245                   s = pool->solvables + p;
2246                   if (s->repo && s->repo != solv->installed)
2247                     solv->decisionmap[p] = -solv->decisionmap[p];
2248                 }
2249               solv->dosplitprovides = dosplitprovides_old;
2250             }
2251
2252           /* multiversion doesn't mix well with supplements.
2253            * filter supplemented packages where we already decided
2254            * to install a different version (see bnc#501088) */
2255           if (dqs.count && solv->multiversion.size)
2256             {
2257               for (i = j = 0; i < dqs.count; i++)
2258                 {
2259                   p = dqs.elements[i];
2260                   if (MAPTST(&solv->multiversion, p))
2261                     {
2262                       Id p2, pp2;
2263                       s = pool->solvables + p;
2264                       FOR_PROVIDES(p2, pp2, s->name)
2265                         if (solv->decisionmap[p2] > 0 && pool->solvables[p2].name == s->name)
2266                           break;
2267                       if (p2)
2268                         continue;       /* ignore this package */
2269                     }
2270                   dqs.elements[j++] = p;
2271                 }
2272               dqs.count = j;
2273             }
2274
2275           /* make dq contain both recommended and supplemented pkgs */
2276           if (dqs.count)
2277             {
2278               for (i = 0; i < dqs.count; i++)
2279                 queue_pushunique(&dq, dqs.elements[i]);
2280             }
2281
2282           if (dq.count)
2283             {
2284               Map dqmap;
2285               int decisioncount = solv->decisionq.count;
2286
2287               if (dq.count == 1)
2288                 {
2289                   /* simple case, just one package. no need to choose to best version */
2290                   p = dq.elements[0];
2291                   if (dqs.count)
2292                     POOL_DEBUG(SOLV_DEBUG_POLICY, "installing supplemented %s\n", pool_solvid2str(pool, p));
2293                   else
2294                     POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended %s\n", pool_solvid2str(pool, p));
2295                   level = setpropagatelearn(solv, level, p, 0, 0);
2296                   if (level == 0)
2297                     break;
2298                   continue;     /* back to main loop */
2299                 }
2300
2301               /* filter packages, this gives us the best versions */
2302               policy_filter_unwanted(solv, &dq, POLICY_MODE_RECOMMEND);
2303
2304               /* create map of result */
2305               map_init(&dqmap, pool->nsolvables);
2306               for (i = 0; i < dq.count; i++)
2307                 MAPSET(&dqmap, dq.elements[i]);
2308
2309               /* install all supplemented packages */
2310               for (i = 0; i < dqs.count; i++)
2311                 {
2312                   p = dqs.elements[i];
2313                   if (solv->decisionmap[p] || !MAPTST(&dqmap, p))
2314                     continue;
2315                   POOL_DEBUG(SOLV_DEBUG_POLICY, "installing supplemented %s\n", pool_solvid2str(pool, p));
2316                   olevel = level;
2317                   level = setpropagatelearn(solv, level, p, 0, 0);
2318                   if (level <= olevel)
2319                     break;
2320                 }
2321               if (i < dqs.count || solv->decisionq.count < decisioncount)
2322                 {
2323                   map_free(&dqmap);
2324                   if (level == 0)
2325                     break;
2326                   continue;
2327                 }
2328
2329               /* install all recommended packages */
2330               /* more work as we want to created branches if multiple
2331                * choices are valid */
2332               for (i = 0; i < decisioncount; i++)
2333                 {
2334                   Id rec, *recp, pp;
2335                   p = solv->decisionq.elements[i];
2336                   if (p < 0)
2337                     continue;
2338                   s = pool->solvables + p;
2339                   if (!s->repo || (!solv->addalreadyrecommended && s->repo == solv->installed))
2340                     continue;
2341                   if (!s->recommends)
2342                     continue;
2343                   recp = s->repo->idarraydata + s->recommends;
2344                   while ((rec = *recp++) != 0)
2345                     {
2346                       queue_empty(&dq);
2347                       FOR_PROVIDES(p, pp, rec)
2348                         {
2349                           if (solv->decisionmap[p] > 0)
2350                             {
2351                               dq.count = 0;
2352                               break;
2353                             }
2354                           else if (solv->decisionmap[p] == 0 && MAPTST(&dqmap, p))
2355                             queue_pushunique(&dq, p);
2356                         }
2357                       if (!dq.count)
2358                         continue;
2359                       if (dq.count > 1)
2360                         {
2361                           /* multiple candidates, open a branch */
2362                           for (i = 1; i < dq.count; i++)
2363                             queue_push(&solv->branches, dq.elements[i]);
2364                           queue_push(&solv->branches, -level);
2365                         }
2366                       p = dq.elements[0];
2367                       POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended %s\n", pool_solvid2str(pool, p));
2368                       olevel = level;
2369                       level = setpropagatelearn(solv, level, p, 0, 0);
2370                       if (level <= olevel || solv->decisionq.count < decisioncount)
2371                         break;  /* we had to revert some decisions */
2372                     }
2373                   if (rec)
2374                     break;      /* had a problem above, quit loop */
2375                 }
2376               map_free(&dqmap);
2377               if (level == 0)
2378                 break;
2379               continue;         /* back to main loop so that all deps are checked */
2380             }
2381         }
2382
2383       solv->decisioncnt_orphan = solv->decisionq.count;
2384       if (solv->dupmap_all && solv->installed)
2385         {
2386           int installedone = 0;
2387
2388           /* let's see if we can install some unsupported package */
2389           POOL_DEBUG(SOLV_DEBUG_SOLVER, "deciding orphaned packages\n");
2390           for (i = 0; i < solv->orphaned.count; i++)
2391             {
2392               p = solv->orphaned.elements[i];
2393               if (solv->decisionmap[p])
2394                 continue;       /* already decided */
2395               if (solv->droporphanedmap_all)
2396                 continue;
2397               if (solv->droporphanedmap.size && MAPTST(&solv->droporphanedmap, p - solv->installed->start))
2398                 continue;
2399               POOL_DEBUG(SOLV_DEBUG_SOLVER, "keeping orphaned %s\n", pool_solvid2str(pool, p));
2400               olevel = level;
2401               level = setpropagatelearn(solv, level, p, 0, 0);
2402               installedone = 1;
2403               if (level < olevel)
2404                 break;
2405             }
2406           if (installedone || i < solv->orphaned.count)
2407             {
2408               if (level == 0)
2409                 break;
2410               continue;         /* back to main loop */
2411             }
2412           for (i = 0; i < solv->orphaned.count; i++)
2413             {
2414               p = solv->orphaned.elements[i];
2415               if (solv->decisionmap[p])
2416                 continue;       /* already decided */
2417               POOL_DEBUG(SOLV_DEBUG_SOLVER, "removing orphaned %s\n", pool_solvid2str(pool, p));
2418               olevel = level;
2419               level = setpropagatelearn(solv, level, -p, 0, 0);
2420               if (level < olevel)
2421                 break;
2422             }
2423           if (i < solv->orphaned.count)
2424             {
2425               if (level == 0)
2426                 break;
2427               continue;         /* back to main loop */
2428             }
2429         }
2430
2431      if (solv->installed && solv->cleandepsmap.size)
2432         {
2433           if (cleandeps_check_mistakes(solv, level))
2434             {
2435               level = 1;        /* restart from scratch */
2436               systemlevel = level + 1;
2437               continue;
2438             }
2439         }
2440
2441      if (solv->solution_callback)
2442         {
2443           solv->solution_callback(solv, solv->solution_callback_data);
2444           if (solv->branches.count)
2445             {
2446               int i = solv->branches.count - 1;
2447               int l = -solv->branches.elements[i];
2448               Id why;
2449
2450               for (; i > 0; i--)
2451                 if (solv->branches.elements[i - 1] < 0)
2452                   break;
2453               p = solv->branches.elements[i];
2454               POOL_DEBUG(SOLV_DEBUG_SOLVER, "branching with %s\n", pool_solvid2str(pool, p));
2455               queue_empty(&dq);
2456               for (j = i + 1; j < solv->branches.count; j++)
2457                 queue_push(&dq, solv->branches.elements[j]);
2458               solv->branches.count = i;
2459               level = l;
2460               revert(solv, level);
2461               if (dq.count > 1)
2462                 for (j = 0; j < dq.count; j++)
2463                   queue_push(&solv->branches, dq.elements[j]);
2464               olevel = level;
2465               why = -solv->decisionq_why.elements[solv->decisionq_why.count];
2466               assert(why >= 0);
2467               level = setpropagatelearn(solv, level, p, disablerules, why);
2468               if (level == 0)
2469                 break;
2470               continue;
2471             }
2472           /* all branches done, we're finally finished */
2473           break;
2474         }
2475
2476       /* auto-minimization step */
2477      if (solv->branches.count)
2478         {
2479           int l = 0, lasti = -1, lastl = -1;
2480           Id why;
2481
2482           p = 0;
2483           for (i = solv->branches.count - 1; i >= 0; i--)
2484             {
2485               p = solv->branches.elements[i];
2486               if (p < 0)
2487                 l = -p;
2488               else if (p > 0 && solv->decisionmap[p] > l + 1)
2489                 {
2490                   lasti = i;
2491                   lastl = l;
2492                 }
2493             }
2494           if (lasti >= 0)
2495             {
2496               /* kill old solvable so that we do not loop */
2497               p = solv->branches.elements[lasti];
2498               solv->branches.elements[lasti] = 0;
2499               POOL_DEBUG(SOLV_DEBUG_SOLVER, "minimizing %d -> %d with %s\n", solv->decisionmap[p], lastl, pool_solvid2str(pool, p));
2500               minimizationsteps++;
2501
2502               level = lastl;
2503               revert(solv, level);
2504               why = -solv->decisionq_why.elements[solv->decisionq_why.count];
2505               assert(why >= 0);
2506               olevel = level;
2507               level = setpropagatelearn(solv, level, p, disablerules, why);
2508               if (level == 0)
2509                 break;
2510               continue;         /* back to main loop */
2511             }
2512         }
2513       /* no minimization found, we're finally finished! */
2514       break;
2515     }
2516
2517   POOL_DEBUG(SOLV_DEBUG_STATS, "solver statistics: %d learned rules, %d unsolvable, %d minimization steps\n", solv->stats_learned, solv->stats_unsolvable, minimizationsteps);
2518
2519   POOL_DEBUG(SOLV_DEBUG_STATS, "done solving.\n\n");
2520   queue_free(&dq);
2521   queue_free(&dqs);
2522   if (level == 0)
2523     {
2524       /* unsolvable */
2525       solv->decisioncnt_update = solv->decisionq.count;
2526       solv->decisioncnt_keep = solv->decisionq.count;
2527       solv->decisioncnt_resolve = solv->decisionq.count;
2528       solv->decisioncnt_weak = solv->decisionq.count;
2529       solv->decisioncnt_orphan = solv->decisionq.count;
2530     }
2531 #if 0
2532   solver_printdecisionq(solv, SOLV_DEBUG_RESULT);
2533 #endif
2534 }
2535
2536
2537 /*-------------------------------------------------------------------
2538  *
2539  * remove disabled conflicts
2540  *
2541  * purpose: update the decisionmap after some rules were disabled.
2542  * this is used to calculate the suggested/recommended package list.
2543  * Also returns a "removed" list to undo the discisionmap changes.
2544  */
2545
2546 static void
2547 removedisabledconflicts(Solver *solv, Queue *removed)
2548 {
2549   Pool *pool = solv->pool;
2550   int i, n;
2551   Id p, why, *dp;
2552   Id new;
2553   Rule *r;
2554   Id *decisionmap = solv->decisionmap;
2555
2556   queue_empty(removed);
2557   for (i = 0; i < solv->decisionq.count; i++)
2558     {
2559       p = solv->decisionq.elements[i];
2560       if (p > 0)
2561         continue;       /* conflicts only, please */
2562       why = solv->decisionq_why.elements[i];
2563       if (why == 0)
2564         {
2565           /* no rule involved, must be a orphan package drop */
2566           continue;
2567         }
2568       /* we never do conflicts on free decisions, so there
2569        * must have been an unit rule */
2570       assert(why > 0);
2571       r = solv->rules + why;
2572       if (r->d < 0 && decisionmap[-p])
2573         {
2574           /* rule is now disabled, remove from decisionmap */
2575           POOL_DEBUG(SOLV_DEBUG_SOLVER, "removing conflict for package %s[%d]\n", pool_solvid2str(pool, -p), -p);
2576           queue_push(removed, -p);
2577           queue_push(removed, decisionmap[-p]);
2578           decisionmap[-p] = 0;
2579         }
2580     }
2581   if (!removed->count)
2582     return;
2583   /* we removed some confliced packages. some of them might still
2584    * be in conflict, so search for unit rules and re-conflict */
2585   new = 0;
2586   for (i = n = 1, r = solv->rules + i; n < solv->nrules; i++, r++, n++)
2587     {
2588       if (i == solv->nrules)
2589         {
2590           i = 1;
2591           r = solv->rules + i;
2592         }
2593       if (r->d < 0)
2594         continue;
2595       if (!r->w2)
2596         {
2597           if (r->p < 0 && !decisionmap[-r->p])
2598             new = r->p;
2599         }
2600       else if (!r->d)
2601         {
2602           /* binary rule */
2603           if (r->p < 0 && decisionmap[-r->p] == 0 && DECISIONMAP_FALSE(r->w2))
2604             new = r->p;
2605           else if (r->w2 < 0 && decisionmap[-r->w2] == 0 && DECISIONMAP_FALSE(r->p))
2606             new = r->w2;
2607         }
2608       else
2609         {
2610           if (r->p < 0 && decisionmap[-r->p] == 0)
2611             new = r->p;
2612           if (new || DECISIONMAP_FALSE(r->p))
2613             {
2614               dp = pool->whatprovidesdata + r->d;
2615               while ((p = *dp++) != 0)
2616                 {
2617                   if (new && p == new)
2618                     continue;
2619                   if (p < 0 && decisionmap[-p] == 0)
2620                     {
2621                       if (new)
2622                         {
2623                           new = 0;
2624                           break;
2625                         }
2626                       new = p;
2627                     }
2628                   else if (!DECISIONMAP_FALSE(p))
2629                     {
2630                       new = 0;
2631                       break;
2632                     }
2633                 }
2634             }
2635         }
2636       if (new)
2637         {
2638           POOL_DEBUG(SOLV_DEBUG_SOLVER, "re-conflicting package %s[%d]\n", pool_solvid2str(pool, -new), -new);
2639           decisionmap[-new] = -1;
2640           new = 0;
2641           n = 0;        /* redo all rules */
2642         }
2643     }
2644 }
2645
2646 static inline void
2647 undo_removedisabledconflicts(Solver *solv, Queue *removed)
2648 {
2649   int i;
2650   for (i = 0; i < removed->count; i += 2)
2651     solv->decisionmap[removed->elements[i]] = removed->elements[i + 1];
2652 }
2653
2654
2655 /*-------------------------------------------------------------------
2656  *
2657  * weaken solvable dependencies
2658  */
2659
2660 static void
2661 weaken_solvable_deps(Solver *solv, Id p)
2662 {
2663   int i;
2664   Rule *r;
2665
2666   for (i = 1, r = solv->rules + i; i < solv->rpmrules_end; i++, r++)
2667     {
2668       if (r->p != -p)
2669         continue;
2670       if ((r->d == 0 || r->d == -1) && r->w2 < 0)
2671         continue;       /* conflict */
2672       queue_push(&solv->weakruleq, i);
2673     }
2674 }
2675
2676
2677 /********************************************************************/
2678 /* main() */
2679
2680
2681 void
2682 solver_calculate_multiversionmap(Pool *pool, Queue *job, Map *multiversionmap)
2683 {
2684   int i;
2685   Id how, what, select;
2686   Id p, pp;
2687   for (i = 0; i < job->count; i += 2)
2688     {
2689       how = job->elements[i];
2690       if ((how & SOLVER_JOBMASK) != SOLVER_MULTIVERSION)
2691         continue;
2692       what = job->elements[i + 1];
2693       select = how & SOLVER_SELECTMASK;
2694       if (!multiversionmap->size)
2695         map_grow(multiversionmap, pool->nsolvables);
2696       if (select == SOLVER_SOLVABLE_ALL)
2697         {
2698           FOR_POOL_SOLVABLES(p)
2699             MAPSET(multiversionmap, p);
2700         }
2701       else if (select == SOLVER_SOLVABLE_REPO)
2702         {
2703           Solvable *s;
2704           Repo *repo = pool_id2repo(pool, what);
2705           if (repo)
2706             FOR_REPO_SOLVABLES(repo, p, s)
2707               MAPSET(multiversionmap, p);
2708         }
2709       FOR_JOB_SELECT(p, pp, select, what)
2710         MAPSET(multiversionmap, p);
2711     }
2712 }
2713
2714 void
2715 solver_calculate_noobsmap(Pool *pool, Queue *job, Map *multiversionmap)
2716 {
2717   solver_calculate_multiversionmap(pool, job, multiversionmap);
2718 }
2719
2720 /*
2721  * add a rule created by a job, record job number and weak flag
2722  */
2723 static inline void
2724 solver_addjobrule(Solver *solv, Id p, Id d, Id job, int weak)
2725 {
2726   solver_addrule(solv, p, d);
2727   queue_push(&solv->ruletojob, job);
2728   if (weak)
2729     queue_push(&solv->weakruleq, solv->nrules - 1);
2730 }
2731
2732 static inline void
2733 add_cleandeps_package(Solver *solv, Id p)
2734 {
2735   if (!solv->cleandeps_updatepkgs)
2736     {
2737       solv->cleandeps_updatepkgs = solv_calloc(1, sizeof(Queue));
2738       queue_init(solv->cleandeps_updatepkgs);
2739     }
2740   queue_pushunique(solv->cleandeps_updatepkgs, p);
2741 }
2742
2743 static void
2744 add_update_target(Solver *solv, Id p, Id how)
2745 {
2746   Pool *pool = solv->pool;
2747   Solvable *s = pool->solvables + p;
2748   Repo *installed = solv->installed;
2749   Id pi, pip;
2750   if (!solv->update_targets)
2751     {
2752       solv->update_targets = solv_calloc(1, sizeof(Queue));
2753       queue_init(solv->update_targets);
2754     }
2755   if (s->repo == installed)
2756     {
2757       queue_push2(solv->update_targets, p, p);
2758       return;
2759     }
2760   FOR_PROVIDES(pi, pip, s->name)
2761     {
2762       Solvable *si = pool->solvables + pi;
2763       if (si->repo != installed || si->name != s->name)
2764         continue;
2765       if (how & SOLVER_FORCEBEST)
2766         {
2767           if (!solv->bestupdatemap.size)
2768             map_grow(&solv->bestupdatemap, installed->end - installed->start);
2769           MAPSET(&solv->bestupdatemap, pi - installed->start);
2770         }
2771       if (how & SOLVER_CLEANDEPS)
2772         add_cleandeps_package(solv, pi);
2773       queue_push2(solv->update_targets, pi, p);
2774       /* check if it's ok to keep the installed package */
2775       if (s->evr == si->evr && solvable_identical(s, si))
2776         queue_push2(solv->update_targets, pi, pi);
2777     }
2778   if (s->obsoletes)
2779     {
2780       Id obs, *obsp = s->repo->idarraydata + s->obsoletes;
2781       while ((obs = *obsp++) != 0)
2782         {
2783           FOR_PROVIDES(pi, pip, obs)
2784             {
2785               Solvable *si = pool->solvables + pi;
2786               if (si->repo != installed)
2787                 continue;
2788               if (si->name == s->name)
2789                 continue;       /* already handled above */
2790               if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, si, obs))
2791                 continue;
2792               if (pool->obsoleteusescolors && !pool_colormatch(pool, s, si))
2793                 continue;
2794               if (how & SOLVER_FORCEBEST)
2795                 {
2796                   if (!solv->bestupdatemap.size)
2797                     map_grow(&solv->bestupdatemap, installed->end - installed->start);
2798                   MAPSET(&solv->bestupdatemap, pi - installed->start);
2799                 }
2800               if (how & SOLVER_CLEANDEPS)
2801                 add_cleandeps_package(solv, pi);
2802               queue_push2(solv->update_targets, pi, p);
2803             }
2804         }
2805     }
2806 }
2807
2808 static int
2809 transform_update_targets_sortfn(const void *ap, const void *bp, void *dp)
2810 {
2811   const Id *a = ap;
2812   const Id *b = bp;
2813   if (a[0] - b[0])
2814     return a[0] - b[0];
2815   return a[1] - b[1];
2816 }
2817
2818 static void
2819 transform_update_targets(Solver *solv)
2820 {
2821   Repo *installed = solv->installed;
2822   Queue *update_targets = solv->update_targets;
2823   int i, j;
2824   Id p, q, lastp, lastq;
2825
2826   if (!update_targets->count)
2827     {
2828       queue_free(update_targets);
2829       solv->update_targets = solv_free(update_targets);
2830       return;
2831     }
2832   if (update_targets->count > 2)
2833     solv_sort(update_targets->elements, update_targets->count >> 1, 2 * sizeof(Id), transform_update_targets_sortfn, solv);
2834   queue_insertn(update_targets, 0, installed->end - installed->start, 0);
2835   lastp = lastq = 0;
2836   for (i = j = installed->end - installed->start; i < update_targets->count; i += 2)
2837     {
2838       if ((p = update_targets->elements[i]) != lastp)
2839         {
2840           if (!solv->updatemap.size)
2841             map_grow(&solv->updatemap, installed->end - installed->start);
2842           MAPSET(&solv->updatemap, p - installed->start);
2843           update_targets->elements[j++] = 0;                    /* finish old set */
2844           update_targets->elements[p - installed->start] = j;   /* start new set */
2845           lastp = p;
2846           lastq = 0;
2847         }
2848       if ((q = update_targets->elements[i + 1]) != lastq)
2849         {
2850           update_targets->elements[j++] = q;
2851           lastq = q;
2852         }
2853     }
2854   queue_truncate(update_targets, j);
2855   queue_push(update_targets, 0);        /* finish last set */
2856 }
2857
2858
2859 static void
2860 addedmap2deduceq(Solver *solv, Map *addedmap)
2861 {
2862   Pool *pool = solv->pool;
2863   int i, j;
2864   Id p;
2865   Rule *r;
2866
2867   queue_empty(&solv->addedmap_deduceq);
2868   for (i = 2, j = solv->rpmrules_end - 1; i < pool->nsolvables && j > 0; j--)
2869     {
2870       r = solv->rules + j;
2871       if (r->p >= 0)
2872         continue;
2873       if ((r->d == 0 || r->d == -1) && r->w2 < 0)
2874         continue;
2875       p = -r->p;
2876       if (!MAPTST(addedmap, p))
2877         {
2878           /* should never happen, but... */
2879           if (!solv->addedmap_deduceq.count || solv->addedmap_deduceq.elements[solv->addedmap_deduceq.count - 1] != -p)
2880             queue_push(&solv->addedmap_deduceq, -p);
2881           continue;
2882         }
2883       for (; i < p; i++)
2884         if (MAPTST(addedmap, i))
2885           queue_push(&solv->addedmap_deduceq, i);
2886       if (i == p)
2887         i++;
2888     }
2889   for (; i < pool->nsolvables; i++)
2890     if (MAPTST(addedmap, i))
2891       queue_push(&solv->addedmap_deduceq, i);
2892   j = 0;
2893   for (i = 2; i < pool->nsolvables; i++)
2894     if (MAPTST(addedmap, i))
2895       j++;
2896 }
2897
2898 static void
2899 deduceq2addedmap(Solver *solv, Map *addedmap)
2900 {
2901   int j;
2902   Id p;
2903   Rule *r;
2904   for (j = solv->rpmrules_end - 1; j > 0; j--)
2905     {
2906       r = solv->rules + j;
2907       if (r->d < 0 && r->p)
2908         solver_enablerule(solv, r);
2909       if (r->p >= 0)
2910         continue;
2911       if ((r->d == 0 || r->d == -1) && r->w2 < 0)
2912         continue;
2913       p = -r->p;
2914       MAPSET(addedmap, p);
2915     }
2916   for (j = 0; j < solv->addedmap_deduceq.count; j++)
2917     {
2918       p = solv->addedmap_deduceq.elements[j];
2919       if (p > 0)
2920         MAPSET(addedmap, p);
2921       else
2922         MAPCLR(addedmap, p);
2923     }
2924 }
2925
2926
2927 /*
2928  *
2929  * solve job queue
2930  *
2931  */
2932
2933 int
2934 solver_solve(Solver *solv, Queue *job)
2935 {
2936   Pool *pool = solv->pool;
2937   Repo *installed = solv->installed;
2938   int i;
2939   int oldnrules, initialnrules;
2940   Map addedmap;                /* '1' == have rpm-rules for solvable */
2941   Map installcandidatemap;
2942   Id how, what, select, name, weak, p, pp, d;
2943   Queue q;
2944   Solvable *s;
2945   Rule *r;
2946   int now, solve_start;
2947   int hasdupjob = 0;
2948   int hasbestinstalljob = 0;
2949
2950   solve_start = solv_timems(0);
2951
2952   /* log solver options */
2953   POOL_DEBUG(SOLV_DEBUG_STATS, "solver started\n");
2954   POOL_DEBUG(SOLV_DEBUG_STATS, "dosplitprovides=%d, noupdateprovide=%d, noinfarchcheck=%d\n", solv->dosplitprovides, solv->noupdateprovide, solv->noinfarchcheck);
2955   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);
2956   POOL_DEBUG(SOLV_DEBUG_STATS, "promoteepoch=%d, forbidselfconflicts=%d\n", pool->promoteepoch, pool->forbidselfconflicts);
2957   POOL_DEBUG(SOLV_DEBUG_STATS, "obsoleteusesprovides=%d, implicitobsoleteusesprovides=%d, obsoleteusescolors=%d, implicitobsoleteusescolors=%d\n", pool->obsoleteusesprovides, pool->implicitobsoleteusesprovides, pool->obsoleteusescolors, pool->implicitobsoleteusescolors);
2958   POOL_DEBUG(SOLV_DEBUG_STATS, "dontinstallrecommended=%d, addalreadyrecommended=%d\n", solv->dontinstallrecommended, solv->addalreadyrecommended);
2959
2960   /* create whatprovides if not already there */
2961   if (!pool->whatprovides)
2962     pool_createwhatprovides(pool);
2963
2964   /* create obsolete index */
2965   policy_create_obsolete_index(solv);
2966
2967   /* remember job */
2968   queue_free(&solv->job);
2969   queue_init_clone(&solv->job, job);
2970   solv->pooljobcnt = pool->pooljobs.count;
2971   if (pool->pooljobs.count)
2972     queue_insertn(&solv->job, 0, pool->pooljobs.count, pool->pooljobs.elements);
2973   job = &solv->job;
2974
2975   /* free old stuff */
2976   if (solv->update_targets)
2977     {
2978       queue_free(solv->update_targets);
2979       solv->update_targets = solv_free(solv->update_targets);
2980     }
2981   if (solv->cleandeps_updatepkgs)
2982     {
2983       queue_free(solv->cleandeps_updatepkgs);
2984       solv->cleandeps_updatepkgs = solv_free(solv->cleandeps_updatepkgs);
2985     }
2986   queue_empty(&solv->ruleassertions);
2987   solv->bestrules_pkg = solv_free(solv->bestrules_pkg);
2988   solv->choicerules_ref = solv_free(solv->choicerules_ref);
2989   if (solv->noupdate.size)
2990     map_empty(&solv->noupdate);
2991   if (solv->multiversion.size)
2992     {
2993       map_free(&solv->multiversion);
2994       map_init(&solv->multiversion, 0);
2995     }
2996   solv->updatemap_all = 0;
2997   if (solv->updatemap.size)
2998     {
2999       map_free(&solv->updatemap);
3000       map_init(&solv->updatemap, 0);
3001     }
3002   solv->bestupdatemap_all = 0;
3003   if (solv->bestupdatemap.size)
3004     {
3005       map_free(&solv->bestupdatemap);
3006       map_init(&solv->bestupdatemap, 0);
3007     }
3008   solv->fixmap_all = 0;
3009   if (solv->fixmap.size)
3010     {
3011       map_free(&solv->fixmap);
3012       map_init(&solv->fixmap, 0);
3013     }
3014   solv->dupmap_all = 0;
3015   if (solv->dupmap.size)
3016     {
3017       map_free(&solv->dupmap);
3018       map_init(&solv->dupmap, 0);
3019     }
3020   if (solv->dupinvolvedmap.size)
3021     {
3022       map_free(&solv->dupinvolvedmap);
3023       map_init(&solv->dupinvolvedmap, 0);
3024     }
3025   solv->droporphanedmap_all = 0;
3026   if (solv->droporphanedmap.size)
3027     {
3028       map_free(&solv->droporphanedmap);
3029       map_init(&solv->droporphanedmap, 0);
3030     }
3031   if (solv->cleandepsmap.size)
3032     {
3033       map_free(&solv->cleandepsmap);
3034       map_init(&solv->cleandepsmap, 0);
3035     }
3036
3037   queue_empty(&solv->weakruleq);
3038   solv->watches = solv_free(solv->watches);
3039   queue_empty(&solv->ruletojob);
3040   if (solv->decisionq.count)
3041     memset(solv->decisionmap, 0, pool->nsolvables * sizeof(Id));
3042   queue_empty(&solv->decisionq);
3043   queue_empty(&solv->decisionq_why);
3044   solv->decisioncnt_update = solv->decisioncnt_keep = solv->decisioncnt_resolve = solv->decisioncnt_weak = solv->decisioncnt_orphan = 0;
3045   queue_empty(&solv->learnt_why);
3046   queue_empty(&solv->learnt_pool);
3047   queue_empty(&solv->branches);
3048   solv->propagate_index = 0;
3049   queue_empty(&solv->problems);
3050   queue_empty(&solv->solutions);
3051   queue_empty(&solv->orphaned);
3052   solv->stats_learned = solv->stats_unsolvable = 0;
3053   if (solv->recommends_index)
3054     {
3055       map_empty(&solv->recommendsmap);
3056       map_empty(&solv->suggestsmap);
3057       solv->recommends_index = 0;
3058     }
3059   solv->multiversionupdaters = solv_free(solv->multiversionupdaters);
3060
3061
3062   /*
3063    * create basic rule set of all involved packages
3064    * use addedmap bitmap to make sure we don't create rules twice
3065    */
3066
3067   /* create multiversion map if needed */
3068   solver_calculate_multiversionmap(pool, job, &solv->multiversion);
3069
3070   map_init(&addedmap, pool->nsolvables);
3071   MAPSET(&addedmap, SYSTEMSOLVABLE);
3072
3073   map_init(&installcandidatemap, pool->nsolvables);
3074   queue_init(&q);
3075
3076   now = solv_timems(0);
3077   /*
3078    * create rules for all package that could be involved with the solving
3079    * so called: rpm rules
3080    *
3081    */
3082   initialnrules = solv->rpmrules_end ? solv->rpmrules_end : 1;
3083   if (initialnrules > 1)
3084     deduceq2addedmap(solv, &addedmap);
3085   if (solv->nrules != initialnrules)
3086     solver_shrinkrules(solv, initialnrules);
3087   solv->nrules = initialnrules;
3088   solv->rpmrules_end = 0;
3089
3090   if (installed)
3091     {
3092       /* check for update/verify jobs as they need to be known early */
3093       for (i = 0; i < job->count; i += 2)
3094         {
3095           how = job->elements[i];
3096           what = job->elements[i + 1];
3097           select = how & SOLVER_SELECTMASK;
3098           switch (how & SOLVER_JOBMASK)
3099             {
3100             case SOLVER_VERIFY:
3101               if (select == SOLVER_SOLVABLE_ALL || (select == SOLVER_SOLVABLE_REPO && installed && what == installed->repoid))
3102                 solv->fixmap_all = 1;
3103               FOR_JOB_SELECT(p, pp, select, what)
3104                 {
3105                   s = pool->solvables + p;
3106                   if (s->repo != installed)
3107                     continue;
3108                   if (!solv->fixmap.size)
3109                     map_grow(&solv->fixmap, installed->end - installed->start);
3110                   MAPSET(&solv->fixmap, p - installed->start);
3111                 }
3112               break;
3113             case SOLVER_UPDATE:
3114               if (select == SOLVER_SOLVABLE_ALL)
3115                 {
3116                   solv->updatemap_all = 1;
3117                   if (how & SOLVER_FORCEBEST)
3118                     solv->bestupdatemap_all = 1;
3119                   if (how & SOLVER_CLEANDEPS)
3120                     {
3121                       FOR_REPO_SOLVABLES(installed, p, s)
3122                         add_cleandeps_package(solv, p);
3123                     }
3124                 }
3125               else if (select == SOLVER_SOLVABLE_REPO)
3126                 {
3127                   Repo *repo = pool_id2repo(pool, what);
3128                   if (!repo)
3129                     break;
3130                   if (repo == installed && !(how & SOLVER_TARGETED))
3131                     {
3132                       solv->updatemap_all = 1;
3133                       if (how & SOLVER_FORCEBEST)
3134                         solv->bestupdatemap_all = 1;
3135                       if (how & SOLVER_CLEANDEPS)
3136                         {
3137                           FOR_REPO_SOLVABLES(installed, p, s)
3138                             add_cleandeps_package(solv, p);
3139                         }
3140                       break;
3141                     }
3142                   if (solv->noautotarget && !(how & SOLVER_TARGETED))
3143                     break;
3144                   /* targeted update */
3145                   FOR_REPO_SOLVABLES(repo, p, s)
3146                     add_update_target(solv, p, how);
3147                 }
3148               else
3149                 {
3150                   if (!(how & SOLVER_TARGETED))
3151                     {
3152                       int targeted = 1;
3153                       FOR_JOB_SELECT(p, pp, select, what)
3154                         {
3155                           s = pool->solvables + p;
3156                           if (s->repo != installed)
3157                             continue;
3158                           if (!solv->updatemap.size)
3159                             map_grow(&solv->updatemap, installed->end - installed->start);
3160                           MAPSET(&solv->updatemap, p - installed->start);
3161                           if (how & SOLVER_FORCEBEST)
3162                             {
3163                               if (!solv->bestupdatemap.size)
3164                                 map_grow(&solv->bestupdatemap, installed->end - installed->start);
3165                               MAPSET(&solv->bestupdatemap, p - installed->start);
3166                             }
3167                           if (how & SOLVER_CLEANDEPS)
3168                             add_cleandeps_package(solv, p);
3169                           targeted = 0;
3170                         }
3171                       if (!targeted || solv->noautotarget)
3172                         break;
3173                     }
3174                   FOR_JOB_SELECT(p, pp, select, what)
3175                     add_update_target(solv, p, how);
3176                 }
3177               break;
3178             default:
3179               break;
3180             }
3181         }
3182
3183       if (solv->update_targets)
3184         transform_update_targets(solv);
3185
3186       oldnrules = solv->nrules;
3187       FOR_REPO_SOLVABLES(installed, p, s)
3188         solver_addrpmrulesforsolvable(solv, s, &addedmap);
3189       POOL_DEBUG(SOLV_DEBUG_STATS, "added %d rpm rules for installed solvables\n", solv->nrules - oldnrules);
3190       oldnrules = solv->nrules;
3191       FOR_REPO_SOLVABLES(installed, p, s)
3192         solver_addrpmrulesforupdaters(solv, s, &addedmap, 1);
3193       POOL_DEBUG(SOLV_DEBUG_STATS, "added %d rpm rules for updaters of installed solvables\n", solv->nrules - oldnrules);
3194     }
3195
3196   /*
3197    * create rules for all packages involved in the job
3198    * (to be installed or removed)
3199    */
3200
3201   oldnrules = solv->nrules;
3202   for (i = 0; i < job->count; i += 2)
3203     {
3204       how = job->elements[i];
3205       what = job->elements[i + 1];
3206       select = how & SOLVER_SELECTMASK;
3207
3208       switch (how & SOLVER_JOBMASK)
3209         {
3210         case SOLVER_INSTALL:
3211           FOR_JOB_SELECT(p, pp, select, what)
3212             {
3213               MAPSET(&installcandidatemap, p);
3214               solver_addrpmrulesforsolvable(solv, pool->solvables + p, &addedmap);
3215             }
3216           break;
3217         case SOLVER_DISTUPGRADE:
3218           if (select == SOLVER_SOLVABLE_ALL)
3219             {
3220               solv->dupmap_all = 1;
3221               solv->updatemap_all = 1;
3222               if (how & SOLVER_FORCEBEST)
3223                 solv->bestupdatemap_all = 1;
3224             }
3225           if (!solv->dupmap_all)
3226             hasdupjob = 1;
3227           break;
3228         default:
3229           break;
3230         }
3231     }
3232   POOL_DEBUG(SOLV_DEBUG_STATS, "added %d rpm rules for packages involved in a job\n", solv->nrules - oldnrules);
3233
3234
3235   /*
3236    * add rules for suggests, enhances
3237    */
3238   oldnrules = solv->nrules;
3239   solver_addrpmrulesforweak(solv, &addedmap);
3240   POOL_DEBUG(SOLV_DEBUG_STATS, "added %d rpm rules because of weak dependencies\n", solv->nrules - oldnrules);
3241
3242   /*
3243    * first pass done, we now have all the rpm rules we need.
3244    * unify existing rules before going over all job rules and
3245    * policy rules.
3246    * at this point the system is always solvable,
3247    * as an empty system (remove all packages) is a valid solution
3248    */
3249
3250   IF_POOLDEBUG (SOLV_DEBUG_STATS)
3251     {
3252       int possible = 0, installable = 0;
3253       for (i = 1; i < pool->nsolvables; i++)
3254         {
3255           if (pool_installable(pool, pool->solvables + i))
3256             installable++;
3257           if (MAPTST(&addedmap, i))
3258             possible++;
3259         }
3260       POOL_DEBUG(SOLV_DEBUG_STATS, "%d of %d installable solvables considered for solving\n", possible, installable);
3261     }
3262
3263   if (solv->nrules > initialnrules)
3264     solver_unifyrules(solv);                    /* remove duplicate rpm rules */
3265   solv->rpmrules_end = solv->nrules;            /* mark end of rpm rules */
3266
3267   if (solv->nrules > initialnrules)
3268     addedmap2deduceq(solv, &addedmap);          /* so that we can recreate the addedmap */
3269
3270   POOL_DEBUG(SOLV_DEBUG_STATS, "rpm rule memory used: %d K\n", solv->nrules * (int)sizeof(Rule) / 1024);
3271   POOL_DEBUG(SOLV_DEBUG_STATS, "rpm rule creation took %d ms\n", solv_timems(now));
3272
3273   /* create dup maps if needed. We need the maps early to create our
3274    * update rules */
3275   if (hasdupjob)
3276     solver_createdupmaps(solv);
3277
3278   /*
3279    * create feature rules
3280    *
3281    * foreach installed:
3282    *   create assertion (keep installed, if no update available)
3283    *   or
3284    *   create update rule (A|update1(A)|update2(A)|...)
3285    *
3286    * those are used later on to keep a version of the installed packages in
3287    * best effort mode
3288    */
3289
3290   solv->featurerules = solv->nrules;              /* mark start of feature rules */
3291   if (installed)
3292     {
3293       /* foreach possibly installed solvable */
3294       for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
3295         {
3296           if (s->repo != installed)
3297             {
3298               solver_addrule(solv, 0, 0);       /* create dummy rule */
3299               continue;
3300             }
3301           solver_addupdaterule(solv, s, 1);    /* allow s to be updated */
3302         }
3303       /* make sure we accounted for all rules */
3304       assert(solv->nrules - solv->featurerules == installed->end - installed->start);
3305     }
3306   solv->featurerules_end = solv->nrules;
3307
3308     /*
3309      * Add update rules for installed solvables
3310      *
3311      * almost identical to feature rules
3312      * except that downgrades/archchanges/vendorchanges are not allowed
3313      */
3314
3315   solv->updaterules = solv->nrules;
3316
3317   if (installed)
3318     { /* foreach installed solvables */
3319       /* we create all update rules, but disable some later on depending on the job */
3320       for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
3321         {
3322           Rule *sr;
3323
3324           if (s->repo != installed)
3325             {
3326               solver_addrule(solv, 0, 0);       /* create dummy rule */
3327               continue;
3328             }
3329           solver_addupdaterule(solv, s, 0);     /* allowall = 0: downgrades not allowed */
3330           /*
3331            * check for and remove duplicate
3332            */
3333           r = solv->rules + solv->nrules - 1;           /* r: update rule */
3334           sr = r - (installed->end - installed->start); /* sr: feature rule */
3335           /* it's orphaned if there is no feature rule or the feature rule
3336            * consists just of the installed package */
3337           if (!sr->p || (sr->p == i && !sr->d && !sr->w2))
3338             queue_push(&solv->orphaned, i);
3339           if (!r->p)
3340             {
3341               assert(solv->dupmap_all && !sr->p);
3342               continue;
3343             }
3344           if (!solver_rulecmp(solv, r, sr))
3345             memset(sr, 0, sizeof(*sr));         /* delete unneeded feature rule */
3346           else
3347             solver_disablerule(solv, sr);       /* disable feature rule */
3348         }
3349       /* consistency check: we added a rule for _every_ installed solvable */
3350       assert(solv->nrules - solv->updaterules == installed->end - installed->start);
3351     }
3352   solv->updaterules_end = solv->nrules;
3353
3354
3355   /*
3356    * now add all job rules
3357    */
3358
3359   solv->jobrules = solv->nrules;
3360   for (i = 0; i < job->count; i += 2)
3361     {
3362       oldnrules = solv->nrules;
3363
3364       if (i && i == solv->pooljobcnt)
3365         POOL_DEBUG(SOLV_DEBUG_JOB, "end of pool jobs\n");
3366       how = job->elements[i];
3367       what = job->elements[i + 1];
3368       weak = how & SOLVER_WEAK;
3369       select = how & SOLVER_SELECTMASK;
3370       switch (how & SOLVER_JOBMASK)
3371         {
3372         case SOLVER_INSTALL:
3373           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sinstall %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
3374           if ((how & SOLVER_CLEANDEPS) != 0 && !solv->cleandepsmap.size && installed)
3375             map_grow(&solv->cleandepsmap, installed->end - installed->start);
3376           if (select == SOLVER_SOLVABLE)
3377             {
3378               p = what;
3379               d = 0;
3380             }
3381           else
3382             {
3383               queue_empty(&q);
3384               FOR_JOB_SELECT(p, pp, select, what)
3385                 queue_push(&q, p);
3386               if (!q.count)
3387                 {
3388                   if (select == SOLVER_SOLVABLE_ONE_OF)
3389                     break;      /* ignore empty installs */
3390                   /* no candidate found or unsupported, make this an impossible rule */
3391                   queue_push(&q, -SYSTEMSOLVABLE);
3392                 }
3393               p = queue_shift(&q);      /* get first candidate */
3394               d = !q.count ? 0 : pool_queuetowhatprovides(pool, &q);    /* internalize */
3395             }
3396           /* force install of namespace supplements hack */
3397           if (select == SOLVER_SOLVABLE_PROVIDES && !d && (p == SYSTEMSOLVABLE || p == -SYSTEMSOLVABLE) && ISRELDEP(what))
3398             {
3399               Reldep *rd = GETRELDEP(pool, what);
3400               if (rd->flags == REL_NAMESPACE)
3401                 {
3402                   p = SYSTEMSOLVABLE;
3403                   if (!solv->installsuppdepq)
3404                     {
3405                       solv->installsuppdepq = solv_calloc(1, sizeof(Queue));
3406                       queue_init(solv->installsuppdepq);
3407                     }
3408                   queue_pushunique(solv->installsuppdepq, rd->evr == 0 ? rd->name : what);
3409                 }
3410             }
3411           solver_addjobrule(solv, p, d, i, weak);
3412           if (how & SOLVER_FORCEBEST)
3413             hasbestinstalljob = 1;
3414           break;
3415         case SOLVER_ERASE:
3416           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %s%serase %s\n", weak ? "weak " : "", how & SOLVER_CLEANDEPS ? "clean deps " : "", solver_select2str(pool, select, what));
3417           if ((how & SOLVER_CLEANDEPS) != 0 && !solv->cleandepsmap.size && installed)
3418             map_grow(&solv->cleandepsmap, installed->end - installed->start);
3419           /* specific solvable: by id or by nevra */
3420           name = (select == SOLVER_SOLVABLE || (select == SOLVER_SOLVABLE_NAME && ISRELDEP(what))) ? 0 : -1;
3421           if (select == SOLVER_SOLVABLE_ALL)    /* hmmm ;) */
3422             {
3423               FOR_POOL_SOLVABLES(p)
3424                 solver_addjobrule(solv, -p, 0, i, weak);
3425             }
3426           else if (select == SOLVER_SOLVABLE_REPO)
3427             {
3428               Repo *repo = pool_id2repo(pool, what);
3429               if (repo)
3430                 FOR_REPO_SOLVABLES(repo, p, s)
3431                   solver_addjobrule(solv, -p, 0, i, weak);
3432             }
3433           FOR_JOB_SELECT(p, pp, select, what)
3434             {
3435               s = pool->solvables + p;
3436               if (installed && s->repo == installed)
3437                 name = !name ? s->name : -1;
3438               solver_addjobrule(solv, -p, 0, i, weak);
3439             }
3440           /* special case for "erase a specific solvable": we also
3441            * erase all other solvables with that name, so that they
3442            * don't get picked up as replacement.
3443            * name is > 0 if exactly one installed solvable matched.
3444            */
3445           /* XXX: look also at packages that obsolete this package? */
3446           if (name > 0)
3447             {
3448               int j, k;
3449               k = solv->nrules;
3450               FOR_PROVIDES(p, pp, name)
3451                 {
3452                   s = pool->solvables + p;
3453                   if (s->name != name)
3454                     continue;
3455                   /* keep other versions installed */
3456                   if (s->repo == installed)
3457                     continue;
3458                   /* keep installcandidates of other jobs */
3459                   if (MAPTST(&installcandidatemap, p))
3460                     continue;
3461                   /* don't add the same rule twice */
3462                   for (j = oldnrules; j < k; j++)
3463                     if (solv->rules[j].p == -p)
3464                       break;
3465                   if (j == k)
3466                     solver_addjobrule(solv, -p, 0, i, weak);    /* remove by id */
3467                 }
3468             }
3469           break;
3470
3471         case SOLVER_UPDATE:
3472           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %supdate %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
3473           break;
3474         case SOLVER_VERIFY:
3475           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sverify %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
3476           break;
3477         case SOLVER_WEAKENDEPS:
3478           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sweaken deps %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
3479           if (select != SOLVER_SOLVABLE)
3480             break;
3481           s = pool->solvables + what;
3482           weaken_solvable_deps(solv, what);
3483           break;
3484         case SOLVER_MULTIVERSION:
3485           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %smultiversion %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
3486           break;
3487         case SOLVER_LOCK:
3488           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %slock %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
3489           if (select == SOLVER_SOLVABLE_ALL)
3490             {
3491               FOR_POOL_SOLVABLES(p)
3492                 solver_addjobrule(solv, installed && pool->solvables[p].repo == installed ? p : -p, 0, i, weak);
3493             }
3494           else if (select == SOLVER_SOLVABLE_REPO)
3495             {
3496               Repo *repo = pool_id2repo(pool, what);
3497               if (repo)
3498                 FOR_REPO_SOLVABLES(repo, p, s)
3499                   solver_addjobrule(solv, installed && pool->solvables[p].repo == installed ? p : -p, 0, i, weak);
3500             }
3501           FOR_JOB_SELECT(p, pp, select, what)
3502             solver_addjobrule(solv, installed && pool->solvables[p].repo == installed ? p : -p, 0, i, weak);
3503           break;
3504         case SOLVER_DISTUPGRADE:
3505           POOL_DEBUG(SOLV_DEBUG_JOB, "job: distupgrade %s\n", solver_select2str(pool, select, what));
3506           break;
3507         case SOLVER_DROP_ORPHANED:
3508           POOL_DEBUG(SOLV_DEBUG_JOB, "job: drop orphaned %s\n", solver_select2str(pool, select, what));
3509           if (select == SOLVER_SOLVABLE_ALL || (select == SOLVER_SOLVABLE_REPO && installed && what == installed->repoid))
3510             solv->droporphanedmap_all = 1;
3511           FOR_JOB_SELECT(p, pp, select, what)
3512             {
3513               s = pool->solvables + p;
3514               if (!installed || s->repo != installed)
3515                 continue;
3516               if (!solv->droporphanedmap.size)
3517                 map_grow(&solv->droporphanedmap, installed->end - installed->start);
3518               MAPSET(&solv->droporphanedmap, p - installed->start);
3519             }
3520           break;
3521         case SOLVER_USERINSTALLED:
3522           POOL_DEBUG(SOLV_DEBUG_JOB, "job: user installed %s\n", solver_select2str(pool, select, what));
3523           break;
3524         default:
3525           POOL_DEBUG(SOLV_DEBUG_JOB, "job: unknown job\n");
3526           break;
3527         }
3528
3529         /*
3530          * debug
3531          */
3532
3533       IF_POOLDEBUG (SOLV_DEBUG_JOB)
3534         {
3535           int j;
3536           if (solv->nrules == oldnrules)
3537             POOL_DEBUG(SOLV_DEBUG_JOB, "  - no rule created\n");
3538           for (j = oldnrules; j < solv->nrules; j++)
3539             {
3540               POOL_DEBUG(SOLV_DEBUG_JOB, "  - job ");
3541               solver_printrule(solv, SOLV_DEBUG_JOB, solv->rules + j);
3542             }
3543         }
3544     }
3545   assert(solv->ruletojob.count == solv->nrules - solv->jobrules);
3546   solv->jobrules_end = solv->nrules;
3547
3548   /* now create infarch and dup rules */
3549   if (!solv->noinfarchcheck)
3550     {
3551       solver_addinfarchrules(solv, &addedmap);
3552       if (pool->implicitobsoleteusescolors)
3553         {
3554           /* currently doesn't work well with infarch rules, so make
3555            * them weak */
3556           for (i = solv->infarchrules; i < solv->infarchrules_end; i++)
3557             queue_push(&solv->weakruleq, i);
3558         }
3559     }
3560   else
3561     solv->infarchrules = solv->infarchrules_end = solv->nrules;
3562
3563   if (hasdupjob)
3564     solver_addduprules(solv, &addedmap);
3565   else
3566     solv->duprules = solv->duprules_end = solv->nrules;
3567
3568   if (solv->bestupdatemap_all || solv->bestupdatemap.size || hasbestinstalljob)
3569     solver_addbestrules(solv, hasbestinstalljob);
3570   else
3571     solv->bestrules = solv->bestrules_end = solv->nrules;
3572
3573   if (hasdupjob)
3574     solver_freedupmaps(solv);   /* no longer needed */
3575
3576   if (1)
3577     solver_addchoicerules(solv);
3578   else
3579     solv->choicerules = solv->choicerules_end = solv->nrules;
3580
3581   if (0)
3582     {
3583       for (i = solv->featurerules; i < solv->nrules; i++)
3584         solver_printruleclass(solv, SOLV_DEBUG_RESULT, solv->rules + i);
3585     }
3586   /* all rules created
3587    * --------------------------------------------------------------
3588    * prepare for solving
3589    */
3590
3591   /* free unneeded memory */
3592   map_free(&addedmap);
3593   map_free(&installcandidatemap);
3594   queue_free(&q);
3595
3596   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);
3597   POOL_DEBUG(SOLV_DEBUG_STATS, "overall rule memory used: %d K\n", solv->nrules * (int)sizeof(Rule) / 1024);
3598
3599   /* create weak map */
3600   map_init(&solv->weakrulemap, solv->nrules);
3601   for (i = 0; i < solv->weakruleq.count; i++)
3602     {
3603       p = solv->weakruleq.elements[i];
3604       MAPSET(&solv->weakrulemap, p);
3605     }
3606
3607   /* enable cleandepsmap creation if we have updatepkgs */
3608   if (solv->cleandeps_updatepkgs && !solv->cleandepsmap.size)
3609     map_grow(&solv->cleandepsmap, installed->end - installed->start);
3610   /* no mistakes */
3611   if (solv->cleandeps_mistakes)
3612     {
3613       queue_free(solv->cleandeps_mistakes);
3614       solv->cleandeps_mistakes = solv_free(solv->cleandeps_mistakes);
3615     }
3616
3617   /* all new rules are learnt after this point */
3618   solv->learntrules = solv->nrules;
3619
3620   /* create watches chains */
3621   makewatches(solv);
3622
3623   /* create assertion index. it is only used to speed up
3624    * makeruledecsions() a bit */
3625   for (i = 1, r = solv->rules + i; i < solv->nrules; i++, r++)
3626     if (r->p && !r->w2 && (r->d == 0 || r->d == -1))
3627       queue_push(&solv->ruleassertions, i);
3628
3629   /* disable update rules that conflict with our job */
3630   solver_disablepolicyrules(solv);
3631
3632   /* make initial decisions based on assertion rules */
3633   makeruledecisions(solv);
3634   POOL_DEBUG(SOLV_DEBUG_SOLVER, "problems so far: %d\n", solv->problems.count);
3635
3636   /*
3637    * ********************************************
3638    * solve!
3639    * ********************************************
3640    */
3641
3642   now = solv_timems(0);
3643   solver_run_sat(solv, 1, solv->dontinstallrecommended ? 0 : 1);
3644   POOL_DEBUG(SOLV_DEBUG_STATS, "solver took %d ms\n", solv_timems(now));
3645
3646   /*
3647    * prepare solution queue if there were problems
3648    */
3649   solver_prepare_solutions(solv);
3650
3651   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);
3652   POOL_DEBUG(SOLV_DEBUG_STATS, "solver_solve took %d ms\n", solv_timems(solve_start));
3653
3654   /* return number of problems */
3655   return solv->problems.count ? solv->problems.count / 2 : 0;
3656 }
3657
3658 Transaction *
3659 solver_create_transaction(Solver *solv)
3660 {
3661   return transaction_create_decisionq(solv->pool, &solv->decisionq, &solv->multiversion);
3662 }
3663
3664 void solver_get_orphaned(Solver *solv, Queue *orphanedq)
3665 {
3666   queue_free(orphanedq);
3667   queue_init_clone(orphanedq, &solv->orphaned);
3668 }
3669
3670 void solver_get_recommendations(Solver *solv, Queue *recommendationsq, Queue *suggestionsq, int noselected)
3671 {
3672   Pool *pool = solv->pool;
3673   Queue redoq, disabledq;
3674   int goterase, i;
3675   Solvable *s;
3676   Rule *r;
3677   Map obsmap;
3678
3679   if (!recommendationsq && !suggestionsq)
3680     return;
3681
3682   map_init(&obsmap, pool->nsolvables);
3683   if (solv->installed)
3684     {
3685       Id obs, *obsp, p, po, ppo;
3686       for (p = solv->installed->start; p < solv->installed->end; p++)
3687         {
3688           s = pool->solvables + p;
3689           if (s->repo != solv->installed || !s->obsoletes)
3690             continue;
3691           if (solv->decisionmap[p] <= 0)
3692             continue;
3693           if (solv->multiversion.size && MAPTST(&solv->multiversion, p))
3694             continue;
3695           obsp = s->repo->idarraydata + s->obsoletes;
3696           /* foreach obsoletes */
3697           while ((obs = *obsp++) != 0)
3698             FOR_PROVIDES(po, ppo, obs)
3699               MAPSET(&obsmap, po);
3700         }
3701     }
3702
3703   queue_init(&redoq);
3704   queue_init(&disabledq);
3705   goterase = 0;
3706   /* disable all erase jobs (including weak "keep uninstalled" rules) */
3707   for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++)
3708     {
3709       if (r->d < 0)     /* disabled ? */
3710         continue;
3711       if (r->p >= 0)    /* install job? */
3712         continue;
3713       queue_push(&disabledq, i);
3714       solver_disablerule(solv, r);
3715       goterase++;
3716     }
3717
3718   if (goterase)
3719     {
3720       enabledisablelearntrules(solv);
3721       removedisabledconflicts(solv, &redoq);
3722     }
3723
3724   /*
3725    * find recommended packages
3726    */
3727   if (recommendationsq)
3728     {
3729       Id rec, *recp, p, pp;
3730
3731       queue_empty(recommendationsq);
3732       /* create map of all recommened packages */
3733       solv->recommends_index = -1;
3734       MAPZERO(&solv->recommendsmap);
3735
3736       /* put all packages the solver already chose in the map */
3737       if (solv->decisioncnt_weak)
3738         {
3739           for (i = solv->decisioncnt_weak; i < solv->decisioncnt_orphan; i++)
3740             {
3741               Id why;
3742               why = solv->decisionq_why.elements[i];
3743               if (why)
3744                 continue;       /* forced by unit rule */
3745               p = solv->decisionq.elements[i];
3746               if (p < 0)
3747                 continue;
3748               MAPSET(&solv->recommendsmap, p);
3749             }
3750         }
3751
3752       for (i = 0; i < solv->decisionq.count; i++)
3753         {
3754           p = solv->decisionq.elements[i];
3755           if (p < 0)
3756             continue;
3757           s = pool->solvables + p;
3758           if (s->recommends)
3759             {
3760               recp = s->repo->idarraydata + s->recommends;
3761               while ((rec = *recp++) != 0)
3762                 {
3763                   FOR_PROVIDES(p, pp, rec)
3764                     if (solv->decisionmap[p] > 0)
3765                       break;
3766                   if (p)
3767                     {
3768                       if (!noselected)
3769                         {
3770                           FOR_PROVIDES(p, pp, rec)
3771                             if (solv->decisionmap[p] > 0)
3772                               MAPSET(&solv->recommendsmap, p);
3773                         }
3774                       continue; /* p != 0: already fulfilled */
3775                     }
3776                   FOR_PROVIDES(p, pp, rec)
3777                     MAPSET(&solv->recommendsmap, p);
3778                 }
3779             }
3780         }
3781       for (i = 1; i < pool->nsolvables; i++)
3782         {
3783           if (solv->decisionmap[i] < 0)
3784             continue;
3785           if (solv->decisionmap[i] > 0 && noselected)
3786             continue;
3787           if (MAPTST(&obsmap, i))
3788             continue;
3789           s = pool->solvables + i;
3790           if (!MAPTST(&solv->recommendsmap, i))
3791             {
3792               if (!s->supplements)
3793                 continue;
3794               if (!pool_installable(pool, s))
3795                 continue;
3796               if (!solver_is_supplementing(solv, s))
3797                 continue;
3798             }
3799           queue_push(recommendationsq, i);
3800         }
3801       /* we use MODE_SUGGEST here so that repo prio is ignored */
3802       policy_filter_unwanted(solv, recommendationsq, POLICY_MODE_SUGGEST);
3803     }
3804
3805   /*
3806    * find suggested packages
3807    */
3808
3809   if (suggestionsq)
3810     {
3811       Id sug, *sugp, p, pp;
3812
3813       queue_empty(suggestionsq);
3814       /* create map of all suggests that are still open */
3815       solv->recommends_index = -1;
3816       MAPZERO(&solv->suggestsmap);
3817       for (i = 0; i < solv->decisionq.count; i++)
3818         {
3819           p = solv->decisionq.elements[i];
3820           if (p < 0)
3821             continue;
3822           s = pool->solvables + p;
3823           if (s->suggests)
3824             {
3825               sugp = s->repo->idarraydata + s->suggests;
3826               while ((sug = *sugp++) != 0)
3827                 {
3828                   FOR_PROVIDES(p, pp, sug)
3829                     if (solv->decisionmap[p] > 0)
3830                       break;
3831                   if (p)
3832                     {
3833                       if (!noselected)
3834                         {
3835                           FOR_PROVIDES(p, pp, sug)
3836                             if (solv->decisionmap[p] > 0)
3837                               MAPSET(&solv->suggestsmap, p);
3838                         }
3839                       continue; /* already fulfilled */
3840                     }
3841                   FOR_PROVIDES(p, pp, sug)
3842                     MAPSET(&solv->suggestsmap, p);
3843                 }
3844             }
3845         }
3846       for (i = 1; i < pool->nsolvables; i++)
3847         {
3848           if (solv->decisionmap[i] < 0)
3849             continue;
3850           if (solv->decisionmap[i] > 0 && noselected)
3851             continue;
3852           if (MAPTST(&obsmap, i))
3853             continue;
3854           s = pool->solvables + i;
3855           if (!MAPTST(&solv->suggestsmap, i))
3856             {
3857               if (!s->enhances)
3858                 continue;
3859               if (!pool_installable(pool, s))
3860                 continue;
3861               if (!solver_is_enhancing(solv, s))
3862                 continue;
3863             }
3864           queue_push(suggestionsq, i);
3865         }
3866       policy_filter_unwanted(solv, suggestionsq, POLICY_MODE_SUGGEST);
3867     }
3868
3869   /* undo removedisabledconflicts */
3870   if (redoq.count)
3871     undo_removedisabledconflicts(solv, &redoq);
3872   queue_free(&redoq);
3873
3874   /* undo job rule disabling */
3875   for (i = 0; i < disabledq.count; i++)
3876     solver_enablerule(solv, solv->rules + disabledq.elements[i]);
3877   queue_free(&disabledq);
3878   map_free(&obsmap);
3879 }
3880
3881
3882 /***********************************************************************/
3883 /* disk usage computations */
3884
3885 /*-------------------------------------------------------------------
3886  *
3887  * calculate DU changes
3888  */
3889
3890 void
3891 solver_calc_duchanges(Solver *solv, DUChanges *mps, int nmps)
3892 {
3893   Map installedmap;
3894
3895   solver_create_state_maps(solv, &installedmap, 0);
3896   pool_calc_duchanges(solv->pool, &installedmap, mps, nmps);
3897   map_free(&installedmap);
3898 }
3899
3900
3901 /*-------------------------------------------------------------------
3902  *
3903  * calculate changes in install size
3904  */
3905
3906 int
3907 solver_calc_installsizechange(Solver *solv)
3908 {
3909   Map installedmap;
3910   int change;
3911
3912   solver_create_state_maps(solv, &installedmap, 0);
3913   change = pool_calc_installsizechange(solv->pool, &installedmap);
3914   map_free(&installedmap);
3915   return change;
3916 }
3917
3918 void
3919 solver_create_state_maps(Solver *solv, Map *installedmap, Map *conflictsmap)
3920 {
3921   pool_create_state_maps(solv->pool, &solv->decisionq, installedmap, conflictsmap);
3922 }
3923
3924 void
3925 solver_trivial_installable(Solver *solv, Queue *pkgs, Queue *res)
3926 {
3927   Pool *pool = solv->pool;
3928   Map installedmap;
3929   int i;
3930   pool_create_state_maps(pool,  &solv->decisionq, &installedmap, 0);
3931   pool_trivial_installable_multiversionmap(pool, &installedmap, pkgs, res, solv->multiversion.size ? &solv->multiversion : 0);
3932   for (i = 0; i < res->count; i++)
3933     if (res->elements[i] != -1)
3934       {
3935         Solvable *s = pool->solvables + pkgs->elements[i];
3936         if (!strncmp("patch:", pool_id2str(pool, s->name), 6) && solvable_is_irrelevant_patch(s, &installedmap))
3937           res->elements[i] = -1;
3938       }
3939   map_free(&installedmap);
3940 }
3941
3942 /*-------------------------------------------------------------------
3943  *
3944  * decision introspection
3945  */
3946
3947 int
3948 solver_get_decisionlevel(Solver *solv, Id p)
3949 {
3950   return solv->decisionmap[p];
3951 }
3952
3953 void
3954 solver_get_decisionqueue(Solver *solv, Queue *decisionq)
3955 {
3956   queue_free(decisionq);
3957   queue_init_clone(decisionq, &solv->decisionq);
3958 }
3959
3960 int
3961 solver_get_lastdecisionblocklevel(Solver *solv)
3962 {
3963   Id p;
3964   if (solv->decisionq.count == 0)
3965     return 0;
3966   p = solv->decisionq.elements[solv->decisionq.count - 1];
3967   if (p < 0)
3968     p = -p;
3969   return solv->decisionmap[p] < 0 ? -solv->decisionmap[p] : solv->decisionmap[p];
3970 }
3971
3972 void
3973 solver_get_decisionblock(Solver *solv, int level, Queue *decisionq)
3974 {
3975   Id p;
3976   int i;
3977
3978   queue_empty(decisionq);
3979   for (i = 0; i < solv->decisionq.count; i++)
3980     {
3981       p = solv->decisionq.elements[i];
3982       if (p < 0)
3983         p = -p;
3984       if (solv->decisionmap[p] == level || solv->decisionmap[p] == -level)
3985         break;
3986     }
3987   if (i == solv->decisionq.count)
3988     return;
3989   for (i = 0; i < solv->decisionq.count; i++)
3990     {
3991       p = solv->decisionq.elements[i];
3992       if (p < 0)
3993         p = -p;
3994       if (solv->decisionmap[p] == level || solv->decisionmap[p] == -level)
3995         queue_push(decisionq, p);
3996       else
3997         break;
3998     }
3999 }
4000
4001 int
4002 solver_describe_decision(Solver *solv, Id p, Id *infop)
4003 {
4004   int i;
4005   Id pp, why;
4006
4007   if (infop)
4008     *infop = 0;
4009   if (!solv->decisionmap[p])
4010     return SOLVER_REASON_UNRELATED;
4011   pp = solv->decisionmap[p] < 0 ? -p : p;
4012   for (i = 0; i < solv->decisionq.count; i++)
4013     if (solv->decisionq.elements[i] == pp)
4014       break;
4015   if (i == solv->decisionq.count)       /* just in case... */
4016     return SOLVER_REASON_UNRELATED;
4017   why = solv->decisionq_why.elements[i];
4018   if (why > 0)
4019     {
4020       if (infop)
4021         *infop = why;
4022       return SOLVER_REASON_UNIT_RULE;
4023     }
4024   why = -why;
4025   if (i < solv->decisioncnt_update)
4026     {
4027       if (i == 0)
4028         {
4029           if (infop)
4030             *infop = SYSTEMSOLVABLE;
4031           return SOLVER_REASON_KEEP_INSTALLED;
4032         }
4033       if (infop)
4034         *infop = why;
4035       return SOLVER_REASON_RESOLVE_JOB;
4036     }
4037   if (i < solv->decisioncnt_keep)
4038     {
4039       if (why == 0 && pp < 0)
4040         return SOLVER_REASON_CLEANDEPS_ERASE;
4041       if (infop)
4042         {
4043           if (why >= solv->updaterules && why < solv->updaterules_end)
4044             *infop = why - solv->updaterules;
4045           else if (why >= solv->featurerules && why < solv->featurerules_end)
4046             *infop = why - solv->featurerules;
4047         }
4048       return SOLVER_REASON_UPDATE_INSTALLED;
4049     }
4050   if (i < solv->decisioncnt_resolve)
4051     {
4052       if (why == 0 && pp < 0)
4053         return SOLVER_REASON_CLEANDEPS_ERASE;
4054       if (infop)
4055         {
4056           if (why >= solv->updaterules && why < solv->updaterules_end)
4057             *infop = why - solv->updaterules;
4058           else if (why >= solv->featurerules && why < solv->featurerules_end)
4059             *infop = why - solv->featurerules;
4060         }
4061       return SOLVER_REASON_KEEP_INSTALLED;
4062     }
4063   if (i < solv->decisioncnt_weak)
4064     {
4065       if (infop)
4066         *infop = why;
4067       return SOLVER_REASON_RESOLVE;
4068     }
4069   if (solv->decisionq.count < solv->decisioncnt_orphan)
4070     return SOLVER_REASON_WEAKDEP;
4071   return SOLVER_REASON_RESOLVE_ORPHAN;
4072 }
4073
4074
4075 void
4076 solver_describe_weakdep_decision(Solver *solv, Id p, Queue *whyq)
4077 {
4078   Pool *pool = solv->pool;
4079   int i;
4080   int level = solv->decisionmap[p];
4081   int decisionno;
4082   Solvable *s;
4083
4084   queue_empty(whyq);
4085   if (level < 0)
4086     return;     /* huh? */
4087   for (decisionno = 0; decisionno < solv->decisionq.count; decisionno++)
4088     if (solv->decisionq.elements[decisionno] == p)
4089       break;
4090   if (decisionno == solv->decisionq.count)
4091     return;     /* huh? */
4092   if (decisionno < solv->decisioncnt_weak || decisionno >= solv->decisioncnt_orphan)
4093     return;     /* huh? */
4094
4095   /* 1) list all packages that recommend us */
4096   for (i = 1; i < pool->nsolvables; i++)
4097     {
4098       Id *recp, rec, pp2, p2;
4099       if (solv->decisionmap[i] < 0 || solv->decisionmap[i] >= level)
4100         continue;
4101       s = pool->solvables + i;
4102       if (!s->recommends)
4103         continue;
4104       if (!solv->addalreadyrecommended && s->repo == solv->installed)
4105         continue;
4106       recp = s->repo->idarraydata + s->recommends;
4107       while ((rec = *recp++) != 0)
4108         {
4109           int found = 0;
4110           FOR_PROVIDES(p2, pp2, rec)
4111             {
4112               if (p2 == p)
4113                 found = 1;
4114               else
4115                 {
4116                   /* if p2 is already installed, this recommends is ignored */
4117                   if (solv->decisionmap[p2] > 0 && solv->decisionmap[p2] < level)
4118                     break;
4119                 }
4120             }
4121           if (!p2 && found)
4122             {
4123               queue_push(whyq, SOLVER_REASON_RECOMMENDED);
4124               queue_push2(whyq, p2, rec);
4125             }
4126         }
4127     }
4128   /* 2) list all supplements */
4129   s = pool->solvables + p;
4130   if (s->supplements && level > 0)
4131     {
4132       Id *supp, sup, pp2, p2;
4133       /* this is a hack. to use solver_dep_fulfilled we temporarily clear
4134        * everything above our level in the decisionmap */
4135       for (i = decisionno; i < solv->decisionq.count; i++ )
4136         {
4137           p2 = solv->decisionq.elements[i];
4138           if (p2 > 0)
4139             solv->decisionmap[p2] = -solv->decisionmap[p2];
4140         }
4141       supp = s->repo->idarraydata + s->supplements;
4142       while ((sup = *supp++) != 0)
4143         if (solver_dep_fulfilled(solv, sup))
4144           {
4145             int found = 0;
4146             /* let's see if this is an easy supp */
4147             FOR_PROVIDES(p2, pp2, sup)
4148               {
4149                 if (!solv->addalreadyrecommended && solv->installed)
4150                   {
4151                     if (pool->solvables[p2].repo == solv->installed)
4152                       continue;
4153                   }
4154                 if (solv->decisionmap[p2] > 0 && solv->decisionmap[p2] < level)
4155                   {
4156                     queue_push(whyq, SOLVER_REASON_SUPPLEMENTED);
4157                     queue_push2(whyq, p2, sup);
4158                     found = 1;
4159                   }
4160               }
4161             if (!found)
4162               {
4163                 /* hard case, just note dependency with no package */
4164                 queue_push(whyq, SOLVER_REASON_SUPPLEMENTED);
4165                 queue_push2(whyq, 0, sup);
4166               }
4167           }
4168       for (i = decisionno; i < solv->decisionq.count; i++)
4169         {
4170           p2 = solv->decisionq.elements[i];
4171           if (p2 > 0)
4172             solv->decisionmap[p2] = -solv->decisionmap[p2];
4173         }
4174     }
4175 }
4176
4177 void
4178 pool_job2solvables(Pool *pool, Queue *pkgs, Id how, Id what)
4179 {
4180   Id p, pp;
4181   how &= SOLVER_SELECTMASK;
4182   queue_empty(pkgs);
4183   if (how == SOLVER_SOLVABLE_ALL)
4184     {
4185       FOR_POOL_SOLVABLES(p)
4186         queue_push(pkgs, p);
4187     }
4188   else if (how == SOLVER_SOLVABLE_REPO)
4189     {
4190       Repo *repo = pool_id2repo(pool, what);
4191       Solvable *s;
4192       if (repo)
4193         FOR_REPO_SOLVABLES(repo, p, s)
4194           queue_push(pkgs, p);
4195     }
4196   else
4197     {
4198       FOR_JOB_SELECT(p, pp, how, what)
4199         queue_push(pkgs, p);
4200     }
4201 }
4202
4203 int
4204 pool_isemptyupdatejob(Pool *pool, Id how, Id what)
4205 {
4206   Id p, pp, pi, pip;
4207   Id select = how & SOLVER_SELECTMASK;
4208   if ((how & SOLVER_JOBMASK) != SOLVER_UPDATE)
4209     return 0;
4210   if (select == SOLVER_SOLVABLE_ALL || select == SOLVER_SOLVABLE_REPO)
4211     return 0;
4212   if (!pool->installed)
4213     return 1;
4214   FOR_JOB_SELECT(p, pp, select, what)
4215     if (pool->solvables[p].repo == pool->installed)
4216       return 0;
4217   /* hard work */
4218   FOR_JOB_SELECT(p, pp, select, what)
4219     {
4220       Solvable *s = pool->solvables + p;
4221       FOR_PROVIDES(pi, pip, s->name)
4222         {
4223           Solvable *si = pool->solvables + pi;
4224           if (si->repo != pool->installed || si->name != s->name)
4225             continue;
4226           return 0;
4227         }
4228       if (s->obsoletes)
4229         {
4230           Id obs, *obsp = s->repo->idarraydata + s->obsoletes;
4231           while ((obs = *obsp++) != 0)
4232             {
4233               FOR_PROVIDES(pi, pip, obs)
4234                 {
4235                   Solvable *si = pool->solvables + pi;
4236                   if (si->repo != pool->installed)
4237                     continue;
4238                   if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, si, obs))
4239                     continue;
4240                   if (pool->obsoleteusescolors && !pool_colormatch(pool, s, si))
4241                     continue;
4242                   return 0;
4243                 }
4244             }
4245         }
4246     }
4247   return 1;
4248 }
4249
4250 const char *
4251 solver_select2str(Pool *pool, Id select, Id what)
4252 {
4253   const char *s;
4254   char *b;
4255   select &= SOLVER_SELECTMASK;
4256   if (select == SOLVER_SOLVABLE)
4257     return pool_solvid2str(pool, what);
4258   if (select == SOLVER_SOLVABLE_NAME)
4259     return pool_dep2str(pool, what);
4260   if (select == SOLVER_SOLVABLE_PROVIDES)
4261     {
4262       s = pool_dep2str(pool, what);
4263       b = pool_alloctmpspace(pool, 11 + strlen(s));
4264       sprintf(b, "providing %s", s);
4265       return b;
4266     }
4267   if (select == SOLVER_SOLVABLE_ONE_OF)
4268     {
4269       Id p;
4270       b = 0;
4271       while ((p = pool->whatprovidesdata[what++]) != 0)
4272         {
4273           s = pool_solvid2str(pool, p);
4274           if (b)
4275             b = pool_tmpappend(pool, b, ", ", s);
4276           else
4277             b = pool_tmpjoin(pool, s, 0, 0);
4278           pool_freetmpspace(pool, s);
4279         }
4280       return b ? b : "nothing";
4281     }
4282   if (select == SOLVER_SOLVABLE_REPO)
4283     {
4284       b = pool_alloctmpspace(pool, 20);
4285       sprintf(b, "repo #%d", what);
4286       return b;
4287     }
4288   if (select == SOLVER_SOLVABLE_ALL)
4289     return "all packages";
4290   return "unknown job select";
4291 }
4292
4293 const char *
4294 pool_job2str(Pool *pool, Id how, Id what, Id flagmask)
4295 {
4296   Id select = how & SOLVER_SELECTMASK;
4297   const char *strstart = 0, *strend = 0;
4298   char *s;
4299   int o;
4300
4301   switch (how & SOLVER_JOBMASK)
4302     {
4303     case SOLVER_NOOP:
4304       return "do nothing";
4305     case SOLVER_INSTALL:
4306       if (select == SOLVER_SOLVABLE && pool->installed && pool->solvables[what].repo == pool->installed)
4307         strstart = "keep ", strend = "installed";
4308       else if (select == SOLVER_SOLVABLE || select == SOLVER_SOLVABLE_NAME)
4309         strstart = "install ";
4310       else if (select == SOLVER_SOLVABLE_PROVIDES)
4311         strstart = "install a package ";
4312       else
4313         strstart = "install one of ";
4314       break;
4315     case SOLVER_ERASE:
4316       if (select == SOLVER_SOLVABLE && !(pool->installed && pool->solvables[what].repo == pool->installed))
4317         strstart = "keep ", strend = "unstalled";
4318       else if (select == SOLVER_SOLVABLE_PROVIDES)
4319         strstart = "deinstall all packages ";
4320       else
4321         strstart = "deinstall ";
4322       break;
4323     case SOLVER_UPDATE:
4324       strstart = "update ";
4325       break;
4326     case SOLVER_WEAKENDEPS:
4327       strstart = "weaken deps of ";
4328       break;
4329     case SOLVER_MULTIVERSION:
4330       strstart = "multi version ";
4331       break;
4332     case SOLVER_LOCK:
4333       strstart = "update ";
4334       break;
4335     case SOLVER_DISTUPGRADE:
4336       strstart = "dist upgrade ";
4337       break;
4338     case SOLVER_VERIFY:
4339       strstart = "verify ";
4340       break;
4341     case SOLVER_DROP_ORPHANED:
4342       strstart = "deinstall ", strend = "if orphaned";
4343       break;
4344     case SOLVER_USERINSTALLED:
4345       strstart = "regard ", strend = "as userinstalled";
4346       break;
4347     default:
4348       strstart = "unknown job ";
4349       break;
4350     }
4351   s = pool_tmpjoin(pool, strstart, solver_select2str(pool, select, what), strend);
4352   how &= flagmask;
4353   if ((how & ~(SOLVER_SELECTMASK|SOLVER_JOBMASK)) == 0)
4354     return s;
4355   o = strlen(s);
4356   s = pool_tmpappend(pool, s, " ", 0);
4357   if (how & SOLVER_WEAK)
4358     s = pool_tmpappend(pool, s, ",weak", 0);
4359   if (how & SOLVER_ESSENTIAL)
4360     s = pool_tmpappend(pool, s, ",essential", 0);
4361   if (how & SOLVER_CLEANDEPS)
4362     s = pool_tmpappend(pool, s, ",cleandeps", 0);
4363   if (how & SOLVER_SETEV)
4364     s = pool_tmpappend(pool, s, ",setev", 0);
4365   if (how & SOLVER_SETEVR)
4366     s = pool_tmpappend(pool, s, ",setevr", 0);
4367   if (how & SOLVER_SETARCH)
4368     s = pool_tmpappend(pool, s, ",setarch", 0);
4369   if (how & SOLVER_SETVENDOR)
4370     s = pool_tmpappend(pool, s, ",setvendor", 0);
4371   if (how & SOLVER_SETREPO)
4372     s = pool_tmpappend(pool, s, ",setrepo", 0);
4373   if (how & SOLVER_NOAUTOSET)
4374     s = pool_tmpappend(pool, s, ",noautoset", 0);
4375   if (s[o + 1] != ',')
4376     s = pool_tmpappend(pool, s, ",?", 0);
4377   s[o + 1] = '[';
4378   return pool_tmpappend(pool, s, "]", 0);
4379 }
4380