Fixed and unified pthread_once.
[glibc.git] / posix / regcomp.c
blob921d0f49a31345ab6042c00e8689de4249e99964
1 /* Extended regular expression matching and search library.
2 Copyright (C) 2002-2014 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
4 Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>.
6 The GNU C Library is free software; you can redistribute it and/or
7 modify it under the terms of the GNU Lesser General Public
8 License as published by the Free Software Foundation; either
9 version 2.1 of the License, or (at your option) any later version.
11 The GNU C Library is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 Lesser General Public License for more details.
16 You should have received a copy of the GNU Lesser General Public
17 License along with the GNU C Library; if not, see
18 <http://www.gnu.org/licenses/>. */
20 #include <stdint.h>
22 static reg_errcode_t re_compile_internal (regex_t *preg, const char * pattern,
23 size_t length, reg_syntax_t syntax);
24 static void re_compile_fastmap_iter (regex_t *bufp,
25 const re_dfastate_t *init_state,
26 char *fastmap);
27 static reg_errcode_t init_dfa (re_dfa_t *dfa, size_t pat_len);
28 #ifdef RE_ENABLE_I18N
29 static void free_charset (re_charset_t *cset);
30 #endif /* RE_ENABLE_I18N */
31 static void free_workarea_compile (regex_t *preg);
32 static reg_errcode_t create_initial_state (re_dfa_t *dfa);
33 #ifdef RE_ENABLE_I18N
34 static void optimize_utf8 (re_dfa_t *dfa);
35 #endif
36 static reg_errcode_t analyze (regex_t *preg);
37 static reg_errcode_t preorder (bin_tree_t *root,
38 reg_errcode_t (fn (void *, bin_tree_t *)),
39 void *extra);
40 static reg_errcode_t postorder (bin_tree_t *root,
41 reg_errcode_t (fn (void *, bin_tree_t *)),
42 void *extra);
43 static reg_errcode_t optimize_subexps (void *extra, bin_tree_t *node);
44 static reg_errcode_t lower_subexps (void *extra, bin_tree_t *node);
45 static bin_tree_t *lower_subexp (reg_errcode_t *err, regex_t *preg,
46 bin_tree_t *node);
47 static reg_errcode_t calc_first (void *extra, bin_tree_t *node);
48 static reg_errcode_t calc_next (void *extra, bin_tree_t *node);
49 static reg_errcode_t link_nfa_nodes (void *extra, bin_tree_t *node);
50 static int duplicate_node (re_dfa_t *dfa, int org_idx, unsigned int constraint);
51 static int search_duplicated_node (const re_dfa_t *dfa, int org_node,
52 unsigned int constraint);
53 static reg_errcode_t calc_eclosure (re_dfa_t *dfa);
54 static reg_errcode_t calc_eclosure_iter (re_node_set *new_set, re_dfa_t *dfa,
55 int node, int root);
56 static reg_errcode_t calc_inveclosure (re_dfa_t *dfa);
57 static int fetch_number (re_string_t *input, re_token_t *token,
58 reg_syntax_t syntax);
59 static int peek_token (re_token_t *token, re_string_t *input,
60 reg_syntax_t syntax) internal_function;
61 static bin_tree_t *parse (re_string_t *regexp, regex_t *preg,
62 reg_syntax_t syntax, reg_errcode_t *err);
63 static bin_tree_t *parse_reg_exp (re_string_t *regexp, regex_t *preg,
64 re_token_t *token, reg_syntax_t syntax,
65 int nest, reg_errcode_t *err);
66 static bin_tree_t *parse_branch (re_string_t *regexp, regex_t *preg,
67 re_token_t *token, reg_syntax_t syntax,
68 int nest, reg_errcode_t *err);
69 static bin_tree_t *parse_expression (re_string_t *regexp, regex_t *preg,
70 re_token_t *token, reg_syntax_t syntax,
71 int nest, reg_errcode_t *err);
72 static bin_tree_t *parse_sub_exp (re_string_t *regexp, regex_t *preg,
73 re_token_t *token, reg_syntax_t syntax,
74 int nest, reg_errcode_t *err);
75 static bin_tree_t *parse_dup_op (bin_tree_t *dup_elem, re_string_t *regexp,
76 re_dfa_t *dfa, re_token_t *token,
77 reg_syntax_t syntax, reg_errcode_t *err);
78 static bin_tree_t *parse_bracket_exp (re_string_t *regexp, re_dfa_t *dfa,
79 re_token_t *token, reg_syntax_t syntax,
80 reg_errcode_t *err);
81 static reg_errcode_t parse_bracket_element (bracket_elem_t *elem,
82 re_string_t *regexp,
83 re_token_t *token, int token_len,
84 re_dfa_t *dfa,
85 reg_syntax_t syntax,
86 int accept_hyphen);
87 static reg_errcode_t parse_bracket_symbol (bracket_elem_t *elem,
88 re_string_t *regexp,
89 re_token_t *token);
90 #ifdef RE_ENABLE_I18N
91 static reg_errcode_t build_equiv_class (bitset_t sbcset,
92 re_charset_t *mbcset,
93 int *equiv_class_alloc,
94 const unsigned char *name);
95 static reg_errcode_t build_charclass (RE_TRANSLATE_TYPE trans,
96 bitset_t sbcset,
97 re_charset_t *mbcset,
98 int *char_class_alloc,
99 const unsigned char *class_name,
100 reg_syntax_t syntax);
101 #else /* not RE_ENABLE_I18N */
102 static reg_errcode_t build_equiv_class (bitset_t sbcset,
103 const unsigned char *name);
104 static reg_errcode_t build_charclass (RE_TRANSLATE_TYPE trans,
105 bitset_t sbcset,
106 const unsigned char *class_name,
107 reg_syntax_t syntax);
108 #endif /* not RE_ENABLE_I18N */
109 static bin_tree_t *build_charclass_op (re_dfa_t *dfa,
110 RE_TRANSLATE_TYPE trans,
111 const unsigned char *class_name,
112 const unsigned char *extra,
113 int non_match, reg_errcode_t *err);
114 static bin_tree_t *create_tree (re_dfa_t *dfa,
115 bin_tree_t *left, bin_tree_t *right,
116 re_token_type_t type);
117 static bin_tree_t *create_token_tree (re_dfa_t *dfa,
118 bin_tree_t *left, bin_tree_t *right,
119 const re_token_t *token);
120 static bin_tree_t *duplicate_tree (const bin_tree_t *src, re_dfa_t *dfa);
121 static void free_token (re_token_t *node);
122 static reg_errcode_t free_tree (void *extra, bin_tree_t *node);
123 static reg_errcode_t mark_opt_subexp (void *extra, bin_tree_t *node);
125 /* This table gives an error message for each of the error codes listed
126 in regex.h. Obviously the order here has to be same as there.
127 POSIX doesn't require that we do anything for REG_NOERROR,
128 but why not be nice? */
130 const char __re_error_msgid[] attribute_hidden =
132 #define REG_NOERROR_IDX 0
133 gettext_noop ("Success") /* REG_NOERROR */
134 "\0"
135 #define REG_NOMATCH_IDX (REG_NOERROR_IDX + sizeof "Success")
136 gettext_noop ("No match") /* REG_NOMATCH */
137 "\0"
138 #define REG_BADPAT_IDX (REG_NOMATCH_IDX + sizeof "No match")
139 gettext_noop ("Invalid regular expression") /* REG_BADPAT */
140 "\0"
141 #define REG_ECOLLATE_IDX (REG_BADPAT_IDX + sizeof "Invalid regular expression")
142 gettext_noop ("Invalid collation character") /* REG_ECOLLATE */
143 "\0"
144 #define REG_ECTYPE_IDX (REG_ECOLLATE_IDX + sizeof "Invalid collation character")
145 gettext_noop ("Invalid character class name") /* REG_ECTYPE */
146 "\0"
147 #define REG_EESCAPE_IDX (REG_ECTYPE_IDX + sizeof "Invalid character class name")
148 gettext_noop ("Trailing backslash") /* REG_EESCAPE */
149 "\0"
150 #define REG_ESUBREG_IDX (REG_EESCAPE_IDX + sizeof "Trailing backslash")
151 gettext_noop ("Invalid back reference") /* REG_ESUBREG */
152 "\0"
153 #define REG_EBRACK_IDX (REG_ESUBREG_IDX + sizeof "Invalid back reference")
154 gettext_noop ("Unmatched [ or [^") /* REG_EBRACK */
155 "\0"
156 #define REG_EPAREN_IDX (REG_EBRACK_IDX + sizeof "Unmatched [ or [^")
157 gettext_noop ("Unmatched ( or \\(") /* REG_EPAREN */
158 "\0"
159 #define REG_EBRACE_IDX (REG_EPAREN_IDX + sizeof "Unmatched ( or \\(")
160 gettext_noop ("Unmatched \\{") /* REG_EBRACE */
161 "\0"
162 #define REG_BADBR_IDX (REG_EBRACE_IDX + sizeof "Unmatched \\{")
163 gettext_noop ("Invalid content of \\{\\}") /* REG_BADBR */
164 "\0"
165 #define REG_ERANGE_IDX (REG_BADBR_IDX + sizeof "Invalid content of \\{\\}")
166 gettext_noop ("Invalid range end") /* REG_ERANGE */
167 "\0"
168 #define REG_ESPACE_IDX (REG_ERANGE_IDX + sizeof "Invalid range end")
169 gettext_noop ("Memory exhausted") /* REG_ESPACE */
170 "\0"
171 #define REG_BADRPT_IDX (REG_ESPACE_IDX + sizeof "Memory exhausted")
172 gettext_noop ("Invalid preceding regular expression") /* REG_BADRPT */
173 "\0"
174 #define REG_EEND_IDX (REG_BADRPT_IDX + sizeof "Invalid preceding regular expression")
175 gettext_noop ("Premature end of regular expression") /* REG_EEND */
176 "\0"
177 #define REG_ESIZE_IDX (REG_EEND_IDX + sizeof "Premature end of regular expression")
178 gettext_noop ("Regular expression too big") /* REG_ESIZE */
179 "\0"
180 #define REG_ERPAREN_IDX (REG_ESIZE_IDX + sizeof "Regular expression too big")
181 gettext_noop ("Unmatched ) or \\)") /* REG_ERPAREN */
184 const size_t __re_error_msgid_idx[] attribute_hidden =
186 REG_NOERROR_IDX,
187 REG_NOMATCH_IDX,
188 REG_BADPAT_IDX,
189 REG_ECOLLATE_IDX,
190 REG_ECTYPE_IDX,
191 REG_EESCAPE_IDX,
192 REG_ESUBREG_IDX,
193 REG_EBRACK_IDX,
194 REG_EPAREN_IDX,
195 REG_EBRACE_IDX,
196 REG_BADBR_IDX,
197 REG_ERANGE_IDX,
198 REG_ESPACE_IDX,
199 REG_BADRPT_IDX,
200 REG_EEND_IDX,
201 REG_ESIZE_IDX,
202 REG_ERPAREN_IDX
205 /* Entry points for GNU code. */
207 /* re_compile_pattern is the GNU regular expression compiler: it
208 compiles PATTERN (of length LENGTH) and puts the result in BUFP.
209 Returns 0 if the pattern was valid, otherwise an error string.
211 Assumes the `allocated' (and perhaps `buffer') and `translate' fields
212 are set in BUFP on entry. */
214 const char *
215 re_compile_pattern (pattern, length, bufp)
216 const char *pattern;
217 size_t length;
218 struct re_pattern_buffer *bufp;
220 reg_errcode_t ret;
222 /* And GNU code determines whether or not to get register information
223 by passing null for the REGS argument to re_match, etc., not by
224 setting no_sub, unless RE_NO_SUB is set. */
225 bufp->no_sub = !!(re_syntax_options & RE_NO_SUB);
227 /* Match anchors at newline. */
228 bufp->newline_anchor = 1;
230 ret = re_compile_internal (bufp, pattern, length, re_syntax_options);
232 if (!ret)
233 return NULL;
234 return gettext (__re_error_msgid + __re_error_msgid_idx[(int) ret]);
236 #ifdef _LIBC
237 weak_alias (__re_compile_pattern, re_compile_pattern)
238 #endif
240 /* Set by `re_set_syntax' to the current regexp syntax to recognize. Can
241 also be assigned to arbitrarily: each pattern buffer stores its own
242 syntax, so it can be changed between regex compilations. */
243 /* This has no initializer because initialized variables in Emacs
244 become read-only after dumping. */
245 reg_syntax_t re_syntax_options;
248 /* Specify the precise syntax of regexps for compilation. This provides
249 for compatibility for various utilities which historically have
250 different, incompatible syntaxes.
252 The argument SYNTAX is a bit mask comprised of the various bits
253 defined in regex.h. We return the old syntax. */
255 reg_syntax_t
256 re_set_syntax (syntax)
257 reg_syntax_t syntax;
259 reg_syntax_t ret = re_syntax_options;
261 re_syntax_options = syntax;
262 return ret;
264 #ifdef _LIBC
265 weak_alias (__re_set_syntax, re_set_syntax)
266 #endif
269 re_compile_fastmap (bufp)
270 struct re_pattern_buffer *bufp;
272 re_dfa_t *dfa = (re_dfa_t *) bufp->buffer;
273 char *fastmap = bufp->fastmap;
275 memset (fastmap, '\0', sizeof (char) * SBC_MAX);
276 re_compile_fastmap_iter (bufp, dfa->init_state, fastmap);
277 if (dfa->init_state != dfa->init_state_word)
278 re_compile_fastmap_iter (bufp, dfa->init_state_word, fastmap);
279 if (dfa->init_state != dfa->init_state_nl)
280 re_compile_fastmap_iter (bufp, dfa->init_state_nl, fastmap);
281 if (dfa->init_state != dfa->init_state_begbuf)
282 re_compile_fastmap_iter (bufp, dfa->init_state_begbuf, fastmap);
283 bufp->fastmap_accurate = 1;
284 return 0;
286 #ifdef _LIBC
287 weak_alias (__re_compile_fastmap, re_compile_fastmap)
288 #endif
290 static inline void
291 __attribute ((always_inline))
292 re_set_fastmap (char *fastmap, int icase, int ch)
294 fastmap[ch] = 1;
295 if (icase)
296 fastmap[tolower (ch)] = 1;
299 /* Helper function for re_compile_fastmap.
300 Compile fastmap for the initial_state INIT_STATE. */
302 static void
303 re_compile_fastmap_iter (regex_t *bufp, const re_dfastate_t *init_state,
304 char *fastmap)
306 re_dfa_t *dfa = (re_dfa_t *) bufp->buffer;
307 int node_cnt;
308 int icase = (dfa->mb_cur_max == 1 && (bufp->syntax & RE_ICASE));
309 for (node_cnt = 0; node_cnt < init_state->nodes.nelem; ++node_cnt)
311 int node = init_state->nodes.elems[node_cnt];
312 re_token_type_t type = dfa->nodes[node].type;
314 if (type == CHARACTER)
316 re_set_fastmap (fastmap, icase, dfa->nodes[node].opr.c);
317 #ifdef RE_ENABLE_I18N
318 if ((bufp->syntax & RE_ICASE) && dfa->mb_cur_max > 1)
320 unsigned char *buf = alloca (dfa->mb_cur_max), *p;
321 wchar_t wc;
322 mbstate_t state;
324 p = buf;
325 *p++ = dfa->nodes[node].opr.c;
326 while (++node < dfa->nodes_len
327 && dfa->nodes[node].type == CHARACTER
328 && dfa->nodes[node].mb_partial)
329 *p++ = dfa->nodes[node].opr.c;
330 memset (&state, '\0', sizeof (state));
331 if (__mbrtowc (&wc, (const char *) buf, p - buf,
332 &state) == p - buf
333 && (__wcrtomb ((char *) buf, towlower (wc), &state)
334 != (size_t) -1))
335 re_set_fastmap (fastmap, 0, buf[0]);
337 #endif
339 else if (type == SIMPLE_BRACKET)
341 int i, ch;
342 for (i = 0, ch = 0; i < BITSET_WORDS; ++i)
344 int j;
345 bitset_word_t w = dfa->nodes[node].opr.sbcset[i];
346 for (j = 0; j < BITSET_WORD_BITS; ++j, ++ch)
347 if (w & ((bitset_word_t) 1 << j))
348 re_set_fastmap (fastmap, icase, ch);
351 #ifdef RE_ENABLE_I18N
352 else if (type == COMPLEX_BRACKET)
354 re_charset_t *cset = dfa->nodes[node].opr.mbcset;
355 int i;
357 # ifdef _LIBC
358 /* See if we have to try all bytes which start multiple collation
359 elements.
360 e.g. In da_DK, we want to catch 'a' since "aa" is a valid
361 collation element, and don't catch 'b' since 'b' is
362 the only collation element which starts from 'b' (and
363 it is caught by SIMPLE_BRACKET). */
364 if (_NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES) != 0
365 && (cset->ncoll_syms || cset->nranges))
367 const int32_t *table = (const int32_t *)
368 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
369 for (i = 0; i < SBC_MAX; ++i)
370 if (table[i] < 0)
371 re_set_fastmap (fastmap, icase, i);
373 # endif /* _LIBC */
375 /* See if we have to start the match at all multibyte characters,
376 i.e. where we would not find an invalid sequence. This only
377 applies to multibyte character sets; for single byte character
378 sets, the SIMPLE_BRACKET again suffices. */
379 if (dfa->mb_cur_max > 1
380 && (cset->nchar_classes || cset->non_match || cset->nranges
381 # ifdef _LIBC
382 || cset->nequiv_classes
383 # endif /* _LIBC */
386 unsigned char c = 0;
389 mbstate_t mbs;
390 memset (&mbs, 0, sizeof (mbs));
391 if (__mbrtowc (NULL, (char *) &c, 1, &mbs) == (size_t) -2)
392 re_set_fastmap (fastmap, false, (int) c);
394 while (++c != 0);
397 else
399 /* ... Else catch all bytes which can start the mbchars. */
400 for (i = 0; i < cset->nmbchars; ++i)
402 char buf[256];
403 mbstate_t state;
404 memset (&state, '\0', sizeof (state));
405 if (__wcrtomb (buf, cset->mbchars[i], &state) != (size_t) -1)
406 re_set_fastmap (fastmap, icase, *(unsigned char *) buf);
407 if ((bufp->syntax & RE_ICASE) && dfa->mb_cur_max > 1)
409 if (__wcrtomb (buf, towlower (cset->mbchars[i]), &state)
410 != (size_t) -1)
411 re_set_fastmap (fastmap, false, *(unsigned char *) buf);
416 #endif /* RE_ENABLE_I18N */
417 else if (type == OP_PERIOD
418 #ifdef RE_ENABLE_I18N
419 || type == OP_UTF8_PERIOD
420 #endif /* RE_ENABLE_I18N */
421 || type == END_OF_RE)
423 memset (fastmap, '\1', sizeof (char) * SBC_MAX);
424 if (type == END_OF_RE)
425 bufp->can_be_null = 1;
426 return;
431 /* Entry point for POSIX code. */
432 /* regcomp takes a regular expression as a string and compiles it.
434 PREG is a regex_t *. We do not expect any fields to be initialized,
435 since POSIX says we shouldn't. Thus, we set
437 `buffer' to the compiled pattern;
438 `used' to the length of the compiled pattern;
439 `syntax' to RE_SYNTAX_POSIX_EXTENDED if the
440 REG_EXTENDED bit in CFLAGS is set; otherwise, to
441 RE_SYNTAX_POSIX_BASIC;
442 `newline_anchor' to REG_NEWLINE being set in CFLAGS;
443 `fastmap' to an allocated space for the fastmap;
444 `fastmap_accurate' to zero;
445 `re_nsub' to the number of subexpressions in PATTERN.
447 PATTERN is the address of the pattern string.
449 CFLAGS is a series of bits which affect compilation.
451 If REG_EXTENDED is set, we use POSIX extended syntax; otherwise, we
452 use POSIX basic syntax.
454 If REG_NEWLINE is set, then . and [^...] don't match newline.
455 Also, regexec will try a match beginning after every newline.
457 If REG_ICASE is set, then we considers upper- and lowercase
458 versions of letters to be equivalent when matching.
460 If REG_NOSUB is set, then when PREG is passed to regexec, that
461 routine will report only success or failure, and nothing about the
462 registers.
464 It returns 0 if it succeeds, nonzero if it doesn't. (See regex.h for
465 the return codes and their meanings.) */
468 regcomp (preg, pattern, cflags)
469 regex_t *__restrict preg;
470 const char *__restrict pattern;
471 int cflags;
473 reg_errcode_t ret;
474 reg_syntax_t syntax = ((cflags & REG_EXTENDED) ? RE_SYNTAX_POSIX_EXTENDED
475 : RE_SYNTAX_POSIX_BASIC);
477 preg->buffer = NULL;
478 preg->allocated = 0;
479 preg->used = 0;
481 /* Try to allocate space for the fastmap. */
482 preg->fastmap = re_malloc (char, SBC_MAX);
483 if (BE (preg->fastmap == NULL, 0))
484 return REG_ESPACE;
486 syntax |= (cflags & REG_ICASE) ? RE_ICASE : 0;
488 /* If REG_NEWLINE is set, newlines are treated differently. */
489 if (cflags & REG_NEWLINE)
490 { /* REG_NEWLINE implies neither . nor [^...] match newline. */
491 syntax &= ~RE_DOT_NEWLINE;
492 syntax |= RE_HAT_LISTS_NOT_NEWLINE;
493 /* It also changes the matching behavior. */
494 preg->newline_anchor = 1;
496 else
497 preg->newline_anchor = 0;
498 preg->no_sub = !!(cflags & REG_NOSUB);
499 preg->translate = NULL;
501 ret = re_compile_internal (preg, pattern, strlen (pattern), syntax);
503 /* POSIX doesn't distinguish between an unmatched open-group and an
504 unmatched close-group: both are REG_EPAREN. */
505 if (ret == REG_ERPAREN)
506 ret = REG_EPAREN;
508 /* We have already checked preg->fastmap != NULL. */
509 if (BE (ret == REG_NOERROR, 1))
510 /* Compute the fastmap now, since regexec cannot modify the pattern
511 buffer. This function never fails in this implementation. */
512 (void) re_compile_fastmap (preg);
513 else
515 /* Some error occurred while compiling the expression. */
516 re_free (preg->fastmap);
517 preg->fastmap = NULL;
520 return (int) ret;
522 #ifdef _LIBC
523 weak_alias (__regcomp, regcomp)
524 #endif
526 /* Returns a message corresponding to an error code, ERRCODE, returned
527 from either regcomp or regexec. We don't use PREG here. */
529 size_t
530 regerror (errcode, preg, errbuf, errbuf_size)
531 int errcode;
532 const regex_t *__restrict preg;
533 char *__restrict errbuf;
534 size_t errbuf_size;
536 const char *msg;
537 size_t msg_size;
539 if (BE (errcode < 0
540 || errcode >= (int) (sizeof (__re_error_msgid_idx)
541 / sizeof (__re_error_msgid_idx[0])), 0))
542 /* Only error codes returned by the rest of the code should be passed
543 to this routine. If we are given anything else, or if other regex
544 code generates an invalid error code, then the program has a bug.
545 Dump core so we can fix it. */
546 abort ();
548 msg = gettext (__re_error_msgid + __re_error_msgid_idx[errcode]);
550 msg_size = strlen (msg) + 1; /* Includes the null. */
552 if (BE (errbuf_size != 0, 1))
554 if (BE (msg_size > errbuf_size, 0))
556 #if defined HAVE_MEMPCPY || defined _LIBC
557 *((char *) __mempcpy (errbuf, msg, errbuf_size - 1)) = '\0';
558 #else
559 memcpy (errbuf, msg, errbuf_size - 1);
560 errbuf[errbuf_size - 1] = 0;
561 #endif
563 else
564 memcpy (errbuf, msg, msg_size);
567 return msg_size;
569 #ifdef _LIBC
570 weak_alias (__regerror, regerror)
571 #endif
574 #ifdef RE_ENABLE_I18N
575 /* This static array is used for the map to single-byte characters when
576 UTF-8 is used. Otherwise we would allocate memory just to initialize
577 it the same all the time. UTF-8 is the preferred encoding so this is
578 a worthwhile optimization. */
579 static const bitset_t utf8_sb_map =
581 /* Set the first 128 bits. */
582 [0 ... 0x80 / BITSET_WORD_BITS - 1] = BITSET_WORD_MAX
584 #endif
587 static void
588 free_dfa_content (re_dfa_t *dfa)
590 int i, j;
592 if (dfa->nodes)
593 for (i = 0; i < dfa->nodes_len; ++i)
594 free_token (dfa->nodes + i);
595 re_free (dfa->nexts);
596 for (i = 0; i < dfa->nodes_len; ++i)
598 if (dfa->eclosures != NULL)
599 re_node_set_free (dfa->eclosures + i);
600 if (dfa->inveclosures != NULL)
601 re_node_set_free (dfa->inveclosures + i);
602 if (dfa->edests != NULL)
603 re_node_set_free (dfa->edests + i);
605 re_free (dfa->edests);
606 re_free (dfa->eclosures);
607 re_free (dfa->inveclosures);
608 re_free (dfa->nodes);
610 if (dfa->state_table)
611 for (i = 0; i <= dfa->state_hash_mask; ++i)
613 struct re_state_table_entry *entry = dfa->state_table + i;
614 for (j = 0; j < entry->num; ++j)
616 re_dfastate_t *state = entry->array[j];
617 free_state (state);
619 re_free (entry->array);
621 re_free (dfa->state_table);
622 #ifdef RE_ENABLE_I18N
623 if (dfa->sb_char != utf8_sb_map)
624 re_free (dfa->sb_char);
625 #endif
626 re_free (dfa->subexp_map);
627 #ifdef DEBUG
628 re_free (dfa->re_str);
629 #endif
631 re_free (dfa);
635 /* Free dynamically allocated space used by PREG. */
637 void
638 regfree (preg)
639 regex_t *preg;
641 re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
642 if (BE (dfa != NULL, 1))
643 free_dfa_content (dfa);
644 preg->buffer = NULL;
645 preg->allocated = 0;
647 re_free (preg->fastmap);
648 preg->fastmap = NULL;
650 re_free (preg->translate);
651 preg->translate = NULL;
653 #ifdef _LIBC
654 weak_alias (__regfree, regfree)
655 #endif
657 /* Entry points compatible with 4.2 BSD regex library. We don't define
658 them unless specifically requested. */
660 #if defined _REGEX_RE_COMP || defined _LIBC
662 /* BSD has one and only one pattern buffer. */
663 static struct re_pattern_buffer re_comp_buf;
665 char *
666 # ifdef _LIBC
667 /* Make these definitions weak in libc, so POSIX programs can redefine
668 these names if they don't use our functions, and still use
669 regcomp/regexec above without link errors. */
670 weak_function
671 # endif
672 re_comp (s)
673 const char *s;
675 reg_errcode_t ret;
676 char *fastmap;
678 if (!s)
680 if (!re_comp_buf.buffer)
681 return gettext ("No previous regular expression");
682 return 0;
685 if (re_comp_buf.buffer)
687 fastmap = re_comp_buf.fastmap;
688 re_comp_buf.fastmap = NULL;
689 __regfree (&re_comp_buf);
690 memset (&re_comp_buf, '\0', sizeof (re_comp_buf));
691 re_comp_buf.fastmap = fastmap;
694 if (re_comp_buf.fastmap == NULL)
696 re_comp_buf.fastmap = (char *) malloc (SBC_MAX);
697 if (re_comp_buf.fastmap == NULL)
698 return (char *) gettext (__re_error_msgid
699 + __re_error_msgid_idx[(int) REG_ESPACE]);
702 /* Since `re_exec' always passes NULL for the `regs' argument, we
703 don't need to initialize the pattern buffer fields which affect it. */
705 /* Match anchors at newlines. */
706 re_comp_buf.newline_anchor = 1;
708 ret = re_compile_internal (&re_comp_buf, s, strlen (s), re_syntax_options);
710 if (!ret)
711 return NULL;
713 /* Yes, we're discarding `const' here if !HAVE_LIBINTL. */
714 return (char *) gettext (__re_error_msgid + __re_error_msgid_idx[(int) ret]);
717 #ifdef _LIBC
718 libc_freeres_fn (free_mem)
720 __regfree (&re_comp_buf);
722 #endif
724 #endif /* _REGEX_RE_COMP */
726 /* Internal entry point.
727 Compile the regular expression PATTERN, whose length is LENGTH.
728 SYNTAX indicate regular expression's syntax. */
730 static reg_errcode_t
731 re_compile_internal (regex_t *preg, const char * pattern, size_t length,
732 reg_syntax_t syntax)
734 reg_errcode_t err = REG_NOERROR;
735 re_dfa_t *dfa;
736 re_string_t regexp;
738 /* Initialize the pattern buffer. */
739 preg->fastmap_accurate = 0;
740 preg->syntax = syntax;
741 preg->not_bol = preg->not_eol = 0;
742 preg->used = 0;
743 preg->re_nsub = 0;
744 preg->can_be_null = 0;
745 preg->regs_allocated = REGS_UNALLOCATED;
747 /* Initialize the dfa. */
748 dfa = (re_dfa_t *) preg->buffer;
749 if (BE (preg->allocated < sizeof (re_dfa_t), 0))
751 /* If zero allocated, but buffer is non-null, try to realloc
752 enough space. This loses if buffer's address is bogus, but
753 that is the user's responsibility. If ->buffer is NULL this
754 is a simple allocation. */
755 dfa = re_realloc (preg->buffer, re_dfa_t, 1);
756 if (dfa == NULL)
757 return REG_ESPACE;
758 preg->allocated = sizeof (re_dfa_t);
759 preg->buffer = (unsigned char *) dfa;
761 preg->used = sizeof (re_dfa_t);
763 err = init_dfa (dfa, length);
764 if (BE (err != REG_NOERROR, 0))
766 free_dfa_content (dfa);
767 preg->buffer = NULL;
768 preg->allocated = 0;
769 return err;
771 #ifdef DEBUG
772 /* Note: length+1 will not overflow since it is checked in init_dfa. */
773 dfa->re_str = re_malloc (char, length + 1);
774 strncpy (dfa->re_str, pattern, length + 1);
775 #endif
777 __libc_lock_init (dfa->lock);
779 err = re_string_construct (&regexp, pattern, length, preg->translate,
780 syntax & RE_ICASE, dfa);
781 if (BE (err != REG_NOERROR, 0))
783 re_compile_internal_free_return:
784 free_workarea_compile (preg);
785 re_string_destruct (&regexp);
786 free_dfa_content (dfa);
787 preg->buffer = NULL;
788 preg->allocated = 0;
789 return err;
792 /* Parse the regular expression, and build a structure tree. */
793 preg->re_nsub = 0;
794 dfa->str_tree = parse (&regexp, preg, syntax, &err);
795 if (BE (dfa->str_tree == NULL, 0))
796 goto re_compile_internal_free_return;
798 /* Analyze the tree and create the nfa. */
799 err = analyze (preg);
800 if (BE (err != REG_NOERROR, 0))
801 goto re_compile_internal_free_return;
803 #ifdef RE_ENABLE_I18N
804 /* If possible, do searching in single byte encoding to speed things up. */
805 if (dfa->is_utf8 && !(syntax & RE_ICASE) && preg->translate == NULL)
806 optimize_utf8 (dfa);
807 #endif
809 /* Then create the initial state of the dfa. */
810 err = create_initial_state (dfa);
812 /* Release work areas. */
813 free_workarea_compile (preg);
814 re_string_destruct (&regexp);
816 if (BE (err != REG_NOERROR, 0))
818 free_dfa_content (dfa);
819 preg->buffer = NULL;
820 preg->allocated = 0;
823 return err;
826 /* Initialize DFA. We use the length of the regular expression PAT_LEN
827 as the initial length of some arrays. */
829 static reg_errcode_t
830 init_dfa (re_dfa_t *dfa, size_t pat_len)
832 unsigned int table_size;
833 #ifndef _LIBC
834 char *codeset_name;
835 #endif
837 memset (dfa, '\0', sizeof (re_dfa_t));
839 /* Force allocation of str_tree_storage the first time. */
840 dfa->str_tree_storage_idx = BIN_TREE_STORAGE_SIZE;
842 /* Avoid overflows. */
843 if (pat_len == SIZE_MAX)
844 return REG_ESPACE;
846 dfa->nodes_alloc = pat_len + 1;
847 dfa->nodes = re_malloc (re_token_t, dfa->nodes_alloc);
849 /* table_size = 2 ^ ceil(log pat_len) */
850 for (table_size = 1; ; table_size <<= 1)
851 if (table_size > pat_len)
852 break;
854 dfa->state_table = calloc (sizeof (struct re_state_table_entry), table_size);
855 dfa->state_hash_mask = table_size - 1;
857 dfa->mb_cur_max = MB_CUR_MAX;
858 #ifdef _LIBC
859 if (dfa->mb_cur_max == 6
860 && strcmp (_NL_CURRENT (LC_CTYPE, _NL_CTYPE_CODESET_NAME), "UTF-8") == 0)
861 dfa->is_utf8 = 1;
862 dfa->map_notascii = (_NL_CURRENT_WORD (LC_CTYPE, _NL_CTYPE_MAP_TO_NONASCII)
863 != 0);
864 #else
865 # ifdef HAVE_LANGINFO_CODESET
866 codeset_name = nl_langinfo (CODESET);
867 # else
868 codeset_name = getenv ("LC_ALL");
869 if (codeset_name == NULL || codeset_name[0] == '\0')
870 codeset_name = getenv ("LC_CTYPE");
871 if (codeset_name == NULL || codeset_name[0] == '\0')
872 codeset_name = getenv ("LANG");
873 if (codeset_name == NULL)
874 codeset_name = "";
875 else if (strchr (codeset_name, '.') != NULL)
876 codeset_name = strchr (codeset_name, '.') + 1;
877 # endif
879 if (strcasecmp (codeset_name, "UTF-8") == 0
880 || strcasecmp (codeset_name, "UTF8") == 0)
881 dfa->is_utf8 = 1;
883 /* We check exhaustively in the loop below if this charset is a
884 superset of ASCII. */
885 dfa->map_notascii = 0;
886 #endif
888 #ifdef RE_ENABLE_I18N
889 if (dfa->mb_cur_max > 1)
891 if (dfa->is_utf8)
892 dfa->sb_char = (re_bitset_ptr_t) utf8_sb_map;
893 else
895 int i, j, ch;
897 dfa->sb_char = (re_bitset_ptr_t) calloc (sizeof (bitset_t), 1);
898 if (BE (dfa->sb_char == NULL, 0))
899 return REG_ESPACE;
901 /* Set the bits corresponding to single byte chars. */
902 for (i = 0, ch = 0; i < BITSET_WORDS; ++i)
903 for (j = 0; j < BITSET_WORD_BITS; ++j, ++ch)
905 wint_t wch = __btowc (ch);
906 if (wch != WEOF)
907 dfa->sb_char[i] |= (bitset_word_t) 1 << j;
908 # ifndef _LIBC
909 if (isascii (ch) && wch != ch)
910 dfa->map_notascii = 1;
911 # endif
915 #endif
917 if (BE (dfa->nodes == NULL || dfa->state_table == NULL, 0))
918 return REG_ESPACE;
919 return REG_NOERROR;
922 /* Initialize WORD_CHAR table, which indicate which character is
923 "word". In this case "word" means that it is the word construction
924 character used by some operators like "\<", "\>", etc. */
926 static void
927 internal_function
928 init_word_char (re_dfa_t *dfa)
930 dfa->word_ops_used = 1;
931 int i = 0;
932 int ch = 0;
933 if (BE (dfa->map_notascii == 0, 1))
935 if (sizeof (dfa->word_char[0]) == 8)
937 /* The extra temporaries here avoid "implicitly truncated"
938 warnings in the case when this is dead code, i.e. 32-bit. */
939 const uint64_t wc0 = UINT64_C (0x03ff000000000000);
940 const uint64_t wc1 = UINT64_C (0x07fffffe87fffffe);
941 dfa->word_char[0] = wc0;
942 dfa->word_char[1] = wc1;
943 i = 2;
945 else if (sizeof (dfa->word_char[0]) == 4)
947 dfa->word_char[0] = UINT32_C (0x00000000);
948 dfa->word_char[1] = UINT32_C (0x03ff0000);
949 dfa->word_char[2] = UINT32_C (0x87fffffe);
950 dfa->word_char[3] = UINT32_C (0x07fffffe);
951 i = 4;
953 else
954 abort ();
955 ch = 128;
957 if (BE (dfa->is_utf8, 1))
959 memset (&dfa->word_char[i], '\0', (SBC_MAX - ch) / 8);
960 return;
964 for (; i < BITSET_WORDS; ++i)
965 for (int j = 0; j < BITSET_WORD_BITS; ++j, ++ch)
966 if (isalnum (ch) || ch == '_')
967 dfa->word_char[i] |= (bitset_word_t) 1 << j;
970 /* Free the work area which are only used while compiling. */
972 static void
973 free_workarea_compile (regex_t *preg)
975 re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
976 bin_tree_storage_t *storage, *next;
977 for (storage = dfa->str_tree_storage; storage; storage = next)
979 next = storage->next;
980 re_free (storage);
982 dfa->str_tree_storage = NULL;
983 dfa->str_tree_storage_idx = BIN_TREE_STORAGE_SIZE;
984 dfa->str_tree = NULL;
985 re_free (dfa->org_indices);
986 dfa->org_indices = NULL;
989 /* Create initial states for all contexts. */
991 static reg_errcode_t
992 create_initial_state (re_dfa_t *dfa)
994 int first, i;
995 reg_errcode_t err;
996 re_node_set init_nodes;
998 /* Initial states have the epsilon closure of the node which is
999 the first node of the regular expression. */
1000 first = dfa->str_tree->first->node_idx;
1001 dfa->init_node = first;
1002 err = re_node_set_init_copy (&init_nodes, dfa->eclosures + first);
1003 if (BE (err != REG_NOERROR, 0))
1004 return err;
1006 /* The back-references which are in initial states can epsilon transit,
1007 since in this case all of the subexpressions can be null.
1008 Then we add epsilon closures of the nodes which are the next nodes of
1009 the back-references. */
1010 if (dfa->nbackref > 0)
1011 for (i = 0; i < init_nodes.nelem; ++i)
1013 int node_idx = init_nodes.elems[i];
1014 re_token_type_t type = dfa->nodes[node_idx].type;
1016 int clexp_idx;
1017 if (type != OP_BACK_REF)
1018 continue;
1019 for (clexp_idx = 0; clexp_idx < init_nodes.nelem; ++clexp_idx)
1021 re_token_t *clexp_node;
1022 clexp_node = dfa->nodes + init_nodes.elems[clexp_idx];
1023 if (clexp_node->type == OP_CLOSE_SUBEXP
1024 && clexp_node->opr.idx == dfa->nodes[node_idx].opr.idx)
1025 break;
1027 if (clexp_idx == init_nodes.nelem)
1028 continue;
1030 if (type == OP_BACK_REF)
1032 int dest_idx = dfa->edests[node_idx].elems[0];
1033 if (!re_node_set_contains (&init_nodes, dest_idx))
1035 reg_errcode_t err = re_node_set_merge (&init_nodes,
1036 dfa->eclosures
1037 + dest_idx);
1038 if (err != REG_NOERROR)
1039 return err;
1040 i = 0;
1045 /* It must be the first time to invoke acquire_state. */
1046 dfa->init_state = re_acquire_state_context (&err, dfa, &init_nodes, 0);
1047 /* We don't check ERR here, since the initial state must not be NULL. */
1048 if (BE (dfa->init_state == NULL, 0))
1049 return err;
1050 if (dfa->init_state->has_constraint)
1052 dfa->init_state_word = re_acquire_state_context (&err, dfa, &init_nodes,
1053 CONTEXT_WORD);
1054 dfa->init_state_nl = re_acquire_state_context (&err, dfa, &init_nodes,
1055 CONTEXT_NEWLINE);
1056 dfa->init_state_begbuf = re_acquire_state_context (&err, dfa,
1057 &init_nodes,
1058 CONTEXT_NEWLINE
1059 | CONTEXT_BEGBUF);
1060 if (BE (dfa->init_state_word == NULL || dfa->init_state_nl == NULL
1061 || dfa->init_state_begbuf == NULL, 0))
1062 return err;
1064 else
1065 dfa->init_state_word = dfa->init_state_nl
1066 = dfa->init_state_begbuf = dfa->init_state;
1068 re_node_set_free (&init_nodes);
1069 return REG_NOERROR;
1072 #ifdef RE_ENABLE_I18N
1073 /* If it is possible to do searching in single byte encoding instead of UTF-8
1074 to speed things up, set dfa->mb_cur_max to 1, clear is_utf8 and change
1075 DFA nodes where needed. */
1077 static void
1078 optimize_utf8 (re_dfa_t *dfa)
1080 int node, i, mb_chars = 0, has_period = 0;
1082 for (node = 0; node < dfa->nodes_len; ++node)
1083 switch (dfa->nodes[node].type)
1085 case CHARACTER:
1086 if (dfa->nodes[node].opr.c >= 0x80)
1087 mb_chars = 1;
1088 break;
1089 case ANCHOR:
1090 switch (dfa->nodes[node].opr.ctx_type)
1092 case LINE_FIRST:
1093 case LINE_LAST:
1094 case BUF_FIRST:
1095 case BUF_LAST:
1096 break;
1097 default:
1098 /* Word anchors etc. cannot be handled. It's okay to test
1099 opr.ctx_type since constraints (for all DFA nodes) are
1100 created by ORing one or more opr.ctx_type values. */
1101 return;
1103 break;
1104 case OP_PERIOD:
1105 has_period = 1;
1106 break;
1107 case OP_BACK_REF:
1108 case OP_ALT:
1109 case END_OF_RE:
1110 case OP_DUP_ASTERISK:
1111 case OP_OPEN_SUBEXP:
1112 case OP_CLOSE_SUBEXP:
1113 break;
1114 case COMPLEX_BRACKET:
1115 return;
1116 case SIMPLE_BRACKET:
1117 /* Just double check. The non-ASCII range starts at 0x80. */
1118 assert (0x80 % BITSET_WORD_BITS == 0);
1119 for (i = 0x80 / BITSET_WORD_BITS; i < BITSET_WORDS; ++i)
1120 if (dfa->nodes[node].opr.sbcset[i])
1121 return;
1122 break;
1123 default:
1124 abort ();
1127 if (mb_chars || has_period)
1128 for (node = 0; node < dfa->nodes_len; ++node)
1130 if (dfa->nodes[node].type == CHARACTER
1131 && dfa->nodes[node].opr.c >= 0x80)
1132 dfa->nodes[node].mb_partial = 0;
1133 else if (dfa->nodes[node].type == OP_PERIOD)
1134 dfa->nodes[node].type = OP_UTF8_PERIOD;
1137 /* The search can be in single byte locale. */
1138 dfa->mb_cur_max = 1;
1139 dfa->is_utf8 = 0;
1140 dfa->has_mb_node = dfa->nbackref > 0 || has_period;
1142 #endif
1144 /* Analyze the structure tree, and calculate "first", "next", "edest",
1145 "eclosure", and "inveclosure". */
1147 static reg_errcode_t
1148 analyze (regex_t *preg)
1150 re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
1151 reg_errcode_t ret;
1153 /* Allocate arrays. */
1154 dfa->nexts = re_malloc (int, dfa->nodes_alloc);
1155 dfa->org_indices = re_malloc (int, dfa->nodes_alloc);
1156 dfa->edests = re_malloc (re_node_set, dfa->nodes_alloc);
1157 dfa->eclosures = re_malloc (re_node_set, dfa->nodes_alloc);
1158 if (BE (dfa->nexts == NULL || dfa->org_indices == NULL || dfa->edests == NULL
1159 || dfa->eclosures == NULL, 0))
1160 return REG_ESPACE;
1162 dfa->subexp_map = re_malloc (int, preg->re_nsub);
1163 if (dfa->subexp_map != NULL)
1165 int i;
1166 for (i = 0; i < preg->re_nsub; i++)
1167 dfa->subexp_map[i] = i;
1168 preorder (dfa->str_tree, optimize_subexps, dfa);
1169 for (i = 0; i < preg->re_nsub; i++)
1170 if (dfa->subexp_map[i] != i)
1171 break;
1172 if (i == preg->re_nsub)
1174 free (dfa->subexp_map);
1175 dfa->subexp_map = NULL;
1179 ret = postorder (dfa->str_tree, lower_subexps, preg);
1180 if (BE (ret != REG_NOERROR, 0))
1181 return ret;
1182 ret = postorder (dfa->str_tree, calc_first, dfa);
1183 if (BE (ret != REG_NOERROR, 0))
1184 return ret;
1185 preorder (dfa->str_tree, calc_next, dfa);
1186 ret = preorder (dfa->str_tree, link_nfa_nodes, dfa);
1187 if (BE (ret != REG_NOERROR, 0))
1188 return ret;
1189 ret = calc_eclosure (dfa);
1190 if (BE (ret != REG_NOERROR, 0))
1191 return ret;
1193 /* We only need this during the prune_impossible_nodes pass in regexec.c;
1194 skip it if p_i_n will not run, as calc_inveclosure can be quadratic. */
1195 if ((!preg->no_sub && preg->re_nsub > 0 && dfa->has_plural_match)
1196 || dfa->nbackref)
1198 dfa->inveclosures = re_malloc (re_node_set, dfa->nodes_len);
1199 if (BE (dfa->inveclosures == NULL, 0))
1200 return REG_ESPACE;
1201 ret = calc_inveclosure (dfa);
1204 return ret;
1207 /* Our parse trees are very unbalanced, so we cannot use a stack to
1208 implement parse tree visits. Instead, we use parent pointers and
1209 some hairy code in these two functions. */
1210 static reg_errcode_t
1211 postorder (bin_tree_t *root, reg_errcode_t (fn (void *, bin_tree_t *)),
1212 void *extra)
1214 bin_tree_t *node, *prev;
1216 for (node = root; ; )
1218 /* Descend down the tree, preferably to the left (or to the right
1219 if that's the only child). */
1220 while (node->left || node->right)
1221 if (node->left)
1222 node = node->left;
1223 else
1224 node = node->right;
1228 reg_errcode_t err = fn (extra, node);
1229 if (BE (err != REG_NOERROR, 0))
1230 return err;
1231 if (node->parent == NULL)
1232 return REG_NOERROR;
1233 prev = node;
1234 node = node->parent;
1236 /* Go up while we have a node that is reached from the right. */
1237 while (node->right == prev || node->right == NULL);
1238 node = node->right;
1242 static reg_errcode_t
1243 preorder (bin_tree_t *root, reg_errcode_t (fn (void *, bin_tree_t *)),
1244 void *extra)
1246 bin_tree_t *node;
1248 for (node = root; ; )
1250 reg_errcode_t err = fn (extra, node);
1251 if (BE (err != REG_NOERROR, 0))
1252 return err;
1254 /* Go to the left node, or up and to the right. */
1255 if (node->left)
1256 node = node->left;
1257 else
1259 bin_tree_t *prev = NULL;
1260 while (node->right == prev || node->right == NULL)
1262 prev = node;
1263 node = node->parent;
1264 if (!node)
1265 return REG_NOERROR;
1267 node = node->right;
1272 /* Optimization pass: if a SUBEXP is entirely contained, strip it and tell
1273 re_search_internal to map the inner one's opr.idx to this one's. Adjust
1274 backreferences as well. Requires a preorder visit. */
1275 static reg_errcode_t
1276 optimize_subexps (void *extra, bin_tree_t *node)
1278 re_dfa_t *dfa = (re_dfa_t *) extra;
1280 if (node->token.type == OP_BACK_REF && dfa->subexp_map)
1282 int idx = node->token.opr.idx;
1283 node->token.opr.idx = dfa->subexp_map[idx];
1284 dfa->used_bkref_map |= 1 << node->token.opr.idx;
1287 else if (node->token.type == SUBEXP
1288 && node->left && node->left->token.type == SUBEXP)
1290 int other_idx = node->left->token.opr.idx;
1292 node->left = node->left->left;
1293 if (node->left)
1294 node->left->parent = node;
1296 dfa->subexp_map[other_idx] = dfa->subexp_map[node->token.opr.idx];
1297 if (other_idx < BITSET_WORD_BITS)
1298 dfa->used_bkref_map &= ~((bitset_word_t) 1 << other_idx);
1301 return REG_NOERROR;
1304 /* Lowering pass: Turn each SUBEXP node into the appropriate concatenation
1305 of OP_OPEN_SUBEXP, the body of the SUBEXP (if any) and OP_CLOSE_SUBEXP. */
1306 static reg_errcode_t
1307 lower_subexps (void *extra, bin_tree_t *node)
1309 regex_t *preg = (regex_t *) extra;
1310 reg_errcode_t err = REG_NOERROR;
1312 if (node->left && node->left->token.type == SUBEXP)
1314 node->left = lower_subexp (&err, preg, node->left);
1315 if (node->left)
1316 node->left->parent = node;
1318 if (node->right && node->right->token.type == SUBEXP)
1320 node->right = lower_subexp (&err, preg, node->right);
1321 if (node->right)
1322 node->right->parent = node;
1325 return err;
1328 static bin_tree_t *
1329 lower_subexp (reg_errcode_t *err, regex_t *preg, bin_tree_t *node)
1331 re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
1332 bin_tree_t *body = node->left;
1333 bin_tree_t *op, *cls, *tree1, *tree;
1335 if (preg->no_sub
1336 /* We do not optimize empty subexpressions, because otherwise we may
1337 have bad CONCAT nodes with NULL children. This is obviously not
1338 very common, so we do not lose much. An example that triggers
1339 this case is the sed "script" /\(\)/x. */
1340 && node->left != NULL
1341 && (node->token.opr.idx >= BITSET_WORD_BITS
1342 || !(dfa->used_bkref_map
1343 & ((bitset_word_t) 1 << node->token.opr.idx))))
1344 return node->left;
1346 /* Convert the SUBEXP node to the concatenation of an
1347 OP_OPEN_SUBEXP, the contents, and an OP_CLOSE_SUBEXP. */
1348 op = create_tree (dfa, NULL, NULL, OP_OPEN_SUBEXP);
1349 cls = create_tree (dfa, NULL, NULL, OP_CLOSE_SUBEXP);
1350 tree1 = body ? create_tree (dfa, body, cls, CONCAT) : cls;
1351 tree = create_tree (dfa, op, tree1, CONCAT);
1352 if (BE (tree == NULL || tree1 == NULL || op == NULL || cls == NULL, 0))
1354 *err = REG_ESPACE;
1355 return NULL;
1358 op->token.opr.idx = cls->token.opr.idx = node->token.opr.idx;
1359 op->token.opt_subexp = cls->token.opt_subexp = node->token.opt_subexp;
1360 return tree;
1363 /* Pass 1 in building the NFA: compute FIRST and create unlinked automaton
1364 nodes. Requires a postorder visit. */
1365 static reg_errcode_t
1366 calc_first (void *extra, bin_tree_t *node)
1368 re_dfa_t *dfa = (re_dfa_t *) extra;
1369 if (node->token.type == CONCAT)
1371 node->first = node->left->first;
1372 node->node_idx = node->left->node_idx;
1374 else
1376 node->first = node;
1377 node->node_idx = re_dfa_add_node (dfa, node->token);
1378 if (BE (node->node_idx == -1, 0))
1379 return REG_ESPACE;
1380 if (node->token.type == ANCHOR)
1381 dfa->nodes[node->node_idx].constraint = node->token.opr.ctx_type;
1383 return REG_NOERROR;
1386 /* Pass 2: compute NEXT on the tree. Preorder visit. */
1387 static reg_errcode_t
1388 calc_next (void *extra, bin_tree_t *node)
1390 switch (node->token.type)
1392 case OP_DUP_ASTERISK:
1393 node->left->next = node;
1394 break;
1395 case CONCAT:
1396 node->left->next = node->right->first;
1397 node->right->next = node->next;
1398 break;
1399 default:
1400 if (node->left)
1401 node->left->next = node->next;
1402 if (node->right)
1403 node->right->next = node->next;
1404 break;
1406 return REG_NOERROR;
1409 /* Pass 3: link all DFA nodes to their NEXT node (any order will do). */
1410 static reg_errcode_t
1411 link_nfa_nodes (void *extra, bin_tree_t *node)
1413 re_dfa_t *dfa = (re_dfa_t *) extra;
1414 int idx = node->node_idx;
1415 reg_errcode_t err = REG_NOERROR;
1417 switch (node->token.type)
1419 case CONCAT:
1420 break;
1422 case END_OF_RE:
1423 assert (node->next == NULL);
1424 break;
1426 case OP_DUP_ASTERISK:
1427 case OP_ALT:
1429 int left, right;
1430 dfa->has_plural_match = 1;
1431 if (node->left != NULL)
1432 left = node->left->first->node_idx;
1433 else
1434 left = node->next->node_idx;
1435 if (node->right != NULL)
1436 right = node->right->first->node_idx;
1437 else
1438 right = node->next->node_idx;
1439 assert (left > -1);
1440 assert (right > -1);
1441 err = re_node_set_init_2 (dfa->edests + idx, left, right);
1443 break;
1445 case ANCHOR:
1446 case OP_OPEN_SUBEXP:
1447 case OP_CLOSE_SUBEXP:
1448 err = re_node_set_init_1 (dfa->edests + idx, node->next->node_idx);
1449 break;
1451 case OP_BACK_REF:
1452 dfa->nexts[idx] = node->next->node_idx;
1453 if (node->token.type == OP_BACK_REF)
1454 err = re_node_set_init_1 (dfa->edests + idx, dfa->nexts[idx]);
1455 break;
1457 default:
1458 assert (!IS_EPSILON_NODE (node->token.type));
1459 dfa->nexts[idx] = node->next->node_idx;
1460 break;
1463 return err;
1466 /* Duplicate the epsilon closure of the node ROOT_NODE.
1467 Note that duplicated nodes have constraint INIT_CONSTRAINT in addition
1468 to their own constraint. */
1470 static reg_errcode_t
1471 internal_function
1472 duplicate_node_closure (re_dfa_t *dfa, int top_org_node, int top_clone_node,
1473 int root_node, unsigned int init_constraint)
1475 int org_node, clone_node, ret;
1476 unsigned int constraint = init_constraint;
1477 for (org_node = top_org_node, clone_node = top_clone_node;;)
1479 int org_dest, clone_dest;
1480 if (dfa->nodes[org_node].type == OP_BACK_REF)
1482 /* If the back reference epsilon-transit, its destination must
1483 also have the constraint. Then duplicate the epsilon closure
1484 of the destination of the back reference, and store it in
1485 edests of the back reference. */
1486 org_dest = dfa->nexts[org_node];
1487 re_node_set_empty (dfa->edests + clone_node);
1488 clone_dest = duplicate_node (dfa, org_dest, constraint);
1489 if (BE (clone_dest == -1, 0))
1490 return REG_ESPACE;
1491 dfa->nexts[clone_node] = dfa->nexts[org_node];
1492 ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);
1493 if (BE (ret < 0, 0))
1494 return REG_ESPACE;
1496 else if (dfa->edests[org_node].nelem == 0)
1498 /* In case of the node can't epsilon-transit, don't duplicate the
1499 destination and store the original destination as the
1500 destination of the node. */
1501 dfa->nexts[clone_node] = dfa->nexts[org_node];
1502 break;
1504 else if (dfa->edests[org_node].nelem == 1)
1506 /* In case of the node can epsilon-transit, and it has only one
1507 destination. */
1508 org_dest = dfa->edests[org_node].elems[0];
1509 re_node_set_empty (dfa->edests + clone_node);
1510 /* If the node is root_node itself, it means the epsilon clsoure
1511 has a loop. Then tie it to the destination of the root_node. */
1512 if (org_node == root_node && clone_node != org_node)
1514 ret = re_node_set_insert (dfa->edests + clone_node, org_dest);
1515 if (BE (ret < 0, 0))
1516 return REG_ESPACE;
1517 break;
1519 /* In case of the node has another constraint, add it. */
1520 constraint |= dfa->nodes[org_node].constraint;
1521 clone_dest = duplicate_node (dfa, org_dest, constraint);
1522 if (BE (clone_dest == -1, 0))
1523 return REG_ESPACE;
1524 ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);
1525 if (BE (ret < 0, 0))
1526 return REG_ESPACE;
1528 else /* dfa->edests[org_node].nelem == 2 */
1530 /* In case of the node can epsilon-transit, and it has two
1531 destinations. In the bin_tree_t and DFA, that's '|' and '*'. */
1532 org_dest = dfa->edests[org_node].elems[0];
1533 re_node_set_empty (dfa->edests + clone_node);
1534 /* Search for a duplicated node which satisfies the constraint. */
1535 clone_dest = search_duplicated_node (dfa, org_dest, constraint);
1536 if (clone_dest == -1)
1538 /* There is no such duplicated node, create a new one. */
1539 reg_errcode_t err;
1540 clone_dest = duplicate_node (dfa, org_dest, constraint);
1541 if (BE (clone_dest == -1, 0))
1542 return REG_ESPACE;
1543 ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);
1544 if (BE (ret < 0, 0))
1545 return REG_ESPACE;
1546 err = duplicate_node_closure (dfa, org_dest, clone_dest,
1547 root_node, constraint);
1548 if (BE (err != REG_NOERROR, 0))
1549 return err;
1551 else
1553 /* There is a duplicated node which satisfies the constraint,
1554 use it to avoid infinite loop. */
1555 ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);
1556 if (BE (ret < 0, 0))
1557 return REG_ESPACE;
1560 org_dest = dfa->edests[org_node].elems[1];
1561 clone_dest = duplicate_node (dfa, org_dest, constraint);
1562 if (BE (clone_dest == -1, 0))
1563 return REG_ESPACE;
1564 ret = re_node_set_insert (dfa->edests + clone_node, clone_dest);
1565 if (BE (ret < 0, 0))
1566 return REG_ESPACE;
1568 org_node = org_dest;
1569 clone_node = clone_dest;
1571 return REG_NOERROR;
1574 /* Search for a node which is duplicated from the node ORG_NODE, and
1575 satisfies the constraint CONSTRAINT. */
1577 static int
1578 search_duplicated_node (const re_dfa_t *dfa, int org_node,
1579 unsigned int constraint)
1581 int idx;
1582 for (idx = dfa->nodes_len - 1; dfa->nodes[idx].duplicated && idx > 0; --idx)
1584 if (org_node == dfa->org_indices[idx]
1585 && constraint == dfa->nodes[idx].constraint)
1586 return idx; /* Found. */
1588 return -1; /* Not found. */
1591 /* Duplicate the node whose index is ORG_IDX and set the constraint CONSTRAINT.
1592 Return the index of the new node, or -1 if insufficient storage is
1593 available. */
1595 static int
1596 duplicate_node (re_dfa_t *dfa, int org_idx, unsigned int constraint)
1598 int dup_idx = re_dfa_add_node (dfa, dfa->nodes[org_idx]);
1599 if (BE (dup_idx != -1, 1))
1601 dfa->nodes[dup_idx].constraint = constraint;
1602 dfa->nodes[dup_idx].constraint |= dfa->nodes[org_idx].constraint;
1603 dfa->nodes[dup_idx].duplicated = 1;
1605 /* Store the index of the original node. */
1606 dfa->org_indices[dup_idx] = org_idx;
1608 return dup_idx;
1611 static reg_errcode_t
1612 calc_inveclosure (re_dfa_t *dfa)
1614 int src, idx, ret;
1615 for (idx = 0; idx < dfa->nodes_len; ++idx)
1616 re_node_set_init_empty (dfa->inveclosures + idx);
1618 for (src = 0; src < dfa->nodes_len; ++src)
1620 int *elems = dfa->eclosures[src].elems;
1621 for (idx = 0; idx < dfa->eclosures[src].nelem; ++idx)
1623 ret = re_node_set_insert_last (dfa->inveclosures + elems[idx], src);
1624 if (BE (ret == -1, 0))
1625 return REG_ESPACE;
1629 return REG_NOERROR;
1632 /* Calculate "eclosure" for all the node in DFA. */
1634 static reg_errcode_t
1635 calc_eclosure (re_dfa_t *dfa)
1637 int node_idx, incomplete;
1638 #ifdef DEBUG
1639 assert (dfa->nodes_len > 0);
1640 #endif
1641 incomplete = 0;
1642 /* For each nodes, calculate epsilon closure. */
1643 for (node_idx = 0; ; ++node_idx)
1645 reg_errcode_t err;
1646 re_node_set eclosure_elem;
1647 if (node_idx == dfa->nodes_len)
1649 if (!incomplete)
1650 break;
1651 incomplete = 0;
1652 node_idx = 0;
1655 #ifdef DEBUG
1656 assert (dfa->eclosures[node_idx].nelem != -1);
1657 #endif
1659 /* If we have already calculated, skip it. */
1660 if (dfa->eclosures[node_idx].nelem != 0)
1661 continue;
1662 /* Calculate epsilon closure of `node_idx'. */
1663 err = calc_eclosure_iter (&eclosure_elem, dfa, node_idx, 1);
1664 if (BE (err != REG_NOERROR, 0))
1665 return err;
1667 if (dfa->eclosures[node_idx].nelem == 0)
1669 incomplete = 1;
1670 re_node_set_free (&eclosure_elem);
1673 return REG_NOERROR;
1676 /* Calculate epsilon closure of NODE. */
1678 static reg_errcode_t
1679 calc_eclosure_iter (re_node_set *new_set, re_dfa_t *dfa, int node, int root)
1681 reg_errcode_t err;
1682 int i;
1683 re_node_set eclosure;
1684 int ret;
1685 int incomplete = 0;
1686 err = re_node_set_alloc (&eclosure, dfa->edests[node].nelem + 1);
1687 if (BE (err != REG_NOERROR, 0))
1688 return err;
1690 /* This indicates that we are calculating this node now.
1691 We reference this value to avoid infinite loop. */
1692 dfa->eclosures[node].nelem = -1;
1694 /* If the current node has constraints, duplicate all nodes
1695 since they must inherit the constraints. */
1696 if (dfa->nodes[node].constraint
1697 && dfa->edests[node].nelem
1698 && !dfa->nodes[dfa->edests[node].elems[0]].duplicated)
1700 err = duplicate_node_closure (dfa, node, node, node,
1701 dfa->nodes[node].constraint);
1702 if (BE (err != REG_NOERROR, 0))
1703 return err;
1706 /* Expand each epsilon destination nodes. */
1707 if (IS_EPSILON_NODE(dfa->nodes[node].type))
1708 for (i = 0; i < dfa->edests[node].nelem; ++i)
1710 re_node_set eclosure_elem;
1711 int edest = dfa->edests[node].elems[i];
1712 /* If calculating the epsilon closure of `edest' is in progress,
1713 return intermediate result. */
1714 if (dfa->eclosures[edest].nelem == -1)
1716 incomplete = 1;
1717 continue;
1719 /* If we haven't calculated the epsilon closure of `edest' yet,
1720 calculate now. Otherwise use calculated epsilon closure. */
1721 if (dfa->eclosures[edest].nelem == 0)
1723 err = calc_eclosure_iter (&eclosure_elem, dfa, edest, 0);
1724 if (BE (err != REG_NOERROR, 0))
1725 return err;
1727 else
1728 eclosure_elem = dfa->eclosures[edest];
1729 /* Merge the epsilon closure of `edest'. */
1730 err = re_node_set_merge (&eclosure, &eclosure_elem);
1731 if (BE (err != REG_NOERROR, 0))
1732 return err;
1733 /* If the epsilon closure of `edest' is incomplete,
1734 the epsilon closure of this node is also incomplete. */
1735 if (dfa->eclosures[edest].nelem == 0)
1737 incomplete = 1;
1738 re_node_set_free (&eclosure_elem);
1742 /* An epsilon closure includes itself. */
1743 ret = re_node_set_insert (&eclosure, node);
1744 if (BE (ret < 0, 0))
1745 return REG_ESPACE;
1746 if (incomplete && !root)
1747 dfa->eclosures[node].nelem = 0;
1748 else
1749 dfa->eclosures[node] = eclosure;
1750 *new_set = eclosure;
1751 return REG_NOERROR;
1754 /* Functions for token which are used in the parser. */
1756 /* Fetch a token from INPUT.
1757 We must not use this function inside bracket expressions. */
1759 static void
1760 internal_function
1761 fetch_token (re_token_t *result, re_string_t *input, reg_syntax_t syntax)
1763 re_string_skip_bytes (input, peek_token (result, input, syntax));
1766 /* Peek a token from INPUT, and return the length of the token.
1767 We must not use this function inside bracket expressions. */
1769 static int
1770 internal_function
1771 peek_token (re_token_t *token, re_string_t *input, reg_syntax_t syntax)
1773 unsigned char c;
1775 if (re_string_eoi (input))
1777 token->type = END_OF_RE;
1778 return 0;
1781 c = re_string_peek_byte (input, 0);
1782 token->opr.c = c;
1784 token->word_char = 0;
1785 #ifdef RE_ENABLE_I18N
1786 token->mb_partial = 0;
1787 if (input->mb_cur_max > 1 &&
1788 !re_string_first_byte (input, re_string_cur_idx (input)))
1790 token->type = CHARACTER;
1791 token->mb_partial = 1;
1792 return 1;
1794 #endif
1795 if (c == '\\')
1797 unsigned char c2;
1798 if (re_string_cur_idx (input) + 1 >= re_string_length (input))
1800 token->type = BACK_SLASH;
1801 return 1;
1804 c2 = re_string_peek_byte_case (input, 1);
1805 token->opr.c = c2;
1806 token->type = CHARACTER;
1807 #ifdef RE_ENABLE_I18N
1808 if (input->mb_cur_max > 1)
1810 wint_t wc = re_string_wchar_at (input,
1811 re_string_cur_idx (input) + 1);
1812 token->word_char = IS_WIDE_WORD_CHAR (wc) != 0;
1814 else
1815 #endif
1816 token->word_char = IS_WORD_CHAR (c2) != 0;
1818 switch (c2)
1820 case '|':
1821 if (!(syntax & RE_LIMITED_OPS) && !(syntax & RE_NO_BK_VBAR))
1822 token->type = OP_ALT;
1823 break;
1824 case '1': case '2': case '3': case '4': case '5':
1825 case '6': case '7': case '8': case '9':
1826 if (!(syntax & RE_NO_BK_REFS))
1828 token->type = OP_BACK_REF;
1829 token->opr.idx = c2 - '1';
1831 break;
1832 case '<':
1833 if (!(syntax & RE_NO_GNU_OPS))
1835 token->type = ANCHOR;
1836 token->opr.ctx_type = WORD_FIRST;
1838 break;
1839 case '>':
1840 if (!(syntax & RE_NO_GNU_OPS))
1842 token->type = ANCHOR;
1843 token->opr.ctx_type = WORD_LAST;
1845 break;
1846 case 'b':
1847 if (!(syntax & RE_NO_GNU_OPS))
1849 token->type = ANCHOR;
1850 token->opr.ctx_type = WORD_DELIM;
1852 break;
1853 case 'B':
1854 if (!(syntax & RE_NO_GNU_OPS))
1856 token->type = ANCHOR;
1857 token->opr.ctx_type = NOT_WORD_DELIM;
1859 break;
1860 case 'w':
1861 if (!(syntax & RE_NO_GNU_OPS))
1862 token->type = OP_WORD;
1863 break;
1864 case 'W':
1865 if (!(syntax & RE_NO_GNU_OPS))
1866 token->type = OP_NOTWORD;
1867 break;
1868 case 's':
1869 if (!(syntax & RE_NO_GNU_OPS))
1870 token->type = OP_SPACE;
1871 break;
1872 case 'S':
1873 if (!(syntax & RE_NO_GNU_OPS))
1874 token->type = OP_NOTSPACE;
1875 break;
1876 case '`':
1877 if (!(syntax & RE_NO_GNU_OPS))
1879 token->type = ANCHOR;
1880 token->opr.ctx_type = BUF_FIRST;
1882 break;
1883 case '\'':
1884 if (!(syntax & RE_NO_GNU_OPS))
1886 token->type = ANCHOR;
1887 token->opr.ctx_type = BUF_LAST;
1889 break;
1890 case '(':
1891 if (!(syntax & RE_NO_BK_PARENS))
1892 token->type = OP_OPEN_SUBEXP;
1893 break;
1894 case ')':
1895 if (!(syntax & RE_NO_BK_PARENS))
1896 token->type = OP_CLOSE_SUBEXP;
1897 break;
1898 case '+':
1899 if (!(syntax & RE_LIMITED_OPS) && (syntax & RE_BK_PLUS_QM))
1900 token->type = OP_DUP_PLUS;
1901 break;
1902 case '?':
1903 if (!(syntax & RE_LIMITED_OPS) && (syntax & RE_BK_PLUS_QM))
1904 token->type = OP_DUP_QUESTION;
1905 break;
1906 case '{':
1907 if ((syntax & RE_INTERVALS) && (!(syntax & RE_NO_BK_BRACES)))
1908 token->type = OP_OPEN_DUP_NUM;
1909 break;
1910 case '}':
1911 if ((syntax & RE_INTERVALS) && (!(syntax & RE_NO_BK_BRACES)))
1912 token->type = OP_CLOSE_DUP_NUM;
1913 break;
1914 default:
1915 break;
1917 return 2;
1920 token->type = CHARACTER;
1921 #ifdef RE_ENABLE_I18N
1922 if (input->mb_cur_max > 1)
1924 wint_t wc = re_string_wchar_at (input, re_string_cur_idx (input));
1925 token->word_char = IS_WIDE_WORD_CHAR (wc) != 0;
1927 else
1928 #endif
1929 token->word_char = IS_WORD_CHAR (token->opr.c);
1931 switch (c)
1933 case '\n':
1934 if (syntax & RE_NEWLINE_ALT)
1935 token->type = OP_ALT;
1936 break;
1937 case '|':
1938 if (!(syntax & RE_LIMITED_OPS) && (syntax & RE_NO_BK_VBAR))
1939 token->type = OP_ALT;
1940 break;
1941 case '*':
1942 token->type = OP_DUP_ASTERISK;
1943 break;
1944 case '+':
1945 if (!(syntax & RE_LIMITED_OPS) && !(syntax & RE_BK_PLUS_QM))
1946 token->type = OP_DUP_PLUS;
1947 break;
1948 case '?':
1949 if (!(syntax & RE_LIMITED_OPS) && !(syntax & RE_BK_PLUS_QM))
1950 token->type = OP_DUP_QUESTION;
1951 break;
1952 case '{':
1953 if ((syntax & RE_INTERVALS) && (syntax & RE_NO_BK_BRACES))
1954 token->type = OP_OPEN_DUP_NUM;
1955 break;
1956 case '}':
1957 if ((syntax & RE_INTERVALS) && (syntax & RE_NO_BK_BRACES))
1958 token->type = OP_CLOSE_DUP_NUM;
1959 break;
1960 case '(':
1961 if (syntax & RE_NO_BK_PARENS)
1962 token->type = OP_OPEN_SUBEXP;
1963 break;
1964 case ')':
1965 if (syntax & RE_NO_BK_PARENS)
1966 token->type = OP_CLOSE_SUBEXP;
1967 break;
1968 case '[':
1969 token->type = OP_OPEN_BRACKET;
1970 break;
1971 case '.':
1972 token->type = OP_PERIOD;
1973 break;
1974 case '^':
1975 if (!(syntax & (RE_CONTEXT_INDEP_ANCHORS | RE_CARET_ANCHORS_HERE)) &&
1976 re_string_cur_idx (input) != 0)
1978 char prev = re_string_peek_byte (input, -1);
1979 if (!(syntax & RE_NEWLINE_ALT) || prev != '\n')
1980 break;
1982 token->type = ANCHOR;
1983 token->opr.ctx_type = LINE_FIRST;
1984 break;
1985 case '$':
1986 if (!(syntax & RE_CONTEXT_INDEP_ANCHORS) &&
1987 re_string_cur_idx (input) + 1 != re_string_length (input))
1989 re_token_t next;
1990 re_string_skip_bytes (input, 1);
1991 peek_token (&next, input, syntax);
1992 re_string_skip_bytes (input, -1);
1993 if (next.type != OP_ALT && next.type != OP_CLOSE_SUBEXP)
1994 break;
1996 token->type = ANCHOR;
1997 token->opr.ctx_type = LINE_LAST;
1998 break;
1999 default:
2000 break;
2002 return 1;
2005 /* Peek a token from INPUT, and return the length of the token.
2006 We must not use this function out of bracket expressions. */
2008 static int
2009 internal_function
2010 peek_token_bracket (re_token_t *token, re_string_t *input, reg_syntax_t syntax)
2012 unsigned char c;
2013 if (re_string_eoi (input))
2015 token->type = END_OF_RE;
2016 return 0;
2018 c = re_string_peek_byte (input, 0);
2019 token->opr.c = c;
2021 #ifdef RE_ENABLE_I18N
2022 if (input->mb_cur_max > 1 &&
2023 !re_string_first_byte (input, re_string_cur_idx (input)))
2025 token->type = CHARACTER;
2026 return 1;
2028 #endif /* RE_ENABLE_I18N */
2030 if (c == '\\' && (syntax & RE_BACKSLASH_ESCAPE_IN_LISTS)
2031 && re_string_cur_idx (input) + 1 < re_string_length (input))
2033 /* In this case, '\' escape a character. */
2034 unsigned char c2;
2035 re_string_skip_bytes (input, 1);
2036 c2 = re_string_peek_byte (input, 0);
2037 token->opr.c = c2;
2038 token->type = CHARACTER;
2039 return 1;
2041 if (c == '[') /* '[' is a special char in a bracket exps. */
2043 unsigned char c2;
2044 int token_len;
2045 if (re_string_cur_idx (input) + 1 < re_string_length (input))
2046 c2 = re_string_peek_byte (input, 1);
2047 else
2048 c2 = 0;
2049 token->opr.c = c2;
2050 token_len = 2;
2051 switch (c2)
2053 case '.':
2054 token->type = OP_OPEN_COLL_ELEM;
2055 break;
2056 case '=':
2057 token->type = OP_OPEN_EQUIV_CLASS;
2058 break;
2059 case ':':
2060 if (syntax & RE_CHAR_CLASSES)
2062 token->type = OP_OPEN_CHAR_CLASS;
2063 break;
2065 /* else fall through. */
2066 default:
2067 token->type = CHARACTER;
2068 token->opr.c = c;
2069 token_len = 1;
2070 break;
2072 return token_len;
2074 switch (c)
2076 case '-':
2077 token->type = OP_CHARSET_RANGE;
2078 break;
2079 case ']':
2080 token->type = OP_CLOSE_BRACKET;
2081 break;
2082 case '^':
2083 token->type = OP_NON_MATCH_LIST;
2084 break;
2085 default:
2086 token->type = CHARACTER;
2088 return 1;
2091 /* Functions for parser. */
2093 /* Entry point of the parser.
2094 Parse the regular expression REGEXP and return the structure tree.
2095 If an error is occured, ERR is set by error code, and return NULL.
2096 This function build the following tree, from regular expression <reg_exp>:
2100 <reg_exp> EOR
2102 CAT means concatenation.
2103 EOR means end of regular expression. */
2105 static bin_tree_t *
2106 parse (re_string_t *regexp, regex_t *preg, reg_syntax_t syntax,
2107 reg_errcode_t *err)
2109 re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
2110 bin_tree_t *tree, *eor, *root;
2111 re_token_t current_token;
2112 dfa->syntax = syntax;
2113 fetch_token (&current_token, regexp, syntax | RE_CARET_ANCHORS_HERE);
2114 tree = parse_reg_exp (regexp, preg, &current_token, syntax, 0, err);
2115 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2116 return NULL;
2117 eor = create_tree (dfa, NULL, NULL, END_OF_RE);
2118 if (tree != NULL)
2119 root = create_tree (dfa, tree, eor, CONCAT);
2120 else
2121 root = eor;
2122 if (BE (eor == NULL || root == NULL, 0))
2124 *err = REG_ESPACE;
2125 return NULL;
2127 return root;
2130 /* This function build the following tree, from regular expression
2131 <branch1>|<branch2>:
2135 <branch1> <branch2>
2137 ALT means alternative, which represents the operator `|'. */
2139 static bin_tree_t *
2140 parse_reg_exp (re_string_t *regexp, regex_t *preg, re_token_t *token,
2141 reg_syntax_t syntax, int nest, reg_errcode_t *err)
2143 re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
2144 bin_tree_t *tree, *branch = NULL;
2145 tree = parse_branch (regexp, preg, token, syntax, nest, err);
2146 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2147 return NULL;
2149 while (token->type == OP_ALT)
2151 fetch_token (token, regexp, syntax | RE_CARET_ANCHORS_HERE);
2152 if (token->type != OP_ALT && token->type != END_OF_RE
2153 && (nest == 0 || token->type != OP_CLOSE_SUBEXP))
2155 branch = parse_branch (regexp, preg, token, syntax, nest, err);
2156 if (BE (*err != REG_NOERROR && branch == NULL, 0))
2157 return NULL;
2159 else
2160 branch = NULL;
2161 tree = create_tree (dfa, tree, branch, OP_ALT);
2162 if (BE (tree == NULL, 0))
2164 *err = REG_ESPACE;
2165 return NULL;
2168 return tree;
2171 /* This function build the following tree, from regular expression
2172 <exp1><exp2>:
2176 <exp1> <exp2>
2178 CAT means concatenation. */
2180 static bin_tree_t *
2181 parse_branch (re_string_t *regexp, regex_t *preg, re_token_t *token,
2182 reg_syntax_t syntax, int nest, reg_errcode_t *err)
2184 bin_tree_t *tree, *exp;
2185 re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
2186 tree = parse_expression (regexp, preg, token, syntax, nest, err);
2187 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2188 return NULL;
2190 while (token->type != OP_ALT && token->type != END_OF_RE
2191 && (nest == 0 || token->type != OP_CLOSE_SUBEXP))
2193 exp = parse_expression (regexp, preg, token, syntax, nest, err);
2194 if (BE (*err != REG_NOERROR && exp == NULL, 0))
2196 if (tree != NULL)
2197 postorder (tree, free_tree, NULL);
2198 return NULL;
2200 if (tree != NULL && exp != NULL)
2202 bin_tree_t *newtree = create_tree (dfa, tree, exp, CONCAT);
2203 if (newtree == NULL)
2205 postorder (exp, free_tree, NULL);
2206 postorder (tree, free_tree, NULL);
2207 *err = REG_ESPACE;
2208 return NULL;
2210 tree = newtree;
2212 else if (tree == NULL)
2213 tree = exp;
2214 /* Otherwise exp == NULL, we don't need to create new tree. */
2216 return tree;
2219 /* This function build the following tree, from regular expression a*:
2225 static bin_tree_t *
2226 parse_expression (re_string_t *regexp, regex_t *preg, re_token_t *token,
2227 reg_syntax_t syntax, int nest, reg_errcode_t *err)
2229 re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
2230 bin_tree_t *tree;
2231 switch (token->type)
2233 case CHARACTER:
2234 tree = create_token_tree (dfa, NULL, NULL, token);
2235 if (BE (tree == NULL, 0))
2237 *err = REG_ESPACE;
2238 return NULL;
2240 #ifdef RE_ENABLE_I18N
2241 if (dfa->mb_cur_max > 1)
2243 while (!re_string_eoi (regexp)
2244 && !re_string_first_byte (regexp, re_string_cur_idx (regexp)))
2246 bin_tree_t *mbc_remain;
2247 fetch_token (token, regexp, syntax);
2248 mbc_remain = create_token_tree (dfa, NULL, NULL, token);
2249 tree = create_tree (dfa, tree, mbc_remain, CONCAT);
2250 if (BE (mbc_remain == NULL || tree == NULL, 0))
2252 *err = REG_ESPACE;
2253 return NULL;
2257 #endif
2258 break;
2259 case OP_OPEN_SUBEXP:
2260 tree = parse_sub_exp (regexp, preg, token, syntax, nest + 1, err);
2261 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2262 return NULL;
2263 break;
2264 case OP_OPEN_BRACKET:
2265 tree = parse_bracket_exp (regexp, dfa, token, syntax, err);
2266 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2267 return NULL;
2268 break;
2269 case OP_BACK_REF:
2270 if (!BE (dfa->completed_bkref_map & (1 << token->opr.idx), 1))
2272 *err = REG_ESUBREG;
2273 return NULL;
2275 dfa->used_bkref_map |= 1 << token->opr.idx;
2276 tree = create_token_tree (dfa, NULL, NULL, token);
2277 if (BE (tree == NULL, 0))
2279 *err = REG_ESPACE;
2280 return NULL;
2282 ++dfa->nbackref;
2283 dfa->has_mb_node = 1;
2284 break;
2285 case OP_OPEN_DUP_NUM:
2286 if (syntax & RE_CONTEXT_INVALID_DUP)
2288 *err = REG_BADRPT;
2289 return NULL;
2291 /* FALLTHROUGH */
2292 case OP_DUP_ASTERISK:
2293 case OP_DUP_PLUS:
2294 case OP_DUP_QUESTION:
2295 if (syntax & RE_CONTEXT_INVALID_OPS)
2297 *err = REG_BADRPT;
2298 return NULL;
2300 else if (syntax & RE_CONTEXT_INDEP_OPS)
2302 fetch_token (token, regexp, syntax);
2303 return parse_expression (regexp, preg, token, syntax, nest, err);
2305 /* else fall through */
2306 case OP_CLOSE_SUBEXP:
2307 if ((token->type == OP_CLOSE_SUBEXP) &&
2308 !(syntax & RE_UNMATCHED_RIGHT_PAREN_ORD))
2310 *err = REG_ERPAREN;
2311 return NULL;
2313 /* else fall through */
2314 case OP_CLOSE_DUP_NUM:
2315 /* We treat it as a normal character. */
2317 /* Then we can these characters as normal characters. */
2318 token->type = CHARACTER;
2319 /* mb_partial and word_char bits should be initialized already
2320 by peek_token. */
2321 tree = create_token_tree (dfa, NULL, NULL, token);
2322 if (BE (tree == NULL, 0))
2324 *err = REG_ESPACE;
2325 return NULL;
2327 break;
2328 case ANCHOR:
2329 if ((token->opr.ctx_type
2330 & (WORD_DELIM | NOT_WORD_DELIM | WORD_FIRST | WORD_LAST))
2331 && dfa->word_ops_used == 0)
2332 init_word_char (dfa);
2333 if (token->opr.ctx_type == WORD_DELIM
2334 || token->opr.ctx_type == NOT_WORD_DELIM)
2336 bin_tree_t *tree_first, *tree_last;
2337 if (token->opr.ctx_type == WORD_DELIM)
2339 token->opr.ctx_type = WORD_FIRST;
2340 tree_first = create_token_tree (dfa, NULL, NULL, token);
2341 token->opr.ctx_type = WORD_LAST;
2343 else
2345 token->opr.ctx_type = INSIDE_WORD;
2346 tree_first = create_token_tree (dfa, NULL, NULL, token);
2347 token->opr.ctx_type = INSIDE_NOTWORD;
2349 tree_last = create_token_tree (dfa, NULL, NULL, token);
2350 tree = create_tree (dfa, tree_first, tree_last, OP_ALT);
2351 if (BE (tree_first == NULL || tree_last == NULL || tree == NULL, 0))
2353 *err = REG_ESPACE;
2354 return NULL;
2357 else
2359 tree = create_token_tree (dfa, NULL, NULL, token);
2360 if (BE (tree == NULL, 0))
2362 *err = REG_ESPACE;
2363 return NULL;
2366 /* We must return here, since ANCHORs can't be followed
2367 by repetition operators.
2368 eg. RE"^*" is invalid or "<ANCHOR(^)><CHAR(*)>",
2369 it must not be "<ANCHOR(^)><REPEAT(*)>". */
2370 fetch_token (token, regexp, syntax);
2371 return tree;
2372 case OP_PERIOD:
2373 tree = create_token_tree (dfa, NULL, NULL, token);
2374 if (BE (tree == NULL, 0))
2376 *err = REG_ESPACE;
2377 return NULL;
2379 if (dfa->mb_cur_max > 1)
2380 dfa->has_mb_node = 1;
2381 break;
2382 case OP_WORD:
2383 case OP_NOTWORD:
2384 tree = build_charclass_op (dfa, regexp->trans,
2385 (const unsigned char *) "alnum",
2386 (const unsigned char *) "_",
2387 token->type == OP_NOTWORD, err);
2388 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2389 return NULL;
2390 break;
2391 case OP_SPACE:
2392 case OP_NOTSPACE:
2393 tree = build_charclass_op (dfa, regexp->trans,
2394 (const unsigned char *) "space",
2395 (const unsigned char *) "",
2396 token->type == OP_NOTSPACE, err);
2397 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2398 return NULL;
2399 break;
2400 case OP_ALT:
2401 case END_OF_RE:
2402 return NULL;
2403 case BACK_SLASH:
2404 *err = REG_EESCAPE;
2405 return NULL;
2406 default:
2407 /* Must not happen? */
2408 #ifdef DEBUG
2409 assert (0);
2410 #endif
2411 return NULL;
2413 fetch_token (token, regexp, syntax);
2415 while (token->type == OP_DUP_ASTERISK || token->type == OP_DUP_PLUS
2416 || token->type == OP_DUP_QUESTION || token->type == OP_OPEN_DUP_NUM)
2418 tree = parse_dup_op (tree, regexp, dfa, token, syntax, err);
2419 if (BE (*err != REG_NOERROR && tree == NULL, 0))
2420 return NULL;
2421 /* In BRE consecutive duplications are not allowed. */
2422 if ((syntax & RE_CONTEXT_INVALID_DUP)
2423 && (token->type == OP_DUP_ASTERISK
2424 || token->type == OP_OPEN_DUP_NUM))
2426 *err = REG_BADRPT;
2427 return NULL;
2431 return tree;
2434 /* This function build the following tree, from regular expression
2435 (<reg_exp>):
2436 SUBEXP
2438 <reg_exp>
2441 static bin_tree_t *
2442 parse_sub_exp (re_string_t *regexp, regex_t *preg, re_token_t *token,
2443 reg_syntax_t syntax, int nest, reg_errcode_t *err)
2445 re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
2446 bin_tree_t *tree;
2447 size_t cur_nsub;
2448 cur_nsub = preg->re_nsub++;
2450 fetch_token (token, regexp, syntax | RE_CARET_ANCHORS_HERE);
2452 /* The subexpression may be a null string. */
2453 if (token->type == OP_CLOSE_SUBEXP)
2454 tree = NULL;
2455 else
2457 tree = parse_reg_exp (regexp, preg, token, syntax, nest, err);
2458 if (BE (*err == REG_NOERROR && token->type != OP_CLOSE_SUBEXP, 0))
2460 if (tree != NULL)
2461 postorder (tree, free_tree, NULL);
2462 *err = REG_EPAREN;
2464 if (BE (*err != REG_NOERROR, 0))
2465 return NULL;
2468 if (cur_nsub <= '9' - '1')
2469 dfa->completed_bkref_map |= 1 << cur_nsub;
2471 tree = create_tree (dfa, tree, NULL, SUBEXP);
2472 if (BE (tree == NULL, 0))
2474 *err = REG_ESPACE;
2475 return NULL;
2477 tree->token.opr.idx = cur_nsub;
2478 return tree;
2481 /* This function parse repetition operators like "*", "+", "{1,3}" etc. */
2483 static bin_tree_t *
2484 parse_dup_op (bin_tree_t *elem, re_string_t *regexp, re_dfa_t *dfa,
2485 re_token_t *token, reg_syntax_t syntax, reg_errcode_t *err)
2487 bin_tree_t *tree = NULL, *old_tree = NULL;
2488 int i, start, end, start_idx = re_string_cur_idx (regexp);
2489 re_token_t start_token = *token;
2491 if (token->type == OP_OPEN_DUP_NUM)
2493 end = 0;
2494 start = fetch_number (regexp, token, syntax);
2495 if (start == -1)
2497 if (token->type == CHARACTER && token->opr.c == ',')
2498 start = 0; /* We treat "{,m}" as "{0,m}". */
2499 else
2501 *err = REG_BADBR; /* <re>{} is invalid. */
2502 return NULL;
2505 if (BE (start != -2, 1))
2507 /* We treat "{n}" as "{n,n}". */
2508 end = ((token->type == OP_CLOSE_DUP_NUM) ? start
2509 : ((token->type == CHARACTER && token->opr.c == ',')
2510 ? fetch_number (regexp, token, syntax) : -2));
2512 if (BE (start == -2 || end == -2, 0))
2514 /* Invalid sequence. */
2515 if (BE (!(syntax & RE_INVALID_INTERVAL_ORD), 0))
2517 if (token->type == END_OF_RE)
2518 *err = REG_EBRACE;
2519 else
2520 *err = REG_BADBR;
2522 return NULL;
2525 /* If the syntax bit is set, rollback. */
2526 re_string_set_index (regexp, start_idx);
2527 *token = start_token;
2528 token->type = CHARACTER;
2529 /* mb_partial and word_char bits should be already initialized by
2530 peek_token. */
2531 return elem;
2534 if (BE ((end != -1 && start > end) || token->type != OP_CLOSE_DUP_NUM, 0))
2536 /* First number greater than second. */
2537 *err = REG_BADBR;
2538 return NULL;
2541 else
2543 start = (token->type == OP_DUP_PLUS) ? 1 : 0;
2544 end = (token->type == OP_DUP_QUESTION) ? 1 : -1;
2547 fetch_token (token, regexp, syntax);
2549 if (BE (elem == NULL, 0))
2550 return NULL;
2551 if (BE (start == 0 && end == 0, 0))
2553 postorder (elem, free_tree, NULL);
2554 return NULL;
2557 /* Extract "<re>{n,m}" to "<re><re>...<re><re>{0,<m-n>}". */
2558 if (BE (start > 0, 0))
2560 tree = elem;
2561 for (i = 2; i <= start; ++i)
2563 elem = duplicate_tree (elem, dfa);
2564 tree = create_tree (dfa, tree, elem, CONCAT);
2565 if (BE (elem == NULL || tree == NULL, 0))
2566 goto parse_dup_op_espace;
2569 if (start == end)
2570 return tree;
2572 /* Duplicate ELEM before it is marked optional. */
2573 elem = duplicate_tree (elem, dfa);
2574 old_tree = tree;
2576 else
2577 old_tree = NULL;
2579 if (elem->token.type == SUBEXP)
2580 postorder (elem, mark_opt_subexp, (void *) (long) elem->token.opr.idx);
2582 tree = create_tree (dfa, elem, NULL, (end == -1 ? OP_DUP_ASTERISK : OP_ALT));
2583 if (BE (tree == NULL, 0))
2584 goto parse_dup_op_espace;
2586 /* This loop is actually executed only when end != -1,
2587 to rewrite <re>{0,n} as (<re>(<re>...<re>?)?)?... We have
2588 already created the start+1-th copy. */
2589 for (i = start + 2; i <= end; ++i)
2591 elem = duplicate_tree (elem, dfa);
2592 tree = create_tree (dfa, tree, elem, CONCAT);
2593 if (BE (elem == NULL || tree == NULL, 0))
2594 goto parse_dup_op_espace;
2596 tree = create_tree (dfa, tree, NULL, OP_ALT);
2597 if (BE (tree == NULL, 0))
2598 goto parse_dup_op_espace;
2601 if (old_tree)
2602 tree = create_tree (dfa, old_tree, tree, CONCAT);
2604 return tree;
2606 parse_dup_op_espace:
2607 *err = REG_ESPACE;
2608 return NULL;
2611 /* Size of the names for collating symbol/equivalence_class/character_class.
2612 I'm not sure, but maybe enough. */
2613 #define BRACKET_NAME_BUF_SIZE 32
2615 #ifndef _LIBC
2616 /* Local function for parse_bracket_exp only used in case of NOT _LIBC.
2617 Build the range expression which starts from START_ELEM, and ends
2618 at END_ELEM. The result are written to MBCSET and SBCSET.
2619 RANGE_ALLOC is the allocated size of mbcset->range_starts, and
2620 mbcset->range_ends, is a pointer argument sinse we may
2621 update it. */
2623 static reg_errcode_t
2624 internal_function
2625 # ifdef RE_ENABLE_I18N
2626 build_range_exp (bitset_t sbcset, re_charset_t *mbcset, int *range_alloc,
2627 bracket_elem_t *start_elem, bracket_elem_t *end_elem)
2628 # else /* not RE_ENABLE_I18N */
2629 build_range_exp (bitset_t sbcset, bracket_elem_t *start_elem,
2630 bracket_elem_t *end_elem)
2631 # endif /* not RE_ENABLE_I18N */
2633 unsigned int start_ch, end_ch;
2634 /* Equivalence Classes and Character Classes can't be a range start/end. */
2635 if (BE (start_elem->type == EQUIV_CLASS || start_elem->type == CHAR_CLASS
2636 || end_elem->type == EQUIV_CLASS || end_elem->type == CHAR_CLASS,
2638 return REG_ERANGE;
2640 /* We can handle no multi character collating elements without libc
2641 support. */
2642 if (BE ((start_elem->type == COLL_SYM
2643 && strlen ((char *) start_elem->opr.name) > 1)
2644 || (end_elem->type == COLL_SYM
2645 && strlen ((char *) end_elem->opr.name) > 1), 0))
2646 return REG_ECOLLATE;
2648 # ifdef RE_ENABLE_I18N
2650 wchar_t wc;
2651 wint_t start_wc;
2652 wint_t end_wc;
2653 wchar_t cmp_buf[6] = {L'\0', L'\0', L'\0', L'\0', L'\0', L'\0'};
2655 start_ch = ((start_elem->type == SB_CHAR) ? start_elem->opr.ch
2656 : ((start_elem->type == COLL_SYM) ? start_elem->opr.name[0]
2657 : 0));
2658 end_ch = ((end_elem->type == SB_CHAR) ? end_elem->opr.ch
2659 : ((end_elem->type == COLL_SYM) ? end_elem->opr.name[0]
2660 : 0));
2661 start_wc = ((start_elem->type == SB_CHAR || start_elem->type == COLL_SYM)
2662 ? __btowc (start_ch) : start_elem->opr.wch);
2663 end_wc = ((end_elem->type == SB_CHAR || end_elem->type == COLL_SYM)
2664 ? __btowc (end_ch) : end_elem->opr.wch);
2665 if (start_wc == WEOF || end_wc == WEOF)
2666 return REG_ECOLLATE;
2667 cmp_buf[0] = start_wc;
2668 cmp_buf[4] = end_wc;
2669 if (wcscoll (cmp_buf, cmp_buf + 4) > 0)
2670 return REG_ERANGE;
2672 /* Got valid collation sequence values, add them as a new entry.
2673 However, for !_LIBC we have no collation elements: if the
2674 character set is single byte, the single byte character set
2675 that we build below suffices. parse_bracket_exp passes
2676 no MBCSET if dfa->mb_cur_max == 1. */
2677 if (mbcset)
2679 /* Check the space of the arrays. */
2680 if (BE (*range_alloc == mbcset->nranges, 0))
2682 /* There is not enough space, need realloc. */
2683 wchar_t *new_array_start, *new_array_end;
2684 int new_nranges;
2686 /* +1 in case of mbcset->nranges is 0. */
2687 new_nranges = 2 * mbcset->nranges + 1;
2688 /* Use realloc since mbcset->range_starts and mbcset->range_ends
2689 are NULL if *range_alloc == 0. */
2690 new_array_start = re_realloc (mbcset->range_starts, wchar_t,
2691 new_nranges);
2692 new_array_end = re_realloc (mbcset->range_ends, wchar_t,
2693 new_nranges);
2695 if (BE (new_array_start == NULL || new_array_end == NULL, 0))
2696 return REG_ESPACE;
2698 mbcset->range_starts = new_array_start;
2699 mbcset->range_ends = new_array_end;
2700 *range_alloc = new_nranges;
2703 mbcset->range_starts[mbcset->nranges] = start_wc;
2704 mbcset->range_ends[mbcset->nranges++] = end_wc;
2707 /* Build the table for single byte characters. */
2708 for (wc = 0; wc < SBC_MAX; ++wc)
2710 cmp_buf[2] = wc;
2711 if (wcscoll (cmp_buf, cmp_buf + 2) <= 0
2712 && wcscoll (cmp_buf + 2, cmp_buf + 4) <= 0)
2713 bitset_set (sbcset, wc);
2716 # else /* not RE_ENABLE_I18N */
2718 unsigned int ch;
2719 start_ch = ((start_elem->type == SB_CHAR ) ? start_elem->opr.ch
2720 : ((start_elem->type == COLL_SYM) ? start_elem->opr.name[0]
2721 : 0));
2722 end_ch = ((end_elem->type == SB_CHAR ) ? end_elem->opr.ch
2723 : ((end_elem->type == COLL_SYM) ? end_elem->opr.name[0]
2724 : 0));
2725 if (start_ch > end_ch)
2726 return REG_ERANGE;
2727 /* Build the table for single byte characters. */
2728 for (ch = 0; ch < SBC_MAX; ++ch)
2729 if (start_ch <= ch && ch <= end_ch)
2730 bitset_set (sbcset, ch);
2732 # endif /* not RE_ENABLE_I18N */
2733 return REG_NOERROR;
2735 #endif /* not _LIBC */
2737 #ifndef _LIBC
2738 /* Helper function for parse_bracket_exp only used in case of NOT _LIBC..
2739 Build the collating element which is represented by NAME.
2740 The result are written to MBCSET and SBCSET.
2741 COLL_SYM_ALLOC is the allocated size of mbcset->coll_sym, is a
2742 pointer argument since we may update it. */
2744 static reg_errcode_t
2745 internal_function
2746 # ifdef RE_ENABLE_I18N
2747 build_collating_symbol (bitset_t sbcset, re_charset_t *mbcset,
2748 int *coll_sym_alloc, const unsigned char *name)
2749 # else /* not RE_ENABLE_I18N */
2750 build_collating_symbol (bitset_t sbcset, const unsigned char *name)
2751 # endif /* not RE_ENABLE_I18N */
2753 size_t name_len = strlen ((const char *) name);
2754 if (BE (name_len != 1, 0))
2755 return REG_ECOLLATE;
2756 else
2758 bitset_set (sbcset, name[0]);
2759 return REG_NOERROR;
2762 #endif /* not _LIBC */
2764 /* This function parse bracket expression like "[abc]", "[a-c]",
2765 "[[.a-a.]]" etc. */
2767 static bin_tree_t *
2768 parse_bracket_exp (re_string_t *regexp, re_dfa_t *dfa, re_token_t *token,
2769 reg_syntax_t syntax, reg_errcode_t *err)
2771 #ifdef _LIBC
2772 const unsigned char *collseqmb;
2773 const char *collseqwc;
2774 uint32_t nrules;
2775 int32_t table_size;
2776 const int32_t *symb_table;
2777 const unsigned char *extra;
2779 /* Local function for parse_bracket_exp used in _LIBC environement.
2780 Seek the collating symbol entry correspondings to NAME.
2781 Return the index of the symbol in the SYMB_TABLE,
2782 or -1 if not found. */
2784 auto inline int32_t
2785 __attribute ((always_inline))
2786 seek_collating_symbol_entry (const unsigned char *name, size_t name_len)
2788 int32_t elem;
2790 for (elem = 0; elem < table_size; elem++)
2791 if (symb_table[2 * elem] != 0)
2793 int32_t idx = symb_table[2 * elem + 1];
2794 /* Skip the name of collating element name. */
2795 idx += 1 + extra[idx];
2796 if (/* Compare the length of the name. */
2797 name_len == extra[idx]
2798 /* Compare the name. */
2799 && memcmp (name, &extra[idx + 1], name_len) == 0)
2800 /* Yep, this is the entry. */
2801 return elem;
2803 return -1;
2806 /* Local function for parse_bracket_exp used in _LIBC environment.
2807 Look up the collation sequence value of BR_ELEM.
2808 Return the value if succeeded, UINT_MAX otherwise. */
2810 auto inline unsigned int
2811 __attribute ((always_inline))
2812 lookup_collation_sequence_value (bracket_elem_t *br_elem)
2814 if (br_elem->type == SB_CHAR)
2817 if (MB_CUR_MAX == 1)
2819 if (nrules == 0)
2820 return collseqmb[br_elem->opr.ch];
2821 else
2823 wint_t wc = __btowc (br_elem->opr.ch);
2824 return __collseq_table_lookup (collseqwc, wc);
2827 else if (br_elem->type == MB_CHAR)
2829 if (nrules != 0)
2830 return __collseq_table_lookup (collseqwc, br_elem->opr.wch);
2832 else if (br_elem->type == COLL_SYM)
2834 size_t sym_name_len = strlen ((char *) br_elem->opr.name);
2835 if (nrules != 0)
2837 int32_t elem, idx;
2838 elem = seek_collating_symbol_entry (br_elem->opr.name,
2839 sym_name_len);
2840 if (elem != -1)
2842 /* We found the entry. */
2843 idx = symb_table[2 * elem + 1];
2844 /* Skip the name of collating element name. */
2845 idx += 1 + extra[idx];
2846 /* Skip the byte sequence of the collating element. */
2847 idx += 1 + extra[idx];
2848 /* Adjust for the alignment. */
2849 idx = (idx + 3) & ~3;
2850 /* Skip the multibyte collation sequence value. */
2851 idx += sizeof (unsigned int);
2852 /* Skip the wide char sequence of the collating element. */
2853 idx += sizeof (unsigned int) *
2854 (1 + *(unsigned int *) (extra + idx));
2855 /* Return the collation sequence value. */
2856 return *(unsigned int *) (extra + idx);
2858 else if (sym_name_len == 1)
2860 /* No valid character. Match it as a single byte
2861 character. */
2862 return collseqmb[br_elem->opr.name[0]];
2865 else if (sym_name_len == 1)
2866 return collseqmb[br_elem->opr.name[0]];
2868 return UINT_MAX;
2871 /* Local function for parse_bracket_exp used in _LIBC environement.
2872 Build the range expression which starts from START_ELEM, and ends
2873 at END_ELEM. The result are written to MBCSET and SBCSET.
2874 RANGE_ALLOC is the allocated size of mbcset->range_starts, and
2875 mbcset->range_ends, is a pointer argument sinse we may
2876 update it. */
2878 auto inline reg_errcode_t
2879 __attribute ((always_inline))
2880 build_range_exp (bitset_t sbcset, re_charset_t *mbcset, int *range_alloc,
2881 bracket_elem_t *start_elem, bracket_elem_t *end_elem)
2883 unsigned int ch;
2884 uint32_t start_collseq;
2885 uint32_t end_collseq;
2887 /* Equivalence Classes and Character Classes can't be a range
2888 start/end. */
2889 if (BE (start_elem->type == EQUIV_CLASS || start_elem->type == CHAR_CLASS
2890 || end_elem->type == EQUIV_CLASS || end_elem->type == CHAR_CLASS,
2892 return REG_ERANGE;
2894 start_collseq = lookup_collation_sequence_value (start_elem);
2895 end_collseq = lookup_collation_sequence_value (end_elem);
2896 /* Check start/end collation sequence values. */
2897 if (BE (start_collseq == UINT_MAX || end_collseq == UINT_MAX, 0))
2898 return REG_ECOLLATE;
2899 if (BE ((syntax & RE_NO_EMPTY_RANGES) && start_collseq > end_collseq, 0))
2900 return REG_ERANGE;
2902 /* Got valid collation sequence values, add them as a new entry.
2903 However, if we have no collation elements, and the character set
2904 is single byte, the single byte character set that we
2905 build below suffices. */
2906 if (nrules > 0 || dfa->mb_cur_max > 1)
2908 /* Check the space of the arrays. */
2909 if (BE (*range_alloc == mbcset->nranges, 0))
2911 /* There is not enough space, need realloc. */
2912 uint32_t *new_array_start;
2913 uint32_t *new_array_end;
2914 int new_nranges;
2916 /* +1 in case of mbcset->nranges is 0. */
2917 new_nranges = 2 * mbcset->nranges + 1;
2918 new_array_start = re_realloc (mbcset->range_starts, uint32_t,
2919 new_nranges);
2920 new_array_end = re_realloc (mbcset->range_ends, uint32_t,
2921 new_nranges);
2923 if (BE (new_array_start == NULL || new_array_end == NULL, 0))
2924 return REG_ESPACE;
2926 mbcset->range_starts = new_array_start;
2927 mbcset->range_ends = new_array_end;
2928 *range_alloc = new_nranges;
2931 mbcset->range_starts[mbcset->nranges] = start_collseq;
2932 mbcset->range_ends[mbcset->nranges++] = end_collseq;
2935 /* Build the table for single byte characters. */
2936 for (ch = 0; ch < SBC_MAX; ch++)
2938 uint32_t ch_collseq;
2940 if (MB_CUR_MAX == 1)
2942 if (nrules == 0)
2943 ch_collseq = collseqmb[ch];
2944 else
2945 ch_collseq = __collseq_table_lookup (collseqwc, __btowc (ch));
2946 if (start_collseq <= ch_collseq && ch_collseq <= end_collseq)
2947 bitset_set (sbcset, ch);
2949 return REG_NOERROR;
2952 /* Local function for parse_bracket_exp used in _LIBC environement.
2953 Build the collating element which is represented by NAME.
2954 The result are written to MBCSET and SBCSET.
2955 COLL_SYM_ALLOC is the allocated size of mbcset->coll_sym, is a
2956 pointer argument sinse we may update it. */
2958 auto inline reg_errcode_t
2959 __attribute ((always_inline))
2960 build_collating_symbol (bitset_t sbcset, re_charset_t *mbcset,
2961 int *coll_sym_alloc, const unsigned char *name)
2963 int32_t elem, idx;
2964 size_t name_len = strlen ((const char *) name);
2965 if (nrules != 0)
2967 elem = seek_collating_symbol_entry (name, name_len);
2968 if (elem != -1)
2970 /* We found the entry. */
2971 idx = symb_table[2 * elem + 1];
2972 /* Skip the name of collating element name. */
2973 idx += 1 + extra[idx];
2975 else if (name_len == 1)
2977 /* No valid character, treat it as a normal
2978 character. */
2979 bitset_set (sbcset, name[0]);
2980 return REG_NOERROR;
2982 else
2983 return REG_ECOLLATE;
2985 /* Got valid collation sequence, add it as a new entry. */
2986 /* Check the space of the arrays. */
2987 if (BE (*coll_sym_alloc == mbcset->ncoll_syms, 0))
2989 /* Not enough, realloc it. */
2990 /* +1 in case of mbcset->ncoll_syms is 0. */
2991 int new_coll_sym_alloc = 2 * mbcset->ncoll_syms + 1;
2992 /* Use realloc since mbcset->coll_syms is NULL
2993 if *alloc == 0. */
2994 int32_t *new_coll_syms = re_realloc (mbcset->coll_syms, int32_t,
2995 new_coll_sym_alloc);
2996 if (BE (new_coll_syms == NULL, 0))
2997 return REG_ESPACE;
2998 mbcset->coll_syms = new_coll_syms;
2999 *coll_sym_alloc = new_coll_sym_alloc;
3001 mbcset->coll_syms[mbcset->ncoll_syms++] = idx;
3002 return REG_NOERROR;
3004 else
3006 if (BE (name_len != 1, 0))
3007 return REG_ECOLLATE;
3008 else
3010 bitset_set (sbcset, name[0]);
3011 return REG_NOERROR;
3015 #endif
3017 re_token_t br_token;
3018 re_bitset_ptr_t sbcset;
3019 #ifdef RE_ENABLE_I18N
3020 re_charset_t *mbcset;
3021 int coll_sym_alloc = 0, range_alloc = 0, mbchar_alloc = 0;
3022 int equiv_class_alloc = 0, char_class_alloc = 0;
3023 #endif /* not RE_ENABLE_I18N */
3024 int non_match = 0;
3025 bin_tree_t *work_tree;
3026 int token_len;
3027 int first_round = 1;
3028 #ifdef _LIBC
3029 collseqmb = (const unsigned char *)
3030 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQMB);
3031 nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
3032 if (nrules)
3035 if (MB_CUR_MAX > 1)
3037 collseqwc = _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQWC);
3038 table_size = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_SYMB_HASH_SIZEMB);
3039 symb_table = (const int32_t *) _NL_CURRENT (LC_COLLATE,
3040 _NL_COLLATE_SYMB_TABLEMB);
3041 extra = (const unsigned char *) _NL_CURRENT (LC_COLLATE,
3042 _NL_COLLATE_SYMB_EXTRAMB);
3044 #endif
3045 sbcset = (re_bitset_ptr_t) calloc (sizeof (bitset_t), 1);
3046 #ifdef RE_ENABLE_I18N
3047 mbcset = (re_charset_t *) calloc (sizeof (re_charset_t), 1);
3048 #endif /* RE_ENABLE_I18N */
3049 #ifdef RE_ENABLE_I18N
3050 if (BE (sbcset == NULL || mbcset == NULL, 0))
3051 #else
3052 if (BE (sbcset == NULL, 0))
3053 #endif /* RE_ENABLE_I18N */
3055 re_free (sbcset);
3056 #ifdef RE_ENABLE_I18N
3057 re_free (mbcset);
3058 #endif
3059 *err = REG_ESPACE;
3060 return NULL;
3063 token_len = peek_token_bracket (token, regexp, syntax);
3064 if (BE (token->type == END_OF_RE, 0))
3066 *err = REG_BADPAT;
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 */
3074 non_match = 1;
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))
3081 *err = REG_BADPAT;
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;
3090 while (1)
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];
3095 reg_errcode_t ret;
3096 int token_len2 = 0, is_range_exp = 0;
3097 re_token_t token2;
3099 start_elem.opr.name = start_name_buf;
3100 ret = parse_bracket_element (&start_elem, regexp, token, token_len, dfa,
3101 syntax, first_round);
3102 if (BE (ret != REG_NOERROR, 0))
3104 *err = ret;
3105 goto parse_bracket_exp_free_return;
3107 first_round = 0;
3109 /* Get information about the next token. We need it in any case. */
3110 token_len = peek_token_bracket (token, regexp, syntax);
3112 /* Do not check for ranges if we know they are not allowed. */
3113 if (start_elem.type != CHAR_CLASS && start_elem.type != EQUIV_CLASS)
3115 if (BE (token->type == END_OF_RE, 0))
3117 *err = REG_EBRACK;
3118 goto parse_bracket_exp_free_return;
3120 if (token->type == OP_CHARSET_RANGE)
3122 re_string_skip_bytes (regexp, token_len); /* Skip '-'. */
3123 token_len2 = peek_token_bracket (&token2, regexp, syntax);
3124 if (BE (token2.type == END_OF_RE, 0))
3126 *err = REG_EBRACK;
3127 goto parse_bracket_exp_free_return;
3129 if (token2.type == OP_CLOSE_BRACKET)
3131 /* We treat the last '-' as a normal character. */
3132 re_string_skip_bytes (regexp, -token_len);
3133 token->type = CHARACTER;
3135 else
3136 is_range_exp = 1;
3140 if (is_range_exp == 1)
3142 end_elem.opr.name = end_name_buf;
3143 ret = parse_bracket_element (&end_elem, regexp, &token2, token_len2,
3144 dfa, syntax, 1);
3145 if (BE (ret != REG_NOERROR, 0))
3147 *err = ret;
3148 goto parse_bracket_exp_free_return;
3151 token_len = peek_token_bracket (token, regexp, syntax);
3153 #ifdef _LIBC
3154 *err = build_range_exp (sbcset, mbcset, &range_alloc,
3155 &start_elem, &end_elem);
3156 #else
3157 # ifdef RE_ENABLE_I18N
3158 *err = build_range_exp (sbcset,
3159 dfa->mb_cur_max > 1 ? mbcset : NULL,
3160 &range_alloc, &start_elem, &end_elem);
3161 # else
3162 *err = build_range_exp (sbcset, &start_elem, &end_elem);
3163 # endif
3164 #endif /* RE_ENABLE_I18N */
3165 if (BE (*err != REG_NOERROR, 0))
3166 goto parse_bracket_exp_free_return;
3168 else
3170 switch (start_elem.type)
3172 case SB_CHAR:
3173 bitset_set (sbcset, start_elem.opr.ch);
3174 break;
3175 #ifdef RE_ENABLE_I18N
3176 case MB_CHAR:
3177 /* Check whether the array has enough space. */
3178 if (BE (mbchar_alloc == mbcset->nmbchars, 0))
3180 wchar_t *new_mbchars;
3181 /* Not enough, realloc it. */
3182 /* +1 in case of mbcset->nmbchars is 0. */
3183 mbchar_alloc = 2 * mbcset->nmbchars + 1;
3184 /* Use realloc since array is NULL if *alloc == 0. */
3185 new_mbchars = re_realloc (mbcset->mbchars, wchar_t,
3186 mbchar_alloc);
3187 if (BE (new_mbchars == NULL, 0))
3188 goto parse_bracket_exp_espace;
3189 mbcset->mbchars = new_mbchars;
3191 mbcset->mbchars[mbcset->nmbchars++] = start_elem.opr.wch;
3192 break;
3193 #endif /* RE_ENABLE_I18N */
3194 case EQUIV_CLASS:
3195 *err = build_equiv_class (sbcset,
3196 #ifdef RE_ENABLE_I18N
3197 mbcset, &equiv_class_alloc,
3198 #endif /* RE_ENABLE_I18N */
3199 start_elem.opr.name);
3200 if (BE (*err != REG_NOERROR, 0))
3201 goto parse_bracket_exp_free_return;
3202 break;
3203 case COLL_SYM:
3204 *err = build_collating_symbol (sbcset,
3205 #ifdef RE_ENABLE_I18N
3206 mbcset, &coll_sym_alloc,
3207 #endif /* RE_ENABLE_I18N */
3208 start_elem.opr.name);
3209 if (BE (*err != REG_NOERROR, 0))
3210 goto parse_bracket_exp_free_return;
3211 break;
3212 case CHAR_CLASS:
3213 *err = build_charclass (regexp->trans, sbcset,
3214 #ifdef RE_ENABLE_I18N
3215 mbcset, &char_class_alloc,
3216 #endif /* RE_ENABLE_I18N */
3217 start_elem.opr.name, syntax);
3218 if (BE (*err != REG_NOERROR, 0))
3219 goto parse_bracket_exp_free_return;
3220 break;
3221 default:
3222 assert (0);
3223 break;
3226 if (BE (token->type == END_OF_RE, 0))
3228 *err = REG_EBRACK;
3229 goto parse_bracket_exp_free_return;
3231 if (token->type == OP_CLOSE_BRACKET)
3232 break;
3235 re_string_skip_bytes (regexp, token_len); /* Skip a token. */
3237 /* If it is non-matching list. */
3238 if (non_match)
3239 bitset_not (sbcset);
3241 #ifdef RE_ENABLE_I18N
3242 /* Ensure only single byte characters are set. */
3243 if (dfa->mb_cur_max > 1)
3244 bitset_mask (sbcset, dfa->sb_char);
3246 if (mbcset->nmbchars || mbcset->ncoll_syms || mbcset->nequiv_classes
3247 || mbcset->nranges || (dfa->mb_cur_max > 1 && (mbcset->nchar_classes
3248 || mbcset->non_match)))
3250 bin_tree_t *mbc_tree;
3251 int sbc_idx;
3252 /* Build a tree for complex bracket. */
3253 dfa->has_mb_node = 1;
3254 br_token.type = COMPLEX_BRACKET;
3255 br_token.opr.mbcset = mbcset;
3256 mbc_tree = create_token_tree (dfa, NULL, NULL, &br_token);
3257 if (BE (mbc_tree == NULL, 0))
3258 goto parse_bracket_exp_espace;
3259 for (sbc_idx = 0; sbc_idx < BITSET_WORDS; ++sbc_idx)
3260 if (sbcset[sbc_idx])
3261 break;
3262 /* If there are no bits set in sbcset, there is no point
3263 of having both SIMPLE_BRACKET and COMPLEX_BRACKET. */
3264 if (sbc_idx < BITSET_WORDS)
3266 /* Build a tree for simple bracket. */
3267 br_token.type = SIMPLE_BRACKET;
3268 br_token.opr.sbcset = sbcset;
3269 work_tree = create_token_tree (dfa, NULL, NULL, &br_token);
3270 if (BE (work_tree == NULL, 0))
3271 goto parse_bracket_exp_espace;
3273 /* Then join them by ALT node. */
3274 work_tree = create_tree (dfa, work_tree, mbc_tree, OP_ALT);
3275 if (BE (work_tree == NULL, 0))
3276 goto parse_bracket_exp_espace;
3278 else
3280 re_free (sbcset);
3281 work_tree = mbc_tree;
3284 else
3285 #endif /* not RE_ENABLE_I18N */
3287 #ifdef RE_ENABLE_I18N
3288 free_charset (mbcset);
3289 #endif
3290 /* Build a tree for simple bracket. */
3291 br_token.type = SIMPLE_BRACKET;
3292 br_token.opr.sbcset = sbcset;
3293 work_tree = create_token_tree (dfa, NULL, NULL, &br_token);
3294 if (BE (work_tree == NULL, 0))
3295 goto parse_bracket_exp_espace;
3297 return work_tree;
3299 parse_bracket_exp_espace:
3300 *err = REG_ESPACE;
3301 parse_bracket_exp_free_return:
3302 re_free (sbcset);
3303 #ifdef RE_ENABLE_I18N
3304 free_charset (mbcset);
3305 #endif /* RE_ENABLE_I18N */
3306 return NULL;
3309 /* Parse an element in the bracket expression. */
3311 static reg_errcode_t
3312 parse_bracket_element (bracket_elem_t *elem, re_string_t *regexp,
3313 re_token_t *token, int token_len, re_dfa_t *dfa,
3314 reg_syntax_t syntax, int accept_hyphen)
3316 #ifdef RE_ENABLE_I18N
3317 int cur_char_size;
3318 cur_char_size = re_string_char_size_at (regexp, re_string_cur_idx (regexp));
3319 if (cur_char_size > 1)
3321 elem->type = MB_CHAR;
3322 elem->opr.wch = re_string_wchar_at (regexp, re_string_cur_idx (regexp));
3323 re_string_skip_bytes (regexp, cur_char_size);
3324 return REG_NOERROR;
3326 #endif /* RE_ENABLE_I18N */
3327 re_string_skip_bytes (regexp, token_len); /* Skip a token. */
3328 if (token->type == OP_OPEN_COLL_ELEM || token->type == OP_OPEN_CHAR_CLASS
3329 || token->type == OP_OPEN_EQUIV_CLASS)
3330 return parse_bracket_symbol (elem, regexp, token);
3331 if (BE (token->type == OP_CHARSET_RANGE, 0) && !accept_hyphen)
3333 /* A '-' must only appear as anything but a range indicator before
3334 the closing bracket. Everything else is an error. */
3335 re_token_t token2;
3336 (void) peek_token_bracket (&token2, regexp, syntax);
3337 if (token2.type != OP_CLOSE_BRACKET)
3338 /* The actual error value is not standardized since this whole
3339 case is undefined. But ERANGE makes good sense. */
3340 return REG_ERANGE;
3342 elem->type = SB_CHAR;
3343 elem->opr.ch = token->opr.c;
3344 return REG_NOERROR;
3347 /* Parse a bracket symbol in the bracket expression. Bracket symbols are
3348 such as [:<character_class>:], [.<collating_element>.], and
3349 [=<equivalent_class>=]. */
3351 static reg_errcode_t
3352 parse_bracket_symbol (bracket_elem_t *elem, re_string_t *regexp,
3353 re_token_t *token)
3355 unsigned char ch, delim = token->opr.c;
3356 int i = 0;
3357 if (re_string_eoi(regexp))
3358 return REG_EBRACK;
3359 for (;; ++i)
3361 if (i >= BRACKET_NAME_BUF_SIZE)
3362 return REG_EBRACK;
3363 if (token->type == OP_OPEN_CHAR_CLASS)
3364 ch = re_string_fetch_byte_case (regexp);
3365 else
3366 ch = re_string_fetch_byte (regexp);
3367 if (re_string_eoi(regexp))
3368 return REG_EBRACK;
3369 if (ch == delim && re_string_peek_byte (regexp, 0) == ']')
3370 break;
3371 elem->opr.name[i] = ch;
3373 re_string_skip_bytes (regexp, 1);
3374 elem->opr.name[i] = '\0';
3375 switch (token->type)
3377 case OP_OPEN_COLL_ELEM:
3378 elem->type = COLL_SYM;
3379 break;
3380 case OP_OPEN_EQUIV_CLASS:
3381 elem->type = EQUIV_CLASS;
3382 break;
3383 case OP_OPEN_CHAR_CLASS:
3384 elem->type = CHAR_CLASS;
3385 break;
3386 default:
3387 break;
3389 return REG_NOERROR;
3392 /* Helper function for parse_bracket_exp.
3393 Build the equivalence class which is represented by NAME.
3394 The result are written to MBCSET and SBCSET.
3395 EQUIV_CLASS_ALLOC is the allocated size of mbcset->equiv_classes,
3396 is a pointer argument sinse we may update it. */
3398 static reg_errcode_t
3399 #ifdef RE_ENABLE_I18N
3400 build_equiv_class (bitset_t sbcset, re_charset_t *mbcset,
3401 int *equiv_class_alloc, const unsigned char *name)
3402 #else /* not RE_ENABLE_I18N */
3403 build_equiv_class (bitset_t sbcset, const unsigned char *name)
3404 #endif /* not RE_ENABLE_I18N */
3406 #ifdef _LIBC
3407 uint32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
3408 if (nrules != 0)
3410 const int32_t *table, *indirect;
3411 const unsigned char *weights, *extra, *cp;
3412 unsigned char char_buf[2];
3413 int32_t idx1, idx2;
3414 unsigned int ch;
3415 size_t len;
3416 /* This #include defines a local function! */
3417 # include <locale/weight.h>
3418 /* Calculate the index for equivalence class. */
3419 cp = name;
3420 table = (const int32_t *) _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
3421 weights = (const unsigned char *) _NL_CURRENT (LC_COLLATE,
3422 _NL_COLLATE_WEIGHTMB);
3423 extra = (const unsigned char *) _NL_CURRENT (LC_COLLATE,
3424 _NL_COLLATE_EXTRAMB);
3425 indirect = (const int32_t *) _NL_CURRENT (LC_COLLATE,
3426 _NL_COLLATE_INDIRECTMB);
3427 idx1 = findidx (&cp, -1);
3428 if (BE (idx1 == 0 || *cp != '\0', 0))
3429 /* This isn't a valid character. */
3430 return REG_ECOLLATE;
3432 /* Build single byte matcing table for this equivalence class. */
3433 len = weights[idx1 & 0xffffff];
3434 for (ch = 0; ch < SBC_MAX; ++ch)
3436 char_buf[0] = ch;
3437 cp = char_buf;
3438 idx2 = findidx (&cp, 1);
3440 idx2 = table[ch];
3442 if (idx2 == 0)
3443 /* This isn't a valid character. */
3444 continue;
3445 /* Compare only if the length matches and the collation rule
3446 index is the same. */
3447 if (len == weights[idx2 & 0xffffff] && (idx1 >> 24) == (idx2 >> 24))
3449 int cnt = 0;
3451 while (cnt <= len &&
3452 weights[(idx1 & 0xffffff) + 1 + cnt]
3453 == weights[(idx2 & 0xffffff) + 1 + cnt])
3454 ++cnt;
3456 if (cnt > len)
3457 bitset_set (sbcset, ch);
3460 /* Check whether the array has enough space. */
3461 if (BE (*equiv_class_alloc == mbcset->nequiv_classes, 0))
3463 /* Not enough, realloc it. */
3464 /* +1 in case of mbcset->nequiv_classes is 0. */
3465 int new_equiv_class_alloc = 2 * mbcset->nequiv_classes + 1;
3466 /* Use realloc since the array is NULL if *alloc == 0. */
3467 int32_t *new_equiv_classes = re_realloc (mbcset->equiv_classes,
3468 int32_t,
3469 new_equiv_class_alloc);
3470 if (BE (new_equiv_classes == NULL, 0))
3471 return REG_ESPACE;
3472 mbcset->equiv_classes = new_equiv_classes;
3473 *equiv_class_alloc = new_equiv_class_alloc;
3475 mbcset->equiv_classes[mbcset->nequiv_classes++] = idx1;
3477 else
3478 #endif /* _LIBC */
3480 if (BE (strlen ((const char *) name) != 1, 0))
3481 return REG_ECOLLATE;
3482 bitset_set (sbcset, *name);
3484 return REG_NOERROR;
3487 /* Helper function for parse_bracket_exp.
3488 Build the character class which is represented by NAME.
3489 The result are written to MBCSET and SBCSET.
3490 CHAR_CLASS_ALLOC is the allocated size of mbcset->char_classes,
3491 is a pointer argument sinse we may update it. */
3493 static reg_errcode_t
3494 #ifdef RE_ENABLE_I18N
3495 build_charclass (RE_TRANSLATE_TYPE trans, bitset_t sbcset,
3496 re_charset_t *mbcset, int *char_class_alloc,
3497 const unsigned char *class_name, reg_syntax_t syntax)
3498 #else /* not RE_ENABLE_I18N */
3499 build_charclass (RE_TRANSLATE_TYPE trans, bitset_t sbcset,
3500 const unsigned char *class_name, reg_syntax_t syntax)
3501 #endif /* not RE_ENABLE_I18N */
3503 int i;
3504 const char *name = (const char *) class_name;
3506 /* In case of REG_ICASE "upper" and "lower" match the both of
3507 upper and lower cases. */
3508 if ((syntax & RE_ICASE)
3509 && (strcmp (name, "upper") == 0 || strcmp (name, "lower") == 0))
3510 name = "alpha";
3512 #ifdef RE_ENABLE_I18N
3513 /* Check the space of the arrays. */
3514 if (BE (*char_class_alloc == mbcset->nchar_classes, 0))
3516 /* Not enough, realloc it. */
3517 /* +1 in case of mbcset->nchar_classes is 0. */
3518 int new_char_class_alloc = 2 * mbcset->nchar_classes + 1;
3519 /* Use realloc since array is NULL if *alloc == 0. */
3520 wctype_t *new_char_classes = re_realloc (mbcset->char_classes, wctype_t,
3521 new_char_class_alloc);
3522 if (BE (new_char_classes == NULL, 0))
3523 return REG_ESPACE;
3524 mbcset->char_classes = new_char_classes;
3525 *char_class_alloc = new_char_class_alloc;
3527 mbcset->char_classes[mbcset->nchar_classes++] = __wctype (name);
3528 #endif /* RE_ENABLE_I18N */
3530 #define BUILD_CHARCLASS_LOOP(ctype_func) \
3531 do { \
3532 if (BE (trans != NULL, 0)) \
3534 for (i = 0; i < SBC_MAX; ++i) \
3535 if (ctype_func (i)) \
3536 bitset_set (sbcset, trans[i]); \
3538 else \
3540 for (i = 0; i < SBC_MAX; ++i) \
3541 if (ctype_func (i)) \
3542 bitset_set (sbcset, i); \
3544 } while (0)
3546 if (strcmp (name, "alnum") == 0)
3547 BUILD_CHARCLASS_LOOP (isalnum);
3548 else if (strcmp (name, "cntrl") == 0)
3549 BUILD_CHARCLASS_LOOP (iscntrl);
3550 else if (strcmp (name, "lower") == 0)
3551 BUILD_CHARCLASS_LOOP (islower);
3552 else if (strcmp (name, "space") == 0)
3553 BUILD_CHARCLASS_LOOP (isspace);
3554 else if (strcmp (name, "alpha") == 0)
3555 BUILD_CHARCLASS_LOOP (isalpha);
3556 else if (strcmp (name, "digit") == 0)
3557 BUILD_CHARCLASS_LOOP (isdigit);
3558 else if (strcmp (name, "print") == 0)
3559 BUILD_CHARCLASS_LOOP (isprint);
3560 else if (strcmp (name, "upper") == 0)
3561 BUILD_CHARCLASS_LOOP (isupper);
3562 else if (strcmp (name, "blank") == 0)
3563 BUILD_CHARCLASS_LOOP (isblank);
3564 else if (strcmp (name, "graph") == 0)
3565 BUILD_CHARCLASS_LOOP (isgraph);
3566 else if (strcmp (name, "punct") == 0)
3567 BUILD_CHARCLASS_LOOP (ispunct);
3568 else if (strcmp (name, "xdigit") == 0)
3569 BUILD_CHARCLASS_LOOP (isxdigit);
3570 else
3571 return REG_ECTYPE;
3573 return REG_NOERROR;
3576 static bin_tree_t *
3577 build_charclass_op (re_dfa_t *dfa, RE_TRANSLATE_TYPE trans,
3578 const unsigned char *class_name,
3579 const unsigned char *extra, int non_match,
3580 reg_errcode_t *err)
3582 re_bitset_ptr_t sbcset;
3583 #ifdef RE_ENABLE_I18N
3584 re_charset_t *mbcset;
3585 int alloc = 0;
3586 #endif /* not RE_ENABLE_I18N */
3587 reg_errcode_t ret;
3588 re_token_t br_token;
3589 bin_tree_t *tree;
3591 sbcset = (re_bitset_ptr_t) calloc (sizeof (bitset_t), 1);
3592 #ifdef RE_ENABLE_I18N
3593 mbcset = (re_charset_t *) calloc (sizeof (re_charset_t), 1);
3594 #endif /* RE_ENABLE_I18N */
3596 #ifdef RE_ENABLE_I18N
3597 if (BE (sbcset == NULL || mbcset == NULL, 0))
3598 #else /* not RE_ENABLE_I18N */
3599 if (BE (sbcset == NULL, 0))
3600 #endif /* not RE_ENABLE_I18N */
3602 *err = REG_ESPACE;
3603 return NULL;
3606 if (non_match)
3608 #ifdef RE_ENABLE_I18N
3609 mbcset->non_match = 1;
3610 #endif /* not RE_ENABLE_I18N */
3613 /* We don't care the syntax in this case. */
3614 ret = build_charclass (trans, sbcset,
3615 #ifdef RE_ENABLE_I18N
3616 mbcset, &alloc,
3617 #endif /* RE_ENABLE_I18N */
3618 class_name, 0);
3620 if (BE (ret != REG_NOERROR, 0))
3622 re_free (sbcset);
3623 #ifdef RE_ENABLE_I18N
3624 free_charset (mbcset);
3625 #endif /* RE_ENABLE_I18N */
3626 *err = ret;
3627 return NULL;
3629 /* \w match '_' also. */
3630 for (; *extra; extra++)
3631 bitset_set (sbcset, *extra);
3633 /* If it is non-matching list. */
3634 if (non_match)
3635 bitset_not (sbcset);
3637 #ifdef RE_ENABLE_I18N
3638 /* Ensure only single byte characters are set. */
3639 if (dfa->mb_cur_max > 1)
3640 bitset_mask (sbcset, dfa->sb_char);
3641 #endif
3643 /* Build a tree for simple bracket. */
3644 br_token.type = SIMPLE_BRACKET;
3645 br_token.opr.sbcset = sbcset;
3646 tree = create_token_tree (dfa, NULL, NULL, &br_token);
3647 if (BE (tree == NULL, 0))
3648 goto build_word_op_espace;
3650 #ifdef RE_ENABLE_I18N
3651 if (dfa->mb_cur_max > 1)
3653 bin_tree_t *mbc_tree;
3654 /* Build a tree for complex bracket. */
3655 br_token.type = COMPLEX_BRACKET;
3656 br_token.opr.mbcset = mbcset;
3657 dfa->has_mb_node = 1;
3658 mbc_tree = create_token_tree (dfa, NULL, NULL, &br_token);
3659 if (BE (mbc_tree == NULL, 0))
3660 goto build_word_op_espace;
3661 /* Then join them by ALT node. */
3662 tree = create_tree (dfa, tree, mbc_tree, OP_ALT);
3663 if (BE (mbc_tree != NULL, 1))
3664 return tree;
3666 else
3668 free_charset (mbcset);
3669 return tree;
3671 #else /* not RE_ENABLE_I18N */
3672 return tree;
3673 #endif /* not RE_ENABLE_I18N */
3675 build_word_op_espace:
3676 re_free (sbcset);
3677 #ifdef RE_ENABLE_I18N
3678 free_charset (mbcset);
3679 #endif /* RE_ENABLE_I18N */
3680 *err = REG_ESPACE;
3681 return NULL;
3684 /* This is intended for the expressions like "a{1,3}".
3685 Fetch a number from `input', and return the number.
3686 Return -1, if the number field is empty like "{,1}".
3687 Return -2, If an error is occured. */
3689 static int
3690 fetch_number (re_string_t *input, re_token_t *token, reg_syntax_t syntax)
3692 int num = -1;
3693 unsigned char c;
3694 while (1)
3696 fetch_token (token, input, syntax);
3697 c = token->opr.c;
3698 if (BE (token->type == END_OF_RE, 0))
3699 return -2;
3700 if (token->type == OP_CLOSE_DUP_NUM || c == ',')
3701 break;
3702 num = ((token->type != CHARACTER || c < '0' || '9' < c || num == -2)
3703 ? -2 : ((num == -1) ? c - '0' : num * 10 + c - '0'));
3704 num = (num > RE_DUP_MAX) ? -2 : num;
3706 return num;
3709 #ifdef RE_ENABLE_I18N
3710 static void
3711 free_charset (re_charset_t *cset)
3713 re_free (cset->mbchars);
3714 # ifdef _LIBC
3715 re_free (cset->coll_syms);
3716 re_free (cset->equiv_classes);
3717 re_free (cset->range_starts);
3718 re_free (cset->range_ends);
3719 # endif
3720 re_free (cset->char_classes);
3721 re_free (cset);
3723 #endif /* RE_ENABLE_I18N */
3725 /* Functions for binary tree operation. */
3727 /* Create a tree node. */
3729 static bin_tree_t *
3730 create_tree (re_dfa_t *dfa, bin_tree_t *left, bin_tree_t *right,
3731 re_token_type_t type)
3733 re_token_t t;
3734 t.type = type;
3735 return create_token_tree (dfa, left, right, &t);
3738 static bin_tree_t *
3739 create_token_tree (re_dfa_t *dfa, bin_tree_t *left, bin_tree_t *right,
3740 const re_token_t *token)
3742 bin_tree_t *tree;
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)
3748 return 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;
3756 tree->left = left;
3757 tree->right = right;
3758 tree->token = *token;
3759 tree->token.duplicated = 0;
3760 tree->token.opt_subexp = 0;
3761 tree->first = NULL;
3762 tree->next = NULL;
3763 tree->node_idx = -1;
3765 if (left != NULL)
3766 left->parent = tree;
3767 if (right != NULL)
3768 right->parent = tree;
3769 return 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 int idx = (int) (long) extra;
3779 if (node->token.type == SUBEXP && node->token.opr.idx == idx)
3780 node->token.opt_subexp = 1;
3782 return REG_NOERROR;
3785 /* Free the allocated memory inside NODE. */
3787 static void
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);
3793 else
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);
3806 return REG_NOERROR;
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. */
3815 static bin_tree_t *
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);
3826 if (*p_new == NULL)
3827 return NULL;
3828 (*p_new)->parent = dup_node;
3829 (*p_new)->token.duplicated = 1;
3830 dup_node = *p_new;
3832 /* Go to the left node, or up and to the right. */
3833 if (node->left)
3835 node = node->left;
3836 p_new = &dup_node->left;
3838 else
3840 const bin_tree_t *prev = NULL;
3841 while (node->right == prev || node->right == NULL)
3843 prev = node;
3844 node = node->parent;
3845 dup_node = dup_node->parent;
3846 if (!node)
3847 return dup_root;
3849 node = node->right;
3850 p_new = &dup_node->right;