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