src/rules.c

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