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