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