1 /* Extended regular expression matching and search library.
2 Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
3 Free Software Foundation, Inc.
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))
1048 if (sifted_states[0] == NULL)
1054 re_free (mctx->state_log);
1055 mctx->state_log = sifted_states;
1056 sifted_states = NULL;
1057 mctx->last_node = halt_node;
1058 mctx->match_last = match_last;
1061 re_free (sifted_states);
1062 re_free (lim_states);
1066 /* Acquire an initial state and return it.
1067 We must select appropriate initial state depending on the context,
1068 since initial states may have constraints like "\<", "^", etc.. */
1070 static inline re_dfastate_t *
1071 __attribute ((always_inline)) internal_function
1072 acquire_init_state_context (reg_errcode_t *err, const re_match_context_t *mctx,
1075 const re_dfa_t *const dfa = mctx->dfa;
1076 if (dfa->init_state->has_constraint)
1078 unsigned int context;
1079 context = re_string_context_at (&mctx->input, idx - 1, mctx->eflags);
1080 if (IS_WORD_CONTEXT (context))
1081 return dfa->init_state_word;
1082 else if (IS_ORDINARY_CONTEXT (context))
1083 return dfa->init_state;
1084 else if (IS_BEGBUF_CONTEXT (context) && IS_NEWLINE_CONTEXT (context))
1085 return dfa->init_state_begbuf;
1086 else if (IS_NEWLINE_CONTEXT (context))
1087 return dfa->init_state_nl;
1088 else if (IS_BEGBUF_CONTEXT (context))
1090 /* It is relatively rare case, then calculate on demand. */
1091 return re_acquire_state_context (err, dfa,
1092 dfa->init_state->entrance_nodes,
1096 /* Must not happen? */
1097 return dfa->init_state;
1100 return dfa->init_state;
1103 /* Check whether the regular expression match input string INPUT or not,
1104 and return the index where the matching end. Return REG_MISSING if
1105 there is no match, and return REG_ERROR in case of an error.
1106 FL_LONGEST_MATCH means we want the POSIX longest matching.
1107 If P_MATCH_FIRST is not NULL, and the match fails, it is set to the
1108 next place where we may want to try matching.
1109 Note that the matcher assume that the maching starts from the current
1110 index of the buffer. */
1114 check_matching (re_match_context_t *mctx, bool fl_longest_match,
1117 const re_dfa_t *const dfa = mctx->dfa;
1120 Idx match_last = REG_MISSING;
1121 Idx cur_str_idx = re_string_cur_idx (&mctx->input);
1122 re_dfastate_t *cur_state;
1123 bool at_init_state = p_match_first != NULL;
1124 Idx next_start_idx = cur_str_idx;
1127 cur_state = acquire_init_state_context (&err, mctx, cur_str_idx);
1128 /* An initial state must not be NULL (invalid). */
1129 if (BE (cur_state == NULL, 0))
1131 assert (err == REG_ESPACE);
1135 if (mctx->state_log != NULL)
1137 mctx->state_log[cur_str_idx] = cur_state;
1139 /* Check OP_OPEN_SUBEXP in the initial state in case that we use them
1140 later. E.g. Processing back references. */
1141 if (BE (dfa->nbackref, 0))
1143 at_init_state = false;
1144 err = check_subexp_matching_top (mctx, &cur_state->nodes, 0);
1145 if (BE (err != REG_NOERROR, 0))
1148 if (cur_state->has_backref)
1150 err = transit_state_bkref (mctx, &cur_state->nodes);
1151 if (BE (err != REG_NOERROR, 0))
1157 /* If the RE accepts NULL string. */
1158 if (BE (cur_state->halt, 0))
1160 if (!cur_state->has_constraint
1161 || check_halt_state_context (mctx, cur_state, cur_str_idx))
1163 if (!fl_longest_match)
1167 match_last = cur_str_idx;
1173 while (!re_string_eoi (&mctx->input))
1175 re_dfastate_t *old_state = cur_state;
1176 Idx next_char_idx = re_string_cur_idx (&mctx->input) + 1;
1178 if (BE (next_char_idx >= mctx->input.bufs_len, 0)
1179 || (BE (next_char_idx >= mctx->input.valid_len, 0)
1180 && mctx->input.valid_len < mctx->input.len))
1182 err = extend_buffers (mctx);
1183 if (BE (err != REG_NOERROR, 0))
1185 assert (err == REG_ESPACE);
1190 cur_state = transit_state (&err, mctx, cur_state);
1191 if (mctx->state_log != NULL)
1192 cur_state = merge_state_with_log (&err, mctx, cur_state);
1194 if (cur_state == NULL)
1196 /* Reached the invalid state or an error. Try to recover a valid
1197 state using the state log, if available and if we have not
1198 already found a valid (even if not the longest) match. */
1199 if (BE (err != REG_NOERROR, 0))
1202 if (mctx->state_log == NULL
1203 || (match && !fl_longest_match)
1204 || (cur_state = find_recover_state (&err, mctx)) == NULL)
1208 if (BE (at_init_state, 0))
1210 if (old_state == cur_state)
1211 next_start_idx = next_char_idx;
1213 at_init_state = false;
1216 if (cur_state->halt)
1218 /* Reached a halt state.
1219 Check the halt state can satisfy the current context. */
1220 if (!cur_state->has_constraint
1221 || check_halt_state_context (mctx, cur_state,
1222 re_string_cur_idx (&mctx->input)))
1224 /* We found an appropriate halt state. */
1225 match_last = re_string_cur_idx (&mctx->input);
1228 /* We found a match, do not modify match_first below. */
1229 p_match_first = NULL;
1230 if (!fl_longest_match)
1237 *p_match_first += next_start_idx;
1242 /* Check NODE match the current context. */
1246 check_halt_node_context (const re_dfa_t *dfa, Idx node, unsigned int context)
1248 re_token_type_t type = dfa->nodes[node].type;
1249 unsigned int constraint = dfa->nodes[node].constraint;
1250 if (type != END_OF_RE)
1254 if (NOT_SATISFY_NEXT_CONSTRAINT (constraint, context))
1259 /* Check the halt state STATE match the current context.
1260 Return 0 if not match, if the node, STATE has, is a halt node and
1261 match the context, return the node. */
1265 check_halt_state_context (const re_match_context_t *mctx,
1266 const re_dfastate_t *state, Idx idx)
1269 unsigned int context;
1271 assert (state->halt);
1273 context = re_string_context_at (&mctx->input, idx, mctx->eflags);
1274 for (i = 0; i < state->nodes.nelem; ++i)
1275 if (check_halt_node_context (mctx->dfa, state->nodes.elems[i], context))
1276 return state->nodes.elems[i];
1280 /* Compute the next node to which "NFA" transit from NODE("NFA" is a NFA
1281 corresponding to the DFA).
1282 Return the destination node, and update EPS_VIA_NODES;
1283 return REG_MISSING in case of errors. */
1287 proceed_next_node (const re_match_context_t *mctx, Idx nregs, regmatch_t *regs,
1288 Idx *pidx, Idx node, re_node_set *eps_via_nodes,
1289 struct re_fail_stack_t *fs)
1291 const re_dfa_t *const dfa = mctx->dfa;
1294 if (IS_EPSILON_NODE (dfa->nodes[node].type))
1296 re_node_set *cur_nodes = &mctx->state_log[*pidx]->nodes;
1297 re_node_set *edests = &dfa->edests[node];
1299 ok = re_node_set_insert (eps_via_nodes, node);
1302 /* Pick up a valid destination, or return REG_MISSING if none
1304 for (dest_node = REG_MISSING, i = 0; i < edests->nelem; ++i)
1306 Idx candidate = edests->elems[i];
1307 if (!re_node_set_contains (cur_nodes, candidate))
1309 if (dest_node == REG_MISSING)
1310 dest_node = candidate;
1314 /* In order to avoid infinite loop like "(a*)*", return the second
1315 epsilon-transition if the first was already considered. */
1316 if (re_node_set_contains (eps_via_nodes, dest_node))
1319 /* Otherwise, push the second epsilon-transition on the fail stack. */
1321 && push_fail_stack (fs, *pidx, candidate, nregs, regs,
1325 /* We know we are going to exit. */
1334 re_token_type_t type = dfa->nodes[node].type;
1336 #ifdef RE_ENABLE_I18N
1337 if (dfa->nodes[node].accept_mb)
1338 naccepted = check_node_accept_bytes (dfa, node, &mctx->input, *pidx);
1340 #endif /* RE_ENABLE_I18N */
1341 if (type == OP_BACK_REF)
1343 Idx subexp_idx = dfa->nodes[node].opr.idx + 1;
1344 naccepted = regs[subexp_idx].rm_eo - regs[subexp_idx].rm_so;
1347 if (regs[subexp_idx].rm_so == -1 || regs[subexp_idx].rm_eo == -1)
1351 char *buf = (char *) re_string_get_buffer (&mctx->input);
1352 if (memcmp (buf + regs[subexp_idx].rm_so, buf + *pidx,
1361 ok = re_node_set_insert (eps_via_nodes, node);
1364 dest_node = dfa->edests[node].elems[0];
1365 if (re_node_set_contains (&mctx->state_log[*pidx]->nodes,
1372 || check_node_accept (mctx, dfa->nodes + node, *pidx))
1374 Idx dest_node = dfa->nexts[node];
1375 *pidx = (naccepted == 0) ? *pidx + 1 : *pidx + naccepted;
1376 if (fs && (*pidx > mctx->match_last || mctx->state_log[*pidx] == NULL
1377 || !re_node_set_contains (&mctx->state_log[*pidx]->nodes,
1380 re_node_set_empty (eps_via_nodes);
1387 static reg_errcode_t
1389 push_fail_stack (struct re_fail_stack_t *fs, Idx str_idx, Idx dest_node,
1390 Idx nregs, regmatch_t *regs, re_node_set *eps_via_nodes)
1393 Idx num = fs->num++;
1394 if (fs->num == fs->alloc)
1396 struct re_fail_stack_ent_t *new_array;
1397 new_array = realloc (fs->stack, (sizeof (struct re_fail_stack_ent_t)
1399 if (new_array == NULL)
1402 fs->stack = new_array;
1404 fs->stack[num].idx = str_idx;
1405 fs->stack[num].node = dest_node;
1406 fs->stack[num].regs = re_malloc (regmatch_t, nregs);
1407 if (fs->stack[num].regs == NULL)
1409 memcpy (fs->stack[num].regs, regs, sizeof (regmatch_t) * nregs);
1410 err = re_node_set_init_copy (&fs->stack[num].eps_via_nodes, eps_via_nodes);
1416 pop_fail_stack (struct re_fail_stack_t *fs, Idx *pidx, Idx nregs,
1417 regmatch_t *regs, re_node_set *eps_via_nodes)
1419 Idx num = --fs->num;
1420 assert (REG_VALID_INDEX (num));
1421 *pidx = fs->stack[num].idx;
1422 memcpy (regs, fs->stack[num].regs, sizeof (regmatch_t) * nregs);
1423 re_node_set_free (eps_via_nodes);
1424 re_free (fs->stack[num].regs);
1425 *eps_via_nodes = fs->stack[num].eps_via_nodes;
1426 return fs->stack[num].node;
1429 /* Set the positions where the subexpressions are starts/ends to registers
1431 Note: We assume that pmatch[0] is already set, and
1432 pmatch[i].rm_so == pmatch[i].rm_eo == -1 for 0 < i < nmatch. */
1434 static reg_errcode_t
1436 set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
1437 regmatch_t *pmatch, bool fl_backtrack)
1439 const re_dfa_t *dfa = (const re_dfa_t *) preg->buffer;
1441 re_node_set eps_via_nodes;
1442 struct re_fail_stack_t *fs;
1443 struct re_fail_stack_t fs_body = { 0, 2, NULL };
1444 regmatch_t *prev_idx_match;
1445 bool prev_idx_match_malloced = false;
1448 assert (nmatch > 1);
1449 assert (mctx->state_log != NULL);
1454 fs->stack = re_malloc (struct re_fail_stack_ent_t, fs->alloc);
1455 if (fs->stack == NULL)
1461 cur_node = dfa->init_node;
1462 re_node_set_init_empty (&eps_via_nodes);
1464 if (__libc_use_alloca (nmatch * sizeof (regmatch_t)))
1465 prev_idx_match = (regmatch_t *) alloca (nmatch * sizeof (regmatch_t));
1468 prev_idx_match = re_malloc (regmatch_t, nmatch);
1469 if (prev_idx_match == NULL)
1471 free_fail_stack_return (fs);
1474 prev_idx_match_malloced = true;
1476 memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
1478 for (idx = pmatch[0].rm_so; idx <= pmatch[0].rm_eo ;)
1480 update_regs (dfa, pmatch, prev_idx_match, cur_node, idx, nmatch);
1482 if (idx == pmatch[0].rm_eo && cur_node == mctx->last_node)
1487 for (reg_idx = 0; reg_idx < nmatch; ++reg_idx)
1488 if (pmatch[reg_idx].rm_so > -1 && pmatch[reg_idx].rm_eo == -1)
1490 if (reg_idx == nmatch)
1492 re_node_set_free (&eps_via_nodes);
1493 if (prev_idx_match_malloced)
1494 re_free (prev_idx_match);
1495 return free_fail_stack_return (fs);
1497 cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
1502 re_node_set_free (&eps_via_nodes);
1503 if (prev_idx_match_malloced)
1504 re_free (prev_idx_match);
1509 /* Proceed to next node. */
1510 cur_node = proceed_next_node (mctx, nmatch, pmatch, &idx, cur_node,
1511 &eps_via_nodes, fs);
1513 if (BE (! REG_VALID_INDEX (cur_node), 0))
1515 if (BE (cur_node == REG_ERROR, 0))
1517 re_node_set_free (&eps_via_nodes);
1518 if (prev_idx_match_malloced)
1519 re_free (prev_idx_match);
1520 free_fail_stack_return (fs);
1524 cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
1528 re_node_set_free (&eps_via_nodes);
1529 if (prev_idx_match_malloced)
1530 re_free (prev_idx_match);
1535 re_node_set_free (&eps_via_nodes);
1536 if (prev_idx_match_malloced)
1537 re_free (prev_idx_match);
1538 return free_fail_stack_return (fs);
1541 static reg_errcode_t
1543 free_fail_stack_return (struct re_fail_stack_t *fs)
1548 for (fs_idx = 0; fs_idx < fs->num; ++fs_idx)
1550 re_node_set_free (&fs->stack[fs_idx].eps_via_nodes);
1551 re_free (fs->stack[fs_idx].regs);
1553 re_free (fs->stack);
1560 update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
1561 regmatch_t *prev_idx_match, Idx cur_node, Idx cur_idx, Idx nmatch)
1563 int type = dfa->nodes[cur_node].type;
1564 if (type == OP_OPEN_SUBEXP)
1566 Idx reg_num = dfa->nodes[cur_node].opr.idx + 1;
1568 /* We are at the first node of this sub expression. */
1569 if (reg_num < nmatch)
1571 pmatch[reg_num].rm_so = cur_idx;
1572 pmatch[reg_num].rm_eo = -1;
1575 else if (type == OP_CLOSE_SUBEXP)
1577 Idx reg_num = dfa->nodes[cur_node].opr.idx + 1;
1578 if (reg_num < nmatch)
1580 /* We are at the last node of this sub expression. */
1581 if (pmatch[reg_num].rm_so < cur_idx)
1583 pmatch[reg_num].rm_eo = cur_idx;
1584 /* This is a non-empty match or we are not inside an optional
1585 subexpression. Accept this right away. */
1586 memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
1590 if (dfa->nodes[cur_node].opt_subexp
1591 && prev_idx_match[reg_num].rm_so != -1)
1592 /* We transited through an empty match for an optional
1593 subexpression, like (a?)*, and this is not the subexp's
1594 first match. Copy back the old content of the registers
1595 so that matches of an inner subexpression are undone as
1596 well, like in ((a?))*. */
1597 memcpy (pmatch, prev_idx_match, sizeof (regmatch_t) * nmatch);
1599 /* We completed a subexpression, but it may be part of
1600 an optional one, so do not update PREV_IDX_MATCH. */
1601 pmatch[reg_num].rm_eo = cur_idx;
1607 /* This function checks the STATE_LOG from the SCTX->last_str_idx to 0
1608 and sift the nodes in each states according to the following rules.
1609 Updated state_log will be wrote to STATE_LOG.
1611 Rules: We throw away the Node `a' in the STATE_LOG[STR_IDX] if...
1612 1. When STR_IDX == MATCH_LAST(the last index in the state_log):
1613 If `a' isn't the LAST_NODE and `a' can't epsilon transit to
1614 the LAST_NODE, we throw away the node `a'.
1615 2. When 0 <= STR_IDX < MATCH_LAST and `a' accepts
1616 string `s' and transit to `b':
1617 i. If 'b' isn't in the STATE_LOG[STR_IDX+strlen('s')], we throw
1619 ii. If 'b' is in the STATE_LOG[STR_IDX+strlen('s')] but 'b' is
1620 thrown away, we throw away the node `a'.
1621 3. When 0 <= STR_IDX < MATCH_LAST and 'a' epsilon transit to 'b':
1622 i. If 'b' isn't in the STATE_LOG[STR_IDX], we throw away the
1624 ii. If 'b' is in the STATE_LOG[STR_IDX] but 'b' is thrown away,
1625 we throw away the node `a'. */
1627 #define STATE_NODE_CONTAINS(state,node) \
1628 ((state) != NULL && re_node_set_contains (&(state)->nodes, node))
1630 static reg_errcode_t
1632 sift_states_backward (const re_match_context_t *mctx, re_sift_context_t *sctx)
1636 Idx str_idx = sctx->last_str_idx;
1637 re_node_set cur_dest;
1640 assert (mctx->state_log != NULL && mctx->state_log[str_idx] != NULL);
1643 /* Build sifted state_log[str_idx]. It has the nodes which can epsilon
1644 transit to the last_node and the last_node itself. */
1645 err = re_node_set_init_1 (&cur_dest, sctx->last_node);
1646 if (BE (err != REG_NOERROR, 0))
1648 err = update_cur_sifted_state (mctx, sctx, str_idx, &cur_dest);
1649 if (BE (err != REG_NOERROR, 0))
1652 /* Then check each states in the state_log. */
1655 /* Update counters. */
1656 null_cnt = (sctx->sifted_states[str_idx] == NULL) ? null_cnt + 1 : 0;
1657 if (null_cnt > mctx->max_mb_elem_len)
1659 memset (sctx->sifted_states, '\0',
1660 sizeof (re_dfastate_t *) * str_idx);
1661 re_node_set_free (&cur_dest);
1664 re_node_set_empty (&cur_dest);
1667 if (mctx->state_log[str_idx])
1669 err = build_sifted_states (mctx, sctx, str_idx, &cur_dest);
1670 if (BE (err != REG_NOERROR, 0))
1674 /* Add all the nodes which satisfy the following conditions:
1675 - It can epsilon transit to a node in CUR_DEST.
1677 And update state_log. */
1678 err = update_cur_sifted_state (mctx, sctx, str_idx, &cur_dest);
1679 if (BE (err != REG_NOERROR, 0))
1684 re_node_set_free (&cur_dest);
1688 static reg_errcode_t
1690 build_sifted_states (const re_match_context_t *mctx, re_sift_context_t *sctx,
1691 Idx str_idx, re_node_set *cur_dest)
1693 const re_dfa_t *const dfa = mctx->dfa;
1694 const re_node_set *cur_src = &mctx->state_log[str_idx]->non_eps_nodes;
1697 /* Then build the next sifted state.
1698 We build the next sifted state on `cur_dest', and update
1699 `sifted_states[str_idx]' with `cur_dest'.
1701 `cur_dest' is the sifted state from `state_log[str_idx + 1]'.
1702 `cur_src' points the node_set of the old `state_log[str_idx]'
1703 (with the epsilon nodes pre-filtered out). */
1704 for (i = 0; i < cur_src->nelem; i++)
1706 Idx prev_node = cur_src->elems[i];
1711 re_token_type_t type = dfa->nodes[prev_node].type;
1712 assert (!IS_EPSILON_NODE (type));
1714 #ifdef RE_ENABLE_I18N
1715 /* If the node may accept `multi byte'. */
1716 if (dfa->nodes[prev_node].accept_mb)
1717 naccepted = sift_states_iter_mb (mctx, sctx, prev_node,
1718 str_idx, sctx->last_str_idx);
1719 #endif /* RE_ENABLE_I18N */
1721 /* We don't check backreferences here.
1722 See update_cur_sifted_state(). */
1724 && check_node_accept (mctx, dfa->nodes + prev_node, str_idx)
1725 && STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + 1],
1726 dfa->nexts[prev_node]))
1732 if (sctx->limits.nelem)
1734 Idx to_idx = str_idx + naccepted;
1735 if (check_dst_limits (mctx, &sctx->limits,
1736 dfa->nexts[prev_node], to_idx,
1737 prev_node, str_idx))
1740 ok = re_node_set_insert (cur_dest, prev_node);
1748 /* Helper functions. */
1750 static reg_errcode_t
1752 clean_state_log_if_needed (re_match_context_t *mctx, Idx next_state_log_idx)
1754 Idx top = mctx->state_log_top;
1756 if (next_state_log_idx >= mctx->input.bufs_len
1757 || (next_state_log_idx >= mctx->input.valid_len
1758 && mctx->input.valid_len < mctx->input.len))
1761 err = extend_buffers (mctx);
1762 if (BE (err != REG_NOERROR, 0))
1766 if (top < next_state_log_idx)
1768 memset (mctx->state_log + top + 1, '\0',
1769 sizeof (re_dfastate_t *) * (next_state_log_idx - top));
1770 mctx->state_log_top = next_state_log_idx;
1775 static reg_errcode_t
1777 merge_state_array (const re_dfa_t *dfa, re_dfastate_t **dst,
1778 re_dfastate_t **src, Idx num)
1782 for (st_idx = 0; st_idx < num; ++st_idx)
1784 if (dst[st_idx] == NULL)
1785 dst[st_idx] = src[st_idx];
1786 else if (src[st_idx] != NULL)
1788 re_node_set merged_set;
1789 err = re_node_set_init_union (&merged_set, &dst[st_idx]->nodes,
1790 &src[st_idx]->nodes);
1791 if (BE (err != REG_NOERROR, 0))
1793 dst[st_idx] = re_acquire_state (&err, dfa, &merged_set);
1794 re_node_set_free (&merged_set);
1795 if (BE (err != REG_NOERROR, 0))
1802 static reg_errcode_t
1804 update_cur_sifted_state (const re_match_context_t *mctx,
1805 re_sift_context_t *sctx, Idx str_idx,
1806 re_node_set *dest_nodes)
1808 const re_dfa_t *const dfa = mctx->dfa;
1809 reg_errcode_t err = REG_NOERROR;
1810 const re_node_set *candidates;
1811 candidates = ((mctx->state_log[str_idx] == NULL) ? NULL
1812 : &mctx->state_log[str_idx]->nodes);
1814 if (dest_nodes->nelem == 0)
1815 sctx->sifted_states[str_idx] = NULL;
1820 /* At first, add the nodes which can epsilon transit to a node in
1822 err = add_epsilon_src_nodes (dfa, dest_nodes, candidates);
1823 if (BE (err != REG_NOERROR, 0))
1826 /* Then, check the limitations in the current sift_context. */
1827 if (sctx->limits.nelem)
1829 err = check_subexp_limits (dfa, dest_nodes, candidates, &sctx->limits,
1830 mctx->bkref_ents, str_idx);
1831 if (BE (err != REG_NOERROR, 0))
1836 sctx->sifted_states[str_idx] = re_acquire_state (&err, dfa, dest_nodes);
1837 if (BE (err != REG_NOERROR, 0))
1841 if (candidates && mctx->state_log[str_idx]->has_backref)
1843 err = sift_states_bkref (mctx, sctx, str_idx, candidates);
1844 if (BE (err != REG_NOERROR, 0))
1850 static reg_errcode_t
1852 add_epsilon_src_nodes (const re_dfa_t *dfa, re_node_set *dest_nodes,
1853 const re_node_set *candidates)
1855 reg_errcode_t err = REG_NOERROR;
1858 re_dfastate_t *state = re_acquire_state (&err, dfa, dest_nodes);
1859 if (BE (err != REG_NOERROR, 0))
1862 if (!state->inveclosure.alloc)
1864 err = re_node_set_alloc (&state->inveclosure, dest_nodes->nelem);
1865 if (BE (err != REG_NOERROR, 0))
1867 for (i = 0; i < dest_nodes->nelem; i++)
1868 re_node_set_merge (&state->inveclosure,
1869 dfa->inveclosures + dest_nodes->elems[i]);
1871 return re_node_set_add_intersect (dest_nodes, candidates,
1872 &state->inveclosure);
1875 static reg_errcode_t
1877 sub_epsilon_src_nodes (const re_dfa_t *dfa, Idx node, re_node_set *dest_nodes,
1878 const re_node_set *candidates)
1882 re_node_set *inv_eclosure = dfa->inveclosures + node;
1883 re_node_set except_nodes;
1884 re_node_set_init_empty (&except_nodes);
1885 for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx)
1887 Idx cur_node = inv_eclosure->elems[ecl_idx];
1888 if (cur_node == node)
1890 if (IS_EPSILON_NODE (dfa->nodes[cur_node].type))
1892 Idx edst1 = dfa->edests[cur_node].elems[0];
1893 Idx edst2 = ((dfa->edests[cur_node].nelem > 1)
1894 ? dfa->edests[cur_node].elems[1] : REG_MISSING);
1895 if ((!re_node_set_contains (inv_eclosure, edst1)
1896 && re_node_set_contains (dest_nodes, edst1))
1897 || (REG_VALID_NONZERO_INDEX (edst2)
1898 && !re_node_set_contains (inv_eclosure, edst2)
1899 && re_node_set_contains (dest_nodes, edst2)))
1901 err = re_node_set_add_intersect (&except_nodes, candidates,
1902 dfa->inveclosures + cur_node);
1903 if (BE (err != REG_NOERROR, 0))
1905 re_node_set_free (&except_nodes);
1911 for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx)
1913 Idx cur_node = inv_eclosure->elems[ecl_idx];
1914 if (!re_node_set_contains (&except_nodes, cur_node))
1916 Idx idx = re_node_set_contains (dest_nodes, cur_node) - 1;
1917 re_node_set_remove_at (dest_nodes, idx);
1920 re_node_set_free (&except_nodes);
1926 check_dst_limits (const re_match_context_t *mctx, const re_node_set *limits,
1927 Idx dst_node, Idx dst_idx, Idx src_node, Idx src_idx)
1929 const re_dfa_t *const dfa = mctx->dfa;
1930 Idx lim_idx, src_pos, dst_pos;
1932 Idx dst_bkref_idx = search_cur_bkref_entry (mctx, dst_idx);
1933 Idx src_bkref_idx = search_cur_bkref_entry (mctx, src_idx);
1934 for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx)
1937 struct re_backref_cache_entry *ent;
1938 ent = mctx->bkref_ents + limits->elems[lim_idx];
1939 subexp_idx = dfa->nodes[ent->node].opr.idx;
1941 dst_pos = check_dst_limits_calc_pos (mctx, limits->elems[lim_idx],
1942 subexp_idx, dst_node, dst_idx,
1944 src_pos = check_dst_limits_calc_pos (mctx, limits->elems[lim_idx],
1945 subexp_idx, src_node, src_idx,
1949 <src> <dst> ( <subexp> )
1950 ( <subexp> ) <src> <dst>
1951 ( <subexp1> <src> <subexp2> <dst> <subexp3> ) */
1952 if (src_pos == dst_pos)
1953 continue; /* This is unrelated limitation. */
1962 check_dst_limits_calc_pos_1 (const re_match_context_t *mctx, int boundaries,
1963 Idx subexp_idx, Idx from_node, Idx bkref_idx)
1965 const re_dfa_t *const dfa = mctx->dfa;
1966 const re_node_set *eclosures = dfa->eclosures + from_node;
1969 /* Else, we are on the boundary: examine the nodes on the epsilon
1971 for (node_idx = 0; node_idx < eclosures->nelem; ++node_idx)
1973 Idx node = eclosures->elems[node_idx];
1974 switch (dfa->nodes[node].type)
1977 if (bkref_idx != REG_MISSING)
1979 struct re_backref_cache_entry *ent = mctx->bkref_ents + bkref_idx;
1985 if (ent->node != node)
1988 if (subexp_idx < BITSET_WORD_BITS
1989 && !(ent->eps_reachable_subexps_map
1990 & ((bitset_word_t) 1 << subexp_idx)))
1993 /* Recurse trying to reach the OP_OPEN_SUBEXP and
1994 OP_CLOSE_SUBEXP cases below. But, if the
1995 destination node is the same node as the source
1996 node, don't recurse because it would cause an
1997 infinite loop: a regex that exhibits this behavior
1999 dst = dfa->edests[node].elems[0];
2000 if (dst == from_node)
2004 else /* if (boundaries & 2) */
2009 check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx,
2011 if (cpos == -1 /* && (boundaries & 1) */)
2013 if (cpos == 0 && (boundaries & 2))
2016 if (subexp_idx < BITSET_WORD_BITS)
2017 ent->eps_reachable_subexps_map
2018 &= ~((bitset_word_t) 1 << subexp_idx);
2020 while (ent++->more);
2024 case OP_OPEN_SUBEXP:
2025 if ((boundaries & 1) && subexp_idx == dfa->nodes[node].opr.idx)
2029 case OP_CLOSE_SUBEXP:
2030 if ((boundaries & 2) && subexp_idx == dfa->nodes[node].opr.idx)
2039 return (boundaries & 2) ? 1 : 0;
2044 check_dst_limits_calc_pos (const re_match_context_t *mctx, Idx limit,
2045 Idx subexp_idx, Idx from_node, Idx str_idx,
2048 struct re_backref_cache_entry *lim = mctx->bkref_ents + limit;
2051 /* If we are outside the range of the subexpression, return -1 or 1. */
2052 if (str_idx < lim->subexp_from)
2055 if (lim->subexp_to < str_idx)
2058 /* If we are within the subexpression, return 0. */
2059 boundaries = (str_idx == lim->subexp_from);
2060 boundaries |= (str_idx == lim->subexp_to) << 1;
2061 if (boundaries == 0)
2064 /* Else, examine epsilon closure. */
2065 return check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx,
2066 from_node, bkref_idx);
2069 /* Check the limitations of sub expressions LIMITS, and remove the nodes
2070 which are against limitations from DEST_NODES. */
2072 static reg_errcode_t
2074 check_subexp_limits (const re_dfa_t *dfa, re_node_set *dest_nodes,
2075 const re_node_set *candidates, re_node_set *limits,
2076 struct re_backref_cache_entry *bkref_ents, Idx str_idx)
2079 Idx node_idx, lim_idx;
2081 for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx)
2084 struct re_backref_cache_entry *ent;
2085 ent = bkref_ents + limits->elems[lim_idx];
2087 if (str_idx <= ent->subexp_from || ent->str_idx < str_idx)
2088 continue; /* This is unrelated limitation. */
2090 subexp_idx = dfa->nodes[ent->node].opr.idx;
2091 if (ent->subexp_to == str_idx)
2093 Idx ops_node = REG_MISSING;
2094 Idx cls_node = REG_MISSING;
2095 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2097 Idx node = dest_nodes->elems[node_idx];
2098 re_token_type_t type = dfa->nodes[node].type;
2099 if (type == OP_OPEN_SUBEXP
2100 && subexp_idx == dfa->nodes[node].opr.idx)
2102 else if (type == OP_CLOSE_SUBEXP
2103 && subexp_idx == dfa->nodes[node].opr.idx)
2107 /* Check the limitation of the open subexpression. */
2108 /* Note that (ent->subexp_to = str_idx != ent->subexp_from). */
2109 if (REG_VALID_INDEX (ops_node))
2111 err = sub_epsilon_src_nodes (dfa, ops_node, dest_nodes,
2113 if (BE (err != REG_NOERROR, 0))
2117 /* Check the limitation of the close subexpression. */
2118 if (REG_VALID_INDEX (cls_node))
2119 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2121 Idx node = dest_nodes->elems[node_idx];
2122 if (!re_node_set_contains (dfa->inveclosures + node,
2124 && !re_node_set_contains (dfa->eclosures + node,
2127 /* It is against this limitation.
2128 Remove it form the current sifted state. */
2129 err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2131 if (BE (err != REG_NOERROR, 0))
2137 else /* (ent->subexp_to != str_idx) */
2139 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2141 Idx node = dest_nodes->elems[node_idx];
2142 re_token_type_t type = dfa->nodes[node].type;
2143 if (type == OP_CLOSE_SUBEXP || type == OP_OPEN_SUBEXP)
2145 if (subexp_idx != dfa->nodes[node].opr.idx)
2147 /* It is against this limitation.
2148 Remove it form the current sifted state. */
2149 err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2151 if (BE (err != REG_NOERROR, 0))
2160 static reg_errcode_t
2162 sift_states_bkref (const re_match_context_t *mctx, re_sift_context_t *sctx,
2163 Idx str_idx, const re_node_set *candidates)
2165 const re_dfa_t *const dfa = mctx->dfa;
2168 re_sift_context_t local_sctx;
2169 Idx first_idx = search_cur_bkref_entry (mctx, str_idx);
2171 if (first_idx == REG_MISSING)
2174 local_sctx.sifted_states = NULL; /* Mark that it hasn't been initialized. */
2176 for (node_idx = 0; node_idx < candidates->nelem; ++node_idx)
2179 re_token_type_t type;
2180 struct re_backref_cache_entry *entry;
2181 node = candidates->elems[node_idx];
2182 type = dfa->nodes[node].type;
2183 /* Avoid infinite loop for the REs like "()\1+". */
2184 if (node == sctx->last_node && str_idx == sctx->last_str_idx)
2186 if (type != OP_BACK_REF)
2189 entry = mctx->bkref_ents + first_idx;
2190 enabled_idx = first_idx;
2197 re_dfastate_t *cur_state;
2199 if (entry->node != node)
2201 subexp_len = entry->subexp_to - entry->subexp_from;
2202 to_idx = str_idx + subexp_len;
2203 dst_node = (subexp_len ? dfa->nexts[node]
2204 : dfa->edests[node].elems[0]);
2206 if (to_idx > sctx->last_str_idx
2207 || sctx->sifted_states[to_idx] == NULL
2208 || !STATE_NODE_CONTAINS (sctx->sifted_states[to_idx], dst_node)
2209 || check_dst_limits (mctx, &sctx->limits, node,
2210 str_idx, dst_node, to_idx))
2213 if (local_sctx.sifted_states == NULL)
2216 err = re_node_set_init_copy (&local_sctx.limits, &sctx->limits);
2217 if (BE (err != REG_NOERROR, 0))
2220 local_sctx.last_node = node;
2221 local_sctx.last_str_idx = str_idx;
2222 ok = re_node_set_insert (&local_sctx.limits, enabled_idx);
2228 cur_state = local_sctx.sifted_states[str_idx];
2229 err = sift_states_backward (mctx, &local_sctx);
2230 if (BE (err != REG_NOERROR, 0))
2232 if (sctx->limited_states != NULL)
2234 err = merge_state_array (dfa, sctx->limited_states,
2235 local_sctx.sifted_states,
2237 if (BE (err != REG_NOERROR, 0))
2240 local_sctx.sifted_states[str_idx] = cur_state;
2241 re_node_set_remove (&local_sctx.limits, enabled_idx);
2243 /* mctx->bkref_ents may have changed, reload the pointer. */
2244 entry = mctx->bkref_ents + enabled_idx;
2246 while (enabled_idx++, entry++->more);
2250 if (local_sctx.sifted_states != NULL)
2252 re_node_set_free (&local_sctx.limits);
2259 #ifdef RE_ENABLE_I18N
2262 sift_states_iter_mb (const re_match_context_t *mctx, re_sift_context_t *sctx,
2263 Idx node_idx, Idx str_idx, Idx max_str_idx)
2265 const re_dfa_t *const dfa = mctx->dfa;
2267 /* Check the node can accept `multi byte'. */
2268 naccepted = check_node_accept_bytes (dfa, node_idx, &mctx->input, str_idx);
2269 if (naccepted > 0 && str_idx + naccepted <= max_str_idx &&
2270 !STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + naccepted],
2271 dfa->nexts[node_idx]))
2272 /* The node can't accept the `multi byte', or the
2273 destination was already thrown away, then the node
2274 could't accept the current input `multi byte'. */
2276 /* Otherwise, it is sure that the node could accept
2277 `naccepted' bytes input. */
2280 #endif /* RE_ENABLE_I18N */
2283 /* Functions for state transition. */
2285 /* Return the next state to which the current state STATE will transit by
2286 accepting the current input byte, and update STATE_LOG if necessary.
2287 If STATE can accept a multibyte char/collating element/back reference
2288 update the destination of STATE_LOG. */
2290 static re_dfastate_t *
2292 transit_state (reg_errcode_t *err, re_match_context_t *mctx,
2293 re_dfastate_t *state)
2295 re_dfastate_t **trtable;
2298 #ifdef RE_ENABLE_I18N
2299 /* If the current state can accept multibyte. */
2300 if (BE (state->accept_mb, 0))
2302 *err = transit_state_mb (mctx, state);
2303 if (BE (*err != REG_NOERROR, 0))
2306 #endif /* RE_ENABLE_I18N */
2308 /* Then decide the next state with the single byte. */
2311 /* don't use transition table */
2312 return transit_state_sb (err, mctx, state);
2315 /* Use transition table */
2316 ch = re_string_fetch_byte (&mctx->input);
2319 trtable = state->trtable;
2320 if (BE (trtable != NULL, 1))
2323 trtable = state->word_trtable;
2324 if (BE (trtable != NULL, 1))
2326 unsigned int context;
2328 = re_string_context_at (&mctx->input,
2329 re_string_cur_idx (&mctx->input) - 1,
2331 if (IS_WORD_CONTEXT (context))
2332 return trtable[ch + SBC_MAX];
2337 if (!build_trtable (mctx->dfa, state))
2343 /* Retry, we now have a transition table. */
2347 /* Update the state_log if we need */
2348 static re_dfastate_t *
2350 merge_state_with_log (reg_errcode_t *err, re_match_context_t *mctx,
2351 re_dfastate_t *next_state)
2353 const re_dfa_t *const dfa = mctx->dfa;
2354 Idx cur_idx = re_string_cur_idx (&mctx->input);
2356 if (cur_idx > mctx->state_log_top)
2358 mctx->state_log[cur_idx] = next_state;
2359 mctx->state_log_top = cur_idx;
2361 else if (mctx->state_log[cur_idx] == 0)
2363 mctx->state_log[cur_idx] = next_state;
2367 re_dfastate_t *pstate;
2368 unsigned int context;
2369 re_node_set next_nodes, *log_nodes, *table_nodes = NULL;
2370 /* If (state_log[cur_idx] != 0), it implies that cur_idx is
2371 the destination of a multibyte char/collating element/
2372 back reference. Then the next state is the union set of
2373 these destinations and the results of the transition table. */
2374 pstate = mctx->state_log[cur_idx];
2375 log_nodes = pstate->entrance_nodes;
2376 if (next_state != NULL)
2378 table_nodes = next_state->entrance_nodes;
2379 *err = re_node_set_init_union (&next_nodes, table_nodes,
2381 if (BE (*err != REG_NOERROR, 0))
2385 next_nodes = *log_nodes;
2386 /* Note: We already add the nodes of the initial state,
2387 then we don't need to add them here. */
2389 context = re_string_context_at (&mctx->input,
2390 re_string_cur_idx (&mctx->input) - 1,
2392 next_state = mctx->state_log[cur_idx]
2393 = re_acquire_state_context (err, dfa, &next_nodes, context);
2394 /* We don't need to check errors here, since the return value of
2395 this function is next_state and ERR is already set. */
2397 if (table_nodes != NULL)
2398 re_node_set_free (&next_nodes);
2401 if (BE (dfa->nbackref, 0) && next_state != NULL)
2403 /* Check OP_OPEN_SUBEXP in the current state in case that we use them
2404 later. We must check them here, since the back references in the
2405 next state might use them. */
2406 *err = check_subexp_matching_top (mctx, &next_state->nodes,
2408 if (BE (*err != REG_NOERROR, 0))
2411 /* If the next state has back references. */
2412 if (next_state->has_backref)
2414 *err = transit_state_bkref (mctx, &next_state->nodes);
2415 if (BE (*err != REG_NOERROR, 0))
2417 next_state = mctx->state_log[cur_idx];
2424 /* Skip bytes in the input that correspond to part of a
2425 multi-byte match, then look in the log for a state
2426 from which to restart matching. */
2427 static re_dfastate_t *
2429 find_recover_state (reg_errcode_t *err, re_match_context_t *mctx)
2431 re_dfastate_t *cur_state;
2434 Idx max = mctx->state_log_top;
2435 Idx cur_str_idx = re_string_cur_idx (&mctx->input);
2439 if (++cur_str_idx > max)
2441 re_string_skip_bytes (&mctx->input, 1);
2443 while (mctx->state_log[cur_str_idx] == NULL);
2445 cur_state = merge_state_with_log (err, mctx, NULL);
2447 while (*err == REG_NOERROR && cur_state == NULL);
2451 /* Helper functions for transit_state. */
2453 /* From the node set CUR_NODES, pick up the nodes whose types are
2454 OP_OPEN_SUBEXP and which have corresponding back references in the regular
2455 expression. And register them to use them later for evaluating the
2456 correspoding back references. */
2458 static reg_errcode_t
2460 check_subexp_matching_top (re_match_context_t *mctx, re_node_set *cur_nodes,
2463 const re_dfa_t *const dfa = mctx->dfa;
2467 /* TODO: This isn't efficient.
2468 Because there might be more than one nodes whose types are
2469 OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
2472 for (node_idx = 0; node_idx < cur_nodes->nelem; ++node_idx)
2474 Idx node = cur_nodes->elems[node_idx];
2475 if (dfa->nodes[node].type == OP_OPEN_SUBEXP
2476 && dfa->nodes[node].opr.idx < BITSET_WORD_BITS
2477 && (dfa->used_bkref_map
2478 & ((bitset_word_t) 1 << dfa->nodes[node].opr.idx)))
2480 err = match_ctx_add_subtop (mctx, node, str_idx);
2481 if (BE (err != REG_NOERROR, 0))
2489 /* Return the next state to which the current state STATE will transit by
2490 accepting the current input byte. */
2492 static re_dfastate_t *
2493 transit_state_sb (reg_errcode_t *err, re_match_context_t *mctx,
2494 re_dfastate_t *state)
2496 const re_dfa_t *const dfa = mctx->dfa;
2497 re_node_set next_nodes;
2498 re_dfastate_t *next_state;
2499 Idx node_cnt, cur_str_idx = re_string_cur_idx (&mctx->input);
2500 unsigned int context;
2502 *err = re_node_set_alloc (&next_nodes, state->nodes.nelem + 1);
2503 if (BE (*err != REG_NOERROR, 0))
2505 for (node_cnt = 0; node_cnt < state->nodes.nelem; ++node_cnt)
2507 Idx cur_node = state->nodes.elems[node_cnt];
2508 if (check_node_accept (mctx, dfa->nodes + cur_node, cur_str_idx))
2510 *err = re_node_set_merge (&next_nodes,
2511 dfa->eclosures + dfa->nexts[cur_node]);
2512 if (BE (*err != REG_NOERROR, 0))
2514 re_node_set_free (&next_nodes);
2519 context = re_string_context_at (&mctx->input, cur_str_idx, mctx->eflags);
2520 next_state = re_acquire_state_context (err, dfa, &next_nodes, context);
2521 /* We don't need to check errors here, since the return value of
2522 this function is next_state and ERR is already set. */
2524 re_node_set_free (&next_nodes);
2525 re_string_skip_bytes (&mctx->input, 1);
2530 #ifdef RE_ENABLE_I18N
2531 static reg_errcode_t
2533 transit_state_mb (re_match_context_t *mctx, re_dfastate_t *pstate)
2535 const re_dfa_t *const dfa = mctx->dfa;
2539 for (i = 0; i < pstate->nodes.nelem; ++i)
2541 re_node_set dest_nodes, *new_nodes;
2542 Idx cur_node_idx = pstate->nodes.elems[i];
2545 unsigned int context;
2546 re_dfastate_t *dest_state;
2548 if (!dfa->nodes[cur_node_idx].accept_mb)
2551 if (dfa->nodes[cur_node_idx].constraint)
2553 context = re_string_context_at (&mctx->input,
2554 re_string_cur_idx (&mctx->input),
2556 if (NOT_SATISFY_NEXT_CONSTRAINT (dfa->nodes[cur_node_idx].constraint,
2561 /* How many bytes the node can accept? */
2562 naccepted = check_node_accept_bytes (dfa, cur_node_idx, &mctx->input,
2563 re_string_cur_idx (&mctx->input));
2567 /* The node can accepts `naccepted' bytes. */
2568 dest_idx = re_string_cur_idx (&mctx->input) + naccepted;
2569 mctx->max_mb_elem_len = ((mctx->max_mb_elem_len < naccepted) ? naccepted
2570 : mctx->max_mb_elem_len);
2571 err = clean_state_log_if_needed (mctx, dest_idx);
2572 if (BE (err != REG_NOERROR, 0))
2575 assert (dfa->nexts[cur_node_idx] != REG_MISSING);
2577 new_nodes = dfa->eclosures + dfa->nexts[cur_node_idx];
2579 dest_state = mctx->state_log[dest_idx];
2580 if (dest_state == NULL)
2581 dest_nodes = *new_nodes;
2584 err = re_node_set_init_union (&dest_nodes,
2585 dest_state->entrance_nodes, new_nodes);
2586 if (BE (err != REG_NOERROR, 0))
2589 context = re_string_context_at (&mctx->input, dest_idx - 1,
2591 mctx->state_log[dest_idx]
2592 = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2593 if (dest_state != NULL)
2594 re_node_set_free (&dest_nodes);
2595 if (BE (mctx->state_log[dest_idx] == NULL && err != REG_NOERROR, 0))
2600 #endif /* RE_ENABLE_I18N */
2602 static reg_errcode_t
2604 transit_state_bkref (re_match_context_t *mctx, const re_node_set *nodes)
2606 const re_dfa_t *const dfa = mctx->dfa;
2609 Idx cur_str_idx = re_string_cur_idx (&mctx->input);
2611 for (i = 0; i < nodes->nelem; ++i)
2613 Idx dest_str_idx, prev_nelem, bkc_idx;
2614 Idx node_idx = nodes->elems[i];
2615 unsigned int context;
2616 const re_token_t *node = dfa->nodes + node_idx;
2617 re_node_set *new_dest_nodes;
2619 /* Check whether `node' is a backreference or not. */
2620 if (node->type != OP_BACK_REF)
2623 if (node->constraint)
2625 context = re_string_context_at (&mctx->input, cur_str_idx,
2627 if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
2631 /* `node' is a backreference.
2632 Check the substring which the substring matched. */
2633 bkc_idx = mctx->nbkref_ents;
2634 err = get_subexp (mctx, node_idx, cur_str_idx);
2635 if (BE (err != REG_NOERROR, 0))
2638 /* And add the epsilon closures (which is `new_dest_nodes') of
2639 the backreference to appropriate state_log. */
2641 assert (dfa->nexts[node_idx] != REG_MISSING);
2643 for (; bkc_idx < mctx->nbkref_ents; ++bkc_idx)
2646 re_dfastate_t *dest_state;
2647 struct re_backref_cache_entry *bkref_ent;
2648 bkref_ent = mctx->bkref_ents + bkc_idx;
2649 if (bkref_ent->node != node_idx || bkref_ent->str_idx != cur_str_idx)
2651 subexp_len = bkref_ent->subexp_to - bkref_ent->subexp_from;
2652 new_dest_nodes = (subexp_len == 0
2653 ? dfa->eclosures + dfa->edests[node_idx].elems[0]
2654 : dfa->eclosures + dfa->nexts[node_idx]);
2655 dest_str_idx = (cur_str_idx + bkref_ent->subexp_to
2656 - bkref_ent->subexp_from);
2657 context = re_string_context_at (&mctx->input, dest_str_idx - 1,
2659 dest_state = mctx->state_log[dest_str_idx];
2660 prev_nelem = ((mctx->state_log[cur_str_idx] == NULL) ? 0
2661 : mctx->state_log[cur_str_idx]->nodes.nelem);
2662 /* Add `new_dest_node' to state_log. */
2663 if (dest_state == NULL)
2665 mctx->state_log[dest_str_idx]
2666 = re_acquire_state_context (&err, dfa, new_dest_nodes,
2668 if (BE (mctx->state_log[dest_str_idx] == NULL
2669 && err != REG_NOERROR, 0))
2674 re_node_set dest_nodes;
2675 err = re_node_set_init_union (&dest_nodes,
2676 dest_state->entrance_nodes,
2678 if (BE (err != REG_NOERROR, 0))
2680 re_node_set_free (&dest_nodes);
2683 mctx->state_log[dest_str_idx]
2684 = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2685 re_node_set_free (&dest_nodes);
2686 if (BE (mctx->state_log[dest_str_idx] == NULL
2687 && err != REG_NOERROR, 0))
2690 /* We need to check recursively if the backreference can epsilon
2693 && mctx->state_log[cur_str_idx]->nodes.nelem > prev_nelem)
2695 err = check_subexp_matching_top (mctx, new_dest_nodes,
2697 if (BE (err != REG_NOERROR, 0))
2699 err = transit_state_bkref (mctx, new_dest_nodes);
2700 if (BE (err != REG_NOERROR, 0))
2710 /* Enumerate all the candidates which the backreference BKREF_NODE can match
2711 at BKREF_STR_IDX, and register them by match_ctx_add_entry().
2712 Note that we might collect inappropriate candidates here.
2713 However, the cost of checking them strictly here is too high, then we
2714 delay these checking for prune_impossible_nodes(). */
2716 static reg_errcode_t
2718 get_subexp (re_match_context_t *mctx, Idx bkref_node, Idx bkref_str_idx)
2720 const re_dfa_t *const dfa = mctx->dfa;
2721 Idx subexp_num, sub_top_idx;
2722 const char *buf = (const char *) re_string_get_buffer (&mctx->input);
2723 /* Return if we have already checked BKREF_NODE at BKREF_STR_IDX. */
2724 Idx cache_idx = search_cur_bkref_entry (mctx, bkref_str_idx);
2725 if (cache_idx != REG_MISSING)
2727 const struct re_backref_cache_entry *entry
2728 = mctx->bkref_ents + cache_idx;
2730 if (entry->node == bkref_node)
2731 return REG_NOERROR; /* We already checked it. */
2732 while (entry++->more);
2735 subexp_num = dfa->nodes[bkref_node].opr.idx;
2737 /* For each sub expression */
2738 for (sub_top_idx = 0; sub_top_idx < mctx->nsub_tops; ++sub_top_idx)
2741 re_sub_match_top_t *sub_top = mctx->sub_tops[sub_top_idx];
2742 re_sub_match_last_t *sub_last;
2743 Idx sub_last_idx, sl_str, bkref_str_off;
2745 if (dfa->nodes[sub_top->node].opr.idx != subexp_num)
2746 continue; /* It isn't related. */
2748 sl_str = sub_top->str_idx;
2749 bkref_str_off = bkref_str_idx;
2750 /* At first, check the last node of sub expressions we already
2752 for (sub_last_idx = 0; sub_last_idx < sub_top->nlasts; ++sub_last_idx)
2754 regoff_t sl_str_diff;
2755 sub_last = sub_top->lasts[sub_last_idx];
2756 sl_str_diff = sub_last->str_idx - sl_str;
2757 /* The matched string by the sub expression match with the substring
2758 at the back reference? */
2759 if (sl_str_diff > 0)
2761 if (BE (bkref_str_off + sl_str_diff > mctx->input.valid_len, 0))
2763 /* Not enough chars for a successful match. */
2764 if (bkref_str_off + sl_str_diff > mctx->input.len)
2767 err = clean_state_log_if_needed (mctx,
2770 if (BE (err != REG_NOERROR, 0))
2772 buf = (const char *) re_string_get_buffer (&mctx->input);
2774 if (memcmp (buf + bkref_str_off, buf + sl_str, sl_str_diff) != 0)
2775 /* We don't need to search this sub expression any more. */
2778 bkref_str_off += sl_str_diff;
2779 sl_str += sl_str_diff;
2780 err = get_subexp_sub (mctx, sub_top, sub_last, bkref_node,
2783 /* Reload buf, since the preceding call might have reallocated
2785 buf = (const char *) re_string_get_buffer (&mctx->input);
2787 if (err == REG_NOMATCH)
2789 if (BE (err != REG_NOERROR, 0))
2793 if (sub_last_idx < sub_top->nlasts)
2795 if (sub_last_idx > 0)
2797 /* Then, search for the other last nodes of the sub expression. */
2798 for (; sl_str <= bkref_str_idx; ++sl_str)
2801 regoff_t sl_str_off;
2802 const re_node_set *nodes;
2803 sl_str_off = sl_str - sub_top->str_idx;
2804 /* The matched string by the sub expression match with the substring
2805 at the back reference? */
2808 if (BE (bkref_str_off >= mctx->input.valid_len, 0))
2810 /* If we are at the end of the input, we cannot match. */
2811 if (bkref_str_off >= mctx->input.len)
2814 err = extend_buffers (mctx);
2815 if (BE (err != REG_NOERROR, 0))
2818 buf = (const char *) re_string_get_buffer (&mctx->input);
2820 if (buf [bkref_str_off++] != buf[sl_str - 1])
2821 break; /* We don't need to search this sub expression
2824 if (mctx->state_log[sl_str] == NULL)
2826 /* Does this state have a ')' of the sub expression? */
2827 nodes = &mctx->state_log[sl_str]->nodes;
2828 cls_node = find_subexp_node (dfa, nodes, subexp_num,
2830 if (cls_node == REG_MISSING)
2832 if (sub_top->path == NULL)
2834 sub_top->path = calloc (sizeof (state_array_t),
2835 sl_str - sub_top->str_idx + 1);
2836 if (sub_top->path == NULL)
2839 /* Can the OP_OPEN_SUBEXP node arrive the OP_CLOSE_SUBEXP node
2840 in the current context? */
2841 err = check_arrival (mctx, sub_top->path, sub_top->node,
2842 sub_top->str_idx, cls_node, sl_str,
2844 if (err == REG_NOMATCH)
2846 if (BE (err != REG_NOERROR, 0))
2848 sub_last = match_ctx_add_sublast (sub_top, cls_node, sl_str);
2849 if (BE (sub_last == NULL, 0))
2851 err = get_subexp_sub (mctx, sub_top, sub_last, bkref_node,
2853 if (err == REG_NOMATCH)
2860 /* Helper functions for get_subexp(). */
2862 /* Check SUB_LAST can arrive to the back reference BKREF_NODE at BKREF_STR.
2863 If it can arrive, register the sub expression expressed with SUB_TOP
2866 static reg_errcode_t
2868 get_subexp_sub (re_match_context_t *mctx, const re_sub_match_top_t *sub_top,
2869 re_sub_match_last_t *sub_last, Idx bkref_node, Idx bkref_str)
2873 /* Can the subexpression arrive the back reference? */
2874 err = check_arrival (mctx, &sub_last->path, sub_last->node,
2875 sub_last->str_idx, bkref_node, bkref_str,
2877 if (err != REG_NOERROR)
2879 err = match_ctx_add_entry (mctx, bkref_node, bkref_str, sub_top->str_idx,
2881 if (BE (err != REG_NOERROR, 0))
2883 to_idx = bkref_str + sub_last->str_idx - sub_top->str_idx;
2884 return clean_state_log_if_needed (mctx, to_idx);
2887 /* Find the first node which is '(' or ')' and whose index is SUBEXP_IDX.
2888 Search '(' if FL_OPEN, or search ')' otherwise.
2889 TODO: This function isn't efficient...
2890 Because there might be more than one nodes whose types are
2891 OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
2897 find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
2898 Idx subexp_idx, int type)
2901 for (cls_idx = 0; cls_idx < nodes->nelem; ++cls_idx)
2903 Idx cls_node = nodes->elems[cls_idx];
2904 const re_token_t *node = dfa->nodes + cls_node;
2905 if (node->type == type
2906 && node->opr.idx == subexp_idx)
2912 /* Check whether the node TOP_NODE at TOP_STR can arrive to the node
2913 LAST_NODE at LAST_STR. We record the path onto PATH since it will be
2915 Return REG_NOERROR if it can arrive, or REG_NOMATCH otherwise. */
2917 static reg_errcode_t
2919 check_arrival (re_match_context_t *mctx, state_array_t *path, Idx top_node,
2920 Idx top_str, Idx last_node, Idx last_str, int type)
2922 const re_dfa_t *const dfa = mctx->dfa;
2923 reg_errcode_t err = REG_NOERROR;
2924 Idx subexp_num, backup_cur_idx, str_idx, null_cnt;
2925 re_dfastate_t *cur_state = NULL;
2926 re_node_set *cur_nodes, next_nodes;
2927 re_dfastate_t **backup_state_log;
2928 unsigned int context;
2930 subexp_num = dfa->nodes[top_node].opr.idx;
2931 /* Extend the buffer if we need. */
2932 if (BE (path->alloc < last_str + mctx->max_mb_elem_len + 1, 0))
2934 re_dfastate_t **new_array;
2935 Idx old_alloc = path->alloc;
2936 Idx new_alloc = old_alloc + last_str + mctx->max_mb_elem_len + 1;
2937 if (BE (new_alloc < old_alloc, 0)
2938 || BE (SIZE_MAX / sizeof (re_dfastate_t *) < new_alloc, 0))
2940 new_array = re_realloc (path->array, re_dfastate_t *, new_alloc);
2941 if (BE (new_array == NULL, 0))
2943 path->array = new_array;
2944 path->alloc = new_alloc;
2945 memset (new_array + old_alloc, '\0',
2946 sizeof (re_dfastate_t *) * (path->alloc - old_alloc));
2949 str_idx = path->next_idx ? path->next_idx : top_str;
2951 /* Temporary modify MCTX. */
2952 backup_state_log = mctx->state_log;
2953 backup_cur_idx = mctx->input.cur_idx;
2954 mctx->state_log = path->array;
2955 mctx->input.cur_idx = str_idx;
2957 /* Setup initial node set. */
2958 context = re_string_context_at (&mctx->input, str_idx - 1, mctx->eflags);
2959 if (str_idx == top_str)
2961 err = re_node_set_init_1 (&next_nodes, top_node);
2962 if (BE (err != REG_NOERROR, 0))
2964 err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
2965 if (BE (err != REG_NOERROR, 0))
2967 re_node_set_free (&next_nodes);
2973 cur_state = mctx->state_log[str_idx];
2974 if (cur_state && cur_state->has_backref)
2976 err = re_node_set_init_copy (&next_nodes, &cur_state->nodes);
2977 if (BE (err != REG_NOERROR, 0))
2981 re_node_set_init_empty (&next_nodes);
2983 if (str_idx == top_str || (cur_state && cur_state->has_backref))
2985 if (next_nodes.nelem)
2987 err = expand_bkref_cache (mctx, &next_nodes, str_idx,
2989 if (BE (err != REG_NOERROR, 0))
2991 re_node_set_free (&next_nodes);
2995 cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
2996 if (BE (cur_state == NULL && err != REG_NOERROR, 0))
2998 re_node_set_free (&next_nodes);
3001 mctx->state_log[str_idx] = cur_state;
3004 for (null_cnt = 0; str_idx < last_str && null_cnt <= mctx->max_mb_elem_len;)
3006 re_node_set_empty (&next_nodes);
3007 if (mctx->state_log[str_idx + 1])
3009 err = re_node_set_merge (&next_nodes,
3010 &mctx->state_log[str_idx + 1]->nodes);
3011 if (BE (err != REG_NOERROR, 0))
3013 re_node_set_free (&next_nodes);
3019 err = check_arrival_add_next_nodes (mctx, str_idx,
3020 &cur_state->non_eps_nodes,
3022 if (BE (err != REG_NOERROR, 0))
3024 re_node_set_free (&next_nodes);
3029 if (next_nodes.nelem)
3031 err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
3032 if (BE (err != REG_NOERROR, 0))
3034 re_node_set_free (&next_nodes);
3037 err = expand_bkref_cache (mctx, &next_nodes, str_idx,
3039 if (BE (err != REG_NOERROR, 0))
3041 re_node_set_free (&next_nodes);
3045 context = re_string_context_at (&mctx->input, str_idx - 1, mctx->eflags);
3046 cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
3047 if (BE (cur_state == NULL && err != REG_NOERROR, 0))
3049 re_node_set_free (&next_nodes);
3052 mctx->state_log[str_idx] = cur_state;
3053 null_cnt = cur_state == NULL ? null_cnt + 1 : 0;
3055 re_node_set_free (&next_nodes);
3056 cur_nodes = (mctx->state_log[last_str] == NULL ? NULL
3057 : &mctx->state_log[last_str]->nodes);
3058 path->next_idx = str_idx;
3061 mctx->state_log = backup_state_log;
3062 mctx->input.cur_idx = backup_cur_idx;
3064 /* Then check the current node set has the node LAST_NODE. */
3065 if (cur_nodes != NULL && re_node_set_contains (cur_nodes, last_node))
3071 /* Helper functions for check_arrival. */
3073 /* Calculate the destination nodes of CUR_NODES at STR_IDX, and append them
3075 TODO: This function is similar to the functions transit_state*(),
3076 however this function has many additional works.
3077 Can't we unify them? */
3079 static reg_errcode_t
3081 check_arrival_add_next_nodes (re_match_context_t *mctx, Idx str_idx,
3082 re_node_set *cur_nodes, re_node_set *next_nodes)
3084 const re_dfa_t *const dfa = mctx->dfa;
3087 #ifdef RE_ENABLE_I18N
3088 reg_errcode_t err = REG_NOERROR;
3090 re_node_set union_set;
3091 re_node_set_init_empty (&union_set);
3092 for (cur_idx = 0; cur_idx < cur_nodes->nelem; ++cur_idx)
3095 Idx cur_node = cur_nodes->elems[cur_idx];
3097 re_token_type_t type = dfa->nodes[cur_node].type;
3098 assert (!IS_EPSILON_NODE (type));
3100 #ifdef RE_ENABLE_I18N
3101 /* If the node may accept `multi byte'. */
3102 if (dfa->nodes[cur_node].accept_mb)
3104 naccepted = check_node_accept_bytes (dfa, cur_node, &mctx->input,
3108 re_dfastate_t *dest_state;
3109 Idx next_node = dfa->nexts[cur_node];
3110 Idx next_idx = str_idx + naccepted;
3111 dest_state = mctx->state_log[next_idx];
3112 re_node_set_empty (&union_set);
3115 err = re_node_set_merge (&union_set, &dest_state->nodes);
3116 if (BE (err != REG_NOERROR, 0))
3118 re_node_set_free (&union_set);
3122 ok = re_node_set_insert (&union_set, next_node);
3125 re_node_set_free (&union_set);
3128 mctx->state_log[next_idx] = re_acquire_state (&err, dfa,
3130 if (BE (mctx->state_log[next_idx] == NULL
3131 && err != REG_NOERROR, 0))
3133 re_node_set_free (&union_set);
3138 #endif /* RE_ENABLE_I18N */
3140 || check_node_accept (mctx, dfa->nodes + cur_node, str_idx))
3142 ok = re_node_set_insert (next_nodes, dfa->nexts[cur_node]);
3145 re_node_set_free (&union_set);
3150 re_node_set_free (&union_set);
3154 /* For all the nodes in CUR_NODES, add the epsilon closures of them to
3155 CUR_NODES, however exclude the nodes which are:
3156 - inside the sub expression whose number is EX_SUBEXP, if FL_OPEN.
3157 - out of the sub expression whose number is EX_SUBEXP, if !FL_OPEN.
3160 static reg_errcode_t
3162 check_arrival_expand_ecl (const re_dfa_t *dfa, re_node_set *cur_nodes,
3163 Idx ex_subexp, int type)
3166 Idx idx, outside_node;
3167 re_node_set new_nodes;
3169 assert (cur_nodes->nelem);
3171 err = re_node_set_alloc (&new_nodes, cur_nodes->nelem);
3172 if (BE (err != REG_NOERROR, 0))
3174 /* Create a new node set NEW_NODES with the nodes which are epsilon
3175 closures of the node in CUR_NODES. */
3177 for (idx = 0; idx < cur_nodes->nelem; ++idx)
3179 Idx cur_node = cur_nodes->elems[idx];
3180 const re_node_set *eclosure = dfa->eclosures + cur_node;
3181 outside_node = find_subexp_node (dfa, eclosure, ex_subexp, type);
3182 if (outside_node == REG_MISSING)
3184 /* There are no problematic nodes, just merge them. */
3185 err = re_node_set_merge (&new_nodes, eclosure);
3186 if (BE (err != REG_NOERROR, 0))
3188 re_node_set_free (&new_nodes);
3194 /* There are problematic nodes, re-calculate incrementally. */
3195 err = check_arrival_expand_ecl_sub (dfa, &new_nodes, cur_node,
3197 if (BE (err != REG_NOERROR, 0))
3199 re_node_set_free (&new_nodes);
3204 re_node_set_free (cur_nodes);
3205 *cur_nodes = new_nodes;
3209 /* Helper function for check_arrival_expand_ecl.
3210 Check incrementally the epsilon closure of TARGET, and if it isn't
3211 problematic append it to DST_NODES. */
3213 static reg_errcode_t
3215 check_arrival_expand_ecl_sub (const re_dfa_t *dfa, re_node_set *dst_nodes,
3216 Idx target, Idx ex_subexp, int type)
3219 for (cur_node = target; !re_node_set_contains (dst_nodes, cur_node);)
3223 if (dfa->nodes[cur_node].type == type
3224 && dfa->nodes[cur_node].opr.idx == ex_subexp)
3226 if (type == OP_CLOSE_SUBEXP)
3228 ok = re_node_set_insert (dst_nodes, cur_node);
3234 ok = re_node_set_insert (dst_nodes, cur_node);
3237 if (dfa->edests[cur_node].nelem == 0)
3239 if (dfa->edests[cur_node].nelem == 2)
3242 err = check_arrival_expand_ecl_sub (dfa, dst_nodes,
3243 dfa->edests[cur_node].elems[1],
3245 if (BE (err != REG_NOERROR, 0))
3248 cur_node = dfa->edests[cur_node].elems[0];
3254 /* For all the back references in the current state, calculate the
3255 destination of the back references by the appropriate entry
3256 in MCTX->BKREF_ENTS. */
3258 static reg_errcode_t
3260 expand_bkref_cache (re_match_context_t *mctx, re_node_set *cur_nodes,
3261 Idx cur_str, Idx subexp_num, int type)
3263 const re_dfa_t *const dfa = mctx->dfa;
3265 Idx cache_idx_start = search_cur_bkref_entry (mctx, cur_str);
3266 struct re_backref_cache_entry *ent;
3268 if (cache_idx_start == REG_MISSING)
3272 ent = mctx->bkref_ents + cache_idx_start;
3275 Idx to_idx, next_node;
3277 /* Is this entry ENT is appropriate? */
3278 if (!re_node_set_contains (cur_nodes, ent->node))
3281 to_idx = cur_str + ent->subexp_to - ent->subexp_from;
3282 /* Calculate the destination of the back reference, and append it
3283 to MCTX->STATE_LOG. */
3284 if (to_idx == cur_str)
3286 /* The backreference did epsilon transit, we must re-check all the
3287 node in the current state. */
3288 re_node_set new_dests;
3289 reg_errcode_t err2, err3;
3290 next_node = dfa->edests[ent->node].elems[0];
3291 if (re_node_set_contains (cur_nodes, next_node))
3293 err = re_node_set_init_1 (&new_dests, next_node);
3294 err2 = check_arrival_expand_ecl (dfa, &new_dests, subexp_num, type);
3295 err3 = re_node_set_merge (cur_nodes, &new_dests);
3296 re_node_set_free (&new_dests);
3297 if (BE (err != REG_NOERROR || err2 != REG_NOERROR
3298 || err3 != REG_NOERROR, 0))
3300 err = (err != REG_NOERROR ? err
3301 : (err2 != REG_NOERROR ? err2 : err3));
3304 /* TODO: It is still inefficient... */
3309 re_node_set union_set;
3310 next_node = dfa->nexts[ent->node];
3311 if (mctx->state_log[to_idx])
3314 if (re_node_set_contains (&mctx->state_log[to_idx]->nodes,
3317 err = re_node_set_init_copy (&union_set,
3318 &mctx->state_log[to_idx]->nodes);
3319 ok = re_node_set_insert (&union_set, next_node);
3320 if (BE (err != REG_NOERROR || ! ok, 0))
3322 re_node_set_free (&union_set);
3323 err = err != REG_NOERROR ? err : REG_ESPACE;
3329 err = re_node_set_init_1 (&union_set, next_node);
3330 if (BE (err != REG_NOERROR, 0))
3333 mctx->state_log[to_idx] = re_acquire_state (&err, dfa, &union_set);
3334 re_node_set_free (&union_set);
3335 if (BE (mctx->state_log[to_idx] == NULL
3336 && err != REG_NOERROR, 0))
3340 while (ent++->more);
3344 /* Build transition table for the state.
3345 Return true if successful. */
3349 build_trtable (const re_dfa_t *dfa, re_dfastate_t *state)
3354 bool need_word_trtable = false;
3355 bitset_word_t elem, mask;
3356 bool dests_node_malloced = false;
3357 bool dest_states_malloced = false;
3358 Idx ndests; /* Number of the destination states from `state'. */
3359 re_dfastate_t **trtable;
3360 re_dfastate_t **dest_states = NULL, **dest_states_word, **dest_states_nl;
3361 re_node_set follows, *dests_node;
3363 bitset_t acceptable;
3367 re_node_set dests_node[SBC_MAX];
3368 bitset_t dests_ch[SBC_MAX];
3371 /* We build DFA states which corresponds to the destination nodes
3372 from `state'. `dests_node[i]' represents the nodes which i-th
3373 destination state contains, and `dests_ch[i]' represents the
3374 characters which i-th destination state accepts. */
3375 if (__libc_use_alloca (sizeof (struct dests_alloc)))
3376 dests_alloc = (struct dests_alloc *) alloca (sizeof (struct dests_alloc));
3379 dests_alloc = re_malloc (struct dests_alloc, 1);
3380 if (BE (dests_alloc == NULL, 0))
3382 dests_node_malloced = true;
3384 dests_node = dests_alloc->dests_node;
3385 dests_ch = dests_alloc->dests_ch;
3387 /* Initialize transiton table. */
3388 state->word_trtable = state->trtable = NULL;
3390 /* At first, group all nodes belonging to `state' into several
3392 ndests = group_nodes_into_DFAstates (dfa, state, dests_node, dests_ch);
3393 if (BE (! REG_VALID_NONZERO_INDEX (ndests), 0))
3395 if (dests_node_malloced)
3399 state->trtable = (re_dfastate_t **)
3400 calloc (sizeof (re_dfastate_t *), SBC_MAX);
3406 err = re_node_set_alloc (&follows, ndests + 1);
3407 if (BE (err != REG_NOERROR, 0))
3410 /* Avoid arithmetic overflow in size calculation. */
3411 if (BE ((((SIZE_MAX - (sizeof (re_node_set) + sizeof (bitset_t)) * SBC_MAX)
3412 / (3 * sizeof (re_dfastate_t *)))
3417 if (__libc_use_alloca ((sizeof (re_node_set) + sizeof (bitset_t)) * SBC_MAX
3418 + ndests * 3 * sizeof (re_dfastate_t *)))
3419 dest_states = (re_dfastate_t **)
3420 alloca (ndests * 3 * sizeof (re_dfastate_t *));
3423 dest_states = (re_dfastate_t **)
3424 malloc (ndests * 3 * sizeof (re_dfastate_t *));
3425 if (BE (dest_states == NULL, 0))
3428 if (dest_states_malloced)
3430 re_node_set_free (&follows);
3431 for (i = 0; i < ndests; ++i)
3432 re_node_set_free (dests_node + i);
3433 if (dests_node_malloced)
3437 dest_states_malloced = true;
3439 dest_states_word = dest_states + ndests;
3440 dest_states_nl = dest_states_word + ndests;
3441 bitset_empty (acceptable);
3443 /* Then build the states for all destinations. */
3444 for (i = 0; i < ndests; ++i)
3447 re_node_set_empty (&follows);
3448 /* Merge the follows of this destination states. */
3449 for (j = 0; j < dests_node[i].nelem; ++j)
3451 next_node = dfa->nexts[dests_node[i].elems[j]];
3452 if (next_node != REG_MISSING)
3454 err = re_node_set_merge (&follows, dfa->eclosures + next_node);
3455 if (BE (err != REG_NOERROR, 0))
3459 dest_states[i] = re_acquire_state_context (&err, dfa, &follows, 0);
3460 if (BE (dest_states[i] == NULL && err != REG_NOERROR, 0))
3462 /* If the new state has context constraint,
3463 build appropriate states for these contexts. */
3464 if (dest_states[i]->has_constraint)
3466 dest_states_word[i] = re_acquire_state_context (&err, dfa, &follows,
3468 if (BE (dest_states_word[i] == NULL && err != REG_NOERROR, 0))
3471 if (dest_states[i] != dest_states_word[i] && dfa->mb_cur_max > 1)
3472 need_word_trtable = true;
3474 dest_states_nl[i] = re_acquire_state_context (&err, dfa, &follows,
3476 if (BE (dest_states_nl[i] == NULL && err != REG_NOERROR, 0))
3481 dest_states_word[i] = dest_states[i];
3482 dest_states_nl[i] = dest_states[i];
3484 bitset_merge (acceptable, dests_ch[i]);
3487 if (!BE (need_word_trtable, 0))
3489 /* We don't care about whether the following character is a word
3490 character, or we are in a single-byte character set so we can
3491 discern by looking at the character code: allocate a
3492 256-entry transition table. */
3493 trtable = state->trtable =
3494 (re_dfastate_t **) calloc (sizeof (re_dfastate_t *), SBC_MAX);
3495 if (BE (trtable == NULL, 0))
3498 /* For all characters ch...: */
3499 for (i = 0; i < BITSET_WORDS; ++i)
3500 for (ch = i * BITSET_WORD_BITS, elem = acceptable[i], mask = 1;
3502 mask <<= 1, elem >>= 1, ++ch)
3503 if (BE (elem & 1, 0))
3505 /* There must be exactly one destination which accepts
3506 character ch. See group_nodes_into_DFAstates. */
3507 for (j = 0; (dests_ch[j][i] & mask) == 0; ++j)
3510 /* j-th destination accepts the word character ch. */
3511 if (dfa->word_char[i] & mask)
3512 trtable[ch] = dest_states_word[j];
3514 trtable[ch] = dest_states[j];
3519 /* We care about whether the following character is a word
3520 character, and we are in a multi-byte character set: discern
3521 by looking at the character code: build two 256-entry
3522 transition tables, one starting at trtable[0] and one
3523 starting at trtable[SBC_MAX]. */
3524 trtable = state->word_trtable =
3525 (re_dfastate_t **) calloc (sizeof (re_dfastate_t *), 2 * SBC_MAX);
3526 if (BE (trtable == NULL, 0))
3529 /* For all characters ch...: */
3530 for (i = 0; i < BITSET_WORDS; ++i)
3531 for (ch = i * BITSET_WORD_BITS, elem = acceptable[i], mask = 1;
3533 mask <<= 1, elem >>= 1, ++ch)
3534 if (BE (elem & 1, 0))
3536 /* There must be exactly one destination which accepts
3537 character ch. See group_nodes_into_DFAstates. */
3538 for (j = 0; (dests_ch[j][i] & mask) == 0; ++j)
3541 /* j-th destination accepts the word character ch. */
3542 trtable[ch] = dest_states[j];
3543 trtable[ch + SBC_MAX] = dest_states_word[j];
3548 if (bitset_contain (acceptable, NEWLINE_CHAR))
3550 /* The current state accepts newline character. */
3551 for (j = 0; j < ndests; ++j)
3552 if (bitset_contain (dests_ch[j], NEWLINE_CHAR))
3554 /* k-th destination accepts newline character. */
3555 trtable[NEWLINE_CHAR] = dest_states_nl[j];
3556 if (need_word_trtable)
3557 trtable[NEWLINE_CHAR + SBC_MAX] = dest_states_nl[j];
3558 /* There must be only one destination which accepts
3559 newline. See group_nodes_into_DFAstates. */
3564 if (dest_states_malloced)
3567 re_node_set_free (&follows);
3568 for (i = 0; i < ndests; ++i)
3569 re_node_set_free (dests_node + i);
3571 if (dests_node_malloced)
3577 /* Group all nodes belonging to STATE into several destinations.
3578 Then for all destinations, set the nodes belonging to the destination
3579 to DESTS_NODE[i] and set the characters accepted by the destination
3580 to DEST_CH[i]. This function return the number of destinations. */
3584 group_nodes_into_DFAstates (const re_dfa_t *dfa, const re_dfastate_t *state,
3585 re_node_set *dests_node, bitset_t *dests_ch)
3590 Idx ndests; /* Number of the destinations from `state'. */
3591 bitset_t accepts; /* Characters a node can accept. */
3592 const re_node_set *cur_nodes = &state->nodes;
3593 bitset_empty (accepts);
3596 /* For all the nodes belonging to `state', */
3597 for (i = 0; i < cur_nodes->nelem; ++i)
3599 re_token_t *node = &dfa->nodes[cur_nodes->elems[i]];
3600 re_token_type_t type = node->type;
3601 unsigned int constraint = node->constraint;
3603 /* Enumerate all single byte character this node can accept. */
3604 if (type == CHARACTER)
3605 bitset_set (accepts, node->opr.c);
3606 else if (type == SIMPLE_BRACKET)
3608 bitset_merge (accepts, node->opr.sbcset);
3610 else if (type == OP_PERIOD)
3612 #ifdef RE_ENABLE_I18N
3613 if (dfa->mb_cur_max > 1)
3614 bitset_merge (accepts, dfa->sb_char);
3617 bitset_set_all (accepts);
3618 if (!(dfa->syntax & RE_DOT_NEWLINE))
3619 bitset_clear (accepts, '\n');
3620 if (dfa->syntax & RE_DOT_NOT_NULL)
3621 bitset_clear (accepts, '\0');
3623 #ifdef RE_ENABLE_I18N
3624 else if (type == OP_UTF8_PERIOD)
3626 if (ASCII_CHARS % BITSET_WORD_BITS == 0)
3627 memset (accepts, -1, ASCII_CHARS / CHAR_BIT);
3629 bitset_merge (accepts, utf8_sb_map);
3630 if (!(dfa->syntax & RE_DOT_NEWLINE))
3631 bitset_clear (accepts, '\n');
3632 if (dfa->syntax & RE_DOT_NOT_NULL)
3633 bitset_clear (accepts, '\0');
3639 /* Check the `accepts' and sift the characters which are not
3640 match it the context. */
3643 if (constraint & NEXT_NEWLINE_CONSTRAINT)
3645 bool accepts_newline = bitset_contain (accepts, NEWLINE_CHAR);
3646 bitset_empty (accepts);
3647 if (accepts_newline)
3648 bitset_set (accepts, NEWLINE_CHAR);
3652 if (constraint & NEXT_ENDBUF_CONSTRAINT)
3654 bitset_empty (accepts);
3658 if (constraint & NEXT_WORD_CONSTRAINT)
3660 bitset_word_t any_set = 0;
3661 if (type == CHARACTER && !node->word_char)
3663 bitset_empty (accepts);
3666 #ifdef RE_ENABLE_I18N
3667 if (dfa->mb_cur_max > 1)
3668 for (j = 0; j < BITSET_WORDS; ++j)
3669 any_set |= (accepts[j] &= (dfa->word_char[j] | ~dfa->sb_char[j]));
3672 for (j = 0; j < BITSET_WORDS; ++j)
3673 any_set |= (accepts[j] &= dfa->word_char[j]);
3677 if (constraint & NEXT_NOTWORD_CONSTRAINT)
3679 bitset_word_t any_set = 0;
3680 if (type == CHARACTER && node->word_char)
3682 bitset_empty (accepts);
3685 #ifdef RE_ENABLE_I18N
3686 if (dfa->mb_cur_max > 1)
3687 for (j = 0; j < BITSET_WORDS; ++j)
3688 any_set |= (accepts[j] &= ~(dfa->word_char[j] & dfa->sb_char[j]));
3691 for (j = 0; j < BITSET_WORDS; ++j)
3692 any_set |= (accepts[j] &= ~dfa->word_char[j]);
3698 /* Then divide `accepts' into DFA states, or create a new
3699 state. Above, we make sure that accepts is not empty. */
3700 for (j = 0; j < ndests; ++j)
3702 bitset_t intersec; /* Intersection sets, see below. */
3704 /* Flags, see below. */
3705 bitset_word_t has_intersec, not_subset, not_consumed;
3707 /* Optimization, skip if this state doesn't accept the character. */
3708 if (type == CHARACTER && !bitset_contain (dests_ch[j], node->opr.c))
3711 /* Enumerate the intersection set of this state and `accepts'. */
3713 for (k = 0; k < BITSET_WORDS; ++k)
3714 has_intersec |= intersec[k] = accepts[k] & dests_ch[j][k];
3715 /* And skip if the intersection set is empty. */
3719 /* Then check if this state is a subset of `accepts'. */
3720 not_subset = not_consumed = 0;
3721 for (k = 0; k < BITSET_WORDS; ++k)
3723 not_subset |= remains[k] = ~accepts[k] & dests_ch[j][k];
3724 not_consumed |= accepts[k] = accepts[k] & ~dests_ch[j][k];
3727 /* If this state isn't a subset of `accepts', create a
3728 new group state, which has the `remains'. */
3731 bitset_copy (dests_ch[ndests], remains);
3732 bitset_copy (dests_ch[j], intersec);
3733 err = re_node_set_init_copy (dests_node + ndests, &dests_node[j]);
3734 if (BE (err != REG_NOERROR, 0))
3739 /* Put the position in the current group. */
3740 ok = re_node_set_insert (&dests_node[j], cur_nodes->elems[i]);
3744 /* If all characters are consumed, go to next node. */
3748 /* Some characters remain, create a new group. */
3751 bitset_copy (dests_ch[ndests], accepts);
3752 err = re_node_set_init_1 (dests_node + ndests, cur_nodes->elems[i]);
3753 if (BE (err != REG_NOERROR, 0))
3756 bitset_empty (accepts);
3761 for (j = 0; j < ndests; ++j)
3762 re_node_set_free (dests_node + j);
3766 #ifdef RE_ENABLE_I18N
3767 /* Check how many bytes the node `dfa->nodes[node_idx]' accepts.
3768 Return the number of the bytes the node accepts.
3769 STR_IDX is the current index of the input string.
3771 This function handles the nodes which can accept one character, or
3772 one collating element like '.', '[a-z]', opposite to the other nodes
3773 can only accept one byte. */
3777 check_node_accept_bytes (const re_dfa_t *dfa, Idx node_idx,
3778 const re_string_t *input, Idx str_idx)
3780 const re_token_t *node = dfa->nodes + node_idx;
3781 int char_len, elem_len;
3784 if (BE (node->type == OP_UTF8_PERIOD, 0))
3786 unsigned char c = re_string_byte_at (input, str_idx), d;
3787 if (BE (c < 0xc2, 1))
3790 if (str_idx + 2 > input->len)
3793 d = re_string_byte_at (input, str_idx + 1);
3795 return (d < 0x80 || d > 0xbf) ? 0 : 2;
3799 if (c == 0xe0 && d < 0xa0)
3805 if (c == 0xf0 && d < 0x90)
3811 if (c == 0xf8 && d < 0x88)
3817 if (c == 0xfc && d < 0x84)
3823 if (str_idx + char_len > input->len)
3826 for (i = 1; i < char_len; ++i)
3828 d = re_string_byte_at (input, str_idx + i);
3829 if (d < 0x80 || d > 0xbf)
3835 char_len = re_string_char_size_at (input, str_idx);
3836 if (node->type == OP_PERIOD)
3840 /* FIXME: I don't think this if is needed, as both '\n'
3841 and '\0' are char_len == 1. */
3842 /* '.' accepts any one character except the following two cases. */
3843 if ((!(dfa->syntax & RE_DOT_NEWLINE) &&
3844 re_string_byte_at (input, str_idx) == '\n') ||
3845 ((dfa->syntax & RE_DOT_NOT_NULL) &&
3846 re_string_byte_at (input, str_idx) == '\0'))
3851 elem_len = re_string_elem_size_at (input, str_idx);
3852 if ((elem_len <= 1 && char_len <= 1) || char_len == 0)
3855 if (node->type == COMPLEX_BRACKET)
3857 const re_charset_t *cset = node->opr.mbcset;
3859 const unsigned char *pin
3860 = ((const unsigned char *) re_string_get_buffer (input) + str_idx);
3865 wchar_t wc = ((cset->nranges || cset->nchar_classes || cset->nmbchars)
3866 ? re_string_wchar_at (input, str_idx) : 0);
3868 /* match with multibyte character? */
3869 for (i = 0; i < cset->nmbchars; ++i)
3870 if (wc == cset->mbchars[i])
3872 match_len = char_len;
3873 goto check_node_accept_bytes_match;
3875 /* match with character_class? */
3876 for (i = 0; i < cset->nchar_classes; ++i)
3878 wctype_t wt = cset->char_classes[i];
3879 if (__iswctype (wc, wt))
3881 match_len = char_len;
3882 goto check_node_accept_bytes_match;
3887 nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
3890 unsigned int in_collseq = 0;
3891 const int32_t *table, *indirect;
3892 const unsigned char *weights, *extra;
3893 const char *collseqwc;
3895 /* This #include defines a local function! */
3896 # include <locale/weight.h>
3898 /* match with collating_symbol? */
3899 if (cset->ncoll_syms)
3900 extra = (const unsigned char *)
3901 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB);
3902 for (i = 0; i < cset->ncoll_syms; ++i)
3904 const unsigned char *coll_sym = extra + cset->coll_syms[i];
3905 /* Compare the length of input collating element and
3906 the length of current collating element. */
3907 if (*coll_sym != elem_len)
3909 /* Compare each bytes. */
3910 for (j = 0; j < *coll_sym; j++)
3911 if (pin[j] != coll_sym[1 + j])
3915 /* Match if every bytes is equal. */
3917 goto check_node_accept_bytes_match;
3923 if (elem_len <= char_len)
3925 collseqwc = _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQWC);
3926 in_collseq = __collseq_table_lookup (collseqwc, wc);
3929 in_collseq = find_collation_sequence_value (pin, elem_len);
3931 /* match with range expression? */
3932 for (i = 0; i < cset->nranges; ++i)
3933 if (cset->range_starts[i] <= in_collseq
3934 && in_collseq <= cset->range_ends[i])
3936 match_len = elem_len;
3937 goto check_node_accept_bytes_match;
3940 /* match with equivalence_class? */
3941 if (cset->nequiv_classes)
3943 const unsigned char *cp = pin;
3944 table = (const int32_t *)
3945 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
3946 weights = (const unsigned char *)
3947 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_WEIGHTMB);
3948 extra = (const unsigned char *)
3949 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAMB);
3950 indirect = (const int32_t *)
3951 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_INDIRECTMB);
3952 idx = findidx (&cp);
3954 for (i = 0; i < cset->nequiv_classes; ++i)
3956 int32_t equiv_class_idx = cset->equiv_classes[i];
3957 size_t weight_len = weights[idx];
3958 if (weight_len == weights[equiv_class_idx])
3961 while (cnt <= weight_len
3962 && (weights[equiv_class_idx + 1 + cnt]
3963 == weights[idx + 1 + cnt]))
3965 if (cnt > weight_len)
3967 match_len = elem_len;
3968 goto check_node_accept_bytes_match;
3977 /* match with range expression? */
3978 #if __GNUC__ >= 2 && ! (__STDC_VERSION__ < 199901L && __STRICT_ANSI__)
3979 wchar_t cmp_buf[] = {L'\0', L'\0', wc, L'\0', L'\0', L'\0'};
3981 wchar_t cmp_buf[] = {L'\0', L'\0', L'\0', L'\0', L'\0', L'\0'};
3984 for (i = 0; i < cset->nranges; ++i)
3986 cmp_buf[0] = cset->range_starts[i];
3987 cmp_buf[4] = cset->range_ends[i];
3988 if (wcscoll (cmp_buf, cmp_buf + 2) <= 0
3989 && wcscoll (cmp_buf + 2, cmp_buf + 4) <= 0)
3991 match_len = char_len;
3992 goto check_node_accept_bytes_match;
3996 check_node_accept_bytes_match:
3997 if (!cset->non_match)
4004 return (elem_len > char_len) ? elem_len : char_len;
4013 find_collation_sequence_value (const unsigned char *mbs, size_t mbs_len)
4015 uint32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
4020 /* No valid character. Match it as a single byte character. */
4021 const unsigned char *collseq = (const unsigned char *)
4022 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQMB);
4023 return collseq[mbs[0]];
4030 const unsigned char *extra = (const unsigned char *)
4031 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB);
4032 int32_t extrasize = (const unsigned char *)
4033 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB + 1) - extra;
4035 for (idx = 0; idx < extrasize;)
4039 int32_t elem_mbs_len;
4040 /* Skip the name of collating element name. */
4041 idx = idx + extra[idx] + 1;
4042 elem_mbs_len = extra[idx++];
4043 if (mbs_len == elem_mbs_len)
4045 for (mbs_cnt = 0; mbs_cnt < elem_mbs_len; ++mbs_cnt)
4046 if (extra[idx + mbs_cnt] != mbs[mbs_cnt])
4048 if (mbs_cnt == elem_mbs_len)
4049 /* Found the entry. */
4052 /* Skip the byte sequence of the collating element. */
4053 idx += elem_mbs_len;
4054 /* Adjust for the alignment. */
4055 idx = (idx + 3) & ~3;
4056 /* Skip the collation sequence value. */
4057 idx += sizeof (uint32_t);
4058 /* Skip the wide char sequence of the collating element. */
4059 idx = idx + sizeof (uint32_t) * (extra[idx] + 1);
4060 /* If we found the entry, return the sequence value. */
4062 return *(uint32_t *) (extra + idx);
4063 /* Skip the collation sequence value. */
4064 idx += sizeof (uint32_t);
4070 #endif /* RE_ENABLE_I18N */
4072 /* Check whether the node accepts the byte which is IDX-th
4073 byte of the INPUT. */
4077 check_node_accept (const re_match_context_t *mctx, const re_token_t *node,
4081 ch = re_string_byte_at (&mctx->input, idx);
4085 if (node->opr.c != ch)
4089 case SIMPLE_BRACKET:
4090 if (!bitset_contain (node->opr.sbcset, ch))
4094 #ifdef RE_ENABLE_I18N
4095 case OP_UTF8_PERIOD:
4096 if (ch >= ASCII_CHARS)
4101 if ((ch == '\n' && !(mctx->dfa->syntax & RE_DOT_NEWLINE))
4102 || (ch == '\0' && (mctx->dfa->syntax & RE_DOT_NOT_NULL)))
4110 if (node->constraint)
4112 /* The node has constraints. Check whether the current context
4113 satisfies the constraints. */
4114 unsigned int context = re_string_context_at (&mctx->input, idx,
4116 if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
4123 /* Extend the buffers, if the buffers have run out. */
4125 static reg_errcode_t
4127 extend_buffers (re_match_context_t *mctx)
4130 re_string_t *pstr = &mctx->input;
4132 /* Avoid overflow. */
4133 if (BE (SIZE_MAX / 2 / sizeof (re_dfastate_t *) <= pstr->bufs_len, 0))
4136 /* Double the lengthes of the buffers. */
4137 ret = re_string_realloc_buffers (pstr, pstr->bufs_len * 2);
4138 if (BE (ret != REG_NOERROR, 0))
4141 if (mctx->state_log != NULL)
4143 /* And double the length of state_log. */
4144 /* XXX We have no indication of the size of this buffer. If this
4145 allocation fail we have no indication that the state_log array
4146 does not have the right size. */
4147 re_dfastate_t **new_array = re_realloc (mctx->state_log, re_dfastate_t *,
4148 pstr->bufs_len + 1);
4149 if (BE (new_array == NULL, 0))
4151 mctx->state_log = new_array;
4154 /* Then reconstruct the buffers. */
4157 #ifdef RE_ENABLE_I18N
4158 if (pstr->mb_cur_max > 1)
4160 ret = build_wcs_upper_buffer (pstr);
4161 if (BE (ret != REG_NOERROR, 0))
4165 #endif /* RE_ENABLE_I18N */
4166 build_upper_buffer (pstr);
4170 #ifdef RE_ENABLE_I18N
4171 if (pstr->mb_cur_max > 1)
4172 build_wcs_buffer (pstr);
4174 #endif /* RE_ENABLE_I18N */
4176 if (pstr->trans != NULL)
4177 re_string_translate_buffer (pstr);
4184 /* Functions for matching context. */
4186 /* Initialize MCTX. */
4188 static reg_errcode_t
4190 match_ctx_init (re_match_context_t *mctx, int eflags, Idx n)
4192 mctx->eflags = eflags;
4193 mctx->match_last = REG_MISSING;
4196 /* Avoid overflow. */
4197 size_t max_object_size =
4198 MAX (sizeof (struct re_backref_cache_entry),
4199 sizeof (re_sub_match_top_t *));
4200 if (BE (SIZE_MAX / max_object_size < n, 0))
4203 mctx->bkref_ents = re_malloc (struct re_backref_cache_entry, n);
4204 mctx->sub_tops = re_malloc (re_sub_match_top_t *, n);
4205 if (BE (mctx->bkref_ents == NULL || mctx->sub_tops == NULL, 0))
4208 /* Already zero-ed by the caller.
4210 mctx->bkref_ents = NULL;
4211 mctx->nbkref_ents = 0;
4212 mctx->nsub_tops = 0; */
4213 mctx->abkref_ents = n;
4214 mctx->max_mb_elem_len = 1;
4215 mctx->asub_tops = n;
4219 /* Clean the entries which depend on the current input in MCTX.
4220 This function must be invoked when the matcher changes the start index
4221 of the input, or changes the input string. */
4225 match_ctx_clean (re_match_context_t *mctx)
4228 for (st_idx = 0; st_idx < mctx->nsub_tops; ++st_idx)
4231 re_sub_match_top_t *top = mctx->sub_tops[st_idx];
4232 for (sl_idx = 0; sl_idx < top->nlasts; ++sl_idx)
4234 re_sub_match_last_t *last = top->lasts[sl_idx];
4235 re_free (last->path.array);
4238 re_free (top->lasts);
4241 re_free (top->path->array);
4242 re_free (top->path);
4247 mctx->nsub_tops = 0;
4248 mctx->nbkref_ents = 0;
4251 /* Free all the memory associated with MCTX. */
4255 match_ctx_free (re_match_context_t *mctx)
4257 /* First, free all the memory associated with MCTX->SUB_TOPS. */
4258 match_ctx_clean (mctx);
4259 re_free (mctx->sub_tops);
4260 re_free (mctx->bkref_ents);
4263 /* Add a new backreference entry to MCTX.
4264 Note that we assume that caller never call this function with duplicate
4265 entry, and call with STR_IDX which isn't smaller than any existing entry.
4268 static reg_errcode_t
4270 match_ctx_add_entry (re_match_context_t *mctx, Idx node, Idx str_idx, Idx from,
4273 if (mctx->nbkref_ents >= mctx->abkref_ents)
4275 struct re_backref_cache_entry* new_entry;
4276 new_entry = re_realloc (mctx->bkref_ents, struct re_backref_cache_entry,
4277 mctx->abkref_ents * 2);
4278 if (BE (new_entry == NULL, 0))
4280 re_free (mctx->bkref_ents);
4283 mctx->bkref_ents = new_entry;
4284 memset (mctx->bkref_ents + mctx->nbkref_ents, '\0',
4285 sizeof (struct re_backref_cache_entry) * mctx->abkref_ents);
4286 mctx->abkref_ents *= 2;
4288 if (mctx->nbkref_ents > 0
4289 && mctx->bkref_ents[mctx->nbkref_ents - 1].str_idx == str_idx)
4290 mctx->bkref_ents[mctx->nbkref_ents - 1].more = 1;
4292 mctx->bkref_ents[mctx->nbkref_ents].node = node;
4293 mctx->bkref_ents[mctx->nbkref_ents].str_idx = str_idx;
4294 mctx->bkref_ents[mctx->nbkref_ents].subexp_from = from;
4295 mctx->bkref_ents[mctx->nbkref_ents].subexp_to = to;
4297 /* This is a cache that saves negative results of check_dst_limits_calc_pos.
4298 If bit N is clear, means that this entry won't epsilon-transition to
4299 an OP_OPEN_SUBEXP or OP_CLOSE_SUBEXP for the N+1-th subexpression. If
4300 it is set, check_dst_limits_calc_pos_1 will recurse and try to find one
4303 A backreference does not epsilon-transition unless it is empty, so set
4304 to all zeros if FROM != TO. */
4305 mctx->bkref_ents[mctx->nbkref_ents].eps_reachable_subexps_map
4306 = (from == to ? -1 : 0);
4308 mctx->bkref_ents[mctx->nbkref_ents++].more = 0;
4309 if (mctx->max_mb_elem_len < to - from)
4310 mctx->max_mb_elem_len = to - from;
4314 /* Return the first entry with the same str_idx, or REG_MISSING if none is
4315 found. Note that MCTX->BKREF_ENTS is already sorted by MCTX->STR_IDX. */
4319 search_cur_bkref_entry (const re_match_context_t *mctx, Idx str_idx)
4321 Idx left, right, mid, last;
4322 last = right = mctx->nbkref_ents;
4323 for (left = 0; left < right;)
4325 mid = (left + right) / 2;
4326 if (mctx->bkref_ents[mid].str_idx < str_idx)
4331 if (left < last && mctx->bkref_ents[left].str_idx == str_idx)
4337 /* Register the node NODE, whose type is OP_OPEN_SUBEXP, and which matches
4340 static reg_errcode_t
4342 match_ctx_add_subtop (re_match_context_t *mctx, Idx node, Idx str_idx)
4345 assert (mctx->sub_tops != NULL);
4346 assert (mctx->asub_tops > 0);
4348 if (BE (mctx->nsub_tops == mctx->asub_tops, 0))
4350 Idx new_asub_tops = mctx->asub_tops * 2;
4351 re_sub_match_top_t **new_array = re_realloc (mctx->sub_tops,
4352 re_sub_match_top_t *,
4354 if (BE (new_array == NULL, 0))
4356 mctx->sub_tops = new_array;
4357 mctx->asub_tops = new_asub_tops;
4359 mctx->sub_tops[mctx->nsub_tops] = calloc (1, sizeof (re_sub_match_top_t));
4360 if (BE (mctx->sub_tops[mctx->nsub_tops] == NULL, 0))
4362 mctx->sub_tops[mctx->nsub_tops]->node = node;
4363 mctx->sub_tops[mctx->nsub_tops++]->str_idx = str_idx;
4367 /* Register the node NODE, whose type is OP_CLOSE_SUBEXP, and which matches
4368 at STR_IDX, whose corresponding OP_OPEN_SUBEXP is SUB_TOP. */
4370 static re_sub_match_last_t *
4372 match_ctx_add_sublast (re_sub_match_top_t *subtop, Idx node, Idx str_idx)
4374 re_sub_match_last_t *new_entry;
4375 if (BE (subtop->nlasts == subtop->alasts, 0))
4377 Idx new_alasts = 2 * subtop->alasts + 1;
4378 re_sub_match_last_t **new_array = re_realloc (subtop->lasts,
4379 re_sub_match_last_t *,
4381 if (BE (new_array == NULL, 0))
4383 subtop->lasts = new_array;
4384 subtop->alasts = new_alasts;
4386 new_entry = calloc (1, sizeof (re_sub_match_last_t));
4387 if (BE (new_entry != NULL, 1))
4389 subtop->lasts[subtop->nlasts] = new_entry;
4390 new_entry->node = node;
4391 new_entry->str_idx = str_idx;
4399 sift_ctx_init (re_sift_context_t *sctx, re_dfastate_t **sifted_sts,
4400 re_dfastate_t **limited_sts, Idx last_node, Idx last_str_idx)
4402 sctx->sifted_states = sifted_sts;
4403 sctx->limited_states = limited_sts;
4404 sctx->last_node = last_node;
4405 sctx->last_str_idx = last_str_idx;
4406 re_node_set_init_empty (&sctx->limits);