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