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