src/rules.c

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