Skip to content

HTTPS clone URL

Subversion checkout URL

You can clone with HTTPS or Subversion.

Download ZIP
branch: master
Fetching contributors…

Cannot retrieve contributors at this time

306 lines (262 sloc) 6.591 kb
/* Fast package list solver.
*
* THIS IS A MESS. SORRY. I STILL NEED TO CLEAN IT UP.
*
* TODO:
* [ ] usage message
* [ ] default to release index file
*/
#include <stdlib.h>
#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include "strnatcmp.h"
enum OPER { lt, le, eq, ge, gt, st, err };
/* A package list entry. */
struct plent {
int found;
enum OPER oper;
char pack[100];
char vers[50];
struct plent *next;
};
/* Parse a comparison operator string and return the corresponding OPER
* value. The err value is returned if the string is not a valid operator.
*/
static inline enum OPER
operparse (char * oper)
{
enum OPER res = err;
if ( oper[0] == '<' ) {
if ( oper[1] == 0 ) {
res = lt;
} else if ( oper[1] == '=' ) {
res = le;
}
} else if ( oper[0] == '>' ) {
if ( oper[1] == 0 ) {
res = gt;
} else if ( oper[1] == '=' ) {
res = ge;
}
} else if ( oper[0] == '=' && oper[1] == 0 ) {
res = eq;
} else if ( oper[0] == '~' && oper[1] == '>' ) {
res = st;
}
return res;
}
/* Replace vers with its next successive version. */
inline void
versucc (char * vers) {
char *pdot = strrchr(vers, '.');
char *pend = NULL;
if ( pdot == NULL ) {
pdot = strrchr(vers, '\0');
*pdot = '.';
}
pdot++;
for (pend = pdot + 10; pdot < pend; pdot++)
*pdot = '9';
*pdot = '\0';
}
/* Normalize a version string by removing any trailing ".0" parts. This is
* required to for proper behavior when comparing versions like: "3.1 >= 3.1.0". */
static void
versnorm (char * vers)
{
char * pe = vers + strlen(vers) - 1;
while (pe > vers) {
if (*pe == '.') {
*pe = '\0';
pe--;
} else if (*pe == '0') {
pe--;
} else {
break;
}
}
return;
}
/* Expand squiggly comparisons into separate ge and lt comparisons. e.g.,
* foo ~> 0.2.3 would become foo >= 0.2.3 and foo < 0.3.*/
static void
plsquig (struct plent * pe)
{
struct plent * pnew;
while (pe) {
if (pe->oper != st) {
pe = pe->next;
continue;
}
pe->oper = ge;
pnew = malloc(sizeof(struct plent));
memcpy(pnew, pe, sizeof(struct plent));
pnew->oper = lt;
versucc(pnew->vers);
versnorm(pe->vers);
pe->next = pnew;
pe = pnew->next;
}
}
/* Parse a package list from the stream. */
static struct plent *
plparse (FILE * stream)
{
int res = 0, lineno = 0;
struct plent *pe, *ppe = NULL, *pfe = NULL;
char stroper[3];
const char * format = "%100s%*[ ]%2[~><=]%*[ ]%50s\n";
while (1) {
lineno++;
pe = malloc(sizeof(struct plent));
pe->found = 0;
pe->next = NULL;
res = fscanf(stream, format, pe->pack, stroper, pe->vers);
if ( res == 3 ) {
pe->oper = operparse(stroper);
} else {
free(pe);
break;
}
if ( ppe ) ppe->next = pe;
else pfe = pe;
ppe = pe;
}
plsquig(pfe);
return pfe;
}
/* Mark all package list entries whose package name matches pack as found. */
static inline void
plmark (struct plent * pe, char * pack)
{
int cmp;
for (; pe != NULL; pe = pe->next) {
cmp = strcmp(pe->pack, pack);
if (cmp == 0) {
pe->found = 1;
} else if (cmp < 0) {
continue;
} else {
break;
}
}
}
/* Remove entries marked as found from the list. */
static struct plent *
plpurge (struct plent * pe) {
struct plent * ptail = NULL,
* phead = NULL;
for (;pe != NULL; pe = pe->next) {
if ( pe->found ) continue;
if ( ptail )
ptail->next = pe;
else
phead = pe;
ptail = pe;
}
if (ptail) ptail->next = NULL;
return phead;
}
/* Compare two versions. */
static inline int
verscmp(char const * v1, char const * v2)
{
return strnatcmp(v1, v2);
}
/* Test if versions compare according to oper. */
static inline int
verstest(enum OPER oper, char const * v1, char const * v2)
{
int res = 0;
int cmp;
if (oper == eq) {
cmp = strcmp(v1, v2);
if (cmp == 0) res = 1;
} else {
cmp = verscmp(v1, v2);
if ((cmp == 0 && (oper == le || oper == ge)) ||
(cmp < 0 && (oper == lt || oper == le)) ||
(cmp > 0 && (oper == gt || oper == ge)))
res = 1;
}
return res;
}
/* Run over all package list entries with the same name as ppack and compare
* versions.
*/
static int
pdxrun(char * ppack, char * pvers, struct plent * pe)
{
while ( pe && strcmp(ppack, pe->pack) == 0 ) {
if (verstest(pe->oper, pvers, pe->vers)) {
pe = pe->next;
} else {
return 0;
}
}
return 1;
}
#define MAXLINE 256
static void
pdxscan(FILE * stream, struct plent * pe)
{
char line[MAXLINE];
char *ppack, *pvers;
int cmp;
while ( fgets(line, MAXLINE - 1, stream) ) {
if (pe->pack[0] > line[0]) continue;
pvers = line;
ppack = strsep(&pvers, " ");
while ((cmp = strcmp(pe->pack, ppack)) < 0) {
pe = pe->next;
if (pe == NULL) return;
}
if (cmp > 0) continue;
pvers = strsep(&pvers, " \n");
if (pdxrun(ppack, pvers, pe)) {
if ( pe->found == 0 )
plmark(pe, ppack);
printf("%s %s\n", ppack, pvers);
}
}
}
#ifdef DEBUG
static void
pldump (FILE * stream, struct plent * pe)
{
fprintf(stream, "dumping package list entries:\n");
while (pe) {
fprintf(stream, "plent: %s %d %s\n", pe->pack, pe->oper, pe->vers);
pe = pe->next;
}
}
#endif
int main (int argc, char *argv[])
{
struct plent * pe = plparse(stdin);
FILE * fidx;
int i;
for (i=1; i < argc; i++) {
/* pldump(stderr, pe) */
if (pe == NULL)
break;
if ((fidx = fopen(argv[i], "r"))) {
pdxscan(fidx, pe);
fclose(fidx);
} else {
fprintf(stderr, "%s: could not open: %s", argv[0], argv[i]);
exit(1);
}
pe = plpurge(pe);
}
/* some packages were not found */
if ( pe ) {
while ( pe ) {
printf("%s -\n", pe->pack);
pe = pe->next;
}
return 1;
}
return 0;
}
Jump to Line
Something went wrong with that request. Please try again.