src/rules.c

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