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