home *** CD-ROM | disk | FTP | other *** search
/ Chip 1998 February / CHIP_2_98.iso / misc / src / rpm / lib / depends.c < prev    next >
C/C++ Source or Header  |  1997-09-17  |  24KB  |  890 lines
  1. #include "config.h"
  2. #include "miscfn.h"
  3.  
  4. #if HAVE_ALLOCA_H
  5. # include <alloca.h>
  6. #endif
  7.  
  8. #include <ctype.h>
  9. #include <stdlib.h>
  10. #include <string.h>
  11.  
  12. #include "misc.h"
  13. #include "rpmlib.h"
  14. #include "messages.h"
  15.  
  16. struct availablePackage {
  17.     Header h;
  18.     char ** provides;
  19.     char ** files;
  20.     char * name, * version, * release;
  21.     int serial, hasSerial, providesCount, filesCount;
  22.     void * key;
  23. } ;
  24.  
  25. enum indexEntryType { IET_NAME, IET_PROVIDES, IET_FILE };
  26.  
  27. enum selectionStatus { UNSELECTED = 0, SELECTED, INPROCESS };
  28.  
  29. struct availableIndexEntry {
  30.     struct availablePackage * package;
  31.     char * entry;
  32.     enum indexEntryType type;
  33. } ;
  34.  
  35. struct availableIndex {
  36.     struct availableIndexEntry * index ;
  37.     int size;
  38. } ;
  39.  
  40. struct availableList {
  41.     struct availablePackage * list;
  42.     struct availableIndex index;
  43.     int size, alloced;
  44. };
  45.  
  46. struct rpmDependencyCheck {
  47.     rpmdb db;                    /* may be NULL */
  48.     int * removedPackages;
  49.     int numRemovedPackages, allocedRemovedPackages;
  50.     struct availableList addedPackages, availablePackages;
  51. };
  52.  
  53. struct problemsSet {
  54.     struct rpmDependencyConflict * problems;
  55.     int num;
  56.     int alloced;
  57. };
  58.  
  59. static void alMakeIndex(struct availableList * al);
  60. static void alCreate(struct availableList * al);
  61. static void alFreeIndex(struct availableList * al);
  62. static void alFree(struct availableList * al);
  63. static void alAddPackage(struct availableList * al, Header h, void * key);
  64.  
  65. static int intcmp(const void * a, const void *b);
  66. static int indexcmp(const void * a, const void *b);
  67. static int unsatisfiedDepend(rpmDependencies rpmdep, char * reqName, 
  68.                  char * reqVersion, int reqFlags,
  69.                  struct availablePackage ** suggestion);
  70. static int checkDependentPackages(rpmDependencies rpmdep, 
  71.                 struct problemsSet * psp, char * key);
  72. static int checkPackageDeps(rpmDependencies rpmdep, struct problemsSet * psp,
  73.             Header h, const char * requirement);
  74. static int dbrecMatchesDepFlags(rpmDependencies rpmdep, int recOffset, 
  75.                     char * reqVersion, int reqFlags);
  76. static int headerMatchesDepFlags(Header h, char * reqVersion, int reqFlags);
  77. struct availablePackage * alSatisfiesDepend(struct availableList * al, 
  78.                         char * reqName, char * reqVersion, 
  79.                         int reqFlags);
  80. static int checkDependentConflicts(rpmDependencies rpmdep, 
  81.                 struct problemsSet * psp, char * package);
  82. static int checkPackageSet(rpmDependencies rpmdep, struct problemsSet * psp, 
  83.                 char * package, dbiIndexSet * matches);
  84. static int addOrderedPack(rpmDependencies rpmdep, 
  85.             struct availablePackage * package,
  86.             void ** ordering, int * orderNumPtr, 
  87.             enum selectionStatus * selected, 
  88.             int satisfyDepends, char ** errorStack);
  89.  
  90. static void alCreate(struct availableList * al) {
  91.     al->list = malloc(sizeof(*al->list) * 5);
  92.     al->alloced = 5;
  93.     al->size = 0;
  94.  
  95.     al->index.index = NULL;
  96.     alFreeIndex(al);
  97. };
  98.  
  99. static void alFreeIndex(struct availableList * al) {
  100.     if (al->index.size) {
  101.     free(al->index.index);
  102.     al->index.index = NULL;
  103.     al->index.size = 0;
  104.     }
  105. }
  106.  
  107. static void alFree(struct availableList * al) {
  108.     int i;
  109.  
  110.     for (i = 0; i < al->size; i++) {
  111.     if (al->list[i].provides)
  112.         free(al->list[i].provides);
  113.     if (al->list[i].files)
  114.         free(al->list[i].files);
  115.     }
  116.  
  117.     if (al->alloced) free(al->list);
  118.     alFreeIndex(al);
  119. }
  120.  
  121. static void alAddPackage(struct availableList * al, Header h, void * key) {
  122.     struct availablePackage * p;
  123.  
  124.     if (al->size == al->alloced) {
  125.     al->alloced += 5;
  126.     al->list = realloc(al->list, sizeof(*al->list) * al->alloced);
  127.     }
  128.  
  129.     p = al->list + al->size++;
  130.     p->h = h;
  131.  
  132.     headerGetEntry(p->h, RPMTAG_NAME, NULL, (void **) &p->name, NULL);
  133.     headerGetEntry(p->h, RPMTAG_VERSION, NULL, (void **) &p->version, NULL);
  134.     headerGetEntry(p->h, RPMTAG_RELEASE, NULL, (void **) &p->release, NULL);
  135.     p->hasSerial = headerGetEntry(h, RPMTAG_SERIAL, NULL, (void **) &p->serial, 
  136.                   NULL);
  137.  
  138.     if (!headerGetEntry(h, RPMTAG_PROVIDES, NULL, (void **) &p->provides,
  139.     &p->providesCount)) {
  140.     p->providesCount = 0;
  141.     p->provides = NULL;
  142.     }
  143.  
  144.     if (!headerGetEntry(h, RPMTAG_FILENAMES, NULL, (void **) &p->files,
  145.     &p->filesCount)) {
  146.     p->filesCount = 0;
  147.     p->files = NULL;
  148.     }
  149.  
  150.     p->key = key;
  151.  
  152.     alFreeIndex(al);
  153. }
  154.  
  155. static void alMakeIndex(struct availableList * al) {
  156.     struct availableIndex * ai = &al->index;
  157.     int i, j, k;
  158.  
  159.     if (ai->size) return;
  160.  
  161.     ai->size = al->size;
  162.     for (i = 0; i < al->size; i++) {
  163.     ai->size += al->list[i].providesCount;
  164.     }
  165.     for (i = 0; i < al->size; i++) {
  166.     ai->size += al->list[i].filesCount;
  167.     }
  168.  
  169.     if (ai->size) {
  170.     ai->index = malloc(sizeof(*ai->index) * ai->size);
  171.     k = 0;
  172.     for (i = 0; i < al->size; i++) {
  173.         ai->index[k].package = al->list + i;
  174.         ai->index[k].entry = al->list[i].name;
  175.         ai->index[k].type = IET_NAME;
  176.         k++;
  177.  
  178.         for (j = 0; j < al->list[i].providesCount; j++) {
  179.         ai->index[k].package = al->list + i;
  180.         ai->index[k].entry = al->list[i].provides[j];
  181.         ai->index[k].type = IET_PROVIDES;
  182.         k++;
  183.         }
  184.  
  185.         for (j = 0; j < al->list[i].filesCount; j++) {
  186.         ai->index[k].package = al->list + i;
  187.         ai->index[k].entry = al->list[i].files[j];
  188.         ai->index[k].type = IET_FILE;
  189.         k++;
  190.         }
  191.     }
  192.  
  193.     qsort(ai->index, ai->size, sizeof(*ai->index), (void *) indexcmp);
  194.     }
  195. }
  196.  
  197. struct availablePackage * alSatisfiesDepend(struct availableList * al, 
  198.                         char * reqName, char * reqVersion, 
  199.                         int reqFlags) {
  200.     struct availableIndexEntry needle, * match;
  201.  
  202.     if (!al->index.size) return NULL;
  203.  
  204.     needle.entry = reqName;
  205.     match = bsearch(&needle, al->index.index, al->index.size,
  206.             sizeof(*al->index.index), (void *) indexcmp);
  207.  
  208.     if (!match) return NULL;
  209.     if (match->type != IET_NAME) return match->package;
  210.  
  211.     if (headerMatchesDepFlags(match->package->h, reqVersion, reqFlags))
  212.     return match->package;
  213.  
  214.     return NULL;
  215. }
  216.  
  217. int indexcmp(const void * a, const void *b) {
  218.     const struct availableIndexEntry * aptr = a;
  219.     const struct availableIndexEntry * bptr = b;
  220.  
  221.     return strcmp(aptr->entry, bptr->entry);
  222. }
  223.  
  224. int intcmp(const void * a, const void *b) {
  225.     const int * aptr = a;
  226.     const int * bptr = b;
  227.  
  228.     if (*aptr < *bptr) 
  229.     return -1;
  230.     else if (*aptr == *bptr)
  231.     return 0;
  232.  
  233.     return 1;
  234. }
  235.  
  236. rpmDependencies rpmdepDependencies(rpmdb db) {
  237.     rpmDependencies rpmdep;
  238.  
  239.     rpmdep = malloc(sizeof(*rpmdep));
  240.     rpmdep->db = db;
  241.     rpmdep->numRemovedPackages = 0;
  242.     rpmdep->allocedRemovedPackages = 5;
  243.     rpmdep->removedPackages = malloc(sizeof(int) * 
  244.                      rpmdep->allocedRemovedPackages);
  245.  
  246.     alCreate(&rpmdep->addedPackages);
  247.     alCreate(&rpmdep->availablePackages);
  248.  
  249.     return rpmdep;
  250. }
  251.  
  252. void rpmdepUpgradePackage(rpmDependencies rpmdep, Header h, void * key) {
  253.     /* this is an install followed by uninstalls */
  254.     dbiIndexSet matches;
  255.     char * name;
  256.     int count, i, j;
  257.     char ** obsoletes;
  258.  
  259.     alAddPackage(&rpmdep->addedPackages, h, key);
  260.  
  261.     if (!rpmdep->db) return;
  262.  
  263.     headerGetEntry(h, RPMTAG_NAME, NULL, (void *) &name, &count);
  264.  
  265.     if (!rpmdbFindPackage(rpmdep->db, name, &matches))  {
  266.     for (i = 0; i < matches.count; i++) {
  267.         rpmdepRemovePackage(rpmdep, matches.recs[i].recOffset);
  268.     }
  269.  
  270.     dbiFreeIndexRecord(matches);
  271.     }
  272.  
  273.     if (headerGetEntry(h, RPMTAG_OBSOLETES, NULL, (void *) &obsoletes, 
  274.             &count)) {
  275.     for (j = 0; j < count; j++) {
  276.         if (!rpmdbFindPackage(rpmdep->db, obsoletes[j], &matches))  {
  277.         for (i = 0; i < matches.count; i++) {
  278.             rpmdepRemovePackage(rpmdep, matches.recs[i].recOffset);
  279.         }
  280.  
  281.         dbiFreeIndexRecord(matches);
  282.         }
  283.     }
  284.  
  285.     free(obsoletes);
  286.     }
  287. }
  288.  
  289. void rpmdepAddPackage(rpmDependencies rpmdep, Header h, void * key) {
  290.     alAddPackage(&rpmdep->addedPackages, h, key);
  291. }
  292.  
  293. void rpmdepAvailablePackage(rpmDependencies rpmdep, Header h, void * key) {
  294.     alAddPackage(&rpmdep->availablePackages, h, key);
  295. }
  296.  
  297. void rpmdepRemovePackage(rpmDependencies rpmdep, int dboffset) {
  298.     if (rpmdep->numRemovedPackages == rpmdep->allocedRemovedPackages) {
  299.     rpmdep->allocedRemovedPackages += 5;
  300.     rpmdep->removedPackages = realloc(rpmdep->removedPackages,
  301.         sizeof(int *) * rpmdep->allocedRemovedPackages);
  302.     }
  303.  
  304.     rpmdep->removedPackages[rpmdep->numRemovedPackages++] = dboffset;
  305. }
  306.  
  307. void rpmdepDone(rpmDependencies rpmdep) {
  308.     alFree(&rpmdep->addedPackages);
  309.     alFree(&rpmdep->availablePackages);
  310.     free(rpmdep->removedPackages);
  311.  
  312.     free(rpmdep);
  313. }
  314.  
  315. void rpmdepFreeConflicts(struct rpmDependencyConflict * conflicts, int
  316.              numConflicts) {
  317.     int i;
  318.  
  319.     for (i = 0; i < numConflicts; i++) {
  320.     free(conflicts[i].byName);
  321.     free(conflicts[i].byVersion);
  322.     free(conflicts[i].byRelease);
  323.     free(conflicts[i].needsName);
  324.     free(conflicts[i].needsVersion);
  325.     }
  326.  
  327.     free(conflicts);
  328. }
  329.  
  330. int rpmdepCheck(rpmDependencies rpmdep, 
  331.         struct rpmDependencyConflict ** conflicts, int * numConflicts) {
  332.     struct availablePackage * p;
  333.     int i, j;
  334.     char ** provides, ** files;
  335.     int providesCount, fileCount;
  336.     int type;
  337.     char * name;
  338.     Header h;
  339.     struct problemsSet ps;
  340.  
  341.     ps.alloced = 5;
  342.     ps.num = 0;
  343.     ps.problems = malloc(sizeof(struct rpmDependencyConflict) * ps.alloced);
  344.  
  345.     *conflicts = NULL;
  346.     *numConflicts = 0;
  347.  
  348.     qsort(rpmdep->removedPackages, rpmdep->numRemovedPackages,
  349.       sizeof(int), intcmp);
  350.  
  351.     alMakeIndex(&rpmdep->addedPackages);
  352.     alMakeIndex(&rpmdep->availablePackages);
  353.     
  354.     /* look at all of the added packages and make sure their dependencies
  355.        are satisfied */
  356.     p = rpmdep->addedPackages.list;
  357.     for (i = 0; i < rpmdep->addedPackages.size; i++, p++) {
  358.     if (checkPackageDeps(rpmdep, &ps, p->h, NULL)) {
  359.         free(ps.problems);
  360.         return 1;
  361.     }
  362.     if (checkDependentConflicts(rpmdep, &ps, p->name)) {
  363.         free(ps.problems);
  364.         return 1;
  365.     }
  366.  
  367.     if (headerGetEntry(p->h, RPMTAG_PROVIDES, &type, (void **) &provides, 
  368.          &providesCount)) {
  369.         for (j = 0; j < providesCount; j++) {
  370.         if (checkDependentConflicts(rpmdep, &ps, provides[j])) {
  371.             free(ps.problems);
  372.             return 1;
  373.         }
  374.         }
  375.     }
  376.     }
  377.  
  378.     /* now look at the removed packages and make sure they aren't critical */
  379.     for (i = 0; i < rpmdep->numRemovedPackages; i++) {
  380.     h = rpmdbGetRecord(rpmdep->db, rpmdep->removedPackages[i]);
  381.     if (!h) {
  382.         rpmError(RPMERR_DBCORRUPT, 
  383.             "cannot read header at %d for dependency "
  384.           "check", rpmdep->removedPackages[i]);
  385.         free(ps.problems);
  386.         return 1;
  387.     }
  388.     
  389.     headerGetEntry(h, RPMTAG_NAME, &type, (void **) &name, &providesCount);
  390.  
  391.     if (checkDependentPackages(rpmdep, &ps, name)) {
  392.         free(ps.problems);
  393.         headerFree(h);
  394.         return 1;
  395.     }
  396.  
  397.     if (headerGetEntry(h, RPMTAG_PROVIDES, NULL, (void **) &provides, 
  398.          &providesCount)) {
  399.         for (j = 0; j < providesCount; j++) {
  400.         if (checkDependentPackages(rpmdep, &ps, provides[j])) {
  401.             free(provides);
  402.             free(ps.problems);
  403.             headerFree(h);
  404.             return 1;
  405.         }
  406.         }
  407.  
  408.         free(provides);
  409.     }
  410.  
  411.     if (headerGetEntry(h, RPMTAG_FILENAMES, NULL, (void **) &files, 
  412.          &fileCount)) {
  413.         for (j = 0; j < fileCount; j++) {
  414.         if (checkDependentPackages(rpmdep, &ps, files[j])) {
  415.             free(files);
  416.             free(ps.problems);
  417.             headerFree(h);
  418.             return 1;
  419.         }
  420.         }
  421.  
  422.         free(files);
  423.     }
  424.  
  425.     headerFree(h);
  426.     }
  427.  
  428.     if (!ps.num) 
  429.     free(ps.problems);
  430.     else  {
  431.     *conflicts = ps.problems;
  432.     *numConflicts = ps.num;
  433.     }
  434.  
  435.     return 0;
  436. }
  437.  
  438. /* 2 == error */
  439. /* 1 == dependency not satisfied */
  440. static int unsatisfiedDepend(rpmDependencies rpmdep, char * reqName, 
  441.                  char * reqVersion, int reqFlags, 
  442.                  struct availablePackage ** suggestion) {
  443.     dbiIndexSet matches;
  444.     int i;
  445.     char * rcProvidesString;
  446.     char * start;
  447.     
  448.     rpmMessage(RPMMESS_DEBUG, "dependencies: looking for %s\n", reqName);
  449.  
  450.     if (suggestion) *suggestion = NULL;
  451.  
  452.     if (!(reqFlags & RPMSENSE_SENSEMASK) &&
  453.     (rcProvidesString = rpmGetVar(RPMVAR_PROVIDES))) {
  454.     i = strlen(reqName);
  455.     while ((start = strstr(rcProvidesString, reqName))) {
  456.         if (isspace(start[i]) || !start[i])
  457.         return 0;
  458.         start += i;
  459.     }
  460.     }
  461.  
  462.     if (alSatisfiesDepend(&rpmdep->addedPackages, reqName, reqVersion, 
  463.               reqFlags))
  464.     return 0;
  465.  
  466.     if (rpmdep->db) {
  467.     if (*reqName == '/') {
  468.         /* reqFlags better be 0! */
  469.         if (!rpmdbFindByFile(rpmdep->db, reqName, &matches)) {
  470.         for (i = 0; i < matches.count; i++) {
  471.             if (bsearch(&matches.recs[i].recOffset, 
  472.                 rpmdep->removedPackages, 
  473.                 rpmdep->numRemovedPackages, 
  474.                 sizeof(int), intcmp)) 
  475.             continue;
  476.             break;
  477.         }
  478.  
  479.         dbiFreeIndexRecord(matches);
  480.         if (i < matches.count) return 0;
  481.         }
  482.     } else {
  483.         if (!reqFlags && !rpmdbFindByProvides(rpmdep->db, reqName, 
  484.                           &matches)) {
  485.         for (i = 0; i < matches.count; i++) {
  486.             if (bsearch(&matches.recs[i].recOffset, 
  487.                 rpmdep->removedPackages, 
  488.                 rpmdep->numRemovedPackages, 
  489.                 sizeof(int), intcmp)) 
  490.             continue;
  491.             break;
  492.         }
  493.  
  494.         dbiFreeIndexRecord(matches);
  495.         if (i < matches.count) return 0;
  496.         }
  497.  
  498.         if (!rpmdbFindPackage(rpmdep->db, reqName, &matches)) {
  499.         for (i = 0; i < matches.count; i++) {
  500.             if (bsearch(&matches.recs[i].recOffset, 
  501.                 rpmdep->removedPackages, 
  502.                 rpmdep->numRemovedPackages, 
  503.                 sizeof(int), intcmp)) 
  504.             continue;
  505.  
  506.             if (dbrecMatchesDepFlags(rpmdep, matches.recs[i].recOffset, 
  507.                          reqVersion, reqFlags)) {
  508.             break;
  509.             }
  510.         }
  511.  
  512.         dbiFreeIndexRecord(matches);
  513.         if (i < matches.count) return 0;
  514.         }
  515.     }
  516.     }
  517.  
  518.     if (suggestion) 
  519.     *suggestion = alSatisfiesDepend(&rpmdep->availablePackages, reqName, 
  520.                     reqVersion, reqFlags);
  521.  
  522.     return 1;
  523. }
  524.  
  525. static int checkPackageSet(rpmDependencies rpmdep, struct problemsSet * psp, 
  526.                 char * package, dbiIndexSet * matches) {
  527.     int i;
  528.     Header h;
  529.  
  530.     for (i = 0; i < matches->count; i++) {
  531.     if (bsearch(&matches->recs[i].recOffset, rpmdep->removedPackages, 
  532.             rpmdep->numRemovedPackages, sizeof(int), intcmp)) 
  533.         continue;
  534.  
  535.     h = rpmdbGetRecord(rpmdep->db, matches->recs[i].recOffset);
  536.     if (!h) {
  537.         rpmError(RPMERR_DBCORRUPT, "cannot read header at %d for dependency "
  538.           "check", rpmdep->removedPackages[i]);
  539.         return 1;
  540.     }
  541.  
  542.     if (checkPackageDeps(rpmdep, psp, h, package)) {
  543.         headerFree(h);
  544.         return 1;
  545.     }
  546.  
  547.     headerFree(h);
  548.     }
  549.  
  550.     return 0;
  551. }
  552.  
  553. static int checkDependentPackages(rpmDependencies rpmdep, 
  554.                 struct problemsSet * psp, char * key) {
  555.     dbiIndexSet matches;
  556.     int rc;
  557.  
  558.     if (rpmdbFindByRequiredBy(rpmdep->db, key, &matches))  {
  559.     return 0;
  560.     }
  561.  
  562.     rc = checkPackageSet(rpmdep, psp, key, &matches);
  563.     dbiFreeIndexRecord(matches);
  564.  
  565.     return rc;
  566. }
  567.  
  568. static int checkDependentConflicts(rpmDependencies rpmdep, 
  569.                 struct problemsSet * psp, char * package) {
  570.     dbiIndexSet matches;
  571.     int rc;
  572.  
  573.     if (!rpmdep->db) return 0;
  574.  
  575.     if (rpmdbFindByConflicts(rpmdep->db, package, &matches)) {
  576.     return 0;
  577.     }
  578.  
  579.     rc = checkPackageSet(rpmdep, psp, package, &matches);
  580.  
  581.     return rc;
  582. }
  583.  
  584. static int checkPackageDeps(rpmDependencies rpmdep, struct problemsSet * psp,
  585.             Header h, const char * requirement) {
  586.     char ** requires, ** requiresVersion;
  587.     char * name, * version, * release;
  588.     char ** conflicts, ** conflictsVersion;
  589.     int requiresCount = 0, conflictsCount;
  590.     int type, count;
  591.     int i, rc;
  592.     int ourrc = 0;
  593.     int * requireFlags, * conflictsFlags;
  594.     struct availablePackage * suggestion;
  595.  
  596.     if (!headerGetEntry(h, RPMTAG_REQUIRENAME, &type, (void **) &requires, 
  597.          &requiresCount)) {
  598.     requiresCount = 0;
  599.     } else {
  600.     headerGetEntry(h, RPMTAG_REQUIREFLAGS, &type, (void **) &requireFlags, 
  601.          &requiresCount);
  602.     headerGetEntry(h, RPMTAG_REQUIREVERSION, &type, 
  603.             (void **) &requiresVersion, 
  604.          &requiresCount);
  605.     }
  606.  
  607.     if (!headerGetEntry(h, RPMTAG_CONFLICTNAME, &type, (void **) &conflicts,
  608.          &conflictsCount)) {
  609.     conflictsCount = 0;
  610.     } else {
  611.     headerGetEntry(h, RPMTAG_CONFLICTFLAGS, &type, 
  612.             (void **) &conflictsFlags, &conflictsCount);
  613.     headerGetEntry(h, RPMTAG_CONFLICTVERSION, &type,
  614.             (void **) &conflictsVersion, 
  615.          &conflictsCount);
  616.     }
  617.  
  618.     for (i = 0; i < requiresCount && !ourrc; i++) {
  619.     if (requirement && strcmp(requirement, requires[i])) continue;
  620.  
  621.     rc = unsatisfiedDepend(rpmdep, requires[i], requiresVersion[i], 
  622.                    requireFlags[i], &suggestion);
  623.     if (rc == 1) {
  624.         headerGetEntry(h, RPMTAG_NAME, &type, (void **) &name, &count);
  625.         headerGetEntry(h, RPMTAG_VERSION, &type, (void **) &version, 
  626.                 &count);
  627.         headerGetEntry(h, RPMTAG_RELEASE, &type, (void **) &release, 
  628.                 &count);
  629.  
  630.         rpmMessage(RPMMESS_DEBUG, "package %s require not satisfied: %s\n",
  631.             name, requires[i]);
  632.         
  633.         if (psp->num == psp->alloced) {
  634.         psp->alloced += 5;
  635.         psp->problems = realloc(psp->problems, sizeof(*psp->problems) * 
  636.                 psp->alloced);
  637.         }
  638.         psp->problems[psp->num].byName = strdup(name);
  639.         psp->problems[psp->num].byVersion = strdup(version);
  640.         psp->problems[psp->num].byRelease = strdup(release);
  641.         psp->problems[psp->num].needsName = strdup(requires[i]);
  642.         psp->problems[psp->num].needsVersion = strdup(requiresVersion[i]);
  643.         psp->problems[psp->num].needsFlags = requireFlags[i];
  644.         psp->problems[psp->num].sense = RPMDEP_SENSE_REQUIRES;
  645.  
  646.         if (suggestion)
  647.         psp->problems[psp->num].suggestedPackage = suggestion->key;
  648.         else
  649.         psp->problems[psp->num].suggestedPackage = NULL;
  650.  
  651.         psp->num++;
  652.     } else if (rc == 2) {
  653.         /* something went wrong! */
  654.         ourrc = 1;
  655.     }
  656.     }
  657.  
  658.     for (i = 0; i < conflictsCount && !ourrc; i++) {
  659.     if (requirement && strcmp(requirement, conflicts[i])) continue;
  660.  
  661.     rc = unsatisfiedDepend(rpmdep, conflicts[i], conflictsVersion[i], 
  662.                    conflictsFlags[i], NULL);
  663.  
  664.     /* 1 == unsatisfied, 0 == satsisfied */
  665.     if (rc == 0) {
  666.         headerGetEntry(h, RPMTAG_NAME, &type, (void **) &name, &count);
  667.         headerGetEntry(h, RPMTAG_VERSION, &type, (void **) &version, 
  668.                 &count);
  669.         headerGetEntry(h, RPMTAG_RELEASE, &type, (void **) &release, 
  670.                 &count);
  671.  
  672.         rpmMessage(RPMMESS_DEBUG, "package %s conflicts: %s\n",
  673.             name, conflicts[i]);
  674.         
  675.         if (psp->num == psp->alloced) {
  676.         psp->alloced += 5;
  677.         psp->problems = realloc(psp->problems, sizeof(*psp->problems) * 
  678.                 psp->alloced);
  679.         }
  680.         psp->problems[psp->num].byName = strdup(name);
  681.         psp->problems[psp->num].byVersion = strdup(version);
  682.         psp->problems[psp->num].byRelease = strdup(release);
  683.         psp->problems[psp->num].needsName = strdup(conflicts[i]);
  684.         psp->problems[psp->num].needsVersion = strdup(conflictsVersion[i]);
  685.         psp->problems[psp->num].needsFlags = conflictsFlags[i];
  686.         psp->problems[psp->num].sense = RPMDEP_SENSE_CONFLICTS;
  687.         psp->problems[psp->num].suggestedPackage = NULL;
  688.  
  689.         psp->num++;
  690.     } else if (rc == 2) {
  691.         /* something went wrong! */
  692.         ourrc = 1;
  693.     }
  694.     }
  695.  
  696.     if (conflictsCount) {
  697.     free(conflictsVersion);
  698.     free(conflicts);
  699.     }
  700.  
  701.     if (requiresCount) {
  702.     free(requiresVersion);
  703.     free(requires);
  704.     }
  705.  
  706.     return ourrc;
  707. }
  708.  
  709. static int headerMatchesDepFlags(Header h, char * reqInfo, int reqFlags) {
  710.     char * name, * version, * release, * chptr;
  711.     char * reqVersion = reqInfo;
  712.     char * reqRelease = NULL;
  713.     int type, count;
  714.     int_32 serial;
  715.     char buf[20];
  716.     int result = 0;
  717.     int sense;
  718.  
  719.     headerGetEntry(h, RPMTAG_NAME, &type, (void *) &name, &count);
  720.  
  721.     if (!(reqFlags & RPMSENSE_SENSEMASK)) {
  722.     return 1;
  723.     }
  724.  
  725.     if (reqFlags & RPMSENSE_SERIAL) {
  726.     if (!headerGetEntry(h, RPMTAG_SERIAL, &type, (void *) &serial, &count)) {
  727.         headerFree(h);
  728.         return 0;
  729.     }
  730.     sprintf(buf, "%d", serial);
  731.     version = buf;
  732.     } else {
  733.     headerGetEntry(h, RPMTAG_VERSION, &type, (void *) &version, &count);
  734.     chptr = strrchr(reqInfo, '-');
  735.     if (chptr) {
  736.         reqVersion = alloca(strlen(reqInfo) + 1);
  737.         strcpy(reqVersion, reqInfo);
  738.         reqVersion[chptr - reqInfo] = '\0';
  739.         reqRelease = reqVersion + (chptr - reqInfo) + 1;
  740.         if (*reqRelease) 
  741.         headerGetEntry(h, RPMTAG_RELEASE, &type, (void *) &release, &count);
  742.         else
  743.         reqRelease = NULL;
  744.     }
  745.     }
  746.  
  747.     sense = rpmvercmp(version, reqVersion);
  748.     if (!sense && reqRelease) {
  749.     /* if a release number is given, use it to break ties */
  750.     sense = rpmvercmp(release, reqRelease);
  751.     }
  752.  
  753.     if ((reqFlags & RPMSENSE_LESS) && sense < 0) {
  754.     result = 1;
  755.     } else if ((reqFlags & RPMSENSE_EQUAL) && sense == 0) {
  756.     result = 1;
  757.     } else if ((reqFlags & RPMSENSE_GREATER) && sense > 0) {
  758.     result = 1;
  759.     }
  760.  
  761.     return result;
  762. }
  763.  
  764. static int dbrecMatchesDepFlags(rpmDependencies rpmdep, int recOffset, 
  765.                     char * reqVersion, int reqFlags) {
  766.     Header h;
  767.     int rc;
  768.  
  769.     h = rpmdbGetRecord(rpmdep->db, recOffset);
  770.     if (!h) {
  771.     rpmMessage(RPMMESS_DEBUG, "dbrecMatchesDepFlags() failed to read header");
  772.     return 0;
  773.     }
  774.  
  775.     rc = headerMatchesDepFlags(h, reqVersion, reqFlags);
  776.  
  777.     headerFree(h);
  778.  
  779.     return rc;
  780. }
  781.  
  782. static int addOrderedPack(rpmDependencies rpmdep, 
  783.             struct availablePackage * package,
  784.             void ** ordering, int * orderNumPtr, 
  785.             enum selectionStatus * selected, 
  786.             int satisfyDepends, char ** errorStack) {
  787.     char ** requires, ** requiresVersion;
  788.     int_32 * requireFlags;
  789.     int requiresCount;
  790.     int packageNum = package - rpmdep->addedPackages.list;
  791.     int i;
  792.     struct availablePackage * match;
  793.     char * errorString;
  794.     char ** stack;
  795.  
  796.     *errorStack++ = package->name;
  797.  
  798.     if (selected[packageNum] == INPROCESS) {
  799.     i = 0;
  800.     stack = errorStack - 1;
  801.     while (*(--stack)) {
  802.         i += strlen(*stack) + 1;
  803.     }
  804.  
  805.     errorString = alloca(i + 2);
  806.     *errorString = '\0';
  807.     
  808.     while ((++stack) < errorStack) {
  809.         strcat(errorString, *stack);
  810.         strcat(errorString, " ");
  811.     }
  812.     
  813.     rpmError(RPMMESS_PREREQLOOP, "loop in prerequisite chain: %s",
  814.          errorString);
  815.  
  816.     return 1;
  817.     }
  818.  
  819.     selected[packageNum] = INPROCESS;
  820.  
  821.     if (headerGetEntry(package->h, RPMTAG_REQUIRENAME, NULL, 
  822.             (void **) &requires, &requiresCount)) {
  823.     headerGetEntry(package->h, RPMTAG_REQUIREFLAGS, NULL, 
  824.             (void **) &requireFlags, NULL);
  825.     headerGetEntry(package->h, RPMTAG_REQUIREVERSION, NULL, 
  826.             (void **) &requiresVersion, NULL);
  827.  
  828.     for (i = 0; i < requiresCount; i++) {
  829.         if (satisfyDepends || (requireFlags[i] & RPMSENSE_PREREQ)) {
  830.         match = alSatisfiesDepend(&rpmdep->addedPackages,
  831.                       requires[i], requiresVersion[i],
  832.                       requireFlags[i]);
  833.         /* broken dependencies don't concern us */
  834.         if (!match) continue;
  835.         
  836.         /* let this package satisfy its own predependencies */
  837.         if (match == package) continue;
  838.  
  839.         /* the package has already been selected */
  840.         if (selected[match - rpmdep->addedPackages.list] == SELECTED)
  841.             continue;
  842.  
  843.         if (addOrderedPack(rpmdep, match, ordering, orderNumPtr,
  844.                    selected, 1, errorStack)) return 1;
  845.         }
  846.     }
  847.     }
  848.  
  849.     /* whew -- add this package */
  850.     ordering[(*orderNumPtr)++] = package->key;
  851.     selected[packageNum] = SELECTED;
  852.  
  853.     return 0;
  854. }
  855.  
  856. int rpmdepOrder(rpmDependencies rpmdep, void *** keysListPtr) {
  857.     int i;
  858.     enum selectionStatus * selected;
  859.     void ** order;
  860.     int orderNum;
  861.     char ** errorStack;
  862.  
  863.     alMakeIndex(&rpmdep->addedPackages);
  864.     alMakeIndex(&rpmdep->availablePackages);
  865.  
  866.     selected = alloca(sizeof(*selected) * rpmdep->addedPackages.size);
  867.     memset(selected, 0, sizeof(*selected) * rpmdep->addedPackages.size);
  868.  
  869.     errorStack = alloca(sizeof(*errorStack) * (rpmdep->addedPackages.size + 1));
  870.     *errorStack++ = NULL;
  871.  
  872.     order = malloc(sizeof(*order) * (rpmdep->addedPackages.size + 1));
  873.     orderNum = 0;
  874.  
  875.     for (i = 0; i < rpmdep->addedPackages.size; i++) {
  876.     if (selected[i] == UNSELECTED) {
  877.         if (addOrderedPack(rpmdep, rpmdep->addedPackages.list + i,
  878.                    order, &orderNum, selected, 0, errorStack)) {
  879.         free(order);
  880.         return 1;
  881.         }
  882.     }
  883.     }
  884.  
  885.     order[orderNum] = NULL;
  886.     *keysListPtr = order;
  887.  
  888.     return 0;
  889. }
  890.