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 int 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, int node,
25 int str_idx, int from, int to)
27 static int search_cur_bkref_entry (re_match_context_t *mctx, int str_idx)
29 static reg_errcode_t match_ctx_add_subtop (re_match_context_t *mctx, int node,
30 int str_idx) internal_function;
31 static re_sub_match_last_t * match_ctx_add_sublast (re_sub_match_top_t *subtop,
32 int node, int str_idx)
34 static void sift_ctx_init (re_sift_context_t *sctx, re_dfastate_t **sifted_sts,
35 re_dfastate_t **limited_sts, int last_node,
38 static reg_errcode_t re_search_internal (const regex_t *preg,
39 const char *string, int length,
40 int start, int range, int stop,
41 size_t nmatch, regmatch_t pmatch[],
42 int eflags) internal_function;
43 static int re_search_2_stub (struct re_pattern_buffer *bufp,
44 const char *string1, int length1,
45 const char *string2, int length2,
46 int start, int range, struct re_registers *regs,
47 int stop, int ret_len) internal_function;
48 static int re_search_stub (struct re_pattern_buffer *bufp,
49 const char *string, int length, int start,
50 int range, int stop, struct re_registers *regs,
51 int ret_len) internal_function;
52 static unsigned re_copy_regs (struct re_registers *regs, regmatch_t *pmatch,
53 int nregs, int regs_allocated) internal_function;
54 static reg_errcode_t prune_impossible_nodes (re_match_context_t *mctx)
56 static int check_matching (re_match_context_t *mctx, int fl_longest_match,
59 static int check_halt_state_context (const re_match_context_t *mctx,
60 const re_dfastate_t *state, int idx)
62 static void update_regs (re_dfa_t *dfa, regmatch_t *pmatch,
63 regmatch_t *prev_idx_match, int cur_node,
64 int cur_idx, int nmatch) internal_function;
65 static reg_errcode_t push_fail_stack (struct re_fail_stack_t *fs,
66 int str_idx, int dest_node, int nregs,
68 re_node_set *eps_via_nodes) internal_function;
69 static reg_errcode_t set_regs (const regex_t *preg,
70 const re_match_context_t *mctx,
71 size_t nmatch, regmatch_t *pmatch,
72 int fl_backtrack) internal_function;
73 static reg_errcode_t free_fail_stack_return (struct re_fail_stack_t *fs) internal_function;
76 static int sift_states_iter_mb (const re_match_context_t *mctx,
77 re_sift_context_t *sctx,
78 int node_idx, int str_idx, int max_str_idx) internal_function;
79 #endif /* RE_ENABLE_I18N */
80 static reg_errcode_t sift_states_backward (re_match_context_t *mctx,
81 re_sift_context_t *sctx) internal_function;
82 static reg_errcode_t build_sifted_states (re_match_context_t *mctx,
83 re_sift_context_t *sctx, int str_idx,
84 re_node_set *cur_dest) internal_function;
85 static reg_errcode_t update_cur_sifted_state (re_match_context_t *mctx,
86 re_sift_context_t *sctx,
88 re_node_set *dest_nodes) internal_function;
89 static reg_errcode_t add_epsilon_src_nodes (re_dfa_t *dfa,
90 re_node_set *dest_nodes,
91 const re_node_set *candidates) internal_function;
92 static int check_dst_limits (re_match_context_t *mctx, re_node_set *limits,
93 int dst_node, int dst_idx, int src_node,
94 int src_idx) internal_function;
95 static int check_dst_limits_calc_pos_1 (re_match_context_t *mctx,
96 int boundaries, int subexp_idx,
97 int from_node, int bkref_idx) internal_function;
98 static int check_dst_limits_calc_pos (re_match_context_t *mctx,
99 int limit, int subexp_idx,
100 int node, int str_idx,
101 int bkref_idx) internal_function;
102 static reg_errcode_t check_subexp_limits (re_dfa_t *dfa,
103 re_node_set *dest_nodes,
104 const re_node_set *candidates,
106 struct re_backref_cache_entry *bkref_ents,
107 int str_idx) internal_function;
108 static reg_errcode_t sift_states_bkref (re_match_context_t *mctx,
109 re_sift_context_t *sctx,
110 int str_idx, const re_node_set *candidates) internal_function;
111 static reg_errcode_t merge_state_array (re_dfa_t *dfa, re_dfastate_t **dst,
112 re_dfastate_t **src, int num) internal_function;
113 static re_dfastate_t *find_recover_state (reg_errcode_t *err,
114 re_match_context_t *mctx) internal_function;
115 static re_dfastate_t *transit_state (reg_errcode_t *err,
116 re_match_context_t *mctx,
117 re_dfastate_t *state) internal_function;
118 static re_dfastate_t *merge_state_with_log (reg_errcode_t *err,
119 re_match_context_t *mctx,
120 re_dfastate_t *next_state) internal_function;
121 static reg_errcode_t check_subexp_matching_top (re_match_context_t *mctx,
122 re_node_set *cur_nodes,
123 int str_idx) internal_function;
125 static re_dfastate_t *transit_state_sb (reg_errcode_t *err,
126 re_match_context_t *mctx,
127 re_dfastate_t *pstate) internal_function;
129 #ifdef RE_ENABLE_I18N
130 static reg_errcode_t transit_state_mb (re_match_context_t *mctx,
131 re_dfastate_t *pstate) internal_function;
132 #endif /* RE_ENABLE_I18N */
133 static reg_errcode_t transit_state_bkref (re_match_context_t *mctx,
134 const re_node_set *nodes) internal_function;
135 static reg_errcode_t get_subexp (re_match_context_t *mctx,
136 int bkref_node, int bkref_str_idx) internal_function;
137 static reg_errcode_t get_subexp_sub (re_match_context_t *mctx,
138 const re_sub_match_top_t *sub_top,
139 re_sub_match_last_t *sub_last,
140 int bkref_node, int bkref_str) internal_function;
141 static int find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
142 int subexp_idx, int type) internal_function;
143 static reg_errcode_t check_arrival (re_match_context_t *mctx,
144 state_array_t *path, int top_node,
145 int top_str, int last_node, int last_str,
146 int type) internal_function;
147 static reg_errcode_t check_arrival_add_next_nodes (re_match_context_t *mctx,
149 re_node_set *cur_nodes,
150 re_node_set *next_nodes) internal_function;
151 static reg_errcode_t check_arrival_expand_ecl (re_dfa_t *dfa,
152 re_node_set *cur_nodes,
153 int ex_subexp, int type) internal_function;
154 static reg_errcode_t check_arrival_expand_ecl_sub (re_dfa_t *dfa,
155 re_node_set *dst_nodes,
156 int target, int ex_subexp,
157 int type) internal_function;
158 static reg_errcode_t expand_bkref_cache (re_match_context_t *mctx,
159 re_node_set *cur_nodes, int cur_str,
160 int subexp_num, int type) internal_function;
161 static int build_trtable (re_dfa_t *dfa,
162 re_dfastate_t *state) internal_function;
163 #ifdef RE_ENABLE_I18N
164 static int check_node_accept_bytes (re_dfa_t *dfa, int node_idx,
165 const re_string_t *input, int idx) internal_function;
167 static unsigned int find_collation_sequence_value (const unsigned char *mbs,
168 size_t name_len) internal_function;
170 #endif /* RE_ENABLE_I18N */
171 static int group_nodes_into_DFAstates (re_dfa_t *dfa,
172 const re_dfastate_t *state,
173 re_node_set *states_node,
174 bitset *states_ch) internal_function;
175 static int check_node_accept (const re_match_context_t *mctx,
176 const re_token_t *node, int idx) internal_function;
177 static reg_errcode_t extend_buffers (re_match_context_t *mctx) internal_function;
179 /* Entry point for POSIX code. */
181 /* regexec searches for a given pattern, specified by PREG, in the
184 If NMATCH is zero or REG_NOSUB was set in the cflags argument to
185 `regcomp', we ignore PMATCH. Otherwise, we assume PMATCH has at
186 least NMATCH elements, and we set them to the offsets of the
187 corresponding matched substrings.
189 EFLAGS specifies `execution flags' which affect matching: if
190 REG_NOTBOL is set, then ^ does not match at the beginning of the
191 string; if REG_NOTEOL is set, then $ does not match at the end.
193 We return 0 if we find a match and REG_NOMATCH if not. */
196 regexec (const regex_t *__restrict preg, const char *__restrict string,
197 size_t nmatch, regmatch_t pmatch[], int eflags)
202 re_dfa_t *dfa = (re_dfa_t *) preg->re_buffer;
205 if (eflags & ~(REG_NOTBOL | REG_NOTEOL | REG_STARTEND))
208 if (eflags & REG_STARTEND)
210 start = pmatch[0].rm_so;
211 length = pmatch[0].rm_eo;
216 length = strlen (string);
219 __libc_lock_lock (dfa->lock);
221 err = re_search_internal (preg, string, length, start, length - start,
222 length, 0, NULL, eflags);
224 err = re_search_internal (preg, string, length, start, length - start,
225 length, nmatch, pmatch, eflags);
226 __libc_lock_unlock (dfa->lock);
227 return err != REG_NOERROR;
231 # include <shlib-compat.h>
232 versioned_symbol (libc, __regexec, regexec, GLIBC_2_3_4);
234 # if SHLIB_COMPAT (libc, GLIBC_2_0, GLIBC_2_3_4)
235 __typeof__ (__regexec) __compat_regexec;
238 attribute_compat_text_section
239 __compat_regexec (const regex_t *__restrict preg,
240 const char *__restrict string, size_t nmatch,
241 regmatch_t pmatch[], int eflags)
243 return regexec (preg, string, nmatch, pmatch,
244 eflags & (REG_NOTBOL | REG_NOTEOL));
246 compat_symbol (libc, __compat_regexec, regexec, GLIBC_2_0);
250 /* Entry points for GNU code. */
252 /* re_match, re_search, re_match_2, re_search_2
254 The former two functions operate on STRING with length LENGTH,
255 while the later two operate on concatenation of STRING1 and STRING2
256 with lengths LENGTH1 and LENGTH2, respectively.
258 re_match() matches the compiled pattern in BUFP against the string,
259 starting at index START.
261 re_search() first tries matching at index START, then it tries to match
262 starting from index START + 1, and so on. The last start position tried
263 is START + RANGE. (Thus RANGE = 0 forces re_search to operate the same
266 The parameter STOP of re_{match,search}_2 specifies that no match exceeding
267 the first STOP characters of the concatenation of the strings should be
270 If REGS is not NULL, and BUFP->re_no_sub is not set, the offsets of the match
271 and all groups is stroed in REGS. (For the "_2" variants, the offsets are
272 computed relative to the concatenation, not relative to the individual
275 On success, re_match* functions return the length of the match, re_search*
276 return the position of the start of the match. Return value -1 means no
277 match was found and -2 indicates an internal error. */
280 re_match (struct re_pattern_buffer *bufp, const char *string,
281 int length, int start, struct re_registers *regs)
283 return re_search_stub (bufp, string, length, start, 0, length, regs, 1);
286 weak_alias (__re_match, re_match)
290 re_search (struct re_pattern_buffer *bufp, const char *string,
291 int length, int start, int range, struct re_registers *regs)
293 return re_search_stub (bufp, string, length, start, range, length, regs, 0);
296 weak_alias (__re_search, re_search)
300 re_match_2 (struct re_pattern_buffer *bufp,
301 const char *string1, int length1,
302 const char *string2, int length2,
303 int start, struct re_registers *regs, int stop)
305 return re_search_2_stub (bufp, string1, length1, string2, length2,
306 start, 0, regs, stop, 1);
309 weak_alias (__re_match_2, re_match_2)
313 re_search_2 (struct re_pattern_buffer *bufp,
314 const char *string1, int length1,
315 const char *string2, int length2,
316 int start, int range, struct re_registers *regs, int stop)
318 return re_search_2_stub (bufp, string1, length1, string2, length2,
319 start, range, regs, stop, 0);
322 weak_alias (__re_search_2, re_search_2)
327 re_search_2_stub (struct re_pattern_buffer *bufp,
328 const char *string1, int length1,
329 const char *string2, int length2,
330 int start, int range, struct re_registers *regs, int stop,
335 int len = length1 + length2;
338 if (BE (length1 < 0 || length2 < 0 || stop < 0, 0))
341 /* Concatenate the strings. */
345 char *s = re_malloc (char, len);
347 if (BE (s == NULL, 0))
349 memcpy (s, string1, length1);
350 memcpy (s + length1, string2, length2);
359 rval = re_search_stub (bufp, str, len, start, range, stop, regs,
362 re_free ((char *) str);
366 /* The parameters have the same meaning as those of re_search.
367 Additional parameters:
368 If RET_LEN is nonzero the length of the match is returned (re_match style);
369 otherwise the position of the match is returned. */
373 re_search_stub (struct re_pattern_buffer *bufp,
374 const char *string, int length,
375 int start, int range, int stop, struct re_registers *regs,
378 reg_errcode_t result;
383 re_dfa_t *dfa = (re_dfa_t *) bufp->re_buffer;
386 /* Check for out-of-range. */
387 if (BE (start < 0 || start > length, 0))
389 if (BE (start + range > length, 0))
390 range = length - start;
391 else if (BE (start + range < 0, 0))
394 __libc_lock_lock (dfa->lock);
396 eflags |= (bufp->re_not_bol) ? REG_NOTBOL : 0;
397 eflags |= (bufp->re_not_eol) ? REG_NOTEOL : 0;
399 /* Compile fastmap if we haven't yet. */
400 if (range > 0 && bufp->re_fastmap != NULL && !bufp->re_fastmap_accurate)
401 re_compile_fastmap (bufp);
403 if (BE (bufp->re_no_sub, 0))
406 /* We need at least 1 register. */
409 else if (BE (bufp->re_regs_allocated == REG_FIXED
410 && regs->rm_num_regs < bufp->re_nsub + 1, 0))
412 nregs = regs->rm_num_regs;
413 if (BE (nregs < 1, 0))
415 /* Nothing can be copied to regs. */
421 nregs = bufp->re_nsub + 1;
422 pmatch = re_malloc (regmatch_t, nregs);
423 if (BE (pmatch == NULL, 0))
429 result = re_search_internal (bufp, string, length, start, range, stop,
430 nregs, pmatch, eflags);
434 /* I hope we needn't fill ther regs with -1's when no match was found. */
435 if (result != REG_NOERROR)
437 else if (regs != NULL)
439 /* If caller wants register contents data back, copy them. */
440 bufp->re_regs_allocated = re_copy_regs (regs, pmatch, nregs,
441 bufp->re_regs_allocated);
442 if (BE (bufp->re_regs_allocated == REG_UNALLOCATED, 0))
446 if (BE (rval == 0, 1))
450 assert (pmatch[0].rm_so == start);
451 rval = pmatch[0].rm_eo - start;
454 rval = pmatch[0].rm_so;
458 __libc_lock_unlock (dfa->lock);
464 re_copy_regs (struct re_registers *regs, regmatch_t *pmatch, int nregs,
467 int rval = REG_REALLOCATE;
469 int need_regs = nregs + 1;
470 /* We need one extra element beyond `rm_num_regs' for the `-1' marker GNU code
473 /* Have the register data arrays been allocated? */
474 if (regs_allocated == REG_UNALLOCATED)
475 { /* No. So allocate them with malloc. */
476 regs->rm_start = re_malloc (regoff_t, need_regs);
477 regs->rm_end = re_malloc (regoff_t, need_regs);
478 if (BE (regs->rm_start == NULL, 0) || BE (regs->rm_end == NULL, 0))
479 return REG_UNALLOCATED;
480 regs->rm_num_regs = need_regs;
482 else if (regs_allocated == REG_REALLOCATE)
483 { /* Yes. If we need more elements than were already
484 allocated, reallocate them. If we need fewer, just
486 if (BE (need_regs > regs->rm_num_regs, 0))
488 regoff_t *new_start =
489 re_realloc (regs->rm_start, regoff_t, need_regs);
490 regoff_t *new_end = re_realloc (regs->rm_end, regoff_t, need_regs);
491 if (BE (new_start == NULL, 0) || BE (new_end == NULL, 0))
492 return REG_UNALLOCATED;
493 regs->rm_start = new_start;
494 regs->rm_end = new_end;
495 regs->rm_num_regs = need_regs;
500 assert (regs_allocated == REG_FIXED);
501 /* This function may not be called with REG_FIXED and nregs too big. */
502 assert (regs->rm_num_regs >= nregs);
507 for (i = 0; i < nregs; ++i)
509 regs->rm_start[i] = pmatch[i].rm_so;
510 regs->rm_end[i] = pmatch[i].rm_eo;
512 for ( ; i < regs->rm_num_regs; ++i)
513 regs->rm_start[i] = regs->rm_end[i] = -1;
518 /* Set REGS to hold NUM_REGS registers, storing them in STARTS and
519 ENDS. Subsequent matches using PATTERN_BUFFER and REGS will use
520 this memory for recording register information. STARTS and ENDS
521 must be allocated using the malloc library routine, and must each
522 be at least NUM_REGS * sizeof (regoff_t) bytes long.
524 If NUM_REGS == 0, then subsequent matches should allocate their own
527 Unless this function is called, the first search or match using
528 PATTERN_BUFFER will allocate its own register data, without
529 freeing the old data. */
532 re_set_registers (struct re_pattern_buffer *bufp, struct re_registers *regs,
533 unsigned int num_regs, regoff_t *starts, regoff_t *ends)
537 bufp->re_regs_allocated = REG_REALLOCATE;
538 regs->rm_num_regs = num_regs;
539 regs->rm_start = starts;
544 bufp->re_regs_allocated = REG_UNALLOCATED;
545 regs->rm_num_regs = 0;
546 regs->rm_start = regs->rm_end = NULL;
550 weak_alias (__re_set_registers, re_set_registers)
553 /* Entry points compatible with 4.2 BSD regex library. We don't define
554 them unless specifically requested. */
556 #if defined _REGEX_RE_COMP || defined _LIBC
564 return 0 == regexec (&re_comp_buf, s, 0, NULL, 0);
566 #endif /* _REGEX_RE_COMP */
568 /* Internal entry point. */
570 /* Searches for a compiled pattern PREG in the string STRING, whose
571 length is LENGTH. NMATCH, PMATCH, and EFLAGS have the same
572 mingings with regexec. START, and RANGE have the same meanings
574 Return REG_NOERROR if we find a match, and REG_NOMATCH if not,
575 otherwise return the error code.
576 Note: We assume front end functions already check ranges.
577 (START + RANGE >= 0 && START + RANGE <= LENGTH) */
581 re_search_internal (const regex_t *preg,
582 const char *string, int length,
583 int start, int range, int stop,
584 size_t nmatch, regmatch_t pmatch[],
588 re_dfa_t *dfa = (re_dfa_t *) preg->re_buffer;
589 int left_lim, right_lim, incr;
590 int fl_longest_match, match_first, match_kind, match_last = -1;
593 #if defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L)
594 re_match_context_t mctx = { .dfa = dfa };
596 re_match_context_t mctx;
598 char *fastmap = (preg->re_fastmap != NULL && preg->re_fastmap_accurate
599 && range && !preg->re_can_be_null) ? preg->re_fastmap : NULL;
600 unsigned REG_TRANSLATE_TYPE t =
601 (unsigned REG_TRANSLATE_TYPE) preg->re_translate;
603 #if !(defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L))
604 memset (&mctx, '\0', sizeof (re_match_context_t));
608 extra_nmatch = (nmatch > preg->re_nsub) ? nmatch - (preg->re_nsub + 1) : 0;
609 nmatch -= extra_nmatch;
611 /* Check if the DFA haven't been compiled. */
612 if (BE (preg->re_used == 0 || dfa->init_state == NULL
613 || dfa->init_state_word == NULL || dfa->init_state_nl == NULL
614 || dfa->init_state_begbuf == NULL, 0))
618 /* We assume front-end functions already check them. */
619 assert (start + range >= 0 && start + range <= length);
622 /* If initial states with non-begbuf contexts have no elements,
623 the regex must be anchored. If preg->re_newline_anchor is set,
624 we'll never use init_state_nl, so do not check it. */
625 if (dfa->init_state->nodes.nelem == 0
626 && dfa->init_state_word->nodes.nelem == 0
627 && (dfa->init_state_nl->nodes.nelem == 0
628 || !preg->re_newline_anchor))
630 if (start != 0 && start + range != 0)
635 /* We must check the longest matching, if nmatch > 0. */
636 fl_longest_match = (nmatch != 0 || dfa->nbackref);
638 err = re_string_allocate (&mctx.input, string, length, dfa->nodes_len + 1,
640 preg->re_syntax & REG_IGNORE_CASE, dfa);
641 if (BE (err != REG_NOERROR, 0))
643 mctx.input.stop = stop;
644 mctx.input.raw_stop = stop;
645 mctx.input.newline_anchor = preg->re_newline_anchor;
647 err = match_ctx_init (&mctx, eflags, dfa->nbackref * 2);
648 if (BE (err != REG_NOERROR, 0))
651 /* We will log all the DFA states through which the dfa pass,
652 if nmatch > 1, or this dfa has "multibyte node", which is a
653 back-reference or a node which can accept multibyte character or
654 multi character collating element. */
655 if (nmatch > 1 || dfa->has_mb_node)
657 mctx.state_log = re_malloc (re_dfastate_t *, mctx.input.bufs_len + 1);
658 if (BE (mctx.state_log == NULL, 0))
665 mctx.state_log = NULL;
668 mctx.input.tip_context = (eflags & REG_NOTBOL) ? CONTEXT_BEGBUF
669 : CONTEXT_NEWLINE | CONTEXT_BEGBUF;
671 /* Check incrementally whether of not the input string match. */
672 incr = (range < 0) ? -1 : 1;
673 left_lim = (range < 0) ? start + range : start;
674 right_lim = (range < 0) ? start : start + range;
675 sb = dfa->mb_cur_max == 1;
678 ? ((sb || !(preg->re_syntax & REG_IGNORE_CASE || t) ? 4 : 0)
679 | (range >= 0 ? 2 : 0)
680 | (t != NULL ? 1 : 0))
683 for (;; match_first += incr)
686 if (match_first < left_lim || right_lim < match_first)
689 /* Advance as rapidly as possible through the string, until we
690 find a plausible place to start matching. This may be done
691 with varying efficiency, so there are various possibilities:
692 only the most common of them are specialized, in order to
693 save on code size. We use a switch statement for speed. */
701 /* Fastmap with single-byte translation, match forward. */
702 while (BE (match_first < right_lim, 1)
703 && !fastmap[t[(unsigned char) string[match_first]]])
705 goto forward_match_found_start_or_reached_end;
708 /* Fastmap without translation, match forward. */
709 while (BE (match_first < right_lim, 1)
710 && !fastmap[(unsigned char) string[match_first]])
713 forward_match_found_start_or_reached_end:
714 if (BE (match_first == right_lim, 0))
716 ch = match_first >= length
717 ? 0 : (unsigned char) string[match_first];
718 if (!fastmap[t ? t[ch] : ch])
725 /* Fastmap without multi-byte translation, match backwards. */
726 while (match_first >= left_lim)
728 ch = match_first >= length
729 ? 0 : (unsigned char) string[match_first];
730 if (fastmap[t ? t[ch] : ch])
734 if (match_first < left_lim)
739 /* In this case, we can't determine easily the current byte,
740 since it might be a component byte of a multibyte
741 character. Then we use the constructed buffer instead. */
744 /* If MATCH_FIRST is out of the valid range, reconstruct the
746 unsigned int offset = match_first - mctx.input.raw_mbs_idx;
747 if (BE (offset >= (unsigned int) mctx.input.valid_raw_len, 0))
749 err = re_string_reconstruct (&mctx.input, match_first,
751 if (BE (err != REG_NOERROR, 0))
754 offset = match_first - mctx.input.raw_mbs_idx;
756 /* If MATCH_FIRST is out of the buffer, leave it as '\0'.
757 Note that MATCH_FIRST must not be smaller than 0. */
758 ch = (match_first >= length
759 ? 0 : re_string_byte_at (&mctx.input, offset));
763 if (match_first < left_lim || match_first > right_lim)
772 /* Reconstruct the buffers so that the matcher can assume that
773 the matching starts from the beginning of the buffer. */
774 err = re_string_reconstruct (&mctx.input, match_first, eflags);
775 if (BE (err != REG_NOERROR, 0))
778 #ifdef RE_ENABLE_I18N
779 /* Don't consider this char as a possible match start if it part,
780 yet isn't the head, of a multibyte character. */
781 if (!sb && !re_string_first_byte (&mctx.input, 0))
785 /* It seems to be appropriate one, then use the matcher. */
786 /* We assume that the matching starts from 0. */
787 mctx.state_log_top = mctx.nbkref_ents = mctx.max_mb_elem_len = 0;
788 match_last = check_matching (&mctx, fl_longest_match,
789 range >= 0 ? &match_first : NULL);
790 if (match_last != -1)
792 if (BE (match_last == -2, 0))
799 mctx.match_last = match_last;
800 if ((!preg->re_no_sub && nmatch > 1) || dfa->nbackref)
802 re_dfastate_t *pstate = mctx.state_log[match_last];
803 mctx.last_node = check_halt_state_context (&mctx, pstate,
806 if ((!preg->re_no_sub && nmatch > 1 && dfa->has_plural_match)
809 err = prune_impossible_nodes (&mctx);
810 if (err == REG_NOERROR)
812 if (BE (err != REG_NOMATCH, 0))
817 break; /* We found a match. */
821 match_ctx_clean (&mctx);
825 assert (match_last != -1);
826 assert (err == REG_NOERROR);
829 /* Set pmatch[] if we need. */
834 /* Initialize registers. */
835 for (reg_idx = 1; reg_idx < nmatch; ++reg_idx)
836 pmatch[reg_idx].rm_so = pmatch[reg_idx].rm_eo = -1;
838 /* Set the points where matching start/end. */
840 pmatch[0].rm_eo = mctx.match_last;
842 if (!preg->re_no_sub && nmatch > 1)
844 err = set_regs (preg, &mctx, nmatch, pmatch,
845 dfa->has_plural_match && dfa->nbackref > 0);
846 if (BE (err != REG_NOERROR, 0))
850 /* At last, add the offset to the each registers, since we slided
851 the buffers so that we could assume that the matching starts
853 for (reg_idx = 0; reg_idx < nmatch; ++reg_idx)
854 if (pmatch[reg_idx].rm_so != -1)
856 #ifdef RE_ENABLE_I18N
857 if (BE (mctx.input.offsets_needed != 0, 0))
859 if (pmatch[reg_idx].rm_so == mctx.input.valid_len)
860 pmatch[reg_idx].rm_so += mctx.input.valid_raw_len - mctx.input.valid_len;
862 pmatch[reg_idx].rm_so = mctx.input.offsets[pmatch[reg_idx].rm_so];
863 if (pmatch[reg_idx].rm_eo == mctx.input.valid_len)
864 pmatch[reg_idx].rm_eo += mctx.input.valid_raw_len - mctx.input.valid_len;
866 pmatch[reg_idx].rm_eo = mctx.input.offsets[pmatch[reg_idx].rm_eo];
869 assert (mctx.input.offsets_needed == 0);
871 pmatch[reg_idx].rm_so += match_first;
872 pmatch[reg_idx].rm_eo += match_first;
874 for (reg_idx = 0; reg_idx < extra_nmatch; ++reg_idx)
876 pmatch[nmatch + reg_idx].rm_so = -1;
877 pmatch[nmatch + reg_idx].rm_eo = -1;
881 for (reg_idx = 0; reg_idx + 1 < nmatch; reg_idx++)
882 if (dfa->subexp_map[reg_idx] != reg_idx)
884 pmatch[reg_idx + 1].rm_so
885 = pmatch[dfa->subexp_map[reg_idx] + 1].rm_so;
886 pmatch[reg_idx + 1].rm_eo
887 = pmatch[dfa->subexp_map[reg_idx] + 1].rm_eo;
892 re_free (mctx.state_log);
894 match_ctx_free (&mctx);
895 re_string_destruct (&mctx.input);
901 prune_impossible_nodes (re_match_context_t *mctx)
903 re_dfa_t *const dfa = mctx->dfa;
904 int halt_node, match_last;
906 re_dfastate_t **sifted_states;
907 re_dfastate_t **lim_states = NULL;
908 re_sift_context_t sctx;
910 assert (mctx->state_log != NULL);
912 match_last = mctx->match_last;
913 halt_node = mctx->last_node;
914 sifted_states = re_malloc (re_dfastate_t *, match_last + 1);
915 if (BE (sifted_states == NULL, 0))
922 lim_states = re_malloc (re_dfastate_t *, match_last + 1);
923 if (BE (lim_states == NULL, 0))
930 memset (lim_states, '\0',
931 sizeof (re_dfastate_t *) * (match_last + 1));
932 sift_ctx_init (&sctx, sifted_states, lim_states, halt_node,
934 ret = sift_states_backward (mctx, &sctx);
935 re_node_set_free (&sctx.limits);
936 if (BE (ret != REG_NOERROR, 0))
938 if (sifted_states[0] != NULL || lim_states[0] != NULL)
948 } while (mctx->state_log[match_last] == NULL
949 || !mctx->state_log[match_last]->halt);
950 halt_node = check_halt_state_context (mctx,
951 mctx->state_log[match_last],
954 ret = merge_state_array (dfa, sifted_states, lim_states,
956 re_free (lim_states);
958 if (BE (ret != REG_NOERROR, 0))
963 sift_ctx_init (&sctx, sifted_states, lim_states, halt_node, match_last);
964 ret = sift_states_backward (mctx, &sctx);
965 re_node_set_free (&sctx.limits);
966 if (BE (ret != REG_NOERROR, 0))
969 re_free (mctx->state_log);
970 mctx->state_log = sifted_states;
971 sifted_states = NULL;
972 mctx->last_node = halt_node;
973 mctx->match_last = match_last;
976 re_free (sifted_states);
977 re_free (lim_states);
981 /* Acquire an initial state and return it.
982 We must select appropriate initial state depending on the context,
983 since initial states may have constraints like "\<", "^", etc.. */
985 static inline re_dfastate_t *
986 __attribute ((always_inline)) internal_function
987 acquire_init_state_context (reg_errcode_t *err, const re_match_context_t *mctx,
990 re_dfa_t *const dfa = mctx->dfa;
991 if (dfa->init_state->has_constraint)
993 unsigned int context;
994 context = re_string_context_at (&mctx->input, idx - 1, mctx->eflags);
995 if (IS_WORD_CONTEXT (context))
996 return dfa->init_state_word;
997 else if (IS_ORDINARY_CONTEXT (context))
998 return dfa->init_state;
999 else if (IS_BEGBUF_CONTEXT (context) && IS_NEWLINE_CONTEXT (context))
1000 return dfa->init_state_begbuf;
1001 else if (IS_NEWLINE_CONTEXT (context))
1002 return dfa->init_state_nl;
1003 else if (IS_BEGBUF_CONTEXT (context))
1005 /* It is relatively rare case, then calculate on demand. */
1006 return re_acquire_state_context (err, dfa,
1007 dfa->init_state->entrance_nodes,
1011 /* Must not happen? */
1012 return dfa->init_state;
1015 return dfa->init_state;
1018 /* Check whether the regular expression match input string INPUT or not,
1019 and return the index where the matching end, return -1 if not match,
1020 or return -2 in case of an error.
1021 FL_LONGEST_MATCH means we want the POSIX longest matching.
1022 If P_MATCH_FIRST is not NULL, and the match fails, it is set to the
1023 next place where we may want to try matching.
1024 Note that the matcher assume that the maching starts from the current
1025 index of the buffer. */
1029 check_matching (re_match_context_t *mctx, int fl_longest_match,
1032 re_dfa_t *const dfa = mctx->dfa;
1035 int match_last = -1;
1036 int cur_str_idx = re_string_cur_idx (&mctx->input);
1037 re_dfastate_t *cur_state;
1038 int at_init_state = p_match_first != NULL;
1039 int next_start_idx = cur_str_idx;
1042 cur_state = acquire_init_state_context (&err, mctx, cur_str_idx);
1043 /* An initial state must not be NULL (invalid). */
1044 if (BE (cur_state == NULL, 0))
1046 assert (err == REG_ESPACE);
1050 if (mctx->state_log != NULL)
1052 mctx->state_log[cur_str_idx] = cur_state;
1054 /* Check OP_OPEN_SUBEXP in the initial state in case that we use them
1055 later. E.g. Processing back references. */
1056 if (BE (dfa->nbackref, 0))
1059 err = check_subexp_matching_top (mctx, &cur_state->nodes, 0);
1060 if (BE (err != REG_NOERROR, 0))
1063 if (cur_state->has_backref)
1065 err = transit_state_bkref (mctx, &cur_state->nodes);
1066 if (BE (err != REG_NOERROR, 0))
1072 /* If the RE accepts NULL string. */
1073 if (BE (cur_state->halt, 0))
1075 if (!cur_state->has_constraint
1076 || check_halt_state_context (mctx, cur_state, cur_str_idx))
1078 if (!fl_longest_match)
1082 match_last = cur_str_idx;
1088 while (!re_string_eoi (&mctx->input))
1090 re_dfastate_t *old_state = cur_state;
1091 int next_char_idx = re_string_cur_idx (&mctx->input) + 1;
1093 if (BE (next_char_idx >= mctx->input.bufs_len, 0)
1094 || (BE (next_char_idx >= mctx->input.valid_len, 0)
1095 && mctx->input.valid_len < mctx->input.len))
1097 err = extend_buffers (mctx);
1098 if (BE (err != REG_NOERROR, 0))
1100 assert (err == REG_ESPACE);
1105 cur_state = transit_state (&err, mctx, cur_state);
1106 if (mctx->state_log != NULL)
1107 cur_state = merge_state_with_log (&err, mctx, cur_state);
1109 if (cur_state == NULL)
1111 /* Reached the invalid state or an error. Try to recover a valid
1112 state using the state log, if available and if we have not
1113 already found a valid (even if not the longest) match. */
1114 if (BE (err != REG_NOERROR, 0))
1117 if (mctx->state_log == NULL
1118 || (match && !fl_longest_match)
1119 || (cur_state = find_recover_state (&err, mctx)) == NULL)
1123 if (BE (at_init_state, 0))
1125 if (old_state == cur_state)
1126 next_start_idx = next_char_idx;
1131 if (cur_state->halt)
1133 /* Reached a halt state.
1134 Check the halt state can satisfy the current context. */
1135 if (!cur_state->has_constraint
1136 || check_halt_state_context (mctx, cur_state,
1137 re_string_cur_idx (&mctx->input)))
1139 /* We found an appropriate halt state. */
1140 match_last = re_string_cur_idx (&mctx->input);
1143 /* We found a match, do not modify match_first below. */
1144 p_match_first = NULL;
1145 if (!fl_longest_match)
1152 *p_match_first += next_start_idx;
1157 /* Check NODE match the current context. */
1161 check_halt_node_context (const re_dfa_t *dfa, int node, unsigned int context)
1163 re_token_type_t type = dfa->nodes[node].type;
1164 unsigned int constraint = dfa->nodes[node].constraint;
1165 if (type != END_OF_RE)
1169 if (NOT_SATISFY_NEXT_CONSTRAINT (constraint, context))
1174 /* Check the halt state STATE match the current context.
1175 Return 0 if not match, if the node, STATE has, is a halt node and
1176 match the context, return the node. */
1180 check_halt_state_context (const re_match_context_t *mctx,
1181 const re_dfastate_t *state, int idx)
1184 unsigned int context;
1186 assert (state->halt);
1188 context = re_string_context_at (&mctx->input, idx, mctx->eflags);
1189 for (i = 0; i < state->nodes.nelem; ++i)
1190 if (check_halt_node_context (mctx->dfa, state->nodes.elems[i], context))
1191 return state->nodes.elems[i];
1195 /* Compute the next node to which "NFA" transit from NODE("NFA" is a NFA
1196 corresponding to the DFA).
1197 Return the destination node, and update EPS_VIA_NODES, return -1 in case
1202 proceed_next_node (const re_match_context_t *mctx,
1203 int nregs, regmatch_t *regs, int *pidx, int node,
1204 re_node_set *eps_via_nodes, struct re_fail_stack_t *fs)
1206 re_dfa_t *const dfa = mctx->dfa;
1208 if (IS_EPSILON_NODE (dfa->nodes[node].type))
1210 re_node_set *cur_nodes = &mctx->state_log[*pidx]->nodes;
1211 re_node_set *edests = &dfa->edests[node];
1213 err = re_node_set_insert (eps_via_nodes, node);
1214 if (BE (err < 0, 0))
1216 /* Pick up a valid destination, or return -1 if none is found. */
1217 for (dest_node = -1, i = 0; i < edests->nelem; ++i)
1219 int candidate = edests->elems[i];
1220 if (!re_node_set_contains (cur_nodes, candidate))
1222 if (dest_node == -1)
1223 dest_node = candidate;
1227 /* In order to avoid infinite loop like "(a*)*", return the second
1228 epsilon-transition if the first was already considered. */
1229 if (re_node_set_contains (eps_via_nodes, dest_node))
1232 /* Otherwise, push the second epsilon-transition on the fail stack. */
1234 && push_fail_stack (fs, *pidx, candidate, nregs, regs,
1238 /* We know we are going to exit. */
1247 re_token_type_t type = dfa->nodes[node].type;
1249 #ifdef RE_ENABLE_I18N
1250 if (dfa->nodes[node].accept_mb)
1251 naccepted = check_node_accept_bytes (dfa, node, &mctx->input, *pidx);
1253 #endif /* RE_ENABLE_I18N */
1254 if (type == OP_BACK_REF)
1256 int subexp_idx = dfa->nodes[node].opr.idx + 1;
1257 naccepted = regs[subexp_idx].rm_eo - regs[subexp_idx].rm_so;
1260 if (regs[subexp_idx].rm_so == -1 || regs[subexp_idx].rm_eo == -1)
1264 char *buf = (char *) re_string_get_buffer (&mctx->input);
1265 if (memcmp (buf + regs[subexp_idx].rm_so, buf + *pidx,
1274 err = re_node_set_insert (eps_via_nodes, node);
1275 if (BE (err < 0, 0))
1277 dest_node = dfa->edests[node].elems[0];
1278 if (re_node_set_contains (&mctx->state_log[*pidx]->nodes,
1285 || check_node_accept (mctx, dfa->nodes + node, *pidx))
1287 int dest_node = dfa->nexts[node];
1288 *pidx = (naccepted == 0) ? *pidx + 1 : *pidx + naccepted;
1289 if (fs && (*pidx > mctx->match_last || mctx->state_log[*pidx] == NULL
1290 || !re_node_set_contains (&mctx->state_log[*pidx]->nodes,
1293 re_node_set_empty (eps_via_nodes);
1300 static reg_errcode_t
1302 push_fail_stack (struct re_fail_stack_t *fs, int str_idx, int dest_node,
1303 int nregs, regmatch_t *regs, re_node_set *eps_via_nodes)
1306 int num = fs->num++;
1307 if (fs->num == fs->alloc)
1309 struct re_fail_stack_ent_t *new_array;
1310 new_array = realloc (fs->stack, (sizeof (struct re_fail_stack_ent_t)
1312 if (new_array == NULL)
1315 fs->stack = new_array;
1317 fs->stack[num].idx = str_idx;
1318 fs->stack[num].node = dest_node;
1319 fs->stack[num].regs = re_malloc (regmatch_t, nregs);
1320 if (fs->stack[num].regs == NULL)
1322 memcpy (fs->stack[num].regs, regs, sizeof (regmatch_t) * nregs);
1323 err = re_node_set_init_copy (&fs->stack[num].eps_via_nodes, eps_via_nodes);
1329 pop_fail_stack (struct re_fail_stack_t *fs, int *pidx,
1330 int nregs, regmatch_t *regs, re_node_set *eps_via_nodes)
1332 int num = --fs->num;
1334 *pidx = fs->stack[num].idx;
1335 memcpy (regs, fs->stack[num].regs, sizeof (regmatch_t) * nregs);
1336 re_node_set_free (eps_via_nodes);
1337 re_free (fs->stack[num].regs);
1338 *eps_via_nodes = fs->stack[num].eps_via_nodes;
1339 return fs->stack[num].node;
1342 /* Set the positions where the subexpressions are starts/ends to registers
1344 Note: We assume that pmatch[0] is already set, and
1345 pmatch[i].rm_so == pmatch[i].rm_eo == -1 for 0 < i < nmatch. */
1347 static reg_errcode_t
1349 set_regs (const regex_t *preg, const re_match_context_t *mctx,
1350 size_t nmatch, regmatch_t *pmatch, int fl_backtrack)
1352 re_dfa_t *dfa = (re_dfa_t *) preg->re_buffer;
1354 re_node_set eps_via_nodes;
1355 struct re_fail_stack_t *fs;
1356 struct re_fail_stack_t fs_body = { 0, 2, NULL };
1357 regmatch_t *prev_idx_match;
1360 assert (nmatch > 1);
1361 assert (mctx->state_log != NULL);
1366 fs->stack = re_malloc (struct re_fail_stack_ent_t, fs->alloc);
1367 if (fs->stack == NULL)
1373 cur_node = dfa->init_node;
1374 re_node_set_init_empty (&eps_via_nodes);
1376 prev_idx_match = (regmatch_t *) alloca (sizeof (regmatch_t) * nmatch);
1377 memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
1379 for (idx = pmatch[0].rm_so; idx <= pmatch[0].rm_eo ;)
1381 update_regs (dfa, pmatch, prev_idx_match, cur_node, idx, nmatch);
1383 if (idx == pmatch[0].rm_eo && cur_node == mctx->last_node)
1388 for (reg_idx = 0; reg_idx < nmatch; ++reg_idx)
1389 if (pmatch[reg_idx].rm_so > -1 && pmatch[reg_idx].rm_eo == -1)
1391 if (reg_idx == nmatch)
1393 re_node_set_free (&eps_via_nodes);
1394 return free_fail_stack_return (fs);
1396 cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
1401 re_node_set_free (&eps_via_nodes);
1406 /* Proceed to next node. */
1407 cur_node = proceed_next_node (mctx, nmatch, pmatch, &idx, cur_node,
1408 &eps_via_nodes, fs);
1410 if (BE (cur_node < 0, 0))
1412 if (BE (cur_node == -2, 0))
1414 re_node_set_free (&eps_via_nodes);
1415 free_fail_stack_return (fs);
1419 cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
1423 re_node_set_free (&eps_via_nodes);
1428 re_node_set_free (&eps_via_nodes);
1429 return free_fail_stack_return (fs);
1432 static reg_errcode_t
1434 free_fail_stack_return (struct re_fail_stack_t *fs)
1439 for (fs_idx = 0; fs_idx < fs->num; ++fs_idx)
1441 re_node_set_free (&fs->stack[fs_idx].eps_via_nodes);
1442 re_free (fs->stack[fs_idx].regs);
1444 re_free (fs->stack);
1451 update_regs (re_dfa_t *dfa, regmatch_t *pmatch, regmatch_t *prev_idx_match,
1452 int cur_node, int cur_idx, int nmatch)
1454 int type = dfa->nodes[cur_node].type;
1455 if (type == OP_OPEN_SUBEXP)
1457 int reg_num = dfa->nodes[cur_node].opr.idx + 1;
1459 /* We are at the first node of this sub expression. */
1460 if (reg_num < nmatch)
1462 pmatch[reg_num].rm_so = cur_idx;
1463 pmatch[reg_num].rm_eo = -1;
1466 else if (type == OP_CLOSE_SUBEXP)
1468 int reg_num = dfa->nodes[cur_node].opr.idx + 1;
1469 if (reg_num < nmatch)
1471 /* We are at the last node of this sub expression. */
1472 if (pmatch[reg_num].rm_so < cur_idx)
1474 pmatch[reg_num].rm_eo = cur_idx;
1475 /* This is a non-empty match or we are not inside an optional
1476 subexpression. Accept this right away. */
1477 memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
1481 if (dfa->nodes[cur_node].opt_subexp
1482 && prev_idx_match[reg_num].rm_so != -1)
1483 /* We transited through an empty match for an optional
1484 subexpression, like (a?)*, and this is not the subexp's
1485 first match. Copy back the old content of the registers
1486 so that matches of an inner subexpression are undone as
1487 well, like in ((a?))*. */
1488 memcpy (pmatch, prev_idx_match, sizeof (regmatch_t) * nmatch);
1490 /* We completed a subexpression, but it may be part of
1491 an optional one, so do not update PREV_IDX_MATCH. */
1492 pmatch[reg_num].rm_eo = cur_idx;
1498 /* This function checks the STATE_LOG from the SCTX->last_str_idx to 0
1499 and sift the nodes in each states according to the following rules.
1500 Updated state_log will be wrote to STATE_LOG.
1502 Rules: We throw away the Node `a' in the STATE_LOG[STR_IDX] if...
1503 1. When STR_IDX == MATCH_LAST(the last index in the state_log):
1504 If `a' isn't the LAST_NODE and `a' can't epsilon transit to
1505 the LAST_NODE, we throw away the node `a'.
1506 2. When 0 <= STR_IDX < MATCH_LAST and `a' accepts
1507 string `s' and transit to `b':
1508 i. If 'b' isn't in the STATE_LOG[STR_IDX+strlen('s')], we throw
1510 ii. If 'b' is in the STATE_LOG[STR_IDX+strlen('s')] but 'b' is
1511 thrown away, we throw away the node `a'.
1512 3. When 0 <= STR_IDX < MATCH_LAST and 'a' epsilon transit to 'b':
1513 i. If 'b' isn't in the STATE_LOG[STR_IDX], we throw away the
1515 ii. If 'b' is in the STATE_LOG[STR_IDX] but 'b' is thrown away,
1516 we throw away the node `a'. */
1518 #define STATE_NODE_CONTAINS(state,node) \
1519 ((state) != NULL && re_node_set_contains (&(state)->nodes, node))
1521 static reg_errcode_t
1523 sift_states_backward (re_match_context_t *mctx, re_sift_context_t *sctx)
1527 int str_idx = sctx->last_str_idx;
1528 re_node_set cur_dest;
1531 assert (mctx->state_log != NULL && mctx->state_log[str_idx] != NULL);
1534 /* Build sifted state_log[str_idx]. It has the nodes which can epsilon
1535 transit to the last_node and the last_node itself. */
1536 err = re_node_set_init_1 (&cur_dest, sctx->last_node);
1537 if (BE (err != REG_NOERROR, 0))
1539 err = update_cur_sifted_state (mctx, sctx, str_idx, &cur_dest);
1540 if (BE (err != REG_NOERROR, 0))
1543 /* Then check each states in the state_log. */
1546 /* Update counters. */
1547 null_cnt = (sctx->sifted_states[str_idx] == NULL) ? null_cnt + 1 : 0;
1548 if (null_cnt > mctx->max_mb_elem_len)
1550 memset (sctx->sifted_states, '\0',
1551 sizeof (re_dfastate_t *) * str_idx);
1552 re_node_set_free (&cur_dest);
1555 re_node_set_empty (&cur_dest);
1558 if (mctx->state_log[str_idx])
1560 err = build_sifted_states (mctx, sctx, str_idx, &cur_dest);
1561 if (BE (err != REG_NOERROR, 0))
1565 /* Add all the nodes which satisfy the following conditions:
1566 - It can epsilon transit to a node in CUR_DEST.
1568 And update state_log. */
1569 err = update_cur_sifted_state (mctx, sctx, str_idx, &cur_dest);
1570 if (BE (err != REG_NOERROR, 0))
1575 re_node_set_free (&cur_dest);
1579 static reg_errcode_t
1581 build_sifted_states (re_match_context_t *mctx, re_sift_context_t *sctx,
1582 int str_idx, re_node_set *cur_dest)
1584 re_dfa_t *const dfa = mctx->dfa;
1585 re_node_set *cur_src = &mctx->state_log[str_idx]->non_eps_nodes;
1588 /* Then build the next sifted state.
1589 We build the next sifted state on `cur_dest', and update
1590 `sifted_states[str_idx]' with `cur_dest'.
1592 `cur_dest' is the sifted state from `state_log[str_idx + 1]'.
1593 `cur_src' points the node_set of the old `state_log[str_idx]'
1594 (with the epsilon nodes pre-filtered out). */
1595 for (i = 0; i < cur_src->nelem; i++)
1597 int prev_node = cur_src->elems[i];
1602 re_token_type_t type = dfa->nodes[prev_node].type;
1603 assert (!IS_EPSILON_NODE (type));
1605 #ifdef RE_ENABLE_I18N
1606 /* If the node may accept `multi byte'. */
1607 if (dfa->nodes[prev_node].accept_mb)
1608 naccepted = sift_states_iter_mb (mctx, sctx, prev_node,
1609 str_idx, sctx->last_str_idx);
1610 #endif /* RE_ENABLE_I18N */
1612 /* We don't check backreferences here.
1613 See update_cur_sifted_state(). */
1615 && check_node_accept (mctx, dfa->nodes + prev_node, str_idx)
1616 && STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + 1],
1617 dfa->nexts[prev_node]))
1623 if (sctx->limits.nelem)
1625 int to_idx = str_idx + naccepted;
1626 if (check_dst_limits (mctx, &sctx->limits,
1627 dfa->nexts[prev_node], to_idx,
1628 prev_node, str_idx))
1631 ret = re_node_set_insert (cur_dest, prev_node);
1632 if (BE (ret == -1, 0))
1639 /* Helper functions. */
1641 static reg_errcode_t
1643 clean_state_log_if_needed (re_match_context_t *mctx, int next_state_log_idx)
1645 int top = mctx->state_log_top;
1647 if (next_state_log_idx >= mctx->input.bufs_len
1648 || (next_state_log_idx >= mctx->input.valid_len
1649 && mctx->input.valid_len < mctx->input.len))
1652 err = extend_buffers (mctx);
1653 if (BE (err != REG_NOERROR, 0))
1657 if (top < next_state_log_idx)
1659 memset (mctx->state_log + top + 1, '\0',
1660 sizeof (re_dfastate_t *) * (next_state_log_idx - top));
1661 mctx->state_log_top = next_state_log_idx;
1666 static reg_errcode_t
1668 merge_state_array (re_dfa_t *dfa, re_dfastate_t **dst, re_dfastate_t **src,
1673 for (st_idx = 0; st_idx < num; ++st_idx)
1675 if (dst[st_idx] == NULL)
1676 dst[st_idx] = src[st_idx];
1677 else if (src[st_idx] != NULL)
1679 re_node_set merged_set;
1680 err = re_node_set_init_union (&merged_set, &dst[st_idx]->nodes,
1681 &src[st_idx]->nodes);
1682 if (BE (err != REG_NOERROR, 0))
1684 dst[st_idx] = re_acquire_state (&err, dfa, &merged_set);
1685 re_node_set_free (&merged_set);
1686 if (BE (err != REG_NOERROR, 0))
1693 static reg_errcode_t
1695 update_cur_sifted_state (re_match_context_t *mctx, re_sift_context_t *sctx,
1696 int str_idx, re_node_set *dest_nodes)
1698 re_dfa_t *const dfa = mctx->dfa;
1700 const re_node_set *candidates;
1701 candidates = ((mctx->state_log[str_idx] == NULL) ? NULL
1702 : &mctx->state_log[str_idx]->nodes);
1704 if (dest_nodes->nelem == 0)
1705 sctx->sifted_states[str_idx] = NULL;
1710 /* At first, add the nodes which can epsilon transit to a node in
1712 err = add_epsilon_src_nodes (dfa, dest_nodes, candidates);
1713 if (BE (err != REG_NOERROR, 0))
1716 /* Then, check the limitations in the current sift_context. */
1717 if (sctx->limits.nelem)
1719 err = check_subexp_limits (dfa, dest_nodes, candidates, &sctx->limits,
1720 mctx->bkref_ents, str_idx);
1721 if (BE (err != REG_NOERROR, 0))
1726 sctx->sifted_states[str_idx] = re_acquire_state (&err, dfa, dest_nodes);
1727 if (BE (err != REG_NOERROR, 0))
1731 if (candidates && mctx->state_log[str_idx]->has_backref)
1733 err = sift_states_bkref (mctx, sctx, str_idx, candidates);
1734 if (BE (err != REG_NOERROR, 0))
1740 static reg_errcode_t
1742 add_epsilon_src_nodes (re_dfa_t *dfa, re_node_set *dest_nodes,
1743 const re_node_set *candidates)
1745 reg_errcode_t err = REG_NOERROR;
1748 re_dfastate_t *state = re_acquire_state (&err, dfa, dest_nodes);
1749 if (BE (err != REG_NOERROR, 0))
1752 if (!state->inveclosure.alloc)
1754 err = re_node_set_alloc (&state->inveclosure, dest_nodes->nelem);
1755 if (BE (err != REG_NOERROR, 0))
1757 for (i = 0; i < dest_nodes->nelem; i++)
1758 re_node_set_merge (&state->inveclosure,
1759 dfa->inveclosures + dest_nodes->elems[i]);
1761 return re_node_set_add_intersect (dest_nodes, candidates,
1762 &state->inveclosure);
1765 static reg_errcode_t
1767 sub_epsilon_src_nodes (re_dfa_t *dfa, int node, re_node_set *dest_nodes,
1768 const re_node_set *candidates)
1772 re_node_set *inv_eclosure = dfa->inveclosures + node;
1773 re_node_set except_nodes;
1774 re_node_set_init_empty (&except_nodes);
1775 for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx)
1777 int cur_node = inv_eclosure->elems[ecl_idx];
1778 if (cur_node == node)
1780 if (IS_EPSILON_NODE (dfa->nodes[cur_node].type))
1782 int edst1 = dfa->edests[cur_node].elems[0];
1783 int edst2 = ((dfa->edests[cur_node].nelem > 1)
1784 ? dfa->edests[cur_node].elems[1] : -1);
1785 if ((!re_node_set_contains (inv_eclosure, edst1)
1786 && re_node_set_contains (dest_nodes, edst1))
1788 && !re_node_set_contains (inv_eclosure, edst2)
1789 && re_node_set_contains (dest_nodes, edst2)))
1791 err = re_node_set_add_intersect (&except_nodes, candidates,
1792 dfa->inveclosures + cur_node);
1793 if (BE (err != REG_NOERROR, 0))
1795 re_node_set_free (&except_nodes);
1801 for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx)
1803 int cur_node = inv_eclosure->elems[ecl_idx];
1804 if (!re_node_set_contains (&except_nodes, cur_node))
1806 int idx = re_node_set_contains (dest_nodes, cur_node) - 1;
1807 re_node_set_remove_at (dest_nodes, idx);
1810 re_node_set_free (&except_nodes);
1816 check_dst_limits (re_match_context_t *mctx, re_node_set *limits,
1817 int dst_node, int dst_idx, int src_node, int src_idx)
1819 re_dfa_t *const dfa = mctx->dfa;
1820 int lim_idx, src_pos, dst_pos;
1822 int dst_bkref_idx = search_cur_bkref_entry (mctx, dst_idx);
1823 int src_bkref_idx = search_cur_bkref_entry (mctx, src_idx);
1824 for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx)
1827 struct re_backref_cache_entry *ent;
1828 ent = mctx->bkref_ents + limits->elems[lim_idx];
1829 subexp_idx = dfa->nodes[ent->node].opr.idx;
1831 dst_pos = check_dst_limits_calc_pos (mctx, limits->elems[lim_idx],
1832 subexp_idx, dst_node, dst_idx,
1834 src_pos = check_dst_limits_calc_pos (mctx, limits->elems[lim_idx],
1835 subexp_idx, src_node, src_idx,
1839 <src> <dst> ( <subexp> )
1840 ( <subexp> ) <src> <dst>
1841 ( <subexp1> <src> <subexp2> <dst> <subexp3> ) */
1842 if (src_pos == dst_pos)
1843 continue; /* This is unrelated limitation. */
1852 check_dst_limits_calc_pos_1 (re_match_context_t *mctx, int boundaries,
1853 int subexp_idx, int from_node, int bkref_idx)
1855 re_dfa_t *const dfa = mctx->dfa;
1856 re_node_set *eclosures = dfa->eclosures + from_node;
1859 /* Else, we are on the boundary: examine the nodes on the epsilon
1861 for (node_idx = 0; node_idx < eclosures->nelem; ++node_idx)
1863 int node = eclosures->elems[node_idx];
1864 switch (dfa->nodes[node].type)
1867 if (bkref_idx != -1)
1869 struct re_backref_cache_entry *ent = mctx->bkref_ents + bkref_idx;
1874 if (ent->node != node)
1877 if (subexp_idx <= 8 * sizeof (ent->eps_reachable_subexps_map)
1878 && !(ent->eps_reachable_subexps_map & (1 << subexp_idx)))
1881 /* Recurse trying to reach the OP_OPEN_SUBEXP and
1882 OP_CLOSE_SUBEXP cases below. But, if the
1883 destination node is the same node as the source
1884 node, don't recurse because it would cause an
1885 infinite loop: a regex that exhibits this behavior
1887 dst = dfa->edests[node].elems[0];
1888 if (dst == from_node)
1892 else /* if (boundaries & 2) */
1897 check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx,
1899 if (cpos == -1 /* && (boundaries & 1) */)
1901 if (cpos == 0 && (boundaries & 2))
1904 ent->eps_reachable_subexps_map &= ~(1 << subexp_idx);
1906 while (ent++->more);
1910 case OP_OPEN_SUBEXP:
1911 if ((boundaries & 1) && subexp_idx == dfa->nodes[node].opr.idx)
1915 case OP_CLOSE_SUBEXP:
1916 if ((boundaries & 2) && subexp_idx == dfa->nodes[node].opr.idx)
1925 return (boundaries & 2) ? 1 : 0;
1930 check_dst_limits_calc_pos (re_match_context_t *mctx, int limit, int subexp_idx,
1931 int from_node, int str_idx, int bkref_idx)
1933 struct re_backref_cache_entry *lim = mctx->bkref_ents + limit;
1936 /* If we are outside the range of the subexpression, return -1 or 1. */
1937 if (str_idx < lim->subexp_from)
1940 if (lim->subexp_to < str_idx)
1943 /* If we are within the subexpression, return 0. */
1944 boundaries = (str_idx == lim->subexp_from);
1945 boundaries |= (str_idx == lim->subexp_to) << 1;
1946 if (boundaries == 0)
1949 /* Else, examine epsilon closure. */
1950 return check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx,
1951 from_node, bkref_idx);
1954 /* Check the limitations of sub expressions LIMITS, and remove the nodes
1955 which are against limitations from DEST_NODES. */
1957 static reg_errcode_t
1959 check_subexp_limits (re_dfa_t *dfa, re_node_set *dest_nodes,
1960 const re_node_set *candidates, re_node_set *limits,
1961 struct re_backref_cache_entry *bkref_ents, int str_idx)
1964 int node_idx, lim_idx;
1966 for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx)
1969 struct re_backref_cache_entry *ent;
1970 ent = bkref_ents + limits->elems[lim_idx];
1972 if (str_idx <= ent->subexp_from || ent->str_idx < str_idx)
1973 continue; /* This is unrelated limitation. */
1975 subexp_idx = dfa->nodes[ent->node].opr.idx;
1976 if (ent->subexp_to == str_idx)
1980 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
1982 int node = dest_nodes->elems[node_idx];
1983 re_token_type_t type = dfa->nodes[node].type;
1984 if (type == OP_OPEN_SUBEXP
1985 && subexp_idx == dfa->nodes[node].opr.idx)
1987 else if (type == OP_CLOSE_SUBEXP
1988 && subexp_idx == dfa->nodes[node].opr.idx)
1992 /* Check the limitation of the open subexpression. */
1993 /* Note that (ent->subexp_to = str_idx != ent->subexp_from). */
1996 err = sub_epsilon_src_nodes (dfa, ops_node, dest_nodes,
1998 if (BE (err != REG_NOERROR, 0))
2002 /* Check the limitation of the close subexpression. */
2004 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2006 int node = dest_nodes->elems[node_idx];
2007 if (!re_node_set_contains (dfa->inveclosures + node,
2009 && !re_node_set_contains (dfa->eclosures + node,
2012 /* It is against this limitation.
2013 Remove it form the current sifted state. */
2014 err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2016 if (BE (err != REG_NOERROR, 0))
2022 else /* (ent->subexp_to != str_idx) */
2024 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2026 int node = dest_nodes->elems[node_idx];
2027 re_token_type_t type = dfa->nodes[node].type;
2028 if (type == OP_CLOSE_SUBEXP || type == OP_OPEN_SUBEXP)
2030 if (subexp_idx != dfa->nodes[node].opr.idx)
2032 /* It is against this limitation.
2033 Remove it form the current sifted state. */
2034 err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2036 if (BE (err != REG_NOERROR, 0))
2045 static reg_errcode_t
2047 sift_states_bkref (re_match_context_t *mctx, re_sift_context_t *sctx,
2048 int str_idx, const re_node_set *candidates)
2050 re_dfa_t *const dfa = mctx->dfa;
2053 re_sift_context_t local_sctx;
2054 int first_idx = search_cur_bkref_entry (mctx, str_idx);
2056 if (first_idx == -1)
2059 local_sctx.sifted_states = NULL; /* Mark that it hasn't been initialized. */
2061 for (node_idx = 0; node_idx < candidates->nelem; ++node_idx)
2064 re_token_type_t type;
2065 struct re_backref_cache_entry *entry;
2066 node = candidates->elems[node_idx];
2067 type = dfa->nodes[node].type;
2068 /* Avoid infinite loop for the REs like "()\1+". */
2069 if (node == sctx->last_node && str_idx == sctx->last_str_idx)
2071 if (type != OP_BACK_REF)
2074 entry = mctx->bkref_ents + first_idx;
2075 enabled_idx = first_idx;
2078 int subexp_len, to_idx, dst_node, ret;
2079 re_dfastate_t *cur_state;
2081 if (entry->node != node)
2083 subexp_len = entry->subexp_to - entry->subexp_from;
2084 to_idx = str_idx + subexp_len;
2085 dst_node = (subexp_len ? dfa->nexts[node]
2086 : dfa->edests[node].elems[0]);
2088 if (to_idx > sctx->last_str_idx
2089 || sctx->sifted_states[to_idx] == NULL
2090 || !STATE_NODE_CONTAINS (sctx->sifted_states[to_idx], dst_node)
2091 || check_dst_limits (mctx, &sctx->limits, node,
2092 str_idx, dst_node, to_idx))
2095 if (local_sctx.sifted_states == NULL)
2098 err = re_node_set_init_copy (&local_sctx.limits, &sctx->limits);
2099 if (BE (err != REG_NOERROR, 0))
2102 local_sctx.last_node = node;
2103 local_sctx.last_str_idx = str_idx;
2104 ret = re_node_set_insert (&local_sctx.limits, enabled_idx);
2105 if (BE (ret < 0, 0))
2110 cur_state = local_sctx.sifted_states[str_idx];
2111 err = sift_states_backward (mctx, &local_sctx);
2112 if (BE (err != REG_NOERROR, 0))
2114 if (sctx->limited_states != NULL)
2116 err = merge_state_array (dfa, sctx->limited_states,
2117 local_sctx.sifted_states,
2119 if (BE (err != REG_NOERROR, 0))
2122 local_sctx.sifted_states[str_idx] = cur_state;
2123 re_node_set_remove (&local_sctx.limits, enabled_idx);
2125 /* mctx->bkref_ents may have changed, reload the pointer. */
2126 entry = mctx->bkref_ents + enabled_idx;
2128 while (enabled_idx++, entry++->more);
2132 if (local_sctx.sifted_states != NULL)
2134 re_node_set_free (&local_sctx.limits);
2141 #ifdef RE_ENABLE_I18N
2144 sift_states_iter_mb (const re_match_context_t *mctx, re_sift_context_t *sctx,
2145 int node_idx, int str_idx, int max_str_idx)
2147 re_dfa_t *const dfa = mctx->dfa;
2149 /* Check the node can accept `multi byte'. */
2150 naccepted = check_node_accept_bytes (dfa, node_idx, &mctx->input, str_idx);
2151 if (naccepted > 0 && str_idx + naccepted <= max_str_idx &&
2152 !STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + naccepted],
2153 dfa->nexts[node_idx]))
2154 /* The node can't accept the `multi byte', or the
2155 destination was already thrown away, then the node
2156 could't accept the current input `multi byte'. */
2158 /* Otherwise, it is sure that the node could accept
2159 `naccepted' bytes input. */
2162 #endif /* RE_ENABLE_I18N */
2165 /* Functions for state transition. */
2167 /* Return the next state to which the current state STATE will transit by
2168 accepting the current input byte, and update STATE_LOG if necessary.
2169 If STATE can accept a multibyte char/collating element/back reference
2170 update the destination of STATE_LOG. */
2172 static re_dfastate_t *
2174 transit_state (reg_errcode_t *err, re_match_context_t *mctx,
2175 re_dfastate_t *state)
2177 re_dfastate_t **trtable;
2180 #ifdef RE_ENABLE_I18N
2181 /* If the current state can accept multibyte. */
2182 if (BE (state->accept_mb, 0))
2184 *err = transit_state_mb (mctx, state);
2185 if (BE (*err != REG_NOERROR, 0))
2188 #endif /* RE_ENABLE_I18N */
2190 /* Then decide the next state with the single byte. */
2193 /* don't use transition table */
2194 return transit_state_sb (err, mctx, state);
2197 /* Use transition table */
2198 ch = re_string_fetch_byte (&mctx->input);
2201 trtable = state->trtable;
2202 if (BE (trtable != NULL, 1))
2205 trtable = state->word_trtable;
2206 if (BE (trtable != NULL, 1))
2208 unsigned int context;
2210 = re_string_context_at (&mctx->input,
2211 re_string_cur_idx (&mctx->input) - 1,
2213 if (IS_WORD_CONTEXT (context))
2214 return trtable[ch + SBC_MAX];
2219 if (!build_trtable (mctx->dfa, state))
2225 /* Retry, we now have a transition table. */
2229 /* Update the state_log if we need */
2232 merge_state_with_log (reg_errcode_t *err, re_match_context_t *mctx,
2233 re_dfastate_t *next_state)
2235 re_dfa_t *const dfa = mctx->dfa;
2236 int cur_idx = re_string_cur_idx (&mctx->input);
2238 if (cur_idx > mctx->state_log_top)
2240 mctx->state_log[cur_idx] = next_state;
2241 mctx->state_log_top = cur_idx;
2243 else if (mctx->state_log[cur_idx] == 0)
2245 mctx->state_log[cur_idx] = next_state;
2249 re_dfastate_t *pstate;
2250 unsigned int context;
2251 re_node_set next_nodes, *log_nodes, *table_nodes = NULL;
2252 /* If (state_log[cur_idx] != 0), it implies that cur_idx is
2253 the destination of a multibyte char/collating element/
2254 back reference. Then the next state is the union set of
2255 these destinations and the results of the transition table. */
2256 pstate = mctx->state_log[cur_idx];
2257 log_nodes = pstate->entrance_nodes;
2258 if (next_state != NULL)
2260 table_nodes = next_state->entrance_nodes;
2261 *err = re_node_set_init_union (&next_nodes, table_nodes,
2263 if (BE (*err != REG_NOERROR, 0))
2267 next_nodes = *log_nodes;
2268 /* Note: We already add the nodes of the initial state,
2269 then we don't need to add them here. */
2271 context = re_string_context_at (&mctx->input,
2272 re_string_cur_idx (&mctx->input) - 1,
2274 next_state = mctx->state_log[cur_idx]
2275 = re_acquire_state_context (err, dfa, &next_nodes, context);
2276 /* We don't need to check errors here, since the return value of
2277 this function is next_state and ERR is already set. */
2279 if (table_nodes != NULL)
2280 re_node_set_free (&next_nodes);
2283 if (BE (dfa->nbackref, 0) && next_state != NULL)
2285 /* Check OP_OPEN_SUBEXP in the current state in case that we use them
2286 later. We must check them here, since the back references in the
2287 next state might use them. */
2288 *err = check_subexp_matching_top (mctx, &next_state->nodes,
2290 if (BE (*err != REG_NOERROR, 0))
2293 /* If the next state has back references. */
2294 if (next_state->has_backref)
2296 *err = transit_state_bkref (mctx, &next_state->nodes);
2297 if (BE (*err != REG_NOERROR, 0))
2299 next_state = mctx->state_log[cur_idx];
2306 /* Skip bytes in the input that correspond to part of a
2307 multi-byte match, then look in the log for a state
2308 from which to restart matching. */
2309 static re_dfastate_t *
2311 find_recover_state (reg_errcode_t *err, re_match_context_t *mctx)
2313 re_dfastate_t *cur_state = NULL;
2316 int max = mctx->state_log_top;
2317 int cur_str_idx = re_string_cur_idx (&mctx->input);
2321 if (++cur_str_idx > max)
2323 re_string_skip_bytes (&mctx->input, 1);
2325 while (mctx->state_log[cur_str_idx] == NULL);
2327 cur_state = merge_state_with_log (err, mctx, NULL);
2329 while (err == REG_NOERROR && cur_state == NULL);
2333 /* Helper functions for transit_state. */
2335 /* From the node set CUR_NODES, pick up the nodes whose types are
2336 OP_OPEN_SUBEXP and which have corresponding back references in the regular
2337 expression. And register them to use them later for evaluating the
2338 correspoding back references. */
2340 static reg_errcode_t
2342 check_subexp_matching_top (re_match_context_t *mctx, re_node_set *cur_nodes,
2345 re_dfa_t *const dfa = mctx->dfa;
2349 /* TODO: This isn't efficient.
2350 Because there might be more than one nodes whose types are
2351 OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
2354 for (node_idx = 0; node_idx < cur_nodes->nelem; ++node_idx)
2356 int node = cur_nodes->elems[node_idx];
2357 if (dfa->nodes[node].type == OP_OPEN_SUBEXP
2358 && dfa->nodes[node].opr.idx < (8 * sizeof (dfa->used_bkref_map))
2359 && dfa->used_bkref_map & (1 << dfa->nodes[node].opr.idx))
2361 err = match_ctx_add_subtop (mctx, node, str_idx);
2362 if (BE (err != REG_NOERROR, 0))
2370 /* Return the next state to which the current state STATE will transit by
2371 accepting the current input byte. */
2373 static re_dfastate_t *
2374 transit_state_sb (err, mctx, state)
2376 re_match_context_t *mctx;
2377 re_dfastate_t *state;
2379 re_dfa_t *const dfa = mctx->dfa;
2380 re_node_set next_nodes;
2381 re_dfastate_t *next_state;
2382 int node_cnt, cur_str_idx = re_string_cur_idx (&mctx->input);
2383 unsigned int context;
2385 *err = re_node_set_alloc (&next_nodes, state->nodes.nelem + 1);
2386 if (BE (*err != REG_NOERROR, 0))
2388 for (node_cnt = 0; node_cnt < state->nodes.nelem; ++node_cnt)
2390 int cur_node = state->nodes.elems[node_cnt];
2391 if (check_node_accept (mctx, dfa->nodes + cur_node, cur_str_idx))
2393 *err = re_node_set_merge (&next_nodes,
2394 dfa->eclosures + dfa->nexts[cur_node]);
2395 if (BE (*err != REG_NOERROR, 0))
2397 re_node_set_free (&next_nodes);
2402 context = re_string_context_at (&mctx->input, cur_str_idx, mctx->eflags);
2403 next_state = re_acquire_state_context (err, dfa, &next_nodes, context);
2404 /* We don't need to check errors here, since the return value of
2405 this function is next_state and ERR is already set. */
2407 re_node_set_free (&next_nodes);
2408 re_string_skip_bytes (&mctx->input, 1);
2413 #ifdef RE_ENABLE_I18N
2414 static reg_errcode_t
2416 transit_state_mb (re_match_context_t *mctx, re_dfastate_t *pstate)
2418 re_dfa_t *const dfa = mctx->dfa;
2422 for (i = 0; i < pstate->nodes.nelem; ++i)
2424 re_node_set dest_nodes, *new_nodes;
2425 int cur_node_idx = pstate->nodes.elems[i];
2426 int naccepted, dest_idx;
2427 unsigned int context;
2428 re_dfastate_t *dest_state;
2430 if (!dfa->nodes[cur_node_idx].accept_mb)
2433 if (dfa->nodes[cur_node_idx].constraint)
2435 context = re_string_context_at (&mctx->input,
2436 re_string_cur_idx (&mctx->input),
2438 if (NOT_SATISFY_NEXT_CONSTRAINT (dfa->nodes[cur_node_idx].constraint,
2443 /* How many bytes the node can accept? */
2444 naccepted = check_node_accept_bytes (dfa, cur_node_idx, &mctx->input,
2445 re_string_cur_idx (&mctx->input));
2449 /* The node can accepts `naccepted' bytes. */
2450 dest_idx = re_string_cur_idx (&mctx->input) + naccepted;
2451 mctx->max_mb_elem_len = ((mctx->max_mb_elem_len < naccepted) ? naccepted
2452 : mctx->max_mb_elem_len);
2453 err = clean_state_log_if_needed (mctx, dest_idx);
2454 if (BE (err != REG_NOERROR, 0))
2457 assert (dfa->nexts[cur_node_idx] != -1);
2459 new_nodes = dfa->eclosures + dfa->nexts[cur_node_idx];
2461 dest_state = mctx->state_log[dest_idx];
2462 if (dest_state == NULL)
2463 dest_nodes = *new_nodes;
2466 err = re_node_set_init_union (&dest_nodes,
2467 dest_state->entrance_nodes, new_nodes);
2468 if (BE (err != REG_NOERROR, 0))
2471 context = re_string_context_at (&mctx->input, dest_idx - 1, mctx->eflags);
2472 mctx->state_log[dest_idx]
2473 = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2474 if (dest_state != NULL)
2475 re_node_set_free (&dest_nodes);
2476 if (BE (mctx->state_log[dest_idx] == NULL && err != REG_NOERROR, 0))
2481 #endif /* RE_ENABLE_I18N */
2483 static reg_errcode_t
2485 transit_state_bkref (re_match_context_t *mctx, const re_node_set *nodes)
2487 re_dfa_t *const dfa = mctx->dfa;
2490 int cur_str_idx = re_string_cur_idx (&mctx->input);
2492 for (i = 0; i < nodes->nelem; ++i)
2494 int dest_str_idx, prev_nelem, bkc_idx;
2495 int node_idx = nodes->elems[i];
2496 unsigned int context;
2497 const re_token_t *node = dfa->nodes + node_idx;
2498 re_node_set *new_dest_nodes;
2500 /* Check whether `node' is a backreference or not. */
2501 if (node->type != OP_BACK_REF)
2504 if (node->constraint)
2506 context = re_string_context_at (&mctx->input, cur_str_idx,
2508 if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
2512 /* `node' is a backreference.
2513 Check the substring which the substring matched. */
2514 bkc_idx = mctx->nbkref_ents;
2515 err = get_subexp (mctx, node_idx, cur_str_idx);
2516 if (BE (err != REG_NOERROR, 0))
2519 /* And add the epsilon closures (which is `new_dest_nodes') of
2520 the backreference to appropriate state_log. */
2522 assert (dfa->nexts[node_idx] != -1);
2524 for (; bkc_idx < mctx->nbkref_ents; ++bkc_idx)
2527 re_dfastate_t *dest_state;
2528 struct re_backref_cache_entry *bkref_ent;
2529 bkref_ent = mctx->bkref_ents + bkc_idx;
2530 if (bkref_ent->node != node_idx || bkref_ent->str_idx != cur_str_idx)
2532 subexp_len = bkref_ent->subexp_to - bkref_ent->subexp_from;
2533 new_dest_nodes = (subexp_len == 0
2534 ? dfa->eclosures + dfa->edests[node_idx].elems[0]
2535 : dfa->eclosures + dfa->nexts[node_idx]);
2536 dest_str_idx = (cur_str_idx + bkref_ent->subexp_to
2537 - bkref_ent->subexp_from);
2538 context = re_string_context_at (&mctx->input, dest_str_idx - 1,
2540 dest_state = mctx->state_log[dest_str_idx];
2541 prev_nelem = ((mctx->state_log[cur_str_idx] == NULL) ? 0
2542 : mctx->state_log[cur_str_idx]->nodes.nelem);
2543 /* Add `new_dest_node' to state_log. */
2544 if (dest_state == NULL)
2546 mctx->state_log[dest_str_idx]
2547 = re_acquire_state_context (&err, dfa, new_dest_nodes,
2549 if (BE (mctx->state_log[dest_str_idx] == NULL
2550 && err != REG_NOERROR, 0))
2555 re_node_set dest_nodes;
2556 err = re_node_set_init_union (&dest_nodes,
2557 dest_state->entrance_nodes,
2559 if (BE (err != REG_NOERROR, 0))
2561 re_node_set_free (&dest_nodes);
2564 mctx->state_log[dest_str_idx]
2565 = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2566 re_node_set_free (&dest_nodes);
2567 if (BE (mctx->state_log[dest_str_idx] == NULL
2568 && err != REG_NOERROR, 0))
2571 /* We need to check recursively if the backreference can epsilon
2574 && mctx->state_log[cur_str_idx]->nodes.nelem > prev_nelem)
2576 err = check_subexp_matching_top (mctx, new_dest_nodes,
2578 if (BE (err != REG_NOERROR, 0))
2580 err = transit_state_bkref (mctx, new_dest_nodes);
2581 if (BE (err != REG_NOERROR, 0))
2591 /* Enumerate all the candidates which the backreference BKREF_NODE can match
2592 at BKREF_STR_IDX, and register them by match_ctx_add_entry().
2593 Note that we might collect inappropriate candidates here.
2594 However, the cost of checking them strictly here is too high, then we
2595 delay these checking for prune_impossible_nodes(). */
2597 static reg_errcode_t
2599 get_subexp (re_match_context_t *mctx, int bkref_node, int bkref_str_idx)
2601 re_dfa_t *const dfa = mctx->dfa;
2602 int subexp_num, sub_top_idx;
2603 const char *buf = (const char *) re_string_get_buffer (&mctx->input);
2604 /* Return if we have already checked BKREF_NODE at BKREF_STR_IDX. */
2605 int cache_idx = search_cur_bkref_entry (mctx, bkref_str_idx);
2606 if (cache_idx != -1)
2608 const struct re_backref_cache_entry *entry = mctx->bkref_ents + cache_idx;
2610 if (entry->node == bkref_node)
2611 return REG_NOERROR; /* We already checked it. */
2612 while (entry++->more);
2615 subexp_num = dfa->nodes[bkref_node].opr.idx;
2617 /* For each sub expression */
2618 for (sub_top_idx = 0; sub_top_idx < mctx->nsub_tops; ++sub_top_idx)
2621 re_sub_match_top_t *sub_top = mctx->sub_tops[sub_top_idx];
2622 re_sub_match_last_t *sub_last;
2623 int sub_last_idx, sl_str, bkref_str_off;
2625 if (dfa->nodes[sub_top->node].opr.idx != subexp_num)
2626 continue; /* It isn't related. */
2628 sl_str = sub_top->str_idx;
2629 bkref_str_off = bkref_str_idx;
2630 /* At first, check the last node of sub expressions we already
2632 for (sub_last_idx = 0; sub_last_idx < sub_top->nlasts; ++sub_last_idx)
2635 sub_last = sub_top->lasts[sub_last_idx];
2636 sl_str_diff = sub_last->str_idx - sl_str;
2637 /* The matched string by the sub expression match with the substring
2638 at the back reference? */
2639 if (sl_str_diff > 0)
2641 if (BE (bkref_str_off + sl_str_diff > mctx->input.valid_len, 0))
2643 /* Not enough chars for a successful match. */
2644 if (bkref_str_off + sl_str_diff > mctx->input.len)
2647 err = clean_state_log_if_needed (mctx,
2650 if (BE (err != REG_NOERROR, 0))
2652 buf = (const char *) re_string_get_buffer (&mctx->input);
2654 if (memcmp (buf + bkref_str_off, buf + sl_str, sl_str_diff) != 0)
2655 break; /* We don't need to search this sub expression any more. */
2657 bkref_str_off += sl_str_diff;
2658 sl_str += sl_str_diff;
2659 err = get_subexp_sub (mctx, sub_top, sub_last, bkref_node,
2662 /* Reload buf, since the preceding call might have reallocated
2664 buf = (const char *) re_string_get_buffer (&mctx->input);
2666 if (err == REG_NOMATCH)
2668 if (BE (err != REG_NOERROR, 0))
2672 if (sub_last_idx < sub_top->nlasts)
2674 if (sub_last_idx > 0)
2676 /* Then, search for the other last nodes of the sub expression. */
2677 for (; sl_str <= bkref_str_idx; ++sl_str)
2679 int cls_node, sl_str_off;
2680 const re_node_set *nodes;
2681 sl_str_off = sl_str - sub_top->str_idx;
2682 /* The matched string by the sub expression match with the substring
2683 at the back reference? */
2686 if (BE (bkref_str_off >= mctx->input.valid_len, 0))
2688 /* If we are at the end of the input, we cannot match. */
2689 if (bkref_str_off >= mctx->input.len)
2692 err = extend_buffers (mctx);
2693 if (BE (err != REG_NOERROR, 0))
2696 buf = (const char *) re_string_get_buffer (&mctx->input);
2698 if (buf [bkref_str_off++] != buf[sl_str - 1])
2699 break; /* We don't need to search this sub expression
2702 if (mctx->state_log[sl_str] == NULL)
2704 /* Does this state have a ')' of the sub expression? */
2705 nodes = &mctx->state_log[sl_str]->nodes;
2706 cls_node = find_subexp_node (dfa, nodes, subexp_num, OP_CLOSE_SUBEXP);
2709 if (sub_top->path == NULL)
2711 sub_top->path = calloc (sizeof (state_array_t),
2712 sl_str - sub_top->str_idx + 1);
2713 if (sub_top->path == NULL)
2716 /* Can the OP_OPEN_SUBEXP node arrive the OP_CLOSE_SUBEXP node
2717 in the current context? */
2718 err = check_arrival (mctx, sub_top->path, sub_top->node,
2719 sub_top->str_idx, cls_node, sl_str, OP_CLOSE_SUBEXP);
2720 if (err == REG_NOMATCH)
2722 if (BE (err != REG_NOERROR, 0))
2724 sub_last = match_ctx_add_sublast (sub_top, cls_node, sl_str);
2725 if (BE (sub_last == NULL, 0))
2727 err = get_subexp_sub (mctx, sub_top, sub_last, bkref_node,
2729 if (err == REG_NOMATCH)
2736 /* Helper functions for get_subexp(). */
2738 /* Check SUB_LAST can arrive to the back reference BKREF_NODE at BKREF_STR.
2739 If it can arrive, register the sub expression expressed with SUB_TOP
2742 static reg_errcode_t
2744 get_subexp_sub (re_match_context_t *mctx, const re_sub_match_top_t *sub_top,
2745 re_sub_match_last_t *sub_last, int bkref_node, int bkref_str)
2749 /* Can the subexpression arrive the back reference? */
2750 err = check_arrival (mctx, &sub_last->path, sub_last->node,
2751 sub_last->str_idx, bkref_node, bkref_str, OP_OPEN_SUBEXP);
2752 if (err != REG_NOERROR)
2754 err = match_ctx_add_entry (mctx, bkref_node, bkref_str, sub_top->str_idx,
2756 if (BE (err != REG_NOERROR, 0))
2758 to_idx = bkref_str + sub_last->str_idx - sub_top->str_idx;
2759 return clean_state_log_if_needed (mctx, to_idx);
2762 /* Find the first node which is '(' or ')' and whose index is SUBEXP_IDX.
2763 Search '(' if FL_OPEN, or search ')' otherwise.
2764 TODO: This function isn't efficient...
2765 Because there might be more than one nodes whose types are
2766 OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
2772 find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
2773 int subexp_idx, int type)
2776 for (cls_idx = 0; cls_idx < nodes->nelem; ++cls_idx)
2778 int cls_node = nodes->elems[cls_idx];
2779 const re_token_t *node = dfa->nodes + cls_node;
2780 if (node->type == type
2781 && node->opr.idx == subexp_idx)
2787 /* Check whether the node TOP_NODE at TOP_STR can arrive to the node
2788 LAST_NODE at LAST_STR. We record the path onto PATH since it will be
2790 Return REG_NOERROR if it can arrive, or REG_NOMATCH otherwise. */
2792 static reg_errcode_t
2794 check_arrival (re_match_context_t *mctx, state_array_t *path,
2795 int top_node, int top_str, int last_node, int last_str,
2798 re_dfa_t *const dfa = mctx->dfa;
2800 int subexp_num, backup_cur_idx, str_idx, null_cnt;
2801 re_dfastate_t *cur_state = NULL;
2802 re_node_set *cur_nodes, next_nodes;
2803 re_dfastate_t **backup_state_log;
2804 unsigned int context;
2806 subexp_num = dfa->nodes[top_node].opr.idx;
2807 /* Extend the buffer if we need. */
2808 if (BE (path->alloc < last_str + mctx->max_mb_elem_len + 1, 0))
2810 re_dfastate_t **new_array;
2811 int old_alloc = path->alloc;
2812 path->alloc += last_str + mctx->max_mb_elem_len + 1;
2813 new_array = re_realloc (path->array, re_dfastate_t *, path->alloc);
2814 if (new_array == NULL)
2816 path->alloc = old_alloc;
2819 path->array = new_array;
2820 memset (new_array + old_alloc, '\0',
2821 sizeof (re_dfastate_t *) * (path->alloc - old_alloc));
2824 str_idx = path->next_idx == 0 ? top_str : path->next_idx;
2826 /* Temporary modify MCTX. */
2827 backup_state_log = mctx->state_log;
2828 backup_cur_idx = mctx->input.cur_idx;
2829 mctx->state_log = path->array;
2830 mctx->input.cur_idx = str_idx;
2832 /* Setup initial node set. */
2833 context = re_string_context_at (&mctx->input, str_idx - 1, mctx->eflags);
2834 if (str_idx == top_str)
2836 err = re_node_set_init_1 (&next_nodes, top_node);
2837 if (BE (err != REG_NOERROR, 0))
2839 err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
2840 if (BE (err != REG_NOERROR, 0))
2842 re_node_set_free (&next_nodes);
2848 cur_state = mctx->state_log[str_idx];
2849 if (cur_state && cur_state->has_backref)
2851 err = re_node_set_init_copy (&next_nodes, &cur_state->nodes);
2852 if (BE ( err != REG_NOERROR, 0))
2856 re_node_set_init_empty (&next_nodes);
2858 if (str_idx == top_str || (cur_state && cur_state->has_backref))
2860 if (next_nodes.nelem)
2862 err = expand_bkref_cache (mctx, &next_nodes, str_idx,
2864 if (BE ( err != REG_NOERROR, 0))
2866 re_node_set_free (&next_nodes);
2870 cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
2871 if (BE (cur_state == NULL && err != REG_NOERROR, 0))
2873 re_node_set_free (&next_nodes);
2876 mctx->state_log[str_idx] = cur_state;
2879 for (null_cnt = 0; str_idx < last_str && null_cnt <= mctx->max_mb_elem_len;)
2881 re_node_set_empty (&next_nodes);
2882 if (mctx->state_log[str_idx + 1])
2884 err = re_node_set_merge (&next_nodes,
2885 &mctx->state_log[str_idx + 1]->nodes);
2886 if (BE (err != REG_NOERROR, 0))
2888 re_node_set_free (&next_nodes);
2894 err = check_arrival_add_next_nodes (mctx, str_idx,
2895 &cur_state->non_eps_nodes, &next_nodes);
2896 if (BE (err != REG_NOERROR, 0))
2898 re_node_set_free (&next_nodes);
2903 if (next_nodes.nelem)
2905 err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
2906 if (BE (err != REG_NOERROR, 0))
2908 re_node_set_free (&next_nodes);
2911 err = expand_bkref_cache (mctx, &next_nodes, str_idx,
2913 if (BE ( err != REG_NOERROR, 0))
2915 re_node_set_free (&next_nodes);
2919 context = re_string_context_at (&mctx->input, str_idx - 1, mctx->eflags);
2920 cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
2921 if (BE (cur_state == NULL && err != REG_NOERROR, 0))
2923 re_node_set_free (&next_nodes);
2926 mctx->state_log[str_idx] = cur_state;
2927 null_cnt = cur_state == NULL ? null_cnt + 1 : 0;
2929 re_node_set_free (&next_nodes);
2930 cur_nodes = (mctx->state_log[last_str] == NULL ? NULL
2931 : &mctx->state_log[last_str]->nodes);
2932 path->next_idx = str_idx;
2935 mctx->state_log = backup_state_log;
2936 mctx->input.cur_idx = backup_cur_idx;
2938 /* Then check the current node set has the node LAST_NODE. */
2939 if (cur_nodes != NULL && re_node_set_contains (cur_nodes, last_node))
2945 /* Helper functions for check_arrival. */
2947 /* Calculate the destination nodes of CUR_NODES at STR_IDX, and append them
2949 TODO: This function is similar to the functions transit_state*(),
2950 however this function has many additional works.
2951 Can't we unify them? */
2953 static reg_errcode_t
2955 check_arrival_add_next_nodes (re_match_context_t *mctx, int str_idx,
2956 re_node_set *cur_nodes,
2957 re_node_set *next_nodes)
2959 re_dfa_t *const dfa = mctx->dfa;
2963 re_node_set union_set;
2964 re_node_set_init_empty (&union_set);
2965 for (cur_idx = 0; cur_idx < cur_nodes->nelem; ++cur_idx)
2968 int cur_node = cur_nodes->elems[cur_idx];
2970 re_token_type_t type = dfa->nodes[cur_node].type;
2971 assert (!IS_EPSILON_NODE (type));
2973 #ifdef RE_ENABLE_I18N
2974 /* If the node may accept `multi byte'. */
2975 if (dfa->nodes[cur_node].accept_mb)
2977 naccepted = check_node_accept_bytes (dfa, cur_node, &mctx->input,
2981 re_dfastate_t *dest_state;
2982 int next_node = dfa->nexts[cur_node];
2983 int next_idx = str_idx + naccepted;
2984 dest_state = mctx->state_log[next_idx];
2985 re_node_set_empty (&union_set);
2988 err = re_node_set_merge (&union_set, &dest_state->nodes);
2989 if (BE (err != REG_NOERROR, 0))
2991 re_node_set_free (&union_set);
2995 result = re_node_set_insert (&union_set, next_node);
2996 if (BE (result < 0, 0))
2998 re_node_set_free (&union_set);
3001 mctx->state_log[next_idx] = re_acquire_state (&err, dfa,
3003 if (BE (mctx->state_log[next_idx] == NULL
3004 && err != REG_NOERROR, 0))
3006 re_node_set_free (&union_set);
3011 #endif /* RE_ENABLE_I18N */
3013 || check_node_accept (mctx, dfa->nodes + cur_node, str_idx))
3015 result = re_node_set_insert (next_nodes, dfa->nexts[cur_node]);
3016 if (BE (result < 0, 0))
3018 re_node_set_free (&union_set);
3023 re_node_set_free (&union_set);
3027 /* For all the nodes in CUR_NODES, add the epsilon closures of them to
3028 CUR_NODES, however exclude the nodes which are:
3029 - inside the sub expression whose number is EX_SUBEXP, if FL_OPEN.
3030 - out of the sub expression whose number is EX_SUBEXP, if !FL_OPEN.
3033 static reg_errcode_t
3035 check_arrival_expand_ecl (re_dfa_t *dfa, re_node_set *cur_nodes,
3036 int ex_subexp, int type)
3039 int idx, outside_node;
3040 re_node_set new_nodes;
3042 assert (cur_nodes->nelem);
3044 err = re_node_set_alloc (&new_nodes, cur_nodes->nelem);
3045 if (BE (err != REG_NOERROR, 0))
3047 /* Create a new node set NEW_NODES with the nodes which are epsilon
3048 closures of the node in CUR_NODES. */
3050 for (idx = 0; idx < cur_nodes->nelem; ++idx)
3052 int cur_node = cur_nodes->elems[idx];
3053 re_node_set *eclosure = dfa->eclosures + cur_node;
3054 outside_node = find_subexp_node (dfa, eclosure, ex_subexp, type);
3055 if (outside_node == -1)
3057 /* There are no problematic nodes, just merge them. */
3058 err = re_node_set_merge (&new_nodes, eclosure);
3059 if (BE (err != REG_NOERROR, 0))
3061 re_node_set_free (&new_nodes);
3067 /* There are problematic nodes, re-calculate incrementally. */
3068 err = check_arrival_expand_ecl_sub (dfa, &new_nodes, cur_node,
3070 if (BE (err != REG_NOERROR, 0))
3072 re_node_set_free (&new_nodes);
3077 re_node_set_free (cur_nodes);
3078 *cur_nodes = new_nodes;
3082 /* Helper function for check_arrival_expand_ecl.
3083 Check incrementally the epsilon closure of TARGET, and if it isn't
3084 problematic append it to DST_NODES. */
3086 static reg_errcode_t
3088 check_arrival_expand_ecl_sub (re_dfa_t *dfa, re_node_set *dst_nodes,
3089 int target, int ex_subexp, int type)
3092 for (cur_node = target; !re_node_set_contains (dst_nodes, cur_node);)
3096 if (dfa->nodes[cur_node].type == type
3097 && dfa->nodes[cur_node].opr.idx == ex_subexp)
3099 if (type == OP_CLOSE_SUBEXP)
3101 err = re_node_set_insert (dst_nodes, cur_node);
3102 if (BE (err == -1, 0))
3107 err = re_node_set_insert (dst_nodes, cur_node);
3108 if (BE (err == -1, 0))
3110 if (dfa->edests[cur_node].nelem == 0)
3112 if (dfa->edests[cur_node].nelem == 2)
3114 err = check_arrival_expand_ecl_sub (dfa, dst_nodes,
3115 dfa->edests[cur_node].elems[1],
3117 if (BE (err != REG_NOERROR, 0))
3120 cur_node = dfa->edests[cur_node].elems[0];
3126 /* For all the back references in the current state, calculate the
3127 destination of the back references by the appropriate entry
3128 in MCTX->BKREF_ENTS. */
3130 static reg_errcode_t
3132 expand_bkref_cache (re_match_context_t *mctx, re_node_set *cur_nodes,
3133 int cur_str, int subexp_num, int type)
3135 re_dfa_t *const dfa = mctx->dfa;
3137 int cache_idx_start = search_cur_bkref_entry (mctx, cur_str);
3138 struct re_backref_cache_entry *ent;
3140 if (cache_idx_start == -1)
3144 ent = mctx->bkref_ents + cache_idx_start;
3147 int to_idx, next_node;
3149 /* Is this entry ENT is appropriate? */
3150 if (!re_node_set_contains (cur_nodes, ent->node))
3153 to_idx = cur_str + ent->subexp_to - ent->subexp_from;
3154 /* Calculate the destination of the back reference, and append it
3155 to MCTX->STATE_LOG. */
3156 if (to_idx == cur_str)
3158 /* The backreference did epsilon transit, we must re-check all the
3159 node in the current state. */
3160 re_node_set new_dests;
3161 reg_errcode_t err2, err3;
3162 next_node = dfa->edests[ent->node].elems[0];
3163 if (re_node_set_contains (cur_nodes, next_node))
3165 err = re_node_set_init_1 (&new_dests, next_node);
3166 err2 = check_arrival_expand_ecl (dfa, &new_dests, subexp_num, type);
3167 err3 = re_node_set_merge (cur_nodes, &new_dests);
3168 re_node_set_free (&new_dests);
3169 if (BE (err != REG_NOERROR || err2 != REG_NOERROR
3170 || err3 != REG_NOERROR, 0))
3172 err = (err != REG_NOERROR ? err
3173 : (err2 != REG_NOERROR ? err2 : err3));
3176 /* TODO: It is still inefficient... */
3181 re_node_set union_set;
3182 next_node = dfa->nexts[ent->node];
3183 if (mctx->state_log[to_idx])
3186 if (re_node_set_contains (&mctx->state_log[to_idx]->nodes,
3189 err = re_node_set_init_copy (&union_set,
3190 &mctx->state_log[to_idx]->nodes);
3191 ret = re_node_set_insert (&union_set, next_node);
3192 if (BE (err != REG_NOERROR || ret < 0, 0))
3194 re_node_set_free (&union_set);
3195 err = err != REG_NOERROR ? err : REG_ESPACE;
3201 err = re_node_set_init_1 (&union_set, next_node);
3202 if (BE (err != REG_NOERROR, 0))
3205 mctx->state_log[to_idx] = re_acquire_state (&err, dfa, &union_set);
3206 re_node_set_free (&union_set);
3207 if (BE (mctx->state_log[to_idx] == NULL
3208 && err != REG_NOERROR, 0))
3212 while (ent++->more);
3216 /* Build transition table for the state.
3217 Return 1 if succeeded, otherwise return NULL. */
3221 build_trtable (re_dfa_t *dfa, re_dfastate_t *state)
3224 int i, j, ch, need_word_trtable = 0;
3225 unsigned int elem, mask;
3226 int dests_node_malloced = 0, dest_states_malloced = 0;
3227 int ndests; /* Number of the destination states from `state'. */
3228 re_dfastate_t **trtable;
3229 re_dfastate_t **dest_states = NULL, **dest_states_word, **dest_states_nl;
3230 re_node_set follows, *dests_node;
3234 /* We build DFA states which corresponds to the destination nodes
3235 from `state'. `dests_node[i]' represents the nodes which i-th
3236 destination state contains, and `dests_ch[i]' represents the
3237 characters which i-th destination state accepts. */
3239 if (__libc_use_alloca ((sizeof (re_node_set) + sizeof (bitset)) * SBC_MAX))
3240 dests_node = (re_node_set *)
3241 alloca ((sizeof (re_node_set) + sizeof (bitset)) * SBC_MAX);
3245 dests_node = (re_node_set *)
3246 malloc ((sizeof (re_node_set) + sizeof (bitset)) * SBC_MAX);
3247 if (BE (dests_node == NULL, 0))
3249 dests_node_malloced = 1;
3251 dests_ch = (bitset *) (dests_node + SBC_MAX);
3253 /* Initialize transiton table. */
3254 state->word_trtable = state->trtable = NULL;
3256 /* At first, group all nodes belonging to `state' into several
3258 ndests = group_nodes_into_DFAstates (dfa, state, dests_node, dests_ch);
3259 if (BE (ndests <= 0, 0))
3261 if (dests_node_malloced)
3263 /* Return 0 in case of an error, 1 otherwise. */
3266 state->trtable = (re_dfastate_t **)
3267 calloc (sizeof (re_dfastate_t *), SBC_MAX);
3273 err = re_node_set_alloc (&follows, ndests + 1);
3274 if (BE (err != REG_NOERROR, 0))
3278 if (__libc_use_alloca ((sizeof (re_node_set) + sizeof (bitset)) * SBC_MAX
3279 + ndests * 3 * sizeof (re_dfastate_t *)))
3280 dest_states = (re_dfastate_t **)
3281 alloca (ndests * 3 * sizeof (re_dfastate_t *));
3285 dest_states = (re_dfastate_t **)
3286 malloc (ndests * 3 * sizeof (re_dfastate_t *));
3287 if (BE (dest_states == NULL, 0))
3290 if (dest_states_malloced)
3292 re_node_set_free (&follows);
3293 for (i = 0; i < ndests; ++i)
3294 re_node_set_free (dests_node + i);
3295 if (dests_node_malloced)
3299 dest_states_malloced = 1;
3301 dest_states_word = dest_states + ndests;
3302 dest_states_nl = dest_states_word + ndests;
3303 bitset_empty (acceptable);
3305 /* Then build the states for all destinations. */
3306 for (i = 0; i < ndests; ++i)
3309 re_node_set_empty (&follows);
3310 /* Merge the follows of this destination states. */
3311 for (j = 0; j < dests_node[i].nelem; ++j)
3313 next_node = dfa->nexts[dests_node[i].elems[j]];
3314 if (next_node != -1)
3316 err = re_node_set_merge (&follows, dfa->eclosures + next_node);
3317 if (BE (err != REG_NOERROR, 0))
3321 dest_states[i] = re_acquire_state_context (&err, dfa, &follows, 0);
3322 if (BE (dest_states[i] == NULL && err != REG_NOERROR, 0))
3324 /* If the new state has context constraint,
3325 build appropriate states for these contexts. */
3326 if (dest_states[i]->has_constraint)
3328 dest_states_word[i] = re_acquire_state_context (&err, dfa, &follows,
3330 if (BE (dest_states_word[i] == NULL && err != REG_NOERROR, 0))
3333 if (dest_states[i] != dest_states_word[i] && dfa->mb_cur_max > 1)
3334 need_word_trtable = 1;
3336 dest_states_nl[i] = re_acquire_state_context (&err, dfa, &follows,
3338 if (BE (dest_states_nl[i] == NULL && err != REG_NOERROR, 0))
3343 dest_states_word[i] = dest_states[i];
3344 dest_states_nl[i] = dest_states[i];
3346 bitset_merge (acceptable, dests_ch[i]);
3349 if (!BE (need_word_trtable, 0))
3351 /* We don't care about whether the following character is a word
3352 character, or we are in a single-byte character set so we can
3353 discern by looking at the character code: allocate a
3354 256-entry transition table. */
3355 trtable = state->trtable =
3356 (re_dfastate_t **) calloc (sizeof (re_dfastate_t *), SBC_MAX);
3357 if (BE (trtable == NULL, 0))
3360 /* For all characters ch...: */
3361 for (i = 0; i < BITSET_UINTS; ++i)
3362 for (ch = i * UINT_BITS, elem = acceptable[i], mask = 1;
3364 mask <<= 1, elem >>= 1, ++ch)
3365 if (BE (elem & 1, 0))
3367 /* There must be exactly one destination which accepts
3368 character ch. See group_nodes_into_DFAstates. */
3369 for (j = 0; (dests_ch[j][i] & mask) == 0; ++j)
3372 /* j-th destination accepts the word character ch. */
3373 if (dfa->word_char[i] & mask)
3374 trtable[ch] = dest_states_word[j];
3376 trtable[ch] = dest_states[j];
3381 /* We care about whether the following character is a word
3382 character, and we are in a multi-byte character set: discern
3383 by looking at the character code: build two 256-entry
3384 transition tables, one starting at trtable[0] and one
3385 starting at trtable[SBC_MAX]. */
3386 trtable = state->word_trtable =
3387 (re_dfastate_t **) calloc (sizeof (re_dfastate_t *), 2 * SBC_MAX);
3388 if (BE (trtable == NULL, 0))
3391 /* For all characters ch...: */
3392 for (i = 0; i < BITSET_UINTS; ++i)
3393 for (ch = i * UINT_BITS, elem = acceptable[i], mask = 1;
3395 mask <<= 1, elem >>= 1, ++ch)
3396 if (BE (elem & 1, 0))
3398 /* There must be exactly one destination which accepts
3399 character ch. See group_nodes_into_DFAstates. */
3400 for (j = 0; (dests_ch[j][i] & mask) == 0; ++j)
3403 /* j-th destination accepts the word character ch. */
3404 trtable[ch] = dest_states[j];
3405 trtable[ch + SBC_MAX] = dest_states_word[j];
3410 if (bitset_contain (acceptable, NEWLINE_CHAR))
3412 /* The current state accepts newline character. */
3413 for (j = 0; j < ndests; ++j)
3414 if (bitset_contain (dests_ch[j], NEWLINE_CHAR))
3416 /* k-th destination accepts newline character. */
3417 trtable[NEWLINE_CHAR] = dest_states_nl[j];
3418 if (need_word_trtable)
3419 trtable[NEWLINE_CHAR + SBC_MAX] = dest_states_nl[j];
3420 /* There must be only one destination which accepts
3421 newline. See group_nodes_into_DFAstates. */
3426 if (dest_states_malloced)
3429 re_node_set_free (&follows);
3430 for (i = 0; i < ndests; ++i)
3431 re_node_set_free (dests_node + i);
3433 if (dests_node_malloced)
3439 /* Group all nodes belonging to STATE into several destinations.
3440 Then for all destinations, set the nodes belonging to the destination
3441 to DESTS_NODE[i] and set the characters accepted by the destination
3442 to DEST_CH[i]. This function return the number of destinations. */
3446 group_nodes_into_DFAstates (re_dfa_t *dfa, const re_dfastate_t *state,
3447 re_node_set *dests_node, bitset *dests_ch)
3452 int ndests; /* Number of the destinations from `state'. */
3453 bitset accepts; /* Characters a node can accept. */
3454 const re_node_set *cur_nodes = &state->nodes;
3455 bitset_empty (accepts);
3458 /* For all the nodes belonging to `state', */
3459 for (i = 0; i < cur_nodes->nelem; ++i)
3461 re_token_t *node = &dfa->nodes[cur_nodes->elems[i]];
3462 re_token_type_t type = node->type;
3463 unsigned int constraint = node->constraint;
3465 /* Enumerate all single byte character this node can accept. */
3466 if (type == CHARACTER)
3467 bitset_set (accepts, node->opr.c);
3468 else if (type == SIMPLE_BRACKET)
3470 bitset_merge (accepts, node->opr.sbcset);
3472 else if (type == OP_PERIOD)
3474 #ifdef RE_ENABLE_I18N
3475 if (dfa->mb_cur_max > 1)
3476 bitset_merge (accepts, dfa->sb_char);
3479 bitset_set_all (accepts);
3480 if (!(dfa->syntax & REG_DOT_NEWLINE))
3481 bitset_clear (accepts, '\n');
3482 if (dfa->syntax & REG_DOT_NOT_NULL)
3483 bitset_clear (accepts, '\0');
3485 #ifdef RE_ENABLE_I18N
3486 else if (type == OP_UTF8_PERIOD)
3488 memset (accepts, 255, sizeof (unsigned int) * BITSET_UINTS / 2);
3489 if (!(dfa->syntax & REG_DOT_NEWLINE))
3490 bitset_clear (accepts, '\n');
3491 if (dfa->syntax & REG_DOT_NOT_NULL)
3492 bitset_clear (accepts, '\0');
3498 /* Check the `accepts' and sift the characters which are not
3499 match it the context. */
3502 if (constraint & NEXT_NEWLINE_CONSTRAINT)
3504 int accepts_newline = bitset_contain (accepts, NEWLINE_CHAR);
3505 bitset_empty (accepts);
3506 if (accepts_newline)
3507 bitset_set (accepts, NEWLINE_CHAR);
3511 if (constraint & NEXT_ENDBUF_CONSTRAINT)
3513 bitset_empty (accepts);
3517 if (constraint & NEXT_WORD_CONSTRAINT)
3519 unsigned int any_set = 0;
3520 if (type == CHARACTER && !node->word_char)
3522 bitset_empty (accepts);
3525 #ifdef RE_ENABLE_I18N
3526 if (dfa->mb_cur_max > 1)
3527 for (j = 0; j < BITSET_UINTS; ++j)
3528 any_set |= (accepts[j] &= (dfa->word_char[j] | ~dfa->sb_char[j]));
3531 for (j = 0; j < BITSET_UINTS; ++j)
3532 any_set |= (accepts[j] &= dfa->word_char[j]);
3536 if (constraint & NEXT_NOTWORD_CONSTRAINT)
3538 unsigned int any_set = 0;
3539 if (type == CHARACTER && node->word_char)
3541 bitset_empty (accepts);
3544 #ifdef RE_ENABLE_I18N
3545 if (dfa->mb_cur_max > 1)
3546 for (j = 0; j < BITSET_UINTS; ++j)
3547 any_set |= (accepts[j] &= ~(dfa->word_char[j] & dfa->sb_char[j]));
3550 for (j = 0; j < BITSET_UINTS; ++j)
3551 any_set |= (accepts[j] &= ~dfa->word_char[j]);
3557 /* Then divide `accepts' into DFA states, or create a new
3558 state. Above, we make sure that accepts is not empty. */
3559 for (j = 0; j < ndests; ++j)
3561 bitset intersec; /* Intersection sets, see below. */
3563 /* Flags, see below. */
3564 int has_intersec, not_subset, not_consumed;
3566 /* Optimization, skip if this state doesn't accept the character. */
3567 if (type == CHARACTER && !bitset_contain (dests_ch[j], node->opr.c))
3570 /* Enumerate the intersection set of this state and `accepts'. */
3572 for (k = 0; k < BITSET_UINTS; ++k)
3573 has_intersec |= intersec[k] = accepts[k] & dests_ch[j][k];
3574 /* And skip if the intersection set is empty. */
3578 /* Then check if this state is a subset of `accepts'. */
3579 not_subset = not_consumed = 0;
3580 for (k = 0; k < BITSET_UINTS; ++k)
3582 not_subset |= remains[k] = ~accepts[k] & dests_ch[j][k];
3583 not_consumed |= accepts[k] = accepts[k] & ~dests_ch[j][k];
3586 /* If this state isn't a subset of `accepts', create a
3587 new group state, which has the `remains'. */
3590 bitset_copy (dests_ch[ndests], remains);
3591 bitset_copy (dests_ch[j], intersec);
3592 err = re_node_set_init_copy (dests_node + ndests, &dests_node[j]);
3593 if (BE (err != REG_NOERROR, 0))
3598 /* Put the position in the current group. */
3599 result = re_node_set_insert (&dests_node[j], cur_nodes->elems[i]);
3600 if (BE (result < 0, 0))
3603 /* If all characters are consumed, go to next node. */
3607 /* Some characters remain, create a new group. */
3610 bitset_copy (dests_ch[ndests], accepts);
3611 err = re_node_set_init_1 (dests_node + ndests, cur_nodes->elems[i]);
3612 if (BE (err != REG_NOERROR, 0))
3615 bitset_empty (accepts);
3620 for (j = 0; j < ndests; ++j)
3621 re_node_set_free (dests_node + j);
3625 #ifdef RE_ENABLE_I18N
3626 /* Check how many bytes the node `dfa->nodes[node_idx]' accepts.
3627 Return the number of the bytes the node accepts.
3628 STR_IDX is the current index of the input string.
3630 This function handles the nodes which can accept one character, or
3631 one collating element like '.', '[a-z]', opposite to the other nodes
3632 can only accept one byte. */
3636 check_node_accept_bytes (re_dfa_t *dfa, int node_idx,
3637 const re_string_t *input, int str_idx)
3639 const re_token_t *node = dfa->nodes + node_idx;
3640 int char_len, elem_len;
3643 if (BE (node->type == OP_UTF8_PERIOD, 0))
3645 unsigned char c = re_string_byte_at (input, str_idx), d;
3646 if (BE (c < 0xc2, 1))
3649 if (str_idx + 2 > input->len)
3652 d = re_string_byte_at (input, str_idx + 1);
3654 return (d < 0x80 || d > 0xbf) ? 0 : 2;
3658 if (c == 0xe0 && d < 0xa0)
3664 if (c == 0xf0 && d < 0x90)
3670 if (c == 0xf8 && d < 0x88)
3676 if (c == 0xfc && d < 0x84)
3682 if (str_idx + char_len > input->len)
3685 for (i = 1; i < char_len; ++i)
3687 d = re_string_byte_at (input, str_idx + i);
3688 if (d < 0x80 || d > 0xbf)
3694 char_len = re_string_char_size_at (input, str_idx);
3695 if (node->type == OP_PERIOD)
3699 /* FIXME: I don't think this if is needed, as both '\n'
3700 and '\0' are char_len == 1. */
3701 /* '.' accepts any one character except the following two cases. */
3702 if ((!(dfa->syntax & REG_DOT_NEWLINE) &&
3703 re_string_byte_at (input, str_idx) == '\n') ||
3704 ((dfa->syntax & REG_DOT_NOT_NULL) &&
3705 re_string_byte_at (input, str_idx) == '\0'))
3710 elem_len = re_string_elem_size_at (input, str_idx);
3711 if ((elem_len <= 1 && char_len <= 1) || char_len == 0)
3714 if (node->type == COMPLEX_BRACKET)
3716 const re_charset_t *cset = node->opr.mbcset;
3718 const unsigned char *pin
3719 = ((const unsigned char *) re_string_get_buffer (input) + str_idx);
3724 wchar_t wc = ((cset->nranges || cset->nchar_classes || cset->nmbchars)
3725 ? re_string_wchar_at (input, str_idx) : 0);
3727 /* match with multibyte character? */
3728 for (i = 0; i < cset->nmbchars; ++i)
3729 if (wc == cset->mbchars[i])
3731 match_len = char_len;
3732 goto check_node_accept_bytes_match;
3734 /* match with character_class? */
3735 for (i = 0; i < cset->nchar_classes; ++i)
3737 wctype_t wt = cset->char_classes[i];
3738 if (__iswctype (wc, wt))
3740 match_len = char_len;
3741 goto check_node_accept_bytes_match;
3746 nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
3749 unsigned int in_collseq = 0;
3750 const int32_t *table, *indirect;
3751 const unsigned char *weights, *extra;
3752 const char *collseqwc;
3754 /* This #include defines a local function! */
3755 # include <locale/weight.h>
3757 /* match with collating_symbol? */
3758 if (cset->ncoll_syms)
3759 extra = (const unsigned char *)
3760 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB);
3761 for (i = 0; i < cset->ncoll_syms; ++i)
3763 const unsigned char *coll_sym = extra + cset->coll_syms[i];
3764 /* Compare the length of input collating element and
3765 the length of current collating element. */
3766 if (*coll_sym != elem_len)
3768 /* Compare each bytes. */
3769 for (j = 0; j < *coll_sym; j++)
3770 if (pin[j] != coll_sym[1 + j])
3774 /* Match if every bytes is equal. */
3776 goto check_node_accept_bytes_match;
3782 if (elem_len <= char_len)
3784 collseqwc = _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQWC);
3785 in_collseq = __collseq_table_lookup (collseqwc, wc);
3788 in_collseq = find_collation_sequence_value (pin, elem_len);
3790 /* match with range expression? */
3791 for (i = 0; i < cset->nranges; ++i)
3792 if (cset->range_starts[i] <= in_collseq
3793 && in_collseq <= cset->range_ends[i])
3795 match_len = elem_len;
3796 goto check_node_accept_bytes_match;
3799 /* match with equivalence_class? */
3800 if (cset->nequiv_classes)
3802 const unsigned char *cp = pin;
3803 table = (const int32_t *)
3804 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
3805 weights = (const unsigned char *)
3806 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_WEIGHTMB);
3807 extra = (const unsigned char *)
3808 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAMB);
3809 indirect = (const int32_t *)
3810 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_INDIRECTMB);
3811 idx = findidx (&cp);
3813 for (i = 0; i < cset->nequiv_classes; ++i)
3815 int32_t equiv_class_idx = cset->equiv_classes[i];
3816 size_t weight_len = weights[idx];
3817 if (weight_len == weights[equiv_class_idx])
3820 while (cnt <= weight_len
3821 && (weights[equiv_class_idx + 1 + cnt]
3822 == weights[idx + 1 + cnt]))
3824 if (cnt > weight_len)
3826 match_len = elem_len;
3827 goto check_node_accept_bytes_match;
3836 /* match with range expression? */
3838 wchar_t cmp_buf[] = {L'\0', L'\0', wc, L'\0', L'\0', L'\0'};
3840 wchar_t cmp_buf[] = {L'\0', L'\0', L'\0', L'\0', L'\0', L'\0'};
3843 for (i = 0; i < cset->nranges; ++i)
3845 cmp_buf[0] = cset->range_starts[i];
3846 cmp_buf[4] = cset->range_ends[i];
3847 if (wcscoll (cmp_buf, cmp_buf + 2) <= 0
3848 && wcscoll (cmp_buf + 2, cmp_buf + 4) <= 0)
3850 match_len = char_len;
3851 goto check_node_accept_bytes_match;
3855 check_node_accept_bytes_match:
3856 if (!cset->non_match)
3863 return (elem_len > char_len) ? elem_len : char_len;
3871 find_collation_sequence_value (mbs, mbs_len)
3872 const unsigned char *mbs;
3875 uint32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
3880 /* No valid character. Match it as a single byte character. */
3881 const unsigned char *collseq = (const unsigned char *)
3882 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQMB);
3883 return collseq[mbs[0]];
3890 const unsigned char *extra = (const unsigned char *)
3891 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB);
3892 int32_t extrasize = (const unsigned char *)
3893 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB + 1) - extra;
3895 for (idx = 0; idx < extrasize;)
3897 int mbs_cnt, found = 0;
3898 int32_t elem_mbs_len;
3899 /* Skip the name of collating element name. */
3900 idx = idx + extra[idx] + 1;
3901 elem_mbs_len = extra[idx++];
3902 if (mbs_len == elem_mbs_len)
3904 for (mbs_cnt = 0; mbs_cnt < elem_mbs_len; ++mbs_cnt)
3905 if (extra[idx + mbs_cnt] != mbs[mbs_cnt])
3907 if (mbs_cnt == elem_mbs_len)
3908 /* Found the entry. */
3911 /* Skip the byte sequence of the collating element. */
3912 idx += elem_mbs_len;
3913 /* Adjust for the alignment. */
3914 idx = (idx + 3) & ~3;
3915 /* Skip the collation sequence value. */
3916 idx += sizeof (uint32_t);
3917 /* Skip the wide char sequence of the collating element. */
3918 idx = idx + sizeof (uint32_t) * (extra[idx] + 1);
3919 /* If we found the entry, return the sequence value. */
3921 return *(uint32_t *) (extra + idx);
3922 /* Skip the collation sequence value. */
3923 idx += sizeof (uint32_t);
3929 #endif /* RE_ENABLE_I18N */
3931 /* Check whether the node accepts the byte which is IDX-th
3932 byte of the INPUT. */
3936 check_node_accept (const re_match_context_t *mctx, const re_token_t *node,
3940 ch = re_string_byte_at (&mctx->input, idx);
3944 if (node->opr.c != ch)
3948 case SIMPLE_BRACKET:
3949 if (!bitset_contain (node->opr.sbcset, ch))
3953 #ifdef RE_ENABLE_I18N
3954 case OP_UTF8_PERIOD:
3960 if ((ch == '\n' && !(mctx->dfa->syntax & REG_DOT_NEWLINE))
3961 || (ch == '\0' && (mctx->dfa->syntax & REG_DOT_NOT_NULL)))
3969 if (node->constraint)
3971 /* The node has constraints. Check whether the current context
3972 satisfies the constraints. */
3973 unsigned int context = re_string_context_at (&mctx->input, idx,
3975 if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
3982 /* Extend the buffers, if the buffers have run out. */
3984 static reg_errcode_t
3986 extend_buffers (re_match_context_t *mctx)
3989 re_string_t *pstr = &mctx->input;
3991 /* Double the lengthes of the buffers. */
3992 ret = re_string_realloc_buffers (pstr, pstr->bufs_len * 2);
3993 if (BE (ret != REG_NOERROR, 0))
3996 if (mctx->state_log != NULL)
3998 /* And double the length of state_log. */
3999 /* XXX We have no indication of the size of this buffer. If this
4000 allocation fail we have no indication that the state_log array
4001 does not have the right size. */
4002 re_dfastate_t **new_array = re_realloc (mctx->state_log, re_dfastate_t *,
4003 pstr->bufs_len + 1);
4004 if (BE (new_array == NULL, 0))
4006 mctx->state_log = new_array;
4009 /* Then reconstruct the buffers. */
4012 #ifdef RE_ENABLE_I18N
4013 if (pstr->mb_cur_max > 1)
4015 ret = build_wcs_upper_buffer (pstr);
4016 if (BE (ret != REG_NOERROR, 0))
4020 #endif /* RE_ENABLE_I18N */
4021 build_upper_buffer (pstr);
4025 #ifdef RE_ENABLE_I18N
4026 if (pstr->mb_cur_max > 1)
4027 build_wcs_buffer (pstr);
4029 #endif /* RE_ENABLE_I18N */
4031 if (pstr->trans != NULL)
4032 re_string_translate_buffer (pstr);
4039 /* Functions for matching context. */
4041 /* Initialize MCTX. */
4043 static reg_errcode_t
4045 match_ctx_init (re_match_context_t *mctx, int eflags, int n)
4047 mctx->eflags = eflags;
4048 mctx->match_last = -1;
4051 mctx->bkref_ents = re_malloc (struct re_backref_cache_entry, n);
4052 mctx->sub_tops = re_malloc (re_sub_match_top_t *, n);
4053 if (BE (mctx->bkref_ents == NULL || mctx->sub_tops == NULL, 0))
4056 /* Already zero-ed by the caller.
4058 mctx->bkref_ents = NULL;
4059 mctx->nbkref_ents = 0;
4060 mctx->nsub_tops = 0; */
4061 mctx->abkref_ents = n;
4062 mctx->max_mb_elem_len = 1;
4063 mctx->asub_tops = n;
4067 /* Clean the entries which depend on the current input in MCTX.
4068 This function must be invoked when the matcher changes the start index
4069 of the input, or changes the input string. */
4073 match_ctx_clean (re_match_context_t *mctx)
4076 for (st_idx = 0; st_idx < mctx->nsub_tops; ++st_idx)
4079 re_sub_match_top_t *top = mctx->sub_tops[st_idx];
4080 for (sl_idx = 0; sl_idx < top->nlasts; ++sl_idx)
4082 re_sub_match_last_t *last = top->lasts[sl_idx];
4083 re_free (last->path.array);
4086 re_free (top->lasts);
4089 re_free (top->path->array);
4090 re_free (top->path);
4095 mctx->nsub_tops = 0;
4096 mctx->nbkref_ents = 0;
4099 /* Free all the memory associated with MCTX. */
4103 match_ctx_free (re_match_context_t *mctx)
4105 /* First, free all the memory associated with MCTX->SUB_TOPS. */
4106 match_ctx_clean (mctx);
4107 re_free (mctx->sub_tops);
4108 re_free (mctx->bkref_ents);
4111 /* Add a new backreference entry to MCTX.
4112 Note that we assume that caller never call this function with duplicate
4113 entry, and call with STR_IDX which isn't smaller than any existing entry.
4116 static reg_errcode_t
4118 match_ctx_add_entry (re_match_context_t *mctx, int node, int str_idx,
4121 if (mctx->nbkref_ents >= mctx->abkref_ents)
4123 struct re_backref_cache_entry* new_entry;
4124 new_entry = re_realloc (mctx->bkref_ents, struct re_backref_cache_entry,
4125 mctx->abkref_ents * 2);
4126 if (BE (new_entry == NULL, 0))
4128 re_free (mctx->bkref_ents);
4131 mctx->bkref_ents = new_entry;
4132 memset (mctx->bkref_ents + mctx->nbkref_ents, '\0',
4133 sizeof (struct re_backref_cache_entry) * mctx->abkref_ents);
4134 mctx->abkref_ents *= 2;
4136 if (mctx->nbkref_ents > 0
4137 && mctx->bkref_ents[mctx->nbkref_ents - 1].str_idx == str_idx)
4138 mctx->bkref_ents[mctx->nbkref_ents - 1].more = 1;
4140 mctx->bkref_ents[mctx->nbkref_ents].node = node;
4141 mctx->bkref_ents[mctx->nbkref_ents].str_idx = str_idx;
4142 mctx->bkref_ents[mctx->nbkref_ents].subexp_from = from;
4143 mctx->bkref_ents[mctx->nbkref_ents].subexp_to = to;
4145 /* This is a cache that saves negative results of check_dst_limits_calc_pos.
4146 If bit N is clear, means that this entry won't epsilon-transition to
4147 an OP_OPEN_SUBEXP or OP_CLOSE_SUBEXP for the N+1-th subexpression. If
4148 it is set, check_dst_limits_calc_pos_1 will recurse and try to find one
4151 A backreference does not epsilon-transition unless it is empty, so set
4152 to all zeros if FROM != TO. */
4153 mctx->bkref_ents[mctx->nbkref_ents].eps_reachable_subexps_map
4154 = (from == to ? ~0 : 0);
4156 mctx->bkref_ents[mctx->nbkref_ents++].more = 0;
4157 if (mctx->max_mb_elem_len < to - from)
4158 mctx->max_mb_elem_len = to - from;
4162 /* Search for the first entry which has the same str_idx, or -1 if none is
4163 found. Note that MCTX->BKREF_ENTS is already sorted by MCTX->STR_IDX. */
4167 search_cur_bkref_entry (re_match_context_t *mctx, int str_idx)
4169 int left, right, mid, last;
4170 last = right = mctx->nbkref_ents;
4171 for (left = 0; left < right;)
4173 mid = (left + right) / 2;
4174 if (mctx->bkref_ents[mid].str_idx < str_idx)
4179 if (left < last && mctx->bkref_ents[left].str_idx == str_idx)
4185 /* Register the node NODE, whose type is OP_OPEN_SUBEXP, and which matches
4188 static reg_errcode_t
4190 match_ctx_add_subtop (re_match_context_t *mctx, int node, int str_idx)
4193 assert (mctx->sub_tops != NULL);
4194 assert (mctx->asub_tops > 0);
4196 if (BE (mctx->nsub_tops == mctx->asub_tops, 0))
4198 int new_asub_tops = mctx->asub_tops * 2;
4199 re_sub_match_top_t **new_array = re_realloc (mctx->sub_tops,
4200 re_sub_match_top_t *,
4202 if (BE (new_array == NULL, 0))
4204 mctx->sub_tops = new_array;
4205 mctx->asub_tops = new_asub_tops;
4207 mctx->sub_tops[mctx->nsub_tops] = calloc (1, sizeof (re_sub_match_top_t));
4208 if (BE (mctx->sub_tops[mctx->nsub_tops] == NULL, 0))
4210 mctx->sub_tops[mctx->nsub_tops]->node = node;
4211 mctx->sub_tops[mctx->nsub_tops++]->str_idx = str_idx;
4215 /* Register the node NODE, whose type is OP_CLOSE_SUBEXP, and which matches
4216 at STR_IDX, whose corresponding OP_OPEN_SUBEXP is SUB_TOP. */
4218 static re_sub_match_last_t *
4220 match_ctx_add_sublast (re_sub_match_top_t *subtop, int node, int str_idx)
4222 re_sub_match_last_t *new_entry;
4223 if (BE (subtop->nlasts == subtop->alasts, 0))
4225 int new_alasts = 2 * subtop->alasts + 1;
4226 re_sub_match_last_t **new_array = re_realloc (subtop->lasts,
4227 re_sub_match_last_t *,
4229 if (BE (new_array == NULL, 0))
4231 subtop->lasts = new_array;
4232 subtop->alasts = new_alasts;
4234 new_entry = calloc (1, sizeof (re_sub_match_last_t));
4235 if (BE (new_entry != NULL, 1))
4237 subtop->lasts[subtop->nlasts] = new_entry;
4238 new_entry->node = node;
4239 new_entry->str_idx = str_idx;
4247 sift_ctx_init (re_sift_context_t *sctx,
4248 re_dfastate_t **sifted_sts,
4249 re_dfastate_t **limited_sts,
4250 int last_node, int last_str_idx)
4252 sctx->sifted_states = sifted_sts;
4253 sctx->limited_states = limited_sts;
4254 sctx->last_node = last_node;
4255 sctx->last_str_idx = last_str_idx;
4256 re_node_set_init_empty (&sctx->limits);