src/rules.c

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