gnu/usr.bin/man/man/glob.c

   1 /* File-name wildcard pattern matching for GNU.
   2    Copyright (C) 1985, 1988, 1989, 1990, 1991 Free Software Foundation, Inc.
   3
   4    This program is free software; you can redistribute it and/or modify
   5    it under the terms of the GNU General Public License as published by
   6    the Free Software Foundation; either version 1, or (at your option)
   7    any later version.
   8
   9    This program is distributed in the hope that it will be useful,
  10    but WITHOUT ANY WARRANTY; without even the implied warranty of
  11    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  12    GNU General Public License for more details.
  13
  14    You should have received a copy of the GNU General Public License
  15    along with this program; if not, write to the Free Software
  16    Foundation, Inc., 675 Mass Ave, Cambridge, MA 02139, USA.  */
  17 \f
  18 /* To whomever it may concern: I have never seen the code which most
  19    Unix programs use to perform this function.  I wrote this from scratch
  20    based on specifications for the pattern matching.  --RMS.  */
  21
  22 #ifdef SHELL
  23 #include "config.h"
  24 #endif /* SHELL */
  25
  26 #include <sys/types.h>
  27 #include <dirent.h>
  28 #include <stdlib.h>
  29 #include <string.h>
  30
  31 #define direct dirent
  32 #define D_NAMLEN(d) strlen((d)->d_name)
  33 #define REAL_DIR_ENTRY(dp) (dp->d_ino != 0)
  34
  35 #define bcopy(s, d, n) memcpy ((d), (s), (n))
  36 #define index strchr
  37 #define rindex strrchr
  38
  39 #ifndef alloca
  40 #define alloca __builtin_alloca
  41 #endif
  42
  43 int glob_pattern_p (char *);
  44 int glob_match (char *, char *, int);
  45 char **glob_vector (char *, const char *);
  46 char **glob_filename (char *);
  47
  48 /* Nonzero if '*' and '?' do not match an initial '.' for glob_filename.  */
  49 int noglob_dot_filenames = 1;
  50
  51 static int glob_match_after_star (char *, char *);
  52
  53 static int
  54 collate_range_cmp (int a, int b)
  55 {
  56         int r;
  57         static char s[2][2];
  58
  59         if ((unsigned char)a == (unsigned char)b)
  60                 return 0;
  61         s[0][0] = a;
  62         s[1][0] = b;
  63         if ((r = strcoll(s[0], s[1])) == 0)
  64                 r = (unsigned char)a - (unsigned char)b;
  65         return r;
  66 }
  67 \f
  68 /* Return nonzero if PATTERN has any special globbing chars in it.  */
  69
  70 int
  71 glob_pattern_p (char *pattern)
  72 {
  73   char *p = pattern;
  74   char c;
  75   int open = 0;
  76
  77   while ((c = *p++) != '\0')
  78     switch (c)
  79       {
  80       case '?':
  81       case '*':
  82         return 1;
  83
  84       case '[':         /* Only accept an open brace if there is a close */
  85         open++;         /* brace to match it.  Bracket expressions must be */
  86         continue;       /* complete, according to Posix.2 */
  87       case ']':
  88         if (open)
  89           return 1;
  90         continue;
  91
  92       case '\\':
  93         if (*p++ == '\0')
  94           return 0;
  95       }
  96
  97   return 0;
  98 }
  99 \f
 100
 101 /* Match the pattern PATTERN against the string TEXT;
 102    return 1 if it matches, 0 otherwise.
 103
 104    A match means the entire string TEXT is used up in matching.
 105
 106    In the pattern string, `*' matches any sequence of characters,
 107    `?' matches any character, [SET] matches any character in the specified set,
 108    [!SET] matches any character not in the specified set.
 109
 110    A set is composed of characters or ranges; a range looks like
 111    character hyphen character (as in 0-9 or A-Z).
 112    [0-9a-zA-Z_] is the set of characters allowed in C identifiers.
 113    Any other character in the pattern must be matched exactly.
 114
 115    To suppress the special syntactic significance of any of `[]*?!-\',
 116    and match the character exactly, precede it with a `\'.
 117
 118    If DOT_SPECIAL is nonzero,
 119    `*' and `?' do not match `.' at the beginning of TEXT.  */
 120
 121 int
 122 glob_match (char *pattern, char *text, int dot_special)
 123 {
 124   char *p = pattern, *t = text;
 125   char c;
 126
 127   while ((c = *p++) != '\0')
 128     switch (c)
 129       {
 130       case '?':
 131         if (*t == '\0' || (dot_special && t == text && *t == '.'))
 132           return 0;
 133         else
 134           ++t;
 135         break;
 136
 137       case '\\':
 138         if (*p++ != *t++)
 139           return 0;
 140         break;
 141
 142       case '*':
 143         if (dot_special && t == text && *t == '.')
 144           return 0;
 145         return glob_match_after_star (p, t);
 146
 147       case '[':
 148         {
 149           char c1 = *t++;
 150           int invert;
 151           char *cp1 = p;
 152
 153           if (c1 == '\0')
 154             return 0;
 155
 156           invert = (*p == '!');
 157
 158           if (invert)
 159             p++;
 160
 161           c = *p++;
 162           while (1)
 163             {
 164               char cstart = c, cend = c;
 165
 166               if (c == '\\')
 167                 {
 168                   cstart = *p++;
 169                   cend = cstart;
 170                 }
 171
 172               if (cstart == '\0')
 173                 {
 174                   /* Missing ']'. */
 175                   if (c1 != '[')
 176                     return 0;
 177                   /* matched a single bracket */
 178                   p = cp1;
 179                   goto breakbracket;
 180                 }
 181
 182               c = *p++;
 183
 184               if (c == '-')
 185                 {
 186                   cend = *p++;
 187                   if (cend == '\\')
 188                     cend = *p++;
 189                   if (cend == '\0')
 190                     return 0;
 191                   c = *p++;
 192                 }
 193               if (   collate_range_cmp (c1, cstart) >= 0
 194                   && collate_range_cmp (c1, cend) <= 0
 195                  )
 196                 goto match;
 197               if (c == ']')
 198                 break;
 199             }
 200           if (!invert)
 201             return 0;
 202           break;
 203
 204         match:
 205           /* Skip the rest of the [...] construct that already matched.  */
 206           while (c != ']')
 207             {
 208               if (c == '\0')
 209                 return 0;
 210               c = *p++;
 211               if (c == '\0')
 212                 return 0;
 213               if (c == '\\')
 214                 p++;
 215             }
 216           if (invert)
 217             return 0;
 218           breakbracket:
 219           break;
 220         }
 221
 222       default:
 223         if (c != *t++)
 224           return 0;
 225       }
 226
 227   return *t == '\0';
 228 }
 229 \f
 230 /* Like glob_match, but match PATTERN against any final segment of TEXT.  */
 231
 232 static int
 233 glob_match_after_star (char *pattern, char *text)
 234 {
 235   char *p = pattern, *t = text;
 236   char c, c1;
 237
 238   while ((c = *p++) == '?' || c == '*')
 239     if (c == '?' && *t++ == '\0')
 240       return 0;
 241
 242   if (c == '\0')
 243     return 1;
 244
 245   if (c == '\\')
 246     c1 = *p;
 247   else
 248     c1 = c;
 249
 250   --p;
 251   while (1)
 252     {
 253       if ((c == '[' || *t == c1) && glob_match (p, t, 0))
 254         return 1;
 255       if (*t++ == '\0')
 256         return 0;
 257     }
 258 }
 259 \f
 260 /* Return a vector of names of files in directory DIR
 261    whose names match glob pattern PAT.
 262    The names are not in any particular order.
 263    Wildcards at the beginning of PAT do not match an initial period
 264    if noglob_dot_filenames is nonzero.
 265
 266    The vector is terminated by an element that is a null pointer.
 267
 268    To free the space allocated, first free the vector's elements,
 269    then free the vector.
 270
 271    Return NULL if cannot get enough memory to hold the pointer
 272    and the names.
 273
 274    Return -1 if cannot access directory DIR.
 275    Look in errno for more information.  */
 276
 277 char **
 278 glob_vector (char *pat, const char *dir)
 279 {
 280   struct globval
 281   {
 282     struct globval *next;
 283     char *name;
 284   };
 285
 286   DIR *d;
 287   struct direct *dp;
 288   struct globval *lastlink;
 289   struct globval *nextlink;
 290   char *nextname;
 291   unsigned int count;
 292   int lose;
 293   char **name_vector;
 294   unsigned int i;
 295
 296   d = opendir (dir);
 297   if (d == NULL)
 298     return (char **) -1;
 299
 300   lastlink = NULL;
 301   count = 0;
 302   lose = 0;
 303
 304   /* Scan the directory, finding all names that match.
 305      For each name that matches, allocate a struct globval
 306      on the stack and store the name in it.
 307      Chain those structs together; lastlink is the front of the chain.  */
 308   while (1)
 309     {
 310 #if defined (SHELL)
 311       /* Make globbing interruptible in the bash shell. */
 312       extern int interrupt_state;
 313
 314       if (interrupt_state)
 315         {
 316           closedir (d);
 317           lose = 1;
 318           goto lost;
 319         }
 320 #endif /* SHELL */
 321
 322       dp = readdir (d);
 323       if (dp == NULL)
 324         break;
 325       if (REAL_DIR_ENTRY (dp)
 326           && glob_match (pat, dp->d_name, noglob_dot_filenames))
 327         {
 328           nextlink = (struct globval *) alloca (sizeof (struct globval));
 329           nextlink->next = lastlink;
 330           i = D_NAMLEN (dp) + 1;
 331           nextname = (char *) malloc (i);
 332           if (nextname == NULL)
 333             {
 334               lose = 1;
 335               break;
 336             }
 337           lastlink = nextlink;
 338           nextlink->name = nextname;
 339           bcopy (dp->d_name, nextname, i);
 340           count++;
 341         }
 342     }
 343   closedir (d);
 344
 345   if (!lose)
 346     {
 347       name_vector = (char **) malloc ((count + 1) * sizeof (char *));
 348       lose |= name_vector == NULL;
 349     }
 350
 351   /* Have we run out of memory?  */
 352 #ifdef  SHELL
 353  lost:
 354 #endif
 355   if (lose)
 356     {
 357       /* Here free the strings we have got.  */
 358       while (lastlink)
 359         {
 360           free (lastlink->name);
 361           lastlink = lastlink->next;
 362         }
 363       return NULL;
 364     }
 365
 366   /* Copy the name pointers from the linked list into the vector.  */
 367   for (i = 0; i < count; ++i)
 368     {
 369       name_vector[i] = lastlink->name;
 370       lastlink = lastlink->next;
 371     }
 372
 373   name_vector[count] = NULL;
 374   return name_vector;
 375 }
 376 \f
 377 /* Return a new array, replacing ARRAY, which is the concatenation
 378    of each string in ARRAY to DIR.
 379    Return NULL if out of memory.  */
 380
 381 static char **
 382 glob_dir_to_array (char *dir, char **array)
 383 {
 384   unsigned int i, l;
 385   int add_slash = 0;
 386   char **result;
 387
 388   l = strlen (dir);
 389   if (l == 0)
 390     return array;
 391
 392   if (dir[l - 1] != '/')
 393     add_slash++;
 394
 395   for (i = 0; array[i] != NULL; i++)
 396     ;
 397
 398   result = (char **) malloc ((i + 1) * sizeof (char *));
 399   if (result == NULL)
 400     return NULL;
 401
 402   for (i = 0; array[i] != NULL; i++)
 403     {
 404       result[i] = (char *) malloc (1 + l + add_slash + strlen (array[i]));
 405       if (result[i] == NULL)
 406         return NULL;
 407       strcpy (result[i], dir);
 408       if (add_slash)
 409         result[i][l] = '/';
 410       strcpy (result[i] + l + add_slash, array[i]);
 411     }
 412   result[i] = NULL;
 413
 414   /* Free the input array.  */
 415   for (i = 0; array[i] != NULL; i++)
 416     free (array[i]);
 417   free ((char *) array);
 418   return result;
 419 }
 420 \f
 421 /* Do globbing on PATHNAME.  Return an array of pathnames that match,
 422    marking the end of the array with a null-pointer as an element.
 423    If no pathnames match, then the array is empty (first element is null).
 424    If there isn't enough memory, then return NULL.
 425    If a file system error occurs, return -1; `errno' has the error code.
 426
 427    Wildcards at the beginning of PAT, or following a slash,
 428    do not match an initial period if noglob_dot_filenames is nonzero.  */
 429
 430 char **
 431 glob_filename (char *pathname)
 432 {
 433   char **result;
 434   unsigned int result_size;
 435   char *directory_name, *filename;
 436   unsigned int directory_len;
 437
 438   result = (char **) malloc (sizeof (char *));
 439   result_size = 1;
 440   if (result == NULL)
 441     return NULL;
 442
 443   result[0] = NULL;
 444
 445   /* Find the filename.  */
 446   filename = rindex (pathname, '/');
 447   if (filename == NULL)
 448     {
 449       filename = pathname;
 450       directory_name = NULL;
 451       directory_len = 0;
 452     }
 453   else
 454     {
 455       directory_len = (filename - pathname) + 1;
 456       directory_name = (char *) alloca (directory_len + 1);
 457       bcopy (pathname, directory_name, directory_len);
 458       directory_name[directory_len] = '\0';
 459       ++filename;
 460     }
 461
 462   /* If directory_name contains globbing characters, then we
 463      have to expand the previous levels.  Just recurse. */
 464   if (glob_pattern_p (directory_name))
 465     {
 466       char **directories;
 467       unsigned int i;
 468
 469       if (directory_name[directory_len - 1] == '/')
 470         directory_name[directory_len - 1] = '\0';
 471
 472       directories = glob_filename (directory_name);
 473       if (directories == NULL)
 474         goto memory_error;
 475       else if (directories == (char **) -1)
 476         return (char **) -1;
 477       else if (*directories == NULL)
 478         {
 479           free ((char *) directories);
 480           return (char **) -1;
 481         }
 482
 483       /* We have successfully globbed the preceding directory name.
 484          For each name in DIRECTORIES, call glob_vector on it and
 485          FILENAME.  Concatenate the results together.  */
 486       for (i = 0; directories[i] != NULL; i++)
 487         {
 488           char **temp_results = glob_vector (filename, directories[i]);
 489           if (temp_results == NULL)
 490             goto memory_error;
 491           else if (temp_results == (char **) -1)
 492             /* This filename is probably not a directory.  Ignore it.  */
 493             ;
 494           else
 495             {
 496               char **array = glob_dir_to_array (directories[i], temp_results);
 497               unsigned int l;
 498
 499               l = 0;
 500               while (array[l] != NULL)
 501                 ++l;
 502
 503               result = (char **) realloc (result,
 504                                           (result_size + l) * sizeof (char *));
 505               if (result == NULL)
 506                 goto memory_error;
 507
 508               for (l = 0; array[l] != NULL; ++l)
 509                 result[result_size++ - 1] = array[l];
 510               result[result_size - 1] = NULL;
 511               free ((char *) array);
 512             }
 513         }
 514       /* Free the directories.  */
 515       for (i = 0; directories[i] != NULL; i++)
 516         free (directories[i]);
 517       free ((char *) directories);
 518
 519       return result;
 520     }
 521
 522   /* If there is only a directory name, return it. */
 523   if (*filename == '\0')
 524     {
 525       result = (char **) realloc ((char *) result, 2 * sizeof (char *));
 526       if (result != NULL)
 527         {
 528           result[0] = (char *) malloc (directory_len + 1);
 529           if (result[0] == NULL)
 530             {
 531               goto memory_error;
 532             }
 533           bcopy (directory_name, result[0], directory_len + 1);
 534           result[1] = NULL;
 535         }
 536       return result;
 537     }
 538   else
 539     {
 540       /* Otherwise, just return what glob_vector
 541          returns appended to the directory name. */
 542       char **temp_results = glob_vector (filename,
 543                                          (directory_len == 0
 544                                           ? "." : directory_name));
 545
 546       if (temp_results == NULL || temp_results == (char **) -1)
 547         {
 548           return temp_results;
 549         }
 550
 551       temp_results = glob_dir_to_array (directory_name, temp_results);
 552       return temp_results;
 553     }
 554
 555   /* We get to memory error if the program has run out of memory, or
 556      if this is the shell, and we have been interrupted. */
 557  memory_error:
 558   if (result != NULL)
 559     {
 560       unsigned int i;
 561       for (i = 0; result[i] != NULL; ++i)
 562         free (result[i]);
 563       free ((char *) result);
 564     }
 565 #if defined (SHELL)
 566   {
 567     extern int interrupt_state;
 568
 569     if (interrupt_state)
 570       throw_to_top_level ();
 571   }
 572 #endif /* SHELL */
 573   return NULL;
 574 }
 575 \f
 576 #ifdef TEST
 577
 578 int
 579 main (int argc, char **argv)
 580 {
 581   char **value;
 582   int i, optind;
 583
 584   for (optind = 1; optind < argc; optind++)
 585     {
 586       value = glob_filename (argv[optind]);
 587       if (value == NULL)
 588         puts ("virtual memory exhausted");
 589       else if (value == (char **) -1)
 590         perror (argv[optind]);
 591       else
 592         for (i = 0; value[i] != NULL; i++)
 593           puts (value[i]);
 594     }
 595   exit (0);
 596 }
 597
 598 #endif /* TEST */