src/rules.c

   1 /*
   2  * Copyright (c) 2007-2009, Novell Inc.
   3  *
   4  * This program is licensed under the BSD license, read LICENSE.BSD
   5  * for further information
   6  */
   7
   8 /*
   9  * rules.c
  10  *
  11  * SAT based dependency solver
  12  */
  13
  14 #include <stdio.h>
  15 #include <stdlib.h>
  16 #include <unistd.h>
  17 #include <string.h>
  18 #include <assert.h>
  19
  20 #include "solver.h"
  21 #include "bitmap.h"
  22 #include "pool.h"
  23 #include "poolarch.h"
  24 #include "util.h"
  25 #include "evr.h"
  26 #include "policy.h"
  27 #include "solverdebug.h"
  28
  29 #define RULES_BLOCK 63
  30
  31 static void addrpmruleinfo(Solver *solv, Id p, Id d, int type, Id dep);
  32 static void solver_createcleandepsmap(Solver *solv);
  33
  34 /*-------------------------------------------------------------------
  35  * Check if dependency is possible
  36  *
  37  * mirrors solver_dep_fulfilled but uses map m instead of the decisionmap
  38  * used in solver_addrpmrulesforweak and solver_createcleandepsmap
  39  */
  40
  41 static inline int
  42 dep_possible(Solver *solv, Id dep, Map *m)
  43 {
  44   Pool *pool = solv->pool;
  45   Id p, pp;
  46
  47   if (ISRELDEP(dep))
  48     {
  49       Reldep *rd = GETRELDEP(pool, dep);
  50       if (rd->flags >= 8)
  51         {
  52           if (rd->flags == REL_AND)
  53             {
  54               if (!dep_possible(solv, rd->name, m))
  55                 return 0;
  56               return dep_possible(solv, rd->evr, m);
  57             }
  58           if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
  59             return solver_splitprovides(solv, rd->evr);
  60           if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
  61             return solver_dep_installed(solv, rd->evr);
  62         }
  63     }
  64   FOR_PROVIDES(p, pp, dep)
  65     {
  66       if (MAPTST(m, p))
  67         return 1;
  68     }
  69   return 0;
  70 }
  71
  72 /********************************************************************
  73  *
  74  * Rule handling
  75  *
  76  * - unify rules, remove duplicates
  77  */
  78
  79 /*-------------------------------------------------------------------
  80  *
  81  * compare rules for unification sort
  82  *
  83  */
  84
  85 static int
  86 unifyrules_sortcmp(const void *ap, const void *bp, void *dp)
  87 {
  88   Pool *pool = dp;
  89   Rule *a = (Rule *)ap;
  90   Rule *b = (Rule *)bp;
  91   Id *ad, *bd;
  92   int x;
  93
  94   x = a->p - b->p;
  95   if (x)
  96     return x;                          /* p differs */
  97
  98   /* identical p */
  99   if (a->d == 0 && b->d == 0)
 100     return a->w2 - b->w2;              /* assertion: return w2 diff */
 101
 102   if (a->d == 0)                       /* a is assertion, b not */
 103     {
 104       x = a->w2 - pool->whatprovidesdata[b->d];
 105       return x ? x : -1;
 106     }
 107
 108   if (b->d == 0)                       /* b is assertion, a not */
 109     {
 110       x = pool->whatprovidesdata[a->d] - b->w2;
 111       return x ? x : 1;
 112     }
 113
 114   /* compare whatprovidesdata */
 115   ad = pool->whatprovidesdata + a->d;
 116   bd = pool->whatprovidesdata + b->d;
 117   while (*bd)
 118     if ((x = *ad++ - *bd++) != 0)
 119       return x;
 120   return *ad;
 121 }
 122
 123 int
 124 solver_samerule(Solver *solv, Rule *r1, Rule *r2)
 125 {
 126   return unifyrules_sortcmp(r1, r2, solv->pool);
 127 }
 128
 129
 130 /*-------------------------------------------------------------------
 131  *
 132  * unify rules
 133  * go over all rules and remove duplicates
 134  */
 135
 136 void
 137 solver_unifyrules(Solver *solv)
 138 {
 139   Pool *pool = solv->pool;
 140   int i, j;
 141   Rule *ir, *jr;
 142
 143   if (solv->nrules <= 2)               /* nothing to unify */
 144     return;
 145
 146   /* sort rules first */
 147   sat_sort(solv->rules + 1, solv->nrules - 1, sizeof(Rule), unifyrules_sortcmp, solv->pool);
 148
 149   /* prune rules
 150    * i = unpruned
 151    * j = pruned
 152    */
 153   jr = 0;
 154   for (i = j = 1, ir = solv->rules + i; i < solv->nrules; i++, ir++)
 155     {
 156       if (jr && !unifyrules_sortcmp(ir, jr, pool))
 157         continue;                      /* prune! */
 158       jr = solv->rules + j++;          /* keep! */
 159       if (ir != jr)
 160         *jr = *ir;
 161     }
 162
 163   /* reduced count from nrules to j rules */
 164   POOL_DEBUG(SAT_DEBUG_STATS, "pruned rules from %d to %d\n", solv->nrules, j);
 165
 166   /* adapt rule buffer */
 167   solv->nrules = j;
 168   solv->rules = sat_extend_resize(solv->rules, solv->nrules, sizeof(Rule), RULES_BLOCK);
 169
 170   /*
 171    * debug: log rule statistics
 172    */
 173   IF_POOLDEBUG (SAT_DEBUG_STATS)
 174     {
 175       int binr = 0;
 176       int lits = 0;
 177       Id *dp;
 178       Rule *r;
 179
 180       for (i = 1; i < solv->nrules; i++)
 181         {
 182           r = solv->rules + i;
 183           if (r->d == 0)
 184             binr++;
 185           else
 186             {
 187               dp = solv->pool->whatprovidesdata + r->d;
 188               while (*dp++)
 189                 lits++;
 190             }
 191         }
 192       POOL_DEBUG(SAT_DEBUG_STATS, "  binary: %d\n", binr);
 193       POOL_DEBUG(SAT_DEBUG_STATS, "  normal: %d, %d literals\n", solv->nrules - 1 - binr, lits);
 194     }
 195 }
 196
 197 #if 0
 198
 199 /*
 200  * hash rule
 201  */
 202
 203 static Hashval
 204 hashrule(Solver *solv, Id p, Id d, int n)
 205 {
 206   unsigned int x = (unsigned int)p;
 207   int *dp;
 208
 209   if (n <= 1)
 210     return (x * 37) ^ (unsigned int)d;
 211   dp = solv->pool->whatprovidesdata + d;
 212   while (*dp)
 213     x = (x * 37) ^ (unsigned int)*dp++;
 214   return x;
 215 }
 216 #endif
 217
 218
 219 /*-------------------------------------------------------------------
 220  *
 221  */
 222
 223 /*
 224  * add rule
 225  *  p = direct literal; always < 0 for installed rpm rules
 226  *  d, if < 0 direct literal, if > 0 offset into whatprovides, if == 0 rule is assertion (look at p only)
 227  *
 228  *
 229  * A requires b, b provided by B1,B2,B3 => (-A|B1|B2|B3)
 230  *
 231  * p < 0 : pkg id of A
 232  * d > 0 : Offset in whatprovidesdata (list of providers of b)
 233  *
 234  * A conflicts b, b provided by B1,B2,B3 => (-A|-B1), (-A|-B2), (-A|-B3)
 235  * p < 0 : pkg id of A
 236  * d < 0 : Id of solvable (e.g. B1)
 237  *
 238  * d == 0: unary rule, assertion => (A) or (-A)
 239  *
 240  *   Install:    p > 0, d = 0   (A)             user requested install
 241  *   Remove:     p < 0, d = 0   (-A)            user requested remove (also: uninstallable)
 242  *   Requires:   p < 0, d > 0   (-A|B1|B2|...)  d: <list of providers for requirement of p>
 243  *   Updates:    p > 0, d > 0   (A|B1|B2|...)   d: <list of updates for solvable p>
 244  *   Conflicts:  p < 0, d < 0   (-A|-B)         either p (conflict issuer) or d (conflict provider) (binary rule)
 245  *                                              also used for obsoletes
 246  *   ?:          p > 0, d < 0   (A|-B)
 247  *   No-op ?:    p = 0, d = 0   (null)          (used as policy rule placeholder)
 248  *
 249  *   resulting watches:
 250  *   ------------------
 251  *   Direct assertion (no watch needed) --> d = 0, w1 = p, w2 = 0
 252  *   Binary rule: p = first literal, d = 0, w2 = second literal, w1 = p
 253  *   every other : w1 = p, w2 = whatprovidesdata[d];
 254  *   Disabled rule: w1 = 0
 255  *
 256  *   always returns a rule for non-rpm rules
 257  */
 258
 259 Rule *
 260 solver_addrule(Solver *solv, Id p, Id d)
 261 {
 262   Pool *pool = solv->pool;
 263   Rule *r = 0;
 264   Id *dp = 0;
 265
 266   int n = 0;                           /* number of literals in rule - 1
 267                                           0 = direct assertion (single literal)
 268                                           1 = binary rule
 269                                           >1 =
 270                                         */
 271
 272   /* it often happenes that requires lead to adding the same rpm rule
 273    * multiple times, so we prune those duplicates right away to make
 274    * the work for unifyrules a bit easier */
 275
 276   if (!solv->rpmrules_end)              /* we add 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 || !r->w2))
 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)                       /* convert to binary rule */
 301         d = dp[-1];
 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   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           && s->repo == installed       /* solvable is installed */
 503           && !solv->fixmap_all          /* NOT repair errors in rpm dependency graph */
 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", pool_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:", pool_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", pool_dep2str(pool, req), pool_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", pool_solvable2str(pool, s), (Id)(s - pool->solvables), pool_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", pool_solvable2str(pool, s), pool_dep2str(pool, req));
 581                   for (i = 0; dp[i]; i++)
 582                     POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "   provided by %s\n", pool_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:", pool_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 }
 749
 750
 751 /*-------------------------------------------------------------------
 752  *
 753  * Add rules for packages possibly selected in by weak dependencies
 754  *
 755  * m: already added solvables
 756  */
 757
 758 void
 759 solver_addrpmrulesforweak(Solver *solv, Map *m)
 760 {
 761   Pool *pool = solv->pool;
 762   Solvable *s;
 763   Id sup, *supp;
 764   int i, n;
 765
 766   /* foreach solvable in pool */
 767   for (i = n = 1; n < pool->nsolvables; i++, n++)
 768     {
 769       if (i == pool->nsolvables)                /* wrap i */
 770         i = 1;
 771       if (MAPTST(m, i))                         /* already added that one */
 772         continue;
 773
 774       s = pool->solvables + i;
 775       if (!pool_installable(pool, s))           /* only look at installable ones */
 776         continue;
 777
 778       sup = 0;
 779       if (s->supplements)
 780         {
 781           /* find possible supplements */
 782           supp = s->repo->idarraydata + s->supplements;
 783           while ((sup = *supp++) != 0)
 784             if (dep_possible(solv, sup, m))
 785               break;
 786         }
 787
 788       /* if nothing found, check for enhances */
 789       if (!sup && s->enhances)
 790         {
 791           supp = s->repo->idarraydata + s->enhances;
 792           while ((sup = *supp++) != 0)
 793             if (dep_possible(solv, sup, m))
 794               break;
 795         }
 796       /* if nothing found, goto next solvables */
 797       if (!sup)
 798         continue;
 799       solver_addrpmrulesforsolvable(solv, s, m);
 800       n = 0;                    /* check all solvables again because we added solvables to m */
 801     }
 802 }
 803
 804
 805 /*-------------------------------------------------------------------
 806  *
 807  * add package rules for possible updates
 808  *
 809  * s: solvable
 810  * m: map of already visited solvables
 811  * allow_all: 0 = dont allow downgrades, 1 = allow all candidates
 812  */
 813
 814 void
 815 solver_addrpmrulesforupdaters(Solver *solv, Solvable *s, Map *m, int allow_all)
 816 {
 817   Pool *pool = solv->pool;
 818   int i;
 819     /* queue and buffer for it */
 820   Queue qs;
 821   Id qsbuf[64];
 822
 823   queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
 824     /* find update candidates for 's' */
 825   policy_findupdatepackages(solv, s, &qs, allow_all);
 826     /* add rule for 's' if not already done */
 827   if (!MAPTST(m, s - pool->solvables))
 828     solver_addrpmrulesforsolvable(solv, s, m);
 829     /* foreach update candidate, add rule if not already done */
 830   for (i = 0; i < qs.count; i++)
 831     if (!MAPTST(m, qs.elements[i]))
 832       solver_addrpmrulesforsolvable(solv, pool->solvables + qs.elements[i], m);
 833   queue_free(&qs);
 834 }
 835
 836
 837 /***********************************************************************
 838  ***
 839  ***  Update/Feature rule part
 840  ***
 841  ***  Those rules make sure an installed package isn't silently deleted
 842  ***
 843  ***/
 844
 845 static Id
 846 finddistupgradepackages(Solver *solv, Solvable *s, Queue *qs, int allow_all)
 847 {
 848   Pool *pool = solv->pool;
 849   int i;
 850
 851   policy_findupdatepackages(solv, s, qs, allow_all);
 852   if (!qs->count)
 853     {
 854       if (allow_all)
 855         return 0;       /* orphaned, don't create feature rule */
 856       /* check if this is an orphaned package */
 857       policy_findupdatepackages(solv, s, qs, 1);
 858       if (!qs->count)
 859         return 0;       /* orphaned, don't create update rule */
 860       qs->count = 0;
 861       return -SYSTEMSOLVABLE;   /* supported but not installable */
 862     }
 863   if (allow_all)
 864     return s - pool->solvables;
 865   /* check if it is ok to keep the installed package */
 866   for (i = 0; i < qs->count; i++)
 867     {
 868       Solvable *ns = pool->solvables + qs->elements[i];
 869       if (s->evr == ns->evr && solvable_identical(s, ns))
 870         return s - pool->solvables;
 871     }
 872   /* nope, it must be some other package */
 873   return -SYSTEMSOLVABLE;
 874 }
 875
 876 /* add packages from the dup repositories to the update candidates
 877  * this isn't needed for the global dup mode as all packages are
 878  * from dup repos in that case */
 879 static void
 880 addduppackages(Solver *solv, Solvable *s, Queue *qs)
 881 {
 882   Queue dupqs;
 883   Id p, dupqsbuf[64];
 884   int i;
 885   int oldnoupdateprovide = solv->noupdateprovide;
 886
 887   queue_init_buffer(&dupqs, dupqsbuf, sizeof(dupqsbuf)/sizeof(*dupqsbuf));
 888   solv->noupdateprovide = 1;
 889   policy_findupdatepackages(solv, s, &dupqs, 2);
 890   solv->noupdateprovide = oldnoupdateprovide;
 891   for (i = 0; i < dupqs.count; i++)
 892     {
 893       p = dupqs.elements[i];
 894       if (MAPTST(&solv->dupmap, p))
 895         queue_pushunique(qs, p);
 896     }
 897   queue_free(&dupqs);
 898 }
 899
 900 /*-------------------------------------------------------------------
 901  *
 902  * add rule for update
 903  *   (A|A1|A2|A3...)  An = update candidates for A
 904  *
 905  * s = (installed) solvable
 906  */
 907
 908 void
 909 solver_addupdaterule(Solver *solv, Solvable *s, int allow_all)
 910 {
 911   /* installed packages get a special upgrade allowed rule */
 912   Pool *pool = solv->pool;
 913   Id p, d;
 914   Queue qs;
 915   Id qsbuf[64];
 916
 917   queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
 918   p = s - pool->solvables;
 919   /* find update candidates for 's' */
 920   if (solv->dupmap_all)
 921     p = finddistupgradepackages(solv, s, &qs, allow_all);
 922   else
 923     policy_findupdatepackages(solv, s, &qs, allow_all);
 924   if (!allow_all && !solv->dupmap_all && solv->dupinvolvedmap.size && MAPTST(&solv->dupinvolvedmap, p))
 925     addduppackages(solv, s, &qs);
 926
 927   if (!allow_all && qs.count && solv->noobsoletes.size)
 928     {
 929       int i, j;
 930
 931       d = pool_queuetowhatprovides(pool, &qs);
 932       /* filter out all noobsoletes packages as they don't update */
 933       for (i = j = 0; i < qs.count; i++)
 934         {
 935           if (MAPTST(&solv->noobsoletes, qs.elements[i]))
 936             {
 937               /* it's ok if they have same nevra */
 938               Solvable *ps = pool->solvables + qs.elements[i];
 939               if (ps->name != s->name || ps->evr != s->evr || ps->arch != s->arch)
 940                 continue;
 941             }
 942           qs.elements[j++] = qs.elements[i];
 943         }
 944       if (j < qs.count)
 945         {
 946           if (d && solv->installed && s->repo == solv->installed &&
 947               (solv->updatemap_all || (solv->updatemap.size && MAPTST(&solv->updatemap, s - pool->solvables - solv->installed->start))))
 948             {
 949               if (!solv->multiversionupdaters)
 950                 solv->multiversionupdaters = sat_calloc(solv->installed->end - solv->installed->start, sizeof(Id));
 951               solv->multiversionupdaters[s - pool->solvables - solv->installed->start] = d;
 952             }
 953           if (j == 0 && p == -SYSTEMSOLVABLE && solv->dupmap_all)
 954             {
 955               queue_push(&solv->orphaned, s - pool->solvables); /* treat as orphaned */
 956               j = qs.count;
 957             }
 958           qs.count = j;
 959         }
 960     }
 961   if (qs.count && p == -SYSTEMSOLVABLE)
 962     p = queue_shift(&qs);
 963   d = qs.count ? pool_queuetowhatprovides(pool, &qs) : 0;
 964   queue_free(&qs);
 965   solver_addrule(solv, p, d);   /* allow update of s */
 966 }
 967
 968 static inline void
 969 disableupdaterule(Solver *solv, Id p)
 970 {
 971   Rule *r;
 972
 973   MAPSET(&solv->noupdate, p - solv->installed->start);
 974   r = solv->rules + solv->updaterules + (p - solv->installed->start);
 975   if (r->p && r->d >= 0)
 976     solver_disablerule(solv, r);
 977   r = solv->rules + solv->featurerules + (p - solv->installed->start);
 978   if (r->p && r->d >= 0)
 979     solver_disablerule(solv, r);
 980 }
 981
 982 static inline void
 983 reenableupdaterule(Solver *solv, Id p)
 984 {
 985   Pool *pool = solv->pool;
 986   Rule *r;
 987
 988   MAPCLR(&solv->noupdate, p - solv->installed->start);
 989   r = solv->rules + solv->updaterules + (p - solv->installed->start);
 990   if (r->p)
 991     {
 992       if (r->d >= 0)
 993         return;
 994       solver_enablerule(solv, r);
 995       IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
 996         {
 997           POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
 998           solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
 999         }
1000       return;
1001     }
1002   r = solv->rules + solv->featurerules + (p - solv->installed->start);
1003   if (r->p && r->d < 0)
1004     {
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     }
1012 }
1013
1014
1015 /***********************************************************************
1016  ***
1017  ***  Infarch rule part
1018  ***
1019  ***  Infarch rules make sure the solver uses the best architecture of
1020  ***  a package if multiple archetectures are available
1021  ***
1022  ***/
1023
1024 void
1025 solver_addinfarchrules(Solver *solv, Map *addedmap)
1026 {
1027   Pool *pool = solv->pool;
1028   int first, i, j;
1029   Id p, pp, a, aa, bestarch;
1030   Solvable *s, *ps, *bests;
1031   Queue badq, allowedarchs;
1032
1033   queue_init(&badq);
1034   queue_init(&allowedarchs);
1035   solv->infarchrules = solv->nrules;
1036   for (i = 1; i < pool->nsolvables; i++)
1037     {
1038       if (i == SYSTEMSOLVABLE || !MAPTST(addedmap, i))
1039         continue;
1040       s = pool->solvables + i;
1041       first = i;
1042       bestarch = 0;
1043       bests = 0;
1044       queue_empty(&allowedarchs);
1045       FOR_PROVIDES(p, pp, s->name)
1046         {
1047           ps = pool->solvables + p;
1048           if (ps->name != s->name || !MAPTST(addedmap, p))
1049             continue;
1050           if (p == i)
1051             first = 0;
1052           if (first)
1053             break;
1054           a = ps->arch;
1055           a = (a <= pool->lastarch) ? pool->id2arch[a] : 0;
1056           if (a != 1 && pool->installed && ps->repo == pool->installed)
1057             {
1058               if (!solv->dupmap_all && !(solv->dupinvolvedmap.size && MAPTST(&solv->dupinvolvedmap, p)))
1059                 queue_pushunique(&allowedarchs, ps->arch);      /* also ok to keep this architecture */
1060               continue;         /* ignore installed solvables when calculating the best arch */
1061             }
1062           if (a && a != 1 && (!bestarch || a < bestarch))
1063             {
1064               bestarch = a;
1065               bests = ps;
1066             }
1067         }
1068       if (first)
1069         continue;
1070       /* speed up common case where installed package already has best arch */
1071       if (allowedarchs.count == 1 && bests && allowedarchs.elements[0] == bests->arch)
1072         allowedarchs.count--;   /* installed arch is best */
1073       queue_empty(&badq);
1074       FOR_PROVIDES(p, pp, s->name)
1075         {
1076           ps = pool->solvables + p;
1077           if (ps->name != s->name || !MAPTST(addedmap, p))
1078             continue;
1079           a = ps->arch;
1080           a = (a <= pool->lastarch) ? pool->id2arch[a] : 0;
1081           if (a != 1 && bestarch && ((a ^ bestarch) & 0xffff0000) != 0)
1082             {
1083               if (pool->installed && ps->repo == pool->installed)
1084                 continue;       /* always ok to keep an installed package */
1085               for (j = 0; j < allowedarchs.count; j++)
1086                 {
1087                   aa = allowedarchs.elements[j];
1088                   if (ps->arch == aa)
1089                     break;
1090                   aa = (aa <= pool->lastarch) ? pool->id2arch[aa] : 0;
1091                   if (aa && ((a ^ aa) & 0xffff0000) == 0)
1092                     break;      /* compatible */
1093                 }
1094               if (j == allowedarchs.count)
1095                 queue_push(&badq, p);
1096             }
1097         }
1098       if (!badq.count)
1099         continue;
1100       /* block all solvables in the badq! */
1101       for (j = 0; j < badq.count; j++)
1102         {
1103           p = badq.elements[j];
1104           solver_addrule(solv, -p, 0);
1105         }
1106     }
1107   queue_free(&badq);
1108   queue_free(&allowedarchs);
1109   solv->infarchrules_end = solv->nrules;
1110 }
1111
1112 static inline void
1113 disableinfarchrule(Solver *solv, Id name)
1114 {
1115   Pool *pool = solv->pool;
1116   Rule *r;
1117   int i;
1118   for (i = solv->infarchrules, r = solv->rules + i; i < solv->infarchrules_end; i++, r++)
1119     {
1120       if (r->p < 0 && r->d >= 0 && pool->solvables[-r->p].name == name)
1121         solver_disablerule(solv, r);
1122     }
1123 }
1124
1125 static inline void
1126 reenableinfarchrule(Solver *solv, Id name)
1127 {
1128   Pool *pool = solv->pool;
1129   Rule *r;
1130   int i;
1131   for (i = solv->infarchrules, r = solv->rules + i; i < solv->infarchrules_end; i++, r++)
1132     {
1133       if (r->p < 0 && r->d < 0 && pool->solvables[-r->p].name == name)
1134         {
1135           solver_enablerule(solv, r);
1136           IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
1137             {
1138               POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
1139               solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
1140             }
1141         }
1142     }
1143 }
1144
1145
1146 /***********************************************************************
1147  ***
1148  ***  Dup rule part
1149  ***
1150  ***  Dup rules make sure a package is selected from the specified dup
1151  ***  repositories if an update candidate is included in one of them.
1152  ***
1153  ***/
1154
1155 void
1156 solver_createdupmaps(Solver *solv)
1157 {
1158   Queue *job = &solv->job;
1159   Pool *pool = solv->pool;
1160   Repo *repo;
1161   Id how, what, p, pi, pp, obs, *obsp;
1162   Solvable *s, *ps;
1163   int i;
1164
1165   map_init(&solv->dupmap, pool->nsolvables);
1166   map_init(&solv->dupinvolvedmap, pool->nsolvables);
1167   for (i = 0; i < job->count; i += 2)
1168     {
1169       how = job->elements[i];
1170       what = job->elements[i + 1];
1171       switch (how & SOLVER_JOBMASK)
1172         {
1173         case SOLVER_DISTUPGRADE:
1174           if ((how & SOLVER_SELECTMASK) != SOLVER_SOLVABLE_REPO)
1175             break;
1176           if (what <= 0 || what > pool->nrepos)
1177             break;
1178           repo = pool_id2repo(pool, what);
1179           FOR_REPO_SOLVABLES(repo, p, s)
1180             {
1181               MAPSET(&solv->dupmap, p);
1182               FOR_PROVIDES(pi, pp, s->name)
1183                 {
1184                   ps = pool->solvables + pi;
1185                   if (ps->name != s->name)
1186                     continue;
1187                   MAPSET(&solv->dupinvolvedmap, pi);
1188                 }
1189               if (s->obsoletes)
1190                 {
1191                   /* FIXME: check obsoletes/provides combination */
1192                   obsp = s->repo->idarraydata + s->obsoletes;
1193                   while ((obs = *obsp++) != 0)
1194                     {
1195                       FOR_PROVIDES(pi, pp, obs)
1196                         {
1197                           Solvable *pis = pool->solvables + pi;
1198                           if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, pis, obs))
1199                             continue;
1200                           if (pool->obsoleteusescolors && !pool_colormatch(pool, s, pis))
1201                             continue;
1202                           MAPSET(&solv->dupinvolvedmap, pi);
1203                         }
1204                     }
1205                 }
1206             }
1207           break;
1208         default:
1209           break;
1210         }
1211     }
1212   MAPCLR(&solv->dupinvolvedmap, SYSTEMSOLVABLE);
1213 }
1214
1215 void
1216 solver_freedupmaps(Solver *solv)
1217 {
1218   map_free(&solv->dupmap);
1219   /* we no longer free solv->dupinvolvedmap as we need it in
1220    * policy's priority pruning code. sigh. */
1221 }
1222
1223 void
1224 solver_addduprules(Solver *solv, Map *addedmap)
1225 {
1226   Pool *pool = solv->pool;
1227   Id p, pp;
1228   Solvable *s, *ps;
1229   int first, i;
1230
1231   solv->duprules = solv->nrules;
1232   for (i = 1; i < pool->nsolvables; i++)
1233     {
1234       if (i == SYSTEMSOLVABLE || !MAPTST(addedmap, i))
1235         continue;
1236       s = pool->solvables + i;
1237       first = i;
1238       FOR_PROVIDES(p, pp, s->name)
1239         {
1240           ps = pool->solvables + p;
1241           if (ps->name != s->name || !MAPTST(addedmap, p))
1242             continue;
1243           if (p == i)
1244             first = 0;
1245           if (first)
1246             break;
1247           if (!MAPTST(&solv->dupinvolvedmap, p))
1248             continue;
1249           if (solv->installed && ps->repo == solv->installed)
1250             {
1251               if (!solv->updatemap.size)
1252                 map_grow(&solv->updatemap, solv->installed->end - solv->installed->start);
1253               MAPSET(&solv->updatemap, p - solv->installed->start);
1254               if (!MAPTST(&solv->dupmap, p))
1255                 {
1256                   Id ip, ipp;
1257                   /* is installed identical to a good one? */
1258                   FOR_PROVIDES(ip, ipp, ps->name)
1259                     {
1260                       Solvable *is = pool->solvables + ip;
1261                       if (!MAPTST(&solv->dupmap, ip))
1262                         continue;
1263                       if (is->evr == ps->evr && solvable_identical(ps, is))
1264                         break;
1265                     }
1266                   if (!ip)
1267                     solver_addrule(solv, -p, 0);        /* no match, sorry */
1268                 }
1269             }
1270           else if (!MAPTST(&solv->dupmap, p))
1271             solver_addrule(solv, -p, 0);
1272         }
1273     }
1274   solv->duprules_end = solv->nrules;
1275 }
1276
1277
1278 static inline void
1279 disableduprule(Solver *solv, Id name)
1280 {
1281   Pool *pool = solv->pool;
1282   Rule *r;
1283   int i;
1284   for (i = solv->duprules, r = solv->rules + i; i < solv->duprules_end; i++, r++)
1285     {
1286       if (r->p < 0 && r->d >= 0 && pool->solvables[-r->p].name == name)
1287         solver_disablerule(solv, r);
1288     }
1289 }
1290
1291 static inline void
1292 reenableduprule(Solver *solv, Id name)
1293 {
1294   Pool *pool = solv->pool;
1295   Rule *r;
1296   int i;
1297   for (i = solv->duprules, r = solv->rules + i; i < solv->duprules_end; i++, r++)
1298     {
1299       if (r->p < 0 && r->d < 0 && pool->solvables[-r->p].name == name)
1300         {
1301           solver_enablerule(solv, r);
1302           IF_POOLDEBUG (SAT_DEBUG_SOLUTIONS)
1303             {
1304               POOL_DEBUG(SAT_DEBUG_SOLUTIONS, "@@@ re-enabling ");
1305               solver_printruleclass(solv, SAT_DEBUG_SOLUTIONS, r);
1306             }
1307         }
1308     }
1309 }
1310
1311
1312 /***********************************************************************
1313  ***
1314  ***  Policy rule disabling/reenabling
1315  ***
1316  ***  Disable all policy rules that conflict with our jobs. If a job
1317  ***  gets disabled later on, reenable the involved policy rules again.
1318  ***
1319  ***/
1320
1321 #define DISABLE_UPDATE  1
1322 #define DISABLE_INFARCH 2
1323 #define DISABLE_DUP     3
1324
1325 static void
1326 jobtodisablelist(Solver *solv, Id how, Id what, Queue *q)
1327 {
1328   Pool *pool = solv->pool;
1329   Id select, p, pp;
1330   Repo *installed;
1331   Solvable *s;
1332   int i, j, set, qstart, pass;
1333   Map omap;
1334
1335   installed = solv->installed;
1336   select = how & SOLVER_SELECTMASK;
1337   switch (how & SOLVER_JOBMASK)
1338     {
1339     case SOLVER_INSTALL:
1340       set = how & SOLVER_SETMASK;
1341       if (!(set & SOLVER_NOAUTOSET))
1342         {
1343           /* automatically add set bits by analysing the job */
1344           if (select == SOLVER_SOLVABLE)
1345             set |= SOLVER_SETARCH | SOLVER_SETVENDOR | SOLVER_SETREPO | SOLVER_SETEVR;
1346           else if ((select == SOLVER_SOLVABLE_NAME || select == SOLVER_SOLVABLE_PROVIDES) && ISRELDEP(what))
1347             {
1348               Reldep *rd = GETRELDEP(pool, what);
1349               if (rd->flags == REL_EQ && select == SOLVER_SOLVABLE_NAME)
1350                 {
1351 #if !defined(DEBIAN_SEMANTICS)
1352                   const char *evr = pool_id2str(pool, rd->evr);
1353                   if (strchr(evr, '-'))
1354                     set |= SOLVER_SETEVR;
1355                   else
1356                     set |= SOLVER_SETEV;
1357 #else
1358                   set |= SOLVER_SETEVR;
1359 #endif
1360                 }
1361               if (rd->flags <= 7 && ISRELDEP(rd->name))
1362                 rd = GETRELDEP(pool, rd->name);
1363               if (rd->flags == REL_ARCH)
1364                 set |= SOLVER_SETARCH;
1365             }
1366         }
1367       else
1368         set &= ~SOLVER_NOAUTOSET;
1369       if (!set)
1370         return;
1371       if ((set & SOLVER_SETARCH) != 0 && solv->infarchrules != solv->infarchrules_end)
1372         {
1373           if (select == SOLVER_SOLVABLE)
1374             queue_push2(q, DISABLE_INFARCH, pool->solvables[what].name);
1375           else
1376             {
1377               int qcnt = q->count;
1378               FOR_JOB_SELECT(p, pp, select, what)
1379                 {
1380                   s = pool->solvables + p;
1381                   /* unify names */
1382                   for (i = qcnt; i < q->count; i += 2)
1383                     if (q->elements[i + 1] == s->name)
1384                       break;
1385                   if (i < q->count)
1386                     continue;
1387                   queue_push2(q, DISABLE_INFARCH, s->name);
1388                 }
1389             }
1390         }
1391       if ((set & SOLVER_SETREPO) != 0 && solv->duprules != solv->duprules_end)
1392         {
1393           if (select == SOLVER_SOLVABLE)
1394             queue_push2(q, DISABLE_DUP, pool->solvables[what].name);
1395           else
1396             {
1397               int qcnt = q->count;
1398               FOR_JOB_SELECT(p, pp, select, what)
1399                 {
1400                   s = pool->solvables + p;
1401                   /* unify names */
1402                   for (i = qcnt; i < q->count; i += 2)
1403                     if (q->elements[i + 1] == s->name)
1404                       break;
1405                   if (i < q->count)
1406                     continue;
1407                   queue_push2(q, DISABLE_DUP, s->name);
1408                 }
1409             }
1410         }
1411       if (!installed)
1412         return;
1413       /* now the hard part: disable some update rules */
1414
1415       /* first check if we have noobs or installed packages in the job */
1416       FOR_JOB_SELECT(p, pp, select, what)
1417         {
1418           if (pool->solvables[p].repo == installed)
1419             {
1420               if (select == SOLVER_SOLVABLE)
1421                 queue_push2(q, DISABLE_UPDATE, what);
1422               return;
1423             }
1424           if (solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p))
1425             return;
1426         }
1427
1428       /* all job packages obsolete */
1429       qstart = q->count;
1430       pass = 0;
1431       memset(&omap, 0, sizeof(omap));
1432       FOR_JOB_SELECT(p, pp, select, what)
1433         {
1434           Id p2, pp2;
1435
1436           if (pass == 1)
1437             map_grow(&omap, installed->end - installed->start);
1438           s = pool->solvables + p;
1439           if (s->obsoletes)
1440             {
1441               Id obs, *obsp;
1442               obsp = s->repo->idarraydata + s->obsoletes;
1443               while ((obs = *obsp++) != 0)
1444                 FOR_PROVIDES(p2, pp2, obs)
1445                   {
1446                     Solvable *ps = pool->solvables + p2;
1447                     if (ps->repo != installed)
1448                       continue;
1449                     if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, ps, obs))
1450                       continue;
1451                     if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
1452                       continue;
1453                     if (pass)
1454                       MAPSET(&omap, p2 - installed->start);
1455                     else
1456                       queue_push2(q, DISABLE_UPDATE, p2);
1457                   }
1458             }
1459           FOR_PROVIDES(p2, pp2, s->name)
1460             {
1461               Solvable *ps = pool->solvables + p2;
1462               if (ps->repo != installed)
1463                 continue;
1464               if (!pool->implicitobsoleteusesprovides && ps->name != s->name)
1465                 continue;
1466               if (pool->obsoleteusescolors && !pool_colormatch(pool, s, ps))
1467                 continue;
1468               if (pass)
1469                 MAPSET(&omap, p2 - installed->start);
1470               else
1471                 queue_push2(q, DISABLE_UPDATE, p2);
1472             }
1473           if (pass)
1474             {
1475               for (i = j = qstart; i < q->count; i += 2)
1476                 {
1477                   if (MAPTST(&omap, q->elements[i + 1] - installed->start))
1478                     {
1479                       MAPCLR(&omap, q->elements[i + 1] - installed->start);
1480                       q->elements[j + 1] = q->elements[i + 1];
1481                       j += 2;
1482                     }
1483                 }
1484               queue_truncate(q, j);
1485             }
1486           if (q->count == qstart)
1487             break;
1488           pass++;
1489         }
1490       if (omap.size)
1491         map_free(&omap);
1492
1493       if (qstart == q->count)
1494         return;         /* nothing to prune */
1495       if ((set & (SOLVER_SETEVR | SOLVER_SETARCH | SOLVER_SETVENDOR)) == (SOLVER_SETEVR | SOLVER_SETARCH | SOLVER_SETVENDOR))
1496         return;         /* all is set */
1497
1498       /* now that we know which installed packages are obsoleted check each of them */
1499       for (i = j = qstart; i < q->count; i += 2)
1500         {
1501           Solvable *is = pool->solvables + q->elements[i + 1];
1502           FOR_JOB_SELECT(p, pp, select, what)
1503             {
1504               int illegal = 0;
1505               s = pool->solvables + p;
1506               if ((set & SOLVER_SETEVR) != 0)
1507                 illegal |= POLICY_ILLEGAL_DOWNGRADE;    /* ignore */
1508               if ((set & SOLVER_SETARCH) != 0)
1509                 illegal |= POLICY_ILLEGAL_ARCHCHANGE;   /* ignore */
1510               if ((set & SOLVER_SETVENDOR) != 0)
1511                 illegal |= POLICY_ILLEGAL_VENDORCHANGE; /* ignore */
1512               illegal = policy_is_illegal(solv, is, s, illegal);
1513               if (illegal && illegal == POLICY_ILLEGAL_DOWNGRADE && (set & SOLVER_SETEV) != 0)
1514                 {
1515                   /* it's ok if the EV is different */
1516                   if (pool_evrcmp(pool, is->evr, s->evr, EVRCMP_COMPARE_EVONLY) != 0)
1517                     illegal = 0;
1518                 }
1519               if (illegal)
1520                 break;
1521             }
1522           if (!p)
1523             {
1524               /* no package conflicts with the update rule */
1525               /* thus keep the DISABLE_UPDATE */
1526               q->elements[j + 1] = q->elements[i + 1];
1527               j += 2;
1528             }
1529         }
1530       queue_truncate(q, j);
1531       return;
1532
1533     case SOLVER_ERASE:
1534       if (!installed)
1535         break;
1536       FOR_JOB_SELECT(p, pp, select, what)
1537         if (pool->solvables[p].repo == installed)
1538           queue_push2(q, DISABLE_UPDATE, p);
1539       return;
1540     default:
1541       return;
1542     }
1543 }
1544
1545 /* disable all policy rules that are in conflict with our job list */
1546 void
1547 solver_disablepolicyrules(Solver *solv)
1548 {
1549   Queue *job = &solv->job;
1550   int i, j;
1551   Queue allq;
1552   Rule *r;
1553   Id lastjob = -1;
1554   Id allqbuf[128];
1555
1556   queue_init_buffer(&allq, allqbuf, sizeof(allqbuf)/sizeof(*allqbuf));
1557
1558   for (i = solv->jobrules; i < solv->jobrules_end; i++)
1559     {
1560       r = solv->rules + i;
1561       if (r->d < 0)     /* disabled? */
1562         continue;
1563       j = solv->ruletojob.elements[i - solv->jobrules];
1564       if (j == lastjob)
1565         continue;
1566       lastjob = j;
1567       jobtodisablelist(solv, job->elements[j], job->elements[j + 1], &allq);
1568     }
1569   if (solv->cleandepsmap.size)
1570     {
1571       solver_createcleandepsmap(solv);
1572       for (i = solv->installed->start; i < solv->installed->end; i++)
1573         if (MAPTST(&solv->cleandepsmap, i - solv->installed->start))
1574           queue_push2(&allq, DISABLE_UPDATE, i);
1575     }
1576   MAPZERO(&solv->noupdate);
1577   for (i = 0; i < allq.count; i += 2)
1578     {
1579       Id type = allq.elements[i], arg = allq.elements[i + 1];
1580       switch(type)
1581         {
1582         case DISABLE_UPDATE:
1583           disableupdaterule(solv, arg);
1584           break;
1585         case DISABLE_INFARCH:
1586           disableinfarchrule(solv, arg);
1587           break;
1588         case DISABLE_DUP:
1589           disableduprule(solv, arg);
1590           break;
1591         default:
1592           break;
1593         }
1594     }
1595   queue_free(&allq);
1596 }
1597
1598 /* we just disabled job #jobidx, now reenable all policy rules that were
1599  * disabled because of this job */
1600 void
1601 solver_reenablepolicyrules(Solver *solv, int jobidx)
1602 {
1603   Queue *job = &solv->job;
1604   int i, j;
1605   Queue q, allq;
1606   Rule *r;
1607   Id lastjob = -1;
1608   Id qbuf[32], allqbuf[128];
1609
1610   queue_init_buffer(&q, qbuf, sizeof(qbuf)/sizeof(*qbuf));
1611   queue_init_buffer(&allq, allqbuf, sizeof(allqbuf)/sizeof(*allqbuf));
1612   jobtodisablelist(solv, job->elements[jobidx], job->elements[jobidx + 1], &q);
1613   if (!q.count)
1614     return;
1615   for (i = solv->jobrules; i < solv->jobrules_end; i++)
1616     {
1617       r = solv->rules + i;
1618       if (r->d < 0)     /* disabled? */
1619         continue;
1620       j = solv->ruletojob.elements[i - solv->jobrules];
1621       if (j == lastjob)
1622         continue;
1623       lastjob = j;
1624       jobtodisablelist(solv, job->elements[j], job->elements[j + 1], &allq);
1625     }
1626   if (solv->cleandepsmap.size)
1627     {
1628       solver_createcleandepsmap(solv);
1629       for (i = solv->installed->start; i < solv->installed->end; i++)
1630         if (MAPTST(&solv->cleandepsmap, i - solv->installed->start))
1631           queue_push2(&allq, DISABLE_UPDATE, i);
1632     }
1633   for (j = 0; j < q.count; j += 2)
1634     {
1635       Id type = q.elements[j], arg = q.elements[j + 1];
1636       for (i = 0; i < allq.count; i += 2)
1637         if (allq.elements[i] == type && allq.elements[i + 1] == arg)
1638           break;
1639       if (i < allq.count)
1640         continue;       /* still disabled */
1641       switch(type)
1642         {
1643         case DISABLE_UPDATE:
1644           reenableupdaterule(solv, arg);
1645           break;
1646         case DISABLE_INFARCH:
1647           reenableinfarchrule(solv, arg);
1648           break;
1649         case DISABLE_DUP:
1650           reenableduprule(solv, arg);
1651           break;
1652         }
1653     }
1654   queue_free(&allq);
1655   queue_free(&q);
1656 }
1657
1658
1659 /***********************************************************************
1660  ***
1661  ***  Rule info part, tell the user what the rule is about.
1662  ***
1663  ***/
1664
1665 static void
1666 addrpmruleinfo(Solver *solv, Id p, Id d, int type, Id dep)
1667 {
1668   Pool *pool = solv->pool;
1669   Rule *r;
1670   Id w2, op, od, ow2;
1671
1672   /* check if this creates the rule we're searching for */
1673   r = solv->rules + solv->ruleinfoq->elements[0];
1674   op = r->p;
1675   od = r->d < 0 ? -r->d - 1 : r->d;
1676   ow2 = 0;
1677
1678   /* normalize */
1679   w2 = d > 0 ? 0 : d;
1680   if (p < 0 && d > 0 && (!pool->whatprovidesdata[d] || !pool->whatprovidesdata[d + 1]))
1681     {
1682       w2 = pool->whatprovidesdata[d];
1683       d = 0;
1684
1685     }
1686   if (p > 0 && d < 0)           /* this hack is used for buddy deps */
1687     {
1688       w2 = p;
1689       p = d;
1690     }
1691
1692   if (d > 0)
1693     {
1694       if (p != op && !od)
1695         return;
1696       if (d != od)
1697         {
1698           Id *dp = pool->whatprovidesdata + d;
1699           Id *odp = pool->whatprovidesdata + od;
1700           while (*dp)
1701             if (*dp++ != *odp++)
1702               return;
1703           if (*odp)
1704             return;
1705         }
1706       w2 = 0;
1707       /* handle multiversion conflict rules */
1708       if (p < 0 && pool->whatprovidesdata[d] < 0)
1709         {
1710           w2 = pool->whatprovidesdata[d];
1711           /* XXX: free memory */
1712         }
1713     }
1714   else
1715     {
1716       if (od)
1717         return;
1718       ow2 = r->w2;
1719       if (p > w2)
1720         {
1721           if (w2 != op || p != ow2)
1722             return;
1723         }
1724       else
1725         {
1726           if (p != op || w2 != ow2)
1727             return;
1728         }
1729     }
1730   /* yep, rule matches. record info */
1731   queue_push(solv->ruleinfoq, type);
1732   if (type == SOLVER_RULE_RPM_SAME_NAME)
1733     {
1734       /* we normalize same name order */
1735       queue_push(solv->ruleinfoq, op < 0 ? -op : 0);
1736       queue_push(solv->ruleinfoq, ow2 < 0 ? -ow2 : 0);
1737     }
1738   else
1739     {
1740       queue_push(solv->ruleinfoq, p < 0 ? -p : 0);
1741       queue_push(solv->ruleinfoq, w2 < 0 ? -w2 : 0);
1742     }
1743   queue_push(solv->ruleinfoq, dep);
1744 }
1745
1746 static int
1747 solver_allruleinfos_cmp(const void *ap, const void *bp, void *dp)
1748 {
1749   const Id *a = ap, *b = bp;
1750   int r;
1751
1752   r = a[0] - b[0];
1753   if (r)
1754     return r;
1755   r = a[1] - b[1];
1756   if (r)
1757     return r;
1758   r = a[2] - b[2];
1759   if (r)
1760     return r;
1761   r = a[3] - b[3];
1762   if (r)
1763     return r;
1764   return 0;
1765 }
1766
1767 int
1768 solver_allruleinfos(Solver *solv, Id rid, Queue *rq)
1769 {
1770   Pool *pool = solv->pool;
1771   Rule *r = solv->rules + rid;
1772   int i, j;
1773
1774   queue_empty(rq);
1775   if (rid <= 0 || rid >= solv->rpmrules_end)
1776     {
1777       Id type, from, to, dep;
1778       type = solver_ruleinfo(solv, rid, &from, &to, &dep);
1779       queue_push(rq, type);
1780       queue_push(rq, from);
1781       queue_push(rq, to);
1782       queue_push(rq, dep);
1783       return 1;
1784     }
1785   if (r->p >= 0)
1786     return 0;
1787   queue_push(rq, rid);
1788   solv->ruleinfoq = rq;
1789   solver_addrpmrulesforsolvable(solv, pool->solvables - r->p, 0);
1790   /* also try reverse direction for conflicts */
1791   if ((r->d == 0 || r->d == -1) && r->w2 < 0)
1792     solver_addrpmrulesforsolvable(solv, pool->solvables - r->w2, 0);
1793   solv->ruleinfoq = 0;
1794   queue_shift(rq);
1795   /* now sort & unify em */
1796   if (!rq->count)
1797     return 0;
1798   sat_sort(rq->elements, rq->count / 4, 4 * sizeof(Id), solver_allruleinfos_cmp, 0);
1799   /* throw out identical entries */
1800   for (i = j = 0; i < rq->count; i += 4)
1801     {
1802       if (j)
1803         {
1804           if (rq->elements[i] == rq->elements[j - 4] &&
1805               rq->elements[i + 1] == rq->elements[j - 3] &&
1806               rq->elements[i + 2] == rq->elements[j - 2] &&
1807               rq->elements[i + 3] == rq->elements[j - 1])
1808             continue;
1809         }
1810       rq->elements[j++] = rq->elements[i];
1811       rq->elements[j++] = rq->elements[i + 1];
1812       rq->elements[j++] = rq->elements[i + 2];
1813       rq->elements[j++] = rq->elements[i + 3];
1814     }
1815   rq->count = j;
1816   return j / 4;
1817 }
1818
1819 SolverRuleinfo
1820 solver_ruleinfo(Solver *solv, Id rid, Id *fromp, Id *top, Id *depp)
1821 {
1822   Pool *pool = solv->pool;
1823   Rule *r = solv->rules + rid;
1824   SolverRuleinfo type = SOLVER_RULE_UNKNOWN;
1825
1826   if (fromp)
1827     *fromp = 0;
1828   if (top)
1829     *top = 0;
1830   if (depp)
1831     *depp = 0;
1832   if (rid > 0 && rid < solv->rpmrules_end)
1833     {
1834       Queue rq;
1835       int i;
1836
1837       if (r->p >= 0)
1838         return SOLVER_RULE_RPM;
1839       if (fromp)
1840         *fromp = -r->p;
1841       queue_init(&rq);
1842       queue_push(&rq, rid);
1843       solv->ruleinfoq = &rq;
1844       solver_addrpmrulesforsolvable(solv, pool->solvables - r->p, 0);
1845       /* also try reverse direction for conflicts */
1846       if ((r->d == 0 || r->d == -1) && r->w2 < 0)
1847         solver_addrpmrulesforsolvable(solv, pool->solvables - r->w2, 0);
1848       solv->ruleinfoq = 0;
1849       type = SOLVER_RULE_RPM;
1850       for (i = 1; i < rq.count; i += 4)
1851         {
1852           Id qt, qo, qp, qd;
1853           qt = rq.elements[i];
1854           qp = rq.elements[i + 1];
1855           qo = rq.elements[i + 2];
1856           qd = rq.elements[i + 3];
1857           if (type == SOLVER_RULE_RPM || type > qt)
1858             {
1859               type = qt;
1860               if (fromp)
1861                 *fromp = qp;
1862               if (top)
1863                 *top = qo;
1864               if (depp)
1865                 *depp = qd;
1866             }
1867         }
1868       queue_free(&rq);
1869       return type;
1870     }
1871   if (rid >= solv->jobrules && rid < solv->jobrules_end)
1872     {
1873       Id jidx = solv->ruletojob.elements[rid - solv->jobrules];
1874       if (fromp)
1875         *fromp = jidx;
1876       if (top)
1877         *top = solv->job.elements[jidx];
1878       if (depp)
1879         *depp = solv->job.elements[jidx + 1];
1880       if ((r->d == 0 || r->d == -1) && r->w2 == 0 && r->p == -SYSTEMSOLVABLE && (solv->job.elements[jidx] & SOLVER_SELECTMASK) != SOLVER_SOLVABLE_ONE_OF)
1881         return SOLVER_RULE_JOB_NOTHING_PROVIDES_DEP;
1882       return SOLVER_RULE_JOB;
1883     }
1884   if (rid >= solv->updaterules && rid < solv->updaterules_end)
1885     {
1886       if (fromp)
1887         *fromp = solv->installed->start + (rid - solv->updaterules);
1888       return SOLVER_RULE_UPDATE;
1889     }
1890   if (rid >= solv->featurerules && rid < solv->featurerules_end)
1891     {
1892       if (fromp)
1893         *fromp = solv->installed->start + (rid - solv->featurerules);
1894       return SOLVER_RULE_FEATURE;
1895     }
1896   if (rid >= solv->duprules && rid < solv->duprules_end)
1897     {
1898       if (fromp)
1899         *fromp = -r->p;
1900       if (depp)
1901         *depp = pool->solvables[-r->p].name;
1902       return SOLVER_RULE_DISTUPGRADE;
1903     }
1904   if (rid >= solv->infarchrules && rid < solv->infarchrules_end)
1905     {
1906       if (fromp)
1907         *fromp = -r->p;
1908       if (depp)
1909         *depp = pool->solvables[-r->p].name;
1910       return SOLVER_RULE_INFARCH;
1911     }
1912   if (rid >= solv->choicerules && rid < solv->choicerules_end)
1913     {
1914       return SOLVER_RULE_CHOICE;
1915     }
1916   if (rid >= solv->learntrules)
1917     {
1918       return SOLVER_RULE_LEARNT;
1919     }
1920   return SOLVER_RULE_UNKNOWN;
1921 }
1922
1923 void
1924 solver_addchoicerules(Solver *solv)
1925 {
1926   Pool *pool = solv->pool;
1927   Map m, mneg;
1928   Rule *r;
1929   Queue q, qi;
1930   int i, j, rid, havechoice;
1931   Id p, d, *pp;
1932   Id p2, pp2;
1933   Solvable *s, *s2;
1934
1935   solv->choicerules = solv->nrules;
1936   if (!pool->installed)
1937     {
1938       solv->choicerules_end = solv->nrules;
1939       return;
1940     }
1941   solv->choicerules_ref = sat_calloc(solv->rpmrules_end, sizeof(Id));
1942   queue_init(&q);
1943   queue_init(&qi);
1944   map_init(&m, pool->nsolvables);
1945   map_init(&mneg, pool->nsolvables);
1946   /* set up negative assertion map from infarch and dup rules */
1947   for (rid = solv->infarchrules, r = solv->rules + rid; rid < solv->infarchrules_end; rid++, r++)
1948     if (r->p < 0 && !r->w2 && (r->d == 0 || r->d == -1))
1949       MAPSET(&mneg, -r->p);
1950   for (rid = solv->duprules, r = solv->rules + rid; rid < solv->duprules_end; rid++, r++)
1951     if (r->p < 0 && !r->w2 && (r->d == 0 || r->d == -1))
1952       MAPSET(&mneg, -r->p);
1953   for (rid = 1; rid < solv->rpmrules_end ; rid++)
1954     {
1955       r = solv->rules + rid;
1956       if (r->p >= 0 || ((r->d == 0 || r->d == -1) && r->w2 < 0))
1957         continue;       /* only look at requires rules */
1958       // solver_printrule(solv, SAT_DEBUG_RESULT, r);
1959       queue_empty(&q);
1960       queue_empty(&qi);
1961       havechoice = 0;
1962       FOR_RULELITERALS(p, pp, r)
1963         {
1964           if (p < 0)
1965             continue;
1966           s = pool->solvables + p;
1967           if (!s->repo)
1968             continue;
1969           if (s->repo == pool->installed)
1970             {
1971               queue_push(&q, p);
1972               continue;
1973             }
1974           /* check if this package is "blocked" by a installed package */
1975           s2 = 0;
1976           FOR_PROVIDES(p2, pp2, s->name)
1977             {
1978               s2 = pool->solvables + p2;
1979               if (s2->repo != pool->installed)
1980                 continue;
1981               if (!pool->implicitobsoleteusesprovides && s->name != s2->name)
1982                 continue;
1983               if (pool->obsoleteusescolors && !pool_colormatch(pool, s, s2))
1984                 continue;
1985               break;
1986             }
1987           if (p2)
1988             {
1989               /* found installed package p2 that we can update to p */
1990               if (MAPTST(&mneg, p))
1991                 continue;
1992               if (policy_is_illegal(solv, s2, s, 0))
1993                 continue;
1994               queue_push(&qi, p2);
1995               queue_push(&q, p);
1996               continue;
1997             }
1998           if (s->obsoletes)
1999             {
2000               Id obs, *obsp = s->repo->idarraydata + s->obsoletes;
2001               s2 = 0;
2002               while ((obs = *obsp++) != 0)
2003                 {
2004                   FOR_PROVIDES(p2, pp2, obs)
2005                     {
2006                       s2 = pool->solvables + p2;
2007                       if (s2->repo != pool->installed)
2008                         continue;
2009                       if (!pool->obsoleteusesprovides && !pool_match_nevr(pool, pool->solvables + p2, obs))
2010                         continue;
2011                       if (pool->obsoleteusescolors && !pool_colormatch(pool, s, s2))
2012                         continue;
2013                       break;
2014                     }
2015                   if (p2)
2016                     break;
2017                 }
2018               if (obs)
2019                 {
2020                   /* found installed package p2 that we can update to p */
2021                   if (MAPTST(&mneg, p))
2022                     continue;
2023                   if (policy_is_illegal(solv, s2, s, 0))
2024                     continue;
2025                   queue_push(&qi, p2);
2026                   queue_push(&q, p);
2027                   continue;
2028                 }
2029             }
2030           /* package p is independent of the installed ones */
2031           havechoice = 1;
2032         }
2033       if (!havechoice || !q.count)
2034         continue;       /* no choice */
2035
2036       /* now check the update rules of the installed package.
2037        * if all packages of the update rules are contained in
2038        * the dependency rules, there's no need to set up the choice rule */
2039       map_empty(&m);
2040       FOR_RULELITERALS(p, pp, r)
2041         if (p > 0)
2042           MAPSET(&m, p);
2043       for (i = 0; i < qi.count; i++)
2044         {
2045           if (!qi.elements[i])
2046             continue;
2047           Rule *ur = solv->rules + solv->updaterules + (qi.elements[i] - pool->installed->start);
2048           if (!ur->p)
2049             ur = solv->rules + solv->featurerules + (qi.elements[i] - pool->installed->start);
2050           if (!ur->p)
2051             continue;
2052           FOR_RULELITERALS(p, pp, ur)
2053             if (!MAPTST(&m, p))
2054               break;
2055           if (p)
2056             break;
2057           for (j = i + 1; j < qi.count; j++)
2058             if (qi.elements[i] == qi.elements[j])
2059               qi.elements[j] = 0;
2060         }
2061       if (i == qi.count)
2062         {
2063 #if 0
2064           printf("skipping choice ");
2065           solver_printrule(solv, SAT_DEBUG_RESULT, solv->rules + rid);
2066 #endif
2067           continue;
2068         }
2069       d = q.count ? pool_queuetowhatprovides(pool, &q) : 0;
2070       solver_addrule(solv, r->p, d);
2071       queue_push(&solv->weakruleq, solv->nrules - 1);
2072       solv->choicerules_ref[solv->nrules - 1 - solv->choicerules] = rid;
2073 #if 0
2074       printf("OLD ");
2075       solver_printrule(solv, SAT_DEBUG_RESULT, solv->rules + rid);
2076       printf("WEAK CHOICE ");
2077       solver_printrule(solv, SAT_DEBUG_RESULT, solv->rules + solv->nrules - 1);
2078 #endif
2079     }
2080   queue_free(&q);
2081   queue_free(&qi);
2082   map_free(&m);
2083   map_free(&mneg);
2084   solv->choicerules_end = solv->nrules;
2085 }
2086
2087 /* called when a choice rule is disabled by analyze_unsolvable. We also
2088  * have to disable all other choice rules so that the best packages get
2089  * picked */
2090 void
2091 solver_disablechoicerules(Solver *solv, Rule *r)
2092 {
2093   Id rid, p, *pp;
2094   Pool *pool = solv->pool;
2095   Map m;
2096   Rule *or;
2097
2098   or = solv->rules + solv->choicerules_ref[(r - solv->rules) - solv->choicerules];
2099   map_init(&m, pool->nsolvables);
2100   FOR_RULELITERALS(p, pp, or)
2101     if (p > 0)
2102       MAPSET(&m, p);
2103   FOR_RULELITERALS(p, pp, r)
2104     if (p > 0)
2105       MAPCLR(&m, p);
2106   for (rid = solv->choicerules; rid < solv->choicerules_end; rid++)
2107     {
2108       r = solv->rules + rid;
2109       if (r->d < 0)
2110         continue;
2111       or = solv->rules + solv->choicerules_ref[(r - solv->rules) - solv->choicerules];
2112       FOR_RULELITERALS(p, pp, or)
2113         if (p > 0 && MAPTST(&m, p))
2114           break;
2115       if (p)
2116         solver_disablerule(solv, r);
2117     }
2118 }
2119
2120 static void solver_createcleandepsmap(Solver *solv)
2121 {
2122   Pool *pool = solv->pool;
2123   Repo *installed = solv->installed;
2124   Queue *job = &solv->job;
2125   Map userinstalled;
2126   Map im;
2127   Map installedm;
2128   Rule *r;
2129   Id rid, how, what, select;
2130   Id p, pp, ip, *jp;
2131   Id req, *reqp, sup, *supp;
2132   Solvable *s;
2133   Queue iq;
2134   int i;
2135
2136   map_init(&userinstalled, installed->end - installed->start);
2137   map_init(&im, pool->nsolvables);
2138   map_init(&installedm, pool->nsolvables);
2139   map_empty(&solv->cleandepsmap);
2140   queue_init(&iq);
2141
2142   for (i = 0; i < job->count; i += 2)
2143     {
2144       how = job->elements[i];
2145       if ((how & SOLVER_JOBMASK) == SOLVER_USERINSTALLED)
2146         {
2147           what = job->elements[i + 1];
2148           select = how & SOLVER_SELECTMASK;
2149           FOR_JOB_SELECT(p, pp, select, what)
2150             if (pool->solvables[p].repo == installed)
2151               MAPSET(&userinstalled, p - installed->start);
2152         }
2153     }
2154   /* add all positive elements (e.g. locks) to "userinstalled" */
2155   for (rid = solv->jobrules; rid < solv->jobrules_end; rid++)
2156     {
2157       r = solv->rules + rid;
2158       if (r->d < 0)
2159         continue;
2160       FOR_RULELITERALS(p, jp, r)
2161         if (p > 0 && pool->solvables[p].repo == installed)
2162           MAPSET(&userinstalled, p - installed->start);
2163     }
2164   for (rid = solv->jobrules; rid < solv->jobrules_end; rid++)
2165     {
2166       r = solv->rules + rid;
2167       if (r->p >= 0 || r->d != 0)
2168         continue;       /* disabled or not erase */
2169       p = -r->p;
2170       if (pool->solvables[p].repo != installed)
2171         continue;
2172       MAPCLR(&userinstalled, p - installed->start);
2173       i = solv->ruletojob.elements[rid - solv->jobrules];
2174       how = job->elements[i];
2175       if ((how & (SOLVER_JOBMASK|SOLVER_CLEANDEPS)) == (SOLVER_ERASE|SOLVER_CLEANDEPS))
2176         queue_push(&iq, p);
2177     }
2178   for (p = installed->start; p < installed->end; p++)
2179     {
2180       if (pool->solvables[p].repo != installed)
2181         continue;
2182       MAPSET(&installedm, p);
2183       MAPSET(&im, p);
2184     }
2185
2186   while (iq.count)
2187     {
2188       ip = queue_shift(&iq);
2189       s = pool->solvables + ip;
2190       if (!MAPTST(&im, ip))
2191         continue;
2192       if (!MAPTST(&installedm, ip))
2193         continue;
2194       if (s->repo == installed && MAPTST(&userinstalled, ip - installed->start))
2195         continue;
2196       MAPCLR(&im, ip);
2197 #ifdef CLEANDEPSDEBUG
2198       printf("hello %s\n", pool_solvable2str(pool, s));
2199 #endif
2200       if (s->requires)
2201         {
2202           reqp = s->repo->idarraydata + s->requires;
2203           while ((req = *reqp++) != 0)
2204             {
2205               if (req == SOLVABLE_PREREQMARKER)
2206                 continue;
2207 #if 0
2208               /* count number of installed packages that match */
2209               count = 0;
2210               FOR_PROVIDES(p, pp, req)
2211                 if (MAPTST(&installedm, p))
2212                   count++;
2213               if (count > 1)
2214                 continue;
2215 #endif
2216               FOR_PROVIDES(p, pp, req)
2217                 {
2218                   if (MAPTST(&im, p))
2219                     {
2220 #ifdef CLEANDEPSDEBUG
2221                       printf("%s requires %s\n", pool_solvid2str(pool, ip), pool_solvid2str(pool, p));
2222 #endif
2223                       queue_push(&iq, p);
2224                     }
2225                 }
2226             }
2227         }
2228       if (s->recommends)
2229         {
2230           reqp = s->repo->idarraydata + s->recommends;
2231           while ((req = *reqp++) != 0)
2232             {
2233 #if 0
2234               count = 0;
2235               FOR_PROVIDES(p, pp, req)
2236                 if (MAPTST(&installedm, p))
2237                   count++;
2238               if (count > 1)
2239                 continue;
2240 #endif
2241               FOR_PROVIDES(p, pp, req)
2242                 {
2243                   if (MAPTST(&im, p))
2244                     {
2245 #ifdef CLEANDEPSDEBUG
2246                       printf("%s recommends %s\n", pool_solvid2str(pool, ip), pool_solvid2str(pool, p));
2247 #endif
2248                       queue_push(&iq, p);
2249                     }
2250                 }
2251             }
2252         }
2253       if (!iq.count)
2254         {
2255           /* supplements pass */
2256           for (ip = solv->installed->start; ip < solv->installed->end; ip++)
2257             {
2258               if (!MAPTST(&installedm, ip))
2259                 continue;
2260               s = pool->solvables + ip;
2261               if (!s->supplements)
2262                 continue;
2263               if (!MAPTST(&im, ip))
2264                 continue;
2265               supp = s->repo->idarraydata + s->supplements;
2266               while ((sup = *supp++) != 0)
2267                 if (!dep_possible(solv, sup, &im) && dep_possible(solv, sup, &installedm))
2268                   break;
2269               /* no longer supplemented, also erase */
2270               if (sup)
2271                 {
2272 #ifdef CLEANDEPSDEBUG
2273                   printf("%s supplemented\n", pool_solvid2str(pool, ip));
2274 #endif
2275                   queue_push(&iq, ip);
2276                 }
2277             }
2278         }
2279     }
2280
2281   /* turn userinstalled into remove set for pruning */
2282   map_empty(&userinstalled);
2283   for (rid = solv->jobrules; rid < solv->jobrules_end; rid++)
2284     {
2285       r = solv->rules + rid;
2286       if (r->p >= 0 || r->d != 0)
2287         continue;       /* disabled or not erase */
2288       p = -r->p;
2289       MAPCLR(&im, p);
2290       if (pool->solvables[p].repo == installed)
2291         MAPSET(&userinstalled, p - installed->start);
2292     }
2293   for (p = installed->start; p < installed->end; p++)
2294     if (MAPTST(&im, p))
2295       queue_push(&iq, p);
2296   for (rid = solv->jobrules; rid < solv->jobrules_end; rid++)
2297     {
2298       r = solv->rules + rid;
2299       if (r->d < 0)
2300         continue;
2301       FOR_RULELITERALS(p, jp, r)
2302         if (p > 0)
2303           queue_push(&iq, p);
2304     }
2305   /* also put directly addressed packages on the install queue
2306    * so we can mark patterns as installed */
2307   for (i = 0; i < job->count; i += 2)
2308     {
2309       how = job->elements[i];
2310       if ((how & SOLVER_JOBMASK) == SOLVER_USERINSTALLED)
2311         {
2312           what = job->elements[i + 1];
2313           select = how & SOLVER_SELECTMASK;
2314           if (select == SOLVER_SOLVABLE && pool->solvables[what].repo != installed)
2315             queue_push(&iq, what);
2316         }
2317     }
2318   while (iq.count)
2319     {
2320       ip = queue_shift(&iq);
2321       s = pool->solvables + ip;
2322 #ifdef CLEANDEPSDEBUG
2323       printf("bye %s\n", pool_solvable2str(pool, s));
2324 #endif
2325       if (s->requires)
2326         {
2327           reqp = s->repo->idarraydata + s->requires;
2328           while ((req = *reqp++) != 0)
2329             {
2330               FOR_PROVIDES(p, pp, req)
2331                 {
2332                   if (!MAPTST(&im, p) && MAPTST(&installedm, p))
2333                     {
2334                       if (p == ip)
2335                         continue;
2336                       if (MAPTST(&userinstalled, p - installed->start))
2337                         continue;
2338 #ifdef CLEANDEPSDEBUG
2339                       printf("%s requires %s\n", pool_solvid2str(pool, ip), pool_solvid2str(pool, p));
2340 #endif
2341                       MAPSET(&im, p);
2342                       queue_push(&iq, p);
2343                     }
2344                 }
2345             }
2346         }
2347       if (s->recommends)
2348         {
2349           reqp = s->repo->idarraydata + s->recommends;
2350           while ((req = *reqp++) != 0)
2351             {
2352               FOR_PROVIDES(p, pp, req)
2353                 {
2354                   if (!MAPTST(&im, p) && MAPTST(&installedm, p))
2355                     {
2356                       if (p == ip)
2357                         continue;
2358                       if (MAPTST(&userinstalled, p - installed->start))
2359                         continue;
2360 #ifdef CLEANDEPSDEBUG
2361                       printf("%s recommends %s\n", pool_solvid2str(pool, ip), pool_solvid2str(pool, p));
2362 #endif
2363                       MAPSET(&im, p);
2364                       queue_push(&iq, p);
2365                     }
2366                 }
2367             }
2368         }
2369       if (!iq.count)
2370         {
2371           /* supplements pass */
2372           for (ip = installed->start; ip < installed->end; ip++)
2373             {
2374               if (!MAPTST(&installedm, ip))
2375                 continue;
2376               if (MAPTST(&userinstalled, ip - installed->start))
2377                 continue;
2378               s = pool->solvables + ip;
2379               if (!s->supplements)
2380                 continue;
2381               if (MAPTST(&im, ip) || !MAPTST(&installedm, ip))
2382                 continue;
2383               supp = s->repo->idarraydata + s->supplements;
2384               while ((sup = *supp++) != 0)
2385                 if (dep_possible(solv, sup, &im))
2386                   break;
2387               if (sup)
2388                 {
2389 #ifdef CLEANDEPSDEBUG
2390                   printf("%s supplemented\n", pool_solvid2str(pool, ip));
2391 #endif
2392                   MAPSET(&im, ip);
2393                   queue_push(&iq, ip);
2394                 }
2395             }
2396         }
2397     }
2398
2399   queue_free(&iq);
2400   for (p = installed->start; p < installed->end; p++)
2401     {
2402       if (pool->solvables[p].repo != installed)
2403         continue;
2404       if (!MAPTST(&im, p))
2405         MAPSET(&solv->cleandepsmap, p - installed->start);
2406     }
2407   map_free(&im);
2408   map_free(&installedm);
2409   map_free(&userinstalled);
2410 }
2411
2412
2413 /* EOF */