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