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