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