src/rules.c

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