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