1 /* Extended regular expression matching and search library.
2 Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008 Free Software Foundation,
4 This file is part of the GNU C Library.
5 Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>.
7 This program is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 This program is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License along
18 with this program; if not, write to the Free Software Foundation,
19 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
21 static reg_errcode_t match_ctx_init (re_match_context_t *cache, int eflags,
22 Idx n) internal_function;
23 static void match_ctx_clean (re_match_context_t *mctx) internal_function;
24 static void match_ctx_free (re_match_context_t *cache) internal_function;
25 static reg_errcode_t match_ctx_add_entry (re_match_context_t *cache, Idx node,
26 Idx str_idx, Idx from, Idx to)
28 static Idx search_cur_bkref_entry (const re_match_context_t *mctx, Idx str_idx)
30 static reg_errcode_t match_ctx_add_subtop (re_match_context_t *mctx, Idx node,
31 Idx str_idx) internal_function;
32 static re_sub_match_last_t * match_ctx_add_sublast (re_sub_match_top_t *subtop,
33 Idx node, Idx str_idx)
35 static void sift_ctx_init (re_sift_context_t *sctx, re_dfastate_t **sifted_sts,
36 re_dfastate_t **limited_sts, Idx last_node,
39 static reg_errcode_t re_search_internal (const regex_t *preg,
40 const char *string, Idx length,
41 Idx start, Idx last_start, Idx stop,
42 size_t nmatch, regmatch_t pmatch[],
43 int eflags) internal_function;
44 static regoff_t re_search_2_stub (struct re_pattern_buffer *bufp,
45 const char *string1, Idx length1,
46 const char *string2, Idx length2,
47 Idx start, regoff_t range,
48 struct re_registers *regs,
49 Idx stop, bool ret_len) internal_function;
50 static regoff_t re_search_stub (struct re_pattern_buffer *bufp,
51 const char *string, Idx length, Idx start,
52 regoff_t range, Idx stop,
53 struct re_registers *regs,
54 bool ret_len) internal_function;
55 static unsigned int re_copy_regs (struct re_registers *regs, regmatch_t *pmatch,
56 Idx nregs, int regs_allocated)
58 static reg_errcode_t prune_impossible_nodes (re_match_context_t *mctx)
60 static Idx check_matching (re_match_context_t *mctx, bool fl_longest_match,
61 Idx *p_match_first) internal_function;
62 static Idx check_halt_state_context (const re_match_context_t *mctx,
63 const re_dfastate_t *state, Idx idx)
65 static void update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
66 regmatch_t *prev_idx_match, Idx cur_node,
67 Idx cur_idx, Idx nmatch) internal_function;
68 static reg_errcode_t push_fail_stack (struct re_fail_stack_t *fs,
69 Idx str_idx, Idx dest_node, Idx nregs,
71 re_node_set *eps_via_nodes)
73 static reg_errcode_t set_regs (const regex_t *preg,
74 const re_match_context_t *mctx,
75 size_t nmatch, regmatch_t *pmatch,
76 bool fl_backtrack) internal_function;
77 static reg_errcode_t free_fail_stack_return (struct re_fail_stack_t *fs)
81 static int sift_states_iter_mb (const re_match_context_t *mctx,
82 re_sift_context_t *sctx,
83 Idx node_idx, Idx str_idx, Idx max_str_idx)
85 #endif /* RE_ENABLE_I18N */
86 static reg_errcode_t sift_states_backward (const re_match_context_t *mctx,
87 re_sift_context_t *sctx)
89 static reg_errcode_t build_sifted_states (const re_match_context_t *mctx,
90 re_sift_context_t *sctx, Idx str_idx,
91 re_node_set *cur_dest)
93 static reg_errcode_t update_cur_sifted_state (const re_match_context_t *mctx,
94 re_sift_context_t *sctx,
96 re_node_set *dest_nodes)
98 static reg_errcode_t add_epsilon_src_nodes (const re_dfa_t *dfa,
99 re_node_set *dest_nodes,
100 const re_node_set *candidates)
102 static bool check_dst_limits (const re_match_context_t *mctx,
103 const re_node_set *limits,
104 Idx dst_node, Idx dst_idx, Idx src_node,
105 Idx src_idx) internal_function;
106 static int check_dst_limits_calc_pos_1 (const re_match_context_t *mctx,
107 int boundaries, Idx subexp_idx,
108 Idx from_node, Idx bkref_idx)
110 static int check_dst_limits_calc_pos (const re_match_context_t *mctx,
111 Idx limit, Idx subexp_idx,
112 Idx node, Idx str_idx,
113 Idx bkref_idx) internal_function;
114 static reg_errcode_t check_subexp_limits (const re_dfa_t *dfa,
115 re_node_set *dest_nodes,
116 const re_node_set *candidates,
118 struct re_backref_cache_entry *bkref_ents,
119 Idx str_idx) internal_function;
120 static reg_errcode_t sift_states_bkref (const re_match_context_t *mctx,
121 re_sift_context_t *sctx,
122 Idx str_idx, const re_node_set *candidates)
124 static reg_errcode_t merge_state_array (const re_dfa_t *dfa,
126 re_dfastate_t **src, Idx num)
128 static re_dfastate_t *find_recover_state (reg_errcode_t *err,
129 re_match_context_t *mctx) internal_function;
130 static re_dfastate_t *transit_state (reg_errcode_t *err,
131 re_match_context_t *mctx,
132 re_dfastate_t *state) internal_function;
133 static re_dfastate_t *merge_state_with_log (reg_errcode_t *err,
134 re_match_context_t *mctx,
135 re_dfastate_t *next_state)
137 static reg_errcode_t check_subexp_matching_top (re_match_context_t *mctx,
138 re_node_set *cur_nodes,
139 Idx str_idx) internal_function;
141 static re_dfastate_t *transit_state_sb (reg_errcode_t *err,
142 re_match_context_t *mctx,
143 re_dfastate_t *pstate)
146 #ifdef RE_ENABLE_I18N
147 static reg_errcode_t transit_state_mb (re_match_context_t *mctx,
148 re_dfastate_t *pstate)
150 #endif /* RE_ENABLE_I18N */
151 static reg_errcode_t transit_state_bkref (re_match_context_t *mctx,
152 const re_node_set *nodes)
154 static reg_errcode_t get_subexp (re_match_context_t *mctx,
155 Idx bkref_node, Idx bkref_str_idx)
157 static reg_errcode_t get_subexp_sub (re_match_context_t *mctx,
158 const re_sub_match_top_t *sub_top,
159 re_sub_match_last_t *sub_last,
160 Idx bkref_node, Idx bkref_str)
162 static Idx find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
163 Idx subexp_idx, int type) internal_function;
164 static reg_errcode_t check_arrival (re_match_context_t *mctx,
165 state_array_t *path, Idx top_node,
166 Idx top_str, Idx last_node, Idx last_str,
167 int type) internal_function;
168 static reg_errcode_t check_arrival_add_next_nodes (re_match_context_t *mctx,
170 re_node_set *cur_nodes,
171 re_node_set *next_nodes)
173 static reg_errcode_t check_arrival_expand_ecl (const re_dfa_t *dfa,
174 re_node_set *cur_nodes,
175 Idx ex_subexp, int type)
177 static reg_errcode_t check_arrival_expand_ecl_sub (const re_dfa_t *dfa,
178 re_node_set *dst_nodes,
179 Idx target, Idx ex_subexp,
180 int type) internal_function;
181 static reg_errcode_t expand_bkref_cache (re_match_context_t *mctx,
182 re_node_set *cur_nodes, Idx cur_str,
183 Idx subexp_num, int type)
185 static bool build_trtable (const re_dfa_t *dfa,
186 re_dfastate_t *state) internal_function;
187 #ifdef RE_ENABLE_I18N
188 static int check_node_accept_bytes (const re_dfa_t *dfa, Idx node_idx,
189 const re_string_t *input, Idx idx)
192 static unsigned int find_collation_sequence_value (const unsigned char *mbs,
196 #endif /* RE_ENABLE_I18N */
197 static Idx group_nodes_into_DFAstates (const re_dfa_t *dfa,
198 const re_dfastate_t *state,
199 re_node_set *states_node,
200 bitset_t *states_ch) internal_function;
201 static bool check_node_accept (const re_match_context_t *mctx,
202 const re_token_t *node, Idx idx)
204 static reg_errcode_t extend_buffers (re_match_context_t *mctx)
207 /* Entry point for POSIX code. */
209 /* regexec searches for a given pattern, specified by PREG, in the
212 If NMATCH is zero or REG_NOSUB was set in the cflags argument to
213 `regcomp', we ignore PMATCH. Otherwise, we assume PMATCH has at
214 least NMATCH elements, and we set them to the offsets of the
215 corresponding matched substrings.
217 EFLAGS specifies `execution flags' which affect matching: if
218 REG_NOTBOL is set, then ^ does not match at the beginning of the
219 string; if REG_NOTEOL is set, then $ does not match at the end.
221 We return 0 if we find a match and REG_NOMATCH if not. */
224 regexec (preg, string, nmatch, pmatch, eflags)
225 const regex_t *_Restrict_ preg;
226 const char *_Restrict_ string;
228 regmatch_t pmatch[_Restrict_arr_];
234 re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
237 if (eflags & ~(REG_NOTBOL | REG_NOTEOL | REG_STARTEND))
240 if (eflags & REG_STARTEND)
242 start = pmatch[0].rm_so;
243 length = pmatch[0].rm_eo;
248 length = strlen (string);
251 __libc_lock_lock (dfa->lock);
253 err = re_search_internal (preg, string, length, start, length,
254 length, 0, NULL, eflags);
256 err = re_search_internal (preg, string, length, start, length,
257 length, nmatch, pmatch, eflags);
258 __libc_lock_unlock (dfa->lock);
259 return err != REG_NOERROR;
263 # include <shlib-compat.h>
264 versioned_symbol (libc, __regexec, regexec, GLIBC_2_3_4);
266 # if SHLIB_COMPAT (libc, GLIBC_2_0, GLIBC_2_3_4)
267 __typeof__ (__regexec) __compat_regexec;
270 attribute_compat_text_section
271 __compat_regexec (const regex_t *_Restrict_ preg,
272 const char *_Restrict_ string, size_t nmatch,
273 regmatch_t pmatch[], int eflags)
275 return regexec (preg, string, nmatch, pmatch,
276 eflags & (REG_NOTBOL | REG_NOTEOL));
278 compat_symbol (libc, __compat_regexec, regexec, GLIBC_2_0);
282 /* Entry points for GNU code. */
284 /* re_match, re_search, re_match_2, re_search_2
286 The former two functions operate on STRING with length LENGTH,
287 while the later two operate on concatenation of STRING1 and STRING2
288 with lengths LENGTH1 and LENGTH2, respectively.
290 re_match() matches the compiled pattern in BUFP against the string,
291 starting at index START.
293 re_search() first tries matching at index START, then it tries to match
294 starting from index START + 1, and so on. The last start position tried
295 is START + RANGE. (Thus RANGE = 0 forces re_search to operate the same
298 The parameter STOP of re_{match,search}_2 specifies that no match exceeding
299 the first STOP characters of the concatenation of the strings should be
302 If REGS is not NULL, and BUFP->no_sub is not set, the offsets of the match
303 and all groups is stored in REGS. (For the "_2" variants, the offsets are
304 computed relative to the concatenation, not relative to the individual
307 On success, re_match* functions return the length of the match, re_search*
308 return the position of the start of the match. Return value -1 means no
309 match was found and -2 indicates an internal error. */
312 re_match (bufp, string, length, start, regs)
313 struct re_pattern_buffer *bufp;
316 struct re_registers *regs;
318 return re_search_stub (bufp, string, length, start, 0, length, regs, true);
321 weak_alias (__re_match, re_match)
325 re_search (bufp, string, length, start, range, regs)
326 struct re_pattern_buffer *bufp;
330 struct re_registers *regs;
332 return re_search_stub (bufp, string, length, start, range, length, regs,
336 weak_alias (__re_search, re_search)
340 re_match_2 (bufp, string1, length1, string2, length2, start, regs, stop)
341 struct re_pattern_buffer *bufp;
342 const char *string1, *string2;
343 Idx length1, length2, start, stop;
344 struct re_registers *regs;
346 return re_search_2_stub (bufp, string1, length1, string2, length2,
347 start, 0, regs, stop, true);
350 weak_alias (__re_match_2, re_match_2)
354 re_search_2 (bufp, string1, length1, string2, length2, start, range, regs, stop)
355 struct re_pattern_buffer *bufp;
356 const char *string1, *string2;
357 Idx length1, length2, start, stop;
359 struct re_registers *regs;
361 return re_search_2_stub (bufp, string1, length1, string2, length2,
362 start, range, regs, stop, false);
365 weak_alias (__re_search_2, re_search_2)
370 re_search_2_stub (struct re_pattern_buffer *bufp,
371 const char *string1, Idx length1,
372 const char *string2, Idx length2,
373 Idx start, regoff_t range, struct re_registers *regs,
374 Idx stop, bool ret_len)
378 Idx len = length1 + length2;
381 if (BE (length1 < 0 || length2 < 0 || stop < 0 || len < length1, 0))
384 /* Concatenate the strings. */
388 s = re_malloc (char, len);
390 if (BE (s == NULL, 0))
393 memcpy (__mempcpy (s, string1, length1), string2, length2);
395 memcpy (s, string1, length1);
396 memcpy (s + length1, string2, length2);
405 rval = re_search_stub (bufp, str, len, start, range, stop, regs,
411 /* The parameters have the same meaning as those of re_search.
412 Additional parameters:
413 If RET_LEN is true the length of the match is returned (re_match style);
414 otherwise the position of the match is returned. */
418 re_search_stub (struct re_pattern_buffer *bufp,
419 const char *string, Idx length,
420 Idx start, regoff_t range, Idx stop, struct re_registers *regs,
423 reg_errcode_t result;
429 re_dfa_t *dfa = (re_dfa_t *) bufp->buffer;
431 Idx last_start = start + range;
433 /* Check for out-of-range. */
434 if (BE (start < 0 || start > length, 0))
436 if (BE (length < last_start || (0 <= range && last_start < start), 0))
438 else if (BE (last_start < 0 || (range < 0 && start <= last_start), 0))
441 __libc_lock_lock (dfa->lock);
443 eflags |= (bufp->not_bol) ? REG_NOTBOL : 0;
444 eflags |= (bufp->not_eol) ? REG_NOTEOL : 0;
446 /* Compile fastmap if we haven't yet. */
447 if (start < last_start && bufp->fastmap != NULL && !bufp->fastmap_accurate)
448 re_compile_fastmap (bufp);
450 if (BE (bufp->no_sub, 0))
453 /* We need at least 1 register. */
456 else if (BE (bufp->regs_allocated == REGS_FIXED
457 && regs->num_regs <= bufp->re_nsub, 0))
459 nregs = regs->num_regs;
460 if (BE (nregs < 1, 0))
462 /* Nothing can be copied to regs. */
468 nregs = bufp->re_nsub + 1;
469 pmatch = re_malloc (regmatch_t, nregs);
470 if (BE (pmatch == NULL, 0))
476 result = re_search_internal (bufp, string, length, start, last_start, stop,
477 nregs, pmatch, eflags);
481 /* I hope we needn't fill ther regs with -1's when no match was found. */
482 if (result != REG_NOERROR)
484 else if (regs != NULL)
486 /* If caller wants register contents data back, copy them. */
487 bufp->regs_allocated = re_copy_regs (regs, pmatch, nregs,
488 bufp->regs_allocated);
489 if (BE (bufp->regs_allocated == REGS_UNALLOCATED, 0))
493 if (BE (rval == 0, 1))
497 assert (pmatch[0].rm_so == start);
498 rval = pmatch[0].rm_eo - start;
501 rval = pmatch[0].rm_so;
505 __libc_lock_unlock (dfa->lock);
511 re_copy_regs (struct re_registers *regs, regmatch_t *pmatch, Idx nregs,
514 int rval = REGS_REALLOCATE;
516 Idx need_regs = nregs + 1;
517 /* We need one extra element beyond `num_regs' for the `-1' marker GNU code
520 /* Have the register data arrays been allocated? */
521 if (regs_allocated == REGS_UNALLOCATED)
522 { /* No. So allocate them with malloc. */
523 regs->start = re_malloc (regoff_t, need_regs);
524 if (BE (regs->start == NULL, 0))
525 return REGS_UNALLOCATED;
526 regs->end = re_malloc (regoff_t, need_regs);
527 if (BE (regs->end == NULL, 0))
529 re_free (regs->start);
530 return REGS_UNALLOCATED;
532 regs->num_regs = need_regs;
534 else if (regs_allocated == REGS_REALLOCATE)
535 { /* Yes. If we need more elements than were already
536 allocated, reallocate them. If we need fewer, just
538 if (BE (need_regs > regs->num_regs, 0))
540 regoff_t *new_start = re_realloc (regs->start, regoff_t, need_regs);
542 if (BE (new_start == NULL, 0))
543 return REGS_UNALLOCATED;
544 new_end = re_realloc (regs->end, regoff_t, need_regs);
545 if (BE (new_end == NULL, 0))
548 return REGS_UNALLOCATED;
550 regs->start = new_start;
552 regs->num_regs = need_regs;
557 assert (regs_allocated == REGS_FIXED);
558 /* This function may not be called with REGS_FIXED and nregs too big. */
559 assert (regs->num_regs >= nregs);
564 for (i = 0; i < nregs; ++i)
566 regs->start[i] = pmatch[i].rm_so;
567 regs->end[i] = pmatch[i].rm_eo;
569 for ( ; i < regs->num_regs; ++i)
570 regs->start[i] = regs->end[i] = -1;
575 /* Set REGS to hold NUM_REGS registers, storing them in STARTS and
576 ENDS. Subsequent matches using PATTERN_BUFFER and REGS will use
577 this memory for recording register information. STARTS and ENDS
578 must be allocated using the malloc library routine, and must each
579 be at least NUM_REGS * sizeof (regoff_t) bytes long.
581 If NUM_REGS == 0, then subsequent matches should allocate their own
584 Unless this function is called, the first search or match using
585 PATTERN_BUFFER will allocate its own register data, without
586 freeing the old data. */
589 re_set_registers (bufp, regs, num_regs, starts, ends)
590 struct re_pattern_buffer *bufp;
591 struct re_registers *regs;
592 __re_size_t num_regs;
593 regoff_t *starts, *ends;
597 bufp->regs_allocated = REGS_REALLOCATE;
598 regs->num_regs = num_regs;
599 regs->start = starts;
604 bufp->regs_allocated = REGS_UNALLOCATED;
606 regs->start = regs->end = NULL;
610 weak_alias (__re_set_registers, re_set_registers)
613 /* Entry points compatible with 4.2 BSD regex library. We don't define
614 them unless specifically requested. */
616 #if defined _REGEX_RE_COMP || defined _LIBC
624 return 0 == regexec (&re_comp_buf, s, 0, NULL, 0);
626 #endif /* _REGEX_RE_COMP */
628 /* Internal entry point. */
630 /* Searches for a compiled pattern PREG in the string STRING, whose
631 length is LENGTH. NMATCH, PMATCH, and EFLAGS have the same
632 meaning as with regexec. LAST_START is START + RANGE, where
633 START and RANGE have the same meaning as with re_search.
634 Return REG_NOERROR if we find a match, and REG_NOMATCH if not,
635 otherwise return the error code.
636 Note: We assume front end functions already check ranges.
637 (0 <= LAST_START && LAST_START <= LENGTH) */
641 re_search_internal (const regex_t *preg,
642 const char *string, Idx length,
643 Idx start, Idx last_start, Idx stop,
644 size_t nmatch, regmatch_t pmatch[],
648 const re_dfa_t *dfa = (const re_dfa_t *) preg->buffer;
649 Idx left_lim, right_lim;
651 bool fl_longest_match;
654 Idx match_last = REG_MISSING;
658 #if defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L)
659 re_match_context_t mctx = { .dfa = dfa };
661 re_match_context_t mctx;
663 char *fastmap = ((preg->fastmap != NULL && preg->fastmap_accurate
664 && start != last_start && !preg->can_be_null)
665 ? preg->fastmap : NULL);
666 RE_TRANSLATE_TYPE t = preg->translate;
668 #if !(defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L))
669 memset (&mctx, '\0', sizeof (re_match_context_t));
673 extra_nmatch = (nmatch > preg->re_nsub) ? nmatch - (preg->re_nsub + 1) : 0;
674 nmatch -= extra_nmatch;
676 /* Check if the DFA haven't been compiled. */
677 if (BE (preg->used == 0 || dfa->init_state == NULL
678 || dfa->init_state_word == NULL || dfa->init_state_nl == NULL
679 || dfa->init_state_begbuf == NULL, 0))
683 /* We assume front-end functions already check them. */
684 assert (0 <= last_start && last_start <= length);
687 /* If initial states with non-begbuf contexts have no elements,
688 the regex must be anchored. If preg->newline_anchor is set,
689 we'll never use init_state_nl, so do not check it. */
690 if (dfa->init_state->nodes.nelem == 0
691 && dfa->init_state_word->nodes.nelem == 0
692 && (dfa->init_state_nl->nodes.nelem == 0
693 || !preg->newline_anchor))
695 if (start != 0 && last_start != 0)
697 start = last_start = 0;
700 /* We must check the longest matching, if nmatch > 0. */
701 fl_longest_match = (nmatch != 0 || dfa->nbackref);
703 err = re_string_allocate (&mctx.input, string, length, dfa->nodes_len + 1,
704 preg->translate, (preg->syntax & RE_ICASE) != 0,
706 if (BE (err != REG_NOERROR, 0))
708 mctx.input.stop = stop;
709 mctx.input.raw_stop = stop;
710 mctx.input.newline_anchor = preg->newline_anchor;
712 err = match_ctx_init (&mctx, eflags, dfa->nbackref * 2);
713 if (BE (err != REG_NOERROR, 0))
716 /* We will log all the DFA states through which the dfa pass,
717 if nmatch > 1, or this dfa has "multibyte node", which is a
718 back-reference or a node which can accept multibyte character or
719 multi character collating element. */
720 if (nmatch > 1 || dfa->has_mb_node)
722 /* Avoid overflow. */
723 if (BE (SIZE_MAX / sizeof (re_dfastate_t *) <= mctx.input.bufs_len, 0))
729 mctx.state_log = re_malloc (re_dfastate_t *, mctx.input.bufs_len + 1);
730 if (BE (mctx.state_log == NULL, 0))
737 mctx.state_log = NULL;
740 mctx.input.tip_context = (eflags & REG_NOTBOL) ? CONTEXT_BEGBUF
741 : CONTEXT_NEWLINE | CONTEXT_BEGBUF;
743 /* Check incrementally whether of not the input string match. */
744 incr = (last_start < start) ? -1 : 1;
745 left_lim = (last_start < start) ? last_start : start;
746 right_lim = (last_start < start) ? start : last_start;
747 sb = dfa->mb_cur_max == 1;
750 ? ((sb || !(preg->syntax & RE_ICASE || t) ? 4 : 0)
751 | (start <= last_start ? 2 : 0)
752 | (t != NULL ? 1 : 0))
755 for (;; match_first += incr)
758 if (match_first < left_lim || right_lim < match_first)
761 /* Advance as rapidly as possible through the string, until we
762 find a plausible place to start matching. This may be done
763 with varying efficiency, so there are various possibilities:
764 only the most common of them are specialized, in order to
765 save on code size. We use a switch statement for speed. */
773 /* Fastmap with single-byte translation, match forward. */
774 while (BE (match_first < right_lim, 1)
775 && !fastmap[t[(unsigned char) string[match_first]]])
777 goto forward_match_found_start_or_reached_end;
780 /* Fastmap without translation, match forward. */
781 while (BE (match_first < right_lim, 1)
782 && !fastmap[(unsigned char) string[match_first]])
785 forward_match_found_start_or_reached_end:
786 if (BE (match_first == right_lim, 0))
788 ch = match_first >= length
789 ? 0 : (unsigned char) string[match_first];
790 if (!fastmap[t ? t[ch] : ch])
797 /* Fastmap without multi-byte translation, match backwards. */
798 while (match_first >= left_lim)
800 ch = match_first >= length
801 ? 0 : (unsigned char) string[match_first];
802 if (fastmap[t ? t[ch] : ch])
806 if (match_first < left_lim)
811 /* In this case, we can't determine easily the current byte,
812 since it might be a component byte of a multibyte
813 character. Then we use the constructed buffer instead. */
816 /* If MATCH_FIRST is out of the valid range, reconstruct the
818 __re_size_t offset = match_first - mctx.input.raw_mbs_idx;
819 if (BE (offset >= (__re_size_t) mctx.input.valid_raw_len, 0))
821 err = re_string_reconstruct (&mctx.input, match_first,
823 if (BE (err != REG_NOERROR, 0))
826 offset = match_first - mctx.input.raw_mbs_idx;
828 /* If MATCH_FIRST is out of the buffer, leave it as '\0'.
829 Note that MATCH_FIRST must not be smaller than 0. */
830 ch = (match_first >= length
831 ? 0 : re_string_byte_at (&mctx.input, offset));
835 if (match_first < left_lim || match_first > right_lim)
844 /* Reconstruct the buffers so that the matcher can assume that
845 the matching starts from the beginning of the buffer. */
846 err = re_string_reconstruct (&mctx.input, match_first, eflags);
847 if (BE (err != REG_NOERROR, 0))
850 #ifdef RE_ENABLE_I18N
851 /* Don't consider this char as a possible match start if it part,
852 yet isn't the head, of a multibyte character. */
853 if (!sb && !re_string_first_byte (&mctx.input, 0))
857 /* It seems to be appropriate one, then use the matcher. */
858 /* We assume that the matching starts from 0. */
859 mctx.state_log_top = mctx.nbkref_ents = mctx.max_mb_elem_len = 0;
860 match_last = check_matching (&mctx, fl_longest_match,
861 start <= last_start ? &match_first : NULL);
862 if (match_last != REG_MISSING)
864 if (BE (match_last == REG_ERROR, 0))
871 mctx.match_last = match_last;
872 if ((!preg->no_sub && nmatch > 1) || dfa->nbackref)
874 re_dfastate_t *pstate = mctx.state_log[match_last];
875 mctx.last_node = check_halt_state_context (&mctx, pstate,
878 if ((!preg->no_sub && nmatch > 1 && dfa->has_plural_match)
881 err = prune_impossible_nodes (&mctx);
882 if (err == REG_NOERROR)
884 if (BE (err != REG_NOMATCH, 0))
886 match_last = REG_MISSING;
889 break; /* We found a match. */
893 match_ctx_clean (&mctx);
897 assert (match_last != REG_MISSING);
898 assert (err == REG_NOERROR);
901 /* Set pmatch[] if we need. */
906 /* Initialize registers. */
907 for (reg_idx = 1; reg_idx < nmatch; ++reg_idx)
908 pmatch[reg_idx].rm_so = pmatch[reg_idx].rm_eo = -1;
910 /* Set the points where matching start/end. */
912 pmatch[0].rm_eo = mctx.match_last;
913 /* FIXME: This function should fail if mctx.match_last exceeds
914 the maximum possible regoff_t value. We need a new error
915 code REG_OVERFLOW. */
917 if (!preg->no_sub && nmatch > 1)
919 err = set_regs (preg, &mctx, nmatch, pmatch,
920 dfa->has_plural_match && dfa->nbackref > 0);
921 if (BE (err != REG_NOERROR, 0))
925 /* At last, add the offset to the each registers, since we slided
926 the buffers so that we could assume that the matching starts
928 for (reg_idx = 0; reg_idx < nmatch; ++reg_idx)
929 if (pmatch[reg_idx].rm_so != -1)
931 #ifdef RE_ENABLE_I18N
932 if (BE (mctx.input.offsets_needed != 0, 0))
934 pmatch[reg_idx].rm_so =
935 (pmatch[reg_idx].rm_so == mctx.input.valid_len
936 ? mctx.input.valid_raw_len
937 : mctx.input.offsets[pmatch[reg_idx].rm_so]);
938 pmatch[reg_idx].rm_eo =
939 (pmatch[reg_idx].rm_eo == mctx.input.valid_len
940 ? mctx.input.valid_raw_len
941 : mctx.input.offsets[pmatch[reg_idx].rm_eo]);
944 assert (mctx.input.offsets_needed == 0);
946 pmatch[reg_idx].rm_so += match_first;
947 pmatch[reg_idx].rm_eo += match_first;
949 for (reg_idx = 0; reg_idx < extra_nmatch; ++reg_idx)
951 pmatch[nmatch + reg_idx].rm_so = -1;
952 pmatch[nmatch + reg_idx].rm_eo = -1;
956 for (reg_idx = 0; reg_idx + 1 < nmatch; reg_idx++)
957 if (dfa->subexp_map[reg_idx] != reg_idx)
959 pmatch[reg_idx + 1].rm_so
960 = pmatch[dfa->subexp_map[reg_idx] + 1].rm_so;
961 pmatch[reg_idx + 1].rm_eo
962 = pmatch[dfa->subexp_map[reg_idx] + 1].rm_eo;
967 re_free (mctx.state_log);
969 match_ctx_free (&mctx);
970 re_string_destruct (&mctx.input);
976 prune_impossible_nodes (re_match_context_t *mctx)
978 const re_dfa_t *const dfa = mctx->dfa;
979 Idx halt_node, match_last;
981 re_dfastate_t **sifted_states;
982 re_dfastate_t **lim_states = NULL;
983 re_sift_context_t sctx;
985 assert (mctx->state_log != NULL);
987 match_last = mctx->match_last;
988 halt_node = mctx->last_node;
990 /* Avoid overflow. */
991 if (BE (SIZE_MAX / sizeof (re_dfastate_t *) <= match_last, 0))
994 sifted_states = re_malloc (re_dfastate_t *, match_last + 1);
995 if (BE (sifted_states == NULL, 0))
1002 lim_states = re_malloc (re_dfastate_t *, match_last + 1);
1003 if (BE (lim_states == NULL, 0))
1010 memset (lim_states, '\0',
1011 sizeof (re_dfastate_t *) * (match_last + 1));
1012 sift_ctx_init (&sctx, sifted_states, lim_states, halt_node,
1014 ret = sift_states_backward (mctx, &sctx);
1015 re_node_set_free (&sctx.limits);
1016 if (BE (ret != REG_NOERROR, 0))
1018 if (sifted_states[0] != NULL || lim_states[0] != NULL)
1023 if (! REG_VALID_INDEX (match_last))
1028 } while (mctx->state_log[match_last] == NULL
1029 || !mctx->state_log[match_last]->halt);
1030 halt_node = check_halt_state_context (mctx,
1031 mctx->state_log[match_last],
1034 ret = merge_state_array (dfa, sifted_states, lim_states,
1036 re_free (lim_states);
1038 if (BE (ret != REG_NOERROR, 0))
1043 sift_ctx_init (&sctx, sifted_states, lim_states, halt_node, match_last);
1044 ret = sift_states_backward (mctx, &sctx);
1045 re_node_set_free (&sctx.limits);
1046 if (BE (ret != REG_NOERROR, 0))
1049 re_free (mctx->state_log);
1050 mctx->state_log = sifted_states;
1051 sifted_states = NULL;
1052 mctx->last_node = halt_node;
1053 mctx->match_last = match_last;
1056 re_free (sifted_states);
1057 re_free (lim_states);
1061 /* Acquire an initial state and return it.
1062 We must select appropriate initial state depending on the context,
1063 since initial states may have constraints like "\<", "^", etc.. */
1065 static inline re_dfastate_t *
1066 __attribute ((always_inline)) internal_function
1067 acquire_init_state_context (reg_errcode_t *err, const re_match_context_t *mctx,
1070 const re_dfa_t *const dfa = mctx->dfa;
1071 if (dfa->init_state->has_constraint)
1073 unsigned int context;
1074 context = re_string_context_at (&mctx->input, idx - 1, mctx->eflags);
1075 if (IS_WORD_CONTEXT (context))
1076 return dfa->init_state_word;
1077 else if (IS_ORDINARY_CONTEXT (context))
1078 return dfa->init_state;
1079 else if (IS_BEGBUF_CONTEXT (context) && IS_NEWLINE_CONTEXT (context))
1080 return dfa->init_state_begbuf;
1081 else if (IS_NEWLINE_CONTEXT (context))
1082 return dfa->init_state_nl;
1083 else if (IS_BEGBUF_CONTEXT (context))
1085 /* It is relatively rare case, then calculate on demand. */
1086 return re_acquire_state_context (err, dfa,
1087 dfa->init_state->entrance_nodes,
1091 /* Must not happen? */
1092 return dfa->init_state;
1095 return dfa->init_state;
1098 /* Check whether the regular expression match input string INPUT or not,
1099 and return the index where the matching end. Return REG_MISSING if
1100 there is no match, and return REG_ERROR in case of an error.
1101 FL_LONGEST_MATCH means we want the POSIX longest matching.
1102 If P_MATCH_FIRST is not NULL, and the match fails, it is set to the
1103 next place where we may want to try matching.
1104 Note that the matcher assume that the maching starts from the current
1105 index of the buffer. */
1109 check_matching (re_match_context_t *mctx, bool fl_longest_match,
1112 const re_dfa_t *const dfa = mctx->dfa;
1115 Idx match_last = REG_MISSING;
1116 Idx cur_str_idx = re_string_cur_idx (&mctx->input);
1117 re_dfastate_t *cur_state;
1118 bool at_init_state = p_match_first != NULL;
1119 Idx next_start_idx = cur_str_idx;
1122 cur_state = acquire_init_state_context (&err, mctx, cur_str_idx);
1123 /* An initial state must not be NULL (invalid). */
1124 if (BE (cur_state == NULL, 0))
1126 assert (err == REG_ESPACE);
1130 if (mctx->state_log != NULL)
1132 mctx->state_log[cur_str_idx] = cur_state;
1134 /* Check OP_OPEN_SUBEXP in the initial state in case that we use them
1135 later. E.g. Processing back references. */
1136 if (BE (dfa->nbackref, 0))
1138 at_init_state = false;
1139 err = check_subexp_matching_top (mctx, &cur_state->nodes, 0);
1140 if (BE (err != REG_NOERROR, 0))
1143 if (cur_state->has_backref)
1145 err = transit_state_bkref (mctx, &cur_state->nodes);
1146 if (BE (err != REG_NOERROR, 0))
1152 /* If the RE accepts NULL string. */
1153 if (BE (cur_state->halt, 0))
1155 if (!cur_state->has_constraint
1156 || check_halt_state_context (mctx, cur_state, cur_str_idx))
1158 if (!fl_longest_match)
1162 match_last = cur_str_idx;
1168 while (!re_string_eoi (&mctx->input))
1170 re_dfastate_t *old_state = cur_state;
1171 Idx next_char_idx = re_string_cur_idx (&mctx->input) + 1;
1173 if (BE (next_char_idx >= mctx->input.bufs_len, 0)
1174 || (BE (next_char_idx >= mctx->input.valid_len, 0)
1175 && mctx->input.valid_len < mctx->input.len))
1177 err = extend_buffers (mctx);
1178 if (BE (err != REG_NOERROR, 0))
1180 assert (err == REG_ESPACE);
1185 cur_state = transit_state (&err, mctx, cur_state);
1186 if (mctx->state_log != NULL)
1187 cur_state = merge_state_with_log (&err, mctx, cur_state);
1189 if (cur_state == NULL)
1191 /* Reached the invalid state or an error. Try to recover a valid
1192 state using the state log, if available and if we have not
1193 already found a valid (even if not the longest) match. */
1194 if (BE (err != REG_NOERROR, 0))
1197 if (mctx->state_log == NULL
1198 || (match && !fl_longest_match)
1199 || (cur_state = find_recover_state (&err, mctx)) == NULL)
1203 if (BE (at_init_state, 0))
1205 if (old_state == cur_state)
1206 next_start_idx = next_char_idx;
1208 at_init_state = false;
1211 if (cur_state->halt)
1213 /* Reached a halt state.
1214 Check the halt state can satisfy the current context. */
1215 if (!cur_state->has_constraint
1216 || check_halt_state_context (mctx, cur_state,
1217 re_string_cur_idx (&mctx->input)))
1219 /* We found an appropriate halt state. */
1220 match_last = re_string_cur_idx (&mctx->input);
1223 /* We found a match, do not modify match_first below. */
1224 p_match_first = NULL;
1225 if (!fl_longest_match)
1232 *p_match_first += next_start_idx;
1237 /* Check NODE match the current context. */
1241 check_halt_node_context (const re_dfa_t *dfa, Idx node, unsigned int context)
1243 re_token_type_t type = dfa->nodes[node].type;
1244 unsigned int constraint = dfa->nodes[node].constraint;
1245 if (type != END_OF_RE)
1249 if (NOT_SATISFY_NEXT_CONSTRAINT (constraint, context))
1254 /* Check the halt state STATE match the current context.
1255 Return 0 if not match, if the node, STATE has, is a halt node and
1256 match the context, return the node. */
1260 check_halt_state_context (const re_match_context_t *mctx,
1261 const re_dfastate_t *state, Idx idx)
1264 unsigned int context;
1266 assert (state->halt);
1268 context = re_string_context_at (&mctx->input, idx, mctx->eflags);
1269 for (i = 0; i < state->nodes.nelem; ++i)
1270 if (check_halt_node_context (mctx->dfa, state->nodes.elems[i], context))
1271 return state->nodes.elems[i];
1275 /* Compute the next node to which "NFA" transit from NODE("NFA" is a NFA
1276 corresponding to the DFA).
1277 Return the destination node, and update EPS_VIA_NODES;
1278 return REG_MISSING in case of errors. */
1282 proceed_next_node (const re_match_context_t *mctx, Idx nregs, regmatch_t *regs,
1283 Idx *pidx, Idx node, re_node_set *eps_via_nodes,
1284 struct re_fail_stack_t *fs)
1286 const re_dfa_t *const dfa = mctx->dfa;
1289 if (IS_EPSILON_NODE (dfa->nodes[node].type))
1291 re_node_set *cur_nodes = &mctx->state_log[*pidx]->nodes;
1292 re_node_set *edests = &dfa->edests[node];
1294 ok = re_node_set_insert (eps_via_nodes, node);
1297 /* Pick up a valid destination, or return REG_MISSING if none
1299 for (dest_node = REG_MISSING, i = 0; i < edests->nelem; ++i)
1301 Idx candidate = edests->elems[i];
1302 if (!re_node_set_contains (cur_nodes, candidate))
1304 if (dest_node == REG_MISSING)
1305 dest_node = candidate;
1309 /* In order to avoid infinite loop like "(a*)*", return the second
1310 epsilon-transition if the first was already considered. */
1311 if (re_node_set_contains (eps_via_nodes, dest_node))
1314 /* Otherwise, push the second epsilon-transition on the fail stack. */
1316 && push_fail_stack (fs, *pidx, candidate, nregs, regs,
1320 /* We know we are going to exit. */
1329 re_token_type_t type = dfa->nodes[node].type;
1331 #ifdef RE_ENABLE_I18N
1332 if (dfa->nodes[node].accept_mb)
1333 naccepted = check_node_accept_bytes (dfa, node, &mctx->input, *pidx);
1335 #endif /* RE_ENABLE_I18N */
1336 if (type == OP_BACK_REF)
1338 Idx subexp_idx = dfa->nodes[node].opr.idx + 1;
1339 naccepted = regs[subexp_idx].rm_eo - regs[subexp_idx].rm_so;
1342 if (regs[subexp_idx].rm_so == -1 || regs[subexp_idx].rm_eo == -1)
1346 char *buf = (char *) re_string_get_buffer (&mctx->input);
1347 if (memcmp (buf + regs[subexp_idx].rm_so, buf + *pidx,
1356 ok = re_node_set_insert (eps_via_nodes, node);
1359 dest_node = dfa->edests[node].elems[0];
1360 if (re_node_set_contains (&mctx->state_log[*pidx]->nodes,
1367 || check_node_accept (mctx, dfa->nodes + node, *pidx))
1369 Idx dest_node = dfa->nexts[node];
1370 *pidx = (naccepted == 0) ? *pidx + 1 : *pidx + naccepted;
1371 if (fs && (*pidx > mctx->match_last || mctx->state_log[*pidx] == NULL
1372 || !re_node_set_contains (&mctx->state_log[*pidx]->nodes,
1375 re_node_set_empty (eps_via_nodes);
1382 static reg_errcode_t
1384 push_fail_stack (struct re_fail_stack_t *fs, Idx str_idx, Idx dest_node,
1385 Idx nregs, regmatch_t *regs, re_node_set *eps_via_nodes)
1388 Idx num = fs->num++;
1389 if (fs->num == fs->alloc)
1391 struct re_fail_stack_ent_t *new_array;
1392 new_array = realloc (fs->stack, (sizeof (struct re_fail_stack_ent_t)
1394 if (new_array == NULL)
1397 fs->stack = new_array;
1399 fs->stack[num].idx = str_idx;
1400 fs->stack[num].node = dest_node;
1401 fs->stack[num].regs = re_malloc (regmatch_t, nregs);
1402 if (fs->stack[num].regs == NULL)
1404 memcpy (fs->stack[num].regs, regs, sizeof (regmatch_t) * nregs);
1405 err = re_node_set_init_copy (&fs->stack[num].eps_via_nodes, eps_via_nodes);
1411 pop_fail_stack (struct re_fail_stack_t *fs, Idx *pidx, Idx nregs,
1412 regmatch_t *regs, re_node_set *eps_via_nodes)
1414 Idx num = --fs->num;
1415 assert (REG_VALID_INDEX (num));
1416 *pidx = fs->stack[num].idx;
1417 memcpy (regs, fs->stack[num].regs, sizeof (regmatch_t) * nregs);
1418 re_node_set_free (eps_via_nodes);
1419 re_free (fs->stack[num].regs);
1420 *eps_via_nodes = fs->stack[num].eps_via_nodes;
1421 return fs->stack[num].node;
1424 /* Set the positions where the subexpressions are starts/ends to registers
1426 Note: We assume that pmatch[0] is already set, and
1427 pmatch[i].rm_so == pmatch[i].rm_eo == -1 for 0 < i < nmatch. */
1429 static reg_errcode_t
1431 set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
1432 regmatch_t *pmatch, bool fl_backtrack)
1434 const re_dfa_t *dfa = (const re_dfa_t *) preg->buffer;
1436 re_node_set eps_via_nodes;
1437 struct re_fail_stack_t *fs;
1438 struct re_fail_stack_t fs_body = { 0, 2, NULL };
1439 regmatch_t *prev_idx_match;
1440 bool prev_idx_match_malloced = false;
1443 assert (nmatch > 1);
1444 assert (mctx->state_log != NULL);
1449 fs->stack = re_malloc (struct re_fail_stack_ent_t, fs->alloc);
1450 if (fs->stack == NULL)
1456 cur_node = dfa->init_node;
1457 re_node_set_init_empty (&eps_via_nodes);
1459 if (__libc_use_alloca (nmatch * sizeof (regmatch_t)))
1460 prev_idx_match = (regmatch_t *) alloca (nmatch * sizeof (regmatch_t));
1463 prev_idx_match = re_malloc (regmatch_t, nmatch);
1464 if (prev_idx_match == NULL)
1466 free_fail_stack_return (fs);
1469 prev_idx_match_malloced = true;
1471 memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
1473 for (idx = pmatch[0].rm_so; idx <= pmatch[0].rm_eo ;)
1475 update_regs (dfa, pmatch, prev_idx_match, cur_node, idx, nmatch);
1477 if (idx == pmatch[0].rm_eo && cur_node == mctx->last_node)
1482 for (reg_idx = 0; reg_idx < nmatch; ++reg_idx)
1483 if (pmatch[reg_idx].rm_so > -1 && pmatch[reg_idx].rm_eo == -1)
1485 if (reg_idx == nmatch)
1487 re_node_set_free (&eps_via_nodes);
1488 if (prev_idx_match_malloced)
1489 re_free (prev_idx_match);
1490 return free_fail_stack_return (fs);
1492 cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
1497 re_node_set_free (&eps_via_nodes);
1498 if (prev_idx_match_malloced)
1499 re_free (prev_idx_match);
1504 /* Proceed to next node. */
1505 cur_node = proceed_next_node (mctx, nmatch, pmatch, &idx, cur_node,
1506 &eps_via_nodes, fs);
1508 if (BE (! REG_VALID_INDEX (cur_node), 0))
1510 if (BE (cur_node == REG_ERROR, 0))
1512 re_node_set_free (&eps_via_nodes);
1513 if (prev_idx_match_malloced)
1514 re_free (prev_idx_match);
1515 free_fail_stack_return (fs);
1519 cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
1523 re_node_set_free (&eps_via_nodes);
1524 if (prev_idx_match_malloced)
1525 re_free (prev_idx_match);
1530 re_node_set_free (&eps_via_nodes);
1531 if (prev_idx_match_malloced)
1532 re_free (prev_idx_match);
1533 return free_fail_stack_return (fs);
1536 static reg_errcode_t
1538 free_fail_stack_return (struct re_fail_stack_t *fs)
1543 for (fs_idx = 0; fs_idx < fs->num; ++fs_idx)
1545 re_node_set_free (&fs->stack[fs_idx].eps_via_nodes);
1546 re_free (fs->stack[fs_idx].regs);
1548 re_free (fs->stack);
1555 update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
1556 regmatch_t *prev_idx_match, Idx cur_node, Idx cur_idx, Idx nmatch)
1558 int type = dfa->nodes[cur_node].type;
1559 if (type == OP_OPEN_SUBEXP)
1561 Idx reg_num = dfa->nodes[cur_node].opr.idx + 1;
1563 /* We are at the first node of this sub expression. */
1564 if (reg_num < nmatch)
1566 pmatch[reg_num].rm_so = cur_idx;
1567 pmatch[reg_num].rm_eo = -1;
1570 else if (type == OP_CLOSE_SUBEXP)
1572 Idx reg_num = dfa->nodes[cur_node].opr.idx + 1;
1573 if (reg_num < nmatch)
1575 /* We are at the last node of this sub expression. */
1576 if (pmatch[reg_num].rm_so < cur_idx)
1578 pmatch[reg_num].rm_eo = cur_idx;
1579 /* This is a non-empty match or we are not inside an optional
1580 subexpression. Accept this right away. */
1581 memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
1585 if (dfa->nodes[cur_node].opt_subexp
1586 && prev_idx_match[reg_num].rm_so != -1)
1587 /* We transited through an empty match for an optional
1588 subexpression, like (a?)*, and this is not the subexp's
1589 first match. Copy back the old content of the registers
1590 so that matches of an inner subexpression are undone as
1591 well, like in ((a?))*. */
1592 memcpy (pmatch, prev_idx_match, sizeof (regmatch_t) * nmatch);
1594 /* We completed a subexpression, but it may be part of
1595 an optional one, so do not update PREV_IDX_MATCH. */
1596 pmatch[reg_num].rm_eo = cur_idx;
1602 /* This function checks the STATE_LOG from the SCTX->last_str_idx to 0
1603 and sift the nodes in each states according to the following rules.
1604 Updated state_log will be wrote to STATE_LOG.
1606 Rules: We throw away the Node `a' in the STATE_LOG[STR_IDX] if...
1607 1. When STR_IDX == MATCH_LAST(the last index in the state_log):
1608 If `a' isn't the LAST_NODE and `a' can't epsilon transit to
1609 the LAST_NODE, we throw away the node `a'.
1610 2. When 0 <= STR_IDX < MATCH_LAST and `a' accepts
1611 string `s' and transit to `b':
1612 i. If 'b' isn't in the STATE_LOG[STR_IDX+strlen('s')], we throw
1614 ii. If 'b' is in the STATE_LOG[STR_IDX+strlen('s')] but 'b' is
1615 thrown away, we throw away the node `a'.
1616 3. When 0 <= STR_IDX < MATCH_LAST and 'a' epsilon transit to 'b':
1617 i. If 'b' isn't in the STATE_LOG[STR_IDX], we throw away the
1619 ii. If 'b' is in the STATE_LOG[STR_IDX] but 'b' is thrown away,
1620 we throw away the node `a'. */
1622 #define STATE_NODE_CONTAINS(state,node) \
1623 ((state) != NULL && re_node_set_contains (&(state)->nodes, node))
1625 static reg_errcode_t
1627 sift_states_backward (const re_match_context_t *mctx, re_sift_context_t *sctx)
1631 Idx str_idx = sctx->last_str_idx;
1632 re_node_set cur_dest;
1635 assert (mctx->state_log != NULL && mctx->state_log[str_idx] != NULL);
1638 /* Build sifted state_log[str_idx]. It has the nodes which can epsilon
1639 transit to the last_node and the last_node itself. */
1640 err = re_node_set_init_1 (&cur_dest, sctx->last_node);
1641 if (BE (err != REG_NOERROR, 0))
1643 err = update_cur_sifted_state (mctx, sctx, str_idx, &cur_dest);
1644 if (BE (err != REG_NOERROR, 0))
1647 /* Then check each states in the state_log. */
1650 /* Update counters. */
1651 null_cnt = (sctx->sifted_states[str_idx] == NULL) ? null_cnt + 1 : 0;
1652 if (null_cnt > mctx->max_mb_elem_len)
1654 memset (sctx->sifted_states, '\0',
1655 sizeof (re_dfastate_t *) * str_idx);
1656 re_node_set_free (&cur_dest);
1659 re_node_set_empty (&cur_dest);
1662 if (mctx->state_log[str_idx])
1664 err = build_sifted_states (mctx, sctx, str_idx, &cur_dest);
1665 if (BE (err != REG_NOERROR, 0))
1669 /* Add all the nodes which satisfy the following conditions:
1670 - It can epsilon transit to a node in CUR_DEST.
1672 And update state_log. */
1673 err = update_cur_sifted_state (mctx, sctx, str_idx, &cur_dest);
1674 if (BE (err != REG_NOERROR, 0))
1679 re_node_set_free (&cur_dest);
1683 static reg_errcode_t
1685 build_sifted_states (const re_match_context_t *mctx, re_sift_context_t *sctx,
1686 Idx str_idx, re_node_set *cur_dest)
1688 const re_dfa_t *const dfa = mctx->dfa;
1689 const re_node_set *cur_src = &mctx->state_log[str_idx]->non_eps_nodes;
1692 /* Then build the next sifted state.
1693 We build the next sifted state on `cur_dest', and update
1694 `sifted_states[str_idx]' with `cur_dest'.
1696 `cur_dest' is the sifted state from `state_log[str_idx + 1]'.
1697 `cur_src' points the node_set of the old `state_log[str_idx]'
1698 (with the epsilon nodes pre-filtered out). */
1699 for (i = 0; i < cur_src->nelem; i++)
1701 Idx prev_node = cur_src->elems[i];
1706 re_token_type_t type = dfa->nodes[prev_node].type;
1707 assert (!IS_EPSILON_NODE (type));
1709 #ifdef RE_ENABLE_I18N
1710 /* If the node may accept `multi byte'. */
1711 if (dfa->nodes[prev_node].accept_mb)
1712 naccepted = sift_states_iter_mb (mctx, sctx, prev_node,
1713 str_idx, sctx->last_str_idx);
1714 #endif /* RE_ENABLE_I18N */
1716 /* We don't check backreferences here.
1717 See update_cur_sifted_state(). */
1719 && check_node_accept (mctx, dfa->nodes + prev_node, str_idx)
1720 && STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + 1],
1721 dfa->nexts[prev_node]))
1727 if (sctx->limits.nelem)
1729 Idx to_idx = str_idx + naccepted;
1730 if (check_dst_limits (mctx, &sctx->limits,
1731 dfa->nexts[prev_node], to_idx,
1732 prev_node, str_idx))
1735 ok = re_node_set_insert (cur_dest, prev_node);
1743 /* Helper functions. */
1745 static reg_errcode_t
1747 clean_state_log_if_needed (re_match_context_t *mctx, Idx next_state_log_idx)
1749 Idx top = mctx->state_log_top;
1751 if (next_state_log_idx >= mctx->input.bufs_len
1752 || (next_state_log_idx >= mctx->input.valid_len
1753 && mctx->input.valid_len < mctx->input.len))
1756 err = extend_buffers (mctx);
1757 if (BE (err != REG_NOERROR, 0))
1761 if (top < next_state_log_idx)
1763 memset (mctx->state_log + top + 1, '\0',
1764 sizeof (re_dfastate_t *) * (next_state_log_idx - top));
1765 mctx->state_log_top = next_state_log_idx;
1770 static reg_errcode_t
1772 merge_state_array (const re_dfa_t *dfa, re_dfastate_t **dst,
1773 re_dfastate_t **src, Idx num)
1777 for (st_idx = 0; st_idx < num; ++st_idx)
1779 if (dst[st_idx] == NULL)
1780 dst[st_idx] = src[st_idx];
1781 else if (src[st_idx] != NULL)
1783 re_node_set merged_set;
1784 err = re_node_set_init_union (&merged_set, &dst[st_idx]->nodes,
1785 &src[st_idx]->nodes);
1786 if (BE (err != REG_NOERROR, 0))
1788 dst[st_idx] = re_acquire_state (&err, dfa, &merged_set);
1789 re_node_set_free (&merged_set);
1790 if (BE (err != REG_NOERROR, 0))
1797 static reg_errcode_t
1799 update_cur_sifted_state (const re_match_context_t *mctx,
1800 re_sift_context_t *sctx, Idx str_idx,
1801 re_node_set *dest_nodes)
1803 const re_dfa_t *const dfa = mctx->dfa;
1804 reg_errcode_t err = REG_NOERROR;
1805 const re_node_set *candidates;
1806 candidates = ((mctx->state_log[str_idx] == NULL) ? NULL
1807 : &mctx->state_log[str_idx]->nodes);
1809 if (dest_nodes->nelem == 0)
1810 sctx->sifted_states[str_idx] = NULL;
1815 /* At first, add the nodes which can epsilon transit to a node in
1817 err = add_epsilon_src_nodes (dfa, dest_nodes, candidates);
1818 if (BE (err != REG_NOERROR, 0))
1821 /* Then, check the limitations in the current sift_context. */
1822 if (sctx->limits.nelem)
1824 err = check_subexp_limits (dfa, dest_nodes, candidates, &sctx->limits,
1825 mctx->bkref_ents, str_idx);
1826 if (BE (err != REG_NOERROR, 0))
1831 sctx->sifted_states[str_idx] = re_acquire_state (&err, dfa, dest_nodes);
1832 if (BE (err != REG_NOERROR, 0))
1836 if (candidates && mctx->state_log[str_idx]->has_backref)
1838 err = sift_states_bkref (mctx, sctx, str_idx, candidates);
1839 if (BE (err != REG_NOERROR, 0))
1845 static reg_errcode_t
1847 add_epsilon_src_nodes (const re_dfa_t *dfa, re_node_set *dest_nodes,
1848 const re_node_set *candidates)
1850 reg_errcode_t err = REG_NOERROR;
1853 re_dfastate_t *state = re_acquire_state (&err, dfa, dest_nodes);
1854 if (BE (err != REG_NOERROR, 0))
1857 if (!state->inveclosure.alloc)
1859 err = re_node_set_alloc (&state->inveclosure, dest_nodes->nelem);
1860 if (BE (err != REG_NOERROR, 0))
1862 for (i = 0; i < dest_nodes->nelem; i++)
1863 re_node_set_merge (&state->inveclosure,
1864 dfa->inveclosures + dest_nodes->elems[i]);
1866 return re_node_set_add_intersect (dest_nodes, candidates,
1867 &state->inveclosure);
1870 static reg_errcode_t
1872 sub_epsilon_src_nodes (const re_dfa_t *dfa, Idx node, re_node_set *dest_nodes,
1873 const re_node_set *candidates)
1877 re_node_set *inv_eclosure = dfa->inveclosures + node;
1878 re_node_set except_nodes;
1879 re_node_set_init_empty (&except_nodes);
1880 for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx)
1882 Idx cur_node = inv_eclosure->elems[ecl_idx];
1883 if (cur_node == node)
1885 if (IS_EPSILON_NODE (dfa->nodes[cur_node].type))
1887 Idx edst1 = dfa->edests[cur_node].elems[0];
1888 Idx edst2 = ((dfa->edests[cur_node].nelem > 1)
1889 ? dfa->edests[cur_node].elems[1] : REG_MISSING);
1890 if ((!re_node_set_contains (inv_eclosure, edst1)
1891 && re_node_set_contains (dest_nodes, edst1))
1892 || (REG_VALID_NONZERO_INDEX (edst2)
1893 && !re_node_set_contains (inv_eclosure, edst2)
1894 && re_node_set_contains (dest_nodes, edst2)))
1896 err = re_node_set_add_intersect (&except_nodes, candidates,
1897 dfa->inveclosures + cur_node);
1898 if (BE (err != REG_NOERROR, 0))
1900 re_node_set_free (&except_nodes);
1906 for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx)
1908 Idx cur_node = inv_eclosure->elems[ecl_idx];
1909 if (!re_node_set_contains (&except_nodes, cur_node))
1911 Idx idx = re_node_set_contains (dest_nodes, cur_node) - 1;
1912 re_node_set_remove_at (dest_nodes, idx);
1915 re_node_set_free (&except_nodes);
1921 check_dst_limits (const re_match_context_t *mctx, const re_node_set *limits,
1922 Idx dst_node, Idx dst_idx, Idx src_node, Idx src_idx)
1924 const re_dfa_t *const dfa = mctx->dfa;
1925 Idx lim_idx, src_pos, dst_pos;
1927 Idx dst_bkref_idx = search_cur_bkref_entry (mctx, dst_idx);
1928 Idx src_bkref_idx = search_cur_bkref_entry (mctx, src_idx);
1929 for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx)
1932 struct re_backref_cache_entry *ent;
1933 ent = mctx->bkref_ents + limits->elems[lim_idx];
1934 subexp_idx = dfa->nodes[ent->node].opr.idx;
1936 dst_pos = check_dst_limits_calc_pos (mctx, limits->elems[lim_idx],
1937 subexp_idx, dst_node, dst_idx,
1939 src_pos = check_dst_limits_calc_pos (mctx, limits->elems[lim_idx],
1940 subexp_idx, src_node, src_idx,
1944 <src> <dst> ( <subexp> )
1945 ( <subexp> ) <src> <dst>
1946 ( <subexp1> <src> <subexp2> <dst> <subexp3> ) */
1947 if (src_pos == dst_pos)
1948 continue; /* This is unrelated limitation. */
1957 check_dst_limits_calc_pos_1 (const re_match_context_t *mctx, int boundaries,
1958 Idx subexp_idx, Idx from_node, Idx bkref_idx)
1960 const re_dfa_t *const dfa = mctx->dfa;
1961 const re_node_set *eclosures = dfa->eclosures + from_node;
1964 /* Else, we are on the boundary: examine the nodes on the epsilon
1966 for (node_idx = 0; node_idx < eclosures->nelem; ++node_idx)
1968 Idx node = eclosures->elems[node_idx];
1969 switch (dfa->nodes[node].type)
1972 if (bkref_idx != REG_MISSING)
1974 struct re_backref_cache_entry *ent = mctx->bkref_ents + bkref_idx;
1980 if (ent->node != node)
1983 if (subexp_idx < BITSET_WORD_BITS
1984 && !(ent->eps_reachable_subexps_map
1985 & ((bitset_word_t) 1 << subexp_idx)))
1988 /* Recurse trying to reach the OP_OPEN_SUBEXP and
1989 OP_CLOSE_SUBEXP cases below. But, if the
1990 destination node is the same node as the source
1991 node, don't recurse because it would cause an
1992 infinite loop: a regex that exhibits this behavior
1994 dst = dfa->edests[node].elems[0];
1995 if (dst == from_node)
1999 else /* if (boundaries & 2) */
2004 check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx,
2006 if (cpos == -1 /* && (boundaries & 1) */)
2008 if (cpos == 0 && (boundaries & 2))
2011 if (subexp_idx < BITSET_WORD_BITS)
2012 ent->eps_reachable_subexps_map
2013 &= ~((bitset_word_t) 1 << subexp_idx);
2015 while (ent++->more);
2019 case OP_OPEN_SUBEXP:
2020 if ((boundaries & 1) && subexp_idx == dfa->nodes[node].opr.idx)
2024 case OP_CLOSE_SUBEXP:
2025 if ((boundaries & 2) && subexp_idx == dfa->nodes[node].opr.idx)
2034 return (boundaries & 2) ? 1 : 0;
2039 check_dst_limits_calc_pos (const re_match_context_t *mctx, Idx limit,
2040 Idx subexp_idx, Idx from_node, Idx str_idx,
2043 struct re_backref_cache_entry *lim = mctx->bkref_ents + limit;
2046 /* If we are outside the range of the subexpression, return -1 or 1. */
2047 if (str_idx < lim->subexp_from)
2050 if (lim->subexp_to < str_idx)
2053 /* If we are within the subexpression, return 0. */
2054 boundaries = (str_idx == lim->subexp_from);
2055 boundaries |= (str_idx == lim->subexp_to) << 1;
2056 if (boundaries == 0)
2059 /* Else, examine epsilon closure. */
2060 return check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx,
2061 from_node, bkref_idx);
2064 /* Check the limitations of sub expressions LIMITS, and remove the nodes
2065 which are against limitations from DEST_NODES. */
2067 static reg_errcode_t
2069 check_subexp_limits (const re_dfa_t *dfa, re_node_set *dest_nodes,
2070 const re_node_set *candidates, re_node_set *limits,
2071 struct re_backref_cache_entry *bkref_ents, Idx str_idx)
2074 Idx node_idx, lim_idx;
2076 for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx)
2079 struct re_backref_cache_entry *ent;
2080 ent = bkref_ents + limits->elems[lim_idx];
2082 if (str_idx <= ent->subexp_from || ent->str_idx < str_idx)
2083 continue; /* This is unrelated limitation. */
2085 subexp_idx = dfa->nodes[ent->node].opr.idx;
2086 if (ent->subexp_to == str_idx)
2088 Idx ops_node = REG_MISSING;
2089 Idx cls_node = REG_MISSING;
2090 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2092 Idx node = dest_nodes->elems[node_idx];
2093 re_token_type_t type = dfa->nodes[node].type;
2094 if (type == OP_OPEN_SUBEXP
2095 && subexp_idx == dfa->nodes[node].opr.idx)
2097 else if (type == OP_CLOSE_SUBEXP
2098 && subexp_idx == dfa->nodes[node].opr.idx)
2102 /* Check the limitation of the open subexpression. */
2103 /* Note that (ent->subexp_to = str_idx != ent->subexp_from). */
2104 if (REG_VALID_INDEX (ops_node))
2106 err = sub_epsilon_src_nodes (dfa, ops_node, dest_nodes,
2108 if (BE (err != REG_NOERROR, 0))
2112 /* Check the limitation of the close subexpression. */
2113 if (REG_VALID_INDEX (cls_node))
2114 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2116 Idx node = dest_nodes->elems[node_idx];
2117 if (!re_node_set_contains (dfa->inveclosures + node,
2119 && !re_node_set_contains (dfa->eclosures + node,
2122 /* It is against this limitation.
2123 Remove it form the current sifted state. */
2124 err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2126 if (BE (err != REG_NOERROR, 0))
2132 else /* (ent->subexp_to != str_idx) */
2134 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2136 Idx node = dest_nodes->elems[node_idx];
2137 re_token_type_t type = dfa->nodes[node].type;
2138 if (type == OP_CLOSE_SUBEXP || type == OP_OPEN_SUBEXP)
2140 if (subexp_idx != dfa->nodes[node].opr.idx)
2142 /* It is against this limitation.
2143 Remove it form the current sifted state. */
2144 err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2146 if (BE (err != REG_NOERROR, 0))
2155 static reg_errcode_t
2157 sift_states_bkref (const re_match_context_t *mctx, re_sift_context_t *sctx,
2158 Idx str_idx, const re_node_set *candidates)
2160 const re_dfa_t *const dfa = mctx->dfa;
2163 re_sift_context_t local_sctx;
2164 Idx first_idx = search_cur_bkref_entry (mctx, str_idx);
2166 if (first_idx == REG_MISSING)
2169 local_sctx.sifted_states = NULL; /* Mark that it hasn't been initialized. */
2171 for (node_idx = 0; node_idx < candidates->nelem; ++node_idx)
2174 re_token_type_t type;
2175 struct re_backref_cache_entry *entry;
2176 node = candidates->elems[node_idx];
2177 type = dfa->nodes[node].type;
2178 /* Avoid infinite loop for the REs like "()\1+". */
2179 if (node == sctx->last_node && str_idx == sctx->last_str_idx)
2181 if (type != OP_BACK_REF)
2184 entry = mctx->bkref_ents + first_idx;
2185 enabled_idx = first_idx;
2192 re_dfastate_t *cur_state;
2194 if (entry->node != node)
2196 subexp_len = entry->subexp_to - entry->subexp_from;
2197 to_idx = str_idx + subexp_len;
2198 dst_node = (subexp_len ? dfa->nexts[node]
2199 : dfa->edests[node].elems[0]);
2201 if (to_idx > sctx->last_str_idx
2202 || sctx->sifted_states[to_idx] == NULL
2203 || !STATE_NODE_CONTAINS (sctx->sifted_states[to_idx], dst_node)
2204 || check_dst_limits (mctx, &sctx->limits, node,
2205 str_idx, dst_node, to_idx))
2208 if (local_sctx.sifted_states == NULL)
2211 err = re_node_set_init_copy (&local_sctx.limits, &sctx->limits);
2212 if (BE (err != REG_NOERROR, 0))
2215 local_sctx.last_node = node;
2216 local_sctx.last_str_idx = str_idx;
2217 ok = re_node_set_insert (&local_sctx.limits, enabled_idx);
2223 cur_state = local_sctx.sifted_states[str_idx];
2224 err = sift_states_backward (mctx, &local_sctx);
2225 if (BE (err != REG_NOERROR, 0))
2227 if (sctx->limited_states != NULL)
2229 err = merge_state_array (dfa, sctx->limited_states,
2230 local_sctx.sifted_states,
2232 if (BE (err != REG_NOERROR, 0))
2235 local_sctx.sifted_states[str_idx] = cur_state;
2236 re_node_set_remove (&local_sctx.limits, enabled_idx);
2238 /* mctx->bkref_ents may have changed, reload the pointer. */
2239 entry = mctx->bkref_ents + enabled_idx;
2241 while (enabled_idx++, entry++->more);
2245 if (local_sctx.sifted_states != NULL)
2247 re_node_set_free (&local_sctx.limits);
2254 #ifdef RE_ENABLE_I18N
2257 sift_states_iter_mb (const re_match_context_t *mctx, re_sift_context_t *sctx,
2258 Idx node_idx, Idx str_idx, Idx max_str_idx)
2260 const re_dfa_t *const dfa = mctx->dfa;
2262 /* Check the node can accept `multi byte'. */
2263 naccepted = check_node_accept_bytes (dfa, node_idx, &mctx->input, str_idx);
2264 if (naccepted > 0 && str_idx + naccepted <= max_str_idx &&
2265 !STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + naccepted],
2266 dfa->nexts[node_idx]))
2267 /* The node can't accept the `multi byte', or the
2268 destination was already thrown away, then the node
2269 could't accept the current input `multi byte'. */
2271 /* Otherwise, it is sure that the node could accept
2272 `naccepted' bytes input. */
2275 #endif /* RE_ENABLE_I18N */
2278 /* Functions for state transition. */
2280 /* Return the next state to which the current state STATE will transit by
2281 accepting the current input byte, and update STATE_LOG if necessary.
2282 If STATE can accept a multibyte char/collating element/back reference
2283 update the destination of STATE_LOG. */
2285 static re_dfastate_t *
2287 transit_state (reg_errcode_t *err, re_match_context_t *mctx,
2288 re_dfastate_t *state)
2290 re_dfastate_t **trtable;
2293 #ifdef RE_ENABLE_I18N
2294 /* If the current state can accept multibyte. */
2295 if (BE (state->accept_mb, 0))
2297 *err = transit_state_mb (mctx, state);
2298 if (BE (*err != REG_NOERROR, 0))
2301 #endif /* RE_ENABLE_I18N */
2303 /* Then decide the next state with the single byte. */
2306 /* don't use transition table */
2307 return transit_state_sb (err, mctx, state);
2310 /* Use transition table */
2311 ch = re_string_fetch_byte (&mctx->input);
2314 trtable = state->trtable;
2315 if (BE (trtable != NULL, 1))
2318 trtable = state->word_trtable;
2319 if (BE (trtable != NULL, 1))
2321 unsigned int context;
2323 = re_string_context_at (&mctx->input,
2324 re_string_cur_idx (&mctx->input) - 1,
2326 if (IS_WORD_CONTEXT (context))
2327 return trtable[ch + SBC_MAX];
2332 if (!build_trtable (mctx->dfa, state))
2338 /* Retry, we now have a transition table. */
2342 /* Update the state_log if we need */
2343 static re_dfastate_t *
2345 merge_state_with_log (reg_errcode_t *err, re_match_context_t *mctx,
2346 re_dfastate_t *next_state)
2348 const re_dfa_t *const dfa = mctx->dfa;
2349 Idx cur_idx = re_string_cur_idx (&mctx->input);
2351 if (cur_idx > mctx->state_log_top)
2353 mctx->state_log[cur_idx] = next_state;
2354 mctx->state_log_top = cur_idx;
2356 else if (mctx->state_log[cur_idx] == 0)
2358 mctx->state_log[cur_idx] = next_state;
2362 re_dfastate_t *pstate;
2363 unsigned int context;
2364 re_node_set next_nodes, *log_nodes, *table_nodes = NULL;
2365 /* If (state_log[cur_idx] != 0), it implies that cur_idx is
2366 the destination of a multibyte char/collating element/
2367 back reference. Then the next state is the union set of
2368 these destinations and the results of the transition table. */
2369 pstate = mctx->state_log[cur_idx];
2370 log_nodes = pstate->entrance_nodes;
2371 if (next_state != NULL)
2373 table_nodes = next_state->entrance_nodes;
2374 *err = re_node_set_init_union (&next_nodes, table_nodes,
2376 if (BE (*err != REG_NOERROR, 0))
2380 next_nodes = *log_nodes;
2381 /* Note: We already add the nodes of the initial state,
2382 then we don't need to add them here. */
2384 context = re_string_context_at (&mctx->input,
2385 re_string_cur_idx (&mctx->input) - 1,
2387 next_state = mctx->state_log[cur_idx]
2388 = re_acquire_state_context (err, dfa, &next_nodes, context);
2389 /* We don't need to check errors here, since the return value of
2390 this function is next_state and ERR is already set. */
2392 if (table_nodes != NULL)
2393 re_node_set_free (&next_nodes);
2396 if (BE (dfa->nbackref, 0) && next_state != NULL)
2398 /* Check OP_OPEN_SUBEXP in the current state in case that we use them
2399 later. We must check them here, since the back references in the
2400 next state might use them. */
2401 *err = check_subexp_matching_top (mctx, &next_state->nodes,
2403 if (BE (*err != REG_NOERROR, 0))
2406 /* If the next state has back references. */
2407 if (next_state->has_backref)
2409 *err = transit_state_bkref (mctx, &next_state->nodes);
2410 if (BE (*err != REG_NOERROR, 0))
2412 next_state = mctx->state_log[cur_idx];
2419 /* Skip bytes in the input that correspond to part of a
2420 multi-byte match, then look in the log for a state
2421 from which to restart matching. */
2422 static re_dfastate_t *
2424 find_recover_state (reg_errcode_t *err, re_match_context_t *mctx)
2426 re_dfastate_t *cur_state;
2429 Idx max = mctx->state_log_top;
2430 Idx cur_str_idx = re_string_cur_idx (&mctx->input);
2434 if (++cur_str_idx > max)
2436 re_string_skip_bytes (&mctx->input, 1);
2438 while (mctx->state_log[cur_str_idx] == NULL);
2440 cur_state = merge_state_with_log (err, mctx, NULL);
2442 while (*err == REG_NOERROR && cur_state == NULL);
2446 /* Helper functions for transit_state. */
2448 /* From the node set CUR_NODES, pick up the nodes whose types are
2449 OP_OPEN_SUBEXP and which have corresponding back references in the regular
2450 expression. And register them to use them later for evaluating the
2451 correspoding back references. */
2453 static reg_errcode_t
2455 check_subexp_matching_top (re_match_context_t *mctx, re_node_set *cur_nodes,
2458 const re_dfa_t *const dfa = mctx->dfa;
2462 /* TODO: This isn't efficient.
2463 Because there might be more than one nodes whose types are
2464 OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
2467 for (node_idx = 0; node_idx < cur_nodes->nelem; ++node_idx)
2469 Idx node = cur_nodes->elems[node_idx];
2470 if (dfa->nodes[node].type == OP_OPEN_SUBEXP
2471 && dfa->nodes[node].opr.idx < BITSET_WORD_BITS
2472 && (dfa->used_bkref_map
2473 & ((bitset_word_t) 1 << dfa->nodes[node].opr.idx)))
2475 err = match_ctx_add_subtop (mctx, node, str_idx);
2476 if (BE (err != REG_NOERROR, 0))
2484 /* Return the next state to which the current state STATE will transit by
2485 accepting the current input byte. */
2487 static re_dfastate_t *
2488 transit_state_sb (reg_errcode_t *err, re_match_context_t *mctx,
2489 re_dfastate_t *state)
2491 const re_dfa_t *const dfa = mctx->dfa;
2492 re_node_set next_nodes;
2493 re_dfastate_t *next_state;
2494 Idx node_cnt, cur_str_idx = re_string_cur_idx (&mctx->input);
2495 unsigned int context;
2497 *err = re_node_set_alloc (&next_nodes, state->nodes.nelem + 1);
2498 if (BE (*err != REG_NOERROR, 0))
2500 for (node_cnt = 0; node_cnt < state->nodes.nelem; ++node_cnt)
2502 Idx cur_node = state->nodes.elems[node_cnt];
2503 if (check_node_accept (mctx, dfa->nodes + cur_node, cur_str_idx))
2505 *err = re_node_set_merge (&next_nodes,
2506 dfa->eclosures + dfa->nexts[cur_node]);
2507 if (BE (*err != REG_NOERROR, 0))
2509 re_node_set_free (&next_nodes);
2514 context = re_string_context_at (&mctx->input, cur_str_idx, mctx->eflags);
2515 next_state = re_acquire_state_context (err, dfa, &next_nodes, context);
2516 /* We don't need to check errors here, since the return value of
2517 this function is next_state and ERR is already set. */
2519 re_node_set_free (&next_nodes);
2520 re_string_skip_bytes (&mctx->input, 1);
2525 #ifdef RE_ENABLE_I18N
2526 static reg_errcode_t
2528 transit_state_mb (re_match_context_t *mctx, re_dfastate_t *pstate)
2530 const re_dfa_t *const dfa = mctx->dfa;
2534 for (i = 0; i < pstate->nodes.nelem; ++i)
2536 re_node_set dest_nodes, *new_nodes;
2537 Idx cur_node_idx = pstate->nodes.elems[i];
2540 unsigned int context;
2541 re_dfastate_t *dest_state;
2543 if (!dfa->nodes[cur_node_idx].accept_mb)
2546 if (dfa->nodes[cur_node_idx].constraint)
2548 context = re_string_context_at (&mctx->input,
2549 re_string_cur_idx (&mctx->input),
2551 if (NOT_SATISFY_NEXT_CONSTRAINT (dfa->nodes[cur_node_idx].constraint,
2556 /* How many bytes the node can accept? */
2557 naccepted = check_node_accept_bytes (dfa, cur_node_idx, &mctx->input,
2558 re_string_cur_idx (&mctx->input));
2562 /* The node can accepts `naccepted' bytes. */
2563 dest_idx = re_string_cur_idx (&mctx->input) + naccepted;
2564 mctx->max_mb_elem_len = ((mctx->max_mb_elem_len < naccepted) ? naccepted
2565 : mctx->max_mb_elem_len);
2566 err = clean_state_log_if_needed (mctx, dest_idx);
2567 if (BE (err != REG_NOERROR, 0))
2570 assert (dfa->nexts[cur_node_idx] != REG_MISSING);
2572 new_nodes = dfa->eclosures + dfa->nexts[cur_node_idx];
2574 dest_state = mctx->state_log[dest_idx];
2575 if (dest_state == NULL)
2576 dest_nodes = *new_nodes;
2579 err = re_node_set_init_union (&dest_nodes,
2580 dest_state->entrance_nodes, new_nodes);
2581 if (BE (err != REG_NOERROR, 0))
2584 context = re_string_context_at (&mctx->input, dest_idx - 1,
2586 mctx->state_log[dest_idx]
2587 = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2588 if (dest_state != NULL)
2589 re_node_set_free (&dest_nodes);
2590 if (BE (mctx->state_log[dest_idx] == NULL && err != REG_NOERROR, 0))
2595 #endif /* RE_ENABLE_I18N */
2597 static reg_errcode_t
2599 transit_state_bkref (re_match_context_t *mctx, const re_node_set *nodes)
2601 const re_dfa_t *const dfa = mctx->dfa;
2604 Idx cur_str_idx = re_string_cur_idx (&mctx->input);
2606 for (i = 0; i < nodes->nelem; ++i)
2608 Idx dest_str_idx, prev_nelem, bkc_idx;
2609 Idx node_idx = nodes->elems[i];
2610 unsigned int context;
2611 const re_token_t *node = dfa->nodes + node_idx;
2612 re_node_set *new_dest_nodes;
2614 /* Check whether `node' is a backreference or not. */
2615 if (node->type != OP_BACK_REF)
2618 if (node->constraint)
2620 context = re_string_context_at (&mctx->input, cur_str_idx,
2622 if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
2626 /* `node' is a backreference.
2627 Check the substring which the substring matched. */
2628 bkc_idx = mctx->nbkref_ents;
2629 err = get_subexp (mctx, node_idx, cur_str_idx);
2630 if (BE (err != REG_NOERROR, 0))
2633 /* And add the epsilon closures (which is `new_dest_nodes') of
2634 the backreference to appropriate state_log. */
2636 assert (dfa->nexts[node_idx] != REG_MISSING);
2638 for (; bkc_idx < mctx->nbkref_ents; ++bkc_idx)
2641 re_dfastate_t *dest_state;
2642 struct re_backref_cache_entry *bkref_ent;
2643 bkref_ent = mctx->bkref_ents + bkc_idx;
2644 if (bkref_ent->node != node_idx || bkref_ent->str_idx != cur_str_idx)
2646 subexp_len = bkref_ent->subexp_to - bkref_ent->subexp_from;
2647 new_dest_nodes = (subexp_len == 0
2648 ? dfa->eclosures + dfa->edests[node_idx].elems[0]
2649 : dfa->eclosures + dfa->nexts[node_idx]);
2650 dest_str_idx = (cur_str_idx + bkref_ent->subexp_to
2651 - bkref_ent->subexp_from);
2652 context = re_string_context_at (&mctx->input, dest_str_idx - 1,
2654 dest_state = mctx->state_log[dest_str_idx];
2655 prev_nelem = ((mctx->state_log[cur_str_idx] == NULL) ? 0
2656 : mctx->state_log[cur_str_idx]->nodes.nelem);
2657 /* Add `new_dest_node' to state_log. */
2658 if (dest_state == NULL)
2660 mctx->state_log[dest_str_idx]
2661 = re_acquire_state_context (&err, dfa, new_dest_nodes,
2663 if (BE (mctx->state_log[dest_str_idx] == NULL
2664 && err != REG_NOERROR, 0))
2669 re_node_set dest_nodes;
2670 err = re_node_set_init_union (&dest_nodes,
2671 dest_state->entrance_nodes,
2673 if (BE (err != REG_NOERROR, 0))
2675 re_node_set_free (&dest_nodes);
2678 mctx->state_log[dest_str_idx]
2679 = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2680 re_node_set_free (&dest_nodes);
2681 if (BE (mctx->state_log[dest_str_idx] == NULL
2682 && err != REG_NOERROR, 0))
2685 /* We need to check recursively if the backreference can epsilon
2688 && mctx->state_log[cur_str_idx]->nodes.nelem > prev_nelem)
2690 err = check_subexp_matching_top (mctx, new_dest_nodes,
2692 if (BE (err != REG_NOERROR, 0))
2694 err = transit_state_bkref (mctx, new_dest_nodes);
2695 if (BE (err != REG_NOERROR, 0))
2705 /* Enumerate all the candidates which the backreference BKREF_NODE can match
2706 at BKREF_STR_IDX, and register them by match_ctx_add_entry().
2707 Note that we might collect inappropriate candidates here.
2708 However, the cost of checking them strictly here is too high, then we
2709 delay these checking for prune_impossible_nodes(). */
2711 static reg_errcode_t
2713 get_subexp (re_match_context_t *mctx, Idx bkref_node, Idx bkref_str_idx)
2715 const re_dfa_t *const dfa = mctx->dfa;
2716 Idx subexp_num, sub_top_idx;
2717 const char *buf = (const char *) re_string_get_buffer (&mctx->input);
2718 /* Return if we have already checked BKREF_NODE at BKREF_STR_IDX. */
2719 Idx cache_idx = search_cur_bkref_entry (mctx, bkref_str_idx);
2720 if (cache_idx != REG_MISSING)
2722 const struct re_backref_cache_entry *entry
2723 = mctx->bkref_ents + cache_idx;
2725 if (entry->node == bkref_node)
2726 return REG_NOERROR; /* We already checked it. */
2727 while (entry++->more);
2730 subexp_num = dfa->nodes[bkref_node].opr.idx;
2732 /* For each sub expression */
2733 for (sub_top_idx = 0; sub_top_idx < mctx->nsub_tops; ++sub_top_idx)
2736 re_sub_match_top_t *sub_top = mctx->sub_tops[sub_top_idx];
2737 re_sub_match_last_t *sub_last;
2738 Idx sub_last_idx, sl_str, bkref_str_off;
2740 if (dfa->nodes[sub_top->node].opr.idx != subexp_num)
2741 continue; /* It isn't related. */
2743 sl_str = sub_top->str_idx;
2744 bkref_str_off = bkref_str_idx;
2745 /* At first, check the last node of sub expressions we already
2747 for (sub_last_idx = 0; sub_last_idx < sub_top->nlasts; ++sub_last_idx)
2749 regoff_t sl_str_diff;
2750 sub_last = sub_top->lasts[sub_last_idx];
2751 sl_str_diff = sub_last->str_idx - sl_str;
2752 /* The matched string by the sub expression match with the substring
2753 at the back reference? */
2754 if (sl_str_diff > 0)
2756 if (BE (bkref_str_off + sl_str_diff > mctx->input.valid_len, 0))
2758 /* Not enough chars for a successful match. */
2759 if (bkref_str_off + sl_str_diff > mctx->input.len)
2762 err = clean_state_log_if_needed (mctx,
2765 if (BE (err != REG_NOERROR, 0))
2767 buf = (const char *) re_string_get_buffer (&mctx->input);
2769 if (memcmp (buf + bkref_str_off, buf + sl_str, sl_str_diff) != 0)
2770 /* We don't need to search this sub expression any more. */
2773 bkref_str_off += sl_str_diff;
2774 sl_str += sl_str_diff;
2775 err = get_subexp_sub (mctx, sub_top, sub_last, bkref_node,
2778 /* Reload buf, since the preceding call might have reallocated
2780 buf = (const char *) re_string_get_buffer (&mctx->input);
2782 if (err == REG_NOMATCH)
2784 if (BE (err != REG_NOERROR, 0))
2788 if (sub_last_idx < sub_top->nlasts)
2790 if (sub_last_idx > 0)
2792 /* Then, search for the other last nodes of the sub expression. */
2793 for (; sl_str <= bkref_str_idx; ++sl_str)
2796 regoff_t sl_str_off;
2797 const re_node_set *nodes;
2798 sl_str_off = sl_str - sub_top->str_idx;
2799 /* The matched string by the sub expression match with the substring
2800 at the back reference? */
2803 if (BE (bkref_str_off >= mctx->input.valid_len, 0))
2805 /* If we are at the end of the input, we cannot match. */
2806 if (bkref_str_off >= mctx->input.len)
2809 err = extend_buffers (mctx);
2810 if (BE (err != REG_NOERROR, 0))
2813 buf = (const char *) re_string_get_buffer (&mctx->input);
2815 if (buf [bkref_str_off++] != buf[sl_str - 1])
2816 break; /* We don't need to search this sub expression
2819 if (mctx->state_log[sl_str] == NULL)
2821 /* Does this state have a ')' of the sub expression? */
2822 nodes = &mctx->state_log[sl_str]->nodes;
2823 cls_node = find_subexp_node (dfa, nodes, subexp_num,
2825 if (cls_node == REG_MISSING)
2827 if (sub_top->path == NULL)
2829 sub_top->path = calloc (sizeof (state_array_t),
2830 sl_str - sub_top->str_idx + 1);
2831 if (sub_top->path == NULL)
2834 /* Can the OP_OPEN_SUBEXP node arrive the OP_CLOSE_SUBEXP node
2835 in the current context? */
2836 err = check_arrival (mctx, sub_top->path, sub_top->node,
2837 sub_top->str_idx, cls_node, sl_str,
2839 if (err == REG_NOMATCH)
2841 if (BE (err != REG_NOERROR, 0))
2843 sub_last = match_ctx_add_sublast (sub_top, cls_node, sl_str);
2844 if (BE (sub_last == NULL, 0))
2846 err = get_subexp_sub (mctx, sub_top, sub_last, bkref_node,
2848 if (err == REG_NOMATCH)
2855 /* Helper functions for get_subexp(). */
2857 /* Check SUB_LAST can arrive to the back reference BKREF_NODE at BKREF_STR.
2858 If it can arrive, register the sub expression expressed with SUB_TOP
2861 static reg_errcode_t
2863 get_subexp_sub (re_match_context_t *mctx, const re_sub_match_top_t *sub_top,
2864 re_sub_match_last_t *sub_last, Idx bkref_node, Idx bkref_str)
2868 /* Can the subexpression arrive the back reference? */
2869 err = check_arrival (mctx, &sub_last->path, sub_last->node,
2870 sub_last->str_idx, bkref_node, bkref_str,
2872 if (err != REG_NOERROR)
2874 err = match_ctx_add_entry (mctx, bkref_node, bkref_str, sub_top->str_idx,
2876 if (BE (err != REG_NOERROR, 0))
2878 to_idx = bkref_str + sub_last->str_idx - sub_top->str_idx;
2879 return clean_state_log_if_needed (mctx, to_idx);
2882 /* Find the first node which is '(' or ')' and whose index is SUBEXP_IDX.
2883 Search '(' if FL_OPEN, or search ')' otherwise.
2884 TODO: This function isn't efficient...
2885 Because there might be more than one nodes whose types are
2886 OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
2892 find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
2893 Idx subexp_idx, int type)
2896 for (cls_idx = 0; cls_idx < nodes->nelem; ++cls_idx)
2898 Idx cls_node = nodes->elems[cls_idx];
2899 const re_token_t *node = dfa->nodes + cls_node;
2900 if (node->type == type
2901 && node->opr.idx == subexp_idx)
2907 /* Check whether the node TOP_NODE at TOP_STR can arrive to the node
2908 LAST_NODE at LAST_STR. We record the path onto PATH since it will be
2910 Return REG_NOERROR if it can arrive, or REG_NOMATCH otherwise. */
2912 static reg_errcode_t
2914 check_arrival (re_match_context_t *mctx, state_array_t *path, Idx top_node,
2915 Idx top_str, Idx last_node, Idx last_str, int type)
2917 const re_dfa_t *const dfa = mctx->dfa;
2918 reg_errcode_t err = REG_NOERROR;
2919 Idx subexp_num, backup_cur_idx, str_idx, null_cnt;
2920 re_dfastate_t *cur_state = NULL;
2921 re_node_set *cur_nodes, next_nodes;
2922 re_dfastate_t **backup_state_log;
2923 unsigned int context;
2925 subexp_num = dfa->nodes[top_node].opr.idx;
2926 /* Extend the buffer if we need. */
2927 if (BE (path->alloc < last_str + mctx->max_mb_elem_len + 1, 0))
2929 re_dfastate_t **new_array;
2930 Idx old_alloc = path->alloc;
2931 Idx new_alloc = old_alloc + last_str + mctx->max_mb_elem_len + 1;
2932 if (BE (new_alloc < old_alloc, 0)
2933 || BE (SIZE_MAX / sizeof (re_dfastate_t *) < new_alloc, 0))
2935 new_array = re_realloc (path->array, re_dfastate_t *, new_alloc);
2936 if (BE (new_array == NULL, 0))
2938 path->array = new_array;
2939 path->alloc = new_alloc;
2940 memset (new_array + old_alloc, '\0',
2941 sizeof (re_dfastate_t *) * (path->alloc - old_alloc));
2944 str_idx = path->next_idx ? path->next_idx : top_str;
2946 /* Temporary modify MCTX. */
2947 backup_state_log = mctx->state_log;
2948 backup_cur_idx = mctx->input.cur_idx;
2949 mctx->state_log = path->array;
2950 mctx->input.cur_idx = str_idx;
2952 /* Setup initial node set. */
2953 context = re_string_context_at (&mctx->input, str_idx - 1, mctx->eflags);
2954 if (str_idx == top_str)
2956 err = re_node_set_init_1 (&next_nodes, top_node);
2957 if (BE (err != REG_NOERROR, 0))
2959 err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
2960 if (BE (err != REG_NOERROR, 0))
2962 re_node_set_free (&next_nodes);
2968 cur_state = mctx->state_log[str_idx];
2969 if (cur_state && cur_state->has_backref)
2971 err = re_node_set_init_copy (&next_nodes, &cur_state->nodes);
2972 if (BE (err != REG_NOERROR, 0))
2976 re_node_set_init_empty (&next_nodes);
2978 if (str_idx == top_str || (cur_state && cur_state->has_backref))
2980 if (next_nodes.nelem)
2982 err = expand_bkref_cache (mctx, &next_nodes, str_idx,
2984 if (BE (err != REG_NOERROR, 0))
2986 re_node_set_free (&next_nodes);
2990 cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
2991 if (BE (cur_state == NULL && err != REG_NOERROR, 0))
2993 re_node_set_free (&next_nodes);
2996 mctx->state_log[str_idx] = cur_state;
2999 for (null_cnt = 0; str_idx < last_str && null_cnt <= mctx->max_mb_elem_len;)
3001 re_node_set_empty (&next_nodes);
3002 if (mctx->state_log[str_idx + 1])
3004 err = re_node_set_merge (&next_nodes,
3005 &mctx->state_log[str_idx + 1]->nodes);
3006 if (BE (err != REG_NOERROR, 0))
3008 re_node_set_free (&next_nodes);
3014 err = check_arrival_add_next_nodes (mctx, str_idx,
3015 &cur_state->non_eps_nodes,
3017 if (BE (err != REG_NOERROR, 0))
3019 re_node_set_free (&next_nodes);
3024 if (next_nodes.nelem)
3026 err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
3027 if (BE (err != REG_NOERROR, 0))
3029 re_node_set_free (&next_nodes);
3032 err = expand_bkref_cache (mctx, &next_nodes, str_idx,
3034 if (BE (err != REG_NOERROR, 0))
3036 re_node_set_free (&next_nodes);
3040 context = re_string_context_at (&mctx->input, str_idx - 1, mctx->eflags);
3041 cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
3042 if (BE (cur_state == NULL && err != REG_NOERROR, 0))
3044 re_node_set_free (&next_nodes);
3047 mctx->state_log[str_idx] = cur_state;
3048 null_cnt = cur_state == NULL ? null_cnt + 1 : 0;
3050 re_node_set_free (&next_nodes);
3051 cur_nodes = (mctx->state_log[last_str] == NULL ? NULL
3052 : &mctx->state_log[last_str]->nodes);
3053 path->next_idx = str_idx;
3056 mctx->state_log = backup_state_log;
3057 mctx->input.cur_idx = backup_cur_idx;
3059 /* Then check the current node set has the node LAST_NODE. */
3060 if (cur_nodes != NULL && re_node_set_contains (cur_nodes, last_node))
3066 /* Helper functions for check_arrival. */
3068 /* Calculate the destination nodes of CUR_NODES at STR_IDX, and append them
3070 TODO: This function is similar to the functions transit_state*(),
3071 however this function has many additional works.
3072 Can't we unify them? */
3074 static reg_errcode_t
3076 check_arrival_add_next_nodes (re_match_context_t *mctx, Idx str_idx,
3077 re_node_set *cur_nodes, re_node_set *next_nodes)
3079 const re_dfa_t *const dfa = mctx->dfa;
3082 reg_errcode_t err = REG_NOERROR;
3083 re_node_set union_set;
3084 re_node_set_init_empty (&union_set);
3085 for (cur_idx = 0; cur_idx < cur_nodes->nelem; ++cur_idx)
3088 Idx cur_node = cur_nodes->elems[cur_idx];
3090 re_token_type_t type = dfa->nodes[cur_node].type;
3091 assert (!IS_EPSILON_NODE (type));
3093 #ifdef RE_ENABLE_I18N
3094 /* If the node may accept `multi byte'. */
3095 if (dfa->nodes[cur_node].accept_mb)
3097 naccepted = check_node_accept_bytes (dfa, cur_node, &mctx->input,
3101 re_dfastate_t *dest_state;
3102 Idx next_node = dfa->nexts[cur_node];
3103 Idx next_idx = str_idx + naccepted;
3104 dest_state = mctx->state_log[next_idx];
3105 re_node_set_empty (&union_set);
3108 err = re_node_set_merge (&union_set, &dest_state->nodes);
3109 if (BE (err != REG_NOERROR, 0))
3111 re_node_set_free (&union_set);
3115 ok = re_node_set_insert (&union_set, next_node);
3118 re_node_set_free (&union_set);
3121 mctx->state_log[next_idx] = re_acquire_state (&err, dfa,
3123 if (BE (mctx->state_log[next_idx] == NULL
3124 && err != REG_NOERROR, 0))
3126 re_node_set_free (&union_set);
3131 #endif /* RE_ENABLE_I18N */
3133 || check_node_accept (mctx, dfa->nodes + cur_node, str_idx))
3135 ok = re_node_set_insert (next_nodes, dfa->nexts[cur_node]);
3138 re_node_set_free (&union_set);
3143 re_node_set_free (&union_set);
3147 /* For all the nodes in CUR_NODES, add the epsilon closures of them to
3148 CUR_NODES, however exclude the nodes which are:
3149 - inside the sub expression whose number is EX_SUBEXP, if FL_OPEN.
3150 - out of the sub expression whose number is EX_SUBEXP, if !FL_OPEN.
3153 static reg_errcode_t
3155 check_arrival_expand_ecl (const re_dfa_t *dfa, re_node_set *cur_nodes,
3156 Idx ex_subexp, int type)
3159 Idx idx, outside_node;
3160 re_node_set new_nodes;
3162 assert (cur_nodes->nelem);
3164 err = re_node_set_alloc (&new_nodes, cur_nodes->nelem);
3165 if (BE (err != REG_NOERROR, 0))
3167 /* Create a new node set NEW_NODES with the nodes which are epsilon
3168 closures of the node in CUR_NODES. */
3170 for (idx = 0; idx < cur_nodes->nelem; ++idx)
3172 Idx cur_node = cur_nodes->elems[idx];
3173 const re_node_set *eclosure = dfa->eclosures + cur_node;
3174 outside_node = find_subexp_node (dfa, eclosure, ex_subexp, type);
3175 if (outside_node == REG_MISSING)
3177 /* There are no problematic nodes, just merge them. */
3178 err = re_node_set_merge (&new_nodes, eclosure);
3179 if (BE (err != REG_NOERROR, 0))
3181 re_node_set_free (&new_nodes);
3187 /* There are problematic nodes, re-calculate incrementally. */
3188 err = check_arrival_expand_ecl_sub (dfa, &new_nodes, cur_node,
3190 if (BE (err != REG_NOERROR, 0))
3192 re_node_set_free (&new_nodes);
3197 re_node_set_free (cur_nodes);
3198 *cur_nodes = new_nodes;
3202 /* Helper function for check_arrival_expand_ecl.
3203 Check incrementally the epsilon closure of TARGET, and if it isn't
3204 problematic append it to DST_NODES. */
3206 static reg_errcode_t
3208 check_arrival_expand_ecl_sub (const re_dfa_t *dfa, re_node_set *dst_nodes,
3209 Idx target, Idx ex_subexp, int type)
3212 for (cur_node = target; !re_node_set_contains (dst_nodes, cur_node);)
3216 if (dfa->nodes[cur_node].type == type
3217 && dfa->nodes[cur_node].opr.idx == ex_subexp)
3219 if (type == OP_CLOSE_SUBEXP)
3221 ok = re_node_set_insert (dst_nodes, cur_node);
3227 ok = re_node_set_insert (dst_nodes, cur_node);
3230 if (dfa->edests[cur_node].nelem == 0)
3232 if (dfa->edests[cur_node].nelem == 2)
3235 err = check_arrival_expand_ecl_sub (dfa, dst_nodes,
3236 dfa->edests[cur_node].elems[1],
3238 if (BE (err != REG_NOERROR, 0))
3241 cur_node = dfa->edests[cur_node].elems[0];
3247 /* For all the back references in the current state, calculate the
3248 destination of the back references by the appropriate entry
3249 in MCTX->BKREF_ENTS. */
3251 static reg_errcode_t
3253 expand_bkref_cache (re_match_context_t *mctx, re_node_set *cur_nodes,
3254 Idx cur_str, Idx subexp_num, int type)
3256 const re_dfa_t *const dfa = mctx->dfa;
3258 Idx cache_idx_start = search_cur_bkref_entry (mctx, cur_str);
3259 struct re_backref_cache_entry *ent;
3261 if (cache_idx_start == REG_MISSING)
3265 ent = mctx->bkref_ents + cache_idx_start;
3268 Idx to_idx, next_node;
3270 /* Is this entry ENT is appropriate? */
3271 if (!re_node_set_contains (cur_nodes, ent->node))
3274 to_idx = cur_str + ent->subexp_to - ent->subexp_from;
3275 /* Calculate the destination of the back reference, and append it
3276 to MCTX->STATE_LOG. */
3277 if (to_idx == cur_str)
3279 /* The backreference did epsilon transit, we must re-check all the
3280 node in the current state. */
3281 re_node_set new_dests;
3282 reg_errcode_t err2, err3;
3283 next_node = dfa->edests[ent->node].elems[0];
3284 if (re_node_set_contains (cur_nodes, next_node))
3286 err = re_node_set_init_1 (&new_dests, next_node);
3287 err2 = check_arrival_expand_ecl (dfa, &new_dests, subexp_num, type);
3288 err3 = re_node_set_merge (cur_nodes, &new_dests);
3289 re_node_set_free (&new_dests);
3290 if (BE (err != REG_NOERROR || err2 != REG_NOERROR
3291 || err3 != REG_NOERROR, 0))
3293 err = (err != REG_NOERROR ? err
3294 : (err2 != REG_NOERROR ? err2 : err3));
3297 /* TODO: It is still inefficient... */
3302 re_node_set union_set;
3303 next_node = dfa->nexts[ent->node];
3304 if (mctx->state_log[to_idx])
3307 if (re_node_set_contains (&mctx->state_log[to_idx]->nodes,
3310 err = re_node_set_init_copy (&union_set,
3311 &mctx->state_log[to_idx]->nodes);
3312 ok = re_node_set_insert (&union_set, next_node);
3313 if (BE (err != REG_NOERROR || ! ok, 0))
3315 re_node_set_free (&union_set);
3316 err = err != REG_NOERROR ? err : REG_ESPACE;
3322 err = re_node_set_init_1 (&union_set, next_node);
3323 if (BE (err != REG_NOERROR, 0))
3326 mctx->state_log[to_idx] = re_acquire_state (&err, dfa, &union_set);
3327 re_node_set_free (&union_set);
3328 if (BE (mctx->state_log[to_idx] == NULL
3329 && err != REG_NOERROR, 0))
3333 while (ent++->more);
3337 /* Build transition table for the state.
3338 Return true if successful. */
3342 build_trtable (const re_dfa_t *dfa, re_dfastate_t *state)
3347 bool need_word_trtable = false;
3348 bitset_word_t elem, mask;
3349 bool dests_node_malloced = false;
3350 bool dest_states_malloced = false;
3351 Idx ndests; /* Number of the destination states from `state'. */
3352 re_dfastate_t **trtable;
3353 re_dfastate_t **dest_states = NULL, **dest_states_word, **dest_states_nl;
3354 re_node_set follows, *dests_node;
3356 bitset_t acceptable;
3360 re_node_set dests_node[SBC_MAX];
3361 bitset_t dests_ch[SBC_MAX];
3364 /* We build DFA states which corresponds to the destination nodes
3365 from `state'. `dests_node[i]' represents the nodes which i-th
3366 destination state contains, and `dests_ch[i]' represents the
3367 characters which i-th destination state accepts. */
3368 if (__libc_use_alloca (sizeof (struct dests_alloc)))
3369 dests_alloc = (struct dests_alloc *) alloca (sizeof (struct dests_alloc));
3372 dests_alloc = re_malloc (struct dests_alloc, 1);
3373 if (BE (dests_alloc == NULL, 0))
3375 dests_node_malloced = true;
3377 dests_node = dests_alloc->dests_node;
3378 dests_ch = dests_alloc->dests_ch;
3380 /* Initialize transiton table. */
3381 state->word_trtable = state->trtable = NULL;
3383 /* At first, group all nodes belonging to `state' into several
3385 ndests = group_nodes_into_DFAstates (dfa, state, dests_node, dests_ch);
3386 if (BE (! REG_VALID_NONZERO_INDEX (ndests), 0))
3388 if (dests_node_malloced)
3392 state->trtable = (re_dfastate_t **)
3393 calloc (sizeof (re_dfastate_t *), SBC_MAX);
3399 err = re_node_set_alloc (&follows, ndests + 1);
3400 if (BE (err != REG_NOERROR, 0))
3403 /* Avoid arithmetic overflow in size calculation. */
3404 if (BE ((((SIZE_MAX - (sizeof (re_node_set) + sizeof (bitset_t)) * SBC_MAX)
3405 / (3 * sizeof (re_dfastate_t *)))
3410 if (__libc_use_alloca ((sizeof (re_node_set) + sizeof (bitset_t)) * SBC_MAX
3411 + ndests * 3 * sizeof (re_dfastate_t *)))
3412 dest_states = (re_dfastate_t **)
3413 alloca (ndests * 3 * sizeof (re_dfastate_t *));
3416 dest_states = (re_dfastate_t **)
3417 malloc (ndests * 3 * sizeof (re_dfastate_t *));
3418 if (BE (dest_states == NULL, 0))
3421 if (dest_states_malloced)
3423 re_node_set_free (&follows);
3424 for (i = 0; i < ndests; ++i)
3425 re_node_set_free (dests_node + i);
3426 if (dests_node_malloced)
3430 dest_states_malloced = true;
3432 dest_states_word = dest_states + ndests;
3433 dest_states_nl = dest_states_word + ndests;
3434 bitset_empty (acceptable);
3436 /* Then build the states for all destinations. */
3437 for (i = 0; i < ndests; ++i)
3440 re_node_set_empty (&follows);
3441 /* Merge the follows of this destination states. */
3442 for (j = 0; j < dests_node[i].nelem; ++j)
3444 next_node = dfa->nexts[dests_node[i].elems[j]];
3445 if (next_node != REG_MISSING)
3447 err = re_node_set_merge (&follows, dfa->eclosures + next_node);
3448 if (BE (err != REG_NOERROR, 0))
3452 dest_states[i] = re_acquire_state_context (&err, dfa, &follows, 0);
3453 if (BE (dest_states[i] == NULL && err != REG_NOERROR, 0))
3455 /* If the new state has context constraint,
3456 build appropriate states for these contexts. */
3457 if (dest_states[i]->has_constraint)
3459 dest_states_word[i] = re_acquire_state_context (&err, dfa, &follows,
3461 if (BE (dest_states_word[i] == NULL && err != REG_NOERROR, 0))
3464 if (dest_states[i] != dest_states_word[i] && dfa->mb_cur_max > 1)
3465 need_word_trtable = true;
3467 dest_states_nl[i] = re_acquire_state_context (&err, dfa, &follows,
3469 if (BE (dest_states_nl[i] == NULL && err != REG_NOERROR, 0))
3474 dest_states_word[i] = dest_states[i];
3475 dest_states_nl[i] = dest_states[i];
3477 bitset_merge (acceptable, dests_ch[i]);
3480 if (!BE (need_word_trtable, 0))
3482 /* We don't care about whether the following character is a word
3483 character, or we are in a single-byte character set so we can
3484 discern by looking at the character code: allocate a
3485 256-entry transition table. */
3486 trtable = state->trtable =
3487 (re_dfastate_t **) calloc (sizeof (re_dfastate_t *), SBC_MAX);
3488 if (BE (trtable == NULL, 0))
3491 /* For all characters ch...: */
3492 for (i = 0; i < BITSET_WORDS; ++i)
3493 for (ch = i * BITSET_WORD_BITS, elem = acceptable[i], mask = 1;
3495 mask <<= 1, elem >>= 1, ++ch)
3496 if (BE (elem & 1, 0))
3498 /* There must be exactly one destination which accepts
3499 character ch. See group_nodes_into_DFAstates. */
3500 for (j = 0; (dests_ch[j][i] & mask) == 0; ++j)
3503 /* j-th destination accepts the word character ch. */
3504 if (dfa->word_char[i] & mask)
3505 trtable[ch] = dest_states_word[j];
3507 trtable[ch] = dest_states[j];
3512 /* We care about whether the following character is a word
3513 character, and we are in a multi-byte character set: discern
3514 by looking at the character code: build two 256-entry
3515 transition tables, one starting at trtable[0] and one
3516 starting at trtable[SBC_MAX]. */
3517 trtable = state->word_trtable =
3518 (re_dfastate_t **) calloc (sizeof (re_dfastate_t *), 2 * SBC_MAX);
3519 if (BE (trtable == NULL, 0))
3522 /* For all characters ch...: */
3523 for (i = 0; i < BITSET_WORDS; ++i)
3524 for (ch = i * BITSET_WORD_BITS, elem = acceptable[i], mask = 1;
3526 mask <<= 1, elem >>= 1, ++ch)
3527 if (BE (elem & 1, 0))
3529 /* There must be exactly one destination which accepts
3530 character ch. See group_nodes_into_DFAstates. */
3531 for (j = 0; (dests_ch[j][i] & mask) == 0; ++j)
3534 /* j-th destination accepts the word character ch. */
3535 trtable[ch] = dest_states[j];
3536 trtable[ch + SBC_MAX] = dest_states_word[j];
3541 if (bitset_contain (acceptable, NEWLINE_CHAR))
3543 /* The current state accepts newline character. */
3544 for (j = 0; j < ndests; ++j)
3545 if (bitset_contain (dests_ch[j], NEWLINE_CHAR))
3547 /* k-th destination accepts newline character. */
3548 trtable[NEWLINE_CHAR] = dest_states_nl[j];
3549 if (need_word_trtable)
3550 trtable[NEWLINE_CHAR + SBC_MAX] = dest_states_nl[j];
3551 /* There must be only one destination which accepts
3552 newline. See group_nodes_into_DFAstates. */
3557 if (dest_states_malloced)
3560 re_node_set_free (&follows);
3561 for (i = 0; i < ndests; ++i)
3562 re_node_set_free (dests_node + i);
3564 if (dests_node_malloced)
3570 /* Group all nodes belonging to STATE into several destinations.
3571 Then for all destinations, set the nodes belonging to the destination
3572 to DESTS_NODE[i] and set the characters accepted by the destination
3573 to DEST_CH[i]. This function return the number of destinations. */
3577 group_nodes_into_DFAstates (const re_dfa_t *dfa, const re_dfastate_t *state,
3578 re_node_set *dests_node, bitset_t *dests_ch)
3583 Idx ndests; /* Number of the destinations from `state'. */
3584 bitset_t accepts; /* Characters a node can accept. */
3585 const re_node_set *cur_nodes = &state->nodes;
3586 bitset_empty (accepts);
3589 /* For all the nodes belonging to `state', */
3590 for (i = 0; i < cur_nodes->nelem; ++i)
3592 re_token_t *node = &dfa->nodes[cur_nodes->elems[i]];
3593 re_token_type_t type = node->type;
3594 unsigned int constraint = node->constraint;
3596 /* Enumerate all single byte character this node can accept. */
3597 if (type == CHARACTER)
3598 bitset_set (accepts, node->opr.c);
3599 else if (type == SIMPLE_BRACKET)
3601 bitset_merge (accepts, node->opr.sbcset);
3603 else if (type == OP_PERIOD)
3605 #ifdef RE_ENABLE_I18N
3606 if (dfa->mb_cur_max > 1)
3607 bitset_merge (accepts, dfa->sb_char);
3610 bitset_set_all (accepts);
3611 if (!(dfa->syntax & RE_DOT_NEWLINE))
3612 bitset_clear (accepts, '\n');
3613 if (dfa->syntax & RE_DOT_NOT_NULL)
3614 bitset_clear (accepts, '\0');
3616 #ifdef RE_ENABLE_I18N
3617 else if (type == OP_UTF8_PERIOD)
3619 if (ASCII_CHARS % BITSET_WORD_BITS == 0)
3620 memset (accepts, -1, ASCII_CHARS / CHAR_BIT);
3622 bitset_merge (accepts, utf8_sb_map);
3623 if (!(dfa->syntax & RE_DOT_NEWLINE))
3624 bitset_clear (accepts, '\n');
3625 if (dfa->syntax & RE_DOT_NOT_NULL)
3626 bitset_clear (accepts, '\0');
3632 /* Check the `accepts' and sift the characters which are not
3633 match it the context. */
3636 if (constraint & NEXT_NEWLINE_CONSTRAINT)
3638 bool accepts_newline = bitset_contain (accepts, NEWLINE_CHAR);
3639 bitset_empty (accepts);
3640 if (accepts_newline)
3641 bitset_set (accepts, NEWLINE_CHAR);
3645 if (constraint & NEXT_ENDBUF_CONSTRAINT)
3647 bitset_empty (accepts);
3651 if (constraint & NEXT_WORD_CONSTRAINT)
3653 bitset_word_t any_set = 0;
3654 if (type == CHARACTER && !node->word_char)
3656 bitset_empty (accepts);
3659 #ifdef RE_ENABLE_I18N
3660 if (dfa->mb_cur_max > 1)
3661 for (j = 0; j < BITSET_WORDS; ++j)
3662 any_set |= (accepts[j] &= (dfa->word_char[j] | ~dfa->sb_char[j]));
3665 for (j = 0; j < BITSET_WORDS; ++j)
3666 any_set |= (accepts[j] &= dfa->word_char[j]);
3670 if (constraint & NEXT_NOTWORD_CONSTRAINT)
3672 bitset_word_t any_set = 0;
3673 if (type == CHARACTER && node->word_char)
3675 bitset_empty (accepts);
3678 #ifdef RE_ENABLE_I18N
3679 if (dfa->mb_cur_max > 1)
3680 for (j = 0; j < BITSET_WORDS; ++j)
3681 any_set |= (accepts[j] &= ~(dfa->word_char[j] & dfa->sb_char[j]));
3684 for (j = 0; j < BITSET_WORDS; ++j)
3685 any_set |= (accepts[j] &= ~dfa->word_char[j]);
3691 /* Then divide `accepts' into DFA states, or create a new
3692 state. Above, we make sure that accepts is not empty. */
3693 for (j = 0; j < ndests; ++j)
3695 bitset_t intersec; /* Intersection sets, see below. */
3697 /* Flags, see below. */
3698 bitset_word_t has_intersec, not_subset, not_consumed;
3700 /* Optimization, skip if this state doesn't accept the character. */
3701 if (type == CHARACTER && !bitset_contain (dests_ch[j], node->opr.c))
3704 /* Enumerate the intersection set of this state and `accepts'. */
3706 for (k = 0; k < BITSET_WORDS; ++k)
3707 has_intersec |= intersec[k] = accepts[k] & dests_ch[j][k];
3708 /* And skip if the intersection set is empty. */
3712 /* Then check if this state is a subset of `accepts'. */
3713 not_subset = not_consumed = 0;
3714 for (k = 0; k < BITSET_WORDS; ++k)
3716 not_subset |= remains[k] = ~accepts[k] & dests_ch[j][k];
3717 not_consumed |= accepts[k] = accepts[k] & ~dests_ch[j][k];
3720 /* If this state isn't a subset of `accepts', create a
3721 new group state, which has the `remains'. */
3724 bitset_copy (dests_ch[ndests], remains);
3725 bitset_copy (dests_ch[j], intersec);
3726 err = re_node_set_init_copy (dests_node + ndests, &dests_node[j]);
3727 if (BE (err != REG_NOERROR, 0))
3732 /* Put the position in the current group. */
3733 ok = re_node_set_insert (&dests_node[j], cur_nodes->elems[i]);
3737 /* If all characters are consumed, go to next node. */
3741 /* Some characters remain, create a new group. */
3744 bitset_copy (dests_ch[ndests], accepts);
3745 err = re_node_set_init_1 (dests_node + ndests, cur_nodes->elems[i]);
3746 if (BE (err != REG_NOERROR, 0))
3749 bitset_empty (accepts);
3754 for (j = 0; j < ndests; ++j)
3755 re_node_set_free (dests_node + j);
3759 #ifdef RE_ENABLE_I18N
3760 /* Check how many bytes the node `dfa->nodes[node_idx]' accepts.
3761 Return the number of the bytes the node accepts.
3762 STR_IDX is the current index of the input string.
3764 This function handles the nodes which can accept one character, or
3765 one collating element like '.', '[a-z]', opposite to the other nodes
3766 can only accept one byte. */
3770 check_node_accept_bytes (const re_dfa_t *dfa, Idx node_idx,
3771 const re_string_t *input, Idx str_idx)
3773 const re_token_t *node = dfa->nodes + node_idx;
3774 int char_len, elem_len;
3777 if (BE (node->type == OP_UTF8_PERIOD, 0))
3779 unsigned char c = re_string_byte_at (input, str_idx), d;
3780 if (BE (c < 0xc2, 1))
3783 if (str_idx + 2 > input->len)
3786 d = re_string_byte_at (input, str_idx + 1);
3788 return (d < 0x80 || d > 0xbf) ? 0 : 2;
3792 if (c == 0xe0 && d < 0xa0)
3798 if (c == 0xf0 && d < 0x90)
3804 if (c == 0xf8 && d < 0x88)
3810 if (c == 0xfc && d < 0x84)
3816 if (str_idx + char_len > input->len)
3819 for (i = 1; i < char_len; ++i)
3821 d = re_string_byte_at (input, str_idx + i);
3822 if (d < 0x80 || d > 0xbf)
3828 char_len = re_string_char_size_at (input, str_idx);
3829 if (node->type == OP_PERIOD)
3833 /* FIXME: I don't think this if is needed, as both '\n'
3834 and '\0' are char_len == 1. */
3835 /* '.' accepts any one character except the following two cases. */
3836 if ((!(dfa->syntax & RE_DOT_NEWLINE) &&
3837 re_string_byte_at (input, str_idx) == '\n') ||
3838 ((dfa->syntax & RE_DOT_NOT_NULL) &&
3839 re_string_byte_at (input, str_idx) == '\0'))
3844 elem_len = re_string_elem_size_at (input, str_idx);
3845 if ((elem_len <= 1 && char_len <= 1) || char_len == 0)
3848 if (node->type == COMPLEX_BRACKET)
3850 const re_charset_t *cset = node->opr.mbcset;
3852 const unsigned char *pin
3853 = ((const unsigned char *) re_string_get_buffer (input) + str_idx);
3858 wchar_t wc = ((cset->nranges || cset->nchar_classes || cset->nmbchars)
3859 ? re_string_wchar_at (input, str_idx) : 0);
3861 /* match with multibyte character? */
3862 for (i = 0; i < cset->nmbchars; ++i)
3863 if (wc == cset->mbchars[i])
3865 match_len = char_len;
3866 goto check_node_accept_bytes_match;
3868 /* match with character_class? */
3869 for (i = 0; i < cset->nchar_classes; ++i)
3871 wctype_t wt = cset->char_classes[i];
3872 if (__iswctype (wc, wt))
3874 match_len = char_len;
3875 goto check_node_accept_bytes_match;
3880 nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
3883 unsigned int in_collseq = 0;
3884 const int32_t *table, *indirect;
3885 const unsigned char *weights, *extra;
3886 const char *collseqwc;
3888 /* This #include defines a local function! */
3889 # include <locale/weight.h>
3891 /* match with collating_symbol? */
3892 if (cset->ncoll_syms)
3893 extra = (const unsigned char *)
3894 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB);
3895 for (i = 0; i < cset->ncoll_syms; ++i)
3897 const unsigned char *coll_sym = extra + cset->coll_syms[i];
3898 /* Compare the length of input collating element and
3899 the length of current collating element. */
3900 if (*coll_sym != elem_len)
3902 /* Compare each bytes. */
3903 for (j = 0; j < *coll_sym; j++)
3904 if (pin[j] != coll_sym[1 + j])
3908 /* Match if every bytes is equal. */
3910 goto check_node_accept_bytes_match;
3916 if (elem_len <= char_len)
3918 collseqwc = _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQWC);
3919 in_collseq = __collseq_table_lookup (collseqwc, wc);
3922 in_collseq = find_collation_sequence_value (pin, elem_len);
3924 /* match with range expression? */
3925 for (i = 0; i < cset->nranges; ++i)
3926 if (cset->range_starts[i] <= in_collseq
3927 && in_collseq <= cset->range_ends[i])
3929 match_len = elem_len;
3930 goto check_node_accept_bytes_match;
3933 /* match with equivalence_class? */
3934 if (cset->nequiv_classes)
3936 const unsigned char *cp = pin;
3937 table = (const int32_t *)
3938 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
3939 weights = (const unsigned char *)
3940 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_WEIGHTMB);
3941 extra = (const unsigned char *)
3942 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAMB);
3943 indirect = (const int32_t *)
3944 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_INDIRECTMB);
3945 idx = findidx (&cp);
3947 for (i = 0; i < cset->nequiv_classes; ++i)
3949 int32_t equiv_class_idx = cset->equiv_classes[i];
3950 size_t weight_len = weights[idx];
3951 if (weight_len == weights[equiv_class_idx])
3954 while (cnt <= weight_len
3955 && (weights[equiv_class_idx + 1 + cnt]
3956 == weights[idx + 1 + cnt]))
3958 if (cnt > weight_len)
3960 match_len = elem_len;
3961 goto check_node_accept_bytes_match;
3970 /* match with range expression? */
3971 #if __GNUC__ >= 2 && ! (__STDC_VERSION__ < 199901L && __STRICT_ANSI__)
3972 wchar_t cmp_buf[] = {L'\0', L'\0', wc, L'\0', L'\0', L'\0'};
3974 wchar_t cmp_buf[] = {L'\0', L'\0', L'\0', L'\0', L'\0', L'\0'};
3977 for (i = 0; i < cset->nranges; ++i)
3979 cmp_buf[0] = cset->range_starts[i];
3980 cmp_buf[4] = cset->range_ends[i];
3981 if (wcscoll (cmp_buf, cmp_buf + 2) <= 0
3982 && wcscoll (cmp_buf + 2, cmp_buf + 4) <= 0)
3984 match_len = char_len;
3985 goto check_node_accept_bytes_match;
3989 check_node_accept_bytes_match:
3990 if (!cset->non_match)
3997 return (elem_len > char_len) ? elem_len : char_len;
4006 find_collation_sequence_value (const unsigned char *mbs, size_t mbs_len)
4008 uint32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
4013 /* No valid character. Match it as a single byte character. */
4014 const unsigned char *collseq = (const unsigned char *)
4015 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQMB);
4016 return collseq[mbs[0]];
4023 const unsigned char *extra = (const unsigned char *)
4024 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB);
4025 int32_t extrasize = (const unsigned char *)
4026 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB + 1) - extra;
4028 for (idx = 0; idx < extrasize;)
4032 int32_t elem_mbs_len;
4033 /* Skip the name of collating element name. */
4034 idx = idx + extra[idx] + 1;
4035 elem_mbs_len = extra[idx++];
4036 if (mbs_len == elem_mbs_len)
4038 for (mbs_cnt = 0; mbs_cnt < elem_mbs_len; ++mbs_cnt)
4039 if (extra[idx + mbs_cnt] != mbs[mbs_cnt])
4041 if (mbs_cnt == elem_mbs_len)
4042 /* Found the entry. */
4045 /* Skip the byte sequence of the collating element. */
4046 idx += elem_mbs_len;
4047 /* Adjust for the alignment. */
4048 idx = (idx + 3) & ~3;
4049 /* Skip the collation sequence value. */
4050 idx += sizeof (uint32_t);
4051 /* Skip the wide char sequence of the collating element. */
4052 idx = idx + sizeof (uint32_t) * (extra[idx] + 1);
4053 /* If we found the entry, return the sequence value. */
4055 return *(uint32_t *) (extra + idx);
4056 /* Skip the collation sequence value. */
4057 idx += sizeof (uint32_t);
4063 #endif /* RE_ENABLE_I18N */
4065 /* Check whether the node accepts the byte which is IDX-th
4066 byte of the INPUT. */
4070 check_node_accept (const re_match_context_t *mctx, const re_token_t *node,
4074 ch = re_string_byte_at (&mctx->input, idx);
4078 if (node->opr.c != ch)
4082 case SIMPLE_BRACKET:
4083 if (!bitset_contain (node->opr.sbcset, ch))
4087 #ifdef RE_ENABLE_I18N
4088 case OP_UTF8_PERIOD:
4089 if (ch >= ASCII_CHARS)
4094 if ((ch == '\n' && !(mctx->dfa->syntax & RE_DOT_NEWLINE))
4095 || (ch == '\0' && (mctx->dfa->syntax & RE_DOT_NOT_NULL)))
4103 if (node->constraint)
4105 /* The node has constraints. Check whether the current context
4106 satisfies the constraints. */
4107 unsigned int context = re_string_context_at (&mctx->input, idx,
4109 if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
4116 /* Extend the buffers, if the buffers have run out. */
4118 static reg_errcode_t
4120 extend_buffers (re_match_context_t *mctx)
4123 re_string_t *pstr = &mctx->input;
4125 /* Avoid overflow. */
4126 if (BE (SIZE_MAX / 2 / sizeof (re_dfastate_t *) <= pstr->bufs_len, 0))
4129 /* Double the lengthes of the buffers. */
4130 ret = re_string_realloc_buffers (pstr, pstr->bufs_len * 2);
4131 if (BE (ret != REG_NOERROR, 0))
4134 if (mctx->state_log != NULL)
4136 /* And double the length of state_log. */
4137 /* XXX We have no indication of the size of this buffer. If this
4138 allocation fail we have no indication that the state_log array
4139 does not have the right size. */
4140 re_dfastate_t **new_array = re_realloc (mctx->state_log, re_dfastate_t *,
4141 pstr->bufs_len + 1);
4142 if (BE (new_array == NULL, 0))
4144 mctx->state_log = new_array;
4147 /* Then reconstruct the buffers. */
4150 #ifdef RE_ENABLE_I18N
4151 if (pstr->mb_cur_max > 1)
4153 ret = build_wcs_upper_buffer (pstr);
4154 if (BE (ret != REG_NOERROR, 0))
4158 #endif /* RE_ENABLE_I18N */
4159 build_upper_buffer (pstr);
4163 #ifdef RE_ENABLE_I18N
4164 if (pstr->mb_cur_max > 1)
4165 build_wcs_buffer (pstr);
4167 #endif /* RE_ENABLE_I18N */
4169 if (pstr->trans != NULL)
4170 re_string_translate_buffer (pstr);
4177 /* Functions for matching context. */
4179 /* Initialize MCTX. */
4181 static reg_errcode_t
4183 match_ctx_init (re_match_context_t *mctx, int eflags, Idx n)
4185 mctx->eflags = eflags;
4186 mctx->match_last = REG_MISSING;
4189 /* Avoid overflow. */
4190 size_t max_object_size =
4191 MAX (sizeof (struct re_backref_cache_entry),
4192 sizeof (re_sub_match_top_t *));
4193 if (BE (SIZE_MAX / max_object_size < n, 0))
4196 mctx->bkref_ents = re_malloc (struct re_backref_cache_entry, n);
4197 mctx->sub_tops = re_malloc (re_sub_match_top_t *, n);
4198 if (BE (mctx->bkref_ents == NULL || mctx->sub_tops == NULL, 0))
4201 /* Already zero-ed by the caller.
4203 mctx->bkref_ents = NULL;
4204 mctx->nbkref_ents = 0;
4205 mctx->nsub_tops = 0; */
4206 mctx->abkref_ents = n;
4207 mctx->max_mb_elem_len = 1;
4208 mctx->asub_tops = n;
4212 /* Clean the entries which depend on the current input in MCTX.
4213 This function must be invoked when the matcher changes the start index
4214 of the input, or changes the input string. */
4218 match_ctx_clean (re_match_context_t *mctx)
4221 for (st_idx = 0; st_idx < mctx->nsub_tops; ++st_idx)
4224 re_sub_match_top_t *top = mctx->sub_tops[st_idx];
4225 for (sl_idx = 0; sl_idx < top->nlasts; ++sl_idx)
4227 re_sub_match_last_t *last = top->lasts[sl_idx];
4228 re_free (last->path.array);
4231 re_free (top->lasts);
4234 re_free (top->path->array);
4235 re_free (top->path);
4240 mctx->nsub_tops = 0;
4241 mctx->nbkref_ents = 0;
4244 /* Free all the memory associated with MCTX. */
4248 match_ctx_free (re_match_context_t *mctx)
4250 /* First, free all the memory associated with MCTX->SUB_TOPS. */
4251 match_ctx_clean (mctx);
4252 re_free (mctx->sub_tops);
4253 re_free (mctx->bkref_ents);
4256 /* Add a new backreference entry to MCTX.
4257 Note that we assume that caller never call this function with duplicate
4258 entry, and call with STR_IDX which isn't smaller than any existing entry.
4261 static reg_errcode_t
4263 match_ctx_add_entry (re_match_context_t *mctx, Idx node, Idx str_idx, Idx from,
4266 if (mctx->nbkref_ents >= mctx->abkref_ents)
4268 struct re_backref_cache_entry* new_entry;
4269 new_entry = re_realloc (mctx->bkref_ents, struct re_backref_cache_entry,
4270 mctx->abkref_ents * 2);
4271 if (BE (new_entry == NULL, 0))
4273 re_free (mctx->bkref_ents);
4276 mctx->bkref_ents = new_entry;
4277 memset (mctx->bkref_ents + mctx->nbkref_ents, '\0',
4278 sizeof (struct re_backref_cache_entry) * mctx->abkref_ents);
4279 mctx->abkref_ents *= 2;
4281 if (mctx->nbkref_ents > 0
4282 && mctx->bkref_ents[mctx->nbkref_ents - 1].str_idx == str_idx)
4283 mctx->bkref_ents[mctx->nbkref_ents - 1].more = 1;
4285 mctx->bkref_ents[mctx->nbkref_ents].node = node;
4286 mctx->bkref_ents[mctx->nbkref_ents].str_idx = str_idx;
4287 mctx->bkref_ents[mctx->nbkref_ents].subexp_from = from;
4288 mctx->bkref_ents[mctx->nbkref_ents].subexp_to = to;
4290 /* This is a cache that saves negative results of check_dst_limits_calc_pos.
4291 If bit N is clear, means that this entry won't epsilon-transition to
4292 an OP_OPEN_SUBEXP or OP_CLOSE_SUBEXP for the N+1-th subexpression. If
4293 it is set, check_dst_limits_calc_pos_1 will recurse and try to find one
4296 A backreference does not epsilon-transition unless it is empty, so set
4297 to all zeros if FROM != TO. */
4298 mctx->bkref_ents[mctx->nbkref_ents].eps_reachable_subexps_map
4299 = (from == to ? -1 : 0);
4301 mctx->bkref_ents[mctx->nbkref_ents++].more = 0;
4302 if (mctx->max_mb_elem_len < to - from)
4303 mctx->max_mb_elem_len = to - from;
4307 /* Return the first entry with the same str_idx, or REG_MISSING if none is
4308 found. Note that MCTX->BKREF_ENTS is already sorted by MCTX->STR_IDX. */
4312 search_cur_bkref_entry (const re_match_context_t *mctx, Idx str_idx)
4314 Idx left, right, mid, last;
4315 last = right = mctx->nbkref_ents;
4316 for (left = 0; left < right;)
4318 mid = (left + right) / 2;
4319 if (mctx->bkref_ents[mid].str_idx < str_idx)
4324 if (left < last && mctx->bkref_ents[left].str_idx == str_idx)
4330 /* Register the node NODE, whose type is OP_OPEN_SUBEXP, and which matches
4333 static reg_errcode_t
4335 match_ctx_add_subtop (re_match_context_t *mctx, Idx node, Idx str_idx)
4338 assert (mctx->sub_tops != NULL);
4339 assert (mctx->asub_tops > 0);
4341 if (BE (mctx->nsub_tops == mctx->asub_tops, 0))
4343 Idx new_asub_tops = mctx->asub_tops * 2;
4344 re_sub_match_top_t **new_array = re_realloc (mctx->sub_tops,
4345 re_sub_match_top_t *,
4347 if (BE (new_array == NULL, 0))
4349 mctx->sub_tops = new_array;
4350 mctx->asub_tops = new_asub_tops;
4352 mctx->sub_tops[mctx->nsub_tops] = calloc (1, sizeof (re_sub_match_top_t));
4353 if (BE (mctx->sub_tops[mctx->nsub_tops] == NULL, 0))
4355 mctx->sub_tops[mctx->nsub_tops]->node = node;
4356 mctx->sub_tops[mctx->nsub_tops++]->str_idx = str_idx;
4360 /* Register the node NODE, whose type is OP_CLOSE_SUBEXP, and which matches
4361 at STR_IDX, whose corresponding OP_OPEN_SUBEXP is SUB_TOP. */
4363 static re_sub_match_last_t *
4365 match_ctx_add_sublast (re_sub_match_top_t *subtop, Idx node, Idx str_idx)
4367 re_sub_match_last_t *new_entry;
4368 if (BE (subtop->nlasts == subtop->alasts, 0))
4370 Idx new_alasts = 2 * subtop->alasts + 1;
4371 re_sub_match_last_t **new_array = re_realloc (subtop->lasts,
4372 re_sub_match_last_t *,
4374 if (BE (new_array == NULL, 0))
4376 subtop->lasts = new_array;
4377 subtop->alasts = new_alasts;
4379 new_entry = calloc (1, sizeof (re_sub_match_last_t));
4380 if (BE (new_entry != NULL, 1))
4382 subtop->lasts[subtop->nlasts] = new_entry;
4383 new_entry->node = node;
4384 new_entry->str_idx = str_idx;
4392 sift_ctx_init (re_sift_context_t *sctx, re_dfastate_t **sifted_sts,
4393 re_dfastate_t **limited_sts, Idx last_node, Idx last_str_idx)
4395 sctx->sifted_states = sifted_sts;
4396 sctx->limited_states = limited_sts;
4397 sctx->last_node = last_node;
4398 sctx->last_str_idx = last_str_idx;
4399 re_node_set_init_empty (&sctx->limits);