src/rules.c

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