1 /* -*- buffer-read-only: t -*- vi: set ro: */
2 /* DO NOT EDIT! GENERATED AUTOMATICALLY! */
3 /* Extended regular expression matching and search library.
4 Copyright (C) 2002-2011 Free Software Foundation, Inc.
5 This file is part of the GNU C Library.
6 Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>.
8 This program is free software; you can redistribute it and/or modify
9 it under the terms of the GNU General Public License as published by
10 the Free Software Foundation; either version 3, or (at your option)
13 This program is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16 GNU General Public License for more details.
18 You should have received a copy of the GNU General Public License along
19 with this program; if not, write to the Free Software Foundation,
20 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
24 static reg_errcode_t match_ctx_init (re_match_context_t *cache, int eflags,
25 Idx n) internal_function;
26 static void match_ctx_clean (re_match_context_t *mctx) internal_function;
27 static void match_ctx_free (re_match_context_t *cache) internal_function;
28 static reg_errcode_t match_ctx_add_entry (re_match_context_t *cache, Idx node,
29 Idx str_idx, Idx from, Idx to)
31 static Idx search_cur_bkref_entry (const re_match_context_t *mctx, Idx str_idx)
33 static reg_errcode_t match_ctx_add_subtop (re_match_context_t *mctx, Idx node,
34 Idx str_idx) internal_function;
35 static re_sub_match_last_t * match_ctx_add_sublast (re_sub_match_top_t *subtop,
36 Idx node, Idx str_idx)
38 static void sift_ctx_init (re_sift_context_t *sctx, re_dfastate_t **sifted_sts,
39 re_dfastate_t **limited_sts, Idx last_node,
42 static reg_errcode_t re_search_internal (const regex_t *preg,
43 const char *string, Idx length,
44 Idx start, Idx last_start, Idx stop,
45 size_t nmatch, regmatch_t pmatch[],
46 int eflags) internal_function;
47 static regoff_t re_search_2_stub (struct re_pattern_buffer *bufp,
48 const char *string1, Idx length1,
49 const char *string2, Idx length2,
50 Idx start, regoff_t range,
51 struct re_registers *regs,
52 Idx stop, bool ret_len) internal_function;
53 static regoff_t re_search_stub (struct re_pattern_buffer *bufp,
54 const char *string, Idx length, Idx start,
55 regoff_t range, Idx stop,
56 struct re_registers *regs,
57 bool ret_len) internal_function;
58 static unsigned int re_copy_regs (struct re_registers *regs, regmatch_t *pmatch,
59 Idx nregs, int regs_allocated)
61 static reg_errcode_t prune_impossible_nodes (re_match_context_t *mctx)
63 static Idx check_matching (re_match_context_t *mctx, bool fl_longest_match,
64 Idx *p_match_first) internal_function;
65 static Idx check_halt_state_context (const re_match_context_t *mctx,
66 const re_dfastate_t *state, Idx idx)
68 static void update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
69 regmatch_t *prev_idx_match, Idx cur_node,
70 Idx cur_idx, Idx nmatch) internal_function;
71 static reg_errcode_t push_fail_stack (struct re_fail_stack_t *fs,
72 Idx str_idx, Idx dest_node, Idx nregs,
74 re_node_set *eps_via_nodes)
76 static reg_errcode_t set_regs (const regex_t *preg,
77 const re_match_context_t *mctx,
78 size_t nmatch, regmatch_t *pmatch,
79 bool fl_backtrack) internal_function;
80 static reg_errcode_t free_fail_stack_return (struct re_fail_stack_t *fs)
84 static int sift_states_iter_mb (const re_match_context_t *mctx,
85 re_sift_context_t *sctx,
86 Idx node_idx, Idx str_idx, Idx max_str_idx)
88 #endif /* RE_ENABLE_I18N */
89 static reg_errcode_t sift_states_backward (const re_match_context_t *mctx,
90 re_sift_context_t *sctx)
92 static reg_errcode_t build_sifted_states (const re_match_context_t *mctx,
93 re_sift_context_t *sctx, Idx str_idx,
94 re_node_set *cur_dest)
96 static reg_errcode_t update_cur_sifted_state (const re_match_context_t *mctx,
97 re_sift_context_t *sctx,
99 re_node_set *dest_nodes)
101 static reg_errcode_t add_epsilon_src_nodes (const re_dfa_t *dfa,
102 re_node_set *dest_nodes,
103 const re_node_set *candidates)
105 static bool check_dst_limits (const re_match_context_t *mctx,
106 const re_node_set *limits,
107 Idx dst_node, Idx dst_idx, Idx src_node,
108 Idx src_idx) internal_function;
109 static int check_dst_limits_calc_pos_1 (const re_match_context_t *mctx,
110 int boundaries, Idx subexp_idx,
111 Idx from_node, Idx bkref_idx)
113 static int check_dst_limits_calc_pos (const re_match_context_t *mctx,
114 Idx limit, Idx subexp_idx,
115 Idx node, Idx str_idx,
116 Idx bkref_idx) internal_function;
117 static reg_errcode_t check_subexp_limits (const re_dfa_t *dfa,
118 re_node_set *dest_nodes,
119 const re_node_set *candidates,
121 struct re_backref_cache_entry *bkref_ents,
122 Idx str_idx) internal_function;
123 static reg_errcode_t sift_states_bkref (const re_match_context_t *mctx,
124 re_sift_context_t *sctx,
125 Idx str_idx, const re_node_set *candidates)
127 static reg_errcode_t merge_state_array (const re_dfa_t *dfa,
129 re_dfastate_t **src, Idx num)
131 static re_dfastate_t *find_recover_state (reg_errcode_t *err,
132 re_match_context_t *mctx) internal_function;
133 static re_dfastate_t *transit_state (reg_errcode_t *err,
134 re_match_context_t *mctx,
135 re_dfastate_t *state) internal_function;
136 static re_dfastate_t *merge_state_with_log (reg_errcode_t *err,
137 re_match_context_t *mctx,
138 re_dfastate_t *next_state)
140 static reg_errcode_t check_subexp_matching_top (re_match_context_t *mctx,
141 re_node_set *cur_nodes,
142 Idx str_idx) internal_function;
144 static re_dfastate_t *transit_state_sb (reg_errcode_t *err,
145 re_match_context_t *mctx,
146 re_dfastate_t *pstate)
149 #ifdef RE_ENABLE_I18N
150 static reg_errcode_t transit_state_mb (re_match_context_t *mctx,
151 re_dfastate_t *pstate)
153 #endif /* RE_ENABLE_I18N */
154 static reg_errcode_t transit_state_bkref (re_match_context_t *mctx,
155 const re_node_set *nodes)
157 static reg_errcode_t get_subexp (re_match_context_t *mctx,
158 Idx bkref_node, Idx bkref_str_idx)
160 static reg_errcode_t get_subexp_sub (re_match_context_t *mctx,
161 const re_sub_match_top_t *sub_top,
162 re_sub_match_last_t *sub_last,
163 Idx bkref_node, Idx bkref_str)
165 static Idx find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
166 Idx subexp_idx, int type) internal_function;
167 static reg_errcode_t check_arrival (re_match_context_t *mctx,
168 state_array_t *path, Idx top_node,
169 Idx top_str, Idx last_node, Idx last_str,
170 int type) internal_function;
171 static reg_errcode_t check_arrival_add_next_nodes (re_match_context_t *mctx,
173 re_node_set *cur_nodes,
174 re_node_set *next_nodes)
176 static reg_errcode_t check_arrival_expand_ecl (const re_dfa_t *dfa,
177 re_node_set *cur_nodes,
178 Idx ex_subexp, int type)
180 static reg_errcode_t check_arrival_expand_ecl_sub (const re_dfa_t *dfa,
181 re_node_set *dst_nodes,
182 Idx target, Idx ex_subexp,
183 int type) internal_function;
184 static reg_errcode_t expand_bkref_cache (re_match_context_t *mctx,
185 re_node_set *cur_nodes, Idx cur_str,
186 Idx subexp_num, int type)
188 static bool build_trtable (const re_dfa_t *dfa,
189 re_dfastate_t *state) internal_function;
190 #ifdef RE_ENABLE_I18N
191 static int check_node_accept_bytes (const re_dfa_t *dfa, Idx node_idx,
192 const re_string_t *input, Idx idx)
195 static unsigned int find_collation_sequence_value (const unsigned char *mbs,
199 #endif /* RE_ENABLE_I18N */
200 static Idx group_nodes_into_DFAstates (const re_dfa_t *dfa,
201 const re_dfastate_t *state,
202 re_node_set *states_node,
203 bitset_t *states_ch) internal_function;
204 static bool check_node_accept (const re_match_context_t *mctx,
205 const re_token_t *node, Idx idx)
207 static reg_errcode_t extend_buffers (re_match_context_t *mctx)
210 /* Entry point for POSIX code. */
212 /* regexec searches for a given pattern, specified by PREG, in the
215 If NMATCH is zero or REG_NOSUB was set in the cflags argument to
216 `regcomp', we ignore PMATCH. Otherwise, we assume PMATCH has at
217 least NMATCH elements, and we set them to the offsets of the
218 corresponding matched substrings.
220 EFLAGS specifies `execution flags' which affect matching: if
221 REG_NOTBOL is set, then ^ does not match at the beginning of the
222 string; if REG_NOTEOL is set, then $ does not match at the end.
224 We return 0 if we find a match and REG_NOMATCH if not. */
227 regexec (preg, string, nmatch, pmatch, eflags)
228 const regex_t *_Restrict_ preg;
229 const char *_Restrict_ string;
231 regmatch_t pmatch[_Restrict_arr_];
237 re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
240 if (eflags & ~(REG_NOTBOL | REG_NOTEOL | REG_STARTEND))
243 if (eflags & REG_STARTEND)
245 start = pmatch[0].rm_so;
246 length = pmatch[0].rm_eo;
251 length = strlen (string);
254 __libc_lock_lock (dfa->lock);
256 err = re_search_internal (preg, string, length, start, length,
257 length, 0, NULL, eflags);
259 err = re_search_internal (preg, string, length, start, length,
260 length, nmatch, pmatch, eflags);
261 __libc_lock_unlock (dfa->lock);
262 return err != REG_NOERROR;
266 # include <shlib-compat.h>
267 versioned_symbol (libc, __regexec, regexec, GLIBC_2_3_4);
269 # if SHLIB_COMPAT (libc, GLIBC_2_0, GLIBC_2_3_4)
270 __typeof__ (__regexec) __compat_regexec;
273 attribute_compat_text_section
274 __compat_regexec (const regex_t *_Restrict_ preg,
275 const char *_Restrict_ string, size_t nmatch,
276 regmatch_t pmatch[], int eflags)
278 return regexec (preg, string, nmatch, pmatch,
279 eflags & (REG_NOTBOL | REG_NOTEOL));
281 compat_symbol (libc, __compat_regexec, regexec, GLIBC_2_0);
285 /* Entry points for GNU code. */
287 /* re_match, re_search, re_match_2, re_search_2
289 The former two functions operate on STRING with length LENGTH,
290 while the later two operate on concatenation of STRING1 and STRING2
291 with lengths LENGTH1 and LENGTH2, respectively.
293 re_match() matches the compiled pattern in BUFP against the string,
294 starting at index START.
296 re_search() first tries matching at index START, then it tries to match
297 starting from index START + 1, and so on. The last start position tried
298 is START + RANGE. (Thus RANGE = 0 forces re_search to operate the same
301 The parameter STOP of re_{match,search}_2 specifies that no match exceeding
302 the first STOP characters of the concatenation of the strings should be
305 If REGS is not NULL, and BUFP->no_sub is not set, the offsets of the match
306 and all groups is stored in REGS. (For the "_2" variants, the offsets are
307 computed relative to the concatenation, not relative to the individual
310 On success, re_match* functions return the length of the match, re_search*
311 return the position of the start of the match. Return value -1 means no
312 match was found and -2 indicates an internal error. */
315 re_match (bufp, string, length, start, regs)
316 struct re_pattern_buffer *bufp;
319 struct re_registers *regs;
321 return re_search_stub (bufp, string, length, start, 0, length, regs, true);
324 weak_alias (__re_match, re_match)
328 re_search (bufp, string, length, start, range, regs)
329 struct re_pattern_buffer *bufp;
333 struct re_registers *regs;
335 return re_search_stub (bufp, string, length, start, range, length, regs,
339 weak_alias (__re_search, re_search)
343 re_match_2 (bufp, string1, length1, string2, length2, start, regs, stop)
344 struct re_pattern_buffer *bufp;
345 const char *string1, *string2;
346 Idx length1, length2, start, stop;
347 struct re_registers *regs;
349 return re_search_2_stub (bufp, string1, length1, string2, length2,
350 start, 0, regs, stop, true);
353 weak_alias (__re_match_2, re_match_2)
357 re_search_2 (bufp, string1, length1, string2, length2, start, range, regs, stop)
358 struct re_pattern_buffer *bufp;
359 const char *string1, *string2;
360 Idx length1, length2, start, stop;
362 struct re_registers *regs;
364 return re_search_2_stub (bufp, string1, length1, string2, length2,
365 start, range, regs, stop, false);
368 weak_alias (__re_search_2, re_search_2)
373 re_search_2_stub (struct re_pattern_buffer *bufp,
374 const char *string1, Idx length1,
375 const char *string2, Idx length2,
376 Idx start, regoff_t range, struct re_registers *regs,
377 Idx stop, bool ret_len)
381 Idx len = length1 + length2;
384 verify (! TYPE_SIGNED (Idx));
385 if (BE (len < length1, 0))
387 /* if (BE (length1 < 0 || length2 < 0 || stop < 0, 0))
390 /* Concatenate the strings. */
394 s = re_malloc (char, len);
396 if (BE (s == NULL, 0))
399 memcpy (__mempcpy (s, string1, length1), string2, length2);
401 memcpy (s, string1, length1);
402 memcpy (s + length1, string2, length2);
411 rval = re_search_stub (bufp, str, len, start, range, stop, regs,
417 /* The parameters have the same meaning as those of re_search.
418 Additional parameters:
419 If RET_LEN is true the length of the match is returned (re_match style);
420 otherwise the position of the match is returned. */
424 re_search_stub (struct re_pattern_buffer *bufp,
425 const char *string, Idx length,
426 Idx start, regoff_t range, Idx stop, struct re_registers *regs,
429 reg_errcode_t result;
435 re_dfa_t *dfa = (re_dfa_t *) bufp->buffer;
437 Idx last_start = start + range;
439 /* Check for out-of-range. */
440 verify (! TYPE_SIGNED (Idx));
441 /* if (BE (start < 0, 0))
443 if (BE (start > length, 0))
445 if (BE (length < last_start || (0 <= range && last_start < start), 0))
447 else if (BE (/* last_start < 0 || */ (range < 0 && start <= last_start), 0))
450 __libc_lock_lock (dfa->lock);
452 eflags |= (bufp->not_bol) ? REG_NOTBOL : 0;
453 eflags |= (bufp->not_eol) ? REG_NOTEOL : 0;
455 /* Compile fastmap if we haven't yet. */
456 if (start < last_start && bufp->fastmap != NULL && !bufp->fastmap_accurate)
457 re_compile_fastmap (bufp);
459 if (BE (bufp->no_sub, 0))
462 /* We need at least 1 register. */
465 else if (BE (bufp->regs_allocated == REGS_FIXED
466 && regs->num_regs <= bufp->re_nsub, 0))
468 nregs = regs->num_regs;
469 if (BE (nregs < 1, 0))
471 /* Nothing can be copied to regs. */
477 nregs = bufp->re_nsub + 1;
478 pmatch = re_malloc (regmatch_t, nregs);
479 if (BE (pmatch == NULL, 0))
485 result = re_search_internal (bufp, string, length, start, last_start, stop,
486 nregs, pmatch, eflags);
490 /* I hope we needn't fill ther regs with -1's when no match was found. */
491 if (result != REG_NOERROR)
493 else if (regs != NULL)
495 /* If caller wants register contents data back, copy them. */
496 bufp->regs_allocated = re_copy_regs (regs, pmatch, nregs,
497 bufp->regs_allocated);
498 if (BE (bufp->regs_allocated == REGS_UNALLOCATED, 0))
502 if (BE (rval == 0, 1))
506 assert (pmatch[0].rm_so == start);
507 rval = pmatch[0].rm_eo - start;
510 rval = pmatch[0].rm_so;
514 __libc_lock_unlock (dfa->lock);
520 re_copy_regs (struct re_registers *regs, regmatch_t *pmatch, Idx nregs,
523 int rval = REGS_REALLOCATE;
525 Idx need_regs = nregs + 1;
526 /* We need one extra element beyond `num_regs' for the `-1' marker GNU code
529 /* Have the register data arrays been allocated? */
530 if (regs_allocated == REGS_UNALLOCATED)
531 { /* No. So allocate them with malloc. */
532 regs->start = re_malloc (regoff_t, need_regs);
533 if (BE (regs->start == NULL, 0))
534 return REGS_UNALLOCATED;
535 regs->end = re_malloc (regoff_t, need_regs);
536 if (BE (regs->end == NULL, 0))
538 re_free (regs->start);
539 return REGS_UNALLOCATED;
541 regs->num_regs = need_regs;
543 else if (regs_allocated == REGS_REALLOCATE)
544 { /* Yes. If we need more elements than were already
545 allocated, reallocate them. If we need fewer, just
547 if (BE (need_regs > regs->num_regs, 0))
549 regoff_t *new_start = re_realloc (regs->start, regoff_t, need_regs);
551 if (BE (new_start == NULL, 0))
552 return REGS_UNALLOCATED;
553 new_end = re_realloc (regs->end, regoff_t, need_regs);
554 if (BE (new_end == NULL, 0))
557 return REGS_UNALLOCATED;
559 regs->start = new_start;
561 regs->num_regs = need_regs;
566 assert (regs_allocated == REGS_FIXED);
567 /* This function may not be called with REGS_FIXED and nregs too big. */
568 assert (regs->num_regs >= nregs);
573 for (i = 0; i < nregs; ++i)
575 regs->start[i] = pmatch[i].rm_so;
576 regs->end[i] = pmatch[i].rm_eo;
578 for ( ; i < regs->num_regs; ++i)
579 regs->start[i] = regs->end[i] = -1;
584 /* Set REGS to hold NUM_REGS registers, storing them in STARTS and
585 ENDS. Subsequent matches using PATTERN_BUFFER and REGS will use
586 this memory for recording register information. STARTS and ENDS
587 must be allocated using the malloc library routine, and must each
588 be at least NUM_REGS * sizeof (regoff_t) bytes long.
590 If NUM_REGS == 0, then subsequent matches should allocate their own
593 Unless this function is called, the first search or match using
594 PATTERN_BUFFER will allocate its own register data, without
595 freeing the old data. */
598 re_set_registers (bufp, regs, num_regs, starts, ends)
599 struct re_pattern_buffer *bufp;
600 struct re_registers *regs;
601 __re_size_t num_regs;
602 regoff_t *starts, *ends;
606 bufp->regs_allocated = REGS_REALLOCATE;
607 regs->num_regs = num_regs;
608 regs->start = starts;
613 bufp->regs_allocated = REGS_UNALLOCATED;
615 regs->start = regs->end = NULL;
619 weak_alias (__re_set_registers, re_set_registers)
622 /* Entry points compatible with 4.2 BSD regex library. We don't define
623 them unless specifically requested. */
625 #if defined _REGEX_RE_COMP || defined _LIBC
633 return 0 == regexec (&re_comp_buf, s, 0, NULL, 0);
635 #endif /* _REGEX_RE_COMP */
637 /* Internal entry point. */
639 /* Searches for a compiled pattern PREG in the string STRING, whose
640 length is LENGTH. NMATCH, PMATCH, and EFLAGS have the same
641 meaning as with regexec. LAST_START is START + RANGE, where
642 START and RANGE have the same meaning as with re_search.
643 Return REG_NOERROR if we find a match, and REG_NOMATCH if not,
644 otherwise return the error code.
645 Note: We assume front end functions already check ranges.
646 (0 <= LAST_START && LAST_START <= LENGTH) */
649 internal_function __attribute_warn_unused_result__
650 re_search_internal (const regex_t *preg,
651 const char *string, Idx length,
652 Idx start, Idx last_start, Idx stop,
653 size_t nmatch, regmatch_t pmatch[],
657 const re_dfa_t *dfa = (const re_dfa_t *) preg->buffer;
658 Idx left_lim, right_lim;
660 bool fl_longest_match;
663 Idx match_last = REG_MISSING;
667 #if defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L)
668 re_match_context_t mctx = { .dfa = dfa };
670 re_match_context_t mctx;
672 char *fastmap = ((preg->fastmap != NULL && preg->fastmap_accurate
673 && start != last_start && !preg->can_be_null)
674 ? preg->fastmap : NULL);
675 RE_TRANSLATE_TYPE t = preg->translate;
677 #if !(defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L))
678 memset (&mctx, '\0', sizeof (re_match_context_t));
682 extra_nmatch = (nmatch > preg->re_nsub) ? nmatch - (preg->re_nsub + 1) : 0;
683 nmatch -= extra_nmatch;
685 /* Check if the DFA haven't been compiled. */
686 if (BE (preg->used == 0 || dfa->init_state == NULL
687 || dfa->init_state_word == NULL || dfa->init_state_nl == NULL
688 || dfa->init_state_begbuf == NULL, 0))
692 /* We assume front-end functions already check them. */
693 assert (0 <= last_start && last_start <= length);
696 /* If initial states with non-begbuf contexts have no elements,
697 the regex must be anchored. If preg->newline_anchor is set,
698 we'll never use init_state_nl, so do not check it. */
699 if (dfa->init_state->nodes.nelem == 0
700 && dfa->init_state_word->nodes.nelem == 0
701 && (dfa->init_state_nl->nodes.nelem == 0
702 || !preg->newline_anchor))
704 if (start != 0 && last_start != 0)
706 start = last_start = 0;
709 /* We must check the longest matching, if nmatch > 0. */
710 fl_longest_match = (nmatch != 0 || dfa->nbackref);
712 err = re_string_allocate (&mctx.input, string, length, dfa->nodes_len + 1,
713 preg->translate, (preg->syntax & RE_ICASE) != 0,
715 if (BE (err != REG_NOERROR, 0))
717 mctx.input.stop = stop;
718 mctx.input.raw_stop = stop;
719 mctx.input.newline_anchor = preg->newline_anchor;
721 err = match_ctx_init (&mctx, eflags, dfa->nbackref * 2);
722 if (BE (err != REG_NOERROR, 0))
725 /* We will log all the DFA states through which the dfa pass,
726 if nmatch > 1, or this dfa has "multibyte node", which is a
727 back-reference or a node which can accept multibyte character or
728 multi character collating element. */
729 if (nmatch > 1 || dfa->has_mb_node)
731 /* Avoid overflow. */
732 if (BE (SIZE_MAX / sizeof (re_dfastate_t *) <= mctx.input.bufs_len, 0))
738 mctx.state_log = re_malloc (re_dfastate_t *, mctx.input.bufs_len + 1);
739 if (BE (mctx.state_log == NULL, 0))
746 mctx.state_log = NULL;
749 mctx.input.tip_context = (eflags & REG_NOTBOL) ? CONTEXT_BEGBUF
750 : CONTEXT_NEWLINE | CONTEXT_BEGBUF;
752 /* Check incrementally whether of not the input string match. */
753 incr = (last_start < start) ? -1 : 1;
754 left_lim = (last_start < start) ? last_start : start;
755 right_lim = (last_start < start) ? start : last_start;
756 sb = dfa->mb_cur_max == 1;
759 ? ((sb || !(preg->syntax & RE_ICASE || t) ? 4 : 0)
760 | (start <= last_start ? 2 : 0)
761 | (t != NULL ? 1 : 0))
764 for (;; match_first += incr)
767 if (match_first < left_lim || right_lim < match_first)
770 /* Advance as rapidly as possible through the string, until we
771 find a plausible place to start matching. This may be done
772 with varying efficiency, so there are various possibilities:
773 only the most common of them are specialized, in order to
774 save on code size. We use a switch statement for speed. */
782 /* Fastmap with single-byte translation, match forward. */
783 while (BE (match_first < right_lim, 1)
784 && !fastmap[t[(unsigned char) string[match_first]]])
786 goto forward_match_found_start_or_reached_end;
789 /* Fastmap without translation, match forward. */
790 while (BE (match_first < right_lim, 1)
791 && !fastmap[(unsigned char) string[match_first]])
794 forward_match_found_start_or_reached_end:
795 if (BE (match_first == right_lim, 0))
797 ch = match_first >= length
798 ? 0 : (unsigned char) string[match_first];
799 if (!fastmap[t ? t[ch] : ch])
806 /* Fastmap without multi-byte translation, match backwards. */
807 while (match_first >= left_lim)
809 ch = match_first >= length
810 ? 0 : (unsigned char) string[match_first];
811 if (fastmap[t ? t[ch] : ch])
815 if (match_first < left_lim)
820 /* In this case, we can't determine easily the current byte,
821 since it might be a component byte of a multibyte
822 character. Then we use the constructed buffer instead. */
825 /* If MATCH_FIRST is out of the valid range, reconstruct the
827 __re_size_t offset = match_first - mctx.input.raw_mbs_idx;
828 if (BE (offset >= (__re_size_t) mctx.input.valid_raw_len, 0))
830 err = re_string_reconstruct (&mctx.input, match_first,
832 if (BE (err != REG_NOERROR, 0))
835 offset = match_first - mctx.input.raw_mbs_idx;
837 /* If MATCH_FIRST is out of the buffer, leave it as '\0'.
838 Note that MATCH_FIRST must not be smaller than 0. */
839 ch = (match_first >= length
840 ? 0 : re_string_byte_at (&mctx.input, offset));
844 if (match_first < left_lim || match_first > right_lim)
853 /* Reconstruct the buffers so that the matcher can assume that
854 the matching starts from the beginning of the buffer. */
855 err = re_string_reconstruct (&mctx.input, match_first, eflags);
856 if (BE (err != REG_NOERROR, 0))
859 #ifdef RE_ENABLE_I18N
860 /* Don't consider this char as a possible match start if it part,
861 yet isn't the head, of a multibyte character. */
862 if (!sb && !re_string_first_byte (&mctx.input, 0))
866 /* It seems to be appropriate one, then use the matcher. */
867 /* We assume that the matching starts from 0. */
868 mctx.state_log_top = mctx.nbkref_ents = mctx.max_mb_elem_len = 0;
869 match_last = check_matching (&mctx, fl_longest_match,
870 start <= last_start ? &match_first : NULL);
871 if (match_last != REG_MISSING)
873 if (BE (match_last == REG_ERROR, 0))
880 mctx.match_last = match_last;
881 if ((!preg->no_sub && nmatch > 1) || dfa->nbackref)
883 re_dfastate_t *pstate = mctx.state_log[match_last];
884 mctx.last_node = check_halt_state_context (&mctx, pstate,
887 if ((!preg->no_sub && nmatch > 1 && dfa->has_plural_match)
890 err = prune_impossible_nodes (&mctx);
891 if (err == REG_NOERROR)
893 if (BE (err != REG_NOMATCH, 0))
895 match_last = REG_MISSING;
898 break; /* We found a match. */
902 match_ctx_clean (&mctx);
906 assert (match_last != REG_MISSING);
907 assert (err == REG_NOERROR);
910 /* Set pmatch[] if we need. */
915 /* Initialize registers. */
916 for (reg_idx = 1; reg_idx < nmatch; ++reg_idx)
917 pmatch[reg_idx].rm_so = pmatch[reg_idx].rm_eo = -1;
919 /* Set the points where matching start/end. */
921 pmatch[0].rm_eo = mctx.match_last;
922 /* FIXME: This function should fail if mctx.match_last exceeds
923 the maximum possible regoff_t value. We need a new error
924 code REG_OVERFLOW. */
926 if (!preg->no_sub && nmatch > 1)
928 err = set_regs (preg, &mctx, nmatch, pmatch,
929 dfa->has_plural_match && dfa->nbackref > 0);
930 if (BE (err != REG_NOERROR, 0))
934 /* At last, add the offset to the each registers, since we slided
935 the buffers so that we could assume that the matching starts
937 for (reg_idx = 0; reg_idx < nmatch; ++reg_idx)
938 if (pmatch[reg_idx].rm_so != -1)
940 #ifdef RE_ENABLE_I18N
941 if (BE (mctx.input.offsets_needed != 0, 0))
943 pmatch[reg_idx].rm_so =
944 (pmatch[reg_idx].rm_so == mctx.input.valid_len
945 ? mctx.input.valid_raw_len
946 : mctx.input.offsets[pmatch[reg_idx].rm_so]);
947 pmatch[reg_idx].rm_eo =
948 (pmatch[reg_idx].rm_eo == mctx.input.valid_len
949 ? mctx.input.valid_raw_len
950 : mctx.input.offsets[pmatch[reg_idx].rm_eo]);
953 assert (mctx.input.offsets_needed == 0);
955 pmatch[reg_idx].rm_so += match_first;
956 pmatch[reg_idx].rm_eo += match_first;
958 for (reg_idx = 0; reg_idx < extra_nmatch; ++reg_idx)
960 pmatch[nmatch + reg_idx].rm_so = -1;
961 pmatch[nmatch + reg_idx].rm_eo = -1;
965 for (reg_idx = 0; reg_idx + 1 < nmatch; reg_idx++)
966 if (dfa->subexp_map[reg_idx] != reg_idx)
968 pmatch[reg_idx + 1].rm_so
969 = pmatch[dfa->subexp_map[reg_idx] + 1].rm_so;
970 pmatch[reg_idx + 1].rm_eo
971 = pmatch[dfa->subexp_map[reg_idx] + 1].rm_eo;
976 re_free (mctx.state_log);
978 match_ctx_free (&mctx);
979 re_string_destruct (&mctx.input);
984 internal_function __attribute_warn_unused_result__
985 prune_impossible_nodes (re_match_context_t *mctx)
987 const re_dfa_t *const dfa = mctx->dfa;
988 Idx halt_node, match_last;
990 re_dfastate_t **sifted_states;
991 re_dfastate_t **lim_states = NULL;
992 re_sift_context_t sctx;
994 assert (mctx->state_log != NULL);
996 match_last = mctx->match_last;
997 halt_node = mctx->last_node;
999 /* Avoid overflow. */
1000 if (BE (SIZE_MAX / sizeof (re_dfastate_t *) <= match_last, 0))
1003 sifted_states = re_malloc (re_dfastate_t *, match_last + 1);
1004 if (BE (sifted_states == NULL, 0))
1011 lim_states = re_malloc (re_dfastate_t *, match_last + 1);
1012 if (BE (lim_states == NULL, 0))
1019 memset (lim_states, '\0',
1020 sizeof (re_dfastate_t *) * (match_last + 1));
1021 sift_ctx_init (&sctx, sifted_states, lim_states, halt_node,
1023 ret = sift_states_backward (mctx, &sctx);
1024 re_node_set_free (&sctx.limits);
1025 if (BE (ret != REG_NOERROR, 0))
1027 if (sifted_states[0] != NULL || lim_states[0] != NULL)
1032 if (! REG_VALID_INDEX (match_last))
1037 } while (mctx->state_log[match_last] == NULL
1038 || !mctx->state_log[match_last]->halt);
1039 halt_node = check_halt_state_context (mctx,
1040 mctx->state_log[match_last],
1043 ret = merge_state_array (dfa, sifted_states, lim_states,
1045 re_free (lim_states);
1047 if (BE (ret != REG_NOERROR, 0))
1052 sift_ctx_init (&sctx, sifted_states, lim_states, halt_node, match_last);
1053 ret = sift_states_backward (mctx, &sctx);
1054 re_node_set_free (&sctx.limits);
1055 if (BE (ret != REG_NOERROR, 0))
1057 if (sifted_states[0] == NULL)
1063 re_free (mctx->state_log);
1064 mctx->state_log = sifted_states;
1065 sifted_states = NULL;
1066 mctx->last_node = halt_node;
1067 mctx->match_last = match_last;
1070 re_free (sifted_states);
1071 re_free (lim_states);
1075 /* Acquire an initial state and return it.
1076 We must select appropriate initial state depending on the context,
1077 since initial states may have constraints like "\<", "^", etc.. */
1079 static inline re_dfastate_t *
1080 __attribute ((always_inline)) internal_function
1081 acquire_init_state_context (reg_errcode_t *err, const re_match_context_t *mctx,
1084 const re_dfa_t *const dfa = mctx->dfa;
1085 if (dfa->init_state->has_constraint)
1087 unsigned int context;
1088 context = re_string_context_at (&mctx->input, idx - 1, mctx->eflags);
1089 if (IS_WORD_CONTEXT (context))
1090 return dfa->init_state_word;
1091 else if (IS_ORDINARY_CONTEXT (context))
1092 return dfa->init_state;
1093 else if (IS_BEGBUF_CONTEXT (context) && IS_NEWLINE_CONTEXT (context))
1094 return dfa->init_state_begbuf;
1095 else if (IS_NEWLINE_CONTEXT (context))
1096 return dfa->init_state_nl;
1097 else if (IS_BEGBUF_CONTEXT (context))
1099 /* It is relatively rare case, then calculate on demand. */
1100 return re_acquire_state_context (err, dfa,
1101 dfa->init_state->entrance_nodes,
1105 /* Must not happen? */
1106 return dfa->init_state;
1109 return dfa->init_state;
1112 /* Check whether the regular expression match input string INPUT or not,
1113 and return the index where the matching end. Return REG_MISSING if
1114 there is no match, and return REG_ERROR in case of an error.
1115 FL_LONGEST_MATCH means we want the POSIX longest matching.
1116 If P_MATCH_FIRST is not NULL, and the match fails, it is set to the
1117 next place where we may want to try matching.
1118 Note that the matcher assume that the maching starts from the current
1119 index of the buffer. */
1122 internal_function __attribute_warn_unused_result__
1123 check_matching (re_match_context_t *mctx, bool fl_longest_match,
1126 const re_dfa_t *const dfa = mctx->dfa;
1129 Idx match_last = REG_MISSING;
1130 Idx cur_str_idx = re_string_cur_idx (&mctx->input);
1131 re_dfastate_t *cur_state;
1132 bool at_init_state = p_match_first != NULL;
1133 Idx next_start_idx = cur_str_idx;
1136 cur_state = acquire_init_state_context (&err, mctx, cur_str_idx);
1137 /* An initial state must not be NULL (invalid). */
1138 if (BE (cur_state == NULL, 0))
1140 assert (err == REG_ESPACE);
1144 if (mctx->state_log != NULL)
1146 mctx->state_log[cur_str_idx] = cur_state;
1148 /* Check OP_OPEN_SUBEXP in the initial state in case that we use them
1149 later. E.g. Processing back references. */
1150 if (BE (dfa->nbackref, 0))
1152 at_init_state = false;
1153 err = check_subexp_matching_top (mctx, &cur_state->nodes, 0);
1154 if (BE (err != REG_NOERROR, 0))
1157 if (cur_state->has_backref)
1159 err = transit_state_bkref (mctx, &cur_state->nodes);
1160 if (BE (err != REG_NOERROR, 0))
1166 /* If the RE accepts NULL string. */
1167 if (BE (cur_state->halt, 0))
1169 if (!cur_state->has_constraint
1170 || check_halt_state_context (mctx, cur_state, cur_str_idx))
1172 if (!fl_longest_match)
1176 match_last = cur_str_idx;
1182 while (!re_string_eoi (&mctx->input))
1184 re_dfastate_t *old_state = cur_state;
1185 Idx next_char_idx = re_string_cur_idx (&mctx->input) + 1;
1187 if (BE (next_char_idx >= mctx->input.bufs_len, 0)
1188 || (BE (next_char_idx >= mctx->input.valid_len, 0)
1189 && mctx->input.valid_len < mctx->input.len))
1191 err = extend_buffers (mctx);
1192 if (BE (err != REG_NOERROR, 0))
1194 assert (err == REG_ESPACE);
1199 cur_state = transit_state (&err, mctx, cur_state);
1200 if (mctx->state_log != NULL)
1201 cur_state = merge_state_with_log (&err, mctx, cur_state);
1203 if (cur_state == NULL)
1205 /* Reached the invalid state or an error. Try to recover a valid
1206 state using the state log, if available and if we have not
1207 already found a valid (even if not the longest) match. */
1208 if (BE (err != REG_NOERROR, 0))
1211 if (mctx->state_log == NULL
1212 || (match && !fl_longest_match)
1213 || (cur_state = find_recover_state (&err, mctx)) == NULL)
1217 if (BE (at_init_state, 0))
1219 if (old_state == cur_state)
1220 next_start_idx = next_char_idx;
1222 at_init_state = false;
1225 if (cur_state->halt)
1227 /* Reached a halt state.
1228 Check the halt state can satisfy the current context. */
1229 if (!cur_state->has_constraint
1230 || check_halt_state_context (mctx, cur_state,
1231 re_string_cur_idx (&mctx->input)))
1233 /* We found an appropriate halt state. */
1234 match_last = re_string_cur_idx (&mctx->input);
1237 /* We found a match, do not modify match_first below. */
1238 p_match_first = NULL;
1239 if (!fl_longest_match)
1246 *p_match_first += next_start_idx;
1251 /* Check NODE match the current context. */
1255 check_halt_node_context (const re_dfa_t *dfa, Idx node, unsigned int context)
1257 re_token_type_t type = dfa->nodes[node].type;
1258 unsigned int constraint = dfa->nodes[node].constraint;
1259 if (type != END_OF_RE)
1263 if (NOT_SATISFY_NEXT_CONSTRAINT (constraint, context))
1268 /* Check the halt state STATE match the current context.
1269 Return 0 if not match, if the node, STATE has, is a halt node and
1270 match the context, return the node. */
1274 check_halt_state_context (const re_match_context_t *mctx,
1275 const re_dfastate_t *state, Idx idx)
1278 unsigned int context;
1280 assert (state->halt);
1282 context = re_string_context_at (&mctx->input, idx, mctx->eflags);
1283 for (i = 0; i < state->nodes.nelem; ++i)
1284 if (check_halt_node_context (mctx->dfa, state->nodes.elems[i], context))
1285 return state->nodes.elems[i];
1289 /* Compute the next node to which "NFA" transit from NODE("NFA" is a NFA
1290 corresponding to the DFA).
1291 Return the destination node, and update EPS_VIA_NODES;
1292 return REG_MISSING in case of errors. */
1296 proceed_next_node (const re_match_context_t *mctx, Idx nregs, regmatch_t *regs,
1297 Idx *pidx, Idx node, re_node_set *eps_via_nodes,
1298 struct re_fail_stack_t *fs)
1300 const re_dfa_t *const dfa = mctx->dfa;
1303 if (IS_EPSILON_NODE (dfa->nodes[node].type))
1305 re_node_set *cur_nodes = &mctx->state_log[*pidx]->nodes;
1306 re_node_set *edests = &dfa->edests[node];
1308 ok = re_node_set_insert (eps_via_nodes, node);
1311 /* Pick up a valid destination, or return REG_MISSING if none
1313 for (dest_node = REG_MISSING, i = 0; i < edests->nelem; ++i)
1315 Idx candidate = edests->elems[i];
1316 if (!re_node_set_contains (cur_nodes, candidate))
1318 if (dest_node == REG_MISSING)
1319 dest_node = candidate;
1323 /* In order to avoid infinite loop like "(a*)*", return the second
1324 epsilon-transition if the first was already considered. */
1325 if (re_node_set_contains (eps_via_nodes, dest_node))
1328 /* Otherwise, push the second epsilon-transition on the fail stack. */
1330 && push_fail_stack (fs, *pidx, candidate, nregs, regs,
1334 /* We know we are going to exit. */
1343 re_token_type_t type = dfa->nodes[node].type;
1345 #ifdef RE_ENABLE_I18N
1346 if (dfa->nodes[node].accept_mb)
1347 naccepted = check_node_accept_bytes (dfa, node, &mctx->input, *pidx);
1349 #endif /* RE_ENABLE_I18N */
1350 if (type == OP_BACK_REF)
1352 Idx subexp_idx = dfa->nodes[node].opr.idx + 1;
1353 naccepted = regs[subexp_idx].rm_eo - regs[subexp_idx].rm_so;
1356 if (regs[subexp_idx].rm_so == -1 || regs[subexp_idx].rm_eo == -1)
1360 char *buf = (char *) re_string_get_buffer (&mctx->input);
1361 if (memcmp (buf + regs[subexp_idx].rm_so, buf + *pidx,
1370 ok = re_node_set_insert (eps_via_nodes, node);
1373 dest_node = dfa->edests[node].elems[0];
1374 if (re_node_set_contains (&mctx->state_log[*pidx]->nodes,
1381 || check_node_accept (mctx, dfa->nodes + node, *pidx))
1383 Idx dest_node = dfa->nexts[node];
1384 *pidx = (naccepted == 0) ? *pidx + 1 : *pidx + naccepted;
1385 if (fs && (*pidx > mctx->match_last || mctx->state_log[*pidx] == NULL
1386 || !re_node_set_contains (&mctx->state_log[*pidx]->nodes,
1389 re_node_set_empty (eps_via_nodes);
1396 static reg_errcode_t
1397 internal_function __attribute_warn_unused_result__
1398 push_fail_stack (struct re_fail_stack_t *fs, Idx str_idx, Idx dest_node,
1399 Idx nregs, regmatch_t *regs, re_node_set *eps_via_nodes)
1402 Idx num = fs->num++;
1403 if (fs->num == fs->alloc)
1405 struct re_fail_stack_ent_t *new_array;
1406 new_array = realloc (fs->stack, (sizeof (struct re_fail_stack_ent_t)
1408 if (new_array == NULL)
1411 fs->stack = new_array;
1413 fs->stack[num].idx = str_idx;
1414 fs->stack[num].node = dest_node;
1415 fs->stack[num].regs = re_malloc (regmatch_t, nregs);
1416 if (fs->stack[num].regs == NULL)
1418 memcpy (fs->stack[num].regs, regs, sizeof (regmatch_t) * nregs);
1419 err = re_node_set_init_copy (&fs->stack[num].eps_via_nodes, eps_via_nodes);
1425 pop_fail_stack (struct re_fail_stack_t *fs, Idx *pidx, Idx nregs,
1426 regmatch_t *regs, re_node_set *eps_via_nodes)
1428 Idx num = --fs->num;
1429 assert (REG_VALID_INDEX (num));
1430 *pidx = fs->stack[num].idx;
1431 memcpy (regs, fs->stack[num].regs, sizeof (regmatch_t) * nregs);
1432 re_node_set_free (eps_via_nodes);
1433 re_free (fs->stack[num].regs);
1434 *eps_via_nodes = fs->stack[num].eps_via_nodes;
1435 return fs->stack[num].node;
1438 /* Set the positions where the subexpressions are starts/ends to registers
1440 Note: We assume that pmatch[0] is already set, and
1441 pmatch[i].rm_so == pmatch[i].rm_eo == -1 for 0 < i < nmatch. */
1443 static reg_errcode_t
1444 internal_function __attribute_warn_unused_result__
1445 set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
1446 regmatch_t *pmatch, bool fl_backtrack)
1448 const re_dfa_t *dfa = (const re_dfa_t *) preg->buffer;
1450 re_node_set eps_via_nodes;
1451 struct re_fail_stack_t *fs;
1452 struct re_fail_stack_t fs_body = { 0, 2, NULL };
1453 regmatch_t *prev_idx_match;
1454 bool prev_idx_match_malloced = false;
1457 assert (nmatch > 1);
1458 assert (mctx->state_log != NULL);
1463 fs->stack = re_malloc (struct re_fail_stack_ent_t, fs->alloc);
1464 if (fs->stack == NULL)
1470 cur_node = dfa->init_node;
1471 re_node_set_init_empty (&eps_via_nodes);
1473 if (__libc_use_alloca (nmatch * sizeof (regmatch_t)))
1474 prev_idx_match = (regmatch_t *) alloca (nmatch * sizeof (regmatch_t));
1477 prev_idx_match = re_malloc (regmatch_t, nmatch);
1478 if (prev_idx_match == NULL)
1480 free_fail_stack_return (fs);
1483 prev_idx_match_malloced = true;
1485 memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
1487 for (idx = pmatch[0].rm_so; idx <= pmatch[0].rm_eo ;)
1489 update_regs (dfa, pmatch, prev_idx_match, cur_node, idx, nmatch);
1491 if (idx == pmatch[0].rm_eo && cur_node == mctx->last_node)
1496 for (reg_idx = 0; reg_idx < nmatch; ++reg_idx)
1497 if (pmatch[reg_idx].rm_so > -1 && pmatch[reg_idx].rm_eo == -1)
1499 if (reg_idx == nmatch)
1501 re_node_set_free (&eps_via_nodes);
1502 if (prev_idx_match_malloced)
1503 re_free (prev_idx_match);
1504 return free_fail_stack_return (fs);
1506 cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
1511 re_node_set_free (&eps_via_nodes);
1512 if (prev_idx_match_malloced)
1513 re_free (prev_idx_match);
1518 /* Proceed to next node. */
1519 cur_node = proceed_next_node (mctx, nmatch, pmatch, &idx, cur_node,
1520 &eps_via_nodes, fs);
1522 if (BE (! REG_VALID_INDEX (cur_node), 0))
1524 if (BE (cur_node == REG_ERROR, 0))
1526 re_node_set_free (&eps_via_nodes);
1527 if (prev_idx_match_malloced)
1528 re_free (prev_idx_match);
1529 free_fail_stack_return (fs);
1533 cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
1537 re_node_set_free (&eps_via_nodes);
1538 if (prev_idx_match_malloced)
1539 re_free (prev_idx_match);
1544 re_node_set_free (&eps_via_nodes);
1545 if (prev_idx_match_malloced)
1546 re_free (prev_idx_match);
1547 return free_fail_stack_return (fs);
1550 static reg_errcode_t
1552 free_fail_stack_return (struct re_fail_stack_t *fs)
1557 for (fs_idx = 0; fs_idx < fs->num; ++fs_idx)
1559 re_node_set_free (&fs->stack[fs_idx].eps_via_nodes);
1560 re_free (fs->stack[fs_idx].regs);
1562 re_free (fs->stack);
1569 update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
1570 regmatch_t *prev_idx_match, Idx cur_node, Idx cur_idx, Idx nmatch)
1572 int type = dfa->nodes[cur_node].type;
1573 if (type == OP_OPEN_SUBEXP)
1575 Idx reg_num = dfa->nodes[cur_node].opr.idx + 1;
1577 /* We are at the first node of this sub expression. */
1578 if (reg_num < nmatch)
1580 pmatch[reg_num].rm_so = cur_idx;
1581 pmatch[reg_num].rm_eo = -1;
1584 else if (type == OP_CLOSE_SUBEXP)
1586 Idx reg_num = dfa->nodes[cur_node].opr.idx + 1;
1587 if (reg_num < nmatch)
1589 /* We are at the last node of this sub expression. */
1590 if (pmatch[reg_num].rm_so < cur_idx)
1592 pmatch[reg_num].rm_eo = cur_idx;
1593 /* This is a non-empty match or we are not inside an optional
1594 subexpression. Accept this right away. */
1595 memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
1599 if (dfa->nodes[cur_node].opt_subexp
1600 && prev_idx_match[reg_num].rm_so != -1)
1601 /* We transited through an empty match for an optional
1602 subexpression, like (a?)*, and this is not the subexp's
1603 first match. Copy back the old content of the registers
1604 so that matches of an inner subexpression are undone as
1605 well, like in ((a?))*. */
1606 memcpy (pmatch, prev_idx_match, sizeof (regmatch_t) * nmatch);
1608 /* We completed a subexpression, but it may be part of
1609 an optional one, so do not update PREV_IDX_MATCH. */
1610 pmatch[reg_num].rm_eo = cur_idx;
1616 /* This function checks the STATE_LOG from the SCTX->last_str_idx to 0
1617 and sift the nodes in each states according to the following rules.
1618 Updated state_log will be wrote to STATE_LOG.
1620 Rules: We throw away the Node `a' in the STATE_LOG[STR_IDX] if...
1621 1. When STR_IDX == MATCH_LAST(the last index in the state_log):
1622 If `a' isn't the LAST_NODE and `a' can't epsilon transit to
1623 the LAST_NODE, we throw away the node `a'.
1624 2. When 0 <= STR_IDX < MATCH_LAST and `a' accepts
1625 string `s' and transit to `b':
1626 i. If 'b' isn't in the STATE_LOG[STR_IDX+strlen('s')], we throw
1628 ii. If 'b' is in the STATE_LOG[STR_IDX+strlen('s')] but 'b' is
1629 thrown away, we throw away the node `a'.
1630 3. When 0 <= STR_IDX < MATCH_LAST and 'a' epsilon transit to 'b':
1631 i. If 'b' isn't in the STATE_LOG[STR_IDX], we throw away the
1633 ii. If 'b' is in the STATE_LOG[STR_IDX] but 'b' is thrown away,
1634 we throw away the node `a'. */
1636 #define STATE_NODE_CONTAINS(state,node) \
1637 ((state) != NULL && re_node_set_contains (&(state)->nodes, node))
1639 static reg_errcode_t
1641 sift_states_backward (const re_match_context_t *mctx, re_sift_context_t *sctx)
1645 Idx str_idx = sctx->last_str_idx;
1646 re_node_set cur_dest;
1649 assert (mctx->state_log != NULL && mctx->state_log[str_idx] != NULL);
1652 /* Build sifted state_log[str_idx]. It has the nodes which can epsilon
1653 transit to the last_node and the last_node itself. */
1654 err = re_node_set_init_1 (&cur_dest, sctx->last_node);
1655 if (BE (err != REG_NOERROR, 0))
1657 err = update_cur_sifted_state (mctx, sctx, str_idx, &cur_dest);
1658 if (BE (err != REG_NOERROR, 0))
1661 /* Then check each states in the state_log. */
1664 /* Update counters. */
1665 null_cnt = (sctx->sifted_states[str_idx] == NULL) ? null_cnt + 1 : 0;
1666 if (null_cnt > mctx->max_mb_elem_len)
1668 memset (sctx->sifted_states, '\0',
1669 sizeof (re_dfastate_t *) * str_idx);
1670 re_node_set_free (&cur_dest);
1673 re_node_set_empty (&cur_dest);
1676 if (mctx->state_log[str_idx])
1678 err = build_sifted_states (mctx, sctx, str_idx, &cur_dest);
1679 if (BE (err != REG_NOERROR, 0))
1683 /* Add all the nodes which satisfy the following conditions:
1684 - It can epsilon transit to a node in CUR_DEST.
1686 And update state_log. */
1687 err = update_cur_sifted_state (mctx, sctx, str_idx, &cur_dest);
1688 if (BE (err != REG_NOERROR, 0))
1693 re_node_set_free (&cur_dest);
1697 static reg_errcode_t
1698 internal_function __attribute_warn_unused_result__
1699 build_sifted_states (const re_match_context_t *mctx, re_sift_context_t *sctx,
1700 Idx str_idx, re_node_set *cur_dest)
1702 const re_dfa_t *const dfa = mctx->dfa;
1703 const re_node_set *cur_src = &mctx->state_log[str_idx]->non_eps_nodes;
1706 /* Then build the next sifted state.
1707 We build the next sifted state on `cur_dest', and update
1708 `sifted_states[str_idx]' with `cur_dest'.
1710 `cur_dest' is the sifted state from `state_log[str_idx + 1]'.
1711 `cur_src' points the node_set of the old `state_log[str_idx]'
1712 (with the epsilon nodes pre-filtered out). */
1713 for (i = 0; i < cur_src->nelem; i++)
1715 Idx prev_node = cur_src->elems[i];
1720 re_token_type_t type = dfa->nodes[prev_node].type;
1721 assert (!IS_EPSILON_NODE (type));
1723 #ifdef RE_ENABLE_I18N
1724 /* If the node may accept `multi byte'. */
1725 if (dfa->nodes[prev_node].accept_mb)
1726 naccepted = sift_states_iter_mb (mctx, sctx, prev_node,
1727 str_idx, sctx->last_str_idx);
1728 #endif /* RE_ENABLE_I18N */
1730 /* We don't check backreferences here.
1731 See update_cur_sifted_state(). */
1733 && check_node_accept (mctx, dfa->nodes + prev_node, str_idx)
1734 && STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + 1],
1735 dfa->nexts[prev_node]))
1741 if (sctx->limits.nelem)
1743 Idx to_idx = str_idx + naccepted;
1744 if (check_dst_limits (mctx, &sctx->limits,
1745 dfa->nexts[prev_node], to_idx,
1746 prev_node, str_idx))
1749 ok = re_node_set_insert (cur_dest, prev_node);
1757 /* Helper functions. */
1759 static reg_errcode_t
1761 clean_state_log_if_needed (re_match_context_t *mctx, Idx next_state_log_idx)
1763 Idx top = mctx->state_log_top;
1765 if (next_state_log_idx >= mctx->input.bufs_len
1766 || (next_state_log_idx >= mctx->input.valid_len
1767 && mctx->input.valid_len < mctx->input.len))
1770 err = extend_buffers (mctx);
1771 if (BE (err != REG_NOERROR, 0))
1775 if (top < next_state_log_idx)
1777 memset (mctx->state_log + top + 1, '\0',
1778 sizeof (re_dfastate_t *) * (next_state_log_idx - top));
1779 mctx->state_log_top = next_state_log_idx;
1784 static reg_errcode_t
1786 merge_state_array (const re_dfa_t *dfa, re_dfastate_t **dst,
1787 re_dfastate_t **src, Idx num)
1791 for (st_idx = 0; st_idx < num; ++st_idx)
1793 if (dst[st_idx] == NULL)
1794 dst[st_idx] = src[st_idx];
1795 else if (src[st_idx] != NULL)
1797 re_node_set merged_set;
1798 err = re_node_set_init_union (&merged_set, &dst[st_idx]->nodes,
1799 &src[st_idx]->nodes);
1800 if (BE (err != REG_NOERROR, 0))
1802 dst[st_idx] = re_acquire_state (&err, dfa, &merged_set);
1803 re_node_set_free (&merged_set);
1804 if (BE (err != REG_NOERROR, 0))
1811 static reg_errcode_t
1813 update_cur_sifted_state (const re_match_context_t *mctx,
1814 re_sift_context_t *sctx, Idx str_idx,
1815 re_node_set *dest_nodes)
1817 const re_dfa_t *const dfa = mctx->dfa;
1818 reg_errcode_t err = REG_NOERROR;
1819 const re_node_set *candidates;
1820 candidates = ((mctx->state_log[str_idx] == NULL) ? NULL
1821 : &mctx->state_log[str_idx]->nodes);
1823 if (dest_nodes->nelem == 0)
1824 sctx->sifted_states[str_idx] = NULL;
1829 /* At first, add the nodes which can epsilon transit to a node in
1831 err = add_epsilon_src_nodes (dfa, dest_nodes, candidates);
1832 if (BE (err != REG_NOERROR, 0))
1835 /* Then, check the limitations in the current sift_context. */
1836 if (sctx->limits.nelem)
1838 err = check_subexp_limits (dfa, dest_nodes, candidates, &sctx->limits,
1839 mctx->bkref_ents, str_idx);
1840 if (BE (err != REG_NOERROR, 0))
1845 sctx->sifted_states[str_idx] = re_acquire_state (&err, dfa, dest_nodes);
1846 if (BE (err != REG_NOERROR, 0))
1850 if (candidates && mctx->state_log[str_idx]->has_backref)
1852 err = sift_states_bkref (mctx, sctx, str_idx, candidates);
1853 if (BE (err != REG_NOERROR, 0))
1859 static reg_errcode_t
1860 internal_function __attribute_warn_unused_result__
1861 add_epsilon_src_nodes (const re_dfa_t *dfa, re_node_set *dest_nodes,
1862 const re_node_set *candidates)
1864 reg_errcode_t err = REG_NOERROR;
1867 re_dfastate_t *state = re_acquire_state (&err, dfa, dest_nodes);
1868 if (BE (err != REG_NOERROR, 0))
1871 if (!state->inveclosure.alloc)
1873 err = re_node_set_alloc (&state->inveclosure, dest_nodes->nelem);
1874 if (BE (err != REG_NOERROR, 0))
1876 for (i = 0; i < dest_nodes->nelem; i++)
1878 err = re_node_set_merge (&state->inveclosure,
1879 dfa->inveclosures + dest_nodes->elems[i]);
1880 if (BE (err != REG_NOERROR, 0))
1884 return re_node_set_add_intersect (dest_nodes, candidates,
1885 &state->inveclosure);
1888 static reg_errcode_t
1890 sub_epsilon_src_nodes (const re_dfa_t *dfa, Idx node, re_node_set *dest_nodes,
1891 const re_node_set *candidates)
1895 re_node_set *inv_eclosure = dfa->inveclosures + node;
1896 re_node_set except_nodes;
1897 re_node_set_init_empty (&except_nodes);
1898 for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx)
1900 Idx cur_node = inv_eclosure->elems[ecl_idx];
1901 if (cur_node == node)
1903 if (IS_EPSILON_NODE (dfa->nodes[cur_node].type))
1905 Idx edst1 = dfa->edests[cur_node].elems[0];
1906 Idx edst2 = ((dfa->edests[cur_node].nelem > 1)
1907 ? dfa->edests[cur_node].elems[1] : REG_MISSING);
1908 if ((!re_node_set_contains (inv_eclosure, edst1)
1909 && re_node_set_contains (dest_nodes, edst1))
1910 || (REG_VALID_NONZERO_INDEX (edst2)
1911 && !re_node_set_contains (inv_eclosure, edst2)
1912 && re_node_set_contains (dest_nodes, edst2)))
1914 err = re_node_set_add_intersect (&except_nodes, candidates,
1915 dfa->inveclosures + cur_node);
1916 if (BE (err != REG_NOERROR, 0))
1918 re_node_set_free (&except_nodes);
1924 for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx)
1926 Idx cur_node = inv_eclosure->elems[ecl_idx];
1927 if (!re_node_set_contains (&except_nodes, cur_node))
1929 Idx idx = re_node_set_contains (dest_nodes, cur_node) - 1;
1930 re_node_set_remove_at (dest_nodes, idx);
1933 re_node_set_free (&except_nodes);
1939 check_dst_limits (const re_match_context_t *mctx, const re_node_set *limits,
1940 Idx dst_node, Idx dst_idx, Idx src_node, Idx src_idx)
1942 const re_dfa_t *const dfa = mctx->dfa;
1943 Idx lim_idx, src_pos, dst_pos;
1945 Idx dst_bkref_idx = search_cur_bkref_entry (mctx, dst_idx);
1946 Idx src_bkref_idx = search_cur_bkref_entry (mctx, src_idx);
1947 for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx)
1950 struct re_backref_cache_entry *ent;
1951 ent = mctx->bkref_ents + limits->elems[lim_idx];
1952 subexp_idx = dfa->nodes[ent->node].opr.idx;
1954 dst_pos = check_dst_limits_calc_pos (mctx, limits->elems[lim_idx],
1955 subexp_idx, dst_node, dst_idx,
1957 src_pos = check_dst_limits_calc_pos (mctx, limits->elems[lim_idx],
1958 subexp_idx, src_node, src_idx,
1962 <src> <dst> ( <subexp> )
1963 ( <subexp> ) <src> <dst>
1964 ( <subexp1> <src> <subexp2> <dst> <subexp3> ) */
1965 if (src_pos == dst_pos)
1966 continue; /* This is unrelated limitation. */
1975 check_dst_limits_calc_pos_1 (const re_match_context_t *mctx, int boundaries,
1976 Idx subexp_idx, Idx from_node, Idx bkref_idx)
1978 const re_dfa_t *const dfa = mctx->dfa;
1979 const re_node_set *eclosures = dfa->eclosures + from_node;
1982 /* Else, we are on the boundary: examine the nodes on the epsilon
1984 for (node_idx = 0; node_idx < eclosures->nelem; ++node_idx)
1986 Idx node = eclosures->elems[node_idx];
1987 switch (dfa->nodes[node].type)
1990 if (bkref_idx != REG_MISSING)
1992 struct re_backref_cache_entry *ent = mctx->bkref_ents + bkref_idx;
1998 if (ent->node != node)
2001 if (subexp_idx < BITSET_WORD_BITS
2002 && !(ent->eps_reachable_subexps_map
2003 & ((bitset_word_t) 1 << subexp_idx)))
2006 /* Recurse trying to reach the OP_OPEN_SUBEXP and
2007 OP_CLOSE_SUBEXP cases below. But, if the
2008 destination node is the same node as the source
2009 node, don't recurse because it would cause an
2010 infinite loop: a regex that exhibits this behavior
2012 dst = dfa->edests[node].elems[0];
2013 if (dst == from_node)
2017 else /* if (boundaries & 2) */
2022 check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx,
2024 if (cpos == -1 /* && (boundaries & 1) */)
2026 if (cpos == 0 && (boundaries & 2))
2029 if (subexp_idx < BITSET_WORD_BITS)
2030 ent->eps_reachable_subexps_map
2031 &= ~((bitset_word_t) 1 << subexp_idx);
2033 while (ent++->more);
2037 case OP_OPEN_SUBEXP:
2038 if ((boundaries & 1) && subexp_idx == dfa->nodes[node].opr.idx)
2042 case OP_CLOSE_SUBEXP:
2043 if ((boundaries & 2) && subexp_idx == dfa->nodes[node].opr.idx)
2052 return (boundaries & 2) ? 1 : 0;
2057 check_dst_limits_calc_pos (const re_match_context_t *mctx, Idx limit,
2058 Idx subexp_idx, Idx from_node, Idx str_idx,
2061 struct re_backref_cache_entry *lim = mctx->bkref_ents + limit;
2064 /* If we are outside the range of the subexpression, return -1 or 1. */
2065 if (str_idx < lim->subexp_from)
2068 if (lim->subexp_to < str_idx)
2071 /* If we are within the subexpression, return 0. */
2072 boundaries = (str_idx == lim->subexp_from);
2073 boundaries |= (str_idx == lim->subexp_to) << 1;
2074 if (boundaries == 0)
2077 /* Else, examine epsilon closure. */
2078 return check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx,
2079 from_node, bkref_idx);
2082 /* Check the limitations of sub expressions LIMITS, and remove the nodes
2083 which are against limitations from DEST_NODES. */
2085 static reg_errcode_t
2087 check_subexp_limits (const re_dfa_t *dfa, re_node_set *dest_nodes,
2088 const re_node_set *candidates, re_node_set *limits,
2089 struct re_backref_cache_entry *bkref_ents, Idx str_idx)
2092 Idx node_idx, lim_idx;
2094 for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx)
2097 struct re_backref_cache_entry *ent;
2098 ent = bkref_ents + limits->elems[lim_idx];
2100 if (str_idx <= ent->subexp_from || ent->str_idx < str_idx)
2101 continue; /* This is unrelated limitation. */
2103 subexp_idx = dfa->nodes[ent->node].opr.idx;
2104 if (ent->subexp_to == str_idx)
2106 Idx ops_node = REG_MISSING;
2107 Idx cls_node = REG_MISSING;
2108 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2110 Idx node = dest_nodes->elems[node_idx];
2111 re_token_type_t type = dfa->nodes[node].type;
2112 if (type == OP_OPEN_SUBEXP
2113 && subexp_idx == dfa->nodes[node].opr.idx)
2115 else if (type == OP_CLOSE_SUBEXP
2116 && subexp_idx == dfa->nodes[node].opr.idx)
2120 /* Check the limitation of the open subexpression. */
2121 /* Note that (ent->subexp_to = str_idx != ent->subexp_from). */
2122 if (REG_VALID_INDEX (ops_node))
2124 err = sub_epsilon_src_nodes (dfa, ops_node, dest_nodes,
2126 if (BE (err != REG_NOERROR, 0))
2130 /* Check the limitation of the close subexpression. */
2131 if (REG_VALID_INDEX (cls_node))
2132 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2134 Idx node = dest_nodes->elems[node_idx];
2135 if (!re_node_set_contains (dfa->inveclosures + node,
2137 && !re_node_set_contains (dfa->eclosures + node,
2140 /* It is against this limitation.
2141 Remove it form the current sifted state. */
2142 err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2144 if (BE (err != REG_NOERROR, 0))
2150 else /* (ent->subexp_to != str_idx) */
2152 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2154 Idx node = dest_nodes->elems[node_idx];
2155 re_token_type_t type = dfa->nodes[node].type;
2156 if (type == OP_CLOSE_SUBEXP || type == OP_OPEN_SUBEXP)
2158 if (subexp_idx != dfa->nodes[node].opr.idx)
2160 /* It is against this limitation.
2161 Remove it form the current sifted state. */
2162 err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2164 if (BE (err != REG_NOERROR, 0))
2173 static reg_errcode_t
2174 internal_function __attribute_warn_unused_result__
2175 sift_states_bkref (const re_match_context_t *mctx, re_sift_context_t *sctx,
2176 Idx str_idx, const re_node_set *candidates)
2178 const re_dfa_t *const dfa = mctx->dfa;
2181 re_sift_context_t local_sctx;
2182 Idx first_idx = search_cur_bkref_entry (mctx, str_idx);
2184 if (first_idx == REG_MISSING)
2187 local_sctx.sifted_states = NULL; /* Mark that it hasn't been initialized. */
2189 for (node_idx = 0; node_idx < candidates->nelem; ++node_idx)
2192 re_token_type_t type;
2193 struct re_backref_cache_entry *entry;
2194 node = candidates->elems[node_idx];
2195 type = dfa->nodes[node].type;
2196 /* Avoid infinite loop for the REs like "()\1+". */
2197 if (node == sctx->last_node && str_idx == sctx->last_str_idx)
2199 if (type != OP_BACK_REF)
2202 entry = mctx->bkref_ents + first_idx;
2203 enabled_idx = first_idx;
2210 re_dfastate_t *cur_state;
2212 if (entry->node != node)
2214 subexp_len = entry->subexp_to - entry->subexp_from;
2215 to_idx = str_idx + subexp_len;
2216 dst_node = (subexp_len ? dfa->nexts[node]
2217 : dfa->edests[node].elems[0]);
2219 if (to_idx > sctx->last_str_idx
2220 || sctx->sifted_states[to_idx] == NULL
2221 || !STATE_NODE_CONTAINS (sctx->sifted_states[to_idx], dst_node)
2222 || check_dst_limits (mctx, &sctx->limits, node,
2223 str_idx, dst_node, to_idx))
2226 if (local_sctx.sifted_states == NULL)
2229 err = re_node_set_init_copy (&local_sctx.limits, &sctx->limits);
2230 if (BE (err != REG_NOERROR, 0))
2233 local_sctx.last_node = node;
2234 local_sctx.last_str_idx = str_idx;
2235 ok = re_node_set_insert (&local_sctx.limits, enabled_idx);
2241 cur_state = local_sctx.sifted_states[str_idx];
2242 err = sift_states_backward (mctx, &local_sctx);
2243 if (BE (err != REG_NOERROR, 0))
2245 if (sctx->limited_states != NULL)
2247 err = merge_state_array (dfa, sctx->limited_states,
2248 local_sctx.sifted_states,
2250 if (BE (err != REG_NOERROR, 0))
2253 local_sctx.sifted_states[str_idx] = cur_state;
2254 re_node_set_remove (&local_sctx.limits, enabled_idx);
2256 /* mctx->bkref_ents may have changed, reload the pointer. */
2257 entry = mctx->bkref_ents + enabled_idx;
2259 while (enabled_idx++, entry++->more);
2263 if (local_sctx.sifted_states != NULL)
2265 re_node_set_free (&local_sctx.limits);
2272 #ifdef RE_ENABLE_I18N
2275 sift_states_iter_mb (const re_match_context_t *mctx, re_sift_context_t *sctx,
2276 Idx node_idx, Idx str_idx, Idx max_str_idx)
2278 const re_dfa_t *const dfa = mctx->dfa;
2280 /* Check the node can accept `multi byte'. */
2281 naccepted = check_node_accept_bytes (dfa, node_idx, &mctx->input, str_idx);
2282 if (naccepted > 0 && str_idx + naccepted <= max_str_idx &&
2283 !STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + naccepted],
2284 dfa->nexts[node_idx]))
2285 /* The node can't accept the `multi byte', or the
2286 destination was already thrown away, then the node
2287 could't accept the current input `multi byte'. */
2289 /* Otherwise, it is sure that the node could accept
2290 `naccepted' bytes input. */
2293 #endif /* RE_ENABLE_I18N */
2296 /* Functions for state transition. */
2298 /* Return the next state to which the current state STATE will transit by
2299 accepting the current input byte, and update STATE_LOG if necessary.
2300 If STATE can accept a multibyte char/collating element/back reference
2301 update the destination of STATE_LOG. */
2303 static re_dfastate_t *
2304 internal_function __attribute_warn_unused_result__
2305 transit_state (reg_errcode_t *err, re_match_context_t *mctx,
2306 re_dfastate_t *state)
2308 re_dfastate_t **trtable;
2311 #ifdef RE_ENABLE_I18N
2312 /* If the current state can accept multibyte. */
2313 if (BE (state->accept_mb, 0))
2315 *err = transit_state_mb (mctx, state);
2316 if (BE (*err != REG_NOERROR, 0))
2319 #endif /* RE_ENABLE_I18N */
2321 /* Then decide the next state with the single byte. */
2324 /* don't use transition table */
2325 return transit_state_sb (err, mctx, state);
2328 /* Use transition table */
2329 ch = re_string_fetch_byte (&mctx->input);
2332 trtable = state->trtable;
2333 if (BE (trtable != NULL, 1))
2336 trtable = state->word_trtable;
2337 if (BE (trtable != NULL, 1))
2339 unsigned int context;
2341 = re_string_context_at (&mctx->input,
2342 re_string_cur_idx (&mctx->input) - 1,
2344 if (IS_WORD_CONTEXT (context))
2345 return trtable[ch + SBC_MAX];
2350 if (!build_trtable (mctx->dfa, state))
2356 /* Retry, we now have a transition table. */
2360 /* Update the state_log if we need */
2361 static re_dfastate_t *
2363 merge_state_with_log (reg_errcode_t *err, re_match_context_t *mctx,
2364 re_dfastate_t *next_state)
2366 const re_dfa_t *const dfa = mctx->dfa;
2367 Idx cur_idx = re_string_cur_idx (&mctx->input);
2369 if (cur_idx > mctx->state_log_top)
2371 mctx->state_log[cur_idx] = next_state;
2372 mctx->state_log_top = cur_idx;
2374 else if (mctx->state_log[cur_idx] == 0)
2376 mctx->state_log[cur_idx] = next_state;
2380 re_dfastate_t *pstate;
2381 unsigned int context;
2382 re_node_set next_nodes, *log_nodes, *table_nodes = NULL;
2383 /* If (state_log[cur_idx] != 0), it implies that cur_idx is
2384 the destination of a multibyte char/collating element/
2385 back reference. Then the next state is the union set of
2386 these destinations and the results of the transition table. */
2387 pstate = mctx->state_log[cur_idx];
2388 log_nodes = pstate->entrance_nodes;
2389 if (next_state != NULL)
2391 table_nodes = next_state->entrance_nodes;
2392 *err = re_node_set_init_union (&next_nodes, table_nodes,
2394 if (BE (*err != REG_NOERROR, 0))
2398 next_nodes = *log_nodes;
2399 /* Note: We already add the nodes of the initial state,
2400 then we don't need to add them here. */
2402 context = re_string_context_at (&mctx->input,
2403 re_string_cur_idx (&mctx->input) - 1,
2405 next_state = mctx->state_log[cur_idx]
2406 = re_acquire_state_context (err, dfa, &next_nodes, context);
2407 /* We don't need to check errors here, since the return value of
2408 this function is next_state and ERR is already set. */
2410 if (table_nodes != NULL)
2411 re_node_set_free (&next_nodes);
2414 if (BE (dfa->nbackref, 0) && next_state != NULL)
2416 /* Check OP_OPEN_SUBEXP in the current state in case that we use them
2417 later. We must check them here, since the back references in the
2418 next state might use them. */
2419 *err = check_subexp_matching_top (mctx, &next_state->nodes,
2421 if (BE (*err != REG_NOERROR, 0))
2424 /* If the next state has back references. */
2425 if (next_state->has_backref)
2427 *err = transit_state_bkref (mctx, &next_state->nodes);
2428 if (BE (*err != REG_NOERROR, 0))
2430 next_state = mctx->state_log[cur_idx];
2437 /* Skip bytes in the input that correspond to part of a
2438 multi-byte match, then look in the log for a state
2439 from which to restart matching. */
2440 static re_dfastate_t *
2442 find_recover_state (reg_errcode_t *err, re_match_context_t *mctx)
2444 re_dfastate_t *cur_state;
2447 Idx max = mctx->state_log_top;
2448 Idx cur_str_idx = re_string_cur_idx (&mctx->input);
2452 if (++cur_str_idx > max)
2454 re_string_skip_bytes (&mctx->input, 1);
2456 while (mctx->state_log[cur_str_idx] == NULL);
2458 cur_state = merge_state_with_log (err, mctx, NULL);
2460 while (*err == REG_NOERROR && cur_state == NULL);
2464 /* Helper functions for transit_state. */
2466 /* From the node set CUR_NODES, pick up the nodes whose types are
2467 OP_OPEN_SUBEXP and which have corresponding back references in the regular
2468 expression. And register them to use them later for evaluating the
2469 correspoding back references. */
2471 static reg_errcode_t
2473 check_subexp_matching_top (re_match_context_t *mctx, re_node_set *cur_nodes,
2476 const re_dfa_t *const dfa = mctx->dfa;
2480 /* TODO: This isn't efficient.
2481 Because there might be more than one nodes whose types are
2482 OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
2485 for (node_idx = 0; node_idx < cur_nodes->nelem; ++node_idx)
2487 Idx node = cur_nodes->elems[node_idx];
2488 if (dfa->nodes[node].type == OP_OPEN_SUBEXP
2489 && dfa->nodes[node].opr.idx < BITSET_WORD_BITS
2490 && (dfa->used_bkref_map
2491 & ((bitset_word_t) 1 << dfa->nodes[node].opr.idx)))
2493 err = match_ctx_add_subtop (mctx, node, str_idx);
2494 if (BE (err != REG_NOERROR, 0))
2502 /* Return the next state to which the current state STATE will transit by
2503 accepting the current input byte. */
2505 static re_dfastate_t *
2506 transit_state_sb (reg_errcode_t *err, re_match_context_t *mctx,
2507 re_dfastate_t *state)
2509 const re_dfa_t *const dfa = mctx->dfa;
2510 re_node_set next_nodes;
2511 re_dfastate_t *next_state;
2512 Idx node_cnt, cur_str_idx = re_string_cur_idx (&mctx->input);
2513 unsigned int context;
2515 *err = re_node_set_alloc (&next_nodes, state->nodes.nelem + 1);
2516 if (BE (*err != REG_NOERROR, 0))
2518 for (node_cnt = 0; node_cnt < state->nodes.nelem; ++node_cnt)
2520 Idx cur_node = state->nodes.elems[node_cnt];
2521 if (check_node_accept (mctx, dfa->nodes + cur_node, cur_str_idx))
2523 *err = re_node_set_merge (&next_nodes,
2524 dfa->eclosures + dfa->nexts[cur_node]);
2525 if (BE (*err != REG_NOERROR, 0))
2527 re_node_set_free (&next_nodes);
2532 context = re_string_context_at (&mctx->input, cur_str_idx, mctx->eflags);
2533 next_state = re_acquire_state_context (err, dfa, &next_nodes, context);
2534 /* We don't need to check errors here, since the return value of
2535 this function is next_state and ERR is already set. */
2537 re_node_set_free (&next_nodes);
2538 re_string_skip_bytes (&mctx->input, 1);
2543 #ifdef RE_ENABLE_I18N
2544 static reg_errcode_t
2546 transit_state_mb (re_match_context_t *mctx, re_dfastate_t *pstate)
2548 const re_dfa_t *const dfa = mctx->dfa;
2552 for (i = 0; i < pstate->nodes.nelem; ++i)
2554 re_node_set dest_nodes, *new_nodes;
2555 Idx cur_node_idx = pstate->nodes.elems[i];
2558 unsigned int context;
2559 re_dfastate_t *dest_state;
2561 if (!dfa->nodes[cur_node_idx].accept_mb)
2564 if (dfa->nodes[cur_node_idx].constraint)
2566 context = re_string_context_at (&mctx->input,
2567 re_string_cur_idx (&mctx->input),
2569 if (NOT_SATISFY_NEXT_CONSTRAINT (dfa->nodes[cur_node_idx].constraint,
2574 /* How many bytes the node can accept? */
2575 naccepted = check_node_accept_bytes (dfa, cur_node_idx, &mctx->input,
2576 re_string_cur_idx (&mctx->input));
2580 /* The node can accepts `naccepted' bytes. */
2581 dest_idx = re_string_cur_idx (&mctx->input) + naccepted;
2582 mctx->max_mb_elem_len = ((mctx->max_mb_elem_len < naccepted) ? naccepted
2583 : mctx->max_mb_elem_len);
2584 err = clean_state_log_if_needed (mctx, dest_idx);
2585 if (BE (err != REG_NOERROR, 0))
2588 assert (dfa->nexts[cur_node_idx] != REG_MISSING);
2590 new_nodes = dfa->eclosures + dfa->nexts[cur_node_idx];
2592 dest_state = mctx->state_log[dest_idx];
2593 if (dest_state == NULL)
2594 dest_nodes = *new_nodes;
2597 err = re_node_set_init_union (&dest_nodes,
2598 dest_state->entrance_nodes, new_nodes);
2599 if (BE (err != REG_NOERROR, 0))
2602 context = re_string_context_at (&mctx->input, dest_idx - 1,
2604 mctx->state_log[dest_idx]
2605 = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2606 if (dest_state != NULL)
2607 re_node_set_free (&dest_nodes);
2608 if (BE (mctx->state_log[dest_idx] == NULL && err != REG_NOERROR, 0))
2613 #endif /* RE_ENABLE_I18N */
2615 static reg_errcode_t
2617 transit_state_bkref (re_match_context_t *mctx, const re_node_set *nodes)
2619 const re_dfa_t *const dfa = mctx->dfa;
2622 Idx cur_str_idx = re_string_cur_idx (&mctx->input);
2624 for (i = 0; i < nodes->nelem; ++i)
2626 Idx dest_str_idx, prev_nelem, bkc_idx;
2627 Idx node_idx = nodes->elems[i];
2628 unsigned int context;
2629 const re_token_t *node = dfa->nodes + node_idx;
2630 re_node_set *new_dest_nodes;
2632 /* Check whether `node' is a backreference or not. */
2633 if (node->type != OP_BACK_REF)
2636 if (node->constraint)
2638 context = re_string_context_at (&mctx->input, cur_str_idx,
2640 if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
2644 /* `node' is a backreference.
2645 Check the substring which the substring matched. */
2646 bkc_idx = mctx->nbkref_ents;
2647 err = get_subexp (mctx, node_idx, cur_str_idx);
2648 if (BE (err != REG_NOERROR, 0))
2651 /* And add the epsilon closures (which is `new_dest_nodes') of
2652 the backreference to appropriate state_log. */
2654 assert (dfa->nexts[node_idx] != REG_MISSING);
2656 for (; bkc_idx < mctx->nbkref_ents; ++bkc_idx)
2659 re_dfastate_t *dest_state;
2660 struct re_backref_cache_entry *bkref_ent;
2661 bkref_ent = mctx->bkref_ents + bkc_idx;
2662 if (bkref_ent->node != node_idx || bkref_ent->str_idx != cur_str_idx)
2664 subexp_len = bkref_ent->subexp_to - bkref_ent->subexp_from;
2665 new_dest_nodes = (subexp_len == 0
2666 ? dfa->eclosures + dfa->edests[node_idx].elems[0]
2667 : dfa->eclosures + dfa->nexts[node_idx]);
2668 dest_str_idx = (cur_str_idx + bkref_ent->subexp_to
2669 - bkref_ent->subexp_from);
2670 context = re_string_context_at (&mctx->input, dest_str_idx - 1,
2672 dest_state = mctx->state_log[dest_str_idx];
2673 prev_nelem = ((mctx->state_log[cur_str_idx] == NULL) ? 0
2674 : mctx->state_log[cur_str_idx]->nodes.nelem);
2675 /* Add `new_dest_node' to state_log. */
2676 if (dest_state == NULL)
2678 mctx->state_log[dest_str_idx]
2679 = re_acquire_state_context (&err, dfa, new_dest_nodes,
2681 if (BE (mctx->state_log[dest_str_idx] == NULL
2682 && err != REG_NOERROR, 0))
2687 re_node_set dest_nodes;
2688 err = re_node_set_init_union (&dest_nodes,
2689 dest_state->entrance_nodes,
2691 if (BE (err != REG_NOERROR, 0))
2693 re_node_set_free (&dest_nodes);
2696 mctx->state_log[dest_str_idx]
2697 = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2698 re_node_set_free (&dest_nodes);
2699 if (BE (mctx->state_log[dest_str_idx] == NULL
2700 && err != REG_NOERROR, 0))
2703 /* We need to check recursively if the backreference can epsilon
2706 && mctx->state_log[cur_str_idx]->nodes.nelem > prev_nelem)
2708 err = check_subexp_matching_top (mctx, new_dest_nodes,
2710 if (BE (err != REG_NOERROR, 0))
2712 err = transit_state_bkref (mctx, new_dest_nodes);
2713 if (BE (err != REG_NOERROR, 0))
2723 /* Enumerate all the candidates which the backreference BKREF_NODE can match
2724 at BKREF_STR_IDX, and register them by match_ctx_add_entry().
2725 Note that we might collect inappropriate candidates here.
2726 However, the cost of checking them strictly here is too high, then we
2727 delay these checking for prune_impossible_nodes(). */
2729 static reg_errcode_t
2730 internal_function __attribute_warn_unused_result__
2731 get_subexp (re_match_context_t *mctx, Idx bkref_node, Idx bkref_str_idx)
2733 const re_dfa_t *const dfa = mctx->dfa;
2734 Idx subexp_num, sub_top_idx;
2735 const char *buf = (const char *) re_string_get_buffer (&mctx->input);
2736 /* Return if we have already checked BKREF_NODE at BKREF_STR_IDX. */
2737 Idx cache_idx = search_cur_bkref_entry (mctx, bkref_str_idx);
2738 if (cache_idx != REG_MISSING)
2740 const struct re_backref_cache_entry *entry
2741 = mctx->bkref_ents + cache_idx;
2743 if (entry->node == bkref_node)
2744 return REG_NOERROR; /* We already checked it. */
2745 while (entry++->more);
2748 subexp_num = dfa->nodes[bkref_node].opr.idx;
2750 /* For each sub expression */
2751 for (sub_top_idx = 0; sub_top_idx < mctx->nsub_tops; ++sub_top_idx)
2754 re_sub_match_top_t *sub_top = mctx->sub_tops[sub_top_idx];
2755 re_sub_match_last_t *sub_last;
2756 Idx sub_last_idx, sl_str, bkref_str_off;
2758 if (dfa->nodes[sub_top->node].opr.idx != subexp_num)
2759 continue; /* It isn't related. */
2761 sl_str = sub_top->str_idx;
2762 bkref_str_off = bkref_str_idx;
2763 /* At first, check the last node of sub expressions we already
2765 for (sub_last_idx = 0; sub_last_idx < sub_top->nlasts; ++sub_last_idx)
2767 regoff_t sl_str_diff;
2768 sub_last = sub_top->lasts[sub_last_idx];
2769 sl_str_diff = sub_last->str_idx - sl_str;
2770 /* The matched string by the sub expression match with the substring
2771 at the back reference? */
2772 if (sl_str_diff > 0)
2774 if (BE (bkref_str_off + sl_str_diff > mctx->input.valid_len, 0))
2776 /* Not enough chars for a successful match. */
2777 if (bkref_str_off + sl_str_diff > mctx->input.len)
2780 err = clean_state_log_if_needed (mctx,
2783 if (BE (err != REG_NOERROR, 0))
2785 buf = (const char *) re_string_get_buffer (&mctx->input);
2787 if (memcmp (buf + bkref_str_off, buf + sl_str, sl_str_diff) != 0)
2788 /* We don't need to search this sub expression any more. */
2791 bkref_str_off += sl_str_diff;
2792 sl_str += sl_str_diff;
2793 err = get_subexp_sub (mctx, sub_top, sub_last, bkref_node,
2796 /* Reload buf, since the preceding call might have reallocated
2798 buf = (const char *) re_string_get_buffer (&mctx->input);
2800 if (err == REG_NOMATCH)
2802 if (BE (err != REG_NOERROR, 0))
2806 if (sub_last_idx < sub_top->nlasts)
2808 if (sub_last_idx > 0)
2810 /* Then, search for the other last nodes of the sub expression. */
2811 for (; sl_str <= bkref_str_idx; ++sl_str)
2814 regoff_t sl_str_off;
2815 const re_node_set *nodes;
2816 sl_str_off = sl_str - sub_top->str_idx;
2817 /* The matched string by the sub expression match with the substring
2818 at the back reference? */
2821 if (BE (bkref_str_off >= mctx->input.valid_len, 0))
2823 /* If we are at the end of the input, we cannot match. */
2824 if (bkref_str_off >= mctx->input.len)
2827 err = extend_buffers (mctx);
2828 if (BE (err != REG_NOERROR, 0))
2831 buf = (const char *) re_string_get_buffer (&mctx->input);
2833 if (buf [bkref_str_off++] != buf[sl_str - 1])
2834 break; /* We don't need to search this sub expression
2837 if (mctx->state_log[sl_str] == NULL)
2839 /* Does this state have a ')' of the sub expression? */
2840 nodes = &mctx->state_log[sl_str]->nodes;
2841 cls_node = find_subexp_node (dfa, nodes, subexp_num,
2843 if (cls_node == REG_MISSING)
2845 if (sub_top->path == NULL)
2847 sub_top->path = calloc (sizeof (state_array_t),
2848 sl_str - sub_top->str_idx + 1);
2849 if (sub_top->path == NULL)
2852 /* Can the OP_OPEN_SUBEXP node arrive the OP_CLOSE_SUBEXP node
2853 in the current context? */
2854 err = check_arrival (mctx, sub_top->path, sub_top->node,
2855 sub_top->str_idx, cls_node, sl_str,
2857 if (err == REG_NOMATCH)
2859 if (BE (err != REG_NOERROR, 0))
2861 sub_last = match_ctx_add_sublast (sub_top, cls_node, sl_str);
2862 if (BE (sub_last == NULL, 0))
2864 err = get_subexp_sub (mctx, sub_top, sub_last, bkref_node,
2866 if (err == REG_NOMATCH)
2873 /* Helper functions for get_subexp(). */
2875 /* Check SUB_LAST can arrive to the back reference BKREF_NODE at BKREF_STR.
2876 If it can arrive, register the sub expression expressed with SUB_TOP
2879 static reg_errcode_t
2881 get_subexp_sub (re_match_context_t *mctx, const re_sub_match_top_t *sub_top,
2882 re_sub_match_last_t *sub_last, Idx bkref_node, Idx bkref_str)
2886 /* Can the subexpression arrive the back reference? */
2887 err = check_arrival (mctx, &sub_last->path, sub_last->node,
2888 sub_last->str_idx, bkref_node, bkref_str,
2890 if (err != REG_NOERROR)
2892 err = match_ctx_add_entry (mctx, bkref_node, bkref_str, sub_top->str_idx,
2894 if (BE (err != REG_NOERROR, 0))
2896 to_idx = bkref_str + sub_last->str_idx - sub_top->str_idx;
2897 return clean_state_log_if_needed (mctx, to_idx);
2900 /* Find the first node which is '(' or ')' and whose index is SUBEXP_IDX.
2901 Search '(' if FL_OPEN, or search ')' otherwise.
2902 TODO: This function isn't efficient...
2903 Because there might be more than one nodes whose types are
2904 OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
2910 find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
2911 Idx subexp_idx, int type)
2914 for (cls_idx = 0; cls_idx < nodes->nelem; ++cls_idx)
2916 Idx cls_node = nodes->elems[cls_idx];
2917 const re_token_t *node = dfa->nodes + cls_node;
2918 if (node->type == type
2919 && node->opr.idx == subexp_idx)
2925 /* Check whether the node TOP_NODE at TOP_STR can arrive to the node
2926 LAST_NODE at LAST_STR. We record the path onto PATH since it will be
2928 Return REG_NOERROR if it can arrive, or REG_NOMATCH otherwise. */
2930 static reg_errcode_t
2931 internal_function __attribute_warn_unused_result__
2932 check_arrival (re_match_context_t *mctx, state_array_t *path, Idx top_node,
2933 Idx top_str, Idx last_node, Idx last_str, int type)
2935 const re_dfa_t *const dfa = mctx->dfa;
2936 reg_errcode_t err = REG_NOERROR;
2937 Idx subexp_num, backup_cur_idx, str_idx, null_cnt;
2938 re_dfastate_t *cur_state = NULL;
2939 re_node_set *cur_nodes, next_nodes;
2940 re_dfastate_t **backup_state_log;
2941 unsigned int context;
2943 subexp_num = dfa->nodes[top_node].opr.idx;
2944 /* Extend the buffer if we need. */
2945 if (BE (path->alloc < last_str + mctx->max_mb_elem_len + 1, 0))
2947 re_dfastate_t **new_array;
2948 Idx old_alloc = path->alloc;
2949 Idx new_alloc = old_alloc + last_str + mctx->max_mb_elem_len + 1;
2950 if (BE (new_alloc < old_alloc, 0)
2951 || BE (SIZE_MAX / sizeof (re_dfastate_t *) < new_alloc, 0))
2953 new_array = re_realloc (path->array, re_dfastate_t *, new_alloc);
2954 if (BE (new_array == NULL, 0))
2956 path->array = new_array;
2957 path->alloc = new_alloc;
2958 memset (new_array + old_alloc, '\0',
2959 sizeof (re_dfastate_t *) * (path->alloc - old_alloc));
2962 str_idx = path->next_idx ? path->next_idx : top_str;
2964 /* Temporary modify MCTX. */
2965 backup_state_log = mctx->state_log;
2966 backup_cur_idx = mctx->input.cur_idx;
2967 mctx->state_log = path->array;
2968 mctx->input.cur_idx = str_idx;
2970 /* Setup initial node set. */
2971 context = re_string_context_at (&mctx->input, str_idx - 1, mctx->eflags);
2972 if (str_idx == top_str)
2974 err = re_node_set_init_1 (&next_nodes, top_node);
2975 if (BE (err != REG_NOERROR, 0))
2977 err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
2978 if (BE (err != REG_NOERROR, 0))
2980 re_node_set_free (&next_nodes);
2986 cur_state = mctx->state_log[str_idx];
2987 if (cur_state && cur_state->has_backref)
2989 err = re_node_set_init_copy (&next_nodes, &cur_state->nodes);
2990 if (BE (err != REG_NOERROR, 0))
2994 re_node_set_init_empty (&next_nodes);
2996 if (str_idx == top_str || (cur_state && cur_state->has_backref))
2998 if (next_nodes.nelem)
3000 err = expand_bkref_cache (mctx, &next_nodes, str_idx,
3002 if (BE (err != REG_NOERROR, 0))
3004 re_node_set_free (&next_nodes);
3008 cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
3009 if (BE (cur_state == NULL && err != REG_NOERROR, 0))
3011 re_node_set_free (&next_nodes);
3014 mctx->state_log[str_idx] = cur_state;
3017 for (null_cnt = 0; str_idx < last_str && null_cnt <= mctx->max_mb_elem_len;)
3019 re_node_set_empty (&next_nodes);
3020 if (mctx->state_log[str_idx + 1])
3022 err = re_node_set_merge (&next_nodes,
3023 &mctx->state_log[str_idx + 1]->nodes);
3024 if (BE (err != REG_NOERROR, 0))
3026 re_node_set_free (&next_nodes);
3032 err = check_arrival_add_next_nodes (mctx, str_idx,
3033 &cur_state->non_eps_nodes,
3035 if (BE (err != REG_NOERROR, 0))
3037 re_node_set_free (&next_nodes);
3042 if (next_nodes.nelem)
3044 err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
3045 if (BE (err != REG_NOERROR, 0))
3047 re_node_set_free (&next_nodes);
3050 err = expand_bkref_cache (mctx, &next_nodes, str_idx,
3052 if (BE (err != REG_NOERROR, 0))
3054 re_node_set_free (&next_nodes);
3058 context = re_string_context_at (&mctx->input, str_idx - 1, mctx->eflags);
3059 cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
3060 if (BE (cur_state == NULL && err != REG_NOERROR, 0))
3062 re_node_set_free (&next_nodes);
3065 mctx->state_log[str_idx] = cur_state;
3066 null_cnt = cur_state == NULL ? null_cnt + 1 : 0;
3068 re_node_set_free (&next_nodes);
3069 cur_nodes = (mctx->state_log[last_str] == NULL ? NULL
3070 : &mctx->state_log[last_str]->nodes);
3071 path->next_idx = str_idx;
3074 mctx->state_log = backup_state_log;
3075 mctx->input.cur_idx = backup_cur_idx;
3077 /* Then check the current node set has the node LAST_NODE. */
3078 if (cur_nodes != NULL && re_node_set_contains (cur_nodes, last_node))
3084 /* Helper functions for check_arrival. */
3086 /* Calculate the destination nodes of CUR_NODES at STR_IDX, and append them
3088 TODO: This function is similar to the functions transit_state*(),
3089 however this function has many additional works.
3090 Can't we unify them? */
3092 static reg_errcode_t
3093 internal_function __attribute_warn_unused_result__
3094 check_arrival_add_next_nodes (re_match_context_t *mctx, Idx str_idx,
3095 re_node_set *cur_nodes, re_node_set *next_nodes)
3097 const re_dfa_t *const dfa = mctx->dfa;
3100 #ifdef RE_ENABLE_I18N
3101 reg_errcode_t err = REG_NOERROR;
3103 re_node_set union_set;
3104 re_node_set_init_empty (&union_set);
3105 for (cur_idx = 0; cur_idx < cur_nodes->nelem; ++cur_idx)
3108 Idx cur_node = cur_nodes->elems[cur_idx];
3110 re_token_type_t type = dfa->nodes[cur_node].type;
3111 assert (!IS_EPSILON_NODE (type));
3113 #ifdef RE_ENABLE_I18N
3114 /* If the node may accept `multi byte'. */
3115 if (dfa->nodes[cur_node].accept_mb)
3117 naccepted = check_node_accept_bytes (dfa, cur_node, &mctx->input,
3121 re_dfastate_t *dest_state;
3122 Idx next_node = dfa->nexts[cur_node];
3123 Idx next_idx = str_idx + naccepted;
3124 dest_state = mctx->state_log[next_idx];
3125 re_node_set_empty (&union_set);
3128 err = re_node_set_merge (&union_set, &dest_state->nodes);
3129 if (BE (err != REG_NOERROR, 0))
3131 re_node_set_free (&union_set);
3135 ok = re_node_set_insert (&union_set, next_node);
3138 re_node_set_free (&union_set);
3141 mctx->state_log[next_idx] = re_acquire_state (&err, dfa,
3143 if (BE (mctx->state_log[next_idx] == NULL
3144 && err != REG_NOERROR, 0))
3146 re_node_set_free (&union_set);
3151 #endif /* RE_ENABLE_I18N */
3153 || check_node_accept (mctx, dfa->nodes + cur_node, str_idx))
3155 ok = re_node_set_insert (next_nodes, dfa->nexts[cur_node]);
3158 re_node_set_free (&union_set);
3163 re_node_set_free (&union_set);
3167 /* For all the nodes in CUR_NODES, add the epsilon closures of them to
3168 CUR_NODES, however exclude the nodes which are:
3169 - inside the sub expression whose number is EX_SUBEXP, if FL_OPEN.
3170 - out of the sub expression whose number is EX_SUBEXP, if !FL_OPEN.
3173 static reg_errcode_t
3175 check_arrival_expand_ecl (const re_dfa_t *dfa, re_node_set *cur_nodes,
3176 Idx ex_subexp, int type)
3179 Idx idx, outside_node;
3180 re_node_set new_nodes;
3182 assert (cur_nodes->nelem);
3184 err = re_node_set_alloc (&new_nodes, cur_nodes->nelem);
3185 if (BE (err != REG_NOERROR, 0))
3187 /* Create a new node set NEW_NODES with the nodes which are epsilon
3188 closures of the node in CUR_NODES. */
3190 for (idx = 0; idx < cur_nodes->nelem; ++idx)
3192 Idx cur_node = cur_nodes->elems[idx];
3193 const re_node_set *eclosure = dfa->eclosures + cur_node;
3194 outside_node = find_subexp_node (dfa, eclosure, ex_subexp, type);
3195 if (outside_node == REG_MISSING)
3197 /* There are no problematic nodes, just merge them. */
3198 err = re_node_set_merge (&new_nodes, eclosure);
3199 if (BE (err != REG_NOERROR, 0))
3201 re_node_set_free (&new_nodes);
3207 /* There are problematic nodes, re-calculate incrementally. */
3208 err = check_arrival_expand_ecl_sub (dfa, &new_nodes, cur_node,
3210 if (BE (err != REG_NOERROR, 0))
3212 re_node_set_free (&new_nodes);
3217 re_node_set_free (cur_nodes);
3218 *cur_nodes = new_nodes;
3222 /* Helper function for check_arrival_expand_ecl.
3223 Check incrementally the epsilon closure of TARGET, and if it isn't
3224 problematic append it to DST_NODES. */
3226 static reg_errcode_t
3227 internal_function __attribute_warn_unused_result__
3228 check_arrival_expand_ecl_sub (const re_dfa_t *dfa, re_node_set *dst_nodes,
3229 Idx target, Idx ex_subexp, int type)
3232 for (cur_node = target; !re_node_set_contains (dst_nodes, cur_node);)
3236 if (dfa->nodes[cur_node].type == type
3237 && dfa->nodes[cur_node].opr.idx == ex_subexp)
3239 if (type == OP_CLOSE_SUBEXP)
3241 ok = re_node_set_insert (dst_nodes, cur_node);
3247 ok = re_node_set_insert (dst_nodes, cur_node);
3250 if (dfa->edests[cur_node].nelem == 0)
3252 if (dfa->edests[cur_node].nelem == 2)
3255 err = check_arrival_expand_ecl_sub (dfa, dst_nodes,
3256 dfa->edests[cur_node].elems[1],
3258 if (BE (err != REG_NOERROR, 0))
3261 cur_node = dfa->edests[cur_node].elems[0];
3267 /* For all the back references in the current state, calculate the
3268 destination of the back references by the appropriate entry
3269 in MCTX->BKREF_ENTS. */
3271 static reg_errcode_t
3272 internal_function __attribute_warn_unused_result__
3273 expand_bkref_cache (re_match_context_t *mctx, re_node_set *cur_nodes,
3274 Idx cur_str, Idx subexp_num, int type)
3276 const re_dfa_t *const dfa = mctx->dfa;
3278 Idx cache_idx_start = search_cur_bkref_entry (mctx, cur_str);
3279 struct re_backref_cache_entry *ent;
3281 if (cache_idx_start == REG_MISSING)
3285 ent = mctx->bkref_ents + cache_idx_start;
3288 Idx to_idx, next_node;
3290 /* Is this entry ENT is appropriate? */
3291 if (!re_node_set_contains (cur_nodes, ent->node))
3294 to_idx = cur_str + ent->subexp_to - ent->subexp_from;
3295 /* Calculate the destination of the back reference, and append it
3296 to MCTX->STATE_LOG. */
3297 if (to_idx == cur_str)
3299 /* The backreference did epsilon transit, we must re-check all the
3300 node in the current state. */
3301 re_node_set new_dests;
3302 reg_errcode_t err2, err3;
3303 next_node = dfa->edests[ent->node].elems[0];
3304 if (re_node_set_contains (cur_nodes, next_node))
3306 err = re_node_set_init_1 (&new_dests, next_node);
3307 err2 = check_arrival_expand_ecl (dfa, &new_dests, subexp_num, type);
3308 err3 = re_node_set_merge (cur_nodes, &new_dests);
3309 re_node_set_free (&new_dests);
3310 if (BE (err != REG_NOERROR || err2 != REG_NOERROR
3311 || err3 != REG_NOERROR, 0))
3313 err = (err != REG_NOERROR ? err
3314 : (err2 != REG_NOERROR ? err2 : err3));
3317 /* TODO: It is still inefficient... */
3322 re_node_set union_set;
3323 next_node = dfa->nexts[ent->node];
3324 if (mctx->state_log[to_idx])
3327 if (re_node_set_contains (&mctx->state_log[to_idx]->nodes,
3330 err = re_node_set_init_copy (&union_set,
3331 &mctx->state_log[to_idx]->nodes);
3332 ok = re_node_set_insert (&union_set, next_node);
3333 if (BE (err != REG_NOERROR || ! ok, 0))
3335 re_node_set_free (&union_set);
3336 err = err != REG_NOERROR ? err : REG_ESPACE;
3342 err = re_node_set_init_1 (&union_set, next_node);
3343 if (BE (err != REG_NOERROR, 0))
3346 mctx->state_log[to_idx] = re_acquire_state (&err, dfa, &union_set);
3347 re_node_set_free (&union_set);
3348 if (BE (mctx->state_log[to_idx] == NULL
3349 && err != REG_NOERROR, 0))
3353 while (ent++->more);
3357 /* Build transition table for the state.
3358 Return true if successful. */
3362 build_trtable (const re_dfa_t *dfa, re_dfastate_t *state)
3367 bool need_word_trtable = false;
3368 bitset_word_t elem, mask;
3369 bool dests_node_malloced = false;
3370 bool dest_states_malloced = false;
3371 Idx ndests; /* Number of the destination states from `state'. */
3372 re_dfastate_t **trtable;
3373 re_dfastate_t **dest_states = NULL, **dest_states_word, **dest_states_nl;
3374 re_node_set follows, *dests_node;
3376 bitset_t acceptable;
3380 re_node_set dests_node[SBC_MAX];
3381 bitset_t dests_ch[SBC_MAX];
3384 /* We build DFA states which corresponds to the destination nodes
3385 from `state'. `dests_node[i]' represents the nodes which i-th
3386 destination state contains, and `dests_ch[i]' represents the
3387 characters which i-th destination state accepts. */
3388 if (__libc_use_alloca (sizeof (struct dests_alloc)))
3389 dests_alloc = (struct dests_alloc *) alloca (sizeof (struct dests_alloc));
3392 dests_alloc = re_malloc (struct dests_alloc, 1);
3393 if (BE (dests_alloc == NULL, 0))
3395 dests_node_malloced = true;
3397 dests_node = dests_alloc->dests_node;
3398 dests_ch = dests_alloc->dests_ch;
3400 /* Initialize transiton table. */
3401 state->word_trtable = state->trtable = NULL;
3403 /* At first, group all nodes belonging to `state' into several
3405 ndests = group_nodes_into_DFAstates (dfa, state, dests_node, dests_ch);
3406 if (BE (! REG_VALID_NONZERO_INDEX (ndests), 0))
3408 if (dests_node_malloced)
3412 state->trtable = (re_dfastate_t **)
3413 calloc (sizeof (re_dfastate_t *), SBC_MAX);
3414 if (BE (state->trtable == NULL, 0))
3421 err = re_node_set_alloc (&follows, ndests + 1);
3422 if (BE (err != REG_NOERROR, 0))
3425 /* Avoid arithmetic overflow in size calculation. */
3426 if (BE ((((SIZE_MAX - (sizeof (re_node_set) + sizeof (bitset_t)) * SBC_MAX)
3427 / (3 * sizeof (re_dfastate_t *)))
3432 if (__libc_use_alloca ((sizeof (re_node_set) + sizeof (bitset_t)) * SBC_MAX
3433 + ndests * 3 * sizeof (re_dfastate_t *)))
3434 dest_states = (re_dfastate_t **)
3435 alloca (ndests * 3 * sizeof (re_dfastate_t *));
3438 dest_states = (re_dfastate_t **)
3439 malloc (ndests * 3 * sizeof (re_dfastate_t *));
3440 if (BE (dest_states == NULL, 0))
3443 if (dest_states_malloced)
3445 re_node_set_free (&follows);
3446 for (i = 0; i < ndests; ++i)
3447 re_node_set_free (dests_node + i);
3448 if (dests_node_malloced)
3452 dest_states_malloced = true;
3454 dest_states_word = dest_states + ndests;
3455 dest_states_nl = dest_states_word + ndests;
3456 bitset_empty (acceptable);
3458 /* Then build the states for all destinations. */
3459 for (i = 0; i < ndests; ++i)
3462 re_node_set_empty (&follows);
3463 /* Merge the follows of this destination states. */
3464 for (j = 0; j < dests_node[i].nelem; ++j)
3466 next_node = dfa->nexts[dests_node[i].elems[j]];
3467 if (next_node != REG_MISSING)
3469 err = re_node_set_merge (&follows, dfa->eclosures + next_node);
3470 if (BE (err != REG_NOERROR, 0))
3474 dest_states[i] = re_acquire_state_context (&err, dfa, &follows, 0);
3475 if (BE (dest_states[i] == NULL && err != REG_NOERROR, 0))
3477 /* If the new state has context constraint,
3478 build appropriate states for these contexts. */
3479 if (dest_states[i]->has_constraint)
3481 dest_states_word[i] = re_acquire_state_context (&err, dfa, &follows,
3483 if (BE (dest_states_word[i] == NULL && err != REG_NOERROR, 0))
3486 if (dest_states[i] != dest_states_word[i] && dfa->mb_cur_max > 1)
3487 need_word_trtable = true;
3489 dest_states_nl[i] = re_acquire_state_context (&err, dfa, &follows,
3491 if (BE (dest_states_nl[i] == NULL && err != REG_NOERROR, 0))
3496 dest_states_word[i] = dest_states[i];
3497 dest_states_nl[i] = dest_states[i];
3499 bitset_merge (acceptable, dests_ch[i]);
3502 if (!BE (need_word_trtable, 0))
3504 /* We don't care about whether the following character is a word
3505 character, or we are in a single-byte character set so we can
3506 discern by looking at the character code: allocate a
3507 256-entry transition table. */
3508 trtable = state->trtable =
3509 (re_dfastate_t **) calloc (sizeof (re_dfastate_t *), SBC_MAX);
3510 if (BE (trtable == NULL, 0))
3513 /* For all characters ch...: */
3514 for (i = 0; i < BITSET_WORDS; ++i)
3515 for (ch = i * BITSET_WORD_BITS, elem = acceptable[i], mask = 1;
3517 mask <<= 1, elem >>= 1, ++ch)
3518 if (BE (elem & 1, 0))
3520 /* There must be exactly one destination which accepts
3521 character ch. See group_nodes_into_DFAstates. */
3522 for (j = 0; (dests_ch[j][i] & mask) == 0; ++j)
3525 /* j-th destination accepts the word character ch. */
3526 if (dfa->word_char[i] & mask)
3527 trtable[ch] = dest_states_word[j];
3529 trtable[ch] = dest_states[j];
3534 /* We care about whether the following character is a word
3535 character, and we are in a multi-byte character set: discern
3536 by looking at the character code: build two 256-entry
3537 transition tables, one starting at trtable[0] and one
3538 starting at trtable[SBC_MAX]. */
3539 trtable = state->word_trtable =
3540 (re_dfastate_t **) calloc (sizeof (re_dfastate_t *), 2 * SBC_MAX);
3541 if (BE (trtable == NULL, 0))
3544 /* For all characters ch...: */
3545 for (i = 0; i < BITSET_WORDS; ++i)
3546 for (ch = i * BITSET_WORD_BITS, elem = acceptable[i], mask = 1;
3548 mask <<= 1, elem >>= 1, ++ch)
3549 if (BE (elem & 1, 0))
3551 /* There must be exactly one destination which accepts
3552 character ch. See group_nodes_into_DFAstates. */
3553 for (j = 0; (dests_ch[j][i] & mask) == 0; ++j)
3556 /* j-th destination accepts the word character ch. */
3557 trtable[ch] = dest_states[j];
3558 trtable[ch + SBC_MAX] = dest_states_word[j];
3563 if (bitset_contain (acceptable, NEWLINE_CHAR))
3565 /* The current state accepts newline character. */
3566 for (j = 0; j < ndests; ++j)
3567 if (bitset_contain (dests_ch[j], NEWLINE_CHAR))
3569 /* k-th destination accepts newline character. */
3570 trtable[NEWLINE_CHAR] = dest_states_nl[j];
3571 if (need_word_trtable)
3572 trtable[NEWLINE_CHAR + SBC_MAX] = dest_states_nl[j];
3573 /* There must be only one destination which accepts
3574 newline. See group_nodes_into_DFAstates. */
3579 if (dest_states_malloced)
3582 re_node_set_free (&follows);
3583 for (i = 0; i < ndests; ++i)
3584 re_node_set_free (dests_node + i);
3586 if (dests_node_malloced)
3592 /* Group all nodes belonging to STATE into several destinations.
3593 Then for all destinations, set the nodes belonging to the destination
3594 to DESTS_NODE[i] and set the characters accepted by the destination
3595 to DEST_CH[i]. This function return the number of destinations. */
3599 group_nodes_into_DFAstates (const re_dfa_t *dfa, const re_dfastate_t *state,
3600 re_node_set *dests_node, bitset_t *dests_ch)
3605 Idx ndests; /* Number of the destinations from `state'. */
3606 bitset_t accepts; /* Characters a node can accept. */
3607 const re_node_set *cur_nodes = &state->nodes;
3608 bitset_empty (accepts);
3611 /* For all the nodes belonging to `state', */
3612 for (i = 0; i < cur_nodes->nelem; ++i)
3614 re_token_t *node = &dfa->nodes[cur_nodes->elems[i]];
3615 re_token_type_t type = node->type;
3616 unsigned int constraint = node->constraint;
3618 /* Enumerate all single byte character this node can accept. */
3619 if (type == CHARACTER)
3620 bitset_set (accepts, node->opr.c);
3621 else if (type == SIMPLE_BRACKET)
3623 bitset_merge (accepts, node->opr.sbcset);
3625 else if (type == OP_PERIOD)
3627 #ifdef RE_ENABLE_I18N
3628 if (dfa->mb_cur_max > 1)
3629 bitset_merge (accepts, dfa->sb_char);
3632 bitset_set_all (accepts);
3633 if (!(dfa->syntax & RE_DOT_NEWLINE))
3634 bitset_clear (accepts, '\n');
3635 if (dfa->syntax & RE_DOT_NOT_NULL)
3636 bitset_clear (accepts, '\0');
3638 #ifdef RE_ENABLE_I18N
3639 else if (type == OP_UTF8_PERIOD)
3641 if (ASCII_CHARS % BITSET_WORD_BITS == 0)
3642 memset (accepts, -1, ASCII_CHARS / CHAR_BIT);
3644 bitset_merge (accepts, utf8_sb_map);
3645 if (!(dfa->syntax & RE_DOT_NEWLINE))
3646 bitset_clear (accepts, '\n');
3647 if (dfa->syntax & RE_DOT_NOT_NULL)
3648 bitset_clear (accepts, '\0');
3654 /* Check the `accepts' and sift the characters which are not
3655 match it the context. */
3658 if (constraint & NEXT_NEWLINE_CONSTRAINT)
3660 bool accepts_newline = bitset_contain (accepts, NEWLINE_CHAR);
3661 bitset_empty (accepts);
3662 if (accepts_newline)
3663 bitset_set (accepts, NEWLINE_CHAR);
3667 if (constraint & NEXT_ENDBUF_CONSTRAINT)
3669 bitset_empty (accepts);
3673 if (constraint & NEXT_WORD_CONSTRAINT)
3675 bitset_word_t any_set = 0;
3676 if (type == CHARACTER && !node->word_char)
3678 bitset_empty (accepts);
3681 #ifdef RE_ENABLE_I18N
3682 if (dfa->mb_cur_max > 1)
3683 for (j = 0; j < BITSET_WORDS; ++j)
3684 any_set |= (accepts[j] &= (dfa->word_char[j] | ~dfa->sb_char[j]));
3687 for (j = 0; j < BITSET_WORDS; ++j)
3688 any_set |= (accepts[j] &= dfa->word_char[j]);
3692 if (constraint & NEXT_NOTWORD_CONSTRAINT)
3694 bitset_word_t any_set = 0;
3695 if (type == CHARACTER && node->word_char)
3697 bitset_empty (accepts);
3700 #ifdef RE_ENABLE_I18N
3701 if (dfa->mb_cur_max > 1)
3702 for (j = 0; j < BITSET_WORDS; ++j)
3703 any_set |= (accepts[j] &= ~(dfa->word_char[j] & dfa->sb_char[j]));
3706 for (j = 0; j < BITSET_WORDS; ++j)
3707 any_set |= (accepts[j] &= ~dfa->word_char[j]);
3713 /* Then divide `accepts' into DFA states, or create a new
3714 state. Above, we make sure that accepts is not empty. */
3715 for (j = 0; j < ndests; ++j)
3717 bitset_t intersec; /* Intersection sets, see below. */
3719 /* Flags, see below. */
3720 bitset_word_t has_intersec, not_subset, not_consumed;
3722 /* Optimization, skip if this state doesn't accept the character. */
3723 if (type == CHARACTER && !bitset_contain (dests_ch[j], node->opr.c))
3726 /* Enumerate the intersection set of this state and `accepts'. */
3728 for (k = 0; k < BITSET_WORDS; ++k)
3729 has_intersec |= intersec[k] = accepts[k] & dests_ch[j][k];
3730 /* And skip if the intersection set is empty. */
3734 /* Then check if this state is a subset of `accepts'. */
3735 not_subset = not_consumed = 0;
3736 for (k = 0; k < BITSET_WORDS; ++k)
3738 not_subset |= remains[k] = ~accepts[k] & dests_ch[j][k];
3739 not_consumed |= accepts[k] = accepts[k] & ~dests_ch[j][k];
3742 /* If this state isn't a subset of `accepts', create a
3743 new group state, which has the `remains'. */
3746 bitset_copy (dests_ch[ndests], remains);
3747 bitset_copy (dests_ch[j], intersec);
3748 err = re_node_set_init_copy (dests_node + ndests, &dests_node[j]);
3749 if (BE (err != REG_NOERROR, 0))
3754 /* Put the position in the current group. */
3755 ok = re_node_set_insert (&dests_node[j], cur_nodes->elems[i]);
3759 /* If all characters are consumed, go to next node. */
3763 /* Some characters remain, create a new group. */
3766 bitset_copy (dests_ch[ndests], accepts);
3767 err = re_node_set_init_1 (dests_node + ndests, cur_nodes->elems[i]);
3768 if (BE (err != REG_NOERROR, 0))
3771 bitset_empty (accepts);
3776 for (j = 0; j < ndests; ++j)
3777 re_node_set_free (dests_node + j);
3781 #ifdef RE_ENABLE_I18N
3782 /* Check how many bytes the node `dfa->nodes[node_idx]' accepts.
3783 Return the number of the bytes the node accepts.
3784 STR_IDX is the current index of the input string.
3786 This function handles the nodes which can accept one character, or
3787 one collating element like '.', '[a-z]', opposite to the other nodes
3788 can only accept one byte. */
3792 check_node_accept_bytes (const re_dfa_t *dfa, Idx node_idx,
3793 const re_string_t *input, Idx str_idx)
3795 const re_token_t *node = dfa->nodes + node_idx;
3796 int char_len, elem_len;
3799 if (BE (node->type == OP_UTF8_PERIOD, 0))
3801 unsigned char c = re_string_byte_at (input, str_idx), d;
3802 if (BE (c < 0xc2, 1))
3805 if (str_idx + 2 > input->len)
3808 d = re_string_byte_at (input, str_idx + 1);
3810 return (d < 0x80 || d > 0xbf) ? 0 : 2;
3814 if (c == 0xe0 && d < 0xa0)
3820 if (c == 0xf0 && d < 0x90)
3826 if (c == 0xf8 && d < 0x88)
3832 if (c == 0xfc && d < 0x84)
3838 if (str_idx + char_len > input->len)
3841 for (i = 1; i < char_len; ++i)
3843 d = re_string_byte_at (input, str_idx + i);
3844 if (d < 0x80 || d > 0xbf)
3850 char_len = re_string_char_size_at (input, str_idx);
3851 if (node->type == OP_PERIOD)
3855 /* FIXME: I don't think this if is needed, as both '\n'
3856 and '\0' are char_len == 1. */
3857 /* '.' accepts any one character except the following two cases. */
3858 if ((!(dfa->syntax & RE_DOT_NEWLINE) &&
3859 re_string_byte_at (input, str_idx) == '\n') ||
3860 ((dfa->syntax & RE_DOT_NOT_NULL) &&
3861 re_string_byte_at (input, str_idx) == '\0'))
3866 elem_len = re_string_elem_size_at (input, str_idx);
3867 if ((elem_len <= 1 && char_len <= 1) || char_len == 0)
3870 if (node->type == COMPLEX_BRACKET)
3872 const re_charset_t *cset = node->opr.mbcset;
3874 const unsigned char *pin
3875 = ((const unsigned char *) re_string_get_buffer (input) + str_idx);
3880 wchar_t wc = ((cset->nranges || cset->nchar_classes || cset->nmbchars)
3881 ? re_string_wchar_at (input, str_idx) : 0);
3883 /* match with multibyte character? */
3884 for (i = 0; i < cset->nmbchars; ++i)
3885 if (wc == cset->mbchars[i])
3887 match_len = char_len;
3888 goto check_node_accept_bytes_match;
3890 /* match with character_class? */
3891 for (i = 0; i < cset->nchar_classes; ++i)
3893 wctype_t wt = cset->char_classes[i];
3894 if (__iswctype (wc, wt))
3896 match_len = char_len;
3897 goto check_node_accept_bytes_match;
3902 nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
3905 unsigned int in_collseq = 0;
3906 const int32_t *table, *indirect;
3907 const unsigned char *weights, *extra;
3908 const char *collseqwc;
3910 /* This #include defines a local function! */
3911 # include <locale/weight.h>
3913 /* match with collating_symbol? */
3914 if (cset->ncoll_syms)
3915 extra = (const unsigned char *)
3916 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB);
3917 for (i = 0; i < cset->ncoll_syms; ++i)
3919 const unsigned char *coll_sym = extra + cset->coll_syms[i];
3920 /* Compare the length of input collating element and
3921 the length of current collating element. */
3922 if (*coll_sym != elem_len)
3924 /* Compare each bytes. */
3925 for (j = 0; j < *coll_sym; j++)
3926 if (pin[j] != coll_sym[1 + j])
3930 /* Match if every bytes is equal. */
3932 goto check_node_accept_bytes_match;
3938 if (elem_len <= char_len)
3940 collseqwc = _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQWC);
3941 in_collseq = __collseq_table_lookup (collseqwc, wc);
3944 in_collseq = find_collation_sequence_value (pin, elem_len);
3946 /* match with range expression? */
3947 for (i = 0; i < cset->nranges; ++i)
3948 if (cset->range_starts[i] <= in_collseq
3949 && in_collseq <= cset->range_ends[i])
3951 match_len = elem_len;
3952 goto check_node_accept_bytes_match;
3955 /* match with equivalence_class? */
3956 if (cset->nequiv_classes)
3958 const unsigned char *cp = pin;
3959 table = (const int32_t *)
3960 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
3961 weights = (const unsigned char *)
3962 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_WEIGHTMB);
3963 extra = (const unsigned char *)
3964 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAMB);
3965 indirect = (const int32_t *)
3966 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_INDIRECTMB);
3967 int32_t idx = findidx (&cp);
3969 for (i = 0; i < cset->nequiv_classes; ++i)
3971 int32_t equiv_class_idx = cset->equiv_classes[i];
3972 size_t weight_len = weights[idx & 0xffffff];
3973 if (weight_len == weights[equiv_class_idx & 0xffffff]
3974 && (idx >> 24) == (equiv_class_idx >> 24))
3979 equiv_class_idx &= 0xffffff;
3981 while (cnt <= weight_len
3982 && (weights[equiv_class_idx + 1 + cnt]
3983 == weights[idx + 1 + cnt]))
3985 if (cnt > weight_len)
3987 match_len = elem_len;
3988 goto check_node_accept_bytes_match;
3997 /* match with range expression? */
3998 #if __GNUC__ >= 2 && ! (__STDC_VERSION__ < 199901L && __STRICT_ANSI__)
3999 wchar_t cmp_buf[] = {L'\0', L'\0', wc, L'\0', L'\0', L'\0'};
4001 wchar_t cmp_buf[] = {L'\0', L'\0', L'\0', L'\0', L'\0', L'\0'};
4004 for (i = 0; i < cset->nranges; ++i)
4006 cmp_buf[0] = cset->range_starts[i];
4007 cmp_buf[4] = cset->range_ends[i];
4008 if (wcscoll (cmp_buf, cmp_buf + 2) <= 0
4009 && wcscoll (cmp_buf + 2, cmp_buf + 4) <= 0)
4011 match_len = char_len;
4012 goto check_node_accept_bytes_match;
4016 check_node_accept_bytes_match:
4017 if (!cset->non_match)
4024 return (elem_len > char_len) ? elem_len : char_len;
4033 find_collation_sequence_value (const unsigned char *mbs, size_t mbs_len)
4035 uint32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
4040 /* No valid character. Match it as a single byte character. */
4041 const unsigned char *collseq = (const unsigned char *)
4042 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQMB);
4043 return collseq[mbs[0]];
4050 const unsigned char *extra = (const unsigned char *)
4051 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB);
4052 int32_t extrasize = (const unsigned char *)
4053 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB + 1) - extra;
4055 for (idx = 0; idx < extrasize;)
4059 int32_t elem_mbs_len;
4060 /* Skip the name of collating element name. */
4061 idx = idx + extra[idx] + 1;
4062 elem_mbs_len = extra[idx++];
4063 if (mbs_len == elem_mbs_len)
4065 for (mbs_cnt = 0; mbs_cnt < elem_mbs_len; ++mbs_cnt)
4066 if (extra[idx + mbs_cnt] != mbs[mbs_cnt])
4068 if (mbs_cnt == elem_mbs_len)
4069 /* Found the entry. */
4072 /* Skip the byte sequence of the collating element. */
4073 idx += elem_mbs_len;
4074 /* Adjust for the alignment. */
4075 idx = (idx + 3) & ~3;
4076 /* Skip the collation sequence value. */
4077 idx += sizeof (uint32_t);
4078 /* Skip the wide char sequence of the collating element. */
4079 idx = idx + sizeof (uint32_t) * (extra[idx] + 1);
4080 /* If we found the entry, return the sequence value. */
4082 return *(uint32_t *) (extra + idx);
4083 /* Skip the collation sequence value. */
4084 idx += sizeof (uint32_t);
4090 #endif /* RE_ENABLE_I18N */
4092 /* Check whether the node accepts the byte which is IDX-th
4093 byte of the INPUT. */
4097 check_node_accept (const re_match_context_t *mctx, const re_token_t *node,
4101 ch = re_string_byte_at (&mctx->input, idx);
4105 if (node->opr.c != ch)
4109 case SIMPLE_BRACKET:
4110 if (!bitset_contain (node->opr.sbcset, ch))
4114 #ifdef RE_ENABLE_I18N
4115 case OP_UTF8_PERIOD:
4116 if (ch >= ASCII_CHARS)
4121 if ((ch == '\n' && !(mctx->dfa->syntax & RE_DOT_NEWLINE))
4122 || (ch == '\0' && (mctx->dfa->syntax & RE_DOT_NOT_NULL)))
4130 if (node->constraint)
4132 /* The node has constraints. Check whether the current context
4133 satisfies the constraints. */
4134 unsigned int context = re_string_context_at (&mctx->input, idx,
4136 if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
4143 /* Extend the buffers, if the buffers have run out. */
4145 static reg_errcode_t
4146 internal_function __attribute_warn_unused_result__
4147 extend_buffers (re_match_context_t *mctx)
4150 re_string_t *pstr = &mctx->input;
4152 /* Avoid overflow. */
4153 if (BE (SIZE_MAX / 2 / sizeof (re_dfastate_t *) <= pstr->bufs_len, 0))
4156 /* Double the lengthes of the buffers. */
4157 ret = re_string_realloc_buffers (pstr, pstr->bufs_len * 2);
4158 if (BE (ret != REG_NOERROR, 0))
4161 if (mctx->state_log != NULL)
4163 /* And double the length of state_log. */
4164 /* XXX We have no indication of the size of this buffer. If this
4165 allocation fail we have no indication that the state_log array
4166 does not have the right size. */
4167 re_dfastate_t **new_array = re_realloc (mctx->state_log, re_dfastate_t *,
4168 pstr->bufs_len + 1);
4169 if (BE (new_array == NULL, 0))
4171 mctx->state_log = new_array;
4174 /* Then reconstruct the buffers. */
4177 #ifdef RE_ENABLE_I18N
4178 if (pstr->mb_cur_max > 1)
4180 ret = build_wcs_upper_buffer (pstr);
4181 if (BE (ret != REG_NOERROR, 0))
4185 #endif /* RE_ENABLE_I18N */
4186 build_upper_buffer (pstr);
4190 #ifdef RE_ENABLE_I18N
4191 if (pstr->mb_cur_max > 1)
4192 build_wcs_buffer (pstr);
4194 #endif /* RE_ENABLE_I18N */
4196 if (pstr->trans != NULL)
4197 re_string_translate_buffer (pstr);
4204 /* Functions for matching context. */
4206 /* Initialize MCTX. */
4208 static reg_errcode_t
4209 internal_function __attribute_warn_unused_result__
4210 match_ctx_init (re_match_context_t *mctx, int eflags, Idx n)
4212 mctx->eflags = eflags;
4213 mctx->match_last = REG_MISSING;
4216 /* Avoid overflow. */
4217 size_t max_object_size =
4218 MAX (sizeof (struct re_backref_cache_entry),
4219 sizeof (re_sub_match_top_t *));
4220 if (BE (SIZE_MAX / max_object_size < n, 0))
4223 mctx->bkref_ents = re_malloc (struct re_backref_cache_entry, n);
4224 mctx->sub_tops = re_malloc (re_sub_match_top_t *, n);
4225 if (BE (mctx->bkref_ents == NULL || mctx->sub_tops == NULL, 0))
4228 /* Already zero-ed by the caller.
4230 mctx->bkref_ents = NULL;
4231 mctx->nbkref_ents = 0;
4232 mctx->nsub_tops = 0; */
4233 mctx->abkref_ents = n;
4234 mctx->max_mb_elem_len = 1;
4235 mctx->asub_tops = n;
4239 /* Clean the entries which depend on the current input in MCTX.
4240 This function must be invoked when the matcher changes the start index
4241 of the input, or changes the input string. */
4245 match_ctx_clean (re_match_context_t *mctx)
4248 for (st_idx = 0; st_idx < mctx->nsub_tops; ++st_idx)
4251 re_sub_match_top_t *top = mctx->sub_tops[st_idx];
4252 for (sl_idx = 0; sl_idx < top->nlasts; ++sl_idx)
4254 re_sub_match_last_t *last = top->lasts[sl_idx];
4255 re_free (last->path.array);
4258 re_free (top->lasts);
4261 re_free (top->path->array);
4262 re_free (top->path);
4267 mctx->nsub_tops = 0;
4268 mctx->nbkref_ents = 0;
4271 /* Free all the memory associated with MCTX. */
4275 match_ctx_free (re_match_context_t *mctx)
4277 /* First, free all the memory associated with MCTX->SUB_TOPS. */
4278 match_ctx_clean (mctx);
4279 re_free (mctx->sub_tops);
4280 re_free (mctx->bkref_ents);
4283 /* Add a new backreference entry to MCTX.
4284 Note that we assume that caller never call this function with duplicate
4285 entry, and call with STR_IDX which isn't smaller than any existing entry.
4288 static reg_errcode_t
4289 internal_function __attribute_warn_unused_result__
4290 match_ctx_add_entry (re_match_context_t *mctx, Idx node, Idx str_idx, Idx from,
4293 if (mctx->nbkref_ents >= mctx->abkref_ents)
4295 struct re_backref_cache_entry* new_entry;
4296 new_entry = re_realloc (mctx->bkref_ents, struct re_backref_cache_entry,
4297 mctx->abkref_ents * 2);
4298 if (BE (new_entry == NULL, 0))
4300 re_free (mctx->bkref_ents);
4303 mctx->bkref_ents = new_entry;
4304 memset (mctx->bkref_ents + mctx->nbkref_ents, '\0',
4305 sizeof (struct re_backref_cache_entry) * mctx->abkref_ents);
4306 mctx->abkref_ents *= 2;
4308 if (mctx->nbkref_ents > 0
4309 && mctx->bkref_ents[mctx->nbkref_ents - 1].str_idx == str_idx)
4310 mctx->bkref_ents[mctx->nbkref_ents - 1].more = 1;
4312 mctx->bkref_ents[mctx->nbkref_ents].node = node;
4313 mctx->bkref_ents[mctx->nbkref_ents].str_idx = str_idx;
4314 mctx->bkref_ents[mctx->nbkref_ents].subexp_from = from;
4315 mctx->bkref_ents[mctx->nbkref_ents].subexp_to = to;
4317 /* This is a cache that saves negative results of check_dst_limits_calc_pos.
4318 If bit N is clear, means that this entry won't epsilon-transition to
4319 an OP_OPEN_SUBEXP or OP_CLOSE_SUBEXP for the N+1-th subexpression. If
4320 it is set, check_dst_limits_calc_pos_1 will recurse and try to find one
4323 A backreference does not epsilon-transition unless it is empty, so set
4324 to all zeros if FROM != TO. */
4325 mctx->bkref_ents[mctx->nbkref_ents].eps_reachable_subexps_map
4326 = (from == to ? -1 : 0);
4328 mctx->bkref_ents[mctx->nbkref_ents++].more = 0;
4329 if (mctx->max_mb_elem_len < to - from)
4330 mctx->max_mb_elem_len = to - from;
4334 /* Return the first entry with the same str_idx, or REG_MISSING if none is
4335 found. Note that MCTX->BKREF_ENTS is already sorted by MCTX->STR_IDX. */
4339 search_cur_bkref_entry (const re_match_context_t *mctx, Idx str_idx)
4341 Idx left, right, mid, last;
4342 last = right = mctx->nbkref_ents;
4343 for (left = 0; left < right;)
4345 mid = (left + right) / 2;
4346 if (mctx->bkref_ents[mid].str_idx < str_idx)
4351 if (left < last && mctx->bkref_ents[left].str_idx == str_idx)
4357 /* Register the node NODE, whose type is OP_OPEN_SUBEXP, and which matches
4360 static reg_errcode_t
4361 internal_function __attribute_warn_unused_result__
4362 match_ctx_add_subtop (re_match_context_t *mctx, Idx node, Idx str_idx)
4365 assert (mctx->sub_tops != NULL);
4366 assert (mctx->asub_tops > 0);
4368 if (BE (mctx->nsub_tops == mctx->asub_tops, 0))
4370 Idx new_asub_tops = mctx->asub_tops * 2;
4371 re_sub_match_top_t **new_array = re_realloc (mctx->sub_tops,
4372 re_sub_match_top_t *,
4374 if (BE (new_array == NULL, 0))
4376 mctx->sub_tops = new_array;
4377 mctx->asub_tops = new_asub_tops;
4379 mctx->sub_tops[mctx->nsub_tops] = calloc (1, sizeof (re_sub_match_top_t));
4380 if (BE (mctx->sub_tops[mctx->nsub_tops] == NULL, 0))
4382 mctx->sub_tops[mctx->nsub_tops]->node = node;
4383 mctx->sub_tops[mctx->nsub_tops++]->str_idx = str_idx;
4387 /* Register the node NODE, whose type is OP_CLOSE_SUBEXP, and which matches
4388 at STR_IDX, whose corresponding OP_OPEN_SUBEXP is SUB_TOP. */
4390 static re_sub_match_last_t *
4392 match_ctx_add_sublast (re_sub_match_top_t *subtop, Idx node, Idx str_idx)
4394 re_sub_match_last_t *new_entry;
4395 if (BE (subtop->nlasts == subtop->alasts, 0))
4397 Idx new_alasts = 2 * subtop->alasts + 1;
4398 re_sub_match_last_t **new_array = re_realloc (subtop->lasts,
4399 re_sub_match_last_t *,
4401 if (BE (new_array == NULL, 0))
4403 subtop->lasts = new_array;
4404 subtop->alasts = new_alasts;
4406 new_entry = calloc (1, sizeof (re_sub_match_last_t));
4407 if (BE (new_entry != NULL, 1))
4409 subtop->lasts[subtop->nlasts] = new_entry;
4410 new_entry->node = node;
4411 new_entry->str_idx = str_idx;
4419 sift_ctx_init (re_sift_context_t *sctx, re_dfastate_t **sifted_sts,
4420 re_dfastate_t **limited_sts, Idx last_node, Idx last_str_idx)
4422 sctx->sifted_states = sifted_sts;
4423 sctx->limited_states = limited_sts;
4424 sctx->last_node = last_node;
4425 sctx->last_str_idx = last_str_idx;
4426 re_node_set_init_empty (&sctx->limits);