src/solver.c

   1 /*
   2  * Copyright (c) 2007-2008, 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 #include <assert.h>
  19
  20 #include "solver.h"
  21 #include "bitmap.h"
  22 #include "pool.h"
  23 #include "util.h"
  24 #include "evr.h"
  25 #include "policy.h"
  26 #include "solverdebug.h"
  27
  28 #define RULES_BLOCK 63
  29
  30 static void reenablepolicyrules(Solver *solv, Queue *job, int jobidx);
  31
  32 /********************************************************************
  33  *
  34  * dependency check helpers
  35  *
  36  */
  37
  38 /*-------------------------------------------------------------------
  39  * handle split provides
  40  */
  41
  42 int
  43 solver_splitprovides(Solver *solv, Id dep)
  44 {
  45   Pool *pool = solv->pool;
  46   Id p, pp;
  47   Reldep *rd;
  48   Solvable *s;
  49
  50   if (!solv->dosplitprovides || !solv->installed)
  51     return 0;
  52   if (!ISRELDEP(dep))
  53     return 0;
  54   rd = GETRELDEP(pool, dep);
  55   if (rd->flags != REL_WITH)
  56     return 0;
  57   FOR_PROVIDES(p, pp, dep)
  58     {
  59       s = pool->solvables + p;
  60       if (s->repo == solv->installed && s->name == rd->name)
  61         return 1;
  62     }
  63   return 0;
  64 }
  65
  66
  67 /*-------------------------------------------------------------------
  68  * solver_dep_installed
  69  */
  70
  71 int
  72 solver_dep_installed(Solver *solv, Id dep)
  73 {
  74 #if 0
  75   Pool *pool = solv->pool;
  76   Id p, pp;
  77
  78   if (ISRELDEP(dep))
  79     {
  80       Reldep *rd = GETRELDEP(pool, dep);
  81       if (rd->flags == REL_AND)
  82         {
  83           if (!solver_dep_installed(solv, rd->name))
  84             return 0;
  85           return solver_dep_installed(solv, rd->evr);
  86         }
  87       if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
  88         return solver_dep_installed(solv, rd->evr);
  89     }
  90   FOR_PROVIDES(p, pp, dep)
  91     {
  92       if (p == SYSTEMSOLVABLE || (solv->installed && pool->solvables[p].repo == solv->installed))
  93         return 1;
  94     }
  95 #endif
  96   return 0;
  97 }
  98
  99
 100 /*-------------------------------------------------------------------
 101  * Check if dependenc is possible
 102  *
 103  * this mirrors solver_dep_fulfilled
 104  * but uses map m instead of the decisionmap
 105  */
 106
 107 static inline int
 108 dep_possible(Solver *solv, Id dep, Map *m)
 109 {
 110   Pool *pool = solv->pool;
 111   Id p, pp;
 112
 113   if (ISRELDEP(dep))
 114     {
 115       Reldep *rd = GETRELDEP(pool, dep);
 116       if (rd->flags == REL_AND)
 117         {
 118           if (!dep_possible(solv, rd->name, m))
 119             return 0;
 120           return dep_possible(solv, rd->evr, m);
 121         }
 122       if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
 123         return solver_splitprovides(solv, rd->evr);
 124       if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
 125         return solver_dep_installed(solv, rd->evr);
 126     }
 127   FOR_PROVIDES(p, pp, dep)
 128     {
 129       if (MAPTST(m, p))
 130         return 1;
 131     }
 132   return 0;
 133 }
 134
 135 /********************************************************************
 136  *
 137  * Rule handling
 138  *
 139  * - unify rules, remove duplicates
 140  */
 141
 142 static Pool *unifyrules_sortcmp_data;
 143
 144 /*-------------------------------------------------------------------
 145  *
 146  * compare rules for unification sort
 147  *
 148  */
 149
 150 static int
 151 unifyrules_sortcmp(const void *ap, const void *bp)
 152 {
 153   Pool *pool = unifyrules_sortcmp_data;
 154   Rule *a = (Rule *)ap;
 155   Rule *b = (Rule *)bp;
 156   Id *ad, *bd;
 157   int x;
 158
 159   x = a->p - b->p;
 160   if (x)
 161     return x;                          /* p differs */
 162
 163   /* identical p */
 164   if (a->d == 0 && b->d == 0)
 165     return a->w2 - b->w2;              /* assertion: return w2 diff */
 166
 167   if (a->d == 0)                       /* a is assertion, b not */
 168     {
 169       x = a->w2 - pool->whatprovidesdata[b->d];
 170       return x ? x : -1;
 171     }
 172
 173   if (b->d == 0)                       /* b is assertion, a not */
 174     {
 175       x = pool->whatprovidesdata[a->d] - b->w2;
 176       return x ? x : 1;
 177     }
 178
 179   /* compare whatprovidesdata */
 180   ad = pool->whatprovidesdata + a->d;
 181   bd = pool->whatprovidesdata + b->d;
 182   while (*bd)
 183     if ((x = *ad++ - *bd++) != 0)
 184       return x;
 185   return *ad;
 186 }
 187
 188
 189 /*-------------------------------------------------------------------
 190  *
 191  * unify rules
 192  * go over all rules and remove duplicates
 193  */
 194
 195 static void
 196 unifyrules(Solver *solv)
 197 {
 198   Pool *pool = solv->pool;
 199   int i, j;
 200   Rule *ir, *jr;
 201
 202   if (solv->nrules <= 1)               /* nothing to unify */
 203     return;
 204
 205   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- unifyrules -----\n");
 206
 207   /* sort rules first */
 208   unifyrules_sortcmp_data = solv->pool;
 209   qsort(solv->rules + 1, solv->nrules - 1, sizeof(Rule), unifyrules_sortcmp);
 210
 211   /* prune rules
 212    * i = unpruned
 213    * j = pruned
 214    */
 215   jr = 0;
 216   for (i = j = 1, ir = solv->rules + i; i < solv->nrules; i++, ir++)
 217     {
 218       if (jr && !unifyrules_sortcmp(ir, jr))
 219         continue;                      /* prune! */
 220       jr = solv->rules + j++;          /* keep! */
 221       if (ir != jr)
 222         *jr = *ir;
 223     }
 224
 225   /* reduced count from nrules to j rules */
 226   POOL_DEBUG(SAT_DEBUG_STATS, "pruned rules from %d to %d\n", solv->nrules, j);
 227
 228   /* adapt rule buffer */
 229   solv->nrules = j;
 230   solv->rules = sat_extend_resize(solv->rules, solv->nrules, sizeof(Rule), RULES_BLOCK);
 231     /*
 232      * debug: statistics
 233      */
 234   IF_POOLDEBUG (SAT_DEBUG_STATS)
 235     {
 236       int binr = 0;
 237       int lits = 0;
 238       Id *dp;
 239       Rule *r;
 240
 241       for (i = 1; i < solv->nrules; i++)
 242         {
 243           r = solv->rules + i;
 244           if (r->d == 0)
 245             binr++;
 246           else
 247             {
 248               dp = solv->pool->whatprovidesdata + r->d;
 249               while (*dp++)
 250                 lits++;
 251             }
 252         }
 253       POOL_DEBUG(SAT_DEBUG_STATS, "  binary: %d\n", binr);
 254       POOL_DEBUG(SAT_DEBUG_STATS, "  normal: %d, %d literals\n", solv->nrules - 1 - binr, lits);
 255     }
 256   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- unifyrules end -----\n");
 257 }
 258
 259 #if 0
 260
 261 /*
 262  * hash rule
 263  */
 264
 265 static Hashval
 266 hashrule(Solver *solv, Id p, Id d, int n)
 267 {
 268   unsigned int x = (unsigned int)p;
 269   int *dp;
 270
 271   if (n <= 1)
 272     return (x * 37) ^ (unsigned int)d;
 273   dp = solv->pool->whatprovidesdata + d;
 274   while (*dp)
 275     x = (x * 37) ^ (unsigned int)*dp++;
 276   return x;
 277 }
 278 #endif
 279
 280
 281 /*-------------------------------------------------------------------
 282  *
 283  */
 284
 285 /*
 286  * add rule
 287  *  p = direct literal; always < 0 for installed rpm rules
 288  *  d, if < 0 direct literal, if > 0 offset into whatprovides, if == 0 rule is assertion (look at p only)
 289  *
 290  *
 291  * A requires b, b provided by B1,B2,B3 => (-A|B1|B2|B3)
 292  *
 293  * p < 0 : pkg id of A
 294  * d > 0 : Offset in whatprovidesdata (list of providers of b)
 295  *
 296  * A conflicts b, b provided by B1,B2,B3 => (-A|-B1), (-A|-B2), (-A|-B3)
 297  * p < 0 : pkg id of A
 298  * d < 0 : Id of solvable (e.g. B1)
 299  *
 300  * d == 0: unary rule, assertion => (A) or (-A)
 301  *
 302  *   Install:    p > 0, d = 0   (A)             user requested install
 303  *   Remove:     p < 0, d = 0   (-A)            user requested remove (also: uninstallable)
 304  *   Requires:   p < 0, d > 0   (-A|B1|B2|...)  d: <list of providers for requirement of p>
 305  *   Updates:    p > 0, d > 0   (A|B1|B2|...)   d: <list of updates for solvable p>
 306  *   Conflicts:  p < 0, d < 0   (-A|-B)         either p (conflict issuer) or d (conflict provider) (binary rule)
 307  *                                              also used for obsoletes
 308  *   ?:          p > 0, d < 0   (A|-B)
 309  *   No-op ?:    p = 0, d = 0   (null)          (used as policy rule placeholder)
 310  *
 311  *   resulting watches:
 312  *   ------------------
 313  *   Direct assertion (no watch needed)( if d <0 ) --> d = 0, w1 = p, w2 = 0
 314  *   Binary rule: p = first literal, d = 0, w2 = second literal, w1 = p
 315  *   every other : w1 = p, w2 = whatprovidesdata[d];
 316  *   Disabled rule: w1 = 0
 317  *
 318  *   always returns a rule for non-rpm rules
 319  */
 320
 321 static Rule *
 322 addrule(Solver *solv, Id p, Id d)
 323 {
 324   Pool *pool = solv->pool;
 325   Rule *r = 0;
 326   Id *dp = 0;
 327
 328   int n = 0;                           /* number of literals in rule - 1
 329                                           0 = direct assertion (single literal)
 330                                           1 = binary rule
 331                                           >1 =
 332                                         */
 333
 334   /* it often happenes that requires lead to adding the same rpm rule
 335    * multiple times, so we prune those duplicates right away to make
 336    * the work for unifyrules a bit easier */
 337
 338   if (solv->nrules                      /* we already have rules */
 339       && !solv->rpmrules_end)           /* but are not done with rpm rules */
 340     {
 341       r = solv->rules + solv->nrules - 1;   /* get the last added rule */
 342       if (r->p == p && r->d == d && d != 0)   /* identical and not user requested */
 343         return r;
 344     }
 345
 346     /*
 347      * compute number of literals (n) in rule
 348      */
 349
 350   if (d < 0)
 351     {
 352       /* always a binary rule */
 353       if (p == d)
 354         return 0;                      /* ignore self conflict */
 355       n = 1;
 356     }
 357   else if (d > 0)
 358     {
 359       for (dp = pool->whatprovidesdata + d; *dp; dp++, n++)
 360         if (*dp == -p)
 361           return 0;                     /* rule is self-fulfilling */
 362
 363       if (n == 1)   /* have single provider */
 364         d = dp[-1];                     /* take single literal */
 365     }
 366
 367   if (n == 1 && p > d && !solv->rpmrules_end)
 368     {
 369       /* smallest literal first so we can find dups */
 370       n = p; p = d; d = n;             /* p <-> d */
 371       n = 1;                           /* re-set n, was used as temp var */
 372     }
 373
 374     /*
 375      * check for duplicate
 376      */
 377
 378   /* check if the last added rule (r) is exactly the same as what we're looking for. */
 379   if (r && n == 1 && !r->d && r->p == p && r->w2 == d)
 380     return r;  /* binary rule */
 381
 382     /* have n-ary rule with same first literal, check other literals */
 383   if (r && n > 1 && r->d && r->p == p)
 384     {
 385       /* Rule where d is an offset in whatprovidesdata */
 386       Id *dp2;
 387       if (d == r->d)
 388         return r;
 389       dp2 = pool->whatprovidesdata + r->d;
 390       for (dp = pool->whatprovidesdata + d; *dp; dp++, dp2++)
 391         if (*dp != *dp2)
 392           break;
 393       if (*dp == *dp2)
 394         return r;
 395    }
 396
 397     /*
 398      * allocate new rule
 399      */
 400
 401   /* extend rule buffer */
 402   solv->rules = sat_extend(solv->rules, solv->nrules, 1, sizeof(Rule), RULES_BLOCK);
 403   r = solv->rules + solv->nrules++;    /* point to rule space */
 404
 405     /*
 406      * r = new rule
 407      */
 408
 409   r->p = p;
 410   if (n == 0)
 411     {
 412       /* direct assertion, no watch needed */
 413       r->d = 0;
 414       r->w1 = p;
 415       r->w2 = 0;
 416     }
 417   else if (n == 1)
 418     {
 419       /* binary rule */
 420       r->d = 0;
 421       r->w1 = p;
 422       r->w2 = d;
 423     }
 424   else
 425     {
 426       r->d = d;
 427       r->w1 = p;
 428       r->w2 = pool->whatprovidesdata[d];
 429     }
 430   r->n1 = 0;
 431   r->n2 = 0;
 432
 433   IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION)
 434     {
 435       POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "  Add rule: ");
 436       solver_printrule(solv, SAT_DEBUG_RULE_CREATION, r);
 437     }
 438
 439   return r;
 440 }
 441
 442 /*-------------------------------------------------------------------
 443  * disable rule
 444  */
 445
 446 static inline void
 447 disablerule(Solver *solv, Rule *r)
 448 {
 449   if (r->d >= 0)
 450     r->d = -r->d - 1;
 451 }
 452
 453 /*-------------------------------------------------------------------
 454  * enable rule
 455  */
 456
 457 static inline void
 458 enablerule(Solver *solv, Rule *r)
 459 {
 460   if (r->d < 0)
 461     r->d = -r->d - 1;
 462 }
 463
 464
 465 /**********************************************************************************/
 466
 467 /* a problem is an item on the solver's problem list. It can either be >0, in that
 468  * case it is a update rule, or it can be <0, which makes it refer to a job
 469  * consisting of multiple job rules.
 470  */
 471
 472 static void
 473 disableproblem(Solver *solv, Id v)
 474 {
 475   Rule *r;
 476   int i;
 477   Id *jp;
 478
 479   if (v > 0)
 480     {
 481       if (v >= solv->infarchrules && v < solv->infarchrules_end)
 482         {
 483           Pool *pool = solv->pool;
 484           Id name = pool->solvables[-solv->rules[v].p].name;
 485           while (v > solv->infarchrules && pool->solvables[-solv->rules[v - 1].p].name == name)
 486             v--;
 487           for (; v < solv->infarchrules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
 488             disablerule(solv, solv->rules + v);
 489           return;
 490         }
 491       if (v >= solv->duprules && v < solv->duprules_end)
 492         {
 493           Pool *pool = solv->pool;
 494           Id name = pool->solvables[-solv->rules[v].p].name;
 495           while (v > solv->duprules && pool->solvables[-solv->rules[v - 1].p].name == name)
 496             v--;
 497           for (; v < solv->duprules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
 498             disablerule(solv, solv->rules + v);
 499           return;
 500         }
 501       disablerule(solv, solv->rules + v);
 502       return;
 503     }
 504   v = -(v + 1);
 505   jp = solv->ruletojob.elements;
 506   for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++, jp++)
 507     if (*jp == v)
 508       disablerule(solv, r);
 509 }
 510
 511 /*-------------------------------------------------------------------
 512  * enableproblem
 513  */
 514
 515 static void
 516 enableproblem(Solver *solv, Id v)
 517 {
 518   Rule *r;
 519   int i;
 520   Id *jp;
 521
 522   if (v > 0)
 523     {
 524       if (v >= solv->infarchrules && v < solv->infarchrules_end)
 525         {
 526           Pool *pool = solv->pool;
 527           Id name = pool->solvables[-solv->rules[v].p].name;
 528           while (v > solv->infarchrules && pool->solvables[-solv->rules[v - 1].p].name == name)
 529             v--;
 530           for (; v < solv->infarchrules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
 531             enablerule(solv, solv->rules + v);
 532           return;
 533         }
 534       if (v >= solv->duprules && v < solv->duprules_end)
 535         {
 536           Pool *pool = solv->pool;
 537           Id name = pool->solvables[-solv->rules[v].p].name;
 538           while (v > solv->duprules && pool->solvables[-solv->rules[v - 1].p].name == name)
 539             v--;
 540           for (; v < solv->duprules_end && pool->solvables[-solv->rules[v].p].name == name; v++)
 541             enablerule(solv, solv->rules + v);
 542           return;
 543         }
 544       if (v >= solv->featurerules && v < solv->featurerules_end)
 545         {
 546           /* do not enable feature rule if update rule is enabled */
 547           r = solv->rules + (v - solv->featurerules + solv->updaterules);
 548           if (r->d >= 0)
 549             return;
 550         }
 551       enablerule(solv, solv->rules + v);
 552       if (v >= solv->updaterules && v < solv->updaterules_end)
 553         {
 554           /* disable feature rule when enabling update rule */
 555           r = solv->rules + (v - solv->updaterules + solv->featurerules);
 556           if (r->p)
 557             disablerule(solv, r);
 558         }
 559       return;
 560     }
 561   v = -(v + 1);
 562   jp = solv->ruletojob.elements;
 563   for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++, jp++)
 564     if (*jp == v)
 565       enablerule(solv, r);
 566 }
 567
 568
 569 /************************************************************************/
 570
 571 /*
 572  * make assertion rules into decisions
 573  *
 574  * go through update and job rules and add direct assertions
 575  * to the decisionqueue. If we find a conflict, disable rules and
 576  * add them to problem queue.
 577  */
 578
 579 static void
 580 makeruledecisions(Solver *solv)
 581 {
 582   Pool *pool = solv->pool;
 583   int i, ri, ii;
 584   Rule *r, *rr;
 585   Id v, vv;
 586   int decisionstart;
 587
 588   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- makeruledecisions ; size decisionq: %d -----\n",solv->decisionq.count);
 589
 590   decisionstart = solv->decisionq.count;
 591   for (ii = 0; ii < solv->ruleassertions.count; ii++)
 592     {
 593       ri = solv->ruleassertions.elements[ii];
 594       r = solv->rules + ri;
 595
 596       if (r->d < 0 || !r->p || r->w2)   /* disabled, dummy or no assertion */
 597         continue;
 598       /* do weak rules in phase 2 */
 599       if (ri < solv->learntrules && MAPTST(&solv->weakrulemap, ri))
 600         continue;
 601
 602       v = r->p;
 603       vv = v > 0 ? v : -v;
 604
 605       if (!solv->decisionmap[vv])          /* if not yet decided */
 606         {
 607             /*
 608              * decide !
 609              */
 610           queue_push(&solv->decisionq, v);
 611           queue_push(&solv->decisionq_why, r - solv->rules);
 612           solv->decisionmap[vv] = v > 0 ? 1 : -1;
 613           IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
 614             {
 615               Solvable *s = solv->pool->solvables + vv;
 616               if (v < 0)
 617                 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "conflicting %s (assertion)\n", solvable2str(solv->pool, s));
 618               else
 619                 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "installing  %s (assertion)\n", solvable2str(solv->pool, s));
 620             }
 621           continue;
 622         }
 623         /*
 624          * check previous decision: is it sane ?
 625          */
 626
 627       if (v > 0 && solv->decisionmap[vv] > 0)    /* ok to install */
 628         continue;
 629       if (v < 0 && solv->decisionmap[vv] < 0)    /* ok to remove */
 630         continue;
 631
 632         /*
 633          * found a conflict!
 634          *
 635          * The rule (r) we're currently processing says something
 636          * different (v = r->p) than a previous decision (decisionmap[abs(v)])
 637          * on this literal
 638          */
 639
 640       if (ri >= solv->learntrules)
 641         {
 642           /* conflict with a learnt rule */
 643           /* can happen when packages cannot be installed for
 644            * multiple reasons. */
 645           /* we disable the learnt rule in this case */
 646           disablerule(solv, r);
 647           continue;
 648         }
 649
 650         /*
 651          * find the decision which is the "opposite" of the rule
 652          */
 653
 654       for (i = 0; i < solv->decisionq.count; i++)
 655         if (solv->decisionq.elements[i] == -v)
 656           break;
 657       assert(i < solv->decisionq.count);         /* assert that we found it */
 658
 659         /*
 660          * conflict with system solvable ?
 661          */
 662
 663       if (v == -SYSTEMSOLVABLE) {
 664         /* conflict with system solvable */
 665         queue_push(&solv->problems, solv->learnt_pool.count);
 666         queue_push(&solv->learnt_pool, ri);
 667         queue_push(&solv->learnt_pool, 0);
 668         POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "conflict with system solvable, disabling rule #%d\n", ri);
 669         if  (ri >= solv->jobrules && ri < solv->jobrules_end)
 670           v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
 671         else
 672           v = ri;
 673         queue_push(&solv->problems, v);
 674         queue_push(&solv->problems, 0);
 675         disableproblem(solv, v);
 676         continue;
 677       }
 678
 679       assert(solv->decisionq_why.elements[i] > 0);
 680
 681         /*
 682          * conflict with an rpm rule ?
 683          */
 684
 685       if (solv->decisionq_why.elements[i] < solv->rpmrules_end)
 686         {
 687           /* conflict with rpm rule assertion */
 688           queue_push(&solv->problems, solv->learnt_pool.count);
 689           queue_push(&solv->learnt_pool, ri);
 690           queue_push(&solv->learnt_pool, solv->decisionq_why.elements[i]);
 691           queue_push(&solv->learnt_pool, 0);
 692           assert(v > 0 || v == -SYSTEMSOLVABLE);
 693           POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "conflict with rpm rule, disabling rule #%d\n", ri);
 694           if (ri >= solv->jobrules && ri < solv->jobrules_end)
 695             v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
 696           else
 697             v = ri;
 698           queue_push(&solv->problems, v);
 699           queue_push(&solv->problems, 0);
 700           disableproblem(solv, v);
 701           continue;
 702         }
 703
 704         /*
 705          * conflict with another job or update/feature rule
 706          */
 707
 708       /* record proof */
 709       queue_push(&solv->problems, solv->learnt_pool.count);
 710       queue_push(&solv->learnt_pool, ri);
 711       queue_push(&solv->learnt_pool, solv->decisionq_why.elements[i]);
 712       queue_push(&solv->learnt_pool, 0);
 713
 714       POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "conflicting update/job assertions over literal %d\n", vv);
 715
 716         /*
 717          * push all of our rules (can only be feature or job rules)
 718          * asserting this literal on the problem stack
 719          */
 720
 721       for (i = solv->featurerules, rr = solv->rules + i; i < solv->learntrules; i++, rr++)
 722         {
 723           if (rr->d < 0                          /* disabled */
 724               || rr->w2)                         /*  or no assertion */
 725             continue;
 726           if (rr->p != vv                        /* not affecting the literal */
 727               && rr->p != -vv)
 728             continue;
 729           if (MAPTST(&solv->weakrulemap, i))     /* weak: silently ignore */
 730             continue;
 731
 732           POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, " - disabling rule #%d\n", i);
 733
 734           solver_printruleclass(solv, SAT_DEBUG_UNSOLVABLE, solv->rules + i);
 735
 736           v = i;
 737             /* is is a job rule ? */
 738           if (i >= solv->jobrules && i < solv->jobrules_end)
 739             v = -(solv->ruletojob.elements[i - solv->jobrules] + 1);
 740
 741           queue_push(&solv->problems, v);
 742           disableproblem(solv, v);
 743         }
 744       queue_push(&solv->problems, 0);
 745
 746        /*
 747         * start over
 748         * (back up from decisions)
 749         */
 750       while (solv->decisionq.count > decisionstart)
 751         {
 752           v = solv->decisionq.elements[--solv->decisionq.count];
 753           --solv->decisionq_why.count;
 754           vv = v > 0 ? v : -v;
 755           solv->decisionmap[vv] = 0;
 756         }
 757       ii = -1; /* restarts loop at 0 */
 758     }
 759
 760     /*
 761      * phase 2: now do the weak assertions
 762      */
 763   for (ii = 0; ii < solv->ruleassertions.count; ii++)
 764     {
 765       ri = solv->ruleassertions.elements[ii];
 766       r = solv->rules + ri;
 767       if (r->d < 0 || r->w2)                     /* disabled or no assertion */
 768         continue;
 769       if (ri >= solv->learntrules || !MAPTST(&solv->weakrulemap, ri))       /* skip non-weak */
 770         continue;
 771       v = r->p;
 772       vv = v > 0 ? v : -v;
 773         /*
 774          * decide !
 775          * (if not yet decided)
 776          */
 777       if (!solv->decisionmap[vv])
 778         {
 779           queue_push(&solv->decisionq, v);
 780           queue_push(&solv->decisionq_why, r - solv->rules);
 781           solv->decisionmap[vv] = v > 0 ? 1 : -1;
 782           IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
 783             {
 784               Solvable *s = solv->pool->solvables + vv;
 785               if (v < 0)
 786                 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "conflicting %s (weak assertion)\n", solvable2str(solv->pool, s));
 787               else
 788                 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "installing  %s (weak assertion)\n", solvable2str(solv->pool, s));
 789             }
 790           continue;
 791         }
 792         /*
 793          * previously decided, sane ?
 794          */
 795       if (v > 0 && solv->decisionmap[vv] > 0)
 796         continue;
 797       if (v < 0 && solv->decisionmap[vv] < 0)
 798         continue;
 799
 800       POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "assertion conflict, but I am weak, disabling ");
 801       solver_printrule(solv, SAT_DEBUG_UNSOLVABLE, r);
 802
 803       if (ri >= solv->jobrules && ri < solv->jobrules_end)
 804         v = -(solv->ruletojob.elements[ri - solv->jobrules] + 1);
 805       else
 806         v = ri;
 807       disableproblem(solv, v);
 808       if (v < 0)
 809         reenablepolicyrules(solv, solv->job, -(v + 1));
 810     }
 811
 812   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- makeruledecisions end; size decisionq: %d -----\n",solv->decisionq.count);
 813 }
 814
 815
 816 /*-------------------------------------------------------------------
 817  * enable/disable learnt rules
 818  *
 819  * we have enabled or disabled some of our rules. We now reenable all
 820  * of our learnt rules except the ones that were learnt from rules that
 821  * are now disabled.
 822  */
 823 static void
 824 enabledisablelearntrules(Solver *solv)
 825 {
 826   Pool *pool = solv->pool;
 827   Rule *r;
 828   Id why, *whyp;
 829   int i;
 830
 831   POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "enabledisablelearntrules called\n");
 832   for (i = solv->learntrules, r = solv->rules + i; i < solv->nrules; i++, r++)
 833     {
 834       whyp = solv->learnt_pool.elements + solv->learnt_why.elements[i - solv->learntrules];
 835       while ((why = *whyp++) != 0)
 836         {
 837           assert(why > 0 && why < i);
 838           if (solv->rules[why].d < 0)
 839             break;
 840         }
 841       /* why != 0: we found a disabled rule, disable the learnt rule */
 842       if (why && r->d >= 0)
 843         {
 844           IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
 845             {
 846               POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "disabling ");
 847               solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
 848             }
 849           disablerule(solv, r);
 850         }
 851       else if (!why && r->d < 0)
 852         {
 853           IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
 854             {
 855               POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "re-enabling ");
 856               solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
 857             }
 858           enablerule(solv, r);
 859         }
 860     }
 861 }
 862
 863
 864 /*-------------------------------------------------------------------
 865  * enable weak rules
 866  *
 867  * Enable all rules, except learnt rules, which are
 868  * - disabled and weak (set in weakrulemap)
 869  *
 870  */
 871
 872 static void
 873 enableweakrules(Solver *solv)
 874 {
 875   int i;
 876   Rule *r;
 877
 878   for (i = 1, r = solv->rules + i; i < solv->learntrules; i++, r++)
 879     {
 880       if (r->d >= 0) /* already enabled? */
 881         continue;
 882       if (!MAPTST(&solv->weakrulemap, i))
 883         continue;
 884       enablerule(solv, r);
 885     }
 886 }
 887
 888
 889 /*-------------------------------------------------------------------
 890  * policy rule enabling/disabling
 891  *
 892  * we need to disable policy rules that conflict with our job list, and
 893  * also reenable such rules with the job was changed due to solution generation
 894  *
 895  */
 896
 897 static inline void
 898 disableinfarchrule(Solver *solv, Id name)
 899 {
 900   Pool *pool = solv->pool;
 901   Rule *r;
 902   int i;
 903   for (i = solv->infarchrules, r = solv->rules + i; i < solv->infarchrules_end; i++, r++)
 904     {
 905       if (r->p < 0 && r->d >= 0 && pool->solvables[-r->p].name == name)
 906         disablerule(solv, r);
 907     }
 908 }
 909
 910 static inline void
 911 reenableinfarchrule(Solver *solv, Id name)
 912 {
 913   Pool *pool = solv->pool;
 914   Rule *r;
 915   int i;
 916   for (i = solv->infarchrules, r = solv->rules + i; i < solv->infarchrules_end; i++, r++)
 917     {
 918       if (r->p < 0 && r->d < 0 && pool->solvables[-r->p].name == name)
 919         {
 920           enablerule(solv, r);
 921           IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
 922             {
 923               POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
 924               solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
 925             }
 926         }
 927     }
 928 }
 929
 930 static inline void
 931 disableduprule(Solver *solv, Id name)
 932 {
 933   Pool *pool = solv->pool;
 934   Rule *r;
 935   int i;
 936   for (i = solv->duprules, r = solv->rules + i; i < solv->duprules_end; i++, r++)
 937     {
 938       if (r->p < 0 && r->d >= 0 && pool->solvables[-r->p].name == name)
 939         disablerule(solv, r);
 940     }
 941 }
 942
 943 static inline void
 944 reenableduprule(Solver *solv, Id name)
 945 {
 946   Pool *pool = solv->pool;
 947   Rule *r;
 948   int i;
 949   for (i = solv->duprules, r = solv->rules + i; i < solv->duprules_end; i++, r++)
 950     {
 951       if (r->p < 0 && r->d < 0 && pool->solvables[-r->p].name == name)
 952         {
 953           enablerule(solv, r);
 954           IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
 955             {
 956               POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
 957               solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
 958             }
 959         }
 960     }
 961 }
 962
 963 static inline void
 964 disableupdaterule(Solver *solv, Id p)
 965 {
 966   Rule *r;
 967
 968   MAPSET(&solv->noupdate, p - solv->installed->start);
 969   r = solv->rules + solv->updaterules + (p - solv->installed->start);
 970   if (r->p && r->d >= 0)
 971     disablerule(solv, r);
 972   r = solv->rules + solv->featurerules + (p - solv->installed->start);
 973   if (r->p && r->d >= 0)
 974     disablerule(solv, r);
 975 }
 976
 977 static inline void
 978 reenableupdaterule(Solver *solv, Id p)
 979 {
 980   Pool *pool = solv->pool;
 981   Rule *r;
 982
 983   MAPCLR(&solv->noupdate, p - solv->installed->start);
 984   r = solv->rules + solv->updaterules + (p - solv->installed->start);
 985   if (r->p)
 986     {
 987       if (r->d >= 0)
 988         return;
 989       enablerule(solv, r);
 990       IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
 991         {
 992           POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
 993           solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
 994         }
 995       return;
 996     }
 997   r = solv->rules + solv->featurerules + (p - solv->installed->start);
 998   if (r->p && r->d < 0)
 999     {
1000       enablerule(solv, r);
1001       IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
1002         {
1003           POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
1004           solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
1005         }
1006     }
1007 }
1008
1009 #define DISABLE_UPDATE  1
1010 #define DISABLE_INFARCH 2
1011 #define DISABLE_DUP     3
1012
1013 static void
1014 jobtodisablelist(Solver *solv, Id how, Id what, Queue *q)
1015 {
1016   Pool *pool = solv->pool;
1017   Id select, p, pp;
1018   Repo *installed;
1019   Solvable *s;
1020   int i;
1021
1022   installed = solv->installed;
1023   select = how & SOLVER_SELECTMASK;
1024   switch (how & SOLVER_JOBMASK)
1025     {
1026     case SOLVER_INSTALL:
1027       if ((select == SOLVER_SOLVABLE_NAME || select == SOLVER_SOLVABLE_PROVIDES) && solv->infarchrules != solv->infarchrules_end && ISRELDEP(what))
1028         {
1029           Reldep *rd = GETRELDEP(pool, what);
1030           if (rd->flags == REL_ARCH)
1031             {
1032               int qcnt = q->count;
1033               FOR_JOB_SELECT(p, pp, select, what)
1034                 {
1035                   s = pool->solvables + p;
1036                   /* unify names */
1037                   for (i = qcnt; i < q->count; i += 2)
1038                     if (q->elements[i + 1] == s->name)
1039                       break;
1040                   if (i < q->count)
1041                     continue;
1042                   queue_push(q, DISABLE_INFARCH);
1043                   queue_push(q, s->name);
1044                 }
1045             }
1046         }
1047       if (select != SOLVER_SOLVABLE)
1048         break;
1049       s = pool->solvables + what;
1050       if (solv->infarchrules != solv->infarchrules_end)
1051         {
1052           queue_push(q, DISABLE_INFARCH);
1053           queue_push(q, s->name);
1054         }
1055       if (solv->duprules != solv->duprules_end)
1056         {
1057           queue_push(q, DISABLE_DUP);
1058           queue_push(q, s->name);
1059         }
1060       if (!installed)
1061         return;
1062       if (solv->noobsoletes.size && MAPTST(&solv->noobsoletes, what))
1063         return;
1064       if (s->repo == installed)
1065         {
1066           queue_push(q, DISABLE_UPDATE);
1067           queue_push(q, what);
1068           return;
1069         }
1070       if (s->obsoletes)
1071         {
1072           Id obs, *obsp;
1073           obsp = s->repo->idarraydata + s->obsoletes;
1074           while ((obs = *obsp++) != 0)
1075             FOR_PROVIDES(p, pp, obs)
1076               {
1077                 Solvable *ps = pool->solvables + p;
1078                 if (ps->repo != installed)
1079                   continue;
1080                 if (!solv->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
1081                   continue;
1082                 queue_push(q, DISABLE_UPDATE);
1083                 queue_push(q, p);
1084               }
1085         }
1086       FOR_PROVIDES(p, pp, s->name)
1087         {
1088           Solvable *ps = pool->solvables + p;
1089           if (ps->repo != installed)
1090             continue;
1091           if (!solv->implicitobsoleteusesprovides && ps->name != s->name)
1092             continue;
1093           queue_push(q, DISABLE_UPDATE);
1094           queue_push(q, p);
1095         }
1096       return;
1097     case SOLVER_ERASE:
1098       if (!installed)
1099         break;
1100       FOR_JOB_SELECT(p, pp, select, what)
1101         if (pool->solvables[p].repo == installed)
1102           {
1103             queue_push(q, DISABLE_UPDATE);
1104             queue_push(q, p);
1105           }
1106       return;
1107     default:
1108       return;
1109     }
1110 }
1111
1112 /* disable all policy rules that are in conflict with our job list */
1113 static void
1114 disablepolicyrules(Solver *solv, Queue *job)
1115 {
1116   int i, j;
1117   Queue allq;
1118   Rule *r;
1119   Id lastjob = -1;
1120   Id allqbuf[128];
1121
1122   queue_init_buffer(&allq, allqbuf, sizeof(allqbuf)/sizeof(*allqbuf));
1123
1124   for (i = solv->jobrules; i < solv->jobrules_end; i++)
1125     {
1126       r = solv->rules + i;
1127       if (r->d < 0)     /* disabled? */
1128         continue;
1129       j = solv->ruletojob.elements[i - solv->jobrules];
1130       if (j == lastjob)
1131         continue;
1132       lastjob = j;
1133       jobtodisablelist(solv, job->elements[j], job->elements[j + 1], &allq);
1134     }
1135   MAPZERO(&solv->noupdate);
1136   for (i = 0; i < allq.count; i += 2)
1137     {
1138       Id type = allq.elements[i], arg = allq.elements[i + 1];
1139       switch(type)
1140         {
1141         case DISABLE_UPDATE:
1142           disableupdaterule(solv, arg);
1143           break;
1144         case DISABLE_INFARCH:
1145           disableinfarchrule(solv, arg);
1146           break;
1147         case DISABLE_DUP:
1148           disableduprule(solv, arg);
1149           break;
1150         default:
1151           break;
1152         }
1153     }
1154   queue_free(&allq);
1155 }
1156
1157 /* we just disabled job #jobidx, now reenable all policy rules that were
1158  * disabled because of this job */
1159 static void
1160 reenablepolicyrules(Solver *solv, Queue *job, int jobidx)
1161 {
1162   int i, j;
1163   Queue q, allq;
1164   Rule *r;
1165   Id lastjob = -1;
1166   Id qbuf[32], allqbuf[128];
1167
1168   queue_init_buffer(&q, qbuf, sizeof(qbuf)/sizeof(*qbuf));
1169   queue_init_buffer(&allq, allqbuf, sizeof(allqbuf)/sizeof(*allqbuf));
1170   jobtodisablelist(solv, job->elements[jobidx], job->elements[jobidx + 1], &q);
1171   if (!q.count)
1172     return;
1173   for (i = solv->jobrules; i < solv->jobrules_end; i++)
1174     {
1175       r = solv->rules + i;
1176       if (r->d < 0)     /* disabled? */
1177         continue;
1178       j = solv->ruletojob.elements[i - solv->jobrules];
1179       if (j == lastjob)
1180         continue;
1181       lastjob = j;
1182       jobtodisablelist(solv, job->elements[j], job->elements[j + 1], &allq);
1183     }
1184   for (j = 0; j < q.count; j += 2)
1185     {
1186       Id type = q.elements[j], arg = q.elements[j + 1];
1187       for (i = 0; i < allq.count; i += 2)
1188         if (allq.elements[i] == type && allq.elements[i + 1] == arg)
1189           break;
1190       if (i < allq.count)
1191         continue;       /* still disabled */
1192       switch(type)
1193         {
1194         case DISABLE_UPDATE:
1195           reenableupdaterule(solv, arg);
1196           break;
1197         case DISABLE_INFARCH:
1198           reenableinfarchrule(solv, arg);
1199           break;
1200         case DISABLE_DUP:
1201           reenableduprule(solv, arg);
1202           break;
1203         }
1204     }
1205   queue_free(&allq);
1206   queue_free(&q);
1207 }
1208
1209 /*-------------------------------------------------------------------
1210  * rule generation
1211  *
1212  */
1213
1214 /*
1215  *  special multiversion patch conflict handling:
1216  *  a patch conflict is also satisfied, if some other
1217  *  version with the same name/arch that doesn't conflict
1218  *  get's installed. The generated rule is thus:
1219  *  -patch|-cpack|opack1|opack2|...
1220  */
1221 Id
1222 makemultiversionconflict(Solver *solv, Id n, Id con)
1223 {
1224   Pool *pool = solv->pool;
1225   Solvable *s, *sn;
1226   Queue q;
1227   Id p, pp, qbuf[64];
1228
1229   sn = pool->solvables + n;
1230   queue_init_buffer(&q, qbuf, sizeof(qbuf)/sizeof(*qbuf));
1231   queue_push(&q, -n);
1232   FOR_PROVIDES(p, pp, sn->name)
1233     {
1234       s = pool->solvables + p;
1235       if (s->name != sn->name || s->arch != sn->arch)
1236         continue;
1237       if (!MAPTST(&solv->noobsoletes, p))
1238         continue;
1239       if (pool_match_nevr(pool, pool->solvables + p, con))
1240         continue;
1241       /* here we have a multiversion solvable that doesn't conflict */
1242       /* thus we're not in conflict if it is installed */
1243       queue_push(&q, p);
1244     }
1245   if (q.count == 1)
1246     return -n;  /* no other package found, generate normal conflict */
1247   return pool_queuetowhatprovides(pool, &q);
1248 }
1249
1250
1251 /*-------------------------------------------------------------------
1252  *
1253  * add (install) rules for solvable
1254  *
1255  * s: Solvable for which to add rules
1256  * m: m[s] = 1 for solvables which have rules, prevent rule duplication
1257  *
1258  * Algorithm: 'visit all nodes of a graph'. The graph nodes are
1259  *  solvables, the edges their dependencies.
1260  *  Starting from an installed solvable, this will create all rules
1261  *  representing the graph created by the solvables dependencies.
1262  *
1263  * for unfulfilled requirements, conflicts, obsoletes,....
1264  * add a negative assertion for solvables that are not installable
1265  *
1266  * It will also create rules for all solvables referenced by 's'
1267  *  i.e. descend to all providers of requirements of 's'
1268  *
1269  */
1270
1271 static void
1272 addrpmrulesforsolvable(Solver *solv, Solvable *s, Map *m)
1273 {
1274   Pool *pool = solv->pool;
1275   Repo *installed = solv->installed;
1276
1277   /* 'work' queue. keeps Ids of solvables we still have to work on.
1278      And buffer for it. */
1279   Queue workq;
1280   Id workqbuf[64];
1281
1282   int i;
1283     /* if to add rules for broken deps ('rpm -V' functionality)
1284      * 0 = yes, 1 = no
1285      */
1286   int dontfix;
1287     /* Id var and pointer for each dependency
1288      * (not used in parallel)
1289      */
1290   Id req, *reqp;
1291   Id con, *conp;
1292   Id obs, *obsp;
1293   Id rec, *recp;
1294   Id sug, *sugp;
1295     /* var and ptr for loops */
1296   Id p, pp;
1297     /* ptr to 'whatprovides' */
1298   Id *dp;
1299     /* Id for current solvable 's' */
1300   Id n;
1301
1302   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforsolvable -----\n");
1303
1304   queue_init_buffer(&workq, workqbuf, sizeof(workqbuf)/sizeof(*workqbuf));
1305   queue_push(&workq, s - pool->solvables);      /* push solvable Id to work queue */
1306
1307   /* loop until there's no more work left */
1308   while (workq.count)
1309     {
1310       /*
1311        * n: Id of solvable
1312        * s: Pointer to solvable
1313        */
1314
1315       n = queue_shift(&workq);             /* 'pop' next solvable to work on from queue */
1316       if (MAPTST(m, n))                    /* continue if already visited */
1317         continue;
1318
1319       MAPSET(m, n);                        /* mark as visited */
1320       s = pool->solvables + n;             /* s = Solvable in question */
1321
1322       dontfix = 0;
1323       if (installed                        /* Installed system available */
1324           && !solv->fixsystem              /* NOT repair errors in rpm dependency graph */
1325           && s->repo == installed)         /* solvable is installed? */
1326       {
1327         dontfix = 1;                       /* dont care about broken rpm deps */
1328       }
1329
1330       if (!dontfix
1331           && s->arch != ARCH_SRC
1332           && s->arch != ARCH_NOSRC
1333           && !pool_installable(pool, s))
1334         {
1335           POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "package %s [%d] is not installable\n", solvable2str(pool, s), (Id)(s - pool->solvables));
1336           addrule(solv, -n, 0);            /* uninstallable */
1337         }
1338
1339       /* yet another SUSE hack, sigh */
1340       if (pool->nscallback && !strncmp("product:", id2str(pool, s->name), 8))
1341         {
1342           Id buddy = pool->nscallback(pool, pool->nscallbackdata, NAMESPACE_PRODUCTBUDDY, n);
1343           if (buddy > 0 && buddy != SYSTEMSOLVABLE && buddy != n && buddy < pool->nsolvables)
1344             {
1345               addrule(solv, n, -buddy);
1346               addrule(solv, buddy, -n);
1347               if (!MAPTST(m, buddy))
1348                 queue_push(&workq, buddy);
1349             }
1350         }
1351
1352       /*-----------------------------------------
1353        * check requires of s
1354        */
1355
1356       if (s->requires)
1357         {
1358           reqp = s->repo->idarraydata + s->requires;
1359           while ((req = *reqp++) != 0)            /* go through all requires */
1360             {
1361               if (req == SOLVABLE_PREREQMARKER)   /* skip the marker */
1362                 continue;
1363
1364               /* find list of solvables providing 'req' */
1365               dp = pool_whatprovides_ptr(pool, req);
1366
1367               if (*dp == SYSTEMSOLVABLE)          /* always installed */
1368                 continue;
1369
1370               if (dontfix)
1371                 {
1372                   /* the strategy here is to not insist on dependencies
1373                    * that are already broken. so if we find one provider
1374                    * that was already installed, we know that the
1375                    * dependency was not broken before so we enforce it */
1376
1377                   /* check if any of the providers for 'req' is installed */
1378                   for (i = 0; (p = dp[i]) != 0; i++)
1379                     {
1380                       if (pool->solvables[p].repo == installed)
1381                         break;          /* provider was installed */
1382                     }
1383                   /* didn't find an installed provider: previously broken dependency */
1384                   if (!p)
1385                     {
1386                       POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "ignoring broken requires %s of installed package %s\n", dep2str(pool, req), solvable2str(pool, s));
1387                       continue;
1388                     }
1389                 }
1390
1391               if (!*dp)
1392                 {
1393                   /* nothing provides req! */
1394                   POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "package %s [%d] is not installable (%s)\n", solvable2str(pool, s), (Id)(s - pool->solvables), dep2str(pool, req));
1395                   addrule(solv, -n, 0); /* mark requestor as uninstallable */
1396                   continue;
1397                 }
1398
1399               IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION)
1400                 {
1401                   POOL_DEBUG(SAT_DEBUG_RULE_CREATION,"  %s requires %s\n", solvable2str(pool, s), dep2str(pool, req));
1402                   for (i = 0; dp[i]; i++)
1403                     POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "   provided by %s\n", solvable2str(pool, pool->solvables + dp[i]));
1404                 }
1405
1406               /* add 'requires' dependency */
1407               /* rule: (-requestor|provider1|provider2|...|providerN) */
1408               addrule(solv, -n, dp - pool->whatprovidesdata);
1409
1410               /* descend the dependency tree
1411                  push all non-visited providers on the work queue */
1412               for (; *dp; dp++)
1413                 {
1414                   if (!MAPTST(m, *dp))
1415                     queue_push(&workq, *dp);
1416                 }
1417
1418             } /* while, requirements of n */
1419
1420         } /* if, requirements */
1421
1422       /* that's all we check for src packages */
1423       if (s->arch == ARCH_SRC || s->arch == ARCH_NOSRC)
1424         continue;
1425
1426       /*-----------------------------------------
1427        * check conflicts of s
1428        */
1429
1430       if (s->conflicts)
1431         {
1432           int ispatch = 0;
1433
1434           /* we treat conflicts in patches a bit differen:
1435            * - nevr matching
1436            * - multiversion handling
1437            * XXX: we should really handle this different, looking
1438            * at the name is a bad hack
1439            */
1440           if (!strncmp("patch:", id2str(pool, s->name), 6))
1441             ispatch = 1;
1442           conp = s->repo->idarraydata + s->conflicts;
1443           /* foreach conflicts of 's' */
1444           while ((con = *conp++) != 0)
1445             {
1446               /* foreach providers of a conflict of 's' */
1447               FOR_PROVIDES(p, pp, con)
1448                 {
1449                   if (ispatch && !pool_match_nevr(pool, pool->solvables + p, con))
1450                     continue;
1451                   /* dontfix: dont care about conflicts with already installed packs */
1452                   if (dontfix && pool->solvables[p].repo == installed)
1453                     continue;
1454                   /* p == n: self conflict */
1455                   if (p == n && !solv->allowselfconflicts)
1456                     {
1457                       if (ISRELDEP(con))
1458                         {
1459                           Reldep *rd = GETRELDEP(pool, con);
1460                           if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_OTHERPROVIDERS)
1461                             continue;
1462                         }
1463                       p = 0;    /* make it a negative assertion, aka 'uninstallable' */
1464                     }
1465                   if (p && ispatch && solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p) && ISRELDEP(con))
1466                     {
1467                       /* our patch conflicts with a noobsoletes (aka multiversion) package */
1468                       p = -makemultiversionconflict(solv, p, con);
1469                     }
1470                  /* rule: -n|-p: either solvable _or_ provider of conflict */
1471                   addrule(solv, -n, -p);
1472                 }
1473             }
1474         }
1475
1476       /*-----------------------------------------
1477        * check obsoletes if not installed
1478        * (only installation will trigger the obsoletes in rpm)
1479        */
1480       if (!installed || pool->solvables[n].repo != installed)
1481         {                              /* not installed */
1482           int noobs = solv->noobsoletes.size && MAPTST(&solv->noobsoletes, n);
1483           if (s->obsoletes && !noobs)
1484             {
1485               obsp = s->repo->idarraydata + s->obsoletes;
1486               /* foreach obsoletes */
1487               while ((obs = *obsp++) != 0)
1488                 {
1489                   /* foreach provider of an obsoletes of 's' */
1490                   FOR_PROVIDES(p, pp, obs)
1491                     {
1492                       if (!solv->obsoleteusesprovides /* obsoletes are matched names, not provides */
1493                           && !pool_match_nevr(pool, pool->solvables + p, obs))
1494                         continue;
1495                       addrule(solv, -n, -p);
1496                     }
1497                 }
1498             }
1499           FOR_PROVIDES(p, pp, s->name)
1500             {
1501               Solvable *ps = pool->solvables + p;
1502               /* we still obsolete packages with same nevra, like rpm does */
1503               /* (actually, rpm mixes those packages. yuck...) */
1504               if (noobs && (s->name != ps->name || s->evr != ps->evr || s->arch != ps->arch))
1505                 continue;
1506               if (!solv->implicitobsoleteusesprovides && s->name != ps->name)
1507                 continue;
1508               addrule(solv, -n, -p);
1509             }
1510         }
1511
1512       /*-----------------------------------------
1513        * add recommends to the work queue
1514        */
1515       if (s->recommends)
1516         {
1517           recp = s->repo->idarraydata + s->recommends;
1518           while ((rec = *recp++) != 0)
1519             {
1520               FOR_PROVIDES(p, pp, rec)
1521                 if (!MAPTST(m, p))
1522                   queue_push(&workq, p);
1523             }
1524         }
1525       if (s->suggests)
1526         {
1527           sugp = s->repo->idarraydata + s->suggests;
1528           while ((sug = *sugp++) != 0)
1529             {
1530               FOR_PROVIDES(p, pp, sug)
1531                 if (!MAPTST(m, p))
1532                   queue_push(&workq, p);
1533             }
1534         }
1535     }
1536   queue_free(&workq);
1537   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforsolvable end -----\n");
1538 }
1539
1540
1541 /*-------------------------------------------------------------------
1542  *
1543  * Add package rules for weak rules
1544  *
1545  * m: visited solvables
1546  */
1547
1548 static void
1549 addrpmrulesforweak(Solver *solv, Map *m)
1550 {
1551   Pool *pool = solv->pool;
1552   Solvable *s;
1553   Id sup, *supp;
1554   int i, n;
1555
1556   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforweak -----\n");
1557     /* foreach solvable in pool */
1558   for (i = n = 1; n < pool->nsolvables; i++, n++)
1559     {
1560       if (i == pool->nsolvables)                 /* wrap i */
1561         i = 1;
1562       if (MAPTST(m, i))                          /* been there */
1563         continue;
1564
1565       s = pool->solvables + i;
1566       if (!pool_installable(pool, s))            /* only look at installable ones */
1567         continue;
1568
1569       sup = 0;
1570       if (s->supplements)
1571         {
1572           /* find possible supplements */
1573           supp = s->repo->idarraydata + s->supplements;
1574           while ((sup = *supp++) != ID_NULL)
1575             if (dep_possible(solv, sup, m))
1576               break;
1577         }
1578
1579         /* if nothing found, check for enhances */
1580       if (!sup && s->enhances)
1581         {
1582           supp = s->repo->idarraydata + s->enhances;
1583           while ((sup = *supp++) != ID_NULL)
1584             if (dep_possible(solv, sup, m))
1585               break;
1586         }
1587         /* if nothing found, goto next solvables */
1588       if (!sup)
1589         continue;
1590       addrpmrulesforsolvable(solv, s, m);
1591       n = 0;
1592     }
1593   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforweak end -----\n");
1594 }
1595
1596
1597 /*-------------------------------------------------------------------
1598  *
1599  * add package rules for possible updates
1600  *
1601  * s: solvable
1602  * m: map of already visited solvables
1603  * allow_all: 0 = dont allow downgrades, 1 = allow all candidates
1604  */
1605
1606 static void
1607 addrpmrulesforupdaters(Solver *solv, Solvable *s, Map *m, int allow_all)
1608 {
1609   Pool *pool = solv->pool;
1610   int i;
1611     /* queue and buffer for it */
1612   Queue qs;
1613   Id qsbuf[64];
1614
1615   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforupdaters -----\n");
1616
1617   queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
1618     /* find update candidates for 's' */
1619   policy_findupdatepackages(solv, s, &qs, allow_all);
1620     /* add rule for 's' if not already done */
1621   if (!MAPTST(m, s - pool->solvables))
1622     addrpmrulesforsolvable(solv, s, m);
1623     /* foreach update candidate, add rule if not already done */
1624   for (i = 0; i < qs.count; i++)
1625     if (!MAPTST(m, qs.elements[i]))
1626       addrpmrulesforsolvable(solv, pool->solvables + qs.elements[i], m);
1627   queue_free(&qs);
1628
1629   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforupdaters -----\n");
1630 }
1631
1632 static Id
1633 finddistupgradepackages(Solver *solv, Solvable *s, Queue *qs, int allow_all)
1634 {
1635   Pool *pool = solv->pool;
1636   int i;
1637
1638   policy_findupdatepackages(solv, s, qs, allow_all);
1639   if (!qs->count)
1640     {
1641       if (allow_all)
1642         return 0;       /* orphaned, don't create feature rule */
1643       /* check if this is an orphaned package */
1644       policy_findupdatepackages(solv, s, qs, 1);
1645       if (!qs->count)
1646         return 0;       /* orphaned, don't create update rule */
1647       qs->count = 0;
1648       return -SYSTEMSOLVABLE;   /* supported but not installable */
1649     }
1650   if (allow_all)
1651     return s - pool->solvables;
1652   /* check if it is ok to keep the installed package */
1653   for (i = 0; i < qs->count; i++)
1654     {
1655       Solvable *ns = pool->solvables + qs->elements[i];
1656       if (s->evr == ns->evr && solvable_identical(s, ns))
1657         return s - pool->solvables;
1658     }
1659   /* nope, it must be some other package */
1660   return -SYSTEMSOLVABLE;
1661 }
1662
1663 /* add packages from the dup repositories to the update candidates
1664  * this isn't needed for the global dup mode as all packages are
1665  * from dup repos in that case */
1666 static void
1667 addduppackages(Solver *solv, Solvable *s, Queue *qs)
1668 {
1669   Queue dupqs;
1670   Id p, dupqsbuf[64];
1671   int i;
1672   int oldnoupdateprovide = solv->noupdateprovide;
1673
1674   queue_init_buffer(&dupqs, dupqsbuf, sizeof(dupqsbuf)/sizeof(*dupqsbuf));
1675   solv->noupdateprovide = 1;
1676   policy_findupdatepackages(solv, s, &dupqs, 2);
1677   solv->noupdateprovide = oldnoupdateprovide;
1678   for (i = 0; i < dupqs.count; i++)
1679     {
1680       p = dupqs.elements[i];
1681       if (MAPTST(&solv->dupmap, p))
1682         queue_pushunique(qs, p);
1683     }
1684   queue_free(&dupqs);
1685 }
1686
1687 /*-------------------------------------------------------------------
1688  *
1689  * add rule for update
1690  *   (A|A1|A2|A3...)  An = update candidates for A
1691  *
1692  * s = (installed) solvable
1693  */
1694
1695 static void
1696 addupdaterule(Solver *solv, Solvable *s, int allow_all)
1697 {
1698   /* installed packages get a special upgrade allowed rule */
1699   Pool *pool = solv->pool;
1700   Id p, d;
1701   Queue qs;
1702   Id qsbuf[64];
1703
1704   POOL_DEBUG(SAT_DEBUG_SCHUBI, "-----  addupdaterule -----\n");
1705   queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
1706   p = s - pool->solvables;
1707   /* find update candidates for 's' */
1708   if (solv->distupgrade)
1709     p = finddistupgradepackages(solv, s, &qs, allow_all);
1710   else
1711     policy_findupdatepackages(solv, s, &qs, allow_all);
1712   if (!allow_all && !solv->distupgrade && solv->dupinvolvedmap.size && MAPTST(&solv->dupinvolvedmap, p))
1713     addduppackages(solv, s, &qs);
1714
1715   if (!allow_all && qs.count && solv->noobsoletes.size)
1716     {
1717       int i, j;
1718
1719       d = pool_queuetowhatprovides(pool, &qs);
1720       /* filter out all noobsoletes packages as they don't update */
1721       for (i = j = 0; i < qs.count; i++)
1722         {
1723           if (MAPTST(&solv->noobsoletes, qs.elements[i]))
1724             {
1725               /* it's ok if they have same nevra */
1726               Solvable *ps = pool->solvables + qs.elements[i];
1727               if (ps->name != s->name || ps->evr != s->evr || ps->arch != s->arch)
1728                 continue;
1729             }
1730           qs.elements[j++] = qs.elements[i];
1731         }
1732       if (j == 0 && p == -SYSTEMSOLVABLE && solv->distupgrade)
1733         {
1734           queue_push(&solv->orphaned, s - pool->solvables);     /* treat as orphaned */
1735           j = qs.count;
1736         }
1737       if (j < qs.count)
1738         {
1739           if (d && solv->updatesystem && solv->installed && s->repo == solv->installed)
1740             {
1741               if (!solv->multiversionupdaters)
1742                 solv->multiversionupdaters = sat_calloc(solv->installed->end - solv->installed->start, sizeof(Id));
1743               solv->multiversionupdaters[s - pool->solvables - solv->installed->start] = d;
1744             }
1745           qs.count = j;
1746         }
1747     }
1748   if (qs.count && p == -SYSTEMSOLVABLE)
1749     p = queue_shift(&qs);
1750   d = qs.count ? pool_queuetowhatprovides(pool, &qs) : 0;
1751   queue_free(&qs);
1752   addrule(solv, p, d);  /* allow update of s */
1753   POOL_DEBUG(SAT_DEBUG_SCHUBI, "-----  addupdaterule end -----\n");
1754 }
1755
1756
1757 /********************************************************************/
1758 /* watches */
1759
1760
1761 /*-------------------------------------------------------------------
1762  * makewatches
1763  *
1764  * initial setup for all watches
1765  */
1766
1767 static void
1768 makewatches(Solver *solv)
1769 {
1770   Rule *r;
1771   int i;
1772   int nsolvables = solv->pool->nsolvables;
1773
1774   sat_free(solv->watches);
1775                                        /* lower half for removals, upper half for installs */
1776   solv->watches = sat_calloc(2 * nsolvables, sizeof(Id));
1777 #if 1
1778   /* do it reverse so rpm rules get triggered first (XXX: obsolete?) */
1779   for (i = 1, r = solv->rules + solv->nrules - 1; i < solv->nrules; i++, r--)
1780 #else
1781   for (i = 1, r = solv->rules + 1; i < solv->nrules; i++, r++)
1782 #endif
1783     {
1784       if (!r->w2)               /* assertions do not need watches */
1785         continue;
1786
1787       /* see addwatches_rule(solv, r) */
1788       r->n1 = solv->watches[nsolvables + r->w1];
1789       solv->watches[nsolvables + r->w1] = r - solv->rules;
1790
1791       r->n2 = solv->watches[nsolvables + r->w2];
1792       solv->watches[nsolvables + r->w2] = r - solv->rules;
1793     }
1794 }
1795
1796
1797 /*-------------------------------------------------------------------
1798  *
1799  * add watches (for rule)
1800  * sets up watches for a single rule
1801  *
1802  * see also makewatches()
1803  */
1804
1805 static inline void
1806 addwatches_rule(Solver *solv, Rule *r)
1807 {
1808   int nsolvables = solv->pool->nsolvables;
1809
1810   r->n1 = solv->watches[nsolvables + r->w1];
1811   solv->watches[nsolvables + r->w1] = r - solv->rules;
1812
1813   r->n2 = solv->watches[nsolvables + r->w2];
1814   solv->watches[nsolvables + r->w2] = r - solv->rules;
1815 }
1816
1817
1818 /********************************************************************/
1819 /*
1820  * rule propagation
1821  */
1822
1823
1824 /* shortcuts to check if a literal (positive or negative) assignment
1825  * evaluates to 'true' or 'false'
1826  */
1827 #define DECISIONMAP_TRUE(p) ((p) > 0 ? (decisionmap[p] > 0) : (decisionmap[-p] < 0))
1828 #define DECISIONMAP_FALSE(p) ((p) > 0 ? (decisionmap[p] < 0) : (decisionmap[-p] > 0))
1829 #define DECISIONMAP_UNDEF(p) (decisionmap[(p) > 0 ? (p) : -(p)] == 0)
1830
1831 /*-------------------------------------------------------------------
1832  *
1833  * propagate
1834  *
1835  * make decision and propagate to all rules
1836  *
1837  * Evaluate each term affected by the decision (linked through watches)
1838  * If we find unit rules we make new decisions based on them
1839  *
1840  * Everything's fixed there, it's just finding rules that are
1841  * unit.
1842  *
1843  * return : 0 = everything is OK
1844  *          rule = conflict found in this rule
1845  */
1846
1847 static Rule *
1848 propagate(Solver *solv, int level)
1849 {
1850   Pool *pool = solv->pool;
1851   Id *rp, *next_rp;           /* rule pointer, next rule pointer in linked list */
1852   Rule *r;                    /* rule */
1853   Id p, pkg, other_watch;
1854   Id *dp;
1855   Id *decisionmap = solv->decisionmap;
1856
1857   Id *watches = solv->watches + pool->nsolvables;   /* place ptr in middle */
1858
1859   POOL_DEBUG(SAT_DEBUG_PROPAGATE, "----- propagate -----\n");
1860
1861   /* foreach non-propagated decision */
1862   while (solv->propagate_index < solv->decisionq.count)
1863     {
1864         /*
1865          * 'pkg' was just decided
1866          * negate because our watches trigger if literal goes FALSE
1867          */
1868       pkg = -solv->decisionq.elements[solv->propagate_index++];
1869
1870       IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1871         {
1872           POOL_DEBUG(SAT_DEBUG_PROPAGATE, "propagate for decision %d level %d\n", -pkg, level);
1873           solver_printruleelement(solv, SAT_DEBUG_PROPAGATE, 0, -pkg);
1874         }
1875
1876       /* foreach rule where 'pkg' is now FALSE */
1877       for (rp = watches + pkg; *rp; rp = next_rp)
1878         {
1879           r = solv->rules + *rp;
1880           if (r->d < 0)
1881             {
1882               /* rule is disabled, goto next */
1883               if (pkg == r->w1)
1884                 next_rp = &r->n1;
1885               else
1886                 next_rp = &r->n2;
1887               continue;
1888             }
1889
1890           IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1891             {
1892               POOL_DEBUG(SAT_DEBUG_PROPAGATE,"  watch triggered ");
1893               solver_printrule(solv, SAT_DEBUG_PROPAGATE, r);
1894             }
1895
1896             /* 'pkg' was just decided (was set to FALSE)
1897              *
1898              *  now find other literal watch, check clause
1899              *   and advance on linked list
1900              */
1901           if (pkg == r->w1)
1902             {
1903               other_watch = r->w2;
1904               next_rp = &r->n1;
1905             }
1906           else
1907             {
1908               other_watch = r->w1;
1909               next_rp = &r->n2;
1910             }
1911
1912             /*
1913              * This term is already true (through the other literal)
1914              * so we have nothing to do
1915              */
1916           if (DECISIONMAP_TRUE(other_watch))
1917             continue;
1918
1919             /*
1920              * The other literal is FALSE or UNDEF
1921              *
1922              */
1923
1924           if (r->d)
1925             {
1926               /* Not a binary clause, try to move our watch.
1927                *
1928                * Go over all literals and find one that is
1929                *   not other_watch
1930                *   and not FALSE
1931                *
1932                * (TRUE is also ok, in that case the rule is fulfilled)
1933                */
1934               if (r->p                                /* we have a 'p' */
1935                   && r->p != other_watch              /* which is not watched */
1936                   && !DECISIONMAP_FALSE(r->p))        /* and not FALSE */
1937                 {
1938                   p = r->p;
1939                 }
1940               else                                    /* go find a 'd' to make 'true' */
1941                 {
1942                   /* foreach p in 'd'
1943                      we just iterate sequentially, doing it in another order just changes the order of decisions, not the decisions itself
1944                    */
1945                   for (dp = pool->whatprovidesdata + r->d; (p = *dp++) != 0;)
1946                     {
1947                       if (p != other_watch              /* which is not watched */
1948                           && !DECISIONMAP_FALSE(p))     /* and not FALSE */
1949                         break;
1950                     }
1951                 }
1952
1953               if (p)
1954                 {
1955                   /*
1956                    * if we found some p that is UNDEF or TRUE, move
1957                    * watch to it
1958                    */
1959                   IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1960                     {
1961                       if (p > 0)
1962                         POOL_DEBUG(SAT_DEBUG_PROPAGATE, "    -> move w%d to %s\n", (pkg == r->w1 ? 1 : 2), solvable2str(pool, pool->solvables + p));
1963                       else
1964                         POOL_DEBUG(SAT_DEBUG_PROPAGATE,"    -> move w%d to !%s\n", (pkg == r->w1 ? 1 : 2), solvable2str(pool, pool->solvables - p));
1965                     }
1966
1967                   *rp = *next_rp;
1968                   next_rp = rp;
1969
1970                   if (pkg == r->w1)
1971                     {
1972                       r->w1 = p;
1973                       r->n1 = watches[p];
1974                     }
1975                   else
1976                     {
1977                       r->w2 = p;
1978                       r->n2 = watches[p];
1979                     }
1980                   watches[p] = r - solv->rules;
1981                   continue;
1982                 }
1983               /* search failed, thus all unwatched literals are FALSE */
1984
1985             } /* not binary */
1986
1987             /*
1988              * unit clause found, set literal other_watch to TRUE
1989              */
1990
1991           if (DECISIONMAP_FALSE(other_watch))      /* check if literal is FALSE */
1992             return r;                              /* eek, a conflict! */
1993
1994           IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
1995             {
1996               POOL_DEBUG(SAT_DEBUG_PROPAGATE, "   unit ");
1997               solver_printrule(solv, SAT_DEBUG_PROPAGATE, r);
1998             }
1999
2000           if (other_watch > 0)
2001             decisionmap[other_watch] = level;    /* install! */
2002           else
2003             decisionmap[-other_watch] = -level;  /* remove! */
2004
2005           queue_push(&solv->decisionq, other_watch);
2006           queue_push(&solv->decisionq_why, r - solv->rules);
2007
2008           IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
2009             {
2010               Solvable *s = pool->solvables + (other_watch > 0 ? other_watch : -other_watch);
2011               if (other_watch > 0)
2012                 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "    -> decided to install %s\n", solvable2str(pool, s));
2013               else
2014                 POOL_DEBUG(SAT_DEBUG_PROPAGATE, "    -> decided to conflict %s\n", solvable2str(pool, s));
2015             }
2016
2017         } /* foreach rule involving 'pkg' */
2018
2019     } /* while we have non-decided decisions */
2020
2021   POOL_DEBUG(SAT_DEBUG_PROPAGATE, "----- propagate end-----\n");
2022
2023   return 0;     /* all is well */
2024 }
2025
2026
2027 /********************************************************************/
2028 /* Analysis */
2029
2030 /*-------------------------------------------------------------------
2031  *
2032  * analyze
2033  *   and learn
2034  */
2035
2036 static int
2037 analyze(Solver *solv, int level, Rule *c, int *pr, int *dr, int *whyp)
2038 {
2039   Pool *pool = solv->pool;
2040   Queue r;
2041   int rlevel = 1;
2042   Map seen;             /* global? */
2043   Id d, v, vv, *dp, why;
2044   int l, i, idx;
2045   int num = 0, l1num = 0;
2046   int learnt_why = solv->learnt_pool.count;
2047   Id *decisionmap = solv->decisionmap;
2048
2049   queue_init(&r);
2050
2051   POOL_DEBUG(SAT_DEBUG_ANALYZE, "ANALYZE at %d ----------------------\n", level);
2052   map_init(&seen, pool->nsolvables);
2053   idx = solv->decisionq.count;
2054   for (;;)
2055     {
2056       IF_POOLDEBUG (SAT_DEBUG_ANALYZE)
2057         solver_printruleclass(solv, SAT_DEBUG_ANALYZE, c);
2058       queue_push(&solv->learnt_pool, c - solv->rules);
2059       d = c->d < 0 ? -c->d - 1 : c->d;
2060       dp = d ? pool->whatprovidesdata + d : 0;
2061       /* go through all literals of the rule */
2062       for (i = -1; ; i++)
2063         {
2064           if (i == -1)
2065             v = c->p;
2066           else if (d == 0)
2067             v = i ? 0 : c->w2;
2068           else
2069             v = *dp++;
2070           if (v == 0)
2071             break;
2072
2073           if (DECISIONMAP_TRUE(v))      /* the one true literal */
2074             continue;
2075           vv = v > 0 ? v : -v;
2076           if (MAPTST(&seen, vv))
2077             continue;
2078           l = solv->decisionmap[vv];
2079           if (l < 0)
2080             l = -l;
2081           MAPSET(&seen, vv);
2082           if (l == 1)
2083             l1num++;                    /* need to do this one in level1 pass */
2084           else if (l == level)
2085             num++;                      /* need to do this one as well */
2086           else
2087             {
2088               queue_push(&r, v);        /* not level1 or conflict level, add to new rule */
2089               if (l > rlevel)
2090                 rlevel = l;
2091             }
2092         }
2093 l1retry:
2094       if (!num && !--l1num)
2095         break;  /* all level 1 literals done */
2096       for (;;)
2097         {
2098           assert(idx > 0);
2099           v = solv->decisionq.elements[--idx];
2100           vv = v > 0 ? v : -v;
2101           if (MAPTST(&seen, vv))
2102             break;
2103         }
2104       MAPCLR(&seen, vv);
2105       if (num && --num == 0)
2106         {
2107           *pr = -v;     /* so that v doesn't get lost */
2108           if (!l1num)
2109             break;
2110           POOL_DEBUG(SAT_DEBUG_ANALYZE, "got %d involved level 1 decisions\n", l1num);
2111           for (i = 0; i < r.count; i++)
2112             {
2113               v = r.elements[i];
2114               MAPCLR(&seen, v > 0 ? v : -v);
2115             }
2116           /* only level 1 marks left */
2117           l1num++;
2118           goto l1retry;
2119         }
2120       why = solv->decisionq_why.elements[idx];
2121       if (why <= 0)     /* just in case, maybe for SYSTEMSOLVABLE */
2122         goto l1retry;
2123       c = solv->rules + why;
2124     }
2125   map_free(&seen);
2126
2127   if (r.count == 0)
2128     *dr = 0;
2129   else if (r.count == 1 && r.elements[0] < 0)
2130     *dr = r.elements[0];
2131   else
2132     *dr = pool_queuetowhatprovides(pool, &r);
2133   IF_POOLDEBUG (SAT_DEBUG_ANALYZE)
2134     {
2135       POOL_DEBUG(SAT_DEBUG_ANALYZE, "learned rule for level %d (am %d)\n", rlevel, level);
2136       solver_printruleelement(solv, SAT_DEBUG_ANALYZE, 0, *pr);
2137       for (i = 0; i < r.count; i++)
2138         solver_printruleelement(solv, SAT_DEBUG_ANALYZE, 0, r.elements[i]);
2139     }
2140   /* push end marker on learnt reasons stack */
2141   queue_push(&solv->learnt_pool, 0);
2142   if (whyp)
2143     *whyp = learnt_why;
2144   solv->stats_learned++;
2145   return rlevel;
2146 }
2147
2148
2149 /*-------------------------------------------------------------------
2150  *
2151  * reset_solver
2152  *
2153  * reset the solver decisions to right after the rpm rules.
2154  * called after rules have been enabled/disabled
2155  */
2156
2157 static void
2158 reset_solver(Solver *solv)
2159 {
2160   Pool *pool = solv->pool;
2161   int i;
2162   Id v;
2163
2164   /* rewind decisions to direct rpm rule assertions */
2165   for (i = solv->decisionq.count - 1; i >= solv->directdecisions; i--)
2166     {
2167       v = solv->decisionq.elements[i];
2168       solv->decisionmap[v > 0 ? v : -v] = 0;
2169     }
2170
2171   POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "decisions done reduced from %d to %d\n", solv->decisionq.count, solv->directdecisions);
2172
2173   solv->decisionq_why.count = solv->directdecisions;
2174   solv->decisionq.count = solv->directdecisions;
2175   solv->recommends_index = -1;
2176   solv->propagate_index = 0;
2177
2178   /* adapt learnt rule status to new set of enabled/disabled rules */
2179   enabledisablelearntrules(solv);
2180
2181   /* redo all job/update decisions */
2182   makeruledecisions(solv);
2183   POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "decisions so far: %d\n", solv->decisionq.count);
2184 }
2185
2186
2187 /*-------------------------------------------------------------------
2188  *
2189  * analyze_unsolvable_rule
2190  */
2191
2192 static void
2193 analyze_unsolvable_rule(Solver *solv, Rule *r, Id *lastweakp)
2194 {
2195   Pool *pool = solv->pool;
2196   int i;
2197   Id why = r - solv->rules;
2198
2199   IF_POOLDEBUG (SAT_DEBUG_UNSOLVABLE)
2200     solver_printruleclass(solv, SAT_DEBUG_UNSOLVABLE, r);
2201   if (solv->learntrules && why >= solv->learntrules)
2202     {
2203       for (i = solv->learnt_why.elements[why - solv->learntrules]; solv->learnt_pool.elements[i]; i++)
2204         if (solv->learnt_pool.elements[i] > 0)
2205           analyze_unsolvable_rule(solv, solv->rules + solv->learnt_pool.elements[i], lastweakp);
2206       return;
2207     }
2208   if (MAPTST(&solv->weakrulemap, why))
2209     if (!*lastweakp || why > *lastweakp)
2210       *lastweakp = why;
2211   /* do not add rpm rules to problem */
2212   if (why < solv->rpmrules_end)
2213     return;
2214   /* turn rule into problem */
2215   if (why >= solv->jobrules && why < solv->jobrules_end)
2216     why = -(solv->ruletojob.elements[why - solv->jobrules] + 1);
2217   /* normalize dup/infarch rules */
2218   if (why > solv->infarchrules && why < solv->infarchrules_end)
2219     {
2220       Id name = pool->solvables[-solv->rules[why].p].name;
2221       while (why > solv->infarchrules && pool->solvables[-solv->rules[why - 1].p].name == name)
2222         why--;
2223     }
2224   if (why > solv->duprules && why < solv->duprules_end)
2225     {
2226       Id name = pool->solvables[-solv->rules[why].p].name;
2227       while (why > solv->duprules && pool->solvables[-solv->rules[why - 1].p].name == name)
2228         why--;
2229     }
2230
2231   /* return if problem already countains our rule */
2232   if (solv->problems.count)
2233     {
2234       for (i = solv->problems.count - 1; i >= 0; i--)
2235         if (solv->problems.elements[i] == 0)    /* end of last problem reached? */
2236           break;
2237         else if (solv->problems.elements[i] == why)
2238           return;
2239     }
2240   queue_push(&solv->problems, why);
2241 }
2242
2243
2244 /*-------------------------------------------------------------------
2245  *
2246  * analyze_unsolvable
2247  *
2248  * return: 1 - disabled some rules, try again
2249  *         0 - hopeless
2250  */
2251
2252 static int
2253 analyze_unsolvable(Solver *solv, Rule *cr, int disablerules)
2254 {
2255   Pool *pool = solv->pool;
2256   Rule *r;
2257   Map seen;             /* global to speed things up? */
2258   Id d, v, vv, *dp, why;
2259   int l, i, idx;
2260   Id *decisionmap = solv->decisionmap;
2261   int oldproblemcount;
2262   int oldlearntpoolcount;
2263   Id lastweak;
2264
2265   POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "ANALYZE UNSOLVABLE ----------------------\n");
2266   solv->stats_unsolvable++;
2267   oldproblemcount = solv->problems.count;
2268   oldlearntpoolcount = solv->learnt_pool.count;
2269
2270   /* make room for proof index */
2271   /* must update it later, as analyze_unsolvable_rule would confuse
2272    * it with a rule index if we put the real value in already */
2273   queue_push(&solv->problems, 0);
2274
2275   r = cr;
2276   map_init(&seen, pool->nsolvables);
2277   queue_push(&solv->learnt_pool, r - solv->rules);
2278   lastweak = 0;
2279   analyze_unsolvable_rule(solv, r, &lastweak);
2280   d = r->d < 0 ? -r->d - 1 : r->d;
2281   dp = d ? pool->whatprovidesdata + d : 0;
2282   for (i = -1; ; i++)
2283     {
2284       if (i == -1)
2285         v = r->p;
2286       else if (d == 0)
2287         v = i ? 0 : r->w2;
2288       else
2289         v = *dp++;
2290       if (v == 0)
2291         break;
2292       if (DECISIONMAP_TRUE(v))  /* the one true literal */
2293           continue;
2294       vv = v > 0 ? v : -v;
2295       l = solv->decisionmap[vv];
2296       if (l < 0)
2297         l = -l;
2298       MAPSET(&seen, vv);
2299     }
2300   idx = solv->decisionq.count;
2301   while (idx > 0)
2302     {
2303       v = solv->decisionq.elements[--idx];
2304       vv = v > 0 ? v : -v;
2305       if (!MAPTST(&seen, vv))
2306         continue;
2307       why = solv->decisionq_why.elements[idx];
2308       assert(why > 0);
2309       queue_push(&solv->learnt_pool, why);
2310       r = solv->rules + why;
2311       analyze_unsolvable_rule(solv, r, &lastweak);
2312       d = r->d < 0 ? -r->d - 1 : r->d;
2313       dp = d ? pool->whatprovidesdata + d : 0;
2314       for (i = -1; ; i++)
2315         {
2316           if (i == -1)
2317             v = r->p;
2318           else if (d == 0)
2319             v = i ? 0 : r->w2;
2320           else
2321             v = *dp++;
2322           if (v == 0)
2323             break;
2324           if (DECISIONMAP_TRUE(v))      /* the one true literal */
2325               continue;
2326           vv = v > 0 ? v : -v;
2327           l = solv->decisionmap[vv];
2328           if (l < 0)
2329             l = -l;
2330           MAPSET(&seen, vv);
2331         }
2332     }
2333   map_free(&seen);
2334   queue_push(&solv->problems, 0);       /* mark end of this problem */
2335
2336   if (lastweak)
2337     {
2338       Id v;
2339       /* disable last weak rule */
2340       solv->problems.count = oldproblemcount;
2341       solv->learnt_pool.count = oldlearntpoolcount;
2342       if (lastweak >= solv->jobrules && lastweak < solv->jobrules_end)
2343         v = -(solv->ruletojob.elements[lastweak - solv->jobrules] + 1);
2344       else
2345         v = lastweak;
2346       POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "disabling ");
2347       solver_printruleclass(solv, SAT_DEBUG_UNSOLVABLE, solv->rules + lastweak);
2348       disableproblem(solv, v);
2349       if (v < 0)
2350         reenablepolicyrules(solv, solv->job, -(v + 1));
2351       reset_solver(solv);
2352       return 1;
2353     }
2354
2355   /* finish proof */
2356   queue_push(&solv->learnt_pool, 0);
2357   solv->problems.elements[oldproblemcount] = oldlearntpoolcount;
2358
2359   if (disablerules)
2360     {
2361       for (i = oldproblemcount + 1; i < solv->problems.count - 1; i++)
2362         disableproblem(solv, solv->problems.elements[i]);
2363       /* XXX: might want to enable all weak rules again */
2364       reset_solver(solv);
2365       return 1;
2366     }
2367   POOL_DEBUG(SAT_DEBUG_UNSOLVABLE, "UNSOLVABLE\n");
2368   return 0;
2369 }
2370
2371
2372 /********************************************************************/
2373 /* Decision revert */
2374
2375 /*-------------------------------------------------------------------
2376  *
2377  * revert
2378  * revert decision at level
2379  */
2380
2381 static void
2382 revert(Solver *solv, int level)
2383 {
2384   Pool *pool = solv->pool;
2385   Id v, vv;
2386   while (solv->decisionq.count)
2387     {
2388       v = solv->decisionq.elements[solv->decisionq.count - 1];
2389       vv = v > 0 ? v : -v;
2390       if (solv->decisionmap[vv] <= level && solv->decisionmap[vv] >= -level)
2391         break;
2392       POOL_DEBUG(SAT_DEBUG_PROPAGATE, "reverting decision %d at %d\n", v, solv->decisionmap[vv]);
2393       if (v > 0 && solv->recommendations.count && v == solv->recommendations.elements[solv->recommendations.count - 1])
2394         solv->recommendations.count--;
2395       solv->decisionmap[vv] = 0;
2396       solv->decisionq.count--;
2397       solv->decisionq_why.count--;
2398       solv->propagate_index = solv->decisionq.count;
2399     }
2400   while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] <= -level)
2401     {
2402       solv->branches.count--;
2403       while (solv->branches.count && solv->branches.elements[solv->branches.count - 1] >= 0)
2404         solv->branches.count--;
2405     }
2406   solv->recommends_index = -1;
2407 }
2408
2409
2410 /*-------------------------------------------------------------------
2411  *
2412  * watch2onhighest - put watch2 on literal with highest level
2413  */
2414
2415 static inline void
2416 watch2onhighest(Solver *solv, Rule *r)
2417 {
2418   int l, wl = 0;
2419   Id d, v, *dp;
2420
2421   d = r->d < 0 ? -r->d - 1 : r->d;
2422   if (!d)
2423     return;     /* binary rule, both watches are set */
2424   dp = solv->pool->whatprovidesdata + d;
2425   while ((v = *dp++) != 0)
2426     {
2427       l = solv->decisionmap[v < 0 ? -v : v];
2428       if (l < 0)
2429         l = -l;
2430       if (l > wl)
2431         {
2432           r->w2 = dp[-1];
2433           wl = l;
2434         }
2435     }
2436 }
2437
2438
2439 /*-------------------------------------------------------------------
2440  *
2441  * setpropagatelearn
2442  *
2443  * add free decision (solvable to install) to decisionq
2444  * increase level and propagate decision
2445  * return if no conflict.
2446  *
2447  * in conflict case, analyze conflict rule, add resulting
2448  * rule to learnt rule set, make decision from learnt
2449  * rule (always unit) and re-propagate.
2450  *
2451  * returns the new solver level or 0 if unsolvable
2452  *
2453  */
2454
2455 static int
2456 setpropagatelearn(Solver *solv, int level, Id decision, int disablerules, Id ruleid)
2457 {
2458   Pool *pool = solv->pool;
2459   Rule *r;
2460   Id p = 0, d = 0;
2461   int l, why;
2462
2463   assert(ruleid >= 0);
2464   if (decision)
2465     {
2466       level++;
2467       if (decision > 0)
2468         solv->decisionmap[decision] = level;
2469       else
2470         solv->decisionmap[-decision] = -level;
2471       queue_push(&solv->decisionq, decision);
2472       queue_push(&solv->decisionq_why, -ruleid);        /* <= 0 -> free decision */
2473     }
2474   for (;;)
2475     {
2476       r = propagate(solv, level);
2477       if (!r)
2478         break;
2479       if (level == 1)
2480         return analyze_unsolvable(solv, r, disablerules);
2481       POOL_DEBUG(SAT_DEBUG_ANALYZE, "conflict with rule #%d\n", (int)(r - solv->rules));
2482       l = analyze(solv, level, r, &p, &d, &why);        /* learnt rule in p and d */
2483       assert(l > 0 && l < level);
2484       POOL_DEBUG(SAT_DEBUG_ANALYZE, "reverting decisions (level %d -> %d)\n", level, l);
2485       level = l;
2486       revert(solv, level);
2487       r = addrule(solv, p, d);
2488       assert(r);
2489       assert(solv->learnt_why.count == (r - solv->rules) - solv->learntrules);
2490       queue_push(&solv->learnt_why, why);
2491       if (d)
2492         {
2493           /* at least 2 literals, needs watches */
2494           watch2onhighest(solv, r);
2495           addwatches_rule(solv, r);
2496         }
2497       else
2498         {
2499           /* learnt rule is an assertion */
2500           queue_push(&solv->ruleassertions, r - solv->rules);
2501         }
2502       solv->decisionmap[p > 0 ? p : -p] = p > 0 ? level : -level;
2503       queue_push(&solv->decisionq, p);
2504       queue_push(&solv->decisionq_why, r - solv->rules);
2505       IF_POOLDEBUG (SAT_DEBUG_ANALYZE)
2506         {
2507           POOL_DEBUG(SAT_DEBUG_ANALYZE, "decision: ");
2508           solver_printruleelement(solv, SAT_DEBUG_ANALYZE, 0, p);
2509           POOL_DEBUG(SAT_DEBUG_ANALYZE, "new rule: ");
2510           solver_printrule(solv, SAT_DEBUG_ANALYZE, r);
2511         }
2512     }
2513   return level;
2514 }
2515
2516
2517 /*-------------------------------------------------------------------
2518  *
2519  * select and install
2520  *
2521  * install best package from the queue. We add an extra package, inst, if
2522  * provided. See comment in weak install section.
2523  *
2524  * returns the new solver level or 0 if unsolvable
2525  *
2526  */
2527
2528 static int
2529 selectandinstall(Solver *solv, int level, Queue *dq, int disablerules, Id ruleid)
2530 {
2531   Pool *pool = solv->pool;
2532   Id p;
2533   int i;
2534
2535   if (dq->count > 1)
2536     policy_filter_unwanted(solv, dq, POLICY_MODE_CHOOSE);
2537   if (dq->count > 1)
2538     {
2539       /* XXX: didn't we already do that? */
2540       /* XXX: shouldn't we prefer installed packages? */
2541       /* XXX: move to policy.c? */
2542       /* choose the supplemented one */
2543       for (i = 0; i < dq->count; i++)
2544         if (solver_is_supplementing(solv, pool->solvables + dq->elements[i]))
2545           {
2546             dq->elements[0] = dq->elements[i];
2547             dq->count = 1;
2548             break;
2549           }
2550     }
2551   if (dq->count > 1)
2552     {
2553       /* multiple candidates, open a branch */
2554       for (i = 1; i < dq->count; i++)
2555         queue_push(&solv->branches, dq->elements[i]);
2556       queue_push(&solv->branches, -level);
2557     }
2558   p = dq->elements[0];
2559
2560   POOL_DEBUG(SAT_DEBUG_POLICY, "installing %s\n", solvable2str(pool, pool->solvables + p));
2561
2562   return setpropagatelearn(solv, level, p, disablerules, ruleid);
2563 }
2564
2565
2566 /********************************************************************/
2567 /* Main solver interface */
2568
2569
2570 /*-------------------------------------------------------------------
2571  *
2572  * solver_create
2573  * create solver structure
2574  *
2575  * pool: all available solvables
2576  * installed: installed Solvables
2577  *
2578  *
2579  * Upon solving, rules are created to flag the Solvables
2580  * of the 'installed' Repo as installed.
2581  */
2582
2583 Solver *
2584 solver_create(Pool *pool)
2585 {
2586   Solver *solv;
2587   solv = (Solver *)sat_calloc(1, sizeof(Solver));
2588   solv->pool = pool;
2589   solv->installed = pool->installed;
2590
2591   queue_init(&solv->ruletojob);
2592   queue_init(&solv->decisionq);
2593   queue_init(&solv->decisionq_why);
2594   queue_init(&solv->problems);
2595   queue_init(&solv->suggestions);
2596   queue_init(&solv->recommendations);
2597   queue_init(&solv->orphaned);
2598   queue_init(&solv->learnt_why);
2599   queue_init(&solv->learnt_pool);
2600   queue_init(&solv->branches);
2601   queue_init(&solv->covenantq);
2602   queue_init(&solv->weakruleq);
2603   queue_init(&solv->ruleassertions);
2604
2605   map_init(&solv->recommendsmap, pool->nsolvables);
2606   map_init(&solv->suggestsmap, pool->nsolvables);
2607   map_init(&solv->noupdate, solv->installed ? solv->installed->end - solv->installed->start : 0);
2608   solv->recommends_index = 0;
2609
2610   solv->decisionmap = (Id *)sat_calloc(pool->nsolvables, sizeof(Id));
2611   solv->nrules = 1;
2612   solv->rules = sat_extend_resize(solv->rules, solv->nrules, sizeof(Rule), RULES_BLOCK);
2613   memset(solv->rules, 0, sizeof(Rule));
2614
2615   return solv;
2616 }
2617
2618
2619 /*-------------------------------------------------------------------
2620  *
2621  * solver_free
2622  */
2623
2624 void
2625 solver_free(Solver *solv)
2626 {
2627   queue_free(&solv->ruletojob);
2628   queue_free(&solv->decisionq);
2629   queue_free(&solv->decisionq_why);
2630   queue_free(&solv->learnt_why);
2631   queue_free(&solv->learnt_pool);
2632   queue_free(&solv->problems);
2633   queue_free(&solv->suggestions);
2634   queue_free(&solv->recommendations);
2635   queue_free(&solv->orphaned);
2636   queue_free(&solv->branches);
2637   queue_free(&solv->covenantq);
2638   queue_free(&solv->weakruleq);
2639   queue_free(&solv->ruleassertions);
2640
2641   map_free(&solv->recommendsmap);
2642   map_free(&solv->suggestsmap);
2643   map_free(&solv->noupdate);
2644   map_free(&solv->weakrulemap);
2645   map_free(&solv->noobsoletes);
2646
2647   map_free(&solv->updatemap);
2648   map_free(&solv->dupmap);
2649   map_free(&solv->dupinvolvedmap);
2650
2651   sat_free(solv->decisionmap);
2652   sat_free(solv->rules);
2653   sat_free(solv->watches);
2654   sat_free(solv->obsoletes);
2655   sat_free(solv->obsoletes_data);
2656   sat_free(solv->multiversionupdaters);
2657   sat_free(solv);
2658 }
2659
2660
2661 /*-------------------------------------------------------------------
2662  *
2663  * run_solver
2664  *
2665  * all rules have been set up, now actually run the solver
2666  *
2667  */
2668
2669 static void
2670 run_solver(Solver *solv, int disablerules, int doweak)
2671 {
2672   Queue dq;             /* local decisionqueue */
2673   Queue dqs;            /* local decisionqueue for supplements */
2674   int systemlevel;
2675   int level, olevel;
2676   Rule *r;
2677   int i, j, n;
2678   Solvable *s;
2679   Pool *pool = solv->pool;
2680   Id p, *dp;
2681   int minimizationsteps;
2682
2683   IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION)
2684     {
2685       POOL_DEBUG (SAT_DEBUG_RULE_CREATION, "number of rules: %d\n", solv->nrules);
2686       for (i = 1; i < solv->nrules; i++)
2687         solver_printruleclass(solv, SAT_DEBUG_RULE_CREATION, solv->rules + i);
2688     }
2689
2690   POOL_DEBUG(SAT_DEBUG_STATS, "initial decisions: %d\n", solv->decisionq.count);
2691
2692   IF_POOLDEBUG (SAT_DEBUG_SCHUBI)
2693     solver_printdecisions(solv);
2694
2695   /* start SAT algorithm */
2696   level = 1;
2697   systemlevel = level + 1;
2698   POOL_DEBUG(SAT_DEBUG_STATS, "solving...\n");
2699
2700   queue_init(&dq);
2701   queue_init(&dqs);
2702
2703   /*
2704    * here's the main loop:
2705    * 1) propagate new decisions (only needed for level 1)
2706    * 2) try to keep installed packages
2707    * 3) fulfill all unresolved rules
2708    * 4) install recommended packages
2709    * 5) minimalize solution if we had choices
2710    * if we encounter a problem, we rewind to a safe level and restart
2711    * with step 1
2712    */
2713
2714   minimizationsteps = 0;
2715   for (;;)
2716     {
2717       /*
2718        * propagate
2719        */
2720
2721       if (level == 1)
2722         {
2723           POOL_DEBUG(SAT_DEBUG_PROPAGATE, "propagating (propagate_index: %d;  size decisionq: %d)...\n", solv->propagate_index, solv->decisionq.count);
2724           if ((r = propagate(solv, level)) != 0)
2725             {
2726               if (analyze_unsolvable(solv, r, disablerules))
2727                 continue;
2728               queue_free(&dq);
2729               queue_free(&dqs);
2730               return;
2731             }
2732         }
2733
2734      if (level < systemlevel)
2735         {
2736           POOL_DEBUG(SAT_DEBUG_STATS, "resolving job rules\n");
2737           for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++)
2738             {
2739               Id l;
2740               if (r->d < 0)             /* ignore disabled rules */
2741                 continue;
2742               queue_empty(&dq);
2743               FOR_RULELITERALS(l, dp, r)
2744                 {
2745                   if (l < 0)
2746                     {
2747                       if (solv->decisionmap[-l] <= 0)
2748                         break;
2749                     }
2750                   else
2751                     {
2752                       if (solv->decisionmap[l] > 0)
2753                         break;
2754                       if (solv->decisionmap[l] == 0)
2755                         queue_push(&dq, l);
2756                     }
2757                 }
2758               if (l || !dq.count)
2759                 continue;
2760               /* prune to installed if not updating */
2761               if (!solv->updatesystem && solv->installed && dq.count > 1)
2762                 {
2763                   int j, k;
2764                   for (j = k = 0; j < dq.count; j++)
2765                     {
2766                       Solvable *s = pool->solvables + dq.elements[j];
2767                       if (s->repo == solv->installed)
2768                         dq.elements[k++] = dq.elements[j];
2769                     }
2770                   if (k)
2771                     dq.count = k;
2772                 }
2773               olevel = level;
2774               level = selectandinstall(solv, level, &dq, disablerules, i);
2775               if (level == 0)
2776                 {
2777                   queue_free(&dq);
2778                   queue_free(&dqs);
2779                   return;
2780                 }
2781               if (level <= olevel)
2782                 break;
2783             }
2784           systemlevel = level + 1;
2785           if (i < solv->jobrules_end)
2786             continue;
2787         }
2788
2789
2790       /*
2791        * installed packages
2792        */
2793
2794       if (level < systemlevel && solv->installed && solv->installed->nsolvables)
2795         {
2796           Repo *installed = solv->installed;
2797           int pass;
2798
2799           /* we use two passes if we need to update packages
2800            * to create a better user experience */
2801           for (pass = solv->updatemap.size ? 0 : 1; pass < 2; pass++)
2802             {
2803               FOR_REPO_SOLVABLES(installed, i, s)
2804                 {
2805                   Rule *rr;
2806                   Id d;
2807
2808                   /* XXX: noupdate check is probably no longer needed, as all jobs should
2809                    * already be satisfied */
2810                   if (MAPTST(&solv->noupdate, i - installed->start))
2811                     continue;
2812                   if (solv->decisionmap[i] > 0)
2813                     continue;
2814                   if (!pass && solv->updatemap.size && !MAPTST(&solv->updatemap, i - installed->start))
2815                     continue;           /* updates first */
2816                   r = solv->rules + solv->updaterules + (i - installed->start);
2817                   rr = r;
2818                   if (!rr->p || rr->d < 0)      /* disabled -> look at feature rule */
2819                     rr -= solv->installed->end - solv->installed->start;
2820                   if (!rr->p)           /* identical to update rule? */
2821                     rr = r;
2822                   if (!rr->p)
2823                     continue;           /* orpaned package */
2824
2825                   queue_empty(&dq);
2826                   if (solv->decisionmap[i] < 0 || solv->updatesystem || (solv->updatemap.size && MAPTST(&solv->updatemap, i - installed->start)) || rr->p != i)
2827                     {
2828                       if (solv->noobsoletes.size && solv->multiversionupdaters
2829                              && (d = solv->multiversionupdaters[i - installed->start]) != 0)
2830                         {
2831                           /* special multiversion handling, make sure best version is chosen */
2832                           queue_push(&dq, i);
2833                           while ((p = pool->whatprovidesdata[d++]) != 0)
2834                             if (solv->decisionmap[p] >= 0)
2835                               queue_push(&dq, p);
2836                           policy_filter_unwanted(solv, &dq, POLICY_MODE_CHOOSE);
2837                           p = dq.elements[0];
2838                           if (p != i && solv->decisionmap[p] == 0)
2839                             {
2840                               rr = solv->rules + solv->featurerules + (i - solv->installed->start);
2841                               if (!rr->p)               /* update rule == feature rule? */
2842                                 rr = rr - solv->featurerules + solv->updaterules;
2843                               dq.count = 1;
2844                             }
2845                           else
2846                             dq.count = 0;
2847                         }
2848                       else
2849                         {
2850                           /* update to best package */
2851                           FOR_RULELITERALS(p, dp, rr)
2852                             {
2853                               if (solv->decisionmap[p] > 0)
2854                                 {
2855                                   dq.count = 0;         /* already fulfilled */
2856                                   break;
2857                                 }
2858                               if (!solv->decisionmap[p])
2859                                 queue_push(&dq, p);
2860                             }
2861                         }
2862                     }
2863                   /* install best version */
2864                   if (dq.count)
2865                     {
2866                       olevel = level;
2867                       level = selectandinstall(solv, level, &dq, disablerules, rr - solv->rules);
2868                       if (level == 0)
2869                         {
2870                           queue_free(&dq);
2871                           queue_free(&dqs);
2872                           return;
2873                         }
2874                       if (level <= olevel)
2875                         break;
2876                     }
2877                   /* if still undecided keep package */
2878                   if (solv->decisionmap[i] == 0)
2879                     {
2880                       olevel = level;
2881                       POOL_DEBUG(SAT_DEBUG_POLICY, "keeping %s\n", solvable2str(pool, pool->solvables + i));
2882                       level = setpropagatelearn(solv, level, i, disablerules, r - solv->rules);
2883                       if (level == 0)
2884                         {
2885                           queue_free(&dq);
2886                           queue_free(&dqs);
2887                           return;
2888                         }
2889                       if (level <= olevel)
2890                         break;
2891                     }
2892                 }
2893               if (i < installed->end)
2894                 break;
2895             }
2896           systemlevel = level + 1;
2897           if (pass < 2)
2898             continue;           /* had trouble, retry */
2899         }
2900
2901       if (level < systemlevel)
2902         systemlevel = level;
2903
2904       /*
2905        * decide
2906        */
2907
2908       POOL_DEBUG(SAT_DEBUG_POLICY, "deciding unresolved rules\n");
2909       for (i = 1, n = 1; ; i++, n++)
2910         {
2911           if (n == solv->nrules)
2912             break;
2913           if (i == solv->nrules)
2914             i = 1;
2915           r = solv->rules + i;
2916           if (r->d < 0)         /* ignore disabled rules */
2917             continue;
2918           queue_empty(&dq);
2919           if (r->d == 0)
2920             {
2921               /* binary or unary rule */
2922               /* need two positive undecided literals */
2923               if (r->p < 0 || r->w2 <= 0)
2924                 continue;
2925               if (solv->decisionmap[r->p] || solv->decisionmap[r->w2])
2926                 continue;
2927               queue_push(&dq, r->p);
2928               queue_push(&dq, r->w2);
2929             }
2930           else
2931             {
2932               /* make sure that
2933                * all negative literals are installed
2934                * no positive literal is installed
2935                * i.e. the rule is not fulfilled and we
2936                * just need to decide on the positive literals
2937                */
2938               if (r->p < 0)
2939                 {
2940                   if (solv->decisionmap[-r->p] <= 0)
2941                     continue;
2942                 }
2943               else
2944                 {
2945                   if (solv->decisionmap[r->p] > 0)
2946                     continue;
2947                   if (solv->decisionmap[r->p] == 0)
2948                     queue_push(&dq, r->p);
2949                 }
2950               dp = pool->whatprovidesdata + r->d;
2951               while ((p = *dp++) != 0)
2952                 {
2953                   if (p < 0)
2954                     {
2955                       if (solv->decisionmap[-p] <= 0)
2956                         break;
2957                     }
2958                   else
2959                     {
2960                       if (solv->decisionmap[p] > 0)
2961                         break;
2962                       if (solv->decisionmap[p] == 0)
2963                         queue_push(&dq, p);
2964                     }
2965                 }
2966               if (p)
2967                 continue;
2968             }
2969           IF_POOLDEBUG (SAT_DEBUG_PROPAGATE)
2970             {
2971               POOL_DEBUG(SAT_DEBUG_PROPAGATE, "unfulfilled ");
2972               solver_printruleclass(solv, SAT_DEBUG_PROPAGATE, r);
2973             }
2974           /* dq.count < 2 cannot happen as this means that
2975            * the rule is unit */
2976           assert(dq.count > 1);
2977
2978           olevel = level;
2979           level = selectandinstall(solv, level, &dq, disablerules, r - solv->rules);
2980           if (level == 0)
2981             {
2982               queue_free(&dq);
2983               queue_free(&dqs);
2984               return;
2985             }
2986           if (level < systemlevel)
2987             break;
2988           n = 0;
2989         } /* for(), decide */
2990
2991       if (n != solv->nrules)    /* continue if level < systemlevel */
2992         continue;
2993
2994       if (doweak)
2995         {
2996           int qcount;
2997
2998           POOL_DEBUG(SAT_DEBUG_POLICY, "installing recommended packages\n");
2999           queue_empty(&dq);     /* recommended packages */
3000           queue_empty(&dqs);    /* supplemented packages */
3001           for (i = 1; i < pool->nsolvables; i++)
3002             {
3003               if (solv->decisionmap[i] < 0)
3004                 continue;
3005               if (solv->decisionmap[i] > 0)
3006                 {
3007                   /* installed, check for recommends */
3008                   Id *recp, rec, pp, p;
3009                   s = pool->solvables + i;
3010                   if (solv->ignorealreadyrecommended && s->repo == solv->installed)
3011                     continue;
3012                   /* XXX need to special case AND ? */
3013                   if (s->recommends)
3014                     {
3015                       recp = s->repo->idarraydata + s->recommends;
3016                       while ((rec = *recp++) != 0)
3017                         {
3018                           qcount = dq.count;
3019                           FOR_PROVIDES(p, pp, rec)
3020                             {
3021                               if (solv->decisionmap[p] > 0)
3022                                 {
3023                                   dq.count = qcount;
3024                                   break;
3025                                 }
3026                               else if (solv->decisionmap[p] == 0)
3027                                 {
3028                                   queue_pushunique(&dq, p);
3029                                 }
3030                             }
3031                         }
3032                     }
3033                 }
3034               else
3035                 {
3036                   s = pool->solvables + i;
3037                   if (!s->supplements)
3038                     continue;
3039                   if (!pool_installable(pool, s))
3040                     continue;
3041                   if (!solver_is_supplementing(solv, s))
3042                     continue;
3043                   queue_push(&dqs, i);
3044                 }
3045             }
3046
3047           /* filter out all packages obsoleted by installed packages */
3048           /* this is no longer needed if we have reverse obsoletes */
3049           if ((dqs.count || dq.count) && solv->installed)
3050             {
3051               Map obsmap;
3052               Id obs, *obsp, po, ppo;
3053
3054               map_init(&obsmap, pool->nsolvables);
3055               for (p = solv->installed->start; p < solv->installed->end; p++)
3056                 {
3057                   s = pool->solvables + p;
3058                   if (s->repo != solv->installed || !s->obsoletes)
3059                     continue;
3060                   if (solv->decisionmap[p] <= 0)
3061                     continue;
3062                   if (solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p))
3063                     continue;
3064                   obsp = s->repo->idarraydata + s->obsoletes;
3065                   /* foreach obsoletes */
3066                   while ((obs = *obsp++) != 0)
3067                     FOR_PROVIDES(po, ppo, obs)
3068                       MAPSET(&obsmap, po);
3069                 }
3070               for (i = j = 0; i < dqs.count; i++)
3071                 if (!MAPTST(&obsmap, dqs.elements[i]))
3072                   dqs.elements[j++] = dqs.elements[i];
3073               dqs.count = j;
3074               for (i = j = 0; i < dq.count; i++)
3075                 if (!MAPTST(&obsmap, dq.elements[i]))
3076                   dq.elements[j++] = dq.elements[i];
3077               dq.count = j;
3078               map_free(&obsmap);
3079             }
3080
3081           /* filter out all already supplemented packages if requested */
3082           if (solv->ignorealreadyrecommended && dqs.count)
3083             {
3084               /* turn off all new packages */
3085               for (i = 0; i < solv->decisionq.count; i++)
3086                 {
3087                   p = solv->decisionq.elements[i];
3088                   if (p < 0)
3089                     continue;
3090                   s = pool->solvables + p;
3091                   if (s->repo && s->repo != solv->installed)
3092                     solv->decisionmap[p] = -solv->decisionmap[p];
3093                 }
3094               /* filter out old supplements */
3095               for (i = j = 0; i < dqs.count; i++)
3096                 {
3097                   p = dqs.elements[i];
3098                   s = pool->solvables + p;
3099                   if (!s->supplements)
3100                     continue;
3101                   if (!solver_is_supplementing(solv, s))
3102                     dqs.elements[j++] = p;
3103                 }
3104               dqs.count = j;
3105               /* undo turning off */
3106               for (i = 0; i < solv->decisionq.count; i++)
3107                 {
3108                   p = solv->decisionq.elements[i];
3109                   if (p < 0)
3110                     continue;
3111                   s = pool->solvables + p;
3112                   if (s->repo && s->repo != solv->installed)
3113                     solv->decisionmap[p] = -solv->decisionmap[p];
3114                 }
3115             }
3116
3117           /* make dq contain both recommended and supplemented pkgs */
3118           if (dqs.count)
3119             {
3120               for (i = 0; i < dqs.count; i++)
3121                 queue_pushunique(&dq, dqs.elements[i]);
3122             }
3123
3124 #if 1
3125           if (dq.count)
3126             {
3127               Map dqmap;
3128               int decisioncount = solv->decisionq.count;
3129
3130               if (dq.count == 1)
3131                 {
3132                   /* simple case, just one package. no need to choose  */
3133                   p = dq.elements[0];
3134                   if (dqs.count)
3135                     POOL_DEBUG(SAT_DEBUG_POLICY, "installing supplemented %s\n", solvable2str(pool, pool->solvables + p));
3136                   else
3137                     POOL_DEBUG(SAT_DEBUG_POLICY, "installing recommended %s\n", solvable2str(pool, pool->solvables + p));
3138                   queue_push(&solv->recommendations, p);
3139                   level = setpropagatelearn(solv, level, p, 0, 0);
3140                   continue;
3141                 }
3142
3143               /* filter and create a map of result */
3144               policy_filter_unwanted(solv, &dq, POLICY_MODE_RECOMMEND);
3145               map_init(&dqmap, pool->nsolvables);
3146               for (i = 0; i < dq.count; i++)
3147                 MAPSET(&dqmap, dq.elements[i]);
3148
3149               /* install all supplemented packages */
3150               for (i = 0; i < dqs.count; i++)
3151                 {
3152                   p = dqs.elements[i];
3153                   if (solv->decisionmap[p] || !MAPTST(&dqmap, p))
3154                     continue;
3155                   POOL_DEBUG(SAT_DEBUG_POLICY, "installing supplemented %s\n", solvable2str(pool, pool->solvables + p));
3156                   queue_push(&solv->recommendations, p);
3157                   olevel = level;
3158                   level = setpropagatelearn(solv, level, p, 0, 0);
3159                   if (level <= olevel)
3160                     break;
3161                 }
3162               if (i < dqs.count || solv->decisionq.count < decisioncount)
3163                 {
3164                   map_free(&dqmap);
3165                   continue;
3166                 }
3167
3168               /* install all recommended packages */
3169               /* more work as we want to created branches if multiple
3170                * choices are valid */
3171               for (i = 0; i < decisioncount; i++)
3172                 {
3173                   Id rec, *recp, pp;
3174                   p = solv->decisionq.elements[i];
3175                   if (p < 0)
3176                     continue;
3177                   s = pool->solvables + p;
3178                   if (!s->repo || (solv->ignorealreadyrecommended && s->repo == solv->installed))
3179                     continue;
3180                   if (!s->recommends)
3181                     continue;
3182                   recp = s->repo->idarraydata + s->recommends;
3183                   while ((rec = *recp++) != 0)
3184                     {
3185                       queue_empty(&dq);
3186                       FOR_PROVIDES(p, pp, rec)
3187                         {
3188                           if (solv->decisionmap[p] > 0)
3189                             {
3190                               dq.count = 0;
3191                               break;
3192                             }
3193                           else if (solv->decisionmap[p] == 0 && MAPTST(&dqmap, p))
3194                             queue_pushunique(&dq, p);
3195                         }
3196                       if (!dq.count)
3197                         continue;
3198                       if (dq.count > 1)
3199                         {
3200                           /* multiple candidates, open a branch */
3201                           for (i = 1; i < dq.count; i++)
3202                             queue_push(&solv->branches, dq.elements[i]);
3203                           queue_push(&solv->branches, -level);
3204                         }
3205                       p = dq.elements[0];
3206                       POOL_DEBUG(SAT_DEBUG_POLICY, "installing recommended %s\n", solvable2str(pool, pool->solvables + p));
3207                       queue_push(&solv->recommendations, p);
3208                       olevel = level;
3209                       level = setpropagatelearn(solv, level, p, 0, 0);
3210                       if (level <= olevel || solv->decisionq.count < decisioncount)
3211                         break;
3212                     }
3213                   if (rec)
3214                     break;      /* had a problem above, quit loop */
3215                 }
3216               map_free(&dqmap);
3217               continue;
3218             }
3219 #else
3220           if (dq.count)
3221             {
3222               if (dq.count > 1)
3223                 policy_filter_unwanted(solv, &dq, POLICY_MODE_RECOMMEND);
3224               p = dq.elements[0];
3225               /* prefer recommended patterns (bnc#450226) */
3226               /* real fix is to minimize recommended packages as well */
3227               for (i = 0; i < dq.count; i++)
3228                 if (!strncmp(id2str(pool, pool->solvables[dq.elements[i]].name), "pattern:", 8))
3229                   {
3230                     p = dq.elements[i];
3231                     break;
3232                   }
3233               POOL_DEBUG(SAT_DEBUG_POLICY, "installing recommended %s\n", solvable2str(pool, pool->solvables + p));
3234               queue_push(&solv->recommendations, p);
3235               level = setpropagatelearn(solv, level, p, 0, 0);
3236               continue;
3237             }
3238 #endif
3239         }
3240
3241      if (solv->distupgrade && solv->installed)
3242         {
3243           int installedone = 0;
3244
3245           /* let's see if we can install some unsupported package */
3246           POOL_DEBUG(SAT_DEBUG_STATS, "deciding unsupported packages\n");
3247           for (i = 0; i < solv->orphaned.count; i++)
3248             {
3249               p = solv->orphaned.elements[i];
3250               if (solv->decisionmap[p])
3251                 continue;       /* already decided */
3252               olevel = level;
3253               if (solv->distupgrade_removeunsupported)
3254                 {
3255                   POOL_DEBUG(SAT_DEBUG_STATS, "removing unsupported %s\n", solvable2str(pool, pool->solvables + p));
3256                   level = setpropagatelearn(solv, level, -p, 0, 0);
3257                 }
3258               else
3259                 {
3260                   POOL_DEBUG(SAT_DEBUG_STATS, "keeping unsupported %s\n", solvable2str(pool, pool->solvables + p));
3261                   level = setpropagatelearn(solv, level, p, 0, 0);
3262                   installedone = 1;
3263                 }
3264               if (level < olevel)
3265                 break;
3266             }
3267           if (installedone || i < solv->orphaned.count)
3268             continue;
3269         }
3270
3271      if (solv->solution_callback)
3272         {
3273           solv->solution_callback(solv, solv->solution_callback_data);
3274           if (solv->branches.count)
3275             {
3276               int i = solv->branches.count - 1;
3277               int l = -solv->branches.elements[i];
3278               Id why;
3279
3280               for (; i > 0; i--)
3281                 if (solv->branches.elements[i - 1] < 0)
3282                   break;
3283               p = solv->branches.elements[i];
3284               POOL_DEBUG(SAT_DEBUG_STATS, "branching with %s\n", solvable2str(pool, pool->solvables + p));
3285               queue_empty(&dq);
3286               for (j = i + 1; j < solv->branches.count; j++)
3287                 queue_push(&dq, solv->branches.elements[j]);
3288               solv->branches.count = i;
3289               level = l;
3290               revert(solv, level);
3291               if (dq.count > 1)
3292                 for (j = 0; j < dq.count; j++)
3293                   queue_push(&solv->branches, dq.elements[j]);
3294               olevel = level;
3295               why = -solv->decisionq_why.elements[solv->decisionq_why.count];
3296               assert(why >= 0);
3297               level = setpropagatelearn(solv, level, p, disablerules, why);
3298               if (level == 0)
3299                 {
3300                   queue_free(&dq);
3301                   queue_free(&dqs);
3302                   return;
3303                 }
3304               continue;
3305             }
3306           /* all branches done, we're finally finished */
3307           break;
3308         }
3309
3310       /* minimization step */
3311      if (solv->branches.count)
3312         {
3313           int l = 0, lasti = -1, lastl = -1;
3314           Id why;
3315
3316           p = 0;
3317           for (i = solv->branches.count - 1; i >= 0; i--)
3318             {
3319               p = solv->branches.elements[i];
3320               if (p < 0)
3321                 l = -p;
3322               else if (p > 0 && solv->decisionmap[p] > l + 1)
3323                 {
3324                   lasti = i;
3325                   lastl = l;
3326                 }
3327             }
3328           if (lasti >= 0)
3329             {
3330               /* kill old solvable so that we do not loop */
3331               p = solv->branches.elements[lasti];
3332               solv->branches.elements[lasti] = 0;
3333               POOL_DEBUG(SAT_DEBUG_STATS, "minimizing %d -> %d with %s\n", solv->decisionmap[p], lastl, solvable2str(pool, pool->solvables + p));
3334               minimizationsteps++;
3335
3336               level = lastl;
3337               revert(solv, level);
3338               why = -solv->decisionq_why.elements[solv->decisionq_why.count];
3339               assert(why >= 0);
3340               olevel = level;
3341               level = setpropagatelearn(solv, level, p, disablerules, why);
3342               if (level == 0)
3343                 {
3344                   queue_free(&dq);
3345                   queue_free(&dqs);
3346                   return;
3347                 }
3348               continue;
3349             }
3350         }
3351       break;
3352     }
3353   POOL_DEBUG(SAT_DEBUG_STATS, "solver statistics: %d learned rules, %d unsolvable, %d minimization steps\n", solv->stats_learned, solv->stats_unsolvable, minimizationsteps);
3354
3355   POOL_DEBUG(SAT_DEBUG_STATS, "done solving.\n\n");
3356   queue_free(&dq);
3357   queue_free(&dqs);
3358 }
3359
3360
3361 /*-------------------------------------------------------------------
3362  *
3363  * refine_suggestion
3364  *
3365  * at this point, all rules that led to conflicts are disabled.
3366  * we re-enable all rules of a problem set but rule "sug", then
3367  * continue to disable more rules until there as again a solution.
3368  */
3369
3370 /* FIXME: think about conflicting assertions */
3371
3372 static void
3373 refine_suggestion(Solver *solv, Queue *job, Id *problem, Id sug, Queue *refined)
3374 {
3375   Pool *pool = solv->pool;
3376   int i, j;
3377   Id v;
3378   Queue disabled;
3379   int disabledcnt;
3380
3381   IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
3382     {
3383       POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "refine_suggestion start\n");
3384       for (i = 0; problem[i]; i++)
3385         {
3386           if (problem[i] == sug)
3387             POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "=> ");
3388           solver_printproblem(solv, problem[i]);
3389         }
3390     }
3391   queue_init(&disabled);
3392   queue_empty(refined);
3393   queue_push(refined, sug);
3394
3395   /* re-enable all problem rules with the exception of "sug"(gestion) */
3396   revert(solv, 1);
3397   reset_solver(solv);
3398
3399   for (i = 0; problem[i]; i++)
3400     if (problem[i] != sug)
3401       enableproblem(solv, problem[i]);
3402
3403   if (sug < 0)
3404     reenablepolicyrules(solv, job, -(sug + 1));
3405   else if (sug >= solv->updaterules && sug < solv->updaterules_end)
3406     {
3407       /* enable feature rule */
3408       Rule *r = solv->rules + solv->featurerules + (sug - solv->updaterules);
3409       if (r->p)
3410         enablerule(solv, r);
3411     }
3412
3413   enableweakrules(solv);
3414
3415   for (;;)
3416     {
3417       int njob, nfeature, nupdate;
3418       queue_empty(&solv->problems);
3419       revert(solv, 1);          /* XXX no longer needed? */
3420       reset_solver(solv);
3421
3422       if (!solv->problems.count)
3423         run_solver(solv, 0, 0);
3424
3425       if (!solv->problems.count)
3426         {
3427           POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "no more problems!\n");
3428           IF_POOLDEBUG (SAT_DEBUG_SCHUBI)
3429             solver_printdecisions(solv);
3430           break;                /* great, no more problems */
3431         }
3432       disabledcnt = disabled.count;
3433       /* start with 1 to skip over proof index */
3434       njob = nfeature = nupdate = 0;
3435       for (i = 1; i < solv->problems.count - 1; i++)
3436         {
3437           /* ignore solutions in refined */
3438           v = solv->problems.elements[i];
3439           if (v == 0)
3440             break;      /* end of problem reached */
3441           for (j = 0; problem[j]; j++)
3442             if (problem[j] != sug && problem[j] == v)
3443               break;
3444           if (problem[j])
3445             continue;
3446           if (v >= solv->featurerules && v < solv->featurerules_end)
3447             nfeature++;
3448           else if (v > 0)
3449             nupdate++;
3450           else
3451             {
3452               if ((job->elements[-v -1] & SOLVER_ESSENTIAL) != 0)
3453                 continue;       /* not that one! */
3454               njob++;
3455             }
3456           queue_push(&disabled, v);
3457         }
3458       if (disabled.count == disabledcnt)
3459         {
3460           /* no solution found, this was an invalid suggestion! */
3461           POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "no solution found!\n");
3462           refined->count = 0;
3463           break;
3464         }
3465       if (!njob && nupdate && nfeature)
3466         {
3467           /* got only update rules, filter out feature rules */
3468           POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "throwing away feature rules\n");
3469           for (i = j = disabledcnt; i < disabled.count; i++)
3470             {
3471               v = disabled.elements[i];
3472               if (v < solv->featurerules || v >= solv->featurerules_end)
3473                 disabled.elements[j++] = v;
3474             }
3475           disabled.count = j;
3476           nfeature = 0;
3477         }
3478       if (disabled.count == disabledcnt + 1)
3479         {
3480           /* just one suggestion, add it to refined list */
3481           v = disabled.elements[disabledcnt];
3482           if (!nfeature)
3483             queue_push(refined, v);     /* do not record feature rules */
3484           disableproblem(solv, v);
3485           if (v >= solv->updaterules && v < solv->updaterules_end)
3486             {
3487               Rule *r = solv->rules + (v - solv->updaterules + solv->featurerules);
3488               if (r->p)
3489                 enablerule(solv, r);    /* enable corresponding feature rule */
3490             }
3491           if (v < 0)
3492             reenablepolicyrules(solv, job, -(v + 1));
3493         }
3494       else
3495         {
3496           /* more than one solution, disable all */
3497           /* do not push anything on refine list, as we do not know which solution to choose */
3498           /* thus, the user will get another problem if he selects this solution, where he
3499            * can choose the right one */
3500           IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
3501             {
3502               POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "more than one solution found:\n");
3503               for (i = disabledcnt; i < disabled.count; i++)
3504                 solver_printproblem(solv, disabled.elements[i]);
3505             }
3506           for (i = disabledcnt; i < disabled.count; i++)
3507             {
3508               v = disabled.elements[i];
3509               disableproblem(solv, v);
3510               if (v >= solv->updaterules && v < solv->updaterules_end)
3511                 {
3512                   Rule *r = solv->rules + (v - solv->updaterules + solv->featurerules);
3513                   if (r->p)
3514                     enablerule(solv, r);
3515                 }
3516             }
3517         }
3518     }
3519   /* all done, get us back into the same state as before */
3520   /* enable refined rules again */
3521   for (i = 0; i < disabled.count; i++)
3522     enableproblem(solv, disabled.elements[i]);
3523   queue_free(&disabled);
3524   /* reset policy rules */
3525   for (i = 0; problem[i]; i++)
3526     enableproblem(solv, problem[i]);
3527   disablepolicyrules(solv, job);
3528   /* disable problem rules again */
3529   for (i = 0; problem[i]; i++)
3530     disableproblem(solv, problem[i]);
3531   POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "refine_suggestion end\n");
3532 }
3533
3534
3535 /*-------------------------------------------------------------------
3536  * sorting helper for problems
3537  *
3538  * bring update rules before job rules
3539  * make essential job rules last
3540  */
3541
3542 Queue *problems_sort_data;
3543
3544 static int
3545 problems_sortcmp(const void *ap, const void *bp)
3546 {
3547   Id a = *(Id *)ap, b = *(Id *)bp;
3548   if (a < 0 && b > 0)
3549     return 1;
3550   if (a > 0 && b < 0)
3551     return -1;
3552   if (a < 0 && b < 0)
3553     {
3554       Queue *job = problems_sort_data;
3555       int af = job->elements[-a - 1] & SOLVER_ESSENTIAL;
3556       int bf = job->elements[-b - 1] & SOLVER_ESSENTIAL;
3557       int x = af - bf;
3558       if (x)
3559         return x;
3560     }
3561   return a - b;
3562 }
3563
3564
3565 /*-------------------------------------------------------------------
3566  * sort problems
3567  */
3568
3569 static void
3570 problems_sort(Solver *solv, Queue *job)
3571 {
3572   int i, j;
3573   if (!solv->problems.count)
3574     return;
3575   for (i = j = 1; i < solv->problems.count; i++)
3576     {
3577       if (!solv->problems.elements[i])
3578         {
3579           if (i > j + 1)
3580             {
3581               problems_sort_data = job;
3582               qsort(solv->problems.elements + j, i - j, sizeof(Id), problems_sortcmp);
3583             }
3584           if (++i == solv->problems.count)
3585             break;
3586           j = i + 1;
3587         }
3588     }
3589 }
3590
3591
3592 /*-------------------------------------------------------------------
3593  * convert problems to solutions
3594  */
3595
3596 static void
3597 problems_to_solutions(Solver *solv, Queue *job)
3598 {
3599   Pool *pool = solv->pool;
3600   Queue problems;
3601   Queue solution;
3602   Queue solutions;
3603   Id *problem;
3604   Id why;
3605   int i, j, nsol, probsolved;
3606   unsigned int now, refnow;
3607
3608   if (!solv->problems.count)
3609     return;
3610   now = sat_timems(0);
3611   problems_sort(solv, job);
3612   queue_clone(&problems, &solv->problems);
3613   queue_init(&solution);
3614   queue_init(&solutions);
3615   /* copy over proof index */
3616   queue_push(&solutions, problems.elements[0]);
3617   problem = problems.elements + 1;
3618   probsolved = 0;
3619   refnow = sat_timems(0);
3620   for (i = 1; i < problems.count; i++)
3621     {
3622       Id v = problems.elements[i];
3623       if (v == 0)
3624         {
3625           /* mark end of this problem */
3626           queue_push(&solutions, 0);
3627           queue_push(&solutions, 0);
3628           POOL_DEBUG(SAT_DEBUG_STATS, "refining took %d ms\n", sat_timems(refnow));
3629           if (i + 1 == problems.count)
3630             break;
3631           /* copy over proof of next problem */
3632           queue_push(&solutions, problems.elements[i + 1]);
3633           i++;
3634           problem = problems.elements + i + 1;
3635           refnow = sat_timems(0);
3636           probsolved = 0;
3637           continue;
3638         }
3639       if (v < 0 && (job->elements[-v - 1] & SOLVER_ESSENTIAL))
3640         {
3641           /* essential job, skip if we already have a non-essential
3642              solution */
3643           if (probsolved > 0)
3644             continue;
3645           probsolved = -1;      /* show all solutions */
3646         }
3647       refine_suggestion(solv, job, problem, v, &solution);
3648       if (!solution.count)
3649         continue;       /* this solution didn't work out */
3650
3651       nsol = 0;
3652       for (j = 0; j < solution.count; j++)
3653         {
3654           why = solution.elements[j];
3655           /* must be either job descriptor or update rule */
3656 #if 0
3657           solver_printproblem(solv, why);
3658 #endif
3659           if (why < 0)
3660             {
3661               /* job descriptor */
3662               queue_push(&solutions, 0);
3663               queue_push(&solutions, -why);
3664             }
3665           else if (why >= solv->infarchrules && why < solv->infarchrules_end)
3666             {
3667               Id p, name;
3668               /* infarch rule, find replacement */
3669               assert(solv->rules[why].p < 0);
3670               name = pool->solvables[-solv->rules[why].p].name;
3671               while (why > solv->infarchrules && pool->solvables[-solv->rules[why - 1].p].name == name)
3672                 why--;
3673               p = 0;
3674               for (; why < solv->infarchrules_end && pool->solvables[-solv->rules[why].p].name == name; why++)
3675                 if (solv->decisionmap[-solv->rules[why].p] > 0)
3676                   {
3677                     p = -solv->rules[why].p;
3678                     break;
3679                   }
3680               if (!p)
3681                 p = -solv->rules[why].p; /* XXX: what to do here? */
3682               queue_push(&solutions, SOLVER_SOLUTION_INFARCH);
3683               queue_push(&solutions, p);
3684             }
3685           else if (why >= solv->duprules && why < solv->duprules_end)
3686             {
3687               Id p, name;
3688               /* dist upgrade rule, find replacement */
3689               assert(solv->rules[why].p < 0);
3690               name = pool->solvables[-solv->rules[why].p].name;
3691               while (why > solv->duprules && pool->solvables[-solv->rules[why - 1].p].name == name)
3692                 why--;
3693               p = 0;
3694               for (; why < solv->duprules_end && pool->solvables[-solv->rules[why].p].name == name; why++)
3695                 if (solv->decisionmap[-solv->rules[why].p] > 0)
3696                   {
3697                     p = -solv->rules[why].p;
3698                     break;
3699                   }
3700               if (!p)
3701                 p = -solv->rules[why].p; /* XXX: what to do here? */
3702               queue_push(&solutions, SOLVER_SOLUTION_DISTUPGRADE);
3703               queue_push(&solutions, p);
3704             }
3705           else
3706             {
3707               /* update rule, find replacement package */
3708               Id p, *dp, rp = 0;
3709               Rule *rr;
3710
3711               assert(why >= solv->updaterules && why < solv->updaterules_end);
3712               /* check if this is a false positive, i.e. the update rule is fulfilled */
3713               rr = solv->rules + why;
3714               FOR_RULELITERALS(p, dp, rr)
3715                 if (p > 0 && solv->decisionmap[p] > 0)
3716                   break;
3717               if (p)
3718                 continue;       /* false alarm */
3719
3720               p = solv->installed->start + (why - solv->updaterules);
3721               rr = solv->rules + solv->featurerules + (why - solv->updaterules);
3722               if (!rr->p)
3723                 rr = solv->rules + why;
3724               if (solv->distupgrade && solv->rules[why].p != p && solv->decisionmap[p] > 0)
3725                 {
3726                   /* distupgrade case, allow to keep old package */
3727                   queue_push(&solutions, p);
3728                   queue_push(&solutions, p);
3729                   nsol++;
3730                   continue;
3731                 }
3732               if (solv->decisionmap[p] > 0)
3733                 continue;       /* false alarm, turned out we can keep the package */
3734               if (rr->w2)
3735                 {
3736                   int mvrp = 0;         /* multi-version replacement */
3737                   FOR_RULELITERALS(rp, dp, rr)
3738                     {
3739                       if (rp > 0 && solv->decisionmap[rp] > 0 && pool->solvables[rp].repo != solv->installed)
3740                         {
3741                           mvrp = rp;
3742                           if (!(solv->noobsoletes.size && MAPTST(&solv->noobsoletes, rp)))
3743                             break;
3744                         }
3745                     }
3746                   if (!rp && mvrp)
3747                     {
3748                       /* found only multi-version replacements */
3749                       /* have to split solution into two parts */
3750                       queue_push(&solutions, p);
3751                       queue_push(&solutions, mvrp);
3752                       nsol++;
3753                     }
3754                 }
3755               queue_push(&solutions, p);
3756               queue_push(&solutions, rp);
3757             }
3758           nsol++;
3759         }
3760       /* mark end of this solution */
3761       if (nsol)
3762         {
3763           if (!probsolved)
3764             probsolved = 1;
3765           queue_push(&solutions, 0);
3766           queue_push(&solutions, 0);
3767         }
3768       else
3769         {
3770           POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "Oops, everything was fine?\n");
3771         }
3772     }
3773   queue_free(&solution);
3774   queue_free(&problems);
3775   /* copy queue over to solutions */
3776   queue_free(&solv->problems);
3777   queue_clone(&solv->problems, &solutions);
3778
3779   /* bring solver back into problem state */
3780   revert(solv, 1);              /* XXX move to reset_solver? */
3781   reset_solver(solv);
3782
3783   assert(solv->problems.count == solutions.count);
3784   queue_free(&solutions);
3785   POOL_DEBUG(SAT_DEBUG_STATS, "problems_to_solutions took %d ms\n", sat_timems(now));
3786 }
3787
3788
3789 /*-------------------------------------------------------------------
3790  *
3791  * problem iterator
3792  *
3793  * advance to next problem
3794  */
3795
3796 Id
3797 solver_next_problem(Solver *solv, Id problem)
3798 {
3799   Id *pp;
3800   if (problem == 0)
3801     return solv->problems.count ? 1 : 0;
3802   pp = solv->problems.elements + problem;
3803   while (pp[0] || pp[1])
3804     {
3805       /* solution */
3806       pp += 2;
3807       while (pp[0] || pp[1])
3808         pp += 2;
3809       pp += 2;
3810     }
3811   pp += 2;
3812   problem = pp - solv->problems.elements;
3813   if (problem >= solv->problems.count)
3814     return 0;
3815   return problem + 1;
3816 }
3817
3818
3819 /*-------------------------------------------------------------------
3820  *
3821  * solution iterator
3822  */
3823
3824 Id
3825 solver_next_solution(Solver *solv, Id problem, Id solution)
3826 {
3827   Id *pp;
3828   if (solution == 0)
3829     {
3830       solution = problem;
3831       pp = solv->problems.elements + solution;
3832       return pp[0] || pp[1] ? solution : 0;
3833     }
3834   pp = solv->problems.elements + solution;
3835   while (pp[0] || pp[1])
3836     pp += 2;
3837   pp += 2;
3838   solution = pp - solv->problems.elements;
3839   return pp[0] || pp[1] ? solution : 0;
3840 }
3841
3842
3843 /*-------------------------------------------------------------------
3844  *
3845  * solution element iterator
3846  */
3847
3848 Id
3849 solver_next_solutionelement(Solver *solv, Id problem, Id solution, Id element, Id *p, Id *rp)
3850 {
3851   Id *pp;
3852   element = element ? element + 2 : solution;
3853   pp = solv->problems.elements + element;
3854   if (!(pp[0] || pp[1]))
3855     return 0;
3856   *p = pp[0];
3857   *rp = pp[1];
3858   return element;
3859 }
3860
3861
3862 /*-------------------------------------------------------------------
3863  *
3864  * Retrieve information about a problematic rule
3865  *
3866  * this is basically the reverse of addrpmrulesforsolvable
3867  */
3868
3869 SolverProbleminfo
3870 solver_problemruleinfo(Solver *solv, Queue *job, Id rid, Id *depp, Id *sourcep, Id *targetp)
3871 {
3872   Pool *pool = solv->pool;
3873   Repo *installed = solv->installed;
3874   Rule *r;
3875   Solvable *s;
3876   int dontfix = 0;
3877   Id p, d, w2, pp, req, *reqp, con, *conp, obs, *obsp, *dp;
3878
3879   assert(rid > 0);
3880   if (rid >= solv->infarchrules && rid < solv->infarchrules_end)
3881     {
3882       r = solv->rules + rid;
3883       *depp = r->p < 0 ? pool->solvables[-r->p].name : 0;
3884       *sourcep = r->p < 0 ? -r->p : 0;
3885       *targetp = 0;
3886       return SOLVER_PROBLEM_INFARCH_RULE;
3887     }
3888   if (rid >= solv->duprules && rid < solv->duprules_end)
3889     {
3890       r = solv->rules + rid;
3891       *depp = r->p < 0 ? pool->solvables[-r->p].name : 0;
3892       *sourcep = r->p < 0 ? -r->p : 0;
3893       *targetp = 0;
3894       return SOLVER_PROBLEM_DISTUPGRADE_RULE;
3895     }
3896   if (rid >= solv->jobrules && rid < solv->jobrules_end)
3897     {
3898
3899       r = solv->rules + rid;
3900       p = solv->ruletojob.elements[rid - solv->jobrules];
3901       *depp = job->elements[p + 1];
3902       *sourcep = p;
3903       *targetp = job->elements[p];
3904       d = r->d < 0 ? -r->d - 1 : r->d;
3905       if (d == 0 && r->w2 == 0 && r->p == -SYSTEMSOLVABLE && (job->elements[p] & SOLVER_SELECTMASK) != SOLVER_SOLVABLE_ONE_OF)
3906         return SOLVER_PROBLEM_JOB_NOTHING_PROVIDES_DEP;
3907       return SOLVER_PROBLEM_JOB_RULE;
3908     }
3909   if (rid >= solv->updaterules && rid < solv->updaterules_end)
3910     {
3911       *depp = 0;
3912       *sourcep = solv->installed->start + (rid - solv->updaterules);
3913       *targetp = 0;
3914       return SOLVER_PROBLEM_UPDATE_RULE;
3915     }
3916   assert(rid < solv->rpmrules_end);
3917   r = solv->rules + rid;
3918   assert(r->p < 0);
3919   d = r->d < 0 ? -r->d - 1 : r->d;
3920   if (d == 0 && r->w2 == 0)
3921     {
3922       /* a rpm rule assertion */
3923       s = pool->solvables - r->p;
3924       if (installed && !solv->fixsystem && s->repo == installed)
3925         dontfix = 1;
3926       assert(!dontfix); /* dontfix packages never have a neg assertion */
3927       *sourcep = -r->p;
3928       *targetp = 0;
3929       /* see why the package is not installable */
3930       if (s->arch != ARCH_SRC && s->arch != ARCH_NOSRC && !pool_installable(pool, s))
3931         {
3932           *depp = 0;
3933           return SOLVER_PROBLEM_NOT_INSTALLABLE;
3934         }
3935       /* check requires */
3936       if (s->requires)
3937         {
3938           reqp = s->repo->idarraydata + s->requires;
3939           while ((req = *reqp++) != 0)
3940             {
3941               if (req == SOLVABLE_PREREQMARKER)
3942                 continue;
3943               dp = pool_whatprovides_ptr(pool, req);
3944               if (*dp == 0)
3945                 break;
3946             }
3947           if (req)
3948             {
3949               *depp = req;
3950               return SOLVER_PROBLEM_NOTHING_PROVIDES_DEP;
3951             }
3952         }
3953       if (!solv->allowselfconflicts && s->conflicts)
3954         {
3955           conp = s->repo->idarraydata + s->conflicts;
3956           while ((con = *conp++) != 0)
3957             FOR_PROVIDES(p, pp, con)
3958               if (p == -r->p)
3959                 {
3960                   *depp = con;
3961                   return SOLVER_PROBLEM_SELF_CONFLICT;
3962                 }
3963         }
3964       /* should never happen */
3965       *depp = 0;
3966       return SOLVER_PROBLEM_RPM_RULE;
3967     }
3968   s = pool->solvables - r->p;
3969   if (installed && !solv->fixsystem && s->repo == installed)
3970     dontfix = 1;
3971   w2 = r->w2;
3972   if (d && pool->whatprovidesdata[d] < 0)
3973     {
3974       /* rule looks like -p|-c|x|x|x..., we only create this for patches with multiversion */
3975       /* reduce it to -p|-c case */
3976       d = 0;
3977       w2 = pool->whatprovidesdata[d];
3978     }
3979   if (d == 0 && w2 < 0)
3980     {
3981       /* a package conflict */
3982       Solvable *s2 = pool->solvables - w2;
3983       int dontfix2 = 0;
3984
3985       if (installed && !solv->fixsystem && s2->repo == installed)
3986         dontfix2 = 1;
3987
3988       /* if both packages have the same name and at least one of them
3989        * is not installed, they conflict */
3990       if (s->name == s2->name && !(installed && s->repo == installed && s2->repo == installed))
3991         {
3992           /* also check noobsoletes map */
3993           if ((s->evr == s2->evr && s->arch == s2->arch) || !solv->noobsoletes.size
3994                 || ((!installed || s->repo != installed) && !MAPTST(&solv->noobsoletes, -r->p))
3995                 || ((!installed || s2->repo != installed) && !MAPTST(&solv->noobsoletes, -w2)))
3996             {
3997               *depp = 0;
3998               *sourcep = -r->p;
3999               *targetp = -w2;
4000               return SOLVER_PROBLEM_SAME_NAME;
4001             }
4002         }
4003
4004       /* check conflicts in both directions */
4005       if (s->conflicts)
4006         {
4007           conp = s->repo->idarraydata + s->conflicts;
4008           while ((con = *conp++) != 0)
4009             {
4010               FOR_PROVIDES(p, pp, con)
4011                 {
4012                   if (dontfix && pool->solvables[p].repo == installed)
4013                     continue;
4014                   if (p != -w2)
4015                     continue;
4016                   *depp = con;
4017                   *sourcep = -r->p;
4018                   *targetp = p;
4019                   return SOLVER_PROBLEM_PACKAGE_CONFLICT;
4020                 }
4021             }
4022         }
4023       if (s2->conflicts)
4024         {
4025           conp = s2->repo->idarraydata + s2->conflicts;
4026           while ((con = *conp++) != 0)
4027             {
4028               FOR_PROVIDES(p, pp, con)
4029                 {
4030                   if (dontfix2 && pool->solvables[p].repo == installed)
4031                     continue;
4032                   if (p != -r->p)
4033                     continue;
4034                   *depp = con;
4035                   *sourcep = -w2;
4036                   *targetp = p;
4037                   return SOLVER_PROBLEM_PACKAGE_CONFLICT;
4038                 }
4039             }
4040         }
4041       /* check obsoletes in both directions */
4042       if ((!installed || s->repo != installed) && s->obsoletes && !(solv->noobsoletes.size && MAPTST(&solv->noobsoletes, -r->p)))
4043         {
4044           obsp = s->repo->idarraydata + s->obsoletes;
4045           while ((obs = *obsp++) != 0)
4046             {
4047               FOR_PROVIDES(p, pp, obs)
4048                 {
4049                   if (p != -w2)
4050                     continue;
4051                   if (!solv->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p, obs))
4052                     continue;
4053                   *depp = obs;
4054                   *sourcep = -r->p;
4055                   *targetp = p;
4056                   return SOLVER_PROBLEM_PACKAGE_OBSOLETES;
4057                 }
4058             }
4059         }
4060       if ((!installed || s2->repo != installed) && s2->obsoletes && !(solv->noobsoletes.size && MAPTST(&solv->noobsoletes, -w2)))
4061         {
4062           obsp = s2->repo->idarraydata + s2->obsoletes;
4063           while ((obs = *obsp++) != 0)
4064             {
4065               FOR_PROVIDES(p, pp, obs)
4066                 {
4067                   if (p != -r->p)
4068                     continue;
4069                   if (!solv->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p, obs))
4070                     continue;
4071                   *depp = obs;
4072                   *sourcep = -w2;
4073                   *targetp = p;
4074                   return SOLVER_PROBLEM_PACKAGE_OBSOLETES;
4075                 }
4076             }
4077         }
4078       if (solv->implicitobsoleteusesprovides && (!installed || s->repo != installed) && !(solv->noobsoletes.size && MAPTST(&solv->noobsoletes, -r->p)))
4079         {
4080           FOR_PROVIDES(p, pp, s->name)
4081             {
4082               if (p != -w2)
4083                 continue;
4084               *depp = s->name;
4085               *sourcep = -r->p;
4086               *targetp = p;
4087               return SOLVER_PROBLEM_PACKAGE_OBSOLETES;
4088             }
4089         }
4090       if (solv->implicitobsoleteusesprovides && (!installed || s2->repo != installed) && !(solv->noobsoletes.size && MAPTST(&solv->noobsoletes, -w2)))
4091         {
4092           FOR_PROVIDES(p, pp, s2->name)
4093             {
4094               if (p != -r->p)
4095                 continue;
4096               *depp = s2->name;
4097               *sourcep = -w2;
4098               *targetp = p;
4099               return SOLVER_PROBLEM_PACKAGE_OBSOLETES;
4100             }
4101         }
4102       /* all cases checked, can't happen */
4103       *depp = 0;
4104       *sourcep = -r->p;
4105       *targetp = 0;
4106       return SOLVER_PROBLEM_RPM_RULE;
4107     }
4108   /* simple requires */
4109   if (s->requires)
4110     {
4111       reqp = s->repo->idarraydata + s->requires;
4112       while ((req = *reqp++) != 0)
4113         {
4114           if (req == SOLVABLE_PREREQMARKER)
4115             continue;
4116           dp = pool_whatprovides_ptr(pool, req);
4117           if (d == 0)
4118             {
4119               if (*dp == r->w2 && dp[1] == 0)
4120                 break;
4121             }
4122           else if (dp - pool->whatprovidesdata == d)
4123             break;
4124         }
4125       if (req)
4126         {
4127           *depp = req;
4128           *sourcep = -r->p;
4129           *targetp = 0;
4130           return SOLVER_PROBLEM_DEP_PROVIDERS_NOT_INSTALLABLE;
4131         }
4132     }
4133
4134   /* check for product buddy requires */
4135   if (d == 0 && w2 > 0 && pool->nscallback)
4136     {
4137       Id buddy = 0;
4138       s = pool->solvables - r->p;
4139       if (!strncmp("product:", id2str(pool, s->name), 8))
4140         {
4141           buddy = pool->nscallback(pool, pool->nscallbackdata, NAMESPACE_PRODUCTBUDDY, -r->p);
4142           if (buddy != w2)
4143             buddy = 0;
4144         }
4145       if (!buddy)
4146         {
4147           s = pool->solvables + w2;
4148           if (!strncmp("product:", id2str(pool, s->name), 8))
4149             {
4150               buddy = pool->nscallback(pool, pool->nscallbackdata, NAMESPACE_PRODUCTBUDDY, w2);
4151               if (buddy != -r->p)
4152                 buddy = 0;
4153             }
4154         }
4155       if (buddy)
4156         {
4157           /* have buddy relation, now fake requires */
4158           s = pool->solvables + w2;
4159           Reldep *rd;
4160           if (s->repo && s->provides)
4161             {
4162               Id prov, *provp;
4163               provp = s->repo->idarraydata + s->provides;
4164               while ((prov = *provp++) != 0)
4165                 {
4166                   if (!ISRELDEP(prov))
4167                     continue;
4168                   rd = GETRELDEP(pool, prov);
4169                   if (rd->name == s->name && rd->evr == s->evr && rd->flags == REL_EQ)
4170                     {
4171                       *depp = prov;
4172                       *sourcep = -r->p;
4173                       *targetp = 0;
4174                       return SOLVER_PROBLEM_DEP_PROVIDERS_NOT_INSTALLABLE;
4175                     }
4176                 }
4177             }
4178           *depp = s->name;
4179           *sourcep = -r->p;
4180           *targetp = 0;
4181           return SOLVER_PROBLEM_DEP_PROVIDERS_NOT_INSTALLABLE;
4182         }
4183     }
4184
4185   /* all cases checked, can't happen */
4186   *depp = 0;
4187   *sourcep = -r->p;
4188   *targetp = 0;
4189   return SOLVER_PROBLEM_RPM_RULE;
4190 }
4191
4192
4193 /*-------------------------------------------------------------------
4194  *
4195  * find problem rule
4196  */
4197
4198 static void
4199 findproblemrule_internal(Solver *solv, Id idx, Id *reqrp, Id *conrp, Id *sysrp, Id *jobrp)
4200 {
4201   Id rid, d;
4202   Id lreqr, lconr, lsysr, ljobr;
4203   Rule *r;
4204   int reqassert = 0;
4205
4206   lreqr = lconr = lsysr = ljobr = 0;
4207   while ((rid = solv->learnt_pool.elements[idx++]) != 0)
4208     {
4209       assert(rid > 0);
4210       if (rid >= solv->learntrules)
4211         findproblemrule_internal(solv, solv->learnt_why.elements[rid - solv->learntrules], &lreqr, &lconr, &lsysr, &ljobr);
4212       else if ((rid >= solv->jobrules && rid < solv->jobrules_end) || (rid >= solv->infarchrules && rid < solv->infarchrules_end) || (rid >= solv->duprules && rid < solv->duprules_end))
4213         {
4214           if (!*jobrp)
4215             *jobrp = rid;
4216         }
4217       else if (rid >= solv->updaterules && rid < solv->updaterules_end)
4218         {
4219           if (!*sysrp)
4220             *sysrp = rid;
4221         }
4222       else
4223         {
4224           assert(rid < solv->rpmrules_end);
4225           r = solv->rules + rid;
4226           d = r->d < 0 ? -r->d - 1 : r->d;
4227           if (!d && r->w2 < 0)
4228             {
4229               if (!*conrp)
4230                 *conrp = rid;
4231             }
4232           else
4233             {
4234               if (!d && r->w2 == 0 && !reqassert)
4235                 {
4236                   if (*reqrp > 0 && r->p < -1)
4237                     {
4238                       Id op = -solv->rules[*reqrp].p;
4239                       if (op > 1 && solv->pool->solvables[op].arch != solv->pool->solvables[-r->p].arch)
4240                         continue;       /* different arch, skip */
4241                     }
4242                   /* prefer assertions */
4243                   *reqrp = rid;
4244                   reqassert = 1;
4245                 }
4246               if (!*reqrp)
4247                 *reqrp = rid;
4248               else if (solv->installed && r->p < 0 && solv->pool->solvables[-r->p].repo == solv->installed && !reqassert)
4249                 {
4250                   /* prefer rules of installed packages */
4251                   *reqrp = rid;
4252                 }
4253             }
4254         }
4255     }
4256   if (!*reqrp && lreqr)
4257     *reqrp = lreqr;
4258   if (!*conrp && lconr)
4259     *conrp = lconr;
4260   if (!*jobrp && ljobr)
4261     *jobrp = ljobr;
4262   if (!*sysrp && lsysr)
4263     *sysrp = lsysr;
4264 }
4265
4266
4267 /*-------------------------------------------------------------------
4268  *
4269  * find problem rule
4270  *
4271  * search for a rule that describes the problem to the
4272  * user. A pretty hopeless task, actually. We currently
4273  * prefer simple requires.
4274  */
4275
4276 Id
4277 solver_findproblemrule(Solver *solv, Id problem)
4278 {
4279   Id reqr, conr, sysr, jobr;
4280   Id idx = solv->problems.elements[problem - 1];
4281   reqr = conr = sysr = jobr = 0;
4282   findproblemrule_internal(solv, idx, &reqr, &conr, &sysr, &jobr);
4283   if (reqr)
4284     return reqr;
4285   if (conr)
4286     return conr;
4287   if (sysr)
4288     return sysr;
4289   if (jobr)
4290     return jobr;
4291   assert(0);
4292 }
4293
4294 static void
4295 findallproblemrules_internal(Solver *solv, Id idx, Queue *rules)
4296 {
4297   Id rid;
4298   while ((rid = solv->learnt_pool.elements[idx++]) != 0)
4299     {
4300       if (rid >= solv->learntrules)
4301         {
4302           findallproblemrules_internal(solv, solv->learnt_why.elements[rid - solv->learntrules], rules);
4303           continue;
4304         }
4305       queue_pushunique(rules, rid);
4306     }
4307 }
4308
4309 void
4310 solver_findallproblemrules(Solver *solv, Id problem, Queue *rules)
4311 {
4312   queue_empty(rules);
4313   findallproblemrules_internal(solv, solv->problems.elements[problem - 1], rules);
4314 }
4315
4316
4317 /*-------------------------------------------------------------------
4318  *
4319  * create reverse obsoletes map for installed solvables
4320  *
4321  * for each installed solvable find which packages with *different* names
4322  * obsolete the solvable.
4323  * this index is used in policy_findupdatepackages if noupdateprovide is set.
4324  */
4325
4326 static void
4327 create_obsolete_index(Solver *solv)
4328 {
4329   Pool *pool = solv->pool;
4330   Solvable *s;
4331   Repo *installed = solv->installed;
4332   Id p, pp, obs, *obsp, *obsoletes, *obsoletes_data;
4333   int i, n;
4334
4335   if (!installed || !installed->nsolvables)
4336     return;
4337   solv->obsoletes = obsoletes = sat_calloc(installed->end - installed->start, sizeof(Id));
4338   for (i = 1; i < pool->nsolvables; i++)
4339     {
4340       s = pool->solvables + i;
4341       if (!s->obsoletes)
4342         continue;
4343       if (!pool_installable(pool, s))
4344         continue;
4345       obsp = s->repo->idarraydata + s->obsoletes;
4346       while ((obs = *obsp++) != 0)
4347         {
4348           FOR_PROVIDES(p, pp, obs)
4349             {
4350               if (pool->solvables[p].repo != installed)
4351                 continue;
4352               if (pool->solvables[p].name == s->name)
4353                 continue;
4354               if (!solv->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p, obs))
4355                 continue;
4356               obsoletes[p - installed->start]++;
4357             }
4358         }
4359     }
4360   n = 0;
4361   for (i = 0; i < installed->nsolvables; i++)
4362     if (obsoletes[i])
4363       {
4364         n += obsoletes[i] + 1;
4365         obsoletes[i] = n;
4366       }
4367   solv->obsoletes_data = obsoletes_data = sat_calloc(n + 1, sizeof(Id));
4368   POOL_DEBUG(SAT_DEBUG_STATS, "obsoletes data: %d entries\n", n + 1);
4369   for (i = pool->nsolvables - 1; i > 0; i--)
4370     {
4371       s = pool->solvables + i;
4372       if (!s->obsoletes)
4373         continue;
4374       if (!pool_installable(pool, s))
4375         continue;
4376       obsp = s->repo->idarraydata + s->obsoletes;
4377       while ((obs = *obsp++) != 0)
4378         {
4379           FOR_PROVIDES(p, pp, obs)
4380             {
4381               if (pool->solvables[p].repo != installed)
4382                 continue;
4383               if (pool->solvables[p].name == s->name)
4384                 continue;
4385               if (!solv->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p, obs))
4386                 continue;
4387               p -= installed->start;
4388               if (obsoletes_data[obsoletes[p]] != i)
4389                 obsoletes_data[--obsoletes[p]] = i;
4390             }
4391         }
4392     }
4393 }
4394
4395
4396 /*-------------------------------------------------------------------
4397  *
4398  * remove disabled conflicts
4399  */
4400
4401 static void
4402 removedisabledconflicts(Solver *solv, Queue *removed)
4403 {
4404   Pool *pool = solv->pool;
4405   int i, n;
4406   Id p, why, *dp;
4407   Id new;
4408   Rule *r;
4409   Id *decisionmap = solv->decisionmap;
4410
4411   POOL_DEBUG(SAT_DEBUG_SCHUBI, "removedisabledconflicts\n");
4412   queue_empty(removed);
4413   for (i = 0; i < solv->decisionq.count; i++)
4414     {
4415       p = solv->decisionq.elements[i];
4416       if (p > 0)
4417         continue;
4418       /* a conflict. we never do conflicts on free decisions, so there
4419        * must have been an unit rule */
4420       why = solv->decisionq_why.elements[i];
4421       assert(why > 0);
4422       r = solv->rules + why;
4423       if (r->d < 0 && decisionmap[-p])
4424         {
4425           /* rule is now disabled, remove from decisionmap */
4426           POOL_DEBUG(SAT_DEBUG_SCHUBI, "removing conflict for package %s[%d]\n", solvable2str(pool, pool->solvables - p), -p);
4427           queue_push(removed, -p);
4428           queue_push(removed, decisionmap[-p]);
4429           decisionmap[-p] = 0;
4430         }
4431     }
4432   if (!removed->count)
4433     return;
4434   /* we removed some confliced packages. some of them might still
4435    * be in conflict, so search for unit rules and re-conflict */
4436   new = 0;
4437   for (i = n = 1, r = solv->rules + i; n < solv->nrules; i++, r++, n++)
4438     {
4439       if (i == solv->nrules)
4440         {
4441           i = 1;
4442           r = solv->rules + i;
4443         }
4444       if (r->d < 0)
4445         continue;
4446       if (!r->w2)
4447         {
4448           if (r->p < 0 && !decisionmap[-r->p])
4449             new = r->p;
4450         }
4451       else if (!r->d)
4452         {
4453           /* binary rule */
4454           if (r->p < 0 && decisionmap[-r->p] == 0 && DECISIONMAP_FALSE(r->w2))
4455             new = r->p;
4456           else if (r->w2 < 0 && decisionmap[-r->w2] == 0 && DECISIONMAP_FALSE(r->p))
4457             new = r->w2;
4458         }
4459       else
4460         {
4461           if (r->p < 0 && decisionmap[-r->p] == 0)
4462             new = r->p;
4463           if (new || DECISIONMAP_FALSE(r->p))
4464             {
4465               dp = pool->whatprovidesdata + r->d;
4466               while ((p = *dp++) != 0)
4467                 {
4468                   if (new && p == new)
4469                     continue;
4470                   if (p < 0 && decisionmap[-p] == 0)
4471                     {
4472                       if (new)
4473                         {
4474                           new = 0;
4475                           break;
4476                         }
4477                       new = p;
4478                     }
4479                   else if (!DECISIONMAP_FALSE(p))
4480                     {
4481                       new = 0;
4482                       break;
4483                     }
4484                 }
4485             }
4486         }
4487       if (new)
4488         {
4489           POOL_DEBUG(SAT_DEBUG_SCHUBI, "re-conflicting package %s[%d]\n", solvable2str(pool, pool->solvables - new), -new);
4490           decisionmap[-new] = -1;
4491           new = 0;
4492           n = 0;        /* redo all rules */
4493         }
4494     }
4495 }
4496
4497
4498 /*-------------------------------------------------------------------
4499  *
4500  * weaken solvable dependencies
4501  */
4502
4503 static void
4504 weaken_solvable_deps(Solver *solv, Id p)
4505 {
4506   int i;
4507   Rule *r;
4508
4509   for (i = 1, r = solv->rules + i; i < solv->rpmrules_end; i++, r++)
4510     {
4511       if (r->p != -p)
4512         continue;
4513       if ((r->d == 0 || r->d == -1) && r->w2 < 0)
4514         continue;       /* conflict */
4515       queue_push(&solv->weakruleq, i);
4516     }
4517 }
4518
4519 /********************************************************************/
4520 /* main() */
4521
4522
4523 static void
4524 addinfarchrules(Solver *solv, Map *addedmap)
4525 {
4526   Pool *pool = solv->pool;
4527   int first, i, j;
4528   Id p, pp, a, aa, bestarch;
4529   Solvable *s, *ps, *bests;
4530   Queue badq, allowedarchs;
4531
4532   queue_init(&badq);
4533   queue_init(&allowedarchs);
4534   solv->infarchrules = solv->nrules;
4535   for (i = 1; i < pool->nsolvables; i++)
4536     {
4537       if (i == SYSTEMSOLVABLE || !MAPTST(addedmap, i))
4538         continue;
4539       s = pool->solvables + i;
4540       first = i;
4541       bestarch = 0;
4542       bests = 0;
4543       queue_empty(&allowedarchs);
4544       FOR_PROVIDES(p, pp, s->name)
4545         {
4546           ps = pool->solvables + p;
4547           if (ps->name != s->name || !MAPTST(addedmap, p))
4548             continue;
4549           if (p == i)
4550             first = 0;
4551           if (first)
4552             break;
4553           a = ps->arch;
4554           a = (a <= pool->lastarch) ? pool->id2arch[a] : 0;
4555           if (a != 1 && pool->installed && ps->repo == pool->installed && !solv->distupgrade)
4556             {
4557               queue_pushunique(&allowedarchs, ps->arch);        /* also ok to keep this architecture */
4558               continue;         /* ignore installed solvables when calculating the best arch */
4559             }
4560           if (a && a != 1 && (!bestarch || a < bestarch))
4561             {
4562               bestarch = a;
4563               bests = ps;
4564             }
4565         }
4566       if (first)
4567         continue;
4568       /* speed up common case where installed package already has best arch */
4569       if (allowedarchs.count == 1 && bests && allowedarchs.elements[0] == bests->arch)
4570         allowedarchs.count--;   /* installed arch is best */
4571       queue_empty(&badq);
4572       FOR_PROVIDES(p, pp, s->name)
4573         {
4574           ps = pool->solvables + p;
4575           if (ps->name != s->name || !MAPTST(addedmap, p))
4576             continue;
4577           a = ps->arch;
4578           a = (a <= pool->lastarch) ? pool->id2arch[a] : 0;
4579           if (a != 1 && bestarch && ((a ^ bestarch) & 0xffff0000) != 0)
4580             {
4581               for (j = 0; j < allowedarchs.count; j++)
4582                 {
4583                   aa = allowedarchs.elements[j];
4584                   if (ps->arch == aa)
4585                     break;
4586                   aa = (aa <= pool->lastarch) ? pool->id2arch[aa] : 0;
4587                   if (aa && ((a ^ aa) & 0xffff0000) == 0)
4588                     break;      /* compatible */
4589                 }
4590               if (j == allowedarchs.count)
4591                 queue_push(&badq, p);
4592             }
4593         }
4594       if (!badq.count)
4595         continue;
4596       /* block all solvables in the badq! */
4597       for (j = 0; j < badq.count; j++)
4598         {
4599           p = badq.elements[j];
4600           addrule(solv, -p, 0);
4601         }
4602     }
4603   queue_free(&badq);
4604   queue_free(&allowedarchs);
4605   solv->infarchrules_end = solv->nrules;
4606 }
4607
4608 static void
4609 createdupmaps(Solver *solv, Queue *job)
4610 {
4611   Pool *pool = solv->pool;
4612   Repo *repo;
4613   Id how, what, p, pi, pp, obs, *obsp;
4614   Solvable *s, *ps;
4615   int i;
4616
4617   map_init(&solv->dupmap, pool->nsolvables);
4618   map_init(&solv->dupinvolvedmap, pool->nsolvables);
4619   for (i = 0; i < job->count; i += 2)
4620     {
4621       how = job->elements[i];
4622       what = job->elements[i + 1];
4623       switch (how & SOLVER_JOBMASK)
4624         {
4625         case SOLVER_DISTUPGRADE:
4626           if (what < 0 || what > pool->nrepos)
4627             break;
4628           repo = pool->repos[what];
4629           FOR_REPO_SOLVABLES(repo, p, s)
4630             {
4631               MAPSET(&solv->dupmap, p);
4632               FOR_PROVIDES(pi, pp, s->name)
4633                 {
4634                   ps = pool->solvables + pi;
4635                   if (ps->name != s->name)
4636                     continue;
4637                   MAPSET(&solv->dupinvolvedmap, pi);
4638                 }
4639               if (s->obsoletes)
4640                 {
4641                   /* FIXME: check obsoletes/provides combination */
4642                   obsp = s->repo->idarraydata + s->obsoletes;
4643                   while ((obs = *obsp++) != 0)
4644                     {
4645                       FOR_PROVIDES(pi, pp, obs)
4646                         {
4647                           if (!solv->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + pi, obs))
4648                             continue;
4649                           MAPSET(&solv->dupinvolvedmap, pi);
4650                         }
4651                     }
4652                 }
4653             }
4654           break;
4655         default:
4656           break;
4657         }
4658     }
4659   MAPCLR(&solv->dupinvolvedmap, SYSTEMSOLVABLE);
4660 }
4661
4662 static void
4663 freedupmaps(Solver *solv)
4664 {
4665   map_free(&solv->dupmap);
4666   map_free(&solv->dupinvolvedmap);
4667 }
4668
4669 static void
4670 addduprules(Solver *solv, Map *addedmap)
4671 {
4672   Pool *pool = solv->pool;
4673   Id p, pp;
4674   Solvable *s, *ps;
4675   int first, i;
4676
4677   solv->duprules = solv->nrules;
4678   for (i = 1; i < pool->nsolvables; i++)
4679     {
4680       if (i == SYSTEMSOLVABLE || !MAPTST(addedmap, i))
4681         continue;
4682       s = pool->solvables + i;
4683       first = i;
4684       FOR_PROVIDES(p, pp, s->name)
4685         {
4686           ps = pool->solvables + p;
4687           if (ps->name != s->name || !MAPTST(addedmap, p))
4688             continue;
4689           if (p == i)
4690             first = 0;
4691           if (first)
4692             break;
4693           if (!MAPTST(&solv->dupinvolvedmap, p))
4694             continue;
4695           if (solv->installed && ps->repo == solv->installed)
4696             {
4697               if (!solv->updatemap.size)
4698                 map_init(&solv->updatemap, pool->nsolvables);
4699               MAPSET(&solv->updatemap, p);
4700               if (!MAPTST(&solv->dupmap, p))
4701                 {
4702                   Id ip, ipp;
4703                   /* is installed identical to a good one? */
4704                   FOR_PROVIDES(ip, ipp, s->name)
4705                     {
4706                       Solvable *is = pool->solvables + ip;
4707                       if (!MAPTST(&solv->dupmap, ip))
4708                         continue;
4709                       if (is->evr == s->evr && solvable_identical(s, is))
4710                         break;
4711                     }
4712                   if (!ip)
4713                     addrule(solv, -p, 0);       /* no match, sorry */
4714                 }
4715             }
4716           else if (!MAPTST(&solv->dupmap, p))
4717             addrule(solv, -p, 0);
4718         }
4719     }
4720   solv->duprules_end = solv->nrules;
4721 }
4722
4723 /*
4724  *
4725  * solve job queue
4726  *
4727  */
4728
4729 void
4730 solver_solve(Solver *solv, Queue *job)
4731 {
4732   Pool *pool = solv->pool;
4733   Repo *installed = solv->installed;
4734   int i;
4735   int oldnrules;
4736   Map addedmap;                /* '1' == have rpm-rules for solvable */
4737   Map installcandidatemap;
4738   Id how, what, select, name, weak, p, pp, d;
4739   Queue q, redoq;
4740   Solvable *s;
4741   int goterase;
4742   Rule *r;
4743   int now, solve_start;
4744   int hasdupjob = 0;
4745
4746   solve_start = sat_timems(0);
4747   POOL_DEBUG(SAT_DEBUG_STATS, "solver started\n");
4748   POOL_DEBUG(SAT_DEBUG_STATS, "fixsystem=%d updatesystem=%d dosplitprovides=%d, noupdateprovide=%d\n", solv->fixsystem, solv->updatesystem, solv->dosplitprovides, solv->noupdateprovide);
4749   POOL_DEBUG(SAT_DEBUG_STATS, "distupgrade=%d distupgrade_removeunsupported=%d\n", solv->distupgrade, solv->distupgrade_removeunsupported);
4750   POOL_DEBUG(SAT_DEBUG_STATS, "allowuninstall=%d, allowdowngrade=%d, allowarchchange=%d, allowvendorchange=%d\n", solv->allowuninstall, solv->allowdowngrade, solv->allowarchchange, solv->allowvendorchange);
4751   POOL_DEBUG(SAT_DEBUG_STATS, "promoteepoch=%d, allowvirtualconflicts=%d, allowselfconflicts=%d\n", pool->promoteepoch, solv->allowvirtualconflicts, solv->allowselfconflicts);
4752   POOL_DEBUG(SAT_DEBUG_STATS, "obsoleteusesprovides=%d, implicitobsoleteusesprovides=%d\n", solv->obsoleteusesprovides, solv->implicitobsoleteusesprovides);
4753   POOL_DEBUG(SAT_DEBUG_STATS, "dontinstallrecommended=%d, ignorealreadyrecommended=%d, dontshowinstalledrecommended=%d\n", solv->dontinstallrecommended, solv->ignorealreadyrecommended, solv->dontshowinstalledrecommended);
4754   /* create whatprovides if not already there */
4755   if (!pool->whatprovides)
4756     pool_createwhatprovides(pool);
4757
4758   /* create obsolete index */
4759   create_obsolete_index(solv);
4760
4761   /* remember job */
4762   solv->job = job;
4763
4764   /*
4765    * create basic rule set of all involved packages
4766    * use addedmap bitmap to make sure we don't create rules twice
4767    *
4768    */
4769
4770   /* create noobsolete map if needed */
4771   for (i = 0; i < job->count; i += 2)
4772     {
4773       how = job->elements[i] & ~SOLVER_WEAK;
4774       if ((how & SOLVER_JOBMASK) != SOLVER_NOOBSOLETES)
4775         continue;
4776       what = job->elements[i + 1];
4777       select = how & SOLVER_SELECTMASK;
4778       if (!solv->noobsoletes.size)
4779         map_init(&solv->noobsoletes, pool->nsolvables);
4780       FOR_JOB_SELECT(p, pp, select, what)
4781         MAPSET(&solv->noobsoletes, p);
4782     }
4783
4784   map_init(&addedmap, pool->nsolvables);
4785   map_init(&installcandidatemap, pool->nsolvables);
4786   queue_init(&q);
4787
4788   /*
4789    * always install our system solvable
4790    */
4791   MAPSET(&addedmap, SYSTEMSOLVABLE);
4792   queue_push(&solv->decisionq, SYSTEMSOLVABLE);
4793   queue_push(&solv->decisionq_why, 0);
4794   solv->decisionmap[SYSTEMSOLVABLE] = 1; /* installed at level '1' */
4795
4796   now = sat_timems(0);
4797   /*
4798    * create rules for all package that could be involved with the solving
4799    * so called: rpm rules
4800    *
4801    */
4802   if (installed)
4803     {
4804       oldnrules = solv->nrules;
4805       POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for installed solvables ***\n");
4806       FOR_REPO_SOLVABLES(installed, p, s)
4807         addrpmrulesforsolvable(solv, s, &addedmap);
4808       POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for installed solvables\n", solv->nrules - oldnrules);
4809       POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for updaters of installed solvables ***\n");
4810       oldnrules = solv->nrules;
4811       FOR_REPO_SOLVABLES(installed, p, s)
4812         addrpmrulesforupdaters(solv, s, &addedmap, 1);
4813       POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for updaters of installed solvables\n", solv->nrules - oldnrules);
4814     }
4815
4816   /*
4817    * create rules for all packages involved in the job
4818    * (to be installed or removed)
4819    */
4820
4821   POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for packages involved with a job ***\n");
4822   oldnrules = solv->nrules;
4823   for (i = 0; i < job->count; i += 2)
4824     {
4825       how = job->elements[i];
4826       what = job->elements[i + 1];
4827       select = how & SOLVER_SELECTMASK;
4828
4829       switch (how & SOLVER_JOBMASK)
4830         {
4831         case SOLVER_INSTALL:
4832           FOR_JOB_SELECT(p, pp, select, what)
4833             {
4834               MAPSET(&installcandidatemap, p);
4835               addrpmrulesforsolvable(solv, pool->solvables + p, &addedmap);
4836             }
4837           break;
4838         case SOLVER_DISTUPGRADE:
4839           if (!solv->distupgrade)
4840             hasdupjob = 1;
4841           break;
4842         default:
4843           break;
4844         }
4845     }
4846   POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules for packages involved in a job\n", solv->nrules - oldnrules);
4847
4848   POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** create rpm rules for recommended/suggested packages ***\n");
4849
4850   oldnrules = solv->nrules;
4851
4852     /*
4853      * add rules for suggests, enhances
4854      */
4855   addrpmrulesforweak(solv, &addedmap);
4856   POOL_DEBUG(SAT_DEBUG_STATS, "added %d rpm rules because of weak dependencies\n", solv->nrules - oldnrules);
4857
4858   IF_POOLDEBUG (SAT_DEBUG_STATS)
4859     {
4860       int possible = 0, installable = 0;
4861       for (i = 1; i < pool->nsolvables; i++)
4862         {
4863           if (pool_installable(pool, pool->solvables + i))
4864             installable++;
4865           if (MAPTST(&addedmap, i))
4866             possible++;
4867         }
4868       POOL_DEBUG(SAT_DEBUG_STATS, "%d of %d installable solvables considered for solving\n", possible, installable);
4869     }
4870
4871   /*
4872    * first pass done, we now have all the rpm rules we need.
4873    * unify existing rules before going over all job rules and
4874    * policy rules.
4875    * at this point the system is always solvable,
4876    * as an empty system (remove all packages) is a valid solution
4877    */
4878
4879   unifyrules(solv);                               /* remove duplicate rpm rules */
4880
4881   solv->rpmrules_end = solv->nrules;              /* mark end of rpm rules */
4882
4883   solv->directdecisions = solv->decisionq.count;
4884   POOL_DEBUG(SAT_DEBUG_STATS, "rpm rule memory usage: %d K\n", solv->nrules * (int)sizeof(Rule) / 1024);
4885   POOL_DEBUG(SAT_DEBUG_STATS, "decisions so far: %d\n", solv->decisionq.count);
4886   POOL_DEBUG(SAT_DEBUG_STATS, "rpm rule creation took %d ms\n", sat_timems(now));
4887
4888   /* create dup maps if needed. We need the maps to create our
4889    * update rules */
4890   if (hasdupjob)
4891     createdupmaps(solv, job);
4892
4893   /*
4894    * create feature rules
4895    *
4896    * foreach installed:
4897    *   create assertion (keep installed, if no update available)
4898    *   or
4899    *   create update rule (A|update1(A)|update2(A)|...)
4900    *
4901    * those are used later on to keep a version of the installed packages in
4902    * best effort mode
4903    */
4904
4905   POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** Add feature rules ***\n");
4906   solv->featurerules = solv->nrules;              /* mark start of feature rules */
4907   if (installed)
4908     {
4909         /* foreach possibly installed solvable */
4910       for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
4911         {
4912           if (s->repo != installed)
4913             {
4914               addrule(solv, 0, 0);      /* create dummy rule */
4915               continue;
4916             }
4917           addupdaterule(solv, s, 1);    /* allow s to be updated */
4918         }
4919         /*
4920          * assert one rule per installed solvable,
4921          * either an assertion (A)
4922          * or a possible update (A|update1(A)|update2(A)|...)
4923          */
4924       assert(solv->nrules - solv->featurerules == installed->end - installed->start);
4925     }
4926   solv->featurerules_end = solv->nrules;
4927
4928     /*
4929      * Add update rules for installed solvables
4930      *
4931      * almost identical to feature rules
4932      * except that downgrades/archchanges/vendorchanges are not allowed
4933      */
4934
4935   POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** Add update rules ***\n");
4936   solv->updaterules = solv->nrules;
4937
4938   if (installed)
4939     { /* foreach installed solvables */
4940       /* we create all update rules, but disable some later on depending on the job */
4941       for (i = installed->start, s = pool->solvables + i; i < installed->end; i++, s++)
4942         {
4943           Rule *sr;
4944
4945           if (s->repo != installed)
4946             {
4947               addrule(solv, 0, 0);      /* create dummy rule */
4948               continue;
4949             }
4950           addupdaterule(solv, s, 0);    /* allowall = 0: downgrades not allowed */
4951             /*
4952              * check for and remove duplicate
4953              */
4954           r = solv->rules + solv->nrules - 1;           /* r: update rule */
4955           sr = r - (installed->end - installed->start); /* sr: feature rule */
4956           /* it's orphaned if there is no feature rule or the feature rule
4957            * consists just of the installed package */
4958           if (!sr->p || (sr->p == i && !sr->d && !sr->w2))
4959             queue_push(&solv->orphaned, i);
4960           if (!r->p)
4961             {
4962               assert(solv->distupgrade && !sr->p);
4963               continue;
4964             }
4965           unifyrules_sortcmp_data = pool;
4966           if (!unifyrules_sortcmp(r, sr))
4967             {
4968               /* identical rule, kill unneeded one */
4969               if (solv->allowuninstall)
4970                 {
4971                   /* keep feature rule, make it weak */
4972                   memset(r, 0, sizeof(*r));
4973                   queue_push(&solv->weakruleq, sr - solv->rules);
4974                 }
4975               else
4976                 {
4977                   /* keep update rule */
4978                   memset(sr, 0, sizeof(*sr));
4979                 }
4980             }
4981           else if (solv->allowuninstall)
4982             {
4983               /* make both feature and update rule weak */
4984               queue_push(&solv->weakruleq, r - solv->rules);
4985               queue_push(&solv->weakruleq, sr - solv->rules);
4986             }
4987           else
4988             disablerule(solv, sr);
4989         }
4990       /* consistency check: we added a rule for _every_ installed solvable */
4991       assert(solv->nrules - solv->updaterules == installed->end - installed->start);
4992     }
4993   solv->updaterules_end = solv->nrules;
4994
4995
4996   /*
4997    * now add all job rules
4998    */
4999
5000   POOL_DEBUG(SAT_DEBUG_SCHUBI, "*** Add JOB rules ***\n");
5001
5002   solv->jobrules = solv->nrules;
5003   for (i = 0; i < job->count; i += 2)
5004     {
5005       oldnrules = solv->nrules;
5006
5007       how = job->elements[i];
5008       what = job->elements[i + 1];
5009       weak = how & SOLVER_WEAK;
5010       select = how & SOLVER_SELECTMASK;
5011       switch (how & SOLVER_JOBMASK)
5012         {
5013         case SOLVER_INSTALL:
5014           POOL_DEBUG(SAT_DEBUG_JOB, "job: %sinstall %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
5015           if (select == SOLVER_SOLVABLE)
5016             {
5017               p = what;
5018               d = 0;
5019             }
5020           else
5021             {
5022               queue_empty(&q);
5023               FOR_JOB_SELECT(p, pp, select, what)
5024                 queue_push(&q, p);
5025               if (!q.count)
5026                 {
5027                   /* no candidate found, make this an impossible rule */
5028                   queue_push(&q, -SYSTEMSOLVABLE);
5029                 }
5030               p = queue_shift(&q);      /* get first candidate */
5031               d = !q.count ? 0 : pool_queuetowhatprovides(pool, &q);    /* internalize */
5032             }
5033           addrule(solv, p, d);          /* add install rule */
5034           queue_push(&solv->ruletojob, i);
5035           if (weak)
5036             queue_push(&solv->weakruleq, solv->nrules - 1);
5037           break;
5038         case SOLVER_ERASE:
5039           POOL_DEBUG(SAT_DEBUG_JOB, "job: %serase %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
5040           if (select == SOLVER_SOLVABLE && solv->installed && pool->solvables[what].repo == solv->installed)
5041             {
5042               /* special case for "erase a specific solvable": we also
5043                * erase all other solvables with that name, so that they
5044                * don't get picked up as replacement */
5045               name = pool->solvables[what].name;
5046               FOR_PROVIDES(p, pp, name)
5047                 {
5048                   if (p == what)
5049                     continue;
5050                   s = pool->solvables + p;
5051                   if (s->name != name)
5052                     continue;
5053                   /* keep other versions installed */
5054                   if (s->repo == solv->installed)
5055                     continue;
5056                   /* keep installcandidates of other jobs */
5057                   if (MAPTST(&installcandidatemap, p))
5058                     continue;
5059                   addrule(solv, -p, 0);                 /* remove by Id */
5060                   queue_push(&solv->ruletojob, i);
5061                   if (weak)
5062                     queue_push(&solv->weakruleq, solv->nrules - 1);
5063                 }
5064             }
5065           FOR_JOB_SELECT(p, pp, select, what)
5066             {
5067               addrule(solv, -p, 0);
5068               queue_push(&solv->ruletojob, i);
5069               if (weak)
5070                 queue_push(&solv->weakruleq, solv->nrules - 1);
5071             }
5072           break;
5073
5074         case SOLVER_UPDATE:
5075           POOL_DEBUG(SAT_DEBUG_JOB, "job: %supdate %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
5076           FOR_JOB_SELECT(p, pp, select, what)
5077             {
5078               s = pool->solvables + p;
5079               if (!solv->installed || s->repo != solv->installed)
5080                 continue;
5081               if (!solv->updatemap.size)
5082                 map_init(&solv->updatemap, pool->nsolvables);
5083               MAPSET(&solv->updatemap, p);
5084             }
5085           break;
5086         case SOLVER_WEAKENDEPS:
5087           POOL_DEBUG(SAT_DEBUG_JOB, "job: %sweaken deps %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
5088           if (select != SOLVER_SOLVABLE)
5089             break;
5090           s = pool->solvables + what;
5091           weaken_solvable_deps(solv, what);
5092           break;
5093         case SOLVER_NOOBSOLETES:
5094           POOL_DEBUG(SAT_DEBUG_JOB, "job: %sno obsolete %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
5095           break;
5096         case SOLVER_LOCK:
5097           POOL_DEBUG(SAT_DEBUG_JOB, "job: %slock %s\n", weak ? "weak " : "", solver_select2str(solv, select, what));
5098           FOR_JOB_SELECT(p, pp, select, what)
5099             {
5100               s = pool->solvables + p;
5101               if (installed && s->repo == installed)
5102                 addrule(solv, p, 0);
5103               else
5104                 addrule(solv, -p, 0);
5105               queue_push(&solv->ruletojob, i);
5106               if (weak)
5107                 queue_push(&solv->weakruleq, solv->nrules - 1);
5108             }
5109           break;
5110         case SOLVER_DISTUPGRADE:
5111           POOL_DEBUG(SAT_DEBUG_JOB, "job: distupgrade repo #%d\n", what);
5112           break;
5113         default:
5114           POOL_DEBUG(SAT_DEBUG_JOB, "job: unknown job\n");
5115           break;
5116         }
5117
5118         /*
5119          * debug
5120          */
5121
5122       IF_POOLDEBUG (SAT_DEBUG_JOB)
5123         {
5124           int j;
5125           if (solv->nrules == oldnrules)
5126             POOL_DEBUG(SAT_DEBUG_JOB, " - no rule created\n");
5127           for (j = oldnrules; j < solv->nrules; j++)
5128             {
5129               POOL_DEBUG(SAT_DEBUG_JOB, " - job ");
5130               solver_printrule(solv, SAT_DEBUG_JOB, solv->rules + j);
5131             }
5132         }
5133     }
5134   assert(solv->ruletojob.count == solv->nrules - solv->jobrules);
5135   solv->jobrules_end = solv->nrules;
5136
5137   /* now create infarch and dup rules */
5138   addinfarchrules(solv, &addedmap);
5139   if (hasdupjob)
5140     {
5141       addduprules(solv, &addedmap);
5142       freedupmaps(solv);        /* no longer needed */
5143     }
5144   else
5145     solv->duprules = solv->duprules_end = solv->nrules;
5146
5147     /* all rules created
5148      * --------------------------------------------------------------
5149      * prepare for solving
5150      */
5151
5152   /* free unneeded memory */
5153   map_free(&addedmap);
5154   map_free(&installcandidatemap);
5155   queue_free(&q);
5156
5157   POOL_DEBUG(SAT_DEBUG_STATS, "%d rpm rules, %d job rules, %d infarch rules, %d dup rules\n", solv->rpmrules_end - 1, solv->jobrules_end - solv->jobrules, solv->infarchrules_end - solv->infarchrules, solv->duprules_end - solv->duprules);
5158
5159   /* create weak map */
5160   map_init(&solv->weakrulemap, solv->nrules);
5161   for (i = 0; i < solv->weakruleq.count; i++)
5162     {
5163       p = solv->weakruleq.elements[i];
5164       MAPSET(&solv->weakrulemap, p);
5165     }
5166
5167   /* all new rules are learnt after this point */
5168   solv->learntrules = solv->nrules;
5169
5170   /* create assertion index. it is only used to speed up
5171    * makeruledecsions() a bit */
5172   for (i = 1, r = solv->rules + i; i < solv->nrules; i++, r++)
5173     if (r->p && !r->w2 && (r->d == 0 || r->d == -1))
5174       queue_push(&solv->ruleassertions, i);
5175
5176   /* disable update rules that conflict with our job */
5177   disablepolicyrules(solv, job);
5178
5179   /* make decisions based on job/update assertions */
5180   makeruledecisions(solv);
5181
5182   /* create watches chains */
5183   makewatches(solv);
5184
5185   POOL_DEBUG(SAT_DEBUG_STATS, "problems so far: %d\n", solv->problems.count);
5186
5187   /*
5188    * ********************************************
5189    * solve!
5190    * ********************************************
5191    */
5192
5193   now = sat_timems(0);
5194   run_solver(solv, 1, solv->dontinstallrecommended ? 0 : 1);
5195   POOL_DEBUG(SAT_DEBUG_STATS, "solver took %d ms\n", sat_timems(now));
5196
5197   queue_init(&redoq);
5198   goterase = 0;
5199   /* disable all erase jobs (including weak "keep uninstalled" rules) */
5200   for (i = solv->jobrules, r = solv->rules + i; i < solv->jobrules_end; i++, r++)
5201     {
5202       if (r->d < 0)     /* disabled ? */
5203         continue;
5204       if (r->p > 0)     /* install job? */
5205         continue;
5206       disablerule(solv, r);
5207       goterase++;
5208     }
5209
5210   if (goterase)
5211     {
5212       enabledisablelearntrules(solv);
5213       removedisabledconflicts(solv, &redoq);
5214     }
5215
5216   /*
5217    * find recommended packages
5218    */
5219
5220   /* if redoq.count == 0 we already found all recommended in the
5221    * solver run */
5222   if (redoq.count || solv->dontinstallrecommended || !solv->dontshowinstalledrecommended || solv->ignorealreadyrecommended)
5223     {
5224       Id rec, *recp, p, pp;
5225
5226       /* create map of all recommened packages */
5227       solv->recommends_index = -1;
5228       MAPZERO(&solv->recommendsmap);
5229       for (i = 0; i < solv->decisionq.count; i++)
5230         {
5231           p = solv->decisionq.elements[i];
5232           if (p < 0)
5233             continue;
5234           s = pool->solvables + p;
5235           if (s->recommends)
5236             {
5237               recp = s->repo->idarraydata + s->recommends;
5238               while ((rec = *recp++) != 0)
5239                 {
5240                   FOR_PROVIDES(p, pp, rec)
5241                     if (solv->decisionmap[p] > 0)
5242                       break;
5243                   if (p)
5244                     {
5245                       if (!solv->dontshowinstalledrecommended)
5246                         {
5247                           FOR_PROVIDES(p, pp, rec)
5248                             if (solv->decisionmap[p] > 0)
5249                               MAPSET(&solv->recommendsmap, p);
5250                         }
5251                       continue; /* p != 0: already fulfilled */
5252                     }
5253                   FOR_PROVIDES(p, pp, rec)
5254                     MAPSET(&solv->recommendsmap, p);
5255                 }
5256             }
5257         }
5258       for (i = 1; i < pool->nsolvables; i++)
5259         {
5260           if (solv->decisionmap[i] < 0)
5261             continue;
5262           if (solv->decisionmap[i] > 0 && solv->dontshowinstalledrecommended)
5263             continue;
5264           s = pool->solvables + i;
5265           if (!MAPTST(&solv->recommendsmap, i))
5266             {
5267               if (!s->supplements)
5268                 continue;
5269               if (!pool_installable(pool, s))
5270                 continue;
5271               if (!solver_is_supplementing(solv, s))
5272                 continue;
5273             }
5274           if (solv->dontinstallrecommended)
5275             queue_push(&solv->recommendations, i);
5276           else
5277             queue_pushunique(&solv->recommendations, i);
5278         }
5279       /* we use MODE_SUGGEST here so that repo prio is ignored */
5280       policy_filter_unwanted(solv, &solv->recommendations, POLICY_MODE_SUGGEST);
5281     }
5282
5283   /*
5284    * find suggested packages
5285    */
5286
5287   if (1)
5288     {
5289       Id sug, *sugp, p, pp;
5290
5291       /* create map of all suggests that are still open */
5292       solv->recommends_index = -1;
5293       MAPZERO(&solv->suggestsmap);
5294       for (i = 0; i < solv->decisionq.count; i++)
5295         {
5296           p = solv->decisionq.elements[i];
5297           if (p < 0)
5298             continue;
5299           s = pool->solvables + p;
5300           if (s->suggests)
5301             {
5302               sugp = s->repo->idarraydata + s->suggests;
5303               while ((sug = *sugp++) != 0)
5304                 {
5305                   FOR_PROVIDES(p, pp, sug)
5306                     if (solv->decisionmap[p] > 0)
5307                       break;
5308                   if (p)
5309                     {
5310                       if (!solv->dontshowinstalledrecommended)
5311                         {
5312                           FOR_PROVIDES(p, pp, sug)
5313                             if (solv->decisionmap[p] > 0)
5314                               MAPSET(&solv->suggestsmap, p);
5315                         }
5316                       continue; /* already fulfilled */
5317                     }
5318                   FOR_PROVIDES(p, pp, sug)
5319                     MAPSET(&solv->suggestsmap, p);
5320                 }
5321             }
5322         }
5323       for (i = 1; i < pool->nsolvables; i++)
5324         {
5325           if (solv->decisionmap[i] < 0)
5326             continue;
5327           if (solv->decisionmap[i] > 0 && solv->dontshowinstalledrecommended)
5328             continue;
5329           s = pool->solvables + i;
5330           if (!MAPTST(&solv->suggestsmap, i))
5331             {
5332               if (!s->enhances)
5333                 continue;
5334               if (!pool_installable(pool, s))
5335                 continue;
5336               if (!solver_is_enhancing(solv, s))
5337                 continue;
5338             }
5339           queue_push(&solv->suggestions, i);
5340         }
5341       policy_filter_unwanted(solv, &solv->suggestions, POLICY_MODE_SUGGEST);
5342     }
5343
5344   if (redoq.count)
5345     {
5346       /* restore decisionmap */
5347       for (i = 0; i < redoq.count; i += 2)
5348         solv->decisionmap[redoq.elements[i]] = redoq.elements[i + 1];
5349     }
5350
5351     /*
5352      * if unsolvable, prepare solutions
5353      */
5354
5355   if (solv->problems.count)
5356     {
5357       int recocount = solv->recommendations.count;
5358       solv->recommendations.count = 0;  /* so that revert() doesn't mess with it */
5359       queue_empty(&redoq);
5360       for (i = 0; i < solv->decisionq.count; i++)
5361         {
5362           Id p = solv->decisionq.elements[i];
5363           queue_push(&redoq, p);
5364           queue_push(&redoq, solv->decisionq_why.elements[i]);
5365           queue_push(&redoq, solv->decisionmap[p > 0 ? p : -p]);
5366         }
5367       problems_to_solutions(solv, job);
5368       memset(solv->decisionmap, 0, pool->nsolvables * sizeof(Id));
5369       queue_empty(&solv->decisionq);
5370       queue_empty(&solv->decisionq_why);
5371       for (i = 0; i < redoq.count; i += 3)
5372         {
5373           Id p = redoq.elements[i];
5374           queue_push(&solv->decisionq, p);
5375           queue_push(&solv->decisionq_why, redoq.elements[i + 1]);
5376           solv->decisionmap[p > 0 ? p : -p] = redoq.elements[i + 2];
5377         }
5378       solv->recommendations.count = recocount;
5379     }
5380
5381   queue_free(&redoq);
5382   POOL_DEBUG(SAT_DEBUG_STATS, "final solver statistics: %d learned rules, %d unsolvable\n", solv->stats_learned, solv->stats_unsolvable);
5383   POOL_DEBUG(SAT_DEBUG_STATS, "solver_solve took %d ms\n", sat_timems(solve_start));
5384   solv->job = 0;
5385 }
5386
5387 /***********************************************************************/
5388 /* disk usage computations */
5389
5390 /*-------------------------------------------------------------------
5391  *
5392  * calculate DU changes
5393  */
5394
5395 void
5396 solver_calc_duchanges(Solver *solv, DUChanges *mps, int nmps)
5397 {
5398   Map installedmap;
5399
5400   solver_create_state_maps(solv, &installedmap, 0);
5401   pool_calc_duchanges(solv->pool, &installedmap, mps, nmps);
5402   map_free(&installedmap);
5403 }
5404
5405
5406 /*-------------------------------------------------------------------
5407  *
5408  * calculate changes in install size
5409  */
5410
5411 int
5412 solver_calc_installsizechange(Solver *solv)
5413 {
5414   Map installedmap;
5415   int change;
5416
5417   solver_create_state_maps(solv, &installedmap, 0);
5418   change = pool_calc_installsizechange(solv->pool, &installedmap);
5419   map_free(&installedmap);
5420   return change;
5421 }
5422
5423 void
5424 solver_trivial_installable(Solver *solv, Queue *pkgs, Queue *res)
5425 {
5426   Map installedmap;
5427   solver_create_state_maps(solv, &installedmap, 0);
5428   pool_trivial_installable_noobsoletesmap(solv->pool, &installedmap, pkgs, res, solv->noobsoletes.size ? &solv->noobsoletes : 0);
5429   map_free(&installedmap);
5430 }
5431
5432
5433 #define FIND_INVOLVED_DEBUG 0
5434 void
5435 solver_find_involved(Solver *solv, Queue *installedq, Solvable *ts, Queue *q)
5436 {
5437   Pool *pool = solv->pool;
5438   Map im;
5439   Map installedm;
5440   Solvable *s;
5441   Queue iq;
5442   Queue installedq_internal;
5443   Id tp, ip, p, pp, req, *reqp, sup, *supp;
5444   int i, count;
5445
5446   tp = ts - pool->solvables;
5447   queue_init(&iq);
5448   queue_init(&installedq_internal);
5449   map_init(&im, pool->nsolvables);
5450   map_init(&installedm, pool->nsolvables);
5451
5452   if (!installedq)
5453     {
5454       installedq = &installedq_internal;
5455       if (solv->installed)
5456         {
5457           for (ip = solv->installed->start; ip < solv->installed->end; ip++)
5458             {
5459               s = pool->solvables + ip;
5460               if (s->repo != solv->installed)
5461                 continue;
5462               queue_push(installedq, ip);
5463             }
5464         }
5465     }
5466   for (i = 0; i < installedq->count; i++)
5467     {
5468       ip = installedq->elements[i];
5469       MAPSET(&installedm, ip);
5470       MAPSET(&im, ip);
5471     }
5472
5473   queue_push(&iq, ts - pool->solvables);
5474   while (iq.count)
5475     {
5476       ip = queue_shift(&iq);
5477       if (!MAPTST(&im, ip))
5478         continue;
5479       if (!MAPTST(&installedm, ip))
5480         continue;
5481       MAPCLR(&im, ip);
5482       s = pool->solvables + ip;
5483 #if FIND_INVOLVED_DEBUG
5484       printf("hello %s\n", solvable2str(pool, s));
5485 #endif
5486       if (s->requires)
5487         {
5488           reqp = s->repo->idarraydata + s->requires;
5489           while ((req = *reqp++) != 0)
5490             {
5491               if (req == SOLVABLE_PREREQMARKER)
5492                 continue;
5493               /* count number of installed packages that match */
5494               count = 0;
5495               FOR_PROVIDES(p, pp, req)
5496                 if (MAPTST(&installedm, p))
5497                   count++;
5498               if (count > 1)
5499                 continue;
5500               FOR_PROVIDES(p, pp, req)
5501                 {
5502                   if (MAPTST(&im, p))
5503                     {
5504 #if FIND_INVOLVED_DEBUG
5505                       printf("%s requires %s\n", solvable2str(pool, pool->solvables + ip), solvable2str(pool, pool->solvables + p));
5506 #endif
5507                       queue_push(&iq, p);
5508                     }
5509                 }
5510             }
5511         }
5512       if (s->recommends)
5513         {
5514           reqp = s->repo->idarraydata + s->recommends;
5515           while ((req = *reqp++) != 0)
5516             {
5517               count = 0;
5518               FOR_PROVIDES(p, pp, req)
5519                 if (MAPTST(&installedm, p))
5520                   count++;
5521               if (count > 1)
5522                 continue;
5523               FOR_PROVIDES(p, pp, req)
5524                 {
5525                   if (MAPTST(&im, p))
5526                     {
5527 #if FIND_INVOLVED_DEBUG
5528                       printf("%s recommends %s\n", solvable2str(pool, pool->solvables + ip), solvable2str(pool, pool->solvables + p));
5529 #endif
5530                       queue_push(&iq, p);
5531                     }
5532                 }
5533             }
5534         }
5535       if (!iq.count)
5536         {
5537           /* supplements pass */
5538           for (i = 0; i < installedq->count; i++)
5539             {
5540               ip = installedq->elements[i];
5541               s = pool->solvables + ip;
5542               if (!s->supplements)
5543                 continue;
5544               if (!MAPTST(&im, ip))
5545                 continue;
5546               supp = s->repo->idarraydata + s->supplements;
5547               while ((sup = *supp++) != 0)
5548                 if (!dep_possible(solv, sup, &im) && dep_possible(solv, sup, &installedm))
5549                   break;
5550               /* no longer supplemented, also erase */
5551               if (sup)
5552                 {
5553 #if FIND_INVOLVED_DEBUG
5554                   printf("%s supplemented\n", solvable2str(pool, pool->solvables + ip));
5555 #endif
5556                   queue_push(&iq, ip);
5557                 }
5558             }
5559         }
5560     }
5561
5562   for (i = 0; i < installedq->count; i++)
5563     {
5564       ip = installedq->elements[i];
5565       if (MAPTST(&im, ip))
5566         queue_push(&iq, ip);
5567     }
5568
5569   while (iq.count)
5570     {
5571       ip = queue_shift(&iq);
5572       if (!MAPTST(&installedm, ip))
5573         continue;
5574       s = pool->solvables + ip;
5575 #if FIND_INVOLVED_DEBUG
5576       printf("bye %s\n", solvable2str(pool, s));
5577 #endif
5578       if (s->requires)
5579         {
5580           reqp = s->repo->idarraydata + s->requires;
5581           while ((req = *reqp++) != 0)
5582             {
5583               FOR_PROVIDES(p, pp, req)
5584                 {
5585                   if (!MAPTST(&im, p))
5586                     {
5587                       if (p == tp)
5588                         continue;
5589 #if FIND_INVOLVED_DEBUG
5590                       printf("%s requires %s\n", solvable2str(pool, pool->solvables + ip), solvable2str(pool, pool->solvables + p));
5591 #endif
5592                       MAPSET(&im, p);
5593                       queue_push(&iq, p);
5594                     }
5595                 }
5596             }
5597         }
5598       if (s->recommends)
5599         {
5600           reqp = s->repo->idarraydata + s->recommends;
5601           while ((req = *reqp++) != 0)
5602             {
5603               FOR_PROVIDES(p, pp, req)
5604                 {
5605                   if (!MAPTST(&im, p))
5606                     {
5607                       if (p == tp)
5608                         continue;
5609 #if FIND_INVOLVED_DEBUG
5610                       printf("%s recommends %s\n", solvable2str(pool, pool->solvables + ip), solvable2str(pool, pool->solvables + p));
5611 #endif
5612                       MAPSET(&im, p);
5613                       queue_push(&iq, p);
5614                     }
5615                 }
5616             }
5617         }
5618       if (!iq.count)
5619         {
5620           /* supplements pass */
5621           for (i = 0; i < installedq->count; i++)
5622             {
5623               ip = installedq->elements[i];
5624               if (ip == tp)
5625                 continue;
5626               s = pool->solvables + ip;
5627               if (!s->supplements)
5628                 continue;
5629               if (MAPTST(&im, ip))
5630                 continue;
5631               supp = s->repo->idarraydata + s->supplements;
5632               while ((sup = *supp++) != 0)
5633                 if (dep_possible(solv, sup, &im))
5634                   break;
5635               if (sup)
5636                 {
5637 #if FIND_INVOLVED_DEBUG
5638                   printf("%s supplemented\n", solvable2str(pool, pool->solvables + ip));
5639 #endif
5640                   MAPSET(&im, ip);
5641                   queue_push(&iq, ip);
5642                 }
5643             }
5644         }
5645     }
5646
5647   queue_free(&iq);
5648
5649   /* convert map into result */
5650   for (i = 0; i < installedq->count; i++)
5651     {
5652       ip = installedq->elements[i];
5653       if (MAPTST(&im, ip))
5654         continue;
5655       if (ip == ts - pool->solvables)
5656         continue;
5657       queue_push(q, ip);
5658     }
5659   map_free(&im);
5660   map_free(&installedm);
5661   queue_free(&installedq_internal);
5662 }
5663
5664 /* EOF */