Annotation of src/lib/libc/gen/glob.c, Revision 1.1.1.1
1.1 cgd 1: /*
2: * Copyright (c) 1989 The Regents of the University of California.
3: * All rights reserved.
4: *
5: * This code is derived from software contributed to Berkeley by
6: * Guido van Rossum.
7: *
8: * Redistribution and use in source and binary forms, with or without
9: * modification, are permitted provided that the following conditions
10: * are met:
11: * 1. Redistributions of source code must retain the above copyright
12: * notice, this list of conditions and the following disclaimer.
13: * 2. Redistributions in binary form must reproduce the above copyright
14: * notice, this list of conditions and the following disclaimer in the
15: * documentation and/or other materials provided with the distribution.
16: * 3. All advertising materials mentioning features or use of this software
17: * must display the following acknowledgement:
18: * This product includes software developed by the University of
19: * California, Berkeley and its contributors.
20: * 4. Neither the name of the University nor the names of its contributors
21: * may be used to endorse or promote products derived from this software
22: * without specific prior written permission.
23: *
24: * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
25: * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
26: * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
27: * ARE DISCLAIMED. IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
28: * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
29: * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
30: * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
31: * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
32: * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
33: * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
34: * SUCH DAMAGE.
35: */
36:
37: #if defined(LIBC_SCCS) && !defined(lint)
38: static char sccsid[] = "@(#)glob.c 5.12 (Berkeley) 6/24/91";
39: #endif /* LIBC_SCCS and not lint */
40:
41: /*
42: * glob(3) -- a superset of the one defined in POSIX 1003.2.
43: *
44: * The [!...] convention to negate a range is supported (SysV, Posix, ksh).
45: *
46: * Optional extra services, controlled by flags not defined by POSIX:
47: *
48: * GLOB_QUOTE:
49: * Escaping convention: \ inhibits any special meaning the following
50: * character might have (except \ at end of string is retained).
51: * GLOB_MAGCHAR:
52: * Set in gl_flags if pattern contained a globbing character.
53: * gl_matchc:
54: * Number of matches in the current invocation of glob.
55: */
56:
57: #include <sys/cdefs.h>
58: #include <sys/param.h>
59: #include <sys/stat.h>
60: #include <dirent.h>
61: #include <glob.h>
62: #include <ctype.h>
63: #include <errno.h>
64: #include <string.h>
65: #include <stdio.h>
66: #include <stdlib.h>
67:
68: #define DOLLAR '$'
69: #define DOT '.'
70: #define EOS '\0'
71: #define LBRACKET '['
72: #define NOT '!'
73: #define QUESTION '?'
74: #define QUOTE '\\'
75: #define RANGE '-'
76: #define RBRACKET ']'
77: #define SEP '/'
78: #define STAR '*'
79: #define TILDE '~'
80: #define UNDERSCORE '_'
81:
82: #define M_QUOTE 0x8000
83: #define M_PROTECT 0x4000
84: #define M_MASK 0xffff
85: #define M_ASCII 0x00ff
86:
87: #define CHAR(c) ((c)&M_ASCII)
88: #define META(c) ((c)|M_QUOTE)
89: #define M_ALL META('*')
90: #define M_END META(']')
91: #define M_NOT META('!')
92: #define M_ONE META('?')
93: #define M_RNG META('-')
94: #define M_SET META('[')
95: #define ismeta(c) (((c)&M_QUOTE) != 0)
96:
97: typedef u_short Char;
98:
99: static int compare __P((const void *, const void *));
100: static void g_Ctoc __P((Char *, char *));
101: static int g_lstat __P((Char *, struct stat *));
102: static DIR *g_opendir __P((Char *));
103: static Char *g_strchr __P((Char *, int));
104: static int g_stat __P((Char *, struct stat *));
105: static int glob1 __P((Char *, glob_t *));
106: static int glob2 __P((Char *, Char *, Char *, glob_t *));
107: static int glob3 __P((Char *, Char *, Char *, Char *, glob_t *));
108: static int globextend __P((Char *, glob_t *));
109: static int match __P((Char *, Char *, Char *));
110: #ifdef DEBUG
111: static void qprintf __P((Char *));
112: #endif
113:
114: /*
115: * The main glob() routine: compiles the pattern (optionally processing
116: * quotes), calls glob1() to do the real pattern matching, and finally
117: * sorts the list (unless unsorted operation is requested). Returns 0
118: * if things went well, nonzero if errors occurred. It is not an error
119: * to find no matches.
120: */
121: glob(pattern, flags, errfunc, pglob)
122: const char *pattern;
123: int flags, (*errfunc) __P((char *, int));
124: glob_t *pglob;
125: {
126: const u_char *compilepat, *patnext;
127: int c, err, oldpathc;
128: Char *bufnext, *bufend, *compilebuf, *qpatnext, patbuf[MAXPATHLEN+1];
129:
130: patnext = (u_char *) pattern;
131: if (!(flags & GLOB_APPEND)) {
132: pglob->gl_pathc = 0;
133: pglob->gl_pathv = NULL;
134: if (!(flags & GLOB_DOOFFS))
135: pglob->gl_offs = 0;
136: }
137: pglob->gl_flags = flags & ~GLOB_MAGCHAR;
138: pglob->gl_errfunc = errfunc;
139: oldpathc = pglob->gl_pathc;
140: pglob->gl_matchc = 0;
141:
142: bufnext = patbuf;
143: bufend = bufnext + MAXPATHLEN;
144: compilebuf = bufnext;
145: compilepat = patnext;
146: if (flags & GLOB_QUOTE) {
147: /* Protect the quoted characters. */
148: while (bufnext < bufend && (c = *patnext++) != EOS)
149: if (c == QUOTE) {
150: if ((c = *patnext++) == EOS) {
151: c = QUOTE;
152: --patnext;
153: }
154: *bufnext++ = c | M_PROTECT;
155: }
156: else
157: *bufnext++ = c;
158: }
159: else
160: while (bufnext < bufend && (c = *patnext++) != EOS)
161: *bufnext++ = c;
162: *bufnext = EOS;
163:
164: bufnext = patbuf;
165: qpatnext = patbuf;
166: /* We don't need to check for buffer overflow any more. */
167: while ((c = *qpatnext++) != EOS) {
168: switch (c) {
169: case LBRACKET:
170: pglob->gl_flags |= GLOB_MAGCHAR;
171: c = *qpatnext;
172: if (c == NOT)
173: ++qpatnext;
174: if (*qpatnext == EOS ||
175: g_strchr(qpatnext+1, RBRACKET) == NULL) {
176: *bufnext++ = LBRACKET;
177: if (c == NOT)
178: --qpatnext;
179: break;
180: }
181: *bufnext++ = M_SET;
182: if (c == NOT)
183: *bufnext++ = M_NOT;
184: c = *qpatnext++;
185: do {
186: *bufnext++ = CHAR(c);
187: if (*qpatnext == RANGE &&
188: (c = qpatnext[1]) != RBRACKET) {
189: *bufnext++ = M_RNG;
190: *bufnext++ = CHAR(c);
191: qpatnext += 2;
192: }
193: } while ((c = *qpatnext++) != RBRACKET);
194: *bufnext++ = M_END;
195: break;
196: case QUESTION:
197: pglob->gl_flags |= GLOB_MAGCHAR;
198: *bufnext++ = M_ONE;
199: break;
200: case STAR:
201: pglob->gl_flags |= GLOB_MAGCHAR;
202: *bufnext++ = M_ALL;
203: break;
204: default:
205: *bufnext++ = CHAR(c);
206: break;
207: }
208: }
209: *bufnext = EOS;
210: #ifdef DEBUG
211: qprintf(patbuf);
212: #endif
213:
214: if ((err = glob1(patbuf, pglob)) != 0)
215: return(err);
216:
217: if (pglob->gl_pathc == oldpathc && flags & GLOB_NOCHECK) {
218: if (!(flags & GLOB_QUOTE)) {
219: Char *dp = compilebuf;
220: const u_char *sp = compilepat;
221: while (*dp++ = *sp++);
222: }
223: else {
224: /*
225: * Copy pattern, interpreting quotes; this is slightly
226: * different than the interpretation of quotes above
227: * -- which should prevail?
228: */
229: while (*compilepat != EOS) {
230: if (*compilepat == QUOTE) {
231: if (*++compilepat == EOS)
232: --compilepat;
233: }
234: *compilebuf++ = (u_char)*compilepat++;
235: }
236: *compilebuf = EOS;
237: }
238: return(globextend(patbuf, pglob));
239: } else if (!(flags & GLOB_NOSORT))
240: qsort(pglob->gl_pathv + pglob->gl_offs + oldpathc,
241: pglob->gl_pathc - oldpathc, sizeof(char *), compare);
242: return(0);
243: }
244:
245: static int
246: compare(p, q)
247: const void *p, *q;
248: {
249: return(strcmp(*(char **)p, *(char **)q));
250: }
251:
252: static
253: glob1(pattern, pglob)
254: Char *pattern;
255: glob_t *pglob;
256: {
257: Char pathbuf[MAXPATHLEN+1];
258:
259: /* A null pathname is invalid -- POSIX 1003.1 sect. 2.4. */
260: if (*pattern == EOS)
261: return(0);
262: return(glob2(pathbuf, pathbuf, pattern, pglob));
263: }
264:
265: /*
266: * The functions glob2 and glob3 are mutually recursive; there is one level
267: * of recursion for each segment in the pattern that contains one or more
268: * meta characters.
269: */
270: static
271: glob2(pathbuf, pathend, pattern, pglob)
272: Char *pathbuf, *pathend, *pattern;
273: glob_t *pglob;
274: {
275: struct stat sb;
276: Char *p, *q;
277: int anymeta;
278:
279: /*
280: * Loop over pattern segments until end of pattern or until
281: * segment with meta character found.
282: */
283: for (anymeta = 0;;) {
284: if (*pattern == EOS) { /* End of pattern? */
285: *pathend = EOS;
286: if (g_stat(pathbuf, &sb))
287: return(0);
288:
289: if (((pglob->gl_flags & GLOB_MARK) &&
290: pathend[-1] != SEP) && (S_ISDIR(sb.st_mode)
291: || (S_ISLNK(sb.st_mode) &&
292: (g_stat(pathbuf, &sb) == 0) &&
293: S_ISDIR(sb.st_mode)))) {
294: *pathend++ = SEP;
295: *pathend = EOS;
296: }
297: ++pglob->gl_matchc;
298: return(globextend(pathbuf, pglob));
299: }
300:
301: /* Find end of next segment, copy tentatively to pathend. */
302: q = pathend;
303: p = pattern;
304: while (*p != EOS && *p != SEP) {
305: if (ismeta(*p))
306: anymeta = 1;
307: *q++ = *p++;
308: }
309:
310: if (!anymeta) { /* No expansion, do next segment. */
311: pathend = q;
312: pattern = p;
313: while (*pattern == SEP)
314: *pathend++ = *pattern++;
315: } else /* Need expansion, recurse. */
316: return(glob3(pathbuf, pathend, pattern, p, pglob));
317: }
318: /* NOTREACHED */
319: }
320:
321: static
322: glob3(pathbuf, pathend, pattern, restpattern, pglob)
323: Char *pathbuf, *pathend, *pattern, *restpattern;
324: glob_t *pglob;
325: {
326: register struct dirent *dp;
327: DIR *dirp;
328: int len, err;
329:
330: *pathend = EOS;
331: errno = 0;
332:
333: if (!(dirp = g_opendir(pathbuf)))
334: /* TODO: don't call for ENOENT or ENOTDIR? */
335: if (pglob->gl_errfunc &&
336: (*pglob->gl_errfunc)(pathbuf, errno) ||
337: (pglob->gl_flags & GLOB_ERR))
338: return(GLOB_ABEND);
339: else
340: return(0);
341:
342: err = 0;
343:
344: /* Search directory for matching names. */
345: while ((dp = readdir(dirp))) {
346: register u_char *sc;
347: register Char *dc;
348:
349: /* Initial DOT must be matched literally. */
350: if (dp->d_name[0] == DOT && *pattern != DOT)
351: continue;
352: for (sc = (u_char *) dp->d_name, dc = pathend;
353: *dc++ = *sc++;);
354: if (!match(pathend, pattern, restpattern)) {
355: *pathend = EOS;
356: continue;
357: }
358: err = glob2(pathbuf, --dc, restpattern, pglob);
359: if (err)
360: break;
361: }
362:
363: /* TODO: check error from readdir? */
364: (void)closedir(dirp);
365: return(err);
366: }
367:
368:
369: /*
370: * Extend the gl_pathv member of a glob_t structure to accomodate a new item,
371: * add the new item, and update gl_pathc.
372: *
373: * This assumes the BSD realloc, which only copies the block when its size
374: * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic
375: * behavior.
376: *
377: * Return 0 if new item added, error code if memory couldn't be allocated.
378: *
379: * Invariant of the glob_t structure:
380: * Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and
381: * gl_pathv points to (gl_offs + gl_pathc + 1) items.
382: */
383: static int
384: globextend(path, pglob)
385: Char *path;
386: glob_t *pglob;
387: {
388: register char **pathv;
389: register int i;
390: u_int newsize;
391: char *copy;
392: Char *p;
393:
394: newsize = sizeof(*pathv) * (2 + pglob->gl_pathc + pglob->gl_offs);
395: pathv = (char **)realloc((char *)pglob->gl_pathv, newsize);
396: if (pathv == NULL)
397: return(GLOB_NOSPACE);
398:
399: if (pglob->gl_pathv == NULL && pglob->gl_offs > 0) {
400: /* first time around -- clear initial gl_offs items */
401: pathv += pglob->gl_offs;
402: for (i = pglob->gl_offs; --i >= 0; )
403: *--pathv = NULL;
404: }
405: pglob->gl_pathv = pathv;
406:
407: for (p = path; *p++;);
408: if ((copy = malloc(p - path)) != NULL) {
409: g_Ctoc(path, copy);
410: pathv[pglob->gl_offs + pglob->gl_pathc++] = copy;
411: }
412: pathv[pglob->gl_offs + pglob->gl_pathc] = NULL;
413: return(copy == NULL ? GLOB_NOSPACE : 0);
414: }
415:
416:
417: /*
418: * pattern matching function for filenames. Each occurrence of the *
419: * pattern causes a recursion level.
420: */
421: static
422: match(name, pat, patend)
423: register Char *name, *pat, *patend;
424: {
425: int ok, negate_range;
426: Char c, k;
427:
428: while (pat < patend) {
429: c = *pat++;
430: switch (c & M_MASK) {
431: case M_ALL:
432: if (pat == patend)
433: return(1);
434: for (; *name != EOS; ++name)
435: if (match(name, pat, patend))
436: return(1);
437: return(0);
438: case M_ONE:
439: if (*name++ == EOS)
440: return(0);
441: break;
442: case M_SET:
443: ok = 0;
444: k = *name++;
445: if (negate_range = ((*pat & M_MASK) == M_NOT))
446: ++pat;
447: while (((c = *pat++) & M_MASK) != M_END)
448: if ((*pat & M_MASK) == M_RNG) {
449: if (c <= k && k <= pat[1])
450: ok = 1;
451: pat += 2;
452: } else if (c == k)
453: ok = 1;
454: if (ok == negate_range)
455: return(0);
456: break;
457: default:
458: if (*name++ != c)
459: return(0);
460: break;
461: }
462: }
463: return(*name == EOS);
464: }
465:
466: /* Free allocated data belonging to a glob_t structure. */
467: void
468: globfree(pglob)
469: glob_t *pglob;
470: {
471: register int i;
472: register char **pp;
473:
474: if (pglob->gl_pathv != NULL) {
475: pp = pglob->gl_pathv + pglob->gl_offs;
476: for (i = pglob->gl_pathc; i--; ++pp)
477: if (*pp)
478: free(*pp);
479: free(pglob->gl_pathv);
480: }
481: }
482:
483: static DIR *
484: g_opendir(str)
485: register Char *str;
486: {
487: char buf[MAXPATHLEN];
488:
489: if (!*str)
490: return(opendir("."));
491: g_Ctoc(str, buf);
492: return(opendir(buf));
493: }
494:
495: static int
496: g_lstat(fn, sb)
497: register Char *fn;
498: struct stat *sb;
499: {
500: char buf[MAXPATHLEN];
501:
502: g_Ctoc(fn, buf);
503: return(lstat(buf, sb));
504: }
505:
506: static int
507: g_stat(fn, sb)
508: register Char *fn;
509: struct stat *sb;
510: {
511: char buf[MAXPATHLEN];
512:
513: g_Ctoc(fn, buf);
514: return(stat(buf, sb));
515: }
516:
517: static Char *
518: g_strchr(str, ch)
519: Char *str;
520: int ch;
521: {
522: do {
523: if (*str == ch)
524: return (str);
525: } while (*str++);
526: return (NULL);
527: }
528:
529: static void
530: g_Ctoc(str, buf)
531: register Char *str;
532: char *buf;
533: {
534: register char *dc;
535:
536: for (dc = buf; *dc++ = *str++;);
537: }
538:
539: #ifdef DEBUG
540: static void
541: qprintf(s)
542: register Char *s;
543: {
544: register Char *p;
545:
546: for (p = s; *p; p++)
547: (void)printf("%c", *p & 0xff);
548: (void)printf("\n");
549: for (p = s; *p; p++)
550: (void)printf("%c", *p & M_PROTECT ? '"' : ' ');
551: (void)printf("\n");
552: for (p = s; *p; p++)
553: (void)printf("%c", *p & M_META ? '_' : ' ');
554: (void)printf("\n");
555: }
556: #endif
CVSweb <webmaster@jp.NetBSD.org>