src/rules.c

   1 /*
   2  * Copyright (c) 2007-2009, Novell Inc.
   3  *
   4  * This program is licensed under the BSD license, read LICENSE.BSD
   5  * for further information
   6  */
   7
   8 /*
   9  * rules.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 "solver_private.h"
  22 #include "bitmap.h"
  23 #include "pool.h"
  24 #include "poolarch.h"
  25 #include "util.h"
  26 #include "evr.h"
  27 #include "policy.h"
  28 #include "solverdebug.h"
  29
  30 #define RULES_BLOCK 63
  31
  32 static void addrpmruleinfo(Solver *solv, Id p, Id d, int type, Id dep);
  33 static void solver_createcleandepsmap(Solver *solv, Map *cleandepsmap, int unneeded);
  34
  35 /*-------------------------------------------------------------------
  36  * Check if dependency is possible
  37  *
  38  * mirrors solver_dep_fulfilled but uses map m instead of the decisionmap.
  39  * used in solver_addrpmrulesforweak and solver_createcleandepsmap.
  40  */
  41
  42 static inline int
  43 dep_possible(Solver *solv, Id dep, Map *m)
  44 {
  45   Pool *pool = solv->pool;
  46   Id p, pp;
  47
  48   if (ISRELDEP(dep))
  49     {
  50       Reldep *rd = GETRELDEP(pool, dep);
  51       if (rd->flags >= 8)
  52         {
  53           if (rd->flags == REL_AND)
  54             {
  55               if (!dep_possible(solv, rd->name, m))
  56                 return 0;
  57               return dep_possible(solv, rd->evr, m);
  58             }
  59           if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
  60             return solver_splitprovides(solv, rd->evr);
  61           if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
  62             return solver_dep_installed(solv, rd->evr);
  63         }
  64     }
  65   FOR_PROVIDES(p, pp, dep)
  66     {
  67       if (MAPTST(m, p))
  68         return 1;
  69     }
  70   return 0;
  71 }
  72
  73 /********************************************************************
  74  *
  75  * Rule handling
  76  *
  77  * - unify rules, remove duplicates
  78  */
  79
  80 /*-------------------------------------------------------------------
  81  *
  82  * compare rules for unification sort
  83  *
  84  */
  85
  86 static int
  87 unifyrules_sortcmp(const void *ap, const void *bp, void *dp)
  88 {
  89   Pool *pool = dp;
  90   Rule *a = (Rule *)ap;
  91   Rule *b = (Rule *)bp;
  92   Id *ad, *bd;
  93   int x;
  94
  95   x = a->p - b->p;
  96   if (x)
  97     return x;                          /* p differs */
  98
  99   /* identical p */
 100   if (a->d == 0 && b->d == 0)
 101     return a->w2 - b->w2;              /* assertion: return w2 diff */
 102
 103   if (a->d == 0)                       /* a is assertion, b not */
 104     {
 105       x = a->w2 - pool->whatprovidesdata[b->d];
 106       return x ? x : -1;
 107     }
 108
 109   if (b->d == 0)                       /* b is assertion, a not */
 110     {
 111       x = pool->whatprovidesdata[a->d] - b->w2;
 112       return x ? x : 1;
 113     }
 114
 115   /* compare whatprovidesdata */
 116   ad = pool->whatprovidesdata + a->d;
 117   bd = pool->whatprovidesdata + b->d;
 118   while (*bd)
 119     if ((x = *ad++ - *bd++) != 0)
 120       return x;
 121   return *ad;
 122 }
 123
 124 int
 125 solver_rulecmp(Solver *solv, Rule *r1, Rule *r2)
 126 {
 127   return unifyrules_sortcmp(r1, r2, solv->pool);
 128 }
 129
 130
 131 /*-------------------------------------------------------------------
 132  *
 133  * unify rules
 134  * go over all rules and remove duplicates
 135  */
 136
 137 void
 138 solver_unifyrules(Solver *solv)
 139 {
 140   Pool *pool = solv->pool;
 141   int i, j;
 142   Rule *ir, *jr;
 143
 144   if (solv->nrules <= 2)               /* nothing to unify */
 145     return;
 146
 147   /* sort rules first */
 148   solv_sort(solv->rules + 1, solv->nrules - 1, sizeof(Rule), unifyrules_sortcmp, solv->pool);
 149
 150   /* prune rules
 151    * i = unpruned
 152    * j = pruned
 153    */
 154   jr = 0;
 155   for (i = j = 1, ir = solv->rules + i; i < solv->nrules; i++, ir++)
 156     {
 157       if (jr && !unifyrules_sortcmp(ir, jr, pool))
 158         continue;                      /* prune! */
 159       jr = solv->rules + j++;          /* keep! */
 160       if (ir != jr)
 161         *jr = *ir;
 162     }
 163
 164   /* reduced count from nrules to j rules */
 165   POOL_DEBUG(SOLV_DEBUG_STATS, "pruned rules from %d to %d\n", solv->nrules, j);
 166
 167   /* adapt rule buffer */
 168   solv->nrules = j;
 169   solv->rules = solv_extend_resize(solv->rules, solv->nrules, sizeof(Rule), RULES_BLOCK);
 170
 171   /*
 172    * debug: log rule statistics
 173    */
 174   IF_POOLDEBUG (SOLV_DEBUG_STATS)
 175     {
 176       int binr = 0;
 177       int lits = 0;
 178       Id *dp;
 179       Rule *r;
 180
 181       for (i = 1; i < solv->nrules; i++)
 182         {
 183           r = solv->rules + i;
 184           if (r->d == 0)
 185             binr++;
 186           else
 187             {
 188               dp = solv->pool->whatprovidesdata + r->d;
 189               while (*dp++)
 190                 lits++;
 191             }
 192         }
 193       POOL_DEBUG(SOLV_DEBUG_STATS, "  binary: %d\n", binr);
 194       POOL_DEBUG(SOLV_DEBUG_STATS, "  normal: %d, %d literals\n", solv->nrules - 1 - binr, lits);
 195     }
 196 }
 197
 198 #if 0
 199
 200 /*
 201  * hash rule
 202  */
 203
 204 static Hashval
 205 hashrule(Solver *solv, Id p, Id d, int n)
 206 {
 207   unsigned int x = (unsigned int)p;
 208   int *dp;
 209
 210   if (n <= 1)
 211     return (x * 37) ^ (unsigned int)d;
 212   dp = solv->pool->whatprovidesdata + d;
 213   while (*dp)
 214     x = (x * 37) ^ (unsigned int)*dp++;
 215   return x;
 216 }
 217 #endif
 218
 219
 220 /*-------------------------------------------------------------------
 221  *
 222  */
 223
 224 /*
 225  * add rule
 226  *  p = direct literal; always < 0 for installed rpm rules
 227  *  d, if < 0 direct literal, if > 0 offset into whatprovides, if == 0 rule is assertion (look at p only)
 228  *
 229  *
 230  * A requires b, b provided by B1,B2,B3 => (-A|B1|B2|B3)
 231  *
 232  * p < 0 : pkg id of A
 233  * d > 0 : Offset in whatprovidesdata (list of providers of b)
 234  *
 235  * A conflicts b, b provided by B1,B2,B3 => (-A|-B1), (-A|-B2), (-A|-B3)
 236  * p < 0 : pkg id of A
 237  * d < 0 : Id of solvable (e.g. B1)
 238  *
 239  * d == 0: unary rule, assertion => (A) or (-A)
 240  *
 241  *   Install:    p > 0, d = 0   (A)             user requested install
 242  *   Remove:     p < 0, d = 0   (-A)            user requested remove (also: uninstallable)
 243  *   Requires:   p < 0, d > 0   (-A|B1|B2|...)  d: <list of providers for requirement of p>
 244  *   Updates:    p > 0, d > 0   (A|B1|B2|...)   d: <list of updates for solvable p>
 245  *   Conflicts:  p < 0, d < 0   (-A|-B)         either p (conflict issuer) or d (conflict provider) (binary rule)
 246  *                                              also used for obsoletes
 247  *   ?:          p > 0, d < 0   (A|-B)
 248  *   No-op ?:    p = 0, d = 0   (null)          (used as policy rule placeholder)
 249  *
 250  *   resulting watches:
 251  *   ------------------
 252  *   Direct assertion (no watch needed) --> d = 0, w1 = p, w2 = 0
 253  *   Binary rule: p = first literal, d = 0, w2 = second literal, w1 = p
 254  *   every other : w1 = p, w2 = whatprovidesdata[d];
 255  *   Disabled rule: w1 = 0
 256  *
 257  *   always returns a rule for non-rpm rules
 258  */
 259
 260 Rule *
 261 solver_addrule(Solver *solv, Id p, Id d)
 262 {
 263   Pool *pool = solv->pool;
 264   Rule *r = 0;
 265   Id *dp = 0;
 266
 267   int n = 0;                           /* number of literals in rule - 1
 268                                           0 = direct assertion (single literal)
 269                                           1 = binary rule
 270                                           >1 =
 271                                         */
 272
 273   /* it often happenes that requires lead to adding the same rpm rule
 274    * multiple times, so we prune those duplicates right away to make
 275    * the work for unifyrules a bit easier */
 276
 277   if (!solv->rpmrules_end)              /* we add rpm rules */
 278     {
 279       r = solv->rules + solv->nrules - 1;       /* get the last added rule */
 280       if (r->p == p && r->d == d && (d != 0 || !r->w2))
 281         return r;
 282     }
 283
 284     /*
 285      * compute number of literals (n) in rule
 286      */
 287
 288   if (d < 0)
 289     {
 290       /* always a binary rule */
 291       if (p == d)
 292         return 0;                      /* ignore self conflict */
 293       n = 1;
 294     }
 295   else if (d > 0)
 296     {
 297       for (dp = pool->whatprovidesdata + d; *dp; dp++, n++)
 298         if (*dp == -p)
 299           return 0;                     /* rule is self-fulfilling */
 300
 301       if (n == 1)                       /* convert to binary rule */
 302         d = dp[-1];
 303     }
 304
 305   if (n == 1 && p > d && !solv->rpmrules_end)
 306     {
 307       /* smallest literal first so we can find dups */
 308       n = p; p = d; d = n;             /* p <-> d */
 309       n = 1;                           /* re-set n, was used as temp var */
 310     }
 311
 312   /*
 313    * check for duplicate
 314    */
 315
 316   /* check if the last added rule (r) is exactly the same as what we're looking for. */
 317   if (r && n == 1 && !r->d && r->p == p && r->w2 == d)
 318     return r;  /* binary rule */
 319
 320     /* have n-ary rule with same first literal, check other literals */
 321   if (r && n > 1 && r->d && r->p == p)
 322     {
 323       /* Rule where d is an offset in whatprovidesdata */
 324       Id *dp2;
 325       if (d == r->d)
 326         return r;
 327       dp2 = pool->whatprovidesdata + r->d;
 328       for (dp = pool->whatprovidesdata + d; *dp; dp++, dp2++)
 329         if (*dp != *dp2)
 330           break;
 331       if (*dp == *dp2)
 332         return r;
 333    }
 334
 335   /*
 336    * allocate new rule
 337    */
 338
 339   /* extend rule buffer */
 340   solv->rules = solv_extend(solv->rules, solv->nrules, 1, sizeof(Rule), RULES_BLOCK);
 341   r = solv->rules + solv->nrules++;    /* point to rule space */
 342
 343     /*
 344      * r = new rule
 345      */
 346
 347   r->p = p;
 348   if (n == 0)
 349     {
 350       /* direct assertion, no watch needed */
 351       r->d = 0;
 352       r->w1 = p;
 353       r->w2 = 0;
 354     }
 355   else if (n == 1)
 356     {
 357       /* binary rule */
 358       r->d = 0;
 359       r->w1 = p;
 360       r->w2 = d;
 361     }
 362   else
 363     {
 364       r->d = d;
 365       r->w1 = p;
 366       r->w2 = pool->whatprovidesdata[d];
 367     }
 368   r->n1 = 0;
 369   r->n2 = 0;
 370
 371   IF_POOLDEBUG (SOLV_DEBUG_RULE_CREATION)
 372     {
 373       POOL_DEBUG(SOLV_DEBUG_RULE_CREATION, "  Add rule: ");
 374       solver_printrule(solv, SOLV_DEBUG_RULE_CREATION, r);
 375     }
 376
 377   return r;
 378 }
 379
 380
 381 /******************************************************************************
 382  ***
 383  *** rpm rule part: create rules representing the package dependencies
 384  ***
 385  ***/
 386
 387 /*
 388  *  special multiversion patch conflict handling:
 389  *  a patch conflict is also satisfied if some other
 390  *  version with the same name/arch that doesn't conflict
 391  *  gets installed. The generated rule is thus:
 392  *  -patch|-cpack|opack1|opack2|...
 393  */
 394 static Id
 395 makemultiversionconflict(Solver *solv, Id n, Id con)
 396 {
 397   Pool *pool = solv->pool;
 398   Solvable *s, *sn;
 399   Queue q;
 400   Id p, pp, qbuf[64];
 401
 402   sn = pool->solvables + n;
 403   queue_init_buffer(&q, qbuf, sizeof(qbuf)/sizeof(*qbuf));
 404   queue_push(&q, -n);
 405   FOR_PROVIDES(p, pp, sn->name)
 406     {
 407       s = pool->solvables + p;
 408       if (s->name != sn->name || s->arch != sn->arch)
 409         continue;
 410       if (!MAPTST(&solv->noobsoletes, p))
 411         continue;
 412       if (pool_match_nevr(pool, pool->solvables + p, con))
 413         continue;
 414       /* here we have a multiversion solvable that doesn't conflict */
 415       /* thus we're not in conflict if it is installed */
 416       queue_push(&q, p);
 417     }
 418   if (q.count == 1)
 419     return -n;  /* no other package found, generate normal conflict */
 420   return pool_queuetowhatprovides(pool, &q);
 421 }
 422
 423 static inline void
 424 addrpmrule(Solver *solv, Id p, Id d, int type, Id dep)
 425 {
 426   if (!solv->ruleinfoq)
 427     solver_addrule(solv, p, d);
 428   else
 429     addrpmruleinfo(solv, p, d, type, dep);
 430 }
 431
 432 /*-------------------------------------------------------------------
 433  *
 434  * add (install) rules for solvable
 435  *
 436  * s: Solvable for which to add rules
 437  * m: m[s] = 1 for solvables which have rules, prevent rule duplication
 438  *
 439  * Algorithm: 'visit all nodes of a graph'. The graph nodes are
 440  *  solvables, the edges their dependencies.
 441  *  Starting from an installed solvable, this will create all rules
 442  *  representing the graph created by the solvables dependencies.
 443  *
 444  * for unfulfilled requirements, conflicts, obsoletes,....
 445  * add a negative assertion for solvables that are not installable
 446  *
 447  * It will also create rules for all solvables referenced by 's'
 448  *  i.e. descend to all providers of requirements of 's'
 449  *
 450  */
 451
 452 void
 453 solver_addrpmrulesforsolvable(Solver *solv, Solvable *s, Map *m)
 454 {
 455   Pool *pool = solv->pool;
 456   Repo *installed = solv->installed;
 457
 458   /* 'work' queue. keeps Ids of solvables we still have to work on.
 459      And buffer for it. */
 460   Queue workq;
 461   Id workqbuf[64];
 462
 463   int i;
 464     /* if to add rules for broken deps ('rpm -V' functionality)
 465      * 0 = yes, 1 = no
 466      */
 467   int dontfix;
 468     /* Id var and pointer for each dependency
 469      * (not used in parallel)
 470      */
 471   Id req, *reqp;
 472   Id con, *conp;
 473   Id obs, *obsp;
 474   Id rec, *recp;
 475   Id sug, *sugp;
 476   Id p, pp;             /* whatprovides loops */
 477   Id *dp;               /* ptr to 'whatprovides' */
 478   Id n;                 /* Id for current solvable 's' */
 479
 480   queue_init_buffer(&workq, workqbuf, sizeof(workqbuf)/sizeof(*workqbuf));
 481   queue_push(&workq, s - pool->solvables);      /* push solvable Id to work queue */
 482
 483   /* loop until there's no more work left */
 484   while (workq.count)
 485     {
 486       /*
 487        * n: Id of solvable
 488        * s: Pointer to solvable
 489        */
 490
 491       n = queue_shift(&workq);          /* 'pop' next solvable to work on from queue */
 492       if (m)
 493         {
 494           if (MAPTST(m, n))             /* continue if already visited */
 495             continue;
 496           MAPSET(m, n);                 /* mark as visited */
 497         }
 498
 499       s = pool->solvables + n;          /* s = Solvable in question */
 500
 501       dontfix = 0;
 502       if (installed                     /* Installed system available */
 503           && s->repo == installed       /* solvable is installed */
 504           && !solv->fixmap_all          /* NOT repair errors in rpm dependency graph */
 505           && !(solv->fixmap.size && MAPTST(&solv->fixmap, n - installed->start)))
 506         {
 507           dontfix = 1;                  /* dont care about broken rpm deps */
 508         }
 509
 510       if (!dontfix)
 511         {
 512           if (s->arch == ARCH_SRC || s->arch == ARCH_NOSRC
 513                 ? pool_disabled_solvable(pool, s)
 514                 : !pool_installable(pool, s))
 515             {
 516               POOL_DEBUG(SOLV_DEBUG_RULE_CREATION, "package %s [%d] is not installable\n", pool_solvable2str(pool, s), (Id)(s - pool->solvables));
 517               addrpmrule(solv, -n, 0, SOLVER_RULE_RPM_NOT_INSTALLABLE, 0);
 518             }
 519         }
 520
 521       /* yet another SUSE hack, sigh */
 522       if (pool->nscallback && !strncmp("product:", pool_id2str(pool, s->name), 8))
 523         {
 524           Id buddy = pool->nscallback(pool, pool->nscallbackdata, NAMESPACE_PRODUCTBUDDY, n);
 525           if (buddy > 0 && buddy != SYSTEMSOLVABLE && buddy != n && buddy < pool->nsolvables)
 526             {
 527               addrpmrule(solv, n, -buddy, SOLVER_RULE_RPM_PACKAGE_REQUIRES, solvable_selfprovidedep(pool->solvables + n));
 528               addrpmrule(solv, buddy, -n, SOLVER_RULE_RPM_PACKAGE_REQUIRES, solvable_selfprovidedep(pool->solvables + buddy));
 529               if (m && !MAPTST(m, buddy))
 530                 queue_push(&workq, buddy);
 531             }
 532         }
 533
 534       /*-----------------------------------------
 535        * check requires of s
 536        */
 537
 538       if (s->requires)
 539         {
 540           reqp = s->repo->idarraydata + s->requires;
 541           while ((req = *reqp++) != 0)            /* go through all requires */
 542             {
 543               if (req == SOLVABLE_PREREQMARKER)   /* skip the marker */
 544                 continue;
 545
 546               /* find list of solvables providing 'req' */
 547               dp = pool_whatprovides_ptr(pool, req);
 548
 549               if (*dp == SYSTEMSOLVABLE)          /* always installed */
 550                 continue;
 551
 552               if (dontfix)
 553                 {
 554                   /* the strategy here is to not insist on dependencies
 555                    * that are already broken. so if we find one provider
 556                    * that was already installed, we know that the
 557                    * dependency was not broken before so we enforce it */
 558
 559                   /* check if any of the providers for 'req' is installed */
 560                   for (i = 0; (p = dp[i]) != 0; i++)
 561                     {
 562                       if (pool->solvables[p].repo == installed)
 563                         break;          /* provider was installed */
 564                     }
 565                   /* didn't find an installed provider: previously broken dependency */
 566                   if (!p)
 567                     {
 568                       POOL_DEBUG(SOLV_DEBUG_RULE_CREATION, "ignoring broken requires %s of installed package %s\n", pool_dep2str(pool, req), pool_solvable2str(pool, s));
 569                       continue;
 570                     }
 571                 }
 572
 573               if (!*dp)
 574                 {
 575                   /* nothing provides req! */
 576                   POOL_DEBUG(SOLV_DEBUG_RULE_CREATION, "package %s [%d] is not installable (%s)\n", pool_solvable2str(pool, s), (Id)(s - pool->solvables), pool_dep2str(pool, req));
 577                   addrpmrule(solv, -n, 0, SOLVER_RULE_RPM_NOTHING_PROVIDES_DEP, req);
 578                   continue;
 579                 }
 580
 581               IF_POOLDEBUG (SOLV_DEBUG_RULE_CREATION)
 582                 {
 583                   POOL_DEBUG(SOLV_DEBUG_RULE_CREATION,"  %s requires %s\n", pool_solvable2str(pool, s), pool_dep2str(pool, req));
 584                   for (i = 0; dp[i]; i++)
 585                     POOL_DEBUG(SOLV_DEBUG_RULE_CREATION, "   provided by %s\n", pool_solvid2str(pool, dp[i]));
 586                 }
 587
 588               /* add 'requires' dependency */
 589               /* rule: (-requestor|provider1|provider2|...|providerN) */
 590               addrpmrule(solv, -n, dp - pool->whatprovidesdata, SOLVER_RULE_RPM_PACKAGE_REQUIRES, req);
 591
 592               /* descend the dependency tree
 593                  push all non-visited providers on the work queue */
 594               if (m)
 595                 {
 596                   for (; *dp; dp++)
 597                     {
 598                       if (!MAPTST(m, *dp))
 599                         queue_push(&workq, *dp);
 600                     }
 601                 }
 602
 603             } /* while, requirements of n */
 604
 605         } /* if, requirements */
 606
 607       /* that's all we check for src packages */
 608       if (s->arch == ARCH_SRC || s->arch == ARCH_NOSRC)
 609         continue;
 610
 611       /*-----------------------------------------
 612        * check conflicts of s
 613        */
 614
 615       if (s->conflicts)
 616         {
 617           int ispatch = 0;
 618
 619           /* we treat conflicts in patches a bit differen:
 620            * - nevr matching
 621            * - multiversion handling
 622            * XXX: we should really handle this different, looking
 623            * at the name is a bad hack
 624            */
 625           if (!strncmp("patch:", pool_id2str(pool, s->name), 6))
 626             ispatch = 1;
 627           conp = s->repo->idarraydata + s->conflicts;
 628           /* foreach conflicts of 's' */
 629           while ((con = *conp++) != 0)
 630             {
 631               /* foreach providers of a conflict of 's' */
 632               FOR_PROVIDES(p, pp, con)
 633                 {
 634                   if (ispatch && !pool_match_nevr(pool, pool->solvables + p, con))
 635                     continue;
 636                   /* dontfix: dont care about conflicts with already installed packs */
 637                   if (dontfix && pool->solvables[p].repo == installed)
 638                     continue;
 639                   /* p == n: self conflict */
 640                   if (p == n && pool->forbidselfconflicts)
 641                     {
 642                       if (ISRELDEP(con))
 643                         {
 644                           Reldep *rd = GETRELDEP(pool, con);
 645                           if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_OTHERPROVIDERS)
 646                             continue;
 647                         }
 648                       p = 0;    /* make it a negative assertion, aka 'uninstallable' */
 649                     }
 650                   if (p && ispatch && solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p) && ISRELDEP(con))
 651                     {
 652                       /* our patch conflicts with a noobsoletes (aka multiversion) package */
 653                       p = -makemultiversionconflict(solv, p, con);
 654                     }
 655                  /* rule: -n|-p: either solvable _or_ provider of conflict */
 656                   addrpmrule(solv, -n, -p, p ? SOLVER_RULE_RPM_PACKAGE_CONFLICT : SOLVER_RULE_RPM_SELF_CONFLICT, con);
 657                 }
 658             }
 659         }
 660
 661       /*-----------------------------------------
 662        * check obsoletes and implicit obsoletes of a package
 663        * if ignoreinstalledsobsoletes is not set, we're also checking
 664        * obsoletes of installed packages (like newer rpm versions)
 665        */
 666       if ((!installed || s->repo != installed) || !pool->noinstalledobsoletes)
 667         {
 668           int noobs = solv->noobsoletes.size && MAPTST(&solv->noobsoletes, n);
 669           int isinstalled = (installed && s->repo == installed);
 670           if (s->obsoletes && (!noobs || solv->keepexplicitobsoletes))
 671             {
 672               obsp = s->repo->idarraydata + s->obsoletes;
 673               /* foreach obsoletes */
 674               while ((obs = *obsp++) != 0)
 675                 {
 676                   /* foreach provider of an obsoletes of 's' */
 677                   FOR_PROVIDES(p, pp, obs)
 678                     {
 679                       Solvable *ps = pool->solvables + p;
 680                       if (p == n)
 681                         continue;
 682                       if (isinstalled && dontfix && ps->repo == installed)
 683                         continue;       /* don't repair installed/installed problems */
 684                       if (!pool->obsoleteusesprovides /* obsoletes are matched names, not provides */
 685                           && !pool_match_nevr(pool, ps, obs))
 686                         continue;
 687                       if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
 688                         continue;
 689                       if (!isinstalled)
 690                         addrpmrule(solv, -n, -p, SOLVER_RULE_RPM_PACKAGE_OBSOLETES, obs);
 691                       else
 692                         addrpmrule(solv, -n, -p, SOLVER_RULE_RPM_INSTALLEDPKG_OBSOLETES, obs);
 693                     }
 694                 }
 695             }
 696           /* check implicit obsoletes
 697            * for installed packages we only need to check installed/installed problems (and
 698            * only when dontfix is not set), as the others are picked up when looking at the
 699            * uninstalled package.
 700            */
 701           if (!isinstalled || !dontfix)
 702             {
 703               FOR_PROVIDES(p, pp, s->name)
 704                 {
 705                   Solvable *ps = pool->solvables + p;
 706                   if (p == n)
 707                     continue;
 708                   if (isinstalled && ps->repo != installed)
 709                     continue;
 710                   /* we still obsolete packages with same nevra, like rpm does */
 711                   /* (actually, rpm mixes those packages. yuck...) */
 712                   if (noobs && (s->name != ps->name || s->evr != ps->evr || s->arch != ps->arch))
 713                     continue;
 714                   if (!pool->implicitobsoleteusesprovides && s->name != ps->name)
 715                     continue;
 716                   if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
 717                     continue;
 718                   if (s->name == ps->name)
 719                     addrpmrule(solv, -n, -p, SOLVER_RULE_RPM_SAME_NAME, 0);
 720                   else
 721                     addrpmrule(solv, -n, -p, SOLVER_RULE_RPM_IMPLICIT_OBSOLETES, s->name);
 722                 }
 723             }
 724         }
 725
 726       /*-----------------------------------------
 727        * add recommends to the work queue
 728        */
 729       if (s->recommends && m)
 730         {
 731           recp = s->repo->idarraydata + s->recommends;
 732           while ((rec = *recp++) != 0)
 733             {
 734               FOR_PROVIDES(p, pp, rec)
 735                 if (!MAPTST(m, p))
 736                   queue_push(&workq, p);
 737             }
 738         }
 739       if (s->suggests && m)
 740         {
 741           sugp = s->repo->idarraydata + s->suggests;
 742           while ((sug = *sugp++) != 0)
 743             {
 744               FOR_PROVIDES(p, pp, sug)
 745                 if (!MAPTST(m, p))
 746                   queue_push(&workq, p);
 747             }
 748         }
 749     }
 750   queue_free(&workq);
 751 }
 752
 753
 754 /*-------------------------------------------------------------------
 755  *
 756  * Add rules for packages possibly selected in by weak dependencies
 757  *
 758  * m: already added solvables
 759  */
 760
 761 void
 762 solver_addrpmrulesforweak(Solver *solv, Map *m)
 763 {
 764   Pool *pool = solv->pool;
 765   Solvable *s;
 766   Id sup, *supp;
 767   int i, n;
 768
 769   /* foreach solvable in pool */
 770   for (i = n = 1; n < pool->nsolvables; i++, n++)
 771     {
 772       if (i == pool->nsolvables)                /* wrap i */
 773         i = 1;
 774       if (MAPTST(m, i))                         /* already added that one */
 775         continue;
 776
 777       s = pool->solvables + i;
 778       if (!s->repo)
 779         continue;
 780       if (s->repo != pool->installed && !pool_installable(pool, s))
 781         continue;       /* only look at installable ones */
 782
 783       sup = 0;
 784       if (s->supplements)
 785         {
 786           /* find possible supplements */
 787           supp = s->repo->idarraydata + s->supplements;
 788           while ((sup = *supp++) != 0)
 789             if (dep_possible(solv, sup, m))
 790               break;
 791         }
 792
 793       /* if nothing found, check for enhances */
 794       if (!sup && s->enhances)
 795         {
 796           supp = s->repo->idarraydata + s->enhances;
 797           while ((sup = *supp++) != 0)
 798             if (dep_possible(solv, sup, m))
 799               break;
 800         }
 801       /* if nothing found, goto next solvables */
 802       if (!sup)
 803         continue;
 804       solver_addrpmrulesforsolvable(solv, s, m);
 805       n = 0;                    /* check all solvables again because we added solvables to m */
 806     }
 807 }
 808
 809
 810 /*-------------------------------------------------------------------
 811  *
 812  * add package rules for possible updates
 813  *
 814  * s: solvable
 815  * m: map of already visited solvables
 816  * allow_all: 0 = dont allow downgrades, 1 = allow all candidates
 817  */
 818
 819 void
 820 solver_addrpmrulesforupdaters(Solver *solv, Solvable *s, Map *m, int allow_all)
 821 {
 822   Pool *pool = solv->pool;
 823   int i;
 824     /* queue and buffer for it */
 825   Queue qs;
 826   Id qsbuf[64];
 827
 828   queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
 829     /* find update candidates for 's' */
 830   policy_findupdatepackages(solv, s, &qs, allow_all);
 831     /* add rule for 's' if not already done */
 832   if (!MAPTST(m, s - pool->solvables))
 833     solver_addrpmrulesforsolvable(solv, s, m);
 834     /* foreach update candidate, add rule if not already done */
 835   for (i = 0; i < qs.count; i++)
 836     if (!MAPTST(m, qs.elements[i]))
 837       solver_addrpmrulesforsolvable(solv, pool->solvables + qs.elements[i], m);
 838   queue_free(&qs);
 839 }
 840
 841
 842 /***********************************************************************
 843  ***
 844  ***  Update/Feature rule part
 845  ***
 846  ***  Those rules make sure an installed package isn't silently deleted
 847  ***
 848  ***/
 849
 850 static Id
 851 finddistupgradepackages(Solver *solv, Solvable *s, Queue *qs, int allow_all)
 852 {
 853   Pool *pool = solv->pool;
 854   int i;
 855
 856   policy_findupdatepackages(solv, s, qs, allow_all ? allow_all : 2);
 857   if (!qs->count)
 858     {
 859       if (allow_all)
 860         return 0;       /* orphaned, don't create feature rule */
 861       /* check if this is an orphaned package */
 862       policy_findupdatepackages(solv, s, qs, 1);
 863       if (!qs->count)
 864         return 0;       /* orphaned, don't create update rule */
 865       qs->count = 0;
 866       return -SYSTEMSOLVABLE;   /* supported but not installable */
 867     }
 868   if (allow_all)
 869     return s - pool->solvables;
 870   /* check if it is ok to keep the installed package */
 871   for (i = 0; i < qs->count; i++)
 872     {
 873       Solvable *ns = pool->solvables + qs->elements[i];
 874       if (s->evr == ns->evr && solvable_identical(s, ns))
 875         return s - pool->solvables;
 876     }
 877   /* nope, it must be some other package */
 878   return -SYSTEMSOLVABLE;
 879 }
 880
 881 /* add packages from the dup repositories to the update candidates
 882  * this isn't needed for the global dup mode as all packages are
 883  * from dup repos in that case */
 884 static void
 885 addduppackages(Solver *solv, Solvable *s, Queue *qs)
 886 {
 887   Queue dupqs;
 888   Id p, dupqsbuf[64];
 889   int i;
 890   int oldnoupdateprovide = solv->noupdateprovide;
 891
 892   queue_init_buffer(&dupqs, dupqsbuf, sizeof(dupqsbuf)/sizeof(*dupqsbuf));
 893   solv->noupdateprovide = 1;
 894   policy_findupdatepackages(solv, s, &dupqs, 2);
 895   solv->noupdateprovide = oldnoupdateprovide;
 896   for (i = 0; i < dupqs.count; i++)
 897     {
 898       p = dupqs.elements[i];
 899       if (MAPTST(&solv->dupmap, p))
 900         queue_pushunique(qs, p);
 901     }
 902   queue_free(&dupqs);
 903 }
 904
 905 /*-------------------------------------------------------------------
 906  *
 907  * add rule for update
 908  *   (A|A1|A2|A3...)  An = update candidates for A
 909  *
 910  * s = (installed) solvable
 911  */
 912
 913 void
 914 solver_addupdaterule(Solver *solv, Solvable *s, int allow_all)
 915 {
 916   /* installed packages get a special upgrade allowed rule */
 917   Pool *pool = solv->pool;
 918   Id p, d;
 919   Queue qs;
 920   Id qsbuf[64];
 921
 922   queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
 923   p = s - pool->solvables;
 924   /* find update candidates for 's' */
 925   if (solv->dupmap_all)
 926     p = finddistupgradepackages(solv, s, &qs, allow_all);
 927   else
 928     policy_findupdatepackages(solv, s, &qs, allow_all);
 929   if (!allow_all && !solv->dupmap_all && solv->dupinvolvedmap.size && MAPTST(&solv->dupinvolvedmap, p))
 930     addduppackages(solv, s, &qs);
 931
 932   if (!allow_all && qs.count && solv->noobsoletes.size)
 933     {
 934       int i, j;
 935
 936       d = pool_queuetowhatprovides(pool, &qs);
 937       /* filter out all noobsoletes packages as they don't update */
 938       for (i = j = 0; i < qs.count; i++)
 939         {
 940           if (MAPTST(&solv->noobsoletes, qs.elements[i]))
 941             {
 942               /* it's ok if they have same nevra */
 943               Solvable *ps = pool->solvables + qs.elements[i];
 944               if (ps->name != s->name || ps->evr != s->evr || ps->arch != s->arch)
 945                 continue;
 946             }
 947           qs.elements[j++] = qs.elements[i];
 948         }
 949       if (j < qs.count)
 950         {
 951           if (d && solv->installed && s->repo == solv->installed &&
 952               (solv->updatemap_all || (solv->updatemap.size && MAPTST(&solv->updatemap, s - pool->solvables - solv->installed->start))))
 953             {
 954               if (!solv->multiversionupdaters)
 955                 solv->multiversionupdaters = solv_calloc(solv->installed->end - solv->installed->start, sizeof(Id));
 956               solv->multiversionupdaters[s - pool->solvables - solv->installed->start] = d;
 957             }
 958           if (j == 0 && p == -SYSTEMSOLVABLE && solv->dupmap_all)
 959             {
 960               queue_push(&solv->orphaned, s - pool->solvables); /* treat as orphaned */
 961               j = qs.count;
 962             }
 963           qs.count = j;
 964         }
 965       else if (p != -SYSTEMSOLVABLE)
 966         {
 967           /* could fallthrough, but then we would do pool_queuetowhatprovides twice */
 968           queue_free(&qs);
 969           solver_addrule(solv, p, d);   /* allow update of s */
 970           return;
 971         }
 972     }
 973   if (qs.count && p == -SYSTEMSOLVABLE)
 974     p = queue_shift(&qs);
 975   d = qs.count ? pool_queuetowhatprovides(pool, &qs) : 0;
 976   queue_free(&qs);
 977   solver_addrule(solv, p, d);   /* allow update of s */
 978 }
 979
 980 static inline void
 981 disableupdaterule(Solver *solv, Id p)
 982 {
 983   Rule *r;
 984
 985   MAPSET(&solv->noupdate, p - solv->installed->start);
 986   r = solv->rules + solv->updaterules + (p - solv->installed->start);
 987   if (r->p && r->d >= 0)
 988     solver_disablerule(solv, r);
 989   r = solv->rules + solv->featurerules + (p - solv->installed->start);
 990   if (r->p && r->d >= 0)
 991     solver_disablerule(solv, r);
 992   if (solv->bestrules_pkg)
 993     {
 994       int i, ni;
 995       ni = solv->bestrules_end - solv->bestrules;
 996       for (i = 0; i < ni; i++)
 997         if (solv->bestrules_pkg[i] == p)
 998           solver_disablerule(solv, solv->rules + solv->bestrules + i);
 999     }
1000 }
1001
1002 static inline void
1003 reenableupdaterule(Solver *solv, Id p)
1004 {
1005   Pool *pool = solv->pool;
1006   Rule *r;
1007
1008   MAPCLR(&solv->noupdate, p - solv->installed->start);
1009   r = solv->rules + solv->updaterules + (p - solv->installed->start);
1010   if (r->p)
1011     {
1012       if (r->d < 0)
1013         {
1014           solver_enablerule(solv, r);
1015           IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS)
1016             {
1017               POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "@@@ re-enabling ");
1018               solver_printruleclass(solv, SOLV_DEBUG_SOLUTIONS, r);
1019             }
1020         }
1021     }
1022   else
1023     {
1024       r = solv->rules + solv->featurerules + (p - solv->installed->start);
1025       if (r->p && r->d < 0)
1026         {
1027           solver_enablerule(solv, r);
1028           IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS)
1029             {
1030               POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "@@@ re-enabling ");
1031               solver_printruleclass(solv, SOLV_DEBUG_SOLUTIONS, r);
1032             }
1033         }
1034     }
1035   if (solv->bestrules_pkg)
1036     {
1037       int i, ni;
1038       ni = solv->bestrules_end - solv->bestrules;
1039       for (i = 0; i < ni; i++)
1040         if (solv->bestrules_pkg[i] == p)
1041           solver_enablerule(solv, solv->rules + solv->bestrules + i);
1042     }
1043 }
1044
1045
1046 /***********************************************************************
1047  ***
1048  ***  Infarch rule part
1049  ***
1050  ***  Infarch rules make sure the solver uses the best architecture of
1051  ***  a package if multiple archetectures are available
1052  ***
1053  ***/
1054
1055 void
1056 solver_addinfarchrules(Solver *solv, Map *addedmap)
1057 {
1058   Pool *pool = solv->pool;
1059   int first, i, j;
1060   Id p, pp, a, aa, bestarch;
1061   Solvable *s, *ps, *bests;
1062   Queue badq, allowedarchs;
1063
1064   queue_init(&badq);
1065   queue_init(&allowedarchs);
1066   solv->infarchrules = solv->nrules;
1067   for (i = 1; i < pool->nsolvables; i++)
1068     {
1069       if (i == SYSTEMSOLVABLE || !MAPTST(addedmap, i))
1070         continue;
1071       s = pool->solvables + i;
1072       first = i;
1073       bestarch = 0;
1074       bests = 0;
1075       queue_empty(&allowedarchs);
1076       FOR_PROVIDES(p, pp, s->name)
1077         {
1078           ps = pool->solvables + p;
1079           if (ps->name != s->name || !MAPTST(addedmap, p))
1080             continue;
1081           if (p == i)
1082             first = 0;
1083           if (first)
1084             break;
1085           a = ps->arch;
1086           a = (a <= pool->lastarch) ? pool->id2arch[a] : 0;
1087           if (a != 1 && pool->installed && ps->repo == pool->installed)
1088             {
1089               if (!solv->dupmap_all && !(solv->dupinvolvedmap.size && MAPTST(&solv->dupinvolvedmap, p)))
1090                 queue_pushunique(&allowedarchs, ps->arch);      /* also ok to keep this architecture */
1091               continue;         /* ignore installed solvables when calculating the best arch */
1092             }
1093           if (a && a != 1 && (!bestarch || a < bestarch))
1094             {
1095               bestarch = a;
1096               bests = ps;
1097             }
1098         }
1099       if (first)
1100         continue;
1101       /* speed up common case where installed package already has best arch */
1102       if (allowedarchs.count == 1 && bests && allowedarchs.elements[0] == bests->arch)
1103         allowedarchs.count--;   /* installed arch is best */
1104       queue_empty(&badq);
1105       FOR_PROVIDES(p, pp, s->name)
1106         {
1107           ps = pool->solvables + p;
1108           if (ps->name != s->name || !MAPTST(addedmap, p))
1109             continue;
1110           a = ps->arch;
1111           a = (a <= pool->lastarch) ? pool->id2arch[a] : 0;
1112           if (a != 1 && bestarch && ((a ^ bestarch) & 0xffff0000) != 0)
1113             {
1114               if (pool->installed && ps->repo == pool->installed)
1115                 continue;       /* always ok to keep an installed package */
1116               for (j = 0; j < allowedarchs.count; j++)
1117                 {
1118                   aa = allowedarchs.elements[j];
1119                   if (ps->arch == aa)
1120                     break;
1121                   aa = (aa <= pool->lastarch) ? pool->id2arch[aa] : 0;
1122                   if (aa && ((a ^ aa) & 0xffff0000) == 0)
1123                     break;      /* compatible */
1124                 }
1125               if (j == allowedarchs.count)
1126                 queue_push(&badq, p);
1127             }
1128         }
1129       if (!badq.count)
1130         continue;
1131       /* block all solvables in the badq! */
1132       for (j = 0; j < badq.count; j++)
1133         {
1134           p = badq.elements[j];
1135           solver_addrule(solv, -p, 0);
1136         }
1137     }
1138   queue_free(&badq);
1139   queue_free(&allowedarchs);
1140   solv->infarchrules_end = solv->nrules;
1141 }
1142
1143 static inline void
1144 disableinfarchrule(Solver *solv, Id name)
1145 {
1146   Pool *pool = solv->pool;
1147   Rule *r;
1148   int i;
1149   for (i = solv->infarchrules, r = solv->rules + i; i < solv->infarchrules_end; i++, r++)
1150     {
1151       if (r->p < 0 && r->d >= 0 && pool->solvables[-r->p].name == name)
1152         solver_disablerule(solv, r);
1153     }
1154 }
1155
1156 static inline void
1157 reenableinfarchrule(Solver *solv, Id name)
1158 {
1159   Pool *pool = solv->pool;
1160   Rule *r;
1161   int i;
1162   for (i = solv->infarchrules, r = solv->rules + i; i < solv->infarchrules_end; i++, r++)
1163     {
1164       if (r->p < 0 && r->d < 0 && pool->solvables[-r->p].name == name)
1165         {
1166           solver_enablerule(solv, r);
1167           IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS)
1168             {
1169               POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "@@@ re-enabling ");
1170               solver_printruleclass(solv, SOLV_DEBUG_SOLUTIONS, r);
1171             }
1172         }
1173     }
1174 }
1175
1176
1177 /***********************************************************************
1178  ***
1179  ***  Dup rule part
1180  ***
1181  ***  Dup rules make sure a package is selected from the specified dup
1182  ***  repositories if an update candidate is included in one of them.
1183  ***
1184  ***/
1185
1186 static inline void
1187 add_cleandeps_package(Solver *solv, Id p)
1188 {
1189   if (!solv->cleandeps_updatepkgs)
1190     {
1191       solv->cleandeps_updatepkgs = solv_calloc(1, sizeof(Queue));
1192       queue_init(solv->cleandeps_updatepkgs);
1193     }
1194   queue_pushunique(solv->cleandeps_updatepkgs, p);
1195 }
1196
1197 static inline void
1198 solver_addtodupmaps(Solver *solv, Id p, Id how, int targeted)
1199 {
1200   Pool *pool = solv->pool;
1201   Solvable *ps, *s = pool->solvables + p;
1202   Repo *installed = solv->installed;
1203   Id pi, pip, obs, *obsp;
1204
1205   MAPSET(&solv->dupinvolvedmap, p);
1206   if (targeted)
1207     MAPSET(&solv->dupmap, p);
1208   FOR_PROVIDES(pi, pip, s->name)
1209     {
1210       ps = pool->solvables + pi;
1211       if (ps->name != s->name)
1212         continue;
1213       MAPSET(&solv->dupinvolvedmap, pi);
1214       if (targeted && ps->repo == installed && solv->obsoletes && solv->obsoletes[pi - installed->start])
1215         {
1216           Id *opp, pi2;
1217           for (opp = solv->obsoletes_data + solv->obsoletes[pi - installed->start]; (pi2 = *opp++) != 0;)
1218             if (pool->solvables[pi2].repo != installed)
1219               MAPSET(&solv->dupinvolvedmap, pi2);
1220         }
1221       if (ps->repo == installed && (how & SOLVER_FORCEBEST) != 0)
1222         {
1223           if (!solv->bestupdatemap.size)
1224             map_grow(&solv->bestupdatemap, installed->end - installed->start);
1225           MAPSET(&solv->bestupdatemap, pi - installed->start);
1226         }
1227       if (ps->repo == installed && (how & SOLVER_CLEANDEPS) != 0)
1228         add_cleandeps_package(solv, pi);
1229       if (!targeted && ps->repo != installed)
1230         MAPSET(&solv->dupmap, pi);
1231     }
1232   if (s->repo == installed && solv->obsoletes && solv->obsoletes[p - installed->start])
1233     {
1234       Id *opp;
1235       for (opp = solv->obsoletes_data + solv->obsoletes[p - installed->start]; (pi = *opp++) != 0;)
1236         {
1237           ps = pool->solvables + pi;
1238           if (ps->repo == installed)
1239             continue;
1240           MAPSET(&solv->dupinvolvedmap, pi);
1241           if (!targeted)
1242             MAPSET(&solv->dupmap, pi);
1243         }
1244     }
1245   if (targeted && s->repo != installed && s->obsoletes)
1246     {
1247       /* XXX: check obsoletes/provides combination */
1248       obsp = s->repo->idarraydata + s->obsoletes;
1249       while ((obs = *obsp++) != 0)
1250         {
1251           FOR_PROVIDES(pi, pip, obs)
1252             {
1253               Solvable *ps = pool->solvables + pi;
1254               if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
1255                 continue;
1256               if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
1257                 continue;
1258               MAPSET(&solv->dupinvolvedmap, pi);
1259               if (targeted && ps->repo == installed && solv->obsoletes && solv->obsoletes[pi - installed->start])
1260                 {
1261                   Id *opp, pi2;
1262                   for (opp = solv->obsoletes_data + solv->obsoletes[pi - installed->start]; (pi2 = *opp++) != 0;)
1263                     if (pool->solvables[pi2].repo != installed)
1264                       MAPSET(&solv->dupinvolvedmap, pi2);
1265                 }
1266               if (ps->repo == installed && (how & SOLVER_FORCEBEST) != 0)
1267                 {
1268                   if (!solv->bestupdatemap.size)
1269                     map_grow(&solv->bestupdatemap, installed->end - installed->start);
1270                   MAPSET(&solv->bestupdatemap, pi - installed->start);
1271                 }
1272               if (ps->repo == installed && (how & SOLVER_CLEANDEPS) != 0)
1273                 add_cleandeps_package(solv, pi);
1274             }
1275         }
1276     }
1277 }
1278
1279 void
1280 solver_createdupmaps(Solver *solv)
1281 {
1282   Queue *job = &solv->job;
1283   Pool *pool = solv->pool;
1284   Repo *installed = solv->installed;
1285   Id select, how, what, p, pp;
1286   Solvable *s;
1287   int i, targeted;
1288
1289   map_init(&solv->dupmap, pool->nsolvables);
1290   map_init(&solv->dupinvolvedmap, pool->nsolvables);
1291   for (i = 0; i < job->count; i += 2)
1292     {
1293       how = job->elements[i];
1294       select = job->elements[i] & SOLVER_SELECTMASK;
1295       what = job->elements[i + 1];
1296       switch (how & SOLVER_JOBMASK)
1297         {
1298         case SOLVER_DISTUPGRADE:
1299           if (select == SOLVER_SOLVABLE_REPO)
1300             {
1301               Repo *repo;
1302               if (what <= 0 || what > pool->nrepos)
1303                 break;
1304               repo = pool_id2repo(pool, what);
1305               if (!repo)
1306                 break;
1307               if (repo != installed && !(how & SOLVER_TARGETED) && solv->noautotarget)
1308                 break;
1309               targeted = repo != installed || (how & SOLVER_TARGETED) != 0;
1310               FOR_REPO_SOLVABLES(repo, p, s)
1311                 {
1312                   if (repo != installed && !pool_installable(pool, s))
1313                     continue;
1314                   solver_addtodupmaps(solv, p, how, targeted);
1315                 }
1316             }
1317           else
1318             {
1319               targeted = how & SOLVER_TARGETED ? 1 : 0;
1320               if (installed && !targeted && !solv->noautotarget)
1321                 {
1322                   FOR_JOB_SELECT(p, pp, select, what)
1323                     if (pool->solvables[p].repo == installed)
1324                       break;
1325                   targeted = p == 0;
1326                 }
1327               else if (!installed && !solv->noautotarget)
1328                 targeted = 1;
1329               FOR_JOB_SELECT(p, pp, select, what)
1330                 {
1331                   Solvable *s = pool->solvables + p;
1332                   if (!s->repo)
1333                     continue;
1334                   if (s->repo != installed && !targeted)
1335                     continue;
1336                   if (s->repo != installed && !pool_installable(pool, s))
1337                     continue;
1338                   solver_addtodupmaps(solv, p, how, targeted);
1339                 }
1340             }
1341           break;
1342         default:
1343           break;
1344         }
1345     }
1346   MAPCLR(&solv->dupinvolvedmap, SYSTEMSOLVABLE);
1347 }
1348
1349 void
1350 solver_freedupmaps(Solver *solv)
1351 {
1352   map_free(&solv->dupmap);
1353   /* we no longer free solv->dupinvolvedmap as we need it in
1354    * policy's priority pruning code. sigh. */
1355 }
1356
1357 void
1358 solver_addduprules(Solver *solv, Map *addedmap)
1359 {
1360   Pool *pool = solv->pool;
1361   Id p, pp;
1362   Solvable *s, *ps;
1363   int first, i;
1364
1365   solv->duprules = solv->nrules;
1366   for (i = 1; i < pool->nsolvables; i++)
1367     {
1368       if (i == SYSTEMSOLVABLE || !MAPTST(addedmap, i))
1369         continue;
1370       s = pool->solvables + i;
1371       first = i;
1372       FOR_PROVIDES(p, pp, s->name)
1373         {
1374           ps = pool->solvables + p;
1375           if (ps->name != s->name || !MAPTST(addedmap, p))
1376             continue;
1377           if (p == i)
1378             first = 0;
1379           if (first)
1380             break;
1381           if (!MAPTST(&solv->dupinvolvedmap, p))
1382             continue;
1383           if (solv->installed && ps->repo == solv->installed)
1384             {
1385               if (!solv->updatemap.size)
1386                 map_grow(&solv->updatemap, solv->installed->end - solv->installed->start);
1387               MAPSET(&solv->updatemap, p - solv->installed->start);
1388               if (!MAPTST(&solv->dupmap, p))
1389                 {
1390                   Id ip, ipp;
1391                   /* is installed identical to a good one? */
1392                   FOR_PROVIDES(ip, ipp, ps->name)
1393                     {
1394                       Solvable *is = pool->solvables + ip;
1395                       if (!MAPTST(&solv->dupmap, ip))
1396                         continue;
1397                       if (is->evr == ps->evr && solvable_identical(ps, is))
1398                         break;
1399                     }
1400                   if (!ip)
1401                     solver_addrule(solv, -p, 0);        /* no match, sorry */
1402                   else
1403                     MAPSET(&solv->dupmap, p);           /* for best rules processing */
1404                 }
1405             }
1406           else if (!MAPTST(&solv->dupmap, p))
1407             solver_addrule(solv, -p, 0);
1408         }
1409     }
1410   solv->duprules_end = solv->nrules;
1411 }
1412
1413
1414 static inline void
1415 disableduprule(Solver *solv, Id name)
1416 {
1417   Pool *pool = solv->pool;
1418   Rule *r;
1419   int i;
1420   for (i = solv->duprules, r = solv->rules + i; i < solv->duprules_end; i++, r++)
1421     {
1422       if (r->p < 0 && r->d >= 0 && pool->solvables[-r->p].name == name)
1423         solver_disablerule(solv, r);
1424     }
1425 }
1426
1427 static inline void
1428 reenableduprule(Solver *solv, Id name)
1429 {
1430   Pool *pool = solv->pool;
1431   Rule *r;
1432   int i;
1433   for (i = solv->duprules, r = solv->rules + i; i < solv->duprules_end; i++, r++)
1434     {
1435       if (r->p < 0 && r->d < 0 && pool->solvables[-r->p].name == name)
1436         {
1437           solver_enablerule(solv, r);
1438           IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS)
1439             {
1440               POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "@@@ re-enabling ");
1441               solver_printruleclass(solv, SOLV_DEBUG_SOLUTIONS, r);
1442             }
1443         }
1444     }
1445 }
1446
1447
1448 /***********************************************************************
1449  ***
1450  ***  Policy rule disabling/reenabling
1451  ***
1452  ***  Disable all policy rules that conflict with our jobs. If a job
1453  ***  gets disabled later on, reenable the involved policy rules again.
1454  ***
1455  ***/
1456
1457 #define DISABLE_UPDATE  1
1458 #define DISABLE_INFARCH 2
1459 #define DISABLE_DUP     3
1460
1461 /*
1462  * add all installed packages that package p obsoletes to Queue q.
1463  * Package p is not installed. Also, we know that if
1464  * solv->keepexplicitobsoletes is not set, p is not in the noobs map.
1465  * Entries may get added multiple times.
1466  */
1467 static void
1468 add_obsoletes(Solver *solv, Id p, Queue *q)
1469 {
1470   Pool *pool = solv->pool;
1471   Repo *installed = solv->installed;
1472   Id p2, pp2;
1473   Solvable *s = pool->solvables + p;
1474   Id obs, *obsp;
1475   Id lastp2 = 0;
1476
1477   if (!solv->keepexplicitobsoletes || !(solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p)))
1478     {
1479       FOR_PROVIDES(p2, pp2, s->name)
1480         {
1481           Solvable *ps = pool->solvables + p2;
1482           if (ps->repo != installed)
1483             continue;
1484           if (!pool->implicitobsoleteusesprovides && ps->name != s->name)
1485             continue;
1486           if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
1487             continue;
1488           queue_push(q, p2);
1489           lastp2 = p2;
1490         }
1491     }
1492   if (!s->obsoletes)
1493     return;
1494   obsp = s->repo->idarraydata + s->obsoletes;
1495   while ((obs = *obsp++) != 0)
1496     FOR_PROVIDES(p2, pp2, obs)
1497       {
1498         Solvable *ps = pool->solvables + p2;
1499         if (ps->repo != installed)
1500           continue;
1501         if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
1502           continue;
1503         if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
1504           continue;
1505         if (p2 == lastp2)
1506           continue;
1507         queue_push(q, p2);
1508         lastp2 = p2;
1509       }
1510 }
1511
1512 /*
1513  * Call add_obsoletes and intersect the result with the
1514  * elements in Queue q starting at qstart.
1515  * Assumes that it's the first call if qstart == q->count.
1516  * May use auxillary map m for the intersection process, all
1517  * elements of q starting at qstart must have their bit cleared.
1518  * (This is also true after the function returns.)
1519  */
1520 static void
1521 intersect_obsoletes(Solver *solv, Id p, Queue *q, int qstart, Map *m)
1522 {
1523   int i, j;
1524   int qcount = q->count;
1525
1526   add_obsoletes(solv, p, q);
1527   if (qcount == qstart)
1528     return;     /* first call */
1529   if (qcount == q->count)
1530     j = qstart;
1531   else if (qcount == qstart + 1)
1532     {
1533       /* easy if there's just one element */
1534       j = qstart;
1535       for (i = qcount; i < q->count; i++)
1536         if (q->elements[i] == q->elements[qstart])
1537           {
1538             j++;        /* keep the element */
1539             break;
1540           }
1541     }
1542   else if (!m->size && q->count - qstart <= 8)
1543     {
1544       /* faster than a map most of the time */
1545       int k;
1546       for (i = j = qstart; i < qcount; i++)
1547         {
1548           Id ip = q->elements[i];
1549           for (k = qcount; k < q->count; k++)
1550             if (q->elements[k] == ip)
1551               {
1552                 q->elements[j++] = ip;
1553                 break;
1554               }
1555         }
1556     }
1557   else
1558     {
1559       /* for the really pathologic cases we use the map */
1560       Repo *installed = solv->installed;
1561       if (!m->size)
1562         map_init(m, installed->end - installed->start);
1563       for (i = qcount; i < q->count; i++)
1564         MAPSET(m, q->elements[i] - installed->start);
1565       for (i = j = qstart; i < qcount; i++)
1566         if (MAPTST(m, q->elements[i] - installed->start))
1567           {
1568             MAPCLR(m, q->elements[i] - installed->start);
1569             q->elements[j++] = q->elements[i];
1570           }
1571     }
1572   queue_truncate(q, j);
1573 }
1574
1575 static void
1576 jobtodisablelist(Solver *solv, Id how, Id what, Queue *q)
1577 {
1578   Pool *pool = solv->pool;
1579   Id select, p, pp;
1580   Repo *installed;
1581   Solvable *s;
1582   int i, j, set, qstart;
1583   Map omap;
1584
1585   installed = solv->installed;
1586   select = how & SOLVER_SELECTMASK;
1587   switch (how & SOLVER_JOBMASK)
1588     {
1589     case SOLVER_INSTALL:
1590       set = how & SOLVER_SETMASK;
1591       if (!(set & SOLVER_NOAUTOSET))
1592         {
1593           /* automatically add set bits by analysing the job */
1594           if (select == SOLVER_SOLVABLE_NAME)
1595             set |= SOLVER_SETNAME;
1596           if (select == SOLVER_SOLVABLE)
1597             set |= SOLVER_SETNAME | SOLVER_SETARCH | SOLVER_SETVENDOR | SOLVER_SETREPO | SOLVER_SETEVR;
1598           else if ((select == SOLVER_SOLVABLE_NAME || select == SOLVER_SOLVABLE_PROVIDES) && ISRELDEP(what))
1599             {
1600               Reldep *rd = GETRELDEP(pool, what);
1601               if (rd->flags == REL_EQ && select == SOLVER_SOLVABLE_NAME)
1602                 {
1603                   if (pool->disttype != DISTTYPE_DEB)
1604                     {
1605                       const char *evr = pool_id2str(pool, rd->evr);
1606                       if (strchr(evr, '-'))
1607                         set |= SOLVER_SETEVR;
1608                       else
1609                         set |= SOLVER_SETEV;
1610                     }
1611                   else
1612                     set |= SOLVER_SETEVR;
1613                 }
1614               if (rd->flags <= 7 && ISRELDEP(rd->name))
1615                 rd = GETRELDEP(pool, rd->name);
1616               if (rd->flags == REL_ARCH)
1617                 set |= SOLVER_SETARCH;
1618             }
1619         }
1620       else
1621         set &= ~SOLVER_NOAUTOSET;
1622       if (!set)
1623         return;
1624       if ((set & SOLVER_SETARCH) != 0 && solv->infarchrules != solv->infarchrules_end)
1625         {
1626           if (select == SOLVER_SOLVABLE)
1627             queue_push2(q, DISABLE_INFARCH, pool->solvables[what].name);
1628           else
1629             {
1630               int qcnt = q->count;
1631               /* does not work for SOLVER_SOLVABLE_ALL and SOLVER_SOLVABLE_REPO, but
1632                  they are not useful for SOLVER_INSTALL jobs anyway */
1633               FOR_JOB_SELECT(p, pp, select, what)
1634                 {
1635                   s = pool->solvables + p;
1636                   /* unify names */
1637                   for (i = qcnt; i < q->count; i += 2)
1638                     if (q->elements[i + 1] == s->name)
1639                       break;
1640                   if (i < q->count)
1641                     continue;
1642                   queue_push2(q, DISABLE_INFARCH, s->name);
1643                 }
1644             }
1645         }
1646       if ((set & SOLVER_SETREPO) != 0 && solv->duprules != solv->duprules_end)
1647         {
1648           if (select == SOLVER_SOLVABLE)
1649             queue_push2(q, DISABLE_DUP, pool->solvables[what].name);
1650           else
1651             {
1652               int qcnt = q->count;
1653               FOR_JOB_SELECT(p, pp, select, what)
1654                 {
1655                   s = pool->solvables + p;
1656                   /* unify names */
1657                   for (i = qcnt; i < q->count; i += 2)
1658                     if (q->elements[i + 1] == s->name)
1659                       break;
1660                   if (i < q->count)
1661                     continue;
1662                   queue_push2(q, DISABLE_DUP, s->name);
1663                 }
1664             }
1665         }
1666       if (!installed || installed->end == installed->start)
1667         return;
1668       /* now the hard part: disable some update rules */
1669
1670       /* first check if we have noobs or installed packages in the job */
1671       i = j = 0;
1672       FOR_JOB_SELECT(p, pp, select, what)
1673         {
1674           if (pool->solvables[p].repo == installed)
1675             j = p;
1676           else if (solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p) && !solv->keepexplicitobsoletes)
1677             return;
1678           i++;
1679         }
1680       if (j)    /* have installed packages */
1681         {
1682           /* this is for dupmap_all jobs, it can go away if we create
1683            * duprules for them */
1684           if (i == 1 && (set & SOLVER_SETREPO) != 0)
1685             queue_push2(q, DISABLE_UPDATE, j);
1686           return;
1687         }
1688
1689       omap.size = 0;
1690       qstart = q->count;
1691       FOR_JOB_SELECT(p, pp, select, what)
1692         {
1693           intersect_obsoletes(solv, p, q, qstart, &omap);
1694           if (q->count == qstart)
1695             break;
1696         }
1697       if (omap.size)
1698         map_free(&omap);
1699
1700       if (qstart == q->count)
1701         return;         /* nothing to prune */
1702
1703       /* convert result to (DISABLE_UPDATE, p) pairs */
1704       i = q->count;
1705       for (j = qstart; j < i; j++)
1706         queue_push(q, q->elements[j]);
1707       for (j = qstart; j < q->count; j += 2)
1708         {
1709           q->elements[j] = DISABLE_UPDATE;
1710           q->elements[j + 1] = q->elements[i++];
1711         }
1712
1713       /* now that we know which installed packages are obsoleted check each of them */
1714       if ((set & (SOLVER_SETEVR | SOLVER_SETARCH | SOLVER_SETVENDOR)) == (SOLVER_SETEVR | SOLVER_SETARCH | SOLVER_SETVENDOR))
1715         return;         /* all is set, nothing to do */
1716
1717       for (i = j = qstart; i < q->count; i += 2)
1718         {
1719           Solvable *is = pool->solvables + q->elements[i + 1];
1720           FOR_JOB_SELECT(p, pp, select, what)
1721             {
1722               int illegal = 0;
1723               s = pool->solvables + p;
1724               if ((set & SOLVER_SETEVR) != 0)
1725                 illegal |= POLICY_ILLEGAL_DOWNGRADE;    /* ignore */
1726               if ((set & SOLVER_SETNAME) != 0)
1727                 illegal |= POLICY_ILLEGAL_NAMECHANGE;   /* ignore */
1728               if ((set & SOLVER_SETARCH) != 0)
1729                 illegal |= POLICY_ILLEGAL_ARCHCHANGE;   /* ignore */
1730               if ((set & SOLVER_SETVENDOR) != 0)
1731                 illegal |= POLICY_ILLEGAL_VENDORCHANGE; /* ignore */
1732               illegal = policy_is_illegal(solv, is, s, illegal);
1733               if (illegal && illegal == POLICY_ILLEGAL_DOWNGRADE && (set & SOLVER_SETEV) != 0)
1734                 {
1735                   /* it's ok if the EV is different */
1736                   if (pool_evrcmp(pool, is->evr, s->evr, EVRCMP_COMPARE_EVONLY) != 0)
1737                     illegal = 0;
1738                 }
1739               if (illegal)
1740                 break;
1741             }
1742           if (!p)
1743             {
1744               /* no package conflicts with the update rule */
1745               /* thus keep the DISABLE_UPDATE */
1746               q->elements[j + 1] = q->elements[i + 1];
1747               j += 2;
1748             }
1749         }
1750       queue_truncate(q, j);
1751       return;
1752
1753     case SOLVER_ERASE:
1754       if (!installed)
1755         break;
1756       if (select == SOLVER_SOLVABLE_ALL || (select == SOLVER_SOLVABLE_REPO && what == installed->repoid))
1757         FOR_REPO_SOLVABLES(installed, p, s)
1758           queue_push2(q, DISABLE_UPDATE, p);
1759       FOR_JOB_SELECT(p, pp, select, what)
1760         if (pool->solvables[p].repo == installed)
1761           queue_push2(q, DISABLE_UPDATE, p);
1762       return;
1763     default:
1764       return;
1765     }
1766 }
1767
1768 /* disable all policy rules that are in conflict with our job list */
1769 void
1770 solver_disablepolicyrules(Solver *solv)
1771 {
1772   Queue *job = &solv->job;
1773   int i, j;
1774   Queue allq;
1775   Rule *r;
1776   Id lastjob = -1;
1777   Id allqbuf[128];
1778
1779   queue_init_buffer(&allq, allqbuf, sizeof(allqbuf)/sizeof(*allqbuf));
1780
1781   for (i = solv->jobrules; i < solv->jobrules_end; i++)
1782     {
1783       r = solv->rules + i;
1784       if (r->d < 0)     /* disabled? */
1785         continue;
1786       j = solv->ruletojob.elements[i - solv->jobrules];
1787       if (j == lastjob)
1788         continue;
1789       lastjob = j;
1790       jobtodisablelist(solv, job->elements[j], job->elements[j + 1], &allq);
1791     }
1792   if (solv->cleandepsmap.size)
1793     {
1794       solver_createcleandepsmap(solv, &solv->cleandepsmap, 0);
1795       for (i = solv->installed->start; i < solv->installed->end; i++)
1796         if (MAPTST(&solv->cleandepsmap, i - solv->installed->start))
1797           queue_push2(&allq, DISABLE_UPDATE, i);
1798     }
1799   MAPZERO(&solv->noupdate);
1800   for (i = 0; i < allq.count; i += 2)
1801     {
1802       Id type = allq.elements[i], arg = allq.elements[i + 1];
1803       switch(type)
1804         {
1805         case DISABLE_UPDATE:
1806           disableupdaterule(solv, arg);
1807           break;
1808         case DISABLE_INFARCH:
1809           disableinfarchrule(solv, arg);
1810           break;
1811         case DISABLE_DUP:
1812           disableduprule(solv, arg);
1813           break;
1814         default:
1815           break;
1816         }
1817     }
1818   queue_free(&allq);
1819 }
1820
1821 /* we just disabled job #jobidx, now reenable all policy rules that were
1822  * disabled because of this job */
1823 void
1824 solver_reenablepolicyrules(Solver *solv, int jobidx)
1825 {
1826   Queue *job = &solv->job;
1827   int i, j;
1828   Queue q, allq;
1829   Rule *r;
1830   Id lastjob = -1;
1831   Id qbuf[32], allqbuf[128];
1832
1833   queue_init_buffer(&q, qbuf, sizeof(qbuf)/sizeof(*qbuf));
1834   queue_init_buffer(&allq, allqbuf, sizeof(allqbuf)/sizeof(*allqbuf));
1835   jobtodisablelist(solv, job->elements[jobidx - 1], job->elements[jobidx], &q);
1836   if (!q.count)
1837     return;
1838   for (i = solv->jobrules; i < solv->jobrules_end; i++)
1839     {
1840       r = solv->rules + i;
1841       if (r->d < 0)     /* disabled? */
1842         continue;
1843       j = solv->ruletojob.elements[i - solv->jobrules];
1844       if (j == lastjob)
1845         continue;
1846       lastjob = j;
1847       jobtodisablelist(solv, job->elements[j], job->elements[j + 1], &allq);
1848     }
1849   if (solv->cleandepsmap.size)
1850     {
1851       solver_createcleandepsmap(solv, &solv->cleandepsmap, 0);
1852       for (i = solv->installed->start; i < solv->installed->end; i++)
1853         if (MAPTST(&solv->cleandepsmap, i - solv->installed->start))
1854           queue_push2(&allq, DISABLE_UPDATE, i);
1855     }
1856   for (j = 0; j < q.count; j += 2)
1857     {
1858       Id type = q.elements[j], arg = q.elements[j + 1];
1859       for (i = 0; i < allq.count; i += 2)
1860         if (allq.elements[i] == type && allq.elements[i + 1] == arg)
1861           break;
1862       if (i < allq.count)
1863         continue;       /* still disabled */
1864       switch(type)
1865         {
1866         case DISABLE_UPDATE:
1867           reenableupdaterule(solv, arg);
1868           break;
1869         case DISABLE_INFARCH:
1870           reenableinfarchrule(solv, arg);
1871           break;
1872         case DISABLE_DUP:
1873           reenableduprule(solv, arg);
1874           break;
1875         }
1876     }
1877   queue_free(&allq);
1878   queue_free(&q);
1879 }
1880
1881 /* we just removed a package from the cleandeps map, now reenable all policy rules that were
1882  * disabled because of this */
1883 void
1884 solver_reenablepolicyrules_cleandeps(Solver *solv, Id pkg)
1885 {
1886   Queue *job = &solv->job;
1887   int i, j;
1888   Queue allq;
1889   Rule *r;
1890   Id lastjob = -1;
1891   Id allqbuf[128];
1892
1893   queue_init_buffer(&allq, allqbuf, sizeof(allqbuf)/sizeof(*allqbuf));
1894   for (i = solv->jobrules; i < solv->jobrules_end; i++)
1895     {
1896       r = solv->rules + i;
1897       if (r->d < 0)     /* disabled? */
1898         continue;
1899       j = solv->ruletojob.elements[i - solv->jobrules];
1900       if (j == lastjob)
1901         continue;
1902       lastjob = j;
1903       jobtodisablelist(solv, job->elements[j], job->elements[j + 1], &allq);
1904     }
1905   for (i = 0; i < allq.count; i += 2)
1906     if (allq.elements[i] == DISABLE_UPDATE && allq.elements[i + 1] == pkg)
1907       break;
1908   if (i == allq.count)
1909     reenableupdaterule(solv, pkg);
1910   queue_free(&allq);
1911 }
1912
1913
1914 /***********************************************************************
1915  ***
1916  ***  Rule info part, tell the user what the rule is about.
1917  ***
1918  ***/
1919
1920 static void
1921 addrpmruleinfo(Solver *solv, Id p, Id d, int type, Id dep)
1922 {
1923   Pool *pool = solv->pool;
1924   Rule *r;
1925   Id w2, op, od, ow2;
1926
1927   /* check if this creates the rule we're searching for */
1928   r = solv->rules + solv->ruleinfoq->elements[0];
1929   op = r->p;
1930   od = r->d < 0 ? -r->d - 1 : r->d;
1931   ow2 = 0;
1932
1933   /* normalize */
1934   w2 = d > 0 ? 0 : d;
1935   if (p < 0 && d > 0 && (!pool->whatprovidesdata[d] || !pool->whatprovidesdata[d + 1]))
1936     {
1937       w2 = pool->whatprovidesdata[d];
1938       d = 0;
1939
1940     }
1941   if (p > 0 && d < 0)           /* this hack is used for buddy deps */
1942     {
1943       w2 = p;
1944       p = d;
1945     }
1946
1947   if (d > 0)
1948     {
1949       if (p != op && !od)
1950         return;
1951       if (d != od)
1952         {
1953           Id *dp = pool->whatprovidesdata + d;
1954           Id *odp = pool->whatprovidesdata + od;
1955           while (*dp)
1956             if (*dp++ != *odp++)
1957               return;
1958           if (*odp)
1959             return;
1960         }
1961       w2 = 0;
1962       /* handle multiversion conflict rules */
1963       if (p < 0 && pool->whatprovidesdata[d] < 0)
1964         {
1965           w2 = pool->whatprovidesdata[d];
1966           /* XXX: free memory */
1967         }
1968     }
1969   else
1970     {
1971       if (od)
1972         return;
1973       ow2 = r->w2;
1974       if (p > w2)
1975         {
1976           if (w2 != op || p != ow2)
1977             return;
1978         }
1979       else
1980         {
1981           if (p != op || w2 != ow2)
1982             return;
1983         }
1984     }
1985   /* yep, rule matches. record info */
1986   queue_push(solv->ruleinfoq, type);
1987   if (type == SOLVER_RULE_RPM_SAME_NAME)
1988     {
1989       /* we normalize same name order */
1990       queue_push(solv->ruleinfoq, op < 0 ? -op : 0);
1991       queue_push(solv->ruleinfoq, ow2 < 0 ? -ow2 : 0);
1992     }
1993   else
1994     {
1995       queue_push(solv->ruleinfoq, p < 0 ? -p : 0);
1996       queue_push(solv->ruleinfoq, w2 < 0 ? -w2 : 0);
1997     }
1998   queue_push(solv->ruleinfoq, dep);
1999 }
2000
2001 static int
2002 solver_allruleinfos_cmp(const void *ap, const void *bp, void *dp)
2003 {
2004   const Id *a = ap, *b = bp;
2005   int r;
2006
2007   r = a[0] - b[0];
2008   if (r)
2009     return r;
2010   r = a[1] - b[1];
2011   if (r)
2012     return r;
2013   r = a[2] - b[2];
2014   if (r)
2015     return r;
2016   r = a[3] - b[3];
2017   if (r)
2018     return r;
2019   return 0;
2020 }
2021
2022 int
2023 solver_allruleinfos(Solver *solv, Id rid, Queue *rq)
2024 {
2025   Pool *pool = solv->pool;
2026   Rule *r = solv->rules + rid;
2027   int i, j;
2028
2029   queue_empty(rq);
2030   if (rid <= 0 || rid >= solv->rpmrules_end)
2031     {
2032       Id type, from, to, dep;
2033       type = solver_ruleinfo(solv, rid, &from, &to, &dep);
2034       queue_push(rq, type);
2035       queue_push(rq, from);
2036       queue_push(rq, to);
2037       queue_push(rq, dep);
2038       return 1;
2039     }
2040   if (r->p >= 0)
2041     return 0;
2042   queue_push(rq, rid);
2043   solv->ruleinfoq = rq;
2044   solver_addrpmrulesforsolvable(solv, pool->solvables - r->p, 0);
2045   /* also try reverse direction for conflicts */
2046   if ((r->d == 0 || r->d == -1) && r->w2 < 0)
2047     solver_addrpmrulesforsolvable(solv, pool->solvables - r->w2, 0);
2048   solv->ruleinfoq = 0;
2049   queue_shift(rq);
2050   /* now sort & unify em */
2051   if (!rq->count)
2052     return 0;
2053   solv_sort(rq->elements, rq->count / 4, 4 * sizeof(Id), solver_allruleinfos_cmp, 0);
2054   /* throw out identical entries */
2055   for (i = j = 0; i < rq->count; i += 4)
2056     {
2057       if (j)
2058         {
2059           if (rq->elements[i] == rq->elements[j - 4] &&
2060               rq->elements[i + 1] == rq->elements[j - 3] &&
2061               rq->elements[i + 2] == rq->elements[j - 2] &&
2062               rq->elements[i + 3] == rq->elements[j - 1])
2063             continue;
2064         }
2065       rq->elements[j++] = rq->elements[i];
2066       rq->elements[j++] = rq->elements[i + 1];
2067       rq->elements[j++] = rq->elements[i + 2];
2068       rq->elements[j++] = rq->elements[i + 3];
2069     }
2070   rq->count = j;
2071   return j / 4;
2072 }
2073
2074 SolverRuleinfo
2075 solver_ruleinfo(Solver *solv, Id rid, Id *fromp, Id *top, Id *depp)
2076 {
2077   Pool *pool = solv->pool;
2078   Rule *r = solv->rules + rid;
2079   SolverRuleinfo type = SOLVER_RULE_UNKNOWN;
2080
2081   if (fromp)
2082     *fromp = 0;
2083   if (top)
2084     *top = 0;
2085   if (depp)
2086     *depp = 0;
2087   if (rid > 0 && rid < solv->rpmrules_end)
2088     {
2089       Queue rq;
2090       int i;
2091
2092       if (r->p >= 0)
2093         return SOLVER_RULE_RPM;
2094       if (fromp)
2095         *fromp = -r->p;
2096       queue_init(&rq);
2097       queue_push(&rq, rid);
2098       solv->ruleinfoq = &rq;
2099       solver_addrpmrulesforsolvable(solv, pool->solvables - r->p, 0);
2100       /* also try reverse direction for conflicts */
2101       if ((r->d == 0 || r->d == -1) && r->w2 < 0)
2102         solver_addrpmrulesforsolvable(solv, pool->solvables - r->w2, 0);
2103       solv->ruleinfoq = 0;
2104       type = SOLVER_RULE_RPM;
2105       for (i = 1; i < rq.count; i += 4)
2106         {
2107           Id qt, qo, qp, qd;
2108           qt = rq.elements[i];
2109           qp = rq.elements[i + 1];
2110           qo = rq.elements[i + 2];
2111           qd = rq.elements[i + 3];
2112           if (type == SOLVER_RULE_RPM || type > qt)
2113             {
2114               type = qt;
2115               if (fromp)
2116                 *fromp = qp;
2117               if (top)
2118                 *top = qo;
2119               if (depp)
2120                 *depp = qd;
2121             }
2122         }
2123       queue_free(&rq);
2124       return type;
2125     }
2126   if (rid >= solv->jobrules && rid < solv->jobrules_end)
2127     {
2128       Id jidx = solv->ruletojob.elements[rid - solv->jobrules];
2129       if (fromp)
2130         *fromp = jidx;
2131       if (top)
2132         *top = solv->job.elements[jidx];
2133       if (depp)
2134         *depp = solv->job.elements[jidx + 1];
2135       if ((r->d == 0 || r->d == -1) && r->w2 == 0 && r->p == -SYSTEMSOLVABLE)
2136         {
2137           if ((solv->job.elements[jidx] & (SOLVER_JOBMASK|SOLVER_SELECTMASK)) == (SOLVER_INSTALL|SOLVER_SOLVABLE_NAME))
2138             return SOLVER_RULE_JOB_NOTHING_PROVIDES_DEP;
2139           if ((solv->job.elements[jidx] & (SOLVER_JOBMASK|SOLVER_SELECTMASK)) == (SOLVER_INSTALL|SOLVER_SOLVABLE_PROVIDES))
2140             return SOLVER_RULE_JOB_NOTHING_PROVIDES_DEP;
2141           if ((solv->job.elements[jidx] & (SOLVER_JOBMASK|SOLVER_SELECTMASK)) == (SOLVER_ERASE|SOLVER_SOLVABLE_NAME))
2142             return SOLVER_RULE_JOB_PROVIDED_BY_SYSTEM;
2143           if ((solv->job.elements[jidx] & (SOLVER_JOBMASK|SOLVER_SELECTMASK)) == (SOLVER_ERASE|SOLVER_SOLVABLE_PROVIDES))
2144             return SOLVER_RULE_JOB_PROVIDED_BY_SYSTEM;
2145         }
2146       return SOLVER_RULE_JOB;
2147     }
2148   if (rid >= solv->updaterules && rid < solv->updaterules_end)
2149     {
2150       if (fromp)
2151         *fromp = solv->installed->start + (rid - solv->updaterules);
2152       return SOLVER_RULE_UPDATE;
2153     }
2154   if (rid >= solv->featurerules && rid < solv->featurerules_end)
2155     {
2156       if (fromp)
2157         *fromp = solv->installed->start + (rid - solv->featurerules);
2158       return SOLVER_RULE_FEATURE;
2159     }
2160   if (rid >= solv->duprules && rid < solv->duprules_end)
2161     {
2162       if (fromp)
2163         *fromp = -r->p;
2164       if (depp)
2165         *depp = pool->solvables[-r->p].name;
2166       return SOLVER_RULE_DISTUPGRADE;
2167     }
2168   if (rid >= solv->infarchrules && rid < solv->infarchrules_end)
2169     {
2170       if (fromp)
2171         *fromp = -r->p;
2172       if (depp)
2173         *depp = pool->solvables[-r->p].name;
2174       return SOLVER_RULE_INFARCH;
2175     }
2176   if (rid >= solv->bestrules && rid < solv->bestrules_end)
2177     {
2178       return SOLVER_RULE_BEST;
2179     }
2180   if (rid >= solv->choicerules && rid < solv->choicerules_end)
2181     {
2182       return SOLVER_RULE_CHOICE;
2183     }
2184   if (rid >= solv->learntrules)
2185     {
2186       return SOLVER_RULE_LEARNT;
2187     }
2188   return SOLVER_RULE_UNKNOWN;
2189 }
2190
2191 SolverRuleinfo
2192 solver_ruleclass(Solver *solv, Id rid)
2193 {
2194   if (rid <= 0)
2195     return SOLVER_RULE_UNKNOWN;
2196   if (rid > 0 && rid < solv->rpmrules_end)
2197     return SOLVER_RULE_RPM;
2198   if (rid >= solv->jobrules && rid < solv->jobrules_end)
2199     return SOLVER_RULE_JOB;
2200   if (rid >= solv->updaterules && rid < solv->updaterules_end)
2201     return SOLVER_RULE_UPDATE;
2202   if (rid >= solv->featurerules && rid < solv->featurerules_end)
2203     return SOLVER_RULE_FEATURE;
2204   if (rid >= solv->duprules && rid < solv->duprules_end)
2205     return SOLVER_RULE_DISTUPGRADE;
2206   if (rid >= solv->infarchrules && rid < solv->infarchrules_end)
2207     return SOLVER_RULE_INFARCH;
2208   if (rid >= solv->bestrules && rid < solv->bestrules_end)
2209     return SOLVER_RULE_BEST;
2210   if (rid >= solv->choicerules && rid < solv->choicerules_end)
2211     return SOLVER_RULE_CHOICE;
2212   if (rid >= solv->learntrules)
2213     return SOLVER_RULE_LEARNT;
2214   return SOLVER_RULE_UNKNOWN;
2215 }
2216
2217 void
2218 solver_ruleliterals(Solver *solv, Id rid, Queue *q)
2219 {
2220   Pool *pool = solv->pool;
2221   Id p, pp;
2222   Rule *r;
2223
2224   queue_empty(q);
2225   r = solv->rules + rid;
2226   FOR_RULELITERALS(p, pp, r)
2227     if (p != -SYSTEMSOLVABLE)
2228       queue_push(q, p);
2229   if (!q->count)
2230     queue_push(q, -SYSTEMSOLVABLE);     /* hmm, better to return an empty result? */
2231 }
2232
2233 int
2234 solver_rule2jobidx(Solver *solv, Id rid)
2235 {
2236   if (rid < solv->jobrules || rid >= solv->jobrules_end)
2237     return 0;
2238   return solv->ruletojob.elements[rid - solv->jobrules] + 1;
2239 }
2240
2241 Id
2242 solver_rule2job(Solver *solv, Id rid, Id *whatp)
2243 {
2244   int idx;
2245   if (rid < solv->jobrules || rid >= solv->jobrules_end)
2246     {
2247       if (whatp)
2248         *whatp = 0;
2249       return 0;
2250     }
2251   idx = solv->ruletojob.elements[rid - solv->jobrules];
2252   if (whatp)
2253     *whatp = solv->job.elements[idx + 1];
2254   return solv->job.elements[idx];
2255 }
2256
2257 void
2258 solver_addchoicerules(Solver *solv)
2259 {
2260   Pool *pool = solv->pool;
2261   Map m, mneg;
2262   Rule *r;
2263   Queue q, qi;
2264   int i, j, rid, havechoice;
2265   Id p, d, pp;
2266   Id p2, pp2;
2267   Solvable *s, *s2;
2268   Id lastaddedp, lastaddedd;
2269   int lastaddedcnt;
2270
2271   solv->choicerules = solv->nrules;
2272   if (!pool->installed)
2273     {
2274       solv->choicerules_end = solv->nrules;
2275       return;
2276     }
2277   solv->choicerules_ref = solv_calloc(solv->rpmrules_end, sizeof(Id));
2278   queue_init(&q);
2279   queue_init(&qi);
2280   map_init(&m, pool->nsolvables);
2281   map_init(&mneg, pool->nsolvables);
2282   /* set up negative assertion map from infarch and dup rules */
2283   for (rid = solv->infarchrules, r = solv->rules + rid; rid < solv->infarchrules_end; rid++, r++)
2284     if (r->p < 0 && !r->w2 && (r->d == 0 || r->d == -1))
2285       MAPSET(&mneg, -r->p);
2286   for (rid = solv->duprules, r = solv->rules + rid; rid < solv->duprules_end; rid++, r++)
2287     if (r->p < 0 && !r->w2 && (r->d == 0 || r->d == -1))
2288       MAPSET(&mneg, -r->p);
2289   lastaddedp = 0;
2290   lastaddedd = 0;
2291   lastaddedcnt = 0;
2292   for (rid = 1; rid < solv->rpmrules_end ; rid++)
2293     {
2294       r = solv->rules + rid;
2295       if (r->p >= 0 || ((r->d == 0 || r->d == -1) && r->w2 < 0))
2296         continue;       /* only look at requires rules */
2297       /* solver_printrule(solv, SOLV_DEBUG_RESULT, r); */
2298       queue_empty(&q);
2299       queue_empty(&qi);
2300       havechoice = 0;
2301       FOR_RULELITERALS(p, pp, r)
2302         {
2303           if (p < 0)
2304             continue;
2305           s = pool->solvables + p;
2306           if (!s->repo)
2307             continue;
2308           if (s->repo == pool->installed)
2309             {
2310               queue_push(&q, p);
2311               continue;
2312             }
2313           /* check if this package is "blocked" by a installed package */
2314           s2 = 0;
2315           FOR_PROVIDES(p2, pp2, s->name)
2316             {
2317               s2 = pool->solvables + p2;
2318               if (s2->repo != pool->installed)
2319                 continue;
2320               if (!pool->implicitobsoleteusesprovides && s->name != s2->name)
2321                 continue;
2322               if (pool->obsoleteusescolors && !pool_colormatch(pool, s, s2))
2323                 continue;
2324               break;
2325             }
2326           if (p2)
2327             {
2328               /* found installed package p2 that we can update to p */
2329               if (MAPTST(&mneg, p))
2330                 continue;
2331               if (policy_is_illegal(solv, s2, s, 0))
2332                 continue;
2333               queue_push(&qi, p2);
2334               queue_push(&q, p);
2335               continue;
2336             }
2337           if (s->obsoletes)
2338             {
2339               Id obs, *obsp = s->repo->idarraydata + s->obsoletes;
2340               s2 = 0;
2341               while ((obs = *obsp++) != 0)
2342                 {
2343                   FOR_PROVIDES(p2, pp2, obs)
2344                     {
2345                       s2 = pool->solvables + p2;
2346                       if (s2->repo != pool->installed)
2347                         continue;
2348                       if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p2, obs))
2349                         continue;
2350                       if (pool->obsoleteusescolors && !pool_colormatch(pool, s, s2))
2351                         continue;
2352                       break;
2353                     }
2354                   if (p2)
2355                     break;
2356                 }
2357               if (obs)
2358                 {
2359                   /* found installed package p2 that we can update to p */
2360                   if (MAPTST(&mneg, p))
2361                     continue;
2362                   if (policy_is_illegal(solv, s2, s, 0))
2363                     continue;
2364                   queue_push(&qi, p2);
2365                   queue_push(&q, p);
2366                   continue;
2367                 }
2368             }
2369           /* package p is independent of the installed ones */
2370           havechoice = 1;
2371         }
2372       if (!havechoice || !q.count)
2373         continue;       /* no choice */
2374
2375       /* now check the update rules of the installed package.
2376        * if all packages of the update rules are contained in
2377        * the dependency rules, there's no need to set up the choice rule */
2378       map_empty(&m);
2379       FOR_RULELITERALS(p, pp, r)
2380         if (p > 0)
2381           MAPSET(&m, p);
2382       for (i = 0; i < qi.count; i++)
2383         {
2384           Rule *ur;
2385           if (!qi.elements[i])
2386             continue;
2387           ur = solv->rules + solv->updaterules + (qi.elements[i] - pool->installed->start);
2388           if (!ur->p)
2389             ur = solv->rules + solv->featurerules + (qi.elements[i] - pool->installed->start);
2390           if (!ur->p)
2391             continue;
2392           FOR_RULELITERALS(p, pp, ur)
2393             if (!MAPTST(&m, p))
2394               break;
2395           if (p)
2396             break;
2397           for (j = i + 1; j < qi.count; j++)
2398             if (qi.elements[i] == qi.elements[j])
2399               qi.elements[j] = 0;
2400         }
2401       if (i == qi.count)
2402         {
2403 #if 0
2404           printf("skipping choice ");
2405           solver_printrule(solv, SOLV_DEBUG_RESULT, solv->rules + rid);
2406 #endif
2407           continue;
2408         }
2409
2410       /* don't add identical rules */
2411       if (lastaddedp == r->p && lastaddedcnt == q.count)
2412         {
2413           for (i = 0; i < q.count; i++)
2414             if (q.elements[i] != pool->whatprovidesdata[lastaddedd + i])
2415               break;
2416           if (i == q.count)
2417             continue;   /* already added that one */
2418         }
2419       d = q.count ? pool_queuetowhatprovides(pool, &q) : 0;
2420
2421       lastaddedp = r->p;
2422       lastaddedd = d;
2423       lastaddedcnt = q.count;
2424
2425       solver_addrule(solv, r->p, d);
2426       queue_push(&solv->weakruleq, solv->nrules - 1);
2427       solv->choicerules_ref[solv->nrules - 1 - solv->choicerules] = rid;
2428 #if 0
2429       printf("OLD ");
2430       solver_printrule(solv, SOLV_DEBUG_RESULT, solv->rules + rid);
2431       printf("WEAK CHOICE ");
2432       solver_printrule(solv, SOLV_DEBUG_RESULT, solv->rules + solv->nrules - 1);
2433 #endif
2434     }
2435   queue_free(&q);
2436   queue_free(&qi);
2437   map_free(&m);
2438   map_free(&mneg);
2439   solv->choicerules_end = solv->nrules;
2440 }
2441
2442 /* called when a choice rule is disabled by analyze_unsolvable. We also
2443  * have to disable all other choice rules so that the best packages get
2444  * picked */
2445 void
2446 solver_disablechoicerules(Solver *solv, Rule *r)
2447 {
2448   Id rid, p, pp;
2449   Pool *pool = solv->pool;
2450   Map m;
2451   Rule *or;
2452
2453   or = solv->rules + solv->choicerules_ref[(r - solv->rules) - solv->choicerules];
2454   map_init(&m, pool->nsolvables);
2455   FOR_RULELITERALS(p, pp, or)
2456     if (p > 0)
2457       MAPSET(&m, p);
2458   FOR_RULELITERALS(p, pp, r)
2459     if (p > 0)
2460       MAPCLR(&m, p);
2461   for (rid = solv->choicerules; rid < solv->choicerules_end; rid++)
2462     {
2463       r = solv->rules + rid;
2464       if (r->d < 0)
2465         continue;
2466       or = solv->rules + solv->choicerules_ref[(r - solv->rules) - solv->choicerules];
2467       FOR_RULELITERALS(p, pp, or)
2468         if (p > 0 && MAPTST(&m, p))
2469           break;
2470       if (p)
2471         solver_disablerule(solv, r);
2472     }
2473 }
2474
2475 static void
2476 prune_to_update_targets(Solver *solv, Id *cp, Queue *q)
2477 {
2478   int i, j;
2479   Id p, *cp2;
2480   for (i = j = 0; i < q->count; i++)
2481     {
2482       p = q->elements[i];
2483       for (cp2 = cp; *cp2; cp2++)
2484         if (*cp2 == p)
2485           {
2486             q->elements[j++] = p;
2487             break;
2488           }
2489     }
2490   queue_truncate(q, j);
2491 }
2492
2493 static void
2494 prune_to_dup_packages(Solver *solv, Id p, Queue *q)
2495 {
2496   int i, j;
2497   for (i = j = 0; i < q->count; i++)
2498     {
2499       Id p = q->elements[i];
2500       if (MAPTST(&solv->dupmap, p))
2501         q->elements[j++] = p;
2502     }
2503   queue_truncate(q, j);
2504 }
2505
2506 void
2507 solver_addbestrules(Solver *solv, int havebestinstalljobs)
2508 {
2509   Pool *pool = solv->pool;
2510   Id p;
2511   Solvable *s;
2512   Repo *installed = solv->installed;
2513   Queue q, q2;
2514   Rule *r;
2515   Queue r2pkg;
2516   int i, oldcnt;
2517
2518   solv->bestrules = solv->nrules;
2519   if (!installed)
2520     {
2521       solv->bestrules_end = solv->nrules;
2522       return;
2523     }
2524   queue_init(&q);
2525   queue_init(&q2);
2526   queue_init(&r2pkg);
2527
2528   if (havebestinstalljobs)
2529     {
2530       for (i = 0; i < solv->job.count; i += 2)
2531         {
2532           if ((solv->job.elements[i] & (SOLVER_JOBMASK | SOLVER_FORCEBEST)) == (SOLVER_INSTALL | SOLVER_FORCEBEST))
2533             {
2534               int j;
2535               Id p2, pp2;
2536               for (j = 0; j < solv->ruletojob.count; j++)
2537                 if (solv->ruletojob.elements[j] == i)
2538                   break;
2539               if (j == solv->ruletojob.count)
2540                 continue;
2541               r = solv->rules + solv->jobrules + j;
2542               queue_empty(&q);
2543               FOR_RULELITERALS(p2, pp2, r)
2544                 if (p2 > 0)
2545                   queue_push(&q, p2);
2546               if (!q.count)
2547                 continue;       /* orphaned */
2548               /* select best packages, just look at prio and version */
2549               oldcnt = q.count;
2550               policy_filter_unwanted(solv, &q, POLICY_MODE_RECOMMEND);
2551               if (q.count == oldcnt)
2552                 continue;       /* nothing filtered */
2553               p2 = queue_shift(&q);
2554               solver_addrule(solv, p2, q.count ? pool_queuetowhatprovides(pool, &q) : 0);
2555               queue_push(&r2pkg, -(solv->jobrules + j));
2556             }
2557         }
2558     }
2559
2560   if (solv->bestupdatemap_all || solv->bestupdatemap.size)
2561     {
2562       FOR_REPO_SOLVABLES(installed, p, s)
2563         {
2564           Id d, p2, pp2;
2565           if (!solv->updatemap_all && (!solv->updatemap.size || !MAPTST(&solv->updatemap, p - installed->start)))
2566             continue;
2567           if (!solv->bestupdatemap_all && (!solv->bestupdatemap.size || !MAPTST(&solv->bestupdatemap, p - installed->start)))
2568             continue;
2569           queue_empty(&q);
2570           if (solv->bestobeypolicy)
2571             r = solv->rules + solv->updaterules + (p - installed->start);
2572           else
2573             {
2574               r = solv->rules + solv->featurerules + (p - installed->start);
2575               if (!r->p)        /* identical to update rule? */
2576                 r = solv->rules + solv->updaterules + (p - installed->start);
2577             }
2578           if (solv->multiversionupdaters && (d = solv->multiversionupdaters[p - installed->start]) != 0 && r == solv->rules + solv->updaterules + (p - installed->start))
2579             {
2580               /* need to check multiversionupdaters */
2581               if (r->p == p)    /* be careful with the dup case */
2582                 queue_push(&q, p);
2583               while ((p2 = pool->whatprovidesdata[d++]) != 0)
2584                 queue_push(&q, p2);
2585             }
2586           else
2587             {
2588               FOR_RULELITERALS(p2, pp2, r)
2589                 if (p2 > 0)
2590                   queue_push(&q, p2);
2591             }
2592           if (solv->update_targets && solv->update_targets->elements[p - installed->start])
2593             prune_to_update_targets(solv, solv->update_targets->elements + solv->update_targets->elements[p - installed->start], &q);
2594           if (solv->dupinvolvedmap.size && MAPTST(&solv->dupinvolvedmap, p))
2595             prune_to_dup_packages(solv, p, &q);
2596           /* select best packages, just look at prio and version */
2597           policy_filter_unwanted(solv, &q, POLICY_MODE_RECOMMEND);
2598           if (!q.count)
2599             continue;   /* orphaned */
2600           if (solv->bestobeypolicy)
2601             {
2602               /* also filter the best of the feature rule packages and add them */
2603               r = solv->rules + solv->featurerules + (p - installed->start);
2604               if (r->p)
2605                 {
2606                   int j;
2607                   queue_empty(&q2);
2608                   FOR_RULELITERALS(p2, pp2, r)
2609                     if (p2 > 0)
2610                       queue_push(&q2, p2);
2611                   if (solv->update_targets && solv->update_targets->elements[p - installed->start])
2612                     prune_to_update_targets(solv, solv->update_targets->elements + solv->update_targets->elements[p - installed->start], &q2);
2613                   if (solv->dupinvolvedmap.size && MAPTST(&solv->dupinvolvedmap, p))
2614                     prune_to_dup_packages(solv, p, &q);
2615                   policy_filter_unwanted(solv, &q2, POLICY_MODE_RECOMMEND);
2616                   for (j = 0; j < q2.count; j++)
2617                     queue_pushunique(&q, q2.elements[j]);
2618                 }
2619             }
2620           p2 = queue_shift(&q);
2621           solver_addrule(solv, p2, q.count ? pool_queuetowhatprovides(pool, &q) : 0);
2622           queue_push(&r2pkg, p);
2623         }
2624     }
2625   if (r2pkg.count)
2626     {
2627       solv->bestrules_pkg = solv_calloc(r2pkg.count, sizeof(Id));
2628       memcpy(solv->bestrules_pkg, r2pkg.elements, r2pkg.count * sizeof(Id));
2629     }
2630   solv->bestrules_end = solv->nrules;
2631   queue_free(&q);
2632   queue_free(&q2);
2633   queue_free(&r2pkg);
2634 }
2635
2636 #undef CLEANDEPSDEBUG
2637
2638 /*
2639  * This functions collects all packages that are looked at
2640  * when a dependency is checked. We need it to "pin" installed
2641  * packages when removing a supplemented package in createcleandepsmap.
2642  * Here's an not uncommon example:
2643  *   A contains "Supplements: packageand(B, C)"
2644  *   B contains "Requires: A"
2645  * Now if we remove C, the supplements is no longer true,
2646  * thus we also remove A. Without the dep_pkgcheck function, we
2647  * would now also remove B, but this is wrong, as adding back
2648  * C doesn't make the supplements true again. Thus we "pin" B
2649  * when we remove A.
2650  * There's probably a better way to do this, but I haven't come
2651  * up with it yet ;)
2652  */
2653 static inline void
2654 dep_pkgcheck(Solver *solv, Id dep, Map *m, Queue *q)
2655 {
2656   Pool *pool = solv->pool;
2657   Id p, pp;
2658
2659   if (ISRELDEP(dep))
2660     {
2661       Reldep *rd = GETRELDEP(pool, dep);
2662       if (rd->flags >= 8)
2663         {
2664           if (rd->flags == REL_AND)
2665             {
2666               dep_pkgcheck(solv, rd->name, m, q);
2667               dep_pkgcheck(solv, rd->evr, m, q);
2668               return;
2669             }
2670           if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
2671             return;
2672           if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
2673             return;
2674         }
2675     }
2676   FOR_PROVIDES(p, pp, dep)
2677     if (!m || MAPTST(m, p))
2678       queue_push(q, p);
2679 }
2680
2681 static int
2682 check_xsupp(Solver *solv, Queue *depq, Id dep)
2683 {
2684   Pool *pool = solv->pool;
2685   Id p, pp;
2686
2687   if (ISRELDEP(dep))
2688     {
2689       Reldep *rd = GETRELDEP(pool, dep);
2690       if (rd->flags >= 8)
2691         {
2692           if (rd->flags == REL_AND)
2693             {
2694               if (!check_xsupp(solv, depq, rd->name))
2695                 return 0;
2696               return check_xsupp(solv, depq, rd->evr);
2697             }
2698           if (rd->flags == REL_OR)
2699             {
2700               if (check_xsupp(solv, depq, rd->name))
2701                 return 1;
2702               return check_xsupp(solv, depq, rd->evr);
2703             }
2704           if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
2705             return solver_splitprovides(solv, rd->evr);
2706           if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
2707             return solver_dep_installed(solv, rd->evr);
2708         }
2709       if (depq && rd->flags == REL_NAMESPACE)
2710         {
2711           int i;
2712           for (i = 0; i < depq->count; i++)
2713             if (depq->elements[i] == dep || depq->elements[i] == rd->name)
2714              return 1;
2715         }
2716     }
2717   FOR_PROVIDES(p, pp, dep)
2718     if (p == SYSTEMSOLVABLE || pool->solvables[p].repo == solv->installed)
2719       return 1;
2720   return 0;
2721 }
2722
2723 static inline int
2724 queue_contains(Queue *q, Id id)
2725 {
2726   int i;
2727   for (i = 0; i < q->count; i++)
2728     if (q->elements[i] == id)
2729       return 1;
2730   return 0;
2731 }
2732
2733
2734 /*
2735  * Find all installed packages that are no longer
2736  * needed regarding the current solver job.
2737  *
2738  * The algorithm is:
2739  * - remove pass: remove all packages that could have
2740  *   been dragged in by the obsoleted packages.
2741  *   i.e. if package A is obsolete and contains "Requires: B",
2742  *   also remove B, as installing A will have pulled in B.
2743  *   after this pass, we have a set of still installed packages
2744  *   with broken dependencies.
2745  * - add back pass:
2746  *   now add back all packages that the still installed packages
2747  *   require.
2748  *
2749  * The cleandeps packages are the packages removed in the first
2750  * pass and not added back in the second pass.
2751  *
2752  * If we search for unneeded packages (unneeded is true), we
2753  * simply remove all packages except the userinstalled ones in
2754  * the first pass.
2755  */
2756 static void
2757 solver_createcleandepsmap(Solver *solv, Map *cleandepsmap, int unneeded)
2758 {
2759   Pool *pool = solv->pool;
2760   Repo *installed = solv->installed;
2761   Queue *job = &solv->job;
2762   Map userinstalled;
2763   Map im;
2764   Map installedm;
2765   Rule *r;
2766   Id rid, how, what, select;
2767   Id p, pp, ip, jp;
2768   Id req, *reqp, sup, *supp;
2769   Solvable *s;
2770   Queue iq, iqcopy, xsuppq;
2771   int i;
2772
2773   map_empty(cleandepsmap);
2774   if (!installed || installed->end == installed->start)
2775     return;
2776   map_init(&userinstalled, installed->end - installed->start);
2777   map_init(&im, pool->nsolvables);
2778   map_init(&installedm, pool->nsolvables);
2779   queue_init(&iq);
2780   queue_init(&xsuppq);
2781
2782   for (i = 0; i < job->count; i += 2)
2783     {
2784       how = job->elements[i];
2785       if ((how & SOLVER_JOBMASK) == SOLVER_USERINSTALLED)
2786         {
2787           what = job->elements[i + 1];
2788           select = how & SOLVER_SELECTMASK;
2789           if (select == SOLVER_SOLVABLE_ALL || (select == SOLVER_SOLVABLE_REPO && what == installed->repoid))
2790             FOR_REPO_SOLVABLES(installed, p, s)
2791               MAPSET(&userinstalled, p - installed->start);
2792           FOR_JOB_SELECT(p, pp, select, what)
2793             if (pool->solvables[p].repo == installed)
2794               MAPSET(&userinstalled, p - installed->start);
2795         }
2796       if ((how & (SOLVER_JOBMASK | SOLVER_SELECTMASK)) == (SOLVER_ERASE | SOLVER_SOLVABLE_PROVIDES))
2797         {
2798           what = job->elements[i + 1];
2799           if (ISRELDEP(what))
2800             {
2801               Reldep *rd = GETRELDEP(pool, what);
2802               if (rd->flags != REL_NAMESPACE)
2803                 continue;
2804               if (rd->evr == 0)
2805                 {
2806                   queue_pushunique(&iq, rd->name);
2807                   continue;
2808                 }
2809               FOR_PROVIDES(p, pp, what)
2810                 if (p)
2811                   break;
2812               if (p)
2813                 continue;
2814               queue_pushunique(&iq, what);
2815             }
2816         }
2817     }
2818
2819   /* have special namespace cleandeps erases */
2820   if (iq.count)
2821     {
2822       for (ip = solv->installed->start; ip < solv->installed->end; ip++)
2823         {
2824           s = pool->solvables + ip;
2825           if (s->repo != installed)
2826             continue;
2827           if (!s->supplements)
2828             continue;
2829           supp = s->repo->idarraydata + s->supplements;
2830           while ((sup = *supp++) != 0)
2831             if (check_xsupp(solv, &iq, sup) && !check_xsupp(solv, 0, sup))
2832               {
2833 #ifdef CLEANDEPSDEBUG
2834                 printf("xsupp %s from %s\n", pool_dep2str(pool, sup), pool_solvid2str(pool, ip));
2835 #endif
2836                 queue_pushunique(&xsuppq, sup);
2837               }
2838         }
2839       queue_empty(&iq);
2840     }
2841
2842   /* also add visible patterns to userinstalled for openSUSE */
2843   if (1)
2844     {
2845       Dataiterator di;
2846       dataiterator_init(&di, pool, 0, 0, SOLVABLE_ISVISIBLE, 0, 0);
2847       while (dataiterator_step(&di))
2848         {
2849           Id *dp;
2850           if (di.solvid <= 0)
2851             continue;
2852           s = pool->solvables + di.solvid;
2853           if (!s->repo || !s->requires)
2854             continue;
2855           if (s->repo != installed && !pool_installable(pool, s))
2856             continue;
2857           if (strncmp(pool_id2str(pool, s->name), "pattern:", 8) != 0)
2858             continue;
2859           dp = s->repo->idarraydata + s->requires;
2860           for (dp = s->repo->idarraydata + s->requires; *dp; dp++)
2861             FOR_PROVIDES(p, pp, *dp)
2862               if (pool->solvables[p].repo == installed)
2863                 {
2864                   if (strncmp(pool_id2str(pool, pool->solvables[p].name), "pattern", 7) != 0)
2865                     continue;
2866                   MAPSET(&userinstalled, p - installed->start);
2867                 }
2868         }
2869       dataiterator_free(&di);
2870     }
2871   if (1)
2872     {
2873       /* all products and their buddies are userinstalled */
2874       for (p = installed->start; p < installed->end; p++)
2875         {
2876           Solvable *s = pool->solvables + p;
2877           if (s->repo != installed)
2878             continue;
2879           if (!strncmp("product:", pool_id2str(pool, s->name), 8))
2880             {
2881               MAPSET(&userinstalled, p - installed->start);
2882               if (pool->nscallback)
2883                 {
2884                   Id buddy = pool->nscallback(pool, pool->nscallbackdata, NAMESPACE_PRODUCTBUDDY, p);
2885                   if (buddy >= installed->start && buddy < installed->end && pool->solvables[buddy].repo == installed)
2886                     MAPSET(&userinstalled, buddy - installed->start);
2887                 }
2888             }
2889         }
2890     }
2891
2892   /* add all positive elements (e.g. locks) to "userinstalled" */
2893   for (rid = solv->jobrules; rid < solv->jobrules_end; rid++)
2894     {
2895       r = solv->rules + rid;
2896       if (r->d < 0)
2897         continue;
2898       i = solv->ruletojob.elements[rid - solv->jobrules];
2899       if ((job->elements[i] & SOLVER_CLEANDEPS) == SOLVER_CLEANDEPS)
2900         continue;
2901       FOR_RULELITERALS(p, jp, r)
2902         if (p > 0 && pool->solvables[p].repo == installed)
2903           MAPSET(&userinstalled, p - installed->start);
2904     }
2905
2906   /* add all cleandeps candidates to iq */
2907   for (rid = solv->jobrules; rid < solv->jobrules_end; rid++)
2908     {
2909       r = solv->rules + rid;
2910       if (r->d < 0)                             /* disabled? */
2911         continue;
2912       if (r->d == 0 && r->p < 0 && r->w2 == 0)  /* negative assertion (erase job)? */
2913         {
2914           p = -r->p;
2915           if (pool->solvables[p].repo != installed)
2916             continue;
2917           MAPCLR(&userinstalled, p - installed->start);
2918           if (unneeded)
2919             continue;
2920           i = solv->ruletojob.elements[rid - solv->jobrules];
2921           how = job->elements[i];
2922           if ((how & (SOLVER_JOBMASK|SOLVER_CLEANDEPS)) == (SOLVER_ERASE|SOLVER_CLEANDEPS))
2923             queue_push(&iq, p);
2924         }
2925       else if (r->p > 0)                        /* install job */
2926         {
2927           if (unneeded)
2928             continue;
2929           i = solv->ruletojob.elements[rid - solv->jobrules];
2930           if ((job->elements[i] & SOLVER_CLEANDEPS) == SOLVER_CLEANDEPS)
2931             {
2932               /* check if the literals all obsolete some installed package */
2933               Map om;
2934               int iqstart;
2935
2936               /* just one installed literal */
2937               if (r->d == 0 && r->w2 == 0 && pool->solvables[r->p].repo == installed)
2938                 continue;
2939               /* noobs is bad */
2940               if (solv->noobsoletes.size && !solv->keepexplicitobsoletes)
2941                 {
2942                   FOR_RULELITERALS(p, jp, r)
2943                     if (MAPTST(&solv->noobsoletes, p))
2944                       break;
2945                   if (p)
2946                     continue;
2947                 }
2948
2949               om.size = 0;
2950               iqstart = iq.count;
2951               FOR_RULELITERALS(p, jp, r)
2952                 {
2953                   if (p < 0)
2954                     {
2955                       queue_truncate(&iq, iqstart);     /* abort */
2956                       break;
2957                     }
2958                   if (pool->solvables[p].repo == installed)
2959                     {
2960                       if (iq.count == iqstart)
2961                         queue_push(&iq, p);
2962                       else
2963                         {
2964                           for (i = iqstart; i < iq.count; i++)
2965                             if (iq.elements[i] == p)
2966                               break;
2967                           queue_truncate(&iq, iqstart);
2968                           if (i < iq.count)
2969                             queue_push(&iq, p);
2970                         }
2971                     }
2972                   else
2973                     intersect_obsoletes(solv, p, &iq, iqstart, &om);
2974                   if (iq.count == iqstart)
2975                     break;
2976                 }
2977               if (om.size)
2978                 map_free(&om);
2979             }
2980         }
2981     }
2982   queue_init_clone(&iqcopy, &iq);
2983
2984   if (!unneeded)
2985     {
2986       if (solv->cleandeps_updatepkgs)
2987         for (i = 0; i < solv->cleandeps_updatepkgs->count; i++)
2988           queue_push(&iq, solv->cleandeps_updatepkgs->elements[i]);
2989     }
2990
2991   if (unneeded)
2992     queue_empty(&iq);   /* just in case... */
2993
2994   /* clear userinstalled bit for the packages we really want to delete/update */
2995   for (i = 0; i < iq.count; i++)
2996     {
2997       p = iq.elements[i];
2998       if (pool->solvables[p].repo != installed)
2999         continue;
3000       MAPCLR(&userinstalled, p - installed->start);
3001     }
3002
3003   for (p = installed->start; p < installed->end; p++)
3004     {
3005       if (pool->solvables[p].repo != installed)
3006         continue;
3007       MAPSET(&installedm, p);
3008       if (unneeded && !MAPTST(&userinstalled, p - installed->start))
3009         continue;
3010       MAPSET(&im, p);
3011     }
3012   MAPSET(&installedm, SYSTEMSOLVABLE);
3013   MAPSET(&im, SYSTEMSOLVABLE);
3014
3015 #ifdef CLEANDEPSDEBUG
3016   printf("REMOVE PASS\n");
3017 #endif
3018
3019   for (;;)
3020     {
3021       if (!iq.count)
3022         {
3023           if (unneeded)
3024             break;
3025           /* supplements pass */
3026           for (ip = installed->start; ip < installed->end; ip++)
3027             {
3028               if (!MAPTST(&installedm, ip))
3029                 continue;
3030               s = pool->solvables + ip;
3031               if (!s->supplements)
3032                 continue;
3033               if (!MAPTST(&im, ip))
3034                 continue;
3035               if (MAPTST(&userinstalled, ip - installed->start))
3036                 continue;
3037               supp = s->repo->idarraydata + s->supplements;
3038               while ((sup = *supp++) != 0)
3039                 if (dep_possible(solv, sup, &im))
3040                   break;
3041               if (!sup)
3042                 {
3043                   supp = s->repo->idarraydata + s->supplements;
3044                   while ((sup = *supp++) != 0)
3045                     if (dep_possible(solv, sup, &installedm) || (xsuppq.count && queue_contains(&xsuppq, sup)))
3046                       {
3047                         /* no longer supplemented, also erase */
3048                         int iqcount = iq.count;
3049                         /* pin packages, see comment above dep_pkgcheck */
3050                         dep_pkgcheck(solv, sup, &im, &iq);
3051                         for (i = iqcount; i < iq.count; i++)
3052                           {
3053                             Id pqp = iq.elements[i];
3054                             if (pool->solvables[pqp].repo == installed)
3055                               MAPSET(&userinstalled, pqp - installed->start);
3056                           }
3057                         queue_truncate(&iq, iqcount);
3058 #ifdef CLEANDEPSDEBUG
3059                         printf("%s supplemented [%s]\n", pool_solvid2str(pool, ip), pool_dep2str(pool, sup));
3060 #endif
3061                         queue_push(&iq, ip);
3062                       }
3063                 }
3064             }
3065           if (!iq.count)
3066             break;      /* no supplementing package found, we're done */
3067         }
3068       ip = queue_shift(&iq);
3069       s = pool->solvables + ip;
3070       if (!MAPTST(&im, ip))
3071         continue;
3072       if (!MAPTST(&installedm, ip))
3073         continue;
3074       if (s->repo == installed && MAPTST(&userinstalled, ip - installed->start))
3075         continue;
3076       MAPCLR(&im, ip);
3077 #ifdef CLEANDEPSDEBUG
3078       printf("removing %s\n", pool_solvable2str(pool, s));
3079 #endif
3080       if (s->requires)
3081         {
3082           reqp = s->repo->idarraydata + s->requires;
3083           while ((req = *reqp++) != 0)
3084             {
3085               if (req == SOLVABLE_PREREQMARKER)
3086                 continue;
3087 #if 0
3088               /* count number of installed packages that match */
3089               count = 0;
3090               FOR_PROVIDES(p, pp, req)
3091                 if (MAPTST(&installedm, p))
3092                   count++;
3093               if (count > 1)
3094                 continue;
3095 #endif
3096               FOR_PROVIDES(p, pp, req)
3097                 {
3098                   if (p != SYSTEMSOLVABLE && MAPTST(&im, p))
3099                     {
3100 #ifdef CLEANDEPSDEBUG
3101                       printf("%s requires %s\n", pool_solvid2str(pool, ip), pool_solvid2str(pool, p));
3102 #endif
3103                       queue_push(&iq, p);
3104                     }
3105                 }
3106             }
3107         }
3108       if (s->recommends)
3109         {
3110           reqp = s->repo->idarraydata + s->recommends;
3111           while ((req = *reqp++) != 0)
3112             {
3113 #if 0
3114               count = 0;
3115               FOR_PROVIDES(p, pp, req)
3116                 if (MAPTST(&installedm, p))
3117                   count++;
3118               if (count > 1)
3119                 continue;
3120 #endif
3121               FOR_PROVIDES(p, pp, req)
3122                 {
3123                   if (p != SYSTEMSOLVABLE && MAPTST(&im, p))
3124                     {
3125 #ifdef CLEANDEPSDEBUG
3126                       printf("%s recommends %s\n", pool_solvid2str(pool, ip), pool_solvid2str(pool, p));
3127 #endif
3128                       queue_push(&iq, p);
3129                     }
3130                 }
3131             }
3132         }
3133     }
3134
3135   /* turn userinstalled into remove set for pruning */
3136   map_empty(&userinstalled);
3137   for (rid = solv->jobrules; rid < solv->jobrules_end; rid++)
3138     {
3139       r = solv->rules + rid;
3140       if (r->p >= 0 || r->d != 0 || r->w2 != 0)
3141         continue;       /* disabled or not erase */
3142       p = -r->p;
3143       MAPCLR(&im, p);
3144       if (pool->solvables[p].repo == installed)
3145         MAPSET(&userinstalled, p - installed->start);
3146     }
3147   MAPSET(&im, SYSTEMSOLVABLE);  /* in case we cleared it above */
3148   for (p = installed->start; p < installed->end; p++)
3149     if (MAPTST(&im, p))
3150       queue_push(&iq, p);
3151   for (rid = solv->jobrules; rid < solv->jobrules_end; rid++)
3152     {
3153       r = solv->rules + rid;
3154       if (r->d < 0)
3155         continue;
3156       FOR_RULELITERALS(p, jp, r)
3157         if (p > 0)
3158           queue_push(&iq, p);
3159     }
3160   /* also put directly addressed packages on the install queue
3161    * so we can mark patterns as installed */
3162   for (i = 0; i < job->count; i += 2)
3163     {
3164       how = job->elements[i];
3165       if ((how & SOLVER_JOBMASK) == SOLVER_USERINSTALLED)
3166         {
3167           what = job->elements[i + 1];
3168           select = how & SOLVER_SELECTMASK;
3169           if (select == SOLVER_SOLVABLE && pool->solvables[what].repo != installed)
3170             queue_push(&iq, what);
3171         }
3172     }
3173
3174 #ifdef CLEANDEPSDEBUG
3175   printf("ADDBACK PASS\n");
3176 #endif
3177   for (;;)
3178     {
3179       if (!iq.count)
3180         {
3181           /* supplements pass */
3182           for (ip = installed->start; ip < installed->end; ip++)
3183             {
3184               if (!MAPTST(&installedm, ip))
3185                 continue;
3186               if (MAPTST(&userinstalled, ip - installed->start))
3187                 continue;
3188               s = pool->solvables + ip;
3189               if (!s->supplements)
3190                 continue;
3191               if (MAPTST(&im, ip))
3192                 continue;
3193               supp = s->repo->idarraydata + s->supplements;
3194               while ((sup = *supp++) != 0)
3195                 if (dep_possible(solv, sup, &im))
3196                   break;
3197               if (sup)
3198                 {
3199 #ifdef CLEANDEPSDEBUG
3200                   printf("%s supplemented\n", pool_solvid2str(pool, ip));
3201 #endif
3202                   MAPSET(&im, ip);
3203                   queue_push(&iq, ip);
3204                 }
3205             }
3206           if (!iq.count)
3207             break;
3208         }
3209       ip = queue_shift(&iq);
3210       s = pool->solvables + ip;
3211 #ifdef CLEANDEPSDEBUG
3212       printf("adding back %s\n", pool_solvable2str(pool, s));
3213 #endif
3214       if (s->requires)
3215         {
3216           reqp = s->repo->idarraydata + s->requires;
3217           while ((req = *reqp++) != 0)
3218             {
3219               FOR_PROVIDES(p, pp, req)
3220                 if (MAPTST(&im, p))
3221                   break;
3222               if (p)
3223                 continue;
3224               FOR_PROVIDES(p, pp, req)
3225                 {
3226                   if (!MAPTST(&im, p) && MAPTST(&installedm, p))
3227                     {
3228                       if (p == ip)
3229                         continue;
3230                       if (MAPTST(&userinstalled, p - installed->start))
3231                         continue;
3232 #ifdef CLEANDEPSDEBUG
3233                       printf("%s requires %s\n", pool_solvid2str(pool, ip), pool_solvid2str(pool, p));
3234 #endif
3235                       MAPSET(&im, p);
3236                       queue_push(&iq, p);
3237                     }
3238                 }
3239             }
3240         }
3241       if (s->recommends)
3242         {
3243           reqp = s->repo->idarraydata + s->recommends;
3244           while ((req = *reqp++) != 0)
3245             {
3246               FOR_PROVIDES(p, pp, req)
3247                 if (MAPTST(&im, p))
3248                   break;
3249               if (p)
3250                 continue;
3251               FOR_PROVIDES(p, pp, req)
3252                 {
3253                   if (!MAPTST(&im, p) && MAPTST(&installedm, p))
3254                     {
3255                       if (p == ip)
3256                         continue;
3257                       if (MAPTST(&userinstalled, p - installed->start))
3258                         continue;
3259 #ifdef CLEANDEPSDEBUG
3260                       printf("%s recommends %s\n", pool_solvid2str(pool, ip), pool_solvid2str(pool, p));
3261 #endif
3262                       MAPSET(&im, p);
3263                       queue_push(&iq, p);
3264                     }
3265                 }
3266             }
3267         }
3268     }
3269
3270   queue_free(&iq);
3271   /* make sure the updatepkgs and mistakes are not in the cleandeps map */
3272   if (solv->cleandeps_updatepkgs)
3273     for (i = 0; i < solv->cleandeps_updatepkgs->count; i++)
3274       MAPSET(&im, solv->cleandeps_updatepkgs->elements[i]);
3275   if (solv->cleandeps_mistakes)
3276     for (i = 0; i < solv->cleandeps_mistakes->count; i++)
3277       MAPSET(&im, solv->cleandeps_mistakes->elements[i]);
3278   /* also remove original iq packages */
3279   for (i = 0; i < iqcopy.count; i++)
3280     MAPSET(&im, iqcopy.elements[i]);
3281   queue_free(&iqcopy);
3282   for (p = installed->start; p < installed->end; p++)
3283     {
3284       if (pool->solvables[p].repo != installed)
3285         continue;
3286       if (!MAPTST(&im, p))
3287         MAPSET(cleandepsmap, p - installed->start);
3288     }
3289   map_free(&im);
3290   map_free(&installedm);
3291   map_free(&userinstalled);
3292   queue_free(&xsuppq);
3293 #ifdef CLEANDEPSDEBUG
3294   printf("=== final cleandeps map:\n");
3295   for (p = installed->start; p < installed->end; p++)
3296     if (MAPTST(cleandepsmap, p - installed->start))
3297       printf("  - %s\n", pool_solvid2str(pool, p));
3298 #endif
3299 }
3300
3301
3302 struct trj_data {
3303   Queue *edges;
3304   Id *low;
3305   Id idx;
3306   Id nstack;
3307   Id firstidx;
3308 };
3309
3310 /* Tarjan's SCC algorithm, slightly modifed */
3311 static void
3312 trj_visit(struct trj_data *trj, Id node)
3313 {
3314   Id *low = trj->low;
3315   Queue *edges = trj->edges;
3316   Id nnode, myidx, stackstart;
3317   int i;
3318
3319   low[node] = myidx = trj->idx++;
3320   low[(stackstart = trj->nstack++)] = node;
3321   for (i = edges->elements[node]; (nnode = edges->elements[i]) != 0; i++)
3322     {
3323       Id l = low[nnode];
3324       if (!l)
3325         {
3326           if (!edges->elements[edges->elements[nnode]])
3327             {
3328               trj->idx++;
3329               low[nnode] = -1;
3330               continue;
3331             }
3332           trj_visit(trj, nnode);
3333           l = low[nnode];
3334         }
3335       if (l < 0)
3336         continue;
3337       if (l < trj->firstidx)
3338         {
3339           int k;
3340           for (k = l; low[low[k]] == l; k++)
3341             low[low[k]] = -1;
3342         }
3343       else if (l < low[node])
3344         low[node] = l;
3345     }
3346   if (low[node] == myidx)
3347     {
3348       if (myidx != trj->firstidx)
3349         myidx = -1;
3350       for (i = stackstart; i < trj->nstack; i++)
3351         low[low[i]] = myidx;
3352       trj->nstack = stackstart;
3353     }
3354 }
3355
3356
3357 void
3358 solver_get_unneeded(Solver *solv, Queue *unneededq, int filtered)
3359 {
3360   Repo *installed = solv->installed;
3361   int i;
3362   Map cleandepsmap;
3363
3364   queue_empty(unneededq);
3365   if (!installed || installed->end == installed->start)
3366     return;
3367
3368   map_init(&cleandepsmap, installed->end - installed->start);
3369   solver_createcleandepsmap(solv, &cleandepsmap, 1);
3370   for (i = installed->start; i < installed->end; i++)
3371     if (MAPTST(&cleandepsmap, i - installed->start))
3372       queue_push(unneededq, i);
3373
3374   if (filtered && unneededq->count > 1)
3375     {
3376       Pool *pool = solv->pool;
3377       Queue edges;
3378       Id *nrequires;
3379       Map installedm;
3380       int j, pass, count = unneededq->count;
3381       Id *low;
3382
3383       map_init(&installedm, pool->nsolvables);
3384       for (i = installed->start; i < installed->end; i++)
3385         if (pool->solvables[i].repo == installed)
3386           MAPSET(&installedm, i);
3387
3388       nrequires = solv_calloc(count, sizeof(Id));
3389       queue_init(&edges);
3390       queue_prealloc(&edges, count * 4 + 10);   /* pre-size */
3391
3392       /*
3393        * Go through the solvables in the nodes queue and create edges for
3394        * all requires/recommends/supplements between the nodes.
3395        * The edges are stored in the edges queue, we add 1 to the node
3396        * index so that nodes in the edges queue are != 0 and we can
3397        * terminate the edge list with 0.
3398        * Thus for node element 5, the edges are stored starting at
3399        * edges.elements[6] and are 0-terminated.
3400        */
3401       /* leave first element zero to make things easier */
3402       /* also add trailing zero */
3403       queue_insertn(&edges, 0, 1 + count + 1);
3404
3405       /* first requires and recommends */
3406       for (i = 0; i < count; i++)
3407         {
3408           Solvable *s = pool->solvables + unneededq->elements[i];
3409           edges.elements[i + 1] = edges.count;
3410           for (pass = 0; pass < 2; pass++)
3411             {
3412               int num = 0;
3413               unsigned int off = pass == 0 ? s->requires : s->recommends;
3414               Id p, pp, *dp;
3415               if (off)
3416                 for (dp = s->repo->idarraydata + off; *dp; dp++)
3417                   FOR_PROVIDES(p, pp, *dp)
3418                     {
3419                       Solvable *sp = pool->solvables + p;
3420                       if (s == sp || sp->repo != installed || !MAPTST(&cleandepsmap, p - installed->start))
3421                         continue;
3422                       for (j = 0; j < count; j++)
3423                         if (p == unneededq->elements[j])
3424                           break;
3425                       if (j == count)
3426                         continue;
3427                       if (num && edges.elements[edges.count - 1] == j + 1)
3428                         continue;
3429                       queue_push(&edges, j + 1);
3430                       num++;
3431                     }
3432                 if (pass == 0)
3433                   nrequires[i] = num;
3434             }
3435           queue_push(&edges, 0);
3436         }
3437 #if 0
3438       printf("requires + recommends\n");
3439       for (i = 0; i < count; i++)
3440         {
3441           int j;
3442           printf("  %s (%d requires):\n", pool_solvid2str(pool, unneededq->elements[i]), nrequires[i]);
3443           for (j = edges.elements[i + 1]; edges.elements[j]; j++)
3444             printf("    - %s\n", pool_solvid2str(pool, unneededq->elements[edges.elements[j] - 1]));
3445         }
3446 #endif
3447
3448       /* then add supplements */
3449       for (i = 0; i < count; i++)
3450         {
3451           Solvable *s = pool->solvables + unneededq->elements[i];
3452           if (s->supplements)
3453             {
3454               Id *dp;
3455               int k;
3456               for (dp = s->repo->idarraydata + s->supplements; *dp; dp++)
3457                 if (dep_possible(solv, *dp, &installedm))
3458                   {
3459                     Queue iq;
3460                     Id iqbuf[16];
3461                     queue_init_buffer(&iq, iqbuf, sizeof(iqbuf)/sizeof(*iqbuf));
3462                     dep_pkgcheck(solv, *dp, 0, &iq);
3463                     for (k = 0; k < iq.count; k++)
3464                       {
3465                         Id p = iq.elements[k];
3466                         Solvable *sp = pool->solvables + p;
3467                         if (p == unneededq->elements[i] || sp->repo != installed || !MAPTST(&cleandepsmap, p - installed->start))
3468                           continue;
3469                         for (j = 0; j < count; j++)
3470                           if (p == unneededq->elements[j])
3471                             break;
3472                         /* now add edge from j + 1 to i + 1 */
3473                         queue_insert(&edges, edges.elements[j + 1] + nrequires[j], i + 1);
3474                         /* addapt following edge pointers */
3475                         for (k = j + 2; k < count + 2; k++)
3476                           edges.elements[k]++;
3477                       }
3478                     queue_free(&iq);
3479                   }
3480             }
3481         }
3482 #if 0
3483       /* print result */
3484       printf("+ supplements\n");
3485       for (i = 0; i < count; i++)
3486         {
3487           int j;
3488           printf("  %s (%d requires):\n", pool_solvid2str(pool, unneededq->elements[i]), nrequires[i]);
3489           for (j = edges.elements[i + 1]; edges.elements[j]; j++)
3490             printf("    - %s\n", pool_solvid2str(pool, unneededq->elements[edges.elements[j] - 1]));
3491     }
3492 #endif
3493       map_free(&installedm);
3494
3495       /* now run SCC algo two times, first with requires+recommends+supplements,
3496        * then again without the requires. We run it the second time to get rid
3497        * of packages that got dragged in via recommends/supplements */
3498       /*
3499        * low will contain the result of the SCC search.
3500        * it must be of at least size 2 * (count + 1) and
3501        * must be zero initialized.
3502        * The layout is:
3503        *    0  low low ... low stack stack ...stack 0
3504        *            count              count
3505        */
3506       low = solv_calloc(count + 1, 2 * sizeof(Id));
3507       for (pass = 0; pass < 2; pass++)
3508         {
3509           struct trj_data trj;
3510           if (pass)
3511             {
3512               memset(low, 0, (count + 1) * (2 * sizeof(Id)));
3513               for (i = 0; i < count; i++)
3514                 {
3515                   edges.elements[i + 1] += nrequires[i];
3516                   if (!unneededq->elements[i])
3517                     low[i + 1] = -1;    /* ignore this node */
3518                 }
3519             }
3520           trj.edges = &edges;
3521           trj.low = low;
3522           trj.idx = count + 1;  /* stack starts here */
3523           for (i = 1; i <= count; i++)
3524             {
3525               if (low[i])
3526                 continue;
3527               if (edges.elements[edges.elements[i]])
3528                 {
3529                   trj.firstidx = trj.nstack = trj.idx;
3530                   trj_visit(&trj, i);
3531                 }
3532               else
3533                 {
3534                   Id myidx = trj.idx++;
3535                   low[i] = myidx;
3536                   low[myidx] = i;
3537                 }
3538             }
3539           /* prune packages */
3540           for (i = 0; i < count; i++)
3541             if (low[i + 1] <= 0)
3542               unneededq->elements[i] = 0;
3543         }
3544       solv_free(low);
3545       solv_free(nrequires);
3546       queue_free(&edges);
3547
3548       /* finally remove all pruned entries from unneededq */
3549       for (i = j = 0; i < count; i++)
3550         if (unneededq->elements[i])
3551           unneededq->elements[j++] = unneededq->elements[i];
3552       queue_truncate(unneededq, j);
3553     }
3554   map_free(&cleandepsmap);
3555 }
3556
3557 /* EOF */