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  *  gets 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           && (!solv->fixmap.size || !MAPTST(&solv->fixmap, n - installed->start)))
 505         {
 506           dontfix = 1;                  /* dont care about broken rpm deps */
 507         }
 508
 509       if (!dontfix
 510           && s->arch != ARCH_SRC
 511           && s->arch != ARCH_NOSRC
 512           && !pool_installable(pool, s))
 513         {
 514           POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "package %s [%d] is not installable\n", solvable2str(pool, s), (Id)(s - pool->solvables));
 515           addrpmrule(solv, -n, 0, SOLVER_RULE_RPM_NOT_INSTALLABLE, 0);
 516         }
 517
 518       /* yet another SUSE hack, sigh */
 519       if (pool->nscallback && !strncmp("product:", id2str(pool, s->name), 8))
 520         {
 521           Id buddy = pool->nscallback(pool, pool->nscallbackdata, NAMESPACE_PRODUCTBUDDY, n);
 522           if (buddy > 0 && buddy != SYSTEMSOLVABLE && buddy != n && buddy < pool->nsolvables)
 523             {
 524               addrpmrule(solv, n, -buddy, SOLVER_RULE_RPM_PACKAGE_REQUIRES, solvable_selfprovidedep(pool->solvables + n));
 525               addrpmrule(solv, buddy, -n, SOLVER_RULE_RPM_PACKAGE_REQUIRES, solvable_selfprovidedep(pool->solvables + buddy));
 526               if (m && !MAPTST(m, buddy))
 527                 queue_push(&workq, buddy);
 528             }
 529         }
 530
 531       /*-----------------------------------------
 532        * check requires of s
 533        */
 534
 535       if (s->requires)
 536         {
 537           reqp = s->repo->idarraydata + s->requires;
 538           while ((req = *reqp++) != 0)            /* go through all requires */
 539             {
 540               if (req == SOLVABLE_PREREQMARKER)   /* skip the marker */
 541                 continue;
 542
 543               /* find list of solvables providing 'req' */
 544               dp = pool_whatprovides_ptr(pool, req);
 545
 546               if (*dp == SYSTEMSOLVABLE)          /* always installed */
 547                 continue;
 548
 549               if (dontfix)
 550                 {
 551                   /* the strategy here is to not insist on dependencies
 552                    * that are already broken. so if we find one provider
 553                    * that was already installed, we know that the
 554                    * dependency was not broken before so we enforce it */
 555
 556                   /* check if any of the providers for 'req' is installed */
 557                   for (i = 0; (p = dp[i]) != 0; i++)
 558                     {
 559                       if (pool->solvables[p].repo == installed)
 560                         break;          /* provider was installed */
 561                     }
 562                   /* didn't find an installed provider: previously broken dependency */
 563                   if (!p)
 564                     {
 565                       POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "ignoring broken requires %s of installed package %s\n", dep2str(pool, req), solvable2str(pool, s));
 566                       continue;
 567                     }
 568                 }
 569
 570               if (!*dp)
 571                 {
 572                   /* nothing provides req! */
 573                   POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "package %s [%d] is not installable (%s)\n", solvable2str(pool, s), (Id)(s - pool->solvables), dep2str(pool, req));
 574                   addrpmrule(solv, -n, 0, SOLVER_RULE_RPM_NOTHING_PROVIDES_DEP, req);
 575                   continue;
 576                 }
 577
 578               IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION)
 579                 {
 580                   POOL_DEBUG(SAT_DEBUG_RULE_CREATION,"  %s requires %s\n", solvable2str(pool, s), dep2str(pool, req));
 581                   for (i = 0; dp[i]; i++)
 582                     POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "   provided by %s\n", solvid2str(pool, dp[i]));
 583                 }
 584
 585               /* add 'requires' dependency */
 586               /* rule: (-requestor|provider1|provider2|...|providerN) */
 587               addrpmrule(solv, -n, dp - pool->whatprovidesdata, SOLVER_RULE_RPM_PACKAGE_REQUIRES, req);
 588
 589               /* descend the dependency tree
 590                  push all non-visited providers on the work queue */
 591               if (m)
 592                 {
 593                   for (; *dp; dp++)
 594                     {
 595                       if (!MAPTST(m, *dp))
 596                         queue_push(&workq, *dp);
 597                     }
 598                 }
 599
 600             } /* while, requirements of n */
 601
 602         } /* if, requirements */
 603
 604       /* that's all we check for src packages */
 605       if (s->arch == ARCH_SRC || s->arch == ARCH_NOSRC)
 606         continue;
 607
 608       /*-----------------------------------------
 609        * check conflicts of s
 610        */
 611
 612       if (s->conflicts)
 613         {
 614           int ispatch = 0;
 615
 616           /* we treat conflicts in patches a bit differen:
 617            * - nevr matching
 618            * - multiversion handling
 619            * XXX: we should really handle this different, looking
 620            * at the name is a bad hack
 621            */
 622           if (!strncmp("patch:", id2str(pool, s->name), 6))
 623             ispatch = 1;
 624           conp = s->repo->idarraydata + s->conflicts;
 625           /* foreach conflicts of 's' */
 626           while ((con = *conp++) != 0)
 627             {
 628               /* foreach providers of a conflict of 's' */
 629               FOR_PROVIDES(p, pp, con)
 630                 {
 631                   if (ispatch && !pool_match_nevr(pool, pool->solvables + p, con))
 632                     continue;
 633                   /* dontfix: dont care about conflicts with already installed packs */
 634                   if (dontfix && pool->solvables[p].repo == installed)
 635                     continue;
 636                   /* p == n: self conflict */
 637                   if (p == n && !pool->allowselfconflicts)
 638                     {
 639                       if (ISRELDEP(con))
 640                         {
 641                           Reldep *rd = GETRELDEP(pool, con);
 642                           if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_OTHERPROVIDERS)
 643                             continue;
 644                         }
 645                       p = 0;    /* make it a negative assertion, aka 'uninstallable' */
 646                     }
 647                   if (p && ispatch && solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p) && ISRELDEP(con))
 648                     {
 649                       /* our patch conflicts with a noobsoletes (aka multiversion) package */
 650                       p = -makemultiversionconflict(solv, p, con);
 651                     }
 652                  /* rule: -n|-p: either solvable _or_ provider of conflict */
 653                   addrpmrule(solv, -n, -p, p ? SOLVER_RULE_RPM_PACKAGE_CONFLICT : SOLVER_RULE_RPM_SELF_CONFLICT, con);
 654                 }
 655             }
 656         }
 657
 658       /*-----------------------------------------
 659        * check obsoletes and implicit obsoletes of a package
 660        * if ignoreinstalledsobsoletes is not set, we're also checking
 661        * obsoletes of installed packages (like newer rpm versions)
 662        */
 663       if ((!installed || s->repo != installed) || !pool->noinstalledobsoletes)
 664         {
 665           int noobs = solv->noobsoletes.size && MAPTST(&solv->noobsoletes, n);
 666           int isinstalled = (installed && s->repo == installed);
 667           if (s->obsoletes && !noobs)
 668             {
 669               obsp = s->repo->idarraydata + s->obsoletes;
 670               /* foreach obsoletes */
 671               while ((obs = *obsp++) != 0)
 672                 {
 673                   /* foreach provider of an obsoletes of 's' */
 674                   FOR_PROVIDES(p, pp, obs)
 675                     {
 676                       Solvable *ps = pool->solvables + p;
 677                       if (p == n)
 678                         continue;
 679                       if (isinstalled && dontfix && ps->repo == installed)
 680                         continue;       /* don't repair installed/installed problems */
 681                       if (!pool->obsoleteusesprovides /* obsoletes are matched names, not provides */
 682                           && !pool_match_nevr(pool, ps, obs))
 683                         continue;
 684                       if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
 685                         continue;
 686                       if (!isinstalled)
 687                         addrpmrule(solv, -n, -p, SOLVER_RULE_RPM_PACKAGE_OBSOLETES, obs);
 688                       else
 689                         addrpmrule(solv, -n, -p, SOLVER_RULE_RPM_INSTALLEDPKG_OBSOLETES, obs);
 690                     }
 691                 }
 692             }
 693           /* check implicit obsoletes
 694            * for installed packages we only need to check installed/installed problems (and
 695            * only when dontfix is not set), as the others are picked up when looking at the
 696            * uninstalled package.
 697            */
 698           if (!isinstalled || !dontfix)
 699             {
 700               FOR_PROVIDES(p, pp, s->name)
 701                 {
 702                   Solvable *ps = pool->solvables + p;
 703                   if (p == n)
 704                     continue;
 705                   if (isinstalled && ps->repo != installed)
 706                     continue;
 707                   /* we still obsolete packages with same nevra, like rpm does */
 708                   /* (actually, rpm mixes those packages. yuck...) */
 709                   if (noobs && (s->name != ps->name || s->evr != ps->evr || s->arch != ps->arch))
 710                     continue;
 711                   if (!pool->implicitobsoleteusesprovides && s->name != ps->name)
 712                     continue;
 713                   if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
 714                     continue;
 715                   if (s->name == ps->name)
 716                     addrpmrule(solv, -n, -p, SOLVER_RULE_RPM_SAME_NAME, 0);
 717                   else
 718                     addrpmrule(solv, -n, -p, SOLVER_RULE_RPM_IMPLICIT_OBSOLETES, s->name);
 719                 }
 720             }
 721         }
 722
 723       /*-----------------------------------------
 724        * add recommends to the work queue
 725        */
 726       if (s->recommends && m)
 727         {
 728           recp = s->repo->idarraydata + s->recommends;
 729           while ((rec = *recp++) != 0)
 730             {
 731               FOR_PROVIDES(p, pp, rec)
 732                 if (!MAPTST(m, p))
 733                   queue_push(&workq, p);
 734             }
 735         }
 736       if (s->suggests && m)
 737         {
 738           sugp = s->repo->idarraydata + s->suggests;
 739           while ((sug = *sugp++) != 0)
 740             {
 741               FOR_PROVIDES(p, pp, sug)
 742                 if (!MAPTST(m, p))
 743                   queue_push(&workq, p);
 744             }
 745         }
 746     }
 747   queue_free(&workq);
 748   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforsolvable end -----\n");
 749 }
 750
 751
 752 /*-------------------------------------------------------------------
 753  *
 754  * Add package rules for weak rules
 755  *
 756  * m: visited solvables
 757  */
 758
 759 void
 760 solver_addrpmrulesforweak(Solver *solv, Map *m)
 761 {
 762   Pool *pool = solv->pool;
 763   Solvable *s;
 764   Id sup, *supp;
 765   int i, n;
 766
 767   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforweak -----\n");
 768     /* foreach solvable in pool */
 769   for (i = n = 1; n < pool->nsolvables; i++, n++)
 770     {
 771       if (i == pool->nsolvables)                /* wrap i */
 772         i = 1;
 773       if (MAPTST(m, i))                         /* been there */
 774         continue;
 775
 776       s = pool->solvables + i;
 777       if (!pool_installable(pool, s))           /* only look at installable ones */
 778         continue;
 779
 780       sup = 0;
 781       if (s->supplements)
 782         {
 783           /* find possible supplements */
 784           supp = s->repo->idarraydata + s->supplements;
 785           while ((sup = *supp++) != ID_NULL)
 786             if (dep_possible(solv, sup, m))
 787               break;
 788         }
 789
 790       /* if nothing found, check for enhances */
 791       if (!sup && s->enhances)
 792         {
 793           supp = s->repo->idarraydata + s->enhances;
 794           while ((sup = *supp++) != ID_NULL)
 795             if (dep_possible(solv, sup, m))
 796               break;
 797         }
 798       /* if nothing found, goto next solvables */
 799       if (!sup)
 800         continue;
 801       solver_addrpmrulesforsolvable(solv, s, m);
 802       n = 0;                    /* check all solvables again */
 803     }
 804   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforweak end -----\n");
 805 }
 806
 807
 808 /*-------------------------------------------------------------------
 809  *
 810  * add package rules for possible updates
 811  *
 812  * s: solvable
 813  * m: map of already visited solvables
 814  * allow_all: 0 = dont allow downgrades, 1 = allow all candidates
 815  */
 816
 817 void
 818 solver_addrpmrulesforupdaters(Solver *solv, Solvable *s, Map *m, int allow_all)
 819 {
 820   Pool *pool = solv->pool;
 821   int i;
 822     /* queue and buffer for it */
 823   Queue qs;
 824   Id qsbuf[64];
 825
 826   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforupdaters -----\n");
 827
 828   queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
 829     /* find update candidates for 's' */
 830   policy_findupdatepackages(solv, s, &qs, allow_all);
 831     /* add rule for 's' if not already done */
 832   if (!MAPTST(m, s - pool->solvables))
 833     solver_addrpmrulesforsolvable(solv, s, m);
 834     /* foreach update candidate, add rule if not already done */
 835   for (i = 0; i < qs.count; i++)
 836     if (!MAPTST(m, qs.elements[i]))
 837       solver_addrpmrulesforsolvable(solv, pool->solvables + qs.elements[i], m);
 838   queue_free(&qs);
 839
 840   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforupdaters -----\n");
 841 }
 842
 843
 844 /***********************************************************************
 845  ***
 846  ***  Update/Feature rule part
 847  ***
 848  ***  Those rules make sure an installed package isn't silently deleted
 849  ***
 850  ***/
 851
 852 static Id
 853 finddistupgradepackages(Solver *solv, Solvable *s, Queue *qs, int allow_all)
 854 {
 855   Pool *pool = solv->pool;
 856   int i;
 857
 858   policy_findupdatepackages(solv, s, qs, allow_all);
 859   if (!qs->count)
 860     {
 861       if (allow_all)
 862         return 0;       /* orphaned, don't create feature rule */
 863       /* check if this is an orphaned package */
 864       policy_findupdatepackages(solv, s, qs, 1);
 865       if (!qs->count)
 866         return 0;       /* orphaned, don't create update rule */
 867       qs->count = 0;
 868       return -SYSTEMSOLVABLE;   /* supported but not installable */
 869     }
 870   if (allow_all)
 871     return s - pool->solvables;
 872   /* check if it is ok to keep the installed package */
 873   for (i = 0; i < qs->count; i++)
 874     {
 875       Solvable *ns = pool->solvables + qs->elements[i];
 876       if (s->evr == ns->evr && solvable_identical(s, ns))
 877         return s - pool->solvables;
 878     }
 879   /* nope, it must be some other package */
 880   return -SYSTEMSOLVABLE;
 881 }
 882
 883 /* add packages from the dup repositories to the update candidates
 884  * this isn't needed for the global dup mode as all packages are
 885  * from dup repos in that case */
 886 static void
 887 addduppackages(Solver *solv, Solvable *s, Queue *qs)
 888 {
 889   Queue dupqs;
 890   Id p, dupqsbuf[64];
 891   int i;
 892   int oldnoupdateprovide = solv->noupdateprovide;
 893
 894   queue_init_buffer(&dupqs, dupqsbuf, sizeof(dupqsbuf)/sizeof(*dupqsbuf));
 895   solv->noupdateprovide = 1;
 896   policy_findupdatepackages(solv, s, &dupqs, 2);
 897   solv->noupdateprovide = oldnoupdateprovide;
 898   for (i = 0; i < dupqs.count; i++)
 899     {
 900       p = dupqs.elements[i];
 901       if (MAPTST(&solv->dupmap, p))
 902         queue_pushunique(qs, p);
 903     }
 904   queue_free(&dupqs);
 905 }
 906
 907 /*-------------------------------------------------------------------
 908  *
 909  * add rule for update
 910  *   (A|A1|A2|A3...)  An = update candidates for A
 911  *
 912  * s = (installed) solvable
 913  */
 914
 915 void
 916 solver_addupdaterule(Solver *solv, Solvable *s, int allow_all)
 917 {
 918   /* installed packages get a special upgrade allowed rule */
 919   Pool *pool = solv->pool;
 920   Id p, d;
 921   Queue qs;
 922   Id qsbuf[64];
 923
 924   POOL_DEBUG(SAT_DEBUG_SCHUBI, "-----  addupdaterule -----\n");
 925   queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
 926   p = s - pool->solvables;
 927   /* find update candidates for 's' */
 928   if (solv->distupgrade)
 929     p = finddistupgradepackages(solv, s, &qs, allow_all);
 930   else
 931     policy_findupdatepackages(solv, s, &qs, allow_all);
 932   if (!allow_all && !solv->distupgrade && solv->dupinvolvedmap.size && MAPTST(&solv->dupinvolvedmap, p))
 933     addduppackages(solv, s, &qs);
 934
 935   if (!allow_all && qs.count && solv->noobsoletes.size)
 936     {
 937       int i, j;
 938
 939       d = pool_queuetowhatprovides(pool, &qs);
 940       /* filter out all noobsoletes packages as they don't update */
 941       for (i = j = 0; i < qs.count; i++)
 942         {
 943           if (MAPTST(&solv->noobsoletes, qs.elements[i]))
 944             {
 945               /* it's ok if they have same nevra */
 946               Solvable *ps = pool->solvables + qs.elements[i];
 947               if (ps->name != s->name || ps->evr != s->evr || ps->arch != s->arch)
 948                 continue;
 949             }
 950           qs.elements[j++] = qs.elements[i];
 951         }
 952       if (j < qs.count)
 953         {
 954           if (d && solv->updatesystem && solv->installed && s->repo == solv->installed)
 955             {
 956               if (!solv->multiversionupdaters)
 957                 solv->multiversionupdaters = sat_calloc(solv->installed->end - solv->installed->start, sizeof(Id));
 958               solv->multiversionupdaters[s - pool->solvables - solv->installed->start] = d;
 959             }
 960           if (j == 0 && p == -SYSTEMSOLVABLE && solv->distupgrade)
 961             {
 962               queue_push(&solv->orphaned, s - pool->solvables); /* treat as orphaned */
 963               j = qs.count;
 964             }
 965           qs.count = j;
 966         }
 967     }
 968   if (qs.count && p == -SYSTEMSOLVABLE)
 969     p = queue_shift(&qs);
 970   d = qs.count ? pool_queuetowhatprovides(pool, &qs) : 0;
 971   queue_free(&qs);
 972   solver_addrule(solv, p, d);   /* allow update of s */
 973   POOL_DEBUG(SAT_DEBUG_SCHUBI, "-----  addupdaterule end -----\n");
 974 }
 975
 976 static inline void
 977 disableupdaterule(Solver *solv, Id p)
 978 {
 979   Rule *r;
 980
 981   MAPSET(&solv->noupdate, p - solv->installed->start);
 982   r = solv->rules + solv->updaterules + (p - solv->installed->start);
 983   if (r->p && r->d >= 0)
 984     solver_disablerule(solv, r);
 985   r = solv->rules + solv->featurerules + (p - solv->installed->start);
 986   if (r->p && r->d >= 0)
 987     solver_disablerule(solv, r);
 988 }
 989
 990 static inline void
 991 reenableupdaterule(Solver *solv, Id p)
 992 {
 993   Pool *pool = solv->pool;
 994   Rule *r;
 995
 996   MAPCLR(&solv->noupdate, p - solv->installed->start);
 997   r = solv->rules + solv->updaterules + (p - solv->installed->start);
 998   if (r->p)
 999     {
1000       if (r->d >= 0)
1001         return;
1002       solver_enablerule(solv, r);
1003       IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
1004         {
1005           POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
1006           solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
1007         }
1008       return;
1009     }
1010   r = solv->rules + solv->featurerules + (p - solv->installed->start);
1011   if (r->p && r->d < 0)
1012     {
1013       solver_enablerule(solv, r);
1014       IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
1015         {
1016           POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
1017           solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
1018         }
1019     }
1020 }
1021
1022
1023 /***********************************************************************
1024  ***
1025  ***  Infarch rule part
1026  ***
1027  ***  Infarch rules make sure the solver uses the best architecture of
1028  ***  a package if multiple archetectures are available
1029  ***
1030  ***/
1031
1032 void
1033 solver_addinfarchrules(Solver *solv, Map *addedmap)
1034 {
1035   Pool *pool = solv->pool;
1036   int first, i, j;
1037   Id p, pp, a, aa, bestarch;
1038   Solvable *s, *ps, *bests;
1039   Queue badq, allowedarchs;
1040
1041   queue_init(&badq);
1042   queue_init(&allowedarchs);
1043   solv->infarchrules = solv->nrules;
1044   for (i = 1; i < pool->nsolvables; i++)
1045     {
1046       if (i == SYSTEMSOLVABLE || !MAPTST(addedmap, i))
1047         continue;
1048       s = pool->solvables + i;
1049       first = i;
1050       bestarch = 0;
1051       bests = 0;
1052       queue_empty(&allowedarchs);
1053       FOR_PROVIDES(p, pp, s->name)
1054         {
1055           ps = pool->solvables + p;
1056           if (ps->name != s->name || !MAPTST(addedmap, p))
1057             continue;
1058           if (p == i)
1059             first = 0;
1060           if (first)
1061             break;
1062           a = ps->arch;
1063           a = (a <= pool->lastarch) ? pool->id2arch[a] : 0;
1064           if (a != 1 && pool->installed && ps->repo == pool->installed)
1065             {
1066               if (!solv->distupgrade)
1067                 queue_pushunique(&allowedarchs, ps->arch);      /* also ok to keep this architecture */
1068               continue;         /* ignore installed solvables when calculating the best arch */
1069             }
1070           if (a && a != 1 && (!bestarch || a < bestarch))
1071             {
1072               bestarch = a;
1073               bests = ps;
1074             }
1075         }
1076       if (first)
1077         continue;
1078       /* speed up common case where installed package already has best arch */
1079       if (allowedarchs.count == 1 && bests && allowedarchs.elements[0] == bests->arch)
1080         allowedarchs.count--;   /* installed arch is best */
1081       queue_empty(&badq);
1082       FOR_PROVIDES(p, pp, s->name)
1083         {
1084           ps = pool->solvables + p;
1085           if (ps->name != s->name || !MAPTST(addedmap, p))
1086             continue;
1087           a = ps->arch;
1088           a = (a <= pool->lastarch) ? pool->id2arch[a] : 0;
1089           if (a != 1 && bestarch && ((a ^ bestarch) & 0xffff0000) != 0)
1090             {
1091               if (pool->installed && ps->repo == pool->installed)
1092                 continue;       /* always ok to keep an installed package */
1093               for (j = 0; j < allowedarchs.count; j++)
1094                 {
1095                   aa = allowedarchs.elements[j];
1096                   if (ps->arch == aa)
1097                     break;
1098                   aa = (aa <= pool->lastarch) ? pool->id2arch[aa] : 0;
1099                   if (aa && ((a ^ aa) & 0xffff0000) == 0)
1100                     break;      /* compatible */
1101                 }
1102               if (j == allowedarchs.count)
1103                 queue_push(&badq, p);
1104             }
1105         }
1106       if (!badq.count)
1107         continue;
1108       /* block all solvables in the badq! */
1109       for (j = 0; j < badq.count; j++)
1110         {
1111           p = badq.elements[j];
1112           solver_addrule(solv, -p, 0);
1113         }
1114     }
1115   queue_free(&badq);
1116   queue_free(&allowedarchs);
1117   solv->infarchrules_end = solv->nrules;
1118 }
1119
1120 static inline void
1121 disableinfarchrule(Solver *solv, Id name)
1122 {
1123   Pool *pool = solv->pool;
1124   Rule *r;
1125   int i;
1126   for (i = solv->infarchrules, r = solv->rules + i; i < solv->infarchrules_end; i++, r++)
1127     {
1128       if (r->p < 0 && r->d >= 0 && pool->solvables[-r->p].name == name)
1129         solver_disablerule(solv, r);
1130     }
1131 }
1132
1133 static inline void
1134 reenableinfarchrule(Solver *solv, Id name)
1135 {
1136   Pool *pool = solv->pool;
1137   Rule *r;
1138   int i;
1139   for (i = solv->infarchrules, r = solv->rules + i; i < solv->infarchrules_end; i++, r++)
1140     {
1141       if (r->p < 0 && r->d < 0 && pool->solvables[-r->p].name == name)
1142         {
1143           solver_enablerule(solv, r);
1144           IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
1145             {
1146               POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
1147               solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
1148             }
1149         }
1150     }
1151 }
1152
1153
1154 /***********************************************************************
1155  ***
1156  ***  Dup rule part
1157  ***
1158  ***  Dup rules make sure a package is selected from the specified dup
1159  ***  repositories if an update candidate is included in one of them.
1160  ***
1161  ***/
1162
1163 void
1164 solver_createdupmaps(Solver *solv)
1165 {
1166   Queue *job = &solv->job;
1167   Pool *pool = solv->pool;
1168   Repo *repo;
1169   Id how, what, p, pi, pp, obs, *obsp;
1170   Solvable *s, *ps;
1171   int i;
1172
1173   map_init(&solv->dupmap, pool->nsolvables);
1174   map_init(&solv->dupinvolvedmap, pool->nsolvables);
1175   for (i = 0; i < job->count; i += 2)
1176     {
1177       how = job->elements[i];
1178       what = job->elements[i + 1];
1179       switch (how & SOLVER_JOBMASK)
1180         {
1181         case SOLVER_DISTUPGRADE:
1182           if ((how & SOLVER_SELECTMASK) != SOLVER_SOLVABLE_REPO)
1183             break;
1184           if (what <= 0 || what > pool->nrepos)
1185             break;
1186           repo = pool_id2repo(pool, what);
1187           FOR_REPO_SOLVABLES(repo, p, s)
1188             {
1189               MAPSET(&solv->dupmap, p);
1190               FOR_PROVIDES(pi, pp, s->name)
1191                 {
1192                   ps = pool->solvables + pi;
1193                   if (ps->name != s->name)
1194                     continue;
1195                   MAPSET(&solv->dupinvolvedmap, pi);
1196                 }
1197               if (s->obsoletes)
1198                 {
1199                   /* FIXME: check obsoletes/provides combination */
1200                   obsp = s->repo->idarraydata + s->obsoletes;
1201                   while ((obs = *obsp++) != 0)
1202                     {
1203                       FOR_PROVIDES(pi, pp, obs)
1204                         {
1205                           Solvable *pis = pool->solvables + pi;
1206                           if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, pis, obs))
1207                             continue;
1208                           if (pool->obsoleteusescolors && !pool_colormatch(pool, s, pis))
1209                             continue;
1210                           MAPSET(&solv->dupinvolvedmap, pi);
1211                         }
1212                     }
1213                 }
1214             }
1215           break;
1216         default:
1217           break;
1218         }
1219     }
1220   MAPCLR(&solv->dupinvolvedmap, SYSTEMSOLVABLE);
1221 }
1222
1223 void
1224 solver_freedupmaps(Solver *solv)
1225 {
1226   map_free(&solv->dupmap);
1227   map_free(&solv->dupinvolvedmap);
1228 }
1229
1230 void
1231 solver_addduprules(Solver *solv, Map *addedmap)
1232 {
1233   Pool *pool = solv->pool;
1234   Id p, pp;
1235   Solvable *s, *ps;
1236   int first, i;
1237
1238   solv->duprules = solv->nrules;
1239   for (i = 1; i < pool->nsolvables; i++)
1240     {
1241       if (i == SYSTEMSOLVABLE || !MAPTST(addedmap, i))
1242         continue;
1243       s = pool->solvables + i;
1244       first = i;
1245       FOR_PROVIDES(p, pp, s->name)
1246         {
1247           ps = pool->solvables + p;
1248           if (ps->name != s->name || !MAPTST(addedmap, p))
1249             continue;
1250           if (p == i)
1251             first = 0;
1252           if (first)
1253             break;
1254           if (!MAPTST(&solv->dupinvolvedmap, p))
1255             continue;
1256           if (solv->installed && ps->repo == solv->installed)
1257             {
1258               if (!solv->updatemap.size)
1259                 map_grow(&solv->updatemap, solv->installed->end - solv->installed->start);
1260               MAPSET(&solv->updatemap, p - solv->installed->start);
1261               if (!MAPTST(&solv->dupmap, p))
1262                 {
1263                   Id ip, ipp;
1264                   /* is installed identical to a good one? */
1265                   FOR_PROVIDES(ip, ipp, ps->name)
1266                     {
1267                       Solvable *is = pool->solvables + ip;
1268                       if (!MAPTST(&solv->dupmap, ip))
1269                         continue;
1270                       if (is->evr == ps->evr && solvable_identical(ps, is))
1271                         break;
1272                     }
1273                   if (!ip)
1274                     solver_addrule(solv, -p, 0);        /* no match, sorry */
1275                 }
1276             }
1277           else if (!MAPTST(&solv->dupmap, p))
1278             solver_addrule(solv, -p, 0);
1279         }
1280     }
1281   solv->duprules_end = solv->nrules;
1282 }
1283
1284
1285 static inline void
1286 disableduprule(Solver *solv, Id name)
1287 {
1288   Pool *pool = solv->pool;
1289   Rule *r;
1290   int i;
1291   for (i = solv->duprules, r = solv->rules + i; i < solv->duprules_end; i++, r++)
1292     {
1293       if (r->p < 0 && r->d >= 0 && pool->solvables[-r->p].name == name)
1294         solver_disablerule(solv, r);
1295     }
1296 }
1297
1298 static inline void
1299 reenableduprule(Solver *solv, Id name)
1300 {
1301   Pool *pool = solv->pool;
1302   Rule *r;
1303   int i;
1304   for (i = solv->duprules, r = solv->rules + i; i < solv->duprules_end; i++, r++)
1305     {
1306       if (r->p < 0 && r->d < 0 && pool->solvables[-r->p].name == name)
1307         {
1308           solver_enablerule(solv, r);
1309           IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
1310             {
1311               POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
1312               solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
1313             }
1314         }
1315     }
1316 }
1317
1318
1319 /***********************************************************************
1320  ***
1321  ***  Policy rule disabling/reenabling
1322  ***
1323  ***  Disable all policy rules that conflict with our jobs. If a job
1324  ***  gets disabled later on, reenable the involved policy rules again.
1325  ***
1326  ***/
1327
1328 #define DISABLE_UPDATE  1
1329 #define DISABLE_INFARCH 2
1330 #define DISABLE_DUP     3
1331
1332 static void
1333 jobtodisablelist(Solver *solv, Id how, Id what, Queue *q)
1334 {
1335   Pool *pool = solv->pool;
1336   Id select, p, pp;
1337   Repo *installed;
1338   Solvable *s;
1339   int i;
1340
1341   installed = solv->installed;
1342   select = how & SOLVER_SELECTMASK;
1343   switch (how & SOLVER_JOBMASK)
1344     {
1345     case SOLVER_INSTALL:
1346       if ((select == SOLVER_SOLVABLE_NAME || select == SOLVER_SOLVABLE_PROVIDES) && solv->infarchrules != solv->infarchrules_end && ISRELDEP(what))
1347         {
1348           Reldep *rd = GETRELDEP(pool, what);
1349           if (rd->flags == REL_ARCH)
1350             {
1351               int qcnt = q->count;
1352               FOR_JOB_SELECT(p, pp, select, what)
1353                 {
1354                   s = pool->solvables + p;
1355                   /* unify names */
1356                   for (i = qcnt; i < q->count; i += 2)
1357                     if (q->elements[i + 1] == s->name)
1358                       break;
1359                   if (i < q->count)
1360                     continue;
1361                   queue_push(q, DISABLE_INFARCH);
1362                   queue_push(q, s->name);
1363                 }
1364             }
1365         }
1366       if (select != SOLVER_SOLVABLE)
1367         break;
1368       s = pool->solvables + what;
1369       if (solv->infarchrules != solv->infarchrules_end)
1370         {
1371           queue_push(q, DISABLE_INFARCH);
1372           queue_push(q, s->name);
1373         }
1374       if (solv->duprules != solv->duprules_end)
1375         {
1376           queue_push(q, DISABLE_DUP);
1377           queue_push(q, s->name);
1378         }
1379       if (!installed)
1380         return;
1381       if (solv->noobsoletes.size && MAPTST(&solv->noobsoletes, what))
1382         {
1383           /* XXX: remove if we always do distupgrade with DUP rules */
1384           if (solv->distupgrade && s->repo == installed)
1385             {
1386               queue_push(q, DISABLE_UPDATE);
1387               queue_push(q, what);
1388               return;
1389             }
1390           return;
1391         }
1392       if (s->repo == installed)
1393         {
1394           queue_push(q, DISABLE_UPDATE);
1395           queue_push(q, what);
1396           return;
1397         }
1398       if (s->obsoletes)
1399         {
1400           Id obs, *obsp;
1401           obsp = s->repo->idarraydata + s->obsoletes;
1402           while ((obs = *obsp++) != 0)
1403             FOR_PROVIDES(p, pp, obs)
1404               {
1405                 Solvable *ps = pool->solvables + p;
1406                 if (ps->repo != installed)
1407                   continue;
1408                 if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
1409                   continue;
1410                 if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
1411                   continue;
1412                 queue_push(q, DISABLE_UPDATE);
1413                 queue_push(q, p);
1414               }
1415         }
1416       FOR_PROVIDES(p, pp, s->name)
1417         {
1418           Solvable *ps = pool->solvables + p;
1419           if (ps->repo != installed)
1420             continue;
1421           if (!pool->implicitobsoleteusesprovides && ps->name != s->name)
1422             continue;
1423           if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
1424             continue;
1425           queue_push(q, DISABLE_UPDATE);
1426           queue_push(q, p);
1427         }
1428       return;
1429     case SOLVER_ERASE:
1430       if (!installed)
1431         break;
1432       FOR_JOB_SELECT(p, pp, select, what)
1433         if (pool->solvables[p].repo == installed)
1434           {
1435             queue_push(q, DISABLE_UPDATE);
1436             queue_push(q, p);
1437           }
1438       return;
1439     default:
1440       return;
1441     }
1442 }
1443
1444 /* disable all policy rules that are in conflict with our job list */
1445 void
1446 solver_disablepolicyrules(Solver *solv)
1447 {
1448   Queue *job = &solv->job;
1449   int i, j;
1450   Queue allq;
1451   Rule *r;
1452   Id lastjob = -1;
1453   Id allqbuf[128];
1454
1455   queue_init_buffer(&allq, allqbuf, sizeof(allqbuf)/sizeof(*allqbuf));
1456
1457   for (i = solv->jobrules; i < solv->jobrules_end; i++)
1458     {
1459       r = solv->rules + i;
1460       if (r->d < 0)     /* disabled? */
1461         continue;
1462       j = solv->ruletojob.elements[i - solv->jobrules];
1463       if (j == lastjob)
1464         continue;
1465       lastjob = j;
1466       jobtodisablelist(solv, job->elements[j], job->elements[j + 1], &allq);
1467     }
1468   MAPZERO(&solv->noupdate);
1469   for (i = 0; i < allq.count; i += 2)
1470     {
1471       Id type = allq.elements[i], arg = allq.elements[i + 1];
1472       switch(type)
1473         {
1474         case DISABLE_UPDATE:
1475           disableupdaterule(solv, arg);
1476           break;
1477         case DISABLE_INFARCH:
1478           disableinfarchrule(solv, arg);
1479           break;
1480         case DISABLE_DUP:
1481           disableduprule(solv, arg);
1482           break;
1483         default:
1484           break;
1485         }
1486     }
1487   queue_free(&allq);
1488 }
1489
1490 /* we just disabled job #jobidx, now reenable all policy rules that were
1491  * disabled because of this job */
1492 void
1493 solver_reenablepolicyrules(Solver *solv, int jobidx)
1494 {
1495   Queue *job = &solv->job;
1496   int i, j;
1497   Queue q, allq;
1498   Rule *r;
1499   Id lastjob = -1;
1500   Id qbuf[32], allqbuf[128];
1501
1502   queue_init_buffer(&q, qbuf, sizeof(qbuf)/sizeof(*qbuf));
1503   queue_init_buffer(&allq, allqbuf, sizeof(allqbuf)/sizeof(*allqbuf));
1504   jobtodisablelist(solv, job->elements[jobidx], job->elements[jobidx + 1], &q);
1505   if (!q.count)
1506     return;
1507   for (i = solv->jobrules; i < solv->jobrules_end; i++)
1508     {
1509       r = solv->rules + i;
1510       if (r->d < 0)     /* disabled? */
1511         continue;
1512       j = solv->ruletojob.elements[i - solv->jobrules];
1513       if (j == lastjob)
1514         continue;
1515       lastjob = j;
1516       jobtodisablelist(solv, job->elements[j], job->elements[j + 1], &allq);
1517     }
1518   for (j = 0; j < q.count; j += 2)
1519     {
1520       Id type = q.elements[j], arg = q.elements[j + 1];
1521       for (i = 0; i < allq.count; i += 2)
1522         if (allq.elements[i] == type && allq.elements[i + 1] == arg)
1523           break;
1524       if (i < allq.count)
1525         continue;       /* still disabled */
1526       switch(type)
1527         {
1528         case DISABLE_UPDATE:
1529           reenableupdaterule(solv, arg);
1530           break;
1531         case DISABLE_INFARCH:
1532           reenableinfarchrule(solv, arg);
1533           break;
1534         case DISABLE_DUP:
1535           reenableduprule(solv, arg);
1536           break;
1537         }
1538     }
1539   queue_free(&allq);
1540   queue_free(&q);
1541 }
1542
1543
1544 /***********************************************************************
1545  ***
1546  ***  Rule info part, tell the user what the rule is about.
1547  ***
1548  ***/
1549
1550 static void
1551 addrpmruleinfo(Solver *solv, Id p, Id d, int type, Id dep)
1552 {
1553   Pool *pool = solv->pool;
1554   Rule *r;
1555   Id w2, op, od, ow2;
1556
1557   /* check if this creates the rule we're searching for */
1558   r = solv->rules + solv->ruleinfoq->elements[0];
1559   op = r->p;
1560   od = r->d < 0 ? -r->d - 1 : r->d;
1561   ow2 = 0;
1562
1563   /* normalize */
1564   w2 = d > 0 ? 0 : d;
1565   if (p < 0 && d > 0 && (!pool->whatprovidesdata[d] || !pool->whatprovidesdata[d + 1]))
1566     {
1567       w2 = pool->whatprovidesdata[d];
1568       d = 0;
1569
1570     }
1571   if (p > 0 && d < 0)           /* this hack is used for buddy deps */
1572     {
1573       w2 = p;
1574       p = d;
1575     }
1576
1577   if (d > 0)
1578     {
1579       if (p != op && !od)
1580         return;
1581       if (d != od)
1582         {
1583           Id *dp = pool->whatprovidesdata + d;
1584           Id *odp = pool->whatprovidesdata + od;
1585           while (*dp)
1586             if (*dp++ != *odp++)
1587               return;
1588           if (*odp)
1589             return;
1590         }
1591       w2 = 0;
1592       /* handle multiversion conflict rules */
1593       if (p < 0 && pool->whatprovidesdata[d] < 0)
1594         {
1595           w2 = pool->whatprovidesdata[d];
1596           /* XXX: free memory */
1597         }
1598     }
1599   else
1600     {
1601       if (od)
1602         return;
1603       ow2 = r->w2;
1604       if (p > w2)
1605         {
1606           if (w2 != op || p != ow2)
1607             return;
1608         }
1609       else
1610         {
1611           if (p != op || w2 != ow2)
1612             return;
1613         }
1614     }
1615   /* yep, rule matches. record info */
1616   queue_push(solv->ruleinfoq, type);
1617   if (type == SOLVER_RULE_RPM_SAME_NAME)
1618     {
1619       /* we normalize same name order */
1620       queue_push(solv->ruleinfoq, op < 0 ? -op : 0);
1621       queue_push(solv->ruleinfoq, ow2 < 0 ? -ow2 : 0);
1622     }
1623   else
1624     {
1625       queue_push(solv->ruleinfoq, p < 0 ? -p : 0);
1626       queue_push(solv->ruleinfoq, w2 < 0 ? -w2 : 0);
1627     }
1628   queue_push(solv->ruleinfoq, dep);
1629 }
1630
1631 static int
1632 solver_allruleinfos_cmp(const void *ap, const void *bp, void *dp)
1633 {
1634   const Id *a = ap, *b = bp;
1635   int r;
1636
1637   r = a[0] - b[0];
1638   if (r)
1639     return r;
1640   r = a[1] - b[1];
1641   if (r)
1642     return r;
1643   r = a[2] - b[2];
1644   if (r)
1645     return r;
1646   r = a[3] - b[3];
1647   if (r)
1648     return r;
1649   return 0;
1650 }
1651
1652 int
1653 solver_allruleinfos(Solver *solv, Id rid, Queue *rq)
1654 {
1655   Pool *pool = solv->pool;
1656   Rule *r = solv->rules + rid;
1657   int i, j;
1658
1659   queue_empty(rq);
1660   if (rid <= 0 || rid >= solv->rpmrules_end)
1661     {
1662       Id type, from, to, dep;
1663       type = solver_ruleinfo(solv, rid, &from, &to, &dep);
1664       queue_push(rq, type);
1665       queue_push(rq, from);
1666       queue_push(rq, to);
1667       queue_push(rq, dep);
1668       return 1;
1669     }
1670   if (r->p >= 0)
1671     return 0;
1672   queue_push(rq, rid);
1673   solv->ruleinfoq = rq;
1674   solver_addrpmrulesforsolvable(solv, pool->solvables - r->p, 0);
1675   /* also try reverse direction for conflicts */
1676   if ((r->d == 0 || r->d == -1) && r->w2 < 0)
1677     solver_addrpmrulesforsolvable(solv, pool->solvables - r->w2, 0);
1678   solv->ruleinfoq = 0;
1679   queue_shift(rq);
1680   /* now sort & unify em */
1681   if (!rq->count)
1682     return 0;
1683   sat_sort(rq->elements, rq->count / 4, 4 * sizeof(Id), solver_allruleinfos_cmp, 0);
1684   /* throw out identical entries */
1685   for (i = j = 0; i < rq->count; i += 4)
1686     {
1687       if (j)
1688         {
1689           if (rq->elements[i] == rq->elements[j - 4] &&
1690               rq->elements[i + 1] == rq->elements[j - 3] &&
1691               rq->elements[i + 2] == rq->elements[j - 2] &&
1692               rq->elements[i + 3] == rq->elements[j - 1])
1693             continue;
1694         }
1695       rq->elements[j++] = rq->elements[i];
1696       rq->elements[j++] = rq->elements[i + 1];
1697       rq->elements[j++] = rq->elements[i + 2];
1698       rq->elements[j++] = rq->elements[i + 3];
1699     }
1700   rq->count = j;
1701   return j / 4;
1702 }
1703
1704 SolverRuleinfo
1705 solver_ruleinfo(Solver *solv, Id rid, Id *fromp, Id *top, Id *depp)
1706 {
1707   Pool *pool = solv->pool;
1708   Rule *r = solv->rules + rid;
1709   SolverRuleinfo type = SOLVER_RULE_UNKNOWN;
1710
1711   if (fromp)
1712     *fromp = 0;
1713   if (top)
1714     *top = 0;
1715   if (depp)
1716     *depp = 0;
1717   if (rid > 0 && rid < solv->rpmrules_end)
1718     {
1719       Queue rq;
1720       int i;
1721
1722       if (r->p >= 0)
1723         return SOLVER_RULE_RPM;
1724       if (fromp)
1725         *fromp = -r->p;
1726       queue_init(&rq);
1727       queue_push(&rq, rid);
1728       solv->ruleinfoq = &rq;
1729       solver_addrpmrulesforsolvable(solv, pool->solvables - r->p, 0);
1730       /* also try reverse direction for conflicts */
1731       if ((r->d == 0 || r->d == -1) && r->w2 < 0)
1732         solver_addrpmrulesforsolvable(solv, pool->solvables - r->w2, 0);
1733       solv->ruleinfoq = 0;
1734       type = SOLVER_RULE_RPM;
1735       for (i = 1; i < rq.count; i += 4)
1736         {
1737           Id qt, qo, qp, qd;
1738           qt = rq.elements[i];
1739           qp = rq.elements[i + 1];
1740           qo = rq.elements[i + 2];
1741           qd = rq.elements[i + 3];
1742           if (type == SOLVER_RULE_RPM || type > qt)
1743             {
1744               type = qt;
1745               if (fromp)
1746                 *fromp = qp;
1747               if (top)
1748                 *top = qo;
1749               if (depp)
1750                 *depp = qd;
1751             }
1752         }
1753       queue_free(&rq);
1754       return type;
1755     }
1756   if (rid >= solv->jobrules && rid < solv->jobrules_end)
1757     {
1758       Id jidx = solv->ruletojob.elements[rid - solv->jobrules];
1759       if (fromp)
1760         *fromp = jidx;
1761       if (top)
1762         *top = solv->job.elements[jidx];
1763       if (depp)
1764         *depp = solv->job.elements[jidx + 1];
1765       if ((r->d == 0 || r->d == -1) && r->w2 == 0 && r->p == -SYSTEMSOLVABLE && (solv->job.elements[jidx] & SOLVER_SELECTMASK) != SOLVER_SOLVABLE_ONE_OF)
1766         return SOLVER_RULE_JOB_NOTHING_PROVIDES_DEP;
1767       return SOLVER_RULE_JOB;
1768     }
1769   if (rid >= solv->updaterules && rid < solv->updaterules_end)
1770     {
1771       if (fromp)
1772         *fromp = solv->installed->start + (rid - solv->updaterules);
1773       return SOLVER_RULE_UPDATE;
1774     }
1775   if (rid >= solv->featurerules && rid < solv->featurerules_end)
1776     {
1777       if (fromp)
1778         *fromp = solv->installed->start + (rid - solv->featurerules);
1779       return SOLVER_RULE_FEATURE;
1780     }
1781   if (rid >= solv->duprules && rid < solv->duprules_end)
1782     {
1783       if (fromp)
1784         *fromp = -r->p;
1785       if (depp)
1786         *depp = pool->solvables[-r->p].name;
1787       return SOLVER_RULE_DISTUPGRADE;
1788     }
1789   if (rid >= solv->infarchrules && rid < solv->infarchrules_end)
1790     {
1791       if (fromp)
1792         *fromp = -r->p;
1793       if (depp)
1794         *depp = pool->solvables[-r->p].name;
1795       return SOLVER_RULE_INFARCH;
1796     }
1797   if (rid >= solv->choicerules && rid < solv->choicerules_end)
1798     {
1799       return SOLVER_RULE_CHOICE;
1800     }
1801   if (rid >= solv->learntrules)
1802     {
1803       return SOLVER_RULE_LEARNT;
1804     }
1805   return SOLVER_RULE_UNKNOWN;
1806 }
1807
1808 void
1809 addchoicerules(Solver *solv)
1810 {
1811   Pool *pool = solv->pool;
1812   Map m, mneg;
1813   Rule *r;
1814   Queue q, qi;
1815   int i, j, rid, havechoice;
1816   Id p, d, *pp;
1817   Id p2, pp2;
1818   Solvable *s, *s2;
1819
1820   solv->choicerules = solv->nrules;
1821   if (!pool->installed)
1822     {
1823       solv->choicerules_end = solv->nrules;
1824       return;
1825     }
1826   solv->choicerules_ref = sat_calloc(solv->rpmrules_end, sizeof(Id));
1827   queue_init(&q);
1828   queue_init(&qi);
1829   map_init(&m, pool->nsolvables);
1830   map_init(&mneg, pool->nsolvables);
1831   /* set up negative assertion map from infarch and dup rules */
1832   for (rid = solv->infarchrules, r = solv->rules + rid; rid < solv->infarchrules_end; rid++, r++)
1833     if (r->p < 0 && !r->w2 && (r->d == 0 || r->d == -1))
1834       MAPSET(&mneg, -r->p);
1835   for (rid = solv->duprules, r = solv->rules + rid; rid < solv->duprules_end; rid++, r++)
1836     if (r->p < 0 && !r->w2 && (r->d == 0 || r->d == -1))
1837       MAPSET(&mneg, -r->p);
1838   for (rid = 1; rid < solv->rpmrules_end ; rid++)
1839     {
1840       r = solv->rules + rid;
1841       if (r->p >= 0 || ((r->d == 0 || r->d == -1) && r->w2 < 0))
1842         continue;       /* only look at requires rules */
1843       // solver_printrule(solv, SAT_DEBUG_RESULT, r);
1844       queue_empty(&q);
1845       queue_empty(&qi);
1846       havechoice = 0;
1847       FOR_RULELITERALS(p, pp, r)
1848         {
1849           if (p < 0)
1850             continue;
1851           s = pool->solvables + p;
1852           if (!s->repo)
1853             continue;
1854           if (s->repo == pool->installed)
1855             {
1856               queue_push(&q, p);
1857               continue;
1858             }
1859           /* check if this package is "blocked" by a installed package */
1860           s2 = 0;
1861           FOR_PROVIDES(p2, pp2, s->name)
1862             {
1863               s2 = pool->solvables + p2;
1864               if (s2->repo != pool->installed)
1865                 continue;
1866               if (!pool->implicitobsoleteusesprovides && s->name != s2->name)
1867                 continue;
1868               if (pool->obsoleteusescolors && !pool_colormatch(pool, s, s2))
1869                 continue;
1870               break;
1871             }
1872           if (p2)
1873             {
1874               /* found installed package p2 that we can update to p */
1875               if (!solv->allowarchchange && s->arch != s2->arch && policy_illegal_archchange(solv, s, s2))
1876                 continue;
1877               if (!solv->allowvendorchange && s->vendor != s2->vendor && policy_illegal_vendorchange(solv, s, s2))
1878                 continue;
1879               if (MAPTST(&mneg, p))
1880                 continue;
1881               queue_push(&qi, p2);
1882               queue_push(&q, p);
1883               continue;
1884             }
1885           if (s->obsoletes)
1886             {
1887               Id obs, *obsp = s->repo->idarraydata + s->obsoletes;
1888               s2 = 0;
1889               while ((obs = *obsp++) != 0)
1890                 {
1891                   FOR_PROVIDES(p2, pp2, obs)
1892                     {
1893                       s2 = pool->solvables + p2;
1894                       if (s2->repo != pool->installed)
1895                         continue;
1896                       if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p2, obs))
1897                         continue;
1898                       if (pool->obsoleteusescolors && !pool_colormatch(pool, s, s2))
1899                         continue;
1900                       break;
1901                     }
1902                   if (p2)
1903                     break;
1904                 }
1905               if (obs)
1906                 {
1907                   /* found installed package p2 that we can update to p */
1908                   if (!solv->allowarchchange && s->arch != s2->arch && policy_illegal_archchange(solv, s, s2))
1909                     continue;
1910                   if (!solv->allowvendorchange && s->vendor != s2->vendor && policy_illegal_vendorchange(solv, s, s2))
1911                     continue;
1912                   if (MAPTST(&mneg, p))
1913                     continue;
1914                   queue_push(&qi, p2);
1915                   queue_push(&q, p);
1916                   continue;
1917                 }
1918             }
1919           /* package p is independent of the installed ones */
1920           havechoice = 1;
1921         }
1922       if (!havechoice || !q.count)
1923         continue;       /* no choice */
1924
1925       /* now check the update rules of the installed package.
1926        * if all packages of the update rules are contained in
1927        * the dependency rules, there's no need to set up the choice rule */
1928       map_empty(&m);
1929       FOR_RULELITERALS(p, pp, r)
1930         if (p > 0)
1931           MAPSET(&m, p);
1932       for (i = 0; i < qi.count; i++)
1933         {
1934           if (!qi.elements[i])
1935             continue;
1936           Rule *ur = solv->rules + solv->updaterules + (qi.elements[i] - pool->installed->start);
1937           if (!ur->p)
1938             ur = solv->rules + solv->featurerules + (qi.elements[i] - pool->installed->start);
1939           if (!ur->p)
1940             continue;
1941           FOR_RULELITERALS(p, pp, ur)
1942             if (!MAPTST(&m, p))
1943               break;
1944           if (p)
1945             break;
1946           for (j = i + 1; j < qi.count; j++)
1947             if (qi.elements[i] == qi.elements[j])
1948               qi.elements[j] = 0;
1949         }
1950       if (i == qi.count)
1951         {
1952 #if 0
1953           printf("skipping choice ");
1954           solver_printrule(solv, SAT_DEBUG_RESULT, solv->rules + rid);
1955 #endif
1956           continue;
1957         }
1958       d = q.count ? pool_queuetowhatprovides(pool, &q) : 0;
1959       solver_addrule(solv, r->p, d);
1960       queue_push(&solv->weakruleq, solv->nrules - 1);
1961       solv->choicerules_ref[solv->nrules - 1 - solv->choicerules] = rid;
1962 #if 0
1963       printf("OLD ");
1964       solver_printrule(solv, SAT_DEBUG_RESULT, solv->rules + rid);
1965       printf("WEAK CHOICE ");
1966       solver_printrule(solv, SAT_DEBUG_RESULT, solv->rules + solv->nrules - 1);
1967 #endif
1968     }
1969   queue_free(&q);
1970   queue_free(&qi);
1971   map_free(&m);
1972   map_free(&mneg);
1973   solv->choicerules_end = solv->nrules;
1974 }
1975
1976 /* called when a choice rule is disabled by analyze_unsolvable. We also
1977  * have to disable all other choice rules so that the best packages get
1978  * picked */
1979
1980 void
1981 disablechoicerules(Solver *solv, Rule *r)
1982 {
1983   Id rid, p, *pp;
1984   Pool *pool = solv->pool;
1985   Map m;
1986   Rule *or;
1987
1988   or = solv->rules + solv->choicerules_ref[(r - solv->rules) - solv->choicerules];
1989   map_init(&m, pool->nsolvables);
1990   FOR_RULELITERALS(p, pp, or)
1991     if (p > 0)
1992       MAPSET(&m, p);
1993   FOR_RULELITERALS(p, pp, r)
1994     if (p > 0)
1995       MAPCLR(&m, p);
1996   for (rid = solv->choicerules; rid < solv->choicerules_end; rid++)
1997     {
1998       r = solv->rules + rid;
1999       if (r->d < 0)
2000         continue;
2001       or = solv->rules + solv->choicerules_ref[(r - solv->rules) - solv->choicerules];
2002       FOR_RULELITERALS(p, pp, or)
2003         if (p > 0 && MAPTST(&m, p))
2004           break;
2005       if (p)
2006         solver_disablerule(solv, r);
2007     }
2008 }
2009
2010 /* EOF */