match.c revision 178103 
1/*
2 * FreeBSD install - a package for the installation and maintainance
3 * of non-core utilities.
4 *
5 * Redistribution and use in source and binary forms, with or without
6 * modification, are permitted provided that the following conditions
7 * are met:
8 * 1. Redistributions of source code must retain the above copyright
9 *    notice, this list of conditions and the following disclaimer.
10 * 2. Redistributions in binary form must reproduce the above copyright
11 *    notice, this list of conditions and the following disclaimer in the
12 *    documentation and/or other materials provided with the distribution.
13 *
14 * Maxim Sobolev
15 * 24 February 2001
16 *
17 * Routines used to query installed packages.
18 *
19 */
20
21#include <sys/cdefs.h>
22__FBSDID("$FreeBSD: head/usr.sbin/pkg_install/lib/match.c 178103 2008-04-11 08:26:06Z pav $");
23
24#include "lib.h"
25#include <err.h>
26#include <fnmatch.h>
27#include <fts.h>
28#include <regex.h>
29
30/*
31 * Simple structure representing argv-like
32 * NULL-terminated list.
33 */
34struct store {
35    int currlen;
36    int used;
37    char **store;
38};
39
40static int rex_match(const char *, const char *, int);
41static int csh_match(const char *, const char *, int);
42struct store *storecreate(struct store *);
43static int storeappend(struct store *, const char *);
44static int fname_cmp(const FTSENT * const *, const FTSENT * const *);
45
46/*
47 * Function to query names of installed packages.
48 * MatchType	- one of MATCH_ALL, MATCH_EREGEX, MATCH_REGEX, MATCH_GLOB, MATCH_NGLOB;
49 * patterns	- NULL-terminated list of glob or regex patterns
50 *		  (could be NULL for MATCH_ALL);
51 * retval	- return value (could be NULL if you don't want/need
52 *		  return value).
53 * Returns NULL-terminated list with matching names.
54 * Names in list returned are dynamically allocated and should
55 * not be altered by the caller.
56 */
57char **
58matchinstalled(match_t MatchType, char **patterns, int *retval)
59{
60    int i, errcode, len;
61    char *matched;
62    const char *paths[2] = {LOG_DIR, NULL};
63    static struct store *store = NULL;
64    FTS *ftsp;
65    FTSENT *f;
66    Boolean *lmatched = NULL;
67
68    store = storecreate(store);
69    if (store == NULL) {
70	if (retval != NULL)
71	    *retval = 1;
72	return NULL;
73    }
74
75    if (retval != NULL)
76	*retval = 0;
77
78    if (!isdir(paths[0])) {
79	if (retval != NULL)
80	    *retval = 1;
81	return NULL;
82	/* Not reached */
83    }
84
85    /* Count number of patterns */
86    if (patterns != NULL) {
87	for (len = 0; patterns[len]; len++) {}
88	lmatched = alloca(sizeof(*lmatched) * len);
89	if (lmatched == NULL) {
90	    warnx("%s(): alloca() failed", __func__);
91	    if (retval != NULL)
92		*retval = 1;
93	    return NULL;
94    	}
95    } else
96	len = 0;
97
98    for (i = 0; i < len; i++)
99	lmatched[i] = FALSE;
100
101    ftsp = fts_open((char * const *)(uintptr_t)paths, FTS_LOGICAL | FTS_NOCHDIR | FTS_NOSTAT, fname_cmp);
102    if (ftsp != NULL) {
103	while ((f = fts_read(ftsp)) != NULL) {
104	    if (f->fts_info == FTS_D && f->fts_level == 1) {
105		fts_set(ftsp, f, FTS_SKIP);
106		matched = NULL;
107		errcode = 0;
108		if (MatchType == MATCH_ALL)
109		    matched = f->fts_name;
110		else
111		    for (i = 0; patterns[i]; i++) {
112			errcode = pattern_match(MatchType, patterns[i], f->fts_name);
113			if (errcode == 1) {
114			    matched = f->fts_name;
115			    lmatched[i] = TRUE;
116			    errcode = 0;
117			}
118			if (matched != NULL || errcode != 0)
119			    break;
120		    }
121		if (errcode == 0 && matched != NULL)
122		    errcode = storeappend(store, matched);
123		if (errcode != 0) {
124		    if (retval != NULL)
125			*retval = 1;
126		    return NULL;
127		    /* Not reached */
128		}
129	    }
130	}
131	fts_close(ftsp);
132    }
133
134    if (MatchType == MATCH_GLOB) {
135	for (i = 0; i < len; i++)
136	    if (lmatched[i] == FALSE)
137		storeappend(store, patterns[i]);
138    }
139
140    if (store->used == 0)
141	return NULL;
142    else
143	return store->store;
144}
145
146int
147pattern_match(match_t MatchType, char *pattern, const char *pkgname)
148{
149    int errcode = 0;
150    const char *fname = pkgname;
151    char basefname[PATH_MAX];
152    char condchar = '\0';
153    char *condition;
154
155    /* do we have an appended condition? */
156    condition = strpbrk(pattern, "<>=");
157    if (condition) {
158	const char *ch;
159	/* yes, isolate the pattern from the condition ... */
160	if (condition > pattern && condition[-1] == '!')
161	    condition--;
162	condchar = *condition;
163	*condition = '\0';
164	/* ... and compare the name without version */
165	ch = strrchr(fname, '-');
166	if (ch && ch - fname < PATH_MAX) {
167	    strlcpy(basefname, fname, ch - fname + 1);
168	    fname = basefname;
169	}
170    }
171
172    switch (MatchType) {
173    case MATCH_EREGEX:
174    case MATCH_REGEX:
175	errcode = rex_match(pattern, fname, MatchType == MATCH_EREGEX ? 1 : 0);
176	break;
177    case MATCH_NGLOB:
178    case MATCH_GLOB:
179	errcode = (csh_match(pattern, fname, 0) == 0) ? 1 : 0;
180	break;
181    case MATCH_EXACT:
182	errcode = (strcmp(pattern, fname) == 0) ? 1 : 0;
183	break;
184    case MATCH_ALL:
185	errcode = 1;
186	break;
187    default:
188	break;
189    }
190
191    /* loop over all appended conditions */
192    while (condition) {
193	/* restore the pattern */
194	*condition = condchar;
195	/* parse the condition (fun with bits) */
196	if (errcode == 1) {
197	    char *nextcondition;
198	    /* compare version numbers */
199	    int match = 0;
200	    if (*++condition == '=') {
201		match = 2;
202		condition++;
203	    }
204	    switch(condchar) {
205	    case '<':
206		match |= 1;
207		break;
208	    case '>':
209		match |= 4;
210		break;
211	    case '=':
212		match |= 2;
213		break;
214	    case '!':
215		match = 5;
216		break;
217	    }
218	    /* isolate the version number from the next condition ... */
219	    nextcondition = strpbrk(condition, "<>=!");
220	    if (nextcondition) {
221		condchar = *nextcondition;
222		*nextcondition = '\0';
223	    }
224	    /* and compare the versions (version_cmp removes the filename for us) */
225	    if ((match & (1 << (version_cmp(pkgname, condition) + 1))) == 0)
226		errcode = 0;
227	    condition = nextcondition;
228	} else {
229	    break;
230	}
231    }
232
233    return errcode;
234}
235
236/*
237 * Synopsis is similar to matchinstalled(), but use origin
238 * as a key for matching packages.
239 */
240char **
241matchallbyorigin(const char **origins, int *retval)
242{
243    char **installed, **allorigins = NULL, **matches = NULL;
244    int i, j;
245
246    if (retval != NULL)
247	*retval = 0;
248
249    installed = matchinstalled(MATCH_ALL, NULL, retval);
250    if (installed == NULL)
251	return NULL;
252
253    /* Gather origins for all installed packages */
254    for (i = 0; installed[i] != NULL; i++) {
255	FILE *fp;
256	char *buf, *cp, tmp[PATH_MAX];
257	int cmd;
258
259	allorigins = realloc(allorigins, (i + 1) * sizeof(*allorigins));
260	allorigins[i] = NULL;
261
262	snprintf(tmp, PATH_MAX, "%s/%s", LOG_DIR, installed[i]);
263	/*
264	 * SPECIAL CASE: ignore empty dirs, since we can can see them
265	 * during port installation.
266	 */
267	if (isemptydir(tmp))
268	    continue;
269	snprintf(tmp, PATH_MAX, "%s/%s", tmp, CONTENTS_FNAME);
270	fp = fopen(tmp, "r");
271	if (fp == NULL) {
272	    warnx("the package info for package '%s' is corrupt", installed[i]);
273	    continue;
274	}
275
276	cmd = -1;
277	while (fgets(tmp, sizeof(tmp), fp)) {
278	    int len = strlen(tmp);
279
280	    while (len && isspace(tmp[len - 1]))
281		tmp[--len] = '\0';
282	    if (!len)
283		continue;
284	    cp = tmp;
285	    if (tmp[0] != CMD_CHAR)
286		continue;
287	    cmd = plist_cmd(tmp + 1, &cp);
288	    if (cmd == PLIST_ORIGIN) {
289		asprintf(&buf, "%s", cp);
290		allorigins[i] = buf;
291		break;
292	    }
293	}
294	if (cmd != PLIST_ORIGIN && ( Verbose || 0 != strncmp("bsdpan-", installed[i], 7 ) ) )
295	    warnx("package %s has no origin recorded", installed[i]);
296	fclose(fp);
297    }
298
299    /* Resolve origins into package names, retaining the sequence */
300    for (i = 0; origins[i] != NULL; i++) {
301	matches = realloc(matches, (i + 1) * sizeof(*matches));
302	matches[i] = NULL;
303
304	for (j = 0; installed[j] != NULL; j++) {
305	    if (allorigins[j]) {
306		if (csh_match(origins[i], allorigins[j], FNM_PATHNAME) == 0) {
307		    matches[i] = installed[j];
308		    break;
309		}
310	    }
311	}
312    }
313
314    if (allorigins) {
315	for (i = 0; installed[i] != NULL; i++)
316	    if (allorigins[i])
317		free(allorigins[i]);
318	free(allorigins);
319    }
320
321    return matches;
322}
323
324/*
325 * Synopsis is similar to matchinstalled(), but use origin
326 * as a key for matching packages.
327 */
328char **
329matchbyorigin(const char *origin, int *retval)
330{
331   const char *origins[2];
332   char **tmp;
333
334   origins[0] = origin;
335   origins[1] = NULL;
336
337   tmp = matchallbyorigin(origins, retval);
338   if (tmp && tmp[0]) {
339	tmp = realloc(tmp, 2 * sizeof(*tmp));
340	tmp[1] = NULL;
341	return tmp;
342   } else {
343	return NULL;
344   }
345}
346
347/*
348 * Small linked list to memoize results of isinstalledpkg().  A hash table
349 * would be faster but for n ~= 1000 may be overkill.
350 */
351struct iip_memo {
352	LIST_ENTRY(iip_memo) iip_link;
353	char	*iip_name;
354	int	 iip_result;
355};
356LIST_HEAD(, iip_memo) iip_memo = LIST_HEAD_INITIALIZER(iip_memo);
357
358/*
359 *
360 * Return 1 if the specified package is installed,
361 * 0 if not, and -1 if an error occured.
362 */
363int
364isinstalledpkg(const char *name)
365{
366    int result;
367    char *buf, *buf2;
368    struct iip_memo *memo;
369
370    LIST_FOREACH(memo, &iip_memo, iip_link) {
371	if (strcmp(memo->iip_name, name) == 0)
372	    return memo->iip_result;
373    }
374
375    buf2 = NULL;
376    asprintf(&buf, "%s/%s", LOG_DIR, name);
377    if (buf == NULL)
378	goto errout;
379    if (!isdir(buf) || access(buf, R_OK) == FAIL) {
380	result = 0;
381    } else {
382	asprintf(&buf2, "%s/%s", buf, CONTENTS_FNAME);
383	if (buf2 == NULL)
384	    goto errout;
385
386	if (!isfile(buf2) || access(buf2, R_OK) == FAIL)
387	    result = -1;
388	else
389	    result = 1;
390    }
391
392    free(buf);
393    buf = strdup(name);
394    if (buf == NULL)
395	goto errout;
396    free(buf2);
397    buf2 = NULL;
398
399    memo = malloc(sizeof *memo);
400    if (memo == NULL)
401	goto errout;
402    memo->iip_name = buf;
403    memo->iip_result = result;
404    LIST_INSERT_HEAD(&iip_memo, memo, iip_link);
405    return result;
406
407errout:
408    if (buf != NULL)
409	free(buf);
410    if (buf2 != NULL)
411	free(buf2);
412    return -1;
413}
414
415/*
416 * Returns 1 if specified pkgname matches RE pattern.
417 * Otherwise returns 0 if doesn't match or -1 if RE
418 * engine reported an error (usually invalid syntax).
419 */
420static int
421rex_match(const char *pattern, const char *pkgname, int extended)
422{
423    char errbuf[128];
424    int errcode;
425    int retval;
426    regex_t rex;
427
428    retval = 0;
429
430    errcode = regcomp(&rex, pattern, (extended ? REG_EXTENDED : REG_BASIC) | REG_NOSUB);
431    if (errcode == 0)
432	errcode = regexec(&rex, pkgname, 0, NULL, 0);
433
434    if (errcode == 0) {
435	retval = 1;
436    } else if (errcode != REG_NOMATCH) {
437	regerror(errcode, &rex, errbuf, sizeof(errbuf));
438	warnx("%s: %s", pattern, errbuf);
439	retval = -1;
440    }
441
442    regfree(&rex);
443
444    return retval;
445}
446
447/*
448 * Match string by a csh-style glob pattern. Returns 0 on
449 * match and FNM_NOMATCH otherwise, to be compatible with
450 * fnmatch(3).
451 */
452static int
453csh_match(const char *pattern, const char *string, int flags)
454{
455    int ret = FNM_NOMATCH;
456
457
458    const char *nextchoice = pattern;
459    const char *current = NULL;
460
461    int prefixlen = -1;
462    int currentlen = 0;
463
464    int level = 0;
465
466    do {
467	const char *pos = nextchoice;
468	const char *postfix = NULL;
469
470	Boolean quoted = FALSE;
471
472	nextchoice = NULL;
473
474	do {
475	    const char *eb;
476	    if (!*pos) {
477		postfix = pos;
478	    } else if (quoted) {
479		quoted = FALSE;
480	    } else {
481		switch (*pos) {
482		case '{':
483		    ++level;
484		    if (level == 1) {
485			current = pos+1;
486			prefixlen = pos-pattern;
487		    }
488		    break;
489		case ',':
490		    if (level == 1 && !nextchoice) {
491			nextchoice = pos+1;
492			currentlen = pos-current;
493		    }
494		    break;
495		case '}':
496		    if (level == 1) {
497			postfix = pos+1;
498			if (!nextchoice)
499			    currentlen = pos-current;
500		    }
501		    level--;
502		    break;
503		case '[':
504		    eb = pos+1;
505		    if (*eb == '!' || *eb == '^')
506			eb++;
507		    if (*eb == ']')
508			eb++;
509		    while(*eb && *eb != ']')
510			eb++;
511		    if (*eb)
512			pos=eb;
513		    break;
514		case '\\':
515		    quoted = TRUE;
516		    break;
517		default:
518		    ;
519		}
520	    }
521	    pos++;
522	} while (!postfix);
523
524	if (current) {
525	    char buf[FILENAME_MAX];
526	    snprintf(buf, sizeof(buf), "%.*s%.*s%s", prefixlen, pattern, currentlen, current, postfix);
527	    ret = csh_match(buf, string, flags);
528	    if (ret) {
529		current = nextchoice;
530		level = 1;
531	    } else
532		current = NULL;
533	} else
534	    ret = fnmatch(pattern, string, flags);
535    } while (current);
536
537    return ret;
538}
539
540/*
541 * Create an empty store, optionally deallocating
542 * any previously allocated space if store != NULL.
543 */
544struct store *
545storecreate(struct store *store)
546{
547    int i;
548
549    if (store == NULL) {
550	store = malloc(sizeof *store);
551	if (store == NULL) {
552	    warnx("%s(): malloc() failed", __func__);
553	    return NULL;
554	}
555	store->currlen = 0;
556	store->store = NULL;
557    } else if (store->store != NULL) {
558	    /* Free previously allocated memory */
559	    for (i = 0; store->store[i] != NULL; i++)
560		free(store->store[i]);
561	    store->store[0] = NULL;
562    }
563    store->used = 0;
564
565    return store;
566}
567
568/*
569 * Append specified element to the provided store.
570 */
571static int
572storeappend(struct store *store, const char *item)
573{
574    if (store->used + 2 > store->currlen) {
575	store->currlen += 16;
576	store->store = reallocf(store->store,
577				store->currlen * sizeof(*(store->store)));
578	if (store->store == NULL) {
579	    store->currlen = 0;
580	    warnx("%s(): reallocf() failed", __func__);
581	    return 1;
582	}
583    }
584
585    asprintf(&(store->store[store->used]), "%s", item);
586    if (store->store[store->used] == NULL) {
587	warnx("%s(): malloc() failed", __func__);
588	return 1;
589    }
590    store->used++;
591    store->store[store->used] = NULL;
592
593    return 0;
594}
595
596static int
597fname_cmp(const FTSENT * const *a, const FTSENT * const *b)
598{
599    return strcmp((*a)->fts_name, (*b)->fts_name);
600}
601