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