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