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