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