src/solver.c

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