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