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

lib/depends.c

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

Generated on Fri Jul 28 03:09:43 2006 for rpm by doxygen 1.3.5