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