src/rules.c

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