gnu/usr.bin/man/man/glob.c

   1 /* File-name wildcard pattern matching for GNU.
   2    Copyright (C) 1985, 1988, 1989, 1990, 1991 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 \f
  18 /* $FreeBSD$ */
  19
  20 /* To whomever it may concern: I have never seen the code which most
  21    Unix programs use to perform this function.  I wrote this from scratch
  22    based on specifications for the pattern matching.  --RMS.  */
  23
  24 #ifdef SHELL
  25 #include "config.h"
  26 #endif /* SHELL */
  27
  28 #include <sys/types.h>
  29
  30 #if defined (USGr3) && !defined (DIRENT)
  31 #define DIRENT
  32 #endif /* USGr3 */
  33 #if defined (Xenix) && !defined (SYSNDIR)
  34 #define SYSNDIR
  35 #endif /* Xenix */
  36
  37 #if defined (POSIX) || defined (DIRENT) || defined (__GNU_LIBRARY__)
  38 #include <dirent.h>
  39 #define direct dirent
  40 #define D_NAMLEN(d) strlen((d)->d_name)
  41 #else /* not POSIX or DIRENT or __GNU_LIBRARY__ */
  42 #define D_NAMLEN(d) ((d)->d_namlen)
  43 #ifdef USG
  44 #if defined (SYSNDIR)
  45 #include <sys/ndir.h>
  46 #else /* SYSNDIR */
  47 #include "ndir.h"
  48 #endif /* not SYSNDIR */
  49 #else /* not USG */
  50 #include <sys/dir.h>
  51 #endif /* USG */
  52 #endif /* POSIX or DIRENT or __GNU_LIBRARY__ */
  53
  54 #if defined (_POSIX_SOURCE)
  55 /* Posix does not require that the d_ino field be present, and some
  56    systems do not provide it. */
  57 #define REAL_DIR_ENTRY(dp) 1
  58 #else
  59 #define REAL_DIR_ENTRY(dp) (dp->d_ino != 0)
  60 #endif /* _POSIX_SOURCE */
  61
  62 #if defined (STDC_HEADERS) || defined (__GNU_LIBRARY__)
  63 #include <stdlib.h>
  64 #include <string.h>
  65 #define STDC_STRINGS
  66 #else /* STDC_HEADERS or __GNU_LIBRARY__ */
  67
  68 #if defined (USG)
  69 #include <string.h>
  70 #ifndef POSIX
  71 #include <memory.h>
  72 #endif /* POSIX */
  73 #define STDC_STRINGS
  74 #else /* not USG */
  75 #ifdef NeXT
  76 #include <string.h>
  77 #else /* NeXT */
  78 #include <strings.h>
  79 #endif /* NeXT */
  80 /* Declaring bcopy causes errors on systems whose declarations are different.
  81    If the declaration is omitted, everything works fine.  */
  82 #endif /* not USG */
  83
  84 extern char *malloc ();
  85 extern char *realloc ();
  86 extern void free ();
  87
  88 #ifndef NULL
  89 #define NULL 0
  90 #endif
  91 #endif  /* Not STDC_HEADERS or __GNU_LIBRARY__.  */
  92
  93 #ifdef STDC_STRINGS
  94 #define bcopy(s, d, n) memcpy ((d), (s), (n))
  95 #define index strchr
  96 #define rindex strrchr
  97 #endif /* STDC_STRINGS */
  98
  99 #ifndef alloca
 100 #ifdef __GNUC__
 101 #define alloca __builtin_alloca
 102 #else /* Not GCC.  */
 103 #ifdef sparc
 104 #include <alloca.h>
 105 #else /* Not sparc.  */
 106 extern char *alloca ();
 107 #endif /* sparc.  */
 108 #endif /* GCC.  */
 109 #endif
 110
 111 /* Nonzero if '*' and '?' do not match an initial '.' for glob_filename.  */
 112 int noglob_dot_filenames = 1;
 113
 114 static int glob_match_after_star ();
 115
 116 #ifdef __FreeBSD__
 117 static int collate_range_cmp(a, b)
 118         int a, b;
 119 {
 120         static char s[2][2];
 121
 122         s[0][0] = a;
 123         s[1][0] = b;
 124         return (strcoll(s[0], s[1]));
 125 }
 126 #endif
 127 \f
 128 /* Return nonzero if PATTERN has any special globbing chars in it.  */
 129
 130 int
 131 glob_pattern_p (pattern)
 132      char *pattern;
 133 {
 134   register char *p = pattern;
 135   register char c;
 136   int open = 0;
 137
 138   while ((c = *p++) != '\0')
 139     switch (c)
 140       {
 141       case '?':
 142       case '*':
 143         return 1;
 144
 145       case '[':         /* Only accept an open brace if there is a close */
 146         open++;         /* brace to match it.  Bracket expressions must be */
 147         continue;       /* complete, according to Posix.2 */
 148       case ']':
 149         if (open)
 150           return 1;
 151         continue;
 152
 153       case '\\':
 154         if (*p++ == '\0')
 155           return 0;
 156       }
 157
 158   return 0;
 159 }
 160 \f
 161
 162 /* Match the pattern PATTERN against the string TEXT;
 163    return 1 if it matches, 0 otherwise.
 164
 165    A match means the entire string TEXT is used up in matching.
 166
 167    In the pattern string, `*' matches any sequence of characters,
 168    `?' matches any character, [SET] matches any character in the specified set,
 169    [!SET] matches any character not in the specified set.
 170
 171    A set is composed of characters or ranges; a range looks like
 172    character hyphen character (as in 0-9 or A-Z).
 173    [0-9a-zA-Z_] is the set of characters allowed in C identifiers.
 174    Any other character in the pattern must be matched exactly.
 175
 176    To suppress the special syntactic significance of any of `[]*?!-\',
 177    and match the character exactly, precede it with a `\'.
 178
 179    If DOT_SPECIAL is nonzero,
 180    `*' and `?' do not match `.' at the beginning of TEXT.  */
 181
 182 int
 183 glob_match (pattern, text, dot_special)
 184      char *pattern, *text;
 185      int dot_special;
 186 {
 187   register char *p = pattern, *t = text;
 188   register char c;
 189
 190   while ((c = *p++) != '\0')
 191     switch (c)
 192       {
 193       case '?':
 194         if (*t == '\0' || (dot_special && t == text && *t == '.'))
 195           return 0;
 196         else
 197           ++t;
 198         break;
 199
 200       case '\\':
 201         if (*p++ != *t++)
 202           return 0;
 203         break;
 204
 205       case '*':
 206         if (dot_special && t == text && *t == '.')
 207           return 0;
 208         return glob_match_after_star (p, t);
 209
 210       case '[':
 211         {
 212           register char c1 = *t++;
 213           int invert;
 214           char *cp1 = p;
 215
 216           if (c1 == '\0')
 217             return 0;
 218
 219           invert = (*p == '!');
 220
 221           if (invert)
 222             p++;
 223
 224           c = *p++;
 225           while (1)
 226             {
 227               register char cstart = c, cend = c;
 228
 229               if (c == '\\')
 230                 {
 231                   cstart = *p++;
 232                   cend = cstart;
 233                 }
 234
 235               if (cstart == '\0')
 236                 {
 237                   /* Missing ']'. */
 238                   if (c1 != '[')
 239                     return 0;
 240                   /* matched a single bracket */
 241                   p = cp1;
 242                   goto breakbracket;
 243                 }
 244
 245               c = *p++;
 246
 247               if (c == '-')
 248                 {
 249                   cend = *p++;
 250                   if (cend == '\\')
 251                     cend = *p++;
 252                   if (cend == '\0')
 253                     return 0;
 254                   c = *p++;
 255                 }
 256 #ifdef __FreeBSD__
 257               if (   collate_range_cmp (c1, cstart) >= 0
 258                   && collate_range_cmp (c1, cend) <= 0
 259                  )
 260 #else
 261               if (c1 >= cstart && c1 <= cend)
 262 #endif
 263                 goto match;
 264               if (c == ']')
 265                 break;
 266             }
 267           if (!invert)
 268             return 0;
 269           break;
 270
 271         match:
 272           /* Skip the rest of the [...] construct that already matched.  */
 273           while (c != ']')
 274             {
 275               if (c == '\0')
 276                 return 0;
 277               c = *p++;
 278               if (c == '\0')
 279                 return 0;
 280               if (c == '\\')
 281                 p++;
 282             }
 283           if (invert)
 284             return 0;
 285           breakbracket:
 286           break;
 287         }
 288
 289       default:
 290         if (c != *t++)
 291           return 0;
 292       }
 293
 294   return *t == '\0';
 295 }
 296 \f
 297 /* Like glob_match, but match PATTERN against any final segment of TEXT.  */
 298
 299 static int
 300 glob_match_after_star (pattern, text)
 301      char *pattern, *text;
 302 {
 303   register char *p = pattern, *t = text;
 304   register char c, c1;
 305
 306   while ((c = *p++) == '?' || c == '*')
 307     if (c == '?' && *t++ == '\0')
 308       return 0;
 309
 310   if (c == '\0')
 311     return 1;
 312
 313   if (c == '\\')
 314     c1 = *p;
 315   else
 316     c1 = c;
 317
 318   --p;
 319   while (1)
 320     {
 321       if ((c == '[' || *t == c1) && glob_match (p, t, 0))
 322         return 1;
 323       if (*t++ == '\0')
 324         return 0;
 325     }
 326 }
 327 \f
 328 /* Return a vector of names of files in directory DIR
 329    whose names match glob pattern PAT.
 330    The names are not in any particular order.
 331    Wildcards at the beginning of PAT do not match an initial period
 332    if noglob_dot_filenames is nonzero.
 333
 334    The vector is terminated by an element that is a null pointer.
 335
 336    To free the space allocated, first free the vector's elements,
 337    then free the vector.
 338
 339    Return NULL if cannot get enough memory to hold the pointer
 340    and the names.
 341
 342    Return -1 if cannot access directory DIR.
 343    Look in errno for more information.  */
 344
 345 char **
 346 glob_vector (pat, dir)
 347      char *pat;
 348      char *dir;
 349 {
 350   struct globval
 351   {
 352     struct globval *next;
 353     char *name;
 354   };
 355
 356   DIR *d;
 357   register struct direct *dp;
 358   struct globval *lastlink;
 359   register struct globval *nextlink;
 360   register char *nextname;
 361   unsigned int count;
 362   int lose;
 363   register char **name_vector;
 364   register unsigned int i;
 365 #ifdef ALLOCA_MISSING
 366   struct globval *templink;
 367 #endif
 368
 369   d = opendir (dir);
 370   if (d == NULL)
 371     return (char **) -1;
 372
 373   lastlink = NULL;
 374   count = 0;
 375   lose = 0;
 376
 377   /* Scan the directory, finding all names that match.
 378      For each name that matches, allocate a struct globval
 379      on the stack and store the name in it.
 380      Chain those structs together; lastlink is the front of the chain.  */
 381   while (1)
 382     {
 383 #if defined (SHELL)
 384       /* Make globbing interruptible in the bash shell. */
 385       extern int interrupt_state;
 386
 387       if (interrupt_state)
 388         {
 389           closedir (d);
 390           lose = 1;
 391           goto lost;
 392         }
 393 #endif /* SHELL */
 394
 395       dp = readdir (d);
 396       if (dp == NULL)
 397         break;
 398       if (REAL_DIR_ENTRY (dp)
 399           && glob_match (pat, dp->d_name, noglob_dot_filenames))
 400         {
 401 #ifdef ALLOCA_MISSING
 402           nextlink = (struct globval *) malloc (sizeof (struct globval));
 403 #else
 404           nextlink = (struct globval *) alloca (sizeof (struct globval));
 405 #endif
 406           nextlink->next = lastlink;
 407           i = D_NAMLEN (dp) + 1;
 408           nextname = (char *) malloc (i);
 409           if (nextname == NULL)
 410             {
 411               lose = 1;
 412               break;
 413             }
 414           lastlink = nextlink;
 415           nextlink->name = nextname;
 416           bcopy (dp->d_name, nextname, i);
 417           count++;
 418         }
 419     }
 420   closedir (d);
 421
 422   if (!lose)
 423     {
 424       name_vector = (char **) malloc ((count + 1) * sizeof (char *));
 425       lose |= name_vector == NULL;
 426     }
 427
 428   /* Have we run out of memory?  */
 429 #ifdef  SHELL
 430  lost:
 431 #endif
 432   if (lose)
 433     {
 434       /* Here free the strings we have got.  */
 435       while (lastlink)
 436         {
 437           free (lastlink->name);
 438 #ifdef ALLOCA_MISSING
 439           templink = lastlink->next;
 440           free ((char *) lastlink);
 441           lastlink = templink;
 442 #else
 443           lastlink = lastlink->next;
 444 #endif
 445         }
 446       return NULL;
 447     }
 448
 449   /* Copy the name pointers from the linked list into the vector.  */
 450   for (i = 0; i < count; ++i)
 451     {
 452       name_vector[i] = lastlink->name;
 453 #ifdef ALLOCA_MISSING
 454       templink = lastlink->next;
 455       free ((char *) lastlink);
 456       lastlink = templink;
 457 #else
 458       lastlink = lastlink->next;
 459 #endif
 460     }
 461
 462   name_vector[count] = NULL;
 463   return name_vector;
 464 }
 465 \f
 466 /* Return a new array, replacing ARRAY, which is the concatenation
 467    of each string in ARRAY to DIR.
 468    Return NULL if out of memory.  */
 469
 470 static char **
 471 glob_dir_to_array (dir, array)
 472      char *dir, **array;
 473 {
 474   register unsigned int i, l;
 475   int add_slash = 0;
 476   char **result;
 477
 478   l = strlen (dir);
 479   if (l == 0)
 480     return array;
 481
 482   if (dir[l - 1] != '/')
 483     add_slash++;
 484
 485   for (i = 0; array[i] != NULL; i++)
 486     ;
 487
 488   result = (char **) malloc ((i + 1) * sizeof (char *));
 489   if (result == NULL)
 490     return NULL;
 491
 492   for (i = 0; array[i] != NULL; i++)
 493     {
 494       result[i] = (char *) malloc (1 + l + add_slash + strlen (array[i]));
 495       if (result[i] == NULL)
 496         return NULL;
 497       strcpy (result[i], dir);
 498       if (add_slash)
 499         result[i][l] = '/';
 500       strcpy (result[i] + l + add_slash, array[i]);
 501     }
 502   result[i] = NULL;
 503
 504   /* Free the input array.  */
 505   for (i = 0; array[i] != NULL; i++)
 506     free (array[i]);
 507   free ((char *) array);
 508   return result;
 509 }
 510 \f
 511 /* Do globbing on PATHNAME.  Return an array of pathnames that match,
 512    marking the end of the array with a null-pointer as an element.
 513    If no pathnames match, then the array is empty (first element is null).
 514    If there isn't enough memory, then return NULL.
 515    If a file system error occurs, return -1; `errno' has the error code.
 516
 517    Wildcards at the beginning of PAT, or following a slash,
 518    do not match an initial period if noglob_dot_filenames is nonzero.  */
 519
 520 char **
 521 glob_filename (pathname)
 522      char *pathname;
 523 {
 524   char **result;
 525   unsigned int result_size;
 526   char *directory_name, *filename;
 527   unsigned int directory_len;
 528
 529   result = (char **) malloc (sizeof (char *));
 530   result_size = 1;
 531   if (result == NULL)
 532     return NULL;
 533
 534   result[0] = NULL;
 535
 536   /* Find the filename.  */
 537   filename = rindex (pathname, '/');
 538   if (filename == NULL)
 539     {
 540       filename = pathname;
 541       directory_name = "";
 542       directory_len = 0;
 543     }
 544   else
 545     {
 546       directory_len = (filename - pathname) + 1;
 547 #ifdef ALLOCA_MISSING
 548       directory_name = (char *) malloc (directory_len + 1);
 549 #else
 550       directory_name = (char *) alloca (directory_len + 1);
 551 #endif
 552       bcopy (pathname, directory_name, directory_len);
 553       directory_name[directory_len] = '\0';
 554       ++filename;
 555     }
 556
 557   /* If directory_name contains globbing characters, then we
 558      have to expand the previous levels.  Just recurse. */
 559   if (glob_pattern_p (directory_name))
 560     {
 561       char **directories;
 562       register unsigned int i;
 563
 564       if (directory_name[directory_len - 1] == '/')
 565         directory_name[directory_len - 1] = '\0';
 566
 567       directories = glob_filename (directory_name);
 568 #ifdef ALLOCA_MISSING
 569       free ((char *) directory_name);
 570 #endif
 571       if (directories == NULL)
 572         goto memory_error;
 573       else if (directories == (char **) -1)
 574         return (char **) -1;
 575       else if (*directories == NULL)
 576         {
 577           free ((char *) directories);
 578           return (char **) -1;
 579         }
 580
 581       /* We have successfully globbed the preceding directory name.
 582          For each name in DIRECTORIES, call glob_vector on it and
 583          FILENAME.  Concatenate the results together.  */
 584       for (i = 0; directories[i] != NULL; i++)
 585         {
 586           char **temp_results = glob_vector (filename, directories[i]);
 587           if (temp_results == NULL)
 588             goto memory_error;
 589           else if (temp_results == (char **) -1)
 590             /* This filename is probably not a directory.  Ignore it.  */
 591             ;
 592           else
 593             {
 594               char **array = glob_dir_to_array (directories[i], temp_results);
 595               register unsigned int l;
 596
 597               l = 0;
 598               while (array[l] != NULL)
 599                 ++l;
 600
 601               result = (char **) realloc (result,
 602                                           (result_size + l) * sizeof (char *));
 603               if (result == NULL)
 604                 goto memory_error;
 605
 606               for (l = 0; array[l] != NULL; ++l)
 607                 result[result_size++ - 1] = array[l];
 608               result[result_size - 1] = NULL;
 609               free ((char *) array);
 610             }
 611         }
 612       /* Free the directories.  */
 613       for (i = 0; directories[i] != NULL; i++)
 614         free (directories[i]);
 615       free ((char *) directories);
 616
 617       return result;
 618     }
 619
 620   /* If there is only a directory name, return it. */
 621   if (*filename == '\0')
 622     {
 623       result = (char **) realloc ((char *) result, 2 * sizeof (char *));
 624       if (result != NULL)
 625         {
 626           result[0] = (char *) malloc (directory_len + 1);
 627           if (result[0] == NULL)
 628             {
 629 #ifdef ALLOCA_MISSING
 630               free ((char *) directory_name);
 631 #endif
 632               goto memory_error;
 633             }
 634           bcopy (directory_name, result[0], directory_len + 1);
 635           result[1] = NULL;
 636         }
 637 #ifdef ALLOCA_MISSING
 638       free ((char *) directory_name);
 639 #endif
 640       return result;
 641     }
 642   else
 643     {
 644       /* Otherwise, just return what glob_vector
 645          returns appended to the directory name. */
 646       char **temp_results = glob_vector (filename,
 647                                          (directory_len == 0
 648                                           ? "." : directory_name));
 649
 650       if (temp_results == NULL || temp_results == (char **) -1)
 651         {
 652 #ifdef NO_ALLOCA
 653           free ((char *) directory_name);
 654 #endif
 655           return temp_results;
 656         }
 657
 658       temp_results = glob_dir_to_array (directory_name, temp_results);
 659 #ifdef NO_ALLOCA
 660       free ((char *) directory_name);
 661 #endif
 662       return temp_results;
 663     }
 664
 665   /* We get to memory error if the program has run out of memory, or
 666      if this is the shell, and we have been interrupted. */
 667  memory_error:
 668   if (result != NULL)
 669     {
 670       register unsigned int i;
 671       for (i = 0; result[i] != NULL; ++i)
 672         free (result[i]);
 673       free ((char *) result);
 674     }
 675 #if defined (SHELL)
 676   {
 677     extern int interrupt_state;
 678
 679     if (interrupt_state)
 680       throw_to_top_level ();
 681   }
 682 #endif /* SHELL */
 683   return NULL;
 684 }
 685 \f
 686 #ifdef TEST
 687
 688 main (argc, argv)
 689      int argc;
 690      char **argv;
 691 {
 692   char **value;
 693   int i, optind;
 694
 695   for (optind = 1; optind < argc; optind++)
 696     {
 697       value = glob_filename (argv[optind]);
 698       if (value == NULL)
 699         puts ("virtual memory exhausted");
 700       else if (value == (char **) -1)
 701         perror (argv[optind]);
 702       else
 703         for (i = 0; value[i] != NULL; i++)
 704           puts (value[i]);
 705     }
 706   exit (0);
 707 }
 708
 709 #endif /* TEST */