2005-12-20 [colin] 1.9.100cvs97
[claws.git] / src / common / fnmatch_loop.c
1 /* Copyright (C) 1991-1993, 1996-2000, 2001 Free Software Foundation, Inc.
2    This file is part of the GNU C Library.
3
4    The GNU C Library is free software; you can redistribute it and/or
5    modify it under the terms of the GNU Lesser General Public
6    License as published by the Free Software Foundation; either
7    version 2.1 of the License, or (at your option) any later version.
8
9    The GNU C Library 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 GNU
12    Lesser General Public License for more details.
13
14    You should have received a copy of the GNU Lesser General Public
15    License along with the GNU C Library; if not, write to the Free
16    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
17    02111-1307 USA.  */
18
19
20 /* Match STRING against the filename pattern PATTERN, returning zero if
21    it matches, nonzero if not.  */
22 static int FCT (const CHAR *pattern, const CHAR *string,
23                 const CHAR *string_end, int no_leading_period, int flags)
24                 internal_function;
25 static int EXT (INT opt, const CHAR *pattern, const CHAR *string,
26                 const CHAR *string_end, int no_leading_period, int flags)
27      internal_function;
28 static const CHAR *END (const CHAR *patternp) internal_function;
29
30 #ifdef WIN32
31 #define __builtin_expect(op,val) ((op) == (val))
32 #endif
33
34 static int
35 internal_function
36 FCT (pattern, string, string_end, no_leading_period, flags)
37      const CHAR *pattern;
38      const CHAR *string;
39      const CHAR *string_end;
40      int no_leading_period;
41      int flags;
42 {
43   register const CHAR *p = pattern, *n = string;
44   register UCHAR c;
45 #ifdef _LIBC
46 # if WIDE_CHAR_VERSION
47   const char *collseq = (const char *)
48     _NL_CURRENT(LC_COLLATE, _NL_COLLATE_COLLSEQWC);
49 # else
50   const UCHAR *collseq = (const UCHAR *)
51     _NL_CURRENT(LC_COLLATE, _NL_COLLATE_COLLSEQMB);
52 # endif
53 #endif
54
55   while ((c = *p++) != L('\0'))
56     {
57       int new_no_leading_period = 0;
58       c = FOLD (c);
59
60       switch (c)
61         {
62         case L('?'):
63           if (__builtin_expect (flags & FNM_EXTMATCH, 0) && *p == '(')
64             {
65               int res;
66
67               res = EXT (c, p, n, string_end, no_leading_period,
68                          flags);
69               if (res != -1)
70                 return res;
71             }
72
73           if (n == string_end)
74             return FNM_NOMATCH;
75           else if (*n == L('/') && (flags & FNM_FILE_NAME))
76             return FNM_NOMATCH;
77           else if (*n == L('.') && no_leading_period)
78             return FNM_NOMATCH;
79           break;
80
81         case L('\\'):
82           if (!(flags & FNM_NOESCAPE))
83             {
84               c = *p++;
85               if (c == L('\0'))
86                 /* Trailing \ loses.  */
87                 return FNM_NOMATCH;
88               c = FOLD (c);
89             }
90           if (n == string_end || FOLD ((UCHAR) *n) != c)
91             return FNM_NOMATCH;
92           break;
93
94         case L('*'):
95           if (__builtin_expect (flags & FNM_EXTMATCH, 0) && *p == '(')
96             {
97               int res;
98
99               res = EXT (c, p, n, string_end, no_leading_period,
100                          flags);
101               if (res != -1)
102                 return res;
103             }
104
105           if (n != string_end && *n == L('.') && no_leading_period)
106             return FNM_NOMATCH;
107
108           for (c = *p++; c == L('?') || c == L('*'); c = *p++)
109             {
110               if (*p == L('(') && (flags & FNM_EXTMATCH) != 0)
111                 {
112                   const CHAR *endp = END (p);
113                   if (endp != p)
114                     {
115                       /* This is a pattern.  Skip over it.  */
116                       p = endp;
117                       continue;
118                     }
119                 }
120
121               if (c == L('?'))
122                 {
123                   /* A ? needs to match one character.  */
124                   if (n == string_end)
125                     /* There isn't another character; no match.  */
126                     return FNM_NOMATCH;
127                   else if (*n == L('/')
128                            && __builtin_expect (flags & FNM_FILE_NAME, 0))
129                     /* A slash does not match a wildcard under
130                        FNM_FILE_NAME.  */
131                     return FNM_NOMATCH;
132                   else
133                     /* One character of the string is consumed in matching
134                        this ? wildcard, so *??? won't match if there are
135                        less than three characters.  */
136                     ++n;
137                 }
138             }
139
140           if (c == L('\0'))
141             /* The wildcard(s) is/are the last element of the pattern.
142                If the name is a file name and contains another slash
143                this means it cannot match, unless the FNM_LEADING_DIR
144                flag is set.  */
145             {
146               int result = (flags & FNM_FILE_NAME) == 0 ? 0 : FNM_NOMATCH;
147
148               if (flags & FNM_FILE_NAME)
149                 {
150                   if (flags & FNM_LEADING_DIR)
151                     result = 0;
152                   else
153                     {
154                       if (MEMCHR (n, L('/'), string_end - n) == NULL)
155                         result = 0;
156                     }
157                 }
158
159               return result;
160             }
161           else
162             {
163               const CHAR *endp;
164
165               endp = MEMCHR (n, (flags & FNM_FILE_NAME) ? L('/') : L('\0'),
166                              string_end - n);
167               if (endp == NULL)
168                 endp = string_end;
169
170               if (c == L('[')
171                   || (__builtin_expect (flags & FNM_EXTMATCH, 0) != 0
172                       && (c == L('@') || c == L('+') || c == L('!'))
173                       && *p == L('(')))
174                 {
175                   int flags2 = ((flags & FNM_FILE_NAME)
176                                 ? flags : (flags & ~FNM_PERIOD));
177                   int no_leading_period2 = no_leading_period;
178
179                   for (--p; n < endp; ++n, no_leading_period2 = 0)
180                     if (FCT (p, n, string_end, no_leading_period2, flags2)
181                         == 0)
182                       return 0;
183                 }
184               else if (c == L('/') && (flags & FNM_FILE_NAME))
185                 {
186                   while (n < string_end && *n != L('/'))
187                     ++n;
188                   if (n < string_end && *n == L('/')
189                       && (FCT (p, n + 1, string_end, flags & FNM_PERIOD, flags)
190                           == 0))
191                     return 0;
192                 }
193               else
194                 {
195                   int flags2 = ((flags & FNM_FILE_NAME)
196                                 ? flags : (flags & ~FNM_PERIOD));
197                   int no_leading_period2 = no_leading_period;
198
199                   if (c == L('\\') && !(flags & FNM_NOESCAPE))
200                     c = *p;
201                   c = FOLD (c);
202                   for (--p; n < endp; ++n, no_leading_period2 = 0)
203                     if (FOLD ((UCHAR) *n) == c
204                         && (FCT (p, n, string_end, no_leading_period2, flags2)
205                             == 0))
206                       return 0;
207                 }
208             }
209
210           /* If we come here no match is possible with the wildcard.  */
211           return FNM_NOMATCH;
212
213         case L('['):
214           {
215             /* Nonzero if the sense of the character class is inverted.  */
216             register int not;
217             CHAR cold;
218             UCHAR fn;
219
220             if (posixly_correct == 0)
221               posixly_correct = getenv ("POSIXLY_CORRECT") != NULL ? 1 : -1;
222
223             if (n == string_end)
224               return FNM_NOMATCH;
225
226             if (*n == L('.') && no_leading_period)
227               return FNM_NOMATCH;
228
229             if (*n == L('/') && (flags & FNM_FILE_NAME))
230               /* `/' cannot be matched.  */
231               return FNM_NOMATCH;
232
233             not = (*p == L('!') || (posixly_correct < 0 && *p == L('^')));
234             if (not)
235               ++p;
236
237             fn = FOLD ((UCHAR) *n);
238
239             c = *p++;
240             for (;;)
241               {
242                 if (!(flags & FNM_NOESCAPE) && c == L('\\'))
243                   {
244                     if (*p == L('\0'))
245                       return FNM_NOMATCH;
246                     c = FOLD ((UCHAR) *p);
247                     ++p;
248
249                     if (c == fn)
250                       goto matched;
251                   }
252                 else if (c == L('[') && *p == L(':'))
253                   {
254                     /* Leave room for the null.  */
255                     CHAR str[CHAR_CLASS_MAX_LENGTH + 1];
256                     size_t c1 = 0;
257 #if defined _LIBC || (defined HAVE_WCTYPE_H && defined HAVE_WCHAR_H)
258                     wctype_t wt;
259 #endif
260                     const CHAR *startp = p;
261
262                     for (;;)
263                       {
264                         if (c1 == CHAR_CLASS_MAX_LENGTH)
265                           /* The name is too long and therefore the pattern
266                              is ill-formed.  */
267                           return FNM_NOMATCH;
268
269                         c = *++p;
270                         if (c == L(':') && p[1] == L(']'))
271                           {
272                             p += 2;
273                             break;
274                           }
275                         if (c < L('a') || c >= L('z'))
276                           {
277                             /* This cannot possibly be a character class name.
278                                Match it as a normal range.  */
279                             p = startp;
280                             c = L('[');
281                             goto normal_bracket;
282                           }
283                         str[c1++] = c;
284                       }
285                     str[c1] = L('\0');
286
287 #if defined _LIBC || (defined HAVE_WCTYPE_H && defined HAVE_WCHAR_H)
288                     wt = IS_CHAR_CLASS (str);
289                     if (wt == 0)
290                       /* Invalid character class name.  */
291                       return FNM_NOMATCH;
292
293 # if defined _LIBC && ! WIDE_CHAR_VERSION
294                     /* The following code is glibc specific but does
295                        there a good job in speeding up the code since
296                        we can avoid the btowc() call.  */
297                     if (_ISCTYPE ((UCHAR) *n, wt))
298                       goto matched;
299 # else
300                     if (ISWCTYPE (BTOWC ((UCHAR) *n), wt))
301                       goto matched;
302 # endif
303 #else
304                     if ((STREQ (str, L("alnum")) && ISALNUM ((UCHAR) *n))
305                         || (STREQ (str, L("alpha")) && ISALPHA ((UCHAR) *n))
306                         || (STREQ (str, L("blank")) && ISBLANK ((UCHAR) *n))
307                         || (STREQ (str, L("cntrl")) && ISCNTRL ((UCHAR) *n))
308                         || (STREQ (str, L("digit")) && ISDIGIT ((UCHAR) *n))
309                         || (STREQ (str, L("graph")) && ISGRAPH ((UCHAR) *n))
310                         || (STREQ (str, L("lower")) && ISLOWER ((UCHAR) *n))
311                         || (STREQ (str, L("print")) && ISPRINT ((UCHAR) *n))
312                         || (STREQ (str, L("punct")) && ISPUNCT ((UCHAR) *n))
313                         || (STREQ (str, L("space")) && ISSPACE ((UCHAR) *n))
314                         || (STREQ (str, L("upper")) && ISUPPER ((UCHAR) *n))
315                         || (STREQ (str, L("xdigit")) && ISXDIGIT ((UCHAR) *n)))
316                       goto matched;
317 #endif
318                     c = *p++;
319                   }
320 #ifdef _LIBC
321                 else if (c == L('[') && *p == L('='))
322                   {
323                     UCHAR str[1];
324                     uint32_t nrules =
325                       _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
326                     const CHAR *startp = p;
327
328                     c = *++p;
329                     if (c == L('\0'))
330                       {
331                         p = startp;
332                         c = L('[');
333                         goto normal_bracket;
334                       }
335                     str[0] = c;
336
337                     c = *++p;
338                     if (c != L('=') || p[1] != L(']'))
339                       {
340                         p = startp;
341                         c = L('[');
342                         goto normal_bracket;
343                       }
344                     p += 2;
345
346                     if (nrules == 0)
347                       {
348                         if ((UCHAR) *n == str[0])
349                           goto matched;
350                       }
351                     else
352                       {
353                         const int32_t *table;
354 # if WIDE_CHAR_VERSION
355                         const int32_t *weights;
356                         const int32_t *extra;
357 # else
358                         const unsigned char *weights;
359                         const unsigned char *extra;
360 # endif
361                         const int32_t *indirect;
362                         int32_t idx;
363                         const UCHAR *cp = (const UCHAR *) str;
364
365                         /* This #include defines a local function!  */
366 # if WIDE_CHAR_VERSION
367 #  include <locale/weightwc.h>
368 # else
369 #  include <locale/weight.h>
370 # endif
371
372 # if WIDE_CHAR_VERSION
373                         table = (const int32_t *)
374                           _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEWC);
375                         weights = (const int32_t *)
376                           _NL_CURRENT (LC_COLLATE, _NL_COLLATE_WEIGHTWC);
377                         extra = (const int32_t *)
378                           _NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAWC);
379                         indirect = (const int32_t *)
380                           _NL_CURRENT (LC_COLLATE, _NL_COLLATE_INDIRECTWC);
381 # else
382                         table = (const int32_t *)
383                           _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
384                         weights = (const unsigned char *)
385                           _NL_CURRENT (LC_COLLATE, _NL_COLLATE_WEIGHTMB);
386                         extra = (const unsigned char *)
387                           _NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAMB);
388                         indirect = (const int32_t *)
389                           _NL_CURRENT (LC_COLLATE, _NL_COLLATE_INDIRECTMB);
390 # endif
391
392                         idx = findidx (&cp);
393                         if (idx != 0)
394                           {
395                             /* We found a table entry.  Now see whether the
396                                character we are currently at has the same
397                                equivalance class value.  */
398                             int len = weights[idx];
399                             int32_t idx2;
400                             const UCHAR *np = (const UCHAR *) n;
401
402                             idx2 = findidx (&np);
403                             if (idx2 != 0 && len == weights[idx2])
404                               {
405                                 int cnt = 0;
406
407                                 while (cnt < len
408                                        && (weights[idx + 1 + cnt]
409                                            == weights[idx2 + 1 + cnt]))
410                                   ++cnt;
411
412                                 if (cnt == len)
413                                   goto matched;
414                               }
415                           }
416                       }
417
418                     c = *p++;
419                   }
420 #endif
421                 else if (c == L('\0'))
422                   /* [ (unterminated) loses.  */
423                   return FNM_NOMATCH;
424                 else
425                   {
426                     int is_range = 0;
427
428 #ifdef _LIBC
429                     int is_seqval = 0;
430
431                     if (c == L('[') && *p == L('.'))
432                       {
433                         uint32_t nrules =
434                           _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
435                         const CHAR *startp = p;
436                         size_t c1 = 0;
437
438                         while (1)
439                           {
440                             c = *++p;
441                             if (c == L('.') && p[1] == L(']'))
442                               {
443                                 p += 2;
444                                 break;
445                               }
446                             if (c == '\0')
447                               return FNM_NOMATCH;
448                             ++c1;
449                           }
450
451                         /* We have to handling the symbols differently in
452                            ranges since then the collation sequence is
453                            important.  */
454                         is_range = *p == L('-') && p[1] != L('\0');
455
456                         if (nrules == 0)
457                           {
458                             /* There are no names defined in the collation
459                                data.  Therefore we only accept the trivial
460                                names consisting of the character itself.  */
461                             if (c1 != 1)
462                               return FNM_NOMATCH;
463
464                             if (!is_range && *n == startp[1])
465                               goto matched;
466
467                             cold = startp[1];
468                             c = *p++;
469                           }
470                         else
471                           {
472                             int32_t table_size;
473                             const int32_t *symb_table;
474 # ifdef WIDE_CHAR_VERSION
475                             char str[c1];
476                             unsigned int strcnt;
477 # else
478 #  define str (startp + 1)
479 # endif
480                             const unsigned char *extra;
481                             int32_t idx;
482                             int32_t elem;
483                             int32_t second;
484                             int32_t hash;
485
486 # ifdef WIDE_CHAR_VERSION
487                             /* We have to convert the name to a single-byte
488                                string.  This is possible since the names
489                                consist of ASCII characters and the internal
490                                representation is UCS4.  */
491                             for (strcnt = 0; strcnt < c1; ++strcnt)
492                               str[strcnt] = startp[1 + strcnt];
493 #endif
494
495                             table_size =
496                               _NL_CURRENT_WORD (LC_COLLATE,
497                                                 _NL_COLLATE_SYMB_HASH_SIZEMB);
498                             symb_table = (const int32_t *)
499                               _NL_CURRENT (LC_COLLATE,
500                                            _NL_COLLATE_SYMB_TABLEMB);
501                             extra = (const unsigned char *)
502                               _NL_CURRENT (LC_COLLATE,
503                                            _NL_COLLATE_SYMB_EXTRAMB);
504
505                             /* Locate the character in the hashing table.  */
506                             hash = elem_hash (str, c1);
507
508                             idx = 0;
509                             elem = hash % table_size;
510                             second = hash % (table_size - 2);
511                             while (symb_table[2 * elem] != 0)
512                               {
513                                 /* First compare the hashing value.  */
514                                 if (symb_table[2 * elem] == hash
515                                     && c1 == extra[symb_table[2 * elem + 1]]
516                                     && memcmp (str,
517                                                &extra[symb_table[2 * elem + 1]
518                                                      + 1], c1) == 0)
519                                   {
520                                     /* Yep, this is the entry.  */
521                                     idx = symb_table[2 * elem + 1];
522                                     idx += 1 + extra[idx];
523                                     break;
524                                   }
525
526                                 /* Next entry.  */
527                                 elem += second;
528                               }
529
530                             if (symb_table[2 * elem] != 0)
531                               {
532                                 /* Compare the byte sequence but only if
533                                    this is not part of a range.  */
534 # ifdef WIDE_CHAR_VERSION
535                                 int32_t *wextra;
536
537                                 idx += 1 + extra[idx];
538                                 /* Adjust for the alignment.  */
539                                 idx = (idx + 3) & ~3;
540
541                                 wextra = (int32_t *) &extra[idx + 4];
542 # endif
543
544                                 if (! is_range)
545                                   {
546 # ifdef WIDE_CHAR_VERSION
547                                     for (c1 = 0; c1 < wextra[idx]; ++c1)
548                                       if (n[c1] != wextra[1 + c1])
549                                         break;
550
551                                     if (c1 == wextra[idx])
552                                       goto matched;
553 # else
554                                     for (c1 = 0; c1 < extra[idx]; ++c1)
555                                       if (n[c1] != extra[1 + c1])
556                                         break;
557
558                                     if (c1 == extra[idx])
559                                       goto matched;
560 # endif
561                                   }
562
563                                 /* Get the collation sequence value.  */
564                                 is_seqval = 1;
565 # ifdef WIDE_CHAR_VERSION
566                                 cold = wextra[1 + wextra[idx]];
567 # else
568                                 /* Adjust for the alignment.  */
569                                 idx += 1 + extra[idx];
570                                 idx = (idx + 3) & ~4;
571                                 cold = *((int32_t *) &extra[idx]);
572 # endif
573
574                                 c = *p++;
575                               }
576                             else if (c1 == 1)
577                               {
578                                 /* No valid character.  Match it as a
579                                    single byte.  */
580                                 if (!is_range && *n == str[0])
581                                   goto matched;
582
583                                 cold = str[0];
584                                 c = *p++;
585                               }
586                             else
587                               return FNM_NOMATCH;
588                           }
589                       }
590                     else
591 # undef str
592 #endif
593                       {
594                         c = FOLD (c);
595                       normal_bracket:
596
597                         /* We have to handling the symbols differently in
598                            ranges since then the collation sequence is
599                            important.  */
600                         is_range = *p == L('-') && p[1] != L('\0');
601
602                         if (!is_range && c == fn)
603                           goto matched;
604
605                         cold = c;
606                         c = *p++;
607                       }
608
609                     if (c == L('-') && *p != L(']'))
610                       {
611 #if _LIBC
612                         /* We have to find the collation sequence
613                            value for C.  Collation sequence is nothing
614                            we can regularly access.  The sequence
615                            value is defined by the order in which the
616                            definitions of the collation values for the
617                            various characters appear in the source
618                            file.  A strange concept, nowhere
619                            documented.  */
620                         uint32_t fcollseq;
621                         uint32_t lcollseq;
622                         UCHAR cend = *p++;
623
624 # ifdef WIDE_CHAR_VERSION
625                         /* Search in the `names' array for the characters.  */
626                         fcollseq = collseq_table_lookup (collseq, fn);
627                         if (fcollseq == ~((uint32_t) 0))
628                           /* XXX We don't know anything about the character
629                              we are supposed to match.  This means we are
630                              failing.  */
631                           goto range_not_matched;
632
633                         if (is_seqval)
634                           lcollseq = cold;
635                         else
636                           lcollseq = collseq_table_lookup (collseq, cold);
637 # else
638                         fcollseq = collseq[fn];
639                         lcollseq = is_seqval ? cold : collseq[(UCHAR) cold];
640 # endif
641
642                         is_seqval = 0;
643                         if (cend == L('[') && *p == L('.'))
644                           {
645                             uint32_t nrules =
646                               _NL_CURRENT_WORD (LC_COLLATE,
647                                                 _NL_COLLATE_NRULES);
648                             const CHAR *startp = p;
649                             size_t c1 = 0;
650
651                             while (1)
652                               {
653                                 c = *++p;
654                                 if (c == L('.') && p[1] == L(']'))
655                                   {
656                                     p += 2;
657                                     break;
658                                   }
659                                 if (c == '\0')
660                                   return FNM_NOMATCH;
661                                 ++c1;
662                               }
663
664                             if (nrules == 0)
665                               {
666                                 /* There are no names defined in the
667                                    collation data.  Therefore we only
668                                    accept the trivial names consisting
669                                    of the character itself.  */
670                                 if (c1 != 1)
671                                   return FNM_NOMATCH;
672
673                                 cend = startp[1];
674                               }
675                             else
676                               {
677                                 int32_t table_size;
678                                 const int32_t *symb_table;
679 # ifdef WIDE_CHAR_VERSION
680                                 char str[c1];
681                                 unsigned int strcnt;
682 # else
683 #  define str (startp + 1)
684 # endif
685                                 const unsigned char *extra;
686                                 int32_t idx;
687                                 int32_t elem;
688                                 int32_t second;
689                                 int32_t hash;
690
691 # ifdef WIDE_CHAR_VERSION
692                                 /* We have to convert the name to a single-byte
693                                    string.  This is possible since the names
694                                    consist of ASCII characters and the internal
695                                    representation is UCS4.  */
696                                 for (strcnt = 0; strcnt < c1; ++strcnt)
697                                   str[strcnt] = startp[1 + strcnt];
698 # endif
699
700                                 table_size =
701                                   _NL_CURRENT_WORD (LC_COLLATE,
702                                                     _NL_COLLATE_SYMB_HASH_SIZEMB);
703                                 symb_table = (const int32_t *)
704                                   _NL_CURRENT (LC_COLLATE,
705                                                _NL_COLLATE_SYMB_TABLEMB);
706                                 extra = (const unsigned char *)
707                                   _NL_CURRENT (LC_COLLATE,
708                                                _NL_COLLATE_SYMB_EXTRAMB);
709
710                                 /* Locate the character in the hashing
711                                    table.  */
712                                 hash = elem_hash (str, c1);
713
714                                 idx = 0;
715                                 elem = hash % table_size;
716                                 second = hash % (table_size - 2);
717                                 while (symb_table[2 * elem] != 0)
718                                   {
719                                 /* First compare the hashing value.  */
720                                     if (symb_table[2 * elem] == hash
721                                         && (c1
722                                             == extra[symb_table[2 * elem + 1]])
723                                         && memcmp (str,
724                                                    &extra[symb_table[2 * elem + 1]
725                                                          + 1], c1) == 0)
726                                       {
727                                         /* Yep, this is the entry.  */
728                                         idx = symb_table[2 * elem + 1];
729                                         idx += 1 + extra[idx];
730                                         break;
731                                       }
732
733                                     /* Next entry.  */
734                                     elem += second;
735                                   }
736
737                                 if (symb_table[2 * elem] != 0)
738                                   {
739                                     /* Compare the byte sequence but only if
740                                        this is not part of a range.  */
741 # ifdef WIDE_CHAR_VERSION
742                                     int32_t *wextra;
743
744                                     idx += 1 + extra[idx];
745                                     /* Adjust for the alignment.  */
746                                     idx = (idx + 3) & ~4;
747
748                                     wextra = (int32_t *) &extra[idx + 4];
749 # endif
750                                     /* Get the collation sequence value.  */
751                                     is_seqval = 1;
752 # ifdef WIDE_CHAR_VERSION
753                                     cend = wextra[1 + wextra[idx]];
754 # else
755                                     /* Adjust for the alignment.  */
756                                     idx += 1 + extra[idx];
757                                     idx = (idx + 3) & ~4;
758                                     cend = *((int32_t *) &extra[idx]);
759 # endif
760                                   }
761                                 else if (symb_table[2 * elem] != 0 && c1 == 1)
762                                   {
763                                     cend = str[0];
764                                     c = *p++;
765                                   }
766                                 else
767                                   return FNM_NOMATCH;
768                               }
769 # undef str
770                           }
771                         else
772                           {
773                             if (!(flags & FNM_NOESCAPE) && cend == L('\\'))
774                               cend = *p++;
775                             if (cend == L('\0'))
776                               return FNM_NOMATCH;
777                             cend = FOLD (cend);
778                           }
779
780                         /* XXX It is not entirely clear to me how to handle
781                            characters which are not mentioned in the
782                            collation specification.  */
783                         if (
784 # ifdef WIDE_CHAR_VERSION
785                             lcollseq == 0xffffffff ||
786 # endif
787                             lcollseq <= fcollseq)
788                           {
789                             /* We have to look at the upper bound.  */
790                             uint32_t hcollseq;
791
792                             if (is_seqval)
793                               hcollseq = cend;
794                             else
795                               {
796 # ifdef WIDE_CHAR_VERSION
797                                 hcollseq =
798                                   collseq_table_lookup (collseq, cend);
799                                 if (hcollseq == ~((uint32_t) 0))
800                                   {
801                                     /* Hum, no information about the upper
802                                        bound.  The matching succeeds if the
803                                        lower bound is matched exactly.  */
804                                     if (lcollseq != fcollseq)
805                                       goto range_not_matched;
806
807                                     goto matched;
808                                   }
809 # else
810                                 hcollseq = collseq[cend];
811 # endif
812                               }
813
814                             if (lcollseq <= hcollseq && fcollseq <= hcollseq)
815                               goto matched;
816                           }
817 # ifdef WIDE_CHAR_VERSION
818                       range_not_matched:
819 # endif
820 #else
821                         /* We use a boring value comparison of the character
822                            values.  This is better than comparing using
823                            `strcoll' since the latter would have surprising
824                            and sometimes fatal consequences.  */
825                         UCHAR cend = *p++;
826
827                         if (!(flags & FNM_NOESCAPE) && cend == L('\\'))
828                           cend = *p++;
829                         if (cend == L('\0'))
830                           return FNM_NOMATCH;
831
832                         /* It is a range.  */
833                         if (cold <= fn && fn <= cend)
834                           goto matched;
835 #endif
836
837                         c = *p++;
838                       }
839                   }
840
841                 if (c == L(']'))
842                   break;
843               }
844
845             if (!not)
846               return FNM_NOMATCH;
847             break;
848
849           matched:
850             /* Skip the rest of the [...] that already matched.  */
851             do
852               {
853               ignore_next:
854                 c = *p++;
855
856                 if (c == L('\0'))
857                   /* [... (unterminated) loses.  */
858                   return FNM_NOMATCH;
859
860                 if (!(flags & FNM_NOESCAPE) && c == L('\\'))
861                   {
862                     if (*p == L('\0'))
863                       return FNM_NOMATCH;
864                     /* XXX 1003.2d11 is unclear if this is right.  */
865                     ++p;
866                   }
867                 else if (c == L('[') && *p == L(':'))
868                   {
869                     int c1 = 0;
870                     const CHAR *startp = p;
871
872                     while (1)
873                       {
874                         c = *++p;
875                         if (++c1 == CHAR_CLASS_MAX_LENGTH)
876                           return FNM_NOMATCH;
877
878                         if (*p == L(':') && p[1] == L(']'))
879                           break;
880
881                         if (c < L('a') || c >= L('z'))
882                           {
883                             p = startp;
884                             goto ignore_next;
885                           }
886                       }
887                     p += 2;
888                     c = *p++;
889                   }
890                 else if (c == L('[') && *p == L('='))
891                   {
892                     c = *++p;
893                     if (c == L('\0'))
894                       return FNM_NOMATCH;
895                     c = *++p;
896                     if (c != L('=') || p[1] != L(']'))
897                       return FNM_NOMATCH;
898                     p += 2;
899                     c = *p++;
900                   }
901                 else if (c == L('[') && *p == L('.'))
902                   {
903                     ++p;
904                     while (1)
905                       {
906                         c = *++p;
907                         if (c == '\0')
908                           return FNM_NOMATCH;
909
910                         if (*p == L('.') && p[1] == L(']'))
911                           break;
912                       }
913                     p += 2;
914                     c = *p++;
915                   }
916               }
917             while (c != L(']'));
918             if (not)
919               return FNM_NOMATCH;
920           }
921           break;
922
923         case L('+'):
924         case L('@'):
925         case L('!'):
926           if (__builtin_expect (flags & FNM_EXTMATCH, 0) && *p == '(')
927             {
928               int res;
929
930               res = EXT (c, p, n, string_end, no_leading_period, flags);
931               if (res != -1)
932                 return res;
933             }
934           goto normal_match;
935
936         case L('/'):
937           if (NO_LEADING_PERIOD (flags))
938             {
939               if (n == string_end || c != *n)
940                 return FNM_NOMATCH;
941
942               new_no_leading_period = 1;
943               break;
944             }
945           /* FALLTHROUGH */
946         default:
947         normal_match:
948           if (n == string_end || c != FOLD ((UCHAR) *n))
949             return FNM_NOMATCH;
950         }
951
952       no_leading_period = new_no_leading_period;
953       ++n;
954     }
955
956   if (n == string_end)
957     return 0;
958
959   if ((flags & FNM_LEADING_DIR) && n != string_end && *n == L('/'))
960     /* The FNM_LEADING_DIR flag says that "foo*" matches "foobar/frobozz".  */
961     return 0;
962
963   return FNM_NOMATCH;
964 }
965
966
967 static const CHAR *
968 internal_function
969 END (const CHAR *pattern)
970 {
971   const CHAR *p = pattern;
972
973   while (1)
974     if (*++p == L('\0'))
975       /* This is an invalid pattern.  */
976       return pattern;
977     else if (*p == L('['))
978       {
979         /* Handle brackets special.  */
980         if (posixly_correct == 0)
981           posixly_correct = getenv ("POSIXLY_CORRECT") != NULL ? 1 : -1;
982
983         /* Skip the not sign.  We have to recognize it because of a possibly
984            following ']'.  */
985         if (*++p == L('!') || (posixly_correct < 0 && *p == L('^')))
986           ++p;
987         /* A leading ']' is recognized as such.  */
988         if (*p == L(']'))
989           ++p;
990         /* Skip over all characters of the list.  */
991         while (*p != L(']'))
992           if (*p++ == L('\0'))
993             /* This is no valid pattern.  */
994             return pattern;
995       }
996     else if ((*p == L('?') || *p == L('*') || *p == L('+') || *p == L('@')
997               || *p == L('!')) && p[1] == L('('))
998       p = END (p + 1);
999     else if (*p == L(')'))
1000       break;
1001
1002   return p + 1;
1003 }
1004
1005 #ifdef WIN32
1006 struct patternlist
1007 {
1008   struct patternlist *next;
1009   CHAR str[0];
1010 };
1011
1012 #define xalloca malloc
1013 #define xfree   free
1014 void free_xalloca(struct patternlist **top){
1015   struct patternlist *p, *next;
1016
1017   p = *top;
1018   while (p){
1019     next = p->next;
1020     xfree(p);
1021     p = next;
1022   }
1023   *top = NULL;
1024 }
1025 #endif
1026
1027 static int
1028 internal_function
1029 EXT (INT opt, const CHAR *pattern, const CHAR *string, const CHAR *string_end,
1030      int no_leading_period, int flags)
1031 {
1032   const CHAR *startp;
1033   int level;
1034 #ifndef WIN32
1035   struct patternlist {
1036     struct patternlist *next;
1037     CHAR str[0];
1038   } *list = NULL;
1039 #else
1040   struct patternlist *list = NULL;
1041 #endif
1042   struct patternlist **lastp = &list;
1043   size_t pattern_len = STRLEN (pattern);
1044   const CHAR *p;
1045   const CHAR *rs;
1046 #ifdef WIN32
1047   static struct patternlist *xalloca_top = NULL;
1048 #endif
1049
1050   /* Parse the pattern.  Store the individual parts in the list.  */
1051   level = 0;
1052   for (startp = p = pattern + 1; level >= 0; ++p)
1053     if (*p == L('\0')) {
1054       /* This is an invalid pattern.  */
1055       free_xalloca(&xalloca_top);
1056       return -1;
1057     } else if (*p == L('[')) {
1058       /* Handle brackets special.  */
1059       if (posixly_correct == 0)
1060         posixly_correct = getenv ("POSIXLY_CORRECT") != NULL ? 1 : -1;
1061
1062       /* Skip the not sign.  We have to recognize it because of a possibly
1063            following ']'.  */
1064       if (*++p == L('!') || (posixly_correct < 0 && *p == L('^')))
1065         ++p;
1066       /* A leading ']' is recognized as such.  */
1067       if (*p == L(']'))
1068         ++p;
1069       /* Skip over all characters of the list.  */
1070       while (*p != L(']'))
1071         if (*p++ == L('\0')) {
1072           /* This is no valid pattern.  */
1073           free_xalloca(&xalloca_top);
1074           return -1;
1075         }
1076     }
1077     else if ((*p == L('?') || *p == L('*') || *p == L('+') || *p == L('@')
1078               || *p == L('!')) && p[1] == L('('))
1079       /* Remember the nesting level.  */
1080       ++level;
1081     else if (*p == L(')'))
1082       {
1083         if (level-- == 0)
1084           {
1085             /* This means we found the end of the pattern.  */
1086 #define NEW_PATTERN \
1087         struct patternlist *newp;                                             \
1088                                                                               \
1089             if (opt == L('?') || opt == L('@'))                               \
1090               newp = xalloca (sizeof (struct patternlist)                     \
1091                              + (pattern_len * sizeof (CHAR)));                \
1092             else                                                              \
1093               newp = xalloca (sizeof (struct patternlist)                     \
1094                              + ((p - startp + 1) * sizeof (CHAR)));           \
1095                 if (!xalloca_top) xalloca_top = newp;                         \
1096             *((CHAR *) MEMPCPY (newp->str, startp, p - startp)) = L('\0');    \
1097             newp->next = NULL;                                                \
1098             *lastp = newp;                                                    \
1099             lastp = &newp->next
1100             NEW_PATTERN;
1101           }
1102       }
1103     else if (*p == L('|'))
1104       {
1105         if (level == 0)
1106           {
1107             NEW_PATTERN;
1108             startp = p + 1;
1109           }
1110       }
1111   assert (list != NULL);
1112   assert (p[-1] == L(')'));
1113 #undef NEW_PATTERN
1114
1115   switch (opt)
1116     {
1117     case L('*'):
1118                 if (FCT (p, string, string_end, no_leading_period, flags) == 0) {
1119         free_xalloca(&xalloca_top);
1120         return 0;
1121       }
1122       /* FALLTHROUGH */
1123
1124     case L('+'):
1125       do
1126         {
1127           for (rs = string; rs <= string_end; ++rs)
1128             /* First match the prefix with the current pattern with the
1129                current pattern.  */
1130             if (FCT (list->str, string, rs, no_leading_period,
1131                      flags & FNM_FILE_NAME ? flags : flags & ~FNM_PERIOD) == 0
1132                 /* This was successful.  Now match the rest with the rest
1133                    of the pattern.  */
1134                 && (FCT (p, rs, string_end,
1135                          rs == string
1136                          ? no_leading_period
1137                          : rs[-1] == '/' && NO_LEADING_PERIOD (flags) ? 1 : 0,
1138                          flags & FNM_FILE_NAME
1139                          ? flags : flags & ~FNM_PERIOD) == 0
1140                     /* This didn't work.  Try the whole pattern.  */
1141                     || (rs != string
1142                         && FCT (pattern - 1, rs, string_end,
1143                                 rs == string
1144                                 ? no_leading_period
1145                                 : (rs[-1] == '/' && NO_LEADING_PERIOD (flags)
1146                                    ? 1 : 0),
1147                                 flags & FNM_FILE_NAME
1148                                 ? flags : flags & ~FNM_PERIOD) == 0)))
1149               /* It worked.  Signal success.  */
1150               free_xalloca(&xalloca_top);
1151               return 0;
1152         }
1153       while ((list = list->next) != NULL);
1154
1155       /* None of the patterns lead to a match.  */
1156       free_xalloca(&xalloca_top);
1157       return FNM_NOMATCH;
1158
1159     case L('?'):
1160       if (FCT (p, string, string_end, no_leading_period, flags) == 0) {
1161         free_xalloca(&xalloca_top);
1162         return 0;
1163       }
1164       /* FALLTHROUGH */
1165
1166     case L('@'):
1167       do
1168         /* I cannot believe it but `strcat' is actually acceptable
1169            here.  Match the entire string with the prefix from the
1170            pattern list and the rest of the pattern following the
1171            pattern list.  */
1172         if (FCT (STRCAT (list->str, p), string, string_end,
1173                  no_leading_period,
1174                  flags & FNM_FILE_NAME ? flags : flags & ~FNM_PERIOD) == 0) {
1175           /* It worked.  Signal success.  */
1176           free_xalloca(&xalloca_top);
1177           return 0;
1178         }
1179       while ((list = list->next) != NULL);
1180
1181       /* None of the patterns lead to a match.  */
1182       free_xalloca(&xalloca_top);
1183       return FNM_NOMATCH;
1184
1185     case L('!'):
1186       for (rs = string; rs <= string_end; ++rs)
1187         {
1188           struct patternlist *runp;
1189
1190           for (runp = list; runp != NULL; runp = runp->next)
1191             if (FCT (runp->str, string, rs,  no_leading_period,
1192                      flags & FNM_FILE_NAME ? flags : flags & ~FNM_PERIOD) == 0)
1193               break;
1194
1195           /* If none of the patterns matched see whether the rest does.  */
1196           if (runp == NULL
1197               && (FCT (p, rs, string_end,
1198                        rs == string
1199                        ? no_leading_period
1200                        : rs[-1] == '/' && NO_LEADING_PERIOD (flags) ? 1 : 0,
1201                        flags & FNM_FILE_NAME ? flags : flags & ~FNM_PERIOD)
1202                   == 0)){
1203             /* This is successful.  */
1204             free_xalloca(&xalloca_top);
1205             return 0;
1206           }
1207         }
1208
1209       /* None of the patterns together with the rest of the pattern
1210          lead to a match.  */
1211       free_xalloca(&xalloca_top);
1212       return FNM_NOMATCH;
1213
1214     default:
1215       assert (! "Invalid extended matching operator");
1216       break;
1217     }
1218
1219   free_xalloca(&xalloca_top);
1220   return -1;
1221 }
1222
1223
1224 #undef FOLD
1225 #undef CHAR
1226 #undef UCHAR
1227 #undef INT
1228 #undef FCT
1229 #undef EXT
1230 #undef END
1231 #undef MEMPCPY
1232 #undef MEMCHR
1233 #undef STRCOLL
1234 #undef STRLEN
1235 #undef STRCAT
1236 #undef L
1237 #undef BTOWC