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 2, 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., 59 Temple Place, Suite 330, Boston, MA 02111 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) && !defined (STRUCT_DIRENT_HAS_D_INO)
  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) && !defined (bcopy)
  79 #  define bcopy(s, d, n) ((void) memcpy ((d), (s), (n)))
  80 #endif /* !HAVE_BCOPY && !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, *npat;
 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       npat = (char *)malloc (strlen (pat) + 1);
 301       if (nextname == 0 || npat == 0)
 302         lose = 1;
 303       else
 304         {
 305           strcpy (npat, pat);
 306           dequote_pathname (npat);
 307
 308           strcpy (nextname, dir);
 309           nextname[dirlen++] = '/';
 310           strcpy (nextname + dirlen, npat);
 311
 312           if (GLOB_TESTNAME (nextname) >= 0)
 313             {
 314               free (nextname);
 315               nextlink = (struct globval *)alloca (sizeof (struct globval));
 316               nextlink->next = (struct globval *)0;
 317               lastlink = nextlink;
 318               nextlink->name = npat;
 319               count = 1;
 320             }
 321           else
 322             {
 323               free (nextname);
 324               free (npat);
 325             }
 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 leading dot need not be explicitly matched, and the pattern
 383              doesn't start with a `.', don't match `.' or `..' */
 384 #define dname dp->d_name
 385           if (noglob_dot_filenames == 0 && pat[0] != '.' &&
 386                 (pat[0] != '\\' || pat[1] != '.') &&
 387                 (dname[0] == '.' &&
 388                   (dname[1] == '\0' || (dname[1] == '.' && dname[2] == '\0'))))
 389 #undef dname
 390             continue;
 391
 392           /* If a dot must be explicity matched, check to see if they do. */
 393           if (noglob_dot_filenames && dp->d_name[0] == '.' && pat[0] != '.' &&
 394                 (pat[0] != '\\' || pat[1] != '.'))
 395             continue;
 396
 397           if (fnmatch (pat, dp->d_name, flags) != FNM_NOMATCH)
 398             {
 399               nextlink = (struct globval *) alloca (sizeof (struct globval));
 400               nextlink->next = lastlink;
 401               nextname = (char *) malloc (D_NAMLEN (dp) + 1);
 402               if (nextname == NULL)
 403                 {
 404                   lose = 1;
 405                   break;
 406                 }
 407               lastlink = nextlink;
 408               nextlink->name = nextname;
 409               bcopy (dp->d_name, nextname, D_NAMLEN (dp) + 1);
 410               ++count;
 411             }
 412         }
 413
 414       (void) closedir (d);
 415     }
 416
 417   if (lose == 0)
 418     {
 419       name_vector = (char **) malloc ((count + 1) * sizeof (char *));
 420       lose |= name_vector == NULL;
 421     }
 422
 423   /* Have we run out of memory?  */
 424   if (lose)
 425     {
 426       /* Here free the strings we have got.  */
 427       while (lastlink)
 428         {
 429           free (lastlink->name);
 430           lastlink = lastlink->next;
 431         }
 432 #if defined (SHELL)
 433       if (interrupt_state)
 434         throw_to_top_level ();
 435 #endif /* SHELL */
 436
 437       return ((char **)NULL);
 438     }
 439
 440   /* Copy the name pointers from the linked list into the vector.  */
 441   for (i = 0; i < count; ++i)
 442     {
 443       name_vector[i] = lastlink->name;
 444       lastlink = lastlink->next;
 445     }
 446
 447   name_vector[count] = NULL;
 448   return (name_vector);
 449 }
 450 \f
 451 /* Return a new array which is the concatenation of each string in ARRAY
 452    to DIR.  This function expects you to pass in an allocated ARRAY, and
 453    it takes care of free()ing that array.  Thus, you might think of this
 454    function as side-effecting ARRAY. */
 455 static char **
 456 glob_dir_to_array (dir, array)
 457      char *dir, **array;
 458 {
 459   register unsigned int i, l;
 460   int add_slash;
 461   char **result;
 462
 463   l = strlen (dir);
 464   if (l == 0)
 465     return (array);
 466
 467   add_slash = dir[l - 1] != '/';
 468
 469   i = 0;
 470   while (array[i] != NULL)
 471     ++i;
 472
 473   result = (char **) malloc ((i + 1) * sizeof (char *));
 474   if (result == NULL)
 475     return (NULL);
 476
 477   for (i = 0; array[i] != NULL; i++)
 478     {
 479       result[i] = (char *) malloc (l + (add_slash ? 1 : 0)
 480                                    + strlen (array[i]) + 1);
 481       if (result[i] == NULL)
 482         return (NULL);
 483 #if 1
 484       strcpy (result[i], dir);
 485       if (add_slash)
 486         result[i][l] = '/';
 487       strcpy (result[i] + l + add_slash, array[i]);
 488 #else
 489       (void)sprintf (result[i], "%s%s%s", dir, add_slash ? "/" : "", array[i]);
 490 #endif
 491     }
 492   result[i] = NULL;
 493
 494   /* Free the input array.  */
 495   for (i = 0; array[i] != NULL; i++)
 496     free (array[i]);
 497   free ((char *) array);
 498
 499   return (result);
 500 }
 501 \f
 502 /* Do globbing on PATHNAME.  Return an array of pathnames that match,
 503    marking the end of the array with a null-pointer as an element.
 504    If no pathnames match, then the array is empty (first element is null).
 505    If there isn't enough memory, then return NULL.
 506    If a file system error occurs, return -1; `errno' has the error code.  */
 507 char **
 508 glob_filename (pathname)
 509      char *pathname;
 510 {
 511   char **result;
 512   unsigned int result_size;
 513   char *directory_name, *filename;
 514   unsigned int directory_len;
 515
 516   result = (char **) malloc (sizeof (char *));
 517   result_size = 1;
 518   if (result == NULL)
 519     return (NULL);
 520
 521   result[0] = NULL;
 522
 523   /* Find the filename.  */
 524   filename = strrchr (pathname, '/');
 525   if (filename == NULL)
 526     {
 527       filename = pathname;
 528       directory_name = "";
 529       directory_len = 0;
 530     }
 531   else
 532     {
 533       directory_len = (filename - pathname) + 1;
 534       directory_name = (char *) alloca (directory_len + 1);
 535
 536       bcopy (pathname, directory_name, directory_len);
 537       directory_name[directory_len] = '\0';
 538       ++filename;
 539     }
 540
 541   /* If directory_name contains globbing characters, then we
 542      have to expand the previous levels.  Just recurse. */
 543   if (glob_pattern_p (directory_name))
 544     {
 545       char **directories;
 546       register unsigned int i;
 547
 548       if (directory_name[directory_len - 1] == '/')
 549         directory_name[directory_len - 1] = '\0';
 550
 551       directories = glob_filename (directory_name);
 552
 553       if (directories == NULL)
 554         goto memory_error;
 555       else if (directories == (char **)&glob_error_return)
 556         {
 557           free ((char *) result);
 558           return ((char **) &glob_error_return);
 559         }
 560       else if (*directories == NULL)
 561         {
 562           free ((char *) directories);
 563           free ((char *) result);
 564           return ((char **) &glob_error_return);
 565         }
 566
 567       /* We have successfully globbed the preceding directory name.
 568          For each name in DIRECTORIES, call glob_vector on it and
 569          FILENAME.  Concatenate the results together.  */
 570       for (i = 0; directories[i] != NULL; ++i)
 571         {
 572           char **temp_results;
 573
 574           /* Scan directory even on a NULL pathname.  That way, `*h/'
 575              returns only directories ending in `h', instead of all
 576              files ending in `h' with a `/' appended. */
 577           temp_results = glob_vector (filename, directories[i]);
 578
 579           /* Handle error cases. */
 580           if (temp_results == NULL)
 581             goto memory_error;
 582           else if (temp_results == (char **)&glob_error_return)
 583             /* This filename is probably not a directory.  Ignore it.  */
 584             ;
 585           else
 586             {
 587               char **array;
 588               register unsigned int l;
 589
 590               array = glob_dir_to_array (directories[i], temp_results);
 591               l = 0;
 592               while (array[l] != NULL)
 593                 ++l;
 594
 595               result =
 596                 (char **)realloc (result, (result_size + l) * sizeof (char *));
 597
 598               if (result == NULL)
 599                 goto memory_error;
 600
 601               for (l = 0; array[l] != NULL; ++l)
 602                 result[result_size++ - 1] = array[l];
 603
 604               result[result_size - 1] = NULL;
 605
 606               /* Note that the elements of ARRAY are not freed.  */
 607               free ((char *) array);
 608             }
 609         }
 610       /* Free the directories.  */
 611       for (i = 0; directories[i]; i++)
 612         free (directories[i]);
 613
 614       free ((char *) directories);
 615
 616       return (result);
 617     }
 618
 619   /* If there is only a directory name, return it. */
 620   if (*filename == '\0')
 621     {
 622       result = (char **) realloc ((char *) result, 2 * sizeof (char *));
 623       if (result == NULL)
 624         return (NULL);
 625       result[0] = (char *) malloc (directory_len + 1);
 626       if (result[0] == NULL)
 627         goto memory_error;
 628       bcopy (directory_name, result[0], directory_len + 1);
 629       result[1] = NULL;
 630       return (result);
 631     }
 632   else
 633     {
 634       char **temp_results;
 635
 636       /* There are no unquoted globbing characters in DIRECTORY_NAME.
 637          Dequote it before we try to open the directory since there may
 638          be quoted globbing characters which should be treated verbatim. */
 639       if (directory_len > 0)
 640         dequote_pathname (directory_name);
 641
 642       /* We allocated a small array called RESULT, which we won't be using.
 643          Free that memory now. */
 644       free (result);
 645
 646       /* Just return what glob_vector () returns appended to the
 647          directory name. */
 648       temp_results =
 649         glob_vector (filename, (directory_len == 0 ? "." : directory_name));
 650
 651       if (temp_results == NULL || temp_results == (char **)&glob_error_return)
 652         return (temp_results);
 653
 654       return (glob_dir_to_array (directory_name, temp_results));
 655     }
 656
 657   /* We get to memory_error if the program has run out of memory, or
 658      if this is the shell, and we have been interrupted. */
 659  memory_error:
 660   if (result != NULL)
 661     {
 662       register unsigned int i;
 663       for (i = 0; result[i] != NULL; ++i)
 664         free (result[i]);
 665       free ((char *) result);
 666     }
 667 #if defined (SHELL)
 668   if (interrupt_state)
 669     throw_to_top_level ();
 670 #endif /* SHELL */
 671   return (NULL);
 672 }
 673 \f
 674 #if defined (TEST)
 675
 676 main (argc, argv)
 677      int argc;
 678      char **argv;
 679 {
 680   unsigned int i;
 681
 682   for (i = 1; i < argc; ++i)
 683     {
 684       char **value = glob_filename (argv[i]);
 685       if (value == NULL)
 686         puts ("Out of memory.");
 687       else if (value == &glob_error_return)
 688         perror (argv[i]);
 689       else
 690         for (i = 0; value[i] != NULL; i++)
 691           puts (value[i]);
 692     }
 693
 694   exit (0);
 695 }
 696 #endif  /* TEST.  */