src/regex/glob.c

   1 #define _BSD_SOURCE
   2 #include <glob.h>
   3 #include <fnmatch.h>
   4 #include <sys/stat.h>
   5 #include <dirent.h>
   6 #include <limits.h>
   7 #include <string.h>
   8 #include <stdlib.h>
   9 #include <errno.h>
  10 #include <stddef.h>
  11 #include <unistd.h>
  12 #include <pwd.h>
  13
  14 struct match
  15 {
  16         struct match *next;
  17         char name[];
  18 };
  19
  20 static int append(struct match **tail, const char *name, size_t len, int mark)
  21 {
  22         struct match *new = malloc(sizeof(struct match) + len + 2);
  23         if (!new) return -1;
  24         (*tail)->next = new;
  25         new->next = NULL;
  26         memcpy(new->name, name, len+1);
  27         if (mark && len && name[len-1]!='/') {
  28                 new->name[len] = '/';
  29                 new->name[len+1] = 0;
  30         }
  31         *tail = new;
  32         return 0;
  33 }
  34
  35 static int do_glob(char *buf, size_t pos, int type, char *pat, int flags, int (*errfunc)(const char *path, int err), struct match **tail)
  36 {
  37         /* If GLOB_MARK is unused, we don't care about type. */
  38         if (!type && !(flags & GLOB_MARK)) type = DT_REG;
  39
  40         /* Special-case the remaining pattern being all slashes, in
  41          * which case we can use caller-passed type if it's a dir. */
  42         if (*pat && type!=DT_DIR) type = 0;
  43         while (pos+1 < PATH_MAX && *pat=='/') buf[pos++] = *pat++;
  44
  45         /* Consume maximal [escaped-]literal prefix of pattern, copying
  46          * and un-escaping it to the running buffer as we go. */
  47         ptrdiff_t i=0, j=0;
  48         int in_bracket = 0, overflow = 0;
  49         for (; pat[i]!='*' && pat[i]!='?' && (!in_bracket || pat[i]!=']'); i++) {
  50                 if (!pat[i]) {
  51                         if (overflow) return 0;
  52                         pat += i;
  53                         pos += j;
  54                         i = j = 0;
  55                         break;
  56                 } else if (pat[i] == '[') {
  57                         in_bracket = 1;
  58                 } else if (pat[i] == '\\' && !(flags & GLOB_NOESCAPE)) {
  59                         /* Backslashes inside a bracket are (at least by
  60                          * our interpretation) non-special, so if next
  61                          * char is ']' we have a complete expression. */
  62                         if (in_bracket && pat[i+1]==']') break;
  63                         /* Unpaired final backslash never matches. */
  64                         if (!pat[i+1]) return 0;
  65                         i++;
  66                 }
  67                 if (pat[i] == '/') {
  68                         if (overflow) return 0;
  69                         in_bracket = 0;
  70                         pat += i+1;
  71                         i = -1;
  72                         pos += j+1;
  73                         j = -1;
  74                 }
  75                 /* Only store a character if it fits in the buffer, but if
  76                  * a potential bracket expression is open, the overflow
  77                  * must be remembered and handled later only if the bracket
  78                  * is unterminated (and thereby a literal), so as not to
  79                  * disallow long bracket expressions with short matches. */
  80                 if (pos+(j+1) < PATH_MAX) {
  81                         buf[pos+j++] = pat[i];
  82                 } else if (in_bracket) {
  83                         overflow = 1;
  84                 } else {
  85                         return 0;
  86                 }
  87                 /* If we consume any new components, the caller-passed type
  88                  * or dummy type from above is no longer valid. */
  89                 type = 0;
  90         }
  91         buf[pos] = 0;
  92         if (!*pat) {
  93                 /* If we consumed any components above, or if GLOB_MARK is
  94                  * requested and we don't yet know if the match is a dir,
  95                  * we must confirm the file exists and/or determine its type.
  96                  *
  97                  * If marking dirs, symlink type is inconclusive; we need the
  98                  * type for the symlink target, and therefore must try stat
  99                  * first unless type is known not to be a symlink. Otherwise,
 100                  * or if that fails, use lstat for determining existence to
 101                  * avoid false negatives in the case of broken symlinks. */
 102                 struct stat st;
 103                 if ((flags & GLOB_MARK) && (!type||type==DT_LNK) && !stat(buf, &st)) {
 104                         if (S_ISDIR(st.st_mode)) type = DT_DIR;
 105                         else type = DT_REG;
 106                 }
 107                 if (!type && lstat(buf, &st)) {
 108                         if (errno!=ENOENT && (errfunc(buf, errno) || (flags & GLOB_ERR)))
 109                                 return GLOB_ABORTED;
 110                         return 0;
 111                 }
 112                 if (append(tail, buf, pos, (flags & GLOB_MARK) && type==DT_DIR))
 113                         return GLOB_NOSPACE;
 114                 return 0;
 115         }
 116         char *p2 = strchr(pat, '/'), saved_sep = '/';
 117         /* Check if the '/' was escaped and, if so, remove the escape char
 118          * so that it will not be unpaired when passed to fnmatch. */
 119         if (p2 && !(flags & GLOB_NOESCAPE)) {
 120                 char *p;
 121                 for (p=p2; p>pat && p[-1]=='\\'; p--);
 122                 if ((p2-p)%2) {
 123                         p2--;
 124                         saved_sep = '\\';
 125                 }
 126         }
 127         DIR *dir = opendir(pos ? buf : ".");
 128         if (!dir) {
 129                 if (errfunc(buf, errno) || (flags & GLOB_ERR))
 130                         return GLOB_ABORTED;
 131                 return 0;
 132         }
 133         int old_errno = errno;
 134         struct dirent *de;
 135         while (errno=0, de=readdir(dir)) {
 136                 /* Quickly skip non-directories when there's pattern left. */
 137                 if (p2 && de->d_type && de->d_type!=DT_DIR && de->d_type!=DT_LNK)
 138                         continue;
 139
 140                 size_t l = strlen(de->d_name);
 141                 if (l >= PATH_MAX-pos) continue;
 142
 143                 if (p2) *p2 = 0;
 144
 145                 int fnm_flags= ((flags & GLOB_NOESCAPE) ? FNM_NOESCAPE : 0)
 146                         | ((!(flags & GLOB_PERIOD)) ? FNM_PERIOD : 0);
 147
 148                 if (fnmatch(pat, de->d_name, fnm_flags))
 149                         continue;
 150
 151                 /* With GLOB_PERIOD, don't allow matching . or .. unless
 152                  * fnmatch would match them with FNM_PERIOD rules in effect. */
 153                 if (p2 && (flags & GLOB_PERIOD) && de->d_name[0]=='.'
 154                     && (!de->d_name[1] || de->d_name[1]=='.' && !de->d_name[2])
 155                     && fnmatch(pat, de->d_name, fnm_flags | FNM_PERIOD))
 156                         continue;
 157
 158                 memcpy(buf+pos, de->d_name, l+1);
 159                 if (p2) *p2 = saved_sep;
 160                 int r = do_glob(buf, pos+l, de->d_type, p2 ? p2 : "", flags, errfunc, tail);
 161                 if (r) {
 162                         closedir(dir);
 163                         return r;
 164                 }
 165         }
 166         int readerr = errno;
 167         if (p2) *p2 = saved_sep;
 168         closedir(dir);
 169         if (readerr && (errfunc(buf, errno) || (flags & GLOB_ERR)))
 170                 return GLOB_ABORTED;
 171         errno = old_errno;
 172         return 0;
 173 }
 174
 175 static int ignore_err(const char *path, int err)
 176 {
 177         return 0;
 178 }
 179
 180 static void freelist(struct match *head)
 181 {
 182         struct match *match, *next;
 183         for (match=head->next; match; match=next) {
 184                 next = match->next;
 185                 free(match);
 186         }
 187 }
 188
 189 static int sort(const void *a, const void *b)
 190 {
 191         return strcmp(*(const char **)a, *(const char **)b);
 192 }
 193
 194 static int expand_tilde(char **pat, char *buf, size_t *pos)
 195 {
 196         char *p = *pat + 1;
 197         size_t i = 0;
 198
 199         char delim, *name_end = __strchrnul(p, '/');
 200         if ((delim = *name_end)) *name_end++ = 0;
 201         *pat = name_end;
 202
 203         char *home = *p ? NULL : getenv("HOME");
 204         if (!home) {
 205                 struct passwd pw, *res;
 206                 switch (*p ? getpwnam_r(p, &pw, buf, PATH_MAX, &res)
 207                            : getpwuid_r(getuid(), &pw, buf, PATH_MAX, &res)) {
 208                 case ENOMEM:
 209                         return GLOB_NOSPACE;
 210                 case 0:
 211                         if (!res)
 212                 default:
 213                                 return GLOB_NOMATCH;
 214                 }
 215                 home = pw.pw_dir;
 216         }
 217         while (i < PATH_MAX - 2 && *home)
 218                 buf[i++] = *home++;
 219         if (*home)
 220                 return GLOB_NOMATCH;
 221         if ((buf[i] = delim))
 222                 buf[++i] = 0;
 223         *pos = i;
 224         return 0;
 225 }
 226
 227 int glob(const char *restrict pat, int flags, int (*errfunc)(const char *path, int err), glob_t *restrict g)
 228 {
 229         struct match head = { .next = NULL }, *tail = &head;
 230         size_t cnt, i;
 231         size_t offs = (flags & GLOB_DOOFFS) ? g->gl_offs : 0;
 232         int error = 0;
 233         char buf[PATH_MAX];
 234
 235         if (!errfunc) errfunc = ignore_err;
 236
 237         if (!(flags & GLOB_APPEND)) {
 238                 g->gl_offs = offs;
 239                 g->gl_pathc = 0;
 240                 g->gl_pathv = NULL;
 241         }
 242
 243         if (*pat) {
 244                 char *p = strdup(pat);
 245                 if (!p) return GLOB_NOSPACE;
 246                 buf[0] = 0;
 247                 size_t pos = 0;
 248                 char *s = p;
 249                 if ((flags & (GLOB_TILDE | GLOB_TILDE_CHECK)) && *p == '~')
 250                         error = expand_tilde(&s, buf, &pos);
 251                 if (!error)
 252                         error = do_glob(buf, pos, 0, s, flags, errfunc, &tail);
 253                 free(p);
 254         }
 255
 256         if (error == GLOB_NOSPACE) {
 257                 freelist(&head);
 258                 return error;
 259         }
 260
 261         for (cnt=0, tail=head.next; tail; tail=tail->next, cnt++);
 262         if (!cnt) {
 263                 if (flags & GLOB_NOCHECK) {
 264                         tail = &head;
 265                         if (append(&tail, pat, strlen(pat), 0))
 266                                 return GLOB_NOSPACE;
 267                         cnt++;
 268                 } else if (!error)
 269                         return GLOB_NOMATCH;
 270         }
 271
 272         if (flags & GLOB_APPEND) {
 273                 char **pathv = realloc(g->gl_pathv, (offs + g->gl_pathc + cnt + 1) * sizeof(char *));
 274                 if (!pathv) {
 275                         freelist(&head);
 276                         return GLOB_NOSPACE;
 277                 }
 278                 g->gl_pathv = pathv;
 279                 offs += g->gl_pathc;
 280         } else {
 281                 g->gl_pathv = malloc((offs + cnt + 1) * sizeof(char *));
 282                 if (!g->gl_pathv) {
 283                         freelist(&head);
 284                         return GLOB_NOSPACE;
 285                 }
 286                 for (i=0; i<offs; i++)
 287                         g->gl_pathv[i] = NULL;
 288         }
 289         for (i=0, tail=head.next; i<cnt; tail=tail->next, i++)
 290                 g->gl_pathv[offs + i] = tail->name;
 291         g->gl_pathv[offs + i] = NULL;
 292         g->gl_pathc += cnt;
 293
 294         if (!(flags & GLOB_NOSORT))
 295                 qsort(g->gl_pathv+offs, cnt, sizeof(char *), sort);
 296
 297         return error;
 298 }
 299
 300 void globfree(glob_t *g)
 301 {
 302         size_t i;
 303         for (i=0; i<g->gl_pathc; i++)
 304                 free(g->gl_pathv[g->gl_offs + i] - offsetof(struct match, name));
 305         free(g->gl_pathv);
 306         g->gl_pathc = 0;
 307         g->gl_pathv = NULL;
 308 }