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