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