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 "bitmap.h"
  22 #include "pool.h"
  23 #include "util.h"
  24 #include "evr.h"
  25 #include "policy.h"
  26 #include "solverdebug.h"
  27
  28 #define RULES_BLOCK 63
  29
  30 static void disableupdaterules(Solver *solv, Queue *job, int jobidx);
  31
  32 /********************************************************************
  33  *
  34  * dependency check helpers
  35  *
  36  */
  37
  38 /*-------------------------------------------------------------------
  39  * handle split provides
  40  */
  41
  42 int
  43 solver_splitprovides(Solver *solv, Id dep)
  44 {
  45   Pool *pool = solv->pool;
  46   Id p, pp;
  47   Reldep *rd;
  48   Solvable *s;
  49
  50   if (!solv->dosplitprovides || !solv->installed)
  51     return 0;
  52   if (!ISRELDEP(dep))
  53     return 0;
  54   rd = GETRELDEP(pool, dep);
  55   if (rd->flags != REL_WITH)
  56     return 0;
  57   FOR_PROVIDES(p, pp, dep)
  58     {
  59       s = pool->solvables + p;
  60       if (s->repo == solv->installed && s->name == rd->name)
  61         return 1;
  62     }
  63   return 0;
  64 }
  65
  66
  67 /*-------------------------------------------------------------------
  68  * solver_dep_installed
  69  */
  70
  71 int
  72 solver_dep_installed(Solver *solv, Id dep)
  73 {
  74 #if 0
  75   Pool *pool = solv->pool;
  76   Id p, pp;
  77
  78   if (ISRELDEP(dep))
  79     {
  80       Reldep *rd = GETRELDEP(pool, dep);
  81       if (rd->flags == REL_AND)
  82         {
  83           if (!solver_dep_installed(solv, rd->name))
  84             return 0;
  85           return solver_dep_installed(solv, rd->evr);
  86         }
  87       if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
  88         return solver_dep_installed(solv, rd->evr);
  89     }
  90   FOR_PROVIDES(p, pp, dep)
  91     {
  92       if (p == SYSTEMSOLVABLE || (solv->installed && pool->solvables[p].repo == solv->installed))
  93         return 1;
  94     }
  95 #endif
  96   return 0;
  97 }
  98
  99
 100 /*-------------------------------------------------------------------
 101  * Check if dependenc is possible
 102  *
 103  * this mirrors solver_dep_fulfilled
 104  * but uses map m instead of the decisionmap
 105  */
 106
 107 static inline int
 108 dep_possible(Solver *solv, Id dep, Map *m)
 109 {
 110   Pool *pool = solv->pool;
 111   Id p, pp;
 112
 113   if (ISRELDEP(dep))
 114     {
 115       Reldep *rd = GETRELDEP(pool, dep);
 116       if (rd->flags == REL_AND)
 117         {
 118           if (!dep_possible(solv, rd->name, m))
 119             return 0;
 120           return dep_possible(solv, rd->evr, m);
 121         }
 122       if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
 123         return solver_splitprovides(solv, rd->evr);
 124       if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
 125         return solver_dep_installed(solv, rd->evr);
 126     }
 127   FOR_PROVIDES(p, pp, dep)
 128     {
 129       if (MAPTST(m, p))
 130         return 1;
 131     }
 132   return 0;
 133 }
 134
 135 /********************************************************************
 136  *
 137  * Rule handling
 138  *
 139  * - unify rules, remove duplicates
 140  */
 141
 142 static Pool *unifyrules_sortcmp_data;
 143
 144 /*-------------------------------------------------------------------
 145  *
 146  * compare rules for unification sort
 147  *
 148  */
 149
 150 static int
 151 unifyrules_sortcmp(const void *ap, const void *bp)
 152 {
 153   Pool *pool = unifyrules_sortcmp_data;
 154   Rule *a = (Rule *)ap;
 155   Rule *b = (Rule *)bp;
 156   Id *ad, *bd;
 157   int x;
 158
 159   x = a->p - b->p;
 160   if (x)
 161     return x;                          /* p differs */
 162
 163   /* identical p */
 164   if (a->d == 0 && b->d == 0)
 165     return a->w2 - b->w2;              /* assertion: return w2 diff */
 166
 167   if (a->d == 0)                       /* a is assertion, b not */
 168     {
 169       x = a->w2 - pool->whatprovidesdata[b->d];
 170       return x ? x : -1;
 171     }
 172
 173   if (b->d == 0)                       /* b is assertion, a not */
 174     {
 175       x = pool->whatprovidesdata[a->d] - b->w2;
 176       return x ? x : 1;
 177     }
 178
 179   /* compare whatprovidesdata */
 180   ad = pool->whatprovidesdata + a->d;
 181   bd = pool->whatprovidesdata + b->d;
 182   while (*bd)
 183     if ((x = *ad++ - *bd++) != 0)
 184       return x;
 185   return *ad;
 186 }
 187
 188
 189 /*-------------------------------------------------------------------
 190  *
 191  * unify rules
 192  * go over all rules and remove duplicates
 193  */
 194
 195 static void
 196 unifyrules(Solver *solv)
 197 {
 198   Pool *pool = solv->pool;
 199   int i, j;
 200   Rule *ir, *jr;
 201
 202   if (solv->nrules <= 1)               /* nothing to unify */
 203     return;
 204
 205   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- unifyrules -----\n");
 206
 207   /* sort rules first */
 208   unifyrules_sortcmp_data = solv->pool;
 209   qsort(solv->rules + 1, solv->nrules - 1, sizeof(Rule), unifyrules_sortcmp);
 210
 211   /* prune rules
 212    * i = unpruned
 213    * j = pruned
 214    */
 215   jr = 0;
 216   for (i = j = 1, ir = solv->rules + i; i < solv->nrules; i++, ir++)
 217     {
 218       if (jr && !unifyrules_sortcmp(ir, jr))
 219         continue;                      /* prune! */
 220       jr = solv->rules + j++;          /* keep! */
 221       if (ir != jr)
 222         *jr = *ir;
 223     }
 224
 225   /* reduced count from nrules to j rules */
 226   POOL_DEBUG(SAT_DEBUG_STATS, "pruned rules from %d to %d\n", solv->nrules, j);
 227
 228   /* adapt rule buffer */
 229   solv->nrules = j;
 230   solv->rules = sat_extend_resize(solv->rules, solv->nrules, sizeof(Rule), RULES_BLOCK);
 231     /*
 232      * debug: statistics
 233      */
 234   IF_POOLDEBUG (SAT_DEBUG_STATS)
 235     {
 236       int binr = 0;
 237       int lits = 0;
 238       Id *dp;
 239       Rule *r;
 240
 241       for (i = 1; i < solv->nrules; i++)
 242         {
 243           r = solv->rules + i;
 244           if (r->d == 0)
 245             binr++;
 246           else
 247             {
 248               dp = solv->pool->whatprovidesdata + r->d;
 249               while (*dp++)
 250                 lits++;
 251             }
 252         }
 253       POOL_DEBUG(SAT_DEBUG_STATS, "  binary: %d\n", binr);
 254       POOL_DEBUG(SAT_DEBUG_STATS, "  normal: %d, %d literals\n", solv->nrules - 1 - binr, lits);
 255     }
 256   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- unifyrules end -----\n");
 257 }
 258
 259 #if 0
 260
 261 /*
 262  * hash rule
 263  */
 264
 265 static Hashval
 266 hashrule(Solver *solv, Id p, Id d, int n)
 267 {
 268   unsigned int x = (unsigned int)p;
 269   int *dp;
 270
 271   if (n <= 1)
 272     return (x * 37) ^ (unsigned int)d;
 273   dp = solv->pool->whatprovidesdata + d;
 274   while (*dp)
 275     x = (x * 37) ^ (unsigned int)*dp++;
 276   return x;
 277 }
 278 #endif
 279
 280
 281 /*-------------------------------------------------------------------
 282  *
 283  */
 284
 285 /*
 286  * add rule
 287  *  p = direct literal; always < 0 for installed rpm rules
 288  *  d, if < 0 direct literal, if > 0 offset into whatprovides, if == 0 rule is assertion (look at p only)
 289  *
 290  *
 291  * A requires b, b provided by B1,B2,B3 => (-A|B1|B2|B3)
 292  *
 293  * p < 0 : pkg id of A
 294  * d > 0 : Offset in whatprovidesdata (list of providers of b)
 295  *
 296  * A conflicts b, b provided by B1,B2,B3 => (-A|-B1), (-A|-B2), (-A|-B3)
 297  * p < 0 : pkg id of A
 298  * d < 0 : Id of solvable (e.g. B1)
 299  *
 300  * d == 0: unary rule, assertion => (A) or (-A)
 301  *
 302  *   Install:    p > 0, d = 0   (A)             user requested install
 303  *   Remove:     p < 0, d = 0   (-A)            user requested remove (also: uninstallable)
 304  *   Requires:   p < 0, d > 0   (-A|B1|B2|...)  d: <list of providers for requirement of p>
 305  *   Updates:    p > 0, d > 0   (A|B1|B2|...)   d: <list of updates for solvable p>
 306  *   Conflicts:  p < 0, d < 0   (-A|-B)         either p (conflict issuer) or d (conflict provider) (binary rule)
 307  *                                              also used for obsoletes
 308  *   ?:          p > 0, d < 0   (A|-B)
 309  *   No-op ?:    p = 0, d = 0   (null)          (used as policy rule placeholder)
 310  *
 311  *   resulting watches:
 312  *   ------------------
 313  *   Direct assertion (no watch needed)( if d <0 ) --> d = 0, w1 = p, w2 = 0
 314  *   Binary rule: p = first literal, d = 0, w2 = second literal, w1 = p
 315  *   every other : w1 = p, w2 = whatprovidesdata[d];
 316  *   Disabled rule: w1 = 0
 317  *
 318  *   always returns a rule for non-rpm rules
 319  */
 320
 321 static Rule *
 322 addrule(Solver *solv, Id p, Id d)
 323 {
 324   Pool *pool = solv->pool;
 325   Rule *r = 0;
 326   Id *dp = 0;
 327
 328   int n = 0;                           /* number of literals in rule - 1
 329                                           0 = direct assertion (single literal)
 330                                           1 = binary rule
 331                                           >1 =
 332                                         */
 333
 334   /* it often happenes that requires lead to adding the same rpm rule
 335    * multiple times, so we prune those duplicates right away to make
 336    * the work for unifyrules a bit easier */
 337
 338   if (solv->nrules                      /* we already have rules */
 339       && !solv->rpmrules_end)           /* but are not done with rpm rules */
 340     {
 341       r = solv->rules + solv->nrules - 1;   /* get the last added rule */
 342       if (r->p == p && r->d == d && d != 0)   /* identical and not user requested */
 343         return r;
 344     }
 345
 346     /*
 347      * compute number of literals (n) in rule
 348      */
 349
 350   if (d < 0)
 351     {
 352       /* always a binary rule */
 353       if (p == d)
 354         return 0;                      /* ignore self conflict */
 355       n = 1;
 356     }
 357   else if (d > 0)
 358     {
 359       for (dp = pool->whatprovidesdata + d; *dp; dp++, n++)
 360         if (*dp == -p)
 361           return 0;                     /* rule is self-fulfilling */
 362
 363       if (n == 1)   /* have single provider */
 364         d = dp[-1];                     /* take single literal */
 365     }
 366
 367   if (n == 1 && p > d && !solv->rpmrules_end)
 368     {
 369       /* smallest literal first so we can find dups */
 370       n = p; p = d; d = n;             /* p <-> d */
 371       n = 1;                           /* re-set n, was used as temp var */
 372     }
 373
 374     /*
 375      * check for duplicate
 376      */
 377
 378   /* check if the last added rule (r) is exactly the same as what we're looking for. */
 379   if (r && n == 1 && !r->d && r->p == p && r->w2 == d)
 380     return r;  /* binary rule */
 381
 382     /* have n-ary rule with same first literal, check other literals */
 383   if (r && n > 1 && r->d && r->p == p)
 384     {
 385       /* Rule where d is an offset in whatprovidesdata */
 386       Id *dp2;
 387       if (d == r->d)
 388         return r;
 389       dp2 = pool->whatprovidesdata + r->d;
 390       for (dp = pool->whatprovidesdata + d; *dp; dp++, dp2++)
 391         if (*dp != *dp2)
 392           break;
 393       if (*dp == *dp2)
 394         return r;
 395    }
 396
 397     /*
 398      * allocate new rule
 399      */
 400
 401   /* extend rule buffer */
 402   solv->rules = sat_extend(solv->rules, solv->nrules, 1, sizeof(Rule), RULES_BLOCK);
 403   r = solv->rules + solv->nrules++;    /* point to rule space */
 404
 405     /*
 406      * r = new rule
 407      */
 408
 409   r->p = p;
 410   if (n == 0)
 411     {
 412       /* direct assertion, no watch needed */
 413       r->d = 0;
 414       r->w1 = p;
 415       r->w2 = 0;
 416     }
 417   else if (n == 1)
 418     {
 419       /* binary rule */
 420       r->d = 0;
 421       r->w1 = p;
 422       r->w2 = d;
 423     }
 424   else
 425     {
 426       r->d = d;
 427       r->w1 = p;
 428       r->w2 = pool->whatprovidesdata[d];
 429     }
 430   r->n1 = 0;
 431   r->n2 = 0;
 432
 433   IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION)
 434     {
 435       POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "  Add rule: ");
 436       solver_printrule(solv, SAT_DEBUG_RULE_CREATION, r);
 437     }
 438
 439   return r;
 440 }
 441
 442 /*-------------------------------------------------------------------
 443  * disable rule
 444  */
 445
 446 static inline void
 447 disablerule(Solver *solv, Rule *r)
 448 {
 449   if (r->d >= 0)
 450     r->d = -r->d - 1;
 451 }
 452
 453 /*-------------------------------------------------------------------
 454  * enable rule
 455  */
 456
 457 static inline void
 458 enablerule(Solver *solv, Rule *r)
 459 {
 460   if (r->d < 0)
 461     r->d = -r->d - 1;
 462 }
 463
 464
 465 /**********************************************************************************/
 466
 467 /* a problem is an item on the solver's problem list. It can either be >0, in that
 468  * case it is a update rule, or it can be <0, which makes it refer to a job
 469  * consisting of multiple job rules.
 470  */
 471
 472 static void
 473 disableproblem(Solver *solv, Id v)
 474 {
 475   Rule *r;
 476   int i;
 477   Id *jp;
 478
 479   if (v > 0)
 480     {
 481       if (v >= solv->infarchrules && v < solv->infarchrules_end)
 482         {
 483           Pool *pool = solv->pool;
 484           Id name = pool->solvables[-solv->rules[v].p].name;
 485           while (v > solv->infarchrules && pool->solvables[-solv->rules[v - 1].p].name == name)
 486             v--;
 487           for (; v < solv->infarchrules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
 488             disablerule(solv, solv->rules + v);
 489           return;
 490         }
 491       if (v >= solv->duprules && v < solv->duprules_end)
 492         {
 493           Pool *pool = solv->pool;
 494           Id name = pool->solvables[-solv->rules[v].p].name;
 495           while (v > solv->duprules && pool->solvables[-solv->rules[v - 1].p].name == name)
 496             v--;
 497           for (; v < solv->duprules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
 498             disablerule(solv, solv->rules + v);
 499           return;
 500         }
 501       disablerule(solv, solv->rules + v);
 502       return;
 503     }
 504   v = -(v + 1);
 505   jp = solv->ruletojob.elements;
 506   for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++, jp++)
 507     if (*jp == v)
 508       disablerule(solv, r);
 509 }
 510
 511 /*-------------------------------------------------------------------
 512  * enableproblem
 513  */
 514
 515 static void
 516 enableproblem(Solver *solv, Id v)
 517 {
 518   Rule *r;
 519   int i;
 520   Id *jp;
 521
 522   if (v > 0)
 523     {
 524       if (v >= solv->infarchrules && v < solv->infarchrules_end)
 525         {
 526           Pool *pool = solv->pool;
 527           Id name = pool->solvables[-solv->rules[v].p].name;
 528           while (v > solv->infarchrules && pool->solvables[-solv->rules[v - 1].p].name == name)
 529             v--;
 530           for (; v < solv->infarchrules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
 531             enablerule(solv, solv->rules + v);
 532           return;
 533         }
 534       if (v >= solv->duprules && v < solv->duprules_end)
 535         {
 536           Pool *pool = solv->pool;
 537           Id name = pool->solvables[-solv->rules[v].p].name;
 538           while (v > solv->duprules && pool->solvables[-solv->rules[v - 1].p].name == name)
 539             v--;
 540           for (; v < solv->duprules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
 541             enablerule(solv, solv->rules + v);
 542           return;
 543         }
 544       if (v >= solv->featurerules && v < solv->featurerules_end)
 545         {
 546           /* do not enable feature rule if update rule is enabled */
 547           r = solv->rules + (v - solv->featurerules + solv->updaterules);
 548           if (r->d >= 0)
 549             return;
 550         }
 551       enablerule(solv, solv->rules + v);
 552       if (v >= solv->updaterules && v < solv->updaterules_end)
 553         {
 554           /* disable feature rule when enabling update rule */
 555           r = solv->rules + (v - solv->updaterules + solv->featurerules);
 556           if (r->p)
 557             disablerule(solv, r);
 558         }
 559       return;
 560     }
 561   v = -(v + 1);
 562   jp = solv->ruletojob.elements;
 563   for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++, jp++)
 564     if (*jp == v)
 565       enablerule(solv, r);
 566 }
 567
 568
 569 /************************************************************************/
 570
 571 /*
 572  * make assertion rules into decisions
 573  *
 574  * go through update and job rules and add direct assertions
 575  * to the decisionqueue. If we find a conflict, disable rules and
 576  * add them to problem queue.
 577  */
 578
 579 static void
 580 makeruledecisions(Solver *solv)
 581 {
 582   Pool *pool = solv->pool;
 583   int i, ri, ii;
 584   Rule *r, *rr;
 585   Id v, vv;
 586   int decisionstart;
 587
 588   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- makeruledecisions ; size decisionq: %d -----\n",solv->decisionq.count);
 589
 590   decisionstart = solv->decisionq.count;
 591   for (ii = 0; ii < solv->ruleassertions.count; ii++)
 592     {
 593       ri = solv->ruleassertions.elements[ii];
 594       r = solv->rules + ri;
 595
 596       if (r->d < 0 || !r->p || r->w2)   /* disabled, dummy or no assertion */
 597         continue;
 598       /* do weak rules in phase 2 */
 599       if (ri < solv->learntrules && MAPTST(&solv->weakrulemap, ri))
 600         continue;
 601
 602       v = r->p;
 603       vv = v > 0 ? v : -v;
 604
 605       if (!solv->decisionmap[vv])          /* if not yet decided */
 606         {
 607             /*
 608              * decide !
 609              */
 610           queue_push(&solv->decisionq, v);
 611           queue_push(&solv->decisionq_why, r - solv->rules);
 612           solv->decisionmap[vv] = v > 0 ? 1 : -1;
 613           IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
 614             {
 615               Solvable *s = solv->pool->solvables + vv;
 616               if (v < 0)
 617                 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "conflicting %s (assertion)\n", solvable2str(solv->pool, s));
 618               else
 619                 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "installing  %s (assertion)\n", solvable2str(solv->pool, s));
 620             }
 621           continue;
 622         }
 623         /*
 624          * check previous decision: is it sane ?
 625          */
 626
 627       if (v > 0 && solv->decisionmap[vv] > 0)    /* ok to install */
 628         continue;
 629       if (v < 0 && solv->decisionmap[vv] < 0)    /* ok to remove */
 630         continue;
 631
 632         /*
 633          * found a conflict!
 634          *
 635          * The rule (r) we're currently processing says something
 636          * different (v = r->p) than a previous decision (decisionmap[abs(v)])
 637          * on this literal
 638          */
 639
 640       if (ri >= solv->learntrules)
 641         {
 642           /* conflict with a learnt rule */
 643           /* can happen when packages cannot be installed for
 644            * multiple reasons. */
 645           /* we disable the learnt rule in this case */
 646           disablerule(solv, r);
 647           continue;
 648         }
 649
 650         /*
 651          * find the decision which is the "opposite" of the rule
 652          */
 653
 654       for (i = 0; i < solv->decisionq.count; i++)
 655         if (solv->decisionq.elements[i] == -v)
 656           break;
 657       assert(i < solv->decisionq.count);         /* assert that we found it */
 658
 659         /*
 660          * conflict with system solvable ?
 661          */
 662
 663       if (v == -SYSTEMSOLVABLE) {
 664         /* conflict with system solvable */
 665         queue_push(&solv->problems, solv->learnt_pool.count);
 666         queue_push(&solv->learnt_pool, ri);
 667         queue_push(&solv->learnt_pool, 0);
 668         POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "conflict with system solvable, disabling rule #%d\n", ri);
 669         if  (ri >= solv->jobrules && ri < solv->jobrules_end)
 670           v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
 671         else
 672           v = ri;
 673         queue_push(&solv->problems, v);
 674         queue_push(&solv->problems, 0);
 675         disableproblem(solv, v);
 676         continue;
 677       }
 678
 679       assert(solv->decisionq_why.elements[i] > 0);
 680
 681         /*
 682          * conflict with an rpm rule ?
 683          */
 684
 685       if (solv->decisionq_why.elements[i] < solv->rpmrules_end)
 686         {
 687           /* conflict with rpm rule assertion */
 688           queue_push(&solv->problems, solv->learnt_pool.count);
 689           queue_push(&solv->learnt_pool, ri);
 690           queue_push(&solv->learnt_pool, solv->decisionq_why.elements[i]);
 691           queue_push(&solv->learnt_pool, 0);
 692           assert(v > 0 || v == -SYSTEMSOLVABLE);
 693           POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "conflict with rpm rule, disabling rule #%d\n", ri);
 694           if (ri >= solv->jobrules && ri < solv->jobrules_end)
 695             v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
 696           else
 697             v = ri;
 698           queue_push(&solv->problems, v);
 699           queue_push(&solv->problems, 0);
 700           disableproblem(solv, v);
 701           continue;
 702         }
 703
 704         /*
 705          * conflict with another job or update/feature rule
 706          */
 707
 708       /* record proof */
 709       queue_push(&solv->problems, solv->learnt_pool.count);
 710       queue_push(&solv->learnt_pool, ri);
 711       queue_push(&solv->learnt_pool, solv->decisionq_why.elements[i]);
 712       queue_push(&solv->learnt_pool, 0);
 713
 714       POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "conflicting update/job assertions over literal %d\n", vv);
 715
 716         /*
 717          * push all of our rules (can only be feature or job rules)
 718          * asserting this literal on the problem stack
 719          */
 720
 721       for (i = solv->featurerules, rr = solv->rules + i; i < solv->learntrules; i++, rr++)
 722         {
 723           if (rr->d < 0                          /* disabled */
 724               || rr->w2)                         /*  or no assertion */
 725             continue;
 726           if (rr->p != vv                        /* not affecting the literal */
 727               && rr->p != -vv)
 728             continue;
 729           if (MAPTST(&solv->weakrulemap, i))     /* weak: silently ignore */
 730             continue;
 731
 732           POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, " - disabling rule #%d\n", i);
 733
 734           solver_printruleclass(solv, SAT_DEBUG_UNSOLVABLE, solv->rules + i);
 735
 736           v = i;
 737             /* is is a job rule ? */
 738           if (i >= solv->jobrules && i < solv->jobrules_end)
 739             v = -(solv->ruletojob.elements[i - solv->jobrules] + 1);
 740
 741           queue_push(&solv->problems, v);
 742           disableproblem(solv, v);
 743         }
 744       queue_push(&solv->problems, 0);
 745
 746        /*
 747         * start over
 748         * (back up from decisions)
 749         */
 750       while (solv->decisionq.count > decisionstart)
 751         {
 752           v = solv->decisionq.elements[--solv->decisionq.count];
 753           --solv->decisionq_why.count;
 754           vv = v > 0 ? v : -v;
 755           solv->decisionmap[vv] = 0;
 756         }
 757       ii = -1; /* restarts loop at 0 */
 758     }
 759
 760     /*
 761      * phase 2: now do the weak assertions
 762      */
 763   for (ii = 0; ii < solv->ruleassertions.count; ii++)
 764     {
 765       ri = solv->ruleassertions.elements[ii];
 766       r = solv->rules + ri;
 767       if (r->d < 0 || r->w2)                     /* disabled or no assertion */
 768         continue;
 769       if (!MAPTST(&solv->weakrulemap, ri))       /* skip non-weak */
 770         continue;
 771       v = r->p;
 772       vv = v > 0 ? v : -v;
 773         /*
 774          * decide !
 775          * (if not yet decided)
 776          */
 777       if (!solv->decisionmap[vv])
 778         {
 779           queue_push(&solv->decisionq, v);
 780           queue_push(&solv->decisionq_why, r - solv->rules);
 781           solv->decisionmap[vv] = v > 0 ? 1 : -1;
 782           IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
 783             {
 784               Solvable *s = solv->pool->solvables + vv;
 785               if (v < 0)
 786                 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "conflicting %s (weak assertion)\n", solvable2str(solv->pool, s));
 787               else
 788                 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "installing  %s (weak assertion)\n", solvable2str(solv->pool, s));
 789             }
 790           continue;
 791         }
 792         /*
 793          * previously decided, sane ?
 794          */
 795       if (v > 0 && solv->decisionmap[vv] > 0)
 796         continue;
 797       if (v < 0 && solv->decisionmap[vv] < 0)
 798         continue;
 799
 800       POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "assertion conflict, but I am weak, disabling ");
 801       solver_printrule(solv, SAT_DEBUG_UNSOLVABLE, r);
 802
 803       if (ri >= solv->jobrules && ri < solv->jobrules_end)
 804         v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
 805       else
 806         v = ri;
 807       disableproblem(solv, v);
 808       if (v < 0)
 809         disableupdaterules(solv, solv->job, -(v + 1));
 810     }
 811
 812   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- makeruledecisions end; size decisionq: %d -----\n",solv->decisionq.count);
 813 }
 814
 815
 816 /*-------------------------------------------------------------------
 817  * enable/disable learnt rules
 818  *
 819  * we have enabled or disabled some of our rules. We now reenable all
 820  * of our learnt rules except the ones that were learnt from rules that
 821  * are now disabled.
 822  */
 823 static void
 824 enabledisablelearntrules(Solver *solv)
 825 {
 826   Pool *pool = solv->pool;
 827   Rule *r;
 828   Id why, *whyp;
 829   int i;
 830
 831   POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "enabledisablelearntrules called\n");
 832   for (i = solv->learntrules, r = solv->rules + i; i < solv->nrules; i++, r++)
 833     {
 834       whyp = solv->learnt_pool.elements + solv->learnt_why.elements[i - solv->learntrules];
 835       while ((why = *whyp++) != 0)
 836         {
 837           assert(why > 0 && why < i);
 838           if (solv->rules[why].d < 0)
 839             break;
 840         }
 841       /* why != 0: we found a disabled rule, disable the learnt rule */
 842       if (why && r->d >= 0)
 843         {
 844           IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
 845             {
 846               POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "disabling ");
 847               solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
 848             }
 849           disablerule(solv, r);
 850         }
 851       else if (!why && r->d < 0)
 852         {
 853           IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
 854             {
 855               POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "re-enabling ");
 856               solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
 857             }
 858           enablerule(solv, r);
 859         }
 860     }
 861 }
 862
 863
 864 /*-------------------------------------------------------------------
 865  * enable weak rules
 866  *
 867  * Enable all rules, except learnt rules, which are
 868  * - disabled and weak (set in weakrulemap)
 869  *
 870  */
 871
 872 static void
 873 enableweakrules(Solver *solv)
 874 {
 875   int i;
 876   Rule *r;
 877
 878   for (i = 1, r = solv->rules + i; i < solv->learntrules; i++, r++)
 879     {
 880       if (r->d >= 0) /* already enabled? */
 881         continue;
 882       if (!MAPTST(&solv->weakrulemap, i))
 883         continue;
 884       enablerule(solv, r);
 885     }
 886 }
 887
 888
 889 /* FIXME: bad code ahead, replace as soon as possible */
 890 /* FIXME: maybe also look at SOLVER_INSTALL|SOLVABLE_ONE_OF */
 891
 892 /*-------------------------------------------------------------------
 893  * disable update rules depending on enabled job
 894  * if jobidx is set we just disabled this job, so we may want
 895  * to re-enable some rules
 896  * otherwise we disable all update rules that conflict with some job.
 897  */
 898
 899 static void
 900 disableupdaterules(Solver *solv, Queue *job, int jobidx)
 901 {
 902   Pool *pool = solv->pool;
 903   int i, j;
 904   Id how, select, what, p, pp;
 905   Solvable *s;
 906   Repo *installed;
 907   Rule *r;
 908   Id lastjob = -1;
 909   Map nolockrules;
 910
 911   installed = solv->installed;
 912
 913   if (jobidx != -1)
 914     {
 915       how = job->elements[jobidx];
 916       select = how & SOLVER_SELECTMASK;
 917       switch (how & SOLVER_JOBMASK)
 918         {
 919         case SOLVER_ERASE:
 920           break;
 921         case SOLVER_INSTALL:
 922           if (select != SOLVER_SOLVABLE)
 923             return;
 924           break;
 925         default:
 926           return;
 927         }
 928     }
 929   /* go through all enabled job rules */
 930   map_init(&nolockrules, pool->nsolvables);
 931   MAPZERO(&solv->noupdate);
 932   for (i = solv->jobrules; i < solv->jobrules_end; i++)
 933     {
 934       r = solv->rules + i;
 935       if (r->d < 0)     /* disabled? */
 936         continue;
 937       j = solv->ruletojob.elements[i - solv->jobrules];
 938       if (j == lastjob)
 939         continue;
 940       lastjob = j;
 941       how = job->elements[j];
 942       what = job->elements[j + 1];
 943       select = how & SOLVER_SELECTMASK;
 944       switch (how & SOLVER_JOBMASK)
 945         {
 946         case SOLVER_INSTALL:
 947           if (select != SOLVER_SOLVABLE)
 948             break;
 949           s = pool->solvables + what;
 950           FOR_PROVIDES(p, pp, s->name)
 951             {
 952               Solvable *ps = pool->solvables + p;
 953               if (ps->name == s->name)
 954                 MAPSET(&nolockrules, p);
 955             }
 956           if (!installed)
 957             break;
 958           if (solv->noobsoletes.size && MAPTST(&solv->noobsoletes, what))
 959             break;
 960           if (s->repo == installed)
 961             {
 962               MAPSET(&solv->noupdate, what - installed->start);
 963               break;
 964             }
 965           if (s->obsoletes)
 966             {
 967               Id obs, *obsp;
 968               obsp = s->repo->idarraydata + s->obsoletes;
 969               while ((obs = *obsp++) != 0)
 970                 FOR_PROVIDES(p, pp, obs)
 971                   {
 972                     Solvable *ps = pool->solvables + p;
 973                     if (ps->repo != installed)
 974                       continue;
 975                     if (!solv->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
 976                       continue;
 977                     MAPSET(&solv->noupdate, p - installed->start);
 978                   }
 979             }
 980           FOR_PROVIDES(p, pp, s->name)
 981             {
 982               Solvable *ps = pool->solvables + p;
 983               if (ps->repo != installed)
 984                 continue;
 985               if (!solv->implicitobsoleteusesprovides && ps->name != s->name)
 986                 continue;
 987               MAPSET(&solv->noupdate, p - installed->start);
 988             }
 989           break;
 990         case SOLVER_ERASE:
 991           if (!installed)
 992             break;
 993           FOR_JOB_SELECT(p, pp, select, what)
 994             if (pool->solvables[p].repo == installed)
 995               MAPSET(&solv->noupdate, p - installed->start);
 996           break;
 997         default:
 998           break;
 999         }
1000     }
1001
1002   /* fixup update rule status */
1003   if (jobidx != -1)
1004     {
1005       /* we just disabled job #jobidx. enable all update rules
1006        * that aren't disabled by the remaining job rules */
1007       how = job->elements[jobidx];
1008       what = job->elements[jobidx + 1];
1009       select = how & SOLVER_SELECTMASK;
1010       if ((how & SOLVER_JOBMASK) == SOLVER_INSTALL && select == SOLVER_SOLVABLE)
1011         {
1012           /* check if we need to enable some lock rule */
1013           for (i = solv->infarchrules, r = solv->rules + i; i < solv->infarchrules_end; i++, r++)
1014             {
1015               if (r->p != -what || r->d >= 0 || !MAPTST(&nolockrules, -r->p))
1016                 continue;
1017               enablerule(solv, r);
1018               IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
1019                 {
1020                   POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
1021                   solver_printrule(solv, SAT_DEBUG_SOLUTIONS, r);
1022                 }
1023             }
1024           for (i = solv->duprules, r = solv->rules + i; i < solv->duprules_end; i++, r++)
1025             {
1026               if (r->p != -what || r->d >= 0 || !MAPTST(&nolockrules, -r->p))
1027                 continue;
1028               enablerule(solv, r);
1029               IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
1030                 {
1031                   POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
1032                   solver_printrule(solv, SAT_DEBUG_SOLUTIONS, r);
1033                 }
1034             }
1035         }
1036       map_free(&nolockrules);
1037       if (!installed)
1038         return;
1039       switch (how & SOLVER_JOBMASK)
1040         {
1041         case SOLVER_INSTALL:
1042           if (select != SOLVER_SOLVABLE)
1043             break;
1044           s = pool->solvables + what;
1045           if (s->repo == installed)
1046             {
1047               if (MAPTST(&solv->noupdate, what - installed->start))
1048                 break;
1049               r = solv->rules + solv->updaterules + (what - installed->start);
1050               if (r->d >= 0)
1051                 break;
1052               enablerule(solv, r);
1053               IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
1054                 {
1055                   POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
1056                   solver_printrule(solv, SAT_DEBUG_SOLUTIONS, r);
1057                 }
1058               break;
1059             }
1060           if (s->obsoletes)
1061             {
1062               Id obs, *obsp;
1063               obsp = s->repo->idarraydata + s->obsoletes;
1064               while ((obs = *obsp++) != 0)
1065                 FOR_PROVIDES(p, pp, obs)
1066                   {
1067                     if (pool->solvables[p].repo != installed)
1068                       continue;
1069                     if (!solv->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p, obs))
1070                       continue;
1071                     if (MAPTST(&solv->noupdate, p - installed->start))
1072                       continue;
1073                     r = solv->rules + solv->updaterules + (p - installed->start);
1074                     if (r->d >= 0)
1075                       continue;
1076                     enablerule(solv, r);
1077                     IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
1078                       {
1079                         POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
1080                         solver_printrule(solv, SAT_DEBUG_SOLUTIONS, r);
1081                       }
1082                   }
1083             }
1084           FOR_PROVIDES(p, pp, s->name)
1085             {
1086               if (!solv->implicitobsoleteusesprovides && pool->solvables[p].name != s->name)
1087                 continue;
1088               if (pool->solvables[p].repo != installed)
1089                 continue;
1090               if (MAPTST(&solv->noupdate, p - installed->start))
1091                 continue;
1092               r = solv->rules + solv->updaterules + (p - installed->start);
1093               if (r->d >= 0)
1094                 continue;
1095               enablerule(solv, r);
1096               IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
1097                 {
1098                   POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
1099                   solver_printrule(solv, SAT_DEBUG_SOLUTIONS, r);
1100                 }
1101             }
1102           break;
1103         case SOLVER_ERASE:
1104           FOR_JOB_SELECT(p, pp, select, what)
1105             {
1106               if (pool->solvables[p].repo != installed)
1107                 continue;
1108               if (MAPTST(&solv->noupdate, p - installed->start))
1109                 continue;
1110               r = solv->rules + solv->updaterules + (p - installed->start);
1111               if (r->d >= 0)
1112                 continue;
1113               enablerule(solv, r);
1114               IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
1115                 {
1116                   POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
1117                   solver_printrule(solv, SAT_DEBUG_SOLUTIONS, r);
1118                 }
1119             }
1120           break;
1121         default:
1122           break;
1123         }
1124       return;
1125     }
1126
1127   for (i = solv->infarchrules, r = solv->rules + i; i < solv->infarchrules_end; i++, r++)
1128     {
1129       if (r->p < 0 && r->d >= 0 && MAPTST(&nolockrules, -r->p))
1130         disablerule(solv, r);   /* was enabled, need to disable */
1131     }
1132   for (i = solv->duprules, r = solv->rules + i; i < solv->duprules_end; i++, r++)
1133     {
1134       if (r->p < 0 && r->d >= 0 && MAPTST(&nolockrules, -r->p))
1135         disablerule(solv, r);   /* was enabled, need to disable */
1136     }
1137   map_free(&nolockrules);
1138   if (installed)
1139     {
1140       for (i = 0; i < installed->nsolvables; i++)
1141         {
1142           r = solv->rules + solv->updaterules + i;
1143           if (r->d >= 0 && MAPTST(&solv->noupdate, i))
1144             disablerule(solv, r);       /* was enabled, need to disable */
1145           r = solv->rules + solv->featurerules + i;
1146           if (r->d >= 0 && MAPTST(&solv->noupdate, i))
1147             disablerule(solv, r);       /* was enabled, need to disable */
1148         }
1149     }
1150 }
1151
1152
1153 /*
1154  *  special multiversion patch conflict handling:
1155  *  a patch conflict is also satisfied, if some other
1156  *  version with the same name/arch that doesn't conflict
1157  *  get's installed. The generated rule is thus:
1158  *  -patch|-cpack|opack1|opack2|...
1159  */
1160 Id
1161 makemultiversionconflict(Solver *solv, Id n, Id con)
1162 {
1163   Pool *pool = solv->pool;
1164   Solvable *s, *sn;
1165   Queue q;
1166   Id p, pp, qbuf[64];
1167
1168   sn = pool->solvables + n;
1169   queue_init_buffer(&q, qbuf, sizeof(qbuf)/sizeof(*qbuf));
1170   queue_push(&q, -n);
1171   FOR_PROVIDES(p, pp, sn->name)
1172     {
1173       s = pool->solvables + p;
1174       if (s->name != sn->name || s->arch != sn->arch)
1175         continue;
1176       if (!MAPTST(&solv->noobsoletes, p))
1177         continue;
1178       if (pool_match_nevr(pool, pool->solvables + p, con))
1179         continue;
1180       /* here we have a multiversion solvable that doesn't conflict */
1181       /* thus we're not in conflict if it is installed */
1182       queue_push(&q, p);
1183     }
1184   if (q.count == 1)
1185     return -n;  /* no other package found, generate normal conflict */
1186   return pool_queuetowhatprovides(pool, &q);
1187 }
1188
1189
1190 /*-------------------------------------------------------------------
1191  *
1192  * add (install) rules for solvable
1193  *
1194  * s: Solvable for which to add rules
1195  * m: m[s] = 1 for solvables which have rules, prevent rule duplication
1196  *
1197  * Algorithm: 'visit all nodes of a graph'. The graph nodes are
1198  *  solvables, the edges their dependencies.
1199  *  Starting from an installed solvable, this will create all rules
1200  *  representing the graph created by the solvables dependencies.
1201  *
1202  * for unfulfilled requirements, conflicts, obsoletes,....
1203  * add a negative assertion for solvables that are not installable
1204  *
1205  * It will also create rules for all solvables referenced by 's'
1206  *  i.e. descend to all providers of requirements of 's'
1207  *
1208  */
1209
1210 static void
1211 addrpmrulesforsolvable(Solver *solv, Solvable *s, Map *m)
1212 {
1213   Pool *pool = solv->pool;
1214   Repo *installed = solv->installed;
1215
1216   /* 'work' queue. keeps Ids of solvables we still have to work on.
1217      And buffer for it. */
1218   Queue workq;
1219   Id workqbuf[64];
1220
1221   int i;
1222     /* if to add rules for broken deps ('rpm -V' functionality)
1223      * 0 = yes, 1 = no
1224      */
1225   int dontfix;
1226     /* Id var and pointer for each dependency
1227      * (not used in parallel)
1228      */
1229   Id req, *reqp;
1230   Id con, *conp;
1231   Id obs, *obsp;
1232   Id rec, *recp;
1233   Id sug, *sugp;
1234     /* var and ptr for loops */
1235   Id p, pp;
1236     /* ptr to 'whatprovides' */
1237   Id *dp;
1238     /* Id for current solvable 's' */
1239   Id n;
1240
1241   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforsolvable -----\n");
1242
1243   queue_init_buffer(&workq, workqbuf, sizeof(workqbuf)/sizeof(*workqbuf));
1244   queue_push(&workq, s - pool->solvables);      /* push solvable Id to work queue */
1245
1246   /* loop until there's no more work left */
1247   while (workq.count)
1248     {
1249       /*
1250        * n: Id of solvable
1251        * s: Pointer to solvable
1252        */
1253
1254       n = queue_shift(&workq);             /* 'pop' next solvable to work on from queue */
1255       if (MAPTST(m, n))                    /* continue if already visited */
1256         continue;
1257
1258       MAPSET(m, n);                        /* mark as visited */
1259       s = pool->solvables + n;             /* s = Solvable in question */
1260
1261       dontfix = 0;
1262       if (installed                        /* Installed system available */
1263           && !solv->fixsystem              /* NOT repair errors in rpm dependency graph */
1264           && s->repo == installed)         /* solvable is installed? */
1265       {
1266         dontfix = 1;                       /* dont care about broken rpm deps */
1267       }
1268
1269       if (!dontfix
1270           && s->arch != ARCH_SRC
1271           && s->arch != ARCH_NOSRC
1272           && !pool_installable(pool, s))
1273         {
1274           POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "package %s [%d] is not installable\n", solvable2str(pool, s), (Id)(s - pool->solvables));
1275           addrule(solv, -n, 0);            /* uninstallable */
1276         }
1277
1278       /* yet another SUSE hack, sigh */
1279       if (pool->nscallback && !strncmp("product:", id2str(pool, s->name), 8))
1280         {
1281           Id buddy = pool->nscallback(pool, pool->nscallbackdata, NAMESPACE_PRODUCTBUDDY, n);
1282           if (buddy > 0 && buddy != SYSTEMSOLVABLE && buddy != n && buddy < pool->nsolvables)
1283             {
1284               addrule(solv, n, -buddy);
1285               addrule(solv, buddy, -n);
1286             }
1287         }
1288
1289       /*-----------------------------------------
1290        * check requires of s
1291        */
1292
1293       if (s->requires)
1294         {
1295           reqp = s->repo->idarraydata + s->requires;
1296           while ((req = *reqp++) != 0)            /* go through all requires */
1297             {
1298               if (req == SOLVABLE_PREREQMARKER)   /* skip the marker */
1299                 continue;
1300
1301               /* find list of solvables providing 'req' */
1302               dp = pool->whatprovidesdata + pool_whatprovides(pool, req);
1303
1304               if (*dp == SYSTEMSOLVABLE)          /* always installed */
1305                 continue;
1306
1307               if (dontfix)
1308                 {
1309                   /* the strategy here is to not insist on dependencies
1310                    * that are already broken. so if we find one provider
1311                    * that was already installed, we know that the
1312                    * dependency was not broken before so we enforce it */
1313
1314                   /* check if any of the providers for 'req' is installed */
1315                   for (i = 0; (p = dp[i]) != 0; i++)
1316                     {
1317                       if (pool->solvables[p].repo == installed)
1318                         break;          /* provider was installed */
1319                     }
1320                   /* didn't find an installed provider: previously broken dependency */
1321                   if (!p)
1322                     {
1323                       POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "ignoring broken requires %s of installed package %s\n", dep2str(pool, req), solvable2str(pool, s));
1324                       continue;
1325                     }
1326                 }
1327
1328               if (!*dp)
1329                 {
1330                   /* nothing provides req! */
1331                   POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "package %s [%d] is not installable (%s)\n", solvable2str(pool, s), (Id)(s - pool->solvables), dep2str(pool, req));
1332                   addrule(solv, -n, 0); /* mark requestor as uninstallable */
1333                   continue;
1334                 }
1335
1336               IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION)
1337                 {
1338                   POOL_DEBUG(SAT_DEBUG_RULE_CREATION,"  %s requires %s\n", solvable2str(pool, s), dep2str(pool, req));
1339                   for (i = 0; dp[i]; i++)
1340                     POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "   provided by %s\n", solvable2str(pool, pool->solvables + dp[i]));
1341                 }
1342
1343               /* add 'requires' dependency */
1344               /* rule: (-requestor|provider1|provider2|...|providerN) */
1345               addrule(solv, -n, dp - pool->whatprovidesdata);
1346
1347               /* descend the dependency tree
1348                  push all non-visited providers on the work queue */
1349               for (; *dp; dp++)
1350                 {
1351                   if (!MAPTST(m, *dp))
1352                     queue_push(&workq, *dp);
1353                 }
1354
1355             } /* while, requirements of n */
1356
1357         } /* if, requirements */
1358
1359       /* that's all we check for src packages */
1360       if (s->arch == ARCH_SRC || s->arch == ARCH_NOSRC)
1361         continue;
1362
1363       /*-----------------------------------------
1364        * check conflicts of s
1365        */
1366
1367       if (s->conflicts)
1368         {
1369           int ispatch = 0;
1370
1371           /* we treat conflicts in patches a bit differen:
1372            * - nevr matching
1373            * - multiversion handling
1374            * XXX: we should really handle this different, looking
1375            * at the name is a bad hack
1376            */
1377           if (!strncmp("patch:", id2str(pool, s->name), 6))
1378             ispatch = 1;
1379           conp = s->repo->idarraydata + s->conflicts;
1380           /* foreach conflicts of 's' */
1381           while ((con = *conp++) != 0)
1382             {
1383               /* foreach providers of a conflict of 's' */
1384               FOR_PROVIDES(p, pp, con)
1385                 {
1386                   if (ispatch && !pool_match_nevr(pool, pool->solvables + p, con))
1387                     continue;
1388                   /* dontfix: dont care about conflicts with already installed packs */
1389                   if (dontfix && pool->solvables[p].repo == installed)
1390                     continue;
1391                   /* p == n: self conflict */
1392                   if (p == n && !solv->allowselfconflicts)
1393                     {
1394                       if (ISRELDEP(con))
1395                         {
1396                           Reldep *rd = GETRELDEP(pool, con);
1397                           if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_OTHERPROVIDERS)
1398                             continue;
1399                         }
1400                       p = 0;    /* make it a negative assertion, aka 'uninstallable' */
1401                     }
1402                   if (p && ispatch && solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p) && ISRELDEP(con))
1403                     {
1404                       /* our patch conflicts with a noobsoletes (aka multiversion) package */
1405                       p = -makemultiversionconflict(solv, p, con);
1406                     }
1407                  /* rule: -n|-p: either solvable _or_ provider of conflict */
1408                   addrule(solv, -n, -p);
1409                 }
1410             }
1411         }
1412
1413       /*-----------------------------------------
1414        * check obsoletes if not installed
1415        * (only installation will trigger the obsoletes in rpm)
1416        */
1417       if (!installed || pool->solvables[n].repo != installed)
1418         {                              /* not installed */
1419           int noobs = solv->noobsoletes.size && MAPTST(&solv->noobsoletes, n);
1420           if (s->obsoletes && !noobs)
1421             {
1422               obsp = s->repo->idarraydata + s->obsoletes;
1423               /* foreach obsoletes */
1424               while ((obs = *obsp++) != 0)
1425                 {
1426                   /* foreach provider of an obsoletes of 's' */
1427                   FOR_PROVIDES(p, pp, obs)
1428                     {
1429                       if (!solv->obsoleteusesprovides /* obsoletes are matched names, not provides */
1430                           && !pool_match_nevr(pool, pool->solvables + p, obs))
1431                         continue;
1432                       addrule(solv, -n, -p);
1433                     }
1434                 }
1435             }
1436           FOR_PROVIDES(p, pp, s->name)
1437             {
1438               Solvable *ps = pool->solvables + p;
1439               /* we still obsolete packages with same nevra, like rpm does */
1440               /* (actually, rpm mixes those packages. yuck...) */
1441               if (noobs && (s->name != ps->name || s->evr != ps->evr || s->arch != ps->arch))
1442                 continue;
1443               if (!solv->implicitobsoleteusesprovides && s->name != ps->name)
1444                 continue;
1445               addrule(solv, -n, -p);
1446             }
1447         }
1448
1449       /*-----------------------------------------
1450        * add recommends to the work queue
1451        */
1452       if (s->recommends)
1453         {
1454           recp = s->repo->idarraydata + s->recommends;
1455           while ((rec = *recp++) != 0)
1456             {
1457               FOR_PROVIDES(p, pp, rec)
1458                 if (!MAPTST(m, p))
1459                   queue_push(&workq, p);
1460             }
1461         }
1462       if (s->suggests)
1463         {
1464           sugp = s->repo->idarraydata + s->suggests;
1465           while ((sug = *sugp++) != 0)
1466             {
1467               FOR_PROVIDES(p, pp, sug)
1468                 if (!MAPTST(m, p))
1469                   queue_push(&workq, p);
1470             }
1471         }
1472     }
1473   queue_free(&workq);
1474   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforsolvable end -----\n");
1475 }
1476
1477
1478 /*-------------------------------------------------------------------
1479  *
1480  * Add package rules for weak rules
1481  *
1482  * m: visited solvables
1483  */
1484
1485 static void
1486 addrpmrulesforweak(Solver *solv, Map *m)
1487 {
1488   Pool *pool = solv->pool;
1489   Solvable *s;
1490   Id sup, *supp;
1491   int i, n;
1492
1493   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforweak -----\n");
1494     /* foreach solvable in pool */
1495   for (i = n = 1; n < pool->nsolvables; i++, n++)
1496     {
1497       if (i == pool->nsolvables)                 /* wrap i */
1498         i = 1;
1499       if (MAPTST(m, i))                          /* been there */
1500         continue;
1501
1502       s = pool->solvables + i;
1503       if (!pool_installable(pool, s))            /* only look at installable ones */
1504         continue;
1505
1506       sup = 0;
1507       if (s->supplements)
1508         {
1509           /* find possible supplements */
1510           supp = s->repo->idarraydata + s->supplements;
1511           while ((sup = *supp++) != ID_NULL)
1512             if (dep_possible(solv, sup, m))
1513               break;
1514         }
1515
1516         /* if nothing found, check for enhances */
1517       if (!sup && s->enhances)
1518         {
1519           supp = s->repo->idarraydata + s->enhances;
1520           while ((sup = *supp++) != ID_NULL)
1521             if (dep_possible(solv, sup, m))
1522               break;
1523         }
1524         /* if nothing found, goto next solvables */
1525       if (!sup)
1526         continue;
1527       addrpmrulesforsolvable(solv, s, m);
1528       n = 0;
1529     }
1530   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforweak end -----\n");
1531 }
1532
1533
1534 /*-------------------------------------------------------------------
1535  *
1536  * add package rules for possible updates
1537  *
1538  * s: solvable
1539  * m: map of already visited solvables
1540  * allow_all: 0 = dont allow downgrades, 1 = allow all candidates
1541  */
1542
1543 static void
1544 addrpmrulesforupdaters(Solver *solv, Solvable *s, Map *m, int allow_all)
1545 {
1546   Pool *pool = solv->pool;
1547   int i;
1548     /* queue and buffer for it */
1549   Queue qs;
1550   Id qsbuf[64];
1551
1552   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforupdaters -----\n");
1553
1554   queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
1555     /* find update candidates for 's' */
1556   policy_findupdatepackages(solv, s, &qs, allow_all);
1557     /* add rule for 's' if not already done */
1558   if (!MAPTST(m, s - pool->solvables))
1559     addrpmrulesforsolvable(solv, s, m);
1560     /* foreach update candidate, add rule if not already done */
1561   for (i = 0; i < qs.count; i++)
1562     if (!MAPTST(m, qs.elements[i]))
1563       addrpmrulesforsolvable(solv, pool->solvables + qs.elements[i], m);
1564   queue_free(&qs);
1565
1566   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforupdaters -----\n");
1567 }
1568
1569 static Id
1570 finddistupgradepackages(Solver *solv, Solvable *s, Queue *qs, int allow_all)
1571 {
1572   Pool *pool = solv->pool;
1573   int i;
1574
1575   policy_findupdatepackages(solv, s, qs, allow_all);
1576   if (!qs->count)
1577     {
1578       if (allow_all)
1579         return 0;       /* orphaned, don't create feature rule */
1580       /* check if this is an orphaned package */
1581       policy_findupdatepackages(solv, s, qs, 1);
1582       if (!qs->count)
1583         return 0;       /* orphaned, don't create update rule */
1584       qs->count = 0;
1585       return -SYSTEMSOLVABLE;   /* supported but not installable */
1586     }
1587   if (allow_all)
1588     return s - pool->solvables;
1589   /* check if it is ok to keep the installed package */
1590   for (i = 0; i < qs->count; i++)
1591     {
1592       Solvable *ns = pool->solvables + qs->elements[i];
1593       if (s->evr == ns->evr && solvable_identical(s, ns))
1594         return s - pool->solvables;
1595     }
1596   /* nope, it must be some other package */
1597   return -SYSTEMSOLVABLE;
1598 }
1599
1600 /* add packages from the dup repositories to the update candidates
1601  * this isn't needed for the global dup mode as all packages are
1602  * from dup repos in that case */
1603 static void
1604 addduppackages(Solver *solv, Solvable *s, Queue *qs)
1605 {
1606   Queue dupqs;
1607   Id p, dupqsbuf[64];
1608   int i;
1609   int oldnoupdateprovide = solv->noupdateprovide;
1610
1611   queue_init_buffer(&dupqs, dupqsbuf, sizeof(dupqsbuf)/sizeof(*dupqsbuf));
1612   solv->noupdateprovide = 1;
1613   policy_findupdatepackages(solv, s, &dupqs, 2);
1614   solv->noupdateprovide = oldnoupdateprovide;
1615   for (i = 0; i < dupqs.count; i++)
1616     {
1617       p = dupqs.elements[i];
1618       if (MAPTST(&solv->dupmap, p))
1619         queue_pushunique(qs, p);
1620     }
1621   queue_free(&dupqs);
1622 }
1623
1624 /*-------------------------------------------------------------------
1625  *
1626  * add rule for update
1627  *   (A|A1|A2|A3...)  An = update candidates for A
1628  *
1629  * s = (installed) solvable
1630  */
1631
1632 static void
1633 addupdaterule(Solver *solv, Solvable *s, int allow_all)
1634 {
1635   /* installed packages get a special upgrade allowed rule */
1636   Pool *pool = solv->pool;
1637   Id p, d;
1638   Queue qs;
1639   Id qsbuf[64];
1640
1641   POOL_DEBUG(SAT_DEBUG_SCHUBI, "-----  addupdaterule -----\n");
1642   queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
1643   p = s - pool->solvables;
1644   /* find update candidates for 's' */
1645   if (solv->distupgrade)
1646     p = finddistupgradepackages(solv, s, &qs, allow_all);
1647   else
1648     policy_findupdatepackages(solv, s, &qs, allow_all);
1649   if (!allow_all && !solv->distupgrade && solv->dupinvolvedmap.size && MAPTST(&solv->dupinvolvedmap, p))
1650     addduppackages(solv, s, &qs);
1651
1652   if (!allow_all && qs.count && solv->noobsoletes.size)
1653     {
1654       int i, j;
1655
1656       d = pool_queuetowhatprovides(pool, &qs);
1657       /* filter out all noobsoletes packages as they don't update */
1658       for (i = j = 0; i < qs.count; i++)
1659         {
1660           if (MAPTST(&solv->noobsoletes, qs.elements[i]))
1661             {
1662               /* it's ok if they have same nevra */
1663               Solvable *ps = pool->solvables + qs.elements[i];
1664               if (ps->name != s->name || ps->evr != s->evr || ps->arch != s->arch)
1665                 continue;
1666             }
1667           qs.elements[j++] = qs.elements[i];
1668         }
1669       if (j == 0 && p == -SYSTEMSOLVABLE && solv->distupgrade)
1670         {
1671           queue_push(&solv->orphaned, s - pool->solvables);     /* treat as orphaned */
1672           j = qs.count;
1673         }
1674       if (j < qs.count)
1675         {
1676           if (d && solv->updatesystem && solv->installed && s->repo == solv->installed)
1677             {
1678               if (!solv->multiversionupdaters)
1679                 solv->multiversionupdaters = sat_calloc(solv->installed->end - solv->installed->start, sizeof(Id));
1680               solv->multiversionupdaters[s - pool->solvables - solv->installed->start] = d;
1681             }
1682           qs.count = j;
1683         }
1684     }
1685   if (qs.count && p == -SYSTEMSOLVABLE)
1686     p = queue_shift(&qs);
1687   d = qs.count ? pool_queuetowhatprovides(pool, &qs) : 0;
1688   queue_free(&qs);
1689   addrule(solv, p, d);  /* allow update of s */
1690   POOL_DEBUG(SAT_DEBUG_SCHUBI, "-----  addupdaterule end -----\n");
1691 }
1692
1693
1694 /********************************************************************/
1695 /* watches */
1696
1697
1698 /*-------------------------------------------------------------------
1699  * makewatches
1700  *
1701  * initial setup for all watches
1702  */
1703
1704 static void
1705 makewatches(Solver *solv)
1706 {
1707   Rule *r;
1708   int i;
1709   int nsolvables = solv->pool->nsolvables;
1710
1711   sat_free(solv->watches);
1712                                        /* lower half for removals, upper half for installs */
1713   solv->watches = sat_calloc(2 * nsolvables, sizeof(Id));
1714 #if 1
1715   /* do it reverse so rpm rules get triggered first (XXX: obsolete?) */
1716   for (i = 1, r = solv->rules + solv->nrules - 1; i < solv->nrules; i++, r--)
1717 #else
1718   for (i = 1, r = solv->rules + 1; i < solv->nrules; i++, r++)
1719 #endif
1720     {
1721       if (!r->w2)               /* assertions do not need watches */
1722         continue;
1723
1724       /* see addwatches_rule(solv, r) */
1725       r->n1 = solv->watches[nsolvables + r->w1];
1726       solv->watches[nsolvables + r->w1] = r - solv->rules;
1727
1728       r->n2 = solv->watches[nsolvables + r->w2];
1729       solv->watches[nsolvables + r->w2] = r - solv->rules;
1730     }
1731 }
1732
1733
1734 /*-------------------------------------------------------------------
1735  *
1736  * add watches (for rule)
1737  * sets up watches for a single rule
1738  *
1739  * see also makewatches()
1740  */
1741
1742 static inline void
1743 addwatches_rule(Solver *solv, Rule *r)
1744 {
1745   int nsolvables = solv->pool->nsolvables;
1746
1747   r->n1 = solv->watches[nsolvables + r->w1];
1748   solv->watches[nsolvables + r->w1] = r - solv->rules;
1749
1750   r->n2 = solv->watches[nsolvables + r->w2];
1751   solv->watches[nsolvables + r->w2] = r - solv->rules;
1752 }
1753
1754
1755 /********************************************************************/
1756 /*
1757  * rule propagation
1758  */
1759
1760
1761 /* shortcuts to check if a literal (positive or negative) assignment
1762  * evaluates to 'true' or 'false'
1763  */
1764 #define DECISIONMAP_TRUE(p) ((p) > 0 ? (decisionmap[p] > 0) : (decisionmap[-p] < 0))
1765 #define DECISIONMAP_FALSE(p) ((p) > 0 ? (decisionmap[p] < 0) : (decisionmap[-p] > 0))
1766 #define DECISIONMAP_UNDEF(p) (decisionmap[(p) > 0 ? (p) : -(p)] == 0)
1767
1768 /*-------------------------------------------------------------------
1769  *
1770  * propagate
1771  *
1772  * make decision and propagate to all rules
1773  *
1774  * Evaluate each term affected by the decision (linked through watches)
1775  * If we find unit rules we make new decisions based on them
1776  *
1777  * Everything's fixed there, it's just finding rules that are
1778  * unit.
1779  *
1780  * return : 0 = everything is OK
1781  *          rule = conflict found in this rule
1782  */
1783
1784 static Rule *
1785 propagate(Solver *solv, int level)
1786 {
1787   Pool *pool = solv->pool;
1788   Id *rp, *next_rp;           /* rule pointer, next rule pointer in linked list */
1789   Rule *r;                    /* rule */
1790   Id p, pkg, other_watch;
1791   Id *dp;
1792   Id *decisionmap = solv->decisionmap;
1793
1794   Id *watches = solv->watches + pool->nsolvables;   /* place ptr in middle */
1795
1796   POOL_DEBUG(SAT_DEBUG_PROPAGATE, "----- propagate -----\n");
1797
1798   /* foreach non-propagated decision */
1799   while (solv->propagate_index < solv->decisionq.count)
1800     {
1801         /*
1802          * 'pkg' was just decided
1803          * negate because our watches trigger if literal goes FALSE
1804          */
1805       pkg = -solv->decisionq.elements[solv->propagate_index++];
1806
1807       IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1808         {
1809           POOL_DEBUG(SAT_DEBUG_PROPAGATE, "propagate for decision %d level %d\n", -pkg, level);
1810           solver_printruleelement(solv, SAT_DEBUG_PROPAGATE, 0, -pkg);
1811         }
1812
1813       /* foreach rule where 'pkg' is now FALSE */
1814       for (rp = watches + pkg; *rp; rp = next_rp)
1815         {
1816           r = solv->rules + *rp;
1817           if (r->d < 0)
1818             {
1819               /* rule is disabled, goto next */
1820               if (pkg == r->w1)
1821                 next_rp = &r->n1;
1822               else
1823                 next_rp = &r->n2;
1824               continue;
1825             }
1826
1827           IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1828             {
1829               POOL_DEBUG(SAT_DEBUG_PROPAGATE,"  watch triggered ");
1830               solver_printrule(solv, SAT_DEBUG_PROPAGATE, r);
1831             }
1832
1833             /* 'pkg' was just decided (was set to FALSE)
1834              *
1835              *  now find other literal watch, check clause
1836              *   and advance on linked list
1837              */
1838           if (pkg == r->w1)
1839             {
1840               other_watch = r->w2;
1841               next_rp = &r->n1;
1842             }
1843           else
1844             {
1845               other_watch = r->w1;
1846               next_rp = &r->n2;
1847             }
1848
1849             /*
1850              * This term is already true (through the other literal)
1851              * so we have nothing to do
1852              */
1853           if (DECISIONMAP_TRUE(other_watch))
1854             continue;
1855
1856             /*
1857              * The other literal is FALSE or UNDEF
1858              *
1859              */
1860
1861           if (r->d)
1862             {
1863               /* Not a binary clause, try to move our watch.
1864                *
1865                * Go over all literals and find one that is
1866                *   not other_watch
1867                *   and not FALSE
1868                *
1869                * (TRUE is also ok, in that case the rule is fulfilled)
1870                */
1871               if (r->p                                /* we have a 'p' */
1872                   && r->p != other_watch              /* which is not watched */
1873                   && !DECISIONMAP_FALSE(r->p))        /* and not FALSE */
1874                 {
1875                   p = r->p;
1876                 }
1877               else                                    /* go find a 'd' to make 'true' */
1878                 {
1879                   /* foreach p in 'd'
1880                      we just iterate sequentially, doing it in another order just changes the order of decisions, not the decisions itself
1881                    */
1882                   for (dp = pool->whatprovidesdata + r->d; (p = *dp++) != 0;)
1883                     {
1884                       if (p != other_watch              /* which is not watched */
1885                           && !DECISIONMAP_FALSE(p))     /* and not FALSE */
1886                         break;
1887                     }
1888                 }
1889
1890               if (p)
1891                 {
1892                   /*
1893                    * if we found some p that is UNDEF or TRUE, move
1894                    * watch to it
1895                    */
1896                   IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1897                     {
1898                       if (p > 0)
1899                         POOL_DEBUG(SAT_DEBUG_PROPAGATE, "    -> move w%d to %s\n", (pkg == r->w1 ? 1 : 2), solvable2str(pool, pool->solvables + p));
1900                       else
1901                         POOL_DEBUG(SAT_DEBUG_PROPAGATE,"    -> move w%d to !%s\n", (pkg == r->w1 ? 1 : 2), solvable2str(pool, pool->solvables - p));
1902                     }
1903
1904                   *rp = *next_rp;
1905                   next_rp = rp;
1906
1907                   if (pkg == r->w1)
1908                     {
1909                       r->w1 = p;
1910                       r->n1 = watches[p];
1911                     }
1912                   else
1913                     {
1914                       r->w2 = p;
1915                       r->n2 = watches[p];
1916                     }
1917                   watches[p] = r - solv->rules;
1918                   continue;
1919                 }
1920               /* search failed, thus all unwatched literals are FALSE */
1921
1922             } /* not binary */
1923
1924             /*
1925              * unit clause found, set literal other_watch to TRUE
1926              */
1927
1928           if (DECISIONMAP_FALSE(other_watch))      /* check if literal is FALSE */
1929             return r;                              /* eek, a conflict! */
1930
1931           IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1932             {
1933               POOL_DEBUG(SAT_DEBUG_PROPAGATE, "   unit ");
1934               solver_printrule(solv, SAT_DEBUG_PROPAGATE, r);
1935             }
1936
1937           if (other_watch > 0)
1938             decisionmap[other_watch] = level;    /* install! */
1939           else
1940             decisionmap[-other_watch] = -level;  /* remove! */
1941
1942           queue_push(&solv->decisionq, other_watch);
1943           queue_push(&solv->decisionq_why, r - solv->rules);
1944
1945           IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1946             {
1947               Solvable *s = pool->solvables + (other_watch > 0 ? other_watch : -other_watch);
1948               if (other_watch > 0)
1949                 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "    -> decided to install %s\n", solvable2str(pool, s));
1950               else
1951                 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "    -> decided to conflict %s\n", solvable2str(pool, s));
1952             }
1953
1954         } /* foreach rule involving 'pkg' */
1955
1956     } /* while we have non-decided decisions */
1957
1958   POOL_DEBUG(SAT_DEBUG_PROPAGATE, "----- propagate end-----\n");
1959
1960   return 0;     /* all is well */
1961 }
1962
1963
1964 /********************************************************************/
1965 /* Analysis */
1966
1967 /*-------------------------------------------------------------------
1968  *
1969  * analyze
1970  *   and learn
1971  */
1972
1973 static int
1974 analyze(Solver *solv, int level, Rule *c, int *pr, int *dr, int *whyp)
1975 {
1976   Pool *pool = solv->pool;
1977   Queue r;
1978   int rlevel = 1;
1979   Map seen;             /* global? */
1980   Id d, v, vv, *dp, why;
1981   int l, i, idx;
1982   int num = 0, l1num = 0;
1983   int learnt_why = solv->learnt_pool.count;
1984   Id *decisionmap = solv->decisionmap;
1985
1986   queue_init(&r);
1987
1988   POOL_DEBUG(SAT_DEBUG_ANALYZE, "ANALYZE at %d ----------------------\n", level);
1989   map_init(&seen, pool->nsolvables);
1990   idx = solv->decisionq.count;
1991   for (;;)
1992     {
1993       IF_POOLDEBUG (SAT_DEBUG_ANALYZE)
1994         solver_printruleclass(solv, SAT_DEBUG_ANALYZE, c);
1995       queue_push(&solv->learnt_pool, c - solv->rules);
1996       d = c->d < 0 ? -c->d - 1 : c->d;
1997       dp = d ? pool->whatprovidesdata + d : 0;
1998       /* go through all literals of the rule */
1999       for (i = -1; ; i++)
2000         {
2001           if (i == -1)
2002             v = c->p;
2003           else if (d == 0)
2004             v = i ? 0 : c->w2;
2005           else
2006             v = *dp++;
2007           if (v == 0)
2008             break;
2009
2010           if (DECISIONMAP_TRUE(v))      /* the one true literal */
2011             continue;
2012           vv = v > 0 ? v : -v;
2013           if (MAPTST(&seen, vv))
2014             continue;
2015           l = solv->decisionmap[vv];
2016           if (l < 0)
2017             l = -l;
2018           MAPSET(&seen, vv);
2019           if (l == 1)
2020             l1num++;                    /* need to do this one in level1 pass */
2021           else if (l == level)
2022             num++;                      /* need to do this one as well */
2023           else
2024             {
2025               queue_push(&r, v);        /* not level1 or conflict level, add to new rule */
2026               if (l > rlevel)
2027                 rlevel = l;
2028             }
2029         }
2030 l1retry:
2031       if (!num && !--l1num)
2032         break;  /* all level 1 literals done */
2033       for (;;)
2034         {
2035           assert(idx > 0);
2036           v = solv->decisionq.elements[--idx];
2037           vv = v > 0 ? v : -v;
2038           if (MAPTST(&seen, vv))
2039             break;
2040         }
2041       MAPCLR(&seen, vv);
2042       if (num && --num == 0)
2043         {
2044           *pr = -v;     /* so that v doesn't get lost */
2045           if (!l1num)
2046             break;
2047           POOL_DEBUG(SAT_DEBUG_ANALYZE, "got %d involved level 1 decisions\n", l1num);
2048           for (i = 0; i < r.count; i++)
2049             {
2050               v = r.elements[i];
2051               MAPCLR(&seen, v > 0 ? v : -v);
2052             }
2053           /* only level 1 marks left */
2054           l1num++;
2055           goto l1retry;
2056         }
2057       why = solv->decisionq_why.elements[idx];
2058       if (why <= 0)     /* just in case, maybe for SYSTEMSOLVABLE */
2059         goto l1retry;
2060       c = solv->rules + why;
2061     }
2062   map_free(&seen);
2063
2064   if (r.count == 0)
2065     *dr = 0;
2066   else if (r.count == 1 && r.elements[0] < 0)
2067     *dr = r.elements[0];
2068   else
2069     *dr = pool_queuetowhatprovides(pool, &r);
2070   IF_POOLDEBUG (SAT_DEBUG_ANALYZE)
2071     {
2072       POOL_DEBUG(SAT_DEBUG_ANALYZE, "learned rule for level %d (am %d)\n", rlevel, level);
2073       solver_printruleelement(solv, SAT_DEBUG_ANALYZE, 0, *pr);
2074       for (i = 0; i < r.count; i++)
2075         solver_printruleelement(solv, SAT_DEBUG_ANALYZE, 0, r.elements[i]);
2076     }
2077   /* push end marker on learnt reasons stack */
2078   queue_push(&solv->learnt_pool, 0);
2079   if (whyp)
2080     *whyp = learnt_why;
2081   solv->stats_learned++;
2082   return rlevel;
2083 }
2084
2085
2086 /*-------------------------------------------------------------------
2087  *
2088  * reset_solver
2089  *
2090  * reset the solver decisions to right after the rpm rules.
2091  * called after rules have been enabled/disabled
2092  */
2093
2094 static void
2095 reset_solver(Solver *solv)
2096 {
2097   Pool *pool = solv->pool;
2098   int i;
2099   Id v;
2100
2101   /* rewind decisions to direct rpm rule assertions */
2102   for (i = solv->decisionq.count - 1; i >= solv->directdecisions; i--)
2103     {
2104       v = solv->decisionq.elements[i];
2105       solv->decisionmap[v > 0 ? v : -v] = 0;
2106     }
2107
2108   POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "decisions done reduced from %d to %d\n", solv->decisionq.count, solv->directdecisions);
2109
2110   solv->decisionq_why.count = solv->directdecisions;
2111   solv->decisionq.count = solv->directdecisions;
2112   solv->recommends_index = -1;
2113   solv->propagate_index = 0;
2114
2115   /* adapt learnt rule status to new set of enabled/disabled rules */
2116   enabledisablelearntrules(solv);
2117
2118   /* redo all job/update decisions */
2119   makeruledecisions(solv);
2120   POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "decisions so far: %d\n", solv->decisionq.count);
2121 }
2122
2123
2124 /*-------------------------------------------------------------------
2125  *
2126  * analyze_unsolvable_rule
2127  */
2128
2129 static void
2130 analyze_unsolvable_rule(Solver *solv, Rule *r, Id *lastweakp)
2131 {
2132   Pool *pool = solv->pool;
2133   int i;
2134   Id why = r - solv->rules;
2135
2136   IF_POOLDEBUG (SAT_DEBUG_UNSOLVABLE)
2137     solver_printruleclass(solv, SAT_DEBUG_UNSOLVABLE, r);
2138   if (solv->learntrules && why >= solv->learntrules)
2139     {
2140       for (i = solv->learnt_why.elements[why - solv->learntrules]; solv->learnt_pool.elements[i]; i++)
2141         if (solv->learnt_pool.elements[i] > 0)
2142           analyze_unsolvable_rule(solv, solv->rules + solv->learnt_pool.elements[i], lastweakp);
2143       return;
2144     }
2145   if (MAPTST(&solv->weakrulemap, why))
2146     if (!*lastweakp || why > *lastweakp)
2147       *lastweakp = why;
2148   /* do not add rpm rules to problem */
2149   if (why < solv->rpmrules_end)
2150     return;
2151   /* turn rule into problem */
2152   if (why >= solv->jobrules && why < solv->jobrules_end)
2153     why = -(solv->ruletojob.elements[why - solv->jobrules] + 1);
2154   /* normalize dup/infarch rules */
2155   if (why > solv->infarchrules && why < solv->infarchrules_end)
2156     {
2157       Id name = pool->solvables[-solv->rules[why].p].name;
2158       while (why > solv->infarchrules && pool->solvables[-solv->rules[why - 1].p].name == name)
2159         why--;
2160     }
2161   if (why > solv->duprules && why < solv->duprules_end)
2162     {
2163       Id name = pool->solvables[-solv->rules[why].p].name;
2164       while (why > solv->duprules && pool->solvables[-solv->rules[why - 1].p].name == name)
2165         why--;
2166     }
2167
2168   /* return if problem already countains our rule */
2169   if (solv->problems.count)
2170     {
2171       for (i = solv->problems.count - 1; i >= 0; i--)
2172         if (solv->problems.elements[i] == 0)    /* end of last problem reached? */
2173           break;
2174         else if (solv->problems.elements[i] == why)
2175           return;
2176     }
2177   queue_push(&solv->problems, why);
2178 }
2179
2180
2181 /*-------------------------------------------------------------------
2182  *
2183  * analyze_unsolvable
2184  *
2185  * return: 1 - disabled some rules, try again
2186  *         0 - hopeless
2187  */
2188
2189 static int
2190 analyze_unsolvable(Solver *solv, Rule *cr, int disablerules)
2191 {
2192   Pool *pool = solv->pool;
2193   Rule *r;
2194   Map seen;             /* global to speed things up? */
2195   Id d, v, vv, *dp, why;
2196   int l, i, idx;
2197   Id *decisionmap = solv->decisionmap;
2198   int oldproblemcount;
2199   int oldlearntpoolcount;
2200   Id lastweak;
2201
2202   POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "ANALYZE UNSOLVABLE ----------------------\n");
2203   solv->stats_unsolvable++;
2204   oldproblemcount = solv->problems.count;
2205   oldlearntpoolcount = solv->learnt_pool.count;
2206
2207   /* make room for proof index */
2208   /* must update it later, as analyze_unsolvable_rule would confuse
2209    * it with a rule index if we put the real value in already */
2210   queue_push(&solv->problems, 0);
2211
2212   r = cr;
2213   map_init(&seen, pool->nsolvables);
2214   queue_push(&solv->learnt_pool, r - solv->rules);
2215   lastweak = 0;
2216   analyze_unsolvable_rule(solv, r, &lastweak);
2217   d = r->d < 0 ? -r->d - 1 : r->d;
2218   dp = d ? pool->whatprovidesdata + d : 0;
2219   for (i = -1; ; i++)
2220     {
2221       if (i == -1)
2222         v = r->p;
2223       else if (d == 0)
2224         v = i ? 0 : r->w2;
2225       else
2226         v = *dp++;
2227       if (v == 0)
2228         break;
2229       if (DECISIONMAP_TRUE(v))  /* the one true literal */
2230           continue;
2231       vv = v > 0 ? v : -v;
2232       l = solv->decisionmap[vv];
2233       if (l < 0)
2234         l = -l;
2235       MAPSET(&seen, vv);
2236     }
2237   idx = solv->decisionq.count;
2238   while (idx > 0)
2239     {
2240       v = solv->decisionq.elements[--idx];
2241       vv = v > 0 ? v : -v;
2242       if (!MAPTST(&seen, vv))
2243         continue;
2244       why = solv->decisionq_why.elements[idx];
2245       assert(why > 0);
2246       queue_push(&solv->learnt_pool, why);
2247       r = solv->rules + why;
2248       analyze_unsolvable_rule(solv, r, &lastweak);
2249       d = r->d < 0 ? -r->d - 1 : r->d;
2250       dp = d ? pool->whatprovidesdata + d : 0;
2251       for (i = -1; ; i++)
2252         {
2253           if (i == -1)
2254             v = r->p;
2255           else if (d == 0)
2256             v = i ? 0 : r->w2;
2257           else
2258             v = *dp++;
2259           if (v == 0)
2260             break;
2261           if (DECISIONMAP_TRUE(v))      /* the one true literal */
2262               continue;
2263           vv = v > 0 ? v : -v;
2264           l = solv->decisionmap[vv];
2265           if (l < 0)
2266             l = -l;
2267           MAPSET(&seen, vv);
2268         }
2269     }
2270   map_free(&seen);
2271   queue_push(&solv->problems, 0);       /* mark end of this problem */
2272
2273   if (lastweak)
2274     {
2275       Id v;
2276       /* disable last weak rule */
2277       solv->problems.count = oldproblemcount;
2278       solv->learnt_pool.count = oldlearntpoolcount;
2279       if (lastweak >= solv->jobrules && lastweak < solv->jobrules_end)
2280         v = -(solv->ruletojob.elements[lastweak - solv->jobrules] + 1);
2281       else
2282         v = lastweak;
2283       POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "disabling ");
2284       solver_printruleclass(solv, SAT_DEBUG_UNSOLVABLE, solv->rules + lastweak);
2285       disableproblem(solv, v);
2286       if (v < 0)
2287         disableupdaterules(solv, solv->job, -(v + 1));
2288       reset_solver(solv);
2289       return 1;
2290     }
2291
2292   /* finish proof */
2293   queue_push(&solv->learnt_pool, 0);
2294   solv->problems.elements[oldproblemcount] = oldlearntpoolcount;
2295
2296   if (disablerules)
2297     {
2298       for (i = oldproblemcount + 1; i < solv->problems.count - 1; i++)
2299         disableproblem(solv, solv->problems.elements[i]);
2300       /* XXX: might want to enable all weak rules again */
2301       reset_solver(solv);
2302       return 1;
2303     }
2304   POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "UNSOLVABLE\n");
2305   return 0;
2306 }
2307
2308
2309 /********************************************************************/
2310 /* Decision revert */
2311
2312 /*-------------------------------------------------------------------
2313  *
2314  * revert
2315  * revert decision at level
2316  */
2317
2318 static void
2319 revert(Solver *solv, int level)
2320 {
2321   Pool *pool = solv->pool;
2322   Id v, vv;
2323   while (solv->decisionq.count)
2324     {
2325       v = solv->decisionq.elements[solv->decisionq.count - 1];
2326       vv = v > 0 ? v : -v;
2327       if (solv->decisionmap[vv] <= level && solv->decisionmap[vv] >= -level)
2328         break;
2329       POOL_DEBUG(SAT_DEBUG_PROPAGATE, "reverting decision %d at %d\n", v, solv->decisionmap[vv]);
2330       if (v > 0 && solv->recommendations.count && v == solv->recommendations.elements[solv->recommendations.count - 1])
2331         solv->recommendations.count--;
2332       solv->decisionmap[vv] = 0;
2333       solv->decisionq.count--;
2334       solv->decisionq_why.count--;
2335       solv->propagate_index = solv->decisionq.count;
2336     }
2337   while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] <= -level)
2338     {
2339       solv->branches.count--;
2340       while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] >= 0)
2341         solv->branches.count--;
2342     }
2343   solv->recommends_index = -1;
2344 }
2345
2346
2347 /*-------------------------------------------------------------------
2348  *
2349  * watch2onhighest - put watch2 on literal with highest level
2350  */
2351
2352 static inline void
2353 watch2onhighest(Solver *solv, Rule *r)
2354 {
2355   int l, wl = 0;
2356   Id d, v, *dp;
2357
2358   d = r->d < 0 ? -r->d - 1 : r->d;
2359   if (!d)
2360     return;     /* binary rule, both watches are set */
2361   dp = solv->pool->whatprovidesdata + d;
2362   while ((v = *dp++) != 0)
2363     {
2364       l = solv->decisionmap[v < 0 ? -v : v];
2365       if (l < 0)
2366         l = -l;
2367       if (l > wl)
2368         {
2369           r->w2 = dp[-1];
2370           wl = l;
2371         }
2372     }
2373 }
2374
2375
2376 /*-------------------------------------------------------------------
2377  *
2378  * setpropagatelearn
2379  *
2380  * add free decision (solvable to install) to decisionq
2381  * increase level and propagate decision
2382  * return if no conflict.
2383  *
2384  * in conflict case, analyze conflict rule, add resulting
2385  * rule to learnt rule set, make decision from learnt
2386  * rule (always unit) and re-propagate.
2387  *
2388  * returns the new solver level or 0 if unsolvable
2389  *
2390  */
2391
2392 static int
2393 setpropagatelearn(Solver *solv, int level, Id decision, int disablerules, Id ruleid)
2394 {
2395   Pool *pool = solv->pool;
2396   Rule *r;
2397   Id p = 0, d = 0;
2398   int l, why;
2399
2400   assert(ruleid >= 0);
2401   if (decision)
2402     {
2403       level++;
2404       if (decision > 0)
2405         solv->decisionmap[decision] = level;
2406       else
2407         solv->decisionmap[-decision] = -level;
2408       queue_push(&solv->decisionq, decision);
2409       queue_push(&solv->decisionq_why, -ruleid);        /* <= 0 -> free decision */
2410     }
2411   for (;;)
2412     {
2413       r = propagate(solv, level);
2414       if (!r)
2415         break;
2416       if (level == 1)
2417         return analyze_unsolvable(solv, r, disablerules);
2418       POOL_DEBUG(SAT_DEBUG_ANALYZE, "conflict with rule #%d\n", (int)(r - solv->rules));
2419       l = analyze(solv, level, r, &p, &d, &why);        /* learnt rule in p and d */
2420       assert(l > 0 && l < level);
2421       POOL_DEBUG(SAT_DEBUG_ANALYZE, "reverting decisions (level %d -> %d)\n", level, l);
2422       level = l;
2423       revert(solv, level);
2424       r = addrule(solv, p, d);
2425       assert(r);
2426       assert(solv->learnt_why.count == (r - solv->rules) - solv->learntrules);
2427       queue_push(&solv->learnt_why, why);
2428       if (d)
2429         {
2430           /* at least 2 literals, needs watches */
2431           watch2onhighest(solv, r);
2432           addwatches_rule(solv, r);
2433         }
2434       else
2435         {
2436           /* learnt rule is an assertion */
2437           queue_push(&solv->ruleassertions, r - solv->rules);
2438         }
2439       solv->decisionmap[p > 0 ? p : -p] = p > 0 ? level : -level;
2440       queue_push(&solv->decisionq, p);
2441       queue_push(&solv->decisionq_why, r - solv->rules);
2442       IF_POOLDEBUG (SAT_DEBUG_ANALYZE)
2443         {
2444           POOL_DEBUG(SAT_DEBUG_ANALYZE, "decision: ");
2445           solver_printruleelement(solv, SAT_DEBUG_ANALYZE, 0, p);
2446           POOL_DEBUG(SAT_DEBUG_ANALYZE, "new rule: ");
2447           solver_printrule(solv, SAT_DEBUG_ANALYZE, r);
2448         }
2449     }
2450   return level;
2451 }
2452
2453
2454 /*-------------------------------------------------------------------
2455  *
2456  * select and install
2457  *
2458  * install best package from the queue. We add an extra package, inst, if
2459  * provided. See comment in weak install section.
2460  *
2461  * returns the new solver level or 0 if unsolvable
2462  *
2463  */
2464
2465 static int
2466 selectandinstall(Solver *solv, int level, Queue *dq, int disablerules, Id ruleid)
2467 {
2468   Pool *pool = solv->pool;
2469   Id p;
2470   int i;
2471
2472   if (dq->count > 1)
2473     policy_filter_unwanted(solv, dq, POLICY_MODE_CHOOSE);
2474   if (dq->count > 1)
2475     {
2476       /* XXX: didn't we already do that? */
2477       /* XXX: shouldn't we prefer installed packages? */
2478       /* XXX: move to policy.c? */
2479       /* choose the supplemented one */
2480       for (i = 0; i < dq->count; i++)
2481         if (solver_is_supplementing(solv, pool->solvables + dq->elements[i]))
2482           {
2483             dq->elements[0] = dq->elements[i];
2484             dq->count = 1;
2485             break;
2486           }
2487     }
2488   if (dq->count > 1)
2489     {
2490       /* multiple candidates, open a branch */
2491       for (i = 1; i < dq->count; i++)
2492         queue_push(&solv->branches, dq->elements[i]);
2493       queue_push(&solv->branches, -level);
2494     }
2495   p = dq->elements[0];
2496
2497   POOL_DEBUG(SAT_DEBUG_POLICY, "installing %s\n", solvable2str(pool, pool->solvables + p));
2498
2499   return setpropagatelearn(solv, level, p, disablerules, ruleid);
2500 }
2501
2502
2503 /********************************************************************/
2504 /* Main solver interface */
2505
2506
2507 /*-------------------------------------------------------------------
2508  *
2509  * solver_create
2510  * create solver structure
2511  *
2512  * pool: all available solvables
2513  * installed: installed Solvables
2514  *
2515  *
2516  * Upon solving, rules are created to flag the Solvables
2517  * of the 'installed' Repo as installed.
2518  */
2519
2520 Solver *
2521 solver_create(Pool *pool)
2522 {
2523   Solver *solv;
2524   solv = (Solver *)sat_calloc(1, sizeof(Solver));
2525   solv->pool = pool;
2526   solv->installed = pool->installed;
2527
2528   queue_init(&solv->ruletojob);
2529   queue_init(&solv->decisionq);
2530   queue_init(&solv->decisionq_why);
2531   queue_init(&solv->problems);
2532   queue_init(&solv->suggestions);
2533   queue_init(&solv->recommendations);
2534   queue_init(&solv->orphaned);
2535   queue_init(&solv->learnt_why);
2536   queue_init(&solv->learnt_pool);
2537   queue_init(&solv->branches);
2538   queue_init(&solv->covenantq);
2539   queue_init(&solv->weakruleq);
2540   queue_init(&solv->ruleassertions);
2541
2542   map_init(&solv->recommendsmap, pool->nsolvables);
2543   map_init(&solv->suggestsmap, pool->nsolvables);
2544   map_init(&solv->noupdate, solv->installed ? solv->installed->end - solv->installed->start : 0);
2545   solv->recommends_index = 0;
2546
2547   solv->decisionmap = (Id *)sat_calloc(pool->nsolvables, sizeof(Id));
2548   solv->nrules = 1;
2549   solv->rules = sat_extend_resize(solv->rules, solv->nrules, sizeof(Rule), RULES_BLOCK);
2550   memset(solv->rules, 0, sizeof(Rule));
2551
2552   return solv;
2553 }
2554
2555
2556 /*-------------------------------------------------------------------
2557  *
2558  * solver_free
2559  */
2560
2561 void
2562 solver_free(Solver *solv)
2563 {
2564   queue_free(&solv->ruletojob);
2565   queue_free(&solv->decisionq);
2566   queue_free(&solv->decisionq_why);
2567   queue_free(&solv->learnt_why);
2568   queue_free(&solv->learnt_pool);
2569   queue_free(&solv->problems);
2570   queue_free(&solv->suggestions);
2571   queue_free(&solv->recommendations);
2572   queue_free(&solv->orphaned);
2573   queue_free(&solv->branches);
2574   queue_free(&solv->covenantq);
2575   queue_free(&solv->weakruleq);
2576   queue_free(&solv->ruleassertions);
2577
2578   map_free(&solv->recommendsmap);
2579   map_free(&solv->suggestsmap);
2580   map_free(&solv->noupdate);
2581   map_free(&solv->weakrulemap);
2582   map_free(&solv->noobsoletes);
2583
2584   map_free(&solv->updatemap);
2585   map_free(&solv->dupmap);
2586   map_free(&solv->dupinvolvedmap);
2587
2588   sat_free(solv->decisionmap);
2589   sat_free(solv->rules);
2590   sat_free(solv->watches);
2591   sat_free(solv->obsoletes);
2592   sat_free(solv->obsoletes_data);
2593   sat_free(solv->multiversionupdaters);
2594   sat_free(solv);
2595 }
2596
2597
2598 /*-------------------------------------------------------------------
2599  *
2600  * run_solver
2601  *
2602  * all rules have been set up, now actually run the solver
2603  *
2604  */
2605
2606 static void
2607 run_solver(Solver *solv, int disablerules, int doweak)
2608 {
2609   Queue dq;             /* local decisionqueue */
2610   Queue dqs;            /* local decisionqueue for supplements */
2611   int systemlevel;
2612   int level, olevel;
2613   Rule *r;
2614   int i, j, n;
2615   Solvable *s;
2616   Pool *pool = solv->pool;
2617   Id p, *dp;
2618   int minimizationsteps;
2619
2620   IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION)
2621     {
2622       POOL_DEBUG (SAT_DEBUG_RULE_CREATION, "number of rules: %d\n", solv->nrules);
2623       for (i = 1; i < solv->nrules; i++)
2624         solver_printruleclass(solv, SAT_DEBUG_RULE_CREATION, solv->rules + i);
2625     }
2626
2627   POOL_DEBUG(SAT_DEBUG_STATS, "initial decisions: %d\n", solv->decisionq.count);
2628
2629   IF_POOLDEBUG (SAT_DEBUG_SCHUBI)
2630     solver_printdecisions(solv);
2631
2632   /* start SAT algorithm */
2633   level = 1;
2634   systemlevel = level + 1;
2635   POOL_DEBUG(SAT_DEBUG_STATS, "solving...\n");
2636
2637   queue_init(&dq);
2638   queue_init(&dqs);
2639
2640   /*
2641    * here's the main loop:
2642    * 1) propagate new decisions (only needed for level 1)
2643    * 2) try to keep installed packages
2644    * 3) fulfill all unresolved rules
2645    * 4) install recommended packages
2646    * 5) minimalize solution if we had choices
2647    * if we encounter a problem, we rewind to a safe level and restart
2648    * with step 1
2649    */
2650
2651   minimizationsteps = 0;
2652   for (;;)
2653     {
2654       /*
2655        * propagate
2656        */
2657
2658       if (level == 1)
2659         {
2660           POOL_DEBUG(SAT_DEBUG_PROPAGATE, "propagating (propagate_index: %d;  size decisionq: %d)...\n", solv->propagate_index, solv->decisionq.count);
2661           if ((r = propagate(solv, level)) != 0)
2662             {
2663               if (analyze_unsolvable(solv, r, disablerules))
2664                 continue;
2665               queue_free(&dq);
2666               queue_free(&dqs);
2667               return;
2668             }
2669         }
2670
2671      if (level < systemlevel)
2672         {
2673           POOL_DEBUG(SAT_DEBUG_STATS, "resolving job rules\n");
2674           for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++)
2675             {
2676               Id l;
2677               if (r->d < 0)             /* ignore disabled rules */
2678                 continue;
2679               queue_empty(&dq);
2680               FOR_RULELITERALS(l, dp, r)
2681                 {
2682                   if (l < 0)
2683                     {
2684                       if (solv->decisionmap[-l] <= 0)
2685                         break;
2686                     }
2687                   else
2688                     {
2689                       if (solv->decisionmap[l] > 0)
2690                         break;
2691                       if (solv->decisionmap[l] == 0)
2692                         queue_push(&dq, l);
2693                     }
2694                 }
2695               if (l || !dq.count)
2696                 continue;
2697               /* prune to installed if not updating */
2698               if (!solv->updatesystem && solv->installed && dq.count > 1)
2699                 {
2700                   int j, k;
2701                   for (j = k = 0; j < dq.count; j++)
2702                     {
2703                       Solvable *s = pool->solvables + dq.elements[j];
2704                       if (s->repo == solv->installed)
2705                         dq.elements[k++] = dq.elements[j];
2706                     }
2707                   if (k)
2708                     dq.count = k;
2709                 }
2710               olevel = level;
2711               level = selectandinstall(solv, level, &dq, disablerules, i);
2712               if (level == 0)
2713                 {
2714                   queue_free(&dq);
2715                   queue_free(&dqs);
2716                   return;
2717                 }
2718               if (level <= olevel)
2719                 break;
2720             }
2721           systemlevel = level + 1;
2722           if (i < solv->jobrules_end)
2723             continue;
2724         }
2725
2726
2727       /*
2728        * installed packages
2729        */
2730
2731       if (level < systemlevel && solv->installed && solv->installed->nsolvables)
2732         {
2733           Repo *installed = solv->installed;
2734           int pass;
2735
2736           /* we use two passes if we need to update packages
2737            * to create a better user experience */
2738           for (pass = solv->updatemap.size ? 0 : 1; pass < 2; pass++)
2739             {
2740               FOR_REPO_SOLVABLES(installed, i, s)
2741                 {
2742                   Rule *rr;
2743                   Id d;
2744
2745                   if (MAPTST(&solv->noupdate, i - installed->start))
2746                     continue;
2747                   if (solv->decisionmap[i] > 0)
2748                     continue;
2749                   if (!pass && solv->updatemap.size && !MAPTST(&solv->updatemap, i - installed->start))
2750                     continue;           /* updates first */
2751                   r = solv->rules + solv->updaterules + (i - installed->start);
2752                   rr = r;
2753                   if (!rr->p || rr->d < 0)      /* disabled -> look at feature rule */
2754                     rr -= solv->installed->end - solv->installed->start;
2755                   if (!rr->p)           /* identical to update rule? */
2756                     rr = r;
2757                   if (!rr->p)
2758                     continue;           /* orpaned package */
2759
2760                   queue_empty(&dq);
2761                   if (solv->decisionmap[i] < 0 || solv->updatesystem || (solv->updatemap.size && MAPTST(&solv->updatemap, i - installed->start)) || rr->p != i)
2762                     {
2763                       if (solv->noobsoletes.size && solv->multiversionupdaters
2764                              && (d = solv->multiversionupdaters[i - installed->start]) != 0)
2765                         {
2766                           /* special multiversion handling, make sure best version is chosen */
2767                           queue_push(&dq, i);
2768                           while ((p = pool->whatprovidesdata[d++]) != 0)
2769                             if (solv->decisionmap[p] >= 0)
2770                               queue_push(&dq, p);
2771                           policy_filter_unwanted(solv, &dq, POLICY_MODE_CHOOSE);
2772                           p = dq.elements[0];
2773                           if (p != i && solv->decisionmap[p] == 0)
2774                             {
2775                               rr = solv->rules + solv->featurerules + (i - solv->installed->start);
2776                               if (!rr->p)               /* update rule == feature rule? */
2777                                 rr = rr - solv->featurerules + solv->updaterules;
2778                               dq.count = 1;
2779                             }
2780                           else
2781                             dq.count = 0;
2782                         }
2783                       else
2784                         {
2785                           /* update to best package */
2786                           FOR_RULELITERALS(p, dp, rr)
2787                             {
2788                               if (solv->decisionmap[p] > 0)
2789                                 {
2790                                   dq.count = 0;         /* already fulfilled */
2791                                   break;
2792                                 }
2793                               if (!solv->decisionmap[p])
2794                                 queue_push(&dq, p);
2795                             }
2796                         }
2797                     }
2798                   /* install best version */
2799                   if (dq.count)
2800                     {
2801                       olevel = level;
2802                       level = selectandinstall(solv, level, &dq, disablerules, rr - solv->rules);
2803                       if (level == 0)
2804                         {
2805                           queue_free(&dq);
2806                           queue_free(&dqs);
2807                           return;
2808                         }
2809                       if (level <= olevel)
2810                         break;
2811                     }
2812                   /* if still undecided keep package */
2813                   if (solv->decisionmap[i] == 0)
2814                     {
2815                       olevel = level;
2816                       POOL_DEBUG(SAT_DEBUG_POLICY, "keeping %s\n", solvable2str(pool, pool->solvables + i));
2817                       level = setpropagatelearn(solv, level, i, disablerules, r - solv->rules);
2818                       if (level == 0)
2819                         {
2820                           queue_free(&dq);
2821                           queue_free(&dqs);
2822                           return;
2823                         }
2824                       if (level <= olevel)
2825                         break;
2826                     }
2827                 }
2828               if (i < installed->end)
2829                 break;
2830             }
2831           systemlevel = level + 1;
2832           if (pass < 2)
2833             continue;           /* had trouble, retry */
2834         }
2835
2836       if (level < systemlevel)
2837         systemlevel = level;
2838
2839       /*
2840        * decide
2841        */
2842
2843       POOL_DEBUG(SAT_DEBUG_POLICY, "deciding unresolved rules\n");
2844       for (i = 1, n = 1; ; i++, n++)
2845         {
2846           if (n == solv->nrules)
2847             break;
2848           if (i == solv->nrules)
2849             i = 1;
2850           r = solv->rules + i;
2851           if (r->d < 0)         /* ignore disabled rules */
2852             continue;
2853           queue_empty(&dq);
2854           if (r->d == 0)
2855             {
2856               /* binary or unary rule */
2857               /* need two positive undecided literals */
2858               if (r->p < 0 || r->w2 <= 0)
2859                 continue;
2860               if (solv->decisionmap[r->p] || solv->decisionmap[r->w2])
2861                 continue;
2862               queue_push(&dq, r->p);
2863               queue_push(&dq, r->w2);
2864             }
2865           else
2866             {
2867               /* make sure that
2868                * all negative literals are installed
2869                * no positive literal is installed
2870                * i.e. the rule is not fulfilled and we
2871                * just need to decide on the positive literals
2872                */
2873               if (r->p < 0)
2874                 {
2875                   if (solv->decisionmap[-r->p] <= 0)
2876                     continue;
2877                 }
2878               else
2879                 {
2880                   if (solv->decisionmap[r->p] > 0)
2881                     continue;
2882                   if (solv->decisionmap[r->p] == 0)
2883                     queue_push(&dq, r->p);
2884                 }
2885               dp = pool->whatprovidesdata + r->d;
2886               while ((p = *dp++) != 0)
2887                 {
2888                   if (p < 0)
2889                     {
2890                       if (solv->decisionmap[-p] <= 0)
2891                         break;
2892                     }
2893                   else
2894                     {
2895                       if (solv->decisionmap[p] > 0)
2896                         break;
2897                       if (solv->decisionmap[p] == 0)
2898                         queue_push(&dq, p);
2899                     }
2900                 }
2901               if (p)
2902                 continue;
2903             }
2904           IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
2905             {
2906               POOL_DEBUG(SAT_DEBUG_PROPAGATE, "unfulfilled ");
2907               solver_printruleclass(solv, SAT_DEBUG_PROPAGATE, r);
2908             }
2909           /* dq.count < 2 cannot happen as this means that
2910            * the rule is unit */
2911           assert(dq.count > 1);
2912
2913           olevel = level;
2914           level = selectandinstall(solv, level, &dq, disablerules, r - solv->rules);
2915           if (level == 0)
2916             {
2917               queue_free(&dq);
2918               queue_free(&dqs);
2919               return;
2920             }
2921           if (level < systemlevel)
2922             break;
2923           n = 0;
2924         } /* for(), decide */
2925
2926       if (n != solv->nrules)    /* continue if level < systemlevel */
2927         continue;
2928
2929       if (doweak)
2930         {
2931           int qcount;
2932
2933           POOL_DEBUG(SAT_DEBUG_POLICY, "installing recommended packages\n");
2934           queue_empty(&dq);     /* recommended packages */
2935           queue_empty(&dqs);    /* supplemented packages */
2936           for (i = 1; i < pool->nsolvables; i++)
2937             {
2938               if (solv->decisionmap[i] < 0)
2939                 continue;
2940               if (solv->decisionmap[i] > 0)
2941                 {
2942                   /* installed, check for recommends */
2943                   Id *recp, rec, pp, p;
2944                   s = pool->solvables + i;
2945                   if (solv->ignorealreadyrecommended && s->repo == solv->installed)
2946                     continue;
2947                   /* XXX need to special case AND ? */
2948                   if (s->recommends)
2949                     {
2950                       recp = s->repo->idarraydata + s->recommends;
2951                       while ((rec = *recp++) != 0)
2952                         {
2953                           qcount = dq.count;
2954                           FOR_PROVIDES(p, pp, rec)
2955                             {
2956                               if (solv->decisionmap[p] > 0)
2957                                 {
2958                                   dq.count = qcount;
2959                                   break;
2960                                 }
2961                               else if (solv->decisionmap[p] == 0)
2962                                 {
2963                                   queue_pushunique(&dq, p);
2964                                 }
2965                             }
2966                         }
2967                     }
2968                 }
2969               else
2970                 {
2971                   s = pool->solvables + i;
2972                   if (!s->supplements)
2973                     continue;
2974                   if (!pool_installable(pool, s))
2975                     continue;
2976                   if (!solver_is_supplementing(solv, s))
2977                     continue;
2978                   queue_push(&dqs, i);
2979                 }
2980             }
2981
2982           /* filter out all packages obsoleted by installed packages */
2983           /* this is no longer needed if we have reverse obsoletes */
2984           if ((dqs.count || dq.count) && solv->installed)
2985             {
2986               Map obsmap;
2987               Id obs, *obsp, po, ppo;
2988
2989               map_init(&obsmap, pool->nsolvables);
2990               for (p = solv->installed->start; p < solv->installed->end; p++)
2991                 {
2992                   s = pool->solvables + p;
2993                   if (s->repo != solv->installed || !s->obsoletes)
2994                     continue;
2995                   if (solv->decisionmap[p] <= 0)
2996                     continue;
2997                   if (solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p))
2998                     continue;
2999                   obsp = s->repo->idarraydata + s->obsoletes;
3000                   /* foreach obsoletes */
3001                   while ((obs = *obsp++) != 0)
3002                     FOR_PROVIDES(po, ppo, obs)
3003                       MAPSET(&obsmap, po);
3004                 }
3005               for (i = j = 0; i < dqs.count; i++)
3006                 if (!MAPTST(&obsmap, dqs.elements[i]))
3007                   dqs.elements[j++] = dqs.elements[i];
3008               dqs.count = j;
3009               for (i = j = 0; i < dq.count; i++)
3010                 if (!MAPTST(&obsmap, dq.elements[i]))
3011                   dq.elements[j++] = dq.elements[i];
3012               dq.count = j;
3013               map_free(&obsmap);
3014             }
3015
3016           /* filter out all already supplemented packages if requested */
3017           if (solv->ignorealreadyrecommended && dqs.count)
3018             {
3019               /* turn off all new packages */
3020               for (i = 0; i < solv->decisionq.count; i++)
3021                 {
3022                   p = solv->decisionq.elements[i];
3023                   if (p < 0)
3024                     continue;
3025                   s = pool->solvables + p;
3026                   if (s->repo && s->repo != solv->installed)
3027                     solv->decisionmap[p] = -solv->decisionmap[p];
3028                 }
3029               /* filter out old supplements */
3030               for (i = j = 0; i < dqs.count; i++)
3031                 {
3032                   p = dqs.elements[i];
3033                   s = pool->solvables + p;
3034                   if (!s->supplements)
3035                     continue;
3036                   if (!solver_is_supplementing(solv, s))
3037                     dqs.elements[j++] = p;
3038                 }
3039               dqs.count = j;
3040               /* undo turning off */
3041               for (i = 0; i < solv->decisionq.count; i++)
3042                 {
3043                   p = solv->decisionq.elements[i];
3044                   if (p < 0)
3045                     continue;
3046                   s = pool->solvables + p;
3047                   if (s->repo && s->repo != solv->installed)
3048                     solv->decisionmap[p] = -solv->decisionmap[p];
3049                 }
3050             }
3051
3052           /* make dq contain both recommended and supplemented pkgs */
3053           if (dqs.count)
3054             {
3055               for (i = 0; i < dqs.count; i++)
3056                 queue_pushunique(&dq, dqs.elements[i]);
3057             }
3058
3059 #if 1
3060           if (dq.count)
3061             {
3062               Map dqmap;
3063               int decisioncount = solv->decisionq.count;
3064
3065               if (dq.count == 1)
3066                 {
3067                   /* simple case, just one package. no need to choose  */
3068                   p = dq.elements[0];
3069                   if (dqs.count)
3070                     POOL_DEBUG(SAT_DEBUG_POLICY, "installing supplemented %s\n", solvable2str(pool, pool->solvables + p));
3071                   else
3072                     POOL_DEBUG(SAT_DEBUG_POLICY, "installing recommended %s\n", solvable2str(pool, pool->solvables + p));
3073                   queue_push(&solv->recommendations, p);
3074                   level = setpropagatelearn(solv, level, p, 0, 0);
3075                   continue;
3076                 }
3077
3078               /* filter and create a map of result */
3079               policy_filter_unwanted(solv, &dq, POLICY_MODE_RECOMMEND);
3080               map_init(&dqmap, pool->nsolvables);
3081               for (i = 0; i < dq.count; i++)
3082                 MAPSET(&dqmap, dq.elements[i]);
3083
3084               /* install all supplemented packages */
3085               for (i = 0; i < dqs.count; i++)
3086                 {
3087                   p = dqs.elements[i];
3088                   if (solv->decisionmap[p] || !MAPTST(&dqmap, p))
3089                     continue;
3090                   POOL_DEBUG(SAT_DEBUG_POLICY, "installing supplemented %s\n", solvable2str(pool, pool->solvables + p));
3091                   queue_push(&solv->recommendations, p);
3092                   olevel = level;
3093                   level = setpropagatelearn(solv, level, p, 0, 0);
3094                   if (level <= olevel)
3095                     break;
3096                 }
3097               if (i < dqs.count || solv->decisionq.count < decisioncount)
3098                 {
3099                   map_free(&dqmap);
3100                   continue;
3101                 }
3102
3103               /* install all recommended packages */
3104               /* more work as we want to created branches if multiple
3105                * choices are valid */
3106               for (i = 0; i < decisioncount; i++)
3107                 {
3108                   Id rec, *recp, pp;
3109                   p = solv->decisionq.elements[i];
3110                   if (p < 0)
3111                     continue;
3112                   s = pool->solvables + p;
3113                   if (!s->repo || (solv->ignorealreadyrecommended && s->repo == solv->installed))
3114                     continue;
3115                   if (!s->recommends)
3116                     continue;
3117                   recp = s->repo->idarraydata + s->recommends;
3118                   while ((rec = *recp++) != 0)
3119                     {
3120                       queue_empty(&dq);
3121                       FOR_PROVIDES(p, pp, rec)
3122                         {
3123                           if (solv->decisionmap[p] > 0)
3124                             {
3125                               dq.count = 0;
3126                               break;
3127                             }
3128                           else if (solv->decisionmap[p] == 0 && MAPTST(&dqmap, p))
3129                             queue_pushunique(&dq, p);
3130                         }
3131                       if (!dq.count)
3132                         continue;
3133                       if (dq.count > 1)
3134                         {
3135                           /* multiple candidates, open a branch */
3136                           for (i = 1; i < dq.count; i++)
3137                             queue_push(&solv->branches, dq.elements[i]);
3138                           queue_push(&solv->branches, -level);
3139                         }
3140                       p = dq.elements[0];
3141                       POOL_DEBUG(SAT_DEBUG_POLICY, "installing recommended %s\n", solvable2str(pool, pool->solvables + p));
3142                       queue_push(&solv->recommendations, p);
3143                       olevel = level;
3144                       level = setpropagatelearn(solv, level, p, 0, 0);
3145                       if (level <= olevel || solv->decisionq.count < decisioncount)
3146                         break;
3147                     }
3148                   if (rec)
3149                     break;      /* had a problem above, quit loop */
3150                 }
3151               map_free(&dqmap);
3152               continue;
3153             }
3154 #else
3155           if (dq.count)
3156             {
3157               if (dq.count > 1)
3158                 policy_filter_unwanted(solv, &dq, POLICY_MODE_RECOMMEND);
3159               p = dq.elements[0];
3160               /* prefer recommended patterns (bnc#450226) */
3161               /* real fix is to minimize recommended packages as well */
3162               for (i = 0; i < dq.count; i++)
3163                 if (!strncmp(id2str(pool, pool->solvables[dq.elements[i]].name), "pattern:", 8))
3164                   {
3165                     p = dq.elements[i];
3166                     break;
3167                   }
3168               POOL_DEBUG(SAT_DEBUG_POLICY, "installing recommended %s\n", solvable2str(pool, pool->solvables + p));
3169               queue_push(&solv->recommendations, p);
3170               level = setpropagatelearn(solv, level, p, 0, 0);
3171               continue;
3172             }
3173 #endif
3174         }
3175
3176      if (solv->distupgrade && solv->installed)
3177         {
3178           int installedone = 0;
3179
3180           /* let's see if we can install some unsupported package */
3181           POOL_DEBUG(SAT_DEBUG_STATS, "deciding unsupported packages\n");
3182           for (i = 0; i < solv->orphaned.count; i++)
3183             {
3184               p = solv->orphaned.elements[i];
3185               if (solv->decisionmap[p])
3186                 continue;       /* already decided */
3187               olevel = level;
3188               if (solv->distupgrade_removeunsupported)
3189                 {
3190                   POOL_DEBUG(SAT_DEBUG_STATS, "removing unsupported %s\n", solvable2str(pool, pool->solvables + p));
3191                   level = setpropagatelearn(solv, level, -p, 0, 0);
3192                 }
3193               else
3194                 {
3195                   POOL_DEBUG(SAT_DEBUG_STATS, "keeping unsupported %s\n", solvable2str(pool, pool->solvables + p));
3196                   level = setpropagatelearn(solv, level, p, 0, 0);
3197                   installedone = 1;
3198                 }
3199               if (level < olevel)
3200                 break;
3201             }
3202           if (installedone || i < solv->orphaned.count)
3203             continue;
3204         }
3205
3206      if (solv->solution_callback)
3207         {
3208           solv->solution_callback(solv, solv->solution_callback_data);
3209           if (solv->branches.count)
3210             {
3211               int i = solv->branches.count - 1;
3212               int l = -solv->branches.elements[i];
3213               Id why;
3214
3215               for (; i > 0; i--)
3216                 if (solv->branches.elements[i - 1] < 0)
3217                   break;
3218               p = solv->branches.elements[i];
3219               POOL_DEBUG(SAT_DEBUG_STATS, "branching with %s\n", solvable2str(pool, pool->solvables + p));
3220               queue_empty(&dq);
3221               for (j = i + 1; j < solv->branches.count; j++)
3222                 queue_push(&dq, solv->branches.elements[j]);
3223               solv->branches.count = i;
3224               level = l;
3225               revert(solv, level);
3226               if (dq.count > 1)
3227                 for (j = 0; j < dq.count; j++)
3228                   queue_push(&solv->branches, dq.elements[j]);
3229               olevel = level;
3230               why = -solv->decisionq_why.elements[solv->decisionq_why.count];
3231               assert(why >= 0);
3232               level = setpropagatelearn(solv, level, p, disablerules, why);
3233               if (level == 0)
3234                 {
3235                   queue_free(&dq);
3236                   queue_free(&dqs);
3237                   return;
3238                 }
3239               continue;
3240             }
3241           /* all branches done, we're finally finished */
3242           break;
3243         }
3244
3245       /* minimization step */
3246      if (solv->branches.count)
3247         {
3248           int l = 0, lasti = -1, lastl = -1;
3249           Id why;
3250
3251           p = 0;
3252           for (i = solv->branches.count - 1; i >= 0; i--)
3253             {
3254               p = solv->branches.elements[i];
3255               if (p < 0)
3256                 l = -p;
3257               else if (p > 0 && solv->decisionmap[p] > l + 1)
3258                 {
3259                   lasti = i;
3260                   lastl = l;
3261                 }
3262             }
3263           if (lasti >= 0)
3264             {
3265               /* kill old solvable so that we do not loop */
3266               p = solv->branches.elements[lasti];
3267               solv->branches.elements[lasti] = 0;
3268               POOL_DEBUG(SAT_DEBUG_STATS, "minimizing %d -> %d with %s\n", solv->decisionmap[p], lastl, solvable2str(pool, pool->solvables + p));
3269               minimizationsteps++;
3270
3271               level = lastl;
3272               revert(solv, level);
3273               why = -solv->decisionq_why.elements[solv->decisionq_why.count];
3274               assert(why >= 0);
3275               olevel = level;
3276               level = setpropagatelearn(solv, level, p, disablerules, why);
3277               if (level == 0)
3278                 {
3279                   queue_free(&dq);
3280                   queue_free(&dqs);
3281                   return;
3282                 }
3283               continue;
3284             }
3285         }
3286       break;
3287     }
3288   POOL_DEBUG(SAT_DEBUG_STATS, "solver statistics: %d learned rules, %d unsolvable, %d minimization steps\n", solv->stats_learned, solv->stats_unsolvable, minimizationsteps);
3289
3290   POOL_DEBUG(SAT_DEBUG_STATS, "done solving.\n\n");
3291   queue_free(&dq);
3292   queue_free(&dqs);
3293 }
3294
3295
3296 /*-------------------------------------------------------------------
3297  *
3298  * refine_suggestion
3299  *
3300  * at this point, all rules that led to conflicts are disabled.
3301  * we re-enable all rules of a problem set but rule "sug", then
3302  * continue to disable more rules until there as again a solution.
3303  */
3304
3305 /* FIXME: think about conflicting assertions */
3306
3307 static void
3308 refine_suggestion(Solver *solv, Queue *job, Id *problem, Id sug, Queue *refined)
3309 {
3310   Pool *pool = solv->pool;
3311   int i, j;
3312   Id v;
3313   Queue disabled;
3314   int disabledcnt;
3315
3316   IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
3317     {
3318       POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "refine_suggestion start\n");
3319       for (i = 0; problem[i]; i++)
3320         {
3321           if (problem[i] == sug)
3322             POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "=> ");
3323           solver_printproblem(solv, problem[i]);
3324         }
3325     }
3326   queue_init(&disabled);
3327   queue_empty(refined);
3328   queue_push(refined, sug);
3329
3330   /* re-enable all problem rules with the exception of "sug"(gestion) */
3331   revert(solv, 1);
3332   reset_solver(solv);
3333
3334   for (i = 0; problem[i]; i++)
3335     if (problem[i] != sug)
3336       enableproblem(solv, problem[i]);
3337
3338   if (sug < 0)
3339     disableupdaterules(solv, job, -(sug + 1));
3340   else if (sug >= solv->updaterules && sug < solv->updaterules_end)
3341     {
3342       /* enable feature rule */
3343       Rule *r = solv->rules + solv->featurerules + (sug - solv->updaterules);
3344       if (r->p)
3345         enablerule(solv, r);
3346     }
3347
3348   enableweakrules(solv);
3349
3350   for (;;)
3351     {
3352       int njob, nfeature, nupdate;
3353       queue_empty(&solv->problems);
3354       revert(solv, 1);          /* XXX no longer needed? */
3355       reset_solver(solv);
3356
3357       if (!solv->problems.count)
3358         run_solver(solv, 0, 0);
3359
3360       if (!solv->problems.count)
3361         {
3362           POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "no more problems!\n");
3363           IF_POOLDEBUG (SAT_DEBUG_SCHUBI)
3364             solver_printdecisions(solv);
3365           break;                /* great, no more problems */
3366         }
3367       disabledcnt = disabled.count;
3368       /* start with 1 to skip over proof index */
3369       njob = nfeature = nupdate = 0;
3370       for (i = 1; i < solv->problems.count - 1; i++)
3371         {
3372           /* ignore solutions in refined */
3373           v = solv->problems.elements[i];
3374           if (v == 0)
3375             break;      /* end of problem reached */
3376           for (j = 0; problem[j]; j++)
3377             if (problem[j] != sug && problem[j] == v)
3378               break;
3379           if (problem[j])
3380             continue;
3381           if (v >= solv->featurerules && v < solv->featurerules_end)
3382             nfeature++;
3383           else if (v > 0)
3384             nupdate++;
3385           else
3386             {
3387               if ((job->elements[-v -1] & SOLVER_ESSENTIAL) != 0)
3388                 continue;       /* not that one! */
3389               njob++;
3390             }
3391           queue_push(&disabled, v);
3392         }
3393       if (disabled.count == disabledcnt)
3394         {
3395           /* no solution found, this was an invalid suggestion! */
3396           POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "no solution found!\n");
3397           refined->count = 0;
3398           break;
3399         }
3400       if (!njob && nupdate && nfeature)
3401         {
3402           /* got only update rules, filter out feature rules */
3403           POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "throwing away feature rules\n");
3404           for (i = j = disabledcnt; i < disabled.count; i++)
3405             {
3406               v = disabled.elements[i];
3407               if (v < solv->featurerules || v >= solv->featurerules_end)
3408                 disabled.elements[j++] = v;
3409             }
3410           disabled.count = j;
3411           nfeature = 0;
3412         }
3413       if (disabled.count == disabledcnt + 1)
3414         {
3415           /* just one suggestion, add it to refined list */
3416           v = disabled.elements[disabledcnt];
3417           if (!nfeature)
3418             queue_push(refined, v);     /* do not record feature rules */
3419           disableproblem(solv, v);
3420           if (v >= solv->updaterules && v < solv->updaterules_end)
3421             {
3422               Rule *r = solv->rules + (v - solv->updaterules + solv->featurerules);
3423               if (r->p)
3424                 enablerule(solv, r);    /* enable corresponding feature rule */
3425             }
3426           if (v < 0)
3427             disableupdaterules(solv, job, -(v + 1));
3428         }
3429       else
3430         {
3431           /* more than one solution, disable all */
3432           /* do not push anything on refine list, as we do not know which solution to choose */
3433           /* thus, the user will get another problem if he selects this solution, where he
3434            * can choose the right one */
3435           IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
3436             {
3437               POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "more than one solution found:\n");
3438               for (i = disabledcnt; i < disabled.count; i++)
3439                 solver_printproblem(solv, disabled.elements[i]);
3440             }
3441           for (i = disabledcnt; i < disabled.count; i++)
3442             {
3443               v = disabled.elements[i];
3444               disableproblem(solv, v);
3445               if (v >= solv->updaterules && v < solv->updaterules_end)
3446                 {
3447                   Rule *r = solv->rules + (v - solv->updaterules + solv->featurerules);
3448                   if (r->p)
3449                     enablerule(solv, r);
3450                 }
3451             }
3452         }
3453     }
3454   /* all done, get us back into the same state as before */
3455   /* enable refined rules again */
3456   for (i = 0; i < disabled.count; i++)
3457     enableproblem(solv, disabled.elements[i]);
3458   queue_free(&disabled);
3459   /* disable problem rules again */
3460
3461   /* FIXME! */
3462   for (i = 0; problem[i]; i++)
3463     enableproblem(solv, problem[i]);
3464   disableupdaterules(solv, job, -1);
3465
3466   /* disable problem rules again */
3467   for (i = 0; problem[i]; i++)
3468     disableproblem(solv, problem[i]);
3469   POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "refine_suggestion end\n");
3470 }
3471
3472
3473 /*-------------------------------------------------------------------
3474  * sorting helper for problems
3475  *
3476  * bring update rules before job rules
3477  * make essential job rules last
3478  */
3479
3480 Queue *problems_sort_data;
3481
3482 static int
3483 problems_sortcmp(const void *ap, const void *bp)
3484 {
3485   Id a = *(Id *)ap, b = *(Id *)bp;
3486   if (a < 0 && b > 0)
3487     return 1;
3488   if (a > 0 && b < 0)
3489     return -1;
3490   if (a < 0 && b < 0)
3491     {
3492       Queue *job = problems_sort_data;
3493       int af = job->elements[-a - 1] & SOLVER_ESSENTIAL;
3494       int bf = job->elements[-b - 1] & SOLVER_ESSENTIAL;
3495       int x = af - bf;
3496       if (x)
3497         return x;
3498     }
3499   return a - b;
3500 }
3501
3502
3503 /*-------------------------------------------------------------------
3504  * sort problems
3505  */
3506
3507 static void
3508 problems_sort(Solver *solv, Queue *job)
3509 {
3510   int i, j;
3511   if (!solv->problems.count)
3512     return;
3513   for (i = j = 1; i < solv->problems.count; i++)
3514     {
3515       if (!solv->problems.elements[i])
3516         {
3517           if (i > j + 1)
3518             {
3519               problems_sort_data = job;
3520               qsort(solv->problems.elements + j, i - j, sizeof(Id), problems_sortcmp);
3521             }
3522           if (++i == solv->problems.count)
3523             break;
3524           j = i + 1;
3525         }
3526     }
3527 }
3528
3529
3530 /*-------------------------------------------------------------------
3531  * convert problems to solutions
3532  */
3533
3534 static void
3535 problems_to_solutions(Solver *solv, Queue *job)
3536 {
3537   Pool *pool = solv->pool;
3538   Queue problems;
3539   Queue solution;
3540   Queue solutions;
3541   Id *problem;
3542   Id why;
3543   int i, j, nsol, probsolved;
3544   unsigned int now, refnow;
3545
3546   if (!solv->problems.count)
3547     return;
3548   now = sat_timems(0);
3549   problems_sort(solv, job);
3550   queue_clone(&problems, &solv->problems);
3551   queue_init(&solution);
3552   queue_init(&solutions);
3553   /* copy over proof index */
3554   queue_push(&solutions, problems.elements[0]);
3555   problem = problems.elements + 1;
3556   probsolved = 0;
3557   refnow = sat_timems(0);
3558   for (i = 1; i < problems.count; i++)
3559     {
3560       Id v = problems.elements[i];
3561       if (v == 0)
3562         {
3563           /* mark end of this problem */
3564           queue_push(&solutions, 0);
3565           queue_push(&solutions, 0);
3566           POOL_DEBUG(SAT_DEBUG_STATS, "refining took %d ms\n", sat_timems(refnow));
3567           if (i + 1 == problems.count)
3568             break;
3569           /* copy over proof of next problem */
3570           queue_push(&solutions, problems.elements[i + 1]);
3571           i++;
3572           problem = problems.elements + i + 1;
3573           refnow = sat_timems(0);
3574           probsolved = 0;
3575           continue;
3576         }
3577       if (v < 0 && (job->elements[-v - 1] & SOLVER_ESSENTIAL))
3578         {
3579           /* essential job, skip if we already have a non-essential
3580              solution */
3581           if (probsolved > 0)
3582             continue;
3583           probsolved = -1;      /* show all solutions */
3584         }
3585       refine_suggestion(solv, job, problem, v, &solution);
3586       if (!solution.count)
3587         continue;       /* this solution didn't work out */
3588
3589       nsol = 0;
3590       for (j = 0; j < solution.count; j++)
3591         {
3592           why = solution.elements[j];
3593           /* must be either job descriptor or update rule */
3594 #if 0
3595           solver_printproblem(solv, why);
3596 #endif
3597           if (why < 0)
3598             {
3599               /* job descriptor */
3600               queue_push(&solutions, 0);
3601               queue_push(&solutions, -why);
3602             }
3603           else if (why >= solv->infarchrules && why < solv->infarchrules_end)
3604             {
3605               Id p, name;
3606               /* infarch rule, find replacement */
3607               assert(solv->rules[why].p < 0);
3608               name = pool->solvables[-solv->rules[why].p].name;
3609               while (why >= solv->infarchrules && pool->solvables[-solv->rules[why - 1].p].name == name)
3610                 why--;
3611               p = 0;
3612               for (; why < solv->infarchrules_end && pool->solvables[-solv->rules[why].p].name == name; why++)
3613                 if (solv->decisionmap[-solv->rules[why].p] > 0)
3614                   {
3615                     p = -solv->rules[why].p;
3616                     break;
3617                   }
3618               if (!p)
3619                 p = -solv->rules[why].p; /* XXX: what to do here? */
3620               queue_push(&solutions, SOLVER_SOLUTION_INFARCH);
3621               queue_push(&solutions, p);
3622             }
3623           else if (why >= solv->duprules && why < solv->duprules_end)
3624             {
3625               Id p, name;
3626               /* dist upgrade rule, find replacement */
3627               assert(solv->rules[why].p < 0);
3628               name = pool->solvables[-solv->rules[why].p].name;
3629               while (why >= solv->infarchrules && pool->solvables[-solv->rules[why - 1].p].name == name)
3630                 why--;
3631               p = 0;
3632               for (; why < solv->infarchrules_end && pool->solvables[-solv->rules[why].p].name == name; why++)
3633                 if (solv->decisionmap[-solv->rules[why].p] > 0)
3634                   {
3635                     p = -solv->rules[why].p;
3636                     break;
3637                   }
3638               if (!p)
3639                 p = -solv->rules[why].p; /* XXX: what to do here? */
3640               queue_push(&solutions, SOLVER_SOLUTION_DISTUPGRADE);
3641               queue_push(&solutions, p);
3642             }
3643           else
3644             {
3645               /* update rule, find replacement package */
3646               Id p, *dp, rp = 0;
3647               Rule *rr;
3648
3649               assert(why >= solv->updaterules && why < solv->updaterules_end);
3650               /* check if this is a false positive, i.e. the update rule is fulfilled */
3651               rr = solv->rules + why;
3652               FOR_RULELITERALS(p, dp, rr)
3653                 if (p > 0 && solv->decisionmap[p] > 0)
3654                   break;
3655               if (p)
3656                 continue;       /* false alarm */
3657
3658               p = solv->installed->start + (why - solv->updaterules);
3659               rr = solv->rules + solv->featurerules + (why - solv->updaterules);
3660               if (!rr->p)
3661                 rr = solv->rules + why;
3662               if (solv->distupgrade && solv->rules[why].p != p && solv->decisionmap[p] > 0)
3663                 {
3664                   /* distupgrade case, allow to keep old package */
3665                   queue_push(&solutions, p);
3666                   queue_push(&solutions, p);
3667                   nsol++;
3668                   continue;
3669                 }
3670               if (solv->decisionmap[p] > 0)
3671                 continue;       /* false alarm, turned out we can keep the package */
3672               if (rr->w2)
3673                 {
3674                   int mvrp = 0;         /* multi-version replacement */
3675                   FOR_RULELITERALS(rp, dp, rr)
3676                     {
3677                       if (rp > 0 && solv->decisionmap[rp] > 0 && pool->solvables[rp].repo != solv->installed)
3678                         {
3679                           mvrp = rp;
3680                           if (!(solv->noobsoletes.size && MAPTST(&solv->noobsoletes, rp)))
3681                             break;
3682                         }
3683                     }
3684                   if (!rp && mvrp)
3685                     {
3686                       /* found only multi-version replacements */
3687                       /* have to split solution into two parts */
3688                       queue_push(&solutions, p);
3689                       queue_push(&solutions, mvrp);
3690                       nsol++;
3691                     }
3692                 }
3693               queue_push(&solutions, p);
3694               queue_push(&solutions, rp);
3695             }
3696           nsol++;
3697         }
3698       /* mark end of this solution */
3699       if (nsol)
3700         {
3701           if (!probsolved)
3702             probsolved = 1;
3703           queue_push(&solutions, 0);
3704           queue_push(&solutions, 0);
3705         }
3706       else
3707         {
3708           POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "Oops, everything was fine?\n");
3709         }
3710     }
3711   queue_free(&solution);
3712   queue_free(&problems);
3713   /* copy queue over to solutions */
3714   queue_free(&solv->problems);
3715   queue_clone(&solv->problems, &solutions);
3716
3717   /* bring solver back into problem state */
3718   revert(solv, 1);              /* XXX move to reset_solver? */
3719   reset_solver(solv);
3720
3721   assert(solv->problems.count == solutions.count);
3722   queue_free(&solutions);
3723   POOL_DEBUG(SAT_DEBUG_STATS, "problems_to_solutions took %d ms\n", sat_timems(now));
3724 }
3725
3726
3727 /*-------------------------------------------------------------------
3728  *
3729  * problem iterator
3730  *
3731  * advance to next problem
3732  */
3733
3734 Id
3735 solver_next_problem(Solver *solv, Id problem)
3736 {
3737   Id *pp;
3738   if (problem == 0)
3739     return solv->problems.count ? 1 : 0;
3740   pp = solv->problems.elements + problem;
3741   while (pp[0] || pp[1])
3742     {
3743       /* solution */
3744       pp += 2;
3745       while (pp[0] || pp[1])
3746         pp += 2;
3747       pp += 2;
3748     }
3749   pp += 2;
3750   problem = pp - solv->problems.elements;
3751   if (problem >= solv->problems.count)
3752     return 0;
3753   return problem + 1;
3754 }
3755
3756
3757 /*-------------------------------------------------------------------
3758  *
3759  * solution iterator
3760  */
3761
3762 Id
3763 solver_next_solution(Solver *solv, Id problem, Id solution)
3764 {
3765   Id *pp;
3766   if (solution == 0)
3767     {
3768       solution = problem;
3769       pp = solv->problems.elements + solution;
3770       return pp[0] || pp[1] ? solution : 0;
3771     }
3772   pp = solv->problems.elements + solution;
3773   while (pp[0] || pp[1])
3774     pp += 2;
3775   pp += 2;
3776   solution = pp - solv->problems.elements;
3777   return pp[0] || pp[1] ? solution : 0;
3778 }
3779
3780
3781 /*-------------------------------------------------------------------
3782  *
3783  * solution element iterator
3784  */
3785
3786 Id
3787 solver_next_solutionelement(Solver *solv, Id problem, Id solution, Id element, Id *p, Id *rp)
3788 {
3789   Id *pp;
3790   element = element ? element + 2 : solution;
3791   pp = solv->problems.elements + element;
3792   if (!(pp[0] || pp[1]))
3793     return 0;
3794   *p = pp[0];
3795   *rp = pp[1];
3796   return element;
3797 }
3798
3799
3800 /*-------------------------------------------------------------------
3801  *
3802  * Retrieve information about a problematic rule
3803  *
3804  * this is basically the reverse of addrpmrulesforsolvable
3805  */
3806
3807 SolverProbleminfo
3808 solver_problemruleinfo(Solver *solv, Queue *job, Id rid, Id *depp, Id *sourcep, Id *targetp)
3809 {
3810   Pool *pool = solv->pool;
3811   Repo *installed = solv->installed;
3812   Rule *r;
3813   Solvable *s;
3814   int dontfix = 0;
3815   Id p, d, w2, pp, req, *reqp, con, *conp, obs, *obsp, *dp;
3816
3817   assert(rid > 0);
3818   if (rid >= solv->infarchrules && rid < solv->infarchrules_end)
3819     {
3820       r = solv->rules + rid;
3821       *depp = r->p < 0 ? pool->solvables[-r->p].name : 0;
3822       *sourcep = 0;
3823       *targetp = 0;
3824       return SOLVER_PROBLEM_INFARCH_RULE;
3825     }
3826   if (rid >= solv->duprules && rid < solv->duprules_end)
3827     {
3828       r = solv->rules + rid;
3829       *depp = r->p < 0 ? pool->solvables[-r->p].name : 0;
3830       *sourcep = 0;
3831       *targetp = 0;
3832       return SOLVER_PROBLEM_DISTUPGRADE_RULE;
3833     }
3834   if (rid >= solv->jobrules && rid < solv->jobrules_end)
3835     {
3836
3837       r = solv->rules + rid;
3838       p = solv->ruletojob.elements[rid - solv->jobrules];
3839       *depp = job->elements[p + 1];
3840       *sourcep = p;
3841       *targetp = job->elements[p];
3842       d = r->d < 0 ? -r->d - 1 : r->d;
3843       if (d == 0 && r->w2 == 0 && r->p == -SYSTEMSOLVABLE && (job->elements[p] & SOLVER_SELECTMASK) != SOLVER_SOLVABLE_ONE_OF)
3844         return SOLVER_PROBLEM_JOB_NOTHING_PROVIDES_DEP;
3845       return SOLVER_PROBLEM_JOB_RULE;
3846     }
3847   if (rid >= solv->updaterules && rid < solv->updaterules_end)
3848     {
3849       *depp = 0;
3850       *sourcep = solv->installed->start + (rid - solv->updaterules);
3851       *targetp = 0;
3852       return SOLVER_PROBLEM_UPDATE_RULE;
3853     }
3854   assert(rid < solv->rpmrules_end);
3855   r = solv->rules + rid;
3856   assert(r->p < 0);
3857   d = r->d < 0 ? -r->d - 1 : r->d;
3858   if (d == 0 && r->w2 == 0)
3859     {
3860       /* a rpm rule assertion */
3861       s = pool->solvables - r->p;
3862       if (installed && !solv->fixsystem && s->repo == installed)
3863         dontfix = 1;
3864       assert(!dontfix); /* dontfix packages never have a neg assertion */
3865       *sourcep = -r->p;
3866       *targetp = 0;
3867       /* see why the package is not installable */
3868       if (s->arch != ARCH_SRC && s->arch != ARCH_NOSRC && !pool_installable(pool, s))
3869         {
3870           *depp = 0;
3871           return SOLVER_PROBLEM_NOT_INSTALLABLE;
3872         }
3873       /* check requires */
3874       if (s->requires)
3875         {
3876           reqp = s->repo->idarraydata + s->requires;
3877           while ((req = *reqp++) != 0)
3878             {
3879               if (req == SOLVABLE_PREREQMARKER)
3880                 continue;
3881               dp = pool->whatprovidesdata + pool_whatprovides(pool, req);
3882               if (*dp == 0)
3883                 break;
3884             }
3885           if (req)
3886             {
3887               *depp = req;
3888               return SOLVER_PROBLEM_NOTHING_PROVIDES_DEP;
3889             }
3890         }
3891       if (!solv->allowselfconflicts && s->conflicts)
3892         {
3893           conp = s->repo->idarraydata + s->conflicts;
3894           while ((con = *conp++) != 0)
3895             FOR_PROVIDES(p, pp, con)
3896               if (p == -r->p)
3897                 {
3898                   *depp = con;
3899                   return SOLVER_PROBLEM_SELF_CONFLICT;
3900                 }
3901         }
3902       /* should never happen */
3903       *depp = 0;
3904       return SOLVER_PROBLEM_RPM_RULE;
3905     }
3906   s = pool->solvables - r->p;
3907   if (installed && !solv->fixsystem && s->repo == installed)
3908     dontfix = 1;
3909   w2 = r->w2;
3910   if (d && pool->whatprovidesdata[d] < 0)
3911     {
3912       /* rule looks like -p|-c|x|x|x..., we only create this for patches with multiversion */
3913       /* reduce it to -p|-c case */
3914       w2 = pool->whatprovidesdata[d];
3915     }
3916   if (d == 0 && w2 < 0)
3917     {
3918       /* a package conflict */
3919       Solvable *s2 = pool->solvables - w2;
3920       int dontfix2 = 0;
3921
3922       if (installed && !solv->fixsystem && s2->repo == installed)
3923         dontfix2 = 1;
3924
3925       /* if both packages have the same name and at least one of them
3926        * is not installed, they conflict */
3927       if (s->name == s2->name && !(installed && s->repo == installed && s2->repo == installed))
3928         {
3929           /* also check noobsoletes map */
3930           if ((s->evr == s2->evr && s->arch == s2->arch) || !solv->noobsoletes.size
3931                 || ((!installed || s->repo != installed) && !MAPTST(&solv->noobsoletes, -r->p))
3932                 || ((!installed || s2->repo != installed) && !MAPTST(&solv->noobsoletes, -w2)))
3933             {
3934               *depp = 0;
3935               *sourcep = -r->p;
3936               *targetp = -w2;
3937               return SOLVER_PROBLEM_SAME_NAME;
3938             }
3939         }
3940
3941       /* check conflicts in both directions */
3942       if (s->conflicts)
3943         {
3944           conp = s->repo->idarraydata + s->conflicts;
3945           while ((con = *conp++) != 0)
3946             {
3947               FOR_PROVIDES(p, pp, con)
3948                 {
3949                   if (dontfix && pool->solvables[p].repo == installed)
3950                     continue;
3951                   if (p != -w2)
3952                     continue;
3953                   *depp = con;
3954                   *sourcep = -r->p;
3955                   *targetp = p;
3956                   return SOLVER_PROBLEM_PACKAGE_CONFLICT;
3957                 }
3958             }
3959         }
3960       if (s2->conflicts)
3961         {
3962           conp = s2->repo->idarraydata + s2->conflicts;
3963           while ((con = *conp++) != 0)
3964             {
3965               FOR_PROVIDES(p, pp, con)
3966                 {
3967                   if (dontfix2 && pool->solvables[p].repo == installed)
3968                     continue;
3969                   if (p != -r->p)
3970                     continue;
3971                   *depp = con;
3972                   *sourcep = -w2;
3973                   *targetp = p;
3974                   return SOLVER_PROBLEM_PACKAGE_CONFLICT;
3975                 }
3976             }
3977         }
3978       /* check obsoletes in both directions */
3979       if ((!installed || s->repo != installed) && s->obsoletes && !(solv->noobsoletes.size && MAPTST(&solv->noobsoletes, -r->p)))
3980         {
3981           obsp = s->repo->idarraydata + s->obsoletes;
3982           while ((obs = *obsp++) != 0)
3983             {
3984               FOR_PROVIDES(p, pp, obs)
3985                 {
3986                   if (p != -w2)
3987                     continue;
3988                   if (!solv->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p, obs))
3989                     continue;
3990                   *depp = obs;
3991                   *sourcep = -r->p;
3992                   *targetp = p;
3993                   return SOLVER_PROBLEM_PACKAGE_OBSOLETES;
3994                 }
3995             }
3996         }
3997       if ((!installed || s2->repo != installed) && s2->obsoletes && !(solv->noobsoletes.size && MAPTST(&solv->noobsoletes, -w2)))
3998         {
3999           obsp = s2->repo->idarraydata + s2->obsoletes;
4000           while ((obs = *obsp++) != 0)
4001             {
4002               FOR_PROVIDES(p, pp, obs)
4003                 {
4004                   if (p != -r->p)
4005                     continue;
4006                   if (!solv->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p, obs))
4007                     continue;
4008                   *depp = obs;
4009                   *sourcep = -w2;
4010                   *targetp = p;
4011                   return SOLVER_PROBLEM_PACKAGE_OBSOLETES;
4012                 }
4013             }
4014         }
4015       if (solv->implicitobsoleteusesprovides && (!installed || s->repo != installed) && !(solv->noobsoletes.size && MAPTST(&solv->noobsoletes, -r->p)))
4016         {
4017           FOR_PROVIDES(p, pp, s->name)
4018             {
4019               if (p != -w2)
4020                 continue;
4021               *depp = s->name;
4022               *sourcep = -r->p;
4023               *targetp = p;
4024               return SOLVER_PROBLEM_PACKAGE_OBSOLETES;
4025             }
4026         }
4027       if (solv->implicitobsoleteusesprovides && (!installed || s2->repo != installed) && !(solv->noobsoletes.size && MAPTST(&solv->noobsoletes, -w2)))
4028         {
4029           FOR_PROVIDES(p, pp, s2->name)
4030             {
4031               if (p != -r->p)
4032                 continue;
4033               *depp = s2->name;
4034               *sourcep = -w2;
4035               *targetp = p;
4036               return SOLVER_PROBLEM_PACKAGE_OBSOLETES;
4037             }
4038         }
4039       /* all cases checked, can't happen */
4040       *depp = 0;
4041       *sourcep = -r->p;
4042       *targetp = 0;
4043       return SOLVER_PROBLEM_RPM_RULE;
4044     }
4045   /* simple requires */
4046   if (s->requires)
4047     {
4048       reqp = s->repo->idarraydata + s->requires;
4049       while ((req = *reqp++) != 0)
4050         {
4051           if (req == SOLVABLE_PREREQMARKER)
4052             continue;
4053           dp = pool->whatprovidesdata + pool_whatprovides(pool, req);
4054           if (d == 0)
4055             {
4056               if (*dp == r->w2 && dp[1] == 0)
4057                 break;
4058             }
4059           else if (dp - pool->whatprovidesdata == d)
4060             break;
4061         }
4062       if (req)
4063         {
4064           *depp = req;
4065           *sourcep = -r->p;
4066           *targetp = 0;
4067           return SOLVER_PROBLEM_DEP_PROVIDERS_NOT_INSTALLABLE;
4068         }
4069     }
4070   /* all cases checked, can't happen */
4071   *depp = 0;
4072   *sourcep = -r->p;
4073   *targetp = 0;
4074   return SOLVER_PROBLEM_RPM_RULE;
4075 }
4076
4077
4078 /*-------------------------------------------------------------------
4079  *
4080  * find problem rule
4081  */
4082
4083 static void
4084 findproblemrule_internal(Solver *solv, Id idx, Id *reqrp, Id *conrp, Id *sysrp, Id *jobrp)
4085 {
4086   Id rid, d;
4087   Id lreqr, lconr, lsysr, ljobr;
4088   Rule *r;
4089   int reqassert = 0;
4090
4091   lreqr = lconr = lsysr = ljobr = 0;
4092   while ((rid = solv->learnt_pool.elements[idx++]) != 0)
4093     {
4094       assert(rid > 0);
4095       if (rid >= solv->learntrules)
4096         findproblemrule_internal(solv, solv->learnt_why.elements[rid - solv->learntrules], &lreqr, &lconr, &lsysr, &ljobr);
4097       else if ((rid >= solv->jobrules && rid < solv->jobrules_end) || (rid >= solv->infarchrules && rid < solv->infarchrules_end) || (rid >= solv->duprules && rid < solv->duprules_end))
4098         {
4099           if (!*jobrp)
4100             *jobrp = rid;
4101         }
4102       else if (rid >= solv->updaterules && rid < solv->updaterules_end)
4103         {
4104           if (!*sysrp)
4105             *sysrp = rid;
4106         }
4107       else
4108         {
4109           assert(rid < solv->rpmrules_end);
4110           r = solv->rules + rid;
4111           d = r->d < 0 ? -r->d - 1 : r->d;
4112           if (!d && r->w2 < 0)
4113             {
4114               if (!*conrp)
4115                 *conrp = rid;
4116             }
4117           else
4118             {
4119               if (!d && r->w2 == 0 && !reqassert)
4120                 {
4121                   if (*reqrp > 0 && r->p < -1)
4122                     {
4123                       Id op = -solv->rules[*reqrp].p;
4124                       if (op > 1 && solv->pool->solvables[op].arch != solv->pool->solvables[-r->p].arch)
4125                         continue;       /* different arch, skip */
4126                     }
4127                   /* prefer assertions */
4128                   *reqrp = rid;
4129                   reqassert = 1;
4130                 }
4131               if (!*reqrp)
4132                 *reqrp = rid;
4133               else if (solv->installed && r->p < 0 && solv->pool->solvables[-r->p].repo == solv->installed && !reqassert)
4134                 {
4135                   /* prefer rules of installed packages */
4136                   *reqrp = rid;
4137                 }
4138             }
4139         }
4140     }
4141   if (!*reqrp && lreqr)
4142     *reqrp = lreqr;
4143   if (!*conrp && lconr)
4144     *conrp = lconr;
4145   if (!*jobrp && ljobr)
4146     *jobrp = ljobr;
4147   if (!*sysrp && lsysr)
4148     *sysrp = lsysr;
4149 }
4150
4151
4152 /*-------------------------------------------------------------------
4153  *
4154  * find problem rule
4155  *
4156  * search for a rule that describes the problem to the
4157  * user. A pretty hopeless task, actually. We currently
4158  * prefer simple requires.
4159  */
4160
4161 Id
4162 solver_findproblemrule(Solver *solv, Id problem)
4163 {
4164   Id reqr, conr, sysr, jobr;
4165   Id idx = solv->problems.elements[problem - 1];
4166   reqr = conr = sysr = jobr = 0;
4167   findproblemrule_internal(solv, idx, &reqr, &conr, &sysr, &jobr);
4168   if (reqr)
4169     return reqr;
4170   if (conr)
4171     return conr;
4172   if (sysr)
4173     return sysr;
4174   if (jobr)
4175     return jobr;
4176   assert(0);
4177 }
4178
4179 static void
4180 findallproblemrules_internal(Solver *solv, Id idx, Queue *rules)
4181 {
4182   Id rid;
4183   while ((rid = solv->learnt_pool.elements[idx++]) != 0)
4184     {
4185       if (rid >= solv->learntrules)
4186         {
4187           findallproblemrules_internal(solv, solv->learnt_why.elements[rid - solv->learntrules], rules);
4188           continue;
4189         }
4190       queue_pushunique(rules, rid);
4191     }
4192 }
4193
4194 void
4195 solver_findallproblemrules(Solver *solv, Id problem, Queue *rules)
4196 {
4197   queue_empty(rules);
4198   findallproblemrules_internal(solv, solv->problems.elements[problem - 1], rules);
4199 }
4200
4201
4202 /*-------------------------------------------------------------------
4203  *
4204  * create reverse obsoletes map for installed solvables
4205  *
4206  * for each installed solvable find which packages with *different* names
4207  * obsolete the solvable.
4208  * this index is used in policy_findupdatepackages if noupdateprovide is set.
4209  */
4210
4211 static void
4212 create_obsolete_index(Solver *solv)
4213 {
4214   Pool *pool = solv->pool;
4215   Solvable *s;
4216   Repo *installed = solv->installed;
4217   Id p, pp, obs, *obsp, *obsoletes, *obsoletes_data;
4218   int i, n;
4219
4220   if (!installed || !installed->nsolvables)
4221     return;
4222   solv->obsoletes = obsoletes = sat_calloc(installed->end - installed->start, sizeof(Id));
4223   for (i = 1; i < pool->nsolvables; i++)
4224     {
4225       s = pool->solvables + i;
4226       if (!s->obsoletes)
4227         continue;
4228       if (!pool_installable(pool, s))
4229         continue;
4230       obsp = s->repo->idarraydata + s->obsoletes;
4231       while ((obs = *obsp++) != 0)
4232         {
4233           FOR_PROVIDES(p, pp, obs)
4234             {
4235               if (pool->solvables[p].repo != installed)
4236                 continue;
4237               if (pool->solvables[p].name == s->name)
4238                 continue;
4239               if (!solv->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p, obs))
4240                 continue;
4241               obsoletes[p - installed->start]++;
4242             }
4243         }
4244     }
4245   n = 0;
4246   for (i = 0; i < installed->nsolvables; i++)
4247     if (obsoletes[i])
4248       {
4249         n += obsoletes[i] + 1;
4250         obsoletes[i] = n;
4251       }
4252   solv->obsoletes_data = obsoletes_data = sat_calloc(n + 1, sizeof(Id));
4253   POOL_DEBUG(SAT_DEBUG_STATS, "obsoletes data: %d entries\n", n + 1);
4254   for (i = pool->nsolvables - 1; i > 0; i--)
4255     {
4256       s = pool->solvables + i;
4257       if (!s->obsoletes)
4258         continue;
4259       if (!pool_installable(pool, s))
4260         continue;
4261       obsp = s->repo->idarraydata + s->obsoletes;
4262       while ((obs = *obsp++) != 0)
4263         {
4264           FOR_PROVIDES(p, pp, obs)
4265             {
4266               if (pool->solvables[p].repo != installed)
4267                 continue;
4268               if (pool->solvables[p].name == s->name)
4269                 continue;
4270               if (!solv->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p, obs))
4271                 continue;
4272               p -= installed->start;
4273               if (obsoletes_data[obsoletes[p]] != i)
4274                 obsoletes_data[--obsoletes[p]] = i;
4275             }
4276         }
4277     }
4278 }
4279
4280
4281 /*-------------------------------------------------------------------
4282  *
4283  * remove disabled conflicts
4284  */
4285
4286 static void
4287 removedisabledconflicts(Solver *solv, Queue *removed)
4288 {
4289   Pool *pool = solv->pool;
4290   int i, n;
4291   Id p, why, *dp;
4292   Id new;
4293   Rule *r;
4294   Id *decisionmap = solv->decisionmap;
4295
4296   POOL_DEBUG(SAT_DEBUG_SCHUBI, "removedisabledconflicts\n");
4297   queue_empty(removed);
4298   for (i = 0; i < solv->decisionq.count; i++)
4299     {
4300       p = solv->decisionq.elements[i];
4301       if (p > 0)
4302         continue;
4303       /* a conflict. we never do conflicts on free decisions, so there
4304        * must have been an unit rule */
4305       why = solv->decisionq_why.elements[i];
4306       assert(why > 0);
4307       r = solv->rules + why;
4308       if (r->d < 0 && decisionmap[-p])
4309         {
4310           /* rule is now disabled, remove from decisionmap */
4311           POOL_DEBUG(SAT_DEBUG_SCHUBI, "removing conflict for package %s[%d]\n", solvable2str(pool, pool->solvables - p), -p);
4312           queue_push(removed, -p);
4313           queue_push(removed, decisionmap[-p]);
4314           decisionmap[-p] = 0;
4315         }
4316     }
4317   if (!removed->count)
4318     return;
4319   /* we removed some confliced packages. some of them might still
4320    * be in conflict, so search for unit rules and re-conflict */
4321   new = 0;
4322   for (i = n = 1, r = solv->rules + i; n < solv->nrules; i++, r++, n++)
4323     {
4324       if (i == solv->nrules)
4325         {
4326           i = 1;
4327           r = solv->rules + i;
4328         }
4329       if (r->d < 0)
4330         continue;
4331       if (!r->w2)
4332         {
4333           if (r->p < 0 && !decisionmap[-r->p])
4334             new = r->p;
4335         }
4336       else if (!r->d)
4337         {
4338           /* binary rule */
4339           if (r->p < 0 && decisionmap[-r->p] == 0 && DECISIONMAP_FALSE(r->w2))
4340             new = r->p;
4341           else if (r->w2 < 0 && decisionmap[-r->w2] == 0 && DECISIONMAP_FALSE(r->p))
4342             new = r->w2;
4343         }
4344       else
4345         {
4346           if (r->p < 0 && decisionmap[-r->p] == 0)
4347             new = r->p;
4348           if (new || DECISIONMAP_FALSE(r->p))
4349             {
4350               dp = pool->whatprovidesdata + r->d;
4351               while ((p = *dp++) != 0)
4352                 {
4353                   if (new && p == new)
4354                     continue;
4355                   if (p < 0 && decisionmap[-p] == 0)
4356                     {
4357                       if (new)
4358                         {
4359                           new = 0;
4360                           break;
4361                         }
4362                       new = p;
4363                     }
4364                   else if (!DECISIONMAP_FALSE(p))
4365                     {
4366                       new = 0;
4367                       break;
4368                     }
4369                 }
4370             }
4371         }
4372       if (new)
4373         {
4374           POOL_DEBUG(SAT_DEBUG_SCHUBI, "re-conflicting package %s[%d]\n", solvable2str(pool, pool->solvables - new), -new);
4375           decisionmap[-new] = -1;
4376           new = 0;
4377           n = 0;        /* redo all rules */
4378         }
4379     }
4380 }
4381
4382
4383 /*-------------------------------------------------------------------
4384  *
4385  * weaken solvable dependencies
4386  */
4387
4388 static void
4389 weaken_solvable_deps(Solver *solv, Id p)
4390 {
4391   int i;
4392   Rule *r;
4393
4394   for (i = 1, r = solv->rules + i; i < solv->rpmrules_end; i++, r++)
4395     {
4396       if (r->p != -p)
4397         continue;
4398       if ((r->d == 0 || r->d == -1) && r->w2 < 0)
4399         continue;       /* conflict */
4400       queue_push(&solv->weakruleq, i);
4401     }
4402 }
4403
4404 /********************************************************************/
4405 /* main() */
4406
4407
4408 static void
4409 addinfarchrules(Solver *solv, Map *addedmap)
4410 {
4411   Pool *pool = solv->pool;
4412   int first, i, j;
4413   Id p, pp, a, aa, bestarch;
4414   Solvable *s, *ps, *bests;
4415   Queue badq, allowedarchs;
4416
4417   queue_init(&badq);
4418   queue_init(&allowedarchs);
4419   solv->infarchrules = solv->nrules;
4420   for (i = 1; i < pool->nsolvables; i++)
4421     {
4422       if (i == SYSTEMSOLVABLE || !MAPTST(addedmap, i))
4423         continue;
4424       s = pool->solvables + i;
4425       first = i;
4426       bestarch = 0;
4427       bests = 0;
4428       queue_empty(&allowedarchs);
4429       FOR_PROVIDES(p, pp, s->name)
4430         {
4431           ps = pool->solvables + p;
4432           if (ps->name != s->name || !MAPTST(addedmap, p))
4433             continue;
4434           if (p == i)
4435             first = 0;
4436           if (first)
4437             break;
4438           a = ps->arch;
4439           a = (a <= pool->lastarch) ? pool->id2arch[a] : 0;
4440           if (a != 1 && pool->installed && ps->repo == pool->installed && !solv->distupgrade)
4441             {
4442               queue_pushunique(&allowedarchs, ps->arch);        /* also ok to keep this architecture */
4443               continue;         /* ignore installed solvables when calculating the best arch */
4444             }
4445           if (a && a != 1 && (!bestarch || a < bestarch))
4446             {
4447               bestarch = a;
4448               bests = ps;
4449             }
4450         }
4451       if (first)
4452         continue;
4453       /* speed up common case where installed package already has best arch */
4454       if (allowedarchs.count == 1 && bests && allowedarchs.elements[0] == bests->arch)
4455         allowedarchs.count--;   /* installed arch is best */
4456       queue_empty(&badq);
4457       FOR_PROVIDES(p, pp, s->name)
4458         {
4459           ps = pool->solvables + p;
4460           if (ps->name != s->name || !MAPTST(addedmap, p))
4461             continue;
4462           a = ps->arch;
4463           a = (a <= pool->lastarch) ? pool->id2arch[a] : 0;
4464           if (a != 1 && bestarch && ((a ^ bestarch) & 0xffff0000) != 0)
4465             {
4466               for (j = 0; j < allowedarchs.count; j++)
4467                 {
4468                   aa = allowedarchs.elements[j];
4469                   if (ps->arch == aa)
4470                     break;
4471                   aa = (aa <= pool->lastarch) ? pool->id2arch[aa] : 0;
4472                   if (aa && ((a ^ aa) & 0xffff0000) == 0)
4473                     break;      /* compatible */
4474                 }
4475               if (j == allowedarchs.count)
4476                 queue_push(&badq, p);
4477             }
4478         }
4479       if (!badq.count)
4480         continue;
4481       /* block all solvables in the badq! */
4482       for (j = 0; j < badq.count; j++)
4483         {
4484           p = badq.elements[j];
4485           addrule(solv, -p, 0);
4486         }
4487     }
4488   queue_free(&badq);
4489   queue_free(&allowedarchs);
4490   solv->infarchrules_end = solv->nrules;
4491 }
4492
4493 static void
4494 createdupmaps(Solver *solv, Queue *job)
4495 {
4496   Pool *pool = solv->pool;
4497   Repo *repo;
4498   Id how, what, p, pi, pp, obs, *obsp;
4499   Solvable *s, *ps;
4500   int i;
4501
4502   map_init(&solv->dupmap, pool->nsolvables);
4503   map_init(&solv->dupinvolvedmap, pool->nsolvables);
4504   for (i = 0; i < job->count; i += 2)
4505     {
4506       how = job->elements[i];
4507       what = job->elements[i + 1];
4508       switch (how & SOLVER_JOBMASK)
4509         {
4510         case SOLVER_DISTUPGRADE:
4511           if (what < 0 || what > pool->nrepos)
4512             break;
4513           repo = pool->repos[what];
4514           FOR_REPO_SOLVABLES(repo, p, s)
4515             {
4516               MAPSET(&solv->dupmap, p);
4517               FOR_PROVIDES(pi, pp, s->name)
4518                 {
4519                   ps = pool->solvables + pi;
4520                   if (ps->name != s->name)
4521                     continue;
4522                   MAPSET(&solv->dupinvolvedmap, pi);
4523                 }
4524               if (s->obsoletes)
4525                 {
4526                   /* FIXME: check obsoletes/provides combination */
4527                   obsp = s->repo->idarraydata + s->obsoletes;
4528                   while ((obs = *obsp++) != 0)
4529                     {
4530                       FOR_PROVIDES(pi, pp, obs)
4531                         {
4532                           if (!solv->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + pi, obs))
4533                             continue;
4534                           MAPSET(&solv->dupinvolvedmap, pi);
4535                         }
4536                     }
4537                 }
4538             }
4539           break;
4540         default:
4541           break;
4542         }
4543     }
4544   MAPCLR(&solv->dupinvolvedmap, SYSTEMSOLVABLE);
4545 }
4546
4547 static void
4548 freedupmaps(Solver *solv)
4549 {
4550   map_free(&solv->dupmap);
4551   map_free(&solv->dupinvolvedmap);
4552 }
4553
4554 static void
4555 addduprules(Solver *solv, Map *addedmap)
4556 {
4557   Pool *pool = solv->pool;
4558   Id p, pp;
4559   Solvable *s, *ps;
4560   int first, i;
4561
4562   solv->duprules = solv->nrules;
4563   for (i = 1; i < pool->nsolvables; i++)
4564     {
4565       if (i == SYSTEMSOLVABLE || !MAPTST(addedmap, i))
4566         continue;
4567       s = pool->solvables + i;
4568       first = i;
4569       FOR_PROVIDES(p, pp, s->name)
4570         {
4571           ps = pool->solvables + p;
4572           if (ps->name != s->name || !MAPTST(addedmap, p))
4573             continue;
4574           if (p == i)
4575             first = 0;
4576           if (first)
4577             break;
4578           if (!MAPTST(&solv->dupinvolvedmap, p))
4579             continue;
4580           if (solv->installed && ps->repo == solv->installed)
4581             {
4582               if (!solv->updatemap.size)
4583                 map_init(&solv->updatemap, pool->nsolvables);
4584               MAPSET(&solv->updatemap, p);
4585               if (!MAPTST(&solv->dupmap, p))
4586                 {
4587                   Id ip, ipp;
4588                   /* is installed identical to a good one? */
4589                   FOR_PROVIDES(ip, ipp, s->name)
4590                     {
4591                       Solvable *is = pool->solvables + ip;
4592                       if (!MAPTST(&solv->dupmap, ip))
4593                         continue;
4594                       if (is->evr == s->evr && solvable_identical(s, is))
4595                         break;
4596                     }
4597                   if (!ip)
4598                     addrule(solv, -p, 0);       /* no match, sorry */
4599                 }
4600             }
4601           else if (!MAPTST(&solv->dupmap, p))
4602             addrule(solv, -p, 0);
4603         }
4604     }
4605   solv->duprules_end = solv->nrules;
4606 }
4607
4608 /*
4609  *
4610  * solve job queue
4611  *
4612  */
4613
4614 void
4615 solver_solve(Solver *solv, Queue *job)
4616 {
4617   Pool *pool = solv->pool;
4618   Repo *installed = solv->installed;
4619   int i;
4620   int oldnrules;
4621   Map addedmap;                /* '1' == have rpm-rules for solvable */
4622   Map installcandidatemap;
4623   Id how, what, select, name, weak, p, pp, d;
4624   Queue q, redoq;
4625   Solvable *s;
4626   int goterase;
4627   Rule *r;
4628   int now, solve_start;
4629   int hasdupjob = 0;
4630
4631   solve_start = sat_timems(0);
4632   POOL_DEBUG(SAT_DEBUG_STATS, "solver started\n");
4633   POOL_DEBUG(SAT_DEBUG_STATS, "fixsystem=%d updatesystem=%d dosplitprovides=%d, noupdateprovide=%d\n", solv->fixsystem, solv->updatesystem, solv->dosplitprovides, solv->noupdateprovide);
4634   POOL_DEBUG(SAT_DEBUG_STATS, "distupgrade=%d distupgrade_removeunsupported=%d\n", solv->distupgrade, solv->distupgrade_removeunsupported);
4635   POOL_DEBUG(SAT_DEBUG_STATS, "allowuninstall=%d, allowdowngrade=%d, allowarchchange=%d, allowvendorchange=%d\n", solv->allowuninstall, solv->allowdowngrade, solv->allowarchchange, solv->allowvendorchange);
4636   POOL_DEBUG(SAT_DEBUG_STATS, "promoteepoch=%d, allowvirtualconflicts=%d, allowselfconflicts=%d\n", pool->promoteepoch, solv->allowvirtualconflicts, solv->allowselfconflicts);
4637   POOL_DEBUG(SAT_DEBUG_STATS, "obsoleteusesprovides=%d, implicitobsoleteusesprovides=%d\n", solv->obsoleteusesprovides, solv->implicitobsoleteusesprovides);
4638   POOL_DEBUG(SAT_DEBUG_STATS, "dontinstallrecommended=%d, ignorealreadyrecommended=%d, dontshowinstalledrecommended=%d\n", solv->dontinstallrecommended, solv->ignorealreadyrecommended, solv->dontshowinstalledrecommended);
4639   /* create whatprovides if not already there */
4640   if (!pool->whatprovides)
4641     pool_createwhatprovides(pool);
4642
4643   /* create obsolete index */
4644   create_obsolete_index(solv);
4645
4646   /* remember job */
4647   solv->job = job;
4648
4649   /*
4650    * create basic rule set of all involved packages
4651    * use addedmap bitmap to make sure we don't create rules twice
4652    *
4653    */
4654
4655   /* create noobsolete map if needed */
4656   for (i = 0; i < job->count; i += 2)
4657     {
4658       how = job->elements[i] & ~SOLVER_WEAK;
4659       if ((how & SOLVER_JOBMASK) != SOLVER_NOOBSOLETES)
4660         continue;
4661       what = job->elements[i + 1];
4662       select = how & SOLVER_SELECTMASK;
4663       if (!solv->noobsoletes.size)
4664         map_init(&solv->noobsoletes, pool->nsolvables);
4665       FOR_JOB_SELECT(p, pp, select, what)
4666         MAPSET(&solv->noobsoletes, p);
4667     }
4668
4669   map_init(&addedmap, pool->nsolvables);
4670   map_init(&installcandidatemap, pool->nsolvables);
4671   queue_init(&q);
4672
4673   /*
4674    * always install our system solvable
4675    */
4676   MAPSET(&addedmap, SYSTEMSOLVABLE);
4677   queue_push(&solv->decisionq, SYSTEMSOLVABLE);
4678   queue_push(&solv->decisionq_why, 0);
4679   solv->decisionmap[SYSTEMSOLVABLE] = 1; /* installed at level '1' */
4680
4681   now = sat_timems(0);
4682   /*
4683    * create rules for all package that could be involved with the solving
4684    * so called: rpm rules
4685    *
4686    */
4687   if (installed)
4688     {
4689       oldnrules = solv->nrules;
4690       POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for installed solvables ***\n");
4691       FOR_REPO_SOLVABLES(installed, p, s)
4692         addrpmrulesforsolvable(solv, s, &addedmap);
4693       POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for installed solvables\n", solv->nrules - oldnrules);
4694       POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for updaters of installed solvables ***\n");
4695       oldnrules = solv->nrules;
4696       FOR_REPO_SOLVABLES(installed, p, s)
4697         addrpmrulesforupdaters(solv, s, &addedmap, 1);
4698       POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for updaters of installed solvables\n", solv->nrules - oldnrules);
4699     }
4700
4701   /*
4702    * create rules for all packages involved in the job
4703    * (to be installed or removed)
4704    */
4705
4706   POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for packages involved with a job ***\n");
4707   oldnrules = solv->nrules;
4708   for (i = 0; i < job->count; i += 2)
4709     {
4710       how = job->elements[i];
4711       what = job->elements[i + 1];
4712       select = how & SOLVER_SELECTMASK;
4713
4714       switch (how & SOLVER_JOBMASK)
4715         {
4716         case SOLVER_INSTALL:
4717           FOR_JOB_SELECT(p, pp, select, what)
4718             {
4719               MAPSET(&installcandidatemap, p);
4720               addrpmrulesforsolvable(solv, pool->solvables + p, &addedmap);
4721             }
4722           break;
4723         case SOLVER_DISTUPGRADE:
4724           if (!solv->distupgrade)
4725             hasdupjob = 1;
4726           break;
4727         default:
4728           break;
4729         }
4730     }
4731   POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for packages involved in a job\n", solv->nrules - oldnrules);
4732
4733   POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for recommended/suggested packages ***\n");
4734
4735   oldnrules = solv->nrules;
4736
4737     /*
4738      * add rules for suggests, enhances
4739      */
4740   addrpmrulesforweak(solv, &addedmap);
4741   POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules because of weak dependencies\n", solv->nrules - oldnrules);
4742
4743   IF_POOLDEBUG (SAT_DEBUG_STATS)
4744     {
4745       int possible = 0, installable = 0;
4746       for (i = 1; i < pool->nsolvables; i++)
4747         {
4748           if (pool_installable(pool, pool->solvables + i))
4749             installable++;
4750           if (MAPTST(&addedmap, i))
4751             possible++;
4752         }
4753       POOL_DEBUG(SAT_DEBUG_STATS, "%d of %d installable solvables considered for solving\n", possible, installable);
4754     }
4755
4756   /*
4757    * first pass done, we now have all the rpm rules we need.
4758    * unify existing rules before going over all job rules and
4759    * policy rules.
4760    * at this point the system is always solvable,
4761    * as an empty system (remove all packages) is a valid solution
4762    */
4763
4764   unifyrules(solv);                               /* remove duplicate rpm rules */
4765
4766   solv->rpmrules_end = solv->nrules;              /* mark end of rpm rules */
4767
4768   solv->directdecisions = solv->decisionq.count;
4769   POOL_DEBUG(SAT_DEBUG_STATS, "rpm rule memory usage: %d K\n", solv->nrules * (int)sizeof(Rule) / 1024);
4770   POOL_DEBUG(SAT_DEBUG_STATS, "decisions so far: %d\n", solv->decisionq.count);
4771   POOL_DEBUG(SAT_DEBUG_STATS, "rpm rule creation took %d ms\n", sat_timems(now));
4772
4773   /* create dup maps if needed. We need the maps to create our
4774    * update rules */
4775   if (hasdupjob)
4776     createdupmaps(solv, job);
4777
4778   /*
4779    * create feature rules
4780    *
4781    * foreach installed:
4782    *   create assertion (keep installed, if no update available)
4783    *   or
4784    *   create update rule (A|update1(A)|update2(A)|...)
4785    *
4786    * those are used later on to keep a version of the installed packages in
4787    * best effort mode
4788    */
4789
4790   POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** Add feature rules ***\n");
4791   solv->featurerules = solv->nrules;              /* mark start of feature rules */
4792   if (installed)
4793     {
4794         /* foreach possibly installed solvable */
4795       for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
4796         {
4797           if (s->repo != installed)
4798             {
4799               addrule(solv, 0, 0);      /* create dummy rule */
4800               continue;
4801             }
4802           addupdaterule(solv, s, 1);    /* allow s to be updated */
4803         }
4804         /*
4805          * assert one rule per installed solvable,
4806          * either an assertion (A)
4807          * or a possible update (A|update1(A)|update2(A)|...)
4808          */
4809       assert(solv->nrules - solv->featurerules == installed->end - installed->start);
4810     }
4811   solv->featurerules_end = solv->nrules;
4812
4813     /*
4814      * Add update rules for installed solvables
4815      *
4816      * almost identical to feature rules
4817      * except that downgrades/archchanges/vendorchanges are not allowed
4818      */
4819
4820   POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** Add update rules ***\n");
4821   solv->updaterules = solv->nrules;
4822
4823   if (installed)
4824     { /* foreach installed solvables */
4825       /* we create all update rules, but disable some later on depending on the job */
4826       for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
4827         {
4828           Rule *sr;
4829
4830           if (s->repo != installed)
4831             {
4832               addrule(solv, 0, 0);      /* create dummy rule */
4833               continue;
4834             }
4835           addupdaterule(solv, s, 0);    /* allowall = 0: downgrades not allowed */
4836             /*
4837              * check for and remove duplicate
4838              */
4839           r = solv->rules + solv->nrules - 1;           /* r: update rule */
4840           sr = r - (installed->end - installed->start); /* sr: feature rule */
4841           /* it's orphaned if there is no feature rule or the feature rule
4842            * consists just of the installed package */
4843           if (!sr->p || (sr->p == i && !sr->d && !sr->w2))
4844             queue_push(&solv->orphaned, i);
4845           if (!r->p)
4846             {
4847               assert(solv->distupgrade && !sr->p);
4848               continue;
4849             }
4850           unifyrules_sortcmp_data = pool;
4851           if (!unifyrules_sortcmp(r, sr))
4852             {
4853               /* identical rule, kill unneeded one */
4854               if (solv->allowuninstall)
4855                 {
4856                   /* keep feature rule, make it weak */
4857                   memset(r, 0, sizeof(*r));
4858                   queue_push(&solv->weakruleq, sr - solv->rules);
4859                 }
4860               else
4861                 {
4862                   /* keep update rule */
4863                   memset(sr, 0, sizeof(*sr));
4864                 }
4865             }
4866           else if (solv->allowuninstall)
4867             {
4868               /* make both feature and update rule weak */
4869               queue_push(&solv->weakruleq, r - solv->rules);
4870               queue_push(&solv->weakruleq, sr - solv->rules);
4871             }
4872           else
4873             disablerule(solv, sr);
4874         }
4875       /* consistency check: we added a rule for _every_ installed solvable */
4876       assert(solv->nrules - solv->updaterules == installed->end - installed->start);
4877     }
4878   solv->updaterules_end = solv->nrules;
4879
4880
4881   /*
4882    * now add all job rules
4883    */
4884
4885   POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** Add JOB rules ***\n");
4886
4887   solv->jobrules = solv->nrules;
4888   for (i = 0; i < job->count; i += 2)
4889     {
4890       oldnrules = solv->nrules;
4891
4892       how = job->elements[i];
4893       what = job->elements[i + 1];
4894       weak = how & SOLVER_WEAK;
4895       select = how & SOLVER_SELECTMASK;
4896       switch (how & SOLVER_JOBMASK)
4897         {
4898         case SOLVER_INSTALL:
4899           POOL_DEBUG(SAT_DEBUG_JOB, "job: %sinstall %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
4900           if (select == SOLVER_SOLVABLE)
4901             {
4902               p = what;
4903               d = 0;
4904             }
4905           else
4906             {
4907               queue_empty(&q);
4908               FOR_JOB_SELECT(p, pp, select, what)
4909                 queue_push(&q, p);
4910               if (!q.count)
4911                 {
4912                   /* no candidate found, make this an impossible rule */
4913                   queue_push(&q, -SYSTEMSOLVABLE);
4914                 }
4915               p = queue_shift(&q);      /* get first candidate */
4916               d = !q.count ? 0 : pool_queuetowhatprovides(pool, &q);    /* internalize */
4917             }
4918           addrule(solv, p, d);          /* add install rule */
4919           queue_push(&solv->ruletojob, i);
4920           if (weak)
4921             queue_push(&solv->weakruleq, solv->nrules - 1);
4922           break;
4923         case SOLVER_ERASE:
4924           POOL_DEBUG(SAT_DEBUG_JOB, "job: %serase %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
4925           if (select == SOLVER_SOLVABLE && solv->installed && pool->solvables[what].repo == solv->installed)
4926             {
4927               /* special case for "erase a specific solvable": we also
4928                * erase all other solvables with that name, so that they
4929                * don't get picked up as replacement */
4930               name = pool->solvables[what].name;
4931               FOR_PROVIDES(p, pp, name)
4932                 {
4933                   if (p == what)
4934                     continue;
4935                   s = pool->solvables + p;
4936                   if (s->name != name)
4937                     continue;
4938                   /* keep other versions installed */
4939                   if (s->repo == solv->installed)
4940                     continue;
4941                   /* keep installcandidates of other jobs */
4942                   if (MAPTST(&installcandidatemap, p))
4943                     continue;
4944                   addrule(solv, -p, 0);                 /* remove by Id */
4945                   queue_push(&solv->ruletojob, i);
4946                   if (weak)
4947                     queue_push(&solv->weakruleq, solv->nrules - 1);
4948                 }
4949             }
4950           FOR_JOB_SELECT(p, pp, select, what)
4951             {
4952               addrule(solv, -p, 0);
4953               queue_push(&solv->ruletojob, i);
4954               if (weak)
4955                 queue_push(&solv->weakruleq, solv->nrules - 1);
4956             }
4957           break;
4958
4959         case SOLVER_UPDATE:
4960           POOL_DEBUG(SAT_DEBUG_JOB, "job: %supdate %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
4961           FOR_JOB_SELECT(p, pp, select, what)
4962             {
4963               s = pool->solvables + p;
4964               if (!solv->installed || s->repo != solv->installed)
4965                 continue;
4966               if (!solv->updatemap.size)
4967                 map_init(&solv->updatemap, pool->nsolvables);
4968               MAPSET(&solv->updatemap, p);
4969             }
4970           break;
4971         case SOLVER_WEAKENDEPS:
4972           POOL_DEBUG(SAT_DEBUG_JOB, "job: %sweaken deps %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
4973           if (select != SOLVER_SOLVABLE)
4974             break;
4975           s = pool->solvables + what;
4976           weaken_solvable_deps(solv, what);
4977           break;
4978         case SOLVER_NOOBSOLETES:
4979           POOL_DEBUG(SAT_DEBUG_JOB, "job: %sno obsolete %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
4980           break;
4981         case SOLVER_LOCK:
4982           POOL_DEBUG(SAT_DEBUG_JOB, "job: %slock %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
4983           FOR_JOB_SELECT(p, pp, select, what)
4984             {
4985               s = pool->solvables + p;
4986               if (installed && s->repo == installed)
4987                 addrule(solv, p, 0);
4988               else
4989                 addrule(solv, -p, 0);
4990               queue_push(&solv->ruletojob, i);
4991               if (weak)
4992                 queue_push(&solv->weakruleq, solv->nrules - 1);
4993             }
4994           break;
4995         case SOLVER_DISTUPGRADE:
4996           POOL_DEBUG(SAT_DEBUG_JOB, "job: distupgrade repo #%d\n", what);
4997           break;
4998         default:
4999           POOL_DEBUG(SAT_DEBUG_JOB, "job: unknown job\n");
5000           break;
5001         }
5002
5003         /*
5004          * debug
5005          */
5006
5007       IF_POOLDEBUG (SAT_DEBUG_JOB)
5008         {
5009           int j;
5010           if (solv->nrules == oldnrules)
5011             POOL_DEBUG(SAT_DEBUG_JOB, " - no rule created\n");
5012           for (j = oldnrules; j < solv->nrules; j++)
5013             {
5014               POOL_DEBUG(SAT_DEBUG_JOB, " - job ");
5015               solver_printrule(solv, SAT_DEBUG_JOB, solv->rules + j);
5016             }
5017         }
5018     }
5019   assert(solv->ruletojob.count == solv->nrules - solv->jobrules);
5020   solv->jobrules_end = solv->nrules;
5021
5022   /* now create infarch and dup rules */
5023   addinfarchrules(solv, &addedmap);
5024   if (hasdupjob)
5025     {
5026       addduprules(solv, &addedmap);
5027       freedupmaps(solv);        /* no longer needed */
5028     }
5029   else
5030     solv->duprules = solv->duprules_end = solv->nrules;
5031
5032     /* all rules created
5033      * --------------------------------------------------------------
5034      * prepare for solving
5035      */
5036
5037   /* free unneeded memory */
5038   map_free(&addedmap);
5039   map_free(&installcandidatemap);
5040   queue_free(&q);
5041
5042   POOL_DEBUG(SAT_DEBUG_STATS, "%d rpm rules, %d job rules, %d infarch rules, %d dup rules\n", solv->rpmrules_end - 1, solv->jobrules_end - solv->jobrules, solv->infarchrules_end - solv->infarchrules, solv->duprules_end - solv->duprules);
5043
5044   /* create weak map */
5045   map_init(&solv->weakrulemap, solv->nrules);
5046   for (i = 0; i < solv->weakruleq.count; i++)
5047     {
5048       p = solv->weakruleq.elements[i];
5049       MAPSET(&solv->weakrulemap, p);
5050     }
5051
5052   /* all new rules are learnt after this point */
5053   solv->learntrules = solv->nrules;
5054
5055   /* create assertion index. it is only used to speed up
5056    * makeruledecsions() a bit */
5057   for (i = 1, r = solv->rules + i; i < solv->nrules; i++, r++)
5058     if (r->p && !r->w2 && (r->d == 0 || r->d == -1))
5059       queue_push(&solv->ruleassertions, i);
5060
5061   /* disable update rules that conflict with our job */
5062   disableupdaterules(solv, job, -1);
5063
5064   /* make decisions based on job/update assertions */
5065   makeruledecisions(solv);
5066
5067   /* create watches chains */
5068   makewatches(solv);
5069
5070   POOL_DEBUG(SAT_DEBUG_STATS, "problems so far: %d\n", solv->problems.count);
5071
5072   /*
5073    * ********************************************
5074    * solve!
5075    * ********************************************
5076    */
5077
5078   now = sat_timems(0);
5079   run_solver(solv, 1, solv->dontinstallrecommended ? 0 : 1);
5080   POOL_DEBUG(SAT_DEBUG_STATS, "solver took %d ms\n", sat_timems(now));
5081
5082   queue_init(&redoq);
5083   goterase = 0;
5084   /* disable all erase jobs (including weak "keep uninstalled" rules) */
5085   for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++)
5086     {
5087       if (r->d < 0)     /* disabled ? */
5088         continue;
5089       if (r->p > 0)     /* install job? */
5090         continue;
5091       disablerule(solv, r);
5092       goterase++;
5093     }
5094
5095   if (goterase)
5096     {
5097       enabledisablelearntrules(solv);
5098       removedisabledconflicts(solv, &redoq);
5099     }
5100
5101   /*
5102    * find recommended packages
5103    */
5104
5105   /* if redoq.count == 0 we already found all recommended in the
5106    * solver run */
5107   if (redoq.count || solv->dontinstallrecommended || !solv->dontshowinstalledrecommended || solv->ignorealreadyrecommended)
5108     {
5109       Id rec, *recp, p, pp;
5110
5111       /* create map of all recommened packages */
5112       solv->recommends_index = -1;
5113       MAPZERO(&solv->recommendsmap);
5114       for (i = 0; i < solv->decisionq.count; i++)
5115         {
5116           p = solv->decisionq.elements[i];
5117           if (p < 0)
5118             continue;
5119           s = pool->solvables + p;
5120           if (s->recommends)
5121             {
5122               recp = s->repo->idarraydata + s->recommends;
5123               while ((rec = *recp++) != 0)
5124                 {
5125                   FOR_PROVIDES(p, pp, rec)
5126                     if (solv->decisionmap[p] > 0)
5127                       break;
5128                   if (p)
5129                     {
5130                       if (!solv->dontshowinstalledrecommended)
5131                         {
5132                           FOR_PROVIDES(p, pp, rec)
5133                             if (solv->decisionmap[p] > 0)
5134                               MAPSET(&solv->recommendsmap, p);
5135                         }
5136                       continue; /* p != 0: already fulfilled */
5137                     }
5138                   FOR_PROVIDES(p, pp, rec)
5139                     MAPSET(&solv->recommendsmap, p);
5140                 }
5141             }
5142         }
5143       for (i = 1; i < pool->nsolvables; i++)
5144         {
5145           if (solv->decisionmap[i] < 0)
5146             continue;
5147           if (solv->decisionmap[i] > 0 && solv->dontshowinstalledrecommended)
5148             continue;
5149           s = pool->solvables + i;
5150           if (!MAPTST(&solv->recommendsmap, i))
5151             {
5152               if (!s->supplements)
5153                 continue;
5154               if (!pool_installable(pool, s))
5155                 continue;
5156               if (!solver_is_supplementing(solv, s))
5157                 continue;
5158             }
5159           if (solv->dontinstallrecommended)
5160             queue_push(&solv->recommendations, i);
5161           else
5162             queue_pushunique(&solv->recommendations, i);
5163         }
5164       /* we use MODE_SUGGEST here so that repo prio is ignored */
5165       policy_filter_unwanted(solv, &solv->recommendations, POLICY_MODE_SUGGEST);
5166     }
5167
5168   /*
5169    * find suggested packages
5170    */
5171
5172   if (1)
5173     {
5174       Id sug, *sugp, p, pp;
5175
5176       /* create map of all suggests that are still open */
5177       solv->recommends_index = -1;
5178       MAPZERO(&solv->suggestsmap);
5179       for (i = 0; i < solv->decisionq.count; i++)
5180         {
5181           p = solv->decisionq.elements[i];
5182           if (p < 0)
5183             continue;
5184           s = pool->solvables + p;
5185           if (s->suggests)
5186             {
5187               sugp = s->repo->idarraydata + s->suggests;
5188               while ((sug = *sugp++) != 0)
5189                 {
5190                   FOR_PROVIDES(p, pp, sug)
5191                     if (solv->decisionmap[p] > 0)
5192                       break;
5193                   if (p)
5194                     {
5195                       if (!solv->dontshowinstalledrecommended)
5196                         {
5197                           FOR_PROVIDES(p, pp, sug)
5198                             if (solv->decisionmap[p] > 0)
5199                               MAPSET(&solv->suggestsmap, p);
5200                         }
5201                       continue; /* already fulfilled */
5202                     }
5203                   FOR_PROVIDES(p, pp, sug)
5204                     MAPSET(&solv->suggestsmap, p);
5205                 }
5206             }
5207         }
5208       for (i = 1; i < pool->nsolvables; i++)
5209         {
5210           if (solv->decisionmap[i] < 0)
5211             continue;
5212           if (solv->decisionmap[i] > 0 && solv->dontshowinstalledrecommended)
5213             continue;
5214           s = pool->solvables + i;
5215           if (!MAPTST(&solv->suggestsmap, i))
5216             {
5217               if (!s->enhances)
5218                 continue;
5219               if (!pool_installable(pool, s))
5220                 continue;
5221               if (!solver_is_enhancing(solv, s))
5222                 continue;
5223             }
5224           queue_push(&solv->suggestions, i);
5225         }
5226       policy_filter_unwanted(solv, &solv->suggestions, POLICY_MODE_SUGGEST);
5227     }
5228
5229   if (redoq.count)
5230     {
5231       /* restore decisionmap */
5232       for (i = 0; i < redoq.count; i += 2)
5233         solv->decisionmap[redoq.elements[i]] = redoq.elements[i + 1];
5234     }
5235
5236     /*
5237      * if unsolvable, prepare solutions
5238      */
5239
5240   if (solv->problems.count)
5241     {
5242       int recocount = solv->recommendations.count;
5243       solv->recommendations.count = 0;  /* so that revert() doesn't mess with it */
5244       queue_empty(&redoq);
5245       for (i = 0; i < solv->decisionq.count; i++)
5246         {
5247           Id p = solv->decisionq.elements[i];
5248           queue_push(&redoq, p);
5249           queue_push(&redoq, solv->decisionq_why.elements[i]);
5250           queue_push(&redoq, solv->decisionmap[p > 0 ? p : -p]);
5251         }
5252       problems_to_solutions(solv, job);
5253       memset(solv->decisionmap, 0, pool->nsolvables * sizeof(Id));
5254       queue_empty(&solv->decisionq);
5255       queue_empty(&solv->decisionq_why);
5256       for (i = 0; i < redoq.count; i += 3)
5257         {
5258           Id p = redoq.elements[i];
5259           queue_push(&solv->decisionq, p);
5260           queue_push(&solv->decisionq_why, redoq.elements[i + 1]);
5261           solv->decisionmap[p > 0 ? p : -p] = redoq.elements[i + 2];
5262         }
5263       solv->recommendations.count = recocount;
5264     }
5265
5266   queue_free(&redoq);
5267   POOL_DEBUG(SAT_DEBUG_STATS, "final solver statistics: %d learned rules, %d unsolvable\n", solv->stats_learned, solv->stats_unsolvable);
5268   POOL_DEBUG(SAT_DEBUG_STATS, "solver_solve took %d ms\n", sat_timems(solve_start));
5269   solv->job = 0;
5270 }
5271
5272 /***********************************************************************/
5273 /* disk usage computations */
5274
5275 /*-------------------------------------------------------------------
5276  *
5277  * calculate DU changes
5278  */
5279
5280 void
5281 solver_calc_duchanges(Solver *solv, DUChanges *mps, int nmps)
5282 {
5283   Map installedmap;
5284
5285   solver_create_state_maps(solv, &installedmap, 0);
5286   pool_calc_duchanges(solv->pool, &installedmap, mps, nmps);
5287   map_free(&installedmap);
5288 }
5289
5290
5291 /*-------------------------------------------------------------------
5292  *
5293  * calculate changes in install size
5294  */
5295
5296 int
5297 solver_calc_installsizechange(Solver *solv)
5298 {
5299   Map installedmap;
5300   int change;
5301
5302   solver_create_state_maps(solv, &installedmap, 0);
5303   change = pool_calc_installsizechange(solv->pool, &installedmap);
5304   map_free(&installedmap);
5305   return change;
5306 }
5307
5308 #define FIND_INVOLVED_DEBUG 0
5309 void
5310 solver_find_involved(Solver *solv, Queue *installedq, Solvable *ts, Queue *q)
5311 {
5312   Pool *pool = solv->pool;
5313   Map im;
5314   Map installedm;
5315   Solvable *s;
5316   Queue iq;
5317   Queue installedq_internal;
5318   Id tp, ip, p, pp, req, *reqp, sup, *supp;
5319   int i, count;
5320
5321   tp = ts - pool->solvables;
5322   queue_init(&iq);
5323   queue_init(&installedq_internal);
5324   map_init(&im, pool->nsolvables);
5325   map_init(&installedm, pool->nsolvables);
5326
5327   if (!installedq)
5328     {
5329       installedq = &installedq_internal;
5330       if (solv->installed)
5331         {
5332           for (ip = solv->installed->start; ip < solv->installed->end; ip++)
5333             {
5334               s = pool->solvables + ip;
5335               if (s->repo != solv->installed)
5336                 continue;
5337               queue_push(installedq, ip);
5338             }
5339         }
5340     }
5341   for (i = 0; i < installedq->count; i++)
5342     {
5343       ip = installedq->elements[i];
5344       MAPSET(&installedm, ip);
5345       MAPSET(&im, ip);
5346     }
5347
5348   queue_push(&iq, ts - pool->solvables);
5349   while (iq.count)
5350     {
5351       ip = queue_shift(&iq);
5352       if (!MAPTST(&im, ip))
5353         continue;
5354       if (!MAPTST(&installedm, ip))
5355         continue;
5356       MAPCLR(&im, ip);
5357       s = pool->solvables + ip;
5358 #if FIND_INVOLVED_DEBUG
5359       printf("hello %s\n", solvable2str(pool, s));
5360 #endif
5361       if (s->requires)
5362         {
5363           reqp = s->repo->idarraydata + s->requires;
5364           while ((req = *reqp++) != 0)
5365             {
5366               if (req == SOLVABLE_PREREQMARKER)
5367                 continue;
5368               /* count number of installed packages that match */
5369               count = 0;
5370               FOR_PROVIDES(p, pp, req)
5371                 if (MAPTST(&installedm, p))
5372                   count++;
5373               if (count > 1)
5374                 continue;
5375               FOR_PROVIDES(p, pp, req)
5376                 {
5377                   if (MAPTST(&im, p))
5378                     {
5379 #if FIND_INVOLVED_DEBUG
5380                       printf("%s requires %s\n", solvable2str(pool, pool->solvables + ip), solvable2str(pool, pool->solvables + p));
5381 #endif
5382                       queue_push(&iq, p);
5383                     }
5384                 }
5385             }
5386         }
5387       if (s->recommends)
5388         {
5389           reqp = s->repo->idarraydata + s->recommends;
5390           while ((req = *reqp++) != 0)
5391             {
5392               count = 0;
5393               FOR_PROVIDES(p, pp, req)
5394                 if (MAPTST(&installedm, p))
5395                   count++;
5396               if (count > 1)
5397                 continue;
5398               FOR_PROVIDES(p, pp, req)
5399                 {
5400                   if (MAPTST(&im, p))
5401                     {
5402 #if FIND_INVOLVED_DEBUG
5403                       printf("%s recommends %s\n", solvable2str(pool, pool->solvables + ip), solvable2str(pool, pool->solvables + p));
5404 #endif
5405                       queue_push(&iq, p);
5406                     }
5407                 }
5408             }
5409         }
5410       if (!iq.count)
5411         {
5412           /* supplements pass */
5413           for (i = 0; i < installedq->count; i++)
5414             {
5415               ip = installedq->elements[i];
5416               s = pool->solvables + ip;
5417               if (!s->supplements)
5418                 continue;
5419               if (!MAPTST(&im, ip))
5420                 continue;
5421               supp = s->repo->idarraydata + s->supplements;
5422               while ((sup = *supp++) != 0)
5423                 if (!dep_possible(solv, sup, &im) && dep_possible(solv, sup, &installedm))
5424                   break;
5425               /* no longer supplemented, also erase */
5426               if (sup)
5427                 {
5428 #if FIND_INVOLVED_DEBUG
5429                   printf("%s supplemented\n", solvable2str(pool, pool->solvables + ip));
5430 #endif
5431                   queue_push(&iq, ip);
5432                 }
5433             }
5434         }
5435     }
5436
5437   for (i = 0; i < installedq->count; i++)
5438     {
5439       ip = installedq->elements[i];
5440       if (MAPTST(&im, ip))
5441         queue_push(&iq, ip);
5442     }
5443
5444   while (iq.count)
5445     {
5446       ip = queue_shift(&iq);
5447       if (!MAPTST(&installedm, ip))
5448         continue;
5449       s = pool->solvables + ip;
5450 #if FIND_INVOLVED_DEBUG
5451       printf("bye %s\n", solvable2str(pool, s));
5452 #endif
5453       if (s->requires)
5454         {
5455           reqp = s->repo->idarraydata + s->requires;
5456           while ((req = *reqp++) != 0)
5457             {
5458               FOR_PROVIDES(p, pp, req)
5459                 {
5460                   if (!MAPTST(&im, p))
5461                     {
5462                       if (p == tp)
5463                         continue;
5464 #if FIND_INVOLVED_DEBUG
5465                       printf("%s requires %s\n", solvable2str(pool, pool->solvables + ip), solvable2str(pool, pool->solvables + p));
5466 #endif
5467                       MAPSET(&im, p);
5468                       queue_push(&iq, p);
5469                     }
5470                 }
5471             }
5472         }
5473       if (s->recommends)
5474         {
5475           reqp = s->repo->idarraydata + s->recommends;
5476           while ((req = *reqp++) != 0)
5477             {
5478               FOR_PROVIDES(p, pp, req)
5479                 {
5480                   if (!MAPTST(&im, p))
5481                     {
5482                       if (p == tp)
5483                         continue;
5484 #if FIND_INVOLVED_DEBUG
5485                       printf("%s recommends %s\n", solvable2str(pool, pool->solvables + ip), solvable2str(pool, pool->solvables + p));
5486 #endif
5487                       MAPSET(&im, p);
5488                       queue_push(&iq, p);
5489                     }
5490                 }
5491             }
5492         }
5493       if (!iq.count)
5494         {
5495           /* supplements pass */
5496           for (i = 0; i < installedq->count; i++)
5497             {
5498               ip = installedq->elements[i];
5499               if (ip == tp)
5500                 continue;
5501               s = pool->solvables + ip;
5502               if (!s->supplements)
5503                 continue;
5504               if (MAPTST(&im, ip))
5505                 continue;
5506               supp = s->repo->idarraydata + s->supplements;
5507               while ((sup = *supp++) != 0)
5508                 if (dep_possible(solv, sup, &im))
5509                   break;
5510               if (sup)
5511                 {
5512 #if FIND_INVOLVED_DEBUG
5513                   printf("%s supplemented\n", solvable2str(pool, pool->solvables + ip));
5514 #endif
5515                   MAPSET(&im, ip);
5516                   queue_push(&iq, ip);
5517                 }
5518             }
5519         }
5520     }
5521
5522   queue_free(&iq);
5523
5524   /* convert map into result */
5525   for (i = 0; i < installedq->count; i++)
5526     {
5527       ip = installedq->elements[i];
5528       if (MAPTST(&im, ip))
5529         continue;
5530       if (ip == ts - pool->solvables)
5531         continue;
5532       queue_push(q, ip);
5533     }
5534   map_free(&im);
5535   map_free(&installedm);
5536   queue_free(&installedq_internal);
5537 }
5538
5539 /* EOF */