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