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 "util.h"
  24 #include "policy.h"
  25 #include "solverdebug.h"
  26
  27 #define RULES_BLOCK 63
  28
  29 static void addrpmruleinfo(Solver *solv, Id p, Id d, int type, Id dep);
  30
  31 /*-------------------------------------------------------------------
  32  * Check if dependency is possible
  33  *
  34  * this mirrors solver_dep_fulfilled
  35  * but uses map m instead of the decisionmap
  36  */
  37
  38 static inline int
  39 dep_possible(Solver *solv, Id dep, Map *m)
  40 {
  41   Pool *pool = solv->pool;
  42   Id p, pp;
  43
  44   if (ISRELDEP(dep))
  45     {
  46       Reldep *rd = GETRELDEP(pool, dep);
  47       if (rd->flags == REL_AND)
  48         {
  49           if (!dep_possible(solv, rd->name, m))
  50             return 0;
  51           return dep_possible(solv, rd->evr, m);
  52         }
  53       if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_SPLITPROVIDES)
  54         return solver_splitprovides(solv, rd->evr);
  55       if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_INSTALLED)
  56         return solver_dep_installed(solv, rd->evr);
  57     }
  58   FOR_PROVIDES(p, pp, dep)
  59     {
  60       if (MAPTST(m, p))
  61         return 1;
  62     }
  63   return 0;
  64 }
  65
  66 /********************************************************************
  67  *
  68  * Rule handling
  69  *
  70  * - unify rules, remove duplicates
  71  */
  72
  73 /*-------------------------------------------------------------------
  74  *
  75  * compare rules for unification sort
  76  *
  77  */
  78
  79 static int
  80 unifyrules_sortcmp(const void *ap, const void *bp, void *dp)
  81 {
  82   Pool *pool = dp;
  83   Rule *a = (Rule *)ap;
  84   Rule *b = (Rule *)bp;
  85   Id *ad, *bd;
  86   int x;
  87
  88   x = a->p - b->p;
  89   if (x)
  90     return x;                          /* p differs */
  91
  92   /* identical p */
  93   if (a->d == 0 && b->d == 0)
  94     return a->w2 - b->w2;              /* assertion: return w2 diff */
  95
  96   if (a->d == 0)                       /* a is assertion, b not */
  97     {
  98       x = a->w2 - pool->whatprovidesdata[b->d];
  99       return x ? x : -1;
 100     }
 101
 102   if (b->d == 0)                       /* b is assertion, a not */
 103     {
 104       x = pool->whatprovidesdata[a->d] - b->w2;
 105       return x ? x : 1;
 106     }
 107
 108   /* compare whatprovidesdata */
 109   ad = pool->whatprovidesdata + a->d;
 110   bd = pool->whatprovidesdata + b->d;
 111   while (*bd)
 112     if ((x = *ad++ - *bd++) != 0)
 113       return x;
 114   return *ad;
 115 }
 116
 117 int
 118 solver_samerule(Solver *solv, Rule *r1, Rule *r2)
 119 {
 120   return unifyrules_sortcmp(r1, r2, solv->pool);
 121 }
 122
 123
 124 /*-------------------------------------------------------------------
 125  *
 126  * unify rules
 127  * go over all rules and remove duplicates
 128  */
 129
 130 void
 131 solver_unifyrules(Solver *solv)
 132 {
 133   Pool *pool = solv->pool;
 134   int i, j;
 135   Rule *ir, *jr;
 136
 137   if (solv->nrules <= 1)               /* nothing to unify */
 138     return;
 139
 140   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- unifyrules -----\n");
 141
 142   /* sort rules first */
 143   sat_sort(solv->rules + 1, solv->nrules - 1, sizeof(Rule), unifyrules_sortcmp, solv->pool);
 144
 145   /* prune rules
 146    * i = unpruned
 147    * j = pruned
 148    */
 149   jr = 0;
 150   for (i = j = 1, ir = solv->rules + i; i < solv->nrules; i++, ir++)
 151     {
 152       if (jr && !unifyrules_sortcmp(ir, jr, pool))
 153         continue;                      /* prune! */
 154       jr = solv->rules + j++;          /* keep! */
 155       if (ir != jr)
 156         *jr = *ir;
 157     }
 158
 159   /* reduced count from nrules to j rules */
 160   POOL_DEBUG(SAT_DEBUG_STATS, "pruned rules from %d to %d\n", solv->nrules, j);
 161
 162   /* adapt rule buffer */
 163   solv->nrules = j;
 164   solv->rules = sat_extend_resize(solv->rules, solv->nrules, sizeof(Rule), RULES_BLOCK);
 165     /*
 166      * debug: statistics
 167      */
 168   IF_POOLDEBUG (SAT_DEBUG_STATS)
 169     {
 170       int binr = 0;
 171       int lits = 0;
 172       Id *dp;
 173       Rule *r;
 174
 175       for (i = 1; i < solv->nrules; i++)
 176         {
 177           r = solv->rules + i;
 178           if (r->d == 0)
 179             binr++;
 180           else
 181             {
 182               dp = solv->pool->whatprovidesdata + r->d;
 183               while (*dp++)
 184                 lits++;
 185             }
 186         }
 187       POOL_DEBUG(SAT_DEBUG_STATS, "  binary: %d\n", binr);
 188       POOL_DEBUG(SAT_DEBUG_STATS, "  normal: %d, %d literals\n", solv->nrules - 1 - binr, lits);
 189     }
 190   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- unifyrules end -----\n");
 191 }
 192
 193 #if 0
 194
 195 /*
 196  * hash rule
 197  */
 198
 199 static Hashval
 200 hashrule(Solver *solv, Id p, Id d, int n)
 201 {
 202   unsigned int x = (unsigned int)p;
 203   int *dp;
 204
 205   if (n <= 1)
 206     return (x * 37) ^ (unsigned int)d;
 207   dp = solv->pool->whatprovidesdata + d;
 208   while (*dp)
 209     x = (x * 37) ^ (unsigned int)*dp++;
 210   return x;
 211 }
 212 #endif
 213
 214
 215 /*-------------------------------------------------------------------
 216  *
 217  */
 218
 219 /*
 220  * add rule
 221  *  p = direct literal; always < 0 for installed rpm rules
 222  *  d, if < 0 direct literal, if > 0 offset into whatprovides, if == 0 rule is assertion (look at p only)
 223  *
 224  *
 225  * A requires b, b provided by B1,B2,B3 => (-A|B1|B2|B3)
 226  *
 227  * p < 0 : pkg id of A
 228  * d > 0 : Offset in whatprovidesdata (list of providers of b)
 229  *
 230  * A conflicts b, b provided by B1,B2,B3 => (-A|-B1), (-A|-B2), (-A|-B3)
 231  * p < 0 : pkg id of A
 232  * d < 0 : Id of solvable (e.g. B1)
 233  *
 234  * d == 0: unary rule, assertion => (A) or (-A)
 235  *
 236  *   Install:    p > 0, d = 0   (A)             user requested install
 237  *   Remove:     p < 0, d = 0   (-A)            user requested remove (also: uninstallable)
 238  *   Requires:   p < 0, d > 0   (-A|B1|B2|...)  d: <list of providers for requirement of p>
 239  *   Updates:    p > 0, d > 0   (A|B1|B2|...)   d: <list of updates for solvable p>
 240  *   Conflicts:  p < 0, d < 0   (-A|-B)         either p (conflict issuer) or d (conflict provider) (binary rule)
 241  *                                              also used for obsoletes
 242  *   ?:          p > 0, d < 0   (A|-B)
 243  *   No-op ?:    p = 0, d = 0   (null)          (used as policy rule placeholder)
 244  *
 245  *   resulting watches:
 246  *   ------------------
 247  *   Direct assertion (no watch needed)( if d <0 ) --> d = 0, w1 = p, w2 = 0
 248  *   Binary rule: p = first literal, d = 0, w2 = second literal, w1 = p
 249  *   every other : w1 = p, w2 = whatprovidesdata[d];
 250  *   Disabled rule: w1 = 0
 251  *
 252  *   always returns a rule for non-rpm rules
 253  */
 254
 255 Rule *
 256 solver_addrule(Solver *solv, Id p, Id d)
 257 {
 258   Pool *pool = solv->pool;
 259   Rule *r = 0;
 260   Id *dp = 0;
 261
 262   int n = 0;                           /* number of literals in rule - 1
 263                                           0 = direct assertion (single literal)
 264                                           1 = binary rule
 265                                           >1 =
 266                                         */
 267
 268   /* it often happenes that requires lead to adding the same rpm rule
 269    * multiple times, so we prune those duplicates right away to make
 270    * the work for unifyrules a bit easier */
 271
 272   if (solv->nrules                      /* we already have rules */
 273       && !solv->rpmrules_end)           /* but are not done with rpm rules */
 274     {
 275       r = solv->rules + solv->nrules - 1;   /* get the last added rule */
 276       if (r->p == p && r->d == d && d != 0)   /* identical and not user requested */
 277         return r;
 278     }
 279
 280     /*
 281      * compute number of literals (n) in rule
 282      */
 283
 284   if (d < 0)
 285     {
 286       /* always a binary rule */
 287       if (p == d)
 288         return 0;                      /* ignore self conflict */
 289       n = 1;
 290     }
 291   else if (d > 0)
 292     {
 293       for (dp = pool->whatprovidesdata + d; *dp; dp++, n++)
 294         if (*dp == -p)
 295           return 0;                     /* rule is self-fulfilling */
 296
 297       if (n == 1)   /* have single provider */
 298         d = dp[-1];                     /* take single literal */
 299     }
 300
 301   if (n == 1 && p > d && !solv->rpmrules_end)
 302     {
 303       /* smallest literal first so we can find dups */
 304       n = p; p = d; d = n;             /* p <-> d */
 305       n = 1;                           /* re-set n, was used as temp var */
 306     }
 307
 308   /*
 309    * check for duplicate
 310    */
 311
 312   /* check if the last added rule (r) is exactly the same as what we're looking for. */
 313   if (r && n == 1 && !r->d && r->p == p && r->w2 == d)
 314     return r;  /* binary rule */
 315
 316     /* have n-ary rule with same first literal, check other literals */
 317   if (r && n > 1 && r->d && r->p == p)
 318     {
 319       /* Rule where d is an offset in whatprovidesdata */
 320       Id *dp2;
 321       if (d == r->d)
 322         return r;
 323       dp2 = pool->whatprovidesdata + r->d;
 324       for (dp = pool->whatprovidesdata + d; *dp; dp++, dp2++)
 325         if (*dp != *dp2)
 326           break;
 327       if (*dp == *dp2)
 328         return r;
 329    }
 330
 331   /*
 332    * allocate new rule
 333    */
 334
 335   /* extend rule buffer */
 336   solv->rules = sat_extend(solv->rules, solv->nrules, 1, sizeof(Rule), RULES_BLOCK);
 337   r = solv->rules + solv->nrules++;    /* point to rule space */
 338
 339     /*
 340      * r = new rule
 341      */
 342
 343   r->p = p;
 344   if (n == 0)
 345     {
 346       /* direct assertion, no watch needed */
 347       r->d = 0;
 348       r->w1 = p;
 349       r->w2 = 0;
 350     }
 351   else if (n == 1)
 352     {
 353       /* binary rule */
 354       r->d = 0;
 355       r->w1 = p;
 356       r->w2 = d;
 357     }
 358   else
 359     {
 360       r->d = d;
 361       r->w1 = p;
 362       r->w2 = pool->whatprovidesdata[d];
 363     }
 364   r->n1 = 0;
 365   r->n2 = 0;
 366
 367   IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION)
 368     {
 369       POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "  Add rule: ");
 370       solver_printrule(solv, SAT_DEBUG_RULE_CREATION, r);
 371     }
 372
 373   return r;
 374 }
 375
 376 /*-------------------------------------------------------------------
 377  * disable rule
 378  */
 379
 380 static inline void
 381 disablerule(Solver *solv, Rule *r)
 382 {
 383   if (r->d >= 0)
 384     r->d = -r->d - 1;
 385 }
 386
 387 /*-------------------------------------------------------------------
 388  * enable rule
 389  */
 390
 391 static inline void
 392 enablerule(Solver *solv, Rule *r)
 393 {
 394   if (r->d < 0)
 395     r->d = -r->d - 1;
 396 }
 397
 398 /*
 399  *  special multiversion patch conflict handling:
 400  *  a patch conflict is also satisfied, if some other
 401  *  version with the same name/arch that doesn't conflict
 402  *  get's installed. The generated rule is thus:
 403  *  -patch|-cpack|opack1|opack2|...
 404  */
 405 static Id
 406 makemultiversionconflict(Solver *solv, Id n, Id con)
 407 {
 408   Pool *pool = solv->pool;
 409   Solvable *s, *sn;
 410   Queue q;
 411   Id p, pp, qbuf[64];
 412
 413   sn = pool->solvables + n;
 414   queue_init_buffer(&q, qbuf, sizeof(qbuf)/sizeof(*qbuf));
 415   queue_push(&q, -n);
 416   FOR_PROVIDES(p, pp, sn->name)
 417     {
 418       s = pool->solvables + p;
 419       if (s->name != sn->name || s->arch != sn->arch)
 420         continue;
 421       if (!MAPTST(&solv->noobsoletes, p))
 422         continue;
 423       if (pool_match_nevr(pool, pool->solvables + p, con))
 424         continue;
 425       /* here we have a multiversion solvable that doesn't conflict */
 426       /* thus we're not in conflict if it is installed */
 427       queue_push(&q, p);
 428     }
 429   if (q.count == 1)
 430     return -n;  /* no other package found, generate normal conflict */
 431   return pool_queuetowhatprovides(pool, &q);
 432 }
 433
 434 static inline void
 435 addrpmrule(Solver *solv, Id p, Id d, int type, Id dep)
 436 {
 437   if (!solv->ruleinfoq)
 438     solver_addrule(solv, p, d);
 439   else
 440     addrpmruleinfo(solv, p, d, type, dep);
 441 }
 442
 443 /*-------------------------------------------------------------------
 444  *
 445  * add (install) rules for solvable
 446  *
 447  * s: Solvable for which to add rules
 448  * m: m[s] = 1 for solvables which have rules, prevent rule duplication
 449  *
 450  * Algorithm: 'visit all nodes of a graph'. The graph nodes are
 451  *  solvables, the edges their dependencies.
 452  *  Starting from an installed solvable, this will create all rules
 453  *  representing the graph created by the solvables dependencies.
 454  *
 455  * for unfulfilled requirements, conflicts, obsoletes,....
 456  * add a negative assertion for solvables that are not installable
 457  *
 458  * It will also create rules for all solvables referenced by 's'
 459  *  i.e. descend to all providers of requirements of 's'
 460  *
 461  */
 462
 463 void
 464 solver_addrpmrulesforsolvable(Solver *solv, Solvable *s, Map *m)
 465 {
 466   Pool *pool = solv->pool;
 467   Repo *installed = solv->installed;
 468
 469   /* 'work' queue. keeps Ids of solvables we still have to work on.
 470      And buffer for it. */
 471   Queue workq;
 472   Id workqbuf[64];
 473
 474   int i;
 475     /* if to add rules for broken deps ('rpm -V' functionality)
 476      * 0 = yes, 1 = no
 477      */
 478   int dontfix;
 479     /* Id var and pointer for each dependency
 480      * (not used in parallel)
 481      */
 482   Id req, *reqp;
 483   Id con, *conp;
 484   Id obs, *obsp;
 485   Id rec, *recp;
 486   Id sug, *sugp;
 487   Id p, pp;             /* whatprovides loops */
 488   Id *dp;               /* ptr to 'whatprovides' */
 489   Id n;                 /* Id for current solvable 's' */
 490
 491   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforsolvable -----\n");
 492
 493   queue_init_buffer(&workq, workqbuf, sizeof(workqbuf)/sizeof(*workqbuf));
 494   queue_push(&workq, s - pool->solvables);      /* push solvable Id to work queue */
 495
 496   /* loop until there's no more work left */
 497   while (workq.count)
 498     {
 499       /*
 500        * n: Id of solvable
 501        * s: Pointer to solvable
 502        */
 503
 504       n = queue_shift(&workq);          /* 'pop' next solvable to work on from queue */
 505       if (m)
 506         {
 507           if (MAPTST(m, n))             /* continue if already visited */
 508             continue;
 509           MAPSET(m, n);                 /* mark as visited */
 510         }
 511
 512       s = pool->solvables + n;          /* s = Solvable in question */
 513
 514       dontfix = 0;
 515       if (installed                     /* Installed system available */
 516           && !solv->fixsystem           /* NOT repair errors in rpm dependency graph */
 517           && s->repo == installed)      /* solvable is installed? */
 518         {
 519           dontfix = 1;                  /* dont care about broken rpm deps */
 520         }
 521
 522       if (!dontfix
 523           && s->arch != ARCH_SRC
 524           && s->arch != ARCH_NOSRC
 525           && !pool_installable(pool, s))
 526         {
 527           POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "package %s [%d] is not installable\n", solvable2str(pool, s), (Id)(s - pool->solvables));
 528           addrpmrule(solv, -n, 0, SOLVER_RULE_RPM_NOT_INSTALLABLE, 0);
 529         }
 530
 531       /* yet another SUSE hack, sigh */
 532       if (pool->nscallback && !strncmp("product:", id2str(pool, s->name), 8))
 533         {
 534           Id buddy = pool->nscallback(pool, pool->nscallbackdata, NAMESPACE_PRODUCTBUDDY, n);
 535           if (buddy > 0 && buddy != SYSTEMSOLVABLE && buddy != n && buddy < pool->nsolvables)
 536             {
 537               addrpmrule(solv, n, -buddy, SOLVER_RULE_RPM_PACKAGE_REQUIRES, solvable_selfprovidedep(pool->solvables + n));
 538               addrpmrule(solv, buddy, -n, SOLVER_RULE_RPM_PACKAGE_REQUIRES, solvable_selfprovidedep(pool->solvables + buddy));
 539               if (m && !MAPTST(m, buddy))
 540                 queue_push(&workq, buddy);
 541             }
 542         }
 543
 544       /*-----------------------------------------
 545        * check requires of s
 546        */
 547
 548       if (s->requires)
 549         {
 550           reqp = s->repo->idarraydata + s->requires;
 551           while ((req = *reqp++) != 0)            /* go through all requires */
 552             {
 553               if (req == SOLVABLE_PREREQMARKER)   /* skip the marker */
 554                 continue;
 555
 556               /* find list of solvables providing 'req' */
 557               dp = pool_whatprovides_ptr(pool, req);
 558
 559               if (*dp == SYSTEMSOLVABLE)          /* always installed */
 560                 continue;
 561
 562               if (dontfix)
 563                 {
 564                   /* the strategy here is to not insist on dependencies
 565                    * that are already broken. so if we find one provider
 566                    * that was already installed, we know that the
 567                    * dependency was not broken before so we enforce it */
 568
 569                   /* check if any of the providers for 'req' is installed */
 570                   for (i = 0; (p = dp[i]) != 0; i++)
 571                     {
 572                       if (pool->solvables[p].repo == installed)
 573                         break;          /* provider was installed */
 574                     }
 575                   /* didn't find an installed provider: previously broken dependency */
 576                   if (!p)
 577                     {
 578                       POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "ignoring broken requires %s of installed package %s\n", dep2str(pool, req), solvable2str(pool, s));
 579                       continue;
 580                     }
 581                 }
 582
 583               if (!*dp)
 584                 {
 585                   /* nothing provides req! */
 586                   POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "package %s [%d] is not installable (%s)\n", solvable2str(pool, s), (Id)(s - pool->solvables), dep2str(pool, req));
 587                   addrpmrule(solv, -n, 0, SOLVER_RULE_RPM_NOTHING_PROVIDES_DEP, req);
 588                   continue;
 589                 }
 590
 591               IF_POOLDEBUG (SAT_DEBUG_RULE_CREATION)
 592                 {
 593                   POOL_DEBUG(SAT_DEBUG_RULE_CREATION,"  %s requires %s\n", solvable2str(pool, s), dep2str(pool, req));
 594                   for (i = 0; dp[i]; i++)
 595                     POOL_DEBUG(SAT_DEBUG_RULE_CREATION, "   provided by %s\n", solvid2str(pool, dp[i]));
 596                 }
 597
 598               /* add 'requires' dependency */
 599               /* rule: (-requestor|provider1|provider2|...|providerN) */
 600               addrpmrule(solv, -n, dp - pool->whatprovidesdata, SOLVER_RULE_RPM_PACKAGE_REQUIRES, req);
 601
 602               /* descend the dependency tree
 603                  push all non-visited providers on the work queue */
 604               if (m)
 605                 {
 606                   for (; *dp; dp++)
 607                     {
 608                       if (!MAPTST(m, *dp))
 609                         queue_push(&workq, *dp);
 610                     }
 611                 }
 612
 613             } /* while, requirements of n */
 614
 615         } /* if, requirements */
 616
 617       /* that's all we check for src packages */
 618       if (s->arch == ARCH_SRC || s->arch == ARCH_NOSRC)
 619         continue;
 620
 621       /*-----------------------------------------
 622        * check conflicts of s
 623        */
 624
 625       if (s->conflicts)
 626         {
 627           int ispatch = 0;
 628
 629           /* we treat conflicts in patches a bit differen:
 630            * - nevr matching
 631            * - multiversion handling
 632            * XXX: we should really handle this different, looking
 633            * at the name is a bad hack
 634            */
 635           if (!strncmp("patch:", id2str(pool, s->name), 6))
 636             ispatch = 1;
 637           conp = s->repo->idarraydata + s->conflicts;
 638           /* foreach conflicts of 's' */
 639           while ((con = *conp++) != 0)
 640             {
 641               /* foreach providers of a conflict of 's' */
 642               FOR_PROVIDES(p, pp, con)
 643                 {
 644                   if (ispatch && !pool_match_nevr(pool, pool->solvables + p, con))
 645                     continue;
 646                   /* dontfix: dont care about conflicts with already installed packs */
 647                   if (dontfix && pool->solvables[p].repo == installed)
 648                     continue;
 649                   /* p == n: self conflict */
 650                   if (p == n && !solv->allowselfconflicts)
 651                     {
 652                       if (ISRELDEP(con))
 653                         {
 654                           Reldep *rd = GETRELDEP(pool, con);
 655                           if (rd->flags == REL_NAMESPACE && rd->name == NAMESPACE_OTHERPROVIDERS)
 656                             continue;
 657                         }
 658                       p = 0;    /* make it a negative assertion, aka 'uninstallable' */
 659                     }
 660                   if (p && ispatch && solv->noobsoletes.size && MAPTST(&solv->noobsoletes, p) && ISRELDEP(con))
 661                     {
 662                       /* our patch conflicts with a noobsoletes (aka multiversion) package */
 663                       p = -makemultiversionconflict(solv, p, con);
 664                     }
 665                  /* rule: -n|-p: either solvable _or_ provider of conflict */
 666                   addrpmrule(solv, -n, -p, p ? SOLVER_RULE_RPM_PACKAGE_CONFLICT : SOLVER_RULE_RPM_SELF_CONFLICT, con);
 667                 }
 668             }
 669         }
 670
 671       /*-----------------------------------------
 672        * check obsoletes if not installed
 673        * (only installation will trigger the obsoletes in rpm)
 674        */
 675       if (!installed || pool->solvables[n].repo != installed)
 676         {                              /* not installed */
 677           int noobs = solv->noobsoletes.size && MAPTST(&solv->noobsoletes, n);
 678           if (s->obsoletes && !noobs)
 679             {
 680               obsp = s->repo->idarraydata + s->obsoletes;
 681               /* foreach obsoletes */
 682               while ((obs = *obsp++) != 0)
 683                 {
 684                   /* foreach provider of an obsoletes of 's' */
 685                   FOR_PROVIDES(p, pp, obs)
 686                     {
 687                       if (!solv->obsoleteusesprovides /* obsoletes are matched names, not provides */
 688                           && !pool_match_nevr(pool, pool->solvables + p, obs))
 689                         continue;
 690                       addrpmrule(solv, -n, -p, SOLVER_RULE_RPM_PACKAGE_OBSOLETES, obs);
 691                     }
 692                 }
 693             }
 694           FOR_PROVIDES(p, pp, s->name)
 695             {
 696               Solvable *ps = pool->solvables + p;
 697               /* we still obsolete packages with same nevra, like rpm does */
 698               /* (actually, rpm mixes those packages. yuck...) */
 699               if (noobs && (s->name != ps->name || s->evr != ps->evr || s->arch != ps->arch))
 700                 continue;
 701               if (!solv->implicitobsoleteusesprovides && s->name != ps->name)
 702                 continue;
 703               if (s->name == ps->name)
 704                 addrpmrule(solv, -n, -p, SOLVER_RULE_RPM_SAME_NAME, 0);
 705               else
 706                 addrpmrule(solv, -n, -p, SOLVER_RULE_RPM_IMPLICIT_OBSOLETES, s->name);
 707             }
 708         }
 709
 710       /*-----------------------------------------
 711        * add recommends to the work queue
 712        */
 713       if (s->recommends && m)
 714         {
 715           recp = s->repo->idarraydata + s->recommends;
 716           while ((rec = *recp++) != 0)
 717             {
 718               FOR_PROVIDES(p, pp, rec)
 719                 if (!MAPTST(m, p))
 720                   queue_push(&workq, p);
 721             }
 722         }
 723       if (s->suggests && m)
 724         {
 725           sugp = s->repo->idarraydata + s->suggests;
 726           while ((sug = *sugp++) != 0)
 727             {
 728               FOR_PROVIDES(p, pp, sug)
 729                 if (!MAPTST(m, p))
 730                   queue_push(&workq, p);
 731             }
 732         }
 733     }
 734   queue_free(&workq);
 735   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforsolvable end -----\n");
 736 }
 737
 738
 739 /*-------------------------------------------------------------------
 740  *
 741  * Add package rules for weak rules
 742  *
 743  * m: visited solvables
 744  */
 745
 746 void
 747 solver_addrpmrulesforweak(Solver *solv, Map *m)
 748 {
 749   Pool *pool = solv->pool;
 750   Solvable *s;
 751   Id sup, *supp;
 752   int i, n;
 753
 754   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforweak -----\n");
 755     /* foreach solvable in pool */
 756   for (i = n = 1; n < pool->nsolvables; i++, n++)
 757     {
 758       if (i == pool->nsolvables)                /* wrap i */
 759         i = 1;
 760       if (MAPTST(m, i))                         /* been there */
 761         continue;
 762
 763       s = pool->solvables + i;
 764       if (!pool_installable(pool, s))           /* only look at installable ones */
 765         continue;
 766
 767       sup = 0;
 768       if (s->supplements)
 769         {
 770           /* find possible supplements */
 771           supp = s->repo->idarraydata + s->supplements;
 772           while ((sup = *supp++) != ID_NULL)
 773             if (dep_possible(solv, sup, m))
 774               break;
 775         }
 776
 777       /* if nothing found, check for enhances */
 778       if (!sup && s->enhances)
 779         {
 780           supp = s->repo->idarraydata + s->enhances;
 781           while ((sup = *supp++) != ID_NULL)
 782             if (dep_possible(solv, sup, m))
 783               break;
 784         }
 785       /* if nothing found, goto next solvables */
 786       if (!sup)
 787         continue;
 788       solver_addrpmrulesforsolvable(solv, s, m);
 789       n = 0;                    /* check all solvables again */
 790     }
 791   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforweak end -----\n");
 792 }
 793
 794
 795 /*-------------------------------------------------------------------
 796  *
 797  * add package rules for possible updates
 798  *
 799  * s: solvable
 800  * m: map of already visited solvables
 801  * allow_all: 0 = dont allow downgrades, 1 = allow all candidates
 802  */
 803
 804 void
 805 solver_addrpmrulesforupdaters(Solver *solv, Solvable *s, Map *m, int allow_all)
 806 {
 807   Pool *pool = solv->pool;
 808   int i;
 809     /* queue and buffer for it */
 810   Queue qs;
 811   Id qsbuf[64];
 812
 813   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforupdaters -----\n");
 814
 815   queue_init_buffer(&qs, qsbuf, sizeof(qsbuf)/sizeof(*qsbuf));
 816     /* find update candidates for 's' */
 817   policy_findupdatepackages(solv, s, &qs, allow_all);
 818     /* add rule for 's' if not already done */
 819   if (!MAPTST(m, s - pool->solvables))
 820     solver_addrpmrulesforsolvable(solv, s, m);
 821     /* foreach update candidate, add rule if not already done */
 822   for (i = 0; i < qs.count; i++)
 823     if (!MAPTST(m, qs.elements[i]))
 824       solver_addrpmrulesforsolvable(solv, pool->solvables + qs.elements[i], m);
 825   queue_free(&qs);
 826
 827   POOL_DEBUG(SAT_DEBUG_SCHUBI, "----- addrpmrulesforupdaters -----\n");
 828 }
 829
 830
 831
 832 static void
 833 addrpmruleinfo(Solver *solv, Id p, Id d, int type, Id dep)
 834 {
 835   Pool *pool = solv->pool;
 836   Rule *r;
 837   Id w2, op, od, ow2;
 838
 839   /* check if this creates the rule we're searching for */
 840   r = solv->rules + solv->ruleinfoq->elements[0];
 841   op = r->p;
 842   od = r->d < 0 ? -r->d - 1 : r->d;
 843   ow2 = 0;
 844
 845   /* normalize */
 846   w2 = d > 0 ? 0 : d;
 847   if (p < 0 && d > 0 && (!pool->whatprovidesdata[d] || !pool->whatprovidesdata[d + 1]))
 848     {
 849       w2 = pool->whatprovidesdata[d];
 850       d = 0;
 851
 852     }
 853   if (p > 0 && d < 0)           /* this hack is used for buddy deps */
 854     {
 855       w2 = p;
 856       p = d;
 857     }
 858
 859   if (d > 0)
 860     {
 861       if (p != op && !od)
 862         return;
 863       if (d != od)
 864         {
 865           Id *dp = pool->whatprovidesdata + d;
 866           Id *odp = pool->whatprovidesdata + od;
 867           while (*dp)
 868             if (*dp++ != *odp++)
 869               return;
 870           if (*odp)
 871             return;
 872         }
 873       w2 = 0;
 874       /* handle multiversion conflict rules */
 875       if (p < 0 && pool->whatprovidesdata[d] < 0)
 876         {
 877           w2 = pool->whatprovidesdata[d];
 878           /* XXX: free memory */
 879         }
 880     }
 881   else
 882     {
 883       if (od)
 884         return;
 885       ow2 = r->w2;
 886       if (p > w2)
 887         {
 888           if (w2 != op || p != ow2)
 889             return;
 890         }
 891       else
 892         {
 893           if (p != op || w2 != ow2)
 894             return;
 895         }
 896     }
 897   /* yep, rule matches. record info */
 898   queue_push(solv->ruleinfoq, type);
 899   if (type == SOLVER_RULE_RPM_SAME_NAME)
 900     {
 901       /* we normalize same name order */
 902       queue_push(solv->ruleinfoq, op < 0 ? -op : 0);
 903       queue_push(solv->ruleinfoq, ow2 < 0 ? -ow2 : 0);
 904     }
 905   else
 906     {
 907       queue_push(solv->ruleinfoq, p < 0 ? -p : 0);
 908       queue_push(solv->ruleinfoq, w2 < 0 ? -w2 : 0);
 909     }
 910   queue_push(solv->ruleinfoq, dep);
 911 }
 912
 913 static int
 914 solver_allruleinfos_cmp(const void *ap, const void *bp, void *dp)
 915 {
 916   const Id *a = ap, *b = bp;
 917   int r;
 918
 919   r = a[0] - b[0];
 920   if (r)
 921     return r;
 922   r = a[1] - b[1];
 923   if (r)
 924     return r;
 925   r = a[2] - b[2];
 926   if (r)
 927     return r;
 928   r = a[3] - b[3];
 929   if (r)
 930     return r;
 931   return 0;
 932 }
 933
 934 int
 935 solver_allruleinfos(Solver *solv, Id rid, Queue *rq)
 936 {
 937   Pool *pool = solv->pool;
 938   Rule *r = solv->rules + rid;
 939   int i, j;
 940
 941   queue_empty(rq);
 942   if (rid <= 0 || rid >= solv->rpmrules_end)
 943     {
 944       Id type, from, to, dep;
 945       type = solver_ruleinfo(solv, rid, &from, &to, &dep);
 946       queue_push(rq, type);
 947       queue_push(rq, from);
 948       queue_push(rq, to);
 949       queue_push(rq, dep);
 950       return 1;
 951     }
 952   if (r->p >= 0)
 953     return 0;
 954   queue_push(rq, rid);
 955   solv->ruleinfoq = rq;
 956   solver_addrpmrulesforsolvable(solv, pool->solvables - r->p, 0);
 957   /* also try reverse direction for conflicts */
 958   if ((r->d == 0 || r->d == -1) && r->w2 < 0)
 959     solver_addrpmrulesforsolvable(solv, pool->solvables - r->w2, 0);
 960   solv->ruleinfoq = 0;
 961   queue_shift(rq);
 962   /* now sort & unify em */
 963   if (!rq->count)
 964     return 0;
 965   sat_sort(rq->elements, rq->count / 4, 4 * sizeof(Id), solver_allruleinfos_cmp, 0);
 966   /* throw out identical entries */
 967   for (i = j = 0; i < rq->count; i += 4)
 968     {
 969       if (j)
 970         {
 971           if (rq->elements[i] == rq->elements[j - 4] &&
 972               rq->elements[i + 1] == rq->elements[j - 3] &&
 973               rq->elements[i + 2] == rq->elements[j - 2] &&
 974               rq->elements[i + 3] == rq->elements[j - 1])
 975             continue;
 976         }
 977       rq->elements[j++] = rq->elements[i];
 978       rq->elements[j++] = rq->elements[i + 1];
 979       rq->elements[j++] = rq->elements[i + 2];
 980       rq->elements[j++] = rq->elements[i + 3];
 981     }
 982   rq->count = j;
 983   return j / 4;
 984 }
 985
 986 SolverRuleinfo
 987 solver_ruleinfo(Solver *solv, Id rid, Id *fromp, Id *top, Id *depp)
 988 {
 989   Pool *pool = solv->pool;
 990   Rule *r = solv->rules + rid;
 991   SolverRuleinfo type = SOLVER_RULE_UNKNOWN;
 992
 993   if (fromp)
 994     *fromp = 0;
 995   if (top)
 996     *top = 0;
 997   if (depp)
 998     *depp = 0;
 999   if (rid > 0 && rid < solv->rpmrules_end)
1000     {
1001       Queue rq;
1002       int i;
1003
1004       if (r->p >= 0)
1005         return SOLVER_RULE_RPM;
1006       if (fromp)
1007         *fromp = -r->p;
1008       queue_init(&rq);
1009       queue_push(&rq, rid);
1010       solv->ruleinfoq = &rq;
1011       solver_addrpmrulesforsolvable(solv, pool->solvables - r->p, 0);
1012       /* also try reverse direction for conflicts */
1013       if ((r->d == 0 || r->d == -1) && r->w2 < 0)
1014         solver_addrpmrulesforsolvable(solv, pool->solvables - r->w2, 0);
1015       solv->ruleinfoq = 0;
1016       type = SOLVER_RULE_RPM;
1017       for (i = 1; i < rq.count; i += 4)
1018         {
1019           Id qt, qo, qp, qd;
1020           qt = rq.elements[i];
1021           qp = rq.elements[i + 1];
1022           qo = rq.elements[i + 2];
1023           qd = rq.elements[i + 3];
1024           if (type == SOLVER_RULE_RPM || type > qt)
1025             {
1026               type = qt;
1027               if (fromp)
1028                 *fromp = qp;
1029               if (top)
1030                 *top = qo;
1031               if (depp)
1032                 *depp = qd;
1033             }
1034         }
1035       queue_free(&rq);
1036       return type;
1037     }
1038   if (rid >= solv->jobrules && rid < solv->jobrules_end)
1039     {
1040       Id jidx = solv->ruletojob.elements[rid - solv->jobrules];
1041       if (fromp)
1042         *fromp = jidx;
1043       if (top)
1044         *top = solv->job.elements[jidx];
1045       if (depp)
1046         *depp = solv->job.elements[jidx + 1];
1047       if ((r->d == 0 || r->d == -1) && r->w2 == 0 && r->p == -SYSTEMSOLVABLE && (solv->job.elements[jidx] & SOLVER_SELECTMASK) != SOLVER_SOLVABLE_ONE_OF)
1048         return SOLVER_RULE_JOB_NOTHING_PROVIDES_DEP;
1049       return SOLVER_RULE_JOB;
1050     }
1051   if (rid >= solv->updaterules && rid < solv->updaterules_end)
1052     {
1053       if (fromp)
1054         *fromp = solv->installed->start + (rid - solv->updaterules);
1055       return SOLVER_RULE_UPDATE;
1056     }
1057   if (rid >= solv->featurerules && rid < solv->featurerules_end)
1058     {
1059       if (fromp)
1060         *fromp = solv->installed->start + (rid - solv->featurerules);
1061       return SOLVER_RULE_FEATURE;
1062     }
1063   if (rid >= solv->duprules && rid < solv->duprules_end)
1064     {
1065       if (fromp)
1066         *fromp = -r->p;
1067       if (depp)
1068         *depp = pool->solvables[-r->p].name;
1069       return SOLVER_RULE_DISTUPGRADE;
1070     }
1071   if (rid >= solv->infarchrules && rid < solv->infarchrules_end)
1072     {
1073       if (fromp)
1074         *fromp = -r->p;
1075       if (depp)
1076         *depp = pool->solvables[-r->p].name;
1077       return SOLVER_RULE_INFARCH;
1078     }
1079   if (rid >= solv->learntrules)
1080     {
1081       return SOLVER_RULE_LEARNT;
1082     }
1083   return SOLVER_RULE_UNKNOWN;
1084 }
1085
1086 /* EOF */