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_ADD_ALREADY_RECOMMENDED:
1389     return solv->addalreadyrecommended;
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_ADD_ALREADY_RECOMMENDED:
1426     solv->addalreadyrecommended = 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 0;
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                   solver_reenablepolicyrules_cleandeps(solv, i);
1482                   mademistake = 1;
1483                 }
1484             }
1485         }
1486     }
1487   if (mademistake)
1488     solver_reset(solv);
1489   return mademistake;
1490 }
1491
1492 /*-------------------------------------------------------------------
1493  *
1494  * solver_run_sat
1495  *
1496  * all rules have been set up, now actually run the solver
1497  *
1498  */
1499
1500 void
1501 solver_run_sat(Solver *solv, int disablerules, int doweak)
1502 {
1503   Queue dq;             /* local decisionqueue */
1504   Queue dqs;            /* local decisionqueue for supplements */
1505   int systemlevel;
1506   int level, olevel;
1507   Rule *r;
1508   int i, j, n;
1509   Solvable *s;
1510   Pool *pool = solv->pool;
1511   Id p, *dp;
1512   int minimizationsteps;
1513   int installedpos = solv->installed ? solv->installed->start : 0;
1514
1515   IF_POOLDEBUG (SOLV_DEBUG_RULE_CREATION)
1516     {
1517       POOL_DEBUG (SOLV_DEBUG_RULE_CREATION, "number of rules: %d\n", solv->nrules);
1518       for (i = 1; i < solv->nrules; i++)
1519         solver_printruleclass(solv, SOLV_DEBUG_RULE_CREATION, solv->rules + i);
1520     }
1521
1522   POOL_DEBUG(SOLV_DEBUG_SOLVER, "initial decisions: %d\n", solv->decisionq.count);
1523
1524   /* start SAT algorithm */
1525   level = 1;
1526   systemlevel = level + 1;
1527   POOL_DEBUG(SOLV_DEBUG_SOLVER, "solving...\n");
1528
1529   queue_init(&dq);
1530   queue_init(&dqs);
1531
1532   /*
1533    * here's the main loop:
1534    * 1) propagate new decisions (only needed once)
1535    * 2) fulfill jobs
1536    * 3) try to keep installed packages
1537    * 4) fulfill all unresolved rules
1538    * 5) install recommended packages
1539    * 6) minimalize solution if we had choices
1540    * if we encounter a problem, we rewind to a safe level and restart
1541    * with step 1
1542    */
1543
1544   minimizationsteps = 0;
1545   for (;;)
1546     {
1547       /*
1548        * initial propagation of the assertions
1549        */
1550       if (level == 1)
1551         {
1552           POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "propagating (propagate_index: %d;  size decisionq: %d)...\n", solv->propagate_index, solv->decisionq.count);
1553           if ((r = propagate(solv, level)) != 0)
1554             {
1555               if (analyze_unsolvable(solv, r, disablerules))
1556                 continue;
1557               level = 0;
1558               break;    /* unsolvable */
1559             }
1560         }
1561
1562       /*
1563        * resolve jobs first
1564        */
1565      if (level < systemlevel)
1566         {
1567           POOL_DEBUG(SOLV_DEBUG_SOLVER, "resolving job rules\n");
1568           for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++)
1569             {
1570               Id l;
1571               if (r->d < 0)             /* ignore disabled rules */
1572                 continue;
1573               queue_empty(&dq);
1574               FOR_RULELITERALS(l, dp, r)
1575                 {
1576                   if (l < 0)
1577                     {
1578                       if (solv->decisionmap[-l] <= 0)
1579                         break;
1580                     }
1581                   else
1582                     {
1583                       if (solv->decisionmap[l] > 0)
1584                         break;
1585                       if (solv->decisionmap[l] == 0)
1586                         queue_push(&dq, l);
1587                     }
1588                 }
1589               if (l || !dq.count)
1590                 continue;
1591               /* prune to installed if not updating */
1592               if (dq.count > 1 && solv->installed && !solv->updatemap_all)
1593                 {
1594                   int j, k;
1595                   for (j = k = 0; j < dq.count; j++)
1596                     {
1597                       Solvable *s = pool->solvables + dq.elements[j];
1598                       if (s->repo == solv->installed)
1599                         {
1600                           dq.elements[k++] = dq.elements[j];
1601                           if (solv->updatemap.size && MAPTST(&solv->updatemap, dq.elements[j] - solv->installed->start))
1602                             {
1603                               k = 0;    /* package wants to be updated, do not prune */
1604                               break;
1605                             }
1606                         }
1607                     }
1608                   if (k)
1609                     dq.count = k;
1610                 }
1611               olevel = level;
1612               level = selectandinstall(solv, level, &dq, disablerules, i);
1613               if (level == 0)
1614                 break;
1615               if (level <= olevel)
1616                 break;
1617             }
1618           if (level == 0)
1619             break;      /* unsolvable */
1620           systemlevel = level + 1;
1621           if (i < solv->jobrules_end)
1622             continue;
1623           solv->decisioncnt_update = solv->decisionq.count;
1624           solv->decisioncnt_keep = solv->decisionq.count;
1625         }
1626
1627       /*
1628        * installed packages
1629        */
1630       if (level < systemlevel && solv->installed && solv->installed->nsolvables && !solv->installed->disabled)
1631         {
1632           Repo *installed = solv->installed;
1633           int pass;
1634
1635           POOL_DEBUG(SOLV_DEBUG_SOLVER, "resolving installed packages\n");
1636           /* we use two passes if we need to update packages
1637            * to create a better user experience */
1638           for (pass = solv->updatemap.size ? 0 : 1; pass < 2; pass++)
1639             {
1640               int passlevel = level;
1641               if (pass == 1)
1642                 solv->decisioncnt_keep = solv->decisionq.count;
1643               /* start with installedpos, the position that gave us problems last time */
1644               for (i = installedpos, n = installed->start; n < installed->end; i++, n++)
1645                 {
1646                   Rule *rr;
1647                   Id d;
1648
1649                   if (i == installed->end)
1650                     i = installed->start;
1651                   s = pool->solvables + i;
1652                   if (s->repo != installed)
1653                     continue;
1654
1655                   if (solv->decisionmap[i] > 0)
1656                     continue;
1657                   if (!pass && solv->updatemap.size && !MAPTST(&solv->updatemap, i - installed->start))
1658                     continue;           /* updates first */
1659                   r = solv->rules + solv->updaterules + (i - installed->start);
1660                   rr = r;
1661                   if (!rr->p || rr->d < 0)      /* disabled -> look at feature rule */
1662                     rr -= solv->installed->end - solv->installed->start;
1663                   if (!rr->p)           /* identical to update rule? */
1664                     rr = r;
1665                   if (!rr->p)
1666                     continue;           /* orpaned package */
1667
1668                   /* XXX: noupdate check is probably no longer needed, as all jobs should
1669                    * already be satisfied */
1670                   /* Actually we currently still need it because of erase jobs */
1671                   /* if noupdate is set we do not look at update candidates */
1672                   queue_empty(&dq);
1673                   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))
1674                     {
1675                       if (solv->noobsoletes.size && solv->multiversionupdaters
1676                              && (d = solv->multiversionupdaters[i - installed->start]) != 0)
1677                         {
1678                           /* special multiversion handling, make sure best version is chosen */
1679                           queue_push(&dq, i);
1680                           while ((p = pool->whatprovidesdata[d++]) != 0)
1681                             if (solv->decisionmap[p] >= 0)
1682                               queue_push(&dq, p);
1683                           policy_filter_unwanted(solv, &dq, POLICY_MODE_CHOOSE);
1684                           p = dq.elements[0];
1685                           if (p != i && solv->decisionmap[p] == 0)
1686                             {
1687                               rr = solv->rules + solv->featurerules + (i - solv->installed->start);
1688                               if (!rr->p)               /* update rule == feature rule? */
1689                                 rr = rr - solv->featurerules + solv->updaterules;
1690                               dq.count = 1;
1691                             }
1692                           else
1693                             dq.count = 0;
1694                         }
1695                       else
1696                         {
1697                           /* update to best package */
1698                           FOR_RULELITERALS(p, dp, rr)
1699                             {
1700                               if (solv->decisionmap[p] > 0)
1701                                 {
1702                                   dq.count = 0;         /* already fulfilled */
1703                                   break;
1704                                 }
1705                               if (!solv->decisionmap[p])
1706                                 queue_push(&dq, p);
1707                             }
1708                         }
1709                     }
1710                   /* install best version */
1711                   if (dq.count)
1712                     {
1713                       olevel = level;
1714                       level = selectandinstall(solv, level, &dq, disablerules, rr - solv->rules);
1715                       if (level == 0)
1716                         {
1717                           queue_free(&dq);
1718                           queue_free(&dqs);
1719                           return;
1720                         }
1721                       if (level <= olevel)
1722                         {
1723                           if (level == 1 || level < passlevel)
1724                             break;      /* trouble */
1725                           if (level < olevel)
1726                             n = installed->start;       /* redo all */
1727                           i--;
1728                           n--;
1729                           continue;
1730                         }
1731                     }
1732                   /* if still undecided keep package */
1733                   if (solv->decisionmap[i] == 0)
1734                     {
1735                       olevel = level;
1736                       if (solv->cleandepsmap.size && MAPTST(&solv->cleandepsmap, i - installed->start))
1737                         {
1738                           POOL_DEBUG(SOLV_DEBUG_POLICY, "cleandeps erasing %s\n", pool_solvid2str(pool, i));
1739                           level = setpropagatelearn(solv, level, -i, disablerules, 0);
1740                         }
1741                       else
1742                         {
1743                           POOL_DEBUG(SOLV_DEBUG_POLICY, "keeping %s\n", pool_solvid2str(pool, i));
1744                           level = setpropagatelearn(solv, level, i, disablerules, r - solv->rules);
1745                         }
1746                       if (level == 0)
1747                         break;
1748                       if (level <= olevel)
1749                         {
1750                           if (level == 1 || level < passlevel)
1751                             break;      /* trouble */
1752                           if (level < olevel)
1753                             n = installed->start;       /* redo all */
1754                           i--;
1755                           n--;
1756                           continue;     /* retry with learnt rule */
1757                         }
1758                     }
1759                 }
1760               if (n < installed->end)
1761                 {
1762                   installedpos = i;     /* retry problem solvable next time */
1763                   break;                /* ran into trouble */
1764                 }
1765               installedpos = installed->start;  /* reset installedpos */
1766             }
1767           if (level == 0)
1768             break;              /* unsolvable */
1769           systemlevel = level + 1;
1770           if (pass < 2)
1771             continue;           /* had trouble, retry */
1772         }
1773
1774       if (level < systemlevel)
1775         systemlevel = level;
1776
1777       /*
1778        * decide
1779        */
1780       solv->decisioncnt_resolve = solv->decisionq.count;
1781       POOL_DEBUG(SOLV_DEBUG_POLICY, "deciding unresolved rules\n");
1782       for (i = 1, n = 1; n < solv->nrules; i++, n++)
1783         {
1784           if (i == solv->nrules)
1785             i = 1;
1786           r = solv->rules + i;
1787           if (r->d < 0)         /* ignore disabled rules */
1788             continue;
1789           queue_empty(&dq);
1790           if (r->d == 0)
1791             {
1792               /* binary or unary rule */
1793               /* need two positive undecided literals */
1794               if (r->p < 0 || r->w2 <= 0)
1795                 continue;
1796               if (solv->decisionmap[r->p] || solv->decisionmap[r->w2])
1797                 continue;
1798               queue_push(&dq, r->p);
1799               queue_push(&dq, r->w2);
1800             }
1801           else
1802             {
1803               /* make sure that
1804                * all negative literals are installed
1805                * no positive literal is installed
1806                * i.e. the rule is not fulfilled and we
1807                * just need to decide on the positive literals
1808                */
1809               if (r->p < 0)
1810                 {
1811                   if (solv->decisionmap[-r->p] <= 0)
1812                     continue;
1813                 }
1814               else
1815                 {
1816                   if (solv->decisionmap[r->p] > 0)
1817                     continue;
1818                   if (solv->decisionmap[r->p] == 0)
1819                     queue_push(&dq, r->p);
1820                 }
1821               dp = pool->whatprovidesdata + r->d;
1822               while ((p = *dp++) != 0)
1823                 {
1824                   if (p < 0)
1825                     {
1826                       if (solv->decisionmap[-p] <= 0)
1827                         break;
1828                     }
1829                   else
1830                     {
1831                       if (solv->decisionmap[p] > 0)
1832                         break;
1833                       if (solv->decisionmap[p] == 0)
1834                         queue_push(&dq, p);
1835                     }
1836                 }
1837               if (p)
1838                 continue;
1839             }
1840           IF_POOLDEBUG (SOLV_DEBUG_PROPAGATE)
1841             {
1842               POOL_DEBUG(SOLV_DEBUG_PROPAGATE, "unfulfilled ");
1843               solver_printruleclass(solv, SOLV_DEBUG_PROPAGATE, r);
1844             }
1845           /* dq.count < 2 cannot happen as this means that
1846            * the rule is unit */
1847           assert(dq.count > 1);
1848
1849           olevel = level;
1850           level = selectandinstall(solv, level, &dq, disablerules, r - solv->rules);
1851           if (level == 0)
1852             break;              /* unsolvable */
1853           if (level < systemlevel || level == 1)
1854             break;              /* trouble */
1855           /* something changed, so look at all rules again */
1856           n = 0;
1857         }
1858
1859       if (n != solv->nrules)    /* ran into trouble? */
1860         {
1861           if (level == 0)
1862             break;              /* unsolvable */
1863           continue;             /* start over */
1864         }
1865
1866       /* at this point we have a consistent system. now do the extras... */
1867
1868       solv->decisioncnt_weak = solv->decisionq.count;
1869       if (doweak)
1870         {
1871           int qcount;
1872
1873           POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended packages\n");
1874           queue_empty(&dq);     /* recommended packages */
1875           queue_empty(&dqs);    /* supplemented packages */
1876           for (i = 1; i < pool->nsolvables; i++)
1877             {
1878               if (solv->decisionmap[i] < 0)
1879                 continue;
1880               if (solv->decisionmap[i] > 0)
1881                 {
1882                   /* installed, check for recommends */
1883                   Id *recp, rec, pp, p;
1884                   s = pool->solvables + i;
1885                   if (!solv->addalreadyrecommended && s->repo == solv->installed)
1886                     continue;
1887                   /* XXX need to special case AND ? */
1888                   if (s->recommends)
1889                     {
1890                       recp = s->repo->idarraydata + s->recommends;
1891                       while ((rec = *recp++) != 0)
1892                         {
1893                           qcount = dq.count;
1894                           FOR_PROVIDES(p, pp, rec)
1895                             {
1896                               if (solv->decisionmap[p] > 0)
1897                                 {
1898                                   dq.count = qcount;
1899                                   break;
1900                                 }
1901                               else if (solv->decisionmap[p] == 0)
1902                                 {
1903                                   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))))
1904                                     continue;
1905                                   queue_pushunique(&dq, p);
1906                                 }
1907                             }
1908                         }
1909                     }
1910                 }
1911               else
1912                 {
1913                   s = pool->solvables + i;
1914                   if (!s->supplements)
1915                     continue;
1916                   if (!pool_installable(pool, s))
1917                     continue;
1918                   if (!solver_is_supplementing(solv, s))
1919                     continue;
1920                   if (solv->dupmap_all && solv->installed && s->repo == solv->installed && (solv->droporphanedmap_all || (solv->droporphanedmap.size && MAPTST(&solv->droporphanedmap, i - solv->installed->start))))
1921                     continue;
1922                   queue_push(&dqs, i);
1923                 }
1924             }
1925
1926           /* filter out all packages obsoleted by installed packages */
1927           /* this is no longer needed if we have reverse obsoletes */
1928           if ((dqs.count || dq.count) && solv->installed)
1929             {
1930               Map obsmap;
1931               Id obs, *obsp, po, ppo;
1932
1933               map_init(&obsmap, pool->nsolvables);
1934               for (p = solv->installed->start; p < solv->installed->end; p++)
1935                 {
1936                   s = pool->solvables + p;
1937                   if (s->repo != solv->installed || !s->obsoletes)
1938                     continue;
1939                   if (solv->decisionmap[p] <= 0)
1940                     continue;
1941                   if (solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p))
1942                     continue;
1943                   obsp = s->repo->idarraydata + s->obsoletes;
1944                   /* foreach obsoletes */
1945                   while ((obs = *obsp++) != 0)
1946                     FOR_PROVIDES(po, ppo, obs)
1947                       MAPSET(&obsmap, po);
1948                 }
1949               for (i = j = 0; i < dqs.count; i++)
1950                 if (!MAPTST(&obsmap, dqs.elements[i]))
1951                   dqs.elements[j++] = dqs.elements[i];
1952               dqs.count = j;
1953               for (i = j = 0; i < dq.count; i++)
1954                 if (!MAPTST(&obsmap, dq.elements[i]))
1955                   dq.elements[j++] = dq.elements[i];
1956               dq.count = j;
1957               map_free(&obsmap);
1958             }
1959
1960           /* filter out all already supplemented packages if requested */
1961           if (!solv->addalreadyrecommended && dqs.count)
1962             {
1963               /* turn off all new packages */
1964               for (i = 0; i < solv->decisionq.count; i++)
1965                 {
1966                   p = solv->decisionq.elements[i];
1967                   if (p < 0)
1968                     continue;
1969                   s = pool->solvables + p;
1970                   if (s->repo && s->repo != solv->installed)
1971                     solv->decisionmap[p] = -solv->decisionmap[p];
1972                 }
1973               /* filter out old supplements */
1974               for (i = j = 0; i < dqs.count; i++)
1975                 {
1976                   p = dqs.elements[i];
1977                   s = pool->solvables + p;
1978                   if (!s->supplements)
1979                     continue;
1980                   if (!solver_is_supplementing(solv, s))
1981                     dqs.elements[j++] = p;
1982                 }
1983               dqs.count = j;
1984               /* undo turning off */
1985               for (i = 0; i < solv->decisionq.count; i++)
1986                 {
1987                   p = solv->decisionq.elements[i];
1988                   if (p < 0)
1989                     continue;
1990                   s = pool->solvables + p;
1991                   if (s->repo && s->repo != solv->installed)
1992                     solv->decisionmap[p] = -solv->decisionmap[p];
1993                 }
1994             }
1995
1996           /* multiversion doesn't mix well with supplements.
1997            * filter supplemented packages where we already decided
1998            * to install a different version (see bnc#501088) */
1999           if (dqs.count && solv->noobsoletes.size)
2000             {
2001               for (i = j = 0; i < dqs.count; i++)
2002                 {
2003                   p = dqs.elements[i];
2004                   if (MAPTST(&solv->noobsoletes, p))
2005                     {
2006                       Id p2, pp2;
2007                       s = pool->solvables + p;
2008                       FOR_PROVIDES(p2, pp2, s->name)
2009                         if (solv->decisionmap[p2] > 0 && pool->solvables[p2].name == s->name)
2010                           break;
2011                       if (p2)
2012                         continue;       /* ignore this package */
2013                     }
2014                   dqs.elements[j++] = p;
2015                 }
2016               dqs.count = j;
2017             }
2018
2019           /* make dq contain both recommended and supplemented pkgs */
2020           if (dqs.count)
2021             {
2022               for (i = 0; i < dqs.count; i++)
2023                 queue_pushunique(&dq, dqs.elements[i]);
2024             }
2025
2026           if (dq.count)
2027             {
2028               Map dqmap;
2029               int decisioncount = solv->decisionq.count;
2030
2031               if (dq.count == 1)
2032                 {
2033                   /* simple case, just one package. no need to choose to best version */
2034                   p = dq.elements[0];
2035                   if (dqs.count)
2036                     POOL_DEBUG(SOLV_DEBUG_POLICY, "installing supplemented %s\n", pool_solvid2str(pool, p));
2037                   else
2038                     POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended %s\n", pool_solvid2str(pool, p));
2039                   level = setpropagatelearn(solv, level, p, 0, 0);
2040                   if (level == 0)
2041                     break;
2042                   continue;     /* back to main loop */
2043                 }
2044
2045               /* filter packages, this gives us the best versions */
2046               policy_filter_unwanted(solv, &dq, POLICY_MODE_RECOMMEND);
2047
2048               /* create map of result */
2049               map_init(&dqmap, pool->nsolvables);
2050               for (i = 0; i < dq.count; i++)
2051                 MAPSET(&dqmap, dq.elements[i]);
2052
2053               /* install all supplemented packages */
2054               for (i = 0; i < dqs.count; i++)
2055                 {
2056                   p = dqs.elements[i];
2057                   if (solv->decisionmap[p] || !MAPTST(&dqmap, p))
2058                     continue;
2059                   POOL_DEBUG(SOLV_DEBUG_POLICY, "installing supplemented %s\n", pool_solvid2str(pool, p));
2060                   olevel = level;
2061                   level = setpropagatelearn(solv, level, p, 0, 0);
2062                   if (level <= olevel)
2063                     break;
2064                 }
2065               if (i < dqs.count || solv->decisionq.count < decisioncount)
2066                 {
2067                   map_free(&dqmap);
2068                   if (level == 0)
2069                     break;
2070                   continue;
2071                 }
2072
2073               /* install all recommended packages */
2074               /* more work as we want to created branches if multiple
2075                * choices are valid */
2076               for (i = 0; i < decisioncount; i++)
2077                 {
2078                   Id rec, *recp, pp;
2079                   p = solv->decisionq.elements[i];
2080                   if (p < 0)
2081                     continue;
2082                   s = pool->solvables + p;
2083                   if (!s->repo || (!solv->addalreadyrecommended && s->repo == solv->installed))
2084                     continue;
2085                   if (!s->recommends)
2086                     continue;
2087                   recp = s->repo->idarraydata + s->recommends;
2088                   while ((rec = *recp++) != 0)
2089                     {
2090                       queue_empty(&dq);
2091                       FOR_PROVIDES(p, pp, rec)
2092                         {
2093                           if (solv->decisionmap[p] > 0)
2094                             {
2095                               dq.count = 0;
2096                               break;
2097                             }
2098                           else if (solv->decisionmap[p] == 0 && MAPTST(&dqmap, p))
2099                             queue_pushunique(&dq, p);
2100                         }
2101                       if (!dq.count)
2102                         continue;
2103                       if (dq.count > 1)
2104                         {
2105                           /* multiple candidates, open a branch */
2106                           for (i = 1; i < dq.count; i++)
2107                             queue_push(&solv->branches, dq.elements[i]);
2108                           queue_push(&solv->branches, -level);
2109                         }
2110                       p = dq.elements[0];
2111                       POOL_DEBUG(SOLV_DEBUG_POLICY, "installing recommended %s\n", pool_solvid2str(pool, p));
2112                       olevel = level;
2113                       level = setpropagatelearn(solv, level, p, 0, 0);
2114                       if (level <= olevel || solv->decisionq.count < decisioncount)
2115                         break;  /* we had to revert some decisions */
2116                     }
2117                   if (rec)
2118                     break;      /* had a problem above, quit loop */
2119                 }
2120               map_free(&dqmap);
2121               if (level == 0)
2122                 break;
2123               continue;         /* back to main loop so that all deps are checked */
2124             }
2125         }
2126
2127       solv->decisioncnt_orphan = solv->decisionq.count;
2128       if (solv->dupmap_all && solv->installed)
2129         {
2130           int installedone = 0;
2131
2132           /* let's see if we can install some unsupported package */
2133           POOL_DEBUG(SOLV_DEBUG_SOLVER, "deciding orphaned packages\n");
2134           for (i = 0; i < solv->orphaned.count; i++)
2135             {
2136               p = solv->orphaned.elements[i];
2137               if (solv->decisionmap[p])
2138                 continue;       /* already decided */
2139               if (solv->droporphanedmap_all)
2140                 continue;
2141               if (solv->droporphanedmap.size && MAPTST(&solv->droporphanedmap, p - solv->installed->start))
2142                 continue;
2143               POOL_DEBUG(SOLV_DEBUG_SOLVER, "keeping orphaned %s\n", pool_solvid2str(pool, p));
2144               olevel = level;
2145               level = setpropagatelearn(solv, level, p, 0, 0);
2146               installedone = 1;
2147               if (level < olevel)
2148                 break;
2149             }
2150           if (installedone || i < solv->orphaned.count)
2151             {
2152               if (level == 0)
2153                 break;
2154               continue;         /* back to main loop */
2155             }
2156           for (i = 0; i < solv->orphaned.count; i++)
2157             {
2158               p = solv->orphaned.elements[i];
2159               if (solv->decisionmap[p])
2160                 continue;       /* already decided */
2161               POOL_DEBUG(SOLV_DEBUG_SOLVER, "removing orphaned %s\n", pool_solvid2str(pool, p));
2162               olevel = level;
2163               level = setpropagatelearn(solv, level, -p, 0, 0);
2164               if (level < olevel)
2165                 break;
2166             }
2167           if (i < solv->orphaned.count)
2168             {
2169               if (level == 0)
2170                 break;
2171               continue;         /* back to main loop */
2172             }
2173         }
2174
2175      if (solv->installed && solv->cleandepsmap.size)
2176         {
2177           if (cleandeps_check_mistakes(solv, level))
2178             {
2179               level = 1;        /* restart from scratch */
2180               continue;
2181             }
2182         }
2183
2184      if (solv->solution_callback)
2185         {
2186           solv->solution_callback(solv, solv->solution_callback_data);
2187           if (solv->branches.count)
2188             {
2189               int i = solv->branches.count - 1;
2190               int l = -solv->branches.elements[i];
2191               Id why;
2192
2193               for (; i > 0; i--)
2194                 if (solv->branches.elements[i - 1] < 0)
2195                   break;
2196               p = solv->branches.elements[i];
2197               POOL_DEBUG(SOLV_DEBUG_SOLVER, "branching with %s\n", pool_solvid2str(pool, p));
2198               queue_empty(&dq);
2199               for (j = i + 1; j < solv->branches.count; j++)
2200                 queue_push(&dq, solv->branches.elements[j]);
2201               solv->branches.count = i;
2202               level = l;
2203               revert(solv, level);
2204               if (dq.count > 1)
2205                 for (j = 0; j < dq.count; j++)
2206                   queue_push(&solv->branches, dq.elements[j]);
2207               olevel = level;
2208               why = -solv->decisionq_why.elements[solv->decisionq_why.count];
2209               assert(why >= 0);
2210               level = setpropagatelearn(solv, level, p, disablerules, why);
2211               if (level == 0)
2212                 break;
2213               continue;
2214             }
2215           /* all branches done, we're finally finished */
2216           break;
2217         }
2218
2219       /* auto-minimization step */
2220      if (solv->branches.count)
2221         {
2222           int l = 0, lasti = -1, lastl = -1;
2223           Id why;
2224
2225           p = 0;
2226           for (i = solv->branches.count - 1; i >= 0; i--)
2227             {
2228               p = solv->branches.elements[i];
2229               if (p < 0)
2230                 l = -p;
2231               else if (p > 0 && solv->decisionmap[p] > l + 1)
2232                 {
2233                   lasti = i;
2234                   lastl = l;
2235                 }
2236             }
2237           if (lasti >= 0)
2238             {
2239               /* kill old solvable so that we do not loop */
2240               p = solv->branches.elements[lasti];
2241               solv->branches.elements[lasti] = 0;
2242               POOL_DEBUG(SOLV_DEBUG_SOLVER, "minimizing %d -> %d with %s\n", solv->decisionmap[p], lastl, pool_solvid2str(pool, p));
2243               minimizationsteps++;
2244
2245               level = lastl;
2246               revert(solv, level);
2247               why = -solv->decisionq_why.elements[solv->decisionq_why.count];
2248               assert(why >= 0);
2249               olevel = level;
2250               level = setpropagatelearn(solv, level, p, disablerules, why);
2251               if (level == 0)
2252                 break;
2253               continue;         /* back to main loop */
2254             }
2255         }
2256       /* no minimization found, we're finally finished! */
2257       break;
2258     }
2259
2260   POOL_DEBUG(SOLV_DEBUG_STATS, "solver statistics: %d learned rules, %d unsolvable, %d minimization steps\n", solv->stats_learned, solv->stats_unsolvable, minimizationsteps);
2261
2262   POOL_DEBUG(SOLV_DEBUG_STATS, "done solving.\n\n");
2263   queue_free(&dq);
2264   queue_free(&dqs);
2265   if (level == 0)
2266     {
2267       /* unsolvable */
2268       solv->decisioncnt_update = solv->decisionq.count;
2269       solv->decisioncnt_keep = solv->decisionq.count;
2270       solv->decisioncnt_resolve = solv->decisionq.count;
2271       solv->decisioncnt_weak = solv->decisionq.count;
2272       solv->decisioncnt_orphan = solv->decisionq.count;
2273     }
2274 #if 0
2275   solver_printdecisionq(solv, SOLV_DEBUG_RESULT);
2276 #endif
2277 }
2278
2279
2280 /*-------------------------------------------------------------------
2281  *
2282  * remove disabled conflicts
2283  *
2284  * purpose: update the decisionmap after some rules were disabled.
2285  * this is used to calculate the suggested/recommended package list.
2286  * Also returns a "removed" list to undo the discisionmap changes.
2287  */
2288
2289 static void
2290 removedisabledconflicts(Solver *solv, Queue *removed)
2291 {
2292   Pool *pool = solv->pool;
2293   int i, n;
2294   Id p, why, *dp;
2295   Id new;
2296   Rule *r;
2297   Id *decisionmap = solv->decisionmap;
2298
2299   queue_empty(removed);
2300   for (i = 0; i < solv->decisionq.count; i++)
2301     {
2302       p = solv->decisionq.elements[i];
2303       if (p > 0)
2304         continue;       /* conflicts only, please */
2305       why = solv->decisionq_why.elements[i];
2306       if (why == 0)
2307         {
2308           /* no rule involved, must be a orphan package drop */
2309           continue;
2310         }
2311       /* we never do conflicts on free decisions, so there
2312        * must have been an unit rule */
2313       assert(why > 0);
2314       r = solv->rules + why;
2315       if (r->d < 0 && decisionmap[-p])
2316         {
2317           /* rule is now disabled, remove from decisionmap */
2318           POOL_DEBUG(SOLV_DEBUG_SOLVER, "removing conflict for package %s[%d]\n", pool_solvid2str(pool, -p), -p);
2319           queue_push(removed, -p);
2320           queue_push(removed, decisionmap[-p]);
2321           decisionmap[-p] = 0;
2322         }
2323     }
2324   if (!removed->count)
2325     return;
2326   /* we removed some confliced packages. some of them might still
2327    * be in conflict, so search for unit rules and re-conflict */
2328   new = 0;
2329   for (i = n = 1, r = solv->rules + i; n < solv->nrules; i++, r++, n++)
2330     {
2331       if (i == solv->nrules)
2332         {
2333           i = 1;
2334           r = solv->rules + i;
2335         }
2336       if (r->d < 0)
2337         continue;
2338       if (!r->w2)
2339         {
2340           if (r->p < 0 && !decisionmap[-r->p])
2341             new = r->p;
2342         }
2343       else if (!r->d)
2344         {
2345           /* binary rule */
2346           if (r->p < 0 && decisionmap[-r->p] == 0 && DECISIONMAP_FALSE(r->w2))
2347             new = r->p;
2348           else if (r->w2 < 0 && decisionmap[-r->w2] == 0 && DECISIONMAP_FALSE(r->p))
2349             new = r->w2;
2350         }
2351       else
2352         {
2353           if (r->p < 0 && decisionmap[-r->p] == 0)
2354             new = r->p;
2355           if (new || DECISIONMAP_FALSE(r->p))
2356             {
2357               dp = pool->whatprovidesdata + r->d;
2358               while ((p = *dp++) != 0)
2359                 {
2360                   if (new && p == new)
2361                     continue;
2362                   if (p < 0 && decisionmap[-p] == 0)
2363                     {
2364                       if (new)
2365                         {
2366                           new = 0;
2367                           break;
2368                         }
2369                       new = p;
2370                     }
2371                   else if (!DECISIONMAP_FALSE(p))
2372                     {
2373                       new = 0;
2374                       break;
2375                     }
2376                 }
2377             }
2378         }
2379       if (new)
2380         {
2381           POOL_DEBUG(SOLV_DEBUG_SOLVER, "re-conflicting package %s[%d]\n", pool_solvid2str(pool, -new), -new);
2382           decisionmap[-new] = -1;
2383           new = 0;
2384           n = 0;        /* redo all rules */
2385         }
2386     }
2387 }
2388
2389 static inline void
2390 undo_removedisabledconflicts(Solver *solv, Queue *removed)
2391 {
2392   int i;
2393   for (i = 0; i < removed->count; i += 2)
2394     solv->decisionmap[removed->elements[i]] = removed->elements[i + 1];
2395 }
2396
2397
2398 /*-------------------------------------------------------------------
2399  *
2400  * weaken solvable dependencies
2401  */
2402
2403 static void
2404 weaken_solvable_deps(Solver *solv, Id p)
2405 {
2406   int i;
2407   Rule *r;
2408
2409   for (i = 1, r = solv->rules + i; i < solv->rpmrules_end; i++, r++)
2410     {
2411       if (r->p != -p)
2412         continue;
2413       if ((r->d == 0 || r->d == -1) && r->w2 < 0)
2414         continue;       /* conflict */
2415       queue_push(&solv->weakruleq, i);
2416     }
2417 }
2418
2419
2420 /********************************************************************/
2421 /* main() */
2422
2423
2424 void
2425 solver_calculate_noobsmap(Pool *pool, Queue *job, Map *noobsmap)
2426 {
2427   int i;
2428   Id how, what, select;
2429   Id p, pp;
2430   for (i = 0; i < job->count; i += 2)
2431     {
2432       how = job->elements[i];
2433       if ((how & SOLVER_JOBMASK) != SOLVER_NOOBSOLETES)
2434         continue;
2435       what = job->elements[i + 1];
2436       select = how & SOLVER_SELECTMASK;
2437       if (!noobsmap->size)
2438         map_grow(noobsmap, pool->nsolvables);
2439       FOR_JOB_SELECT(p, pp, select, what)
2440         MAPSET(noobsmap, p);
2441     }
2442 }
2443
2444 /*
2445  * add a rule created by a job, record job number and weak flag
2446  */
2447 static inline void
2448 solver_addjobrule(Solver *solv, Id p, Id d, Id job, int weak)
2449 {
2450   solver_addrule(solv, p, d);
2451   queue_push(&solv->ruletojob, job);
2452   if (weak)
2453     queue_push(&solv->weakruleq, solv->nrules - 1);
2454 }
2455
2456 /*
2457  *
2458  * solve job queue
2459  *
2460  */
2461
2462 int
2463 solver_solve(Solver *solv, Queue *job)
2464 {
2465   Pool *pool = solv->pool;
2466   Repo *installed = solv->installed;
2467   int i;
2468   int oldnrules;
2469   Map addedmap;                /* '1' == have rpm-rules for solvable */
2470   Map installcandidatemap;
2471   Id how, what, select, name, weak, p, pp, d;
2472   Queue q;
2473   Solvable *s;
2474   Rule *r;
2475   int now, solve_start;
2476   int hasdupjob = 0;
2477
2478   solve_start = solv_timems(0);
2479
2480   /* log solver options */
2481   POOL_DEBUG(SOLV_DEBUG_STATS, "solver started\n");
2482   POOL_DEBUG(SOLV_DEBUG_STATS, "dosplitprovides=%d, noupdateprovide=%d noinfarchcheck=%d\n", solv->dosplitprovides, solv->noupdateprovide, solv->noinfarchcheck);
2483   POOL_DEBUG(SOLV_DEBUG_STATS, "allowuninstall=%d, allowdowngrade=%d, allowarchchange=%d, allowvendorchange=%d\n", solv->allowuninstall, solv->allowdowngrade, solv->allowarchchange, solv->allowvendorchange);
2484   POOL_DEBUG(SOLV_DEBUG_STATS, "promoteepoch=%d, forbidselfconflicts=%d\n", pool->promoteepoch, pool->forbidselfconflicts);
2485   POOL_DEBUG(SOLV_DEBUG_STATS, "obsoleteusesprovides=%d, implicitobsoleteusesprovides=%d, obsoleteusescolors=%d\n", pool->obsoleteusesprovides, pool->implicitobsoleteusesprovides, pool->obsoleteusescolors);
2486   POOL_DEBUG(SOLV_DEBUG_STATS, "dontinstallrecommended=%d, addalreadyrecommended=%d\n", solv->dontinstallrecommended, solv->addalreadyrecommended);
2487
2488   /* create whatprovides if not already there */
2489   if (!pool->whatprovides)
2490     pool_createwhatprovides(pool);
2491
2492   /* create obsolete index */
2493   policy_create_obsolete_index(solv);
2494
2495   /* remember job */
2496   queue_free(&solv->job);
2497   queue_init_clone(&solv->job, job);
2498
2499   /*
2500    * create basic rule set of all involved packages
2501    * use addedmap bitmap to make sure we don't create rules twice
2502    */
2503
2504   /* create noobsolete map if needed */
2505   solver_calculate_noobsmap(pool, job, &solv->noobsoletes);
2506
2507   map_init(&addedmap, pool->nsolvables);
2508   MAPSET(&addedmap, SYSTEMSOLVABLE);
2509
2510   map_init(&installcandidatemap, pool->nsolvables);
2511   queue_init(&q);
2512
2513   now = solv_timems(0);
2514   /*
2515    * create rules for all package that could be involved with the solving
2516    * so called: rpm rules
2517    *
2518    */
2519   if (installed)
2520     {
2521       /* check for update/verify jobs as they need to be known early */
2522       for (i = 0; i < job->count; i += 2)
2523         {
2524           how = job->elements[i];
2525           what = job->elements[i + 1];
2526           select = how & SOLVER_SELECTMASK;
2527           switch (how & SOLVER_JOBMASK)
2528             {
2529             case SOLVER_VERIFY:
2530               if (select == SOLVER_SOLVABLE_ALL)
2531                 solv->fixmap_all = 1;
2532               FOR_JOB_SELECT(p, pp, select, what)
2533                 {
2534                   s = pool->solvables + p;
2535                   if (!solv->installed || s->repo != solv->installed)
2536                     continue;
2537                   if (!solv->fixmap.size)
2538                     map_grow(&solv->fixmap, solv->installed->end - solv->installed->start);
2539                   MAPSET(&solv->fixmap, p - solv->installed->start);
2540                 }
2541               break;
2542             case SOLVER_UPDATE:
2543               if (select == SOLVER_SOLVABLE_ALL)
2544                 solv->updatemap_all = 1;
2545               FOR_JOB_SELECT(p, pp, select, what)
2546                 {
2547                   s = pool->solvables + p;
2548                   if (!solv->installed || s->repo != solv->installed)
2549                     continue;
2550                   if (!solv->updatemap.size)
2551                     map_grow(&solv->updatemap, solv->installed->end - solv->installed->start);
2552                   MAPSET(&solv->updatemap, p - solv->installed->start);
2553                 }
2554               break;
2555             default:
2556               break;
2557             }
2558         }
2559
2560       oldnrules = solv->nrules;
2561       FOR_REPO_SOLVABLES(installed, p, s)
2562         solver_addrpmrulesforsolvable(solv, s, &addedmap);
2563       POOL_DEBUG(SOLV_DEBUG_STATS, "added %d rpm rules for installed solvables\n", solv->nrules - oldnrules);
2564       oldnrules = solv->nrules;
2565       FOR_REPO_SOLVABLES(installed, p, s)
2566         solver_addrpmrulesforupdaters(solv, s, &addedmap, 1);
2567       POOL_DEBUG(SOLV_DEBUG_STATS, "added %d rpm rules for updaters of installed solvables\n", solv->nrules - oldnrules);
2568     }
2569
2570   /*
2571    * create rules for all packages involved in the job
2572    * (to be installed or removed)
2573    */
2574
2575   oldnrules = solv->nrules;
2576   for (i = 0; i < job->count; i += 2)
2577     {
2578       how = job->elements[i];
2579       what = job->elements[i + 1];
2580       select = how & SOLVER_SELECTMASK;
2581
2582       switch (how & SOLVER_JOBMASK)
2583         {
2584         case SOLVER_INSTALL:
2585           FOR_JOB_SELECT(p, pp, select, what)
2586             {
2587               MAPSET(&installcandidatemap, p);
2588               solver_addrpmrulesforsolvable(solv, pool->solvables + p, &addedmap);
2589             }
2590           break;
2591         case SOLVER_DISTUPGRADE:
2592           if (select == SOLVER_SOLVABLE_ALL)
2593             {
2594               solv->dupmap_all = 1;
2595               solv->updatemap_all = 1;
2596             }
2597           if (!solv->dupmap_all)
2598             hasdupjob = 1;
2599           break;
2600         default:
2601           break;
2602         }
2603     }
2604   POOL_DEBUG(SOLV_DEBUG_STATS, "added %d rpm rules for packages involved in a job\n", solv->nrules - oldnrules);
2605
2606
2607   /*
2608    * add rules for suggests, enhances
2609    */
2610   oldnrules = solv->nrules;
2611   solver_addrpmrulesforweak(solv, &addedmap);
2612   POOL_DEBUG(SOLV_DEBUG_STATS, "added %d rpm rules because of weak dependencies\n", solv->nrules - oldnrules);
2613
2614   /*
2615    * first pass done, we now have all the rpm rules we need.
2616    * unify existing rules before going over all job rules and
2617    * policy rules.
2618    * at this point the system is always solvable,
2619    * as an empty system (remove all packages) is a valid solution
2620    */
2621
2622   IF_POOLDEBUG (SOLV_DEBUG_STATS)
2623     {
2624       int possible = 0, installable = 0;
2625       for (i = 1; i < pool->nsolvables; i++)
2626         {
2627           if (pool_installable(pool, pool->solvables + i))
2628             installable++;
2629           if (MAPTST(&addedmap, i))
2630             possible++;
2631         }
2632       POOL_DEBUG(SOLV_DEBUG_STATS, "%d of %d installable solvables considered for solving\n", possible, installable);
2633     }
2634
2635   solver_unifyrules(solv);                          /* remove duplicate rpm rules */
2636   solv->rpmrules_end = solv->nrules;              /* mark end of rpm rules */
2637
2638   POOL_DEBUG(SOLV_DEBUG_STATS, "rpm rule memory usage: %d K\n", solv->nrules * (int)sizeof(Rule) / 1024);
2639   POOL_DEBUG(SOLV_DEBUG_STATS, "rpm rule creation took %d ms\n", solv_timems(now));
2640
2641   /* create dup maps if needed. We need the maps early to create our
2642    * update rules */
2643   if (hasdupjob)
2644     solver_createdupmaps(solv);
2645
2646   /*
2647    * create feature rules
2648    *
2649    * foreach installed:
2650    *   create assertion (keep installed, if no update available)
2651    *   or
2652    *   create update rule (A|update1(A)|update2(A)|...)
2653    *
2654    * those are used later on to keep a version of the installed packages in
2655    * best effort mode
2656    */
2657
2658   solv->featurerules = solv->nrules;              /* mark start of feature rules */
2659   if (installed)
2660     {
2661       /* foreach possibly installed solvable */
2662       for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
2663         {
2664           if (s->repo != installed)
2665             {
2666               solver_addrule(solv, 0, 0);       /* create dummy rule */
2667               continue;
2668             }
2669           solver_addupdaterule(solv, s, 1);    /* allow s to be updated */
2670         }
2671       /* make sure we accounted for all rules */
2672       assert(solv->nrules - solv->featurerules == installed->end - installed->start);
2673     }
2674   solv->featurerules_end = solv->nrules;
2675
2676     /*
2677      * Add update rules for installed solvables
2678      *
2679      * almost identical to feature rules
2680      * except that downgrades/archchanges/vendorchanges are not allowed
2681      */
2682
2683   solv->updaterules = solv->nrules;
2684
2685   if (installed)
2686     { /* foreach installed solvables */
2687       /* we create all update rules, but disable some later on depending on the job */
2688       for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
2689         {
2690           Rule *sr;
2691
2692           if (s->repo != installed)
2693             {
2694               solver_addrule(solv, 0, 0);       /* create dummy rule */
2695               continue;
2696             }
2697           solver_addupdaterule(solv, s, 0);     /* allowall = 0: downgrades not allowed */
2698           /*
2699            * check for and remove duplicate
2700            */
2701           r = solv->rules + solv->nrules - 1;           /* r: update rule */
2702           sr = r - (installed->end - installed->start); /* sr: feature rule */
2703           /* it's orphaned if there is no feature rule or the feature rule
2704            * consists just of the installed package */
2705           if (!sr->p || (sr->p == i && !sr->d && !sr->w2))
2706             queue_push(&solv->orphaned, i);
2707           if (!r->p)
2708             {
2709               assert(solv->dupmap_all && !sr->p);
2710               continue;
2711             }
2712           if (!solver_samerule(solv, r, sr))
2713             {
2714               /* identical rule, kill unneeded one */
2715               if (solv->allowuninstall)
2716                 {
2717                   /* keep feature rule, make it weak */
2718                   memset(r, 0, sizeof(*r));
2719                   queue_push(&solv->weakruleq, sr - solv->rules);
2720                 }
2721               else
2722                 {
2723                   /* keep update rule */
2724                   memset(sr, 0, sizeof(*sr));
2725                 }
2726             }
2727           else if (solv->allowuninstall)
2728             {
2729               /* make both feature and update rule weak */
2730               queue_push(&solv->weakruleq, r - solv->rules);
2731               queue_push(&solv->weakruleq, sr - solv->rules);
2732             }
2733           else
2734             solver_disablerule(solv, sr);
2735         }
2736       /* consistency check: we added a rule for _every_ installed solvable */
2737       assert(solv->nrules - solv->updaterules == installed->end - installed->start);
2738     }
2739   solv->updaterules_end = solv->nrules;
2740
2741
2742   /*
2743    * now add all job rules
2744    */
2745
2746   solv->jobrules = solv->nrules;
2747   if (solv->cleandeps_updatepkgs)
2748     {
2749       queue_free(solv->cleandeps_updatepkgs);
2750       solv->cleandeps_updatepkgs = solv_free(solv->cleandeps_updatepkgs);
2751     }
2752   for (i = 0; i < job->count; i += 2)
2753     {
2754       oldnrules = solv->nrules;
2755
2756       how = job->elements[i];
2757       what = job->elements[i + 1];
2758       weak = how & SOLVER_WEAK;
2759       select = how & SOLVER_SELECTMASK;
2760       switch (how & SOLVER_JOBMASK)
2761         {
2762         case SOLVER_INSTALL:
2763           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sinstall %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
2764           if ((how & SOLVER_CLEANDEPS) != 0 && !solv->cleandepsmap.size && installed)
2765             map_grow(&solv->cleandepsmap, installed->end - installed->start);
2766           if (select == SOLVER_SOLVABLE)
2767             {
2768               p = what;
2769               d = 0;
2770             }
2771           else
2772             {
2773               queue_empty(&q);
2774               FOR_JOB_SELECT(p, pp, select, what)
2775                 queue_push(&q, p);
2776               if (!q.count)
2777                 {
2778                   /* no candidate found, make this an impossible rule */
2779                   queue_push(&q, -SYSTEMSOLVABLE);
2780                 }
2781               p = queue_shift(&q);      /* get first candidate */
2782               d = !q.count ? 0 : pool_queuetowhatprovides(pool, &q);    /* internalize */
2783             }
2784           solver_addjobrule(solv, p, d, i, weak);
2785           break;
2786         case SOLVER_ERASE:
2787           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %s%serase %s\n", weak ? "weak " : "", how & SOLVER_CLEANDEPS ? "clean deps " : "", solver_select2str(pool, select, what));
2788           if ((how & SOLVER_CLEANDEPS) != 0 && !solv->cleandepsmap.size && installed)
2789             map_grow(&solv->cleandepsmap, installed->end - installed->start);
2790           name = (select == SOLVER_SOLVABLE || (select == SOLVER_SOLVABLE_NAME && ISRELDEP(what))) ? 0 : -1;
2791           FOR_JOB_SELECT(p, pp, select, what)
2792             {
2793               s = pool->solvables + p;
2794               if (installed && s->repo == installed)
2795                 name = !name ? s->name : -1;
2796               solver_addjobrule(solv, -p, 0, i, weak);
2797             }
2798           /* special case for "erase a specific solvable": we also
2799            * erase all other solvables with that name, so that they
2800            * don't get picked up as replacement.
2801            * name is > 0 if exactly one installed solvable matched.
2802            */
2803           /* XXX: look also at packages that obsolete this package? */
2804           if (name > 0)
2805             {
2806               int j, k;
2807               k = solv->nrules;
2808               FOR_PROVIDES(p, pp, name)
2809                 {
2810                   s = pool->solvables + p;
2811                   if (s->name != name)
2812                     continue;
2813                   /* keep other versions installed */
2814                   if (s->repo == installed)
2815                     continue;
2816                   /* keep installcandidates of other jobs */
2817                   if (MAPTST(&installcandidatemap, p))
2818                     continue;
2819                   /* don't add the same rule twice */
2820                   for (j = oldnrules; j < k; j++)
2821                     if (solv->rules[j].p == -p)
2822                       break;
2823                   if (j == k)
2824                     solver_addjobrule(solv, -p, 0, i, weak);    /* remove by id */
2825                 }
2826             }
2827           break;
2828
2829         case SOLVER_UPDATE:
2830           if ((how & SOLVER_CLEANDEPS) != 0 && installed)
2831             {
2832               FOR_JOB_SELECT(p, pp, select, what)
2833                 {
2834                   s = pool->solvables + p;
2835                   if (s->repo != installed)
2836                     continue;
2837                   if (!solv->cleandeps_updatepkgs)
2838                     {
2839                       solv->cleandeps_updatepkgs = solv_calloc(1, sizeof(Queue));
2840                       queue_init(solv->cleandeps_updatepkgs);
2841                     }
2842                   queue_pushunique(solv->cleandeps_updatepkgs, p);
2843                   if (!solv->cleandepsmap.size)
2844                     map_grow(&solv->cleandepsmap, installed->end - installed->start);
2845                 }
2846             }
2847           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %supdate %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
2848           break;
2849         case SOLVER_VERIFY:
2850           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sverify %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
2851           break;
2852         case SOLVER_WEAKENDEPS:
2853           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sweaken deps %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
2854           if (select != SOLVER_SOLVABLE)
2855             break;
2856           s = pool->solvables + what;
2857           weaken_solvable_deps(solv, what);
2858           break;
2859         case SOLVER_NOOBSOLETES:
2860           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %sno obsolete %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
2861           break;
2862         case SOLVER_LOCK:
2863           POOL_DEBUG(SOLV_DEBUG_JOB, "job: %slock %s\n", weak ? "weak " : "", solver_select2str(pool, select, what));
2864           FOR_JOB_SELECT(p, pp, select, what)
2865             {
2866               s = pool->solvables + p;
2867               solver_addjobrule(solv, installed && s->repo == installed ? p : -p, 0, i, weak);
2868             }
2869           break;
2870         case SOLVER_DISTUPGRADE:
2871           POOL_DEBUG(SOLV_DEBUG_JOB, "job: distupgrade %s\n", solver_select2str(pool, select, what));
2872           break;
2873         case SOLVER_DROP_ORPHANED:
2874           POOL_DEBUG(SOLV_DEBUG_JOB, "job: drop orphaned %s\n", solver_select2str(pool, select, what));
2875           if (select == SOLVER_SOLVABLE_ALL)
2876             solv->droporphanedmap_all = 1;
2877           FOR_JOB_SELECT(p, pp, select, what)
2878             {
2879               s = pool->solvables + p;
2880               if (!installed || s->repo != installed)
2881                 continue;
2882               if (!solv->droporphanedmap.size)
2883                 map_grow(&solv->droporphanedmap, installed->end - installed->start);
2884               MAPSET(&solv->droporphanedmap, p - installed->start);
2885             }
2886           break;
2887         case SOLVER_USERINSTALLED:
2888           POOL_DEBUG(SOLV_DEBUG_JOB, "job: user installed %s\n", solver_select2str(pool, select, what));
2889           break;
2890         default:
2891           POOL_DEBUG(SOLV_DEBUG_JOB, "job: unknown job\n");
2892           break;
2893         }
2894
2895         /*
2896          * debug
2897          */
2898
2899       IF_POOLDEBUG (SOLV_DEBUG_JOB)
2900         {
2901           int j;
2902           if (solv->nrules == oldnrules)
2903             POOL_DEBUG(SOLV_DEBUG_JOB, " - no rule created\n");
2904           for (j = oldnrules; j < solv->nrules; j++)
2905             {
2906               POOL_DEBUG(SOLV_DEBUG_JOB, " - job ");
2907               solver_printrule(solv, SOLV_DEBUG_JOB, solv->rules + j);
2908             }
2909         }
2910     }
2911   assert(solv->ruletojob.count == solv->nrules - solv->jobrules);
2912   solv->jobrules_end = solv->nrules;
2913
2914   /* now create infarch and dup rules */
2915   if (!solv->noinfarchcheck)
2916     {
2917       solver_addinfarchrules(solv, &addedmap);
2918       if (pool->obsoleteusescolors)
2919         {
2920           /* currently doesn't work well with infarch rules, so make
2921            * them weak */
2922           for (i = solv->infarchrules; i < solv->infarchrules_end; i++)
2923             queue_push(&solv->weakruleq, i);
2924         }
2925     }
2926   else
2927     solv->infarchrules = solv->infarchrules_end = solv->nrules;
2928
2929   if (hasdupjob)
2930     {
2931       solver_addduprules(solv, &addedmap);
2932       solver_freedupmaps(solv); /* no longer needed */
2933     }
2934   else
2935     solv->duprules = solv->duprules_end = solv->nrules;
2936
2937   if (1)
2938     solver_addchoicerules(solv);
2939   else
2940     solv->choicerules = solv->choicerules_end = solv->nrules;
2941
2942   /* all rules created
2943    * --------------------------------------------------------------
2944    * prepare for solving
2945    */
2946
2947   /* free unneeded memory */
2948   map_free(&addedmap);
2949   map_free(&installcandidatemap);
2950   queue_free(&q);
2951
2952   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);
2953
2954   /* create weak map */
2955   map_init(&solv->weakrulemap, solv->nrules);
2956   for (i = 0; i < solv->weakruleq.count; i++)
2957     {
2958       p = solv->weakruleq.elements[i];
2959       MAPSET(&solv->weakrulemap, p);
2960     }
2961
2962   /* all new rules are learnt after this point */
2963   solv->learntrules = solv->nrules;
2964
2965   /* create watches chains */
2966   makewatches(solv);
2967
2968   /* create assertion index. it is only used to speed up
2969    * makeruledecsions() a bit */
2970   for (i = 1, r = solv->rules + i; i < solv->nrules; i++, r++)
2971     if (r->p && !r->w2 && (r->d == 0 || r->d == -1))
2972       queue_push(&solv->ruleassertions, i);
2973
2974   /* disable update rules that conflict with our job */
2975   solver_disablepolicyrules(solv);
2976
2977   /* make initial decisions based on assertion rules */
2978   makeruledecisions(solv);
2979   POOL_DEBUG(SOLV_DEBUG_SOLVER, "problems so far: %d\n", solv->problems.count);
2980
2981   /* no mistakes */
2982   if (solv->cleandeps_mistakes)
2983     {
2984       queue_free(solv->cleandeps_mistakes);
2985       solv->cleandeps_mistakes = solv_free(solv->cleandeps_mistakes);
2986     }
2987
2988   /*
2989    * ********************************************
2990    * solve!
2991    * ********************************************
2992    */
2993
2994   now = solv_timems(0);
2995   solver_run_sat(solv, 1, solv->dontinstallrecommended ? 0 : 1);
2996   POOL_DEBUG(SOLV_DEBUG_STATS, "solver took %d ms\n", solv_timems(now));
2997
2998   /*
2999    * prepare solution queue if there were problems
3000    */
3001   solver_prepare_solutions(solv);
3002
3003   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);
3004   POOL_DEBUG(SOLV_DEBUG_STATS, "solver_solve took %d ms\n", solv_timems(solve_start));
3005
3006   /* return number of problems */
3007   return solv->problems.count ? solv->problems.count / 2 : 0;
3008 }
3009
3010 Transaction *
3011 solver_create_transaction(Solver *solv)
3012 {
3013   return transaction_create_decisionq(solv->pool, &solv->decisionq, &solv->noobsoletes);
3014 }
3015
3016 void solver_get_orphaned(Solver *solv, Queue *orphanedq)
3017 {
3018   queue_free(orphanedq);
3019   queue_init_clone(orphanedq, &solv->orphaned);
3020 }
3021
3022 void solver_get_recommendations(Solver *solv, Queue *recommendationsq, Queue *suggestionsq, int noselected)
3023 {
3024   Pool *pool = solv->pool;
3025   Queue redoq, disabledq;
3026   int goterase, i;
3027   Solvable *s;
3028   Rule *r;
3029   Map obsmap;
3030
3031   if (!recommendationsq && !suggestionsq)
3032     return;
3033
3034   map_init(&obsmap, pool->nsolvables);
3035   if (solv->installed)
3036     {
3037       Id obs, *obsp, p, po, ppo;
3038       for (p = solv->installed->start; p < solv->installed->end; p++)
3039         {
3040           s = pool->solvables + p;
3041           if (s->repo != solv->installed || !s->obsoletes)
3042             continue;
3043           if (solv->decisionmap[p] <= 0)
3044             continue;
3045           if (solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p))
3046             continue;
3047           obsp = s->repo->idarraydata + s->obsoletes;
3048           /* foreach obsoletes */
3049           while ((obs = *obsp++) != 0)
3050             FOR_PROVIDES(po, ppo, obs)
3051               MAPSET(&obsmap, po);
3052         }
3053     }
3054
3055   queue_init(&redoq);
3056   queue_init(&disabledq);
3057   goterase = 0;
3058   /* disable all erase jobs (including weak "keep uninstalled" rules) */
3059   for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++)
3060     {
3061       if (r->d < 0)     /* disabled ? */
3062         continue;
3063       if (r->p >= 0)    /* install job? */
3064         continue;
3065       queue_push(&disabledq, i);
3066       solver_disablerule(solv, r);
3067       goterase++;
3068     }
3069
3070   if (goterase)
3071     {
3072       enabledisablelearntrules(solv);
3073       removedisabledconflicts(solv, &redoq);
3074     }
3075
3076   /*
3077    * find recommended packages
3078    */
3079   if (recommendationsq)
3080     {
3081       Id rec, *recp, p, pp;
3082
3083       queue_empty(recommendationsq);
3084       /* create map of all recommened packages */
3085       solv->recommends_index = -1;
3086       MAPZERO(&solv->recommendsmap);
3087
3088       /* put all packages the solver already chose in the map */
3089       if (solv->decisioncnt_weak)
3090         {
3091           for (i = solv->decisioncnt_weak; i < solv->decisioncnt_orphan; i++)
3092             {
3093               Id why;
3094               why = solv->decisionq_why.elements[i];
3095               if (why)
3096                 continue;       /* forced by unit rule */
3097               p = solv->decisionq.elements[i];
3098               if (p < 0)
3099                 continue;
3100               MAPSET(&solv->recommendsmap, p);
3101             }
3102         }
3103
3104       for (i = 0; i < solv->decisionq.count; i++)
3105         {
3106           p = solv->decisionq.elements[i];
3107           if (p < 0)
3108             continue;
3109           s = pool->solvables + p;
3110           if (s->recommends)
3111             {
3112               recp = s->repo->idarraydata + s->recommends;
3113               while ((rec = *recp++) != 0)
3114                 {
3115                   FOR_PROVIDES(p, pp, rec)
3116                     if (solv->decisionmap[p] > 0)
3117                       break;
3118                   if (p)
3119                     {
3120                       if (!noselected)
3121                         {
3122                           FOR_PROVIDES(p, pp, rec)
3123                             if (solv->decisionmap[p] > 0)
3124                               MAPSET(&solv->recommendsmap, p);
3125                         }
3126                       continue; /* p != 0: already fulfilled */
3127                     }
3128                   FOR_PROVIDES(p, pp, rec)
3129                     MAPSET(&solv->recommendsmap, p);
3130                 }
3131             }
3132         }
3133       for (i = 1; i < pool->nsolvables; i++)
3134         {
3135           if (solv->decisionmap[i] < 0)
3136             continue;
3137           if (solv->decisionmap[i] > 0 && noselected)
3138             continue;
3139           if (MAPTST(&obsmap, i))
3140             continue;
3141           s = pool->solvables + i;
3142           if (!MAPTST(&solv->recommendsmap, i))
3143             {
3144               if (!s->supplements)
3145                 continue;
3146               if (!pool_installable(pool, s))
3147                 continue;
3148               if (!solver_is_supplementing(solv, s))
3149                 continue;
3150             }
3151           queue_push(recommendationsq, i);
3152         }
3153       /* we use MODE_SUGGEST here so that repo prio is ignored */
3154       policy_filter_unwanted(solv, recommendationsq, POLICY_MODE_SUGGEST);
3155     }
3156
3157   /*
3158    * find suggested packages
3159    */
3160
3161   if (suggestionsq)
3162     {
3163       Id sug, *sugp, p, pp;
3164
3165       queue_empty(suggestionsq);
3166       /* create map of all suggests that are still open */
3167       solv->recommends_index = -1;
3168       MAPZERO(&solv->suggestsmap);
3169       for (i = 0; i < solv->decisionq.count; i++)
3170         {
3171           p = solv->decisionq.elements[i];
3172           if (p < 0)
3173             continue;
3174           s = pool->solvables + p;
3175           if (s->suggests)
3176             {
3177               sugp = s->repo->idarraydata + s->suggests;
3178               while ((sug = *sugp++) != 0)
3179                 {
3180                   FOR_PROVIDES(p, pp, sug)
3181                     if (solv->decisionmap[p] > 0)
3182                       break;
3183                   if (p)
3184                     {
3185                       if (!noselected)
3186                         {
3187                           FOR_PROVIDES(p, pp, sug)
3188                             if (solv->decisionmap[p] > 0)
3189                               MAPSET(&solv->suggestsmap, p);
3190                         }
3191                       continue; /* already fulfilled */
3192                     }
3193                   FOR_PROVIDES(p, pp, sug)
3194                     MAPSET(&solv->suggestsmap, p);
3195                 }
3196             }
3197         }
3198       for (i = 1; i < pool->nsolvables; i++)
3199         {
3200           if (solv->decisionmap[i] < 0)
3201             continue;
3202           if (solv->decisionmap[i] > 0 && noselected)
3203             continue;
3204           if (MAPTST(&obsmap, i))
3205             continue;
3206           s = pool->solvables + i;
3207           if (!MAPTST(&solv->suggestsmap, i))
3208             {
3209               if (!s->enhances)
3210                 continue;
3211               if (!pool_installable(pool, s))
3212                 continue;
3213               if (!solver_is_enhancing(solv, s))
3214                 continue;
3215             }
3216           queue_push(suggestionsq, i);
3217         }
3218       policy_filter_unwanted(solv, suggestionsq, POLICY_MODE_SUGGEST);
3219     }
3220
3221   /* undo removedisabledconflicts */
3222   if (redoq.count)
3223     undo_removedisabledconflicts(solv, &redoq);
3224   queue_free(&redoq);
3225
3226   /* undo job rule disabling */
3227   for (i = 0; i < disabledq.count; i++)
3228     solver_enablerule(solv, solv->rules + disabledq.elements[i]);
3229   queue_free(&disabledq);
3230   map_free(&obsmap);
3231 }
3232
3233
3234 /***********************************************************************/
3235 /* disk usage computations */
3236
3237 /*-------------------------------------------------------------------
3238  *
3239  * calculate DU changes
3240  */
3241
3242 void
3243 solver_calc_duchanges(Solver *solv, DUChanges *mps, int nmps)
3244 {
3245   Map installedmap;
3246
3247   solver_create_state_maps(solv, &installedmap, 0);
3248   pool_calc_duchanges(solv->pool, &installedmap, mps, nmps);
3249   map_free(&installedmap);
3250 }
3251
3252
3253 /*-------------------------------------------------------------------
3254  *
3255  * calculate changes in install size
3256  */
3257
3258 int
3259 solver_calc_installsizechange(Solver *solv)
3260 {
3261   Map installedmap;
3262   int change;
3263
3264   solver_create_state_maps(solv, &installedmap, 0);
3265   change = pool_calc_installsizechange(solv->pool, &installedmap);
3266   map_free(&installedmap);
3267   return change;
3268 }
3269
3270 void
3271 solver_create_state_maps(Solver *solv, Map *installedmap, Map *conflictsmap)
3272 {
3273   pool_create_state_maps(solv->pool, &solv->decisionq, installedmap, conflictsmap);
3274 }
3275
3276 void
3277 solver_trivial_installable(Solver *solv, Queue *pkgs, Queue *res)
3278 {
3279   Map installedmap;
3280   pool_create_state_maps(solv->pool,  &solv->decisionq, &installedmap, 0);
3281   pool_trivial_installable_noobsoletesmap(solv->pool, &installedmap, pkgs, res, solv->noobsoletes.size ? &solv->noobsoletes : 0);
3282   map_free(&installedmap);
3283 }
3284
3285 /*-------------------------------------------------------------------
3286  *
3287  * decision introspection
3288  */
3289
3290 int
3291 solver_get_decisionlevel(Solver *solv, Id p)
3292 {
3293   return solv->decisionmap[p];
3294 }
3295
3296 void
3297 solver_get_decisionqueue(Solver *solv, Queue *decisionq)
3298 {
3299   queue_free(decisionq);
3300   queue_init_clone(decisionq, &solv->decisionq);
3301 }
3302
3303 int
3304 solver_get_lastdecisionblocklevel(Solver *solv)
3305 {
3306   Id p;
3307   if (solv->decisionq.count == 0)
3308     return 0;
3309   p = solv->decisionq.elements[solv->decisionq.count - 1];
3310   if (p < 0)
3311     p = -p;
3312   return solv->decisionmap[p] < 0 ? -solv->decisionmap[p] : solv->decisionmap[p];
3313 }
3314
3315 void
3316 solver_get_decisionblock(Solver *solv, int level, Queue *decisionq)
3317 {
3318   Id p;
3319   int i;
3320
3321   queue_empty(decisionq);
3322   for (i = 0; i < solv->decisionq.count; i++)
3323     {
3324       p = solv->decisionq.elements[i];
3325       if (p < 0)
3326         p = -p;
3327       if (solv->decisionmap[p] == level || solv->decisionmap[p] == -level)
3328         break;
3329     }
3330   if (i == solv->decisionq.count)
3331     return;
3332   for (i = 0; i < solv->decisionq.count; i++)
3333     {
3334       p = solv->decisionq.elements[i];
3335       if (p < 0)
3336         p = -p;
3337       if (solv->decisionmap[p] == level || solv->decisionmap[p] == -level)
3338         queue_push(decisionq, p);
3339       else
3340         break;
3341     }
3342 }
3343
3344 int
3345 solver_describe_decision(Solver *solv, Id p, Id *infop)
3346 {
3347   int i;
3348   Id pp, why;
3349
3350   if (infop)
3351     *infop = 0;
3352   if (!solv->decisionmap[p])
3353     return SOLVER_REASON_UNRELATED;
3354   pp = solv->decisionmap[p] < 0 ? -p : p;
3355   for (i = 0; i < solv->decisionq.count; i++)
3356     if (solv->decisionq.elements[i] == pp)
3357       break;
3358   if (i == solv->decisionq.count)       /* just in case... */
3359     return SOLVER_REASON_UNRELATED;
3360   why = solv->decisionq_why.elements[i];
3361   if (why > 0)
3362     {
3363       if (infop)
3364         *infop = why;
3365       return SOLVER_REASON_UNIT_RULE;
3366     }
3367   why = -why;
3368   if (i < solv->decisioncnt_update)
3369     {
3370       if (i == 0)
3371         {
3372           if (infop)
3373             *infop = SYSTEMSOLVABLE;
3374           return SOLVER_REASON_KEEP_INSTALLED;
3375         }
3376       if (infop)
3377         *infop = why;
3378       return SOLVER_REASON_RESOLVE_JOB;
3379     }
3380   if (i < solv->decisioncnt_keep)
3381     {
3382       if (why == 0 && pp < 0)
3383         return SOLVER_REASON_CLEANDEPS_ERASE;
3384       if (infop)
3385         {
3386           if (why >= solv->updaterules && why < solv->updaterules_end)
3387             *infop = why - solv->updaterules;
3388           else if (why >= solv->featurerules && why < solv->featurerules_end)
3389             *infop = why - solv->featurerules;
3390         }
3391       return SOLVER_REASON_UPDATE_INSTALLED;
3392     }
3393   if (i < solv->decisioncnt_resolve)
3394     {
3395       if (why == 0 && pp < 0)
3396         return SOLVER_REASON_CLEANDEPS_ERASE;
3397       if (infop)
3398         {
3399           if (why >= solv->updaterules && why < solv->updaterules_end)
3400             *infop = why - solv->updaterules;
3401           else if (why >= solv->featurerules && why < solv->featurerules_end)
3402             *infop = why - solv->featurerules;
3403         }
3404       return SOLVER_REASON_KEEP_INSTALLED;
3405     }
3406   if (i < solv->decisioncnt_weak)
3407     {
3408       if (infop)
3409         *infop = why;
3410       return SOLVER_REASON_RESOLVE;
3411     }
3412   if (solv->decisionq.count < solv->decisioncnt_orphan)
3413     return SOLVER_REASON_WEAKDEP;
3414   return SOLVER_REASON_RESOLVE_ORPHAN;
3415 }
3416
3417
3418 void
3419 solver_describe_weakdep_decision(Solver *solv, Id p, Queue *whyq)
3420 {
3421   Pool *pool = solv->pool;
3422   int i;
3423   int level = solv->decisionmap[p];
3424   int decisionno;
3425   Solvable *s;
3426
3427   queue_empty(whyq);
3428   if (level < 0)
3429     return;     /* huh? */
3430   for (decisionno = 0; decisionno < solv->decisionq.count; decisionno++)
3431     if (solv->decisionq.elements[decisionno] == p)
3432       break;
3433   if (decisionno == solv->decisionq.count)
3434     return;     /* huh? */
3435   if (decisionno < solv->decisioncnt_weak || decisionno >= solv->decisioncnt_orphan)
3436     return;     /* huh? */
3437
3438   /* 1) list all packages that recommend us */
3439   for (i = 1; i < pool->nsolvables; i++)
3440     {
3441       Id *recp, rec, pp2, p2;
3442       if (solv->decisionmap[i] < 0 || solv->decisionmap[i] >= level)
3443         continue;
3444       s = pool->solvables + i;
3445       if (!s->recommends)
3446         continue;
3447       if (!solv->addalreadyrecommended && s->repo == solv->installed)
3448         continue;
3449       recp = s->repo->idarraydata + s->recommends;
3450       while ((rec = *recp++) != 0)
3451         {
3452           int found = 0;
3453           FOR_PROVIDES(p2, pp2, rec)
3454             {
3455               if (p2 == p)
3456                 found = 1;
3457               else
3458                 {
3459                   /* if p2 is already installed, this recommends is ignored */
3460                   if (solv->decisionmap[p2] > 0 && solv->decisionmap[p2] < level)
3461                     break;
3462                 }
3463             }
3464           if (!p2 && found)
3465             {
3466               queue_push(whyq, SOLVER_REASON_RECOMMENDED);
3467               queue_push2(whyq, p2, rec);
3468             }
3469         }
3470     }
3471   /* 2) list all supplements */
3472   s = pool->solvables + p;
3473   if (s->supplements && level > 0)
3474     {
3475       Id *supp, sup, pp2, p2;
3476       /* this is a hack. to use solver_dep_fulfilled we temporarily clear
3477        * everything above our level in the decisionmap */
3478       for (i = decisionno; i < solv->decisionq.count; i++ )
3479         {
3480           p2 = solv->decisionq.elements[i];
3481           if (p2 > 0)
3482             solv->decisionmap[p2] = -solv->decisionmap[p2];
3483         }
3484       supp = s->repo->idarraydata + s->supplements;
3485       while ((sup = *supp++) != 0)
3486         if (solver_dep_fulfilled(solv, sup))
3487           {
3488             int found = 0;
3489             /* let's see if this is an easy supp */
3490             FOR_PROVIDES(p2, pp2, sup)
3491               {
3492                 if (!solv->addalreadyrecommended && solv->installed)
3493                   {
3494                     if (pool->solvables[p2].repo == solv->installed)
3495                       continue;
3496                   }
3497                 if (solv->decisionmap[p2] > 0 && solv->decisionmap[p2] < level)
3498                   {
3499                     queue_push(whyq, SOLVER_REASON_SUPPLEMENTED);
3500                     queue_push2(whyq, p2, sup);
3501                     found = 1;
3502                   }
3503               }
3504             if (!found)
3505               {
3506                 /* hard case, just note dependency with no package */
3507                 queue_push(whyq, SOLVER_REASON_SUPPLEMENTED);
3508                 queue_push2(whyq, 0, sup);
3509               }
3510           }
3511       for (i = decisionno; i < solv->decisionq.count; i++)
3512         {
3513           p2 = solv->decisionq.elements[i];
3514           if (p2 > 0)
3515             solv->decisionmap[p2] = -solv->decisionmap[p2];
3516         }
3517     }
3518 }