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