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 && qs.count && 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                   if (!r->p || (r->p == p && !r->d && !r->w2))
1868                     {
1869                       /* this is an orphan */
1870                       MAPSET(&solv->dupmap, p);         /* for best rules processing */
1871                       continue;
1872                     }
1873                   solver_addrule(solv, -p, 0, 0);       /* no match, sorry */
1874                 }
1875             }
1876           else if (!MAPTST(&solv->dupmap, p))
1877             solver_addrule(solv, -p, 0, 0);
1878         }
1879     }
1880   solv->duprules_end = solv->nrules;
1881 }
1882
1883
1884 static inline void
1885 disableduprule(Solver *solv, Id name)
1886 {
1887   Pool *pool = solv->pool;
1888   Rule *r;
1889   int i;
1890   for (i = solv->duprules, r = solv->rules + i; i < solv->duprules_end; i++, r++)
1891     {
1892       if (r->p < 0 && r->d >= 0 && pool->solvables[-r->p].name == name)
1893         solver_disablerule(solv, r);
1894     }
1895 }
1896
1897 static inline void
1898 reenableduprule(Solver *solv, Id name)
1899 {
1900   Pool *pool = solv->pool;
1901   Rule *r;
1902   int i;
1903   for (i = solv->duprules, r = solv->rules + i; i < solv->duprules_end; i++, r++)
1904     {
1905       if (r->p < 0 && r->d < 0 && pool->solvables[-r->p].name == name)
1906         {
1907           solver_enablerule(solv, r);
1908           IF_POOLDEBUG (SOLV_DEBUG_SOLUTIONS)
1909             {
1910               POOL_DEBUG(SOLV_DEBUG_SOLUTIONS, "@@@ re-enabling ");
1911               solver_printruleclass(solv, SOLV_DEBUG_SOLUTIONS, r);
1912             }
1913         }
1914     }
1915 }
1916
1917
1918 /***********************************************************************
1919  ***
1920  ***  Policy rule disabling/reenabling
1921  ***
1922  ***  Disable all policy rules that conflict with our jobs. If a job
1923  ***  gets disabled later on, reenable the involved policy rules again.
1924  ***
1925  ***/
1926
1927 #define DISABLE_UPDATE  1
1928 #define DISABLE_INFARCH 2
1929 #define DISABLE_DUP     3
1930
1931 /*
1932  * add all installed packages that package p obsoletes to Queue q.
1933  * Package p is not installed. Also, we know that if
1934  * solv->keepexplicitobsoletes is not set, p is not in the multiversion map.
1935  * Entries may get added multiple times.
1936  */
1937 static void
1938 add_obsoletes(Solver *solv, Id p, Queue *q)
1939 {
1940   Pool *pool = solv->pool;
1941   Repo *installed = solv->installed;
1942   Id p2, pp2;
1943   Solvable *s = pool->solvables + p;
1944   Id obs, *obsp;
1945   Id lastp2 = 0;
1946
1947   if (!solv->keepexplicitobsoletes || !(solv->multiversion.size && MAPTST(&solv->multiversion, p)))
1948     {
1949       FOR_PROVIDES(p2, pp2, s->name)
1950         {
1951           Solvable *ps = pool->solvables + p2;
1952           if (ps->repo != installed)
1953             continue;
1954           if (!pool->implicitobsoleteusesprovides && ps->name != s->name)
1955             continue;
1956           if (pool->implicitobsoleteusescolors && !pool_colormatch(pool, s, ps))
1957             continue;
1958           queue_push(q, p2);
1959           lastp2 = p2;
1960         }
1961     }
1962   if (!s->obsoletes)
1963     return;
1964   obsp = s->repo->idarraydata + s->obsoletes;
1965   while ((obs = *obsp++) != 0)
1966     FOR_PROVIDES(p2, pp2, obs)
1967       {
1968         Solvable *ps = pool->solvables + p2;
1969         if (ps->repo != installed)
1970           continue;
1971         if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
1972           continue;
1973         if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
1974           continue;
1975         if (p2 == lastp2)
1976           continue;
1977         queue_push(q, p2);
1978         lastp2 = p2;
1979       }
1980 }
1981
1982 /*
1983  * Call add_obsoletes and intersect the result with the
1984  * elements in Queue q starting at qstart.
1985  * Assumes that it's the first call if qstart == q->count.
1986  * May use auxillary map m for the intersection process, all
1987  * elements of q starting at qstart must have their bit cleared.
1988  * (This is also true after the function returns.)
1989  */
1990 static void
1991 intersect_obsoletes(Solver *solv, Id p, Queue *q, int qstart, Map *m)
1992 {
1993   int i, j;
1994   int qcount = q->count;
1995
1996   add_obsoletes(solv, p, q);
1997   if (qcount == qstart)
1998     return;     /* first call */
1999   if (qcount == q->count)
2000     j = qstart;
2001   else if (qcount == qstart + 1)
2002     {
2003       /* easy if there's just one element */
2004       j = qstart;
2005       for (i = qcount; i < q->count; i++)
2006         if (q->elements[i] == q->elements[qstart])
2007           {
2008             j++;        /* keep the element */
2009             break;
2010           }
2011     }
2012   else if (!m->size && q->count - qstart <= 8)
2013     {
2014       /* faster than a map most of the time */
2015       int k;
2016       for (i = j = qstart; i < qcount; i++)
2017         {
2018           Id ip = q->elements[i];
2019           for (k = qcount; k < q->count; k++)
2020             if (q->elements[k] == ip)
2021               {
2022                 q->elements[j++] = ip;
2023                 break;
2024               }
2025         }
2026     }
2027   else
2028     {
2029       /* for the really pathologic cases we use the map */
2030       Repo *installed = solv->installed;
2031       if (!m->size)
2032         map_init(m, installed->end - installed->start);
2033       for (i = qcount; i < q->count; i++)
2034         MAPSET(m, q->elements[i] - installed->start);
2035       for (i = j = qstart; i < qcount; i++)
2036         if (MAPTST(m, q->elements[i] - installed->start))
2037           {
2038             MAPCLR(m, q->elements[i] - installed->start);
2039             q->elements[j++] = q->elements[i];
2040           }
2041     }
2042   queue_truncate(q, j);
2043 }
2044
2045 static void
2046 jobtodisablelist(Solver *solv, Id how, Id what, Queue *q)
2047 {
2048   Pool *pool = solv->pool;
2049   Id select, p, pp;
2050   Repo *installed;
2051   Solvable *s;
2052   int i, j, set, qstart;
2053   Map omap;
2054
2055   installed = solv->installed;
2056   select = how & SOLVER_SELECTMASK;
2057   switch (how & SOLVER_JOBMASK)
2058     {
2059     case SOLVER_INSTALL:
2060       set = how & SOLVER_SETMASK;
2061       if (!(set & SOLVER_NOAUTOSET))
2062         {
2063           /* automatically add set bits by analysing the job */
2064           if (select == SOLVER_SOLVABLE_NAME)
2065             set |= SOLVER_SETNAME;
2066           if (select == SOLVER_SOLVABLE)
2067             set |= SOLVER_SETNAME | SOLVER_SETARCH | SOLVER_SETVENDOR | SOLVER_SETREPO | SOLVER_SETEVR;
2068           else if ((select == SOLVER_SOLVABLE_NAME || select == SOLVER_SOLVABLE_PROVIDES) && ISRELDEP(what))
2069             {
2070               Reldep *rd = GETRELDEP(pool, what);
2071               if (rd->flags == REL_EQ && select == SOLVER_SOLVABLE_NAME)
2072                 {
2073                   if (pool->disttype != DISTTYPE_DEB)
2074                     {
2075                       const char *rel = strrchr(pool_id2str(pool, rd->evr), '-');
2076                       set |= rel ? SOLVER_SETEVR : SOLVER_SETEV;
2077                     }
2078                   else
2079                     set |= SOLVER_SETEVR;
2080                 }
2081               if (rd->flags <= 7 && ISRELDEP(rd->name))
2082                 rd = GETRELDEP(pool, rd->name);
2083               if (rd->flags == REL_ARCH)
2084                 set |= SOLVER_SETARCH;
2085             }
2086         }
2087       else
2088         set &= ~SOLVER_NOAUTOSET;
2089       if (!set)
2090         return;
2091       if ((set & SOLVER_SETARCH) != 0 && solv->infarchrules != solv->infarchrules_end)
2092         {
2093           if (select == SOLVER_SOLVABLE)
2094             queue_push2(q, DISABLE_INFARCH, pool->solvables[what].name);
2095           else
2096             {
2097               int qcnt = q->count;
2098               /* does not work for SOLVER_SOLVABLE_ALL and SOLVER_SOLVABLE_REPO, but
2099                  they are not useful for SOLVER_INSTALL jobs anyway */
2100               FOR_JOB_SELECT(p, pp, select, what)
2101                 {
2102                   s = pool->solvables + p;
2103                   /* unify names */
2104                   for (i = qcnt; i < q->count; i += 2)
2105                     if (q->elements[i + 1] == s->name)
2106                       break;
2107                   if (i < q->count)
2108                     continue;
2109                   queue_push2(q, DISABLE_INFARCH, s->name);
2110                 }
2111             }
2112         }
2113       if ((set & SOLVER_SETREPO) != 0 && solv->duprules != solv->duprules_end)
2114         {
2115           if (select == SOLVER_SOLVABLE)
2116             queue_push2(q, DISABLE_DUP, pool->solvables[what].name);
2117           else
2118             {
2119               int qcnt = q->count;
2120               FOR_JOB_SELECT(p, pp, select, what)
2121                 {
2122                   s = pool->solvables + p;
2123                   /* unify names */
2124                   for (i = qcnt; i < q->count; i += 2)
2125                     if (q->elements[i + 1] == s->name)
2126                       break;
2127                   if (i < q->count)
2128                     continue;
2129                   queue_push2(q, DISABLE_DUP, s->name);
2130                 }
2131             }
2132         }
2133       if (!installed || installed->end == installed->start)
2134         return;
2135       /* now the hard part: disable some update rules */
2136
2137       /* first check if we have multiversion or installed packages in the job */
2138       i = j = 0;
2139       FOR_JOB_SELECT(p, pp, select, what)
2140         {
2141           if (pool->solvables[p].repo == installed)
2142             j = p;
2143           else if (solv->multiversion.size && MAPTST(&solv->multiversion, p) && !solv->keepexplicitobsoletes)
2144             return;
2145           i++;
2146         }
2147       if (j)    /* have installed packages */
2148         {
2149           /* this is for dupmap_all jobs, it can go away if we create
2150            * duprules for them */
2151           if (i == 1 && (set & SOLVER_SETREPO) != 0)
2152             queue_push2(q, DISABLE_UPDATE, j);
2153           return;
2154         }
2155
2156       omap.size = 0;
2157       qstart = q->count;
2158       FOR_JOB_SELECT(p, pp, select, what)
2159         {
2160           intersect_obsoletes(solv, p, q, qstart, &omap);
2161           if (q->count == qstart)
2162             break;
2163         }
2164       if (omap.size)
2165         map_free(&omap);
2166
2167       if (qstart == q->count)
2168         return;         /* nothing to prune */
2169
2170       /* convert result to (DISABLE_UPDATE, p) pairs */
2171       i = q->count;
2172       for (j = qstart; j < i; j++)
2173         queue_push(q, q->elements[j]);
2174       for (j = qstart; j < q->count; j += 2)
2175         {
2176           q->elements[j] = DISABLE_UPDATE;
2177           q->elements[j + 1] = q->elements[i++];
2178         }
2179
2180       /* now that we know which installed packages are obsoleted check each of them */
2181       if ((set & (SOLVER_SETEVR | SOLVER_SETARCH | SOLVER_SETVENDOR)) == (SOLVER_SETEVR | SOLVER_SETARCH | SOLVER_SETVENDOR))
2182         return;         /* all is set, nothing to do */
2183
2184       for (i = j = qstart; i < q->count; i += 2)
2185         {
2186           Solvable *is = pool->solvables + q->elements[i + 1];
2187           FOR_JOB_SELECT(p, pp, select, what)
2188             {
2189               int illegal = 0;
2190               s = pool->solvables + p;
2191               if ((set & SOLVER_SETEVR) != 0)
2192                 illegal |= POLICY_ILLEGAL_DOWNGRADE;    /* ignore */
2193               if ((set & SOLVER_SETNAME) != 0)
2194                 illegal |= POLICY_ILLEGAL_NAMECHANGE;   /* ignore */
2195               if ((set & SOLVER_SETARCH) != 0)
2196                 illegal |= POLICY_ILLEGAL_ARCHCHANGE;   /* ignore */
2197               if ((set & SOLVER_SETVENDOR) != 0)
2198                 illegal |= POLICY_ILLEGAL_VENDORCHANGE; /* ignore */
2199               illegal = policy_is_illegal(solv, is, s, illegal);
2200               if (illegal && illegal == POLICY_ILLEGAL_DOWNGRADE && (set & SOLVER_SETEV) != 0)
2201                 {
2202                   /* it's ok if the EV is different */
2203                   if (pool_evrcmp(pool, is->evr, s->evr, EVRCMP_COMPARE_EVONLY) != 0)
2204                     illegal = 0;
2205                 }
2206               if (illegal)
2207                 break;
2208             }
2209           if (!p)
2210             {
2211               /* no package conflicts with the update rule */
2212               /* thus keep the DISABLE_UPDATE */
2213               q->elements[j + 1] = q->elements[i + 1];
2214               j += 2;
2215             }
2216         }
2217       queue_truncate(q, j);
2218       return;
2219
2220     case SOLVER_ERASE:
2221       if (!installed)
2222         break;
2223       if (select == SOLVER_SOLVABLE_ALL || (select == SOLVER_SOLVABLE_REPO && what == installed->repoid))
2224         FOR_REPO_SOLVABLES(installed, p, s)
2225           queue_push2(q, DISABLE_UPDATE, p);
2226       FOR_JOB_SELECT(p, pp, select, what)
2227         if (pool->solvables[p].repo == installed)
2228           {
2229             queue_push2(q, DISABLE_UPDATE, p);
2230 #ifdef ENABLE_LINKED_PKGS
2231             if (solv->instbuddy && solv->instbuddy[p - installed->start] > 1)
2232               queue_push2(q, DISABLE_UPDATE, solv->instbuddy[p - installed->start]);
2233 #endif
2234           }
2235       return;
2236     default:
2237       return;
2238     }
2239 }
2240
2241 /* disable all policy rules that are in conflict with our job list */
2242 void
2243 solver_disablepolicyrules(Solver *solv)
2244 {
2245   Queue *job = &solv->job;
2246   int i, j;
2247   Queue allq;
2248   Rule *r;
2249   Id lastjob = -1;
2250   Id allqbuf[128];
2251
2252   queue_init_buffer(&allq, allqbuf, sizeof(allqbuf)/sizeof(*allqbuf));
2253
2254   for (i = solv->jobrules; i < solv->jobrules_end; i++)
2255     {
2256       r = solv->rules + i;
2257       if (r->d < 0)     /* disabled? */
2258         continue;
2259       j = solv->ruletojob.elements[i - solv->jobrules];
2260       if (j == lastjob)
2261         continue;
2262       lastjob = j;
2263       jobtodisablelist(solv, job->elements[j], job->elements[j + 1], &allq);
2264     }
2265   if (solv->cleandepsmap.size)
2266     {
2267       solver_createcleandepsmap(solv, &solv->cleandepsmap, 0);
2268       for (i = solv->installed->start; i < solv->installed->end; i++)
2269         if (MAPTST(&solv->cleandepsmap, i - solv->installed->start))
2270           queue_push2(&allq, DISABLE_UPDATE, i);
2271     }
2272   MAPZERO(&solv->noupdate);
2273   for (i = 0; i < allq.count; i += 2)
2274     {
2275       Id type = allq.elements[i], arg = allq.elements[i + 1];
2276       switch(type)
2277         {
2278         case DISABLE_UPDATE:
2279           disableupdaterule(solv, arg);
2280           break;
2281         case DISABLE_INFARCH:
2282           disableinfarchrule(solv, arg);
2283           break;
2284         case DISABLE_DUP:
2285           disableduprule(solv, arg);
2286           break;
2287         default:
2288           break;
2289         }
2290     }
2291   queue_free(&allq);
2292 }
2293
2294 /* we just disabled job #jobidx, now reenable all policy rules that were
2295  * disabled because of this job */
2296 void
2297 solver_reenablepolicyrules(Solver *solv, int jobidx)
2298 {
2299   Queue *job = &solv->job;
2300   int i, j, k, ai;
2301   Queue q, allq;
2302   Rule *r;
2303   Id lastjob = -1;
2304   Id qbuf[32], allqbuf[32];
2305
2306   queue_init_buffer(&q, qbuf, sizeof(qbuf)/sizeof(*qbuf));
2307   jobtodisablelist(solv, job->elements[jobidx - 1], job->elements[jobidx], &q);
2308   if (!q.count)
2309     {
2310       queue_free(&q);
2311       return;
2312     }
2313   /* now remove everything from q that is disabled by other jobs */
2314
2315   /* first remove cleandeps packages, they count as DISABLE_UPDATE */
2316   if (solv->cleandepsmap.size)
2317     {
2318       solver_createcleandepsmap(solv, &solv->cleandepsmap, 0);
2319       for (j = k = 0; j < q.count; j += 2)
2320         {
2321           if (q.elements[j] == DISABLE_UPDATE)
2322             {
2323               Id p = q.elements[j + 1];
2324               if (p >= solv->installed->start && p < solv->installed->end && MAPTST(&solv->cleandepsmap, p - solv->installed->start))
2325                 continue;       /* remove element from q */
2326             }
2327           q.elements[k++] = q.elements[j];
2328           q.elements[k++] = q.elements[j + 1];
2329         }
2330       q.count = k;
2331       if (!q.count)
2332         {
2333           queue_free(&q);
2334           return;
2335         }
2336     }
2337
2338   /* now go through the disable list of all other jobs */
2339   queue_init_buffer(&allq, allqbuf, sizeof(allqbuf)/sizeof(*allqbuf));
2340   for (i = solv->jobrules; i < solv->jobrules_end; i++)
2341     {
2342       r = solv->rules + i;
2343       if (r->d < 0)     /* disabled? */
2344         continue;
2345       j = solv->ruletojob.elements[i - solv->jobrules];
2346       if (j == lastjob)
2347         continue;
2348       lastjob = j;
2349       jobtodisablelist(solv, job->elements[j], job->elements[j + 1], &allq);
2350       if (!allq.count)
2351         continue;
2352       /* remove all elements in allq from q */
2353       for (j = k = 0; j < q.count; j += 2)
2354         {
2355           Id type = q.elements[j], arg = q.elements[j + 1];
2356           for (ai = 0; ai < allq.count; ai += 2)
2357             if (allq.elements[ai] == type && allq.elements[ai + 1] == arg)
2358               break;
2359           if (ai < allq.count)
2360             continue;   /* found it in allq, remove element from q */
2361           q.elements[k++] = q.elements[j];
2362           q.elements[k++] = q.elements[j + 1];
2363         }
2364       q.count = k;
2365       if (!q.count)
2366         {
2367           queue_free(&q);
2368           queue_free(&allq);
2369           return;
2370         }
2371       queue_empty(&allq);
2372     }
2373   queue_free(&allq);
2374
2375   /* now re-enable anything that's left in q */
2376   for (j = 0; j < q.count; j += 2)
2377     {
2378       Id type = q.elements[j], arg = q.elements[j + 1];
2379       switch(type)
2380         {
2381         case DISABLE_UPDATE:
2382           reenableupdaterule(solv, arg);
2383           break;
2384         case DISABLE_INFARCH:
2385           reenableinfarchrule(solv, arg);
2386           break;
2387         case DISABLE_DUP:
2388           reenableduprule(solv, arg);
2389           break;
2390         }
2391     }
2392   queue_free(&q);
2393 }
2394
2395 /* we just removed a package from the cleandeps map, now reenable all policy rules that were
2396  * disabled because of this */
2397 void
2398 solver_reenablepolicyrules_cleandeps(Solver *solv, Id pkg)
2399 {
2400   Queue *job = &solv->job;
2401   int i, j;
2402   Queue allq;
2403   Rule *r;
2404   Id lastjob = -1;
2405   Id allqbuf[128];
2406
2407   queue_init_buffer(&allq, allqbuf, sizeof(allqbuf)/sizeof(*allqbuf));
2408   for (i = solv->jobrules; i < solv->jobrules_end; i++)
2409     {
2410       r = solv->rules + i;
2411       if (r->d < 0)     /* disabled? */
2412         continue;
2413       j = solv->ruletojob.elements[i - solv->jobrules];
2414       if (j == lastjob)
2415         continue;
2416       lastjob = j;
2417       jobtodisablelist(solv, job->elements[j], job->elements[j + 1], &allq);
2418     }
2419   for (i = 0; i < allq.count; i += 2)
2420     if (allq.elements[i] == DISABLE_UPDATE && allq.elements[i + 1] == pkg)
2421       break;
2422   if (i == allq.count)
2423     reenableupdaterule(solv, pkg);
2424   queue_free(&allq);
2425 }
2426
2427
2428 /***********************************************************************
2429  ***
2430  ***  Rule info part, tell the user what the rule is about.
2431  ***
2432  ***/
2433
2434 static void
2435 addpkgruleinfo(Solver *solv, Id p, Id p2, Id d, int type, Id dep)
2436 {
2437   Pool *pool = solv->pool;
2438   Rule *r;
2439
2440   if (d)
2441     {
2442       assert(!p2 && d > 0);
2443       if (!pool->whatprovidesdata[d])
2444         d = 0;
2445       else if (!pool->whatprovidesdata[d + 1])
2446         {
2447           p2 = pool->whatprovidesdata[d];
2448           d = 0;
2449         }
2450     }
2451
2452   /* check if this creates the rule we're searching for */
2453   r = solv->rules + solv->ruleinfoq->elements[0];
2454   if (d)
2455     {
2456       /* three or more literals */
2457       Id od = r->d < 0 ? -r->d - 1 : r->d;
2458       if (p != r->p && !od)
2459         return;
2460       if (d != od)
2461         {
2462           Id *dp = pool->whatprovidesdata + d;
2463           Id *odp = pool->whatprovidesdata + od;
2464           while (*dp)
2465             if (*dp++ != *odp++)
2466               return;
2467           if (*odp)
2468             return;
2469         }
2470       if (p < 0 && pool->whatprovidesdata[d] < 0 && type == SOLVER_RULE_PKG_CONFLICTS)
2471         p2 = pool->whatprovidesdata[d];
2472     }
2473   else
2474     {
2475       /* one or two literals */
2476       Id op = p, op2 = p2;
2477       if (op2 && op > op2)      /* normalize */
2478         {
2479           Id o = op;
2480           op = op2;
2481           op2 = o;
2482         }
2483       if (r->p != op || r->w2 != op2 || (r->d && r->d != -1))
2484         return;
2485       if (type == SOLVER_RULE_PKG_CONFLICTS && !p2)
2486         p2 = -SYSTEMSOLVABLE;
2487       if (type == SOLVER_RULE_PKG_SAME_NAME)
2488         {
2489           p = op;       /* we normalize same name order */
2490           p2 = op2;
2491         }
2492     }
2493   /* yep, rule matches. record info */
2494   queue_push(solv->ruleinfoq, type);
2495   queue_push(solv->ruleinfoq, p < 0 ? -p : 0);
2496   queue_push(solv->ruleinfoq, p2 < 0 ? -p2 : 0);
2497   queue_push(solv->ruleinfoq, dep);
2498 }
2499
2500 static int
2501 solver_allruleinfos_cmp(const void *ap, const void *bp, void *dp)
2502 {
2503   const Id *a = ap, *b = bp;
2504   int r;
2505
2506   r = a[0] - b[0];
2507   if (r)
2508     return r;
2509   r = a[1] - b[1];
2510   if (r)
2511     return r;
2512   r = a[2] - b[2];
2513   if (r)
2514     return r;
2515   r = a[3] - b[3];
2516   if (r)
2517     return r;
2518   return 0;
2519 }
2520
2521 static void
2522 getpkgruleinfos(Solver *solv, Rule *r, Queue *rq)
2523 {
2524   Pool *pool = solv->pool;
2525   Id l, pp;
2526   if (r->p >= 0)
2527     return;
2528   queue_push(rq, r - solv->rules);      /* push the rule we're interested in */
2529   solv->ruleinfoq = rq;
2530   FOR_RULELITERALS(l, pp, r)
2531     {
2532       if (l >= 0)
2533         break;
2534       solver_addpkgrulesforsolvable(solv, pool->solvables - l, 0);
2535     }
2536 #ifdef ENABLE_LINKED_PKGS
2537   FOR_RULELITERALS(l, pp, r)
2538     {
2539       if (l < 0)
2540         {
2541           if (l == r->p)
2542             continue;
2543           break;
2544         }
2545       if (!strchr(pool_id2str(pool, pool->solvables[l].name), ':') || !has_package_link(pool, pool->solvables + l))
2546         break;
2547       add_package_link(solv, pool->solvables + l, 0, 0);
2548     }
2549 #endif
2550   solv->ruleinfoq = 0;
2551   queue_shift(rq);
2552 }
2553
2554 int
2555 solver_allruleinfos(Solver *solv, Id rid, Queue *rq)
2556 {
2557   Rule *r = solv->rules + rid;
2558   int i, j;
2559
2560   queue_empty(rq);
2561   if (rid <= 0 || rid >= solv->pkgrules_end)
2562     {
2563       Id type, from, to, dep;
2564       type = solver_ruleinfo(solv, rid, &from, &to, &dep);
2565       queue_push(rq, type);
2566       queue_push(rq, from);
2567       queue_push(rq, to);
2568       queue_push(rq, dep);
2569       return 1;
2570     }
2571   getpkgruleinfos(solv, r, rq);
2572   /* now sort & unify em */
2573   if (!rq->count)
2574     return 0;
2575   solv_sort(rq->elements, rq->count / 4, 4 * sizeof(Id), solver_allruleinfos_cmp, 0);
2576   /* throw out identical entries */
2577   for (i = j = 0; i < rq->count; i += 4)
2578     {
2579       if (j)
2580         {
2581           if (rq->elements[i] == rq->elements[j - 4] &&
2582               rq->elements[i + 1] == rq->elements[j - 3] &&
2583               rq->elements[i + 2] == rq->elements[j - 2] &&
2584               rq->elements[i + 3] == rq->elements[j - 1])
2585             continue;
2586         }
2587       rq->elements[j++] = rq->elements[i];
2588       rq->elements[j++] = rq->elements[i + 1];
2589       rq->elements[j++] = rq->elements[i + 2];
2590       rq->elements[j++] = rq->elements[i + 3];
2591     }
2592   rq->count = j;
2593   return j / 4;
2594 }
2595
2596 SolverRuleinfo
2597 solver_ruleinfo(Solver *solv, Id rid, Id *fromp, Id *top, Id *depp)
2598 {
2599   Pool *pool = solv->pool;
2600   Rule *r = solv->rules + rid;
2601   SolverRuleinfo type = SOLVER_RULE_UNKNOWN;
2602
2603   if (fromp)
2604     *fromp = 0;
2605   if (top)
2606     *top = 0;
2607   if (depp)
2608     *depp = 0;
2609   if (rid > 0 && rid < solv->pkgrules_end)
2610     {
2611       Queue rq;
2612       int i;
2613
2614       if (r->p >= 0)
2615         return SOLVER_RULE_PKG;
2616       if (fromp)
2617         *fromp = -r->p;
2618       queue_init(&rq);
2619       getpkgruleinfos(solv, r, &rq);
2620       type = SOLVER_RULE_PKG;
2621       for (i = 0; i < rq.count; i += 4)
2622         {
2623           Id qt, qo, qp, qd;
2624           qt = rq.elements[i];
2625           qp = rq.elements[i + 1];
2626           qo = rq.elements[i + 2];
2627           qd = rq.elements[i + 3];
2628           if (type == SOLVER_RULE_PKG || type > qt)
2629             {
2630               type = qt;
2631               if (fromp)
2632                 *fromp = qp;
2633               if (top)
2634                 *top = qo;
2635               if (depp)
2636                 *depp = qd;
2637             }
2638         }
2639       queue_free(&rq);
2640       return type;
2641     }
2642   if (rid >= solv->jobrules && rid < solv->jobrules_end)
2643     {
2644       Id jidx = solv->ruletojob.elements[rid - solv->jobrules];
2645       if (fromp)
2646         *fromp = jidx;
2647       if (top)
2648         *top = solv->job.elements[jidx];
2649       if (depp)
2650         *depp = solv->job.elements[jidx + 1];
2651       if ((r->d == 0 || r->d == -1) && r->w2 == 0 && r->p == -SYSTEMSOLVABLE)
2652         {
2653           Id how = solv->job.elements[jidx];
2654           if ((how & (SOLVER_JOBMASK|SOLVER_SELECTMASK)) == (SOLVER_INSTALL|SOLVER_SOLVABLE_NAME))
2655             return SOLVER_RULE_JOB_UNKNOWN_PACKAGE;
2656           if ((how & (SOLVER_JOBMASK|SOLVER_SELECTMASK)) == (SOLVER_INSTALL|SOLVER_SOLVABLE_PROVIDES))
2657             return SOLVER_RULE_JOB_NOTHING_PROVIDES_DEP;
2658           if ((how & (SOLVER_JOBMASK|SOLVER_SELECTMASK)) == (SOLVER_ERASE|SOLVER_SOLVABLE_NAME))
2659             return SOLVER_RULE_JOB_PROVIDED_BY_SYSTEM;
2660           if ((how & (SOLVER_JOBMASK|SOLVER_SELECTMASK)) == (SOLVER_ERASE|SOLVER_SOLVABLE_PROVIDES))
2661             return SOLVER_RULE_JOB_PROVIDED_BY_SYSTEM;
2662           return SOLVER_RULE_JOB_UNSUPPORTED;
2663         }
2664       return SOLVER_RULE_JOB;
2665     }
2666   if (rid >= solv->updaterules && rid < solv->updaterules_end)
2667     {
2668       if (fromp)
2669         *fromp = solv->installed->start + (rid - solv->updaterules);
2670       return SOLVER_RULE_UPDATE;
2671     }
2672   if (rid >= solv->featurerules && rid < solv->featurerules_end)
2673     {
2674       if (fromp)
2675         *fromp = solv->installed->start + (rid - solv->featurerules);
2676       return SOLVER_RULE_FEATURE;
2677     }
2678   if (rid >= solv->duprules && rid < solv->duprules_end)
2679     {
2680       if (fromp)
2681         *fromp = -r->p;
2682       if (depp)
2683         *depp = pool->solvables[-r->p].name;
2684       return SOLVER_RULE_DISTUPGRADE;
2685     }
2686   if (rid >= solv->infarchrules && rid < solv->infarchrules_end)
2687     {
2688       if (fromp)
2689         *fromp = -r->p;
2690       if (depp)
2691         *depp = pool->solvables[-r->p].name;
2692       return SOLVER_RULE_INFARCH;
2693     }
2694   if (rid >= solv->bestrules && rid < solv->bestrules_end)
2695     {
2696       if (fromp && solv->bestrules_pkg[rid - solv->bestrules] > 0)
2697         *fromp = solv->bestrules_pkg[rid - solv->bestrules];
2698       return SOLVER_RULE_BEST;
2699     }
2700   if (rid >= solv->yumobsrules && rid < solv->yumobsrules_end)
2701     {
2702       if (fromp)
2703         *fromp = -r->p;
2704       if (top)
2705         {
2706           /* first solvable is enough, we just need it for the name */
2707           if (!r->d || r->d == -1)
2708             *top = r->w2;
2709           else
2710             *top = pool->whatprovidesdata[r->d < 0 ? -r->d : r->d];
2711         }
2712       if (depp)
2713         *depp = solv->yumobsrules_info[rid - solv->yumobsrules];
2714       return SOLVER_RULE_YUMOBS;
2715     }
2716   if (rid >= solv->choicerules && rid < solv->choicerules_end)
2717     {
2718       return SOLVER_RULE_CHOICE;
2719     }
2720   if (rid >= solv->learntrules)
2721     {
2722       return SOLVER_RULE_LEARNT;
2723     }
2724   return SOLVER_RULE_UNKNOWN;
2725 }
2726
2727 SolverRuleinfo
2728 solver_ruleclass(Solver *solv, Id rid)
2729 {
2730   if (rid <= 0)
2731     return SOLVER_RULE_UNKNOWN;
2732   if (rid > 0 && rid < solv->pkgrules_end)
2733     return SOLVER_RULE_PKG;
2734   if (rid >= solv->jobrules && rid < solv->jobrules_end)
2735     return SOLVER_RULE_JOB;
2736   if (rid >= solv->updaterules && rid < solv->updaterules_end)
2737     return SOLVER_RULE_UPDATE;
2738   if (rid >= solv->featurerules && rid < solv->featurerules_end)
2739     return SOLVER_RULE_FEATURE;
2740   if (rid >= solv->duprules && rid < solv->duprules_end)
2741     return SOLVER_RULE_DISTUPGRADE;
2742   if (rid >= solv->infarchrules && rid < solv->infarchrules_end)
2743     return SOLVER_RULE_INFARCH;
2744   if (rid >= solv->bestrules && rid < solv->bestrules_end)
2745     return SOLVER_RULE_BEST;
2746   if (rid >= solv->yumobsrules && rid < solv->yumobsrules_end)
2747     return SOLVER_RULE_YUMOBS;
2748   if (rid >= solv->choicerules && rid < solv->choicerules_end)
2749     return SOLVER_RULE_CHOICE;
2750   if (rid >= solv->learntrules && rid < solv->nrules)
2751     return SOLVER_RULE_LEARNT;
2752   return SOLVER_RULE_UNKNOWN;
2753 }
2754
2755 void
2756 solver_ruleliterals(Solver *solv, Id rid, Queue *q)
2757 {
2758   Pool *pool = solv->pool;
2759   Id p, pp;
2760   Rule *r;
2761
2762   queue_empty(q);
2763   r = solv->rules + rid;
2764   FOR_RULELITERALS(p, pp, r)
2765     if (p != -SYSTEMSOLVABLE)
2766       queue_push(q, p);
2767   if (!q->count)
2768     queue_push(q, -SYSTEMSOLVABLE);     /* hmm, better to return an empty result? */
2769 }
2770
2771 int
2772 solver_rule2jobidx(Solver *solv, Id rid)
2773 {
2774   if (rid < solv->jobrules || rid >= solv->jobrules_end)
2775     return 0;
2776   return solv->ruletojob.elements[rid - solv->jobrules] + 1;
2777 }
2778
2779 /* job rule introspection */
2780 Id
2781 solver_rule2job(Solver *solv, Id rid, Id *whatp)
2782 {
2783   int idx;
2784   if (rid < solv->jobrules || rid >= solv->jobrules_end)
2785     {
2786       if (whatp)
2787         *whatp = 0;
2788       return 0;
2789     }
2790   idx = solv->ruletojob.elements[rid - solv->jobrules];
2791   if (whatp)
2792     *whatp = solv->job.elements[idx + 1];
2793   return solv->job.elements[idx];
2794 }
2795
2796 /* update/feature rule introspection */
2797 Id
2798 solver_rule2solvable(Solver *solv, Id rid)
2799 {
2800   if (rid >= solv->updaterules && rid < solv->updaterules_end)
2801     return rid - solv->updaterules;
2802   if (rid >= solv->featurerules && rid < solv->featurerules_end)
2803     return rid - solv->featurerules;
2804   return 0;
2805 }
2806
2807 Id
2808 solver_rule2pkgrule(Solver *solv, Id rid)
2809 {
2810   if (rid >= solv->choicerules && rid < solv->choicerules_end)
2811     return solv->choicerules_ref[rid - solv->choicerules];
2812   return 0;
2813 }
2814
2815 static void
2816 solver_rule2rules_rec(Solver *solv, Id rid, Queue *q, Map *seen)
2817 {
2818   int i;
2819   Id rid2;
2820
2821   if (seen)
2822     MAPSET(seen, rid);
2823   for (i = solv->learnt_why.elements[rid - solv->learntrules]; (rid2 = solv->learnt_pool.elements[i]) != 0; i++)
2824     {
2825       if (seen)
2826         {
2827           if (MAPTST(seen, rid2))
2828             continue;
2829           if (rid2 >= solv->learntrules)
2830             solver_rule2rules_rec(solv, rid2, q, seen);
2831           continue;
2832         }
2833       queue_push(q, rid2);
2834     }
2835 }
2836
2837 /* learnt rule introspection */
2838 void
2839 solver_rule2rules(Solver *solv, Id rid, Queue *q, int recursive)
2840 {
2841   queue_empty(q);
2842   if (rid < solv->learntrules || rid >= solv->nrules)
2843     return;
2844   if (recursive)
2845     {
2846       Map seen;
2847       map_init(&seen, solv->nrules);
2848       solver_rule2rules_rec(solv, rid, q, &seen);
2849       map_free(&seen);
2850     }
2851   else
2852     solver_rule2rules_rec(solv, rid, q, 0);
2853 }
2854
2855
2856 /* check if the newest versions of pi still provides the dependency we're looking for */
2857 static int
2858 solver_choicerulecheck(Solver *solv, Id pi, Rule *r, Map *m, Queue *q)
2859 {
2860   Pool *pool = solv->pool;
2861   Rule *ur;
2862   Id p, pp;
2863   int i;
2864
2865   if (!q->count || q->elements[0] != pi)
2866     {
2867       if (q->count)
2868         queue_empty(q);
2869       ur = solv->rules + solv->updaterules + (pi - pool->installed->start);
2870       if (!ur->p)
2871         ur = solv->rules + solv->featurerules + (pi - pool->installed->start);
2872       if (!ur->p)
2873         return 0;
2874       queue_push2(q, pi, 0);
2875       FOR_RULELITERALS(p, pp, ur)
2876         if (p > 0)
2877           queue_push(q, p);
2878     }
2879   if (q->count == 2)
2880     return 1;
2881   if (q->count == 3)
2882     {
2883       p = q->elements[2];
2884       return MAPTST(m, p) ? 0 : 1;
2885     }
2886   if (!q->elements[1])
2887     {
2888       for (i = 2; i < q->count; i++)
2889         if (!MAPTST(m, q->elements[i]))
2890           break;
2891       if (i == q->count)
2892         return 0;       /* all provide it, no need to filter */
2893       /* some don't provide it, have to filter */
2894       queue_deleten(q, 0, 2);
2895       policy_filter_unwanted(solv, q, POLICY_MODE_CHOOSE);
2896       queue_unshift(q, 1);      /* filter mark */
2897       queue_unshift(q, pi);
2898     }
2899   for (i = 2; i < q->count; i++)
2900     if (MAPTST(m, q->elements[i]))
2901       return 0;         /* at least one provides it */
2902   return 1;     /* none of the new packages provided it */
2903 }
2904
2905 static inline void
2906 queue_removeelement(Queue *q, Id el)
2907 {
2908   int i, j;
2909   for (i = 0; i < q->count; i++)
2910     if (q->elements[i] == el)
2911       break;
2912   if (i < q->count)
2913     {
2914       for (j = i++; i < q->count; i++)
2915         if (q->elements[i] != el)
2916           q->elements[j++] = q->elements[i];
2917       queue_truncate(q, j);
2918     }
2919 }
2920
2921 void
2922 solver_addchoicerules(Solver *solv)
2923 {
2924   Pool *pool = solv->pool;
2925   Map m, mneg;
2926   Rule *r;
2927   Queue q, qi, qcheck;
2928   int i, j, rid, havechoice;
2929   Id p, d, pp;
2930   Id p2, pp2;
2931   Solvable *s, *s2;
2932   Id lastaddedp, lastaddedd;
2933   int lastaddedcnt;
2934   unsigned int now;
2935
2936   solv->choicerules = solv->nrules;
2937   if (!pool->installed)
2938     {
2939       solv->choicerules_end = solv->nrules;
2940       return;
2941     }
2942   now = solv_timems(0);
2943   solv->choicerules_ref = solv_calloc(solv->pkgrules_end, sizeof(Id));
2944   queue_init(&q);
2945   queue_init(&qi);
2946   queue_init(&qcheck);
2947   map_init(&m, pool->nsolvables);
2948   map_init(&mneg, pool->nsolvables);
2949   /* set up negative assertion map from infarch and dup rules */
2950   for (rid = solv->infarchrules, r = solv->rules + rid; rid < solv->infarchrules_end; rid++, r++)
2951     if (r->p < 0 && !r->w2 && (r->d == 0 || r->d == -1))
2952       MAPSET(&mneg, -r->p);
2953   for (rid = solv->duprules, r = solv->rules + rid; rid < solv->duprules_end; rid++, r++)
2954     if (r->p < 0 && !r->w2 && (r->d == 0 || r->d == -1))
2955       MAPSET(&mneg, -r->p);
2956   lastaddedp = 0;
2957   lastaddedd = 0;
2958   lastaddedcnt = 0;
2959   for (rid = 1; rid < solv->pkgrules_end ; rid++)
2960     {
2961       r = solv->rules + rid;
2962       if (r->p >= 0 || ((r->d == 0 || r->d == -1) && r->w2 <= 0))
2963         continue;       /* only look at requires rules */
2964       /* solver_printrule(solv, SOLV_DEBUG_RESULT, r); */
2965       queue_empty(&q);
2966       queue_empty(&qi);
2967       havechoice = 0;
2968       FOR_RULELITERALS(p, pp, r)
2969         {
2970           if (p < 0)
2971             continue;
2972           s = pool->solvables + p;
2973           if (!s->repo)
2974             continue;
2975           if (s->repo == pool->installed)
2976             {
2977               queue_push(&q, p);
2978               continue;
2979             }
2980           /* check if this package is "blocked" by a installed package */
2981           s2 = 0;
2982           FOR_PROVIDES(p2, pp2, s->name)
2983             {
2984               s2 = pool->solvables + p2;
2985               if (s2->repo != pool->installed)
2986                 continue;
2987               if (!pool->implicitobsoleteusesprovides && s->name != s2->name)
2988                 continue;
2989               if (pool->implicitobsoleteusescolors && !pool_colormatch(pool, s, s2))
2990                 continue;
2991               break;
2992             }
2993           if (p2)
2994             {
2995               /* found installed package p2 that we can update to p */
2996               if (MAPTST(&mneg, p))
2997                 continue;
2998               if (policy_is_illegal(solv, s2, s, 0))
2999                 continue;
3000 #if 0
3001               if (solver_choicerulecheck(solv, p2, r, &m))
3002                 continue;
3003               queue_push(&qi, p2);
3004 #else
3005               queue_push2(&qi, p2, p);
3006 #endif
3007               queue_push(&q, p);
3008               continue;
3009             }
3010           if (s->obsoletes)
3011             {
3012               Id obs, *obsp = s->repo->idarraydata + s->obsoletes;
3013               s2 = 0;
3014               while ((obs = *obsp++) != 0)
3015                 {
3016                   FOR_PROVIDES(p2, pp2, obs)
3017                     {
3018                       s2 = pool->solvables + p2;
3019                       if (s2->repo != pool->installed)
3020                         continue;
3021                       if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p2, obs))
3022                         continue;
3023                       if (pool->obsoleteusescolors && !pool_colormatch(pool, s, s2))
3024                         continue;
3025                       break;
3026                     }
3027                   if (p2)
3028                     break;
3029                 }
3030               if (obs)
3031                 {
3032                   /* found installed package p2 that we can update to p */
3033                   if (MAPTST(&mneg, p))
3034                     continue;
3035                   if (policy_is_illegal(solv, s2, s, 0))
3036                     continue;
3037 #if 0
3038                   if (solver_choicerulecheck(solv, p2, r, &m))
3039                     continue;
3040                   queue_push(&qi, p2);
3041 #else
3042                   queue_push2(&qi, p2, p);
3043 #endif
3044                   queue_push(&q, p);
3045                   continue;
3046                 }
3047             }
3048           /* package p is independent of the installed ones */
3049           havechoice = 1;
3050         }
3051       if (!havechoice || !q.count || !qi.count)
3052         continue;       /* no choice */
3053
3054       FOR_RULELITERALS(p, pp, r)
3055         if (p > 0)
3056           MAPSET(&m, p);
3057
3058       /* do extra checking */
3059       for (i = j = 0; i < qi.count; i += 2)
3060         {
3061           p2 = qi.elements[i];
3062           if (!p2)
3063             continue;
3064           if (solver_choicerulecheck(solv, p2, r, &m, &qcheck))
3065             {
3066               /* oops, remove element p from q */
3067               queue_removeelement(&q, qi.elements[i + 1]);
3068               continue;
3069             }
3070           qi.elements[j++] = p2;
3071         }
3072       queue_truncate(&qi, j);
3073
3074       if (!q.count || !qi.count)
3075         {
3076           FOR_RULELITERALS(p, pp, r)
3077             if (p > 0)
3078               MAPCLR(&m, p);
3079           continue;
3080         }
3081
3082
3083       /* now check the update rules of the installed package.
3084        * if all packages of the update rules are contained in
3085        * the dependency rules, there's no need to set up the choice rule */
3086       for (i = 0; i < qi.count; i++)
3087         {
3088           Rule *ur;
3089           if (!qi.elements[i])
3090             continue;
3091           ur = solv->rules + solv->updaterules + (qi.elements[i] - pool->installed->start);
3092           if (!ur->p)
3093             ur = solv->rules + solv->featurerules + (qi.elements[i] - pool->installed->start);
3094           if (!ur->p)
3095             continue;
3096           FOR_RULELITERALS(p, pp, ur)
3097             if (!MAPTST(&m, p))
3098               break;
3099           if (p)
3100             break;
3101           for (j = i + 1; j < qi.count; j++)
3102             if (qi.elements[i] == qi.elements[j])
3103               qi.elements[j] = 0;
3104         }
3105       /* empty map again */
3106       FOR_RULELITERALS(p, pp, r)
3107         if (p > 0)
3108           MAPCLR(&m, p);
3109       if (i == qi.count)
3110         {
3111 #if 0
3112           printf("skipping choice ");
3113           solver_printrule(solv, SOLV_DEBUG_RESULT, solv->rules + rid);
3114 #endif
3115           continue;
3116         }
3117
3118       /* don't add identical rules */
3119       if (lastaddedp == r->p && lastaddedcnt == q.count)
3120         {
3121           for (i = 0; i < q.count; i++)
3122             if (q.elements[i] != pool->whatprovidesdata[lastaddedd + i])
3123               break;
3124           if (i == q.count)
3125             continue;   /* already added that one */
3126         }
3127       d = q.count ? pool_queuetowhatprovides(pool, &q) : 0;
3128
3129       lastaddedp = r->p;
3130       lastaddedd = d;
3131       lastaddedcnt = q.count;
3132
3133       solver_addrule(solv, r->p, 0, d);
3134       queue_push(&solv->weakruleq, solv->nrules - 1);
3135       solv->choicerules_ref[solv->nrules - 1 - solv->choicerules] = rid;
3136 #if 0
3137       printf("OLD ");
3138       solver_printrule(solv, SOLV_DEBUG_RESULT, solv->rules + rid);
3139       printf("WEAK CHOICE ");
3140       solver_printrule(solv, SOLV_DEBUG_RESULT, solv->rules + solv->nrules - 1);
3141 #endif
3142     }
3143   queue_free(&q);
3144   queue_free(&qi);
3145   queue_free(&qcheck);
3146   map_free(&m);
3147   map_free(&mneg);
3148   solv->choicerules_end = solv->nrules;
3149   /* shrink choicerules_ref */
3150   solv->choicerules_ref = solv_realloc2(solv->choicerules_ref, solv->choicerules_end - solv->choicerules, sizeof(Id));
3151   POOL_DEBUG(SOLV_DEBUG_STATS, "choice rule creation took %d ms\n", solv_timems(now));
3152 }
3153
3154 /* called when a choice rule is disabled by analyze_unsolvable. We also
3155  * have to disable all other choice rules so that the best packages get
3156  * picked */
3157 void
3158 solver_disablechoicerules(Solver *solv, Rule *r)
3159 {
3160   Id rid, p, pp;
3161   Pool *pool = solv->pool;
3162   Map m;
3163   Rule *or;
3164
3165   or = solv->rules + solv->choicerules_ref[(r - solv->rules) - solv->choicerules];
3166   map_init(&m, pool->nsolvables);
3167   FOR_RULELITERALS(p, pp, or)
3168     if (p > 0)
3169       MAPSET(&m, p);
3170   FOR_RULELITERALS(p, pp, r)
3171     if (p > 0)
3172       MAPCLR(&m, p);
3173   for (rid = solv->choicerules; rid < solv->choicerules_end; rid++)
3174     {
3175       r = solv->rules + rid;
3176       if (r->d < 0)
3177         continue;
3178       or = solv->rules + solv->choicerules_ref[(r - solv->rules) - solv->choicerules];
3179       FOR_RULELITERALS(p, pp, or)
3180         if (p > 0 && MAPTST(&m, p))
3181           break;
3182       if (p)
3183         solver_disablerule(solv, r);
3184     }
3185 }
3186
3187 static void
3188 prune_to_update_targets(Solver *solv, Id *cp, Queue *q)
3189 {
3190   int i, j;
3191   Id p, *cp2;
3192   for (i = j = 0; i < q->count; i++)
3193     {
3194       p = q->elements[i];
3195       for (cp2 = cp; *cp2; cp2++)
3196         if (*cp2 == p)
3197           {
3198             q->elements[j++] = p;
3199             break;
3200           }
3201     }
3202   queue_truncate(q, j);
3203 }
3204
3205 static void
3206 prune_to_dup_packages(Solver *solv, Id p, Queue *q)
3207 {
3208   int i, j;
3209   for (i = j = 0; i < q->count; i++)
3210     {
3211       Id p = q->elements[i];
3212       if (MAPTST(&solv->dupmap, p))
3213         q->elements[j++] = p;
3214     }
3215   queue_truncate(q, j);
3216 }
3217
3218 void
3219 solver_addbestrules(Solver *solv, int havebestinstalljobs)
3220 {
3221   Pool *pool = solv->pool;
3222   Id p;
3223   Solvable *s;
3224   Repo *installed = solv->installed;
3225   Queue q, q2;
3226   Rule *r;
3227   Queue r2pkg;
3228   int i, oldcnt;
3229
3230   solv->bestrules = solv->nrules;
3231   if (!installed)
3232     {
3233       solv->bestrules_end = solv->nrules;
3234       return;
3235     }
3236   queue_init(&q);
3237   queue_init(&q2);
3238   queue_init(&r2pkg);
3239
3240   if (havebestinstalljobs)
3241     {
3242       for (i = 0; i < solv->job.count; i += 2)
3243         {
3244           if ((solv->job.elements[i] & (SOLVER_JOBMASK | SOLVER_FORCEBEST)) == (SOLVER_INSTALL | SOLVER_FORCEBEST))
3245             {
3246               int j;
3247               Id p2, pp2;
3248               for (j = 0; j < solv->ruletojob.count; j++)
3249                 if (solv->ruletojob.elements[j] == i)
3250                   break;
3251               if (j == solv->ruletojob.count)
3252                 continue;
3253               r = solv->rules + solv->jobrules + j;
3254               queue_empty(&q);
3255               FOR_RULELITERALS(p2, pp2, r)
3256                 if (p2 > 0)
3257                   queue_push(&q, p2);
3258               if (!q.count)
3259                 continue;       /* orphaned */
3260               /* select best packages, just look at prio and version */
3261               oldcnt = q.count;
3262               policy_filter_unwanted(solv, &q, POLICY_MODE_RECOMMEND);
3263               if (q.count == oldcnt)
3264                 continue;       /* nothing filtered */
3265               p2 = queue_shift(&q);
3266               if (q.count < 2)
3267                 solver_addrule(solv, p2, q.count ? q.elements[0] : 0, 0);
3268               else
3269                 solver_addrule(solv, p2, 0, pool_queuetowhatprovides(pool, &q));
3270               queue_push(&r2pkg, -(solv->jobrules + j));
3271             }
3272         }
3273     }
3274
3275   if (solv->bestupdatemap_all || solv->bestupdatemap.size)
3276     {
3277       FOR_REPO_SOLVABLES(installed, p, s)
3278         {
3279           Id d, p2, pp2;
3280           if (!solv->updatemap_all && (!solv->updatemap.size || !MAPTST(&solv->updatemap, p - installed->start)))
3281             continue;
3282           if (!solv->bestupdatemap_all && (!solv->bestupdatemap.size || !MAPTST(&solv->bestupdatemap, p - installed->start)))
3283             continue;
3284           queue_empty(&q);
3285           if (solv->bestobeypolicy)
3286             r = solv->rules + solv->updaterules + (p - installed->start);
3287           else
3288             {
3289               r = solv->rules + solv->featurerules + (p - installed->start);
3290               if (!r->p)        /* identical to update rule? */
3291                 r = solv->rules + solv->updaterules + (p - installed->start);
3292             }
3293           if (solv->specialupdaters && (d = solv->specialupdaters[p - installed->start]) != 0 && r == solv->rules + solv->updaterules + (p - installed->start))
3294             {
3295               /* need to check specialupdaters */
3296               if (r->p == p)    /* be careful with the dup case */
3297                 queue_push(&q, p);
3298               while ((p2 = pool->whatprovidesdata[d++]) != 0)
3299                 queue_push(&q, p2);
3300             }
3301           else
3302             {
3303               FOR_RULELITERALS(p2, pp2, r)
3304                 if (p2 > 0)
3305                   queue_push(&q, p2);
3306             }
3307           if (solv->update_targets && solv->update_targets->elements[p - installed->start])
3308             prune_to_update_targets(solv, solv->update_targets->elements + solv->update_targets->elements[p - installed->start], &q);
3309           if (solv->dupinvolvedmap.size && MAPTST(&solv->dupinvolvedmap, p))
3310             prune_to_dup_packages(solv, p, &q);
3311           /* select best packages, just look at prio and version */
3312           policy_filter_unwanted(solv, &q, POLICY_MODE_RECOMMEND);
3313           if (!q.count)
3314             continue;   /* orphaned */
3315           if (solv->bestobeypolicy)
3316             {
3317               /* also filter the best of the feature rule packages and add them */
3318               r = solv->rules + solv->featurerules + (p - installed->start);
3319               if (r->p)
3320                 {
3321                   int j;
3322                   queue_empty(&q2);
3323                   FOR_RULELITERALS(p2, pp2, r)
3324                     if (p2 > 0)
3325                       queue_push(&q2, p2);
3326                   if (solv->update_targets && solv->update_targets->elements[p - installed->start])
3327                     prune_to_update_targets(solv, solv->update_targets->elements + solv->update_targets->elements[p - installed->start], &q2);
3328                   if (solv->dupinvolvedmap.size && MAPTST(&solv->dupinvolvedmap, p))
3329                     prune_to_dup_packages(solv, p, &q2);
3330                   policy_filter_unwanted(solv, &q2, POLICY_MODE_RECOMMEND);
3331                   for (j = 0; j < q2.count; j++)
3332                     queue_pushunique(&q, q2.elements[j]);
3333                 }
3334             }
3335           p2 = queue_shift(&q);
3336           if (q.count < 2)
3337             solver_addrule(solv, p2, q.count ? q.elements[0] : 0, 0);
3338           else
3339             solver_addrule(solv, p2, 0, pool_queuetowhatprovides(pool, &q));
3340           queue_push(&r2pkg, p);
3341         }
3342     }
3343   if (r2pkg.count)
3344     solv->bestrules_pkg = solv_memdup2(r2pkg.elements, r2pkg.count, sizeof(Id));
3345   solv->bestrules_end = solv->nrules;
3346   queue_free(&q);
3347   queue_free(&q2);
3348   queue_free(&r2pkg);
3349 }
3350
3351
3352
3353
3354 /* yumobs rule handling */
3355
3356 static void
3357 find_obsolete_group(Solver *solv, Id obs, Queue *q)
3358 {
3359   Pool *pool = solv->pool;
3360   Queue qn;
3361   Id p2, pp2, op, *opp, opp2;
3362   int i, j, qnc, ncnt;
3363
3364   queue_empty(q);
3365   FOR_PROVIDES(p2, pp2, obs)
3366     {
3367       Solvable *s2 = pool->solvables + p2;
3368       if (s2->repo != pool->installed)
3369         continue;
3370       if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p2, obs))
3371         continue;
3372       /* we obsolete installed package s2 with obs. now find all other packages that have the same dep  */
3373       for (opp = solv->obsoletes_data + solv->obsoletes[p2 - solv->installed->start]; (op = *opp++) != 0;)
3374         {
3375           Solvable *os = pool->solvables + op;
3376           Id obs2, *obsp2;
3377           if (!os->obsoletes)
3378             continue;
3379           if (pool->obsoleteusescolors && !pool_colormatch(pool, s2, os))
3380             continue;
3381           obsp2 = os->repo->idarraydata + os->obsoletes;
3382           while ((obs2 = *obsp2++) != 0)
3383             if (obs2 == obs)
3384               break;
3385           if (obs2)
3386             queue_pushunique(q, op);
3387         }
3388       /* also search packages with the same name */
3389       FOR_PROVIDES(op, opp2, s2->name)
3390         {
3391           Solvable *os = pool->solvables + op;
3392           Id obs2, *obsp2;
3393           if (os->name != s2->name)
3394             continue;
3395           if (!os->obsoletes)
3396             continue;
3397           if (pool->obsoleteusescolors && !pool_colormatch(pool, s2, os))
3398             continue;
3399           obsp2 = os->repo->idarraydata + os->obsoletes;
3400           while ((obs2 = *obsp2++) != 0)
3401             if (obs2 == obs)
3402               break;
3403           if (obs2)
3404             queue_pushunique(q, op);
3405         }
3406     }
3407   /* find names so that we can build groups */
3408   queue_init_clone(&qn, q);
3409   prune_to_best_version(solv->pool, &qn);
3410 #if 0
3411 {
3412   for (i = 0; i < qn.count; i++)
3413     printf(" + %s\n", pool_solvid2str(pool, qn.elements[i]));
3414 }
3415 #endif
3416   /* filter into name groups */
3417   qnc = qn.count;
3418   if (qnc == 1)
3419     {
3420       queue_free(&qn);
3421       queue_empty(q);
3422       return;
3423     }
3424   ncnt = 0;
3425   for (i = 0; i < qnc; i++)
3426     {
3427       Id n = pool->solvables[qn.elements[i]].name;
3428       int got = 0;
3429       for (j = 0; j < q->count; j++)
3430         {
3431           Id p = q->elements[j];
3432           if (pool->solvables[p].name == n)
3433             {
3434               queue_push(&qn, p);
3435               got = 1;
3436             }
3437         }
3438       if (got)
3439         {
3440           queue_push(&qn, 0);
3441           ncnt++;
3442         }
3443     }
3444   if (ncnt <= 1)
3445     {
3446       queue_empty(q);
3447     }
3448   else
3449     {
3450       queue_empty(q);
3451       queue_insertn(q, 0, qn.count - qnc, qn.elements + qnc);
3452     }
3453   queue_free(&qn);
3454 }
3455
3456 void
3457 solver_addyumobsrules(Solver *solv)
3458 {
3459   Pool *pool = solv->pool;
3460   Repo *installed = solv->installed;
3461   Id p, op, *opp;
3462   Solvable *s;
3463   Queue qo, qq, yumobsinfoq;
3464   int i, j, k;
3465   unsigned int now;
3466
3467   solv->yumobsrules = solv->nrules;
3468   if (!installed || !solv->obsoletes)
3469     {
3470       solv->yumobsrules_end = solv->nrules;
3471       return;
3472     }
3473   now = solv_timems(0);
3474   queue_init(&qo);
3475   FOR_REPO_SOLVABLES(installed, p, s)
3476     {
3477       if (!solv->obsoletes[p - installed->start])
3478         continue;
3479 #if 0
3480 printf("checking yumobs for %s\n", pool_solvable2str(pool, s));
3481 #endif
3482       queue_empty(&qo);
3483       for (opp = solv->obsoletes_data + solv->obsoletes[p - installed->start]; (op = *opp++) != 0;)
3484         {
3485           Solvable *os = pool->solvables + op;
3486           Id obs, *obsp = os->repo->idarraydata + os->obsoletes;
3487           Id p2, pp2;
3488           while ((obs = *obsp++) != 0)
3489             {
3490               FOR_PROVIDES(p2, pp2, obs)
3491                 {
3492                   Solvable *s2 = pool->solvables + p2;
3493                   if (s2->repo != installed)
3494                     continue;
3495                   if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p2, obs))
3496                     continue;
3497                   if (pool->obsoleteusescolors && !pool_colormatch(pool, s, s2))
3498                     continue;
3499                   queue_pushunique(&qo, obs);
3500                   break;
3501                 }
3502             }
3503         }
3504     }
3505   if (!qo.count)
3506     {
3507       queue_free(&qo);
3508       return;
3509     }
3510   queue_init(&yumobsinfoq);
3511   queue_init(&qq);
3512   for (i = 0; i < qo.count; i++)
3513     {
3514       int group, groupk, groupstart;
3515       queue_empty(&qq);
3516 #if 0
3517 printf("investigating %s\n", pool_dep2str(pool, qo.elements[i]));
3518 #endif
3519       find_obsolete_group(solv, qo.elements[i], &qq);
3520 #if 0
3521 printf("result:\n");
3522 for (j = 0; j < qq.count; j++)
3523   if (qq.elements[j] == 0)
3524     printf("---\n");
3525   else
3526     printf("%s\n", pool_solvid2str(pool, qq.elements[j]));
3527 #endif
3528
3529       if (!qq.count)
3530         continue;
3531       /* at least two goups, build rules */
3532       group = 0;
3533       for (j = 0; j < qq.count; j++)
3534         {
3535           p = qq.elements[j];
3536           if (!p)
3537             {
3538               group++;
3539               continue;
3540             }
3541           if (pool->solvables[p].repo == installed)
3542             continue;
3543           groupk = 0;
3544           groupstart = 0;
3545           for (k = 0; k < qq.count; k++)
3546             {
3547               Id pk = qq.elements[k];
3548               if (pk)
3549                 continue;
3550               if (group != groupk && k > groupstart)
3551                 {
3552                   /* add the rule */
3553                   if (k - groupstart == 1)
3554                     solver_addrule(solv, -p, qq.elements[groupstart], 0);
3555                   else
3556                     solver_addrule(solv, -p, 0, pool_ids2whatprovides(pool, qq.elements + groupstart, k - groupstart));
3557                   queue_push(&yumobsinfoq, qo.elements[i]);
3558                 }
3559               groupstart = k + 1;
3560               groupk++;
3561             }
3562         }
3563     }
3564   if (yumobsinfoq.count)
3565     solv->yumobsrules_info = solv_memdup2(yumobsinfoq.elements, yumobsinfoq.count, sizeof(Id));
3566   queue_free(&yumobsinfoq);
3567   queue_free(&qq);
3568   queue_free(&qo);
3569   solv->yumobsrules_end = solv->nrules;
3570   POOL_DEBUG(SOLV_DEBUG_STATS, "yumobs rule creation took %d ms\n", solv_timems(now));
3571 }
3572
3573 #undef CLEANDEPSDEBUG
3574
3575 /*
3576  * This functions collects all packages that are looked at
3577  * when a dependency is checked. We need it to "pin" installed
3578  * packages when removing a supplemented package in createcleandepsmap.
3579  * Here's an not uncommon example:
3580  *   A contains "Supplements: packageand(B, C)"
3581  *   B contains "Requires: A"
3582  * Now if we remove C, the supplements is no longer true,
3583  * thus we also remove A. Without the dep_pkgcheck function, we
3584  * would now also remove B, but this is wrong, as adding back
3585  * C doesn't make the supplements true again. Thus we "pin" B
3586  * when we remove A.
3587  * There's probably a better way to do this, but I haven't come
3588  * up with it yet ;)
3589  */
3590 static inline void
3591 dep_pkgcheck(Solver *solv, Id dep, Map *m, Queue *q)
3592 {
3593   Pool *pool = solv->pool;
3594   Id p, pp;
3595
3596   if (ISRELDEP(dep))
3597     {
3598       Reldep *rd = GETRELDEP(pool, dep);
3599       if (rd->flags >= 8)
3600         {
3601           if (rd->flags == REL_AND)
3602             {
3603               dep_pkgcheck(solv, rd->name, m, q);
3604               dep_pkgcheck(solv, rd->evr, m, q);
3605               return;
3606             }
3607           if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
3608             return;
3609         }
3610     }
3611   FOR_PROVIDES(p, pp, dep)
3612     if (!m || MAPTST(m, p))
3613       queue_push(q, p);
3614 }
3615
3616 static int
3617 check_xsupp(Solver *solv, Queue *depq, Id dep)
3618 {
3619   Pool *pool = solv->pool;
3620   Id p, pp;
3621
3622   if (ISRELDEP(dep))
3623     {
3624       Reldep *rd = GETRELDEP(pool, dep);
3625       if (rd->flags >= 8)
3626         {
3627           if (rd->flags == REL_AND)
3628             {
3629               if (!check_xsupp(solv, depq, rd->name))
3630                 return 0;
3631               return check_xsupp(solv, depq, rd->evr);
3632             }
3633           if (rd->flags == REL_OR)
3634             {
3635               if (check_xsupp(solv, depq, rd->name))
3636                 return 1;
3637               return check_xsupp(solv, depq, rd->evr);
3638             }
3639           if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
3640 #if 0
3641             return solver_splitprovides(solv, rd->evr);
3642 #else
3643             return 0;
3644 #endif
3645         }
3646       if (depq && rd->flags == REL_NAMESPACE)
3647         {
3648           int i;
3649           for (i = 0; i < depq->count; i++)
3650             if (depq->elements[i] == dep || depq->elements[i] == rd->name)
3651              return 1;
3652         }
3653     }
3654   FOR_PROVIDES(p, pp, dep)
3655     if (p == SYSTEMSOLVABLE || pool->solvables[p].repo == solv->installed)
3656       return 1;
3657   return 0;
3658 }
3659
3660 static inline int
3661 queue_contains(Queue *q, Id id)
3662 {
3663   int i;
3664   for (i = 0; i < q->count; i++)
3665     if (q->elements[i] == id)
3666       return 1;
3667   return 0;
3668 }
3669
3670 #ifdef ENABLE_COMPLEX_DEPS
3671 static void
3672 complex_cleandeps_remove(Pool *pool, Id ip, Id req, Map *im, Map *installedm, Queue *iq)
3673 {
3674   int i;
3675   Queue dq;
3676   Id p;
3677
3678   queue_init(&dq);
3679   i = pool_normalize_complex_dep(pool, req, &dq, CPLXDEPS_EXPAND);
3680   if (i == 0 || i == 1)
3681     {
3682       queue_free(&dq);
3683       return;
3684     }
3685   for (i = 0; i < dq.count; i++)
3686     {
3687       for (; (p = dq.elements[i]) != 0; i++)
3688         {
3689           if (p < 0)
3690             {
3691               if (!MAPTST(installedm, -p))
3692                 break;
3693               continue;
3694             }
3695           if (p != SYSTEMSOLVABLE && MAPTST(im, p))
3696             {
3697 #ifdef CLEANDEPSDEBUG
3698               printf("%s requires/recommends %s\n", pool_solvid2str(pool, ip), pool_solvid2str(pool, p));
3699 #endif
3700               queue_push(iq, p);
3701             }
3702         }
3703       while (dq.elements[i])
3704         i++;
3705     }
3706   queue_free(&dq);
3707 }
3708
3709 static void
3710 complex_cleandeps_addback(Pool *pool, Id ip, Id req, Map *im, Map *installedm, Queue *iq, Map *userinstalled)
3711 {
3712   int i, blk;
3713   Queue dq;
3714   Id p;
3715
3716   queue_init(&dq);
3717   i = pool_normalize_complex_dep(pool, req, &dq, CPLXDEPS_EXPAND);
3718   if (i == 0 || i == 1)
3719     {
3720       queue_free(&dq);
3721       return;
3722     }
3723   for (i = 0; i < dq.count; i++)
3724     {
3725       blk = i;
3726       for (; (p = dq.elements[i]) != 0; i++)
3727         {
3728           if (p < 0)
3729             {
3730               if (!MAPTST(installedm, -p))
3731                 break;
3732               continue;
3733             }
3734           if (MAPTST(im, p))
3735             break;
3736         }
3737       if (!p)
3738         {
3739           for (i = blk; (p = dq.elements[i]) != 0; i++)
3740             {
3741               if (p < 0)
3742                 continue;
3743               if (!MAPTST(installedm, p))
3744                 continue;
3745               if (p == ip || MAPTST(userinstalled, p - pool->installed->start))
3746                 continue;
3747 #ifdef CLEANDEPSDEBUG
3748               printf("%s requires/recommends %s\n", pool_solvid2str(pool, ip), pool_solvid2str(pool, p));
3749 #endif
3750               MAPSET(im, p);
3751               queue_push(iq, p);
3752             }
3753         }
3754       while (dq.elements[i])
3755         i++;
3756     }
3757   queue_free(&dq);
3758 }
3759
3760 #endif
3761
3762 /*
3763  * Find all installed packages that are no longer
3764  * needed regarding the current solver job.
3765  *
3766  * The algorithm is:
3767  * - remove pass: remove all packages that could have
3768  *   been dragged in by the obsoleted packages.
3769  *   i.e. if package A is obsolete and contains "Requires: B",
3770  *   also remove B, as installing A will have pulled in B.
3771  *   after this pass, we have a set of still installed packages
3772  *   with broken dependencies.
3773  * - add back pass:
3774  *   now add back all packages that the still installed packages
3775  *   require.
3776  *
3777  * The cleandeps packages are the packages removed in the first
3778  * pass and not added back in the second pass.
3779  *
3780  * If we search for unneeded packages (unneeded is true), we
3781  * simply remove all packages except the userinstalled ones in
3782  * the first pass.
3783  */
3784 static void
3785 solver_createcleandepsmap(Solver *solv, Map *cleandepsmap, int unneeded)
3786 {
3787   Pool *pool = solv->pool;
3788   Repo *installed = solv->installed;
3789   Queue *job = &solv->job;
3790   Map userinstalled;
3791   Map im;
3792   Map installedm;
3793   Rule *r;
3794   Id rid, how, what, select;
3795   Id p, pp, ip, jp;
3796   Id req, *reqp, sup, *supp;
3797   Solvable *s;
3798   Queue iq, iqcopy, xsuppq;
3799   int i;
3800
3801   map_empty(cleandepsmap);
3802   if (!installed || installed->end == installed->start)
3803     return;
3804   map_init(&userinstalled, installed->end - installed->start);
3805   map_init(&im, pool->nsolvables);
3806   map_init(&installedm, pool->nsolvables);
3807   queue_init(&iq);
3808   queue_init(&xsuppq);
3809
3810   for (i = 0; i < job->count; i += 2)
3811     {
3812       how = job->elements[i];
3813       if ((how & SOLVER_JOBMASK) == SOLVER_USERINSTALLED)
3814         {
3815           what = job->elements[i + 1];
3816           select = how & SOLVER_SELECTMASK;
3817           if (select == SOLVER_SOLVABLE_ALL || (select == SOLVER_SOLVABLE_REPO && what == installed->repoid))
3818             FOR_REPO_SOLVABLES(installed, p, s)
3819               MAPSET(&userinstalled, p - installed->start);
3820           FOR_JOB_SELECT(p, pp, select, what)
3821             if (pool->solvables[p].repo == installed)
3822               MAPSET(&userinstalled, p - installed->start);
3823         }
3824       if ((how & (SOLVER_JOBMASK | SOLVER_SELECTMASK)) == (SOLVER_ERASE | SOLVER_SOLVABLE_PROVIDES))
3825         {
3826           what = job->elements[i + 1];
3827           if (ISRELDEP(what))
3828             {
3829               Reldep *rd = GETRELDEP(pool, what);
3830               if (rd->flags != REL_NAMESPACE)
3831                 continue;
3832               if (rd->evr == 0)
3833                 {
3834                   queue_pushunique(&iq, rd->name);
3835                   continue;
3836                 }
3837               FOR_PROVIDES(p, pp, what)
3838                 if (p)
3839                   break;
3840               if (p)
3841                 continue;
3842               queue_pushunique(&iq, what);
3843             }
3844         }
3845     }
3846
3847   /* have special namespace cleandeps erases */
3848   if (iq.count)
3849     {
3850       for (ip = installed->start; ip < installed->end; ip++)
3851         {
3852           s = pool->solvables + ip;
3853           if (s->repo != installed)
3854             continue;
3855           if (!s->supplements)
3856             continue;
3857           supp = s->repo->idarraydata + s->supplements;
3858           while ((sup = *supp++) != 0)
3859             if (ISRELDEP(sup) && check_xsupp(solv, &iq, sup) && !check_xsupp(solv, 0, sup))
3860               {
3861 #ifdef CLEANDEPSDEBUG
3862                 printf("xsupp %s from %s\n", pool_dep2str(pool, sup), pool_solvid2str(pool, ip));
3863 #endif
3864                 queue_pushunique(&xsuppq, sup);
3865               }
3866         }
3867       queue_empty(&iq);
3868     }
3869
3870   /* also add visible patterns to userinstalled for openSUSE */
3871   if (1)
3872     {
3873       Dataiterator di;
3874       dataiterator_init(&di, pool, 0, 0, SOLVABLE_ISVISIBLE, 0, 0);
3875       while (dataiterator_step(&di))
3876         {
3877           Id *dp;
3878           if (di.solvid <= 0)
3879             continue;
3880           s = pool->solvables + di.solvid;
3881           if (!s->repo || !s->requires)
3882             continue;
3883           if (s->repo != installed && !pool_installable(pool, s))
3884             continue;
3885           if (strncmp(pool_id2str(pool, s->name), "pattern:", 8) != 0)
3886             continue;
3887           dp = s->repo->idarraydata + s->requires;
3888           for (dp = s->repo->idarraydata + s->requires; *dp; dp++)
3889             FOR_PROVIDES(p, pp, *dp)
3890               if (pool->solvables[p].repo == installed)
3891                 {
3892                   if (strncmp(pool_id2str(pool, pool->solvables[p].name), "pattern", 7) != 0)
3893                     continue;
3894                   MAPSET(&userinstalled, p - installed->start);
3895                 }
3896         }
3897       dataiterator_free(&di);
3898     }
3899   if (1)
3900     {
3901       /* all products and their buddies are userinstalled */
3902       for (p = installed->start; p < installed->end; p++)
3903         {
3904           Solvable *s = pool->solvables + p;
3905           if (s->repo != installed)
3906             continue;
3907           if (!strncmp("product:", pool_id2str(pool, s->name), 8))
3908             {
3909               MAPSET(&userinstalled, p - installed->start);
3910 #ifdef ENABLE_LINKED_PKGS
3911               if (solv->instbuddy && solv->instbuddy[p - installed->start] > 1)
3912                 {
3913                   Id buddy = solv->instbuddy[p - installed->start];
3914                   if (buddy >= installed->start && buddy < installed->end)
3915                     MAPSET(&userinstalled, buddy - installed->start);
3916                 }
3917 #endif
3918             }
3919         }
3920     }
3921
3922   /* add all positive elements (e.g. locks) to "userinstalled" */
3923   for (rid = solv->jobrules; rid < solv->jobrules_end; rid++)
3924     {
3925       r = solv->rules + rid;
3926       if (r->d < 0)
3927         continue;
3928       i = solv->ruletojob.elements[rid - solv->jobrules];
3929       if ((job->elements[i] & SOLVER_CLEANDEPS) == SOLVER_CLEANDEPS)
3930         continue;
3931       FOR_RULELITERALS(p, jp, r)
3932         if (p > 0 && pool->solvables[p].repo == installed)
3933           MAPSET(&userinstalled, p - installed->start);
3934     }
3935
3936   /* add all cleandeps candidates to iq */
3937   for (rid = solv->jobrules; rid < solv->jobrules_end; rid++)
3938     {
3939       r = solv->rules + rid;
3940       if (r->d < 0)                             /* disabled? */
3941         continue;
3942       if (r->d == 0 && r->p < 0 && r->w2 == 0)  /* negative assertion (erase job)? */
3943         {
3944           p = -r->p;
3945           if (pool->solvables[p].repo != installed)
3946             continue;
3947           MAPCLR(&userinstalled, p - installed->start);
3948           if (unneeded)
3949             continue;
3950           i = solv->ruletojob.elements[rid - solv->jobrules];
3951           how = job->elements[i];
3952           if ((how & (SOLVER_JOBMASK|SOLVER_CLEANDEPS)) == (SOLVER_ERASE|SOLVER_CLEANDEPS))
3953             queue_push(&iq, p);
3954         }
3955       else if (r->p > 0)                        /* install job */
3956         {
3957           if (unneeded)
3958             continue;
3959           i = solv->ruletojob.elements[rid - solv->jobrules];
3960           if ((job->elements[i] & SOLVER_CLEANDEPS) == SOLVER_CLEANDEPS)
3961             {
3962               /* check if the literals all obsolete some installed package */
3963               Map om;
3964               int iqstart;
3965
3966               /* just one installed literal */
3967               if (r->d == 0 && r->w2 == 0 && pool->solvables[r->p].repo == installed)
3968                 continue;
3969               /* multiversion is bad */
3970               if (solv->multiversion.size && !solv->keepexplicitobsoletes)
3971                 {
3972                   FOR_RULELITERALS(p, jp, r)
3973                     if (MAPTST(&solv->multiversion, p))
3974                       break;
3975                   if (p)
3976                     continue;
3977                 }
3978
3979               om.size = 0;
3980               iqstart = iq.count;
3981               FOR_RULELITERALS(p, jp, r)
3982                 {
3983                   if (p < 0)
3984                     {
3985                       queue_truncate(&iq, iqstart);     /* abort */
3986                       break;
3987                     }
3988                   if (pool->solvables[p].repo == installed)
3989                     {
3990                       if (iq.count == iqstart)
3991                         queue_push(&iq, p);
3992                       else
3993                         {
3994                           for (i = iqstart; i < iq.count; i++)
3995                             if (iq.elements[i] == p)
3996                               break;
3997                           queue_truncate(&iq, iqstart);
3998                           if (i < iq.count)
3999                             queue_push(&iq, p);
4000                         }
4001                     }
4002                   else
4003                     intersect_obsoletes(solv, p, &iq, iqstart, &om);
4004                   if (iq.count == iqstart)
4005                     break;
4006                 }
4007               if (om.size)
4008                 map_free(&om);
4009             }
4010         }
4011     }
4012   queue_init_clone(&iqcopy, &iq);
4013
4014   if (!unneeded)
4015     {
4016       if (solv->cleandeps_updatepkgs)
4017         for (i = 0; i < solv->cleandeps_updatepkgs->count; i++)
4018           queue_push(&iq, solv->cleandeps_updatepkgs->elements[i]);
4019     }
4020
4021   if (unneeded)
4022     queue_empty(&iq);   /* just in case... */
4023
4024   /* clear userinstalled bit for the packages we really want to delete/update */
4025   for (i = 0; i < iq.count; i++)
4026     {
4027       p = iq.elements[i];
4028       if (pool->solvables[p].repo != installed)
4029         continue;
4030       MAPCLR(&userinstalled, p - installed->start);
4031     }
4032
4033   for (p = installed->start; p < installed->end; p++)
4034     {
4035       if (pool->solvables[p].repo != installed)
4036         continue;
4037       MAPSET(&installedm, p);
4038       if (unneeded && !MAPTST(&userinstalled, p - installed->start))
4039         continue;
4040       MAPSET(&im, p);
4041     }
4042   MAPSET(&installedm, SYSTEMSOLVABLE);
4043   MAPSET(&im, SYSTEMSOLVABLE);
4044
4045 #ifdef CLEANDEPSDEBUG
4046   printf("REMOVE PASS\n");
4047 #endif
4048
4049   for (;;)
4050     {
4051       if (!iq.count)
4052         {
4053           if (unneeded)
4054             break;
4055           /* supplements pass */
4056           for (ip = installed->start; ip < installed->end; ip++)
4057             {
4058               if (!MAPTST(&installedm, ip))
4059                 continue;
4060               s = pool->solvables + ip;
4061               if (!s->supplements)
4062                 continue;
4063               if (!MAPTST(&im, ip))
4064                 continue;
4065               if (MAPTST(&userinstalled, ip - installed->start))
4066                 continue;
4067               supp = s->repo->idarraydata + s->supplements;
4068               while ((sup = *supp++) != 0)
4069                 if (dep_possible(solv, sup, &im))
4070                   break;
4071               if (!sup)
4072                 {
4073                   supp = s->repo->idarraydata + s->supplements;
4074                   while ((sup = *supp++) != 0)
4075                     if (dep_possible(solv, sup, &installedm) || (xsuppq.count && queue_contains(&xsuppq, sup)))
4076                       {
4077                         /* no longer supplemented, also erase */
4078                         int iqcount = iq.count;
4079                         /* pin packages, see comment above dep_pkgcheck */
4080                         dep_pkgcheck(solv, sup, &im, &iq);
4081                         for (i = iqcount; i < iq.count; i++)
4082                           {
4083                             Id pqp = iq.elements[i];
4084                             if (pool->solvables[pqp].repo == installed)
4085                               MAPSET(&userinstalled, pqp - installed->start);
4086                           }
4087                         queue_truncate(&iq, iqcount);
4088 #ifdef CLEANDEPSDEBUG
4089                         printf("%s supplemented [%s]\n", pool_solvid2str(pool, ip), pool_dep2str(pool, sup));
4090 #endif
4091                         queue_push(&iq, ip);
4092                       }
4093                 }
4094             }
4095           if (!iq.count)
4096             break;      /* no supplementing package found, we're done */
4097         }
4098       ip = queue_shift(&iq);
4099       s = pool->solvables + ip;
4100       if (!MAPTST(&im, ip))
4101         continue;
4102       if (!MAPTST(&installedm, ip))
4103         continue;
4104       if (s->repo == installed && MAPTST(&userinstalled, ip - installed->start))
4105         continue;
4106       MAPCLR(&im, ip);
4107 #ifdef CLEANDEPSDEBUG
4108       printf("removing %s\n", pool_solvable2str(pool, s));
4109 #endif
4110       if (s->requires)
4111         {
4112           reqp = s->repo->idarraydata + s->requires;
4113           while ((req = *reqp++) != 0)
4114             {
4115               if (req == SOLVABLE_PREREQMARKER)
4116                 continue;
4117 #ifdef ENABLE_COMPLEX_DEPS
4118               if (pool_is_complex_dep(pool, req))
4119                 {
4120                   complex_cleandeps_remove(pool, ip, req, &im, &installedm, &iq);
4121                   continue;
4122                 }
4123 #endif
4124               FOR_PROVIDES(p, pp, req)
4125                 {
4126                   if (p != SYSTEMSOLVABLE && MAPTST(&im, p))
4127                     {
4128 #ifdef CLEANDEPSDEBUG
4129                       printf("%s requires %s\n", pool_solvid2str(pool, ip), pool_solvid2str(pool, p));
4130 #endif
4131                       queue_push(&iq, p);
4132                     }
4133                 }
4134             }
4135         }
4136       if (s->recommends)
4137         {
4138           reqp = s->repo->idarraydata + s->recommends;
4139           while ((req = *reqp++) != 0)
4140             {
4141 #ifdef ENABLE_COMPLEX_DEPS
4142               if (pool_is_complex_dep(pool, req))
4143                 {
4144                   complex_cleandeps_remove(pool, ip, req, &im, &installedm, &iq);
4145                   continue;
4146                 }
4147 #endif
4148               FOR_PROVIDES(p, pp, req)
4149                 {
4150                   if (p != SYSTEMSOLVABLE && MAPTST(&im, p))
4151                     {
4152 #ifdef CLEANDEPSDEBUG
4153                       printf("%s recommends %s\n", pool_solvid2str(pool, ip), pool_solvid2str(pool, p));
4154 #endif
4155                       queue_push(&iq, p);
4156                     }
4157                 }
4158             }
4159         }
4160     }
4161
4162   /* turn userinstalled into remove set for pruning */
4163   map_empty(&userinstalled);
4164   for (rid = solv->jobrules; rid < solv->jobrules_end; rid++)
4165     {
4166       r = solv->rules + rid;
4167       if (r->p >= 0 || r->d != 0 || r->w2 != 0)
4168         continue;       /* disabled or not erase */
4169       p = -r->p;
4170       MAPCLR(&im, p);
4171       if (pool->solvables[p].repo == installed)
4172         MAPSET(&userinstalled, p - installed->start);
4173     }
4174   if (!unneeded && solv->cleandeps_updatepkgs)
4175     {
4176       for (i = 0; i < solv->cleandeps_updatepkgs->count; i++)
4177         {
4178           p = solv->cleandeps_updatepkgs->elements[i];
4179           if (pool->solvables[p].repo == installed)
4180             MAPSET(&userinstalled, p - installed->start);
4181         }
4182     }
4183   MAPSET(&im, SYSTEMSOLVABLE);  /* in case we cleared it above */
4184   for (p = installed->start; p < installed->end; p++)
4185     if (MAPTST(&im, p))
4186       queue_push(&iq, p);
4187   for (rid = solv->jobrules; rid < solv->jobrules_end; rid++)
4188     {
4189       r = solv->rules + rid;
4190       if (r->d < 0)
4191         continue;
4192       FOR_RULELITERALS(p, jp, r)
4193         if (p > 0)
4194           queue_push(&iq, p);
4195     }
4196   /* also put directly addressed packages on the install queue
4197    * so we can mark patterns as installed */
4198   for (i = 0; i < job->count; i += 2)
4199     {
4200       how = job->elements[i];
4201       if ((how & SOLVER_JOBMASK) == SOLVER_USERINSTALLED)
4202         {
4203           what = job->elements[i + 1];
4204           select = how & SOLVER_SELECTMASK;
4205           if (select == SOLVER_SOLVABLE && pool->solvables[what].repo != installed)
4206             queue_push(&iq, what);
4207         }
4208     }
4209
4210 #ifdef CLEANDEPSDEBUG
4211   printf("ADDBACK PASS\n");
4212 #endif
4213   for (;;)
4214     {
4215       if (!iq.count)
4216         {
4217           /* supplements pass */
4218           for (ip = installed->start; ip < installed->end; ip++)
4219             {
4220               if (!MAPTST(&installedm, ip))
4221                 continue;
4222               if (MAPTST(&userinstalled, ip - installed->start))
4223                 continue;
4224               s = pool->solvables + ip;
4225               if (!s->supplements)
4226                 continue;
4227               if (MAPTST(&im, ip))
4228                 continue;
4229               supp = s->repo->idarraydata + s->supplements;
4230               while ((sup = *supp++) != 0)
4231                 if (dep_possible(solv, sup, &im))
4232                   break;
4233               if (sup)
4234                 {
4235 #ifdef CLEANDEPSDEBUG
4236                   printf("%s supplemented\n", pool_solvid2str(pool, ip));
4237 #endif
4238                   MAPSET(&im, ip);
4239                   queue_push(&iq, ip);
4240                 }
4241             }
4242           if (!iq.count)
4243             break;
4244         }
4245       ip = queue_shift(&iq);
4246       s = pool->solvables + ip;
4247 #ifdef CLEANDEPSDEBUG
4248       printf("adding back %s\n", pool_solvable2str(pool, s));
4249 #endif
4250       if (s->requires)
4251         {
4252           reqp = s->repo->idarraydata + s->requires;
4253           while ((req = *reqp++) != 0)
4254             {
4255 #ifdef ENABLE_COMPLEX_DEPS
4256               if (pool_is_complex_dep(pool, req))
4257                 {
4258                   complex_cleandeps_addback(pool, ip, req, &im, &installedm, &iq, &userinstalled);
4259                   continue;
4260                 }
4261 #endif
4262               FOR_PROVIDES(p, pp, req)
4263                 if (MAPTST(&im, p))
4264                   break;
4265               if (p)
4266                 continue;
4267               FOR_PROVIDES(p, pp, req)
4268                 {
4269                   if (MAPTST(&installedm, p))
4270                     {
4271                       if (p == ip)
4272                         continue;
4273                       if (MAPTST(&userinstalled, p - installed->start))
4274                         continue;
4275 #ifdef CLEANDEPSDEBUG
4276                       printf("%s requires %s\n", pool_solvid2str(pool, ip), pool_solvid2str(pool, p));
4277 #endif
4278                       MAPSET(&im, p);
4279                       queue_push(&iq, p);
4280                     }
4281                 }
4282             }
4283         }
4284       if (s->recommends)
4285         {
4286           reqp = s->repo->idarraydata + s->recommends;
4287           while ((req = *reqp++) != 0)
4288             {
4289 #ifdef ENABLE_COMPLEX_DEPS
4290               if (pool_is_complex_dep(pool, req))
4291                 {
4292                   complex_cleandeps_addback(pool, ip, req, &im, &installedm, &iq, &userinstalled);
4293                   continue;
4294                 }
4295 #endif
4296               FOR_PROVIDES(p, pp, req)
4297                 if (MAPTST(&im, p))
4298                   break;
4299               if (p)
4300                 continue;
4301               FOR_PROVIDES(p, pp, req)
4302                 {
4303                   if (MAPTST(&installedm, p))
4304                     {
4305                       if (p == ip)
4306                         continue;
4307                       if (MAPTST(&userinstalled, p - installed->start))
4308                         continue;
4309 #ifdef CLEANDEPSDEBUG
4310                       printf("%s recommends %s\n", pool_solvid2str(pool, ip), pool_solvid2str(pool, p));
4311 #endif
4312                       MAPSET(&im, p);
4313                       queue_push(&iq, p);
4314                     }
4315                 }
4316             }
4317         }
4318     }
4319
4320   queue_free(&iq);
4321   /* make sure the updatepkgs and mistakes are not in the cleandeps map */
4322   if (solv->cleandeps_updatepkgs)
4323     for (i = 0; i < solv->cleandeps_updatepkgs->count; i++)
4324       MAPSET(&im, solv->cleandeps_updatepkgs->elements[i]);
4325   if (solv->cleandeps_mistakes)
4326     for (i = 0; i < solv->cleandeps_mistakes->count; i++)
4327       MAPSET(&im, solv->cleandeps_mistakes->elements[i]);
4328   /* also remove original iq packages */
4329   for (i = 0; i < iqcopy.count; i++)
4330     MAPSET(&im, iqcopy.elements[i]);
4331   queue_free(&iqcopy);
4332   for (p = installed->start; p < installed->end; p++)
4333     {
4334       if (pool->solvables[p].repo != installed)
4335         continue;
4336       if (!MAPTST(&im, p))
4337         MAPSET(cleandepsmap, p - installed->start);
4338     }
4339   map_free(&im);
4340   map_free(&installedm);
4341   map_free(&userinstalled);
4342   queue_free(&xsuppq);
4343 #ifdef CLEANDEPSDEBUG
4344   printf("=== final cleandeps map:\n");
4345   for (p = installed->start; p < installed->end; p++)
4346     if (MAPTST(cleandepsmap, p - installed->start))
4347       printf("  - %s\n", pool_solvid2str(pool, p));
4348 #endif
4349 }
4350
4351
4352 struct trj_data {
4353   Queue *edges;
4354   Id *low;
4355   Id idx;
4356   Id nstack;
4357   Id firstidx;
4358 };
4359
4360 /* Tarjan's SCC algorithm, slightly modifed */
4361 static void
4362 trj_visit(struct trj_data *trj, Id node)
4363 {
4364   Id *low = trj->low;
4365   Queue *edges = trj->edges;
4366   Id nnode, myidx, stackstart;
4367   int i;
4368
4369   low[node] = myidx = trj->idx++;
4370   low[(stackstart = trj->nstack++)] = node;
4371   for (i = edges->elements[node]; (nnode = edges->elements[i]) != 0; i++)
4372     {
4373       Id l = low[nnode];
4374       if (!l)
4375         {
4376           if (!edges->elements[edges->elements[nnode]])
4377             {
4378               trj->idx++;
4379               low[nnode] = -1;
4380               continue;
4381             }
4382           trj_visit(trj, nnode);
4383           l = low[nnode];
4384         }
4385       if (l < 0)
4386         continue;
4387       if (l < trj->firstidx)
4388         {
4389           int k;
4390           for (k = l; low[low[k]] == l; k++)
4391             low[low[k]] = -1;
4392         }
4393       else if (l < low[node])
4394         low[node] = l;
4395     }
4396   if (low[node] == myidx)
4397     {
4398       if (myidx != trj->firstidx)
4399         myidx = -1;
4400       for (i = stackstart; i < trj->nstack; i++)
4401         low[low[i]] = myidx;
4402       trj->nstack = stackstart;
4403     }
4404 }
4405
4406 #ifdef ENABLE_COMPLEX_DEPS
4407 static void
4408 complex_unneeded(Pool *pool, Id ip, Id req, Queue *edges, Map *cleandepsmap, Queue *unneededq)
4409 {
4410   int i, j;
4411   Queue dq;
4412   Id p;
4413
4414   queue_init(&dq);
4415   i = pool_normalize_complex_dep(pool, req, &dq, CPLXDEPS_EXPAND);
4416   if (i == 0 || i == 1)
4417     {
4418       queue_free(&dq);
4419       return;
4420     }
4421   for (i = 0; i < dq.count; i++)
4422     {
4423       for (; (p = dq.elements[i]) != 0; i++)
4424         {
4425           if (p < 0)
4426             {
4427               if (pool->solvables[-p].repo != pool->installed)
4428                 break;
4429               continue;
4430             }
4431           if (p == ip || pool->solvables[p].repo != pool->installed || !MAPTST(cleandepsmap, p - pool->installed->start))
4432             continue;
4433           for (j = 0; j < unneededq->count; j++)
4434             if (p == unneededq->elements[j])
4435               {
4436                 if (edges->elements[edges->count - 1] != j + 1)
4437                   queue_push(edges, j + 1);
4438                 break;
4439               }
4440         }
4441       while (dq.elements[i])
4442         i++;
4443     }
4444   queue_free(&dq);
4445 }
4446 #endif
4447
4448 void
4449 solver_get_unneeded(Solver *solv, Queue *unneededq, int filtered)
4450 {
4451   Repo *installed = solv->installed;
4452   int i;
4453   Map cleandepsmap;
4454
4455   queue_empty(unneededq);
4456   if (!installed || installed->end == installed->start)
4457     return;
4458
4459   map_init(&cleandepsmap, installed->end - installed->start);
4460   solver_createcleandepsmap(solv, &cleandepsmap, 1);
4461   for (i = installed->start; i < installed->end; i++)
4462     if (MAPTST(&cleandepsmap, i - installed->start))
4463       queue_push(unneededq, i);
4464
4465   if (filtered && unneededq->count > 1)
4466     {
4467       Pool *pool = solv->pool;
4468       Queue edges;
4469       Id *nrequires;
4470       Map installedm;
4471       int j, pass, count = unneededq->count;
4472       Id *low;
4473
4474       map_init(&installedm, pool->nsolvables);
4475       for (i = installed->start; i < installed->end; i++)
4476         if (pool->solvables[i].repo == installed)
4477           MAPSET(&installedm, i);
4478
4479       nrequires = solv_calloc(count, sizeof(Id));
4480       queue_init(&edges);
4481       queue_prealloc(&edges, count * 4 + 10);   /* pre-size */
4482
4483       /*
4484        * Go through the solvables in the nodes queue and create edges for
4485        * all requires/recommends/supplements between the nodes.
4486        * The edges are stored in the edges queue, we add 1 to the node
4487        * index so that nodes in the edges queue are != 0 and we can
4488        * terminate the edge list with 0.
4489        * Thus for node element 5, the edges are stored starting at
4490        * edges.elements[6] and are 0-terminated.
4491        */
4492       /* leave first element zero to make things easier */
4493       /* also add trailing zero */
4494       queue_insertn(&edges, 0, 1 + count + 1, 0);
4495
4496       /* first requires and recommends */
4497       for (i = 0; i < count; i++)
4498         {
4499           Solvable *s = pool->solvables + unneededq->elements[i];
4500           int oldcount = edges.count;
4501           edges.elements[i + 1] = oldcount;
4502           for (pass = 0; pass < 2; pass++)
4503             {
4504               unsigned int off = pass == 0 ? s->requires : s->recommends;
4505               Id p, pp, dep, *dp;
4506               if (off)
4507                 for (dp = s->repo->idarraydata + off; (dep = *dp) != 0; dp++)
4508                   {
4509 #ifdef ENABLE_COMPLEX_DEPS
4510                     if (pool_is_complex_dep(pool, dep))
4511                       {
4512                         complex_unneeded(pool, s - pool->solvables, dep, &edges, &cleandepsmap, unneededq);
4513                         continue;
4514                       }
4515 #endif
4516                     FOR_PROVIDES(p, pp, dep)
4517                       {
4518                         Solvable *sp = pool->solvables + p;
4519                         if (s == sp || sp->repo != installed || !MAPTST(&cleandepsmap, p - installed->start))
4520                           continue;
4521                         for (j = 0; j < count; j++)
4522                           if (p == unneededq->elements[j])
4523                             {
4524                               if (edges.elements[edges.count - 1] != j + 1)
4525                                 queue_push(&edges, j + 1);
4526                             }
4527                       }
4528                   }
4529               if (pass == 0)
4530                 nrequires[i] = edges.count - oldcount;
4531             }
4532           queue_push(&edges, 0);
4533         }
4534 #if 0
4535       printf("requires + recommends\n");
4536       for (i = 0; i < count; i++)
4537         {
4538           int j;
4539           printf("  %s (%d requires):\n", pool_solvid2str(pool, unneededq->elements[i]), nrequires[i]);
4540           for (j = edges.elements[i + 1]; edges.elements[j]; j++)
4541             printf("    - %s\n", pool_solvid2str(pool, unneededq->elements[edges.elements[j] - 1]));
4542         }
4543 #endif
4544
4545       /* then add supplements */
4546       for (i = 0; i < count; i++)
4547         {
4548           Solvable *s = pool->solvables + unneededq->elements[i];
4549           if (s->supplements)
4550             {
4551               Id *dp;
4552               int k;
4553               for (dp = s->repo->idarraydata + s->supplements; *dp; dp++)
4554                 if (dep_possible(solv, *dp, &installedm))
4555                   {
4556                     Queue iq;
4557                     Id iqbuf[16];
4558                     queue_init_buffer(&iq, iqbuf, sizeof(iqbuf)/sizeof(*iqbuf));
4559                     dep_pkgcheck(solv, *dp, 0, &iq);
4560                     for (k = 0; k < iq.count; k++)
4561                       {
4562                         Id p = iq.elements[k];
4563                         Solvable *sp = pool->solvables + p;
4564                         if (p == unneededq->elements[i] || sp->repo != installed || !MAPTST(&cleandepsmap, p - installed->start))
4565                           continue;
4566                         for (j = 0; j < count; j++)
4567                           if (p == unneededq->elements[j])
4568                             break;
4569                         /* now add edge from j + 1 to i + 1 */
4570                         queue_insert(&edges, edges.elements[j + 1] + nrequires[j], i + 1);
4571                         /* addapt following edge pointers */
4572                         for (j = j + 2; j < count + 1; j++)
4573                           edges.elements[j]++;
4574                       }
4575                     queue_free(&iq);
4576                   }
4577             }
4578         }
4579 #if 0
4580       /* print result */
4581       printf("+ supplements\n");
4582       for (i = 0; i < count; i++)
4583         {
4584           int j;
4585           printf("  %s (%d requires):\n", pool_solvid2str(pool, unneededq->elements[i]), nrequires[i]);
4586           for (j = edges.elements[i + 1]; edges.elements[j]; j++)
4587             printf("    - %s\n", pool_solvid2str(pool, unneededq->elements[edges.elements[j] - 1]));
4588         }
4589 #endif
4590       map_free(&installedm);
4591
4592       /* now run SCC algo two times, first with requires+recommends+supplements,
4593        * then again without the requires. We run it the second time to get rid
4594        * of packages that got dragged in via recommends/supplements */
4595       /*
4596        * low will contain the result of the SCC search.
4597        * it must be of at least size 2 * (count + 1) and
4598        * must be zero initialized.
4599        * The layout is:
4600        *    0  low low ... low stack stack ...stack 0
4601        *            count              count
4602        */
4603       low = solv_calloc(count + 1, 2 * sizeof(Id));
4604       for (pass = 0; pass < 2; pass++)
4605         {
4606           struct trj_data trj;
4607           if (pass)
4608             {
4609               memset(low, 0, (count + 1) * (2 * sizeof(Id)));
4610               for (i = 0; i < count; i++)
4611                 {
4612                   edges.elements[i + 1] += nrequires[i];
4613                   if (!unneededq->elements[i])
4614                     low[i + 1] = -1;    /* ignore this node */
4615                 }
4616             }
4617           trj.edges = &edges;
4618           trj.low = low;
4619           trj.idx = count + 1;  /* stack starts here */
4620           for (i = 1; i <= count; i++)
4621             {
4622               if (low[i])
4623                 continue;
4624               if (edges.elements[edges.elements[i]])
4625                 {
4626                   trj.firstidx = trj.nstack = trj.idx;
4627                   trj_visit(&trj, i);
4628                 }
4629               else
4630                 {
4631                   Id myidx = trj.idx++;
4632                   low[i] = myidx;
4633                   low[myidx] = i;
4634                 }
4635             }
4636           /* prune packages */
4637           for (i = 0; i < count; i++)
4638             if (low[i + 1] <= 0)
4639               unneededq->elements[i] = 0;
4640         }
4641       solv_free(low);
4642       solv_free(nrequires);
4643       queue_free(&edges);
4644
4645       /* finally remove all pruned entries from unneededq */
4646       for (i = j = 0; i < count; i++)
4647         if (unneededq->elements[i])
4648           unneededq->elements[j++] = unneededq->elements[i];
4649       queue_truncate(unneededq, j);
4650     }
4651   map_free(&cleandepsmap);
4652 }
4653
4654
4655 void
4656 solver_breakorphans(Solver *solv)
4657 {
4658   Pool *pool = solv->pool;
4659   Repo *installed = solv->installed;
4660   int i, rid;
4661   Map m;
4662
4663   if (!installed || solv->droporphanedmap_all)
4664     return;
4665   solv->brokenorphanrules = solv_calloc(1, sizeof(Queue));
4666   queue_init(solv->brokenorphanrules);
4667   map_init(&m, installed->end - installed->start);
4668   for (i = 0; i < solv->orphaned.count; i++)
4669     {
4670       Id p = solv->orphaned.elements[i];
4671       if (pool->solvables[p].repo != installed)
4672         continue;
4673       if (solv->droporphanedmap.size && MAPTST(&solv->droporphanedmap, p - installed->start))
4674         continue;
4675       MAPSET(&m, p - installed->start);
4676     }
4677   for (rid = 1; rid < solv->pkgrules_end ; rid++)
4678     {
4679       Id p, *dp;
4680       Rule *r = solv->rules + rid;
4681       /* ignore non-deps and simple conflicts */
4682       if (r->p >= 0 || ((r->d == 0 || r->d == -1) && r->w2 < 0))
4683         continue;
4684       p = -r->p;
4685       if (p < installed->start || p >= installed->end || !MAPTST(&m, p - installed->start))
4686         {
4687           /* need to check other literals */
4688           if (r->d == 0 || r->d == -1)
4689             continue;
4690           for (dp = pool->whatprovidesdata + (r->d < 0 ? -r->d - 1 : r->d); *dp < 0; dp++)
4691             {
4692               p = -*dp;
4693               if (p >= installed->start && p < installed->end && MAPTST(&m, p - installed->start))
4694                 break;
4695             }
4696           if (*dp >= 0)
4697             continue;
4698         }
4699       /* ok, disable this rule */
4700       queue_push(solv->brokenorphanrules, rid);
4701       if (r->d >= 0)
4702         solver_disablerule(solv, r);
4703     }
4704   map_free(&m);
4705   if (!solv->brokenorphanrules->count)
4706     {
4707       queue_free(solv->brokenorphanrules);
4708       solv->brokenorphanrules = solv_free(solv->brokenorphanrules);
4709     }
4710 }
4711
4712 void
4713 solver_check_brokenorphanrules(Solver *solv, Queue *dq)
4714 {
4715   Pool *pool = solv->pool;
4716   int i;
4717   Id l, pp;
4718
4719   queue_empty(dq);
4720   if (!solv->brokenorphanrules)
4721     return;
4722   for (i = 0; i < solv->brokenorphanrules->count; i++)
4723     {
4724       int rid = solv->brokenorphanrules->elements[i];
4725       Rule *r = solv->rules + rid;
4726       FOR_RULELITERALS(l, pp, r)
4727         {
4728           if (l < 0)
4729             {
4730               if (solv->decisionmap[-l] <= 0)
4731                 break;
4732             }
4733           else
4734             {
4735               if (solv->decisionmap[l] > 0 && pool->solvables[l].repo != solv->installed)
4736                 break;
4737             }
4738         }
4739       if (l)
4740         continue;
4741       FOR_RULELITERALS(l, pp, r)
4742         if (l > 0 && solv->decisionmap[l] == 0 && pool->solvables[l].repo != solv->installed)
4743           queue_pushunique(dq, l);
4744     }
4745 }
4746