1 /* Extended regular expression matching and search library.
2 Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
4 Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>.
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License along
17 with this program; if not, write to the Free Software Foundation,
18 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
20 static reg_errcode_t re_compile_internal (regex_t *preg, const char * pattern,
21 Idx length, reg_syntax_t syntax);
22 static void re_compile_fastmap_iter (regex_t *bufp,
23 const re_dfastate_t *init_state,
25 static reg_errcode_t init_dfa (re_dfa_t *dfa, Idx pat_len);
27 static void free_charset (re_charset_t *cset);
28 #endif /* RE_ENABLE_I18N */
29 static void free_workarea_compile (regex_t *preg);
30 static reg_errcode_t create_initial_state (re_dfa_t *dfa);
32 static void optimize_utf8 (re_dfa_t *dfa);
34 static reg_errcode_t analyze (regex_t *preg);
35 static reg_errcode_t preorder (bin_tree_t *root,
36 reg_errcode_t (fn (void *, bin_tree_t *)),
38 static reg_errcode_t postorder (bin_tree_t *root,
39 reg_errcode_t (fn (void *, bin_tree_t *)),
41 static reg_errcode_t optimize_subexps (void *extra, bin_tree_t *node);
42 static reg_errcode_t lower_subexps (void *extra, bin_tree_t *node);
43 static bin_tree_t *lower_subexp (reg_errcode_t *err, regex_t *preg,
45 static reg_errcode_t calc_first (void *extra, bin_tree_t *node);
46 static reg_errcode_t calc_next (void *extra, bin_tree_t *node);
47 static reg_errcode_t link_nfa_nodes (void *extra, bin_tree_t *node);
48 static Idx duplicate_node (re_dfa_t *dfa, Idx org_idx, unsigned int constraint);
49 static Idx search_duplicated_node (const re_dfa_t *dfa, Idx org_node,
50 unsigned int constraint);
51 static reg_errcode_t calc_eclosure (re_dfa_t *dfa);
52 static reg_errcode_t calc_eclosure_iter (re_node_set *new_set, re_dfa_t *dfa,
54 static reg_errcode_t calc_inveclosure (re_dfa_t *dfa);
55 static Idx fetch_number (re_string_t *input, re_token_t *token,
57 static int peek_token (re_token_t *token, re_string_t *input,
59 static bin_tree_t *parse (re_string_t *regexp, regex_t *preg,
60 reg_syntax_t syntax, reg_errcode_t *err);
61 static bin_tree_t *parse_reg_exp (re_string_t *regexp, regex_t *preg,
62 re_token_t *token, reg_syntax_t syntax,
63 Idx nest, reg_errcode_t *err);
64 static bin_tree_t *parse_branch (re_string_t *regexp, regex_t *preg,
65 re_token_t *token, reg_syntax_t syntax,
66 Idx nest, reg_errcode_t *err);
67 static bin_tree_t *parse_expression (re_string_t *regexp, regex_t *preg,
68 re_token_t *token, reg_syntax_t syntax,
69 Idx nest, reg_errcode_t *err);
70 static bin_tree_t *parse_sub_exp (re_string_t *regexp, regex_t *preg,
71 re_token_t *token, reg_syntax_t syntax,
72 Idx nest, reg_errcode_t *err);
73 static bin_tree_t *parse_dup_op (bin_tree_t *dup_elem, re_string_t *regexp,
74 re_dfa_t *dfa, re_token_t *token,
75 reg_syntax_t syntax, reg_errcode_t *err);
76 static bin_tree_t *parse_bracket_exp (re_string_t *regexp, re_dfa_t *dfa,
77 re_token_t *token, reg_syntax_t syntax,
79 static reg_errcode_t parse_bracket_element (bracket_elem_t *elem,
81 re_token_t *token, int token_len,
85 static reg_errcode_t parse_bracket_symbol (bracket_elem_t *elem,
89 static reg_errcode_t build_equiv_class (bitset sbcset,
91 Idx *equiv_class_alloc,
92 const unsigned char *name);
93 static reg_errcode_t build_charclass (unsigned REG_TRANSLATE_TYPE trans,
96 Idx *char_class_alloc,
97 const unsigned char *class_name,
99 #else /* not RE_ENABLE_I18N */
100 static reg_errcode_t build_equiv_class (bitset sbcset,
101 const unsigned char *name);
102 static reg_errcode_t build_charclass (unsigned REG_TRANSLATE_TYPE trans,
104 const unsigned char *class_name,
105 reg_syntax_t syntax);
106 #endif /* not RE_ENABLE_I18N */
107 static bin_tree_t *build_charclass_op (re_dfa_t *dfa,
108 unsigned REG_TRANSLATE_TYPE trans,
109 const unsigned char *class_name,
110 const unsigned char *extra,
111 bool non_match, reg_errcode_t *err);
112 static bin_tree_t *create_tree (re_dfa_t *dfa,
113 bin_tree_t *left, bin_tree_t *right,
114 re_token_type_t type);
115 static bin_tree_t *create_token_tree (re_dfa_t *dfa,
116 bin_tree_t *left, bin_tree_t *right,
117 const re_token_t *token);
118 static bin_tree_t *duplicate_tree (const bin_tree_t *src, re_dfa_t *dfa);
119 static void free_token (re_token_t *node);
120 static reg_errcode_t free_tree (void *extra, bin_tree_t *node);
121 static reg_errcode_t mark_opt_subexp (void *extra, bin_tree_t *node);
123 /* This table gives an error message for each of the error codes listed
124 in regex.h. Obviously the order here has to be same as there.
125 POSIX doesn't require that we do anything for REG_NOERROR,
126 but why not be nice? */
128 const char __re_error_msgid[] attribute_hidden =
130 #define REG_NOERROR_IDX 0
131 gettext_noop ("Success") /* REG_NOERROR */
133 #define REG_NOMATCH_IDX (REG_NOERROR_IDX + sizeof "Success")
134 gettext_noop ("No match") /* REG_NOMATCH */
136 #define REG_BADPAT_IDX (REG_NOMATCH_IDX + sizeof "No match")
137 gettext_noop ("Invalid regular expression") /* REG_BADPAT */
139 #define REG_ECOLLATE_IDX (REG_BADPAT_IDX + sizeof "Invalid regular expression")
140 gettext_noop ("Invalid collation character") /* REG_ECOLLATE */
142 #define REG_ECTYPE_IDX (REG_ECOLLATE_IDX + sizeof "Invalid collation character")
143 gettext_noop ("Invalid character class name") /* REG_ECTYPE */
145 #define REG_EESCAPE_IDX (REG_ECTYPE_IDX + sizeof "Invalid character class name")
146 gettext_noop ("Trailing backslash") /* REG_EESCAPE */
148 #define REG_ESUBREG_IDX (REG_EESCAPE_IDX + sizeof "Trailing backslash")
149 gettext_noop ("Invalid back reference") /* REG_ESUBREG */
151 #define REG_EBRACK_IDX (REG_ESUBREG_IDX + sizeof "Invalid back reference")
152 gettext_noop ("Unmatched [ or [^") /* REG_EBRACK */
154 #define REG_EPAREN_IDX (REG_EBRACK_IDX + sizeof "Unmatched [ or [^")
155 gettext_noop ("Unmatched ( or \\(") /* REG_EPAREN */
157 #define REG_EBRACE_IDX (REG_EPAREN_IDX + sizeof "Unmatched ( or \\(")
158 gettext_noop ("Unmatched \\{") /* REG_EBRACE */
160 #define REG_BADBR_IDX (REG_EBRACE_IDX + sizeof "Unmatched \\{")
161 gettext_noop ("Invalid content of \\{\\}") /* REG_BADBR */
163 #define REG_ERANGE_IDX (REG_BADBR_IDX + sizeof "Invalid content of \\{\\}")
164 gettext_noop ("Invalid range end") /* REG_ERANGE */
166 #define REG_ESPACE_IDX (REG_ERANGE_IDX + sizeof "Invalid range end")
167 gettext_noop ("Memory exhausted") /* REG_ESPACE */
169 #define REG_BADRPT_IDX (REG_ESPACE_IDX + sizeof "Memory exhausted")
170 gettext_noop ("Invalid preceding regular expression") /* REG_BADRPT */
172 #define REG_EEND_IDX (REG_BADRPT_IDX + sizeof "Invalid preceding regular expression")
173 gettext_noop ("Premature end of regular expression") /* REG_EEND */
175 #define REG_ESIZE_IDX (REG_EEND_IDX + sizeof "Premature end of regular expression")
176 gettext_noop ("Regular expression too big") /* REG_ESIZE */
178 #define REG_ERPAREN_IDX (REG_ESIZE_IDX + sizeof "Regular expression too big")
179 gettext_noop ("Unmatched ) or \\)") /* REG_ERPAREN */
182 const size_t __re_error_msgid_idx[] attribute_hidden =
203 /* Entry points for GNU code. */
205 /* re_compile_pattern is the GNU regular expression compiler: it
206 compiles PATTERN (of length LENGTH) and puts the result in BUFP.
207 Returns 0 if the pattern was valid, otherwise an error string.
209 Assumes the `re_allocated' (and perhaps `re_buffer') and `translate' fields
210 are set in BUFP on entry. */
213 re_compile_pattern (const char *pattern, size_t length,
214 struct re_pattern_buffer *bufp)
218 /* And GNU code determines whether or not to get register information
219 by passing null for the REGS argument to re_match, etc., not by
220 setting re_no_sub, unless REG_NO_SUB is set. */
221 bufp->re_no_sub = !!(re_syntax_options & REG_NO_SUB);
223 /* Match anchors at newline. */
224 bufp->re_newline_anchor = 1;
226 ret = re_compile_internal (bufp, pattern, length, re_syntax_options);
230 return gettext (__re_error_msgid + __re_error_msgid_idx[(int) ret]);
233 weak_alias (__re_compile_pattern, re_compile_pattern)
236 /* Set by `re_set_syntax' to the current regexp syntax to recognize. Can
237 also be assigned to arbitrarily: each pattern buffer stores its own
238 syntax, so it can be changed between regex compilations. */
239 /* This has no initializer because initialized variables in Emacs
240 become read-only after dumping. */
241 reg_syntax_t re_syntax_options;
244 /* Specify the precise syntax of regexps for compilation. This provides
245 for compatibility for various utilities which historically have
246 different, incompatible syntaxes.
248 The argument SYNTAX is a bit mask comprised of the various bits
249 defined in regex.h. We return the old syntax. */
252 re_set_syntax (reg_syntax_t syntax)
254 reg_syntax_t ret = re_syntax_options;
256 re_syntax_options = syntax;
260 weak_alias (__re_set_syntax, re_set_syntax)
264 re_compile_fastmap (struct re_pattern_buffer *bufp)
266 re_dfa_t *dfa = (re_dfa_t *) bufp->re_buffer;
267 char *fastmap = bufp->re_fastmap;
269 memset (fastmap, '\0', sizeof (char) * SBC_MAX);
270 re_compile_fastmap_iter (bufp, dfa->init_state, fastmap);
271 if (dfa->init_state != dfa->init_state_word)
272 re_compile_fastmap_iter (bufp, dfa->init_state_word, fastmap);
273 if (dfa->init_state != dfa->init_state_nl)
274 re_compile_fastmap_iter (bufp, dfa->init_state_nl, fastmap);
275 if (dfa->init_state != dfa->init_state_begbuf)
276 re_compile_fastmap_iter (bufp, dfa->init_state_begbuf, fastmap);
277 bufp->re_fastmap_accurate = 1;
281 weak_alias (__re_compile_fastmap, re_compile_fastmap)
285 __attribute ((always_inline))
286 re_set_fastmap (char *fastmap, bool icase, int ch)
290 fastmap[tolower (ch)] = 1;
293 /* Helper function for re_compile_fastmap.
294 Compile fastmap for the initial_state INIT_STATE. */
297 re_compile_fastmap_iter (regex_t *bufp, const re_dfastate_t *init_state,
300 re_dfa_t *dfa = (re_dfa_t *) bufp->re_buffer;
302 bool icase = (dfa->mb_cur_max == 1 && (bufp->re_syntax & REG_IGNORE_CASE));
303 for (node_cnt = 0; node_cnt < init_state->nodes.nelem; ++node_cnt)
305 Idx node = init_state->nodes.elems[node_cnt];
306 re_token_type_t type = dfa->nodes[node].type;
308 if (type == CHARACTER)
310 re_set_fastmap (fastmap, icase, dfa->nodes[node].opr.c);
311 #ifdef RE_ENABLE_I18N
312 if ((bufp->re_syntax & REG_IGNORE_CASE) && dfa->mb_cur_max > 1)
314 unsigned char buf[MB_LEN_MAX];
320 *p++ = dfa->nodes[node].opr.c;
321 while (++node < dfa->nodes_len
322 && dfa->nodes[node].type == CHARACTER
323 && dfa->nodes[node].mb_partial)
324 *p++ = dfa->nodes[node].opr.c;
325 memset (&state, 0, sizeof (state));
326 if (mbrtowc (&wc, (const char *) buf, p - buf,
328 && (__wcrtomb ((char *) buf, towlower (wc), &state)
330 re_set_fastmap (fastmap, false, buf[0]);
334 else if (type == SIMPLE_BRACKET)
337 for (i = 0, ch = 0; i < BITSET_WORDS; ++i)
338 for (j = 0; j < BITSET_WORD_BITS; ++j, ++ch)
339 if (dfa->nodes[node].opr.sbcset[i] & ((bitset_word) 1 << j))
340 re_set_fastmap (fastmap, icase, ch);
342 #ifdef RE_ENABLE_I18N
343 else if (type == COMPLEX_BRACKET)
346 re_charset_t *cset = dfa->nodes[node].opr.mbcset;
347 if (cset->non_match || cset->ncoll_syms || cset->nequiv_classes
348 || cset->nranges || cset->nchar_classes)
351 if (_NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES) != 0)
353 /* In this case we want to catch the bytes which are
354 the first byte of any collation elements.
355 e.g. In da_DK, we want to catch 'a' since "aa"
356 is a valid collation element, and don't catch
357 'b' since 'b' is the only collation element
358 which starts from 'b'. */
359 const int32_t *table = (const int32_t *)
360 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
361 for (i = 0; i < SBC_MAX; ++i)
363 re_set_fastmap (fastmap, icase, i);
366 if (dfa->mb_cur_max > 1)
367 for (i = 0; i < SBC_MAX; ++i)
368 if (__btowc (i) == WEOF)
369 re_set_fastmap (fastmap, icase, i);
370 # endif /* not _LIBC */
372 for (i = 0; i < cset->nmbchars; ++i)
376 memset (&state, '\0', sizeof (state));
377 if (__wcrtomb (buf, cset->mbchars[i], &state) != (size_t) -1)
378 re_set_fastmap (fastmap, icase, *(unsigned char *) buf);
379 if ((bufp->re_syntax & REG_IGNORE_CASE) && dfa->mb_cur_max > 1)
381 if (__wcrtomb (buf, towlower (cset->mbchars[i]), &state)
383 re_set_fastmap (fastmap, false, *(unsigned char *) buf);
387 #endif /* RE_ENABLE_I18N */
388 else if (type == OP_PERIOD
389 #ifdef RE_ENABLE_I18N
390 || type == OP_UTF8_PERIOD
391 #endif /* RE_ENABLE_I18N */
392 || type == END_OF_RE)
394 memset (fastmap, '\1', sizeof (char) * SBC_MAX);
395 if (type == END_OF_RE)
396 bufp->re_can_be_null = 1;
402 /* Entry point for POSIX code. */
403 /* regcomp takes a regular expression as a string and compiles it.
405 PREG is a regex_t *. We do not expect any fields to be initialized,
406 since POSIX says we shouldn't. Thus, we set
408 `re_buffer' to the compiled pattern;
409 `re_used' to the length of the compiled pattern;
410 `re_syntax' to REG_SYNTAX_POSIX_EXTENDED if the
411 REG_EXTENDED bit in CFLAGS is set; otherwise, to
412 REG_SYNTAX_POSIX_BASIC;
413 `re_newline_anchor' to REG_NEWLINE being set in CFLAGS;
414 `re_fastmap' to an allocated space for the fastmap;
415 `re_fastmap_accurate' to zero;
416 `re_nsub' to the number of subexpressions in PATTERN.
418 PATTERN is the address of the pattern string.
420 CFLAGS is a series of bits which affect compilation.
422 If REG_EXTENDED is set, we use POSIX extended syntax; otherwise, we
423 use POSIX basic syntax.
425 If REG_NEWLINE is set, then . and [^...] don't match newline.
426 Also, regexec will try a match beginning after every newline.
428 If REG_ICASE is set, then we considers upper- and lowercase
429 versions of letters to be equivalent when matching.
431 If REG_NOSUB is set, then when PREG is passed to regexec, that
432 routine will report only success or failure, and nothing about the
435 It returns 0 if it succeeds, nonzero if it doesn't. (See regex.h for
436 the return codes and their meanings.) */
439 regcomp (regex_t *__restrict preg, const char *__restrict pattern, int cflags)
442 reg_syntax_t syntax = ((cflags & REG_EXTENDED) ? REG_SYNTAX_POSIX_EXTENDED
443 : REG_SYNTAX_POSIX_BASIC);
445 preg->re_buffer = NULL;
446 preg->re_allocated = 0;
449 /* Try to allocate space for the fastmap. */
450 preg->re_fastmap = re_malloc (char, SBC_MAX);
451 if (BE (preg->re_fastmap == NULL, 0))
454 syntax |= (cflags & REG_ICASE) ? REG_IGNORE_CASE : 0;
456 /* If REG_NEWLINE is set, newlines are treated differently. */
457 if (cflags & REG_NEWLINE)
458 { /* REG_NEWLINE implies neither . nor [^...] match newline. */
459 syntax &= ~REG_DOT_NEWLINE;
460 syntax |= REG_HAT_LISTS_NOT_NEWLINE;
461 /* It also changes the matching behavior. */
462 preg->re_newline_anchor = 1;
465 preg->re_newline_anchor = 0;
466 preg->re_no_sub = !!(cflags & REG_NOSUB);
467 preg->re_translate = NULL;
469 ret = re_compile_internal (preg, pattern, strlen (pattern), syntax);
471 /* POSIX doesn't distinguish between an unmatched open-group and an
472 unmatched close-group: both are REG_EPAREN. */
473 if (ret == REG_ERPAREN)
476 /* We have already checked preg->re_fastmap != NULL. */
477 if (BE (ret == REG_NOERROR, 1))
478 /* Compute the fastmap now, since regexec cannot modify the pattern
479 buffer. This function never fails in this implementation. */
480 (void) re_compile_fastmap (preg);
483 /* Some error occurred while compiling the expression. */
484 re_free (preg->re_fastmap);
485 preg->re_fastmap = NULL;
491 weak_alias (__regcomp, regcomp)
494 /* Returns a message corresponding to an error code, ERRCODE, returned
495 from either regcomp or regexec. We don't use PREG here. */
498 regerror (int errcode, const regex_t *__restrict preg,
499 char *__restrict errbuf, size_t errbuf_size)
505 || errcode >= (int) (sizeof (__re_error_msgid_idx)
506 / sizeof (__re_error_msgid_idx[0])), 0))
507 /* Only error codes returned by the rest of the code should be passed
508 to this routine. If we are given anything else, or if other regex
509 code generates an invalid error code, then the program has a bug.
510 Dump core so we can fix it. */
513 msg = gettext (__re_error_msgid + __re_error_msgid_idx[errcode]);
515 msg_size = strlen (msg) + 1; /* Includes the null. */
517 if (BE (errbuf_size != 0, 1))
519 if (BE (msg_size > errbuf_size, 0))
521 #if defined HAVE_MEMPCPY || defined _LIBC
522 *((char *) __mempcpy (errbuf, msg, errbuf_size - 1)) = '\0';
524 memcpy (errbuf, msg, errbuf_size - 1);
525 errbuf[errbuf_size - 1] = 0;
529 memcpy (errbuf, msg, msg_size);
535 weak_alias (__regerror, regerror)
539 #ifdef RE_ENABLE_I18N
540 /* This static array is used for the map to single-byte characters when
541 UTF-8 is used. Otherwise we would allocate memory just to initialize
542 it the same all the time. UTF-8 is the preferred encoding so this is
543 a worthwhile optimization. */
544 static const bitset utf8_sb_map =
546 /* Set the first 128 bits. */
547 # if 2 < BITSET_WORDS
550 # if 4 < BITSET_WORDS
553 # if 6 < BITSET_WORDS
556 # if 8 < BITSET_WORDS
557 # error "Invalid BITSET_WORDS"
560 >> (SBC_MAX % BITSET_WORD_BITS == 0
562 : BITSET_WORD_BITS - SBC_MAX % BITSET_WORD_BITS))
568 free_dfa_content (re_dfa_t *dfa)
573 for (i = 0; i < dfa->nodes_len; ++i)
574 free_token (dfa->nodes + i);
575 re_free (dfa->nexts);
576 for (i = 0; i < dfa->nodes_len; ++i)
578 if (dfa->eclosures != NULL)
579 re_node_set_free (dfa->eclosures + i);
580 if (dfa->inveclosures != NULL)
581 re_node_set_free (dfa->inveclosures + i);
582 if (dfa->edests != NULL)
583 re_node_set_free (dfa->edests + i);
585 re_free (dfa->edests);
586 re_free (dfa->eclosures);
587 re_free (dfa->inveclosures);
588 re_free (dfa->nodes);
590 if (dfa->state_table)
591 for (i = 0; i <= dfa->state_hash_mask; ++i)
593 struct re_state_table_entry *entry = dfa->state_table + i;
594 for (j = 0; j < entry->num; ++j)
596 re_dfastate_t *state = entry->array[j];
599 re_free (entry->array);
601 re_free (dfa->state_table);
602 #ifdef RE_ENABLE_I18N
603 if (dfa->sb_char != utf8_sb_map)
604 re_free (dfa->sb_char);
606 re_free (dfa->subexp_map);
608 re_free (dfa->re_str);
615 /* Free dynamically allocated space used by PREG. */
618 regfree (regex_t *preg)
620 re_dfa_t *dfa = (re_dfa_t *) preg->re_buffer;
621 if (BE (dfa != NULL, 1))
622 free_dfa_content (dfa);
623 preg->re_buffer = NULL;
624 preg->re_allocated = 0;
626 re_free (preg->re_fastmap);
627 preg->re_fastmap = NULL;
629 re_free (preg->re_translate);
630 preg->re_translate = NULL;
633 weak_alias (__regfree, regfree)
636 /* Entry points compatible with 4.2 BSD regex library. We don't define
637 them unless specifically requested. */
639 #if defined _REGEX_RE_COMP || defined _LIBC
641 /* BSD has one and only one pattern buffer. */
642 static struct re_pattern_buffer re_comp_buf;
646 /* Make these definitions weak in libc, so POSIX programs can redefine
647 these names if they don't use our functions, and still use
648 regcomp/regexec above without link errors. */
651 re_comp (const char *s)
658 if (!re_comp_buf.re_buffer)
659 return gettext ("No previous regular expression");
663 if (re_comp_buf.re_buffer)
665 fastmap = re_comp_buf.re_fastmap;
666 re_comp_buf.re_fastmap = NULL;
667 __regfree (&re_comp_buf);
668 memset (&re_comp_buf, '\0', sizeof (re_comp_buf));
669 re_comp_buf.re_fastmap = fastmap;
672 if (re_comp_buf.re_fastmap == NULL)
674 re_comp_buf.re_fastmap = (char *) malloc (SBC_MAX);
675 if (re_comp_buf.re_fastmap == NULL)
676 return (char *) gettext (__re_error_msgid
677 + __re_error_msgid_idx[(int) REG_ESPACE]);
680 /* Since `re_exec' always passes NULL for the `regs' argument, we
681 don't need to initialize the pattern buffer fields which affect it. */
683 /* Match anchors at newlines. */
684 re_comp_buf.re_newline_anchor = 1;
686 ret = re_compile_internal (&re_comp_buf, s, strlen (s), re_syntax_options);
691 /* Yes, we're discarding `const' here if !HAVE_LIBINTL. */
692 return (char *) gettext (__re_error_msgid + __re_error_msgid_idx[(int) ret]);
696 libc_freeres_fn (free_mem)
698 __regfree (&re_comp_buf);
702 #endif /* _REGEX_RE_COMP */
704 /* Internal entry point.
705 Compile the regular expression PATTERN, whose length is LENGTH.
706 SYNTAX indicate regular expression's syntax. */
709 re_compile_internal (regex_t *preg, const char *pattern, Idx length,
712 reg_errcode_t err = REG_NOERROR;
716 /* Initialize the pattern buffer. */
717 preg->re_fastmap_accurate = 0;
718 preg->re_syntax = syntax;
719 preg->re_not_bol = preg->re_not_eol = 0;
722 preg->re_can_be_null = 0;
723 preg->re_regs_allocated = REG_UNALLOCATED;
725 /* Initialize the dfa. */
726 dfa = (re_dfa_t *) preg->re_buffer;
727 if (BE (preg->re_allocated < sizeof (re_dfa_t), 0))
729 /* If zero allocated, but buffer is non-null, try to realloc
730 enough space. This loses if buffer's address is bogus, but
731 that is the user's responsibility. If buffer is null this
732 is a simple allocation. */
733 dfa = re_realloc (preg->re_buffer, re_dfa_t, 1);
736 preg->re_allocated = sizeof (re_dfa_t);
737 preg->re_buffer = (unsigned char *) dfa;
739 preg->re_used = sizeof (re_dfa_t);
741 __libc_lock_init (dfa->lock);
743 err = init_dfa (dfa, length);
744 if (BE (err != REG_NOERROR, 0))
746 free_dfa_content (dfa);
747 preg->re_buffer = NULL;
748 preg->re_allocated = 0;
752 dfa->re_str = re_malloc (char, length + 1);
753 strncpy (dfa->re_str, pattern, length + 1);
756 err = re_string_construct (®exp, pattern, length, preg->re_translate,
757 syntax & REG_IGNORE_CASE, dfa);
758 if (BE (err != REG_NOERROR, 0))
760 re_compile_internal_free_return:
761 free_workarea_compile (preg);
762 re_string_destruct (®exp);
763 free_dfa_content (dfa);
764 preg->re_buffer = NULL;
765 preg->re_allocated = 0;
769 /* Parse the regular expression, and build a structure tree. */
771 dfa->str_tree = parse (®exp, preg, syntax, &err);
772 if (BE (dfa->str_tree == NULL, 0))
773 goto re_compile_internal_free_return;
775 /* Analyze the tree and create the nfa. */
776 err = analyze (preg);
777 if (BE (err != REG_NOERROR, 0))
778 goto re_compile_internal_free_return;
780 #ifdef RE_ENABLE_I18N
781 /* If possible, do searching in single byte encoding to speed things up. */
782 if (dfa->is_utf8 && !(syntax & REG_IGNORE_CASE) && preg->re_translate == NULL)
786 /* Then create the initial state of the dfa. */
787 err = create_initial_state (dfa);
789 /* Release work areas. */
790 free_workarea_compile (preg);
791 re_string_destruct (®exp);
793 if (BE (err != REG_NOERROR, 0))
795 free_dfa_content (dfa);
796 preg->re_buffer = NULL;
797 preg->re_allocated = 0;
803 /* Initialize DFA. We use the length of the regular expression PAT_LEN
804 as the initial length of some arrays. */
807 init_dfa (re_dfa_t *dfa, Idx pat_len)
809 __re_size_t table_size;
814 memset (dfa, '\0', sizeof (re_dfa_t));
816 /* Force allocation of str_tree_storage the first time. */
817 dfa->str_tree_storage_idx = BIN_TREE_STORAGE_SIZE;
819 dfa->nodes_alloc = pat_len + 1;
820 dfa->nodes = re_xmalloc (re_token_t, dfa->nodes_alloc);
822 /* table_size = 2 ^ ceil(log pat_len) */
823 for (table_size = 1; table_size <= pat_len; table_size <<= 1)
824 if (0 < (Idx) -1 && table_size == 0)
827 dfa->state_table = re_calloc (struct re_state_table_entry, table_size);
828 dfa->state_hash_mask = table_size - 1;
830 dfa->mb_cur_max = MB_CUR_MAX;
832 if (dfa->mb_cur_max == 6
833 && strcmp (_NL_CURRENT (LC_CTYPE, _NL_CTYPE_CODESET_NAME), "UTF-8") == 0)
835 dfa->map_notascii = (_NL_CURRENT_WORD (LC_CTYPE, _NL_CTYPE_MAP_TO_NONASCII)
838 # ifdef HAVE_LANGINFO_CODESET
839 codeset_name = nl_langinfo (CODESET);
841 codeset_name = getenv ("LC_ALL");
842 if (codeset_name == NULL || codeset_name[0] == '\0')
843 codeset_name = getenv ("LC_CTYPE");
844 if (codeset_name == NULL || codeset_name[0] == '\0')
845 codeset_name = getenv ("LANG");
846 if (codeset_name == NULL)
848 else if (strchr (codeset_name, '.') != NULL)
849 codeset_name = strchr (codeset_name, '.') + 1;
852 if (strcasecmp (codeset_name, "UTF-8") == 0
853 || strcasecmp (codeset_name, "UTF8") == 0)
856 /* We check exhaustively in the loop below if this charset is a
857 superset of ASCII. */
858 dfa->map_notascii = 0;
861 #ifdef RE_ENABLE_I18N
862 if (dfa->mb_cur_max > 1)
865 dfa->sb_char = (re_bitset_ptr_t) utf8_sb_map;
870 dfa->sb_char = re_calloc (bitset_word, BITSET_WORDS);
871 if (BE (dfa->sb_char == NULL, 0))
874 /* Set the bits corresponding to single byte chars. */
875 for (i = 0, ch = 0; i < BITSET_WORDS; ++i)
876 for (j = 0; j < BITSET_WORD_BITS; ++j, ++ch)
878 wint_t wch = __btowc (ch);
880 dfa->sb_char[i] |= (bitset_word) 1 << j;
882 if (isascii (ch) && wch != ch)
883 dfa->map_notascii = 1;
890 if (BE (dfa->nodes == NULL || dfa->state_table == NULL, 0))
895 /* Initialize WORD_CHAR table, which indicate which character is
896 "word". In this case "word" means that it is the word construction
897 character used by some operators like "\<", "\>", etc. */
900 init_word_char (re_dfa_t *dfa)
903 dfa->word_ops_used = 1;
904 for (i = 0, ch = 0; i < BITSET_WORDS; ++i)
905 for (j = 0; j < BITSET_WORD_BITS; ++j, ++ch)
906 if (isalnum (ch) || ch == '_')
907 dfa->word_char[i] |= (bitset_word) 1 << j;
910 /* Free the work area which are only used while compiling. */
913 free_workarea_compile (regex_t *preg)
915 re_dfa_t *dfa = (re_dfa_t *) preg->re_buffer;
916 bin_tree_storage_t *storage, *next;
917 for (storage = dfa->str_tree_storage; storage; storage = next)
919 next = storage->next;
922 dfa->str_tree_storage = NULL;
923 dfa->str_tree_storage_idx = BIN_TREE_STORAGE_SIZE;
924 dfa->str_tree = NULL;
925 re_free (dfa->org_indices);
926 dfa->org_indices = NULL;
929 /* Create initial states for all contexts. */
932 create_initial_state (re_dfa_t *dfa)
936 re_node_set init_nodes;
938 /* Initial states have the epsilon closure of the node which is
939 the first node of the regular expression. */
940 first = dfa->str_tree->first->node_idx;
941 dfa->init_node = first;
942 err = re_node_set_init_copy (&init_nodes, dfa->eclosures + first);
943 if (BE (err != REG_NOERROR, 0))
946 /* The back-references which are in initial states can epsilon transit,
947 since in this case all of the subexpressions can be null.
948 Then we add epsilon closures of the nodes which are the next nodes of
949 the back-references. */
950 if (dfa->nbackref > 0)
951 for (i = 0; i < init_nodes.nelem; ++i)
953 Idx node_idx = init_nodes.elems[i];
954 re_token_type_t type = dfa->nodes[node_idx].type;
957 if (type != OP_BACK_REF)
959 for (clexp_idx = 0; clexp_idx < init_nodes.nelem; ++clexp_idx)
961 re_token_t *clexp_node;
962 clexp_node = dfa->nodes + init_nodes.elems[clexp_idx];
963 if (clexp_node->type == OP_CLOSE_SUBEXP
964 && clexp_node->opr.idx == dfa->nodes[node_idx].opr.idx)
967 if (clexp_idx == init_nodes.nelem)
970 if (type == OP_BACK_REF)
972 Idx dest_idx = dfa->edests[node_idx].elems[0];
973 if (!re_node_set_contains (&init_nodes, dest_idx))
975 re_node_set_merge (&init_nodes, dfa->eclosures + dest_idx);
981 /* It must be the first time to invoke acquire_state. */
982 dfa->init_state = re_acquire_state_context (&err, dfa, &init_nodes, 0);
983 /* We don't check ERR here, since the initial state must not be NULL. */
984 if (BE (dfa->init_state == NULL, 0))
986 if (dfa->init_state->has_constraint)
988 dfa->init_state_word = re_acquire_state_context (&err, dfa, &init_nodes,
990 dfa->init_state_nl = re_acquire_state_context (&err, dfa, &init_nodes,
992 dfa->init_state_begbuf = re_acquire_state_context (&err, dfa,
996 if (BE (dfa->init_state_word == NULL || dfa->init_state_nl == NULL
997 || dfa->init_state_begbuf == NULL, 0))
1001 dfa->init_state_word = dfa->init_state_nl
1002 = dfa->init_state_begbuf = dfa->init_state;
1004 re_node_set_free (&init_nodes);
1008 #ifdef RE_ENABLE_I18N
1009 /* If it is possible to do searching in single byte encoding instead of UTF-8
1010 to speed things up, set dfa->mb_cur_max to 1, clear is_utf8 and change
1011 DFA nodes where needed. */
1014 optimize_utf8 (re_dfa_t *dfa)
1018 bool mb_chars = false;
1019 bool has_period = false;
1021 for (node = 0; node < dfa->nodes_len; ++node)
1022 switch (dfa->nodes[node].type)
1025 if (dfa->nodes[node].opr.c >= 0x80)
1029 switch (dfa->nodes[node].opr.idx)
1037 /* Word anchors etc. cannot be handled. */
1047 case OP_DUP_ASTERISK:
1048 case OP_OPEN_SUBEXP:
1049 case OP_CLOSE_SUBEXP:
1051 case COMPLEX_BRACKET:
1053 case SIMPLE_BRACKET:
1054 /* Just double check. */
1057 (SBC_MAX / 2 % BITSET_WORD_BITS == 0
1059 : BITSET_WORD_BITS - SBC_MAX / 2 % BITSET_WORD_BITS);
1060 for (i = SBC_MAX / 2 / BITSET_WORD_BITS; i < BITSET_WORDS; ++i)
1062 if (dfa->nodes[node].opr.sbcset[i] >> rshift != 0)
1072 if (mb_chars || has_period)
1073 for (node = 0; node < dfa->nodes_len; ++node)
1075 if (dfa->nodes[node].type == CHARACTER
1076 && dfa->nodes[node].opr.c >= 0x80)
1077 dfa->nodes[node].mb_partial = 0;
1078 else if (dfa->nodes[node].type == OP_PERIOD)
1079 dfa->nodes[node].type = OP_UTF8_PERIOD;
1082 /* The search can be in single byte locale. */
1083 dfa->mb_cur_max = 1;
1085 dfa->has_mb_node = dfa->nbackref > 0 || has_period;
1089 /* Analyze the structure tree, and calculate "first", "next", "edest",
1090 "eclosure", and "inveclosure". */
1092 static reg_errcode_t
1093 analyze (regex_t *preg)
1095 re_dfa_t *dfa = (re_dfa_t *) preg->re_buffer;
1098 /* Allocate arrays. */
1099 dfa->nexts = re_malloc (Idx, dfa->nodes_alloc);
1100 dfa->org_indices = re_malloc (Idx, dfa->nodes_alloc);
1101 dfa->edests = re_xmalloc (re_node_set, dfa->nodes_alloc);
1102 dfa->eclosures = re_malloc (re_node_set, dfa->nodes_alloc);
1103 if (BE (dfa->nexts == NULL || dfa->org_indices == NULL || dfa->edests == NULL
1104 || dfa->eclosures == NULL, 0))
1107 dfa->subexp_map = re_xmalloc (Idx, preg->re_nsub);
1108 if (dfa->subexp_map != NULL)
1111 for (i = 0; i < preg->re_nsub; i++)
1112 dfa->subexp_map[i] = i;
1113 preorder (dfa->str_tree, optimize_subexps, dfa);
1114 for (i = 0; i < preg->re_nsub; i++)
1115 if (dfa->subexp_map[i] != i)
1117 if (i == preg->re_nsub)
1119 free (dfa->subexp_map);
1120 dfa->subexp_map = NULL;
1124 ret = postorder (dfa->str_tree, lower_subexps, preg);
1125 if (BE (ret != REG_NOERROR, 0))
1127 ret = postorder (dfa->str_tree, calc_first, dfa);
1128 if (BE (ret != REG_NOERROR, 0))
1130 preorder (dfa->str_tree, calc_next, dfa);
1131 ret = preorder (dfa->str_tree, link_nfa_nodes, dfa);
1132 if (BE (ret != REG_NOERROR, 0))
1134 ret = calc_eclosure (dfa);
1135 if (BE (ret != REG_NOERROR, 0))
1138 /* We only need this during the prune_impossible_nodes pass in regexec.c;
1139 skip it if p_i_n will not run, as calc_inveclosure can be quadratic. */
1140 if ((!preg->re_no_sub && preg->re_nsub > 0 && dfa->has_plural_match)
1143 dfa->inveclosures = re_xmalloc (re_node_set, dfa->nodes_len);
1144 if (BE (dfa->inveclosures == NULL, 0))
1146 ret = calc_inveclosure (dfa);
1152 /* Our parse trees are very unbalanced, so we cannot use a stack to
1153 implement parse tree visits. Instead, we use parent pointers and
1154 some hairy code in these two functions. */
1155 static reg_errcode_t
1156 postorder (bin_tree_t *root, reg_errcode_t (fn (void *, bin_tree_t *)),
1159 bin_tree_t *node, *prev;
1161 for (node = root; ; )
1163 /* Descend down the tree, preferably to the left (or to the right
1164 if that's the only child). */
1165 while (node->left || node->right)
1173 reg_errcode_t err = fn (extra, node);
1174 if (BE (err != REG_NOERROR, 0))
1176 if (node->parent == NULL)
1179 node = node->parent;
1181 /* Go up while we have a node that is reached from the right. */
1182 while (node->right == prev || node->right == NULL);
1187 static reg_errcode_t
1188 preorder (bin_tree_t *root, reg_errcode_t (fn (void *, bin_tree_t *)),
1193 for (node = root; ; )
1195 reg_errcode_t err = fn (extra, node);
1196 if (BE (err != REG_NOERROR, 0))
1199 /* Go to the left node, or up and to the right. */
1204 bin_tree_t *prev = NULL;
1205 while (node->right == prev || node->right == NULL)
1208 node = node->parent;
1217 /* Optimization pass: if a SUBEXP is entirely contained, strip it and tell
1218 re_search_internal to map the inner one's opr.idx to this one's. Adjust
1219 backreferences as well. Requires a preorder visit. */
1220 static reg_errcode_t
1221 optimize_subexps (void *extra, bin_tree_t *node)
1223 re_dfa_t *dfa = (re_dfa_t *) extra;
1225 if (node->token.type == OP_BACK_REF && dfa->subexp_map)
1227 int idx = node->token.opr.idx;
1228 node->token.opr.idx = dfa->subexp_map[idx];
1229 dfa->used_bkref_map |= 1 << node->token.opr.idx;
1232 else if (node->token.type == SUBEXP
1233 && node->left && node->left->token.type == SUBEXP)
1235 Idx other_idx = node->left->token.opr.idx;
1237 node->left = node->left->left;
1239 node->left->parent = node;
1241 dfa->subexp_map[other_idx] = dfa->subexp_map[node->token.opr.idx];
1242 if (other_idx < BITSET_WORD_BITS)
1243 dfa->used_bkref_map &= ~ ((bitset_word) 1 << other_idx);
1249 /* Lowering pass: Turn each SUBEXP node into the appropriate concatenation
1250 of OP_OPEN_SUBEXP, the body of the SUBEXP (if any) and OP_CLOSE_SUBEXP. */
1251 static reg_errcode_t
1252 lower_subexps (void *extra, bin_tree_t *node)
1254 regex_t *preg = (regex_t *) extra;
1255 reg_errcode_t err = REG_NOERROR;
1257 if (node->left && node->left->token.type == SUBEXP)
1259 node->left = lower_subexp (&err, preg, node->left);
1261 node->left->parent = node;
1263 if (node->right && node->right->token.type == SUBEXP)
1265 node->right = lower_subexp (&err, preg, node->right);
1267 node->right->parent = node;
1274 lower_subexp (reg_errcode_t *err, regex_t *preg, bin_tree_t *node)
1276 re_dfa_t *dfa = (re_dfa_t *) preg->re_buffer;
1277 bin_tree_t *body = node->left;
1278 bin_tree_t *op, *cls, *tree1, *tree;
1281 /* We do not optimize empty subexpressions, because otherwise we may
1282 have bad CONCAT nodes with NULL children. This is obviously not
1283 very common, so we do not lose much. An example that triggers
1284 this case is the sed "script" /\(\)/x. */
1285 && node->left != NULL
1286 && ! (node->token.opr.idx < BITSET_WORD_BITS
1287 && dfa->used_bkref_map & ((bitset_word) 1 << node->token.opr.idx)))
1290 /* Convert the SUBEXP node to the concatenation of an
1291 OP_OPEN_SUBEXP, the contents, and an OP_CLOSE_SUBEXP. */
1292 op = create_tree (dfa, NULL, NULL, OP_OPEN_SUBEXP);
1293 cls = create_tree (dfa, NULL, NULL, OP_CLOSE_SUBEXP);
1294 tree1 = body ? create_tree (dfa, body, cls, CONCAT) : cls;
1295 tree = create_tree (dfa, op, tree1, CONCAT);
1296 if (BE (tree == NULL || tree1 == NULL || op == NULL || cls == NULL, 0))
1302 op->token.opr.idx = cls->token.opr.idx = node->token.opr.idx;
1303 op->token.opt_subexp = cls->token.opt_subexp = node->token.opt_subexp;
1307 /* Pass 1 in building the NFA: compute FIRST and create unlinked automaton
1308 nodes. Requires a postorder visit. */
1309 static reg_errcode_t
1310 calc_first (void *extra, bin_tree_t *node)
1312 re_dfa_t *dfa = (re_dfa_t *) extra;
1313 if (node->token.type == CONCAT)
1315 node->first = node->left->first;
1316 node->node_idx = node->left->node_idx;
1321 node->node_idx = re_dfa_add_node (dfa, node->token);
1322 if (BE (node->node_idx == REG_MISSING, 0))
1328 /* Pass 2: compute NEXT on the tree. Preorder visit. */
1329 static reg_errcode_t
1330 calc_next (void *extra, bin_tree_t *node)
1332 switch (node->token.type)
1334 case OP_DUP_ASTERISK:
1335 node->left->next = node;
1338 node->left->next = node->right->first;
1339 node->right->next = node->next;
1343 node->left->next = node->next;
1345 node->right->next = node->next;
1351 /* Pass 3: link all DFA nodes to their NEXT node (any order will do). */
1352 static reg_errcode_t
1353 link_nfa_nodes (void *extra, bin_tree_t *node)
1355 re_dfa_t *dfa = (re_dfa_t *) extra;
1356 Idx idx = node->node_idx;
1357 reg_errcode_t err = REG_NOERROR;
1359 switch (node->token.type)
1365 assert (node->next == NULL);
1368 case OP_DUP_ASTERISK:
1372 dfa->has_plural_match = 1;
1373 if (node->left != NULL)
1374 left = node->left->first->node_idx;
1376 left = node->next->node_idx;
1377 if (node->right != NULL)
1378 right = node->right->first->node_idx;
1380 right = node->next->node_idx;
1381 assert (REG_VALID_INDEX (left));
1382 assert (REG_VALID_INDEX (right));
1383 err = re_node_set_init_2 (dfa->edests + idx, left, right);
1388 case OP_OPEN_SUBEXP:
1389 case OP_CLOSE_SUBEXP:
1390 err = re_node_set_init_1 (dfa->edests + idx, node->next->node_idx);
1394 dfa->nexts[idx] = node->next->node_idx;
1395 if (node->token.type == OP_BACK_REF)
1396 re_node_set_init_1 (dfa->edests + idx, dfa->nexts[idx]);
1400 assert (!IS_EPSILON_NODE (node->token.type));
1401 dfa->nexts[idx] = node->next->node_idx;
1408 /* Duplicate the epsilon closure of the node ROOT_NODE.
1409 Note that duplicated nodes have constraint INIT_CONSTRAINT in addition
1410 to their own constraint. */
1412 static reg_errcode_t
1413 duplicate_node_closure (re_dfa_t *dfa, Idx top_org_node,
1414 Idx top_clone_node, Idx root_node,
1415 unsigned int init_constraint)
1417 Idx org_node, clone_node;
1419 unsigned int constraint = init_constraint;
1420 for (org_node = top_org_node, clone_node = top_clone_node;;)
1422 Idx org_dest, clone_dest;
1423 if (dfa->nodes[org_node].type == OP_BACK_REF)
1425 /* If the back reference epsilon-transit, its destination must
1426 also have the constraint. Then duplicate the epsilon closure
1427 of the destination of the back reference, and store it in
1428 edests of the back reference. */
1429 org_dest = dfa->nexts[org_node];
1430 re_node_set_empty (dfa->edests + clone_node);
1431 clone_dest = duplicate_node (dfa, org_dest, constraint);
1432 if (BE (clone_dest == REG_MISSING, 0))
1434 dfa->nexts[clone_node] = dfa->nexts[org_node];
1435 ok = re_node_set_insert (dfa->edests + clone_node, clone_dest);
1439 else if (dfa->edests[org_node].nelem == 0)
1441 /* In case of the node can't epsilon-transit, don't duplicate the
1442 destination and store the original destination as the
1443 destination of the node. */
1444 dfa->nexts[clone_node] = dfa->nexts[org_node];
1447 else if (dfa->edests[org_node].nelem == 1)
1449 /* In case of the node can epsilon-transit, and it has only one
1451 org_dest = dfa->edests[org_node].elems[0];
1452 re_node_set_empty (dfa->edests + clone_node);
1453 if (dfa->nodes[org_node].type == ANCHOR)
1455 /* In case of the node has another constraint, append it. */
1456 if (org_node == root_node && clone_node != org_node)
1458 /* ...but if the node is root_node itself, it means the
1459 epsilon closure have a loop, then tie it to the
1460 destination of the root_node. */
1461 ok = re_node_set_insert (dfa->edests + clone_node,
1467 constraint |= dfa->nodes[org_node].opr.ctx_type;
1469 clone_dest = duplicate_node (dfa, org_dest, constraint);
1470 if (BE (clone_dest == REG_MISSING, 0))
1472 ok = re_node_set_insert (dfa->edests + clone_node, clone_dest);
1476 else /* dfa->edests[org_node].nelem == 2 */
1478 /* In case of the node can epsilon-transit, and it has two
1479 destinations. In the bin_tree_t and DFA, that's '|' and '*'. */
1480 org_dest = dfa->edests[org_node].elems[0];
1481 re_node_set_empty (dfa->edests + clone_node);
1482 /* Search for a duplicated node which satisfies the constraint. */
1483 clone_dest = search_duplicated_node (dfa, org_dest, constraint);
1484 if (clone_dest == REG_MISSING)
1486 /* There are no such a duplicated node, create a new one. */
1488 clone_dest = duplicate_node (dfa, org_dest, constraint);
1489 if (BE (clone_dest == REG_MISSING, 0))
1491 ok = re_node_set_insert (dfa->edests + clone_node, clone_dest);
1494 err = duplicate_node_closure (dfa, org_dest, clone_dest,
1495 root_node, constraint);
1496 if (BE (err != REG_NOERROR, 0))
1501 /* There are a duplicated node which satisfy the constraint,
1502 use it to avoid infinite loop. */
1503 ok = re_node_set_insert (dfa->edests + clone_node, clone_dest);
1508 org_dest = dfa->edests[org_node].elems[1];
1509 clone_dest = duplicate_node (dfa, org_dest, constraint);
1510 if (BE (clone_dest == REG_MISSING, 0))
1512 ok = re_node_set_insert (dfa->edests + clone_node, clone_dest);
1516 org_node = org_dest;
1517 clone_node = clone_dest;
1522 /* Search for a node which is duplicated from the node ORG_NODE, and
1523 satisfies the constraint CONSTRAINT. */
1526 search_duplicated_node (const re_dfa_t *dfa, Idx org_node,
1527 unsigned int constraint)
1530 for (idx = dfa->nodes_len - 1; dfa->nodes[idx].duplicated && idx > 0; --idx)
1532 if (org_node == dfa->org_indices[idx]
1533 && constraint == dfa->nodes[idx].constraint)
1534 return idx; /* Found. */
1536 return REG_MISSING; /* Not found. */
1539 /* Duplicate the node whose index is ORG_IDX and set the constraint CONSTRAINT.
1540 Return the index of the new node, or REG_MISSING if insufficient storage is
1544 duplicate_node (re_dfa_t *dfa, Idx org_idx, unsigned int constraint)
1546 Idx dup_idx = re_dfa_add_node (dfa, dfa->nodes[org_idx]);
1547 if (BE (dup_idx != REG_MISSING, 1))
1549 dfa->nodes[dup_idx].constraint = constraint;
1550 if (dfa->nodes[org_idx].type == ANCHOR)
1551 dfa->nodes[dup_idx].constraint |= dfa->nodes[org_idx].opr.ctx_type;
1552 dfa->nodes[dup_idx].duplicated = 1;
1554 /* Store the index of the original node. */
1555 dfa->org_indices[dup_idx] = org_idx;
1560 static reg_errcode_t
1561 calc_inveclosure (re_dfa_t *dfa)
1565 for (idx = 0; idx < dfa->nodes_len; ++idx)
1566 re_node_set_init_empty (dfa->inveclosures + idx);
1568 for (src = 0; src < dfa->nodes_len; ++src)
1570 Idx *elems = dfa->eclosures[src].elems;
1571 for (idx = 0; idx < dfa->eclosures[src].nelem; ++idx)
1573 ok = re_node_set_insert_last (dfa->inveclosures + elems[idx], src);
1582 /* Calculate "eclosure" for all the node in DFA. */
1584 static reg_errcode_t
1585 calc_eclosure (re_dfa_t *dfa)
1590 assert (dfa->nodes_len > 0);
1593 /* For each nodes, calculate epsilon closure. */
1594 for (node_idx = 0; ; ++node_idx)
1597 re_node_set eclosure_elem;
1598 if (node_idx == dfa->nodes_len)
1607 assert (dfa->eclosures[node_idx].nelem != REG_MISSING);
1610 /* If we have already calculated, skip it. */
1611 if (dfa->eclosures[node_idx].nelem != 0)
1613 /* Calculate epsilon closure of `node_idx'. */
1614 err = calc_eclosure_iter (&eclosure_elem, dfa, node_idx, true);
1615 if (BE (err != REG_NOERROR, 0))
1618 if (dfa->eclosures[node_idx].nelem == 0)
1621 re_node_set_free (&eclosure_elem);
1627 /* Calculate epsilon closure of NODE. */
1629 static reg_errcode_t
1630 calc_eclosure_iter (re_node_set *new_set, re_dfa_t *dfa, Idx node, bool root)
1633 unsigned int constraint;
1637 re_node_set eclosure;
1639 err = re_node_set_alloc (&eclosure, dfa->edests[node].nelem + 1);
1640 if (BE (err != REG_NOERROR, 0))
1643 /* This indicates that we are calculating this node now.
1644 We reference this value to avoid infinite loop. */
1645 dfa->eclosures[node].nelem = REG_MISSING;
1647 constraint = ((dfa->nodes[node].type == ANCHOR)
1648 ? dfa->nodes[node].opr.ctx_type : 0);
1649 /* If the current node has constraints, duplicate all nodes.
1650 Since they must inherit the constraints. */
1652 && dfa->edests[node].nelem
1653 && !dfa->nodes[dfa->edests[node].elems[0]].duplicated)
1655 err = duplicate_node_closure (dfa, node, node, node, constraint);
1656 if (BE (err != REG_NOERROR, 0))
1660 /* Expand each epsilon destination nodes. */
1661 if (IS_EPSILON_NODE(dfa->nodes[node].type))
1662 for (i = 0; i < dfa->edests[node].nelem; ++i)
1664 re_node_set eclosure_elem;
1665 Idx edest = dfa->edests[node].elems[i];
1666 /* If calculating the epsilon closure of `edest' is in progress,
1667 return intermediate result. */
1668 if (dfa->eclosures[edest].nelem == REG_MISSING)
1673 /* If we haven't calculated the epsilon closure of `edest' yet,
1674 calculate now. Otherwise use calculated epsilon closure. */
1675 if (dfa->eclosures[edest].nelem == 0)
1677 err = calc_eclosure_iter (&eclosure_elem, dfa, edest, false);
1678 if (BE (err != REG_NOERROR, 0))
1682 eclosure_elem = dfa->eclosures[edest];
1683 /* Merge the epsilon closure of `edest'. */
1684 re_node_set_merge (&eclosure, &eclosure_elem);
1685 /* If the epsilon closure of `edest' is incomplete,
1686 the epsilon closure of this node is also incomplete. */
1687 if (dfa->eclosures[edest].nelem == 0)
1690 re_node_set_free (&eclosure_elem);
1694 /* Epsilon closures include itself. */
1695 ok = re_node_set_insert (&eclosure, node);
1698 if (incomplete && !root)
1699 dfa->eclosures[node].nelem = 0;
1701 dfa->eclosures[node] = eclosure;
1702 *new_set = eclosure;
1706 /* Functions for token which are used in the parser. */
1708 /* Fetch a token from INPUT.
1709 We must not use this function inside bracket expressions. */
1712 fetch_token (re_token_t *result, re_string_t *input, reg_syntax_t syntax)
1714 re_string_skip_bytes (input, peek_token (result, input, syntax));
1717 /* Peek a token from INPUT, and return the length of the token.
1718 We must not use this function inside bracket expressions. */
1721 peek_token (re_token_t *token, re_string_t *input, reg_syntax_t syntax)
1725 if (re_string_eoi (input))
1727 token->type = END_OF_RE;
1731 c = re_string_peek_byte (input, 0);
1734 token->word_char = 0;
1735 #ifdef RE_ENABLE_I18N
1736 token->mb_partial = 0;
1737 if (input->mb_cur_max > 1 &&
1738 !re_string_first_byte (input, re_string_cur_idx (input)))
1740 token->type = CHARACTER;
1741 token->mb_partial = 1;
1748 if (re_string_cur_idx (input) + 1 >= re_string_length (input))
1750 token->type = BACK_SLASH;
1754 c2 = re_string_peek_byte_case (input, 1);
1756 token->type = CHARACTER;
1757 #ifdef RE_ENABLE_I18N
1758 if (input->mb_cur_max > 1)
1760 wint_t wc = re_string_wchar_at (input,
1761 re_string_cur_idx (input) + 1);
1762 token->word_char = IS_WIDE_WORD_CHAR (wc) != 0;
1766 token->word_char = IS_WORD_CHAR (c2) != 0;
1771 if (!(syntax & REG_LIMITED_OPS) && !(syntax & REG_NO_BK_VBAR))
1772 token->type = OP_ALT;
1774 case '1': case '2': case '3': case '4': case '5':
1775 case '6': case '7': case '8': case '9':
1776 if (!(syntax & REG_NO_BK_REFS))
1778 token->type = OP_BACK_REF;
1779 token->opr.idx = c2 - '1';
1783 if (!(syntax & REG_NO_GNU_OPS))
1785 token->type = ANCHOR;
1786 token->opr.ctx_type = WORD_FIRST;
1790 if (!(syntax & REG_NO_GNU_OPS))
1792 token->type = ANCHOR;
1793 token->opr.ctx_type = WORD_LAST;
1797 if (!(syntax & REG_NO_GNU_OPS))
1799 token->type = ANCHOR;
1800 token->opr.ctx_type = WORD_DELIM;
1804 if (!(syntax & REG_NO_GNU_OPS))
1806 token->type = ANCHOR;
1807 token->opr.ctx_type = NOT_WORD_DELIM;
1811 if (!(syntax & REG_NO_GNU_OPS))
1812 token->type = OP_WORD;
1815 if (!(syntax & REG_NO_GNU_OPS))
1816 token->type = OP_NOTWORD;
1819 if (!(syntax & REG_NO_GNU_OPS))
1820 token->type = OP_SPACE;
1823 if (!(syntax & REG_NO_GNU_OPS))
1824 token->type = OP_NOTSPACE;
1827 if (!(syntax & REG_NO_GNU_OPS))
1829 token->type = ANCHOR;
1830 token->opr.ctx_type = BUF_FIRST;
1834 if (!(syntax & REG_NO_GNU_OPS))
1836 token->type = ANCHOR;
1837 token->opr.ctx_type = BUF_LAST;
1841 if (!(syntax & REG_NO_BK_PARENS))
1842 token->type = OP_OPEN_SUBEXP;
1845 if (!(syntax & REG_NO_BK_PARENS))
1846 token->type = OP_CLOSE_SUBEXP;
1849 if (!(syntax & REG_LIMITED_OPS) && (syntax & REG_BK_PLUS_QM))
1850 token->type = OP_DUP_PLUS;
1853 if (!(syntax & REG_LIMITED_OPS) && (syntax & REG_BK_PLUS_QM))
1854 token->type = OP_DUP_QUESTION;
1857 if ((syntax & REG_INTERVALS) && (!(syntax & REG_NO_BK_BRACES)))
1858 token->type = OP_OPEN_DUP_NUM;
1861 if ((syntax & REG_INTERVALS) && (!(syntax & REG_NO_BK_BRACES)))
1862 token->type = OP_CLOSE_DUP_NUM;
1870 token->type = CHARACTER;
1871 #ifdef RE_ENABLE_I18N
1872 if (input->mb_cur_max > 1)
1874 wint_t wc = re_string_wchar_at (input, re_string_cur_idx (input));
1875 token->word_char = IS_WIDE_WORD_CHAR (wc) != 0;
1879 token->word_char = IS_WORD_CHAR (token->opr.c);
1884 if (syntax & REG_NEWLINE_ALT)
1885 token->type = OP_ALT;
1888 if (!(syntax & REG_LIMITED_OPS) && (syntax & REG_NO_BK_VBAR))
1889 token->type = OP_ALT;
1892 token->type = OP_DUP_ASTERISK;
1895 if (!(syntax & REG_LIMITED_OPS) && !(syntax & REG_BK_PLUS_QM))
1896 token->type = OP_DUP_PLUS;
1899 if (!(syntax & REG_LIMITED_OPS) && !(syntax & REG_BK_PLUS_QM))
1900 token->type = OP_DUP_QUESTION;
1903 if ((syntax & REG_INTERVALS) && (syntax & REG_NO_BK_BRACES))
1904 token->type = OP_OPEN_DUP_NUM;
1907 if ((syntax & REG_INTERVALS) && (syntax & REG_NO_BK_BRACES))
1908 token->type = OP_CLOSE_DUP_NUM;
1911 if (syntax & REG_NO_BK_PARENS)
1912 token->type = OP_OPEN_SUBEXP;
1915 if (syntax & REG_NO_BK_PARENS)
1916 token->type = OP_CLOSE_SUBEXP;
1919 token->type = OP_OPEN_BRACKET;
1922 token->type = OP_PERIOD;
1925 if (!(syntax & (REG_CONTEXT_INDEP_ANCHORS | REG_CARET_ANCHORS_HERE)) &&
1926 re_string_cur_idx (input) != 0)
1928 char prev = re_string_peek_byte (input, -1);
1929 if (!(syntax & REG_NEWLINE_ALT) || prev != '\n')
1932 token->type = ANCHOR;
1933 token->opr.ctx_type = LINE_FIRST;
1936 if (!(syntax & REG_CONTEXT_INDEP_ANCHORS) &&
1937 re_string_cur_idx (input) + 1 != re_string_length (input))
1940 re_string_skip_bytes (input, 1);
1941 peek_token (&next, input, syntax);
1942 re_string_skip_bytes (input, -1);
1943 if (next.type != OP_ALT && next.type != OP_CLOSE_SUBEXP)
1946 token->type = ANCHOR;
1947 token->opr.ctx_type = LINE_LAST;
1955 /* Peek a token from INPUT, and return the length of the token.
1956 We must not use this function out of bracket expressions. */
1959 peek_token_bracket (re_token_t *token, re_string_t *input, reg_syntax_t syntax)
1962 if (re_string_eoi (input))
1964 token->type = END_OF_RE;
1967 c = re_string_peek_byte (input, 0);
1970 #ifdef RE_ENABLE_I18N
1971 if (input->mb_cur_max > 1 &&
1972 !re_string_first_byte (input, re_string_cur_idx (input)))
1974 token->type = CHARACTER;
1977 #endif /* RE_ENABLE_I18N */
1979 if (c == '\\' && (syntax & REG_BACKSLASH_ESCAPE_IN_LISTS)
1980 && re_string_cur_idx (input) + 1 < re_string_length (input))
1982 /* In this case, '\' escape a character. */
1984 re_string_skip_bytes (input, 1);
1985 c2 = re_string_peek_byte (input, 0);
1987 token->type = CHARACTER;
1990 if (c == '[') /* '[' is a special char in a bracket exps. */
1994 if (re_string_cur_idx (input) + 1 < re_string_length (input))
1995 c2 = re_string_peek_byte (input, 1);
2003 token->type = OP_OPEN_COLL_ELEM;
2006 token->type = OP_OPEN_EQUIV_CLASS;
2009 if (syntax & REG_CHAR_CLASSES)
2011 token->type = OP_OPEN_CHAR_CLASS;
2014 /* else fall through. */
2016 token->type = CHARACTER;
2026 token->type = OP_CHARSET_RANGE;
2029 token->type = OP_CLOSE_BRACKET;
2032 token->type = OP_NON_MATCH_LIST;
2035 token->type = CHARACTER;
2040 /* Functions for parser. */
2042 /* Entry point of the parser.
2043 Parse the regular expression REGEXP and return the structure tree.
2044 If an error is occured, ERR is set by error code, and return NULL.
2045 This function build the following tree, from regular expression <reg_exp>:
2051 CAT means concatenation.
2052 EOR means end of regular expression. */
2055 parse (re_string_t *regexp, regex_t *preg, reg_syntax_t syntax,
2058 re_dfa_t *dfa = (re_dfa_t *) preg->re_buffer;
2059 bin_tree_t *tree, *eor, *root;
2060 re_token_t current_token;
2061 dfa->syntax = syntax;
2062 fetch_token (¤t_token, regexp, syntax | REG_CARET_ANCHORS_HERE);
2063 tree = parse_reg_exp (regexp, preg, ¤t_token, syntax, 0, err);
2064 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2066 eor = create_tree (dfa, NULL, NULL, END_OF_RE);
2068 root = create_tree (dfa, tree, eor, CONCAT);
2071 if (BE (eor == NULL || root == NULL, 0))
2079 /* This function build the following tree, from regular expression
2080 <branch1>|<branch2>:
2086 ALT means alternative, which represents the operator `|'. */
2089 parse_reg_exp (re_string_t *regexp, regex_t *preg, re_token_t *token,
2090 reg_syntax_t syntax, Idx nest, reg_errcode_t *err)
2092 re_dfa_t *dfa = (re_dfa_t *) preg->re_buffer;
2093 bin_tree_t *tree, *branch = NULL;
2094 tree = parse_branch (regexp, preg, token, syntax, nest, err);
2095 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2098 while (token->type == OP_ALT)
2100 fetch_token (token, regexp, syntax | REG_CARET_ANCHORS_HERE);
2101 if (token->type != OP_ALT && token->type != END_OF_RE
2102 && (nest == 0 || token->type != OP_CLOSE_SUBEXP))
2104 branch = parse_branch (regexp, preg, token, syntax, nest, err);
2105 if (BE (*err != REG_NOERROR && branch == NULL, 0))
2110 tree = create_tree (dfa, tree, branch, OP_ALT);
2111 if (BE (tree == NULL, 0))
2120 /* This function build the following tree, from regular expression
2127 CAT means concatenation. */
2130 parse_branch (re_string_t *regexp, regex_t *preg, re_token_t *token,
2131 reg_syntax_t syntax, Idx nest, reg_errcode_t *err)
2133 bin_tree_t *tree, *exp;
2134 re_dfa_t *dfa = (re_dfa_t *) preg->re_buffer;
2135 tree = parse_expression (regexp, preg, token, syntax, nest, err);
2136 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2139 while (token->type != OP_ALT && token->type != END_OF_RE
2140 && (nest == 0 || token->type != OP_CLOSE_SUBEXP))
2142 exp = parse_expression (regexp, preg, token, syntax, nest, err);
2143 if (BE (*err != REG_NOERROR && exp == NULL, 0))
2147 if (tree != NULL && exp != NULL)
2149 tree = create_tree (dfa, tree, exp, CONCAT);
2156 else if (tree == NULL)
2158 /* Otherwise exp == NULL, we don't need to create new tree. */
2163 /* This function build the following tree, from regular expression a*:
2170 parse_expression (re_string_t *regexp, regex_t *preg, re_token_t *token,
2171 reg_syntax_t syntax, Idx nest, reg_errcode_t *err)
2173 re_dfa_t *dfa = (re_dfa_t *) preg->re_buffer;
2175 switch (token->type)
2178 tree = create_token_tree (dfa, NULL, NULL, token);
2179 if (BE (tree == NULL, 0))
2184 #ifdef RE_ENABLE_I18N
2185 if (dfa->mb_cur_max > 1)
2187 while (!re_string_eoi (regexp)
2188 && !re_string_first_byte (regexp, re_string_cur_idx (regexp)))
2190 bin_tree_t *mbc_remain;
2191 fetch_token (token, regexp, syntax);
2192 mbc_remain = create_token_tree (dfa, NULL, NULL, token);
2193 tree = create_tree (dfa, tree, mbc_remain, CONCAT);
2194 if (BE (mbc_remain == NULL || tree == NULL, 0))
2203 case OP_OPEN_SUBEXP:
2204 tree = parse_sub_exp (regexp, preg, token, syntax, nest + 1, err);
2205 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2208 case OP_OPEN_BRACKET:
2209 tree = parse_bracket_exp (regexp, dfa, token, syntax, err);
2210 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2214 if (!BE (dfa->completed_bkref_map & (1 << token->opr.idx), 1))
2219 dfa->used_bkref_map |= 1 << token->opr.idx;
2220 tree = create_token_tree (dfa, NULL, NULL, token);
2221 if (BE (tree == NULL, 0))
2227 dfa->has_mb_node = 1;
2229 case OP_OPEN_DUP_NUM:
2230 if (syntax & REG_CONTEXT_INVALID_DUP)
2236 case OP_DUP_ASTERISK:
2238 case OP_DUP_QUESTION:
2239 if (syntax & REG_CONTEXT_INVALID_OPS)
2244 else if (syntax & REG_CONTEXT_INDEP_OPS)
2246 fetch_token (token, regexp, syntax);
2247 return parse_expression (regexp, preg, token, syntax, nest, err);
2249 /* else fall through */
2250 case OP_CLOSE_SUBEXP:
2251 if ((token->type == OP_CLOSE_SUBEXP) &&
2252 !(syntax & REG_UNMATCHED_RIGHT_PAREN_ORD))
2257 /* else fall through */
2258 case OP_CLOSE_DUP_NUM:
2259 /* We treat it as a normal character. */
2261 /* Then we can these characters as normal characters. */
2262 token->type = CHARACTER;
2263 /* mb_partial and word_char bits should be initialized already
2265 tree = create_token_tree (dfa, NULL, NULL, token);
2266 if (BE (tree == NULL, 0))
2273 if ((token->opr.ctx_type
2274 & (WORD_DELIM | NOT_WORD_DELIM | WORD_FIRST | WORD_LAST))
2275 && dfa->word_ops_used == 0)
2276 init_word_char (dfa);
2277 if (token->opr.ctx_type == WORD_DELIM
2278 || token->opr.ctx_type == NOT_WORD_DELIM)
2280 bin_tree_t *tree_first, *tree_last;
2281 if (token->opr.ctx_type == WORD_DELIM)
2283 token->opr.ctx_type = WORD_FIRST;
2284 tree_first = create_token_tree (dfa, NULL, NULL, token);
2285 token->opr.ctx_type = WORD_LAST;
2289 token->opr.ctx_type = INSIDE_WORD;
2290 tree_first = create_token_tree (dfa, NULL, NULL, token);
2291 token->opr.ctx_type = INSIDE_NOTWORD;
2293 tree_last = create_token_tree (dfa, NULL, NULL, token);
2294 tree = create_tree (dfa, tree_first, tree_last, OP_ALT);
2295 if (BE (tree_first == NULL || tree_last == NULL || tree == NULL, 0))
2303 tree = create_token_tree (dfa, NULL, NULL, token);
2304 if (BE (tree == NULL, 0))
2310 /* We must return here, since ANCHORs can't be followed
2311 by repetition operators.
2312 eg. RE"^*" is invalid or "<ANCHOR(^)><CHAR(*)>",
2313 it must not be "<ANCHOR(^)><REPEAT(*)>". */
2314 fetch_token (token, regexp, syntax);
2317 tree = create_token_tree (dfa, NULL, NULL, token);
2318 if (BE (tree == NULL, 0))
2323 if (dfa->mb_cur_max > 1)
2324 dfa->has_mb_node = 1;
2328 tree = build_charclass_op (dfa, regexp->trans,
2329 (const unsigned char *) "alnum",
2330 (const unsigned char *) "_",
2331 token->type == OP_NOTWORD, err);
2332 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2337 tree = build_charclass_op (dfa, regexp->trans,
2338 (const unsigned char *) "space",
2339 (const unsigned char *) "",
2340 token->type == OP_NOTSPACE, err);
2341 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2351 /* Must not happen? */
2357 fetch_token (token, regexp, syntax);
2359 while (token->type == OP_DUP_ASTERISK || token->type == OP_DUP_PLUS
2360 || token->type == OP_DUP_QUESTION || token->type == OP_OPEN_DUP_NUM)
2362 tree = parse_dup_op (tree, regexp, dfa, token, syntax, err);
2363 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2365 /* In BRE consecutive duplications are not allowed. */
2366 if ((syntax & REG_CONTEXT_INVALID_DUP)
2367 && (token->type == OP_DUP_ASTERISK
2368 || token->type == OP_OPEN_DUP_NUM))
2378 /* This function build the following tree, from regular expression
2386 parse_sub_exp (re_string_t *regexp, regex_t *preg, re_token_t *token,
2387 reg_syntax_t syntax, Idx nest, reg_errcode_t *err)
2389 re_dfa_t *dfa = (re_dfa_t *) preg->re_buffer;
2392 cur_nsub = preg->re_nsub++;
2394 fetch_token (token, regexp, syntax | REG_CARET_ANCHORS_HERE);
2396 /* The subexpression may be a null string. */
2397 if (token->type == OP_CLOSE_SUBEXP)
2401 tree = parse_reg_exp (regexp, preg, token, syntax, nest, err);
2402 if (BE (*err == REG_NOERROR && token->type != OP_CLOSE_SUBEXP, 0))
2404 if (BE (*err != REG_NOERROR, 0))
2408 if (cur_nsub <= '9' - '1')
2409 dfa->completed_bkref_map |= 1 << cur_nsub;
2411 tree = create_tree (dfa, tree, NULL, SUBEXP);
2412 if (BE (tree == NULL, 0))
2417 tree->token.opr.idx = cur_nsub;
2421 /* This function parse repetition operators like "*", "+", "{1,3}" etc. */
2424 parse_dup_op (bin_tree_t *elem, re_string_t *regexp, re_dfa_t *dfa,
2425 re_token_t *token, reg_syntax_t syntax, reg_errcode_t *err)
2427 bin_tree_t *tree = NULL, *old_tree = NULL;
2428 Idx i, start, end, start_idx = re_string_cur_idx (regexp);
2429 re_token_t start_token = *token;
2431 if (token->type == OP_OPEN_DUP_NUM)
2434 start = fetch_number (regexp, token, syntax);
2435 if (start == REG_MISSING)
2437 if (token->type == CHARACTER && token->opr.c == ',')
2438 start = 0; /* We treat "{,m}" as "{0,m}". */
2441 *err = REG_BADBR; /* <re>{} is invalid. */
2445 if (BE (start != REG_ERROR, 1))
2447 /* We treat "{n}" as "{n,n}". */
2448 end = ((token->type == OP_CLOSE_DUP_NUM) ? start
2449 : ((token->type == CHARACTER && token->opr.c == ',')
2450 ? fetch_number (regexp, token, syntax) : REG_ERROR));
2452 if (BE (start == REG_ERROR || end == REG_ERROR, 0))
2454 /* Invalid sequence. */
2455 if (BE (!(syntax & REG_INVALID_INTERVAL_ORD), 0))
2457 if (token->type == END_OF_RE)
2465 /* If the syntax bit is set, rollback. */
2466 re_string_set_index (regexp, start_idx);
2467 *token = start_token;
2468 token->type = CHARACTER;
2469 /* mb_partial and word_char bits should be already initialized by
2474 if (BE (end != REG_MISSING && start > end, 0))
2476 /* First number greater than second. */
2483 start = (token->type == OP_DUP_PLUS) ? 1 : 0;
2484 end = (token->type == OP_DUP_QUESTION) ? 1 : REG_MISSING;
2487 fetch_token (token, regexp, syntax);
2489 if (BE (elem == NULL, 0))
2491 if (BE (start == 0 && end == 0, 0))
2493 postorder (elem, free_tree, NULL);
2497 /* Extract "<re>{n,m}" to "<re><re>...<re><re>{0,<m-n>}". */
2498 if (BE (start > 0, 0))
2501 for (i = 2; i <= start; ++i)
2503 elem = duplicate_tree (elem, dfa);
2504 tree = create_tree (dfa, tree, elem, CONCAT);
2505 if (BE (elem == NULL || tree == NULL, 0))
2506 goto parse_dup_op_espace;
2512 /* Duplicate ELEM before it is marked optional. */
2513 elem = duplicate_tree (elem, dfa);
2519 if (elem->token.type == SUBEXP)
2520 postorder (elem, mark_opt_subexp, (void *) (long) elem->token.opr.idx);
2522 tree = create_tree (dfa, elem, NULL,
2523 (end == REG_MISSING ? OP_DUP_ASTERISK : OP_ALT));
2524 if (BE (tree == NULL, 0))
2525 goto parse_dup_op_espace;
2527 /* This loop is actually executed only when end != REG_MISSING,
2528 to rewrite <re>{0,n} as (<re>(<re>...<re>?)?)?... We have
2529 already created the start+1-th copy. */
2530 if ((Idx) -1 < 0 || end != REG_MISSING)
2531 for (i = start + 2; i <= end; ++i)
2533 elem = duplicate_tree (elem, dfa);
2534 tree = create_tree (dfa, tree, elem, CONCAT);
2535 if (BE (elem == NULL || tree == NULL, 0))
2536 goto parse_dup_op_espace;
2538 tree = create_tree (dfa, tree, NULL, OP_ALT);
2539 if (BE (tree == NULL, 0))
2540 goto parse_dup_op_espace;
2544 tree = create_tree (dfa, old_tree, tree, CONCAT);
2548 parse_dup_op_espace:
2553 /* Size of the names for collating symbol/equivalence_class/character_class.
2554 I'm not sure, but maybe enough. */
2555 #define BRACKET_NAME_BUF_SIZE 32
2558 /* Local function for parse_bracket_exp only used in case of NOT _LIBC.
2559 Build the range expression which starts from START_ELEM, and ends
2560 at END_ELEM. The result are written to MBCSET and SBCSET.
2561 RANGE_ALLOC is the allocated size of mbcset->range_starts, and
2562 mbcset->range_ends, is a pointer argument sinse we may
2565 static reg_errcode_t
2566 build_range_exp (bitset sbcset,
2567 # ifdef RE_ENABLE_I18N
2568 re_charset_t *mbcset, Idx *range_alloc,
2570 bracket_elem_t *start_elem, bracket_elem_t *end_elem)
2572 unsigned int start_ch, end_ch;
2573 /* Equivalence Classes and Character Classes can't be a range start/end. */
2574 if (BE (start_elem->type == EQUIV_CLASS || start_elem->type == CHAR_CLASS
2575 || end_elem->type == EQUIV_CLASS || end_elem->type == CHAR_CLASS,
2579 /* We can handle no multi character collating elements without libc
2581 if (BE ((start_elem->type == COLL_SYM
2582 && strlen ((char *) start_elem->opr.name) > 1)
2583 || (end_elem->type == COLL_SYM
2584 && strlen ((char *) end_elem->opr.name) > 1), 0))
2585 return REG_ECOLLATE;
2587 # ifdef RE_ENABLE_I18N
2590 wint_t start_wc, end_wc;
2591 wchar_t cmp_buf[6] = {L'\0', L'\0', L'\0', L'\0', L'\0', L'\0'};
2593 start_ch = ((start_elem->type == SB_CHAR) ? start_elem->opr.ch
2594 : ((start_elem->type == COLL_SYM) ? start_elem->opr.name[0]
2596 end_ch = ((end_elem->type == SB_CHAR) ? end_elem->opr.ch
2597 : ((end_elem->type == COLL_SYM) ? end_elem->opr.name[0]
2599 start_wc = ((start_elem->type == SB_CHAR || start_elem->type == COLL_SYM)
2600 ? __btowc (start_ch) : start_elem->opr.wch);
2601 end_wc = ((end_elem->type == SB_CHAR || end_elem->type == COLL_SYM)
2602 ? __btowc (end_ch) : end_elem->opr.wch);
2603 if (start_wc == WEOF || end_wc == WEOF)
2604 return REG_ECOLLATE;
2605 cmp_buf[0] = start_wc;
2606 cmp_buf[4] = end_wc;
2607 if (wcscoll (cmp_buf, cmp_buf + 4) > 0)
2610 /* Got valid collation sequence values, add them as a new entry.
2611 However, for !_LIBC we have no collation elements: if the
2612 character set is single byte, the single byte character set
2613 that we build below suffices. parse_bracket_exp passes
2614 no MBCSET if dfa->mb_cur_max == 1. */
2617 /* Check the space of the arrays. */
2618 if (BE (*range_alloc == mbcset->nranges, 0))
2620 /* There is not enough space, need realloc. */
2621 wchar_t *new_array_start, *new_array_end;
2624 new_nranges = mbcset->nranges;
2625 /* Use realloc since mbcset->range_starts and mbcset->range_ends
2626 are NULL if *range_alloc == 0. */
2627 new_array_start = re_x2realloc (mbcset->range_starts, wchar_t,
2629 new_array_end = re_realloc (mbcset->range_ends, wchar_t,
2632 if (BE (new_array_start == NULL || new_array_end == NULL, 0))
2635 mbcset->range_starts = new_array_start;
2636 mbcset->range_ends = new_array_end;
2637 *range_alloc = new_nranges;
2640 mbcset->range_starts[mbcset->nranges] = start_wc;
2641 mbcset->range_ends[mbcset->nranges++] = end_wc;
2644 /* Build the table for single byte characters. */
2645 for (wc = 0; wc < SBC_MAX; ++wc)
2648 if (wcscoll (cmp_buf, cmp_buf + 2) <= 0
2649 && wcscoll (cmp_buf + 2, cmp_buf + 4) <= 0)
2650 bitset_set (sbcset, wc);
2653 # else /* not RE_ENABLE_I18N */
2656 start_ch = ((start_elem->type == SB_CHAR ) ? start_elem->opr.ch
2657 : ((start_elem->type == COLL_SYM) ? start_elem->opr.name[0]
2659 end_ch = ((end_elem->type == SB_CHAR ) ? end_elem->opr.ch
2660 : ((end_elem->type == COLL_SYM) ? end_elem->opr.name[0]
2662 if (start_ch > end_ch)
2664 /* Build the table for single byte characters. */
2665 for (ch = 0; ch < SBC_MAX; ++ch)
2666 if (start_ch <= ch && ch <= end_ch)
2667 bitset_set (sbcset, ch);
2669 # endif /* not RE_ENABLE_I18N */
2672 #endif /* not _LIBC */
2675 /* Helper function for parse_bracket_exp only used in case of NOT _LIBC..
2676 Build the collating element which is represented by NAME.
2677 The result are written to MBCSET and SBCSET.
2678 COLL_SYM_ALLOC is the allocated size of mbcset->coll_sym, is a
2679 pointer argument since we may update it. */
2681 static reg_errcode_t
2682 build_collating_symbol (bitset sbcset,
2683 # ifdef RE_ENABLE_I18N
2684 re_charset_t *mbcset, Idx *coll_sym_alloc,
2686 const unsigned char *name)
2688 size_t name_len = strlen ((const char *) name);
2689 if (BE (name_len != 1, 0))
2690 return REG_ECOLLATE;
2693 bitset_set (sbcset, name[0]);
2697 #endif /* not _LIBC */
2699 /* This function parse bracket expression like "[abc]", "[a-c]",
2703 parse_bracket_exp (re_string_t *regexp, re_dfa_t *dfa, re_token_t *token,
2704 reg_syntax_t syntax, reg_errcode_t *err)
2707 const unsigned char *collseqmb;
2708 const char *collseqwc;
2711 const int32_t *symb_table;
2712 const unsigned char *extra;
2714 /* Local function for parse_bracket_exp used in _LIBC environement.
2715 Seek the collating symbol entry correspondings to NAME.
2716 Return the index of the symbol in the SYMB_TABLE. */
2719 __attribute ((always_inline))
2720 seek_collating_symbol_entry (const unsigned char *name, size_t name_len)
2722 int32_t hash = elem_hash ((const char *) name, name_len);
2723 int32_t elem = hash % table_size;
2724 int32_t second = hash % (table_size - 2);
2725 while (symb_table[2 * elem] != 0)
2727 /* First compare the hashing value. */
2728 if (symb_table[2 * elem] == hash
2729 /* Compare the length of the name. */
2730 && name_len == extra[symb_table[2 * elem + 1]]
2731 /* Compare the name. */
2732 && memcmp (name, &extra[symb_table[2 * elem + 1] + 1],
2735 /* Yep, this is the entry. */
2745 /* Local function for parse_bracket_exp used in _LIBC environement.
2746 Look up the collation sequence value of BR_ELEM.
2747 Return the value if succeeded, UINT_MAX otherwise. */
2749 auto inline unsigned int
2750 __attribute ((always_inline))
2751 lookup_collation_sequence_value (bracket_elem_t *br_elem)
2753 if (br_elem->type == SB_CHAR)
2756 if (MB_CUR_MAX == 1)
2759 return collseqmb[br_elem->opr.ch];
2762 wint_t wc = __btowc (br_elem->opr.ch);
2763 return __collseq_table_lookup (collseqwc, wc);
2766 else if (br_elem->type == MB_CHAR)
2768 return __collseq_table_lookup (collseqwc, br_elem->opr.wch);
2770 else if (br_elem->type == COLL_SYM)
2772 size_t sym_name_len = strlen ((char *) br_elem->opr.name);
2776 elem = seek_collating_symbol_entry (br_elem->opr.name,
2778 if (symb_table[2 * elem] != 0)
2780 /* We found the entry. */
2781 idx = symb_table[2 * elem + 1];
2782 /* Skip the name of collating element name. */
2783 idx += 1 + extra[idx];
2784 /* Skip the byte sequence of the collating element. */
2785 idx += 1 + extra[idx];
2786 /* Adjust for the alignment. */
2787 idx = (idx + 3) & ~3;
2788 /* Skip the multibyte collation sequence value. */
2789 idx += sizeof (unsigned int);
2790 /* Skip the wide char sequence of the collating element. */
2791 idx += sizeof (unsigned int) *
2792 (1 + *(unsigned int *) (extra + idx));
2793 /* Return the collation sequence value. */
2794 return *(unsigned int *) (extra + idx);
2796 else if (symb_table[2 * elem] == 0 && sym_name_len == 1)
2798 /* No valid character. Match it as a single byte
2800 return collseqmb[br_elem->opr.name[0]];
2803 else if (sym_name_len == 1)
2804 return collseqmb[br_elem->opr.name[0]];
2809 /* Local function for parse_bracket_exp used in _LIBC environement.
2810 Build the range expression which starts from START_ELEM, and ends
2811 at END_ELEM. The result are written to MBCSET and SBCSET.
2812 RANGE_ALLOC is the allocated size of mbcset->range_starts, and
2813 mbcset->range_ends, is a pointer argument sinse we may
2816 auto inline reg_errcode_t
2817 __attribute ((always_inline))
2818 build_range_exp (bitset sbcset, re_charset_t *mbcset,
2820 bracket_elem_t *start_elem, bracket_elem_t *end_elem)
2823 uint32_t start_collseq;
2824 uint32_t end_collseq;
2826 /* Equivalence Classes and Character Classes can't be a range
2828 if (BE (start_elem->type == EQUIV_CLASS || start_elem->type == CHAR_CLASS
2829 || end_elem->type == EQUIV_CLASS || end_elem->type == CHAR_CLASS,
2833 start_collseq = lookup_collation_sequence_value (start_elem);
2834 end_collseq = lookup_collation_sequence_value (end_elem);
2835 /* Check start/end collation sequence values. */
2836 if (BE (start_collseq == UINT_MAX || end_collseq == UINT_MAX, 0))
2837 return REG_ECOLLATE;
2838 if (BE ((syntax & REG_NO_EMPTY_RANGES) && start_collseq > end_collseq, 0))
2841 /* Got valid collation sequence values, add them as a new entry.
2842 However, if we have no collation elements, and the character set
2843 is single byte, the single byte character set that we
2844 build below suffices. */
2845 if (nrules > 0 || dfa->mb_cur_max > 1)
2847 /* Check the space of the arrays. */
2848 if (BE (*range_alloc == mbcset->nranges, 0))
2850 /* There is not enough space, need realloc. */
2851 uint32_t *new_array_start;
2852 uint32_t *new_array_end;
2855 new_nranges = mbcset->nranges;
2856 new_array_start = re_x2realloc (mbcset->range_starts, uint32_t,
2858 new_array_end = re_realloc (mbcset->range_ends, uint32_t,
2861 if (BE (new_array_start == NULL || new_array_end == NULL, 0))
2864 mbcset->range_starts = new_array_start;
2865 mbcset->range_ends = new_array_end;
2866 *range_alloc = new_nranges;
2869 mbcset->range_starts[mbcset->nranges] = start_collseq;
2870 mbcset->range_ends[mbcset->nranges++] = end_collseq;
2873 /* Build the table for single byte characters. */
2874 for (ch = 0; ch < SBC_MAX; ch++)
2876 uint32_t ch_collseq;
2878 if (MB_CUR_MAX == 1)
2881 ch_collseq = collseqmb[ch];
2883 ch_collseq = __collseq_table_lookup (collseqwc, __btowc (ch));
2884 if (start_collseq <= ch_collseq && ch_collseq <= end_collseq)
2885 bitset_set (sbcset, ch);
2890 /* Local function for parse_bracket_exp used in _LIBC environement.
2891 Build the collating element which is represented by NAME.
2892 The result are written to MBCSET and SBCSET.
2893 COLL_SYM_ALLOC is the allocated size of mbcset->coll_sym, is a
2894 pointer argument sinse we may update it. */
2896 auto inline reg_errcode_t
2897 __attribute ((always_inline))
2898 build_collating_symbol (bitset sbcset, re_charset_t *mbcset,
2899 Idx *coll_sym_alloc, const unsigned char *name)
2902 size_t name_len = strlen ((const char *) name);
2905 elem = seek_collating_symbol_entry (name, name_len);
2906 if (symb_table[2 * elem] != 0)
2908 /* We found the entry. */
2909 idx = symb_table[2 * elem + 1];
2910 /* Skip the name of collating element name. */
2911 idx += 1 + extra[idx];
2913 else if (symb_table[2 * elem] == 0 && name_len == 1)
2915 /* No valid character, treat it as a normal
2917 bitset_set (sbcset, name[0]);
2921 return REG_ECOLLATE;
2923 /* Got valid collation sequence, add it as a new entry. */
2924 /* Check the space of the arrays. */
2925 if (BE (*coll_sym_alloc == mbcset->ncoll_syms, 0))
2927 /* Not enough, realloc it. */
2928 Idx new_coll_sym_alloc = mbcset->ncoll_syms;
2929 /* Use realloc since mbcset->coll_syms is NULL
2931 int32_t *new_coll_syms = re_x2realloc (mbcset->coll_syms, int32_t,
2932 &new_coll_sym_alloc);
2933 if (BE (new_coll_syms == NULL, 0))
2935 mbcset->coll_syms = new_coll_syms;
2936 *coll_sym_alloc = new_coll_sym_alloc;
2938 mbcset->coll_syms[mbcset->ncoll_syms++] = idx;
2943 if (BE (name_len != 1, 0))
2944 return REG_ECOLLATE;
2947 bitset_set (sbcset, name[0]);
2954 re_token_t br_token;
2955 re_bitset_ptr_t sbcset;
2956 #ifdef RE_ENABLE_I18N
2957 re_charset_t *mbcset;
2958 Idx coll_sym_alloc = 0, range_alloc = 0, mbchar_alloc = 0;
2959 Idx equiv_class_alloc = 0, char_class_alloc = 0;
2960 #endif /* not RE_ENABLE_I18N */
2961 bool non_match = false;
2962 bin_tree_t *work_tree;
2964 bool first_round = true;
2966 collseqmb = (const unsigned char *)
2967 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQMB);
2968 nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
2974 collseqwc = _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQWC);
2975 table_size = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_SYMB_HASH_SIZEMB);
2976 symb_table = (const int32_t *) _NL_CURRENT (LC_COLLATE,
2977 _NL_COLLATE_SYMB_TABLEMB);
2978 extra = (const unsigned char *) _NL_CURRENT (LC_COLLATE,
2979 _NL_COLLATE_SYMB_EXTRAMB);
2982 sbcset = re_calloc (bitset_word, BITSET_WORDS);
2983 #ifdef RE_ENABLE_I18N
2984 mbcset = re_calloc (re_charset_t, 1);
2985 #endif /* RE_ENABLE_I18N */
2986 #ifdef RE_ENABLE_I18N
2987 if (BE (sbcset == NULL || mbcset == NULL, 0))
2989 if (BE (sbcset == NULL, 0))
2990 #endif /* RE_ENABLE_I18N */
2996 token_len = peek_token_bracket (token, regexp, syntax);
2997 if (BE (token->type == END_OF_RE, 0))
3000 goto parse_bracket_exp_free_return;
3002 if (token->type == OP_NON_MATCH_LIST)
3004 #ifdef RE_ENABLE_I18N
3005 mbcset->non_match = 1;
3006 #endif /* not RE_ENABLE_I18N */
3008 if (syntax & REG_HAT_LISTS_NOT_NEWLINE)
3009 bitset_set (sbcset, '\0');
3010 re_string_skip_bytes (regexp, token_len); /* Skip a token. */
3011 token_len = peek_token_bracket (token, regexp, syntax);
3012 if (BE (token->type == END_OF_RE, 0))
3015 goto parse_bracket_exp_free_return;
3019 /* We treat the first ']' as a normal character. */
3020 if (token->type == OP_CLOSE_BRACKET)
3021 token->type = CHARACTER;
3025 bracket_elem_t start_elem, end_elem;
3026 unsigned char start_name_buf[BRACKET_NAME_BUF_SIZE];
3027 unsigned char end_name_buf[BRACKET_NAME_BUF_SIZE];
3030 bool is_range_exp = false;
3033 start_elem.opr.name = start_name_buf;
3034 ret = parse_bracket_element (&start_elem, regexp, token, token_len, dfa,
3035 syntax, first_round);
3036 if (BE (ret != REG_NOERROR, 0))
3039 goto parse_bracket_exp_free_return;
3041 first_round = false;
3043 /* Get information about the next token. We need it in any case. */
3044 token_len = peek_token_bracket (token, regexp, syntax);
3046 /* Do not check for ranges if we know they are not allowed. */
3047 if (start_elem.type != CHAR_CLASS && start_elem.type != EQUIV_CLASS)
3049 if (BE (token->type == END_OF_RE, 0))
3052 goto parse_bracket_exp_free_return;
3054 if (token->type == OP_CHARSET_RANGE)
3056 re_string_skip_bytes (regexp, token_len); /* Skip '-'. */
3057 token_len2 = peek_token_bracket (&token2, regexp, syntax);
3058 if (BE (token2.type == END_OF_RE, 0))
3061 goto parse_bracket_exp_free_return;
3063 if (token2.type == OP_CLOSE_BRACKET)
3065 /* We treat the last '-' as a normal character. */
3066 re_string_skip_bytes (regexp, -token_len);
3067 token->type = CHARACTER;
3070 is_range_exp = true;
3074 if (is_range_exp == true)
3076 end_elem.opr.name = end_name_buf;
3077 ret = parse_bracket_element (&end_elem, regexp, &token2, token_len2,
3079 if (BE (ret != REG_NOERROR, 0))
3082 goto parse_bracket_exp_free_return;
3085 token_len = peek_token_bracket (token, regexp, syntax);
3088 *err = build_range_exp (sbcset, mbcset, &range_alloc,
3089 &start_elem, &end_elem);
3091 # ifdef RE_ENABLE_I18N
3092 *err = build_range_exp (sbcset,
3093 dfa->mb_cur_max > 1 ? mbcset : NULL,
3094 &range_alloc, &start_elem, &end_elem);
3096 *err = build_range_exp (sbcset, &start_elem, &end_elem);
3098 #endif /* RE_ENABLE_I18N */
3099 if (BE (*err != REG_NOERROR, 0))
3100 goto parse_bracket_exp_free_return;
3104 switch (start_elem.type)
3107 bitset_set (sbcset, start_elem.opr.ch);
3109 #ifdef RE_ENABLE_I18N
3111 /* Check whether the array has enough space. */
3112 if (BE (mbchar_alloc == mbcset->nmbchars, 0))
3114 wchar_t *new_mbchars;
3115 /* Not enough, realloc it. */
3116 mbchar_alloc = mbcset->nmbchars;
3117 /* Use realloc since array is NULL if *alloc == 0. */
3118 new_mbchars = re_x2realloc (mbcset->mbchars, wchar_t,
3120 if (BE (new_mbchars == NULL, 0))
3121 goto parse_bracket_exp_espace;
3122 mbcset->mbchars = new_mbchars;
3124 mbcset->mbchars[mbcset->nmbchars++] = start_elem.opr.wch;
3126 #endif /* RE_ENABLE_I18N */
3128 *err = build_equiv_class (sbcset,
3129 #ifdef RE_ENABLE_I18N
3130 mbcset, &equiv_class_alloc,
3131 #endif /* RE_ENABLE_I18N */
3132 start_elem.opr.name);
3133 if (BE (*err != REG_NOERROR, 0))
3134 goto parse_bracket_exp_free_return;
3137 *err = build_collating_symbol (sbcset,
3138 #ifdef RE_ENABLE_I18N
3139 mbcset, &coll_sym_alloc,
3140 #endif /* RE_ENABLE_I18N */
3141 start_elem.opr.name);
3142 if (BE (*err != REG_NOERROR, 0))
3143 goto parse_bracket_exp_free_return;
3146 *err = build_charclass (regexp->trans, sbcset,
3147 #ifdef RE_ENABLE_I18N
3148 mbcset, &char_class_alloc,
3149 #endif /* RE_ENABLE_I18N */
3150 start_elem.opr.name, syntax);
3151 if (BE (*err != REG_NOERROR, 0))
3152 goto parse_bracket_exp_free_return;
3159 if (BE (token->type == END_OF_RE, 0))
3162 goto parse_bracket_exp_free_return;
3164 if (token->type == OP_CLOSE_BRACKET)
3168 re_string_skip_bytes (regexp, token_len); /* Skip a token. */
3170 /* If it is non-matching list. */
3172 bitset_not (sbcset);
3174 #ifdef RE_ENABLE_I18N
3175 /* Ensure only single byte characters are set. */
3176 if (dfa->mb_cur_max > 1)
3177 bitset_mask (sbcset, dfa->sb_char);
3179 if (mbcset->nmbchars || mbcset->ncoll_syms || mbcset->nequiv_classes
3180 || mbcset->nranges || (dfa->mb_cur_max > 1 && (mbcset->nchar_classes
3181 || mbcset->non_match)))
3183 bin_tree_t *mbc_tree;
3185 /* Build a tree for complex bracket. */
3186 dfa->has_mb_node = 1;
3187 br_token.type = COMPLEX_BRACKET;
3188 br_token.opr.mbcset = mbcset;
3189 mbc_tree = create_token_tree (dfa, NULL, NULL, &br_token);
3190 if (BE (mbc_tree == NULL, 0))
3191 goto parse_bracket_exp_espace;
3192 for (sbc_idx = 0; sbc_idx < BITSET_WORDS; ++sbc_idx)
3193 if (sbcset[sbc_idx])
3195 /* If there are no bits set in sbcset, there is no point
3196 of having both SIMPLE_BRACKET and COMPLEX_BRACKET. */
3197 if (sbc_idx < BITSET_WORDS)
3199 /* Build a tree for simple bracket. */
3200 br_token.type = SIMPLE_BRACKET;
3201 br_token.opr.sbcset = sbcset;
3202 work_tree = create_token_tree (dfa, NULL, NULL, &br_token);
3203 if (BE (work_tree == NULL, 0))
3204 goto parse_bracket_exp_espace;
3206 /* Then join them by ALT node. */
3207 work_tree = create_tree (dfa, work_tree, mbc_tree, OP_ALT);
3208 if (BE (work_tree == NULL, 0))
3209 goto parse_bracket_exp_espace;
3214 work_tree = mbc_tree;
3218 #endif /* not RE_ENABLE_I18N */
3220 #ifdef RE_ENABLE_I18N
3221 free_charset (mbcset);
3223 /* Build a tree for simple bracket. */
3224 br_token.type = SIMPLE_BRACKET;
3225 br_token.opr.sbcset = sbcset;
3226 work_tree = create_token_tree (dfa, NULL, NULL, &br_token);
3227 if (BE (work_tree == NULL, 0))
3228 goto parse_bracket_exp_espace;
3232 parse_bracket_exp_espace:
3234 parse_bracket_exp_free_return:
3236 #ifdef RE_ENABLE_I18N
3237 free_charset (mbcset);
3238 #endif /* RE_ENABLE_I18N */
3242 /* Parse an element in the bracket expression. */
3244 static reg_errcode_t
3245 parse_bracket_element (bracket_elem_t *elem, re_string_t *regexp,
3246 re_token_t *token, int token_len, re_dfa_t *dfa,
3247 reg_syntax_t syntax, bool accept_hyphen)
3249 #ifdef RE_ENABLE_I18N
3251 cur_char_size = re_string_char_size_at (regexp, re_string_cur_idx (regexp));
3252 if (cur_char_size > 1)
3254 elem->type = MB_CHAR;
3255 elem->opr.wch = re_string_wchar_at (regexp, re_string_cur_idx (regexp));
3256 re_string_skip_bytes (regexp, cur_char_size);
3259 #endif /* RE_ENABLE_I18N */
3260 re_string_skip_bytes (regexp, token_len); /* Skip a token. */
3261 if (token->type == OP_OPEN_COLL_ELEM || token->type == OP_OPEN_CHAR_CLASS
3262 || token->type == OP_OPEN_EQUIV_CLASS)
3263 return parse_bracket_symbol (elem, regexp, token);
3264 if (BE (token->type == OP_CHARSET_RANGE, 0) && !accept_hyphen)
3266 /* A '-' must only appear as anything but a range indicator before
3267 the closing bracket. Everything else is an error. */
3269 (void) peek_token_bracket (&token2, regexp, syntax);
3270 if (token2.type != OP_CLOSE_BRACKET)
3271 /* The actual error value is not standardized since this whole
3272 case is undefined. But ERANGE makes good sense. */
3275 elem->type = SB_CHAR;
3276 elem->opr.ch = token->opr.c;
3280 /* Parse a bracket symbol in the bracket expression. Bracket symbols are
3281 such as [:<character_class>:], [.<collating_element>.], and
3282 [=<equivalent_class>=]. */
3284 static reg_errcode_t
3285 parse_bracket_symbol (bracket_elem_t *elem, re_string_t *regexp,
3288 unsigned char ch, delim = token->opr.c;
3290 if (re_string_eoi(regexp))
3294 if (i >= BRACKET_NAME_BUF_SIZE)
3296 if (token->type == OP_OPEN_CHAR_CLASS)
3297 ch = re_string_fetch_byte_case (regexp);
3299 ch = re_string_fetch_byte (regexp);
3300 if (re_string_eoi(regexp))
3302 if (ch == delim && re_string_peek_byte (regexp, 0) == ']')
3304 elem->opr.name[i] = ch;