src/solver.c

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