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

lib/depends.c

Go to the documentation of this file.
00001 
00005 #include "system.h"
00006 
00007 #include <rpmcli.h>             /* XXX rpmcliPackagesTotal */
00008 
00009 #include <rpmmacro.h>           /* XXX rpmExpand("%{_dependency_whiteout}" */
00010 
00011 #include "rpmdb.h"              /* XXX response cache needs dbiOpen et al. */
00012 
00013 #include "rpmds.h"
00014 #include "rpmfi.h"
00015 
00016 #define _RPMTE_INTERNAL
00017 #include "rpmte.h"
00018 
00019 #define _RPMTS_INTERNAL
00020 #include "rpmts.h"
00021 
00022 #include "debug.h"
00023 
00024 /*@access tsortInfo @*/
00025 /*@access rpmts @*/
00026 
00027 /*@access dbiIndex @*/          /* XXX for dbi->dbi_txnid */
00028 
00029 /*@access alKey @*/     /* XXX for reordering and RPMAL_NOMATCH assign */
00030 
00033 typedef /*@abstract@*/ struct orderListIndex_s *        orderListIndex;
00034 /*@access orderListIndex@*/
00035 
00038 struct orderListIndex_s {
00039 /*@dependent@*/
00040     alKey pkgKey;
00041     int orIndex;
00042 };
00043 
00044 /*@unchecked@*/
00045 int _cacheDependsRC = 1;
00046 
00047 /*@observer@*/ /*@unchecked@*/
00048 const char *rpmNAME = PACKAGE;
00049 
00050 /*@observer@*/ /*@unchecked@*/
00051 const char *rpmEVR = VERSION;
00052 
00053 /*@unchecked@*/
00054 int rpmFLAGS = RPMSENSE_EQUAL;
00055 
00062 static int intcmp(const void * a, const void * b)
00063         /*@requires maxRead(a) == 0 /\ maxRead(b) == 0 @*/
00064 {
00065     const int * aptr = a;
00066     const int * bptr = b;
00067     int rc = (*aptr - *bptr);
00068     return rc;
00069 }
00070 
00079 static int removePackage(rpmts ts, Header h, int dboffset,
00080                 /*@exposed@*/ /*@dependent@*/ /*@null@*/ alKey depends)
00081         /*@globals fileSystem @*/
00082         /*@modifies ts, h, fileSystem @*/
00083 {
00084     rpmte p;
00085 
00086     /* Filter out duplicate erasures. */
00087     if (ts->numRemovedPackages > 0 && ts->removedPackages != NULL) {
00088 /*@-boundswrite@*/
00089         if (bsearch(&dboffset, ts->removedPackages, ts->numRemovedPackages,
00090                         sizeof(*ts->removedPackages), intcmp) != NULL)
00091             return 0;
00092 /*@=boundswrite@*/
00093     }
00094 
00095     if (ts->numRemovedPackages == ts->allocedRemovedPackages) {
00096         ts->allocedRemovedPackages += ts->delta;
00097         ts->removedPackages = xrealloc(ts->removedPackages,
00098                 sizeof(ts->removedPackages) * ts->allocedRemovedPackages);
00099     }
00100 
00101     if (ts->removedPackages != NULL) {  /* XXX can't happen. */
00102 /*@-boundswrite@*/
00103         ts->removedPackages[ts->numRemovedPackages] = dboffset;
00104         ts->numRemovedPackages++;
00105 /*@=boundswrite@*/
00106         if (ts->numRemovedPackages > 1)
00107             qsort(ts->removedPackages, ts->numRemovedPackages,
00108                         sizeof(*ts->removedPackages), intcmp);
00109     }
00110 
00111     if (ts->orderCount >= ts->orderAlloced) {
00112         ts->orderAlloced += (ts->orderCount - ts->orderAlloced) + ts->delta;
00113 /*@-type +voidabstract @*/
00114         ts->order = xrealloc(ts->order, sizeof(*ts->order) * ts->orderAlloced);
00115 /*@=type =voidabstract @*/
00116     }
00117 
00118     p = rpmteNew(ts, h, TR_REMOVED, NULL, NULL, dboffset, depends);
00119 /*@-boundswrite@*/
00120     ts->order[ts->orderCount] = p;
00121     ts->orderCount++;
00122 /*@=boundswrite@*/
00123 
00124     return 0;
00125 }
00126 
00127 int rpmtsAddInstallElement(rpmts ts, Header h,
00128                         fnpyKey key, int upgrade, rpmRelocation * relocs)
00129 {
00130     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 package config dependencies. */
01025     if (!strncmp(Name, "config(", sizeof("config(")-1))
01026         return 0;
01027 
01028     pkgKey = RPMAL_NOMATCH;
01029     key = rpmalSatisfiesDepend(ts->addedPackages, requires, &pkgKey);
01030 
01031     /* Ordering depends only on added package relations. */
01032     if (pkgKey == RPMAL_NOMATCH)
01033         return 0;
01034 
01035 /* XXX Set q to the added package that has pkgKey == q->u.addedKey */
01036 /* XXX FIXME: bsearch is possible/needed here */
01037     for (qi = rpmtsiInit(ts), i = 0; (q = rpmtsiNext(qi, 0)) != NULL; i++) {
01038 
01039         /* XXX Only added packages need be checked for matches. */
01040         if (rpmteType(q) == TR_REMOVED)
01041             continue;
01042 
01043         if (pkgKey == rpmteAddedKey(q))
01044             break;
01045     }
01046     qi = rpmtsiFree(qi);
01047     if (q == NULL || i == ts->orderCount)
01048         return 0;
01049 
01050     /* Avoid certain dependency relations. */
01051     if (ignoreDep(p, q))
01052         return 0;
01053 
01054     /* Avoid redundant relations. */
01055     /* XXX TODO: add control bit. */
01056 /*@-boundsread@*/
01057     if (selected[i] != 0)
01058         return 0;
01059 /*@=boundsread@*/
01060 /*@-boundswrite@*/
01061     selected[i] = 1;
01062 /*@=boundswrite@*/
01063 
01064     /* T3. Record next "q <- p" relation (i.e. "p" requires "q"). */
01065     rpmteTSI(p)->tsi_count++;                   /* bump p predecessor count */
01066 
01067     if (rpmteDepth(p) <= rpmteDepth(q)) /* Save max. depth in dependency tree */
01068         (void) rpmteSetDepth(p, (rpmteDepth(q) + 1));
01069 
01070     tsi = xcalloc(1, sizeof(*tsi));
01071     tsi->tsi_suc = p;
01072 
01073     tsi->tsi_reqx = rpmdsIx(requires);
01074 
01075     tsi->tsi_next = rpmteTSI(q)->tsi_next;
01076     rpmteTSI(q)->tsi_next = tsi;
01077     rpmteTSI(q)->tsi_qcnt++;                    /* bump q successor count */
01078     return 0;
01079 }
01080 /*@=mustmod@*/
01081 
01088 static int orderListIndexCmp(const void * one, const void * two)        /*@*/
01089 {
01090     /*@-castexpose@*/
01091     long a = (long) ((const orderListIndex)one)->pkgKey;
01092     long b = (long) ((const orderListIndex)two)->pkgKey;
01093     /*@=castexpose@*/
01094     return (a - b);
01095 }
01096 
01103 /*@-boundswrite@*/
01104 /*@-mustmod@*/
01105 static void addQ(/*@dependent@*/ rpmte p,
01106                 /*@in@*/ /*@out@*/ rpmte * qp,
01107                 /*@in@*/ /*@out@*/ rpmte * rp)
01108         /*@modifies p, *qp, *rp @*/
01109 {
01110     rpmte q, qprev;
01111 
01112     /* Mark the package as queued. */
01113     rpmteTSI(p)->tsi_reqx = 1;
01114 
01115     if ((*rp) == NULL) {        /* 1st element */
01116         /*@-dependenttrans@*/ /* FIX: double indirection */
01117         (*rp) = (*qp) = p;
01118         /*@=dependenttrans@*/
01119         return;
01120     }
01121 
01122     /* Find location in queue using metric tsi_qcnt. */
01123     for (qprev = NULL, q = (*qp);
01124          q != NULL;
01125          qprev = q, q = rpmteTSI(q)->tsi_suc)
01126     {
01127         if (rpmteTSI(q)->tsi_qcnt <= rpmteTSI(p)->tsi_qcnt)
01128             break;
01129     }
01130 
01131     if (qprev == NULL) {        /* insert at beginning of list */
01132         rpmteTSI(p)->tsi_suc = q;
01133         /*@-dependenttrans@*/
01134         (*qp) = p;              /* new head */
01135         /*@=dependenttrans@*/
01136     } else if (q == NULL) {     /* insert at end of list */
01137         rpmteTSI(qprev)->tsi_suc = p;
01138         /*@-dependenttrans@*/
01139         (*rp) = p;              /* new tail */
01140         /*@=dependenttrans@*/
01141     } else {                    /* insert between qprev and q */
01142         rpmteTSI(p)->tsi_suc = q;
01143         rpmteTSI(qprev)->tsi_suc = p;
01144     }
01145 }
01146 /*@=mustmod@*/
01147 /*@=boundswrite@*/
01148 
01149 /*@-bounds@*/
01150 int rpmtsOrder(rpmts ts)
01151 {
01152     rpmds requires;
01153     int_32 Flags;
01154     int anaconda = rpmtsFlags(ts) & RPMTRANS_FLAG_ANACONDA;
01155     rpmtsi pi; rpmte p;
01156     rpmtsi qi; rpmte q;
01157     rpmtsi ri; rpmte r;
01158     tsortInfo tsi;
01159     tsortInfo tsi_next;
01160     alKey * ordering;
01161     int orderingCount = 0;
01162     unsigned char * selected = alloca(sizeof(*selected) * (ts->orderCount + 1));
01163     int loopcheck;
01164     rpmte * newOrder;
01165     int newOrderCount = 0;
01166     orderListIndex orderList;
01167     int numOrderList;
01168     int nrescans = 10;
01169     int _printed = 0;
01170     char deptypechar;
01171     size_t tsbytes;
01172     int oType = 0;
01173     int treex;
01174     int depth;
01175     int qlen;
01176     int i, j;
01177 
01178 #ifdef  DYING
01179     rpmalMakeIndex(ts->addedPackages);
01180 #endif
01181 
01182     (void) rpmswEnter(rpmtsOp(ts, RPMTS_OP_ORDER), 0);
01183 
01184     /* T1. Initialize. */
01185     if (oType == 0)
01186         numOrderList = ts->orderCount;
01187     else {
01188         numOrderList = 0;
01189         if (oType & TR_ADDED)
01190             numOrderList += ts->numAddedPackages;
01191         if (oType & TR_REMOVED)
01192             numOrderList += ts->numRemovedPackages;
01193      }
01194     ordering = alloca(sizeof(*ordering) * (numOrderList + 1));
01195     loopcheck = numOrderList;
01196     tsbytes = 0;
01197 
01198     pi = rpmtsiInit(ts);
01199     while ((p = rpmtsiNext(pi, oType)) != NULL)
01200         rpmteNewTSI(p);
01201     pi = rpmtsiFree(pi);
01202 
01203     /* Record all relations. */
01204     rpmMessage(RPMMESS_DEBUG, _("========== recording tsort relations\n"));
01205     pi = rpmtsiInit(ts);
01206     while ((p = rpmtsiNext(pi, oType)) != NULL) {
01207 
01208         if ((requires = rpmteDS(p, RPMTAG_REQUIRENAME)) == NULL)
01209             continue;
01210 
01211         memset(selected, 0, sizeof(*selected) * ts->orderCount);
01212 
01213         /* Avoid narcisstic relations. */
01214         selected[rpmtsiOc(pi)] = 1;
01215 
01216         /* T2. Next "q <- p" relation. */
01217 
01218         /* First, do pre-requisites. */
01219         requires = rpmdsInit(requires);
01220         if (requires != NULL)
01221         while (rpmdsNext(requires) >= 0) {
01222 
01223             Flags = rpmdsFlags(requires);
01224 
01225             switch (rpmteType(p)) {
01226             case TR_REMOVED:
01227                 /* Skip if not %preun/%postun requires or legacy prereq. */
01228                 if (isInstallPreReq(Flags)
01229                  || !( isErasePreReq(Flags) || isLegacyPreReq(Flags) ) )
01230                     /*@innercontinue@*/ continue;
01231                 /*@switchbreak@*/ break;
01232             case TR_ADDED:
01233                 /* Skip if not %pre/%post requires or legacy prereq. */
01234                 if (isErasePreReq(Flags)
01235                  || !( isInstallPreReq(Flags) || isLegacyPreReq(Flags) ) )
01236                     /*@innercontinue@*/ continue;
01237                 /*@switchbreak@*/ break;
01238             }
01239 
01240             /* T3. Record next "q <- p" relation (i.e. "p" requires "q"). */
01241             (void) addRelation(ts, p, selected, requires);
01242 
01243         }
01244 
01245         /* Then do co-requisites. */
01246         requires = rpmdsInit(requires);
01247         if (requires != NULL)
01248         while (rpmdsNext(requires) >= 0) {
01249 
01250             Flags = rpmdsFlags(requires);
01251 
01252             switch (rpmteType(p)) {
01253             case TR_REMOVED:
01254                 /* Skip if %preun/%postun requires or legacy prereq. */
01255                 if (isInstallPreReq(Flags)
01256                  ||  ( isErasePreReq(Flags) || isLegacyPreReq(Flags) ) )
01257                     /*@innercontinue@*/ continue;
01258                 /*@switchbreak@*/ break;
01259             case TR_ADDED:
01260                 /* Skip if %pre/%post requires or legacy prereq. */
01261                 if (isErasePreReq(Flags)
01262                  ||  ( isInstallPreReq(Flags) || isLegacyPreReq(Flags) ) )
01263                     /*@innercontinue@*/ continue;
01264                 /*@switchbreak@*/ break;
01265             }
01266 
01267             /* T3. Record next "q <- p" relation (i.e. "p" requires "q"). */
01268             (void) addRelation(ts, p, selected, requires);
01269 
01270         }
01271     }
01272     pi = rpmtsiFree(pi);
01273 
01274     /* Save predecessor count and mark tree roots. */
01275     treex = 0;
01276     pi = rpmtsiInit(ts);
01277     while ((p = rpmtsiNext(pi, oType)) != NULL) {
01278         int npreds;
01279 
01280         npreds = rpmteTSI(p)->tsi_count;
01281 
01282         (void) rpmteSetNpreds(p, npreds);
01283 
01284         if (npreds == 0)
01285             (void) rpmteSetTree(p, treex++);
01286         else
01287             (void) rpmteSetTree(p, -1);
01288 #ifdef  UNNECESSARY
01289         (void) rpmteSetParent(p, NULL);
01290 #endif
01291 
01292     }
01293     pi = rpmtsiFree(pi);
01294 
01295     /* T4. Scan for zeroes. */
01296     rpmMessage(RPMMESS_DEBUG, _("========== tsorting packages (order, #predecessors, #succesors, tree, depth)\n"));
01297 
01298 rescan:
01299     if (pi != NULL) pi = rpmtsiFree(pi);
01300     q = r = NULL;
01301     qlen = 0;
01302     pi = rpmtsiInit(ts);
01303     while ((p = rpmtsiNext(pi, oType)) != NULL) {
01304 
01305         /* Prefer packages in chainsaw or anaconda presentation order. */
01306         if (anaconda)
01307             rpmteTSI(p)->tsi_qcnt = (ts->orderCount - rpmtsiOc(pi));
01308 
01309         if (rpmteTSI(p)->tsi_count != 0)
01310             continue;
01311         rpmteTSI(p)->tsi_suc = NULL;
01312         addQ(p, &q, &r);
01313         qlen++;
01314     }
01315     pi = rpmtsiFree(pi);
01316 
01317     /* T5. Output front of queue (T7. Remove from queue.) */
01318     for (; q != NULL; q = rpmteTSI(q)->tsi_suc) {
01319 
01320         /* Mark the package as unqueued. */
01321         rpmteTSI(q)->tsi_reqx = 0;
01322 
01323         if (oType != 0)
01324         switch (rpmteType(q)) {
01325         case TR_ADDED:
01326             if (!(oType & TR_ADDED))
01327                 continue;
01328             /*@switchbreak@*/ break;
01329         case TR_REMOVED:
01330             if (!(oType & TR_REMOVED))
01331                 continue;
01332             /*@switchbreak@*/ break;
01333         default:
01334             continue;
01335             /*@notreached@*/ /*@switchbreak@*/ break;
01336         }
01337         deptypechar = (rpmteType(q) == TR_REMOVED ? '-' : '+');
01338 
01339         rpmMessage(RPMMESS_DEBUG, "%5d%5d%5d%5d%5d %*s%c%s\n",
01340                         orderingCount, rpmteNpreds(q),
01341                         rpmteTSI(q)->tsi_qcnt, rpmteTree(q), rpmteDepth(q),
01342                         (2 * rpmteDepth(q)), "",
01343                         deptypechar,
01344                         (rpmteNEVR(q) ? rpmteNEVR(q) : "???"));
01345 
01346         treex = rpmteTree(q);
01347         depth = rpmteDepth(q);
01348         (void) rpmteSetDegree(q, 0);
01349         tsbytes += rpmtePkgFileSize(q);
01350 
01351         ordering[orderingCount] = rpmteAddedKey(q);
01352         orderingCount++;
01353         qlen--;
01354         loopcheck--;
01355 
01356         /* T6. Erase relations. */
01357         tsi_next = rpmteTSI(q)->tsi_next;
01358         rpmteTSI(q)->tsi_next = NULL;
01359         while ((tsi = tsi_next) != NULL) {
01360             tsi_next = tsi->tsi_next;
01361             tsi->tsi_next = NULL;
01362             p = tsi->tsi_suc;
01363             if (p && (--rpmteTSI(p)->tsi_count) <= 0) {
01364 
01365                 (void) rpmteSetTree(p, treex);
01366                 (void) rpmteSetDepth(p, depth+1);
01367                 (void) rpmteSetParent(p, q);
01368                 (void) rpmteSetDegree(q, rpmteDegree(q)+1);
01369 
01370                 /* XXX TODO: add control bit. */
01371                 rpmteTSI(p)->tsi_suc = NULL;
01372                 addQ(p, &rpmteTSI(q)->tsi_suc, &r);
01373                 qlen++;
01374             }
01375             tsi = _free(tsi);
01376         }
01377         if (!_printed && loopcheck == qlen && rpmteTSI(q)->tsi_suc != NULL) {
01378             _printed++;
01379             (void) rpmtsUnorderedSuccessors(ts, orderingCount);
01380             rpmMessage(RPMMESS_DEBUG,
01381                 _("========== successors only (%d bytes)\n"), (int)tsbytes);
01382 
01383             /* Relink the queue in presentation order. */
01384             tsi = rpmteTSI(q);
01385             pi = rpmtsiInit(ts);
01386             while ((p = rpmtsiNext(pi, oType)) != NULL) {
01387                 /* Is this element in the queue? */
01388                 if (rpmteTSI(p)->tsi_reqx == 0)
01389                     /*@innercontinue@*/ continue;
01390                 tsi->tsi_suc = p;
01391                 tsi = rpmteTSI(p);
01392             }
01393             pi = rpmtsiFree(pi);
01394             tsi->tsi_suc = NULL;
01395         }
01396     }
01397 
01398     /* T8. End of process. Check for loops. */
01399     if (loopcheck != 0) {
01400         int nzaps;
01401 
01402         /* T9. Initialize predecessor chain. */
01403         nzaps = 0;
01404         qi = rpmtsiInit(ts);
01405         while ((q = rpmtsiNext(qi, oType)) != NULL) {
01406             rpmteTSI(q)->tsi_chain = NULL;
01407             rpmteTSI(q)->tsi_reqx = 0;
01408             /* Mark packages already sorted. */
01409             if (rpmteTSI(q)->tsi_count == 0)
01410                 rpmteTSI(q)->tsi_count = -1;
01411         }
01412         qi = rpmtsiFree(qi);
01413 
01414         /* T10. Mark all packages with their predecessors. */
01415         qi = rpmtsiInit(ts);
01416         while ((q = rpmtsiNext(qi, oType)) != NULL) {
01417             if ((tsi = rpmteTSI(q)->tsi_next) == NULL)
01418                 continue;
01419             rpmteTSI(q)->tsi_next = NULL;
01420             markLoop(tsi, q);
01421             rpmteTSI(q)->tsi_next = tsi;
01422         }
01423         qi = rpmtsiFree(qi);
01424 
01425         /* T11. Print all dependency loops. */
01426         ri = rpmtsiInit(ts);
01427         while ((r = rpmtsiNext(ri, oType)) != NULL)
01428         {
01429             int printed;
01430 
01431             printed = 0;
01432 
01433             /* T12. Mark predecessor chain, looking for start of loop. */
01434             for (q = rpmteTSI(r)->tsi_chain; q != NULL;
01435                  q = rpmteTSI(q)->tsi_chain)
01436             {
01437                 if (rpmteTSI(q)->tsi_reqx)
01438                     /*@innerbreak@*/ break;
01439                 rpmteTSI(q)->tsi_reqx = 1;
01440             }
01441 
01442             /* T13. Print predecessor chain from start of loop. */
01443             while ((p = q) != NULL && (q = rpmteTSI(p)->tsi_chain) != NULL) {
01444                 const char * dp;
01445                 char buf[4096];
01446 
01447                 /* Unchain predecessor loop. */
01448                 rpmteTSI(p)->tsi_chain = NULL;
01449 
01450                 if (!printed) {
01451                     rpmMessage(RPMMESS_DEBUG, _("LOOP:\n"));
01452                     printed = 1;
01453                 }
01454 
01455                 /* Find (and destroy if co-requisite) "q <- p" relation. */
01456                 requires = rpmteDS(p, RPMTAG_REQUIRENAME);
01457                 requires = rpmdsInit(requires);
01458                 if (requires == NULL)
01459                     /*@innercontinue@*/ continue;       /* XXX can't happen */
01460                 dp = zapRelation(q, p, requires, 1, &nzaps);
01461 
01462                 /* Print next member of loop. */
01463                 buf[0] = '\0';
01464                 if (rpmteNEVR(p) != NULL)
01465                     (void) stpcpy(buf, rpmteNEVR(p));
01466                 rpmMessage(RPMMESS_DEBUG, "    %-40s %s\n", buf,
01467                         (dp ? dp : "not found!?!"));
01468 
01469                 dp = _free(dp);
01470             }
01471 
01472             /* Walk (and erase) linear part of predecessor chain as well. */
01473             for (p = r, q = rpmteTSI(r)->tsi_chain; q != NULL;
01474                  p = q, q = rpmteTSI(q)->tsi_chain)
01475             {
01476                 /* Unchain linear part of predecessor loop. */
01477                 rpmteTSI(p)->tsi_chain = NULL;
01478                 rpmteTSI(p)->tsi_reqx = 0;
01479             }
01480         }
01481         ri = rpmtsiFree(ri);
01482 
01483         /* If a relation was eliminated, then continue sorting. */
01484         /* XXX TODO: add control bit. */
01485         if (nzaps && nrescans-- > 0) {
01486             rpmMessage(RPMMESS_DEBUG, _("========== continuing tsort ...\n"));
01487             goto rescan;
01488         }
01489 
01490         /* Return no. of packages that could not be ordered. */
01491         rpmMessage(RPMMESS_ERROR, _("rpmtsOrder failed, %d elements remain\n"),
01492                         loopcheck);
01493         return loopcheck;
01494     }
01495 
01496     /* Clean up tsort remnants (if any). */
01497     pi = rpmtsiInit(ts);
01498     while ((p = rpmtsiNext(pi, 0)) != NULL)
01499         rpmteFreeTSI(p);
01500     pi = rpmtsiFree(pi);
01501 
01502     /*
01503      * The order ends up as installed packages followed by removed packages,
01504      * with removes for upgrades immediately following the installation of
01505      * the new package. This would be easier if we could sort the
01506      * addedPackages array, but we store indexes into it in various places.
01507      */
01508     orderList = xcalloc(numOrderList, sizeof(*orderList));
01509     j = 0;
01510     pi = rpmtsiInit(ts);
01511     while ((p = rpmtsiNext(pi, oType)) != NULL) {
01512         /* Prepare added package ordering permutation. */
01513         switch (rpmteType(p)) {
01514         case TR_ADDED:
01515             orderList[j].pkgKey = rpmteAddedKey(p);
01516             /*@switchbreak@*/ break;
01517         case TR_REMOVED:
01518             orderList[j].pkgKey = RPMAL_NOMATCH;
01519             /*@switchbreak@*/ break;
01520         }
01521         orderList[j].orIndex = rpmtsiOc(pi);
01522         j++;
01523     }
01524     pi = rpmtsiFree(pi);
01525 
01526     qsort(orderList, numOrderList, sizeof(*orderList), orderListIndexCmp);
01527 
01528 /*@-type@*/
01529     newOrder = xcalloc(ts->orderCount, sizeof(*newOrder));
01530 /*@=type@*/
01531     /*@-branchstate@*/
01532     for (i = 0, newOrderCount = 0; i < orderingCount; i++)
01533     {
01534         struct orderListIndex_s key;
01535         orderListIndex needle;
01536 
01537         key.pkgKey = ordering[i];
01538         needle = bsearch(&key, orderList, numOrderList,
01539                                 sizeof(key), orderListIndexCmp);
01540         /* bsearch should never, ever fail */
01541         if (needle == NULL)
01542             continue;
01543 
01544         j = needle->orIndex;
01545         if ((q = ts->order[j]) == NULL)
01546             continue;
01547 
01548         newOrder[newOrderCount++] = q;
01549         ts->order[j] = NULL;
01550         if (anaconda)
01551         for (j = needle->orIndex + 1; j < ts->orderCount; j++) {
01552             if ((q = ts->order[j]) == NULL)
01553                 /*@innerbreak@*/ break;
01554             if (rpmteType(q) == TR_REMOVED
01555              && rpmteDependsOnKey(q) == needle->pkgKey)
01556             {
01557                 newOrder[newOrderCount++] = q;
01558                 ts->order[j] = NULL;
01559             } else
01560                 /*@innerbreak@*/ break;
01561         }
01562     }
01563     /*@=branchstate@*/
01564 
01565     for (j = 0; j < ts->orderCount; j++) {
01566         if ((p = ts->order[j]) == NULL)
01567             continue;
01568         newOrder[newOrderCount++] = p;
01569         ts->order[j] = NULL;
01570     }
01571 assert(newOrderCount == ts->orderCount);
01572 
01573 /*@+voidabstract@*/
01574     ts->order = _free(ts->order);
01575 /*@=voidabstract@*/
01576     ts->order = newOrder;
01577     ts->orderAlloced = ts->orderCount;
01578     orderList = _free(orderList);
01579 
01580 #ifdef  DYING   /* XXX now done at the CLI level just before rpmtsRun(). */
01581     rpmtsClean(ts);
01582 #endif
01583     freeBadDeps();
01584 
01585     (void) rpmswExit(rpmtsOp(ts, RPMTS_OP_ORDER), 0);
01586 
01587     return 0;
01588 }
01589 /*@=bounds@*/
01590 
01591 int rpmtsCheck(rpmts ts)
01592 {
01593     uint_32 tscolor = rpmtsColor(ts);
01594     rpmdbMatchIterator mi = NULL;
01595     rpmtsi pi = NULL; rpmte p;
01596     int closeatexit = 0;
01597     int xx;
01598     int rc;
01599 
01600     (void) rpmswEnter(rpmtsOp(ts, RPMTS_OP_CHECK), 0);
01601 
01602     /* Do lazy, readonly, open of rpm database. */
01603     if (rpmtsGetRdb(ts) == NULL && ts->dbmode != -1) {
01604         if ((rc = rpmtsOpenDB(ts, ts->dbmode)) != 0)
01605             goto exit;
01606         closeatexit = 1;
01607     }
01608 
01609     ts->probs = rpmpsFree(ts->probs);
01610     ts->probs = rpmpsCreate();
01611 
01612     rpmalMakeIndex(ts->addedPackages);
01613 
01614     /*
01615      * Look at all of the added packages and make sure their dependencies
01616      * are satisfied.
01617      */
01618     pi = rpmtsiInit(ts);
01619     while ((p = rpmtsiNext(pi, TR_ADDED)) != NULL) {
01620         rpmds provides;
01621 
01622 /*@-nullpass@*/ /* FIX: rpmts{A,O} can return null. */
01623         rpmMessage(RPMMESS_DEBUG, "========== +++ %s %s-%s 0x%x\n",
01624                 rpmteNEVR(p), rpmteA(p), rpmteO(p), rpmteColor(p));
01625 /*@=nullpass@*/
01626         rc = checkPackageDeps(ts, rpmteNEVR(p),
01627                         rpmteDS(p, RPMTAG_REQUIRENAME),
01628                         rpmteDS(p, RPMTAG_CONFLICTNAME),
01629                         NULL,
01630                         tscolor, 1);
01631         if (rc)
01632             goto exit;
01633 
01634 #if defined(DYING) || defined(__LCLINT__)
01635         /* XXX all packages now have Provides: name = version-release */
01636         /* Adding: check name against conflicts matches. */
01637         rc = checkDependentConflicts(ts, rpmteN(p));
01638         if (rc)
01639             goto exit;
01640 #endif
01641 
01642         rc = 0;
01643         provides = rpmteDS(p, RPMTAG_PROVIDENAME);
01644         provides = rpmdsInit(provides);
01645         if (provides == NULL || rpmdsN(provides) == NULL)
01646             continue;
01647         while (rpmdsNext(provides) >= 0) {
01648             const char * Name;
01649 
01650             if ((Name = rpmdsN(provides)) == NULL)
01651                 /*@innercontinue@*/ continue;   /* XXX can't happen */
01652 
01653             /* Adding: check provides key against conflicts matches. */
01654             if (!checkDependentConflicts(ts, Name))
01655                 /*@innercontinue@*/ continue;
01656             rc = 1;
01657             /*@innerbreak@*/ break;
01658         }
01659         if (rc)
01660             goto exit;
01661     }
01662     pi = rpmtsiFree(pi);
01663 
01664     /*
01665      * Look at the removed packages and make sure they aren't critical.
01666      */
01667     pi = rpmtsiInit(ts);
01668     while ((p = rpmtsiNext(pi, TR_REMOVED)) != NULL) {
01669         rpmds provides;
01670         rpmfi fi;
01671 
01672 /*@-nullpass@*/ /* FIX: rpmts{A,O} can return null. */
01673         rpmMessage(RPMMESS_DEBUG, "========== --- %s %s-%s 0x%x\n",
01674                 rpmteNEVR(p), rpmteA(p), rpmteO(p), rpmteColor(p));
01675 /*@=nullpass@*/
01676 
01677 #if defined(DYING) || defined(__LCLINT__)
01678         /* XXX all packages now have Provides: name = version-release */
01679         /* Erasing: check name against requiredby matches. */
01680         rc = checkDependentPackages(ts, rpmteN(p));
01681         if (rc)
01682                 goto exit;
01683 #endif
01684 
01685         rc = 0;
01686         provides = rpmteDS(p, RPMTAG_PROVIDENAME);
01687         provides = rpmdsInit(provides);
01688         if (provides != NULL)
01689         while (rpmdsNext(provides) >= 0) {
01690             const char * Name;
01691 
01692             if ((Name = rpmdsN(provides)) == NULL)
01693                 /*@innercontinue@*/ continue;   /* XXX can't happen */
01694 
01695             /* Erasing: check provides against requiredby matches. */
01696             if (!checkDependentPackages(ts, Name))
01697                 /*@innercontinue@*/ continue;
01698             rc = 1;
01699             /*@innerbreak@*/ break;
01700         }
01701         if (rc)
01702             goto exit;
01703 
01704         rc = 0;
01705         fi = rpmteFI(p, RPMTAG_BASENAMES);
01706         fi = rpmfiInit(fi, 0);
01707         while (rpmfiNext(fi) >= 0) {
01708             const char * fn = rpmfiFN(fi);
01709 
01710             /* Erasing: check filename against requiredby matches. */
01711             if (!checkDependentPackages(ts, fn))
01712                 /*@innercontinue@*/ continue;
01713             rc = 1;
01714             /*@innerbreak@*/ break;
01715         }
01716         if (rc)
01717             goto exit;
01718     }
01719     pi = rpmtsiFree(pi);
01720 
01721     rc = 0;
01722 
01723 exit:
01724     mi = rpmdbFreeIterator(mi);
01725     pi = rpmtsiFree(pi);
01726 
01727     (void) rpmswExit(rpmtsOp(ts, RPMTS_OP_CHECK), 0);
01728 
01729     /*@-branchstate@*/
01730     if (closeatexit)
01731         xx = rpmtsCloseDB(ts);
01732     else if (_cacheDependsRC)
01733         xx = rpmdbCloseDBI(rpmtsGetRdb(ts), RPMDBI_DEPENDS);
01734     /*@=branchstate@*/
01735     return rc;
01736 }

Generated on Sun Oct 26 13:01:58 2003 for rpm by doxygen1.2.18