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
 484       strcpy (result[i], dir);
 485       if (add_slash)
 486         result[i][l] = '/';
 487       strcpy (result[i] + l + add_slash, array[i]);
 488     }
 489   result[i] = NULL;
 490
 491   /* Free the input array.  */
 492   for (i = 0; array[i] != NULL; i++)
 493     free (array[i]);
 494   free ((char *) array);
 495
 496   return (result);
 497 }
 498 \f
 499 /* Do globbing on PATHNAME.  Return an array of pathnames that match,
 500    marking the end of the array with a null-pointer as an element.
 501    If no pathnames match, then the array is empty (first element is null).
 502    If there isn't enough memory, then return NULL.
 503    If a file system error occurs, return -1; `errno' has the error code.  */
 504 char **
 505 glob_filename (pathname)
 506      char *pathname;
 507 {
 508   char **result;
 509   unsigned int result_size;
 510   char *directory_name, *filename;
 511   unsigned int directory_len;
 512
 513   result = (char **) malloc (sizeof (char *));
 514   result_size = 1;
 515   if (result == NULL)
 516     return (NULL);
 517
 518   result[0] = NULL;
 519
 520   /* Find the filename.  */
 521   filename = strrchr (pathname, '/');
 522   if (filename == NULL)
 523     {
 524       filename = pathname;
 525       directory_name = "";
 526       directory_len = 0;
 527     }
 528   else
 529     {
 530       directory_len = (filename - pathname) + 1;
 531       directory_name = (char *) alloca (directory_len + 1);
 532
 533       bcopy (pathname, directory_name, directory_len);
 534       directory_name[directory_len] = '\0';
 535       ++filename;
 536     }
 537
 538   /* If directory_name contains globbing characters, then we
 539      have to expand the previous levels.  Just recurse. */
 540   if (glob_pattern_p (directory_name))
 541     {
 542       char **directories;
 543       register unsigned int i;
 544
 545       if (directory_name[directory_len - 1] == '/')
 546         directory_name[directory_len - 1] = '\0';
 547
 548       directories = glob_filename (directory_name);
 549
 550       if (directories == NULL)
 551         goto memory_error;
 552       else if (directories == (char **)&glob_error_return)
 553         {
 554           free ((char *) result);
 555           return ((char **) &glob_error_return);
 556         }
 557       else if (*directories == NULL)
 558         {
 559           free ((char *) directories);
 560           free ((char *) result);
 561           return ((char **) &glob_error_return);
 562         }
 563
 564       /* We have successfully globbed the preceding directory name.
 565          For each name in DIRECTORIES, call glob_vector on it and
 566          FILENAME.  Concatenate the results together.  */
 567       for (i = 0; directories[i] != NULL; ++i)
 568         {
 569           char **temp_results;
 570
 571           /* Scan directory even on a NULL pathname.  That way, `*h/'
 572              returns only directories ending in `h', instead of all
 573              files ending in `h' with a `/' appended. */
 574           temp_results = glob_vector (filename, directories[i]);
 575
 576           /* Handle error cases. */
 577           if (temp_results == NULL)
 578             goto memory_error;
 579           else if (temp_results == (char **)&glob_error_return)
 580             /* This filename is probably not a directory.  Ignore it.  */
 581             ;
 582           else
 583             {
 584               char **array;
 585               register unsigned int l;
 586
 587               array = glob_dir_to_array (directories[i], temp_results);
 588               l = 0;
 589               while (array[l] != NULL)
 590                 ++l;
 591
 592               result =
 593                 (char **)realloc (result, (result_size + l) * sizeof (char *));
 594
 595               if (result == NULL)
 596                 goto memory_error;
 597
 598               for (l = 0; array[l] != NULL; ++l)
 599                 result[result_size++ - 1] = array[l];
 600
 601               result[result_size - 1] = NULL;
 602
 603               /* Note that the elements of ARRAY are not freed.  */
 604               free ((char *) array);
 605             }
 606         }
 607       /* Free the directories.  */
 608       for (i = 0; directories[i]; i++)
 609         free (directories[i]);
 610
 611       free ((char *) directories);
 612
 613       return (result);
 614     }
 615
 616   /* If there is only a directory name, return it. */
 617   if (*filename == '\0')
 618     {
 619       result = (char **) realloc ((char *) result, 2 * sizeof (char *));
 620       if (result == NULL)
 621         return (NULL);
 622       result[0] = (char *) malloc (directory_len + 1);
 623       if (result[0] == NULL)
 624         goto memory_error;
 625       bcopy (directory_name, result[0], directory_len + 1);
 626       result[1] = NULL;
 627       return (result);
 628     }
 629   else
 630     {
 631       char **temp_results;
 632
 633       /* There are no unquoted globbing characters in DIRECTORY_NAME.
 634          Dequote it before we try to open the directory since there may
 635          be quoted globbing characters which should be treated verbatim. */
 636       if (directory_len > 0)
 637         dequote_pathname (directory_name);
 638
 639       /* We allocated a small array called RESULT, which we won't be using.
 640          Free that memory now. */
 641       free (result);
 642
 643       /* Just return what glob_vector () returns appended to the
 644          directory name. */
 645       temp_results =
 646         glob_vector (filename, (directory_len == 0 ? "." : directory_name));
 647
 648       if (temp_results == NULL || temp_results == (char **)&glob_error_return)
 649         return (temp_results);
 650
 651       return (glob_dir_to_array (directory_name, temp_results));
 652     }
 653
 654   /* We get to memory_error if the program has run out of memory, or
 655      if this is the shell, and we have been interrupted. */
 656  memory_error:
 657   if (result != NULL)
 658     {
 659       register unsigned int i;
 660       for (i = 0; result[i] != NULL; ++i)
 661         free (result[i]);
 662       free ((char *) result);
 663     }
 664 #if defined (SHELL)
 665   if (interrupt_state)
 666     throw_to_top_level ();
 667 #endif /* SHELL */
 668   return (NULL);
 669 }
 670 \f
 671 #if defined (TEST)
 672
 673 main (argc, argv)
 674      int argc;
 675      char **argv;
 676 {
 677   unsigned int i;
 678
 679   for (i = 1; i < argc; ++i)
 680     {
 681       char **value = glob_filename (argv[i]);
 682       if (value == NULL)
 683         puts ("Out of memory.");
 684       else if (value == &glob_error_return)
 685         perror (argv[i]);
 686       else
 687         for (i = 0; value[i] != NULL; i++)
 688           puts (value[i]);
 689     }
 690
 691   exit (0);
 692 }
 693 #endif  /* TEST.  */