Debian Codegraph @

lib/regcomp.c

raw
1 /* Extended regular expression matching and search library.
2 Copyright (C) 2002-2026 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
4 Contributed by Isamu Hasegawa <[email protected]>.
5
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.
10
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.
15
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 <https://www.gnu.org/licenses/>. */
19
20 #ifdef _LIBC
21 # include <locale/weight.h>
22 #endif
23
24 static reg_errcode_t re_compile_internal (regex_t *preg, const char * pattern,
25 size_t length, reg_syntax_t syntax);
26 static void re_compile_fastmap_iter (regex_t *bufp,
27 const re_dfastate_t *init_state,
28 char *fastmap);
29 static reg_errcode_t init_dfa (re_dfa_t *dfa, size_t pat_len);
30 static void free_charset (re_charset_t *cset);
31 static void free_workarea_compile (regex_t *preg);
32 static reg_errcode_t create_initial_state (re_dfa_t *dfa);
33 static void optimize_utf8 (re_dfa_t *dfa);
34 static reg_errcode_t analyze (regex_t *preg);
35 static reg_errcode_t preorder (bin_tree_t *root,
36 reg_errcode_t (fn (void *, bin_tree_t *)),
37 void *extra);
38 static reg_errcode_t postorder (bin_tree_t *root,
39 reg_errcode_t (fn (void *, bin_tree_t *)),
40 void *extra);
41 static reg_errcode_t optimize_subexps (void *extra, bin_tree_t *node);
42 static reg_errcode_t lower_subexps (void *extra, bin_tree_t *node);
43 static bin_tree_t *lower_subexp (reg_errcode_t *err, regex_t *preg,
44 bin_tree_t *node);
45 static reg_errcode_t calc_first (void *extra, bin_tree_t *node);
46 static reg_errcode_t calc_next (void *extra, bin_tree_t *node);
47 static reg_errcode_t link_nfa_nodes (void *extra, bin_tree_t *node);
48 static Idx duplicate_node (re_dfa_t *dfa, Idx org_idx, unsigned int constraint);
49 static Idx search_duplicated_node (const re_dfa_t *dfa, Idx org_node,
50 unsigned int constraint);
51 static reg_errcode_t calc_eclosure (re_dfa_t *dfa);
52 static reg_errcode_t calc_eclosure_iter (re_node_set *new_set, re_dfa_t *dfa,
53 Idx node, bool root);
54 static reg_errcode_t calc_inveclosure (re_dfa_t *dfa);
55 static Idx fetch_number (re_string_t *input, re_token_t *token,
56 reg_syntax_t syntax);
57 static int peek_token (re_token_t *token, re_string_t *input,
58 reg_syntax_t syntax);
59 static bin_tree_t *parse (re_string_t *regexp, regex_t *preg,
60 reg_syntax_t syntax, reg_errcode_t *err);
61 static bin_tree_t *parse_reg_exp (re_string_t *regexp, regex_t *preg,
62 re_token_t *token, reg_syntax_t syntax,
63 Idx nest, reg_errcode_t *err);
64 static bin_tree_t *parse_branch (re_string_t *regexp, regex_t *preg,
65 re_token_t *token, reg_syntax_t syntax,
66 Idx nest, reg_errcode_t *err);
67 static bin_tree_t *parse_expression (re_string_t *regexp, regex_t *preg,
68 re_token_t *token, reg_syntax_t syntax,
69 Idx nest, reg_errcode_t *err);
70 static bin_tree_t *parse_sub_exp (re_string_t *regexp, regex_t *preg,
71 re_token_t *token, reg_syntax_t syntax,
72 Idx nest, reg_errcode_t *err);
73 static bin_tree_t *parse_dup_op (bin_tree_t *dup_elem, re_string_t *regexp,
74 re_dfa_t *dfa, re_token_t *token,
75 reg_syntax_t syntax, reg_errcode_t *err);
76 static bin_tree_t *parse_bracket_exp (re_string_t *regexp, re_dfa_t *dfa,
77 re_token_t *token, reg_syntax_t syntax,
78 reg_errcode_t *err);
79 static reg_errcode_t parse_bracket_element (bracket_elem_t *elem,
80 re_string_t *regexp,
81 re_token_t *token, int token_len,
82 re_dfa_t *dfa,
83 reg_syntax_t syntax,
84 bool accept_hyphen);
85 static reg_errcode_t parse_bracket_symbol (bracket_elem_t *elem,
86 re_string_t *regexp,
87 re_token_t *token);
88 static reg_errcode_t build_equiv_class (bitset_t sbcset,
89 re_charset_t *mbcset,
90 Idx *equiv_class_alloc,
91 const unsigned char *name);
92 static reg_errcode_t build_charclass (RE_TRANSLATE_TYPE trans,
93 bitset_t sbcset,
94 re_charset_t *mbcset,
95 Idx *char_class_alloc,
96 const char *class_name,
97 reg_syntax_t syntax);
98 static bin_tree_t *build_charclass_op (re_dfa_t *dfa,
99 RE_TRANSLATE_TYPE trans,
100 const char *class_name,
101 const char *extra,
102 bool non_match, reg_errcode_t *err);
103 static bin_tree_t *create_tree (re_dfa_t *dfa,
104 bin_tree_t *left, bin_tree_t *right,
105 re_token_type_t type);
106 static bin_tree_t *create_token_tree (re_dfa_t *dfa,
107 bin_tree_t *left, bin_tree_t *right,
108 const re_token_t *token);
109 static bin_tree_t *duplicate_tree (const bin_tree_t *src, re_dfa_t *dfa);
110 static void free_token (re_token_t *node);
111 static reg_errcode_t free_tree (void *extra, bin_tree_t *node);
112 static reg_errcode_t mark_opt_subexp (void *extra, bin_tree_t *node);
113
114 /* This table gives an error message for each of the error codes listed
115 in regex.h. Obviously the order here has to be same as there.
116 POSIX doesn't require that we do anything for REG_NOERROR,
117 but why not be nice? */
118
119 static const char __re_error_msgid[] =
120 {
121 #define REG_NOERROR_IDX 0
122 gettext_noop ("Success") /* REG_NOERROR */
123 "\0"
124 #define REG_NOMATCH_IDX (REG_NOERROR_IDX + sizeof "Success")
125 gettext_noop ("No match") /* REG_NOMATCH */
126 "\0"
127 #define REG_BADPAT_IDX (REG_NOMATCH_IDX + sizeof "No match")
128 gettext_noop ("Invalid regular expression") /* REG_BADPAT */
129 "\0"
130 #define REG_ECOLLATE_IDX (REG_BADPAT_IDX + sizeof "Invalid regular expression")
131 gettext_noop ("Invalid collation character") /* REG_ECOLLATE */
132 "\0"
133 #define REG_ECTYPE_IDX (REG_ECOLLATE_IDX + sizeof "Invalid collation character")
134 gettext_noop ("Invalid character class name") /* REG_ECTYPE */
135 "\0"
136 #define REG_EESCAPE_IDX (REG_ECTYPE_IDX + sizeof "Invalid character class name")
137 gettext_noop ("Trailing backslash") /* REG_EESCAPE */
138 "\0"
139 #define REG_ESUBREG_IDX (REG_EESCAPE_IDX + sizeof "Trailing backslash")
140 gettext_noop ("Invalid back reference") /* REG_ESUBREG */
141 "\0"
142 #define REG_EBRACK_IDX (REG_ESUBREG_IDX + sizeof "Invalid back reference")
143 gettext_noop ("Unmatched [, [^, [:, [., or [=") /* REG_EBRACK */
144 "\0"
145 #define REG_EPAREN_IDX (REG_EBRACK_IDX + sizeof "Unmatched [, [^, [:, [., or [=")
146 gettext_noop ("Unmatched ( or \\(") /* REG_EPAREN */
147 "\0"
148 #define REG_EBRACE_IDX (REG_EPAREN_IDX + sizeof "Unmatched ( or \\(")
149 gettext_noop ("Unmatched \\{") /* REG_EBRACE */
150 "\0"
151 #define REG_BADBR_IDX (REG_EBRACE_IDX + sizeof "Unmatched \\{")
152 gettext_noop ("Invalid content of \\{\\}") /* REG_BADBR */
153 "\0"
154 #define REG_ERANGE_IDX (REG_BADBR_IDX + sizeof "Invalid content of \\{\\}")
155 gettext_noop ("Invalid range end") /* REG_ERANGE */
156 "\0"
157 #define REG_ESPACE_IDX (REG_ERANGE_IDX + sizeof "Invalid range end")
158 gettext_noop ("Memory exhausted") /* REG_ESPACE */
159 "\0"
160 #define REG_BADRPT_IDX (REG_ESPACE_IDX + sizeof "Memory exhausted")
161 gettext_noop ("Invalid preceding regular expression") /* REG_BADRPT */
162 "\0"
163 #define REG_EEND_IDX (REG_BADRPT_IDX + sizeof "Invalid preceding regular expression")
164 gettext_noop ("Premature end of regular expression") /* REG_EEND */
165 "\0"
166 #define REG_ESIZE_IDX (REG_EEND_IDX + sizeof "Premature end of regular expression")
167 gettext_noop ("Regular expression too big") /* REG_ESIZE */
168 "\0"
169 #define REG_ERPAREN_IDX (REG_ESIZE_IDX + sizeof "Regular expression too big")
170 gettext_noop ("Unmatched ) or \\)") /* REG_ERPAREN */
171 };
172
173 static const size_t __re_error_msgid_idx[] =
174 {
175 REG_NOERROR_IDX,
176 REG_NOMATCH_IDX,
177 REG_BADPAT_IDX,
178 REG_ECOLLATE_IDX,
179 REG_ECTYPE_IDX,
180 REG_EESCAPE_IDX,
181 REG_ESUBREG_IDX,
182 REG_EBRACK_IDX,
183 REG_EPAREN_IDX,
184 REG_EBRACE_IDX,
185 REG_BADBR_IDX,
186 REG_ERANGE_IDX,
187 REG_ESPACE_IDX,
188 REG_BADRPT_IDX,
189 REG_EEND_IDX,
190 REG_ESIZE_IDX,
191 REG_ERPAREN_IDX
192 };
193
194 /* Entry points for GNU code. */
195
196 /* re_compile_pattern is the GNU regular expression compiler: it
197 compiles PATTERN (of length LENGTH) and puts the result in BUFP.
198 Returns 0 if the pattern was valid, otherwise an error string.
199
200 Assumes the 'allocated' (and perhaps 'buffer') and 'translate' fields
201 are set in BUFP on entry. */
202
203 const char *
204 re_compile_pattern (const char *pattern, size_t length,
205 struct re_pattern_buffer *bufp)
206 {
207 reg_errcode_t ret;
208
209 /* And GNU code determines whether or not to get register information
210 by passing null for the REGS argument to re_match, etc., not by
211 setting no_sub, unless RE_NO_SUB is set. */
212 bufp->no_sub = !!(re_syntax_options & RE_NO_SUB);
213
214 /* Match anchors at newline. */
215 bufp->newline_anchor = 1;
216
217 ret = re_compile_internal (bufp, pattern, length, re_syntax_options);
218
219 if (!ret)
220 return NULL;
221 return gettext (__re_error_msgid + __re_error_msgid_idx[(int) ret]);
222 }
223 weak_alias (__re_compile_pattern, re_compile_pattern)
224
225 /* Set by 're_set_syntax' to the current regexp syntax to recognize. Can
226 also be assigned to arbitrarily: each pattern buffer stores its own
227 syntax, so it can be changed between regex compilations. */
228 /* This has no initializer because initialized variables in Emacs
229 become read-only after dumping. */
230 reg_syntax_t re_syntax_options;
231
232
233 /* Specify the precise syntax of regexps for compilation. This provides
234 for compatibility for various utilities which historically have
235 different, incompatible syntaxes.
236
237 The argument SYNTAX is a bit mask comprised of the various bits
238 defined in regex.h. We return the old syntax. */
239
240 reg_syntax_t
241 re_set_syntax (reg_syntax_t syntax)
242 {
243 reg_syntax_t ret = re_syntax_options;
244
245 re_syntax_options = syntax;
246 return ret;
247 }
248 weak_alias (__re_set_syntax, re_set_syntax)
249
250 int
251 re_compile_fastmap (struct re_pattern_buffer *bufp)
252 {
253 re_dfa_t *dfa = bufp->buffer;
254 char *fastmap = bufp->fastmap;
255
256 memset (fastmap, '\0', sizeof (char) * SBC_MAX);
257 re_compile_fastmap_iter (bufp, dfa->init_state, fastmap);
258 if (dfa->init_state != dfa->init_state_word)
259 re_compile_fastmap_iter (bufp, dfa->init_state_word, fastmap);
260 if (dfa->init_state != dfa->init_state_nl)
261 re_compile_fastmap_iter (bufp, dfa->init_state_nl, fastmap);
262 if (dfa->init_state != dfa->init_state_begbuf)
263 re_compile_fastmap_iter (bufp, dfa->init_state_begbuf, fastmap);
264 bufp->fastmap_accurate = 1;
265 return 0;
266 }
267 weak_alias (__re_compile_fastmap, re_compile_fastmap)
268
269 static __always_inline void
270 re_set_fastmap (char *fastmap, bool icase, int ch)
271 {
272 fastmap[ch] = 1;
273 if (icase)
274 fastmap[tolower (ch)] = 1;
275 }
276
277 /* Helper function for re_compile_fastmap.
278 Compile fastmap for the initial_state INIT_STATE. */
279
280 static void
281 re_compile_fastmap_iter (regex_t *bufp, const re_dfastate_t *init_state,
282 char *fastmap)
283 {
284 re_dfa_t *dfa = bufp->buffer;
285 Idx node_cnt;
286 bool icase = (dfa->mb_cur_max == 1 && (bufp->syntax & RE_ICASE));
287 for (node_cnt = 0; node_cnt < init_state->nodes.nelem; ++node_cnt)
288 {
289 Idx node = init_state->nodes.elems[node_cnt];
290 re_token_type_t type = dfa->nodes[node].type;
291
292 if (type == CHARACTER)
293 {
294 re_set_fastmap (fastmap, icase, dfa->nodes[node].opr.c);
295 if ((bufp->syntax & RE_ICASE) && dfa->mb_cur_max > 1)
296 {
297 unsigned char buf[MB_LEN_MAX];
298 unsigned char *p;
299 wchar_t wc;
300 mbstate_t state;
301
302 p = buf;
303 *p++ = dfa->nodes[node].opr.c;
304 while (++node < dfa->nodes_len
305 && dfa->nodes[node].type == CHARACTER
306 && dfa->nodes[node].mb_partial)
307 *p++ = dfa->nodes[node].opr.c;
308 memset (&state, '\0', sizeof (state));
309 if (__mbrtowc (&wc, (const char *) buf, p - buf,
310 &state) == p - buf
311 && (__wcrtomb ((char *) buf, __towlower (wc), &state)
312 != (size_t) -1))
313 re_set_fastmap (fastmap, false, buf[0]);
314 }
315 }
316 else if (type == SIMPLE_BRACKET)
317 {
318 int i, ch;
319 for (i = 0, ch = 0; i < BITSET_WORDS; ++i)
320 {
321 int j;
322 bitset_word_t w = dfa->nodes[node].opr.sbcset[i];
323 for (j = 0; j < BITSET_WORD_BITS; ++j, ++ch)
324 if (w & ((bitset_word_t) 1 << j))
325 re_set_fastmap (fastmap, icase, ch);
326 }
327 }
328 else if (type == COMPLEX_BRACKET)
329 {
330 re_charset_t *cset = dfa->nodes[node].opr.mbcset;
331 Idx i;
332
333 #ifdef _LIBC
334 /* See if we have to try all bytes which start multiple collation
335 elements.
336 e.g. In da_DK, we want to catch 'a' since "aa" is a valid
337 collation element, and don't catch 'b' since 'b' is
338 the only collation element which starts from 'b' (and
339 it is caught by SIMPLE_BRACKET). */
340 if (_NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES) != 0
341 && (cset->ncoll_syms || cset->nranges))
342 {
343 const int32_t *table = (const int32_t *)
344 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
345 for (i = 0; i < SBC_MAX; ++i)
346 if (table[i] < 0)
347 re_set_fastmap (fastmap, icase, i);
348 }
349 #endif /* _LIBC */
350
351 /* See if we have to start the match at all multibyte characters,
352 i.e. where we would not find an invalid sequence. This only
353 applies to multibyte character sets; for single byte character
354 sets, the SIMPLE_BRACKET again suffices. */
355 if (dfa->mb_cur_max > 1
356 && (cset->nchar_classes || cset->non_match || cset->nranges
357 #ifdef _LIBC
358 || cset->nequiv_classes
359 #endif /* _LIBC */
360 ))
361 {
362 unsigned char c = 0;
363 do
364 {
365 mbstate_t mbs;
366 memset (&mbs, 0, sizeof (mbs));
367 if (__mbrtowc (NULL, (char *) &c, 1, &mbs) == (size_t) -2)
368 re_set_fastmap (fastmap, false, (int) c);
369 }
370 while (++c != 0);
371 }
372
373 else
374 {
375 /* ... Else catch all bytes which can start the mbchars. */
376 for (i = 0; i < cset->nmbchars; ++i)
377 {
378 char buf[256];
379 mbstate_t state;
380 memset (&state, '\0', sizeof (state));
381 if (__wcrtomb (buf, cset->mbchars[i], &state) != (size_t) -1)
382 re_set_fastmap (fastmap, icase, *(unsigned char *) buf);
383 if ((bufp->syntax & RE_ICASE) && dfa->mb_cur_max > 1)
384 {
385 if (__wcrtomb (buf, __towlower (cset->mbchars[i]), &state)
386 != (size_t) -1)
387 re_set_fastmap (fastmap, false, *(unsigned char *) buf);
388 }
389 }
390 }
391 }
392 else if (type == OP_PERIOD || type == OP_UTF8_PERIOD || type == END_OF_RE)
393 {
394 memset (fastmap, '\1', sizeof (char) * SBC_MAX);
395 if (type == END_OF_RE)
396 bufp->can_be_null = 1;
397 return;
398 }
399 }
400 }
401
402 /* Entry point for POSIX code. */
403 /* regcomp takes a regular expression as a string and compiles it.
404
405 PREG is a regex_t *. We do not expect any fields to be initialized,
406 since POSIX says we shouldn't. Thus, we set
407
408 'buffer' to the compiled pattern;
409 'used' to the length of the compiled pattern;
410 'syntax' to RE_SYNTAX_POSIX_EXTENDED if the
411 REG_EXTENDED bit in CFLAGS is set; otherwise, to
412 RE_SYNTAX_POSIX_BASIC;
413 'newline_anchor' to REG_NEWLINE being set in CFLAGS;
414 'fastmap' to an allocated space for the fastmap;
415 'fastmap_accurate' to zero;
416 're_nsub' to the number of subexpressions in PATTERN.
417
418 PATTERN is the address of the pattern string.
419
420 CFLAGS is a series of bits which affect compilation.
421
422 If REG_EXTENDED is set, we use POSIX extended syntax; otherwise, we
423 use POSIX basic syntax.
424
425 If REG_NEWLINE is set, then . and [^...] don't match newline.
426 Also, regexec will try a match beginning after every newline.
427
428 If REG_ICASE is set, then we considers upper- and lowercase
429 versions of letters to be equivalent when matching.
430
431 If REG_NOSUB is set, then when PREG is passed to regexec, that
432 routine will report only success or failure, and nothing about the
433 registers.
434
435 It returns 0 if it succeeds, nonzero if it doesn't. (See regex.h for
436 the return codes and their meanings.) */
437
438 int
439 regcomp (regex_t *__restrict preg, const char *__restrict pattern, int cflags)
440 {
441 reg_errcode_t ret;
442 reg_syntax_t syntax = ((cflags & REG_EXTENDED) ? RE_SYNTAX_POSIX_EXTENDED
443 : RE_SYNTAX_POSIX_BASIC);
444
445 preg->buffer = NULL;
446 preg->allocated = 0;
447 preg->used = 0;
448
449 /* Try to allocate space for the fastmap. */
450 preg->fastmap = re_malloc (char, SBC_MAX);
451 if (__glibc_unlikely (preg->fastmap == NULL))
452 return REG_ESPACE;
453
454 syntax |= (cflags & REG_ICASE) ? RE_ICASE : 0;
455
456 /* If REG_NEWLINE is set, newlines are treated differently. */
457 if (cflags & REG_NEWLINE)
458 { /* REG_NEWLINE implies neither . nor [^...] match newline. */
459 syntax &= ~RE_DOT_NEWLINE;
460 syntax |= RE_HAT_LISTS_NOT_NEWLINE;
461 /* It also changes the matching behavior. */
462 preg->newline_anchor = 1;
463 }
464 else
465 preg->newline_anchor = 0;
466 preg->no_sub = !!(cflags & REG_NOSUB);
467 preg->translate = NULL;
468
469 ret = re_compile_internal (preg, pattern, strlen (pattern), syntax);
470
471 /* POSIX doesn't distinguish between an unmatched open-group and an
472 unmatched close-group: both are REG_EPAREN. */
473 if (ret == REG_ERPAREN)
474 ret = REG_EPAREN;
475
476 /* We have already checked preg->fastmap != NULL. */
477 if (__glibc_likely (ret == REG_NOERROR))
478 /* Compute the fastmap now, since regexec cannot modify the pattern
479 buffer. This function never fails in this implementation. */
480 (void) re_compile_fastmap (preg);
481 else
482 {
483 /* Some error occurred while compiling the expression. */
484 re_free (preg->fastmap);
485 preg->fastmap = NULL;
486 }
487
488 return (int) ret;
489 }
490 libc_hidden_def (__regcomp)
491 weak_alias (__regcomp, regcomp)
492
493 /* Returns a message corresponding to an error code, ERRCODE, returned
494 from either regcomp or regexec. We don't use PREG here. */
495
496 size_t
497 regerror (int errcode, const regex_t *__restrict preg, char *__restrict errbuf,
498 size_t errbuf_size)
499 {
500 const char *msg;
501 size_t msg_size;
502 int nerrcodes = sizeof __re_error_msgid_idx / sizeof __re_error_msgid_idx[0];
503
504 if (__glibc_unlikely (errcode < 0 || errcode >= nerrcodes))
505 /* Only error codes returned by the rest of the code should be passed
506 to this routine. If we are given anything else, or if other regex
507 code generates an invalid error code, then the program has a bug.
508 Dump core so we can fix it. */
509 abort ();
510
511 msg = gettext (__re_error_msgid + __re_error_msgid_idx[errcode]);
512
513 msg_size = strlen (msg) + 1; /* Includes the null. */
514
515 if (__glibc_likely (errbuf_size != 0))
516 {
517 size_t cpy_size = msg_size;
518 if (__glibc_unlikely (msg_size > errbuf_size))
519 {
520 cpy_size = errbuf_size - 1;
521 errbuf[cpy_size] = '\0';
522 }
523 memcpy (errbuf, msg, cpy_size);
524 }
525
526 return msg_size;
527 }
528 weak_alias (__regerror, regerror)
529
530
531 /* This static array is used for the map to single-byte characters when
532 UTF-8 is used. Otherwise we would allocate memory just to initialize
533 it the same all the time. UTF-8 is the preferred encoding so this is
534 a worthwhile optimization. */
535 static const bitset_t utf8_sb_map =
536 {
537 /* Set the first 128 bits. */
538 #if (defined __GNUC__ || __clang_major__ >= 4) && !defined __STRICT_ANSI__
539 [0 ... 0x80 / BITSET_WORD_BITS - 1] = BITSET_WORD_MAX
540 #else
541 # if 4 * BITSET_WORD_BITS < ASCII_CHARS
542 # error "bitset_word_t is narrower than 32 bits"
543 # elif 3 * BITSET_WORD_BITS < ASCII_CHARS
544 BITSET_WORD_MAX, BITSET_WORD_MAX, BITSET_WORD_MAX,
545 # elif 2 * BITSET_WORD_BITS < ASCII_CHARS
546 BITSET_WORD_MAX, BITSET_WORD_MAX,
547 # elif 1 * BITSET_WORD_BITS < ASCII_CHARS
548 BITSET_WORD_MAX,
549 # endif
550 (BITSET_WORD_MAX
551 >> (SBC_MAX % BITSET_WORD_BITS == 0
552 ? 0
553 : BITSET_WORD_BITS - SBC_MAX % BITSET_WORD_BITS))
554 #endif
555 };
556
557
558 static void
559 free_dfa_content (re_dfa_t *dfa)
560 {
561 Idx i, j;
562
563 if (dfa->nodes)
564 for (i = 0; i < dfa->nodes_len; ++i)
565 free_token (dfa->nodes + i);
566 re_free (dfa->nexts);
567 for (i = 0; i < dfa->nodes_len; ++i)
568 {
569 if (dfa->eclosures != NULL)
570 re_node_set_free (dfa->eclosures + i);
571 if (dfa->inveclosures != NULL)
572 re_node_set_free (dfa->inveclosures + i);
573 if (dfa->edests != NULL)
574 re_node_set_free (dfa->edests + i);
575 }
576 re_free (dfa->edests);
577 re_free (dfa->eclosures);
578 re_free (dfa->inveclosures);
579 re_free (dfa->nodes);
580
581 if (dfa->state_table)
582 for (i = 0; i <= dfa->state_hash_mask; ++i)
583 {
584 struct re_state_table_entry *entry = dfa->state_table + i;
585 for (j = 0; j < entry->num; ++j)
586 {
587 re_dfastate_t *state = entry->array[j];
588 free_state (state);
589 }
590 re_free (entry->array);
591 }
592 re_free (dfa->state_table);
593 if (dfa->sb_char != utf8_sb_map)
594 re_free (dfa->sb_char);
595 re_free (dfa->subexp_map);
596 #ifdef DEBUG
597 re_free (dfa->re_str);
598 #endif
599
600 re_free (dfa);
601 }
602
603
604 /* Free dynamically allocated space used by PREG. */
605
606 void
607 regfree (regex_t *preg)
608 {
609 re_dfa_t *dfa = preg->buffer;
610 if (__glibc_likely (dfa != NULL))
611 {
612 lock_fini (dfa->lock);
613 free_dfa_content (dfa);
614 }
615 preg->buffer = NULL;
616 preg->allocated = 0;
617
618 re_free (preg->fastmap);
619 preg->fastmap = NULL;
620
621 re_free (preg->translate);
622 preg->translate = NULL;
623 }
624 libc_hidden_def (__regfree)
625 weak_alias (__regfree, regfree)
626
627 /* Entry points compatible with 4.2 BSD regex library. We don't define
628 them unless specifically requested. */
629
630 #if defined _REGEX_RE_COMP || defined _LIBC
631
632 /* BSD has one and only one pattern buffer. */
633 static struct re_pattern_buffer re_comp_buf;
634
635 char *
636 # ifdef _LIBC
637 /* Make these definitions weak in libc, so POSIX programs can redefine
638 these names if they don't use our functions, and still use
639 regcomp/regexec above without link errors. */
640 weak_function
641 # endif
642 re_comp (const char *s)
643 {
644 reg_errcode_t ret;
645 char *fastmap;
646
647 if (!s)
648 {
649 if (!re_comp_buf.buffer)
650 return gettext ("No previous regular expression");
651 return 0;
652 }
653
654 if (re_comp_buf.buffer)
655 {
656 fastmap = re_comp_buf.fastmap;
657 re_comp_buf.fastmap = NULL;
658 __regfree (&re_comp_buf);
659 memset (&re_comp_buf, '\0', sizeof (re_comp_buf));
660 re_comp_buf.fastmap = fastmap;
661 }
662
663 if (re_comp_buf.fastmap == NULL)
664 {
665 re_comp_buf.fastmap = re_malloc (char, SBC_MAX);
666 if (re_comp_buf.fastmap == NULL)
667 return (char *) gettext (__re_error_msgid
668 + __re_error_msgid_idx[(int) REG_ESPACE]);
669 }
670
671 /* Since 're_exec' always passes NULL for the 'regs' argument, we
672 don't need to initialize the pattern buffer fields which affect it. */
673
674 /* Match anchors at newlines. */
675 re_comp_buf.newline_anchor = 1;
676
677 ret = re_compile_internal (&re_comp_buf, s, strlen (s), re_syntax_options);
678
679 if (!ret)
680 return NULL;
681
682 /* Yes, we're discarding 'const' here if !HAVE_LIBINTL. */
683 return (char *) gettext (__re_error_msgid + __re_error_msgid_idx[(int) ret]);
684 }
685
686 #ifdef _LIBC
687 libc_freeres_fn (free_mem)
688 {
689 __regfree (&re_comp_buf);
690 }
691 #endif
692
693 #endif /* _REGEX_RE_COMP */
694
695 /* Internal entry point.
696 Compile the regular expression PATTERN, whose length is LENGTH.
697 SYNTAX indicate regular expression's syntax. */
698
699 static reg_errcode_t
700 re_compile_internal (regex_t *preg, const char * pattern, size_t length,
701 reg_syntax_t syntax)
702 {
703 reg_errcode_t err = REG_NOERROR;
704 re_dfa_t *dfa;
705 re_string_t regexp;
706
707 /* Initialize the pattern buffer. */
708 preg->fastmap_accurate = 0;
709 preg->syntax = syntax;
710 preg->not_bol = preg->not_eol = 0;
711 preg->used = 0;
712 preg->re_nsub = 0;
713 preg->can_be_null = 0;
714 preg->regs_allocated = REGS_UNALLOCATED;
715
716 /* Initialize the dfa. */
717 dfa = preg->buffer;
718 if (__glibc_unlikely (preg->allocated < sizeof (re_dfa_t)))
719 {
720 /* If zero allocated, but buffer is non-null, try to realloc
721 enough space. This loses if buffer's address is bogus, but
722 that is the user's responsibility. If ->buffer is NULL this
723 is a simple allocation. */
724 dfa = re_realloc (preg->buffer, re_dfa_t, 1);
725 if (dfa == NULL)
726 return REG_ESPACE;
727 preg->allocated = sizeof (re_dfa_t);
728 preg->buffer = dfa;
729 }
730 preg->used = sizeof (re_dfa_t);
731
732 err = init_dfa (dfa, length);
733 if (__glibc_unlikely (err == REG_NOERROR && lock_init (dfa->lock) != 0))
734 err = REG_ESPACE;
735 if (__glibc_unlikely (err != REG_NOERROR))
736 {
737 free_dfa_content (dfa);
738 preg->buffer = NULL;
739 preg->allocated = 0;
740 return err;
741 }
742 #ifdef DEBUG
743 /* Note: length+1 will not overflow since it is checked in init_dfa. */
744 dfa->re_str = re_malloc (char, length + 1);
745 strncpy (dfa->re_str, pattern, length + 1);
746 #endif
747
748 err = re_string_construct (&regexp, pattern, length, preg->translate,
749 (syntax & RE_ICASE) != 0, dfa);
750 if (__glibc_unlikely (err != REG_NOERROR))
751 {
752 re_compile_internal_free_return:
753 free_workarea_compile (preg);
754 re_string_destruct (&regexp);
755 lock_fini (dfa->lock);
756 free_dfa_content (dfa);
757 preg->buffer = NULL;
758 preg->allocated = 0;
759 return err;
760 }
761
762 /* Parse the regular expression, and build a structure tree. */
763 preg->re_nsub = 0;
764 dfa->str_tree = parse (&regexp, preg, syntax, &err);
765 if (__glibc_unlikely (dfa->str_tree == NULL))
766 goto re_compile_internal_free_return;
767
768 /* Analyze the tree and create the nfa. */
769 err = analyze (preg);
770 if (__glibc_unlikely (err != REG_NOERROR))
771 goto re_compile_internal_free_return;
772
773 /* If possible, do searching in single byte encoding to speed things up. */
774 if (dfa->is_utf8 && !(syntax & RE_ICASE) && preg->translate == NULL)
775 optimize_utf8 (dfa);
776
777 /* Then create the initial state of the dfa. */
778 err = create_initial_state (dfa);
779
780 /* Release work areas. */
781 free_workarea_compile (preg);
782 re_string_destruct (&regexp);
783
784 if (__glibc_unlikely (err != REG_NOERROR))
785 {
786 lock_fini (dfa->lock);
787 free_dfa_content (dfa);
788 preg->buffer = NULL;
789 preg->allocated = 0;
790 }
791
792 return err;
793 }
794
795 /* Initialize DFA. We use the length of the regular expression PAT_LEN
796 as the initial length of some arrays. */
797
798 static reg_errcode_t
799 init_dfa (re_dfa_t *dfa, size_t pat_len)
800 {
801 __re_size_t table_size;
802 #ifndef _LIBC
803 const char *codeset_name;
804 #endif
805 size_t max_i18n_object_size = MAX (sizeof (wchar_t), sizeof (wctype_t));
806 size_t max_object_size =
807 MAX (sizeof (struct re_state_table_entry),
808 MAX (sizeof (re_token_t),
809 MAX (sizeof (re_node_set),
810 MAX (sizeof (regmatch_t),
811 max_i18n_object_size))));
812
813 memset (dfa, '\0', sizeof (re_dfa_t));
814
815 /* Force allocation of str_tree_storage the first time. */
816 dfa->str_tree_storage_idx = BIN_TREE_STORAGE_SIZE;
817
818 /* Avoid overflows. The extra "/ 2" is for the table_size doubling
819 calculation below, and for similar doubling calculations
820 elsewhere. And it's <= rather than <, because some of the
821 doubling calculations add 1 afterwards. */
822 if (__glibc_unlikely (MIN (IDX_MAX, SIZE_MAX / max_object_size) / 2
823 <= pat_len))
824 return REG_ESPACE;
825
826 dfa->nodes_alloc = pat_len + 1;
827 dfa->nodes = re_malloc (re_token_t, dfa->nodes_alloc);
828
829 /* table_size = 2 ^ ceil(log pat_len) */
830 for (table_size = 1; ; table_size <<= 1)
831 if (table_size > pat_len)
832 break;
833
834 dfa->state_table = calloc (table_size, sizeof (struct re_state_table_entry));
835 dfa->state_hash_mask = table_size - 1;
836
837 dfa->mb_cur_max = MB_CUR_MAX;
838 #ifdef _LIBC
839 if (dfa->mb_cur_max == 6
840 && strcmp (_NL_CURRENT (LC_CTYPE, _NL_CTYPE_CODESET_NAME), "UTF-8") == 0)
841 dfa->is_utf8 = 1;
842 dfa->map_notascii = (_NL_CURRENT_WORD (LC_CTYPE, _NL_CTYPE_MAP_TO_NONASCII)
843 != 0);
844 #else
845 codeset_name = nl_langinfo (CODESET);
846 if ((codeset_name[0] == 'U' || codeset_name[0] == 'u')
847 && (codeset_name[1] == 'T' || codeset_name[1] == 't')
848 && (codeset_name[2] == 'F' || codeset_name[2] == 'f')
849 && strcmp (codeset_name + 3 + (codeset_name[3] == '-'), "8") == 0)
850 dfa->is_utf8 = 1;
851
852 /* We check exhaustively in the loop below if this charset is a
853 superset of ASCII. */
854 dfa->map_notascii = 0;
855 #endif
856
857 if (dfa->mb_cur_max > 1)
858 {
859 if (dfa->is_utf8)
860 dfa->sb_char = (re_bitset_ptr_t) utf8_sb_map;
861 else
862 {
863 int i, j, ch;
864
865 dfa->sb_char = (re_bitset_ptr_t) calloc (1, sizeof (bitset_t));
866 if (__glibc_unlikely (dfa->sb_char == NULL))
867 return REG_ESPACE;
868
869 /* Set the bits corresponding to single byte chars. */
870 for (i = 0, ch = 0; i < BITSET_WORDS; ++i)
871 for (j = 0; j < BITSET_WORD_BITS; ++j, ++ch)
872 {
873 wint_t wch = __btowc (ch);
874 if (wch != WEOF)
875 dfa->sb_char[i] |= (bitset_word_t) 1 << j;
876 #ifndef _LIBC
877 if (isascii (ch) && wch != ch)
878 dfa->map_notascii = 1;
879 #endif
880 }
881 }
882 }
883
884 if (__glibc_unlikely (dfa->nodes == NULL || dfa->state_table == NULL))
885 return REG_ESPACE;
886 return REG_NOERROR;
887 }
888
889 /* Initialize WORD_CHAR table, which indicate which character is
890 "word". In this case "word" means that it is the word construction
891 character used by some operators like "\<", "\>", etc. */
892
893 static void
894 init_word_char (re_dfa_t *dfa)
895 {
896 int i = 0;
897 int j;
898 int ch = 0;
899 dfa->word_ops_used = 1;
900 if (__glibc_likely (dfa->map_notascii == 0))
901 {
902 bitset_word_t bits0 = 0x00000000;
903 bitset_word_t bits1 = 0x03ff0000;
904 bitset_word_t bits2 = 0x87fffffe;
905 bitset_word_t bits3 = 0x07fffffe;
906 if (BITSET_WORD_BITS == 64)
907 {
908 /* Pacify gcc -Woverflow on 32-bit platforms. */
909 dfa->word_char[0] = bits1 << 31 << 1 | bits0;
910 dfa->word_char[1] = bits3 << 31 << 1 | bits2;
911 i = 2;
912 }
913 else if (BITSET_WORD_BITS == 32)
914 {
915 dfa->word_char[0] = bits0;
916 dfa->word_char[1] = bits1;
917 dfa->word_char[2] = bits2;
918 dfa->word_char[3] = bits3;
919 i = 4;
920 }
921 else
922 goto general_case;
923 ch = 128;
924
925 if (__glibc_likely (dfa->is_utf8))
926 {
927 memset (&dfa->word_char[i], '\0', (SBC_MAX - ch) / 8);
928 return;
929 }
930 }
931
932 general_case:
933 for (; i < BITSET_WORDS; ++i)
934 for (j = 0; j < BITSET_WORD_BITS; ++j, ++ch)
935 if (isalnum (ch) || ch == '_')
936 dfa->word_char[i] |= (bitset_word_t) 1 << j;
937 }
938
939 /* Free the work area which are only used while compiling. */
940
941 static void
942 free_workarea_compile (regex_t *preg)
943 {
944 re_dfa_t *dfa = preg->buffer;
945 bin_tree_storage_t *storage, *next;
946 for (storage = dfa->str_tree_storage; storage; storage = next)
947 {
948 next = storage->next;
949 re_free (storage);
950 }
951 dfa->str_tree_storage = NULL;
952 dfa->str_tree_storage_idx = BIN_TREE_STORAGE_SIZE;
953 dfa->str_tree = NULL;
954 re_free (dfa->org_indices);
955 dfa->org_indices = NULL;
956 }
957
958 /* Create initial states for all contexts. */
959
960 static reg_errcode_t
961 create_initial_state (re_dfa_t *dfa)
962 {
963 Idx first, i;
964 reg_errcode_t err;
965 re_node_set init_nodes;
966
967 /* Initial states have the epsilon closure of the node which is
968 the first node of the regular expression. */
969 first = dfa->str_tree->first->node_idx;
970 dfa->init_node = first;
971 err = re_node_set_init_copy (&init_nodes, dfa->eclosures + first);
972 if (__glibc_unlikely (err != REG_NOERROR))
973 return err;
974
975 /* The back-references which are in initial states can epsilon transit,
976 since in this case all of the subexpressions can be null.
977 Then we add epsilon closures of the nodes which are the next nodes of
978 the back-references. */
979 if (dfa->nbackref > 0)
980 for (i = 0; i < init_nodes.nelem; ++i)
981 {
982 Idx node_idx = init_nodes.elems[i];
983 re_token_type_t type = dfa->nodes[node_idx].type;
984
985 Idx clexp_idx;
986 if (type != OP_BACK_REF)
987 continue;
988 for (clexp_idx = 0; clexp_idx < init_nodes.nelem; ++clexp_idx)
989 {
990 re_token_t *clexp_node;
991 clexp_node = dfa->nodes + init_nodes.elems[clexp_idx];
992 if (clexp_node->type == OP_CLOSE_SUBEXP
993 && clexp_node->opr.idx == dfa->nodes[node_idx].opr.idx)
994 break;
995 }
996 if (clexp_idx == init_nodes.nelem)
997 continue;
998
999 if (type == OP_BACK_REF)
1000 {
1001 Idx dest_idx = dfa->edests[node_idx].elems[0];
1002 if (!re_node_set_contains (&init_nodes, dest_idx))
1003 {
1004 err
1005 = re_node_set_merge (&init_nodes, dfa->eclosures + dest_idx);
1006 if (err != REG_NOERROR)
1007 break;
1008 i = 0;
1009 }
1010 }
1011 }
1012
1013 /* It must be the first time to invoke acquire_state. */
1014 dfa->init_state
1015 = (err == REG_NOERROR
1016 ? re_acquire_state_context (&err, dfa, &init_nodes, 0)
1017 : NULL);
1018 if (__glibc_unlikely (dfa->init_state == NULL))
1019 {
1020 /* Don't check ERR here, as the initial state must not be null. */
1021 }
1022 else if (dfa->init_state->has_constraint)
1023 {
1024 dfa->init_state_word = re_acquire_state_context (&err, dfa, &init_nodes,
1025 CONTEXT_WORD);
1026 dfa->init_state_nl = re_acquire_state_context (&err, dfa, &init_nodes,
1027 CONTEXT_NEWLINE);
1028 dfa->init_state_begbuf = re_acquire_state_context (&err, dfa,
1029 &init_nodes,
1030 CONTEXT_NEWLINE
1031 | CONTEXT_BEGBUF);
1032 }
1033 else
1034 dfa->init_state_word = dfa->init_state_nl
1035 = dfa->init_state_begbuf = dfa->init_state;
1036
1037 re_node_set_free (&init_nodes);
1038 return err;
1039 }
1040
1041 /* If it is possible to do searching in single byte encoding instead of UTF-8
1042 to speed things up, set dfa->mb_cur_max to 1, clear is_utf8 and change
1043 DFA nodes where needed. */
1044
1045 static void
1046 optimize_utf8 (re_dfa_t *dfa)
1047 {
1048 Idx node;
1049 int i;
1050 bool mb_chars = false;
1051 bool has_period = false;
1052
1053 for (node = 0; node < dfa->nodes_len; ++node)
1054 switch (dfa->nodes[node].type)
1055 {
1056 case CHARACTER:
1057 if (dfa->nodes[node].opr.c >= ASCII_CHARS)
1058 mb_chars = true;
1059 break;
1060 case ANCHOR:
1061 switch (dfa->nodes[node].opr.ctx_type)
1062 {
1063 case LINE_FIRST:
1064 case LINE_LAST:
1065 case BUF_FIRST:
1066 case BUF_LAST:
1067 break;
1068 default:
1069 /* Word anchors etc. cannot be handled. It's okay to test
1070 opr.ctx_type since constraints (for all DFA nodes) are
1071 created by ORing one or more opr.ctx_type values. */
1072 return;
1073 }
1074 break;
1075 case OP_PERIOD:
1076 has_period = true;
1077 break;
1078 case OP_BACK_REF:
1079 case OP_ALT:
1080 case END_OF_RE:
1081 case OP_DUP_ASTERISK:
1082 case OP_OPEN_SUBEXP:
1083 case OP_CLOSE_SUBEXP:
1084 break;
1085 case COMPLEX_BRACKET:
1086 return;
1087 case SIMPLE_BRACKET:
1088 /* Just double check. */
1089 {
1090 int rshift = (ASCII_CHARS % BITSET_WORD_BITS == 0
1091 ? 0
1092 : BITSET_WORD_BITS - ASCII_CHARS % BITSET_WORD_BITS);
1093 for (i = ASCII_CHARS / BITSET_WORD_BITS; i < BITSET_WORDS; ++i)
1094 {
1095 if (dfa->nodes[node].opr.sbcset[i] >> rshift != 0)
1096 return;
1097 rshift = 0;
1098 }
1099 }
1100 break;
1101 default:
1102 abort ();
1103 }
1104
1105 if (mb_chars || has_period)
1106 for (node = 0; node < dfa->nodes_len; ++node)
1107 {
1108 if (dfa->nodes[node].type == CHARACTER
1109 && dfa->nodes[node].opr.c >= ASCII_CHARS)
1110 dfa->nodes[node].mb_partial = 0;
1111 else if (dfa->nodes[node].type == OP_PERIOD)
1112 dfa->nodes[node].type = OP_UTF8_PERIOD;
1113 }
1114
1115 /* The search can be in single byte locale. */
1116 dfa->mb_cur_max = 1;
1117 dfa->is_utf8 = 0;
1118 dfa->has_mb_node = dfa->nbackref > 0 || has_period;
1119 }
1120
1121 /* Analyze the structure tree, and calculate "first", "next", "edest",
1122 "eclosure", and "inveclosure". */
1123
1124 static reg_errcode_t
1125 analyze (regex_t *preg)
1126 {
1127 re_dfa_t *dfa = preg->buffer;
1128 reg_errcode_t ret;
1129
1130 /* Allocate arrays. */
1131 dfa->nexts = re_malloc (Idx, dfa->nodes_alloc);
1132 dfa->org_indices = re_malloc (Idx, dfa->nodes_alloc);
1133 dfa->edests = re_malloc (re_node_set, dfa->nodes_alloc);
1134 dfa->eclosures = re_malloc (re_node_set, dfa->nodes_alloc);
1135 if (__glibc_unlikely (dfa->nexts == NULL || dfa->org_indices == NULL
1136 || dfa->edests == NULL || dfa->eclosures == NULL))
1137 return REG_ESPACE;
1138
1139 dfa->subexp_map = re_malloc (Idx, preg->re_nsub);
1140 if (dfa->subexp_map != NULL)
1141 {
1142 Idx i;
1143 for (i = 0; i < preg->re_nsub; i++)
1144 dfa->subexp_map[i] = i;
1145 preorder (dfa->str_tree, optimize_subexps, dfa);
1146 for (i = 0; i < preg->re_nsub; i++)
1147 if (dfa->subexp_map[i] != i)
1148 break;
1149 if (i == preg->re_nsub)
1150 {
1151 re_free (dfa->subexp_map);
1152 dfa->subexp_map = NULL;
1153 }
1154 }
1155
1156 ret = postorder (dfa->str_tree, lower_subexps, preg);
1157 if (__glibc_unlikely (ret != REG_NOERROR))
1158 return ret;
1159 ret = postorder (dfa->str_tree, calc_first, dfa);
1160 if (__glibc_unlikely (ret != REG_NOERROR))
1161 return ret;
1162 preorder (dfa->str_tree, calc_next, dfa);
1163 ret = preorder (dfa->str_tree, link_nfa_nodes, dfa);
1164 if (__glibc_unlikely (ret != REG_NOERROR))
1165 return ret;
1166 ret = calc_eclosure (dfa);
1167 if (__glibc_unlikely (ret != REG_NOERROR))
1168 return ret;
1169
1170 /* We only need this during the prune_impossible_nodes pass in regexec.c;
1171 skip it if p_i_n will not run, as calc_inveclosure can be quadratic. */
1172 if ((!preg->no_sub && preg->re_nsub > 0 && dfa->has_plural_match)
1173 || dfa->nbackref)
1174 {
1175 dfa->inveclosures = re_malloc (re_node_set, dfa->nodes_len);
1176 if (__glibc_unlikely (dfa->inveclosures == NULL))
1177 return REG_ESPACE;
1178 ret = calc_inveclosure (dfa);
1179 }
1180
1181 return ret;
1182 }
1183
1184 /* Our parse trees are very unbalanced, so we cannot use a stack to
1185 implement parse tree visits. Instead, we use parent pointers and
1186 some hairy code in these two functions. */
1187 static reg_errcode_t
1188 postorder (bin_tree_t *root, reg_errcode_t (fn (void *, bin_tree_t *)),
1189 void *extra)
1190 {
1191 bin_tree_t *node, *prev;
1192
1193 for (node = root; ; )
1194 {
1195 /* Descend down the tree, preferably to the left (or to the right
1196 if that's the only child). */
1197 while (node->left || node->right)
1198 if (node->left)
1199 node = node->left;
1200 else
1201 node = node->right;
1202
1203 do
1204 {
1205 reg_errcode_t err = fn (extra, node);
1206 if (__glibc_unlikely (err != REG_NOERROR))
1207 return err;
1208 if (node->parent == NULL)
1209 return REG_NOERROR;
1210 prev = node;
1211 node = node->parent;
1212 }
1213 /* Go up while we have a node that is reached from the right. */
1214 while (node->right == prev || node->right == NULL);
1215 node = node->right;
1216 }
1217 }
1218
1219 static reg_errcode_t
1220 preorder (bin_tree_t *root, reg_errcode_t (fn (void *, bin_tree_t *)),
1221 void *extra)
1222 {
1223 bin_tree_t *node;
1224
1225 for (node = root; ; )
1226 {
1227 reg_errcode_t err = fn (extra, node);
1228 if (__glibc_unlikely (err != REG_NOERROR))
1229 return err;
1230
1231 /* Go to the left node, or up and to the right. */
1232 if (node->left)
1233 node = node->left;
1234 else
1235 {
1236 bin_tree_t *prev = NULL;
1237 while (node->right == prev || node->right == NULL)
1238 {
1239 prev = node;
1240 node = node->parent;
1241 if (!node)
1242 return REG_NOERROR;
1243 }
1244 node = node->right;
1245 }
1246 }
1247 }
1248
1249 /* Optimization pass: if a SUBEXP is entirely contained, strip it and tell
1250 re_search_internal to map the inner one's opr.idx to this one's. Adjust
1251 backreferences as well. Requires a preorder visit. */
1252 static reg_errcode_t
1253 optimize_subexps (void *extra, bin_tree_t *node)
1254 {
1255 re_dfa_t *dfa = (re_dfa_t *) extra;
1256
1257 if (node->token.type == OP_BACK_REF && dfa->subexp_map)
1258 {
1259 int idx = node->token.opr.idx;
1260 node->token.opr.idx = dfa->subexp_map[idx];
1261 dfa->used_bkref_map |= 1 << node->token.opr.idx;
1262 }
1263
1264 else if (node->token.type == SUBEXP
1265 && node->left && node->left->token.type == SUBEXP)
1266 {
1267 Idx other_idx = node->left->token.opr.idx;
1268
1269 node->left = node->left->left;
1270 if (node->left)
1271 node->left->parent = node;
1272
1273 dfa->subexp_map[other_idx] = dfa->subexp_map[node->token.opr.idx];
1274 if (other_idx < BITSET_WORD_BITS)
1275 dfa->used_bkref_map &= ~((bitset_word_t) 1 << other_idx);
1276 }
1277
1278 return REG_NOERROR;
1279 }
1280
1281 /* Lowering pass: Turn each SUBEXP node into the appropriate concatenation
1282 of OP_OPEN_SUBEXP, the body of the SUBEXP (if any) and OP_CLOSE_SUBEXP. */
1283 static reg_errcode_t
1284 lower_subexps (void *extra, bin_tree_t *node)
1285 {
1286 regex_t *preg = (regex_t *) extra;
1287 reg_errcode_t err = REG_NOERROR;
1288
1289 if (node->left && node->left->token.type == SUBEXP)
1290 {
1291 node->left = lower_subexp (&err, preg, node->left);
1292 if (node->left)
1293 node->left->parent = node;
1294 }
1295 if (node->right && node->right->token.type == SUBEXP)
1296 {
1297 node->right = lower_subexp (&err, preg, node->right);
1298 if (node->right)
1299 node->right->parent = node;
1300 }
1301
1302 return err;
1303 }
1304
1305 static bin_tree_t *
1306 lower_subexp (reg_errcode_t *err, regex_t *preg, bin_tree_t *node)
1307 {
1308 re_dfa_t *dfa = preg->buffer;
1309 bin_tree_t *body = node->left;
1310 bin_tree_t *op, *cls, *tree1, *tree;
1311
1312 if (preg->no_sub
1313 /* We do not optimize empty subexpressions, because otherwise we may
1314 have bad CONCAT nodes with NULL children. This is obviously not
1315 very common, so we do not lose much. An example that triggers
1316 this case is the sed "script" /\(\)/x. */
1317 && node->left != NULL
1318 && (node->token.opr.idx >= BITSET_WORD_BITS
1319 || !(dfa->used_bkref_map
1320 & ((bitset_word_t) 1 << node->token.opr.idx))))
1321 return node->left;
1322
1323 /* Convert the SUBEXP node to the concatenation of an
1324 OP_OPEN_SUBEXP, the contents, and an OP_CLOSE_SUBEXP. */
1325 op = create_tree (dfa, NULL, NULL, OP_OPEN_SUBEXP);
1326 cls = create_tree (dfa, NULL, NULL, OP_CLOSE_SUBEXP);
1327 tree1 = body ? create_tree (dfa, body, cls, CONCAT) : cls;
1328 tree = create_tree (dfa, op, tree1, CONCAT);
1329 if (__glibc_unlikely (tree == NULL || tree1 == NULL
1330 || op == NULL || cls == NULL))
1331 {
1332 *err = REG_ESPACE;
1333 return NULL;
1334 }
1335
1336 op->token.opr.idx = cls->token.opr.idx = node->token.opr.idx;
1337 op->token.opt_subexp = cls->token.opt_subexp = node->token.opt_subexp;
1338 return tree;
1339 }
1340
1341 /* Pass 1 in building the NFA: compute FIRST and create unlinked automaton
1342 nodes. Requires a postorder visit. */
1343 static reg_errcode_t
1344 calc_first (void *extra, bin_tree_t *node)
1345 {
1346 re_dfa_t *dfa = (re_dfa_t *) extra;
1347 if (node->token.type == CONCAT)
1348 {
1349 node->first = node->left->first;
1350 node->node_idx = node->left->node_idx;
1351 }
1352 else
1353 {
1354 node->first = node;
1355 node->node_idx = re_dfa_add_node (dfa, node->token);
1356 if (__glibc_unlikely (node->node_idx == -1))
1357 return REG_ESPACE;
1358 if (node->token.type == ANCHOR)
1359 dfa->nodes[node->node_idx].constraint = node->token.opr.ctx_type;
1360 }
1361 return REG_NOERROR;
1362 }
1363
1364 /* Pass 2: compute NEXT on the tree. Preorder visit. */
1365 static reg_errcode_t
1366 calc_next (void *extra, bin_tree_t *node)
1367 {
1368 switch (node->token.type)
1369 {
1370 case OP_DUP_ASTERISK:
1371 node->left->next = node;
1372 break;
1373 case CONCAT:
1374 node->left->next = node->right->first;
1375 node->right->next = node->next;
1376 break;
1377 default:
1378 if (node->left)
1379 node->left->next = node->next;
1380 if (node->right)
1381 node->right->next = node->next;
1382 break;
1383 }
1384 return REG_NOERROR;
1385 }
1386
1387 /* Pass 3: link all DFA nodes to their NEXT node (any order will do). */
1388 static reg_errcode_t
1389 link_nfa_nodes (void *extra, bin_tree_t *node)
1390 {
1391 re_dfa_t *dfa = (re_dfa_t *) extra;
1392 Idx idx = node->node_idx;
1393 reg_errcode_t err = REG_NOERROR;
1394
1395 switch (node->token.type)
1396 {
1397 case CONCAT:
1398 break;
1399
1400 case END_OF_RE:
1401 DEBUG_ASSERT (node->next == NULL);
1402 break;
1403
1404 case OP_DUP_ASTERISK:
1405 case OP_ALT:
1406 {
1407 Idx left, right;
1408 dfa->has_plural_match = 1;
1409 if (node->left != NULL)
1410 left = node->left->first->node_idx;
1411 else
1412 left = node->next->node_idx;
1413 if (node->right != NULL)
1414 right = node->right->first->node_idx;
1415 else
1416 right = node->next->node_idx;
1417 DEBUG_ASSERT (left > -1);
1418 DEBUG_ASSERT (right > -1);
1419 err = re_node_set_init_2 (dfa->edests + idx, left, right);
1420 }
1421 break;
1422
1423 case ANCHOR:
1424 case OP_OPEN_SUBEXP:
1425 case OP_CLOSE_SUBEXP:
1426 err = re_node_set_init_1 (dfa->edests + idx, node->next->node_idx);
1427 break;
1428
1429 case OP_BACK_REF:
1430 dfa->nexts[idx] = node->next->node_idx;
1431 if (node->token.type == OP_BACK_REF)
1432 err = re_node_set_init_1 (dfa->edests + idx, dfa->nexts[idx]);
1433 break;
1434
1435 default:
1436 DEBUG_ASSERT (!IS_EPSILON_NODE (node->token.type));
1437 dfa->nexts[idx] = node->next->node_idx;
1438 break;
1439 }
1440
1441 return err;
1442 }
1443
1444 /* Duplicate the epsilon closure of the node ROOT_NODE.
1445 Note that duplicated nodes have constraint INIT_CONSTRAINT in addition
1446 to their own constraint. */
1447
1448 static reg_errcode_t
1449 duplicate_node_closure (re_dfa_t *dfa, Idx top_org_node, Idx top_clone_node,
1450 Idx root_node, unsigned int init_constraint)
1451 {
1452 Idx org_node, clone_node;
1453 bool ok;
1454 unsigned int constraint = init_constraint;
1455 for (org_node = top_org_node, clone_node = top_clone_node;;)
1456 {
1457 Idx org_dest, clone_dest;
1458 if (dfa->nodes[org_node].type == OP_BACK_REF)
1459 {
1460 /* If the back reference epsilon-transit, its destination must
1461 also have the constraint. Then duplicate the epsilon closure
1462 of the destination of the back reference, and store it in
1463 edests of the back reference. */
1464 org_dest = dfa->nexts[org_node];
1465 re_node_set_empty (dfa->edests + clone_node);
1466 clone_dest = duplicate_node (dfa, org_dest, constraint);
1467 if (__glibc_unlikely (clone_dest == -1))
1468 return REG_ESPACE;
1469 dfa->nexts[clone_node] = dfa->nexts[org_node];
1470 ok = re_node_set_insert (dfa->edests + clone_node, clone_dest);
1471 if (__glibc_unlikely (! ok))
1472 return REG_ESPACE;
1473 }
1474 else if (dfa->edests[org_node].nelem == 0)
1475 {
1476 /* In case of the node can't epsilon-transit, don't duplicate the
1477 destination and store the original destination as the
1478 destination of the node. */
1479 dfa->nexts[clone_node] = dfa->nexts[org_node];
1480 break;
1481 }
1482 else if (dfa->edests[org_node].nelem == 1)
1483 {
1484 /* In case of the node can epsilon-transit, and it has only one
1485 destination. */
1486 org_dest = dfa->edests[org_node].elems[0];
1487 re_node_set_empty (dfa->edests + clone_node);
1488 /* If the node is root_node itself, it means the epsilon closure
1489 has a loop. Then tie it to the destination of the root_node. */
1490 if (org_node == root_node && clone_node != org_node)
1491 {
1492 ok = re_node_set_insert (dfa->edests + clone_node, org_dest);
1493 if (__glibc_unlikely (! ok))
1494 return REG_ESPACE;
1495 break;
1496 }
1497 /* In case the node has another constraint, append it. */
1498 constraint |= dfa->nodes[org_node].constraint;
1499 clone_dest = duplicate_node (dfa, org_dest, constraint);
1500 if (__glibc_unlikely (clone_dest == -1))
1501 return REG_ESPACE;
1502 ok = re_node_set_insert (dfa->edests + clone_node, clone_dest);
1503 if (__glibc_unlikely (! ok))
1504 return REG_ESPACE;
1505 }
1506 else /* dfa->edests[org_node].nelem == 2 */
1507 {
1508 /* In case of the node can epsilon-transit, and it has two
1509 destinations. In the bin_tree_t and DFA, that's '|' and '*'. */
1510 org_dest = dfa->edests[org_node].elems[0];
1511 re_node_set_empty (dfa->edests + clone_node);
1512 /* Search for a duplicated node which satisfies the constraint. */
1513 clone_dest = search_duplicated_node (dfa, org_dest, constraint);
1514 if (clone_dest == -1)
1515 {
1516 /* There is no such duplicated node, create a new one. */
1517 reg_errcode_t err;
1518 clone_dest = duplicate_node (dfa, org_dest, constraint);
1519 if (__glibc_unlikely (clone_dest == -1))
1520 return REG_ESPACE;
1521 ok = re_node_set_insert (dfa->edests + clone_node, clone_dest);
1522 if (__glibc_unlikely (! ok))
1523 return REG_ESPACE;
1524 err = duplicate_node_closure (dfa, org_dest, clone_dest,
1525 root_node, constraint);
1526 if (__glibc_unlikely (err != REG_NOERROR))
1527 return err;
1528 }
1529 else
1530 {
1531 /* There is a duplicated node which satisfies the constraint,
1532 use it to avoid infinite loop. */
1533 ok = re_node_set_insert (dfa->edests + clone_node, clone_dest);
1534 if (__glibc_unlikely (! ok))
1535 return REG_ESPACE;
1536 }
1537
1538 org_dest = dfa->edests[org_node].elems[1];
1539 clone_dest = duplicate_node (dfa, org_dest, constraint);
1540 if (__glibc_unlikely (clone_dest == -1))
1541 return REG_ESPACE;
1542 ok = re_node_set_insert (dfa->edests + clone_node, clone_dest);
1543 if (__glibc_unlikely (! ok))
1544 return REG_ESPACE;
1545 }
1546 org_node = org_dest;
1547 clone_node = clone_dest;
1548 }
1549 return REG_NOERROR;
1550 }
1551
1552 /* Search for a node which is duplicated from the node ORG_NODE, and
1553 satisfies the constraint CONSTRAINT. */
1554
1555 static Idx
1556 search_duplicated_node (const re_dfa_t *dfa, Idx org_node,
1557 unsigned int constraint)
1558 {
1559 Idx idx;
1560 for (idx = dfa->nodes_len - 1; dfa->nodes[idx].duplicated && idx > 0; --idx)
1561 {
1562 if (org_node == dfa->org_indices[idx]
1563 && constraint == dfa->nodes[idx].constraint)
1564 return idx; /* Found. */
1565 }
1566 return -1; /* Not found. */
1567 }
1568
1569 /* Duplicate the node whose index is ORG_IDX and set the constraint CONSTRAINT.
1570 Return the index of the new node, or -1 if insufficient storage is
1571 available. */
1572
1573 static Idx
1574 duplicate_node (re_dfa_t *dfa, Idx org_idx, unsigned int constraint)
1575 {
1576 Idx dup_idx = re_dfa_add_node (dfa, dfa->nodes[org_idx]);
1577 if (__glibc_likely (dup_idx != -1))
1578 {
1579 dfa->nodes[dup_idx].constraint = constraint;
1580 dfa->nodes[dup_idx].constraint |= dfa->nodes[org_idx].constraint;
1581 dfa->nodes[dup_idx].duplicated = 1;
1582
1583 /* Store the index of the original node. */
1584 dfa->org_indices[dup_idx] = org_idx;
1585 }
1586 return dup_idx;
1587 }
1588
1589 static reg_errcode_t
1590 calc_inveclosure (re_dfa_t *dfa)
1591 {
1592 Idx src, idx;
1593 bool ok;
1594 for (idx = 0; idx < dfa->nodes_len; ++idx)
1595 re_node_set_init_empty (dfa->inveclosures + idx);
1596
1597 for (src = 0; src < dfa->nodes_len; ++src)
1598 {
1599 Idx *elems = dfa->eclosures[src].elems;
1600 for (idx = 0; idx < dfa->eclosures[src].nelem; ++idx)
1601 {
1602 ok = re_node_set_insert_last (dfa->inveclosures + elems[idx], src);
1603 if (__glibc_unlikely (! ok))
1604 return REG_ESPACE;
1605 }
1606 }
1607
1608 return REG_NOERROR;
1609 }
1610
1611 /* Calculate "eclosure" for all the node in DFA. */
1612
1613 static reg_errcode_t
1614 calc_eclosure (re_dfa_t *dfa)
1615 {
1616 Idx node_idx;
1617 bool incomplete;
1618 DEBUG_ASSERT (dfa->nodes_len > 0);
1619 incomplete = false;
1620 /* For each nodes, calculate epsilon closure. */
1621 for (node_idx = 0; ; ++node_idx)
1622 {
1623 reg_errcode_t err;
1624 re_node_set eclosure_elem;
1625 if (node_idx == dfa->nodes_len)
1626 {
1627 if (!incomplete)
1628 break;
1629 incomplete = false;
1630 node_idx = 0;
1631 }
1632
1633 DEBUG_ASSERT (dfa->eclosures[node_idx].nelem != -1);
1634
1635 /* If we have already calculated, skip it. */
1636 if (dfa->eclosures[node_idx].nelem != 0)
1637 continue;
1638 /* Calculate epsilon closure of 'node_idx'. */
1639 err = calc_eclosure_iter (&eclosure_elem, dfa, node_idx, true);
1640 if (__glibc_unlikely (err != REG_NOERROR))
1641 return err;
1642
1643 if (dfa->eclosures[node_idx].nelem == 0)
1644 {
1645 incomplete = true;
1646 re_node_set_free (&eclosure_elem);
1647 }
1648 }
1649 return REG_NOERROR;
1650 }
1651
1652 /* Calculate epsilon closure of NODE. */
1653
1654 static reg_errcode_t
1655 calc_eclosure_iter (re_node_set *new_set, re_dfa_t *dfa, Idx node, bool root)
1656 {
1657 reg_errcode_t err;
1658 Idx i;
1659 re_node_set eclosure;
1660 bool incomplete = false;
1661 err = re_node_set_alloc (&eclosure, dfa->edests[node].nelem + 1);
1662 if (__glibc_unlikely (err != REG_NOERROR))
1663 return err;
1664
1665 /* An epsilon closure includes itself. */
1666 eclosure.elems[eclosure.nelem++] = node;
1667
1668 /* This indicates that we are calculating this node now.
1669 We reference this value to avoid infinite loop. */
1670 dfa->eclosures[node].nelem = -1;
1671
1672 /* If the current node has constraints, duplicate all nodes
1673 since they must inherit the constraints. */
1674 if (dfa->nodes[node].constraint
1675 && dfa->edests[node].nelem
1676 && !dfa->nodes[dfa->edests[node].elems[0]].duplicated)
1677 {
1678 err = duplicate_node_closure (dfa, node, node, node,
1679 dfa->nodes[node].constraint);
1680 }
1681
1682 /* Expand each epsilon destination nodes. */
1683 if (__glibc_likely (err == REG_NOERROR)
1684 && IS_EPSILON_NODE (dfa->nodes[node].type))
1685 for (i = 0; i < dfa->edests[node].nelem; ++i)
1686 {
1687 re_node_set eclosure_elem;
1688 Idx edest = dfa->edests[node].elems[i];
1689 /* If calculating the epsilon closure of 'edest' is in progress,
1690 return intermediate result. */
1691 if (dfa->eclosures[edest].nelem == -1)
1692 {
1693 incomplete = true;
1694 continue;
1695 }
1696 /* If we haven't calculated the epsilon closure of 'edest' yet,
1697 calculate now. Otherwise use calculated epsilon closure. */
1698 if (dfa->eclosures[edest].nelem == 0)
1699 {
1700 err = calc_eclosure_iter (&eclosure_elem, dfa, edest, false);
1701 if (__glibc_unlikely (err != REG_NOERROR))
1702 break;
1703 }
1704 else
1705 eclosure_elem = dfa->eclosures[edest];
1706 /* Merge the epsilon closure of 'edest'. */
1707 err = re_node_set_merge (&eclosure, &eclosure_elem);
1708 if (__glibc_unlikely (err != REG_NOERROR))
1709 break;
1710 /* If the epsilon closure of 'edest' is incomplete,
1711 the epsilon closure of this node is also incomplete. */
1712 if (dfa->eclosures[edest].nelem == 0)
1713 {
1714 incomplete = true;
1715 re_node_set_free (&eclosure_elem);
1716 }
1717 }
1718
1719 if (err != REG_NOERROR)
1720 re_node_set_free (&eclosure);
1721 else
1722 {
1723 if (incomplete && !root)
1724 dfa->eclosures[node].nelem = 0;
1725 else
1726 dfa->eclosures[node] = eclosure;
1727 *new_set = eclosure;
1728 }
1729
1730 return err;
1731 }
1732
1733 /* Functions for token which are used in the parser. */
1734
1735 /* Fetch a token from INPUT.
1736 We must not use this function inside bracket expressions. */
1737
1738 static void
1739 fetch_token (re_token_t *result, re_string_t *input, reg_syntax_t syntax)
1740 {
1741 re_string_skip_bytes (input, peek_token (result, input, syntax));
1742 }
1743
1744 /* Peek a token from INPUT, and return the length of the token.
1745 We must not use this function inside bracket expressions. */
1746
1747 static int
1748 peek_token (re_token_t *token, re_string_t *input, reg_syntax_t syntax)
1749 {
1750 unsigned char c;
1751
1752 if (re_string_eoi (input))
1753 {
1754 token->type = END_OF_RE;
1755 return 0;
1756 }
1757
1758 c = re_string_peek_byte (input, 0);
1759 token->opr.c = c;
1760
1761 token->word_char = 0;
1762 token->mb_partial = 0;
1763 if (input->mb_cur_max > 1
1764 && !re_string_first_byte (input, re_string_cur_idx (input)))
1765 {
1766 token->type = CHARACTER;
1767 token->mb_partial = 1;
1768 return 1;
1769 }
1770 if (c == '\\')
1771 {
1772 unsigned char c2;
1773 if (re_string_cur_idx (input) + 1 >= re_string_length (input))
1774 {
1775 token->type = BACK_SLASH;
1776 return 1;
1777 }
1778
1779 c2 = re_string_peek_byte_case (input, 1);
1780 token->opr.c = c2;
1781 token->type = CHARACTER;
1782 if (input->mb_cur_max > 1)
1783 {
1784 wint_t wc = re_string_wchar_at (input,
1785 re_string_cur_idx (input) + 1);
1786 token->word_char = IS_WIDE_WORD_CHAR (wc) != 0;
1787 }
1788 else
1789 token->word_char = IS_WORD_CHAR (c2) != 0;
1790
1791 switch (c2)
1792 {
1793 case '|':
1794 if (!(syntax & RE_LIMITED_OPS) && !(syntax & RE_NO_BK_VBAR))
1795 token->type = OP_ALT;
1796 break;
1797 case '1': case '2': case '3': case '4': case '5':
1798 case '6': case '7': case '8': case '9':
1799 if (!(syntax & RE_NO_BK_REFS))
1800 {
1801 token->type = OP_BACK_REF;
1802 token->opr.idx = c2 - '1';
1803 }
1804 break;
1805 case '<':
1806 if (!(syntax & RE_NO_GNU_OPS))
1807 {
1808 token->type = ANCHOR;
1809 token->opr.ctx_type = WORD_FIRST;
1810 }
1811 break;
1812 case '>':
1813 if (!(syntax & RE_NO_GNU_OPS))
1814 {
1815 token->type = ANCHOR;
1816 token->opr.ctx_type = WORD_LAST;
1817 }
1818 break;
1819 case 'b':
1820 if (!(syntax & RE_NO_GNU_OPS))
1821 {
1822 token->type = ANCHOR;
1823 token->opr.ctx_type = WORD_DELIM;
1824 }
1825 break;
1826 case 'B':
1827 if (!(syntax & RE_NO_GNU_OPS))
1828 {
1829 token->type = ANCHOR;
1830 token->opr.ctx_type = NOT_WORD_DELIM;
1831 }
1832 break;
1833 case 'w':
1834 if (!(syntax & RE_NO_GNU_OPS))
1835 token->type = OP_WORD;
1836 break;
1837 case 'W':
1838 if (!(syntax & RE_NO_GNU_OPS))
1839 token->type = OP_NOTWORD;
1840 break;
1841 case 's':
1842 if (!(syntax & RE_NO_GNU_OPS))
1843 token->type = OP_SPACE;
1844 break;
1845 case 'S':
1846 if (!(syntax & RE_NO_GNU_OPS))
1847 token->type = OP_NOTSPACE;
1848 break;
1849 case '`':
1850 if (!(syntax & RE_NO_GNU_OPS))
1851 {
1852 token->type = ANCHOR;
1853 token->opr.ctx_type = BUF_FIRST;
1854 }
1855 break;
1856 case '\'':
1857 if (!(syntax & RE_NO_GNU_OPS))
1858 {
1859 token->type = ANCHOR;
1860 token->opr.ctx_type = BUF_LAST;
1861 }
1862 break;
1863 case '(':
1864 if (!(syntax & RE_NO_BK_PARENS))
1865 token->type = OP_OPEN_SUBEXP;
1866 break;
1867 case ')':
1868 if (!(syntax & RE_NO_BK_PARENS))
1869 token->type = OP_CLOSE_SUBEXP;
1870 break;
1871 case '+':
1872 if (!(syntax & RE_LIMITED_OPS) && (syntax & RE_BK_PLUS_QM))
1873 token->type = OP_DUP_PLUS;
1874 break;
1875 case '?':
1876 if (!(syntax & RE_LIMITED_OPS) && (syntax & RE_BK_PLUS_QM))
1877 token->type = OP_DUP_QUESTION;
1878 break;
1879 case '{':
1880 if ((syntax & RE_INTERVALS) && (!(syntax & RE_NO_BK_BRACES)))
1881 token->type = OP_OPEN_DUP_NUM;
1882 break;
1883 case '}':
1884 if ((syntax & RE_INTERVALS) && (!(syntax & RE_NO_BK_BRACES)))
1885 token->type = OP_CLOSE_DUP_NUM;
1886 break;
1887 default:
1888 break;
1889 }
1890 return 2;
1891 }
1892
1893 token->type = CHARACTER;
1894 if (input->mb_cur_max > 1)
1895 {
1896 wint_t wc = re_string_wchar_at (input, re_string_cur_idx (input));
1897 token->word_char = IS_WIDE_WORD_CHAR (wc) != 0;
1898 }
1899 else
1900 token->word_char = IS_WORD_CHAR (token->opr.c);
1901
1902 switch (c)
1903 {
1904 case '\n':
1905 if (syntax & RE_NEWLINE_ALT)
1906 token->type = OP_ALT;
1907 break;
1908 case '|':
1909 if (!(syntax & RE_LIMITED_OPS) && (syntax & RE_NO_BK_VBAR))
1910 token->type = OP_ALT;
1911 break;
1912 case '*':
1913 token->type = OP_DUP_ASTERISK;
1914 break;
1915 case '+':
1916 if (!(syntax & RE_LIMITED_OPS) && !(syntax & RE_BK_PLUS_QM))
1917 token->type = OP_DUP_PLUS;
1918 break;
1919 case '?':
1920 if (!(syntax & RE_LIMITED_OPS) && !(syntax & RE_BK_PLUS_QM))
1921 token->type = OP_DUP_QUESTION;
1922 break;
1923 case '{':
1924 if ((syntax & RE_INTERVALS) && (syntax & RE_NO_BK_BRACES))
1925 token->type = OP_OPEN_DUP_NUM;
1926 break;
1927 case '}':
1928 if ((syntax & RE_INTERVALS) && (syntax & RE_NO_BK_BRACES))
1929 token->type = OP_CLOSE_DUP_NUM;
1930 break;
1931 case '(':
1932 if (syntax & RE_NO_BK_PARENS)
1933 token->type = OP_OPEN_SUBEXP;
1934 break;
1935 case ')':
1936 if (syntax & RE_NO_BK_PARENS)
1937 token->type = OP_CLOSE_SUBEXP;
1938 break;
1939 case '[':
1940 token->type = OP_OPEN_BRACKET;
1941 break;
1942 case '.':
1943 token->type = OP_PERIOD;
1944 break;
1945 case '^':
1946 if (!(syntax & (RE_CONTEXT_INDEP_ANCHORS | RE_CARET_ANCHORS_HERE))
1947 && re_string_cur_idx (input) != 0)
1948 {
1949 char prev = re_string_peek_byte (input, -1);
1950 if (!(syntax & RE_NEWLINE_ALT) || prev != '\n')
1951 break;
1952 }
1953 token->type = ANCHOR;
1954 token->opr.ctx_type = LINE_FIRST;
1955 break;
1956 case '$':
1957 if (!(syntax & RE_CONTEXT_INDEP_ANCHORS)
1958 && re_string_cur_idx (input) + 1 != re_string_length (input))
1959 {
1960 re_token_t next;
1961 re_string_skip_bytes (input, 1);
1962 peek_token (&next, input, syntax);
1963 re_string_skip_bytes (input, -1);
1964 if (next.type != OP_ALT && next.type != OP_CLOSE_SUBEXP)
1965 break;
1966 }
1967 token->type = ANCHOR;
1968 token->opr.ctx_type = LINE_LAST;
1969 break;
1970 default:
1971 break;
1972 }
1973 return 1;
1974 }
1975
1976 /* Peek a token from INPUT, and return the length of the token.
1977 We must not use this function out of bracket expressions. */
1978
1979 static int
1980 peek_token_bracket (re_token_t *token, re_string_t *input, reg_syntax_t syntax)
1981 {
1982 unsigned char c;
1983 if (re_string_eoi (input))
1984 {
1985 token->type = END_OF_RE;
1986 return 0;
1987 }
1988 c = re_string_peek_byte (input, 0);
1989 token->opr.c = c;
1990
1991 if (input->mb_cur_max > 1
1992 && !re_string_first_byte (input, re_string_cur_idx (input)))
1993 {
1994 token->type = CHARACTER;
1995 return 1;
1996 }
1997
1998 if (c == '\\' && (syntax & RE_BACKSLASH_ESCAPE_IN_LISTS)
1999 && re_string_cur_idx (input) + 1 < re_string_length (input))
2000 {
2001 /* In this case, '\' escape a character. */
2002 unsigned char c2;
2003 re_string_skip_bytes (input, 1);
2004 c2 = re_string_peek_byte (input, 0);
2005 token->opr.c = c2;
2006 token->type = CHARACTER;
2007 return 1;
2008 }
2009 if (c == '[') /* '[' is a special char in a bracket exps. */
2010 {
2011 unsigned char c2;
2012 int token_len;
2013 if (re_string_cur_idx (input) + 1 < re_string_length (input))
2014 c2 = re_string_peek_byte (input, 1);
2015 else
2016 c2 = 0;
2017 token->opr.c = c2;
2018 token_len = 2;
2019 switch (c2)
2020 {
2021 case '.':
2022 token->type = OP_OPEN_COLL_ELEM;
2023 break;
2024
2025 case '=':
2026 token->type = OP_OPEN_EQUIV_CLASS;
2027 break;
2028
2029 case ':':
2030 if (syntax & RE_CHAR_CLASSES)
2031 {
2032 token->type = OP_OPEN_CHAR_CLASS;
2033 break;
2034 }
2035 FALLTHROUGH;
2036 default:
2037 token->type = CHARACTER;
2038 token->opr.c = c;
2039 token_len = 1;
2040 break;
2041 }
2042 return token_len;
2043 }
2044 switch (c)
2045 {
2046 case ']':
2047 token->type = OP_CLOSE_BRACKET;
2048 break;
2049 case '^':
2050 token->type = OP_NON_MATCH_LIST;
2051 break;
2052 case '-':
2053 /* In V7 Unix grep and Unix awk and mawk, [...---...]
2054 (3 adjacent minus signs) stands for a single minus sign.
2055 Support that without breaking anything else. */
2056 if (! (re_string_cur_idx (input) + 2 < re_string_length (input)
2057 && re_string_peek_byte (input, 1) == '-'
2058 && re_string_peek_byte (input, 2) == '-'))
2059 {
2060 token->type = OP_CHARSET_RANGE;
2061 break;
2062 }
2063 re_string_skip_bytes (input, 2);
2064 FALLTHROUGH;
2065 default:
2066 token->type = CHARACTER;
2067 }
2068 return 1;
2069 }
2070
2071 /* Functions for parser. */
2072
2073 /* Entry point of the parser.
2074 Parse the regular expression REGEXP and return the structure tree.
2075 If an error occurs, ERR is set by error code, and return NULL.
2076 This function build the following tree, from regular expression <reg_exp>:
2077 CAT
2078 / \
2079 / \
2080 <reg_exp> EOR
2081
2082 CAT means concatenation.
2083 EOR means end of regular expression. */
2084
2085 static bin_tree_t *
2086 parse (re_string_t *regexp, regex_t *preg, reg_syntax_t syntax,
2087 reg_errcode_t *err)
2088 {
2089 re_dfa_t *dfa = preg->buffer;
2090 bin_tree_t *tree, *eor, *root;
2091 re_token_t current_token;
2092 dfa->syntax = syntax;
2093 fetch_token (&current_token, regexp, syntax | RE_CARET_ANCHORS_HERE);
2094 tree = parse_reg_exp (regexp, preg, &current_token, syntax, 0, err);
2095 if (__glibc_unlikely (*err != REG_NOERROR && tree == NULL))
2096 return NULL;
2097 eor = create_tree (dfa, NULL, NULL, END_OF_RE);
2098 if (tree != NULL)
2099 root = create_tree (dfa, tree, eor, CONCAT);
2100 else
2101 root = eor;
2102 if (__glibc_unlikely (eor == NULL || root == NULL))
2103 {
2104 *err = REG_ESPACE;
2105 return NULL;
2106 }
2107 return root;
2108 }
2109
2110 /* This function build the following tree, from regular expression
2111 <branch1>|<branch2>:
2112 ALT
2113 / \
2114 / \
2115 <branch1> <branch2>
2116
2117 ALT means alternative, which represents the operator '|'. */
2118
2119 static bin_tree_t *
2120 parse_reg_exp (re_string_t *regexp, regex_t *preg, re_token_t *token,
2121 reg_syntax_t syntax, Idx nest, reg_errcode_t *err)
2122 {
2123 re_dfa_t *dfa = preg->buffer;
2124 bin_tree_t *tree, *branch = NULL;
2125 bitset_word_t initial_bkref_map = dfa->completed_bkref_map;
2126 tree = parse_branch (regexp, preg, token, syntax, nest, err);
2127 if (__glibc_unlikely (*err != REG_NOERROR && tree == NULL))
2128 return NULL;
2129
2130 while (token->type == OP_ALT)
2131 {
2132 fetch_token (token, regexp, syntax | RE_CARET_ANCHORS_HERE);
2133 if (token->type != OP_ALT && token->type != END_OF_RE
2134 && (nest == 0 || token->type != OP_CLOSE_SUBEXP))
2135 {
2136 bitset_word_t accumulated_bkref_map = dfa->completed_bkref_map;
2137 dfa->completed_bkref_map = initial_bkref_map;
2138 branch = parse_branch (regexp, preg, token, syntax, nest, err);
2139 if (__glibc_unlikely (*err != REG_NOERROR && branch == NULL))
2140 {
2141 if (tree != NULL)
2142 postorder (tree, free_tree, NULL);
2143 return NULL;
2144 }
2145 dfa->completed_bkref_map |= accumulated_bkref_map;
2146 }
2147 else
2148 branch = NULL;
2149 tree = create_tree (dfa, tree, branch, OP_ALT);
2150 if (__glibc_unlikely (tree == NULL))
2151 {
2152 *err = REG_ESPACE;
2153 return NULL;
2154 }
2155 }
2156 return tree;
2157 }
2158
2159 /* This function build the following tree, from regular expression
2160 <exp1><exp2>:
2161 CAT
2162 / \
2163 / \
2164 <exp1> <exp2>
2165
2166 CAT means concatenation. */
2167
2168 static bin_tree_t *
2169 parse_branch (re_string_t *regexp, regex_t *preg, re_token_t *token,
2170 reg_syntax_t syntax, Idx nest, reg_errcode_t *err)
2171 {
2172 bin_tree_t *tree, *expr;
2173 re_dfa_t *dfa = preg->buffer;
2174 tree = parse_expression (regexp, preg, token, syntax, nest, err);
2175 if (__glibc_unlikely (*err != REG_NOERROR && tree == NULL))
2176 return NULL;
2177
2178 while (token->type != OP_ALT && token->type != END_OF_RE
2179 && (nest == 0 || token->type != OP_CLOSE_SUBEXP))
2180 {
2181 expr = parse_expression (regexp, preg, token, syntax, nest, err);
2182 if (__glibc_unlikely (*err != REG_NOERROR && expr == NULL))
2183 {
2184 if (tree != NULL)
2185 postorder (tree, free_tree, NULL);
2186 return NULL;
2187 }
2188 if (tree != NULL && expr != NULL)
2189 {
2190 bin_tree_t *newtree = create_tree (dfa, tree, expr, CONCAT);
2191 if (newtree == NULL)
2192 {
2193 postorder (expr, free_tree, NULL);
2194 postorder (tree, free_tree, NULL);
2195 *err = REG_ESPACE;
2196 return NULL;
2197 }
2198 tree = newtree;
2199 }
2200 else if (tree == NULL)
2201 tree = expr;
2202 /* Otherwise expr == NULL, we don't need to create new tree. */
2203 }
2204 return tree;
2205 }
2206
2207 /* This function build the following tree, from regular expression a*:
2208 *
2209 |
2210 a
2211 */
2212
2213 static bin_tree_t *
2214 parse_expression (re_string_t *regexp, regex_t *preg, re_token_t *token,
2215 reg_syntax_t syntax, Idx nest, reg_errcode_t *err)
2216 {
2217 re_dfa_t *dfa = preg->buffer;
2218 bin_tree_t *tree;
2219 switch (token->type)
2220 {
2221 case CHARACTER:
2222 tree = create_token_tree (dfa, NULL, NULL, token);
2223 if (__glibc_unlikely (tree == NULL))
2224 {
2225 *err = REG_ESPACE;
2226 return NULL;
2227 }
2228 if (dfa->mb_cur_max > 1)
2229 {
2230 while (!re_string_eoi (regexp)
2231 && !re_string_first_byte (regexp, re_string_cur_idx (regexp)))
2232 {
2233 bin_tree_t *mbc_remain;
2234 fetch_token (token, regexp, syntax);
2235 mbc_remain = create_token_tree (dfa, NULL, NULL, token);
2236 tree = create_tree (dfa, tree, mbc_remain, CONCAT);
2237 if (__glibc_unlikely (mbc_remain == NULL || tree == NULL))
2238 {
2239 *err = REG_ESPACE;
2240 return NULL;
2241 }
2242 }
2243 }
2244 break;
2245
2246 case OP_OPEN_SUBEXP:
2247 tree = parse_sub_exp (regexp, preg, token, syntax, nest + 1, err);
2248 if (__glibc_unlikely (*err != REG_NOERROR && tree == NULL))
2249 return NULL;
2250 break;
2251
2252 case OP_OPEN_BRACKET:
2253 tree = parse_bracket_exp (regexp, dfa, token, syntax, err);
2254 if (__glibc_unlikely (*err != REG_NOERROR && tree == NULL))
2255 return NULL;
2256 break;
2257
2258 case OP_BACK_REF:
2259 if (!__glibc_likely (dfa->completed_bkref_map & (1 << token->opr.idx)))
2260 {
2261 *err = REG_ESUBREG;
2262 return NULL;
2263 }
2264 dfa->used_bkref_map |= 1 << token->opr.idx;
2265 tree = create_token_tree (dfa, NULL, NULL, token);
2266 if (__glibc_unlikely (tree == NULL))
2267 {
2268 *err = REG_ESPACE;
2269 return NULL;
2270 }
2271 ++dfa->nbackref;
2272 dfa->has_mb_node = 1;
2273 break;
2274
2275 case OP_OPEN_DUP_NUM:
2276 if (syntax & RE_CONTEXT_INVALID_DUP)
2277 {
2278 *err = REG_BADRPT;
2279 return NULL;
2280 }
2281 FALLTHROUGH;
2282 case OP_DUP_ASTERISK:
2283 case OP_DUP_PLUS:
2284 case OP_DUP_QUESTION:
2285 if (syntax & RE_CONTEXT_INVALID_OPS)
2286 {
2287 *err = REG_BADRPT;
2288 return NULL;
2289 }
2290 else if (syntax & RE_CONTEXT_INDEP_OPS)
2291 {
2292 fetch_token (token, regexp, syntax);
2293 return parse_expression (regexp, preg, token, syntax, nest, err);
2294 }
2295 FALLTHROUGH;
2296 case OP_CLOSE_SUBEXP:
2297 if ((token->type == OP_CLOSE_SUBEXP)
2298 && !(syntax & RE_UNMATCHED_RIGHT_PAREN_ORD))
2299 {
2300 *err = REG_ERPAREN;
2301 return NULL;
2302 }
2303 FALLTHROUGH;
2304 case OP_CLOSE_DUP_NUM:
2305 /* We treat it as a normal character. */
2306
2307 /* Then we can these characters as normal characters. */
2308 token->type = CHARACTER;
2309 /* mb_partial and word_char bits should be initialized already
2310 by peek_token. */
2311 tree = create_token_tree (dfa, NULL, NULL, token);
2312 if (__glibc_unlikely (tree == NULL))
2313 {
2314 *err = REG_ESPACE;
2315 return NULL;
2316 }
2317 break;
2318
2319 case ANCHOR:
2320 if ((token->opr.ctx_type
2321 & (WORD_DELIM | NOT_WORD_DELIM | WORD_FIRST | WORD_LAST))
2322 && dfa->word_ops_used == 0)
2323 init_word_char (dfa);
2324 if (token->opr.ctx_type == WORD_DELIM
2325 || token->opr.ctx_type == NOT_WORD_DELIM)
2326 {
2327 bin_tree_t *tree_first, *tree_last;
2328 if (token->opr.ctx_type == WORD_DELIM)
2329 {
2330 token->opr.ctx_type = WORD_FIRST;
2331 tree_first = create_token_tree (dfa, NULL, NULL, token);
2332 token->opr.ctx_type = WORD_LAST;
2333 }
2334 else
2335 {
2336 token->opr.ctx_type = INSIDE_WORD;
2337 tree_first = create_token_tree (dfa, NULL, NULL, token);
2338 token->opr.ctx_type = INSIDE_NOTWORD;
2339 }
2340 tree_last = create_token_tree (dfa, NULL, NULL, token);
2341 tree = create_tree (dfa, tree_first, tree_last, OP_ALT);
2342 if (__glibc_unlikely (tree_first == NULL || tree_last == NULL
2343 || tree == NULL))
2344 {
2345 *err = REG_ESPACE;
2346 return NULL;
2347 }
2348 }
2349 else
2350 {
2351 tree = create_token_tree (dfa, NULL, NULL, token);
2352 if (__glibc_unlikely (tree == NULL))
2353 {
2354 *err = REG_ESPACE;
2355 return NULL;
2356 }
2357 }
2358 /* We must return here, since ANCHORs can't be followed
2359 by repetition operators.
2360 eg. RE"^*" is invalid or "<ANCHOR(^)><CHAR(*)>",
2361 it must not be "<ANCHOR(^)><REPEAT(*)>". */
2362 fetch_token (token, regexp, syntax);
2363 return tree;
2364
2365 case OP_PERIOD:
2366 tree = create_token_tree (dfa, NULL, NULL, token);
2367 if (__glibc_unlikely (tree == NULL))
2368 {
2369 *err = REG_ESPACE;
2370 return NULL;
2371 }
2372 if (dfa->mb_cur_max > 1)
2373 dfa->has_mb_node = 1;
2374 break;
2375
2376 case OP_WORD:
2377 case OP_NOTWORD:
2378 tree = build_charclass_op (dfa, regexp->trans,
2379 "alnum",
2380 "_",
2381 token->type == OP_NOTWORD, err);
2382 if (__glibc_unlikely (*err != REG_NOERROR && tree == NULL))
2383 return NULL;
2384 break;
2385
2386 case OP_SPACE:
2387 case OP_NOTSPACE:
2388 tree = build_charclass_op (dfa, regexp->trans,
2389 "space",
2390 "",
2391 token->type == OP_NOTSPACE, err);
2392 if (__glibc_unlikely (*err != REG_NOERROR && tree == NULL))
2393 return NULL;
2394 break;
2395
2396 case OP_ALT:
2397 case END_OF_RE:
2398 return NULL;
2399
2400 case BACK_SLASH:
2401 *err = REG_EESCAPE;
2402 return NULL;
2403
2404 default:
2405 /* Must not happen? */
2406 DEBUG_ASSERT (false);
2407 return NULL;
2408 }
2409 fetch_token (token, regexp, syntax);
2410
2411 while (token->type == OP_DUP_ASTERISK || token->type == OP_DUP_PLUS
2412 || token->type == OP_DUP_QUESTION || token->type == OP_OPEN_DUP_NUM)
2413 {
2414 bin_tree_t *dup_tree = parse_dup_op (tree, regexp, dfa, token,
2415 syntax, err);
2416 if (__glibc_unlikely (*err != REG_NOERROR && dup_tree == NULL))
2417 {
2418 if (tree != NULL)
2419 postorder (tree, free_tree, NULL);
2420 return NULL;
2421 }
2422 tree = dup_tree;
2423 /* In BRE consecutive duplications are not allowed. */
2424 if ((syntax & RE_CONTEXT_INVALID_DUP)
2425 && (token->type == OP_DUP_ASTERISK
2426 || token->type == OP_OPEN_DUP_NUM))
2427 {
2428 if (tree != NULL)
2429 postorder (tree, free_tree, NULL);
2430 *err = REG_BADRPT;
2431 return NULL;
2432 }
2433 }
2434
2435 return tree;
2436 }
2437
2438 /* This function build the following tree, from regular expression
2439 (<reg_exp>):
2440 SUBEXP
2441 |
2442 <reg_exp>
2443 */
2444
2445 static bin_tree_t *
2446 parse_sub_exp (re_string_t *regexp, regex_t *preg, re_token_t *token,
2447 reg_syntax_t syntax, Idx nest, reg_errcode_t *err)
2448 {
2449 re_dfa_t *dfa = preg->buffer;
2450 bin_tree_t *tree;
2451 size_t cur_nsub;
2452 cur_nsub = preg->re_nsub++;
2453
2454 fetch_token (token, regexp, syntax | RE_CARET_ANCHORS_HERE);
2455
2456 /* The subexpression may be a null string. */
2457 if (token->type == OP_CLOSE_SUBEXP)
2458 tree = NULL;
2459 else
2460 {
2461 tree = parse_reg_exp (regexp, preg, token, syntax, nest, err);
2462 if (__glibc_unlikely (*err == REG_NOERROR
2463 && token->type != OP_CLOSE_SUBEXP))
2464 {
2465 if (tree != NULL)
2466 postorder (tree, free_tree, NULL);
2467 *err = REG_EPAREN;
2468 }
2469 if (__glibc_unlikely (*err != REG_NOERROR))
2470 return NULL;
2471 }
2472
2473 if (cur_nsub <= '9' - '1')
2474 dfa->completed_bkref_map |= 1 << cur_nsub;
2475
2476 tree = create_tree (dfa, tree, NULL, SUBEXP);
2477 if (__glibc_unlikely (tree == NULL))
2478 {
2479 *err = REG_ESPACE;
2480 return NULL;
2481 }
2482 tree->token.opr.idx = cur_nsub;
2483 return tree;
2484 }
2485
2486 /* This function parse repetition operators like "*", "+", "{1,3}" etc. */
2487
2488 static bin_tree_t *
2489 parse_dup_op (bin_tree_t *elem, re_string_t *regexp, re_dfa_t *dfa,
2490 re_token_t *token, reg_syntax_t syntax, reg_errcode_t *err)
2491 {
2492 bin_tree_t *tree = NULL, *old_tree = NULL;
2493 Idx i, start, end, start_idx = re_string_cur_idx (regexp);
2494 re_token_t start_token = *token;
2495
2496 if (token->type == OP_OPEN_DUP_NUM)
2497 {
2498 end = 0;
2499 start = fetch_number (regexp, token, syntax);
2500 if (start == -1)
2501 {
2502 if (token->type == CHARACTER && token->opr.c == ',')
2503 start = 0; /* We treat "{,m}" as "{0,m}". */
2504 else
2505 {
2506 *err = REG_BADBR; /* <re>{} is invalid. */
2507 return NULL;
2508 }
2509 }
2510 if (__glibc_likely (start != -2))
2511 {
2512 /* We treat "{n}" as "{n,n}". */
2513 end = ((token->type == OP_CLOSE_DUP_NUM) ? start
2514 : ((token->type == CHARACTER && token->opr.c == ',')
2515 ? fetch_number (regexp, token, syntax) : -2));
2516 }
2517 if (__glibc_unlikely (start == -2 || end == -2))
2518 {
2519 /* Invalid sequence. */
2520 if (__glibc_unlikely (!(syntax & RE_INVALID_INTERVAL_ORD)))
2521 {
2522 if (token->type == END_OF_RE)
2523 *err = REG_EBRACE;
2524 else
2525 *err = REG_BADBR;
2526
2527 return NULL;
2528 }
2529
2530 /* If the syntax bit is set, rollback. */
2531 re_string_set_index (regexp, start_idx);
2532 *token = start_token;
2533 token->type = CHARACTER;
2534 /* mb_partial and word_char bits should be already initialized by
2535 peek_token. */
2536 return elem;
2537 }
2538
2539 if (__glibc_unlikely ((end != -1 && start > end)
2540 || token->type != OP_CLOSE_DUP_NUM))
2541 {
2542 /* First number greater than second. */
2543 *err = REG_BADBR;
2544 return NULL;
2545 }
2546
2547 if (__glibc_unlikely (RE_DUP_MAX < (end == -1 ? start : end)))
2548 {
2549 *err = REG_ESIZE;
2550 return NULL;
2551 }
2552 }
2553 else
2554 {
2555 start = (token->type == OP_DUP_PLUS) ? 1 : 0;
2556 end = (token->type == OP_DUP_QUESTION) ? 1 : -1;
2557 }
2558
2559 fetch_token (token, regexp, syntax);
2560
2561 if (__glibc_unlikely (elem == NULL))
2562 return NULL;
2563 if (__glibc_unlikely (start == 0 && end == 0))
2564 {
2565 postorder (elem, free_tree, NULL);
2566 return NULL;
2567 }
2568
2569 /* Extract "<re>{n,m}" to "<re><re>...<re><re>{0,<m-n>}". */
2570 if (__glibc_unlikely (start > 0))
2571 {
2572 tree = elem;
2573 for (i = 2; i <= start; ++i)
2574 {
2575 elem = duplicate_tree (elem, dfa);
2576 tree = create_tree (dfa, tree, elem, CONCAT);
2577 if (__glibc_unlikely (elem == NULL || tree == NULL))
2578 goto parse_dup_op_espace;
2579 }
2580
2581 if (start == end)
2582 return tree;
2583
2584 /* Duplicate ELEM before it is marked optional. */
2585 elem = duplicate_tree (elem, dfa);
2586 if (__glibc_unlikely (elem == NULL))
2587 goto parse_dup_op_espace;
2588 old_tree = tree;
2589 }
2590 else
2591 old_tree = NULL;
2592
2593 if (elem->token.type == SUBEXP)
2594 {
2595 uintptr_t subidx = elem->token.opr.idx;
2596 postorder (elem, mark_opt_subexp, (void *) subidx);
2597 }
2598
2599 tree = create_tree (dfa, elem, NULL,
2600 (end == -1 ? OP_DUP_ASTERISK : OP_ALT));
2601 if (__glibc_unlikely (tree == NULL))
2602 goto parse_dup_op_espace;
2603
2604 /* This loop is actually executed only when end != -1,
2605 to rewrite <re>{0,n} as (<re>(<re>...<re>?)?)?... We have
2606 already created the start+1-th copy. */
2607 if (TYPE_SIGNED (Idx) || end != -1)
2608 for (i = start + 2; i <= end; ++i)
2609 {
2610 elem = duplicate_tree (elem, dfa);
2611 tree = create_tree (dfa, tree, elem, CONCAT);
2612 if (__glibc_unlikely (elem == NULL || tree == NULL))
2613 goto parse_dup_op_espace;
2614
2615 tree = create_tree (dfa, tree, NULL, OP_ALT);
2616 if (__glibc_unlikely (tree == NULL))
2617 goto parse_dup_op_espace;
2618 }
2619
2620 if (old_tree)
2621 tree = create_tree (dfa, old_tree, tree, CONCAT);
2622
2623 return tree;
2624
2625 parse_dup_op_espace:
2626 *err = REG_ESPACE;
2627 return NULL;
2628 }
2629
2630 /* Size of the names for collating symbol/equivalence_class/character_class.
2631 I'm not sure, but maybe enough. */
2632 #define BRACKET_NAME_BUF_SIZE 32
2633
2634 #ifndef _LIBC
2635
2636 /* Convert the byte B to the corresponding wide character. In a
2637 unibyte locale, treat B as itself. In a multibyte locale, return
2638 WEOF if B is an encoding error. */
2639 static wint_t
2640 parse_byte (unsigned char b, re_dfa_t const *dfa)
2641 {
2642 return dfa->mb_cur_max > 1 ? __btowc (b) : b;
2643 }
2644
2645 /* Local function for parse_bracket_exp used in _LIBC environment.
2646 Build the range expression which starts from START_ELEM, and ends
2647 at END_ELEM. The result are written to MBCSET and SBCSET.
2648 RANGE_ALLOC is the allocated size of mbcset->range_starts, and
2649 mbcset->range_ends, is a pointer argument since we may
2650 update it. */
2651
2652 static reg_errcode_t
2653 build_range_exp (bitset_t sbcset, re_charset_t *mbcset, Idx *range_alloc,
2654 bracket_elem_t *start_elem, bracket_elem_t *end_elem,
2655 re_dfa_t *dfa, reg_syntax_t syntax, uint_fast32_t nrules,
2656 const unsigned char *collseqmb, const char *collseqwc,
2657 int_fast32_t table_size, const void *symb_table,
2658 const unsigned char *extra)
2659 {
2660 /* Equivalence Classes and Character Classes can't be a range start/end. */
2661 if (__glibc_unlikely (start_elem->type == EQUIV_CLASS
2662 || start_elem->type == CHAR_CLASS
2663 || end_elem->type == EQUIV_CLASS
2664 || end_elem->type == CHAR_CLASS))
2665 return REG_ERANGE;
2666
2667 /* We can handle no multi character collating elements without libc
2668 support. */
2669 if (__glibc_unlikely ((start_elem->type == COLL_SYM
2670 && strlen ((char *) start_elem->opr.name) > 1)
2671 || (end_elem->type == COLL_SYM
2672 && strlen ((char *) end_elem->opr.name) > 1)))
2673 return REG_ECOLLATE;
2674
2675 unsigned int
2676 start_ch = ((start_elem->type == SB_CHAR) ? start_elem->opr.ch
2677 : ((start_elem->type == COLL_SYM) ? start_elem->opr.name[0]
2678 : 0)),
2679 end_ch = ((end_elem->type == SB_CHAR) ? end_elem->opr.ch
2680 : ((end_elem->type == COLL_SYM) ? end_elem->opr.name[0]
2681 : 0));
2682 wint_t
2683 start_wc = ((start_elem->type == SB_CHAR || start_elem->type == COLL_SYM)
2684 ? parse_byte (start_ch, dfa) : start_elem->opr.wch),
2685 end_wc = ((end_elem->type == SB_CHAR || end_elem->type == COLL_SYM)
2686 ? parse_byte (end_ch, dfa) : end_elem->opr.wch);
2687
2688 if (start_wc == WEOF || end_wc == WEOF)
2689 return REG_ECOLLATE;
2690 else if (__glibc_unlikely ((syntax & RE_NO_EMPTY_RANGES)
2691 && start_wc > end_wc))
2692 return REG_ERANGE;
2693
2694 /* Got valid collation sequence values, add them as a new entry.
2695 However, for !_LIBC we have no collation elements: if the
2696 character set is single byte, the single byte character set
2697 that we build below suffices. parse_bracket_exp passes
2698 no MBCSET if dfa->mb_cur_max == 1. */
2699 if (dfa->mb_cur_max > 1)
2700 {
2701 /* Check the space of the arrays. */
2702 if (__glibc_unlikely (*range_alloc == mbcset->nranges))
2703 {
2704 /* There is not enough space, need realloc. */
2705 wchar_t *new_array_start, *new_array_end;
2706 Idx new_nranges;
2707
2708 /* +1 in case of mbcset->nranges is 0. */
2709 new_nranges = 2 * mbcset->nranges + 1;
2710 /* Use realloc since mbcset->range_starts and mbcset->range_ends
2711 are NULL if *range_alloc == 0. */
2712 new_array_start = re_realloc (mbcset->range_starts, wchar_t,
2713 new_nranges);
2714 new_array_end = re_realloc (mbcset->range_ends, wchar_t,
2715 new_nranges);
2716
2717 if (__glibc_unlikely (new_array_start == NULL
2718 || new_array_end == NULL))
2719 {
2720 re_free (new_array_start);
2721 re_free (new_array_end);
2722 return REG_ESPACE;
2723 }
2724
2725 mbcset->range_starts = new_array_start;
2726 mbcset->range_ends = new_array_end;
2727 *range_alloc = new_nranges;
2728 }
2729
2730 mbcset->range_starts[mbcset->nranges] = start_wc;
2731 mbcset->range_ends[mbcset->nranges++] = end_wc;
2732 }
2733
2734 /* Build the table for single byte characters. */
2735 for (wchar_t wc = 0; wc < SBC_MAX; ++wc)
2736 {
2737 if (start_wc <= wc && wc <= end_wc)
2738 bitset_set (sbcset, wc);
2739 }
2740
2741 return REG_NOERROR;
2742 }
2743 #endif /* not _LIBC */
2744
2745 #ifndef _LIBC
2746 /* Helper function for parse_bracket_exp only used in case of NOT _LIBC.
2747 Build the collating element which is represented by NAME.
2748 The result are written to MBCSET and SBCSET.
2749 COLL_SYM_ALLOC is the allocated size of mbcset->coll_sym, is a
2750 pointer argument since we may update it. */
2751
2752 static reg_errcode_t
2753 build_collating_symbol (bitset_t sbcset, re_charset_t *mbcset,
2754 Idx *coll_sym_alloc, const unsigned char *name,
2755 uint_fast32_t nrules, int_fast32_t table_size,
2756 const void *symb_table, const unsigned char *extra)
2757 {
2758 size_t name_len = strlen ((const char *) name);
2759 if (__glibc_unlikely (name_len != 1))
2760 return REG_ECOLLATE;
2761 else
2762 {
2763 bitset_set (sbcset, name[0]);
2764 return REG_NOERROR;
2765 }
2766 }
2767 #endif /* not _LIBC */
2768
2769 #ifdef _LIBC
2770 /* Local function for parse_bracket_exp used in _LIBC environment.
2771 Seek the collating symbol entry corresponding to NAME.
2772 Return the index of the symbol in the SYMB_TABLE,
2773 or -1 if not found. */
2774
2775 static __always_inline int32_t
2776 seek_collating_symbol_entry (const unsigned char *name, size_t name_len,
2777 const int32_t *symb_table,
2778 int_fast32_t table_size,
2779 const unsigned char *extra)
2780 {
2781 int_fast32_t elem;
2782
2783 for (elem = 0; elem < table_size; elem++)
2784 if (symb_table[2 * elem] != 0)
2785 {
2786 int32_t idx = symb_table[2 * elem + 1];
2787 /* Skip the name of collating element name. */
2788 idx += 1 + extra[idx];
2789 if (/* Compare the length of the name. */
2790 name_len == extra[idx]
2791 /* Compare the name. */
2792 && memcmp (name, &extra[idx + 1], name_len) == 0)
2793 /* Yep, this is the entry. */
2794 return elem;
2795 }
2796 return -1;
2797 }
2798
2799 /* Local function for parse_bracket_exp used in _LIBC environment.
2800 Look up the collation sequence value of BR_ELEM.
2801 Return the value if succeeded, UINT_MAX otherwise. */
2802
2803 static __always_inline unsigned int
2804 lookup_collation_sequence_value (bracket_elem_t *br_elem, uint32_t nrules,
2805 const unsigned char *collseqmb,
2806 const char *collseqwc,
2807 int_fast32_t table_size,
2808 const int32_t *symb_table,
2809 const unsigned char *extra)
2810 {
2811 if (br_elem->type == SB_CHAR)
2812 {
2813 /* if (MB_CUR_MAX == 1) */
2814 if (nrules == 0)
2815 return collseqmb[br_elem->opr.ch];
2816 else
2817 {
2818 wint_t wc = __btowc (br_elem->opr.ch);
2819 return __collseq_table_lookup (collseqwc, wc);
2820 }
2821 }
2822 else if (br_elem->type == MB_CHAR)
2823 {
2824 if (nrules != 0)
2825 return __collseq_table_lookup (collseqwc, br_elem->opr.wch);
2826 }
2827 else if (br_elem->type == COLL_SYM)
2828 {
2829 size_t sym_name_len = strlen ((char *) br_elem->opr.name);
2830 if (nrules != 0)
2831 {
2832 int32_t elem, idx;
2833 elem = seek_collating_symbol_entry (br_elem->opr.name,
2834 sym_name_len,
2835 symb_table, table_size,
2836 extra);
2837 if (elem != -1)
2838 {
2839 /* We found the entry. */
2840 idx = symb_table[2 * elem + 1];
2841 /* Skip the name of collating element name. */
2842 idx += 1 + extra[idx];
2843 /* Skip the byte sequence of the collating element. */
2844 idx += 1 + extra[idx];
2845 /* Adjust for the alignment. */
2846 idx = (idx + 3) & ~3;
2847 /* Skip the multibyte collation sequence value. */
2848 idx += sizeof (unsigned int);
2849 /* Skip the wide char sequence of the collating element. */
2850 idx += sizeof (unsigned int) *
2851 (1 + *(unsigned int *) (extra + idx));
2852 /* Return the collation sequence value. */
2853 return *(unsigned int *) (extra + idx);
2854 }
2855 else if (sym_name_len == 1)
2856 {
2857 /* No valid character. Match it as a single byte
2858 character. */
2859 return collseqmb[br_elem->opr.name[0]];
2860 }
2861 }
2862 else if (sym_name_len == 1)
2863 return collseqmb[br_elem->opr.name[0]];
2864 }
2865 return UINT_MAX;
2866 }
2867
2868 /* Local function for parse_bracket_exp used in _LIBC environment.
2869 Build the range expression which starts from START_ELEM, and ends
2870 at END_ELEM. The result are written to MBCSET and SBCSET.
2871 RANGE_ALLOC is the allocated size of mbcset->range_starts, and
2872 mbcset->range_ends, is a pointer argument since we may
2873 update it. */
2874
2875 static __always_inline reg_errcode_t
2876 build_range_exp (bitset_t sbcset, re_charset_t *mbcset, Idx *range_alloc,
2877 bracket_elem_t *start_elem, bracket_elem_t *end_elem,
2878 re_dfa_t *dfa, reg_syntax_t syntax, uint32_t nrules,
2879 const unsigned char *collseqmb, const char *collseqwc,
2880 int_fast32_t table_size, const int32_t *symb_table,
2881 const unsigned char *extra)
2882 {
2883 unsigned int ch;
2884 uint32_t start_collseq;
2885 uint32_t end_collseq;
2886
2887 /* Equivalence Classes and Character Classes can't be a range
2888 start/end. */
2889 if (__glibc_unlikely (start_elem->type == EQUIV_CLASS
2890 || start_elem->type == CHAR_CLASS
2891 || end_elem->type == EQUIV_CLASS
2892 || end_elem->type == CHAR_CLASS))
2893 return REG_ERANGE;
2894
2895 /* FIXME: Implement rational ranges here, too. */
2896 start_collseq = lookup_collation_sequence_value (start_elem, nrules, collseqmb, collseqwc,
2897 table_size, symb_table, extra);
2898 end_collseq = lookup_collation_sequence_value (end_elem, nrules, collseqmb, collseqwc,
2899 table_size, symb_table, extra);
2900 /* Check start/end collation sequence values. */
2901 if (__glibc_unlikely (start_collseq == UINT_MAX
2902 || end_collseq == UINT_MAX))
2903 return REG_ECOLLATE;
2904 if (__glibc_unlikely ((syntax & RE_NO_EMPTY_RANGES)
2905 && start_collseq > end_collseq))
2906 return REG_ERANGE;
2907
2908 /* Got valid collation sequence values, add them as a new entry.
2909 However, if we have no collation elements, and the character set
2910 is single byte, the single byte character set that we
2911 build below suffices. */
2912 if (nrules > 0 || dfa->mb_cur_max > 1)
2913 {
2914 /* Check the space of the arrays. */
2915 if (__glibc_unlikely (*range_alloc == mbcset->nranges))
2916 {
2917 /* There is not enough space, need realloc. */
2918 uint32_t *new_array_start;
2919 uint32_t *new_array_end;
2920 int new_nranges;
2921
2922 /* +1 in case of mbcset->nranges is 0. */
2923 new_nranges = 2 * mbcset->nranges + 1;
2924 new_array_start = re_realloc (mbcset->range_starts, uint32_t,
2925 new_nranges);
2926 new_array_end = re_realloc (mbcset->range_ends, uint32_t,
2927 new_nranges);
2928
2929 if (__glibc_unlikely (new_array_start == NULL
2930 || new_array_end == NULL))
2931 return REG_ESPACE;
2932
2933 mbcset->range_starts = new_array_start;
2934 mbcset->range_ends = new_array_end;
2935 *range_alloc = new_nranges;
2936 }
2937
2938 mbcset->range_starts[mbcset->nranges] = start_collseq;
2939 mbcset->range_ends[mbcset->nranges++] = end_collseq;
2940 }
2941
2942 /* Build the table for single byte characters. */
2943 for (ch = 0; ch < SBC_MAX; ch++)
2944 {
2945 uint32_t ch_collseq;
2946 /* if (MB_CUR_MAX == 1) */
2947 if (nrules == 0)
2948 ch_collseq = collseqmb[ch];
2949 else
2950 ch_collseq = __collseq_table_lookup (collseqwc, __btowc (ch));
2951 if (start_collseq <= ch_collseq && ch_collseq <= end_collseq)
2952 bitset_set (sbcset, ch);
2953 }
2954 return REG_NOERROR;
2955 }
2956
2957 /* Local function for parse_bracket_exp used in _LIBC environment.
2958 Build the collating element which is represented by NAME.
2959 The result are written to MBCSET and SBCSET.
2960 COLL_SYM_ALLOC is the allocated size of mbcset->coll_sym, is a
2961 pointer argument since we may update it. */
2962
2963 static __always_inline reg_errcode_t
2964 build_collating_symbol (bitset_t sbcset, re_charset_t *mbcset,
2965 Idx *coll_sym_alloc, const unsigned char *name,
2966 uint_fast32_t nrules, int_fast32_t table_size,
2967 const int32_t *symb_table, const unsigned char *extra)
2968 {
2969 int32_t elem, idx;
2970 size_t name_len = strlen ((const char *) name);
2971 if (nrules != 0)
2972 {
2973 elem = seek_collating_symbol_entry (name, name_len, symb_table,
2974 table_size, extra);
2975 if (elem != -1)
2976 {
2977 /* We found the entry. */
2978 idx = symb_table[2 * elem + 1];
2979 /* Skip the name of collating element name. */
2980 idx += 1 + extra[idx];
2981 }
2982 else if (name_len == 1)
2983 {
2984 /* No valid character, treat it as a normal
2985 character. */
2986 bitset_set (sbcset, name[0]);
2987 return REG_NOERROR;
2988 }
2989 else
2990 return REG_ECOLLATE;
2991
2992 /* Got valid collation sequence, add it as a new entry. */
2993 /* Check the space of the arrays. */
2994 if (__glibc_unlikely (*coll_sym_alloc == mbcset->ncoll_syms))
2995 {
2996 /* Not enough, realloc it. */
2997 /* +1 in case of mbcset->ncoll_syms is 0. */
2998 int new_coll_sym_alloc = 2 * mbcset->ncoll_syms + 1;
2999 /* Use realloc since mbcset->coll_syms is NULL
3000 if *alloc == 0. */
3001 int32_t *new_coll_syms = re_realloc (mbcset->coll_syms, int32_t,
3002 new_coll_sym_alloc);
3003 if (__glibc_unlikely (new_coll_syms == NULL))
3004 return REG_ESPACE;
3005 mbcset->coll_syms = new_coll_syms;
3006 *coll_sym_alloc = new_coll_sym_alloc;
3007 }
3008 mbcset->coll_syms[mbcset->ncoll_syms++] = idx;
3009 return REG_NOERROR;
3010 }
3011 else
3012 {
3013 if (__glibc_unlikely (name_len != 1))
3014 return REG_ECOLLATE;
3015 else
3016 {
3017 bitset_set (sbcset, name[0]);
3018 return REG_NOERROR;
3019 }
3020 }
3021 }
3022 #endif /* _LIBC */
3023
3024 /* This function parse bracket expression like "[abc]", "[a-c]",
3025 "[[.a-a.]]" etc. */
3026
3027 static bin_tree_t *
3028 parse_bracket_exp (re_string_t *regexp, re_dfa_t *dfa, re_token_t *token,
3029 reg_syntax_t syntax, reg_errcode_t *err)
3030 {
3031 const unsigned char *collseqmb = NULL;
3032 const char *collseqwc = NULL;
3033 uint_fast32_t nrules = 0;
3034 int_fast32_t table_size = 0;
3035 const void *symb_table = NULL;
3036 const unsigned char *extra = NULL;
3037
3038 re_token_t br_token;
3039 re_bitset_ptr_t sbcset;
3040 re_charset_t *mbcset;
3041 Idx coll_sym_alloc = 0, range_alloc = 0, mbchar_alloc = 0;
3042 Idx equiv_class_alloc = 0, char_class_alloc = 0;
3043 bool non_match = false;
3044 bin_tree_t *work_tree;
3045 int token_len;
3046 bool first_round = true;
3047 #ifdef _LIBC
3048 collseqmb = (const unsigned char *)
3049 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQMB);
3050 nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
3051 if (nrules)
3052 {
3053 /*
3054 if (MB_CUR_MAX > 1)
3055 */
3056 collseqwc = _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQWC);
3057 table_size = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_SYMB_HASH_SIZEMB);
3058 symb_table = _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_TABLEMB);
3059 extra = (const unsigned char *) _NL_CURRENT (LC_COLLATE,
3060 _NL_COLLATE_SYMB_EXTRAMB);
3061 }
3062 #endif
3063 sbcset = (re_bitset_ptr_t) calloc (1, sizeof (bitset_t));
3064 mbcset = (re_charset_t *) calloc (1, sizeof (re_charset_t));
3065 if (__glibc_unlikely (sbcset == NULL || mbcset == NULL))
3066 {
3067 re_free (sbcset);
3068 re_free (mbcset);
3069 *err = REG_ESPACE;
3070 return NULL;
3071 }
3072
3073 token_len = peek_token_bracket (token, regexp, syntax);
3074 if (__glibc_unlikely (token->type == END_OF_RE))
3075 {
3076 *err = REG_BADPAT;
3077 goto parse_bracket_exp_free_return;
3078 }
3079 if (token->type == OP_NON_MATCH_LIST)
3080 {
3081 mbcset->non_match = 1;
3082 non_match = true;
3083 if (syntax & RE_HAT_LISTS_NOT_NEWLINE)
3084 bitset_set (sbcset, '\n');
3085 re_string_skip_bytes (regexp, token_len); /* Skip a token. */
3086 token_len = peek_token_bracket (token, regexp, syntax);
3087 if (__glibc_unlikely (token->type == END_OF_RE))
3088 {
3089 *err = REG_BADPAT;
3090 goto parse_bracket_exp_free_return;
3091 }
3092 }
3093
3094 /* We treat the first ']' as a normal character. */
3095 if (token->type == OP_CLOSE_BRACKET)
3096 token->type = CHARACTER;
3097
3098 while (1)
3099 {
3100 bracket_elem_t start_elem, end_elem;
3101 unsigned char start_name_buf[BRACKET_NAME_BUF_SIZE];
3102 unsigned char end_name_buf[BRACKET_NAME_BUF_SIZE];
3103 reg_errcode_t ret;
3104 int token_len2 = 0;
3105 bool is_range_exp = false;
3106 re_token_t token2;
3107
3108 start_elem.opr.name = start_name_buf;
3109 start_elem.type = COLL_SYM;
3110 ret = parse_bracket_element (&start_elem, regexp, token, token_len, dfa,
3111 syntax, first_round);
3112 if (__glibc_unlikely (ret != REG_NOERROR))
3113 {
3114 *err = ret;
3115 goto parse_bracket_exp_free_return;
3116 }
3117 first_round = false;
3118
3119 /* Get information about the next token. We need it in any case. */
3120 token_len = peek_token_bracket (token, regexp, syntax);
3121
3122 /* Do not check for ranges if we know they are not allowed. */
3123 if (start_elem.type != CHAR_CLASS && start_elem.type != EQUIV_CLASS)
3124 {
3125 if (__glibc_unlikely (token->type == END_OF_RE))
3126 {
3127 *err = REG_EBRACK;
3128 goto parse_bracket_exp_free_return;
3129 }
3130 if (token->type == OP_CHARSET_RANGE)
3131 {
3132 re_string_skip_bytes (regexp, token_len); /* Skip '-'. */
3133 token_len2 = peek_token_bracket (&token2, regexp, syntax);
3134 if (__glibc_unlikely (token2.type == END_OF_RE))
3135 {
3136 *err = REG_EBRACK;
3137 goto parse_bracket_exp_free_return;
3138 }
3139 if (token2.type == OP_CLOSE_BRACKET)
3140 {
3141 /* We treat the last '-' as a normal character. */
3142 re_string_skip_bytes (regexp, -token_len);
3143 token->type = CHARACTER;
3144 }
3145 else
3146 is_range_exp = true;
3147 }
3148 }
3149
3150 if (is_range_exp == true)
3151 {
3152 end_elem.opr.name = end_name_buf;
3153 end_elem.type = COLL_SYM;
3154 ret = parse_bracket_element (&end_elem, regexp, &token2, token_len2,
3155 dfa, syntax, true);
3156 if (__glibc_unlikely (ret != REG_NOERROR))
3157 {
3158 *err = ret;
3159 goto parse_bracket_exp_free_return;
3160 }
3161
3162 token_len = peek_token_bracket (token, regexp, syntax);
3163
3164 *err = build_range_exp (sbcset, mbcset, &range_alloc,
3165 &start_elem, &end_elem,
3166 dfa, syntax, nrules, collseqmb, collseqwc,
3167 table_size, symb_table, extra);
3168 if (__glibc_unlikely (*err != REG_NOERROR))
3169 goto parse_bracket_exp_free_return;
3170 }
3171 else
3172 {
3173 switch (start_elem.type)
3174 {
3175 case SB_CHAR:
3176 bitset_set (sbcset, start_elem.opr.ch);
3177 break;
3178 case MB_CHAR:
3179 /* Check whether the array has enough space. */
3180 if (__glibc_unlikely (mbchar_alloc == mbcset->nmbchars))
3181 {
3182 wchar_t *new_mbchars;
3183 /* Not enough, realloc it. */
3184 /* +1 in case of mbcset->nmbchars is 0. */
3185 mbchar_alloc = 2 * mbcset->nmbchars + 1;
3186 /* Use realloc since array is NULL if *alloc == 0. */
3187 new_mbchars = re_realloc (mbcset->mbchars, wchar_t,
3188 mbchar_alloc);
3189 if (__glibc_unlikely (new_mbchars == NULL))
3190 goto parse_bracket_exp_espace;
3191 mbcset->mbchars = new_mbchars;
3192 }
3193 mbcset->mbchars[mbcset->nmbchars++] = start_elem.opr.wch;
3194 break;
3195 case EQUIV_CLASS:
3196 *err = build_equiv_class (sbcset,
3197 mbcset, &equiv_class_alloc,
3198 start_elem.opr.name);
3199 if (__glibc_unlikely (*err != REG_NOERROR))
3200 goto parse_bracket_exp_free_return;
3201 break;
3202 case COLL_SYM:
3203 *err = build_collating_symbol (sbcset,
3204 mbcset, &coll_sym_alloc,
3205 start_elem.opr.name,
3206 nrules, table_size, symb_table, extra);
3207 if (__glibc_unlikely (*err != REG_NOERROR))
3208 goto parse_bracket_exp_free_return;
3209 break;
3210 case CHAR_CLASS:
3211 *err = build_charclass (regexp->trans, sbcset,
3212 mbcset, &char_class_alloc,
3213 (const char *) start_elem.opr.name,
3214 syntax);
3215 if (__glibc_unlikely (*err != REG_NOERROR))
3216 goto parse_bracket_exp_free_return;
3217 break;
3218 default:
3219 DEBUG_ASSERT (false);
3220 break;
3221 }
3222 }
3223 if (__glibc_unlikely (token->type == END_OF_RE))
3224 {
3225 *err = REG_EBRACK;
3226 goto parse_bracket_exp_free_return;
3227 }
3228 if (token->type == OP_CLOSE_BRACKET)
3229 break;
3230 }
3231
3232 re_string_skip_bytes (regexp, token_len); /* Skip a token. */
3233
3234 /* If it is non-matching list. */
3235 if (non_match)
3236 bitset_not (sbcset);
3237
3238 /* Ensure only single byte characters are set. */
3239 if (dfa->mb_cur_max > 1)
3240 bitset_mask (sbcset, dfa->sb_char);
3241
3242 if (mbcset->nmbchars || mbcset->ncoll_syms || mbcset->nequiv_classes
3243 || mbcset->nranges || (dfa->mb_cur_max > 1 && (mbcset->nchar_classes
3244 || mbcset->non_match)))
3245 {
3246 bin_tree_t *mbc_tree;
3247 int sbc_idx;
3248 /* Build a tree for complex bracket. */
3249 dfa->has_mb_node = 1;
3250 br_token.type = COMPLEX_BRACKET;
3251 br_token.opr.mbcset = mbcset;
3252 mbc_tree = create_token_tree (dfa, NULL, NULL, &br_token);
3253 if (__glibc_unlikely (mbc_tree == NULL))
3254 goto parse_bracket_exp_espace;
3255 for (sbc_idx = 0; sbc_idx < BITSET_WORDS; ++sbc_idx)
3256 if (sbcset[sbc_idx])
3257 break;
3258 /* If there are no bits set in sbcset, there is no point
3259 of having both SIMPLE_BRACKET and COMPLEX_BRACKET. */
3260 if (sbc_idx < BITSET_WORDS)
3261 {
3262 /* Build a tree for simple bracket. */
3263 br_token.type = SIMPLE_BRACKET;
3264 br_token.opr.sbcset = sbcset;
3265 work_tree = create_token_tree (dfa, NULL, NULL, &br_token);
3266 if (__glibc_unlikely (work_tree == NULL))
3267 goto parse_bracket_exp_espace;
3268
3269 /* Then join them by ALT node. */
3270 work_tree = create_tree (dfa, work_tree, mbc_tree, OP_ALT);
3271 if (__glibc_unlikely (work_tree == NULL))
3272 goto parse_bracket_exp_espace;
3273 }
3274 else
3275 {
3276 re_free (sbcset);
3277 work_tree = mbc_tree;
3278 }
3279 }
3280 else
3281 {
3282 free_charset (mbcset);
3283 mbcset = NULL;
3284 /* Build a tree for simple bracket. */
3285 br_token.type = SIMPLE_BRACKET;
3286 br_token.opr.sbcset = sbcset;
3287 work_tree = create_token_tree (dfa, NULL, NULL, &br_token);
3288 if (__glibc_unlikely (work_tree == NULL))
3289 goto parse_bracket_exp_espace;
3290 }
3291 return work_tree;
3292
3293 parse_bracket_exp_espace:
3294 *err = REG_ESPACE;
3295 parse_bracket_exp_free_return:
3296 re_free (sbcset);
3297 if (__glibc_likely (mbcset != NULL))
3298 free_charset (mbcset);
3299 return NULL;
3300 }
3301
3302 /* Parse an element in the bracket expression. */
3303
3304 static reg_errcode_t
3305 parse_bracket_element (bracket_elem_t *elem, re_string_t *regexp,
3306 re_token_t *token, int token_len, re_dfa_t *dfa,
3307 reg_syntax_t syntax, bool accept_hyphen)
3308 {
3309 int cur_char_size;
3310 cur_char_size = re_string_char_size_at (regexp, re_string_cur_idx (regexp));
3311 if (cur_char_size > 1)
3312 {
3313 elem->type = MB_CHAR;
3314 elem->opr.wch = re_string_wchar_at (regexp, re_string_cur_idx (regexp));
3315 re_string_skip_bytes (regexp, cur_char_size);
3316 return REG_NOERROR;
3317 }
3318 re_string_skip_bytes (regexp, token_len); /* Skip a token. */
3319 if (token->type == OP_OPEN_COLL_ELEM || token->type == OP_OPEN_CHAR_CLASS
3320 || token->type == OP_OPEN_EQUIV_CLASS)
3321 return parse_bracket_symbol (elem, regexp, token);
3322 if (__glibc_unlikely (token->type == OP_CHARSET_RANGE) && !accept_hyphen)
3323 {
3324 /* A '-' must only appear as anything but a range indicator before
3325 the closing bracket. Everything else is an error. */
3326 re_token_t token2;
3327 (void) peek_token_bracket (&token2, regexp, syntax);
3328 if (token2.type != OP_CLOSE_BRACKET)
3329 /* The actual error value is not standardized since this whole
3330 case is undefined. But ERANGE makes good sense. */
3331 return REG_ERANGE;
3332 }
3333 elem->type = SB_CHAR;
3334 elem->opr.ch = token->opr.c;
3335 return REG_NOERROR;
3336 }
3337
3338 /* Parse a bracket symbol in the bracket expression. Bracket symbols are
3339 such as [:<character_class>:], [.<collating_element>.], and
3340 [=<equivalent_class>=]. */
3341
3342 static reg_errcode_t
3343 parse_bracket_symbol (bracket_elem_t *elem, re_string_t *regexp,
3344 re_token_t *token)
3345 {
3346 unsigned char ch, delim = token->opr.c;
3347 int i = 0;
3348 if (re_string_eoi(regexp))
3349 return REG_EBRACK;
3350 for (;; ++i)
3351 {
3352 if (i >= BRACKET_NAME_BUF_SIZE)
3353 return REG_EBRACK;
3354 if (token->type == OP_OPEN_CHAR_CLASS)
3355 ch = re_string_fetch_byte_case (regexp);
3356 else
3357 ch = re_string_fetch_byte (regexp);
3358 if (re_string_eoi(regexp))
3359 return REG_EBRACK;
3360 if (ch == delim && re_string_peek_byte (regexp, 0) == ']')
3361 break;
3362 elem->opr.name[i] = ch;
3363 }
3364 re_string_skip_bytes (regexp, 1);
3365 elem->opr.name[i] = '\0';
3366 switch (token->type)
3367 {
3368 case OP_OPEN_COLL_ELEM:
3369 elem->type = COLL_SYM;
3370 break;
3371 case OP_OPEN_EQUIV_CLASS:
3372 elem->type = EQUIV_CLASS;
3373 break;
3374 case OP_OPEN_CHAR_CLASS:
3375 elem->type = CHAR_CLASS;
3376 break;
3377 default:
3378 break;
3379 }
3380 return REG_NOERROR;
3381 }
3382
3383 /* Helper function for parse_bracket_exp.
3384 Build the equivalence class which is represented by NAME.
3385 The result are written to MBCSET and SBCSET.
3386 EQUIV_CLASS_ALLOC is the allocated size of mbcset->equiv_classes,
3387 is a pointer argument since we may update it. */
3388
3389 static reg_errcode_t
3390 build_equiv_class (bitset_t sbcset, re_charset_t *mbcset,
3391 Idx *equiv_class_alloc, const unsigned char *name)
3392 {
3393 #ifdef _LIBC
3394 uint32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
3395 if (nrules != 0)
3396 {
3397 const int32_t *table, *indirect;
3398 const unsigned char *weights, *extra, *cp;
3399 unsigned char char_buf[2];
3400 int32_t idx1, idx2;
3401 unsigned int ch;
3402 size_t len;
3403 /* Calculate the index for equivalence class. */
3404 cp = name;
3405 table = (const int32_t *) _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
3406 weights = (const unsigned char *) _NL_CURRENT (LC_COLLATE,
3407 _NL_COLLATE_WEIGHTMB);
3408 extra = (const unsigned char *) _NL_CURRENT (LC_COLLATE,
3409 _NL_COLLATE_EXTRAMB);
3410 indirect = (const int32_t *) _NL_CURRENT (LC_COLLATE,
3411 _NL_COLLATE_INDIRECTMB);
3412 idx1 = findidx (table, indirect, extra, &cp, -1);
3413 if (__glibc_unlikely (idx1 == 0 || *cp != '\0'))
3414 /* This isn't a valid character. */
3415 return REG_ECOLLATE;
3416
3417 /* Build single byte matching table for this equivalence class. */
3418 len = weights[idx1 & 0xffffff];
3419 for (ch = 0; ch < SBC_MAX; ++ch)
3420 {
3421 char_buf[0] = ch;
3422 cp = char_buf;
3423 idx2 = findidx (table, indirect, extra, &cp, 1);
3424 /*
3425 idx2 = table[ch];
3426 */
3427 if (idx2 == 0)
3428 /* This isn't a valid character. */
3429 continue;
3430 /* Compare only if the length matches and the collation rule
3431 index is the same. */
3432 if (len == weights[idx2 & 0xffffff] && (idx1 >> 24) == (idx2 >> 24)
3433 && memcmp (weights + (idx1 & 0xffffff) + 1,
3434 weights + (idx2 & 0xffffff) + 1, len) == 0)
3435 bitset_set (sbcset, ch);
3436 }
3437 /* Check whether the array has enough space. */
3438 if (__glibc_unlikely (*equiv_class_alloc == mbcset->nequiv_classes))
3439 {
3440 /* Not enough, realloc it. */
3441 /* +1 in case of mbcset->nequiv_classes is 0. */
3442 Idx new_equiv_class_alloc = 2 * mbcset->nequiv_classes + 1;
3443 /* Use realloc since the array is NULL if *alloc == 0. */
3444 int32_t *new_equiv_classes = re_realloc (mbcset->equiv_classes,
3445 int32_t,
3446 new_equiv_class_alloc);
3447 if (__glibc_unlikely (new_equiv_classes == NULL))
3448 return REG_ESPACE;
3449 mbcset->equiv_classes = new_equiv_classes;
3450 *equiv_class_alloc = new_equiv_class_alloc;
3451 }
3452 mbcset->equiv_classes[mbcset->nequiv_classes++] = idx1;
3453 }
3454 else
3455 #endif /* _LIBC */
3456 {
3457 if (__glibc_unlikely (strlen ((const char *) name) != 1))
3458 return REG_ECOLLATE;
3459 bitset_set (sbcset, *name);
3460 }
3461 return REG_NOERROR;
3462 }
3463
3464 /* Helper function for parse_bracket_exp.
3465 Build the character class which is represented by NAME.
3466 The result are written to MBCSET and SBCSET.
3467 CHAR_CLASS_ALLOC is the allocated size of mbcset->char_classes,
3468 is a pointer argument since we may update it. */
3469
3470 static reg_errcode_t
3471 build_charclass (RE_TRANSLATE_TYPE trans, bitset_t sbcset,
3472 re_charset_t *mbcset, Idx *char_class_alloc,
3473 const char *class_name, reg_syntax_t syntax)
3474 {
3475 int i;
3476 const char *name = class_name;
3477
3478 /* In case of REG_ICASE "upper" and "lower" match the both of
3479 upper and lower cases. */
3480 if ((syntax & RE_ICASE)
3481 && (strcmp (name, "upper") == 0 || strcmp (name, "lower") == 0))
3482 name = "alpha";
3483
3484 /* Check the space of the arrays. */
3485 if (__glibc_unlikely (*char_class_alloc == mbcset->nchar_classes))
3486 {
3487 /* Not enough, realloc it. */
3488 /* +1 in case of mbcset->nchar_classes is 0. */
3489 Idx new_char_class_alloc = 2 * mbcset->nchar_classes + 1;
3490 /* Use realloc since array is NULL if *alloc == 0. */
3491 wctype_t *new_char_classes = re_realloc (mbcset->char_classes, wctype_t,
3492 new_char_class_alloc);
3493 if (__glibc_unlikely (new_char_classes == NULL))
3494 return REG_ESPACE;
3495 mbcset->char_classes = new_char_classes;
3496 *char_class_alloc = new_char_class_alloc;
3497 }
3498 mbcset->char_classes[mbcset->nchar_classes++] = __wctype (name);
3499
3500 #define BUILD_CHARCLASS_LOOP(ctype_func) \
3501 do { \
3502 if (__glibc_unlikely (trans != NULL)) \
3503 { \
3504 for (i = 0; i < SBC_MAX; ++i) \
3505 if (ctype_func (i)) \
3506 bitset_set (sbcset, trans[i]); \
3507 } \
3508 else \
3509 { \
3510 for (i = 0; i < SBC_MAX; ++i) \
3511 if (ctype_func (i)) \
3512 bitset_set (sbcset, i); \
3513 } \
3514 } while (0)
3515
3516 if (strcmp (name, "alnum") == 0)
3517 BUILD_CHARCLASS_LOOP (isalnum);
3518 else if (strcmp (name, "cntrl") == 0)
3519 BUILD_CHARCLASS_LOOP (iscntrl);
3520 else if (strcmp (name, "lower") == 0)
3521 BUILD_CHARCLASS_LOOP (islower);
3522 else if (strcmp (name, "space") == 0)
3523 BUILD_CHARCLASS_LOOP (isspace);
3524 else if (strcmp (name, "alpha") == 0)
3525 BUILD_CHARCLASS_LOOP (isalpha);
3526 else if (strcmp (name, "digit") == 0)
3527 BUILD_CHARCLASS_LOOP (isdigit);
3528 else if (strcmp (name, "print") == 0)
3529 BUILD_CHARCLASS_LOOP (isprint);
3530 else if (strcmp (name, "upper") == 0)
3531 BUILD_CHARCLASS_LOOP (isupper);
3532 else if (strcmp (name, "blank") == 0)
3533 BUILD_CHARCLASS_LOOP (isblank);
3534 else if (strcmp (name, "graph") == 0)
3535 BUILD_CHARCLASS_LOOP (isgraph);
3536 else if (strcmp (name, "punct") == 0)
3537 BUILD_CHARCLASS_LOOP (ispunct);
3538 else if (strcmp (name, "xdigit") == 0)
3539 BUILD_CHARCLASS_LOOP (isxdigit);
3540 else
3541 return REG_ECTYPE;
3542
3543 return REG_NOERROR;
3544 }
3545
3546 static bin_tree_t *
3547 build_charclass_op (re_dfa_t *dfa, RE_TRANSLATE_TYPE trans,
3548 const char *class_name,
3549 const char *extra, bool non_match,
3550 reg_errcode_t *err)
3551 {
3552 re_bitset_ptr_t sbcset;
3553 re_charset_t *mbcset;
3554 Idx alloc = 0;
3555 reg_errcode_t ret;
3556 bin_tree_t *tree;
3557
3558 sbcset = (re_bitset_ptr_t) calloc (1, sizeof (bitset_t));
3559 if (__glibc_unlikely (sbcset == NULL))
3560 {
3561 *err = REG_ESPACE;
3562 return NULL;
3563 }
3564 mbcset = (re_charset_t *) calloc (1, sizeof (re_charset_t));
3565 if (__glibc_unlikely (mbcset == NULL))
3566 {
3567 re_free (sbcset);
3568 *err = REG_ESPACE;
3569 return NULL;
3570 }
3571 mbcset->non_match = non_match;
3572
3573 /* We don't care the syntax in this case. */
3574 ret = build_charclass (trans, sbcset, mbcset, &alloc, class_name, 0);
3575
3576 if (__glibc_unlikely (ret != REG_NOERROR))
3577 {
3578 re_free (sbcset);
3579 free_charset (mbcset);
3580 *err = ret;
3581 return NULL;
3582 }
3583 /* \w match '_' also. */
3584 for (; *extra; extra++)
3585 bitset_set (sbcset, *extra);
3586
3587 /* If it is non-matching list. */
3588 if (non_match)
3589 bitset_not (sbcset);
3590
3591 /* Ensure only single byte characters are set. */
3592 if (dfa->mb_cur_max > 1)
3593 bitset_mask (sbcset, dfa->sb_char);
3594
3595 /* Build a tree for simple bracket. */
3596 re_token_t br_token = { .type = SIMPLE_BRACKET, .opr.sbcset = sbcset };
3597 tree = create_token_tree (dfa, NULL, NULL, &br_token);
3598 if (__glibc_unlikely (tree == NULL))
3599 goto build_word_op_espace;
3600
3601 if (dfa->mb_cur_max > 1)
3602 {
3603 bin_tree_t *mbc_tree;
3604 /* Build a tree for complex bracket. */
3605 br_token.type = COMPLEX_BRACKET;
3606 br_token.opr.mbcset = mbcset;
3607 dfa->has_mb_node = 1;
3608 mbc_tree = create_token_tree (dfa, NULL, NULL, &br_token);
3609 if (__glibc_unlikely (mbc_tree == NULL))
3610 goto build_word_op_espace;
3611 /* Then join them by ALT node. */
3612 tree = create_tree (dfa, tree, mbc_tree, OP_ALT);
3613 if (__glibc_likely (mbc_tree != NULL))
3614 return tree;
3615 }
3616 else
3617 {
3618 free_charset (mbcset);
3619 return tree;
3620 }
3621
3622 build_word_op_espace:
3623 re_free (sbcset);
3624 free_charset (mbcset);
3625 *err = REG_ESPACE;
3626 return NULL;
3627 }
3628
3629 /* This is intended for the expressions like "a{1,3}".
3630 Fetch a number from 'input', and return the number.
3631 Return -1 if the number field is empty like "{,1}".
3632 Return RE_DUP_MAX + 1 if the number field is too large.
3633 Return -2 if an error occurred. */
3634
3635 static Idx
3636 fetch_number (re_string_t *input, re_token_t *token, reg_syntax_t syntax)
3637 {
3638 Idx num = -1;
3639 unsigned char c;
3640 while (1)
3641 {
3642 fetch_token (token, input, syntax);
3643 c = token->opr.c;
3644 if (__glibc_unlikely (token->type == END_OF_RE))
3645 return -2;
3646 if (token->type == OP_CLOSE_DUP_NUM || c == ',')
3647 break;
3648 num = ((token->type != CHARACTER || c < '0' || '9' < c || num == -2)
3649 ? -2
3650 : num == -1
3651 ? c - '0'
3652 : MIN (RE_DUP_MAX + 1, num * 10 + c - '0'));
3653 }
3654 return num;
3655 }
3656
3657 static void
3658 free_charset (re_charset_t *cset)
3659 {
3660 re_free (cset->mbchars);
3661 #ifdef _LIBC
3662 re_free (cset->coll_syms);
3663 re_free (cset->equiv_classes);
3664 #endif
3665 re_free (cset->range_starts);
3666 re_free (cset->range_ends);
3667 re_free (cset->char_classes);
3668 re_free (cset);
3669 }
3670
3671 /* Functions for binary tree operation. */
3672
3673 /* Create a tree node. */
3674
3675 static bin_tree_t *
3676 create_tree (re_dfa_t *dfa, bin_tree_t *left, bin_tree_t *right,
3677 re_token_type_t type)
3678 {
3679 re_token_t t = { .type = type };
3680 return create_token_tree (dfa, left, right, &t);
3681 }
3682
3683 static bin_tree_t *
3684 create_token_tree (re_dfa_t *dfa, bin_tree_t *left, bin_tree_t *right,
3685 const re_token_t *token)
3686 {
3687 bin_tree_t *tree;
3688 if (__glibc_unlikely (dfa->str_tree_storage_idx == BIN_TREE_STORAGE_SIZE))
3689 {
3690 bin_tree_storage_t *storage = re_malloc (bin_tree_storage_t, 1);
3691
3692 if (storage == NULL)
3693 return NULL;
3694 storage->next = dfa->str_tree_storage;
3695 dfa->str_tree_storage = storage;
3696 dfa->str_tree_storage_idx = 0;
3697 }
3698 tree = &dfa->str_tree_storage->data[dfa->str_tree_storage_idx++];
3699
3700 tree->parent = NULL;
3701 tree->left = left;
3702 tree->right = right;
3703 tree->token = *token;
3704 tree->token.duplicated = 0;
3705 tree->token.opt_subexp = 0;
3706 tree->first = NULL;
3707 tree->next = NULL;
3708 tree->node_idx = -1;
3709
3710 if (left != NULL)
3711 left->parent = tree;
3712 if (right != NULL)
3713 right->parent = tree;
3714 return tree;
3715 }
3716
3717 /* Mark the tree SRC as an optional subexpression.
3718 To be called from preorder or postorder. */
3719
3720 static reg_errcode_t
3721 mark_opt_subexp (void *extra, bin_tree_t *node)
3722 {
3723 Idx idx = (uintptr_t) extra;
3724 if (node->token.type == SUBEXP && node->token.opr.idx == idx)
3725 node->token.opt_subexp = 1;
3726
3727 return REG_NOERROR;
3728 }
3729
3730 /* Free the allocated memory inside NODE. */
3731
3732 static void
3733 free_token (re_token_t *node)
3734 {
3735 if (node->type == COMPLEX_BRACKET && node->duplicated == 0)
3736 free_charset (node->opr.mbcset);
3737 else if (node->type == SIMPLE_BRACKET && node->duplicated == 0)
3738 re_free (node->opr.sbcset);
3739 }
3740
3741 /* Worker function for tree walking. Free the allocated memory inside NODE
3742 and its children. */
3743
3744 static reg_errcode_t
3745 free_tree (void *extra, bin_tree_t *node)
3746 {
3747 free_token (&node->token);
3748 return REG_NOERROR;
3749 }
3750
3751
3752 /* Duplicate the node SRC, and return new node. This is a preorder
3753 visit similar to the one implemented by the generic visitor, but
3754 we need more infrastructure to maintain two parallel trees --- so,
3755 it's easier to duplicate. */
3756
3757 static bin_tree_t *
3758 duplicate_tree (const bin_tree_t *root, re_dfa_t *dfa)
3759 {
3760 const bin_tree_t *node;
3761 bin_tree_t *dup_root;
3762 bin_tree_t **p_new = &dup_root, *dup_node = root->parent;
3763
3764 for (node = root; ; )
3765 {
3766 /* Create a new tree and link it back to the current parent. */
3767 *p_new = create_token_tree (dfa, NULL, NULL, &node->token);
3768 if (*p_new == NULL)
3769 return NULL;
3770 (*p_new)->parent = dup_node;
3771 (*p_new)->token.duplicated = 1;
3772 dup_node = *p_new;
3773
3774 /* Go to the left node, or up and to the right. */
3775 if (node->left)
3776 {
3777 node = node->left;
3778 p_new = &dup_node->left;
3779 }
3780 else
3781 {
3782 const bin_tree_t *prev = NULL;
3783 while (node->right == prev || node->right == NULL)
3784 {
3785 prev = node;
3786 node = node->parent;
3787 dup_node = dup_node->parent;
3788 if (!node)
3789 return dup_root;
3790 }
3791 node = node->right;
3792 p_new = &dup_node->right;
3793 }
3794 }
3795 }