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               if (!MAPTST(m, buddy))
1287                 queue_push(&workq, buddy);
1288             }
1289         }
1290
1291       /*-----------------------------------------
1292        * check requires of s
1293        */
1294
1295       if (s->requires)
1296         {
1297           reqp = s->repo->idarraydata + s->requires;
1298           while ((req = *reqp++) != 0)            /* go through all requires */
1299             {
1300               if (req == SOLVABLE_PREREQMARKER)   /* skip the marker */
1301                 continue;
1302
1303               /* find list of solvables providing 'req' */
1304               dp = pool->whatprovidesdata + pool_whatprovides(pool, req);
1305
1306               if (*dp == SYSTEMSOLVABLE)          /* always installed */
1307                 continue;
1308
1309               if (dontfix)
1310                 {
1311                   /* the strategy here is to not insist on dependencies
1312                    * that are already broken. so if we find one provider
1313                    * that was already installed, we know that the
1314                    * dependency was not broken before so we enforce it */
1315
1316                   /* check if any of the providers for 'req' is installed */
1317                   for (i = 0; (p = dp[i]) != 0; i++)
1318                     {
1319                       if (pool->solvables[p].repo == installed)
1320                         break;          /* provider was installed */
1321                     }
1322                   /* didn't find an installed provider: previously broken dependency */
1323                   if (!p)
1324                     {
1325                       POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "ignoring broken requires %s of installed package %s\n", dep2str(pool, req), solvable2str(pool, s));
1326                       continue;
1327                     }
1328                 }
1329
1330               if (!*dp)
1331                 {
1332                   /* nothing provides req! */
1333                   POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "package %s [%d] is not installable (%s)\n", solvable2str(pool, s), (Id)(s - pool->solvables), dep2str(pool, req));
1334                   addrule(solv, -n, 0); /* mark requestor as uninstallable */
1335                   continue;
1336                 }
1337
1338               IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION)
1339                 {
1340                   POOL_DEBUG(SAT_DEBUG_RULE_CREATION,"  %s requires %s\n", solvable2str(pool, s), dep2str(pool, req));
1341                   for (i = 0; dp[i]; i++)
1342                     POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "   provided by %s\n", solvable2str(pool, pool->solvables + dp[i]));
1343                 }
1344
1345               /* add 'requires' dependency */
1346               /* rule: (-requestor|provider1|provider2|...|providerN) */
1347               addrule(solv, -n, dp - pool->whatprovidesdata);
1348
1349               /* descend the dependency tree
1350                  push all non-visited providers on the work queue */
1351               for (; *dp; dp++)
1352                 {
1353                   if (!MAPTST(m, *dp))
1354                     queue_push(&workq, *dp);
1355                 }
1356
1357             } /* while, requirements of n */
1358
1359         } /* if, requirements */
1360
1361       /* that's all we check for src packages */
1362       if (s->arch == ARCH_SRC || s->arch == ARCH_NOSRC)
1363         continue;
1364
1365       /*-----------------------------------------
1366        * check conflicts of s
1367        */
1368
1369       if (s->conflicts)
1370         {
1371           int ispatch = 0;
1372
1373           /* we treat conflicts in patches a bit differen:
1374            * - nevr matching
1375            * - multiversion handling
1376            * XXX: we should really handle this different, looking
1377            * at the name is a bad hack
1378            */
1379           if (!strncmp("patch:", id2str(pool, s->name), 6))
1380             ispatch = 1;
1381           conp = s->repo->idarraydata + s->conflicts;
1382           /* foreach conflicts of 's' */
1383           while ((con = *conp++) != 0)
1384             {
1385               /* foreach providers of a conflict of 's' */
1386               FOR_PROVIDES(p, pp, con)
1387                 {
1388                   if (ispatch && !pool_match_nevr(pool, pool->solvables + p, con))
1389                     continue;
1390                   /* dontfix: dont care about conflicts with already installed packs */
1391                   if (dontfix && pool->solvables[p].repo == installed)
1392                     continue;
1393                   /* p == n: self conflict */
1394                   if (p == n && !solv->allowselfconflicts)
1395                     {
1396                       if (ISRELDEP(con))
1397                         {
1398                           Reldep *rd = GETRELDEP(pool, con);
1399                           if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_OTHERPROVIDERS)
1400                             continue;
1401                         }
1402                       p = 0;    /* make it a negative assertion, aka 'uninstallable' */
1403                     }
1404                   if (p && ispatch && solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p) && ISRELDEP(con))
1405                     {
1406                       /* our patch conflicts with a noobsoletes (aka multiversion) package */
1407                       p = -makemultiversionconflict(solv, p, con);
1408                     }
1409                  /* rule: -n|-p: either solvable _or_ provider of conflict */
1410                   addrule(solv, -n, -p);
1411                 }
1412             }
1413         }
1414
1415       /*-----------------------------------------
1416        * check obsoletes if not installed
1417        * (only installation will trigger the obsoletes in rpm)
1418        */
1419       if (!installed || pool->solvables[n].repo != installed)
1420         {                              /* not installed */
1421           int noobs = solv->noobsoletes.size && MAPTST(&solv->noobsoletes, n);
1422           if (s->obsoletes && !noobs)
1423             {
1424               obsp = s->repo->idarraydata + s->obsoletes;
1425               /* foreach obsoletes */
1426               while ((obs = *obsp++) != 0)
1427                 {
1428                   /* foreach provider of an obsoletes of 's' */
1429                   FOR_PROVIDES(p, pp, obs)
1430                     {
1431                       if (!solv->obsoleteusesprovides /* obsoletes are matched names, not provides */
1432                           && !pool_match_nevr(pool, pool->solvables + p, obs))
1433                         continue;
1434                       addrule(solv, -n, -p);
1435                     }
1436                 }
1437             }
1438           FOR_PROVIDES(p, pp, s->name)
1439             {
1440               Solvable *ps = pool->solvables + p;
1441               /* we still obsolete packages with same nevra, like rpm does */
1442               /* (actually, rpm mixes those packages. yuck...) */
1443               if (noobs && (s->name != ps->name || s->evr != ps->evr || s->arch != ps->arch))
1444                 continue;
1445               if (!solv->implicitobsoleteusesprovides && s->name != ps->name)
1446                 continue;
1447               addrule(solv, -n, -p);
1448             }
1449         }
1450
1451       /*-----------------------------------------
1452        * add recommends to the work queue
1453        */
1454       if (s->recommends)
1455         {
1456           recp = s->repo->idarraydata + s->recommends;
1457           while ((rec = *recp++) != 0)
1458             {
1459               FOR_PROVIDES(p, pp, rec)
1460                 if (!MAPTST(m, p))
1461                   queue_push(&workq, p);
1462             }
1463         }
1464       if (s->suggests)
1465         {
1466           sugp = s->repo->idarraydata + s->suggests;
1467           while ((sug = *sugp++) != 0)
1468             {
1469               FOR_PROVIDES(p, pp, sug)
1470                 if (!MAPTST(m, p))
1471                   queue_push(&workq, p);
1472             }
1473         }
1474     }
1475   queue_free(&workq);
1476   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforsolvable end -----\n");
1477 }
1478
1479
1480 /*-------------------------------------------------------------------
1481  *
1482  * Add package rules for weak rules
1483  *
1484  * m: visited solvables
1485  */
1486
1487 static void
1488 addrpmrulesforweak(Solver *solv, Map *m)
1489 {
1490   Pool *pool = solv->pool;
1491   Solvable *s;
1492   Id sup, *supp;
1493   int i, n;
1494
1495   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforweak -----\n");
1496     /* foreach solvable in pool */
1497   for (i = n = 1; n < pool->nsolvables; i++, n++)
1498     {
1499       if (i == pool->nsolvables)                 /* wrap i */
1500         i = 1;
1501       if (MAPTST(m, i))                          /* been there */
1502         continue;
1503
1504       s = pool->solvables + i;
1505       if (!pool_installable(pool, s))            /* only look at installable ones */
1506         continue;
1507
1508       sup = 0;
1509       if (s->supplements)
1510         {
1511           /* find possible supplements */
1512           supp = s->repo->idarraydata + s->supplements;
1513           while ((sup = *supp++) != ID_NULL)
1514             if (dep_possible(solv, sup, m))
1515               break;
1516         }
1517
1518         /* if nothing found, check for enhances */
1519       if (!sup && s->enhances)
1520         {
1521           supp = s->repo->idarraydata + s->enhances;
1522           while ((sup = *supp++) != ID_NULL)
1523             if (dep_possible(solv, sup, m))
1524               break;
1525         }
1526         /* if nothing found, goto next solvables */
1527       if (!sup)
1528         continue;
1529       addrpmrulesforsolvable(solv, s, m);
1530       n = 0;
1531     }
1532   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforweak end -----\n");
1533 }
1534
1535
1536 /*-------------------------------------------------------------------
1537  *
1538  * add package rules for possible updates
1539  *
1540  * s: solvable
1541  * m: map of already visited solvables
1542  * allow_all: 0 = dont allow downgrades, 1 = allow all candidates
1543  */
1544
1545 static void
1546 addrpmrulesforupdaters(Solver *solv, Solvable *s, Map *m, int allow_all)
1547 {
1548   Pool *pool = solv->pool;
1549   int i;
1550     /* queue and buffer for it */
1551   Queue qs;
1552   Id qsbuf[64];
1553
1554   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforupdaters -----\n");
1555
1556   queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
1557     /* find update candidates for 's' */
1558   policy_findupdatepackages(solv, s, &qs, allow_all);
1559     /* add rule for 's' if not already done */
1560   if (!MAPTST(m, s - pool->solvables))
1561     addrpmrulesforsolvable(solv, s, m);
1562     /* foreach update candidate, add rule if not already done */
1563   for (i = 0; i < qs.count; i++)
1564     if (!MAPTST(m, qs.elements[i]))
1565       addrpmrulesforsolvable(solv, pool->solvables + qs.elements[i], m);
1566   queue_free(&qs);
1567
1568   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforupdaters -----\n");
1569 }
1570
1571 static Id
1572 finddistupgradepackages(Solver *solv, Solvable *s, Queue *qs, int allow_all)
1573 {
1574   Pool *pool = solv->pool;
1575   int i;
1576
1577   policy_findupdatepackages(solv, s, qs, allow_all);
1578   if (!qs->count)
1579     {
1580       if (allow_all)
1581         return 0;       /* orphaned, don't create feature rule */
1582       /* check if this is an orphaned package */
1583       policy_findupdatepackages(solv, s, qs, 1);
1584       if (!qs->count)
1585         return 0;       /* orphaned, don't create update rule */
1586       qs->count = 0;
1587       return -SYSTEMSOLVABLE;   /* supported but not installable */
1588     }
1589   if (allow_all)
1590     return s - pool->solvables;
1591   /* check if it is ok to keep the installed package */
1592   for (i = 0; i < qs->count; i++)
1593     {
1594       Solvable *ns = pool->solvables + qs->elements[i];
1595       if (s->evr == ns->evr && solvable_identical(s, ns))
1596         return s - pool->solvables;
1597     }
1598   /* nope, it must be some other package */
1599   return -SYSTEMSOLVABLE;
1600 }
1601
1602 /* add packages from the dup repositories to the update candidates
1603  * this isn't needed for the global dup mode as all packages are
1604  * from dup repos in that case */
1605 static void
1606 addduppackages(Solver *solv, Solvable *s, Queue *qs)
1607 {
1608   Queue dupqs;
1609   Id p, dupqsbuf[64];
1610   int i;
1611   int oldnoupdateprovide = solv->noupdateprovide;
1612
1613   queue_init_buffer(&dupqs, dupqsbuf, sizeof(dupqsbuf)/sizeof(*dupqsbuf));
1614   solv->noupdateprovide = 1;
1615   policy_findupdatepackages(solv, s, &dupqs, 2);
1616   solv->noupdateprovide = oldnoupdateprovide;
1617   for (i = 0; i < dupqs.count; i++)
1618     {
1619       p = dupqs.elements[i];
1620       if (MAPTST(&solv->dupmap, p))
1621         queue_pushunique(qs, p);
1622     }
1623   queue_free(&dupqs);
1624 }
1625
1626 /*-------------------------------------------------------------------
1627  *
1628  * add rule for update
1629  *   (A|A1|A2|A3...)  An = update candidates for A
1630  *
1631  * s = (installed) solvable
1632  */
1633
1634 static void
1635 addupdaterule(Solver *solv, Solvable *s, int allow_all)
1636 {
1637   /* installed packages get a special upgrade allowed rule */
1638   Pool *pool = solv->pool;
1639   Id p, d;
1640   Queue qs;
1641   Id qsbuf[64];
1642
1643   POOL_DEBUG(SAT_DEBUG_SCHUBI, "-----  addupdaterule -----\n");
1644   queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
1645   p = s - pool->solvables;
1646   /* find update candidates for 's' */
1647   if (solv->distupgrade)
1648     p = finddistupgradepackages(solv, s, &qs, allow_all);
1649   else
1650     policy_findupdatepackages(solv, s, &qs, allow_all);
1651   if (!allow_all && !solv->distupgrade && solv->dupinvolvedmap.size && MAPTST(&solv->dupinvolvedmap, p))
1652     addduppackages(solv, s, &qs);
1653
1654   if (!allow_all && qs.count && solv->noobsoletes.size)
1655     {
1656       int i, j;
1657
1658       d = pool_queuetowhatprovides(pool, &qs);
1659       /* filter out all noobsoletes packages as they don't update */
1660       for (i = j = 0; i < qs.count; i++)
1661         {
1662           if (MAPTST(&solv->noobsoletes, qs.elements[i]))
1663             {
1664               /* it's ok if they have same nevra */
1665               Solvable *ps = pool->solvables + qs.elements[i];
1666               if (ps->name != s->name || ps->evr != s->evr || ps->arch != s->arch)
1667                 continue;
1668             }
1669           qs.elements[j++] = qs.elements[i];
1670         }
1671       if (j == 0 && p == -SYSTEMSOLVABLE && solv->distupgrade)
1672         {
1673           queue_push(&solv->orphaned, s - pool->solvables);     /* treat as orphaned */
1674           j = qs.count;
1675         }
1676       if (j < qs.count)
1677         {
1678           if (d && solv->updatesystem && solv->installed && s->repo == solv->installed)
1679             {
1680               if (!solv->multiversionupdaters)
1681                 solv->multiversionupdaters = sat_calloc(solv->installed->end - solv->installed->start, sizeof(Id));
1682               solv->multiversionupdaters[s - pool->solvables - solv->installed->start] = d;
1683             }
1684           qs.count = j;
1685         }
1686     }
1687   if (qs.count && p == -SYSTEMSOLVABLE)
1688     p = queue_shift(&qs);
1689   d = qs.count ? pool_queuetowhatprovides(pool, &qs) : 0;
1690   queue_free(&qs);
1691   addrule(solv, p, d);  /* allow update of s */
1692   POOL_DEBUG(SAT_DEBUG_SCHUBI, "-----  addupdaterule end -----\n");
1693 }
1694
1695
1696 /********************************************************************/
1697 /* watches */
1698
1699
1700 /*-------------------------------------------------------------------
1701  * makewatches
1702  *
1703  * initial setup for all watches
1704  */
1705
1706 static void
1707 makewatches(Solver *solv)
1708 {
1709   Rule *r;
1710   int i;
1711   int nsolvables = solv->pool->nsolvables;
1712
1713   sat_free(solv->watches);
1714                                        /* lower half for removals, upper half for installs */
1715   solv->watches = sat_calloc(2 * nsolvables, sizeof(Id));
1716 #if 1
1717   /* do it reverse so rpm rules get triggered first (XXX: obsolete?) */
1718   for (i = 1, r = solv->rules + solv->nrules - 1; i < solv->nrules; i++, r--)
1719 #else
1720   for (i = 1, r = solv->rules + 1; i < solv->nrules; i++, r++)
1721 #endif
1722     {
1723       if (!r->w2)               /* assertions do not need watches */
1724         continue;
1725
1726       /* see addwatches_rule(solv, r) */
1727       r->n1 = solv->watches[nsolvables + r->w1];
1728       solv->watches[nsolvables + r->w1] = r - solv->rules;
1729
1730       r->n2 = solv->watches[nsolvables + r->w2];
1731       solv->watches[nsolvables + r->w2] = r - solv->rules;
1732     }
1733 }
1734
1735
1736 /*-------------------------------------------------------------------
1737  *
1738  * add watches (for rule)
1739  * sets up watches for a single rule
1740  *
1741  * see also makewatches()
1742  */
1743
1744 static inline void
1745 addwatches_rule(Solver *solv, Rule *r)
1746 {
1747   int nsolvables = solv->pool->nsolvables;
1748
1749   r->n1 = solv->watches[nsolvables + r->w1];
1750   solv->watches[nsolvables + r->w1] = r - solv->rules;
1751
1752   r->n2 = solv->watches[nsolvables + r->w2];
1753   solv->watches[nsolvables + r->w2] = r - solv->rules;
1754 }
1755
1756
1757 /********************************************************************/
1758 /*
1759  * rule propagation
1760  */
1761
1762
1763 /* shortcuts to check if a literal (positive or negative) assignment
1764  * evaluates to 'true' or 'false'
1765  */
1766 #define DECISIONMAP_TRUE(p) ((p) > 0 ? (decisionmap[p] > 0) : (decisionmap[-p] < 0))
1767 #define DECISIONMAP_FALSE(p) ((p) > 0 ? (decisionmap[p] < 0) : (decisionmap[-p] > 0))
1768 #define DECISIONMAP_UNDEF(p) (decisionmap[(p) > 0 ? (p) : -(p)] == 0)
1769
1770 /*-------------------------------------------------------------------
1771  *
1772  * propagate
1773  *
1774  * make decision and propagate to all rules
1775  *
1776  * Evaluate each term affected by the decision (linked through watches)
1777  * If we find unit rules we make new decisions based on them
1778  *
1779  * Everything's fixed there, it's just finding rules that are
1780  * unit.
1781  *
1782  * return : 0 = everything is OK
1783  *          rule = conflict found in this rule
1784  */
1785
1786 static Rule *
1787 propagate(Solver *solv, int level)
1788 {
1789   Pool *pool = solv->pool;
1790   Id *rp, *next_rp;           /* rule pointer, next rule pointer in linked list */
1791   Rule *r;                    /* rule */
1792   Id p, pkg, other_watch;
1793   Id *dp;
1794   Id *decisionmap = solv->decisionmap;
1795
1796   Id *watches = solv->watches + pool->nsolvables;   /* place ptr in middle */
1797
1798   POOL_DEBUG(SAT_DEBUG_PROPAGATE, "----- propagate -----\n");
1799
1800   /* foreach non-propagated decision */
1801   while (solv->propagate_index < solv->decisionq.count)
1802     {
1803         /*
1804          * 'pkg' was just decided
1805          * negate because our watches trigger if literal goes FALSE
1806          */
1807       pkg = -solv->decisionq.elements[solv->propagate_index++];
1808
1809       IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1810         {
1811           POOL_DEBUG(SAT_DEBUG_PROPAGATE, "propagate for decision %d level %d\n", -pkg, level);
1812           solver_printruleelement(solv, SAT_DEBUG_PROPAGATE, 0, -pkg);
1813         }
1814
1815       /* foreach rule where 'pkg' is now FALSE */
1816       for (rp = watches + pkg; *rp; rp = next_rp)
1817         {
1818           r = solv->rules + *rp;
1819           if (r->d < 0)
1820             {
1821               /* rule is disabled, goto next */
1822               if (pkg == r->w1)
1823                 next_rp = &r->n1;
1824               else
1825                 next_rp = &r->n2;
1826               continue;
1827             }
1828
1829           IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1830             {
1831               POOL_DEBUG(SAT_DEBUG_PROPAGATE,"  watch triggered ");
1832               solver_printrule(solv, SAT_DEBUG_PROPAGATE, r);
1833             }
1834
1835             /* 'pkg' was just decided (was set to FALSE)
1836              *
1837              *  now find other literal watch, check clause
1838              *   and advance on linked list
1839              */
1840           if (pkg == r->w1)
1841             {
1842               other_watch = r->w2;
1843               next_rp = &r->n1;
1844             }
1845           else
1846             {
1847               other_watch = r->w1;
1848               next_rp = &r->n2;
1849             }
1850
1851             /*
1852              * This term is already true (through the other literal)
1853              * so we have nothing to do
1854              */
1855           if (DECISIONMAP_TRUE(other_watch))
1856             continue;
1857
1858             /*
1859              * The other literal is FALSE or UNDEF
1860              *
1861              */
1862
1863           if (r->d)
1864             {
1865               /* Not a binary clause, try to move our watch.
1866                *
1867                * Go over all literals and find one that is
1868                *   not other_watch
1869                *   and not FALSE
1870                *
1871                * (TRUE is also ok, in that case the rule is fulfilled)
1872                */
1873               if (r->p                                /* we have a 'p' */
1874                   && r->p != other_watch              /* which is not watched */
1875                   && !DECISIONMAP_FALSE(r->p))        /* and not FALSE */
1876                 {
1877                   p = r->p;
1878                 }
1879               else                                    /* go find a 'd' to make 'true' */
1880                 {
1881                   /* foreach p in 'd'
1882                      we just iterate sequentially, doing it in another order just changes the order of decisions, not the decisions itself
1883                    */
1884                   for (dp = pool->whatprovidesdata + r->d; (p = *dp++) != 0;)
1885                     {
1886                       if (p != other_watch              /* which is not watched */
1887                           && !DECISIONMAP_FALSE(p))     /* and not FALSE */
1888                         break;
1889                     }
1890                 }
1891
1892               if (p)
1893                 {
1894                   /*
1895                    * if we found some p that is UNDEF or TRUE, move
1896                    * watch to it
1897                    */
1898                   IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1899                     {
1900                       if (p > 0)
1901                         POOL_DEBUG(SAT_DEBUG_PROPAGATE, "    -> move w%d to %s\n", (pkg == r->w1 ? 1 : 2), solvable2str(pool, pool->solvables + p));
1902                       else
1903                         POOL_DEBUG(SAT_DEBUG_PROPAGATE,"    -> move w%d to !%s\n", (pkg == r->w1 ? 1 : 2), solvable2str(pool, pool->solvables - p));
1904                     }
1905
1906                   *rp = *next_rp;
1907                   next_rp = rp;
1908
1909                   if (pkg == r->w1)
1910                     {
1911                       r->w1 = p;
1912                       r->n1 = watches[p];
1913                     }
1914                   else
1915                     {
1916                       r->w2 = p;
1917                       r->n2 = watches[p];
1918                     }
1919                   watches[p] = r - solv->rules;
1920                   continue;
1921                 }
1922               /* search failed, thus all unwatched literals are FALSE */
1923
1924             } /* not binary */
1925
1926             /*
1927              * unit clause found, set literal other_watch to TRUE
1928              */
1929
1930           if (DECISIONMAP_FALSE(other_watch))      /* check if literal is FALSE */
1931             return r;                              /* eek, a conflict! */
1932
1933           IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1934             {
1935               POOL_DEBUG(SAT_DEBUG_PROPAGATE, "   unit ");
1936               solver_printrule(solv, SAT_DEBUG_PROPAGATE, r);
1937             }
1938
1939           if (other_watch > 0)
1940             decisionmap[other_watch] = level;    /* install! */
1941           else
1942             decisionmap[-other_watch] = -level;  /* remove! */
1943
1944           queue_push(&solv->decisionq, other_watch);
1945           queue_push(&solv->decisionq_why, r - solv->rules);
1946
1947           IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1948             {
1949               Solvable *s = pool->solvables + (other_watch > 0 ? other_watch : -other_watch);
1950               if (other_watch > 0)
1951                 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "    -> decided to install %s\n", solvable2str(pool, s));
1952               else
1953                 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "    -> decided to conflict %s\n", solvable2str(pool, s));
1954             }
1955
1956         } /* foreach rule involving 'pkg' */
1957
1958     } /* while we have non-decided decisions */
1959
1960   POOL_DEBUG(SAT_DEBUG_PROPAGATE, "----- propagate end-----\n");
1961
1962   return 0;     /* all is well */
1963 }
1964
1965
1966 /********************************************************************/
1967 /* Analysis */
1968
1969 /*-------------------------------------------------------------------
1970  *
1971  * analyze
1972  *   and learn
1973  */
1974
1975 static int
1976 analyze(Solver *solv, int level, Rule *c, int *pr, int *dr, int *whyp)
1977 {
1978   Pool *pool = solv->pool;
1979   Queue r;
1980   int rlevel = 1;
1981   Map seen;             /* global? */
1982   Id d, v, vv, *dp, why;
1983   int l, i, idx;
1984   int num = 0, l1num = 0;
1985   int learnt_why = solv->learnt_pool.count;
1986   Id *decisionmap = solv->decisionmap;
1987
1988   queue_init(&r);
1989
1990   POOL_DEBUG(SAT_DEBUG_ANALYZE, "ANALYZE at %d ----------------------\n", level);
1991   map_init(&seen, pool->nsolvables);
1992   idx = solv->decisionq.count;
1993   for (;;)
1994     {
1995       IF_POOLDEBUG (SAT_DEBUG_ANALYZE)
1996         solver_printruleclass(solv, SAT_DEBUG_ANALYZE, c);
1997       queue_push(&solv->learnt_pool, c - solv->rules);
1998       d = c->d < 0 ? -c->d - 1 : c->d;
1999       dp = d ? pool->whatprovidesdata + d : 0;
2000       /* go through all literals of the rule */
2001       for (i = -1; ; i++)
2002         {
2003           if (i == -1)
2004             v = c->p;
2005           else if (d == 0)
2006             v = i ? 0 : c->w2;
2007           else
2008             v = *dp++;
2009           if (v == 0)
2010             break;
2011
2012           if (DECISIONMAP_TRUE(v))      /* the one true literal */
2013             continue;
2014           vv = v > 0 ? v : -v;
2015           if (MAPTST(&seen, vv))
2016             continue;
2017           l = solv->decisionmap[vv];
2018           if (l < 0)
2019             l = -l;
2020           MAPSET(&seen, vv);
2021           if (l == 1)
2022             l1num++;                    /* need to do this one in level1 pass */
2023           else if (l == level)
2024             num++;                      /* need to do this one as well */
2025           else
2026             {
2027               queue_push(&r, v);        /* not level1 or conflict level, add to new rule */
2028               if (l > rlevel)
2029                 rlevel = l;
2030             }
2031         }
2032 l1retry:
2033       if (!num && !--l1num)
2034         break;  /* all level 1 literals done */
2035       for (;;)
2036         {
2037           assert(idx > 0);
2038           v = solv->decisionq.elements[--idx];
2039           vv = v > 0 ? v : -v;
2040           if (MAPTST(&seen, vv))
2041             break;
2042         }
2043       MAPCLR(&seen, vv);
2044       if (num && --num == 0)
2045         {
2046           *pr = -v;     /* so that v doesn't get lost */
2047           if (!l1num)
2048             break;
2049           POOL_DEBUG(SAT_DEBUG_ANALYZE, "got %d involved level 1 decisions\n", l1num);
2050           for (i = 0; i < r.count; i++)
2051             {
2052               v = r.elements[i];
2053               MAPCLR(&seen, v > 0 ? v : -v);
2054             }
2055           /* only level 1 marks left */
2056           l1num++;
2057           goto l1retry;
2058         }
2059       why = solv->decisionq_why.elements[idx];
2060       if (why <= 0)     /* just in case, maybe for SYSTEMSOLVABLE */
2061         goto l1retry;
2062       c = solv->rules + why;
2063     }
2064   map_free(&seen);
2065
2066   if (r.count == 0)
2067     *dr = 0;
2068   else if (r.count == 1 && r.elements[0] < 0)
2069     *dr = r.elements[0];
2070   else
2071     *dr = pool_queuetowhatprovides(pool, &r);
2072   IF_POOLDEBUG (SAT_DEBUG_ANALYZE)
2073     {
2074       POOL_DEBUG(SAT_DEBUG_ANALYZE, "learned rule for level %d (am %d)\n", rlevel, level);
2075       solver_printruleelement(solv, SAT_DEBUG_ANALYZE, 0, *pr);
2076       for (i = 0; i < r.count; i++)
2077         solver_printruleelement(solv, SAT_DEBUG_ANALYZE, 0, r.elements[i]);
2078     }
2079   /* push end marker on learnt reasons stack */
2080   queue_push(&solv->learnt_pool, 0);
2081   if (whyp)
2082     *whyp = learnt_why;
2083   solv->stats_learned++;
2084   return rlevel;
2085 }
2086
2087
2088 /*-------------------------------------------------------------------
2089  *
2090  * reset_solver
2091  *
2092  * reset the solver decisions to right after the rpm rules.
2093  * called after rules have been enabled/disabled
2094  */
2095
2096 static void
2097 reset_solver(Solver *solv)
2098 {
2099   Pool *pool = solv->pool;
2100   int i;
2101   Id v;
2102
2103   /* rewind decisions to direct rpm rule assertions */
2104   for (i = solv->decisionq.count - 1; i >= solv->directdecisions; i--)
2105     {
2106       v = solv->decisionq.elements[i];
2107       solv->decisionmap[v > 0 ? v : -v] = 0;
2108     }
2109
2110   POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "decisions done reduced from %d to %d\n", solv->decisionq.count, solv->directdecisions);
2111
2112   solv->decisionq_why.count = solv->directdecisions;
2113   solv->decisionq.count = solv->directdecisions;
2114   solv->recommends_index = -1;
2115   solv->propagate_index = 0;
2116
2117   /* adapt learnt rule status to new set of enabled/disabled rules */
2118   enabledisablelearntrules(solv);
2119
2120   /* redo all job/update decisions */
2121   makeruledecisions(solv);
2122   POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "decisions so far: %d\n", solv->decisionq.count);
2123 }
2124
2125
2126 /*-------------------------------------------------------------------
2127  *
2128  * analyze_unsolvable_rule
2129  */
2130
2131 static void
2132 analyze_unsolvable_rule(Solver *solv, Rule *r, Id *lastweakp)
2133 {
2134   Pool *pool = solv->pool;
2135   int i;
2136   Id why = r - solv->rules;
2137
2138   IF_POOLDEBUG (SAT_DEBUG_UNSOLVABLE)
2139     solver_printruleclass(solv, SAT_DEBUG_UNSOLVABLE, r);
2140   if (solv->learntrules && why >= solv->learntrules)
2141     {
2142       for (i = solv->learnt_why.elements[why - solv->learntrules]; solv->learnt_pool.elements[i]; i++)
2143         if (solv->learnt_pool.elements[i] > 0)
2144           analyze_unsolvable_rule(solv, solv->rules + solv->learnt_pool.elements[i], lastweakp);
2145       return;
2146     }
2147   if (MAPTST(&solv->weakrulemap, why))
2148     if (!*lastweakp || why > *lastweakp)
2149       *lastweakp = why;
2150   /* do not add rpm rules to problem */
2151   if (why < solv->rpmrules_end)
2152     return;
2153   /* turn rule into problem */
2154   if (why >= solv->jobrules && why < solv->jobrules_end)
2155     why = -(solv->ruletojob.elements[why - solv->jobrules] + 1);
2156   /* normalize dup/infarch rules */
2157   if (why > solv->infarchrules && why < solv->infarchrules_end)
2158     {
2159       Id name = pool->solvables[-solv->rules[why].p].name;
2160       while (why > solv->infarchrules && pool->solvables[-solv->rules[why - 1].p].name == name)
2161         why--;
2162     }
2163   if (why > solv->duprules && why < solv->duprules_end)
2164     {
2165       Id name = pool->solvables[-solv->rules[why].p].name;
2166       while (why > solv->duprules && pool->solvables[-solv->rules[why - 1].p].name == name)
2167         why--;
2168     }
2169
2170   /* return if problem already countains our rule */
2171   if (solv->problems.count)
2172     {
2173       for (i = solv->problems.count - 1; i >= 0; i--)
2174         if (solv->problems.elements[i] == 0)    /* end of last problem reached? */
2175           break;
2176         else if (solv->problems.elements[i] == why)
2177           return;
2178     }
2179   queue_push(&solv->problems, why);
2180 }
2181
2182
2183 /*-------------------------------------------------------------------
2184  *
2185  * analyze_unsolvable
2186  *
2187  * return: 1 - disabled some rules, try again
2188  *         0 - hopeless
2189  */
2190
2191 static int
2192 analyze_unsolvable(Solver *solv, Rule *cr, int disablerules)
2193 {
2194   Pool *pool = solv->pool;
2195   Rule *r;
2196   Map seen;             /* global to speed things up? */
2197   Id d, v, vv, *dp, why;
2198   int l, i, idx;
2199   Id *decisionmap = solv->decisionmap;
2200   int oldproblemcount;
2201   int oldlearntpoolcount;
2202   Id lastweak;
2203
2204   POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "ANALYZE UNSOLVABLE ----------------------\n");
2205   solv->stats_unsolvable++;
2206   oldproblemcount = solv->problems.count;
2207   oldlearntpoolcount = solv->learnt_pool.count;
2208
2209   /* make room for proof index */
2210   /* must update it later, as analyze_unsolvable_rule would confuse
2211    * it with a rule index if we put the real value in already */
2212   queue_push(&solv->problems, 0);
2213
2214   r = cr;
2215   map_init(&seen, pool->nsolvables);
2216   queue_push(&solv->learnt_pool, r - solv->rules);
2217   lastweak = 0;
2218   analyze_unsolvable_rule(solv, r, &lastweak);
2219   d = r->d < 0 ? -r->d - 1 : r->d;
2220   dp = d ? pool->whatprovidesdata + d : 0;
2221   for (i = -1; ; i++)
2222     {
2223       if (i == -1)
2224         v = r->p;
2225       else if (d == 0)
2226         v = i ? 0 : r->w2;
2227       else
2228         v = *dp++;
2229       if (v == 0)
2230         break;
2231       if (DECISIONMAP_TRUE(v))  /* the one true literal */
2232           continue;
2233       vv = v > 0 ? v : -v;
2234       l = solv->decisionmap[vv];
2235       if (l < 0)
2236         l = -l;
2237       MAPSET(&seen, vv);
2238     }
2239   idx = solv->decisionq.count;
2240   while (idx > 0)
2241     {
2242       v = solv->decisionq.elements[--idx];
2243       vv = v > 0 ? v : -v;
2244       if (!MAPTST(&seen, vv))
2245         continue;
2246       why = solv->decisionq_why.elements[idx];
2247       assert(why > 0);
2248       queue_push(&solv->learnt_pool, why);
2249       r = solv->rules + why;
2250       analyze_unsolvable_rule(solv, r, &lastweak);
2251       d = r->d < 0 ? -r->d - 1 : r->d;
2252       dp = d ? pool->whatprovidesdata + d : 0;
2253       for (i = -1; ; i++)
2254         {
2255           if (i == -1)
2256             v = r->p;
2257           else if (d == 0)
2258             v = i ? 0 : r->w2;
2259           else
2260             v = *dp++;
2261           if (v == 0)
2262             break;
2263           if (DECISIONMAP_TRUE(v))      /* the one true literal */
2264               continue;
2265           vv = v > 0 ? v : -v;
2266           l = solv->decisionmap[vv];
2267           if (l < 0)
2268             l = -l;
2269           MAPSET(&seen, vv);
2270         }
2271     }
2272   map_free(&seen);
2273   queue_push(&solv->problems, 0);       /* mark end of this problem */
2274
2275   if (lastweak)
2276     {
2277       Id v;
2278       /* disable last weak rule */
2279       solv->problems.count = oldproblemcount;
2280       solv->learnt_pool.count = oldlearntpoolcount;
2281       if (lastweak >= solv->jobrules && lastweak < solv->jobrules_end)
2282         v = -(solv->ruletojob.elements[lastweak - solv->jobrules] + 1);
2283       else
2284         v = lastweak;
2285       POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "disabling ");
2286       solver_printruleclass(solv, SAT_DEBUG_UNSOLVABLE, solv->rules + lastweak);
2287       disableproblem(solv, v);
2288       if (v < 0)
2289         disableupdaterules(solv, solv->job, -(v + 1));
2290       reset_solver(solv);
2291       return 1;
2292     }
2293
2294   /* finish proof */
2295   queue_push(&solv->learnt_pool, 0);
2296   solv->problems.elements[oldproblemcount] = oldlearntpoolcount;
2297
2298   if (disablerules)
2299     {
2300       for (i = oldproblemcount + 1; i < solv->problems.count - 1; i++)
2301         disableproblem(solv, solv->problems.elements[i]);
2302       /* XXX: might want to enable all weak rules again */
2303       reset_solver(solv);
2304       return 1;
2305     }
2306   POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "UNSOLVABLE\n");
2307   return 0;
2308 }
2309
2310
2311 /********************************************************************/
2312 /* Decision revert */
2313
2314 /*-------------------------------------------------------------------
2315  *
2316  * revert
2317  * revert decision at level
2318  */
2319
2320 static void
2321 revert(Solver *solv, int level)
2322 {
2323   Pool *pool = solv->pool;
2324   Id v, vv;
2325   while (solv->decisionq.count)
2326     {
2327       v = solv->decisionq.elements[solv->decisionq.count - 1];
2328       vv = v > 0 ? v : -v;
2329       if (solv->decisionmap[vv] <= level && solv->decisionmap[vv] >= -level)
2330         break;
2331       POOL_DEBUG(SAT_DEBUG_PROPAGATE, "reverting decision %d at %d\n", v, solv->decisionmap[vv]);
2332       if (v > 0 && solv->recommendations.count && v == solv->recommendations.elements[solv->recommendations.count - 1])
2333         solv->recommendations.count--;
2334       solv->decisionmap[vv] = 0;
2335       solv->decisionq.count--;
2336       solv->decisionq_why.count--;
2337       solv->propagate_index = solv->decisionq.count;
2338     }
2339   while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] <= -level)
2340     {
2341       solv->branches.count--;
2342       while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] >= 0)
2343         solv->branches.count--;
2344     }
2345   solv->recommends_index = -1;
2346 }
2347
2348
2349 /*-------------------------------------------------------------------
2350  *
2351  * watch2onhighest - put watch2 on literal with highest level
2352  */
2353
2354 static inline void
2355 watch2onhighest(Solver *solv, Rule *r)
2356 {
2357   int l, wl = 0;
2358   Id d, v, *dp;
2359
2360   d = r->d < 0 ? -r->d - 1 : r->d;
2361   if (!d)
2362     return;     /* binary rule, both watches are set */
2363   dp = solv->pool->whatprovidesdata + d;
2364   while ((v = *dp++) != 0)
2365     {
2366       l = solv->decisionmap[v < 0 ? -v : v];
2367       if (l < 0)
2368         l = -l;
2369       if (l > wl)
2370         {
2371           r->w2 = dp[-1];
2372           wl = l;
2373         }
2374     }
2375 }
2376
2377
2378 /*-------------------------------------------------------------------
2379  *
2380  * setpropagatelearn
2381  *
2382  * add free decision (solvable to install) to decisionq
2383  * increase level and propagate decision
2384  * return if no conflict.
2385  *
2386  * in conflict case, analyze conflict rule, add resulting
2387  * rule to learnt rule set, make decision from learnt
2388  * rule (always unit) and re-propagate.
2389  *
2390  * returns the new solver level or 0 if unsolvable
2391  *
2392  */
2393
2394 static int
2395 setpropagatelearn(Solver *solv, int level, Id decision, int disablerules, Id ruleid)
2396 {
2397   Pool *pool = solv->pool;
2398   Rule *r;
2399   Id p = 0, d = 0;
2400   int l, why;
2401
2402   assert(ruleid >= 0);
2403   if (decision)
2404     {
2405       level++;
2406       if (decision > 0)
2407         solv->decisionmap[decision] = level;
2408       else
2409         solv->decisionmap[-decision] = -level;
2410       queue_push(&solv->decisionq, decision);
2411       queue_push(&solv->decisionq_why, -ruleid);        /* <= 0 -> free decision */
2412     }
2413   for (;;)
2414     {
2415       r = propagate(solv, level);
2416       if (!r)
2417         break;
2418       if (level == 1)
2419         return analyze_unsolvable(solv, r, disablerules);
2420       POOL_DEBUG(SAT_DEBUG_ANALYZE, "conflict with rule #%d\n", (int)(r - solv->rules));
2421       l = analyze(solv, level, r, &p, &d, &why);        /* learnt rule in p and d */
2422       assert(l > 0 && l < level);
2423       POOL_DEBUG(SAT_DEBUG_ANALYZE, "reverting decisions (level %d -> %d)\n", level, l);
2424       level = l;
2425       revert(solv, level);
2426       r = addrule(solv, p, d);
2427       assert(r);
2428       assert(solv->learnt_why.count == (r - solv->rules) - solv->learntrules);
2429       queue_push(&solv->learnt_why, why);
2430       if (d)
2431         {
2432           /* at least 2 literals, needs watches */
2433           watch2onhighest(solv, r);
2434           addwatches_rule(solv, r);
2435         }
2436       else
2437         {
2438           /* learnt rule is an assertion */
2439           queue_push(&solv->ruleassertions, r - solv->rules);
2440         }
2441       solv->decisionmap[p > 0 ? p : -p] = p > 0 ? level : -level;
2442       queue_push(&solv->decisionq, p);
2443       queue_push(&solv->decisionq_why, r - solv->rules);
2444       IF_POOLDEBUG (SAT_DEBUG_ANALYZE)
2445         {
2446           POOL_DEBUG(SAT_DEBUG_ANALYZE, "decision: ");
2447           solver_printruleelement(solv, SAT_DEBUG_ANALYZE, 0, p);
2448           POOL_DEBUG(SAT_DEBUG_ANALYZE, "new rule: ");
2449           solver_printrule(solv, SAT_DEBUG_ANALYZE, r);
2450         }
2451     }
2452   return level;
2453 }
2454
2455
2456 /*-------------------------------------------------------------------
2457  *
2458  * select and install
2459  *
2460  * install best package from the queue. We add an extra package, inst, if
2461  * provided. See comment in weak install section.
2462  *
2463  * returns the new solver level or 0 if unsolvable
2464  *
2465  */
2466
2467 static int
2468 selectandinstall(Solver *solv, int level, Queue *dq, int disablerules, Id ruleid)
2469 {
2470   Pool *pool = solv->pool;
2471   Id p;
2472   int i;
2473
2474   if (dq->count > 1)
2475     policy_filter_unwanted(solv, dq, POLICY_MODE_CHOOSE);
2476   if (dq->count > 1)
2477     {
2478       /* XXX: didn't we already do that? */
2479       /* XXX: shouldn't we prefer installed packages? */
2480       /* XXX: move to policy.c? */
2481       /* choose the supplemented one */
2482       for (i = 0; i < dq->count; i++)
2483         if (solver_is_supplementing(solv, pool->solvables + dq->elements[i]))
2484           {
2485             dq->elements[0] = dq->elements[i];
2486             dq->count = 1;
2487             break;
2488           }
2489     }
2490   if (dq->count > 1)
2491     {
2492       /* multiple candidates, open a branch */
2493       for (i = 1; i < dq->count; i++)
2494         queue_push(&solv->branches, dq->elements[i]);
2495       queue_push(&solv->branches, -level);
2496     }
2497   p = dq->elements[0];
2498
2499   POOL_DEBUG(SAT_DEBUG_POLICY, "installing %s\n", solvable2str(pool, pool->solvables + p));
2500
2501   return setpropagatelearn(solv, level, p, disablerules, ruleid);
2502 }
2503
2504
2505 /********************************************************************/
2506 /* Main solver interface */
2507
2508
2509 /*-------------------------------------------------------------------
2510  *
2511  * solver_create
2512  * create solver structure
2513  *
2514  * pool: all available solvables
2515  * installed: installed Solvables
2516  *
2517  *
2518  * Upon solving, rules are created to flag the Solvables
2519  * of the 'installed' Repo as installed.
2520  */
2521
2522 Solver *
2523 solver_create(Pool *pool)
2524 {
2525   Solver *solv;
2526   solv = (Solver *)sat_calloc(1, sizeof(Solver));
2527   solv->pool = pool;
2528   solv->installed = pool->installed;
2529
2530   queue_init(&solv->ruletojob);
2531   queue_init(&solv->decisionq);
2532   queue_init(&solv->decisionq_why);
2533   queue_init(&solv->problems);
2534   queue_init(&solv->suggestions);
2535   queue_init(&solv->recommendations);
2536   queue_init(&solv->orphaned);
2537   queue_init(&solv->learnt_why);
2538   queue_init(&solv->learnt_pool);
2539   queue_init(&solv->branches);
2540   queue_init(&solv->covenantq);
2541   queue_init(&solv->weakruleq);
2542   queue_init(&solv->ruleassertions);
2543
2544   map_init(&solv->recommendsmap, pool->nsolvables);
2545   map_init(&solv->suggestsmap, pool->nsolvables);
2546   map_init(&solv->noupdate, solv->installed ? solv->installed->end - solv->installed->start : 0);
2547   solv->recommends_index = 0;
2548
2549   solv->decisionmap = (Id *)sat_calloc(pool->nsolvables, sizeof(Id));
2550   solv->nrules = 1;
2551   solv->rules = sat_extend_resize(solv->rules, solv->nrules, sizeof(Rule), RULES_BLOCK);
2552   memset(solv->rules, 0, sizeof(Rule));
2553
2554   return solv;
2555 }
2556
2557
2558 /*-------------------------------------------------------------------
2559  *
2560  * solver_free
2561  */
2562
2563 void
2564 solver_free(Solver *solv)
2565 {
2566   queue_free(&solv->ruletojob);
2567   queue_free(&solv->decisionq);
2568   queue_free(&solv->decisionq_why);
2569   queue_free(&solv->learnt_why);
2570   queue_free(&solv->learnt_pool);
2571   queue_free(&solv->problems);
2572   queue_free(&solv->suggestions);
2573   queue_free(&solv->recommendations);
2574   queue_free(&solv->orphaned);
2575   queue_free(&solv->branches);
2576   queue_free(&solv->covenantq);
2577   queue_free(&solv->weakruleq);
2578   queue_free(&solv->ruleassertions);
2579
2580   map_free(&solv->recommendsmap);
2581   map_free(&solv->suggestsmap);
2582   map_free(&solv->noupdate);
2583   map_free(&solv->weakrulemap);
2584   map_free(&solv->noobsoletes);
2585
2586   map_free(&solv->updatemap);
2587   map_free(&solv->dupmap);
2588   map_free(&solv->dupinvolvedmap);
2589
2590   sat_free(solv->decisionmap);
2591   sat_free(solv->rules);
2592   sat_free(solv->watches);
2593   sat_free(solv->obsoletes);
2594   sat_free(solv->obsoletes_data);
2595   sat_free(solv->multiversionupdaters);
2596   sat_free(solv);
2597 }
2598
2599
2600 /*-------------------------------------------------------------------
2601  *
2602  * run_solver
2603  *
2604  * all rules have been set up, now actually run the solver
2605  *
2606  */
2607
2608 static void
2609 run_solver(Solver *solv, int disablerules, int doweak)
2610 {
2611   Queue dq;             /* local decisionqueue */
2612   Queue dqs;            /* local decisionqueue for supplements */
2613   int systemlevel;
2614   int level, olevel;
2615   Rule *r;
2616   int i, j, n;
2617   Solvable *s;
2618   Pool *pool = solv->pool;
2619   Id p, *dp;
2620   int minimizationsteps;
2621
2622   IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION)
2623     {
2624       POOL_DEBUG (SAT_DEBUG_RULE_CREATION, "number of rules: %d\n", solv->nrules);
2625       for (i = 1; i < solv->nrules; i++)
2626         solver_printruleclass(solv, SAT_DEBUG_RULE_CREATION, solv->rules + i);
2627     }
2628
2629   POOL_DEBUG(SAT_DEBUG_STATS, "initial decisions: %d\n", solv->decisionq.count);
2630
2631   IF_POOLDEBUG (SAT_DEBUG_SCHUBI)
2632     solver_printdecisions(solv);
2633
2634   /* start SAT algorithm */
2635   level = 1;
2636   systemlevel = level + 1;
2637   POOL_DEBUG(SAT_DEBUG_STATS, "solving...\n");
2638
2639   queue_init(&dq);
2640   queue_init(&dqs);
2641
2642   /*
2643    * here's the main loop:
2644    * 1) propagate new decisions (only needed for level 1)
2645    * 2) try to keep installed packages
2646    * 3) fulfill all unresolved rules
2647    * 4) install recommended packages
2648    * 5) minimalize solution if we had choices
2649    * if we encounter a problem, we rewind to a safe level and restart
2650    * with step 1
2651    */
2652
2653   minimizationsteps = 0;
2654   for (;;)
2655     {
2656       /*
2657        * propagate
2658        */
2659
2660       if (level == 1)
2661         {
2662           POOL_DEBUG(SAT_DEBUG_PROPAGATE, "propagating (propagate_index: %d;  size decisionq: %d)...\n", solv->propagate_index, solv->decisionq.count);
2663           if ((r = propagate(solv, level)) != 0)
2664             {
2665               if (analyze_unsolvable(solv, r, disablerules))
2666                 continue;
2667               queue_free(&dq);
2668               queue_free(&dqs);
2669               return;
2670             }
2671         }
2672
2673      if (level < systemlevel)
2674         {
2675           POOL_DEBUG(SAT_DEBUG_STATS, "resolving job rules\n");
2676           for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++)
2677             {
2678               Id l;
2679               if (r->d < 0)             /* ignore disabled rules */
2680                 continue;
2681               queue_empty(&dq);
2682               FOR_RULELITERALS(l, dp, r)
2683                 {
2684                   if (l < 0)
2685                     {
2686                       if (solv->decisionmap[-l] <= 0)
2687                         break;
2688                     }
2689                   else
2690                     {
2691                       if (solv->decisionmap[l] > 0)
2692                         break;
2693                       if (solv->decisionmap[l] == 0)
2694                         queue_push(&dq, l);
2695                     }
2696                 }
2697               if (l || !dq.count)
2698                 continue;
2699               /* prune to installed if not updating */
2700               if (!solv->updatesystem && solv->installed && dq.count > 1)
2701                 {
2702                   int j, k;
2703                   for (j = k = 0; j < dq.count; j++)
2704                     {
2705                       Solvable *s = pool->solvables + dq.elements[j];
2706                       if (s->repo == solv->installed)
2707                         dq.elements[k++] = dq.elements[j];
2708                     }
2709                   if (k)
2710                     dq.count = k;
2711                 }
2712               olevel = level;
2713               level = selectandinstall(solv, level, &dq, disablerules, i);
2714               if (level == 0)
2715                 {
2716                   queue_free(&dq);
2717                   queue_free(&dqs);
2718                   return;
2719                 }
2720               if (level <= olevel)
2721                 break;
2722             }
2723           systemlevel = level + 1;
2724           if (i < solv->jobrules_end)
2725             continue;
2726         }
2727
2728
2729       /*
2730        * installed packages
2731        */
2732
2733       if (level < systemlevel && solv->installed && solv->installed->nsolvables)
2734         {
2735           Repo *installed = solv->installed;
2736           int pass;
2737
2738           /* we use two passes if we need to update packages
2739            * to create a better user experience */
2740           for (pass = solv->updatemap.size ? 0 : 1; pass < 2; pass++)
2741             {
2742               FOR_REPO_SOLVABLES(installed, i, s)
2743                 {
2744                   Rule *rr;
2745                   Id d;
2746
2747                   if (MAPTST(&solv->noupdate, i - installed->start))
2748                     continue;
2749                   if (solv->decisionmap[i] > 0)
2750                     continue;
2751                   if (!pass && solv->updatemap.size && !MAPTST(&solv->updatemap, i - installed->start))
2752                     continue;           /* updates first */
2753                   r = solv->rules + solv->updaterules + (i - installed->start);
2754                   rr = r;
2755                   if (!rr->p || rr->d < 0)      /* disabled -> look at feature rule */
2756                     rr -= solv->installed->end - solv->installed->start;
2757                   if (!rr->p)           /* identical to update rule? */
2758                     rr = r;
2759                   if (!rr->p)
2760                     continue;           /* orpaned package */
2761
2762                   queue_empty(&dq);
2763                   if (solv->decisionmap[i] < 0 || solv->updatesystem || (solv->updatemap.size && MAPTST(&solv->updatemap, i - installed->start)) || rr->p != i)
2764                     {
2765                       if (solv->noobsoletes.size && solv->multiversionupdaters
2766                              && (d = solv->multiversionupdaters[i - installed->start]) != 0)
2767                         {
2768                           /* special multiversion handling, make sure best version is chosen */
2769                           queue_push(&dq, i);
2770                           while ((p = pool->whatprovidesdata[d++]) != 0)
2771                             if (solv->decisionmap[p] >= 0)
2772                               queue_push(&dq, p);
2773                           policy_filter_unwanted(solv, &dq, POLICY_MODE_CHOOSE);
2774                           p = dq.elements[0];
2775                           if (p != i && solv->decisionmap[p] == 0)
2776                             {
2777                               rr = solv->rules + solv->featurerules + (i - solv->installed->start);
2778                               if (!rr->p)               /* update rule == feature rule? */
2779                                 rr = rr - solv->featurerules + solv->updaterules;
2780                               dq.count = 1;
2781                             }
2782                           else
2783                             dq.count = 0;
2784                         }
2785                       else
2786                         {
2787                           /* update to best package */
2788                           FOR_RULELITERALS(p, dp, rr)
2789                             {
2790                               if (solv->decisionmap[p] > 0)
2791                                 {
2792                                   dq.count = 0;         /* already fulfilled */
2793                                   break;
2794                                 }
2795                               if (!solv->decisionmap[p])
2796                                 queue_push(&dq, p);
2797                             }
2798                         }
2799                     }
2800                   /* install best version */
2801                   if (dq.count)
2802                     {
2803                       olevel = level;
2804                       level = selectandinstall(solv, level, &dq, disablerules, rr - solv->rules);
2805                       if (level == 0)
2806                         {
2807                           queue_free(&dq);
2808                           queue_free(&dqs);
2809                           return;
2810                         }
2811                       if (level <= olevel)
2812                         break;
2813                     }
2814                   /* if still undecided keep package */
2815                   if (solv->decisionmap[i] == 0)
2816                     {
2817                       olevel = level;
2818                       POOL_DEBUG(SAT_DEBUG_POLICY, "keeping %s\n", solvable2str(pool, pool->solvables + i));
2819                       level = setpropagatelearn(solv, level, i, disablerules, r - solv->rules);
2820                       if (level == 0)
2821                         {
2822                           queue_free(&dq);
2823                           queue_free(&dqs);
2824                           return;
2825                         }
2826                       if (level <= olevel)
2827                         break;
2828                     }
2829                 }
2830               if (i < installed->end)
2831                 break;
2832             }
2833           systemlevel = level + 1;
2834           if (pass < 2)
2835             continue;           /* had trouble, retry */
2836         }
2837
2838       if (level < systemlevel)
2839         systemlevel = level;
2840
2841       /*
2842        * decide
2843        */
2844
2845       POOL_DEBUG(SAT_DEBUG_POLICY, "deciding unresolved rules\n");
2846       for (i = 1, n = 1; ; i++, n++)
2847         {
2848           if (n == solv->nrules)
2849             break;
2850           if (i == solv->nrules)
2851             i = 1;
2852           r = solv->rules + i;
2853           if (r->d < 0)         /* ignore disabled rules */
2854             continue;
2855           queue_empty(&dq);
2856           if (r->d == 0)
2857             {
2858               /* binary or unary rule */
2859               /* need two positive undecided literals */
2860               if (r->p < 0 || r->w2 <= 0)
2861                 continue;
2862               if (solv->decisionmap[r->p] || solv->decisionmap[r->w2])
2863                 continue;
2864               queue_push(&dq, r->p);
2865               queue_push(&dq, r->w2);
2866             }
2867           else
2868             {
2869               /* make sure that
2870                * all negative literals are installed
2871                * no positive literal is installed
2872                * i.e. the rule is not fulfilled and we
2873                * just need to decide on the positive literals
2874                */
2875               if (r->p < 0)
2876                 {
2877                   if (solv->decisionmap[-r->p] <= 0)
2878                     continue;
2879                 }
2880               else
2881                 {
2882                   if (solv->decisionmap[r->p] > 0)
2883                     continue;
2884                   if (solv->decisionmap[r->p] == 0)
2885                     queue_push(&dq, r->p);
2886                 }
2887               dp = pool->whatprovidesdata + r->d;
2888               while ((p = *dp++) != 0)
2889                 {
2890                   if (p < 0)
2891                     {
2892                       if (solv->decisionmap[-p] <= 0)
2893                         break;
2894                     }
2895                   else
2896                     {
2897                       if (solv->decisionmap[p] > 0)
2898                         break;
2899                       if (solv->decisionmap[p] == 0)
2900                         queue_push(&dq, p);
2901                     }
2902                 }
2903               if (p)
2904                 continue;
2905             }
2906           IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
2907             {
2908               POOL_DEBUG(SAT_DEBUG_PROPAGATE, "unfulfilled ");
2909               solver_printruleclass(solv, SAT_DEBUG_PROPAGATE, r);
2910             }
2911           /* dq.count < 2 cannot happen as this means that
2912            * the rule is unit */
2913           assert(dq.count > 1);
2914
2915           olevel = level;
2916           level = selectandinstall(solv, level, &dq, disablerules, r - solv->rules);
2917           if (level == 0)
2918             {
2919               queue_free(&dq);
2920               queue_free(&dqs);
2921               return;
2922             }
2923           if (level < systemlevel)
2924             break;
2925           n = 0;
2926         } /* for(), decide */
2927
2928       if (n != solv->nrules)    /* continue if level < systemlevel */
2929         continue;
2930
2931       if (doweak)
2932         {
2933           int qcount;
2934
2935           POOL_DEBUG(SAT_DEBUG_POLICY, "installing recommended packages\n");
2936           queue_empty(&dq);     /* recommended packages */
2937           queue_empty(&dqs);    /* supplemented packages */
2938           for (i = 1; i < pool->nsolvables; i++)
2939             {
2940               if (solv->decisionmap[i] < 0)
2941                 continue;
2942               if (solv->decisionmap[i] > 0)
2943                 {
2944                   /* installed, check for recommends */
2945                   Id *recp, rec, pp, p;
2946                   s = pool->solvables + i;
2947                   if (solv->ignorealreadyrecommended && s->repo == solv->installed)
2948                     continue;
2949                   /* XXX need to special case AND ? */
2950                   if (s->recommends)
2951                     {
2952                       recp = s->repo->idarraydata + s->recommends;
2953                       while ((rec = *recp++) != 0)
2954                         {
2955                           qcount = dq.count;
2956                           FOR_PROVIDES(p, pp, rec)
2957                             {
2958                               if (solv->decisionmap[p] > 0)
2959                                 {
2960                                   dq.count = qcount;
2961                                   break;
2962                                 }
2963                               else if (solv->decisionmap[p] == 0)
2964                                 {
2965                                   queue_pushunique(&dq, p);
2966                                 }
2967                             }
2968                         }
2969                     }
2970                 }
2971               else
2972                 {
2973                   s = pool->solvables + i;
2974                   if (!s->supplements)
2975                     continue;
2976                   if (!pool_installable(pool, s))
2977                     continue;
2978                   if (!solver_is_supplementing(solv, s))
2979                     continue;
2980                   queue_push(&dqs, i);
2981                 }
2982             }
2983
2984           /* filter out all packages obsoleted by installed packages */
2985           /* this is no longer needed if we have reverse obsoletes */
2986           if ((dqs.count || dq.count) && solv->installed)
2987             {
2988               Map obsmap;
2989               Id obs, *obsp, po, ppo;
2990
2991               map_init(&obsmap, pool->nsolvables);
2992               for (p = solv->installed->start; p < solv->installed->end; p++)
2993                 {
2994                   s = pool->solvables + p;
2995                   if (s->repo != solv->installed || !s->obsoletes)
2996                     continue;
2997                   if (solv->decisionmap[p] <= 0)
2998                     continue;
2999                   if (solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p))
3000                     continue;
3001                   obsp = s->repo->idarraydata + s->obsoletes;
3002                   /* foreach obsoletes */
3003                   while ((obs = *obsp++) != 0)
3004                     FOR_PROVIDES(po, ppo, obs)
3005                       MAPSET(&obsmap, po);
3006                 }
3007               for (i = j = 0; i < dqs.count; i++)
3008                 if (!MAPTST(&obsmap, dqs.elements[i]))
3009                   dqs.elements[j++] = dqs.elements[i];
3010               dqs.count = j;
3011               for (i = j = 0; i < dq.count; i++)
3012                 if (!MAPTST(&obsmap, dq.elements[i]))
3013                   dq.elements[j++] = dq.elements[i];
3014               dq.count = j;
3015               map_free(&obsmap);
3016             }
3017
3018           /* filter out all already supplemented packages if requested */
3019           if (solv->ignorealreadyrecommended && dqs.count)
3020             {
3021               /* turn off all new packages */
3022               for (i = 0; i < solv->decisionq.count; i++)
3023                 {
3024                   p = solv->decisionq.elements[i];
3025                   if (p < 0)
3026                     continue;
3027                   s = pool->solvables + p;
3028                   if (s->repo && s->repo != solv->installed)
3029                     solv->decisionmap[p] = -solv->decisionmap[p];
3030                 }
3031               /* filter out old supplements */
3032               for (i = j = 0; i < dqs.count; i++)
3033                 {
3034                   p = dqs.elements[i];
3035                   s = pool->solvables + p;
3036                   if (!s->supplements)
3037                     continue;
3038                   if (!solver_is_supplementing(solv, s))
3039                     dqs.elements[j++] = p;
3040                 }
3041               dqs.count = j;
3042               /* undo turning off */
3043               for (i = 0; i < solv->decisionq.count; i++)
3044                 {
3045                   p = solv->decisionq.elements[i];
3046                   if (p < 0)
3047                     continue;
3048                   s = pool->solvables + p;
3049                   if (s->repo && s->repo != solv->installed)
3050                     solv->decisionmap[p] = -solv->decisionmap[p];
3051                 }
3052             }
3053
3054           /* make dq contain both recommended and supplemented pkgs */
3055           if (dqs.count)
3056             {
3057               for (i = 0; i < dqs.count; i++)
3058                 queue_pushunique(&dq, dqs.elements[i]);
3059             }
3060
3061 #if 1
3062           if (dq.count)
3063             {
3064               Map dqmap;
3065               int decisioncount = solv->decisionq.count;
3066
3067               if (dq.count == 1)
3068                 {
3069                   /* simple case, just one package. no need to choose  */
3070                   p = dq.elements[0];
3071                   if (dqs.count)
3072                     POOL_DEBUG(SAT_DEBUG_POLICY, "installing supplemented %s\n", solvable2str(pool, pool->solvables + p));
3073                   else
3074                     POOL_DEBUG(SAT_DEBUG_POLICY, "installing recommended %s\n", solvable2str(pool, pool->solvables + p));
3075                   queue_push(&solv->recommendations, p);
3076                   level = setpropagatelearn(solv, level, p, 0, 0);
3077                   continue;
3078                 }
3079
3080               /* filter and create a map of result */
3081               policy_filter_unwanted(solv, &dq, POLICY_MODE_RECOMMEND);
3082               map_init(&dqmap, pool->nsolvables);
3083               for (i = 0; i < dq.count; i++)
3084                 MAPSET(&dqmap, dq.elements[i]);
3085
3086               /* install all supplemented packages */
3087               for (i = 0; i < dqs.count; i++)
3088                 {
3089                   p = dqs.elements[i];
3090                   if (solv->decisionmap[p] || !MAPTST(&dqmap, p))
3091                     continue;
3092                   POOL_DEBUG(SAT_DEBUG_POLICY, "installing supplemented %s\n", solvable2str(pool, pool->solvables + p));
3093                   queue_push(&solv->recommendations, p);
3094                   olevel = level;
3095                   level = setpropagatelearn(solv, level, p, 0, 0);
3096                   if (level <= olevel)
3097                     break;
3098                 }
3099               if (i < dqs.count || solv->decisionq.count < decisioncount)
3100                 {
3101                   map_free(&dqmap);
3102                   continue;
3103                 }
3104
3105               /* install all recommended packages */
3106               /* more work as we want to created branches if multiple
3107                * choices are valid */
3108               for (i = 0; i < decisioncount; i++)
3109                 {
3110                   Id rec, *recp, pp;
3111                   p = solv->decisionq.elements[i];
3112                   if (p < 0)
3113                     continue;
3114                   s = pool->solvables + p;
3115                   if (!s->repo || (solv->ignorealreadyrecommended && s->repo == solv->installed))
3116                     continue;
3117                   if (!s->recommends)
3118                     continue;
3119                   recp = s->repo->idarraydata + s->recommends;
3120                   while ((rec = *recp++) != 0)
3121                     {
3122                       queue_empty(&dq);
3123                       FOR_PROVIDES(p, pp, rec)
3124                         {
3125                           if (solv->decisionmap[p] > 0)
3126                             {
3127                               dq.count = 0;
3128                               break;
3129                             }
3130                           else if (solv->decisionmap[p] == 0 && MAPTST(&dqmap, p))
3131                             queue_pushunique(&dq, p);
3132                         }
3133                       if (!dq.count)
3134                         continue;
3135                       if (dq.count > 1)
3136                         {
3137                           /* multiple candidates, open a branch */
3138                           for (i = 1; i < dq.count; i++)
3139                             queue_push(&solv->branches, dq.elements[i]);
3140                           queue_push(&solv->branches, -level);
3141                         }
3142                       p = dq.elements[0];
3143                       POOL_DEBUG(SAT_DEBUG_POLICY, "installing recommended %s\n", solvable2str(pool, pool->solvables + p));
3144                       queue_push(&solv->recommendations, p);
3145                       olevel = level;
3146                       level = setpropagatelearn(solv, level, p, 0, 0);
3147                       if (level <= olevel || solv->decisionq.count < decisioncount)
3148                         break;
3149                     }
3150                   if (rec)
3151                     break;      /* had a problem above, quit loop */
3152                 }
3153               map_free(&dqmap);
3154               continue;
3155             }
3156 #else
3157           if (dq.count)
3158             {
3159               if (dq.count > 1)
3160                 policy_filter_unwanted(solv, &dq, POLICY_MODE_RECOMMEND);
3161               p = dq.elements[0];
3162               /* prefer recommended patterns (bnc#450226) */
3163               /* real fix is to minimize recommended packages as well */
3164               for (i = 0; i < dq.count; i++)
3165                 if (!strncmp(id2str(pool, pool->solvables[dq.elements[i]].name), "pattern:", 8))
3166                   {
3167                     p = dq.elements[i];
3168                     break;
3169                   }
3170               POOL_DEBUG(SAT_DEBUG_POLICY, "installing recommended %s\n", solvable2str(pool, pool->solvables + p));
3171               queue_push(&solv->recommendations, p);
3172               level = setpropagatelearn(solv, level, p, 0, 0);
3173               continue;
3174             }
3175 #endif
3176         }
3177
3178      if (solv->distupgrade && solv->installed)
3179         {
3180           int installedone = 0;
3181
3182           /* let's see if we can install some unsupported package */
3183           POOL_DEBUG(SAT_DEBUG_STATS, "deciding unsupported packages\n");
3184           for (i = 0; i < solv->orphaned.count; i++)
3185             {
3186               p = solv->orphaned.elements[i];
3187               if (solv->decisionmap[p])
3188                 continue;       /* already decided */
3189               olevel = level;
3190               if (solv->distupgrade_removeunsupported)
3191                 {
3192                   POOL_DEBUG(SAT_DEBUG_STATS, "removing unsupported %s\n", solvable2str(pool, pool->solvables + p));
3193                   level = setpropagatelearn(solv, level, -p, 0, 0);
3194                 }
3195               else
3196                 {
3197                   POOL_DEBUG(SAT_DEBUG_STATS, "keeping unsupported %s\n", solvable2str(pool, pool->solvables + p));
3198                   level = setpropagatelearn(solv, level, p, 0, 0);
3199                   installedone = 1;
3200                 }
3201               if (level < olevel)
3202                 break;
3203             }
3204           if (installedone || i < solv->orphaned.count)
3205             continue;
3206         }
3207
3208      if (solv->solution_callback)
3209         {
3210           solv->solution_callback(solv, solv->solution_callback_data);
3211           if (solv->branches.count)
3212             {
3213               int i = solv->branches.count - 1;
3214               int l = -solv->branches.elements[i];
3215               Id why;
3216
3217               for (; i > 0; i--)
3218                 if (solv->branches.elements[i - 1] < 0)
3219                   break;
3220               p = solv->branches.elements[i];
3221               POOL_DEBUG(SAT_DEBUG_STATS, "branching with %s\n", solvable2str(pool, pool->solvables + p));
3222               queue_empty(&dq);
3223               for (j = i + 1; j < solv->branches.count; j++)
3224                 queue_push(&dq, solv->branches.elements[j]);
3225               solv->branches.count = i;
3226               level = l;
3227               revert(solv, level);
3228               if (dq.count > 1)
3229                 for (j = 0; j < dq.count; j++)
3230                   queue_push(&solv->branches, dq.elements[j]);
3231               olevel = level;
3232               why = -solv->decisionq_why.elements[solv->decisionq_why.count];
3233               assert(why >= 0);
3234               level = setpropagatelearn(solv, level, p, disablerules, why);
3235               if (level == 0)
3236                 {
3237                   queue_free(&dq);
3238                   queue_free(&dqs);
3239                   return;
3240                 }
3241               continue;
3242             }
3243           /* all branches done, we're finally finished */
3244           break;
3245         }
3246
3247       /* minimization step */
3248      if (solv->branches.count)
3249         {
3250           int l = 0, lasti = -1, lastl = -1;
3251           Id why;
3252
3253           p = 0;
3254           for (i = solv->branches.count - 1; i >= 0; i--)
3255             {
3256               p = solv->branches.elements[i];
3257               if (p < 0)
3258                 l = -p;
3259               else if (p > 0 && solv->decisionmap[p] > l + 1)
3260                 {
3261                   lasti = i;
3262                   lastl = l;
3263                 }
3264             }
3265           if (lasti >= 0)
3266             {
3267               /* kill old solvable so that we do not loop */
3268               p = solv->branches.elements[lasti];
3269               solv->branches.elements[lasti] = 0;
3270               POOL_DEBUG(SAT_DEBUG_STATS, "minimizing %d -> %d with %s\n", solv->decisionmap[p], lastl, solvable2str(pool, pool->solvables + p));
3271               minimizationsteps++;
3272
3273               level = lastl;
3274               revert(solv, level);
3275               why = -solv->decisionq_why.elements[solv->decisionq_why.count];
3276               assert(why >= 0);
3277               olevel = level;
3278               level = setpropagatelearn(solv, level, p, disablerules, why);
3279               if (level == 0)
3280                 {
3281                   queue_free(&dq);
3282                   queue_free(&dqs);
3283                   return;
3284                 }
3285               continue;
3286             }
3287         }
3288       break;
3289     }
3290   POOL_DEBUG(SAT_DEBUG_STATS, "solver statistics: %d learned rules, %d unsolvable, %d minimization steps\n", solv->stats_learned, solv->stats_unsolvable, minimizationsteps);
3291
3292   POOL_DEBUG(SAT_DEBUG_STATS, "done solving.\n\n");
3293   queue_free(&dq);
3294   queue_free(&dqs);
3295 }
3296
3297
3298 /*-------------------------------------------------------------------
3299  *
3300  * refine_suggestion
3301  *
3302  * at this point, all rules that led to conflicts are disabled.
3303  * we re-enable all rules of a problem set but rule "sug", then
3304  * continue to disable more rules until there as again a solution.
3305  */
3306
3307 /* FIXME: think about conflicting assertions */
3308
3309 static void
3310 refine_suggestion(Solver *solv, Queue *job, Id *problem, Id sug, Queue *refined)
3311 {
3312   Pool *pool = solv->pool;
3313   int i, j;
3314   Id v;
3315   Queue disabled;
3316   int disabledcnt;
3317
3318   IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
3319     {
3320       POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "refine_suggestion start\n");
3321       for (i = 0; problem[i]; i++)
3322         {
3323           if (problem[i] == sug)
3324             POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "=> ");
3325           solver_printproblem(solv, problem[i]);
3326         }
3327     }
3328   queue_init(&disabled);
3329   queue_empty(refined);
3330   queue_push(refined, sug);
3331
3332   /* re-enable all problem rules with the exception of "sug"(gestion) */
3333   revert(solv, 1);
3334   reset_solver(solv);
3335
3336   for (i = 0; problem[i]; i++)
3337     if (problem[i] != sug)
3338       enableproblem(solv, problem[i]);
3339
3340   if (sug < 0)
3341     disableupdaterules(solv, job, -(sug + 1));
3342   else if (sug >= solv->updaterules && sug < solv->updaterules_end)
3343     {
3344       /* enable feature rule */
3345       Rule *r = solv->rules + solv->featurerules + (sug - solv->updaterules);
3346       if (r->p)
3347         enablerule(solv, r);
3348     }
3349
3350   enableweakrules(solv);
3351
3352   for (;;)
3353     {
3354       int njob, nfeature, nupdate;
3355       queue_empty(&solv->problems);
3356       revert(solv, 1);          /* XXX no longer needed? */
3357       reset_solver(solv);
3358
3359       if (!solv->problems.count)
3360         run_solver(solv, 0, 0);
3361
3362       if (!solv->problems.count)
3363         {
3364           POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "no more problems!\n");
3365           IF_POOLDEBUG (SAT_DEBUG_SCHUBI)
3366             solver_printdecisions(solv);
3367           break;                /* great, no more problems */
3368         }
3369       disabledcnt = disabled.count;
3370       /* start with 1 to skip over proof index */
3371       njob = nfeature = nupdate = 0;
3372       for (i = 1; i < solv->problems.count - 1; i++)
3373         {
3374           /* ignore solutions in refined */
3375           v = solv->problems.elements[i];
3376           if (v == 0)
3377             break;      /* end of problem reached */
3378           for (j = 0; problem[j]; j++)
3379             if (problem[j] != sug && problem[j] == v)
3380               break;
3381           if (problem[j])
3382             continue;
3383           if (v >= solv->featurerules && v < solv->featurerules_end)
3384             nfeature++;
3385           else if (v > 0)
3386             nupdate++;
3387           else
3388             {
3389               if ((job->elements[-v -1] & SOLVER_ESSENTIAL) != 0)
3390                 continue;       /* not that one! */
3391               njob++;
3392             }
3393           queue_push(&disabled, v);
3394         }
3395       if (disabled.count == disabledcnt)
3396         {
3397           /* no solution found, this was an invalid suggestion! */
3398           POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "no solution found!\n");
3399           refined->count = 0;
3400           break;
3401         }
3402       if (!njob && nupdate && nfeature)
3403         {
3404           /* got only update rules, filter out feature rules */
3405           POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "throwing away feature rules\n");
3406           for (i = j = disabledcnt; i < disabled.count; i++)
3407             {
3408               v = disabled.elements[i];
3409               if (v < solv->featurerules || v >= solv->featurerules_end)
3410                 disabled.elements[j++] = v;
3411             }
3412           disabled.count = j;
3413           nfeature = 0;
3414         }
3415       if (disabled.count == disabledcnt + 1)
3416         {
3417           /* just one suggestion, add it to refined list */
3418           v = disabled.elements[disabledcnt];
3419           if (!nfeature)
3420             queue_push(refined, v);     /* do not record feature rules */
3421           disableproblem(solv, v);
3422           if (v >= solv->updaterules && v < solv->updaterules_end)
3423             {
3424               Rule *r = solv->rules + (v - solv->updaterules + solv->featurerules);
3425               if (r->p)
3426                 enablerule(solv, r);    /* enable corresponding feature rule */
3427             }
3428           if (v < 0)
3429             disableupdaterules(solv, job, -(v + 1));
3430         }
3431       else
3432         {
3433           /* more than one solution, disable all */
3434           /* do not push anything on refine list, as we do not know which solution to choose */
3435           /* thus, the user will get another problem if he selects this solution, where he
3436            * can choose the right one */
3437           IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
3438             {
3439               POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "more than one solution found:\n");
3440               for (i = disabledcnt; i < disabled.count; i++)
3441                 solver_printproblem(solv, disabled.elements[i]);
3442             }
3443           for (i = disabledcnt; i < disabled.count; i++)
3444             {
3445               v = disabled.elements[i];
3446               disableproblem(solv, v);
3447               if (v >= solv->updaterules && v < solv->updaterules_end)
3448                 {
3449                   Rule *r = solv->rules + (v - solv->updaterules + solv->featurerules);
3450                   if (r->p)
3451                     enablerule(solv, r);
3452                 }
3453             }
3454         }
3455     }
3456   /* all done, get us back into the same state as before */
3457   /* enable refined rules again */
3458   for (i = 0; i < disabled.count; i++)
3459     enableproblem(solv, disabled.elements[i]);
3460   queue_free(&disabled);
3461   /* disable problem rules again */
3462
3463   /* FIXME! */
3464   for (i = 0; problem[i]; i++)
3465     enableproblem(solv, problem[i]);
3466   disableupdaterules(solv, job, -1);
3467
3468   /* disable problem rules again */
3469   for (i = 0; problem[i]; i++)
3470     disableproblem(solv, problem[i]);
3471   POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "refine_suggestion end\n");
3472 }
3473
3474
3475 /*-------------------------------------------------------------------
3476  * sorting helper for problems
3477  *
3478  * bring update rules before job rules
3479  * make essential job rules last
3480  */
3481
3482 Queue *problems_sort_data;
3483
3484 static int
3485 problems_sortcmp(const void *ap, const void *bp)
3486 {
3487   Id a = *(Id *)ap, b = *(Id *)bp;
3488   if (a < 0 && b > 0)
3489     return 1;
3490   if (a > 0 && b < 0)
3491     return -1;
3492   if (a < 0 && b < 0)
3493     {
3494       Queue *job = problems_sort_data;
3495       int af = job->elements[-a - 1] & SOLVER_ESSENTIAL;
3496       int bf = job->elements[-b - 1] & SOLVER_ESSENTIAL;
3497       int x = af - bf;
3498       if (x)
3499         return x;
3500     }
3501   return a - b;
3502 }
3503
3504
3505 /*-------------------------------------------------------------------
3506  * sort problems
3507  */
3508
3509 static void
3510 problems_sort(Solver *solv, Queue *job)
3511 {
3512   int i, j;
3513   if (!solv->problems.count)
3514     return;
3515   for (i = j = 1; i < solv->problems.count; i++)
3516     {
3517       if (!solv->problems.elements[i])
3518         {
3519           if (i > j + 1)
3520             {
3521               problems_sort_data = job;
3522               qsort(solv->problems.elements + j, i - j, sizeof(Id), problems_sortcmp);
3523             }
3524           if (++i == solv->problems.count)
3525             break;
3526           j = i + 1;
3527         }
3528     }
3529 }
3530
3531
3532 /*-------------------------------------------------------------------
3533  * convert problems to solutions
3534  */
3535
3536 static void
3537 problems_to_solutions(Solver *solv, Queue *job)
3538 {
3539   Pool *pool = solv->pool;
3540   Queue problems;
3541   Queue solution;
3542   Queue solutions;
3543   Id *problem;
3544   Id why;
3545   int i, j, nsol, probsolved;
3546   unsigned int now, refnow;
3547
3548   if (!solv->problems.count)
3549     return;
3550   now = sat_timems(0);
3551   problems_sort(solv, job);
3552   queue_clone(&problems, &solv->problems);
3553   queue_init(&solution);
3554   queue_init(&solutions);
3555   /* copy over proof index */
3556   queue_push(&solutions, problems.elements[0]);
3557   problem = problems.elements + 1;
3558   probsolved = 0;
3559   refnow = sat_timems(0);
3560   for (i = 1; i < problems.count; i++)
3561     {
3562       Id v = problems.elements[i];
3563       if (v == 0)
3564         {
3565           /* mark end of this problem */
3566           queue_push(&solutions, 0);
3567           queue_push(&solutions, 0);
3568           POOL_DEBUG(SAT_DEBUG_STATS, "refining took %d ms\n", sat_timems(refnow));
3569           if (i + 1 == problems.count)
3570             break;
3571           /* copy over proof of next problem */
3572           queue_push(&solutions, problems.elements[i + 1]);
3573           i++;
3574           problem = problems.elements + i + 1;
3575           refnow = sat_timems(0);
3576           probsolved = 0;
3577           continue;
3578         }
3579       if (v < 0 && (job->elements[-v - 1] & SOLVER_ESSENTIAL))
3580         {
3581           /* essential job, skip if we already have a non-essential
3582              solution */
3583           if (probsolved > 0)
3584             continue;
3585           probsolved = -1;      /* show all solutions */
3586         }
3587       refine_suggestion(solv, job, problem, v, &solution);
3588       if (!solution.count)
3589         continue;       /* this solution didn't work out */
3590
3591       nsol = 0;
3592       for (j = 0; j < solution.count; j++)
3593         {
3594           why = solution.elements[j];
3595           /* must be either job descriptor or update rule */
3596 #if 0
3597           solver_printproblem(solv, why);
3598 #endif
3599           if (why < 0)
3600             {
3601               /* job descriptor */
3602               queue_push(&solutions, 0);
3603               queue_push(&solutions, -why);
3604             }
3605           else if (why >= solv->infarchrules && why < solv->infarchrules_end)
3606             {
3607               Id p, name;
3608               /* infarch rule, find replacement */
3609               assert(solv->rules[why].p < 0);
3610               name = pool->solvables[-solv->rules[why].p].name;
3611               while (why >= solv->infarchrules && pool->solvables[-solv->rules[why - 1].p].name == name)
3612                 why--;
3613               p = 0;
3614               for (; why < solv->infarchrules_end && pool->solvables[-solv->rules[why].p].name == name; why++)
3615                 if (solv->decisionmap[-solv->rules[why].p] > 0)
3616                   {
3617                     p = -solv->rules[why].p;
3618                     break;
3619                   }
3620               if (!p)
3621                 p = -solv->rules[why].p; /* XXX: what to do here? */
3622               queue_push(&solutions, SOLVER_SOLUTION_INFARCH);
3623               queue_push(&solutions, p);
3624             }
3625           else if (why >= solv->duprules && why < solv->duprules_end)
3626             {
3627               Id p, name;
3628               /* dist upgrade rule, find replacement */
3629               assert(solv->rules[why].p < 0);
3630               name = pool->solvables[-solv->rules[why].p].name;
3631               while (why >= solv->infarchrules && pool->solvables[-solv->rules[why - 1].p].name == name)
3632                 why--;
3633               p = 0;
3634               for (; why < solv->infarchrules_end && pool->solvables[-solv->rules[why].p].name == name; why++)
3635                 if (solv->decisionmap[-solv->rules[why].p] > 0)
3636                   {
3637                     p = -solv->rules[why].p;
3638                     break;
3639                   }
3640               if (!p)
3641                 p = -solv->rules[why].p; /* XXX: what to do here? */
3642               queue_push(&solutions, SOLVER_SOLUTION_DISTUPGRADE);
3643               queue_push(&solutions, p);
3644             }
3645           else
3646             {
3647               /* update rule, find replacement package */
3648               Id p, *dp, rp = 0;
3649               Rule *rr;
3650
3651               assert(why >= solv->updaterules && why < solv->updaterules_end);
3652               /* check if this is a false positive, i.e. the update rule is fulfilled */
3653               rr = solv->rules + why;
3654               FOR_RULELITERALS(p, dp, rr)
3655                 if (p > 0 && solv->decisionmap[p] > 0)
3656                   break;
3657               if (p)
3658                 continue;       /* false alarm */
3659
3660               p = solv->installed->start + (why - solv->updaterules);
3661               rr = solv->rules + solv->featurerules + (why - solv->updaterules);
3662               if (!rr->p)
3663                 rr = solv->rules + why;
3664               if (solv->distupgrade && solv->rules[why].p != p && solv->decisionmap[p] > 0)
3665                 {
3666                   /* distupgrade case, allow to keep old package */
3667                   queue_push(&solutions, p);
3668                   queue_push(&solutions, p);
3669                   nsol++;
3670                   continue;
3671                 }
3672               if (solv->decisionmap[p] > 0)
3673                 continue;       /* false alarm, turned out we can keep the package */
3674               if (rr->w2)
3675                 {
3676                   int mvrp = 0;         /* multi-version replacement */
3677                   FOR_RULELITERALS(rp, dp, rr)
3678                     {
3679                       if (rp > 0 && solv->decisionmap[rp] > 0 && pool->solvables[rp].repo != solv->installed)
3680                         {
3681                           mvrp = rp;
3682                           if (!(solv->noobsoletes.size && MAPTST(&solv->noobsoletes, rp)))
3683                             break;
3684                         }
3685                     }
3686                   if (!rp && mvrp)
3687                     {
3688                       /* found only multi-version replacements */
3689                       /* have to split solution into two parts */
3690                       queue_push(&solutions, p);
3691                       queue_push(&solutions, mvrp);
3692                       nsol++;
3693                     }
3694                 }
3695               queue_push(&solutions, p);
3696               queue_push(&solutions, rp);
3697             }
3698           nsol++;
3699         }
3700       /* mark end of this solution */
3701       if (nsol)
3702         {
3703           if (!probsolved)
3704             probsolved = 1;
3705           queue_push(&solutions, 0);
3706           queue_push(&solutions, 0);
3707         }
3708       else
3709         {
3710           POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "Oops, everything was fine?\n");
3711         }
3712     }
3713   queue_free(&solution);
3714   queue_free(&problems);
3715   /* copy queue over to solutions */
3716   queue_free(&solv->problems);
3717   queue_clone(&solv->problems, &solutions);
3718
3719   /* bring solver back into problem state */
3720   revert(solv, 1);              /* XXX move to reset_solver? */
3721   reset_solver(solv);
3722
3723   assert(solv->problems.count == solutions.count);
3724   queue_free(&solutions);
3725   POOL_DEBUG(SAT_DEBUG_STATS, "problems_to_solutions took %d ms\n", sat_timems(now));
3726 }
3727
3728
3729 /*-------------------------------------------------------------------
3730  *
3731  * problem iterator
3732  *
3733  * advance to next problem
3734  */
3735
3736 Id
3737 solver_next_problem(Solver *solv, Id problem)
3738 {
3739   Id *pp;
3740   if (problem == 0)
3741     return solv->problems.count ? 1 : 0;
3742   pp = solv->problems.elements + problem;
3743   while (pp[0] || pp[1])
3744     {
3745       /* solution */
3746       pp += 2;
3747       while (pp[0] || pp[1])
3748         pp += 2;
3749       pp += 2;
3750     }
3751   pp += 2;
3752   problem = pp - solv->problems.elements;
3753   if (problem >= solv->problems.count)
3754     return 0;
3755   return problem + 1;
3756 }
3757
3758
3759 /*-------------------------------------------------------------------
3760  *
3761  * solution iterator
3762  */
3763
3764 Id
3765 solver_next_solution(Solver *solv, Id problem, Id solution)
3766 {
3767   Id *pp;
3768   if (solution == 0)
3769     {
3770       solution = problem;
3771       pp = solv->problems.elements + solution;
3772       return pp[0] || pp[1] ? solution : 0;
3773     }
3774   pp = solv->problems.elements + solution;
3775   while (pp[0] || pp[1])
3776     pp += 2;
3777   pp += 2;
3778   solution = pp - solv->problems.elements;
3779   return pp[0] || pp[1] ? solution : 0;
3780 }
3781
3782
3783 /*-------------------------------------------------------------------
3784  *
3785  * solution element iterator
3786  */
3787
3788 Id
3789 solver_next_solutionelement(Solver *solv, Id problem, Id solution, Id element, Id *p, Id *rp)
3790 {
3791   Id *pp;
3792   element = element ? element + 2 : solution;
3793   pp = solv->problems.elements + element;
3794   if (!(pp[0] || pp[1]))
3795     return 0;
3796   *p = pp[0];
3797   *rp = pp[1];
3798   return element;
3799 }
3800
3801
3802 /*-------------------------------------------------------------------
3803  *
3804  * Retrieve information about a problematic rule
3805  *
3806  * this is basically the reverse of addrpmrulesforsolvable
3807  */
3808
3809 SolverProbleminfo
3810 solver_problemruleinfo(Solver *solv, Queue *job, Id rid, Id *depp, Id *sourcep, Id *targetp)
3811 {
3812   Pool *pool = solv->pool;
3813   Repo *installed = solv->installed;
3814   Rule *r;
3815   Solvable *s;
3816   int dontfix = 0;
3817   Id p, d, w2, pp, req, *reqp, con, *conp, obs, *obsp, *dp;
3818
3819   assert(rid > 0);
3820   if (rid >= solv->infarchrules && rid < solv->infarchrules_end)
3821     {
3822       r = solv->rules + rid;
3823       *depp = r->p < 0 ? pool->solvables[-r->p].name : 0;
3824       *sourcep = r->p < 0 ? -r->p : 0;
3825       *targetp = 0;
3826       return SOLVER_PROBLEM_INFARCH_RULE;
3827     }
3828   if (rid >= solv->duprules && rid < solv->duprules_end)
3829     {
3830       r = solv->rules + rid;
3831       *depp = r->p < 0 ? pool->solvables[-r->p].name : 0;
3832       *sourcep = r->p < 0 ? -r->p : 0;
3833       *targetp = 0;
3834       return SOLVER_PROBLEM_DISTUPGRADE_RULE;
3835     }
3836   if (rid >= solv->jobrules && rid < solv->jobrules_end)
3837     {
3838
3839       r = solv->rules + rid;
3840       p = solv->ruletojob.elements[rid - solv->jobrules];
3841       *depp = job->elements[p + 1];
3842       *sourcep = p;
3843       *targetp = job->elements[p];
3844       d = r->d < 0 ? -r->d - 1 : r->d;
3845       if (d == 0 && r->w2 == 0 && r->p == -SYSTEMSOLVABLE && (job->elements[p] & SOLVER_SELECTMASK) != SOLVER_SOLVABLE_ONE_OF)
3846         return SOLVER_PROBLEM_JOB_NOTHING_PROVIDES_DEP;
3847       return SOLVER_PROBLEM_JOB_RULE;
3848     }
3849   if (rid >= solv->updaterules && rid < solv->updaterules_end)
3850     {
3851       *depp = 0;
3852       *sourcep = solv->installed->start + (rid - solv->updaterules);
3853       *targetp = 0;
3854       return SOLVER_PROBLEM_UPDATE_RULE;
3855     }
3856   assert(rid < solv->rpmrules_end);
3857   r = solv->rules + rid;
3858   assert(r->p < 0);
3859   d = r->d < 0 ? -r->d - 1 : r->d;
3860   if (d == 0 && r->w2 == 0)
3861     {
3862       /* a rpm rule assertion */
3863       s = pool->solvables - r->p;
3864       if (installed && !solv->fixsystem && s->repo == installed)
3865         dontfix = 1;
3866       assert(!dontfix); /* dontfix packages never have a neg assertion */
3867       *sourcep = -r->p;
3868       *targetp = 0;
3869       /* see why the package is not installable */
3870       if (s->arch != ARCH_SRC && s->arch != ARCH_NOSRC && !pool_installable(pool, s))
3871         {
3872           *depp = 0;
3873           return SOLVER_PROBLEM_NOT_INSTALLABLE;
3874         }
3875       /* check requires */
3876       if (s->requires)
3877         {
3878           reqp = s->repo->idarraydata + s->requires;
3879           while ((req = *reqp++) != 0)
3880             {
3881               if (req == SOLVABLE_PREREQMARKER)
3882                 continue;
3883               dp = pool->whatprovidesdata + pool_whatprovides(pool, req);
3884               if (*dp == 0)
3885                 break;
3886             }
3887           if (req)
3888             {
3889               *depp = req;
3890               return SOLVER_PROBLEM_NOTHING_PROVIDES_DEP;
3891             }
3892         }
3893       if (!solv->allowselfconflicts && s->conflicts)
3894         {
3895           conp = s->repo->idarraydata + s->conflicts;
3896           while ((con = *conp++) != 0)
3897             FOR_PROVIDES(p, pp, con)
3898               if (p == -r->p)
3899                 {
3900                   *depp = con;
3901                   return SOLVER_PROBLEM_SELF_CONFLICT;
3902                 }
3903         }
3904       /* should never happen */
3905       *depp = 0;
3906       return SOLVER_PROBLEM_RPM_RULE;
3907     }
3908   s = pool->solvables - r->p;
3909   if (installed && !solv->fixsystem && s->repo == installed)
3910     dontfix = 1;
3911   w2 = r->w2;
3912   if (d && pool->whatprovidesdata[d] < 0)
3913     {
3914       /* rule looks like -p|-c|x|x|x..., we only create this for patches with multiversion */
3915       /* reduce it to -p|-c case */
3916       d = 0;
3917       w2 = pool->whatprovidesdata[d];
3918     }
3919   if (d == 0 && w2 < 0)
3920     {
3921       /* a package conflict */
3922       Solvable *s2 = pool->solvables - w2;
3923       int dontfix2 = 0;
3924
3925       if (installed && !solv->fixsystem && s2->repo == installed)
3926         dontfix2 = 1;
3927
3928       /* if both packages have the same name and at least one of them
3929        * is not installed, they conflict */
3930       if (s->name == s2->name && !(installed && s->repo == installed && s2->repo == installed))
3931         {
3932           /* also check noobsoletes map */
3933           if ((s->evr == s2->evr && s->arch == s2->arch) || !solv->noobsoletes.size
3934                 || ((!installed || s->repo != installed) && !MAPTST(&solv->noobsoletes, -r->p))
3935                 || ((!installed || s2->repo != installed) && !MAPTST(&solv->noobsoletes, -w2)))
3936             {
3937               *depp = 0;
3938               *sourcep = -r->p;
3939               *targetp = -w2;
3940               return SOLVER_PROBLEM_SAME_NAME;
3941             }
3942         }
3943
3944       /* check conflicts in both directions */
3945       if (s->conflicts)
3946         {
3947           conp = s->repo->idarraydata + s->conflicts;
3948           while ((con = *conp++) != 0)
3949             {
3950               FOR_PROVIDES(p, pp, con)
3951                 {
3952                   if (dontfix && pool->solvables[p].repo == installed)
3953                     continue;
3954                   if (p != -w2)
3955                     continue;
3956                   *depp = con;
3957                   *sourcep = -r->p;
3958                   *targetp = p;
3959                   return SOLVER_PROBLEM_PACKAGE_CONFLICT;
3960                 }
3961             }
3962         }
3963       if (s2->conflicts)
3964         {
3965           conp = s2->repo->idarraydata + s2->conflicts;
3966           while ((con = *conp++) != 0)
3967             {
3968               FOR_PROVIDES(p, pp, con)
3969                 {
3970                   if (dontfix2 && pool->solvables[p].repo == installed)
3971                     continue;
3972                   if (p != -r->p)
3973                     continue;
3974                   *depp = con;
3975                   *sourcep = -w2;
3976                   *targetp = p;
3977                   return SOLVER_PROBLEM_PACKAGE_CONFLICT;
3978                 }
3979             }
3980         }
3981       /* check obsoletes in both directions */
3982       if ((!installed || s->repo != installed) && s->obsoletes && !(solv->noobsoletes.size && MAPTST(&solv->noobsoletes, -r->p)))
3983         {
3984           obsp = s->repo->idarraydata + s->obsoletes;
3985           while ((obs = *obsp++) != 0)
3986             {
3987               FOR_PROVIDES(p, pp, obs)
3988                 {
3989                   if (p != -w2)
3990                     continue;
3991                   if (!solv->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p, obs))
3992                     continue;
3993                   *depp = obs;
3994                   *sourcep = -r->p;
3995                   *targetp = p;
3996                   return SOLVER_PROBLEM_PACKAGE_OBSOLETES;
3997                 }
3998             }
3999         }
4000       if ((!installed || s2->repo != installed) && s2->obsoletes && !(solv->noobsoletes.size && MAPTST(&solv->noobsoletes, -w2)))
4001         {
4002           obsp = s2->repo->idarraydata + s2->obsoletes;
4003           while ((obs = *obsp++) != 0)
4004             {
4005               FOR_PROVIDES(p, pp, obs)
4006                 {
4007                   if (p != -r->p)
4008                     continue;
4009                   if (!solv->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p, obs))
4010                     continue;
4011                   *depp = obs;
4012                   *sourcep = -w2;
4013                   *targetp = p;
4014                   return SOLVER_PROBLEM_PACKAGE_OBSOLETES;
4015                 }
4016             }
4017         }
4018       if (solv->implicitobsoleteusesprovides && (!installed || s->repo != installed) && !(solv->noobsoletes.size && MAPTST(&solv->noobsoletes, -r->p)))
4019         {
4020           FOR_PROVIDES(p, pp, s->name)
4021             {
4022               if (p != -w2)
4023                 continue;
4024               *depp = s->name;
4025               *sourcep = -r->p;
4026               *targetp = p;
4027               return SOLVER_PROBLEM_PACKAGE_OBSOLETES;
4028             }
4029         }
4030       if (solv->implicitobsoleteusesprovides && (!installed || s2->repo != installed) && !(solv->noobsoletes.size && MAPTST(&solv->noobsoletes, -w2)))
4031         {
4032           FOR_PROVIDES(p, pp, s2->name)
4033             {
4034               if (p != -r->p)
4035                 continue;
4036               *depp = s2->name;
4037               *sourcep = -w2;
4038               *targetp = p;
4039               return SOLVER_PROBLEM_PACKAGE_OBSOLETES;
4040             }
4041         }
4042       /* all cases checked, can't happen */
4043       *depp = 0;
4044       *sourcep = -r->p;
4045       *targetp = 0;
4046       return SOLVER_PROBLEM_RPM_RULE;
4047     }
4048   /* simple requires */
4049   if (s->requires)
4050     {
4051       reqp = s->repo->idarraydata + s->requires;
4052       while ((req = *reqp++) != 0)
4053         {
4054           if (req == SOLVABLE_PREREQMARKER)
4055             continue;
4056           dp = pool->whatprovidesdata + pool_whatprovides(pool, req);
4057           if (d == 0)
4058             {
4059               if (*dp == r->w2 && dp[1] == 0)
4060                 break;
4061             }
4062           else if (dp - pool->whatprovidesdata == d)
4063             break;
4064         }
4065       if (req)
4066         {
4067           *depp = req;
4068           *sourcep = -r->p;
4069           *targetp = 0;
4070           return SOLVER_PROBLEM_DEP_PROVIDERS_NOT_INSTALLABLE;
4071         }
4072     }
4073
4074   /* check for product buddy requires */
4075   if (d == 0 && w2 > 0 && pool->nscallback)
4076     {
4077       Id buddy = 0;
4078       s = pool->solvables - r->p;
4079       if (!strncmp("product:", id2str(pool, s->name), 8))
4080         {
4081           buddy = pool->nscallback(pool, pool->nscallbackdata, NAMESPACE_PRODUCTBUDDY, -r->p);
4082           if (buddy != w2)
4083             buddy = 0;
4084         }
4085       if (!buddy)
4086         {
4087           s = pool->solvables + w2;
4088           if (!strncmp("product:", id2str(pool, s->name), 8))
4089             {
4090               buddy = pool->nscallback(pool, pool->nscallbackdata, NAMESPACE_PRODUCTBUDDY, w2);
4091               if (buddy != -r->p)
4092                 buddy = 0;
4093             }
4094         }
4095       if (buddy)
4096         {
4097           /* have buddy relation, now fake requires */
4098           s = pool->solvables + w2;
4099           Reldep *rd;
4100           if (s->repo && s->provides)
4101             {
4102               Id prov, *provp;
4103               provp = s->repo->idarraydata + s->provides;
4104               while ((prov = *provp++) != 0)
4105                 {
4106                   if (!ISRELDEP(prov))
4107                     continue;
4108                   rd = GETRELDEP(pool, prov);
4109                   if (rd->name == s->name && rd->evr == s->evr && rd->flags == REL_EQ)
4110                     {
4111                       *depp = prov;
4112                       *sourcep = -r->p;
4113                       *targetp = 0;
4114                       return SOLVER_PROBLEM_DEP_PROVIDERS_NOT_INSTALLABLE;
4115                     }
4116                 }
4117             }
4118           *depp = s->name;
4119           *sourcep = -r->p;
4120           *targetp = 0;
4121           return SOLVER_PROBLEM_DEP_PROVIDERS_NOT_INSTALLABLE;
4122         }
4123     }
4124
4125   /* all cases checked, can't happen */
4126   *depp = 0;
4127   *sourcep = -r->p;
4128   *targetp = 0;
4129   return SOLVER_PROBLEM_RPM_RULE;
4130 }
4131
4132
4133 /*-------------------------------------------------------------------
4134  *
4135  * find problem rule
4136  */
4137
4138 static void
4139 findproblemrule_internal(Solver *solv, Id idx, Id *reqrp, Id *conrp, Id *sysrp, Id *jobrp)
4140 {
4141   Id rid, d;
4142   Id lreqr, lconr, lsysr, ljobr;
4143   Rule *r;
4144   int reqassert = 0;
4145
4146   lreqr = lconr = lsysr = ljobr = 0;
4147   while ((rid = solv->learnt_pool.elements[idx++]) != 0)
4148     {
4149       assert(rid > 0);
4150       if (rid >= solv->learntrules)
4151         findproblemrule_internal(solv, solv->learnt_why.elements[rid - solv->learntrules], &lreqr, &lconr, &lsysr, &ljobr);
4152       else if ((rid >= solv->jobrules && rid < solv->jobrules_end) || (rid >= solv->infarchrules && rid < solv->infarchrules_end) || (rid >= solv->duprules && rid < solv->duprules_end))
4153         {
4154           if (!*jobrp)
4155             *jobrp = rid;
4156         }
4157       else if (rid >= solv->updaterules && rid < solv->updaterules_end)
4158         {
4159           if (!*sysrp)
4160             *sysrp = rid;
4161         }
4162       else
4163         {
4164           assert(rid < solv->rpmrules_end);
4165           r = solv->rules + rid;
4166           d = r->d < 0 ? -r->d - 1 : r->d;
4167           if (!d && r->w2 < 0)
4168             {
4169               if (!*conrp)
4170                 *conrp = rid;
4171             }
4172           else
4173             {
4174               if (!d && r->w2 == 0 && !reqassert)
4175                 {
4176                   if (*reqrp > 0 && r->p < -1)
4177                     {
4178                       Id op = -solv->rules[*reqrp].p;
4179                       if (op > 1 && solv->pool->solvables[op].arch != solv->pool->solvables[-r->p].arch)
4180                         continue;       /* different arch, skip */
4181                     }
4182                   /* prefer assertions */
4183                   *reqrp = rid;
4184                   reqassert = 1;
4185                 }
4186               if (!*reqrp)
4187                 *reqrp = rid;
4188               else if (solv->installed && r->p < 0 && solv->pool->solvables[-r->p].repo == solv->installed && !reqassert)
4189                 {
4190                   /* prefer rules of installed packages */
4191                   *reqrp = rid;
4192                 }
4193             }
4194         }
4195     }
4196   if (!*reqrp && lreqr)
4197     *reqrp = lreqr;
4198   if (!*conrp && lconr)
4199     *conrp = lconr;
4200   if (!*jobrp && ljobr)
4201     *jobrp = ljobr;
4202   if (!*sysrp && lsysr)
4203     *sysrp = lsysr;
4204 }
4205
4206
4207 /*-------------------------------------------------------------------
4208  *
4209  * find problem rule
4210  *
4211  * search for a rule that describes the problem to the
4212  * user. A pretty hopeless task, actually. We currently
4213  * prefer simple requires.
4214  */
4215
4216 Id
4217 solver_findproblemrule(Solver *solv, Id problem)
4218 {
4219   Id reqr, conr, sysr, jobr;
4220   Id idx = solv->problems.elements[problem - 1];
4221   reqr = conr = sysr = jobr = 0;
4222   findproblemrule_internal(solv, idx, &reqr, &conr, &sysr, &jobr);
4223   if (reqr)
4224     return reqr;
4225   if (conr)
4226     return conr;
4227   if (sysr)
4228     return sysr;
4229   if (jobr)
4230     return jobr;
4231   assert(0);
4232 }
4233
4234 static void
4235 findallproblemrules_internal(Solver *solv, Id idx, Queue *rules)
4236 {
4237   Id rid;
4238   while ((rid = solv->learnt_pool.elements[idx++]) != 0)
4239     {
4240       if (rid >= solv->learntrules)
4241         {
4242           findallproblemrules_internal(solv, solv->learnt_why.elements[rid - solv->learntrules], rules);
4243           continue;
4244         }
4245       queue_pushunique(rules, rid);
4246     }
4247 }
4248
4249 void
4250 solver_findallproblemrules(Solver *solv, Id problem, Queue *rules)
4251 {
4252   queue_empty(rules);
4253   findallproblemrules_internal(solv, solv->problems.elements[problem - 1], rules);
4254 }
4255
4256
4257 /*-------------------------------------------------------------------
4258  *
4259  * create reverse obsoletes map for installed solvables
4260  *
4261  * for each installed solvable find which packages with *different* names
4262  * obsolete the solvable.
4263  * this index is used in policy_findupdatepackages if noupdateprovide is set.
4264  */
4265
4266 static void
4267 create_obsolete_index(Solver *solv)
4268 {
4269   Pool *pool = solv->pool;
4270   Solvable *s;
4271   Repo *installed = solv->installed;
4272   Id p, pp, obs, *obsp, *obsoletes, *obsoletes_data;
4273   int i, n;
4274
4275   if (!installed || !installed->nsolvables)
4276     return;
4277   solv->obsoletes = obsoletes = sat_calloc(installed->end - installed->start, sizeof(Id));
4278   for (i = 1; i < pool->nsolvables; i++)
4279     {
4280       s = pool->solvables + i;
4281       if (!s->obsoletes)
4282         continue;
4283       if (!pool_installable(pool, s))
4284         continue;
4285       obsp = s->repo->idarraydata + s->obsoletes;
4286       while ((obs = *obsp++) != 0)
4287         {
4288           FOR_PROVIDES(p, pp, obs)
4289             {
4290               if (pool->solvables[p].repo != installed)
4291                 continue;
4292               if (pool->solvables[p].name == s->name)
4293                 continue;
4294               if (!solv->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p, obs))
4295                 continue;
4296               obsoletes[p - installed->start]++;
4297             }
4298         }
4299     }
4300   n = 0;
4301   for (i = 0; i < installed->nsolvables; i++)
4302     if (obsoletes[i])
4303       {
4304         n += obsoletes[i] + 1;
4305         obsoletes[i] = n;
4306       }
4307   solv->obsoletes_data = obsoletes_data = sat_calloc(n + 1, sizeof(Id));
4308   POOL_DEBUG(SAT_DEBUG_STATS, "obsoletes data: %d entries\n", n + 1);
4309   for (i = pool->nsolvables - 1; i > 0; i--)
4310     {
4311       s = pool->solvables + i;
4312       if (!s->obsoletes)
4313         continue;
4314       if (!pool_installable(pool, s))
4315         continue;
4316       obsp = s->repo->idarraydata + s->obsoletes;
4317       while ((obs = *obsp++) != 0)
4318         {
4319           FOR_PROVIDES(p, pp, obs)
4320             {
4321               if (pool->solvables[p].repo != installed)
4322                 continue;
4323               if (pool->solvables[p].name == s->name)
4324                 continue;
4325               if (!solv->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p, obs))
4326                 continue;
4327               p -= installed->start;
4328               if (obsoletes_data[obsoletes[p]] != i)
4329                 obsoletes_data[--obsoletes[p]] = i;
4330             }
4331         }
4332     }
4333 }
4334
4335
4336 /*-------------------------------------------------------------------
4337  *
4338  * remove disabled conflicts
4339  */
4340
4341 static void
4342 removedisabledconflicts(Solver *solv, Queue *removed)
4343 {
4344   Pool *pool = solv->pool;
4345   int i, n;
4346   Id p, why, *dp;
4347   Id new;
4348   Rule *r;
4349   Id *decisionmap = solv->decisionmap;
4350
4351   POOL_DEBUG(SAT_DEBUG_SCHUBI, "removedisabledconflicts\n");
4352   queue_empty(removed);
4353   for (i = 0; i < solv->decisionq.count; i++)
4354     {
4355       p = solv->decisionq.elements[i];
4356       if (p > 0)
4357         continue;
4358       /* a conflict. we never do conflicts on free decisions, so there
4359        * must have been an unit rule */
4360       why = solv->decisionq_why.elements[i];
4361       assert(why > 0);
4362       r = solv->rules + why;
4363       if (r->d < 0 && decisionmap[-p])
4364         {
4365           /* rule is now disabled, remove from decisionmap */
4366           POOL_DEBUG(SAT_DEBUG_SCHUBI, "removing conflict for package %s[%d]\n", solvable2str(pool, pool->solvables - p), -p);
4367           queue_push(removed, -p);
4368           queue_push(removed, decisionmap[-p]);
4369           decisionmap[-p] = 0;
4370         }
4371     }
4372   if (!removed->count)
4373     return;
4374   /* we removed some confliced packages. some of them might still
4375    * be in conflict, so search for unit rules and re-conflict */
4376   new = 0;
4377   for (i = n = 1, r = solv->rules + i; n < solv->nrules; i++, r++, n++)
4378     {
4379       if (i == solv->nrules)
4380         {
4381           i = 1;
4382           r = solv->rules + i;
4383         }
4384       if (r->d < 0)
4385         continue;
4386       if (!r->w2)
4387         {
4388           if (r->p < 0 && !decisionmap[-r->p])
4389             new = r->p;
4390         }
4391       else if (!r->d)
4392         {
4393           /* binary rule */
4394           if (r->p < 0 && decisionmap[-r->p] == 0 && DECISIONMAP_FALSE(r->w2))
4395             new = r->p;
4396           else if (r->w2 < 0 && decisionmap[-r->w2] == 0 && DECISIONMAP_FALSE(r->p))
4397             new = r->w2;
4398         }
4399       else
4400         {
4401           if (r->p < 0 && decisionmap[-r->p] == 0)
4402             new = r->p;
4403           if (new || DECISIONMAP_FALSE(r->p))
4404             {
4405               dp = pool->whatprovidesdata + r->d;
4406               while ((p = *dp++) != 0)
4407                 {
4408                   if (new && p == new)
4409                     continue;
4410                   if (p < 0 && decisionmap[-p] == 0)
4411                     {
4412                       if (new)
4413                         {
4414                           new = 0;
4415                           break;
4416                         }
4417                       new = p;
4418                     }
4419                   else if (!DECISIONMAP_FALSE(p))
4420                     {
4421                       new = 0;
4422                       break;
4423                     }
4424                 }
4425             }
4426         }
4427       if (new)
4428         {
4429           POOL_DEBUG(SAT_DEBUG_SCHUBI, "re-conflicting package %s[%d]\n", solvable2str(pool, pool->solvables - new), -new);
4430           decisionmap[-new] = -1;
4431           new = 0;
4432           n = 0;        /* redo all rules */
4433         }
4434     }
4435 }
4436
4437
4438 /*-------------------------------------------------------------------
4439  *
4440  * weaken solvable dependencies
4441  */
4442
4443 static void
4444 weaken_solvable_deps(Solver *solv, Id p)
4445 {
4446   int i;
4447   Rule *r;
4448
4449   for (i = 1, r = solv->rules + i; i < solv->rpmrules_end; i++, r++)
4450     {
4451       if (r->p != -p)
4452         continue;
4453       if ((r->d == 0 || r->d == -1) && r->w2 < 0)
4454         continue;       /* conflict */
4455       queue_push(&solv->weakruleq, i);
4456     }
4457 }
4458
4459 /********************************************************************/
4460 /* main() */
4461
4462
4463 static void
4464 addinfarchrules(Solver *solv, Map *addedmap)
4465 {
4466   Pool *pool = solv->pool;
4467   int first, i, j;
4468   Id p, pp, a, aa, bestarch;
4469   Solvable *s, *ps, *bests;
4470   Queue badq, allowedarchs;
4471
4472   queue_init(&badq);
4473   queue_init(&allowedarchs);
4474   solv->infarchrules = solv->nrules;
4475   for (i = 1; i < pool->nsolvables; i++)
4476     {
4477       if (i == SYSTEMSOLVABLE || !MAPTST(addedmap, i))
4478         continue;
4479       s = pool->solvables + i;
4480       first = i;
4481       bestarch = 0;
4482       bests = 0;
4483       queue_empty(&allowedarchs);
4484       FOR_PROVIDES(p, pp, s->name)
4485         {
4486           ps = pool->solvables + p;
4487           if (ps->name != s->name || !MAPTST(addedmap, p))
4488             continue;
4489           if (p == i)
4490             first = 0;
4491           if (first)
4492             break;
4493           a = ps->arch;
4494           a = (a <= pool->lastarch) ? pool->id2arch[a] : 0;
4495           if (a != 1 && pool->installed && ps->repo == pool->installed && !solv->distupgrade)
4496             {
4497               queue_pushunique(&allowedarchs, ps->arch);        /* also ok to keep this architecture */
4498               continue;         /* ignore installed solvables when calculating the best arch */
4499             }
4500           if (a && a != 1 && (!bestarch || a < bestarch))
4501             {
4502               bestarch = a;
4503               bests = ps;
4504             }
4505         }
4506       if (first)
4507         continue;
4508       /* speed up common case where installed package already has best arch */
4509       if (allowedarchs.count == 1 && bests && allowedarchs.elements[0] == bests->arch)
4510         allowedarchs.count--;   /* installed arch is best */
4511       queue_empty(&badq);
4512       FOR_PROVIDES(p, pp, s->name)
4513         {
4514           ps = pool->solvables + p;
4515           if (ps->name != s->name || !MAPTST(addedmap, p))
4516             continue;
4517           a = ps->arch;
4518           a = (a <= pool->lastarch) ? pool->id2arch[a] : 0;
4519           if (a != 1 && bestarch && ((a ^ bestarch) & 0xffff0000) != 0)
4520             {
4521               for (j = 0; j < allowedarchs.count; j++)
4522                 {
4523                   aa = allowedarchs.elements[j];
4524                   if (ps->arch == aa)
4525                     break;
4526                   aa = (aa <= pool->lastarch) ? pool->id2arch[aa] : 0;
4527                   if (aa && ((a ^ aa) & 0xffff0000) == 0)
4528                     break;      /* compatible */
4529                 }
4530               if (j == allowedarchs.count)
4531                 queue_push(&badq, p);
4532             }
4533         }
4534       if (!badq.count)
4535         continue;
4536       /* block all solvables in the badq! */
4537       for (j = 0; j < badq.count; j++)
4538         {
4539           p = badq.elements[j];
4540           addrule(solv, -p, 0);
4541         }
4542     }
4543   queue_free(&badq);
4544   queue_free(&allowedarchs);
4545   solv->infarchrules_end = solv->nrules;
4546 }
4547
4548 static void
4549 createdupmaps(Solver *solv, Queue *job)
4550 {
4551   Pool *pool = solv->pool;
4552   Repo *repo;
4553   Id how, what, p, pi, pp, obs, *obsp;
4554   Solvable *s, *ps;
4555   int i;
4556
4557   map_init(&solv->dupmap, pool->nsolvables);
4558   map_init(&solv->dupinvolvedmap, pool->nsolvables);
4559   for (i = 0; i < job->count; i += 2)
4560     {
4561       how = job->elements[i];
4562       what = job->elements[i + 1];
4563       switch (how & SOLVER_JOBMASK)
4564         {
4565         case SOLVER_DISTUPGRADE:
4566           if (what < 0 || what > pool->nrepos)
4567             break;
4568           repo = pool->repos[what];
4569           FOR_REPO_SOLVABLES(repo, p, s)
4570             {
4571               MAPSET(&solv->dupmap, p);
4572               FOR_PROVIDES(pi, pp, s->name)
4573                 {
4574                   ps = pool->solvables + pi;
4575                   if (ps->name != s->name)
4576                     continue;
4577                   MAPSET(&solv->dupinvolvedmap, pi);
4578                 }
4579               if (s->obsoletes)
4580                 {
4581                   /* FIXME: check obsoletes/provides combination */
4582                   obsp = s->repo->idarraydata + s->obsoletes;
4583                   while ((obs = *obsp++) != 0)
4584                     {
4585                       FOR_PROVIDES(pi, pp, obs)
4586                         {
4587                           if (!solv->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + pi, obs))
4588                             continue;
4589                           MAPSET(&solv->dupinvolvedmap, pi);
4590                         }
4591                     }
4592                 }
4593             }
4594           break;
4595         default:
4596           break;
4597         }
4598     }
4599   MAPCLR(&solv->dupinvolvedmap, SYSTEMSOLVABLE);
4600 }
4601
4602 static void
4603 freedupmaps(Solver *solv)
4604 {
4605   map_free(&solv->dupmap);
4606   map_free(&solv->dupinvolvedmap);
4607 }
4608
4609 static void
4610 addduprules(Solver *solv, Map *addedmap)
4611 {
4612   Pool *pool = solv->pool;
4613   Id p, pp;
4614   Solvable *s, *ps;
4615   int first, i;
4616
4617   solv->duprules = solv->nrules;
4618   for (i = 1; i < pool->nsolvables; i++)
4619     {
4620       if (i == SYSTEMSOLVABLE || !MAPTST(addedmap, i))
4621         continue;
4622       s = pool->solvables + i;
4623       first = i;
4624       FOR_PROVIDES(p, pp, s->name)
4625         {
4626           ps = pool->solvables + p;
4627           if (ps->name != s->name || !MAPTST(addedmap, p))
4628             continue;
4629           if (p == i)
4630             first = 0;
4631           if (first)
4632             break;
4633           if (!MAPTST(&solv->dupinvolvedmap, p))
4634             continue;
4635           if (solv->installed && ps->repo == solv->installed)
4636             {
4637               if (!solv->updatemap.size)
4638                 map_init(&solv->updatemap, pool->nsolvables);
4639               MAPSET(&solv->updatemap, p);
4640               if (!MAPTST(&solv->dupmap, p))
4641                 {
4642                   Id ip, ipp;
4643                   /* is installed identical to a good one? */
4644                   FOR_PROVIDES(ip, ipp, s->name)
4645                     {
4646                       Solvable *is = pool->solvables + ip;
4647                       if (!MAPTST(&solv->dupmap, ip))
4648                         continue;
4649                       if (is->evr == s->evr && solvable_identical(s, is))
4650                         break;
4651                     }
4652                   if (!ip)
4653                     addrule(solv, -p, 0);       /* no match, sorry */
4654                 }
4655             }
4656           else if (!MAPTST(&solv->dupmap, p))
4657             addrule(solv, -p, 0);
4658         }
4659     }
4660   solv->duprules_end = solv->nrules;
4661 }
4662
4663 /*
4664  *
4665  * solve job queue
4666  *
4667  */
4668
4669 void
4670 solver_solve(Solver *solv, Queue *job)
4671 {
4672   Pool *pool = solv->pool;
4673   Repo *installed = solv->installed;
4674   int i;
4675   int oldnrules;
4676   Map addedmap;                /* '1' == have rpm-rules for solvable */
4677   Map installcandidatemap;
4678   Id how, what, select, name, weak, p, pp, d;
4679   Queue q, redoq;
4680   Solvable *s;
4681   int goterase;
4682   Rule *r;
4683   int now, solve_start;
4684   int hasdupjob = 0;
4685
4686   solve_start = sat_timems(0);
4687   POOL_DEBUG(SAT_DEBUG_STATS, "solver started\n");
4688   POOL_DEBUG(SAT_DEBUG_STATS, "fixsystem=%d updatesystem=%d dosplitprovides=%d, noupdateprovide=%d\n", solv->fixsystem, solv->updatesystem, solv->dosplitprovides, solv->noupdateprovide);
4689   POOL_DEBUG(SAT_DEBUG_STATS, "distupgrade=%d distupgrade_removeunsupported=%d\n", solv->distupgrade, solv->distupgrade_removeunsupported);
4690   POOL_DEBUG(SAT_DEBUG_STATS, "allowuninstall=%d, allowdowngrade=%d, allowarchchange=%d, allowvendorchange=%d\n", solv->allowuninstall, solv->allowdowngrade, solv->allowarchchange, solv->allowvendorchange);
4691   POOL_DEBUG(SAT_DEBUG_STATS, "promoteepoch=%d, allowvirtualconflicts=%d, allowselfconflicts=%d\n", pool->promoteepoch, solv->allowvirtualconflicts, solv->allowselfconflicts);
4692   POOL_DEBUG(SAT_DEBUG_STATS, "obsoleteusesprovides=%d, implicitobsoleteusesprovides=%d\n", solv->obsoleteusesprovides, solv->implicitobsoleteusesprovides);
4693   POOL_DEBUG(SAT_DEBUG_STATS, "dontinstallrecommended=%d, ignorealreadyrecommended=%d, dontshowinstalledrecommended=%d\n", solv->dontinstallrecommended, solv->ignorealreadyrecommended, solv->dontshowinstalledrecommended);
4694   /* create whatprovides if not already there */
4695   if (!pool->whatprovides)
4696     pool_createwhatprovides(pool);
4697
4698   /* create obsolete index */
4699   create_obsolete_index(solv);
4700
4701   /* remember job */
4702   solv->job = job;
4703
4704   /*
4705    * create basic rule set of all involved packages
4706    * use addedmap bitmap to make sure we don't create rules twice
4707    *
4708    */
4709
4710   /* create noobsolete map if needed */
4711   for (i = 0; i < job->count; i += 2)
4712     {
4713       how = job->elements[i] & ~SOLVER_WEAK;
4714       if ((how & SOLVER_JOBMASK) != SOLVER_NOOBSOLETES)
4715         continue;
4716       what = job->elements[i + 1];
4717       select = how & SOLVER_SELECTMASK;
4718       if (!solv->noobsoletes.size)
4719         map_init(&solv->noobsoletes, pool->nsolvables);
4720       FOR_JOB_SELECT(p, pp, select, what)
4721         MAPSET(&solv->noobsoletes, p);
4722     }
4723
4724   map_init(&addedmap, pool->nsolvables);
4725   map_init(&installcandidatemap, pool->nsolvables);
4726   queue_init(&q);
4727
4728   /*
4729    * always install our system solvable
4730    */
4731   MAPSET(&addedmap, SYSTEMSOLVABLE);
4732   queue_push(&solv->decisionq, SYSTEMSOLVABLE);
4733   queue_push(&solv->decisionq_why, 0);
4734   solv->decisionmap[SYSTEMSOLVABLE] = 1; /* installed at level '1' */
4735
4736   now = sat_timems(0);
4737   /*
4738    * create rules for all package that could be involved with the solving
4739    * so called: rpm rules
4740    *
4741    */
4742   if (installed)
4743     {
4744       oldnrules = solv->nrules;
4745       POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for installed solvables ***\n");
4746       FOR_REPO_SOLVABLES(installed, p, s)
4747         addrpmrulesforsolvable(solv, s, &addedmap);
4748       POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for installed solvables\n", solv->nrules - oldnrules);
4749       POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for updaters of installed solvables ***\n");
4750       oldnrules = solv->nrules;
4751       FOR_REPO_SOLVABLES(installed, p, s)
4752         addrpmrulesforupdaters(solv, s, &addedmap, 1);
4753       POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for updaters of installed solvables\n", solv->nrules - oldnrules);
4754     }
4755
4756   /*
4757    * create rules for all packages involved in the job
4758    * (to be installed or removed)
4759    */
4760
4761   POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for packages involved with a job ***\n");
4762   oldnrules = solv->nrules;
4763   for (i = 0; i < job->count; i += 2)
4764     {
4765       how = job->elements[i];
4766       what = job->elements[i + 1];
4767       select = how & SOLVER_SELECTMASK;
4768
4769       switch (how & SOLVER_JOBMASK)
4770         {
4771         case SOLVER_INSTALL:
4772           FOR_JOB_SELECT(p, pp, select, what)
4773             {
4774               MAPSET(&installcandidatemap, p);
4775               addrpmrulesforsolvable(solv, pool->solvables + p, &addedmap);
4776             }
4777           break;
4778         case SOLVER_DISTUPGRADE:
4779           if (!solv->distupgrade)
4780             hasdupjob = 1;
4781           break;
4782         default:
4783           break;
4784         }
4785     }
4786   POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for packages involved in a job\n", solv->nrules - oldnrules);
4787
4788   POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for recommended/suggested packages ***\n");
4789
4790   oldnrules = solv->nrules;
4791
4792     /*
4793      * add rules for suggests, enhances
4794      */
4795   addrpmrulesforweak(solv, &addedmap);
4796   POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules because of weak dependencies\n", solv->nrules - oldnrules);
4797
4798   IF_POOLDEBUG (SAT_DEBUG_STATS)
4799     {
4800       int possible = 0, installable = 0;
4801       for (i = 1; i < pool->nsolvables; i++)
4802         {
4803           if (pool_installable(pool, pool->solvables + i))
4804             installable++;
4805           if (MAPTST(&addedmap, i))
4806             possible++;
4807         }
4808       POOL_DEBUG(SAT_DEBUG_STATS, "%d of %d installable solvables considered for solving\n", possible, installable);
4809     }
4810
4811   /*
4812    * first pass done, we now have all the rpm rules we need.
4813    * unify existing rules before going over all job rules and
4814    * policy rules.
4815    * at this point the system is always solvable,
4816    * as an empty system (remove all packages) is a valid solution
4817    */
4818
4819   unifyrules(solv);                               /* remove duplicate rpm rules */
4820
4821   solv->rpmrules_end = solv->nrules;              /* mark end of rpm rules */
4822
4823   solv->directdecisions = solv->decisionq.count;
4824   POOL_DEBUG(SAT_DEBUG_STATS, "rpm rule memory usage: %d K\n", solv->nrules * (int)sizeof(Rule) / 1024);
4825   POOL_DEBUG(SAT_DEBUG_STATS, "decisions so far: %d\n", solv->decisionq.count);
4826   POOL_DEBUG(SAT_DEBUG_STATS, "rpm rule creation took %d ms\n", sat_timems(now));
4827
4828   /* create dup maps if needed. We need the maps to create our
4829    * update rules */
4830   if (hasdupjob)
4831     createdupmaps(solv, job);
4832
4833   /*
4834    * create feature rules
4835    *
4836    * foreach installed:
4837    *   create assertion (keep installed, if no update available)
4838    *   or
4839    *   create update rule (A|update1(A)|update2(A)|...)
4840    *
4841    * those are used later on to keep a version of the installed packages in
4842    * best effort mode
4843    */
4844
4845   POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** Add feature rules ***\n");
4846   solv->featurerules = solv->nrules;              /* mark start of feature rules */
4847   if (installed)
4848     {
4849         /* foreach possibly installed solvable */
4850       for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
4851         {
4852           if (s->repo != installed)
4853             {
4854               addrule(solv, 0, 0);      /* create dummy rule */
4855               continue;
4856             }
4857           addupdaterule(solv, s, 1);    /* allow s to be updated */
4858         }
4859         /*
4860          * assert one rule per installed solvable,
4861          * either an assertion (A)
4862          * or a possible update (A|update1(A)|update2(A)|...)
4863          */
4864       assert(solv->nrules - solv->featurerules == installed->end - installed->start);
4865     }
4866   solv->featurerules_end = solv->nrules;
4867
4868     /*
4869      * Add update rules for installed solvables
4870      *
4871      * almost identical to feature rules
4872      * except that downgrades/archchanges/vendorchanges are not allowed
4873      */
4874
4875   POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** Add update rules ***\n");
4876   solv->updaterules = solv->nrules;
4877
4878   if (installed)
4879     { /* foreach installed solvables */
4880       /* we create all update rules, but disable some later on depending on the job */
4881       for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
4882         {
4883           Rule *sr;
4884
4885           if (s->repo != installed)
4886             {
4887               addrule(solv, 0, 0);      /* create dummy rule */
4888               continue;
4889             }
4890           addupdaterule(solv, s, 0);    /* allowall = 0: downgrades not allowed */
4891             /*
4892              * check for and remove duplicate
4893              */
4894           r = solv->rules + solv->nrules - 1;           /* r: update rule */
4895           sr = r - (installed->end - installed->start); /* sr: feature rule */
4896           /* it's orphaned if there is no feature rule or the feature rule
4897            * consists just of the installed package */
4898           if (!sr->p || (sr->p == i && !sr->d && !sr->w2))
4899             queue_push(&solv->orphaned, i);
4900           if (!r->p)
4901             {
4902               assert(solv->distupgrade && !sr->p);
4903               continue;
4904             }
4905           unifyrules_sortcmp_data = pool;
4906           if (!unifyrules_sortcmp(r, sr))
4907             {
4908               /* identical rule, kill unneeded one */
4909               if (solv->allowuninstall)
4910                 {
4911                   /* keep feature rule, make it weak */
4912                   memset(r, 0, sizeof(*r));
4913                   queue_push(&solv->weakruleq, sr - solv->rules);
4914                 }
4915               else
4916                 {
4917                   /* keep update rule */
4918                   memset(sr, 0, sizeof(*sr));
4919                 }
4920             }
4921           else if (solv->allowuninstall)
4922             {
4923               /* make both feature and update rule weak */
4924               queue_push(&solv->weakruleq, r - solv->rules);
4925               queue_push(&solv->weakruleq, sr - solv->rules);
4926             }
4927           else
4928             disablerule(solv, sr);
4929         }
4930       /* consistency check: we added a rule for _every_ installed solvable */
4931       assert(solv->nrules - solv->updaterules == installed->end - installed->start);
4932     }
4933   solv->updaterules_end = solv->nrules;
4934
4935
4936   /*
4937    * now add all job rules
4938    */
4939
4940   POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** Add JOB rules ***\n");
4941
4942   solv->jobrules = solv->nrules;
4943   for (i = 0; i < job->count; i += 2)
4944     {
4945       oldnrules = solv->nrules;
4946
4947       how = job->elements[i];
4948       what = job->elements[i + 1];
4949       weak = how & SOLVER_WEAK;
4950       select = how & SOLVER_SELECTMASK;
4951       switch (how & SOLVER_JOBMASK)
4952         {
4953         case SOLVER_INSTALL:
4954           POOL_DEBUG(SAT_DEBUG_JOB, "job: %sinstall %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
4955           if (select == SOLVER_SOLVABLE)
4956             {
4957               p = what;
4958               d = 0;
4959             }
4960           else
4961             {
4962               queue_empty(&q);
4963               FOR_JOB_SELECT(p, pp, select, what)
4964                 queue_push(&q, p);
4965               if (!q.count)
4966                 {
4967                   /* no candidate found, make this an impossible rule */
4968                   queue_push(&q, -SYSTEMSOLVABLE);
4969                 }
4970               p = queue_shift(&q);      /* get first candidate */
4971               d = !q.count ? 0 : pool_queuetowhatprovides(pool, &q);    /* internalize */
4972             }
4973           addrule(solv, p, d);          /* add install rule */
4974           queue_push(&solv->ruletojob, i);
4975           if (weak)
4976             queue_push(&solv->weakruleq, solv->nrules - 1);
4977           break;
4978         case SOLVER_ERASE:
4979           POOL_DEBUG(SAT_DEBUG_JOB, "job: %serase %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
4980           if (select == SOLVER_SOLVABLE && solv->installed && pool->solvables[what].repo == solv->installed)
4981             {
4982               /* special case for "erase a specific solvable": we also
4983                * erase all other solvables with that name, so that they
4984                * don't get picked up as replacement */
4985               name = pool->solvables[what].name;
4986               FOR_PROVIDES(p, pp, name)
4987                 {
4988                   if (p == what)
4989                     continue;
4990                   s = pool->solvables + p;
4991                   if (s->name != name)
4992                     continue;
4993                   /* keep other versions installed */
4994                   if (s->repo == solv->installed)
4995                     continue;
4996                   /* keep installcandidates of other jobs */
4997                   if (MAPTST(&installcandidatemap, p))
4998                     continue;
4999                   addrule(solv, -p, 0);                 /* remove by Id */
5000                   queue_push(&solv->ruletojob, i);
5001                   if (weak)
5002                     queue_push(&solv->weakruleq, solv->nrules - 1);
5003                 }
5004             }
5005           FOR_JOB_SELECT(p, pp, select, what)
5006             {
5007               addrule(solv, -p, 0);
5008               queue_push(&solv->ruletojob, i);
5009               if (weak)
5010                 queue_push(&solv->weakruleq, solv->nrules - 1);
5011             }
5012           break;
5013
5014         case SOLVER_UPDATE:
5015           POOL_DEBUG(SAT_DEBUG_JOB, "job: %supdate %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
5016           FOR_JOB_SELECT(p, pp, select, what)
5017             {
5018               s = pool->solvables + p;
5019               if (!solv->installed || s->repo != solv->installed)
5020                 continue;
5021               if (!solv->updatemap.size)
5022                 map_init(&solv->updatemap, pool->nsolvables);
5023               MAPSET(&solv->updatemap, p);
5024             }
5025           break;
5026         case SOLVER_WEAKENDEPS:
5027           POOL_DEBUG(SAT_DEBUG_JOB, "job: %sweaken deps %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
5028           if (select != SOLVER_SOLVABLE)
5029             break;
5030           s = pool->solvables + what;
5031           weaken_solvable_deps(solv, what);
5032           break;
5033         case SOLVER_NOOBSOLETES:
5034           POOL_DEBUG(SAT_DEBUG_JOB, "job: %sno obsolete %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
5035           break;
5036         case SOLVER_LOCK:
5037           POOL_DEBUG(SAT_DEBUG_JOB, "job: %slock %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
5038           FOR_JOB_SELECT(p, pp, select, what)
5039             {
5040               s = pool->solvables + p;
5041               if (installed && s->repo == installed)
5042                 addrule(solv, p, 0);
5043               else
5044                 addrule(solv, -p, 0);
5045               queue_push(&solv->ruletojob, i);
5046               if (weak)
5047                 queue_push(&solv->weakruleq, solv->nrules - 1);
5048             }
5049           break;
5050         case SOLVER_DISTUPGRADE:
5051           POOL_DEBUG(SAT_DEBUG_JOB, "job: distupgrade repo #%d\n", what);
5052           break;
5053         default:
5054           POOL_DEBUG(SAT_DEBUG_JOB, "job: unknown job\n");
5055           break;
5056         }
5057
5058         /*
5059          * debug
5060          */
5061
5062       IF_POOLDEBUG (SAT_DEBUG_JOB)
5063         {
5064           int j;
5065           if (solv->nrules == oldnrules)
5066             POOL_DEBUG(SAT_DEBUG_JOB, " - no rule created\n");
5067           for (j = oldnrules; j < solv->nrules; j++)
5068             {
5069               POOL_DEBUG(SAT_DEBUG_JOB, " - job ");
5070               solver_printrule(solv, SAT_DEBUG_JOB, solv->rules + j);
5071             }
5072         }
5073     }
5074   assert(solv->ruletojob.count == solv->nrules - solv->jobrules);
5075   solv->jobrules_end = solv->nrules;
5076
5077   /* now create infarch and dup rules */
5078   addinfarchrules(solv, &addedmap);
5079   if (hasdupjob)
5080     {
5081       addduprules(solv, &addedmap);
5082       freedupmaps(solv);        /* no longer needed */
5083     }
5084   else
5085     solv->duprules = solv->duprules_end = solv->nrules;
5086
5087     /* all rules created
5088      * --------------------------------------------------------------
5089      * prepare for solving
5090      */
5091
5092   /* free unneeded memory */
5093   map_free(&addedmap);
5094   map_free(&installcandidatemap);
5095   queue_free(&q);
5096
5097   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);
5098
5099   /* create weak map */
5100   map_init(&solv->weakrulemap, solv->nrules);
5101   for (i = 0; i < solv->weakruleq.count; i++)
5102     {
5103       p = solv->weakruleq.elements[i];
5104       MAPSET(&solv->weakrulemap, p);
5105     }
5106
5107   /* all new rules are learnt after this point */
5108   solv->learntrules = solv->nrules;
5109
5110   /* create assertion index. it is only used to speed up
5111    * makeruledecsions() a bit */
5112   for (i = 1, r = solv->rules + i; i < solv->nrules; i++, r++)
5113     if (r->p && !r->w2 && (r->d == 0 || r->d == -1))
5114       queue_push(&solv->ruleassertions, i);
5115
5116   /* disable update rules that conflict with our job */
5117   disableupdaterules(solv, job, -1);
5118
5119   /* make decisions based on job/update assertions */
5120   makeruledecisions(solv);
5121
5122   /* create watches chains */
5123   makewatches(solv);
5124
5125   POOL_DEBUG(SAT_DEBUG_STATS, "problems so far: %d\n", solv->problems.count);
5126
5127   /*
5128    * ********************************************
5129    * solve!
5130    * ********************************************
5131    */
5132
5133   now = sat_timems(0);
5134   run_solver(solv, 1, solv->dontinstallrecommended ? 0 : 1);
5135   POOL_DEBUG(SAT_DEBUG_STATS, "solver took %d ms\n", sat_timems(now));
5136
5137   queue_init(&redoq);
5138   goterase = 0;
5139   /* disable all erase jobs (including weak "keep uninstalled" rules) */
5140   for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++)
5141     {
5142       if (r->d < 0)     /* disabled ? */
5143         continue;
5144       if (r->p > 0)     /* install job? */
5145         continue;
5146       disablerule(solv, r);
5147       goterase++;
5148     }
5149
5150   if (goterase)
5151     {
5152       enabledisablelearntrules(solv);
5153       removedisabledconflicts(solv, &redoq);
5154     }
5155
5156   /*
5157    * find recommended packages
5158    */
5159
5160   /* if redoq.count == 0 we already found all recommended in the
5161    * solver run */
5162   if (redoq.count || solv->dontinstallrecommended || !solv->dontshowinstalledrecommended || solv->ignorealreadyrecommended)
5163     {
5164       Id rec, *recp, p, pp;
5165
5166       /* create map of all recommened packages */
5167       solv->recommends_index = -1;
5168       MAPZERO(&solv->recommendsmap);
5169       for (i = 0; i < solv->decisionq.count; i++)
5170         {
5171           p = solv->decisionq.elements[i];
5172           if (p < 0)
5173             continue;
5174           s = pool->solvables + p;
5175           if (s->recommends)
5176             {
5177               recp = s->repo->idarraydata + s->recommends;
5178               while ((rec = *recp++) != 0)
5179                 {
5180                   FOR_PROVIDES(p, pp, rec)
5181                     if (solv->decisionmap[p] > 0)
5182                       break;
5183                   if (p)
5184                     {
5185                       if (!solv->dontshowinstalledrecommended)
5186                         {
5187                           FOR_PROVIDES(p, pp, rec)
5188                             if (solv->decisionmap[p] > 0)
5189                               MAPSET(&solv->recommendsmap, p);
5190                         }
5191                       continue; /* p != 0: already fulfilled */
5192                     }
5193                   FOR_PROVIDES(p, pp, rec)
5194                     MAPSET(&solv->recommendsmap, p);
5195                 }
5196             }
5197         }
5198       for (i = 1; i < pool->nsolvables; i++)
5199         {
5200           if (solv->decisionmap[i] < 0)
5201             continue;
5202           if (solv->decisionmap[i] > 0 && solv->dontshowinstalledrecommended)
5203             continue;
5204           s = pool->solvables + i;
5205           if (!MAPTST(&solv->recommendsmap, i))
5206             {
5207               if (!s->supplements)
5208                 continue;
5209               if (!pool_installable(pool, s))
5210                 continue;
5211               if (!solver_is_supplementing(solv, s))
5212                 continue;
5213             }
5214           if (solv->dontinstallrecommended)
5215             queue_push(&solv->recommendations, i);
5216           else
5217             queue_pushunique(&solv->recommendations, i);
5218         }
5219       /* we use MODE_SUGGEST here so that repo prio is ignored */
5220       policy_filter_unwanted(solv, &solv->recommendations, POLICY_MODE_SUGGEST);
5221     }
5222
5223   /*
5224    * find suggested packages
5225    */
5226
5227   if (1)
5228     {
5229       Id sug, *sugp, p, pp;
5230
5231       /* create map of all suggests that are still open */
5232       solv->recommends_index = -1;
5233       MAPZERO(&solv->suggestsmap);
5234       for (i = 0; i < solv->decisionq.count; i++)
5235         {
5236           p = solv->decisionq.elements[i];
5237           if (p < 0)
5238             continue;
5239           s = pool->solvables + p;
5240           if (s->suggests)
5241             {
5242               sugp = s->repo->idarraydata + s->suggests;
5243               while ((sug = *sugp++) != 0)
5244                 {
5245                   FOR_PROVIDES(p, pp, sug)
5246                     if (solv->decisionmap[p] > 0)
5247                       break;
5248                   if (p)
5249                     {
5250                       if (!solv->dontshowinstalledrecommended)
5251                         {
5252                           FOR_PROVIDES(p, pp, sug)
5253                             if (solv->decisionmap[p] > 0)
5254                               MAPSET(&solv->suggestsmap, p);
5255                         }
5256                       continue; /* already fulfilled */
5257                     }
5258                   FOR_PROVIDES(p, pp, sug)
5259                     MAPSET(&solv->suggestsmap, p);
5260                 }
5261             }
5262         }
5263       for (i = 1; i < pool->nsolvables; i++)
5264         {
5265           if (solv->decisionmap[i] < 0)
5266             continue;
5267           if (solv->decisionmap[i] > 0 && solv->dontshowinstalledrecommended)
5268             continue;
5269           s = pool->solvables + i;
5270           if (!MAPTST(&solv->suggestsmap, i))
5271             {
5272               if (!s->enhances)
5273                 continue;
5274               if (!pool_installable(pool, s))
5275                 continue;
5276               if (!solver_is_enhancing(solv, s))
5277                 continue;
5278             }
5279           queue_push(&solv->suggestions, i);
5280         }
5281       policy_filter_unwanted(solv, &solv->suggestions, POLICY_MODE_SUGGEST);
5282     }
5283
5284   if (redoq.count)
5285     {
5286       /* restore decisionmap */
5287       for (i = 0; i < redoq.count; i += 2)
5288         solv->decisionmap[redoq.elements[i]] = redoq.elements[i + 1];
5289     }
5290
5291     /*
5292      * if unsolvable, prepare solutions
5293      */
5294
5295   if (solv->problems.count)
5296     {
5297       int recocount = solv->recommendations.count;
5298       solv->recommendations.count = 0;  /* so that revert() doesn't mess with it */
5299       queue_empty(&redoq);
5300       for (i = 0; i < solv->decisionq.count; i++)
5301         {
5302           Id p = solv->decisionq.elements[i];
5303           queue_push(&redoq, p);
5304           queue_push(&redoq, solv->decisionq_why.elements[i]);
5305           queue_push(&redoq, solv->decisionmap[p > 0 ? p : -p]);
5306         }
5307       problems_to_solutions(solv, job);
5308       memset(solv->decisionmap, 0, pool->nsolvables * sizeof(Id));
5309       queue_empty(&solv->decisionq);
5310       queue_empty(&solv->decisionq_why);
5311       for (i = 0; i < redoq.count; i += 3)
5312         {
5313           Id p = redoq.elements[i];
5314           queue_push(&solv->decisionq, p);
5315           queue_push(&solv->decisionq_why, redoq.elements[i + 1]);
5316           solv->decisionmap[p > 0 ? p : -p] = redoq.elements[i + 2];
5317         }
5318       solv->recommendations.count = recocount;
5319     }
5320
5321   queue_free(&redoq);
5322   POOL_DEBUG(SAT_DEBUG_STATS, "final solver statistics: %d learned rules, %d unsolvable\n", solv->stats_learned, solv->stats_unsolvable);
5323   POOL_DEBUG(SAT_DEBUG_STATS, "solver_solve took %d ms\n", sat_timems(solve_start));
5324   solv->job = 0;
5325 }
5326
5327 /***********************************************************************/
5328 /* disk usage computations */
5329
5330 /*-------------------------------------------------------------------
5331  *
5332  * calculate DU changes
5333  */
5334
5335 void
5336 solver_calc_duchanges(Solver *solv, DUChanges *mps, int nmps)
5337 {
5338   Map installedmap;
5339
5340   solver_create_state_maps(solv, &installedmap, 0);
5341   pool_calc_duchanges(solv->pool, &installedmap, mps, nmps);
5342   map_free(&installedmap);
5343 }
5344
5345
5346 /*-------------------------------------------------------------------
5347  *
5348  * calculate changes in install size
5349  */
5350
5351 int
5352 solver_calc_installsizechange(Solver *solv)
5353 {
5354   Map installedmap;
5355   int change;
5356
5357   solver_create_state_maps(solv, &installedmap, 0);
5358   change = pool_calc_installsizechange(solv->pool, &installedmap);
5359   map_free(&installedmap);
5360   return change;
5361 }
5362
5363 #define FIND_INVOLVED_DEBUG 0
5364 void
5365 solver_find_involved(Solver *solv, Queue *installedq, Solvable *ts, Queue *q)
5366 {
5367   Pool *pool = solv->pool;
5368   Map im;
5369   Map installedm;
5370   Solvable *s;
5371   Queue iq;
5372   Queue installedq_internal;
5373   Id tp, ip, p, pp, req, *reqp, sup, *supp;
5374   int i, count;
5375
5376   tp = ts - pool->solvables;
5377   queue_init(&iq);
5378   queue_init(&installedq_internal);
5379   map_init(&im, pool->nsolvables);
5380   map_init(&installedm, pool->nsolvables);
5381
5382   if (!installedq)
5383     {
5384       installedq = &installedq_internal;
5385       if (solv->installed)
5386         {
5387           for (ip = solv->installed->start; ip < solv->installed->end; ip++)
5388             {
5389               s = pool->solvables + ip;
5390               if (s->repo != solv->installed)
5391                 continue;
5392               queue_push(installedq, ip);
5393             }
5394         }
5395     }
5396   for (i = 0; i < installedq->count; i++)
5397     {
5398       ip = installedq->elements[i];
5399       MAPSET(&installedm, ip);
5400       MAPSET(&im, ip);
5401     }
5402
5403   queue_push(&iq, ts - pool->solvables);
5404   while (iq.count)
5405     {
5406       ip = queue_shift(&iq);
5407       if (!MAPTST(&im, ip))
5408         continue;
5409       if (!MAPTST(&installedm, ip))
5410         continue;
5411       MAPCLR(&im, ip);
5412       s = pool->solvables + ip;
5413 #if FIND_INVOLVED_DEBUG
5414       printf("hello %s\n", solvable2str(pool, s));
5415 #endif
5416       if (s->requires)
5417         {
5418           reqp = s->repo->idarraydata + s->requires;
5419           while ((req = *reqp++) != 0)
5420             {
5421               if (req == SOLVABLE_PREREQMARKER)
5422                 continue;
5423               /* count number of installed packages that match */
5424               count = 0;
5425               FOR_PROVIDES(p, pp, req)
5426                 if (MAPTST(&installedm, p))
5427                   count++;
5428               if (count > 1)
5429                 continue;
5430               FOR_PROVIDES(p, pp, req)
5431                 {
5432                   if (MAPTST(&im, p))
5433                     {
5434 #if FIND_INVOLVED_DEBUG
5435                       printf("%s requires %s\n", solvable2str(pool, pool->solvables + ip), solvable2str(pool, pool->solvables + p));
5436 #endif
5437                       queue_push(&iq, p);
5438                     }
5439                 }
5440             }
5441         }
5442       if (s->recommends)
5443         {
5444           reqp = s->repo->idarraydata + s->recommends;
5445           while ((req = *reqp++) != 0)
5446             {
5447               count = 0;
5448               FOR_PROVIDES(p, pp, req)
5449                 if (MAPTST(&installedm, p))
5450                   count++;
5451               if (count > 1)
5452                 continue;
5453               FOR_PROVIDES(p, pp, req)
5454                 {
5455                   if (MAPTST(&im, p))
5456                     {
5457 #if FIND_INVOLVED_DEBUG
5458                       printf("%s recommends %s\n", solvable2str(pool, pool->solvables + ip), solvable2str(pool, pool->solvables + p));
5459 #endif
5460                       queue_push(&iq, p);
5461                     }
5462                 }
5463             }
5464         }
5465       if (!iq.count)
5466         {
5467           /* supplements pass */
5468           for (i = 0; i < installedq->count; i++)
5469             {
5470               ip = installedq->elements[i];
5471               s = pool->solvables + ip;
5472               if (!s->supplements)
5473                 continue;
5474               if (!MAPTST(&im, ip))
5475                 continue;
5476               supp = s->repo->idarraydata + s->supplements;
5477               while ((sup = *supp++) != 0)
5478                 if (!dep_possible(solv, sup, &im) && dep_possible(solv, sup, &installedm))
5479                   break;
5480               /* no longer supplemented, also erase */
5481               if (sup)
5482                 {
5483 #if FIND_INVOLVED_DEBUG
5484                   printf("%s supplemented\n", solvable2str(pool, pool->solvables + ip));
5485 #endif
5486                   queue_push(&iq, ip);
5487                 }
5488             }
5489         }
5490     }
5491
5492   for (i = 0; i < installedq->count; i++)
5493     {
5494       ip = installedq->elements[i];
5495       if (MAPTST(&im, ip))
5496         queue_push(&iq, ip);
5497     }
5498
5499   while (iq.count)
5500     {
5501       ip = queue_shift(&iq);
5502       if (!MAPTST(&installedm, ip))
5503         continue;
5504       s = pool->solvables + ip;
5505 #if FIND_INVOLVED_DEBUG
5506       printf("bye %s\n", solvable2str(pool, s));
5507 #endif
5508       if (s->requires)
5509         {
5510           reqp = s->repo->idarraydata + s->requires;
5511           while ((req = *reqp++) != 0)
5512             {
5513               FOR_PROVIDES(p, pp, req)
5514                 {
5515                   if (!MAPTST(&im, p))
5516                     {
5517                       if (p == tp)
5518                         continue;
5519 #if FIND_INVOLVED_DEBUG
5520                       printf("%s requires %s\n", solvable2str(pool, pool->solvables + ip), solvable2str(pool, pool->solvables + p));
5521 #endif
5522                       MAPSET(&im, p);
5523                       queue_push(&iq, p);
5524                     }
5525                 }
5526             }
5527         }
5528       if (s->recommends)
5529         {
5530           reqp = s->repo->idarraydata + s->recommends;
5531           while ((req = *reqp++) != 0)
5532             {
5533               FOR_PROVIDES(p, pp, req)
5534                 {
5535                   if (!MAPTST(&im, p))
5536                     {
5537                       if (p == tp)
5538                         continue;
5539 #if FIND_INVOLVED_DEBUG
5540                       printf("%s recommends %s\n", solvable2str(pool, pool->solvables + ip), solvable2str(pool, pool->solvables + p));
5541 #endif
5542                       MAPSET(&im, p);
5543                       queue_push(&iq, p);
5544                     }
5545                 }
5546             }
5547         }
5548       if (!iq.count)
5549         {
5550           /* supplements pass */
5551           for (i = 0; i < installedq->count; i++)
5552             {
5553               ip = installedq->elements[i];
5554               if (ip == tp)
5555                 continue;
5556               s = pool->solvables + ip;
5557               if (!s->supplements)
5558                 continue;
5559               if (MAPTST(&im, ip))
5560                 continue;
5561               supp = s->repo->idarraydata + s->supplements;
5562               while ((sup = *supp++) != 0)
5563                 if (dep_possible(solv, sup, &im))
5564                   break;
5565               if (sup)
5566                 {
5567 #if FIND_INVOLVED_DEBUG
5568                   printf("%s supplemented\n", solvable2str(pool, pool->solvables + ip));
5569 #endif
5570                   MAPSET(&im, ip);
5571                   queue_push(&iq, ip);
5572                 }
5573             }
5574         }
5575     }
5576
5577   queue_free(&iq);
5578
5579   /* convert map into result */
5580   for (i = 0; i < installedq->count; i++)
5581     {
5582       ip = installedq->elements[i];
5583       if (MAPTST(&im, ip))
5584         continue;
5585       if (ip == ts - pool->solvables)
5586         continue;
5587       queue_push(q, ip);
5588     }
5589   map_free(&im);
5590   map_free(&installedm);
5591   queue_free(&installedq_internal);
5592 }
5593
5594 /* EOF */