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   if (!allow_all && qs.count && solv->multiversion.size)
1062     {
1063       int i, j;
1064
1065       d = pool_queuetowhatprovides(pool, &qs);
1066       /* filter out all multiversion packages as they don't update */
1067       for (i = j = 0; i < qs.count; i++)
1068         {
1069           if (MAPTST(&solv->multiversion, qs.elements[i]))
1070             {
1071               Solvable *ps = pool->solvables + qs.elements[i];
1072               /* if keepexplicitobsoletes is set and the name is different,
1073                * we assume that there is an obsoletes. XXX: not 100% correct */
1074               if (solv->keepexplicitobsoletes && ps->name != s->name)
1075                 {
1076                   qs.elements[j++] = qs.elements[i];
1077                   continue;
1078                 }
1079               /* it's ok if they have same nevra */
1080               if (ps->name != s->name || ps->evr != s->evr || ps->arch != s->arch)
1081                 continue;
1082             }
1083           qs.elements[j++] = qs.elements[i];
1084         }
1085       if (j < qs.count)
1086         {
1087           if (d && solv->installed && s->repo == solv->installed &&
1088               (solv->updatemap_all || (solv->updatemap.size && MAPTST(&solv->updatemap, s - pool->solvables - solv->installed->start))))
1089             {
1090               if (!solv->multiversionupdaters)
1091                 solv->multiversionupdaters = solv_calloc(solv->installed->end - solv->installed->start, sizeof(Id));
1092               solv->multiversionupdaters[s - pool->solvables - solv->installed->start] = d;
1093             }
1094           if (j == 0 && p == -SYSTEMSOLVABLE && solv->dupmap_all)
1095             {
1096               queue_push(&solv->orphaned, s - pool->solvables); /* treat as orphaned */
1097               j = qs.count;
1098             }
1099           qs.count = j;
1100         }
1101       else if (p != -SYSTEMSOLVABLE)
1102         {
1103           /* could fallthrough, but then we would do pool_queuetowhatprovides twice */
1104           queue_free(&qs);
1105           solver_addrule(solv, p, d);   /* allow update of s */
1106           return;
1107         }
1108     }
1109   if (qs.count && p == -SYSTEMSOLVABLE)
1110     p = queue_shift(&qs);
1111   d = qs.count ? pool_queuetowhatprovides(pool, &qs) : 0;
1112   queue_free(&qs);
1113   solver_addrule(solv, p, d);   /* allow update of s */
1114 }
1115
1116 static inline void
1117 disableupdaterule(Solver *solv, Id p)
1118 {
1119   Rule *r;
1120
1121   MAPSET(&solv->noupdate, p - solv->installed->start);
1122   r = solv->rules + solv->updaterules + (p - solv->installed->start);
1123   if (r->p && r->d >= 0)
1124     solver_disablerule(solv, r);
1125   r = solv->rules + solv->featurerules + (p - solv->installed->start);
1126   if (r->p && r->d >= 0)
1127     solver_disablerule(solv, r);
1128   if (solv->bestrules_pkg)
1129     {
1130       int i, ni;
1131       ni = solv->bestrules_end - solv->bestrules;
1132       for (i = 0; i < ni; i++)
1133         if (solv->bestrules_pkg[i] == p)
1134           solver_disablerule(solv, solv->rules + solv->bestrules + i);
1135     }
1136 }
1137
1138 static inline void
1139 reenableupdaterule(Solver *solv, Id p)
1140 {
1141   Pool *pool = solv->pool;
1142   Rule *r;
1143
1144   MAPCLR(&solv->noupdate, p - solv->installed->start);
1145   r = solv->rules + solv->updaterules + (p - solv->installed->start);
1146   if (r->p)
1147     {
1148       if (r->d < 0)
1149         {
1150           solver_enablerule(solv, r);
1151           IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS)
1152             {
1153               POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "@@@ re-enabling ");
1154               solver_printruleclass(solv, SOLV_DEBUG_SOLUTIONS, r);
1155             }
1156         }
1157     }
1158   else
1159     {
1160       r = solv->rules + solv->featurerules + (p - solv->installed->start);
1161       if (r->p && r->d < 0)
1162         {
1163           solver_enablerule(solv, r);
1164           IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS)
1165             {
1166               POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "@@@ re-enabling ");
1167               solver_printruleclass(solv, SOLV_DEBUG_SOLUTIONS, r);
1168             }
1169         }
1170     }
1171   if (solv->bestrules_pkg)
1172     {
1173       int i, ni;
1174       ni = solv->bestrules_end - solv->bestrules;
1175       for (i = 0; i < ni; i++)
1176         if (solv->bestrules_pkg[i] == p)
1177           solver_enablerule(solv, solv->rules + solv->bestrules + i);
1178     }
1179 }
1180
1181
1182 /***********************************************************************
1183  ***
1184  ***  Infarch rule part
1185  ***
1186  ***  Infarch rules make sure the solver uses the best architecture of
1187  ***  a package if multiple archetectures are available
1188  ***
1189  ***/
1190
1191 void
1192 solver_addinfarchrules(Solver *solv, Map *addedmap)
1193 {
1194   Pool *pool = solv->pool;
1195   Repo *installed = pool->installed;
1196   int first, i, j;
1197   Id p, pp, a, aa, bestarch;
1198   Solvable *s, *ps, *bests;
1199   Queue badq, allowedarchs;
1200   Queue lsq;
1201
1202   queue_init(&badq);
1203   queue_init(&allowedarchs);
1204   queue_init(&lsq);
1205   solv->infarchrules = solv->nrules;
1206   for (i = 1; i < pool->nsolvables; i++)
1207     {
1208       if (i == SYSTEMSOLVABLE || !MAPTST(addedmap, i))
1209         continue;
1210       s = pool->solvables + i;
1211       first = i;
1212       bestarch = 0;
1213       bests = 0;
1214       queue_empty(&allowedarchs);
1215       FOR_PROVIDES(p, pp, s->name)
1216         {
1217           ps = pool->solvables + p;
1218           if (ps->name != s->name || !MAPTST(addedmap, p))
1219             continue;
1220           if (p == i)
1221             first = 0;
1222           if (first)
1223             break;
1224           a = ps->arch;
1225           a = (a <= pool->lastarch) ? pool->id2arch[a] : 0;
1226           if (a != 1 && installed && ps->repo == installed)
1227             {
1228               if (!solv->dupmap_all && !(solv->dupinvolvedmap.size && MAPTST(&solv->dupinvolvedmap, p)))
1229                 queue_pushunique(&allowedarchs, ps->arch);      /* also ok to keep this architecture */
1230               continue;         /* ignore installed solvables when calculating the best arch */
1231             }
1232           if (a && a != 1 && (!bestarch || a < bestarch))
1233             {
1234               bestarch = a;
1235               bests = ps;
1236             }
1237         }
1238       if (first)
1239         continue;
1240
1241       /* speed up common case where installed package already has best arch */
1242       if (allowedarchs.count == 1 && bests && allowedarchs.elements[0] == bests->arch)
1243         allowedarchs.count--;   /* installed arch is best */
1244
1245       if (allowedarchs.count && pool->implicitobsoleteusescolors && installed && bestarch)
1246         {
1247           /* need an extra pass for lockstep checking: we only allow to keep an inferior arch
1248            * if the corresponding installed package is not lock-stepped */
1249           queue_empty(&allowedarchs);
1250           FOR_PROVIDES(p, pp, s->name)
1251             {
1252               Id p2, pp2;
1253               ps = pool->solvables + p;
1254               if (ps->name != s->name || ps->repo != installed || !MAPTST(addedmap, p))
1255                 continue;
1256               if (solv->dupmap_all || (solv->dupinvolvedmap.size && MAPTST(&solv->dupinvolvedmap, p)))
1257                 continue;
1258               a = ps->arch;
1259               a = (a <= pool->lastarch) ? pool->id2arch[a] : 0;
1260               if (!a)
1261                 {
1262                   queue_pushunique(&allowedarchs, ps->arch);    /* strange arch, allow */
1263                   continue;
1264                 }
1265               if (a == 1 || ((a ^ bestarch) & 0xffff0000) == 0)
1266                 continue;
1267               /* have installed package with inferior arch, check if lock-stepped */
1268               FOR_PROVIDES(p2, pp2, s->name)
1269                 {
1270                   Solvable *s2 = pool->solvables + p2;
1271                   Id a2;
1272                   if (p2 == p || s2->name != s->name || s2->evr != pool->solvables[p].evr || s2->arch == pool->solvables[p].arch)
1273                     continue;
1274                   a2 = s2->arch;
1275                   a2 = (a2 <= pool->lastarch) ? pool->id2arch[a2] : 0;
1276                   if (a2 && (a2 == 1 || ((a2 ^ bestarch) & 0xffff0000) == 0))
1277                     break;
1278                 }
1279               if (!p2)
1280                 queue_pushunique(&allowedarchs, ps->arch);
1281             }
1282         }
1283
1284       /* find all bad packages */
1285       queue_empty(&badq);
1286       FOR_PROVIDES(p, pp, s->name)
1287         {
1288           ps = pool->solvables + p;
1289           if (ps->name != s->name || !MAPTST(addedmap, p))
1290             continue;
1291           a = ps->arch;
1292           a = (a <= pool->lastarch) ? pool->id2arch[a] : 0;
1293           if (a != 1 && bestarch && ((a ^ bestarch) & 0xffff0000) != 0)
1294             {
1295               if (installed && ps->repo == installed)
1296                 {
1297                   if (pool->implicitobsoleteusescolors)
1298                     queue_push(&badq, p);               /* special lock-step handling, see below */
1299                   continue;     /* always ok to keep an installed package */
1300                 }
1301               for (j = 0; j < allowedarchs.count; j++)
1302                 {
1303                   aa = allowedarchs.elements[j];
1304                   if (ps->arch == aa)
1305                     break;
1306                   aa = (aa <= pool->lastarch) ? pool->id2arch[aa] : 0;
1307                   if (aa && ((a ^ aa) & 0xffff0000) == 0)
1308                     break;      /* compatible */
1309                 }
1310               if (j == allowedarchs.count)
1311                 queue_push(&badq, p);
1312             }
1313         }
1314
1315       /* block all solvables in the badq! */
1316       for (j = 0; j < badq.count; j++)
1317         {
1318           p = badq.elements[j];
1319           /* lock-step */
1320           if (pool->implicitobsoleteusescolors)
1321             {
1322               Id p2;
1323               int haveinstalled = 0;
1324               queue_empty(&lsq);
1325               FOR_PROVIDES(p2, pp, s->name)
1326                 {
1327                   Solvable *s2 = pool->solvables + p2;
1328                   if (p2 == p || s2->name != s->name || s2->evr != pool->solvables[p].evr || s2->arch == pool->solvables[p].arch)
1329                     continue;
1330                   a = s2->arch;
1331                   a = (a <= pool->lastarch) ? pool->id2arch[a] : 0;
1332                   if (a && (a == 1 || ((a ^ bestarch) & 0xffff000) == 0))
1333                     {
1334                       queue_push(&lsq, p2);
1335                       if (installed && s2->repo == installed)
1336                         haveinstalled = 1;
1337                     }
1338                 }
1339               if (installed && pool->solvables[p].repo == installed && !haveinstalled)
1340                 continue;       /* installed package not in lock-step */
1341             }
1342           solver_addrule(solv, -p, lsq.count ? pool_queuetowhatprovides(pool, &lsq) : 0);
1343         }
1344     }
1345   queue_free(&lsq);
1346   queue_free(&badq);
1347   queue_free(&allowedarchs);
1348   solv->infarchrules_end = solv->nrules;
1349 }
1350
1351 static inline void
1352 disableinfarchrule(Solver *solv, Id name)
1353 {
1354   Pool *pool = solv->pool;
1355   Rule *r;
1356   int i;
1357   for (i = solv->infarchrules, r = solv->rules + i; i < solv->infarchrules_end; i++, r++)
1358     {
1359       if (r->p < 0 && r->d >= 0 && pool->solvables[-r->p].name == name)
1360         solver_disablerule(solv, r);
1361     }
1362 }
1363
1364 static inline void
1365 reenableinfarchrule(Solver *solv, Id name)
1366 {
1367   Pool *pool = solv->pool;
1368   Rule *r;
1369   int i;
1370   for (i = solv->infarchrules, r = solv->rules + i; i < solv->infarchrules_end; i++, r++)
1371     {
1372       if (r->p < 0 && r->d < 0 && pool->solvables[-r->p].name == name)
1373         {
1374           solver_enablerule(solv, r);
1375           IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS)
1376             {
1377               POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "@@@ re-enabling ");
1378               solver_printruleclass(solv, SOLV_DEBUG_SOLUTIONS, r);
1379             }
1380         }
1381     }
1382 }
1383
1384
1385 /***********************************************************************
1386  ***
1387  ***  Dup rule part
1388  ***
1389  ***  Dup rules make sure a package is selected from the specified dup
1390  ***  repositories if an update candidate is included in one of them.
1391  ***
1392  ***/
1393
1394 static inline void
1395 add_cleandeps_package(Solver *solv, Id p)
1396 {
1397   if (!solv->cleandeps_updatepkgs)
1398     {
1399       solv->cleandeps_updatepkgs = solv_calloc(1, sizeof(Queue));
1400       queue_init(solv->cleandeps_updatepkgs);
1401     }
1402   queue_pushunique(solv->cleandeps_updatepkgs, p);
1403 }
1404
1405 static inline void
1406 solver_addtodupmaps(Solver *solv, Id p, Id how, int targeted)
1407 {
1408   Pool *pool = solv->pool;
1409   Solvable *ps, *s = pool->solvables + p;
1410   Repo *installed = solv->installed;
1411   Id pi, pip, obs, *obsp;
1412
1413   MAPSET(&solv->dupinvolvedmap, p);
1414   if (targeted)
1415     MAPSET(&solv->dupmap, p);
1416   FOR_PROVIDES(pi, pip, s->name)
1417     {
1418       ps = pool->solvables + pi;
1419       if (ps->name != s->name)
1420         continue;
1421       MAPSET(&solv->dupinvolvedmap, pi);
1422       if (targeted && ps->repo == installed && solv->obsoletes && solv->obsoletes[pi - installed->start])
1423         {
1424           Id *opp, pi2;
1425           for (opp = solv->obsoletes_data + solv->obsoletes[pi - installed->start]; (pi2 = *opp++) != 0;)
1426             if (pool->solvables[pi2].repo != installed)
1427               MAPSET(&solv->dupinvolvedmap, pi2);
1428         }
1429       if (ps->repo == installed && (how & SOLVER_FORCEBEST) != 0)
1430         {
1431           if (!solv->bestupdatemap.size)
1432             map_grow(&solv->bestupdatemap, installed->end - installed->start);
1433           MAPSET(&solv->bestupdatemap, pi - installed->start);
1434         }
1435       if (ps->repo == installed && (how & SOLVER_CLEANDEPS) != 0)
1436         add_cleandeps_package(solv, pi);
1437       if (!targeted && ps->repo != installed)
1438         MAPSET(&solv->dupmap, pi);
1439     }
1440   if (s->repo == installed && solv->obsoletes && solv->obsoletes[p - installed->start])
1441     {
1442       Id *opp;
1443       for (opp = solv->obsoletes_data + solv->obsoletes[p - installed->start]; (pi = *opp++) != 0;)
1444         {
1445           ps = pool->solvables + pi;
1446           if (ps->repo == installed)
1447             continue;
1448           MAPSET(&solv->dupinvolvedmap, pi);
1449           if (!targeted)
1450             MAPSET(&solv->dupmap, pi);
1451         }
1452     }
1453   if (targeted && s->repo != installed && s->obsoletes)
1454     {
1455       /* XXX: check obsoletes/provides combination */
1456       obsp = s->repo->idarraydata + s->obsoletes;
1457       while ((obs = *obsp++) != 0)
1458         {
1459           FOR_PROVIDES(pi, pip, obs)
1460             {
1461               Solvable *ps = pool->solvables + pi;
1462               if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
1463                 continue;
1464               if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
1465                 continue;
1466               MAPSET(&solv->dupinvolvedmap, pi);
1467               if (targeted && ps->repo == installed && solv->obsoletes && solv->obsoletes[pi - installed->start])
1468                 {
1469                   Id *opp, pi2;
1470                   for (opp = solv->obsoletes_data + solv->obsoletes[pi - installed->start]; (pi2 = *opp++) != 0;)
1471                     if (pool->solvables[pi2].repo != installed)
1472                       MAPSET(&solv->dupinvolvedmap, pi2);
1473                 }
1474               if (ps->repo == installed && (how & SOLVER_FORCEBEST) != 0)
1475                 {
1476                   if (!solv->bestupdatemap.size)
1477                     map_grow(&solv->bestupdatemap, installed->end - installed->start);
1478                   MAPSET(&solv->bestupdatemap, pi - installed->start);
1479                 }
1480               if (ps->repo == installed && (how & SOLVER_CLEANDEPS) != 0)
1481                 add_cleandeps_package(solv, pi);
1482             }
1483         }
1484     }
1485 }
1486
1487 void
1488 solver_createdupmaps(Solver *solv)
1489 {
1490   Queue *job = &solv->job;
1491   Pool *pool = solv->pool;
1492   Repo *installed = solv->installed;
1493   Id select, how, what, p, pp;
1494   Solvable *s;
1495   int i, targeted;
1496
1497   map_init(&solv->dupmap, pool->nsolvables);
1498   map_init(&solv->dupinvolvedmap, pool->nsolvables);
1499   for (i = 0; i < job->count; i += 2)
1500     {
1501       how = job->elements[i];
1502       select = job->elements[i] & SOLVER_SELECTMASK;
1503       what = job->elements[i + 1];
1504       switch (how & SOLVER_JOBMASK)
1505         {
1506         case SOLVER_DISTUPGRADE:
1507           if (select == SOLVER_SOLVABLE_REPO)
1508             {
1509               Repo *repo;
1510               if (what <= 0 || what > pool->nrepos)
1511                 break;
1512               repo = pool_id2repo(pool, what);
1513               if (!repo)
1514                 break;
1515               if (repo != installed && !(how & SOLVER_TARGETED) && solv->noautotarget)
1516                 break;
1517               targeted = repo != installed || (how & SOLVER_TARGETED) != 0;
1518               FOR_REPO_SOLVABLES(repo, p, s)
1519                 {
1520                   if (repo != installed && !pool_installable(pool, s))
1521                     continue;
1522                   solver_addtodupmaps(solv, p, how, targeted);
1523                 }
1524             }
1525           else
1526             {
1527               targeted = how & SOLVER_TARGETED ? 1 : 0;
1528               if (installed && !targeted && !solv->noautotarget)
1529                 {
1530                   FOR_JOB_SELECT(p, pp, select, what)
1531                     if (pool->solvables[p].repo == installed)
1532                       break;
1533                   targeted = p == 0;
1534                 }
1535               else if (!installed && !solv->noautotarget)
1536                 targeted = 1;
1537               FOR_JOB_SELECT(p, pp, select, what)
1538                 {
1539                   Solvable *s = pool->solvables + p;
1540                   if (!s->repo)
1541                     continue;
1542                   if (s->repo != installed && !targeted)
1543                     continue;
1544                   if (s->repo != installed && !pool_installable(pool, s))
1545                     continue;
1546                   solver_addtodupmaps(solv, p, how, targeted);
1547                 }
1548             }
1549           break;
1550         default:
1551           break;
1552         }
1553     }
1554   MAPCLR(&solv->dupinvolvedmap, SYSTEMSOLVABLE);
1555 }
1556
1557 void
1558 solver_freedupmaps(Solver *solv)
1559 {
1560   map_free(&solv->dupmap);
1561   /* we no longer free solv->dupinvolvedmap as we need it in
1562    * policy's priority pruning code. sigh. */
1563 }
1564
1565 void
1566 solver_addduprules(Solver *solv, Map *addedmap)
1567 {
1568   Pool *pool = solv->pool;
1569   Id p, pp;
1570   Solvable *s, *ps;
1571   int first, i;
1572
1573   solv->duprules = solv->nrules;
1574   for (i = 1; i < pool->nsolvables; i++)
1575     {
1576       if (i == SYSTEMSOLVABLE || !MAPTST(addedmap, i))
1577         continue;
1578       s = pool->solvables + i;
1579       first = i;
1580       FOR_PROVIDES(p, pp, s->name)
1581         {
1582           ps = pool->solvables + p;
1583           if (ps->name != s->name || !MAPTST(addedmap, p))
1584             continue;
1585           if (p == i)
1586             first = 0;
1587           if (first)
1588             break;
1589           if (!MAPTST(&solv->dupinvolvedmap, p))
1590             continue;
1591           if (solv->installed && ps->repo == solv->installed)
1592             {
1593               if (!solv->updatemap.size)
1594                 map_grow(&solv->updatemap, solv->installed->end - solv->installed->start);
1595               MAPSET(&solv->updatemap, p - solv->installed->start);
1596               if (!MAPTST(&solv->dupmap, p))
1597                 {
1598                   Id ip, ipp;
1599                   /* is installed identical to a good one? */
1600                   FOR_PROVIDES(ip, ipp, ps->name)
1601                     {
1602                       Solvable *is = pool->solvables + ip;
1603                       if (!MAPTST(&solv->dupmap, ip))
1604                         continue;
1605                       if (is->evr == ps->evr && solvable_identical(ps, is))
1606                         break;
1607                     }
1608                   if (!ip)
1609                     solver_addrule(solv, -p, 0);        /* no match, sorry */
1610                   else
1611                     MAPSET(&solv->dupmap, p);           /* for best rules processing */
1612                 }
1613             }
1614           else if (!MAPTST(&solv->dupmap, p))
1615             solver_addrule(solv, -p, 0);
1616         }
1617     }
1618   solv->duprules_end = solv->nrules;
1619 }
1620
1621
1622 static inline void
1623 disableduprule(Solver *solv, Id name)
1624 {
1625   Pool *pool = solv->pool;
1626   Rule *r;
1627   int i;
1628   for (i = solv->duprules, r = solv->rules + i; i < solv->duprules_end; i++, r++)
1629     {
1630       if (r->p < 0 && r->d >= 0 && pool->solvables[-r->p].name == name)
1631         solver_disablerule(solv, r);
1632     }
1633 }
1634
1635 static inline void
1636 reenableduprule(Solver *solv, Id name)
1637 {
1638   Pool *pool = solv->pool;
1639   Rule *r;
1640   int i;
1641   for (i = solv->duprules, r = solv->rules + i; i < solv->duprules_end; i++, r++)
1642     {
1643       if (r->p < 0 && r->d < 0 && pool->solvables[-r->p].name == name)
1644         {
1645           solver_enablerule(solv, r);
1646           IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS)
1647             {
1648               POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "@@@ re-enabling ");
1649               solver_printruleclass(solv, SOLV_DEBUG_SOLUTIONS, r);
1650             }
1651         }
1652     }
1653 }
1654
1655
1656 /***********************************************************************
1657  ***
1658  ***  Policy rule disabling/reenabling
1659  ***
1660  ***  Disable all policy rules that conflict with our jobs. If a job
1661  ***  gets disabled later on, reenable the involved policy rules again.
1662  ***
1663  ***/
1664
1665 #define DISABLE_UPDATE  1
1666 #define DISABLE_INFARCH 2
1667 #define DISABLE_DUP     3
1668
1669 /*
1670  * add all installed packages that package p obsoletes to Queue q.
1671  * Package p is not installed. Also, we know that if
1672  * solv->keepexplicitobsoletes is not set, p is not in the multiversion map.
1673  * Entries may get added multiple times.
1674  */
1675 static void
1676 add_obsoletes(Solver *solv, Id p, Queue *q)
1677 {
1678   Pool *pool = solv->pool;
1679   Repo *installed = solv->installed;
1680   Id p2, pp2;
1681   Solvable *s = pool->solvables + p;
1682   Id obs, *obsp;
1683   Id lastp2 = 0;
1684
1685   if (!solv->keepexplicitobsoletes || !(solv->multiversion.size && MAPTST(&solv->multiversion, p)))
1686     {
1687       FOR_PROVIDES(p2, pp2, s->name)
1688         {
1689           Solvable *ps = pool->solvables + p2;
1690           if (ps->repo != installed)
1691             continue;
1692           if (!pool->implicitobsoleteusesprovides && ps->name != s->name)
1693             continue;
1694           if (pool->implicitobsoleteusescolors && !pool_colormatch(pool, s, ps))
1695             continue;
1696           queue_push(q, p2);
1697           lastp2 = p2;
1698         }
1699     }
1700   if (!s->obsoletes)
1701     return;
1702   obsp = s->repo->idarraydata + s->obsoletes;
1703   while ((obs = *obsp++) != 0)
1704     FOR_PROVIDES(p2, pp2, obs)
1705       {
1706         Solvable *ps = pool->solvables + p2;
1707         if (ps->repo != installed)
1708           continue;
1709         if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
1710           continue;
1711         if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
1712           continue;
1713         if (p2 == lastp2)
1714           continue;
1715         queue_push(q, p2);
1716         lastp2 = p2;
1717       }
1718 }
1719
1720 /*
1721  * Call add_obsoletes and intersect the result with the
1722  * elements in Queue q starting at qstart.
1723  * Assumes that it's the first call if qstart == q->count.
1724  * May use auxillary map m for the intersection process, all
1725  * elements of q starting at qstart must have their bit cleared.
1726  * (This is also true after the function returns.)
1727  */
1728 static void
1729 intersect_obsoletes(Solver *solv, Id p, Queue *q, int qstart, Map *m)
1730 {
1731   int i, j;
1732   int qcount = q->count;
1733
1734   add_obsoletes(solv, p, q);
1735   if (qcount == qstart)
1736     return;     /* first call */
1737   if (qcount == q->count)
1738     j = qstart;
1739   else if (qcount == qstart + 1)
1740     {
1741       /* easy if there's just one element */
1742       j = qstart;
1743       for (i = qcount; i < q->count; i++)
1744         if (q->elements[i] == q->elements[qstart])
1745           {
1746             j++;        /* keep the element */
1747             break;
1748           }
1749     }
1750   else if (!m->size && q->count - qstart <= 8)
1751     {
1752       /* faster than a map most of the time */
1753       int k;
1754       for (i = j = qstart; i < qcount; i++)
1755         {
1756           Id ip = q->elements[i];
1757           for (k = qcount; k < q->count; k++)
1758             if (q->elements[k] == ip)
1759               {
1760                 q->elements[j++] = ip;
1761                 break;
1762               }
1763         }
1764     }
1765   else
1766     {
1767       /* for the really pathologic cases we use the map */
1768       Repo *installed = solv->installed;
1769       if (!m->size)
1770         map_init(m, installed->end - installed->start);
1771       for (i = qcount; i < q->count; i++)
1772         MAPSET(m, q->elements[i] - installed->start);
1773       for (i = j = qstart; i < qcount; i++)
1774         if (MAPTST(m, q->elements[i] - installed->start))
1775           {
1776             MAPCLR(m, q->elements[i] - installed->start);
1777             q->elements[j++] = q->elements[i];
1778           }
1779     }
1780   queue_truncate(q, j);
1781 }
1782
1783 static void
1784 jobtodisablelist(Solver *solv, Id how, Id what, Queue *q)
1785 {
1786   Pool *pool = solv->pool;
1787   Id select, p, pp;
1788   Repo *installed;
1789   Solvable *s;
1790   int i, j, set, qstart;
1791   Map omap;
1792
1793   installed = solv->installed;
1794   select = how & SOLVER_SELECTMASK;
1795   switch (how & SOLVER_JOBMASK)
1796     {
1797     case SOLVER_INSTALL:
1798       set = how & SOLVER_SETMASK;
1799       if (!(set & SOLVER_NOAUTOSET))
1800         {
1801           /* automatically add set bits by analysing the job */
1802           if (select == SOLVER_SOLVABLE_NAME)
1803             set |= SOLVER_SETNAME;
1804           if (select == SOLVER_SOLVABLE)
1805             set |= SOLVER_SETNAME | SOLVER_SETARCH | SOLVER_SETVENDOR | SOLVER_SETREPO | SOLVER_SETEVR;
1806           else if ((select == SOLVER_SOLVABLE_NAME || select == SOLVER_SOLVABLE_PROVIDES) && ISRELDEP(what))
1807             {
1808               Reldep *rd = GETRELDEP(pool, what);
1809               if (rd->flags == REL_EQ && select == SOLVER_SOLVABLE_NAME)
1810                 {
1811                   if (pool->disttype != DISTTYPE_DEB)
1812                     {
1813                       const char *rel = strrchr(pool_id2str(pool, rd->evr), '-');
1814                       set |= rel ? SOLVER_SETEVR : SOLVER_SETEV;
1815                     }
1816                   else
1817                     set |= SOLVER_SETEVR;
1818                 }
1819               if (rd->flags <= 7 && ISRELDEP(rd->name))
1820                 rd = GETRELDEP(pool, rd->name);
1821               if (rd->flags == REL_ARCH)
1822                 set |= SOLVER_SETARCH;
1823             }
1824         }
1825       else
1826         set &= ~SOLVER_NOAUTOSET;
1827       if (!set)
1828         return;
1829       if ((set & SOLVER_SETARCH) != 0 && solv->infarchrules != solv->infarchrules_end)
1830         {
1831           if (select == SOLVER_SOLVABLE)
1832             queue_push2(q, DISABLE_INFARCH, pool->solvables[what].name);
1833           else
1834             {
1835               int qcnt = q->count;
1836               /* does not work for SOLVER_SOLVABLE_ALL and SOLVER_SOLVABLE_REPO, but
1837                  they are not useful for SOLVER_INSTALL jobs anyway */
1838               FOR_JOB_SELECT(p, pp, select, what)
1839                 {
1840                   s = pool->solvables + p;
1841                   /* unify names */
1842                   for (i = qcnt; i < q->count; i += 2)
1843                     if (q->elements[i + 1] == s->name)
1844                       break;
1845                   if (i < q->count)
1846                     continue;
1847                   queue_push2(q, DISABLE_INFARCH, s->name);
1848                 }
1849             }
1850         }
1851       if ((set & SOLVER_SETREPO) != 0 && solv->duprules != solv->duprules_end)
1852         {
1853           if (select == SOLVER_SOLVABLE)
1854             queue_push2(q, DISABLE_DUP, pool->solvables[what].name);
1855           else
1856             {
1857               int qcnt = q->count;
1858               FOR_JOB_SELECT(p, pp, select, what)
1859                 {
1860                   s = pool->solvables + p;
1861                   /* unify names */
1862                   for (i = qcnt; i < q->count; i += 2)
1863                     if (q->elements[i + 1] == s->name)
1864                       break;
1865                   if (i < q->count)
1866                     continue;
1867                   queue_push2(q, DISABLE_DUP, s->name);
1868                 }
1869             }
1870         }
1871       if (!installed || installed->end == installed->start)
1872         return;
1873       /* now the hard part: disable some update rules */
1874
1875       /* first check if we have multiversion or installed packages in the job */
1876       i = j = 0;
1877       FOR_JOB_SELECT(p, pp, select, what)
1878         {
1879           if (pool->solvables[p].repo == installed)
1880             j = p;
1881           else if (solv->multiversion.size && MAPTST(&solv->multiversion, p) && !solv->keepexplicitobsoletes)
1882             return;
1883           i++;
1884         }
1885       if (j)    /* have installed packages */
1886         {
1887           /* this is for dupmap_all jobs, it can go away if we create
1888            * duprules for them */
1889           if (i == 1 && (set & SOLVER_SETREPO) != 0)
1890             queue_push2(q, DISABLE_UPDATE, j);
1891           return;
1892         }
1893
1894       omap.size = 0;
1895       qstart = q->count;
1896       FOR_JOB_SELECT(p, pp, select, what)
1897         {
1898           intersect_obsoletes(solv, p, q, qstart, &omap);
1899           if (q->count == qstart)
1900             break;
1901         }
1902       if (omap.size)
1903         map_free(&omap);
1904
1905       if (qstart == q->count)
1906         return;         /* nothing to prune */
1907
1908       /* convert result to (DISABLE_UPDATE, p) pairs */
1909       i = q->count;
1910       for (j = qstart; j < i; j++)
1911         queue_push(q, q->elements[j]);
1912       for (j = qstart; j < q->count; j += 2)
1913         {
1914           q->elements[j] = DISABLE_UPDATE;
1915           q->elements[j + 1] = q->elements[i++];
1916         }
1917
1918       /* now that we know which installed packages are obsoleted check each of them */
1919       if ((set & (SOLVER_SETEVR | SOLVER_SETARCH | SOLVER_SETVENDOR)) == (SOLVER_SETEVR | SOLVER_SETARCH | SOLVER_SETVENDOR))
1920         return;         /* all is set, nothing to do */
1921
1922       for (i = j = qstart; i < q->count; i += 2)
1923         {
1924           Solvable *is = pool->solvables + q->elements[i + 1];
1925           FOR_JOB_SELECT(p, pp, select, what)
1926             {
1927               int illegal = 0;
1928               s = pool->solvables + p;
1929               if ((set & SOLVER_SETEVR) != 0)
1930                 illegal |= POLICY_ILLEGAL_DOWNGRADE;    /* ignore */
1931               if ((set & SOLVER_SETNAME) != 0)
1932                 illegal |= POLICY_ILLEGAL_NAMECHANGE;   /* ignore */
1933               if ((set & SOLVER_SETARCH) != 0)
1934                 illegal |= POLICY_ILLEGAL_ARCHCHANGE;   /* ignore */
1935               if ((set & SOLVER_SETVENDOR) != 0)
1936                 illegal |= POLICY_ILLEGAL_VENDORCHANGE; /* ignore */
1937               illegal = policy_is_illegal(solv, is, s, illegal);
1938               if (illegal && illegal == POLICY_ILLEGAL_DOWNGRADE && (set & SOLVER_SETEV) != 0)
1939                 {
1940                   /* it's ok if the EV is different */
1941                   if (pool_evrcmp(pool, is->evr, s->evr, EVRCMP_COMPARE_EVONLY) != 0)
1942                     illegal = 0;
1943                 }
1944               if (illegal)
1945                 break;
1946             }
1947           if (!p)
1948             {
1949               /* no package conflicts with the update rule */
1950               /* thus keep the DISABLE_UPDATE */
1951               q->elements[j + 1] = q->elements[i + 1];
1952               j += 2;
1953             }
1954         }
1955       queue_truncate(q, j);
1956       return;
1957
1958     case SOLVER_ERASE:
1959       if (!installed)
1960         break;
1961       if (select == SOLVER_SOLVABLE_ALL || (select == SOLVER_SOLVABLE_REPO && what == installed->repoid))
1962         FOR_REPO_SOLVABLES(installed, p, s)
1963           queue_push2(q, DISABLE_UPDATE, p);
1964       FOR_JOB_SELECT(p, pp, select, what)
1965         if (pool->solvables[p].repo == installed)
1966           {
1967             queue_push2(q, DISABLE_UPDATE, p);
1968             if (solv->instbuddy && solv->instbuddy[p - installed->start] > 1)
1969               queue_push2(q, DISABLE_UPDATE, solv->instbuddy[p - installed->start]);
1970           }
1971       return;
1972     default:
1973       return;
1974     }
1975 }
1976
1977 /* disable all policy rules that are in conflict with our job list */
1978 void
1979 solver_disablepolicyrules(Solver *solv)
1980 {
1981   Queue *job = &solv->job;
1982   int i, j;
1983   Queue allq;
1984   Rule *r;
1985   Id lastjob = -1;
1986   Id allqbuf[128];
1987
1988   queue_init_buffer(&allq, allqbuf, sizeof(allqbuf)/sizeof(*allqbuf));
1989
1990   for (i = solv->jobrules; i < solv->jobrules_end; i++)
1991     {
1992       r = solv->rules + i;
1993       if (r->d < 0)     /* disabled? */
1994         continue;
1995       j = solv->ruletojob.elements[i - solv->jobrules];
1996       if (j == lastjob)
1997         continue;
1998       lastjob = j;
1999       jobtodisablelist(solv, job->elements[j], job->elements[j + 1], &allq);
2000     }
2001   if (solv->cleandepsmap.size)
2002     {
2003       solver_createcleandepsmap(solv, &solv->cleandepsmap, 0);
2004       for (i = solv->installed->start; i < solv->installed->end; i++)
2005         if (MAPTST(&solv->cleandepsmap, i - solv->installed->start))
2006           queue_push2(&allq, DISABLE_UPDATE, i);
2007     }
2008   MAPZERO(&solv->noupdate);
2009   for (i = 0; i < allq.count; i += 2)
2010     {
2011       Id type = allq.elements[i], arg = allq.elements[i + 1];
2012       switch(type)
2013         {
2014         case DISABLE_UPDATE:
2015           disableupdaterule(solv, arg);
2016           break;
2017         case DISABLE_INFARCH:
2018           disableinfarchrule(solv, arg);
2019           break;
2020         case DISABLE_DUP:
2021           disableduprule(solv, arg);
2022           break;
2023         default:
2024           break;
2025         }
2026     }
2027   queue_free(&allq);
2028 }
2029
2030 /* we just disabled job #jobidx, now reenable all policy rules that were
2031  * disabled because of this job */
2032 void
2033 solver_reenablepolicyrules(Solver *solv, int jobidx)
2034 {
2035   Queue *job = &solv->job;
2036   int i, j, k, ai;
2037   Queue q, allq;
2038   Rule *r;
2039   Id lastjob = -1;
2040   Id qbuf[32], allqbuf[32];
2041
2042   queue_init_buffer(&q, qbuf, sizeof(qbuf)/sizeof(*qbuf));
2043   jobtodisablelist(solv, job->elements[jobidx - 1], job->elements[jobidx], &q);
2044   if (!q.count)
2045     {
2046       queue_free(&q);
2047       return;
2048     }
2049   /* now remove everything from q that is disabled by other jobs */
2050
2051   /* first remove cleandeps packages, they count as DISABLE_UPDATE */
2052   if (solv->cleandepsmap.size)
2053     {
2054       solver_createcleandepsmap(solv, &solv->cleandepsmap, 0);
2055       for (j = k = 0; j < q.count; j += 2)
2056         {
2057           if (q.elements[j] == DISABLE_UPDATE)
2058             {
2059               Id p = q.elements[j + 1];
2060               if (p >= solv->installed->start && p < solv->installed->end && MAPTST(&solv->cleandepsmap, p - solv->installed->start))
2061                 continue;       /* remove element from q */
2062             }
2063           q.elements[k++] = q.elements[j];
2064           q.elements[k++] = q.elements[j + 1];
2065         }
2066       q.count = k;
2067       if (!q.count)
2068         {
2069           queue_free(&q);
2070           return;
2071         }
2072     }
2073
2074   /* now go through the disable list of all other jobs */
2075   queue_init_buffer(&allq, allqbuf, sizeof(allqbuf)/sizeof(*allqbuf));
2076   for (i = solv->jobrules; i < solv->jobrules_end; i++)
2077     {
2078       r = solv->rules + i;
2079       if (r->d < 0)     /* disabled? */
2080         continue;
2081       j = solv->ruletojob.elements[i - solv->jobrules];
2082       if (j == lastjob)
2083         continue;
2084       lastjob = j;
2085       jobtodisablelist(solv, job->elements[j], job->elements[j + 1], &allq);
2086       if (!allq.count)
2087         continue;
2088       /* remove all elements in allq from q */
2089       for (j = k = 0; j < q.count; j += 2)
2090         {
2091           Id type = q.elements[j], arg = q.elements[j + 1];
2092           for (ai = 0; ai < allq.count; ai += 2)
2093             if (allq.elements[ai] == type && allq.elements[ai + 1] == arg)
2094               break;
2095           if (ai < allq.count)
2096             continue;   /* found it in allq, remove element from q */
2097           q.elements[k++] = q.elements[j];
2098           q.elements[k++] = q.elements[j + 1];
2099         }
2100       q.count = k;
2101       if (!q.count)
2102         {
2103           queue_free(&q);
2104           queue_free(&allq);
2105           return;
2106         }
2107       queue_empty(&allq);
2108     }
2109   queue_free(&allq);
2110
2111   /* now re-enable anything that's left in q */
2112   for (j = 0; j < q.count; j += 2)
2113     {
2114       Id type = q.elements[j], arg = q.elements[j + 1];
2115       switch(type)
2116         {
2117         case DISABLE_UPDATE:
2118           reenableupdaterule(solv, arg);
2119           break;
2120         case DISABLE_INFARCH:
2121           reenableinfarchrule(solv, arg);
2122           break;
2123         case DISABLE_DUP:
2124           reenableduprule(solv, arg);
2125           break;
2126         }
2127     }
2128   queue_free(&q);
2129 }
2130
2131 /* we just removed a package from the cleandeps map, now reenable all policy rules that were
2132  * disabled because of this */
2133 void
2134 solver_reenablepolicyrules_cleandeps(Solver *solv, Id pkg)
2135 {
2136   Queue *job = &solv->job;
2137   int i, j;
2138   Queue allq;
2139   Rule *r;
2140   Id lastjob = -1;
2141   Id allqbuf[128];
2142
2143   queue_init_buffer(&allq, allqbuf, sizeof(allqbuf)/sizeof(*allqbuf));
2144   for (i = solv->jobrules; i < solv->jobrules_end; i++)
2145     {
2146       r = solv->rules + i;
2147       if (r->d < 0)     /* disabled? */
2148         continue;
2149       j = solv->ruletojob.elements[i - solv->jobrules];
2150       if (j == lastjob)
2151         continue;
2152       lastjob = j;
2153       jobtodisablelist(solv, job->elements[j], job->elements[j + 1], &allq);
2154     }
2155   for (i = 0; i < allq.count; i += 2)
2156     if (allq.elements[i] == DISABLE_UPDATE && allq.elements[i + 1] == pkg)
2157       break;
2158   if (i == allq.count)
2159     reenableupdaterule(solv, pkg);
2160   queue_free(&allq);
2161 }
2162
2163
2164 /***********************************************************************
2165  ***
2166  ***  Rule info part, tell the user what the rule is about.
2167  ***
2168  ***/
2169
2170 static void
2171 addrpmruleinfo(Solver *solv, Id p, Id d, int type, Id dep)
2172 {
2173   Pool *pool = solv->pool;
2174   Rule *r;
2175   Id w2, op, od, ow2;
2176
2177   /* check if this creates the rule we're searching for */
2178   r = solv->rules + solv->ruleinfoq->elements[0];
2179   op = r->p;
2180   od = r->d < 0 ? -r->d - 1 : r->d;
2181   ow2 = 0;
2182
2183   /* normalize */
2184   w2 = d > 0 ? 0 : d;
2185   if (p < 0 && d > 0 && (!pool->whatprovidesdata[d] || !pool->whatprovidesdata[d + 1]))
2186     {
2187       w2 = pool->whatprovidesdata[d];
2188       d = 0;
2189     }
2190   if (p > 0 && d < 0)           /* this hack is used for buddy deps */
2191     {
2192       w2 = p;
2193       p = d;
2194     }
2195
2196   if (d > 0)
2197     {
2198       if (p != op && !od)
2199         return;
2200       if (d != od)
2201         {
2202           Id *dp = pool->whatprovidesdata + d;
2203           Id *odp = pool->whatprovidesdata + od;
2204           while (*dp)
2205             if (*dp++ != *odp++)
2206               return;
2207           if (*odp)
2208             return;
2209         }
2210       w2 = 0;
2211       /* handle multiversion conflict rules */
2212       if (p < 0 && pool->whatprovidesdata[d] < 0)
2213         {
2214           w2 = pool->whatprovidesdata[d];
2215           /* XXX: free memory */
2216         }
2217     }
2218   else
2219     {
2220       if (od)
2221         return;
2222       ow2 = r->w2;
2223       if (p > w2)
2224         {
2225           if (w2 != op || p != ow2)
2226             return;
2227         }
2228       else
2229         {
2230           if (p != op || w2 != ow2)
2231             return;
2232         }
2233     }
2234   /* yep, rule matches. record info */
2235   queue_push(solv->ruleinfoq, type);
2236   if (type == SOLVER_RULE_RPM_SAME_NAME)
2237     {
2238       /* we normalize same name order */
2239       queue_push(solv->ruleinfoq, op < 0 ? -op : 0);
2240       queue_push(solv->ruleinfoq, ow2 < 0 ? -ow2 : 0);
2241     }
2242   else
2243     {
2244       queue_push(solv->ruleinfoq, p < 0 ? -p : 0);
2245       queue_push(solv->ruleinfoq, w2 < 0 ? -w2 : 0);
2246     }
2247   queue_push(solv->ruleinfoq, dep);
2248 }
2249
2250 static int
2251 solver_allruleinfos_cmp(const void *ap, const void *bp, void *dp)
2252 {
2253   const Id *a = ap, *b = bp;
2254   int r;
2255
2256   r = a[0] - b[0];
2257   if (r)
2258     return r;
2259   r = a[1] - b[1];
2260   if (r)
2261     return r;
2262   r = a[2] - b[2];
2263   if (r)
2264     return r;
2265   r = a[3] - b[3];
2266   if (r)
2267     return r;
2268   return 0;
2269 }
2270
2271 static void
2272 getrpmruleinfos(Solver *solv, Rule *r, Queue *rq)
2273 {
2274   Pool *pool = solv->pool;
2275 #ifdef ENABLE_LINKED_PKGS
2276   Id l, d;
2277 #endif
2278   if (r->p >= 0)
2279     return;
2280   queue_push(rq, r - solv->rules);      /* push the rule we're interested in */
2281   solv->ruleinfoq = rq;
2282   solver_addrpmrulesforsolvable(solv, pool->solvables - r->p, 0);
2283   /* also try reverse direction for conflicts */
2284   if ((r->d == 0 || r->d == -1) && r->w2 < 0)
2285     solver_addrpmrulesforsolvable(solv, pool->solvables - r->w2, 0);
2286 #ifdef ENABLE_LINKED_PKGS
2287   /* check linked packages */
2288   d = 0;
2289   if ((r->d == 0 || r->d == -1))
2290     l = r->w2;
2291   else
2292     {
2293       d = r->d < 0 ? -r->d - 1 : r->d;
2294       l = pool->whatprovidesdata[d++];
2295     }
2296   for (; l; l = (d ? pool->whatprovidesdata[d++] : 0))
2297     {
2298       if (l <= 0 || !strchr(pool_id2str(pool, pool->solvables[l].name), ':'))
2299         break;
2300       if (has_package_link(pool, pool->solvables + l))
2301         add_package_link(solv, pool->solvables + l, 0, 0);
2302     }
2303 #endif
2304   solv->ruleinfoq = 0;
2305   queue_shift(rq);
2306 }
2307
2308 int
2309 solver_allruleinfos(Solver *solv, Id rid, Queue *rq)
2310 {
2311   Rule *r = solv->rules + rid;
2312   int i, j;
2313
2314   queue_empty(rq);
2315   if (rid <= 0 || rid >= solv->rpmrules_end)
2316     {
2317       Id type, from, to, dep;
2318       type = solver_ruleinfo(solv, rid, &from, &to, &dep);
2319       queue_push(rq, type);
2320       queue_push(rq, from);
2321       queue_push(rq, to);
2322       queue_push(rq, dep);
2323       return 1;
2324     }
2325   getrpmruleinfos(solv, r, rq);
2326   /* now sort & unify em */
2327   if (!rq->count)
2328     return 0;
2329   solv_sort(rq->elements, rq->count / 4, 4 * sizeof(Id), solver_allruleinfos_cmp, 0);
2330   /* throw out identical entries */
2331   for (i = j = 0; i < rq->count; i += 4)
2332     {
2333       if (j)
2334         {
2335           if (rq->elements[i] == rq->elements[j - 4] &&
2336               rq->elements[i + 1] == rq->elements[j - 3] &&
2337               rq->elements[i + 2] == rq->elements[j - 2] &&
2338               rq->elements[i + 3] == rq->elements[j - 1])
2339             continue;
2340         }
2341       rq->elements[j++] = rq->elements[i];
2342       rq->elements[j++] = rq->elements[i + 1];
2343       rq->elements[j++] = rq->elements[i + 2];
2344       rq->elements[j++] = rq->elements[i + 3];
2345     }
2346   rq->count = j;
2347   return j / 4;
2348 }
2349
2350 SolverRuleinfo
2351 solver_ruleinfo(Solver *solv, Id rid, Id *fromp, Id *top, Id *depp)
2352 {
2353   Pool *pool = solv->pool;
2354   Rule *r = solv->rules + rid;
2355   SolverRuleinfo type = SOLVER_RULE_UNKNOWN;
2356
2357   if (fromp)
2358     *fromp = 0;
2359   if (top)
2360     *top = 0;
2361   if (depp)
2362     *depp = 0;
2363   if (rid > 0 && rid < solv->rpmrules_end)
2364     {
2365       Queue rq;
2366       int i;
2367
2368       if (r->p >= 0)
2369         return SOLVER_RULE_RPM;
2370       if (fromp)
2371         *fromp = -r->p;
2372       queue_init(&rq);
2373       getrpmruleinfos(solv, r, &rq);
2374       type = SOLVER_RULE_RPM;
2375       for (i = 0; i < rq.count; i += 4)
2376         {
2377           Id qt, qo, qp, qd;
2378           qt = rq.elements[i];
2379           qp = rq.elements[i + 1];
2380           qo = rq.elements[i + 2];
2381           qd = rq.elements[i + 3];
2382           if (type == SOLVER_RULE_RPM || type > qt)
2383             {
2384               type = qt;
2385               if (fromp)
2386                 *fromp = qp;
2387               if (top)
2388                 *top = qo;
2389               if (depp)
2390                 *depp = qd;
2391             }
2392         }
2393       queue_free(&rq);
2394       return type;
2395     }
2396   if (rid >= solv->jobrules && rid < solv->jobrules_end)
2397     {
2398       Id jidx = solv->ruletojob.elements[rid - solv->jobrules];
2399       if (fromp)
2400         *fromp = jidx;
2401       if (top)
2402         *top = solv->job.elements[jidx];
2403       if (depp)
2404         *depp = solv->job.elements[jidx + 1];
2405       if ((r->d == 0 || r->d == -1) && r->w2 == 0 && r->p == -SYSTEMSOLVABLE)
2406         {
2407           Id how = solv->job.elements[jidx];
2408           if ((how & (SOLVER_JOBMASK|SOLVER_SELECTMASK)) == (SOLVER_INSTALL|SOLVER_SOLVABLE_NAME))
2409             return SOLVER_RULE_JOB_UNKNOWN_PACKAGE;
2410           if ((how & (SOLVER_JOBMASK|SOLVER_SELECTMASK)) == (SOLVER_INSTALL|SOLVER_SOLVABLE_PROVIDES))
2411             return SOLVER_RULE_JOB_NOTHING_PROVIDES_DEP;
2412           if ((how & (SOLVER_JOBMASK|SOLVER_SELECTMASK)) == (SOLVER_ERASE|SOLVER_SOLVABLE_NAME))
2413             return SOLVER_RULE_JOB_PROVIDED_BY_SYSTEM;
2414           if ((how & (SOLVER_JOBMASK|SOLVER_SELECTMASK)) == (SOLVER_ERASE|SOLVER_SOLVABLE_PROVIDES))
2415             return SOLVER_RULE_JOB_PROVIDED_BY_SYSTEM;
2416           return SOLVER_RULE_JOB_UNSUPPORTED;
2417         }
2418       return SOLVER_RULE_JOB;
2419     }
2420   if (rid >= solv->updaterules && rid < solv->updaterules_end)
2421     {
2422       if (fromp)
2423         *fromp = solv->installed->start + (rid - solv->updaterules);
2424       return SOLVER_RULE_UPDATE;
2425     }
2426   if (rid >= solv->featurerules && rid < solv->featurerules_end)
2427     {
2428       if (fromp)
2429         *fromp = solv->installed->start + (rid - solv->featurerules);
2430       return SOLVER_RULE_FEATURE;
2431     }
2432   if (rid >= solv->duprules && rid < solv->duprules_end)
2433     {
2434       if (fromp)
2435         *fromp = -r->p;
2436       if (depp)
2437         *depp = pool->solvables[-r->p].name;
2438       return SOLVER_RULE_DISTUPGRADE;
2439     }
2440   if (rid >= solv->infarchrules && rid < solv->infarchrules_end)
2441     {
2442       if (fromp)
2443         *fromp = -r->p;
2444       if (depp)
2445         *depp = pool->solvables[-r->p].name;
2446       return SOLVER_RULE_INFARCH;
2447     }
2448   if (rid >= solv->bestrules && rid < solv->bestrules_end)
2449     {
2450       return SOLVER_RULE_BEST;
2451     }
2452   if (rid >= solv->choicerules && rid < solv->choicerules_end)
2453     {
2454       return SOLVER_RULE_CHOICE;
2455     }
2456   if (rid >= solv->learntrules)
2457     {
2458       return SOLVER_RULE_LEARNT;
2459     }
2460   return SOLVER_RULE_UNKNOWN;
2461 }
2462
2463 SolverRuleinfo
2464 solver_ruleclass(Solver *solv, Id rid)
2465 {
2466   if (rid <= 0)
2467     return SOLVER_RULE_UNKNOWN;
2468   if (rid > 0 && rid < solv->rpmrules_end)
2469     return SOLVER_RULE_RPM;
2470   if (rid >= solv->jobrules && rid < solv->jobrules_end)
2471     return SOLVER_RULE_JOB;
2472   if (rid >= solv->updaterules && rid < solv->updaterules_end)
2473     return SOLVER_RULE_UPDATE;
2474   if (rid >= solv->featurerules && rid < solv->featurerules_end)
2475     return SOLVER_RULE_FEATURE;
2476   if (rid >= solv->duprules && rid < solv->duprules_end)
2477     return SOLVER_RULE_DISTUPGRADE;
2478   if (rid >= solv->infarchrules && rid < solv->infarchrules_end)
2479     return SOLVER_RULE_INFARCH;
2480   if (rid >= solv->bestrules && rid < solv->bestrules_end)
2481     return SOLVER_RULE_BEST;
2482   if (rid >= solv->choicerules && rid < solv->choicerules_end)
2483     return SOLVER_RULE_CHOICE;
2484   if (rid >= solv->learntrules)
2485     return SOLVER_RULE_LEARNT;
2486   return SOLVER_RULE_UNKNOWN;
2487 }
2488
2489 void
2490 solver_ruleliterals(Solver *solv, Id rid, Queue *q)
2491 {
2492   Pool *pool = solv->pool;
2493   Id p, pp;
2494   Rule *r;
2495
2496   queue_empty(q);
2497   r = solv->rules + rid;
2498   FOR_RULELITERALS(p, pp, r)
2499     if (p != -SYSTEMSOLVABLE)
2500       queue_push(q, p);
2501   if (!q->count)
2502     queue_push(q, -SYSTEMSOLVABLE);     /* hmm, better to return an empty result? */
2503 }
2504
2505 int
2506 solver_rule2jobidx(Solver *solv, Id rid)
2507 {
2508   if (rid < solv->jobrules || rid >= solv->jobrules_end)
2509     return 0;
2510   return solv->ruletojob.elements[rid - solv->jobrules] + 1;
2511 }
2512
2513 /* job rule introspection */
2514 Id
2515 solver_rule2job(Solver *solv, Id rid, Id *whatp)
2516 {
2517   int idx;
2518   if (rid < solv->jobrules || rid >= solv->jobrules_end)
2519     {
2520       if (whatp)
2521         *whatp = 0;
2522       return 0;
2523     }
2524   idx = solv->ruletojob.elements[rid - solv->jobrules];
2525   if (whatp)
2526     *whatp = solv->job.elements[idx + 1];
2527   return solv->job.elements[idx];
2528 }
2529
2530 /* update/feature rule introspection */
2531 Id
2532 solver_rule2solvable(Solver *solv, Id rid)
2533 {
2534   if (rid >= solv->updaterules && rid < solv->updaterules_end)
2535     return rid - solv->updaterules;
2536   if (rid >= solv->featurerules && rid < solv->featurerules_end)
2537     return rid - solv->featurerules;
2538   return 0;
2539 }
2540
2541 static void
2542 solver_rule2rules_rec(Solver *solv, Id rid, Queue *q, Map *seen)
2543 {
2544   int i;
2545   Id rid2;
2546
2547   if (seen)
2548     MAPSET(seen, rid);
2549   for (i = solv->learnt_why.elements[rid - solv->learntrules]; (rid2 = solv->learnt_pool.elements[i]) != 0; i++)
2550     {
2551       if (seen)
2552         {
2553           if (MAPTST(seen, rid2))
2554             continue;
2555           if (rid2 >= solv->learntrules)
2556             solver_rule2rules_rec(solv, rid2, q, seen);
2557           continue;
2558         }
2559       queue_push(q, rid2);
2560     }
2561 }
2562
2563 /* learnt rule introspection */
2564 void
2565 solver_rule2rules(Solver *solv, Id rid, Queue *q, int recursive)
2566 {
2567   queue_empty(q);
2568   if (rid < solv->learntrules || rid >= solv->nrules)
2569     return;
2570   if (recursive)
2571     {
2572       Map seen;
2573       map_init(&seen, solv->nrules);
2574       solver_rule2rules_rec(solv, rid, q, &seen);
2575       map_free(&seen);
2576     }
2577   else
2578     solver_rule2rules_rec(solv, rid, q, 0);
2579 }
2580
2581
2582 /* check if the newest versions of pi still provides the dependency we're looking for */
2583 static int
2584 solver_choicerulecheck(Solver *solv, Id pi, Rule *r, Map *m)
2585 {
2586   Pool *pool = solv->pool;
2587   Rule *ur;
2588   Queue q;
2589   Id p, pp, qbuf[32];
2590   int i;
2591
2592   ur = solv->rules + solv->updaterules + (pi - pool->installed->start);
2593   if (!ur->p)
2594     ur = solv->rules + solv->featurerules + (pi - pool->installed->start);
2595   if (!ur->p)
2596     return 0;
2597   queue_init_buffer(&q, qbuf, sizeof(qbuf)/sizeof(*qbuf));
2598   FOR_RULELITERALS(p, pp, ur)
2599     if (p > 0)
2600       queue_push(&q, p);
2601   if (q.count > 1)
2602     policy_filter_unwanted(solv, &q, POLICY_MODE_CHOOSE);
2603   for (i = 0; i < q.count; i++)
2604     if (MAPTST(m, q.elements[i]))
2605       break;
2606   /* 1: none of the newest versions provide it */
2607   i = i == q.count ? 1 : 0;
2608   queue_free(&q);
2609   return i;
2610 }
2611
2612 static inline void
2613 queue_removeelement(Queue *q, Id el)
2614 {
2615   int i, j;
2616   for (i = 0; i < q->count; i++)
2617     if (q->elements[i] == el)
2618       break;
2619   if (i < q->count)
2620     {
2621       for (j = i++; i < q->count; i++)
2622         if (q->elements[i] != el)
2623           q->elements[j++] = q->elements[i];
2624       queue_truncate(q, j);
2625     }
2626 }
2627
2628 void
2629 solver_addchoicerules(Solver *solv)
2630 {
2631   Pool *pool = solv->pool;
2632   Map m, mneg;
2633   Rule *r;
2634   Queue q, qi;
2635   int i, j, rid, havechoice;
2636   Id p, d, pp;
2637   Id p2, pp2;
2638   Solvable *s, *s2;
2639   Id lastaddedp, lastaddedd;
2640   int lastaddedcnt;
2641   unsigned int now;
2642
2643   solv->choicerules = solv->nrules;
2644   if (!pool->installed)
2645     {
2646       solv->choicerules_end = solv->nrules;
2647       return;
2648     }
2649   now = solv_timems(0);
2650   solv->choicerules_ref = solv_calloc(solv->rpmrules_end, sizeof(Id));
2651   queue_init(&q);
2652   queue_init(&qi);
2653   map_init(&m, pool->nsolvables);
2654   map_init(&mneg, pool->nsolvables);
2655   /* set up negative assertion map from infarch and dup rules */
2656   for (rid = solv->infarchrules, r = solv->rules + rid; rid < solv->infarchrules_end; rid++, r++)
2657     if (r->p < 0 && !r->w2 && (r->d == 0 || r->d == -1))
2658       MAPSET(&mneg, -r->p);
2659   for (rid = solv->duprules, r = solv->rules + rid; rid < solv->duprules_end; rid++, r++)
2660     if (r->p < 0 && !r->w2 && (r->d == 0 || r->d == -1))
2661       MAPSET(&mneg, -r->p);
2662   lastaddedp = 0;
2663   lastaddedd = 0;
2664   lastaddedcnt = 0;
2665   for (rid = 1; rid < solv->rpmrules_end ; rid++)
2666     {
2667       r = solv->rules + rid;
2668       if (r->p >= 0 || ((r->d == 0 || r->d == -1) && r->w2 < 0))
2669         continue;       /* only look at requires rules */
2670       /* solver_printrule(solv, SOLV_DEBUG_RESULT, r); */
2671       queue_empty(&q);
2672       queue_empty(&qi);
2673       havechoice = 0;
2674       FOR_RULELITERALS(p, pp, r)
2675         {
2676           if (p < 0)
2677             continue;
2678           s = pool->solvables + p;
2679           if (!s->repo)
2680             continue;
2681           if (s->repo == pool->installed)
2682             {
2683               queue_push(&q, p);
2684               continue;
2685             }
2686           /* check if this package is "blocked" by a installed package */
2687           s2 = 0;
2688           FOR_PROVIDES(p2, pp2, s->name)
2689             {
2690               s2 = pool->solvables + p2;
2691               if (s2->repo != pool->installed)
2692                 continue;
2693               if (!pool->implicitobsoleteusesprovides && s->name != s2->name)
2694                 continue;
2695               if (pool->implicitobsoleteusescolors && !pool_colormatch(pool, s, s2))
2696                 continue;
2697               break;
2698             }
2699           if (p2)
2700             {
2701               /* found installed package p2 that we can update to p */
2702               if (MAPTST(&mneg, p))
2703                 continue;
2704               if (policy_is_illegal(solv, s2, s, 0))
2705                 continue;
2706 #if 0
2707               if (solver_choicerulecheck(solv, p2, r, &m))
2708                 continue;
2709               queue_push(&qi, p2);
2710 #else
2711               queue_push2(&qi, p2, p);
2712 #endif
2713               queue_push(&q, p);
2714               continue;
2715             }
2716           if (s->obsoletes)
2717             {
2718               Id obs, *obsp = s->repo->idarraydata + s->obsoletes;
2719               s2 = 0;
2720               while ((obs = *obsp++) != 0)
2721                 {
2722                   FOR_PROVIDES(p2, pp2, obs)
2723                     {
2724                       s2 = pool->solvables + p2;
2725                       if (s2->repo != pool->installed)
2726                         continue;
2727                       if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p2, obs))
2728                         continue;
2729                       if (pool->obsoleteusescolors && !pool_colormatch(pool, s, s2))
2730                         continue;
2731                       break;
2732                     }
2733                   if (p2)
2734                     break;
2735                 }
2736               if (obs)
2737                 {
2738                   /* found installed package p2 that we can update to p */
2739                   if (MAPTST(&mneg, p))
2740                     continue;
2741                   if (policy_is_illegal(solv, s2, s, 0))
2742                     continue;
2743 #if 0
2744                   if (solver_choicerulecheck(solv, p2, r, &m))
2745                     continue;
2746                   queue_push(&qi, p2);
2747 #else
2748                   queue_push2(&qi, p2, p);
2749 #endif
2750                   queue_push(&q, p);
2751                   continue;
2752                 }
2753             }
2754           /* package p is independent of the installed ones */
2755           havechoice = 1;
2756         }
2757       if (!havechoice || !q.count || !qi.count)
2758         continue;       /* no choice */
2759
2760       FOR_RULELITERALS(p, pp, r)
2761         if (p > 0)
2762           MAPSET(&m, p);
2763
2764       /* do extra checking */
2765       for (i = j = 0; i < qi.count; i += 2)
2766         {
2767           p2 = qi.elements[i];
2768           if (!p2)
2769             continue;
2770           if (solver_choicerulecheck(solv, p2, r, &m))
2771             {
2772               /* oops, remove element p from q */
2773               queue_removeelement(&q, qi.elements[i + 1]);
2774               continue;
2775             }
2776           qi.elements[j++] = p2;
2777         }
2778       queue_truncate(&qi, j);
2779       if (!q.count || !qi.count)
2780         {
2781           FOR_RULELITERALS(p, pp, r)
2782             if (p > 0)
2783               MAPCLR(&m, p);
2784           continue;
2785         }
2786
2787
2788       /* now check the update rules of the installed package.
2789        * if all packages of the update rules are contained in
2790        * the dependency rules, there's no need to set up the choice rule */
2791       for (i = 0; i < qi.count; i++)
2792         {
2793           Rule *ur;
2794           if (!qi.elements[i])
2795             continue;
2796           ur = solv->rules + solv->updaterules + (qi.elements[i] - pool->installed->start);
2797           if (!ur->p)
2798             ur = solv->rules + solv->featurerules + (qi.elements[i] - pool->installed->start);
2799           if (!ur->p)
2800             continue;
2801           FOR_RULELITERALS(p, pp, ur)
2802             if (!MAPTST(&m, p))
2803               break;
2804           if (p)
2805             break;
2806           for (j = i + 1; j < qi.count; j++)
2807             if (qi.elements[i] == qi.elements[j])
2808               qi.elements[j] = 0;
2809         }
2810       /* empty map again */
2811       FOR_RULELITERALS(p, pp, r)
2812         if (p > 0)
2813           MAPCLR(&m, p);
2814       if (i == qi.count)
2815         {
2816 #if 0
2817           printf("skipping choice ");
2818           solver_printrule(solv, SOLV_DEBUG_RESULT, solv->rules + rid);
2819 #endif
2820           continue;
2821         }
2822
2823       /* don't add identical rules */
2824       if (lastaddedp == r->p && lastaddedcnt == q.count)
2825         {
2826           for (i = 0; i < q.count; i++)
2827             if (q.elements[i] != pool->whatprovidesdata[lastaddedd + i])
2828               break;
2829           if (i == q.count)
2830             continue;   /* already added that one */
2831         }
2832       d = q.count ? pool_queuetowhatprovides(pool, &q) : 0;
2833
2834       lastaddedp = r->p;
2835       lastaddedd = d;
2836       lastaddedcnt = q.count;
2837
2838       solver_addrule(solv, r->p, d);
2839       queue_push(&solv->weakruleq, solv->nrules - 1);
2840       solv->choicerules_ref[solv->nrules - 1 - solv->choicerules] = rid;
2841 #if 0
2842       printf("OLD ");
2843       solver_printrule(solv, SOLV_DEBUG_RESULT, solv->rules + rid);
2844       printf("WEAK CHOICE ");
2845       solver_printrule(solv, SOLV_DEBUG_RESULT, solv->rules + solv->nrules - 1);
2846 #endif
2847     }
2848   queue_free(&q);
2849   queue_free(&qi);
2850   map_free(&m);
2851   map_free(&mneg);
2852   solv->choicerules_end = solv->nrules;
2853   /* shrink choicerules_ref */
2854   solv->choicerules_ref = solv_realloc2(solv->choicerules_ref, solv->choicerules_end - solv->choicerules, sizeof(Id));
2855   POOL_DEBUG(SOLV_DEBUG_STATS, "choice rule creation took %d ms\n", solv_timems(now));
2856 }
2857
2858 /* called when a choice rule is disabled by analyze_unsolvable. We also
2859  * have to disable all other choice rules so that the best packages get
2860  * picked */
2861 void
2862 solver_disablechoicerules(Solver *solv, Rule *r)
2863 {
2864   Id rid, p, pp;
2865   Pool *pool = solv->pool;
2866   Map m;
2867   Rule *or;
2868
2869   or = solv->rules + solv->choicerules_ref[(r - solv->rules) - solv->choicerules];
2870   map_init(&m, pool->nsolvables);
2871   FOR_RULELITERALS(p, pp, or)
2872     if (p > 0)
2873       MAPSET(&m, p);
2874   FOR_RULELITERALS(p, pp, r)
2875     if (p > 0)
2876       MAPCLR(&m, p);
2877   for (rid = solv->choicerules; rid < solv->choicerules_end; rid++)
2878     {
2879       r = solv->rules + rid;
2880       if (r->d < 0)
2881         continue;
2882       or = solv->rules + solv->choicerules_ref[(r - solv->rules) - solv->choicerules];
2883       FOR_RULELITERALS(p, pp, or)
2884         if (p > 0 && MAPTST(&m, p))
2885           break;
2886       if (p)
2887         solver_disablerule(solv, r);
2888     }
2889 }
2890
2891 static void
2892 prune_to_update_targets(Solver *solv, Id *cp, Queue *q)
2893 {
2894   int i, j;
2895   Id p, *cp2;
2896   for (i = j = 0; i < q->count; i++)
2897     {
2898       p = q->elements[i];
2899       for (cp2 = cp; *cp2; cp2++)
2900         if (*cp2 == p)
2901           {
2902             q->elements[j++] = p;
2903             break;
2904           }
2905     }
2906   queue_truncate(q, j);
2907 }
2908
2909 static void
2910 prune_to_dup_packages(Solver *solv, Id p, Queue *q)
2911 {
2912   int i, j;
2913   for (i = j = 0; i < q->count; i++)
2914     {
2915       Id p = q->elements[i];
2916       if (MAPTST(&solv->dupmap, p))
2917         q->elements[j++] = p;
2918     }
2919   queue_truncate(q, j);
2920 }
2921
2922 void
2923 solver_addbestrules(Solver *solv, int havebestinstalljobs)
2924 {
2925   Pool *pool = solv->pool;
2926   Id p;
2927   Solvable *s;
2928   Repo *installed = solv->installed;
2929   Queue q, q2;
2930   Rule *r;
2931   Queue r2pkg;
2932   int i, oldcnt;
2933
2934   solv->bestrules = solv->nrules;
2935   if (!installed)
2936     {
2937       solv->bestrules_end = solv->nrules;
2938       return;
2939     }
2940   queue_init(&q);
2941   queue_init(&q2);
2942   queue_init(&r2pkg);
2943
2944   if (havebestinstalljobs)
2945     {
2946       for (i = 0; i < solv->job.count; i += 2)
2947         {
2948           if ((solv->job.elements[i] & (SOLVER_JOBMASK | SOLVER_FORCEBEST)) == (SOLVER_INSTALL | SOLVER_FORCEBEST))
2949             {
2950               int j;
2951               Id p2, pp2;
2952               for (j = 0; j < solv->ruletojob.count; j++)
2953                 if (solv->ruletojob.elements[j] == i)
2954                   break;
2955               if (j == solv->ruletojob.count)
2956                 continue;
2957               r = solv->rules + solv->jobrules + j;
2958               queue_empty(&q);
2959               FOR_RULELITERALS(p2, pp2, r)
2960                 if (p2 > 0)
2961                   queue_push(&q, p2);
2962               if (!q.count)
2963                 continue;       /* orphaned */
2964               /* select best packages, just look at prio and version */
2965               oldcnt = q.count;
2966               policy_filter_unwanted(solv, &q, POLICY_MODE_RECOMMEND);
2967               if (q.count == oldcnt)
2968                 continue;       /* nothing filtered */
2969               p2 = queue_shift(&q);
2970               solver_addrule(solv, p2, q.count ? pool_queuetowhatprovides(pool, &q) : 0);
2971               queue_push(&r2pkg, -(solv->jobrules + j));
2972             }
2973         }
2974     }
2975
2976   if (solv->bestupdatemap_all || solv->bestupdatemap.size)
2977     {
2978       FOR_REPO_SOLVABLES(installed, p, s)
2979         {
2980           Id d, p2, pp2;
2981           if (!solv->updatemap_all && (!solv->updatemap.size || !MAPTST(&solv->updatemap, p - installed->start)))
2982             continue;
2983           if (!solv->bestupdatemap_all && (!solv->bestupdatemap.size || !MAPTST(&solv->bestupdatemap, p - installed->start)))
2984             continue;
2985           queue_empty(&q);
2986           if (solv->bestobeypolicy)
2987             r = solv->rules + solv->updaterules + (p - installed->start);
2988           else
2989             {
2990               r = solv->rules + solv->featurerules + (p - installed->start);
2991               if (!r->p)        /* identical to update rule? */
2992                 r = solv->rules + solv->updaterules + (p - installed->start);
2993             }
2994           if (solv->multiversionupdaters && (d = solv->multiversionupdaters[p - installed->start]) != 0 && r == solv->rules + solv->updaterules + (p - installed->start))
2995             {
2996               /* need to check multiversionupdaters */
2997               if (r->p == p)    /* be careful with the dup case */
2998                 queue_push(&q, p);
2999               while ((p2 = pool->whatprovidesdata[d++]) != 0)
3000                 queue_push(&q, p2);
3001             }
3002           else
3003             {
3004               FOR_RULELITERALS(p2, pp2, r)
3005                 if (p2 > 0)
3006                   queue_push(&q, p2);
3007             }
3008           if (solv->update_targets && solv->update_targets->elements[p - installed->start])
3009             prune_to_update_targets(solv, solv->update_targets->elements + solv->update_targets->elements[p - installed->start], &q);
3010           if (solv->dupinvolvedmap.size && MAPTST(&solv->dupinvolvedmap, p))
3011             prune_to_dup_packages(solv, p, &q);
3012           /* select best packages, just look at prio and version */
3013           policy_filter_unwanted(solv, &q, POLICY_MODE_RECOMMEND);
3014           if (!q.count)
3015             continue;   /* orphaned */
3016           if (solv->bestobeypolicy)
3017             {
3018               /* also filter the best of the feature rule packages and add them */
3019               r = solv->rules + solv->featurerules + (p - installed->start);
3020               if (r->p)
3021                 {
3022                   int j;
3023                   queue_empty(&q2);
3024                   FOR_RULELITERALS(p2, pp2, r)
3025                     if (p2 > 0)
3026                       queue_push(&q2, p2);
3027                   if (solv->update_targets && solv->update_targets->elements[p - installed->start])
3028                     prune_to_update_targets(solv, solv->update_targets->elements + solv->update_targets->elements[p - installed->start], &q2);
3029                   if (solv->dupinvolvedmap.size && MAPTST(&solv->dupinvolvedmap, p))
3030                     prune_to_dup_packages(solv, p, &q2);
3031                   policy_filter_unwanted(solv, &q2, POLICY_MODE_RECOMMEND);
3032                   for (j = 0; j < q2.count; j++)
3033                     queue_pushunique(&q, q2.elements[j]);
3034                 }
3035             }
3036           p2 = queue_shift(&q);
3037           solver_addrule(solv, p2, q.count ? pool_queuetowhatprovides(pool, &q) : 0);
3038           queue_push(&r2pkg, p);
3039         }
3040     }
3041   if (r2pkg.count)
3042     solv->bestrules_pkg = solv_memdup2(r2pkg.elements, r2pkg.count, sizeof(Id));
3043   solv->bestrules_end = solv->nrules;
3044   queue_free(&q);
3045   queue_free(&q2);
3046   queue_free(&r2pkg);
3047 }
3048
3049 #undef CLEANDEPSDEBUG
3050
3051 /*
3052  * This functions collects all packages that are looked at
3053  * when a dependency is checked. We need it to "pin" installed
3054  * packages when removing a supplemented package in createcleandepsmap.
3055  * Here's an not uncommon example:
3056  *   A contains "Supplements: packageand(B, C)"
3057  *   B contains "Requires: A"
3058  * Now if we remove C, the supplements is no longer true,
3059  * thus we also remove A. Without the dep_pkgcheck function, we
3060  * would now also remove B, but this is wrong, as adding back
3061  * C doesn't make the supplements true again. Thus we "pin" B
3062  * when we remove A.
3063  * There's probably a better way to do this, but I haven't come
3064  * up with it yet ;)
3065  */
3066 static inline void
3067 dep_pkgcheck(Solver *solv, Id dep, Map *m, Queue *q)
3068 {
3069   Pool *pool = solv->pool;
3070   Id p, pp;
3071
3072   if (ISRELDEP(dep))
3073     {
3074       Reldep *rd = GETRELDEP(pool, dep);
3075       if (rd->flags >= 8)
3076         {
3077           if (rd->flags == REL_AND)
3078             {
3079               dep_pkgcheck(solv, rd->name, m, q);
3080               dep_pkgcheck(solv, rd->evr, m, q);
3081               return;
3082             }
3083           if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
3084             return;
3085           if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
3086             return;
3087         }
3088     }
3089   FOR_PROVIDES(p, pp, dep)
3090     if (!m || MAPTST(m, p))
3091       queue_push(q, p);
3092 }
3093
3094 static int
3095 check_xsupp(Solver *solv, Queue *depq, Id dep)
3096 {
3097   Pool *pool = solv->pool;
3098   Id p, pp;
3099
3100   if (ISRELDEP(dep))
3101     {
3102       Reldep *rd = GETRELDEP(pool, dep);
3103       if (rd->flags >= 8)
3104         {
3105           if (rd->flags == REL_AND)
3106             {
3107               if (!check_xsupp(solv, depq, rd->name))
3108                 return 0;
3109               return check_xsupp(solv, depq, rd->evr);
3110             }
3111           if (rd->flags == REL_OR)
3112             {
3113               if (check_xsupp(solv, depq, rd->name))
3114                 return 1;
3115               return check_xsupp(solv, depq, rd->evr);
3116             }
3117           if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
3118             return solver_splitprovides(solv, rd->evr);
3119           if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
3120             return solver_dep_installed(solv, rd->evr);
3121         }
3122       if (depq && rd->flags == REL_NAMESPACE)
3123         {
3124           int i;
3125           for (i = 0; i < depq->count; i++)
3126             if (depq->elements[i] == dep || depq->elements[i] == rd->name)
3127              return 1;
3128         }
3129     }
3130   FOR_PROVIDES(p, pp, dep)
3131     if (p == SYSTEMSOLVABLE || pool->solvables[p].repo == solv->installed)
3132       return 1;
3133   return 0;
3134 }
3135
3136 static inline int
3137 queue_contains(Queue *q, Id id)
3138 {
3139   int i;
3140   for (i = 0; i < q->count; i++)
3141     if (q->elements[i] == id)
3142       return 1;
3143   return 0;
3144 }
3145
3146
3147 /*
3148  * Find all installed packages that are no longer
3149  * needed regarding the current solver job.
3150  *
3151  * The algorithm is:
3152  * - remove pass: remove all packages that could have
3153  *   been dragged in by the obsoleted packages.
3154  *   i.e. if package A is obsolete and contains "Requires: B",
3155  *   also remove B, as installing A will have pulled in B.
3156  *   after this pass, we have a set of still installed packages
3157  *   with broken dependencies.
3158  * - add back pass:
3159  *   now add back all packages that the still installed packages
3160  *   require.
3161  *
3162  * The cleandeps packages are the packages removed in the first
3163  * pass and not added back in the second pass.
3164  *
3165  * If we search for unneeded packages (unneeded is true), we
3166  * simply remove all packages except the userinstalled ones in
3167  * the first pass.
3168  */
3169 static void
3170 solver_createcleandepsmap(Solver *solv, Map *cleandepsmap, int unneeded)
3171 {
3172   Pool *pool = solv->pool;
3173   Repo *installed = solv->installed;
3174   Queue *job = &solv->job;
3175   Map userinstalled;
3176   Map im;
3177   Map installedm;
3178   Rule *r;
3179   Id rid, how, what, select;
3180   Id p, pp, ip, jp;
3181   Id req, *reqp, sup, *supp;
3182   Solvable *s;
3183   Queue iq, iqcopy, xsuppq;
3184   int i;
3185
3186   map_empty(cleandepsmap);
3187   if (!installed || installed->end == installed->start)
3188     return;
3189   map_init(&userinstalled, installed->end - installed->start);
3190   map_init(&im, pool->nsolvables);
3191   map_init(&installedm, pool->nsolvables);
3192   queue_init(&iq);
3193   queue_init(&xsuppq);
3194
3195   for (i = 0; i < job->count; i += 2)
3196     {
3197       how = job->elements[i];
3198       if ((how & SOLVER_JOBMASK) == SOLVER_USERINSTALLED)
3199         {
3200           what = job->elements[i + 1];
3201           select = how & SOLVER_SELECTMASK;
3202           if (select == SOLVER_SOLVABLE_ALL || (select == SOLVER_SOLVABLE_REPO && what == installed->repoid))
3203             FOR_REPO_SOLVABLES(installed, p, s)
3204               MAPSET(&userinstalled, p - installed->start);
3205           FOR_JOB_SELECT(p, pp, select, what)
3206             if (pool->solvables[p].repo == installed)
3207               MAPSET(&userinstalled, p - installed->start);
3208         }
3209       if ((how & (SOLVER_JOBMASK | SOLVER_SELECTMASK)) == (SOLVER_ERASE | SOLVER_SOLVABLE_PROVIDES))
3210         {
3211           what = job->elements[i + 1];
3212           if (ISRELDEP(what))
3213             {
3214               Reldep *rd = GETRELDEP(pool, what);
3215               if (rd->flags != REL_NAMESPACE)
3216                 continue;
3217               if (rd->evr == 0)
3218                 {
3219                   queue_pushunique(&iq, rd->name);
3220                   continue;
3221                 }
3222               FOR_PROVIDES(p, pp, what)
3223                 if (p)
3224                   break;
3225               if (p)
3226                 continue;
3227               queue_pushunique(&iq, what);
3228             }
3229         }
3230     }
3231
3232   /* have special namespace cleandeps erases */
3233   if (iq.count)
3234     {
3235       for (ip = solv->installed->start; ip < solv->installed->end; ip++)
3236         {
3237           s = pool->solvables + ip;
3238           if (s->repo != installed)
3239             continue;
3240           if (!s->supplements)
3241             continue;
3242           supp = s->repo->idarraydata + s->supplements;
3243           while ((sup = *supp++) != 0)
3244             if (check_xsupp(solv, &iq, sup) && !check_xsupp(solv, 0, sup))
3245               {
3246 #ifdef CLEANDEPSDEBUG
3247                 printf("xsupp %s from %s\n", pool_dep2str(pool, sup), pool_solvid2str(pool, ip));
3248 #endif
3249                 queue_pushunique(&xsuppq, sup);
3250               }
3251         }
3252       queue_empty(&iq);
3253     }
3254
3255   /* also add visible patterns to userinstalled for openSUSE */
3256   if (1)
3257     {
3258       Dataiterator di;
3259       dataiterator_init(&di, pool, 0, 0, SOLVABLE_ISVISIBLE, 0, 0);
3260       while (dataiterator_step(&di))
3261         {
3262           Id *dp;
3263           if (di.solvid <= 0)
3264             continue;
3265           s = pool->solvables + di.solvid;
3266           if (!s->repo || !s->requires)
3267             continue;
3268           if (s->repo != installed && !pool_installable(pool, s))
3269             continue;
3270           if (strncmp(pool_id2str(pool, s->name), "pattern:", 8) != 0)
3271             continue;
3272           dp = s->repo->idarraydata + s->requires;
3273           for (dp = s->repo->idarraydata + s->requires; *dp; dp++)
3274             FOR_PROVIDES(p, pp, *dp)
3275               if (pool->solvables[p].repo == installed)
3276                 {
3277                   if (strncmp(pool_id2str(pool, pool->solvables[p].name), "pattern", 7) != 0)
3278                     continue;
3279                   MAPSET(&userinstalled, p - installed->start);
3280                 }
3281         }
3282       dataiterator_free(&di);
3283     }
3284   if (1)
3285     {
3286       /* all products and their buddies are userinstalled */
3287       for (p = installed->start; p < installed->end; p++)
3288         {
3289           Solvable *s = pool->solvables + p;
3290           if (s->repo != installed)
3291             continue;
3292           if (!strncmp("product:", pool_id2str(pool, s->name), 8))
3293             {
3294               MAPSET(&userinstalled, p - installed->start);
3295               if (pool->nscallback)
3296                 {
3297                   Id buddy = pool->nscallback(pool, pool->nscallbackdata, NAMESPACE_PRODUCTBUDDY, p);
3298                   if (buddy >= installed->start && buddy < installed->end && pool->solvables[buddy].repo == installed)
3299                     MAPSET(&userinstalled, buddy - installed->start);
3300                 }
3301             }
3302         }
3303     }
3304
3305   /* add all positive elements (e.g. locks) to "userinstalled" */
3306   for (rid = solv->jobrules; rid < solv->jobrules_end; rid++)
3307     {
3308       r = solv->rules + rid;
3309       if (r->d < 0)
3310         continue;
3311       i = solv->ruletojob.elements[rid - solv->jobrules];
3312       if ((job->elements[i] & SOLVER_CLEANDEPS) == SOLVER_CLEANDEPS)
3313         continue;
3314       FOR_RULELITERALS(p, jp, r)
3315         if (p > 0 && pool->solvables[p].repo == installed)
3316           MAPSET(&userinstalled, p - installed->start);
3317     }
3318
3319   /* add all cleandeps candidates to iq */
3320   for (rid = solv->jobrules; rid < solv->jobrules_end; rid++)
3321     {
3322       r = solv->rules + rid;
3323       if (r->d < 0)                             /* disabled? */
3324         continue;
3325       if (r->d == 0 && r->p < 0 && r->w2 == 0)  /* negative assertion (erase job)? */
3326         {
3327           p = -r->p;
3328           if (pool->solvables[p].repo != installed)
3329             continue;
3330           MAPCLR(&userinstalled, p - installed->start);
3331           if (unneeded)
3332             continue;
3333           i = solv->ruletojob.elements[rid - solv->jobrules];
3334           how = job->elements[i];
3335           if ((how & (SOLVER_JOBMASK|SOLVER_CLEANDEPS)) == (SOLVER_ERASE|SOLVER_CLEANDEPS))
3336             queue_push(&iq, p);
3337         }
3338       else if (r->p > 0)                        /* install job */
3339         {
3340           if (unneeded)
3341             continue;
3342           i = solv->ruletojob.elements[rid - solv->jobrules];
3343           if ((job->elements[i] & SOLVER_CLEANDEPS) == SOLVER_CLEANDEPS)
3344             {
3345               /* check if the literals all obsolete some installed package */
3346               Map om;
3347               int iqstart;
3348
3349               /* just one installed literal */
3350               if (r->d == 0 && r->w2 == 0 && pool->solvables[r->p].repo == installed)
3351                 continue;
3352               /* multiversion is bad */
3353               if (solv->multiversion.size && !solv->keepexplicitobsoletes)
3354                 {
3355                   FOR_RULELITERALS(p, jp, r)
3356                     if (MAPTST(&solv->multiversion, p))
3357                       break;
3358                   if (p)
3359                     continue;
3360                 }
3361
3362               om.size = 0;
3363               iqstart = iq.count;
3364               FOR_RULELITERALS(p, jp, r)
3365                 {
3366                   if (p < 0)
3367                     {
3368                       queue_truncate(&iq, iqstart);     /* abort */
3369                       break;
3370                     }
3371                   if (pool->solvables[p].repo == installed)
3372                     {
3373                       if (iq.count == iqstart)
3374                         queue_push(&iq, p);
3375                       else
3376                         {
3377                           for (i = iqstart; i < iq.count; i++)
3378                             if (iq.elements[i] == p)
3379                               break;
3380                           queue_truncate(&iq, iqstart);
3381                           if (i < iq.count)
3382                             queue_push(&iq, p);
3383                         }
3384                     }
3385                   else
3386                     intersect_obsoletes(solv, p, &iq, iqstart, &om);
3387                   if (iq.count == iqstart)
3388                     break;
3389                 }
3390               if (om.size)
3391                 map_free(&om);
3392             }
3393         }
3394     }
3395   queue_init_clone(&iqcopy, &iq);
3396
3397   if (!unneeded)
3398     {
3399       if (solv->cleandeps_updatepkgs)
3400         for (i = 0; i < solv->cleandeps_updatepkgs->count; i++)
3401           queue_push(&iq, solv->cleandeps_updatepkgs->elements[i]);
3402     }
3403
3404   if (unneeded)
3405     queue_empty(&iq);   /* just in case... */
3406
3407   /* clear userinstalled bit for the packages we really want to delete/update */
3408   for (i = 0; i < iq.count; i++)
3409     {
3410       p = iq.elements[i];
3411       if (pool->solvables[p].repo != installed)
3412         continue;
3413       MAPCLR(&userinstalled, p - installed->start);
3414     }
3415
3416   for (p = installed->start; p < installed->end; p++)
3417     {
3418       if (pool->solvables[p].repo != installed)
3419         continue;
3420       MAPSET(&installedm, p);
3421       if (unneeded && !MAPTST(&userinstalled, p - installed->start))
3422         continue;
3423       MAPSET(&im, p);
3424     }
3425   MAPSET(&installedm, SYSTEMSOLVABLE);
3426   MAPSET(&im, SYSTEMSOLVABLE);
3427
3428 #ifdef CLEANDEPSDEBUG
3429   printf("REMOVE PASS\n");
3430 #endif
3431
3432   for (;;)
3433     {
3434       if (!iq.count)
3435         {
3436           if (unneeded)
3437             break;
3438           /* supplements pass */
3439           for (ip = installed->start; ip < installed->end; ip++)
3440             {
3441               if (!MAPTST(&installedm, ip))
3442                 continue;
3443               s = pool->solvables + ip;
3444               if (!s->supplements)
3445                 continue;
3446               if (!MAPTST(&im, ip))
3447                 continue;
3448               if (MAPTST(&userinstalled, ip - installed->start))
3449                 continue;
3450               supp = s->repo->idarraydata + s->supplements;
3451               while ((sup = *supp++) != 0)
3452                 if (dep_possible(solv, sup, &im))
3453                   break;
3454               if (!sup)
3455                 {
3456                   supp = s->repo->idarraydata + s->supplements;
3457                   while ((sup = *supp++) != 0)
3458                     if (dep_possible(solv, sup, &installedm) || (xsuppq.count && queue_contains(&xsuppq, sup)))
3459                       {
3460                         /* no longer supplemented, also erase */
3461                         int iqcount = iq.count;
3462                         /* pin packages, see comment above dep_pkgcheck */
3463                         dep_pkgcheck(solv, sup, &im, &iq);
3464                         for (i = iqcount; i < iq.count; i++)
3465                           {
3466                             Id pqp = iq.elements[i];
3467                             if (pool->solvables[pqp].repo == installed)
3468                               MAPSET(&userinstalled, pqp - installed->start);
3469                           }
3470                         queue_truncate(&iq, iqcount);
3471 #ifdef CLEANDEPSDEBUG
3472                         printf("%s supplemented [%s]\n", pool_solvid2str(pool, ip), pool_dep2str(pool, sup));
3473 #endif
3474                         queue_push(&iq, ip);
3475                       }
3476                 }
3477             }
3478           if (!iq.count)
3479             break;      /* no supplementing package found, we're done */
3480         }
3481       ip = queue_shift(&iq);
3482       s = pool->solvables + ip;
3483       if (!MAPTST(&im, ip))
3484         continue;
3485       if (!MAPTST(&installedm, ip))
3486         continue;
3487       if (s->repo == installed && MAPTST(&userinstalled, ip - installed->start))
3488         continue;
3489       MAPCLR(&im, ip);
3490 #ifdef CLEANDEPSDEBUG
3491       printf("removing %s\n", pool_solvable2str(pool, s));
3492 #endif
3493       if (s->requires)
3494         {
3495           reqp = s->repo->idarraydata + s->requires;
3496           while ((req = *reqp++) != 0)
3497             {
3498               if (req == SOLVABLE_PREREQMARKER)
3499                 continue;
3500 #if 0
3501               /* count number of installed packages that match */
3502               count = 0;
3503               FOR_PROVIDES(p, pp, req)
3504                 if (MAPTST(&installedm, p))
3505                   count++;
3506               if (count > 1)
3507                 continue;
3508 #endif
3509               FOR_PROVIDES(p, pp, req)
3510                 {
3511                   if (p != SYSTEMSOLVABLE && MAPTST(&im, p))
3512                     {
3513 #ifdef CLEANDEPSDEBUG
3514                       printf("%s requires %s\n", pool_solvid2str(pool, ip), pool_solvid2str(pool, p));
3515 #endif
3516                       queue_push(&iq, p);
3517                     }
3518                 }
3519             }
3520         }
3521       if (s->recommends)
3522         {
3523           reqp = s->repo->idarraydata + s->recommends;
3524           while ((req = *reqp++) != 0)
3525             {
3526 #if 0
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 recommends %s\n", pool_solvid2str(pool, ip), pool_solvid2str(pool, p));
3540 #endif
3541                       queue_push(&iq, p);
3542                     }
3543                 }
3544             }
3545         }
3546     }
3547
3548   /* turn userinstalled into remove set for pruning */
3549   map_empty(&userinstalled);
3550   for (rid = solv->jobrules; rid < solv->jobrules_end; rid++)
3551     {
3552       r = solv->rules + rid;
3553       if (r->p >= 0 || r->d != 0 || r->w2 != 0)
3554         continue;       /* disabled or not erase */
3555       p = -r->p;
3556       MAPCLR(&im, p);
3557       if (pool->solvables[p].repo == installed)
3558         MAPSET(&userinstalled, p - installed->start);
3559     }
3560   if (!unneeded && solv->cleandeps_updatepkgs)
3561     {
3562       for (i = 0; i < solv->cleandeps_updatepkgs->count; i++)
3563         {
3564           p = solv->cleandeps_updatepkgs->elements[i];
3565           if (pool->solvables[p].repo == installed)
3566             MAPSET(&userinstalled, p - installed->start);
3567         }
3568     }
3569   MAPSET(&im, SYSTEMSOLVABLE);  /* in case we cleared it above */
3570   for (p = installed->start; p < installed->end; p++)
3571     if (MAPTST(&im, p))
3572       queue_push(&iq, p);
3573   for (rid = solv->jobrules; rid < solv->jobrules_end; rid++)
3574     {
3575       r = solv->rules + rid;
3576       if (r->d < 0)
3577         continue;
3578       FOR_RULELITERALS(p, jp, r)
3579         if (p > 0)
3580           queue_push(&iq, p);
3581     }
3582   /* also put directly addressed packages on the install queue
3583    * so we can mark patterns as installed */
3584   for (i = 0; i < job->count; i += 2)
3585     {
3586       how = job->elements[i];
3587       if ((how & SOLVER_JOBMASK) == SOLVER_USERINSTALLED)
3588         {
3589           what = job->elements[i + 1];
3590           select = how & SOLVER_SELECTMASK;
3591           if (select == SOLVER_SOLVABLE && pool->solvables[what].repo != installed)
3592             queue_push(&iq, what);
3593         }
3594     }
3595
3596 #ifdef CLEANDEPSDEBUG
3597   printf("ADDBACK PASS\n");
3598 #endif
3599   for (;;)
3600     {
3601       if (!iq.count)
3602         {
3603           /* supplements pass */
3604           for (ip = installed->start; ip < installed->end; ip++)
3605             {
3606               if (!MAPTST(&installedm, ip))
3607                 continue;
3608               if (MAPTST(&userinstalled, ip - installed->start))
3609                 continue;
3610               s = pool->solvables + ip;
3611               if (!s->supplements)
3612                 continue;
3613               if (MAPTST(&im, ip))
3614                 continue;
3615               supp = s->repo->idarraydata + s->supplements;
3616               while ((sup = *supp++) != 0)
3617                 if (dep_possible(solv, sup, &im))
3618                   break;
3619               if (sup)
3620                 {
3621 #ifdef CLEANDEPSDEBUG
3622                   printf("%s supplemented\n", pool_solvid2str(pool, ip));
3623 #endif
3624                   MAPSET(&im, ip);
3625                   queue_push(&iq, ip);
3626                 }
3627             }
3628           if (!iq.count)
3629             break;
3630         }
3631       ip = queue_shift(&iq);
3632       s = pool->solvables + ip;
3633 #ifdef CLEANDEPSDEBUG
3634       printf("adding back %s\n", pool_solvable2str(pool, s));
3635 #endif
3636       if (s->requires)
3637         {
3638           reqp = s->repo->idarraydata + s->requires;
3639           while ((req = *reqp++) != 0)
3640             {
3641               FOR_PROVIDES(p, pp, req)
3642                 if (MAPTST(&im, p))
3643                   break;
3644               if (p)
3645                 continue;
3646               FOR_PROVIDES(p, pp, req)
3647                 {
3648                   if (!MAPTST(&im, p) && MAPTST(&installedm, p))
3649                     {
3650                       if (p == ip)
3651                         continue;
3652                       if (MAPTST(&userinstalled, p - installed->start))
3653                         continue;
3654 #ifdef CLEANDEPSDEBUG
3655                       printf("%s requires %s\n", pool_solvid2str(pool, ip), pool_solvid2str(pool, p));
3656 #endif
3657                       MAPSET(&im, p);
3658                       queue_push(&iq, p);
3659                     }
3660                 }
3661             }
3662         }
3663       if (s->recommends)
3664         {
3665           reqp = s->repo->idarraydata + s->recommends;
3666           while ((req = *reqp++) != 0)
3667             {
3668               FOR_PROVIDES(p, pp, req)
3669                 if (MAPTST(&im, p))
3670                   break;
3671               if (p)
3672                 continue;
3673               FOR_PROVIDES(p, pp, req)
3674                 {
3675                   if (!MAPTST(&im, p) && MAPTST(&installedm, p))
3676                     {
3677                       if (p == ip)
3678                         continue;
3679                       if (MAPTST(&userinstalled, p - installed->start))
3680                         continue;
3681 #ifdef CLEANDEPSDEBUG
3682                       printf("%s recommends %s\n", pool_solvid2str(pool, ip), pool_solvid2str(pool, p));
3683 #endif
3684                       MAPSET(&im, p);
3685                       queue_push(&iq, p);
3686                     }
3687                 }
3688             }
3689         }
3690     }
3691
3692   queue_free(&iq);
3693   /* make sure the updatepkgs and mistakes are not in the cleandeps map */
3694   if (solv->cleandeps_updatepkgs)
3695     for (i = 0; i < solv->cleandeps_updatepkgs->count; i++)
3696       MAPSET(&im, solv->cleandeps_updatepkgs->elements[i]);
3697   if (solv->cleandeps_mistakes)
3698     for (i = 0; i < solv->cleandeps_mistakes->count; i++)
3699       MAPSET(&im, solv->cleandeps_mistakes->elements[i]);
3700   /* also remove original iq packages */
3701   for (i = 0; i < iqcopy.count; i++)
3702     MAPSET(&im, iqcopy.elements[i]);
3703   queue_free(&iqcopy);
3704   for (p = installed->start; p < installed->end; p++)
3705     {
3706       if (pool->solvables[p].repo != installed)
3707         continue;
3708       if (!MAPTST(&im, p))
3709         MAPSET(cleandepsmap, p - installed->start);
3710     }
3711   map_free(&im);
3712   map_free(&installedm);
3713   map_free(&userinstalled);
3714   queue_free(&xsuppq);
3715 #ifdef CLEANDEPSDEBUG
3716   printf("=== final cleandeps map:\n");
3717   for (p = installed->start; p < installed->end; p++)
3718     if (MAPTST(cleandepsmap, p - installed->start))
3719       printf("  - %s\n", pool_solvid2str(pool, p));
3720 #endif
3721 }
3722
3723
3724 struct trj_data {
3725   Queue *edges;
3726   Id *low;
3727   Id idx;
3728   Id nstack;
3729   Id firstidx;
3730 };
3731
3732 /* Tarjan's SCC algorithm, slightly modifed */
3733 static void
3734 trj_visit(struct trj_data *trj, Id node)
3735 {
3736   Id *low = trj->low;
3737   Queue *edges = trj->edges;
3738   Id nnode, myidx, stackstart;
3739   int i;
3740
3741   low[node] = myidx = trj->idx++;
3742   low[(stackstart = trj->nstack++)] = node;
3743   for (i = edges->elements[node]; (nnode = edges->elements[i]) != 0; i++)
3744     {
3745       Id l = low[nnode];
3746       if (!l)
3747         {
3748           if (!edges->elements[edges->elements[nnode]])
3749             {
3750               trj->idx++;
3751               low[nnode] = -1;
3752               continue;
3753             }
3754           trj_visit(trj, nnode);
3755           l = low[nnode];
3756         }
3757       if (l < 0)
3758         continue;
3759       if (l < trj->firstidx)
3760         {
3761           int k;
3762           for (k = l; low[low[k]] == l; k++)
3763             low[low[k]] = -1;
3764         }
3765       else if (l < low[node])
3766         low[node] = l;
3767     }
3768   if (low[node] == myidx)
3769     {
3770       if (myidx != trj->firstidx)
3771         myidx = -1;
3772       for (i = stackstart; i < trj->nstack; i++)
3773         low[low[i]] = myidx;
3774       trj->nstack = stackstart;
3775     }
3776 }
3777
3778
3779 void
3780 solver_get_unneeded(Solver *solv, Queue *unneededq, int filtered)
3781 {
3782   Repo *installed = solv->installed;
3783   int i;
3784   Map cleandepsmap;
3785
3786   queue_empty(unneededq);
3787   if (!installed || installed->end == installed->start)
3788     return;
3789
3790   map_init(&cleandepsmap, installed->end - installed->start);
3791   solver_createcleandepsmap(solv, &cleandepsmap, 1);
3792   for (i = installed->start; i < installed->end; i++)
3793     if (MAPTST(&cleandepsmap, i - installed->start))
3794       queue_push(unneededq, i);
3795
3796   if (filtered && unneededq->count > 1)
3797     {
3798       Pool *pool = solv->pool;
3799       Queue edges;
3800       Id *nrequires;
3801       Map installedm;
3802       int j, pass, count = unneededq->count;
3803       Id *low;
3804
3805       map_init(&installedm, pool->nsolvables);
3806       for (i = installed->start; i < installed->end; i++)
3807         if (pool->solvables[i].repo == installed)
3808           MAPSET(&installedm, i);
3809
3810       nrequires = solv_calloc(count, sizeof(Id));
3811       queue_init(&edges);
3812       queue_prealloc(&edges, count * 4 + 10);   /* pre-size */
3813
3814       /*
3815        * Go through the solvables in the nodes queue and create edges for
3816        * all requires/recommends/supplements between the nodes.
3817        * The edges are stored in the edges queue, we add 1 to the node
3818        * index so that nodes in the edges queue are != 0 and we can
3819        * terminate the edge list with 0.
3820        * Thus for node element 5, the edges are stored starting at
3821        * edges.elements[6] and are 0-terminated.
3822        */
3823       /* leave first element zero to make things easier */
3824       /* also add trailing zero */
3825       queue_insertn(&edges, 0, 1 + count + 1, 0);
3826
3827       /* first requires and recommends */
3828       for (i = 0; i < count; i++)
3829         {
3830           Solvable *s = pool->solvables + unneededq->elements[i];
3831           edges.elements[i + 1] = edges.count;
3832           for (pass = 0; pass < 2; pass++)
3833             {
3834               int num = 0;
3835               unsigned int off = pass == 0 ? s->requires : s->recommends;
3836               Id p, pp, *dp;
3837               if (off)
3838                 for (dp = s->repo->idarraydata + off; *dp; dp++)
3839                   FOR_PROVIDES(p, pp, *dp)
3840                     {
3841                       Solvable *sp = pool->solvables + p;
3842                       if (s == sp || sp->repo != installed || !MAPTST(&cleandepsmap, p - installed->start))
3843                         continue;
3844                       for (j = 0; j < count; j++)
3845                         if (p == unneededq->elements[j])
3846                           break;
3847                       if (j == count)
3848                         continue;
3849                       if (num && edges.elements[edges.count - 1] == j + 1)
3850                         continue;
3851                       queue_push(&edges, j + 1);
3852                       num++;
3853                     }
3854                 if (pass == 0)
3855                   nrequires[i] = num;
3856             }
3857           queue_push(&edges, 0);
3858         }
3859 #if 0
3860       printf("requires + recommends\n");
3861       for (i = 0; i < count; i++)
3862         {
3863           int j;
3864           printf("  %s (%d requires):\n", pool_solvid2str(pool, unneededq->elements[i]), nrequires[i]);
3865           for (j = edges.elements[i + 1]; edges.elements[j]; j++)
3866             printf("    - %s\n", pool_solvid2str(pool, unneededq->elements[edges.elements[j] - 1]));
3867         }
3868 #endif
3869
3870       /* then add supplements */
3871       for (i = 0; i < count; i++)
3872         {
3873           Solvable *s = pool->solvables + unneededq->elements[i];
3874           if (s->supplements)
3875             {
3876               Id *dp;
3877               int k;
3878               for (dp = s->repo->idarraydata + s->supplements; *dp; dp++)
3879                 if (dep_possible(solv, *dp, &installedm))
3880                   {
3881                     Queue iq;
3882                     Id iqbuf[16];
3883                     queue_init_buffer(&iq, iqbuf, sizeof(iqbuf)/sizeof(*iqbuf));
3884                     dep_pkgcheck(solv, *dp, 0, &iq);
3885                     for (k = 0; k < iq.count; k++)
3886                       {
3887                         Id p = iq.elements[k];
3888                         Solvable *sp = pool->solvables + p;
3889                         if (p == unneededq->elements[i] || sp->repo != installed || !MAPTST(&cleandepsmap, p - installed->start))
3890                           continue;
3891                         for (j = 0; j < count; j++)
3892                           if (p == unneededq->elements[j])
3893                             break;
3894                         /* now add edge from j + 1 to i + 1 */
3895                         queue_insert(&edges, edges.elements[j + 1] + nrequires[j], i + 1);
3896                         /* addapt following edge pointers */
3897                         for (k = j + 2; k < count + 2; k++)
3898                           edges.elements[k]++;
3899                       }
3900                     queue_free(&iq);
3901                   }
3902             }
3903         }
3904 #if 0
3905       /* print result */
3906       printf("+ supplements\n");
3907       for (i = 0; i < count; i++)
3908         {
3909           int j;
3910           printf("  %s (%d requires):\n", pool_solvid2str(pool, unneededq->elements[i]), nrequires[i]);
3911           for (j = edges.elements[i + 1]; edges.elements[j]; j++)
3912             printf("    - %s\n", pool_solvid2str(pool, unneededq->elements[edges.elements[j] - 1]));
3913     }
3914 #endif
3915       map_free(&installedm);
3916
3917       /* now run SCC algo two times, first with requires+recommends+supplements,
3918        * then again without the requires. We run it the second time to get rid
3919        * of packages that got dragged in via recommends/supplements */
3920       /*
3921        * low will contain the result of the SCC search.
3922        * it must be of at least size 2 * (count + 1) and
3923        * must be zero initialized.
3924        * The layout is:
3925        *    0  low low ... low stack stack ...stack 0
3926        *            count              count
3927        */
3928       low = solv_calloc(count + 1, 2 * sizeof(Id));
3929       for (pass = 0; pass < 2; pass++)
3930         {
3931           struct trj_data trj;
3932           if (pass)
3933             {
3934               memset(low, 0, (count + 1) * (2 * sizeof(Id)));
3935               for (i = 0; i < count; i++)
3936                 {
3937                   edges.elements[i + 1] += nrequires[i];
3938                   if (!unneededq->elements[i])
3939                     low[i + 1] = -1;    /* ignore this node */
3940                 }
3941             }
3942           trj.edges = &edges;
3943           trj.low = low;
3944           trj.idx = count + 1;  /* stack starts here */
3945           for (i = 1; i <= count; i++)
3946             {
3947               if (low[i])
3948                 continue;
3949               if (edges.elements[edges.elements[i]])
3950                 {
3951                   trj.firstidx = trj.nstack = trj.idx;
3952                   trj_visit(&trj, i);
3953                 }
3954               else
3955                 {
3956                   Id myidx = trj.idx++;
3957                   low[i] = myidx;
3958                   low[myidx] = i;
3959                 }
3960             }
3961           /* prune packages */
3962           for (i = 0; i < count; i++)
3963             if (low[i + 1] <= 0)
3964               unneededq->elements[i] = 0;
3965         }
3966       solv_free(low);
3967       solv_free(nrequires);
3968       queue_free(&edges);
3969
3970       /* finally remove all pruned entries from unneededq */
3971       for (i = j = 0; i < count; i++)
3972         if (unneededq->elements[i])
3973           unneededq->elements[j++] = unneededq->elements[i];
3974       queue_truncate(unneededq, j);
3975     }
3976   map_free(&cleandepsmap);
3977 }
3978
3979 /* EOF */