src/solver.c

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