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 "policy.h"
  26 #include "solverdebug.h"
  27
  28 #define RULES_BLOCK 63
  29
  30 static void addrpmruleinfo(Solver *solv, Id p, Id d, int type, Id dep);
  31
  32 /*-------------------------------------------------------------------
  33  * Check if dependency is possible
  34  *
  35  * mirrors solver_dep_fulfilled but uses map m instead of the decisionmap
  36  */
  37
  38 static inline int
  39 dep_possible(Solver *solv, Id dep, Map *m)
  40 {
  41   Pool *pool = solv->pool;
  42   Id p, pp;
  43
  44   if (ISRELDEP(dep))
  45     {
  46       Reldep *rd = GETRELDEP(pool, dep);
  47       if (rd->flags == REL_AND)
  48         {
  49           if (!dep_possible(solv, rd->name, m))
  50             return 0;
  51           return dep_possible(solv, rd->evr, m);
  52         }
  53       if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
  54         return solver_splitprovides(solv, rd->evr);
  55       if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
  56         return solver_dep_installed(solv, rd->evr);
  57     }
  58   FOR_PROVIDES(p, pp, dep)
  59     {
  60       if (MAPTST(m, p))
  61         return 1;
  62     }
  63   return 0;
  64 }
  65
  66 /********************************************************************
  67  *
  68  * Rule handling
  69  *
  70  * - unify rules, remove duplicates
  71  */
  72
  73 /*-------------------------------------------------------------------
  74  *
  75  * compare rules for unification sort
  76  *
  77  */
  78
  79 static int
  80 unifyrules_sortcmp(const void *ap, const void *bp, void *dp)
  81 {
  82   Pool *pool = dp;
  83   Rule *a = (Rule *)ap;
  84   Rule *b = (Rule *)bp;
  85   Id *ad, *bd;
  86   int x;
  87
  88   x = a->p - b->p;
  89   if (x)
  90     return x;                          /* p differs */
  91
  92   /* identical p */
  93   if (a->d == 0 && b->d == 0)
  94     return a->w2 - b->w2;              /* assertion: return w2 diff */
  95
  96   if (a->d == 0)                       /* a is assertion, b not */
  97     {
  98       x = a->w2 - pool->whatprovidesdata[b->d];
  99       return x ? x : -1;
 100     }
 101
 102   if (b->d == 0)                       /* b is assertion, a not */
 103     {
 104       x = pool->whatprovidesdata[a->d] - b->w2;
 105       return x ? x : 1;
 106     }
 107
 108   /* compare whatprovidesdata */
 109   ad = pool->whatprovidesdata + a->d;
 110   bd = pool->whatprovidesdata + b->d;
 111   while (*bd)
 112     if ((x = *ad++ - *bd++) != 0)
 113       return x;
 114   return *ad;
 115 }
 116
 117 int
 118 solver_samerule(Solver *solv, Rule *r1, Rule *r2)
 119 {
 120   return unifyrules_sortcmp(r1, r2, solv->pool);
 121 }
 122
 123
 124 /*-------------------------------------------------------------------
 125  *
 126  * unify rules
 127  * go over all rules and remove duplicates
 128  */
 129
 130 void
 131 solver_unifyrules(Solver *solv)
 132 {
 133   Pool *pool = solv->pool;
 134   int i, j;
 135   Rule *ir, *jr;
 136
 137   if (solv->nrules <= 1)               /* nothing to unify */
 138     return;
 139
 140   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- unifyrules -----\n");
 141
 142   /* sort rules first */
 143   sat_sort(solv->rules + 1, solv->nrules - 1, sizeof(Rule), unifyrules_sortcmp, solv->pool);
 144
 145   /* prune rules
 146    * i = unpruned
 147    * j = pruned
 148    */
 149   jr = 0;
 150   for (i = j = 1, ir = solv->rules + i; i < solv->nrules; i++, ir++)
 151     {
 152       if (jr && !unifyrules_sortcmp(ir, jr, pool))
 153         continue;                      /* prune! */
 154       jr = solv->rules + j++;          /* keep! */
 155       if (ir != jr)
 156         *jr = *ir;
 157     }
 158
 159   /* reduced count from nrules to j rules */
 160   POOL_DEBUG(SAT_DEBUG_STATS, "pruned rules from %d to %d\n", solv->nrules, j);
 161
 162   /* adapt rule buffer */
 163   solv->nrules = j;
 164   solv->rules = sat_extend_resize(solv->rules, solv->nrules, sizeof(Rule), RULES_BLOCK);
 165
 166   /*
 167    * debug: log rule statistics
 168    */
 169   IF_POOLDEBUG (SAT_DEBUG_STATS)
 170     {
 171       int binr = 0;
 172       int lits = 0;
 173       Id *dp;
 174       Rule *r;
 175
 176       for (i = 1; i < solv->nrules; i++)
 177         {
 178           r = solv->rules + i;
 179           if (r->d == 0)
 180             binr++;
 181           else
 182             {
 183               dp = solv->pool->whatprovidesdata + r->d;
 184               while (*dp++)
 185                 lits++;
 186             }
 187         }
 188       POOL_DEBUG(SAT_DEBUG_STATS, "  binary: %d\n", binr);
 189       POOL_DEBUG(SAT_DEBUG_STATS, "  normal: %d, %d literals\n", solv->nrules - 1 - binr, lits);
 190     }
 191   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- unifyrules end -----\n");
 192 }
 193
 194 #if 0
 195
 196 /*
 197  * hash rule
 198  */
 199
 200 static Hashval
 201 hashrule(Solver *solv, Id p, Id d, int n)
 202 {
 203   unsigned int x = (unsigned int)p;
 204   int *dp;
 205
 206   if (n <= 1)
 207     return (x * 37) ^ (unsigned int)d;
 208   dp = solv->pool->whatprovidesdata + d;
 209   while (*dp)
 210     x = (x * 37) ^ (unsigned int)*dp++;
 211   return x;
 212 }
 213 #endif
 214
 215
 216 /*-------------------------------------------------------------------
 217  *
 218  */
 219
 220 /*
 221  * add rule
 222  *  p = direct literal; always < 0 for installed rpm rules
 223  *  d, if < 0 direct literal, if > 0 offset into whatprovides, if == 0 rule is assertion (look at p only)
 224  *
 225  *
 226  * A requires b, b provided by B1,B2,B3 => (-A|B1|B2|B3)
 227  *
 228  * p < 0 : pkg id of A
 229  * d > 0 : Offset in whatprovidesdata (list of providers of b)
 230  *
 231  * A conflicts b, b provided by B1,B2,B3 => (-A|-B1), (-A|-B2), (-A|-B3)
 232  * p < 0 : pkg id of A
 233  * d < 0 : Id of solvable (e.g. B1)
 234  *
 235  * d == 0: unary rule, assertion => (A) or (-A)
 236  *
 237  *   Install:    p > 0, d = 0   (A)             user requested install
 238  *   Remove:     p < 0, d = 0   (-A)            user requested remove (also: uninstallable)
 239  *   Requires:   p < 0, d > 0   (-A|B1|B2|...)  d: <list of providers for requirement of p>
 240  *   Updates:    p > 0, d > 0   (A|B1|B2|...)   d: <list of updates for solvable p>
 241  *   Conflicts:  p < 0, d < 0   (-A|-B)         either p (conflict issuer) or d (conflict provider) (binary rule)
 242  *                                              also used for obsoletes
 243  *   ?:          p > 0, d < 0   (A|-B)
 244  *   No-op ?:    p = 0, d = 0   (null)          (used as policy rule placeholder)
 245  *
 246  *   resulting watches:
 247  *   ------------------
 248  *   Direct assertion (no watch needed)( if d <0 ) --> d = 0, w1 = p, w2 = 0
 249  *   Binary rule: p = first literal, d = 0, w2 = second literal, w1 = p
 250  *   every other : w1 = p, w2 = whatprovidesdata[d];
 251  *   Disabled rule: w1 = 0
 252  *
 253  *   always returns a rule for non-rpm rules
 254  */
 255
 256 Rule *
 257 solver_addrule(Solver *solv, Id p, Id d)
 258 {
 259   Pool *pool = solv->pool;
 260   Rule *r = 0;
 261   Id *dp = 0;
 262
 263   int n = 0;                           /* number of literals in rule - 1
 264                                           0 = direct assertion (single literal)
 265                                           1 = binary rule
 266                                           >1 =
 267                                         */
 268
 269   /* it often happenes that requires lead to adding the same rpm rule
 270    * multiple times, so we prune those duplicates right away to make
 271    * the work for unifyrules a bit easier */
 272
 273   if (solv->nrules                      /* we already have rules */
 274       && !solv->rpmrules_end)           /* but are not done with rpm rules */
 275     {
 276       r = solv->rules + solv->nrules - 1;   /* get the last added rule */
 277       if (r->p == p && r->d == d && d != 0)   /* identical and not user requested */
 278         return r;
 279     }
 280
 281     /*
 282      * compute number of literals (n) in rule
 283      */
 284
 285   if (d < 0)
 286     {
 287       /* always a binary rule */
 288       if (p == d)
 289         return 0;                      /* ignore self conflict */
 290       n = 1;
 291     }
 292   else if (d > 0)
 293     {
 294       for (dp = pool->whatprovidesdata + d; *dp; dp++, n++)
 295         if (*dp == -p)
 296           return 0;                     /* rule is self-fulfilling */
 297
 298       if (n == 1)   /* have single provider */
 299         d = dp[-1];                     /* take single literal */
 300     }
 301
 302   if (n == 1 && p > d && !solv->rpmrules_end)
 303     {
 304       /* smallest literal first so we can find dups */
 305       n = p; p = d; d = n;             /* p <-> d */
 306       n = 1;                           /* re-set n, was used as temp var */
 307     }
 308
 309   /*
 310    * check for duplicate
 311    */
 312
 313   /* check if the last added rule (r) is exactly the same as what we're looking for. */
 314   if (r && n == 1 && !r->d && r->p == p && r->w2 == d)
 315     return r;  /* binary rule */
 316
 317     /* have n-ary rule with same first literal, check other literals */
 318   if (r && n > 1 && r->d && r->p == p)
 319     {
 320       /* Rule where d is an offset in whatprovidesdata */
 321       Id *dp2;
 322       if (d == r->d)
 323         return r;
 324       dp2 = pool->whatprovidesdata + r->d;
 325       for (dp = pool->whatprovidesdata + d; *dp; dp++, dp2++)
 326         if (*dp != *dp2)
 327           break;
 328       if (*dp == *dp2)
 329         return r;
 330    }
 331
 332   /*
 333    * allocate new rule
 334    */
 335
 336   /* extend rule buffer */
 337   solv->rules = sat_extend(solv->rules, solv->nrules, 1, sizeof(Rule), RULES_BLOCK);
 338   r = solv->rules + solv->nrules++;    /* point to rule space */
 339
 340     /*
 341      * r = new rule
 342      */
 343
 344   r->p = p;
 345   if (n == 0)
 346     {
 347       /* direct assertion, no watch needed */
 348       r->d = 0;
 349       r->w1 = p;
 350       r->w2 = 0;
 351     }
 352   else if (n == 1)
 353     {
 354       /* binary rule */
 355       r->d = 0;
 356       r->w1 = p;
 357       r->w2 = d;
 358     }
 359   else
 360     {
 361       r->d = d;
 362       r->w1 = p;
 363       r->w2 = pool->whatprovidesdata[d];
 364     }
 365   r->n1 = 0;
 366   r->n2 = 0;
 367
 368   IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION)
 369     {
 370       POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "  Add rule: ");
 371       solver_printrule(solv, SAT_DEBUG_RULE_CREATION, r);
 372     }
 373
 374   return r;
 375 }
 376
 377
 378 /******************************************************************************
 379  ***
 380  *** rpm rule part: create rules representing the package dependencies
 381  ***
 382  ***/
 383
 384 /*
 385  *  special multiversion patch conflict handling:
 386  *  a patch conflict is also satisfied, if some other
 387  *  version with the same name/arch that doesn't conflict
 388  *  get's installed. The generated rule is thus:
 389  *  -patch|-cpack|opack1|opack2|...
 390  */
 391 static Id
 392 makemultiversionconflict(Solver *solv, Id n, Id con)
 393 {
 394   Pool *pool = solv->pool;
 395   Solvable *s, *sn;
 396   Queue q;
 397   Id p, pp, qbuf[64];
 398
 399   sn = pool->solvables + n;
 400   queue_init_buffer(&q, qbuf, sizeof(qbuf)/sizeof(*qbuf));
 401   queue_push(&q, -n);
 402   FOR_PROVIDES(p, pp, sn->name)
 403     {
 404       s = pool->solvables + p;
 405       if (s->name != sn->name || s->arch != sn->arch)
 406         continue;
 407       if (!MAPTST(&solv->noobsoletes, p))
 408         continue;
 409       if (pool_match_nevr(pool, pool->solvables + p, con))
 410         continue;
 411       /* here we have a multiversion solvable that doesn't conflict */
 412       /* thus we're not in conflict if it is installed */
 413       queue_push(&q, p);
 414     }
 415   if (q.count == 1)
 416     return -n;  /* no other package found, generate normal conflict */
 417   return pool_queuetowhatprovides(pool, &q);
 418 }
 419
 420 static inline void
 421 addrpmrule(Solver *solv, Id p, Id d, int type, Id dep)
 422 {
 423   if (!solv->ruleinfoq)
 424     solver_addrule(solv, p, d);
 425   else
 426     addrpmruleinfo(solv, p, d, type, dep);
 427 }
 428
 429 /*-------------------------------------------------------------------
 430  *
 431  * add (install) rules for solvable
 432  *
 433  * s: Solvable for which to add rules
 434  * m: m[s] = 1 for solvables which have rules, prevent rule duplication
 435  *
 436  * Algorithm: 'visit all nodes of a graph'. The graph nodes are
 437  *  solvables, the edges their dependencies.
 438  *  Starting from an installed solvable, this will create all rules
 439  *  representing the graph created by the solvables dependencies.
 440  *
 441  * for unfulfilled requirements, conflicts, obsoletes,....
 442  * add a negative assertion for solvables that are not installable
 443  *
 444  * It will also create rules for all solvables referenced by 's'
 445  *  i.e. descend to all providers of requirements of 's'
 446  *
 447  */
 448
 449 void
 450 solver_addrpmrulesforsolvable(Solver *solv, Solvable *s, Map *m)
 451 {
 452   Pool *pool = solv->pool;
 453   Repo *installed = solv->installed;
 454
 455   /* 'work' queue. keeps Ids of solvables we still have to work on.
 456      And buffer for it. */
 457   Queue workq;
 458   Id workqbuf[64];
 459
 460   int i;
 461     /* if to add rules for broken deps ('rpm -V' functionality)
 462      * 0 = yes, 1 = no
 463      */
 464   int dontfix;
 465     /* Id var and pointer for each dependency
 466      * (not used in parallel)
 467      */
 468   Id req, *reqp;
 469   Id con, *conp;
 470   Id obs, *obsp;
 471   Id rec, *recp;
 472   Id sug, *sugp;
 473   Id p, pp;             /* whatprovides loops */
 474   Id *dp;               /* ptr to 'whatprovides' */
 475   Id n;                 /* Id for current solvable 's' */
 476
 477   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforsolvable -----\n");
 478
 479   queue_init_buffer(&workq, workqbuf, sizeof(workqbuf)/sizeof(*workqbuf));
 480   queue_push(&workq, s - pool->solvables);      /* push solvable Id to work queue */
 481
 482   /* loop until there's no more work left */
 483   while (workq.count)
 484     {
 485       /*
 486        * n: Id of solvable
 487        * s: Pointer to solvable
 488        */
 489
 490       n = queue_shift(&workq);          /* 'pop' next solvable to work on from queue */
 491       if (m)
 492         {
 493           if (MAPTST(m, n))             /* continue if already visited */
 494             continue;
 495           MAPSET(m, n);                 /* mark as visited */
 496         }
 497
 498       s = pool->solvables + n;          /* s = Solvable in question */
 499
 500       dontfix = 0;
 501       if (installed                     /* Installed system available */
 502           && !solv->fixsystem           /* NOT repair errors in rpm dependency graph */
 503           && s->repo == installed)      /* solvable is installed? */
 504         {
 505           dontfix = 1;                  /* dont care about broken rpm deps */
 506         }
 507
 508       if (!dontfix
 509           && s->arch != ARCH_SRC
 510           && s->arch != ARCH_NOSRC
 511           && !pool_installable(pool, s))
 512         {
 513           POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "package %s [%d] is not installable\n", solvable2str(pool, s), (Id)(s - pool->solvables));
 514           addrpmrule(solv, -n, 0, SOLVER_RULE_RPM_NOT_INSTALLABLE, 0);
 515         }
 516
 517       /* yet another SUSE hack, sigh */
 518       if (pool->nscallback && !strncmp("product:", id2str(pool, s->name), 8))
 519         {
 520           Id buddy = pool->nscallback(pool, pool->nscallbackdata, NAMESPACE_PRODUCTBUDDY, n);
 521           if (buddy > 0 && buddy != SYSTEMSOLVABLE && buddy != n && buddy < pool->nsolvables)
 522             {
 523               addrpmrule(solv, n, -buddy, SOLVER_RULE_RPM_PACKAGE_REQUIRES, solvable_selfprovidedep(pool->solvables + n));
 524               addrpmrule(solv, buddy, -n, SOLVER_RULE_RPM_PACKAGE_REQUIRES, solvable_selfprovidedep(pool->solvables + buddy));
 525               if (m && !MAPTST(m, buddy))
 526                 queue_push(&workq, buddy);
 527             }
 528         }
 529
 530       /*-----------------------------------------
 531        * check requires of s
 532        */
 533
 534       if (s->requires)
 535         {
 536           reqp = s->repo->idarraydata + s->requires;
 537           while ((req = *reqp++) != 0)            /* go through all requires */
 538             {
 539               if (req == SOLVABLE_PREREQMARKER)   /* skip the marker */
 540                 continue;
 541
 542               /* find list of solvables providing 'req' */
 543               dp = pool_whatprovides_ptr(pool, req);
 544
 545               if (*dp == SYSTEMSOLVABLE)          /* always installed */
 546                 continue;
 547
 548               if (dontfix)
 549                 {
 550                   /* the strategy here is to not insist on dependencies
 551                    * that are already broken. so if we find one provider
 552                    * that was already installed, we know that the
 553                    * dependency was not broken before so we enforce it */
 554
 555                   /* check if any of the providers for 'req' is installed */
 556                   for (i = 0; (p = dp[i]) != 0; i++)
 557                     {
 558                       if (pool->solvables[p].repo == installed)
 559                         break;          /* provider was installed */
 560                     }
 561                   /* didn't find an installed provider: previously broken dependency */
 562                   if (!p)
 563                     {
 564                       POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "ignoring broken requires %s of installed package %s\n", dep2str(pool, req), solvable2str(pool, s));
 565                       continue;
 566                     }
 567                 }
 568
 569               if (!*dp)
 570                 {
 571                   /* nothing provides req! */
 572                   POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "package %s [%d] is not installable (%s)\n", solvable2str(pool, s), (Id)(s - pool->solvables), dep2str(pool, req));
 573                   addrpmrule(solv, -n, 0, SOLVER_RULE_RPM_NOTHING_PROVIDES_DEP, req);
 574                   continue;
 575                 }
 576
 577               IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION)
 578                 {
 579                   POOL_DEBUG(SAT_DEBUG_RULE_CREATION,"  %s requires %s\n", solvable2str(pool, s), dep2str(pool, req));
 580                   for (i = 0; dp[i]; i++)
 581                     POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "   provided by %s\n", solvid2str(pool, dp[i]));
 582                 }
 583
 584               /* add 'requires' dependency */
 585               /* rule: (-requestor|provider1|provider2|...|providerN) */
 586               addrpmrule(solv, -n, dp - pool->whatprovidesdata, SOLVER_RULE_RPM_PACKAGE_REQUIRES, req);
 587
 588               /* descend the dependency tree
 589                  push all non-visited providers on the work queue */
 590               if (m)
 591                 {
 592                   for (; *dp; dp++)
 593                     {
 594                       if (!MAPTST(m, *dp))
 595                         queue_push(&workq, *dp);
 596                     }
 597                 }
 598
 599             } /* while, requirements of n */
 600
 601         } /* if, requirements */
 602
 603       /* that's all we check for src packages */
 604       if (s->arch == ARCH_SRC || s->arch == ARCH_NOSRC)
 605         continue;
 606
 607       /*-----------------------------------------
 608        * check conflicts of s
 609        */
 610
 611       if (s->conflicts)
 612         {
 613           int ispatch = 0;
 614
 615           /* we treat conflicts in patches a bit differen:
 616            * - nevr matching
 617            * - multiversion handling
 618            * XXX: we should really handle this different, looking
 619            * at the name is a bad hack
 620            */
 621           if (!strncmp("patch:", id2str(pool, s->name), 6))
 622             ispatch = 1;
 623           conp = s->repo->idarraydata + s->conflicts;
 624           /* foreach conflicts of 's' */
 625           while ((con = *conp++) != 0)
 626             {
 627               /* foreach providers of a conflict of 's' */
 628               FOR_PROVIDES(p, pp, con)
 629                 {
 630                   if (ispatch && !pool_match_nevr(pool, pool->solvables + p, con))
 631                     continue;
 632                   /* dontfix: dont care about conflicts with already installed packs */
 633                   if (dontfix && pool->solvables[p].repo == installed)
 634                     continue;
 635                   /* p == n: self conflict */
 636                   if (p == n && !pool->allowselfconflicts)
 637                     {
 638                       if (ISRELDEP(con))
 639                         {
 640                           Reldep *rd = GETRELDEP(pool, con);
 641                           if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_OTHERPROVIDERS)
 642                             continue;
 643                         }
 644                       p = 0;    /* make it a negative assertion, aka 'uninstallable' */
 645                     }
 646                   if (p && ispatch && solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p) && ISRELDEP(con))
 647                     {
 648                       /* our patch conflicts with a noobsoletes (aka multiversion) package */
 649                       p = -makemultiversionconflict(solv, p, con);
 650                     }
 651                  /* rule: -n|-p: either solvable _or_ provider of conflict */
 652                   addrpmrule(solv, -n, -p, p ? SOLVER_RULE_RPM_PACKAGE_CONFLICT : SOLVER_RULE_RPM_SELF_CONFLICT, con);
 653                 }
 654             }
 655         }
 656
 657       /*-----------------------------------------
 658        * check obsoletes if not installed
 659        * (only installation will trigger the obsoletes in rpm)
 660        */
 661       if (!installed || pool->solvables[n].repo != installed)
 662         {                              /* not installed */
 663           int noobs = solv->noobsoletes.size && MAPTST(&solv->noobsoletes, n);
 664           if (s->obsoletes && !noobs)
 665             {
 666               obsp = s->repo->idarraydata + s->obsoletes;
 667               /* foreach obsoletes */
 668               while ((obs = *obsp++) != 0)
 669                 {
 670                   /* foreach provider of an obsoletes of 's' */
 671                   FOR_PROVIDES(p, pp, obs)
 672                     {
 673                       Solvable *ps = pool->solvables + p;
 674                       if (!pool->obsoleteusesprovides /* obsoletes are matched names, not provides */
 675                           && !pool_match_nevr(pool, ps, obs))
 676                         continue;
 677                       if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
 678                         continue;
 679                       addrpmrule(solv, -n, -p, SOLVER_RULE_RPM_PACKAGE_OBSOLETES, obs);
 680                     }
 681                 }
 682             }
 683           FOR_PROVIDES(p, pp, s->name)
 684             {
 685               Solvable *ps = pool->solvables + p;
 686               /* we still obsolete packages with same nevra, like rpm does */
 687               /* (actually, rpm mixes those packages. yuck...) */
 688               if (noobs && (s->name != ps->name || s->evr != ps->evr || s->arch != ps->arch))
 689                 continue;
 690               if (!pool->implicitobsoleteusesprovides && s->name != ps->name)
 691                 continue;
 692               if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
 693                 continue;
 694               if (s->name == ps->name)
 695                 addrpmrule(solv, -n, -p, SOLVER_RULE_RPM_SAME_NAME, 0);
 696               else
 697                 addrpmrule(solv, -n, -p, SOLVER_RULE_RPM_IMPLICIT_OBSOLETES, s->name);
 698             }
 699         }
 700
 701       /*-----------------------------------------
 702        * add recommends to the work queue
 703        */
 704       if (s->recommends && m)
 705         {
 706           recp = s->repo->idarraydata + s->recommends;
 707           while ((rec = *recp++) != 0)
 708             {
 709               FOR_PROVIDES(p, pp, rec)
 710                 if (!MAPTST(m, p))
 711                   queue_push(&workq, p);
 712             }
 713         }
 714       if (s->suggests && m)
 715         {
 716           sugp = s->repo->idarraydata + s->suggests;
 717           while ((sug = *sugp++) != 0)
 718             {
 719               FOR_PROVIDES(p, pp, sug)
 720                 if (!MAPTST(m, p))
 721                   queue_push(&workq, p);
 722             }
 723         }
 724     }
 725   queue_free(&workq);
 726   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforsolvable end -----\n");
 727 }
 728
 729
 730 /*-------------------------------------------------------------------
 731  *
 732  * Add package rules for weak rules
 733  *
 734  * m: visited solvables
 735  */
 736
 737 void
 738 solver_addrpmrulesforweak(Solver *solv, Map *m)
 739 {
 740   Pool *pool = solv->pool;
 741   Solvable *s;
 742   Id sup, *supp;
 743   int i, n;
 744
 745   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforweak -----\n");
 746     /* foreach solvable in pool */
 747   for (i = n = 1; n < pool->nsolvables; i++, n++)
 748     {
 749       if (i == pool->nsolvables)                /* wrap i */
 750         i = 1;
 751       if (MAPTST(m, i))                         /* been there */
 752         continue;
 753
 754       s = pool->solvables + i;
 755       if (!pool_installable(pool, s))           /* only look at installable ones */
 756         continue;
 757
 758       sup = 0;
 759       if (s->supplements)
 760         {
 761           /* find possible supplements */
 762           supp = s->repo->idarraydata + s->supplements;
 763           while ((sup = *supp++) != ID_NULL)
 764             if (dep_possible(solv, sup, m))
 765               break;
 766         }
 767
 768       /* if nothing found, check for enhances */
 769       if (!sup && s->enhances)
 770         {
 771           supp = s->repo->idarraydata + s->enhances;
 772           while ((sup = *supp++) != ID_NULL)
 773             if (dep_possible(solv, sup, m))
 774               break;
 775         }
 776       /* if nothing found, goto next solvables */
 777       if (!sup)
 778         continue;
 779       solver_addrpmrulesforsolvable(solv, s, m);
 780       n = 0;                    /* check all solvables again */
 781     }
 782   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforweak end -----\n");
 783 }
 784
 785
 786 /*-------------------------------------------------------------------
 787  *
 788  * add package rules for possible updates
 789  *
 790  * s: solvable
 791  * m: map of already visited solvables
 792  * allow_all: 0 = dont allow downgrades, 1 = allow all candidates
 793  */
 794
 795 void
 796 solver_addrpmrulesforupdaters(Solver *solv, Solvable *s, Map *m, int allow_all)
 797 {
 798   Pool *pool = solv->pool;
 799   int i;
 800     /* queue and buffer for it */
 801   Queue qs;
 802   Id qsbuf[64];
 803
 804   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforupdaters -----\n");
 805
 806   queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
 807     /* find update candidates for 's' */
 808   policy_findupdatepackages(solv, s, &qs, allow_all);
 809     /* add rule for 's' if not already done */
 810   if (!MAPTST(m, s - pool->solvables))
 811     solver_addrpmrulesforsolvable(solv, s, m);
 812     /* foreach update candidate, add rule if not already done */
 813   for (i = 0; i < qs.count; i++)
 814     if (!MAPTST(m, qs.elements[i]))
 815       solver_addrpmrulesforsolvable(solv, pool->solvables + qs.elements[i], m);
 816   queue_free(&qs);
 817
 818   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforupdaters -----\n");
 819 }
 820
 821
 822 /***********************************************************************
 823  ***
 824  ***  Update/Feature rule part
 825  ***
 826  ***  Those rules make sure an installed package isn't silently deleted
 827  ***
 828  ***/
 829
 830 static Id
 831 finddistupgradepackages(Solver *solv, Solvable *s, Queue *qs, int allow_all)
 832 {
 833   Pool *pool = solv->pool;
 834   int i;
 835
 836   policy_findupdatepackages(solv, s, qs, allow_all);
 837   if (!qs->count)
 838     {
 839       if (allow_all)
 840         return 0;       /* orphaned, don't create feature rule */
 841       /* check if this is an orphaned package */
 842       policy_findupdatepackages(solv, s, qs, 1);
 843       if (!qs->count)
 844         return 0;       /* orphaned, don't create update rule */
 845       qs->count = 0;
 846       return -SYSTEMSOLVABLE;   /* supported but not installable */
 847     }
 848   if (allow_all)
 849     return s - pool->solvables;
 850   /* check if it is ok to keep the installed package */
 851   for (i = 0; i < qs->count; i++)
 852     {
 853       Solvable *ns = pool->solvables + qs->elements[i];
 854       if (s->evr == ns->evr && solvable_identical(s, ns))
 855         return s - pool->solvables;
 856     }
 857   /* nope, it must be some other package */
 858   return -SYSTEMSOLVABLE;
 859 }
 860
 861 /* add packages from the dup repositories to the update candidates
 862  * this isn't needed for the global dup mode as all packages are
 863  * from dup repos in that case */
 864 static void
 865 addduppackages(Solver *solv, Solvable *s, Queue *qs)
 866 {
 867   Queue dupqs;
 868   Id p, dupqsbuf[64];
 869   int i;
 870   int oldnoupdateprovide = solv->noupdateprovide;
 871
 872   queue_init_buffer(&dupqs, dupqsbuf, sizeof(dupqsbuf)/sizeof(*dupqsbuf));
 873   solv->noupdateprovide = 1;
 874   policy_findupdatepackages(solv, s, &dupqs, 2);
 875   solv->noupdateprovide = oldnoupdateprovide;
 876   for (i = 0; i < dupqs.count; i++)
 877     {
 878       p = dupqs.elements[i];
 879       if (MAPTST(&solv->dupmap, p))
 880         queue_pushunique(qs, p);
 881     }
 882   queue_free(&dupqs);
 883 }
 884
 885 /*-------------------------------------------------------------------
 886  *
 887  * add rule for update
 888  *   (A|A1|A2|A3...)  An = update candidates for A
 889  *
 890  * s = (installed) solvable
 891  */
 892
 893 void
 894 solver_addupdaterule(Solver *solv, Solvable *s, int allow_all)
 895 {
 896   /* installed packages get a special upgrade allowed rule */
 897   Pool *pool = solv->pool;
 898   Id p, d;
 899   Queue qs;
 900   Id qsbuf[64];
 901
 902   POOL_DEBUG(SAT_DEBUG_SCHUBI, "-----  addupdaterule -----\n");
 903   queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
 904   p = s - pool->solvables;
 905   /* find update candidates for 's' */
 906   if (solv->distupgrade)
 907     p = finddistupgradepackages(solv, s, &qs, allow_all);
 908   else
 909     policy_findupdatepackages(solv, s, &qs, allow_all);
 910   if (!allow_all && !solv->distupgrade && solv->dupinvolvedmap.size && MAPTST(&solv->dupinvolvedmap, p))
 911     addduppackages(solv, s, &qs);
 912
 913   if (!allow_all && qs.count && solv->noobsoletes.size)
 914     {
 915       int i, j;
 916
 917       d = pool_queuetowhatprovides(pool, &qs);
 918       /* filter out all noobsoletes packages as they don't update */
 919       for (i = j = 0; i < qs.count; i++)
 920         {
 921           if (MAPTST(&solv->noobsoletes, qs.elements[i]))
 922             {
 923               /* it's ok if they have same nevra */
 924               Solvable *ps = pool->solvables + qs.elements[i];
 925               if (ps->name != s->name || ps->evr != s->evr || ps->arch != s->arch)
 926                 continue;
 927             }
 928           qs.elements[j++] = qs.elements[i];
 929         }
 930       if (j == 0 && p == -SYSTEMSOLVABLE && solv->distupgrade)
 931         {
 932           queue_push(&solv->orphaned, s - pool->solvables);     /* treat as orphaned */
 933           j = qs.count;
 934         }
 935       if (j < qs.count)
 936         {
 937           if (d && solv->updatesystem && solv->installed && s->repo == solv->installed)
 938             {
 939               if (!solv->multiversionupdaters)
 940                 solv->multiversionupdaters = sat_calloc(solv->installed->end - solv->installed->start, sizeof(Id));
 941               solv->multiversionupdaters[s - pool->solvables - solv->installed->start] = d;
 942             }
 943           qs.count = j;
 944         }
 945     }
 946   if (qs.count && p == -SYSTEMSOLVABLE)
 947     p = queue_shift(&qs);
 948   d = qs.count ? pool_queuetowhatprovides(pool, &qs) : 0;
 949   queue_free(&qs);
 950   solver_addrule(solv, p, d);   /* allow update of s */
 951   POOL_DEBUG(SAT_DEBUG_SCHUBI, "-----  addupdaterule end -----\n");
 952 }
 953
 954 static inline void
 955 disableupdaterule(Solver *solv, Id p)
 956 {
 957   Rule *r;
 958
 959   MAPSET(&solv->noupdate, p - solv->installed->start);
 960   r = solv->rules + solv->updaterules + (p - solv->installed->start);
 961   if (r->p && r->d >= 0)
 962     solver_disablerule(solv, r);
 963   r = solv->rules + solv->featurerules + (p - solv->installed->start);
 964   if (r->p && r->d >= 0)
 965     solver_disablerule(solv, r);
 966 }
 967
 968 static inline void
 969 reenableupdaterule(Solver *solv, Id p)
 970 {
 971   Pool *pool = solv->pool;
 972   Rule *r;
 973
 974   MAPCLR(&solv->noupdate, p - solv->installed->start);
 975   r = solv->rules + solv->updaterules + (p - solv->installed->start);
 976   if (r->p)
 977     {
 978       if (r->d >= 0)
 979         return;
 980       solver_enablerule(solv, r);
 981       IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
 982         {
 983           POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
 984           solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
 985         }
 986       return;
 987     }
 988   r = solv->rules + solv->featurerules + (p - solv->installed->start);
 989   if (r->p && r->d < 0)
 990     {
 991       solver_enablerule(solv, r);
 992       IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
 993         {
 994           POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
 995           solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
 996         }
 997     }
 998 }
 999
1000
1001 /***********************************************************************
1002  ***
1003  ***  Infarch rule part
1004  ***
1005  ***  Infarch rules make sure the solver uses the best architecture of
1006  ***  a package if multiple archetectures are available
1007  ***
1008  ***/
1009
1010 void
1011 solver_addinfarchrules(Solver *solv, Map *addedmap)
1012 {
1013   Pool *pool = solv->pool;
1014   int first, i, j;
1015   Id p, pp, a, aa, bestarch;
1016   Solvable *s, *ps, *bests;
1017   Queue badq, allowedarchs;
1018
1019   queue_init(&badq);
1020   queue_init(&allowedarchs);
1021   solv->infarchrules = solv->nrules;
1022   for (i = 1; i < pool->nsolvables; i++)
1023     {
1024       if (i == SYSTEMSOLVABLE || !MAPTST(addedmap, i))
1025         continue;
1026       s = pool->solvables + i;
1027       first = i;
1028       bestarch = 0;
1029       bests = 0;
1030       queue_empty(&allowedarchs);
1031       FOR_PROVIDES(p, pp, s->name)
1032         {
1033           ps = pool->solvables + p;
1034           if (ps->name != s->name || !MAPTST(addedmap, p))
1035             continue;
1036           if (p == i)
1037             first = 0;
1038           if (first)
1039             break;
1040           a = ps->arch;
1041           a = (a <= pool->lastarch) ? pool->id2arch[a] : 0;
1042           if (a != 1 && pool->installed && ps->repo == pool->installed)
1043             {
1044               if (!solv->distupgrade)
1045                 queue_pushunique(&allowedarchs, ps->arch);      /* also ok to keep this architecture */
1046               continue;         /* ignore installed solvables when calculating the best arch */
1047             }
1048           if (a && a != 1 && (!bestarch || a < bestarch))
1049             {
1050               bestarch = a;
1051               bests = ps;
1052             }
1053         }
1054       if (first)
1055         continue;
1056       /* speed up common case where installed package already has best arch */
1057       if (allowedarchs.count == 1 && bests && allowedarchs.elements[0] == bests->arch)
1058         allowedarchs.count--;   /* installed arch is best */
1059       queue_empty(&badq);
1060       FOR_PROVIDES(p, pp, s->name)
1061         {
1062           ps = pool->solvables + p;
1063           if (ps->name != s->name || !MAPTST(addedmap, p))
1064             continue;
1065           a = ps->arch;
1066           a = (a <= pool->lastarch) ? pool->id2arch[a] : 0;
1067           if (a != 1 && bestarch && ((a ^ bestarch) & 0xffff0000) != 0)
1068             {
1069               for (j = 0; j < allowedarchs.count; j++)
1070                 {
1071                   aa = allowedarchs.elements[j];
1072                   if (ps->arch == aa)
1073                     break;
1074                   aa = (aa <= pool->lastarch) ? pool->id2arch[aa] : 0;
1075                   if (aa && ((a ^ aa) & 0xffff0000) == 0)
1076                     break;      /* compatible */
1077                 }
1078               if (j == allowedarchs.count)
1079                 queue_push(&badq, p);
1080             }
1081         }
1082       if (!badq.count)
1083         continue;
1084       /* block all solvables in the badq! */
1085       for (j = 0; j < badq.count; j++)
1086         {
1087           p = badq.elements[j];
1088           solver_addrule(solv, -p, 0);
1089         }
1090     }
1091   queue_free(&badq);
1092   queue_free(&allowedarchs);
1093   solv->infarchrules_end = solv->nrules;
1094 }
1095
1096 static inline void
1097 disableinfarchrule(Solver *solv, Id name)
1098 {
1099   Pool *pool = solv->pool;
1100   Rule *r;
1101   int i;
1102   for (i = solv->infarchrules, r = solv->rules + i; i < solv->infarchrules_end; i++, r++)
1103     {
1104       if (r->p < 0 && r->d >= 0 && pool->solvables[-r->p].name == name)
1105         solver_disablerule(solv, r);
1106     }
1107 }
1108
1109 static inline void
1110 reenableinfarchrule(Solver *solv, Id name)
1111 {
1112   Pool *pool = solv->pool;
1113   Rule *r;
1114   int i;
1115   for (i = solv->infarchrules, r = solv->rules + i; i < solv->infarchrules_end; i++, r++)
1116     {
1117       if (r->p < 0 && r->d < 0 && pool->solvables[-r->p].name == name)
1118         {
1119           solver_enablerule(solv, r);
1120           IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
1121             {
1122               POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
1123               solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
1124             }
1125         }
1126     }
1127 }
1128
1129
1130 /***********************************************************************
1131  ***
1132  ***  Dup rule part
1133  ***
1134  ***  Dup rules make sure a package is selected from the specified dup
1135  ***  repositories if an update candidate is included in one of them.
1136  ***
1137  ***/
1138
1139 void
1140 solver_createdupmaps(Solver *solv)
1141 {
1142   Queue *job = &solv->job;
1143   Pool *pool = solv->pool;
1144   Repo *repo;
1145   Id how, what, p, pi, pp, obs, *obsp;
1146   Solvable *s, *ps;
1147   int i;
1148
1149   map_init(&solv->dupmap, pool->nsolvables);
1150   map_init(&solv->dupinvolvedmap, pool->nsolvables);
1151   for (i = 0; i < job->count; i += 2)
1152     {
1153       how = job->elements[i];
1154       what = job->elements[i + 1];
1155       switch (how & SOLVER_JOBMASK)
1156         {
1157         case SOLVER_DISTUPGRADE:
1158           if (what <= 0 || what > pool->nrepos)
1159             break;
1160           repo = pool_id2repo(pool, what);
1161           FOR_REPO_SOLVABLES(repo, p, s)
1162             {
1163               MAPSET(&solv->dupmap, p);
1164               FOR_PROVIDES(pi, pp, s->name)
1165                 {
1166                   ps = pool->solvables + pi;
1167                   if (ps->name != s->name)
1168                     continue;
1169                   MAPSET(&solv->dupinvolvedmap, pi);
1170                 }
1171               if (s->obsoletes)
1172                 {
1173                   /* FIXME: check obsoletes/provides combination */
1174                   obsp = s->repo->idarraydata + s->obsoletes;
1175                   while ((obs = *obsp++) != 0)
1176                     {
1177                       FOR_PROVIDES(pi, pp, obs)
1178                         {
1179                           Solvable *pis = pool->solvables + pi;
1180                           if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, pis, obs))
1181                             continue;
1182                           if (pool->obsoleteusescolors && !pool_colormatch(pool, s, pis))
1183                             continue;
1184                           MAPSET(&solv->dupinvolvedmap, pi);
1185                         }
1186                     }
1187                 }
1188             }
1189           break;
1190         default:
1191           break;
1192         }
1193     }
1194   MAPCLR(&solv->dupinvolvedmap, SYSTEMSOLVABLE);
1195 }
1196
1197 void
1198 solver_freedupmaps(Solver *solv)
1199 {
1200   map_free(&solv->dupmap);
1201   map_free(&solv->dupinvolvedmap);
1202 }
1203
1204 void
1205 solver_addduprules(Solver *solv, Map *addedmap)
1206 {
1207   Pool *pool = solv->pool;
1208   Id p, pp;
1209   Solvable *s, *ps;
1210   int first, i;
1211
1212   solv->duprules = solv->nrules;
1213   for (i = 1; i < pool->nsolvables; i++)
1214     {
1215       if (i == SYSTEMSOLVABLE || !MAPTST(addedmap, i))
1216         continue;
1217       s = pool->solvables + i;
1218       first = i;
1219       FOR_PROVIDES(p, pp, s->name)
1220         {
1221           ps = pool->solvables + p;
1222           if (ps->name != s->name || !MAPTST(addedmap, p))
1223             continue;
1224           if (p == i)
1225             first = 0;
1226           if (first)
1227             break;
1228           if (!MAPTST(&solv->dupinvolvedmap, p))
1229             continue;
1230           if (solv->installed && ps->repo == solv->installed)
1231             {
1232               if (!solv->updatemap.size)
1233                 map_grow(&solv->updatemap, solv->installed->end - solv->installed->start);
1234               MAPSET(&solv->updatemap, p - solv->installed->start);
1235               if (!MAPTST(&solv->dupmap, p))
1236                 {
1237                   Id ip, ipp;
1238                   /* is installed identical to a good one? */
1239                   FOR_PROVIDES(ip, ipp, s->name)
1240                     {
1241                       Solvable *is = pool->solvables + ip;
1242                       if (!MAPTST(&solv->dupmap, ip))
1243                         continue;
1244                       if (is->evr == s->evr && solvable_identical(s, is))
1245                         break;
1246                     }
1247                   if (!ip)
1248                     solver_addrule(solv, -p, 0);        /* no match, sorry */
1249                 }
1250             }
1251           else if (!MAPTST(&solv->dupmap, p))
1252             solver_addrule(solv, -p, 0);
1253         }
1254     }
1255   solv->duprules_end = solv->nrules;
1256 }
1257
1258
1259 static inline void
1260 disableduprule(Solver *solv, Id name)
1261 {
1262   Pool *pool = solv->pool;
1263   Rule *r;
1264   int i;
1265   for (i = solv->duprules, r = solv->rules + i; i < solv->duprules_end; i++, r++)
1266     {
1267       if (r->p < 0 && r->d >= 0 && pool->solvables[-r->p].name == name)
1268         solver_disablerule(solv, r);
1269     }
1270 }
1271
1272 static inline void
1273 reenableduprule(Solver *solv, Id name)
1274 {
1275   Pool *pool = solv->pool;
1276   Rule *r;
1277   int i;
1278   for (i = solv->duprules, r = solv->rules + i; i < solv->duprules_end; i++, r++)
1279     {
1280       if (r->p < 0 && r->d < 0 && pool->solvables[-r->p].name == name)
1281         {
1282           solver_enablerule(solv, r);
1283           IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
1284             {
1285               POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
1286               solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
1287             }
1288         }
1289     }
1290 }
1291
1292
1293 /***********************************************************************
1294  ***
1295  ***  Policy rule disabling/reenabling
1296  ***
1297  ***  Disable all policy rules that conflict with our jobs. If a job
1298  ***  gets disabled later on, reenable the involved policy rules again.
1299  ***
1300  ***/
1301
1302 #define DISABLE_UPDATE  1
1303 #define DISABLE_INFARCH 2
1304 #define DISABLE_DUP     3
1305
1306 static void
1307 jobtodisablelist(Solver *solv, Id how, Id what, Queue *q)
1308 {
1309   Pool *pool = solv->pool;
1310   Id select, p, pp;
1311   Repo *installed;
1312   Solvable *s;
1313   int i;
1314
1315   installed = solv->installed;
1316   select = how & SOLVER_SELECTMASK;
1317   switch (how & SOLVER_JOBMASK)
1318     {
1319     case SOLVER_INSTALL:
1320       if ((select == SOLVER_SOLVABLE_NAME || select == SOLVER_SOLVABLE_PROVIDES) && solv->infarchrules != solv->infarchrules_end && ISRELDEP(what))
1321         {
1322           Reldep *rd = GETRELDEP(pool, what);
1323           if (rd->flags == REL_ARCH)
1324             {
1325               int qcnt = q->count;
1326               FOR_JOB_SELECT(p, pp, select, what)
1327                 {
1328                   s = pool->solvables + p;
1329                   /* unify names */
1330                   for (i = qcnt; i < q->count; i += 2)
1331                     if (q->elements[i + 1] == s->name)
1332                       break;
1333                   if (i < q->count)
1334                     continue;
1335                   queue_push(q, DISABLE_INFARCH);
1336                   queue_push(q, s->name);
1337                 }
1338             }
1339         }
1340       if (select != SOLVER_SOLVABLE)
1341         break;
1342       s = pool->solvables + what;
1343       if (solv->infarchrules != solv->infarchrules_end)
1344         {
1345           queue_push(q, DISABLE_INFARCH);
1346           queue_push(q, s->name);
1347         }
1348       if (solv->duprules != solv->duprules_end)
1349         {
1350           queue_push(q, DISABLE_DUP);
1351           queue_push(q, s->name);
1352         }
1353       if (!installed)
1354         return;
1355       if (solv->noobsoletes.size && MAPTST(&solv->noobsoletes, what))
1356         return;
1357       if (s->repo == installed)
1358         {
1359           queue_push(q, DISABLE_UPDATE);
1360           queue_push(q, what);
1361           return;
1362         }
1363       if (s->obsoletes)
1364         {
1365           Id obs, *obsp;
1366           obsp = s->repo->idarraydata + s->obsoletes;
1367           while ((obs = *obsp++) != 0)
1368             FOR_PROVIDES(p, pp, obs)
1369               {
1370                 Solvable *ps = pool->solvables + p;
1371                 if (ps->repo != installed)
1372                   continue;
1373                 if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
1374                   continue;
1375                 if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
1376                   continue;
1377                 queue_push(q, DISABLE_UPDATE);
1378                 queue_push(q, p);
1379               }
1380         }
1381       FOR_PROVIDES(p, pp, s->name)
1382         {
1383           Solvable *ps = pool->solvables + p;
1384           if (ps->repo != installed)
1385             continue;
1386           if (!pool->implicitobsoleteusesprovides && ps->name != s->name)
1387             continue;
1388           if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
1389             continue;
1390           queue_push(q, DISABLE_UPDATE);
1391           queue_push(q, p);
1392         }
1393       return;
1394     case SOLVER_ERASE:
1395       if (!installed)
1396         break;
1397       FOR_JOB_SELECT(p, pp, select, what)
1398         if (pool->solvables[p].repo == installed)
1399           {
1400             queue_push(q, DISABLE_UPDATE);
1401             queue_push(q, p);
1402           }
1403       return;
1404     default:
1405       return;
1406     }
1407 }
1408
1409 /* disable all policy rules that are in conflict with our job list */
1410 void
1411 solver_disablepolicyrules(Solver *solv)
1412 {
1413   Queue *job = &solv->job;
1414   int i, j;
1415   Queue allq;
1416   Rule *r;
1417   Id lastjob = -1;
1418   Id allqbuf[128];
1419
1420   queue_init_buffer(&allq, allqbuf, sizeof(allqbuf)/sizeof(*allqbuf));
1421
1422   for (i = solv->jobrules; i < solv->jobrules_end; i++)
1423     {
1424       r = solv->rules + i;
1425       if (r->d < 0)     /* disabled? */
1426         continue;
1427       j = solv->ruletojob.elements[i - solv->jobrules];
1428       if (j == lastjob)
1429         continue;
1430       lastjob = j;
1431       jobtodisablelist(solv, job->elements[j], job->elements[j + 1], &allq);
1432     }
1433   MAPZERO(&solv->noupdate);
1434   for (i = 0; i < allq.count; i += 2)
1435     {
1436       Id type = allq.elements[i], arg = allq.elements[i + 1];
1437       switch(type)
1438         {
1439         case DISABLE_UPDATE:
1440           disableupdaterule(solv, arg);
1441           break;
1442         case DISABLE_INFARCH:
1443           disableinfarchrule(solv, arg);
1444           break;
1445         case DISABLE_DUP:
1446           disableduprule(solv, arg);
1447           break;
1448         default:
1449           break;
1450         }
1451     }
1452   queue_free(&allq);
1453 }
1454
1455 /* we just disabled job #jobidx, now reenable all policy rules that were
1456  * disabled because of this job */
1457 void
1458 solver_reenablepolicyrules(Solver *solv, int jobidx)
1459 {
1460   Queue *job = &solv->job;
1461   int i, j;
1462   Queue q, allq;
1463   Rule *r;
1464   Id lastjob = -1;
1465   Id qbuf[32], allqbuf[128];
1466
1467   queue_init_buffer(&q, qbuf, sizeof(qbuf)/sizeof(*qbuf));
1468   queue_init_buffer(&allq, allqbuf, sizeof(allqbuf)/sizeof(*allqbuf));
1469   jobtodisablelist(solv, job->elements[jobidx], job->elements[jobidx + 1], &q);
1470   if (!q.count)
1471     return;
1472   for (i = solv->jobrules; i < solv->jobrules_end; i++)
1473     {
1474       r = solv->rules + i;
1475       if (r->d < 0)     /* disabled? */
1476         continue;
1477       j = solv->ruletojob.elements[i - solv->jobrules];
1478       if (j == lastjob)
1479         continue;
1480       lastjob = j;
1481       jobtodisablelist(solv, job->elements[j], job->elements[j + 1], &allq);
1482     }
1483   for (j = 0; j < q.count; j += 2)
1484     {
1485       Id type = q.elements[j], arg = q.elements[j + 1];
1486       for (i = 0; i < allq.count; i += 2)
1487         if (allq.elements[i] == type && allq.elements[i + 1] == arg)
1488           break;
1489       if (i < allq.count)
1490         continue;       /* still disabled */
1491       switch(type)
1492         {
1493         case DISABLE_UPDATE:
1494           reenableupdaterule(solv, arg);
1495           break;
1496         case DISABLE_INFARCH:
1497           reenableinfarchrule(solv, arg);
1498           break;
1499         case DISABLE_DUP:
1500           reenableduprule(solv, arg);
1501           break;
1502         }
1503     }
1504   queue_free(&allq);
1505   queue_free(&q);
1506 }
1507
1508
1509 /***********************************************************************
1510  ***
1511  ***  Rule info part, tell the user what the rule is about.
1512  ***
1513  ***/
1514
1515 static void
1516 addrpmruleinfo(Solver *solv, Id p, Id d, int type, Id dep)
1517 {
1518   Pool *pool = solv->pool;
1519   Rule *r;
1520   Id w2, op, od, ow2;
1521
1522   /* check if this creates the rule we're searching for */
1523   r = solv->rules + solv->ruleinfoq->elements[0];
1524   op = r->p;
1525   od = r->d < 0 ? -r->d - 1 : r->d;
1526   ow2 = 0;
1527
1528   /* normalize */
1529   w2 = d > 0 ? 0 : d;
1530   if (p < 0 && d > 0 && (!pool->whatprovidesdata[d] || !pool->whatprovidesdata[d + 1]))
1531     {
1532       w2 = pool->whatprovidesdata[d];
1533       d = 0;
1534
1535     }
1536   if (p > 0 && d < 0)           /* this hack is used for buddy deps */
1537     {
1538       w2 = p;
1539       p = d;
1540     }
1541
1542   if (d > 0)
1543     {
1544       if (p != op && !od)
1545         return;
1546       if (d != od)
1547         {
1548           Id *dp = pool->whatprovidesdata + d;
1549           Id *odp = pool->whatprovidesdata + od;
1550           while (*dp)
1551             if (*dp++ != *odp++)
1552               return;
1553           if (*odp)
1554             return;
1555         }
1556       w2 = 0;
1557       /* handle multiversion conflict rules */
1558       if (p < 0 && pool->whatprovidesdata[d] < 0)
1559         {
1560           w2 = pool->whatprovidesdata[d];
1561           /* XXX: free memory */
1562         }
1563     }
1564   else
1565     {
1566       if (od)
1567         return;
1568       ow2 = r->w2;
1569       if (p > w2)
1570         {
1571           if (w2 != op || p != ow2)
1572             return;
1573         }
1574       else
1575         {
1576           if (p != op || w2 != ow2)
1577             return;
1578         }
1579     }
1580   /* yep, rule matches. record info */
1581   queue_push(solv->ruleinfoq, type);
1582   if (type == SOLVER_RULE_RPM_SAME_NAME)
1583     {
1584       /* we normalize same name order */
1585       queue_push(solv->ruleinfoq, op < 0 ? -op : 0);
1586       queue_push(solv->ruleinfoq, ow2 < 0 ? -ow2 : 0);
1587     }
1588   else
1589     {
1590       queue_push(solv->ruleinfoq, p < 0 ? -p : 0);
1591       queue_push(solv->ruleinfoq, w2 < 0 ? -w2 : 0);
1592     }
1593   queue_push(solv->ruleinfoq, dep);
1594 }
1595
1596 static int
1597 solver_allruleinfos_cmp(const void *ap, const void *bp, void *dp)
1598 {
1599   const Id *a = ap, *b = bp;
1600   int r;
1601
1602   r = a[0] - b[0];
1603   if (r)
1604     return r;
1605   r = a[1] - b[1];
1606   if (r)
1607     return r;
1608   r = a[2] - b[2];
1609   if (r)
1610     return r;
1611   r = a[3] - b[3];
1612   if (r)
1613     return r;
1614   return 0;
1615 }
1616
1617 int
1618 solver_allruleinfos(Solver *solv, Id rid, Queue *rq)
1619 {
1620   Pool *pool = solv->pool;
1621   Rule *r = solv->rules + rid;
1622   int i, j;
1623
1624   queue_empty(rq);
1625   if (rid <= 0 || rid >= solv->rpmrules_end)
1626     {
1627       Id type, from, to, dep;
1628       type = solver_ruleinfo(solv, rid, &from, &to, &dep);
1629       queue_push(rq, type);
1630       queue_push(rq, from);
1631       queue_push(rq, to);
1632       queue_push(rq, dep);
1633       return 1;
1634     }
1635   if (r->p >= 0)
1636     return 0;
1637   queue_push(rq, rid);
1638   solv->ruleinfoq = rq;
1639   solver_addrpmrulesforsolvable(solv, pool->solvables - r->p, 0);
1640   /* also try reverse direction for conflicts */
1641   if ((r->d == 0 || r->d == -1) && r->w2 < 0)
1642     solver_addrpmrulesforsolvable(solv, pool->solvables - r->w2, 0);
1643   solv->ruleinfoq = 0;
1644   queue_shift(rq);
1645   /* now sort & unify em */
1646   if (!rq->count)
1647     return 0;
1648   sat_sort(rq->elements, rq->count / 4, 4 * sizeof(Id), solver_allruleinfos_cmp, 0);
1649   /* throw out identical entries */
1650   for (i = j = 0; i < rq->count; i += 4)
1651     {
1652       if (j)
1653         {
1654           if (rq->elements[i] == rq->elements[j - 4] &&
1655               rq->elements[i + 1] == rq->elements[j - 3] &&
1656               rq->elements[i + 2] == rq->elements[j - 2] &&
1657               rq->elements[i + 3] == rq->elements[j - 1])
1658             continue;
1659         }
1660       rq->elements[j++] = rq->elements[i];
1661       rq->elements[j++] = rq->elements[i + 1];
1662       rq->elements[j++] = rq->elements[i + 2];
1663       rq->elements[j++] = rq->elements[i + 3];
1664     }
1665   rq->count = j;
1666   return j / 4;
1667 }
1668
1669 SolverRuleinfo
1670 solver_ruleinfo(Solver *solv, Id rid, Id *fromp, Id *top, Id *depp)
1671 {
1672   Pool *pool = solv->pool;
1673   Rule *r = solv->rules + rid;
1674   SolverRuleinfo type = SOLVER_RULE_UNKNOWN;
1675
1676   if (fromp)
1677     *fromp = 0;
1678   if (top)
1679     *top = 0;
1680   if (depp)
1681     *depp = 0;
1682   if (rid > 0 && rid < solv->rpmrules_end)
1683     {
1684       Queue rq;
1685       int i;
1686
1687       if (r->p >= 0)
1688         return SOLVER_RULE_RPM;
1689       if (fromp)
1690         *fromp = -r->p;
1691       queue_init(&rq);
1692       queue_push(&rq, rid);
1693       solv->ruleinfoq = &rq;
1694       solver_addrpmrulesforsolvable(solv, pool->solvables - r->p, 0);
1695       /* also try reverse direction for conflicts */
1696       if ((r->d == 0 || r->d == -1) && r->w2 < 0)
1697         solver_addrpmrulesforsolvable(solv, pool->solvables - r->w2, 0);
1698       solv->ruleinfoq = 0;
1699       type = SOLVER_RULE_RPM;
1700       for (i = 1; i < rq.count; i += 4)
1701         {
1702           Id qt, qo, qp, qd;
1703           qt = rq.elements[i];
1704           qp = rq.elements[i + 1];
1705           qo = rq.elements[i + 2];
1706           qd = rq.elements[i + 3];
1707           if (type == SOLVER_RULE_RPM || type > qt)
1708             {
1709               type = qt;
1710               if (fromp)
1711                 *fromp = qp;
1712               if (top)
1713                 *top = qo;
1714               if (depp)
1715                 *depp = qd;
1716             }
1717         }
1718       queue_free(&rq);
1719       return type;
1720     }
1721   if (rid >= solv->jobrules && rid < solv->jobrules_end)
1722     {
1723       Id jidx = solv->ruletojob.elements[rid - solv->jobrules];
1724       if (fromp)
1725         *fromp = jidx;
1726       if (top)
1727         *top = solv->job.elements[jidx];
1728       if (depp)
1729         *depp = solv->job.elements[jidx + 1];
1730       if ((r->d == 0 || r->d == -1) && r->w2 == 0 && r->p == -SYSTEMSOLVABLE && (solv->job.elements[jidx] & SOLVER_SELECTMASK) != SOLVER_SOLVABLE_ONE_OF)
1731         return SOLVER_RULE_JOB_NOTHING_PROVIDES_DEP;
1732       return SOLVER_RULE_JOB;
1733     }
1734   if (rid >= solv->updaterules && rid < solv->updaterules_end)
1735     {
1736       if (fromp)
1737         *fromp = solv->installed->start + (rid - solv->updaterules);
1738       return SOLVER_RULE_UPDATE;
1739     }
1740   if (rid >= solv->featurerules && rid < solv->featurerules_end)
1741     {
1742       if (fromp)
1743         *fromp = solv->installed->start + (rid - solv->featurerules);
1744       return SOLVER_RULE_FEATURE;
1745     }
1746   if (rid >= solv->duprules && rid < solv->duprules_end)
1747     {
1748       if (fromp)
1749         *fromp = -r->p;
1750       if (depp)
1751         *depp = pool->solvables[-r->p].name;
1752       return SOLVER_RULE_DISTUPGRADE;
1753     }
1754   if (rid >= solv->infarchrules && rid < solv->infarchrules_end)
1755     {
1756       if (fromp)
1757         *fromp = -r->p;
1758       if (depp)
1759         *depp = pool->solvables[-r->p].name;
1760       return SOLVER_RULE_INFARCH;
1761     }
1762   if (rid >= solv->learntrules)
1763     {
1764       return SOLVER_RULE_LEARNT;
1765     }
1766   return SOLVER_RULE_UNKNOWN;
1767 }
1768
1769 /* EOF */