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 "bitmap.h"
  22 #include "pool.h"
  23 #include "poolarch.h"
  24 #include "util.h"
  25 #include "evr.h"
  26 #include "policy.h"
  27 #include "solverdebug.h"
  28
  29 #define RULES_BLOCK 63
  30
  31 static void addrpmruleinfo(Solver *solv, Id p, Id d, int type, Id dep);
  32 static void solver_createcleandepsmap(Solver *solv);
  33
  34 /*-------------------------------------------------------------------
  35  * Check if dependency is possible
  36  *
  37  * mirrors solver_dep_fulfilled but uses map m instead of the decisionmap
  38  * used in solver_addrpmrulesforweak and solver_createcleandepsmap
  39  */
  40
  41 static inline int
  42 dep_possible(Solver *solv, Id dep, Map *m)
  43 {
  44   Pool *pool = solv->pool;
  45   Id p, pp;
  46
  47   if (ISRELDEP(dep))
  48     {
  49       Reldep *rd = GETRELDEP(pool, dep);
  50       if (rd->flags >= 8)
  51         {
  52           if (rd->flags == REL_AND)
  53             {
  54               if (!dep_possible(solv, rd->name, m))
  55                 return 0;
  56               return dep_possible(solv, rd->evr, m);
  57             }
  58           if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
  59             return solver_splitprovides(solv, rd->evr);
  60           if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
  61             return solver_dep_installed(solv, rd->evr);
  62         }
  63     }
  64   FOR_PROVIDES(p, pp, dep)
  65     {
  66       if (MAPTST(m, p))
  67         return 1;
  68     }
  69   return 0;
  70 }
  71
  72 /********************************************************************
  73  *
  74  * Rule handling
  75  *
  76  * - unify rules, remove duplicates
  77  */
  78
  79 /*-------------------------------------------------------------------
  80  *
  81  * compare rules for unification sort
  82  *
  83  */
  84
  85 static int
  86 unifyrules_sortcmp(const void *ap, const void *bp, void *dp)
  87 {
  88   Pool *pool = dp;
  89   Rule *a = (Rule *)ap;
  90   Rule *b = (Rule *)bp;
  91   Id *ad, *bd;
  92   int x;
  93
  94   x = a->p - b->p;
  95   if (x)
  96     return x;                          /* p differs */
  97
  98   /* identical p */
  99   if (a->d == 0 && b->d == 0)
 100     return a->w2 - b->w2;              /* assertion: return w2 diff */
 101
 102   if (a->d == 0)                       /* a is assertion, b not */
 103     {
 104       x = a->w2 - pool->whatprovidesdata[b->d];
 105       return x ? x : -1;
 106     }
 107
 108   if (b->d == 0)                       /* b is assertion, a not */
 109     {
 110       x = pool->whatprovidesdata[a->d] - b->w2;
 111       return x ? x : 1;
 112     }
 113
 114   /* compare whatprovidesdata */
 115   ad = pool->whatprovidesdata + a->d;
 116   bd = pool->whatprovidesdata + b->d;
 117   while (*bd)
 118     if ((x = *ad++ - *bd++) != 0)
 119       return x;
 120   return *ad;
 121 }
 122
 123 int
 124 solver_samerule(Solver *solv, Rule *r1, Rule *r2)
 125 {
 126   return unifyrules_sortcmp(r1, r2, solv->pool);
 127 }
 128
 129
 130 /*-------------------------------------------------------------------
 131  *
 132  * unify rules
 133  * go over all rules and remove duplicates
 134  */
 135
 136 void
 137 solver_unifyrules(Solver *solv)
 138 {
 139   Pool *pool = solv->pool;
 140   int i, j;
 141   Rule *ir, *jr;
 142
 143   if (solv->nrules <= 2)               /* nothing to unify */
 144     return;
 145
 146   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- unifyrules -----\n");
 147
 148   /* sort rules first */
 149   sat_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(SAT_DEBUG_STATS, "pruned rules from %d to %d\n", solv->nrules, j);
 167
 168   /* adapt rule buffer */
 169   solv->nrules = j;
 170   solv->rules = sat_extend_resize(solv->rules, solv->nrules, sizeof(Rule), RULES_BLOCK);
 171
 172   /*
 173    * debug: log rule statistics
 174    */
 175   IF_POOLDEBUG (SAT_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(SAT_DEBUG_STATS, "  binary: %d\n", binr);
 195       POOL_DEBUG(SAT_DEBUG_STATS, "  normal: %d, %d literals\n", solv->nrules - 1 - binr, lits);
 196     }
 197   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- unifyrules end -----\n");
 198 }
 199
 200 #if 0
 201
 202 /*
 203  * hash rule
 204  */
 205
 206 static Hashval
 207 hashrule(Solver *solv, Id p, Id d, int n)
 208 {
 209   unsigned int x = (unsigned int)p;
 210   int *dp;
 211
 212   if (n <= 1)
 213     return (x * 37) ^ (unsigned int)d;
 214   dp = solv->pool->whatprovidesdata + d;
 215   while (*dp)
 216     x = (x * 37) ^ (unsigned int)*dp++;
 217   return x;
 218 }
 219 #endif
 220
 221
 222 /*-------------------------------------------------------------------
 223  *
 224  */
 225
 226 /*
 227  * add rule
 228  *  p = direct literal; always < 0 for installed rpm rules
 229  *  d, if < 0 direct literal, if > 0 offset into whatprovides, if == 0 rule is assertion (look at p only)
 230  *
 231  *
 232  * A requires b, b provided by B1,B2,B3 => (-A|B1|B2|B3)
 233  *
 234  * p < 0 : pkg id of A
 235  * d > 0 : Offset in whatprovidesdata (list of providers of b)
 236  *
 237  * A conflicts b, b provided by B1,B2,B3 => (-A|-B1), (-A|-B2), (-A|-B3)
 238  * p < 0 : pkg id of A
 239  * d < 0 : Id of solvable (e.g. B1)
 240  *
 241  * d == 0: unary rule, assertion => (A) or (-A)
 242  *
 243  *   Install:    p > 0, d = 0   (A)             user requested install
 244  *   Remove:     p < 0, d = 0   (-A)            user requested remove (also: uninstallable)
 245  *   Requires:   p < 0, d > 0   (-A|B1|B2|...)  d: <list of providers for requirement of p>
 246  *   Updates:    p > 0, d > 0   (A|B1|B2|...)   d: <list of updates for solvable p>
 247  *   Conflicts:  p < 0, d < 0   (-A|-B)         either p (conflict issuer) or d (conflict provider) (binary rule)
 248  *                                              also used for obsoletes
 249  *   ?:          p > 0, d < 0   (A|-B)
 250  *   No-op ?:    p = 0, d = 0   (null)          (used as policy rule placeholder)
 251  *
 252  *   resulting watches:
 253  *   ------------------
 254  *   Direct assertion (no watch needed) --> d = 0, w1 = p, w2 = 0
 255  *   Binary rule: p = first literal, d = 0, w2 = second literal, w1 = p
 256  *   every other : w1 = p, w2 = whatprovidesdata[d];
 257  *   Disabled rule: w1 = 0
 258  *
 259  *   always returns a rule for non-rpm rules
 260  */
 261
 262 Rule *
 263 solver_addrule(Solver *solv, Id p, Id d)
 264 {
 265   Pool *pool = solv->pool;
 266   Rule *r = 0;
 267   Id *dp = 0;
 268
 269   int n = 0;                           /* number of literals in rule - 1
 270                                           0 = direct assertion (single literal)
 271                                           1 = binary rule
 272                                           >1 =
 273                                         */
 274
 275   /* it often happenes that requires lead to adding the same rpm rule
 276    * multiple times, so we prune those duplicates right away to make
 277    * the work for unifyrules a bit easier */
 278
 279   if (!solv->rpmrules_end)              /* we add rpm rules */
 280     {
 281       r = solv->rules + solv->nrules - 1;       /* get the last added rule */
 282       if (r->p == p && r->d == d && (d != 0 || !r->w2))
 283         return r;
 284     }
 285
 286     /*
 287      * compute number of literals (n) in rule
 288      */
 289
 290   if (d < 0)
 291     {
 292       /* always a binary rule */
 293       if (p == d)
 294         return 0;                      /* ignore self conflict */
 295       n = 1;
 296     }
 297   else if (d > 0)
 298     {
 299       for (dp = pool->whatprovidesdata + d; *dp; dp++, n++)
 300         if (*dp == -p)
 301           return 0;                     /* rule is self-fulfilling */
 302
 303       if (n == 1)                       /* convert to binary rule */
 304         d = dp[-1];
 305     }
 306
 307   if (n == 1 && p > d && !solv->rpmrules_end)
 308     {
 309       /* smallest literal first so we can find dups */
 310       n = p; p = d; d = n;             /* p <-> d */
 311       n = 1;                           /* re-set n, was used as temp var */
 312     }
 313
 314   /*
 315    * check for duplicate
 316    */
 317
 318   /* check if the last added rule (r) is exactly the same as what we're looking for. */
 319   if (r && n == 1 && !r->d && r->p == p && r->w2 == d)
 320     return r;  /* binary rule */
 321
 322     /* have n-ary rule with same first literal, check other literals */
 323   if (r && n > 1 && r->d && r->p == p)
 324     {
 325       /* Rule where d is an offset in whatprovidesdata */
 326       Id *dp2;
 327       if (d == r->d)
 328         return r;
 329       dp2 = pool->whatprovidesdata + r->d;
 330       for (dp = pool->whatprovidesdata + d; *dp; dp++, dp2++)
 331         if (*dp != *dp2)
 332           break;
 333       if (*dp == *dp2)
 334         return r;
 335    }
 336
 337   /*
 338    * allocate new rule
 339    */
 340
 341   /* extend rule buffer */
 342   solv->rules = sat_extend(solv->rules, solv->nrules, 1, sizeof(Rule), RULES_BLOCK);
 343   r = solv->rules + solv->nrules++;    /* point to rule space */
 344
 345     /*
 346      * r = new rule
 347      */
 348
 349   r->p = p;
 350   if (n == 0)
 351     {
 352       /* direct assertion, no watch needed */
 353       r->d = 0;
 354       r->w1 = p;
 355       r->w2 = 0;
 356     }
 357   else if (n == 1)
 358     {
 359       /* binary rule */
 360       r->d = 0;
 361       r->w1 = p;
 362       r->w2 = d;
 363     }
 364   else
 365     {
 366       r->d = d;
 367       r->w1 = p;
 368       r->w2 = pool->whatprovidesdata[d];
 369     }
 370   r->n1 = 0;
 371   r->n2 = 0;
 372
 373   IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION)
 374     {
 375       POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "  Add rule: ");
 376       solver_printrule(solv, SAT_DEBUG_RULE_CREATION, r);
 377     }
 378
 379   return r;
 380 }
 381
 382
 383 /******************************************************************************
 384  ***
 385  *** rpm rule part: create rules representing the package dependencies
 386  ***
 387  ***/
 388
 389 /*
 390  *  special multiversion patch conflict handling:
 391  *  a patch conflict is also satisfied if some other
 392  *  version with the same name/arch that doesn't conflict
 393  *  gets installed. The generated rule is thus:
 394  *  -patch|-cpack|opack1|opack2|...
 395  */
 396 static Id
 397 makemultiversionconflict(Solver *solv, Id n, Id con)
 398 {
 399   Pool *pool = solv->pool;
 400   Solvable *s, *sn;
 401   Queue q;
 402   Id p, pp, qbuf[64];
 403
 404   sn = pool->solvables + n;
 405   queue_init_buffer(&q, qbuf, sizeof(qbuf)/sizeof(*qbuf));
 406   queue_push(&q, -n);
 407   FOR_PROVIDES(p, pp, sn->name)
 408     {
 409       s = pool->solvables + p;
 410       if (s->name != sn->name || s->arch != sn->arch)
 411         continue;
 412       if (!MAPTST(&solv->noobsoletes, p))
 413         continue;
 414       if (pool_match_nevr(pool, pool->solvables + p, con))
 415         continue;
 416       /* here we have a multiversion solvable that doesn't conflict */
 417       /* thus we're not in conflict if it is installed */
 418       queue_push(&q, p);
 419     }
 420   if (q.count == 1)
 421     return -n;  /* no other package found, generate normal conflict */
 422   return pool_queuetowhatprovides(pool, &q);
 423 }
 424
 425 static inline void
 426 addrpmrule(Solver *solv, Id p, Id d, int type, Id dep)
 427 {
 428   if (!solv->ruleinfoq)
 429     solver_addrule(solv, p, d);
 430   else
 431     addrpmruleinfo(solv, p, d, type, dep);
 432 }
 433
 434 /*-------------------------------------------------------------------
 435  *
 436  * add (install) rules for solvable
 437  *
 438  * s: Solvable for which to add rules
 439  * m: m[s] = 1 for solvables which have rules, prevent rule duplication
 440  *
 441  * Algorithm: 'visit all nodes of a graph'. The graph nodes are
 442  *  solvables, the edges their dependencies.
 443  *  Starting from an installed solvable, this will create all rules
 444  *  representing the graph created by the solvables dependencies.
 445  *
 446  * for unfulfilled requirements, conflicts, obsoletes,....
 447  * add a negative assertion for solvables that are not installable
 448  *
 449  * It will also create rules for all solvables referenced by 's'
 450  *  i.e. descend to all providers of requirements of 's'
 451  *
 452  */
 453
 454 void
 455 solver_addrpmrulesforsolvable(Solver *solv, Solvable *s, Map *m)
 456 {
 457   Pool *pool = solv->pool;
 458   Repo *installed = solv->installed;
 459
 460   /* 'work' queue. keeps Ids of solvables we still have to work on.
 461      And buffer for it. */
 462   Queue workq;
 463   Id workqbuf[64];
 464
 465   int i;
 466     /* if to add rules for broken deps ('rpm -V' functionality)
 467      * 0 = yes, 1 = no
 468      */
 469   int dontfix;
 470     /* Id var and pointer for each dependency
 471      * (not used in parallel)
 472      */
 473   Id req, *reqp;
 474   Id con, *conp;
 475   Id obs, *obsp;
 476   Id rec, *recp;
 477   Id sug, *sugp;
 478   Id p, pp;             /* whatprovides loops */
 479   Id *dp;               /* ptr to 'whatprovides' */
 480   Id n;                 /* Id for current solvable 's' */
 481
 482   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforsolvable -----\n");
 483
 484   queue_init_buffer(&workq, workqbuf, sizeof(workqbuf)/sizeof(*workqbuf));
 485   queue_push(&workq, s - pool->solvables);      /* push solvable Id to work queue */
 486
 487   /* loop until there's no more work left */
 488   while (workq.count)
 489     {
 490       /*
 491        * n: Id of solvable
 492        * s: Pointer to solvable
 493        */
 494
 495       n = queue_shift(&workq);          /* 'pop' next solvable to work on from queue */
 496       if (m)
 497         {
 498           if (MAPTST(m, n))             /* continue if already visited */
 499             continue;
 500           MAPSET(m, n);                 /* mark as visited */
 501         }
 502
 503       s = pool->solvables + n;          /* s = Solvable in question */
 504
 505       dontfix = 0;
 506       if (installed                     /* Installed system available */
 507           && s->repo == installed       /* solvable is installed */
 508           && !solv->fixmap_all          /* NOT repair errors in rpm dependency graph */
 509           && !(solv->fixmap.size && MAPTST(&solv->fixmap, n - installed->start)))
 510         {
 511           dontfix = 1;                  /* dont care about broken rpm deps */
 512         }
 513
 514       if (!dontfix
 515           && s->arch != ARCH_SRC
 516           && s->arch != ARCH_NOSRC
 517           && !pool_installable(pool, s))
 518         {
 519           POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "package %s [%d] is not installable\n", pool_solvable2str(pool, s), (Id)(s - pool->solvables));
 520           addrpmrule(solv, -n, 0, SOLVER_RULE_RPM_NOT_INSTALLABLE, 0);
 521         }
 522
 523       /* yet another SUSE hack, sigh */
 524       if (pool->nscallback && !strncmp("product:", pool_id2str(pool, s->name), 8))
 525         {
 526           Id buddy = pool->nscallback(pool, pool->nscallbackdata, NAMESPACE_PRODUCTBUDDY, n);
 527           if (buddy > 0 && buddy != SYSTEMSOLVABLE && buddy != n && buddy < pool->nsolvables)
 528             {
 529               addrpmrule(solv, n, -buddy, SOLVER_RULE_RPM_PACKAGE_REQUIRES, solvable_selfprovidedep(pool->solvables + n));
 530               addrpmrule(solv, buddy, -n, SOLVER_RULE_RPM_PACKAGE_REQUIRES, solvable_selfprovidedep(pool->solvables + buddy));
 531               if (m && !MAPTST(m, buddy))
 532                 queue_push(&workq, buddy);
 533             }
 534         }
 535
 536       /*-----------------------------------------
 537        * check requires of s
 538        */
 539
 540       if (s->requires)
 541         {
 542           reqp = s->repo->idarraydata + s->requires;
 543           while ((req = *reqp++) != 0)            /* go through all requires */
 544             {
 545               if (req == SOLVABLE_PREREQMARKER)   /* skip the marker */
 546                 continue;
 547
 548               /* find list of solvables providing 'req' */
 549               dp = pool_whatprovides_ptr(pool, req);
 550
 551               if (*dp == SYSTEMSOLVABLE)          /* always installed */
 552                 continue;
 553
 554               if (dontfix)
 555                 {
 556                   /* the strategy here is to not insist on dependencies
 557                    * that are already broken. so if we find one provider
 558                    * that was already installed, we know that the
 559                    * dependency was not broken before so we enforce it */
 560
 561                   /* check if any of the providers for 'req' is installed */
 562                   for (i = 0; (p = dp[i]) != 0; i++)
 563                     {
 564                       if (pool->solvables[p].repo == installed)
 565                         break;          /* provider was installed */
 566                     }
 567                   /* didn't find an installed provider: previously broken dependency */
 568                   if (!p)
 569                     {
 570                       POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "ignoring broken requires %s of installed package %s\n", pool_dep2str(pool, req), pool_solvable2str(pool, s));
 571                       continue;
 572                     }
 573                 }
 574
 575               if (!*dp)
 576                 {
 577                   /* nothing provides req! */
 578                   POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "package %s [%d] is not installable (%s)\n", pool_solvable2str(pool, s), (Id)(s - pool->solvables), pool_dep2str(pool, req));
 579                   addrpmrule(solv, -n, 0, SOLVER_RULE_RPM_NOTHING_PROVIDES_DEP, req);
 580                   continue;
 581                 }
 582
 583               IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION)
 584                 {
 585                   POOL_DEBUG(SAT_DEBUG_RULE_CREATION,"  %s requires %s\n", pool_solvable2str(pool, s), pool_dep2str(pool, req));
 586                   for (i = 0; dp[i]; i++)
 587                     POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "   provided by %s\n", pool_solvid2str(pool, dp[i]));
 588                 }
 589
 590               /* add 'requires' dependency */
 591               /* rule: (-requestor|provider1|provider2|...|providerN) */
 592               addrpmrule(solv, -n, dp - pool->whatprovidesdata, SOLVER_RULE_RPM_PACKAGE_REQUIRES, req);
 593
 594               /* descend the dependency tree
 595                  push all non-visited providers on the work queue */
 596               if (m)
 597                 {
 598                   for (; *dp; dp++)
 599                     {
 600                       if (!MAPTST(m, *dp))
 601                         queue_push(&workq, *dp);
 602                     }
 603                 }
 604
 605             } /* while, requirements of n */
 606
 607         } /* if, requirements */
 608
 609       /* that's all we check for src packages */
 610       if (s->arch == ARCH_SRC || s->arch == ARCH_NOSRC)
 611         continue;
 612
 613       /*-----------------------------------------
 614        * check conflicts of s
 615        */
 616
 617       if (s->conflicts)
 618         {
 619           int ispatch = 0;
 620
 621           /* we treat conflicts in patches a bit differen:
 622            * - nevr matching
 623            * - multiversion handling
 624            * XXX: we should really handle this different, looking
 625            * at the name is a bad hack
 626            */
 627           if (!strncmp("patch:", pool_id2str(pool, s->name), 6))
 628             ispatch = 1;
 629           conp = s->repo->idarraydata + s->conflicts;
 630           /* foreach conflicts of 's' */
 631           while ((con = *conp++) != 0)
 632             {
 633               /* foreach providers of a conflict of 's' */
 634               FOR_PROVIDES(p, pp, con)
 635                 {
 636                   if (ispatch && !pool_match_nevr(pool, pool->solvables + p, con))
 637                     continue;
 638                   /* dontfix: dont care about conflicts with already installed packs */
 639                   if (dontfix && pool->solvables[p].repo == installed)
 640                     continue;
 641                   /* p == n: self conflict */
 642                   if (p == n && !pool->allowselfconflicts)
 643                     {
 644                       if (ISRELDEP(con))
 645                         {
 646                           Reldep *rd = GETRELDEP(pool, con);
 647                           if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_OTHERPROVIDERS)
 648                             continue;
 649                         }
 650                       p = 0;    /* make it a negative assertion, aka 'uninstallable' */
 651                     }
 652                   if (p && ispatch && solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p) && ISRELDEP(con))
 653                     {
 654                       /* our patch conflicts with a noobsoletes (aka multiversion) package */
 655                       p = -makemultiversionconflict(solv, p, con);
 656                     }
 657                  /* rule: -n|-p: either solvable _or_ provider of conflict */
 658                   addrpmrule(solv, -n, -p, p ? SOLVER_RULE_RPM_PACKAGE_CONFLICT : SOLVER_RULE_RPM_SELF_CONFLICT, con);
 659                 }
 660             }
 661         }
 662
 663       /*-----------------------------------------
 664        * check obsoletes and implicit obsoletes of a package
 665        * if ignoreinstalledsobsoletes is not set, we're also checking
 666        * obsoletes of installed packages (like newer rpm versions)
 667        */
 668       if ((!installed || s->repo != installed) || !pool->noinstalledobsoletes)
 669         {
 670           int noobs = solv->noobsoletes.size && MAPTST(&solv->noobsoletes, n);
 671           int isinstalled = (installed && s->repo == installed);
 672           if (s->obsoletes && !noobs)
 673             {
 674               obsp = s->repo->idarraydata + s->obsoletes;
 675               /* foreach obsoletes */
 676               while ((obs = *obsp++) != 0)
 677                 {
 678                   /* foreach provider of an obsoletes of 's' */
 679                   FOR_PROVIDES(p, pp, obs)
 680                     {
 681                       Solvable *ps = pool->solvables + p;
 682                       if (p == n)
 683                         continue;
 684                       if (isinstalled && dontfix && ps->repo == installed)
 685                         continue;       /* don't repair installed/installed problems */
 686                       if (!pool->obsoleteusesprovides /* obsoletes are matched names, not provides */
 687                           && !pool_match_nevr(pool, ps, obs))
 688                         continue;
 689                       if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
 690                         continue;
 691                       if (!isinstalled)
 692                         addrpmrule(solv, -n, -p, SOLVER_RULE_RPM_PACKAGE_OBSOLETES, obs);
 693                       else
 694                         addrpmrule(solv, -n, -p, SOLVER_RULE_RPM_INSTALLEDPKG_OBSOLETES, obs);
 695                     }
 696                 }
 697             }
 698           /* check implicit obsoletes
 699            * for installed packages we only need to check installed/installed problems (and
 700            * only when dontfix is not set), as the others are picked up when looking at the
 701            * uninstalled package.
 702            */
 703           if (!isinstalled || !dontfix)
 704             {
 705               FOR_PROVIDES(p, pp, s->name)
 706                 {
 707                   Solvable *ps = pool->solvables + p;
 708                   if (p == n)
 709                     continue;
 710                   if (isinstalled && ps->repo != installed)
 711                     continue;
 712                   /* we still obsolete packages with same nevra, like rpm does */
 713                   /* (actually, rpm mixes those packages. yuck...) */
 714                   if (noobs && (s->name != ps->name || s->evr != ps->evr || s->arch != ps->arch))
 715                     continue;
 716                   if (!pool->implicitobsoleteusesprovides && s->name != ps->name)
 717                     continue;
 718                   if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
 719                     continue;
 720                   if (s->name == ps->name)
 721                     addrpmrule(solv, -n, -p, SOLVER_RULE_RPM_SAME_NAME, 0);
 722                   else
 723                     addrpmrule(solv, -n, -p, SOLVER_RULE_RPM_IMPLICIT_OBSOLETES, s->name);
 724                 }
 725             }
 726         }
 727
 728       /*-----------------------------------------
 729        * add recommends to the work queue
 730        */
 731       if (s->recommends && m)
 732         {
 733           recp = s->repo->idarraydata + s->recommends;
 734           while ((rec = *recp++) != 0)
 735             {
 736               FOR_PROVIDES(p, pp, rec)
 737                 if (!MAPTST(m, p))
 738                   queue_push(&workq, p);
 739             }
 740         }
 741       if (s->suggests && m)
 742         {
 743           sugp = s->repo->idarraydata + s->suggests;
 744           while ((sug = *sugp++) != 0)
 745             {
 746               FOR_PROVIDES(p, pp, sug)
 747                 if (!MAPTST(m, p))
 748                   queue_push(&workq, p);
 749             }
 750         }
 751     }
 752   queue_free(&workq);
 753   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforsolvable end -----\n");
 754 }
 755
 756
 757 /*-------------------------------------------------------------------
 758  *
 759  * Add rules for packages possibly selected in by weak dependencies
 760  *
 761  * m: already added solvables
 762  */
 763
 764 void
 765 solver_addrpmrulesforweak(Solver *solv, Map *m)
 766 {
 767   Pool *pool = solv->pool;
 768   Solvable *s;
 769   Id sup, *supp;
 770   int i, n;
 771
 772   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforweak -----\n");
 773   /* foreach solvable in pool */
 774   for (i = n = 1; n < pool->nsolvables; i++, n++)
 775     {
 776       if (i == pool->nsolvables)                /* wrap i */
 777         i = 1;
 778       if (MAPTST(m, i))                         /* already added that one */
 779         continue;
 780
 781       s = pool->solvables + i;
 782       if (!pool_installable(pool, s))           /* only look at installable ones */
 783         continue;
 784
 785       sup = 0;
 786       if (s->supplements)
 787         {
 788           /* find possible supplements */
 789           supp = s->repo->idarraydata + s->supplements;
 790           while ((sup = *supp++) != 0)
 791             if (dep_possible(solv, sup, m))
 792               break;
 793         }
 794
 795       /* if nothing found, check for enhances */
 796       if (!sup && s->enhances)
 797         {
 798           supp = s->repo->idarraydata + s->enhances;
 799           while ((sup = *supp++) != 0)
 800             if (dep_possible(solv, sup, m))
 801               break;
 802         }
 803       /* if nothing found, goto next solvables */
 804       if (!sup)
 805         continue;
 806       solver_addrpmrulesforsolvable(solv, s, m);
 807       n = 0;                    /* check all solvables again because we added solvables to m */
 808     }
 809   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforweak end -----\n");
 810 }
 811
 812
 813 /*-------------------------------------------------------------------
 814  *
 815  * add package rules for possible updates
 816  *
 817  * s: solvable
 818  * m: map of already visited solvables
 819  * allow_all: 0 = dont allow downgrades, 1 = allow all candidates
 820  */
 821
 822 void
 823 solver_addrpmrulesforupdaters(Solver *solv, Solvable *s, Map *m, int allow_all)
 824 {
 825   Pool *pool = solv->pool;
 826   int i;
 827     /* queue and buffer for it */
 828   Queue qs;
 829   Id qsbuf[64];
 830
 831   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforupdaters -----\n");
 832
 833   queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
 834     /* find update candidates for 's' */
 835   policy_findupdatepackages(solv, s, &qs, allow_all);
 836     /* add rule for 's' if not already done */
 837   if (!MAPTST(m, s - pool->solvables))
 838     solver_addrpmrulesforsolvable(solv, s, m);
 839     /* foreach update candidate, add rule if not already done */
 840   for (i = 0; i < qs.count; i++)
 841     if (!MAPTST(m, qs.elements[i]))
 842       solver_addrpmrulesforsolvable(solv, pool->solvables + qs.elements[i], m);
 843   queue_free(&qs);
 844
 845   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforupdaters -----\n");
 846 }
 847
 848
 849 /***********************************************************************
 850  ***
 851  ***  Update/Feature rule part
 852  ***
 853  ***  Those rules make sure an installed package isn't silently deleted
 854  ***
 855  ***/
 856
 857 static Id
 858 finddistupgradepackages(Solver *solv, Solvable *s, Queue *qs, int allow_all)
 859 {
 860   Pool *pool = solv->pool;
 861   int i;
 862
 863   policy_findupdatepackages(solv, s, qs, allow_all);
 864   if (!qs->count)
 865     {
 866       if (allow_all)
 867         return 0;       /* orphaned, don't create feature rule */
 868       /* check if this is an orphaned package */
 869       policy_findupdatepackages(solv, s, qs, 1);
 870       if (!qs->count)
 871         return 0;       /* orphaned, don't create update rule */
 872       qs->count = 0;
 873       return -SYSTEMSOLVABLE;   /* supported but not installable */
 874     }
 875   if (allow_all)
 876     return s - pool->solvables;
 877   /* check if it is ok to keep the installed package */
 878   for (i = 0; i < qs->count; i++)
 879     {
 880       Solvable *ns = pool->solvables + qs->elements[i];
 881       if (s->evr == ns->evr && solvable_identical(s, ns))
 882         return s - pool->solvables;
 883     }
 884   /* nope, it must be some other package */
 885   return -SYSTEMSOLVABLE;
 886 }
 887
 888 /* add packages from the dup repositories to the update candidates
 889  * this isn't needed for the global dup mode as all packages are
 890  * from dup repos in that case */
 891 static void
 892 addduppackages(Solver *solv, Solvable *s, Queue *qs)
 893 {
 894   Queue dupqs;
 895   Id p, dupqsbuf[64];
 896   int i;
 897   int oldnoupdateprovide = solv->noupdateprovide;
 898
 899   queue_init_buffer(&dupqs, dupqsbuf, sizeof(dupqsbuf)/sizeof(*dupqsbuf));
 900   solv->noupdateprovide = 1;
 901   policy_findupdatepackages(solv, s, &dupqs, 2);
 902   solv->noupdateprovide = oldnoupdateprovide;
 903   for (i = 0; i < dupqs.count; i++)
 904     {
 905       p = dupqs.elements[i];
 906       if (MAPTST(&solv->dupmap, p))
 907         queue_pushunique(qs, p);
 908     }
 909   queue_free(&dupqs);
 910 }
 911
 912 /*-------------------------------------------------------------------
 913  *
 914  * add rule for update
 915  *   (A|A1|A2|A3...)  An = update candidates for A
 916  *
 917  * s = (installed) solvable
 918  */
 919
 920 void
 921 solver_addupdaterule(Solver *solv, Solvable *s, int allow_all)
 922 {
 923   /* installed packages get a special upgrade allowed rule */
 924   Pool *pool = solv->pool;
 925   Id p, d;
 926   Queue qs;
 927   Id qsbuf[64];
 928
 929   POOL_DEBUG(SAT_DEBUG_SCHUBI, "-----  addupdaterule -----\n");
 930   queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
 931   p = s - pool->solvables;
 932   /* find update candidates for 's' */
 933   if (solv->dupmap_all)
 934     p = finddistupgradepackages(solv, s, &qs, allow_all);
 935   else
 936     policy_findupdatepackages(solv, s, &qs, allow_all);
 937   if (!allow_all && !solv->dupmap_all && solv->dupinvolvedmap.size && MAPTST(&solv->dupinvolvedmap, p))
 938     addduppackages(solv, s, &qs);
 939
 940   if (!allow_all && qs.count && solv->noobsoletes.size)
 941     {
 942       int i, j;
 943
 944       d = pool_queuetowhatprovides(pool, &qs);
 945       /* filter out all noobsoletes packages as they don't update */
 946       for (i = j = 0; i < qs.count; i++)
 947         {
 948           if (MAPTST(&solv->noobsoletes, qs.elements[i]))
 949             {
 950               /* it's ok if they have same nevra */
 951               Solvable *ps = pool->solvables + qs.elements[i];
 952               if (ps->name != s->name || ps->evr != s->evr || ps->arch != s->arch)
 953                 continue;
 954             }
 955           qs.elements[j++] = qs.elements[i];
 956         }
 957       if (j < qs.count)
 958         {
 959           if (d && solv->installed && s->repo == solv->installed &&
 960               (solv->updatemap_all || (solv->updatemap.size && MAPTST(&solv->updatemap, s - pool->solvables - solv->installed->start))))
 961             {
 962               if (!solv->multiversionupdaters)
 963                 solv->multiversionupdaters = sat_calloc(solv->installed->end - solv->installed->start, sizeof(Id));
 964               solv->multiversionupdaters[s - pool->solvables - solv->installed->start] = d;
 965             }
 966           if (j == 0 && p == -SYSTEMSOLVABLE && solv->dupmap_all)
 967             {
 968               queue_push(&solv->orphaned, s - pool->solvables); /* treat as orphaned */
 969               j = qs.count;
 970             }
 971           qs.count = j;
 972         }
 973     }
 974   if (qs.count && p == -SYSTEMSOLVABLE)
 975     p = queue_shift(&qs);
 976   d = qs.count ? pool_queuetowhatprovides(pool, &qs) : 0;
 977   queue_free(&qs);
 978   solver_addrule(solv, p, d);   /* allow update of s */
 979   POOL_DEBUG(SAT_DEBUG_SCHUBI, "-----  addupdaterule end -----\n");
 980 }
 981
 982 static inline void
 983 disableupdaterule(Solver *solv, Id p)
 984 {
 985   Rule *r;
 986
 987   MAPSET(&solv->noupdate, p - solv->installed->start);
 988   r = solv->rules + solv->updaterules + (p - solv->installed->start);
 989   if (r->p && r->d >= 0)
 990     solver_disablerule(solv, r);
 991   r = solv->rules + solv->featurerules + (p - solv->installed->start);
 992   if (r->p && r->d >= 0)
 993     solver_disablerule(solv, r);
 994 }
 995
 996 static inline void
 997 reenableupdaterule(Solver *solv, Id p)
 998 {
 999   Pool *pool = solv->pool;
1000   Rule *r;
1001
1002   MAPCLR(&solv->noupdate, p - solv->installed->start);
1003   r = solv->rules + solv->updaterules + (p - solv->installed->start);
1004   if (r->p)
1005     {
1006       if (r->d >= 0)
1007         return;
1008       solver_enablerule(solv, r);
1009       IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
1010         {
1011           POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
1012           solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
1013         }
1014       return;
1015     }
1016   r = solv->rules + solv->featurerules + (p - solv->installed->start);
1017   if (r->p && r->d < 0)
1018     {
1019       solver_enablerule(solv, r);
1020       IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
1021         {
1022           POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
1023           solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
1024         }
1025     }
1026 }
1027
1028
1029 /***********************************************************************
1030  ***
1031  ***  Infarch rule part
1032  ***
1033  ***  Infarch rules make sure the solver uses the best architecture of
1034  ***  a package if multiple archetectures are available
1035  ***
1036  ***/
1037
1038 void
1039 solver_addinfarchrules(Solver *solv, Map *addedmap)
1040 {
1041   Pool *pool = solv->pool;
1042   int first, i, j;
1043   Id p, pp, a, aa, bestarch;
1044   Solvable *s, *ps, *bests;
1045   Queue badq, allowedarchs;
1046
1047   queue_init(&badq);
1048   queue_init(&allowedarchs);
1049   solv->infarchrules = solv->nrules;
1050   for (i = 1; i < pool->nsolvables; i++)
1051     {
1052       if (i == SYSTEMSOLVABLE || !MAPTST(addedmap, i))
1053         continue;
1054       s = pool->solvables + i;
1055       first = i;
1056       bestarch = 0;
1057       bests = 0;
1058       queue_empty(&allowedarchs);
1059       FOR_PROVIDES(p, pp, s->name)
1060         {
1061           ps = pool->solvables + p;
1062           if (ps->name != s->name || !MAPTST(addedmap, p))
1063             continue;
1064           if (p == i)
1065             first = 0;
1066           if (first)
1067             break;
1068           a = ps->arch;
1069           a = (a <= pool->lastarch) ? pool->id2arch[a] : 0;
1070           if (a != 1 && pool->installed && ps->repo == pool->installed)
1071             {
1072               if (!solv->dupmap_all && !(solv->dupinvolvedmap.size && MAPTST(&solv->dupinvolvedmap, p)))
1073                 queue_pushunique(&allowedarchs, ps->arch);      /* also ok to keep this architecture */
1074               continue;         /* ignore installed solvables when calculating the best arch */
1075             }
1076           if (a && a != 1 && (!bestarch || a < bestarch))
1077             {
1078               bestarch = a;
1079               bests = ps;
1080             }
1081         }
1082       if (first)
1083         continue;
1084       /* speed up common case where installed package already has best arch */
1085       if (allowedarchs.count == 1 && bests && allowedarchs.elements[0] == bests->arch)
1086         allowedarchs.count--;   /* installed arch is best */
1087       queue_empty(&badq);
1088       FOR_PROVIDES(p, pp, s->name)
1089         {
1090           ps = pool->solvables + p;
1091           if (ps->name != s->name || !MAPTST(addedmap, p))
1092             continue;
1093           a = ps->arch;
1094           a = (a <= pool->lastarch) ? pool->id2arch[a] : 0;
1095           if (a != 1 && bestarch && ((a ^ bestarch) & 0xffff0000) != 0)
1096             {
1097               if (pool->installed && ps->repo == pool->installed)
1098                 continue;       /* always ok to keep an installed package */
1099               for (j = 0; j < allowedarchs.count; j++)
1100                 {
1101                   aa = allowedarchs.elements[j];
1102                   if (ps->arch == aa)
1103                     break;
1104                   aa = (aa <= pool->lastarch) ? pool->id2arch[aa] : 0;
1105                   if (aa && ((a ^ aa) & 0xffff0000) == 0)
1106                     break;      /* compatible */
1107                 }
1108               if (j == allowedarchs.count)
1109                 queue_push(&badq, p);
1110             }
1111         }
1112       if (!badq.count)
1113         continue;
1114       /* block all solvables in the badq! */
1115       for (j = 0; j < badq.count; j++)
1116         {
1117           p = badq.elements[j];
1118           solver_addrule(solv, -p, 0);
1119         }
1120     }
1121   queue_free(&badq);
1122   queue_free(&allowedarchs);
1123   solv->infarchrules_end = solv->nrules;
1124 }
1125
1126 static inline void
1127 disableinfarchrule(Solver *solv, Id name)
1128 {
1129   Pool *pool = solv->pool;
1130   Rule *r;
1131   int i;
1132   for (i = solv->infarchrules, r = solv->rules + i; i < solv->infarchrules_end; i++, r++)
1133     {
1134       if (r->p < 0 && r->d >= 0 && pool->solvables[-r->p].name == name)
1135         solver_disablerule(solv, r);
1136     }
1137 }
1138
1139 static inline void
1140 reenableinfarchrule(Solver *solv, Id name)
1141 {
1142   Pool *pool = solv->pool;
1143   Rule *r;
1144   int i;
1145   for (i = solv->infarchrules, r = solv->rules + i; i < solv->infarchrules_end; i++, r++)
1146     {
1147       if (r->p < 0 && r->d < 0 && pool->solvables[-r->p].name == name)
1148         {
1149           solver_enablerule(solv, r);
1150           IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
1151             {
1152               POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
1153               solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
1154             }
1155         }
1156     }
1157 }
1158
1159
1160 /***********************************************************************
1161  ***
1162  ***  Dup rule part
1163  ***
1164  ***  Dup rules make sure a package is selected from the specified dup
1165  ***  repositories if an update candidate is included in one of them.
1166  ***
1167  ***/
1168
1169 void
1170 solver_createdupmaps(Solver *solv)
1171 {
1172   Queue *job = &solv->job;
1173   Pool *pool = solv->pool;
1174   Repo *repo;
1175   Id how, what, p, pi, pp, obs, *obsp;
1176   Solvable *s, *ps;
1177   int i;
1178
1179   map_init(&solv->dupmap, pool->nsolvables);
1180   map_init(&solv->dupinvolvedmap, pool->nsolvables);
1181   for (i = 0; i < job->count; i += 2)
1182     {
1183       how = job->elements[i];
1184       what = job->elements[i + 1];
1185       switch (how & SOLVER_JOBMASK)
1186         {
1187         case SOLVER_DISTUPGRADE:
1188           if ((how & SOLVER_SELECTMASK) != SOLVER_SOLVABLE_REPO)
1189             break;
1190           if (what <= 0 || what > pool->nrepos)
1191             break;
1192           repo = pool_id2repo(pool, what);
1193           FOR_REPO_SOLVABLES(repo, p, s)
1194             {
1195               MAPSET(&solv->dupmap, p);
1196               FOR_PROVIDES(pi, pp, s->name)
1197                 {
1198                   ps = pool->solvables + pi;
1199                   if (ps->name != s->name)
1200                     continue;
1201                   MAPSET(&solv->dupinvolvedmap, pi);
1202                 }
1203               if (s->obsoletes)
1204                 {
1205                   /* FIXME: check obsoletes/provides combination */
1206                   obsp = s->repo->idarraydata + s->obsoletes;
1207                   while ((obs = *obsp++) != 0)
1208                     {
1209                       FOR_PROVIDES(pi, pp, obs)
1210                         {
1211                           Solvable *pis = pool->solvables + pi;
1212                           if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, pis, obs))
1213                             continue;
1214                           if (pool->obsoleteusescolors && !pool_colormatch(pool, s, pis))
1215                             continue;
1216                           MAPSET(&solv->dupinvolvedmap, pi);
1217                         }
1218                     }
1219                 }
1220             }
1221           break;
1222         default:
1223           break;
1224         }
1225     }
1226   MAPCLR(&solv->dupinvolvedmap, SYSTEMSOLVABLE);
1227 }
1228
1229 void
1230 solver_freedupmaps(Solver *solv)
1231 {
1232   map_free(&solv->dupmap);
1233   /* we no longer free solv->dupinvolvedmap as we need it in
1234    * policy's priority pruning code. sigh. */
1235 }
1236
1237 void
1238 solver_addduprules(Solver *solv, Map *addedmap)
1239 {
1240   Pool *pool = solv->pool;
1241   Id p, pp;
1242   Solvable *s, *ps;
1243   int first, i;
1244
1245   solv->duprules = solv->nrules;
1246   for (i = 1; i < pool->nsolvables; i++)
1247     {
1248       if (i == SYSTEMSOLVABLE || !MAPTST(addedmap, i))
1249         continue;
1250       s = pool->solvables + i;
1251       first = i;
1252       FOR_PROVIDES(p, pp, s->name)
1253         {
1254           ps = pool->solvables + p;
1255           if (ps->name != s->name || !MAPTST(addedmap, p))
1256             continue;
1257           if (p == i)
1258             first = 0;
1259           if (first)
1260             break;
1261           if (!MAPTST(&solv->dupinvolvedmap, p))
1262             continue;
1263           if (solv->installed && ps->repo == solv->installed)
1264             {
1265               if (!solv->updatemap.size)
1266                 map_grow(&solv->updatemap, solv->installed->end - solv->installed->start);
1267               MAPSET(&solv->updatemap, p - solv->installed->start);
1268               if (!MAPTST(&solv->dupmap, p))
1269                 {
1270                   Id ip, ipp;
1271                   /* is installed identical to a good one? */
1272                   FOR_PROVIDES(ip, ipp, ps->name)
1273                     {
1274                       Solvable *is = pool->solvables + ip;
1275                       if (!MAPTST(&solv->dupmap, ip))
1276                         continue;
1277                       if (is->evr == ps->evr && solvable_identical(ps, is))
1278                         break;
1279                     }
1280                   if (!ip)
1281                     solver_addrule(solv, -p, 0);        /* no match, sorry */
1282                 }
1283             }
1284           else if (!MAPTST(&solv->dupmap, p))
1285             solver_addrule(solv, -p, 0);
1286         }
1287     }
1288   solv->duprules_end = solv->nrules;
1289 }
1290
1291
1292 static inline void
1293 disableduprule(Solver *solv, Id name)
1294 {
1295   Pool *pool = solv->pool;
1296   Rule *r;
1297   int i;
1298   for (i = solv->duprules, r = solv->rules + i; i < solv->duprules_end; i++, r++)
1299     {
1300       if (r->p < 0 && r->d >= 0 && pool->solvables[-r->p].name == name)
1301         solver_disablerule(solv, r);
1302     }
1303 }
1304
1305 static inline void
1306 reenableduprule(Solver *solv, Id name)
1307 {
1308   Pool *pool = solv->pool;
1309   Rule *r;
1310   int i;
1311   for (i = solv->duprules, r = solv->rules + i; i < solv->duprules_end; i++, r++)
1312     {
1313       if (r->p < 0 && r->d < 0 && pool->solvables[-r->p].name == name)
1314         {
1315           solver_enablerule(solv, r);
1316           IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
1317             {
1318               POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
1319               solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
1320             }
1321         }
1322     }
1323 }
1324
1325
1326 /***********************************************************************
1327  ***
1328  ***  Policy rule disabling/reenabling
1329  ***
1330  ***  Disable all policy rules that conflict with our jobs. If a job
1331  ***  gets disabled later on, reenable the involved policy rules again.
1332  ***
1333  ***/
1334
1335 #define DISABLE_UPDATE  1
1336 #define DISABLE_INFARCH 2
1337 #define DISABLE_DUP     3
1338
1339 static void
1340 jobtodisablelist(Solver *solv, Id how, Id what, Queue *q)
1341 {
1342   Pool *pool = solv->pool;
1343   Id select, p, pp;
1344   Repo *installed;
1345   Solvable *s;
1346   int i, j, set, qstart, pass;
1347   Map omap;
1348
1349   installed = solv->installed;
1350   select = how & SOLVER_SELECTMASK;
1351   switch (how & SOLVER_JOBMASK)
1352     {
1353     case SOLVER_INSTALL:
1354       set = how & SOLVER_SETMASK;
1355       if (!(set & SOLVER_NOAUTOSET))
1356         {
1357           /* automatically add set bits by analysing the job */
1358           if (select == SOLVER_SOLVABLE)
1359             set |= SOLVER_SETARCH | SOLVER_SETVENDOR | SOLVER_SETREPO | SOLVER_SETEVR;
1360           else if ((select == SOLVER_SOLVABLE_NAME || select == SOLVER_SOLVABLE_PROVIDES) && ISRELDEP(what))
1361             {
1362               Reldep *rd = GETRELDEP(pool, what);
1363               if (rd->flags == REL_EQ && select == SOLVER_SOLVABLE_NAME)
1364                 {
1365 #if !defined(DEBIAN_SEMANTICS)
1366                   const char *evr = pool_id2str(pool, rd->evr);
1367                   if (strchr(evr, '-'))
1368                     set |= SOLVER_SETEVR;
1369                   else
1370                     set |= SOLVER_SETEV;
1371 #else
1372                   set |= SOLVER_SETEVR;
1373 #endif
1374                 }
1375               if (rd->flags <= 7 && ISRELDEP(rd->name))
1376                 rd = GETRELDEP(pool, rd->name);
1377               if (rd->flags == REL_ARCH)
1378                 set |= SOLVER_SETARCH;
1379             }
1380         }
1381       else
1382         set &= ~SOLVER_NOAUTOSET;
1383       if (!set)
1384         return;
1385       if ((set & SOLVER_SETARCH) != 0 && solv->infarchrules != solv->infarchrules_end)
1386         {
1387           if (select == SOLVER_SOLVABLE)
1388             queue_push2(q, DISABLE_INFARCH, pool->solvables[what].name);
1389           else
1390             {
1391               int qcnt = q->count;
1392               FOR_JOB_SELECT(p, pp, select, what)
1393                 {
1394                   s = pool->solvables + p;
1395                   /* unify names */
1396                   for (i = qcnt; i < q->count; i += 2)
1397                     if (q->elements[i + 1] == s->name)
1398                       break;
1399                   if (i < q->count)
1400                     continue;
1401                   queue_push2(q, DISABLE_INFARCH, s->name);
1402                 }
1403             }
1404         }
1405       if ((set & SOLVER_SETREPO) != 0 && solv->duprules != solv->duprules_end)
1406         {
1407           if (select == SOLVER_SOLVABLE)
1408             queue_push2(q, DISABLE_DUP, pool->solvables[what].name);
1409           else
1410             {
1411               int qcnt = q->count;
1412               FOR_JOB_SELECT(p, pp, select, what)
1413                 {
1414                   s = pool->solvables + p;
1415                   /* unify names */
1416                   for (i = qcnt; i < q->count; i += 2)
1417                     if (q->elements[i + 1] == s->name)
1418                       break;
1419                   if (i < q->count)
1420                     continue;
1421                   queue_push2(q, DISABLE_DUP, s->name);
1422                 }
1423             }
1424         }
1425       if (!installed)
1426         return;
1427       /* now the hard part: disable some update rules */
1428
1429       /* first check if we have noobs or installed packages in the job */
1430       FOR_JOB_SELECT(p, pp, select, what)
1431         {
1432           if (pool->solvables[p].repo == installed)
1433             {
1434               if (select == SOLVER_SOLVABLE)
1435                 queue_push2(q, DISABLE_UPDATE, what);
1436               return;
1437             }
1438           if (solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p))
1439             return;
1440         }
1441
1442       /* all job packages obsolete */
1443       qstart = q->count;
1444       pass = 0;
1445       memset(&omap, 0, sizeof(omap));
1446       FOR_JOB_SELECT(p, pp, select, what)
1447         {
1448           Id p2, pp2;
1449
1450           if (pass == 1)
1451             map_grow(&omap, installed->end - installed->start);
1452           s = pool->solvables + p;
1453           if (s->obsoletes)
1454             {
1455               Id obs, *obsp;
1456               obsp = s->repo->idarraydata + s->obsoletes;
1457               while ((obs = *obsp++) != 0)
1458                 FOR_PROVIDES(p2, pp2, obs)
1459                   {
1460                     Solvable *ps = pool->solvables + p2;
1461                     if (ps->repo != installed)
1462                       continue;
1463                     if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
1464                       continue;
1465                     if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
1466                       continue;
1467                     if (pass)
1468                       MAPSET(&omap, p2 - installed->start);
1469                     else
1470                       queue_push2(q, DISABLE_UPDATE, p2);
1471                   }
1472             }
1473           FOR_PROVIDES(p2, pp2, s->name)
1474             {
1475               Solvable *ps = pool->solvables + p2;
1476               if (ps->repo != installed)
1477                 continue;
1478               if (!pool->implicitobsoleteusesprovides && ps->name != s->name)
1479                 continue;
1480               if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
1481                 continue;
1482               if (pass)
1483                 MAPSET(&omap, p2 - installed->start);
1484               else
1485                 queue_push2(q, DISABLE_UPDATE, p2);
1486             }
1487           if (pass)
1488             {
1489               for (i = j = qstart; i < q->count; i += 2)
1490                 {
1491                   if (MAPTST(&omap, q->elements[i + 1] - installed->start))
1492                     {
1493                       MAPCLR(&omap, q->elements[i + 1] - installed->start);
1494                       q->elements[j + 1] = q->elements[i + 1];
1495                       j += 2;
1496                     }
1497                 }
1498               queue_truncate(q, j);
1499             }
1500           if (q->count == qstart)
1501             break;
1502           pass++;
1503         }
1504       if (omap.size)
1505         map_free(&omap);
1506
1507       if (qstart == q->count)
1508         return;         /* nothing to prune */
1509       if ((set & (SOLVER_SETEVR | SOLVER_SETARCH | SOLVER_SETVENDOR)) == (SOLVER_SETEVR | SOLVER_SETARCH | SOLVER_SETVENDOR))
1510         return;         /* all is set */
1511
1512       /* now that we know which installed packages are obsoleted check each of them */
1513       for (i = j = qstart; i < q->count; i += 2)
1514         {
1515           Solvable *is = pool->solvables + q->elements[i + 1];
1516           FOR_JOB_SELECT(p, pp, select, what)
1517             {
1518               int illegal = 0;
1519               s = pool->solvables + p;
1520               if ((set & SOLVER_SETEVR) != 0)
1521                 illegal |= POLICY_ILLEGAL_DOWNGRADE;    /* ignore */
1522               if ((set & SOLVER_SETARCH) != 0)
1523                 illegal |= POLICY_ILLEGAL_ARCHCHANGE;   /* ignore */
1524               if ((set & SOLVER_SETVENDOR) != 0)
1525                 illegal |= POLICY_ILLEGAL_VENDORCHANGE; /* ignore */
1526               illegal = policy_is_illegal(solv, is, s, illegal);
1527               if (illegal && illegal == POLICY_ILLEGAL_DOWNGRADE && (set & SOLVER_SETEV) != 0)
1528                 {
1529                   /* it's ok if the EV is different */
1530                   if (pool_evrcmp(pool, is->evr, s->evr, EVRCMP_COMPARE_EVONLY) != 0)
1531                     illegal = 0;
1532                 }
1533               if (illegal)
1534                 break;
1535             }
1536           if (!p)
1537             {
1538               /* no package conflicts with the update rule */
1539               /* thus keep the DISABLE_UPDATE */
1540               q->elements[j + 1] = q->elements[i + 1];
1541               j += 2;
1542             }
1543         }
1544       queue_truncate(q, j);
1545       return;
1546
1547     case SOLVER_ERASE:
1548       if (!installed)
1549         break;
1550       FOR_JOB_SELECT(p, pp, select, what)
1551         if (pool->solvables[p].repo == installed)
1552           queue_push2(q, DISABLE_UPDATE, p);
1553       return;
1554     default:
1555       return;
1556     }
1557 }
1558
1559 /* disable all policy rules that are in conflict with our job list */
1560 void
1561 solver_disablepolicyrules(Solver *solv)
1562 {
1563   Queue *job = &solv->job;
1564   int i, j;
1565   Queue allq;
1566   Rule *r;
1567   Id lastjob = -1;
1568   Id allqbuf[128];
1569
1570   queue_init_buffer(&allq, allqbuf, sizeof(allqbuf)/sizeof(*allqbuf));
1571
1572   for (i = solv->jobrules; i < solv->jobrules_end; i++)
1573     {
1574       r = solv->rules + i;
1575       if (r->d < 0)     /* disabled? */
1576         continue;
1577       j = solv->ruletojob.elements[i - solv->jobrules];
1578       if (j == lastjob)
1579         continue;
1580       lastjob = j;
1581       jobtodisablelist(solv, job->elements[j], job->elements[j + 1], &allq);
1582     }
1583   if (solv->cleandepsmap.size)
1584     {
1585       solver_createcleandepsmap(solv);
1586       for (i = solv->installed->start; i < solv->installed->end; i++)
1587         if (MAPTST(&solv->cleandepsmap, i - solv->installed->start))
1588           queue_push2(&allq, DISABLE_UPDATE, i);
1589     }
1590   MAPZERO(&solv->noupdate);
1591   for (i = 0; i < allq.count; i += 2)
1592     {
1593       Id type = allq.elements[i], arg = allq.elements[i + 1];
1594       switch(type)
1595         {
1596         case DISABLE_UPDATE:
1597           disableupdaterule(solv, arg);
1598           break;
1599         case DISABLE_INFARCH:
1600           disableinfarchrule(solv, arg);
1601           break;
1602         case DISABLE_DUP:
1603           disableduprule(solv, arg);
1604           break;
1605         default:
1606           break;
1607         }
1608     }
1609   queue_free(&allq);
1610 }
1611
1612 /* we just disabled job #jobidx, now reenable all policy rules that were
1613  * disabled because of this job */
1614 void
1615 solver_reenablepolicyrules(Solver *solv, int jobidx)
1616 {
1617   Queue *job = &solv->job;
1618   int i, j;
1619   Queue q, allq;
1620   Rule *r;
1621   Id lastjob = -1;
1622   Id qbuf[32], allqbuf[128];
1623
1624   queue_init_buffer(&q, qbuf, sizeof(qbuf)/sizeof(*qbuf));
1625   queue_init_buffer(&allq, allqbuf, sizeof(allqbuf)/sizeof(*allqbuf));
1626   jobtodisablelist(solv, job->elements[jobidx], job->elements[jobidx + 1], &q);
1627   if (!q.count)
1628     return;
1629   for (i = solv->jobrules; i < solv->jobrules_end; i++)
1630     {
1631       r = solv->rules + i;
1632       if (r->d < 0)     /* disabled? */
1633         continue;
1634       j = solv->ruletojob.elements[i - solv->jobrules];
1635       if (j == lastjob)
1636         continue;
1637       lastjob = j;
1638       jobtodisablelist(solv, job->elements[j], job->elements[j + 1], &allq);
1639     }
1640   if (solv->cleandepsmap.size)
1641     {
1642       solver_createcleandepsmap(solv);
1643       for (i = solv->installed->start; i < solv->installed->end; i++)
1644         if (MAPTST(&solv->cleandepsmap, i - solv->installed->start))
1645           queue_push2(&allq, DISABLE_UPDATE, i);
1646     }
1647   for (j = 0; j < q.count; j += 2)
1648     {
1649       Id type = q.elements[j], arg = q.elements[j + 1];
1650       for (i = 0; i < allq.count; i += 2)
1651         if (allq.elements[i] == type && allq.elements[i + 1] == arg)
1652           break;
1653       if (i < allq.count)
1654         continue;       /* still disabled */
1655       switch(type)
1656         {
1657         case DISABLE_UPDATE:
1658           reenableupdaterule(solv, arg);
1659           break;
1660         case DISABLE_INFARCH:
1661           reenableinfarchrule(solv, arg);
1662           break;
1663         case DISABLE_DUP:
1664           reenableduprule(solv, arg);
1665           break;
1666         }
1667     }
1668   queue_free(&allq);
1669   queue_free(&q);
1670 }
1671
1672
1673 /***********************************************************************
1674  ***
1675  ***  Rule info part, tell the user what the rule is about.
1676  ***
1677  ***/
1678
1679 static void
1680 addrpmruleinfo(Solver *solv, Id p, Id d, int type, Id dep)
1681 {
1682   Pool *pool = solv->pool;
1683   Rule *r;
1684   Id w2, op, od, ow2;
1685
1686   /* check if this creates the rule we're searching for */
1687   r = solv->rules + solv->ruleinfoq->elements[0];
1688   op = r->p;
1689   od = r->d < 0 ? -r->d - 1 : r->d;
1690   ow2 = 0;
1691
1692   /* normalize */
1693   w2 = d > 0 ? 0 : d;
1694   if (p < 0 && d > 0 && (!pool->whatprovidesdata[d] || !pool->whatprovidesdata[d + 1]))
1695     {
1696       w2 = pool->whatprovidesdata[d];
1697       d = 0;
1698
1699     }
1700   if (p > 0 && d < 0)           /* this hack is used for buddy deps */
1701     {
1702       w2 = p;
1703       p = d;
1704     }
1705
1706   if (d > 0)
1707     {
1708       if (p != op && !od)
1709         return;
1710       if (d != od)
1711         {
1712           Id *dp = pool->whatprovidesdata + d;
1713           Id *odp = pool->whatprovidesdata + od;
1714           while (*dp)
1715             if (*dp++ != *odp++)
1716               return;
1717           if (*odp)
1718             return;
1719         }
1720       w2 = 0;
1721       /* handle multiversion conflict rules */
1722       if (p < 0 && pool->whatprovidesdata[d] < 0)
1723         {
1724           w2 = pool->whatprovidesdata[d];
1725           /* XXX: free memory */
1726         }
1727     }
1728   else
1729     {
1730       if (od)
1731         return;
1732       ow2 = r->w2;
1733       if (p > w2)
1734         {
1735           if (w2 != op || p != ow2)
1736             return;
1737         }
1738       else
1739         {
1740           if (p != op || w2 != ow2)
1741             return;
1742         }
1743     }
1744   /* yep, rule matches. record info */
1745   queue_push(solv->ruleinfoq, type);
1746   if (type == SOLVER_RULE_RPM_SAME_NAME)
1747     {
1748       /* we normalize same name order */
1749       queue_push(solv->ruleinfoq, op < 0 ? -op : 0);
1750       queue_push(solv->ruleinfoq, ow2 < 0 ? -ow2 : 0);
1751     }
1752   else
1753     {
1754       queue_push(solv->ruleinfoq, p < 0 ? -p : 0);
1755       queue_push(solv->ruleinfoq, w2 < 0 ? -w2 : 0);
1756     }
1757   queue_push(solv->ruleinfoq, dep);
1758 }
1759
1760 static int
1761 solver_allruleinfos_cmp(const void *ap, const void *bp, void *dp)
1762 {
1763   const Id *a = ap, *b = bp;
1764   int r;
1765
1766   r = a[0] - b[0];
1767   if (r)
1768     return r;
1769   r = a[1] - b[1];
1770   if (r)
1771     return r;
1772   r = a[2] - b[2];
1773   if (r)
1774     return r;
1775   r = a[3] - b[3];
1776   if (r)
1777     return r;
1778   return 0;
1779 }
1780
1781 int
1782 solver_allruleinfos(Solver *solv, Id rid, Queue *rq)
1783 {
1784   Pool *pool = solv->pool;
1785   Rule *r = solv->rules + rid;
1786   int i, j;
1787
1788   queue_empty(rq);
1789   if (rid <= 0 || rid >= solv->rpmrules_end)
1790     {
1791       Id type, from, to, dep;
1792       type = solver_ruleinfo(solv, rid, &from, &to, &dep);
1793       queue_push(rq, type);
1794       queue_push(rq, from);
1795       queue_push(rq, to);
1796       queue_push(rq, dep);
1797       return 1;
1798     }
1799   if (r->p >= 0)
1800     return 0;
1801   queue_push(rq, rid);
1802   solv->ruleinfoq = rq;
1803   solver_addrpmrulesforsolvable(solv, pool->solvables - r->p, 0);
1804   /* also try reverse direction for conflicts */
1805   if ((r->d == 0 || r->d == -1) && r->w2 < 0)
1806     solver_addrpmrulesforsolvable(solv, pool->solvables - r->w2, 0);
1807   solv->ruleinfoq = 0;
1808   queue_shift(rq);
1809   /* now sort & unify em */
1810   if (!rq->count)
1811     return 0;
1812   sat_sort(rq->elements, rq->count / 4, 4 * sizeof(Id), solver_allruleinfos_cmp, 0);
1813   /* throw out identical entries */
1814   for (i = j = 0; i < rq->count; i += 4)
1815     {
1816       if (j)
1817         {
1818           if (rq->elements[i] == rq->elements[j - 4] &&
1819               rq->elements[i + 1] == rq->elements[j - 3] &&
1820               rq->elements[i + 2] == rq->elements[j - 2] &&
1821               rq->elements[i + 3] == rq->elements[j - 1])
1822             continue;
1823         }
1824       rq->elements[j++] = rq->elements[i];
1825       rq->elements[j++] = rq->elements[i + 1];
1826       rq->elements[j++] = rq->elements[i + 2];
1827       rq->elements[j++] = rq->elements[i + 3];
1828     }
1829   rq->count = j;
1830   return j / 4;
1831 }
1832
1833 SolverRuleinfo
1834 solver_ruleinfo(Solver *solv, Id rid, Id *fromp, Id *top, Id *depp)
1835 {
1836   Pool *pool = solv->pool;
1837   Rule *r = solv->rules + rid;
1838   SolverRuleinfo type = SOLVER_RULE_UNKNOWN;
1839
1840   if (fromp)
1841     *fromp = 0;
1842   if (top)
1843     *top = 0;
1844   if (depp)
1845     *depp = 0;
1846   if (rid > 0 && rid < solv->rpmrules_end)
1847     {
1848       Queue rq;
1849       int i;
1850
1851       if (r->p >= 0)
1852         return SOLVER_RULE_RPM;
1853       if (fromp)
1854         *fromp = -r->p;
1855       queue_init(&rq);
1856       queue_push(&rq, rid);
1857       solv->ruleinfoq = &rq;
1858       solver_addrpmrulesforsolvable(solv, pool->solvables - r->p, 0);
1859       /* also try reverse direction for conflicts */
1860       if ((r->d == 0 || r->d == -1) && r->w2 < 0)
1861         solver_addrpmrulesforsolvable(solv, pool->solvables - r->w2, 0);
1862       solv->ruleinfoq = 0;
1863       type = SOLVER_RULE_RPM;
1864       for (i = 1; i < rq.count; i += 4)
1865         {
1866           Id qt, qo, qp, qd;
1867           qt = rq.elements[i];
1868           qp = rq.elements[i + 1];
1869           qo = rq.elements[i + 2];
1870           qd = rq.elements[i + 3];
1871           if (type == SOLVER_RULE_RPM || type > qt)
1872             {
1873               type = qt;
1874               if (fromp)
1875                 *fromp = qp;
1876               if (top)
1877                 *top = qo;
1878               if (depp)
1879                 *depp = qd;
1880             }
1881         }
1882       queue_free(&rq);
1883       return type;
1884     }
1885   if (rid >= solv->jobrules && rid < solv->jobrules_end)
1886     {
1887       Id jidx = solv->ruletojob.elements[rid - solv->jobrules];
1888       if (fromp)
1889         *fromp = jidx;
1890       if (top)
1891         *top = solv->job.elements[jidx];
1892       if (depp)
1893         *depp = solv->job.elements[jidx + 1];
1894       if ((r->d == 0 || r->d == -1) && r->w2 == 0 && r->p == -SYSTEMSOLVABLE && (solv->job.elements[jidx] & SOLVER_SELECTMASK) != SOLVER_SOLVABLE_ONE_OF)
1895         return SOLVER_RULE_JOB_NOTHING_PROVIDES_DEP;
1896       return SOLVER_RULE_JOB;
1897     }
1898   if (rid >= solv->updaterules && rid < solv->updaterules_end)
1899     {
1900       if (fromp)
1901         *fromp = solv->installed->start + (rid - solv->updaterules);
1902       return SOLVER_RULE_UPDATE;
1903     }
1904   if (rid >= solv->featurerules && rid < solv->featurerules_end)
1905     {
1906       if (fromp)
1907         *fromp = solv->installed->start + (rid - solv->featurerules);
1908       return SOLVER_RULE_FEATURE;
1909     }
1910   if (rid >= solv->duprules && rid < solv->duprules_end)
1911     {
1912       if (fromp)
1913         *fromp = -r->p;
1914       if (depp)
1915         *depp = pool->solvables[-r->p].name;
1916       return SOLVER_RULE_DISTUPGRADE;
1917     }
1918   if (rid >= solv->infarchrules && rid < solv->infarchrules_end)
1919     {
1920       if (fromp)
1921         *fromp = -r->p;
1922       if (depp)
1923         *depp = pool->solvables[-r->p].name;
1924       return SOLVER_RULE_INFARCH;
1925     }
1926   if (rid >= solv->choicerules && rid < solv->choicerules_end)
1927     {
1928       return SOLVER_RULE_CHOICE;
1929     }
1930   if (rid >= solv->learntrules)
1931     {
1932       return SOLVER_RULE_LEARNT;
1933     }
1934   return SOLVER_RULE_UNKNOWN;
1935 }
1936
1937 void
1938 solver_addchoicerules(Solver *solv)
1939 {
1940   Pool *pool = solv->pool;
1941   Map m, mneg;
1942   Rule *r;
1943   Queue q, qi;
1944   int i, j, rid, havechoice;
1945   Id p, d, *pp;
1946   Id p2, pp2;
1947   Solvable *s, *s2;
1948
1949   solv->choicerules = solv->nrules;
1950   if (!pool->installed)
1951     {
1952       solv->choicerules_end = solv->nrules;
1953       return;
1954     }
1955   solv->choicerules_ref = sat_calloc(solv->rpmrules_end, sizeof(Id));
1956   queue_init(&q);
1957   queue_init(&qi);
1958   map_init(&m, pool->nsolvables);
1959   map_init(&mneg, pool->nsolvables);
1960   /* set up negative assertion map from infarch and dup rules */
1961   for (rid = solv->infarchrules, r = solv->rules + rid; rid < solv->infarchrules_end; rid++, r++)
1962     if (r->p < 0 && !r->w2 && (r->d == 0 || r->d == -1))
1963       MAPSET(&mneg, -r->p);
1964   for (rid = solv->duprules, r = solv->rules + rid; rid < solv->duprules_end; rid++, r++)
1965     if (r->p < 0 && !r->w2 && (r->d == 0 || r->d == -1))
1966       MAPSET(&mneg, -r->p);
1967   for (rid = 1; rid < solv->rpmrules_end ; rid++)
1968     {
1969       r = solv->rules + rid;
1970       if (r->p >= 0 || ((r->d == 0 || r->d == -1) && r->w2 < 0))
1971         continue;       /* only look at requires rules */
1972       // solver_printrule(solv, SAT_DEBUG_RESULT, r);
1973       queue_empty(&q);
1974       queue_empty(&qi);
1975       havechoice = 0;
1976       FOR_RULELITERALS(p, pp, r)
1977         {
1978           if (p < 0)
1979             continue;
1980           s = pool->solvables + p;
1981           if (!s->repo)
1982             continue;
1983           if (s->repo == pool->installed)
1984             {
1985               queue_push(&q, p);
1986               continue;
1987             }
1988           /* check if this package is "blocked" by a installed package */
1989           s2 = 0;
1990           FOR_PROVIDES(p2, pp2, s->name)
1991             {
1992               s2 = pool->solvables + p2;
1993               if (s2->repo != pool->installed)
1994                 continue;
1995               if (!pool->implicitobsoleteusesprovides && s->name != s2->name)
1996                 continue;
1997               if (pool->obsoleteusescolors && !pool_colormatch(pool, s, s2))
1998                 continue;
1999               break;
2000             }
2001           if (p2)
2002             {
2003               /* found installed package p2 that we can update to p */
2004               if (MAPTST(&mneg, p))
2005                 continue;
2006               if (policy_is_illegal(solv, s2, s, 0))
2007                 continue;
2008               queue_push(&qi, p2);
2009               queue_push(&q, p);
2010               continue;
2011             }
2012           if (s->obsoletes)
2013             {
2014               Id obs, *obsp = s->repo->idarraydata + s->obsoletes;
2015               s2 = 0;
2016               while ((obs = *obsp++) != 0)
2017                 {
2018                   FOR_PROVIDES(p2, pp2, obs)
2019                     {
2020                       s2 = pool->solvables + p2;
2021                       if (s2->repo != pool->installed)
2022                         continue;
2023                       if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p2, obs))
2024                         continue;
2025                       if (pool->obsoleteusescolors && !pool_colormatch(pool, s, s2))
2026                         continue;
2027                       break;
2028                     }
2029                   if (p2)
2030                     break;
2031                 }
2032               if (obs)
2033                 {
2034                   /* found installed package p2 that we can update to p */
2035                   if (MAPTST(&mneg, p))
2036                     continue;
2037                   if (policy_is_illegal(solv, s2, s, 0))
2038                     continue;
2039                   queue_push(&qi, p2);
2040                   queue_push(&q, p);
2041                   continue;
2042                 }
2043             }
2044           /* package p is independent of the installed ones */
2045           havechoice = 1;
2046         }
2047       if (!havechoice || !q.count)
2048         continue;       /* no choice */
2049
2050       /* now check the update rules of the installed package.
2051        * if all packages of the update rules are contained in
2052        * the dependency rules, there's no need to set up the choice rule */
2053       map_empty(&m);
2054       FOR_RULELITERALS(p, pp, r)
2055         if (p > 0)
2056           MAPSET(&m, p);
2057       for (i = 0; i < qi.count; i++)
2058         {
2059           if (!qi.elements[i])
2060             continue;
2061           Rule *ur = solv->rules + solv->updaterules + (qi.elements[i] - pool->installed->start);
2062           if (!ur->p)
2063             ur = solv->rules + solv->featurerules + (qi.elements[i] - pool->installed->start);
2064           if (!ur->p)
2065             continue;
2066           FOR_RULELITERALS(p, pp, ur)
2067             if (!MAPTST(&m, p))
2068               break;
2069           if (p)
2070             break;
2071           for (j = i + 1; j < qi.count; j++)
2072             if (qi.elements[i] == qi.elements[j])
2073               qi.elements[j] = 0;
2074         }
2075       if (i == qi.count)
2076         {
2077 #if 0
2078           printf("skipping choice ");
2079           solver_printrule(solv, SAT_DEBUG_RESULT, solv->rules + rid);
2080 #endif
2081           continue;
2082         }
2083       d = q.count ? pool_queuetowhatprovides(pool, &q) : 0;
2084       solver_addrule(solv, r->p, d);
2085       queue_push(&solv->weakruleq, solv->nrules - 1);
2086       solv->choicerules_ref[solv->nrules - 1 - solv->choicerules] = rid;
2087 #if 0
2088       printf("OLD ");
2089       solver_printrule(solv, SAT_DEBUG_RESULT, solv->rules + rid);
2090       printf("WEAK CHOICE ");
2091       solver_printrule(solv, SAT_DEBUG_RESULT, solv->rules + solv->nrules - 1);
2092 #endif
2093     }
2094   queue_free(&q);
2095   queue_free(&qi);
2096   map_free(&m);
2097   map_free(&mneg);
2098   solv->choicerules_end = solv->nrules;
2099 }
2100
2101 /* called when a choice rule is disabled by analyze_unsolvable. We also
2102  * have to disable all other choice rules so that the best packages get
2103  * picked */
2104 void
2105 solver_disablechoicerules(Solver *solv, Rule *r)
2106 {
2107   Id rid, p, *pp;
2108   Pool *pool = solv->pool;
2109   Map m;
2110   Rule *or;
2111
2112   or = solv->rules + solv->choicerules_ref[(r - solv->rules) - solv->choicerules];
2113   map_init(&m, pool->nsolvables);
2114   FOR_RULELITERALS(p, pp, or)
2115     if (p > 0)
2116       MAPSET(&m, p);
2117   FOR_RULELITERALS(p, pp, r)
2118     if (p > 0)
2119       MAPCLR(&m, p);
2120   for (rid = solv->choicerules; rid < solv->choicerules_end; rid++)
2121     {
2122       r = solv->rules + rid;
2123       if (r->d < 0)
2124         continue;
2125       or = solv->rules + solv->choicerules_ref[(r - solv->rules) - solv->choicerules];
2126       FOR_RULELITERALS(p, pp, or)
2127         if (p > 0 && MAPTST(&m, p))
2128           break;
2129       if (p)
2130         solver_disablerule(solv, r);
2131     }
2132 }
2133
2134 static void solver_createcleandepsmap(Solver *solv)
2135 {
2136   Pool *pool = solv->pool;
2137   Repo *installed = solv->installed;
2138   Queue *job = &solv->job;
2139   Map userinstalled;
2140   Map im;
2141   Map installedm;
2142   Rule *r;
2143   Id rid, how, what, select;
2144   Id p, pp, ip, *jp;
2145   Id req, *reqp, sup, *supp;
2146   Solvable *s;
2147   Queue iq;
2148   int i;
2149
2150   map_init(&userinstalled, installed->end - installed->start);
2151   map_init(&im, pool->nsolvables);
2152   map_init(&installedm, pool->nsolvables);
2153   map_empty(&solv->cleandepsmap);
2154   queue_init(&iq);
2155
2156   for (i = 0; i < job->count; i += 2)
2157     {
2158       how = job->elements[i];
2159       if ((how & SOLVER_JOBMASK) == SOLVER_USERINSTALLED)
2160         {
2161           what = job->elements[i + 1];
2162           select = how & SOLVER_SELECTMASK;
2163           FOR_JOB_SELECT(p, pp, select, what)
2164             if (pool->solvables[p].repo == installed)
2165               MAPSET(&userinstalled, p - installed->start);
2166         }
2167     }
2168   /* add all positive elements (e.g. locks) to "userinstalled" */
2169   for (rid = solv->jobrules; rid < solv->jobrules_end; rid++)
2170     {
2171       r = solv->rules + rid;
2172       if (r->d < 0)
2173         continue;
2174       FOR_RULELITERALS(p, jp, r)
2175         if (p > 0 && pool->solvables[p].repo == installed)
2176           MAPSET(&userinstalled, p - installed->start);
2177     }
2178   for (rid = solv->jobrules; rid < solv->jobrules_end; rid++)
2179     {
2180       r = solv->rules + rid;
2181       if (r->p >= 0 || r->d != 0)
2182         continue;       /* disabled or not erase */
2183       p = -r->p;
2184       if (pool->solvables[p].repo != installed)
2185         continue;
2186       MAPCLR(&userinstalled, p - installed->start);
2187       i = solv->ruletojob.elements[rid - solv->jobrules];
2188       how = job->elements[i];
2189       if ((how & (SOLVER_JOBMASK|SOLVER_CLEANDEPS)) == (SOLVER_ERASE|SOLVER_CLEANDEPS))
2190         queue_push(&iq, p);
2191     }
2192   for (p = installed->start; p < installed->end; p++)
2193     {
2194       if (pool->solvables[p].repo != installed)
2195         continue;
2196       MAPSET(&installedm, p);
2197       MAPSET(&im, p);
2198     }
2199
2200   while (iq.count)
2201     {
2202       ip = queue_shift(&iq);
2203       s = pool->solvables + ip;
2204       if (!MAPTST(&im, ip))
2205         continue;
2206       if (!MAPTST(&installedm, ip))
2207         continue;
2208       if (s->repo == installed && MAPTST(&userinstalled, ip - installed->start))
2209         continue;
2210       MAPCLR(&im, ip);
2211 #ifdef CLEANDEPSDEBUG
2212       printf("hello %s\n", pool_solvable2str(pool, s));
2213 #endif
2214       if (s->requires)
2215         {
2216           reqp = s->repo->idarraydata + s->requires;
2217           while ((req = *reqp++) != 0)
2218             {
2219               if (req == SOLVABLE_PREREQMARKER)
2220                 continue;
2221 #if 0
2222               /* count number of installed packages that match */
2223               count = 0;
2224               FOR_PROVIDES(p, pp, req)
2225                 if (MAPTST(&installedm, p))
2226                   count++;
2227               if (count > 1)
2228                 continue;
2229 #endif
2230               FOR_PROVIDES(p, pp, req)
2231                 {
2232                   if (MAPTST(&im, p))
2233                     {
2234 #ifdef CLEANDEPSDEBUG
2235                       printf("%s requires %s\n", pool_solvid2str(pool, ip), pool_solvid2str(pool, p));
2236 #endif
2237                       queue_push(&iq, p);
2238                     }
2239                 }
2240             }
2241         }
2242       if (s->recommends)
2243         {
2244           reqp = s->repo->idarraydata + s->recommends;
2245           while ((req = *reqp++) != 0)
2246             {
2247 #if 0
2248               count = 0;
2249               FOR_PROVIDES(p, pp, req)
2250                 if (MAPTST(&installedm, p))
2251                   count++;
2252               if (count > 1)
2253                 continue;
2254 #endif
2255               FOR_PROVIDES(p, pp, req)
2256                 {
2257                   if (MAPTST(&im, p))
2258                     {
2259 #ifdef CLEANDEPSDEBUG
2260                       printf("%s recommends %s\n", pool_solvid2str(pool, ip), pool_solvid2str(pool, p));
2261 #endif
2262                       queue_push(&iq, p);
2263                     }
2264                 }
2265             }
2266         }
2267       if (!iq.count)
2268         {
2269           /* supplements pass */
2270           for (ip = solv->installed->start; ip < solv->installed->end; ip++)
2271             {
2272               if (!MAPTST(&installedm, ip))
2273                 continue;
2274               s = pool->solvables + ip;
2275               if (!s->supplements)
2276                 continue;
2277               if (!MAPTST(&im, ip))
2278                 continue;
2279               supp = s->repo->idarraydata + s->supplements;
2280               while ((sup = *supp++) != 0)
2281                 if (!dep_possible(solv, sup, &im) && dep_possible(solv, sup, &installedm))
2282                   break;
2283               /* no longer supplemented, also erase */
2284               if (sup)
2285                 {
2286 #ifdef CLEANDEPSDEBUG
2287                   printf("%s supplemented\n", pool_solvid2str(pool, ip));
2288 #endif
2289                   queue_push(&iq, ip);
2290                 }
2291             }
2292         }
2293     }
2294
2295   /* turn userinstalled into remove set for pruning */
2296   map_empty(&userinstalled);
2297   for (rid = solv->jobrules; rid < solv->jobrules_end; rid++)
2298     {
2299       r = solv->rules + rid;
2300       if (r->p >= 0 || r->d != 0)
2301         continue;       /* disabled or not erase */
2302       p = -r->p;
2303       MAPCLR(&im, p);
2304       if (pool->solvables[p].repo == installed)
2305         MAPSET(&userinstalled, p - installed->start);
2306     }
2307   for (p = installed->start; p < installed->end; p++)
2308     if (MAPTST(&im, p))
2309       queue_push(&iq, p);
2310   for (rid = solv->jobrules; rid < solv->jobrules_end; rid++)
2311     {
2312       r = solv->rules + rid;
2313       if (r->d < 0)
2314         continue;
2315       FOR_RULELITERALS(p, jp, r)
2316         if (p > 0)
2317           queue_push(&iq, p);
2318     }
2319   /* also put directly addressed packages on the install queue
2320    * so we can mark patterns as installed */
2321   for (i = 0; i < job->count; i += 2)
2322     {
2323       how = job->elements[i];
2324       if ((how & SOLVER_JOBMASK) == SOLVER_USERINSTALLED)
2325         {
2326           what = job->elements[i + 1];
2327           select = how & SOLVER_SELECTMASK;
2328           if (select == SOLVER_SOLVABLE && pool->solvables[what].repo != installed)
2329             queue_push(&iq, what);
2330         }
2331     }
2332   while (iq.count)
2333     {
2334       ip = queue_shift(&iq);
2335       s = pool->solvables + ip;
2336 #ifdef CLEANDEPSDEBUG
2337       printf("bye %s\n", pool_solvable2str(pool, s));
2338 #endif
2339       if (s->requires)
2340         {
2341           reqp = s->repo->idarraydata + s->requires;
2342           while ((req = *reqp++) != 0)
2343             {
2344               FOR_PROVIDES(p, pp, req)
2345                 {
2346                   if (!MAPTST(&im, p) && MAPTST(&installedm, p))
2347                     {
2348                       if (p == ip)
2349                         continue;
2350                       if (MAPTST(&userinstalled, p - installed->start))
2351                         continue;
2352 #ifdef CLEANDEPSDEBUG
2353                       printf("%s requires %s\n", pool_solvid2str(pool, ip), pool_solvid2str(pool, p));
2354 #endif
2355                       MAPSET(&im, p);
2356                       queue_push(&iq, p);
2357                     }
2358                 }
2359             }
2360         }
2361       if (s->recommends)
2362         {
2363           reqp = s->repo->idarraydata + s->recommends;
2364           while ((req = *reqp++) != 0)
2365             {
2366               FOR_PROVIDES(p, pp, req)
2367                 {
2368                   if (!MAPTST(&im, p) && MAPTST(&installedm, p))
2369                     {
2370                       if (p == ip)
2371                         continue;
2372                       if (MAPTST(&userinstalled, p - installed->start))
2373                         continue;
2374 #ifdef CLEANDEPSDEBUG
2375                       printf("%s recommends %s\n", pool_solvid2str(pool, ip), pool_solvid2str(pool, p));
2376 #endif
2377                       MAPSET(&im, p);
2378                       queue_push(&iq, p);
2379                     }
2380                 }
2381             }
2382         }
2383       if (!iq.count)
2384         {
2385           /* supplements pass */
2386           for (ip = installed->start; ip < installed->end; ip++)
2387             {
2388               if (!MAPTST(&installedm, ip))
2389                 continue;
2390               if (MAPTST(&userinstalled, ip - installed->start))
2391                 continue;
2392               s = pool->solvables + ip;
2393               if (!s->supplements)
2394                 continue;
2395               if (MAPTST(&im, ip) || !MAPTST(&installedm, ip))
2396                 continue;
2397               supp = s->repo->idarraydata + s->supplements;
2398               while ((sup = *supp++) != 0)
2399                 if (dep_possible(solv, sup, &im))
2400                   break;
2401               if (sup)
2402                 {
2403 #ifdef CLEANDEPSDEBUG
2404                   printf("%s supplemented\n", pool_solvid2str(pool, ip));
2405 #endif
2406                   MAPSET(&im, ip);
2407                   queue_push(&iq, ip);
2408                 }
2409             }
2410         }
2411     }
2412
2413   queue_free(&iq);
2414   for (p = installed->start; p < installed->end; p++)
2415     {
2416       if (pool->solvables[p].repo != installed)
2417         continue;
2418       if (!MAPTST(&im, p))
2419         MAPSET(&solv->cleandepsmap, p - installed->start);
2420     }
2421   map_free(&im);
2422   map_free(&installedm);
2423   map_free(&userinstalled);
2424 }
2425
2426
2427 /* EOF */