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
3866 /*
3867  *  return the next item of the proposed solution
3868  *  here are the possibilities for p / rp and what
3869  *  the solver expects the application to do:
3870  *    p                             rp
3871  *  -------------------------------------------------------
3872  *    SOLVER_SOLUTION_INFARCH       pkgid
3873  *    -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job
3874  *    SOLVER_SOLUTION_DISTUPGRADE   pkgid
3875  *    -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job
3876  *    SOLVER_SOLUTION_JOB           jobidx
3877  *    -> remove job (jobidx - 1, jobidx) from job queue
3878  *    pkgid (> 0)                   0
3879  *    -> add (SOLVER_ERASE|SOLVER_SOLVABLE, p) to the job
3880  *    pkgid (> 0)                   pkgid (> 0)
3881  *    -> add (SOLVER_INSTALL|SOLVER_SOLVABLE, rp) to the job
3882  *       (this will replace package p)
3883  *
3884  * Thus, the solver will either ask the application to remove
3885  * a specific job from the job queue, or ask to add an install/erase
3886  * job to it.
3887  *
3888  */
3889
3890 Id
3891 solver_next_solutionelement(Solver *solv, Id problem, Id solution, Id element, Id *p, Id *rp)
3892 {
3893   Id solidx = solv->problems.elements[problem * 2 - 1];
3894   solidx = solv->solutions.elements[solidx + solution];
3895   if (!solidx)
3896     return 0;
3897   solidx += 1 + element * 2;
3898   if (!solv->solutions.elements[solidx] && !solv->solutions.elements[solidx + 1])
3899     return 0;
3900   *p = solv->solutions.elements[solidx];
3901   *rp = solv->solutions.elements[solidx + 1];
3902   return element + 1;
3903 }
3904
3905 /*-------------------------------------------------------------------
3906  *
3907  * find problem rule
3908  */
3909
3910 static void
3911 findproblemrule_internal(Solver *solv, Id idx, Id *reqrp, Id *conrp, Id *sysrp, Id *jobrp)
3912 {
3913   Id rid, d;
3914   Id lreqr, lconr, lsysr, ljobr;
3915   Rule *r;
3916   int reqassert = 0;
3917
3918   lreqr = lconr = lsysr = ljobr = 0;
3919   while ((rid = solv->learnt_pool.elements[idx++]) != 0)
3920     {
3921       assert(rid > 0);
3922       if (rid >= solv->learntrules)
3923         findproblemrule_internal(solv, solv->learnt_why.elements[rid - solv->learntrules], &lreqr, &lconr, &lsysr, &ljobr);
3924       else if ((rid >= solv->jobrules && rid < solv->jobrules_end) || (rid >= solv->infarchrules && rid < solv->infarchrules_end) || (rid >= solv->duprules && rid < solv->duprules_end))
3925         {
3926           if (!*jobrp)
3927             *jobrp = rid;
3928         }
3929       else if (rid >= solv->updaterules && rid < solv->updaterules_end)
3930         {
3931           if (!*sysrp)
3932             *sysrp = rid;
3933         }
3934       else
3935         {
3936           assert(rid < solv->rpmrules_end);
3937           r = solv->rules + rid;
3938           d = r->d < 0 ? -r->d - 1 : r->d;
3939           if (!d && r->w2 < 0)
3940             {
3941               if (!*conrp)
3942                 *conrp = rid;
3943             }
3944           else
3945             {
3946               if (!d && r->w2 == 0 && !reqassert)
3947                 {
3948                   if (*reqrp > 0 && r->p < -1)
3949                     {
3950                       Id op = -solv->rules[*reqrp].p;
3951                       if (op > 1 && solv->pool->solvables[op].arch != solv->pool->solvables[-r->p].arch)
3952                         continue;       /* different arch, skip */
3953                     }
3954                   /* prefer assertions */
3955                   *reqrp = rid;
3956                   reqassert = 1;
3957                 }
3958               if (!*reqrp)
3959                 *reqrp = rid;
3960               else if (solv->installed && r->p < 0 && solv->pool->solvables[-r->p].repo == solv->installed && !reqassert)
3961                 {
3962                   /* prefer rules of installed packages */
3963                   *reqrp = rid;
3964                 }
3965             }
3966         }
3967     }
3968   if (!*reqrp && lreqr)
3969     *reqrp = lreqr;
3970   if (!*conrp && lconr)
3971     *conrp = lconr;
3972   if (!*jobrp && ljobr)
3973     *jobrp = ljobr;
3974   if (!*sysrp && lsysr)
3975     *sysrp = lsysr;
3976 }
3977
3978 /*
3979  * find problem rule
3980  *
3981  * search for a rule that describes the problem to the
3982  * user. Actually a pretty hopeless task that may leave the user
3983  * puzzled. To get all of the needed information use
3984  * solver_findallproblemrules() instead.
3985  */
3986
3987 Id
3988 solver_findproblemrule(Solver *solv, Id problem)
3989 {
3990   Id reqr, conr, sysr, jobr;
3991   Id idx = solv->problems.elements[2 * problem - 2];
3992   reqr = conr = sysr = jobr = 0;
3993   findproblemrule_internal(solv, idx, &reqr, &conr, &sysr, &jobr);
3994   if (reqr)
3995     return reqr;        /* some requires */
3996   if (conr)
3997     return conr;        /* some conflict */
3998   if (sysr)
3999     return sysr;        /* an update rule */
4000   if (jobr)
4001     return jobr;        /* a user request */
4002   assert(0);
4003 }
4004
4005 /*-------------------------------------------------------------------*/
4006
4007 static void
4008 findallproblemrules_internal(Solver *solv, Id idx, Queue *rules)
4009 {
4010   Id rid;
4011   while ((rid = solv->learnt_pool.elements[idx++]) != 0)
4012     {
4013       if (rid >= solv->learntrules)
4014         {
4015           findallproblemrules_internal(solv, solv->learnt_why.elements[rid - solv->learntrules], rules);
4016           continue;
4017         }
4018       queue_pushunique(rules, rid);
4019     }
4020 }
4021
4022 /*
4023  * find all problem rule
4024  *
4025  * return all rules that lead to the problem. This gives the user
4026  * all of the information to understand the problem, but the result
4027  * can be a large number of rules.
4028  */
4029
4030 void
4031 solver_findallproblemrules(Solver *solv, Id problem, Queue *rules)
4032 {
4033   queue_empty(rules);
4034   findallproblemrules_internal(solv, solv->problems.elements[2 * problem - 2], rules);
4035 }
4036
4037
4038 /*-------------------------------------------------------------------
4039  *
4040  * create reverse obsoletes map for installed solvables
4041  *
4042  * For each installed solvable find which packages with *different* names
4043  * obsolete the solvable.
4044  * This index is used in policy_findupdatepackages if noupdateprovide is
4045  * set.
4046  */
4047
4048 static void
4049 create_obsolete_index(Solver *solv)
4050 {
4051   Pool *pool = solv->pool;
4052   Solvable *s;
4053   Repo *installed = solv->installed;
4054   Id p, pp, obs, *obsp, *obsoletes, *obsoletes_data;
4055   int i, n, cnt;
4056
4057   if (!installed || installed->start == installed->end)
4058     return;
4059   cnt = installed->end - installed->start;
4060   solv->obsoletes = obsoletes = sat_calloc(cnt, sizeof(Id));
4061   for (i = 1; i < pool->nsolvables; i++)
4062     {
4063       s = pool->solvables + i;
4064       if (!s->obsoletes)
4065         continue;
4066       if (!pool_installable(pool, s))
4067         continue;
4068       obsp = s->repo->idarraydata + s->obsoletes;
4069       while ((obs = *obsp++) != 0)
4070         {
4071           FOR_PROVIDES(p, pp, obs)
4072             {
4073               if (pool->solvables[p].repo != installed)
4074                 continue;
4075               if (pool->solvables[p].name == s->name)
4076                 continue;
4077               if (!solv->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p, obs))
4078                 continue;
4079               obsoletes[p - installed->start]++;
4080             }
4081         }
4082     }
4083   n = 0;
4084   for (i = 0; i < cnt; i++)
4085     if (obsoletes[i])
4086       {
4087         n += obsoletes[i] + 1;
4088         obsoletes[i] = n;
4089       }
4090   solv->obsoletes_data = obsoletes_data = sat_calloc(n + 1, sizeof(Id));
4091   POOL_DEBUG(SAT_DEBUG_STATS, "obsoletes data: %d entries\n", n + 1);
4092   for (i = pool->nsolvables - 1; i > 0; i--)
4093     {
4094       s = pool->solvables + i;
4095       if (!s->obsoletes)
4096         continue;
4097       if (!pool_installable(pool, s))
4098         continue;
4099       obsp = s->repo->idarraydata + s->obsoletes;
4100       while ((obs = *obsp++) != 0)
4101         {
4102           FOR_PROVIDES(p, pp, obs)
4103             {
4104               if (pool->solvables[p].repo != installed)
4105                 continue;
4106               if (pool->solvables[p].name == s->name)
4107                 continue;
4108               if (!solv->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p, obs))
4109                 continue;
4110               p -= installed->start;
4111               if (obsoletes_data[obsoletes[p]] != i)
4112                 obsoletes_data[--obsoletes[p]] = i;
4113             }
4114         }
4115     }
4116 }
4117
4118
4119 /*-------------------------------------------------------------------
4120  *
4121  * remove disabled conflicts
4122  *
4123  * purpose: update the decisionmap after some rules were disabled.
4124  * this is used to calculate the suggested/recommended package list.
4125  * Also returns a "removed" list to undo the discisionmap changes.
4126  */
4127
4128 static void
4129 removedisabledconflicts(Solver *solv, Queue *removed)
4130 {
4131   Pool *pool = solv->pool;
4132   int i, n;
4133   Id p, why, *dp;
4134   Id new;
4135   Rule *r;
4136   Id *decisionmap = solv->decisionmap;
4137
4138   POOL_DEBUG(SAT_DEBUG_SCHUBI, "removedisabledconflicts\n");
4139   queue_empty(removed);
4140   for (i = 0; i < solv->decisionq.count; i++)
4141     {
4142       p = solv->decisionq.elements[i];
4143       if (p > 0)
4144         continue;
4145       /* a conflict. we never do conflicts on free decisions, so there
4146        * must have been an unit rule */
4147       why = solv->decisionq_why.elements[i];
4148       assert(why > 0);
4149       r = solv->rules + why;
4150       if (r->d < 0 && decisionmap[-p])
4151         {
4152           /* rule is now disabled, remove from decisionmap */
4153           POOL_DEBUG(SAT_DEBUG_SCHUBI, "removing conflict for package %s[%d]\n", solvid2str(pool, -p), -p);
4154           queue_push(removed, -p);
4155           queue_push(removed, decisionmap[-p]);
4156           decisionmap[-p] = 0;
4157         }
4158     }
4159   if (!removed->count)
4160     return;
4161   /* we removed some confliced packages. some of them might still
4162    * be in conflict, so search for unit rules and re-conflict */
4163   new = 0;
4164   for (i = n = 1, r = solv->rules + i; n < solv->nrules; i++, r++, n++)
4165     {
4166       if (i == solv->nrules)
4167         {
4168           i = 1;
4169           r = solv->rules + i;
4170         }
4171       if (r->d < 0)
4172         continue;
4173       if (!r->w2)
4174         {
4175           if (r->p < 0 && !decisionmap[-r->p])
4176             new = r->p;
4177         }
4178       else if (!r->d)
4179         {
4180           /* binary rule */
4181           if (r->p < 0 && decisionmap[-r->p] == 0 && DECISIONMAP_FALSE(r->w2))
4182             new = r->p;
4183           else if (r->w2 < 0 && decisionmap[-r->w2] == 0 && DECISIONMAP_FALSE(r->p))
4184             new = r->w2;
4185         }
4186       else
4187         {
4188           if (r->p < 0 && decisionmap[-r->p] == 0)
4189             new = r->p;
4190           if (new || DECISIONMAP_FALSE(r->p))
4191             {
4192               dp = pool->whatprovidesdata + r->d;
4193               while ((p = *dp++) != 0)
4194                 {
4195                   if (new && p == new)
4196                     continue;
4197                   if (p < 0 && decisionmap[-p] == 0)
4198                     {
4199                       if (new)
4200                         {
4201                           new = 0;
4202                           break;
4203                         }
4204                       new = p;
4205                     }
4206                   else if (!DECISIONMAP_FALSE(p))
4207                     {
4208                       new = 0;
4209                       break;
4210                     }
4211                 }
4212             }
4213         }
4214       if (new)
4215         {
4216           POOL_DEBUG(SAT_DEBUG_SCHUBI, "re-conflicting package %s[%d]\n", solvid2str(pool, -new), -new);
4217           decisionmap[-new] = -1;
4218           new = 0;
4219           n = 0;        /* redo all rules */
4220         }
4221     }
4222 }
4223
4224 static inline void
4225 undo_removedisabledconflicts(Solver *solv, Queue *removed)
4226 {
4227   int i;
4228   for (i = 0; i < removed->count; i += 2)
4229     solv->decisionmap[removed->elements[i]] = removed->elements[i + 1];
4230 }
4231
4232
4233 /*-------------------------------------------------------------------
4234  *
4235  * weaken solvable dependencies
4236  */
4237
4238 static void
4239 weaken_solvable_deps(Solver *solv, Id p)
4240 {
4241   int i;
4242   Rule *r;
4243
4244   for (i = 1, r = solv->rules + i; i < solv->rpmrules_end; i++, r++)
4245     {
4246       if (r->p != -p)
4247         continue;
4248       if ((r->d == 0 || r->d == -1) && r->w2 < 0)
4249         continue;       /* conflict */
4250       queue_push(&solv->weakruleq, i);
4251     }
4252 }
4253
4254 /********************************************************************/
4255 /* main() */
4256
4257
4258 static void
4259 addinfarchrules(Solver *solv, Map *addedmap)
4260 {
4261   Pool *pool = solv->pool;
4262   int first, i, j;
4263   Id p, pp, a, aa, bestarch;
4264   Solvable *s, *ps, *bests;
4265   Queue badq, allowedarchs;
4266
4267   queue_init(&badq);
4268   queue_init(&allowedarchs);
4269   solv->infarchrules = solv->nrules;
4270   for (i = 1; i < pool->nsolvables; i++)
4271     {
4272       if (i == SYSTEMSOLVABLE || !MAPTST(addedmap, i))
4273         continue;
4274       s = pool->solvables + i;
4275       first = i;
4276       bestarch = 0;
4277       bests = 0;
4278       queue_empty(&allowedarchs);
4279       FOR_PROVIDES(p, pp, s->name)
4280         {
4281           ps = pool->solvables + p;
4282           if (ps->name != s->name || !MAPTST(addedmap, p))
4283             continue;
4284           if (p == i)
4285             first = 0;
4286           if (first)
4287             break;
4288           a = ps->arch;
4289           a = (a <= pool->lastarch) ? pool->id2arch[a] : 0;
4290           if (a != 1 && pool->installed && ps->repo == pool->installed)
4291             {
4292               if (!solv->distupgrade)
4293                 queue_pushunique(&allowedarchs, ps->arch);      /* also ok to keep this architecture */
4294               continue;         /* ignore installed solvables when calculating the best arch */
4295             }
4296           if (a && a != 1 && (!bestarch || a < bestarch))
4297             {
4298               bestarch = a;
4299               bests = ps;
4300             }
4301         }
4302       if (first)
4303         continue;
4304       /* speed up common case where installed package already has best arch */
4305       if (allowedarchs.count == 1 && bests && allowedarchs.elements[0] == bests->arch)
4306         allowedarchs.count--;   /* installed arch is best */
4307       queue_empty(&badq);
4308       FOR_PROVIDES(p, pp, s->name)
4309         {
4310           ps = pool->solvables + p;
4311           if (ps->name != s->name || !MAPTST(addedmap, p))
4312             continue;
4313           a = ps->arch;
4314           a = (a <= pool->lastarch) ? pool->id2arch[a] : 0;
4315           if (a != 1 && bestarch && ((a ^ bestarch) & 0xffff0000) != 0)
4316             {
4317               for (j = 0; j < allowedarchs.count; j++)
4318                 {
4319                   aa = allowedarchs.elements[j];
4320                   if (ps->arch == aa)
4321                     break;
4322                   aa = (aa <= pool->lastarch) ? pool->id2arch[aa] : 0;
4323                   if (aa && ((a ^ aa) & 0xffff0000) == 0)
4324                     break;      /* compatible */
4325                 }
4326               if (j == allowedarchs.count)
4327                 queue_push(&badq, p);
4328             }
4329         }
4330       if (!badq.count)
4331         continue;
4332       /* block all solvables in the badq! */
4333       for (j = 0; j < badq.count; j++)
4334         {
4335           p = badq.elements[j];
4336           addrule(solv, -p, 0);
4337         }
4338     }
4339   queue_free(&badq);
4340   queue_free(&allowedarchs);
4341   solv->infarchrules_end = solv->nrules;
4342 }
4343
4344 static void
4345 createdupmaps(Solver *solv, Queue *job)
4346 {
4347   Pool *pool = solv->pool;
4348   Repo *repo;
4349   Id how, what, p, pi, pp, obs, *obsp;
4350   Solvable *s, *ps;
4351   int i;
4352
4353   map_init(&solv->dupmap, pool->nsolvables);
4354   map_init(&solv->dupinvolvedmap, pool->nsolvables);
4355   for (i = 0; i < job->count; i += 2)
4356     {
4357       how = job->elements[i];
4358       what = job->elements[i + 1];
4359       switch (how & SOLVER_JOBMASK)
4360         {
4361         case SOLVER_DISTUPGRADE:
4362           if (what < 0 || what > pool->nrepos)
4363             break;
4364           repo = pool->repos[what];
4365           FOR_REPO_SOLVABLES(repo, p, s)
4366             {
4367               MAPSET(&solv->dupmap, p);
4368               FOR_PROVIDES(pi, pp, s->name)
4369                 {
4370                   ps = pool->solvables + pi;
4371                   if (ps->name != s->name)
4372                     continue;
4373                   MAPSET(&solv->dupinvolvedmap, pi);
4374                 }
4375               if (s->obsoletes)
4376                 {
4377                   /* FIXME: check obsoletes/provides combination */
4378                   obsp = s->repo->idarraydata + s->obsoletes;
4379                   while ((obs = *obsp++) != 0)
4380                     {
4381                       FOR_PROVIDES(pi, pp, obs)
4382                         {
4383                           if (!solv->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + pi, obs))
4384                             continue;
4385                           MAPSET(&solv->dupinvolvedmap, pi);
4386                         }
4387                     }
4388                 }
4389             }
4390           break;
4391         default:
4392           break;
4393         }
4394     }
4395   MAPCLR(&solv->dupinvolvedmap, SYSTEMSOLVABLE);
4396 }
4397
4398 static void
4399 freedupmaps(Solver *solv)
4400 {
4401   map_free(&solv->dupmap);
4402   map_free(&solv->dupinvolvedmap);
4403 }
4404
4405 static void
4406 addduprules(Solver *solv, Map *addedmap)
4407 {
4408   Pool *pool = solv->pool;
4409   Id p, pp;
4410   Solvable *s, *ps;
4411   int first, i;
4412
4413   solv->duprules = solv->nrules;
4414   for (i = 1; i < pool->nsolvables; i++)
4415     {
4416       if (i == SYSTEMSOLVABLE || !MAPTST(addedmap, i))
4417         continue;
4418       s = pool->solvables + i;
4419       first = i;
4420       FOR_PROVIDES(p, pp, s->name)
4421         {
4422           ps = pool->solvables + p;
4423           if (ps->name != s->name || !MAPTST(addedmap, p))
4424             continue;
4425           if (p == i)
4426             first = 0;
4427           if (first)
4428             break;
4429           if (!MAPTST(&solv->dupinvolvedmap, p))
4430             continue;
4431           if (solv->installed && ps->repo == solv->installed)
4432             {
4433               if (!solv->updatemap.size)
4434                 map_init(&solv->updatemap, pool->nsolvables);
4435               MAPSET(&solv->updatemap, p);
4436               if (!MAPTST(&solv->dupmap, p))
4437                 {
4438                   Id ip, ipp;
4439                   /* is installed identical to a good one? */
4440                   FOR_PROVIDES(ip, ipp, s->name)
4441                     {
4442                       Solvable *is = pool->solvables + ip;
4443                       if (!MAPTST(&solv->dupmap, ip))
4444                         continue;
4445                       if (is->evr == s->evr && solvable_identical(s, is))
4446                         break;
4447                     }
4448                   if (!ip)
4449                     addrule(solv, -p, 0);       /* no match, sorry */
4450                 }
4451             }
4452           else if (!MAPTST(&solv->dupmap, p))
4453             addrule(solv, -p, 0);
4454         }
4455     }
4456   solv->duprules_end = solv->nrules;
4457 }
4458
4459
4460 static void
4461 findrecommendedsuggested(Solver *solv)
4462 {
4463   Pool *pool = solv->pool;
4464   Queue redoq, disabledq;
4465   int goterase, i;
4466   Solvable *s;
4467   Rule *r;
4468   Map obsmap;
4469
4470   map_init(&obsmap, pool->nsolvables);
4471   if (solv->installed)
4472     {
4473       Id obs, *obsp, p, po, ppo;
4474       for (p = solv->installed->start; p < solv->installed->end; p++)
4475         {
4476           s = pool->solvables + p;
4477           if (s->repo != solv->installed || !s->obsoletes)
4478             continue;
4479           if (solv->decisionmap[p] <= 0)
4480             continue;
4481           if (solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p))
4482             continue;
4483           obsp = s->repo->idarraydata + s->obsoletes;
4484           /* foreach obsoletes */
4485           while ((obs = *obsp++) != 0)
4486             FOR_PROVIDES(po, ppo, obs)
4487               MAPSET(&obsmap, po);
4488         }
4489     }
4490
4491   queue_init(&redoq);
4492   queue_init(&disabledq);
4493   goterase = 0;
4494   /* disable all erase jobs (including weak "keep uninstalled" rules) */
4495   for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++)
4496     {
4497       if (r->d < 0)     /* disabled ? */
4498         continue;
4499       if (r->p >= 0)    /* install job? */
4500         continue;
4501       queue_push(&disabledq, i);
4502       disablerule(solv, r);
4503       goterase++;
4504     }
4505
4506   if (goterase)
4507     {
4508       enabledisablelearntrules(solv);
4509       removedisabledconflicts(solv, &redoq);
4510     }
4511
4512   /*
4513    * find recommended packages
4514    */
4515
4516   /* if redoq.count == 0 we already found all recommended in the
4517    * solver run */
4518   if (redoq.count || solv->dontinstallrecommended || !solv->dontshowinstalledrecommended || solv->ignorealreadyrecommended)
4519     {
4520       Id rec, *recp, p, pp;
4521
4522       /* create map of all recommened packages */
4523       solv->recommends_index = -1;
4524       MAPZERO(&solv->recommendsmap);
4525       for (i = 0; i < solv->decisionq.count; i++)
4526         {
4527           p = solv->decisionq.elements[i];
4528           if (p < 0)
4529             continue;
4530           s = pool->solvables + p;
4531           if (s->recommends)
4532             {
4533               recp = s->repo->idarraydata + s->recommends;
4534               while ((rec = *recp++) != 0)
4535                 {
4536                   FOR_PROVIDES(p, pp, rec)
4537                     if (solv->decisionmap[p] > 0)
4538                       break;
4539                   if (p)
4540                     {
4541                       if (!solv->dontshowinstalledrecommended)
4542                         {
4543                           FOR_PROVIDES(p, pp, rec)
4544                             if (solv->decisionmap[p] > 0)
4545                               MAPSET(&solv->recommendsmap, p);
4546                         }
4547                       continue; /* p != 0: already fulfilled */
4548                     }
4549                   FOR_PROVIDES(p, pp, rec)
4550                     MAPSET(&solv->recommendsmap, p);
4551                 }
4552             }
4553         }
4554       for (i = 1; i < pool->nsolvables; i++)
4555         {
4556           if (solv->decisionmap[i] < 0)
4557             continue;
4558           if (solv->decisionmap[i] > 0 && solv->dontshowinstalledrecommended)
4559             continue;
4560           if (MAPTST(&obsmap, i))
4561             continue;
4562           s = pool->solvables + i;
4563           if (!MAPTST(&solv->recommendsmap, i))
4564             {
4565               if (!s->supplements)
4566                 continue;
4567               if (!pool_installable(pool, s))
4568                 continue;
4569               if (!solver_is_supplementing(solv, s))
4570                 continue;
4571             }
4572           if (solv->dontinstallrecommended)
4573             queue_push(&solv->recommendations, i);
4574           else
4575             queue_pushunique(&solv->recommendations, i);
4576         }
4577       /* we use MODE_SUGGEST here so that repo prio is ignored */
4578       policy_filter_unwanted(solv, &solv->recommendations, POLICY_MODE_SUGGEST);
4579     }
4580
4581   /*
4582    * find suggested packages
4583    */
4584
4585   if (1)
4586     {
4587       Id sug, *sugp, p, pp;
4588
4589       /* create map of all suggests that are still open */
4590       solv->recommends_index = -1;
4591       MAPZERO(&solv->suggestsmap);
4592       for (i = 0; i < solv->decisionq.count; i++)
4593         {
4594           p = solv->decisionq.elements[i];
4595           if (p < 0)
4596             continue;
4597           s = pool->solvables + p;
4598           if (s->suggests)
4599             {
4600               sugp = s->repo->idarraydata + s->suggests;
4601               while ((sug = *sugp++) != 0)
4602                 {
4603                   FOR_PROVIDES(p, pp, sug)
4604                     if (solv->decisionmap[p] > 0)
4605                       break;
4606                   if (p)
4607                     {
4608                       if (!solv->dontshowinstalledrecommended)
4609                         {
4610                           FOR_PROVIDES(p, pp, sug)
4611                             if (solv->decisionmap[p] > 0)
4612                               MAPSET(&solv->suggestsmap, p);
4613                         }
4614                       continue; /* already fulfilled */
4615                     }
4616                   FOR_PROVIDES(p, pp, sug)
4617                     MAPSET(&solv->suggestsmap, p);
4618                 }
4619             }
4620         }
4621       for (i = 1; i < pool->nsolvables; i++)
4622         {
4623           if (solv->decisionmap[i] < 0)
4624             continue;
4625           if (solv->decisionmap[i] > 0 && solv->dontshowinstalledrecommended)
4626             continue;
4627           if (MAPTST(&obsmap, i))
4628             continue;
4629           s = pool->solvables + i;
4630           if (!MAPTST(&solv->suggestsmap, i))
4631             {
4632               if (!s->enhances)
4633                 continue;
4634               if (!pool_installable(pool, s))
4635                 continue;
4636               if (!solver_is_enhancing(solv, s))
4637                 continue;
4638             }
4639           queue_push(&solv->suggestions, i);
4640         }
4641       policy_filter_unwanted(solv, &solv->suggestions, POLICY_MODE_SUGGEST);
4642     }
4643
4644   /* undo removedisabledconflicts */
4645   if (redoq.count)
4646     undo_removedisabledconflicts(solv, &redoq);
4647   queue_free(&redoq);
4648
4649   /* undo job rule disabling */
4650   for (i = 0; i < disabledq.count; i++)
4651     enablerule(solv, solv->rules + disabledq.elements[i]);
4652   queue_free(&disabledq);
4653   map_free(&obsmap);
4654 }
4655
4656
4657 /*
4658  *
4659  * solve job queue
4660  *
4661  */
4662
4663 void
4664 solver_solve(Solver *solv, Queue *job)
4665 {
4666   Pool *pool = solv->pool;
4667   Repo *installed = solv->installed;
4668   int i;
4669   int oldnrules;
4670   Map addedmap;                /* '1' == have rpm-rules for solvable */
4671   Map installcandidatemap;
4672   Id how, what, select, name, weak, p, pp, d;
4673   Queue q;
4674   Solvable *s;
4675   Rule *r;
4676   int now, solve_start;
4677   int hasdupjob = 0;
4678
4679   solve_start = sat_timems(0);
4680
4681   /* log solver options */
4682   POOL_DEBUG(SAT_DEBUG_STATS, "solver started\n");
4683   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);
4684   POOL_DEBUG(SAT_DEBUG_STATS, "distupgrade=%d distupgrade_removeunsupported=%d\n", solv->distupgrade, solv->distupgrade_removeunsupported);
4685   POOL_DEBUG(SAT_DEBUG_STATS, "allowuninstall=%d, allowdowngrade=%d, allowarchchange=%d, allowvendorchange=%d\n", solv->allowuninstall, solv->allowdowngrade, solv->allowarchchange, solv->allowvendorchange);
4686   POOL_DEBUG(SAT_DEBUG_STATS, "promoteepoch=%d, allowvirtualconflicts=%d, allowselfconflicts=%d\n", pool->promoteepoch, solv->allowvirtualconflicts, solv->allowselfconflicts);
4687   POOL_DEBUG(SAT_DEBUG_STATS, "obsoleteusesprovides=%d, implicitobsoleteusesprovides=%d\n", solv->obsoleteusesprovides, solv->implicitobsoleteusesprovides);
4688   POOL_DEBUG(SAT_DEBUG_STATS, "dontinstallrecommended=%d, ignorealreadyrecommended=%d, dontshowinstalledrecommended=%d\n", solv->dontinstallrecommended, solv->ignorealreadyrecommended, solv->dontshowinstalledrecommended);
4689
4690   /* create whatprovides if not already there */
4691   if (!pool->whatprovides)
4692     pool_createwhatprovides(pool);
4693
4694   /* create obsolete index */
4695   create_obsolete_index(solv);
4696
4697   /* remember job */
4698   queue_free(&solv->job);
4699   queue_clone(&solv->job, job);
4700
4701   /*
4702    * create basic rule set of all involved packages
4703    * use addedmap bitmap to make sure we don't create rules twice
4704    */
4705
4706   /* create noobsolete map if needed */
4707   for (i = 0; i < job->count; i += 2)
4708     {
4709       how = job->elements[i] & ~SOLVER_WEAK;
4710       if ((how & SOLVER_JOBMASK) != SOLVER_NOOBSOLETES)
4711         continue;
4712       what = job->elements[i + 1];
4713       select = how & SOLVER_SELECTMASK;
4714       if (!solv->noobsoletes.size)
4715         map_init(&solv->noobsoletes, pool->nsolvables);
4716       FOR_JOB_SELECT(p, pp, select, what)
4717         MAPSET(&solv->noobsoletes, p);
4718     }
4719
4720   map_init(&addedmap, pool->nsolvables);
4721   map_init(&installcandidatemap, pool->nsolvables);
4722   queue_init(&q);
4723
4724   /*
4725    * always install our system solvable
4726    */
4727   MAPSET(&addedmap, SYSTEMSOLVABLE);
4728   queue_push(&solv->decisionq, SYSTEMSOLVABLE);
4729   queue_push(&solv->decisionq_why, 0);
4730   solv->decisionmap[SYSTEMSOLVABLE] = 1; /* installed at level '1' */
4731
4732   now = sat_timems(0);
4733   /*
4734    * create rules for all package that could be involved with the solving
4735    * so called: rpm rules
4736    *
4737    */
4738   if (installed)
4739     {
4740       oldnrules = solv->nrules;
4741       POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for installed solvables ***\n");
4742       FOR_REPO_SOLVABLES(installed, p, s)
4743         addrpmrulesforsolvable(solv, s, &addedmap);
4744       POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for installed solvables\n", solv->nrules - oldnrules);
4745       POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for updaters of installed solvables ***\n");
4746       oldnrules = solv->nrules;
4747       FOR_REPO_SOLVABLES(installed, p, s)
4748         addrpmrulesforupdaters(solv, s, &addedmap, 1);
4749       POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for updaters of installed solvables\n", solv->nrules - oldnrules);
4750     }
4751
4752   /*
4753    * create rules for all packages involved in the job
4754    * (to be installed or removed)
4755    */
4756
4757   POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for packages involved with a job ***\n");
4758   oldnrules = solv->nrules;
4759   for (i = 0; i < job->count; i += 2)
4760     {
4761       how = job->elements[i];
4762       what = job->elements[i + 1];
4763       select = how & SOLVER_SELECTMASK;
4764
4765       switch (how & SOLVER_JOBMASK)
4766         {
4767         case SOLVER_INSTALL:
4768           FOR_JOB_SELECT(p, pp, select, what)
4769             {
4770               MAPSET(&installcandidatemap, p);
4771               addrpmrulesforsolvable(solv, pool->solvables + p, &addedmap);
4772             }
4773           break;
4774         case SOLVER_DISTUPGRADE:
4775           if (!solv->distupgrade)
4776             hasdupjob = 1;
4777           break;
4778         default:
4779           break;
4780         }
4781     }
4782   POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for packages involved in a job\n", solv->nrules - oldnrules);
4783
4784   POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for recommended/suggested packages ***\n");
4785
4786   oldnrules = solv->nrules;
4787
4788     /*
4789      * add rules for suggests, enhances
4790      */
4791   addrpmrulesforweak(solv, &addedmap);
4792   POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules because of weak dependencies\n", solv->nrules - oldnrules);
4793
4794   IF_POOLDEBUG (SAT_DEBUG_STATS)
4795     {
4796       int possible = 0, installable = 0;
4797       for (i = 1; i < pool->nsolvables; i++)
4798         {
4799           if (pool_installable(pool, pool->solvables + i))
4800             installable++;
4801           if (MAPTST(&addedmap, i))
4802             possible++;
4803         }
4804       POOL_DEBUG(SAT_DEBUG_STATS, "%d of %d installable solvables considered for solving\n", possible, installable);
4805     }
4806
4807   /*
4808    * first pass done, we now have all the rpm rules we need.
4809    * unify existing rules before going over all job rules and
4810    * policy rules.
4811    * at this point the system is always solvable,
4812    * as an empty system (remove all packages) is a valid solution
4813    */
4814
4815   unifyrules(solv);                               /* remove duplicate rpm rules */
4816
4817   solv->rpmrules_end = solv->nrules;              /* mark end of rpm rules */
4818
4819   solv->directdecisions = solv->decisionq.count;
4820   POOL_DEBUG(SAT_DEBUG_STATS, "rpm rule memory usage: %d K\n", solv->nrules * (int)sizeof(Rule) / 1024);
4821   POOL_DEBUG(SAT_DEBUG_STATS, "decisions so far: %d\n", solv->decisionq.count);
4822   POOL_DEBUG(SAT_DEBUG_STATS, "rpm rule creation took %d ms\n", sat_timems(now));
4823
4824   /* create dup maps if needed. We need the maps early to create our
4825    * update rules */
4826   if (hasdupjob)
4827     createdupmaps(solv, job);
4828
4829   /*
4830    * create feature rules
4831    *
4832    * foreach installed:
4833    *   create assertion (keep installed, if no update available)
4834    *   or
4835    *   create update rule (A|update1(A)|update2(A)|...)
4836    *
4837    * those are used later on to keep a version of the installed packages in
4838    * best effort mode
4839    */
4840
4841   POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** Add feature rules ***\n");
4842   solv->featurerules = solv->nrules;              /* mark start of feature rules */
4843   if (installed)
4844     {
4845         /* foreach possibly installed solvable */
4846       for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
4847         {
4848           if (s->repo != installed)
4849             {
4850               addrule(solv, 0, 0);      /* create dummy rule */
4851               continue;
4852             }
4853           addupdaterule(solv, s, 1);    /* allow s to be updated */
4854         }
4855         /*
4856          * assert one rule per installed solvable,
4857          * either an assertion (A)
4858          * or a possible update (A|update1(A)|update2(A)|...)
4859          */
4860       assert(solv->nrules - solv->featurerules == installed->end - installed->start);
4861     }
4862   solv->featurerules_end = solv->nrules;
4863
4864     /*
4865      * Add update rules for installed solvables
4866      *
4867      * almost identical to feature rules
4868      * except that downgrades/archchanges/vendorchanges are not allowed
4869      */
4870
4871   POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** Add update rules ***\n");
4872   solv->updaterules = solv->nrules;
4873
4874   if (installed)
4875     { /* foreach installed solvables */
4876       /* we create all update rules, but disable some later on depending on the job */
4877       for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
4878         {
4879           Rule *sr;
4880
4881           if (s->repo != installed)
4882             {
4883               addrule(solv, 0, 0);      /* create dummy rule */
4884               continue;
4885             }
4886           addupdaterule(solv, s, 0);    /* allowall = 0: downgrades not allowed */
4887             /*
4888              * check for and remove duplicate
4889              */
4890           r = solv->rules + solv->nrules - 1;           /* r: update rule */
4891           sr = r - (installed->end - installed->start); /* sr: feature rule */
4892           /* it's orphaned if there is no feature rule or the feature rule
4893            * consists just of the installed package */
4894           if (!sr->p || (sr->p == i && !sr->d && !sr->w2))
4895             queue_push(&solv->orphaned, i);
4896           if (!r->p)
4897             {
4898               assert(solv->distupgrade && !sr->p);
4899               continue;
4900             }
4901           if (!unifyrules_sortcmp(r, sr, pool))
4902             {
4903               /* identical rule, kill unneeded one */
4904               if (solv->allowuninstall)
4905                 {
4906                   /* keep feature rule, make it weak */
4907                   memset(r, 0, sizeof(*r));
4908                   queue_push(&solv->weakruleq, sr - solv->rules);
4909                 }
4910               else
4911                 {
4912                   /* keep update rule */
4913                   memset(sr, 0, sizeof(*sr));
4914                 }
4915             }
4916           else if (solv->allowuninstall)
4917             {
4918               /* make both feature and update rule weak */
4919               queue_push(&solv->weakruleq, r - solv->rules);
4920               queue_push(&solv->weakruleq, sr - solv->rules);
4921             }
4922           else
4923             disablerule(solv, sr);
4924         }
4925       /* consistency check: we added a rule for _every_ installed solvable */
4926       assert(solv->nrules - solv->updaterules == installed->end - installed->start);
4927     }
4928   solv->updaterules_end = solv->nrules;
4929
4930
4931   /*
4932    * now add all job rules
4933    */
4934
4935   POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** Add JOB rules ***\n");
4936
4937   solv->jobrules = solv->nrules;
4938   for (i = 0; i < job->count; i += 2)
4939     {
4940       oldnrules = solv->nrules;
4941
4942       how = job->elements[i];
4943       what = job->elements[i + 1];
4944       weak = how & SOLVER_WEAK;
4945       select = how & SOLVER_SELECTMASK;
4946       switch (how & SOLVER_JOBMASK)
4947         {
4948         case SOLVER_INSTALL:
4949           POOL_DEBUG(SAT_DEBUG_JOB, "job: %sinstall %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
4950           if (select == SOLVER_SOLVABLE)
4951             {
4952               p = what;
4953               d = 0;
4954             }
4955           else
4956             {
4957               queue_empty(&q);
4958               FOR_JOB_SELECT(p, pp, select, what)
4959                 queue_push(&q, p);
4960               if (!q.count)
4961                 {
4962                   /* no candidate found, make this an impossible rule */
4963                   queue_push(&q, -SYSTEMSOLVABLE);
4964                 }
4965               p = queue_shift(&q);      /* get first candidate */
4966               d = !q.count ? 0 : pool_queuetowhatprovides(pool, &q);    /* internalize */
4967             }
4968           addrule(solv, p, d);          /* add install rule */
4969           queue_push(&solv->ruletojob, i);
4970           if (weak)
4971             queue_push(&solv->weakruleq, solv->nrules - 1);
4972           break;
4973         case SOLVER_ERASE:
4974           POOL_DEBUG(SAT_DEBUG_JOB, "job: %serase %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
4975           if (select == SOLVER_SOLVABLE && solv->installed && pool->solvables[what].repo == solv->installed)
4976             {
4977               /* special case for "erase a specific solvable": we also
4978                * erase all other solvables with that name, so that they
4979                * don't get picked up as replacement */
4980               name = pool->solvables[what].name;
4981               FOR_PROVIDES(p, pp, name)
4982                 {
4983                   if (p == what)
4984                     continue;
4985                   s = pool->solvables + p;
4986                   if (s->name != name)
4987                     continue;
4988                   /* keep other versions installed */
4989                   if (s->repo == solv->installed)
4990                     continue;
4991                   /* keep installcandidates of other jobs */
4992                   if (MAPTST(&installcandidatemap, p))
4993                     continue;
4994                   addrule(solv, -p, 0);                 /* remove by Id */
4995                   queue_push(&solv->ruletojob, i);
4996                   if (weak)
4997                     queue_push(&solv->weakruleq, solv->nrules - 1);
4998                 }
4999             }
5000           FOR_JOB_SELECT(p, pp, select, what)
5001             {
5002               addrule(solv, -p, 0);
5003               queue_push(&solv->ruletojob, i);
5004               if (weak)
5005                 queue_push(&solv->weakruleq, solv->nrules - 1);
5006             }
5007           break;
5008
5009         case SOLVER_UPDATE:
5010           POOL_DEBUG(SAT_DEBUG_JOB, "job: %supdate %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
5011           FOR_JOB_SELECT(p, pp, select, what)
5012             {
5013               s = pool->solvables + p;
5014               if (!solv->installed || s->repo != solv->installed)
5015                 continue;
5016               if (!solv->updatemap.size)
5017                 map_init(&solv->updatemap, pool->nsolvables);
5018               MAPSET(&solv->updatemap, p);
5019             }
5020           break;
5021         case SOLVER_WEAKENDEPS:
5022           POOL_DEBUG(SAT_DEBUG_JOB, "job: %sweaken deps %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
5023           if (select != SOLVER_SOLVABLE)
5024             break;
5025           s = pool->solvables + what;
5026           weaken_solvable_deps(solv, what);
5027           break;
5028         case SOLVER_NOOBSOLETES:
5029           POOL_DEBUG(SAT_DEBUG_JOB, "job: %sno obsolete %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
5030           break;
5031         case SOLVER_LOCK:
5032           POOL_DEBUG(SAT_DEBUG_JOB, "job: %slock %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
5033           FOR_JOB_SELECT(p, pp, select, what)
5034             {
5035               s = pool->solvables + p;
5036               if (installed && s->repo == installed)
5037                 addrule(solv, p, 0);
5038               else
5039                 addrule(solv, -p, 0);
5040               queue_push(&solv->ruletojob, i);
5041               if (weak)
5042                 queue_push(&solv->weakruleq, solv->nrules - 1);
5043             }
5044           break;
5045         case SOLVER_DISTUPGRADE:
5046           POOL_DEBUG(SAT_DEBUG_JOB, "job: distupgrade repo #%d\n", what);
5047           break;
5048         default:
5049           POOL_DEBUG(SAT_DEBUG_JOB, "job: unknown job\n");
5050           break;
5051         }
5052
5053         /*
5054          * debug
5055          */
5056
5057       IF_POOLDEBUG (SAT_DEBUG_JOB)
5058         {
5059           int j;
5060           if (solv->nrules == oldnrules)
5061             POOL_DEBUG(SAT_DEBUG_JOB, " - no rule created\n");
5062           for (j = oldnrules; j < solv->nrules; j++)
5063             {
5064               POOL_DEBUG(SAT_DEBUG_JOB, " - job ");
5065               solver_printrule(solv, SAT_DEBUG_JOB, solv->rules + j);
5066             }
5067         }
5068     }
5069   assert(solv->ruletojob.count == solv->nrules - solv->jobrules);
5070   solv->jobrules_end = solv->nrules;
5071
5072   /* now create infarch and dup rules */
5073   if (!solv->noinfarchcheck)
5074     addinfarchrules(solv, &addedmap);
5075   else
5076     solv->infarchrules = solv->infarchrules_end = solv->nrules;
5077
5078   if (hasdupjob)
5079     {
5080       addduprules(solv, &addedmap);
5081       freedupmaps(solv);        /* no longer needed */
5082     }
5083   else
5084     solv->duprules = solv->duprules_end = solv->nrules;
5085
5086
5087   /* all rules created
5088    * --------------------------------------------------------------
5089    * prepare for solving
5090    */
5091
5092   /* free unneeded memory */
5093   map_free(&addedmap);
5094   map_free(&installcandidatemap);
5095   queue_free(&q);
5096
5097   POOL_DEBUG(SAT_DEBUG_STATS, "%d rpm rules, %d job rules, %d infarch rules, %d dup rules\n", solv->rpmrules_end - 1, solv->jobrules_end - solv->jobrules, solv->infarchrules_end - solv->infarchrules, solv->duprules_end - solv->duprules);
5098
5099   /* create weak map */
5100   map_init(&solv->weakrulemap, solv->nrules);
5101   for (i = 0; i < solv->weakruleq.count; i++)
5102     {
5103       p = solv->weakruleq.elements[i];
5104       MAPSET(&solv->weakrulemap, p);
5105     }
5106
5107   /* all new rules are learnt after this point */
5108   solv->learntrules = solv->nrules;
5109
5110   /* create assertion index. it is only used to speed up
5111    * makeruledecsions() a bit */
5112   for (i = 1, r = solv->rules + i; i < solv->nrules; i++, r++)
5113     if (r->p && !r->w2 && (r->d == 0 || r->d == -1))
5114       queue_push(&solv->ruleassertions, i);
5115
5116   /* disable update rules that conflict with our job */
5117   disablepolicyrules(solv, job);
5118
5119   /* make decisions based on job/update assertions */
5120   makeruledecisions(solv);
5121
5122   /* create watches chains */
5123   makewatches(solv);
5124
5125   POOL_DEBUG(SAT_DEBUG_STATS, "problems so far: %d\n", solv->problems.count);
5126
5127   /*
5128    * ********************************************
5129    * solve!
5130    * ********************************************
5131    */
5132
5133   now = sat_timems(0);
5134   run_solver(solv, 1, solv->dontinstallrecommended ? 0 : 1);
5135   POOL_DEBUG(SAT_DEBUG_STATS, "solver took %d ms\n", sat_timems(now));
5136
5137   /*
5138    * calculate recommended/suggested packages
5139    */
5140   findrecommendedsuggested(solv);
5141
5142   /*
5143    * prepare solution queue if there were problems
5144    */
5145   prepare_solutions(solv);
5146
5147   /*
5148    * finally prepare transaction info
5149    */
5150   solver_create_transaction(solv);
5151
5152   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);
5153   POOL_DEBUG(SAT_DEBUG_STATS, "solver_solve took %d ms\n", sat_timems(solve_start));
5154 }
5155
5156 /***********************************************************************/
5157 /* disk usage computations */
5158
5159 /*-------------------------------------------------------------------
5160  *
5161  * calculate DU changes
5162  */
5163
5164 void
5165 solver_calc_duchanges(Solver *solv, DUChanges *mps, int nmps)
5166 {
5167   Map installedmap;
5168
5169   solver_create_state_maps(solv, &installedmap, 0);
5170   pool_calc_duchanges(solv->pool, &installedmap, mps, nmps);
5171   map_free(&installedmap);
5172 }
5173
5174
5175 /*-------------------------------------------------------------------
5176  *
5177  * calculate changes in install size
5178  */
5179
5180 int
5181 solver_calc_installsizechange(Solver *solv)
5182 {
5183   Map installedmap;
5184   int change;
5185
5186   solver_create_state_maps(solv, &installedmap, 0);
5187   change = pool_calc_installsizechange(solv->pool, &installedmap);
5188   map_free(&installedmap);
5189   return change;
5190 }
5191
5192 void
5193 solver_trivial_installable(Solver *solv, Queue *pkgs, Queue *res)
5194 {
5195   Map installedmap;
5196   solver_create_state_maps(solv, &installedmap, 0);
5197   pool_trivial_installable_noobsoletesmap(solv->pool, &installedmap, pkgs, res, solv->noobsoletes.size ? &solv->noobsoletes : 0);
5198   map_free(&installedmap);
5199 }
5200
5201
5202 #define FIND_INVOLVED_DEBUG 0
5203 void
5204 solver_find_involved(Solver *solv, Queue *installedq, Solvable *ts, Queue *q)
5205 {
5206   Pool *pool = solv->pool;
5207   Map im;
5208   Map installedm;
5209   Solvable *s;
5210   Queue iq;
5211   Queue installedq_internal;
5212   Id tp, ip, p, pp, req, *reqp, sup, *supp;
5213   int i, count;
5214
5215   tp = ts - pool->solvables;
5216   queue_init(&iq);
5217   queue_init(&installedq_internal);
5218   map_init(&im, pool->nsolvables);
5219   map_init(&installedm, pool->nsolvables);
5220
5221   if (!installedq)
5222     {
5223       installedq = &installedq_internal;
5224       if (solv->installed)
5225         {
5226           for (ip = solv->installed->start; ip < solv->installed->end; ip++)
5227             {
5228               s = pool->solvables + ip;
5229               if (s->repo != solv->installed)
5230                 continue;
5231               queue_push(installedq, ip);
5232             }
5233         }
5234     }
5235   for (i = 0; i < installedq->count; i++)
5236     {
5237       ip = installedq->elements[i];
5238       MAPSET(&installedm, ip);
5239       MAPSET(&im, ip);
5240     }
5241
5242   queue_push(&iq, ts - pool->solvables);
5243   while (iq.count)
5244     {
5245       ip = queue_shift(&iq);
5246       if (!MAPTST(&im, ip))
5247         continue;
5248       if (!MAPTST(&installedm, ip))
5249         continue;
5250       MAPCLR(&im, ip);
5251       s = pool->solvables + ip;
5252 #if FIND_INVOLVED_DEBUG
5253       printf("hello %s\n", solvable2str(pool, s));
5254 #endif
5255       if (s->requires)
5256         {
5257           reqp = s->repo->idarraydata + s->requires;
5258           while ((req = *reqp++) != 0)
5259             {
5260               if (req == SOLVABLE_PREREQMARKER)
5261                 continue;
5262               /* count number of installed packages that match */
5263               count = 0;
5264               FOR_PROVIDES(p, pp, req)
5265                 if (MAPTST(&installedm, p))
5266                   count++;
5267               if (count > 1)
5268                 continue;
5269               FOR_PROVIDES(p, pp, req)
5270                 {
5271                   if (MAPTST(&im, p))
5272                     {
5273 #if FIND_INVOLVED_DEBUG
5274                       printf("%s requires %s\n", solvid2str(pool, ip), solvid2str(pool, p));
5275 #endif
5276                       queue_push(&iq, p);
5277                     }
5278                 }
5279             }
5280         }
5281       if (s->recommends)
5282         {
5283           reqp = s->repo->idarraydata + s->recommends;
5284           while ((req = *reqp++) != 0)
5285             {
5286               count = 0;
5287               FOR_PROVIDES(p, pp, req)
5288                 if (MAPTST(&installedm, p))
5289                   count++;
5290               if (count > 1)
5291                 continue;
5292               FOR_PROVIDES(p, pp, req)
5293                 {
5294                   if (MAPTST(&im, p))
5295                     {
5296 #if FIND_INVOLVED_DEBUG
5297                       printf("%s recommends %s\n", solvid2str(pool, ip), solvid2str(pool, p));
5298 #endif
5299                       queue_push(&iq, p);
5300                     }
5301                 }
5302             }
5303         }
5304       if (!iq.count)
5305         {
5306           /* supplements pass */
5307           for (i = 0; i < installedq->count; i++)
5308             {
5309               ip = installedq->elements[i];
5310               s = pool->solvables + ip;
5311               if (!s->supplements)
5312                 continue;
5313               if (!MAPTST(&im, ip))
5314                 continue;
5315               supp = s->repo->idarraydata + s->supplements;
5316               while ((sup = *supp++) != 0)
5317                 if (!dep_possible(solv, sup, &im) && dep_possible(solv, sup, &installedm))
5318                   break;
5319               /* no longer supplemented, also erase */
5320               if (sup)
5321                 {
5322 #if FIND_INVOLVED_DEBUG
5323                   printf("%s supplemented\n", solvid2str(pool, ip));
5324 #endif
5325                   queue_push(&iq, ip);
5326                 }
5327             }
5328         }
5329     }
5330
5331   for (i = 0; i < installedq->count; i++)
5332     {
5333       ip = installedq->elements[i];
5334       if (MAPTST(&im, ip))
5335         queue_push(&iq, ip);
5336     }
5337
5338   while (iq.count)
5339     {
5340       ip = queue_shift(&iq);
5341       if (!MAPTST(&installedm, ip))
5342         continue;
5343       s = pool->solvables + ip;
5344 #if FIND_INVOLVED_DEBUG
5345       printf("bye %s\n", solvable2str(pool, s));
5346 #endif
5347       if (s->requires)
5348         {
5349           reqp = s->repo->idarraydata + s->requires;
5350           while ((req = *reqp++) != 0)
5351             {
5352               FOR_PROVIDES(p, pp, req)
5353                 {
5354                   if (!MAPTST(&im, p))
5355                     {
5356                       if (p == tp)
5357                         continue;
5358 #if FIND_INVOLVED_DEBUG
5359                       printf("%s requires %s\n", solvid2str(pool, ip), solvid2str(pool, p));
5360 #endif
5361                       MAPSET(&im, p);
5362                       queue_push(&iq, p);
5363                     }
5364                 }
5365             }
5366         }
5367       if (s->recommends)
5368         {
5369           reqp = s->repo->idarraydata + s->recommends;
5370           while ((req = *reqp++) != 0)
5371             {
5372               FOR_PROVIDES(p, pp, req)
5373                 {
5374                   if (!MAPTST(&im, p))
5375                     {
5376                       if (p == tp)
5377                         continue;
5378 #if FIND_INVOLVED_DEBUG
5379                       printf("%s recommends %s\n", solvid2str(pool, ip), solvid2str(pool, p));
5380 #endif
5381                       MAPSET(&im, p);
5382                       queue_push(&iq, p);
5383                     }
5384                 }
5385             }
5386         }
5387       if (!iq.count)
5388         {
5389           /* supplements pass */
5390           for (i = 0; i < installedq->count; i++)
5391             {
5392               ip = installedq->elements[i];
5393               if (ip == tp)
5394                 continue;
5395               s = pool->solvables + ip;
5396               if (!s->supplements)
5397                 continue;
5398               if (MAPTST(&im, ip))
5399                 continue;
5400               supp = s->repo->idarraydata + s->supplements;
5401               while ((sup = *supp++) != 0)
5402                 if (dep_possible(solv, sup, &im))
5403                   break;
5404               if (sup)
5405                 {
5406 #if FIND_INVOLVED_DEBUG
5407                   printf("%s supplemented\n", solvid2str(pool, ip));
5408 #endif
5409                   MAPSET(&im, ip);
5410                   queue_push(&iq, ip);
5411                 }
5412             }
5413         }
5414     }
5415
5416   queue_free(&iq);
5417
5418   /* convert map into result */
5419   for (i = 0; i < installedq->count; i++)
5420     {
5421       ip = installedq->elements[i];
5422       if (MAPTST(&im, ip))
5423         continue;
5424       if (ip == ts - pool->solvables)
5425         continue;
5426       queue_push(q, ip);
5427     }
5428   map_free(&im);
5429   map_free(&installedm);
5430   queue_free(&installedq_internal);
5431 }
5432
5433
5434 static void
5435 addrpmruleinfo(Solver *solv, Id p, Id d, int type, Id dep)
5436 {
5437   Pool *pool = solv->pool;
5438   Rule *r;
5439   Id w2, op, od, ow2;
5440
5441   /* check if this creates the rule we're searching for */
5442   r = solv->rules + solv->ruleinfoq->elements[0];
5443   op = r->p;
5444   od = r->d < 0 ? -r->d - 1 : r->d;
5445   ow2 = 0;
5446
5447   /* normalize */
5448   w2 = d > 0 ? 0 : d;
5449   if (p < 0 && d > 0 && (!pool->whatprovidesdata[d] || !pool->whatprovidesdata[d + 1]))
5450     {
5451       w2 = pool->whatprovidesdata[d];
5452       d = 0;
5453
5454     }
5455   if (p > 0 && d < 0)           /* this hack is used for buddy deps */
5456     {
5457       w2 = p;
5458       p = d;
5459     }
5460
5461   if (d > 0)
5462     {
5463       if (p != op && !od)
5464         return;
5465       if (d != od)
5466         {
5467           Id *dp = pool->whatprovidesdata + d;
5468           Id *odp = pool->whatprovidesdata + od;
5469           while (*dp)
5470             if (*dp++ != *odp++)
5471               return;
5472           if (*odp)
5473             return;
5474         }
5475       w2 = 0;
5476       /* handle multiversion conflict rules */
5477       if (p < 0 && pool->whatprovidesdata[d] < 0)
5478         {
5479           w2 = pool->whatprovidesdata[d];
5480           /* XXX: free memory */
5481         }
5482     }
5483   else
5484     {
5485       if (od)
5486         return;
5487       ow2 = r->w2;
5488       if (p > w2)
5489         {
5490           if (w2 != op || p != ow2)
5491             return;
5492         }
5493       else
5494         {
5495           if (p != op || w2 != ow2)
5496             return;
5497         }
5498     }
5499   /* yep, rule matches. record info */
5500   queue_push(solv->ruleinfoq, type);
5501   if (type == SOLVER_RULE_RPM_SAME_NAME)
5502     {
5503       /* we normalize same name order */
5504       queue_push(solv->ruleinfoq, op < 0 ? -op : 0);
5505       queue_push(solv->ruleinfoq, ow2 < 0 ? -ow2 : 0);
5506     }
5507   else
5508     {
5509       queue_push(solv->ruleinfoq, p < 0 ? -p : 0);
5510       queue_push(solv->ruleinfoq, w2 < 0 ? -w2 : 0);
5511     }
5512   queue_push(solv->ruleinfoq, dep);
5513 }
5514
5515 static int
5516 solver_allruleinfos_cmp(const void *ap, const void *bp, void *dp)
5517 {
5518   const Id *a = ap, *b = bp;
5519   int r;
5520
5521   r = a[0] - b[0];
5522   if (r)
5523     return r;
5524   r = a[1] - b[1];
5525   if (r)
5526     return r;
5527   r = a[2] - b[2];
5528   if (r)
5529     return r;
5530   r = a[3] - b[3];
5531   if (r)
5532     return r;
5533   return 0;
5534 }
5535
5536 int
5537 solver_allruleinfos(Solver *solv, Id rid, Queue *rq)
5538 {
5539   Pool *pool = solv->pool;
5540   Rule *r = solv->rules + rid;
5541   int i, j;
5542
5543   queue_empty(rq);
5544   if (rid <= 0 || rid >= solv->rpmrules_end)
5545     {
5546       Id type, from, to, dep;
5547       type = solver_ruleinfo(solv, rid, &from, &to, &dep);
5548       queue_push(rq, type);
5549       queue_push(rq, from);
5550       queue_push(rq, to);
5551       queue_push(rq, dep);
5552       return 1;
5553     }
5554   if (r->p >= 0)
5555     return 0;
5556   queue_push(rq, rid);
5557   solv->ruleinfoq = rq;
5558   addrpmrulesforsolvable(solv, pool->solvables - r->p, 0);
5559   /* also try reverse direction for conflicts */
5560   if ((r->d == 0 || r->d == -1) && r->w2 < 0)
5561     addrpmrulesforsolvable(solv, pool->solvables - r->w2, 0);
5562   solv->ruleinfoq = 0;
5563   queue_shift(rq);
5564   /* now sort & unify em */
5565   if (!rq->count)
5566     return 0;
5567   sat_sort(rq->elements, rq->count / 4, 4 * sizeof(Id), solver_allruleinfos_cmp, 0);
5568   /* throw out identical entries */
5569   for (i = j = 0; i < rq->count; i += 4)
5570     {
5571       if (j)
5572         {
5573           if (rq->elements[i] == rq->elements[j - 4] &&
5574               rq->elements[i + 1] == rq->elements[j - 3] &&
5575               rq->elements[i + 2] == rq->elements[j - 2] &&
5576               rq->elements[i + 3] == rq->elements[j - 1])
5577             continue;
5578         }
5579       rq->elements[j++] = rq->elements[i];
5580       rq->elements[j++] = rq->elements[i + 1];
5581       rq->elements[j++] = rq->elements[i + 2];
5582       rq->elements[j++] = rq->elements[i + 3];
5583     }
5584   rq->count = j;
5585   return j / 4;
5586 }
5587
5588 SolverRuleinfo
5589 solver_ruleinfo(Solver *solv, Id rid, Id *fromp, Id *top, Id *depp)
5590 {
5591   Pool *pool = solv->pool;
5592   Rule *r = solv->rules + rid;
5593   SolverRuleinfo type = SOLVER_RULE_UNKNOWN;
5594
5595   if (fromp)
5596     *fromp = 0;
5597   if (top)
5598     *top = 0;
5599   if (depp)
5600     *depp = 0;
5601   if (rid > 0 && rid < solv->rpmrules_end)
5602     {
5603       Queue rq;
5604       int i;
5605
5606       if (r->p >= 0)
5607         return SOLVER_RULE_RPM;
5608       if (fromp)
5609         *fromp = -r->p;
5610       queue_init(&rq);
5611       queue_push(&rq, rid);
5612       solv->ruleinfoq = &rq;
5613       addrpmrulesforsolvable(solv, pool->solvables - r->p, 0);
5614       /* also try reverse direction for conflicts */
5615       if ((r->d == 0 || r->d == -1) && r->w2 < 0)
5616         addrpmrulesforsolvable(solv, pool->solvables - r->w2, 0);
5617       solv->ruleinfoq = 0;
5618       type = SOLVER_RULE_RPM;
5619       for (i = 1; i < rq.count; i += 4)
5620         {
5621           Id qt, qo, qp, qd;
5622           qt = rq.elements[i];
5623           qp = rq.elements[i + 1];
5624           qo = rq.elements[i + 2];
5625           qd = rq.elements[i + 3];
5626           if (type == SOLVER_RULE_RPM || type > qt)
5627             {
5628               type = qt;
5629               if (fromp)
5630                 *fromp = qp;
5631               if (top)
5632                 *top = qo;
5633               if (depp)
5634                 *depp = qd;
5635             }
5636         }
5637       queue_free(&rq);
5638       return type;
5639     }
5640   if (rid >= solv->jobrules && rid < solv->jobrules_end)
5641     {
5642       Id jidx = solv->ruletojob.elements[rid - solv->jobrules];
5643       if (fromp)
5644         *fromp = jidx;
5645       if (top)
5646         *top = solv->job.elements[jidx];
5647       if (depp)
5648         *depp = solv->job.elements[jidx + 1];
5649       if ((r->d == 0 || r->d == -1) && r->w2 == 0 && r->p == -SYSTEMSOLVABLE && (solv->job.elements[jidx] & SOLVER_SELECTMASK) != SOLVER_SOLVABLE_ONE_OF)
5650         return SOLVER_RULE_JOB_NOTHING_PROVIDES_DEP;
5651       return SOLVER_RULE_JOB;
5652     }
5653   if (rid >= solv->updaterules && rid < solv->updaterules_end)
5654     {
5655       if (fromp)
5656         *fromp = solv->installed->start + (rid - solv->updaterules);
5657       return SOLVER_RULE_UPDATE;
5658     }
5659   if (rid >= solv->featurerules && rid < solv->featurerules_end)
5660     {
5661       if (fromp)
5662         *fromp = solv->installed->start + (rid - solv->featurerules);
5663       return SOLVER_RULE_FEATURE;
5664     }
5665   if (rid >= solv->duprules && rid < solv->duprules_end)
5666     {
5667       if (fromp)
5668         *fromp = -r->p;
5669       if (depp)
5670         *depp = pool->solvables[-r->p].name;
5671       return SOLVER_RULE_DISTUPGRADE;
5672     }
5673   if (rid >= solv->infarchrules && rid < solv->infarchrules_end)
5674     {
5675       if (fromp)
5676         *fromp = -r->p;
5677       if (depp)
5678         *depp = pool->solvables[-r->p].name;
5679       return SOLVER_RULE_INFARCH;
5680     }
5681   if (rid >= solv->learntrules)
5682     {
5683       return SOLVER_RULE_LEARNT;
5684     }
5685   return SOLVER_RULE_UNKNOWN;
5686 }
5687
5688 /* obsolete function */
5689 SolverRuleinfo
5690 solver_problemruleinfo(Solver *solv, Queue *job, Id rid, Id *depp, Id *sourcep, Id *targetp)
5691 {
5692   return solver_ruleinfo(solv, rid, sourcep, targetp, depp);
5693 }
5694
5695 /* EOF */