1 /* -*- buffer-read-only: t -*- vi: set ro: */
2 /* DO NOT EDIT! GENERATED AUTOMATICALLY! */
3 /* Extended regular expression matching and search library.
4 Copyright (C) 2002,2003,2004,2005,2006,2007,2008,2009
5 Free Software Foundation, Inc.
6 This file is part of the GNU C Library.
7 Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>.
9 This program is free software; you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation; either version 3, or (at your option)
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
19 You should have received a copy of the GNU General Public License along
20 with this program; if not, write to the Free Software Foundation,
21 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
23 static reg_errcode_t re_compile_internal (regex_t *preg, const char * pattern,
24 size_t length, reg_syntax_t syntax);
25 static void re_compile_fastmap_iter (regex_t *bufp,
26 const re_dfastate_t *init_state,
28 static reg_errcode_t init_dfa (re_dfa_t *dfa, size_t pat_len);
30 static void free_charset (re_charset_t *cset);
31 #endif /* RE_ENABLE_I18N */
32 static void free_workarea_compile (regex_t *preg);
33 static reg_errcode_t create_initial_state (re_dfa_t *dfa);
35 static void optimize_utf8 (re_dfa_t *dfa);
37 static reg_errcode_t analyze (regex_t *preg);
38 static reg_errcode_t preorder (bin_tree_t *root,
39 reg_errcode_t (fn (void *, bin_tree_t *)),
41 static reg_errcode_t postorder (bin_tree_t *root,
42 reg_errcode_t (fn (void *, bin_tree_t *)),
44 static reg_errcode_t optimize_subexps (void *extra, bin_tree_t *node);
45 static reg_errcode_t lower_subexps (void *extra, bin_tree_t *node);
46 static bin_tree_t *lower_subexp (reg_errcode_t *err, regex_t *preg,
48 static reg_errcode_t calc_first (void *extra, bin_tree_t *node);
49 static reg_errcode_t calc_next (void *extra, bin_tree_t *node);
50 static reg_errcode_t link_nfa_nodes (void *extra, bin_tree_t *node);
51 static Idx duplicate_node (re_dfa_t *dfa, Idx org_idx, unsigned int constraint);
52 static Idx search_duplicated_node (const re_dfa_t *dfa, Idx org_node,
53 unsigned int constraint);
54 static reg_errcode_t calc_eclosure (re_dfa_t *dfa);
55 static reg_errcode_t calc_eclosure_iter (re_node_set *new_set, re_dfa_t *dfa,
57 static reg_errcode_t calc_inveclosure (re_dfa_t *dfa);
58 static Idx fetch_number (re_string_t *input, re_token_t *token,
60 static int peek_token (re_token_t *token, re_string_t *input,
61 reg_syntax_t syntax) internal_function;
62 static bin_tree_t *parse (re_string_t *regexp, regex_t *preg,
63 reg_syntax_t syntax, reg_errcode_t *err);
64 static bin_tree_t *parse_reg_exp (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_branch (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_expression (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_sub_exp (re_string_t *regexp, regex_t *preg,
74 re_token_t *token, reg_syntax_t syntax,
75 Idx nest, reg_errcode_t *err);
76 static bin_tree_t *parse_dup_op (bin_tree_t *dup_elem, re_string_t *regexp,
77 re_dfa_t *dfa, re_token_t *token,
78 reg_syntax_t syntax, reg_errcode_t *err);
79 static bin_tree_t *parse_bracket_exp (re_string_t *regexp, re_dfa_t *dfa,
80 re_token_t *token, reg_syntax_t syntax,
82 static reg_errcode_t parse_bracket_element (bracket_elem_t *elem,
84 re_token_t *token, int token_len,
88 static reg_errcode_t parse_bracket_symbol (bracket_elem_t *elem,
92 static reg_errcode_t build_equiv_class (bitset_t sbcset,
94 Idx *equiv_class_alloc,
95 const unsigned char *name);
96 static reg_errcode_t build_charclass (RE_TRANSLATE_TYPE trans,
99 Idx *char_class_alloc,
100 const unsigned char *class_name,
101 reg_syntax_t syntax);
102 #else /* not RE_ENABLE_I18N */
103 static reg_errcode_t build_equiv_class (bitset_t sbcset,
104 const unsigned char *name);
105 static reg_errcode_t build_charclass (RE_TRANSLATE_TYPE trans,
107 const unsigned char *class_name,
108 reg_syntax_t syntax);
109 #endif /* not RE_ENABLE_I18N */
110 static bin_tree_t *build_charclass_op (re_dfa_t *dfa,
111 RE_TRANSLATE_TYPE trans,
112 const unsigned char *class_name,
113 const unsigned char *extra,
114 bool non_match, reg_errcode_t *err);
115 static bin_tree_t *create_tree (re_dfa_t *dfa,
116 bin_tree_t *left, bin_tree_t *right,
117 re_token_type_t type);
118 static bin_tree_t *create_token_tree (re_dfa_t *dfa,
119 bin_tree_t *left, bin_tree_t *right,
120 const re_token_t *token);
121 static bin_tree_t *duplicate_tree (const bin_tree_t *src, re_dfa_t *dfa);
122 static void free_token (re_token_t *node);
123 static reg_errcode_t free_tree (void *extra, bin_tree_t *node);
124 static reg_errcode_t mark_opt_subexp (void *extra, bin_tree_t *node);
126 /* This table gives an error message for each of the error codes listed
127 in regex.h. Obviously the order here has to be same as there.
128 POSIX doesn't require that we do anything for REG_NOERROR,
129 but why not be nice? */
131 static const char __re_error_msgid[] =
133 #define REG_NOERROR_IDX 0
134 gettext_noop ("Success") /* REG_NOERROR */
136 #define REG_NOMATCH_IDX (REG_NOERROR_IDX + sizeof "Success")
137 gettext_noop ("No match") /* REG_NOMATCH */
139 #define REG_BADPAT_IDX (REG_NOMATCH_IDX + sizeof "No match")
140 gettext_noop ("Invalid regular expression") /* REG_BADPAT */
142 #define REG_ECOLLATE_IDX (REG_BADPAT_IDX + sizeof "Invalid regular expression")
143 gettext_noop ("Invalid collation character") /* REG_ECOLLATE */
145 #define REG_ECTYPE_IDX (REG_ECOLLATE_IDX + sizeof "Invalid collation character")
146 gettext_noop ("Invalid character class name") /* REG_ECTYPE */
148 #define REG_EESCAPE_IDX (REG_ECTYPE_IDX + sizeof "Invalid character class name")
149 gettext_noop ("Trailing backslash") /* REG_EESCAPE */
151 #define REG_ESUBREG_IDX (REG_EESCAPE_IDX + sizeof "Trailing backslash")
152 gettext_noop ("Invalid back reference") /* REG_ESUBREG */
154 #define REG_EBRACK_IDX (REG_ESUBREG_IDX + sizeof "Invalid back reference")
155 gettext_noop ("Unmatched [ or [^") /* REG_EBRACK */
157 #define REG_EPAREN_IDX (REG_EBRACK_IDX + sizeof "Unmatched [ or [^")
158 gettext_noop ("Unmatched ( or \\(") /* REG_EPAREN */
160 #define REG_EBRACE_IDX (REG_EPAREN_IDX + sizeof "Unmatched ( or \\(")
161 gettext_noop ("Unmatched \\{") /* REG_EBRACE */
163 #define REG_BADBR_IDX (REG_EBRACE_IDX + sizeof "Unmatched \\{")
164 gettext_noop ("Invalid content of \\{\\}") /* REG_BADBR */
166 #define REG_ERANGE_IDX (REG_BADBR_IDX + sizeof "Invalid content of \\{\\}")
167 gettext_noop ("Invalid range end") /* REG_ERANGE */
169 #define REG_ESPACE_IDX (REG_ERANGE_IDX + sizeof "Invalid range end")
170 gettext_noop ("Memory exhausted") /* REG_ESPACE */
172 #define REG_BADRPT_IDX (REG_ESPACE_IDX + sizeof "Memory exhausted")
173 gettext_noop ("Invalid preceding regular expression") /* REG_BADRPT */
175 #define REG_EEND_IDX (REG_BADRPT_IDX + sizeof "Invalid preceding regular expression")
176 gettext_noop ("Premature end of regular expression") /* REG_EEND */
178 #define REG_ESIZE_IDX (REG_EEND_IDX + sizeof "Premature end of regular expression")
179 gettext_noop ("Regular expression too big") /* REG_ESIZE */
181 #define REG_ERPAREN_IDX (REG_ESIZE_IDX + sizeof "Regular expression too big")
182 gettext_noop ("Unmatched ) or \\)") /* REG_ERPAREN */
185 static const size_t __re_error_msgid_idx[] =
206 /* Entry points for GNU code. */
208 /* re_compile_pattern is the GNU regular expression compiler: it
209 compiles PATTERN (of length LENGTH) and puts the result in BUFP.
210 Returns 0 if the pattern was valid, otherwise an error string.
212 Assumes the `allocated' (and perhaps `buffer') and `translate' fields
213 are set in BUFP on entry. */
217 re_compile_pattern (pattern, length, bufp)
220 struct re_pattern_buffer *bufp;
221 #else /* size_t might promote */
223 re_compile_pattern (const char *pattern, size_t length,
224 struct re_pattern_buffer *bufp)
229 /* And GNU code determines whether or not to get register information
230 by passing null for the REGS argument to re_match, etc., not by
231 setting no_sub, unless RE_NO_SUB is set. */
232 bufp->no_sub = !!(re_syntax_options & RE_NO_SUB);
234 /* Match anchors at newline. */
235 bufp->newline_anchor = 1;
237 ret = re_compile_internal (bufp, pattern, length, re_syntax_options);
241 return gettext (__re_error_msgid + __re_error_msgid_idx[(int) ret]);
244 weak_alias (__re_compile_pattern, re_compile_pattern)
247 /* Set by `re_set_syntax' to the current regexp syntax to recognize. Can
248 also be assigned to arbitrarily: each pattern buffer stores its own
249 syntax, so it can be changed between regex compilations. */
250 /* This has no initializer because initialized variables in Emacs
251 become read-only after dumping. */
252 reg_syntax_t re_syntax_options;
255 /* Specify the precise syntax of regexps for compilation. This provides
256 for compatibility for various utilities which historically have
257 different, incompatible syntaxes.
259 The argument SYNTAX is a bit mask comprised of the various bits
260 defined in regex.h. We return the old syntax. */
263 re_set_syntax (syntax)
266 reg_syntax_t ret = re_syntax_options;
268 re_syntax_options = syntax;
272 weak_alias (__re_set_syntax, re_set_syntax)
276 re_compile_fastmap (bufp)
277 struct re_pattern_buffer *bufp;
279 re_dfa_t *dfa = (re_dfa_t *) bufp->buffer;
280 char *fastmap = bufp->fastmap;
282 memset (fastmap, '\0', sizeof (char) * SBC_MAX);
283 re_compile_fastmap_iter (bufp, dfa->init_state, fastmap);
284 if (dfa->init_state != dfa->init_state_word)
285 re_compile_fastmap_iter (bufp, dfa->init_state_word, fastmap);
286 if (dfa->init_state != dfa->init_state_nl)
287 re_compile_fastmap_iter (bufp, dfa->init_state_nl, fastmap);
288 if (dfa->init_state != dfa->init_state_begbuf)
289 re_compile_fastmap_iter (bufp, dfa->init_state_begbuf, fastmap);
290 bufp->fastmap_accurate = 1;
294 weak_alias (__re_compile_fastmap, re_compile_fastmap)
298 __attribute ((always_inline))
299 re_set_fastmap (char *fastmap, bool icase, int ch)
303 fastmap[tolower (ch)] = 1;
306 /* Helper function for re_compile_fastmap.
307 Compile fastmap for the initial_state INIT_STATE. */
310 re_compile_fastmap_iter (regex_t *bufp, const re_dfastate_t *init_state,
313 re_dfa_t *dfa = (re_dfa_t *) bufp->buffer;
315 bool icase = (dfa->mb_cur_max == 1 && (bufp->syntax & RE_ICASE));
316 for (node_cnt = 0; node_cnt < init_state->nodes.nelem; ++node_cnt)
318 Idx node = init_state->nodes.elems[node_cnt];
319 re_token_type_t type = dfa->nodes[node].type;
321 if (type == CHARACTER)
323 re_set_fastmap (fastmap, icase, dfa->nodes[node].opr.c);
324 #ifdef RE_ENABLE_I18N
325 if ((bufp->syntax & RE_ICASE) && dfa->mb_cur_max > 1)
327 unsigned char buf[MB_LEN_MAX];
333 *p++ = dfa->nodes[node].opr.c;
334 while (++node < dfa->nodes_len
335 && dfa->nodes[node].type == CHARACTER
336 && dfa->nodes[node].mb_partial)
337 *p++ = dfa->nodes[node].opr.c;
338 memset (&state, '\0', sizeof (state));
339 if (__mbrtowc (&wc, (const char *) buf, p - buf,
341 && (__wcrtomb ((char *) buf, towlower (wc), &state)
343 re_set_fastmap (fastmap, false, buf[0]);
347 else if (type == SIMPLE_BRACKET)
350 for (i = 0, ch = 0; i < BITSET_WORDS; ++i)
353 bitset_word_t w = dfa->nodes[node].opr.sbcset[i];
354 for (j = 0; j < BITSET_WORD_BITS; ++j, ++ch)
355 if (w & ((bitset_word_t) 1 << j))
356 re_set_fastmap (fastmap, icase, ch);
359 #ifdef RE_ENABLE_I18N
360 else if (type == COMPLEX_BRACKET)
362 re_charset_t *cset = dfa->nodes[node].opr.mbcset;
366 /* See if we have to try all bytes which start multiple collation
368 e.g. In da_DK, we want to catch 'a' since "aa" is a valid
369 collation element, and don't catch 'b' since 'b' is
370 the only collation element which starts from 'b' (and
371 it is caught by SIMPLE_BRACKET). */
372 if (_NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES) != 0
373 && (cset->ncoll_syms || cset->nranges))
375 const int32_t *table = (const int32_t *)
376 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
377 for (i = 0; i < SBC_MAX; ++i)
379 re_set_fastmap (fastmap, icase, i);
383 /* See if we have to start the match at all multibyte characters,
384 i.e. where we would not find an invalid sequence. This only
385 applies to multibyte character sets; for single byte character
386 sets, the SIMPLE_BRACKET again suffices. */
387 if (dfa->mb_cur_max > 1
388 && (cset->nchar_classes || cset->non_match
390 || cset->nequiv_classes
398 memset (&mbs, 0, sizeof (mbs));
399 if (__mbrtowc (NULL, (char *) &c, 1, &mbs) == (size_t) -2)
400 re_set_fastmap (fastmap, false, (int) c);
407 /* ... Else catch all bytes which can start the mbchars. */
408 for (i = 0; i < cset->nmbchars; ++i)
412 memset (&state, '\0', sizeof (state));
413 if (__wcrtomb (buf, cset->mbchars[i], &state) != (size_t) -1)
414 re_set_fastmap (fastmap, icase, *(unsigned char *) buf);
415 if ((bufp->syntax & RE_ICASE) && dfa->mb_cur_max > 1)
417 if (__wcrtomb (buf, towlower (cset->mbchars[i]), &state)
419 re_set_fastmap (fastmap, false, *(unsigned char *) buf);
424 #endif /* RE_ENABLE_I18N */
425 else if (type == OP_PERIOD
426 #ifdef RE_ENABLE_I18N
427 || type == OP_UTF8_PERIOD
428 #endif /* RE_ENABLE_I18N */
429 || type == END_OF_RE)
431 memset (fastmap, '\1', sizeof (char) * SBC_MAX);
432 if (type == END_OF_RE)
433 bufp->can_be_null = 1;
439 /* Entry point for POSIX code. */
440 /* regcomp takes a regular expression as a string and compiles it.
442 PREG is a regex_t *. We do not expect any fields to be initialized,
443 since POSIX says we shouldn't. Thus, we set
445 `buffer' to the compiled pattern;
446 `used' to the length of the compiled pattern;
447 `syntax' to RE_SYNTAX_POSIX_EXTENDED if the
448 REG_EXTENDED bit in CFLAGS is set; otherwise, to
449 RE_SYNTAX_POSIX_BASIC;
450 `newline_anchor' to REG_NEWLINE being set in CFLAGS;
451 `fastmap' to an allocated space for the fastmap;
452 `fastmap_accurate' to zero;
453 `re_nsub' to the number of subexpressions in PATTERN.
455 PATTERN is the address of the pattern string.
457 CFLAGS is a series of bits which affect compilation.
459 If REG_EXTENDED is set, we use POSIX extended syntax; otherwise, we
460 use POSIX basic syntax.
462 If REG_NEWLINE is set, then . and [^...] don't match newline.
463 Also, regexec will try a match beginning after every newline.
465 If REG_ICASE is set, then we considers upper- and lowercase
466 versions of letters to be equivalent when matching.
468 If REG_NOSUB is set, then when PREG is passed to regexec, that
469 routine will report only success or failure, and nothing about the
472 It returns 0 if it succeeds, nonzero if it doesn't. (See regex.h for
473 the return codes and their meanings.) */
476 regcomp (preg, pattern, cflags)
477 regex_t *_Restrict_ preg;
478 const char *_Restrict_ pattern;
482 reg_syntax_t syntax = ((cflags & REG_EXTENDED) ? RE_SYNTAX_POSIX_EXTENDED
483 : RE_SYNTAX_POSIX_BASIC);
489 /* Try to allocate space for the fastmap. */
490 preg->fastmap = re_malloc (char, SBC_MAX);
491 if (BE (preg->fastmap == NULL, 0))
494 syntax |= (cflags & REG_ICASE) ? RE_ICASE : 0;
496 /* If REG_NEWLINE is set, newlines are treated differently. */
497 if (cflags & REG_NEWLINE)
498 { /* REG_NEWLINE implies neither . nor [^...] match newline. */
499 syntax &= ~RE_DOT_NEWLINE;
500 syntax |= RE_HAT_LISTS_NOT_NEWLINE;
501 /* It also changes the matching behavior. */
502 preg->newline_anchor = 1;
505 preg->newline_anchor = 0;
506 preg->no_sub = !!(cflags & REG_NOSUB);
507 preg->translate = NULL;
509 ret = re_compile_internal (preg, pattern, strlen (pattern), syntax);
511 /* POSIX doesn't distinguish between an unmatched open-group and an
512 unmatched close-group: both are REG_EPAREN. */
513 if (ret == REG_ERPAREN)
516 /* We have already checked preg->fastmap != NULL. */
517 if (BE (ret == REG_NOERROR, 1))
518 /* Compute the fastmap now, since regexec cannot modify the pattern
519 buffer. This function never fails in this implementation. */
520 (void) re_compile_fastmap (preg);
523 /* Some error occurred while compiling the expression. */
524 re_free (preg->fastmap);
525 preg->fastmap = NULL;
531 weak_alias (__regcomp, regcomp)
534 /* Returns a message corresponding to an error code, ERRCODE, returned
535 from either regcomp or regexec. We don't use PREG here. */
539 regerror (errcode, preg, errbuf, errbuf_size)
541 const regex_t *_Restrict_ preg;
542 char *_Restrict_ errbuf;
544 #else /* size_t might promote */
546 regerror (int errcode, const regex_t *_Restrict_ preg,
547 char *_Restrict_ errbuf, size_t errbuf_size)
554 || errcode >= (int) (sizeof (__re_error_msgid_idx)
555 / sizeof (__re_error_msgid_idx[0])), 0))
556 /* Only error codes returned by the rest of the code should be passed
557 to this routine. If we are given anything else, or if other regex
558 code generates an invalid error code, then the program has a bug.
559 Dump core so we can fix it. */
562 msg = gettext (__re_error_msgid + __re_error_msgid_idx[errcode]);
564 msg_size = strlen (msg) + 1; /* Includes the null. */
566 if (BE (errbuf_size != 0, 1))
568 size_t cpy_size = msg_size;
569 if (BE (msg_size > errbuf_size, 0))
571 cpy_size = errbuf_size - 1;
572 errbuf[cpy_size] = '\0';
574 memcpy (errbuf, msg, cpy_size);
580 weak_alias (__regerror, regerror)
584 #ifdef RE_ENABLE_I18N
585 /* This static array is used for the map to single-byte characters when
586 UTF-8 is used. Otherwise we would allocate memory just to initialize
587 it the same all the time. UTF-8 is the preferred encoding so this is
588 a worthwhile optimization. */
589 static const bitset_t utf8_sb_map =
591 /* Set the first 128 bits. */
592 # if 4 * BITSET_WORD_BITS < ASCII_CHARS
593 # error "bitset_word_t is narrower than 32 bits"
594 # elif 3 * BITSET_WORD_BITS < ASCII_CHARS
595 BITSET_WORD_MAX, BITSET_WORD_MAX, BITSET_WORD_MAX,
596 # elif 2 * BITSET_WORD_BITS < ASCII_CHARS
597 BITSET_WORD_MAX, BITSET_WORD_MAX,
598 # elif 1 * BITSET_WORD_BITS < ASCII_CHARS
602 >> (SBC_MAX % BITSET_WORD_BITS == 0
604 : BITSET_WORD_BITS - SBC_MAX % BITSET_WORD_BITS))
610 free_dfa_content (re_dfa_t *dfa)
615 for (i = 0; i < dfa->nodes_len; ++i)
616 free_token (dfa->nodes + i);
617 re_free (dfa->nexts);
618 for (i = 0; i < dfa->nodes_len; ++i)
620 if (dfa->eclosures != NULL)
621 re_node_set_free (dfa->eclosures + i);
622 if (dfa->inveclosures != NULL)
623 re_node_set_free (dfa->inveclosures + i);
624 if (dfa->edests != NULL)
625 re_node_set_free (dfa->edests + i);
627 re_free (dfa->edests);
628 re_free (dfa->eclosures);
629 re_free (dfa->inveclosures);
630 re_free (dfa->nodes);
632 if (dfa->state_table)
633 for (i = 0; i <= dfa->state_hash_mask; ++i)
635 struct re_state_table_entry *entry = dfa->state_table + i;
636 for (j = 0; j < entry->num; ++j)
638 re_dfastate_t *state = entry->array[j];
641 re_free (entry->array);
643 re_free (dfa->state_table);
644 #ifdef RE_ENABLE_I18N
645 if (dfa->sb_char != utf8_sb_map)
646 re_free (dfa->sb_char);
648 re_free (dfa->subexp_map);
650 re_free (dfa->re_str);
657 /* Free dynamically allocated space used by PREG. */
663 re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
664 if (BE (dfa != NULL, 1))
665 free_dfa_content (dfa);
669 re_free (preg->fastmap);
670 preg->fastmap = NULL;
672 re_free (preg->translate);
673 preg->translate = NULL;
676 weak_alias (__regfree, regfree)
679 /* Entry points compatible with 4.2 BSD regex library. We don't define
680 them unless specifically requested. */
682 #if defined _REGEX_RE_COMP || defined _LIBC
684 /* BSD has one and only one pattern buffer. */
685 static struct re_pattern_buffer re_comp_buf;
689 /* Make these definitions weak in libc, so POSIX programs can redefine
690 these names if they don't use our functions, and still use
691 regcomp/regexec above without link errors. */
702 if (!re_comp_buf.buffer)
703 return gettext ("No previous regular expression");
707 if (re_comp_buf.buffer)
709 fastmap = re_comp_buf.fastmap;
710 re_comp_buf.fastmap = NULL;
711 __regfree (&re_comp_buf);
712 memset (&re_comp_buf, '\0', sizeof (re_comp_buf));
713 re_comp_buf.fastmap = fastmap;
716 if (re_comp_buf.fastmap == NULL)
718 re_comp_buf.fastmap = (char *) malloc (SBC_MAX);
719 if (re_comp_buf.fastmap == NULL)
720 return (char *) gettext (__re_error_msgid
721 + __re_error_msgid_idx[(int) REG_ESPACE]);
724 /* Since `re_exec' always passes NULL for the `regs' argument, we
725 don't need to initialize the pattern buffer fields which affect it. */
727 /* Match anchors at newlines. */
728 re_comp_buf.newline_anchor = 1;
730 ret = re_compile_internal (&re_comp_buf, s, strlen (s), re_syntax_options);
735 /* Yes, we're discarding `const' here if !HAVE_LIBINTL. */
736 return (char *) gettext (__re_error_msgid + __re_error_msgid_idx[(int) ret]);
740 libc_freeres_fn (free_mem)
742 __regfree (&re_comp_buf);
746 #endif /* _REGEX_RE_COMP */
748 /* Internal entry point.
749 Compile the regular expression PATTERN, whose length is LENGTH.
750 SYNTAX indicate regular expression's syntax. */
753 re_compile_internal (regex_t *preg, const char * pattern, size_t length,
756 reg_errcode_t err = REG_NOERROR;
760 /* Initialize the pattern buffer. */
761 preg->fastmap_accurate = 0;
762 preg->syntax = syntax;
763 preg->not_bol = preg->not_eol = 0;
766 preg->can_be_null = 0;
767 preg->regs_allocated = REGS_UNALLOCATED;
769 /* Initialize the dfa. */
770 dfa = (re_dfa_t *) preg->buffer;
771 if (BE (preg->allocated < sizeof (re_dfa_t), 0))
773 /* If zero allocated, but buffer is non-null, try to realloc
774 enough space. This loses if buffer's address is bogus, but
775 that is the user's responsibility. If ->buffer is NULL this
776 is a simple allocation. */
777 dfa = re_realloc (preg->buffer, re_dfa_t, 1);
780 preg->allocated = sizeof (re_dfa_t);
781 preg->buffer = (unsigned char *) dfa;
783 preg->used = sizeof (re_dfa_t);
785 err = init_dfa (dfa, length);
786 if (BE (err != REG_NOERROR, 0))
788 free_dfa_content (dfa);
794 /* Note: length+1 will not overflow since it is checked in init_dfa. */
795 dfa->re_str = re_malloc (char, length + 1);
796 strncpy (dfa->re_str, pattern, length + 1);
799 __libc_lock_init (dfa->lock);
801 err = re_string_construct (®exp, pattern, length, preg->translate,
802 (syntax & RE_ICASE) != 0, dfa);
803 if (BE (err != REG_NOERROR, 0))
805 re_compile_internal_free_return:
806 free_workarea_compile (preg);
807 re_string_destruct (®exp);
808 free_dfa_content (dfa);
814 /* Parse the regular expression, and build a structure tree. */
816 dfa->str_tree = parse (®exp, preg, syntax, &err);
817 if (BE (dfa->str_tree == NULL, 0))
818 goto re_compile_internal_free_return;
820 /* Analyze the tree and create the nfa. */
821 err = analyze (preg);
822 if (BE (err != REG_NOERROR, 0))
823 goto re_compile_internal_free_return;
825 #ifdef RE_ENABLE_I18N
826 /* If possible, do searching in single byte encoding to speed things up. */
827 if (dfa->is_utf8 && !(syntax & RE_ICASE) && preg->translate == NULL)
831 /* Then create the initial state of the dfa. */
832 err = create_initial_state (dfa);
834 /* Release work areas. */
835 free_workarea_compile (preg);
836 re_string_destruct (®exp);
838 if (BE (err != REG_NOERROR, 0))
840 free_dfa_content (dfa);
848 /* Initialize DFA. We use the length of the regular expression PAT_LEN
849 as the initial length of some arrays. */
852 init_dfa (re_dfa_t *dfa, size_t pat_len)
854 __re_size_t table_size;
855 #ifdef RE_ENABLE_I18N
856 size_t max_i18n_object_size = MAX (sizeof (wchar_t), sizeof (wctype_t));
858 size_t max_i18n_object_size = 0;
860 size_t max_object_size =
861 MAX (sizeof (struct re_state_table_entry),
862 MAX (sizeof (re_token_t),
863 MAX (sizeof (re_node_set),
864 MAX (sizeof (regmatch_t),
865 max_i18n_object_size))));
867 memset (dfa, '\0', sizeof (re_dfa_t));
869 /* Force allocation of str_tree_storage the first time. */
870 dfa->str_tree_storage_idx = BIN_TREE_STORAGE_SIZE;
872 /* Avoid overflows. The extra "/ 2" is for the table_size doubling
873 calculation below, and for similar doubling calculations
874 elsewhere. And it's <= rather than <, because some of the
875 doubling calculations add 1 afterwards. */
876 if (BE (SIZE_MAX / max_object_size / 2 <= pat_len, 0))
879 dfa->nodes_alloc = pat_len + 1;
880 dfa->nodes = re_malloc (re_token_t, dfa->nodes_alloc);
882 /* table_size = 2 ^ ceil(log pat_len) */
883 for (table_size = 1; ; table_size <<= 1)
884 if (table_size > pat_len)
887 dfa->state_table = calloc (sizeof (struct re_state_table_entry), table_size);
888 dfa->state_hash_mask = table_size - 1;
890 dfa->mb_cur_max = MB_CUR_MAX;
892 if (dfa->mb_cur_max == 6
893 && strcmp (_NL_CURRENT (LC_CTYPE, _NL_CTYPE_CODESET_NAME), "UTF-8") == 0)
895 dfa->map_notascii = (_NL_CURRENT_WORD (LC_CTYPE, _NL_CTYPE_MAP_TO_NONASCII)
898 if (strcmp (locale_charset (), "UTF-8") == 0)
901 /* We check exhaustively in the loop below if this charset is a
902 superset of ASCII. */
903 dfa->map_notascii = 0;
906 #ifdef RE_ENABLE_I18N
907 if (dfa->mb_cur_max > 1)
910 dfa->sb_char = (re_bitset_ptr_t) utf8_sb_map;
915 dfa->sb_char = (re_bitset_ptr_t) calloc (sizeof (bitset_t), 1);
916 if (BE (dfa->sb_char == NULL, 0))
919 /* Set the bits corresponding to single byte chars. */
920 for (i = 0, ch = 0; i < BITSET_WORDS; ++i)
921 for (j = 0; j < BITSET_WORD_BITS; ++j, ++ch)
923 wint_t wch = __btowc (ch);
925 dfa->sb_char[i] |= (bitset_word_t) 1 << j;
927 if (isascii (ch) && wch != ch)
928 dfa->map_notascii = 1;
935 if (BE (dfa->nodes == NULL || dfa->state_table == NULL, 0))
940 /* Initialize WORD_CHAR table, which indicate which character is
941 "word". In this case "word" means that it is the word construction
942 character used by some operators like "\<", "\>", etc. */
946 init_word_char (re_dfa_t *dfa)
949 dfa->word_ops_used = 1;
950 for (i = 0, ch = 0; i < BITSET_WORDS; ++i)
951 for (j = 0; j < BITSET_WORD_BITS; ++j, ++ch)
952 if (isalnum (ch) || ch == '_')
953 dfa->word_char[i] |= (bitset_word_t) 1 << j;
956 /* Free the work area which are only used while compiling. */
959 free_workarea_compile (regex_t *preg)
961 re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
962 bin_tree_storage_t *storage, *next;
963 for (storage = dfa->str_tree_storage; storage; storage = next)
965 next = storage->next;
968 dfa->str_tree_storage = NULL;
969 dfa->str_tree_storage_idx = BIN_TREE_STORAGE_SIZE;
970 dfa->str_tree = NULL;
971 re_free (dfa->org_indices);
972 dfa->org_indices = NULL;
975 /* Create initial states for all contexts. */
978 create_initial_state (re_dfa_t *dfa)
982 re_node_set init_nodes;
984 /* Initial states have the epsilon closure of the node which is
985 the first node of the regular expression. */
986 first = dfa->str_tree->first->node_idx;
987 dfa->init_node = first;
988 err = re_node_set_init_copy (&init_nodes, dfa->eclosures + first);
989 if (BE (err != REG_NOERROR, 0))
992 /* The back-references which are in initial states can epsilon transit,
993 since in this case all of the subexpressions can be null.
994 Then we add epsilon closures of the nodes which are the next nodes of
995 the back-references. */
996 if (dfa->nbackref > 0)
997 for (i = 0; i < init_nodes.nelem; ++i)
999 Idx node_idx = init_nodes.elems[i];
1000 re_token_type_t type = dfa->nodes[node_idx].type;
1003 if (type != OP_BACK_REF)
1005 for (clexp_idx = 0; clexp_idx < init_nodes.nelem; ++clexp_idx)
1007 re_token_t *clexp_node;
1008 clexp_node = dfa->nodes + init_nodes.elems[clexp_idx];
1009 if (clexp_node->type == OP_CLOSE_SUBEXP
1010 && clexp_node->opr.idx == dfa->nodes[node_idx].opr.idx)
1013 if (clexp_idx == init_nodes.nelem)
1016 if (type == OP_BACK_REF)
1018 Idx dest_idx = dfa->edests[node_idx].elems[0];
1019 if (!re_node_set_contains (&init_nodes, dest_idx))
1021 re_node_set_merge (&init_nodes, dfa->eclosures + dest_idx);
1027 /* It must be the first time to invoke acquire_state. */
1028 dfa->init_state = re_acquire_state_context (&err, dfa, &init_nodes, 0);
1029 /* We don't check ERR here, since the initial state must not be NULL. */
1030 if (BE (dfa->init_state == NULL, 0))
1032 if (dfa->init_state->has_constraint)
1034 dfa->init_state_word = re_acquire_state_context (&err, dfa, &init_nodes,
1036 dfa->init_state_nl = re_acquire_state_context (&err, dfa, &init_nodes,
1038 dfa->init_state_begbuf = re_acquire_state_context (&err, dfa,
1042 if (BE (dfa->init_state_word == NULL || dfa->init_state_nl == NULL
1043 || dfa->init_state_begbuf == NULL, 0))
1047 dfa->init_state_word = dfa->init_state_nl
1048 = dfa->init_state_begbuf = dfa->init_state;
1050 re_node_set_free (&init_nodes);
1054 #ifdef RE_ENABLE_I18N
1055 /* If it is possible to do searching in single byte encoding instead of UTF-8
1056 to speed things up, set dfa->mb_cur_max to 1, clear is_utf8 and change
1057 DFA nodes where needed. */
1060 optimize_utf8 (re_dfa_t *dfa)
1064 bool mb_chars = false;
1065 bool has_period = false;
1067 for (node = 0; node < dfa->nodes_len; ++node)
1068 switch (dfa->nodes[node].type)
1071 if (dfa->nodes[node].opr.c >= ASCII_CHARS)
1075 switch (dfa->nodes[node].opr.ctx_type)
1083 /* Word anchors etc. cannot be handled. It's okay to test
1084 opr.ctx_type since constraints (for all DFA nodes) are
1085 created by ORing one or more opr.ctx_type values. */
1095 case OP_DUP_ASTERISK:
1096 case OP_OPEN_SUBEXP:
1097 case OP_CLOSE_SUBEXP:
1099 case COMPLEX_BRACKET:
1101 case SIMPLE_BRACKET:
1102 /* Just double check. */
1104 int rshift = (ASCII_CHARS % BITSET_WORD_BITS == 0
1106 : BITSET_WORD_BITS - ASCII_CHARS % BITSET_WORD_BITS);
1107 for (i = ASCII_CHARS / BITSET_WORD_BITS; i < BITSET_WORDS; ++i)
1109 if (dfa->nodes[node].opr.sbcset[i] >> rshift != 0)
1119 if (mb_chars || has_period)
1120 for (node = 0; node < dfa->nodes_len; ++node)
1122 if (dfa->nodes[node].type == CHARACTER
1123 && dfa->nodes[node].opr.c >= ASCII_CHARS)
1124 dfa->nodes[node].mb_partial = 0;
1125 else if (dfa->nodes[node].type == OP_PERIOD)
1126 dfa->nodes[node].type = OP_UTF8_PERIOD;
1129 /* The search can be in single byte locale. */
1130 dfa->mb_cur_max = 1;
1132 dfa->has_mb_node = dfa->nbackref > 0 || has_period;
1136 /* Analyze the structure tree, and calculate "first", "next", "edest",
1137 "eclosure", and "inveclosure". */
1139 static reg_errcode_t
1140 analyze (regex_t *preg)
1142 re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
1145 /* Allocate arrays. */
1146 dfa->nexts = re_malloc (Idx, dfa->nodes_alloc);
1147 dfa->org_indices = re_malloc (Idx, dfa->nodes_alloc);
1148 dfa->edests = re_malloc (re_node_set, dfa->nodes_alloc);
1149 dfa->eclosures = re_malloc (re_node_set, dfa->nodes_alloc);
1150 if (BE (dfa->nexts == NULL || dfa->org_indices == NULL || dfa->edests == NULL
1151 || dfa->eclosures == NULL, 0))
1154 dfa->subexp_map = re_malloc (Idx, preg->re_nsub);
1155 if (dfa->subexp_map != NULL)
1158 for (i = 0; i < preg->re_nsub; i++)
1159 dfa->subexp_map[i] = i;
1160 preorder (dfa->str_tree, optimize_subexps, dfa);
1161 for (i = 0; i < preg->re_nsub; i++)
1162 if (dfa->subexp_map[i] != i)
1164 if (i == preg->re_nsub)
1166 free (dfa->subexp_map);
1167 dfa->subexp_map = NULL;
1171 ret = postorder (dfa->str_tree, lower_subexps, preg);
1172 if (BE (ret != REG_NOERROR, 0))
1174 ret = postorder (dfa->str_tree, calc_first, dfa);
1175 if (BE (ret != REG_NOERROR, 0))
1177 preorder (dfa->str_tree, calc_next, dfa);
1178 ret = preorder (dfa->str_tree, link_nfa_nodes, dfa);
1179 if (BE (ret != REG_NOERROR, 0))
1181 ret = calc_eclosure (dfa);
1182 if (BE (ret != REG_NOERROR, 0))
1185 /* We only need this during the prune_impossible_nodes pass in regexec.c;
1186 skip it if p_i_n will not run, as calc_inveclosure can be quadratic. */
1187 if ((!preg->no_sub && preg->re_nsub > 0 && dfa->has_plural_match)
1190 dfa->inveclosures = re_malloc (re_node_set, dfa->nodes_len);
1191 if (BE (dfa->inveclosures == NULL, 0))
1193 ret = calc_inveclosure (dfa);
1199 /* Our parse trees are very unbalanced, so we cannot use a stack to
1200 implement parse tree visits. Instead, we use parent pointers and
1201 some hairy code in these two functions. */
1202 static reg_errcode_t
1203 postorder (bin_tree_t *root, reg_errcode_t (fn (void *, bin_tree_t *)),
1206 bin_tree_t *node, *prev;
1208 for (node = root; ; )
1210 /* Descend down the tree, preferably to the left (or to the right
1211 if that's the only child). */
1212 while (node->left || node->right)
1220 reg_errcode_t err = fn (extra, node);
1221 if (BE (err != REG_NOERROR, 0))
1223 if (node->parent == NULL)
1226 node = node->parent;
1228 /* Go up while we have a node that is reached from the right. */
1229 while (node->right == prev || node->right == NULL);
1234 static reg_errcode_t
1235 preorder (bin_tree_t *root, reg_errcode_t (fn (void *, bin_tree_t *)),
1240 for (node = root; ; )
1242 reg_errcode_t err = fn (extra, node);
1243 if (BE (err != REG_NOERROR, 0))
1246 /* Go to the left node, or up and to the right. */
1251 bin_tree_t *prev = NULL;
1252 while (node->right == prev || node->right == NULL)
1255 node = node->parent;
1264 /* Optimization pass: if a SUBEXP is entirely contained, strip it and tell
1265 re_search_internal to map the inner one's opr.idx to this one's. Adjust
1266 backreferences as well. Requires a preorder visit. */
1267 static reg_errcode_t
1268 optimize_subexps (void *extra, bin_tree_t *node)
1270 re_dfa_t *dfa = (re_dfa_t *) extra;
1272 if (node->token.type == OP_BACK_REF && dfa->subexp_map)
1274 int idx = node->token.opr.idx;
1275 node->token.opr.idx = dfa->subexp_map[idx];
1276 dfa->used_bkref_map |= 1 << node->token.opr.idx;
1279 else if (node->token.type == SUBEXP
1280 && node->left && node->left->token.type == SUBEXP)
1282 Idx other_idx = node->left->token.opr.idx;
1284 node->left = node->left->left;
1286 node->left->parent = node;
1288 dfa->subexp_map[other_idx] = dfa->subexp_map[node->token.opr.idx];
1289 if (other_idx < BITSET_WORD_BITS)
1290 dfa->used_bkref_map &= ~((bitset_word_t) 1 << other_idx);
1296 /* Lowering pass: Turn each SUBEXP node into the appropriate concatenation
1297 of OP_OPEN_SUBEXP, the body of the SUBEXP (if any) and OP_CLOSE_SUBEXP. */
1298 static reg_errcode_t
1299 lower_subexps (void *extra, bin_tree_t *node)
1301 regex_t *preg = (regex_t *) extra;
1302 reg_errcode_t err = REG_NOERROR;
1304 if (node->left && node->left->token.type == SUBEXP)
1306 node->left = lower_subexp (&err, preg, node->left);
1308 node->left->parent = node;
1310 if (node->right && node->right->token.type == SUBEXP)
1312 node->right = lower_subexp (&err, preg, node->right);
1314 node->right->parent = node;
1321 lower_subexp (reg_errcode_t *err, regex_t *preg, bin_tree_t *node)
1323 re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
1324 bin_tree_t *body = node->left;
1325 bin_tree_t *op, *cls, *tree1, *tree;
1328 /* We do not optimize empty subexpressions, because otherwise we may
1329 have bad CONCAT nodes with NULL children. This is obviously not
1330 very common, so we do not lose much. An example that triggers
1331 this case is the sed "script" /\(\)/x. */
1332 && node->left != NULL
1333 && (node->token.opr.idx >= BITSET_WORD_BITS
1334 || !(dfa->used_bkref_map
1335 & ((bitset_word_t) 1 << node->token.opr.idx))))
1338 /* Convert the SUBEXP node to the concatenation of an
1339 OP_OPEN_SUBEXP, the contents, and an OP_CLOSE_SUBEXP. */
1340 op = create_tree (dfa, NULL, NULL, OP_OPEN_SUBEXP);
1341 cls = create_tree (dfa, NULL, NULL, OP_CLOSE_SUBEXP);
1342 tree1 = body ? create_tree (dfa, body, cls, CONCAT) : cls;
1343 tree = create_tree (dfa, op, tree1, CONCAT);
1344 if (BE (tree == NULL || tree1 == NULL || op == NULL || cls == NULL, 0))
1350 op->token.opr.idx = cls->token.opr.idx = node->token.opr.idx;
1351 op->token.opt_subexp = cls->token.opt_subexp = node->token.opt_subexp;
1355 /* Pass 1 in building the NFA: compute FIRST and create unlinked automaton
1356 nodes. Requires a postorder visit. */
1357 static reg_errcode_t
1358 calc_first (void *extra, bin_tree_t *node)
1360 re_dfa_t *dfa = (re_dfa_t *) extra;
1361 if (node->token.type == CONCAT)
1363 node->first = node->left->first;
1364 node->node_idx = node->left->node_idx;
1369 node->node_idx = re_dfa_add_node (dfa, node->token);
1370 if (BE (node->node_idx == REG_MISSING, 0))
1372 if (node->token.type == ANCHOR)
1373 dfa->nodes[node->node_idx].constraint = node->token.opr.ctx_type;
1378 /* Pass 2: compute NEXT on the tree. Preorder visit. */
1379 static reg_errcode_t
1380 calc_next (void *extra, bin_tree_t *node)
1382 switch (node->token.type)
1384 case OP_DUP_ASTERISK:
1385 node->left->next = node;
1388 node->left->next = node->right->first;
1389 node->right->next = node->next;
1393 node->left->next = node->next;
1395 node->right->next = node->next;
1401 /* Pass 3: link all DFA nodes to their NEXT node (any order will do). */
1402 static reg_errcode_t
1403 link_nfa_nodes (void *extra, bin_tree_t *node)
1405 re_dfa_t *dfa = (re_dfa_t *) extra;
1406 Idx idx = node->node_idx;
1407 reg_errcode_t err = REG_NOERROR;
1409 switch (node->token.type)
1415 assert (node->next == NULL);
1418 case OP_DUP_ASTERISK:
1422 dfa->has_plural_match = 1;
1423 if (node->left != NULL)
1424 left = node->left->first->node_idx;
1426 left = node->next->node_idx;
1427 if (node->right != NULL)
1428 right = node->right->first->node_idx;
1430 right = node->next->node_idx;
1431 assert (REG_VALID_INDEX (left));
1432 assert (REG_VALID_INDEX (right));
1433 err = re_node_set_init_2 (dfa->edests + idx, left, right);
1438 case OP_OPEN_SUBEXP:
1439 case OP_CLOSE_SUBEXP:
1440 err = re_node_set_init_1 (dfa->edests + idx, node->next->node_idx);
1444 dfa->nexts[idx] = node->next->node_idx;
1445 if (node->token.type == OP_BACK_REF)
1446 re_node_set_init_1 (dfa->edests + idx, dfa->nexts[idx]);
1450 assert (!IS_EPSILON_NODE (node->token.type));
1451 dfa->nexts[idx] = node->next->node_idx;
1458 /* Duplicate the epsilon closure of the node ROOT_NODE.
1459 Note that duplicated nodes have constraint INIT_CONSTRAINT in addition
1460 to their own constraint. */
1462 static reg_errcode_t
1464 duplicate_node_closure (re_dfa_t *dfa, Idx top_org_node, Idx top_clone_node,
1465 Idx root_node, unsigned int init_constraint)
1467 Idx org_node, clone_node;
1469 unsigned int constraint = init_constraint;
1470 for (org_node = top_org_node, clone_node = top_clone_node;;)
1472 Idx org_dest, clone_dest;
1473 if (dfa->nodes[org_node].type == OP_BACK_REF)
1475 /* If the back reference epsilon-transit, its destination must
1476 also have the constraint. Then duplicate the epsilon closure
1477 of the destination of the back reference, and store it in
1478 edests of the back reference. */
1479 org_dest = dfa->nexts[org_node];
1480 re_node_set_empty (dfa->edests + clone_node);
1481 clone_dest = duplicate_node (dfa, org_dest, constraint);
1482 if (BE (clone_dest == REG_MISSING, 0))
1484 dfa->nexts[clone_node] = dfa->nexts[org_node];
1485 ok = re_node_set_insert (dfa->edests + clone_node, clone_dest);
1489 else if (dfa->edests[org_node].nelem == 0)
1491 /* In case of the node can't epsilon-transit, don't duplicate the
1492 destination and store the original destination as the
1493 destination of the node. */
1494 dfa->nexts[clone_node] = dfa->nexts[org_node];
1497 else if (dfa->edests[org_node].nelem == 1)
1499 /* In case of the node can epsilon-transit, and it has only one
1501 org_dest = dfa->edests[org_node].elems[0];
1502 re_node_set_empty (dfa->edests + clone_node);
1503 clone_dest = search_duplicated_node (dfa, org_dest, constraint);
1504 /* If the node is root_node itself, it means the epsilon closure
1505 has a loop. Then tie it to the destination of the root_node. */
1506 if (org_node == root_node && clone_node != org_node)
1508 ok = re_node_set_insert (dfa->edests + clone_node, org_dest);
1513 /* In case the node has another constraint, append it. */
1514 constraint |= dfa->nodes[org_node].constraint;
1515 clone_dest = duplicate_node (dfa, org_dest, constraint);
1516 if (BE (clone_dest == REG_MISSING, 0))
1518 ok = re_node_set_insert (dfa->edests + clone_node, clone_dest);
1522 else /* dfa->edests[org_node].nelem == 2 */
1524 /* In case of the node can epsilon-transit, and it has two
1525 destinations. In the bin_tree_t and DFA, that's '|' and '*'. */
1526 org_dest = dfa->edests[org_node].elems[0];
1527 re_node_set_empty (dfa->edests + clone_node);
1528 /* Search for a duplicated node which satisfies the constraint. */
1529 clone_dest = search_duplicated_node (dfa, org_dest, constraint);
1530 if (clone_dest == REG_MISSING)
1532 /* There is no such duplicated node, create a new one. */
1534 clone_dest = duplicate_node (dfa, org_dest, constraint);
1535 if (BE (clone_dest == REG_MISSING, 0))
1537 ok = re_node_set_insert (dfa->edests + clone_node, clone_dest);
1540 err = duplicate_node_closure (dfa, org_dest, clone_dest,
1541 root_node, constraint);
1542 if (BE (err != REG_NOERROR, 0))
1547 /* There is a duplicated node which satisfy the constraint,
1548 use it to avoid infinite loop. */
1549 ok = re_node_set_insert (dfa->edests + clone_node, clone_dest);
1554 org_dest = dfa->edests[org_node].elems[1];
1555 clone_dest = duplicate_node (dfa, org_dest, constraint);
1556 if (BE (clone_dest == REG_MISSING, 0))
1558 ok = re_node_set_insert (dfa->edests + clone_node, clone_dest);
1562 org_node = org_dest;
1563 clone_node = clone_dest;
1568 /* Search for a node which is duplicated from the node ORG_NODE, and
1569 satisfies the constraint CONSTRAINT. */
1572 search_duplicated_node (const re_dfa_t *dfa, Idx org_node,
1573 unsigned int constraint)
1576 for (idx = dfa->nodes_len - 1; dfa->nodes[idx].duplicated && idx > 0; --idx)
1578 if (org_node == dfa->org_indices[idx]
1579 && constraint == dfa->nodes[idx].constraint)
1580 return idx; /* Found. */
1582 return REG_MISSING; /* Not found. */
1585 /* Duplicate the node whose index is ORG_IDX and set the constraint CONSTRAINT.
1586 Return the index of the new node, or REG_MISSING if insufficient storage is
1590 duplicate_node (re_dfa_t *dfa, Idx org_idx, unsigned int constraint)
1592 Idx dup_idx = re_dfa_add_node (dfa, dfa->nodes[org_idx]);
1593 if (BE (dup_idx != REG_MISSING, 1))
1595 dfa->nodes[dup_idx].constraint = constraint;
1596 dfa->nodes[dup_idx].constraint |= dfa->nodes[org_idx].constraint;
1597 dfa->nodes[dup_idx].duplicated = 1;
1599 /* Store the index of the original node. */
1600 dfa->org_indices[dup_idx] = org_idx;
1605 static reg_errcode_t
1606 calc_inveclosure (re_dfa_t *dfa)
1610 for (idx = 0; idx < dfa->nodes_len; ++idx)
1611 re_node_set_init_empty (dfa->inveclosures + idx);
1613 for (src = 0; src < dfa->nodes_len; ++src)
1615 Idx *elems = dfa->eclosures[src].elems;
1616 for (idx = 0; idx < dfa->eclosures[src].nelem; ++idx)
1618 ok = re_node_set_insert_last (dfa->inveclosures + elems[idx], src);
1627 /* Calculate "eclosure" for all the node in DFA. */
1629 static reg_errcode_t
1630 calc_eclosure (re_dfa_t *dfa)
1635 assert (dfa->nodes_len > 0);
1638 /* For each nodes, calculate epsilon closure. */
1639 for (node_idx = 0; ; ++node_idx)
1642 re_node_set eclosure_elem;
1643 if (node_idx == dfa->nodes_len)
1652 assert (dfa->eclosures[node_idx].nelem != REG_MISSING);
1655 /* If we have already calculated, skip it. */
1656 if (dfa->eclosures[node_idx].nelem != 0)
1658 /* Calculate epsilon closure of `node_idx'. */
1659 err = calc_eclosure_iter (&eclosure_elem, dfa, node_idx, true);
1660 if (BE (err != REG_NOERROR, 0))
1663 if (dfa->eclosures[node_idx].nelem == 0)
1666 re_node_set_free (&eclosure_elem);
1672 /* Calculate epsilon closure of NODE. */
1674 static reg_errcode_t
1675 calc_eclosure_iter (re_node_set *new_set, re_dfa_t *dfa, Idx node, bool root)
1681 re_node_set eclosure;
1683 err = re_node_set_alloc (&eclosure, dfa->edests[node].nelem + 1);
1684 if (BE (err != REG_NOERROR, 0))
1687 /* This indicates that we are calculating this node now.
1688 We reference this value to avoid infinite loop. */
1689 dfa->eclosures[node].nelem = REG_MISSING;
1691 /* If the current node has constraints, duplicate all nodes
1692 since they must inherit the constraints. */
1693 if (dfa->nodes[node].constraint
1694 && dfa->edests[node].nelem
1695 && !dfa->nodes[dfa->edests[node].elems[0]].duplicated)
1697 err = duplicate_node_closure (dfa, node, node, node,
1698 dfa->nodes[node].constraint);
1699 if (BE (err != REG_NOERROR, 0))
1703 /* Expand each epsilon destination nodes. */
1704 if (IS_EPSILON_NODE(dfa->nodes[node].type))
1705 for (i = 0; i < dfa->edests[node].nelem; ++i)
1707 re_node_set eclosure_elem;
1708 Idx edest = dfa->edests[node].elems[i];
1709 /* If calculating the epsilon closure of `edest' is in progress,
1710 return intermediate result. */
1711 if (dfa->eclosures[edest].nelem == REG_MISSING)
1716 /* If we haven't calculated the epsilon closure of `edest' yet,
1717 calculate now. Otherwise use calculated epsilon closure. */
1718 if (dfa->eclosures[edest].nelem == 0)
1720 err = calc_eclosure_iter (&eclosure_elem, dfa, edest, false);
1721 if (BE (err != REG_NOERROR, 0))
1725 eclosure_elem = dfa->eclosures[edest];
1726 /* Merge the epsilon closure of `edest'. */
1727 re_node_set_merge (&eclosure, &eclosure_elem);
1728 /* If the epsilon closure of `edest' is incomplete,
1729 the epsilon closure of this node is also incomplete. */
1730 if (dfa->eclosures[edest].nelem == 0)
1733 re_node_set_free (&eclosure_elem);
1737 /* Epsilon closures include itself. */
1738 ok = re_node_set_insert (&eclosure, node);
1741 if (incomplete && !root)
1742 dfa->eclosures[node].nelem = 0;
1744 dfa->eclosures[node] = eclosure;
1745 *new_set = eclosure;
1749 /* Functions for token which are used in the parser. */
1751 /* Fetch a token from INPUT.
1752 We must not use this function inside bracket expressions. */
1756 fetch_token (re_token_t *result, re_string_t *input, reg_syntax_t syntax)
1758 re_string_skip_bytes (input, peek_token (result, input, syntax));
1761 /* Peek a token from INPUT, and return the length of the token.
1762 We must not use this function inside bracket expressions. */
1766 peek_token (re_token_t *token, re_string_t *input, reg_syntax_t syntax)
1770 if (re_string_eoi (input))
1772 token->type = END_OF_RE;
1776 c = re_string_peek_byte (input, 0);
1779 token->word_char = 0;
1780 #ifdef RE_ENABLE_I18N
1781 token->mb_partial = 0;
1782 if (input->mb_cur_max > 1 &&
1783 !re_string_first_byte (input, re_string_cur_idx (input)))
1785 token->type = CHARACTER;
1786 token->mb_partial = 1;
1793 if (re_string_cur_idx (input) + 1 >= re_string_length (input))
1795 token->type = BACK_SLASH;
1799 c2 = re_string_peek_byte_case (input, 1);
1801 token->type = CHARACTER;
1802 #ifdef RE_ENABLE_I18N
1803 if (input->mb_cur_max > 1)
1805 wint_t wc = re_string_wchar_at (input,
1806 re_string_cur_idx (input) + 1);
1807 token->word_char = IS_WIDE_WORD_CHAR (wc) != 0;
1811 token->word_char = IS_WORD_CHAR (c2) != 0;
1816 if (!(syntax & RE_LIMITED_OPS) && !(syntax & RE_NO_BK_VBAR))
1817 token->type = OP_ALT;
1819 case '1': case '2': case '3': case '4': case '5':
1820 case '6': case '7': case '8': case '9':
1821 if (!(syntax & RE_NO_BK_REFS))
1823 token->type = OP_BACK_REF;
1824 token->opr.idx = c2 - '1';
1828 if (!(syntax & RE_NO_GNU_OPS))
1830 token->type = ANCHOR;
1831 token->opr.ctx_type = WORD_FIRST;
1835 if (!(syntax & RE_NO_GNU_OPS))
1837 token->type = ANCHOR;
1838 token->opr.ctx_type = WORD_LAST;
1842 if (!(syntax & RE_NO_GNU_OPS))
1844 token->type = ANCHOR;
1845 token->opr.ctx_type = WORD_DELIM;
1849 if (!(syntax & RE_NO_GNU_OPS))
1851 token->type = ANCHOR;
1852 token->opr.ctx_type = NOT_WORD_DELIM;
1856 if (!(syntax & RE_NO_GNU_OPS))
1857 token->type = OP_WORD;
1860 if (!(syntax & RE_NO_GNU_OPS))
1861 token->type = OP_NOTWORD;
1864 if (!(syntax & RE_NO_GNU_OPS))
1865 token->type = OP_SPACE;
1868 if (!(syntax & RE_NO_GNU_OPS))
1869 token->type = OP_NOTSPACE;
1872 if (!(syntax & RE_NO_GNU_OPS))
1874 token->type = ANCHOR;
1875 token->opr.ctx_type = BUF_FIRST;
1879 if (!(syntax & RE_NO_GNU_OPS))
1881 token->type = ANCHOR;
1882 token->opr.ctx_type = BUF_LAST;
1886 if (!(syntax & RE_NO_BK_PARENS))
1887 token->type = OP_OPEN_SUBEXP;
1890 if (!(syntax & RE_NO_BK_PARENS))
1891 token->type = OP_CLOSE_SUBEXP;
1894 if (!(syntax & RE_LIMITED_OPS) && (syntax & RE_BK_PLUS_QM))
1895 token->type = OP_DUP_PLUS;
1898 if (!(syntax & RE_LIMITED_OPS) && (syntax & RE_BK_PLUS_QM))
1899 token->type = OP_DUP_QUESTION;
1902 if ((syntax & RE_INTERVALS) && (!(syntax & RE_NO_BK_BRACES)))
1903 token->type = OP_OPEN_DUP_NUM;
1906 if ((syntax & RE_INTERVALS) && (!(syntax & RE_NO_BK_BRACES)))
1907 token->type = OP_CLOSE_DUP_NUM;
1915 token->type = CHARACTER;
1916 #ifdef RE_ENABLE_I18N
1917 if (input->mb_cur_max > 1)
1919 wint_t wc = re_string_wchar_at (input, re_string_cur_idx (input));
1920 token->word_char = IS_WIDE_WORD_CHAR (wc) != 0;
1924 token->word_char = IS_WORD_CHAR (token->opr.c);
1929 if (syntax & RE_NEWLINE_ALT)
1930 token->type = OP_ALT;
1933 if (!(syntax & RE_LIMITED_OPS) && (syntax & RE_NO_BK_VBAR))
1934 token->type = OP_ALT;
1937 token->type = OP_DUP_ASTERISK;
1940 if (!(syntax & RE_LIMITED_OPS) && !(syntax & RE_BK_PLUS_QM))
1941 token->type = OP_DUP_PLUS;
1944 if (!(syntax & RE_LIMITED_OPS) && !(syntax & RE_BK_PLUS_QM))
1945 token->type = OP_DUP_QUESTION;
1948 if ((syntax & RE_INTERVALS) && (syntax & RE_NO_BK_BRACES))
1949 token->type = OP_OPEN_DUP_NUM;
1952 if ((syntax & RE_INTERVALS) && (syntax & RE_NO_BK_BRACES))
1953 token->type = OP_CLOSE_DUP_NUM;
1956 if (syntax & RE_NO_BK_PARENS)
1957 token->type = OP_OPEN_SUBEXP;
1960 if (syntax & RE_NO_BK_PARENS)
1961 token->type = OP_CLOSE_SUBEXP;
1964 token->type = OP_OPEN_BRACKET;
1967 token->type = OP_PERIOD;
1970 if (!(syntax & (RE_CONTEXT_INDEP_ANCHORS | RE_CARET_ANCHORS_HERE)) &&
1971 re_string_cur_idx (input) != 0)
1973 char prev = re_string_peek_byte (input, -1);
1974 if (!(syntax & RE_NEWLINE_ALT) || prev != '\n')
1977 token->type = ANCHOR;
1978 token->opr.ctx_type = LINE_FIRST;
1981 if (!(syntax & RE_CONTEXT_INDEP_ANCHORS) &&
1982 re_string_cur_idx (input) + 1 != re_string_length (input))
1985 re_string_skip_bytes (input, 1);
1986 peek_token (&next, input, syntax);
1987 re_string_skip_bytes (input, -1);
1988 if (next.type != OP_ALT && next.type != OP_CLOSE_SUBEXP)
1991 token->type = ANCHOR;
1992 token->opr.ctx_type = LINE_LAST;
2000 /* Peek a token from INPUT, and return the length of the token.
2001 We must not use this function out of bracket expressions. */
2005 peek_token_bracket (re_token_t *token, re_string_t *input, reg_syntax_t syntax)
2008 if (re_string_eoi (input))
2010 token->type = END_OF_RE;
2013 c = re_string_peek_byte (input, 0);
2016 #ifdef RE_ENABLE_I18N
2017 if (input->mb_cur_max > 1 &&
2018 !re_string_first_byte (input, re_string_cur_idx (input)))
2020 token->type = CHARACTER;
2023 #endif /* RE_ENABLE_I18N */
2025 if (c == '\\' && (syntax & RE_BACKSLASH_ESCAPE_IN_LISTS)
2026 && re_string_cur_idx (input) + 1 < re_string_length (input))
2028 /* In this case, '\' escape a character. */
2030 re_string_skip_bytes (input, 1);
2031 c2 = re_string_peek_byte (input, 0);
2033 token->type = CHARACTER;
2036 if (c == '[') /* '[' is a special char in a bracket exps. */
2040 if (re_string_cur_idx (input) + 1 < re_string_length (input))
2041 c2 = re_string_peek_byte (input, 1);
2049 token->type = OP_OPEN_COLL_ELEM;
2052 token->type = OP_OPEN_EQUIV_CLASS;
2055 if (syntax & RE_CHAR_CLASSES)
2057 token->type = OP_OPEN_CHAR_CLASS;
2060 /* else fall through. */
2062 token->type = CHARACTER;
2072 token->type = OP_CHARSET_RANGE;
2075 token->type = OP_CLOSE_BRACKET;
2078 token->type = OP_NON_MATCH_LIST;
2081 token->type = CHARACTER;
2086 /* Functions for parser. */
2088 /* Entry point of the parser.
2089 Parse the regular expression REGEXP and return the structure tree.
2090 If an error is occured, ERR is set by error code, and return NULL.
2091 This function build the following tree, from regular expression <reg_exp>:
2097 CAT means concatenation.
2098 EOR means end of regular expression. */
2101 parse (re_string_t *regexp, regex_t *preg, reg_syntax_t syntax,
2104 re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
2105 bin_tree_t *tree, *eor, *root;
2106 re_token_t current_token;
2107 dfa->syntax = syntax;
2108 fetch_token (¤t_token, regexp, syntax | RE_CARET_ANCHORS_HERE);
2109 tree = parse_reg_exp (regexp, preg, ¤t_token, syntax, 0, err);
2110 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2112 eor = create_tree (dfa, NULL, NULL, END_OF_RE);
2114 root = create_tree (dfa, tree, eor, CONCAT);
2117 if (BE (eor == NULL || root == NULL, 0))
2125 /* This function build the following tree, from regular expression
2126 <branch1>|<branch2>:
2132 ALT means alternative, which represents the operator `|'. */
2135 parse_reg_exp (re_string_t *regexp, regex_t *preg, re_token_t *token,
2136 reg_syntax_t syntax, Idx nest, reg_errcode_t *err)
2138 re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
2139 bin_tree_t *tree, *branch = NULL;
2140 tree = parse_branch (regexp, preg, token, syntax, nest, err);
2141 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2144 while (token->type == OP_ALT)
2146 fetch_token (token, regexp, syntax | RE_CARET_ANCHORS_HERE);
2147 if (token->type != OP_ALT && token->type != END_OF_RE
2148 && (nest == 0 || token->type != OP_CLOSE_SUBEXP))
2150 branch = parse_branch (regexp, preg, token, syntax, nest, err);
2151 if (BE (*err != REG_NOERROR && branch == NULL, 0))
2156 tree = create_tree (dfa, tree, branch, OP_ALT);
2157 if (BE (tree == NULL, 0))
2166 /* This function build the following tree, from regular expression
2173 CAT means concatenation. */
2176 parse_branch (re_string_t *regexp, regex_t *preg, re_token_t *token,
2177 reg_syntax_t syntax, Idx nest, reg_errcode_t *err)
2179 bin_tree_t *tree, *expr;
2180 re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
2181 tree = parse_expression (regexp, preg, token, syntax, nest, err);
2182 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2185 while (token->type != OP_ALT && token->type != END_OF_RE
2186 && (nest == 0 || token->type != OP_CLOSE_SUBEXP))
2188 expr = parse_expression (regexp, preg, token, syntax, nest, err);
2189 if (BE (*err != REG_NOERROR && expr == NULL, 0))
2193 if (tree != NULL && expr != NULL)
2195 tree = create_tree (dfa, tree, expr, CONCAT);
2202 else if (tree == NULL)
2204 /* Otherwise expr == NULL, we don't need to create new tree. */
2209 /* This function build the following tree, from regular expression a*:
2216 parse_expression (re_string_t *regexp, regex_t *preg, re_token_t *token,
2217 reg_syntax_t syntax, Idx nest, reg_errcode_t *err)
2219 re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
2221 switch (token->type)
2224 tree = create_token_tree (dfa, NULL, NULL, token);
2225 if (BE (tree == NULL, 0))
2230 #ifdef RE_ENABLE_I18N
2231 if (dfa->mb_cur_max > 1)
2233 while (!re_string_eoi (regexp)
2234 && !re_string_first_byte (regexp, re_string_cur_idx (regexp)))
2236 bin_tree_t *mbc_remain;
2237 fetch_token (token, regexp, syntax);
2238 mbc_remain = create_token_tree (dfa, NULL, NULL, token);
2239 tree = create_tree (dfa, tree, mbc_remain, CONCAT);
2240 if (BE (mbc_remain == NULL || tree == NULL, 0))
2249 case OP_OPEN_SUBEXP:
2250 tree = parse_sub_exp (regexp, preg, token, syntax, nest + 1, err);
2251 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2254 case OP_OPEN_BRACKET:
2255 tree = parse_bracket_exp (regexp, dfa, token, syntax, err);
2256 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2260 if (!BE (dfa->completed_bkref_map & (1 << token->opr.idx), 1))
2265 dfa->used_bkref_map |= 1 << token->opr.idx;
2266 tree = create_token_tree (dfa, NULL, NULL, token);
2267 if (BE (tree == NULL, 0))
2273 dfa->has_mb_node = 1;
2275 case OP_OPEN_DUP_NUM:
2276 if (syntax & RE_CONTEXT_INVALID_DUP)
2282 case OP_DUP_ASTERISK:
2284 case OP_DUP_QUESTION:
2285 if (syntax & RE_CONTEXT_INVALID_OPS)
2290 else if (syntax & RE_CONTEXT_INDEP_OPS)
2292 fetch_token (token, regexp, syntax);
2293 return parse_expression (regexp, preg, token, syntax, nest, err);
2295 /* else fall through */
2296 case OP_CLOSE_SUBEXP:
2297 if ((token->type == OP_CLOSE_SUBEXP) &&
2298 !(syntax & RE_UNMATCHED_RIGHT_PAREN_ORD))
2303 /* else fall through */
2304 case OP_CLOSE_DUP_NUM:
2305 /* We treat it as a normal character. */
2307 /* Then we can these characters as normal characters. */
2308 token->type = CHARACTER;
2309 /* mb_partial and word_char bits should be initialized already
2311 tree = create_token_tree (dfa, NULL, NULL, token);
2312 if (BE (tree == NULL, 0))
2319 if ((token->opr.ctx_type
2320 & (WORD_DELIM | NOT_WORD_DELIM | WORD_FIRST | WORD_LAST))
2321 && dfa->word_ops_used == 0)
2322 init_word_char (dfa);
2323 if (token->opr.ctx_type == WORD_DELIM
2324 || token->opr.ctx_type == NOT_WORD_DELIM)
2326 bin_tree_t *tree_first, *tree_last;
2327 if (token->opr.ctx_type == WORD_DELIM)
2329 token->opr.ctx_type = WORD_FIRST;
2330 tree_first = create_token_tree (dfa, NULL, NULL, token);
2331 token->opr.ctx_type = WORD_LAST;
2335 token->opr.ctx_type = INSIDE_WORD;
2336 tree_first = create_token_tree (dfa, NULL, NULL, token);
2337 token->opr.ctx_type = INSIDE_NOTWORD;
2339 tree_last = create_token_tree (dfa, NULL, NULL, token);
2340 tree = create_tree (dfa, tree_first, tree_last, OP_ALT);
2341 if (BE (tree_first == NULL || tree_last == NULL || tree == NULL, 0))
2349 tree = create_token_tree (dfa, NULL, NULL, token);
2350 if (BE (tree == NULL, 0))
2356 /* We must return here, since ANCHORs can't be followed
2357 by repetition operators.
2358 eg. RE"^*" is invalid or "<ANCHOR(^)><CHAR(*)>",
2359 it must not be "<ANCHOR(^)><REPEAT(*)>". */
2360 fetch_token (token, regexp, syntax);
2363 tree = create_token_tree (dfa, NULL, NULL, token);
2364 if (BE (tree == NULL, 0))
2369 if (dfa->mb_cur_max > 1)
2370 dfa->has_mb_node = 1;
2374 tree = build_charclass_op (dfa, regexp->trans,
2375 (const unsigned char *) "alnum",
2376 (const unsigned char *) "_",
2377 token->type == OP_NOTWORD, err);
2378 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2383 tree = build_charclass_op (dfa, regexp->trans,
2384 (const unsigned char *) "space",
2385 (const unsigned char *) "",
2386 token->type == OP_NOTSPACE, err);
2387 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2397 /* Must not happen? */
2403 fetch_token (token, regexp, syntax);
2405 while (token->type == OP_DUP_ASTERISK || token->type == OP_DUP_PLUS
2406 || token->type == OP_DUP_QUESTION || token->type == OP_OPEN_DUP_NUM)
2408 tree = parse_dup_op (tree, regexp, dfa, token, syntax, err);
2409 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2411 /* In BRE consecutive duplications are not allowed. */
2412 if ((syntax & RE_CONTEXT_INVALID_DUP)
2413 && (token->type == OP_DUP_ASTERISK
2414 || token->type == OP_OPEN_DUP_NUM))
2424 /* This function build the following tree, from regular expression
2432 parse_sub_exp (re_string_t *regexp, regex_t *preg, re_token_t *token,
2433 reg_syntax_t syntax, Idx nest, reg_errcode_t *err)
2435 re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
2438 cur_nsub = preg->re_nsub++;
2440 fetch_token (token, regexp, syntax | RE_CARET_ANCHORS_HERE);
2442 /* The subexpression may be a null string. */
2443 if (token->type == OP_CLOSE_SUBEXP)
2447 tree = parse_reg_exp (regexp, preg, token, syntax, nest, err);
2448 if (BE (*err == REG_NOERROR && token->type != OP_CLOSE_SUBEXP, 0))
2450 if (BE (*err != REG_NOERROR, 0))
2454 if (cur_nsub <= '9' - '1')
2455 dfa->completed_bkref_map |= 1 << cur_nsub;
2457 tree = create_tree (dfa, tree, NULL, SUBEXP);
2458 if (BE (tree == NULL, 0))
2463 tree->token.opr.idx = cur_nsub;
2467 /* This function parse repetition operators like "*", "+", "{1,3}" etc. */
2470 parse_dup_op (bin_tree_t *elem, re_string_t *regexp, re_dfa_t *dfa,
2471 re_token_t *token, reg_syntax_t syntax, reg_errcode_t *err)
2473 bin_tree_t *tree = NULL, *old_tree = NULL;
2474 Idx i, start, end, start_idx = re_string_cur_idx (regexp);
2475 re_token_t start_token = *token;
2477 if (token->type == OP_OPEN_DUP_NUM)
2480 start = fetch_number (regexp, token, syntax);
2481 if (start == REG_MISSING)
2483 if (token->type == CHARACTER && token->opr.c == ',')
2484 start = 0; /* We treat "{,m}" as "{0,m}". */
2487 *err = REG_BADBR; /* <re>{} is invalid. */
2491 if (BE (start != REG_ERROR, 1))
2493 /* We treat "{n}" as "{n,n}". */
2494 end = ((token->type == OP_CLOSE_DUP_NUM) ? start
2495 : ((token->type == CHARACTER && token->opr.c == ',')
2496 ? fetch_number (regexp, token, syntax) : REG_ERROR));
2498 if (BE (start == REG_ERROR || end == REG_ERROR, 0))
2500 /* Invalid sequence. */
2501 if (BE (!(syntax & RE_INVALID_INTERVAL_ORD), 0))
2503 if (token->type == END_OF_RE)
2511 /* If the syntax bit is set, rollback. */
2512 re_string_set_index (regexp, start_idx);
2513 *token = start_token;
2514 token->type = CHARACTER;
2515 /* mb_partial and word_char bits should be already initialized by
2520 if (BE (end != REG_MISSING && start > end, 0))
2522 /* First number greater than second. */
2529 start = (token->type == OP_DUP_PLUS) ? 1 : 0;
2530 end = (token->type == OP_DUP_QUESTION) ? 1 : REG_MISSING;
2533 fetch_token (token, regexp, syntax);
2535 if (BE (elem == NULL, 0))
2537 if (BE (start == 0 && end == 0, 0))
2539 postorder (elem, free_tree, NULL);
2543 /* Extract "<re>{n,m}" to "<re><re>...<re><re>{0,<m-n>}". */
2544 if (BE (start > 0, 0))
2547 for (i = 2; i <= start; ++i)
2549 elem = duplicate_tree (elem, dfa);
2550 tree = create_tree (dfa, tree, elem, CONCAT);
2551 if (BE (elem == NULL || tree == NULL, 0))
2552 goto parse_dup_op_espace;
2558 /* Duplicate ELEM before it is marked optional. */
2559 elem = duplicate_tree (elem, dfa);
2565 if (elem->token.type == SUBEXP)
2566 postorder (elem, mark_opt_subexp, (void *) (long) elem->token.opr.idx);
2568 tree = create_tree (dfa, elem, NULL,
2569 (end == REG_MISSING ? OP_DUP_ASTERISK : OP_ALT));
2570 if (BE (tree == NULL, 0))
2571 goto parse_dup_op_espace;
2573 /* This loop is actually executed only when end != REG_MISSING,
2574 to rewrite <re>{0,n} as (<re>(<re>...<re>?)?)?... We have
2575 already created the start+1-th copy. */
2576 if ((Idx) -1 < 0 || end != REG_MISSING)
2577 for (i = start + 2; i <= end; ++i)
2579 elem = duplicate_tree (elem, dfa);
2580 tree = create_tree (dfa, tree, elem, CONCAT);
2581 if (BE (elem == NULL || tree == NULL, 0))
2582 goto parse_dup_op_espace;
2584 tree = create_tree (dfa, tree, NULL, OP_ALT);
2585 if (BE (tree == NULL, 0))
2586 goto parse_dup_op_espace;
2590 tree = create_tree (dfa, old_tree, tree, CONCAT);
2594 parse_dup_op_espace:
2599 /* Size of the names for collating symbol/equivalence_class/character_class.
2600 I'm not sure, but maybe enough. */
2601 #define BRACKET_NAME_BUF_SIZE 32
2604 /* Local function for parse_bracket_exp only used in case of NOT _LIBC.
2605 Build the range expression which starts from START_ELEM, and ends
2606 at END_ELEM. The result are written to MBCSET and SBCSET.
2607 RANGE_ALLOC is the allocated size of mbcset->range_starts, and
2608 mbcset->range_ends, is a pointer argument sinse we may
2611 static reg_errcode_t
2613 # ifdef RE_ENABLE_I18N
2614 build_range_exp (bitset_t sbcset, re_charset_t *mbcset, Idx *range_alloc,
2615 bracket_elem_t *start_elem, bracket_elem_t *end_elem)
2616 # else /* not RE_ENABLE_I18N */
2617 build_range_exp (bitset_t sbcset, bracket_elem_t *start_elem,
2618 bracket_elem_t *end_elem)
2619 # endif /* not RE_ENABLE_I18N */
2621 unsigned int start_ch, end_ch;
2622 /* Equivalence Classes and Character Classes can't be a range start/end. */
2623 if (BE (start_elem->type == EQUIV_CLASS || start_elem->type == CHAR_CLASS
2624 || end_elem->type == EQUIV_CLASS || end_elem->type == CHAR_CLASS,
2628 /* We can handle no multi character collating elements without libc
2630 if (BE ((start_elem->type == COLL_SYM
2631 && strlen ((char *) start_elem->opr.name) > 1)
2632 || (end_elem->type == COLL_SYM
2633 && strlen ((char *) end_elem->opr.name) > 1), 0))
2634 return REG_ECOLLATE;
2636 # ifdef RE_ENABLE_I18N
2641 wchar_t cmp_buf[6] = {L'\0', L'\0', L'\0', L'\0', L'\0', L'\0'};
2643 start_ch = ((start_elem->type == SB_CHAR) ? start_elem->opr.ch
2644 : ((start_elem->type == COLL_SYM) ? start_elem->opr.name[0]
2646 end_ch = ((end_elem->type == SB_CHAR) ? end_elem->opr.ch
2647 : ((end_elem->type == COLL_SYM) ? end_elem->opr.name[0]
2649 start_wc = ((start_elem->type == SB_CHAR || start_elem->type == COLL_SYM)
2650 ? __btowc (start_ch) : start_elem->opr.wch);
2651 end_wc = ((end_elem->type == SB_CHAR || end_elem->type == COLL_SYM)
2652 ? __btowc (end_ch) : end_elem->opr.wch);
2653 if (start_wc == WEOF || end_wc == WEOF)
2654 return REG_ECOLLATE;
2655 cmp_buf[0] = start_wc;
2656 cmp_buf[4] = end_wc;
2657 if (wcscoll (cmp_buf, cmp_buf + 4) > 0)
2660 /* Got valid collation sequence values, add them as a new entry.
2661 However, for !_LIBC we have no collation elements: if the
2662 character set is single byte, the single byte character set
2663 that we build below suffices. parse_bracket_exp passes
2664 no MBCSET if dfa->mb_cur_max == 1. */
2667 /* Check the space of the arrays. */
2668 if (BE (*range_alloc == mbcset->nranges, 0))
2670 /* There is not enough space, need realloc. */
2671 wchar_t *new_array_start, *new_array_end;
2674 /* +1 in case of mbcset->nranges is 0. */
2675 new_nranges = 2 * mbcset->nranges + 1;
2676 /* Use realloc since mbcset->range_starts and mbcset->range_ends
2677 are NULL if *range_alloc == 0. */
2678 new_array_start = re_realloc (mbcset->range_starts, wchar_t,
2680 new_array_end = re_realloc (mbcset->range_ends, wchar_t,
2683 if (BE (new_array_start == NULL || new_array_end == NULL, 0))
2686 mbcset->range_starts = new_array_start;
2687 mbcset->range_ends = new_array_end;
2688 *range_alloc = new_nranges;
2691 mbcset->range_starts[mbcset->nranges] = start_wc;
2692 mbcset->range_ends[mbcset->nranges++] = end_wc;
2695 /* Build the table for single byte characters. */
2696 for (wc = 0; wc < SBC_MAX; ++wc)
2699 if (wcscoll (cmp_buf, cmp_buf + 2) <= 0
2700 && wcscoll (cmp_buf + 2, cmp_buf + 4) <= 0)
2701 bitset_set (sbcset, wc);
2704 # else /* not RE_ENABLE_I18N */
2707 start_ch = ((start_elem->type == SB_CHAR ) ? start_elem->opr.ch
2708 : ((start_elem->type == COLL_SYM) ? start_elem->opr.name[0]
2710 end_ch = ((end_elem->type == SB_CHAR ) ? end_elem->opr.ch
2711 : ((end_elem->type == COLL_SYM) ? end_elem->opr.name[0]
2713 if (start_ch > end_ch)
2715 /* Build the table for single byte characters. */
2716 for (ch = 0; ch < SBC_MAX; ++ch)
2717 if (start_ch <= ch && ch <= end_ch)
2718 bitset_set (sbcset, ch);
2720 # endif /* not RE_ENABLE_I18N */
2723 #endif /* not _LIBC */
2726 /* Helper function for parse_bracket_exp only used in case of NOT _LIBC..
2727 Build the collating element which is represented by NAME.
2728 The result are written to MBCSET and SBCSET.
2729 COLL_SYM_ALLOC is the allocated size of mbcset->coll_sym, is a
2730 pointer argument since we may update it. */
2732 static reg_errcode_t
2734 build_collating_symbol (bitset_t sbcset,
2735 # ifdef RE_ENABLE_I18N
2736 re_charset_t *mbcset, Idx *coll_sym_alloc,
2738 const unsigned char *name)
2740 size_t name_len = strlen ((const char *) name);
2741 if (BE (name_len != 1, 0))
2742 return REG_ECOLLATE;
2745 bitset_set (sbcset, name[0]);
2749 #endif /* not _LIBC */
2751 /* This function parse bracket expression like "[abc]", "[a-c]",
2755 parse_bracket_exp (re_string_t *regexp, re_dfa_t *dfa, re_token_t *token,
2756 reg_syntax_t syntax, reg_errcode_t *err)
2759 const unsigned char *collseqmb;
2760 const char *collseqwc;
2763 const int32_t *symb_table;
2764 const unsigned char *extra;
2766 /* Local function for parse_bracket_exp used in _LIBC environement.
2767 Seek the collating symbol entry correspondings to NAME.
2768 Return the index of the symbol in the SYMB_TABLE. */
2771 __attribute ((always_inline))
2772 seek_collating_symbol_entry (name, name_len)
2773 const unsigned char *name;
2776 int32_t hash = elem_hash ((const char *) name, name_len);
2777 int32_t elem = hash % table_size;
2778 if (symb_table[2 * elem] != 0)
2780 int32_t second = hash % (table_size - 2) + 1;
2784 /* First compare the hashing value. */
2785 if (symb_table[2 * elem] == hash
2786 /* Compare the length of the name. */
2787 && name_len == extra[symb_table[2 * elem + 1]]
2788 /* Compare the name. */
2789 && memcmp (name, &extra[symb_table[2 * elem + 1] + 1],
2792 /* Yep, this is the entry. */
2799 while (symb_table[2 * elem] != 0);
2804 /* Local function for parse_bracket_exp used in _LIBC environement.
2805 Look up the collation sequence value of BR_ELEM.
2806 Return the value if succeeded, UINT_MAX otherwise. */
2808 auto inline unsigned int
2809 __attribute ((always_inline))
2810 lookup_collation_sequence_value (br_elem)
2811 bracket_elem_t *br_elem;
2813 if (br_elem->type == SB_CHAR)
2816 if (MB_CUR_MAX == 1)
2819 return collseqmb[br_elem->opr.ch];
2822 wint_t wc = __btowc (br_elem->opr.ch);
2823 return __collseq_table_lookup (collseqwc, wc);
2826 else if (br_elem->type == MB_CHAR)
2828 return __collseq_table_lookup (collseqwc, br_elem->opr.wch);
2830 else if (br_elem->type == COLL_SYM)
2832 size_t sym_name_len = strlen ((char *) br_elem->opr.name);
2836 elem = seek_collating_symbol_entry (br_elem->opr.name,
2838 if (symb_table[2 * elem] != 0)
2840 /* We found the entry. */
2841 idx = symb_table[2 * elem + 1];
2842 /* Skip the name of collating element name. */
2843 idx += 1 + extra[idx];
2844 /* Skip the byte sequence of the collating element. */
2845 idx += 1 + extra[idx];
2846 /* Adjust for the alignment. */
2847 idx = (idx + 3) & ~3;
2848 /* Skip the multibyte collation sequence value. */
2849 idx += sizeof (unsigned int);
2850 /* Skip the wide char sequence of the collating element. */
2851 idx += sizeof (unsigned int) *
2852 (1 + *(unsigned int *) (extra + idx));
2853 /* Return the collation sequence value. */
2854 return *(unsigned int *) (extra + idx);
2856 else if (symb_table[2 * elem] == 0 && sym_name_len == 1)
2858 /* No valid character. Match it as a single byte
2860 return collseqmb[br_elem->opr.name[0]];
2863 else if (sym_name_len == 1)
2864 return collseqmb[br_elem->opr.name[0]];
2869 /* Local function for parse_bracket_exp used in _LIBC environement.
2870 Build the range expression which starts from START_ELEM, and ends
2871 at END_ELEM. The result are written to MBCSET and SBCSET.
2872 RANGE_ALLOC is the allocated size of mbcset->range_starts, and
2873 mbcset->range_ends, is a pointer argument sinse we may
2876 auto inline reg_errcode_t
2877 __attribute ((always_inline))
2878 build_range_exp (sbcset, mbcset, range_alloc, start_elem, end_elem)
2879 re_charset_t *mbcset;
2882 bracket_elem_t *start_elem, *end_elem;
2885 uint32_t start_collseq;
2886 uint32_t end_collseq;
2888 /* Equivalence Classes and Character Classes can't be a range
2890 if (BE (start_elem->type == EQUIV_CLASS || start_elem->type == CHAR_CLASS
2891 || end_elem->type == EQUIV_CLASS || end_elem->type == CHAR_CLASS,
2895 start_collseq = lookup_collation_sequence_value (start_elem);
2896 end_collseq = lookup_collation_sequence_value (end_elem);
2897 /* Check start/end collation sequence values. */
2898 if (BE (start_collseq == UINT_MAX || end_collseq == UINT_MAX, 0))
2899 return REG_ECOLLATE;
2900 if (BE ((syntax & RE_NO_EMPTY_RANGES) && start_collseq > end_collseq, 0))
2903 /* Got valid collation sequence values, add them as a new entry.
2904 However, if we have no collation elements, and the character set
2905 is single byte, the single byte character set that we
2906 build below suffices. */
2907 if (nrules > 0 || dfa->mb_cur_max > 1)
2909 /* Check the space of the arrays. */
2910 if (BE (*range_alloc == mbcset->nranges, 0))
2912 /* There is not enough space, need realloc. */
2913 uint32_t *new_array_start;
2914 uint32_t *new_array_end;
2917 /* +1 in case of mbcset->nranges is 0. */
2918 new_nranges = 2 * mbcset->nranges + 1;
2919 new_array_start = re_realloc (mbcset->range_starts, uint32_t,
2921 new_array_end = re_realloc (mbcset->range_ends, uint32_t,
2924 if (BE (new_array_start == NULL || new_array_end == NULL, 0))
2927 mbcset->range_starts = new_array_start;
2928 mbcset->range_ends = new_array_end;
2929 *range_alloc = new_nranges;
2932 mbcset->range_starts[mbcset->nranges] = start_collseq;
2933 mbcset->range_ends[mbcset->nranges++] = end_collseq;
2936 /* Build the table for single byte characters. */
2937 for (ch = 0; ch < SBC_MAX; ch++)
2939 uint32_t ch_collseq;
2941 if (MB_CUR_MAX == 1)
2944 ch_collseq = collseqmb[ch];
2946 ch_collseq = __collseq_table_lookup (collseqwc, __btowc (ch));
2947 if (start_collseq <= ch_collseq && ch_collseq <= end_collseq)
2948 bitset_set (sbcset, ch);
2953 /* Local function for parse_bracket_exp used in _LIBC environement.
2954 Build the collating element which is represented by NAME.
2955 The result are written to MBCSET and SBCSET.
2956 COLL_SYM_ALLOC is the allocated size of mbcset->coll_sym, is a
2957 pointer argument sinse we may update it. */
2959 auto inline reg_errcode_t
2960 __attribute ((always_inline))
2961 build_collating_symbol (sbcset, mbcset, coll_sym_alloc, name)
2962 re_charset_t *mbcset;
2963 Idx *coll_sym_alloc;
2965 const unsigned char *name;
2968 size_t name_len = strlen ((const char *) name);
2971 elem = seek_collating_symbol_entry (name, name_len);
2972 if (symb_table[2 * elem] != 0)
2974 /* We found the entry. */
2975 idx = symb_table[2 * elem + 1];
2976 /* Skip the name of collating element name. */
2977 idx += 1 + extra[idx];
2979 else if (symb_table[2 * elem] == 0 && name_len == 1)
2981 /* No valid character, treat it as a normal
2983 bitset_set (sbcset, name[0]);
2987 return REG_ECOLLATE;
2989 /* Got valid collation sequence, add it as a new entry. */
2990 /* Check the space of the arrays. */
2991 if (BE (*coll_sym_alloc == mbcset->ncoll_syms, 0))
2993 /* Not enough, realloc it. */
2994 /* +1 in case of mbcset->ncoll_syms is 0. */
2995 Idx new_coll_sym_alloc = 2 * mbcset->ncoll_syms + 1;
2996 /* Use realloc since mbcset->coll_syms is NULL
2998 int32_t *new_coll_syms = re_realloc (mbcset->coll_syms, int32_t,
2999 new_coll_sym_alloc);
3000 if (BE (new_coll_syms == NULL, 0))
3002 mbcset->coll_syms = new_coll_syms;
3003 *coll_sym_alloc = new_coll_sym_alloc;
3005 mbcset->coll_syms[mbcset->ncoll_syms++] = idx;
3010 if (BE (name_len != 1, 0))
3011 return REG_ECOLLATE;
3014 bitset_set (sbcset, name[0]);
3021 re_token_t br_token;
3022 re_bitset_ptr_t sbcset;
3023 #ifdef RE_ENABLE_I18N
3024 re_charset_t *mbcset;
3025 Idx coll_sym_alloc = 0, range_alloc = 0, mbchar_alloc = 0;
3026 Idx equiv_class_alloc = 0, char_class_alloc = 0;
3027 #endif /* not RE_ENABLE_I18N */
3028 bool non_match = false;
3029 bin_tree_t *work_tree;
3031 bool first_round = true;
3033 collseqmb = (const unsigned char *)
3034 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQMB);
3035 nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
3041 collseqwc = _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQWC);
3042 table_size = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_SYMB_HASH_SIZEMB);
3043 symb_table = (const int32_t *) _NL_CURRENT (LC_COLLATE,
3044 _NL_COLLATE_SYMB_TABLEMB);
3045 extra = (const unsigned char *) _NL_CURRENT (LC_COLLATE,
3046 _NL_COLLATE_SYMB_EXTRAMB);
3049 sbcset = (re_bitset_ptr_t) calloc (sizeof (bitset_t), 1);
3050 #ifdef RE_ENABLE_I18N
3051 mbcset = (re_charset_t *) calloc (sizeof (re_charset_t), 1);
3052 #endif /* RE_ENABLE_I18N */
3053 #ifdef RE_ENABLE_I18N
3054 if (BE (sbcset == NULL || mbcset == NULL, 0))
3056 if (BE (sbcset == NULL, 0))
3057 #endif /* RE_ENABLE_I18N */
3063 token_len = peek_token_bracket (token, regexp, syntax);
3064 if (BE (token->type == END_OF_RE, 0))
3067 goto parse_bracket_exp_free_return;
3069 if (token->type == OP_NON_MATCH_LIST)
3071 #ifdef RE_ENABLE_I18N
3072 mbcset->non_match = 1;
3073 #endif /* not RE_ENABLE_I18N */
3075 if (syntax & RE_HAT_LISTS_NOT_NEWLINE)
3076 bitset_set (sbcset, '\n');
3077 re_string_skip_bytes (regexp, token_len); /* Skip a token. */
3078 token_len = peek_token_bracket (token, regexp, syntax);
3079 if (BE (token->type == END_OF_RE, 0))
3082 goto parse_bracket_exp_free_return;
3086 /* We treat the first ']' as a normal character. */
3087 if (token->type == OP_CLOSE_BRACKET)
3088 token->type = CHARACTER;
3092 bracket_elem_t start_elem, end_elem;
3093 unsigned char start_name_buf[BRACKET_NAME_BUF_SIZE];
3094 unsigned char end_name_buf[BRACKET_NAME_BUF_SIZE];
3097 bool is_range_exp = false;
3100 start_elem.opr.name = start_name_buf;
3101 ret = parse_bracket_element (&start_elem, regexp, token, token_len, dfa,
3102 syntax, first_round);
3103 if (BE (ret != REG_NOERROR, 0))
3106 goto parse_bracket_exp_free_return;
3108 first_round = false;
3110 /* Get information about the next token. We need it in any case. */
3111 token_len = peek_token_bracket (token, regexp, syntax);
3113 /* Do not check for ranges if we know they are not allowed. */
3114 if (start_elem.type != CHAR_CLASS && start_elem.type != EQUIV_CLASS)
3116 if (BE (token->type == END_OF_RE, 0))
3119 goto parse_bracket_exp_free_return;
3121 if (token->type == OP_CHARSET_RANGE)
3123 re_string_skip_bytes (regexp, token_len); /* Skip '-'. */
3124 token_len2 = peek_token_bracket (&token2, regexp, syntax);
3125 if (BE (token2.type == END_OF_RE, 0))
3128 goto parse_bracket_exp_free_return;
3130 if (token2.type == OP_CLOSE_BRACKET)
3132 /* We treat the last '-' as a normal character. */
3133 re_string_skip_bytes (regexp, -token_len);
3134 token->type = CHARACTER;
3137 is_range_exp = true;
3141 if (is_range_exp == true)
3143 end_elem.opr.name = end_name_buf;
3144 ret = parse_bracket_element (&end_elem, regexp, &token2, token_len2,
3146 if (BE (ret != REG_NOERROR, 0))
3149 goto parse_bracket_exp_free_return;
3152 token_len = peek_token_bracket (token, regexp, syntax);
3155 *err = build_range_exp (sbcset, mbcset, &range_alloc,
3156 &start_elem, &end_elem);
3158 # ifdef RE_ENABLE_I18N
3159 *err = build_range_exp (sbcset,
3160 dfa->mb_cur_max > 1 ? mbcset : NULL,
3161 &range_alloc, &start_elem, &end_elem);
3163 *err = build_range_exp (sbcset, &start_elem, &end_elem);
3165 #endif /* RE_ENABLE_I18N */
3166 if (BE (*err != REG_NOERROR, 0))
3167 goto parse_bracket_exp_free_return;
3171 switch (start_elem.type)
3174 bitset_set (sbcset, start_elem.opr.ch);
3176 #ifdef RE_ENABLE_I18N
3178 /* Check whether the array has enough space. */
3179 if (BE (mbchar_alloc == mbcset->nmbchars, 0))
3181 wchar_t *new_mbchars;
3182 /* Not enough, realloc it. */
3183 /* +1 in case of mbcset->nmbchars is 0. */
3184 mbchar_alloc = 2 * mbcset->nmbchars + 1;
3185 /* Use realloc since array is NULL if *alloc == 0. */
3186 new_mbchars = re_realloc (mbcset->mbchars, wchar_t,
3188 if (BE (new_mbchars == NULL, 0))
3189 goto parse_bracket_exp_espace;
3190 mbcset->mbchars = new_mbchars;
3192 mbcset->mbchars[mbcset->nmbchars++] = start_elem.opr.wch;
3194 #endif /* RE_ENABLE_I18N */
3196 *err = build_equiv_class (sbcset,
3197 #ifdef RE_ENABLE_I18N
3198 mbcset, &equiv_class_alloc,
3199 #endif /* RE_ENABLE_I18N */
3200 start_elem.opr.name);
3201 if (BE (*err != REG_NOERROR, 0))
3202 goto parse_bracket_exp_free_return;
3205 *err = build_collating_symbol (sbcset,
3206 #ifdef RE_ENABLE_I18N
3207 mbcset, &coll_sym_alloc,
3208 #endif /* RE_ENABLE_I18N */
3209 start_elem.opr.name);
3210 if (BE (*err != REG_NOERROR, 0))
3211 goto parse_bracket_exp_free_return;
3214 *err = build_charclass (regexp->trans, sbcset,
3215 #ifdef RE_ENABLE_I18N
3216 mbcset, &char_class_alloc,
3217 #endif /* RE_ENABLE_I18N */
3218 start_elem.opr.name, syntax);
3219 if (BE (*err != REG_NOERROR, 0))
3220 goto parse_bracket_exp_free_return;
3227 if (BE (token->type == END_OF_RE, 0))
3230 goto parse_bracket_exp_free_return;
3232 if (token->type == OP_CLOSE_BRACKET)
3236 re_string_skip_bytes (regexp, token_len); /* Skip a token. */
3238 /* If it is non-matching list. */
3240 bitset_not (sbcset);
3242 #ifdef RE_ENABLE_I18N
3243 /* Ensure only single byte characters are set. */
3244 if (dfa->mb_cur_max > 1)
3245 bitset_mask (sbcset, dfa->sb_char);
3247 if (mbcset->nmbchars || mbcset->ncoll_syms || mbcset->nequiv_classes
3248 || mbcset->nranges || (dfa->mb_cur_max > 1 && (mbcset->nchar_classes
3249 || mbcset->non_match)))
3251 bin_tree_t *mbc_tree;
3253 /* Build a tree for complex bracket. */
3254 dfa->has_mb_node = 1;
3255 br_token.type = COMPLEX_BRACKET;
3256 br_token.opr.mbcset = mbcset;
3257 mbc_tree = create_token_tree (dfa, NULL, NULL, &br_token);
3258 if (BE (mbc_tree == NULL, 0))
3259 goto parse_bracket_exp_espace;
3260 for (sbc_idx = 0; sbc_idx < BITSET_WORDS; ++sbc_idx)
3261 if (sbcset[sbc_idx])
3263 /* If there are no bits set in sbcset, there is no point
3264 of having both SIMPLE_BRACKET and COMPLEX_BRACKET. */
3265 if (sbc_idx < BITSET_WORDS)
3267 /* Build a tree for simple bracket. */
3268 br_token.type = SIMPLE_BRACKET;
3269 br_token.opr.sbcset = sbcset;
3270 work_tree = create_token_tree (dfa, NULL, NULL, &br_token);
3271 if (BE (work_tree == NULL, 0))
3272 goto parse_bracket_exp_espace;
3274 /* Then join them by ALT node. */
3275 work_tree = create_tree (dfa, work_tree, mbc_tree, OP_ALT);
3276 if (BE (work_tree == NULL, 0))
3277 goto parse_bracket_exp_espace;
3282 work_tree = mbc_tree;
3286 #endif /* not RE_ENABLE_I18N */
3288 #ifdef RE_ENABLE_I18N
3289 free_charset (mbcset);
3291 /* Build a tree for simple bracket. */
3292 br_token.type = SIMPLE_BRACKET;
3293 br_token.opr.sbcset = sbcset;
3294 work_tree = create_token_tree (dfa, NULL, NULL, &br_token);
3295 if (BE (work_tree == NULL, 0))
3296 goto parse_bracket_exp_espace;
3300 parse_bracket_exp_espace:
3302 parse_bracket_exp_free_return:
3304 #ifdef RE_ENABLE_I18N
3305 free_charset (mbcset);
3306 #endif /* RE_ENABLE_I18N */
3310 /* Parse an element in the bracket expression. */
3312 static reg_errcode_t
3313 parse_bracket_element (bracket_elem_t *elem, re_string_t *regexp,
3314 re_token_t *token, int token_len, re_dfa_t *dfa,
3315 reg_syntax_t syntax, bool accept_hyphen)
3317 #ifdef RE_ENABLE_I18N
3319 cur_char_size = re_string_char_size_at (regexp, re_string_cur_idx (regexp));
3320 if (cur_char_size > 1)
3322 elem->type = MB_CHAR;
3323 elem->opr.wch = re_string_wchar_at (regexp, re_string_cur_idx (regexp));
3324 re_string_skip_bytes (regexp, cur_char_size);
3327 #endif /* RE_ENABLE_I18N */
3328 re_string_skip_bytes (regexp, token_len); /* Skip a token. */
3329 if (token->type == OP_OPEN_COLL_ELEM || token->type == OP_OPEN_CHAR_CLASS
3330 || token->type == OP_OPEN_EQUIV_CLASS)
3331 return parse_bracket_symbol (elem, regexp, token);
3332 if (BE (token->type == OP_CHARSET_RANGE, 0) && !accept_hyphen)
3334 /* A '-' must only appear as anything but a range indicator before
3335 the closing bracket. Everything else is an error. */
3337 (void) peek_token_bracket (&token2, regexp, syntax);
3338 if (token2.type != OP_CLOSE_BRACKET)
3339 /* The actual error value is not standardized since this whole
3340 case is undefined. But ERANGE makes good sense. */
3343 elem->type = SB_CHAR;
3344 elem->opr.ch = token->opr.c;
3348 /* Parse a bracket symbol in the bracket expression. Bracket symbols are
3349 such as [:<character_class>:], [.<collating_element>.], and
3350 [=<equivalent_class>=]. */
3352 static reg_errcode_t
3353 parse_bracket_symbol (bracket_elem_t *elem, re_string_t *regexp,
3356 unsigned char ch, delim = token->opr.c;
3358 if (re_string_eoi(regexp))
3362 if (i >= BRACKET_NAME_BUF_SIZE)
3364 if (token->type == OP_OPEN_CHAR_CLASS)
3365 ch = re_string_fetch_byte_case (regexp);
3367 ch = re_string_fetch_byte (regexp);
3368 if (re_string_eoi(regexp))
3370 if (ch == delim && re_string_peek_byte (regexp, 0) == ']')
3372 elem->opr.name[i] = ch;
3374 re_string_skip_bytes (regexp, 1);
3375 elem->opr.name[i] = '\0';
3376 switch (token->type)
3378 case OP_OPEN_COLL_ELEM:
3379 elem->type = COLL_SYM;
3381 case OP_OPEN_EQUIV_CLASS:
3382 elem->type = EQUIV_CLASS;
3384 case OP_OPEN_CHAR_CLASS:
3385 elem->type = CHAR_CLASS;
3393 /* Helper function for parse_bracket_exp.
3394 Build the equivalence class which is represented by NAME.
3395 The result are written to MBCSET and SBCSET.
3396 EQUIV_CLASS_ALLOC is the allocated size of mbcset->equiv_classes,
3397 is a pointer argument sinse we may update it. */
3399 static reg_errcode_t
3400 #ifdef RE_ENABLE_I18N
3401 build_equiv_class (bitset_t sbcset, re_charset_t *mbcset,
3402 Idx *equiv_class_alloc, const unsigned char *name)
3403 #else /* not RE_ENABLE_I18N */
3404 build_equiv_class (bitset_t sbcset, const unsigned char *name)
3405 #endif /* not RE_ENABLE_I18N */
3408 uint32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
3411 const int32_t *table, *indirect;
3412 const unsigned char *weights, *extra, *cp;
3413 unsigned char char_buf[2];
3417 /* This #include defines a local function! */
3418 # include <locale/weight.h>
3419 /* Calculate the index for equivalence class. */
3421 table = (const int32_t *) _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
3422 weights = (const unsigned char *) _NL_CURRENT (LC_COLLATE,
3423 _NL_COLLATE_WEIGHTMB);
3424 extra = (const unsigned char *) _NL_CURRENT (LC_COLLATE,
3425 _NL_COLLATE_EXTRAMB);
3426 indirect = (const int32_t *) _NL_CURRENT (LC_COLLATE,
3427 _NL_COLLATE_INDIRECTMB);
3428 idx1 = findidx (&cp);
3429 if (BE (idx1 == 0 || cp < name + strlen ((const char *) name), 0))
3430 /* This isn't a valid character. */
3431 return REG_ECOLLATE;
3433 /* Build single byte matcing table for this equivalence class. */
3434 char_buf[1] = (unsigned char) '\0';
3435 len = weights[idx1];
3436 for (ch = 0; ch < SBC_MAX; ++ch)
3440 idx2 = findidx (&cp);
3445 /* This isn't a valid character. */
3447 if (len == weights[idx2])
3450 while (cnt <= len &&
3451 weights[idx1 + 1 + cnt] == weights[idx2 + 1 + cnt])
3455 bitset_set (sbcset, ch);
3458 /* Check whether the array has enough space. */
3459 if (BE (*equiv_class_alloc == mbcset->nequiv_classes, 0))
3461 /* Not enough, realloc it. */
3462 /* +1 in case of mbcset->nequiv_classes is 0. */
3463 Idx new_equiv_class_alloc = 2 * mbcset->nequiv_classes + 1;
3464 /* Use realloc since the array is NULL if *alloc == 0. */
3465 int32_t *new_equiv_classes = re_realloc (mbcset->equiv_classes,
3467 new_equiv_class_alloc);
3468 if (BE (new_equiv_classes == NULL, 0))
3470 mbcset->equiv_classes = new_equiv_classes;
3471 *equiv_class_alloc = new_equiv_class_alloc;
3473 mbcset->equiv_classes[mbcset->nequiv_classes++] = idx1;
3478 if (BE (strlen ((const char *) name) != 1, 0))
3479 return REG_ECOLLATE;
3480 bitset_set (sbcset, *name);
3485 /* Helper function for parse_bracket_exp.
3486 Build the character class which is represented by NAME.
3487 The result are written to MBCSET and SBCSET.
3488 CHAR_CLASS_ALLOC is the allocated size of mbcset->char_classes,
3489 is a pointer argument sinse we may update it. */
3491 static reg_errcode_t
3492 #ifdef RE_ENABLE_I18N
3493 build_charclass (RE_TRANSLATE_TYPE trans, bitset_t sbcset,
3494 re_charset_t *mbcset, Idx *char_class_alloc,
3495 const unsigned char *class_name, reg_syntax_t syntax)
3496 #else /* not RE_ENABLE_I18N */
3497 build_charclass (RE_TRANSLATE_TYPE trans, bitset_t sbcset,
3498 const unsigned char *class_name, reg_syntax_t syntax)
3499 #endif /* not RE_ENABLE_I18N */
3502 const char *name = (const char *) class_name;
3504 /* In case of REG_ICASE "upper" and "lower" match the both of
3505 upper and lower cases. */
3506 if ((syntax & RE_ICASE)
3507 && (strcmp (name, "upper") == 0 || strcmp (name, "lower") == 0))
3510 #ifdef RE_ENABLE_I18N
3511 /* Check the space of the arrays. */
3512 if (BE (*char_class_alloc == mbcset->nchar_classes, 0))
3514 /* Not enough, realloc it. */
3515 /* +1 in case of mbcset->nchar_classes is 0. */
3516 Idx new_char_class_alloc = 2 * mbcset->nchar_classes + 1;
3517 /* Use realloc since array is NULL if *alloc == 0. */
3518 wctype_t *new_char_classes = re_realloc (mbcset->char_classes, wctype_t,
3519 new_char_class_alloc);
3520 if (BE (new_char_classes == NULL, 0))
3522 mbcset->char_classes = new_char_classes;
3523 *char_class_alloc = new_char_class_alloc;
3525 mbcset->char_classes[mbcset->nchar_classes++] = __wctype (name);
3526 #endif /* RE_ENABLE_I18N */
3528 #define BUILD_CHARCLASS_LOOP(ctype_func) \
3530 if (BE (trans != NULL, 0)) \
3532 for (i = 0; i < SBC_MAX; ++i) \
3533 if (ctype_func (i)) \
3534 bitset_set (sbcset, trans[i]); \
3538 for (i = 0; i < SBC_MAX; ++i) \
3539 if (ctype_func (i)) \
3540 bitset_set (sbcset, i); \
3544 if (strcmp (name, "alnum") == 0)
3545 BUILD_CHARCLASS_LOOP (isalnum);
3546 else if (strcmp (name, "cntrl") == 0)
3547 BUILD_CHARCLASS_LOOP (iscntrl);
3548 else if (strcmp (name, "lower") == 0)
3549 BUILD_CHARCLASS_LOOP (islower);
3550 else if (strcmp (name, "space") == 0)
3551 BUILD_CHARCLASS_LOOP (isspace);
3552 else if (strcmp (name, "alpha") == 0)
3553 BUILD_CHARCLASS_LOOP (isalpha);
3554 else if (strcmp (name, "digit") == 0)
3555 BUILD_CHARCLASS_LOOP (isdigit);
3556 else if (strcmp (name, "print") == 0)
3557 BUILD_CHARCLASS_LOOP (isprint);
3558 else if (strcmp (name, "upper") == 0)
3559 BUILD_CHARCLASS_LOOP (isupper);
3560 else if (strcmp (name, "blank") == 0)
3561 BUILD_CHARCLASS_LOOP (isblank);
3562 else if (strcmp (name, "graph") == 0)
3563 BUILD_CHARCLASS_LOOP (isgraph);
3564 else if (strcmp (name, "punct") == 0)
3565 BUILD_CHARCLASS_LOOP (ispunct);
3566 else if (strcmp (name, "xdigit") == 0)
3567 BUILD_CHARCLASS_LOOP (isxdigit);
3575 build_charclass_op (re_dfa_t *dfa, RE_TRANSLATE_TYPE trans,
3576 const unsigned char *class_name,
3577 const unsigned char *extra, bool non_match,
3580 re_bitset_ptr_t sbcset;
3581 #ifdef RE_ENABLE_I18N
3582 re_charset_t *mbcset;
3584 #endif /* not RE_ENABLE_I18N */
3586 re_token_t br_token;
3589 sbcset = (re_bitset_ptr_t) calloc (sizeof (bitset_t), 1);
3590 #ifdef RE_ENABLE_I18N
3591 mbcset = (re_charset_t *) calloc (sizeof (re_charset_t), 1);
3592 #endif /* RE_ENABLE_I18N */
3594 #ifdef RE_ENABLE_I18N
3595 if (BE (sbcset == NULL || mbcset == NULL, 0))
3596 #else /* not RE_ENABLE_I18N */
3597 if (BE (sbcset == NULL, 0))
3598 #endif /* not RE_ENABLE_I18N */
3606 #ifdef RE_ENABLE_I18N
3607 mbcset->non_match = 1;
3608 #endif /* not RE_ENABLE_I18N */
3611 /* We don't care the syntax in this case. */
3612 ret = build_charclass (trans, sbcset,
3613 #ifdef RE_ENABLE_I18N
3615 #endif /* RE_ENABLE_I18N */
3618 if (BE (ret != REG_NOERROR, 0))
3621 #ifdef RE_ENABLE_I18N
3622 free_charset (mbcset);
3623 #endif /* RE_ENABLE_I18N */
3627 /* \w match '_' also. */
3628 for (; *extra; extra++)
3629 bitset_set (sbcset, *extra);
3631 /* If it is non-matching list. */
3633 bitset_not (sbcset);
3635 #ifdef RE_ENABLE_I18N
3636 /* Ensure only single byte characters are set. */
3637 if (dfa->mb_cur_max > 1)
3638 bitset_mask (sbcset, dfa->sb_char);
3641 /* Build a tree for simple bracket. */
3642 br_token.type = SIMPLE_BRACKET;
3643 br_token.opr.sbcset = sbcset;
3644 tree = create_token_tree (dfa, NULL, NULL, &br_token);
3645 if (BE (tree == NULL, 0))
3646 goto build_word_op_espace;
3648 #ifdef RE_ENABLE_I18N
3649 if (dfa->mb_cur_max > 1)
3651 bin_tree_t *mbc_tree;
3652 /* Build a tree for complex bracket. */
3653 br_token.type = COMPLEX_BRACKET;
3654 br_token.opr.mbcset = mbcset;
3655 dfa->has_mb_node = 1;
3656 mbc_tree = create_token_tree (dfa, NULL, NULL, &br_token);
3657 if (BE (mbc_tree == NULL, 0))
3658 goto build_word_op_espace;
3659 /* Then join them by ALT node. */
3660 tree = create_tree (dfa, tree, mbc_tree, OP_ALT);
3661 if (BE (mbc_tree != NULL, 1))
3666 free_charset (mbcset);
3669 #else /* not RE_ENABLE_I18N */
3671 #endif /* not RE_ENABLE_I18N */
3673 build_word_op_espace:
3675 #ifdef RE_ENABLE_I18N
3676 free_charset (mbcset);
3677 #endif /* RE_ENABLE_I18N */
3682 /* This is intended for the expressions like "a{1,3}".
3683 Fetch a number from `input', and return the number.
3684 Return REG_MISSING if the number field is empty like "{,1}".
3685 Return REG_ERROR if an error occurred. */
3688 fetch_number (re_string_t *input, re_token_t *token, reg_syntax_t syntax)
3690 Idx num = REG_MISSING;
3694 fetch_token (token, input, syntax);
3696 if (BE (token->type == END_OF_RE, 0))
3698 if (token->type == OP_CLOSE_DUP_NUM || c == ',')
3700 num = ((token->type != CHARACTER || c < '0' || '9' < c
3701 || num == REG_ERROR)
3703 : ((num == REG_MISSING) ? c - '0' : num * 10 + c - '0'));
3704 num = (num > RE_DUP_MAX) ? REG_ERROR : num;
3709 #ifdef RE_ENABLE_I18N
3711 free_charset (re_charset_t *cset)
3713 re_free (cset->mbchars);
3715 re_free (cset->coll_syms);
3716 re_free (cset->equiv_classes);
3717 re_free (cset->range_starts);
3718 re_free (cset->range_ends);
3720 re_free (cset->char_classes);
3723 #endif /* RE_ENABLE_I18N */
3725 /* Functions for binary tree operation. */
3727 /* Create a tree node. */
3730 create_tree (re_dfa_t *dfa, bin_tree_t *left, bin_tree_t *right,
3731 re_token_type_t type)
3735 return create_token_tree (dfa, left, right, &t);
3739 create_token_tree (re_dfa_t *dfa, bin_tree_t *left, bin_tree_t *right,
3740 const re_token_t *token)
3743 if (BE (dfa->str_tree_storage_idx == BIN_TREE_STORAGE_SIZE, 0))
3745 bin_tree_storage_t *storage = re_malloc (bin_tree_storage_t, 1);
3747 if (storage == NULL)
3749 storage->next = dfa->str_tree_storage;
3750 dfa->str_tree_storage = storage;
3751 dfa->str_tree_storage_idx = 0;
3753 tree = &dfa->str_tree_storage->data[dfa->str_tree_storage_idx++];
3755 tree->parent = NULL;
3757 tree->right = right;
3758 tree->token = *token;
3759 tree->token.duplicated = 0;
3760 tree->token.opt_subexp = 0;
3763 tree->node_idx = REG_MISSING;
3766 left->parent = tree;
3768 right->parent = tree;
3772 /* Mark the tree SRC as an optional subexpression.
3773 To be called from preorder or postorder. */
3775 static reg_errcode_t
3776 mark_opt_subexp (void *extra, bin_tree_t *node)
3778 Idx idx = (Idx) (long) extra;
3779 if (node->token.type == SUBEXP && node->token.opr.idx == idx)
3780 node->token.opt_subexp = 1;
3785 /* Free the allocated memory inside NODE. */
3788 free_token (re_token_t *node)
3790 #ifdef RE_ENABLE_I18N
3791 if (node->type == COMPLEX_BRACKET && node->duplicated == 0)
3792 free_charset (node->opr.mbcset);
3794 #endif /* RE_ENABLE_I18N */
3795 if (node->type == SIMPLE_BRACKET && node->duplicated == 0)
3796 re_free (node->opr.sbcset);
3799 /* Worker function for tree walking. Free the allocated memory inside NODE
3800 and its children. */
3802 static reg_errcode_t
3803 free_tree (void *extra, bin_tree_t *node)
3805 free_token (&node->token);
3810 /* Duplicate the node SRC, and return new node. This is a preorder
3811 visit similar to the one implemented by the generic visitor, but
3812 we need more infrastructure to maintain two parallel trees --- so,
3813 it's easier to duplicate. */
3816 duplicate_tree (const bin_tree_t *root, re_dfa_t *dfa)
3818 const bin_tree_t *node;
3819 bin_tree_t *dup_root;
3820 bin_tree_t **p_new = &dup_root, *dup_node = root->parent;
3822 for (node = root; ; )
3824 /* Create a new tree and link it back to the current parent. */
3825 *p_new = create_token_tree (dfa, NULL, NULL, &node->token);
3828 (*p_new)->parent = dup_node;
3829 (*p_new)->token.duplicated = 1;
3832 /* Go to the left node, or up and to the right. */
3836 p_new = &dup_node->left;
3840 const bin_tree_t *prev = NULL;
3841 while (node->right == prev || node->right == NULL)
3844 node = node->parent;
3845 dup_node = dup_node->parent;
3850 p_new = &dup_node->right;