lib/glob/glob.c

   1 /* File-name wildcard pattern matching for GNU.
   2    Copyright (C) 1985, 1988, 1989 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 #if defined (SHELL)
  23 #  if defined (HAVE_STDLIB_H)
  24 #    include <stdlib.h>
  25 #  else
  26 #    include "ansi_stdlib.h"
  27 #  endif /* HAVE_STDLIB_H */
  28 #  include <config.h>
  29 #endif
  30
  31 #include <sys/types.h>
  32
  33 #if !defined (SHELL) && (defined (_POSIX_VERSION) || defined (USGr3))
  34 #  if !defined (HAVE_DIRENT_H)
  35 #    define HAVE_DIRENT_H
  36 #  endif /* !HAVE_DIRENT_H */
  37 #endif /* !SHELL && (_POSIX_VERSION || USGr3) */
  38
  39 #if defined (HAVE_DIRENT_H)
  40 #  include <dirent.h>
  41 #  if !defined (direct)
  42 #    define direct dirent
  43 #  endif /* !direct */
  44 #  define D_NAMLEN(d) strlen ((d)->d_name)
  45 #else /* !HAVE_DIRENT_H */
  46 #  define D_NAMLEN(d) ((d)->d_namlen)
  47 #  if defined (USG)
  48 #    if defined (Xenix)
  49 #      include <sys/ndir.h>
  50 #    else /* !Xenix (but USG...) */
  51 #      include "ndir.h"
  52 #    endif /* !Xenix */
  53 #  else /* !USG */
  54 #    include <sys/dir.h>
  55 #  endif /* !USG */
  56 #endif /* !HAVE_DIRENT_H */
  57
  58 #if defined (_POSIX_SOURCE)
  59 /* Posix does not require that the d_ino field be present, and some
  60    systems do not provide it. */
  61 #  define REAL_DIR_ENTRY(dp) 1
  62 #else
  63 #  define REAL_DIR_ENTRY(dp) (dp->d_ino != 0)
  64 #endif /* _POSIX_SOURCE */
  65
  66 #if defined (USG) || defined (NeXT)
  67 #  if !defined (HAVE_STRING_H)
  68 #    define HAVE_STRING_H
  69 #  endif /* !HAVE_STRING_H */
  70 #endif /* USG || NeXT */
  71
  72 #if defined (HAVE_STRING_H)
  73 #  include <string.h>
  74 #else /* !HAVE_STRING_H */
  75 #  include <strings.h>
  76 #endif /* !HAVE_STRING_H */
  77
  78 #if defined (USG)
  79 #  if !defined (isc386)
  80 #    include <memory.h>
  81 #  endif /* !isc386 */
  82 #  if defined (RISC6000)
  83 extern void bcopy ();
  84 #  else /* !RISC6000 */
  85 #    define bcopy(s, d, n) ((void) memcpy ((d), (s), (n)))
  86 #  endif /* !RISC6000 */
  87 #endif /* USG */
  88
  89 #include "fnmatch.h"
  90
  91 /* If the opendir () on your system lets you open non-directory files,
  92    then we consider that not robust.  Define OPENDIR_NOT_ROBUST in the
  93    SYSDEP_CFLAGS for your machines entry in machines.h. */
  94 #if defined (OPENDIR_NOT_ROBUST)
  95 #  if defined (SHELL)
  96 #    include "posixstat.h"
  97 #  else /* !SHELL */
  98 #    include <sys/stat.h>
  99 #  endif /* !SHELL */
 100 #endif /* OPENDIR_NOT_ROBUST */
 101
 102 #if !defined (HAVE_STDLIB_H)
 103 extern char *malloc (), *realloc ();
 104 extern void free ();
 105 #endif /* !HAVE_STDLIB_H */
 106
 107 #if !defined (NULL)
 108 #  if defined (__STDC__)
 109 #    define NULL ((void *) 0)
 110 #  else
 111 #    define NULL 0x0
 112 #  endif /* __STDC__ */
 113 #endif /* !NULL */
 114
 115 #if defined (SHELL)
 116 extern int interrupt_state;
 117 #endif /* SHELL */
 118
 119 /* Global variable which controls whether or not * matches .*.
 120    Non-zero means don't match .*.  */
 121 int noglob_dot_filenames = 1;
 122
 123 /* Global variable to return to signify an error in globbing. */
 124 char *glob_error_return;
 125
 126 \f
 127 /* Return nonzero if PATTERN has any special globbing chars in it.  */
 128 int
 129 glob_pattern_p (pattern)
 130      char *pattern;
 131 {
 132   register char *p = pattern;
 133   register char c;
 134   int open = 0;
 135
 136   while ((c = *p++) != '\0')
 137     switch (c)
 138       {
 139       case '?':
 140       case '*':
 141         return (1);
 142
 143       case '[':         /* Only accept an open brace if there is a close */
 144         open++;         /* brace to match it.  Bracket expressions must be */
 145         continue;       /* complete, according to Posix.2 */
 146       case ']':
 147         if (open)
 148           return (1);
 149         continue;
 150
 151       case '\\':
 152         if (*p++ == '\0')
 153           return (0);
 154       }
 155
 156   return (0);
 157 }
 158
 159 /* Remove backslashes quoting characters in PATHNAME by modifying PATHNAME. */
 160 static void
 161 dequote_pathname (pathname)
 162      char *pathname;
 163 {
 164   register int i, j;
 165
 166   for (i = j = 0; pathname && pathname[i]; )
 167     {
 168       if (pathname[i] == '\\')
 169         i++;
 170
 171       pathname[j++] = pathname[i++];
 172
 173       if (!pathname[i - 1])
 174         break;
 175     }
 176   pathname[j] = '\0';
 177 }
 178
 179 \f
 180 /* Return a vector of names of files in directory DIR
 181    whose names match glob pattern PAT.
 182    The names are not in any particular order.
 183    Wildcards at the beginning of PAT do not match an initial period.
 184
 185    The vector is terminated by an element that is a null pointer.
 186
 187    To free the space allocated, first free the vector's elements,
 188    then free the vector.
 189
 190    Return 0 if cannot get enough memory to hold the pointer
 191    and the names.
 192
 193    Return -1 if cannot access directory DIR.
 194    Look in errno for more information.  */
 195
 196 char **
 197 glob_vector (pat, dir)
 198      char *pat;
 199      char *dir;
 200 {
 201   struct globval
 202     {
 203       struct globval *next;
 204       char *name;
 205     };
 206
 207   DIR *d;
 208   register struct direct *dp;
 209   struct globval *lastlink;
 210   register struct globval *nextlink;
 211   register char *nextname;
 212   unsigned int count;
 213   int lose, skip;
 214   register char **name_vector;
 215   register unsigned int i;
 216 #if defined (OPENDIR_NOT_ROBUST)
 217   struct stat finfo;
 218
 219   if (stat (dir, &finfo) < 0)
 220     return ((char **) &glob_error_return);
 221
 222   if (!S_ISDIR (finfo.st_mode))
 223     return ((char **) &glob_error_return);
 224 #endif /* OPENDIR_NOT_ROBUST */
 225
 226   d = opendir (dir);
 227   if (d == NULL)
 228     return ((char **) &glob_error_return);
 229
 230   lastlink = 0;
 231   count = 0;
 232   lose = 0;
 233   skip = 0;
 234
 235   /* If PAT is empty, skip the loop, but return one (empty) filename. */
 236   if (!pat || !*pat)
 237     {
 238       nextlink = (struct globval *)alloca (sizeof (struct globval));
 239       nextlink->next = lastlink;
 240       nextname = (char *) malloc (1);
 241       if (!nextname)
 242         lose = 1;
 243       else
 244         {
 245           lastlink = nextlink;
 246           nextlink->name = nextname;
 247           nextname[0] = '\0';
 248           count++;
 249         }
 250       skip = 1;
 251     }
 252
 253   /* Scan the directory, finding all names that match.
 254      For each name that matches, allocate a struct globval
 255      on the stack and store the name in it.
 256      Chain those structs together; lastlink is the front of the chain.  */
 257   while (!skip)
 258     {
 259       int flags;                /* Flags passed to fnmatch (). */
 260 #if defined (SHELL)
 261       /* Make globbing interruptible in the bash shell. */
 262       if (interrupt_state)
 263         {
 264           closedir (d);
 265           lose = 1;
 266           goto lost;
 267         }
 268 #endif /* SHELL */
 269
 270       dp = readdir (d);
 271       if (dp == NULL)
 272         break;
 273
 274       /* If this directory entry is not to be used, try again. */
 275       if (!REAL_DIR_ENTRY (dp))
 276         continue;
 277
 278       /* If a dot must be explicity matched, check to see if they do. */
 279       if (noglob_dot_filenames && dp->d_name[0] == '.' && pat[0] != '.')
 280         continue;
 281
 282       flags = (noglob_dot_filenames ? FNM_PERIOD : 0) | FNM_PATHNAME;
 283
 284       if (fnmatch (pat, dp->d_name, flags) != FNM_NOMATCH)
 285         {
 286           nextlink = (struct globval *) alloca (sizeof (struct globval));
 287           nextlink->next = lastlink;
 288           nextname = (char *) malloc (D_NAMLEN (dp) + 1);
 289           if (nextname == NULL)
 290             {
 291               lose = 1;
 292               break;
 293             }
 294           lastlink = nextlink;
 295           nextlink->name = nextname;
 296           bcopy (dp->d_name, nextname, D_NAMLEN (dp) + 1);
 297           ++count;
 298         }
 299     }
 300   (void) closedir (d);
 301
 302   if (!lose)
 303     {
 304       name_vector = (char **) malloc ((count + 1) * sizeof (char *));
 305       lose |= name_vector == NULL;
 306     }
 307
 308   /* Have we run out of memory?  */
 309  lost:
 310   if (lose)
 311     {
 312       /* Here free the strings we have got.  */
 313       while (lastlink)
 314         {
 315           free (lastlink->name);
 316           lastlink = lastlink->next;
 317         }
 318 #if defined (SHELL)
 319       if (interrupt_state)
 320         throw_to_top_level ();
 321 #endif /* SHELL */
 322       return (NULL);
 323     }
 324
 325   /* Copy the name pointers from the linked list into the vector.  */
 326   for (i = 0; i < count; ++i)
 327     {
 328       name_vector[i] = lastlink->name;
 329       lastlink = lastlink->next;
 330     }
 331
 332   name_vector[count] = NULL;
 333   return (name_vector);
 334 }
 335 \f
 336 /* Return a new array which is the concatenation of each string in ARRAY
 337    to DIR.  This function expects you to pass in an allocated ARRAY, and
 338    it takes care of free()ing that array.  Thus, you might think of this
 339    function as side-effecting ARRAY. */
 340 static char **
 341 glob_dir_to_array (dir, array)
 342      char *dir, **array;
 343 {
 344   register unsigned int i, l;
 345   int add_slash;
 346   char **result;
 347
 348   l = strlen (dir);
 349   if (l == 0)
 350     return (array);
 351
 352   add_slash = dir[l - 1] != '/';
 353
 354   i = 0;
 355   while (array[i] != NULL)
 356     ++i;
 357
 358   result = (char **) malloc ((i + 1) * sizeof (char *));
 359   if (result == NULL)
 360     return (NULL);
 361
 362   for (i = 0; array[i] != NULL; i++)
 363     {
 364       result[i] = (char *) malloc (l + (add_slash ? 1 : 0)
 365                                    + strlen (array[i]) + 1);
 366       if (result[i] == NULL)
 367         return (NULL);
 368       sprintf (result[i], "%s%s%s", dir, add_slash ? "/" : "", array[i]);
 369     }
 370   result[i] = NULL;
 371
 372   /* Free the input array.  */
 373   for (i = 0; array[i] != NULL; i++)
 374     free (array[i]);
 375   free ((char *) array);
 376
 377   return (result);
 378 }
 379 \f
 380 /* Do globbing on PATHNAME.  Return an array of pathnames that match,
 381    marking the end of the array with a null-pointer as an element.
 382    If no pathnames match, then the array is empty (first element is null).
 383    If there isn't enough memory, then return NULL.
 384    If a file system error occurs, return -1; `errno' has the error code.  */
 385 char **
 386 glob_filename (pathname)
 387      char *pathname;
 388 {
 389   char **result;
 390   unsigned int result_size;
 391   char *directory_name, *filename;
 392   unsigned int directory_len;
 393
 394   result = (char **) malloc (sizeof (char *));
 395   result_size = 1;
 396   if (result == NULL)
 397     return (NULL);
 398
 399   result[0] = NULL;
 400
 401   /* Find the filename.  */
 402   filename = strrchr (pathname, '/');
 403   if (filename == NULL)
 404     {
 405       filename = pathname;
 406       directory_name = "";
 407       directory_len = 0;
 408     }
 409   else
 410     {
 411       directory_len = (filename - pathname) + 1;
 412       directory_name = (char *) alloca (directory_len + 1);
 413
 414       bcopy (pathname, directory_name, directory_len);
 415       directory_name[directory_len] = '\0';
 416       ++filename;
 417     }
 418
 419   /* If directory_name contains globbing characters, then we
 420      have to expand the previous levels.  Just recurse. */
 421   if (glob_pattern_p (directory_name))
 422     {
 423       char **directories;
 424       register unsigned int i;
 425
 426       if (directory_name[directory_len - 1] == '/')
 427         directory_name[directory_len - 1] = '\0';
 428
 429       directories = glob_filename (directory_name);
 430
 431       if (directories == NULL)
 432         goto memory_error;
 433       else if (directories == (char **)&glob_error_return)
 434         {
 435           free ((char *)result);
 436           return ((char **) &glob_error_return);
 437         }
 438       else if (*directories == NULL)
 439         {
 440           free ((char *) directories);
 441           free ((char *) result);
 442           return ((char **) &glob_error_return);
 443         }
 444
 445       /* We have successfully globbed the preceding directory name.
 446          For each name in DIRECTORIES, call glob_vector on it and
 447          FILENAME.  Concatenate the results together.  */
 448       for (i = 0; directories[i] != NULL; ++i)
 449         {
 450           char **temp_results;
 451
 452           /* Scan directory even on a NULL pathname.  That way, `*h/'
 453              returns only directories ending in `h', instead of all
 454              files ending in `h' with a `/' appended. */
 455           temp_results = glob_vector (filename, directories[i]);
 456
 457           /* Handle error cases. */
 458           if (temp_results == NULL)
 459             goto memory_error;
 460           else if (temp_results == (char **)&glob_error_return)
 461             /* This filename is probably not a directory.  Ignore it.  */
 462             ;
 463           else
 464             {
 465               char **array;
 466               register unsigned int l;
 467
 468               array = glob_dir_to_array (directories[i], temp_results);
 469               l = 0;
 470               while (array[l] != NULL)
 471                 ++l;
 472
 473               result =
 474                 (char **)realloc (result, (result_size + l) * sizeof (char *));
 475
 476               if (result == NULL)
 477                 goto memory_error;
 478
 479               for (l = 0; array[l] != NULL; ++l)
 480                 result[result_size++ - 1] = array[l];
 481
 482               result[result_size - 1] = NULL;
 483
 484               /* Note that the elements of ARRAY are not freed.  */
 485               free ((char *) array);
 486             }
 487         }
 488       /* Free the directories.  */
 489       for (i = 0; directories[i]; i++)
 490         free (directories[i]);
 491
 492       free ((char *) directories);
 493
 494       return (result);
 495     }
 496
 497   /* If there is only a directory name, return it. */
 498   if (*filename == '\0')
 499     {
 500       result = (char **) realloc ((char *) result, 2 * sizeof (char *));
 501       if (result == NULL)
 502         return (NULL);
 503       result[0] = (char *) malloc (directory_len + 1);
 504       if (result[0] == NULL)
 505         goto memory_error;
 506       bcopy (directory_name, result[0], directory_len + 1);
 507       result[1] = NULL;
 508       return (result);
 509     }
 510   else
 511     {
 512       char **temp_results;
 513
 514       /* There are no unquoted globbing characters in DIRECTORY_NAME.
 515          Dequote it before we try to open the directory since there may
 516          be quoted globbing characters which should be treated verbatim. */
 517       if (directory_len > 0)
 518         dequote_pathname (directory_name);
 519
 520       /* We allocated a small array called RESULT, which we won't be using.
 521          Free that memory now. */
 522       free (result);
 523
 524       /* Just return what glob_vector () returns appended to the
 525          directory name. */
 526       temp_results =
 527         glob_vector (filename, (directory_len == 0 ? "." : directory_name));
 528
 529       if (temp_results == NULL || temp_results == (char **)&glob_error_return)
 530         return (temp_results);
 531
 532       return (glob_dir_to_array (directory_name, temp_results));
 533     }
 534
 535   /* We get to memory_error if the program has run out of memory, or
 536      if this is the shell, and we have been interrupted. */
 537  memory_error:
 538   if (result != NULL)
 539     {
 540       register unsigned int i;
 541       for (i = 0; result[i] != NULL; ++i)
 542         free (result[i]);
 543       free ((char *) result);
 544     }
 545 #if defined (SHELL)
 546   if (interrupt_state)
 547     throw_to_top_level ();
 548 #endif /* SHELL */
 549   return (NULL);
 550 }
 551 \f
 552 #if defined (TEST)
 553
 554 main (argc, argv)
 555      int argc;
 556      char **argv;
 557 {
 558   unsigned int i;
 559
 560   for (i = 1; i < argc; ++i)
 561     {
 562       char **value = glob_filename (argv[i]);
 563       if (value == NULL)
 564         puts ("Out of memory.");
 565       else if (value == &glob_error_return)
 566         perror (argv[i]);
 567       else
 568         for (i = 0; value[i] != NULL; i++)
 569           puts (value[i]);
 570     }
 571
 572   exit (0);
 573 }
 574 #endif  /* TEST.  */