src/rules.c

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