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

Generated on Wed Jan 28 12:45:24 2009 for rpm by  doxygen 1.4.7