Main Page Modules Data Structures File List Data Fields Globals Related Pages

# lib/depends.c

Go to the documentation of this file.

    00001
    00005 #include "system.h"
    00006
    00007 #include <rpmcli.h>             /* XXX rpmcliPackagesTotal */
    00008
    00009 #include <rpmmacro.h>           /* XXX rpmExpand("%{_dependency_whiteout}" */
    00010
    00011 #include "rpmdb.h"              /* XXX response cache needs dbiOpen et al. */
    00012
    00013 #include "rpmds.h"
    00014 #include "rpmfi.h"
    00015
    00016 #define _RPMTE_INTERNAL
    00017 #include "rpmte.h"
    00018
    00019 #define _RPMTS_INTERNAL
    00020 #include "rpmts.h"
    00021
    00022 #include "debug.h"
    00023
    00024 /*@access tsortInfo @*/
    00025 /*@access rpmts @*/
    00026
    00027 /*@access dbiIndex @*/          /* XXX for dbi->dbi_txnid */
    00028
    00029 /*@access alKey @*/     /* XXX for reordering and RPMAL_NOMATCH assign */
    00030
    00033 typedef /*@abstract@*/ struct orderListIndex_s *        orderListIndex;
    00034 /*@access orderListIndex@*/
    00035
    00038 struct orderListIndex_s {
    00039 /*@dependent@*/
    00040     alKey pkgKey;
    00041     int orIndex;
    00042 };
    00043
    00044 /*@unchecked@*/
    00045 int _cacheDependsRC = 1;
    00046
    00047 /*@observer@*/ /*@unchecked@*/
    00048 const char *rpmNAME = PACKAGE;
    00049
    00050 /*@observer@*/ /*@unchecked@*/
    00051 const char *rpmEVR = VERSION;
    00052
    00053 /*@unchecked@*/
    00054 int rpmFLAGS = RPMSENSE_EQUAL;
    00055
    00062 static int intcmp(const void * a, const void * b)
    00063         /*@requires maxRead(a) == 0 /\ maxRead(b) == 0 @*/
    00064 {
    00065     const int * aptr = a;
    00066     const int * bptr = b;
    00067     int rc = (*aptr - *bptr);
    00068     return rc;
    00069 }
    00070
    00079 static int removePackage(rpmts ts, Header h, int dboffset,
    00080                 /*@exposed@*/ /*@dependent@*/ /*@null@*/ alKey depends)
    00081         /*@globals fileSystem @*/
    00082         /*@modifies ts, h, fileSystem @*/
    00083 {
    00084     rpmte p;
    00085
    00086     /* Filter out duplicate erasures. */
    00087     if (ts->numRemovedPackages > 0 && ts->removedPackages != NULL) {
    00088 /*@-boundswrite@*/
    00089         if (bsearch(&dboffset, ts->removedPackages, ts->numRemovedPackages,
    00090                         sizeof(*ts->removedPackages), intcmp) != NULL)
    00091             return 0;
    00092 /*@=boundswrite@*/
    00093     }
    00094
    00095     if (ts->numRemovedPackages == ts->allocedRemovedPackages) {
    00096         ts->allocedRemovedPackages += ts->delta;
    00097         ts->removedPackages = xrealloc(ts->removedPackages,
    00098                 sizeof(ts->removedPackages) * ts->allocedRemovedPackages);
    00099     }
    00100
    00101     if (ts->removedPackages != NULL) {  /* XXX can't happen. */
    00102 /*@-boundswrite@*/
    00103         ts->removedPackages[ts->numRemovedPackages] = dboffset;
    00104         ts->numRemovedPackages++;
    00105 /*@=boundswrite@*/
    00106         if (ts->numRemovedPackages > 1)
    00107             qsort(ts->removedPackages, ts->numRemovedPackages,
    00108                         sizeof(*ts->removedPackages), intcmp);
    00109     }
    00110
    00111     if (ts->orderCount >= ts->orderAlloced) {
    00112         ts->orderAlloced += (ts->orderCount - ts->orderAlloced) + ts->delta;
    00113 /*@-type +voidabstract @*/
    00114         ts->order = xrealloc(ts->order, sizeof(*ts->order) * ts->orderAlloced);
    00115 /*@=type =voidabstract @*/
    00116     }
    00117
    00118     p = rpmteNew(ts, h, TR_REMOVED, NULL, NULL, dboffset, depends);
    00119 /*@-boundswrite@*/
    00120     ts->order[ts->orderCount] = p;
    00121     ts->orderCount++;
    00122 /*@=boundswrite@*/
    00123
    00124     return 0;
    00125 }
    00126
    00127 int rpmtsAddInstallElement(rpmts ts, Header h,
    00128                         fnpyKey key, int upgrade, rpmRelocation * relocs)
    00129 {
    00130     HGE_t hge = (HGE_t)headerGetEntryMinMemory;
    00131     int isSource;
    00132     int duplicate = 0;
    00133     rpmtsi pi; rpmte p;
    00134     rpmds add;
    00135     rpmds obsoletes;
    00136     alKey pkgKey;       /* addedPackages key */
    00137     int xx;
    00138     int ec = 0;
    00139     int rc;
    00140     int oc;
    00141
    00142     /*
    00143      * Check for previously added versions with the same name.
    00144      * FIXME: only catches previously added, older packages.
    00145      */
    00146     add = rpmdsThis(h, RPMTAG_REQUIRENAME, (RPMSENSE_EQUAL|RPMSENSE_LESS));
    00147     pkgKey = RPMAL_NOMATCH;
    00148     for (pi = rpmtsiInit(ts), oc = 0; (p = rpmtsiNext(pi, 0)) != NULL; oc++) {
    00149         rpmds this;
    00150
    00151         /* XXX Only added packages need be checked for dupes. */
    00152         if (rpmteType(p) == TR_REMOVED)
    00153             continue;
    00154
    00155         if ((this = rpmteDS(p, RPMTAG_NAME)) == NULL)
    00156             continue;   /* XXX can't happen */
    00157
    00158         rc = rpmdsCompare(add, this);
    00159         if (rc != 0) {
    00160             const char * pkgNEVR = rpmdsDNEVR(this);
    00161             const char * addNEVR = rpmdsDNEVR(add);
    00162             rpmMessage(RPMMESS_WARNING,
    00163                 _("package %s was already added, replacing with %s\n"),
    00164                 (pkgNEVR ? pkgNEVR + 2 : "?pkgNEVR?"),
    00165                 (addNEVR ? addNEVR + 2 : "?addNEVR?"));
    00166             duplicate = 1;
    00167             pkgKey = rpmteAddedKey(p);
    00168             break;
    00169         }
    00170     }
    00171     pi = rpmtsiFree(pi);
    00172     add = rpmdsFree(add);
    00173
    00174     isSource = headerIsEntry(h, RPMTAG_SOURCEPACKAGE);
    00175
    00176     if (oc >= ts->orderAlloced) {
    00177         ts->orderAlloced += (oc - ts->orderAlloced) + ts->delta;
    00178 /*@-type +voidabstract @*/
    00179         ts->order = xrealloc(ts->order, ts->orderAlloced * sizeof(*ts->order));
    00180 /*@=type =voidabstract @*/
    00181     }
    00182
    00183     p = rpmteNew(ts, h, TR_ADDED, key, relocs, -1, pkgKey);
    00184
    00185     if (duplicate && oc < ts->orderCount) {
    00186 /*@-type -unqualifiedtrans@*/
    00187 /*@-boundswrite@*/
    00188         ts->order[oc] = rpmteFree(ts->order[oc]);
    00189 /*@=boundswrite@*/
    00190 /*@=type =unqualifiedtrans@*/
    00191     }
    00192
    00193 /*@-boundswrite@*/
    00194     ts->order[oc] = p;
    00195 /*@=boundswrite@*/
    00196     if (!duplicate) {
    00197         ts->orderCount++;
    00198         rpmcliPackagesTotal++;
    00199     }
    00200
    00201     pkgKey = rpmalAdd(&ts->addedPackages, pkgKey, rpmteKey(p),
    00202                         rpmteDS(p, RPMTAG_PROVIDENAME),
    00203                         rpmteFI(p, RPMTAG_BASENAMES));
    00204     if (pkgKey == RPMAL_NOMATCH) {
    00205 /*@-boundswrite@*/
    00206         ts->order[oc] = rpmteFree(ts->order[oc]);
    00207 /*@=boundswrite@*/
    00208         ec = 1;
    00209         goto exit;
    00210     }
    00211     (void) rpmteSetAddedKey(p, pkgKey);
    00212
    00213 #ifdef  NOYET
    00214   /* XXX this needs a search over ts->order, not ts->addedPackages */
    00215   { uint_32 *pp = NULL;
    00216
    00217     /* XXX This should be added always so that packages look alike.
    00218      * XXX However, there is logic in files.c/depends.c that checks for
    00219      * XXX existence (rather than value) that will need to change as well.
    00220      */
    00221     if (hge(h, RPMTAG_MULTILIBS, NULL, (void **) &pp, NULL))
    00222         multiLibMask = *pp;
    00223
    00224     if (multiLibMask) {
    00225         for (i = 0; i < pkgNum - 1; i++) {
    00226             if (!strcmp (rpmteN(p), al->list[i].name)
    00227                 && hge(al->list[i].h, RPMTAG_MULTILIBS, NULL,
    00228                                   (void **) &pp, NULL)
    00229                 && !rpmVersionCompare(p->h, al->list[i].h)
    00230                 && *pp && !(*pp & multiLibMask))
    00231                     (void) rpmteSetMultiLib(p, multiLibMask);
    00232         }
    00233     }
    00234   }
    00235 #endif
    00236
    00237     if (!duplicate) {
    00238         ts->numAddedPackages++;
    00239     }
    00240
    00241     if (!upgrade)
    00242         goto exit;
    00243
    00244     /* XXX binary rpms always have RPMTAG_SOURCERPM, source rpms do not */
    00245     if (isSource)
    00246         goto exit;
    00247
    00248     /* Do lazy (readonly?) open of rpm database. */
    00249     if (rpmtsGetRdb(ts) == NULL && ts->dbmode != -1) {
    00250         if ((ec = rpmtsOpenDB(ts, ts->dbmode)) != 0)
    00251             goto exit;
    00252     }
    00253
    00254 /*@-boundsread@*/
    00255     {   rpmdbMatchIterator mi;
    00256         Header h2;
    00257
    00258         mi = rpmtsInitIterator(ts, RPMTAG_PROVIDENAME, rpmteN(p), 0);
    00259         while((h2 = rpmdbNextIterator(mi)) != NULL) {
    00260             if (rpmVersionCompare(h, h2))
    00261                 xx = removePackage(ts, h2, rpmdbGetIteratorOffset(mi), pkgKey);
    00262             else {
    00263                 uint_32 *pp, multiLibMask = 0, oldmultiLibMask = 0;
    00264
    00265                 if (hge(h2, RPMTAG_MULTILIBS, NULL, (void **) &pp, NULL))
    00266                     oldmultiLibMask = *pp;
    00267                 if (hge(h, RPMTAG_MULTILIBS, NULL, (void **) &pp, NULL))
    00268                     multiLibMask = *pp;
    00269                 if (oldmultiLibMask && multiLibMask
    00270                  && !(oldmultiLibMask & multiLibMask))
    00271                 {
    00272                     (void) rpmteSetMultiLib(p, multiLibMask);
    00273                 }
    00274             }
    00275         }
    00276         mi = rpmdbFreeIterator(mi);
    00277     }
    00278 /*@=boundsread@*/
    00279
    00280     obsoletes = rpmdsLink(rpmteDS(p, RPMTAG_OBSOLETENAME), "Obsoletes");
    00281     obsoletes = rpmdsInit(obsoletes);
    00282     if (obsoletes != NULL)
    00283     while (rpmdsNext(obsoletes) >= 0) {
    00284         const char * Name;
    00285
    00286         if ((Name = rpmdsN(obsoletes)) == NULL)
    00287             continue;   /* XXX can't happen */
    00288
    00289         /* XXX avoid self-obsoleting packages. */
    00290         if (!strcmp(rpmteN(p), Name))
    00291                 continue;
    00292
    00293         {   rpmdbMatchIterator mi;
    00294             Header h2;
    00295
    00296             mi = rpmtsInitIterator(ts, RPMTAG_PROVIDENAME, Name, 0);
    00297
    00298             xx = rpmdbPruneIterator(mi,
    00299                 ts->removedPackages, ts->numRemovedPackages, 1);
    00300
    00301             while((h2 = rpmdbNextIterator(mi)) != NULL) {
    00302                 /*
    00303                  * Rpm prior to 3.0.3 does not have versioned obsoletes.
    00304                  * If no obsoletes version info is available, match all names.
    00305                  */
    00306                 if (rpmdsEVR(obsoletes) == NULL
    00307                  || rpmdsAnyMatchesDep(h2, obsoletes, _rpmds_nopromote))
    00308                     xx = removePackage(ts, h2, rpmdbGetIteratorOffset(mi), pkgKey);
    00309             }
    00310             mi = rpmdbFreeIterator(mi);
    00311         }
    00312     }
    00313     obsoletes = rpmdsFree(obsoletes);
    00314
    00315     ec = 0;
    00316
    00317 exit:
    00318     pi = rpmtsiFree(pi);
    00319     return ec;
    00320 }
    00321
    00322 int rpmtsAddEraseElement(rpmts ts, Header h, int dboffset)
    00323 {
    00324     return removePackage(ts, h, dboffset, RPMAL_NOMATCH);
    00325 }
    00326
    00334 static int unsatisfiedDepend(rpmts ts, rpmds dep, int adding)
    00335         /*@globals _cacheDependsRC, rpmGlobalMacroContext,
    00336                 fileSystem, internalState @*/
    00337         /*@modifies ts, _cacheDependsRC, rpmGlobalMacroContext,
    00338                 fileSystem, internalState @*/
    00339 {
    00340     DBT * key = alloca(sizeof(*key));
    00341     DBT * data = alloca(sizeof(*data));
    00342     rpmdbMatchIterator mi;
    00343     const char * Name;
    00344     Header h;
    00345     int _cacheThisRC = 1;
    00346     int rc;
    00347     int xx;
    00348     int retrying = 0;
    00349
    00350     if ((Name = rpmdsN(dep)) == NULL)
    00351         return 0;       /* XXX can't happen */
    00352
    00353     /*
    00354      * Check if dbiOpen/dbiPut failed (e.g. permissions), we can't cache.
    00355      */
    00356     if (_cacheDependsRC) {
    00357         dbiIndex dbi;
    00358         dbi = dbiOpen(rpmtsGetRdb(ts), RPMDBI_DEPENDS, 0);
    00359         if (dbi == NULL)
    00360             _cacheDependsRC = 0;
    00361         else {
    00362             const char * DNEVR;
    00363
    00364             rc = -1;
    00365 /*@-branchstate@*/
    00366             if ((DNEVR = rpmdsDNEVR(dep)) != NULL) {
    00367                 DBC * dbcursor = NULL;
    00368                 void * datap = NULL;
    00369                 size_t datalen = 0;
    00370                 size_t DNEVRlen = strlen(DNEVR);
    00371
    00372                 xx = dbiCopen(dbi, dbi->dbi_txnid, &dbcursor, 0);
    00373
    00374                 memset(key, 0, sizeof(*key));
    00375 /*@i@*/         key->data = (void *) DNEVR;
    00376                 key->size = DNEVRlen;
    00377                 memset(data, 0, sizeof(*data));
    00378                 data->data = datap;
    00379                 data->size = datalen;
    00380                 xx = dbiGet(dbi, dbcursor, key, data, DB_SET);
    00381                 DNEVR = key->data;
    00382                 DNEVRlen = key->size;
    00383                 datap = data->data;
    00384                 datalen = data->size;
    00385
    00386 /*@-boundswrite@*/
    00387                 if (xx == 0 && datap && datalen == 4)
    00388                     memcpy(&rc, datap, datalen);
    00389 /*@=boundswrite@*/
    00390                 xx = dbiCclose(dbi, dbcursor, 0);
    00391             }
    00392 /*@=branchstate@*/
    00393
    00394             if (rc >= 0) {
    00395                 rpmdsNotify(dep, _("(cached)"), rc);
    00396                 return rc;
    00397             }
    00398         }
    00399     }
    00400
    00401 retry:
    00402     rc = 0;     /* assume dependency is satisfied */
    00403
    00404 #if defined(DYING) || defined(__LCLINT__)
    00405   { static /*@observer@*/ const char noProvidesString[] = "nada";
    00406     static /*@observer@*/ const char * rcProvidesString = noProvidesString;
    00407     int_32 Flags = rpmdsFlags(dep);
    00408     const char * start;
    00409     int i;
    00410
    00411     if (rcProvidesString == noProvidesString)
    00412         rcProvidesString = rpmGetVar(RPMVAR_PROVIDES);
    00413
    00414     if (rcProvidesString != NULL && !(Flags & RPMSENSE_SENSEMASK)) {
    00415
    00416         i = strlen(Name);
    00417         /*@-observertrans -mayaliasunique@*/
    00418         while ((start = strstr(rcProvidesString, Name))) {
    00419         /*@=observertrans =mayaliasunique@*/
    00420 /*@-boundsread@*/
    00421             if (xisspace(start[i]) || start[i] == '\0' || start[i] == ',') {
    00422                 rpmdsNotify(dep, _("(rpmrc provides)"), rc);
    00423                 goto exit;
    00424             }
    00425 /*@=boundsread@*/
    00426             rcProvidesString = start + 1;
    00427         }
    00428     }
    00429   }
    00430 #endif
    00431
    00432     /*
    00433      * New features in rpm packaging implicitly add versioned dependencies
    00434      * on rpmlib provides. The dependencies look like "rpmlib(YaddaYadda)".
    00435      * Check those dependencies now.
    00436      */
    00437     if (!strncmp(Name, "rpmlib(", sizeof("rpmlib(")-1)) {
    00438         if (rpmCheckRpmlibProvides(dep)) {
    00439             rpmdsNotify(dep, _("(rpmlib provides)"), rc);
    00440             goto exit;
    00441         }
    00442         goto unsatisfied;
    00443     }
    00444
    00445     /* Search added packages for the dependency. */
    00446     if (rpmalSatisfiesDepend(ts->addedPackages, dep, NULL) != NULL) {
    00447         /*
    00448          * XXX Ick, context sensitive answers from dependency cache.
    00449          * XXX Always resolve added dependencies within context to disambiguate.
    00450          */
    00451         if (_rpmds_nopromote)
    00452             _cacheThisRC = 0;
    00453         goto exit;
    00454     }
    00455
    00456     /* XXX only the installer does not have the database open here. */
    00457     if (rpmtsGetRdb(ts) != NULL) {
    00458 /*@-boundsread@*/
    00459         if (Name[0] == '/') {
    00460             /* depFlags better be 0! */
    00461
    00462             mi = rpmtsInitIterator(ts, RPMTAG_BASENAMES, Name, 0);
    00463
    00464             (void) rpmdbPruneIterator(mi,
    00465                         ts->removedPackages, ts->numRemovedPackages, 1);
    00466
    00467             while ((h = rpmdbNextIterator(mi)) != NULL) {
    00468                 rpmdsNotify(dep, _("(db files)"), rc);
    00469                 mi = rpmdbFreeIterator(mi);
    00470                 goto exit;
    00471             }
    00472             mi = rpmdbFreeIterator(mi);
    00473         }
    00474 /*@=boundsread@*/
    00475
    00476         mi = rpmtsInitIterator(ts, RPMTAG_PROVIDENAME, Name, 0);
    00477         (void) rpmdbPruneIterator(mi,
    00478                         ts->removedPackages, ts->numRemovedPackages, 1);
    00479         while ((h = rpmdbNextIterator(mi)) != NULL) {
    00480             if (rpmdsAnyMatchesDep(h, dep, _rpmds_nopromote)) {
    00481                 rpmdsNotify(dep, _("(db provides)"), rc);
    00482                 mi = rpmdbFreeIterator(mi);
    00483                 goto exit;
    00484             }
    00485         }
    00486         mi = rpmdbFreeIterator(mi);
    00487
    00488 #if defined(DYING) || defined(__LCLINT__)
    00489         mi = rpmtsInitIterator(ts, RPMTAG_NAME, Name, 0);
    00490         (void) rpmdbPruneIterator(mi,
    00491                         ts->removedPackages, ts->numRemovedPackages, 1);
    00492         while ((h = rpmdbNextIterator(mi)) != NULL) {
    00493             if (rpmdsAnyMatchesDep(h, dep, _rpmds_nopromote)) {
    00494                 rpmdsNotify(dep, _("(db package)"), rc);
    00495                 mi = rpmdbFreeIterator(mi);
    00496                 goto exit;
    00497             }
    00498         }
    00499         mi = rpmdbFreeIterator(mi);
    00500 #endif
    00501
    00502     }
    00503
    00504     /*
    00505      * Search for an unsatisfied dependency.
    00506      */
    00507 /*@-boundsread@*/
    00508     if (adding && !retrying && !(rpmtsFlags(ts) & RPMTRANS_FLAG_NOSUGGEST)) {
    00509         if (ts->solve != NULL) {
    00510             xx = (*ts->solve) (ts, dep, ts->solveData);
    00511             if (xx == 0)
    00512                 goto exit;
    00513             if (xx == -1) {
    00514                 retrying = 1;
    00515                 rpmalMakeIndex(ts->addedPackages);
    00516                 goto retry;
    00517             }
    00518         }
    00519     }
    00520 /*@=boundsread@*/
    00521
    00522 unsatisfied:
    00523     rc = 1;     /* dependency is unsatisfied */
    00524     rpmdsNotify(dep, NULL, rc);
    00525
    00526 exit:
    00527     /*
    00528      * If dbiOpen/dbiPut fails (e.g. permissions), we can't cache.
    00529      */
    00530     if (_cacheDependsRC && _cacheThisRC) {
    00531         dbiIndex dbi;
    00532         dbi = dbiOpen(rpmtsGetRdb(ts), RPMDBI_DEPENDS, 0);
    00533         if (dbi == NULL) {
    00534             _cacheDependsRC = 0;
    00535         } else {
    00536             const char * DNEVR;
    00537             xx = 0;
    00538             /*@-branchstate@*/
    00539             if ((DNEVR = rpmdsDNEVR(dep)) != NULL) {
    00540                 DBC * dbcursor = NULL;
    00541                 size_t DNEVRlen = strlen(DNEVR);
    00542
    00543                 xx = dbiCopen(dbi, dbi->dbi_txnid, &dbcursor, DB_WRITECURSOR);
    00544
    00545                 memset(key, 0, sizeof(*key));
    00546 /*@i@*/         key->data = (void *) DNEVR;
    00547                 key->size = DNEVRlen;
    00548                 memset(data, 0, sizeof(*data));
    00549                 data->data = &rc;
    00550                 data->size = sizeof(rc);
    00551
    00552                 /*@-compmempass@*/
    00553                 xx = dbiPut(dbi, dbcursor, key, data, 0);
    00554                 /*@=compmempass@*/
    00555                 xx = dbiCclose(dbi, dbcursor, DB_WRITECURSOR);
    00556             }
    00557             /*@=branchstate@*/
    00558             if (xx)
    00559                 _cacheDependsRC = 0;
    00560         }
    00561     }
    00562     return rc;
    00563 }
    00564
    00576 static int checkPackageDeps(rpmts ts, const char * pkgNEVR,
    00577                 /*@null@*/ rpmds requires, /*@null@*/ rpmds conflicts,
    00578                 /*@null@*/ const char * depName, uint_32 multiLib, int adding)
    00579         /*@globals rpmGlobalMacroContext,
    00580                 fileSystem, internalState @*/
    00581         /*@modifies ts, requires, conflicts, rpmGlobalMacroContext,
    00582                 fileSystem, internalState */
    00583 {
    00584     const char * Name;
    00585     int_32 Flags;
    00586     int rc;
    00587     int ourrc = 0;
    00588
    00589     requires = rpmdsInit(requires);
    00590     if (requires != NULL)
    00591     while (!ourrc && rpmdsNext(requires) >= 0) {
    00592
    00593         if ((Name = rpmdsN(requires)) == NULL)
    00594             continue;   /* XXX can't happen */
    00595
    00596         /* Filter out requires that came along for the ride. */
    00597         if (depName != NULL && strcmp(depName, Name))
    00598             continue;
    00599
    00600         Flags = rpmdsFlags(requires);
    00601
    00602         /* If this requirement comes from the core package only, not libraries,
    00603            then if we're installing the libraries only, don't count it in. */
    00604         if (multiLib && !isDependsMULTILIB(Flags))
    00605             continue;
    00606
    00607         rc = unsatisfiedDepend(ts, requires, adding);
    00608
    00609         switch (rc) {
    00610         case 0:         /* requirements are satisfied. */
    00611             /*@switchbreak@*/ break;
    00612         case 1:         /* requirements are not satisfied. */
    00613         {   fnpyKey * suggestedKeys = NULL;
    00614
    00615             /*@-branchstate@*/
    00616             if (ts->availablePackages != NULL) {
    00617                 suggestedKeys = rpmalAllSatisfiesDepend(ts->availablePackages,
    00618                                 requires, NULL);
    00619             }
    00620             /*@=branchstate@*/
    00621
    00622             rpmdsProblem(ts->probs, pkgNEVR, requires, suggestedKeys, adding);
    00623
    00624         }
    00625             /*@switchbreak@*/ break;
    00626         case 2:         /* something went wrong! */
    00627         default:
    00628             ourrc = 1;
    00629             /*@switchbreak@*/ break;
    00630         }
    00631     }
    00632
    00633     conflicts = rpmdsInit(conflicts);
    00634     if (conflicts != NULL)
    00635     while (!ourrc && rpmdsNext(conflicts) >= 0) {
    00636
    00637         if ((Name = rpmdsN(conflicts)) == NULL)
    00638             continue;   /* XXX can't happen */
    00639
    00640         /* Filter out conflicts that came along for the ride. */
    00641         if (depName != NULL && strcmp(depName, Name))
    00642             continue;
    00643
    00644         Flags = rpmdsFlags(conflicts);
    00645
    00646         /* If this requirement comes from the core package only, not libraries,
    00647            then if we're installing the libraries only, don't count it in. */
    00648         if (multiLib && !isDependsMULTILIB(Flags))
    00649             continue;
    00650
    00651         rc = unsatisfiedDepend(ts, conflicts, adding);
    00652
    00653         /* 1 == unsatisfied, 0 == satsisfied */
    00654         switch (rc) {
    00655         case 0:         /* conflicts exist. */
    00656             rpmdsProblem(ts->probs, pkgNEVR, conflicts, NULL, adding);
    00657             /*@switchbreak@*/ break;
    00658         case 1:         /* conflicts don't exist. */
    00659             /*@switchbreak@*/ break;
    00660         case 2:         /* something went wrong! */
    00661         default:
    00662             ourrc = 1;
    00663             /*@switchbreak@*/ break;
    00664         }
    00665     }
    00666
    00667     return ourrc;
    00668 }
    00669
    00680 static int checkPackageSet(rpmts ts, const char * dep,
    00681                 /*@only@*/ /*@null@*/ rpmdbMatchIterator mi, int adding)
    00682         /*@globals rpmGlobalMacroContext, fileSystem, internalState @*/
    00683         /*@modifies ts, mi, rpmGlobalMacroContext, fileSystem, internalState @*/
    00684 {
    00685     int scareMem = 1;
    00686     Header h;
    00687     int ec = 0;
    00688
    00689     (void) rpmdbPruneIterator(mi,
    00690                 ts->removedPackages, ts->numRemovedPackages, 1);
    00691     while ((h = rpmdbNextIterator(mi)) != NULL) {
    00692         const char * pkgNEVR;
    00693         rpmds requires, conflicts;
    00694         int rc;
    00695
    00696         pkgNEVR = hGetNEVR(h, NULL);
    00697         requires = rpmdsNew(h, RPMTAG_REQUIRENAME, scareMem);
    00698         (void) rpmdsSetNoPromote(requires, _rpmds_nopromote);
    00699         conflicts = rpmdsNew(h, RPMTAG_CONFLICTNAME, scareMem);
    00700         (void) rpmdsSetNoPromote(requires, _rpmds_nopromote);
    00701         rc = checkPackageDeps(ts, pkgNEVR, requires, conflicts, dep, 0, adding);
    00702         conflicts = rpmdsFree(conflicts);
    00703         requires = rpmdsFree(requires);
    00704         pkgNEVR = _free(pkgNEVR);
    00705
    00706         if (rc) {
    00707             ec = 1;
    00708             break;
    00709         }
    00710     }
    00711     mi = rpmdbFreeIterator(mi);
    00712
    00713     return ec;
    00714 }
    00715
    00722 static int checkDependentPackages(rpmts ts, const char * dep)
    00723         /*@globals rpmGlobalMacroContext, fileSystem, internalState @*/
    00724         /*@modifies ts, rpmGlobalMacroContext, fileSystem, internalState @*/
    00725 {
    00726     rpmdbMatchIterator mi;
    00727     mi = rpmtsInitIterator(ts, RPMTAG_REQUIRENAME, dep, 0);
    00728     return checkPackageSet(ts, dep, mi, 0);
    00729 }
    00730
    00737 static int checkDependentConflicts(rpmts ts, const char * dep)
    00738         /*@globals rpmGlobalMacroContext, fileSystem, internalState @*/
    00739         /*@modifies ts, rpmGlobalMacroContext, fileSystem, internalState @*/
    00740 {
    00741     int rc = 0;
    00742
    00743     if (rpmtsGetRdb(ts) != NULL) {      /* XXX is this necessary? */
    00744         rpmdbMatchIterator mi;
    00745         mi = rpmtsInitIterator(ts, RPMTAG_CONFLICTNAME, dep, 0);
    00746         rc = checkPackageSet(ts, dep, mi, 1);
    00747     }
    00748
    00749     return rc;
    00750 }
    00751
    00752 struct badDeps_s {
    00753 /*@observer@*/ /*@owned@*/ /*@null@*/
    00754     const char * pname;
    00755 /*@observer@*/ /*@dependent@*/ /*@null@*/
    00756     const char * qname;
    00757 };
    00758
    00759 #ifdef REFERENCE
    00760 static struct badDeps_s {
    00761 /*@observer@*/ /*@null@*/ const char * pname;
    00762 /*@observer@*/ /*@null@*/ const char * qname;
    00763 } badDeps[] = {
    00764     { "libtermcap", "bash" },
    00765     { "modutils", "vixie-cron" },
    00766     { "ypbind", "yp-tools" },
    00767     { "ghostscript-fonts", "ghostscript" },
    00768     /* 7.2 only */
    00769     { "libgnomeprint15", "gnome-print" },
    00770     { "nautilus", "nautilus-mozilla" },
    00771     /* 7.1 only */
    00772     { "arts", "kdelibs-sound" },
    00773     /* 7.0 only */
    00774     { "pango-gtkbeta-devel", "pango-gtkbeta" },
    00775     { "XFree86", "Mesa" },
    00776     { "compat-glibc", "db2" },
    00777     { "compat-glibc", "db1" },
    00778     { "pam", "initscripts" },
    00779     { "initscripts", "sysklogd" },
    00780     /* 6.2 */
    00781     { "egcs-c++", "libstdc++" },
    00782     /* 6.1 */
    00783     { "pilot-link-devel", "pilot-link" },
    00784     /* 5.2 */
    00785     { "pam", "pamconfig" },
    00786     { NULL, NULL }
    00787 };
    00788 #else
    00789 /*@unchecked@*/
    00790 static int badDepsInitialized = 0;
    00791
    00792 /*@unchecked@*/ /*@only@*/ /*@null@*/
    00793 static struct badDeps_s * badDeps = NULL;
    00794 #endif
    00795
    00798 /*@-modobserver -observertrans @*/
    00799 static void freeBadDeps(void)
    00800         /*@globals badDeps, badDepsInitialized @*/
    00801         /*@modifies badDeps, badDepsInitialized @*/
    00802 {
    00803     if (badDeps) {
    00804         struct badDeps_s * bdp;
    00805         for (bdp = badDeps; bdp->pname != NULL && bdp->qname != NULL; bdp++)
    00806             bdp->pname = _free(bdp->pname);
    00807         badDeps = _free(badDeps);
    00808     }
    00809     badDepsInitialized = 0;
    00810 }
    00811 /*@=modobserver =observertrans @*/
    00812
    00820 /*@-boundsread@*/
    00821 static int ignoreDep(const rpmte p, const rpmte q)
    00822         /*@globals badDeps, badDepsInitialized @*/
    00823         /*@modifies badDeps, badDepsInitialized @*/
    00824 {
    00825     struct badDeps_s * bdp;
    00826
    00827 /*@-globs -mods@*/
    00828     if (!badDepsInitialized) {
    00829         char * s = rpmExpand("%{?_dependency_whiteout}", NULL);
    00830         const char ** av = NULL;
    00831         int ac = 0;
    00832         int i;
    00833
    00834         if (s != NULL && *s != '\0'
    00835         && !(i = poptParseArgvString(s, &ac, (const char ***)&av))
    00836         && ac > 0 && av != NULL)
    00837         {
    00838             bdp = badDeps = xcalloc(ac+1, sizeof(*badDeps));
    00839             for (i = 0; i < ac; i++, bdp++) {
    00840                 char * pname, * qname;
    00841
    00842                 if (av[i] == NULL)
    00843                     break;
    00844                 pname = xstrdup(av[i]);
    00845                 if ((qname = strchr(pname, '>')) != NULL)
    00846                     *qname++ = '\0';
    00847                 bdp->pname = pname;
    00848                 /*@-usereleased@*/
    00849                 bdp->qname = qname;
    00850                 /*@=usereleased@*/
    00851                 rpmMessage(RPMMESS_DEBUG,
    00852                         _("ignore package name relation(s) [%d]\t%s -> %s\n"),
    00853                         i, bdp->pname, (bdp->qname ? bdp->qname : "???"));
    00854             }
    00855             bdp->pname = NULL;
    00856             bdp->qname = NULL;
    00857         }
    00858         av = _free(av);
    00859         s = _free(s);
    00860         badDepsInitialized++;
    00861     }
    00862 /*@=globs =mods@*/
    00863
    00864     /*@-compdef@*/
    00865     if (badDeps != NULL)
    00866     for (bdp = badDeps; bdp->pname != NULL && bdp->qname != NULL; bdp++) {
    00867         if (!strcmp(rpmteN(p), bdp->pname) && !strcmp(rpmteN(q), bdp->qname))
    00868             return 1;
    00869     }
    00870     return 0;
    00871     /*@=compdef@*/
    00872 }
    00873 /*@=boundsread@*/
    00874
    00880 static void markLoop(/*@special@*/ tsortInfo tsi, rpmte q)
    00881         /*@globals internalState @*/
    00882         /*@uses tsi @*/
    00883         /*@modifies internalState @*/
    00884 {
    00885     rpmte p;
    00886
    00887     /*@-branchstate@*/ /* FIX: q is kept */
    00888     while (tsi != NULL && (p = tsi->tsi_suc) != NULL) {
    00889         tsi = tsi->tsi_next;
    00890         if (rpmteTSI(p)->tsi_chain != NULL)
    00891             continue;
    00892         /*@-assignexpose -temptrans@*/
    00893         rpmteTSI(p)->tsi_chain = q;
    00894         /*@=assignexpose =temptrans@*/
    00895         if (rpmteTSI(p)->tsi_next != NULL)
    00896             markLoop(rpmteTSI(p)->tsi_next, p);
    00897     }
    00898     /*@=branchstate@*/
    00899 }
    00900
    00901 static inline /*@observer@*/ const char * const identifyDepend(int_32 f)
    00902         /*@*/
    00903 {
    00904     if (isLegacyPreReq(f))
    00905         return "PreReq:";
    00906     f = _notpre(f);
    00907     if (f & RPMSENSE_SCRIPT_PRE)
    00908         return "Requires(pre):";
    00909     if (f & RPMSENSE_SCRIPT_POST)
    00910         return "Requires(post):";
    00911     if (f & RPMSENSE_SCRIPT_PREUN)
    00912         return "Requires(preun):";
    00913     if (f & RPMSENSE_SCRIPT_POSTUN)
    00914         return "Requires(postun):";
    00915     if (f & RPMSENSE_SCRIPT_VERIFY)
    00916         return "Requires(verify):";
    00917     if (f & RPMSENSE_FIND_REQUIRES)
    00918         return "Requires(auto):";
    00919     return "Requires:";
    00920 }
    00921
    00934 /*@-boundswrite@*/
    00935 /*@-mustmod@*/ /* FIX: hack modifies, but -type disables */
    00936 static /*@owned@*/ /*@null@*/ const char *
    00937 zapRelation(rpmte q, rpmte p,
    00938                 /*@null@*/ rpmds requires,
    00939                 int zap, /*@in@*/ /*@out@*/ int * nzaps)
    00940         /*@modifies q, p, requires, *nzaps @*/
    00941 {
    00942     tsortInfo tsi_prev;
    00943     tsortInfo tsi;
    00944     const char *dp = NULL;
    00945
    00946     for (tsi_prev = rpmteTSI(q), tsi = rpmteTSI(q)->tsi_next;
    00947          tsi != NULL;
    00948         /* XXX Note: the loop traverses "not found", break on "found". */
    00949         /*@-nullderef@*/
    00950          tsi_prev = tsi, tsi = tsi->tsi_next)
    00951         /*@=nullderef@*/
    00952     {
    00953         int_32 Flags;
    00954
    00955         /*@-abstract@*/
    00956         if (tsi->tsi_suc != p)
    00957             continue;
    00958         /*@=abstract@*/
    00959
    00960         if (requires == NULL) continue;         /* XXX can't happen */
    00961
    00962         (void) rpmdsSetIx(requires, tsi->tsi_reqx);
    00963
    00964         Flags = rpmdsFlags(requires);
    00965
    00966         dp = rpmdsNewDNEVR( identifyDepend(Flags), requires);
    00967
    00968         /*
    00969          * Attempt to unravel a dependency loop by eliminating Requires's.
    00970          */
    00971         /*@-branchstate@*/
    00972         if (zap && !(Flags & RPMSENSE_PREREQ)) {
    00973             rpmMessage(RPMMESS_DEBUG,
    00974                         _("removing %s \"%s\" from tsort relations.\n"),
    00975                         (rpmteNEVR(p) ?  rpmteNEVR(p) : "???"), dp);
    00976             rpmteTSI(p)->tsi_count--;
    00977             if (tsi_prev) tsi_prev->tsi_next = tsi->tsi_next;
    00978             tsi->tsi_next = NULL;
    00979             tsi->tsi_suc = NULL;
    00980             tsi = _free(tsi);
    00981             if (nzaps)
    00982                 (*nzaps)++;
    00983             if (zap)
    00984                 zap--;
    00985         }
    00986         /*@=branchstate@*/
    00987         /* XXX Note: the loop traverses "not found", get out now! */
    00988         break;
    00989     }
    00990     return dp;
    00991 }
    00992 /*@=mustmod@*/
    00993 /*@=boundswrite@*/
    00994
    01003 /*@-mustmod@*/
    01004 static inline int addRelation(rpmts ts,
    01005                 /*@dependent@*/ rpmte p,
    01006                 unsigned char * selected,
    01007                 rpmds requires)
    01008         /*@globals fileSystem @*/
    01009         /*@modifies ts, p, *selected, fileSystem @*/
    01010 {
    01011     rpmtsi qi; rpmte q;
    01012     tsortInfo tsi;
    01013     const char * Name;
    01014     fnpyKey key;
    01015     alKey pkgKey;
    01016     int i = 0;
    01017
    01018     if ((Name = rpmdsN(requires)) == NULL)
    01019         return 0;       /* XXX can't happen */
    01020
    01021     /* Avoid rpmlib feature dependencies. */
    01022     if (!strncmp(Name, "rpmlib(", sizeof("rpmlib(")-1))
    01023         return 0;
    01024
    01025     pkgKey = RPMAL_NOMATCH;
    01026     key = rpmalSatisfiesDepend(ts->addedPackages, requires, &pkgKey);
    01027
    01028     /* Ordering depends only on added package relations. */
    01029     if (pkgKey == RPMAL_NOMATCH)
    01030         return 0;
    01031
    01032 /* XXX Set q to the added package that has pkgKey == q->u.addedKey */
    01033 /* XXX FIXME: bsearch is possible/needed here */
    01034     for (qi = rpmtsiInit(ts), i = 0; (q = rpmtsiNext(qi, 0)) != NULL; i++) {
    01035
    01036         /* XXX Only added packages need be checked for matches. */
    01037         if (rpmteType(q) == TR_REMOVED)
    01038             continue;
    01039
    01040         if (pkgKey == rpmteAddedKey(q))
    01041             break;
    01042     }
    01043     qi = rpmtsiFree(qi);
    01044     if (q == NULL || i == ts->orderCount)
    01045         return 0;
    01046
    01047     /* Avoid certain dependency relations. */
    01048     if (ignoreDep(p, q))
    01049         return 0;
    01050
    01051     /* Avoid redundant relations. */
    01052     /* XXX TODO: add control bit. */
    01053 /*@-boundsread@*/
    01054     if (selected[i] != 0)
    01055         return 0;
    01056 /*@=boundsread@*/
    01057 /*@-boundswrite@*/
    01058     selected[i] = 1;
    01059 /*@=boundswrite@*/
    01060
    01061     /* T3. Record next "q <- p" relation (i.e. "p" requires "q"). */
    01062     rpmteTSI(p)->tsi_count++;                   /* bump p predecessor count */
    01063
    01064     if (rpmteDepth(p) <= rpmteDepth(q)) /* Save max. depth in dependency tree */
    01065         (void) rpmteSetDepth(p, (rpmteDepth(q) + 1));
    01066
    01067     tsi = xcalloc(1, sizeof(*tsi));
    01068     tsi->tsi_suc = p;
    01069
    01070     tsi->tsi_reqx = rpmdsIx(requires);
    01071
    01072     tsi->tsi_next = rpmteTSI(q)->tsi_next;
    01073 /*@-mods@*/
    01074     rpmteTSI(q)->tsi_next = tsi;
    01075     rpmteTSI(q)->tsi_qcnt++;                    /* bump q successor count */
    01076 /*@=mods@*/
    01077     return 0;
    01078 }
    01079 /*@=mustmod@*/
    01080
    01087 static int orderListIndexCmp(const void * one, const void * two)        /*@*/
    01088 {
    01089     /*@-castexpose@*/
    01090     long a = (long) ((const orderListIndex)one)->pkgKey;
    01091     long b = (long) ((const orderListIndex)two)->pkgKey;
    01092     /*@=castexpose@*/
    01093     return (a - b);
    01094 }
    01095
    01102 /*@-boundswrite@*/
    01103 /*@-mustmod@*/
    01104 static void addQ(/*@dependent@*/ rpmte p,
    01105                 /*@in@*/ /*@out@*/ rpmte * qp,
    01106                 /*@in@*/ /*@out@*/ rpmte * rp)
    01107         /*@modifies p, *qp, *rp @*/
    01108 {
    01109     rpmte q, qprev;
    01110
    01111     /* Mark the package as queued. */
    01112     rpmteTSI(p)->tsi_reqx = 1;
    01113
    01114     if ((*rp) == NULL) {        /* 1st element */
    01115         /*@-dependenttrans@*/ /* FIX: double indirection */
    01116         (*rp) = (*qp) = p;
    01117         /*@=dependenttrans@*/
    01118         return;
    01119     }
    01120
    01121     /* Find location in queue using metric tsi_qcnt. */
    01122     for (qprev = NULL, q = (*qp);
    01123          q != NULL;
    01124          qprev = q, q = rpmteTSI(q)->tsi_suc)
    01125     {
    01126         if (rpmteTSI(q)->tsi_qcnt <= rpmteTSI(p)->tsi_qcnt)
    01127             break;
    01128     }
    01129
    01130     if (qprev == NULL) {        /* insert at beginning of list */
    01131         rpmteTSI(p)->tsi_suc = q;
    01132         /*@-dependenttrans@*/
    01133         (*qp) = p;              /* new head */
    01134         /*@=dependenttrans@*/
    01135     } else if (q == NULL) {     /* insert at end of list */
    01136         rpmteTSI(qprev)->tsi_suc = p;
    01137         /*@-dependenttrans@*/
    01138         (*rp) = p;              /* new tail */
    01139         /*@=dependenttrans@*/
    01140     } else {                    /* insert between qprev and q */
    01141         rpmteTSI(p)->tsi_suc = q;
    01142         rpmteTSI(qprev)->tsi_suc = p;
    01143     }
    01144 }
    01145 /*@=mustmod@*/
    01146 /*@=boundswrite@*/
    01147
    01148 /*@-bounds@*/
    01149 int rpmtsOrder(rpmts ts)
    01150 {
    01151     rpmds requires;
    01152     int_32 Flags;
    01153
    01154 #ifdef  DYING
    01155     int chainsaw = rpmtsFlags(ts) & RPMTRANS_FLAG_CHAINSAW;
    01156 #else
    01157     int chainsaw = 1;
    01158 #endif
    01159     rpmtsi pi; rpmte p;
    01160     rpmtsi qi; rpmte q;
    01161     rpmtsi ri; rpmte r;
    01162     tsortInfo tsi;
    01163     tsortInfo tsi_next;
    01164     alKey * ordering;
    01165     int orderingCount = 0;
    01166     unsigned char * selected = alloca(sizeof(*selected) * (ts->orderCount + 1));
    01167     int loopcheck;
    01168     rpmte * newOrder;
    01169     int newOrderCount = 0;
    01170     orderListIndex orderList;
    01171     int numOrderList;
    01172     int nrescans = 10;
    01173     int _printed = 0;
    01174     char deptypechar;
    01175 #ifdef  DYING
    01176     int oType = TR_ADDED;
    01177 #else
    01178     int oType = 0;
    01179 #endif
    01180     int treex;
    01181     int depth;
    01182     int qlen;
    01183     int i, j;
    01184
    01185 #ifdef  DYING
    01186     rpmalMakeIndex(ts->addedPackages);
    01187 #endif
    01188
    01189     /* T1. Initialize. */
    01190     if (oType == 0)
    01191         numOrderList = ts->orderCount;
    01192     else {
    01193         numOrderList = 0;
    01194         if (oType & TR_ADDED)
    01195             numOrderList += ts->numAddedPackages;
    01196         if (oType & TR_REMOVED)
    01197             numOrderList += ts->numRemovedPackages;
    01198      }
    01199     ordering = alloca(sizeof(*ordering) * (numOrderList + 1));
    01200     loopcheck = numOrderList;
    01201
    01202     pi = rpmtsiInit(ts);
    01203     while ((p = rpmtsiNext(pi, oType)) != NULL)
    01204         rpmteNewTSI(p);
    01205     pi = rpmtsiFree(pi);
    01206
    01207     /* Record all relations. */
    01208     rpmMessage(RPMMESS_DEBUG, _("========== recording tsort relations\n"));
    01209     pi = rpmtsiInit(ts);
    01210     /* XXX Only added packages are ordered (for now). */
    01211     while ((p = rpmtsiNext(pi, oType)) != NULL) {
    01212
    01213         if ((requires = rpmteDS(p, RPMTAG_REQUIRENAME)) == NULL)
    01214             continue;
    01215
    01216         memset(selected, 0, sizeof(*selected) * ts->orderCount);
    01217
    01218         /* Avoid narcisstic relations. */
    01219         selected[rpmtsiOc(pi)] = 1;
    01220
    01221         /* T2. Next "q <- p" relation. */
    01222
    01223         /* First, do pre-requisites. */
    01224         requires = rpmdsInit(requires);
    01225         if (requires != NULL)
    01226         while (rpmdsNext(requires) >= 0) {
    01227
    01228             Flags = rpmdsFlags(requires);
    01229
    01230             switch (rpmteType(p)) {
    01231             case TR_REMOVED:
    01232                 /* Skip if not %preun/%postun requires or legacy prereq. */
    01233                 if (isInstallPreReq(Flags)
    01234                  || !( isErasePreReq(Flags)
    01235                     || isLegacyPreReq(Flags) )
    01236                     )
    01237                     /*@innercontinue@*/ continue;
    01238                 /*@switchbreak@*/ break;
    01239             case TR_ADDED:
    01240                 /* Skip if not %pre/%post requires or legacy prereq. */
    01241                 if (isErasePreReq(Flags)
    01242                  || !( isInstallPreReq(Flags)
    01243                     || isLegacyPreReq(Flags) )
    01244                     )
    01245                     /*@innercontinue@*/ continue;
    01246                 /*@switchbreak@*/ break;
    01247             }
    01248
    01249             /* T3. Record next "q <- p" relation (i.e. "p" requires "q"). */
    01250             (void) addRelation(ts, p, selected, requires);
    01251
    01252         }
    01253
    01254         /* Then do co-requisites. */
    01255         requires = rpmdsInit(requires);
    01256         if (requires != NULL)
    01257         while (rpmdsNext(requires) >= 0) {
    01258
    01259             Flags = rpmdsFlags(requires);
    01260
    01261             switch (rpmteType(p)) {
    01262             case TR_REMOVED:
    01263                 /* Skip if %preun/%postun requires or legacy prereq. */
    01264                 if (isInstallPreReq(Flags)
    01265                  ||  ( isErasePreReq(Flags)
    01266                     || isLegacyPreReq(Flags) )
    01267                     )
    01268                     /*@innercontinue@*/ continue;
    01269                 /*@switchbreak@*/ break;
    01270             case TR_ADDED:
    01271                 /* Skip if %pre/%post requires or legacy prereq. */
    01272                 if (isErasePreReq(Flags)
    01273                  ||  ( isInstallPreReq(Flags)
    01274                     || isLegacyPreReq(Flags) )
    01275                     )
    01276                     /*@innercontinue@*/ continue;
    01277                 /*@switchbreak@*/ break;
    01278             }
    01279
    01280             /* T3. Record next "q <- p" relation (i.e. "p" requires "q"). */
    01281             (void) addRelation(ts, p, selected, requires);
    01282
    01283         }
    01284     }
    01285     pi = rpmtsiFree(pi);
    01286
    01287     /* Save predecessor count and mark tree roots. */
    01288     treex = 0;
    01289     pi = rpmtsiInit(ts);
    01290     while ((p = rpmtsiNext(pi, oType)) != NULL) {
    01291         int npreds;
    01292
    01293         npreds = rpmteTSI(p)->tsi_count;
    01294
    01295         (void) rpmteSetNpreds(p, npreds);
    01296
    01297         if (npreds == 0)
    01298             (void) rpmteSetTree(p, treex++);
    01299         else
    01300             (void) rpmteSetTree(p, -1);
    01301 #ifdef  UNNECESSARY
    01302         (void) rpmteSetParent(p, NULL);
    01303 #endif
    01304
    01305     }
    01306     pi = rpmtsiFree(pi);
    01307
    01308     /* T4. Scan for zeroes. */
    01309     rpmMessage(RPMMESS_DEBUG, _("========== tsorting packages (order, #predecessors, #succesors, tree, depth)\n"));
    01310
    01311 rescan:
    01312     if (pi != NULL) pi = rpmtsiFree(pi);
    01313     q = r = NULL;
    01314     qlen = 0;
    01315     pi = rpmtsiInit(ts);
    01316     while ((p = rpmtsiNext(pi, oType)) != NULL) {
    01317
    01318         /* Prefer packages in chainsaw or presentation order. */
    01319         if (!chainsaw)
    01320             rpmteTSI(p)->tsi_qcnt = (ts->orderCount - rpmtsiOc(pi));
    01321
    01322         if (rpmteTSI(p)->tsi_count != 0)
    01323             continue;
    01324         rpmteTSI(p)->tsi_suc = NULL;
    01325         addQ(p, &q, &r);
    01326         qlen++;
    01327     }
    01328     pi = rpmtsiFree(pi);
    01329
    01330     /* T5. Output front of queue (T7. Remove from queue.) */
    01331     for (; q != NULL; q = rpmteTSI(q)->tsi_suc) {
    01332
    01333         /* Mark the package as unqueued. */
    01334         rpmteTSI(q)->tsi_reqx = 0;
    01335
    01336         if (oType != 0)
    01337         switch (rpmteType(q)) {
    01338         case TR_ADDED:
    01339             if (!(oType & TR_ADDED))
    01340                 continue;
    01341             /*@switchbreak@*/ break;
    01342         case TR_REMOVED:
    01343             if (!(oType & TR_REMOVED))
    01344                 continue;
    01345             /*@switchbreak@*/ break;
    01346         default:
    01347             continue;
    01348             /*@notreached@*/ /*@switchbreak@*/ break;
    01349         }
    01350         deptypechar = (rpmteType(q) == TR_REMOVED ? '-' : '+');
    01351
    01352         rpmMessage(RPMMESS_DEBUG, "%5d%5d%5d%5d%5d %*s%c%s\n",
    01353                         orderingCount, rpmteNpreds(q),
    01354                         rpmteTSI(q)->tsi_qcnt, rpmteTree(q), rpmteDepth(q),
    01355                         (2 * rpmteDepth(q)), "",
    01356                         deptypechar,
    01357                         (rpmteNEVR(q) ? rpmteNEVR(q) : "???"));
    01358
    01359         treex = rpmteTree(q);
    01360         depth = rpmteDepth(q);
    01361         (void) rpmteSetDegree(q, 0);
    01362
    01363         ordering[orderingCount] = rpmteAddedKey(q);
    01364         orderingCount++;
    01365         qlen--;
    01366         loopcheck--;
    01367
    01368         /* T6. Erase relations. */
    01369         tsi_next = rpmteTSI(q)->tsi_next;
    01370         rpmteTSI(q)->tsi_next = NULL;
    01371         while ((tsi = tsi_next) != NULL) {
    01372             tsi_next = tsi->tsi_next;
    01373             tsi->tsi_next = NULL;
    01374             p = tsi->tsi_suc;
    01375             if (p && (--rpmteTSI(p)->tsi_count) <= 0) {
    01376
    01377                 (void) rpmteSetTree(p, treex);
    01378                 (void) rpmteSetDepth(p, depth+1);
    01379                 (void) rpmteSetParent(p, q);
    01380                 (void) rpmteSetDegree(q, rpmteDegree(q)+1);
    01381
    01382                 /* XXX TODO: add control bit. */
    01383                 rpmteTSI(p)->tsi_suc = NULL;
    01384                 addQ(p, &rpmteTSI(q)->tsi_suc, &r);
    01385                 qlen++;
    01386             }
    01387             tsi = _free(tsi);
    01388         }
    01389         if (!_printed && loopcheck == qlen && rpmteTSI(q)->tsi_suc != NULL) {
    01390             _printed++;
    01391             (void) rpmtsUnorderedSuccessors(ts, orderingCount);
    01392             rpmMessage(RPMMESS_DEBUG,
    01393                 _("========== successors only (presentation order)\n"));
    01394
    01395             /* Relink the queue in presentation order. */
    01396             tsi = rpmteTSI(q);
    01397             pi = rpmtsiInit(ts);
    01398             while ((p = rpmtsiNext(pi, oType)) != NULL) {
    01399                 /* Is this element in the queue? */
    01400                 if (rpmteTSI(p)->tsi_reqx == 0)
    01401                     /*@innercontinue@*/ continue;
    01402                 tsi->tsi_suc = p;
    01403                 tsi = rpmteTSI(p);
    01404             }
    01405             pi = rpmtsiFree(pi);
    01406             tsi->tsi_suc = NULL;
    01407         }
    01408     }
    01409
    01410     /* T8. End of process. Check for loops. */
    01411     if (loopcheck != 0) {
    01412         int nzaps;
    01413
    01414         /* T9. Initialize predecessor chain. */
    01415         nzaps = 0;
    01416         qi = rpmtsiInit(ts);
    01417         while ((q = rpmtsiNext(qi, oType)) != NULL) {
    01418             rpmteTSI(q)->tsi_chain = NULL;
    01419             rpmteTSI(q)->tsi_reqx = 0;
    01420             /* Mark packages already sorted. */
    01421             if (rpmteTSI(q)->tsi_count == 0)
    01422                 rpmteTSI(q)->tsi_count = -1;
    01423         }
    01424         qi = rpmtsiFree(qi);
    01425
    01426         /* T10. Mark all packages with their predecessors. */
    01427         qi = rpmtsiInit(ts);
    01428         while ((q = rpmtsiNext(qi, oType)) != NULL) {
    01429             if ((tsi = rpmteTSI(q)->tsi_next) == NULL)
    01430                 continue;
    01431             rpmteTSI(q)->tsi_next = NULL;
    01432             markLoop(tsi, q);
    01433             rpmteTSI(q)->tsi_next = tsi;
    01434         }
    01435         qi = rpmtsiFree(qi);
    01436
    01437         /* T11. Print all dependency loops. */
    01438         ri = rpmtsiInit(ts);
    01439         while ((r = rpmtsiNext(ri, oType)) != NULL)
    01440         {
    01441             int printed;
    01442
    01443             printed = 0;
    01444
    01445             /* T12. Mark predecessor chain, looking for start of loop. */
    01446             for (q = rpmteTSI(r)->tsi_chain; q != NULL;
    01447                  q = rpmteTSI(q)->tsi_chain)
    01448             {
    01449                 if (rpmteTSI(q)->tsi_reqx)
    01450                     /*@innerbreak@*/ break;
    01451                 rpmteTSI(q)->tsi_reqx = 1;
    01452             }
    01453
    01454             /* T13. Print predecessor chain from start of loop. */
    01455             while ((p = q) != NULL && (q = rpmteTSI(p)->tsi_chain) != NULL) {
    01456                 const char * dp;
    01457                 char buf[4096];
    01458
    01459                 /* Unchain predecessor loop. */
    01460                 rpmteTSI(p)->tsi_chain = NULL;
    01461
    01462                 if (!printed) {
    01463                     rpmMessage(RPMMESS_DEBUG, _("LOOP:\n"));
    01464                     printed = 1;
    01465                 }
    01466
    01467                 /* Find (and destroy if co-requisite) "q <- p" relation. */
    01468                 requires = rpmteDS(p, RPMTAG_REQUIRENAME);
    01469                 requires = rpmdsInit(requires);
    01470                 if (requires == NULL)
    01471                     /*@innercontinue@*/ continue;       /* XXX can't happen */
    01472                 dp = zapRelation(q, p, requires, 1, &nzaps);
    01473
    01474                 /* Print next member of loop. */
    01475                 buf[0] = '\0';
    01476                 if (rpmteNEVR(p) != NULL)
    01477                     (void) stpcpy(buf, rpmteNEVR(p));
    01478                 rpmMessage(RPMMESS_DEBUG, "    %-40s %s\n", buf,
    01479                         (dp ? dp : "not found!?!"));
    01480
    01481                 dp = _free(dp);
    01482             }
    01483
    01484             /* Walk (and erase) linear part of predecessor chain as well. */
    01485             for (p = r, q = rpmteTSI(r)->tsi_chain; q != NULL;
    01486                  p = q, q = rpmteTSI(q)->tsi_chain)
    01487             {
    01488                 /* Unchain linear part of predecessor loop. */
    01489                 rpmteTSI(p)->tsi_chain = NULL;
    01490                 rpmteTSI(p)->tsi_reqx = 0;
    01491             }
    01492         }
    01493         ri = rpmtsiFree(ri);
    01494
    01495         /* If a relation was eliminated, then continue sorting. */
    01496         /* XXX TODO: add control bit. */
    01497         if (nzaps && nrescans-- > 0) {
    01498             rpmMessage(RPMMESS_DEBUG, _("========== continuing tsort ...\n"));
    01499             goto rescan;
    01500         }
    01501
    01502         /* Return no. of packages that could not be ordered. */
    01503         rpmMessage(RPMMESS_ERROR, _("rpmtsOrder failed, %d elements remain\n"),
    01504                         loopcheck);
    01505         return loopcheck;
    01506     }
    01507
    01508     /* Clean up tsort remnants (if any). */
    01509     pi = rpmtsiInit(ts);
    01510     while ((p = rpmtsiNext(pi, 0)) != NULL)
    01511         rpmteFreeTSI(p);
    01512     pi = rpmtsiFree(pi);
    01513
    01514     /*
    01515      * The order ends up as installed packages followed by removed packages,
    01516      * with removes for upgrades immediately following the installation of
    01517      * the new package. This would be easier if we could sort the
    01518      * addedPackages array, but we store indexes into it in various places.
    01519      */
    01520     orderList = xcalloc(numOrderList, sizeof(*orderList));
    01521     j = 0;
    01522     pi = rpmtsiInit(ts);
    01523     while ((p = rpmtsiNext(pi, oType)) != NULL) {
    01524         /* Prepare added package ordering permutation. */
    01525         switch (rpmteType(p)) {
    01526         case TR_ADDED:
    01527             orderList[j].pkgKey = rpmteAddedKey(p);
    01528             /*@switchbreak@*/ break;
    01529         case TR_REMOVED:
    01530             orderList[j].pkgKey = RPMAL_NOMATCH;
    01531             /*@switchbreak@*/ break;
    01532         }
    01533         orderList[j].orIndex = rpmtsiOc(pi);
    01534         j++;
    01535     }
    01536     pi = rpmtsiFree(pi);
    01537
    01538     qsort(orderList, numOrderList, sizeof(*orderList), orderListIndexCmp);
    01539
    01540 /*@-type@*/
    01541     newOrder = xcalloc(ts->orderCount, sizeof(*newOrder));
    01542 /*@=type@*/
    01543     /*@-branchstate@*/
    01544     for (i = 0, newOrderCount = 0; i < orderingCount; i++)
    01545     {
    01546         struct orderListIndex_s key;
    01547         orderListIndex needle;
    01548
    01549         key.pkgKey = ordering[i];
    01550         needle = bsearch(&key, orderList, numOrderList,
    01551                                 sizeof(key), orderListIndexCmp);
    01552         /* bsearch should never, ever fail */
    01553         if (needle == NULL)
    01554             continue;
    01555
    01556         j = needle->orIndex;
    01557         if ((q = ts->order[j]) == NULL)
    01558             continue;
    01559
    01560         newOrder[newOrderCount++] = q;
    01561         ts->order[j] = NULL;
    01562         if (!chainsaw)
    01563         for (j = needle->orIndex + 1; j < ts->orderCount; j++) {
    01564             if ((q = ts->order[j]) == NULL)
    01565                 /*@innerbreak@*/ break;
    01566             if (rpmteType(q) == TR_REMOVED
    01567              && rpmteDependsOnKey(q) == needle->pkgKey)
    01568             {
    01569                 newOrder[newOrderCount++] = q;
    01570                 ts->order[j] = NULL;
    01571             } else
    01572                 /*@innerbreak@*/ break;
    01573         }
    01574     }
    01575     /*@=branchstate@*/
    01576
    01577     for (j = 0; j < ts->orderCount; j++) {
    01578         if ((p = ts->order[j]) == NULL)
    01579             continue;
    01580         newOrder[newOrderCount++] = p;
    01581         ts->order[j] = NULL;
    01582     }
    01583 assert(newOrderCount == ts->orderCount);
    01584
    01585 /*@+voidabstract@*/
    01586     ts->order = _free(ts->order);
    01587 /*@=voidabstract@*/
    01588     ts->order = newOrder;
    01589     ts->orderAlloced = ts->orderCount;
    01590     orderList = _free(orderList);
    01591
    01592 #ifdef  DYING   /* XXX now done at the CLI level just before rpmtsRun(). */
    01593     rpmtsClean(ts);
    01594 #endif
    01595     freeBadDeps();
    01596
    01597     return 0;
    01598 }
    01599 /*@=bounds@*/
    01600
    01601 int rpmtsCheck(rpmts ts)
    01602 {
    01603     rpmdbMatchIterator mi = NULL;
    01604     rpmtsi pi = NULL; rpmte p;
    01605     int closeatexit = 0;
    01606     int xx;
    01607     int rc;
    01608
    01609     /* Do lazy, readonly, open of rpm database. */
    01610     if (rpmtsGetRdb(ts) == NULL && ts->dbmode != -1) {
    01611         if ((rc = rpmtsOpenDB(ts, ts->dbmode)) != 0)
    01612             goto exit;
    01613         closeatexit = 1;
    01614     }
    01615
    01616     ts->probs = rpmpsFree(ts->probs);
    01617     ts->probs = rpmpsCreate();
    01618
    01619     rpmalMakeIndex(ts->addedPackages);
    01620
    01621     /*
    01622      * Look at all of the added packages and make sure their dependencies
    01623      * are satisfied.
    01624      */
    01625     pi = rpmtsiInit(ts);
    01626     while ((p = rpmtsiNext(pi, TR_ADDED)) != NULL) {
    01627         rpmds provides;
    01628
    01629         rpmMessage(RPMMESS_DEBUG,  "========== +++ %s\n" , rpmteNEVR(p));
    01630         rc = checkPackageDeps(ts, rpmteNEVR(p),
    01631                         rpmteDS(p, RPMTAG_REQUIRENAME),
    01632                         rpmteDS(p, RPMTAG_CONFLICTNAME),
    01633                         NULL,
    01634                         rpmteMultiLib(p), 1);
    01635         if (rc)
    01636             goto exit;
    01637
    01638 #if defined(DYING) || defined(__LCLINT__)
    01639         /* XXX all packages now have Provides: name = version-release */
    01640         /* Adding: check name against conflicts matches. */
    01641         rc = checkDependentConflicts(ts, rpmteN(p));
    01642         if (rc)
    01643             goto exit;
    01644 #endif
    01645
    01646         rc = 0;
    01647         provides = rpmteDS(p, RPMTAG_PROVIDENAME);
    01648         provides = rpmdsInit(provides);
    01649         if (provides == NULL || rpmdsN(provides) == NULL)
    01650             continue;
    01651         while (rpmdsNext(provides) >= 0) {
    01652             const char * Name;
    01653
    01654             if ((Name = rpmdsN(provides)) == NULL)
    01655                 /*@innercontinue@*/ continue;   /* XXX can't happen */
    01656
    01657             /* Adding: check provides key against conflicts matches. */
    01658             if (!checkDependentConflicts(ts, Name))
    01659                 /*@innercontinue@*/ continue;
    01660             rc = 1;
    01661             /*@innerbreak@*/ break;
    01662         }
    01663         if (rc)
    01664             goto exit;
    01665     }
    01666     pi = rpmtsiFree(pi);
    01667
    01668     /*
    01669      * Look at the removed packages and make sure they aren't critical.
    01670      */
    01671     pi = rpmtsiInit(ts);
    01672     while ((p = rpmtsiNext(pi, TR_REMOVED)) != NULL) {
    01673         rpmds provides;
    01674         rpmfi fi;
    01675
    01676         rpmMessage(RPMMESS_DEBUG,  "========== --- %s\n" , rpmteNEVR(p));
    01677
    01678 #if defined(DYING) || defined(__LCLINT__)
    01679         /* XXX all packages now have Provides: name = version-release */
    01680         /* Erasing: check name against requiredby matches. */
    01681         rc = checkDependentPackages(ts, rpmteN(p));
    01682         if (rc)
    01683                 goto exit;
    01684 #endif
    01685
    01686         rc = 0;
    01687         provides = rpmteDS(p, RPMTAG_PROVIDENAME);
    01688         provides = rpmdsInit(provides);
    01689         if (provides != NULL)
    01690         while (rpmdsNext(provides) >= 0) {
    01691             const char * Name;
    01692
    01693             if ((Name = rpmdsN(provides)) == NULL)
    01694                 /*@innercontinue@*/ continue;   /* XXX can't happen */
    01695
    01696             /* Erasing: check provides against requiredby matches. */
    01697             if (!checkDependentPackages(ts, Name))
    01698                 /*@innercontinue@*/ continue;
    01699             rc = 1;
    01700             /*@innerbreak@*/ break;
    01701         }
    01702         if (rc)
    01703             goto exit;
    01704
    01705         rc = 0;
    01706         fi = rpmteFI(p, RPMTAG_BASENAMES);
    01707         fi = rpmfiInit(fi, 0);
    01708         while (rpmfiNext(fi) >= 0) {
    01709             const char * fn = rpmfiFN(fi);
    01710
    01711             /* Erasing: check filename against requiredby matches. */
    01712             if (!checkDependentPackages(ts, fn))
    01713                 /*@innercontinue@*/ continue;
    01714             rc = 1;
    01715             /*@innerbreak@*/ break;
    01716         }
    01717         if (rc)
    01718             goto exit;
    01719     }
    01720     pi = rpmtsiFree(pi);
    01721
    01722     rc = 0;
    01723
    01724 exit:
    01725     mi = rpmdbFreeIterator(mi);
    01726     pi = rpmtsiFree(pi);
    01727     /*@-branchstate@*/
    01728     if (closeatexit)
    01729         xx = rpmtsCloseDB(ts);
    01730     else if (_cacheDependsRC)
    01731         xx = rpmdbCloseDBI(rpmtsGetRdb(ts), RPMDBI_DEPENDS);
    01732     /*@=branchstate@*/
    01733     return rc;
    01734 }