src/solver.c

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