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   #if 0
 883               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);
 884               for (i = 0; dp[i]; i++)
 885                 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));
 886   #endif
 887               /* add 'requires' dependency */
 888               /* rule: (-requestor|provider1|provider2|...|providerN) */
 889               addrule(solv, -n, dp - pool->whatprovidesdata);
 890
 891               /* descend the dependency tree */
 892               for (; *dp; dp++)   /* loop through all providers */
 893                 {
 894                   if (!MAPTST(m, *dp))
 895                     queuepush(&q, *dp);
 896                 }
 897
 898             } /* while, requirements of n */
 899
 900         } /* if, requirements */
 901
 902
 903       /*-----------------------------------------
 904        * check conflicts of s
 905        */
 906
 907       if (s->conflicts)
 908         {
 909           conp = s->source->idarraydata + s->conflicts;
 910           while ((con = *conp++) != 0)
 911             {
 912               FOR_PROVIDES(p, pp, con)
 913                 {
 914                    /* dontfix: dont care about conflicts with already installed packs */
 915                   if (dontfix && p >= system->start && p < system->start + system->nsolvables)
 916                     continue;
 917                  /* rule: -n|-p: either solvable _or_ provider of conflict */
 918                   addrule(solv, -n, -p);
 919                 }
 920             }
 921         }
 922
 923       /*-----------------------------------------
 924        * check obsoletes if not installed
 925        */
 926       if (!system || n < system->start || n >= (system->start + system->nsolvables))
 927         {                              /* not installed */
 928           if (s->obsoletes)
 929             {
 930               obsp = s->source->idarraydata + s->obsoletes;
 931               while ((obs = *obsp++) != 0)
 932                 {
 933                   FOR_PROVIDES(p, pp, obs)
 934                     addrule(solv, -n, -p);
 935                 }
 936             }
 937           FOR_PROVIDES(p, pp, s->name)
 938             {
 939               if (s->name == pool->solvables[p].name)
 940                 addrule(solv, -n, -p);
 941             }
 942         }
 943
 944       /*-----------------------------------------
 945        * add recommends to the rule list
 946        */
 947       if (s->recommends)
 948         {
 949           recp = s->source->idarraydata + s->recommends;
 950           while ((rec = *recp++) != 0)
 951             {
 952               FOR_PROVIDES(p, pp, rec)
 953                 if (!MAPTST(m, p))
 954                   queuepush(&q, p);
 955             }
 956         }
 957       if (s->suggests)
 958         {
 959           sugp = s->source->idarraydata + s->suggests;
 960           while ((sug = *sugp++) != 0)
 961             {
 962               FOR_PROVIDES(p, pp, sug)
 963                 if (!MAPTST(m, p))
 964                   queuepush(&q, p);
 965             }
 966         }
 967     }
 968   queuefree(&q);
 969 }
 970
 971 static void
 972 addrulesforweak(Solver *solv, Map *m)
 973 {
 974   Pool *pool = solv->pool;
 975   Solvable *s;
 976   Id sup, *supp;
 977   int i, n;
 978
 979   if (pool->verbose) printf("addrulesforweak... (%d)\n", solv->nrules);
 980   for (i = n = 1; n < pool->nsolvables; i++, n++)
 981     {
 982       if (i == pool->nsolvables)
 983         i = 1;
 984       if (MAPTST(m, i))
 985         continue;
 986       s = pool->solvables + i;
 987       if (!pool_installable(pool, s))
 988         continue;
 989       sup = 0;
 990       if (s->supplements)
 991         {
 992           supp = s->source->idarraydata + s->supplements;
 993           while ((sup = *supp++) != ID_NULL)
 994             if (dep_possible(solv, sup, m))
 995               break;
 996         }
 997       if (!sup && s->freshens)
 998         {
 999           supp = s->source->idarraydata + s->freshens;
1000           while ((sup = *supp++) != ID_NULL)
1001             if (dep_possible(solv, sup, m))
1002               break;
1003         }
1004       if (!sup && s->enhances)
1005         {
1006           supp = s->source->idarraydata + s->enhances;
1007           while ((sup = *supp++) != ID_NULL)
1008             if (dep_possible(solv, sup, m))
1009               break;
1010         }
1011       if (!sup)
1012         continue;
1013       addrulesforsolvable(solv, s, m);
1014       n = 0;
1015     }
1016   if (pool->verbose) printf("done. (%d)\n", solv->nrules);
1017 }
1018
1019 static inline int
1020 archchanges(Pool *pool, Solvable *s1, Solvable *s2)
1021 {
1022   Id a1 = s1->arch, a2 = s2->arch;
1023
1024   /* we allow changes to/from noarch */
1025   if (a1 == a2 || a1 == ARCH_NOARCH || a2 == ARCH_NOARCH)
1026     return 0;
1027   if (!pool->id2arch)
1028     return 0;
1029   a1 = a1 <= pool->lastarch ? pool->id2arch[a1] : 0;
1030   a2 = a2 <= pool->lastarch ? pool->id2arch[a2] : 0;
1031   if (((a1 ^ a2) & 0xffff0000) != 0)
1032     return 1;
1033   return 0;
1034 }
1035
1036
1037 static void
1038 findupdatepackages(Solver *solv, Solvable *s, Queue *qs, Map *m, int allowdowngrade, int allowarchchange)
1039 {
1040   /* system packages get a special upgrade allowed rule */
1041   Pool *pool = solv->pool;
1042   Id p, *pp, n, p2, *pp2;
1043   Id obs, *obsp;
1044   Solvable *ps;
1045
1046   QUEUEEMPTY(qs);
1047   /*
1048    * s = solvable ptr
1049    * n = solvable Id
1050    */
1051   n = s - pool->solvables;
1052   if (m && !MAPTST(m, n))       /* add rule for s if not already done */
1053     addrulesforsolvable(solv, s, m);
1054
1055   /*
1056    * look for updates for s
1057    */
1058   FOR_PROVIDES(p, pp, s->name)  /* every provider of s' name */
1059     {
1060       if (p == n)               /* skip itself */
1061         continue;
1062
1063       ps = pool->solvables + p;
1064       if (s->name == ps->name)  /* name match */
1065         {
1066           if (!allowdowngrade                   /* consider downgrades ? */
1067               && evrcmp(pool, s->evr, ps->evr) > 0)
1068             continue;
1069           /* XXX */
1070           if (!allowarchchange && archchanges(pool, s, ps))
1071             continue;
1072         }
1073       else if (!solv->noupdateprovide && ps->obsoletes)   /* provides/obsoletes combination ? */
1074         {
1075           obsp = ps->source->idarraydata + ps->obsoletes;
1076           while ((obs = *obsp++) != 0)  /* for all obsoletes */
1077             {
1078               FOR_PROVIDES(p2, pp2, obs)   /* and all matching providers of the obsoletes */
1079                 {
1080                   if (p2 == n)          /* match ! */
1081                     break;
1082                 }
1083               if (p2)                   /* match! */
1084                 break;
1085             }
1086           if (!obs)                     /* continue if no match */
1087             continue;
1088           /* here we have 'p' with a matching provides/obsoletes combination
1089            * thus flagging p as a valid update candidate for s
1090            */
1091         }
1092       else
1093         continue;
1094       queuepush(qs, p);
1095
1096       if (m && !MAPTST(m, p))           /* mark p for install if not already done */
1097         addrulesforsolvable(solv, pool->solvables + p, m);
1098     }
1099   if (solv->noupdateprovide && solv->obsoletes && solv->obsoletes[n - solv->system->start])
1100     {
1101       for (pp = solv->obsoletes_data + solv->obsoletes[n - solv->system->start]; (p = *pp++) != 0;)
1102         {
1103           queuepush(qs, p);
1104           if (m && !MAPTST(m, p))               /* mark p for install if not already done */
1105             addrulesforsolvable(solv, pool->solvables + p, m);
1106         }
1107     }
1108 }
1109
1110 /*
1111  * add rule for update
1112  *   (A|A1|A2|A3...)  An = update candidates for A
1113  *
1114  * s = (installed) solvable
1115  * m = 'addedmap', bit set if 'install' rule for solvable exists
1116  */
1117
1118 static void
1119 addupdaterule(Solver *solv, Solvable *s, Map *m, int allowdowngrade, int allowarchchange, int dontaddrule)
1120 {
1121   /* system packages get a special upgrade allowed rule */
1122   Pool *pool = solv->pool;
1123   Id p, d;
1124   Rule *r;
1125   Queue qs;
1126   Id qsbuf[64];
1127
1128   queueinit_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
1129   findupdatepackages(solv, s, &qs, m, allowdowngrade, allowarchchange);
1130   p = s - pool->solvables;
1131   if (dontaddrule)      /* we consider update candidates but dont force them */
1132     {
1133       queuefree(&qs);
1134       return;
1135     }
1136
1137   if (qs.count == 0)                   /* no updates found */
1138     {
1139 #if 0
1140       printf("new update rule: must keep %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
1141 #endif
1142       addrule(solv, p, 0);              /* request 'install' of s */
1143       queuefree(&qs);
1144       return;
1145     }
1146
1147   d = pool_queuetowhatprovides(pool, &qs);   /* intern computed provider queue */
1148   queuefree(&qs);
1149   r = addrule(solv, p, d);             /* allow update of s */
1150 #if 0
1151   printf("new update rule ");
1152   if (r)
1153     printrule(solv, r);
1154 #endif
1155 }
1156
1157
1158 /*-----------------------------------------------------------------*/
1159 /* watches */
1160
1161
1162 /*
1163  * makewatches
1164  *
1165  * initial setup for all watches
1166  */
1167
1168 static void
1169 makewatches(Solver *solv)
1170 {
1171   Rule *r;
1172   int i;
1173   int nsolvables = solv->pool->nsolvables;
1174
1175   xfree(solv->watches);
1176                                        /* lower half for removals, upper half for installs */
1177   solv->watches = (Id *)xcalloc(2 * nsolvables, sizeof(Id));
1178 #if 1
1179   /* do it reverse so rpm rules get triggered first */
1180   for (i = 1, r = solv->rules + solv->nrules - 1; i < solv->nrules; i++, r--)
1181 #else
1182   for (i = 1, r = solv->rules + 1; i < solv->nrules; i++, r++)
1183 #endif
1184     {
1185       if (!r->w1                       /* rule is disabled */
1186           || !r->w2)                   /* rule is assertion */
1187         continue;
1188
1189       /* see addwatches(solv, r) */
1190       r->n1 = solv->watches[nsolvables + r->w1];
1191       solv->watches[nsolvables + r->w1] = r - solv->rules;
1192
1193       r->n2 = solv->watches[nsolvables + r->w2];
1194       solv->watches[nsolvables + r->w2] = r - solv->rules;
1195     }
1196 }
1197
1198
1199 /*
1200  * add watches (for rule)
1201  */
1202
1203 static void
1204 addwatches(Solver *solv, Rule *r)
1205 {
1206   int nsolvables = solv->pool->nsolvables;
1207
1208   r->n1 = solv->watches[nsolvables + r->w1];
1209   solv->watches[nsolvables + r->w1] = r - solv->rules;
1210
1211   r->n2 = solv->watches[nsolvables + r->w2];
1212   solv->watches[nsolvables + r->w2] = r - solv->rules;
1213 }
1214
1215
1216 /*-----------------------------------------------------------------*/
1217 /* rule propagation */
1218
1219 #define DECISIONMAP_TRUE(p) ((p) > 0 ? (decisionmap[p] > 0) : (decisionmap[-p] < 0))
1220
1221 /*
1222  * propagate
1223  *
1224  * propagate decision to all rules
1225  */
1226
1227 static Rule *
1228 propagate(Solver *solv, int level)
1229 {
1230   Pool *pool = solv->pool;
1231   Id *rp, *nrp;
1232   Rule *r;
1233   Id p, pkg, ow;
1234   Id *dp;
1235   Id *decisionmap = solv->decisionmap;
1236   Id *watches = solv->watches + pool->nsolvables;
1237
1238   while (solv->propagate_index < solv->decisionq.count)
1239     {
1240       /* negative because our watches trigger if literal goes FALSE */
1241       pkg = -solv->decisionq.elements[solv->propagate_index++];
1242 #if 0
1243   printf("popagate for decision %d level %d\n", -pkg, level);
1244   printruleelement(solv, 0, -pkg);
1245 #endif
1246       for (rp = watches + pkg; *rp; rp = nrp)
1247         {
1248           r = solv->rules + *rp;
1249 #if 0
1250   printf("  watch triggered ");
1251   printrule(solv, r);
1252 #endif
1253           if (pkg == r->w1)
1254             {
1255               ow = r->w2;
1256               nrp = &r->n1;
1257             }
1258           else
1259             {
1260               ow = r->w1;
1261               nrp = &r->n2;
1262             }
1263           /* if clause is TRUE, nothing to do */
1264           if (DECISIONMAP_TRUE(ow))
1265             continue;
1266
1267           if (r->d)
1268             {
1269               /* not a binary clause, check if we need to move our watch */
1270               if (r->p && r->p != ow && !DECISIONMAP_TRUE(-r->p))
1271                 p = r->p;
1272               else
1273                 for (dp = pool->whatprovidesdata + r->d; (p = *dp++) != 0;)
1274                   if (p != ow && !DECISIONMAP_TRUE(-p))
1275                     break;
1276               if (p)
1277                 {
1278                   /* p is free to watch, move watch to p */
1279 #if 0
1280                   if (p > 0)
1281                     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));
1282                   else
1283                     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));
1284 #endif
1285                   *rp = *nrp;
1286                   nrp = rp;
1287                   if (pkg == r->w1)
1288                     {
1289                       r->w1 = p;
1290                       r->n1 = watches[p];
1291                     }
1292                   else
1293                     {
1294                       r->w2 = p;
1295                       r->n2 = watches[p];
1296                     }
1297                   watches[p] = r - solv->rules;
1298                   continue;
1299                 }
1300             }
1301           /* unit clause found, set other watch to TRUE */
1302           if (DECISIONMAP_TRUE(-ow))
1303             return r;           /* eek, a conflict! */
1304 #if 0
1305           printf("unit ");
1306           printrule(solv, r);
1307 #endif
1308           if (ow > 0)
1309             decisionmap[ow] = level;
1310           else
1311             decisionmap[-ow] = -level;
1312           queuepush(&solv->decisionq, ow);
1313           queuepush(&solv->decisionq_why, r - solv->rules);
1314 #if 0
1315             {
1316               Solvable *s = pool->solvables + (ow > 0 ? ow : -ow);
1317               if (ow > 0)
1318                 printf("  -> decided to install %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
1319               else
1320                 printf("  -> decided to conflict %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
1321             }
1322 #endif
1323         }
1324     }
1325   return 0;     /* all is well */
1326 }
1327
1328
1329 /*-----------------------------------------------------------------*/
1330 /* Analysis */
1331
1332 /*
1333  * analyze
1334  *   and learn
1335  */
1336
1337 static int
1338 analyze(Solver *solv, int level, Rule *c, int *pr, int *dr, int *why)
1339 {
1340   Pool *pool = solv->pool;
1341   Queue r;
1342   int rlevel = 1;
1343   Map seen;             /* global? */
1344   Id v, vv, *dp;
1345   int l, i, idx;
1346   int num = 0;
1347   int learnt_why = solv->learnt_pool.count;
1348   Id *decisionmap = solv->decisionmap;
1349
1350   queueinit(&r);
1351
1352   if (pool->verbose) printf("ANALYZE at %d ----------------------\n", level);
1353   mapinit(&seen, pool->nsolvables);
1354   idx = solv->decisionq.count;
1355   for (;;)
1356     {
1357       printrule(solv, c);
1358       queuepush(&solv->learnt_pool, c - solv->rules);
1359       dp = c->d ? pool->whatprovidesdata + c->d : 0;
1360       for (i = -1; ; i++)
1361         {
1362           if (i == -1)
1363             v = c->p;
1364           else if (c->d == 0)
1365             v = i ? 0 : c->w2;
1366           else
1367             v = *dp++;
1368           if (v == 0)
1369             break;
1370           if (DECISIONMAP_TRUE(v))      /* the one true literal */
1371               continue;
1372           vv = v > 0 ? v : -v;
1373           if (MAPTST(&seen, vv))
1374             continue;
1375           l = solv->decisionmap[vv];
1376           if (l < 0)
1377             l = -l;
1378           if (l == 1)
1379             {
1380 #if 0
1381               int j;
1382               for (j = 0; j < solv->decisionq.count; j++)
1383                 if (solv->decisionq.elements[j] == v)
1384                   break;
1385               if (j == solv->decisionq.count)
1386                 abort();
1387               queuepush(&rulq, -(j + 1));
1388 #endif
1389               continue;                 /* initial setting */
1390             }
1391           MAPSET(&seen, vv);
1392           if (l == level)
1393             num++;                      /* need to do this one as well */
1394           else
1395             {
1396               queuepush(&r, v);
1397 #if 0
1398   printf("PUSH %d ", v);
1399   printruleelement(solv, 0, v);
1400 #endif
1401               if (l > rlevel)
1402                 rlevel = l;
1403             }
1404         }
1405 #if 0
1406       printf("num = %d\n", num);
1407 #endif
1408       if (num <= 0)
1409         abort();
1410       for (;;)
1411         {
1412           v = solv->decisionq.elements[--idx];
1413           vv = v > 0 ? v : -v;
1414           if (MAPTST(&seen, vv))
1415             break;
1416         }
1417       c = solv->rules + solv->decisionq_why.elements[idx];
1418       MAPCLR(&seen, vv);
1419       if (--num == 0)
1420         break;
1421     }
1422   *pr = -v;
1423   if (r.count == 0)
1424     *dr = 0;
1425   else if (r.count == 1 && r.elements[0] < 0)
1426     *dr = r.elements[0];
1427   else
1428     *dr = pool_queuetowhatprovides(pool, &r);
1429   if (pool->verbose)
1430     {
1431       printf("learned rule for level %d (am %d)\n", rlevel, level);
1432       printruleelement(solv, 0, -v);
1433       for (i = 0; i < r.count; i++)
1434         {
1435           v = r.elements[i];
1436           printruleelement(solv, 0, v);
1437         }
1438     }
1439   mapfree(&seen);
1440   queuepush(&solv->learnt_pool, 0);
1441 #if 0
1442   for (i = learnt_why; solv->learnt_pool.elements[i]; i++)
1443     {
1444       printf("learnt_why ");
1445       printrule(solv, solv->rules + solv->learnt_pool.elements[i]);
1446     }
1447 #endif
1448   if (why)
1449     *why = learnt_why;
1450   return rlevel;
1451 }
1452
1453
1454 /*
1455  * reset_solver
1456  * reset the solver decisions to right after the rpm rules
1457  */
1458
1459 static void
1460 reset_solver(Solver *solv)
1461 {
1462   int i;
1463   Id v;
1464
1465   /* delete all learnt rules */
1466   solv->nrules = solv->learntrules;
1467   QUEUEEMPTY(&solv->learnt_why);
1468   QUEUEEMPTY(&solv->learnt_pool);
1469
1470   /* redo all direct rpm rule decisions */
1471   /* we break at the first decision with a why attached, this is
1472    * either a job/system rule decision of a propagated decision */
1473   for (i = 0; i < solv->decisionq.count; i++)
1474     {
1475       v = solv->decisionq.elements[i];
1476       solv->decisionmap[v > 0 ? v : -v] = 0;
1477     }
1478   for (i = 0; i < solv->decisionq_why.count; i++)
1479     if (solv->decisionq_why.elements[i])
1480       break;
1481     else
1482       {
1483         v = solv->decisionq.elements[i];
1484         solv->decisionmap[v > 0 ? v : -v] = v > 0 ? 1 : -1;
1485       }
1486
1487   if (solv->pool->verbose)
1488     printf("decisions done reduced from %d to %d\n", solv->decisionq.count, i);
1489
1490   solv->decisionq_why.count = i;
1491   solv->decisionq.count = i;
1492   solv->recommends_index = -1;
1493   solv->propagate_index = 0;
1494
1495   /* redo all job/system decisions */
1496   makeruledecisions(solv);
1497   if (solv->pool->verbose)
1498     printf("decisions after adding job and system rules: %d\n", solv->decisionq.count);
1499   /* recreate watches */
1500   makewatches(solv);
1501 }
1502
1503
1504 /*
1505  * analyze_unsolvable_rule
1506  */
1507
1508 static void
1509 analyze_unsolvable_rule(Solver *solv, Rule *r)
1510 {
1511   int i;
1512   Id why = r - solv->rules;
1513 #if 0
1514   if (why >= solv->jobrules && why < solv->systemrules)
1515     printf("JOB ");
1516   if (why >= solv->systemrules && why < solv->weakrules)
1517     printf("SYSTEM %d ", why - solv->systemrules);
1518   if (why >= solv->weakrules && why < solv->learntrules)
1519     printf("WEAK ");
1520   if (solv->learntrules && why >= solv->learntrules)
1521     printf("LEARNED ");
1522   printrule(solv, r);
1523 #endif
1524   if (solv->learntrules && why >= solv->learntrules)
1525     {
1526       for (i = solv->learnt_why.elements[why - solv->learntrules]; solv->learnt_pool.elements[i]; i++)
1527         analyze_unsolvable_rule(solv, solv->rules + solv->learnt_pool.elements[i]);
1528       return;
1529     }
1530   /* do not add rpm rules to problem */
1531   if (why < solv->jobrules)
1532     return;
1533   /* return if problem already countains the rule */
1534   if (solv->problems.count)
1535     {
1536       for (i = solv->problems.count - 1; i >= 0; i--)
1537         if (solv->problems.elements[i] == 0)
1538           break;
1539         else if (solv->problems.elements[i] == why)
1540           return;
1541     }
1542   queuepush(&solv->problems, why);
1543 }
1544
1545
1546 /*
1547  * analyze_unsolvable
1548  *
1549  * return: 1 - disabled some rules, try again
1550  *         0 - hopeless
1551  */
1552
1553 static int
1554 analyze_unsolvable(Solver *solv, Rule *r, int disablerules)
1555 {
1556   Pool *pool = solv->pool;
1557   Map seen;             /* global? */
1558   Id v, vv, *dp, why;
1559   int l, i, idx;
1560   Id *decisionmap = solv->decisionmap;
1561   int oldproblemcount;
1562   int lastweak;
1563
1564 #if 0
1565   printf("ANALYZE UNSOLVABLE ----------------------\n");
1566 #endif
1567   oldproblemcount = solv->problems.count;
1568   mapinit(&seen, pool->nsolvables);
1569   analyze_unsolvable_rule(solv, r);
1570   dp = r->d ? pool->whatprovidesdata + r->d : 0;
1571   for (i = -1; ; i++)
1572     {
1573       if (i == -1)
1574         v = r->p;
1575       else if (r->d == 0)
1576         v = i ? 0 : r->w2;
1577       else
1578         v = *dp++;
1579       if (v == 0)
1580         break;
1581       if (DECISIONMAP_TRUE(v))  /* the one true literal */
1582           continue;
1583       vv = v > 0 ? v : -v;
1584       l = solv->decisionmap[vv];
1585       if (l < 0)
1586         l = -l;
1587       MAPSET(&seen, vv);
1588     }
1589   idx = solv->decisionq.count;
1590   while (idx > 0)
1591     {
1592       v = solv->decisionq.elements[--idx];
1593       vv = v > 0 ? v : -v;
1594       if (!MAPTST(&seen, vv))
1595         continue;
1596       why = solv->decisionq_why.elements[idx];
1597       if (!why)
1598         {
1599 #if 0
1600           printf("RPM ");
1601           printruleelement(solv, 0, v);
1602 #endif
1603           continue;
1604         }
1605       r = solv->rules + why;
1606       analyze_unsolvable_rule(solv, r);
1607       dp = r->d ? pool->whatprovidesdata + r->d : 0;
1608       for (i = -1; ; i++)
1609         {
1610           if (i == -1)
1611             v = r->p;
1612           else if (r->d == 0)
1613             v = i ? 0 : r->w2;
1614           else
1615             v = *dp++;
1616           if (v == 0)
1617             break;
1618           if (DECISIONMAP_TRUE(v))      /* the one true literal */
1619               continue;
1620           vv = v > 0 ? v : -v;
1621           l = solv->decisionmap[vv];
1622           if (l < 0)
1623             l = -l;
1624           MAPSET(&seen, vv);
1625         }
1626     }
1627   mapfree(&seen);
1628   queuepush(&solv->problems, 0);        /* mark end of this problem */
1629
1630   lastweak = 0;
1631   if (solv->weakrules != solv->learntrules)
1632     {
1633       for (i = oldproblemcount; i < solv->problems.count - 1; i++)
1634         {
1635           why = solv->problems.elements[i];
1636           if (why < solv->weakrules || why >= solv->learntrules)
1637             continue;
1638           if (!lastweak || lastweak < why)
1639             lastweak = why;
1640         }
1641     }
1642   if (lastweak)
1643     {
1644       /* disable last weak rule */
1645       solv->problems.count = oldproblemcount;
1646       r = solv->rules + lastweak;
1647       printf("disabling weak ");
1648       printrule(solv, r);
1649       r->w1 = 0;
1650       reset_solver(solv);
1651       return 1;
1652     }
1653   else if (disablerules)
1654     {
1655       for (i = oldproblemcount; i < solv->problems.count - 1; i++)
1656         {
1657           r = solv->rules + solv->problems.elements[i];
1658           r->w1 = 0;
1659         }
1660       reset_solver(solv);
1661       return 1;
1662     }
1663   return 0;
1664 }
1665
1666
1667 /*-----------------------------------------------------------------*/
1668 /* Decision revert */
1669
1670 /*
1671  * revert
1672  * revert decision at level
1673  */
1674
1675 static void
1676 revert(Solver *solv, int level)
1677 {
1678   Id v, vv;
1679   while (solv->decisionq.count)
1680     {
1681       v = solv->decisionq.elements[solv->decisionq.count - 1];
1682       vv = v > 0 ? v : -v;
1683       if (solv->decisionmap[vv] <= level && solv->decisionmap[vv] >= -level)
1684         break;
1685 #if 0
1686       printf("reverting decision %d at %d\n", v, solv->decisionmap[vv]);
1687 #endif
1688       solv->decisionmap[vv] = 0;
1689       solv->decisionq.count--;
1690       solv->decisionq_why.count--;
1691       solv->propagate_index = solv->decisionq.count;
1692     }
1693   solv->recommends_index = -1;
1694 }
1695
1696
1697 /*
1698  * watch2onhighest - put watch2 on literal with highest level
1699  */
1700
1701 static void
1702 watch2onhighest(Solver *solv, Rule *r)
1703 {
1704   int l, wl = 0;
1705   Id v, *dp;
1706
1707   if (!r->d)
1708     return;     /* binary rule, both watches are set */
1709   dp = solv->pool->whatprovidesdata + r->d;
1710   while ((v = *dp++) != 0)
1711     {
1712       l = solv->decisionmap[v < 0 ? -v : v];
1713       if (l < 0)
1714         l = -l;
1715       if (l > wl)
1716         {
1717           r->w2 = dp[-1];
1718           wl = l;
1719         }
1720     }
1721 }
1722
1723
1724 /*
1725  * setpropagatelearn
1726  */
1727
1728 static int
1729 setpropagatelearn(Solver *solv, int level, Id decision, int disablerules)
1730 {
1731   Rule *r;
1732   Id p, d;
1733   int l, why;
1734
1735   if (decision)
1736     {
1737       level++;
1738       if (decision > 0)
1739         solv->decisionmap[decision] = level;
1740       else
1741         solv->decisionmap[-decision] = -level;
1742       queuepush(&solv->decisionq, decision);
1743       queuepush(&solv->decisionq_why, 0);
1744     }
1745   for (;;)
1746     {
1747       r = propagate(solv, level);
1748       if (!r)
1749         break;
1750       if (level == 1)
1751         return analyze_unsolvable(solv, r, disablerules);
1752       printf("conflict with rule #%d\n", (int)(r - solv->rules));
1753       l = analyze(solv, level, r, &p, &d, &why);
1754       if (l >= level || l <= 0)
1755         abort();
1756       printf("reverting decisions (level %d -> %d)\n", level, l);
1757       level = l;
1758       revert(solv, level);
1759       r = addrule(solv, p, d);       /* p requires d */
1760       if (!r)
1761         abort();
1762       if (solv->learnt_why.count != (r - solv->rules) - solv->learntrules)
1763         {
1764           printf("%d %d\n", solv->learnt_why.count, (int)(r - solv->rules) - solv->learntrules);
1765           abort();
1766         }
1767       queuepush(&solv->learnt_why, why);
1768       if (d)
1769         {
1770           /* at least 2 literals, needs watches */
1771           watch2onhighest(solv, r);
1772           addwatches(solv, r);
1773         }
1774       solv->decisionmap[p > 0 ? p : -p] = p > 0 ? level : -level;
1775       queuepush(&solv->decisionq, p);
1776       queuepush(&solv->decisionq_why, r - solv->rules);
1777       printf("decision: ");
1778       printruleelement(solv, 0, p);
1779       printf("new rule: ");
1780       printrule(solv, r);
1781     }
1782   return level;
1783 }
1784
1785 /*-----------------------------------------------------------------*/
1786 /* Main solver interface */
1787
1788
1789 /*
1790  * solver_create
1791  * create solver structure
1792  *
1793  * pool: all available solvables
1794  * system: installed Solvables
1795  *
1796  *
1797  * Upon solving, rules are created to flag the Solvables
1798  * of the 'system' Source as installed.
1799  */
1800
1801 Solver *
1802 solver_create(Pool *pool, Source *system)
1803 {
1804   Solver *solv;
1805   solv = (Solver *)xcalloc(1, sizeof(Solver));
1806   solv->pool = pool;
1807   solv->system = system;
1808   pool->verbose = 1;
1809
1810   queueinit(&solv->ruletojob);
1811   queueinit(&solv->decisionq);
1812   queueinit(&solv->decisionq_why);
1813   queueinit(&solv->problems);
1814   queueinit(&solv->suggestions);
1815   queueinit(&solv->learnt_why);
1816   queueinit(&solv->learnt_pool);
1817
1818   mapinit(&solv->recommendsmap, pool->nsolvables);
1819   mapinit(&solv->suggestsmap, pool->nsolvables);
1820   solv->recommends_index = 0;
1821
1822   solv->decisionmap = (Id *)xcalloc(pool->nsolvables, sizeof(Id));
1823   solv->rules = (Rule *)xmalloc((solv->nrules + (RULES_BLOCK + 1)) * sizeof(Rule));
1824   memset(solv->rules, 0, sizeof(Rule));
1825   solv->nrules = 1;
1826
1827   return solv;
1828 }
1829
1830
1831 /*
1832  * solver_free
1833  */
1834
1835 void
1836 solver_free(Solver *solv)
1837 {
1838   queuefree(&solv->ruletojob);
1839   queuefree(&solv->decisionq);
1840   queuefree(&solv->decisionq_why);
1841   queuefree(&solv->learnt_why);
1842   queuefree(&solv->learnt_pool);
1843   queuefree(&solv->problems);
1844   queuefree(&solv->suggestions);
1845
1846   mapfree(&solv->recommendsmap);
1847   mapfree(&solv->suggestsmap);
1848   xfree(solv->decisionmap);
1849   xfree(solv->rules);
1850   xfree(solv->watches);
1851   xfree(solv->weaksystemrules);
1852   xfree(solv->obsoletes);
1853   xfree(solv->obsoletes_data);
1854   xfree(solv);
1855 }
1856
1857
1858 /*-------------------------------------------------------*/
1859
1860 /*
1861  * run_solver
1862  *
1863  * all rules have been set up, not actually run the solver
1864  *
1865  */
1866
1867 static void
1868 run_solver(Solver *solv, int disablerules, int doweak)
1869 {
1870   Queue dq;
1871   int systemlevel;
1872   int level, olevel;
1873   Rule *r;
1874   int i, n;
1875   Solvable *s;
1876   Pool *pool = solv->pool;
1877   Id p, *dp;
1878
1879 #if 0
1880   printf("number of rules: %d\n", solv->nrules);
1881 {
1882   int i;
1883   for (i = 0; i < solv->nrules; i++)
1884     {
1885       printrule(solv, solv->rules + i);
1886     }
1887 }
1888 #endif
1889
1890   /* all new rules are learnt after this point */
1891   solv->learntrules = solv->nrules;
1892   /* crate watches lists */
1893   makewatches(solv);
1894
1895   if (pool->verbose) printf("initial decisions: %d\n", solv->decisionq.count);
1896
1897   /* start SAT algorithm */
1898   level = 1;
1899   systemlevel = level + 1;
1900   if (pool->verbose) printf("solving...\n");
1901
1902   queueinit(&dq);
1903   for (;;)
1904     {
1905       /*
1906        * propagate
1907        */
1908
1909       if (level == 1)
1910         {
1911           if (pool->verbose) printf("propagating (%d %d)...\n", solv->propagate_index, solv->decisionq.count);
1912           if ((r = propagate(solv, level)) != 0)
1913             {
1914               if (analyze_unsolvable(solv, r, disablerules))
1915                 continue;
1916               printf("UNSOLVABLE\n");
1917               queuefree(&dq);
1918               return;
1919             }
1920         }
1921
1922       /*
1923        * system packages
1924        */
1925
1926       if (level < systemlevel && solv->system->nsolvables)
1927         {
1928           if (!solv->updatesystem)
1929             {
1930               /* try to keep as many packages as possible */
1931               if (pool->verbose) printf("installing system packages\n");
1932               for (i = solv->system->start, n = 0; ; i++, n++)
1933                 {
1934                   if (n == solv->system->nsolvables)
1935                     break;
1936                   if (i == solv->system->start + solv->system->nsolvables)
1937                     i = solv->system->start;
1938                   s = pool->solvables + i;
1939                   if (solv->decisionmap[i] != 0)
1940                     continue;
1941 #if 0
1942                   printf("system installing %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
1943 #endif
1944                   olevel = level;
1945                   level = setpropagatelearn(solv, level, i, disablerules);
1946                   if (level == 0)
1947                     {
1948                       printf("UNSOLVABLE\n");
1949                       queuefree(&dq);
1950                       return;
1951                     }
1952                   if (level <= olevel)
1953                     n = 0;
1954                 }
1955             }
1956           if (solv->weaksystemrules)
1957             {
1958               if (pool->verbose) printf("installing weak system packages\n");
1959               for (i = solv->system->start, n = 0; ; i++, n++)
1960                 {
1961                   if (n == solv->system->nsolvables)
1962                     break;
1963                   if (solv->decisionmap[i] > 0 || (solv->decisionmap[i] < 0 && solv->weaksystemrules[i - solv->system->start] == 0))
1964                     continue;
1965                   QUEUEEMPTY(&dq);
1966                   if (solv->decisionmap[i] == 0)
1967                     queuepush(&dq, i);
1968                   if (solv->weaksystemrules[i - solv->system->start])
1969                     {
1970                       dp = pool->whatprovidesdata + solv->weaksystemrules[i - solv->system->start];
1971                       while ((p = *dp++) != 0)
1972                         {
1973                           if (solv->decisionmap[p] > 0)
1974                             break;
1975                           if (solv->decisionmap[p] == 0)
1976                             queuepush(&dq, p);
1977                         }
1978                       if (p)
1979                         continue;       /* rule is already true */
1980                     }
1981                   if (!dq.count)
1982                     continue;
1983
1984                   if (dq.count > 1)
1985                     prune_to_highest_prio(pool, &dq);
1986                   if (dq.count > 1)
1987                     prune_to_recommended(solv, &dq);
1988                   if (dq.count > 1)
1989                     prune_best_version_arch(pool, &dq);
1990 #if 0
1991                   s = pool->solvables + dq.elements[0];
1992                   printf("weak system installing %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
1993 #endif
1994                   olevel = level;
1995                   level = setpropagatelearn(solv, level, dq.elements[0], disablerules);
1996                   if (level == 0)
1997                     {
1998                       printf("UNSOLVABLE\n");
1999                       queuefree(&dq);
2000                       return;
2001                     }
2002                   if (level <= olevel)
2003                     {
2004                       n = 0;
2005                       break;
2006                     }
2007                 }
2008               if (n != solv->system->nsolvables)
2009                 continue;
2010             }
2011           systemlevel = level;
2012         }
2013
2014       /*
2015        * decide
2016        */
2017
2018       if (pool->verbose) printf("deciding unresolved rules\n");
2019       for (i = 1, n = 1; ; i++, n++)
2020         {
2021           if (n == solv->nrules)
2022             break;
2023           if (i == solv->nrules)
2024             i = 1;
2025           r = solv->rules + i;
2026           if (!r->w1)
2027             continue;
2028           QUEUEEMPTY(&dq);
2029           if (r->d == 0)
2030             {
2031               /* binary or unary rule */
2032               /* need two positive undecided literals */
2033               if (r->p < 0 || r->w2 <= 0)
2034                 continue;
2035               if (solv->decisionmap[r->p] || solv->decisionmap[r->w2])
2036                 continue;
2037               queuepush(&dq, r->p);
2038               queuepush(&dq, r->w2);
2039             }
2040           else
2041             {
2042               /* make sure that
2043                * all negative literals are installed
2044                * no positive literal is installed
2045                * i.e. the rule is not fulfilled and we
2046                * just need to decide on the positive literals
2047                */
2048               if (r->p < 0)
2049                 {
2050                   if (solv->decisionmap[-r->p] <= 0)
2051                     continue;
2052                 }
2053               else
2054                 {
2055                   if (solv->decisionmap[r->p] > 0)
2056                     continue;
2057                   if (solv->decisionmap[r->p] == 0)
2058                     queuepush(&dq, r->p);
2059                 }
2060               dp = pool->whatprovidesdata + r->d;
2061               while ((p = *dp++) != 0)
2062                 {
2063                   if (p < 0)
2064                     {
2065                       if (solv->decisionmap[-p] <= 0)
2066                         break;
2067                     }
2068                   else
2069                     {
2070                       if (solv->decisionmap[p] > 0)
2071                         break;
2072                       if (solv->decisionmap[p] == 0)
2073                         queuepush(&dq, p);
2074                     }
2075                 }
2076               if (p)
2077                 continue;
2078             }
2079           if (dq.count < 2)
2080             {
2081               /* cannot happen as this means that
2082                * the rule is unit */
2083               printrule(solv, r);
2084               abort();
2085             }
2086           prune_to_highest_prio(pool, &dq);
2087           if (dq.count > 1)
2088             prune_to_recommended(solv, &dq);
2089           if (dq.count > 1)
2090             prune_best_version_arch(pool, &dq);
2091           p = dq.elements[dq.count - 1];
2092           s = pool->solvables + p;
2093 #if 0
2094           printf("installing %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2095 #endif
2096           olevel = level;
2097           level = setpropagatelearn(solv, level, p, disablerules);
2098           if (level == 0)
2099             {
2100               printf("UNSOLVABLE\n");
2101               queuefree(&dq);
2102               return;
2103             }
2104           if (level < systemlevel)
2105             break;
2106           n = 0;
2107         } /* for(), decide */
2108
2109       if (n != solv->nrules)    /* continue if level < systemlevel */
2110         continue;
2111
2112       if (doweak && !solv->problems.count)
2113         {
2114           int qcount;
2115
2116           if (pool->verbose) printf("installing recommended packages\n");
2117           QUEUEEMPTY(&dq);
2118           for (i = 1; i < pool->nsolvables; i++)
2119             {
2120               if (solv->decisionmap[i] < 0)
2121                 continue;
2122               if (solv->decisionmap[i] > 0)
2123                 {
2124                   Id *recp, rec, *pp, p;
2125                   s = pool->solvables + i;
2126                   /* installed, check for recommends */
2127                   /* XXX need to special case AND ? */
2128                   if (s->recommends)
2129                     {
2130                       recp = s->source->idarraydata + s->recommends;
2131                       while ((rec = *recp++) != 0)
2132                         {
2133                           qcount = dq.count;
2134                           FOR_PROVIDES(p, pp, rec)
2135                             {
2136                               if (solv->decisionmap[p] > 0)
2137                                 {
2138                                   dq.count = qcount;
2139                                   break;
2140                                 }
2141                               else if (solv->decisionmap[p] == 0)
2142                                 queuepushunique(&dq, p);
2143                             }
2144                         }
2145                     }
2146                 }
2147               else
2148                 {
2149                   Id *supp, sup;
2150                   s = pool->solvables + i;
2151                   if (!s->supplements && !s->freshens)
2152                     continue;
2153                   if (!pool_installable(pool, s))
2154                     continue;
2155                   if (s->supplements)
2156                     {
2157                       supp = s->source->idarraydata + s->supplements;
2158                       while ((sup = *supp++) != 0)
2159                         if (dep_fulfilled(solv, sup))
2160                           break;
2161                       if (!sup)
2162                         continue;
2163                     }
2164                   if (s->freshens)
2165                     {
2166                       supp = s->source->idarraydata + s->freshens;
2167                       while ((sup = *supp++) != 0)
2168                         if (dep_fulfilled(solv, sup))
2169                           break;
2170                       if (!sup)
2171                         continue;
2172                     }
2173                   queuepushunique(&dq, i);
2174                 }
2175             }
2176           if (dq.count)
2177             {
2178               if (dq.count > 1)
2179                 prune_to_highest_prio(pool, &dq);
2180               if (dq.count > 1)
2181                 prune_best_version_arch(pool, &dq);
2182               p = dq.elements[dq.count - 1];
2183               s = pool->solvables + p;
2184 #if 1
2185               printf("installing recommended %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2186 #endif
2187               level = setpropagatelearn(solv, level, p, 0);
2188               continue;
2189             }
2190         }
2191       break;
2192     }
2193   queuefree(&dq);
2194 }
2195
2196
2197 /*
2198  * refine_suggestion
2199  */
2200
2201 static void
2202 refine_suggestion(Solver *solv, Id *problem, Id sug, Queue *refined)
2203 {
2204   Rule *r;
2205   int i, j, sugseen, sugjob = -1;
2206   Id v, sugassert;
2207   Queue disabled;
2208   int disabledcnt;
2209
2210   printf("refine_suggestion start\n");
2211
2212   if (sug >= solv->jobrules && sug < solv->systemrules)
2213     sugjob = solv->ruletojob.elements[sug - solv->jobrules];
2214
2215   queueinit(&disabled);
2216   QUEUEEMPTY(refined);
2217   queuepush(refined, sug);
2218
2219   /* re-enable all rules but rule "sug" of the problem */
2220   revert(solv, 1);
2221   reset_solver(solv);
2222
2223   sugassert = 0;
2224   sugseen = 0;
2225   r = solv->rules + sug;
2226   if (r->w2 == 0)
2227     sugassert = r->p;
2228
2229   for (i = 0; problem[i]; i++)
2230     {
2231       if (problem[i] == sug)
2232         {
2233           continue;
2234           sugseen = 1;
2235         }
2236       if (sugjob >= 0 && problem[i] >= solv->jobrules && problem[i] < solv->systemrules && sugjob == solv->ruletojob.elements[problem[i] - solv->jobrules])
2237         {
2238           /* rule belongs to same job */
2239           continue;
2240         }
2241       r = solv->rules + problem[i];
2242 #if 0
2243       printf("enable ");
2244       printrule(solv, r);
2245 #endif
2246       if (r->w2 == 0)
2247         {
2248           /* direct assertion */
2249           if (r->p == sugassert && sugseen)
2250             {
2251               /* also leave this assertion disabled */
2252               continue;
2253             }
2254           v = r->p > 0 ? r->p : -r->p;
2255           if (solv->decisionmap[v])
2256             {
2257               if ((solv->decisionmap[v] > 0 && r->p < 0) ||
2258                   (solv->decisionmap[v] < 0 && r->p > 0))
2259                 {
2260                   printf("direct assertion failure, no solution found!\n");
2261                   while (--i >= 0)
2262                     {
2263                       r = solv->rules + problem[i];
2264                       r->w1 = 0;
2265                     }
2266                   return;
2267                 }
2268             }
2269         }
2270       if (r->d == 0 || r->w2 != r->p)
2271         r->w1 = r->p;
2272       else
2273         r->w1 = solv->pool->whatprovidesdata[r->d];
2274     }
2275   for (;;)
2276     {
2277       /* re-enable as many weak rules as possible */
2278       for (i = solv->weakrules; i < solv->learntrules; i++)
2279         {
2280           r = solv->rules + i;
2281           if (r->w1)
2282             continue;
2283           if (r->d == 0 || r->w2 != r->p)
2284             r->w1 = r->p;
2285           else
2286             r->w1 = solv->pool->whatprovidesdata[r->d];
2287         }
2288
2289       QUEUEEMPTY(&solv->problems);
2290       revert(solv, 1);          /* XXX move to reset_solver? */
2291       reset_solver(solv);
2292       run_solver(solv, 0, 0);
2293       if (!solv->problems.count)
2294         {
2295           printf("no more problems!\n");
2296 #if 0
2297           printdecisions(solv);
2298 #endif
2299           break;                /* great, no more problems */
2300         }
2301       disabledcnt = disabled.count;
2302       for (i = 0; i < solv->problems.elements[i]; i++)
2303         {
2304           /* ignore solutions in refined */
2305           v = solv->problems.elements[i];
2306           for (j = 0; problem[j]; j++)
2307             if (problem[j] != sug && problem[j] == v)
2308               break;
2309           if (problem[j])
2310             continue;
2311           queuepush(&disabled, v);
2312           queuepush(&disabled, 0);      /* room for watch */
2313         }
2314       if (disabled.count == disabledcnt)
2315         {
2316           /* no solution found, this was an invalid suggestion! */
2317           printf("no solution found!\n");
2318           refined->count = 0;
2319           break;
2320         }
2321       if (disabled.count == disabledcnt + 2)
2322         {
2323           /* just one suggestion, add it to refined list */
2324           queuepush(refined, disabled.elements[disabledcnt]);
2325         }
2326       else
2327         {
2328           printf("##############################################   more than one solution found.\n");
2329 #if 1
2330           for (i = 0; i < solv->problems.elements[i]; i++)
2331             printrule(solv, solv->rules + solv->problems.elements[i]);
2332           printf("##############################################\n");
2333 #endif
2334           /* more than one solution, keep all disabled */
2335         }
2336       for (i = disabledcnt; i < disabled.count; i += 2)
2337         {
2338           /* disable em */
2339           r = solv->rules + disabled.elements[i];
2340           disabled.elements[i + 1] = r->w1;
2341           r->w1 = 0;
2342 #if 0
2343           printf("disable ");
2344           printrule(solv, r);
2345 #endif
2346         }
2347     }
2348   /* enable refined rules again */
2349   for (i = 0; i < disabled.count; i += 2)
2350     {
2351       r = solv->rules + disabled.elements[i];
2352       r->w1 = disabled.elements[i + 1];
2353     }
2354   /* disable problem rules again so that we are in the same state as before */
2355   for (i = 0; problem[i]; i++)
2356     {
2357       r = solv->rules + problem[i];
2358       r->w1 = 0;
2359     }
2360   printf("refine_suggestion end\n");
2361 }
2362
2363
2364 /*
2365  * printdecisions
2366  */
2367
2368 static const char *
2369 id2rc(Solver *solv, Id id)
2370 {
2371   const char *evr;
2372   if (solv->rc_output != 2)
2373     return "";
2374   evr = id2str(solv->pool, id);
2375   if (*evr < '0' || *evr > '9')
2376     return "0:";
2377   while (*evr >= '0' && *evr <= '9')
2378     evr++;
2379   if (*evr != ':')
2380     return "0:";
2381   return "";
2382 }
2383
2384 void
2385 printdecisions(Solver *solv)
2386 {
2387   Pool *pool = solv->pool;
2388   Id p, *obsoletesmap;
2389   int i;
2390   Solvable *s;
2391
2392   obsoletesmap = (Id *)xcalloc(pool->nsolvables, sizeof(Id));
2393   for (i = 0; i < solv->decisionq.count; i++)
2394     {
2395       Id obs, *obsp;
2396       Id *pp, n;
2397
2398       n = solv->decisionq.elements[i];
2399       if (n < 0)
2400         continue;
2401       if (n == SYSTEMSOLVABLE)
2402         continue;
2403       if (n >= solv->system->start && n < solv->system->start + solv->system->nsolvables)
2404         continue;
2405       s = pool->solvables + n;
2406       if (s->obsoletes)
2407         {
2408           obsp = s->source->idarraydata + s->obsoletes;
2409           while ((obs = *obsp++) != 0)
2410             FOR_PROVIDES(p, pp, obs)
2411               {
2412                 if (p >= solv->system->start && p < solv->system->start + solv->system->nsolvables)
2413                   {
2414                     obsoletesmap[p] = n;
2415                     obsoletesmap[n]++;
2416                   }
2417               }
2418         }
2419       FOR_PROVIDES(p, pp, s->name)
2420         if (s->name == pool->solvables[p].name)
2421           {
2422             if (p >= solv->system->start && p < solv->system->start + solv->system->nsolvables)
2423               {
2424                 obsoletesmap[p] = n;
2425                 obsoletesmap[n]++;
2426               }
2427           }
2428     }
2429
2430   if (solv->rc_output)
2431     printf(">!> Solution #1:\n");
2432
2433   int installs = 0, uninstalls = 0, upgrades = 0;
2434
2435   /* print solvables to be erased */
2436
2437   for (i = solv->system->start; i < solv->system->start + solv->system->nsolvables; i++)
2438     {
2439       if (solv->decisionmap[i] > 0)
2440         continue;
2441       if (obsoletesmap[i])
2442         continue;
2443       s = pool->solvables + i;
2444       if (solv->rc_output == 2)
2445         printf(">!> remove  %s-%s%s\n", id2str(pool, s->name), id2rc(solv, s->evr), id2str(pool, s->evr));
2446       else if (solv->rc_output)
2447         printf(">!> remove  %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2448       else
2449         printf("erase   %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2450       uninstalls++;
2451     }
2452
2453   /* print solvables to be installed */
2454
2455   for (i = 0; i < solv->decisionq.count; i++)
2456     {
2457       int j;
2458       p = solv->decisionq.elements[i];
2459       if (p < 0)
2460         continue;
2461       if (p == SYSTEMSOLVABLE)
2462         continue;
2463       if (p >= solv->system->start && p < solv->system->start + solv->system->nsolvables)
2464         continue;
2465       s = pool->solvables + p;
2466
2467       if (!obsoletesmap[p])
2468         {
2469           if (solv->rc_output)
2470             printf(">!> ");
2471           printf("install %s-%s%s", id2str(pool, s->name), id2rc(solv, s->evr), id2str(pool, s->evr));
2472           if (solv->rc_output != 2)
2473             printf(".%s", id2str(pool, s->arch));
2474           installs++;
2475         }
2476       else if (!solv->rc_output)
2477         {
2478           printf("update  %s-%s.%s  (obsoletes", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2479           for (j = solv->system->start; j < solv->system->start + solv->system->nsolvables; j++)
2480             {
2481               if (obsoletesmap[j] != p)
2482                 continue;
2483               s = pool->solvables + j;
2484               printf(" %s-%s.%s", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2485             }
2486           printf(")");
2487           upgrades++;
2488         }
2489       else
2490         {
2491           Solvable *f, *fn = 0;
2492           for (j = solv->system->start; j < solv->system->start + solv->system->nsolvables; j++)
2493             {
2494               if (obsoletesmap[j] != p)
2495                 continue;
2496               f = pool->solvables + j;
2497               if (fn || f->name != s->name)
2498                 {
2499                   if (solv->rc_output == 2)
2500                     printf(">!> remove  %s-%s%s\n", id2str(pool, f->name), id2rc(solv, f->evr), id2str(pool, f->evr));
2501                   else if (solv->rc_output)
2502                     printf(">!> remove  %s-%s.%s\n", id2str(pool, f->name), id2str(pool, f->evr), id2str(pool, f->arch));
2503                   uninstalls++;
2504                 }
2505               else
2506                 fn = f;
2507             }
2508           if (!fn)
2509             {
2510               printf(">!> install %s-%s%s", id2str(pool, s->name), id2rc(solv, s->evr), id2str(pool, s->evr));
2511               if (solv->rc_output != 2)
2512                 printf(".%s", id2str(pool, s->arch));
2513               installs++;
2514             }
2515           else
2516             {
2517               if (solv->rc_output == 2)
2518                 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));
2519               else
2520                 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));
2521               upgrades++;
2522             }
2523         }
2524       if (solv->rc_output)
2525         {
2526           Source *source = s->source;
2527           if (source && strcmp(source_name(source), "locales"))
2528             printf("[%s]", source_name(source));
2529         }
2530       printf("\n");
2531     }
2532
2533   if (solv->rc_output)
2534     printf(">!> installs=%d, upgrades=%d, uninstalls=%d\n", installs, upgrades, uninstalls);
2535
2536   xfree(obsoletesmap);
2537 }
2538
2539 static void
2540 create_obsolete_index(Solver *solv)
2541 {
2542   Pool *pool = solv->pool;
2543   Solvable *s;
2544   Source *system = solv->system;
2545   Id p, *pp, obs, *obsp, *obsoletes, *obsoletes_data;
2546   int i, n;
2547
2548   /* create reverse obsoletes map for system solvables */
2549   solv->obsoletes = obsoletes = xcalloc(system->nsolvables, sizeof(Id));
2550   for (i = 1; i < pool->nsolvables; i++)
2551     {
2552       s = pool->solvables + i;
2553       if (!s->obsoletes)
2554         continue;
2555       if (!pool_installable(pool, s))
2556         continue;
2557       obsp = s->source->idarraydata + s->obsoletes;
2558       while ((obs = *obsp++) != 0)
2559         FOR_PROVIDES(p, pp, obs)
2560           {
2561             if (p < system->start || p >= system->start + system->nsolvables)
2562               continue;
2563             if (pool->solvables[p].name == s->name)
2564               continue;
2565             obsoletes[p - system->start]++;
2566           }
2567     }
2568   n = 0;
2569   for (i = 0; i < system->nsolvables; i++)
2570     if (obsoletes[i])
2571       {
2572         n += obsoletes[i] + 1;
2573         obsoletes[i] = n;
2574       }
2575   solv->obsoletes_data = obsoletes_data = xcalloc(n + 1, sizeof(Id));
2576   if (pool->verbose) printf("obsoletes data: %d entries\n", n + 1);
2577   for (i = pool->nsolvables - 1; i > 0; i--)
2578     {
2579       s = pool->solvables + i;
2580       if (!s->obsoletes)
2581         continue;
2582       if (!pool_installable(pool, s))
2583         continue;
2584       obsp = s->source->idarraydata + s->obsoletes;
2585       while ((obs = *obsp++) != 0)
2586         FOR_PROVIDES(p, pp, obs)
2587           {
2588             if (p < system->start || p >= system->start + system->nsolvables)
2589               continue;
2590             if (pool->solvables[p].name == s->name)
2591               continue;
2592             p -= system->start;
2593             if (obsoletes_data[obsoletes[p]] != i)
2594               obsoletes_data[--obsoletes[p]] = i;
2595           }
2596     }
2597 }
2598
2599 /*-----------------------------------------------------------------*/
2600 /* main() */
2601
2602 /*
2603  *
2604  * solve job queue
2605  *
2606  */
2607
2608 void
2609 solve(Solver *solv, Queue *job)
2610 {
2611   Pool *pool = solv->pool;
2612   int i;
2613   Map addedmap;                        /* '1' == have rule for solvable */
2614   Map noupdaterule;                    /* '1' == don't update (scheduled for removal) */
2615   Id how, what, p, *pp, d;
2616   Queue q;
2617   Rule *r;
2618   Solvable *s;
2619
2620   /*
2621    * create basic rule set of all involved packages
2622    * as bitmaps
2623    *
2624    */
2625
2626   mapinit(&addedmap, pool->nsolvables);
2627   mapinit(&noupdaterule, pool->nsolvables);
2628
2629   queueinit(&q);
2630
2631   /*
2632    * always install our system solvable
2633    */
2634   MAPSET(&addedmap, SYSTEMSOLVABLE);
2635   queuepush(&solv->decisionq, SYSTEMSOLVABLE);
2636   queuepush(&solv->decisionq_why, 0);
2637   solv->decisionmap[SYSTEMSOLVABLE] = 1;
2638
2639   /*
2640    * create rules for installed solvables -> keep them installed
2641    * so called: rpm rules
2642    *
2643    */
2644
2645   for (i = solv->system->start; i < solv->system->start + solv->system->nsolvables; i++)
2646     addrulesforsolvable(solv, pool->solvables + i, &addedmap);
2647
2648   /*
2649    * create install rules
2650    *
2651    * two passes, as we want to keep the rpm rules distinct from the job rules
2652    *
2653    */
2654
2655   if (solv->noupdateprovide && solv->system->nsolvables)
2656     create_obsolete_index(solv);
2657
2658   /*
2659    * solvable rules
2660    *  process job rules for solvables
2661    */
2662
2663   for (i = 0; i < job->count; i += 2)
2664     {
2665       how = job->elements[i];
2666       what = job->elements[i + 1];
2667
2668       switch(how)
2669         {
2670         case SOLVER_INSTALL_SOLVABLE:
2671           addrulesforsolvable(solv, pool->solvables + what, &addedmap);
2672           break;
2673         case SOLVER_INSTALL_SOLVABLE_NAME:
2674         case SOLVER_INSTALL_SOLVABLE_PROVIDES:
2675           QUEUEEMPTY(&q);
2676           FOR_PROVIDES(p, pp, what)
2677             {
2678                                        /* if by name, ensure that the name matches */
2679               if (how == SOLVER_INSTALL_SOLVABLE_NAME && pool->solvables[p].name != what)
2680                 continue;
2681               addrulesforsolvable(solv, pool->solvables + p, &addedmap);
2682             }
2683           break;
2684         case SOLVER_INSTALL_SOLVABLE_UPDATE:
2685           /* dont allow downgrade */
2686           addupdaterule(solv, pool->solvables + what, &addedmap, 0, 0, 1);
2687           break;
2688         }
2689     }
2690
2691   /*
2692    * if unstalls are disallowed, add update rules for every
2693    * installed solvables in the hope to circumvent uninstall
2694    * by upgrading
2695    *
2696    */
2697
2698 #if 0
2699   if (!solv->allowuninstall)
2700     {
2701       /* add update rule for every installed package */
2702       for (i = solv->system->start; i < solv->system->start + solv->system->nsolvables; i++)
2703         addupdaterule(solv, pool->solvables + i, &addedmap, solv->allowdowngrade, solv->allowarchchange, 1);
2704     }
2705 #else  /* this is just to add the needed rpm rules to our set */
2706   for (i = solv->system->start; i < solv->system->start + solv->system->nsolvables; i++)
2707     addupdaterule(solv, pool->solvables + i, &addedmap, 1, 1, 1);
2708 #endif
2709
2710   addrulesforweak(solv, &addedmap);
2711 #if 1
2712   if (pool->verbose)
2713     {
2714       int possible = 0, installable = 0;
2715       for (i = 1; i < pool->nsolvables; i++)
2716         {
2717           if (pool_installable(pool, pool->solvables + i))
2718             installable++;
2719           if (MAPTST(&addedmap, i))
2720             possible++;
2721         }
2722       printf("%d of %d installable solvables used for solving\n", possible, installable);
2723     }
2724 #endif
2725
2726   /*
2727    * first pass done
2728    *
2729    * unify existing rules before going over all job rules
2730    *
2731    */
2732
2733   unifyrules(solv);     /* remove duplicate rpm rules */
2734
2735   /*
2736    * at this point the system is always solvable,
2737    * as an empty system (remove all packages) is a valid solution
2738    */
2739   if (pool->verbose) printf("decisions based on rpms: %d\n", solv->decisionq.count);
2740
2741   /*
2742    * now add all job rules
2743    */
2744
2745   solv->jobrules = solv->nrules;
2746
2747   for (i = 0; i < job->count; i += 2)
2748     {
2749       how = job->elements[i];
2750       what = job->elements[i + 1];
2751       switch(how)
2752         {
2753         case SOLVER_INSTALL_SOLVABLE:                   /* install specific solvable */
2754           if (solv->rc_output) {
2755             Solvable *s = pool->solvables + what;
2756             printf(">!> Installing %s from channel %s\n", id2str(pool, s->name), source_name(s->source));
2757           }
2758           addrule(solv, what, 0);                       /* install by Id */
2759           queuepush(&solv->ruletojob, i);
2760           break;
2761         case SOLVER_ERASE_SOLVABLE:
2762           addrule(solv, -what, 0);                        /* remove by Id */
2763           queuepush(&solv->ruletojob, i);
2764           MAPSET(&noupdaterule, what);
2765           break;
2766         case SOLVER_INSTALL_SOLVABLE_NAME:                /* install by capability */
2767         case SOLVER_INSTALL_SOLVABLE_PROVIDES:
2768           QUEUEEMPTY(&q);
2769           FOR_PROVIDES(p, pp, what)    /* check all providers */
2770             {
2771                                        /* if by name, ensure that the name matches */
2772               if (how == SOLVER_INSTALL_SOLVABLE_NAME && pool->solvables[p].name != what)
2773                 continue;
2774               queuepush(&q, p);
2775             }
2776           if (!q.count) {              /* no provider found -> abort */
2777             fprintf(stderr, "Nothing provides '%s'\n", id2str(pool, what));
2778             /* XXX make this a problem! */
2779             return;
2780             abort();
2781           }
2782
2783           p = queueshift(&q);          /* get first provider */
2784           if (!q.count)
2785             d = 0;                     /* single provider ? -> make assertion */
2786           else
2787             d = pool_queuetowhatprovides(pool, &q);   /* get all providers */
2788           addrule(solv, p, d);         /* add 'requires' rule */
2789           queuepush(&solv->ruletojob, i);
2790           break;
2791         case SOLVER_ERASE_SOLVABLE_NAME:                  /* remove by capability */
2792         case SOLVER_ERASE_SOLVABLE_PROVIDES:
2793           FOR_PROVIDES(p, pp, what)
2794             {
2795                                        /* if by name, ensure that the name matches */
2796               if (how == SOLVER_ERASE_SOLVABLE_NAME && pool->solvables[p].name != what)
2797                 continue;
2798
2799               addrule(solv, -p, 0);  /* add 'remove' rule */
2800               queuepush(&solv->ruletojob, i);
2801               MAPSET(&noupdaterule, p);
2802             }
2803           break;
2804         case SOLVER_INSTALL_SOLVABLE_UPDATE:              /* find update for solvable */
2805           addupdaterule(solv, pool->solvables + what, &addedmap, 0, 0, 0);
2806           queuepush(&solv->ruletojob, i);
2807           break;
2808         }
2809     }
2810
2811   if (solv->ruletojob.count != solv->nrules - solv->jobrules)
2812     abort();
2813
2814   if (pool->verbose) printf("problems so far: %d\n", solv->problems.count);
2815
2816   /*
2817    * now add policy rules
2818    *
2819    */
2820
2821   solv->systemrules = solv->nrules;
2822
2823   /*
2824    * create rules for updating installed solvables
2825    *
2826    * (Again ?)
2827    *
2828    */
2829
2830   if (!solv->allowuninstall)
2831     {                                  /* loop over all installed solvables */
2832       for (i = solv->system->start; i < solv->system->start + solv->system->nsolvables; i++)
2833       {
2834         if (!MAPTST(&noupdaterule, i)) /* if not marked as 'noupdate' */
2835           addupdaterule(solv, pool->solvables + i, &addedmap, solv->allowdowngrade, solv->allowarchchange, 0);
2836         else
2837           addrule(solv, 0, 0);          /* place holder */
2838       }
2839       /* consistency check: we added a rule for _every_ system solvable */
2840       if (solv->nrules - solv->systemrules != solv->system->nsolvables)
2841         abort();
2842     }
2843
2844   if (pool->verbose) printf("problems so far: %d\n", solv->problems.count);
2845
2846   /* create special weak system rules */
2847   if (solv->system->nsolvables)
2848     {
2849       solv->weaksystemrules = xcalloc(solv->system->nsolvables, sizeof(Id));
2850       for (i = 0; i < solv->system->nsolvables; i++)
2851         {
2852           if (MAPTST(&noupdaterule, solv->system->start + i))
2853             continue;
2854           findupdatepackages(solv, pool->solvables + solv->system->start + i, &q, (Map *)0, 1, 1);
2855           if (q.count)
2856             solv->weaksystemrules[i] = pool_queuetowhatprovides(pool, &q);
2857         }
2858     }
2859
2860   /* free unneeded memory */
2861   mapfree(&addedmap);
2862   mapfree(&noupdaterule);
2863   queuefree(&q);
2864
2865   solv->weakrules = solv->nrules;
2866
2867   /* try real hard to keep packages installed */
2868   if (0)
2869     {
2870       for (i = 0; i < solv->system->nsolvables; i++)
2871         {
2872           d = solv->weaksystemrules[i];
2873           addrule(solv, solv->system->start + i, d);
2874         }
2875     }
2876
2877   /*
2878    * solve !
2879    *
2880    */
2881
2882   makeruledecisions(solv);
2883   run_solver(solv, 1, 1);
2884
2885   /* find suggested packages */
2886   if (!solv->problems.count)
2887     {
2888       Id sug, *sugp, enh, *enhp, p, *pp;
2889
2890       /* create map of all suggests that are still open */
2891       solv->recommends_index = -1;
2892       MAPZERO(&solv->suggestsmap);
2893       for (i = 0; i < solv->decisionq.count; i++)
2894         {
2895           p = solv->decisionq.elements[i];
2896           if (p < 0)
2897             continue;
2898           s = pool->solvables + p;
2899           if (s->suggests)
2900             {
2901               sugp = s->source->idarraydata + s->suggests;
2902               while ((sug = *sugp++) != 0)
2903                 {
2904                   FOR_PROVIDES(p, pp, sug)
2905                     if (solv->decisionmap[p] > 0)
2906                       break;
2907                   if (p)
2908                     continue;   /* already fulfilled */
2909                   FOR_PROVIDES(p, pp, sug)
2910                     MAPSET(&solv->suggestsmap, p);
2911                 }
2912             }
2913         }
2914       for (i = 1; i < pool->nsolvables; i++)
2915         {
2916           if (solv->decisionmap[i] != 0)
2917             continue;
2918           s = pool->solvables + i;
2919           if (!MAPTST(&solv->suggestsmap, i))
2920             {
2921               if (!s->enhances)
2922                 continue;
2923               if (!pool_installable(pool, s))
2924                 continue;
2925               enhp = s->source->idarraydata + s->enhances;
2926               while ((enh = *enhp++) != 0)
2927                 if (dep_fulfilled(solv, enh))
2928                   break;
2929               if (!enh)
2930                 continue;
2931             }
2932           queuepush(&solv->suggestions, i);
2933         }
2934       prune_best_version_arch(pool, &solv->suggestions);
2935     }
2936
2937   /*
2938    *
2939    * print solver result
2940    *
2941    */
2942
2943   if (pool->verbose) printf("-------------------------------------------------------------\n");
2944
2945   if (solv->problems.count)
2946     {
2947       Queue problems;
2948       Queue solution;
2949       Id *problem;
2950       Id why, what;
2951       int j, ji;
2952
2953       if (!pool->verbose)
2954         return;
2955       clonequeue(&problems, &solv->problems);
2956       queueinit(&solution);
2957       printf("Encountered problems! Here are the solutions:\n");
2958       problem = problems.elements;
2959       for (i = 0; i < problems.count; i++)
2960         {
2961           Id v = problems.elements[i];
2962           if (v == 0)
2963             {
2964               printf("====================================\n");
2965               problem = problems.elements + i + 1;
2966               continue;
2967             }
2968           if (v >= solv->jobrules && v < solv->systemrules)
2969             {
2970               ji = solv->ruletojob.elements[v - solv->jobrules];
2971               for (j = 0; ; j++)
2972                 {
2973                   if (problem[j] >= solv->jobrules && problem[j] < solv->systemrules && ji == solv->ruletojob.elements[problem[j] - solv->jobrules])
2974                     break;
2975                 }
2976               if (problem + j < problems.elements + i)
2977                 continue;
2978             }
2979           refine_suggestion(solv, problem, v, &solution);
2980           for (j = 0; j < solution.count; j++)
2981             {
2982               r = solv->rules + solution.elements[j];
2983               why = solution.elements[j];
2984 #if 0
2985               printrule(solv, r);
2986 #endif
2987               if (why >= solv->jobrules && why < solv->systemrules)
2988                 {
2989                   ji = solv->ruletojob.elements[why - solv->jobrules];
2990                   what = job->elements[ji + 1];
2991                   switch (job->elements[ji])
2992                     {
2993                     case SOLVER_INSTALL_SOLVABLE:
2994                       s = pool->solvables + what;
2995                       printf("- do not install %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
2996                       break;
2997                     case SOLVER_ERASE_SOLVABLE:
2998                       s = pool->solvables + what;
2999                       printf("- do not deinstall %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
3000                       break;
3001                     case SOLVER_INSTALL_SOLVABLE_NAME:
3002                       printf("- do not install %s\n", id2str(pool, what));
3003                       break;
3004                     case SOLVER_ERASE_SOLVABLE_NAME:
3005                       printf("- do not deinstall %s\n", id2str(pool, what));
3006                       break;
3007                     case SOLVER_INSTALL_SOLVABLE_PROVIDES:
3008                       printf("- do not install a solvable providing %s\n", dep2str(pool, what));
3009                       break;
3010                     case SOLVER_ERASE_SOLVABLE_PROVIDES:
3011                       printf("- do not deinstall all solvables providing %s\n", dep2str(pool, what));
3012                       break;
3013                     case SOLVER_INSTALL_SOLVABLE_UPDATE:
3014                       s = pool->solvables + what;
3015                       printf("- do not install most recent version of %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
3016                       break;
3017                     default:
3018                       printf("- do something different\n");
3019                       break;
3020                     }
3021                 }
3022               else if (why >= solv->systemrules && why < solv->weakrules)
3023                 {
3024                   Solvable *sd = 0;
3025                   s = pool->solvables + solv->system->start + (why - solv->systemrules);
3026                   if (solv->weaksystemrules && solv->weaksystemrules[why - solv->systemrules])
3027                     {
3028                       Id *dp = pool->whatprovidesdata + solv->weaksystemrules[why - solv->systemrules];
3029                       for (; *dp; dp++)
3030                         {
3031                           if (*dp >= solv->system->start && *dp < solv->system->start + solv->system->nsolvables)
3032                             continue;
3033                           if (solv->decisionmap[*dp] > 0)
3034                             {
3035                               sd = pool->solvables + *dp;
3036                               break;
3037                             }
3038                         }
3039                     }
3040                   if (sd)
3041                     {
3042                       int gotone = 0;
3043                       if (evrcmp(pool, sd->evr, s->evr) < 0)
3044                         {
3045                           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));
3046                           gotone = 1;
3047                         }
3048                       if (!solv->allowarchchange && archchanges(pool, sd, s))
3049                         {
3050                           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));
3051                           gotone = 1;
3052                         }
3053                       if (!gotone)
3054                         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));
3055                     }
3056                   else
3057                     {
3058                       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));
3059                     }
3060                 }
3061               else
3062                 {
3063                   abort();
3064                 }
3065             }
3066           printf("------------------------------------\n");
3067         }
3068       return;
3069     }
3070
3071   printdecisions(solv);
3072   if (solv->suggestions.count)
3073     {
3074       printf("\nsuggested packages:\n");
3075       for (i = 0; i < solv->suggestions.count; i++)
3076         {
3077           s = pool->solvables + solv->suggestions.elements[i];
3078           printf("- %s-%s.%s\n", id2str(pool, s->name), id2str(pool, s->evr), id2str(pool, s->arch));
3079         }
3080     }
3081 }
3082
3083
3084 // EOF