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