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