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