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