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

Generated on Mon Mar 19 08:20:54 2007 for rpm by  doxygen 1.4.7