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