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->yumobsrules_info);
1685   solv_free(solv->instbuddy);
1686   solv_free(solv);
1687 }
1688
1689 int
1690 solver_get_flag(Solver *solv, int flag)
1691 {
1692   switch (flag)
1693   {
1694   case SOLVER_FLAG_ALLOW_DOWNGRADE:
1695     return solv->allowdowngrade;
1696   case SOLVER_FLAG_ALLOW_NAMECHANGE:
1697     return solv->allownamechange;
1698   case SOLVER_FLAG_ALLOW_ARCHCHANGE:
1699     return solv->allowarchchange;
1700   case SOLVER_FLAG_ALLOW_VENDORCHANGE:
1701     return solv->allowvendorchange;
1702   case SOLVER_FLAG_ALLOW_UNINSTALL:
1703     return solv->allowuninstall;
1704   case SOLVER_FLAG_NO_UPDATEPROVIDE:
1705     return solv->noupdateprovide;
1706   case SOLVER_FLAG_SPLITPROVIDES:
1707     return solv->dosplitprovides;
1708   case SOLVER_FLAG_IGNORE_RECOMMENDED:
1709     return solv->dontinstallrecommended;
1710   case SOLVER_FLAG_ADD_ALREADY_RECOMMENDED:
1711     return solv->addalreadyrecommended;
1712   case SOLVER_FLAG_NO_INFARCHCHECK:
1713     return solv->noinfarchcheck;
1714   case SOLVER_FLAG_KEEP_EXPLICIT_OBSOLETES:
1715     return solv->keepexplicitobsoletes;
1716   case SOLVER_FLAG_BEST_OBEY_POLICY:
1717     return solv->bestobeypolicy;
1718   case SOLVER_FLAG_NO_AUTOTARGET:
1719     return solv->noautotarget;
1720   case SOLVER_FLAG_DUP_ALLOW_DOWNGRADE:
1721     return solv->dup_allowdowngrade;
1722   case SOLVER_FLAG_DUP_ALLOW_NAMECHANGE:
1723     return solv->dup_allownamechange;
1724   case SOLVER_FLAG_DUP_ALLOW_ARCHCHANGE:
1725     return solv->dup_allowarchchange;
1726   case SOLVER_FLAG_DUP_ALLOW_VENDORCHANGE:
1727     return solv->dup_allowvendorchange;
1728   case SOLVER_FLAG_KEEP_ORPHANS:
1729     return solv->keep_orphans;
1730   case SOLVER_FLAG_BREAK_ORPHANS:
1731     return solv->break_orphans;
1732   case SOLVER_FLAG_FOCUS_INSTALLED:
1733     return solv->focus_installed;
1734   case SOLVER_FLAG_YUM_OBSOLETES:
1735     return solv->do_yum_obsoletes;
1736   default:
1737     break;
1738   }
1739   return -1;
1740 }
1741
1742 int
1743 solver_set_flag(Solver *solv, int flag, int value)
1744 {
1745   int old = solver_get_flag(solv, flag);
1746   switch (flag)
1747   {
1748   case SOLVER_FLAG_ALLOW_DOWNGRADE:
1749     solv->allowdowngrade = value;
1750     break;
1751   case SOLVER_FLAG_ALLOW_NAMECHANGE:
1752     solv->allownamechange = value;
1753     break;
1754   case SOLVER_FLAG_ALLOW_ARCHCHANGE:
1755     solv->allowarchchange = value;
1756     break;
1757   case SOLVER_FLAG_ALLOW_VENDORCHANGE:
1758     solv->allowvendorchange = value;
1759     break;
1760   case SOLVER_FLAG_ALLOW_UNINSTALL:
1761     solv->allowuninstall = value;
1762     break;
1763   case SOLVER_FLAG_NO_UPDATEPROVIDE:
1764     solv->noupdateprovide = value;
1765     break;
1766   case SOLVER_FLAG_SPLITPROVIDES:
1767     solv->dosplitprovides = value;
1768     break;
1769   case SOLVER_FLAG_IGNORE_RECOMMENDED:
1770     solv->dontinstallrecommended = value;
1771     break;
1772   case SOLVER_FLAG_ADD_ALREADY_RECOMMENDED:
1773     solv->addalreadyrecommended = value;
1774     break;
1775   case SOLVER_FLAG_NO_INFARCHCHECK:
1776     solv->noinfarchcheck = value;
1777     break;
1778   case SOLVER_FLAG_KEEP_EXPLICIT_OBSOLETES:
1779     solv->keepexplicitobsoletes = value;
1780     break;
1781   case SOLVER_FLAG_BEST_OBEY_POLICY:
1782     solv->bestobeypolicy = value;
1783     break;
1784   case SOLVER_FLAG_NO_AUTOTARGET:
1785     solv->noautotarget = value;
1786     break;
1787   case SOLVER_FLAG_DUP_ALLOW_DOWNGRADE:
1788     solv->dup_allowdowngrade = value;
1789     break;
1790   case SOLVER_FLAG_DUP_ALLOW_NAMECHANGE:
1791     solv->dup_allownamechange = value;
1792     break;
1793   case SOLVER_FLAG_DUP_ALLOW_ARCHCHANGE:
1794     solv->dup_allowarchchange = value;
1795     break;
1796   case SOLVER_FLAG_DUP_ALLOW_VENDORCHANGE:
1797     solv->dup_allowvendorchange = value;
1798     break;
1799   case SOLVER_FLAG_KEEP_ORPHANS:
1800     solv->keep_orphans = value;
1801     break;
1802   case SOLVER_FLAG_BREAK_ORPHANS:
1803     solv->break_orphans = value;
1804     break;
1805   case SOLVER_FLAG_FOCUS_INSTALLED:
1806     solv->focus_installed = value;
1807     break;
1808   case SOLVER_FLAG_YUM_OBSOLETES:
1809     solv->do_yum_obsoletes = value;
1810     break;
1811   default:
1812     break;
1813   }
1814   return old;
1815 }
1816
1817 int
1818 cleandeps_check_mistakes(Solver *solv, int level)
1819 {
1820   Pool *pool = solv->pool;
1821   Rule *r;
1822   Id p, pp;
1823   int i;
1824   int mademistake = 0;
1825
1826   if (!solv->cleandepsmap.size)
1827     return 0;
1828   /* check for mistakes */
1829   for (i = solv->installed->start; i < solv->installed->end; i++)
1830     {
1831       if (!MAPTST(&solv->cleandepsmap, i - solv->installed->start))
1832         continue;
1833       r = solv->rules + solv->featurerules + (i - solv->installed->start);
1834       /* a mistake is when the featurerule is true but the updaterule is false */
1835       if (!r->p)
1836         continue;
1837       FOR_RULELITERALS(p, pp, r)
1838         if (p > 0 && solv->decisionmap[p] > 0)
1839           break;
1840       if (!p)
1841         continue;       /* feature rule is not true */
1842       r = solv->rules + solv->updaterules + (i - solv->installed->start);
1843       if (!r->p)
1844         continue;
1845       FOR_RULELITERALS(p, pp, r)
1846         if (p > 0 && solv->decisionmap[p] > 0)
1847           break;
1848       if (p)
1849         continue;       /* update rule is true */
1850       POOL_DEBUG(SOLV_DEBUG_SOLVER, "cleandeps mistake: ");
1851       solver_printruleclass(solv, SOLV_DEBUG_SOLVER, r);
1852       POOL_DEBUG(SOLV_DEBUG_SOLVER, "feature rule: ");
1853       solver_printruleclass(solv, SOLV_DEBUG_SOLVER, solv->rules + solv->featurerules + (i - solv->installed->start));
1854       if (!solv->cleandeps_mistakes)
1855         {
1856           solv->cleandeps_mistakes = solv_calloc(1, sizeof(Queue));
1857           queue_init(solv->cleandeps_mistakes);
1858         }
1859       queue_push(solv->cleandeps_mistakes, i);
1860       MAPCLR(&solv->cleandepsmap, i - solv->installed->start);
1861       solver_reenablepolicyrules_cleandeps(solv, i);
1862       mademistake = 1;
1863     }
1864   if (mademistake)
1865     solver_reset(solv);
1866   return mademistake;
1867 }
1868
1869 static void
1870 prune_to_update_targets(Solver *solv, Id *cp, Queue *q)
1871 {
1872   int i, j;
1873   Id p, *cp2;
1874   for (i = j = 0; i < q->count; i++)
1875     {
1876       p = q->elements[i];
1877       for (cp2 = cp; *cp2; cp2++)
1878         if (*cp2 == p)
1879           {
1880             q->elements[j++] = p;
1881             break;
1882           }
1883     }
1884   queue_truncate(q, j);
1885 }
1886
1887 #ifdef ENABLE_COMPLEX_DEPS
1888
1889 static void
1890 add_complex_recommends(Solver *solv, Id rec, Queue *dq, Map *dqmap)
1891 {
1892   Pool *pool = solv->pool;
1893   int oldcnt = dq->count;
1894   int cutcnt, blkcnt;
1895   Id p;
1896   int i, j;
1897
1898 #if 0
1899   printf("ADD_COMPLEX_RECOMMENDS %s\n", pool_dep2str(pool, rec));
1900 #endif
1901   i = pool_normalize_complex_dep(pool, rec, dq, CPLXDEPS_EXPAND);
1902   if (i == 0 || i == 1)
1903     return;
1904   cutcnt = dq->count;
1905   for (i = oldcnt; i < cutcnt; i++)
1906     {
1907       blkcnt = dq->count;
1908       for (; (p = dq->elements[i]) != 0; i++)
1909         {
1910           if (p < 0)
1911             {
1912               if (solv->decisionmap[-p] <= 0)
1913                 break;
1914               continue;
1915             }
1916           if (solv->decisionmap[p] > 0)
1917             {
1918               queue_truncate(dq, blkcnt);
1919               break;
1920             }
1921           if (dqmap)
1922             {
1923               if (!MAPTST(dqmap, p))
1924                 continue;
1925             }
1926           else
1927             {
1928               if (solv->decisionmap[p] < 0)
1929                 continue;
1930               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))))
1931                 continue;
1932             }
1933           queue_push(dq, p);
1934         }
1935       while (dq->elements[i])
1936         i++;
1937     }
1938   queue_deleten(dq, oldcnt, cutcnt - oldcnt);
1939   /* unify */
1940   if (dq->count != oldcnt)
1941     {
1942       for (j = oldcnt; j < dq->count; j++)
1943         {
1944           p = dq->elements[j];
1945           for (i = 0; i < j; i++)
1946             if (dq->elements[i] == p)
1947               {
1948                 dq->elements[j] = 0;
1949                 break;
1950               }
1951         }
1952       for (i = j = oldcnt; j < dq->count; j++)
1953         if (dq->elements[j])
1954           dq->elements[i++] = dq->elements[j];
1955       queue_truncate(dq, i);
1956     }
1957 #if 0
1958   printf("RETURN:\n");
1959   for (i = oldcnt; i < dq->count; i++)
1960     printf("  - %s\n", pool_solvid2str(pool, dq->elements[i]));
1961 #endif
1962 }
1963
1964 static void
1965 do_complex_recommendations(Solver *solv, Id rec, Map *m, int noselected)
1966 {
1967   Pool *pool = solv->pool;
1968   Queue dq;
1969   Id p;
1970   int i, blk;
1971
1972 #if 0
1973   printf("DO_COMPLEX_RECOMMENDATIONS %s\n", pool_dep2str(pool, rec));
1974 #endif
1975   queue_init(&dq);
1976   i = pool_normalize_complex_dep(pool, rec, &dq, CPLXDEPS_EXPAND);
1977   if (i == 0 || i == 1)
1978     {
1979       queue_free(&dq);
1980       return;
1981     }
1982   for (i = 0; i < dq.count; i++)
1983     {
1984       blk = i;
1985       for (; (p = dq.elements[i]) != 0; i++)
1986         {
1987           if (p < 0)
1988             {
1989               if (solv->decisionmap[-p] <= 0)
1990                 break;
1991               continue;
1992             }
1993           if (solv->decisionmap[p] > 0)
1994             {
1995               if (noselected)
1996                 break;
1997               MAPSET(m, p);
1998               for (i++; (p = dq.elements[i]) != 0; i++)
1999                 if (p > 0 && solv->decisionmap[p] > 0)
2000                   MAPSET(m, p);
2001               p = 1;
2002               break;
2003             }
2004         }
2005       if (!p)
2006         {
2007           for (i = blk; (p = dq.elements[i]) != 0; i++)
2008             if (p > 0)
2009               MAPSET(m, p);
2010         }
2011       while (dq.elements[i])
2012         i++;
2013     }
2014   queue_free(&dq);
2015 }
2016
2017 #endif
2018
2019 /*-------------------------------------------------------------------
2020  *
2021  * solver_run_sat
2022  *
2023  * all rules have been set up, now actually run the solver
2024  *
2025  */
2026
2027 void
2028 solver_run_sat(Solver *solv, int disablerules, int doweak)
2029 {
2030   Queue dq;             /* local decisionqueue */
2031   Queue dqs;            /* local decisionqueue for supplements */
2032   int systemlevel;
2033   int level, olevel;
2034   Rule *r;
2035   int i, j, n;
2036   Solvable *s;
2037   Pool *pool = solv->pool;
2038   Id p, pp, *dp;
2039   int minimizationsteps;
2040   int installedpos = solv->installed ? solv->installed->start : 0;
2041
2042   IF_POOLDEBUG (SOLV_DEBUG_RULE_CREATION)
2043     {
2044       POOL_DEBUG (SOLV_DEBUG_RULE_CREATION, "number of rules: %d\n", solv->nrules);
2045       for (i = 1; i < solv->nrules; i++)
2046         solver_printruleclass(solv, SOLV_DEBUG_RULE_CREATION, solv->rules + i);
2047     }
2048
2049   POOL_DEBUG(SOLV_DEBUG_SOLVER, "initial decisions: %d\n", solv->decisionq.count);
2050
2051   /* start SAT algorithm */
2052   level = 1;
2053   systemlevel = level + 1;
2054   POOL_DEBUG(SOLV_DEBUG_SOLVER, "solving...\n");
2055
2056   queue_init(&dq);
2057   queue_init(&dqs);
2058
2059   /*
2060    * here's the main loop:
2061    * 1) propagate new decisions (only needed once)
2062    * 2) fulfill jobs
2063    * 3) try to keep installed packages
2064    * 4) fulfill all unresolved rules
2065    * 5) install recommended packages
2066    * 6) minimalize solution if we had choices
2067    * if we encounter a problem, we rewind to a safe level and restart
2068    * with step 1
2069    */
2070
2071   minimizationsteps = 0;
2072   for (;;)
2073     {
2074       /*
2075        * initial propagation of the assertions
2076        */
2077       if (level == 1)
2078         {
2079           POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "propagating (propagate_index: %d;  size decisionq: %d)...\n", solv->propagate_index, solv->decisionq.count);
2080           if ((r = propagate(solv, level)) != 0)
2081             {
2082               if (analyze_unsolvable(solv, r, disablerules))
2083                 continue;
2084               level = 0;
2085               break;    /* unsolvable */
2086             }
2087         }
2088
2089       /*
2090        * resolve jobs first (unless focus_installed is set)
2091        */
2092      if (level < systemlevel && !solv->focus_installed)
2093         {
2094           olevel = level;
2095           level = resolve_jobrules(solv, level, disablerules, &dq);
2096           if (level < olevel)
2097             {
2098               if (level == 0)
2099                 break;  /* unsolvable */
2100               continue;
2101             }
2102           systemlevel = level + 1;
2103         }
2104
2105
2106       /*
2107        * installed packages
2108        */
2109       if (!solv->decisioncnt_update)
2110         solv->decisioncnt_update = solv->decisionq.count;
2111       if (level < systemlevel && solv->installed && solv->installed->nsolvables && !solv->installed->disabled)
2112         {
2113           Repo *installed = solv->installed;
2114           int pass;
2115
2116           POOL_DEBUG(SOLV_DEBUG_SOLVER, "resolving installed packages\n");
2117           /* we use two passes if we need to update packages
2118            * to create a better user experience */
2119           for (pass = solv->updatemap.size ? 0 : 1; pass < 2; pass++)
2120             {
2121               int passlevel = level;
2122               Id *specialupdaters = solv->specialupdaters;
2123               if (pass == 1 && !solv->decisioncnt_keep)
2124                 solv->decisioncnt_keep = solv->decisionq.count;
2125               /* start with installedpos, the position that gave us problems the last time */
2126               for (i = installedpos, n = installed->start; n < installed->end; i++, n++)
2127                 {
2128                   Rule *rr;
2129                   Id d;
2130
2131                   if (i == installed->end)
2132                     i = installed->start;
2133                   s = pool->solvables + i;
2134                   if (s->repo != installed)
2135                     continue;
2136
2137                   if (solv->decisionmap[i] > 0 && (!specialupdaters || !specialupdaters[i - installed->start]))
2138                     continue;           /* already decided */
2139                   if (!pass && solv->updatemap.size && !MAPTST(&solv->updatemap, i - installed->start))
2140                     continue;           /* updates first */
2141                   r = solv->rules + solv->updaterules + (i - installed->start);
2142                   rr = r;
2143                   if (!rr->p || rr->d < 0)      /* disabled -> look at feature rule */
2144                     rr -= solv->installed->end - solv->installed->start;
2145                   if (!rr->p)           /* identical to update rule? */
2146                     rr = r;
2147                   if (!rr->p && !(specialupdaters && specialupdaters[i - installed->start]))
2148                     continue;           /* orpaned package */
2149
2150                   /* check if we should update this package to the latest version
2151                    * noupdate is set for erase jobs, in that case we want to deinstall
2152                    * the installed package and not replace it with a newer version
2153                    * rr->p != i is for dup jobs where the installed package cannot be kept */
2154                   queue_empty(&dq);
2155                   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)))
2156                     {
2157                       if (!rr->p)
2158                         {
2159                           /* specialupdater with no update/feature rule */
2160                           for (d = specialupdaters[i - installed->start]; (p = pool->whatprovidesdata[d++]) != 0; )
2161                             {
2162                               if (solv->decisionmap[p] > 0)
2163                                 {
2164                                   dq.count = 0;
2165                                   break;
2166                                 }
2167                               if (!solv->decisionmap[p])
2168                                 queue_push(&dq, p);
2169                             }
2170                         }
2171                       else if (specialupdaters && (d = specialupdaters[i - installed->start]) != 0)
2172                         {
2173                           /* special multiversion handling, make sure best version is chosen */
2174                           if (rr->p == i && solv->decisionmap[i] >= 0)
2175                             queue_push(&dq, i);
2176                           while ((p = pool->whatprovidesdata[d++]) != 0)
2177                             if (solv->decisionmap[p] >= 0)
2178                               queue_push(&dq, p);
2179                           if (dq.count && solv->update_targets && solv->update_targets->elements[i - installed->start])
2180                             prune_to_update_targets(solv, solv->update_targets->elements + solv->update_targets->elements[i - installed->start], &dq);
2181                           if (dq.count)
2182                             {
2183                               policy_filter_unwanted(solv, &dq, POLICY_MODE_CHOOSE);
2184                               p = dq.elements[0];
2185                               if (p != i && solv->decisionmap[p] == 0)
2186                                 {
2187                                   rr = solv->rules + solv->featurerules + (i - solv->installed->start);
2188                                   if (!rr->p)           /* update rule == feature rule? */
2189                                     rr = rr - solv->featurerules + solv->updaterules;
2190                                   dq.count = 1;
2191                                 }
2192                               else
2193                                 dq.count = 0;
2194                             }
2195                         }
2196                       else
2197                         {
2198                           /* update to best package of the update rule */
2199                           FOR_RULELITERALS(p, pp, rr)
2200                             {
2201                               if (solv->decisionmap[p] > 0)
2202                                 {
2203                                   dq.count = 0;         /* already fulfilled */
2204                                   break;
2205                                 }
2206                               if (!solv->decisionmap[p])
2207                                 queue_push(&dq, p);
2208                             }
2209                         }
2210                     }
2211                   if (dq.count && solv->update_targets && solv->update_targets->elements[i - installed->start])
2212                     prune_to_update_targets(solv, solv->update_targets->elements + solv->update_targets->elements[i - installed->start], &dq);
2213                   /* install best version */
2214                   if (dq.count)
2215                     {
2216                       olevel = level;
2217                       level = selectandinstall(solv, level, &dq, disablerules, rr - solv->rules);
2218                       if (level == 0)
2219                         {
2220                           queue_free(&dq);
2221                           queue_free(&dqs);
2222                           return;
2223                         }
2224                       if (level <= olevel)
2225                         {
2226                           if (level == 1 || level < passlevel)
2227                             break;      /* trouble */
2228                           if (level < olevel)
2229                             n = installed->start;       /* redo all */
2230                           i--;
2231                           n--;
2232                           continue;
2233                         }
2234                     }
2235                   /* if still undecided keep package */
2236                   if (solv->decisionmap[i] == 0)
2237                     {
2238                       olevel = level;
2239                       if (solv->cleandepsmap.size && MAPTST(&solv->cleandepsmap, i - installed->start))
2240                         {
2241 #if 0
2242                           POOL_DEBUG(SOLV_DEBUG_POLICY, "cleandeps erasing %s\n", pool_solvid2str(pool, i));
2243                           level = setpropagatelearn(solv, level, -i, disablerules, 0);
2244 #else
2245                           continue;
2246 #endif
2247                         }
2248                       else
2249                         {
2250                           POOL_DEBUG(SOLV_DEBUG_POLICY, "keeping %s\n", pool_solvid2str(pool, i));
2251                           level = setpropagatelearn(solv, level, i, disablerules, r - solv->rules);
2252                         }
2253                       if (level == 0)
2254                         break;
2255                       if (level <= olevel)
2256                         {
2257                           if (level == 1 || level < passlevel)
2258                             break;      /* trouble */
2259                           if (level < olevel)
2260                             n = installed->start;       /* redo all */
2261                           i--;
2262                           n--;
2263                           continue;     /* retry with learnt rule */
2264                         }
2265                     }
2266                 }
2267               if (n < installed->end)
2268                 {
2269                   installedpos = i;     /* retry problem solvable next time */
2270                   break;                /* ran into trouble */
2271                 }
2272               installedpos = installed->start;  /* reset installedpos */
2273             }
2274           if (level == 0)
2275             break;              /* unsolvable */
2276           systemlevel = level + 1;
2277           if (pass < 2)
2278             continue;           /* had trouble, retry */
2279         }
2280       if (!solv->decisioncnt_keep)
2281         solv->decisioncnt_keep = solv->decisionq.count;
2282
2283      if (level < systemlevel && solv->focus_installed)
2284         {
2285           olevel = level;
2286           level = resolve_jobrules(solv, level, disablerules, &dq);
2287           if (level < olevel)
2288             {
2289               if (level == 0)
2290                 break;  /* unsolvable */
2291               continue;
2292             }
2293           systemlevel = level + 1;
2294         }
2295
2296       if (level < systemlevel)
2297         systemlevel = level;
2298
2299       /*
2300        * decide
2301        */
2302       if (!solv->decisioncnt_resolve)
2303         solv->decisioncnt_resolve = solv->decisionq.count;
2304       POOL_DEBUG(SOLV_DEBUG_POLICY, "deciding unresolved rules\n");
2305       for (i = 1, n = 1; n < solv->nrules; i++, n++)
2306         {
2307           if (i == solv->nrules)
2308             i = 1;
2309           r = solv->rules + i;
2310           if (r->d < 0)         /* ignore disabled rules */
2311             continue;
2312           if (r->p < 0)         /* most common cases first */
2313             {
2314               if (r->d == 0 || solv->decisionmap[-r->p] <= 0)
2315                 continue;
2316             }
2317           if (dq.count)
2318             queue_empty(&dq);
2319           if (r->d == 0)
2320             {
2321               /* binary or unary rule */
2322               /* need two positive undecided literals, r->p already checked above */
2323               if (r->w2 <= 0)
2324                 continue;
2325               if (solv->decisionmap[r->p] || solv->decisionmap[r->w2])
2326                 continue;
2327               queue_push(&dq, r->p);
2328               queue_push(&dq, r->w2);
2329             }
2330           else
2331             {
2332               /* make sure that
2333                * all negative literals are installed
2334                * no positive literal is installed
2335                * i.e. the rule is not fulfilled and we
2336                * just need to decide on the positive literals
2337                * (decisionmap[-r->p] for the r->p < 0 case is already checked above)
2338                */
2339               if (r->p >= 0)
2340                 {
2341                   if (solv->decisionmap[r->p] > 0)
2342                     continue;
2343                   if (solv->decisionmap[r->p] == 0)
2344                     queue_push(&dq, r->p);
2345                 }
2346               dp = pool->whatprovidesdata + r->d;
2347               while ((p = *dp++) != 0)
2348                 {
2349                   if (p < 0)
2350                     {
2351                       if (solv->decisionmap[-p] <= 0)
2352                         break;
2353                     }
2354                   else
2355                     {
2356                       if (solv->decisionmap[p] > 0)
2357                         break;
2358                       if (solv->decisionmap[p] == 0)
2359                         queue_push(&dq, p);
2360                     }
2361                 }
2362               if (p)
2363                 continue;
2364             }
2365           IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
2366             {
2367               POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "unfulfilled ");
2368               solver_printruleclass(solv, SOLV_DEBUG_PROPAGATE, r);
2369             }
2370           /* dq.count < 2 cannot happen as this means that
2371            * the rule is unit */
2372           assert(dq.count > 1);
2373
2374           /* prune to cleandeps packages */
2375           if (solv->cleandepsmap.size && solv->installed)
2376             {
2377               Repo *installed = solv->installed;
2378               for (j = 0; j < dq.count; j++)
2379                 if (pool->solvables[dq.elements[j]].repo == installed && MAPTST(&solv->cleandepsmap, dq.elements[j] - installed->start))
2380                   break;
2381               if (j < dq.count)
2382                 {
2383                   dq.elements[0] = dq.elements[j];
2384                   queue_truncate(&dq, 1);
2385                 }
2386             }
2387
2388           olevel = level;
2389           level = selectandinstall(solv, level, &dq, disablerules, r - solv->rules);
2390           if (level == 0)
2391             break;              /* unsolvable */
2392           if (level < systemlevel || level == 1)
2393             break;              /* trouble */
2394           /* something changed, so look at all rules again */
2395           n = 0;
2396         }
2397
2398       if (n != solv->nrules)    /* ran into trouble? */
2399         {
2400           if (level == 0)
2401             break;              /* unsolvable */
2402           continue;             /* start over */
2403         }
2404
2405       /* decide leftover cleandeps packages */
2406       if (solv->cleandepsmap.size && solv->installed)
2407         {
2408           for (p = solv->installed->start; p < solv->installed->end; p++)
2409             {
2410               s = pool->solvables + p;
2411               if (s->repo != solv->installed)
2412                 continue;
2413               if (solv->decisionmap[p] == 0 && MAPTST(&solv->cleandepsmap, p - solv->installed->start))
2414                 {
2415                   POOL_DEBUG(SOLV_DEBUG_POLICY, "cleandeps erasing %s\n", pool_solvid2str(pool, p));
2416                   olevel = level;
2417                   level = setpropagatelearn(solv, level, -p, 0, 0);
2418                   if (level < olevel)
2419                     break;
2420                 }
2421             }
2422           if (p < solv->installed->end)
2423             continue;
2424         }
2425
2426       /* at this point we have a consistent system. now do the extras... */
2427
2428       if (!solv->decisioncnt_weak)
2429         solv->decisioncnt_weak = solv->decisionq.count;
2430       if (doweak)
2431         {
2432           int qcount;
2433
2434           POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended packages\n");
2435           queue_empty(&dq);     /* recommended packages */
2436           queue_empty(&dqs);    /* supplemented packages */
2437           for (i = 1; i < pool->nsolvables; i++)
2438             {
2439               if (solv->decisionmap[i] < 0)
2440                 continue;
2441               if (solv->decisionmap[i] > 0)
2442                 {
2443                   /* installed, check for recommends */
2444                   Id *recp, rec, pp, p;
2445                   s = pool->solvables + i;
2446                   if (!solv->addalreadyrecommended && s->repo == solv->installed)
2447                     continue;
2448                   /* XXX need to special case AND ? */
2449                   if (s->recommends)
2450                     {
2451                       recp = s->repo->idarraydata + s->recommends;
2452                       while ((rec = *recp++) != 0)
2453                         {
2454 #ifdef ENABLE_COMPLEX_DEPS
2455                           if (pool_is_complex_dep(pool, rec))
2456                             {
2457                               add_complex_recommends(solv, rec, &dq, 0);
2458                               continue;
2459                             }
2460 #endif
2461                           qcount = dq.count;
2462                           FOR_PROVIDES(p, pp, rec)
2463                             {
2464                               if (solv->decisionmap[p] > 0)
2465                                 {
2466                                   dq.count = qcount;
2467                                   break;
2468                                 }
2469                               else if (solv->decisionmap[p] == 0)
2470                                 {
2471                                   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))))
2472                                     continue;
2473                                   queue_pushunique(&dq, p);
2474                                 }
2475                             }
2476                         }
2477                     }
2478                 }
2479               else
2480                 {
2481                   s = pool->solvables + i;
2482                   if (!s->supplements)
2483                     continue;
2484                   if (!pool_installable(pool, s))
2485                     continue;
2486                   if (!solver_is_supplementing(solv, s))
2487                     continue;
2488                   if (solv->dupmap_all && solv->installed && s->repo == solv->installed && (solv->droporphanedmap_all || (solv->droporphanedmap.size && MAPTST(&solv->droporphanedmap, i - solv->installed->start))))
2489                     continue;
2490                   queue_push(&dqs, i);
2491                 }
2492             }
2493
2494           /* filter out all packages obsoleted by installed packages */
2495           /* this is no longer needed if we have reverse obsoletes */
2496           if ((dqs.count || dq.count) && solv->installed)
2497             {
2498               Map obsmap;
2499               Id obs, *obsp, po, ppo;
2500
2501               map_init(&obsmap, pool->nsolvables);
2502               for (p = solv->installed->start; p < solv->installed->end; p++)
2503                 {
2504                   s = pool->solvables + p;
2505                   if (s->repo != solv->installed || !s->obsoletes)
2506                     continue;
2507                   if (solv->decisionmap[p] <= 0)
2508                     continue;
2509                   if (solv->multiversion.size && MAPTST(&solv->multiversion, p))
2510                     continue;
2511                   obsp = s->repo->idarraydata + s->obsoletes;
2512                   /* foreach obsoletes */
2513                   while ((obs = *obsp++) != 0)
2514                     FOR_PROVIDES(po, ppo, obs)
2515                       MAPSET(&obsmap, po);
2516                 }
2517               for (i = j = 0; i < dqs.count; i++)
2518                 if (!MAPTST(&obsmap, dqs.elements[i]))
2519                   dqs.elements[j++] = dqs.elements[i];
2520               dqs.count = j;
2521               for (i = j = 0; i < dq.count; i++)
2522                 if (!MAPTST(&obsmap, dq.elements[i]))
2523                   dq.elements[j++] = dq.elements[i];
2524               dq.count = j;
2525               map_free(&obsmap);
2526             }
2527
2528           /* filter out all already supplemented packages if requested */
2529           if (!solv->addalreadyrecommended && dqs.count)
2530             {
2531               int dosplitprovides_old = solv->dosplitprovides;
2532               /* turn off all new packages */
2533               for (i = 0; i < solv->decisionq.count; i++)
2534                 {
2535                   p = solv->decisionq.elements[i];
2536                   if (p < 0)
2537                     continue;
2538                   s = pool->solvables + p;
2539                   if (s->repo && s->repo != solv->installed)
2540                     solv->decisionmap[p] = -solv->decisionmap[p];
2541                 }
2542               solv->dosplitprovides = 0;
2543               /* filter out old supplements */
2544               for (i = j = 0; i < dqs.count; i++)
2545                 {
2546                   p = dqs.elements[i];
2547                   s = pool->solvables + p;
2548                   if (!s->supplements)
2549                     continue;
2550                   if (!solver_is_supplementing(solv, s))
2551                     dqs.elements[j++] = p;
2552                   else if (solv->installsuppdepq && solver_check_installsuppdepq(solv, s))
2553                     dqs.elements[j++] = p;
2554                 }
2555               dqs.count = j;
2556               /* undo turning off */
2557               for (i = 0; i < solv->decisionq.count; i++)
2558                 {
2559                   p = solv->decisionq.elements[i];
2560                   if (p < 0)
2561                     continue;
2562                   s = pool->solvables + p;
2563                   if (s->repo && s->repo != solv->installed)
2564                     solv->decisionmap[p] = -solv->decisionmap[p];
2565                 }
2566               solv->dosplitprovides = dosplitprovides_old;
2567             }
2568
2569           /* multiversion doesn't mix well with supplements.
2570            * filter supplemented packages where we already decided
2571            * to install a different version (see bnc#501088) */
2572           if (dqs.count && solv->multiversion.size)
2573             {
2574               for (i = j = 0; i < dqs.count; i++)
2575                 {
2576                   p = dqs.elements[i];
2577                   if (MAPTST(&solv->multiversion, p))
2578                     {
2579                       Id p2, pp2;
2580                       s = pool->solvables + p;
2581                       FOR_PROVIDES(p2, pp2, s->name)
2582                         if (solv->decisionmap[p2] > 0 && pool->solvables[p2].name == s->name)
2583                           break;
2584                       if (p2)
2585                         continue;       /* ignore this package */
2586                     }
2587                   dqs.elements[j++] = p;
2588                 }
2589               dqs.count = j;
2590             }
2591
2592           /* make dq contain both recommended and supplemented pkgs */
2593           if (dqs.count)
2594             {
2595               for (i = 0; i < dqs.count; i++)
2596                 queue_pushunique(&dq, dqs.elements[i]);
2597             }
2598
2599           if (dq.count)
2600             {
2601               Map dqmap;
2602               int decisioncount = solv->decisionq.count;
2603
2604               if (dq.count == 1)
2605                 {
2606                   /* simple case, just one package. no need to choose to best version */
2607                   p = dq.elements[0];
2608                   if (dqs.count)
2609                     POOL_DEBUG(SOLV_DEBUG_POLICY, "installing supplemented %s\n", pool_solvid2str(pool, p));
2610                   else
2611                     POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended %s\n", pool_solvid2str(pool, p));
2612                   level = setpropagatelearn(solv, level, p, 0, 0);
2613                   if (level == 0)
2614                     break;
2615                   continue;     /* back to main loop */
2616                 }
2617
2618               /* filter packages, this gives us the best versions */
2619               policy_filter_unwanted(solv, &dq, POLICY_MODE_RECOMMEND);
2620
2621               /* create map of result */
2622               map_init(&dqmap, pool->nsolvables);
2623               for (i = 0; i < dq.count; i++)
2624                 MAPSET(&dqmap, dq.elements[i]);
2625
2626               /* install all supplemented packages */
2627               for (i = 0; i < dqs.count; i++)
2628                 {
2629                   p = dqs.elements[i];
2630                   if (solv->decisionmap[p] || !MAPTST(&dqmap, p))
2631                     continue;
2632                   POOL_DEBUG(SOLV_DEBUG_POLICY, "installing supplemented %s\n", pool_solvid2str(pool, p));
2633                   olevel = level;
2634                   level = setpropagatelearn(solv, level, p, 0, 0);
2635                   if (level <= olevel)
2636                     break;
2637                 }
2638               if (i < dqs.count || solv->decisionq.count < decisioncount)
2639                 {
2640                   map_free(&dqmap);
2641                   if (level == 0)
2642                     break;
2643                   continue;
2644                 }
2645
2646               /* install all recommended packages */
2647               /* more work as we want to created branches if multiple
2648                * choices are valid */
2649               for (i = 0; i < decisioncount; i++)
2650                 {
2651                   Id rec, *recp, pp;
2652                   p = solv->decisionq.elements[i];
2653                   if (p < 0)
2654                     continue;
2655                   s = pool->solvables + p;
2656                   if (!s->repo || (!solv->addalreadyrecommended && s->repo == solv->installed))
2657                     continue;
2658                   if (!s->recommends)
2659                     continue;
2660                   recp = s->repo->idarraydata + s->recommends;
2661                   while ((rec = *recp++) != 0)
2662                     {
2663                       queue_empty(&dq);
2664 #ifdef ENABLE_COMPLEX_DEPS
2665                       if (pool_is_complex_dep(pool, rec))
2666                           add_complex_recommends(solv, rec, &dq, &dqmap);
2667                       else
2668 #endif
2669                       FOR_PROVIDES(p, pp, rec)
2670                         {
2671                           if (solv->decisionmap[p] > 0)
2672                             {
2673                               dq.count = 0;
2674                               break;
2675                             }
2676                           else if (solv->decisionmap[p] == 0 && MAPTST(&dqmap, p))
2677                             queue_push(&dq, p);
2678                         }
2679                       if (!dq.count)
2680                         continue;
2681                       if (dq.count > 1)
2682                         {
2683                           /* multiple candidates, open a branch */
2684                           queue_push(&solv->branches, -dq.elements[0]);
2685                           for (i = 1; i < dq.count; i++)
2686                             queue_push(&solv->branches, dq.elements[i]);
2687                           queue_push(&solv->branches, level);
2688                         }
2689                       p = dq.elements[0];
2690                       POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended %s\n", pool_solvid2str(pool, p));
2691                       olevel = level;
2692                       level = setpropagatelearn(solv, level, p, 0, 0);
2693                       if (level <= olevel || solv->decisionq.count < decisioncount)
2694                         break;  /* we had to revert some decisions */
2695                     }
2696                   if (rec)
2697                     break;      /* had a problem above, quit loop */
2698                 }
2699               map_free(&dqmap);
2700               if (level == 0)
2701                 break;
2702               continue;         /* back to main loop so that all deps are checked */
2703             }
2704         }
2705
2706       if (!solv->decisioncnt_orphan)
2707         solv->decisioncnt_orphan = solv->decisionq.count;
2708       if (solv->dupmap_all && solv->installed)
2709         {
2710           int installedone = 0;
2711
2712           /* let's see if we can install some unsupported package */
2713           POOL_DEBUG(SOLV_DEBUG_SOLVER, "deciding orphaned packages\n");
2714           for (i = 0; i < solv->orphaned.count; i++)
2715             {
2716               p = solv->orphaned.elements[i];
2717               if (solv->decisionmap[p])
2718                 continue;       /* already decided */
2719               if (solv->droporphanedmap_all)
2720                 continue;
2721               if (solv->droporphanedmap.size && MAPTST(&solv->droporphanedmap, p - solv->installed->start))
2722                 continue;
2723               POOL_DEBUG(SOLV_DEBUG_SOLVER, "keeping orphaned %s\n", pool_solvid2str(pool, p));
2724               olevel = level;
2725               level = setpropagatelearn(solv, level, p, 0, 0);
2726               installedone = 1;
2727               if (level < olevel)
2728                 break;
2729             }
2730           if (installedone || i < solv->orphaned.count)
2731             {
2732               if (level == 0)
2733                 break;
2734               continue;         /* back to main loop */
2735             }
2736           for (i = 0; i < solv->orphaned.count; i++)
2737             {
2738               p = solv->orphaned.elements[i];
2739               if (solv->decisionmap[p])
2740                 continue;       /* already decided */
2741               POOL_DEBUG(SOLV_DEBUG_SOLVER, "removing orphaned %s\n", pool_solvid2str(pool, p));
2742               olevel = level;
2743               level = setpropagatelearn(solv, level, -p, 0, 0);
2744               if (level < olevel)
2745                 break;
2746             }
2747           if (i < solv->orphaned.count)
2748             {
2749               if (level == 0)
2750                 break;
2751               continue;         /* back to main loop */
2752             }
2753           if (solv->brokenorphanrules)
2754             {
2755               solver_check_brokenorphanrules(solv, &dq);
2756               if (dq.count)
2757                 {
2758                   policy_filter_unwanted(solv, &dq, POLICY_MODE_CHOOSE);
2759                   for (i = 0; i < dq.count; i++)
2760                     {
2761                       p = dq.elements[i];
2762                       POOL_DEBUG(SOLV_DEBUG_POLICY, "installing orphaned dep %s\n", pool_solvid2str(pool, p));
2763                       olevel = level;
2764                       level = setpropagatelearn(solv, level, p, 0, 0);
2765                       if (level < olevel)
2766                         break;
2767                     }
2768                   if (level == 0)
2769                     break;
2770                   continue;
2771                 }
2772             }
2773         }
2774
2775      /* one final pass to make sure we decided all installed packages */
2776       if (solv->installed)
2777         {
2778           for (p = solv->installed->start; p < solv->installed->end; p++)
2779             {
2780               if (solv->decisionmap[p])
2781                 continue;       /* already decided */
2782               s = pool->solvables + p;
2783               if (s->repo != solv->installed)
2784                 continue;
2785               POOL_DEBUG(SOLV_DEBUG_SOLVER, "removing unwanted %s\n", pool_solvid2str(pool, p));
2786               olevel = level;
2787               level = setpropagatelearn(solv, level, -p, 0, 0);
2788               if (level < olevel)
2789                 break;
2790             }
2791           if (p < solv->installed->end)
2792             {
2793               if (level == 0)
2794                 break;
2795               continue;         /* back to main loop */
2796             }
2797         }
2798
2799       if (solv->installed && solv->cleandepsmap.size)
2800         {
2801           if (cleandeps_check_mistakes(solv, level))
2802             {
2803               level = 1;        /* restart from scratch */
2804               systemlevel = level + 1;
2805               continue;
2806             }
2807         }
2808
2809       if (solv->solution_callback)
2810         {
2811           solv->solution_callback(solv, solv->solution_callback_data);
2812           if (solv->branches.count)
2813             {
2814               int l, endi = 0;
2815               Id why;
2816               p = l = 0;
2817               for (i = solv->branches.count - 1; i >= 0; i--)
2818                 {
2819                   p = solv->branches.elements[i];
2820                   if (p > 0 && !l)
2821                     {
2822                       endi = i + 1;
2823                       l = p;
2824                     }
2825                   else if (p > 0)
2826                     break;
2827                   else if (p < 0)
2828                     l = 0;
2829                 }
2830               if (i >= 0)
2831                 {
2832                   while (i > 0 && solv->branches.elements[i - 1] > 0)
2833                     i--;
2834                   p = solv->branches.elements[i];
2835                   solv->branches.elements[i] = -p;
2836                   while (i > 0 && solv->branches.elements[i - 1] < 0)
2837                     i--;
2838                   POOL_DEBUG(SOLV_DEBUG_SOLVER, "branching with %s\n", pool_solvid2str(pool, p));
2839                   queue_empty(&dq);
2840                   queue_insertn(&dq, 0, endi - i, solv->branches.elements + i);
2841                   level = l;
2842                   revert(solv, level);
2843                   queue_insertn(&solv->branches, solv->branches.count, dq.count, dq.elements);
2844                   /* hack: revert simply sets the count, so we can still access the reverted elements */
2845                   why = -solv->decisionq_why.elements[solv->decisionq_why.count];
2846                   assert(why >= 0);
2847                   olevel = level;
2848                   level = setpropagatelearn(solv, level, p, disablerules, why);
2849                   if (level == 0)
2850                     break;
2851                   continue;
2852                 }
2853             }
2854           /* all branches done, we're finally finished */
2855           break;
2856         }
2857
2858       /* auto-minimization step */
2859       if (solv->branches.count)
2860         {
2861           int l = 0, lasti = -1, lastsi = -1, endi = 0;
2862           Id why;
2863           p = l = 0;
2864           if (solv->recommends_index < solv->decisionq.count)
2865             policy_update_recommendsmap(solv);
2866           for (i = solv->branches.count - 1; i >= 0; i--)
2867             {
2868               p = solv->branches.elements[i];
2869               if (p > 0 && !l)
2870                 {
2871                   l = p;
2872                   endi = i + 1;
2873                   lastsi = -1;
2874                 }
2875               else if (p > 0)
2876                 {
2877                   if (solv->decisionmap[p] > l + 1)
2878                     lasti = i;
2879                   else
2880                     {
2881                       if (MAPTST(&solv->recommendsmap, p) || solver_is_supplementing(solv, pool->solvables + p))
2882                         {
2883                           lastsi = p;
2884                         }
2885                     }
2886                 }
2887               else if (p < 0)
2888                 {
2889                   l = 0;
2890                   if (lastsi >= 0)
2891                     {
2892                       p = -p;
2893                       if (solv->decisionmap[p] == l)
2894                         {
2895                           if (!(MAPTST(&solv->recommendsmap, p) || solver_is_supplementing(solv, pool->solvables + p)))
2896                             lasti = lastsi;
2897                         }
2898                     }
2899                 }
2900             }
2901           if (lasti >= 0)
2902             {
2903               int starti;
2904               /* find start of branch */
2905               for (i = lasti; i && solv->branches.elements[i] >= 0; )
2906                 i--;
2907               while (i > 0 && solv->branches.elements[i] < 0)
2908                 i--;
2909               starti = i ? i + 1 : 0;
2910 #if 0
2911               printf("minimization group level %d [%d-%d]:\n", solv->branches.elements[endi - 1], starti, endi);
2912               for (i = starti; i < endi - 1; i++)
2913                 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]));
2914 #endif
2915               l = solv->branches.elements[endi - 1];
2916               p = solv->branches.elements[lasti];
2917               solv->branches.elements[lasti] = -p;
2918               POOL_DEBUG(SOLV_DEBUG_SOLVER, "minimizing %d -> %d with %s\n", solv->decisionmap[p], l, pool_solvid2str(pool, p));
2919               minimizationsteps++;
2920               queue_empty(&dq);
2921               for (i = starti; i < endi - 1; i++)
2922                 if (solv->branches.elements[i] < 0)
2923                   queue_push(&dq, solv->branches.elements[i]);
2924               for (i = starti; i < endi; i++)
2925                 if (solv->branches.elements[i] > 0)
2926                   queue_push(&dq, solv->branches.elements[i]);
2927               if (dq.elements[dq.count - 2] <= 0)
2928                 queue_empty(&dq);
2929               level = l;
2930               revert(solv, level);
2931               queue_insertn(&solv->branches, solv->branches.count, dq.count, dq.elements);
2932               /* hack: revert simply sets the count, so we can still access the reverted elements */
2933               why = -solv->decisionq_why.elements[solv->decisionq_why.count];
2934               assert(why >= 0);
2935               olevel = level;
2936               level = setpropagatelearn(solv, level, p, disablerules, why);
2937               if (level == 0)
2938                 break;
2939               continue;         /* back to main loop */
2940             }
2941         }
2942       /* no minimization found, we're finally finished! */
2943       break;
2944     }
2945
2946   POOL_DEBUG(SOLV_DEBUG_STATS, "solver statistics: %d learned rules, %d unsolvable, %d minimization steps\n", solv->stats_learned, solv->stats_unsolvable, minimizationsteps);
2947
2948   POOL_DEBUG(SOLV_DEBUG_STATS, "done solving.\n\n");
2949   queue_free(&dq);
2950   queue_free(&dqs);
2951   if (level == 0)
2952     {
2953       /* unsolvable */
2954       solv->decisioncnt_jobs = solv->decisionq.count;
2955       solv->decisioncnt_update = solv->decisionq.count;
2956       solv->decisioncnt_keep = solv->decisionq.count;
2957       solv->decisioncnt_resolve = solv->decisionq.count;
2958       solv->decisioncnt_weak = solv->decisionq.count;
2959       solv->decisioncnt_orphan = solv->decisionq.count;
2960     }
2961 #if 0
2962   solver_printdecisionq(solv, SOLV_DEBUG_RESULT);
2963 #endif
2964 }
2965
2966
2967 /*-------------------------------------------------------------------
2968  *
2969  * remove disabled conflicts
2970  *
2971  * purpose: update the decisionmap after some rules were disabled.
2972  * this is used to calculate the suggested/recommended package list.
2973  * Also returns a "removed" list to undo the discisionmap changes.
2974  */
2975
2976 static void
2977 removedisabledconflicts(Solver *solv, Queue *removed)
2978 {
2979   Pool *pool = solv->pool;
2980   int i, n;
2981   Id p, why, *dp;
2982   Id new;
2983   Rule *r;
2984   Id *decisionmap = solv->decisionmap;
2985
2986   queue_empty(removed);
2987   for (i = 0; i < solv->decisionq.count; i++)
2988     {
2989       p = solv->decisionq.elements[i];
2990       if (p > 0)
2991         continue;       /* conflicts only, please */
2992       why = solv->decisionq_why.elements[i];
2993       if (why == 0)
2994         {
2995           /* no rule involved, must be a orphan package drop */
2996           continue;
2997         }
2998       /* we never do conflicts on free decisions, so there
2999        * must have been an unit rule */
3000       assert(why > 0);
3001       r = solv->rules + why;
3002       if (r->d < 0 && decisionmap[-p])
3003         {
3004           /* rule is now disabled, remove from decisionmap */
3005           POOL_DEBUG(SOLV_DEBUG_SOLVER, "removing conflict for package %s[%d]\n", pool_solvid2str(pool, -p), -p);
3006           queue_push(removed, -p);
3007           queue_push(removed, decisionmap[-p]);
3008           decisionmap[-p] = 0;
3009         }
3010     }
3011   if (!removed->count)
3012     return;
3013   /* we removed some confliced packages. some of them might still
3014    * be in conflict, so search for unit rules and re-conflict */
3015   new = 0;
3016   for (i = n = 1, r = solv->rules + i; n < solv->nrules; i++, r++, n++)
3017     {
3018       if (i == solv->nrules)
3019         {
3020           i = 1;
3021           r = solv->rules + i;
3022         }
3023       if (r->d < 0)
3024         continue;
3025       if (!r->w2)
3026         {
3027           if (r->p < 0 && !decisionmap[-r->p])
3028             new = r->p;
3029         }
3030       else if (!r->d)
3031         {
3032           /* binary rule */
3033           if (r->p < 0 && decisionmap[-r->p] == 0 && DECISIONMAP_FALSE(r->w2))
3034             new = r->p;
3035           else if (r->w2 < 0 && decisionmap[-r->w2] == 0 && DECISIONMAP_FALSE(r->p))
3036             new = r->w2;
3037         }
3038       else
3039         {
3040           if (r->p < 0 && decisionmap[-r->p] == 0)
3041             new = r->p;
3042           if (new || DECISIONMAP_FALSE(r->p))
3043             {
3044               dp = pool->whatprovidesdata + r->d;
3045               while ((p = *dp++) != 0)
3046                 {
3047                   if (new && p == new)
3048                     continue;
3049                   if (p < 0 && decisionmap[-p] == 0)
3050                     {
3051                       if (new)
3052                         {
3053                           new = 0;
3054                           break;
3055                         }
3056                       new = p;
3057                     }
3058                   else if (!DECISIONMAP_FALSE(p))
3059                     {
3060                       new = 0;
3061                       break;
3062                     }
3063                 }
3064             }
3065         }
3066       if (new)
3067         {
3068           POOL_DEBUG(SOLV_DEBUG_SOLVER, "re-conflicting package %s[%d]\n", pool_solvid2str(pool, -new), -new);
3069           decisionmap[-new] = -1;
3070           new = 0;
3071           n = 0;        /* redo all rules */
3072         }
3073     }
3074 }
3075
3076 static inline void
3077 undo_removedisabledconflicts(Solver *solv, Queue *removed)
3078 {
3079   int i;
3080   for (i = 0; i < removed->count; i += 2)
3081     solv->decisionmap[removed->elements[i]] = removed->elements[i + 1];
3082 }
3083
3084
3085 /*-------------------------------------------------------------------
3086  *
3087  * weaken solvable dependencies
3088  */
3089
3090 static void
3091 weaken_solvable_deps(Solver *solv, Id p)
3092 {
3093   int i;
3094   Rule *r;
3095
3096   for (i = 1, r = solv->rules + i; i < solv->rpmrules_end; i++, r++)
3097     {
3098       if (r->p != -p)
3099         continue;
3100       if ((r->d == 0 || r->d == -1) && r->w2 < 0)
3101         continue;       /* conflict */
3102       queue_push(&solv->weakruleq, i);
3103     }
3104 }
3105
3106
3107 /********************************************************************/
3108 /* main() */
3109
3110
3111 void
3112 solver_calculate_multiversionmap(Pool *pool, Queue *job, Map *multiversionmap)
3113 {
3114   int i;
3115   Id how, what, select;
3116   Id p, pp;
3117   for (i = 0; i < job->count; i += 2)
3118     {
3119       how = job->elements[i];
3120       if ((how & SOLVER_JOBMASK) != SOLVER_MULTIVERSION)
3121         continue;
3122       what = job->elements[i + 1];
3123       select = how & SOLVER_SELECTMASK;
3124       if (!multiversionmap->size)
3125         map_grow(multiversionmap, pool->nsolvables);
3126       if (select == SOLVER_SOLVABLE_ALL)
3127         {
3128           FOR_POOL_SOLVABLES(p)
3129             MAPSET(multiversionmap, p);
3130         }
3131       else if (select == SOLVER_SOLVABLE_REPO)
3132         {
3133           Solvable *s;
3134           Repo *repo = pool_id2repo(pool, what);
3135           if (repo)
3136             FOR_REPO_SOLVABLES(repo, p, s)
3137               MAPSET(multiversionmap, p);
3138         }
3139       FOR_JOB_SELECT(p, pp, select, what)
3140         MAPSET(multiversionmap, p);
3141     }
3142 }
3143
3144 void
3145 solver_calculate_noobsmap(Pool *pool, Queue *job, Map *multiversionmap)
3146 {
3147   solver_calculate_multiversionmap(pool, job, multiversionmap);
3148 }
3149
3150 /*
3151  * add a rule created by a job, record job number and weak flag
3152  */
3153 static inline void
3154 solver_addjobrule(Solver *solv, Id p, Id d, Id job, int weak)
3155 {
3156   solver_addrule(solv, p, d);
3157   queue_push(&solv->ruletojob, job);
3158   if (weak)
3159     queue_push(&solv->weakruleq, solv->nrules - 1);
3160 }
3161
3162 static inline void
3163 add_cleandeps_package(Solver *solv, Id p)
3164 {
3165   if (!solv->cleandeps_updatepkgs)
3166     {
3167       solv->cleandeps_updatepkgs = solv_calloc(1, sizeof(Queue));
3168       queue_init(solv->cleandeps_updatepkgs);
3169     }
3170   queue_pushunique(solv->cleandeps_updatepkgs, p);
3171 }
3172
3173 static void
3174 add_update_target(Solver *solv, Id p, Id how)
3175 {
3176   Pool *pool = solv->pool;
3177   Solvable *s = pool->solvables + p;
3178   Repo *installed = solv->installed;
3179   Id pi, pip;
3180   if (!solv->update_targets)
3181     {
3182       solv->update_targets = solv_calloc(1, sizeof(Queue));
3183       queue_init(solv->update_targets);
3184     }
3185   if (s->repo == installed)
3186     {
3187       queue_push2(solv->update_targets, p, p);
3188       return;
3189     }
3190   FOR_PROVIDES(pi, pip, s->name)
3191     {
3192       Solvable *si = pool->solvables + pi;
3193       if (si->repo != installed || si->name != s->name)
3194         continue;
3195       if (how & SOLVER_FORCEBEST)
3196         {
3197           if (!solv->bestupdatemap.size)
3198             map_grow(&solv->bestupdatemap, installed->end - installed->start);
3199           MAPSET(&solv->bestupdatemap, pi - installed->start);
3200         }
3201       if (how & SOLVER_CLEANDEPS)
3202         add_cleandeps_package(solv, pi);
3203       queue_push2(solv->update_targets, pi, p);
3204       /* check if it's ok to keep the installed package */
3205       if (s->evr == si->evr && solvable_identical(s, si))
3206         queue_push2(solv->update_targets, pi, pi);
3207     }
3208   if (s->obsoletes)
3209     {
3210       Id obs, *obsp = s->repo->idarraydata + s->obsoletes;
3211       while ((obs = *obsp++) != 0)
3212         {
3213           FOR_PROVIDES(pi, pip, obs)
3214             {
3215               Solvable *si = pool->solvables + pi;
3216               if (si->repo != installed)
3217                 continue;
3218               if (si->name == s->name)
3219                 continue;       /* already handled above */
3220               if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, si, obs))
3221                 continue;
3222               if (pool->obsoleteusescolors && !pool_colormatch(pool, s, si))
3223                 continue;
3224               if (how & SOLVER_FORCEBEST)
3225                 {
3226                   if (!solv->bestupdatemap.size)
3227                     map_grow(&solv->bestupdatemap, installed->end - installed->start);
3228                   MAPSET(&solv->bestupdatemap, pi - installed->start);
3229                 }
3230               if (how & SOLVER_CLEANDEPS)
3231                 add_cleandeps_package(solv, pi);
3232               queue_push2(solv->update_targets, pi, p);
3233             }
3234         }
3235     }
3236 }
3237
3238 static int
3239 transform_update_targets_sortfn(const void *ap, const void *bp, void *dp)
3240 {
3241   const Id *a = ap;
3242   const Id *b = bp;
3243   if (a[0] - b[0])
3244     return a[0] - b[0];
3245   return a[1] - b[1];
3246 }
3247
3248 static void
3249 transform_update_targets(Solver *solv)
3250 {
3251   Repo *installed = solv->installed;
3252   Queue *update_targets = solv->update_targets;
3253   int i, j;
3254   Id p, q, lastp, lastq;
3255
3256   if (!update_targets->count)
3257     {
3258       queue_free(update_targets);
3259       solv->update_targets = solv_free(update_targets);
3260       return;
3261     }
3262   if (update_targets->count > 2)
3263     solv_sort(update_targets->elements, update_targets->count >> 1, 2 * sizeof(Id), transform_update_targets_sortfn, solv);
3264   queue_insertn(update_targets, 0, installed->end - installed->start, 0);
3265   lastp = lastq = 0;
3266   for (i = j = installed->end - installed->start; i < update_targets->count; i += 2)
3267     {
3268       if ((p = update_targets->elements[i]) != lastp)
3269         {
3270           if (!solv->updatemap.size)
3271             map_grow(&solv->updatemap, installed->end - installed->start);
3272           MAPSET(&solv->updatemap, p - installed->start);
3273           update_targets->elements[j++] = 0;                    /* finish old set */
3274           update_targets->elements[p - installed->start] = j;   /* start new set */
3275           lastp = p;
3276           lastq = 0;
3277         }
3278       if ((q = update_targets->elements[i + 1]) != lastq)
3279         {
3280           update_targets->elements[j++] = q;
3281           lastq = q;
3282         }
3283     }
3284   queue_truncate(update_targets, j);
3285   queue_push(update_targets, 0);        /* finish last set */
3286 }
3287
3288
3289 static void
3290 addedmap2deduceq(Solver *solv, Map *addedmap)
3291 {
3292   Pool *pool = solv->pool;
3293   int i, j;
3294   Id p;
3295   Rule *r;
3296
3297   queue_empty(&solv->addedmap_deduceq);
3298   for (i = 2, j = solv->rpmrules_end - 1; i < pool->nsolvables && j > 0; j--)
3299     {
3300       r = solv->rules + j;
3301       if (r->p >= 0)
3302         continue;
3303       if ((r->d == 0 || r->d == -1) && r->w2 < 0)
3304         continue;
3305       p = -r->p;
3306       if (!MAPTST(addedmap, p))
3307         {
3308           /* should never happen, but... */
3309           if (!solv->addedmap_deduceq.count || solv->addedmap_deduceq.elements[solv->addedmap_deduceq.count - 1] != -p)
3310             queue_push(&solv->addedmap_deduceq, -p);
3311           continue;
3312         }
3313       for (; i < p; i++)
3314         if (MAPTST(addedmap, i))
3315           queue_push(&solv->addedmap_deduceq, i);
3316       if (i == p)
3317         i++;
3318     }
3319   for (; i < pool->nsolvables; i++)
3320     if (MAPTST(addedmap, i))
3321       queue_push(&solv->addedmap_deduceq, i);
3322   j = 0;
3323   for (i = 2; i < pool->nsolvables; i++)
3324     if (MAPTST(addedmap, i))
3325       j++;
3326 }
3327
3328 static void
3329 deduceq2addedmap(Solver *solv, Map *addedmap)
3330 {
3331   int j;
3332   Id p;
3333   Rule *r;
3334   for (j = solv->rpmrules_end - 1; j > 0; j--)
3335     {
3336       r = solv->rules + j;
3337       if (r->d < 0 && r->p)
3338         solver_enablerule(solv, r);
3339       if (r->p >= 0)
3340         continue;
3341       if ((r->d == 0 || r->d == -1) && r->w2 < 0)
3342         continue;
3343       p = -r->p;
3344       MAPSET(addedmap, p);
3345     }
3346   for (j = 0; j < solv->addedmap_deduceq.count; j++)
3347     {
3348       p = solv->addedmap_deduceq.elements[j];
3349       if (p > 0)
3350         MAPSET(addedmap, p);
3351       else
3352         MAPCLR(addedmap, p);
3353     }
3354 }
3355
3356
3357 /*
3358  *
3359  * solve job queue
3360  *
3361  */
3362
3363 int
3364 solver_solve(Solver *solv, Queue *job)
3365 {
3366   Pool *pool = solv->pool;
3367   Repo *installed = solv->installed;
3368   int i;
3369   int oldnrules, initialnrules;
3370   Map addedmap;                /* '1' == have rpm-rules for solvable */
3371   Map installcandidatemap;
3372   Id how, what, select, name, weak, p, pp, d;
3373   Queue q;
3374   Solvable *s;
3375   Rule *r;
3376   int now, solve_start;
3377   int hasdupjob = 0;
3378   int hasbestinstalljob = 0;
3379
3380   solve_start = solv_timems(0);
3381
3382   /* log solver options */
3383   POOL_DEBUG(SOLV_DEBUG_STATS, "solver started\n");
3384   POOL_DEBUG(SOLV_DEBUG_STATS, "dosplitprovides=%d, noupdateprovide=%d, noinfarchcheck=%d\n", solv->dosplitprovides, solv->noupdateprovide, solv->noinfarchcheck);
3385   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);
3386   POOL_DEBUG(SOLV_DEBUG_STATS, "promoteepoch=%d, forbidselfconflicts=%d\n", pool->promoteepoch, pool->forbidselfconflicts);
3387   POOL_DEBUG(SOLV_DEBUG_STATS, "obsoleteusesprovides=%d, implicitobsoleteusesprovides=%d, obsoleteusescolors=%d, implicitobsoleteusescolors=%d\n", pool->obsoleteusesprovides, pool->implicitobsoleteusesprovides, pool->obsoleteusescolors, pool->implicitobsoleteusescolors);
3388   POOL_DEBUG(SOLV_DEBUG_STATS, "dontinstallrecommended=%d, addalreadyrecommended=%d\n", solv->dontinstallrecommended, solv->addalreadyrecommended);
3389
3390   /* create whatprovides if not already there */
3391   if (!pool->whatprovides)
3392     pool_createwhatprovides(pool);
3393
3394   /* create obsolete index */
3395   policy_create_obsolete_index(solv);
3396
3397   /* remember job */
3398   queue_free(&solv->job);
3399   queue_init_clone(&solv->job, job);
3400   solv->pooljobcnt = pool->pooljobs.count;
3401   if (pool->pooljobs.count)
3402     queue_insertn(&solv->job, 0, pool->pooljobs.count, pool->pooljobs.elements);
3403   job = &solv->job;
3404
3405   /* free old stuff in jase we re-run a solver */
3406   queuep_free(&solv->update_targets);
3407   queuep_free(&solv->cleandeps_updatepkgs);
3408   queue_empty(&solv->ruleassertions);
3409   solv->bestrules_pkg = solv_free(solv->bestrules_pkg);
3410   solv->yumobsrules_info = solv_free(solv->yumobsrules_info);
3411   solv->choicerules_ref = solv_free(solv->choicerules_ref);
3412   if (solv->noupdate.size)
3413     map_empty(&solv->noupdate);
3414   map_zerosize(&solv->multiversion);
3415   solv->updatemap_all = 0;
3416   map_zerosize(&solv->updatemap);
3417   solv->bestupdatemap_all = 0;
3418   map_zerosize(&solv->bestupdatemap);
3419   solv->fixmap_all = 0;
3420   map_zerosize(&solv->fixmap);
3421   solv->dupmap_all = 0;
3422   map_zerosize(&solv->dupmap);
3423   map_zerosize(&solv->dupinvolvedmap);
3424   solv->droporphanedmap_all = 0;
3425   map_zerosize(&solv->droporphanedmap);
3426   map_zerosize(&solv->cleandepsmap);
3427   map_zerosize(&solv->weakrulemap);
3428   queue_empty(&solv->weakruleq);
3429   solv->watches = solv_free(solv->watches);
3430   queue_empty(&solv->ruletojob);
3431   if (solv->decisionq.count)
3432     memset(solv->decisionmap, 0, pool->nsolvables * sizeof(Id));
3433   queue_empty(&solv->decisionq);
3434   queue_empty(&solv->decisionq_why);
3435   solv->decisioncnt_jobs = solv->decisioncnt_update = solv->decisioncnt_keep = solv->decisioncnt_resolve = solv->decisioncnt_weak = solv->decisioncnt_orphan = 0;
3436   queue_empty(&solv->learnt_why);
3437   queue_empty(&solv->learnt_pool);
3438   queue_empty(&solv->branches);
3439   solv->propagate_index = 0;
3440   queue_empty(&solv->problems);
3441   queue_empty(&solv->solutions);
3442   queue_empty(&solv->orphaned);
3443   solv->stats_learned = solv->stats_unsolvable = 0;
3444   if (solv->recommends_index)
3445     {
3446       map_empty(&solv->recommendsmap);
3447       map_empty(&solv->suggestsmap);
3448       queuep_free(&solv->recommendscplxq);
3449       queuep_free(&solv->suggestscplxq);
3450       solv->recommends_index = 0;
3451     }
3452   queuep_free(&solv->brokenorphanrules);
3453   solv->specialupdaters = solv_free(solv->specialupdaters);
3454
3455
3456   /*
3457    * create basic rule set of all involved packages
3458    * use addedmap bitmap to make sure we don't create rules twice
3459    */
3460
3461   /* create multiversion map if needed */
3462   solver_calculate_multiversionmap(pool, job, &solv->multiversion);
3463
3464   map_init(&addedmap, pool->nsolvables);
3465   MAPSET(&addedmap, SYSTEMSOLVABLE);
3466
3467   map_init(&installcandidatemap, pool->nsolvables);
3468   queue_init(&q);
3469
3470   now = solv_timems(0);
3471   /*
3472    * create rules for all package that could be involved with the solving
3473    * so called: rpm rules
3474    *
3475    */
3476   initialnrules = solv->rpmrules_end ? solv->rpmrules_end : 1;
3477   if (initialnrules > 1)
3478     deduceq2addedmap(solv, &addedmap);
3479   if (solv->nrules != initialnrules)
3480     solver_shrinkrules(solv, initialnrules);
3481   solv->nrules = initialnrules;
3482   solv->rpmrules_end = 0;
3483
3484   if (installed)
3485     {
3486       /* check for update/verify jobs as they need to be known early */
3487       /* also setup the droporphaned map, we need it when creating update rules */
3488       for (i = 0; i < job->count; i += 2)
3489         {
3490           how = job->elements[i];
3491           what = job->elements[i + 1];
3492           select = how & SOLVER_SELECTMASK;
3493           switch (how & SOLVER_JOBMASK)
3494             {
3495             case SOLVER_VERIFY:
3496               if (select == SOLVER_SOLVABLE_ALL || (select == SOLVER_SOLVABLE_REPO && installed && what == installed->repoid))
3497                 solv->fixmap_all = 1;
3498               FOR_JOB_SELECT(p, pp, select, what)
3499                 {
3500                   s = pool->solvables + p;
3501                   if (s->repo != installed)
3502                     continue;
3503                   if (!solv->fixmap.size)
3504                     map_grow(&solv->fixmap, installed->end - installed->start);
3505                   MAPSET(&solv->fixmap, p - installed->start);
3506                 }
3507               break;
3508             case SOLVER_UPDATE:
3509               if (select == SOLVER_SOLVABLE_ALL)
3510                 {
3511                   solv->updatemap_all = 1;
3512                   if (how & SOLVER_FORCEBEST)
3513                     solv->bestupdatemap_all = 1;
3514                   if (how & SOLVER_CLEANDEPS)
3515                     {
3516                       FOR_REPO_SOLVABLES(installed, p, s)
3517                         add_cleandeps_package(solv, p);
3518                     }
3519                 }
3520               else if (select == SOLVER_SOLVABLE_REPO)
3521                 {
3522                   Repo *repo = pool_id2repo(pool, what);
3523                   if (!repo)
3524                     break;
3525                   if (repo == installed && !(how & SOLVER_TARGETED))
3526                     {
3527                       solv->updatemap_all = 1;
3528                       if (how & SOLVER_FORCEBEST)
3529                         solv->bestupdatemap_all = 1;
3530                       if (how & SOLVER_CLEANDEPS)
3531                         {
3532                           FOR_REPO_SOLVABLES(installed, p, s)
3533                             add_cleandeps_package(solv, p);
3534                         }
3535                       break;
3536                     }
3537                   if (solv->noautotarget && !(how & SOLVER_TARGETED))
3538                     break;
3539                   /* targeted update */
3540                   FOR_REPO_SOLVABLES(repo, p, s)
3541                     add_update_target(solv, p, how);
3542                 }
3543               else
3544                 {
3545                   if (!(how & SOLVER_TARGETED))
3546                     {
3547                       int targeted = 1;
3548                       FOR_JOB_SELECT(p, pp, select, what)
3549                         {
3550                           s = pool->solvables + p;
3551                           if (s->repo != installed)
3552                             continue;
3553                           if (!solv->updatemap.size)
3554                             map_grow(&solv->updatemap, installed->end - installed->start);
3555                           MAPSET(&solv->updatemap, p - installed->start);
3556                           if (how & SOLVER_FORCEBEST)
3557                             {
3558                               if (!solv->bestupdatemap.size)
3559                                 map_grow(&solv->bestupdatemap, installed->end - installed->start);
3560                               MAPSET(&solv->bestupdatemap, p - installed->start);
3561                             }
3562                           if (how & SOLVER_CLEANDEPS)
3563                             add_cleandeps_package(solv, p);
3564                           targeted = 0;
3565                         }
3566                       if (!targeted || solv->noautotarget)
3567                         break;
3568                     }
3569                   FOR_JOB_SELECT(p, pp, select, what)
3570                     add_update_target(solv, p, how);
3571                 }
3572               break;
3573             case SOLVER_DROP_ORPHANED:
3574               if (select == SOLVER_SOLVABLE_ALL || (select == SOLVER_SOLVABLE_REPO && what == installed->repoid))
3575                 solv->droporphanedmap_all = 1;
3576               FOR_JOB_SELECT(p, pp, select, what)
3577                 {
3578                   s = pool->solvables + p;
3579                   if (s->repo != installed)
3580                     continue;
3581                   if (!solv->droporphanedmap.size)
3582                     map_grow(&solv->droporphanedmap, installed->end - installed->start);
3583                   MAPSET(&solv->droporphanedmap, p - installed->start);
3584                 }
3585               break;
3586             default:
3587               break;
3588             }
3589         }
3590
3591       if (solv->update_targets)
3592         transform_update_targets(solv);
3593
3594       oldnrules = solv->nrules;
3595       FOR_REPO_SOLVABLES(installed, p, s)
3596         solver_addrpmrulesforsolvable(solv, s, &addedmap);
3597       POOL_DEBUG(SOLV_DEBUG_STATS, "added %d rpm rules for installed solvables\n", solv->nrules - oldnrules);
3598       oldnrules = solv->nrules;
3599       FOR_REPO_SOLVABLES(installed, p, s)
3600         solver_addrpmrulesforupdaters(solv, s, &addedmap, 1);
3601       POOL_DEBUG(SOLV_DEBUG_STATS, "added %d rpm rules for updaters of installed solvables\n", solv->nrules - oldnrules);
3602     }
3603
3604   /*
3605    * create rules for all packages involved in the job
3606    * (to be installed or removed)
3607    */
3608
3609   oldnrules = solv->nrules;
3610   for (i = 0; i < job->count; i += 2)
3611     {
3612       how = job->elements[i];
3613       what = job->elements[i + 1];
3614       select = how & SOLVER_SELECTMASK;
3615
3616       switch (how & SOLVER_JOBMASK)
3617         {
3618         case SOLVER_INSTALL:
3619           FOR_JOB_SELECT(p, pp, select, what)
3620             {
3621               MAPSET(&installcandidatemap, p);
3622               solver_addrpmrulesforsolvable(solv, pool->solvables + p, &addedmap);
3623             }
3624           break;
3625         case SOLVER_DISTUPGRADE:
3626           if (select == SOLVER_SOLVABLE_ALL)
3627             {
3628               solv->dupmap_all = 1;
3629               solv->updatemap_all = 1;
3630               if (how & SOLVER_FORCEBEST)
3631                 solv->bestupdatemap_all = 1;
3632             }
3633           if (!solv->dupmap_all)
3634             hasdupjob = 1;
3635           break;
3636         default:
3637           break;
3638         }
3639     }
3640   POOL_DEBUG(SOLV_DEBUG_STATS, "added %d rpm rules for packages involved in a job\n", solv->nrules - oldnrules);
3641
3642
3643   /*
3644    * add rules for suggests, enhances
3645    */
3646   oldnrules = solv->nrules;
3647   solver_addrpmrulesforweak(solv, &addedmap);
3648   POOL_DEBUG(SOLV_DEBUG_STATS, "added %d rpm rules because of weak dependencies\n", solv->nrules - oldnrules);
3649
3650 #ifdef ENABLE_LINKED_PKGS
3651   oldnrules = solv->nrules;
3652   solver_addrpmrulesforlinked(solv, &addedmap);
3653   POOL_DEBUG(SOLV_DEBUG_STATS, "added %d rpm rules because of linked packages\n", solv->nrules - oldnrules);
3654 #endif
3655
3656   /*
3657    * first pass done, we now have all the rpm rules we need.
3658    * unify existing rules before going over all job rules and
3659    * policy rules.
3660    * at this point the system is always solvable,
3661    * as an empty system (remove all packages) is a valid solution
3662    */
3663
3664   IF_POOLDEBUG (SOLV_DEBUG_STATS)
3665     {
3666       int possible = 0, installable = 0;
3667       for (i = 1; i < pool->nsolvables; i++)
3668         {
3669           if (pool_installable(pool, pool->solvables + i))
3670             installable++;
3671           if (MAPTST(&addedmap, i))
3672             possible++;
3673         }
3674       POOL_DEBUG(SOLV_DEBUG_STATS, "%d of %d installable solvables considered for solving\n", possible, installable);
3675     }
3676
3677   if (solv->nrules > initialnrules)
3678     solver_unifyrules(solv);                    /* remove duplicate rpm rules */
3679   solv->rpmrules_end = solv->nrules;            /* mark end of rpm rules */
3680
3681   if (solv->nrules > initialnrules)
3682     addedmap2deduceq(solv, &addedmap);          /* so that we can recreate the addedmap */
3683
3684   POOL_DEBUG(SOLV_DEBUG_STATS, "rpm rule memory used: %d K\n", solv->nrules * (int)sizeof(Rule) / 1024);
3685   POOL_DEBUG(SOLV_DEBUG_STATS, "rpm rule creation took %d ms\n", solv_timems(now));
3686
3687   /* create dup maps if needed. We need the maps early to create our
3688    * update rules */
3689   if (hasdupjob)
3690     solver_createdupmaps(solv);
3691
3692   /*
3693    * create feature rules
3694    *
3695    * foreach installed:
3696    *   create assertion (keep installed, if no update available)
3697    *   or
3698    *   create update rule (A|update1(A)|update2(A)|...)
3699    *
3700    * those are used later on to keep a version of the installed packages in
3701    * best effort mode
3702    */
3703
3704   solv->featurerules = solv->nrules;              /* mark start of feature rules */
3705   if (installed)
3706     {
3707       /* foreach possibly installed solvable */
3708       for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
3709         {
3710           if (s->repo != installed)
3711             {
3712               solver_addrule(solv, 0, 0);       /* create dummy rule */
3713               continue;
3714             }
3715           solver_addupdaterule(solv, s, 1);    /* allow s to be updated */
3716         }
3717       /* make sure we accounted for all rules */
3718       assert(solv->nrules - solv->featurerules == installed->end - installed->start);
3719     }
3720   solv->featurerules_end = solv->nrules;
3721
3722     /*
3723      * Add update rules for installed solvables
3724      *
3725      * almost identical to feature rules
3726      * except that downgrades/archchanges/vendorchanges are not allowed
3727      */
3728
3729   solv->updaterules = solv->nrules;
3730
3731   if (installed)
3732     { /* foreach installed solvables */
3733       /* we create all update rules, but disable some later on depending on the job */
3734       for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
3735         {
3736           Rule *sr;
3737
3738           if (s->repo != installed)
3739             {
3740               solver_addrule(solv, 0, 0);       /* create dummy rule */
3741               continue;
3742             }
3743           solver_addupdaterule(solv, s, 0);     /* allowall = 0: downgrades not allowed */
3744           /*
3745            * check for and remove duplicate
3746            */
3747           r = solv->rules + solv->nrules - 1;           /* r: update rule */
3748           if (!r->p)
3749             continue;
3750           sr = r - (installed->end - installed->start); /* sr: feature rule */
3751           /* it's also orphaned if the feature rule consists just of the installed package */
3752           if (!solv->dupmap_all && sr->p == i && !sr->d && !sr->w2)
3753             queue_push(&solv->orphaned, i);
3754           if (!solver_rulecmp(solv, r, sr))
3755             memset(sr, 0, sizeof(*sr));         /* delete unneeded feature rule */
3756           else
3757             solver_disablerule(solv, sr);       /* disable feature rule for now */
3758         }
3759       /* consistency check: we added a rule for _every_ installed solvable */
3760       assert(solv->nrules - solv->updaterules == installed->end - installed->start);
3761     }
3762   solv->updaterules_end = solv->nrules;
3763
3764
3765   /*
3766    * now add all job rules
3767    */
3768
3769   solv->jobrules = solv->nrules;
3770   for (i = 0; i < job->count; i += 2)
3771     {
3772       oldnrules = solv->nrules;
3773
3774       if (i && i == solv->pooljobcnt)
3775         POOL_DEBUG(SOLV_DEBUG_JOB, "end of pool jobs\n");
3776       how = job->elements[i];
3777       what = job->elements[i + 1];
3778       weak = how & SOLVER_WEAK;
3779       select = how & SOLVER_SELECTMASK;
3780       switch (how & SOLVER_JOBMASK)
3781         {
3782         case SOLVER_INSTALL:
3783           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sinstall %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
3784           if ((how & SOLVER_CLEANDEPS) != 0 && !solv->cleandepsmap.size && installed)
3785             map_grow(&solv->cleandepsmap, installed->end - installed->start);
3786           if (select == SOLVER_SOLVABLE)
3787             {
3788               p = what;
3789               d = 0;
3790             }
3791           else
3792             {
3793               queue_empty(&q);
3794               FOR_JOB_SELECT(p, pp, select, what)
3795                 queue_push(&q, p);
3796               if (!q.count)
3797                 {
3798                   if (select == SOLVER_SOLVABLE_ONE_OF)
3799                     break;      /* ignore empty installs */
3800                   /* no candidate found or unsupported, make this an impossible rule */
3801                   queue_push(&q, -SYSTEMSOLVABLE);
3802                 }
3803               p = queue_shift(&q);      /* get first candidate */
3804               d = !q.count ? 0 : pool_queuetowhatprovides(pool, &q);    /* internalize */
3805             }
3806           /* force install of namespace supplements hack */
3807           if (select == SOLVER_SOLVABLE_PROVIDES && !d && (p == SYSTEMSOLVABLE || p == -SYSTEMSOLVABLE) && ISRELDEP(what))
3808             {
3809               Reldep *rd = GETRELDEP(pool, what);
3810               if (rd->flags == REL_NAMESPACE)
3811                 {
3812                   p = SYSTEMSOLVABLE;
3813                   if (!solv->installsuppdepq)
3814                     {
3815                       solv->installsuppdepq = solv_calloc(1, sizeof(Queue));
3816                       queue_init(solv->installsuppdepq);
3817                     }
3818                   queue_pushunique(solv->installsuppdepq, rd->evr == 0 ? rd->name : what);
3819                 }
3820             }
3821           solver_addjobrule(solv, p, d, i, weak);
3822           if (how & SOLVER_FORCEBEST)
3823             hasbestinstalljob = 1;
3824           break;
3825         case SOLVER_ERASE:
3826           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %s%serase %s\n", weak ? "weak " : "", how & SOLVER_CLEANDEPS ? "clean deps " : "", solver_select2str(pool, select, what));
3827           if ((how & SOLVER_CLEANDEPS) != 0 && !solv->cleandepsmap.size && installed)
3828             map_grow(&solv->cleandepsmap, installed->end - installed->start);
3829           /* specific solvable: by id or by nevra */
3830           name = (select == SOLVER_SOLVABLE || (select == SOLVER_SOLVABLE_NAME && ISRELDEP(what))) ? 0 : -1;
3831           if (select == SOLVER_SOLVABLE_ALL)    /* hmmm ;) */
3832             {
3833               FOR_POOL_SOLVABLES(p)
3834                 solver_addjobrule(solv, -p, 0, i, weak);
3835             }
3836           else if (select == SOLVER_SOLVABLE_REPO)
3837             {
3838               Repo *repo = pool_id2repo(pool, what);
3839               if (repo)
3840                 FOR_REPO_SOLVABLES(repo, p, s)
3841                   solver_addjobrule(solv, -p, 0, i, weak);
3842             }
3843           FOR_JOB_SELECT(p, pp, select, what)
3844             {
3845               s = pool->solvables + p;
3846               if (installed && s->repo == installed)
3847                 name = !name ? s->name : -1;
3848               solver_addjobrule(solv, -p, 0, i, weak);
3849             }
3850           /* special case for "erase a specific solvable": we also
3851            * erase all other solvables with that name, so that they
3852            * don't get picked up as replacement.
3853            * name is > 0 if exactly one installed solvable matched.
3854            */
3855           /* XXX: look also at packages that obsolete this package? */
3856           if (name > 0)
3857             {
3858               int j, k;
3859               k = solv->nrules;
3860               FOR_PROVIDES(p, pp, name)
3861                 {
3862                   s = pool->solvables + p;
3863                   if (s->name != name)
3864                     continue;
3865                   /* keep other versions installed */
3866                   if (s->repo == installed)
3867                     continue;
3868                   /* keep installcandidates of other jobs */
3869                   if (MAPTST(&installcandidatemap, p))
3870                     continue;
3871                   /* don't add the same rule twice */
3872                   for (j = oldnrules; j < k; j++)
3873                     if (solv->rules[j].p == -p)
3874                       break;
3875                   if (j == k)
3876                     solver_addjobrule(solv, -p, 0, i, weak);    /* remove by id */
3877                 }
3878             }
3879           break;
3880
3881         case SOLVER_UPDATE:
3882           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %supdate %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
3883           break;
3884         case SOLVER_VERIFY:
3885           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sverify %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
3886           break;
3887         case SOLVER_WEAKENDEPS:
3888           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sweaken deps %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
3889           if (select != SOLVER_SOLVABLE)
3890             break;
3891           s = pool->solvables + what;
3892           weaken_solvable_deps(solv, what);
3893           break;
3894         case SOLVER_MULTIVERSION:
3895           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %smultiversion %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
3896           break;
3897         case SOLVER_LOCK:
3898           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %slock %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
3899           if (select == SOLVER_SOLVABLE_ALL)
3900             {
3901               FOR_POOL_SOLVABLES(p)
3902                 solver_addjobrule(solv, installed && pool->solvables[p].repo == installed ? p : -p, 0, i, weak);
3903             }
3904           else if (select == SOLVER_SOLVABLE_REPO)
3905             {
3906               Repo *repo = pool_id2repo(pool, what);
3907               if (repo)
3908                 FOR_REPO_SOLVABLES(repo, p, s)
3909                   solver_addjobrule(solv, installed && pool->solvables[p].repo == installed ? p : -p, 0, i, weak);
3910             }
3911           FOR_JOB_SELECT(p, pp, select, what)
3912             solver_addjobrule(solv, installed && pool->solvables[p].repo == installed ? p : -p, 0, i, weak);
3913           break;
3914         case SOLVER_DISTUPGRADE:
3915           POOL_DEBUG(SOLV_DEBUG_JOB, "job: distupgrade %s\n", solver_select2str(pool, select, what));
3916           break;
3917         case SOLVER_DROP_ORPHANED:
3918           POOL_DEBUG(SOLV_DEBUG_JOB, "job: drop orphaned %s\n", solver_select2str(pool, select, what));
3919           break;
3920         case SOLVER_USERINSTALLED:
3921           POOL_DEBUG(SOLV_DEBUG_JOB, "job: user installed %s\n", solver_select2str(pool, select, what));
3922           break;
3923         default:
3924           POOL_DEBUG(SOLV_DEBUG_JOB, "job: unknown job\n");
3925           break;
3926         }
3927
3928       IF_POOLDEBUG (SOLV_DEBUG_JOB)
3929         {
3930           int j;
3931           if (solv->nrules == oldnrules)
3932             POOL_DEBUG(SOLV_DEBUG_JOB, "  - no rule created\n");
3933           for (j = oldnrules; j < solv->nrules; j++)
3934             {
3935               POOL_DEBUG(SOLV_DEBUG_JOB, "  - job ");
3936               solver_printrule(solv, SOLV_DEBUG_JOB, solv->rules + j);
3937             }
3938         }
3939     }
3940   assert(solv->ruletojob.count == solv->nrules - solv->jobrules);
3941   solv->jobrules_end = solv->nrules;
3942
3943   /* now create infarch and dup rules */
3944   if (!solv->noinfarchcheck)
3945     {
3946       solver_addinfarchrules(solv, &addedmap);
3947 #if 0
3948       if (pool->implicitobsoleteusescolors)
3949         {
3950           /* currently doesn't work well with infarch rules, so make
3951            * them weak */
3952           for (i = solv->infarchrules; i < solv->infarchrules_end; i++)
3953             queue_push(&solv->weakruleq, i);
3954         }
3955 #endif
3956     }
3957   else
3958     solv->infarchrules = solv->infarchrules_end = solv->nrules;
3959
3960   if (hasdupjob)
3961     solver_addduprules(solv, &addedmap);
3962   else
3963     solv->duprules = solv->duprules_end = solv->nrules;
3964
3965   if (solv->bestupdatemap_all || solv->bestupdatemap.size || hasbestinstalljob)
3966     solver_addbestrules(solv, hasbestinstalljob);
3967   else
3968     solv->bestrules = solv->bestrules_end = solv->nrules;
3969
3970   if (hasdupjob)
3971     solver_freedupmaps(solv);   /* no longer needed */
3972
3973   if (solv->do_yum_obsoletes)
3974     solver_addyumobsrules(solv);
3975   else
3976     solv->yumobsrules = solv->yumobsrules_end = solv->nrules;
3977
3978   if (1)
3979     solver_addchoicerules(solv);
3980   else
3981     solv->choicerules = solv->choicerules_end = solv->nrules;
3982
3983   if (0)
3984     {
3985       for (i = solv->featurerules; i < solv->nrules; i++)
3986         solver_printruleclass(solv, SOLV_DEBUG_RESULT, solv->rules + i);
3987     }
3988   /* all rules created
3989    * --------------------------------------------------------------
3990    * prepare for solving
3991    */
3992
3993   /* free unneeded memory */
3994   map_free(&addedmap);
3995   map_free(&installcandidatemap);
3996   queue_free(&q);
3997
3998   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);
3999   POOL_DEBUG(SOLV_DEBUG_STATS, "overall rule memory used: %d K\n", solv->nrules * (int)sizeof(Rule) / 1024);
4000
4001   /* create weak map */
4002   map_init(&solv->weakrulemap, solv->nrules);
4003   for (i = 0; i < solv->weakruleq.count; i++)
4004     {
4005       p = solv->weakruleq.elements[i];
4006       MAPSET(&solv->weakrulemap, p);
4007     }
4008
4009   /* enable cleandepsmap creation if we have updatepkgs */
4010   if (solv->cleandeps_updatepkgs && !solv->cleandepsmap.size)
4011     map_grow(&solv->cleandepsmap, installed->end - installed->start);
4012   /* no mistakes */
4013   if (solv->cleandeps_mistakes)
4014     {
4015       queue_free(solv->cleandeps_mistakes);
4016       solv->cleandeps_mistakes = solv_free(solv->cleandeps_mistakes);
4017     }
4018
4019   /* all new rules are learnt after this point */
4020   solv->learntrules = solv->nrules;
4021
4022   /* create watches chains */
4023   makewatches(solv);
4024
4025   /* create assertion index. it is only used to speed up
4026    * makeruledecsions() a bit */
4027   for (i = 1, r = solv->rules + i; i < solv->nrules; i++, r++)
4028     if (r->p && !r->w2 && (r->d == 0 || r->d == -1))
4029       queue_push(&solv->ruleassertions, i);
4030
4031   /* disable update rules that conflict with our job */
4032   solver_disablepolicyrules(solv);
4033
4034   /* break orphans if requested */
4035   if (solv->dupmap_all && solv->orphaned.count && solv->break_orphans)
4036     solver_breakorphans(solv);
4037
4038   /* make initial decisions based on assertion rules */
4039   makeruledecisions(solv);
4040   POOL_DEBUG(SOLV_DEBUG_SOLVER, "problems so far: %d\n", solv->problems.count);
4041
4042   /*
4043    * ********************************************
4044    * solve!
4045    * ********************************************
4046    */
4047
4048   now = solv_timems(0);
4049   solver_run_sat(solv, 1, solv->dontinstallrecommended ? 0 : 1);
4050   POOL_DEBUG(SOLV_DEBUG_STATS, "solver took %d ms\n", solv_timems(now));
4051
4052   /*
4053    * prepare solution queue if there were problems
4054    */
4055   solver_prepare_solutions(solv);
4056
4057   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);
4058   POOL_DEBUG(SOLV_DEBUG_STATS, "solver_solve took %d ms\n", solv_timems(solve_start));
4059
4060   /* return number of problems */
4061   return solv->problems.count ? solv->problems.count / 2 : 0;
4062 }
4063
4064 Transaction *
4065 solver_create_transaction(Solver *solv)
4066 {
4067   return transaction_create_decisionq(solv->pool, &solv->decisionq, &solv->multiversion);
4068 }
4069
4070 void solver_get_orphaned(Solver *solv, Queue *orphanedq)
4071 {
4072   queue_free(orphanedq);
4073   queue_init_clone(orphanedq, &solv->orphaned);
4074 }
4075
4076 void solver_get_recommendations(Solver *solv, Queue *recommendationsq, Queue *suggestionsq, int noselected)
4077 {
4078   Pool *pool = solv->pool;
4079   Queue redoq, disabledq;
4080   int goterase, i;
4081   Solvable *s;
4082   Rule *r;
4083   Map obsmap;
4084
4085   if (!recommendationsq && !suggestionsq)
4086     return;
4087
4088   map_init(&obsmap, pool->nsolvables);
4089   if (solv->installed)
4090     {
4091       Id obs, *obsp, p, po, ppo;
4092       for (p = solv->installed->start; p < solv->installed->end; p++)
4093         {
4094           s = pool->solvables + p;
4095           if (s->repo != solv->installed || !s->obsoletes)
4096             continue;
4097           if (solv->decisionmap[p] <= 0)
4098             continue;
4099           if (solv->multiversion.size && MAPTST(&solv->multiversion, p))
4100             continue;
4101           obsp = s->repo->idarraydata + s->obsoletes;
4102           /* foreach obsoletes */
4103           while ((obs = *obsp++) != 0)
4104             FOR_PROVIDES(po, ppo, obs)
4105               MAPSET(&obsmap, po);
4106         }
4107     }
4108
4109   queue_init(&redoq);
4110   queue_init(&disabledq);
4111   goterase = 0;
4112   /* disable all erase jobs (including weak "keep uninstalled" rules) */
4113   for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++)
4114     {
4115       if (r->d < 0)     /* disabled ? */
4116         continue;
4117       if (r->p >= 0)    /* install job? */
4118         continue;
4119       queue_push(&disabledq, i);
4120       solver_disablerule(solv, r);
4121       goterase++;
4122     }
4123
4124   if (goterase)
4125     {
4126       enabledisablelearntrules(solv);
4127       removedisabledconflicts(solv, &redoq);
4128     }
4129
4130   /*
4131    * find recommended packages
4132    */
4133   if (recommendationsq)
4134     {
4135       Id rec, *recp, p, pp;
4136
4137       queue_empty(recommendationsq);
4138       /* create map of all recommened packages */
4139       solv->recommends_index = -1;
4140       MAPZERO(&solv->recommendsmap);
4141
4142       /* put all packages the solver already chose in the map */
4143       if (solv->decisioncnt_weak)
4144         {
4145           for (i = solv->decisioncnt_weak; i < solv->decisioncnt_orphan; i++)
4146             {
4147               Id why;
4148               why = solv->decisionq_why.elements[i];
4149               if (why)
4150                 continue;       /* forced by unit rule or dep resolving */
4151               p = solv->decisionq.elements[i];
4152               if (p < 0)
4153                 continue;
4154               MAPSET(&solv->recommendsmap, p);
4155             }
4156         }
4157
4158       for (i = 0; i < solv->decisionq.count; i++)
4159         {
4160           p = solv->decisionq.elements[i];
4161           if (p < 0)
4162             continue;
4163           s = pool->solvables + p;
4164           if (s->recommends)
4165             {
4166               recp = s->repo->idarraydata + s->recommends;
4167               while ((rec = *recp++) != 0)
4168                 {
4169 #ifdef ENABLE_COMPLEX_DEPS
4170                   if (pool_is_complex_dep(pool, rec))
4171                     {
4172                       do_complex_recommendations(solv, rec, &solv->recommendsmap, noselected);
4173                       continue;
4174                     }
4175 #endif
4176                   FOR_PROVIDES(p, pp, rec)
4177                     if (solv->decisionmap[p] > 0)
4178                       break;
4179                   if (p)
4180                     {
4181                       if (!noselected)
4182                         {
4183                           FOR_PROVIDES(p, pp, rec)
4184                             if (solv->decisionmap[p] > 0)
4185                               MAPSET(&solv->recommendsmap, p);
4186                         }
4187                       continue; /* p != 0: already fulfilled */
4188                     }
4189                   FOR_PROVIDES(p, pp, rec)
4190                     MAPSET(&solv->recommendsmap, p);
4191                 }
4192             }
4193         }
4194       for (i = 1; i < pool->nsolvables; i++)
4195         {
4196           if (solv->decisionmap[i] < 0)
4197             continue;
4198           if (solv->decisionmap[i] > 0 && noselected)
4199             continue;
4200           if (MAPTST(&obsmap, i))
4201             continue;
4202           s = pool->solvables + i;
4203           if (!MAPTST(&solv->recommendsmap, i))
4204             {
4205               if (!s->supplements)
4206                 continue;
4207               if (!pool_installable(pool, s))
4208                 continue;
4209               if (!solver_is_supplementing(solv, s))
4210                 continue;
4211             }
4212           queue_push(recommendationsq, i);
4213         }
4214       /* we use MODE_SUGGEST here so that repo prio is ignored */
4215       policy_filter_unwanted(solv, recommendationsq, POLICY_MODE_SUGGEST);
4216     }
4217
4218   /*
4219    * find suggested packages
4220    */
4221
4222   if (suggestionsq)
4223     {
4224       Id sug, *sugp, p, pp;
4225
4226       queue_empty(suggestionsq);
4227       /* create map of all suggests that are still open */
4228       solv->recommends_index = -1;
4229       MAPZERO(&solv->suggestsmap);
4230       for (i = 0; i < solv->decisionq.count; i++)
4231         {
4232           p = solv->decisionq.elements[i];
4233           if (p < 0)
4234             continue;
4235           s = pool->solvables + p;
4236           if (s->suggests)
4237             {
4238               sugp = s->repo->idarraydata + s->suggests;
4239               while ((sug = *sugp++) != 0)
4240                 {
4241 #ifdef ENABLE_COMPLEX_DEPS
4242                   if (pool_is_complex_dep(pool, sug))
4243                     {
4244                       do_complex_recommendations(solv, sug, &solv->suggestsmap, noselected);
4245                       continue;
4246                     }
4247 #endif
4248                   FOR_PROVIDES(p, pp, sug)
4249                     if (solv->decisionmap[p] > 0)
4250                       break;
4251                   if (p)
4252                     {
4253                       if (!noselected)
4254                         {
4255                           FOR_PROVIDES(p, pp, sug)
4256                             if (solv->decisionmap[p] > 0)
4257                               MAPSET(&solv->suggestsmap, p);
4258                         }
4259                       continue; /* already fulfilled */
4260                     }
4261                   FOR_PROVIDES(p, pp, sug)
4262                     MAPSET(&solv->suggestsmap, p);
4263                 }
4264             }
4265         }
4266       for (i = 1; i < pool->nsolvables; i++)
4267         {
4268           if (solv->decisionmap[i] < 0)
4269             continue;
4270           if (solv->decisionmap[i] > 0 && noselected)
4271             continue;
4272           if (MAPTST(&obsmap, i))
4273             continue;
4274           s = pool->solvables + i;
4275           if (!MAPTST(&solv->suggestsmap, i))
4276             {
4277               if (!s->enhances)
4278                 continue;
4279               if (!pool_installable(pool, s))
4280                 continue;
4281               if (!solver_is_enhancing(solv, s))
4282                 continue;
4283             }
4284           queue_push(suggestionsq, i);
4285         }
4286       policy_filter_unwanted(solv, suggestionsq, POLICY_MODE_SUGGEST);
4287     }
4288
4289   /* undo removedisabledconflicts */
4290   if (redoq.count)
4291     undo_removedisabledconflicts(solv, &redoq);
4292   queue_free(&redoq);
4293
4294   /* undo job rule disabling */
4295   for (i = 0; i < disabledq.count; i++)
4296     solver_enablerule(solv, solv->rules + disabledq.elements[i]);
4297   queue_free(&disabledq);
4298   map_free(&obsmap);
4299 }
4300
4301
4302 /***********************************************************************/
4303 /* disk usage computations */
4304
4305 /*-------------------------------------------------------------------
4306  *
4307  * calculate DU changes
4308  */
4309
4310 void
4311 solver_calc_duchanges(Solver *solv, DUChanges *mps, int nmps)
4312 {
4313   Map installedmap;
4314
4315   solver_create_state_maps(solv, &installedmap, 0);
4316   pool_calc_duchanges(solv->pool, &installedmap, mps, nmps);
4317   map_free(&installedmap);
4318 }
4319
4320
4321 /*-------------------------------------------------------------------
4322  *
4323  * calculate changes in install size
4324  */
4325
4326 int
4327 solver_calc_installsizechange(Solver *solv)
4328 {
4329   Map installedmap;
4330   int change;
4331
4332   solver_create_state_maps(solv, &installedmap, 0);
4333   change = pool_calc_installsizechange(solv->pool, &installedmap);
4334   map_free(&installedmap);
4335   return change;
4336 }
4337
4338 void
4339 solver_create_state_maps(Solver *solv, Map *installedmap, Map *conflictsmap)
4340 {
4341   pool_create_state_maps(solv->pool, &solv->decisionq, installedmap, conflictsmap);
4342 }
4343
4344 void
4345 solver_trivial_installable(Solver *solv, Queue *pkgs, Queue *res)
4346 {
4347   Pool *pool = solv->pool;
4348   Map installedmap;
4349   int i;
4350   pool_create_state_maps(pool,  &solv->decisionq, &installedmap, 0);
4351   pool_trivial_installable_multiversionmap(pool, &installedmap, pkgs, res, solv->multiversion.size ? &solv->multiversion : 0);
4352   for (i = 0; i < res->count; i++)
4353     if (res->elements[i] != -1)
4354       {
4355         Solvable *s = pool->solvables + pkgs->elements[i];
4356         if (!strncmp("patch:", pool_id2str(pool, s->name), 6) && solvable_is_irrelevant_patch(s, &installedmap))
4357           res->elements[i] = -1;
4358       }
4359   map_free(&installedmap);
4360 }
4361
4362 /*-------------------------------------------------------------------
4363  *
4364  * decision introspection
4365  */
4366
4367 int
4368 solver_get_decisionlevel(Solver *solv, Id p)
4369 {
4370   return solv->decisionmap[p];
4371 }
4372
4373 void
4374 solver_get_decisionqueue(Solver *solv, Queue *decisionq)
4375 {
4376   queue_free(decisionq);
4377   queue_init_clone(decisionq, &solv->decisionq);
4378 }
4379
4380 int
4381 solver_get_lastdecisionblocklevel(Solver *solv)
4382 {
4383   Id p;
4384   if (solv->decisionq.count == 0)
4385     return 0;
4386   p = solv->decisionq.elements[solv->decisionq.count - 1];
4387   if (p < 0)
4388     p = -p;
4389   return solv->decisionmap[p] < 0 ? -solv->decisionmap[p] : solv->decisionmap[p];
4390 }
4391
4392 void
4393 solver_get_decisionblock(Solver *solv, int level, Queue *decisionq)
4394 {
4395   Id p;
4396   int i;
4397
4398   queue_empty(decisionq);
4399   for (i = 0; i < solv->decisionq.count; i++)
4400     {
4401       p = solv->decisionq.elements[i];
4402       if (p < 0)
4403         p = -p;
4404       if (solv->decisionmap[p] == level || solv->decisionmap[p] == -level)
4405         break;
4406     }
4407   if (i == solv->decisionq.count)
4408     return;
4409   for (i = 0; i < solv->decisionq.count; i++)
4410     {
4411       p = solv->decisionq.elements[i];
4412       if (p < 0)
4413         p = -p;
4414       if (solv->decisionmap[p] == level || solv->decisionmap[p] == -level)
4415         queue_push(decisionq, p);
4416       else
4417         break;
4418     }
4419 }
4420
4421 int
4422 solver_describe_decision(Solver *solv, Id p, Id *infop)
4423 {
4424   int i;
4425   Id pp, why;
4426
4427   if (infop)
4428     *infop = 0;
4429   if (!solv->decisionmap[p])
4430     return SOLVER_REASON_UNRELATED;
4431   pp = solv->decisionmap[p] < 0 ? -p : p;
4432   for (i = 0; i < solv->decisionq.count; i++)
4433     if (solv->decisionq.elements[i] == pp)
4434       break;
4435   if (i == solv->decisionq.count)       /* just in case... */
4436     return SOLVER_REASON_UNRELATED;
4437   why = solv->decisionq_why.elements[i];
4438   if (infop)
4439     *infop = why > 0 ? why : -why;
4440   if (why > 0)
4441     return SOLVER_REASON_UNIT_RULE;
4442   why = -why;
4443   if (i == 0)
4444     return SOLVER_REASON_KEEP_INSTALLED;        /* the systemsolvable */
4445   if (i < solv->decisioncnt_update)
4446     return SOLVER_REASON_RESOLVE_JOB;
4447   if (i < solv->decisioncnt_keep)
4448     {
4449       if (why == 0 && pp < 0)
4450         return SOLVER_REASON_CLEANDEPS_ERASE;
4451       return SOLVER_REASON_UPDATE_INSTALLED;
4452     }
4453   if (i < solv->decisioncnt_resolve)
4454     {
4455       if (solv->focus_installed && i >= solv->decisioncnt_jobs)
4456         return SOLVER_REASON_RESOLVE_JOB;
4457       if (why == 0 && pp < 0)
4458         return SOLVER_REASON_CLEANDEPS_ERASE;
4459       return SOLVER_REASON_KEEP_INSTALLED;
4460     }
4461   if (why > 0)
4462     return SOLVER_REASON_RESOLVE;
4463   /* weak or orphaned */
4464   if (i < solv->decisioncnt_orphan)
4465     return SOLVER_REASON_WEAKDEP;
4466   return SOLVER_REASON_RESOLVE_ORPHAN;
4467 }
4468
4469
4470 void
4471 solver_describe_weakdep_decision(Solver *solv, Id p, Queue *whyq)
4472 {
4473   Pool *pool = solv->pool;
4474   int i;
4475   int level = solv->decisionmap[p];
4476   int decisionno;
4477   Solvable *s;
4478
4479   queue_empty(whyq);
4480   if (level < 0)
4481     return;     /* huh? */
4482   for (decisionno = 0; decisionno < solv->decisionq.count; decisionno++)
4483     if (solv->decisionq.elements[decisionno] == p)
4484       break;
4485   if (decisionno == solv->decisionq.count)
4486     return;     /* huh? */
4487   if (decisionno < solv->decisioncnt_weak || decisionno >= solv->decisioncnt_orphan)
4488     return;     /* huh? */
4489
4490   /* 1) list all packages that recommend us */
4491   for (i = 1; i < pool->nsolvables; i++)
4492     {
4493       Id *recp, rec, pp2, p2;
4494       if (solv->decisionmap[i] < 0 || solv->decisionmap[i] >= level)
4495         continue;
4496       s = pool->solvables + i;
4497       if (!s->recommends)
4498         continue;
4499       if (!solv->addalreadyrecommended && s->repo == solv->installed)
4500         continue;
4501       recp = s->repo->idarraydata + s->recommends;
4502       while ((rec = *recp++) != 0)
4503         {
4504           int found = 0;
4505           FOR_PROVIDES(p2, pp2, rec)
4506             {
4507               if (p2 == p)
4508                 found = 1;
4509               else
4510                 {
4511                   /* if p2 is already installed, this recommends is ignored */
4512                   if (solv->decisionmap[p2] > 0 && solv->decisionmap[p2] < level)
4513                     break;
4514                 }
4515             }
4516           if (!p2 && found)
4517             {
4518               queue_push(whyq, SOLVER_REASON_RECOMMENDED);
4519               queue_push2(whyq, i, rec);
4520             }
4521         }
4522     }
4523   /* 2) list all supplements */
4524   s = pool->solvables + p;
4525   if (s->supplements && level > 0)
4526     {
4527       Id *supp, sup, pp2, p2;
4528       /* this is a hack. to use solver_dep_fulfilled we temporarily clear
4529        * everything above our level in the decisionmap */
4530       for (i = decisionno; i < solv->decisionq.count; i++ )
4531         {
4532           p2 = solv->decisionq.elements[i];
4533           if (p2 > 0)
4534             solv->decisionmap[p2] = -solv->decisionmap[p2];
4535         }
4536       supp = s->repo->idarraydata + s->supplements;
4537       while ((sup = *supp++) != 0)
4538         if (solver_dep_fulfilled(solv, sup))
4539           {
4540             int found = 0;
4541             /* let's see if this is an easy supp */
4542             FOR_PROVIDES(p2, pp2, sup)
4543               {
4544                 if (!solv->addalreadyrecommended && solv->installed)
4545                   {
4546                     if (pool->solvables[p2].repo == solv->installed)
4547                       continue;
4548                   }
4549                 if (solv->decisionmap[p2] > 0 && solv->decisionmap[p2] < level)
4550                   {
4551                     queue_push(whyq, SOLVER_REASON_SUPPLEMENTED);
4552                     queue_push2(whyq, p2, sup);
4553                     found = 1;
4554                   }
4555               }
4556             if (!found)
4557               {
4558                 /* hard case, just note dependency with no package */
4559                 queue_push(whyq, SOLVER_REASON_SUPPLEMENTED);
4560                 queue_push2(whyq, 0, sup);
4561               }
4562           }
4563       for (i = decisionno; i < solv->decisionq.count; i++)
4564         {
4565           p2 = solv->decisionq.elements[i];
4566           if (p2 > 0)
4567             solv->decisionmap[p2] = -solv->decisionmap[p2];
4568         }
4569     }
4570 }
4571
4572 void
4573 pool_job2solvables(Pool *pool, Queue *pkgs, Id how, Id what)
4574 {
4575   Id p, pp;
4576   how &= SOLVER_SELECTMASK;
4577   queue_empty(pkgs);
4578   if (how == SOLVER_SOLVABLE_ALL)
4579     {
4580       FOR_POOL_SOLVABLES(p)
4581         queue_push(pkgs, p);
4582     }
4583   else if (how == SOLVER_SOLVABLE_REPO)
4584     {
4585       Repo *repo = pool_id2repo(pool, what);
4586       Solvable *s;
4587       if (repo)
4588         FOR_REPO_SOLVABLES(repo, p, s)
4589           queue_push(pkgs, p);
4590     }
4591   else
4592     {
4593       FOR_JOB_SELECT(p, pp, how, what)
4594         queue_push(pkgs, p);
4595     }
4596 }
4597
4598 int
4599 pool_isemptyupdatejob(Pool *pool, Id how, Id what)
4600 {
4601   Id p, pp, pi, pip;
4602   Id select = how & SOLVER_SELECTMASK;
4603   if ((how & SOLVER_JOBMASK) != SOLVER_UPDATE)
4604     return 0;
4605   if (select == SOLVER_SOLVABLE_ALL || select == SOLVER_SOLVABLE_REPO)
4606     return 0;
4607   if (!pool->installed)
4608     return 1;
4609   FOR_JOB_SELECT(p, pp, select, what)
4610     if (pool->solvables[p].repo == pool->installed)
4611       return 0;
4612   /* hard work */
4613   FOR_JOB_SELECT(p, pp, select, what)
4614     {
4615       Solvable *s = pool->solvables + p;
4616       FOR_PROVIDES(pi, pip, s->name)
4617         {
4618           Solvable *si = pool->solvables + pi;
4619           if (si->repo != pool->installed || si->name != s->name)
4620             continue;
4621           return 0;
4622         }
4623       if (s->obsoletes)
4624         {
4625           Id obs, *obsp = s->repo->idarraydata + s->obsoletes;
4626           while ((obs = *obsp++) != 0)
4627             {
4628               FOR_PROVIDES(pi, pip, obs)
4629                 {
4630                   Solvable *si = pool->solvables + pi;
4631                   if (si->repo != pool->installed)
4632                     continue;
4633                   if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, si, obs))
4634                     continue;
4635                   if (pool->obsoleteusescolors && !pool_colormatch(pool, s, si))
4636                     continue;
4637                   return 0;
4638                 }
4639             }
4640         }
4641     }
4642   return 1;
4643 }
4644
4645 static int
4646 get_userinstalled_cmp(const void *ap, const void *bp, void *dp)
4647 {
4648   return *(Id *)ap - *(Id *)bp;
4649 }
4650
4651 static int
4652 get_userinstalled_cmp_names(const void *ap, const void *bp, void *dp)
4653 {
4654   Pool *pool = dp;
4655   return strcmp(pool_id2str(pool, *(Id *)ap), pool_id2str(pool, *(Id *)bp));
4656 }
4657
4658 static void
4659 get_userinstalled_sort_uniq(Pool *pool, Queue *q, int flags)
4660 {
4661   Id lastp = -1;
4662   int i, j;
4663   if ((flags & GET_USERINSTALLED_NAMES) != 0)
4664     solv_sort(q->elements, q->count, sizeof(Id), get_userinstalled_cmp_names, pool);
4665   else
4666     solv_sort(q->elements, q->count, sizeof(Id), get_userinstalled_cmp, 0);
4667   for (i = j = 0; i < q->count; i++)
4668     if (q->elements[i] != lastp)
4669       q->elements[j++] = lastp = q->elements[i];
4670   queue_truncate(q, j);
4671 }
4672
4673 void
4674 solver_get_userinstalled(Solver *solv, Queue *q, int flags)
4675 {
4676   Pool *pool = solv->pool;
4677   Id p, p2, pp;
4678   Solvable *s;
4679   Repo *installed = solv->installed;
4680   int i, j;
4681   Map userinstalled;
4682
4683   map_init(&userinstalled, 0);
4684   queue_empty(q);
4685   /* first process jobs */
4686   for (i = 0; i < solv->job.count; i += 2)
4687     {
4688       Id how = solv->job.elements[i];
4689       Id what, select;
4690       if (installed && (how & SOLVER_JOBMASK) == SOLVER_USERINSTALLED)
4691         {
4692           if (!userinstalled.size)
4693             map_grow(&userinstalled, installed->end - installed->start);
4694           what = solv->job.elements[i + 1];
4695           select = how & SOLVER_SELECTMASK;
4696           if (select == SOLVER_SOLVABLE_ALL || (select == SOLVER_SOLVABLE_REPO && what == installed->repoid))
4697             FOR_REPO_SOLVABLES(installed, p, s)
4698               MAPSET(&userinstalled, p - installed->start);
4699           FOR_JOB_SELECT(p, pp, select, what)
4700             if (pool->solvables[p].repo == installed)
4701               MAPSET(&userinstalled, p - installed->start);
4702           continue;
4703         }
4704       if ((how & SOLVER_JOBMASK) != SOLVER_INSTALL)
4705         continue;
4706       if ((how & SOLVER_NOTBYUSER) != 0)
4707         continue;
4708       what = solv->job.elements[i + 1];
4709       select = how & SOLVER_SELECTMASK;
4710       FOR_JOB_SELECT(p, pp, select, what)
4711         if (solv->decisionmap[p] > 0)
4712           {
4713             queue_push(q, p);
4714 #ifdef ENABLE_LINKED_PKGS
4715             if (has_package_link(pool, pool->solvables + p))
4716               {
4717                 int j;
4718                 Queue lq;
4719                 queue_init(&lq);
4720                 find_package_link(pool, pool->solvables + p, 0, &lq, 0, 0);
4721                 for (j = 0; j < lq.count; j++)
4722                   if (solv->decisionmap[lq.elements[j]] > 0)
4723                     queue_push(q, lq.elements[j]);
4724               }
4725 #endif
4726           }
4727     }
4728   /* now process updates of userinstalled packages */
4729   if (installed && userinstalled.size)
4730     {
4731       for (i = 1; i < solv->decisionq.count; i++)
4732         {
4733           p = solv->decisionq.elements[i];
4734           if (p <= 0)
4735             continue;
4736           s = pool->solvables + p;
4737           if (!s->repo)
4738             continue;
4739           if (s->repo == installed)
4740             {
4741               if (MAPTST(&userinstalled, p - installed->start))
4742                 queue_push(q, p);
4743               continue;
4744             }
4745           /* new package, check if we replace a userinstalled one */
4746           FOR_PROVIDES(p2, pp, s->name)
4747             {
4748               Solvable *ps = pool->solvables + p2;
4749               if (p2 == p || ps->repo != installed || !MAPTST(&userinstalled, p2 - installed->start))
4750                 continue;
4751               if (!pool->implicitobsoleteusesprovides && s->name != ps->name)
4752                 continue;
4753               if (pool->implicitobsoleteusescolors && !pool_colormatch(pool, s, ps))
4754                 continue;
4755               queue_push(q, p);
4756               break;
4757             }
4758           if (!p2 && s->repo != installed && s->obsoletes)
4759             {
4760               Id obs, *obsp = s->repo->idarraydata + s->obsoletes;
4761               while ((obs = *obsp++) != 0)
4762                 {
4763                   FOR_PROVIDES(p2, pp, obs)
4764                     {
4765                       Solvable *ps = pool->solvables + p2;
4766                       if (p2 == p || ps->repo != installed || !MAPTST(&userinstalled, p2 - installed->start))
4767                         continue;
4768                       if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
4769                         continue;
4770                       if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
4771                         continue;
4772                       queue_push(q, p);
4773                       break;
4774                     }
4775                   if (p2)
4776                     break;
4777                 }
4778             }
4779         }
4780     }
4781   map_free(&userinstalled);
4782   /* convert to names if asked */
4783   if ((flags & GET_USERINSTALLED_NAMES) != 0)
4784     {
4785       for (i = 0; i < q->count; i++)
4786         {
4787           s = pool->solvables + q->elements[i];
4788           q->elements[i] = s->name;
4789         }
4790     }
4791   /* sort and unify */
4792   if (q->count > 1)
4793     get_userinstalled_sort_uniq(pool, q, flags);
4794   /* invert if asked */
4795   if ((flags & GET_USERINSTALLED_INVERTED) != 0)
4796     {
4797       /* first generate queue with all installed packages */
4798       Queue invq;
4799       queue_init(&invq);
4800       for (i = 1; i < solv->decisionq.count; i++)
4801         {
4802           p = solv->decisionq.elements[i];
4803           if (p <= 0)
4804             continue;
4805           s = pool->solvables + p;
4806           if (!s->repo)
4807             continue;
4808           if ((flags & GET_USERINSTALLED_NAMES) != 0)
4809             queue_push(&invq, s->name);
4810           else
4811             queue_push(&invq, p);
4812         }
4813       /* push q on invq, just in case... */
4814       queue_insertn(&invq, invq.count, q->count, q->elements);
4815       if (invq.count > 1)
4816         get_userinstalled_sort_uniq(pool, &invq, flags);
4817       /* subtract queues (easy as they are sorted and invq is a superset of q) */
4818       if (q->count)
4819         {
4820           for (i = j = 0; i < invq.count; i++)
4821             if (invq.elements[i] == q->elements[j])
4822               {
4823                 invq.elements[i] = 0;
4824                 if (++j >= q->count)
4825                   break;
4826               }
4827           queue_empty(q);
4828         }
4829       for (i = j = 0; i < invq.count; i++)
4830         if (invq.elements[i])
4831           queue_push(q, invq.elements[i]);
4832       queue_free(&invq);
4833     }
4834 }
4835
4836 void
4837 pool_add_userinstalled_jobs(Pool *pool, Queue *q, Queue *job, int flags)
4838 {
4839   int i;
4840
4841   if (flags & GET_USERINSTALLED_INVERTED)
4842     {
4843       Queue invq;
4844       Id p, lastid;
4845       Solvable *s;
4846       int bad;
4847       if (!pool->installed)
4848         return;
4849       queue_init(&invq);
4850       FOR_REPO_SOLVABLES(pool->installed, p, s)
4851         queue_push(&invq, flags & GET_USERINSTALLED_NAMES ? s->name : p);
4852       queue_insertn(&invq, invq.count, q->count, q->elements);
4853       if (invq.count > 1)
4854         get_userinstalled_sort_uniq(pool, &invq, flags);
4855       /* now the fun part, add q again, sort, and remove all dups */
4856       queue_insertn(&invq, invq.count, q->count, q->elements);
4857       if (invq.count > 1)
4858         {
4859           if ((flags & GET_USERINSTALLED_NAMES) != 0)
4860             solv_sort(invq.elements, invq.count, sizeof(Id), get_userinstalled_cmp_names, pool);
4861           else
4862             solv_sort(invq.elements, invq.count, sizeof(Id), get_userinstalled_cmp, 0);
4863         }
4864       lastid = -1;
4865       bad = 1;
4866       for (i = 0; i < invq.count; i++)
4867         {
4868           if (invq.elements[i] == lastid)
4869             {
4870               bad = 1;
4871               continue;
4872             }
4873           if (!bad)
4874             queue_push2(job, SOLVER_USERINSTALLED | (flags & GET_USERINSTALLED_NAMES ? SOLVER_SOLVABLE_NAME : SOLVER_SOLVABLE), lastid);
4875           bad = 0;
4876           lastid = invq.elements[i];
4877         }
4878       if (!bad)
4879         queue_push2(job, SOLVER_USERINSTALLED | (flags & GET_USERINSTALLED_NAMES ? SOLVER_SOLVABLE_NAME : SOLVER_SOLVABLE), lastid);
4880       queue_free(&invq);
4881     }
4882   else
4883     {
4884       for (i = 0; i < q->count; i++)
4885         queue_push2(job, SOLVER_USERINSTALLED | (flags & GET_USERINSTALLED_NAMES ? SOLVER_SOLVABLE_NAME : SOLVER_SOLVABLE), q->elements[i]);
4886     }
4887 }
4888
4889 const char *
4890 solver_select2str(Pool *pool, Id select, Id what)
4891 {
4892   const char *s;
4893   char *b;
4894   select &= SOLVER_SELECTMASK;
4895   if (select == SOLVER_SOLVABLE)
4896     return pool_solvid2str(pool, what);
4897   if (select == SOLVER_SOLVABLE_NAME)
4898     return pool_dep2str(pool, what);
4899   if (select == SOLVER_SOLVABLE_PROVIDES)
4900     {
4901       s = pool_dep2str(pool, what);
4902       b = pool_alloctmpspace(pool, 11 + strlen(s));
4903       sprintf(b, "providing %s", s);
4904       return b;
4905     }
4906   if (select == SOLVER_SOLVABLE_ONE_OF)
4907     {
4908       Id p;
4909       b = 0;
4910       while ((p = pool->whatprovidesdata[what++]) != 0)
4911         {
4912           s = pool_solvid2str(pool, p);
4913           if (b)
4914             b = pool_tmpappend(pool, b, ", ", s);
4915           else
4916             b = pool_tmpjoin(pool, s, 0, 0);
4917           pool_freetmpspace(pool, s);
4918         }
4919       return b ? b : "nothing";
4920     }
4921   if (select == SOLVER_SOLVABLE_REPO)
4922     {
4923       b = pool_alloctmpspace(pool, 20);
4924       sprintf(b, "repo #%d", what);
4925       return b;
4926     }
4927   if (select == SOLVER_SOLVABLE_ALL)
4928     return "all packages";
4929   return "unknown job select";
4930 }
4931
4932 const char *
4933 pool_job2str(Pool *pool, Id how, Id what, Id flagmask)
4934 {
4935   Id select = how & SOLVER_SELECTMASK;
4936   const char *strstart = 0, *strend = 0;
4937   char *s;
4938   int o;
4939
4940   switch (how & SOLVER_JOBMASK)
4941     {
4942     case SOLVER_NOOP:
4943       return "do nothing";
4944     case SOLVER_INSTALL:
4945       if (select == SOLVER_SOLVABLE && pool->installed && pool->solvables[what].repo == pool->installed)
4946         strstart = "keep ", strend = " installed";
4947       else if (select == SOLVER_SOLVABLE || select == SOLVER_SOLVABLE_NAME)
4948         strstart = "install ";
4949       else if (select == SOLVER_SOLVABLE_PROVIDES)
4950         strstart = "install a package ";
4951       else
4952         strstart = "install one of ";
4953       break;
4954     case SOLVER_ERASE:
4955       if (select == SOLVER_SOLVABLE && !(pool->installed && pool->solvables[what].repo == pool->installed))
4956         strstart = "keep ", strend = " uninstalled";
4957       else if (select == SOLVER_SOLVABLE_PROVIDES)
4958         strstart = "deinstall all packages ";
4959       else
4960         strstart = "deinstall ";
4961       break;
4962     case SOLVER_UPDATE:
4963       strstart = "update ";
4964       break;
4965     case SOLVER_WEAKENDEPS:
4966       strstart = "weaken deps of ";
4967       break;
4968     case SOLVER_MULTIVERSION:
4969       strstart = "multi version ";
4970       break;
4971     case SOLVER_LOCK:
4972       strstart = "lock ";
4973       break;
4974     case SOLVER_DISTUPGRADE:
4975       strstart = "dist upgrade ";
4976       break;
4977     case SOLVER_VERIFY:
4978       strstart = "verify ";
4979       break;
4980     case SOLVER_DROP_ORPHANED:
4981       strstart = "deinstall ", strend = " if orphaned";
4982       break;
4983     case SOLVER_USERINSTALLED:
4984       strstart = "regard ", strend = " as userinstalled";
4985       break;
4986     default:
4987       strstart = "unknown job ";
4988       break;
4989     }
4990   s = pool_tmpjoin(pool, strstart, solver_select2str(pool, select, what), strend);
4991   how &= flagmask;
4992   if ((how & ~(SOLVER_SELECTMASK|SOLVER_JOBMASK)) == 0)
4993     return s;
4994   o = strlen(s);
4995   s = pool_tmpappend(pool, s, " ", 0);
4996   if (how & SOLVER_WEAK)
4997     s = pool_tmpappend(pool, s, ",weak", 0);
4998   if (how & SOLVER_ESSENTIAL)
4999     s = pool_tmpappend(pool, s, ",essential", 0);
5000   if (how & SOLVER_CLEANDEPS)
5001     s = pool_tmpappend(pool, s, ",cleandeps", 0);
5002   if (how & SOLVER_ORUPDATE)
5003     s = pool_tmpappend(pool, s, ",orupdate", 0);
5004   if (how & SOLVER_FORCEBEST)
5005     s = pool_tmpappend(pool, s, ",forcebest", 0);
5006   if (how & SOLVER_TARGETED)
5007     s = pool_tmpappend(pool, s, ",targeted", 0);
5008   if (how & SOLVER_SETEV)
5009     s = pool_tmpappend(pool, s, ",setev", 0);
5010   if (how & SOLVER_SETEVR)
5011     s = pool_tmpappend(pool, s, ",setevr", 0);
5012   if (how & SOLVER_SETARCH)
5013     s = pool_tmpappend(pool, s, ",setarch", 0);
5014   if (how & SOLVER_SETVENDOR)
5015     s = pool_tmpappend(pool, s, ",setvendor", 0);
5016   if (how & SOLVER_SETREPO)
5017     s = pool_tmpappend(pool, s, ",setrepo", 0);
5018   if (how & SOLVER_SETNAME)
5019     s = pool_tmpappend(pool, s, ",setname", 0);
5020   if (how & SOLVER_NOAUTOSET)
5021     s = pool_tmpappend(pool, s, ",noautoset", 0);
5022   if (s[o + 1] != ',')
5023     s = pool_tmpappend(pool, s, ",?", 0);
5024   s[o + 1] = '[';
5025   return pool_tmpappend(pool, s, "]", 0);
5026 }
5027