src/rules.c

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