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 /*@-nullstate@*/ /* FIX: data->data may be NULL */
 380                 xx = dbiGet(dbi, dbcursor, key, data, DB_SET);
 381 /*@=nullstate@*/
 382                 DNEVR = key->data;
 383                 DNEVRlen = key->size;
 384                 datap = data->data;
 385                 datalen = data->size;
 386
 387 /*@-boundswrite@*/
 388                 if (xx == 0 && datap && datalen == 4)
 389                     memcpy(&rc, datap, datalen);
 390 /*@=boundswrite@*/
 391                 xx = dbiCclose(dbi, dbcursor, 0);
 392             }
 393 /*@=branchstate@*/
 394
 395             if (rc >= 0) {
 396                 rpmdsNotify(dep, _("(cached)"), rc);
 397                 return rc;
 398             }
 399         }
 400     }
 401
 402 retry:
 403     rc = 0;     /* assume dependency is satisfied */
 404
 405 #if defined(DYING) || defined(__LCLINT__)
 406   { static /*@observer@*/ const char noProvidesString[] = "nada";
 407     static /*@observer@*/ const char * rcProvidesString = noProvidesString;
 408     int_32 Flags = rpmdsFlags(dep);
 409     const char * start;
 410     int i;
 411
 412     if (rcProvidesString == noProvidesString)
 413         rcProvidesString = rpmGetVar(RPMVAR_PROVIDES);
 414
 415     if (rcProvidesString != NULL && !(Flags & RPMSENSE_SENSEMASK)) {
 416
 417         i = strlen(Name);
 418         /*@-observertrans -mayaliasunique@*/
 419         while ((start = strstr(rcProvidesString, Name))) {
 420         /*@=observertrans =mayaliasunique@*/
 421 /*@-boundsread@*/
 422             if (xisspace(start[i]) || start[i] == '\0' || start[i] == ',') {
 423                 rpmdsNotify(dep, _("(rpmrc provides)"), rc);
 424                 goto exit;
 425             }
 426 /*@=boundsread@*/
 427             rcProvidesString = start + 1;
 428         }
 429     }
 430   }
 431 #endif
 432
 433     /*
 434      * New features in rpm packaging implicitly add versioned dependencies
 435      * on rpmlib provides. The dependencies look like "rpmlib(YaddaYadda)".
 436      * Check those dependencies now.
 437      */
 438     if (!strncmp(Name, "rpmlib(", sizeof("rpmlib(")-1)) {
 439         if (rpmCheckRpmlibProvides(dep)) {
 440             rpmdsNotify(dep, _("(rpmlib provides)"), rc);
 441             goto exit;
 442         }
 443         goto unsatisfied;
 444     }
 445
 446     /* Search added packages for the dependency. */
 447     if (rpmalSatisfiesDepend(ts->addedPackages, dep, NULL) != NULL) {
 448         /*
 449          * XXX Ick, context sensitive answers from dependency cache.
 450          * XXX Always resolve added dependencies within context to disambiguate.
 451          */
 452         if (_rpmds_nopromote)
 453             _cacheThisRC = 0;
 454         goto exit;
 455     }
 456
 457     /* XXX only the installer does not have the database open here. */
 458     if (rpmtsGetRdb(ts) != NULL) {
 459 /*@-boundsread@*/
 460         if (Name[0] == '/') {
 461             /* depFlags better be 0! */
 462
 463             mi = rpmtsInitIterator(ts, RPMTAG_BASENAMES, Name, 0);
 464
 465             (void) rpmdbPruneIterator(mi,
 466                         ts->removedPackages, ts->numRemovedPackages, 1);
 467
 468             while ((h = rpmdbNextIterator(mi)) != NULL) {
 469                 rpmdsNotify(dep, _("(db files)"), rc);
 470                 mi = rpmdbFreeIterator(mi);
 471                 goto exit;
 472             }
 473             mi = rpmdbFreeIterator(mi);
 474         }
 475 /*@=boundsread@*/
 476
 477         mi = rpmtsInitIterator(ts, RPMTAG_PROVIDENAME, Name, 0);
 478         (void) rpmdbPruneIterator(mi,
 479                         ts->removedPackages, ts->numRemovedPackages, 1);
 480         while ((h = rpmdbNextIterator(mi)) != NULL) {
 481             if (rpmdsAnyMatchesDep(h, dep, _rpmds_nopromote)) {
 482                 rpmdsNotify(dep, _("(db provides)"), rc);
 483                 mi = rpmdbFreeIterator(mi);
 484                 goto exit;
 485             }
 486         }
 487         mi = rpmdbFreeIterator(mi);
 488
 489 #if defined(DYING) || defined(__LCLINT__)
 490         mi = rpmtsInitIterator(ts, RPMTAG_NAME, Name, 0);
 491         (void) rpmdbPruneIterator(mi,
 492                         ts->removedPackages, ts->numRemovedPackages, 1);
 493         while ((h = rpmdbNextIterator(mi)) != NULL) {
 494             if (rpmdsAnyMatchesDep(h, dep, _rpmds_nopromote)) {
 495                 rpmdsNotify(dep, _("(db package)"), rc);
 496                 mi = rpmdbFreeIterator(mi);
 497                 goto exit;
 498             }
 499         }
 500         mi = rpmdbFreeIterator(mi);
 501 #endif
 502
 503     }
 504
 505     /*
 506      * Search for an unsatisfied dependency.
 507      */
 508 /*@-boundsread@*/
 509     if (adding && !retrying && !(rpmtsFlags(ts) & RPMTRANS_FLAG_NOSUGGEST)) {
 510         if (ts->solve != NULL) {
 511             xx = (*ts->solve) (ts, dep, ts->solveData);
 512             if (xx == 0)
 513                 goto exit;
 514             if (xx == -1) {
 515                 retrying = 1;
 516                 rpmalMakeIndex(ts->addedPackages);
 517                 goto retry;
 518             }
 519         }
 520     }
 521 /*@=boundsread@*/
 522
 523 unsatisfied:
 524     rc = 1;     /* dependency is unsatisfied */
 525     rpmdsNotify(dep, NULL, rc);
 526
 527 exit:
 528     /*
 529      * If dbiOpen/dbiPut fails (e.g. permissions), we can't cache.
 530      */
 531     if (_cacheDependsRC && _cacheThisRC) {
 532         dbiIndex dbi;
 533         dbi = dbiOpen(rpmtsGetRdb(ts), RPMDBI_DEPENDS, 0);
 534         if (dbi == NULL) {
 535             _cacheDependsRC = 0;
 536         } else {
 537             const char * DNEVR;
 538             xx = 0;
 539             /*@-branchstate@*/
 540             if ((DNEVR = rpmdsDNEVR(dep)) != NULL) {
 541                 DBC * dbcursor = NULL;
 542                 size_t DNEVRlen = strlen(DNEVR);
 543
 544                 xx = dbiCopen(dbi, dbi->dbi_txnid, &dbcursor, DB_WRITECURSOR);
 545
 546                 memset(key, 0, sizeof(*key));
 547 /*@i@*/         key->data = (void *) DNEVR;
 548                 key->size = DNEVRlen;
 549                 memset(data, 0, sizeof(*data));
 550                 data->data = &rc;
 551                 data->size = sizeof(rc);
 552
 553                 /*@-compmempass@*/
 554                 xx = dbiPut(dbi, dbcursor, key, data, 0);
 555                 /*@=compmempass@*/
 556                 xx = dbiCclose(dbi, dbcursor, DB_WRITECURSOR);
 557             }
 558             /*@=branchstate@*/
 559             if (xx)
 560                 _cacheDependsRC = 0;
 561         }
 562     }
 563     return rc;
 564 }
 565
 566 /**
 567  * Check added requires/conflicts against against installed+added packages.
 568  * @param ts            transaction set
 569  * @param pkgNEVR       package name-version-release
 570  * @param requires      Requires: dependencies (or NULL)
 571  * @param conflicts     Conflicts: dependencies (or NULL)
 572  * @param depName       dependency name to filter (or NULL)
 573  * @param tscolor       color bits for transaction set (0 disables)
 574  * @param adding        dependency is from added package set?
 575  * @return              0 no problems found
 576  */
 577 static int checkPackageDeps(rpmts ts, const char * pkgNEVR,
 578                 /*@null@*/ rpmds requires, /*@null@*/ rpmds conflicts,
 579                 /*@null@*/ const char * depName, uint_32 tscolor, int adding)
 580         /*@globals rpmGlobalMacroContext,
 581                 fileSystem, internalState @*/
 582         /*@modifies ts, requires, conflicts, rpmGlobalMacroContext,
 583                 fileSystem, internalState */
 584 {
 585     uint_32 dscolor;
 586     const char * Name;
 587     int rc;
 588     int ourrc = 0;
 589
 590     requires = rpmdsInit(requires);
 591     if (requires != NULL)
 592     while (!ourrc && rpmdsNext(requires) >= 0) {
 593
 594         if ((Name = rpmdsN(requires)) == NULL)
 595             continue;   /* XXX can't happen */
 596
 597         /* Filter out requires that came along for the ride. */
 598         if (depName != NULL && strcmp(depName, Name))
 599             continue;
 600
 601         /* Ignore colored requires not in our rainbow. */
 602         dscolor = rpmdsColor(requires);
 603         if (tscolor && dscolor && !(tscolor & dscolor))
 604             continue;
 605
 606         rc = unsatisfiedDepend(ts, requires, adding);
 607
 608         switch (rc) {
 609         case 0:         /* requirements are satisfied. */
 610             /*@switchbreak@*/ break;
 611         case 1:         /* requirements are not satisfied. */
 612         {   fnpyKey * suggestedKeys = NULL;
 613
 614             /*@-branchstate@*/
 615             if (ts->availablePackages != NULL) {
 616                 suggestedKeys = rpmalAllSatisfiesDepend(ts->availablePackages,
 617                                 requires, NULL);
 618             }
 619             /*@=branchstate@*/
 620
 621             rpmdsProblem(ts->probs, pkgNEVR, requires, suggestedKeys, adding);
 622
 623         }
 624             /*@switchbreak@*/ break;
 625         case 2:         /* something went wrong! */
 626         default:
 627             ourrc = 1;
 628             /*@switchbreak@*/ break;
 629         }
 630     }
 631
 632     conflicts = rpmdsInit(conflicts);
 633     if (conflicts != NULL)
 634     while (!ourrc && rpmdsNext(conflicts) >= 0) {
 635
 636         if ((Name = rpmdsN(conflicts)) == NULL)
 637             continue;   /* XXX can't happen */
 638
 639         /* Filter out conflicts that came along for the ride. */
 640         if (depName != NULL && strcmp(depName, Name))
 641             continue;
 642
 643         /* Ignore colored conflicts not in our rainbow. */
 644         dscolor = rpmdsColor(conflicts);
 645         if (tscolor && dscolor && !(tscolor & dscolor))
 646             continue;
 647
 648         rc = unsatisfiedDepend(ts, conflicts, adding);
 649
 650         /* 1 == unsatisfied, 0 == satsisfied */
 651         switch (rc) {
 652         case 0:         /* conflicts exist. */
 653             rpmdsProblem(ts->probs, pkgNEVR, conflicts, NULL, adding);
 654             /*@switchbreak@*/ break;
 655         case 1:         /* conflicts don't exist. */
 656             /*@switchbreak@*/ break;
 657         case 2:         /* something went wrong! */
 658         default:
 659             ourrc = 1;
 660             /*@switchbreak@*/ break;
 661         }
 662     }
 663
 664     return ourrc;
 665 }
 666
 667 /**
 668  * Check dependency against installed packages.
 669  * Adding: check name/provides dep against each conflict match,
 670  * Erasing: check name/provides/filename dep against each requiredby match.
 671  * @param ts            transaction set
 672  * @param dep           dependency name
 673  * @param mi            rpm database iterator
 674  * @param adding        dependency is from added package set?
 675  * @return              0 no problems found
 676  */
 677 static int checkPackageSet(rpmts ts, const char * dep,
 678                 /*@only@*/ /*@null@*/ rpmdbMatchIterator mi, int adding)
 679         /*@globals rpmGlobalMacroContext, fileSystem, internalState @*/
 680         /*@modifies ts, mi, rpmGlobalMacroContext, fileSystem, internalState @*/
 681 {
 682     int scareMem = 1;
 683     Header h;
 684     int ec = 0;
 685
 686     (void) rpmdbPruneIterator(mi,
 687                 ts->removedPackages, ts->numRemovedPackages, 1);
 688     while ((h = rpmdbNextIterator(mi)) != NULL) {
 689         const char * pkgNEVR;
 690         rpmds requires, conflicts;
 691         int rc;
 692
 693         pkgNEVR = hGetNEVR(h, NULL);
 694         requires = rpmdsNew(h, RPMTAG_REQUIRENAME, scareMem);
 695         (void) rpmdsSetNoPromote(requires, _rpmds_nopromote);
 696         conflicts = rpmdsNew(h, RPMTAG_CONFLICTNAME, scareMem);
 697         (void) rpmdsSetNoPromote(requires, _rpmds_nopromote);
 698         rc = checkPackageDeps(ts, pkgNEVR, requires, conflicts, dep, 0, adding);
 699         conflicts = rpmdsFree(conflicts);
 700         requires = rpmdsFree(requires);
 701         pkgNEVR = _free(pkgNEVR);
 702
 703         if (rc) {
 704             ec = 1;
 705             break;
 706         }
 707     }
 708     mi = rpmdbFreeIterator(mi);
 709
 710     return ec;
 711 }
 712
 713 /**
 714  * Check to-be-erased dependencies against installed requires.
 715  * @param ts            transaction set
 716  * @param dep           requires name
 717  * @return              0 no problems found
 718  */
 719 static int checkDependentPackages(rpmts ts, const char * dep)
 720         /*@globals rpmGlobalMacroContext, fileSystem, internalState @*/
 721         /*@modifies ts, rpmGlobalMacroContext, fileSystem, internalState @*/
 722 {
 723     rpmdbMatchIterator mi;
 724     mi = rpmtsInitIterator(ts, RPMTAG_REQUIRENAME, dep, 0);
 725     return checkPackageSet(ts, dep, mi, 0);
 726 }
 727
 728 /**
 729  * Check to-be-added dependencies against installed conflicts.
 730  * @param ts            transaction set
 731  * @param dep           conflicts name
 732  * @return              0 no problems found
 733  */
 734 static int checkDependentConflicts(rpmts ts, const char * dep)
 735         /*@globals rpmGlobalMacroContext, fileSystem, internalState @*/
 736         /*@modifies ts, rpmGlobalMacroContext, fileSystem, internalState @*/
 737 {
 738     int rc = 0;
 739
 740     if (rpmtsGetRdb(ts) != NULL) {      /* XXX is this necessary? */
 741         rpmdbMatchIterator mi;
 742         mi = rpmtsInitIterator(ts, RPMTAG_CONFLICTNAME, dep, 0);
 743         rc = checkPackageSet(ts, dep, mi, 1);
 744     }
 745
 746     return rc;
 747 }
 748
 749 struct badDeps_s {
 750 /*@observer@*/ /*@owned@*/ /*@null@*/
 751     const char * pname;
 752 /*@observer@*/ /*@dependent@*/ /*@null@*/
 753     const char * qname;
 754 };
 755
 756 #ifdef REFERENCE
 757 static struct badDeps_s {
 758 /*@observer@*/ /*@null@*/ const char * pname;
 759 /*@observer@*/ /*@null@*/ const char * qname;
 760 } badDeps[] = {
 761     { "libtermcap", "bash" },
 762     { "modutils", "vixie-cron" },
 763     { "ypbind", "yp-tools" },
 764     { "ghostscript-fonts", "ghostscript" },
 765     /* 7.2 only */
 766     { "libgnomeprint15", "gnome-print" },
 767     { "nautilus", "nautilus-mozilla" },
 768     /* 7.1 only */
 769     { "arts", "kdelibs-sound" },
 770     /* 7.0 only */
 771     { "pango-gtkbeta-devel", "pango-gtkbeta" },
 772     { "XFree86", "Mesa" },
 773     { "compat-glibc", "db2" },
 774     { "compat-glibc", "db1" },
 775     { "pam", "initscripts" },
 776     { "initscripts", "sysklogd" },
 777     /* 6.2 */
 778     { "egcs-c++", "libstdc++" },
 779     /* 6.1 */
 780     { "pilot-link-devel", "pilot-link" },
 781     /* 5.2 */
 782     { "pam", "pamconfig" },
 783     { NULL, NULL }
 784 };
 785 #else
 786 /*@unchecked@*/
 787 static int badDepsInitialized = 0;
 788
 789 /*@unchecked@*/ /*@only@*/ /*@null@*/
 790 static struct badDeps_s * badDeps = NULL;
 791 #endif
 792
 793 /**
 794  */
 795 /*@-modobserver -observertrans @*/
 796 static void freeBadDeps(void)
 797         /*@globals badDeps, badDepsInitialized @*/
 798         /*@modifies badDeps, badDepsInitialized @*/
 799 {
 800     if (badDeps) {
 801         struct badDeps_s * bdp;
 802         for (bdp = badDeps; bdp->pname != NULL && bdp->qname != NULL; bdp++)
 803             bdp->pname = _free(bdp->pname);
 804         badDeps = _free(badDeps);
 805     }
 806     badDepsInitialized = 0;
 807 }
 808 /*@=modobserver =observertrans @*/
 809
 810 /**
 811  * Check for dependency relations to be ignored.
 812  *
 813  * @param p     successor element (i.e. with Requires: )
 814  * @param q     predecessor element (i.e. with Provides: )
 815  * @return      1 if dependency is to be ignored.
 816  */
 817 /*@-boundsread@*/
 818 static int ignoreDep(const rpmte p, const rpmte q)
 819         /*@globals badDeps, badDepsInitialized, rpmGlobalMacroContext @*/
 820         /*@modifies badDeps, badDepsInitialized, rpmGlobalMacroContext @*/
 821 {
 822     struct badDeps_s * bdp;
 823
 824     if (!badDepsInitialized) {
 825         char * s = rpmExpand("%{?_dependency_whiteout}", NULL);
 826         const char ** av = NULL;
 827         int ac = 0;
 828         int i;
 829
 830         if (s != NULL && *s != '\0'
 831         && !(i = poptParseArgvString(s, &ac, (const char ***)&av))
 832         && ac > 0 && av != NULL)
 833         {
 834             bdp = badDeps = xcalloc(ac+1, sizeof(*badDeps));
 835             for (i = 0; i < ac; i++, bdp++) {
 836                 char * pname, * qname;
 837
 838                 if (av[i] == NULL)
 839                     break;
 840                 pname = xstrdup(av[i]);
 841                 if ((qname = strchr(pname, '>')) != NULL)
 842                     *qname++ = '\0';
 843                 bdp->pname = pname;
 844                 /*@-usereleased@*/
 845                 bdp->qname = qname;
 846                 /*@=usereleased@*/
 847                 rpmMessage(RPMMESS_DEBUG,
 848                         _("ignore package name relation(s) [%d]\t%s -> %s\n"),
 849                         i, bdp->pname, (bdp->qname ? bdp->qname : "???"));
 850             }
 851             bdp->pname = NULL;
 852             bdp->qname = NULL;
 853         }
 854         av = _free(av);
 855         s = _free(s);
 856         badDepsInitialized++;
 857     }
 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 rpmGlobalMacroContext, fileSystem, internalState @*/
1004         /*@modifies ts, p, *selected, rpmGlobalMacroContext,
1005                 fileSystem, internalState @*/
1006 {
1007     rpmtsi qi; rpmte q;
1008     tsortInfo tsi;
1009     const char * Name;
1010     fnpyKey key;
1011     alKey pkgKey;
1012     int i = 0;
1013
1014     if ((Name = rpmdsN(requires)) == NULL)
1015         return 0;
1016
1017     /* Avoid rpmlib feature dependencies. */
1018     if (!strncmp(Name, "rpmlib(", sizeof("rpmlib(")-1))
1019         return 0;
1020
1021     /* Avoid package config dependencies. */
1022     if (!strncmp(Name, "config(", sizeof("config(")-1))
1023         return 0;
1024
1025     pkgKey = RPMAL_NOMATCH;
1026     key = rpmalSatisfiesDepend(ts->addedPackages, requires, &pkgKey);
1027
1028     /* Ordering depends only on added package relations. */
1029     if (pkgKey == RPMAL_NOMATCH)
1030         return 0;
1031
1032 /* XXX Set q to the added package that has pkgKey == q->u.addedKey */
1033 /* XXX FIXME: bsearch is possible/needed here */
1034     for (qi = rpmtsiInit(ts), i = 0; (q = rpmtsiNext(qi, 0)) != NULL; i++) {
1035
1036         /* XXX Only added packages need be checked for matches. */
1037         if (rpmteType(q) == TR_REMOVED)
1038             continue;
1039
1040         if (pkgKey == rpmteAddedKey(q))
1041             break;
1042     }
1043     qi = rpmtsiFree(qi);
1044     if (q == NULL || i == ts->orderCount)
1045         return 0;
1046
1047     /* Avoid certain dependency relations. */
1048     if (ignoreDep(p, q))
1049         return 0;
1050
1051     /* Avoid redundant relations. */
1052     /* XXX TODO: add control bit. */
1053 /*@-boundsread@*/
1054     if (selected[i] != 0)
1055         return 0;
1056 /*@=boundsread@*/
1057 /*@-boundswrite@*/
1058     selected[i] = 1;
1059 /*@=boundswrite@*/
1060
1061     /* T3. Record next "q <- p" relation (i.e. "p" requires "q"). */
1062     rpmteTSI(p)->tsi_count++;                   /* bump p predecessor count */
1063
1064     if (rpmteDepth(p) <= rpmteDepth(q)) /* Save max. depth in dependency tree */
1065         (void) rpmteSetDepth(p, (rpmteDepth(q) + 1));
1066
1067     tsi = xcalloc(1, sizeof(*tsi));
1068     tsi->tsi_suc = p;
1069
1070     tsi->tsi_reqx = rpmdsIx(requires);
1071
1072     tsi->tsi_next = rpmteTSI(q)->tsi_next;
1073     rpmteTSI(q)->tsi_next = tsi;
1074     rpmteTSI(q)->tsi_qcnt++;                    /* bump q successor count */
1075     return 0;
1076 }
1077 /*@=mustmod@*/
1078
1079 /**
1080  * Compare ordered list entries by index (qsort/bsearch).
1081  * @param one           1st ordered list entry
1082  * @param two           2nd ordered list entry
1083  * @return              result of comparison
1084  */
1085 static int orderListIndexCmp(const void * one, const void * two)        /*@*/
1086 {
1087     /*@-castexpose@*/
1088     long a = (long) ((const orderListIndex)one)->pkgKey;
1089     long b = (long) ((const orderListIndex)two)->pkgKey;
1090     /*@=castexpose@*/
1091     return (a - b);
1092 }
1093
1094 /**
1095  * Add element to list sorting by tsi_qcnt.
1096  * @param p             new element
1097  * @retval qp           address of first element
1098  * @retval rp           address of last element
1099  */
1100 /*@-boundswrite@*/
1101 /*@-mustmod@*/
1102 static void addQ(/*@dependent@*/ rpmte p,
1103                 /*@in@*/ /*@out@*/ rpmte * qp,
1104                 /*@in@*/ /*@out@*/ rpmte * rp)
1105         /*@modifies p, *qp, *rp @*/
1106 {
1107     rpmte q, qprev;
1108
1109     /* Mark the package as queued. */
1110     rpmteTSI(p)->tsi_reqx = 1;
1111
1112     if ((*rp) == NULL) {        /* 1st element */
1113         /*@-dependenttrans@*/ /* FIX: double indirection */
1114         (*rp) = (*qp) = p;
1115         /*@=dependenttrans@*/
1116         return;
1117     }
1118
1119     /* Find location in queue using metric tsi_qcnt. */
1120     for (qprev = NULL, q = (*qp);
1121          q != NULL;
1122          qprev = q, q = rpmteTSI(q)->tsi_suc)
1123     {
1124         if (rpmteTSI(q)->tsi_qcnt <= rpmteTSI(p)->tsi_qcnt)
1125             break;
1126     }
1127
1128     if (qprev == NULL) {        /* insert at beginning of list */
1129         rpmteTSI(p)->tsi_suc = q;
1130         /*@-dependenttrans@*/
1131         (*qp) = p;              /* new head */
1132         /*@=dependenttrans@*/
1133     } else if (q == NULL) {     /* insert at end of list */
1134         rpmteTSI(qprev)->tsi_suc = p;
1135         /*@-dependenttrans@*/
1136         (*rp) = p;              /* new tail */
1137         /*@=dependenttrans@*/
1138     } else {                    /* insert between qprev and q */
1139         rpmteTSI(p)->tsi_suc = q;
1140         rpmteTSI(qprev)->tsi_suc = p;
1141     }
1142 }
1143 /*@=mustmod@*/
1144 /*@=boundswrite@*/
1145
1146 /*@-bounds@*/
1147 int rpmtsOrder(rpmts ts)
1148 {
1149     rpmds requires;
1150     int_32 Flags;
1151     int anaconda = rpmtsFlags(ts) & RPMTRANS_FLAG_ANACONDA;
1152     rpmtsi pi; rpmte p;
1153     rpmtsi qi; rpmte q;
1154     rpmtsi ri; rpmte r;
1155     tsortInfo tsi;
1156     tsortInfo tsi_next;
1157     alKey * ordering;
1158     int orderingCount = 0;
1159     unsigned char * selected = alloca(sizeof(*selected) * (ts->orderCount + 1));
1160     int loopcheck;
1161     rpmte * newOrder;
1162     int newOrderCount = 0;
1163     orderListIndex orderList;
1164     int numOrderList;
1165     int nrescans = 10;
1166     int _printed = 0;
1167     char deptypechar;
1168     size_t tsbytes;
1169     int oType = 0;
1170     int treex;
1171     int depth;
1172     int qlen;
1173     int i, j;
1174
1175 #ifdef  DYING
1176     rpmalMakeIndex(ts->addedPackages);
1177 #endif
1178
1179     (void) rpmswEnter(rpmtsOp(ts, RPMTS_OP_ORDER), 0);
1180
1181     /* T1. Initialize. */
1182     if (oType == 0)
1183         numOrderList = ts->orderCount;
1184     else {
1185         numOrderList = 0;
1186         if (oType & TR_ADDED)
1187             numOrderList += ts->numAddedPackages;
1188         if (oType & TR_REMOVED)
1189             numOrderList += ts->numRemovedPackages;
1190      }
1191     ordering = alloca(sizeof(*ordering) * (numOrderList + 1));
1192     loopcheck = numOrderList;
1193     tsbytes = 0;
1194
1195     pi = rpmtsiInit(ts);
1196     while ((p = rpmtsiNext(pi, oType)) != NULL)
1197         rpmteNewTSI(p);
1198     pi = rpmtsiFree(pi);
1199
1200     /* Record all relations. */
1201     rpmMessage(RPMMESS_DEBUG, _("========== recording tsort relations\n"));
1202     pi = rpmtsiInit(ts);
1203     while ((p = rpmtsiNext(pi, oType)) != NULL) {
1204
1205         if ((requires = rpmteDS(p, RPMTAG_REQUIRENAME)) == NULL)
1206             continue;
1207
1208         memset(selected, 0, sizeof(*selected) * ts->orderCount);
1209
1210         /* Avoid narcisstic relations. */
1211         selected[rpmtsiOc(pi)] = 1;
1212
1213         /* T2. Next "q <- p" relation. */
1214
1215         /* First, do pre-requisites. */
1216         requires = rpmdsInit(requires);
1217         if (requires != NULL)
1218         while (rpmdsNext(requires) >= 0) {
1219
1220             Flags = rpmdsFlags(requires);
1221
1222             switch (rpmteType(p)) {
1223             case TR_REMOVED:
1224                 /* Skip if not %preun/%postun requires or legacy prereq. */
1225                 if (isInstallPreReq(Flags)
1226                  || !( isErasePreReq(Flags) || isLegacyPreReq(Flags) ) )
1227                     /*@innercontinue@*/ continue;
1228                 /*@switchbreak@*/ break;
1229             case TR_ADDED:
1230                 /* Skip if not %pre/%post requires or legacy prereq. */
1231                 if (isErasePreReq(Flags)
1232                  || !( isInstallPreReq(Flags) || isLegacyPreReq(Flags) ) )
1233                     /*@innercontinue@*/ continue;
1234                 /*@switchbreak@*/ break;
1235             }
1236
1237             /* T3. Record next "q <- p" relation (i.e. "p" requires "q"). */
1238             (void) addRelation(ts, p, selected, requires);
1239
1240         }
1241
1242         /* Then do co-requisites. */
1243         requires = rpmdsInit(requires);
1244         if (requires != NULL)
1245         while (rpmdsNext(requires) >= 0) {
1246
1247             Flags = rpmdsFlags(requires);
1248
1249             switch (rpmteType(p)) {
1250             case TR_REMOVED:
1251                 /* Skip if %preun/%postun requires or legacy prereq. */
1252                 if (isInstallPreReq(Flags)
1253                  ||  ( isErasePreReq(Flags) || isLegacyPreReq(Flags) ) )
1254                     /*@innercontinue@*/ continue;
1255                 /*@switchbreak@*/ break;
1256             case TR_ADDED:
1257                 /* Skip if %pre/%post requires or legacy prereq. */
1258                 if (isErasePreReq(Flags)
1259                  ||  ( isInstallPreReq(Flags) || isLegacyPreReq(Flags) ) )
1260                     /*@innercontinue@*/ continue;
1261                 /*@switchbreak@*/ break;
1262             }
1263
1264             /* T3. Record next "q <- p" relation (i.e. "p" requires "q"). */
1265             (void) addRelation(ts, p, selected, requires);
1266
1267         }
1268     }
1269     pi = rpmtsiFree(pi);
1270
1271     /* Save predecessor count and mark tree roots. */
1272     treex = 0;
1273     pi = rpmtsiInit(ts);
1274     while ((p = rpmtsiNext(pi, oType)) != NULL) {
1275         int npreds;
1276
1277         npreds = rpmteTSI(p)->tsi_count;
1278
1279         (void) rpmteSetNpreds(p, npreds);
1280
1281         if (npreds == 0)
1282             (void) rpmteSetTree(p, treex++);
1283         else
1284             (void) rpmteSetTree(p, -1);
1285 #ifdef  UNNECESSARY
1286         (void) rpmteSetParent(p, NULL);
1287 #endif
1288
1289     }
1290     pi = rpmtsiFree(pi);
1291
1292     /* T4. Scan for zeroes. */
1293     rpmMessage(RPMMESS_DEBUG, _("========== tsorting packages (order, #predecessors, #succesors, tree, depth)\n"));
1294
1295 rescan:
1296     if (pi != NULL) pi = rpmtsiFree(pi);
1297     q = r = NULL;
1298     qlen = 0;
1299     pi = rpmtsiInit(ts);
1300     while ((p = rpmtsiNext(pi, oType)) != NULL) {
1301
1302         /* Prefer packages in chainsaw or anaconda presentation order. */
1303         if (anaconda)
1304             rpmteTSI(p)->tsi_qcnt = (ts->orderCount - rpmtsiOc(pi));
1305
1306         if (rpmteTSI(p)->tsi_count != 0)
1307             continue;
1308         rpmteTSI(p)->tsi_suc = NULL;
1309         addQ(p, &q, &r);
1310         qlen++;
1311     }
1312     pi = rpmtsiFree(pi);
1313
1314     /* T5. Output front of queue (T7. Remove from queue.) */
1315     for (; q != NULL; q = rpmteTSI(q)->tsi_suc) {
1316
1317         /* Mark the package as unqueued. */
1318         rpmteTSI(q)->tsi_reqx = 0;
1319
1320         if (oType != 0)
1321         switch (rpmteType(q)) {
1322         case TR_ADDED:
1323             if (!(oType & TR_ADDED))
1324                 continue;
1325             /*@switchbreak@*/ break;
1326         case TR_REMOVED:
1327             if (!(oType & TR_REMOVED))
1328                 continue;
1329             /*@switchbreak@*/ break;
1330         default:
1331             continue;
1332             /*@notreached@*/ /*@switchbreak@*/ break;
1333         }
1334         deptypechar = (rpmteType(q) == TR_REMOVED ? '-' : '+');
1335
1336         rpmMessage(RPMMESS_DEBUG, "%5d%5d%5d%5d%5d %*s%c%s\n",
1337                         orderingCount, rpmteNpreds(q),
1338                         rpmteTSI(q)->tsi_qcnt, rpmteTree(q), rpmteDepth(q),
1339                         (2 * rpmteDepth(q)), "",
1340                         deptypechar,
1341                         (rpmteNEVR(q) ? rpmteNEVR(q) : "???"));
1342
1343         treex = rpmteTree(q);
1344         depth = rpmteDepth(q);
1345         (void) rpmteSetDegree(q, 0);
1346         tsbytes += rpmtePkgFileSize(q);
1347
1348         ordering[orderingCount] = rpmteAddedKey(q);
1349         orderingCount++;
1350         qlen--;
1351         loopcheck--;
1352
1353         /* T6. Erase relations. */
1354         tsi_next = rpmteTSI(q)->tsi_next;
1355         rpmteTSI(q)->tsi_next = NULL;
1356         while ((tsi = tsi_next) != NULL) {
1357             tsi_next = tsi->tsi_next;
1358             tsi->tsi_next = NULL;
1359             p = tsi->tsi_suc;
1360             if (p && (--rpmteTSI(p)->tsi_count) <= 0) {
1361
1362                 (void) rpmteSetTree(p, treex);
1363                 (void) rpmteSetDepth(p, depth+1);
1364                 (void) rpmteSetParent(p, q);
1365                 (void) rpmteSetDegree(q, rpmteDegree(q)+1);
1366
1367                 /* XXX TODO: add control bit. */
1368                 rpmteTSI(p)->tsi_suc = NULL;
1369                 addQ(p, &rpmteTSI(q)->tsi_suc, &r);
1370                 qlen++;
1371             }
1372             tsi = _free(tsi);
1373         }
1374         if (!_printed && loopcheck == qlen && rpmteTSI(q)->tsi_suc != NULL) {
1375             _printed++;
1376             (void) rpmtsUnorderedSuccessors(ts, orderingCount);
1377             rpmMessage(RPMMESS_DEBUG,
1378                 _("========== successors only (%d bytes)\n"), (int)tsbytes);
1379
1380             /* Relink the queue in presentation order. */
1381             tsi = rpmteTSI(q);
1382             pi = rpmtsiInit(ts);
1383             while ((p = rpmtsiNext(pi, oType)) != NULL) {
1384                 /* Is this element in the queue? */
1385                 if (rpmteTSI(p)->tsi_reqx == 0)
1386                     /*@innercontinue@*/ continue;
1387                 tsi->tsi_suc = p;
1388                 tsi = rpmteTSI(p);
1389             }
1390             pi = rpmtsiFree(pi);
1391             tsi->tsi_suc = NULL;
1392         }
1393     }
1394
1395     /* T8. End of process. Check for loops. */
1396     if (loopcheck != 0) {
1397         int nzaps;
1398
1399         /* T9. Initialize predecessor chain. */
1400         nzaps = 0;
1401         qi = rpmtsiInit(ts);
1402         while ((q = rpmtsiNext(qi, oType)) != NULL) {
1403             rpmteTSI(q)->tsi_chain = NULL;
1404             rpmteTSI(q)->tsi_reqx = 0;
1405             /* Mark packages already sorted. */
1406             if (rpmteTSI(q)->tsi_count == 0)
1407                 rpmteTSI(q)->tsi_count = -1;
1408         }
1409         qi = rpmtsiFree(qi);
1410
1411         /* T10. Mark all packages with their predecessors. */
1412         qi = rpmtsiInit(ts);
1413         while ((q = rpmtsiNext(qi, oType)) != NULL) {
1414             if ((tsi = rpmteTSI(q)->tsi_next) == NULL)
1415                 continue;
1416             rpmteTSI(q)->tsi_next = NULL;
1417             markLoop(tsi, q);
1418             rpmteTSI(q)->tsi_next = tsi;
1419         }
1420         qi = rpmtsiFree(qi);
1421
1422         /* T11. Print all dependency loops. */
1423         ri = rpmtsiInit(ts);
1424         while ((r = rpmtsiNext(ri, oType)) != NULL)
1425         {
1426             int printed;
1427
1428             printed = 0;
1429
1430             /* T12. Mark predecessor chain, looking for start of loop. */
1431             for (q = rpmteTSI(r)->tsi_chain; q != NULL;
1432                  q = rpmteTSI(q)->tsi_chain)
1433             {
1434                 if (rpmteTSI(q)->tsi_reqx)
1435                     /*@innerbreak@*/ break;
1436                 rpmteTSI(q)->tsi_reqx = 1;
1437             }
1438
1439             /* T13. Print predecessor chain from start of loop. */
1440             while ((p = q) != NULL && (q = rpmteTSI(p)->tsi_chain) != NULL) {
1441                 const char * dp;
1442                 char buf[4096];
1443
1444                 /* Unchain predecessor loop. */
1445                 rpmteTSI(p)->tsi_chain = NULL;
1446
1447                 if (!printed) {
1448                     rpmMessage(RPMMESS_DEBUG, _("LOOP:\n"));
1449                     printed = 1;
1450                 }
1451
1452                 /* Find (and destroy if co-requisite) "q <- p" relation. */
1453                 requires = rpmteDS(p, RPMTAG_REQUIRENAME);
1454                 requires = rpmdsInit(requires);
1455                 if (requires == NULL)
1456                     /*@innercontinue@*/ continue;       /* XXX can't happen */
1457                 dp = zapRelation(q, p, requires, 1, &nzaps);
1458
1459                 /* Print next member of loop. */
1460                 buf[0] = '\0';
1461                 if (rpmteNEVR(p) != NULL)
1462                     (void) stpcpy(buf, rpmteNEVR(p));
1463                 rpmMessage(RPMMESS_DEBUG, "    %-40s %s\n", buf,
1464                         (dp ? dp : "not found!?!"));
1465
1466                 dp = _free(dp);
1467             }
1468
1469             /* Walk (and erase) linear part of predecessor chain as well. */
1470             for (p = r, q = rpmteTSI(r)->tsi_chain; q != NULL;
1471                  p = q, q = rpmteTSI(q)->tsi_chain)
1472             {
1473                 /* Unchain linear part of predecessor loop. */
1474                 rpmteTSI(p)->tsi_chain = NULL;
1475                 rpmteTSI(p)->tsi_reqx = 0;
1476             }
1477         }
1478         ri = rpmtsiFree(ri);
1479
1480         /* If a relation was eliminated, then continue sorting. */
1481         /* XXX TODO: add control bit. */
1482         if (nzaps && nrescans-- > 0) {
1483             rpmMessage(RPMMESS_DEBUG, _("========== continuing tsort ...\n"));
1484             goto rescan;
1485         }
1486
1487         /* Return no. of packages that could not be ordered. */
1488         rpmMessage(RPMMESS_ERROR, _("rpmtsOrder failed, %d elements remain\n"),
1489                         loopcheck);
1490         return loopcheck;
1491     }
1492
1493     /* Clean up tsort remnants (if any). */
1494     pi = rpmtsiInit(ts);
1495     while ((p = rpmtsiNext(pi, 0)) != NULL)
1496         rpmteFreeTSI(p);
1497     pi = rpmtsiFree(pi);
1498
1499     /*
1500      * The order ends up as installed packages followed by removed packages,
1501      * with removes for upgrades immediately following the installation of
1502      * the new package. This would be easier if we could sort the
1503      * addedPackages array, but we store indexes into it in various places.
1504      */
1505     orderList = xcalloc(numOrderList, sizeof(*orderList));
1506     j = 0;
1507     pi = rpmtsiInit(ts);
1508     while ((p = rpmtsiNext(pi, oType)) != NULL) {
1509         /* Prepare added package ordering permutation. */
1510         switch (rpmteType(p)) {
1511         case TR_ADDED:
1512             orderList[j].pkgKey = rpmteAddedKey(p);
1513             /*@switchbreak@*/ break;
1514         case TR_REMOVED:
1515             orderList[j].pkgKey = RPMAL_NOMATCH;
1516             /*@switchbreak@*/ break;
1517         }
1518         orderList[j].orIndex = rpmtsiOc(pi);
1519         j++;
1520     }
1521     pi = rpmtsiFree(pi);
1522
1523     qsort(orderList, numOrderList, sizeof(*orderList), orderListIndexCmp);
1524
1525 /*@-type@*/
1526     newOrder = xcalloc(ts->orderCount, sizeof(*newOrder));
1527 /*@=type@*/
1528     /*@-branchstate@*/
1529     for (i = 0, newOrderCount = 0; i < orderingCount; i++)
1530     {
1531         struct orderListIndex_s key;
1532         orderListIndex needle;
1533
1534         key.pkgKey = ordering[i];
1535         needle = bsearch(&key, orderList, numOrderList,
1536                                 sizeof(key), orderListIndexCmp);
1537         /* bsearch should never, ever fail */
1538         if (needle == NULL)
1539             continue;
1540
1541         j = needle->orIndex;
1542         if ((q = ts->order[j]) == NULL)
1543             continue;
1544
1545         newOrder[newOrderCount++] = q;
1546         ts->order[j] = NULL;
1547         if (anaconda)
1548         for (j = needle->orIndex + 1; j < ts->orderCount; j++) {
1549             if ((q = ts->order[j]) == NULL)
1550                 /*@innerbreak@*/ break;
1551             if (rpmteType(q) == TR_REMOVED
1552              && rpmteDependsOnKey(q) == needle->pkgKey)
1553             {
1554                 newOrder[newOrderCount++] = q;
1555                 ts->order[j] = NULL;
1556             } else
1557                 /*@innerbreak@*/ break;
1558         }
1559     }
1560     /*@=branchstate@*/
1561
1562     for (j = 0; j < ts->orderCount; j++) {
1563         if ((p = ts->order[j]) == NULL)
1564             continue;
1565         newOrder[newOrderCount++] = p;
1566         ts->order[j] = NULL;
1567     }
1568 assert(newOrderCount == ts->orderCount);
1569
1570 /*@+voidabstract@*/
1571     ts->order = _free(ts->order);
1572 /*@=voidabstract@*/
1573     ts->order = newOrder;
1574     ts->orderAlloced = ts->orderCount;
1575     orderList = _free(orderList);
1576
1577 #ifdef  DYING   /* XXX now done at the CLI level just before rpmtsRun(). */
1578     rpmtsClean(ts);
1579 #endif
1580     freeBadDeps();
1581
1582     (void) rpmswExit(rpmtsOp(ts, RPMTS_OP_ORDER), 0);
1583
1584     return 0;
1585 }
1586 /*@=bounds@*/
1587
1588 int rpmtsCheck(rpmts ts)
1589 {
1590     uint_32 tscolor = rpmtsColor(ts);
1591     rpmdbMatchIterator mi = NULL;
1592     rpmtsi pi = NULL; rpmte p;
1593     int closeatexit = 0;
1594     int xx;
1595     int rc;
1596
1597     (void) rpmswEnter(rpmtsOp(ts, RPMTS_OP_CHECK), 0);
1598
1599     /* Do lazy, readonly, open of rpm database. */
1600     if (rpmtsGetRdb(ts) == NULL && ts->dbmode != -1) {
1601         if ((rc = rpmtsOpenDB(ts, ts->dbmode)) != 0)
1602             goto exit;
1603         closeatexit = 1;
1604     }
1605
1606     ts->probs = rpmpsFree(ts->probs);
1607     ts->probs = rpmpsCreate();
1608
1609     rpmalMakeIndex(ts->addedPackages);
1610
1611     /*
1612      * Look at all of the added packages and make sure their dependencies
1613      * are satisfied.
1614      */
1615     pi = rpmtsiInit(ts);
1616     while ((p = rpmtsiNext(pi, TR_ADDED)) != NULL) {
1617         rpmds provides;
1618
1619 /*@-nullpass@*/ /* FIX: rpmts{A,O} can return null. */
1620         rpmMessage(RPMMESS_DEBUG,  "========== +++ %s %s/%s 0x%x\n",
1621                 rpmteNEVR(p), rpmteA(p), rpmteO(p), rpmteColor(p));
1622 /*@=nullpass@*/
1623         rc = checkPackageDeps(ts, rpmteNEVR(p),
1624                         rpmteDS(p, RPMTAG_REQUIRENAME),
1625                         rpmteDS(p, RPMTAG_CONFLICTNAME),
1626                         NULL,
1627                         tscolor, 1);
1628         if (rc)
1629             goto exit;
1630
1631 #if defined(DYING) || defined(__LCLINT__)
1632         /* XXX all packages now have Provides: name = version-release */
1633         /* Adding: check name against conflicts matches. */
1634         rc = checkDependentConflicts(ts, rpmteN(p));
1635         if (rc)
1636             goto exit;
1637 #endif
1638
1639         rc = 0;
1640         provides = rpmteDS(p, RPMTAG_PROVIDENAME);
1641         provides = rpmdsInit(provides);
1642         if (provides == NULL || rpmdsN(provides) == NULL)
1643             continue;
1644         while (rpmdsNext(provides) >= 0) {
1645             const char * Name;
1646
1647             if ((Name = rpmdsN(provides)) == NULL)
1648                 /*@innercontinue@*/ continue;   /* XXX can't happen */
1649
1650             /* Adding: check provides key against conflicts matches. */
1651             if (!checkDependentConflicts(ts, Name))
1652                 /*@innercontinue@*/ continue;
1653             rc = 1;
1654             /*@innerbreak@*/ break;
1655         }
1656         if (rc)
1657             goto exit;
1658     }
1659     pi = rpmtsiFree(pi);
1660
1661     /*
1662      * Look at the removed packages and make sure they aren't critical.
1663      */
1664     pi = rpmtsiInit(ts);
1665     while ((p = rpmtsiNext(pi, TR_REMOVED)) != NULL) {
1666         rpmds provides;
1667         rpmfi fi;
1668
1669 /*@-nullpass@*/ /* FIX: rpmts{A,O} can return null. */
1670         rpmMessage(RPMMESS_DEBUG,  "========== --- %s %s/%s 0x%x\n",
1671                 rpmteNEVR(p), rpmteA(p), rpmteO(p), rpmteColor(p));
1672 /*@=nullpass@*/
1673
1674 #if defined(DYING) || defined(__LCLINT__)
1675         /* XXX all packages now have Provides: name = version-release */
1676         /* Erasing: check name against requiredby matches. */
1677         rc = checkDependentPackages(ts, rpmteN(p));
1678         if (rc)
1679                 goto exit;
1680 #endif
1681
1682         rc = 0;
1683         provides = rpmteDS(p, RPMTAG_PROVIDENAME);
1684         provides = rpmdsInit(provides);
1685         if (provides != NULL)
1686         while (rpmdsNext(provides) >= 0) {
1687             const char * Name;
1688
1689             if ((Name = rpmdsN(provides)) == NULL)
1690                 /*@innercontinue@*/ continue;   /* XXX can't happen */
1691
1692             /* Erasing: check provides against requiredby matches. */
1693             if (!checkDependentPackages(ts, Name))
1694                 /*@innercontinue@*/ continue;
1695             rc = 1;
1696             /*@innerbreak@*/ break;
1697         }
1698         if (rc)
1699             goto exit;
1700
1701         rc = 0;
1702         fi = rpmteFI(p, RPMTAG_BASENAMES);
1703         fi = rpmfiInit(fi, 0);
1704         while (rpmfiNext(fi) >= 0) {
1705             const char * fn = rpmfiFN(fi);
1706
1707             /* Erasing: check filename against requiredby matches. */
1708             if (!checkDependentPackages(ts, fn))
1709                 /*@innercontinue@*/ continue;
1710             rc = 1;
1711             /*@innerbreak@*/ break;
1712         }
1713         if (rc)
1714             goto exit;
1715     }
1716     pi = rpmtsiFree(pi);
1717
1718     rc = 0;
1719
1720 exit:
1721     mi = rpmdbFreeIterator(mi);
1722     pi = rpmtsiFree(pi);
1723
1724     (void) rpmswExit(rpmtsOp(ts, RPMTS_OP_CHECK), 0);
1725
1726     /*@-branchstate@*/
1727     if (closeatexit)
1728         xx = rpmtsCloseDB(ts);
1729     else if (_cacheDependsRC)
1730         xx = rpmdbCloseDBI(rpmtsGetRdb(ts), RPMDBI_DEPENDS);
1731     /*@=branchstate@*/
1732     return rc;
1733 }