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