lib/depends.c

   1 /** \ingroup rpmts
   2  * \file lib/depends.c
   3  */
   4
   5 #include "system.h"
   6
   7 #include <rpmcli.h>             /* XXX rpmcliPackagesTotal */
   8
   9 #include <rpmmacro.h>           /* XXX rpmExpand("%{_dependency_whiteout}" */
  10
  11 #include "rpmdb.h"              /* XXX response cache needs dbiOpen et al. */
  12
  13 #include "rpmds.h"
  14 #include "rpmfi.h"
  15
  16 #define _RPMTE_INTERNAL
  17 #include "rpmte.h"
  18
  19 #define _RPMTS_INTERNAL
  20 #include "rpmts.h"
  21
  22 #include "debug.h"
  23
  24 /*@access tsortInfo @*/
  25 /*@access rpmts @*/
  26
  27 /*@access dbiIndex @*/          /* XXX for dbi->dbi_txnid */
  28
  29 /*@access alKey @*/     /* XXX for reordering and RPMAL_NOMATCH assign */
  30
  31 /**
  32  */
  33 typedef /*@abstract@*/ struct orderListIndex_s *        orderListIndex;
  34 /*@access orderListIndex@*/
  35
  36 /**
  37  */
  38 struct orderListIndex_s {
  39 /*@dependent@*/
  40     alKey pkgKey;
  41     int orIndex;
  42 };
  43
  44 /*@unchecked@*/
  45 int _cacheDependsRC = 1;
  46
  47 /*@observer@*/ /*@unchecked@*/
  48 const char *rpmNAME = PACKAGE;
  49
  50 /*@observer@*/ /*@unchecked@*/
  51 const char *rpmEVR = VERSION;
  52
  53 /*@unchecked@*/
  54 int rpmFLAGS = RPMSENSE_EQUAL;
  55
  56 /**
  57  * Compare removed package instances (qsort/bsearch).
  58  * @param a             1st instance address
  59  * @param b             2nd instance address
  60  * @return              result of comparison
  61  */
  62 static int intcmp(const void * a, const void * b)
  63         /*@requires maxRead(a) == 0 /\ maxRead(b) == 0 @*/
  64 {
  65     const int * aptr = a;
  66     const int * bptr = b;
  67     int rc = (*aptr - *bptr);
  68     return rc;
  69 }
  70
  71 /**
  72  * Add removed package instance to ordered transaction set.
  73  * @param ts            transaction set
  74  * @param h             header
  75  * @param dboffset      rpm database instance
  76  * @param depends       installed package of pair (or RPMAL_NOMATCH on erase)
  77  * @return              0 on success
  78  */
  79 static int removePackage(rpmts ts, Header h, int dboffset,
  80                 /*@exposed@*/ /*@dependent@*/ /*@null@*/ alKey depends)
  81         /*@globals fileSystem @*/
  82         /*@modifies ts, h, fileSystem @*/
  83 {
  84     rpmte p;
  85
  86     /* Filter out duplicate erasures. */
  87     if (ts->numRemovedPackages > 0 && ts->removedPackages != NULL) {
  88 /*@-boundswrite@*/
  89         if (bsearch(&dboffset, ts->removedPackages, ts->numRemovedPackages,
  90                         sizeof(*ts->removedPackages), intcmp) != NULL)
  91             return 0;
  92 /*@=boundswrite@*/
  93     }
  94
  95     if (ts->numRemovedPackages == ts->allocedRemovedPackages) {
  96         ts->allocedRemovedPackages += ts->delta;
  97         ts->removedPackages = xrealloc(ts->removedPackages,
  98                 sizeof(ts->removedPackages) * ts->allocedRemovedPackages);
  99     }
 100
 101     if (ts->removedPackages != NULL) {  /* XXX can't happen. */
 102 /*@-boundswrite@*/
 103         ts->removedPackages[ts->numRemovedPackages] = dboffset;
 104         ts->numRemovedPackages++;
 105 /*@=boundswrite@*/
 106         if (ts->numRemovedPackages > 1)
 107             qsort(ts->removedPackages, ts->numRemovedPackages,
 108                         sizeof(*ts->removedPackages), intcmp);
 109     }
 110
 111     if (ts->orderCount >= ts->orderAlloced) {
 112         ts->orderAlloced += (ts->orderCount - ts->orderAlloced) + ts->delta;
 113 /*@-type +voidabstract @*/
 114         ts->order = xrealloc(ts->order, sizeof(*ts->order) * ts->orderAlloced);
 115 /*@=type =voidabstract @*/
 116     }
 117
 118     p = rpmteNew(ts, h, TR_REMOVED, NULL, NULL, dboffset, depends);
 119 /*@-boundswrite@*/
 120     ts->order[ts->orderCount] = p;
 121     ts->orderCount++;
 122 /*@=boundswrite@*/
 123
 124     return 0;
 125 }
 126
 127 int rpmtsAddInstallElement(rpmts ts, Header h,
 128                         fnpyKey key, int upgrade, rpmRelocation * relocs)
 129 {
 130     uint_32 tscolor = rpmtsColor(ts);
 131     uint_32 dscolor;
 132     uint_32 hcolor;
 133     rpmdbMatchIterator mi;
 134     Header oh;
 135     uint_32 ohcolor;
 136     int isSource;
 137     int duplicate = 0;
 138     rpmtsi pi; rpmte p;
 139     HGE_t hge = (HGE_t)headerGetEntryMinMemory;
 140     const char * arch;
 141     const char * os;
 142     rpmds add;
 143     rpmds obsoletes;
 144     alKey pkgKey;       /* addedPackages key */
 145     int xx;
 146     int ec = 0;
 147     int rc;
 148     int oc;
 149
 150     /*
 151      * Check for previously added versions with the same name and arch/os.
 152      * FIXME: only catches previously added, older packages.
 153      */
 154     add = rpmdsThis(h, RPMTAG_REQUIRENAME, (RPMSENSE_EQUAL|RPMSENSE_LESS));
 155     arch = NULL;
 156     xx = hge(h, RPMTAG_ARCH, NULL, (void **)&arch, NULL);
 157     os = NULL;
 158     xx = hge(h, RPMTAG_OS, NULL, (void **)&os, NULL);
 159     hcolor = hGetColor(h);
 160
 161     pkgKey = RPMAL_NOMATCH;
 162     for (pi = rpmtsiInit(ts), oc = 0; (p = rpmtsiNext(pi, 0)) != NULL; oc++) {
 163         const char * parch;
 164         const char * pos;
 165         rpmds this;
 166
 167         /* XXX Only added packages need be checked for dupes. */
 168         if (rpmteType(p) == TR_REMOVED)
 169             continue;
 170
 171         if (tscolor) {
 172             if (arch == NULL || (parch = rpmteA(p)) == NULL)
 173                 continue;
 174             if (os == NULL || (pos = rpmteO(p)) == NULL)
 175                 continue;
 176             if (strcmp(arch, parch) || strcmp(os, pos))
 177                 continue;
 178         }
 179
 180         if ((this = rpmteDS(p, RPMTAG_NAME)) == NULL)
 181             continue;   /* XXX can't happen */
 182
 183         rc = rpmdsCompare(add, this);
 184         if (rc != 0) {
 185             const char * pkgNEVR = rpmdsDNEVR(this);
 186             const char * addNEVR = rpmdsDNEVR(add);
 187             rpmMessage(RPMMESS_WARNING,
 188                 _("package %s was already added, replacing with %s\n"),
 189                 (pkgNEVR ? pkgNEVR + 2 : "?pkgNEVR?"),
 190                 (addNEVR ? addNEVR + 2 : "?addNEVR?"));
 191             duplicate = 1;
 192             pkgKey = rpmteAddedKey(p);
 193             break;
 194         }
 195     }
 196     pi = rpmtsiFree(pi);
 197     add = rpmdsFree(add);
 198
 199     isSource = headerIsEntry(h, RPMTAG_SOURCEPACKAGE);
 200
 201     if (oc >= ts->orderAlloced) {
 202         ts->orderAlloced += (oc - ts->orderAlloced) + ts->delta;
 203 /*@-type +voidabstract @*/
 204         ts->order = xrealloc(ts->order, ts->orderAlloced * sizeof(*ts->order));
 205 /*@=type =voidabstract @*/
 206     }
 207
 208     p = rpmteNew(ts, h, TR_ADDED, key, relocs, -1, pkgKey);
 209
 210     if (duplicate && oc < ts->orderCount) {
 211 /*@-type -unqualifiedtrans@*/
 212 /*@-boundswrite@*/
 213         ts->order[oc] = rpmteFree(ts->order[oc]);
 214 /*@=boundswrite@*/
 215 /*@=type =unqualifiedtrans@*/
 216     }
 217
 218 /*@-boundswrite@*/
 219     ts->order[oc] = p;
 220 /*@=boundswrite@*/
 221     if (!duplicate) {
 222         ts->orderCount++;
 223         rpmcliPackagesTotal++;
 224     }
 225
 226     pkgKey = rpmalAdd(&ts->addedPackages, pkgKey, rpmteKey(p),
 227                         rpmteDS(p, RPMTAG_PROVIDENAME),
 228                         rpmteFI(p, RPMTAG_BASENAMES), tscolor);
 229     if (pkgKey == RPMAL_NOMATCH) {
 230 /*@-boundswrite@*/
 231         ts->order[oc] = rpmteFree(ts->order[oc]);
 232 /*@=boundswrite@*/
 233         ec = 1;
 234         goto exit;
 235     }
 236     (void) rpmteSetAddedKey(p, pkgKey);
 237
 238     if (!duplicate) {
 239         ts->numAddedPackages++;
 240     }
 241
 242     if (!upgrade)
 243         goto exit;
 244
 245     /* XXX binary rpms always have RPMTAG_SOURCERPM, source rpms do not */
 246     if (isSource)
 247         goto exit;
 248
 249     /* Do lazy (readonly?) open of rpm database. */
 250     if (rpmtsGetRdb(ts) == NULL && ts->dbmode != -1) {
 251         if ((ec = rpmtsOpenDB(ts, ts->dbmode)) != 0)
 252             goto exit;
 253     }
 254
 255     /* On upgrade, erase older packages of same color (if any). */
 256
 257     mi = rpmtsInitIterator(ts, RPMTAG_PROVIDENAME, rpmteN(p), 0);
 258     while((oh = rpmdbNextIterator(mi)) != NULL) {
 259
 260         /* Ignore colored packages not in our rainbow. */
 261         ohcolor = hGetColor(oh);
 262         if (tscolor && hcolor && ohcolor && !(hcolor & ohcolor))
 263             continue;
 264
 265         /* Skip packages that contain identical NEVR. */
 266         if (rpmVersionCompare(h, oh) == 0)
 267             continue;
 268
 269         xx = removePackage(ts, oh, rpmdbGetIteratorOffset(mi), pkgKey);
 270     }
 271     mi = rpmdbFreeIterator(mi);
 272
 273     obsoletes = rpmdsLink(rpmteDS(p, RPMTAG_OBSOLETENAME), "Obsoletes");
 274     obsoletes = rpmdsInit(obsoletes);
 275     if (obsoletes != NULL)
 276     while (rpmdsNext(obsoletes) >= 0) {
 277         const char * Name;
 278
 279         if ((Name = rpmdsN(obsoletes)) == NULL)
 280             continue;   /* XXX can't happen */
 281
 282         /* Ignore colored obsoletes not in our rainbow. */
 283         dscolor = rpmdsColor(obsoletes);
 284         if (tscolor && dscolor && !(tscolor & dscolor))
 285             continue;
 286
 287         /* XXX avoid self-obsoleting packages. */
 288         if (!strcmp(rpmteN(p), Name))
 289             continue;
 290
 291         mi = rpmtsInitIterator(ts, RPMTAG_PROVIDENAME, Name, 0);
 292
 293         xx = rpmdbPruneIterator(mi,
 294             ts->removedPackages, ts->numRemovedPackages, 1);
 295
 296         while((oh = rpmdbNextIterator(mi)) != NULL) {
 297             /* Ignore colored packages not in our rainbow. */
 298             ohcolor = hGetColor(oh);
 299             if (tscolor && hcolor && ohcolor && !(hcolor & ohcolor))
 300                 /*@innercontinue@*/ continue;
 301
 302             /*
 303              * Rpm prior to 3.0.3 does not have versioned obsoletes.
 304              * If no obsoletes version info is available, match all names.
 305              */
 306             if (rpmdsEVR(obsoletes) == NULL
 307              || rpmdsAnyMatchesDep(oh, obsoletes, _rpmds_nopromote))
 308                 xx = removePackage(ts, oh, rpmdbGetIteratorOffset(mi), pkgKey);
 309         }
 310         mi = rpmdbFreeIterator(mi);
 311     }
 312     obsoletes = rpmdsFree(obsoletes);
 313
 314     ec = 0;
 315
 316 exit:
 317     pi = rpmtsiFree(pi);
 318     return ec;
 319 }
 320
 321 int rpmtsAddEraseElement(rpmts ts, Header h, int dboffset)
 322 {
 323     return removePackage(ts, h, dboffset, RPMAL_NOMATCH);
 324 }
 325
 326 /**
 327  * Check dep for an unsatisfied dependency.
 328  * @param ts            transaction set
 329  * @param dep           dependency
 330  * @param adding        dependency is from added package set?
 331  * @return              0 if satisfied, 1 if not satisfied, 2 if error
 332  */
 333 static int unsatisfiedDepend(rpmts ts, rpmds dep, int adding)
 334         /*@globals _cacheDependsRC, rpmGlobalMacroContext,
 335                 fileSystem, internalState @*/
 336         /*@modifies ts, _cacheDependsRC, rpmGlobalMacroContext,
 337                 fileSystem, internalState @*/
 338 {
 339     DBT * key = alloca(sizeof(*key));
 340     DBT * data = alloca(sizeof(*data));
 341     rpmdbMatchIterator mi;
 342     const char * Name;
 343     Header h;
 344     int _cacheThisRC = 1;
 345     int rc;
 346     int xx;
 347     int retrying = 0;
 348
 349     if ((Name = rpmdsN(dep)) == NULL)
 350         return 0;       /* XXX can't happen */
 351
 352     /*
 353      * Check if dbiOpen/dbiPut failed (e.g. permissions), we can't cache.
 354      */
 355     if (_cacheDependsRC) {
 356         dbiIndex dbi;
 357         dbi = dbiOpen(rpmtsGetRdb(ts), RPMDBI_DEPENDS, 0);
 358         if (dbi == NULL)
 359             _cacheDependsRC = 0;
 360         else {
 361             const char * DNEVR;
 362
 363             rc = -1;
 364 /*@-branchstate@*/
 365             if ((DNEVR = rpmdsDNEVR(dep)) != NULL) {
 366                 DBC * dbcursor = NULL;
 367                 void * datap = NULL;
 368                 size_t datalen = 0;
 369                 size_t DNEVRlen = strlen(DNEVR);
 370
 371                 xx = dbiCopen(dbi, dbi->dbi_txnid, &dbcursor, 0);
 372
 373                 memset(key, 0, sizeof(*key));
 374 /*@i@*/         key->data = (void *) DNEVR;
 375                 key->size = DNEVRlen;
 376                 memset(data, 0, sizeof(*data));
 377                 data->data = datap;
 378                 data->size = datalen;
 379                 xx = dbiGet(dbi, dbcursor, key, data, DB_SET);
 380                 DNEVR = key->data;
 381                 DNEVRlen = key->size;
 382                 datap = data->data;
 383                 datalen = data->size;
 384
 385 /*@-boundswrite@*/
 386                 if (xx == 0 && datap && datalen == 4)
 387                     memcpy(&rc, datap, datalen);
 388 /*@=boundswrite@*/
 389                 xx = dbiCclose(dbi, dbcursor, 0);
 390             }
 391 /*@=branchstate@*/
 392
 393             if (rc >= 0) {
 394                 rpmdsNotify(dep, _("(cached)"), rc);
 395                 return rc;
 396             }
 397         }
 398     }
 399
 400 retry:
 401     rc = 0;     /* assume dependency is satisfied */
 402
 403 #if defined(DYING) || defined(__LCLINT__)
 404   { static /*@observer@*/ const char noProvidesString[] = "nada";
 405     static /*@observer@*/ const char * rcProvidesString = noProvidesString;
 406     int_32 Flags = rpmdsFlags(dep);
 407     const char * start;
 408     int i;
 409
 410     if (rcProvidesString == noProvidesString)
 411         rcProvidesString = rpmGetVar(RPMVAR_PROVIDES);
 412
 413     if (rcProvidesString != NULL && !(Flags & RPMSENSE_SENSEMASK)) {
 414
 415         i = strlen(Name);
 416         /*@-observertrans -mayaliasunique@*/
 417         while ((start = strstr(rcProvidesString, Name))) {
 418         /*@=observertrans =mayaliasunique@*/
 419 /*@-boundsread@*/
 420             if (xisspace(start[i]) || start[i] == '\0' || start[i] == ',') {
 421                 rpmdsNotify(dep, _("(rpmrc provides)"), rc);
 422                 goto exit;
 423             }
 424 /*@=boundsread@*/
 425             rcProvidesString = start + 1;
 426         }
 427     }
 428   }
 429 #endif
 430
 431     /*
 432      * New features in rpm packaging implicitly add versioned dependencies
 433      * on rpmlib provides. The dependencies look like "rpmlib(YaddaYadda)".
 434      * Check those dependencies now.
 435      */
 436     if (!strncmp(Name, "rpmlib(", sizeof("rpmlib(")-1)) {
 437         if (rpmCheckRpmlibProvides(dep)) {
 438             rpmdsNotify(dep, _("(rpmlib provides)"), rc);
 439             goto exit;
 440         }
 441         goto unsatisfied;
 442     }
 443
 444     /* Search added packages for the dependency. */
 445     if (rpmalSatisfiesDepend(ts->addedPackages, dep, NULL) != NULL) {
 446         /*
 447          * XXX Ick, context sensitive answers from dependency cache.
 448          * XXX Always resolve added dependencies within context to disambiguate.
 449          */
 450         if (_rpmds_nopromote)
 451             _cacheThisRC = 0;
 452         goto exit;
 453     }
 454
 455     /* XXX only the installer does not have the database open here. */
 456     if (rpmtsGetRdb(ts) != NULL) {
 457 /*@-boundsread@*/
 458         if (Name[0] == '/') {
 459             /* depFlags better be 0! */
 460
 461             mi = rpmtsInitIterator(ts, RPMTAG_BASENAMES, Name, 0);
 462
 463             (void) rpmdbPruneIterator(mi,
 464                         ts->removedPackages, ts->numRemovedPackages, 1);
 465
 466             while ((h = rpmdbNextIterator(mi)) != NULL) {
 467                 rpmdsNotify(dep, _("(db files)"), rc);
 468                 mi = rpmdbFreeIterator(mi);
 469                 goto exit;
 470             }
 471             mi = rpmdbFreeIterator(mi);
 472         }
 473 /*@=boundsread@*/
 474
 475         mi = rpmtsInitIterator(ts, RPMTAG_PROVIDENAME, Name, 0);
 476         (void) rpmdbPruneIterator(mi,
 477                         ts->removedPackages, ts->numRemovedPackages, 1);
 478         while ((h = rpmdbNextIterator(mi)) != NULL) {
 479             if (rpmdsAnyMatchesDep(h, dep, _rpmds_nopromote)) {
 480                 rpmdsNotify(dep, _("(db provides)"), rc);
 481                 mi = rpmdbFreeIterator(mi);
 482                 goto exit;
 483             }
 484         }
 485         mi = rpmdbFreeIterator(mi);
 486
 487 #if defined(DYING) || defined(__LCLINT__)
 488         mi = rpmtsInitIterator(ts, RPMTAG_NAME, Name, 0);
 489         (void) rpmdbPruneIterator(mi,
 490                         ts->removedPackages, ts->numRemovedPackages, 1);
 491         while ((h = rpmdbNextIterator(mi)) != NULL) {
 492             if (rpmdsAnyMatchesDep(h, dep, _rpmds_nopromote)) {
 493                 rpmdsNotify(dep, _("(db package)"), rc);
 494                 mi = rpmdbFreeIterator(mi);
 495                 goto exit;
 496             }
 497         }
 498         mi = rpmdbFreeIterator(mi);
 499 #endif
 500
 501     }
 502
 503     /*
 504      * Search for an unsatisfied dependency.
 505      */
 506 /*@-boundsread@*/
 507     if (adding && !retrying && !(rpmtsFlags(ts) & RPMTRANS_FLAG_NOSUGGEST)) {
 508         if (ts->solve != NULL) {
 509             xx = (*ts->solve) (ts, dep, ts->solveData);
 510             if (xx == 0)
 511                 goto exit;
 512             if (xx == -1) {
 513                 retrying = 1;
 514                 rpmalMakeIndex(ts->addedPackages);
 515                 goto retry;
 516             }
 517         }
 518     }
 519 /*@=boundsread@*/
 520
 521 unsatisfied:
 522     rc = 1;     /* dependency is unsatisfied */
 523     rpmdsNotify(dep, NULL, rc);
 524
 525 exit:
 526     /*
 527      * If dbiOpen/dbiPut fails (e.g. permissions), we can't cache.
 528      */
 529     if (_cacheDependsRC && _cacheThisRC) {
 530         dbiIndex dbi;
 531         dbi = dbiOpen(rpmtsGetRdb(ts), RPMDBI_DEPENDS, 0);
 532         if (dbi == NULL) {
 533             _cacheDependsRC = 0;
 534         } else {
 535             const char * DNEVR;
 536             xx = 0;
 537             /*@-branchstate@*/
 538             if ((DNEVR = rpmdsDNEVR(dep)) != NULL) {
 539                 DBC * dbcursor = NULL;
 540                 size_t DNEVRlen = strlen(DNEVR);
 541
 542                 xx = dbiCopen(dbi, dbi->dbi_txnid, &dbcursor, DB_WRITECURSOR);
 543
 544                 memset(key, 0, sizeof(*key));
 545 /*@i@*/         key->data = (void *) DNEVR;
 546                 key->size = DNEVRlen;
 547                 memset(data, 0, sizeof(*data));
 548                 data->data = &rc;
 549                 data->size = sizeof(rc);
 550
 551                 /*@-compmempass@*/
 552                 xx = dbiPut(dbi, dbcursor, key, data, 0);
 553                 /*@=compmempass@*/
 554                 xx = dbiCclose(dbi, dbcursor, DB_WRITECURSOR);
 555             }
 556             /*@=branchstate@*/
 557             if (xx)
 558                 _cacheDependsRC = 0;
 559         }
 560     }
 561     return rc;
 562 }
 563
 564 /**
 565  * Check added requires/conflicts against against installed+added packages.
 566  * @param ts            transaction set
 567  * @param pkgNEVR       package name-version-release
 568  * @param requires      Requires: dependencies (or NULL)
 569  * @param conflicts     Conflicts: dependencies (or NULL)
 570  * @param depName       dependency name to filter (or NULL)
 571  * @param tscolor       color bits for transaction set (0 disables)
 572  * @param adding        dependency is from added package set?
 573  * @return              0 no problems found
 574  */
 575 static int checkPackageDeps(rpmts ts, const char * pkgNEVR,
 576                 /*@null@*/ rpmds requires, /*@null@*/ rpmds conflicts,
 577                 /*@null@*/ const char * depName, uint_32 tscolor, int adding)
 578         /*@globals rpmGlobalMacroContext,
 579                 fileSystem, internalState @*/
 580         /*@modifies ts, requires, conflicts, rpmGlobalMacroContext,
 581                 fileSystem, internalState */
 582 {
 583     uint_32 dscolor;
 584     const char * Name;
 585     int rc;
 586     int ourrc = 0;
 587
 588     requires = rpmdsInit(requires);
 589     if (requires != NULL)
 590     while (!ourrc && rpmdsNext(requires) >= 0) {
 591
 592         if ((Name = rpmdsN(requires)) == NULL)
 593             continue;   /* XXX can't happen */
 594
 595         /* Filter out requires that came along for the ride. */
 596         if (depName != NULL && strcmp(depName, Name))
 597             continue;
 598
 599         /* Ignore colored requires not in our rainbow. */
 600         dscolor = rpmdsColor(requires);
 601         if (tscolor && dscolor && !(tscolor & dscolor))
 602             continue;
 603
 604         rc = unsatisfiedDepend(ts, requires, adding);
 605
 606         switch (rc) {
 607         case 0:         /* requirements are satisfied. */
 608             /*@switchbreak@*/ break;
 609         case 1:         /* requirements are not satisfied. */
 610         {   fnpyKey * suggestedKeys = NULL;
 611
 612             /*@-branchstate@*/
 613             if (ts->availablePackages != NULL) {
 614                 suggestedKeys = rpmalAllSatisfiesDepend(ts->availablePackages,
 615                                 requires, NULL);
 616             }
 617             /*@=branchstate@*/
 618
 619             rpmdsProblem(ts->probs, pkgNEVR, requires, suggestedKeys, adding);
 620
 621         }
 622             /*@switchbreak@*/ break;
 623         case 2:         /* something went wrong! */
 624         default:
 625             ourrc = 1;
 626             /*@switchbreak@*/ break;
 627         }
 628     }
 629
 630     conflicts = rpmdsInit(conflicts);
 631     if (conflicts != NULL)
 632     while (!ourrc && rpmdsNext(conflicts) >= 0) {
 633
 634         if ((Name = rpmdsN(conflicts)) == NULL)
 635             continue;   /* XXX can't happen */
 636
 637         /* Filter out conflicts that came along for the ride. */
 638         if (depName != NULL && strcmp(depName, Name))
 639             continue;
 640
 641         /* Ignore colored conflicts not in our rainbow. */
 642         dscolor = rpmdsColor(conflicts);
 643         if (tscolor && dscolor && !(tscolor & dscolor))
 644             continue;
 645
 646         rc = unsatisfiedDepend(ts, conflicts, adding);
 647
 648         /* 1 == unsatisfied, 0 == satsisfied */
 649         switch (rc) {
 650         case 0:         /* conflicts exist. */
 651             rpmdsProblem(ts->probs, pkgNEVR, conflicts, NULL, adding);
 652             /*@switchbreak@*/ break;
 653         case 1:         /* conflicts don't exist. */
 654             /*@switchbreak@*/ break;
 655         case 2:         /* something went wrong! */
 656         default:
 657             ourrc = 1;
 658             /*@switchbreak@*/ break;
 659         }
 660     }
 661
 662     return ourrc;
 663 }
 664
 665 /**
 666  * Check dependency against installed packages.
 667  * Adding: check name/provides dep against each conflict match,
 668  * Erasing: check name/provides/filename dep against each requiredby match.
 669  * @param ts            transaction set
 670  * @param dep           dependency name
 671  * @param mi            rpm database iterator
 672  * @param adding        dependency is from added package set?
 673  * @return              0 no problems found
 674  */
 675 static int checkPackageSet(rpmts ts, const char * dep,
 676                 /*@only@*/ /*@null@*/ rpmdbMatchIterator mi, int adding)
 677         /*@globals rpmGlobalMacroContext, fileSystem, internalState @*/
 678         /*@modifies ts, mi, rpmGlobalMacroContext, fileSystem, internalState @*/
 679 {
 680     int scareMem = 1;
 681     Header h;
 682     int ec = 0;
 683
 684     (void) rpmdbPruneIterator(mi,
 685                 ts->removedPackages, ts->numRemovedPackages, 1);
 686     while ((h = rpmdbNextIterator(mi)) != NULL) {
 687         const char * pkgNEVR;
 688         rpmds requires, conflicts;
 689         int rc;
 690
 691         pkgNEVR = hGetNEVR(h, NULL);
 692         requires = rpmdsNew(h, RPMTAG_REQUIRENAME, scareMem);
 693         (void) rpmdsSetNoPromote(requires, _rpmds_nopromote);
 694         conflicts = rpmdsNew(h, RPMTAG_CONFLICTNAME, scareMem);
 695         (void) rpmdsSetNoPromote(requires, _rpmds_nopromote);
 696         rc = checkPackageDeps(ts, pkgNEVR, requires, conflicts, dep, 0, adding);
 697         conflicts = rpmdsFree(conflicts);
 698         requires = rpmdsFree(requires);
 699         pkgNEVR = _free(pkgNEVR);
 700
 701         if (rc) {
 702             ec = 1;
 703             break;
 704         }
 705     }
 706     mi = rpmdbFreeIterator(mi);
 707
 708     return ec;
 709 }
 710
 711 /**
 712  * Check to-be-erased dependencies against installed requires.
 713  * @param ts            transaction set
 714  * @param dep           requires name
 715  * @return              0 no problems found
 716  */
 717 static int checkDependentPackages(rpmts ts, const char * dep)
 718         /*@globals rpmGlobalMacroContext, fileSystem, internalState @*/
 719         /*@modifies ts, rpmGlobalMacroContext, fileSystem, internalState @*/
 720 {
 721     rpmdbMatchIterator mi;
 722     mi = rpmtsInitIterator(ts, RPMTAG_REQUIRENAME, dep, 0);
 723     return checkPackageSet(ts, dep, mi, 0);
 724 }
 725
 726 /**
 727  * Check to-be-added dependencies against installed conflicts.
 728  * @param ts            transaction set
 729  * @param dep           conflicts name
 730  * @return              0 no problems found
 731  */
 732 static int checkDependentConflicts(rpmts ts, const char * dep)
 733         /*@globals rpmGlobalMacroContext, fileSystem, internalState @*/
 734         /*@modifies ts, rpmGlobalMacroContext, fileSystem, internalState @*/
 735 {
 736     int rc = 0;
 737
 738     if (rpmtsGetRdb(ts) != NULL) {      /* XXX is this necessary? */
 739         rpmdbMatchIterator mi;
 740         mi = rpmtsInitIterator(ts, RPMTAG_CONFLICTNAME, dep, 0);
 741         rc = checkPackageSet(ts, dep, mi, 1);
 742     }
 743
 744     return rc;
 745 }
 746
 747 struct badDeps_s {
 748 /*@observer@*/ /*@owned@*/ /*@null@*/
 749     const char * pname;
 750 /*@observer@*/ /*@dependent@*/ /*@null@*/
 751     const char * qname;
 752 };
 753
 754 #ifdef REFERENCE
 755 static struct badDeps_s {
 756 /*@observer@*/ /*@null@*/ const char * pname;
 757 /*@observer@*/ /*@null@*/ const char * qname;
 758 } badDeps[] = {
 759     { "libtermcap", "bash" },
 760     { "modutils", "vixie-cron" },
 761     { "ypbind", "yp-tools" },
 762     { "ghostscript-fonts", "ghostscript" },
 763     /* 7.2 only */
 764     { "libgnomeprint15", "gnome-print" },
 765     { "nautilus", "nautilus-mozilla" },
 766     /* 7.1 only */
 767     { "arts", "kdelibs-sound" },
 768     /* 7.0 only */
 769     { "pango-gtkbeta-devel", "pango-gtkbeta" },
 770     { "XFree86", "Mesa" },
 771     { "compat-glibc", "db2" },
 772     { "compat-glibc", "db1" },
 773     { "pam", "initscripts" },
 774     { "initscripts", "sysklogd" },
 775     /* 6.2 */
 776     { "egcs-c++", "libstdc++" },
 777     /* 6.1 */
 778     { "pilot-link-devel", "pilot-link" },
 779     /* 5.2 */
 780     { "pam", "pamconfig" },
 781     { NULL, NULL }
 782 };
 783 #else
 784 /*@unchecked@*/
 785 static int badDepsInitialized = 0;
 786
 787 /*@unchecked@*/ /*@only@*/ /*@null@*/
 788 static struct badDeps_s * badDeps = NULL;
 789 #endif
 790
 791 /**
 792  */
 793 /*@-modobserver -observertrans @*/
 794 static void freeBadDeps(void)
 795         /*@globals badDeps, badDepsInitialized @*/
 796         /*@modifies badDeps, badDepsInitialized @*/
 797 {
 798     if (badDeps) {
 799         struct badDeps_s * bdp;
 800         for (bdp = badDeps; bdp->pname != NULL && bdp->qname != NULL; bdp++)
 801             bdp->pname = _free(bdp->pname);
 802         badDeps = _free(badDeps);
 803     }
 804     badDepsInitialized = 0;
 805 }
 806 /*@=modobserver =observertrans @*/
 807
 808 /**
 809  * Check for dependency relations to be ignored.
 810  *
 811  * @param p     successor element (i.e. with Requires: )
 812  * @param q     predecessor element (i.e. with Provides: )
 813  * @return      1 if dependency is to be ignored.
 814  */
 815 /*@-boundsread@*/
 816 static int ignoreDep(const rpmte p, const rpmte q)
 817         /*@globals badDeps, badDepsInitialized @*/
 818         /*@modifies badDeps, badDepsInitialized @*/
 819 {
 820     struct badDeps_s * bdp;
 821
 822 /*@-globs -mods@*/
 823     if (!badDepsInitialized) {
 824         char * s = rpmExpand("%{?_dependency_whiteout}", NULL);
 825         const char ** av = NULL;
 826         int ac = 0;
 827         int i;
 828
 829         if (s != NULL && *s != '\0'
 830         && !(i = poptParseArgvString(s, &ac, (const char ***)&av))
 831         && ac > 0 && av != NULL)
 832         {
 833             bdp = badDeps = xcalloc(ac+1, sizeof(*badDeps));
 834             for (i = 0; i < ac; i++, bdp++) {
 835                 char * pname, * qname;
 836
 837                 if (av[i] == NULL)
 838                     break;
 839                 pname = xstrdup(av[i]);
 840                 if ((qname = strchr(pname, '>')) != NULL)
 841                     *qname++ = '\0';
 842                 bdp->pname = pname;
 843                 /*@-usereleased@*/
 844                 bdp->qname = qname;
 845                 /*@=usereleased@*/
 846                 rpmMessage(RPMMESS_DEBUG,
 847                         _("ignore package name relation(s) [%d]\t%s -> %s\n"),
 848                         i, bdp->pname, (bdp->qname ? bdp->qname : "???"));
 849             }
 850             bdp->pname = NULL;
 851             bdp->qname = NULL;
 852         }
 853         av = _free(av);
 854         s = _free(s);
 855         badDepsInitialized++;
 856     }
 857 /*@=globs =mods@*/
 858
 859     /*@-compdef@*/
 860     if (badDeps != NULL)
 861     for (bdp = badDeps; bdp->pname != NULL && bdp->qname != NULL; bdp++) {
 862         if (!strcmp(rpmteN(p), bdp->pname) && !strcmp(rpmteN(q), bdp->qname))
 863             return 1;
 864     }
 865     return 0;
 866     /*@=compdef@*/
 867 }
 868 /*@=boundsread@*/
 869
 870 /**
 871  * Recursively mark all nodes with their predecessors.
 872  * @param tsi           successor chain
 873  * @param q             predecessor
 874  */
 875 static void markLoop(/*@special@*/ tsortInfo tsi, rpmte q)
 876         /*@globals internalState @*/
 877         /*@uses tsi @*/
 878         /*@modifies internalState @*/
 879 {
 880     rpmte p;
 881
 882     /*@-branchstate@*/ /* FIX: q is kept */
 883     while (tsi != NULL && (p = tsi->tsi_suc) != NULL) {
 884         tsi = tsi->tsi_next;
 885         if (rpmteTSI(p)->tsi_chain != NULL)
 886             continue;
 887         /*@-assignexpose -temptrans@*/
 888         rpmteTSI(p)->tsi_chain = q;
 889         /*@=assignexpose =temptrans@*/
 890         if (rpmteTSI(p)->tsi_next != NULL)
 891             markLoop(rpmteTSI(p)->tsi_next, p);
 892     }
 893     /*@=branchstate@*/
 894 }
 895
 896 static inline /*@observer@*/ const char * const identifyDepend(int_32 f)
 897         /*@*/
 898 {
 899     if (isLegacyPreReq(f))
 900         return "PreReq:";
 901     f = _notpre(f);
 902     if (f & RPMSENSE_SCRIPT_PRE)
 903         return "Requires(pre):";
 904     if (f & RPMSENSE_SCRIPT_POST)
 905         return "Requires(post):";
 906     if (f & RPMSENSE_SCRIPT_PREUN)
 907         return "Requires(preun):";
 908     if (f & RPMSENSE_SCRIPT_POSTUN)
 909         return "Requires(postun):";
 910     if (f & RPMSENSE_SCRIPT_VERIFY)
 911         return "Requires(verify):";
 912     if (f & RPMSENSE_FIND_REQUIRES)
 913         return "Requires(auto):";
 914     return "Requires:";
 915 }
 916
 917 /**
 918  * Find (and eliminate co-requisites) "q <- p" relation in dependency loop.
 919  * Search all successors of q for instance of p. Format the specific relation,
 920  * (e.g. p contains "Requires: q"). Unlink and free co-requisite (i.e.
 921  * pure Requires: dependencies) successor node(s).
 922  * @param q             sucessor (i.e. package required by p)
 923  * @param p             predecessor (i.e. package that "Requires: q")
 924  * @param requires      relation
 925  * @param zap           max. no. of co-requisites to remove (-1 is all)?
 926  * @retval nzaps        address of no. of relations removed
 927  * @return              (possibly NULL) formatted "q <- p" releation (malloc'ed)
 928  */
 929 /*@-boundswrite@*/
 930 /*@-mustmod@*/ /* FIX: hack modifies, but -type disables */
 931 static /*@owned@*/ /*@null@*/ const char *
 932 zapRelation(rpmte q, rpmte p,
 933                 /*@null@*/ rpmds requires,
 934                 int zap, /*@in@*/ /*@out@*/ int * nzaps)
 935         /*@modifies q, p, requires, *nzaps @*/
 936 {
 937     tsortInfo tsi_prev;
 938     tsortInfo tsi;
 939     const char *dp = NULL;
 940
 941     for (tsi_prev = rpmteTSI(q), tsi = rpmteTSI(q)->tsi_next;
 942          tsi != NULL;
 943         /* XXX Note: the loop traverses "not found", break on "found". */
 944         /*@-nullderef@*/
 945          tsi_prev = tsi, tsi = tsi->tsi_next)
 946         /*@=nullderef@*/
 947     {
 948         int_32 Flags;
 949
 950         /*@-abstractcompare@*/
 951         if (tsi->tsi_suc != p)
 952             continue;
 953         /*@=abstractcompare@*/
 954
 955         if (requires == NULL) continue;         /* XXX can't happen */
 956
 957         (void) rpmdsSetIx(requires, tsi->tsi_reqx);
 958
 959         Flags = rpmdsFlags(requires);
 960
 961         dp = rpmdsNewDNEVR( identifyDepend(Flags), requires);
 962
 963         /*
 964          * Attempt to unravel a dependency loop by eliminating Requires's.
 965          */
 966         /*@-branchstate@*/
 967         if (zap && !(Flags & RPMSENSE_PREREQ)) {
 968             rpmMessage(RPMMESS_DEBUG,
 969                         _("removing %s \"%s\" from tsort relations.\n"),
 970                         (rpmteNEVR(p) ?  rpmteNEVR(p) : "???"), dp);
 971             rpmteTSI(p)->tsi_count--;
 972             if (tsi_prev) tsi_prev->tsi_next = tsi->tsi_next;
 973             tsi->tsi_next = NULL;
 974             tsi->tsi_suc = NULL;
 975             tsi = _free(tsi);
 976             if (nzaps)
 977                 (*nzaps)++;
 978             if (zap)
 979                 zap--;
 980         }
 981         /*@=branchstate@*/
 982         /* XXX Note: the loop traverses "not found", get out now! */
 983         break;
 984     }
 985     return dp;
 986 }
 987 /*@=mustmod@*/
 988 /*@=boundswrite@*/
 989
 990 /**
 991  * Record next "q <- p" relation (i.e. "p" requires "q").
 992  * @param ts            transaction set
 993  * @param p             predecessor (i.e. package that "Requires: q")
 994  * @param selected      boolean package selected array
 995  * @param requires      relation
 996  * @return              0 always
 997  */
 998 /*@-mustmod@*/
 999 static inline int addRelation(rpmts ts,
1000                 /*@dependent@*/ rpmte p,
1001                 unsigned char * selected,
1002                 rpmds requires)
1003         /*@globals fileSystem @*/
1004         /*@modifies ts, p, *selected, fileSystem @*/
1005 {
1006     rpmtsi qi; rpmte q;
1007     tsortInfo tsi;
1008     const char * Name;
1009     fnpyKey key;
1010     alKey pkgKey;
1011     int i = 0;
1012
1013     if ((Name = rpmdsN(requires)) == NULL)
1014         return 0;
1015
1016     /* Avoid rpmlib feature dependencies. */
1017     if (!strncmp(Name, "rpmlib(", sizeof("rpmlib(")-1))
1018         return 0;
1019
1020     /* Avoid package config dependencies. */
1021     if (!strncmp(Name, "config(", sizeof("config(")-1))
1022         return 0;
1023
1024     pkgKey = RPMAL_NOMATCH;
1025     key = rpmalSatisfiesDepend(ts->addedPackages, requires, &pkgKey);
1026
1027     /* Ordering depends only on added package relations. */
1028     if (pkgKey == RPMAL_NOMATCH)
1029         return 0;
1030
1031 /* XXX Set q to the added package that has pkgKey == q->u.addedKey */
1032 /* XXX FIXME: bsearch is possible/needed here */
1033     for (qi = rpmtsiInit(ts), i = 0; (q = rpmtsiNext(qi, 0)) != NULL; i++) {
1034
1035         /* XXX Only added packages need be checked for matches. */
1036         if (rpmteType(q) == TR_REMOVED)
1037             continue;
1038
1039         if (pkgKey == rpmteAddedKey(q))
1040             break;
1041     }
1042     qi = rpmtsiFree(qi);
1043     if (q == NULL || i == ts->orderCount)
1044         return 0;
1045
1046     /* Avoid certain dependency relations. */
1047     if (ignoreDep(p, q))
1048         return 0;
1049
1050     /* Avoid redundant relations. */
1051     /* XXX TODO: add control bit. */
1052 /*@-boundsread@*/
1053     if (selected[i] != 0)
1054         return 0;
1055 /*@=boundsread@*/
1056 /*@-boundswrite@*/
1057     selected[i] = 1;
1058 /*@=boundswrite@*/
1059
1060     /* T3. Record next "q <- p" relation (i.e. "p" requires "q"). */
1061     rpmteTSI(p)->tsi_count++;                   /* bump p predecessor count */
1062
1063     if (rpmteDepth(p) <= rpmteDepth(q)) /* Save max. depth in dependency tree */
1064         (void) rpmteSetDepth(p, (rpmteDepth(q) + 1));
1065
1066     tsi = xcalloc(1, sizeof(*tsi));
1067     tsi->tsi_suc = p;
1068
1069     tsi->tsi_reqx = rpmdsIx(requires);
1070
1071     tsi->tsi_next = rpmteTSI(q)->tsi_next;
1072 /*@-mods@*/
1073     rpmteTSI(q)->tsi_next = tsi;
1074     rpmteTSI(q)->tsi_qcnt++;                    /* bump q successor count */
1075 /*@=mods@*/
1076     return 0;
1077 }
1078 /*@=mustmod@*/
1079
1080 /**
1081  * Compare ordered list entries by index (qsort/bsearch).
1082  * @param one           1st ordered list entry
1083  * @param two           2nd ordered list entry
1084  * @return              result of comparison
1085  */
1086 static int orderListIndexCmp(const void * one, const void * two)        /*@*/
1087 {
1088     /*@-castexpose@*/
1089     long a = (long) ((const orderListIndex)one)->pkgKey;
1090     long b = (long) ((const orderListIndex)two)->pkgKey;
1091     /*@=castexpose@*/
1092     return (a - b);
1093 }
1094
1095 /**
1096  * Add element to list sorting by tsi_qcnt.
1097  * @param p             new element
1098  * @retval qp           address of first element
1099  * @retval rp           address of last element
1100  */
1101 /*@-boundswrite@*/
1102 /*@-mustmod@*/
1103 static void addQ(/*@dependent@*/ rpmte p,
1104                 /*@in@*/ /*@out@*/ rpmte * qp,
1105                 /*@in@*/ /*@out@*/ rpmte * rp)
1106         /*@modifies p, *qp, *rp @*/
1107 {
1108     rpmte q, qprev;
1109
1110     /* Mark the package as queued. */
1111     rpmteTSI(p)->tsi_reqx = 1;
1112
1113     if ((*rp) == NULL) {        /* 1st element */
1114         /*@-dependenttrans@*/ /* FIX: double indirection */
1115         (*rp) = (*qp) = p;
1116         /*@=dependenttrans@*/
1117         return;
1118     }
1119
1120     /* Find location in queue using metric tsi_qcnt. */
1121     for (qprev = NULL, q = (*qp);
1122          q != NULL;
1123          qprev = q, q = rpmteTSI(q)->tsi_suc)
1124     {
1125         if (rpmteTSI(q)->tsi_qcnt <= rpmteTSI(p)->tsi_qcnt)
1126             break;
1127     }
1128
1129     if (qprev == NULL) {        /* insert at beginning of list */
1130         rpmteTSI(p)->tsi_suc = q;
1131         /*@-dependenttrans@*/
1132         (*qp) = p;              /* new head */
1133         /*@=dependenttrans@*/
1134     } else if (q == NULL) {     /* insert at end of list */
1135         rpmteTSI(qprev)->tsi_suc = p;
1136         /*@-dependenttrans@*/
1137         (*rp) = p;              /* new tail */
1138         /*@=dependenttrans@*/
1139     } else {                    /* insert between qprev and q */
1140         rpmteTSI(p)->tsi_suc = q;
1141         rpmteTSI(qprev)->tsi_suc = p;
1142     }
1143 }
1144 /*@=mustmod@*/
1145 /*@=boundswrite@*/
1146
1147 /*@-bounds@*/
1148 int rpmtsOrder(rpmts ts)
1149 {
1150     rpmds requires;
1151     int_32 Flags;
1152     int anaconda = rpmtsFlags(ts) & RPMTRANS_FLAG_ANACONDA;
1153     rpmtsi pi; rpmte p;
1154     rpmtsi qi; rpmte q;
1155     rpmtsi ri; rpmte r;
1156     tsortInfo tsi;
1157     tsortInfo tsi_next;
1158     alKey * ordering;
1159     int orderingCount = 0;
1160     unsigned char * selected = alloca(sizeof(*selected) * (ts->orderCount + 1));
1161     int loopcheck;
1162     rpmte * newOrder;
1163     int newOrderCount = 0;
1164     orderListIndex orderList;
1165     int numOrderList;
1166     int nrescans = 10;
1167     int _printed = 0;
1168     char deptypechar;
1169     size_t tsbytes;
1170     int oType = 0;
1171     int treex;
1172     int depth;
1173     int qlen;
1174     int i, j;
1175
1176 #ifdef  DYING
1177     rpmalMakeIndex(ts->addedPackages);
1178 #endif
1179
1180     /* T1. Initialize. */
1181     if (oType == 0)
1182         numOrderList = ts->orderCount;
1183     else {
1184         numOrderList = 0;
1185         if (oType & TR_ADDED)
1186             numOrderList += ts->numAddedPackages;
1187         if (oType & TR_REMOVED)
1188             numOrderList += ts->numRemovedPackages;
1189      }
1190     ordering = alloca(sizeof(*ordering) * (numOrderList + 1));
1191     loopcheck = numOrderList;
1192     tsbytes = 0;
1193
1194     pi = rpmtsiInit(ts);
1195     while ((p = rpmtsiNext(pi, oType)) != NULL)
1196         rpmteNewTSI(p);
1197     pi = rpmtsiFree(pi);
1198
1199     /* Record all relations. */
1200     rpmMessage(RPMMESS_DEBUG, _("========== recording tsort relations\n"));
1201     pi = rpmtsiInit(ts);
1202     while ((p = rpmtsiNext(pi, oType)) != NULL) {
1203
1204         if ((requires = rpmteDS(p, RPMTAG_REQUIRENAME)) == NULL)
1205             continue;
1206
1207         memset(selected, 0, sizeof(*selected) * ts->orderCount);
1208
1209         /* Avoid narcisstic relations. */
1210         selected[rpmtsiOc(pi)] = 1;
1211
1212         /* T2. Next "q <- p" relation. */
1213
1214         /* First, do pre-requisites. */
1215         requires = rpmdsInit(requires);
1216         if (requires != NULL)
1217         while (rpmdsNext(requires) >= 0) {
1218
1219             Flags = rpmdsFlags(requires);
1220
1221             switch (rpmteType(p)) {
1222             case TR_REMOVED:
1223                 /* Skip if not %preun/%postun requires or legacy prereq. */
1224                 if (isInstallPreReq(Flags)
1225                  || !( isErasePreReq(Flags) || isLegacyPreReq(Flags) ) )
1226                     /*@innercontinue@*/ continue;
1227                 /*@switchbreak@*/ break;
1228             case TR_ADDED:
1229                 /* Skip if not %pre/%post requires or legacy prereq. */
1230                 if (isErasePreReq(Flags)
1231                  || !( isInstallPreReq(Flags) || isLegacyPreReq(Flags) ) )
1232                     /*@innercontinue@*/ continue;
1233                 /*@switchbreak@*/ break;
1234             }
1235
1236             /* T3. Record next "q <- p" relation (i.e. "p" requires "q"). */
1237             (void) addRelation(ts, p, selected, requires);
1238
1239         }
1240
1241         /* Then do co-requisites. */
1242         requires = rpmdsInit(requires);
1243         if (requires != NULL)
1244         while (rpmdsNext(requires) >= 0) {
1245
1246             Flags = rpmdsFlags(requires);
1247
1248             switch (rpmteType(p)) {
1249             case TR_REMOVED:
1250                 /* Skip if %preun/%postun requires or legacy prereq. */
1251                 if (isInstallPreReq(Flags)
1252                  ||  ( isErasePreReq(Flags) || isLegacyPreReq(Flags) ) )
1253                     /*@innercontinue@*/ continue;
1254                 /*@switchbreak@*/ break;
1255             case TR_ADDED:
1256                 /* Skip if %pre/%post requires or legacy prereq. */
1257                 if (isErasePreReq(Flags)
1258                  ||  ( isInstallPreReq(Flags) || isLegacyPreReq(Flags) ) )
1259                     /*@innercontinue@*/ continue;
1260                 /*@switchbreak@*/ break;
1261             }
1262
1263             /* T3. Record next "q <- p" relation (i.e. "p" requires "q"). */
1264             (void) addRelation(ts, p, selected, requires);
1265
1266         }
1267     }
1268     pi = rpmtsiFree(pi);
1269
1270     /* Save predecessor count and mark tree roots. */
1271     treex = 0;
1272     pi = rpmtsiInit(ts);
1273     while ((p = rpmtsiNext(pi, oType)) != NULL) {
1274         int npreds;
1275
1276         npreds = rpmteTSI(p)->tsi_count;
1277
1278         (void) rpmteSetNpreds(p, npreds);
1279
1280         if (npreds == 0)
1281             (void) rpmteSetTree(p, treex++);
1282         else
1283             (void) rpmteSetTree(p, -1);
1284 #ifdef  UNNECESSARY
1285         (void) rpmteSetParent(p, NULL);
1286 #endif
1287
1288     }
1289     pi = rpmtsiFree(pi);
1290
1291     /* T4. Scan for zeroes. */
1292     rpmMessage(RPMMESS_DEBUG, _("========== tsorting packages (order, #predecessors, #succesors, tree, depth)\n"));
1293
1294 rescan:
1295     if (pi != NULL) pi = rpmtsiFree(pi);
1296     q = r = NULL;
1297     qlen = 0;
1298     pi = rpmtsiInit(ts);
1299     while ((p = rpmtsiNext(pi, oType)) != NULL) {
1300
1301         /* Prefer packages in chainsaw or anaconda presentation order. */
1302         if (anaconda)
1303             rpmteTSI(p)->tsi_qcnt = (ts->orderCount - rpmtsiOc(pi));
1304
1305         if (rpmteTSI(p)->tsi_count != 0)
1306             continue;
1307         rpmteTSI(p)->tsi_suc = NULL;
1308         addQ(p, &q, &r);
1309         qlen++;
1310     }
1311     pi = rpmtsiFree(pi);
1312
1313     /* T5. Output front of queue (T7. Remove from queue.) */
1314     for (; q != NULL; q = rpmteTSI(q)->tsi_suc) {
1315
1316         /* Mark the package as unqueued. */
1317         rpmteTSI(q)->tsi_reqx = 0;
1318
1319         if (oType != 0)
1320         switch (rpmteType(q)) {
1321         case TR_ADDED:
1322             if (!(oType & TR_ADDED))
1323                 continue;
1324             /*@switchbreak@*/ break;
1325         case TR_REMOVED:
1326             if (!(oType & TR_REMOVED))
1327                 continue;
1328             /*@switchbreak@*/ break;
1329         default:
1330             continue;
1331             /*@notreached@*/ /*@switchbreak@*/ break;
1332         }
1333         deptypechar = (rpmteType(q) == TR_REMOVED ? '-' : '+');
1334
1335         rpmMessage(RPMMESS_DEBUG, "%5d%5d%5d%5d%5d %*s%c%s\n",
1336                         orderingCount, rpmteNpreds(q),
1337                         rpmteTSI(q)->tsi_qcnt, rpmteTree(q), rpmteDepth(q),
1338                         (2 * rpmteDepth(q)), "",
1339                         deptypechar,
1340                         (rpmteNEVR(q) ? rpmteNEVR(q) : "???"));
1341
1342         treex = rpmteTree(q);
1343         depth = rpmteDepth(q);
1344         (void) rpmteSetDegree(q, 0);
1345         tsbytes += rpmtePkgFileSize(q);
1346
1347         ordering[orderingCount] = rpmteAddedKey(q);
1348         orderingCount++;
1349         qlen--;
1350         loopcheck--;
1351
1352         /* T6. Erase relations. */
1353         tsi_next = rpmteTSI(q)->tsi_next;
1354         rpmteTSI(q)->tsi_next = NULL;
1355         while ((tsi = tsi_next) != NULL) {
1356             tsi_next = tsi->tsi_next;
1357             tsi->tsi_next = NULL;
1358             p = tsi->tsi_suc;
1359             if (p && (--rpmteTSI(p)->tsi_count) <= 0) {
1360
1361                 (void) rpmteSetTree(p, treex);
1362                 (void) rpmteSetDepth(p, depth+1);
1363                 (void) rpmteSetParent(p, q);
1364                 (void) rpmteSetDegree(q, rpmteDegree(q)+1);
1365
1366                 /* XXX TODO: add control bit. */
1367                 rpmteTSI(p)->tsi_suc = NULL;
1368                 addQ(p, &rpmteTSI(q)->tsi_suc, &r);
1369                 qlen++;
1370             }
1371             tsi = _free(tsi);
1372         }
1373         if (!_printed && loopcheck == qlen && rpmteTSI(q)->tsi_suc != NULL) {
1374             _printed++;
1375             (void) rpmtsUnorderedSuccessors(ts, orderingCount);
1376             rpmMessage(RPMMESS_DEBUG,
1377                 _("========== successors only (%d bytes)\n"), (int)tsbytes);
1378
1379             /* Relink the queue in presentation order. */
1380             tsi = rpmteTSI(q);
1381             pi = rpmtsiInit(ts);
1382             while ((p = rpmtsiNext(pi, oType)) != NULL) {
1383                 /* Is this element in the queue? */
1384                 if (rpmteTSI(p)->tsi_reqx == 0)
1385                     /*@innercontinue@*/ continue;
1386                 tsi->tsi_suc = p;
1387                 tsi = rpmteTSI(p);
1388             }
1389             pi = rpmtsiFree(pi);
1390             tsi->tsi_suc = NULL;
1391         }
1392     }
1393
1394     /* T8. End of process. Check for loops. */
1395     if (loopcheck != 0) {
1396         int nzaps;
1397
1398         /* T9. Initialize predecessor chain. */
1399         nzaps = 0;
1400         qi = rpmtsiInit(ts);
1401         while ((q = rpmtsiNext(qi, oType)) != NULL) {
1402             rpmteTSI(q)->tsi_chain = NULL;
1403             rpmteTSI(q)->tsi_reqx = 0;
1404             /* Mark packages already sorted. */
1405             if (rpmteTSI(q)->tsi_count == 0)
1406                 rpmteTSI(q)->tsi_count = -1;
1407         }
1408         qi = rpmtsiFree(qi);
1409
1410         /* T10. Mark all packages with their predecessors. */
1411         qi = rpmtsiInit(ts);
1412         while ((q = rpmtsiNext(qi, oType)) != NULL) {
1413             if ((tsi = rpmteTSI(q)->tsi_next) == NULL)
1414                 continue;
1415             rpmteTSI(q)->tsi_next = NULL;
1416             markLoop(tsi, q);
1417             rpmteTSI(q)->tsi_next = tsi;
1418         }
1419         qi = rpmtsiFree(qi);
1420
1421         /* T11. Print all dependency loops. */
1422         ri = rpmtsiInit(ts);
1423         while ((r = rpmtsiNext(ri, oType)) != NULL)
1424         {
1425             int printed;
1426
1427             printed = 0;
1428
1429             /* T12. Mark predecessor chain, looking for start of loop. */
1430             for (q = rpmteTSI(r)->tsi_chain; q != NULL;
1431                  q = rpmteTSI(q)->tsi_chain)
1432             {
1433                 if (rpmteTSI(q)->tsi_reqx)
1434                     /*@innerbreak@*/ break;
1435                 rpmteTSI(q)->tsi_reqx = 1;
1436             }
1437
1438             /* T13. Print predecessor chain from start of loop. */
1439             while ((p = q) != NULL && (q = rpmteTSI(p)->tsi_chain) != NULL) {
1440                 const char * dp;
1441                 char buf[4096];
1442
1443                 /* Unchain predecessor loop. */
1444                 rpmteTSI(p)->tsi_chain = NULL;
1445
1446                 if (!printed) {
1447                     rpmMessage(RPMMESS_DEBUG, _("LOOP:\n"));
1448                     printed = 1;
1449                 }
1450
1451                 /* Find (and destroy if co-requisite) "q <- p" relation. */
1452                 requires = rpmteDS(p, RPMTAG_REQUIRENAME);
1453                 requires = rpmdsInit(requires);
1454                 if (requires == NULL)
1455                     /*@innercontinue@*/ continue;       /* XXX can't happen */
1456                 dp = zapRelation(q, p, requires, 1, &nzaps);
1457
1458                 /* Print next member of loop. */
1459                 buf[0] = '\0';
1460                 if (rpmteNEVR(p) != NULL)
1461                     (void) stpcpy(buf, rpmteNEVR(p));
1462                 rpmMessage(RPMMESS_DEBUG, "    %-40s %s\n", buf,
1463                         (dp ? dp : "not found!?!"));
1464
1465                 dp = _free(dp);
1466             }
1467
1468             /* Walk (and erase) linear part of predecessor chain as well. */
1469             for (p = r, q = rpmteTSI(r)->tsi_chain; q != NULL;
1470                  p = q, q = rpmteTSI(q)->tsi_chain)
1471             {
1472                 /* Unchain linear part of predecessor loop. */
1473                 rpmteTSI(p)->tsi_chain = NULL;
1474                 rpmteTSI(p)->tsi_reqx = 0;
1475             }
1476         }
1477         ri = rpmtsiFree(ri);
1478
1479         /* If a relation was eliminated, then continue sorting. */
1480         /* XXX TODO: add control bit. */
1481         if (nzaps && nrescans-- > 0) {
1482             rpmMessage(RPMMESS_DEBUG, _("========== continuing tsort ...\n"));
1483             goto rescan;
1484         }
1485
1486         /* Return no. of packages that could not be ordered. */
1487         rpmMessage(RPMMESS_ERROR, _("rpmtsOrder failed, %d elements remain\n"),
1488                         loopcheck);
1489         return loopcheck;
1490     }
1491
1492     /* Clean up tsort remnants (if any). */
1493     pi = rpmtsiInit(ts);
1494     while ((p = rpmtsiNext(pi, 0)) != NULL)
1495         rpmteFreeTSI(p);
1496     pi = rpmtsiFree(pi);
1497
1498     /*
1499      * The order ends up as installed packages followed by removed packages,
1500      * with removes for upgrades immediately following the installation of
1501      * the new package. This would be easier if we could sort the
1502      * addedPackages array, but we store indexes into it in various places.
1503      */
1504     orderList = xcalloc(numOrderList, sizeof(*orderList));
1505     j = 0;
1506     pi = rpmtsiInit(ts);
1507     while ((p = rpmtsiNext(pi, oType)) != NULL) {
1508         /* Prepare added package ordering permutation. */
1509         switch (rpmteType(p)) {
1510         case TR_ADDED:
1511             orderList[j].pkgKey = rpmteAddedKey(p);
1512             /*@switchbreak@*/ break;
1513         case TR_REMOVED:
1514             orderList[j].pkgKey = RPMAL_NOMATCH;
1515             /*@switchbreak@*/ break;
1516         }
1517         orderList[j].orIndex = rpmtsiOc(pi);
1518         j++;
1519     }
1520     pi = rpmtsiFree(pi);
1521
1522     qsort(orderList, numOrderList, sizeof(*orderList), orderListIndexCmp);
1523
1524 /*@-type@*/
1525     newOrder = xcalloc(ts->orderCount, sizeof(*newOrder));
1526 /*@=type@*/
1527     /*@-branchstate@*/
1528     for (i = 0, newOrderCount = 0; i < orderingCount; i++)
1529     {
1530         struct orderListIndex_s key;
1531         orderListIndex needle;
1532
1533         key.pkgKey = ordering[i];
1534         needle = bsearch(&key, orderList, numOrderList,
1535                                 sizeof(key), orderListIndexCmp);
1536         /* bsearch should never, ever fail */
1537         if (needle == NULL)
1538             continue;
1539
1540         j = needle->orIndex;
1541         if ((q = ts->order[j]) == NULL)
1542             continue;
1543
1544         newOrder[newOrderCount++] = q;
1545         ts->order[j] = NULL;
1546         if (anaconda)
1547         for (j = needle->orIndex + 1; j < ts->orderCount; j++) {
1548             if ((q = ts->order[j]) == NULL)
1549                 /*@innerbreak@*/ break;
1550             if (rpmteType(q) == TR_REMOVED
1551              && rpmteDependsOnKey(q) == needle->pkgKey)
1552             {
1553                 newOrder[newOrderCount++] = q;
1554                 ts->order[j] = NULL;
1555             } else
1556                 /*@innerbreak@*/ break;
1557         }
1558     }
1559     /*@=branchstate@*/
1560
1561     for (j = 0; j < ts->orderCount; j++) {
1562         if ((p = ts->order[j]) == NULL)
1563             continue;
1564         newOrder[newOrderCount++] = p;
1565         ts->order[j] = NULL;
1566     }
1567 assert(newOrderCount == ts->orderCount);
1568
1569 /*@+voidabstract@*/
1570     ts->order = _free(ts->order);
1571 /*@=voidabstract@*/
1572     ts->order = newOrder;
1573     ts->orderAlloced = ts->orderCount;
1574     orderList = _free(orderList);
1575
1576 #ifdef  DYING   /* XXX now done at the CLI level just before rpmtsRun(). */
1577     rpmtsClean(ts);
1578 #endif
1579     freeBadDeps();
1580
1581     return 0;
1582 }
1583 /*@=bounds@*/
1584
1585 int rpmtsCheck(rpmts ts)
1586 {
1587     uint_32 tscolor = rpmtsColor(ts);
1588     rpmdbMatchIterator mi = NULL;
1589     rpmtsi pi = NULL; rpmte p;
1590     int closeatexit = 0;
1591     int xx;
1592     int rc;
1593
1594     /* Do lazy, readonly, open of rpm database. */
1595     if (rpmtsGetRdb(ts) == NULL && ts->dbmode != -1) {
1596         if ((rc = rpmtsOpenDB(ts, ts->dbmode)) != 0)
1597             goto exit;
1598         closeatexit = 1;
1599     }
1600
1601     ts->probs = rpmpsFree(ts->probs);
1602     ts->probs = rpmpsCreate();
1603
1604     rpmalMakeIndex(ts->addedPackages);
1605
1606     /*
1607      * Look at all of the added packages and make sure their dependencies
1608      * are satisfied.
1609      */
1610     pi = rpmtsiInit(ts);
1611     while ((p = rpmtsiNext(pi, TR_ADDED)) != NULL) {
1612         rpmds provides;
1613
1614 /*@-nullpass@*/ /* FIX: rpmts{A,O} can return null. */
1615         rpmMessage(RPMMESS_DEBUG,  "========== +++ %s %s/%s 0x%x\n",
1616                 rpmteNEVR(p), rpmteA(p), rpmteO(p), rpmteColor(p));
1617 /*@=nullpass@*/
1618         rc = checkPackageDeps(ts, rpmteNEVR(p),
1619                         rpmteDS(p, RPMTAG_REQUIRENAME),
1620                         rpmteDS(p, RPMTAG_CONFLICTNAME),
1621                         NULL,
1622                         tscolor, 1);
1623         if (rc)
1624             goto exit;
1625
1626 #if defined(DYING) || defined(__LCLINT__)
1627         /* XXX all packages now have Provides: name = version-release */
1628         /* Adding: check name against conflicts matches. */
1629         rc = checkDependentConflicts(ts, rpmteN(p));
1630         if (rc)
1631             goto exit;
1632 #endif
1633
1634         rc = 0;
1635         provides = rpmteDS(p, RPMTAG_PROVIDENAME);
1636         provides = rpmdsInit(provides);
1637         if (provides == NULL || rpmdsN(provides) == NULL)
1638             continue;
1639         while (rpmdsNext(provides) >= 0) {
1640             const char * Name;
1641
1642             if ((Name = rpmdsN(provides)) == NULL)
1643                 /*@innercontinue@*/ continue;   /* XXX can't happen */
1644
1645             /* Adding: check provides key against conflicts matches. */
1646             if (!checkDependentConflicts(ts, Name))
1647                 /*@innercontinue@*/ continue;
1648             rc = 1;
1649             /*@innerbreak@*/ break;
1650         }
1651         if (rc)
1652             goto exit;
1653     }
1654     pi = rpmtsiFree(pi);
1655
1656     /*
1657      * Look at the removed packages and make sure they aren't critical.
1658      */
1659     pi = rpmtsiInit(ts);
1660     while ((p = rpmtsiNext(pi, TR_REMOVED)) != NULL) {
1661         rpmds provides;
1662         rpmfi fi;
1663
1664 /*@-nullpass@*/ /* FIX: rpmts{A,O} can return null. */
1665         rpmMessage(RPMMESS_DEBUG,  "========== --- %s %s/%s 0x%x\n",
1666                 rpmteNEVR(p), rpmteA(p), rpmteO(p), rpmteColor(p));
1667 /*@=nullpass@*/
1668
1669 #if defined(DYING) || defined(__LCLINT__)
1670         /* XXX all packages now have Provides: name = version-release */
1671         /* Erasing: check name against requiredby matches. */
1672         rc = checkDependentPackages(ts, rpmteN(p));
1673         if (rc)
1674                 goto exit;
1675 #endif
1676
1677         rc = 0;
1678         provides = rpmteDS(p, RPMTAG_PROVIDENAME);
1679         provides = rpmdsInit(provides);
1680         if (provides != NULL)
1681         while (rpmdsNext(provides) >= 0) {
1682             const char * Name;
1683
1684             if ((Name = rpmdsN(provides)) == NULL)
1685                 /*@innercontinue@*/ continue;   /* XXX can't happen */
1686
1687             /* Erasing: check provides against requiredby matches. */
1688             if (!checkDependentPackages(ts, Name))
1689                 /*@innercontinue@*/ continue;
1690             rc = 1;
1691             /*@innerbreak@*/ break;
1692         }
1693         if (rc)
1694             goto exit;
1695
1696         rc = 0;
1697         fi = rpmteFI(p, RPMTAG_BASENAMES);
1698         fi = rpmfiInit(fi, 0);
1699         while (rpmfiNext(fi) >= 0) {
1700             const char * fn = rpmfiFN(fi);
1701
1702             /* Erasing: check filename against requiredby matches. */
1703             if (!checkDependentPackages(ts, fn))
1704                 /*@innercontinue@*/ continue;
1705             rc = 1;
1706             /*@innerbreak@*/ break;
1707         }
1708         if (rc)
1709             goto exit;
1710     }
1711     pi = rpmtsiFree(pi);
1712
1713     rc = 0;
1714
1715 exit:
1716     mi = rpmdbFreeIterator(mi);
1717     pi = rpmtsiFree(pi);
1718     /*@-branchstate@*/
1719     if (closeatexit)
1720         xx = rpmtsCloseDB(ts);
1721     else if (_cacheDependsRC)
1722         xx = rpmdbCloseDBI(rpmtsGetRdb(ts), RPMDBI_DEPENDS);
1723     /*@=branchstate@*/
1724     return rc;
1725 }