1 /* File-name wildcard pattern matching for GNU.
2 Copyright (C) 1985, 1988, 1989, 1990, 1991 Free Software Foundation, Inc.
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)
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.
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. */
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. */
26 #include <sys/types.h>
28 #if defined (USGr3) && !defined (DIRENT)
31 #if defined (Xenix) && !defined (SYSNDIR)
35 #if defined (POSIX) || defined (DIRENT) || defined (__GNU_LIBRARY__)
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)
46 #endif /* not SYSNDIR */
50 #endif /* POSIX or DIRENT or __GNU_LIBRARY__ */
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
57 #define REAL_DIR_ENTRY(dp) (dp->d_ino != 0)
58 #endif /* _POSIX_SOURCE */
60 #if defined (STDC_HEADERS) || defined (__GNU_LIBRARY__)
64 #else /* STDC_HEADERS or __GNU_LIBRARY__ */
78 /* Declaring bcopy causes errors on systems whose declarations are different.
79 If the declaration is omitted, everything works fine. */
82 extern char *malloc ();
83 extern char *realloc ();
89 #endif /* Not STDC_HEADERS or __GNU_LIBRARY__. */
92 #define bcopy(s, d, n) memcpy ((d), (s), (n))
94 #define rindex strrchr
95 #endif /* STDC_STRINGS */
99 #define alloca __builtin_alloca
103 #else /* Not sparc. */
104 extern char *alloca ();
109 /* Nonzero if '*' and '?' do not match an initial '.' for glob_filename. */
110 int noglob_dot_filenames = 1;
112 static int glob_match_after_star ();
115 static int collate_range_cmp (a, b)
121 if ((unsigned char)a == (unsigned char)b)
125 if ((r = strcoll(s[0], s[1])) == 0)
126 r = (unsigned char)a - (unsigned char)b;
131 /* Return nonzero if PATTERN has any special globbing chars in it. */
134 glob_pattern_p (pattern)
137 register char *p = pattern;
141 while ((c = *p++) != '\0')
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 */
165 /* Match the pattern PATTERN against the string TEXT;
166 return 1 if it matches, 0 otherwise.
168 A match means the entire string TEXT is used up in matching.
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.
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.
179 To suppress the special syntactic significance of any of `[]*?!-\',
180 and match the character exactly, precede it with a `\'.
182 If DOT_SPECIAL is nonzero,
183 `*' and `?' do not match `.' at the beginning of TEXT. */
186 glob_match (pattern, text, dot_special)
187 char *pattern, *text;
190 register char *p = pattern, *t = text;
193 while ((c = *p++) != '\0')
197 if (*t == '\0' || (dot_special && t == text && *t == '.'))
209 if (dot_special && t == text && *t == '.')
211 return glob_match_after_star (p, t);
215 register char c1 = *t++;
222 invert = (*p == '!');
230 register char cstart = c, cend = c;
243 /* matched a single bracket */
260 if ( collate_range_cmp (c1, cstart) >= 0
261 && collate_range_cmp (c1, cend) <= 0
264 if (c1 >= cstart && c1 <= cend)
275 /* Skip the rest of the [...] construct that already matched. */
300 /* Like glob_match, but match PATTERN against any final segment of TEXT. */
303 glob_match_after_star (pattern, text)
304 char *pattern, *text;
306 register char *p = pattern, *t = text;
309 while ((c = *p++) == '?' || c == '*')
310 if (c == '?' && *t++ == '\0')
324 if ((c == '[' || *t == c1) && glob_match (p, t, 0))
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.
337 The vector is terminated by an element that is a null pointer.
339 To free the space allocated, first free the vector's elements,
340 then free the vector.
342 Return NULL if cannot get enough memory to hold the pointer
345 Return -1 if cannot access directory DIR.
346 Look in errno for more information. */
349 glob_vector (pat, dir)
355 struct globval *next;
360 register struct direct *dp;
361 struct globval *lastlink;
362 register struct globval *nextlink;
363 register char *nextname;
366 register char **name_vector;
367 register unsigned int i;
368 #ifdef ALLOCA_MISSING
369 struct globval *templink;
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. */
387 /* Make globbing interruptible in the bash shell. */
388 extern int interrupt_state;
401 if (REAL_DIR_ENTRY (dp)
402 && glob_match (pat, dp->d_name, noglob_dot_filenames))
404 #ifdef ALLOCA_MISSING
405 nextlink = (struct globval *) malloc (sizeof (struct globval));
407 nextlink = (struct globval *) alloca (sizeof (struct globval));
409 nextlink->next = lastlink;
410 i = D_NAMLEN (dp) + 1;
411 nextname = (char *) malloc (i);
412 if (nextname == NULL)
418 nextlink->name = nextname;
419 bcopy (dp->d_name, nextname, i);
427 name_vector = (char **) malloc ((count + 1) * sizeof (char *));
428 lose |= name_vector == NULL;
431 /* Have we run out of memory? */
437 /* Here free the strings we have got. */
440 free (lastlink->name);
441 #ifdef ALLOCA_MISSING
442 templink = lastlink->next;
443 free ((char *) lastlink);
446 lastlink = lastlink->next;
452 /* Copy the name pointers from the linked list into the vector. */
453 for (i = 0; i < count; ++i)
455 name_vector[i] = lastlink->name;
456 #ifdef ALLOCA_MISSING
457 templink = lastlink->next;
458 free ((char *) lastlink);
461 lastlink = lastlink->next;
465 name_vector[count] = NULL;
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. */
474 glob_dir_to_array (dir, array)
477 register unsigned int i, l;
485 if (dir[l - 1] != '/')
488 for (i = 0; array[i] != NULL; i++)
491 result = (char **) malloc ((i + 1) * sizeof (char *));
495 for (i = 0; array[i] != NULL; i++)
497 result[i] = (char *) malloc (1 + l + add_slash + strlen (array[i]));
498 if (result[i] == NULL)
500 strcpy (result[i], dir);
503 strcpy (result[i] + l + add_slash, array[i]);
507 /* Free the input array. */
508 for (i = 0; array[i] != NULL; i++)
510 free ((char *) array);
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.
520 Wildcards at the beginning of PAT, or following a slash,
521 do not match an initial period if noglob_dot_filenames is nonzero. */
524 glob_filename (pathname)
528 unsigned int result_size;
529 char *directory_name, *filename;
530 unsigned int directory_len;
532 result = (char **) malloc (sizeof (char *));
539 /* Find the filename. */
540 filename = rindex (pathname, '/');
541 if (filename == NULL)
549 directory_len = (filename - pathname) + 1;
550 #ifdef ALLOCA_MISSING
551 directory_name = (char *) malloc (directory_len + 1);
553 directory_name = (char *) alloca (directory_len + 1);
555 bcopy (pathname, directory_name, directory_len);
556 directory_name[directory_len] = '\0';
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))
565 register unsigned int i;
567 if (directory_name[directory_len - 1] == '/')
568 directory_name[directory_len - 1] = '\0';
570 directories = glob_filename (directory_name);
571 #ifdef ALLOCA_MISSING
572 free ((char *) directory_name);
574 if (directories == NULL)
576 else if (directories == (char **) -1)
578 else if (*directories == NULL)
580 free ((char *) directories);
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++)
589 char **temp_results = glob_vector (filename, directories[i]);
590 if (temp_results == NULL)
592 else if (temp_results == (char **) -1)
593 /* This filename is probably not a directory. Ignore it. */
597 char **array = glob_dir_to_array (directories[i], temp_results);
598 register unsigned int l;
601 while (array[l] != NULL)
604 result = (char **) realloc (result,
605 (result_size + l) * sizeof (char *));
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);
615 /* Free the directories. */
616 for (i = 0; directories[i] != NULL; i++)
617 free (directories[i]);
618 free ((char *) directories);
623 /* If there is only a directory name, return it. */
624 if (*filename == '\0')
626 result = (char **) realloc ((char *) result, 2 * sizeof (char *));
629 result[0] = (char *) malloc (directory_len + 1);
630 if (result[0] == NULL)
632 #ifdef ALLOCA_MISSING
633 free ((char *) directory_name);
637 bcopy (directory_name, result[0], directory_len + 1);
640 #ifdef ALLOCA_MISSING
641 free ((char *) directory_name);
647 /* Otherwise, just return what glob_vector
648 returns appended to the directory name. */
649 char **temp_results = glob_vector (filename,
651 ? "." : directory_name));
653 if (temp_results == NULL || temp_results == (char **) -1)
656 free ((char *) directory_name);
661 temp_results = glob_dir_to_array (directory_name, temp_results);
663 free ((char *) directory_name);
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. */
673 register unsigned int i;
674 for (i = 0; result[i] != NULL; ++i)
676 free ((char *) result);
680 extern int interrupt_state;
683 throw_to_top_level ();
698 for (optind = 1; optind < argc; optind++)
700 value = glob_filename (argv[optind]);
702 puts ("virtual memory exhausted");
703 else if (value == (char **) -1)
704 perror (argv[optind]);
706 for (i = 0; value[i] != NULL; i++)