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