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