Add OpenBSD's compat glob.c for OpenSSH.
[dragonfly.git] / crypto / openssh / openbsd-compat / glob.c
1 /*      $OpenBSD: glob.c,v 1.35 2011/01/12 01:53:14 djm Exp $ */
2 /*
3  * Copyright (c) 1989, 1993
4  *      The Regents of the University of California.  All rights reserved.
5  *
6  * This code is derived from software contributed to Berkeley by
7  * Guido van Rossum.
8  *
9  * Redistribution and use in source and binary forms, with or without
10  * modification, are permitted provided that the following conditions
11  * are met:
12  * 1. Redistributions of source code must retain the above copyright
13  *    notice, this list of conditions and the following disclaimer.
14  * 2. Redistributions in binary form must reproduce the above copyright
15  *    notice, this list of conditions and the following disclaimer in the
16  *    documentation and/or other materials provided with the distribution.
17  * 3. Neither the name of the University nor the names of its contributors
18  *    may be used to endorse or promote products derived from this software
19  *    without specific prior written permission.
20  *
21  * THIS SOFTWARE IS PROVIDED BY THE REGENTS AND CONTRIBUTORS ``AS IS'' AND
22  * ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE
23  * IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE
24  * ARE DISCLAIMED.  IN NO EVENT SHALL THE REGENTS OR CONTRIBUTORS BE LIABLE
25  * FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
26  * DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS
27  * OR SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION)
28  * HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT
29  * LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY
30  * OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF
31  * SUCH DAMAGE.
32  */
33
34 /* OPENBSD ORIGINAL: lib/libc/gen/glob.c */
35
36 /*
37  * glob(3) -- a superset of the one defined in POSIX 1003.2.
38  *
39  * The [!...] convention to negate a range is supported (SysV, Posix, ksh).
40  *
41  * Optional extra services, controlled by flags not defined by POSIX:
42  *
43  * GLOB_QUOTE:
44  *      Escaping convention: \ inhibits any special meaning the following
45  *      character might have (except \ at end of string is retained).
46  * GLOB_MAGCHAR:
47  *      Set in gl_flags if pattern contained a globbing character.
48  * GLOB_NOMAGIC:
49  *      Same as GLOB_NOCHECK, but it will only append pattern if it did
50  *      not contain any magic characters.  [Used in csh style globbing]
51  * GLOB_ALTDIRFUNC:
52  *      Use alternately specified directory access functions.
53  * GLOB_TILDE:
54  *      expand ~user/foo to the /home/dir/of/user/foo
55  * GLOB_BRACE:
56  *      expand {1,2}{a,b} to 1a 1b 2a 2b
57  * gl_matchc:
58  *      Number of matches in the current invocation of glob.
59  */
60
61 #include "includes.h"
62
63 #include <sys/types.h>
64 #include <sys/stat.h>
65
66 #include <dirent.h>
67 #include <ctype.h>
68 #include <errno.h>
69 #include <pwd.h>
70 #include <stdlib.h>
71 #include <string.h>
72 #include <unistd.h>
73
74 #if !defined(HAVE_GLOB) || !defined(GLOB_HAS_ALTDIRFUNC) || \
75     !defined(GLOB_HAS_GL_MATCHC) || !defined(GLOB_HAS_GL_STATV) || \
76     !defined(HAVE_DECL_GLOB_NOMATCH) || HAVE_DECL_GLOB_NOMATCH == 0 || \
77     defined(BROKEN_GLOB)
78
79 #include "charclass.h"
80
81 #define DOLLAR          '$'
82 #define DOT             '.'
83 #define EOS             '\0'
84 #define LBRACKET        '['
85 #define NOT             '!'
86 #define QUESTION        '?'
87 #define QUOTE           '\\'
88 #define RANGE           '-'
89 #define RBRACKET        ']'
90 #define SEP             '/'
91 #define STAR            '*'
92 #define TILDE           '~'
93 #define UNDERSCORE      '_'
94 #define LBRACE          '{'
95 #define RBRACE          '}'
96 #define SLASH           '/'
97 #define COMMA           ','
98
99 #ifndef DEBUG
100
101 #define M_QUOTE         0x8000
102 #define M_PROTECT       0x4000
103 #define M_MASK          0xffff
104 #define M_ASCII         0x00ff
105
106 typedef u_short Char;
107
108 #else
109
110 #define M_QUOTE         0x80
111 #define M_PROTECT       0x40
112 #define M_MASK          0xff
113 #define M_ASCII         0x7f
114
115 typedef char Char;
116
117 #endif
118
119
120 #define CHAR(c)         ((Char)((c)&M_ASCII))
121 #define META(c)         ((Char)((c)|M_QUOTE))
122 #define M_ALL           META('*')
123 #define M_END           META(']')
124 #define M_NOT           META('!')
125 #define M_ONE           META('?')
126 #define M_RNG           META('-')
127 #define M_SET           META('[')
128 #define M_CLASS         META(':')
129 #define ismeta(c)       (((c)&M_QUOTE) != 0)
130
131 #define GLOB_LIMIT_MALLOC       65536
132 #define GLOB_LIMIT_STAT         128
133 #define GLOB_LIMIT_READDIR      16384
134
135 struct glob_lim {
136         size_t  glim_malloc;
137         size_t  glim_stat;
138         size_t  glim_readdir;
139 };
140
141 static int       compare(const void *, const void *);
142 static int       g_Ctoc(const Char *, char *, u_int);
143 static int       g_lstat(Char *, struct stat *, glob_t *);
144 static DIR      *g_opendir(Char *, glob_t *);
145 static Char     *g_strchr(const Char *, int);
146 static int       g_strncmp(const Char *, const char *, size_t);
147 static int       g_stat(Char *, struct stat *, glob_t *);
148 static int       glob0(const Char *, glob_t *, struct glob_lim *);
149 static int       glob1(Char *, Char *, glob_t *, struct glob_lim *);
150 static int       glob2(Char *, Char *, Char *, Char *, Char *, Char *,
151                     glob_t *, struct glob_lim *);
152 static int       glob3(Char *, Char *, Char *, Char *, Char *,
153                     Char *, Char *, glob_t *, struct glob_lim *);
154 static int       globextend(const Char *, glob_t *, struct glob_lim *,
155                     struct stat *);
156 static const Char *
157                  globtilde(const Char *, Char *, size_t, glob_t *);
158 static int       globexp1(const Char *, glob_t *, struct glob_lim *);
159 static int       globexp2(const Char *, const Char *, glob_t *,
160                     struct glob_lim *);
161 static int       match(Char *, Char *, Char *);
162 #ifdef DEBUG
163 static void      qprintf(const char *, Char *);
164 #endif
165
166 int
167 glob(const char *pattern, int flags, int (*errfunc)(const char *, int),
168     glob_t *pglob)
169 {
170         const u_char *patnext;
171         int c;
172         Char *bufnext, *bufend, patbuf[MAXPATHLEN];
173         struct glob_lim limit = { 0, 0, 0 };
174
175         patnext = (u_char *) pattern;
176         if (!(flags & GLOB_APPEND)) {
177                 pglob->gl_pathc = 0;
178                 pglob->gl_pathv = NULL;
179                 pglob->gl_statv = NULL;
180                 if (!(flags & GLOB_DOOFFS))
181                         pglob->gl_offs = 0;
182         }
183         pglob->gl_flags = flags & ~GLOB_MAGCHAR;
184         pglob->gl_errfunc = errfunc;
185         pglob->gl_matchc = 0;
186
187         if (pglob->gl_offs < 0 || pglob->gl_pathc < 0 ||
188             pglob->gl_offs >= INT_MAX || pglob->gl_pathc >= INT_MAX ||
189             pglob->gl_pathc >= INT_MAX - pglob->gl_offs - 1)
190                 return GLOB_NOSPACE;
191
192         bufnext = patbuf;
193         bufend = bufnext + MAXPATHLEN - 1;
194         if (flags & GLOB_NOESCAPE)
195                 while (bufnext < bufend && (c = *patnext++) != EOS)
196                         *bufnext++ = c;
197         else {
198                 /* Protect the quoted characters. */
199                 while (bufnext < bufend && (c = *patnext++) != EOS)
200                         if (c == QUOTE) {
201                                 if ((c = *patnext++) == EOS) {
202                                         c = QUOTE;
203                                         --patnext;
204                                 }
205                                 *bufnext++ = c | M_PROTECT;
206                         } else
207                                 *bufnext++ = c;
208         }
209         *bufnext = EOS;
210
211         if (flags & GLOB_BRACE)
212                 return globexp1(patbuf, pglob, &limit);
213         else
214                 return glob0(patbuf, pglob, &limit);
215 }
216
217 /*
218  * Expand recursively a glob {} pattern. When there is no more expansion
219  * invoke the standard globbing routine to glob the rest of the magic
220  * characters
221  */
222 static int
223 globexp1(const Char *pattern, glob_t *pglob, struct glob_lim *limitp)
224 {
225         const Char* ptr = pattern;
226
227         /* Protect a single {}, for find(1), like csh */
228         if (pattern[0] == LBRACE && pattern[1] == RBRACE && pattern[2] == EOS)
229                 return glob0(pattern, pglob, limitp);
230
231         if ((ptr = (const Char *) g_strchr(ptr, LBRACE)) != NULL)
232                 return globexp2(ptr, pattern, pglob, limitp);
233
234         return glob0(pattern, pglob, limitp);
235 }
236
237
238 /*
239  * Recursive brace globbing helper. Tries to expand a single brace.
240  * If it succeeds then it invokes globexp1 with the new pattern.
241  * If it fails then it tries to glob the rest of the pattern and returns.
242  */
243 static int
244 globexp2(const Char *ptr, const Char *pattern, glob_t *pglob,
245     struct glob_lim *limitp)
246 {
247         int     i, rv;
248         Char   *lm, *ls;
249         const Char *pe, *pm, *pl;
250         Char    patbuf[MAXPATHLEN];
251
252         /* copy part up to the brace */
253         for (lm = patbuf, pm = pattern; pm != ptr; *lm++ = *pm++)
254                 ;
255         *lm = EOS;
256         ls = lm;
257
258         /* Find the balanced brace */
259         for (i = 0, pe = ++ptr; *pe; pe++)
260                 if (*pe == LBRACKET) {
261                         /* Ignore everything between [] */
262                         for (pm = pe++; *pe != RBRACKET && *pe != EOS; pe++)
263                                 ;
264                         if (*pe == EOS) {
265                                 /*
266                                  * We could not find a matching RBRACKET.
267                                  * Ignore and just look for RBRACE
268                                  */
269                                 pe = pm;
270                         }
271                 } else if (*pe == LBRACE)
272                         i++;
273                 else if (*pe == RBRACE) {
274                         if (i == 0)
275                                 break;
276                         i--;
277                 }
278
279         /* Non matching braces; just glob the pattern */
280         if (i != 0 || *pe == EOS)
281                 return glob0(patbuf, pglob, limitp);
282
283         for (i = 0, pl = pm = ptr; pm <= pe; pm++) {
284                 switch (*pm) {
285                 case LBRACKET:
286                         /* Ignore everything between [] */
287                         for (pl = pm++; *pm != RBRACKET && *pm != EOS; pm++)
288                                 ;
289                         if (*pm == EOS) {
290                                 /*
291                                  * We could not find a matching RBRACKET.
292                                  * Ignore and just look for RBRACE
293                                  */
294                                 pm = pl;
295                         }
296                         break;
297
298                 case LBRACE:
299                         i++;
300                         break;
301
302                 case RBRACE:
303                         if (i) {
304                                 i--;
305                                 break;
306                         }
307                         /* FALLTHROUGH */
308                 case COMMA:
309                         if (i && *pm == COMMA)
310                                 break;
311                         else {
312                                 /* Append the current string */
313                                 for (lm = ls; (pl < pm); *lm++ = *pl++)
314                                         ;
315
316                                 /*
317                                  * Append the rest of the pattern after the
318                                  * closing brace
319                                  */
320                                 for (pl = pe + 1; (*lm++ = *pl++) != EOS; )
321                                         ;
322
323                                 /* Expand the current pattern */
324 #ifdef DEBUG
325                                 qprintf("globexp2:", patbuf);
326 #endif
327                                 rv = globexp1(patbuf, pglob, limitp);
328                                 if (rv && rv != GLOB_NOMATCH)
329                                         return rv;
330
331                                 /* move after the comma, to the next string */
332                                 pl = pm + 1;
333                         }
334                         break;
335
336                 default:
337                         break;
338                 }
339         }
340         return 0;
341 }
342
343
344
345 /*
346  * expand tilde from the passwd file.
347  */
348 static const Char *
349 globtilde(const Char *pattern, Char *patbuf, size_t patbuf_len, glob_t *pglob)
350 {
351         struct passwd *pwd;
352         char *h;
353         const Char *p;
354         Char *b, *eb;
355
356         if (*pattern != TILDE || !(pglob->gl_flags & GLOB_TILDE))
357                 return pattern;
358
359         /* Copy up to the end of the string or / */
360         eb = &patbuf[patbuf_len - 1];
361         for (p = pattern + 1, h = (char *) patbuf;
362             h < (char *)eb && *p && *p != SLASH; *h++ = *p++)
363                 ;
364
365         *h = EOS;
366
367 #if 0
368         if (h == (char *)eb)
369                 return what;
370 #endif
371
372         if (((char *) patbuf)[0] == EOS) {
373                 /*
374                  * handle a plain ~ or ~/ by expanding $HOME
375                  * first and then trying the password file
376                  */
377 #if 0
378                 if (issetugid() != 0 || (h = getenv("HOME")) == NULL) {
379 #endif
380                 if ((getuid() != geteuid()) || (h = getenv("HOME")) == NULL) {
381                         if ((pwd = getpwuid(getuid())) == NULL)
382                                 return pattern;
383                         else
384                                 h = pwd->pw_dir;
385                 }
386         } else {
387                 /*
388                  * Expand a ~user
389                  */
390                 if ((pwd = getpwnam((char*) patbuf)) == NULL)
391                         return pattern;
392                 else
393                         h = pwd->pw_dir;
394         }
395
396         /* Copy the home directory */
397         for (b = patbuf; b < eb && *h; *b++ = *h++)
398                 ;
399
400         /* Append the rest of the pattern */
401         while (b < eb && (*b++ = *p++) != EOS)
402                 ;
403         *b = EOS;
404
405         return patbuf;
406 }
407
408 static int
409 g_strncmp(const Char *s1, const char *s2, size_t n)
410 {
411         int rv = 0;
412
413         while (n--) {
414                 rv = *(Char *)s1 - *(const unsigned char *)s2++;
415                 if (rv)
416                         break;
417                 if (*s1++ == '\0')
418                         break;
419         }
420         return rv;
421 }
422
423 static int
424 g_charclass(const Char **patternp, Char **bufnextp)
425 {
426         const Char *pattern = *patternp + 1;
427         Char *bufnext = *bufnextp;
428         const Char *colon;
429         struct cclass *cc;
430         size_t len;
431
432         if ((colon = g_strchr(pattern, ':')) == NULL || colon[1] != ']')
433                 return 1;       /* not a character class */
434
435         len = (size_t)(colon - pattern);
436         for (cc = cclasses; cc->name != NULL; cc++) {
437                 if (!g_strncmp(pattern, cc->name, len) && cc->name[len] == '\0')
438                         break;
439         }
440         if (cc->name == NULL)
441                 return -1;      /* invalid character class */
442         *bufnext++ = M_CLASS;
443         *bufnext++ = (Char)(cc - &cclasses[0]);
444         *bufnextp = bufnext;
445         *patternp += len + 3;
446
447         return 0;
448 }
449
450 /*
451  * The main glob() routine: compiles the pattern (optionally processing
452  * quotes), calls glob1() to do the real pattern matching, and finally
453  * sorts the list (unless unsorted operation is requested).  Returns 0
454  * if things went well, nonzero if errors occurred.  It is not an error
455  * to find no matches.
456  */
457 static int
458 glob0(const Char *pattern, glob_t *pglob, struct glob_lim *limitp)
459 {
460         const Char *qpatnext;
461         int c, err, oldpathc;
462         Char *bufnext, patbuf[MAXPATHLEN];
463
464         qpatnext = globtilde(pattern, patbuf, MAXPATHLEN, pglob);
465         oldpathc = pglob->gl_pathc;
466         bufnext = patbuf;
467
468         /* We don't need to check for buffer overflow any more. */
469         while ((c = *qpatnext++) != EOS) {
470                 switch (c) {
471                 case LBRACKET:
472                         c = *qpatnext;
473                         if (c == NOT)
474                                 ++qpatnext;
475                         if (*qpatnext == EOS ||
476                             g_strchr(qpatnext+1, RBRACKET) == NULL) {
477                                 *bufnext++ = LBRACKET;
478                                 if (c == NOT)
479                                         --qpatnext;
480                                 break;
481                         }
482                         *bufnext++ = M_SET;
483                         if (c == NOT)
484                                 *bufnext++ = M_NOT;
485                         c = *qpatnext++;
486                         do {
487                                 if (c == LBRACKET && *qpatnext == ':') {
488                                         do {
489                                                 err = g_charclass(&qpatnext,
490                                                     &bufnext);
491                                                 if (err)
492                                                         break;
493                                                 c = *qpatnext++;
494                                         } while (c == LBRACKET && *qpatnext == ':');
495                                         if (err == -1 &&
496                                             !(pglob->gl_flags & GLOB_NOCHECK))
497                                                 return GLOB_NOMATCH;
498                                         if (c == RBRACKET)
499                                                 break;
500                                 }
501                                 *bufnext++ = CHAR(c);
502                                 if (*qpatnext == RANGE &&
503                                     (c = qpatnext[1]) != RBRACKET) {
504                                         *bufnext++ = M_RNG;
505                                         *bufnext++ = CHAR(c);
506                                         qpatnext += 2;
507                                 }
508                         } while ((c = *qpatnext++) != RBRACKET);
509                         pglob->gl_flags |= GLOB_MAGCHAR;
510                         *bufnext++ = M_END;
511                         break;
512                 case QUESTION:
513                         pglob->gl_flags |= GLOB_MAGCHAR;
514                         *bufnext++ = M_ONE;
515                         break;
516                 case STAR:
517                         pglob->gl_flags |= GLOB_MAGCHAR;
518                         /* collapse adjacent stars to one,
519                          * to avoid exponential behavior
520                          */
521                         if (bufnext == patbuf || bufnext[-1] != M_ALL)
522                                 *bufnext++ = M_ALL;
523                         break;
524                 default:
525                         *bufnext++ = CHAR(c);
526                         break;
527                 }
528         }
529         *bufnext = EOS;
530 #ifdef DEBUG
531         qprintf("glob0:", patbuf);
532 #endif
533
534         if ((err = glob1(patbuf, patbuf+MAXPATHLEN-1, pglob, limitp)) != 0)
535                 return(err);
536
537         /*
538          * If there was no match we are going to append the pattern
539          * if GLOB_NOCHECK was specified or if GLOB_NOMAGIC was specified
540          * and the pattern did not contain any magic characters
541          * GLOB_NOMAGIC is there just for compatibility with csh.
542          */
543         if (pglob->gl_pathc == oldpathc) {
544                 if ((pglob->gl_flags & GLOB_NOCHECK) ||
545                     ((pglob->gl_flags & GLOB_NOMAGIC) &&
546                     !(pglob->gl_flags & GLOB_MAGCHAR)))
547                         return(globextend(pattern, pglob, limitp, NULL));
548                 else
549                         return(GLOB_NOMATCH);
550         }
551         if (!(pglob->gl_flags & GLOB_NOSORT))
552                 qsort(pglob->gl_pathv + pglob->gl_offs + oldpathc,
553                     pglob->gl_pathc - oldpathc, sizeof(char *), compare);
554         return(0);
555 }
556
557 static int
558 compare(const void *p, const void *q)
559 {
560         return(strcmp(*(char **)p, *(char **)q));
561 }
562
563 static int
564 glob1(Char *pattern, Char *pattern_last, glob_t *pglob, struct glob_lim *limitp)
565 {
566         Char pathbuf[MAXPATHLEN];
567
568         /* A null pathname is invalid -- POSIX 1003.1 sect. 2.4. */
569         if (*pattern == EOS)
570                 return(0);
571         return(glob2(pathbuf, pathbuf+MAXPATHLEN-1,
572             pathbuf, pathbuf+MAXPATHLEN-1,
573             pattern, pattern_last, pglob, limitp));
574 }
575
576 /*
577  * The functions glob2 and glob3 are mutually recursive; there is one level
578  * of recursion for each segment in the pattern that contains one or more
579  * meta characters.
580  */
581 static int
582 glob2(Char *pathbuf, Char *pathbuf_last, Char *pathend, Char *pathend_last,
583     Char *pattern, Char *pattern_last, glob_t *pglob, struct glob_lim *limitp)
584 {
585         struct stat sb;
586         Char *p, *q;
587         int anymeta;
588
589         /*
590          * Loop over pattern segments until end of pattern or until
591          * segment with meta character found.
592          */
593         for (anymeta = 0;;) {
594                 if (*pattern == EOS) {          /* End of pattern? */
595                         *pathend = EOS;
596                         if (g_lstat(pathbuf, &sb, pglob))
597                                 return(0);
598
599                         if ((pglob->gl_flags & GLOB_LIMIT) &&
600                             limitp->glim_stat++ >= GLOB_LIMIT_STAT) {
601                                 errno = 0;
602                                 *pathend++ = SEP;
603                                 *pathend = EOS;
604                                 return(GLOB_NOSPACE);
605                         }
606
607                         if (((pglob->gl_flags & GLOB_MARK) &&
608                             pathend[-1] != SEP) && (S_ISDIR(sb.st_mode) ||
609                             (S_ISLNK(sb.st_mode) &&
610                             (g_stat(pathbuf, &sb, pglob) == 0) &&
611                             S_ISDIR(sb.st_mode)))) {
612                                 if (pathend+1 > pathend_last)
613                                         return (1);
614                                 *pathend++ = SEP;
615                                 *pathend = EOS;
616                         }
617                         ++pglob->gl_matchc;
618                         return(globextend(pathbuf, pglob, limitp, &sb));
619                 }
620
621                 /* Find end of next segment, copy tentatively to pathend. */
622                 q = pathend;
623                 p = pattern;
624                 while (*p != EOS && *p != SEP) {
625                         if (ismeta(*p))
626                                 anymeta = 1;
627                         if (q+1 > pathend_last)
628                                 return (1);
629                         *q++ = *p++;
630                 }
631
632                 if (!anymeta) {         /* No expansion, do next segment. */
633                         pathend = q;
634                         pattern = p;
635                         while (*pattern == SEP) {
636                                 if (pathend+1 > pathend_last)
637                                         return (1);
638                                 *pathend++ = *pattern++;
639                         }
640                 } else
641                         /* Need expansion, recurse. */
642                         return(glob3(pathbuf, pathbuf_last, pathend,
643                             pathend_last, pattern, p, pattern_last,
644                             pglob, limitp));
645         }
646         /* NOTREACHED */
647 }
648
649 static int
650 glob3(Char *pathbuf, Char *pathbuf_last, Char *pathend, Char *pathend_last,
651     Char *pattern, Char *restpattern, Char *restpattern_last, glob_t *pglob,
652     struct glob_lim *limitp)
653 {
654         struct dirent *dp;
655         DIR *dirp;
656         int err;
657         char buf[MAXPATHLEN];
658
659         /*
660          * The readdirfunc declaration can't be prototyped, because it is
661          * assigned, below, to two functions which are prototyped in glob.h
662          * and dirent.h as taking pointers to differently typed opaque
663          * structures.
664          */
665         struct dirent *(*readdirfunc)(void *);
666
667         if (pathend > pathend_last)
668                 return (1);
669         *pathend = EOS;
670         errno = 0;
671
672         if ((dirp = g_opendir(pathbuf, pglob)) == NULL) {
673                 /* TODO: don't call for ENOENT or ENOTDIR? */
674                 if (pglob->gl_errfunc) {
675                         if (g_Ctoc(pathbuf, buf, sizeof(buf)))
676                                 return(GLOB_ABORTED);
677                         if (pglob->gl_errfunc(buf, errno) ||
678                             pglob->gl_flags & GLOB_ERR)
679                                 return(GLOB_ABORTED);
680                 }
681                 return(0);
682         }
683
684         err = 0;
685
686         /* Search directory for matching names. */
687         if (pglob->gl_flags & GLOB_ALTDIRFUNC)
688                 readdirfunc = pglob->gl_readdir;
689         else
690                 readdirfunc = (struct dirent *(*)(void *))readdir;
691         while ((dp = (*readdirfunc)(dirp))) {
692                 u_char *sc;
693                 Char *dc;
694
695                 if ((pglob->gl_flags & GLOB_LIMIT) &&
696                     limitp->glim_readdir++ >= GLOB_LIMIT_READDIR) {
697                         errno = 0;
698                         *pathend++ = SEP;
699                         *pathend = EOS;
700                         return(GLOB_NOSPACE);
701                 }
702
703                 /* Initial DOT must be matched literally. */
704                 if (dp->d_name[0] == DOT && *pattern != DOT)
705                         continue;
706                 dc = pathend;
707                 sc = (u_char *) dp->d_name;
708                 while (dc < pathend_last && (*dc++ = *sc++) != EOS)
709                         ;
710                 if (dc >= pathend_last) {
711                         *dc = EOS;
712                         err = 1;
713                         break;
714                 }
715
716                 if (!match(pathend, pattern, restpattern)) {
717                         *pathend = EOS;
718                         continue;
719                 }
720                 err = glob2(pathbuf, pathbuf_last, --dc, pathend_last,
721                     restpattern, restpattern_last, pglob, limitp);
722                 if (err)
723                         break;
724         }
725
726         if (pglob->gl_flags & GLOB_ALTDIRFUNC)
727                 (*pglob->gl_closedir)(dirp);
728         else
729                 closedir(dirp);
730         return(err);
731 }
732
733
734 /*
735  * Extend the gl_pathv member of a glob_t structure to accommodate a new item,
736  * add the new item, and update gl_pathc.
737  *
738  * This assumes the BSD realloc, which only copies the block when its size
739  * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic
740  * behavior.
741  *
742  * Return 0 if new item added, error code if memory couldn't be allocated.
743  *
744  * Invariant of the glob_t structure:
745  *      Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and
746  *      gl_pathv points to (gl_offs + gl_pathc + 1) items.
747  */
748 static int
749 globextend(const Char *path, glob_t *pglob, struct glob_lim *limitp,
750     struct stat *sb)
751 {
752         char **pathv;
753         ssize_t i;
754         size_t newn, len;
755         char *copy = NULL;
756         const Char *p;
757         struct stat **statv;
758
759         newn = 2 + pglob->gl_pathc + pglob->gl_offs;
760         if (pglob->gl_offs >= INT_MAX ||
761             pglob->gl_pathc >= INT_MAX ||
762             newn >= INT_MAX ||
763             SIZE_MAX / sizeof(*pathv) <= newn ||
764             SIZE_MAX / sizeof(*statv) <= newn) {
765  nospace:
766                 for (i = pglob->gl_offs; i < (ssize_t)(newn - 2); i++) {
767                         if (pglob->gl_pathv && pglob->gl_pathv[i])
768                                 free(pglob->gl_pathv[i]);
769                         if ((pglob->gl_flags & GLOB_KEEPSTAT) != 0 &&
770                             pglob->gl_pathv && pglob->gl_pathv[i])
771                                 free(pglob->gl_statv[i]);
772                 }
773                 if (pglob->gl_pathv) {
774                         free(pglob->gl_pathv);
775                         pglob->gl_pathv = NULL;
776                 }
777                 if (pglob->gl_statv) {
778                         free(pglob->gl_statv);
779                         pglob->gl_statv = NULL;
780                 }
781                 return(GLOB_NOSPACE);
782         }
783
784         pathv = realloc(pglob->gl_pathv, newn * sizeof(*pathv));
785         if (pathv == NULL)
786                 goto nospace;
787         if (pglob->gl_pathv == NULL && pglob->gl_offs > 0) {
788                 /* first time around -- clear initial gl_offs items */
789                 pathv += pglob->gl_offs;
790                 for (i = pglob->gl_offs; --i >= 0; )
791                         *--pathv = NULL;
792         }
793         pglob->gl_pathv = pathv;
794
795         if ((pglob->gl_flags & GLOB_KEEPSTAT) != 0) {
796                 statv = realloc(pglob->gl_statv, newn * sizeof(*statv));
797                 if (statv == NULL)
798                         goto nospace;
799                 if (pglob->gl_statv == NULL && pglob->gl_offs > 0) {
800                         /* first time around -- clear initial gl_offs items */
801                         statv += pglob->gl_offs;
802                         for (i = pglob->gl_offs; --i >= 0; )
803                                 *--statv = NULL;
804                 }
805                 pglob->gl_statv = statv;
806                 if (sb == NULL)
807                         statv[pglob->gl_offs + pglob->gl_pathc] = NULL;
808                 else {
809                         limitp->glim_malloc += sizeof(**statv);
810                         if ((pglob->gl_flags & GLOB_LIMIT) &&
811                             limitp->glim_malloc >= GLOB_LIMIT_MALLOC) {
812                                 errno = 0;
813                                 return(GLOB_NOSPACE);
814                         }
815                         if ((statv[pglob->gl_offs + pglob->gl_pathc] =
816                             malloc(sizeof(**statv))) == NULL)
817                                 goto copy_error;
818                         memcpy(statv[pglob->gl_offs + pglob->gl_pathc], sb,
819                             sizeof(*sb));
820                 }
821                 statv[pglob->gl_offs + pglob->gl_pathc + 1] = NULL;
822         }
823
824         for (p = path; *p++;)
825                 ;
826         len = (size_t)(p - path);
827         limitp->glim_malloc += len;
828         if ((copy = malloc(len)) != NULL) {
829                 if (g_Ctoc(path, copy, len)) {
830                         free(copy);
831                         return(GLOB_NOSPACE);
832                 }
833                 pathv[pglob->gl_offs + pglob->gl_pathc++] = copy;
834         }
835         pathv[pglob->gl_offs + pglob->gl_pathc] = NULL;
836
837         if ((pglob->gl_flags & GLOB_LIMIT) &&
838             (newn * sizeof(*pathv)) + limitp->glim_malloc >
839             GLOB_LIMIT_MALLOC) {
840                 errno = 0;
841                 return(GLOB_NOSPACE);
842         }
843  copy_error:
844         return(copy == NULL ? GLOB_NOSPACE : 0);
845 }
846
847
848 /*
849  * pattern matching function for filenames.  Each occurrence of the *
850  * pattern causes a recursion level.
851  */
852 static int
853 match(Char *name, Char *pat, Char *patend)
854 {
855         int ok, negate_range;
856         Char c, k;
857
858         while (pat < patend) {
859                 c = *pat++;
860                 switch (c & M_MASK) {
861                 case M_ALL:
862                         if (pat == patend)
863                                 return(1);
864                         do {
865                             if (match(name, pat, patend))
866                                     return(1);
867                         } while (*name++ != EOS);
868                         return(0);
869                 case M_ONE:
870                         if (*name++ == EOS)
871                                 return(0);
872                         break;
873                 case M_SET:
874                         ok = 0;
875                         if ((k = *name++) == EOS)
876                                 return(0);
877                         if ((negate_range = ((*pat & M_MASK) == M_NOT)) != EOS)
878                                 ++pat;
879                         while (((c = *pat++) & M_MASK) != M_END) {
880                                 if ((c & M_MASK) == M_CLASS) {
881                                         Char idx = *pat & M_MASK;
882                                         if (idx < NCCLASSES &&
883                                             cclasses[idx].isctype(k))
884                                                 ok = 1;
885                                         ++pat;
886                                 }
887                                 if ((*pat & M_MASK) == M_RNG) {
888                                         if (c <= k && k <= pat[1])
889                                                 ok = 1;
890                                         pat += 2;
891                                 } else if (c == k)
892                                         ok = 1;
893                         }
894                         if (ok == negate_range)
895                                 return(0);
896                         break;
897                 default:
898                         if (*name++ != c)
899                                 return(0);
900                         break;
901                 }
902         }
903         return(*name == EOS);
904 }
905
906 /* Free allocated data belonging to a glob_t structure. */
907 void
908 globfree(glob_t *pglob)
909 {
910         int i;
911         char **pp;
912
913         if (pglob->gl_pathv != NULL) {
914                 pp = pglob->gl_pathv + pglob->gl_offs;
915                 for (i = pglob->gl_pathc; i--; ++pp)
916                         if (*pp)
917                                 free(*pp);
918                 free(pglob->gl_pathv);
919                 pglob->gl_pathv = NULL;
920         }
921         if (pglob->gl_statv != NULL) {
922                 for (i = 0; i < pglob->gl_pathc; i++) {
923                         if (pglob->gl_statv[i] != NULL)
924                                 free(pglob->gl_statv[i]);
925                 }
926                 free(pglob->gl_statv);
927                 pglob->gl_statv = NULL;
928         }
929 }
930
931 static DIR *
932 g_opendir(Char *str, glob_t *pglob)
933 {
934         char buf[MAXPATHLEN];
935
936         if (!*str)
937                 strlcpy(buf, ".", sizeof buf);
938         else {
939                 if (g_Ctoc(str, buf, sizeof(buf)))
940                         return(NULL);
941         }
942
943         if (pglob->gl_flags & GLOB_ALTDIRFUNC)
944                 return((*pglob->gl_opendir)(buf));
945
946         return(opendir(buf));
947 }
948
949 static int
950 g_lstat(Char *fn, struct stat *sb, glob_t *pglob)
951 {
952         char buf[MAXPATHLEN];
953
954         if (g_Ctoc(fn, buf, sizeof(buf)))
955                 return(-1);
956         if (pglob->gl_flags & GLOB_ALTDIRFUNC)
957                 return((*pglob->gl_lstat)(buf, sb));
958         return(lstat(buf, sb));
959 }
960
961 static int
962 g_stat(Char *fn, struct stat *sb, glob_t *pglob)
963 {
964         char buf[MAXPATHLEN];
965
966         if (g_Ctoc(fn, buf, sizeof(buf)))
967                 return(-1);
968         if (pglob->gl_flags & GLOB_ALTDIRFUNC)
969                 return((*pglob->gl_stat)(buf, sb));
970         return(stat(buf, sb));
971 }
972
973 static Char *
974 g_strchr(const Char *str, int ch)
975 {
976         do {
977                 if (*str == ch)
978                         return ((Char *)str);
979         } while (*str++);
980         return (NULL);
981 }
982
983 static int
984 g_Ctoc(const Char *str, char *buf, u_int len)
985 {
986
987         while (len--) {
988                 if ((*buf++ = *str++) == EOS)
989                         return (0);
990         }
991         return (1);
992 }
993
994 #ifdef DEBUG
995 static void
996 qprintf(const char *str, Char *s)
997 {
998         Char *p;
999
1000         (void)printf("%s:\n", str);
1001         for (p = s; *p; p++)
1002                 (void)printf("%c", CHAR(*p));
1003         (void)printf("\n");
1004         for (p = s; *p; p++)
1005                 (void)printf("%c", *p & M_PROTECT ? '"' : ' ');
1006         (void)printf("\n");
1007         for (p = s; *p; p++)
1008                 (void)printf("%c", ismeta(*p) ? '_' : ' ');
1009         (void)printf("\n");
1010 }
1011 #endif
1012
1013 #endif /* !defined(HAVE_GLOB) || !defined(GLOB_HAS_ALTDIRFUNC) ||
1014           !defined(GLOB_HAS_GL_MATCHC) || !defined(GLOB_HAS_GL_STATV) */