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