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 "solverdebug.h"
  27
  28 #define RULES_BLOCK 63
  29
  30 /********************************************************************
  31  *
  32  * dependency check helpers
  33  *
  34  */
  35
  36 /*-------------------------------------------------------------------
  37  * handle split provides
  38  *
  39  * a splitprovides dep looks like
  40  *     namespace:splitprovides(pkg REL_WITH path)
  41  * and is only true if pkg is installed and contains the specified path.
  42  * we also make sure that pkg is selected for an update, otherwise the
  43  * update would always be forced onto the user.
  44  */
  45 int
  46 solver_splitprovides(Solver *solv, Id dep)
  47 {
  48   Pool *pool = solv->pool;
  49   Id p, pp;
  50   Reldep *rd;
  51   Solvable *s;
  52
  53   if (!solv->dosplitprovides || !solv->installed || (!solv->updatemap_all && !solv->updatemap.size))
  54     return 0;
  55   if (!ISRELDEP(dep))
  56     return 0;
  57   rd = GETRELDEP(pool, dep);
  58   if (rd->flags != REL_WITH)
  59     return 0;
  60   FOR_PROVIDES(p, pp, dep)
  61     {
  62       /* here we have packages that provide the correct name and contain the path,
  63        * now do extra filtering */
  64       s = pool->solvables + p;
  65       if (s->repo == solv->installed && s->name == rd->name &&
  66           (solv->updatemap_all || (solv->updatemap.size && MAPTST(&solv->updatemap, p - solv->installed->start))))
  67         return 1;
  68     }
  69   return 0;
  70 }
  71
  72
  73 /*-------------------------------------------------------------------
  74  * solver_dep_installed
  75  */
  76
  77 int
  78 solver_dep_installed(Solver *solv, Id dep)
  79 {
  80 #if 0
  81   Pool *pool = solv->pool;
  82   Id p, pp;
  83
  84   if (ISRELDEP(dep))
  85     {
  86       Reldep *rd = GETRELDEP(pool, dep);
  87       if (rd->flags == REL_AND)
  88         {
  89           if (!solver_dep_installed(solv, rd->name))
  90             return 0;
  91           return solver_dep_installed(solv, rd->evr);
  92         }
  93       if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
  94         return solver_dep_installed(solv, rd->evr);
  95     }
  96   FOR_PROVIDES(p, pp, dep)
  97     {
  98       if (p == SYSTEMSOLVABLE || (solv->installed && pool->solvables[p].repo == solv->installed))
  99         return 1;
 100     }
 101 #endif
 102   return 0;
 103 }
 104
 105
 106
 107 /************************************************************************/
 108
 109 /*
 110  * make assertion rules into decisions
 111  *
 112  * Go through rules and add direct assertions to the decisionqueue.
 113  * If we find a conflict, disable rules and add them to problem queue.
 114  */
 115
 116 static void
 117 makeruledecisions(Solver *solv)
 118 {
 119   Pool *pool = solv->pool;
 120   int i, ri, ii;
 121   Rule *r, *rr;
 122   Id v, vv;
 123   int decisionstart;
 124   int record_proof = 1;
 125
 126   /* The system solvable is always installed first */
 127   assert(solv->decisionq.count == 0);
 128   queue_push(&solv->decisionq, SYSTEMSOLVABLE);
 129   queue_push(&solv->decisionq_why, 0);
 130   solv->decisionmap[SYSTEMSOLVABLE] = 1;        /* installed at level '1' */
 131
 132   decisionstart = solv->decisionq.count;
 133   for (ii = 0; ii < solv->ruleassertions.count; ii++)
 134     {
 135       ri = solv->ruleassertions.elements[ii];
 136       r = solv->rules + ri;
 137
 138       if (r->d < 0 || !r->p || r->w2)   /* disabled, dummy or no assertion */
 139         continue;
 140       /* do weak rules in phase 2 */
 141       if (ri < solv->learntrules && MAPTST(&solv->weakrulemap, ri))
 142         continue;
 143
 144       v = r->p;
 145       vv = v > 0 ? v : -v;
 146
 147       if (!solv->decisionmap[vv])          /* if not yet decided */
 148         {
 149             /*
 150              * decide !
 151              */
 152           queue_push(&solv->decisionq, v);
 153           queue_push(&solv->decisionq_why, r - solv->rules);
 154           solv->decisionmap[vv] = v > 0 ? 1 : -1;
 155           IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
 156             {
 157               Solvable *s = solv->pool->solvables + vv;
 158               if (v < 0)
 159                 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "conflicting %s (assertion)\n", pool_solvable2str(solv->pool, s));
 160               else
 161                 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "installing  %s (assertion)\n", pool_solvable2str(solv->pool, s));
 162             }
 163           continue;
 164         }
 165         /*
 166          * check previous decision: is it sane ?
 167          */
 168
 169       if (v > 0 && solv->decisionmap[vv] > 0)    /* ok to install */
 170         continue;
 171       if (v < 0 && solv->decisionmap[vv] < 0)    /* ok to remove */
 172         continue;
 173
 174         /*
 175          * found a conflict!
 176          *
 177          * The rule (r) we're currently processing says something
 178          * different (v = r->p) than a previous decision (decisionmap[abs(v)])
 179          * on this literal
 180          */
 181
 182       if (ri >= solv->learntrules)
 183         {
 184           /* conflict with a learnt rule */
 185           /* can happen when packages cannot be installed for
 186            * multiple reasons. */
 187           /* we disable the learnt rule in this case */
 188           solver_disablerule(solv, r);
 189           continue;
 190         }
 191
 192         /*
 193          * find the decision which is the "opposite" of the rule
 194          */
 195
 196       for (i = 0; i < solv->decisionq.count; i++)
 197         if (solv->decisionq.elements[i] == -v)
 198           break;
 199       assert(i < solv->decisionq.count);         /* assert that we found it */
 200
 201       /*
 202        * conflict with system solvable ?
 203        */
 204
 205       if (v == -SYSTEMSOLVABLE)
 206         {
 207           /* conflict with system solvable */
 208           if (record_proof)
 209             {
 210               queue_push(&solv->problems, solv->learnt_pool.count);
 211               queue_push(&solv->learnt_pool, ri);
 212               queue_push(&solv->learnt_pool, 0);
 213             }
 214           else
 215             queue_push(&solv->problems, 0);
 216           POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "conflict with system solvable, disabling rule #%d\n", ri);
 217           if  (ri >= solv->jobrules && ri < solv->jobrules_end)
 218             v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
 219           else
 220             v = ri;
 221           queue_push(&solv->problems, v);
 222           queue_push(&solv->problems, 0);
 223           solver_disableproblem(solv, v);
 224           continue;
 225         }
 226
 227       assert(solv->decisionq_why.elements[i] > 0);
 228
 229       /*
 230        * conflict with an rpm rule ?
 231        */
 232
 233       if (solv->decisionq_why.elements[i] < solv->rpmrules_end)
 234         {
 235           /* conflict with rpm rule assertion */
 236           if (record_proof)
 237             {
 238               queue_push(&solv->problems, solv->learnt_pool.count);
 239               queue_push(&solv->learnt_pool, ri);
 240               queue_push(&solv->learnt_pool, solv->decisionq_why.elements[i]);
 241               queue_push(&solv->learnt_pool, 0);
 242             }
 243           else
 244             queue_push(&solv->problems, 0);
 245           assert(v > 0 || v == -SYSTEMSOLVABLE);
 246           POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "conflict with rpm rule, disabling rule #%d\n", ri);
 247           if (ri >= solv->jobrules && ri < solv->jobrules_end)
 248             v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
 249           else
 250             v = ri;
 251           queue_push(&solv->problems, v);
 252           queue_push(&solv->problems, 0);
 253           solver_disableproblem(solv, v);
 254           continue;
 255         }
 256
 257       /*
 258        * conflict with another job or update/feature rule
 259        */
 260
 261       /* record proof */
 262       if (record_proof)
 263         {
 264           queue_push(&solv->problems, solv->learnt_pool.count);
 265           queue_push(&solv->learnt_pool, ri);
 266           queue_push(&solv->learnt_pool, solv->decisionq_why.elements[i]);
 267           queue_push(&solv->learnt_pool, 0);
 268         }
 269       else
 270         queue_push(&solv->problems, 0);
 271
 272       POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "conflicting update/job assertions over literal %d\n", vv);
 273
 274         /*
 275          * push all of our rules (can only be feature or job rules)
 276          * asserting this literal on the problem stack
 277          */
 278
 279       for (i = solv->featurerules, rr = solv->rules + i; i < solv->learntrules; i++, rr++)
 280         {
 281           if (rr->d < 0                          /* disabled */
 282               || rr->w2)                         /*  or no assertion */
 283             continue;
 284           if (rr->p != vv                        /* not affecting the literal */
 285               && rr->p != -vv)
 286             continue;
 287           if (MAPTST(&solv->weakrulemap, i))     /* weak: silently ignore */
 288             continue;
 289
 290           POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, " - disabling rule #%d\n", i);
 291
 292           solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE, solv->rules + i);
 293
 294           v = i;
 295             /* is is a job rule ? */
 296           if (i >= solv->jobrules && i < solv->jobrules_end)
 297             v = -(solv->ruletojob.elements[i - solv->jobrules] + 1);
 298
 299           queue_push(&solv->problems, v);
 300           solver_disableproblem(solv, v);
 301         }
 302       queue_push(&solv->problems, 0);
 303
 304       /*
 305        * start over
 306        * (back up from decisions)
 307        */
 308       while (solv->decisionq.count > decisionstart)
 309         {
 310           v = solv->decisionq.elements[--solv->decisionq.count];
 311           --solv->decisionq_why.count;
 312           vv = v > 0 ? v : -v;
 313           solv->decisionmap[vv] = 0;
 314         }
 315       ii = -1; /* restarts loop at 0 */
 316     }
 317
 318   /*
 319    * phase 2: now do the weak assertions
 320    */
 321   for (ii = 0; ii < solv->ruleassertions.count; ii++)
 322     {
 323       ri = solv->ruleassertions.elements[ii];
 324       r = solv->rules + ri;
 325       if (r->d < 0 || r->w2)                     /* disabled or no assertion */
 326         continue;
 327       if (ri >= solv->learntrules || !MAPTST(&solv->weakrulemap, ri))       /* skip non-weak */
 328         continue;
 329       v = r->p;
 330       vv = v > 0 ? v : -v;
 331       /*
 332        * decide !
 333        * (if not yet decided)
 334        */
 335       if (!solv->decisionmap[vv])
 336         {
 337           queue_push(&solv->decisionq, v);
 338           queue_push(&solv->decisionq_why, r - solv->rules);
 339           solv->decisionmap[vv] = v > 0 ? 1 : -1;
 340           IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
 341             {
 342               Solvable *s = solv->pool->solvables + vv;
 343               if (v < 0)
 344                 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "conflicting %s (weak assertion)\n", pool_solvable2str(solv->pool, s));
 345               else
 346                 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "installing  %s (weak assertion)\n", pool_solvable2str(solv->pool, s));
 347             }
 348           continue;
 349         }
 350       /*
 351        * previously decided, sane ?
 352        */
 353       if (v > 0 && solv->decisionmap[vv] > 0)
 354         continue;
 355       if (v < 0 && solv->decisionmap[vv] < 0)
 356         continue;
 357
 358       POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "assertion conflict, but I am weak, disabling ");
 359       solver_printrule(solv, SOLV_DEBUG_UNSOLVABLE, r);
 360
 361       if (ri >= solv->jobrules && ri < solv->jobrules_end)
 362         v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
 363       else
 364         v = ri;
 365       solver_disableproblem(solv, v);
 366       if (v < 0)
 367         solver_reenablepolicyrules(solv, -v);
 368     }
 369 }
 370
 371
 372 /*-------------------------------------------------------------------
 373  * enable/disable learnt rules
 374  *
 375  * we have enabled or disabled some of our rules. We now reenable all
 376  * of our learnt rules except the ones that were learnt from rules that
 377  * are now disabled.
 378  */
 379 static void
 380 enabledisablelearntrules(Solver *solv)
 381 {
 382   Pool *pool = solv->pool;
 383   Rule *r;
 384   Id why, *whyp;
 385   int i;
 386
 387   POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "enabledisablelearntrules called\n");
 388   for (i = solv->learntrules, r = solv->rules + i; i < solv->nrules; i++, r++)
 389     {
 390       whyp = solv->learnt_pool.elements + solv->learnt_why.elements[i - solv->learntrules];
 391       while ((why = *whyp++) != 0)
 392         {
 393           assert(why > 0 && why < i);
 394           if (solv->rules[why].d < 0)
 395             break;
 396         }
 397       /* why != 0: we found a disabled rule, disable the learnt rule */
 398       if (why && r->d >= 0)
 399         {
 400           IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS)
 401             {
 402               POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "disabling ");
 403               solver_printruleclass(solv, SOLV_DEBUG_SOLUTIONS, r);
 404             }
 405           solver_disablerule(solv, r);
 406         }
 407       else if (!why && r->d < 0)
 408         {
 409           IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS)
 410             {
 411               POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "re-enabling ");
 412               solver_printruleclass(solv, SOLV_DEBUG_SOLUTIONS, r);
 413             }
 414           solver_enablerule(solv, r);
 415         }
 416     }
 417 }
 418
 419
 420 /********************************************************************/
 421 /* watches */
 422
 423
 424 /*-------------------------------------------------------------------
 425  * makewatches
 426  *
 427  * initial setup for all watches
 428  */
 429
 430 static void
 431 makewatches(Solver *solv)
 432 {
 433   Rule *r;
 434   int i;
 435   int nsolvables = solv->pool->nsolvables;
 436
 437   solv_free(solv->watches);
 438                                        /* lower half for removals, upper half for installs */
 439   solv->watches = solv_calloc(2 * nsolvables, sizeof(Id));
 440 #if 1
 441   /* do it reverse so rpm rules get triggered first (XXX: obsolete?) */
 442   for (i = 1, r = solv->rules + solv->nrules - 1; i < solv->nrules; i++, r--)
 443 #else
 444   for (i = 1, r = solv->rules + 1; i < solv->nrules; i++, r++)
 445 #endif
 446     {
 447       if (!r->w2)               /* assertions do not need watches */
 448         continue;
 449
 450       /* see addwatches_rule(solv, r) */
 451       r->n1 = solv->watches[nsolvables + r->w1];
 452       solv->watches[nsolvables + r->w1] = r - solv->rules;
 453
 454       r->n2 = solv->watches[nsolvables + r->w2];
 455       solv->watches[nsolvables + r->w2] = r - solv->rules;
 456     }
 457 }
 458
 459
 460 /*-------------------------------------------------------------------
 461  *
 462  * add watches (for a new learned rule)
 463  * sets up watches for a single rule
 464  *
 465  * see also makewatches() above.
 466  */
 467
 468 static inline void
 469 addwatches_rule(Solver *solv, Rule *r)
 470 {
 471   int nsolvables = solv->pool->nsolvables;
 472
 473   r->n1 = solv->watches[nsolvables + r->w1];
 474   solv->watches[nsolvables + r->w1] = r - solv->rules;
 475
 476   r->n2 = solv->watches[nsolvables + r->w2];
 477   solv->watches[nsolvables + r->w2] = r - solv->rules;
 478 }
 479
 480
 481 /********************************************************************/
 482 /*
 483  * rule propagation
 484  */
 485
 486
 487 /* shortcuts to check if a literal (positive or negative) assignment
 488  * evaluates to 'true' or 'false'
 489  */
 490 #define DECISIONMAP_TRUE(p) ((p) > 0 ? (decisionmap[p] > 0) : (decisionmap[-p] < 0))
 491 #define DECISIONMAP_FALSE(p) ((p) > 0 ? (decisionmap[p] < 0) : (decisionmap[-p] > 0))
 492 #define DECISIONMAP_UNDEF(p) (decisionmap[(p) > 0 ? (p) : -(p)] == 0)
 493
 494 /*-------------------------------------------------------------------
 495  *
 496  * propagate
 497  *
 498  * make decision and propagate to all rules
 499  *
 500  * Evaluate each term affected by the decision (linked through watches).
 501  * If we find unit rules we make new decisions based on them.
 502  *
 503  * return : 0 = everything is OK
 504  *          rule = conflict found in this rule
 505  */
 506
 507 static Rule *
 508 propagate(Solver *solv, int level)
 509 {
 510   Pool *pool = solv->pool;
 511   Id *rp, *next_rp;           /* rule pointer, next rule pointer in linked list */
 512   Rule *r;                    /* rule */
 513   Id p, pkg, other_watch;
 514   Id *dp;
 515   Id *decisionmap = solv->decisionmap;
 516
 517   Id *watches = solv->watches + pool->nsolvables;   /* place ptr in middle */
 518
 519   POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "----- propagate -----\n");
 520
 521   /* foreach non-propagated decision */
 522   while (solv->propagate_index < solv->decisionq.count)
 523     {
 524         /*
 525          * 'pkg' was just decided
 526          * negate because our watches trigger if literal goes FALSE
 527          */
 528       pkg = -solv->decisionq.elements[solv->propagate_index++];
 529
 530       IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
 531         {
 532           POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "propagate for decision %d level %d\n", -pkg, level);
 533           solver_printruleelement(solv, SOLV_DEBUG_PROPAGATE, 0, -pkg);
 534         }
 535
 536       /* foreach rule where 'pkg' is now FALSE */
 537       for (rp = watches + pkg; *rp; rp = next_rp)
 538         {
 539           r = solv->rules + *rp;
 540           if (r->d < 0)
 541             {
 542               /* rule is disabled, goto next */
 543               if (pkg == r->w1)
 544                 next_rp = &r->n1;
 545               else
 546                 next_rp = &r->n2;
 547               continue;
 548             }
 549
 550           IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
 551             {
 552               POOL_DEBUG(SOLV_DEBUG_PROPAGATE,"  watch triggered ");
 553               solver_printrule(solv, SOLV_DEBUG_PROPAGATE, r);
 554             }
 555
 556             /* 'pkg' was just decided (was set to FALSE)
 557              *
 558              *  now find other literal watch, check clause
 559              *   and advance on linked list
 560              */
 561           if (pkg == r->w1)
 562             {
 563               other_watch = r->w2;
 564               next_rp = &r->n1;
 565             }
 566           else
 567             {
 568               other_watch = r->w1;
 569               next_rp = &r->n2;
 570             }
 571
 572             /*
 573              * This term is already true (through the other literal)
 574              * so we have nothing to do
 575              */
 576           if (DECISIONMAP_TRUE(other_watch))
 577             continue;
 578
 579             /*
 580              * The other literal is FALSE or UNDEF
 581              *
 582              */
 583
 584           if (r->d)
 585             {
 586               /* Not a binary clause, try to move our watch.
 587                *
 588                * Go over all literals and find one that is
 589                *   not other_watch
 590                *   and not FALSE
 591                *
 592                * (TRUE is also ok, in that case the rule is fulfilled)
 593                */
 594               if (r->p                                /* we have a 'p' */
 595                   && r->p != other_watch              /* which is not watched */
 596                   && !DECISIONMAP_FALSE(r->p))        /* and not FALSE */
 597                 {
 598                   p = r->p;
 599                 }
 600               else                                    /* go find a 'd' to make 'true' */
 601                 {
 602                   /* foreach p in 'd'
 603                      we just iterate sequentially, doing it in another order just changes the order of decisions, not the decisions itself
 604                    */
 605                   for (dp = pool->whatprovidesdata + r->d; (p = *dp++) != 0;)
 606                     {
 607                       if (p != other_watch              /* which is not watched */
 608                           && !DECISIONMAP_FALSE(p))     /* and not FALSE */
 609                         break;
 610                     }
 611                 }
 612
 613               if (p)
 614                 {
 615                   /*
 616                    * if we found some p that is UNDEF or TRUE, move
 617                    * watch to it
 618                    */
 619                   IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
 620                     {
 621                       if (p > 0)
 622                         POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "    -> move w%d to %s\n", (pkg == r->w1 ? 1 : 2), pool_solvid2str(pool, p));
 623                       else
 624                         POOL_DEBUG(SOLV_DEBUG_PROPAGATE,"    -> move w%d to !%s\n", (pkg == r->w1 ? 1 : 2), pool_solvid2str(pool, -p));
 625                     }
 626
 627                   *rp = *next_rp;
 628                   next_rp = rp;
 629
 630                   if (pkg == r->w1)
 631                     {
 632                       r->w1 = p;
 633                       r->n1 = watches[p];
 634                     }
 635                   else
 636                     {
 637                       r->w2 = p;
 638                       r->n2 = watches[p];
 639                     }
 640                   watches[p] = r - solv->rules;
 641                   continue;
 642                 }
 643               /* search failed, thus all unwatched literals are FALSE */
 644
 645             } /* not binary */
 646
 647           /*
 648            * unit clause found, set literal other_watch to TRUE
 649            */
 650
 651           if (DECISIONMAP_FALSE(other_watch))      /* check if literal is FALSE */
 652             return r;                              /* eek, a conflict! */
 653
 654           IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
 655             {
 656               POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "   unit ");
 657               solver_printrule(solv, SOLV_DEBUG_PROPAGATE, r);
 658             }
 659
 660           if (other_watch > 0)
 661             decisionmap[other_watch] = level;    /* install! */
 662           else
 663             decisionmap[-other_watch] = -level;  /* remove! */
 664
 665           queue_push(&solv->decisionq, other_watch);
 666           queue_push(&solv->decisionq_why, r - solv->rules);
 667
 668           IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
 669             {
 670               if (other_watch > 0)
 671                 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "    -> decided to install %s\n", pool_solvid2str(pool, other_watch));
 672               else
 673                 POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "    -> decided to conflict %s\n", pool_solvid2str(pool, -other_watch));
 674             }
 675
 676         } /* foreach rule involving 'pkg' */
 677
 678     } /* while we have non-decided decisions */
 679
 680   POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "----- propagate end-----\n");
 681
 682   return 0;     /* all is well */
 683 }
 684
 685
 686 /********************************************************************/
 687 /* Analysis */
 688
 689 /*-------------------------------------------------------------------
 690  *
 691  * analyze
 692  *   and learn
 693  */
 694
 695 static int
 696 analyze(Solver *solv, int level, Rule *c, int *pr, int *dr, int *whyp)
 697 {
 698   Pool *pool = solv->pool;
 699   Queue r;
 700   Id r_buf[4];
 701   int rlevel = 1;
 702   Map seen;             /* global? */
 703   Id d, v, vv, *dp, why;
 704   int l, i, idx;
 705   int num = 0, l1num = 0;
 706   int learnt_why = solv->learnt_pool.count;
 707   Id *decisionmap = solv->decisionmap;
 708
 709   queue_init_buffer(&r, r_buf, sizeof(r_buf)/sizeof(*r_buf));
 710
 711   POOL_DEBUG(SOLV_DEBUG_ANALYZE, "ANALYZE at %d ----------------------\n", level);
 712   map_init(&seen, pool->nsolvables);
 713   idx = solv->decisionq.count;
 714   for (;;)
 715     {
 716       IF_POOLDEBUG (SOLV_DEBUG_ANALYZE)
 717         solver_printruleclass(solv, SOLV_DEBUG_ANALYZE, c);
 718       queue_push(&solv->learnt_pool, c - solv->rules);
 719       d = c->d < 0 ? -c->d - 1 : c->d;
 720       dp = d ? pool->whatprovidesdata + d : 0;
 721       /* go through all literals of the rule */
 722       for (i = -1; ; i++)
 723         {
 724           if (i == -1)
 725             v = c->p;
 726           else if (d == 0)
 727             v = i ? 0 : c->w2;
 728           else
 729             v = *dp++;
 730           if (v == 0)
 731             break;
 732
 733           if (DECISIONMAP_TRUE(v))      /* the one true literal */
 734             continue;
 735           vv = v > 0 ? v : -v;
 736           if (MAPTST(&seen, vv))
 737             continue;
 738           l = solv->decisionmap[vv];
 739           if (l < 0)
 740             l = -l;
 741           MAPSET(&seen, vv);            /* mark that we also need to look at this literal */
 742           if (l == 1)
 743             l1num++;                    /* need to do this one in level1 pass */
 744           else if (l == level)
 745             num++;                      /* need to do this one as well */
 746           else
 747             {
 748               queue_push(&r, v);        /* not level1 or conflict level, add to new rule */
 749               if (l > rlevel)
 750                 rlevel = l;
 751             }
 752         }
 753 l1retry:
 754       if (!num && !--l1num)
 755         break;  /* all level 1 literals done */
 756
 757       /* find the next literal to investigate */
 758       /* (as num + l1num > 0, we know that we'll always find one) */
 759       for (;;)
 760         {
 761           assert(idx > 0);
 762           v = solv->decisionq.elements[--idx];
 763           vv = v > 0 ? v : -v;
 764           if (MAPTST(&seen, vv))
 765             break;
 766         }
 767       MAPCLR(&seen, vv);
 768
 769       if (num && --num == 0)
 770         {
 771           *pr = -v;     /* so that v doesn't get lost */
 772           if (!l1num)
 773             break;
 774           POOL_DEBUG(SOLV_DEBUG_ANALYZE, "got %d involved level 1 decisions\n", l1num);
 775           /* clear non-l1 bits from seen map */
 776           for (i = 0; i < r.count; i++)
 777             {
 778               v = r.elements[i];
 779               MAPCLR(&seen, v > 0 ? v : -v);
 780             }
 781           /* only level 1 marks left in seen map */
 782           l1num++;      /* as l1retry decrements it */
 783           goto l1retry;
 784         }
 785
 786       why = solv->decisionq_why.elements[idx];
 787       if (why <= 0)     /* just in case, maybe for SYSTEMSOLVABLE */
 788         goto l1retry;
 789       c = solv->rules + why;
 790     }
 791   map_free(&seen);
 792
 793   if (r.count == 0)
 794     *dr = 0;
 795   else if (r.count == 1 && r.elements[0] < 0)
 796     *dr = r.elements[0];
 797   else
 798     *dr = pool_queuetowhatprovides(pool, &r);
 799   IF_POOLDEBUG (SOLV_DEBUG_ANALYZE)
 800     {
 801       POOL_DEBUG(SOLV_DEBUG_ANALYZE, "learned rule for level %d (am %d)\n", rlevel, level);
 802       solver_printruleelement(solv, SOLV_DEBUG_ANALYZE, 0, *pr);
 803       for (i = 0; i < r.count; i++)
 804         solver_printruleelement(solv, SOLV_DEBUG_ANALYZE, 0, r.elements[i]);
 805     }
 806   /* push end marker on learnt reasons stack */
 807   queue_push(&solv->learnt_pool, 0);
 808   if (whyp)
 809     *whyp = learnt_why;
 810   queue_free(&r);
 811   solv->stats_learned++;
 812   return rlevel;
 813 }
 814
 815
 816 /*-------------------------------------------------------------------
 817  *
 818  * solver_reset
 819  *
 820  * reset all solver decisions
 821  * called after rules have been enabled/disabled
 822  */
 823
 824 void
 825 solver_reset(Solver *solv)
 826 {
 827   Pool *pool = solv->pool;
 828   int i;
 829   Id v;
 830
 831   /* rewind all decisions */
 832   for (i = solv->decisionq.count - 1; i >= 0; i--)
 833     {
 834       v = solv->decisionq.elements[i];
 835       solv->decisionmap[v > 0 ? v : -v] = 0;
 836     }
 837   solv->decisionq_why.count = 0;
 838   solv->decisionq.count = 0;
 839   solv->recommends_index = -1;
 840   solv->propagate_index = 0;
 841   solv->branches.count = 0;
 842
 843   /* adapt learnt rule status to new set of enabled/disabled rules */
 844   enabledisablelearntrules(solv);
 845
 846   /* redo all assertion rule decisions */
 847   makeruledecisions(solv);
 848   POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "decisions so far: %d\n", solv->decisionq.count);
 849 }
 850
 851
 852 /*-------------------------------------------------------------------
 853  *
 854  * analyze_unsolvable_rule
 855  *
 856  * recursion helper used by analyze_unsolvable
 857  */
 858
 859 static void
 860 analyze_unsolvable_rule(Solver *solv, Rule *r, Id *lastweakp, Map *rseen)
 861 {
 862   Pool *pool = solv->pool;
 863   int i;
 864   Id why = r - solv->rules;
 865
 866   IF_POOLDEBUG (SOLV_DEBUG_UNSOLVABLE)
 867     solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE, r);
 868   if (solv->learntrules && why >= solv->learntrules)
 869     {
 870       if (MAPTST(rseen, why - solv->learntrules))
 871         return;
 872       MAPSET(rseen, why - solv->learntrules);
 873       for (i = solv->learnt_why.elements[why - solv->learntrules]; solv->learnt_pool.elements[i]; i++)
 874         if (solv->learnt_pool.elements[i] > 0)
 875           analyze_unsolvable_rule(solv, solv->rules + solv->learnt_pool.elements[i], lastweakp, rseen);
 876       return;
 877     }
 878   if (MAPTST(&solv->weakrulemap, why))
 879     if (!*lastweakp || why > *lastweakp)
 880       *lastweakp = why;
 881   /* do not add rpm rules to problem */
 882   if (why < solv->rpmrules_end)
 883     return;
 884   /* turn rule into problem */
 885   if (why >= solv->jobrules && why < solv->jobrules_end)
 886     why = -(solv->ruletojob.elements[why - solv->jobrules] + 1);
 887   /* normalize dup/infarch rules */
 888   if (why > solv->infarchrules && why < solv->infarchrules_end)
 889     {
 890       Id name = pool->solvables[-solv->rules[why].p].name;
 891       while (why > solv->infarchrules && pool->solvables[-solv->rules[why - 1].p].name == name)
 892         why--;
 893     }
 894   if (why > solv->duprules && why < solv->duprules_end)
 895     {
 896       Id name = pool->solvables[-solv->rules[why].p].name;
 897       while (why > solv->duprules && pool->solvables[-solv->rules[why - 1].p].name == name)
 898         why--;
 899     }
 900
 901   /* return if problem already countains our rule */
 902   if (solv->problems.count)
 903     {
 904       for (i = solv->problems.count - 1; i >= 0; i--)
 905         if (solv->problems.elements[i] == 0)    /* end of last problem reached? */
 906           break;
 907         else if (solv->problems.elements[i] == why)
 908           return;
 909     }
 910   queue_push(&solv->problems, why);
 911 }
 912
 913
 914 /*-------------------------------------------------------------------
 915  *
 916  * analyze_unsolvable
 917  *
 918  * We know that the problem is not solvable. Record all involved
 919  * rules (i.e. the "proof") into solv->learnt_pool.
 920  * Record the learnt pool index and all non-rpm rules into
 921  * solv->problems. (Our solutions to fix the problems are to
 922  * disable those rules.)
 923  *
 924  * If the proof contains at least one weak rule, we disable the
 925  * last of them.
 926  *
 927  * Otherwise we return 0 if disablerules is not set or disable
 928  * _all_ of the problem rules and return 1.
 929  *
 930  * return: 1 - disabled some rules, try again
 931  *         0 - hopeless
 932  */
 933
 934 static int
 935 analyze_unsolvable(Solver *solv, Rule *cr, int disablerules)
 936 {
 937   Pool *pool = solv->pool;
 938   Rule *r;
 939   Map seen;             /* global to speed things up? */
 940   Map rseen;
 941   Id d, v, vv, *dp, why;
 942   int l, i, idx;
 943   Id *decisionmap = solv->decisionmap;
 944   int oldproblemcount;
 945   int oldlearntpoolcount;
 946   Id lastweak;
 947   int record_proof = 1;
 948
 949   POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "ANALYZE UNSOLVABLE ----------------------\n");
 950   solv->stats_unsolvable++;
 951   oldproblemcount = solv->problems.count;
 952   oldlearntpoolcount = solv->learnt_pool.count;
 953
 954   /* make room for proof index */
 955   /* must update it later, as analyze_unsolvable_rule would confuse
 956    * it with a rule index if we put the real value in already */
 957   queue_push(&solv->problems, 0);
 958
 959   r = cr;
 960   map_init(&seen, pool->nsolvables);
 961   map_init(&rseen, solv->learntrules ? solv->nrules - solv->learntrules : 0);
 962   if (record_proof)
 963     queue_push(&solv->learnt_pool, r - solv->rules);
 964   lastweak = 0;
 965   analyze_unsolvable_rule(solv, r, &lastweak, &rseen);
 966   d = r->d < 0 ? -r->d - 1 : r->d;
 967   dp = d ? pool->whatprovidesdata + d : 0;
 968   for (i = -1; ; i++)
 969     {
 970       if (i == -1)
 971         v = r->p;
 972       else if (d == 0)
 973         v = i ? 0 : r->w2;
 974       else
 975         v = *dp++;
 976       if (v == 0)
 977         break;
 978       if (DECISIONMAP_TRUE(v))  /* the one true literal */
 979           continue;
 980       vv = v > 0 ? v : -v;
 981       l = solv->decisionmap[vv];
 982       if (l < 0)
 983         l = -l;
 984       MAPSET(&seen, vv);
 985     }
 986   idx = solv->decisionq.count;
 987   while (idx > 0)
 988     {
 989       v = solv->decisionq.elements[--idx];
 990       vv = v > 0 ? v : -v;
 991       if (!MAPTST(&seen, vv))
 992         continue;
 993       why = solv->decisionq_why.elements[idx];
 994       assert(why > 0);
 995       if (record_proof)
 996         queue_push(&solv->learnt_pool, why);
 997       r = solv->rules + why;
 998       analyze_unsolvable_rule(solv, r, &lastweak, &rseen);
 999       d = r->d < 0 ? -r->d - 1 : r->d;
1000       dp = d ? pool->whatprovidesdata + d : 0;
1001       for (i = -1; ; i++)
1002         {
1003           if (i == -1)
1004             v = r->p;
1005           else if (d == 0)
1006             v = i ? 0 : r->w2;
1007           else
1008             v = *dp++;
1009           if (v == 0)
1010             break;
1011           if (DECISIONMAP_TRUE(v))      /* the one true literal */
1012               continue;
1013           vv = v > 0 ? v : -v;
1014           l = solv->decisionmap[vv];
1015           if (l < 0)
1016             l = -l;
1017           MAPSET(&seen, vv);
1018         }
1019     }
1020   map_free(&seen);
1021   map_free(&rseen);
1022   queue_push(&solv->problems, 0);       /* mark end of this problem */
1023
1024   if (lastweak)
1025     {
1026       Id v;
1027       /* disable last weak rule */
1028       solv->problems.count = oldproblemcount;
1029       solv->learnt_pool.count = oldlearntpoolcount;
1030       if (lastweak >= solv->jobrules && lastweak < solv->jobrules_end)
1031         v = -(solv->ruletojob.elements[lastweak - solv->jobrules] + 1);
1032       else
1033         v = lastweak;
1034       POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "disabling ");
1035       solver_printruleclass(solv, SOLV_DEBUG_UNSOLVABLE, solv->rules + lastweak);
1036       if (lastweak >= solv->choicerules && lastweak < solv->choicerules_end)
1037         solver_disablechoicerules(solv, solv->rules + lastweak);
1038       solver_disableproblem(solv, v);
1039       if (v < 0)
1040         solver_reenablepolicyrules(solv, -v);
1041       solver_reset(solv);
1042       return 1;
1043     }
1044
1045   /* finish proof */
1046   if (record_proof)
1047     {
1048       queue_push(&solv->learnt_pool, 0);
1049       solv->problems.elements[oldproblemcount] = oldlearntpoolcount;
1050     }
1051
1052   /* + 2: index + trailing zero */
1053   if (disablerules && oldproblemcount + 2 < solv->problems.count)
1054     {
1055       for (i = oldproblemcount + 1; i < solv->problems.count - 1; i++)
1056         solver_disableproblem(solv, solv->problems.elements[i]);
1057       /* XXX: might want to enable all weak rules again */
1058       solver_reset(solv);
1059       return 1;
1060     }
1061   POOL_DEBUG(SOLV_DEBUG_UNSOLVABLE, "UNSOLVABLE\n");
1062   return 0;
1063 }
1064
1065
1066 /********************************************************************/
1067 /* Decision revert */
1068
1069 /*-------------------------------------------------------------------
1070  *
1071  * revert
1072  * revert decisionq to a level
1073  */
1074
1075 static void
1076 revert(Solver *solv, int level)
1077 {
1078   Pool *pool = solv->pool;
1079   Id v, vv;
1080   while (solv->decisionq.count)
1081     {
1082       v = solv->decisionq.elements[solv->decisionq.count - 1];
1083       vv = v > 0 ? v : -v;
1084       if (solv->decisionmap[vv] <= level && solv->decisionmap[vv] >= -level)
1085         break;
1086       POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "reverting decision %d at %d\n", v, solv->decisionmap[vv]);
1087       solv->decisionmap[vv] = 0;
1088       solv->decisionq.count--;
1089       solv->decisionq_why.count--;
1090       solv->propagate_index = solv->decisionq.count;
1091     }
1092   while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] <= -level)
1093     {
1094       solv->branches.count--;
1095       while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] >= 0)
1096         solv->branches.count--;
1097     }
1098   solv->recommends_index = -1;
1099 }
1100
1101
1102 /*-------------------------------------------------------------------
1103  *
1104  * watch2onhighest - put watch2 on literal with highest level
1105  */
1106
1107 static inline void
1108 watch2onhighest(Solver *solv, Rule *r)
1109 {
1110   int l, wl = 0;
1111   Id d, v, *dp;
1112
1113   d = r->d < 0 ? -r->d - 1 : r->d;
1114   if (!d)
1115     return;     /* binary rule, both watches are set */
1116   dp = solv->pool->whatprovidesdata + d;
1117   while ((v = *dp++) != 0)
1118     {
1119       l = solv->decisionmap[v < 0 ? -v : v];
1120       if (l < 0)
1121         l = -l;
1122       if (l > wl)
1123         {
1124           r->w2 = dp[-1];
1125           wl = l;
1126         }
1127     }
1128 }
1129
1130
1131 /*-------------------------------------------------------------------
1132  *
1133  * setpropagatelearn
1134  *
1135  * add free decision (solvable to install) to decisionq
1136  * increase level and propagate decision
1137  * return if no conflict.
1138  *
1139  * in conflict case, analyze conflict rule, add resulting
1140  * rule to learnt rule set, make decision from learnt
1141  * rule (always unit) and re-propagate.
1142  *
1143  * returns the new solver level or 0 if unsolvable
1144  *
1145  */
1146
1147 static int
1148 setpropagatelearn(Solver *solv, int level, Id decision, int disablerules, Id ruleid)
1149 {
1150   Pool *pool = solv->pool;
1151   Rule *r;
1152   Id p = 0, d = 0;
1153   int l, why;
1154
1155   assert(ruleid >= 0);
1156   if (decision)
1157     {
1158       level++;
1159       if (decision > 0)
1160         solv->decisionmap[decision] = level;
1161       else
1162         solv->decisionmap[-decision] = -level;
1163       queue_push(&solv->decisionq, decision);
1164       queue_push(&solv->decisionq_why, -ruleid);        /* <= 0 -> free decision */
1165     }
1166   for (;;)
1167     {
1168       r = propagate(solv, level);
1169       if (!r)
1170         break;
1171       if (level == 1)
1172         return analyze_unsolvable(solv, r, disablerules);
1173       POOL_DEBUG(SOLV_DEBUG_ANALYZE, "conflict with rule #%d\n", (int)(r - solv->rules));
1174       l = analyze(solv, level, r, &p, &d, &why);        /* learnt rule in p and d */
1175       assert(l > 0 && l < level);
1176       POOL_DEBUG(SOLV_DEBUG_ANALYZE, "reverting decisions (level %d -> %d)\n", level, l);
1177       level = l;
1178       revert(solv, level);
1179       r = solver_addrule(solv, p, d);
1180       assert(r);
1181       assert(solv->learnt_why.count == (r - solv->rules) - solv->learntrules);
1182       queue_push(&solv->learnt_why, why);
1183       if (d)
1184         {
1185           /* at least 2 literals, needs watches */
1186           watch2onhighest(solv, r);
1187           addwatches_rule(solv, r);
1188         }
1189       else
1190         {
1191           /* learnt rule is an assertion */
1192           queue_push(&solv->ruleassertions, r - solv->rules);
1193         }
1194       /* the new rule is unit by design */
1195       solv->decisionmap[p > 0 ? p : -p] = p > 0 ? level : -level;
1196       queue_push(&solv->decisionq, p);
1197       queue_push(&solv->decisionq_why, r - solv->rules);
1198       IF_POOLDEBUG (SOLV_DEBUG_ANALYZE)
1199         {
1200           POOL_DEBUG(SOLV_DEBUG_ANALYZE, "decision: ");
1201           solver_printruleelement(solv, SOLV_DEBUG_ANALYZE, 0, p);
1202           POOL_DEBUG(SOLV_DEBUG_ANALYZE, "new rule: ");
1203           solver_printrule(solv, SOLV_DEBUG_ANALYZE, r);
1204         }
1205     }
1206   return level;
1207 }
1208
1209
1210 /*-------------------------------------------------------------------
1211  *
1212  * select and install
1213  *
1214  * install best package from the queue. We add an extra package, inst, if
1215  * provided. See comment in weak install section.
1216  *
1217  * returns the new solver level or 0 if unsolvable
1218  *
1219  */
1220
1221 static int
1222 selectandinstall(Solver *solv, int level, Queue *dq, int disablerules, Id ruleid)
1223 {
1224   Pool *pool = solv->pool;
1225   Id p;
1226   int i;
1227
1228   if (dq->count > 1)
1229     policy_filter_unwanted(solv, dq, POLICY_MODE_CHOOSE);
1230   if (dq->count > 1)
1231     {
1232       /* XXX: didn't we already do that? */
1233       /* XXX: shouldn't we prefer installed packages? */
1234       /* XXX: move to policy.c? */
1235       /* choose the supplemented one */
1236       for (i = 0; i < dq->count; i++)
1237         if (solver_is_supplementing(solv, pool->solvables + dq->elements[i]))
1238           {
1239             dq->elements[0] = dq->elements[i];
1240             dq->count = 1;
1241             break;
1242           }
1243     }
1244   if (dq->count > 1)
1245     {
1246       /* multiple candidates, open a branch */
1247       for (i = 1; i < dq->count; i++)
1248         queue_push(&solv->branches, dq->elements[i]);
1249       queue_push(&solv->branches, -level);
1250     }
1251   p = dq->elements[0];
1252
1253   POOL_DEBUG(SOLV_DEBUG_POLICY, "installing %s\n", pool_solvid2str(pool, p));
1254
1255   return setpropagatelearn(solv, level, p, disablerules, ruleid);
1256 }
1257
1258
1259 /********************************************************************/
1260 /* Main solver interface */
1261
1262
1263 /*-------------------------------------------------------------------
1264  *
1265  * solver_create
1266  * create solver structure
1267  *
1268  * pool: all available solvables
1269  * installed: installed Solvables
1270  *
1271  *
1272  * Upon solving, rules are created to flag the Solvables
1273  * of the 'installed' Repo as installed.
1274  */
1275
1276 Solver *
1277 solver_create(Pool *pool)
1278 {
1279   Solver *solv;
1280   solv = (Solver *)solv_calloc(1, sizeof(Solver));
1281   solv->pool = pool;
1282   solv->installed = pool->installed;
1283
1284   solv->dup_allowdowngrade = 1;
1285   solv->dup_allowarchchange = 1;
1286   solv->dup_allowvendorchange = 1;
1287
1288   queue_init(&solv->ruletojob);
1289   queue_init(&solv->decisionq);
1290   queue_init(&solv->decisionq_why);
1291   queue_init(&solv->problems);
1292   queue_init(&solv->orphaned);
1293   queue_init(&solv->learnt_why);
1294   queue_init(&solv->learnt_pool);
1295   queue_init(&solv->branches);
1296   queue_init(&solv->weakruleq);
1297   queue_init(&solv->ruleassertions);
1298
1299   queue_push(&solv->learnt_pool, 0);    /* so that 0 does not describe a proof */
1300
1301   map_init(&solv->recommendsmap, pool->nsolvables);
1302   map_init(&solv->suggestsmap, pool->nsolvables);
1303   map_init(&solv->noupdate, solv->installed ? solv->installed->end - solv->installed->start : 0);
1304   solv->recommends_index = 0;
1305
1306   solv->decisionmap = (Id *)solv_calloc(pool->nsolvables, sizeof(Id));
1307   solv->nrules = 1;
1308   solv->rules = solv_extend_resize(solv->rules, solv->nrules, sizeof(Rule), RULES_BLOCK);
1309   memset(solv->rules, 0, sizeof(Rule));
1310
1311   return solv;
1312 }
1313
1314
1315 /*-------------------------------------------------------------------
1316  *
1317  * solver_free
1318  */
1319
1320 void
1321 solver_free(Solver *solv)
1322 {
1323   queue_free(&solv->job);
1324   queue_free(&solv->ruletojob);
1325   queue_free(&solv->decisionq);
1326   queue_free(&solv->decisionq_why);
1327   queue_free(&solv->learnt_why);
1328   queue_free(&solv->learnt_pool);
1329   queue_free(&solv->problems);
1330   queue_free(&solv->solutions);
1331   queue_free(&solv->orphaned);
1332   queue_free(&solv->branches);
1333   queue_free(&solv->weakruleq);
1334   queue_free(&solv->ruleassertions);
1335   if (solv->cleandeps_updatepkgs)
1336     {
1337       queue_free(solv->cleandeps_updatepkgs);
1338       solv->cleandeps_updatepkgs = solv_free(solv->cleandeps_updatepkgs);
1339     }
1340   if (solv->cleandeps_mistakes)
1341     {
1342       queue_free(solv->cleandeps_mistakes);
1343       solv->cleandeps_mistakes = solv_free(solv->cleandeps_mistakes);
1344     }
1345
1346   map_free(&solv->recommendsmap);
1347   map_free(&solv->suggestsmap);
1348   map_free(&solv->noupdate);
1349   map_free(&solv->weakrulemap);
1350   map_free(&solv->noobsoletes);
1351
1352   map_free(&solv->updatemap);
1353   map_free(&solv->fixmap);
1354   map_free(&solv->dupmap);
1355   map_free(&solv->dupinvolvedmap);
1356   map_free(&solv->droporphanedmap);
1357   map_free(&solv->cleandepsmap);
1358
1359   solv_free(solv->decisionmap);
1360   solv_free(solv->rules);
1361   solv_free(solv->watches);
1362   solv_free(solv->obsoletes);
1363   solv_free(solv->obsoletes_data);
1364   solv_free(solv->multiversionupdaters);
1365   solv_free(solv->choicerules_ref);
1366   solv_free(solv);
1367 }
1368
1369 int
1370 solver_get_flag(Solver *solv, int flag)
1371 {
1372   switch (flag)
1373   {
1374   case SOLVER_FLAG_ALLOW_DOWNGRADE:
1375     return solv->allowdowngrade;
1376   case SOLVER_FLAG_ALLOW_ARCHCHANGE:
1377     return solv->allowarchchange;
1378   case SOLVER_FLAG_ALLOW_VENDORCHANGE:
1379     return solv->allowvendorchange;
1380   case SOLVER_FLAG_ALLOW_UNINSTALL:
1381     return solv->allowuninstall;
1382   case SOLVER_FLAG_NO_UPDATEPROVIDE:
1383     return solv->noupdateprovide;
1384   case SOLVER_FLAG_SPLITPROVIDES:
1385     return solv->dosplitprovides;
1386   case SOLVER_FLAG_IGNORE_RECOMMENDED:
1387     return solv->dontinstallrecommended;
1388   case SOLVER_FLAG_IGNORE_ALREADY_RECOMMENDED:
1389     return solv->ignorealreadyrecommended;
1390   case SOLVER_FLAG_NO_INFARCHCHECK:
1391     return solv->noinfarchcheck;
1392   default:
1393     break;
1394   }
1395   return -1;
1396 }
1397
1398 int
1399 solver_set_flag(Solver *solv, int flag, int value)
1400 {
1401   int old = solver_get_flag(solv, flag);
1402   switch (flag)
1403   {
1404   case SOLVER_FLAG_ALLOW_DOWNGRADE:
1405     solv->allowdowngrade = value;
1406     break;
1407   case SOLVER_FLAG_ALLOW_ARCHCHANGE:
1408     solv->allowarchchange = value;
1409     break;
1410   case SOLVER_FLAG_ALLOW_VENDORCHANGE:
1411     solv->allowvendorchange = value;
1412     break;
1413   case SOLVER_FLAG_ALLOW_UNINSTALL:
1414     solv->allowuninstall = value;
1415     break;
1416   case SOLVER_FLAG_NO_UPDATEPROVIDE:
1417     solv->noupdateprovide = value;
1418     break;
1419   case SOLVER_FLAG_SPLITPROVIDES:
1420     solv->dosplitprovides = value;
1421     break;
1422   case SOLVER_FLAG_IGNORE_RECOMMENDED:
1423     solv->dontinstallrecommended = value;
1424     break;
1425   case SOLVER_FLAG_IGNORE_ALREADY_RECOMMENDED:
1426     solv->ignorealreadyrecommended = value;
1427     break;
1428   case SOLVER_FLAG_NO_INFARCHCHECK:
1429     solv->noinfarchcheck = value;
1430     break;
1431   default:
1432     break;
1433   }
1434   return old;
1435 }
1436
1437 int
1438 cleandeps_check_mistakes(Solver *solv, int level)
1439 {
1440   Pool *pool = solv->pool;
1441   Rule *r;
1442   Id p, *dp;
1443   int i;
1444   int mademistake = 0;
1445
1446   if (!solv->cleandepsmap.size)
1447     return level;
1448   /* check for mistakes */
1449   for (i = solv->installed->start; i < solv->installed->end; i++)
1450     {
1451       if (!MAPTST(&solv->cleandepsmap, i - solv->installed->start))
1452         continue;
1453       r = solv->rules + solv->featurerules + (i - solv->installed->start);
1454       /* a mistake is when the featurerule is true but the updaterule is false */
1455       if (r->p)
1456         {
1457           FOR_RULELITERALS(p, dp, r)
1458             if (p > 0 && solv->decisionmap[p] > 0)
1459               break;
1460           if (p)
1461             {
1462               r = solv->rules + solv->updaterules + (i - solv->installed->start);
1463               if (!r->p)
1464                 continue;
1465               FOR_RULELITERALS(p, dp, r)
1466                 if (p > 0 && solv->decisionmap[p] > 0)
1467                   break;
1468               if (!p)
1469                 {
1470                   POOL_DEBUG(SOLV_DEBUG_SOLVER, "cleandeps mistake: ");
1471                   solver_printruleclass(solv, SOLV_DEBUG_SOLVER, r);
1472                   POOL_DEBUG(SOLV_DEBUG_SOLVER, "feature rule: ");
1473                   solver_printruleclass(solv, SOLV_DEBUG_SOLVER, solv->rules + solv->featurerules + (i - solv->installed->start));
1474                   if (!solv->cleandeps_mistakes)
1475                     {
1476                       solv->cleandeps_mistakes = solv_calloc(1, sizeof(Queue));
1477                       queue_init(solv->cleandeps_mistakes);
1478                     }
1479                   queue_push(solv->cleandeps_mistakes, i);
1480                   MAPCLR(&solv->cleandepsmap, i - solv->installed->start);
1481                   mademistake = 1;
1482                 }
1483             }
1484         }
1485     }
1486   if (mademistake)
1487     {
1488       level = 1;
1489       revert(solv, level);
1490     }
1491   return level;
1492 }
1493
1494 /*-------------------------------------------------------------------
1495  *
1496  * solver_run_sat
1497  *
1498  * all rules have been set up, now actually run the solver
1499  *
1500  */
1501
1502 void
1503 solver_run_sat(Solver *solv, int disablerules, int doweak)
1504 {
1505   Queue dq;             /* local decisionqueue */
1506   Queue dqs;            /* local decisionqueue for supplements */
1507   int systemlevel;
1508   int level, olevel;
1509   Rule *r;
1510   int i, j, n;
1511   Solvable *s;
1512   Pool *pool = solv->pool;
1513   Id p, *dp;
1514   int minimizationsteps;
1515   int installedpos = solv->installed ? solv->installed->start : 0;
1516
1517   IF_POOLDEBUG (SOLV_DEBUG_RULE_CREATION)
1518     {
1519       POOL_DEBUG (SOLV_DEBUG_RULE_CREATION, "number of rules: %d\n", solv->nrules);
1520       for (i = 1; i < solv->nrules; i++)
1521         solver_printruleclass(solv, SOLV_DEBUG_RULE_CREATION, solv->rules + i);
1522     }
1523
1524   POOL_DEBUG(SOLV_DEBUG_SOLVER, "initial decisions: %d\n", solv->decisionq.count);
1525
1526   /* start SAT algorithm */
1527   level = 1;
1528   systemlevel = level + 1;
1529   POOL_DEBUG(SOLV_DEBUG_SOLVER, "solving...\n");
1530
1531   queue_init(&dq);
1532   queue_init(&dqs);
1533
1534   /*
1535    * here's the main loop:
1536    * 1) propagate new decisions (only needed once)
1537    * 2) fulfill jobs
1538    * 3) try to keep installed packages
1539    * 4) fulfill all unresolved rules
1540    * 5) install recommended packages
1541    * 6) minimalize solution if we had choices
1542    * if we encounter a problem, we rewind to a safe level and restart
1543    * with step 1
1544    */
1545
1546   minimizationsteps = 0;
1547   for (;;)
1548     {
1549       /*
1550        * initial propagation of the assertions
1551        */
1552       if (level == 1)
1553         {
1554           POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "propagating (propagate_index: %d;  size decisionq: %d)...\n", solv->propagate_index, solv->decisionq.count);
1555           if ((r = propagate(solv, level)) != 0)
1556             {
1557               if (analyze_unsolvable(solv, r, disablerules))
1558                 continue;
1559               level = 0;
1560               break;    /* unsolvable */
1561             }
1562         }
1563
1564       /*
1565        * resolve jobs first
1566        */
1567      if (level < systemlevel)
1568         {
1569           POOL_DEBUG(SOLV_DEBUG_SOLVER, "resolving job rules\n");
1570           for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++)
1571             {
1572               Id l;
1573               if (r->d < 0)             /* ignore disabled rules */
1574                 continue;
1575               queue_empty(&dq);
1576               FOR_RULELITERALS(l, dp, r)
1577                 {
1578                   if (l < 0)
1579                     {
1580                       if (solv->decisionmap[-l] <= 0)
1581                         break;
1582                     }
1583                   else
1584                     {
1585                       if (solv->decisionmap[l] > 0)
1586                         break;
1587                       if (solv->decisionmap[l] == 0)
1588                         queue_push(&dq, l);
1589                     }
1590                 }
1591               if (l || !dq.count)
1592                 continue;
1593               /* prune to installed if not updating */
1594               if (dq.count > 1 && solv->installed && !solv->updatemap_all)
1595                 {
1596                   int j, k;
1597                   for (j = k = 0; j < dq.count; j++)
1598                     {
1599                       Solvable *s = pool->solvables + dq.elements[j];
1600                       if (s->repo == solv->installed)
1601                         {
1602                           dq.elements[k++] = dq.elements[j];
1603                           if (solv->updatemap.size && MAPTST(&solv->updatemap, dq.elements[j] - solv->installed->start))
1604                             {
1605                               k = 0;    /* package wants to be updated, do not prune */
1606                               break;
1607                             }
1608                         }
1609                     }
1610                   if (k)
1611                     dq.count = k;
1612                 }
1613               olevel = level;
1614               level = selectandinstall(solv, level, &dq, disablerules, i);
1615               if (level == 0)
1616                 break;
1617               if (level <= olevel)
1618                 break;
1619             }
1620           if (level == 0)
1621             break;      /* unsolvable */
1622           systemlevel = level + 1;
1623           if (i < solv->jobrules_end)
1624             continue;
1625           solv->decisioncnt_update = solv->decisionq.count;
1626           solv->decisioncnt_keep = solv->decisionq.count;
1627         }
1628
1629       /*
1630        * installed packages
1631        */
1632       if (level < systemlevel && solv->installed && solv->installed->nsolvables && !solv->installed->disabled)
1633         {
1634           Repo *installed = solv->installed;
1635           int pass;
1636
1637           POOL_DEBUG(SOLV_DEBUG_SOLVER, "resolving installed packages\n");
1638           /* we use two passes if we need to update packages
1639            * to create a better user experience */
1640           for (pass = solv->updatemap.size ? 0 : 1; pass < 2; pass++)
1641             {
1642               int passlevel = level;
1643               if (pass == 1)
1644                 solv->decisioncnt_keep = solv->decisionq.count;
1645               /* start with installedpos, the position that gave us problems last time */
1646               for (i = installedpos, n = installed->start; n < installed->end; i++, n++)
1647                 {
1648                   Rule *rr;
1649                   Id d;
1650
1651                   if (i == installed->end)
1652                     i = installed->start;
1653                   s = pool->solvables + i;
1654                   if (s->repo != installed)
1655                     continue;
1656
1657                   if (solv->decisionmap[i] > 0)
1658                     continue;
1659                   if (!pass && solv->updatemap.size && !MAPTST(&solv->updatemap, i - installed->start))
1660                     continue;           /* updates first */
1661                   r = solv->rules + solv->updaterules + (i - installed->start);
1662                   rr = r;
1663                   if (!rr->p || rr->d < 0)      /* disabled -> look at feature rule */
1664                     rr -= solv->installed->end - solv->installed->start;
1665                   if (!rr->p)           /* identical to update rule? */
1666                     rr = r;
1667                   if (!rr->p)
1668                     continue;           /* orpaned package */
1669
1670                   /* XXX: noupdate check is probably no longer needed, as all jobs should
1671                    * already be satisfied */
1672                   /* Actually we currently still need it because of erase jobs */
1673                   /* if noupdate is set we do not look at update candidates */
1674                   queue_empty(&dq);
1675                   if (!MAPTST(&solv->noupdate, i - installed->start) && (solv->decisionmap[i] < 0 || solv->updatemap_all || (solv->updatemap.size && MAPTST(&solv->updatemap, i - installed->start)) || rr->p != i))
1676                     {
1677                       if (solv->noobsoletes.size && solv->multiversionupdaters
1678                              && (d = solv->multiversionupdaters[i - installed->start]) != 0)
1679                         {
1680                           /* special multiversion handling, make sure best version is chosen */
1681                           queue_push(&dq, i);
1682                           while ((p = pool->whatprovidesdata[d++]) != 0)
1683                             if (solv->decisionmap[p] >= 0)
1684                               queue_push(&dq, p);
1685                           policy_filter_unwanted(solv, &dq, POLICY_MODE_CHOOSE);
1686                           p = dq.elements[0];
1687                           if (p != i && solv->decisionmap[p] == 0)
1688                             {
1689                               rr = solv->rules + solv->featurerules + (i - solv->installed->start);
1690                               if (!rr->p)               /* update rule == feature rule? */
1691                                 rr = rr - solv->featurerules + solv->updaterules;
1692                               dq.count = 1;
1693                             }
1694                           else
1695                             dq.count = 0;
1696                         }
1697                       else
1698                         {
1699                           /* update to best package */
1700                           FOR_RULELITERALS(p, dp, rr)
1701                             {
1702                               if (solv->decisionmap[p] > 0)
1703                                 {
1704                                   dq.count = 0;         /* already fulfilled */
1705                                   break;
1706                                 }
1707                               if (!solv->decisionmap[p])
1708                                 queue_push(&dq, p);
1709                             }
1710                         }
1711                     }
1712                   /* install best version */
1713                   if (dq.count)
1714                     {
1715                       olevel = level;
1716                       level = selectandinstall(solv, level, &dq, disablerules, rr - solv->rules);
1717                       if (level == 0)
1718                         {
1719                           queue_free(&dq);
1720                           queue_free(&dqs);
1721                           return;
1722                         }
1723                       if (level <= olevel)
1724                         {
1725                           if (level == 1 || level < passlevel)
1726                             break;      /* trouble */
1727                           if (level < olevel)
1728                             n = installed->start;       /* redo all */
1729                           i--;
1730                           n--;
1731                           continue;
1732                         }
1733                     }
1734                   /* if still undecided keep package */
1735                   if (solv->decisionmap[i] == 0)
1736                     {
1737                       olevel = level;
1738                       if (solv->cleandepsmap.size && MAPTST(&solv->cleandepsmap, i - installed->start))
1739                         {
1740                           POOL_DEBUG(SOLV_DEBUG_POLICY, "cleandeps erasing %s\n", pool_solvid2str(pool, i));
1741                           level = setpropagatelearn(solv, level, -i, disablerules, 0);
1742                         }
1743                       else
1744                         {
1745                           POOL_DEBUG(SOLV_DEBUG_POLICY, "keeping %s\n", pool_solvid2str(pool, i));
1746                           level = setpropagatelearn(solv, level, i, disablerules, r - solv->rules);
1747                         }
1748                       if (level == 0)
1749                         break;
1750                       if (level <= olevel)
1751                         {
1752                           if (level == 1 || level < passlevel)
1753                             break;      /* trouble */
1754                           if (level < olevel)
1755                             n = installed->start;       /* redo all */
1756                           i--;
1757                           n--;
1758                           continue;     /* retry with learnt rule */
1759                         }
1760                     }
1761                 }
1762               if (n < installed->end)
1763                 {
1764                   installedpos = i;     /* retry problem solvable next time */
1765                   break;                /* ran into trouble */
1766                 }
1767               installedpos = installed->start;  /* reset installedpos */
1768             }
1769           if (level == 0)
1770             break;              /* unsolvable */
1771           systemlevel = level + 1;
1772           if (pass < 2)
1773             continue;           /* had trouble, retry */
1774         }
1775
1776       if (level < systemlevel)
1777         systemlevel = level;
1778
1779       /*
1780        * decide
1781        */
1782       solv->decisioncnt_resolve = solv->decisionq.count;
1783       POOL_DEBUG(SOLV_DEBUG_POLICY, "deciding unresolved rules\n");
1784       for (i = 1, n = 1; n < solv->nrules; i++, n++)
1785         {
1786           if (i == solv->nrules)
1787             i = 1;
1788           r = solv->rules + i;
1789           if (r->d < 0)         /* ignore disabled rules */
1790             continue;
1791           queue_empty(&dq);
1792           if (r->d == 0)
1793             {
1794               /* binary or unary rule */
1795               /* need two positive undecided literals */
1796               if (r->p < 0 || r->w2 <= 0)
1797                 continue;
1798               if (solv->decisionmap[r->p] || solv->decisionmap[r->w2])
1799                 continue;
1800               queue_push(&dq, r->p);
1801               queue_push(&dq, r->w2);
1802             }
1803           else
1804             {
1805               /* make sure that
1806                * all negative literals are installed
1807                * no positive literal is installed
1808                * i.e. the rule is not fulfilled and we
1809                * just need to decide on the positive literals
1810                */
1811               if (r->p < 0)
1812                 {
1813                   if (solv->decisionmap[-r->p] <= 0)
1814                     continue;
1815                 }
1816               else
1817                 {
1818                   if (solv->decisionmap[r->p] > 0)
1819                     continue;
1820                   if (solv->decisionmap[r->p] == 0)
1821                     queue_push(&dq, r->p);
1822                 }
1823               dp = pool->whatprovidesdata + r->d;
1824               while ((p = *dp++) != 0)
1825                 {
1826                   if (p < 0)
1827                     {
1828                       if (solv->decisionmap[-p] <= 0)
1829                         break;
1830                     }
1831                   else
1832                     {
1833                       if (solv->decisionmap[p] > 0)
1834                         break;
1835                       if (solv->decisionmap[p] == 0)
1836                         queue_push(&dq, p);
1837                     }
1838                 }
1839               if (p)
1840                 continue;
1841             }
1842           IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
1843             {
1844               POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "unfulfilled ");
1845               solver_printruleclass(solv, SOLV_DEBUG_PROPAGATE, r);
1846             }
1847           /* dq.count < 2 cannot happen as this means that
1848            * the rule is unit */
1849           assert(dq.count > 1);
1850
1851           olevel = level;
1852           level = selectandinstall(solv, level, &dq, disablerules, r - solv->rules);
1853           if (level == 0)
1854             break;              /* unsolvable */
1855           if (level < systemlevel || level == 1)
1856             break;              /* trouble */
1857           /* something changed, so look at all rules again */
1858           n = 0;
1859         }
1860
1861       if (n != solv->nrules)    /* ran into trouble? */
1862         {
1863           if (level == 0)
1864             break;              /* unsolvable */
1865           continue;             /* start over */
1866         }
1867
1868       /* at this point we have a consistent system. now do the extras... */
1869
1870       solv->decisioncnt_weak = solv->decisionq.count;
1871       if (doweak)
1872         {
1873           int qcount;
1874
1875           POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended packages\n");
1876           queue_empty(&dq);     /* recommended packages */
1877           queue_empty(&dqs);    /* supplemented packages */
1878           for (i = 1; i < pool->nsolvables; i++)
1879             {
1880               if (solv->decisionmap[i] < 0)
1881                 continue;
1882               if (solv->decisionmap[i] > 0)
1883                 {
1884                   /* installed, check for recommends */
1885                   Id *recp, rec, pp, p;
1886                   s = pool->solvables + i;
1887                   if (solv->ignorealreadyrecommended && s->repo == solv->installed)
1888                     continue;
1889                   /* XXX need to special case AND ? */
1890                   if (s->recommends)
1891                     {
1892                       recp = s->repo->idarraydata + s->recommends;
1893                       while ((rec = *recp++) != 0)
1894                         {
1895                           qcount = dq.count;
1896                           FOR_PROVIDES(p, pp, rec)
1897                             {
1898                               if (solv->decisionmap[p] > 0)
1899                                 {
1900                                   dq.count = qcount;
1901                                   break;
1902                                 }
1903                               else if (solv->decisionmap[p] == 0)
1904                                 {
1905                                   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))))
1906                                     continue;
1907                                   queue_pushunique(&dq, p);
1908                                 }
1909                             }
1910                         }
1911                     }
1912                 }
1913               else
1914                 {
1915                   s = pool->solvables + i;
1916                   if (!s->supplements)
1917                     continue;
1918                   if (!pool_installable(pool, s))
1919                     continue;
1920                   if (!solver_is_supplementing(solv, s))
1921                     continue;
1922                   if (solv->dupmap_all && solv->installed && s->repo == solv->installed && (solv->droporphanedmap_all || (solv->droporphanedmap.size && MAPTST(&solv->droporphanedmap, i - solv->installed->start))))
1923                     continue;
1924                   queue_push(&dqs, i);
1925                 }
1926             }
1927
1928           /* filter out all packages obsoleted by installed packages */
1929           /* this is no longer needed if we have reverse obsoletes */
1930           if ((dqs.count || dq.count) && solv->installed)
1931             {
1932               Map obsmap;
1933               Id obs, *obsp, po, ppo;
1934
1935               map_init(&obsmap, pool->nsolvables);
1936               for (p = solv->installed->start; p < solv->installed->end; p++)
1937                 {
1938                   s = pool->solvables + p;
1939                   if (s->repo != solv->installed || !s->obsoletes)
1940                     continue;
1941                   if (solv->decisionmap[p] <= 0)
1942                     continue;
1943                   if (solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p))
1944                     continue;
1945                   obsp = s->repo->idarraydata + s->obsoletes;
1946                   /* foreach obsoletes */
1947                   while ((obs = *obsp++) != 0)
1948                     FOR_PROVIDES(po, ppo, obs)
1949                       MAPSET(&obsmap, po);
1950                 }
1951               for (i = j = 0; i < dqs.count; i++)
1952                 if (!MAPTST(&obsmap, dqs.elements[i]))
1953                   dqs.elements[j++] = dqs.elements[i];
1954               dqs.count = j;
1955               for (i = j = 0; i < dq.count; i++)
1956                 if (!MAPTST(&obsmap, dq.elements[i]))
1957                   dq.elements[j++] = dq.elements[i];
1958               dq.count = j;
1959               map_free(&obsmap);
1960             }
1961
1962           /* filter out all already supplemented packages if requested */
1963           if (solv->ignorealreadyrecommended && dqs.count)
1964             {
1965               /* turn off all new packages */
1966               for (i = 0; i < solv->decisionq.count; i++)
1967                 {
1968                   p = solv->decisionq.elements[i];
1969                   if (p < 0)
1970                     continue;
1971                   s = pool->solvables + p;
1972                   if (s->repo && s->repo != solv->installed)
1973                     solv->decisionmap[p] = -solv->decisionmap[p];
1974                 }
1975               /* filter out old supplements */
1976               for (i = j = 0; i < dqs.count; i++)
1977                 {
1978                   p = dqs.elements[i];
1979                   s = pool->solvables + p;
1980                   if (!s->supplements)
1981                     continue;
1982                   if (!solver_is_supplementing(solv, s))
1983                     dqs.elements[j++] = p;
1984                 }
1985               dqs.count = j;
1986               /* undo turning off */
1987               for (i = 0; i < solv->decisionq.count; i++)
1988                 {
1989                   p = solv->decisionq.elements[i];
1990                   if (p < 0)
1991                     continue;
1992                   s = pool->solvables + p;
1993                   if (s->repo && s->repo != solv->installed)
1994                     solv->decisionmap[p] = -solv->decisionmap[p];
1995                 }
1996             }
1997
1998           /* multiversion doesn't mix well with supplements.
1999            * filter supplemented packages where we already decided
2000            * to install a different version (see bnc#501088) */
2001           if (dqs.count && solv->noobsoletes.size)
2002             {
2003               for (i = j = 0; i < dqs.count; i++)
2004                 {
2005                   p = dqs.elements[i];
2006                   if (MAPTST(&solv->noobsoletes, p))
2007                     {
2008                       Id p2, pp2;
2009                       s = pool->solvables + p;
2010                       FOR_PROVIDES(p2, pp2, s->name)
2011                         if (solv->decisionmap[p2] > 0 && pool->solvables[p2].name == s->name)
2012                           break;
2013                       if (p2)
2014                         continue;       /* ignore this package */
2015                     }
2016                   dqs.elements[j++] = p;
2017                 }
2018               dqs.count = j;
2019             }
2020
2021           /* make dq contain both recommended and supplemented pkgs */
2022           if (dqs.count)
2023             {
2024               for (i = 0; i < dqs.count; i++)
2025                 queue_pushunique(&dq, dqs.elements[i]);
2026             }
2027
2028           if (dq.count)
2029             {
2030               Map dqmap;
2031               int decisioncount = solv->decisionq.count;
2032
2033               if (dq.count == 1)
2034                 {
2035                   /* simple case, just one package. no need to choose to best version */
2036                   p = dq.elements[0];
2037                   if (dqs.count)
2038                     POOL_DEBUG(SOLV_DEBUG_POLICY, "installing supplemented %s\n", pool_solvid2str(pool, p));
2039                   else
2040                     POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended %s\n", pool_solvid2str(pool, p));
2041                   level = setpropagatelearn(solv, level, p, 0, 0);
2042                   if (level == 0)
2043                     break;
2044                   continue;     /* back to main loop */
2045                 }
2046
2047               /* filter packages, this gives us the best versions */
2048               policy_filter_unwanted(solv, &dq, POLICY_MODE_RECOMMEND);
2049
2050               /* create map of result */
2051               map_init(&dqmap, pool->nsolvables);
2052               for (i = 0; i < dq.count; i++)
2053                 MAPSET(&dqmap, dq.elements[i]);
2054
2055               /* install all supplemented packages */
2056               for (i = 0; i < dqs.count; i++)
2057                 {
2058                   p = dqs.elements[i];
2059                   if (solv->decisionmap[p] || !MAPTST(&dqmap, p))
2060                     continue;
2061                   POOL_DEBUG(SOLV_DEBUG_POLICY, "installing supplemented %s\n", pool_solvid2str(pool, p));
2062                   olevel = level;
2063                   level = setpropagatelearn(solv, level, p, 0, 0);
2064                   if (level <= olevel)
2065                     break;
2066                 }
2067               if (i < dqs.count || solv->decisionq.count < decisioncount)
2068                 {
2069                   map_free(&dqmap);
2070                   if (level == 0)
2071                     break;
2072                   continue;
2073                 }
2074
2075               /* install all recommended packages */
2076               /* more work as we want to created branches if multiple
2077                * choices are valid */
2078               for (i = 0; i < decisioncount; i++)
2079                 {
2080                   Id rec, *recp, pp;
2081                   p = solv->decisionq.elements[i];
2082                   if (p < 0)
2083                     continue;
2084                   s = pool->solvables + p;
2085                   if (!s->repo || (solv->ignorealreadyrecommended && s->repo == solv->installed))
2086                     continue;
2087                   if (!s->recommends)
2088                     continue;
2089                   recp = s->repo->idarraydata + s->recommends;
2090                   while ((rec = *recp++) != 0)
2091                     {
2092                       queue_empty(&dq);
2093                       FOR_PROVIDES(p, pp, rec)
2094                         {
2095                           if (solv->decisionmap[p] > 0)
2096                             {
2097                               dq.count = 0;
2098                               break;
2099                             }
2100                           else if (solv->decisionmap[p] == 0 && MAPTST(&dqmap, p))
2101                             queue_pushunique(&dq, p);
2102                         }
2103                       if (!dq.count)
2104                         continue;
2105                       if (dq.count > 1)
2106                         {
2107                           /* multiple candidates, open a branch */
2108                           for (i = 1; i < dq.count; i++)
2109                             queue_push(&solv->branches, dq.elements[i]);
2110                           queue_push(&solv->branches, -level);
2111                         }
2112                       p = dq.elements[0];
2113                       POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended %s\n", pool_solvid2str(pool, p));
2114                       olevel = level;
2115                       level = setpropagatelearn(solv, level, p, 0, 0);
2116                       if (level <= olevel || solv->decisionq.count < decisioncount)
2117                         break;  /* we had to revert some decisions */
2118                     }
2119                   if (rec)
2120                     break;      /* had a problem above, quit loop */
2121                 }
2122               map_free(&dqmap);
2123               if (level == 0)
2124                 break;
2125               continue;         /* back to main loop so that all deps are checked */
2126             }
2127         }
2128
2129       solv->decisioncnt_orphan = solv->decisionq.count;
2130       if (solv->dupmap_all && solv->installed)
2131         {
2132           int installedone = 0;
2133
2134           /* let's see if we can install some unsupported package */
2135           POOL_DEBUG(SOLV_DEBUG_SOLVER, "deciding orphaned packages\n");
2136           for (i = 0; i < solv->orphaned.count; i++)
2137             {
2138               p = solv->orphaned.elements[i];
2139               if (solv->decisionmap[p])
2140                 continue;       /* already decided */
2141               if (solv->droporphanedmap_all)
2142                 continue;
2143               if (solv->droporphanedmap.size && MAPTST(&solv->droporphanedmap, p - solv->installed->start))
2144                 continue;
2145               POOL_DEBUG(SOLV_DEBUG_SOLVER, "keeping orphaned %s\n", pool_solvid2str(pool, p));
2146               olevel = level;
2147               level = setpropagatelearn(solv, level, p, 0, 0);
2148               installedone = 1;
2149               if (level < olevel)
2150                 break;
2151             }
2152           if (installedone || i < solv->orphaned.count)
2153             {
2154               if (level == 0)
2155                 break;
2156               continue;         /* back to main loop */
2157             }
2158           for (i = 0; i < solv->orphaned.count; i++)
2159             {
2160               p = solv->orphaned.elements[i];
2161               if (solv->decisionmap[p])
2162                 continue;       /* already decided */
2163               POOL_DEBUG(SOLV_DEBUG_SOLVER, "removing orphaned %s\n", pool_solvid2str(pool, p));
2164               olevel = level;
2165               level = setpropagatelearn(solv, level, -p, 0, 0);
2166               if (level < olevel)
2167                 break;
2168             }
2169           if (i < solv->orphaned.count)
2170             {
2171               if (level == 0)
2172                 break;
2173               continue;         /* back to main loop */
2174             }
2175         }
2176
2177      if (solv->installed && solv->cleandepsmap.size)
2178         {
2179           olevel = level;
2180           level = cleandeps_check_mistakes(solv, level);
2181           if (level < olevel)
2182             continue;
2183         }
2184
2185      if (solv->solution_callback)
2186         {
2187           solv->solution_callback(solv, solv->solution_callback_data);
2188           if (solv->branches.count)
2189             {
2190               int i = solv->branches.count - 1;
2191               int l = -solv->branches.elements[i];
2192               Id why;
2193
2194               for (; i > 0; i--)
2195                 if (solv->branches.elements[i - 1] < 0)
2196                   break;
2197               p = solv->branches.elements[i];
2198               POOL_DEBUG(SOLV_DEBUG_SOLVER, "branching with %s\n", pool_solvid2str(pool, p));
2199               queue_empty(&dq);
2200               for (j = i + 1; j < solv->branches.count; j++)
2201                 queue_push(&dq, solv->branches.elements[j]);
2202               solv->branches.count = i;
2203               level = l;
2204               revert(solv, level);
2205               if (dq.count > 1)
2206                 for (j = 0; j < dq.count; j++)
2207                   queue_push(&solv->branches, dq.elements[j]);
2208               olevel = level;
2209               why = -solv->decisionq_why.elements[solv->decisionq_why.count];
2210               assert(why >= 0);
2211               level = setpropagatelearn(solv, level, p, disablerules, why);
2212               if (level == 0)
2213                 break;
2214               continue;
2215             }
2216           /* all branches done, we're finally finished */
2217           break;
2218         }
2219
2220       /* auto-minimization step */
2221      if (solv->branches.count)
2222         {
2223           int l = 0, lasti = -1, lastl = -1;
2224           Id why;
2225
2226           p = 0;
2227           for (i = solv->branches.count - 1; i >= 0; i--)
2228             {
2229               p = solv->branches.elements[i];
2230               if (p < 0)
2231                 l = -p;
2232               else if (p > 0 && solv->decisionmap[p] > l + 1)
2233                 {
2234                   lasti = i;
2235                   lastl = l;
2236                 }
2237             }
2238           if (lasti >= 0)
2239             {
2240               /* kill old solvable so that we do not loop */
2241               p = solv->branches.elements[lasti];
2242               solv->branches.elements[lasti] = 0;
2243               POOL_DEBUG(SOLV_DEBUG_SOLVER, "minimizing %d -> %d with %s\n", solv->decisionmap[p], lastl, pool_solvid2str(pool, p));
2244               minimizationsteps++;
2245
2246               level = lastl;
2247               revert(solv, level);
2248               why = -solv->decisionq_why.elements[solv->decisionq_why.count];
2249               assert(why >= 0);
2250               olevel = level;
2251               level = setpropagatelearn(solv, level, p, disablerules, why);
2252               if (level == 0)
2253                 break;
2254               continue;         /* back to main loop */
2255             }
2256         }
2257       /* no minimization found, we're finally finished! */
2258       break;
2259     }
2260
2261   POOL_DEBUG(SOLV_DEBUG_STATS, "solver statistics: %d learned rules, %d unsolvable, %d minimization steps\n", solv->stats_learned, solv->stats_unsolvable, minimizationsteps);
2262
2263   POOL_DEBUG(SOLV_DEBUG_STATS, "done solving.\n\n");
2264   queue_free(&dq);
2265   queue_free(&dqs);
2266   if (level == 0)
2267     {
2268       /* unsolvable */
2269       solv->decisioncnt_update = solv->decisionq.count;
2270       solv->decisioncnt_keep = solv->decisionq.count;
2271       solv->decisioncnt_resolve = solv->decisionq.count;
2272       solv->decisioncnt_weak = solv->decisionq.count;
2273       solv->decisioncnt_orphan = solv->decisionq.count;
2274     }
2275 #if 0
2276   solver_printdecisionq(solv, SOLV_DEBUG_RESULT);
2277 #endif
2278 }
2279
2280
2281 /*-------------------------------------------------------------------
2282  *
2283  * remove disabled conflicts
2284  *
2285  * purpose: update the decisionmap after some rules were disabled.
2286  * this is used to calculate the suggested/recommended package list.
2287  * Also returns a "removed" list to undo the discisionmap changes.
2288  */
2289
2290 static void
2291 removedisabledconflicts(Solver *solv, Queue *removed)
2292 {
2293   Pool *pool = solv->pool;
2294   int i, n;
2295   Id p, why, *dp;
2296   Id new;
2297   Rule *r;
2298   Id *decisionmap = solv->decisionmap;
2299
2300   queue_empty(removed);
2301   for (i = 0; i < solv->decisionq.count; i++)
2302     {
2303       p = solv->decisionq.elements[i];
2304       if (p > 0)
2305         continue;       /* conflicts only, please */
2306       why = solv->decisionq_why.elements[i];
2307       if (why == 0)
2308         {
2309           /* no rule involved, must be a orphan package drop */
2310           continue;
2311         }
2312       /* we never do conflicts on free decisions, so there
2313        * must have been an unit rule */
2314       assert(why > 0);
2315       r = solv->rules + why;
2316       if (r->d < 0 && decisionmap[-p])
2317         {
2318           /* rule is now disabled, remove from decisionmap */
2319           POOL_DEBUG(SOLV_DEBUG_SOLVER, "removing conflict for package %s[%d]\n", pool_solvid2str(pool, -p), -p);
2320           queue_push(removed, -p);
2321           queue_push(removed, decisionmap[-p]);
2322           decisionmap[-p] = 0;
2323         }
2324     }
2325   if (!removed->count)
2326     return;
2327   /* we removed some confliced packages. some of them might still
2328    * be in conflict, so search for unit rules and re-conflict */
2329   new = 0;
2330   for (i = n = 1, r = solv->rules + i; n < solv->nrules; i++, r++, n++)
2331     {
2332       if (i == solv->nrules)
2333         {
2334           i = 1;
2335           r = solv->rules + i;
2336         }
2337       if (r->d < 0)
2338         continue;
2339       if (!r->w2)
2340         {
2341           if (r->p < 0 && !decisionmap[-r->p])
2342             new = r->p;
2343         }
2344       else if (!r->d)
2345         {
2346           /* binary rule */
2347           if (r->p < 0 && decisionmap[-r->p] == 0 && DECISIONMAP_FALSE(r->w2))
2348             new = r->p;
2349           else if (r->w2 < 0 && decisionmap[-r->w2] == 0 && DECISIONMAP_FALSE(r->p))
2350             new = r->w2;
2351         }
2352       else
2353         {
2354           if (r->p < 0 && decisionmap[-r->p] == 0)
2355             new = r->p;
2356           if (new || DECISIONMAP_FALSE(r->p))
2357             {
2358               dp = pool->whatprovidesdata + r->d;
2359               while ((p = *dp++) != 0)
2360                 {
2361                   if (new && p == new)
2362                     continue;
2363                   if (p < 0 && decisionmap[-p] == 0)
2364                     {
2365                       if (new)
2366                         {
2367                           new = 0;
2368                           break;
2369                         }
2370                       new = p;
2371                     }
2372                   else if (!DECISIONMAP_FALSE(p))
2373                     {
2374                       new = 0;
2375                       break;
2376                     }
2377                 }
2378             }
2379         }
2380       if (new)
2381         {
2382           POOL_DEBUG(SOLV_DEBUG_SOLVER, "re-conflicting package %s[%d]\n", pool_solvid2str(pool, -new), -new);
2383           decisionmap[-new] = -1;
2384           new = 0;
2385           n = 0;        /* redo all rules */
2386         }
2387     }
2388 }
2389
2390 static inline void
2391 undo_removedisabledconflicts(Solver *solv, Queue *removed)
2392 {
2393   int i;
2394   for (i = 0; i < removed->count; i += 2)
2395     solv->decisionmap[removed->elements[i]] = removed->elements[i + 1];
2396 }
2397
2398
2399 /*-------------------------------------------------------------------
2400  *
2401  * weaken solvable dependencies
2402  */
2403
2404 static void
2405 weaken_solvable_deps(Solver *solv, Id p)
2406 {
2407   int i;
2408   Rule *r;
2409
2410   for (i = 1, r = solv->rules + i; i < solv->rpmrules_end; i++, r++)
2411     {
2412       if (r->p != -p)
2413         continue;
2414       if ((r->d == 0 || r->d == -1) && r->w2 < 0)
2415         continue;       /* conflict */
2416       queue_push(&solv->weakruleq, i);
2417     }
2418 }
2419
2420
2421 /********************************************************************/
2422 /* main() */
2423
2424
2425 void
2426 solver_calculate_noobsmap(Pool *pool, Queue *job, Map *noobsmap)
2427 {
2428   int i;
2429   Id how, what, select;
2430   Id p, pp;
2431   for (i = 0; i < job->count; i += 2)
2432     {
2433       how = job->elements[i];
2434       if ((how & SOLVER_JOBMASK) != SOLVER_NOOBSOLETES)
2435         continue;
2436       what = job->elements[i + 1];
2437       select = how & SOLVER_SELECTMASK;
2438       if (!noobsmap->size)
2439         map_grow(noobsmap, pool->nsolvables);
2440       FOR_JOB_SELECT(p, pp, select, what)
2441         MAPSET(noobsmap, p);
2442     }
2443 }
2444
2445 /*
2446  * add a rule created by a job, record job number and weak flag
2447  */
2448 static inline void
2449 solver_addjobrule(Solver *solv, Id p, Id d, Id job, int weak)
2450 {
2451   solver_addrule(solv, p, d);
2452   queue_push(&solv->ruletojob, job);
2453   if (weak)
2454     queue_push(&solv->weakruleq, solv->nrules - 1);
2455 }
2456
2457 /*
2458  *
2459  * solve job queue
2460  *
2461  */
2462
2463 int
2464 solver_solve(Solver *solv, Queue *job)
2465 {
2466   Pool *pool = solv->pool;
2467   Repo *installed = solv->installed;
2468   int i;
2469   int oldnrules;
2470   Map addedmap;                /* '1' == have rpm-rules for solvable */
2471   Map installcandidatemap;
2472   Id how, what, select, name, weak, p, pp, d;
2473   Queue q;
2474   Solvable *s;
2475   Rule *r;
2476   int now, solve_start;
2477   int hasdupjob = 0;
2478
2479   solve_start = solv_timems(0);
2480
2481   /* log solver options */
2482   POOL_DEBUG(SOLV_DEBUG_STATS, "solver started\n");
2483   POOL_DEBUG(SOLV_DEBUG_STATS, "dosplitprovides=%d, noupdateprovide=%d noinfarchcheck=%d\n", solv->dosplitprovides, solv->noupdateprovide, solv->noinfarchcheck);
2484   POOL_DEBUG(SOLV_DEBUG_STATS, "allowuninstall=%d, allowdowngrade=%d, allowarchchange=%d, allowvendorchange=%d\n", solv->allowuninstall, solv->allowdowngrade, solv->allowarchchange, solv->allowvendorchange);
2485   POOL_DEBUG(SOLV_DEBUG_STATS, "promoteepoch=%d, forbidselfconflicts=%d\n", pool->promoteepoch, pool->forbidselfconflicts);
2486   POOL_DEBUG(SOLV_DEBUG_STATS, "obsoleteusesprovides=%d, implicitobsoleteusesprovides=%d, obsoleteusescolors=%d\n", pool->obsoleteusesprovides, pool->implicitobsoleteusesprovides, pool->obsoleteusescolors);
2487   POOL_DEBUG(SOLV_DEBUG_STATS, "dontinstallrecommended=%d, ignorealreadyrecommended=%d\n", solv->dontinstallrecommended, solv->ignorealreadyrecommended);
2488
2489   /* create whatprovides if not already there */
2490   if (!pool->whatprovides)
2491     pool_createwhatprovides(pool);
2492
2493   /* create obsolete index */
2494   policy_create_obsolete_index(solv);
2495
2496   /* remember job */
2497   queue_free(&solv->job);
2498   queue_init_clone(&solv->job, job);
2499
2500   /*
2501    * create basic rule set of all involved packages
2502    * use addedmap bitmap to make sure we don't create rules twice
2503    */
2504
2505   /* create noobsolete map if needed */
2506   solver_calculate_noobsmap(pool, job, &solv->noobsoletes);
2507
2508   map_init(&addedmap, pool->nsolvables);
2509   MAPSET(&addedmap, SYSTEMSOLVABLE);
2510
2511   map_init(&installcandidatemap, pool->nsolvables);
2512   queue_init(&q);
2513
2514   now = solv_timems(0);
2515   /*
2516    * create rules for all package that could be involved with the solving
2517    * so called: rpm rules
2518    *
2519    */
2520   if (installed)
2521     {
2522       /* check for update/verify jobs as they need to be known early */
2523       for (i = 0; i < job->count; i += 2)
2524         {
2525           how = job->elements[i];
2526           what = job->elements[i + 1];
2527           select = how & SOLVER_SELECTMASK;
2528           switch (how & SOLVER_JOBMASK)
2529             {
2530             case SOLVER_VERIFY:
2531               if (select == SOLVER_SOLVABLE_ALL)
2532                 solv->fixmap_all = 1;
2533               FOR_JOB_SELECT(p, pp, select, what)
2534                 {
2535                   s = pool->solvables + p;
2536                   if (!solv->installed || s->repo != solv->installed)
2537                     continue;
2538                   if (!solv->fixmap.size)
2539                     map_grow(&solv->fixmap, solv->installed->end - solv->installed->start);
2540                   MAPSET(&solv->fixmap, p - solv->installed->start);
2541                 }
2542               break;
2543             case SOLVER_UPDATE:
2544               if (select == SOLVER_SOLVABLE_ALL)
2545                 solv->updatemap_all = 1;
2546               FOR_JOB_SELECT(p, pp, select, what)
2547                 {
2548                   s = pool->solvables + p;
2549                   if (!solv->installed || s->repo != solv->installed)
2550                     continue;
2551                   if (!solv->updatemap.size)
2552                     map_grow(&solv->updatemap, solv->installed->end - solv->installed->start);
2553                   MAPSET(&solv->updatemap, p - solv->installed->start);
2554                 }
2555               break;
2556             default:
2557               break;
2558             }
2559         }
2560
2561       oldnrules = solv->nrules;
2562       FOR_REPO_SOLVABLES(installed, p, s)
2563         solver_addrpmrulesforsolvable(solv, s, &addedmap);
2564       POOL_DEBUG(SOLV_DEBUG_STATS, "added %d rpm rules for installed solvables\n", solv->nrules - oldnrules);
2565       oldnrules = solv->nrules;
2566       FOR_REPO_SOLVABLES(installed, p, s)
2567         solver_addrpmrulesforupdaters(solv, s, &addedmap, 1);
2568       POOL_DEBUG(SOLV_DEBUG_STATS, "added %d rpm rules for updaters of installed solvables\n", solv->nrules - oldnrules);
2569     }
2570
2571   /*
2572    * create rules for all packages involved in the job
2573    * (to be installed or removed)
2574    */
2575
2576   oldnrules = solv->nrules;
2577   for (i = 0; i < job->count; i += 2)
2578     {
2579       how = job->elements[i];
2580       what = job->elements[i + 1];
2581       select = how & SOLVER_SELECTMASK;
2582
2583       switch (how & SOLVER_JOBMASK)
2584         {
2585         case SOLVER_INSTALL:
2586           FOR_JOB_SELECT(p, pp, select, what)
2587             {
2588               MAPSET(&installcandidatemap, p);
2589               solver_addrpmrulesforsolvable(solv, pool->solvables + p, &addedmap);
2590             }
2591           break;
2592         case SOLVER_DISTUPGRADE:
2593           if (select == SOLVER_SOLVABLE_ALL)
2594             {
2595               solv->dupmap_all = 1;
2596               solv->updatemap_all = 1;
2597             }
2598           if (!solv->dupmap_all)
2599             hasdupjob = 1;
2600           break;
2601         default:
2602           break;
2603         }
2604     }
2605   POOL_DEBUG(SOLV_DEBUG_STATS, "added %d rpm rules for packages involved in a job\n", solv->nrules - oldnrules);
2606
2607
2608   /*
2609    * add rules for suggests, enhances
2610    */
2611   oldnrules = solv->nrules;
2612   solver_addrpmrulesforweak(solv, &addedmap);
2613   POOL_DEBUG(SOLV_DEBUG_STATS, "added %d rpm rules because of weak dependencies\n", solv->nrules - oldnrules);
2614
2615   /*
2616    * first pass done, we now have all the rpm rules we need.
2617    * unify existing rules before going over all job rules and
2618    * policy rules.
2619    * at this point the system is always solvable,
2620    * as an empty system (remove all packages) is a valid solution
2621    */
2622
2623   IF_POOLDEBUG (SOLV_DEBUG_STATS)
2624     {
2625       int possible = 0, installable = 0;
2626       for (i = 1; i < pool->nsolvables; i++)
2627         {
2628           if (pool_installable(pool, pool->solvables + i))
2629             installable++;
2630           if (MAPTST(&addedmap, i))
2631             possible++;
2632         }
2633       POOL_DEBUG(SOLV_DEBUG_STATS, "%d of %d installable solvables considered for solving\n", possible, installable);
2634     }
2635
2636   solver_unifyrules(solv);                          /* remove duplicate rpm rules */
2637   solv->rpmrules_end = solv->nrules;              /* mark end of rpm rules */
2638
2639   POOL_DEBUG(SOLV_DEBUG_STATS, "rpm rule memory usage: %d K\n", solv->nrules * (int)sizeof(Rule) / 1024);
2640   POOL_DEBUG(SOLV_DEBUG_STATS, "rpm rule creation took %d ms\n", solv_timems(now));
2641
2642   /* create dup maps if needed. We need the maps early to create our
2643    * update rules */
2644   if (hasdupjob)
2645     solver_createdupmaps(solv);
2646
2647   /*
2648    * create feature rules
2649    *
2650    * foreach installed:
2651    *   create assertion (keep installed, if no update available)
2652    *   or
2653    *   create update rule (A|update1(A)|update2(A)|...)
2654    *
2655    * those are used later on to keep a version of the installed packages in
2656    * best effort mode
2657    */
2658
2659   solv->featurerules = solv->nrules;              /* mark start of feature rules */
2660   if (installed)
2661     {
2662       /* foreach possibly installed solvable */
2663       for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
2664         {
2665           if (s->repo != installed)
2666             {
2667               solver_addrule(solv, 0, 0);       /* create dummy rule */
2668               continue;
2669             }
2670           solver_addupdaterule(solv, s, 1);    /* allow s to be updated */
2671         }
2672       /* make sure we accounted for all rules */
2673       assert(solv->nrules - solv->featurerules == installed->end - installed->start);
2674     }
2675   solv->featurerules_end = solv->nrules;
2676
2677     /*
2678      * Add update rules for installed solvables
2679      *
2680      * almost identical to feature rules
2681      * except that downgrades/archchanges/vendorchanges are not allowed
2682      */
2683
2684   solv->updaterules = solv->nrules;
2685
2686   if (installed)
2687     { /* foreach installed solvables */
2688       /* we create all update rules, but disable some later on depending on the job */
2689       for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
2690         {
2691           Rule *sr;
2692
2693           if (s->repo != installed)
2694             {
2695               solver_addrule(solv, 0, 0);       /* create dummy rule */
2696               continue;
2697             }
2698           solver_addupdaterule(solv, s, 0);     /* allowall = 0: downgrades not allowed */
2699           /*
2700            * check for and remove duplicate
2701            */
2702           r = solv->rules + solv->nrules - 1;           /* r: update rule */
2703           sr = r - (installed->end - installed->start); /* sr: feature rule */
2704           /* it's orphaned if there is no feature rule or the feature rule
2705            * consists just of the installed package */
2706           if (!sr->p || (sr->p == i && !sr->d && !sr->w2))
2707             queue_push(&solv->orphaned, i);
2708           if (!r->p)
2709             {
2710               assert(solv->dupmap_all && !sr->p);
2711               continue;
2712             }
2713           if (!solver_samerule(solv, r, sr))
2714             {
2715               /* identical rule, kill unneeded one */
2716               if (solv->allowuninstall)
2717                 {
2718                   /* keep feature rule, make it weak */
2719                   memset(r, 0, sizeof(*r));
2720                   queue_push(&solv->weakruleq, sr - solv->rules);
2721                 }
2722               else
2723                 {
2724                   /* keep update rule */
2725                   memset(sr, 0, sizeof(*sr));
2726                 }
2727             }
2728           else if (solv->allowuninstall)
2729             {
2730               /* make both feature and update rule weak */
2731               queue_push(&solv->weakruleq, r - solv->rules);
2732               queue_push(&solv->weakruleq, sr - solv->rules);
2733             }
2734           else
2735             solver_disablerule(solv, sr);
2736         }
2737       /* consistency check: we added a rule for _every_ installed solvable */
2738       assert(solv->nrules - solv->updaterules == installed->end - installed->start);
2739     }
2740   solv->updaterules_end = solv->nrules;
2741
2742
2743   /*
2744    * now add all job rules
2745    */
2746
2747   solv->jobrules = solv->nrules;
2748   if (solv->cleandeps_updatepkgs)
2749     {
2750       queue_free(solv->cleandeps_updatepkgs);
2751       solv->cleandeps_updatepkgs = solv_free(solv->cleandeps_updatepkgs);
2752     }
2753   for (i = 0; i < job->count; i += 2)
2754     {
2755       oldnrules = solv->nrules;
2756
2757       how = job->elements[i];
2758       what = job->elements[i + 1];
2759       weak = how & SOLVER_WEAK;
2760       select = how & SOLVER_SELECTMASK;
2761       switch (how & SOLVER_JOBMASK)
2762         {
2763         case SOLVER_INSTALL:
2764           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sinstall %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
2765           if ((how & SOLVER_CLEANDEPS) != 0 && !solv->cleandepsmap.size && installed)
2766             map_grow(&solv->cleandepsmap, installed->end - installed->start);
2767           if (select == SOLVER_SOLVABLE)
2768             {
2769               p = what;
2770               d = 0;
2771             }
2772           else
2773             {
2774               queue_empty(&q);
2775               FOR_JOB_SELECT(p, pp, select, what)
2776                 queue_push(&q, p);
2777               if (!q.count)
2778                 {
2779                   /* no candidate found, make this an impossible rule */
2780                   queue_push(&q, -SYSTEMSOLVABLE);
2781                 }
2782               p = queue_shift(&q);      /* get first candidate */
2783               d = !q.count ? 0 : pool_queuetowhatprovides(pool, &q);    /* internalize */
2784             }
2785           solver_addjobrule(solv, p, d, i, weak);
2786           break;
2787         case SOLVER_ERASE:
2788           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %s%serase %s\n", weak ? "weak " : "", how & SOLVER_CLEANDEPS ? "clean deps " : "", solver_select2str(pool, select, what));
2789           if ((how & SOLVER_CLEANDEPS) != 0 && !solv->cleandepsmap.size && installed)
2790             map_grow(&solv->cleandepsmap, installed->end - installed->start);
2791           name = (select == SOLVER_SOLVABLE || (select == SOLVER_SOLVABLE_NAME && ISRELDEP(what))) ? 0 : -1;
2792           FOR_JOB_SELECT(p, pp, select, what)
2793             {
2794               s = pool->solvables + p;
2795               if (installed && s->repo == installed)
2796                 name = !name ? s->name : -1;
2797               solver_addjobrule(solv, -p, 0, i, weak);
2798             }
2799           /* special case for "erase a specific solvable": we also
2800            * erase all other solvables with that name, so that they
2801            * don't get picked up as replacement.
2802            * name is > 0 if exactly one installed solvable matched.
2803            */
2804           /* XXX: look also at packages that obsolete this package? */
2805           if (name > 0)
2806             {
2807               int j, k;
2808               k = solv->nrules;
2809               FOR_PROVIDES(p, pp, name)
2810                 {
2811                   s = pool->solvables + p;
2812                   if (s->name != name)
2813                     continue;
2814                   /* keep other versions installed */
2815                   if (s->repo == installed)
2816                     continue;
2817                   /* keep installcandidates of other jobs */
2818                   if (MAPTST(&installcandidatemap, p))
2819                     continue;
2820                   /* don't add the same rule twice */
2821                   for (j = oldnrules; j < k; j++)
2822                     if (solv->rules[j].p == -p)
2823                       break;
2824                   if (j == k)
2825                     solver_addjobrule(solv, -p, 0, i, weak);    /* remove by id */
2826                 }
2827             }
2828           break;
2829
2830         case SOLVER_UPDATE:
2831           if ((how & SOLVER_CLEANDEPS) != 0 && installed)
2832             {
2833               FOR_JOB_SELECT(p, pp, select, what)
2834                 {
2835                   s = pool->solvables + p;
2836                   if (s->repo != installed)
2837                     continue;
2838                   if (!solv->cleandeps_updatepkgs)
2839                     {
2840                       solv->cleandeps_updatepkgs = solv_calloc(1, sizeof(Queue));
2841                       queue_init(solv->cleandeps_updatepkgs);
2842                     }
2843                   queue_pushunique(solv->cleandeps_updatepkgs, p);
2844                   if (!solv->cleandepsmap.size)
2845                     map_grow(&solv->cleandepsmap, installed->end - installed->start);
2846                 }
2847             }
2848           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %supdate %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
2849           break;
2850         case SOLVER_VERIFY:
2851           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sverify %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
2852           break;
2853         case SOLVER_WEAKENDEPS:
2854           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sweaken deps %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
2855           if (select != SOLVER_SOLVABLE)
2856             break;
2857           s = pool->solvables + what;
2858           weaken_solvable_deps(solv, what);
2859           break;
2860         case SOLVER_NOOBSOLETES:
2861           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sno obsolete %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
2862           break;
2863         case SOLVER_LOCK:
2864           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %slock %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
2865           FOR_JOB_SELECT(p, pp, select, what)
2866             {
2867               s = pool->solvables + p;
2868               solver_addjobrule(solv, installed && s->repo == installed ? p : -p, 0, i, weak);
2869             }
2870           break;
2871         case SOLVER_DISTUPGRADE:
2872           POOL_DEBUG(SOLV_DEBUG_JOB, "job: distupgrade %s\n", solver_select2str(pool, select, what));
2873           break;
2874         case SOLVER_DROP_ORPHANED:
2875           POOL_DEBUG(SOLV_DEBUG_JOB, "job: drop orphaned %s\n", solver_select2str(pool, select, what));
2876           if (select == SOLVER_SOLVABLE_ALL)
2877             solv->droporphanedmap_all = 1;
2878           FOR_JOB_SELECT(p, pp, select, what)
2879             {
2880               s = pool->solvables + p;
2881               if (!installed || s->repo != installed)
2882                 continue;
2883               if (!solv->droporphanedmap.size)
2884                 map_grow(&solv->droporphanedmap, installed->end - installed->start);
2885               MAPSET(&solv->droporphanedmap, p - installed->start);
2886             }
2887           break;
2888         case SOLVER_USERINSTALLED:
2889           POOL_DEBUG(SOLV_DEBUG_JOB, "job: user installed %s\n", solver_select2str(pool, select, what));
2890           break;
2891         default:
2892           POOL_DEBUG(SOLV_DEBUG_JOB, "job: unknown job\n");
2893           break;
2894         }
2895
2896         /*
2897          * debug
2898          */
2899
2900       IF_POOLDEBUG (SOLV_DEBUG_JOB)
2901         {
2902           int j;
2903           if (solv->nrules == oldnrules)
2904             POOL_DEBUG(SOLV_DEBUG_JOB, " - no rule created\n");
2905           for (j = oldnrules; j < solv->nrules; j++)
2906             {
2907               POOL_DEBUG(SOLV_DEBUG_JOB, " - job ");
2908               solver_printrule(solv, SOLV_DEBUG_JOB, solv->rules + j);
2909             }
2910         }
2911     }
2912   assert(solv->ruletojob.count == solv->nrules - solv->jobrules);
2913   solv->jobrules_end = solv->nrules;
2914
2915   /* now create infarch and dup rules */
2916   if (!solv->noinfarchcheck)
2917     {
2918       solver_addinfarchrules(solv, &addedmap);
2919       if (pool->obsoleteusescolors)
2920         {
2921           /* currently doesn't work well with infarch rules, so make
2922            * them weak */
2923           for (i = solv->infarchrules; i < solv->infarchrules_end; i++)
2924             queue_push(&solv->weakruleq, i);
2925         }
2926     }
2927   else
2928     solv->infarchrules = solv->infarchrules_end = solv->nrules;
2929
2930   if (hasdupjob)
2931     {
2932       solver_addduprules(solv, &addedmap);
2933       solver_freedupmaps(solv); /* no longer needed */
2934     }
2935   else
2936     solv->duprules = solv->duprules_end = solv->nrules;
2937
2938   if (1)
2939     solver_addchoicerules(solv);
2940   else
2941     solv->choicerules = solv->choicerules_end = solv->nrules;
2942
2943   /* all rules created
2944    * --------------------------------------------------------------
2945    * prepare for solving
2946    */
2947
2948   /* free unneeded memory */
2949   map_free(&addedmap);
2950   map_free(&installcandidatemap);
2951   queue_free(&q);
2952
2953   POOL_DEBUG(SOLV_DEBUG_STATS, "%d rpm rules, %d job rules, %d infarch rules, %d dup rules, %d choice rules\n", solv->rpmrules_end - 1, solv->jobrules_end - solv->jobrules, solv->infarchrules_end - solv->infarchrules, solv->duprules_end - solv->duprules, solv->choicerules_end - solv->choicerules);
2954
2955   /* create weak map */
2956   map_init(&solv->weakrulemap, solv->nrules);
2957   for (i = 0; i < solv->weakruleq.count; i++)
2958     {
2959       p = solv->weakruleq.elements[i];
2960       MAPSET(&solv->weakrulemap, p);
2961     }
2962
2963   /* all new rules are learnt after this point */
2964   solv->learntrules = solv->nrules;
2965
2966   /* create watches chains */
2967   makewatches(solv);
2968
2969   /* create assertion index. it is only used to speed up
2970    * makeruledecsions() a bit */
2971   for (i = 1, r = solv->rules + i; i < solv->nrules; i++, r++)
2972     if (r->p && !r->w2 && (r->d == 0 || r->d == -1))
2973       queue_push(&solv->ruleassertions, i);
2974
2975   /* disable update rules that conflict with our job */
2976   solver_disablepolicyrules(solv);
2977
2978   /* make initial decisions based on assertion rules */
2979   makeruledecisions(solv);
2980   POOL_DEBUG(SOLV_DEBUG_SOLVER, "problems so far: %d\n", solv->problems.count);
2981
2982   /* no mistakes */
2983   if (solv->cleandeps_mistakes)
2984     {
2985       queue_free(solv->cleandeps_mistakes);
2986       solv->cleandeps_mistakes = solv_free(solv->cleandeps_mistakes);
2987     }
2988
2989   /*
2990    * ********************************************
2991    * solve!
2992    * ********************************************
2993    */
2994
2995   now = solv_timems(0);
2996   solver_run_sat(solv, 1, solv->dontinstallrecommended ? 0 : 1);
2997   POOL_DEBUG(SOLV_DEBUG_STATS, "solver took %d ms\n", solv_timems(now));
2998
2999   /*
3000    * prepare solution queue if there were problems
3001    */
3002   solver_prepare_solutions(solv);
3003
3004   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);
3005   POOL_DEBUG(SOLV_DEBUG_STATS, "solver_solve took %d ms\n", solv_timems(solve_start));
3006
3007   /* return number of problems */
3008   return solv->problems.count ? solv->problems.count / 2 : 0;
3009 }
3010
3011 Transaction *
3012 solver_create_transaction(Solver *solv)
3013 {
3014   return transaction_create_decisionq(solv->pool, &solv->decisionq, &solv->noobsoletes);
3015 }
3016
3017 void solver_get_orphaned(Solver *solv, Queue *orphanedq)
3018 {
3019   queue_free(orphanedq);
3020   queue_init_clone(orphanedq, &solv->orphaned);
3021 }
3022
3023 void solver_get_recommendations(Solver *solv, Queue *recommendationsq, Queue *suggestionsq, int noselected)
3024 {
3025   Pool *pool = solv->pool;
3026   Queue redoq, disabledq;
3027   int goterase, i;
3028   Solvable *s;
3029   Rule *r;
3030   Map obsmap;
3031
3032   if (!recommendationsq && !suggestionsq)
3033     return;
3034
3035   map_init(&obsmap, pool->nsolvables);
3036   if (solv->installed)
3037     {
3038       Id obs, *obsp, p, po, ppo;
3039       for (p = solv->installed->start; p < solv->installed->end; p++)
3040         {
3041           s = pool->solvables + p;
3042           if (s->repo != solv->installed || !s->obsoletes)
3043             continue;
3044           if (solv->decisionmap[p] <= 0)
3045             continue;
3046           if (solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p))
3047             continue;
3048           obsp = s->repo->idarraydata + s->obsoletes;
3049           /* foreach obsoletes */
3050           while ((obs = *obsp++) != 0)
3051             FOR_PROVIDES(po, ppo, obs)
3052               MAPSET(&obsmap, po);
3053         }
3054     }
3055
3056   queue_init(&redoq);
3057   queue_init(&disabledq);
3058   goterase = 0;
3059   /* disable all erase jobs (including weak "keep uninstalled" rules) */
3060   for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++)
3061     {
3062       if (r->d < 0)     /* disabled ? */
3063         continue;
3064       if (r->p >= 0)    /* install job? */
3065         continue;
3066       queue_push(&disabledq, i);
3067       solver_disablerule(solv, r);
3068       goterase++;
3069     }
3070
3071   if (goterase)
3072     {
3073       enabledisablelearntrules(solv);
3074       removedisabledconflicts(solv, &redoq);
3075     }
3076
3077   /*
3078    * find recommended packages
3079    */
3080   if (recommendationsq)
3081     {
3082       Id rec, *recp, p, pp;
3083
3084       queue_empty(recommendationsq);
3085       /* create map of all recommened packages */
3086       solv->recommends_index = -1;
3087       MAPZERO(&solv->recommendsmap);
3088
3089       /* put all packages the solver already chose in the map */
3090       if (solv->decisioncnt_weak)
3091         {
3092           for (i = solv->decisioncnt_weak; i < solv->decisioncnt_orphan; i++)
3093             {
3094               Id why;
3095               why = solv->decisionq_why.elements[i];
3096               if (why)
3097                 continue;       /* forced by unit rule */
3098               p = solv->decisionq.elements[i];
3099               if (p < 0)
3100                 continue;
3101               MAPSET(&solv->recommendsmap, p);
3102             }
3103         }
3104
3105       for (i = 0; i < solv->decisionq.count; i++)
3106         {
3107           p = solv->decisionq.elements[i];
3108           if (p < 0)
3109             continue;
3110           s = pool->solvables + p;
3111           if (s->recommends)
3112             {
3113               recp = s->repo->idarraydata + s->recommends;
3114               while ((rec = *recp++) != 0)
3115                 {
3116                   FOR_PROVIDES(p, pp, rec)
3117                     if (solv->decisionmap[p] > 0)
3118                       break;
3119                   if (p)
3120                     {
3121                       if (!noselected)
3122                         {
3123                           FOR_PROVIDES(p, pp, rec)
3124                             if (solv->decisionmap[p] > 0)
3125                               MAPSET(&solv->recommendsmap, p);
3126                         }
3127                       continue; /* p != 0: already fulfilled */
3128                     }
3129                   FOR_PROVIDES(p, pp, rec)
3130                     MAPSET(&solv->recommendsmap, p);
3131                 }
3132             }
3133         }
3134       for (i = 1; i < pool->nsolvables; i++)
3135         {
3136           if (solv->decisionmap[i] < 0)
3137             continue;
3138           if (solv->decisionmap[i] > 0 && noselected)
3139             continue;
3140           if (MAPTST(&obsmap, i))
3141             continue;
3142           s = pool->solvables + i;
3143           if (!MAPTST(&solv->recommendsmap, i))
3144             {
3145               if (!s->supplements)
3146                 continue;
3147               if (!pool_installable(pool, s))
3148                 continue;
3149               if (!solver_is_supplementing(solv, s))
3150                 continue;
3151             }
3152           queue_push(recommendationsq, i);
3153         }
3154       /* we use MODE_SUGGEST here so that repo prio is ignored */
3155       policy_filter_unwanted(solv, recommendationsq, POLICY_MODE_SUGGEST);
3156     }
3157
3158   /*
3159    * find suggested packages
3160    */
3161
3162   if (suggestionsq)
3163     {
3164       Id sug, *sugp, p, pp;
3165
3166       queue_empty(suggestionsq);
3167       /* create map of all suggests that are still open */
3168       solv->recommends_index = -1;
3169       MAPZERO(&solv->suggestsmap);
3170       for (i = 0; i < solv->decisionq.count; i++)
3171         {
3172           p = solv->decisionq.elements[i];
3173           if (p < 0)
3174             continue;
3175           s = pool->solvables + p;
3176           if (s->suggests)
3177             {
3178               sugp = s->repo->idarraydata + s->suggests;
3179               while ((sug = *sugp++) != 0)
3180                 {
3181                   FOR_PROVIDES(p, pp, sug)
3182                     if (solv->decisionmap[p] > 0)
3183                       break;
3184                   if (p)
3185                     {
3186                       if (!noselected)
3187                         {
3188                           FOR_PROVIDES(p, pp, sug)
3189                             if (solv->decisionmap[p] > 0)
3190                               MAPSET(&solv->suggestsmap, p);
3191                         }
3192                       continue; /* already fulfilled */
3193                     }
3194                   FOR_PROVIDES(p, pp, sug)
3195                     MAPSET(&solv->suggestsmap, p);
3196                 }
3197             }
3198         }
3199       for (i = 1; i < pool->nsolvables; i++)
3200         {
3201           if (solv->decisionmap[i] < 0)
3202             continue;
3203           if (solv->decisionmap[i] > 0 && noselected)
3204             continue;
3205           if (MAPTST(&obsmap, i))
3206             continue;
3207           s = pool->solvables + i;
3208           if (!MAPTST(&solv->suggestsmap, i))
3209             {
3210               if (!s->enhances)
3211                 continue;
3212               if (!pool_installable(pool, s))
3213                 continue;
3214               if (!solver_is_enhancing(solv, s))
3215                 continue;
3216             }
3217           queue_push(suggestionsq, i);
3218         }
3219       policy_filter_unwanted(solv, suggestionsq, POLICY_MODE_SUGGEST);
3220     }
3221
3222   /* undo removedisabledconflicts */
3223   if (redoq.count)
3224     undo_removedisabledconflicts(solv, &redoq);
3225   queue_free(&redoq);
3226
3227   /* undo job rule disabling */
3228   for (i = 0; i < disabledq.count; i++)
3229     solver_enablerule(solv, solv->rules + disabledq.elements[i]);
3230   queue_free(&disabledq);
3231   map_free(&obsmap);
3232 }
3233
3234
3235 /***********************************************************************/
3236 /* disk usage computations */
3237
3238 /*-------------------------------------------------------------------
3239  *
3240  * calculate DU changes
3241  */
3242
3243 void
3244 solver_calc_duchanges(Solver *solv, DUChanges *mps, int nmps)
3245 {
3246   Map installedmap;
3247
3248   solver_create_state_maps(solv, &installedmap, 0);
3249   pool_calc_duchanges(solv->pool, &installedmap, mps, nmps);
3250   map_free(&installedmap);
3251 }
3252
3253
3254 /*-------------------------------------------------------------------
3255  *
3256  * calculate changes in install size
3257  */
3258
3259 int
3260 solver_calc_installsizechange(Solver *solv)
3261 {
3262   Map installedmap;
3263   int change;
3264
3265   solver_create_state_maps(solv, &installedmap, 0);
3266   change = pool_calc_installsizechange(solv->pool, &installedmap);
3267   map_free(&installedmap);
3268   return change;
3269 }
3270
3271 void
3272 solver_create_state_maps(Solver *solv, Map *installedmap, Map *conflictsmap)
3273 {
3274   pool_create_state_maps(solv->pool, &solv->decisionq, installedmap, conflictsmap);
3275 }
3276
3277 void
3278 solver_trivial_installable(Solver *solv, Queue *pkgs, Queue *res)
3279 {
3280   Map installedmap;
3281   pool_create_state_maps(solv->pool,  &solv->decisionq, &installedmap, 0);
3282   pool_trivial_installable_noobsoletesmap(solv->pool, &installedmap, pkgs, res, solv->noobsoletes.size ? &solv->noobsoletes : 0);
3283   map_free(&installedmap);
3284 }
3285
3286 /*-------------------------------------------------------------------
3287  *
3288  * decision introspection
3289  */
3290
3291 int
3292 solver_get_decisionlevel(Solver *solv, Id p)
3293 {
3294   return solv->decisionmap[p];
3295 }
3296
3297 void
3298 solver_get_decisionqueue(Solver *solv, Queue *decisionq)
3299 {
3300   queue_free(decisionq);
3301   queue_init_clone(decisionq, &solv->decisionq);
3302 }
3303
3304 int
3305 solver_get_lastdecisionblocklevel(Solver *solv)
3306 {
3307   Id p;
3308   if (solv->decisionq.count == 0)
3309     return 0;
3310   p = solv->decisionq.elements[solv->decisionq.count - 1];
3311   if (p < 0)
3312     p = -p;
3313   return solv->decisionmap[p] < 0 ? -solv->decisionmap[p] : solv->decisionmap[p];
3314 }
3315
3316 void
3317 solver_get_decisionblock(Solver *solv, int level, Queue *decisionq)
3318 {
3319   Id p;
3320   int i;
3321
3322   queue_empty(decisionq);
3323   for (i = 0; i < solv->decisionq.count; i++)
3324     {
3325       p = solv->decisionq.elements[i];
3326       if (p < 0)
3327         p = -p;
3328       if (solv->decisionmap[p] == level || solv->decisionmap[p] == -level)
3329         break;
3330     }
3331   if (i == solv->decisionq.count)
3332     return;
3333   for (i = 0; i < solv->decisionq.count; i++)
3334     {
3335       p = solv->decisionq.elements[i];
3336       if (p < 0)
3337         p = -p;
3338       if (solv->decisionmap[p] == level || solv->decisionmap[p] == -level)
3339         queue_push(decisionq, p);
3340       else
3341         break;
3342     }
3343 }
3344
3345 int
3346 solver_describe_decision(Solver *solv, Id p, Id *infop)
3347 {
3348   int i;
3349   Id pp, why;
3350
3351   if (infop)
3352     *infop = 0;
3353   if (!solv->decisionmap[p])
3354     return SOLVER_REASON_UNRELATED;
3355   pp = solv->decisionmap[p] < 0 ? -p : p;
3356   for (i = 0; i < solv->decisionq.count; i++)
3357     if (solv->decisionq.elements[i] == pp)
3358       break;
3359   if (i == solv->decisionq.count)       /* just in case... */
3360     return SOLVER_REASON_UNRELATED;
3361   why = solv->decisionq_why.elements[i];
3362   if (why > 0)
3363     {
3364       if (infop)
3365         *infop = why;
3366       return SOLVER_REASON_UNIT_RULE;
3367     }
3368   why = -why;
3369   if (i < solv->decisioncnt_update)
3370     {
3371       if (i == 0)
3372         {
3373           if (infop)
3374             *infop = SYSTEMSOLVABLE;
3375           return SOLVER_REASON_KEEP_INSTALLED;
3376         }
3377       if (infop)
3378         *infop = why;
3379       return SOLVER_REASON_RESOLVE_JOB;
3380     }
3381   if (i < solv->decisioncnt_keep)
3382     {
3383       if (why == 0 && pp < 0)
3384         return SOLVER_REASON_CLEANDEPS_ERASE;
3385       if (infop)
3386         {
3387           if (why >= solv->updaterules && why < solv->updaterules_end)
3388             *infop = why - solv->updaterules;
3389           else if (why >= solv->featurerules && why < solv->featurerules_end)
3390             *infop = why - solv->featurerules;
3391         }
3392       return SOLVER_REASON_UPDATE_INSTALLED;
3393     }
3394   if (i < solv->decisioncnt_resolve)
3395     {
3396       if (why == 0 && pp < 0)
3397         return SOLVER_REASON_CLEANDEPS_ERASE;
3398       if (infop)
3399         {
3400           if (why >= solv->updaterules && why < solv->updaterules_end)
3401             *infop = why - solv->updaterules;
3402           else if (why >= solv->featurerules && why < solv->featurerules_end)
3403             *infop = why - solv->featurerules;
3404         }
3405       return SOLVER_REASON_KEEP_INSTALLED;
3406     }
3407   if (i < solv->decisioncnt_weak)
3408     {
3409       if (infop)
3410         *infop = why;
3411       return SOLVER_REASON_RESOLVE;
3412     }
3413   if (solv->decisionq.count < solv->decisioncnt_orphan)
3414     return SOLVER_REASON_WEAKDEP;
3415   return SOLVER_REASON_RESOLVE_ORPHAN;
3416 }
3417
3418
3419 void
3420 solver_describe_weakdep_decision(Solver *solv, Id p, Queue *whyq)
3421 {
3422   Pool *pool = solv->pool;
3423   int i;
3424   int level = solv->decisionmap[p];
3425   int decisionno;
3426   Solvable *s;
3427
3428   queue_empty(whyq);
3429   if (level < 0)
3430     return;     /* huh? */
3431   for (decisionno = 0; decisionno < solv->decisionq.count; decisionno++)
3432     if (solv->decisionq.elements[decisionno] == p)
3433       break;
3434   if (decisionno == solv->decisionq.count)
3435     return;     /* huh? */
3436   if (decisionno < solv->decisioncnt_weak || decisionno >= solv->decisioncnt_orphan)
3437     return;     /* huh? */
3438
3439   /* 1) list all packages that recommend us */
3440   for (i = 1; i < pool->nsolvables; i++)
3441     {
3442       Id *recp, rec, pp2, p2;
3443       if (solv->decisionmap[i] < 0 || solv->decisionmap[i] >= level)
3444         continue;
3445       s = pool->solvables + i;
3446       if (!s->recommends)
3447         continue;
3448       if (solv->ignorealreadyrecommended && s->repo == solv->installed)
3449         continue;
3450       recp = s->repo->idarraydata + s->recommends;
3451       while ((rec = *recp++) != 0)
3452         {
3453           int found = 0;
3454           FOR_PROVIDES(p2, pp2, rec)
3455             {
3456               if (p2 == p)
3457                 found = 1;
3458               else
3459                 {
3460                   /* if p2 is already installed, this recommends is ignored */
3461                   if (solv->decisionmap[p2] > 0 && solv->decisionmap[p2] < level)
3462                     break;
3463                 }
3464             }
3465           if (!p2 && found)
3466             {
3467               queue_push(whyq, SOLVER_REASON_RECOMMENDED);
3468               queue_push2(whyq, p2, rec);
3469             }
3470         }
3471     }
3472   /* 2) list all supplements */
3473   s = pool->solvables + p;
3474   if (s->supplements && level > 0)
3475     {
3476       Id *supp, sup, pp2, p2;
3477       /* this is a hack. to use solver_dep_fulfilled we temporarily clear
3478        * everything above our level in the decisionmap */
3479       for (i = decisionno; i < solv->decisionq.count; i++ )
3480         {
3481           p2 = solv->decisionq.elements[i];
3482           if (p2 > 0)
3483             solv->decisionmap[p2] = -solv->decisionmap[p2];
3484         }
3485       supp = s->repo->idarraydata + s->supplements;
3486       while ((sup = *supp++) != 0)
3487         if (solver_dep_fulfilled(solv, sup))
3488           {
3489             int found = 0;
3490             /* let's see if this is an easy supp */
3491             FOR_PROVIDES(p2, pp2, sup)
3492               {
3493                 if (solv->ignorealreadyrecommended && solv->installed)
3494                   {
3495                     if (pool->solvables[p2].repo == solv->installed)
3496                       continue;
3497                   }
3498                 if (solv->decisionmap[p2] > 0 && solv->decisionmap[p2] < level)
3499                   {
3500                     queue_push(whyq, SOLVER_REASON_SUPPLEMENTED);
3501                     queue_push2(whyq, p2, sup);
3502                     found = 1;
3503                   }
3504               }
3505             if (!found)
3506               {
3507                 /* hard case, just note dependency with no package */
3508                 queue_push(whyq, SOLVER_REASON_SUPPLEMENTED);
3509                 queue_push2(whyq, 0, sup);
3510               }
3511           }
3512       for (i = decisionno; i < solv->decisionq.count; i++)
3513         {
3514           p2 = solv->decisionq.elements[i];
3515           if (p2 > 0)
3516             solv->decisionmap[p2] = -solv->decisionmap[p2];
3517         }
3518     }
3519 }