mono/io-layer/wapi_glob.c

   1 /*      $OpenBSD: glob.c,v 1.26 2005/11/28 17:50:12 deraadt 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 /*
  35  * _wapi_glob(3) -- a subset of the one defined in POSIX 1003.2.
  36  *
  37  * Optional extra services, controlled by flags not defined by POSIX:
  38  *
  39  * GLOB_MAGCHAR:
  40  *      Set in gl_flags if pattern contained a globbing character.
  41  */
  42 #include <sys/param.h>
  43 #include <sys/stat.h>
  44
  45 #include <glib.h>
  46 #include <ctype.h>
  47 #include <dirent.h>
  48 #include <errno.h>
  49 #include <pwd.h>
  50 #include <stdio.h>
  51 #include <stdlib.h>
  52 #include <string.h>
  53 #include <unistd.h>
  54
  55 #include "wapi_glob.h"
  56
  57 #define EOS             '\0'
  58 #define NOT             '!'
  59 #define QUESTION        '?'
  60 #define QUOTE           '\\'
  61 #define STAR            '*'
  62
  63 #ifndef DEBUG
  64
  65 #define M_QUOTE         0x8000
  66 #define M_PROTECT       0x4000
  67 #define M_MASK          0xffff
  68 #define M_ASCII         0x00ff
  69
  70 typedef u_short Char;
  71
  72 #else
  73
  74 #define M_QUOTE         0x80
  75 #define M_PROTECT       0x40
  76 #define M_MASK          0xff
  77 #define M_ASCII         0x7f
  78
  79 typedef char Char;
  80
  81 #endif
  82
  83
  84 #define CHAR(c)         ((gchar)((c)&M_ASCII))
  85 #define META(c)         ((gchar)((c)|M_QUOTE))
  86 #define M_ALL           META('*')
  87 #define M_ONE           META('?')
  88 #define ismeta(c)       (((c)&M_QUOTE) != 0)
  89
  90
  91 static int       g_Ctoc(const gchar *, char *, u_int);
  92 static int       glob0(GDir *dir, const gchar *, wapi_glob_t *, gboolean);
  93 static int       glob1(GDir *dir, gchar *, gchar *, wapi_glob_t *, size_t *, gboolean);
  94 static int       glob3(GDir *dir, gchar *, gchar *, wapi_glob_t *, size_t *, gboolean);
  95 static int       globextend(const gchar *, wapi_glob_t *, size_t *);
  96 static int       match(const gchar *, gchar *, gchar *, gboolean);
  97 #ifdef DEBUG
  98 static void      qprintf(const char *, Char *);
  99 #endif
 100
 101 int
 102 _wapi_glob(GDir *dir, const char *pattern, int flags, wapi_glob_t *pglob)
 103 {
 104         const u_char *patnext;
 105         int c;
 106         gchar *bufnext, *bufend, patbuf[MAXPATHLEN];
 107
 108         patnext = (u_char *) pattern;
 109         pglob->gl_pathc = 0;
 110         pglob->gl_pathv = NULL;
 111         pglob->gl_offs = 0;
 112         pglob->gl_flags = flags & ~WAPI_GLOB_MAGCHAR;
 113
 114         bufnext = patbuf;
 115         bufend = bufnext + MAXPATHLEN - 1;
 116
 117         /* Protect the quoted characters. */
 118         while (bufnext < bufend && (c = *patnext++) != EOS)
 119                 if (c == QUOTE) {
 120                         if ((c = *patnext++) == EOS) {
 121                                 c = QUOTE;
 122                                 --patnext;
 123                         }
 124                         *bufnext++ = c | M_PROTECT;
 125                 } else
 126                         *bufnext++ = c;
 127
 128         *bufnext = EOS;
 129
 130         return glob0(dir, patbuf, pglob, flags & WAPI_GLOB_IGNORECASE);
 131 }
 132
 133 /*
 134  * The main glob() routine: compiles the pattern (optionally processing
 135  * quotes), calls glob1() to do the real pattern matching, and finally
 136  * sorts the list (unless unsorted operation is requested).  Returns 0
 137  * if things went well, nonzero if errors occurred.  It is not an error
 138  * to find no matches.
 139  */
 140 static int
 141 glob0(GDir *dir, const gchar *pattern, wapi_glob_t *pglob, gboolean ignorecase)
 142 {
 143         const gchar *qpatnext;
 144         int c, err, oldpathc;
 145         gchar *bufnext, patbuf[MAXPATHLEN];
 146         size_t limit = 0;
 147
 148         qpatnext = pattern;
 149         oldpathc = pglob->gl_pathc;
 150         bufnext = patbuf;
 151
 152         /* We don't need to check for buffer overflow any more. */
 153         while ((c = *qpatnext++) != EOS) {
 154                 switch (c) {
 155                 case QUESTION:
 156                         pglob->gl_flags |= WAPI_GLOB_MAGCHAR;
 157                         *bufnext++ = M_ONE;
 158                         break;
 159                 case STAR:
 160                         pglob->gl_flags |= WAPI_GLOB_MAGCHAR;
 161                         /* collapse adjacent stars to one,
 162                          * to avoid exponential behavior
 163                          */
 164                         if (bufnext == patbuf || bufnext[-1] != M_ALL)
 165                                 *bufnext++ = M_ALL;
 166                         break;
 167                 default:
 168                         *bufnext++ = CHAR(c);
 169                         break;
 170                 }
 171         }
 172         *bufnext = EOS;
 173 #ifdef DEBUG
 174         qprintf("glob0:", patbuf);
 175 #endif
 176
 177         if ((err = glob1(dir, patbuf, patbuf+MAXPATHLEN-1, pglob, &limit,
 178                          ignorecase)) != 0)
 179                 return(err);
 180
 181         if (pglob->gl_pathc == oldpathc) {
 182                 return(WAPI_GLOB_NOMATCH);
 183         }
 184
 185         return(0);
 186 }
 187
 188 static int
 189 glob1(GDir *dir, gchar *pattern, gchar *pattern_last, wapi_glob_t *pglob,
 190       size_t *limitp, gboolean ignorecase)
 191 {
 192         /* A null pathname is invalid -- POSIX 1003.1 sect. 2.4. */
 193         if (*pattern == EOS)
 194                 return(0);
 195         return(glob3(dir, pattern, pattern_last, pglob, limitp, ignorecase));
 196 }
 197
 198 static int
 199 glob3(GDir *dir, gchar *pattern, gchar *pattern_last, wapi_glob_t *pglob,
 200       size_t *limitp, gboolean ignorecase)
 201 {
 202         const gchar *name;
 203
 204         /* Search directory for matching names. */
 205         while ((name = g_dir_read_name(dir))) {
 206                 if (!match(name, pattern, pattern + strlen (pattern),
 207                            ignorecase)) {
 208                         continue;
 209                 }
 210                 globextend (name, pglob, limitp);
 211         }
 212
 213         return(0);
 214 }
 215
 216
 217 /*
 218  * Extend the gl_pathv member of a wapi_glob_t structure to accommodate a new item,
 219  * add the new item, and update gl_pathc.
 220  *
 221  * This assumes the BSD realloc, which only copies the block when its size
 222  * crosses a power-of-two boundary; for v7 realloc, this would cause quadratic
 223  * behavior.
 224  *
 225  * Return 0 if new item added, error code if memory couldn't be allocated.
 226  *
 227  * Invariant of the wapi_glob_t structure:
 228  *      Either gl_pathc is zero and gl_pathv is NULL; or gl_pathc > 0 and
 229  *      gl_pathv points to (gl_offs + gl_pathc + 1) items.
 230  */
 231 static int
 232 globextend(const gchar *path, wapi_glob_t *pglob, size_t *limitp)
 233 {
 234         char **pathv;
 235         int i;
 236         u_int newsize, len;
 237         char *copy;
 238         const gchar *p;
 239
 240         newsize = sizeof(*pathv) * (2 + pglob->gl_pathc + pglob->gl_offs);
 241         pathv = pglob->gl_pathv ? realloc((char *)pglob->gl_pathv, newsize) :
 242             malloc(newsize);
 243         if (pathv == NULL) {
 244                 if (pglob->gl_pathv) {
 245                         free(pglob->gl_pathv);
 246                         pglob->gl_pathv = NULL;
 247                 }
 248                 return(WAPI_GLOB_NOSPACE);
 249         }
 250
 251         if (pglob->gl_pathv == NULL && pglob->gl_offs > 0) {
 252                 /* first time around -- clear initial gl_offs items */
 253                 pathv += pglob->gl_offs;
 254                 for (i = pglob->gl_offs; --i >= 0; )
 255                         *--pathv = NULL;
 256         }
 257         pglob->gl_pathv = pathv;
 258
 259         for (p = path; *p++;)
 260                 ;
 261         len = (size_t)(p - path);
 262         *limitp += len;
 263         if ((copy = malloc(len)) != NULL) {
 264                 if (g_Ctoc(path, copy, len)) {
 265                         free(copy);
 266                         return(WAPI_GLOB_NOSPACE);
 267                 }
 268                 pathv[pglob->gl_offs + pglob->gl_pathc++] = copy;
 269         }
 270         pathv[pglob->gl_offs + pglob->gl_pathc] = NULL;
 271
 272         if ((pglob->gl_flags & WAPI_GLOB_LIMIT) &&
 273             newsize + *limitp >= ARG_MAX) {
 274                 errno = 0;
 275                 return(WAPI_GLOB_NOSPACE);
 276         }
 277
 278         return(copy == NULL ? WAPI_GLOB_NOSPACE : 0);
 279 }
 280
 281
 282 /*
 283  * pattern matching function for filenames.  Each occurrence of the *
 284  * pattern causes a recursion level.
 285  */
 286 static int
 287 match(const gchar *name, gchar *pat, gchar *patend, gboolean ignorecase)
 288 {
 289         gchar c;
 290
 291         while (pat < patend) {
 292                 c = *pat++;
 293                 switch (c & M_MASK) {
 294                 case M_ALL:
 295                         if (pat == patend)
 296                                 return(1);
 297                         do {
 298                                 if (match(name, pat, patend, ignorecase))
 299                                         return(1);
 300                         } while (*name++ != EOS);
 301                         return(0);
 302                 case M_ONE:
 303                         if (*name++ == EOS)
 304                                 return(0);
 305                         break;
 306                 default:
 307                         if (ignorecase) {
 308                                 if (g_ascii_tolower (*name++) != g_ascii_tolower (c))
 309                                         return(0);
 310                         } else {
 311                                 if (*name++ != c)
 312                                         return(0);
 313                         }
 314
 315                         break;
 316                 }
 317         }
 318         return(*name == EOS);
 319 }
 320
 321 /* Free allocated data belonging to a wapi_glob_t structure. */
 322 void
 323 _wapi_globfree(wapi_glob_t *pglob)
 324 {
 325         int i;
 326         char **pp;
 327
 328         if (pglob->gl_pathv != NULL) {
 329                 pp = pglob->gl_pathv + pglob->gl_offs;
 330                 for (i = pglob->gl_pathc; i--; ++pp)
 331                         if (*pp)
 332                                 free(*pp);
 333                 free(pglob->gl_pathv);
 334                 pglob->gl_pathv = NULL;
 335         }
 336 }
 337
 338 static int
 339 g_Ctoc(const gchar *str, char *buf, u_int len)
 340 {
 341
 342         while (len--) {
 343                 if ((*buf++ = *str++) == EOS)
 344                         return (0);
 345         }
 346         return (1);
 347 }
 348
 349 #ifdef DEBUG
 350 static void
 351 qprintf(const char *str, Char *s)
 352 {
 353         Char *p;
 354
 355         (void)printf("%s:\n", str);
 356         for (p = s; *p; p++)
 357                 (void)printf("%c", CHAR(*p));
 358         (void)printf("\n");
 359         for (p = s; *p; p++)
 360                 (void)printf("%c", *p & M_PROTECT ? '"' : ' ');
 361         (void)printf("\n");
 362         for (p = s; *p; p++)
 363                 (void)printf("%c", ismeta(*p) ? '_' : ' ');
 364         (void)printf("\n");
 365 }
 366 #endif