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