src/rules.c

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