src/solver.c

   1 /*
   2  * solver.c
   3  *
   4  * SAT based dependency solver
   5  */
   6
   7 #include <stdio.h>
   8 #include <stdlib.h>
   9 #include <unistd.h>
  10 #include <string.h>
  11
  12 #include "solver.h"
  13 #include "bitmap.h"
  14 #include "pool.h"
  15 #include "util.h"
  16 #include "evr.h"
  17
  18 #define RULES_BLOCK 63
  19
  20 static Pool *prune_best_version_arch_sortcmp_data;
  21
  22 /*-----------------------------------------------------------------*/
  23
  24 /*
  25  * prep for prune_best_version_arch
  26  *   sort by name
  27  */
  28
  29 static int
  30 prune_best_version_arch_sortcmp(const void *ap, const void *bp)
  31 {
  32   Pool *pool = prune_best_version_arch_sortcmp_data;
  33   Id a = *(Id *)ap;
  34   Id b = *(Id *)bp;
  35   return pool->solvables[a].name - pool->solvables[b].name;
  36 }
  37
  38
  39 #if 0
  40 static Id
  41 replaces_system(Solver *solv, Id id)
  42 {
  43   Pool *pool = solv->pool;
  44   Source *system = solv->system;
  45   Id *name = pool->solvables[id].name;
  46
  47   FOR_PROVIDES(p, pp, id)
  48     {
  49       s = pool->solvables + p;
  50       if (s->name != name)
  51         continue;
  52       if (p >= system->start && p < system->start + system->nsolvables)
  53         return p;
  54     }
  55 }
  56 #endif
  57
  58 static int
  59 dep_installed(Solver *solv, Id dep)
  60 {
  61   Pool *pool = solv->pool;
  62   Id p, *pp;
  63
  64   if (ISRELDEP(dep))
  65     {
  66       Reldep *rd = GETRELDEP(pool, dep);
  67       if (rd->flags == REL_AND)
  68         {
  69           if (!dep_installed(solv, rd->name))
  70             return 0;
  71           return dep_installed(solv, rd->evr);
  72         }
  73       if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
  74         return dep_installed(solv, rd->evr);
  75     }
  76   FOR_PROVIDES(p, pp, dep)
  77     {
  78       if (p >= solv->system->start && p < solv->system->start + solv->system->nsolvables)
  79         return 1;
  80     }
  81   return 0;
  82 }
  83
  84 static inline int
  85 dep_fulfilled(Solver *solv, Id dep)
  86 {
  87   Pool *pool = solv->pool;
  88   Id p, *pp;
  89
  90   if (ISRELDEP(dep))
  91     {
  92       Reldep *rd = GETRELDEP(pool, dep);
  93       if (rd->flags == REL_AND)
  94         {
  95           if (!dep_fulfilled(solv, rd->name))
  96             return 0;
  97           return dep_fulfilled(solv, rd->evr);
  98         }
  99       if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
 100         return dep_installed(solv, rd->evr);
 101     }
 102   FOR_PROVIDES(p, pp, dep)
 103     {
 104       if (solv->decisionmap[p] > 0)
 105         return 1;
 106     }
 107   return 0;
 108 }
 109
 110 static inline int
 111 dep_possible(Solver *solv, Id dep, Map *m)
 112 {
 113   Pool *pool = solv->pool;
 114   Id p, *pp;
 115
 116   if (ISRELDEP(dep))
 117     {
 118       Reldep *rd = GETRELDEP(pool, dep);
 119       if (rd->flags == REL_AND)
 120         {
 121           if (!dep_possible(solv, rd->name, m))
 122             return 0;
 123           return dep_possible(solv, rd->evr, m);
 124         }
 125       if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
 126         return 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  * prune_to_recommended
 138  *
 139  * XXX: should we prune to requires/suggests that are already
 140  * fulfilled by other packages?
 141  */
 142 static void
 143 prune_to_recommended(Solver *solv, Queue *plist)
 144 {
 145   Pool *pool = solv->pool;
 146   int i, j;
 147   Solvable *s;
 148   Id p, *pp, sup, *supp, rec, *recp, sug, *sugp, enh, *enhp;
 149
 150   if (solv->recommends_index < 0)
 151     {
 152       MAPZERO(&solv->recommendsmap);
 153       MAPZERO(&solv->suggestsmap);
 154       solv->recommends_index = 0;
 155     }
 156   while (solv->recommends_index < solv->decisionq.count)
 157     {
 158       p = solv->decisionq.elements[solv->recommends_index++];
 159       if (p < 0)
 160         continue;
 161       s = pool->solvables + p;
 162       if ((recp = s->recommends) != 0)
 163         while ((rec = *recp++) != 0)
 164           FOR_PROVIDES(p, pp, rec)
 165             MAPSET(&solv->recommendsmap, p);
 166       if ((sugp = s->suggests) != 0)
 167         while ((sug = *sugp++) != 0)
 168           FOR_PROVIDES(p, pp, sug)
 169             MAPSET(&solv->suggestsmap, p);
 170     }
 171   /* prune to recommended/supplemented */
 172   for (i = j = 0; i < plist->count; i++)
 173     {
 174       p = plist->elements[i];
 175       if (MAPTST(&solv->recommendsmap, p))
 176         {
 177           plist->elements[j++] = p;
 178           continue;
 179         }
 180       s = pool->solvables + p;
 181       if (!s->supplements && !s->freshens)
 182         continue;
 183       if ((supp = s->supplements) != 0)
 184         {
 185           while ((sup = *supp++) != 0)
 186             if (dep_fulfilled(solv, sup))
 187               break;
 188           if (!sup)
 189             continue;
 190         }
 191       if ((supp = s->freshens) != 0)
 192         {
 193           while ((sup = *supp++) != 0)
 194             if (dep_fulfilled(solv, sup))
 195               break;
 196           if (!sup)
 197             continue;
 198         }
 199       plist->elements[j++] = s - pool->solvables;
 200     }
 201   if (j)
 202     plist->count = j;
 203
 204   /* prune to suggested/enhanced*/
 205   if (plist->count < 2)
 206     return;
 207   for (i = j = 0; i < plist->count; i++)
 208     {
 209       p = plist->elements[i];
 210       if (MAPTST(&solv->suggestsmap, p))
 211         {
 212           plist->elements[j++] = p;
 213           continue;
 214         }
 215       s = pool->solvables + p;
 216       if (!(enhp = s->enhances))
 217         continue;
 218       while ((enh = *enhp++) != 0)
 219         if (dep_fulfilled(solv, enh))
 220           break;
 221       if (!enh)
 222         continue;
 223       plist->elements[j++] = s - pool->solvables;
 224     }
 225   if (j)
 226     plist->count = j;
 227 }
 228
 229 /*
 230  * prune_best_version_arch
 231  *
 232  * sort list of packages (given through plist) by name and evr
 233  * return result through plist
 234  *
 235  */
 236
 237 /* FIXME: must also look at update packages */
 238
 239 void
 240 prune_best_version_arch(Pool *pool, Queue *plist)
 241 {
 242   Id best = ID_NULL;
 243   int i, j;
 244   Solvable *s;
 245   Id a, bestscore;
 246
 247   if (plist->count < 2)         /* no need to prune for a single entry */
 248     return;
 249   if (pool->verbose) printf("prune_best_version_arch %d\n", plist->count);
 250
 251   /* prune to best architecture */
 252   if (pool->id2arch)
 253     {
 254       bestscore = 0;
 255       for (i = 0; i < plist->count; i++)
 256         {
 257           s = pool->solvables + plist->elements[i];
 258           a = s->arch;
 259           if (a > pool->lastarch)
 260             continue;
 261           a = pool->id2arch[a];
 262           if (!bestscore || (a & 0xffff0000) < bestscore)
 263             bestscore = a & 0xffff0000;
 264         }
 265       for (i = j = 0; i < plist->count; i++)
 266         {
 267           s = pool->solvables + plist->elements[i];
 268           a = s->arch;
 269           if (a > pool->lastarch)
 270             continue;
 271           a = pool->id2arch[a];
 272           /* a == 1 -> noarch */
 273           if (a != 1 && (a & 0xffff0000) != bestscore)
 274             continue;
 275           plist->elements[j++] = plist->elements[i];
 276         }
 277       plist->count = j;
 278       if (j == 0)
 279         return;
 280     }
 281
 282   prune_best_version_arch_sortcmp_data = pool;
 283   /* sort by name first */
 284   qsort(plist->elements, plist->count, sizeof(Id), prune_best_version_arch_sortcmp);
 285
 286   /* now find best 'per name' */
 287   for (i = j = 0; i < plist->count; i++)
 288     {
 289       s = pool->solvables + plist->elements[i];
 290
 291       if (pool->verbose) printf("- %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
 292
 293       if (!best)                       /* if no best yet, the current is best */
 294         {
 295           best = plist->elements[i];
 296           continue;
 297         }
 298
 299       /* name switch: re-init */
 300       if (pool->solvables[best].name != s->name)   /* new name */
 301         {
 302           if (pool->verbose) printf("BEST: %s-%s.%s\n", id2str(pool, pool->solvables[best].name), id2str(pool, pool->solvables[best].evr), id2str(pool, pool->solvables[best].arch));
 303           plist->elements[j++] = best; /* move old best to front */
 304           best = plist->elements[i];   /* take current as new best */
 305           continue;
 306         }
 307
 308       if (pool->solvables[best].evr != s->evr)   /* compare evr */
 309         {
 310           if (evrcmp(pool, pool->solvables[best].evr, s->evr) < 0)
 311             best = plist->elements[i];
 312         }
 313     }
 314
 315   if (best == ID_NULL)
 316     best = plist->elements[0];
 317
 318   /* XXX also check obsoletes! */
 319   if (pool->verbose) printf("BEST: %s-%s.%s\n", id2str(pool, pool->solvables[best].name), id2str(pool, pool->solvables[best].evr), id2str(pool, pool->solvables[best].arch));
 320
 321   plist->elements[j++] = best;
 322   plist->count = j;
 323
 324 }
 325
 326 /*-----------------------------------------------------------------*/
 327
 328 /*
 329  * print rules
 330  */
 331
 332 static void
 333 printruleelement(Solver *solv, Rule *r, Id v)
 334 {
 335   Pool *pool = solv->pool;
 336   Solvable *s;
 337   if (v < 0)
 338     {
 339       s = pool->solvables + -v;
 340       printf("    !%s-%s.%s [%d]", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch), -v);
 341     }
 342   else
 343     {
 344       s = pool->solvables + v;
 345       printf("    %s-%s.%s [%d]", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch), v);
 346     }
 347   if (r)
 348     {
 349       if (r->w1 == v)
 350         printf(" (w1)");
 351       if (r->w2 == v)
 352         printf(" (w2)");
 353     }
 354   if (solv->decisionmap[s - pool->solvables] > 0)
 355     printf(" I.%d", solv->decisionmap[s - pool->solvables]);
 356   if (solv->decisionmap[s - pool->solvables] < 0)
 357     printf(" C.%d", -solv->decisionmap[s - pool->solvables]);
 358   printf("\n");
 359 }
 360
 361
 362 /*
 363  * print rule
 364  */
 365
 366 static void
 367 printrule(Solver *solv, Rule *r)
 368 {
 369   int i;
 370   Id v;
 371
 372   if (r >= solv->rules && r < solv->rules + solv->nrules)   /* r is a solver rule */
 373     printf("Rule #%d:\n", (int)(r - solv->rules));
 374   else
 375     printf("Rule:\n");                 /* r is any rule */
 376   for (i = 0; ; i++)
 377     {
 378       if (i == 0)
 379         v = r->p;
 380       else if (r->d == ID_NULL)
 381         {
 382           if (i == 2)
 383             break;
 384           v = r->w2;
 385         }
 386       else
 387         v = solv->pool->whatprovidesdata[r->d + i - 1];
 388       if (v == ID_NULL)
 389         break;
 390       printruleelement(solv, r, v);
 391     }
 392   printf("    next: %d %d\n", r->n1, r->n2);
 393 }
 394
 395
 396 /*-----------------------------------------------------------------*/
 397
 398 /*
 399  * Rule handling
 400  */
 401
 402 static Pool *unifyrules_sortcmp_data;
 403
 404 /*
 405  * compare rules for unification sort
 406  */
 407
 408 static int
 409 unifyrules_sortcmp(const void *ap, const void *bp)
 410 {
 411   Pool *pool = unifyrules_sortcmp_data;
 412   Rule *a = (Rule *)ap;
 413   Rule *b = (Rule *)bp;
 414   Id *ad, *bd;
 415   int x;
 416
 417   x = a->p - b->p;
 418   if (x)
 419     return x;                          /* p differs */
 420
 421   /* identical p */
 422   if (a->d == 0 && b->d == 0)
 423     return a->w2 - b->w2;              /* assertion: return w2 diff */
 424
 425   if (a->d == 0)                       /* a is assertion, b not */
 426     {
 427       x = a->w2 - pool->whatprovidesdata[b->d];
 428       return x ? x : -1;
 429     }
 430
 431   if (b->d == 0)                       /* b is assertion, a not */
 432     {
 433       x = pool->whatprovidesdata[a->d] - b->w2;
 434       return x ? x : 1;
 435     }
 436
 437   /* compare whatprovidesdata */
 438   ad = pool->whatprovidesdata + a->d;
 439   bd = pool->whatprovidesdata + b->d;
 440   while (*bd)
 441     if ((x = *ad++ - *bd++) != 0)
 442       return x;
 443   return *ad;
 444 }
 445
 446
 447 /*
 448  * unify rules
 449  */
 450
 451 static void
 452 unifyrules(Solver *solv)
 453 {
 454   int i, j;
 455   Rule *ir, *jr;
 456
 457   if (solv->nrules <= 1)               /* nothing to unify */
 458     return;
 459
 460   /* sort rules first */
 461   unifyrules_sortcmp_data = solv->pool;
 462   qsort(solv->rules + 1, solv->nrules - 1, sizeof(Rule), unifyrules_sortcmp);
 463
 464   /* prune rules
 465    * i = unpruned
 466    * j = pruned
 467    */
 468   jr = 0;
 469   for (i = j = 1, ir = solv->rules + 1; i < solv->nrules; i++, ir++)
 470     {
 471       if (jr && !unifyrules_sortcmp(ir, jr))
 472         continue;                      /* prune! */
 473       jr = solv->rules + j++;          /* keep! */
 474       if (ir != jr)
 475         *jr = *ir;
 476     }
 477
 478   /* reduced count from nrules to j rules */
 479   if (solv->pool->verbose) printf("pruned rules from %d to %d\n", solv->nrules, j);
 480
 481   /* adapt rule buffer */
 482   solv->rules = (Rule *)xrealloc(solv->rules, ((solv->nrules + RULES_BLOCK) & ~RULES_BLOCK) * sizeof(Rule));
 483   solv->nrules = j;
 484 #if 1
 485   {
 486     int binr = 0;
 487     int dc = 0;
 488     Id *dp;
 489     Rule *r;
 490
 491     for (i = 1; i < solv->nrules; i++)
 492       {
 493         r = solv->rules + i;
 494         if (r->d == 0)                 /* assertion */
 495           {
 496             binr++;
 497             continue;
 498           }
 499         dp = solv->pool->whatprovidesdata + r->d;
 500         while (*dp++)
 501           dc++;
 502       }
 503     if (solv->pool->verbose)
 504       {
 505         printf("  binary: %d\n", binr);
 506         printf("  normal: %d\n", solv->nrules - 1 - binr);
 507         printf("  normal lits: %d\n", dc);
 508       }
 509   }
 510 #endif
 511 }
 512
 513 #if 0
 514
 515 /*
 516  * hash rule
 517  */
 518
 519 static Hashval
 520 hashrule(Solver *solv, Id p, Id d, int n)
 521 {
 522   unsigned int x = (unsigned int)p;
 523   int *dp;
 524
 525   if (n <= 1)
 526     return (x * 37) ^ (unsigned int)d;
 527   dp = solv->pool->whatprovidesdata + d;
 528   while (*dp)
 529     x = (x * 37) ^ (unsigned int)*dp++;
 530   return x;
 531 }
 532 #endif
 533
 534
 535 /*
 536  * add rule
 537  *  p = direct literal; > 0 for learnt, < 0 for installed pkg (rpm)
 538  *  d, if < 0 direct literal, if > 0 offset into whatprovides, if == 0 rule is assertion (look at p only)
 539  *
 540  *
 541  * A requires b, b provided by B1,B2,B3 => (-A|B1|B2|B3)
 542  *
 543  * p < 0 : rule from rpm (installed pkg)
 544  * d > 0 : Offset in whatprovidesdata (list of providers)
 545  *
 546  * A conflicts b, b provided by B1,B2,B3 => (-A|-B1), (-A|-B2), (-A|-B3)
 547  *  d < 0: Id of solvable (e.g. B1)
 548  *
 549  * d == 0: unary rule, assertion => (A) or (-A)
 550  *
 551  *   Install:    p > 0, d = 0   (A)             user requested install
 552  *   Remove:     p < 0, d = 0   (-A)            user requested remove
 553  *   Requires:   p < 0, d > 0   (-A|B1|B2|...)  d: <list of providers for requirement of p>
 554  *   Updates:    p > 0, d > 0   (A|B1|B2|...)   d: <list of updates for solvable p>
 555  *   Conflicts:  p < 0, d < 0   (-A|-B)         either p (conflict issuer) or d (conflict provider)
 556  *   ?           p > 0, d < 0   (A|-B)
 557  *   No-op ?:    p = 0, d = 0   (null)          (used as policy rule placeholder)
 558  */
 559
 560 static Rule *
 561 addrule(Solver *solv, Id p, Id d)
 562 {
 563   Rule *r = 0;
 564   Id *dp = 0;
 565
 566   int n = 0;                           /* number of literals in rule - 1
 567                                           0 = direct assertion (single literal)
 568                                           1 = binary rule
 569                                         */
 570
 571   /* it often happenes that requires lead to adding the same rpm rule
 572    * multiple times, so we prune those duplicates right away to make
 573    * the work for unifyrules a bit easier */
 574
 575   if (solv->nrules && !solv->jobrules)
 576     {
 577       r = solv->rules + solv->nrules - 1;   /* get the last added rule */
 578       if (r->p == p && r->d == d && d != 0)   /* identical and not user requested */
 579         return r;
 580     }
 581
 582   if (d < 0)
 583     {
 584       if (p == d)
 585         return 0;                      /* ignore self conflict */
 586       n = 1;
 587     }
 588   else if (d == 0)                     /* user requested */
 589     n = 0;
 590   else
 591     {
 592       for (dp = solv->pool->whatprovidesdata + d; *dp; dp++, n++)
 593         if (*dp == -p)
 594           return 0;                     /* rule is self-fulfilling */
 595       if (n == 1)
 596         d = dp[-1];
 597     }
 598
 599   if (n == 0)                          /* direct assertion */
 600     {
 601       if (!solv->jobrules)
 602         {
 603           /* this is a rpm rule assertion, we do not have to allocate it */
 604           /* it can be identified by a level of 1 and a zero reason */
 605           if (p > 0)
 606             abort();
 607           if (solv->decisionmap[-p] > 0 || solv->decisionmap[-p] < -1)
 608             abort();
 609           if (solv->decisionmap[-p])
 610             return NULL;
 611           queuepush(&solv->decisionq, p);
 612           queuepush(&solv->decisionq_why, 0);
 613           solv->decisionmap[-p] = -1;
 614           return 0;
 615         }
 616     }
 617   else if (n == 1 && p > d)
 618     {
 619       /* smallest literal first so we can find dups */
 620       n = p;
 621       p = d;
 622       d = n;
 623       n = 1;                           /* re-set n, was used as temp var */
 624     }
 625
 626   /* check if the last added rule is exactly the same as what we're looking for. */
 627   if (r && n == 1 && !r->d && r->p == p && r->w2 == d)
 628     return r;
 629
 630   if (r && n > 1 && r->d && r->p == p)
 631     {
 632       Id *dp2;
 633       if (d == r->d)
 634         return r;
 635       dp2 = solv->pool->whatprovidesdata + r->d;
 636       for (dp = solv->pool->whatprovidesdata + d; *dp; dp++, dp2++)
 637         if (*dp != *dp2)
 638           break;
 639       if (*dp == *dp2)
 640         return r;
 641    }
 642
 643   /*
 644    * allocate new rule
 645    */
 646
 647   /* check and extend rule buffer */
 648   if ((solv->nrules & RULES_BLOCK) == 0)
 649     {
 650       solv->rules = (Rule *)xrealloc(solv->rules, (solv->nrules + (RULES_BLOCK + 1)) * sizeof(Rule));
 651     }
 652
 653   r = solv->rules + solv->nrules++;    /* point to rule space */
 654
 655   r->p = p;
 656   if (n == 0)
 657     {
 658       /* direct assertion, no watch needed */
 659       r->d = 0;
 660       r->w1 = p;
 661       r->w2 = 0;
 662     }
 663   else if (n == 1)
 664     {
 665       /* binary rule */
 666       r->d = 0;
 667       r->w1 = p;
 668       r->w2 = d;
 669     }
 670   else
 671     {
 672       r->d = d;
 673       r->w1 = p;
 674       r->w2 = solv->pool->whatprovidesdata[d];
 675     }
 676   r->n1 = 0;
 677   r->n2 = 0;
 678   return r;
 679 }
 680
 681
 682 /* go through system and job rules and add direct assertions
 683  * to the decisionqueue. If we find a conflict, disable rules and
 684  * add them to problem queue.
 685  */
 686 static void
 687 makeruledecisions(Solver *solv)
 688 {
 689   int i, ri;
 690   Rule *r, *rr;
 691   Id v, vv;
 692
 693   /* no learnt rules for now */
 694   if (solv->learntrules && solv->learntrules != solv->nrules)
 695     abort();
 696
 697   for (ri = solv->jobrules, r = solv->rules + ri; ri < solv->nrules; ri++, r++)
 698     {
 699       if (!r->w1 || r->w2)
 700         continue;
 701       v = r->p;
 702       vv = v > 0 ? v : -v;
 703       if (solv->decisionmap[vv] == 0)
 704         {
 705           queuepush(&solv->decisionq, v);
 706           queuepush(&solv->decisionq_why, r - solv->rules);
 707           solv->decisionmap[vv] = v > 0 ? 1 : -1;
 708           continue;
 709         }
 710       if (v > 0 && solv->decisionmap[vv] > 0)
 711         continue;
 712       if (v < 0 && solv->decisionmap[vv] < 0)
 713         continue;
 714       /* found a conflict! */
 715       /* if we are weak, just disable ourself */
 716       if (ri >= solv->weakrules)
 717         {
 718           printf("conflict, but I am weak, disabling ");
 719           printrule(solv, r);
 720           r->w1 = 0;
 721           continue;
 722         }
 723       for (i = 0; i < solv->decisionq.count; i++)
 724         if (solv->decisionq.elements[i] == -v)
 725           break;
 726       if (i == solv->decisionq.count)
 727         abort();
 728       if (solv->decisionq_why.elements[i] == 0)
 729         {
 730           /* conflict with rpm rule, need only disable our rule */
 731           printf("conflict with rpm rule, disabling rule #%d\n", ri);
 732           queuepush(&solv->problems, r - solv->rules);
 733           queuepush(&solv->problems, 0);
 734           r->w1 = 0;    /* disable */
 735           continue;
 736         }
 737       /* conflict with another job or system rule */
 738       /* remove old decision */
 739       printf("conflicting system/job rules over literal %d\n", vv);
 740       solv->decisionmap[vv] = 0;
 741       for (; i + 1 < solv->decisionq.count; i++)
 742         {
 743           solv->decisionq.elements[i] = solv->decisionq.elements[i + 1];
 744           solv->decisionq_why.elements[i] = solv->decisionq_why.elements[i + 1];
 745         }
 746       solv->decisionq.count--;
 747       solv->decisionq_why.count--;
 748       /* push all of our rules asserting this literal on the problem stack */
 749       for (i = solv->jobrules, rr = solv->rules + i; i < solv->nrules; i++, rr++)
 750         {
 751           if (!rr->w1 || rr->w2)
 752             continue;
 753           if (rr->p != v && rr->p != -v)
 754             continue;
 755           printf(" - disabling rule #%d\n", i);
 756           queuepush(&solv->problems, i);
 757           rr->w1 = 0;   /* disable */
 758         }
 759       queuepush(&solv->problems, 0);
 760     }
 761 }
 762
 763
 764 /*
 765  * add (install) rules for solvable
 766  *
 767  */
 768
 769 static void
 770 addrulesforsolvable(Solver *solv, Solvable *s, Map *m)
 771 {
 772   Pool *pool = solv->pool;
 773   Source *system = solv->system;
 774   Queue q;
 775   Id qbuf[64];
 776   int i;
 777   int dontfix;
 778   Id req, *reqp;
 779   Id con, *conp;
 780   Id obs, *obsp;
 781   Id rec, *recp;
 782   Id p, *pp;
 783   Id *dp;
 784   Id n;
 785
 786   queueinit_buffer(&q, qbuf, sizeof(qbuf)/sizeof(*qbuf));
 787   queuepush(&q, s - pool->solvables);   /* push solvable Id */
 788
 789   while (q.count)
 790     {
 791       /*
 792        * n: Id of solvable
 793        * s: Pointer to solvable
 794        */
 795
 796       n = queueshift(&q);
 797       if (MAPTST(m, n))                /* continue if already done */
 798         continue;
 799
 800       MAPSET(m, n);
 801       s = pool->solvables + n;         /* s = Solvable in question */
 802
 803       dontfix = 0;
 804       if (system
 805           && !solv->fixsystem
 806           && n >= system->start        /* is it installed? */
 807           && n < system->start + system->nsolvables)
 808       {
 809         dontfix = 1;                   /* dont care about broken rpm deps */
 810       }
 811
 812       /*-----------------------------------------
 813        * check requires of s
 814        */
 815
 816       if ((reqp = s->requires) != ID_NULL)
 817         {
 818           while ((req = *reqp++) != ID_NULL)
 819             {
 820               if (req == SOLVABLE_PREREQMARKER)   /* skip the marker */
 821                 continue;
 822
 823               dp = GET_PROVIDESP(req, p);      /* get providers of req */
 824
 825               if (!*dp                       /* dont care if noone provides rpmlib() */
 826                   && !strncmp(id2str(pool, req), "rpmlib(", 7))
 827                 {
 828                   continue;
 829                 }
 830
 831               if (dontfix)             /* dont care about breakage */
 832                 {
 833                   /* the strategy here is to not insist on dependencies
 834                    * that are already broken. so if we find one provider
 835                    * that was already installed, we know that the
 836                    * dependency was not broken before so we enforce it */
 837                   for (i = 0; dp[i]; i++)       /* for all providers */
 838                     {
 839                       if (dp[i] >= system->start && dp[i] < system->start + system->nsolvables)
 840                         break;         /* provider is installed */
 841                     }
 842                   if (!dp[i])          /* previously broken dependency */
 843                     {
 844                       if (pool->verbose) printf("ignoring broken requires %s of system package %s-%s.%s\n", dep2str(pool, req), id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
 845                       continue;
 846                     }
 847                 }
 848
 849               if (!*dp)
 850                 {
 851                   /* nothing provides req! */
 852   #if 1
 853                   if (pool->verbose) printf("package %s-%s.%s [%ld] is not installable (%s)\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch), (long int)(s - pool->solvables), dep2str(pool, req));
 854   #endif
 855                   addrule(solv, -n, 0); /* mark requestor as uninstallable */
 856                   if (solv->rc_output)
 857                     printf(">!> !unflag %s-%s.%s[%s]\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch), source_name(s->source));
 858                   continue;
 859                 }
 860   #if 0
 861               printf("addrule %s-%s.%s %s %d %d\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch), dep2str(pool, req), -n, dp - pool->whatprovidesdata);
 862               for (i = 0; dp[i]; i++)
 863                 printf("  %s-%s.%s\n", id2str(pool, pool->solvables[dp[i]].name), id2str(pool, pool->solvables[dp[i]].evr), id2str(pool, pool->solvables[dp[i]].arch));
 864   #endif
 865               /* add 'requires' dependency */
 866               /* rule: (-requestor|provider1|provider2|...|providerN) */
 867               addrule(solv, -n, dp - pool->whatprovidesdata);
 868
 869               /* descend the dependency tree */
 870               for (; *dp; dp++)   /* loop through all providers */
 871                 {
 872                   if (!MAPTST(m, *dp))
 873                     queuepush(&q, *dp);
 874                 }
 875
 876             } /* while, requirements of n */
 877
 878         } /* if, requirements */
 879
 880
 881       /*-----------------------------------------
 882        * check conflicts of s
 883        */
 884
 885       if ((conp = s->conflicts) != 0)
 886         {
 887           while ((con = *conp++) != 0)
 888             {
 889               FOR_PROVIDES(p, pp, con)
 890                 {
 891                    /* dontfix: dont care about conflicts with already installed packs */
 892                   if (dontfix && p >= system->start && p < system->start + system->nsolvables)
 893                     continue;
 894                  /* rule: -n|-p: either solvable _or_ provider of conflict */
 895                   addrule(solv, -n, -p);
 896                 }
 897             }
 898         }
 899
 900       /*-----------------------------------------
 901        * check obsoletes if not installed
 902        */
 903       if (!system || n < system->start || n >= (system->start + system->nsolvables))
 904         {                              /* not installed */
 905           if ((obsp = s->obsoletes) != 0)
 906             {
 907               while ((obs = *obsp++) != 0)
 908                 {
 909                   FOR_PROVIDES(p, pp, obs)
 910                     addrule(solv, -n, -p);
 911                 }
 912             }
 913           FOR_PROVIDES(p, pp, s->name)
 914             {
 915               if (s->name == pool->solvables[p].name)
 916                 addrule(solv, -n, -p);
 917             }
 918         }
 919
 920       /*-----------------------------------------
 921        * add recommends to the rule list
 922        */
 923       if ((recp = s->recommends) != 0)
 924         while ((rec = *recp++) != 0)
 925           {
 926             FOR_PROVIDES(p, pp, rec)
 927               if (!MAPTST(m, p))
 928                 queuepush(&q, p);
 929           }
 930     }
 931   queuefree(&q);
 932 }
 933
 934 static void
 935 addrulesforsupplements(Solver *solv, Map *m)
 936 {
 937   Pool *pool = solv->pool;
 938   Solvable *s;
 939   Id sup, *supp;
 940   int i, n;
 941
 942   if (pool->verbose) printf("addrulesforsupplements... (%d)\n", solv->nrules);
 943   for (i = n = 1; n < pool->nsolvables; i++, n++)
 944     {
 945       if (i == pool->nsolvables)
 946         i = 1;
 947       if (MAPTST(m, i))
 948         continue;
 949       s = pool->solvables + i;
 950       if (!pool_installable(pool, s))
 951         continue;
 952       sup = 0;
 953       if ((supp = s->supplements) != 0)
 954         while ((sup = *supp++) != ID_NULL)
 955           if (dep_possible(solv, sup, m))
 956             break;
 957       if (!sup && (supp = s->freshens) != 0)
 958         while ((sup = *supp++) != ID_NULL)
 959           if (dep_possible(solv, sup, m))
 960             break;
 961       if (!sup)
 962         continue;
 963       addrulesforsolvable(solv, s, m);
 964       n = 0;
 965     }
 966   if (pool->verbose) printf("done. (%d)\n", solv->nrules);
 967 }
 968
 969 static void
 970 addrulesforenhances(Solver *solv, Map *m)
 971 {
 972   Pool *pool = solv->pool;
 973   int i;
 974   Solvable *s;
 975   Id p, *pp, enh, *enhp, obs, *obsp, con, *conp;
 976
 977   if (pool->verbose) printf("addrulesforenhances... (%d)\n", solv->nrules);
 978   for (i = 1; i < pool->nsolvables; i++)
 979     {
 980       if (MAPTST(m, i))
 981         continue;
 982       s = pool->solvables + i;
 983       if ((enhp = s->enhances) == 0)
 984         continue;
 985       if (!pool_installable(pool, s))
 986         continue;
 987       while ((enh = *enhp++) != ID_NULL)
 988         if (dep_possible(solv, enh, m))
 989           break;
 990       if (!enh)
 991         continue;
 992       if ((conp = s->conflicts) != 0)
 993         while ((con = *conp++) != 0)
 994           FOR_PROVIDES(p, pp, con)
 995             addrule(solv, -i, -p);
 996       if ((obsp = s->obsoletes) != 0)
 997         while ((obs = *obsp++) != ID_NULL)
 998           FOR_PROVIDES(p, pp, obs)
 999             addrule(solv, -i, -p);
1000       FOR_PROVIDES(p, pp, s->name)
1001         if (s->name == pool->solvables[p].name)
1002           addrule(solv, -i, -p);
1003     }
1004 }
1005
1006
1007 static inline int
1008 archchanges(Pool *pool, Solvable *s1, Solvable *s2)
1009 {
1010   Id a1 = s1->arch, a2 = s2->arch;
1011
1012   /* we allow changes to/from noarch */
1013   if (a1 == a2 || a1 == ARCH_NOARCH || a2 == ARCH_NOARCH)
1014     return 0;
1015   if (!pool->id2arch)
1016     return 0;
1017   a1 = a1 <= pool->lastarch ? pool->id2arch[a1] : 0;
1018   a2 = a2 <= pool->lastarch ? pool->id2arch[a2] : 0;
1019   if (((a1 ^ a2) & 0xffff0000) != 0)
1020     return 1;
1021   return 0;
1022 }
1023
1024
1025 static void
1026 findupdatepackages(Solver *solv, Solvable *s, Queue *qs, Map *m, int allowdowngrade, int allowarchchange)
1027 {
1028   /* system packages get a special upgrade allowed rule */
1029   Pool *pool = solv->pool;
1030   Id p, *pp, n, p2, *pp2;
1031   Id obs, *obsp;
1032
1033   QUEUEEMPTY(qs);
1034   /*
1035    * s = solvable ptr
1036    * n = solvable Id
1037    */
1038   n = s - pool->solvables;
1039   if (m && !MAPTST(m, n))       /* add rule for s if not already done */
1040     addrulesforsolvable(solv, s, m);
1041
1042   /*
1043    * look for updates for s
1044    */
1045   FOR_PROVIDES(p, pp, s->name)  /* every provider of s' name */
1046     {
1047       if (p == n)               /* skip itself */
1048         continue;
1049
1050       if (s->name == pool->solvables[p].name)   /* name match */
1051         {
1052           if (!allowdowngrade                   /* consider downgrades ? */
1053               && evrcmp(pool, s->evr, pool->solvables[p].evr) > 0)
1054             continue;
1055           /* XXX */
1056           if (!allowarchchange && archchanges(pool, s, pool->solvables + p))
1057             continue;
1058         }
1059       else if (!solv->noupdateprovide && (obsp = pool->solvables[p].obsoletes) != 0)   /* provides/obsoletes combination ? */
1060         {
1061           while ((obs = *obsp++) != 0)  /* for all obsoletes */
1062             {
1063               FOR_PROVIDES(p2, pp2, obs)   /* and all matching providers of the obsoletes */
1064                 {
1065                   if (p2 == n)          /* match ! */
1066                     break;
1067                 }
1068               if (p2)                   /* match! */
1069                 break;
1070             }
1071           if (!obs)                     /* continue if no match */
1072             continue;
1073           /* here we have 'p' with a matching provides/obsoletes combination
1074            * thus flagging p as a valid update candidate for s
1075            */
1076         }
1077       else
1078         continue;
1079       queuepush(qs, p);
1080
1081       if (m && !MAPTST(m, p))           /* mark p for install if not already done */
1082         addrulesforsolvable(solv, pool->solvables + p, m);
1083     }
1084   if (solv->noupdateprovide && solv->obsoletes && solv->obsoletes[n - solv->system->start])
1085     {
1086       for (pp = solv->obsoletes_data + solv->obsoletes[n - solv->system->start]; (p = *pp++) != 0;)
1087         {
1088           queuepush(qs, p);
1089           if (m && !MAPTST(m, p))               /* mark p for install if not already done */
1090             addrulesforsolvable(solv, pool->solvables + p, m);
1091         }
1092     }
1093 }
1094
1095 /*
1096  * add rule for update
1097  *   (A|A1|A2|A3...)  An = update candidates for A
1098  *
1099  * s = (installed) solvable
1100  * m = 'addedmap', bit set if 'install' rule for solvable exists
1101  */
1102
1103 static void
1104 addupdaterule(Solver *solv, Solvable *s, Map *m, int allowdowngrade, int allowarchchange, int dontaddrule)
1105 {
1106   /* system packages get a special upgrade allowed rule */
1107   Pool *pool = solv->pool;
1108   Id p, d;
1109   Rule *r;
1110   Queue qs;
1111   Id qsbuf[64];
1112
1113   queueinit_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
1114   findupdatepackages(solv, s, &qs, m, allowdowngrade, allowarchchange);
1115   p = s - pool->solvables;
1116   if (dontaddrule)      /* we consider update candidates but dont force them */
1117     {
1118       queuefree(&qs);
1119       return;
1120     }
1121
1122   if (qs.count == 0)                   /* no updates found */
1123     {
1124 #if 0
1125       printf("new update rule: must keep %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
1126 #endif
1127       addrule(solv, p, 0);              /* request 'install' of s */
1128       queuefree(&qs);
1129       return;
1130     }
1131
1132   d = pool_queuetowhatprovides(pool, &qs);   /* intern computed provider queue */
1133   queuefree(&qs);
1134   r = addrule(solv, p, d);             /* allow update of s */
1135 #if 0
1136   printf("new update rule ");
1137   if (r)
1138     printrule(solv, r);
1139 #endif
1140 }
1141
1142
1143 /*-----------------------------------------------------------------*/
1144 /* watches */
1145
1146
1147 /*
1148  * makewatches
1149  *
1150  * initial setup for all watches
1151  */
1152
1153 static void
1154 makewatches(Solver *solv)
1155 {
1156   Rule *r;
1157   int i;
1158   int nsolvables = solv->pool->nsolvables;
1159
1160   xfree(solv->watches);
1161                                        /* lower half for removals, upper half for installs */
1162   solv->watches = (Id *)xcalloc(2 * nsolvables, sizeof(Id));
1163 #if 1
1164   /* do it reverse so rpm rules get triggered first */
1165   for (i = 1, r = solv->rules + solv->nrules - 1; i < solv->nrules; i++, r--)
1166 #else
1167   for (i = 1, r = solv->rules + 1; i < solv->nrules; i++, r++)
1168 #endif
1169     {
1170       if (!r->w1                       /* rule is disabled */
1171           || !r->w2)                   /* rule is assertion */
1172         continue;
1173
1174       /* see addwatches(solv, r) */
1175       r->n1 = solv->watches[nsolvables + r->w1];
1176       solv->watches[nsolvables + r->w1] = r - solv->rules;
1177
1178       r->n2 = solv->watches[nsolvables + r->w2];
1179       solv->watches[nsolvables + r->w2] = r - solv->rules;
1180     }
1181 }
1182
1183
1184 /*
1185  * add watches (for rule)
1186  */
1187
1188 static void
1189 addwatches(Solver *solv, Rule *r)
1190 {
1191   int nsolvables = solv->pool->nsolvables;
1192
1193   r->n1 = solv->watches[nsolvables + r->w1];
1194   solv->watches[nsolvables + r->w1] = r - solv->rules;
1195
1196   r->n2 = solv->watches[nsolvables + r->w2];
1197   solv->watches[nsolvables + r->w2] = r - solv->rules;
1198 }
1199
1200
1201 /*-----------------------------------------------------------------*/
1202 /* rule propagation */
1203
1204 #define DECISIONMAP_TRUE(p) ((p) > 0 ? (decisionmap[p] > 0) : (decisionmap[-p] < 0))
1205
1206 /*
1207  * propagate
1208  *
1209  * propagate decision to all rules
1210  */
1211
1212 static Rule *
1213 propagate(Solver *solv, int level)
1214 {
1215   Pool *pool = solv->pool;
1216   Id *rp, *nrp;
1217   Rule *r;
1218   Id p, pkg, ow;
1219   Id *dp;
1220   Id *decisionmap = solv->decisionmap;
1221   Id *watches = solv->watches + pool->nsolvables;
1222
1223   while (solv->propagate_index < solv->decisionq.count)
1224     {
1225       /* negative because our watches trigger if literal goes FALSE */
1226       pkg = -solv->decisionq.elements[solv->propagate_index++];
1227 #if 0
1228   printf("popagate for decision %d level %d\n", -pkg, level);
1229   printruleelement(solv, 0, -pkg);
1230 #endif
1231       for (rp = watches + pkg; *rp; rp = nrp)
1232         {
1233           r = solv->rules + *rp;
1234 #if 0
1235   printf("  watch triggered ");
1236   printrule(solv, r);
1237 #endif
1238           if (pkg == r->w1)
1239             {
1240               ow = r->w2;
1241               nrp = &r->n1;
1242             }
1243           else
1244             {
1245               ow = r->w1;
1246               nrp = &r->n2;
1247             }
1248           /* if clause is TRUE, nothing to do */
1249           if (DECISIONMAP_TRUE(ow))
1250             continue;
1251
1252           if (r->d)
1253             {
1254               /* not a binary clause, check if we need to move our watch */
1255               if (r->p && r->p != ow && !DECISIONMAP_TRUE(-r->p))
1256                 p = r->p;
1257               else
1258                 for (dp = pool->whatprovidesdata + r->d; (p = *dp++) != 0;)
1259                   if (p != ow && !DECISIONMAP_TRUE(-p))
1260                     break;
1261               if (p)
1262                 {
1263                   /* p is free to watch, move watch to p */
1264 #if 0
1265                   if (p > 0)
1266                     printf("    -> move w%d to %s-%s.%s\n", (pkg == r->w1 ? 1 : 2), id2str(pool, pool->solvables[p].name), id2str(pool, pool->solvables[p].evr), id2str(pool, pool->solvables[p].arch));
1267                   else
1268                     printf("    -> move w%d to !%s-%s.%s\n", (pkg == r->w1 ? 1 : 2), id2str(pool, pool->solvables[-p].name), id2str(pool, pool->solvables[-p].evr), id2str(pool, pool->solvables[-p].arch));
1269 #endif
1270                   *rp = *nrp;
1271                   nrp = rp;
1272                   if (pkg == r->w1)
1273                     {
1274                       r->w1 = p;
1275                       r->n1 = watches[p];
1276                     }
1277                   else
1278                     {
1279                       r->w2 = p;
1280                       r->n2 = watches[p];
1281                     }
1282                   watches[p] = r - solv->rules;
1283                   continue;
1284                 }
1285             }
1286           /* unit clause found, set other watch to TRUE */
1287           if (DECISIONMAP_TRUE(-ow))
1288             return r;           /* eek, a conflict! */
1289 #if 0
1290           printf("unit ");
1291           printrule(solv, r);
1292 #endif
1293           if (ow > 0)
1294             decisionmap[ow] = level;
1295           else
1296             decisionmap[-ow] = -level;
1297           queuepush(&solv->decisionq, ow);
1298           queuepush(&solv->decisionq_why, r - solv->rules);
1299 #if 0
1300             {
1301               Solvable *s = pool->solvables + (ow > 0 ? ow : -ow);
1302               if (ow > 0)
1303                 printf("  -> decided to install %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
1304               else
1305                 printf("  -> decided to conflict %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
1306             }
1307 #endif
1308         }
1309     }
1310   return 0;     /* all is well */
1311 }
1312
1313
1314 /*-----------------------------------------------------------------*/
1315 /* Analysis */
1316
1317 /*
1318  * analyze
1319  *   and learn
1320  */
1321
1322 static int
1323 analyze(Solver *solv, int level, Rule *c, int *pr, int *dr, int *why)
1324 {
1325   Pool *pool = solv->pool;
1326   Queue r;
1327   int rlevel = 1;
1328   Map seen;             /* global? */
1329   Id v, vv, *dp;
1330   int l, i, idx;
1331   int num = 0;
1332   int learnt_why = solv->learnt_pool.count;
1333   Id *decisionmap = solv->decisionmap;
1334
1335   queueinit(&r);
1336
1337   if (pool->verbose) printf("ANALYZE at %d ----------------------\n", level);
1338   mapinit(&seen, pool->nsolvables);
1339   idx = solv->decisionq.count;
1340   for (;;)
1341     {
1342       printrule(solv, c);
1343       queuepush(&solv->learnt_pool, c - solv->rules);
1344       dp = c->d ? pool->whatprovidesdata + c->d : 0;
1345       for (i = -1; ; i++)
1346         {
1347           if (i == -1)
1348             v = c->p;
1349           else if (c->d == 0)
1350             v = i ? 0 : c->w2;
1351           else
1352             v = *dp++;
1353           if (v == 0)
1354             break;
1355           if (DECISIONMAP_TRUE(v))      /* the one true literal */
1356               continue;
1357           vv = v > 0 ? v : -v;
1358           if (MAPTST(&seen, vv))
1359             continue;
1360           l = solv->decisionmap[vv];
1361           if (l < 0)
1362             l = -l;
1363           if (l == 1)
1364             {
1365 #if 0
1366               int j;
1367               for (j = 0; j < solv->decisionq.count; j++)
1368                 if (solv->decisionq.elements[j] == v)
1369                   break;
1370               if (j == solv->decisionq.count)
1371                 abort();
1372               queuepush(&rulq, -(j + 1));
1373 #endif
1374               continue;                 /* initial setting */
1375             }
1376           MAPSET(&seen, vv);
1377           if (l == level)
1378             num++;                      /* need to do this one as well */
1379           else
1380             {
1381               queuepush(&r, v);
1382 #if 0
1383   printf("PUSH %d ", v);
1384   printruleelement(solv, 0, v);
1385 #endif
1386               if (l > rlevel)
1387                 rlevel = l;
1388             }
1389         }
1390 #if 0
1391       printf("num = %d\n", num);
1392 #endif
1393       if (num <= 0)
1394         abort();
1395       for (;;)
1396         {
1397           v = solv->decisionq.elements[--idx];
1398           vv = v > 0 ? v : -v;
1399           if (MAPTST(&seen, vv))
1400             break;
1401         }
1402       c = solv->rules + solv->decisionq_why.elements[idx];
1403       MAPCLR(&seen, vv);
1404       if (--num == 0)
1405         break;
1406     }
1407   *pr = -v;
1408   if (r.count == 0)
1409     *dr = 0;
1410   else if (r.count == 1 && r.elements[0] < 0)
1411     *dr = r.elements[0];
1412   else
1413     *dr = pool_queuetowhatprovides(pool, &r);
1414   if (pool->verbose)
1415     {
1416       printf("learned rule for level %d (am %d)\n", rlevel, level);
1417       printruleelement(solv, 0, -v);
1418       for (i = 0; i < r.count; i++)
1419         {
1420           v = r.elements[i];
1421           printruleelement(solv, 0, v);
1422         }
1423     }
1424   mapfree(&seen);
1425   queuepush(&solv->learnt_pool, 0);
1426 #if 0
1427   for (i = learnt_why; solv->learnt_pool.elements[i]; i++)
1428     {
1429       printf("learnt_why ");
1430       printrule(solv, solv->rules + solv->learnt_pool.elements[i]);
1431     }
1432 #endif
1433   if (why)
1434     *why = learnt_why;
1435   return rlevel;
1436 }
1437
1438
1439 /*
1440  * reset_solver
1441  * reset the solver decisions to right after the rpm rules
1442  */
1443
1444 static void
1445 reset_solver(Solver *solv)
1446 {
1447   int i;
1448   Id v;
1449
1450   /* delete all learnt rules */
1451   solv->nrules = solv->learntrules;
1452   QUEUEEMPTY(&solv->learnt_why);
1453   QUEUEEMPTY(&solv->learnt_pool);
1454
1455   /* redo all direct rpm rule decisions */
1456   /* we break at the first decision with a why attached, this is
1457    * either a job/system rule decision of a propagated decision */
1458   for (i = 0; i < solv->decisionq.count; i++)
1459     {
1460       v = solv->decisionq.elements[i];
1461       solv->decisionmap[v > 0 ? v : -v] = 0;
1462     }
1463   for (i = 0; i < solv->decisionq_why.count; i++)
1464     if (solv->decisionq_why.elements[i])
1465       break;
1466     else
1467       {
1468         v = solv->decisionq.elements[i];
1469         solv->decisionmap[v > 0 ? v : -v] = v > 0 ? 1 : -1;
1470       }
1471
1472   if (solv->pool->verbose)
1473     printf("decisions done reduced from %d to %d\n", solv->decisionq.count, i);
1474
1475   solv->decisionq_why.count = i;
1476   solv->decisionq.count = i;
1477   solv->recommends_index = -1;
1478   solv->propagate_index = 0;
1479
1480   /* redo all job/system decisions */
1481   makeruledecisions(solv);
1482   if (solv->pool->verbose)
1483     printf("decisions after adding job and system rules: %d\n", solv->decisionq.count);
1484   /* recreate watches */
1485   makewatches(solv);
1486 }
1487
1488
1489 /*
1490  * analyze_unsolvable_rule
1491  */
1492
1493 static void
1494 analyze_unsolvable_rule(Solver *solv, Rule *r)
1495 {
1496   int i;
1497   Id why = r - solv->rules;
1498 #if 0
1499   if (why >= solv->jobrules && why < solv->systemrules)
1500     printf("JOB ");
1501   if (why >= solv->systemrules && why < solv->weakrules)
1502     printf("SYSTEM %d ", why - solv->systemrules);
1503   if (why >= solv->weakrules && why < solv->learntrules)
1504     printf("WEAK ");
1505   if (solv->learntrules && why >= solv->learntrules)
1506     printf("LEARNED ");
1507   printrule(solv, r);
1508 #endif
1509   if (solv->learntrules && why >= solv->learntrules)
1510     {
1511       for (i = solv->learnt_why.elements[why - solv->learntrules]; solv->learnt_pool.elements[i]; i++)
1512         analyze_unsolvable_rule(solv, solv->rules + solv->learnt_pool.elements[i]);
1513       return;
1514     }
1515   /* do not add rpm rules to problem */
1516   if (why < solv->jobrules)
1517     return;
1518   /* return if problem already countains the rule */
1519   if (solv->problems.count)
1520     {
1521       for (i = solv->problems.count - 1; i >= 0; i--)
1522         if (solv->problems.elements[i] == 0)
1523           break;
1524         else if (solv->problems.elements[i] == why)
1525           return;
1526     }
1527   queuepush(&solv->problems, why);
1528 }
1529
1530
1531 /*
1532  * analyze_unsolvable
1533  *
1534  * return: 1 - disabled some rules, try again
1535  *         0 - hopeless
1536  */
1537
1538 static int
1539 analyze_unsolvable(Solver *solv, Rule *r, int disablerules)
1540 {
1541   Pool *pool = solv->pool;
1542   Map seen;             /* global? */
1543   Id v, vv, *dp, why;
1544   int l, i, idx;
1545   Id *decisionmap = solv->decisionmap;
1546   int oldproblemcount;
1547   int lastweak;
1548
1549 #if 0
1550   printf("ANALYZE UNSOLVABLE ----------------------\n");
1551 #endif
1552   oldproblemcount = solv->problems.count;
1553   mapinit(&seen, pool->nsolvables);
1554   analyze_unsolvable_rule(solv, r);
1555   dp = r->d ? pool->whatprovidesdata + r->d : 0;
1556   for (i = -1; ; i++)
1557     {
1558       if (i == -1)
1559         v = r->p;
1560       else if (r->d == 0)
1561         v = i ? 0 : r->w2;
1562       else
1563         v = *dp++;
1564       if (v == 0)
1565         break;
1566       if (DECISIONMAP_TRUE(v))  /* the one true literal */
1567           continue;
1568       vv = v > 0 ? v : -v;
1569       l = solv->decisionmap[vv];
1570       if (l < 0)
1571         l = -l;
1572       MAPSET(&seen, vv);
1573     }
1574   idx = solv->decisionq.count;
1575   while (idx > 0)
1576     {
1577       v = solv->decisionq.elements[--idx];
1578       vv = v > 0 ? v : -v;
1579       if (!MAPTST(&seen, vv))
1580         continue;
1581       why = solv->decisionq_why.elements[idx];
1582       if (!why)
1583         {
1584 #if 0
1585           printf("RPM ");
1586           printruleelement(solv, 0, v);
1587 #endif
1588           continue;
1589         }
1590       r = solv->rules + why;
1591       analyze_unsolvable_rule(solv, r);
1592       dp = r->d ? pool->whatprovidesdata + r->d : 0;
1593       for (i = -1; ; i++)
1594         {
1595           if (i == -1)
1596             v = r->p;
1597           else if (r->d == 0)
1598             v = i ? 0 : r->w2;
1599           else
1600             v = *dp++;
1601           if (v == 0)
1602             break;
1603           if (DECISIONMAP_TRUE(v))      /* the one true literal */
1604               continue;
1605           vv = v > 0 ? v : -v;
1606           l = solv->decisionmap[vv];
1607           if (l < 0)
1608             l = -l;
1609           MAPSET(&seen, vv);
1610         }
1611     }
1612   mapfree(&seen);
1613   queuepush(&solv->problems, 0);        /* mark end of this problem */
1614
1615   lastweak = 0;
1616   if (solv->weakrules != solv->learntrules)
1617     {
1618       for (i = oldproblemcount; i < solv->problems.count - 1; i++)
1619         {
1620           why = solv->problems.elements[i];
1621           if (why < solv->weakrules || why >= solv->learntrules)
1622             continue;
1623           if (!lastweak || lastweak < why)
1624             lastweak = why;
1625         }
1626     }
1627   if (lastweak)
1628     {
1629       /* disable last weak rule */
1630       solv->problems.count = oldproblemcount;
1631       r = solv->rules + lastweak;
1632       printf("disabling weak ");
1633       printrule(solv, r);
1634       r->w1 = 0;
1635       reset_solver(solv);
1636       return 1;
1637     }
1638   else if (disablerules)
1639     {
1640       for (i = oldproblemcount; i < solv->problems.count - 1; i++)
1641         {
1642           r = solv->rules + solv->problems.elements[i];
1643           r->w1 = 0;
1644         }
1645       reset_solver(solv);
1646       return 1;
1647     }
1648   return 0;
1649 }
1650
1651
1652 /*-----------------------------------------------------------------*/
1653 /* Decision revert */
1654
1655 /*
1656  * revert
1657  * revert decision at level
1658  */
1659
1660 static void
1661 revert(Solver *solv, int level)
1662 {
1663   Id v, vv;
1664   while (solv->decisionq.count)
1665     {
1666       v = solv->decisionq.elements[solv->decisionq.count - 1];
1667       vv = v > 0 ? v : -v;
1668       if (solv->decisionmap[vv] <= level && solv->decisionmap[vv] >= -level)
1669         break;
1670 #if 0
1671       printf("reverting decision %d at %d\n", v, solv->decisionmap[vv]);
1672 #endif
1673       solv->decisionmap[vv] = 0;
1674       solv->decisionq.count--;
1675       solv->decisionq_why.count--;
1676       solv->propagate_index = solv->decisionq.count;
1677     }
1678   solv->recommends_index = -1;
1679 }
1680
1681
1682 /*
1683  * watch2onhighest - put watch2 on literal with highest level
1684  */
1685
1686 static void
1687 watch2onhighest(Solver *solv, Rule *r)
1688 {
1689   int l, wl = 0;
1690   Id v, *dp;
1691
1692   if (!r->d)
1693     return;     /* binary rule, both watches are set */
1694   dp = solv->pool->whatprovidesdata + r->d;
1695   while ((v = *dp++) != 0)
1696     {
1697       l = solv->decisionmap[v < 0 ? -v : v];
1698       if (l < 0)
1699         l = -l;
1700       if (l > wl)
1701         {
1702           r->w2 = dp[-1];
1703           wl = l;
1704         }
1705     }
1706 }
1707
1708
1709 /*
1710  * setpropagatelearn
1711  */
1712
1713 static int
1714 setpropagatelearn(Solver *solv, int level, Id decision, int disablerules)
1715 {
1716   Rule *r;
1717   Id p, d;
1718   int l, why;
1719
1720   if (decision)
1721     {
1722       level++;
1723       if (decision > 0)
1724         solv->decisionmap[decision] = level;
1725       else
1726         solv->decisionmap[-decision] = -level;
1727       queuepush(&solv->decisionq, decision);
1728       queuepush(&solv->decisionq_why, 0);
1729     }
1730   for (;;)
1731     {
1732       r = propagate(solv, level);
1733       if (!r)
1734         break;
1735       if (level == 1)
1736         return analyze_unsolvable(solv, r, disablerules);
1737       printf("conflict with rule #%d\n", (int)(r - solv->rules));
1738       l = analyze(solv, level, r, &p, &d, &why);
1739       if (l >= level || l <= 0)
1740         abort();
1741       printf("reverting decisions (level %d -> %d)\n", level, l);
1742       level = l;
1743       revert(solv, level);
1744       r = addrule(solv, p, d);       /* p requires d */
1745       if (!r)
1746         abort();
1747       if (solv->learnt_why.count != (r - solv->rules) - solv->learntrules)
1748         {
1749           printf("%d %d\n", solv->learnt_why.count, (int)(r - solv->rules) - solv->learntrules);
1750           abort();
1751         }
1752       queuepush(&solv->learnt_why, why);
1753       if (d)
1754         {
1755           /* at least 2 literals, needs watches */
1756           watch2onhighest(solv, r);
1757           addwatches(solv, r);
1758         }
1759       solv->decisionmap[p > 0 ? p : -p] = p > 0 ? level : -level;
1760       queuepush(&solv->decisionq, p);
1761       queuepush(&solv->decisionq_why, r - solv->rules);
1762       printf("decision: ");
1763       printruleelement(solv, 0, p);
1764       printf("new rule: ");
1765       printrule(solv, r);
1766     }
1767   return level;
1768 }
1769
1770 /*-----------------------------------------------------------------*/
1771 /* Main solver interface */
1772
1773
1774 /*
1775  * solver_create
1776  * create solver structure
1777  *
1778  * pool: all available solvables
1779  * system: installed Solvables
1780  *
1781  *
1782  * Upon solving, rules are created to flag the Solvables
1783  * of the 'system' Source as installed.
1784  */
1785
1786 Solver *
1787 solver_create(Pool *pool, Source *system)
1788 {
1789   Solver *solv;
1790   solv = (Solver *)xcalloc(1, sizeof(Solver));
1791   solv->pool = pool;
1792   solv->system = system;
1793   pool->verbose = 1;
1794
1795   queueinit(&solv->decisionq);
1796   queueinit(&solv->decisionq_why);
1797   queueinit(&solv->problems);
1798   queueinit(&solv->suggestions);
1799   queueinit(&solv->learnt_why);
1800   queueinit(&solv->learnt_pool);
1801
1802   mapinit(&solv->recommendsmap, pool->nsolvables);
1803   mapinit(&solv->suggestsmap, pool->nsolvables);
1804   solv->recommends_index = 0;
1805
1806   solv->decisionmap = (Id *)xcalloc(pool->nsolvables, sizeof(Id));
1807   solv->rules = (Rule *)xmalloc((solv->nrules + (RULES_BLOCK + 1)) * sizeof(Rule));
1808   memset(solv->rules, 0, sizeof(Rule));
1809   solv->nrules = 1;
1810
1811   return solv;
1812 }
1813
1814
1815 /*
1816  * solver_free
1817  */
1818
1819 void
1820 solver_free(Solver *solv)
1821 {
1822   queuefree(&solv->decisionq);
1823   queuefree(&solv->decisionq_why);
1824   queuefree(&solv->learnt_why);
1825   queuefree(&solv->learnt_pool);
1826   queuefree(&solv->problems);
1827   queuefree(&solv->suggestions);
1828
1829   mapfree(&solv->recommendsmap);
1830   mapfree(&solv->suggestsmap);
1831   xfree(solv->decisionmap);
1832   xfree(solv->rules);
1833   xfree(solv->watches);
1834   xfree(solv->weaksystemrules);
1835   xfree(solv->obsoletes);
1836   xfree(solv->obsoletes_data);
1837   xfree(solv);
1838 }
1839
1840
1841 /*-------------------------------------------------------*/
1842
1843 /*
1844  * run_solver
1845  *
1846  * all rules have been set up, not actually run the solver
1847  *
1848  */
1849
1850 static void
1851 run_solver(Solver *solv, int disablerules, int doweak)
1852 {
1853   Queue dq;
1854   int systemlevel;
1855   int level, olevel;
1856   Rule *r;
1857   int i, n;
1858   Solvable *s;
1859   Pool *pool = solv->pool;
1860   Id p, *dp;
1861
1862 #if 0
1863   printf("number of rules: %d\n", solv->nrules);
1864 {
1865   int i;
1866   for (i = 0; i < solv->nrules; i++)
1867     {
1868       printrule(solv, solv->rules + i);
1869     }
1870 }
1871 #endif
1872
1873   /* all new rules are learnt after this point */
1874   solv->learntrules = solv->nrules;
1875   /* crate watches lists */
1876   makewatches(solv);
1877
1878   if (pool->verbose) printf("initial decisions: %d\n", solv->decisionq.count);
1879
1880   /* start SAT algorithm */
1881   level = 1;
1882   systemlevel = level + 1;
1883   if (pool->verbose) printf("solving...\n");
1884
1885   queueinit(&dq);
1886   for (;;)
1887     {
1888       /*
1889        * propagate
1890        */
1891
1892       if (level == 1)
1893         {
1894           if (pool->verbose) printf("propagating (%d %d)...\n", solv->propagate_index, solv->decisionq.count);
1895           if ((r = propagate(solv, level)) != 0)
1896             {
1897               if (analyze_unsolvable(solv, r, disablerules))
1898                 continue;
1899               printf("UNSOLVABLE\n");
1900               queuefree(&dq);
1901               return;
1902             }
1903         }
1904
1905       /*
1906        * system packages
1907        */
1908
1909       if (level < systemlevel && solv->system->nsolvables)
1910         {
1911           if (!solv->updatesystem)
1912             {
1913               /* try to keep as many packages as possible */
1914               if (pool->verbose) printf("installing system packages\n");
1915               for (i = solv->system->start, n = 0; ; i++, n++)
1916                 {
1917                   if (n == solv->system->nsolvables)
1918                     break;
1919                   if (i == solv->system->start + solv->system->nsolvables)
1920                     i = solv->system->start;
1921                   s = pool->solvables + i;
1922                   if (solv->decisionmap[i] != 0)
1923                     continue;
1924 #if 0
1925                   printf("system installing %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
1926 #endif
1927                   olevel = level;
1928                   level = setpropagatelearn(solv, level, i, disablerules);
1929                   if (level == 0)
1930                     {
1931                       printf("UNSOLVABLE\n");
1932                       queuefree(&dq);
1933                       return;
1934                     }
1935                   if (level <= olevel)
1936                     n = 0;
1937                 }
1938             }
1939           if (solv->weaksystemrules)
1940             {
1941               if (pool->verbose) printf("installing weak system packages\n");
1942               for (i = solv->system->start, n = 0; ; i++, n++)
1943                 {
1944                   if (n == solv->system->nsolvables)
1945                     break;
1946                   if (solv->decisionmap[i] > 0 || (solv->decisionmap[i] < 0 && solv->weaksystemrules[i - solv->system->start] == 0))
1947                     continue;
1948                   QUEUEEMPTY(&dq);
1949                   if (solv->decisionmap[i] == 0)
1950                     queuepush(&dq, i);
1951                   if (solv->weaksystemrules[i - solv->system->start])
1952                     {
1953                       dp = pool->whatprovidesdata + solv->weaksystemrules[i - solv->system->start];
1954                       while ((p = *dp++) != 0)
1955                         {
1956                           if (solv->decisionmap[p] > 0)
1957                             break;
1958                           if (solv->decisionmap[p] == 0)
1959                             queuepush(&dq, p);
1960                         }
1961                       if (p)
1962                         continue;       /* rule is already true */
1963                     }
1964                   if (!dq.count)
1965                     continue;
1966
1967                   if (dq.count > 1)
1968                     prune_to_recommended(solv, &dq);
1969                   if (dq.count > 1)
1970                     prune_best_version_arch(pool, &dq);
1971 #if 0
1972                   s = pool->solvables + dq.elements[0];
1973                   printf("weak system installing %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
1974 #endif
1975                   olevel = level;
1976                   level = setpropagatelearn(solv, level, dq.elements[0], disablerules);
1977                   if (level == 0)
1978                     {
1979                       printf("UNSOLVABLE\n");
1980                       queuefree(&dq);
1981                       return;
1982                     }
1983                   if (level <= olevel)
1984                     {
1985                       n = 0;
1986                       break;
1987                     }
1988                 }
1989               if (n != solv->system->nsolvables)
1990                 continue;
1991             }
1992           systemlevel = level;
1993         }
1994
1995       /*
1996        * decide
1997        */
1998
1999       if (pool->verbose) printf("deciding unresolved rules\n");
2000       for (i = 1, n = 1; ; i++, n++)
2001         {
2002           if (n == solv->nrules)
2003             break;
2004           if (i == solv->nrules)
2005             i = 1;
2006           r = solv->rules + i;
2007           if (!r->w1)
2008             continue;
2009           QUEUEEMPTY(&dq);
2010           if (r->d == 0)
2011             {
2012               /* binary or unary rule */
2013               /* need two positive undecided literals */
2014               if (r->p < 0 || r->w2 <= 0)
2015                 continue;
2016               if (solv->decisionmap[r->p] || solv->decisionmap[r->w2])
2017                 continue;
2018               queuepush(&dq, r->p);
2019               queuepush(&dq, r->w2);
2020             }
2021           else
2022             {
2023               /* make sure that
2024                * all negative literals are installed
2025                * no positive literal is installed
2026                * i.e. the rule is not fulfilled and we
2027                * just need to decide on the positive literals
2028                */
2029               if (r->p < 0)
2030                 {
2031                   if (solv->decisionmap[-r->p] <= 0)
2032                     continue;
2033                 }
2034               else
2035                 {
2036                   if (solv->decisionmap[r->p] > 0)
2037                     continue;
2038                   if (solv->decisionmap[r->p] == 0)
2039                     queuepush(&dq, r->p);
2040                 }
2041               dp = pool->whatprovidesdata + r->d;
2042               while ((p = *dp++) != 0)
2043                 {
2044                   if (p < 0)
2045                     {
2046                       if (solv->decisionmap[-p] <= 0)
2047                         break;
2048                     }
2049                   else
2050                     {
2051                       if (solv->decisionmap[p] > 0)
2052                         break;
2053                       if (solv->decisionmap[p] == 0)
2054                         queuepush(&dq, p);
2055                     }
2056                 }
2057               if (p)
2058                 continue;
2059             }
2060           if (dq.count < 2)
2061             {
2062               /* cannot happen as this means that
2063                * the rule is unit */
2064               printrule(solv, r);
2065               abort();
2066             }
2067           prune_to_recommended(solv, &dq);
2068           if (dq.count > 1)
2069             prune_best_version_arch(pool, &dq);
2070           p = dq.elements[dq.count - 1];
2071           s = pool->solvables + p;
2072 #if 0
2073           printf("installing %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2074 #endif
2075           olevel = level;
2076           level = setpropagatelearn(solv, level, p, disablerules);
2077           if (level == 0)
2078             {
2079               printf("UNSOLVABLE\n");
2080               queuefree(&dq);
2081               return;
2082             }
2083           if (level < systemlevel)
2084             break;
2085           n = 0;
2086         } /* for(), decide */
2087
2088       if (n != solv->nrules)    /* continue if level < systemlevel */
2089         continue;
2090
2091       if (doweak && !solv->problems.count)
2092         {
2093           int qcount;
2094
2095           if (pool->verbose) printf("installing recommended packages\n");
2096           QUEUEEMPTY(&dq);
2097           for (i = 1; i < pool->nsolvables; i++)
2098             {
2099               if (solv->decisionmap[i] < 0)
2100                 continue;
2101               if (solv->decisionmap[i] > 0)
2102                 {
2103                   Id *recp, rec, *pp, p;
2104                   s = pool->solvables + i;
2105                   /* installed, check for recommends */
2106                   /* XXX need to special case AND ? */
2107                   if ((recp = s->recommends) != 0)
2108                     {
2109                       while ((rec = *recp++) != 0)
2110                         {
2111                           qcount = dq.count;
2112                           FOR_PROVIDES(p, pp, rec)
2113                             {
2114                               if (solv->decisionmap[p] > 0)
2115                                 {
2116                                   dq.count = qcount;
2117                                   break;
2118                                 }
2119                               else if (solv->decisionmap[p] == 0)
2120                                 queuepushunique(&dq, p);
2121                             }
2122                         }
2123                     }
2124                 }
2125               else
2126                 {
2127                   Id *supp, sup;
2128                   s = pool->solvables + i;
2129                   if (!s->supplements && !s->freshens)
2130                     continue;
2131                   if (!pool_installable(pool, s))
2132                     continue;
2133                   if ((supp = s->supplements) != 0)
2134                     {
2135                       while ((sup = *supp++) != 0)
2136                         if (dep_fulfilled(solv, sup))
2137                           break;
2138                       if (!sup)
2139                         continue;
2140                     }
2141                   if ((supp = s->freshens) != 0)
2142                     {
2143                       while ((sup = *supp++) != 0)
2144                         if (dep_fulfilled(solv, sup))
2145                           break;
2146                       if (!sup)
2147                         continue;
2148                     }
2149                   queuepushunique(&dq, i);
2150                 }
2151             }
2152           if (dq.count)
2153             {
2154               prune_best_version_arch(pool, &dq);
2155               p = dq.elements[dq.count - 1];
2156               s = pool->solvables + p;
2157 #if 1
2158               printf("installing recommended %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2159 #endif
2160               level = setpropagatelearn(solv, level, p, 0);
2161               continue;
2162             }
2163         }
2164       break;
2165     }
2166   queuefree(&dq);
2167 }
2168
2169
2170 /*
2171  * refine_suggestion
2172  */
2173
2174 static void
2175 refine_suggestion(Solver *solv, Id *problem, Id sug, Queue *refined)
2176 {
2177   Rule *r;
2178   int i, j, sugseen;
2179   Id v, sugassert;
2180   Queue disabled;
2181   int disabledcnt;
2182
2183   printf("refine_suggestion start\n");
2184   queueinit(&disabled);
2185   QUEUEEMPTY(refined);
2186   queuepush(refined, sug);
2187
2188   /* re-enable all rules but rule "sug" of the problem */
2189   revert(solv, 1);
2190   reset_solver(solv);
2191
2192   sugassert = 0;
2193   sugseen = 0;
2194   r = solv->rules + sug;
2195   if (r->w2 == 0)
2196     sugassert = r->p;
2197
2198   for (i = 0; problem[i]; i++)
2199     {
2200       if (problem[i] == sug)
2201         {
2202           continue;
2203           sugseen = 1;
2204         }
2205       r = solv->rules + problem[i];
2206 #if 0
2207       printf("enable ");
2208       printrule(solv, r);
2209 #endif
2210       if (r->w2 == 0)
2211         {
2212           /* direct assertion */
2213           if (r->p == sugassert && sugseen)
2214             {
2215               /* also leave this assertion disabled */
2216               continue;
2217             }
2218           v = r->p > 0 ? r->p : -r->p;
2219           if (solv->decisionmap[v])
2220             {
2221               if ((solv->decisionmap[v] > 0 && r->p < 0) ||
2222                   (solv->decisionmap[v] < 0 && r->p > 0))
2223                 {
2224                   printf("direct assertion failure, no solution found!\n");
2225                   while (--i >= 0)
2226                     {
2227                       r = solv->rules + problem[i];
2228                       r->w1 = 0;
2229                     }
2230                   return;
2231                 }
2232             }
2233         }
2234       if (r->d == 0 || r->w2 != r->p)
2235         r->w1 = r->p;
2236       else
2237         r->w1 = solv->pool->whatprovidesdata[r->d];
2238     }
2239   for (;;)
2240     {
2241       /* re-enable as many weak rules as possible */
2242       for (i = solv->weakrules; i < solv->learntrules; i++)
2243         {
2244           r = solv->rules + i;
2245           if (r->w1)
2246             continue;
2247           if (r->d == 0 || r->w2 != r->p)
2248             r->w1 = r->p;
2249           else
2250             r->w1 = solv->pool->whatprovidesdata[r->d];
2251         }
2252
2253       QUEUEEMPTY(&solv->problems);
2254       revert(solv, 1);          /* XXX move to reset_solver? */
2255       reset_solver(solv);
2256       run_solver(solv, 0, 0);
2257       if (!solv->problems.count)
2258         {
2259           printf("no more problems!\n");
2260 #if 0
2261           printdecisions(solv);
2262 #endif
2263           break;                /* great, no more problems */
2264         }
2265       disabledcnt = disabled.count;
2266       for (i = 0; i < solv->problems.elements[i]; i++)
2267         {
2268           /* ignore solutions in refined */
2269           v = solv->problems.elements[i];
2270           for (j = 0; problem[j]; j++)
2271             if (problem[j] != sug && problem[j] == v)
2272               break;
2273           if (problem[j])
2274             continue;
2275           queuepush(&disabled, v);
2276           queuepush(&disabled, 0);      /* room for watch */
2277         }
2278       if (disabled.count == disabledcnt)
2279         {
2280           /* no solution found, this was an invalid suggestion! */
2281           printf("no solution found!\n");
2282           refined->count = 0;
2283           break;
2284         }
2285       if (disabled.count == disabledcnt + 2)
2286         {
2287           /* just one suggestion, add it to refined list */
2288           queuepush(refined, disabled.elements[disabledcnt]);
2289         }
2290       else
2291         {
2292           printf("##############################################   more than one solution found.\n");
2293 #if 1
2294           for (i = 0; i < solv->problems.elements[i]; i++)
2295             printrule(solv, solv->rules + solv->problems.elements[i]);
2296           printf("##############################################\n");
2297 #endif
2298           /* more than one solution, keep all disabled */
2299         }
2300       for (i = disabledcnt; i < disabled.count; i += 2)
2301         {
2302           /* disable em */
2303           r = solv->rules + disabled.elements[i];
2304           disabled.elements[i + 1] = r->w1;
2305           r->w1 = 0;
2306 #if 0
2307           printf("disable ");
2308           printrule(solv, r);
2309 #endif
2310         }
2311     }
2312   /* enable refined rules again */
2313   for (i = 0; i < disabled.count; i += 2)
2314     {
2315       r = solv->rules + disabled.elements[i];
2316       r->w1 = disabled.elements[i + 1];
2317     }
2318   /* disable problem rules again so that we are in the same state as before */
2319   for (i = 0; problem[i]; i++)
2320     {
2321       r = solv->rules + problem[i];
2322       r->w1 = 0;
2323     }
2324   printf("refine_suggestion end\n");
2325 }
2326
2327
2328 /*
2329  * printdecisions
2330  */
2331
2332 static const char *
2333 id2rc(Solver *solv, Id id)
2334 {
2335   const char *evr;
2336   if (solv->rc_output != 2)
2337     return "";
2338   evr = id2str(solv->pool, id);
2339   if (*evr < '0' || *evr > '9')
2340     return "0:";
2341   while (*evr >= '0' && *evr <= '9')
2342     evr++;
2343   if (*evr != ':')
2344     return "0:";
2345   return "";
2346 }
2347
2348 void
2349 printdecisions(Solver *solv)
2350 {
2351   Pool *pool = solv->pool;
2352   Id p, *obsoletesmap;
2353   int i;
2354   Solvable *s;
2355
2356   obsoletesmap = (Id *)xcalloc(pool->nsolvables, sizeof(Id));
2357   for (i = 0; i < solv->decisionq.count; i++)
2358     {
2359       Id obs, *obsp;
2360       Id *pp, n;
2361
2362       n = solv->decisionq.elements[i];
2363       if (n < 0)
2364         continue;
2365       if (n >= solv->system->start && n < solv->system->start + solv->system->nsolvables)
2366         continue;
2367       s = pool->solvables + n;
2368       if ((obsp = s->obsoletes) != 0)
2369         while ((obs = *obsp++) != 0)
2370           FOR_PROVIDES(p, pp, obs)
2371             {
2372               if (p >= solv->system->start && p < solv->system->start + solv->system->nsolvables)
2373                 {
2374                   obsoletesmap[p] = n;
2375                   obsoletesmap[n]++;
2376                 }
2377             }
2378       FOR_PROVIDES(p, pp, s->name)
2379         if (s->name == pool->solvables[p].name)
2380           {
2381             if (p >= solv->system->start && p < solv->system->start + solv->system->nsolvables)
2382               {
2383                 obsoletesmap[p] = n;
2384                 obsoletesmap[n]++;
2385               }
2386           }
2387     }
2388
2389   if (solv->rc_output)
2390     printf(">!> Solution #1:\n");
2391
2392   int installs = 0, uninstalls = 0, upgrades = 0;
2393
2394   /* print solvables to be erased */
2395
2396   for (i = solv->system->start; i < solv->system->start + solv->system->nsolvables; i++)
2397     {
2398       if (solv->decisionmap[i] > 0)
2399         continue;
2400       if (obsoletesmap[i])
2401         continue;
2402       s = pool->solvables + i;
2403       if (solv->rc_output == 2)
2404         printf(">!> remove  %s-%s%s\n", id2str(pool, s->name), id2rc(solv, s->evr), id2str(pool, s->evr));
2405       else if (solv->rc_output)
2406         printf(">!> remove  %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2407       else
2408         printf("erase   %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2409       uninstalls++;
2410     }
2411
2412   /* print solvables to be installed */
2413
2414   for (i = 0; i < solv->decisionq.count; i++)
2415     {
2416       int j;
2417       p = solv->decisionq.elements[i];
2418       if (p < 0)
2419         continue;
2420       if (p >= solv->system->start && p < solv->system->start + solv->system->nsolvables)
2421         continue;
2422       s = pool->solvables + p;
2423
2424       if (!obsoletesmap[p])
2425         {
2426           if (solv->rc_output)
2427             printf(">!> ");
2428           printf("install %s-%s%s", id2str(pool, s->name), id2rc(solv, s->evr), id2str(pool, s->evr));
2429           if (solv->rc_output != 2)
2430             printf(".%s", id2str(pool, s->arch));
2431           installs++;
2432         }
2433       else if (!solv->rc_output)
2434         {
2435           printf("update  %s-%s.%s  (obsoletes", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2436           for (j = solv->system->start; j < solv->system->start + solv->system->nsolvables; j++)
2437             {
2438               if (obsoletesmap[j] != p)
2439                 continue;
2440               s = pool->solvables + j;
2441               printf(" %s-%s.%s", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2442             }
2443           printf(")");
2444           upgrades++;
2445         }
2446       else
2447         {
2448           Solvable *f, *fn = 0;
2449           for (j = solv->system->start; j < solv->system->start + solv->system->nsolvables; j++)
2450             {
2451               if (obsoletesmap[j] != p)
2452                 continue;
2453               f = pool->solvables + j;
2454               if (fn || f->name != s->name)
2455                 {
2456                   if (solv->rc_output == 2)
2457                     printf(">!> remove  %s-%s%s\n", id2str(pool, f->name), id2rc(solv, f->evr), id2str(pool, f->evr));
2458                   else if (solv->rc_output)
2459                     printf(">!> remove  %s-%s.%s\n", id2str(pool, f->name), id2str(pool, f->evr), id2str(pool, f->arch));
2460                   uninstalls++;
2461                 }
2462               else
2463                 fn = f;
2464             }
2465           if (!fn)
2466             {
2467               printf(">!> install %s-%s%s", id2str(pool, s->name), id2rc(solv, s->evr), id2str(pool, s->evr));
2468               if (solv->rc_output != 2)
2469                 printf(".%s", id2str(pool, s->arch));
2470               installs++;
2471             }
2472           else
2473             {
2474               if (solv->rc_output == 2)
2475                 printf(">!> upgrade %s-%s => %s-%s%s", id2str(pool, fn->name), id2str(pool, fn->evr), id2str(pool, s->name), id2rc(solv, s->evr), id2str(pool, s->evr));
2476               else
2477                 printf(">!> upgrade %s-%s.%s => %s-%s.%s", id2str(pool, fn->name), id2str(pool, fn->evr), id2str(pool, fn->arch), id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2478               upgrades++;
2479             }
2480         }
2481       if (solv->rc_output)
2482         {
2483           Source *source = s->source;
2484           if (source && strcmp(source_name(source), "locales"))
2485             printf("[%s]", source_name(source));
2486         }
2487       printf("\n");
2488     }
2489
2490   if (solv->rc_output)
2491     printf(">!> installs=%d, upgrades=%d, uninstalls=%d\n", installs, upgrades, uninstalls);
2492
2493   xfree(obsoletesmap);
2494 }
2495
2496 static void
2497 create_obsolete_index(Solver *solv)
2498 {
2499   Pool *pool = solv->pool;
2500   Solvable *s;
2501   Source *system = solv->system;
2502   Id p, *pp, obs, *obsp, *obsoletes, *obsoletes_data;
2503   int i, n;
2504
2505   /* create reverse obsoletes map for system solvables */
2506   solv->obsoletes = obsoletes = xcalloc(system->nsolvables, sizeof(Id));
2507   for (i = 1; i < pool->nsolvables; i++)
2508     {
2509       s = pool->solvables + i;
2510       if ((obsp = s->obsoletes) == 0)
2511         continue;
2512       if (!pool_installable(pool, s))
2513         continue;
2514       while ((obs = *obsp++) != 0)
2515         FOR_PROVIDES(p, pp, obs)
2516           {
2517             if (p < system->start || p >= system->start + system->nsolvables)
2518               continue;
2519             if (pool->solvables[p].name == s->name)
2520               continue;
2521             obsoletes[p - system->start]++;
2522           }
2523     }
2524   n = 0;
2525   for (i = 0; i < system->nsolvables; i++)
2526     if (obsoletes[i])
2527       {
2528         n += obsoletes[i] + 1;
2529         obsoletes[i] = n;
2530       }
2531   solv->obsoletes_data = obsoletes_data = xcalloc(n + 1, sizeof(Id));
2532   if (pool->verbose) printf("obsoletes data: %d entries\n", n + 1);
2533   for (i = pool->nsolvables - 1; i > 0; i--)
2534     {
2535       s = pool->solvables + i;
2536       if ((obsp = s->obsoletes) == 0)
2537         continue;
2538       if (!pool_installable(pool, s))
2539         continue;
2540       while ((obs = *obsp++) != 0)
2541         FOR_PROVIDES(p, pp, obs)
2542           {
2543             if (p < system->start || p >= system->start + system->nsolvables)
2544               continue;
2545             if (pool->solvables[p].name == s->name)
2546               continue;
2547             p -= system->start;
2548             if (obsoletes_data[obsoletes[p]] != i)
2549               obsoletes_data[--obsoletes[p]] = i;
2550           }
2551     }
2552 }
2553
2554 /*-----------------------------------------------------------------*/
2555 /* main() */
2556
2557 /*
2558  *
2559  * solve job queue
2560  *
2561  */
2562
2563 void
2564 solve(Solver *solv, Queue *job)
2565 {
2566   Pool *pool = solv->pool;
2567   int i;
2568   Map addedmap;                        /* '1' == have rule for solvable */
2569   Map noupdaterule;                    /* '1' == don't update (scheduled for removal) */
2570   Id how, what, p, *pp, d;
2571   Queue q;
2572   Rule *r;
2573   Solvable *s;
2574
2575   /*
2576    * create basic rule set of all involved packages
2577    * as bitmaps
2578    *
2579    */
2580
2581   mapinit(&addedmap, pool->nsolvables);
2582   mapinit(&noupdaterule, pool->nsolvables);
2583
2584   queueinit(&q);
2585
2586   /*
2587    * create rules for installed solvables -> keep them installed
2588    * so called: rpm rules
2589    *
2590    */
2591
2592   for (i = solv->system->start; i < solv->system->start + solv->system->nsolvables; i++)
2593     addrulesforsolvable(solv, pool->solvables + i, &addedmap);
2594
2595   /*
2596    * create install rules
2597    *
2598    * two passes, as we want to keep the rpm rules distinct from the job rules
2599    *
2600    */
2601
2602   if (solv->noupdateprovide && solv->system->nsolvables)
2603     create_obsolete_index(solv);
2604
2605   /*
2606    * solvable rules
2607    *  process job rules for solvables
2608    */
2609
2610   for (i = 0; i < job->count; i += 2)
2611     {
2612       how = job->elements[i];
2613       what = job->elements[i + 1];
2614
2615       switch(how)
2616         {
2617         case SOLVER_INSTALL_SOLVABLE:
2618           addrulesforsolvable(solv, pool->solvables + what, &addedmap);
2619           break;
2620         case SOLVER_INSTALL_SOLVABLE_NAME:
2621         case SOLVER_INSTALL_SOLVABLE_PROVIDES:
2622           QUEUEEMPTY(&q);
2623           FOR_PROVIDES(p, pp, what)
2624             {
2625                                        /* if by name, ensure that the name matches */
2626               if (how == SOLVER_INSTALL_SOLVABLE_NAME && pool->solvables[p].name != what)
2627                 continue;
2628               addrulesforsolvable(solv, pool->solvables + p, &addedmap);
2629             }
2630           break;
2631         case SOLVER_INSTALL_SOLVABLE_UPDATE:
2632           /* dont allow downgrade */
2633           addupdaterule(solv, pool->solvables + what, &addedmap, 0, 0, 1);
2634           break;
2635         }
2636     }
2637
2638   /*
2639    * if unstalls are disallowed, add update rules for every
2640    * installed solvables in the hope to circumvent uninstall
2641    * by upgrading
2642    *
2643    */
2644
2645 #if 0
2646   if (!solv->allowuninstall)
2647     {
2648       /* add update rule for every installed package */
2649       for (i = solv->system->start; i < solv->system->start + solv->system->nsolvables; i++)
2650         addupdaterule(solv, pool->solvables + i, &addedmap, solv->allowdowngrade, solv->allowarchchange, 1);
2651     }
2652 #else  /* this is just to add the needed rpm rules to our set */
2653   for (i = solv->system->start; i < solv->system->start + solv->system->nsolvables; i++)
2654     addupdaterule(solv, pool->solvables + i, &addedmap, 1, 1, 1);
2655 #endif
2656
2657   addrulesforsupplements(solv, &addedmap);
2658   addrulesforenhances(solv, &addedmap);         /* do this last */
2659 #if 1
2660   if (pool->verbose)
2661     {
2662       int possible = 0, installable = 0;
2663       for (i = 1; i < pool->nsolvables; i++)
2664         {
2665           if (pool_installable(pool, pool->solvables + i))
2666             installable++;
2667           if (MAPTST(&addedmap, i))
2668             possible++;
2669         }
2670       printf("%d of %d installable solvables used for solving\n", possible, installable);
2671     }
2672 #endif
2673
2674   /*
2675    * first pass done
2676    *
2677    * unify existing rules before going over all job rules
2678    *
2679    */
2680
2681   unifyrules(solv);     /* remove duplicate rpm rules */
2682
2683   /*
2684    * at this point the system is always solvable,
2685    * as an empty system (remove all packages) is a valid solution
2686    */
2687   if (pool->verbose) printf("decisions based on rpms: %d\n", solv->decisionq.count);
2688
2689   /*
2690    * now add all job rules
2691    */
2692
2693   solv->jobrules = solv->nrules;
2694
2695   for (i = 0; i < job->count; i += 2)
2696     {
2697       how = job->elements[i];
2698       what = job->elements[i + 1];
2699       switch(how)
2700         {
2701         case SOLVER_INSTALL_SOLVABLE:                     /* install specific solvable */
2702           if (solv->rc_output) {
2703             Solvable *s = pool->solvables + what;
2704             printf(">!> Installing %s from channel %s\n", id2str(pool, s->name), source_name(s->source));
2705           }
2706           addrule(solv, what, 0);                         /* install by Id */
2707           break;
2708         case SOLVER_ERASE_SOLVABLE:
2709           addrule(solv, -what, 0);                        /* remove by Id */
2710           MAPSET(&noupdaterule, what);
2711           break;
2712         case SOLVER_INSTALL_SOLVABLE_NAME:                /* install by capability */
2713         case SOLVER_INSTALL_SOLVABLE_PROVIDES:
2714           QUEUEEMPTY(&q);
2715           FOR_PROVIDES(p, pp, what)    /* check all providers */
2716             {
2717                                        /* if by name, ensure that the name matches */
2718               if (how == SOLVER_INSTALL_SOLVABLE_NAME && pool->solvables[p].name != what)
2719                 continue;
2720               queuepush(&q, p);
2721             }
2722           if (!q.count) {              /* no provider found -> abort */
2723             fprintf(stderr, "Nothing provides '%s'\n", id2str(pool, what));
2724             /* XXX make this a problem! */
2725             return;
2726             abort();
2727           }
2728
2729           p = queueshift(&q);          /* get first provider */
2730           if (!q.count)
2731             d = 0;                     /* single provider ? -> make assertion */
2732           else
2733             d = pool_queuetowhatprovides(pool, &q);   /* get all providers */
2734           addrule(solv, p, d);         /* add 'requires' rule */
2735           break;
2736         case SOLVER_ERASE_SOLVABLE_NAME:                  /* remove by capability */
2737         case SOLVER_ERASE_SOLVABLE_PROVIDES:
2738           FOR_PROVIDES(p, pp, what)
2739             {
2740                                        /* if by name, ensure that the name matches */
2741               if (how == SOLVER_ERASE_SOLVABLE_NAME && pool->solvables[p].name != what)
2742                 continue;
2743
2744               addrule(solv, -p, 0);  /* add 'remove' rule */
2745               MAPSET(&noupdaterule, p);
2746             }
2747           break;
2748         case SOLVER_INSTALL_SOLVABLE_UPDATE:              /* find update for solvable */
2749           addupdaterule(solv, pool->solvables + what, &addedmap, 0, 0, 0);
2750           break;
2751         }
2752     }
2753
2754   if (pool->verbose) printf("problems so far: %d\n", solv->problems.count);
2755
2756   /*
2757    * now add policy rules
2758    *
2759    */
2760
2761   solv->systemrules = solv->nrules;
2762
2763   /*
2764    * create rules for updating installed solvables
2765    *
2766    * (Again ?)
2767    *
2768    */
2769
2770   if (!solv->allowuninstall)
2771     {                                  /* loop over all installed solvables */
2772       for (i = solv->system->start; i < solv->system->start + solv->system->nsolvables; i++)
2773       {
2774         if (!MAPTST(&noupdaterule, i)) /* if not marked as 'noupdate' */
2775           addupdaterule(solv, pool->solvables + i, &addedmap, solv->allowdowngrade, solv->allowarchchange, 0);
2776         else
2777           addrule(solv, 0, 0);          /* place holder */
2778       }
2779       /* consistency check: we added a rule for _every_ system solvable */
2780       if (solv->nrules - solv->systemrules != solv->system->nsolvables)
2781         abort();
2782     }
2783
2784   if (pool->verbose) printf("problems so far: %d\n", solv->problems.count);
2785
2786   /* create special weak system rules */
2787   if (solv->system->nsolvables)
2788     {
2789       solv->weaksystemrules = xcalloc(solv->system->nsolvables, sizeof(Id));
2790       for (i = 0; i < solv->system->nsolvables; i++)
2791         {
2792           if (MAPTST(&noupdaterule, solv->system->start + i))
2793             continue;
2794           findupdatepackages(solv, pool->solvables + solv->system->start + i, &q, (Map *)0, 1, 1);
2795           if (q.count)
2796             solv->weaksystemrules[i] = pool_queuetowhatprovides(pool, &q);
2797         }
2798     }
2799
2800   /* free unneeded memory */
2801   mapfree(&addedmap);
2802   mapfree(&noupdaterule);
2803   queuefree(&q);
2804
2805   solv->weakrules = solv->nrules;
2806
2807   /* try real hard to keep packages installed */
2808   if (0)
2809     {
2810       for (i = 0; i < solv->system->nsolvables; i++)
2811         {
2812           d = solv->weaksystemrules[i];
2813           addrule(solv, solv->system->start + i, d);
2814         }
2815     }
2816
2817   /*
2818    * solve !
2819    *
2820    */
2821
2822   makeruledecisions(solv);
2823   run_solver(solv, 1, 1);
2824
2825   /* find suggested packages */
2826   if (!solv->problems.count)
2827     {
2828       Id sug, *sugp, enh, *enhp, req, *reqp, p, *pp;
2829
2830       /* create map of all suggests that are still open */
2831       solv->recommends_index = -1;
2832       MAPZERO(&solv->suggestsmap);
2833       for (i = 0; i < solv->decisionq.count; i++)
2834         {
2835           p = solv->decisionq.elements[i];
2836           if (p < 0)
2837             continue;
2838           s = pool->solvables + p;
2839           if ((sugp = s->suggests) != 0)
2840             while ((sug = *sugp++) != 0)
2841               {
2842                 FOR_PROVIDES(p, pp, sug)
2843                   if (solv->decisionmap[p] > 0)
2844                     break;
2845                 if (p)
2846                   continue;     /* already fulfilled */
2847                 FOR_PROVIDES(p, pp, sug)
2848                   MAPSET(&solv->suggestsmap, p);
2849               }
2850         }
2851       for (i = 1; i < pool->nsolvables; i++)
2852         {
2853           if (solv->decisionmap[i] != 0)
2854             continue;
2855           s = pool->solvables + i;
2856           if (!MAPTST(&solv->suggestsmap, i))
2857             {
2858               if ((enhp = s->enhances) == 0)
2859                 continue;
2860               if (!pool_installable(pool, s))
2861                 continue;
2862               while ((enh = *enhp++) != 0)
2863                 if (dep_fulfilled(solv, enh))
2864                   break;
2865               if (!enh)
2866                 continue;
2867             }
2868           /* check if installation is possible at all */
2869           if ((reqp = s->requires) != 0)
2870             {
2871               while ((req = *reqp++) != 0)
2872                 {
2873                   if (req == SOLVABLE_PREREQMARKER)   /* skip the marker */
2874                     continue;
2875                   FOR_PROVIDES(p, pp, req)
2876                     if (solv->decisionmap[p] >= 0)
2877                       break;
2878                   if (!p && !strncmp(id2str(pool, req), "rpmlib(", 7))
2879                     continue;
2880                   if (!p)
2881                     break;              /* no provider installable! */
2882                 }
2883               if (req)
2884                 continue;
2885             }
2886           queuepush(&solv->suggestions, i);
2887         }
2888       prune_best_version_arch(pool, &solv->suggestions);
2889     }
2890
2891   /*
2892    *
2893    * print solver result
2894    *
2895    */
2896
2897   if (pool->verbose) printf("-------------------------------------------------------------\n");
2898
2899   if (solv->problems.count)
2900     {
2901       Queue problems;
2902       Queue solution;
2903       Id *problem;
2904       Id why;
2905       int j;
2906
2907       if (!pool->verbose)
2908         return;
2909       clonequeue(&problems, &solv->problems);
2910       queueinit(&solution);
2911       printf("Encountered problems! Here are the solutions:\n");
2912       problem = problems.elements;
2913       for (i = 0; i < problems.count; i++)
2914         {
2915           Id v = problems.elements[i];
2916           if (v == 0)
2917             {
2918               printf("====================================\n");
2919               problem = problems.elements + i + 1;
2920               continue;
2921             }
2922           refine_suggestion(solv, problem, v, &solution);
2923           for (j = 0; j < solution.count; j++)
2924             {
2925               r = solv->rules + solution.elements[j];
2926               why = solution.elements[j];
2927 #if 0
2928               printrule(solv, r);
2929 #endif
2930               if (why >= solv->jobrules && why < solv->systemrules)
2931                 {
2932                   /* do a sloppy job of analyzing the job rule */
2933                   if (r->p > 0)
2934                     {
2935                       s = pool->solvables + r->p;
2936                       printf("- do not install %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2937                     }
2938                   else
2939                     {
2940                       s = pool->solvables - r->p;
2941                       printf("- do not erase %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2942                     }
2943                 }
2944               else if (why >= solv->systemrules && why < solv->weakrules)
2945                 {
2946                   Solvable *sd = 0;
2947                   s = pool->solvables + solv->system->start + (why - solv->systemrules);
2948                   if (solv->weaksystemrules && solv->weaksystemrules[why - solv->systemrules])
2949                     {
2950                       Id *dp = pool->whatprovidesdata + solv->weaksystemrules[why - solv->systemrules];
2951                       for (; *dp; dp++)
2952                         {
2953                           if (*dp >= solv->system->start && *dp < solv->system->start + solv->system->nsolvables)
2954                             continue;
2955                           if (solv->decisionmap[*dp] > 0)
2956                             {
2957                               sd = pool->solvables + *dp;
2958                               break;
2959                             }
2960                         }
2961                     }
2962                   if (sd)
2963                     {
2964                       printf("- allow downgrade of %s-%s.%s to %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch), id2str(pool, sd->name), id2str(pool, sd->evr), id2str(pool, sd->arch));
2965                     }
2966                   else
2967                     {
2968                       printf("- allow deinstallation of %s-%s.%s [%ld]\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch), (long int)(s - pool->solvables));
2969                     }
2970                 }
2971               else
2972                 {
2973                   abort();
2974                 }
2975             }
2976           printf("------------------------------------\n");
2977         }
2978       return;
2979     }
2980
2981   printdecisions(solv);
2982   if (solv->suggestions.count)
2983     {
2984       printf("\nsuggested packages:\n");
2985       for (i = 0; i < solv->suggestions.count; i++)
2986         {
2987           s = pool->solvables + solv->suggestions.elements[i];
2988           printf("- %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2989         }
2990     }
2991 }
2992
2993
2994 // EOF