src/solver.c

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