1 /* Extended regular expression matching and search library.
2 Copyright (C) 2002-2011 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
4 Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>.
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License along
17 with this program; if not, write to the Free Software Foundation,
18 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
20 static reg_errcode_t match_ctx_init (re_match_context_t *cache, int eflags,
21 Idx n) internal_function;
22 static void match_ctx_clean (re_match_context_t *mctx) internal_function;
23 static void match_ctx_free (re_match_context_t *cache) internal_function;
24 static reg_errcode_t match_ctx_add_entry (re_match_context_t *cache, Idx node,
25 Idx str_idx, Idx from, Idx to)
27 static Idx search_cur_bkref_entry (const re_match_context_t *mctx, Idx str_idx)
29 static reg_errcode_t match_ctx_add_subtop (re_match_context_t *mctx, Idx node,
30 Idx str_idx) internal_function;
31 static re_sub_match_last_t * match_ctx_add_sublast (re_sub_match_top_t *subtop,
32 Idx node, Idx str_idx)
34 static void sift_ctx_init (re_sift_context_t *sctx, re_dfastate_t **sifted_sts,
35 re_dfastate_t **limited_sts, Idx last_node,
38 static reg_errcode_t re_search_internal (const regex_t *preg,
39 const char *string, Idx length,
40 Idx start, Idx last_start, Idx stop,
41 size_t nmatch, regmatch_t pmatch[],
42 int eflags) internal_function;
43 static regoff_t re_search_2_stub (struct re_pattern_buffer *bufp,
44 const char *string1, Idx length1,
45 const char *string2, Idx length2,
46 Idx start, regoff_t range,
47 struct re_registers *regs,
48 Idx stop, bool ret_len) internal_function;
49 static regoff_t re_search_stub (struct re_pattern_buffer *bufp,
50 const char *string, Idx length, Idx start,
51 regoff_t range, Idx stop,
52 struct re_registers *regs,
53 bool ret_len) internal_function;
54 static unsigned int re_copy_regs (struct re_registers *regs, regmatch_t *pmatch,
55 Idx nregs, int regs_allocated)
57 static reg_errcode_t prune_impossible_nodes (re_match_context_t *mctx)
59 static Idx check_matching (re_match_context_t *mctx, bool fl_longest_match,
60 Idx *p_match_first) internal_function;
61 static Idx check_halt_state_context (const re_match_context_t *mctx,
62 const re_dfastate_t *state, Idx idx)
64 static void update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
65 regmatch_t *prev_idx_match, Idx cur_node,
66 Idx cur_idx, Idx nmatch) internal_function;
67 static reg_errcode_t push_fail_stack (struct re_fail_stack_t *fs,
68 Idx str_idx, Idx dest_node, Idx nregs,
70 re_node_set *eps_via_nodes)
72 static reg_errcode_t set_regs (const regex_t *preg,
73 const re_match_context_t *mctx,
74 size_t nmatch, regmatch_t *pmatch,
75 bool fl_backtrack) internal_function;
76 static reg_errcode_t free_fail_stack_return (struct re_fail_stack_t *fs)
80 static int sift_states_iter_mb (const re_match_context_t *mctx,
81 re_sift_context_t *sctx,
82 Idx node_idx, Idx str_idx, Idx max_str_idx)
84 #endif /* RE_ENABLE_I18N */
85 static reg_errcode_t sift_states_backward (const re_match_context_t *mctx,
86 re_sift_context_t *sctx)
88 static reg_errcode_t build_sifted_states (const re_match_context_t *mctx,
89 re_sift_context_t *sctx, Idx str_idx,
90 re_node_set *cur_dest)
92 static reg_errcode_t update_cur_sifted_state (const re_match_context_t *mctx,
93 re_sift_context_t *sctx,
95 re_node_set *dest_nodes)
97 static reg_errcode_t add_epsilon_src_nodes (const re_dfa_t *dfa,
98 re_node_set *dest_nodes,
99 const re_node_set *candidates)
101 static bool check_dst_limits (const re_match_context_t *mctx,
102 const re_node_set *limits,
103 Idx dst_node, Idx dst_idx, Idx src_node,
104 Idx src_idx) internal_function;
105 static int check_dst_limits_calc_pos_1 (const re_match_context_t *mctx,
106 int boundaries, Idx subexp_idx,
107 Idx from_node, Idx bkref_idx)
109 static int check_dst_limits_calc_pos (const re_match_context_t *mctx,
110 Idx limit, Idx subexp_idx,
111 Idx node, Idx str_idx,
112 Idx bkref_idx) internal_function;
113 static reg_errcode_t check_subexp_limits (const re_dfa_t *dfa,
114 re_node_set *dest_nodes,
115 const re_node_set *candidates,
117 struct re_backref_cache_entry *bkref_ents,
118 Idx str_idx) internal_function;
119 static reg_errcode_t sift_states_bkref (const re_match_context_t *mctx,
120 re_sift_context_t *sctx,
121 Idx str_idx, const re_node_set *candidates)
123 static reg_errcode_t merge_state_array (const re_dfa_t *dfa,
125 re_dfastate_t **src, Idx num)
127 static re_dfastate_t *find_recover_state (reg_errcode_t *err,
128 re_match_context_t *mctx) internal_function;
129 static re_dfastate_t *transit_state (reg_errcode_t *err,
130 re_match_context_t *mctx,
131 re_dfastate_t *state) internal_function;
132 static re_dfastate_t *merge_state_with_log (reg_errcode_t *err,
133 re_match_context_t *mctx,
134 re_dfastate_t *next_state)
136 static reg_errcode_t check_subexp_matching_top (re_match_context_t *mctx,
137 re_node_set *cur_nodes,
138 Idx str_idx) internal_function;
140 static re_dfastate_t *transit_state_sb (reg_errcode_t *err,
141 re_match_context_t *mctx,
142 re_dfastate_t *pstate)
145 #ifdef RE_ENABLE_I18N
146 static reg_errcode_t transit_state_mb (re_match_context_t *mctx,
147 re_dfastate_t *pstate)
149 #endif /* RE_ENABLE_I18N */
150 static reg_errcode_t transit_state_bkref (re_match_context_t *mctx,
151 const re_node_set *nodes)
153 static reg_errcode_t get_subexp (re_match_context_t *mctx,
154 Idx bkref_node, Idx bkref_str_idx)
156 static reg_errcode_t get_subexp_sub (re_match_context_t *mctx,
157 const re_sub_match_top_t *sub_top,
158 re_sub_match_last_t *sub_last,
159 Idx bkref_node, Idx bkref_str)
161 static Idx find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
162 Idx subexp_idx, int type) internal_function;
163 static reg_errcode_t check_arrival (re_match_context_t *mctx,
164 state_array_t *path, Idx top_node,
165 Idx top_str, Idx last_node, Idx last_str,
166 int type) internal_function;
167 static reg_errcode_t check_arrival_add_next_nodes (re_match_context_t *mctx,
169 re_node_set *cur_nodes,
170 re_node_set *next_nodes)
172 static reg_errcode_t check_arrival_expand_ecl (const re_dfa_t *dfa,
173 re_node_set *cur_nodes,
174 Idx ex_subexp, int type)
176 static reg_errcode_t check_arrival_expand_ecl_sub (const re_dfa_t *dfa,
177 re_node_set *dst_nodes,
178 Idx target, Idx ex_subexp,
179 int type) internal_function;
180 static reg_errcode_t expand_bkref_cache (re_match_context_t *mctx,
181 re_node_set *cur_nodes, Idx cur_str,
182 Idx subexp_num, int type)
184 static bool build_trtable (const re_dfa_t *dfa,
185 re_dfastate_t *state) internal_function;
186 #ifdef RE_ENABLE_I18N
187 static int check_node_accept_bytes (const re_dfa_t *dfa, Idx node_idx,
188 const re_string_t *input, Idx idx)
191 static unsigned int find_collation_sequence_value (const unsigned char *mbs,
195 #endif /* RE_ENABLE_I18N */
196 static Idx group_nodes_into_DFAstates (const re_dfa_t *dfa,
197 const re_dfastate_t *state,
198 re_node_set *states_node,
199 bitset_t *states_ch) internal_function;
200 static bool check_node_accept (const re_match_context_t *mctx,
201 const re_token_t *node, Idx idx)
203 static reg_errcode_t extend_buffers (re_match_context_t *mctx)
206 /* Entry point for POSIX code. */
208 /* regexec searches for a given pattern, specified by PREG, in the
211 If NMATCH is zero or REG_NOSUB was set in the cflags argument to
212 `regcomp', we ignore PMATCH. Otherwise, we assume PMATCH has at
213 least NMATCH elements, and we set them to the offsets of the
214 corresponding matched substrings.
216 EFLAGS specifies `execution flags' which affect matching: if
217 REG_NOTBOL is set, then ^ does not match at the beginning of the
218 string; if REG_NOTEOL is set, then $ does not match at the end.
220 We return 0 if we find a match and REG_NOMATCH if not. */
223 regexec (preg, string, nmatch, pmatch, eflags)
224 const regex_t *_Restrict_ preg;
225 const char *_Restrict_ string;
227 regmatch_t pmatch[_Restrict_arr_];
233 re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
236 if (eflags & ~(REG_NOTBOL | REG_NOTEOL | REG_STARTEND))
239 if (eflags & REG_STARTEND)
241 start = pmatch[0].rm_so;
242 length = pmatch[0].rm_eo;
247 length = strlen (string);
250 __libc_lock_lock (dfa->lock);
252 err = re_search_internal (preg, string, length, start, length,
253 length, 0, NULL, eflags);
255 err = re_search_internal (preg, string, length, start, length,
256 length, nmatch, pmatch, eflags);
257 __libc_lock_unlock (dfa->lock);
258 return err != REG_NOERROR;
262 # include <shlib-compat.h>
263 versioned_symbol (libc, __regexec, regexec, GLIBC_2_3_4);
265 # if SHLIB_COMPAT (libc, GLIBC_2_0, GLIBC_2_3_4)
266 __typeof__ (__regexec) __compat_regexec;
269 attribute_compat_text_section
270 __compat_regexec (const regex_t *_Restrict_ preg,
271 const char *_Restrict_ string, size_t nmatch,
272 regmatch_t pmatch[], int eflags)
274 return regexec (preg, string, nmatch, pmatch,
275 eflags & (REG_NOTBOL | REG_NOTEOL));
277 compat_symbol (libc, __compat_regexec, regexec, GLIBC_2_0);
281 /* Entry points for GNU code. */
283 /* re_match, re_search, re_match_2, re_search_2
285 The former two functions operate on STRING with length LENGTH,
286 while the later two operate on concatenation of STRING1 and STRING2
287 with lengths LENGTH1 and LENGTH2, respectively.
289 re_match() matches the compiled pattern in BUFP against the string,
290 starting at index START.
292 re_search() first tries matching at index START, then it tries to match
293 starting from index START + 1, and so on. The last start position tried
294 is START + RANGE. (Thus RANGE = 0 forces re_search to operate the same
297 The parameter STOP of re_{match,search}_2 specifies that no match exceeding
298 the first STOP characters of the concatenation of the strings should be
301 If REGS is not NULL, and BUFP->no_sub is not set, the offsets of the match
302 and all groups is stored in REGS. (For the "_2" variants, the offsets are
303 computed relative to the concatenation, not relative to the individual
306 On success, re_match* functions return the length of the match, re_search*
307 return the position of the start of the match. Return value -1 means no
308 match was found and -2 indicates an internal error. */
311 re_match (bufp, string, length, start, regs)
312 struct re_pattern_buffer *bufp;
315 struct re_registers *regs;
317 return re_search_stub (bufp, string, length, start, 0, length, regs, true);
320 weak_alias (__re_match, re_match)
324 re_search (bufp, string, length, start, range, regs)
325 struct re_pattern_buffer *bufp;
329 struct re_registers *regs;
331 return re_search_stub (bufp, string, length, start, range, length, regs,
335 weak_alias (__re_search, re_search)
339 re_match_2 (bufp, string1, length1, string2, length2, start, regs, stop)
340 struct re_pattern_buffer *bufp;
341 const char *string1, *string2;
342 Idx length1, length2, start, stop;
343 struct re_registers *regs;
345 return re_search_2_stub (bufp, string1, length1, string2, length2,
346 start, 0, regs, stop, true);
349 weak_alias (__re_match_2, re_match_2)
353 re_search_2 (bufp, string1, length1, string2, length2, start, range, regs, stop)
354 struct re_pattern_buffer *bufp;
355 const char *string1, *string2;
356 Idx length1, length2, start, stop;
358 struct re_registers *regs;
360 return re_search_2_stub (bufp, string1, length1, string2, length2,
361 start, range, regs, stop, false);
364 weak_alias (__re_search_2, re_search_2)
369 re_search_2_stub (struct re_pattern_buffer *bufp,
370 const char *string1, Idx length1,
371 const char *string2, Idx length2,
372 Idx start, regoff_t range, struct re_registers *regs,
373 Idx stop, bool ret_len)
377 Idx len = length1 + length2;
380 if (BE (length1 < 0 || length2 < 0 || stop < 0 || len < length1, 0))
383 /* Concatenate the strings. */
387 s = re_malloc (char, len);
389 if (BE (s == NULL, 0))
392 memcpy (__mempcpy (s, string1, length1), string2, length2);
394 memcpy (s, string1, length1);
395 memcpy (s + length1, string2, length2);
404 rval = re_search_stub (bufp, str, len, start, range, stop, regs,
410 /* The parameters have the same meaning as those of re_search.
411 Additional parameters:
412 If RET_LEN is true the length of the match is returned (re_match style);
413 otherwise the position of the match is returned. */
417 re_search_stub (struct re_pattern_buffer *bufp,
418 const char *string, Idx length,
419 Idx start, regoff_t range, Idx stop, struct re_registers *regs,
422 reg_errcode_t result;
428 re_dfa_t *dfa = (re_dfa_t *) bufp->buffer;
430 Idx last_start = start + range;
432 /* Check for out-of-range. */
433 if (BE (start < 0 || start > length, 0))
435 if (BE (length < last_start || (0 <= range && last_start < start), 0))
437 else if (BE (last_start < 0 || (range < 0 && start <= last_start), 0))
440 __libc_lock_lock (dfa->lock);
442 eflags |= (bufp->not_bol) ? REG_NOTBOL : 0;
443 eflags |= (bufp->not_eol) ? REG_NOTEOL : 0;
445 /* Compile fastmap if we haven't yet. */
446 if (start < last_start && bufp->fastmap != NULL && !bufp->fastmap_accurate)
447 re_compile_fastmap (bufp);
449 if (BE (bufp->no_sub, 0))
452 /* We need at least 1 register. */
455 else if (BE (bufp->regs_allocated == REGS_FIXED
456 && regs->num_regs <= bufp->re_nsub, 0))
458 nregs = regs->num_regs;
459 if (BE (nregs < 1, 0))
461 /* Nothing can be copied to regs. */
467 nregs = bufp->re_nsub + 1;
468 pmatch = re_malloc (regmatch_t, nregs);
469 if (BE (pmatch == NULL, 0))
475 result = re_search_internal (bufp, string, length, start, last_start, stop,
476 nregs, pmatch, eflags);
480 /* I hope we needn't fill ther regs with -1's when no match was found. */
481 if (result != REG_NOERROR)
483 else if (regs != NULL)
485 /* If caller wants register contents data back, copy them. */
486 bufp->regs_allocated = re_copy_regs (regs, pmatch, nregs,
487 bufp->regs_allocated);
488 if (BE (bufp->regs_allocated == REGS_UNALLOCATED, 0))
492 if (BE (rval == 0, 1))
496 assert (pmatch[0].rm_so == start);
497 rval = pmatch[0].rm_eo - start;
500 rval = pmatch[0].rm_so;
504 __libc_lock_unlock (dfa->lock);
510 re_copy_regs (struct re_registers *regs, regmatch_t *pmatch, Idx nregs,
513 int rval = REGS_REALLOCATE;
515 Idx need_regs = nregs + 1;
516 /* We need one extra element beyond `num_regs' for the `-1' marker GNU code
519 /* Have the register data arrays been allocated? */
520 if (regs_allocated == REGS_UNALLOCATED)
521 { /* No. So allocate them with malloc. */
522 regs->start = re_malloc (regoff_t, need_regs);
523 if (BE (regs->start == NULL, 0))
524 return REGS_UNALLOCATED;
525 regs->end = re_malloc (regoff_t, need_regs);
526 if (BE (regs->end == NULL, 0))
528 re_free (regs->start);
529 return REGS_UNALLOCATED;
531 regs->num_regs = need_regs;
533 else if (regs_allocated == REGS_REALLOCATE)
534 { /* Yes. If we need more elements than were already
535 allocated, reallocate them. If we need fewer, just
537 if (BE (need_regs > regs->num_regs, 0))
539 regoff_t *new_start = re_realloc (regs->start, regoff_t, need_regs);
541 if (BE (new_start == NULL, 0))
542 return REGS_UNALLOCATED;
543 new_end = re_realloc (regs->end, regoff_t, need_regs);
544 if (BE (new_end == NULL, 0))
547 return REGS_UNALLOCATED;
549 regs->start = new_start;
551 regs->num_regs = need_regs;
556 assert (regs_allocated == REGS_FIXED);
557 /* This function may not be called with REGS_FIXED and nregs too big. */
558 assert (regs->num_regs >= nregs);
563 for (i = 0; i < nregs; ++i)
565 regs->start[i] = pmatch[i].rm_so;
566 regs->end[i] = pmatch[i].rm_eo;
568 for ( ; i < regs->num_regs; ++i)
569 regs->start[i] = regs->end[i] = -1;
574 /* Set REGS to hold NUM_REGS registers, storing them in STARTS and
575 ENDS. Subsequent matches using PATTERN_BUFFER and REGS will use
576 this memory for recording register information. STARTS and ENDS
577 must be allocated using the malloc library routine, and must each
578 be at least NUM_REGS * sizeof (regoff_t) bytes long.
580 If NUM_REGS == 0, then subsequent matches should allocate their own
583 Unless this function is called, the first search or match using
584 PATTERN_BUFFER will allocate its own register data, without
585 freeing the old data. */
588 re_set_registers (bufp, regs, num_regs, starts, ends)
589 struct re_pattern_buffer *bufp;
590 struct re_registers *regs;
591 __re_size_t num_regs;
592 regoff_t *starts, *ends;
596 bufp->regs_allocated = REGS_REALLOCATE;
597 regs->num_regs = num_regs;
598 regs->start = starts;
603 bufp->regs_allocated = REGS_UNALLOCATED;
605 regs->start = regs->end = NULL;
609 weak_alias (__re_set_registers, re_set_registers)
612 /* Entry points compatible with 4.2 BSD regex library. We don't define
613 them unless specifically requested. */
615 #if defined _REGEX_RE_COMP || defined _LIBC
623 return 0 == regexec (&re_comp_buf, s, 0, NULL, 0);
625 #endif /* _REGEX_RE_COMP */
627 /* Internal entry point. */
629 /* Searches for a compiled pattern PREG in the string STRING, whose
630 length is LENGTH. NMATCH, PMATCH, and EFLAGS have the same
631 meaning as with regexec. LAST_START is START + RANGE, where
632 START and RANGE have the same meaning as with re_search.
633 Return REG_NOERROR if we find a match, and REG_NOMATCH if not,
634 otherwise return the error code.
635 Note: We assume front end functions already check ranges.
636 (0 <= LAST_START && LAST_START <= LENGTH) */
639 internal_function __attribute_warn_unused_result__
640 re_search_internal (const regex_t *preg,
641 const char *string, Idx length,
642 Idx start, Idx last_start, Idx stop,
643 size_t nmatch, regmatch_t pmatch[],
647 const re_dfa_t *dfa = (const re_dfa_t *) preg->buffer;
648 Idx left_lim, right_lim;
650 bool fl_longest_match;
653 Idx match_last = REG_MISSING;
657 #if defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L)
658 re_match_context_t mctx = { .dfa = dfa };
660 re_match_context_t mctx;
662 char *fastmap = ((preg->fastmap != NULL && preg->fastmap_accurate
663 && start != last_start && !preg->can_be_null)
664 ? preg->fastmap : NULL);
665 RE_TRANSLATE_TYPE t = preg->translate;
667 #if !(defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L))
668 memset (&mctx, '\0', sizeof (re_match_context_t));
672 extra_nmatch = (nmatch > preg->re_nsub) ? nmatch - (preg->re_nsub + 1) : 0;
673 nmatch -= extra_nmatch;
675 /* Check if the DFA haven't been compiled. */
676 if (BE (preg->used == 0 || dfa->init_state == NULL
677 || dfa->init_state_word == NULL || dfa->init_state_nl == NULL
678 || dfa->init_state_begbuf == NULL, 0))
682 /* We assume front-end functions already check them. */
683 assert (0 <= last_start && last_start <= length);
686 /* If initial states with non-begbuf contexts have no elements,
687 the regex must be anchored. If preg->newline_anchor is set,
688 we'll never use init_state_nl, so do not check it. */
689 if (dfa->init_state->nodes.nelem == 0
690 && dfa->init_state_word->nodes.nelem == 0
691 && (dfa->init_state_nl->nodes.nelem == 0
692 || !preg->newline_anchor))
694 if (start != 0 && last_start != 0)
696 start = last_start = 0;
699 /* We must check the longest matching, if nmatch > 0. */
700 fl_longest_match = (nmatch != 0 || dfa->nbackref);
702 err = re_string_allocate (&mctx.input, string, length, dfa->nodes_len + 1,
703 preg->translate, (preg->syntax & RE_ICASE) != 0,
705 if (BE (err != REG_NOERROR, 0))
707 mctx.input.stop = stop;
708 mctx.input.raw_stop = stop;
709 mctx.input.newline_anchor = preg->newline_anchor;
711 err = match_ctx_init (&mctx, eflags, dfa->nbackref * 2);
712 if (BE (err != REG_NOERROR, 0))
715 /* We will log all the DFA states through which the dfa pass,
716 if nmatch > 1, or this dfa has "multibyte node", which is a
717 back-reference or a node which can accept multibyte character or
718 multi character collating element. */
719 if (nmatch > 1 || dfa->has_mb_node)
721 /* Avoid overflow. */
722 if (BE (SIZE_MAX / sizeof (re_dfastate_t *) <= mctx.input.bufs_len, 0))
728 mctx.state_log = re_malloc (re_dfastate_t *, mctx.input.bufs_len + 1);
729 if (BE (mctx.state_log == NULL, 0))
736 mctx.state_log = NULL;
739 mctx.input.tip_context = (eflags & REG_NOTBOL) ? CONTEXT_BEGBUF
740 : CONTEXT_NEWLINE | CONTEXT_BEGBUF;
742 /* Check incrementally whether of not the input string match. */
743 incr = (last_start < start) ? -1 : 1;
744 left_lim = (last_start < start) ? last_start : start;
745 right_lim = (last_start < start) ? start : last_start;
746 sb = dfa->mb_cur_max == 1;
749 ? ((sb || !(preg->syntax & RE_ICASE || t) ? 4 : 0)
750 | (start <= last_start ? 2 : 0)
751 | (t != NULL ? 1 : 0))
754 for (;; match_first += incr)
757 if (match_first < left_lim || right_lim < match_first)
760 /* Advance as rapidly as possible through the string, until we
761 find a plausible place to start matching. This may be done
762 with varying efficiency, so there are various possibilities:
763 only the most common of them are specialized, in order to
764 save on code size. We use a switch statement for speed. */
772 /* Fastmap with single-byte translation, match forward. */
773 while (BE (match_first < right_lim, 1)
774 && !fastmap[t[(unsigned char) string[match_first]]])
776 goto forward_match_found_start_or_reached_end;
779 /* Fastmap without translation, match forward. */
780 while (BE (match_first < right_lim, 1)
781 && !fastmap[(unsigned char) string[match_first]])
784 forward_match_found_start_or_reached_end:
785 if (BE (match_first == right_lim, 0))
787 ch = match_first >= length
788 ? 0 : (unsigned char) string[match_first];
789 if (!fastmap[t ? t[ch] : ch])
796 /* Fastmap without multi-byte translation, match backwards. */
797 while (match_first >= left_lim)
799 ch = match_first >= length
800 ? 0 : (unsigned char) string[match_first];
801 if (fastmap[t ? t[ch] : ch])
805 if (match_first < left_lim)
810 /* In this case, we can't determine easily the current byte,
811 since it might be a component byte of a multibyte
812 character. Then we use the constructed buffer instead. */
815 /* If MATCH_FIRST is out of the valid range, reconstruct the
817 __re_size_t offset = match_first - mctx.input.raw_mbs_idx;
818 if (BE (offset >= (__re_size_t) mctx.input.valid_raw_len, 0))
820 err = re_string_reconstruct (&mctx.input, match_first,
822 if (BE (err != REG_NOERROR, 0))
825 offset = match_first - mctx.input.raw_mbs_idx;
827 /* If MATCH_FIRST is out of the buffer, leave it as '\0'.
828 Note that MATCH_FIRST must not be smaller than 0. */
829 ch = (match_first >= length
830 ? 0 : re_string_byte_at (&mctx.input, offset));
834 if (match_first < left_lim || match_first > right_lim)
843 /* Reconstruct the buffers so that the matcher can assume that
844 the matching starts from the beginning of the buffer. */
845 err = re_string_reconstruct (&mctx.input, match_first, eflags);
846 if (BE (err != REG_NOERROR, 0))
849 #ifdef RE_ENABLE_I18N
850 /* Don't consider this char as a possible match start if it part,
851 yet isn't the head, of a multibyte character. */
852 if (!sb && !re_string_first_byte (&mctx.input, 0))
856 /* It seems to be appropriate one, then use the matcher. */
857 /* We assume that the matching starts from 0. */
858 mctx.state_log_top = mctx.nbkref_ents = mctx.max_mb_elem_len = 0;
859 match_last = check_matching (&mctx, fl_longest_match,
860 start <= last_start ? &match_first : NULL);
861 if (match_last != REG_MISSING)
863 if (BE (match_last == REG_ERROR, 0))
870 mctx.match_last = match_last;
871 if ((!preg->no_sub && nmatch > 1) || dfa->nbackref)
873 re_dfastate_t *pstate = mctx.state_log[match_last];
874 mctx.last_node = check_halt_state_context (&mctx, pstate,
877 if ((!preg->no_sub && nmatch > 1 && dfa->has_plural_match)
880 err = prune_impossible_nodes (&mctx);
881 if (err == REG_NOERROR)
883 if (BE (err != REG_NOMATCH, 0))
885 match_last = REG_MISSING;
888 break; /* We found a match. */
892 match_ctx_clean (&mctx);
896 assert (match_last != REG_MISSING);
897 assert (err == REG_NOERROR);
900 /* Set pmatch[] if we need. */
905 /* Initialize registers. */
906 for (reg_idx = 1; reg_idx < nmatch; ++reg_idx)
907 pmatch[reg_idx].rm_so = pmatch[reg_idx].rm_eo = -1;
909 /* Set the points where matching start/end. */
911 pmatch[0].rm_eo = mctx.match_last;
912 /* FIXME: This function should fail if mctx.match_last exceeds
913 the maximum possible regoff_t value. We need a new error
914 code REG_OVERFLOW. */
916 if (!preg->no_sub && nmatch > 1)
918 err = set_regs (preg, &mctx, nmatch, pmatch,
919 dfa->has_plural_match && dfa->nbackref > 0);
920 if (BE (err != REG_NOERROR, 0))
924 /* At last, add the offset to the each registers, since we slided
925 the buffers so that we could assume that the matching starts
927 for (reg_idx = 0; reg_idx < nmatch; ++reg_idx)
928 if (pmatch[reg_idx].rm_so != -1)
930 #ifdef RE_ENABLE_I18N
931 if (BE (mctx.input.offsets_needed != 0, 0))
933 pmatch[reg_idx].rm_so =
934 (pmatch[reg_idx].rm_so == mctx.input.valid_len
935 ? mctx.input.valid_raw_len
936 : mctx.input.offsets[pmatch[reg_idx].rm_so]);
937 pmatch[reg_idx].rm_eo =
938 (pmatch[reg_idx].rm_eo == mctx.input.valid_len
939 ? mctx.input.valid_raw_len
940 : mctx.input.offsets[pmatch[reg_idx].rm_eo]);
943 assert (mctx.input.offsets_needed == 0);
945 pmatch[reg_idx].rm_so += match_first;
946 pmatch[reg_idx].rm_eo += match_first;
948 for (reg_idx = 0; reg_idx < extra_nmatch; ++reg_idx)
950 pmatch[nmatch + reg_idx].rm_so = -1;
951 pmatch[nmatch + reg_idx].rm_eo = -1;
955 for (reg_idx = 0; reg_idx + 1 < nmatch; reg_idx++)
956 if (dfa->subexp_map[reg_idx] != reg_idx)
958 pmatch[reg_idx + 1].rm_so
959 = pmatch[dfa->subexp_map[reg_idx] + 1].rm_so;
960 pmatch[reg_idx + 1].rm_eo
961 = pmatch[dfa->subexp_map[reg_idx] + 1].rm_eo;
966 re_free (mctx.state_log);
968 match_ctx_free (&mctx);
969 re_string_destruct (&mctx.input);
974 internal_function __attribute_warn_unused_result__
975 prune_impossible_nodes (re_match_context_t *mctx)
977 const re_dfa_t *const dfa = mctx->dfa;
978 Idx halt_node, match_last;
980 re_dfastate_t **sifted_states;
981 re_dfastate_t **lim_states = NULL;
982 re_sift_context_t sctx;
984 assert (mctx->state_log != NULL);
986 match_last = mctx->match_last;
987 halt_node = mctx->last_node;
989 /* Avoid overflow. */
990 if (BE (SIZE_MAX / sizeof (re_dfastate_t *) <= match_last, 0))
993 sifted_states = re_malloc (re_dfastate_t *, match_last + 1);
994 if (BE (sifted_states == NULL, 0))
1001 lim_states = re_malloc (re_dfastate_t *, match_last + 1);
1002 if (BE (lim_states == NULL, 0))
1009 memset (lim_states, '\0',
1010 sizeof (re_dfastate_t *) * (match_last + 1));
1011 sift_ctx_init (&sctx, sifted_states, lim_states, halt_node,
1013 ret = sift_states_backward (mctx, &sctx);
1014 re_node_set_free (&sctx.limits);
1015 if (BE (ret != REG_NOERROR, 0))
1017 if (sifted_states[0] != NULL || lim_states[0] != NULL)
1022 if (! REG_VALID_INDEX (match_last))
1027 } while (mctx->state_log[match_last] == NULL
1028 || !mctx->state_log[match_last]->halt);
1029 halt_node = check_halt_state_context (mctx,
1030 mctx->state_log[match_last],
1033 ret = merge_state_array (dfa, sifted_states, lim_states,
1035 re_free (lim_states);
1037 if (BE (ret != REG_NOERROR, 0))
1042 sift_ctx_init (&sctx, sifted_states, lim_states, halt_node, match_last);
1043 ret = sift_states_backward (mctx, &sctx);
1044 re_node_set_free (&sctx.limits);
1045 if (BE (ret != REG_NOERROR, 0))
1047 if (sifted_states[0] == NULL)
1053 re_free (mctx->state_log);
1054 mctx->state_log = sifted_states;
1055 sifted_states = NULL;
1056 mctx->last_node = halt_node;
1057 mctx->match_last = match_last;
1060 re_free (sifted_states);
1061 re_free (lim_states);
1065 /* Acquire an initial state and return it.
1066 We must select appropriate initial state depending on the context,
1067 since initial states may have constraints like "\<", "^", etc.. */
1069 static inline re_dfastate_t *
1070 __attribute ((always_inline)) internal_function
1071 acquire_init_state_context (reg_errcode_t *err, const re_match_context_t *mctx,
1074 const re_dfa_t *const dfa = mctx->dfa;
1075 if (dfa->init_state->has_constraint)
1077 unsigned int context;
1078 context = re_string_context_at (&mctx->input, idx - 1, mctx->eflags);
1079 if (IS_WORD_CONTEXT (context))
1080 return dfa->init_state_word;
1081 else if (IS_ORDINARY_CONTEXT (context))
1082 return dfa->init_state;
1083 else if (IS_BEGBUF_CONTEXT (context) && IS_NEWLINE_CONTEXT (context))
1084 return dfa->init_state_begbuf;
1085 else if (IS_NEWLINE_CONTEXT (context))
1086 return dfa->init_state_nl;
1087 else if (IS_BEGBUF_CONTEXT (context))
1089 /* It is relatively rare case, then calculate on demand. */
1090 return re_acquire_state_context (err, dfa,
1091 dfa->init_state->entrance_nodes,
1095 /* Must not happen? */
1096 return dfa->init_state;
1099 return dfa->init_state;
1102 /* Check whether the regular expression match input string INPUT or not,
1103 and return the index where the matching end. Return REG_MISSING if
1104 there is no match, and return REG_ERROR in case of an error.
1105 FL_LONGEST_MATCH means we want the POSIX longest matching.
1106 If P_MATCH_FIRST is not NULL, and the match fails, it is set to the
1107 next place where we may want to try matching.
1108 Note that the matcher assume that the maching starts from the current
1109 index of the buffer. */
1112 internal_function __attribute_warn_unused_result__
1113 check_matching (re_match_context_t *mctx, bool fl_longest_match,
1116 const re_dfa_t *const dfa = mctx->dfa;
1119 Idx match_last = REG_MISSING;
1120 Idx cur_str_idx = re_string_cur_idx (&mctx->input);
1121 re_dfastate_t *cur_state;
1122 bool at_init_state = p_match_first != NULL;
1123 Idx next_start_idx = cur_str_idx;
1126 cur_state = acquire_init_state_context (&err, mctx, cur_str_idx);
1127 /* An initial state must not be NULL (invalid). */
1128 if (BE (cur_state == NULL, 0))
1130 assert (err == REG_ESPACE);
1134 if (mctx->state_log != NULL)
1136 mctx->state_log[cur_str_idx] = cur_state;
1138 /* Check OP_OPEN_SUBEXP in the initial state in case that we use them
1139 later. E.g. Processing back references. */
1140 if (BE (dfa->nbackref, 0))
1142 at_init_state = false;
1143 err = check_subexp_matching_top (mctx, &cur_state->nodes, 0);
1144 if (BE (err != REG_NOERROR, 0))
1147 if (cur_state->has_backref)
1149 err = transit_state_bkref (mctx, &cur_state->nodes);
1150 if (BE (err != REG_NOERROR, 0))
1156 /* If the RE accepts NULL string. */
1157 if (BE (cur_state->halt, 0))
1159 if (!cur_state->has_constraint
1160 || check_halt_state_context (mctx, cur_state, cur_str_idx))
1162 if (!fl_longest_match)
1166 match_last = cur_str_idx;
1172 while (!re_string_eoi (&mctx->input))
1174 re_dfastate_t *old_state = cur_state;
1175 Idx next_char_idx = re_string_cur_idx (&mctx->input) + 1;
1177 if (BE (next_char_idx >= mctx->input.bufs_len, 0)
1178 || (BE (next_char_idx >= mctx->input.valid_len, 0)
1179 && mctx->input.valid_len < mctx->input.len))
1181 err = extend_buffers (mctx);
1182 if (BE (err != REG_NOERROR, 0))
1184 assert (err == REG_ESPACE);
1189 cur_state = transit_state (&err, mctx, cur_state);
1190 if (mctx->state_log != NULL)
1191 cur_state = merge_state_with_log (&err, mctx, cur_state);
1193 if (cur_state == NULL)
1195 /* Reached the invalid state or an error. Try to recover a valid
1196 state using the state log, if available and if we have not
1197 already found a valid (even if not the longest) match. */
1198 if (BE (err != REG_NOERROR, 0))
1201 if (mctx->state_log == NULL
1202 || (match && !fl_longest_match)
1203 || (cur_state = find_recover_state (&err, mctx)) == NULL)
1207 if (BE (at_init_state, 0))
1209 if (old_state == cur_state)
1210 next_start_idx = next_char_idx;
1212 at_init_state = false;
1215 if (cur_state->halt)
1217 /* Reached a halt state.
1218 Check the halt state can satisfy the current context. */
1219 if (!cur_state->has_constraint
1220 || check_halt_state_context (mctx, cur_state,
1221 re_string_cur_idx (&mctx->input)))
1223 /* We found an appropriate halt state. */
1224 match_last = re_string_cur_idx (&mctx->input);
1227 /* We found a match, do not modify match_first below. */
1228 p_match_first = NULL;
1229 if (!fl_longest_match)
1236 *p_match_first += next_start_idx;
1241 /* Check NODE match the current context. */
1245 check_halt_node_context (const re_dfa_t *dfa, Idx node, unsigned int context)
1247 re_token_type_t type = dfa->nodes[node].type;
1248 unsigned int constraint = dfa->nodes[node].constraint;
1249 if (type != END_OF_RE)
1253 if (NOT_SATISFY_NEXT_CONSTRAINT (constraint, context))
1258 /* Check the halt state STATE match the current context.
1259 Return 0 if not match, if the node, STATE has, is a halt node and
1260 match the context, return the node. */
1264 check_halt_state_context (const re_match_context_t *mctx,
1265 const re_dfastate_t *state, Idx idx)
1268 unsigned int context;
1270 assert (state->halt);
1272 context = re_string_context_at (&mctx->input, idx, mctx->eflags);
1273 for (i = 0; i < state->nodes.nelem; ++i)
1274 if (check_halt_node_context (mctx->dfa, state->nodes.elems[i], context))
1275 return state->nodes.elems[i];
1279 /* Compute the next node to which "NFA" transit from NODE("NFA" is a NFA
1280 corresponding to the DFA).
1281 Return the destination node, and update EPS_VIA_NODES;
1282 return REG_MISSING in case of errors. */
1286 proceed_next_node (const re_match_context_t *mctx, Idx nregs, regmatch_t *regs,
1287 Idx *pidx, Idx node, re_node_set *eps_via_nodes,
1288 struct re_fail_stack_t *fs)
1290 const re_dfa_t *const dfa = mctx->dfa;
1293 if (IS_EPSILON_NODE (dfa->nodes[node].type))
1295 re_node_set *cur_nodes = &mctx->state_log[*pidx]->nodes;
1296 re_node_set *edests = &dfa->edests[node];
1298 ok = re_node_set_insert (eps_via_nodes, node);
1301 /* Pick up a valid destination, or return REG_MISSING if none
1303 for (dest_node = REG_MISSING, i = 0; i < edests->nelem; ++i)
1305 Idx candidate = edests->elems[i];
1306 if (!re_node_set_contains (cur_nodes, candidate))
1308 if (dest_node == REG_MISSING)
1309 dest_node = candidate;
1313 /* In order to avoid infinite loop like "(a*)*", return the second
1314 epsilon-transition if the first was already considered. */
1315 if (re_node_set_contains (eps_via_nodes, dest_node))
1318 /* Otherwise, push the second epsilon-transition on the fail stack. */
1320 && push_fail_stack (fs, *pidx, candidate, nregs, regs,
1324 /* We know we are going to exit. */
1333 re_token_type_t type = dfa->nodes[node].type;
1335 #ifdef RE_ENABLE_I18N
1336 if (dfa->nodes[node].accept_mb)
1337 naccepted = check_node_accept_bytes (dfa, node, &mctx->input, *pidx);
1339 #endif /* RE_ENABLE_I18N */
1340 if (type == OP_BACK_REF)
1342 Idx subexp_idx = dfa->nodes[node].opr.idx + 1;
1343 naccepted = regs[subexp_idx].rm_eo - regs[subexp_idx].rm_so;
1346 if (regs[subexp_idx].rm_so == -1 || regs[subexp_idx].rm_eo == -1)
1350 char *buf = (char *) re_string_get_buffer (&mctx->input);
1351 if (memcmp (buf + regs[subexp_idx].rm_so, buf + *pidx,
1360 ok = re_node_set_insert (eps_via_nodes, node);
1363 dest_node = dfa->edests[node].elems[0];
1364 if (re_node_set_contains (&mctx->state_log[*pidx]->nodes,
1371 || check_node_accept (mctx, dfa->nodes + node, *pidx))
1373 Idx dest_node = dfa->nexts[node];
1374 *pidx = (naccepted == 0) ? *pidx + 1 : *pidx + naccepted;
1375 if (fs && (*pidx > mctx->match_last || mctx->state_log[*pidx] == NULL
1376 || !re_node_set_contains (&mctx->state_log[*pidx]->nodes,
1379 re_node_set_empty (eps_via_nodes);
1386 static reg_errcode_t
1387 internal_function __attribute_warn_unused_result__
1388 push_fail_stack (struct re_fail_stack_t *fs, Idx str_idx, Idx dest_node,
1389 Idx nregs, regmatch_t *regs, re_node_set *eps_via_nodes)
1392 Idx num = fs->num++;
1393 if (fs->num == fs->alloc)
1395 struct re_fail_stack_ent_t *new_array;
1396 new_array = realloc (fs->stack, (sizeof (struct re_fail_stack_ent_t)
1398 if (new_array == NULL)
1401 fs->stack = new_array;
1403 fs->stack[num].idx = str_idx;
1404 fs->stack[num].node = dest_node;
1405 fs->stack[num].regs = re_malloc (regmatch_t, nregs);
1406 if (fs->stack[num].regs == NULL)
1408 memcpy (fs->stack[num].regs, regs, sizeof (regmatch_t) * nregs);
1409 err = re_node_set_init_copy (&fs->stack[num].eps_via_nodes, eps_via_nodes);
1415 pop_fail_stack (struct re_fail_stack_t *fs, Idx *pidx, Idx nregs,
1416 regmatch_t *regs, re_node_set *eps_via_nodes)
1418 Idx num = --fs->num;
1419 assert (REG_VALID_INDEX (num));
1420 *pidx = fs->stack[num].idx;
1421 memcpy (regs, fs->stack[num].regs, sizeof (regmatch_t) * nregs);
1422 re_node_set_free (eps_via_nodes);
1423 re_free (fs->stack[num].regs);
1424 *eps_via_nodes = fs->stack[num].eps_via_nodes;
1425 return fs->stack[num].node;
1428 /* Set the positions where the subexpressions are starts/ends to registers
1430 Note: We assume that pmatch[0] is already set, and
1431 pmatch[i].rm_so == pmatch[i].rm_eo == -1 for 0 < i < nmatch. */
1433 static reg_errcode_t
1434 internal_function __attribute_warn_unused_result__
1435 set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
1436 regmatch_t *pmatch, bool fl_backtrack)
1438 const re_dfa_t *dfa = (const re_dfa_t *) preg->buffer;
1440 re_node_set eps_via_nodes;
1441 struct re_fail_stack_t *fs;
1442 struct re_fail_stack_t fs_body = { 0, 2, NULL };
1443 regmatch_t *prev_idx_match;
1444 bool prev_idx_match_malloced = false;
1447 assert (nmatch > 1);
1448 assert (mctx->state_log != NULL);
1453 fs->stack = re_malloc (struct re_fail_stack_ent_t, fs->alloc);
1454 if (fs->stack == NULL)
1460 cur_node = dfa->init_node;
1461 re_node_set_init_empty (&eps_via_nodes);
1463 if (__libc_use_alloca (nmatch * sizeof (regmatch_t)))
1464 prev_idx_match = (regmatch_t *) alloca (nmatch * sizeof (regmatch_t));
1467 prev_idx_match = re_malloc (regmatch_t, nmatch);
1468 if (prev_idx_match == NULL)
1470 free_fail_stack_return (fs);
1473 prev_idx_match_malloced = true;
1475 memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
1477 for (idx = pmatch[0].rm_so; idx <= pmatch[0].rm_eo ;)
1479 update_regs (dfa, pmatch, prev_idx_match, cur_node, idx, nmatch);
1481 if (idx == pmatch[0].rm_eo && cur_node == mctx->last_node)
1486 for (reg_idx = 0; reg_idx < nmatch; ++reg_idx)
1487 if (pmatch[reg_idx].rm_so > -1 && pmatch[reg_idx].rm_eo == -1)
1489 if (reg_idx == nmatch)
1491 re_node_set_free (&eps_via_nodes);
1492 if (prev_idx_match_malloced)
1493 re_free (prev_idx_match);
1494 return free_fail_stack_return (fs);
1496 cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
1501 re_node_set_free (&eps_via_nodes);
1502 if (prev_idx_match_malloced)
1503 re_free (prev_idx_match);
1508 /* Proceed to next node. */
1509 cur_node = proceed_next_node (mctx, nmatch, pmatch, &idx, cur_node,
1510 &eps_via_nodes, fs);
1512 if (BE (! REG_VALID_INDEX (cur_node), 0))
1514 if (BE (cur_node == REG_ERROR, 0))
1516 re_node_set_free (&eps_via_nodes);
1517 if (prev_idx_match_malloced)
1518 re_free (prev_idx_match);
1519 free_fail_stack_return (fs);
1523 cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
1527 re_node_set_free (&eps_via_nodes);
1528 if (prev_idx_match_malloced)
1529 re_free (prev_idx_match);
1534 re_node_set_free (&eps_via_nodes);
1535 if (prev_idx_match_malloced)
1536 re_free (prev_idx_match);
1537 return free_fail_stack_return (fs);
1540 static reg_errcode_t
1542 free_fail_stack_return (struct re_fail_stack_t *fs)
1547 for (fs_idx = 0; fs_idx < fs->num; ++fs_idx)
1549 re_node_set_free (&fs->stack[fs_idx].eps_via_nodes);
1550 re_free (fs->stack[fs_idx].regs);
1552 re_free (fs->stack);
1559 update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
1560 regmatch_t *prev_idx_match, Idx cur_node, Idx cur_idx, Idx nmatch)
1562 int type = dfa->nodes[cur_node].type;
1563 if (type == OP_OPEN_SUBEXP)
1565 Idx reg_num = dfa->nodes[cur_node].opr.idx + 1;
1567 /* We are at the first node of this sub expression. */
1568 if (reg_num < nmatch)
1570 pmatch[reg_num].rm_so = cur_idx;
1571 pmatch[reg_num].rm_eo = -1;
1574 else if (type == OP_CLOSE_SUBEXP)
1576 Idx reg_num = dfa->nodes[cur_node].opr.idx + 1;
1577 if (reg_num < nmatch)
1579 /* We are at the last node of this sub expression. */
1580 if (pmatch[reg_num].rm_so < cur_idx)
1582 pmatch[reg_num].rm_eo = cur_idx;
1583 /* This is a non-empty match or we are not inside an optional
1584 subexpression. Accept this right away. */
1585 memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
1589 if (dfa->nodes[cur_node].opt_subexp
1590 && prev_idx_match[reg_num].rm_so != -1)
1591 /* We transited through an empty match for an optional
1592 subexpression, like (a?)*, and this is not the subexp's
1593 first match. Copy back the old content of the registers
1594 so that matches of an inner subexpression are undone as
1595 well, like in ((a?))*. */
1596 memcpy (pmatch, prev_idx_match, sizeof (regmatch_t) * nmatch);
1598 /* We completed a subexpression, but it may be part of
1599 an optional one, so do not update PREV_IDX_MATCH. */
1600 pmatch[reg_num].rm_eo = cur_idx;
1606 /* This function checks the STATE_LOG from the SCTX->last_str_idx to 0
1607 and sift the nodes in each states according to the following rules.
1608 Updated state_log will be wrote to STATE_LOG.
1610 Rules: We throw away the Node `a' in the STATE_LOG[STR_IDX] if...
1611 1. When STR_IDX == MATCH_LAST(the last index in the state_log):
1612 If `a' isn't the LAST_NODE and `a' can't epsilon transit to
1613 the LAST_NODE, we throw away the node `a'.
1614 2. When 0 <= STR_IDX < MATCH_LAST and `a' accepts
1615 string `s' and transit to `b':
1616 i. If 'b' isn't in the STATE_LOG[STR_IDX+strlen('s')], we throw
1618 ii. If 'b' is in the STATE_LOG[STR_IDX+strlen('s')] but 'b' is
1619 thrown away, we throw away the node `a'.
1620 3. When 0 <= STR_IDX < MATCH_LAST and 'a' epsilon transit to 'b':
1621 i. If 'b' isn't in the STATE_LOG[STR_IDX], we throw away the
1623 ii. If 'b' is in the STATE_LOG[STR_IDX] but 'b' is thrown away,
1624 we throw away the node `a'. */
1626 #define STATE_NODE_CONTAINS(state,node) \
1627 ((state) != NULL && re_node_set_contains (&(state)->nodes, node))
1629 static reg_errcode_t
1631 sift_states_backward (const re_match_context_t *mctx, re_sift_context_t *sctx)
1635 Idx str_idx = sctx->last_str_idx;
1636 re_node_set cur_dest;
1639 assert (mctx->state_log != NULL && mctx->state_log[str_idx] != NULL);
1642 /* Build sifted state_log[str_idx]. It has the nodes which can epsilon
1643 transit to the last_node and the last_node itself. */
1644 err = re_node_set_init_1 (&cur_dest, sctx->last_node);
1645 if (BE (err != REG_NOERROR, 0))
1647 err = update_cur_sifted_state (mctx, sctx, str_idx, &cur_dest);
1648 if (BE (err != REG_NOERROR, 0))
1651 /* Then check each states in the state_log. */
1654 /* Update counters. */
1655 null_cnt = (sctx->sifted_states[str_idx] == NULL) ? null_cnt + 1 : 0;
1656 if (null_cnt > mctx->max_mb_elem_len)
1658 memset (sctx->sifted_states, '\0',
1659 sizeof (re_dfastate_t *) * str_idx);
1660 re_node_set_free (&cur_dest);
1663 re_node_set_empty (&cur_dest);
1666 if (mctx->state_log[str_idx])
1668 err = build_sifted_states (mctx, sctx, str_idx, &cur_dest);
1669 if (BE (err != REG_NOERROR, 0))
1673 /* Add all the nodes which satisfy the following conditions:
1674 - It can epsilon transit to a node in CUR_DEST.
1676 And update state_log. */
1677 err = update_cur_sifted_state (mctx, sctx, str_idx, &cur_dest);
1678 if (BE (err != REG_NOERROR, 0))
1683 re_node_set_free (&cur_dest);
1687 static reg_errcode_t
1688 internal_function __attribute_warn_unused_result__
1689 build_sifted_states (const re_match_context_t *mctx, re_sift_context_t *sctx,
1690 Idx str_idx, re_node_set *cur_dest)
1692 const re_dfa_t *const dfa = mctx->dfa;
1693 const re_node_set *cur_src = &mctx->state_log[str_idx]->non_eps_nodes;
1696 /* Then build the next sifted state.
1697 We build the next sifted state on `cur_dest', and update
1698 `sifted_states[str_idx]' with `cur_dest'.
1700 `cur_dest' is the sifted state from `state_log[str_idx + 1]'.
1701 `cur_src' points the node_set of the old `state_log[str_idx]'
1702 (with the epsilon nodes pre-filtered out). */
1703 for (i = 0; i < cur_src->nelem; i++)
1705 Idx prev_node = cur_src->elems[i];
1710 re_token_type_t type = dfa->nodes[prev_node].type;
1711 assert (!IS_EPSILON_NODE (type));
1713 #ifdef RE_ENABLE_I18N
1714 /* If the node may accept `multi byte'. */
1715 if (dfa->nodes[prev_node].accept_mb)
1716 naccepted = sift_states_iter_mb (mctx, sctx, prev_node,
1717 str_idx, sctx->last_str_idx);
1718 #endif /* RE_ENABLE_I18N */
1720 /* We don't check backreferences here.
1721 See update_cur_sifted_state(). */
1723 && check_node_accept (mctx, dfa->nodes + prev_node, str_idx)
1724 && STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + 1],
1725 dfa->nexts[prev_node]))
1731 if (sctx->limits.nelem)
1733 Idx to_idx = str_idx + naccepted;
1734 if (check_dst_limits (mctx, &sctx->limits,
1735 dfa->nexts[prev_node], to_idx,
1736 prev_node, str_idx))
1739 ok = re_node_set_insert (cur_dest, prev_node);
1747 /* Helper functions. */
1749 static reg_errcode_t
1751 clean_state_log_if_needed (re_match_context_t *mctx, Idx next_state_log_idx)
1753 Idx top = mctx->state_log_top;
1755 if (next_state_log_idx >= mctx->input.bufs_len
1756 || (next_state_log_idx >= mctx->input.valid_len
1757 && mctx->input.valid_len < mctx->input.len))
1760 err = extend_buffers (mctx);
1761 if (BE (err != REG_NOERROR, 0))
1765 if (top < next_state_log_idx)
1767 memset (mctx->state_log + top + 1, '\0',
1768 sizeof (re_dfastate_t *) * (next_state_log_idx - top));
1769 mctx->state_log_top = next_state_log_idx;
1774 static reg_errcode_t
1776 merge_state_array (const re_dfa_t *dfa, re_dfastate_t **dst,
1777 re_dfastate_t **src, Idx num)
1781 for (st_idx = 0; st_idx < num; ++st_idx)
1783 if (dst[st_idx] == NULL)
1784 dst[st_idx] = src[st_idx];
1785 else if (src[st_idx] != NULL)
1787 re_node_set merged_set;
1788 err = re_node_set_init_union (&merged_set, &dst[st_idx]->nodes,
1789 &src[st_idx]->nodes);
1790 if (BE (err != REG_NOERROR, 0))
1792 dst[st_idx] = re_acquire_state (&err, dfa, &merged_set);
1793 re_node_set_free (&merged_set);
1794 if (BE (err != REG_NOERROR, 0))
1801 static reg_errcode_t
1803 update_cur_sifted_state (const re_match_context_t *mctx,
1804 re_sift_context_t *sctx, Idx str_idx,
1805 re_node_set *dest_nodes)
1807 const re_dfa_t *const dfa = mctx->dfa;
1808 reg_errcode_t err = REG_NOERROR;
1809 const re_node_set *candidates;
1810 candidates = ((mctx->state_log[str_idx] == NULL) ? NULL
1811 : &mctx->state_log[str_idx]->nodes);
1813 if (dest_nodes->nelem == 0)
1814 sctx->sifted_states[str_idx] = NULL;
1819 /* At first, add the nodes which can epsilon transit to a node in
1821 err = add_epsilon_src_nodes (dfa, dest_nodes, candidates);
1822 if (BE (err != REG_NOERROR, 0))
1825 /* Then, check the limitations in the current sift_context. */
1826 if (sctx->limits.nelem)
1828 err = check_subexp_limits (dfa, dest_nodes, candidates, &sctx->limits,
1829 mctx->bkref_ents, str_idx);
1830 if (BE (err != REG_NOERROR, 0))
1835 sctx->sifted_states[str_idx] = re_acquire_state (&err, dfa, dest_nodes);
1836 if (BE (err != REG_NOERROR, 0))
1840 if (candidates && mctx->state_log[str_idx]->has_backref)
1842 err = sift_states_bkref (mctx, sctx, str_idx, candidates);
1843 if (BE (err != REG_NOERROR, 0))
1849 static reg_errcode_t
1850 internal_function __attribute_warn_unused_result__
1851 add_epsilon_src_nodes (const re_dfa_t *dfa, re_node_set *dest_nodes,
1852 const re_node_set *candidates)
1854 reg_errcode_t err = REG_NOERROR;
1857 re_dfastate_t *state = re_acquire_state (&err, dfa, dest_nodes);
1858 if (BE (err != REG_NOERROR, 0))
1861 if (!state->inveclosure.alloc)
1863 err = re_node_set_alloc (&state->inveclosure, dest_nodes->nelem);
1864 if (BE (err != REG_NOERROR, 0))
1866 for (i = 0; i < dest_nodes->nelem; i++)
1868 err = re_node_set_merge (&state->inveclosure,
1869 dfa->inveclosures + dest_nodes->elems[i]);
1870 if (BE (err != REG_NOERROR, 0))
1874 return re_node_set_add_intersect (dest_nodes, candidates,
1875 &state->inveclosure);
1878 static reg_errcode_t
1880 sub_epsilon_src_nodes (const re_dfa_t *dfa, Idx node, re_node_set *dest_nodes,
1881 const re_node_set *candidates)
1885 re_node_set *inv_eclosure = dfa->inveclosures + node;
1886 re_node_set except_nodes;
1887 re_node_set_init_empty (&except_nodes);
1888 for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx)
1890 Idx cur_node = inv_eclosure->elems[ecl_idx];
1891 if (cur_node == node)
1893 if (IS_EPSILON_NODE (dfa->nodes[cur_node].type))
1895 Idx edst1 = dfa->edests[cur_node].elems[0];
1896 Idx edst2 = ((dfa->edests[cur_node].nelem > 1)
1897 ? dfa->edests[cur_node].elems[1] : REG_MISSING);
1898 if ((!re_node_set_contains (inv_eclosure, edst1)
1899 && re_node_set_contains (dest_nodes, edst1))
1900 || (REG_VALID_NONZERO_INDEX (edst2)
1901 && !re_node_set_contains (inv_eclosure, edst2)
1902 && re_node_set_contains (dest_nodes, edst2)))
1904 err = re_node_set_add_intersect (&except_nodes, candidates,
1905 dfa->inveclosures + cur_node);
1906 if (BE (err != REG_NOERROR, 0))
1908 re_node_set_free (&except_nodes);
1914 for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx)
1916 Idx cur_node = inv_eclosure->elems[ecl_idx];
1917 if (!re_node_set_contains (&except_nodes, cur_node))
1919 Idx idx = re_node_set_contains (dest_nodes, cur_node) - 1;
1920 re_node_set_remove_at (dest_nodes, idx);
1923 re_node_set_free (&except_nodes);
1929 check_dst_limits (const re_match_context_t *mctx, const re_node_set *limits,
1930 Idx dst_node, Idx dst_idx, Idx src_node, Idx src_idx)
1932 const re_dfa_t *const dfa = mctx->dfa;
1933 Idx lim_idx, src_pos, dst_pos;
1935 Idx dst_bkref_idx = search_cur_bkref_entry (mctx, dst_idx);
1936 Idx src_bkref_idx = search_cur_bkref_entry (mctx, src_idx);
1937 for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx)
1940 struct re_backref_cache_entry *ent;
1941 ent = mctx->bkref_ents + limits->elems[lim_idx];
1942 subexp_idx = dfa->nodes[ent->node].opr.idx;
1944 dst_pos = check_dst_limits_calc_pos (mctx, limits->elems[lim_idx],
1945 subexp_idx, dst_node, dst_idx,
1947 src_pos = check_dst_limits_calc_pos (mctx, limits->elems[lim_idx],
1948 subexp_idx, src_node, src_idx,
1952 <src> <dst> ( <subexp> )
1953 ( <subexp> ) <src> <dst>
1954 ( <subexp1> <src> <subexp2> <dst> <subexp3> ) */
1955 if (src_pos == dst_pos)
1956 continue; /* This is unrelated limitation. */
1965 check_dst_limits_calc_pos_1 (const re_match_context_t *mctx, int boundaries,
1966 Idx subexp_idx, Idx from_node, Idx bkref_idx)
1968 const re_dfa_t *const dfa = mctx->dfa;
1969 const re_node_set *eclosures = dfa->eclosures + from_node;
1972 /* Else, we are on the boundary: examine the nodes on the epsilon
1974 for (node_idx = 0; node_idx < eclosures->nelem; ++node_idx)
1976 Idx node = eclosures->elems[node_idx];
1977 switch (dfa->nodes[node].type)
1980 if (bkref_idx != REG_MISSING)
1982 struct re_backref_cache_entry *ent = mctx->bkref_ents + bkref_idx;
1988 if (ent->node != node)
1991 if (subexp_idx < BITSET_WORD_BITS
1992 && !(ent->eps_reachable_subexps_map
1993 & ((bitset_word_t) 1 << subexp_idx)))
1996 /* Recurse trying to reach the OP_OPEN_SUBEXP and
1997 OP_CLOSE_SUBEXP cases below. But, if the
1998 destination node is the same node as the source
1999 node, don't recurse because it would cause an
2000 infinite loop: a regex that exhibits this behavior
2002 dst = dfa->edests[node].elems[0];
2003 if (dst == from_node)
2007 else /* if (boundaries & 2) */
2012 check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx,
2014 if (cpos == -1 /* && (boundaries & 1) */)
2016 if (cpos == 0 && (boundaries & 2))
2019 if (subexp_idx < BITSET_WORD_BITS)
2020 ent->eps_reachable_subexps_map
2021 &= ~((bitset_word_t) 1 << subexp_idx);
2023 while (ent++->more);
2027 case OP_OPEN_SUBEXP:
2028 if ((boundaries & 1) && subexp_idx == dfa->nodes[node].opr.idx)
2032 case OP_CLOSE_SUBEXP:
2033 if ((boundaries & 2) && subexp_idx == dfa->nodes[node].opr.idx)
2042 return (boundaries & 2) ? 1 : 0;
2047 check_dst_limits_calc_pos (const re_match_context_t *mctx, Idx limit,
2048 Idx subexp_idx, Idx from_node, Idx str_idx,
2051 struct re_backref_cache_entry *lim = mctx->bkref_ents + limit;
2054 /* If we are outside the range of the subexpression, return -1 or 1. */
2055 if (str_idx < lim->subexp_from)
2058 if (lim->subexp_to < str_idx)
2061 /* If we are within the subexpression, return 0. */
2062 boundaries = (str_idx == lim->subexp_from);
2063 boundaries |= (str_idx == lim->subexp_to) << 1;
2064 if (boundaries == 0)
2067 /* Else, examine epsilon closure. */
2068 return check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx,
2069 from_node, bkref_idx);
2072 /* Check the limitations of sub expressions LIMITS, and remove the nodes
2073 which are against limitations from DEST_NODES. */
2075 static reg_errcode_t
2077 check_subexp_limits (const re_dfa_t *dfa, re_node_set *dest_nodes,
2078 const re_node_set *candidates, re_node_set *limits,
2079 struct re_backref_cache_entry *bkref_ents, Idx str_idx)
2082 Idx node_idx, lim_idx;
2084 for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx)
2087 struct re_backref_cache_entry *ent;
2088 ent = bkref_ents + limits->elems[lim_idx];
2090 if (str_idx <= ent->subexp_from || ent->str_idx < str_idx)
2091 continue; /* This is unrelated limitation. */
2093 subexp_idx = dfa->nodes[ent->node].opr.idx;
2094 if (ent->subexp_to == str_idx)
2096 Idx ops_node = REG_MISSING;
2097 Idx cls_node = REG_MISSING;
2098 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2100 Idx node = dest_nodes->elems[node_idx];
2101 re_token_type_t type = dfa->nodes[node].type;
2102 if (type == OP_OPEN_SUBEXP
2103 && subexp_idx == dfa->nodes[node].opr.idx)
2105 else if (type == OP_CLOSE_SUBEXP
2106 && subexp_idx == dfa->nodes[node].opr.idx)
2110 /* Check the limitation of the open subexpression. */
2111 /* Note that (ent->subexp_to = str_idx != ent->subexp_from). */
2112 if (REG_VALID_INDEX (ops_node))
2114 err = sub_epsilon_src_nodes (dfa, ops_node, dest_nodes,
2116 if (BE (err != REG_NOERROR, 0))
2120 /* Check the limitation of the close subexpression. */
2121 if (REG_VALID_INDEX (cls_node))
2122 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2124 Idx node = dest_nodes->elems[node_idx];
2125 if (!re_node_set_contains (dfa->inveclosures + node,
2127 && !re_node_set_contains (dfa->eclosures + node,
2130 /* It is against this limitation.
2131 Remove it form the current sifted state. */
2132 err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2134 if (BE (err != REG_NOERROR, 0))
2140 else /* (ent->subexp_to != str_idx) */
2142 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2144 Idx node = dest_nodes->elems[node_idx];
2145 re_token_type_t type = dfa->nodes[node].type;
2146 if (type == OP_CLOSE_SUBEXP || type == OP_OPEN_SUBEXP)
2148 if (subexp_idx != dfa->nodes[node].opr.idx)
2150 /* It is against this limitation.
2151 Remove it form the current sifted state. */
2152 err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2154 if (BE (err != REG_NOERROR, 0))
2163 static reg_errcode_t
2164 internal_function __attribute_warn_unused_result__
2165 sift_states_bkref (const re_match_context_t *mctx, re_sift_context_t *sctx,
2166 Idx str_idx, const re_node_set *candidates)
2168 const re_dfa_t *const dfa = mctx->dfa;
2171 re_sift_context_t local_sctx;
2172 Idx first_idx = search_cur_bkref_entry (mctx, str_idx);
2174 if (first_idx == REG_MISSING)
2177 local_sctx.sifted_states = NULL; /* Mark that it hasn't been initialized. */
2179 for (node_idx = 0; node_idx < candidates->nelem; ++node_idx)
2182 re_token_type_t type;
2183 struct re_backref_cache_entry *entry;
2184 node = candidates->elems[node_idx];
2185 type = dfa->nodes[node].type;
2186 /* Avoid infinite loop for the REs like "()\1+". */
2187 if (node == sctx->last_node && str_idx == sctx->last_str_idx)
2189 if (type != OP_BACK_REF)
2192 entry = mctx->bkref_ents + first_idx;
2193 enabled_idx = first_idx;
2200 re_dfastate_t *cur_state;
2202 if (entry->node != node)
2204 subexp_len = entry->subexp_to - entry->subexp_from;
2205 to_idx = str_idx + subexp_len;
2206 dst_node = (subexp_len ? dfa->nexts[node]
2207 : dfa->edests[node].elems[0]);
2209 if (to_idx > sctx->last_str_idx
2210 || sctx->sifted_states[to_idx] == NULL
2211 || !STATE_NODE_CONTAINS (sctx->sifted_states[to_idx], dst_node)
2212 || check_dst_limits (mctx, &sctx->limits, node,
2213 str_idx, dst_node, to_idx))
2216 if (local_sctx.sifted_states == NULL)
2219 err = re_node_set_init_copy (&local_sctx.limits, &sctx->limits);
2220 if (BE (err != REG_NOERROR, 0))
2223 local_sctx.last_node = node;
2224 local_sctx.last_str_idx = str_idx;
2225 ok = re_node_set_insert (&local_sctx.limits, enabled_idx);
2231 cur_state = local_sctx.sifted_states[str_idx];
2232 err = sift_states_backward (mctx, &local_sctx);
2233 if (BE (err != REG_NOERROR, 0))
2235 if (sctx->limited_states != NULL)
2237 err = merge_state_array (dfa, sctx->limited_states,
2238 local_sctx.sifted_states,
2240 if (BE (err != REG_NOERROR, 0))
2243 local_sctx.sifted_states[str_idx] = cur_state;
2244 re_node_set_remove (&local_sctx.limits, enabled_idx);
2246 /* mctx->bkref_ents may have changed, reload the pointer. */
2247 entry = mctx->bkref_ents + enabled_idx;
2249 while (enabled_idx++, entry++->more);
2253 if (local_sctx.sifted_states != NULL)
2255 re_node_set_free (&local_sctx.limits);
2262 #ifdef RE_ENABLE_I18N
2265 sift_states_iter_mb (const re_match_context_t *mctx, re_sift_context_t *sctx,
2266 Idx node_idx, Idx str_idx, Idx max_str_idx)
2268 const re_dfa_t *const dfa = mctx->dfa;
2270 /* Check the node can accept `multi byte'. */
2271 naccepted = check_node_accept_bytes (dfa, node_idx, &mctx->input, str_idx);
2272 if (naccepted > 0 && str_idx + naccepted <= max_str_idx &&
2273 !STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + naccepted],
2274 dfa->nexts[node_idx]))
2275 /* The node can't accept the `multi byte', or the
2276 destination was already thrown away, then the node
2277 could't accept the current input `multi byte'. */
2279 /* Otherwise, it is sure that the node could accept
2280 `naccepted' bytes input. */
2283 #endif /* RE_ENABLE_I18N */
2286 /* Functions for state transition. */
2288 /* Return the next state to which the current state STATE will transit by
2289 accepting the current input byte, and update STATE_LOG if necessary.
2290 If STATE can accept a multibyte char/collating element/back reference
2291 update the destination of STATE_LOG. */
2293 static re_dfastate_t *
2294 internal_function __attribute_warn_unused_result__
2295 transit_state (reg_errcode_t *err, re_match_context_t *mctx,
2296 re_dfastate_t *state)
2298 re_dfastate_t **trtable;
2301 #ifdef RE_ENABLE_I18N
2302 /* If the current state can accept multibyte. */
2303 if (BE (state->accept_mb, 0))
2305 *err = transit_state_mb (mctx, state);
2306 if (BE (*err != REG_NOERROR, 0))
2309 #endif /* RE_ENABLE_I18N */
2311 /* Then decide the next state with the single byte. */
2314 /* don't use transition table */
2315 return transit_state_sb (err, mctx, state);
2318 /* Use transition table */
2319 ch = re_string_fetch_byte (&mctx->input);
2322 trtable = state->trtable;
2323 if (BE (trtable != NULL, 1))
2326 trtable = state->word_trtable;
2327 if (BE (trtable != NULL, 1))
2329 unsigned int context;
2331 = re_string_context_at (&mctx->input,
2332 re_string_cur_idx (&mctx->input) - 1,
2334 if (IS_WORD_CONTEXT (context))
2335 return trtable[ch + SBC_MAX];
2340 if (!build_trtable (mctx->dfa, state))
2346 /* Retry, we now have a transition table. */
2350 /* Update the state_log if we need */
2351 static re_dfastate_t *
2353 merge_state_with_log (reg_errcode_t *err, re_match_context_t *mctx,
2354 re_dfastate_t *next_state)
2356 const re_dfa_t *const dfa = mctx->dfa;
2357 Idx cur_idx = re_string_cur_idx (&mctx->input);
2359 if (cur_idx > mctx->state_log_top)
2361 mctx->state_log[cur_idx] = next_state;
2362 mctx->state_log_top = cur_idx;
2364 else if (mctx->state_log[cur_idx] == 0)
2366 mctx->state_log[cur_idx] = next_state;
2370 re_dfastate_t *pstate;
2371 unsigned int context;
2372 re_node_set next_nodes, *log_nodes, *table_nodes = NULL;
2373 /* If (state_log[cur_idx] != 0), it implies that cur_idx is
2374 the destination of a multibyte char/collating element/
2375 back reference. Then the next state is the union set of
2376 these destinations and the results of the transition table. */
2377 pstate = mctx->state_log[cur_idx];
2378 log_nodes = pstate->entrance_nodes;
2379 if (next_state != NULL)
2381 table_nodes = next_state->entrance_nodes;
2382 *err = re_node_set_init_union (&next_nodes, table_nodes,
2384 if (BE (*err != REG_NOERROR, 0))
2388 next_nodes = *log_nodes;
2389 /* Note: We already add the nodes of the initial state,
2390 then we don't need to add them here. */
2392 context = re_string_context_at (&mctx->input,
2393 re_string_cur_idx (&mctx->input) - 1,
2395 next_state = mctx->state_log[cur_idx]
2396 = re_acquire_state_context (err, dfa, &next_nodes, context);
2397 /* We don't need to check errors here, since the return value of
2398 this function is next_state and ERR is already set. */
2400 if (table_nodes != NULL)
2401 re_node_set_free (&next_nodes);
2404 if (BE (dfa->nbackref, 0) && next_state != NULL)
2406 /* Check OP_OPEN_SUBEXP in the current state in case that we use them
2407 later. We must check them here, since the back references in the
2408 next state might use them. */
2409 *err = check_subexp_matching_top (mctx, &next_state->nodes,
2411 if (BE (*err != REG_NOERROR, 0))
2414 /* If the next state has back references. */
2415 if (next_state->has_backref)
2417 *err = transit_state_bkref (mctx, &next_state->nodes);
2418 if (BE (*err != REG_NOERROR, 0))
2420 next_state = mctx->state_log[cur_idx];
2427 /* Skip bytes in the input that correspond to part of a
2428 multi-byte match, then look in the log for a state
2429 from which to restart matching. */
2430 static re_dfastate_t *
2432 find_recover_state (reg_errcode_t *err, re_match_context_t *mctx)
2434 re_dfastate_t *cur_state;
2437 Idx max = mctx->state_log_top;
2438 Idx cur_str_idx = re_string_cur_idx (&mctx->input);
2442 if (++cur_str_idx > max)
2444 re_string_skip_bytes (&mctx->input, 1);
2446 while (mctx->state_log[cur_str_idx] == NULL);
2448 cur_state = merge_state_with_log (err, mctx, NULL);
2450 while (*err == REG_NOERROR && cur_state == NULL);
2454 /* Helper functions for transit_state. */
2456 /* From the node set CUR_NODES, pick up the nodes whose types are
2457 OP_OPEN_SUBEXP and which have corresponding back references in the regular
2458 expression. And register them to use them later for evaluating the
2459 correspoding back references. */
2461 static reg_errcode_t
2463 check_subexp_matching_top (re_match_context_t *mctx, re_node_set *cur_nodes,
2466 const re_dfa_t *const dfa = mctx->dfa;
2470 /* TODO: This isn't efficient.
2471 Because there might be more than one nodes whose types are
2472 OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
2475 for (node_idx = 0; node_idx < cur_nodes->nelem; ++node_idx)
2477 Idx node = cur_nodes->elems[node_idx];
2478 if (dfa->nodes[node].type == OP_OPEN_SUBEXP
2479 && dfa->nodes[node].opr.idx < BITSET_WORD_BITS
2480 && (dfa->used_bkref_map
2481 & ((bitset_word_t) 1 << dfa->nodes[node].opr.idx)))
2483 err = match_ctx_add_subtop (mctx, node, str_idx);
2484 if (BE (err != REG_NOERROR, 0))
2492 /* Return the next state to which the current state STATE will transit by
2493 accepting the current input byte. */
2495 static re_dfastate_t *
2496 transit_state_sb (reg_errcode_t *err, re_match_context_t *mctx,
2497 re_dfastate_t *state)
2499 const re_dfa_t *const dfa = mctx->dfa;
2500 re_node_set next_nodes;
2501 re_dfastate_t *next_state;
2502 Idx node_cnt, cur_str_idx = re_string_cur_idx (&mctx->input);
2503 unsigned int context;
2505 *err = re_node_set_alloc (&next_nodes, state->nodes.nelem + 1);
2506 if (BE (*err != REG_NOERROR, 0))
2508 for (node_cnt = 0; node_cnt < state->nodes.nelem; ++node_cnt)
2510 Idx cur_node = state->nodes.elems[node_cnt];
2511 if (check_node_accept (mctx, dfa->nodes + cur_node, cur_str_idx))
2513 *err = re_node_set_merge (&next_nodes,
2514 dfa->eclosures + dfa->nexts[cur_node]);
2515 if (BE (*err != REG_NOERROR, 0))
2517 re_node_set_free (&next_nodes);
2522 context = re_string_context_at (&mctx->input, cur_str_idx, mctx->eflags);
2523 next_state = re_acquire_state_context (err, dfa, &next_nodes, context);
2524 /* We don't need to check errors here, since the return value of
2525 this function is next_state and ERR is already set. */
2527 re_node_set_free (&next_nodes);
2528 re_string_skip_bytes (&mctx->input, 1);
2533 #ifdef RE_ENABLE_I18N
2534 static reg_errcode_t
2536 transit_state_mb (re_match_context_t *mctx, re_dfastate_t *pstate)
2538 const re_dfa_t *const dfa = mctx->dfa;
2542 for (i = 0; i < pstate->nodes.nelem; ++i)
2544 re_node_set dest_nodes, *new_nodes;
2545 Idx cur_node_idx = pstate->nodes.elems[i];
2548 unsigned int context;
2549 re_dfastate_t *dest_state;
2551 if (!dfa->nodes[cur_node_idx].accept_mb)
2554 if (dfa->nodes[cur_node_idx].constraint)
2556 context = re_string_context_at (&mctx->input,
2557 re_string_cur_idx (&mctx->input),
2559 if (NOT_SATISFY_NEXT_CONSTRAINT (dfa->nodes[cur_node_idx].constraint,
2564 /* How many bytes the node can accept? */
2565 naccepted = check_node_accept_bytes (dfa, cur_node_idx, &mctx->input,
2566 re_string_cur_idx (&mctx->input));
2570 /* The node can accepts `naccepted' bytes. */
2571 dest_idx = re_string_cur_idx (&mctx->input) + naccepted;
2572 mctx->max_mb_elem_len = ((mctx->max_mb_elem_len < naccepted) ? naccepted
2573 : mctx->max_mb_elem_len);
2574 err = clean_state_log_if_needed (mctx, dest_idx);
2575 if (BE (err != REG_NOERROR, 0))
2578 assert (dfa->nexts[cur_node_idx] != REG_MISSING);
2580 new_nodes = dfa->eclosures + dfa->nexts[cur_node_idx];
2582 dest_state = mctx->state_log[dest_idx];
2583 if (dest_state == NULL)
2584 dest_nodes = *new_nodes;
2587 err = re_node_set_init_union (&dest_nodes,
2588 dest_state->entrance_nodes, new_nodes);
2589 if (BE (err != REG_NOERROR, 0))
2592 context = re_string_context_at (&mctx->input, dest_idx - 1,
2594 mctx->state_log[dest_idx]
2595 = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2596 if (dest_state != NULL)
2597 re_node_set_free (&dest_nodes);
2598 if (BE (mctx->state_log[dest_idx] == NULL && err != REG_NOERROR, 0))
2603 #endif /* RE_ENABLE_I18N */
2605 static reg_errcode_t
2607 transit_state_bkref (re_match_context_t *mctx, const re_node_set *nodes)
2609 const re_dfa_t *const dfa = mctx->dfa;
2612 Idx cur_str_idx = re_string_cur_idx (&mctx->input);
2614 for (i = 0; i < nodes->nelem; ++i)
2616 Idx dest_str_idx, prev_nelem, bkc_idx;
2617 Idx node_idx = nodes->elems[i];
2618 unsigned int context;
2619 const re_token_t *node = dfa->nodes + node_idx;
2620 re_node_set *new_dest_nodes;
2622 /* Check whether `node' is a backreference or not. */
2623 if (node->type != OP_BACK_REF)
2626 if (node->constraint)
2628 context = re_string_context_at (&mctx->input, cur_str_idx,
2630 if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
2634 /* `node' is a backreference.
2635 Check the substring which the substring matched. */
2636 bkc_idx = mctx->nbkref_ents;
2637 err = get_subexp (mctx, node_idx, cur_str_idx);
2638 if (BE (err != REG_NOERROR, 0))
2641 /* And add the epsilon closures (which is `new_dest_nodes') of
2642 the backreference to appropriate state_log. */
2644 assert (dfa->nexts[node_idx] != REG_MISSING);
2646 for (; bkc_idx < mctx->nbkref_ents; ++bkc_idx)
2649 re_dfastate_t *dest_state;
2650 struct re_backref_cache_entry *bkref_ent;
2651 bkref_ent = mctx->bkref_ents + bkc_idx;
2652 if (bkref_ent->node != node_idx || bkref_ent->str_idx != cur_str_idx)
2654 subexp_len = bkref_ent->subexp_to - bkref_ent->subexp_from;
2655 new_dest_nodes = (subexp_len == 0
2656 ? dfa->eclosures + dfa->edests[node_idx].elems[0]
2657 : dfa->eclosures + dfa->nexts[node_idx]);
2658 dest_str_idx = (cur_str_idx + bkref_ent->subexp_to
2659 - bkref_ent->subexp_from);
2660 context = re_string_context_at (&mctx->input, dest_str_idx - 1,
2662 dest_state = mctx->state_log[dest_str_idx];
2663 prev_nelem = ((mctx->state_log[cur_str_idx] == NULL) ? 0
2664 : mctx->state_log[cur_str_idx]->nodes.nelem);
2665 /* Add `new_dest_node' to state_log. */
2666 if (dest_state == NULL)
2668 mctx->state_log[dest_str_idx]
2669 = re_acquire_state_context (&err, dfa, new_dest_nodes,
2671 if (BE (mctx->state_log[dest_str_idx] == NULL
2672 && err != REG_NOERROR, 0))
2677 re_node_set dest_nodes;
2678 err = re_node_set_init_union (&dest_nodes,
2679 dest_state->entrance_nodes,
2681 if (BE (err != REG_NOERROR, 0))
2683 re_node_set_free (&dest_nodes);
2686 mctx->state_log[dest_str_idx]
2687 = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2688 re_node_set_free (&dest_nodes);
2689 if (BE (mctx->state_log[dest_str_idx] == NULL
2690 && err != REG_NOERROR, 0))
2693 /* We need to check recursively if the backreference can epsilon
2696 && mctx->state_log[cur_str_idx]->nodes.nelem > prev_nelem)
2698 err = check_subexp_matching_top (mctx, new_dest_nodes,
2700 if (BE (err != REG_NOERROR, 0))
2702 err = transit_state_bkref (mctx, new_dest_nodes);
2703 if (BE (err != REG_NOERROR, 0))
2713 /* Enumerate all the candidates which the backreference BKREF_NODE can match
2714 at BKREF_STR_IDX, and register them by match_ctx_add_entry().
2715 Note that we might collect inappropriate candidates here.
2716 However, the cost of checking them strictly here is too high, then we
2717 delay these checking for prune_impossible_nodes(). */
2719 static reg_errcode_t
2720 internal_function __attribute_warn_unused_result__
2721 get_subexp (re_match_context_t *mctx, Idx bkref_node, Idx bkref_str_idx)
2723 const re_dfa_t *const dfa = mctx->dfa;
2724 Idx subexp_num, sub_top_idx;
2725 const char *buf = (const char *) re_string_get_buffer (&mctx->input);
2726 /* Return if we have already checked BKREF_NODE at BKREF_STR_IDX. */
2727 Idx cache_idx = search_cur_bkref_entry (mctx, bkref_str_idx);
2728 if (cache_idx != REG_MISSING)
2730 const struct re_backref_cache_entry *entry
2731 = mctx->bkref_ents + cache_idx;
2733 if (entry->node == bkref_node)
2734 return REG_NOERROR; /* We already checked it. */
2735 while (entry++->more);
2738 subexp_num = dfa->nodes[bkref_node].opr.idx;
2740 /* For each sub expression */
2741 for (sub_top_idx = 0; sub_top_idx < mctx->nsub_tops; ++sub_top_idx)
2744 re_sub_match_top_t *sub_top = mctx->sub_tops[sub_top_idx];
2745 re_sub_match_last_t *sub_last;
2746 Idx sub_last_idx, sl_str, bkref_str_off;
2748 if (dfa->nodes[sub_top->node].opr.idx != subexp_num)
2749 continue; /* It isn't related. */
2751 sl_str = sub_top->str_idx;
2752 bkref_str_off = bkref_str_idx;
2753 /* At first, check the last node of sub expressions we already
2755 for (sub_last_idx = 0; sub_last_idx < sub_top->nlasts; ++sub_last_idx)
2757 regoff_t sl_str_diff;
2758 sub_last = sub_top->lasts[sub_last_idx];
2759 sl_str_diff = sub_last->str_idx - sl_str;
2760 /* The matched string by the sub expression match with the substring
2761 at the back reference? */
2762 if (sl_str_diff > 0)
2764 if (BE (bkref_str_off + sl_str_diff > mctx->input.valid_len, 0))
2766 /* Not enough chars for a successful match. */
2767 if (bkref_str_off + sl_str_diff > mctx->input.len)
2770 err = clean_state_log_if_needed (mctx,
2773 if (BE (err != REG_NOERROR, 0))
2775 buf = (const char *) re_string_get_buffer (&mctx->input);
2777 if (memcmp (buf + bkref_str_off, buf + sl_str, sl_str_diff) != 0)
2778 /* We don't need to search this sub expression any more. */
2781 bkref_str_off += sl_str_diff;
2782 sl_str += sl_str_diff;
2783 err = get_subexp_sub (mctx, sub_top, sub_last, bkref_node,
2786 /* Reload buf, since the preceding call might have reallocated
2788 buf = (const char *) re_string_get_buffer (&mctx->input);
2790 if (err == REG_NOMATCH)
2792 if (BE (err != REG_NOERROR, 0))
2796 if (sub_last_idx < sub_top->nlasts)
2798 if (sub_last_idx > 0)
2800 /* Then, search for the other last nodes of the sub expression. */
2801 for (; sl_str <= bkref_str_idx; ++sl_str)
2804 regoff_t sl_str_off;
2805 const re_node_set *nodes;
2806 sl_str_off = sl_str - sub_top->str_idx;
2807 /* The matched string by the sub expression match with the substring
2808 at the back reference? */
2811 if (BE (bkref_str_off >= mctx->input.valid_len, 0))
2813 /* If we are at the end of the input, we cannot match. */
2814 if (bkref_str_off >= mctx->input.len)
2817 err = extend_buffers (mctx);
2818 if (BE (err != REG_NOERROR, 0))
2821 buf = (const char *) re_string_get_buffer (&mctx->input);
2823 if (buf [bkref_str_off++] != buf[sl_str - 1])
2824 break; /* We don't need to search this sub expression
2827 if (mctx->state_log[sl_str] == NULL)
2829 /* Does this state have a ')' of the sub expression? */
2830 nodes = &mctx->state_log[sl_str]->nodes;
2831 cls_node = find_subexp_node (dfa, nodes, subexp_num,
2833 if (cls_node == REG_MISSING)
2835 if (sub_top->path == NULL)
2837 sub_top->path = calloc (sizeof (state_array_t),
2838 sl_str - sub_top->str_idx + 1);
2839 if (sub_top->path == NULL)
2842 /* Can the OP_OPEN_SUBEXP node arrive the OP_CLOSE_SUBEXP node
2843 in the current context? */
2844 err = check_arrival (mctx, sub_top->path, sub_top->node,
2845 sub_top->str_idx, cls_node, sl_str,
2847 if (err == REG_NOMATCH)
2849 if (BE (err != REG_NOERROR, 0))
2851 sub_last = match_ctx_add_sublast (sub_top, cls_node, sl_str);
2852 if (BE (sub_last == NULL, 0))
2854 err = get_subexp_sub (mctx, sub_top, sub_last, bkref_node,
2856 if (err == REG_NOMATCH)
2863 /* Helper functions for get_subexp(). */
2865 /* Check SUB_LAST can arrive to the back reference BKREF_NODE at BKREF_STR.
2866 If it can arrive, register the sub expression expressed with SUB_TOP
2869 static reg_errcode_t
2871 get_subexp_sub (re_match_context_t *mctx, const re_sub_match_top_t *sub_top,
2872 re_sub_match_last_t *sub_last, Idx bkref_node, Idx bkref_str)
2876 /* Can the subexpression arrive the back reference? */
2877 err = check_arrival (mctx, &sub_last->path, sub_last->node,
2878 sub_last->str_idx, bkref_node, bkref_str,
2880 if (err != REG_NOERROR)
2882 err = match_ctx_add_entry (mctx, bkref_node, bkref_str, sub_top->str_idx,
2884 if (BE (err != REG_NOERROR, 0))
2886 to_idx = bkref_str + sub_last->str_idx - sub_top->str_idx;
2887 return clean_state_log_if_needed (mctx, to_idx);
2890 /* Find the first node which is '(' or ')' and whose index is SUBEXP_IDX.
2891 Search '(' if FL_OPEN, or search ')' otherwise.
2892 TODO: This function isn't efficient...
2893 Because there might be more than one nodes whose types are
2894 OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
2900 find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
2901 Idx subexp_idx, int type)
2904 for (cls_idx = 0; cls_idx < nodes->nelem; ++cls_idx)
2906 Idx cls_node = nodes->elems[cls_idx];
2907 const re_token_t *node = dfa->nodes + cls_node;
2908 if (node->type == type
2909 && node->opr.idx == subexp_idx)
2915 /* Check whether the node TOP_NODE at TOP_STR can arrive to the node
2916 LAST_NODE at LAST_STR. We record the path onto PATH since it will be
2918 Return REG_NOERROR if it can arrive, or REG_NOMATCH otherwise. */
2920 static reg_errcode_t
2921 internal_function __attribute_warn_unused_result__
2922 check_arrival (re_match_context_t *mctx, state_array_t *path, Idx top_node,
2923 Idx top_str, Idx last_node, Idx last_str, int type)
2925 const re_dfa_t *const dfa = mctx->dfa;
2926 reg_errcode_t err = REG_NOERROR;
2927 Idx subexp_num, backup_cur_idx, str_idx, null_cnt;
2928 re_dfastate_t *cur_state = NULL;
2929 re_node_set *cur_nodes, next_nodes;
2930 re_dfastate_t **backup_state_log;
2931 unsigned int context;
2933 subexp_num = dfa->nodes[top_node].opr.idx;
2934 /* Extend the buffer if we need. */
2935 if (BE (path->alloc < last_str + mctx->max_mb_elem_len + 1, 0))
2937 re_dfastate_t **new_array;
2938 Idx old_alloc = path->alloc;
2939 Idx new_alloc = old_alloc + last_str + mctx->max_mb_elem_len + 1;
2940 if (BE (new_alloc < old_alloc, 0)
2941 || BE (SIZE_MAX / sizeof (re_dfastate_t *) < new_alloc, 0))
2943 new_array = re_realloc (path->array, re_dfastate_t *, new_alloc);
2944 if (BE (new_array == NULL, 0))
2946 path->array = new_array;
2947 path->alloc = new_alloc;
2948 memset (new_array + old_alloc, '\0',
2949 sizeof (re_dfastate_t *) * (path->alloc - old_alloc));
2952 str_idx = path->next_idx ? path->next_idx : top_str;
2954 /* Temporary modify MCTX. */
2955 backup_state_log = mctx->state_log;
2956 backup_cur_idx = mctx->input.cur_idx;
2957 mctx->state_log = path->array;
2958 mctx->input.cur_idx = str_idx;
2960 /* Setup initial node set. */
2961 context = re_string_context_at (&mctx->input, str_idx - 1, mctx->eflags);
2962 if (str_idx == top_str)
2964 err = re_node_set_init_1 (&next_nodes, top_node);
2965 if (BE (err != REG_NOERROR, 0))
2967 err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
2968 if (BE (err != REG_NOERROR, 0))
2970 re_node_set_free (&next_nodes);
2976 cur_state = mctx->state_log[str_idx];
2977 if (cur_state && cur_state->has_backref)
2979 err = re_node_set_init_copy (&next_nodes, &cur_state->nodes);
2980 if (BE (err != REG_NOERROR, 0))
2984 re_node_set_init_empty (&next_nodes);
2986 if (str_idx == top_str || (cur_state && cur_state->has_backref))
2988 if (next_nodes.nelem)
2990 err = expand_bkref_cache (mctx, &next_nodes, str_idx,
2992 if (BE (err != REG_NOERROR, 0))
2994 re_node_set_free (&next_nodes);
2998 cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
2999 if (BE (cur_state == NULL && err != REG_NOERROR, 0))
3001 re_node_set_free (&next_nodes);
3004 mctx->state_log[str_idx] = cur_state;
3007 for (null_cnt = 0; str_idx < last_str && null_cnt <= mctx->max_mb_elem_len;)
3009 re_node_set_empty (&next_nodes);
3010 if (mctx->state_log[str_idx + 1])
3012 err = re_node_set_merge (&next_nodes,
3013 &mctx->state_log[str_idx + 1]->nodes);
3014 if (BE (err != REG_NOERROR, 0))
3016 re_node_set_free (&next_nodes);
3022 err = check_arrival_add_next_nodes (mctx, str_idx,
3023 &cur_state->non_eps_nodes,
3025 if (BE (err != REG_NOERROR, 0))
3027 re_node_set_free (&next_nodes);
3032 if (next_nodes.nelem)
3034 err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
3035 if (BE (err != REG_NOERROR, 0))
3037 re_node_set_free (&next_nodes);
3040 err = expand_bkref_cache (mctx, &next_nodes, str_idx,
3042 if (BE (err != REG_NOERROR, 0))
3044 re_node_set_free (&next_nodes);
3048 context = re_string_context_at (&mctx->input, str_idx - 1, mctx->eflags);
3049 cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
3050 if (BE (cur_state == NULL && err != REG_NOERROR, 0))
3052 re_node_set_free (&next_nodes);
3055 mctx->state_log[str_idx] = cur_state;
3056 null_cnt = cur_state == NULL ? null_cnt + 1 : 0;
3058 re_node_set_free (&next_nodes);
3059 cur_nodes = (mctx->state_log[last_str] == NULL ? NULL
3060 : &mctx->state_log[last_str]->nodes);
3061 path->next_idx = str_idx;
3064 mctx->state_log = backup_state_log;
3065 mctx->input.cur_idx = backup_cur_idx;
3067 /* Then check the current node set has the node LAST_NODE. */
3068 if (cur_nodes != NULL && re_node_set_contains (cur_nodes, last_node))
3074 /* Helper functions for check_arrival. */
3076 /* Calculate the destination nodes of CUR_NODES at STR_IDX, and append them
3078 TODO: This function is similar to the functions transit_state*(),
3079 however this function has many additional works.
3080 Can't we unify them? */
3082 static reg_errcode_t
3083 internal_function __attribute_warn_unused_result__
3084 check_arrival_add_next_nodes (re_match_context_t *mctx, Idx str_idx,
3085 re_node_set *cur_nodes, re_node_set *next_nodes)
3087 const re_dfa_t *const dfa = mctx->dfa;
3090 #ifdef RE_ENABLE_I18N
3091 reg_errcode_t err = REG_NOERROR;
3093 re_node_set union_set;
3094 re_node_set_init_empty (&union_set);
3095 for (cur_idx = 0; cur_idx < cur_nodes->nelem; ++cur_idx)
3098 Idx cur_node = cur_nodes->elems[cur_idx];
3100 re_token_type_t type = dfa->nodes[cur_node].type;
3101 assert (!IS_EPSILON_NODE (type));
3103 #ifdef RE_ENABLE_I18N
3104 /* If the node may accept `multi byte'. */
3105 if (dfa->nodes[cur_node].accept_mb)
3107 naccepted = check_node_accept_bytes (dfa, cur_node, &mctx->input,
3111 re_dfastate_t *dest_state;
3112 Idx next_node = dfa->nexts[cur_node];
3113 Idx next_idx = str_idx + naccepted;
3114 dest_state = mctx->state_log[next_idx];
3115 re_node_set_empty (&union_set);
3118 err = re_node_set_merge (&union_set, &dest_state->nodes);
3119 if (BE (err != REG_NOERROR, 0))
3121 re_node_set_free (&union_set);
3125 ok = re_node_set_insert (&union_set, next_node);
3128 re_node_set_free (&union_set);
3131 mctx->state_log[next_idx] = re_acquire_state (&err, dfa,
3133 if (BE (mctx->state_log[next_idx] == NULL
3134 && err != REG_NOERROR, 0))
3136 re_node_set_free (&union_set);
3141 #endif /* RE_ENABLE_I18N */
3143 || check_node_accept (mctx, dfa->nodes + cur_node, str_idx))
3145 ok = re_node_set_insert (next_nodes, dfa->nexts[cur_node]);
3148 re_node_set_free (&union_set);
3153 re_node_set_free (&union_set);
3157 /* For all the nodes in CUR_NODES, add the epsilon closures of them to
3158 CUR_NODES, however exclude the nodes which are:
3159 - inside the sub expression whose number is EX_SUBEXP, if FL_OPEN.
3160 - out of the sub expression whose number is EX_SUBEXP, if !FL_OPEN.
3163 static reg_errcode_t
3165 check_arrival_expand_ecl (const re_dfa_t *dfa, re_node_set *cur_nodes,
3166 Idx ex_subexp, int type)
3169 Idx idx, outside_node;
3170 re_node_set new_nodes;
3172 assert (cur_nodes->nelem);
3174 err = re_node_set_alloc (&new_nodes, cur_nodes->nelem);
3175 if (BE (err != REG_NOERROR, 0))
3177 /* Create a new node set NEW_NODES with the nodes which are epsilon
3178 closures of the node in CUR_NODES. */
3180 for (idx = 0; idx < cur_nodes->nelem; ++idx)
3182 Idx cur_node = cur_nodes->elems[idx];
3183 const re_node_set *eclosure = dfa->eclosures + cur_node;
3184 outside_node = find_subexp_node (dfa, eclosure, ex_subexp, type);
3185 if (outside_node == REG_MISSING)
3187 /* There are no problematic nodes, just merge them. */
3188 err = re_node_set_merge (&new_nodes, eclosure);
3189 if (BE (err != REG_NOERROR, 0))
3191 re_node_set_free (&new_nodes);
3197 /* There are problematic nodes, re-calculate incrementally. */
3198 err = check_arrival_expand_ecl_sub (dfa, &new_nodes, cur_node,
3200 if (BE (err != REG_NOERROR, 0))
3202 re_node_set_free (&new_nodes);
3207 re_node_set_free (cur_nodes);
3208 *cur_nodes = new_nodes;
3212 /* Helper function for check_arrival_expand_ecl.
3213 Check incrementally the epsilon closure of TARGET, and if it isn't
3214 problematic append it to DST_NODES. */
3216 static reg_errcode_t
3217 internal_function __attribute_warn_unused_result__
3218 check_arrival_expand_ecl_sub (const re_dfa_t *dfa, re_node_set *dst_nodes,
3219 Idx target, Idx ex_subexp, int type)
3222 for (cur_node = target; !re_node_set_contains (dst_nodes, cur_node);)
3226 if (dfa->nodes[cur_node].type == type
3227 && dfa->nodes[cur_node].opr.idx == ex_subexp)
3229 if (type == OP_CLOSE_SUBEXP)
3231 ok = re_node_set_insert (dst_nodes, cur_node);
3237 ok = re_node_set_insert (dst_nodes, cur_node);
3240 if (dfa->edests[cur_node].nelem == 0)
3242 if (dfa->edests[cur_node].nelem == 2)
3245 err = check_arrival_expand_ecl_sub (dfa, dst_nodes,
3246 dfa->edests[cur_node].elems[1],
3248 if (BE (err != REG_NOERROR, 0))
3251 cur_node = dfa->edests[cur_node].elems[0];
3257 /* For all the back references in the current state, calculate the
3258 destination of the back references by the appropriate entry
3259 in MCTX->BKREF_ENTS. */
3261 static reg_errcode_t
3262 internal_function __attribute_warn_unused_result__
3263 expand_bkref_cache (re_match_context_t *mctx, re_node_set *cur_nodes,
3264 Idx cur_str, Idx subexp_num, int type)
3266 const re_dfa_t *const dfa = mctx->dfa;
3268 Idx cache_idx_start = search_cur_bkref_entry (mctx, cur_str);
3269 struct re_backref_cache_entry *ent;
3271 if (cache_idx_start == REG_MISSING)
3275 ent = mctx->bkref_ents + cache_idx_start;
3278 Idx to_idx, next_node;
3280 /* Is this entry ENT is appropriate? */
3281 if (!re_node_set_contains (cur_nodes, ent->node))
3284 to_idx = cur_str + ent->subexp_to - ent->subexp_from;
3285 /* Calculate the destination of the back reference, and append it
3286 to MCTX->STATE_LOG. */
3287 if (to_idx == cur_str)
3289 /* The backreference did epsilon transit, we must re-check all the
3290 node in the current state. */
3291 re_node_set new_dests;
3292 reg_errcode_t err2, err3;
3293 next_node = dfa->edests[ent->node].elems[0];
3294 if (re_node_set_contains (cur_nodes, next_node))
3296 err = re_node_set_init_1 (&new_dests, next_node);
3297 err2 = check_arrival_expand_ecl (dfa, &new_dests, subexp_num, type);
3298 err3 = re_node_set_merge (cur_nodes, &new_dests);
3299 re_node_set_free (&new_dests);
3300 if (BE (err != REG_NOERROR || err2 != REG_NOERROR
3301 || err3 != REG_NOERROR, 0))
3303 err = (err != REG_NOERROR ? err
3304 : (err2 != REG_NOERROR ? err2 : err3));
3307 /* TODO: It is still inefficient... */
3312 re_node_set union_set;
3313 next_node = dfa->nexts[ent->node];
3314 if (mctx->state_log[to_idx])
3317 if (re_node_set_contains (&mctx->state_log[to_idx]->nodes,
3320 err = re_node_set_init_copy (&union_set,
3321 &mctx->state_log[to_idx]->nodes);
3322 ok = re_node_set_insert (&union_set, next_node);
3323 if (BE (err != REG_NOERROR || ! ok, 0))
3325 re_node_set_free (&union_set);
3326 err = err != REG_NOERROR ? err : REG_ESPACE;
3332 err = re_node_set_init_1 (&union_set, next_node);
3333 if (BE (err != REG_NOERROR, 0))
3336 mctx->state_log[to_idx] = re_acquire_state (&err, dfa, &union_set);
3337 re_node_set_free (&union_set);
3338 if (BE (mctx->state_log[to_idx] == NULL
3339 && err != REG_NOERROR, 0))
3343 while (ent++->more);
3347 /* Build transition table for the state.
3348 Return true if successful. */
3352 build_trtable (const re_dfa_t *dfa, re_dfastate_t *state)
3357 bool need_word_trtable = false;
3358 bitset_word_t elem, mask;
3359 bool dests_node_malloced = false;
3360 bool dest_states_malloced = false;
3361 Idx ndests; /* Number of the destination states from `state'. */
3362 re_dfastate_t **trtable;
3363 re_dfastate_t **dest_states = NULL, **dest_states_word, **dest_states_nl;
3364 re_node_set follows, *dests_node;
3366 bitset_t acceptable;
3370 re_node_set dests_node[SBC_MAX];
3371 bitset_t dests_ch[SBC_MAX];
3374 /* We build DFA states which corresponds to the destination nodes
3375 from `state'. `dests_node[i]' represents the nodes which i-th
3376 destination state contains, and `dests_ch[i]' represents the
3377 characters which i-th destination state accepts. */
3378 if (__libc_use_alloca (sizeof (struct dests_alloc)))
3379 dests_alloc = (struct dests_alloc *) alloca (sizeof (struct dests_alloc));
3382 dests_alloc = re_malloc (struct dests_alloc, 1);
3383 if (BE (dests_alloc == NULL, 0))
3385 dests_node_malloced = true;
3387 dests_node = dests_alloc->dests_node;
3388 dests_ch = dests_alloc->dests_ch;
3390 /* Initialize transiton table. */
3391 state->word_trtable = state->trtable = NULL;
3393 /* At first, group all nodes belonging to `state' into several
3395 ndests = group_nodes_into_DFAstates (dfa, state, dests_node, dests_ch);
3396 if (BE (! REG_VALID_NONZERO_INDEX (ndests), 0))
3398 if (dests_node_malloced)
3402 state->trtable = (re_dfastate_t **)
3403 calloc (sizeof (re_dfastate_t *), SBC_MAX);
3404 if (BE (state->trtable == NULL, 0))
3411 err = re_node_set_alloc (&follows, ndests + 1);
3412 if (BE (err != REG_NOERROR, 0))
3415 /* Avoid arithmetic overflow in size calculation. */
3416 if (BE ((((SIZE_MAX - (sizeof (re_node_set) + sizeof (bitset_t)) * SBC_MAX)
3417 / (3 * sizeof (re_dfastate_t *)))
3422 if (__libc_use_alloca ((sizeof (re_node_set) + sizeof (bitset_t)) * SBC_MAX
3423 + ndests * 3 * sizeof (re_dfastate_t *)))
3424 dest_states = (re_dfastate_t **)
3425 alloca (ndests * 3 * sizeof (re_dfastate_t *));
3428 dest_states = (re_dfastate_t **)
3429 malloc (ndests * 3 * sizeof (re_dfastate_t *));
3430 if (BE (dest_states == NULL, 0))
3433 if (dest_states_malloced)
3435 re_node_set_free (&follows);
3436 for (i = 0; i < ndests; ++i)
3437 re_node_set_free (dests_node + i);
3438 if (dests_node_malloced)
3442 dest_states_malloced = true;
3444 dest_states_word = dest_states + ndests;
3445 dest_states_nl = dest_states_word + ndests;
3446 bitset_empty (acceptable);
3448 /* Then build the states for all destinations. */
3449 for (i = 0; i < ndests; ++i)
3452 re_node_set_empty (&follows);
3453 /* Merge the follows of this destination states. */
3454 for (j = 0; j < dests_node[i].nelem; ++j)
3456 next_node = dfa->nexts[dests_node[i].elems[j]];
3457 if (next_node != REG_MISSING)
3459 err = re_node_set_merge (&follows, dfa->eclosures + next_node);
3460 if (BE (err != REG_NOERROR, 0))
3464 dest_states[i] = re_acquire_state_context (&err, dfa, &follows, 0);
3465 if (BE (dest_states[i] == NULL && err != REG_NOERROR, 0))
3467 /* If the new state has context constraint,
3468 build appropriate states for these contexts. */
3469 if (dest_states[i]->has_constraint)
3471 dest_states_word[i] = re_acquire_state_context (&err, dfa, &follows,
3473 if (BE (dest_states_word[i] == NULL && err != REG_NOERROR, 0))
3476 if (dest_states[i] != dest_states_word[i] && dfa->mb_cur_max > 1)
3477 need_word_trtable = true;
3479 dest_states_nl[i] = re_acquire_state_context (&err, dfa, &follows,
3481 if (BE (dest_states_nl[i] == NULL && err != REG_NOERROR, 0))
3486 dest_states_word[i] = dest_states[i];
3487 dest_states_nl[i] = dest_states[i];
3489 bitset_merge (acceptable, dests_ch[i]);
3492 if (!BE (need_word_trtable, 0))
3494 /* We don't care about whether the following character is a word
3495 character, or we are in a single-byte character set so we can
3496 discern by looking at the character code: allocate a
3497 256-entry transition table. */
3498 trtable = state->trtable =
3499 (re_dfastate_t **) calloc (sizeof (re_dfastate_t *), SBC_MAX);
3500 if (BE (trtable == NULL, 0))
3503 /* For all characters ch...: */
3504 for (i = 0; i < BITSET_WORDS; ++i)
3505 for (ch = i * BITSET_WORD_BITS, elem = acceptable[i], mask = 1;
3507 mask <<= 1, elem >>= 1, ++ch)
3508 if (BE (elem & 1, 0))
3510 /* There must be exactly one destination which accepts
3511 character ch. See group_nodes_into_DFAstates. */
3512 for (j = 0; (dests_ch[j][i] & mask) == 0; ++j)
3515 /* j-th destination accepts the word character ch. */
3516 if (dfa->word_char[i] & mask)
3517 trtable[ch] = dest_states_word[j];
3519 trtable[ch] = dest_states[j];
3524 /* We care about whether the following character is a word
3525 character, and we are in a multi-byte character set: discern
3526 by looking at the character code: build two 256-entry
3527 transition tables, one starting at trtable[0] and one
3528 starting at trtable[SBC_MAX]. */
3529 trtable = state->word_trtable =
3530 (re_dfastate_t **) calloc (sizeof (re_dfastate_t *), 2 * SBC_MAX);
3531 if (BE (trtable == NULL, 0))
3534 /* For all characters ch...: */
3535 for (i = 0; i < BITSET_WORDS; ++i)
3536 for (ch = i * BITSET_WORD_BITS, elem = acceptable[i], mask = 1;
3538 mask <<= 1, elem >>= 1, ++ch)
3539 if (BE (elem & 1, 0))
3541 /* There must be exactly one destination which accepts
3542 character ch. See group_nodes_into_DFAstates. */
3543 for (j = 0; (dests_ch[j][i] & mask) == 0; ++j)
3546 /* j-th destination accepts the word character ch. */
3547 trtable[ch] = dest_states[j];
3548 trtable[ch + SBC_MAX] = dest_states_word[j];
3553 if (bitset_contain (acceptable, NEWLINE_CHAR))
3555 /* The current state accepts newline character. */
3556 for (j = 0; j < ndests; ++j)
3557 if (bitset_contain (dests_ch[j], NEWLINE_CHAR))
3559 /* k-th destination accepts newline character. */
3560 trtable[NEWLINE_CHAR] = dest_states_nl[j];
3561 if (need_word_trtable)
3562 trtable[NEWLINE_CHAR + SBC_MAX] = dest_states_nl[j];
3563 /* There must be only one destination which accepts
3564 newline. See group_nodes_into_DFAstates. */
3569 if (dest_states_malloced)
3572 re_node_set_free (&follows);
3573 for (i = 0; i < ndests; ++i)
3574 re_node_set_free (dests_node + i);
3576 if (dests_node_malloced)
3582 /* Group all nodes belonging to STATE into several destinations.
3583 Then for all destinations, set the nodes belonging to the destination
3584 to DESTS_NODE[i] and set the characters accepted by the destination
3585 to DEST_CH[i]. This function return the number of destinations. */
3589 group_nodes_into_DFAstates (const re_dfa_t *dfa, const re_dfastate_t *state,
3590 re_node_set *dests_node, bitset_t *dests_ch)
3595 Idx ndests; /* Number of the destinations from `state'. */
3596 bitset_t accepts; /* Characters a node can accept. */
3597 const re_node_set *cur_nodes = &state->nodes;
3598 bitset_empty (accepts);
3601 /* For all the nodes belonging to `state', */
3602 for (i = 0; i < cur_nodes->nelem; ++i)
3604 re_token_t *node = &dfa->nodes[cur_nodes->elems[i]];
3605 re_token_type_t type = node->type;
3606 unsigned int constraint = node->constraint;
3608 /* Enumerate all single byte character this node can accept. */
3609 if (type == CHARACTER)
3610 bitset_set (accepts, node->opr.c);
3611 else if (type == SIMPLE_BRACKET)
3613 bitset_merge (accepts, node->opr.sbcset);
3615 else if (type == OP_PERIOD)
3617 #ifdef RE_ENABLE_I18N
3618 if (dfa->mb_cur_max > 1)
3619 bitset_merge (accepts, dfa->sb_char);
3622 bitset_set_all (accepts);
3623 if (!(dfa->syntax & RE_DOT_NEWLINE))
3624 bitset_clear (accepts, '\n');
3625 if (dfa->syntax & RE_DOT_NOT_NULL)
3626 bitset_clear (accepts, '\0');
3628 #ifdef RE_ENABLE_I18N
3629 else if (type == OP_UTF8_PERIOD)
3631 if (ASCII_CHARS % BITSET_WORD_BITS == 0)
3632 memset (accepts, -1, ASCII_CHARS / CHAR_BIT);
3634 bitset_merge (accepts, utf8_sb_map);
3635 if (!(dfa->syntax & RE_DOT_NEWLINE))
3636 bitset_clear (accepts, '\n');
3637 if (dfa->syntax & RE_DOT_NOT_NULL)
3638 bitset_clear (accepts, '\0');
3644 /* Check the `accepts' and sift the characters which are not
3645 match it the context. */
3648 if (constraint & NEXT_NEWLINE_CONSTRAINT)
3650 bool accepts_newline = bitset_contain (accepts, NEWLINE_CHAR);
3651 bitset_empty (accepts);
3652 if (accepts_newline)
3653 bitset_set (accepts, NEWLINE_CHAR);
3657 if (constraint & NEXT_ENDBUF_CONSTRAINT)
3659 bitset_empty (accepts);
3663 if (constraint & NEXT_WORD_CONSTRAINT)
3665 bitset_word_t any_set = 0;
3666 if (type == CHARACTER && !node->word_char)
3668 bitset_empty (accepts);
3671 #ifdef RE_ENABLE_I18N
3672 if (dfa->mb_cur_max > 1)
3673 for (j = 0; j < BITSET_WORDS; ++j)
3674 any_set |= (accepts[j] &= (dfa->word_char[j] | ~dfa->sb_char[j]));
3677 for (j = 0; j < BITSET_WORDS; ++j)
3678 any_set |= (accepts[j] &= dfa->word_char[j]);
3682 if (constraint & NEXT_NOTWORD_CONSTRAINT)
3684 bitset_word_t any_set = 0;
3685 if (type == CHARACTER && node->word_char)
3687 bitset_empty (accepts);
3690 #ifdef RE_ENABLE_I18N
3691 if (dfa->mb_cur_max > 1)
3692 for (j = 0; j < BITSET_WORDS; ++j)
3693 any_set |= (accepts[j] &= ~(dfa->word_char[j] & dfa->sb_char[j]));
3696 for (j = 0; j < BITSET_WORDS; ++j)
3697 any_set |= (accepts[j] &= ~dfa->word_char[j]);
3703 /* Then divide `accepts' into DFA states, or create a new
3704 state. Above, we make sure that accepts is not empty. */
3705 for (j = 0; j < ndests; ++j)
3707 bitset_t intersec; /* Intersection sets, see below. */
3709 /* Flags, see below. */
3710 bitset_word_t has_intersec, not_subset, not_consumed;
3712 /* Optimization, skip if this state doesn't accept the character. */
3713 if (type == CHARACTER && !bitset_contain (dests_ch[j], node->opr.c))
3716 /* Enumerate the intersection set of this state and `accepts'. */
3718 for (k = 0; k < BITSET_WORDS; ++k)
3719 has_intersec |= intersec[k] = accepts[k] & dests_ch[j][k];
3720 /* And skip if the intersection set is empty. */
3724 /* Then check if this state is a subset of `accepts'. */
3725 not_subset = not_consumed = 0;
3726 for (k = 0; k < BITSET_WORDS; ++k)
3728 not_subset |= remains[k] = ~accepts[k] & dests_ch[j][k];
3729 not_consumed |= accepts[k] = accepts[k] & ~dests_ch[j][k];
3732 /* If this state isn't a subset of `accepts', create a
3733 new group state, which has the `remains'. */
3736 bitset_copy (dests_ch[ndests], remains);
3737 bitset_copy (dests_ch[j], intersec);
3738 err = re_node_set_init_copy (dests_node + ndests, &dests_node[j]);
3739 if (BE (err != REG_NOERROR, 0))
3744 /* Put the position in the current group. */
3745 ok = re_node_set_insert (&dests_node[j], cur_nodes->elems[i]);
3749 /* If all characters are consumed, go to next node. */
3753 /* Some characters remain, create a new group. */
3756 bitset_copy (dests_ch[ndests], accepts);
3757 err = re_node_set_init_1 (dests_node + ndests, cur_nodes->elems[i]);
3758 if (BE (err != REG_NOERROR, 0))
3761 bitset_empty (accepts);
3766 for (j = 0; j < ndests; ++j)
3767 re_node_set_free (dests_node + j);
3771 #ifdef RE_ENABLE_I18N
3772 /* Check how many bytes the node `dfa->nodes[node_idx]' accepts.
3773 Return the number of the bytes the node accepts.
3774 STR_IDX is the current index of the input string.
3776 This function handles the nodes which can accept one character, or
3777 one collating element like '.', '[a-z]', opposite to the other nodes
3778 can only accept one byte. */
3782 check_node_accept_bytes (const re_dfa_t *dfa, Idx node_idx,
3783 const re_string_t *input, Idx str_idx)
3785 const re_token_t *node = dfa->nodes + node_idx;
3786 int char_len, elem_len;
3789 if (BE (node->type == OP_UTF8_PERIOD, 0))
3791 unsigned char c = re_string_byte_at (input, str_idx), d;
3792 if (BE (c < 0xc2, 1))
3795 if (str_idx + 2 > input->len)
3798 d = re_string_byte_at (input, str_idx + 1);
3800 return (d < 0x80 || d > 0xbf) ? 0 : 2;
3804 if (c == 0xe0 && d < 0xa0)
3810 if (c == 0xf0 && d < 0x90)
3816 if (c == 0xf8 && d < 0x88)
3822 if (c == 0xfc && d < 0x84)
3828 if (str_idx + char_len > input->len)
3831 for (i = 1; i < char_len; ++i)
3833 d = re_string_byte_at (input, str_idx + i);
3834 if (d < 0x80 || d > 0xbf)
3840 char_len = re_string_char_size_at (input, str_idx);
3841 if (node->type == OP_PERIOD)
3845 /* FIXME: I don't think this if is needed, as both '\n'
3846 and '\0' are char_len == 1. */
3847 /* '.' accepts any one character except the following two cases. */
3848 if ((!(dfa->syntax & RE_DOT_NEWLINE) &&
3849 re_string_byte_at (input, str_idx) == '\n') ||
3850 ((dfa->syntax & RE_DOT_NOT_NULL) &&
3851 re_string_byte_at (input, str_idx) == '\0'))
3856 elem_len = re_string_elem_size_at (input, str_idx);
3857 if ((elem_len <= 1 && char_len <= 1) || char_len == 0)
3860 if (node->type == COMPLEX_BRACKET)
3862 const re_charset_t *cset = node->opr.mbcset;
3864 const unsigned char *pin
3865 = ((const unsigned char *) re_string_get_buffer (input) + str_idx);
3870 wchar_t wc = ((cset->nranges || cset->nchar_classes || cset->nmbchars)
3871 ? re_string_wchar_at (input, str_idx) : 0);
3873 /* match with multibyte character? */
3874 for (i = 0; i < cset->nmbchars; ++i)
3875 if (wc == cset->mbchars[i])
3877 match_len = char_len;
3878 goto check_node_accept_bytes_match;
3880 /* match with character_class? */
3881 for (i = 0; i < cset->nchar_classes; ++i)
3883 wctype_t wt = cset->char_classes[i];
3884 if (__iswctype (wc, wt))
3886 match_len = char_len;
3887 goto check_node_accept_bytes_match;
3892 nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
3895 unsigned int in_collseq = 0;
3896 const int32_t *table, *indirect;
3897 const unsigned char *weights, *extra;
3898 const char *collseqwc;
3900 /* This #include defines a local function! */
3901 # include <locale/weight.h>
3903 /* match with collating_symbol? */
3904 if (cset->ncoll_syms)
3905 extra = (const unsigned char *)
3906 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB);
3907 for (i = 0; i < cset->ncoll_syms; ++i)
3909 const unsigned char *coll_sym = extra + cset->coll_syms[i];
3910 /* Compare the length of input collating element and
3911 the length of current collating element. */
3912 if (*coll_sym != elem_len)
3914 /* Compare each bytes. */
3915 for (j = 0; j < *coll_sym; j++)
3916 if (pin[j] != coll_sym[1 + j])
3920 /* Match if every bytes is equal. */
3922 goto check_node_accept_bytes_match;
3928 if (elem_len <= char_len)
3930 collseqwc = _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQWC);
3931 in_collseq = __collseq_table_lookup (collseqwc, wc);
3934 in_collseq = find_collation_sequence_value (pin, elem_len);
3936 /* match with range expression? */
3937 for (i = 0; i < cset->nranges; ++i)
3938 if (cset->range_starts[i] <= in_collseq
3939 && in_collseq <= cset->range_ends[i])
3941 match_len = elem_len;
3942 goto check_node_accept_bytes_match;
3945 /* match with equivalence_class? */
3946 if (cset->nequiv_classes)
3948 const unsigned char *cp = pin;
3949 table = (const int32_t *)
3950 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
3951 weights = (const unsigned char *)
3952 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_WEIGHTMB);
3953 extra = (const unsigned char *)
3954 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAMB);
3955 indirect = (const int32_t *)
3956 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_INDIRECTMB);
3957 int32_t idx = findidx (&cp);
3959 for (i = 0; i < cset->nequiv_classes; ++i)
3961 int32_t equiv_class_idx = cset->equiv_classes[i];
3962 size_t weight_len = weights[idx & 0xffffff];
3963 if (weight_len == weights[equiv_class_idx & 0xffffff]
3964 && (idx >> 24) == (equiv_class_idx >> 24))
3969 equiv_class_idx &= 0xffffff;
3971 while (cnt <= weight_len
3972 && (weights[equiv_class_idx + 1 + cnt]
3973 == weights[idx + 1 + cnt]))
3975 if (cnt > weight_len)
3977 match_len = elem_len;
3978 goto check_node_accept_bytes_match;
3987 /* match with range expression? */
3988 #if __GNUC__ >= 2 && ! (__STDC_VERSION__ < 199901L && __STRICT_ANSI__)
3989 wchar_t cmp_buf[] = {L'\0', L'\0', wc, L'\0', L'\0', L'\0'};
3991 wchar_t cmp_buf[] = {L'\0', L'\0', L'\0', L'\0', L'\0', L'\0'};
3994 for (i = 0; i < cset->nranges; ++i)
3996 cmp_buf[0] = cset->range_starts[i];
3997 cmp_buf[4] = cset->range_ends[i];
3998 if (wcscoll (cmp_buf, cmp_buf + 2) <= 0
3999 && wcscoll (cmp_buf + 2, cmp_buf + 4) <= 0)
4001 match_len = char_len;
4002 goto check_node_accept_bytes_match;
4006 check_node_accept_bytes_match:
4007 if (!cset->non_match)
4014 return (elem_len > char_len) ? elem_len : char_len;
4023 find_collation_sequence_value (const unsigned char *mbs, size_t mbs_len)
4025 uint32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
4030 /* No valid character. Match it as a single byte character. */
4031 const unsigned char *collseq = (const unsigned char *)
4032 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQMB);
4033 return collseq[mbs[0]];
4040 const unsigned char *extra = (const unsigned char *)
4041 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB);
4042 int32_t extrasize = (const unsigned char *)
4043 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB + 1) - extra;
4045 for (idx = 0; idx < extrasize;)
4049 int32_t elem_mbs_len;
4050 /* Skip the name of collating element name. */
4051 idx = idx + extra[idx] + 1;
4052 elem_mbs_len = extra[idx++];
4053 if (mbs_len == elem_mbs_len)
4055 for (mbs_cnt = 0; mbs_cnt < elem_mbs_len; ++mbs_cnt)
4056 if (extra[idx + mbs_cnt] != mbs[mbs_cnt])
4058 if (mbs_cnt == elem_mbs_len)
4059 /* Found the entry. */
4062 /* Skip the byte sequence of the collating element. */
4063 idx += elem_mbs_len;
4064 /* Adjust for the alignment. */
4065 idx = (idx + 3) & ~3;
4066 /* Skip the collation sequence value. */
4067 idx += sizeof (uint32_t);
4068 /* Skip the wide char sequence of the collating element. */
4069 idx = idx + sizeof (uint32_t) * (extra[idx] + 1);
4070 /* If we found the entry, return the sequence value. */
4072 return *(uint32_t *) (extra + idx);
4073 /* Skip the collation sequence value. */
4074 idx += sizeof (uint32_t);
4080 #endif /* RE_ENABLE_I18N */
4082 /* Check whether the node accepts the byte which is IDX-th
4083 byte of the INPUT. */
4087 check_node_accept (const re_match_context_t *mctx, const re_token_t *node,
4091 ch = re_string_byte_at (&mctx->input, idx);
4095 if (node->opr.c != ch)
4099 case SIMPLE_BRACKET:
4100 if (!bitset_contain (node->opr.sbcset, ch))
4104 #ifdef RE_ENABLE_I18N
4105 case OP_UTF8_PERIOD:
4106 if (ch >= ASCII_CHARS)
4111 if ((ch == '\n' && !(mctx->dfa->syntax & RE_DOT_NEWLINE))
4112 || (ch == '\0' && (mctx->dfa->syntax & RE_DOT_NOT_NULL)))
4120 if (node->constraint)
4122 /* The node has constraints. Check whether the current context
4123 satisfies the constraints. */
4124 unsigned int context = re_string_context_at (&mctx->input, idx,
4126 if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
4133 /* Extend the buffers, if the buffers have run out. */
4135 static reg_errcode_t
4136 internal_function __attribute_warn_unused_result__
4137 extend_buffers (re_match_context_t *mctx)
4140 re_string_t *pstr = &mctx->input;
4142 /* Avoid overflow. */
4143 if (BE (SIZE_MAX / 2 / sizeof (re_dfastate_t *) <= pstr->bufs_len, 0))
4146 /* Double the lengthes of the buffers. */
4147 ret = re_string_realloc_buffers (pstr, pstr->bufs_len * 2);
4148 if (BE (ret != REG_NOERROR, 0))
4151 if (mctx->state_log != NULL)
4153 /* And double the length of state_log. */
4154 /* XXX We have no indication of the size of this buffer. If this
4155 allocation fail we have no indication that the state_log array
4156 does not have the right size. */
4157 re_dfastate_t **new_array = re_realloc (mctx->state_log, re_dfastate_t *,
4158 pstr->bufs_len + 1);
4159 if (BE (new_array == NULL, 0))
4161 mctx->state_log = new_array;
4164 /* Then reconstruct the buffers. */
4167 #ifdef RE_ENABLE_I18N
4168 if (pstr->mb_cur_max > 1)
4170 ret = build_wcs_upper_buffer (pstr);
4171 if (BE (ret != REG_NOERROR, 0))
4175 #endif /* RE_ENABLE_I18N */
4176 build_upper_buffer (pstr);
4180 #ifdef RE_ENABLE_I18N
4181 if (pstr->mb_cur_max > 1)
4182 build_wcs_buffer (pstr);
4184 #endif /* RE_ENABLE_I18N */
4186 if (pstr->trans != NULL)
4187 re_string_translate_buffer (pstr);
4194 /* Functions for matching context. */
4196 /* Initialize MCTX. */
4198 static reg_errcode_t
4199 internal_function __attribute_warn_unused_result__
4200 match_ctx_init (re_match_context_t *mctx, int eflags, Idx n)
4202 mctx->eflags = eflags;
4203 mctx->match_last = REG_MISSING;
4206 /* Avoid overflow. */
4207 size_t max_object_size =
4208 MAX (sizeof (struct re_backref_cache_entry),
4209 sizeof (re_sub_match_top_t *));
4210 if (BE (SIZE_MAX / max_object_size < n, 0))
4213 mctx->bkref_ents = re_malloc (struct re_backref_cache_entry, n);
4214 mctx->sub_tops = re_malloc (re_sub_match_top_t *, n);
4215 if (BE (mctx->bkref_ents == NULL || mctx->sub_tops == NULL, 0))
4218 /* Already zero-ed by the caller.
4220 mctx->bkref_ents = NULL;
4221 mctx->nbkref_ents = 0;
4222 mctx->nsub_tops = 0; */
4223 mctx->abkref_ents = n;
4224 mctx->max_mb_elem_len = 1;
4225 mctx->asub_tops = n;
4229 /* Clean the entries which depend on the current input in MCTX.
4230 This function must be invoked when the matcher changes the start index
4231 of the input, or changes the input string. */
4235 match_ctx_clean (re_match_context_t *mctx)
4238 for (st_idx = 0; st_idx < mctx->nsub_tops; ++st_idx)
4241 re_sub_match_top_t *top = mctx->sub_tops[st_idx];
4242 for (sl_idx = 0; sl_idx < top->nlasts; ++sl_idx)
4244 re_sub_match_last_t *last = top->lasts[sl_idx];
4245 re_free (last->path.array);
4248 re_free (top->lasts);
4251 re_free (top->path->array);
4252 re_free (top->path);
4257 mctx->nsub_tops = 0;
4258 mctx->nbkref_ents = 0;
4261 /* Free all the memory associated with MCTX. */
4265 match_ctx_free (re_match_context_t *mctx)
4267 /* First, free all the memory associated with MCTX->SUB_TOPS. */
4268 match_ctx_clean (mctx);
4269 re_free (mctx->sub_tops);
4270 re_free (mctx->bkref_ents);
4273 /* Add a new backreference entry to MCTX.
4274 Note that we assume that caller never call this function with duplicate
4275 entry, and call with STR_IDX which isn't smaller than any existing entry.
4278 static reg_errcode_t
4279 internal_function __attribute_warn_unused_result__
4280 match_ctx_add_entry (re_match_context_t *mctx, Idx node, Idx str_idx, Idx from,
4283 if (mctx->nbkref_ents >= mctx->abkref_ents)
4285 struct re_backref_cache_entry* new_entry;
4286 new_entry = re_realloc (mctx->bkref_ents, struct re_backref_cache_entry,
4287 mctx->abkref_ents * 2);
4288 if (BE (new_entry == NULL, 0))
4290 re_free (mctx->bkref_ents);
4293 mctx->bkref_ents = new_entry;
4294 memset (mctx->bkref_ents + mctx->nbkref_ents, '\0',
4295 sizeof (struct re_backref_cache_entry) * mctx->abkref_ents);
4296 mctx->abkref_ents *= 2;
4298 if (mctx->nbkref_ents > 0
4299 && mctx->bkref_ents[mctx->nbkref_ents - 1].str_idx == str_idx)
4300 mctx->bkref_ents[mctx->nbkref_ents - 1].more = 1;
4302 mctx->bkref_ents[mctx->nbkref_ents].node = node;
4303 mctx->bkref_ents[mctx->nbkref_ents].str_idx = str_idx;
4304 mctx->bkref_ents[mctx->nbkref_ents].subexp_from = from;
4305 mctx->bkref_ents[mctx->nbkref_ents].subexp_to = to;
4307 /* This is a cache that saves negative results of check_dst_limits_calc_pos.
4308 If bit N is clear, means that this entry won't epsilon-transition to
4309 an OP_OPEN_SUBEXP or OP_CLOSE_SUBEXP for the N+1-th subexpression. If
4310 it is set, check_dst_limits_calc_pos_1 will recurse and try to find one
4313 A backreference does not epsilon-transition unless it is empty, so set
4314 to all zeros if FROM != TO. */
4315 mctx->bkref_ents[mctx->nbkref_ents].eps_reachable_subexps_map
4316 = (from == to ? -1 : 0);
4318 mctx->bkref_ents[mctx->nbkref_ents++].more = 0;
4319 if (mctx->max_mb_elem_len < to - from)
4320 mctx->max_mb_elem_len = to - from;
4324 /* Return the first entry with the same str_idx, or REG_MISSING if none is
4325 found. Note that MCTX->BKREF_ENTS is already sorted by MCTX->STR_IDX. */
4329 search_cur_bkref_entry (const re_match_context_t *mctx, Idx str_idx)
4331 Idx left, right, mid, last;
4332 last = right = mctx->nbkref_ents;
4333 for (left = 0; left < right;)
4335 mid = (left + right) / 2;
4336 if (mctx->bkref_ents[mid].str_idx < str_idx)
4341 if (left < last && mctx->bkref_ents[left].str_idx == str_idx)
4347 /* Register the node NODE, whose type is OP_OPEN_SUBEXP, and which matches
4350 static reg_errcode_t
4351 internal_function __attribute_warn_unused_result__
4352 match_ctx_add_subtop (re_match_context_t *mctx, Idx node, Idx str_idx)
4355 assert (mctx->sub_tops != NULL);
4356 assert (mctx->asub_tops > 0);
4358 if (BE (mctx->nsub_tops == mctx->asub_tops, 0))
4360 Idx new_asub_tops = mctx->asub_tops * 2;
4361 re_sub_match_top_t **new_array = re_realloc (mctx->sub_tops,
4362 re_sub_match_top_t *,
4364 if (BE (new_array == NULL, 0))
4366 mctx->sub_tops = new_array;
4367 mctx->asub_tops = new_asub_tops;
4369 mctx->sub_tops[mctx->nsub_tops] = calloc (1, sizeof (re_sub_match_top_t));
4370 if (BE (mctx->sub_tops[mctx->nsub_tops] == NULL, 0))
4372 mctx->sub_tops[mctx->nsub_tops]->node = node;
4373 mctx->sub_tops[mctx->nsub_tops++]->str_idx = str_idx;
4377 /* Register the node NODE, whose type is OP_CLOSE_SUBEXP, and which matches
4378 at STR_IDX, whose corresponding OP_OPEN_SUBEXP is SUB_TOP. */
4380 static re_sub_match_last_t *
4382 match_ctx_add_sublast (re_sub_match_top_t *subtop, Idx node, Idx str_idx)
4384 re_sub_match_last_t *new_entry;
4385 if (BE (subtop->nlasts == subtop->alasts, 0))
4387 Idx new_alasts = 2 * subtop->alasts + 1;
4388 re_sub_match_last_t **new_array = re_realloc (subtop->lasts,
4389 re_sub_match_last_t *,
4391 if (BE (new_array == NULL, 0))
4393 subtop->lasts = new_array;
4394 subtop->alasts = new_alasts;
4396 new_entry = calloc (1, sizeof (re_sub_match_last_t));
4397 if (BE (new_entry != NULL, 1))
4399 subtop->lasts[subtop->nlasts] = new_entry;
4400 new_entry->node = node;
4401 new_entry->str_idx = str_idx;
4409 sift_ctx_init (re_sift_context_t *sctx, re_dfastate_t **sifted_sts,
4410 re_dfastate_t **limited_sts, Idx last_node, Idx last_str_idx)
4412 sctx->sifted_states = sifted_sts;
4413 sctx->limited_states = limited_sts;
4414 sctx->last_node = last_node;
4415 sctx->last_str_idx = last_str_idx;
4416 re_node_set_init_empty (&sctx->limits);