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