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

Generated on Fri Feb 24 08:33:31 2006 for rpm by  doxygen 1.4.5