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