1 /* Extended regular expression matching and search library.
2 Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
4 Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>.
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License along
17 with this program; if not, write to the Free Software Foundation,
18 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
20 static reg_errcode_t match_ctx_init (re_match_context_t *cache, int eflags,
21 Idx n) internal_function;
22 static void match_ctx_clean (re_match_context_t *mctx) internal_function;
23 static void match_ctx_free (re_match_context_t *cache) internal_function;
24 static reg_errcode_t match_ctx_add_entry (re_match_context_t *cache, Idx node,
25 Idx str_idx, Idx from, Idx to)
27 static Idx search_cur_bkref_entry (const re_match_context_t *mctx, Idx str_idx)
29 static reg_errcode_t match_ctx_add_subtop (re_match_context_t *mctx, Idx node,
30 Idx str_idx) internal_function;
31 static re_sub_match_last_t * match_ctx_add_sublast (re_sub_match_top_t *subtop,
32 Idx node, Idx str_idx)
34 static void sift_ctx_init (re_sift_context_t *sctx, re_dfastate_t **sifted_sts,
35 re_dfastate_t **limited_sts, Idx last_node,
38 static reg_errcode_t re_search_internal (const regex_t *preg,
39 const char *string, Idx length,
40 Idx start, Idx last_start, Idx stop,
41 size_t nmatch, regmatch_t pmatch[],
42 int eflags) internal_function;
43 static regoff_t re_search_2_stub (struct re_pattern_buffer *bufp,
44 const char *string1, Idx length1,
45 const char *string2, Idx length2,
46 Idx start, regoff_t range,
47 struct re_registers *regs,
48 Idx stop, bool ret_len) internal_function;
49 static regoff_t re_search_stub (struct re_pattern_buffer *bufp,
50 const char *string, Idx length, Idx start,
51 regoff_t range, Idx stop,
52 struct re_registers *regs,
53 bool ret_len) internal_function;
54 static unsigned re_copy_regs (struct re_registers *regs, regmatch_t *pmatch,
55 Idx nregs, int regs_allocated) internal_function;
56 static reg_errcode_t prune_impossible_nodes (re_match_context_t *mctx)
58 static Idx check_matching (re_match_context_t *mctx, bool fl_longest_match,
61 static Idx check_halt_state_context (const re_match_context_t *mctx,
62 const re_dfastate_t *state, Idx idx)
64 static void update_regs (re_dfa_t *dfa, regmatch_t *pmatch,
65 regmatch_t *prev_idx_match, Idx cur_node,
66 Idx cur_idx, Idx nmatch) internal_function;
67 static reg_errcode_t push_fail_stack (struct re_fail_stack_t *fs,
68 Idx str_idx, Idx dest_node, Idx nregs,
70 re_node_set *eps_via_nodes) internal_function;
71 static reg_errcode_t set_regs (const regex_t *preg,
72 const re_match_context_t *mctx,
73 size_t nmatch, regmatch_t *pmatch,
74 bool fl_backtrack) internal_function;
75 static reg_errcode_t free_fail_stack_return (struct re_fail_stack_t *fs) internal_function;
78 static int sift_states_iter_mb (const re_match_context_t *mctx,
79 re_sift_context_t *sctx,
80 Idx node_idx, Idx str_idx, Idx max_str_idx) internal_function;
81 #endif /* RE_ENABLE_I18N */
82 static reg_errcode_t sift_states_backward (re_match_context_t *mctx,
83 re_sift_context_t *sctx) internal_function;
84 static reg_errcode_t build_sifted_states (re_match_context_t *mctx,
85 re_sift_context_t *sctx, Idx str_idx,
86 re_node_set *cur_dest) internal_function;
87 static reg_errcode_t update_cur_sifted_state (re_match_context_t *mctx,
88 re_sift_context_t *sctx,
90 re_node_set *dest_nodes) internal_function;
91 static reg_errcode_t add_epsilon_src_nodes (re_dfa_t *dfa,
92 re_node_set *dest_nodes,
93 const re_node_set *candidates) internal_function;
94 static bool check_dst_limits (const re_match_context_t *mctx,
95 const re_node_set *limits,
96 Idx dst_node, Idx dst_idx, Idx src_node,
97 Idx src_idx) internal_function;
98 static int check_dst_limits_calc_pos_1 (const re_match_context_t *mctx,
99 int boundaries, Idx subexp_idx,
100 Idx from_node, Idx bkref_idx) internal_function;
101 static int check_dst_limits_calc_pos (const re_match_context_t *mctx,
102 Idx limit, Idx subexp_idx,
103 Idx node, Idx str_idx,
104 Idx bkref_idx) internal_function;
105 static reg_errcode_t check_subexp_limits (re_dfa_t *dfa,
106 re_node_set *dest_nodes,
107 const re_node_set *candidates,
109 struct re_backref_cache_entry *bkref_ents,
110 Idx str_idx) internal_function;
111 static reg_errcode_t sift_states_bkref (re_match_context_t *mctx,
112 re_sift_context_t *sctx,
113 Idx str_idx, const re_node_set *candidates) internal_function;
114 static reg_errcode_t merge_state_array (re_dfa_t *dfa, re_dfastate_t **dst,
115 re_dfastate_t **src, Idx num) internal_function;
116 static re_dfastate_t *find_recover_state (reg_errcode_t *err,
117 re_match_context_t *mctx) internal_function;
118 static re_dfastate_t *transit_state (reg_errcode_t *err,
119 re_match_context_t *mctx,
120 re_dfastate_t *state) internal_function;
121 static re_dfastate_t *merge_state_with_log (reg_errcode_t *err,
122 re_match_context_t *mctx,
123 re_dfastate_t *next_state) internal_function;
124 static reg_errcode_t check_subexp_matching_top (re_match_context_t *mctx,
125 re_node_set *cur_nodes,
126 Idx str_idx) internal_function;
128 static re_dfastate_t *transit_state_sb (reg_errcode_t *err,
129 re_match_context_t *mctx,
130 re_dfastate_t *pstate) internal_function;
132 #ifdef RE_ENABLE_I18N
133 static reg_errcode_t transit_state_mb (re_match_context_t *mctx,
134 re_dfastate_t *pstate) internal_function;
135 #endif /* RE_ENABLE_I18N */
136 static reg_errcode_t transit_state_bkref (re_match_context_t *mctx,
137 const re_node_set *nodes) internal_function;
138 static reg_errcode_t get_subexp (re_match_context_t *mctx,
139 Idx bkref_node, Idx bkref_str_idx) internal_function;
140 static reg_errcode_t get_subexp_sub (re_match_context_t *mctx,
141 const re_sub_match_top_t *sub_top,
142 re_sub_match_last_t *sub_last,
143 Idx bkref_node, Idx bkref_str) internal_function;
144 static Idx find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
145 Idx subexp_idx, int type) internal_function;
146 static reg_errcode_t check_arrival (re_match_context_t *mctx,
147 state_array_t *path, Idx top_node,
148 Idx top_str, Idx last_node, Idx last_str,
149 int type) internal_function;
150 static reg_errcode_t check_arrival_add_next_nodes (re_match_context_t *mctx,
152 re_node_set *cur_nodes,
153 re_node_set *next_nodes) internal_function;
154 static reg_errcode_t check_arrival_expand_ecl (re_dfa_t *dfa,
155 re_node_set *cur_nodes,
156 Idx ex_subexp, int type) internal_function;
157 static reg_errcode_t check_arrival_expand_ecl_sub (re_dfa_t *dfa,
158 re_node_set *dst_nodes,
159 Idx target, Idx ex_subexp,
160 int type) internal_function;
161 static reg_errcode_t expand_bkref_cache (re_match_context_t *mctx,
162 re_node_set *cur_nodes, Idx cur_str,
163 Idx subexp_num, int type) internal_function;
164 static bool build_trtable (re_dfa_t *dfa,
165 re_dfastate_t *state) internal_function;
166 #ifdef RE_ENABLE_I18N
167 static int check_node_accept_bytes (re_dfa_t *dfa, Idx node_idx,
168 const re_string_t *input, Idx idx) internal_function;
170 static unsigned int find_collation_sequence_value (const unsigned char *mbs,
171 size_t name_len) internal_function;
173 #endif /* RE_ENABLE_I18N */
174 static Idx group_nodes_into_DFAstates (const re_dfa_t *dfa,
175 const re_dfastate_t *state,
176 re_node_set *states_node,
177 bitset *states_ch) internal_function;
178 static bool check_node_accept (const re_match_context_t *mctx,
179 const re_token_t *node, Idx idx)
181 static reg_errcode_t extend_buffers (re_match_context_t *mctx) internal_function;
183 /* Entry point for POSIX code. */
185 /* regexec searches for a given pattern, specified by PREG, in the
188 If NMATCH is zero or REG_NOSUB was set in the cflags argument to
189 `regcomp', we ignore PMATCH. Otherwise, we assume PMATCH has at
190 least NMATCH elements, and we set them to the offsets of the
191 corresponding matched substrings.
193 EFLAGS specifies `execution flags' which affect matching: if
194 REG_NOTBOL is set, then ^ does not match at the beginning of the
195 string; if REG_NOTEOL is set, then $ does not match at the end.
197 We return 0 if we find a match and REG_NOMATCH if not. */
200 regexec (const regex_t *__restrict preg, const char *__restrict string,
201 size_t nmatch, regmatch_t pmatch[], int eflags)
206 re_dfa_t *dfa = (re_dfa_t *) preg->re_buffer;
209 if (eflags & ~(REG_NOTBOL | REG_NOTEOL | REG_STARTEND))
212 if (eflags & REG_STARTEND)
214 start = pmatch[0].rm_so;
215 length = pmatch[0].rm_eo;
220 length = strlen (string);
223 __libc_lock_lock (dfa->lock);
225 err = re_search_internal (preg, string, length, start, length,
226 length, 0, NULL, eflags);
228 err = re_search_internal (preg, string, length, start, length,
229 length, nmatch, pmatch, eflags);
230 __libc_lock_unlock (dfa->lock);
231 return err != REG_NOERROR;
235 # include <shlib-compat.h>
236 versioned_symbol (libc, __regexec, regexec, GLIBC_2_3_4);
238 # if SHLIB_COMPAT (libc, GLIBC_2_0, GLIBC_2_3_4)
239 __typeof__ (__regexec) __compat_regexec;
242 attribute_compat_text_section
243 __compat_regexec (const regex_t *__restrict preg,
244 const char *__restrict string, size_t nmatch,
245 regmatch_t pmatch[], int eflags)
247 return regexec (preg, string, nmatch, pmatch,
248 eflags & (REG_NOTBOL | REG_NOTEOL));
250 compat_symbol (libc, __compat_regexec, regexec, GLIBC_2_0);
254 /* Entry points for GNU code. */
256 /* re_match, re_search, re_match_2, re_search_2
258 The former two functions operate on STRING with length LENGTH,
259 while the later two operate on concatenation of STRING1 and STRING2
260 with lengths LENGTH1 and LENGTH2, respectively.
262 re_match() matches the compiled pattern in BUFP against the string,
263 starting at index START.
265 re_search() first tries matching at index START, then it tries to match
266 starting from index START + 1, and so on. The last start position tried
267 is START + RANGE. (Thus RANGE = 0 forces re_search to operate the same
270 The parameter STOP of re_{match,search}_2 specifies that no match exceeding
271 the first STOP characters of the concatenation of the strings should be
274 If REGS is not NULL, and BUFP->re_no_sub is not set, the offsets of the match
275 and all groups is stroed in REGS. (For the "_2" variants, the offsets are
276 computed relative to the concatenation, not relative to the individual
279 On success, re_match* functions return the length of the match, re_search*
280 return the position of the start of the match. Return value -1 means no
281 match was found and -2 indicates an internal error. */
284 re_match (struct re_pattern_buffer *bufp, const char *string,
285 Idx length, Idx start, struct re_registers *regs)
287 return re_search_stub (bufp, string, length, start, 0, length, regs, true);
290 weak_alias (__re_match, re_match)
294 re_search (struct re_pattern_buffer *bufp, const char *string,
295 Idx length, Idx start, regoff_t range, struct re_registers *regs)
297 return re_search_stub (bufp, string, length, start, range, length, regs,
301 weak_alias (__re_search, re_search)
305 re_match_2 (struct re_pattern_buffer *bufp,
306 const char *string1, Idx length1,
307 const char *string2, Idx length2,
308 Idx start, struct re_registers *regs, Idx stop)
310 return re_search_2_stub (bufp, string1, length1, string2, length2,
311 start, 0, regs, stop, true);
314 weak_alias (__re_match_2, re_match_2)
318 re_search_2 (struct re_pattern_buffer *bufp,
319 const char *string1, Idx length1,
320 const char *string2, Idx length2,
321 Idx start, regoff_t range, struct re_registers *regs, Idx stop)
323 return re_search_2_stub (bufp, string1, length1, string2, length2,
324 start, range, regs, stop, false);
327 weak_alias (__re_search_2, re_search_2)
332 re_search_2_stub (struct re_pattern_buffer *bufp,
333 const char *string1, Idx length1,
334 const char *string2, Idx length2,
335 Idx start, regoff_t range, struct re_registers *regs,
336 Idx stop, bool ret_len)
340 Idx len = length1 + length2;
343 if (BE (length1 < 0 || length2 < 0 || stop < 0 || len < length1, 0))
346 /* Concatenate the strings. */
350 s = re_malloc (char, len);
352 if (BE (s == NULL, 0))
354 memcpy (s, string1, length1);
355 memcpy (s + length1, string2, length2);
363 rval = re_search_stub (bufp, str, len, start, range, stop, regs,
369 /* The parameters have the same meaning as those of re_search.
370 Additional parameters:
371 If RET_LEN is true the length of the match is returned (re_match style);
372 otherwise the position of the match is returned. */
376 re_search_stub (struct re_pattern_buffer *bufp,
377 const char *string, Idx length,
378 Idx start, regoff_t range, Idx stop, struct re_registers *regs,
381 reg_errcode_t result;
387 re_dfa_t *dfa = (re_dfa_t *) bufp->re_buffer;
389 Idx last_start = start + range;
391 /* Check for out-of-range. */
392 if (BE (start < 0 || start > length, 0))
394 if (sizeof start < sizeof range)
396 regoff_t length_offset = length;
397 regoff_t start_offset = start;
398 if (BE (length_offset - start_offset < range, 0))
400 else if (BE (range < - start_offset, 0))
405 if (BE ((last_start < start) != (range < 0), 0))
407 /* Overflow occurred when computing last_start; substitute
408 the extreme value. */
409 last_start = range < 0 ? 0 : length;
413 if (BE (length < last_start, 0))
415 else if (BE (last_start < 0, 0))
420 __libc_lock_lock (dfa->lock);
422 eflags |= (bufp->re_not_bol) ? REG_NOTBOL : 0;
423 eflags |= (bufp->re_not_eol) ? REG_NOTEOL : 0;
425 /* Compile fastmap if we haven't yet. */
426 if (start < last_start && bufp->re_fastmap != NULL
427 && !bufp->re_fastmap_accurate)
428 re_compile_fastmap (bufp);
430 if (BE (bufp->re_no_sub, 0))
433 /* We need at least 1 register. */
436 else if (BE (bufp->re_regs_allocated == REG_FIXED
437 && regs->rm_num_regs < bufp->re_nsub + 1, 0))
439 nregs = regs->rm_num_regs;
440 if (BE (nregs < 1, 0))
442 /* Nothing can be copied to regs. */
448 nregs = bufp->re_nsub + 1;
449 pmatch = re_malloc (regmatch_t, nregs);
450 if (BE (pmatch == NULL, 0))
456 result = re_search_internal (bufp, string, length, start, last_start, stop,
457 nregs, pmatch, eflags);
461 /* I hope we needn't fill ther regs with -1's when no match was found. */
462 if (result != REG_NOERROR)
464 else if (regs != NULL)
466 /* If caller wants register contents data back, copy them. */
467 bufp->re_regs_allocated = re_copy_regs (regs, pmatch, nregs,
468 bufp->re_regs_allocated);
469 if (BE (bufp->re_regs_allocated == REG_UNALLOCATED, 0))
473 if (BE (rval == 0, 1))
477 assert (pmatch[0].rm_so == start);
478 rval = pmatch[0].rm_eo - start;
481 rval = pmatch[0].rm_so;
485 __libc_lock_unlock (dfa->lock);
491 re_copy_regs (struct re_registers *regs, regmatch_t *pmatch, Idx nregs,
494 int rval = REG_REALLOCATE;
496 Idx need_regs = nregs + 1;
497 /* We need one extra element beyond `rm_num_regs' for the `-1' marker GNU code
500 /* Have the register data arrays been allocated? */
501 if (regs_allocated == REG_UNALLOCATED)
502 { /* No. So allocate them with malloc. */
503 regs->rm_start = re_malloc (regoff_t, need_regs);
504 regs->rm_end = re_malloc (regoff_t, need_regs);
505 if (BE (regs->rm_start == NULL, 0) || BE (regs->rm_end == NULL, 0))
506 return REG_UNALLOCATED;
507 regs->rm_num_regs = need_regs;
509 else if (regs_allocated == REG_REALLOCATE)
510 { /* Yes. If we need more elements than were already
511 allocated, reallocate them. If we need fewer, just
513 if (BE (need_regs > regs->rm_num_regs, 0))
515 regoff_t *new_start =
516 re_realloc (regs->rm_start, regoff_t, need_regs);
517 regoff_t *new_end = re_realloc (regs->rm_end, regoff_t, need_regs);
518 if (BE (new_start == NULL, 0) || BE (new_end == NULL, 0))
519 return REG_UNALLOCATED;
520 regs->rm_start = new_start;
521 regs->rm_end = new_end;
522 regs->rm_num_regs = need_regs;
527 assert (regs_allocated == REG_FIXED);
528 /* This function may not be called with REG_FIXED and nregs too big. */
529 assert (regs->rm_num_regs >= nregs);
534 for (i = 0; i < nregs; ++i)
536 regs->rm_start[i] = pmatch[i].rm_so;
537 regs->rm_end[i] = pmatch[i].rm_eo;
539 for ( ; i < regs->rm_num_regs; ++i)
540 regs->rm_start[i] = regs->rm_end[i] = -1;
545 /* Set REGS to hold NUM_REGS registers, storing them in STARTS and
546 ENDS. Subsequent matches using PATTERN_BUFFER and REGS will use
547 this memory for recording register information. STARTS and ENDS
548 must be allocated using the malloc library routine, and must each
549 be at least NUM_REGS * sizeof (regoff_t) bytes long.
551 If NUM_REGS == 0, then subsequent matches should allocate their own
554 Unless this function is called, the first search or match using
555 PATTERN_BUFFER will allocate its own register data, without
556 freeing the old data. */
559 re_set_registers (struct re_pattern_buffer *bufp, struct re_registers *regs,
560 __re_size_t num_regs, regoff_t *starts, regoff_t *ends)
564 bufp->re_regs_allocated = REG_REALLOCATE;
565 regs->rm_num_regs = num_regs;
566 regs->rm_start = starts;
571 bufp->re_regs_allocated = REG_UNALLOCATED;
572 regs->rm_num_regs = 0;
573 regs->rm_start = regs->rm_end = NULL;
577 weak_alias (__re_set_registers, re_set_registers)
580 /* Entry points compatible with 4.2 BSD regex library. We don't define
581 them unless specifically requested. */
583 #if defined _REGEX_RE_COMP || defined _LIBC
588 re_exec (const char *s)
590 return 0 == regexec (&re_comp_buf, s, 0, NULL, 0);
592 #endif /* _REGEX_RE_COMP */
594 /* Internal entry point. */
596 /* Searches for a compiled pattern PREG in the string STRING, whose
597 length is LENGTH. NMATCH, PMATCH, and EFLAGS have the same
598 meaning as with regexec. LAST_START is START + RANGE, where
599 START and RANGE have the same meaning as with re_search.
600 Return REG_NOERROR if we find a match, and REG_NOMATCH if not,
601 otherwise return the error code.
602 Note: We assume front end functions already check ranges.
603 (0 <= LAST_START && LAST_START <= LENGTH) */
607 re_search_internal (const regex_t *preg,
608 const char *string, Idx length,
609 Idx start, Idx last_start, Idx stop,
610 size_t nmatch, regmatch_t pmatch[],
614 re_dfa_t *dfa = (re_dfa_t *) preg->re_buffer;
615 Idx left_lim, right_lim;
617 bool fl_longest_match;
619 Idx match_first, match_last = REG_MISSING;
623 #if defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L)
624 re_match_context_t mctx = { .dfa = dfa };
626 re_match_context_t mctx;
628 char *fastmap = ((preg->re_fastmap != NULL && preg->re_fastmap_accurate
629 && start != last_start && !preg->re_can_be_null)
630 ? preg->re_fastmap : NULL);
631 unsigned REG_TRANSLATE_TYPE t =
632 (unsigned REG_TRANSLATE_TYPE) preg->re_translate;
634 #if !(defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L))
635 memset (&mctx, '\0', sizeof (re_match_context_t));
639 extra_nmatch = (nmatch > preg->re_nsub) ? nmatch - (preg->re_nsub + 1) : 0;
640 nmatch -= extra_nmatch;
642 /* Check if the DFA haven't been compiled. */
643 if (BE (preg->re_used == 0 || dfa->init_state == NULL
644 || dfa->init_state_word == NULL || dfa->init_state_nl == NULL
645 || dfa->init_state_begbuf == NULL, 0))
649 /* We assume front-end functions already check them. */
650 assert (0 <= last_start && last_start <= length);
653 /* If initial states with non-begbuf contexts have no elements,
654 the regex must be anchored. If preg->re_newline_anchor is set,
655 we'll never use init_state_nl, so do not check it. */
656 if (dfa->init_state->nodes.nelem == 0
657 && dfa->init_state_word->nodes.nelem == 0
658 && (dfa->init_state_nl->nodes.nelem == 0
659 || !preg->re_newline_anchor))
661 if (start != 0 && last_start != 0)
663 start = last_start = 0;
666 /* We must check the longest matching, if nmatch > 0. */
667 fl_longest_match = (nmatch != 0 || dfa->nbackref);
669 err = re_string_allocate (&mctx.input, string, length, dfa->nodes_len + 1,
671 preg->re_syntax & REG_IGNORE_CASE, dfa);
672 if (BE (err != REG_NOERROR, 0))
674 mctx.input.stop = stop;
675 mctx.input.raw_stop = stop;
676 mctx.input.newline_anchor = preg->re_newline_anchor;
678 err = match_ctx_init (&mctx, eflags, dfa->nbackref * 2);
679 if (BE (err != REG_NOERROR, 0))
682 /* We will log all the DFA states through which the dfa pass,
683 if nmatch > 1, or this dfa has "multibyte node", which is a
684 back-reference or a node which can accept multibyte character or
685 multi character collating element. */
686 if (nmatch > 1 || dfa->has_mb_node)
688 mctx.state_log = re_malloc (re_dfastate_t *, mctx.input.bufs_len + 1);
689 if (BE (mctx.state_log == NULL, 0))
696 mctx.state_log = NULL;
699 mctx.input.tip_context = (eflags & REG_NOTBOL) ? CONTEXT_BEGBUF
700 : CONTEXT_NEWLINE | CONTEXT_BEGBUF;
702 /* Check incrementally whether of not the input string match. */
703 incr = (last_start < start) ? -1 : 1;
704 left_lim = (last_start < start) ? last_start : start;
705 right_lim = (last_start < start) ? start : last_start;
706 sb = dfa->mb_cur_max == 1;
709 ? ((sb || !(preg->re_syntax & REG_IGNORE_CASE || t) ? 4 : 0)
710 | (start <= last_start ? 2 : 0)
711 | (t != NULL ? 1 : 0))
714 for (;; match_first += incr)
717 if (match_first < left_lim || right_lim < match_first)
720 /* Advance as rapidly as possible through the string, until we
721 find a plausible place to start matching. This may be done
722 with varying efficiency, so there are various possibilities:
723 only the most common of them are specialized, in order to
724 save on code size. We use a switch statement for speed. */
732 /* Fastmap with single-byte translation, match forward. */
733 while (BE (match_first < right_lim, 1)
734 && !fastmap[t[(unsigned char) string[match_first]]])
736 goto forward_match_found_start_or_reached_end;
739 /* Fastmap without translation, match forward. */
740 while (BE (match_first < right_lim, 1)
741 && !fastmap[(unsigned char) string[match_first]])
744 forward_match_found_start_or_reached_end:
745 if (BE (match_first == right_lim, 0))
747 ch = match_first >= length
748 ? 0 : (unsigned char) string[match_first];
749 if (!fastmap[t ? t[ch] : ch])
756 /* Fastmap without multi-byte translation, match backwards. */
757 while (match_first >= left_lim)
759 ch = match_first >= length
760 ? 0 : (unsigned char) string[match_first];
761 if (fastmap[t ? t[ch] : ch])
765 if (match_first < left_lim)
770 /* In this case, we can't determine easily the current byte,
771 since it might be a component byte of a multibyte
772 character. Then we use the constructed buffer instead. */
775 /* If MATCH_FIRST is out of the valid range, reconstruct the
777 __re_size_t offset = match_first - mctx.input.raw_mbs_idx;
778 if (BE (offset >= (__re_size_t) mctx.input.valid_raw_len, 0))
780 err = re_string_reconstruct (&mctx.input, match_first,
782 if (BE (err != REG_NOERROR, 0))
785 offset = match_first - mctx.input.raw_mbs_idx;
787 /* If MATCH_FIRST is out of the buffer, leave it as '\0'.
788 Note that MATCH_FIRST must not be smaller than 0. */
789 ch = (match_first >= length
790 ? 0 : re_string_byte_at (&mctx.input, offset));
794 if (match_first < left_lim || match_first > right_lim)
803 /* Reconstruct the buffers so that the matcher can assume that
804 the matching starts from the beginning of the buffer. */
805 err = re_string_reconstruct (&mctx.input, match_first, eflags);
806 if (BE (err != REG_NOERROR, 0))
809 #ifdef RE_ENABLE_I18N
810 /* Don't consider this char as a possible match start if it part,
811 yet isn't the head, of a multibyte character. */
812 if (!sb && !re_string_first_byte (&mctx.input, 0))
816 /* It seems to be appropriate one, then use the matcher. */
817 /* We assume that the matching starts from 0. */
818 mctx.state_log_top = mctx.nbkref_ents = mctx.max_mb_elem_len = 0;
819 match_last = check_matching (&mctx, fl_longest_match,
820 start <= last_start ? &match_first : NULL);
821 if (match_last != REG_MISSING)
823 if (BE (match_last == REG_ERROR, 0))
830 mctx.match_last = match_last;
831 if ((!preg->re_no_sub && nmatch > 1) || dfa->nbackref)
833 re_dfastate_t *pstate = mctx.state_log[match_last];
834 mctx.last_node = check_halt_state_context (&mctx, pstate,
837 if ((!preg->re_no_sub && nmatch > 1 && dfa->has_plural_match)
840 err = prune_impossible_nodes (&mctx);
841 if (err == REG_NOERROR)
843 if (BE (err != REG_NOMATCH, 0))
845 match_last = REG_MISSING;
848 break; /* We found a match. */
852 match_ctx_clean (&mctx);
856 assert (match_last != REG_MISSING);
857 assert (err == REG_NOERROR);
860 /* Set pmatch[] if we need. */
865 /* Initialize registers. */
866 for (reg_idx = 1; reg_idx < nmatch; ++reg_idx)
867 pmatch[reg_idx].rm_so = pmatch[reg_idx].rm_eo = -1;
869 /* Set the points where matching start/end. */
871 pmatch[0].rm_eo = mctx.match_last;
872 /* FIXME: This function should fail if mctx.match_last exceeds
873 the maximum possible regoff_t value. We need a new error
874 code REG_OVERFLOW. */
876 if (!preg->re_no_sub && nmatch > 1)
878 err = set_regs (preg, &mctx, nmatch, pmatch,
879 dfa->has_plural_match && dfa->nbackref > 0);
880 if (BE (err != REG_NOERROR, 0))
884 /* At last, add the offset to the each registers, since we slided
885 the buffers so that we could assume that the matching starts
887 for (reg_idx = 0; reg_idx < nmatch; ++reg_idx)
888 if (pmatch[reg_idx].rm_so != -1)
890 #ifdef RE_ENABLE_I18N
891 if (BE (mctx.input.offsets_needed != 0, 0))
893 pmatch[reg_idx].rm_so =
894 (pmatch[reg_idx].rm_so == mctx.input.valid_len
895 ? mctx.input.valid_raw_len
896 : mctx.input.offsets[pmatch[reg_idx].rm_so]);
897 pmatch[reg_idx].rm_eo =
898 (pmatch[reg_idx].rm_eo == mctx.input.valid_len
899 ? mctx.input.valid_raw_len
900 : mctx.input.offsets[pmatch[reg_idx].rm_eo]);
903 assert (mctx.input.offsets_needed == 0);
905 pmatch[reg_idx].rm_so += match_first;
906 pmatch[reg_idx].rm_eo += match_first;
908 for (reg_idx = 0; reg_idx < extra_nmatch; ++reg_idx)
910 pmatch[nmatch + reg_idx].rm_so = -1;
911 pmatch[nmatch + reg_idx].rm_eo = -1;
915 for (reg_idx = 0; reg_idx + 1 < nmatch; reg_idx++)
916 if (dfa->subexp_map[reg_idx] != reg_idx)
918 pmatch[reg_idx + 1].rm_so
919 = pmatch[dfa->subexp_map[reg_idx] + 1].rm_so;
920 pmatch[reg_idx + 1].rm_eo
921 = pmatch[dfa->subexp_map[reg_idx] + 1].rm_eo;
926 re_free (mctx.state_log);
928 match_ctx_free (&mctx);
929 re_string_destruct (&mctx.input);
935 prune_impossible_nodes (re_match_context_t *mctx)
937 re_dfa_t *const dfa = mctx->dfa;
938 Idx halt_node, match_last;
940 re_dfastate_t **sifted_states;
941 re_dfastate_t **lim_states = NULL;
942 re_sift_context_t sctx;
944 assert (mctx->state_log != NULL);
946 match_last = mctx->match_last;
947 halt_node = mctx->last_node;
948 sifted_states = re_malloc (re_dfastate_t *, match_last + 1);
949 if (BE (sifted_states == NULL, 0))
956 lim_states = re_malloc (re_dfastate_t *, match_last + 1);
957 if (BE (lim_states == NULL, 0))
964 memset (lim_states, '\0',
965 sizeof (re_dfastate_t *) * (match_last + 1));
966 sift_ctx_init (&sctx, sifted_states, lim_states, halt_node,
968 ret = sift_states_backward (mctx, &sctx);
969 re_node_set_free (&sctx.limits);
970 if (BE (ret != REG_NOERROR, 0))
972 if (sifted_states[0] != NULL || lim_states[0] != NULL)
977 if (! REG_VALID_INDEX (match_last))
982 } while (mctx->state_log[match_last] == NULL
983 || !mctx->state_log[match_last]->halt);
984 halt_node = check_halt_state_context (mctx,
985 mctx->state_log[match_last],
988 ret = merge_state_array (dfa, sifted_states, lim_states,
990 re_free (lim_states);
992 if (BE (ret != REG_NOERROR, 0))
997 sift_ctx_init (&sctx, sifted_states, lim_states, halt_node, match_last);
998 ret = sift_states_backward (mctx, &sctx);
999 re_node_set_free (&sctx.limits);
1000 if (BE (ret != REG_NOERROR, 0))
1003 re_free (mctx->state_log);
1004 mctx->state_log = sifted_states;
1005 sifted_states = NULL;
1006 mctx->last_node = halt_node;
1007 mctx->match_last = match_last;
1010 re_free (sifted_states);
1011 re_free (lim_states);
1015 /* Acquire an initial state and return it.
1016 We must select appropriate initial state depending on the context,
1017 since initial states may have constraints like "\<", "^", etc.. */
1019 static inline re_dfastate_t *
1020 __attribute ((always_inline)) internal_function
1021 acquire_init_state_context (reg_errcode_t *err, const re_match_context_t *mctx,
1024 re_dfa_t *const dfa = mctx->dfa;
1025 if (dfa->init_state->has_constraint)
1027 unsigned int context;
1028 context = re_string_context_at (&mctx->input, idx - 1, mctx->eflags);
1029 if (IS_WORD_CONTEXT (context))
1030 return dfa->init_state_word;
1031 else if (IS_ORDINARY_CONTEXT (context))
1032 return dfa->init_state;
1033 else if (IS_BEGBUF_CONTEXT (context) && IS_NEWLINE_CONTEXT (context))
1034 return dfa->init_state_begbuf;
1035 else if (IS_NEWLINE_CONTEXT (context))
1036 return dfa->init_state_nl;
1037 else if (IS_BEGBUF_CONTEXT (context))
1039 /* It is relatively rare case, then calculate on demand. */
1040 return re_acquire_state_context (err, dfa,
1041 dfa->init_state->entrance_nodes,
1045 /* Must not happen? */
1046 return dfa->init_state;
1049 return dfa->init_state;
1052 /* Check whether the regular expression match input string INPUT or not,
1053 and return the index where the matching end. Return REG_MISSING if
1054 there is no match, and return REG_ERROR in case of an error.
1055 FL_LONGEST_MATCH means we want the POSIX longest matching.
1056 If P_MATCH_FIRST is not NULL, and the match fails, it is set to the
1057 next place where we may want to try matching.
1058 Note that the matcher assume that the maching starts from the current
1059 index of the buffer. */
1063 check_matching (re_match_context_t *mctx, bool fl_longest_match,
1066 re_dfa_t *const dfa = mctx->dfa;
1069 Idx match_last = REG_MISSING;
1070 Idx cur_str_idx = re_string_cur_idx (&mctx->input);
1071 re_dfastate_t *cur_state;
1072 bool at_init_state = p_match_first != NULL;
1073 Idx next_start_idx = cur_str_idx;
1076 cur_state = acquire_init_state_context (&err, mctx, cur_str_idx);
1077 /* An initial state must not be NULL (invalid). */
1078 if (BE (cur_state == NULL, 0))
1080 assert (err == REG_ESPACE);
1084 if (mctx->state_log != NULL)
1086 mctx->state_log[cur_str_idx] = cur_state;
1088 /* Check OP_OPEN_SUBEXP in the initial state in case that we use them
1089 later. E.g. Processing back references. */
1090 if (BE (dfa->nbackref, 0))
1092 at_init_state = false;
1093 err = check_subexp_matching_top (mctx, &cur_state->nodes, 0);
1094 if (BE (err != REG_NOERROR, 0))
1097 if (cur_state->has_backref)
1099 err = transit_state_bkref (mctx, &cur_state->nodes);
1100 if (BE (err != REG_NOERROR, 0))
1106 /* If the RE accepts NULL string. */
1107 if (BE (cur_state->halt, 0))
1109 if (!cur_state->has_constraint
1110 || check_halt_state_context (mctx, cur_state, cur_str_idx))
1112 if (!fl_longest_match)
1116 match_last = cur_str_idx;
1122 while (!re_string_eoi (&mctx->input))
1124 re_dfastate_t *old_state = cur_state;
1125 Idx next_char_idx = re_string_cur_idx (&mctx->input) + 1;
1127 if (BE (next_char_idx >= mctx->input.bufs_len, 0)
1128 || (BE (next_char_idx >= mctx->input.valid_len, 0)
1129 && mctx->input.valid_len < mctx->input.len))
1131 err = extend_buffers (mctx);
1132 if (BE (err != REG_NOERROR, 0))
1134 assert (err == REG_ESPACE);
1139 cur_state = transit_state (&err, mctx, cur_state);
1140 if (mctx->state_log != NULL)
1141 cur_state = merge_state_with_log (&err, mctx, cur_state);
1143 if (cur_state == NULL)
1145 /* Reached the invalid state or an error. Try to recover a valid
1146 state using the state log, if available and if we have not
1147 already found a valid (even if not the longest) match. */
1148 if (BE (err != REG_NOERROR, 0))
1151 if (mctx->state_log == NULL
1152 || (match && !fl_longest_match)
1153 || (cur_state = find_recover_state (&err, mctx)) == NULL)
1157 if (BE (at_init_state, 0))
1159 if (old_state == cur_state)
1160 next_start_idx = next_char_idx;
1162 at_init_state = false;
1165 if (cur_state->halt)
1167 /* Reached a halt state.
1168 Check the halt state can satisfy the current context. */
1169 if (!cur_state->has_constraint
1170 || check_halt_state_context (mctx, cur_state,
1171 re_string_cur_idx (&mctx->input)))
1173 /* We found an appropriate halt state. */
1174 match_last = re_string_cur_idx (&mctx->input);
1177 /* We found a match, do not modify match_first below. */
1178 p_match_first = NULL;
1179 if (!fl_longest_match)
1186 *p_match_first += next_start_idx;
1191 /* Check NODE match the current context. */
1195 check_halt_node_context (const re_dfa_t *dfa, Idx node, unsigned int context)
1197 re_token_type_t type = dfa->nodes[node].type;
1198 unsigned int constraint = dfa->nodes[node].constraint;
1199 if (type != END_OF_RE)
1203 if (NOT_SATISFY_NEXT_CONSTRAINT (constraint, context))
1208 /* Check the halt state STATE match the current context.
1209 Return 0 if not match, if the node, STATE has, is a halt node and
1210 match the context, return the node. */
1214 check_halt_state_context (const re_match_context_t *mctx,
1215 const re_dfastate_t *state, Idx idx)
1218 unsigned int context;
1220 assert (state->halt);
1222 context = re_string_context_at (&mctx->input, idx, mctx->eflags);
1223 for (i = 0; i < state->nodes.nelem; ++i)
1224 if (check_halt_node_context (mctx->dfa, state->nodes.elems[i], context))
1225 return state->nodes.elems[i];
1229 /* Compute the next node to which "NFA" transit from NODE("NFA" is a NFA
1230 corresponding to the DFA).
1231 Return the destination node, and update EPS_VIA_NODES;
1232 return REG_MISSING in case of errors. */
1236 proceed_next_node (const re_match_context_t *mctx,
1237 Idx nregs, regmatch_t *regs, Idx *pidx, Idx node,
1238 re_node_set *eps_via_nodes, struct re_fail_stack_t *fs)
1240 re_dfa_t *const dfa = mctx->dfa;
1243 if (IS_EPSILON_NODE (dfa->nodes[node].type))
1245 re_node_set *cur_nodes = &mctx->state_log[*pidx]->nodes;
1246 re_node_set *edests = &dfa->edests[node];
1248 ok = re_node_set_insert (eps_via_nodes, node);
1251 /* Pick up a valid destination, or return REG_MISSING if none
1253 for (dest_node = REG_MISSING, i = 0; i < edests->nelem; ++i)
1255 Idx candidate = edests->elems[i];
1256 if (!re_node_set_contains (cur_nodes, candidate))
1258 if (dest_node == REG_MISSING)
1259 dest_node = candidate;
1263 /* In order to avoid infinite loop like "(a*)*", return the second
1264 epsilon-transition if the first was already considered. */
1265 if (re_node_set_contains (eps_via_nodes, dest_node))
1268 /* Otherwise, push the second epsilon-transition on the fail stack. */
1270 && push_fail_stack (fs, *pidx, candidate, nregs, regs,
1274 /* We know we are going to exit. */
1283 re_token_type_t type = dfa->nodes[node].type;
1285 #ifdef RE_ENABLE_I18N
1286 if (dfa->nodes[node].accept_mb)
1287 naccepted = check_node_accept_bytes (dfa, node, &mctx->input, *pidx);
1289 #endif /* RE_ENABLE_I18N */
1290 if (type == OP_BACK_REF)
1292 Idx subexp_idx = dfa->nodes[node].opr.idx + 1;
1293 naccepted = regs[subexp_idx].rm_eo - regs[subexp_idx].rm_so;
1296 if (regs[subexp_idx].rm_so == -1 || regs[subexp_idx].rm_eo == -1)
1300 char *buf = (char *) re_string_get_buffer (&mctx->input);
1301 if (memcmp (buf + regs[subexp_idx].rm_so, buf + *pidx,
1310 ok = re_node_set_insert (eps_via_nodes, node);
1313 dest_node = dfa->edests[node].elems[0];
1314 if (re_node_set_contains (&mctx->state_log[*pidx]->nodes,
1321 || check_node_accept (mctx, dfa->nodes + node, *pidx))
1323 Idx dest_node = dfa->nexts[node];
1324 *pidx = (naccepted == 0) ? *pidx + 1 : *pidx + naccepted;
1325 if (fs && (*pidx > mctx->match_last || mctx->state_log[*pidx] == NULL
1326 || !re_node_set_contains (&mctx->state_log[*pidx]->nodes,
1329 re_node_set_empty (eps_via_nodes);
1336 static reg_errcode_t
1338 push_fail_stack (struct re_fail_stack_t *fs, Idx str_idx, Idx dest_node,
1339 Idx nregs, regmatch_t *regs, re_node_set *eps_via_nodes)
1342 Idx num = fs->num++;
1343 if (fs->num == fs->alloc)
1345 struct re_fail_stack_ent_t *new_array =
1346 re_realloc (fs->stack, struct re_fail_stack_ent_t, fs->alloc * 2);
1347 if (new_array == NULL)
1350 fs->stack = new_array;
1352 fs->stack[num].idx = str_idx;
1353 fs->stack[num].node = dest_node;
1354 fs->stack[num].regs = re_malloc (regmatch_t, nregs);
1355 if (fs->stack[num].regs == NULL)
1357 memcpy (fs->stack[num].regs, regs, sizeof (regmatch_t) * nregs);
1358 err = re_node_set_init_copy (&fs->stack[num].eps_via_nodes, eps_via_nodes);
1364 pop_fail_stack (struct re_fail_stack_t *fs, Idx *pidx,
1365 Idx nregs, regmatch_t *regs, re_node_set *eps_via_nodes)
1367 Idx num = --fs->num;
1368 assert (REG_VALID_INDEX (num));
1369 *pidx = fs->stack[num].idx;
1370 memcpy (regs, fs->stack[num].regs, sizeof (regmatch_t) * nregs);
1371 re_node_set_free (eps_via_nodes);
1372 re_free (fs->stack[num].regs);
1373 *eps_via_nodes = fs->stack[num].eps_via_nodes;
1374 return fs->stack[num].node;
1377 /* Set the positions where the subexpressions are starts/ends to registers
1379 Note: We assume that pmatch[0] is already set, and
1380 pmatch[i].rm_so == pmatch[i].rm_eo == -1 for 0 < i < nmatch. */
1382 static reg_errcode_t
1384 set_regs (const regex_t *preg, const re_match_context_t *mctx,
1385 size_t nmatch, regmatch_t *pmatch, bool fl_backtrack)
1387 re_dfa_t *dfa = (re_dfa_t *) preg->re_buffer;
1389 re_node_set eps_via_nodes;
1390 struct re_fail_stack_t *fs;
1391 struct re_fail_stack_t fs_body = { 0, 2, NULL };
1392 regmatch_t *prev_idx_match;
1393 bool prev_idx_match_malloced = false;
1396 assert (nmatch > 1);
1397 assert (mctx->state_log != NULL);
1402 fs->stack = re_malloc (struct re_fail_stack_ent_t, fs->alloc);
1403 if (fs->stack == NULL)
1409 cur_node = dfa->init_node;
1410 re_node_set_init_empty (&eps_via_nodes);
1412 if (__libc_use_alloca (nmatch * sizeof (regmatch_t)))
1413 prev_idx_match = (regmatch_t *) alloca (nmatch * sizeof (regmatch_t));
1416 prev_idx_match = re_malloc (regmatch_t, nmatch);
1417 if (prev_idx_match == NULL)
1419 free_fail_stack_return (fs);
1422 prev_idx_match_malloced = true;
1424 memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
1426 for (idx = pmatch[0].rm_so; idx <= pmatch[0].rm_eo ;)
1428 update_regs (dfa, pmatch, prev_idx_match, cur_node, idx, nmatch);
1430 if (idx == pmatch[0].rm_eo && cur_node == mctx->last_node)
1435 for (reg_idx = 0; reg_idx < nmatch; ++reg_idx)
1436 if (pmatch[reg_idx].rm_so > -1 && pmatch[reg_idx].rm_eo == -1)
1438 if (reg_idx == nmatch)
1440 re_node_set_free (&eps_via_nodes);
1441 if (prev_idx_match_malloced)
1442 re_free (prev_idx_match);
1443 return free_fail_stack_return (fs);
1445 cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
1450 re_node_set_free (&eps_via_nodes);
1451 if (prev_idx_match_malloced)
1452 re_free (prev_idx_match);
1457 /* Proceed to next node. */
1458 cur_node = proceed_next_node (mctx, nmatch, pmatch, &idx, cur_node,
1459 &eps_via_nodes, fs);
1461 if (BE (! REG_VALID_INDEX (cur_node), 0))
1463 if (BE (cur_node == REG_ERROR, 0))
1465 re_node_set_free (&eps_via_nodes);
1466 if (prev_idx_match_malloced)
1467 re_free (prev_idx_match);
1468 free_fail_stack_return (fs);
1472 cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
1476 re_node_set_free (&eps_via_nodes);
1477 if (prev_idx_match_malloced)
1478 re_free (prev_idx_match);
1483 re_node_set_free (&eps_via_nodes);
1484 if (prev_idx_match_malloced)
1485 re_free (prev_idx_match);
1486 return free_fail_stack_return (fs);
1489 static reg_errcode_t
1491 free_fail_stack_return (struct re_fail_stack_t *fs)
1496 for (fs_idx = 0; fs_idx < fs->num; ++fs_idx)
1498 re_node_set_free (&fs->stack[fs_idx].eps_via_nodes);
1499 re_free (fs->stack[fs_idx].regs);
1501 re_free (fs->stack);
1508 update_regs (re_dfa_t *dfa, regmatch_t *pmatch, regmatch_t *prev_idx_match,
1509 Idx cur_node, Idx cur_idx, Idx nmatch)
1511 int type = dfa->nodes[cur_node].type;
1512 if (type == OP_OPEN_SUBEXP)
1514 Idx reg_num = dfa->nodes[cur_node].opr.idx + 1;
1516 /* We are at the first node of this sub expression. */
1517 if (reg_num < nmatch)
1519 pmatch[reg_num].rm_so = cur_idx;
1520 pmatch[reg_num].rm_eo = -1;
1523 else if (type == OP_CLOSE_SUBEXP)
1525 Idx reg_num = dfa->nodes[cur_node].opr.idx + 1;
1526 if (reg_num < nmatch)
1528 /* We are at the last node of this sub expression. */
1529 if (pmatch[reg_num].rm_so < cur_idx)
1531 pmatch[reg_num].rm_eo = cur_idx;
1532 /* This is a non-empty match or we are not inside an optional
1533 subexpression. Accept this right away. */
1534 memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
1538 if (dfa->nodes[cur_node].opt_subexp
1539 && prev_idx_match[reg_num].rm_so != -1)
1540 /* We transited through an empty match for an optional
1541 subexpression, like (a?)*, and this is not the subexp's
1542 first match. Copy back the old content of the registers
1543 so that matches of an inner subexpression are undone as
1544 well, like in ((a?))*. */
1545 memcpy (pmatch, prev_idx_match, sizeof (regmatch_t) * nmatch);
1547 /* We completed a subexpression, but it may be part of
1548 an optional one, so do not update PREV_IDX_MATCH. */
1549 pmatch[reg_num].rm_eo = cur_idx;
1555 /* This function checks the STATE_LOG from the SCTX->last_str_idx to 0
1556 and sift the nodes in each states according to the following rules.
1557 Updated state_log will be wrote to STATE_LOG.
1559 Rules: We throw away the Node `a' in the STATE_LOG[STR_IDX] if...
1560 1. When STR_IDX == MATCH_LAST(the last index in the state_log):
1561 If `a' isn't the LAST_NODE and `a' can't epsilon transit to
1562 the LAST_NODE, we throw away the node `a'.
1563 2. When 0 <= STR_IDX < MATCH_LAST and `a' accepts
1564 string `s' and transit to `b':
1565 i. If 'b' isn't in the STATE_LOG[STR_IDX+strlen('s')], we throw
1567 ii. If 'b' is in the STATE_LOG[STR_IDX+strlen('s')] but 'b' is
1568 thrown away, we throw away the node `a'.
1569 3. When 0 <= STR_IDX < MATCH_LAST and 'a' epsilon transit to 'b':
1570 i. If 'b' isn't in the STATE_LOG[STR_IDX], we throw away the
1572 ii. If 'b' is in the STATE_LOG[STR_IDX] but 'b' is thrown away,
1573 we throw away the node `a'. */
1575 #define STATE_NODE_CONTAINS(state,node) \
1576 ((state) != NULL && re_node_set_contains (&(state)->nodes, node))
1578 static reg_errcode_t
1580 sift_states_backward (re_match_context_t *mctx, re_sift_context_t *sctx)
1584 Idx str_idx = sctx->last_str_idx;
1585 re_node_set cur_dest;
1588 assert (mctx->state_log != NULL && mctx->state_log[str_idx] != NULL);
1591 /* Build sifted state_log[str_idx]. It has the nodes which can epsilon
1592 transit to the last_node and the last_node itself. */
1593 err = re_node_set_init_1 (&cur_dest, sctx->last_node);
1594 if (BE (err != REG_NOERROR, 0))
1596 err = update_cur_sifted_state (mctx, sctx, str_idx, &cur_dest);
1597 if (BE (err != REG_NOERROR, 0))
1600 /* Then check each states in the state_log. */
1603 /* Update counters. */
1604 null_cnt = (sctx->sifted_states[str_idx] == NULL) ? null_cnt + 1 : 0;
1605 if (null_cnt > mctx->max_mb_elem_len)
1607 memset (sctx->sifted_states, '\0',
1608 sizeof (re_dfastate_t *) * str_idx);
1609 re_node_set_free (&cur_dest);
1612 re_node_set_empty (&cur_dest);
1615 if (mctx->state_log[str_idx])
1617 err = build_sifted_states (mctx, sctx, str_idx, &cur_dest);
1618 if (BE (err != REG_NOERROR, 0))
1622 /* Add all the nodes which satisfy the following conditions:
1623 - It can epsilon transit to a node in CUR_DEST.
1625 And update state_log. */
1626 err = update_cur_sifted_state (mctx, sctx, str_idx, &cur_dest);
1627 if (BE (err != REG_NOERROR, 0))
1632 re_node_set_free (&cur_dest);
1636 static reg_errcode_t
1638 build_sifted_states (re_match_context_t *mctx, re_sift_context_t *sctx,
1639 Idx str_idx, re_node_set *cur_dest)
1641 re_dfa_t *const dfa = mctx->dfa;
1642 re_node_set *cur_src = &mctx->state_log[str_idx]->non_eps_nodes;
1645 /* Then build the next sifted state.
1646 We build the next sifted state on `cur_dest', and update
1647 `sifted_states[str_idx]' with `cur_dest'.
1649 `cur_dest' is the sifted state from `state_log[str_idx + 1]'.
1650 `cur_src' points the node_set of the old `state_log[str_idx]'
1651 (with the epsilon nodes pre-filtered out). */
1652 for (i = 0; i < cur_src->nelem; i++)
1654 Idx prev_node = cur_src->elems[i];
1659 re_token_type_t type = dfa->nodes[prev_node].type;
1660 assert (!IS_EPSILON_NODE (type));
1662 #ifdef RE_ENABLE_I18N
1663 /* If the node may accept `multi byte'. */
1664 if (dfa->nodes[prev_node].accept_mb)
1665 naccepted = sift_states_iter_mb (mctx, sctx, prev_node,
1666 str_idx, sctx->last_str_idx);
1667 #endif /* RE_ENABLE_I18N */
1669 /* We don't check backreferences here.
1670 See update_cur_sifted_state(). */
1672 && check_node_accept (mctx, dfa->nodes + prev_node, str_idx)
1673 && STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + 1],
1674 dfa->nexts[prev_node]))
1680 if (sctx->limits.nelem)
1682 Idx to_idx = str_idx + naccepted;
1683 if (check_dst_limits (mctx, &sctx->limits,
1684 dfa->nexts[prev_node], to_idx,
1685 prev_node, str_idx))
1688 ok = re_node_set_insert (cur_dest, prev_node);
1696 /* Helper functions. */
1698 static reg_errcode_t
1700 clean_state_log_if_needed (re_match_context_t *mctx, Idx next_state_log_idx)
1702 Idx top = mctx->state_log_top;
1704 if (next_state_log_idx >= mctx->input.bufs_len
1705 || (next_state_log_idx >= mctx->input.valid_len
1706 && mctx->input.valid_len < mctx->input.len))
1709 err = extend_buffers (mctx);
1710 if (BE (err != REG_NOERROR, 0))
1714 if (top < next_state_log_idx)
1716 memset (mctx->state_log + top + 1, '\0',
1717 sizeof (re_dfastate_t *) * (next_state_log_idx - top));
1718 mctx->state_log_top = next_state_log_idx;
1723 static reg_errcode_t
1725 merge_state_array (re_dfa_t *dfa, re_dfastate_t **dst, re_dfastate_t **src,
1730 for (st_idx = 0; st_idx < num; ++st_idx)
1732 if (dst[st_idx] == NULL)
1733 dst[st_idx] = src[st_idx];
1734 else if (src[st_idx] != NULL)
1736 re_node_set merged_set;
1737 err = re_node_set_init_union (&merged_set, &dst[st_idx]->nodes,
1738 &src[st_idx]->nodes);
1739 if (BE (err != REG_NOERROR, 0))
1741 dst[st_idx] = re_acquire_state (&err, dfa, &merged_set);
1742 re_node_set_free (&merged_set);
1743 if (BE (err != REG_NOERROR, 0))
1750 static reg_errcode_t
1752 update_cur_sifted_state (re_match_context_t *mctx, re_sift_context_t *sctx,
1753 Idx str_idx, re_node_set *dest_nodes)
1755 re_dfa_t *const dfa = mctx->dfa;
1757 const re_node_set *candidates;
1758 candidates = ((mctx->state_log[str_idx] == NULL) ? NULL
1759 : &mctx->state_log[str_idx]->nodes);
1761 if (dest_nodes->nelem == 0)
1762 sctx->sifted_states[str_idx] = NULL;
1767 /* At first, add the nodes which can epsilon transit to a node in
1769 err = add_epsilon_src_nodes (dfa, dest_nodes, candidates);
1770 if (BE (err != REG_NOERROR, 0))
1773 /* Then, check the limitations in the current sift_context. */
1774 if (sctx->limits.nelem)
1776 err = check_subexp_limits (dfa, dest_nodes, candidates, &sctx->limits,
1777 mctx->bkref_ents, str_idx);
1778 if (BE (err != REG_NOERROR, 0))
1783 sctx->sifted_states[str_idx] = re_acquire_state (&err, dfa, dest_nodes);
1784 if (BE (err != REG_NOERROR, 0))
1788 if (candidates && mctx->state_log[str_idx]->has_backref)
1790 err = sift_states_bkref (mctx, sctx, str_idx, candidates);
1791 if (BE (err != REG_NOERROR, 0))
1797 static reg_errcode_t
1799 add_epsilon_src_nodes (re_dfa_t *dfa, re_node_set *dest_nodes,
1800 const re_node_set *candidates)
1802 reg_errcode_t err = REG_NOERROR;
1805 re_dfastate_t *state = re_acquire_state (&err, dfa, dest_nodes);
1806 if (BE (err != REG_NOERROR, 0))
1809 if (!state->inveclosure.alloc)
1811 err = re_node_set_alloc (&state->inveclosure, dest_nodes->nelem);
1812 if (BE (err != REG_NOERROR, 0))
1814 for (i = 0; i < dest_nodes->nelem; i++)
1815 re_node_set_merge (&state->inveclosure,
1816 dfa->inveclosures + dest_nodes->elems[i]);
1818 return re_node_set_add_intersect (dest_nodes, candidates,
1819 &state->inveclosure);
1822 static reg_errcode_t
1824 sub_epsilon_src_nodes (re_dfa_t *dfa, Idx node, re_node_set *dest_nodes,
1825 const re_node_set *candidates)
1829 re_node_set *inv_eclosure = dfa->inveclosures + node;
1830 re_node_set except_nodes;
1831 re_node_set_init_empty (&except_nodes);
1832 for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx)
1834 Idx cur_node = inv_eclosure->elems[ecl_idx];
1835 if (cur_node == node)
1837 if (IS_EPSILON_NODE (dfa->nodes[cur_node].type))
1839 Idx edst1 = dfa->edests[cur_node].elems[0];
1840 Idx edst2 = ((dfa->edests[cur_node].nelem > 1)
1841 ? dfa->edests[cur_node].elems[1] : REG_MISSING);
1842 if ((!re_node_set_contains (inv_eclosure, edst1)
1843 && re_node_set_contains (dest_nodes, edst1))
1844 || (REG_VALID_NONZERO_INDEX (edst2)
1845 && !re_node_set_contains (inv_eclosure, edst2)
1846 && re_node_set_contains (dest_nodes, edst2)))
1848 err = re_node_set_add_intersect (&except_nodes, candidates,
1849 dfa->inveclosures + cur_node);
1850 if (BE (err != REG_NOERROR, 0))
1852 re_node_set_free (&except_nodes);
1858 for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx)
1860 Idx cur_node = inv_eclosure->elems[ecl_idx];
1861 if (!re_node_set_contains (&except_nodes, cur_node))
1863 Idx idx = re_node_set_contains (dest_nodes, cur_node) - 1;
1864 re_node_set_remove_at (dest_nodes, idx);
1867 re_node_set_free (&except_nodes);
1873 check_dst_limits (const re_match_context_t *mctx, const re_node_set *limits,
1874 Idx dst_node, Idx dst_idx, Idx src_node, Idx src_idx)
1876 re_dfa_t *const dfa = mctx->dfa;
1877 Idx lim_idx, src_pos, dst_pos;
1879 Idx dst_bkref_idx = search_cur_bkref_entry (mctx, dst_idx);
1880 Idx src_bkref_idx = search_cur_bkref_entry (mctx, src_idx);
1881 for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx)
1884 struct re_backref_cache_entry *ent;
1885 ent = mctx->bkref_ents + limits->elems[lim_idx];
1886 subexp_idx = dfa->nodes[ent->node].opr.idx;
1888 dst_pos = check_dst_limits_calc_pos (mctx, limits->elems[lim_idx],
1889 subexp_idx, dst_node, dst_idx,
1891 src_pos = check_dst_limits_calc_pos (mctx, limits->elems[lim_idx],
1892 subexp_idx, src_node, src_idx,
1896 <src> <dst> ( <subexp> )
1897 ( <subexp> ) <src> <dst>
1898 ( <subexp1> <src> <subexp2> <dst> <subexp3> ) */
1899 if (src_pos == dst_pos)
1900 continue; /* This is unrelated limitation. */
1909 check_dst_limits_calc_pos_1 (const re_match_context_t *mctx, int boundaries,
1910 Idx subexp_idx, Idx from_node, Idx bkref_idx)
1912 re_dfa_t *const dfa = mctx->dfa;
1913 re_node_set *eclosures = dfa->eclosures + from_node;
1916 /* Else, we are on the boundary: examine the nodes on the epsilon
1918 for (node_idx = 0; node_idx < eclosures->nelem; ++node_idx)
1920 Idx node = eclosures->elems[node_idx];
1921 switch (dfa->nodes[node].type)
1924 if (bkref_idx != REG_MISSING)
1926 struct re_backref_cache_entry *ent = mctx->bkref_ents + bkref_idx;
1932 if (ent->node != node)
1936 < CHAR_BIT * sizeof ent->eps_reachable_subexps_map
1937 && !(ent->eps_reachable_subexps_map & (1u << subexp_idx)))
1940 /* Recurse trying to reach the OP_OPEN_SUBEXP and
1941 OP_CLOSE_SUBEXP cases below. But, if the
1942 destination node is the same node as the source
1943 node, don't recurse because it would cause an
1944 infinite loop: a regex that exhibits this behavior
1946 dst = dfa->edests[node].elems[0];
1947 if (dst == from_node)
1951 else /* if (boundaries & 2) */
1956 check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx,
1958 if (cpos == -1 /* && (boundaries & 1) */)
1960 if (cpos == 0 && (boundaries & 2))
1964 < CHAR_BIT * sizeof ent->eps_reachable_subexps_map)
1965 ent->eps_reachable_subexps_map &= ~(1u << subexp_idx);
1967 while (ent++->more);
1971 case OP_OPEN_SUBEXP:
1972 if ((boundaries & 1) && subexp_idx == dfa->nodes[node].opr.idx)
1976 case OP_CLOSE_SUBEXP:
1977 if ((boundaries & 2) && subexp_idx == dfa->nodes[node].opr.idx)
1986 return (boundaries & 2) ? 1 : 0;
1991 check_dst_limits_calc_pos (const re_match_context_t *mctx,
1992 Idx limit, Idx subexp_idx,
1993 Idx from_node, Idx str_idx, Idx bkref_idx)
1995 struct re_backref_cache_entry *lim = mctx->bkref_ents + limit;
1998 /* If we are outside the range of the subexpression, return -1 or 1. */
1999 if (str_idx < lim->subexp_from)
2002 if (lim->subexp_to < str_idx)
2005 /* If we are within the subexpression, return 0. */
2006 boundaries = (str_idx == lim->subexp_from);
2007 boundaries |= (str_idx == lim->subexp_to) << 1;
2008 if (boundaries == 0)
2011 /* Else, examine epsilon closure. */
2012 return check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx,
2013 from_node, bkref_idx);
2016 /* Check the limitations of sub expressions LIMITS, and remove the nodes
2017 which are against limitations from DEST_NODES. */
2019 static reg_errcode_t
2021 check_subexp_limits (re_dfa_t *dfa, re_node_set *dest_nodes,
2022 const re_node_set *candidates, re_node_set *limits,
2023 struct re_backref_cache_entry *bkref_ents, Idx str_idx)
2026 Idx node_idx, lim_idx;
2028 for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx)
2031 struct re_backref_cache_entry *ent;
2032 ent = bkref_ents + limits->elems[lim_idx];
2034 if (str_idx <= ent->subexp_from || ent->str_idx < str_idx)
2035 continue; /* This is unrelated limitation. */
2037 subexp_idx = dfa->nodes[ent->node].opr.idx;
2038 if (ent->subexp_to == str_idx)
2040 Idx ops_node = REG_MISSING;
2041 Idx cls_node = REG_MISSING;
2042 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2044 Idx node = dest_nodes->elems[node_idx];
2045 re_token_type_t type = dfa->nodes[node].type;
2046 if (type == OP_OPEN_SUBEXP
2047 && subexp_idx == dfa->nodes[node].opr.idx)
2049 else if (type == OP_CLOSE_SUBEXP
2050 && subexp_idx == dfa->nodes[node].opr.idx)
2054 /* Check the limitation of the open subexpression. */
2055 /* Note that (ent->subexp_to = str_idx != ent->subexp_from). */
2056 if (REG_VALID_INDEX (ops_node))
2058 err = sub_epsilon_src_nodes (dfa, ops_node, dest_nodes,
2060 if (BE (err != REG_NOERROR, 0))
2064 /* Check the limitation of the close subexpression. */
2065 if (REG_VALID_INDEX (cls_node))
2066 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2068 Idx node = dest_nodes->elems[node_idx];
2069 if (!re_node_set_contains (dfa->inveclosures + node,
2071 && !re_node_set_contains (dfa->eclosures + node,
2074 /* It is against this limitation.
2075 Remove it form the current sifted state. */
2076 err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2078 if (BE (err != REG_NOERROR, 0))
2084 else /* (ent->subexp_to != str_idx) */
2086 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2088 Idx node = dest_nodes->elems[node_idx];
2089 re_token_type_t type = dfa->nodes[node].type;
2090 if (type == OP_CLOSE_SUBEXP || type == OP_OPEN_SUBEXP)
2092 if (subexp_idx != dfa->nodes[node].opr.idx)
2094 /* It is against this limitation.
2095 Remove it form the current sifted state. */
2096 err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2098 if (BE (err != REG_NOERROR, 0))
2107 static reg_errcode_t
2109 sift_states_bkref (re_match_context_t *mctx, re_sift_context_t *sctx,
2110 Idx str_idx, const re_node_set *candidates)
2112 re_dfa_t *const dfa = mctx->dfa;
2115 re_sift_context_t local_sctx;
2116 Idx first_idx = search_cur_bkref_entry (mctx, str_idx);
2118 if (first_idx == REG_MISSING)
2121 local_sctx.sifted_states = NULL; /* Mark that it hasn't been initialized. */
2123 for (node_idx = 0; node_idx < candidates->nelem; ++node_idx)
2126 re_token_type_t type;
2127 struct re_backref_cache_entry *entry;
2128 node = candidates->elems[node_idx];
2129 type = dfa->nodes[node].type;
2130 /* Avoid infinite loop for the REs like "()\1+". */
2131 if (node == sctx->last_node && str_idx == sctx->last_str_idx)
2133 if (type != OP_BACK_REF)
2136 entry = mctx->bkref_ents + first_idx;
2137 enabled_idx = first_idx;
2141 Idx subexp_len, to_idx, dst_node;
2142 re_dfastate_t *cur_state;
2144 if (entry->node != node)
2146 subexp_len = entry->subexp_to - entry->subexp_from;
2147 to_idx = str_idx + subexp_len;
2148 dst_node = (subexp_len ? dfa->nexts[node]
2149 : dfa->edests[node].elems[0]);
2151 if (to_idx > sctx->last_str_idx
2152 || sctx->sifted_states[to_idx] == NULL
2153 || !STATE_NODE_CONTAINS (sctx->sifted_states[to_idx], dst_node)
2154 || check_dst_limits (mctx, &sctx->limits, node,
2155 str_idx, dst_node, to_idx))
2158 if (local_sctx.sifted_states == NULL)
2161 err = re_node_set_init_copy (&local_sctx.limits, &sctx->limits);
2162 if (BE (err != REG_NOERROR, 0))
2165 local_sctx.last_node = node;
2166 local_sctx.last_str_idx = str_idx;
2167 ok = re_node_set_insert (&local_sctx.limits, enabled_idx);
2173 cur_state = local_sctx.sifted_states[str_idx];
2174 err = sift_states_backward (mctx, &local_sctx);
2175 if (BE (err != REG_NOERROR, 0))
2177 if (sctx->limited_states != NULL)
2179 err = merge_state_array (dfa, sctx->limited_states,
2180 local_sctx.sifted_states,
2182 if (BE (err != REG_NOERROR, 0))
2185 local_sctx.sifted_states[str_idx] = cur_state;
2186 re_node_set_remove (&local_sctx.limits, enabled_idx);
2188 /* mctx->bkref_ents may have changed, reload the pointer. */
2189 entry = mctx->bkref_ents + enabled_idx;
2191 while (enabled_idx++, entry++->more);
2195 if (local_sctx.sifted_states != NULL)
2197 re_node_set_free (&local_sctx.limits);
2204 #ifdef RE_ENABLE_I18N
2207 sift_states_iter_mb (const re_match_context_t *mctx, re_sift_context_t *sctx,
2208 Idx node_idx, Idx str_idx, Idx max_str_idx)
2210 re_dfa_t *const dfa = mctx->dfa;
2212 /* Check the node can accept `multi byte'. */
2213 naccepted = check_node_accept_bytes (dfa, node_idx, &mctx->input, str_idx);
2214 if (naccepted > 0 && str_idx + naccepted <= max_str_idx &&
2215 !STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + naccepted],
2216 dfa->nexts[node_idx]))
2217 /* The node can't accept the `multi byte', or the
2218 destination was already thrown away, then the node
2219 could't accept the current input `multi byte'. */
2221 /* Otherwise, it is sure that the node could accept
2222 `naccepted' bytes input. */
2225 #endif /* RE_ENABLE_I18N */
2228 /* Functions for state transition. */
2230 /* Return the next state to which the current state STATE will transit by
2231 accepting the current input byte, and update STATE_LOG if necessary.
2232 If STATE can accept a multibyte char/collating element/back reference
2233 update the destination of STATE_LOG. */
2235 static re_dfastate_t *
2237 transit_state (reg_errcode_t *err, re_match_context_t *mctx,
2238 re_dfastate_t *state)
2240 re_dfastate_t **trtable;
2243 #ifdef RE_ENABLE_I18N
2244 /* If the current state can accept multibyte. */
2245 if (BE (state->accept_mb, 0))
2247 *err = transit_state_mb (mctx, state);
2248 if (BE (*err != REG_NOERROR, 0))
2251 #endif /* RE_ENABLE_I18N */
2253 /* Then decide the next state with the single byte. */
2256 /* don't use transition table */
2257 return transit_state_sb (err, mctx, state);
2260 /* Use transition table */
2261 ch = re_string_fetch_byte (&mctx->input);
2264 trtable = state->trtable;
2265 if (BE (trtable != NULL, 1))
2268 trtable = state->word_trtable;
2269 if (BE (trtable != NULL, 1))
2271 unsigned int context;
2273 = re_string_context_at (&mctx->input,
2274 re_string_cur_idx (&mctx->input) - 1,
2276 if (IS_WORD_CONTEXT (context))
2277 return trtable[ch + SBC_MAX];
2282 if (!build_trtable (mctx->dfa, state))
2288 /* Retry, we now have a transition table. */
2292 /* Update the state_log if we need */
2295 merge_state_with_log (reg_errcode_t *err, re_match_context_t *mctx,
2296 re_dfastate_t *next_state)
2298 re_dfa_t *const dfa = mctx->dfa;
2299 Idx cur_idx = re_string_cur_idx (&mctx->input);
2301 if (cur_idx > mctx->state_log_top)
2303 mctx->state_log[cur_idx] = next_state;
2304 mctx->state_log_top = cur_idx;
2306 else if (mctx->state_log[cur_idx] == 0)
2308 mctx->state_log[cur_idx] = next_state;
2312 re_dfastate_t *pstate;
2313 unsigned int context;
2314 re_node_set next_nodes, *log_nodes, *table_nodes = NULL;
2315 /* If (state_log[cur_idx] != 0), it implies that cur_idx is
2316 the destination of a multibyte char/collating element/
2317 back reference. Then the next state is the union set of
2318 these destinations and the results of the transition table. */
2319 pstate = mctx->state_log[cur_idx];
2320 log_nodes = pstate->entrance_nodes;
2321 if (next_state != NULL)
2323 table_nodes = next_state->entrance_nodes;
2324 *err = re_node_set_init_union (&next_nodes, table_nodes,
2326 if (BE (*err != REG_NOERROR, 0))
2330 next_nodes = *log_nodes;
2331 /* Note: We already add the nodes of the initial state,
2332 then we don't need to add them here. */
2334 context = re_string_context_at (&mctx->input,
2335 re_string_cur_idx (&mctx->input) - 1,
2337 next_state = mctx->state_log[cur_idx]
2338 = re_acquire_state_context (err, dfa, &next_nodes, context);
2339 /* We don't need to check errors here, since the return value of
2340 this function is next_state and ERR is already set. */
2342 if (table_nodes != NULL)
2343 re_node_set_free (&next_nodes);
2346 if (BE (dfa->nbackref, 0) && next_state != NULL)
2348 /* Check OP_OPEN_SUBEXP in the current state in case that we use them
2349 later. We must check them here, since the back references in the
2350 next state might use them. */
2351 *err = check_subexp_matching_top (mctx, &next_state->nodes,
2353 if (BE (*err != REG_NOERROR, 0))
2356 /* If the next state has back references. */
2357 if (next_state->has_backref)
2359 *err = transit_state_bkref (mctx, &next_state->nodes);
2360 if (BE (*err != REG_NOERROR, 0))
2362 next_state = mctx->state_log[cur_idx];
2369 /* Skip bytes in the input that correspond to part of a
2370 multi-byte match, then look in the log for a state
2371 from which to restart matching. */
2372 static re_dfastate_t *
2374 find_recover_state (reg_errcode_t *err, re_match_context_t *mctx)
2376 re_dfastate_t *cur_state = NULL;
2379 Idx max = mctx->state_log_top;
2380 Idx cur_str_idx = re_string_cur_idx (&mctx->input);
2384 if (++cur_str_idx > max)
2386 re_string_skip_bytes (&mctx->input, 1);
2388 while (mctx->state_log[cur_str_idx] == NULL);
2390 cur_state = merge_state_with_log (err, mctx, NULL);
2392 while (*err == REG_NOERROR && cur_state == NULL);
2396 /* Helper functions for transit_state. */
2398 /* From the node set CUR_NODES, pick up the nodes whose types are
2399 OP_OPEN_SUBEXP and which have corresponding back references in the regular
2400 expression. And register them to use them later for evaluating the
2401 correspoding back references. */
2403 static reg_errcode_t
2405 check_subexp_matching_top (re_match_context_t *mctx, re_node_set *cur_nodes,
2408 re_dfa_t *const dfa = mctx->dfa;
2412 /* TODO: This isn't efficient.
2413 Because there might be more than one nodes whose types are
2414 OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
2417 for (node_idx = 0; node_idx < cur_nodes->nelem; ++node_idx)
2419 Idx node = cur_nodes->elems[node_idx];
2420 if (dfa->nodes[node].type == OP_OPEN_SUBEXP
2421 && dfa->nodes[node].opr.idx < CHAR_BIT * sizeof dfa->used_bkref_map
2422 && dfa->used_bkref_map & (1u << dfa->nodes[node].opr.idx))
2424 err = match_ctx_add_subtop (mctx, node, str_idx);
2425 if (BE (err != REG_NOERROR, 0))
2433 /* Return the next state to which the current state STATE will transit by
2434 accepting the current input byte. */
2436 static re_dfastate_t *
2437 transit_state_sb (reg_errcode_t *err, re_match_context_t *mctx,
2438 re_dfastate_t *state)
2440 re_dfa_t *const dfa = mctx->dfa;
2441 re_node_set next_nodes;
2442 re_dfastate_t *next_state;
2443 Idx node_cnt, cur_str_idx = re_string_cur_idx (&mctx->input);
2444 unsigned int context;
2446 *err = re_node_set_alloc (&next_nodes, state->nodes.nelem + 1);
2447 if (BE (*err != REG_NOERROR, 0))
2449 for (node_cnt = 0; node_cnt < state->nodes.nelem; ++node_cnt)
2451 Idx cur_node = state->nodes.elems[node_cnt];
2452 if (check_node_accept (mctx, dfa->nodes + cur_node, cur_str_idx))
2454 *err = re_node_set_merge (&next_nodes,
2455 dfa->eclosures + dfa->nexts[cur_node]);
2456 if (BE (*err != REG_NOERROR, 0))
2458 re_node_set_free (&next_nodes);
2463 context = re_string_context_at (&mctx->input, cur_str_idx, mctx->eflags);
2464 next_state = re_acquire_state_context (err, dfa, &next_nodes, context);
2465 /* We don't need to check errors here, since the return value of
2466 this function is next_state and ERR is already set. */
2468 re_node_set_free (&next_nodes);
2469 re_string_skip_bytes (&mctx->input, 1);
2474 #ifdef RE_ENABLE_I18N
2475 static reg_errcode_t
2477 transit_state_mb (re_match_context_t *mctx, re_dfastate_t *pstate)
2479 re_dfa_t *const dfa = mctx->dfa;
2483 for (i = 0; i < pstate->nodes.nelem; ++i)
2485 re_node_set dest_nodes, *new_nodes;
2486 Idx cur_node_idx = pstate->nodes.elems[i];
2489 unsigned int context;
2490 re_dfastate_t *dest_state;
2492 if (!dfa->nodes[cur_node_idx].accept_mb)
2495 if (dfa->nodes[cur_node_idx].constraint)
2497 context = re_string_context_at (&mctx->input,
2498 re_string_cur_idx (&mctx->input),
2500 if (NOT_SATISFY_NEXT_CONSTRAINT (dfa->nodes[cur_node_idx].constraint,
2505 /* How many bytes the node can accept? */
2506 naccepted = check_node_accept_bytes (dfa, cur_node_idx, &mctx->input,
2507 re_string_cur_idx (&mctx->input));
2511 /* The node can accepts `naccepted' bytes. */
2512 dest_idx = re_string_cur_idx (&mctx->input) + naccepted;
2513 mctx->max_mb_elem_len = ((mctx->max_mb_elem_len < naccepted) ? naccepted
2514 : mctx->max_mb_elem_len);
2515 err = clean_state_log_if_needed (mctx, dest_idx);
2516 if (BE (err != REG_NOERROR, 0))
2519 assert (dfa->nexts[cur_node_idx] != REG_MISSING);
2521 new_nodes = dfa->eclosures + dfa->nexts[cur_node_idx];
2523 dest_state = mctx->state_log[dest_idx];
2524 if (dest_state == NULL)
2525 dest_nodes = *new_nodes;
2528 err = re_node_set_init_union (&dest_nodes,
2529 dest_state->entrance_nodes, new_nodes);
2530 if (BE (err != REG_NOERROR, 0))
2533 context = re_string_context_at (&mctx->input, dest_idx - 1, mctx->eflags);
2534 mctx->state_log[dest_idx]
2535 = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2536 if (dest_state != NULL)
2537 re_node_set_free (&dest_nodes);
2538 if (BE (mctx->state_log[dest_idx] == NULL && err != REG_NOERROR, 0))
2543 #endif /* RE_ENABLE_I18N */
2545 static reg_errcode_t
2547 transit_state_bkref (re_match_context_t *mctx, const re_node_set *nodes)
2549 re_dfa_t *const dfa = mctx->dfa;
2552 Idx cur_str_idx = re_string_cur_idx (&mctx->input);
2554 for (i = 0; i < nodes->nelem; ++i)
2556 Idx dest_str_idx, prev_nelem, bkc_idx;
2557 Idx node_idx = nodes->elems[i];
2558 unsigned int context;
2559 const re_token_t *node = dfa->nodes + node_idx;
2560 re_node_set *new_dest_nodes;
2562 /* Check whether `node' is a backreference or not. */
2563 if (node->type != OP_BACK_REF)
2566 if (node->constraint)
2568 context = re_string_context_at (&mctx->input, cur_str_idx,
2570 if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
2574 /* `node' is a backreference.
2575 Check the substring which the substring matched. */
2576 bkc_idx = mctx->nbkref_ents;
2577 err = get_subexp (mctx, node_idx, cur_str_idx);
2578 if (BE (err != REG_NOERROR, 0))
2581 /* And add the epsilon closures (which is `new_dest_nodes') of
2582 the backreference to appropriate state_log. */
2584 assert (dfa->nexts[node_idx] != REG_MISSING);
2586 for (; bkc_idx < mctx->nbkref_ents; ++bkc_idx)
2589 re_dfastate_t *dest_state;
2590 struct re_backref_cache_entry *bkref_ent;
2591 bkref_ent = mctx->bkref_ents + bkc_idx;
2592 if (bkref_ent->node != node_idx || bkref_ent->str_idx != cur_str_idx)
2594 subexp_len = bkref_ent->subexp_to - bkref_ent->subexp_from;
2595 new_dest_nodes = (subexp_len == 0
2596 ? dfa->eclosures + dfa->edests[node_idx].elems[0]
2597 : dfa->eclosures + dfa->nexts[node_idx]);
2598 dest_str_idx = (cur_str_idx + bkref_ent->subexp_to
2599 - bkref_ent->subexp_from);
2600 context = re_string_context_at (&mctx->input, dest_str_idx - 1,
2602 dest_state = mctx->state_log[dest_str_idx];
2603 prev_nelem = ((mctx->state_log[cur_str_idx] == NULL) ? 0
2604 : mctx->state_log[cur_str_idx]->nodes.nelem);
2605 /* Add `new_dest_node' to state_log. */
2606 if (dest_state == NULL)
2608 mctx->state_log[dest_str_idx]
2609 = re_acquire_state_context (&err, dfa, new_dest_nodes,
2611 if (BE (mctx->state_log[dest_str_idx] == NULL
2612 && err != REG_NOERROR, 0))
2617 re_node_set dest_nodes;
2618 err = re_node_set_init_union (&dest_nodes,
2619 dest_state->entrance_nodes,
2621 if (BE (err != REG_NOERROR, 0))
2623 re_node_set_free (&dest_nodes);
2626 mctx->state_log[dest_str_idx]
2627 = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2628 re_node_set_free (&dest_nodes);
2629 if (BE (mctx->state_log[dest_str_idx] == NULL
2630 && err != REG_NOERROR, 0))
2633 /* We need to check recursively if the backreference can epsilon
2636 && mctx->state_log[cur_str_idx]->nodes.nelem > prev_nelem)
2638 err = check_subexp_matching_top (mctx, new_dest_nodes,
2640 if (BE (err != REG_NOERROR, 0))
2642 err = transit_state_bkref (mctx, new_dest_nodes);
2643 if (BE (err != REG_NOERROR, 0))
2653 /* Enumerate all the candidates which the backreference BKREF_NODE can match
2654 at BKREF_STR_IDX, and register them by match_ctx_add_entry().
2655 Note that we might collect inappropriate candidates here.
2656 However, the cost of checking them strictly here is too high, then we
2657 delay these checking for prune_impossible_nodes(). */
2659 static reg_errcode_t
2661 get_subexp (re_match_context_t *mctx, Idx bkref_node, Idx bkref_str_idx)
2663 re_dfa_t *const dfa = mctx->dfa;
2664 Idx subexp_num, sub_top_idx;
2665 const char *buf = (const char *) re_string_get_buffer (&mctx->input);
2666 /* Return if we have already checked BKREF_NODE at BKREF_STR_IDX. */
2667 Idx cache_idx = search_cur_bkref_entry (mctx, bkref_str_idx);
2668 if (cache_idx != REG_MISSING)
2670 const struct re_backref_cache_entry *entry = mctx->bkref_ents + cache_idx;
2672 if (entry->node == bkref_node)
2673 return REG_NOERROR; /* We already checked it. */
2674 while (entry++->more);
2677 subexp_num = dfa->nodes[bkref_node].opr.idx;
2679 /* For each sub expression */
2680 for (sub_top_idx = 0; sub_top_idx < mctx->nsub_tops; ++sub_top_idx)
2683 re_sub_match_top_t *sub_top = mctx->sub_tops[sub_top_idx];
2684 re_sub_match_last_t *sub_last;
2685 Idx sub_last_idx, sl_str, bkref_str_off;
2687 if (dfa->nodes[sub_top->node].opr.idx != subexp_num)
2688 continue; /* It isn't related. */
2690 sl_str = sub_top->str_idx;
2691 bkref_str_off = bkref_str_idx;
2692 /* At first, check the last node of sub expressions we already
2694 for (sub_last_idx = 0; sub_last_idx < sub_top->nlasts; ++sub_last_idx)
2696 regoff_t sl_str_diff;
2697 sub_last = sub_top->lasts[sub_last_idx];
2698 sl_str_diff = sub_last->str_idx - sl_str;
2699 /* The matched string by the sub expression match with the substring
2700 at the back reference? */
2701 if (sl_str_diff > 0)
2703 if (BE (bkref_str_off + sl_str_diff > mctx->input.valid_len, 0))
2705 /* Not enough chars for a successful match. */
2706 if (bkref_str_off + sl_str_diff > mctx->input.len)
2709 err = clean_state_log_if_needed (mctx,
2712 if (BE (err != REG_NOERROR, 0))
2714 buf = (const char *) re_string_get_buffer (&mctx->input);
2716 if (memcmp (buf + bkref_str_off, buf + sl_str, sl_str_diff) != 0)
2717 break; /* We don't need to search this sub expression any more. */
2719 bkref_str_off += sl_str_diff;
2720 sl_str += sl_str_diff;
2721 err = get_subexp_sub (mctx, sub_top, sub_last, bkref_node,
2724 /* Reload buf, since the preceding call might have reallocated
2726 buf = (const char *) re_string_get_buffer (&mctx->input);
2728 if (err == REG_NOMATCH)
2730 if (BE (err != REG_NOERROR, 0))
2734 if (sub_last_idx < sub_top->nlasts)
2736 if (sub_last_idx > 0)
2738 /* Then, search for the other last nodes of the sub expression. */
2739 for (; sl_str <= bkref_str_idx; ++sl_str)
2742 regoff_t sl_str_off;
2743 const re_node_set *nodes;
2744 sl_str_off = sl_str - sub_top->str_idx;
2745 /* The matched string by the sub expression match with the substring
2746 at the back reference? */
2749 if (BE (bkref_str_off >= mctx->input.valid_len, 0))
2751 /* If we are at the end of the input, we cannot match. */
2752 if (bkref_str_off >= mctx->input.len)
2755 err = extend_buffers (mctx);
2756 if (BE (err != REG_NOERROR, 0))
2759 buf = (const char *) re_string_get_buffer (&mctx->input);
2761 if (buf [bkref_str_off++] != buf[sl_str - 1])
2762 break; /* We don't need to search this sub expression
2765 if (mctx->state_log[sl_str] == NULL)
2767 /* Does this state have a ')' of the sub expression? */
2768 nodes = &mctx->state_log[sl_str]->nodes;
2769 cls_node = find_subexp_node (dfa, nodes, subexp_num, OP_CLOSE_SUBEXP);
2770 if (cls_node == REG_MISSING)
2772 if (sub_top->path == NULL)
2774 sub_top->path = re_calloc (state_array_t,
2775 sl_str - sub_top->str_idx + 1);
2776 if (sub_top->path == NULL)
2779 /* Can the OP_OPEN_SUBEXP node arrive the OP_CLOSE_SUBEXP node
2780 in the current context? */
2781 err = check_arrival (mctx, sub_top->path, sub_top->node,
2782 sub_top->str_idx, cls_node, sl_str, OP_CLOSE_SUBEXP);
2783 if (err == REG_NOMATCH)
2785 if (BE (err != REG_NOERROR, 0))
2787 sub_last = match_ctx_add_sublast (sub_top, cls_node, sl_str);
2788 if (BE (sub_last == NULL, 0))
2790 err = get_subexp_sub (mctx, sub_top, sub_last, bkref_node,
2792 if (err == REG_NOMATCH)
2799 /* Helper functions for get_subexp(). */
2801 /* Check SUB_LAST can arrive to the back reference BKREF_NODE at BKREF_STR.
2802 If it can arrive, register the sub expression expressed with SUB_TOP
2805 static reg_errcode_t
2807 get_subexp_sub (re_match_context_t *mctx, const re_sub_match_top_t *sub_top,
2808 re_sub_match_last_t *sub_last, Idx bkref_node, Idx bkref_str)
2812 /* Can the subexpression arrive the back reference? */
2813 err = check_arrival (mctx, &sub_last->path, sub_last->node,
2814 sub_last->str_idx, bkref_node, bkref_str, OP_OPEN_SUBEXP);
2815 if (err != REG_NOERROR)
2817 err = match_ctx_add_entry (mctx, bkref_node, bkref_str, sub_top->str_idx,
2819 if (BE (err != REG_NOERROR, 0))
2821 to_idx = bkref_str + sub_last->str_idx - sub_top->str_idx;
2822 return clean_state_log_if_needed (mctx, to_idx);
2825 /* Find the first node which is '(' or ')' and whose index is SUBEXP_IDX.
2826 Search '(' if FL_OPEN, or search ')' otherwise.
2827 TODO: This function isn't efficient...
2828 Because there might be more than one nodes whose types are
2829 OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
2835 find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
2836 Idx subexp_idx, int type)
2839 for (cls_idx = 0; cls_idx < nodes->nelem; ++cls_idx)
2841 Idx cls_node = nodes->elems[cls_idx];
2842 const re_token_t *node = dfa->nodes + cls_node;
2843 if (node->type == type
2844 && node->opr.idx == subexp_idx)
2850 /* Check whether the node TOP_NODE at TOP_STR can arrive to the node
2851 LAST_NODE at LAST_STR. We record the path onto PATH since it will be
2853 Return REG_NOERROR if it can arrive, or REG_NOMATCH otherwise. */
2855 static reg_errcode_t
2857 check_arrival (re_match_context_t *mctx, state_array_t *path,
2858 Idx top_node, Idx top_str, Idx last_node, Idx last_str,
2861 re_dfa_t *const dfa = mctx->dfa;
2863 Idx subexp_num, backup_cur_idx, str_idx, null_cnt;
2864 re_dfastate_t *cur_state = NULL;
2865 re_node_set *cur_nodes, next_nodes;
2866 re_dfastate_t **backup_state_log;
2867 unsigned int context;
2869 subexp_num = dfa->nodes[top_node].opr.idx;
2870 /* Extend the buffer if we need. */
2871 if (BE (path->alloc < last_str + mctx->max_mb_elem_len + 1, 0))
2873 re_dfastate_t **new_array;
2874 Idx old_alloc = path->alloc;
2875 path->alloc += last_str + mctx->max_mb_elem_len + 1;
2876 new_array = re_realloc (path->array, re_dfastate_t *, path->alloc);
2877 if (new_array == NULL)
2879 path->alloc = old_alloc;
2882 path->array = new_array;
2883 memset (new_array + old_alloc, '\0',
2884 sizeof (re_dfastate_t *) * (path->alloc - old_alloc));
2887 str_idx = path->next_idx == 0 ? top_str : path->next_idx;
2889 /* Temporary modify MCTX. */
2890 backup_state_log = mctx->state_log;
2891 backup_cur_idx = mctx->input.cur_idx;
2892 mctx->state_log = path->array;
2893 mctx->input.cur_idx = str_idx;
2895 /* Setup initial node set. */
2896 context = re_string_context_at (&mctx->input, str_idx - 1, mctx->eflags);
2897 if (str_idx == top_str)
2899 err = re_node_set_init_1 (&next_nodes, top_node);
2900 if (BE (err != REG_NOERROR, 0))
2902 err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
2903 if (BE (err != REG_NOERROR, 0))
2905 re_node_set_free (&next_nodes);
2911 cur_state = mctx->state_log[str_idx];
2912 if (cur_state && cur_state->has_backref)
2914 err = re_node_set_init_copy (&next_nodes, &cur_state->nodes);
2915 if (BE ( err != REG_NOERROR, 0))
2919 re_node_set_init_empty (&next_nodes);
2921 if (str_idx == top_str || (cur_state && cur_state->has_backref))
2923 if (next_nodes.nelem)
2925 err = expand_bkref_cache (mctx, &next_nodes, str_idx,
2927 if (BE ( err != REG_NOERROR, 0))
2929 re_node_set_free (&next_nodes);
2933 cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
2934 if (BE (cur_state == NULL && err != REG_NOERROR, 0))
2936 re_node_set_free (&next_nodes);
2939 mctx->state_log[str_idx] = cur_state;
2942 for (null_cnt = 0; str_idx < last_str && null_cnt <= mctx->max_mb_elem_len;)
2944 re_node_set_empty (&next_nodes);
2945 if (mctx->state_log[str_idx + 1])
2947 err = re_node_set_merge (&next_nodes,
2948 &mctx->state_log[str_idx + 1]->nodes);
2949 if (BE (err != REG_NOERROR, 0))
2951 re_node_set_free (&next_nodes);
2957 err = check_arrival_add_next_nodes (mctx, str_idx,
2958 &cur_state->non_eps_nodes, &next_nodes);
2959 if (BE (err != REG_NOERROR, 0))
2961 re_node_set_free (&next_nodes);
2966 if (next_nodes.nelem)
2968 err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
2969 if (BE (err != REG_NOERROR, 0))
2971 re_node_set_free (&next_nodes);
2974 err = expand_bkref_cache (mctx, &next_nodes, str_idx,
2976 if (BE ( err != REG_NOERROR, 0))
2978 re_node_set_free (&next_nodes);
2982 context = re_string_context_at (&mctx->input, str_idx - 1, mctx->eflags);
2983 cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
2984 if (BE (cur_state == NULL && err != REG_NOERROR, 0))
2986 re_node_set_free (&next_nodes);
2989 mctx->state_log[str_idx] = cur_state;
2990 null_cnt = cur_state == NULL ? null_cnt + 1 : 0;
2992 re_node_set_free (&next_nodes);
2993 cur_nodes = (mctx->state_log[last_str] == NULL ? NULL
2994 : &mctx->state_log[last_str]->nodes);
2995 path->next_idx = str_idx;
2998 mctx->state_log = backup_state_log;
2999 mctx->input.cur_idx = backup_cur_idx;
3001 /* Then check the current node set has the node LAST_NODE. */
3002 if (cur_nodes != NULL && re_node_set_contains (cur_nodes, last_node))
3008 /* Helper functions for check_arrival. */
3010 /* Calculate the destination nodes of CUR_NODES at STR_IDX, and append them
3012 TODO: This function is similar to the functions transit_state*(),
3013 however this function has many additional works.
3014 Can't we unify them? */
3016 static reg_errcode_t
3018 check_arrival_add_next_nodes (re_match_context_t *mctx, Idx str_idx,
3019 re_node_set *cur_nodes,
3020 re_node_set *next_nodes)
3022 re_dfa_t *const dfa = mctx->dfa;
3026 re_node_set union_set;
3027 re_node_set_init_empty (&union_set);
3028 for (cur_idx = 0; cur_idx < cur_nodes->nelem; ++cur_idx)
3031 Idx cur_node = cur_nodes->elems[cur_idx];
3033 re_token_type_t type = dfa->nodes[cur_node].type;
3034 assert (!IS_EPSILON_NODE (type));
3036 #ifdef RE_ENABLE_I18N
3037 /* If the node may accept `multi byte'. */
3038 if (dfa->nodes[cur_node].accept_mb)
3040 naccepted = check_node_accept_bytes (dfa, cur_node, &mctx->input,
3044 re_dfastate_t *dest_state;
3045 Idx next_node = dfa->nexts[cur_node];
3046 Idx next_idx = str_idx + naccepted;
3047 dest_state = mctx->state_log[next_idx];
3048 re_node_set_empty (&union_set);
3051 err = re_node_set_merge (&union_set, &dest_state->nodes);
3052 if (BE (err != REG_NOERROR, 0))
3054 re_node_set_free (&union_set);
3058 ok = re_node_set_insert (&union_set, next_node);
3061 re_node_set_free (&union_set);
3064 mctx->state_log[next_idx] = re_acquire_state (&err, dfa,
3066 if (BE (mctx->state_log[next_idx] == NULL
3067 && err != REG_NOERROR, 0))
3069 re_node_set_free (&union_set);
3074 #endif /* RE_ENABLE_I18N */
3076 || check_node_accept (mctx, dfa->nodes + cur_node, str_idx))
3078 ok = re_node_set_insert (next_nodes, dfa->nexts[cur_node]);
3081 re_node_set_free (&union_set);
3086 re_node_set_free (&union_set);
3090 /* For all the nodes in CUR_NODES, add the epsilon closures of them to
3091 CUR_NODES, however exclude the nodes which are:
3092 - inside the sub expression whose number is EX_SUBEXP, if FL_OPEN.
3093 - out of the sub expression whose number is EX_SUBEXP, if !FL_OPEN.
3096 static reg_errcode_t
3098 check_arrival_expand_ecl (re_dfa_t *dfa, re_node_set *cur_nodes,
3099 Idx ex_subexp, int type)
3102 Idx idx, outside_node;
3103 re_node_set new_nodes;
3105 assert (cur_nodes->nelem);
3107 err = re_node_set_alloc (&new_nodes, cur_nodes->nelem);
3108 if (BE (err != REG_NOERROR, 0))
3110 /* Create a new node set NEW_NODES with the nodes which are epsilon
3111 closures of the node in CUR_NODES. */
3113 for (idx = 0; idx < cur_nodes->nelem; ++idx)
3115 Idx cur_node = cur_nodes->elems[idx];
3116 re_node_set *eclosure = dfa->eclosures + cur_node;
3117 outside_node = find_subexp_node (dfa, eclosure, ex_subexp, type);
3118 if (outside_node == REG_MISSING)
3120 /* There are no problematic nodes, just merge them. */
3121 err = re_node_set_merge (&new_nodes, eclosure);
3122 if (BE (err != REG_NOERROR, 0))
3124 re_node_set_free (&new_nodes);
3130 /* There are problematic nodes, re-calculate incrementally. */
3131 err = check_arrival_expand_ecl_sub (dfa, &new_nodes, cur_node,
3133 if (BE (err != REG_NOERROR, 0))
3135 re_node_set_free (&new_nodes);
3140 re_node_set_free (cur_nodes);
3141 *cur_nodes = new_nodes;
3145 /* Helper function for check_arrival_expand_ecl.
3146 Check incrementally the epsilon closure of TARGET, and if it isn't
3147 problematic append it to DST_NODES. */
3149 static reg_errcode_t
3151 check_arrival_expand_ecl_sub (re_dfa_t *dfa, re_node_set *dst_nodes,
3152 Idx target, Idx ex_subexp, int type)
3155 for (cur_node = target; !re_node_set_contains (dst_nodes, cur_node);)
3159 if (dfa->nodes[cur_node].type == type
3160 && dfa->nodes[cur_node].opr.idx == ex_subexp)
3162 if (type == OP_CLOSE_SUBEXP)
3164 ok = re_node_set_insert (dst_nodes, cur_node);
3170 ok = re_node_set_insert (dst_nodes, cur_node);
3173 if (dfa->edests[cur_node].nelem == 0)
3175 if (dfa->edests[cur_node].nelem == 2)
3178 check_arrival_expand_ecl_sub (dfa, dst_nodes,
3179 dfa->edests[cur_node].elems[1],
3181 if (BE (ret != REG_NOERROR, 0))
3184 cur_node = dfa->edests[cur_node].elems[0];
3190 /* For all the back references in the current state, calculate the
3191 destination of the back references by the appropriate entry
3192 in MCTX->BKREF_ENTS. */
3194 static reg_errcode_t
3196 expand_bkref_cache (re_match_context_t *mctx, re_node_set *cur_nodes,
3197 Idx cur_str, Idx subexp_num, int type)
3199 re_dfa_t *const dfa = mctx->dfa;
3201 Idx cache_idx_start = search_cur_bkref_entry (mctx, cur_str);
3202 struct re_backref_cache_entry *ent;
3204 if (cache_idx_start == REG_MISSING)
3208 ent = mctx->bkref_ents + cache_idx_start;
3211 Idx to_idx, next_node;
3213 /* Is this entry ENT is appropriate? */
3214 if (!re_node_set_contains (cur_nodes, ent->node))
3217 to_idx = cur_str + ent->subexp_to - ent->subexp_from;
3218 /* Calculate the destination of the back reference, and append it
3219 to MCTX->STATE_LOG. */
3220 if (to_idx == cur_str)
3222 /* The backreference did epsilon transit, we must re-check all the
3223 node in the current state. */
3224 re_node_set new_dests;
3225 reg_errcode_t err2, err3;
3226 next_node = dfa->edests[ent->node].elems[0];
3227 if (re_node_set_contains (cur_nodes, next_node))
3229 err = re_node_set_init_1 (&new_dests, next_node);
3230 err2 = check_arrival_expand_ecl (dfa, &new_dests, subexp_num, type);
3231 err3 = re_node_set_merge (cur_nodes, &new_dests);
3232 re_node_set_free (&new_dests);
3233 if (BE (err != REG_NOERROR || err2 != REG_NOERROR
3234 || err3 != REG_NOERROR, 0))
3236 err = (err != REG_NOERROR ? err
3237 : (err2 != REG_NOERROR ? err2 : err3));
3240 /* TODO: It is still inefficient... */
3245 re_node_set union_set;
3246 next_node = dfa->nexts[ent->node];
3247 if (mctx->state_log[to_idx])
3250 if (re_node_set_contains (&mctx->state_log[to_idx]->nodes,
3253 err = re_node_set_init_copy (&union_set,
3254 &mctx->state_log[to_idx]->nodes);
3255 ok = re_node_set_insert (&union_set, next_node);
3256 if (BE (err != REG_NOERROR || ! ok, 0))
3258 re_node_set_free (&union_set);
3259 err = err != REG_NOERROR ? err : REG_ESPACE;
3265 err = re_node_set_init_1 (&union_set, next_node);
3266 if (BE (err != REG_NOERROR, 0))
3269 mctx->state_log[to_idx] = re_acquire_state (&err, dfa, &union_set);
3270 re_node_set_free (&union_set);
3271 if (BE (mctx->state_log[to_idx] == NULL
3272 && err != REG_NOERROR, 0))
3276 while (ent++->more);
3280 /* Build transition table for the state.
3281 Return true if successful. */
3285 build_trtable (re_dfa_t *dfa, re_dfastate_t *state)
3290 bool need_word_trtable = false;
3291 unsigned int elem, mask;
3292 bool dests_node_malloced = false, dest_states_malloced = false;
3293 Idx ndests; /* Number of the destination states from `state'. */
3294 re_dfastate_t **trtable;
3295 re_dfastate_t **dest_states = NULL, **dest_states_word, **dest_states_nl;
3296 re_node_set follows, *dests_node;
3300 /* We build DFA states which corresponds to the destination nodes
3301 from `state'. `dests_node[i]' represents the nodes which i-th
3302 destination state contains, and `dests_ch[i]' represents the
3303 characters which i-th destination state accepts. */
3304 if (__libc_use_alloca ((sizeof (re_node_set) + sizeof (bitset)) * SBC_MAX))
3305 dests_node = (re_node_set *)
3306 alloca ((sizeof (re_node_set) + sizeof (bitset)) * SBC_MAX);
3309 dests_node = (re_node_set *)
3310 malloc ((sizeof (re_node_set) + sizeof (bitset)) * SBC_MAX);
3311 if (BE (dests_node == NULL, 0))
3313 dests_node_malloced = true;
3315 dests_ch = (bitset *) (dests_node + SBC_MAX);
3317 /* Initialize transiton table. */
3318 state->word_trtable = state->trtable = NULL;
3320 /* At first, group all nodes belonging to `state' into several
3322 ndests = group_nodes_into_DFAstates (dfa, state, dests_node, dests_ch);
3323 if (BE (! REG_VALID_NONZERO_INDEX (ndests), 0))
3325 if (dests_node_malloced)
3329 state->trtable = re_calloc (re_dfastate_t *, SBC_MAX);
3335 err = re_node_set_alloc (&follows, ndests + 1);
3336 if (BE (err != REG_NOERROR, 0))
3339 if (__libc_use_alloca ((sizeof (re_node_set) + sizeof (bitset)) * SBC_MAX
3340 + ndests * 3 * sizeof (re_dfastate_t *)))
3341 dest_states = (re_dfastate_t **)
3342 alloca (ndests * 3 * sizeof (re_dfastate_t *));
3345 dest_states = (re_dfastate_t **)
3346 malloc (ndests * 3 * sizeof (re_dfastate_t *));
3347 if (BE (dest_states == NULL, 0))
3350 if (dest_states_malloced)
3352 re_node_set_free (&follows);
3353 for (i = 0; i < ndests; ++i)
3354 re_node_set_free (dests_node + i);
3355 if (dests_node_malloced)
3359 dest_states_malloced = true;
3361 dest_states_word = dest_states + ndests;
3362 dest_states_nl = dest_states_word + ndests;
3363 bitset_empty (acceptable);
3365 /* Then build the states for all destinations. */
3366 for (i = 0; i < ndests; ++i)
3369 re_node_set_empty (&follows);
3370 /* Merge the follows of this destination states. */
3371 for (j = 0; j < dests_node[i].nelem; ++j)
3373 next_node = dfa->nexts[dests_node[i].elems[j]];
3374 if (next_node != REG_MISSING)
3376 err = re_node_set_merge (&follows, dfa->eclosures + next_node);
3377 if (BE (err != REG_NOERROR, 0))
3381 dest_states[i] = re_acquire_state_context (&err, dfa, &follows, 0);
3382 if (BE (dest_states[i] == NULL && err != REG_NOERROR, 0))
3384 /* If the new state has context constraint,
3385 build appropriate states for these contexts. */
3386 if (dest_states[i]->has_constraint)
3388 dest_states_word[i] = re_acquire_state_context (&err, dfa, &follows,
3390 if (BE (dest_states_word[i] == NULL && err != REG_NOERROR, 0))
3393 if (dest_states[i] != dest_states_word[i] && dfa->mb_cur_max > 1)
3394 need_word_trtable = true;
3396 dest_states_nl[i] = re_acquire_state_context (&err, dfa, &follows,
3398 if (BE (dest_states_nl[i] == NULL && err != REG_NOERROR, 0))
3403 dest_states_word[i] = dest_states[i];
3404 dest_states_nl[i] = dest_states[i];
3406 bitset_merge (acceptable, dests_ch[i]);
3409 if (!BE (need_word_trtable, 0))
3411 /* We don't care about whether the following character is a word
3412 character, or we are in a single-byte character set so we can
3413 discern by looking at the character code: allocate a
3414 256-entry transition table. */
3415 trtable = state->trtable = re_calloc (re_dfastate_t *, SBC_MAX);
3416 if (BE (trtable == NULL, 0))
3419 /* For all characters ch...: */
3420 for (i = 0; i < BITSET_UINTS; ++i)
3421 for (ch = i * UINT_BITS, elem = acceptable[i], mask = 1;
3423 mask <<= 1, elem >>= 1, ++ch)
3424 if (BE (elem & 1, 0))
3426 /* There must be exactly one destination which accepts
3427 character ch. See group_nodes_into_DFAstates. */
3428 for (j = 0; (dests_ch[j][i] & mask) == 0; ++j)
3431 /* j-th destination accepts the word character ch. */
3432 if (dfa->word_char[i] & mask)
3433 trtable[ch] = dest_states_word[j];
3435 trtable[ch] = dest_states[j];
3440 /* We care about whether the following character is a word
3441 character, and we are in a multi-byte character set: discern
3442 by looking at the character code: build two 256-entry
3443 transition tables, one starting at trtable[0] and one
3444 starting at trtable[SBC_MAX]. */
3445 trtable = state->word_trtable = re_calloc (re_dfastate_t *, 2 * SBC_MAX);
3446 if (BE (trtable == NULL, 0))
3449 /* For all characters ch...: */
3450 for (i = 0; i < BITSET_UINTS; ++i)
3451 for (ch = i * UINT_BITS, elem = acceptable[i], mask = 1;
3453 mask <<= 1, elem >>= 1, ++ch)
3454 if (BE (elem & 1, 0))
3456 /* There must be exactly one destination which accepts
3457 character ch. See group_nodes_into_DFAstates. */
3458 for (j = 0; (dests_ch[j][i] & mask) == 0; ++j)
3461 /* j-th destination accepts the word character ch. */
3462 trtable[ch] = dest_states[j];
3463 trtable[ch + SBC_MAX] = dest_states_word[j];
3468 if (bitset_contain (acceptable, NEWLINE_CHAR))
3470 /* The current state accepts newline character. */
3471 for (j = 0; j < ndests; ++j)
3472 if (bitset_contain (dests_ch[j], NEWLINE_CHAR))
3474 /* k-th destination accepts newline character. */
3475 trtable[NEWLINE_CHAR] = dest_states_nl[j];
3476 if (need_word_trtable)
3477 trtable[NEWLINE_CHAR + SBC_MAX] = dest_states_nl[j];
3478 /* There must be only one destination which accepts
3479 newline. See group_nodes_into_DFAstates. */
3484 if (dest_states_malloced)
3487 re_node_set_free (&follows);
3488 for (i = 0; i < ndests; ++i)
3489 re_node_set_free (dests_node + i);
3491 if (dests_node_malloced)
3497 /* Group all nodes belonging to STATE into several destinations.
3498 Then for all destinations, set the nodes belonging to the destination
3499 to DESTS_NODE[i] and set the characters accepted by the destination
3500 to DEST_CH[i]. This function return the number of destinations. */
3504 group_nodes_into_DFAstates (const re_dfa_t *dfa, const re_dfastate_t *state,
3505 re_node_set *dests_node, bitset *dests_ch)
3510 Idx ndests; /* Number of the destinations from `state'. */
3511 bitset accepts; /* Characters a node can accept. */
3512 const re_node_set *cur_nodes = &state->nodes;
3513 bitset_empty (accepts);
3516 /* For all the nodes belonging to `state', */
3517 for (i = 0; i < cur_nodes->nelem; ++i)
3519 re_token_t *node = &dfa->nodes[cur_nodes->elems[i]];
3520 re_token_type_t type = node->type;
3521 unsigned int constraint = node->constraint;
3523 /* Enumerate all single byte character this node can accept. */
3524 if (type == CHARACTER)
3525 bitset_set (accepts, node->opr.c);
3526 else if (type == SIMPLE_BRACKET)
3528 bitset_merge (accepts, node->opr.sbcset);
3530 else if (type == OP_PERIOD)
3532 #ifdef RE_ENABLE_I18N
3533 if (dfa->mb_cur_max > 1)
3534 bitset_merge (accepts, dfa->sb_char);
3537 bitset_set_all (accepts);
3538 if (!(dfa->syntax & REG_DOT_NEWLINE))
3539 bitset_clear (accepts, '\n');
3540 if (dfa->syntax & REG_DOT_NOT_NULL)
3541 bitset_clear (accepts, '\0');
3543 #ifdef RE_ENABLE_I18N
3544 else if (type == OP_UTF8_PERIOD)
3546 memset (accepts, 255, sizeof (unsigned int) * BITSET_UINTS / 2);
3547 if (!(dfa->syntax & REG_DOT_NEWLINE))
3548 bitset_clear (accepts, '\n');
3549 if (dfa->syntax & REG_DOT_NOT_NULL)
3550 bitset_clear (accepts, '\0');
3556 /* Check the `accepts' and sift the characters which are not
3557 match it the context. */
3560 if (constraint & NEXT_NEWLINE_CONSTRAINT)
3562 unsigned int accepts_newline =
3563 bitset_contain (accepts, NEWLINE_CHAR);
3564 bitset_empty (accepts);
3565 if (accepts_newline)
3566 bitset_set (accepts, NEWLINE_CHAR);
3570 if (constraint & NEXT_ENDBUF_CONSTRAINT)
3572 bitset_empty (accepts);
3576 if (constraint & NEXT_WORD_CONSTRAINT)
3578 unsigned int any_set = 0;
3579 if (type == CHARACTER && !node->word_char)
3581 bitset_empty (accepts);
3584 #ifdef RE_ENABLE_I18N
3585 if (dfa->mb_cur_max > 1)
3586 for (j = 0; j < BITSET_UINTS; ++j)
3587 any_set |= (accepts[j] &= (dfa->word_char[j] | ~dfa->sb_char[j]));
3590 for (j = 0; j < BITSET_UINTS; ++j)
3591 any_set |= (accepts[j] &= dfa->word_char[j]);
3595 if (constraint & NEXT_NOTWORD_CONSTRAINT)
3597 unsigned int any_set = 0;
3598 if (type == CHARACTER && node->word_char)
3600 bitset_empty (accepts);
3603 #ifdef RE_ENABLE_I18N
3604 if (dfa->mb_cur_max > 1)
3605 for (j = 0; j < BITSET_UINTS; ++j)
3606 any_set |= (accepts[j] &= ~(dfa->word_char[j] & dfa->sb_char[j]));
3609 for (j = 0; j < BITSET_UINTS; ++j)
3610 any_set |= (accepts[j] &= ~dfa->word_char[j]);
3616 /* Then divide `accepts' into DFA states, or create a new
3617 state. Above, we make sure that accepts is not empty. */
3618 for (j = 0; j < ndests; ++j)
3620 bitset intersec; /* Intersection sets, see below. */
3622 /* Flags, see below. */
3623 unsigned int has_intersec, not_subset, not_consumed;
3625 /* Optimization, skip if this state doesn't accept the character. */
3626 if (type == CHARACTER && !bitset_contain (dests_ch[j], node->opr.c))
3629 /* Enumerate the intersection set of this state and `accepts'. */
3631 for (k = 0; k < BITSET_UINTS; ++k)
3632 has_intersec |= intersec[k] = accepts[k] & dests_ch[j][k];
3633 /* And skip if the intersection set is empty. */
3637 /* Then check if this state is a subset of `accepts'. */
3638 not_subset = not_consumed = 0;
3639 for (k = 0; k < BITSET_UINTS; ++k)
3641 not_subset |= remains[k] = ~accepts[k] & dests_ch[j][k];
3642 not_consumed |= accepts[k] = accepts[k] & ~dests_ch[j][k];
3645 /* If this state isn't a subset of `accepts', create a
3646 new group state, which has the `remains'. */
3649 bitset_copy (dests_ch[ndests], remains);
3650 bitset_copy (dests_ch[j], intersec);
3651 err = re_node_set_init_copy (dests_node + ndests, &dests_node[j]);
3652 if (BE (err != REG_NOERROR, 0))
3657 /* Put the position in the current group. */
3658 ok = re_node_set_insert (&dests_node[j], cur_nodes->elems[i]);
3662 /* If all characters are consumed, go to next node. */
3666 /* Some characters remain, create a new group. */
3669 bitset_copy (dests_ch[ndests], accepts);
3670 err = re_node_set_init_1 (dests_node + ndests, cur_nodes->elems[i]);
3671 if (BE (err != REG_NOERROR, 0))
3674 bitset_empty (accepts);
3679 for (j = 0; j < ndests; ++j)
3680 re_node_set_free (dests_node + j);
3684 #ifdef RE_ENABLE_I18N
3685 /* Check how many bytes the node `dfa->nodes[node_idx]' accepts.
3686 Return the number of the bytes the node accepts.
3687 STR_IDX is the current index of the input string.
3689 This function handles the nodes which can accept one character, or
3690 one collating element like '.', '[a-z]', opposite to the other nodes
3691 can only accept one byte. */
3695 check_node_accept_bytes (re_dfa_t *dfa, Idx node_idx,
3696 const re_string_t *input, Idx str_idx)
3698 const re_token_t *node = dfa->nodes + node_idx;
3699 int char_len, elem_len;
3702 if (BE (node->type == OP_UTF8_PERIOD, 0))
3704 unsigned char c = re_string_byte_at (input, str_idx), d;
3705 if (BE (c < 0xc2, 1))
3708 if (str_idx + 2 > input->len)
3711 d = re_string_byte_at (input, str_idx + 1);
3713 return (d < 0x80 || d > 0xbf) ? 0 : 2;
3717 if (c == 0xe0 && d < 0xa0)
3723 if (c == 0xf0 && d < 0x90)
3729 if (c == 0xf8 && d < 0x88)
3735 if (c == 0xfc && d < 0x84)
3741 if (str_idx + char_len > input->len)
3744 for (i = 1; i < char_len; ++i)
3746 d = re_string_byte_at (input, str_idx + i);
3747 if (d < 0x80 || d > 0xbf)
3753 char_len = re_string_char_size_at (input, str_idx);
3754 if (node->type == OP_PERIOD)
3758 /* FIXME: I don't think this if is needed, as both '\n'
3759 and '\0' are char_len == 1. */
3760 /* '.' accepts any one character except the following two cases. */
3761 if ((!(dfa->syntax & REG_DOT_NEWLINE) &&
3762 re_string_byte_at (input, str_idx) == '\n') ||
3763 ((dfa->syntax & REG_DOT_NOT_NULL) &&
3764 re_string_byte_at (input, str_idx) == '\0'))
3769 elem_len = re_string_elem_size_at (input, str_idx);
3770 if ((elem_len <= 1 && char_len <= 1) || char_len == 0)
3773 if (node->type == COMPLEX_BRACKET)
3775 const re_charset_t *cset = node->opr.mbcset;
3777 const unsigned char *pin
3778 = ((const unsigned char *) re_string_get_buffer (input) + str_idx);
3783 wchar_t wc = ((cset->nranges || cset->nchar_classes || cset->nmbchars)
3784 ? re_string_wchar_at (input, str_idx) : 0);
3786 /* match with multibyte character? */
3787 for (i = 0; i < cset->nmbchars; ++i)
3788 if (wc == cset->mbchars[i])
3790 match_len = char_len;
3791 goto check_node_accept_bytes_match;
3793 /* match with character_class? */
3794 for (i = 0; i < cset->nchar_classes; ++i)
3796 wctype_t wt = cset->char_classes[i];
3797 if (__iswctype (wc, wt))
3799 match_len = char_len;
3800 goto check_node_accept_bytes_match;
3805 nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
3808 unsigned int in_collseq = 0;
3809 const int32_t *table, *indirect;
3810 const unsigned char *weights, *extra;
3811 const char *collseqwc;
3813 /* This #include defines a local function! */
3814 # include <locale/weight.h>
3816 /* match with collating_symbol? */
3817 if (cset->ncoll_syms)
3818 extra = (const unsigned char *)
3819 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB);
3820 for (i = 0; i < cset->ncoll_syms; ++i)
3822 const unsigned char *coll_sym = extra + cset->coll_syms[i];
3823 /* Compare the length of input collating element and
3824 the length of current collating element. */
3825 if (*coll_sym != elem_len)
3827 /* Compare each bytes. */
3828 for (j = 0; j < *coll_sym; j++)
3829 if (pin[j] != coll_sym[1 + j])
3833 /* Match if every bytes is equal. */
3835 goto check_node_accept_bytes_match;
3841 if (elem_len <= char_len)
3843 collseqwc = _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQWC);
3844 in_collseq = __collseq_table_lookup (collseqwc, wc);
3847 in_collseq = find_collation_sequence_value (pin, elem_len);
3849 /* match with range expression? */
3850 for (i = 0; i < cset->nranges; ++i)
3851 if (cset->range_starts[i] <= in_collseq
3852 && in_collseq <= cset->range_ends[i])
3854 match_len = elem_len;
3855 goto check_node_accept_bytes_match;
3858 /* match with equivalence_class? */
3859 if (cset->nequiv_classes)
3861 const unsigned char *cp = pin;
3862 table = (const int32_t *)
3863 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
3864 weights = (const unsigned char *)
3865 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_WEIGHTMB);
3866 extra = (const unsigned char *)
3867 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAMB);
3868 indirect = (const int32_t *)
3869 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_INDIRECTMB);
3870 idx = findidx (&cp);
3872 for (i = 0; i < cset->nequiv_classes; ++i)
3874 int32_t equiv_class_idx = cset->equiv_classes[i];
3875 size_t weight_len = weights[idx];
3876 if (weight_len == weights[equiv_class_idx])
3879 while (cnt <= weight_len
3880 && (weights[equiv_class_idx + 1 + cnt]
3881 == weights[idx + 1 + cnt]))
3883 if (cnt > weight_len)
3885 match_len = elem_len;
3886 goto check_node_accept_bytes_match;
3895 /* match with range expression? */
3897 wchar_t cmp_buf[] = {L'\0', L'\0', wc, L'\0', L'\0', L'\0'};
3899 wchar_t cmp_buf[] = {L'\0', L'\0', L'\0', L'\0', L'\0', L'\0'};
3902 for (i = 0; i < cset->nranges; ++i)
3904 cmp_buf[0] = cset->range_starts[i];
3905 cmp_buf[4] = cset->range_ends[i];
3906 if (wcscoll (cmp_buf, cmp_buf + 2) <= 0
3907 && wcscoll (cmp_buf + 2, cmp_buf + 4) <= 0)
3909 match_len = char_len;
3910 goto check_node_accept_bytes_match;
3914 check_node_accept_bytes_match:
3915 if (!cset->non_match)
3922 return (elem_len > char_len) ? elem_len : char_len;
3930 find_collation_sequence_value (const unsigned char *mbs, size_t mbs_len)
3932 uint32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
3937 /* No valid character. Match it as a single byte character. */
3938 const unsigned char *collseq = (const unsigned char *)
3939 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQMB);
3940 return collseq[mbs[0]];
3947 const unsigned char *extra = (const unsigned char *)
3948 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB);
3949 int32_t extrasize = (const unsigned char *)
3950 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB + 1) - extra;
3952 for (idx = 0; idx < extrasize;)
3956 int32_t elem_mbs_len;
3957 /* Skip the name of collating element name. */
3958 idx = idx + extra[idx] + 1;
3959 elem_mbs_len = extra[idx++];
3960 if (mbs_len == elem_mbs_len)
3962 for (mbs_cnt = 0; mbs_cnt < elem_mbs_len; ++mbs_cnt)
3963 if (extra[idx + mbs_cnt] != mbs[mbs_cnt])
3965 if (mbs_cnt == elem_mbs_len)
3966 /* Found the entry. */
3969 /* Skip the byte sequence of the collating element. */
3970 idx += elem_mbs_len;
3971 /* Adjust for the alignment. */
3972 idx = (idx + 3) & ~3;
3973 /* Skip the collation sequence value. */
3974 idx += sizeof (uint32_t);
3975 /* Skip the wide char sequence of the collating element. */
3976 idx = idx + sizeof (uint32_t) * (extra[idx] + 1);
3977 /* If we found the entry, return the sequence value. */
3979 return *(uint32_t *) (extra + idx);
3980 /* Skip the collation sequence value. */
3981 idx += sizeof (uint32_t);
3987 #endif /* RE_ENABLE_I18N */
3989 /* Check whether the node accepts the byte which is IDX-th
3990 byte of the INPUT. */
3994 check_node_accept (const re_match_context_t *mctx, const re_token_t *node,
3998 ch = re_string_byte_at (&mctx->input, idx);
4002 if (node->opr.c != ch)
4006 case SIMPLE_BRACKET:
4007 if (!bitset_contain (node->opr.sbcset, ch))
4011 #ifdef RE_ENABLE_I18N
4012 case OP_UTF8_PERIOD:
4018 if ((ch == '\n' && !(mctx->dfa->syntax & REG_DOT_NEWLINE))
4019 || (ch == '\0' && (mctx->dfa->syntax & REG_DOT_NOT_NULL)))
4027 if (node->constraint)
4029 /* The node has constraints. Check whether the current context
4030 satisfies the constraints. */
4031 unsigned int context = re_string_context_at (&mctx->input, idx,
4033 if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
4040 /* Extend the buffers, if the buffers have run out. */
4042 static reg_errcode_t
4044 extend_buffers (re_match_context_t *mctx)
4047 re_string_t *pstr = &mctx->input;
4049 /* Double the lengthes of the buffers. */
4050 ret = re_string_realloc_buffers (pstr, pstr->bufs_len * 2);
4051 if (BE (ret != REG_NOERROR, 0))
4054 if (mctx->state_log != NULL)
4056 /* And double the length of state_log. */
4057 /* XXX We have no indication of the size of this buffer. If this
4058 allocation fail we have no indication that the state_log array
4059 does not have the right size. */
4060 re_dfastate_t **new_array = re_realloc (mctx->state_log, re_dfastate_t *,
4061 pstr->bufs_len + 1);
4062 if (BE (new_array == NULL, 0))
4064 mctx->state_log = new_array;
4067 /* Then reconstruct the buffers. */
4070 #ifdef RE_ENABLE_I18N
4071 if (pstr->mb_cur_max > 1)
4073 ret = build_wcs_upper_buffer (pstr);
4074 if (BE (ret != REG_NOERROR, 0))
4078 #endif /* RE_ENABLE_I18N */
4079 build_upper_buffer (pstr);
4083 #ifdef RE_ENABLE_I18N
4084 if (pstr->mb_cur_max > 1)
4085 build_wcs_buffer (pstr);
4087 #endif /* RE_ENABLE_I18N */
4089 if (pstr->trans != NULL)
4090 re_string_translate_buffer (pstr);
4097 /* Functions for matching context. */
4099 /* Initialize MCTX. */
4101 static reg_errcode_t
4103 match_ctx_init (re_match_context_t *mctx, int eflags, Idx n)
4105 mctx->eflags = eflags;
4106 mctx->match_last = REG_MISSING;
4109 mctx->bkref_ents = re_malloc (struct re_backref_cache_entry, n);
4110 mctx->sub_tops = re_malloc (re_sub_match_top_t *, n);
4111 if (BE (mctx->bkref_ents == NULL || mctx->sub_tops == NULL, 0))
4114 /* Already zero-ed by the caller.
4116 mctx->bkref_ents = NULL;
4117 mctx->nbkref_ents = 0;
4118 mctx->nsub_tops = 0; */
4119 mctx->abkref_ents = n;
4120 mctx->max_mb_elem_len = 1;
4121 mctx->asub_tops = n;
4125 /* Clean the entries which depend on the current input in MCTX.
4126 This function must be invoked when the matcher changes the start index
4127 of the input, or changes the input string. */
4131 match_ctx_clean (re_match_context_t *mctx)
4134 for (st_idx = 0; st_idx < mctx->nsub_tops; ++st_idx)
4137 re_sub_match_top_t *top = mctx->sub_tops[st_idx];
4138 for (sl_idx = 0; sl_idx < top->nlasts; ++sl_idx)
4140 re_sub_match_last_t *last = top->lasts[sl_idx];
4141 re_free (last->path.array);
4144 re_free (top->lasts);
4147 re_free (top->path->array);
4148 re_free (top->path);
4153 mctx->nsub_tops = 0;
4154 mctx->nbkref_ents = 0;
4157 /* Free all the memory associated with MCTX. */
4161 match_ctx_free (re_match_context_t *mctx)
4163 /* First, free all the memory associated with MCTX->SUB_TOPS. */
4164 match_ctx_clean (mctx);
4165 re_free (mctx->sub_tops);
4166 re_free (mctx->bkref_ents);
4169 /* Add a new backreference entry to MCTX.
4170 Note that we assume that caller never call this function with duplicate
4171 entry, and call with STR_IDX which isn't smaller than any existing entry.
4174 static reg_errcode_t
4176 match_ctx_add_entry (re_match_context_t *mctx, Idx node, Idx str_idx,
4179 if (mctx->nbkref_ents >= mctx->abkref_ents)
4181 struct re_backref_cache_entry* new_entry;
4182 new_entry = re_realloc (mctx->bkref_ents, struct re_backref_cache_entry,
4183 mctx->abkref_ents * 2);
4184 if (BE (new_entry == NULL, 0))
4186 re_free (mctx->bkref_ents);
4189 mctx->bkref_ents = new_entry;
4190 memset (mctx->bkref_ents + mctx->nbkref_ents, '\0',
4191 sizeof (struct re_backref_cache_entry) * mctx->abkref_ents);
4192 mctx->abkref_ents *= 2;
4194 if (mctx->nbkref_ents > 0
4195 && mctx->bkref_ents[mctx->nbkref_ents - 1].str_idx == str_idx)
4196 mctx->bkref_ents[mctx->nbkref_ents - 1].more = 1;
4198 mctx->bkref_ents[mctx->nbkref_ents].node = node;
4199 mctx->bkref_ents[mctx->nbkref_ents].str_idx = str_idx;
4200 mctx->bkref_ents[mctx->nbkref_ents].subexp_from = from;
4201 mctx->bkref_ents[mctx->nbkref_ents].subexp_to = to;
4203 /* This is a cache that saves negative results of check_dst_limits_calc_pos.
4204 If bit N is clear, means that this entry won't epsilon-transition to
4205 an OP_OPEN_SUBEXP or OP_CLOSE_SUBEXP for the N+1-th subexpression. If
4206 it is set, check_dst_limits_calc_pos_1 will recurse and try to find one
4209 A backreference does not epsilon-transition unless it is empty, so set
4210 to all zeros if FROM != TO. */
4211 mctx->bkref_ents[mctx->nbkref_ents].eps_reachable_subexps_map
4212 = (from == to ? -1 : 0);
4214 mctx->bkref_ents[mctx->nbkref_ents++].more = 0;
4215 if (mctx->max_mb_elem_len < to - from)
4216 mctx->max_mb_elem_len = to - from;
4220 /* Return the first entry with the same str_idx, or REG_MISSING if none is
4221 found. Note that MCTX->BKREF_ENTS is already sorted by MCTX->STR_IDX. */
4225 search_cur_bkref_entry (const re_match_context_t *mctx, Idx str_idx)
4227 Idx left, right, mid, last;
4228 last = right = mctx->nbkref_ents;
4229 for (left = 0; left < right;)
4231 mid = (left + right) / 2;
4232 if (mctx->bkref_ents[mid].str_idx < str_idx)
4237 if (left < last && mctx->bkref_ents[left].str_idx == str_idx)
4243 /* Register the node NODE, whose type is OP_OPEN_SUBEXP, and which matches
4246 static reg_errcode_t
4248 match_ctx_add_subtop (re_match_context_t *mctx, Idx node, Idx str_idx)
4251 assert (mctx->sub_tops != NULL);
4252 assert (mctx->asub_tops > 0);
4254 if (BE (mctx->nsub_tops == mctx->asub_tops, 0))
4256 Idx new_asub_tops = mctx->asub_tops * 2;
4257 re_sub_match_top_t **new_array = re_realloc (mctx->sub_tops,
4258 re_sub_match_top_t *,
4260 if (BE (new_array == NULL, 0))
4262 mctx->sub_tops = new_array;
4263 mctx->asub_tops = new_asub_tops;
4265 mctx->sub_tops[mctx->nsub_tops] = re_calloc (re_sub_match_top_t, 1);
4266 if (BE (mctx->sub_tops[mctx->nsub_tops] == NULL, 0))
4268 mctx->sub_tops[mctx->nsub_tops]->node = node;
4269 mctx->sub_tops[mctx->nsub_tops++]->str_idx = str_idx;
4273 /* Register the node NODE, whose type is OP_CLOSE_SUBEXP, and which matches
4274 at STR_IDX, whose corresponding OP_OPEN_SUBEXP is SUB_TOP. */
4276 static re_sub_match_last_t *
4278 match_ctx_add_sublast (re_sub_match_top_t *subtop, Idx node, Idx str_idx)
4280 re_sub_match_last_t *new_entry;
4281 if (BE (subtop->nlasts == subtop->alasts, 0))
4283 Idx new_alasts = 2 * subtop->alasts + 1;
4284 re_sub_match_last_t **new_array = re_realloc (subtop->lasts,
4285 re_sub_match_last_t *,
4287 if (BE (new_array == NULL, 0))
4289 subtop->lasts = new_array;
4290 subtop->alasts = new_alasts;
4292 new_entry = re_calloc (re_sub_match_last_t, 1);
4293 if (BE (new_entry != NULL, 1))
4295 subtop->lasts[subtop->nlasts] = new_entry;
4296 new_entry->node = node;
4297 new_entry->str_idx = str_idx;
4305 sift_ctx_init (re_sift_context_t *sctx,
4306 re_dfastate_t **sifted_sts,
4307 re_dfastate_t **limited_sts,
4308 Idx last_node, Idx last_str_idx)
4310 sctx->sifted_states = sifted_sts;
4311 sctx->limited_states = limited_sts;
4312 sctx->last_node = last_node;
4313 sctx->last_str_idx = last_str_idx;
4314 re_node_set_init_empty (&sctx->limits);