1 /* -*- buffer-read-only: t -*- vi: set ro: */
2 /* DO NOT EDIT! GENERATED AUTOMATICALLY! */
3 /* Extended regular expression matching and search library.
4 Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008 Free Software Foundation,
6 This file is part of the GNU C Library.
7 Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>.
9 This program is free software; you can redistribute it and/or modify
10 it under the terms of the GNU General Public License as published by
11 the Free Software Foundation; either version 3, or (at your option)
14 This program is distributed in the hope that it will be useful,
15 but WITHOUT ANY WARRANTY; without even the implied warranty of
16 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
17 GNU General Public License for more details.
19 You should have received a copy of the GNU General Public License along
20 with this program; if not, write to the Free Software Foundation,
21 Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA. */
23 static reg_errcode_t match_ctx_init (re_match_context_t *cache, int eflags,
24 Idx n) internal_function;
25 static void match_ctx_clean (re_match_context_t *mctx) internal_function;
26 static void match_ctx_free (re_match_context_t *cache) internal_function;
27 static reg_errcode_t match_ctx_add_entry (re_match_context_t *cache, Idx node,
28 Idx str_idx, Idx from, Idx to)
30 static Idx search_cur_bkref_entry (const re_match_context_t *mctx, Idx str_idx)
32 static reg_errcode_t match_ctx_add_subtop (re_match_context_t *mctx, Idx node,
33 Idx str_idx) internal_function;
34 static re_sub_match_last_t * match_ctx_add_sublast (re_sub_match_top_t *subtop,
35 Idx node, Idx str_idx)
37 static void sift_ctx_init (re_sift_context_t *sctx, re_dfastate_t **sifted_sts,
38 re_dfastate_t **limited_sts, Idx last_node,
41 static reg_errcode_t re_search_internal (const regex_t *preg,
42 const char *string, Idx length,
43 Idx start, Idx last_start, Idx stop,
44 size_t nmatch, regmatch_t pmatch[],
45 int eflags) internal_function;
46 static regoff_t re_search_2_stub (struct re_pattern_buffer *bufp,
47 const char *string1, Idx length1,
48 const char *string2, Idx length2,
49 Idx start, regoff_t range,
50 struct re_registers *regs,
51 Idx stop, bool ret_len) internal_function;
52 static regoff_t re_search_stub (struct re_pattern_buffer *bufp,
53 const char *string, Idx length, Idx start,
54 regoff_t range, Idx stop,
55 struct re_registers *regs,
56 bool ret_len) internal_function;
57 static unsigned int re_copy_regs (struct re_registers *regs, regmatch_t *pmatch,
58 Idx nregs, int regs_allocated)
60 static reg_errcode_t prune_impossible_nodes (re_match_context_t *mctx)
62 static Idx check_matching (re_match_context_t *mctx, bool fl_longest_match,
63 Idx *p_match_first) internal_function;
64 static Idx check_halt_state_context (const re_match_context_t *mctx,
65 const re_dfastate_t *state, Idx idx)
67 static void update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
68 regmatch_t *prev_idx_match, Idx cur_node,
69 Idx cur_idx, Idx nmatch) internal_function;
70 static reg_errcode_t push_fail_stack (struct re_fail_stack_t *fs,
71 Idx str_idx, Idx dest_node, Idx nregs,
73 re_node_set *eps_via_nodes)
75 static reg_errcode_t set_regs (const regex_t *preg,
76 const re_match_context_t *mctx,
77 size_t nmatch, regmatch_t *pmatch,
78 bool fl_backtrack) internal_function;
79 static reg_errcode_t free_fail_stack_return (struct re_fail_stack_t *fs)
83 static int sift_states_iter_mb (const re_match_context_t *mctx,
84 re_sift_context_t *sctx,
85 Idx node_idx, Idx str_idx, Idx max_str_idx)
87 #endif /* RE_ENABLE_I18N */
88 static reg_errcode_t sift_states_backward (const re_match_context_t *mctx,
89 re_sift_context_t *sctx)
91 static reg_errcode_t build_sifted_states (const re_match_context_t *mctx,
92 re_sift_context_t *sctx, Idx str_idx,
93 re_node_set *cur_dest)
95 static reg_errcode_t update_cur_sifted_state (const re_match_context_t *mctx,
96 re_sift_context_t *sctx,
98 re_node_set *dest_nodes)
100 static reg_errcode_t add_epsilon_src_nodes (const re_dfa_t *dfa,
101 re_node_set *dest_nodes,
102 const re_node_set *candidates)
104 static bool check_dst_limits (const re_match_context_t *mctx,
105 const re_node_set *limits,
106 Idx dst_node, Idx dst_idx, Idx src_node,
107 Idx src_idx) internal_function;
108 static int check_dst_limits_calc_pos_1 (const re_match_context_t *mctx,
109 int boundaries, Idx subexp_idx,
110 Idx from_node, Idx bkref_idx)
112 static int check_dst_limits_calc_pos (const re_match_context_t *mctx,
113 Idx limit, Idx subexp_idx,
114 Idx node, Idx str_idx,
115 Idx bkref_idx) internal_function;
116 static reg_errcode_t check_subexp_limits (const re_dfa_t *dfa,
117 re_node_set *dest_nodes,
118 const re_node_set *candidates,
120 struct re_backref_cache_entry *bkref_ents,
121 Idx str_idx) internal_function;
122 static reg_errcode_t sift_states_bkref (const re_match_context_t *mctx,
123 re_sift_context_t *sctx,
124 Idx str_idx, const re_node_set *candidates)
126 static reg_errcode_t merge_state_array (const re_dfa_t *dfa,
128 re_dfastate_t **src, Idx num)
130 static re_dfastate_t *find_recover_state (reg_errcode_t *err,
131 re_match_context_t *mctx) internal_function;
132 static re_dfastate_t *transit_state (reg_errcode_t *err,
133 re_match_context_t *mctx,
134 re_dfastate_t *state) internal_function;
135 static re_dfastate_t *merge_state_with_log (reg_errcode_t *err,
136 re_match_context_t *mctx,
137 re_dfastate_t *next_state)
139 static reg_errcode_t check_subexp_matching_top (re_match_context_t *mctx,
140 re_node_set *cur_nodes,
141 Idx str_idx) internal_function;
143 static re_dfastate_t *transit_state_sb (reg_errcode_t *err,
144 re_match_context_t *mctx,
145 re_dfastate_t *pstate)
148 #ifdef RE_ENABLE_I18N
149 static reg_errcode_t transit_state_mb (re_match_context_t *mctx,
150 re_dfastate_t *pstate)
152 #endif /* RE_ENABLE_I18N */
153 static reg_errcode_t transit_state_bkref (re_match_context_t *mctx,
154 const re_node_set *nodes)
156 static reg_errcode_t get_subexp (re_match_context_t *mctx,
157 Idx bkref_node, Idx bkref_str_idx)
159 static reg_errcode_t get_subexp_sub (re_match_context_t *mctx,
160 const re_sub_match_top_t *sub_top,
161 re_sub_match_last_t *sub_last,
162 Idx bkref_node, Idx bkref_str)
164 static Idx find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
165 Idx subexp_idx, int type) internal_function;
166 static reg_errcode_t check_arrival (re_match_context_t *mctx,
167 state_array_t *path, Idx top_node,
168 Idx top_str, Idx last_node, Idx last_str,
169 int type) internal_function;
170 static reg_errcode_t check_arrival_add_next_nodes (re_match_context_t *mctx,
172 re_node_set *cur_nodes,
173 re_node_set *next_nodes)
175 static reg_errcode_t check_arrival_expand_ecl (const re_dfa_t *dfa,
176 re_node_set *cur_nodes,
177 Idx ex_subexp, int type)
179 static reg_errcode_t check_arrival_expand_ecl_sub (const re_dfa_t *dfa,
180 re_node_set *dst_nodes,
181 Idx target, Idx ex_subexp,
182 int type) internal_function;
183 static reg_errcode_t expand_bkref_cache (re_match_context_t *mctx,
184 re_node_set *cur_nodes, Idx cur_str,
185 Idx subexp_num, int type)
187 static bool build_trtable (const re_dfa_t *dfa,
188 re_dfastate_t *state) internal_function;
189 #ifdef RE_ENABLE_I18N
190 static int check_node_accept_bytes (const re_dfa_t *dfa, Idx node_idx,
191 const re_string_t *input, Idx idx)
194 static unsigned int find_collation_sequence_value (const unsigned char *mbs,
198 #endif /* RE_ENABLE_I18N */
199 static Idx group_nodes_into_DFAstates (const re_dfa_t *dfa,
200 const re_dfastate_t *state,
201 re_node_set *states_node,
202 bitset_t *states_ch) internal_function;
203 static bool check_node_accept (const re_match_context_t *mctx,
204 const re_token_t *node, Idx idx)
206 static reg_errcode_t extend_buffers (re_match_context_t *mctx)
209 /* Entry point for POSIX code. */
211 /* regexec searches for a given pattern, specified by PREG, in the
214 If NMATCH is zero or REG_NOSUB was set in the cflags argument to
215 `regcomp', we ignore PMATCH. Otherwise, we assume PMATCH has at
216 least NMATCH elements, and we set them to the offsets of the
217 corresponding matched substrings.
219 EFLAGS specifies `execution flags' which affect matching: if
220 REG_NOTBOL is set, then ^ does not match at the beginning of the
221 string; if REG_NOTEOL is set, then $ does not match at the end.
223 We return 0 if we find a match and REG_NOMATCH if not. */
226 regexec (preg, string, nmatch, pmatch, eflags)
227 const regex_t *_Restrict_ preg;
228 const char *_Restrict_ string;
230 regmatch_t pmatch[_Restrict_arr_];
236 re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
239 if (eflags & ~(REG_NOTBOL | REG_NOTEOL | REG_STARTEND))
242 if (eflags & REG_STARTEND)
244 start = pmatch[0].rm_so;
245 length = pmatch[0].rm_eo;
250 length = strlen (string);
253 __libc_lock_lock (dfa->lock);
255 err = re_search_internal (preg, string, length, start, length,
256 length, 0, NULL, eflags);
258 err = re_search_internal (preg, string, length, start, length,
259 length, nmatch, pmatch, eflags);
260 __libc_lock_unlock (dfa->lock);
261 return err != REG_NOERROR;
265 # include <shlib-compat.h>
266 versioned_symbol (libc, __regexec, regexec, GLIBC_2_3_4);
268 # if SHLIB_COMPAT (libc, GLIBC_2_0, GLIBC_2_3_4)
269 __typeof__ (__regexec) __compat_regexec;
272 attribute_compat_text_section
273 __compat_regexec (const regex_t *_Restrict_ preg,
274 const char *_Restrict_ string, size_t nmatch,
275 regmatch_t pmatch[], int eflags)
277 return regexec (preg, string, nmatch, pmatch,
278 eflags & (REG_NOTBOL | REG_NOTEOL));
280 compat_symbol (libc, __compat_regexec, regexec, GLIBC_2_0);
284 /* Entry points for GNU code. */
286 /* re_match, re_search, re_match_2, re_search_2
288 The former two functions operate on STRING with length LENGTH,
289 while the later two operate on concatenation of STRING1 and STRING2
290 with lengths LENGTH1 and LENGTH2, respectively.
292 re_match() matches the compiled pattern in BUFP against the string,
293 starting at index START.
295 re_search() first tries matching at index START, then it tries to match
296 starting from index START + 1, and so on. The last start position tried
297 is START + RANGE. (Thus RANGE = 0 forces re_search to operate the same
300 The parameter STOP of re_{match,search}_2 specifies that no match exceeding
301 the first STOP characters of the concatenation of the strings should be
304 If REGS is not NULL, and BUFP->no_sub is not set, the offsets of the match
305 and all groups is stored in REGS. (For the "_2" variants, the offsets are
306 computed relative to the concatenation, not relative to the individual
309 On success, re_match* functions return the length of the match, re_search*
310 return the position of the start of the match. Return value -1 means no
311 match was found and -2 indicates an internal error. */
314 re_match (bufp, string, length, start, regs)
315 struct re_pattern_buffer *bufp;
318 struct re_registers *regs;
320 return re_search_stub (bufp, string, length, start, 0, length, regs, true);
323 weak_alias (__re_match, re_match)
327 re_search (bufp, string, length, start, range, regs)
328 struct re_pattern_buffer *bufp;
332 struct re_registers *regs;
334 return re_search_stub (bufp, string, length, start, range, length, regs,
338 weak_alias (__re_search, re_search)
342 re_match_2 (bufp, string1, length1, string2, length2, start, regs, stop)
343 struct re_pattern_buffer *bufp;
344 const char *string1, *string2;
345 Idx length1, length2, start, stop;
346 struct re_registers *regs;
348 return re_search_2_stub (bufp, string1, length1, string2, length2,
349 start, 0, regs, stop, true);
352 weak_alias (__re_match_2, re_match_2)
356 re_search_2 (bufp, string1, length1, string2, length2, start, range, regs, stop)
357 struct re_pattern_buffer *bufp;
358 const char *string1, *string2;
359 Idx length1, length2, start, stop;
361 struct re_registers *regs;
363 return re_search_2_stub (bufp, string1, length1, string2, length2,
364 start, range, regs, stop, false);
367 weak_alias (__re_search_2, re_search_2)
372 re_search_2_stub (struct re_pattern_buffer *bufp,
373 const char *string1, Idx length1,
374 const char *string2, Idx length2,
375 Idx start, regoff_t range, struct re_registers *regs,
376 Idx stop, bool ret_len)
380 Idx len = length1 + length2;
383 if (BE (length1 < 0 || length2 < 0 || stop < 0 || len < length1, 0))
386 /* Concatenate the strings. */
390 s = re_malloc (char, len);
392 if (BE (s == NULL, 0))
395 memcpy (__mempcpy (s, string1, length1), string2, length2);
397 memcpy (s, string1, length1);
398 memcpy (s + length1, string2, length2);
407 rval = re_search_stub (bufp, str, len, start, range, stop, regs,
413 /* The parameters have the same meaning as those of re_search.
414 Additional parameters:
415 If RET_LEN is true the length of the match is returned (re_match style);
416 otherwise the position of the match is returned. */
420 re_search_stub (struct re_pattern_buffer *bufp,
421 const char *string, Idx length,
422 Idx start, regoff_t range, Idx stop, struct re_registers *regs,
425 reg_errcode_t result;
431 re_dfa_t *dfa = (re_dfa_t *) bufp->buffer;
433 Idx last_start = start + range;
435 /* Check for out-of-range. */
436 if (BE (start < 0 || start > length, 0))
438 if (BE (length < last_start || (0 <= range && last_start < start), 0))
440 else if (BE (last_start < 0 || (range < 0 && start <= last_start), 0))
443 __libc_lock_lock (dfa->lock);
445 eflags |= (bufp->not_bol) ? REG_NOTBOL : 0;
446 eflags |= (bufp->not_eol) ? REG_NOTEOL : 0;
448 /* Compile fastmap if we haven't yet. */
449 if (start < last_start && bufp->fastmap != NULL && !bufp->fastmap_accurate)
450 re_compile_fastmap (bufp);
452 if (BE (bufp->no_sub, 0))
455 /* We need at least 1 register. */
458 else if (BE (bufp->regs_allocated == REGS_FIXED
459 && regs->num_regs <= bufp->re_nsub, 0))
461 nregs = regs->num_regs;
462 if (BE (nregs < 1, 0))
464 /* Nothing can be copied to regs. */
470 nregs = bufp->re_nsub + 1;
471 pmatch = re_malloc (regmatch_t, nregs);
472 if (BE (pmatch == NULL, 0))
478 result = re_search_internal (bufp, string, length, start, last_start, stop,
479 nregs, pmatch, eflags);
483 /* I hope we needn't fill ther regs with -1's when no match was found. */
484 if (result != REG_NOERROR)
486 else if (regs != NULL)
488 /* If caller wants register contents data back, copy them. */
489 bufp->regs_allocated = re_copy_regs (regs, pmatch, nregs,
490 bufp->regs_allocated);
491 if (BE (bufp->regs_allocated == REGS_UNALLOCATED, 0))
495 if (BE (rval == 0, 1))
499 assert (pmatch[0].rm_so == start);
500 rval = pmatch[0].rm_eo - start;
503 rval = pmatch[0].rm_so;
507 __libc_lock_unlock (dfa->lock);
513 re_copy_regs (struct re_registers *regs, regmatch_t *pmatch, Idx nregs,
516 int rval = REGS_REALLOCATE;
518 Idx need_regs = nregs + 1;
519 /* We need one extra element beyond `num_regs' for the `-1' marker GNU code
522 /* Have the register data arrays been allocated? */
523 if (regs_allocated == REGS_UNALLOCATED)
524 { /* No. So allocate them with malloc. */
525 regs->start = re_malloc (regoff_t, need_regs);
526 if (BE (regs->start == NULL, 0))
527 return REGS_UNALLOCATED;
528 regs->end = re_malloc (regoff_t, need_regs);
529 if (BE (regs->end == NULL, 0))
531 re_free (regs->start);
532 return REGS_UNALLOCATED;
534 regs->num_regs = need_regs;
536 else if (regs_allocated == REGS_REALLOCATE)
537 { /* Yes. If we need more elements than were already
538 allocated, reallocate them. If we need fewer, just
540 if (BE (need_regs > regs->num_regs, 0))
542 regoff_t *new_start = re_realloc (regs->start, regoff_t, need_regs);
544 if (BE (new_start == NULL, 0))
545 return REGS_UNALLOCATED;
546 new_end = re_realloc (regs->end, regoff_t, need_regs);
547 if (BE (new_end == NULL, 0))
550 return REGS_UNALLOCATED;
552 regs->start = new_start;
554 regs->num_regs = need_regs;
559 assert (regs_allocated == REGS_FIXED);
560 /* This function may not be called with REGS_FIXED and nregs too big. */
561 assert (regs->num_regs >= nregs);
566 for (i = 0; i < nregs; ++i)
568 regs->start[i] = pmatch[i].rm_so;
569 regs->end[i] = pmatch[i].rm_eo;
571 for ( ; i < regs->num_regs; ++i)
572 regs->start[i] = regs->end[i] = -1;
577 /* Set REGS to hold NUM_REGS registers, storing them in STARTS and
578 ENDS. Subsequent matches using PATTERN_BUFFER and REGS will use
579 this memory for recording register information. STARTS and ENDS
580 must be allocated using the malloc library routine, and must each
581 be at least NUM_REGS * sizeof (regoff_t) bytes long.
583 If NUM_REGS == 0, then subsequent matches should allocate their own
586 Unless this function is called, the first search or match using
587 PATTERN_BUFFER will allocate its own register data, without
588 freeing the old data. */
591 re_set_registers (bufp, regs, num_regs, starts, ends)
592 struct re_pattern_buffer *bufp;
593 struct re_registers *regs;
594 __re_size_t num_regs;
595 regoff_t *starts, *ends;
599 bufp->regs_allocated = REGS_REALLOCATE;
600 regs->num_regs = num_regs;
601 regs->start = starts;
606 bufp->regs_allocated = REGS_UNALLOCATED;
608 regs->start = regs->end = NULL;
612 weak_alias (__re_set_registers, re_set_registers)
615 /* Entry points compatible with 4.2 BSD regex library. We don't define
616 them unless specifically requested. */
618 #if defined _REGEX_RE_COMP || defined _LIBC
626 return 0 == regexec (&re_comp_buf, s, 0, NULL, 0);
628 #endif /* _REGEX_RE_COMP */
630 /* Internal entry point. */
632 /* Searches for a compiled pattern PREG in the string STRING, whose
633 length is LENGTH. NMATCH, PMATCH, and EFLAGS have the same
634 meaning as with regexec. LAST_START is START + RANGE, where
635 START and RANGE have the same meaning as with re_search.
636 Return REG_NOERROR if we find a match, and REG_NOMATCH if not,
637 otherwise return the error code.
638 Note: We assume front end functions already check ranges.
639 (0 <= LAST_START && LAST_START <= LENGTH) */
643 re_search_internal (const regex_t *preg,
644 const char *string, Idx length,
645 Idx start, Idx last_start, Idx stop,
646 size_t nmatch, regmatch_t pmatch[],
650 const re_dfa_t *dfa = (const re_dfa_t *) preg->buffer;
651 Idx left_lim, right_lim;
653 bool fl_longest_match;
656 Idx match_last = REG_MISSING;
660 #if defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L)
661 re_match_context_t mctx = { .dfa = dfa };
663 re_match_context_t mctx;
665 char *fastmap = ((preg->fastmap != NULL && preg->fastmap_accurate
666 && start != last_start && !preg->can_be_null)
667 ? preg->fastmap : NULL);
668 RE_TRANSLATE_TYPE t = preg->translate;
670 #if !(defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L))
671 memset (&mctx, '\0', sizeof (re_match_context_t));
675 extra_nmatch = (nmatch > preg->re_nsub) ? nmatch - (preg->re_nsub + 1) : 0;
676 nmatch -= extra_nmatch;
678 /* Check if the DFA haven't been compiled. */
679 if (BE (preg->used == 0 || dfa->init_state == NULL
680 || dfa->init_state_word == NULL || dfa->init_state_nl == NULL
681 || dfa->init_state_begbuf == NULL, 0))
685 /* We assume front-end functions already check them. */
686 assert (0 <= last_start && last_start <= length);
689 /* If initial states with non-begbuf contexts have no elements,
690 the regex must be anchored. If preg->newline_anchor is set,
691 we'll never use init_state_nl, so do not check it. */
692 if (dfa->init_state->nodes.nelem == 0
693 && dfa->init_state_word->nodes.nelem == 0
694 && (dfa->init_state_nl->nodes.nelem == 0
695 || !preg->newline_anchor))
697 if (start != 0 && last_start != 0)
699 start = last_start = 0;
702 /* We must check the longest matching, if nmatch > 0. */
703 fl_longest_match = (nmatch != 0 || dfa->nbackref);
705 err = re_string_allocate (&mctx.input, string, length, dfa->nodes_len + 1,
706 preg->translate, (preg->syntax & RE_ICASE) != 0,
708 if (BE (err != REG_NOERROR, 0))
710 mctx.input.stop = stop;
711 mctx.input.raw_stop = stop;
712 mctx.input.newline_anchor = preg->newline_anchor;
714 err = match_ctx_init (&mctx, eflags, dfa->nbackref * 2);
715 if (BE (err != REG_NOERROR, 0))
718 /* We will log all the DFA states through which the dfa pass,
719 if nmatch > 1, or this dfa has "multibyte node", which is a
720 back-reference or a node which can accept multibyte character or
721 multi character collating element. */
722 if (nmatch > 1 || dfa->has_mb_node)
724 /* Avoid overflow. */
725 if (BE (SIZE_MAX / sizeof (re_dfastate_t *) <= mctx.input.bufs_len, 0))
731 mctx.state_log = re_malloc (re_dfastate_t *, mctx.input.bufs_len + 1);
732 if (BE (mctx.state_log == NULL, 0))
739 mctx.state_log = NULL;
742 mctx.input.tip_context = (eflags & REG_NOTBOL) ? CONTEXT_BEGBUF
743 : CONTEXT_NEWLINE | CONTEXT_BEGBUF;
745 /* Check incrementally whether of not the input string match. */
746 incr = (last_start < start) ? -1 : 1;
747 left_lim = (last_start < start) ? last_start : start;
748 right_lim = (last_start < start) ? start : last_start;
749 sb = dfa->mb_cur_max == 1;
752 ? ((sb || !(preg->syntax & RE_ICASE || t) ? 4 : 0)
753 | (start <= last_start ? 2 : 0)
754 | (t != NULL ? 1 : 0))
757 for (;; match_first += incr)
760 if (match_first < left_lim || right_lim < match_first)
763 /* Advance as rapidly as possible through the string, until we
764 find a plausible place to start matching. This may be done
765 with varying efficiency, so there are various possibilities:
766 only the most common of them are specialized, in order to
767 save on code size. We use a switch statement for speed. */
775 /* Fastmap with single-byte translation, match forward. */
776 while (BE (match_first < right_lim, 1)
777 && !fastmap[t[(unsigned char) string[match_first]]])
779 goto forward_match_found_start_or_reached_end;
782 /* Fastmap without translation, match forward. */
783 while (BE (match_first < right_lim, 1)
784 && !fastmap[(unsigned char) string[match_first]])
787 forward_match_found_start_or_reached_end:
788 if (BE (match_first == right_lim, 0))
790 ch = match_first >= length
791 ? 0 : (unsigned char) string[match_first];
792 if (!fastmap[t ? t[ch] : ch])
799 /* Fastmap without multi-byte translation, match backwards. */
800 while (match_first >= left_lim)
802 ch = match_first >= length
803 ? 0 : (unsigned char) string[match_first];
804 if (fastmap[t ? t[ch] : ch])
808 if (match_first < left_lim)
813 /* In this case, we can't determine easily the current byte,
814 since it might be a component byte of a multibyte
815 character. Then we use the constructed buffer instead. */
818 /* If MATCH_FIRST is out of the valid range, reconstruct the
820 __re_size_t offset = match_first - mctx.input.raw_mbs_idx;
821 if (BE (offset >= (__re_size_t) mctx.input.valid_raw_len, 0))
823 err = re_string_reconstruct (&mctx.input, match_first,
825 if (BE (err != REG_NOERROR, 0))
828 offset = match_first - mctx.input.raw_mbs_idx;
830 /* If MATCH_FIRST is out of the buffer, leave it as '\0'.
831 Note that MATCH_FIRST must not be smaller than 0. */
832 ch = (match_first >= length
833 ? 0 : re_string_byte_at (&mctx.input, offset));
837 if (match_first < left_lim || match_first > right_lim)
846 /* Reconstruct the buffers so that the matcher can assume that
847 the matching starts from the beginning of the buffer. */
848 err = re_string_reconstruct (&mctx.input, match_first, eflags);
849 if (BE (err != REG_NOERROR, 0))
852 #ifdef RE_ENABLE_I18N
853 /* Don't consider this char as a possible match start if it part,
854 yet isn't the head, of a multibyte character. */
855 if (!sb && !re_string_first_byte (&mctx.input, 0))
859 /* It seems to be appropriate one, then use the matcher. */
860 /* We assume that the matching starts from 0. */
861 mctx.state_log_top = mctx.nbkref_ents = mctx.max_mb_elem_len = 0;
862 match_last = check_matching (&mctx, fl_longest_match,
863 start <= last_start ? &match_first : NULL);
864 if (match_last != REG_MISSING)
866 if (BE (match_last == REG_ERROR, 0))
873 mctx.match_last = match_last;
874 if ((!preg->no_sub && nmatch > 1) || dfa->nbackref)
876 re_dfastate_t *pstate = mctx.state_log[match_last];
877 mctx.last_node = check_halt_state_context (&mctx, pstate,
880 if ((!preg->no_sub && nmatch > 1 && dfa->has_plural_match)
883 err = prune_impossible_nodes (&mctx);
884 if (err == REG_NOERROR)
886 if (BE (err != REG_NOMATCH, 0))
888 match_last = REG_MISSING;
891 break; /* We found a match. */
895 match_ctx_clean (&mctx);
899 assert (match_last != REG_MISSING);
900 assert (err == REG_NOERROR);
903 /* Set pmatch[] if we need. */
908 /* Initialize registers. */
909 for (reg_idx = 1; reg_idx < nmatch; ++reg_idx)
910 pmatch[reg_idx].rm_so = pmatch[reg_idx].rm_eo = -1;
912 /* Set the points where matching start/end. */
914 pmatch[0].rm_eo = mctx.match_last;
915 /* FIXME: This function should fail if mctx.match_last exceeds
916 the maximum possible regoff_t value. We need a new error
917 code REG_OVERFLOW. */
919 if (!preg->no_sub && nmatch > 1)
921 err = set_regs (preg, &mctx, nmatch, pmatch,
922 dfa->has_plural_match && dfa->nbackref > 0);
923 if (BE (err != REG_NOERROR, 0))
927 /* At last, add the offset to the each registers, since we slided
928 the buffers so that we could assume that the matching starts
930 for (reg_idx = 0; reg_idx < nmatch; ++reg_idx)
931 if (pmatch[reg_idx].rm_so != -1)
933 #ifdef RE_ENABLE_I18N
934 if (BE (mctx.input.offsets_needed != 0, 0))
936 pmatch[reg_idx].rm_so =
937 (pmatch[reg_idx].rm_so == mctx.input.valid_len
938 ? mctx.input.valid_raw_len
939 : mctx.input.offsets[pmatch[reg_idx].rm_so]);
940 pmatch[reg_idx].rm_eo =
941 (pmatch[reg_idx].rm_eo == mctx.input.valid_len
942 ? mctx.input.valid_raw_len
943 : mctx.input.offsets[pmatch[reg_idx].rm_eo]);
946 assert (mctx.input.offsets_needed == 0);
948 pmatch[reg_idx].rm_so += match_first;
949 pmatch[reg_idx].rm_eo += match_first;
951 for (reg_idx = 0; reg_idx < extra_nmatch; ++reg_idx)
953 pmatch[nmatch + reg_idx].rm_so = -1;
954 pmatch[nmatch + reg_idx].rm_eo = -1;
958 for (reg_idx = 0; reg_idx + 1 < nmatch; reg_idx++)
959 if (dfa->subexp_map[reg_idx] != reg_idx)
961 pmatch[reg_idx + 1].rm_so
962 = pmatch[dfa->subexp_map[reg_idx] + 1].rm_so;
963 pmatch[reg_idx + 1].rm_eo
964 = pmatch[dfa->subexp_map[reg_idx] + 1].rm_eo;
969 re_free (mctx.state_log);
971 match_ctx_free (&mctx);
972 re_string_destruct (&mctx.input);
978 prune_impossible_nodes (re_match_context_t *mctx)
980 const re_dfa_t *const dfa = mctx->dfa;
981 Idx halt_node, match_last;
983 re_dfastate_t **sifted_states;
984 re_dfastate_t **lim_states = NULL;
985 re_sift_context_t sctx;
987 assert (mctx->state_log != NULL);
989 match_last = mctx->match_last;
990 halt_node = mctx->last_node;
992 /* Avoid overflow. */
993 if (BE (SIZE_MAX / sizeof (re_dfastate_t *) <= match_last, 0))
996 sifted_states = re_malloc (re_dfastate_t *, match_last + 1);
997 if (BE (sifted_states == NULL, 0))
1004 lim_states = re_malloc (re_dfastate_t *, match_last + 1);
1005 if (BE (lim_states == NULL, 0))
1012 memset (lim_states, '\0',
1013 sizeof (re_dfastate_t *) * (match_last + 1));
1014 sift_ctx_init (&sctx, sifted_states, lim_states, halt_node,
1016 ret = sift_states_backward (mctx, &sctx);
1017 re_node_set_free (&sctx.limits);
1018 if (BE (ret != REG_NOERROR, 0))
1020 if (sifted_states[0] != NULL || lim_states[0] != NULL)
1025 if (! REG_VALID_INDEX (match_last))
1030 } while (mctx->state_log[match_last] == NULL
1031 || !mctx->state_log[match_last]->halt);
1032 halt_node = check_halt_state_context (mctx,
1033 mctx->state_log[match_last],
1036 ret = merge_state_array (dfa, sifted_states, lim_states,
1038 re_free (lim_states);
1040 if (BE (ret != REG_NOERROR, 0))
1045 sift_ctx_init (&sctx, sifted_states, lim_states, halt_node, match_last);
1046 ret = sift_states_backward (mctx, &sctx);
1047 re_node_set_free (&sctx.limits);
1048 if (BE (ret != REG_NOERROR, 0))
1051 re_free (mctx->state_log);
1052 mctx->state_log = sifted_states;
1053 sifted_states = NULL;
1054 mctx->last_node = halt_node;
1055 mctx->match_last = match_last;
1058 re_free (sifted_states);
1059 re_free (lim_states);
1063 /* Acquire an initial state and return it.
1064 We must select appropriate initial state depending on the context,
1065 since initial states may have constraints like "\<", "^", etc.. */
1067 static inline re_dfastate_t *
1068 __attribute ((always_inline)) internal_function
1069 acquire_init_state_context (reg_errcode_t *err, const re_match_context_t *mctx,
1072 const re_dfa_t *const dfa = mctx->dfa;
1073 if (dfa->init_state->has_constraint)
1075 unsigned int context;
1076 context = re_string_context_at (&mctx->input, idx - 1, mctx->eflags);
1077 if (IS_WORD_CONTEXT (context))
1078 return dfa->init_state_word;
1079 else if (IS_ORDINARY_CONTEXT (context))
1080 return dfa->init_state;
1081 else if (IS_BEGBUF_CONTEXT (context) && IS_NEWLINE_CONTEXT (context))
1082 return dfa->init_state_begbuf;
1083 else if (IS_NEWLINE_CONTEXT (context))
1084 return dfa->init_state_nl;
1085 else if (IS_BEGBUF_CONTEXT (context))
1087 /* It is relatively rare case, then calculate on demand. */
1088 return re_acquire_state_context (err, dfa,
1089 dfa->init_state->entrance_nodes,
1093 /* Must not happen? */
1094 return dfa->init_state;
1097 return dfa->init_state;
1100 /* Check whether the regular expression match input string INPUT or not,
1101 and return the index where the matching end. Return REG_MISSING if
1102 there is no match, and return REG_ERROR in case of an error.
1103 FL_LONGEST_MATCH means we want the POSIX longest matching.
1104 If P_MATCH_FIRST is not NULL, and the match fails, it is set to the
1105 next place where we may want to try matching.
1106 Note that the matcher assume that the maching starts from the current
1107 index of the buffer. */
1111 check_matching (re_match_context_t *mctx, bool fl_longest_match,
1114 const re_dfa_t *const dfa = mctx->dfa;
1117 Idx match_last = REG_MISSING;
1118 Idx cur_str_idx = re_string_cur_idx (&mctx->input);
1119 re_dfastate_t *cur_state;
1120 bool at_init_state = p_match_first != NULL;
1121 Idx next_start_idx = cur_str_idx;
1124 cur_state = acquire_init_state_context (&err, mctx, cur_str_idx);
1125 /* An initial state must not be NULL (invalid). */
1126 if (BE (cur_state == NULL, 0))
1128 assert (err == REG_ESPACE);
1132 if (mctx->state_log != NULL)
1134 mctx->state_log[cur_str_idx] = cur_state;
1136 /* Check OP_OPEN_SUBEXP in the initial state in case that we use them
1137 later. E.g. Processing back references. */
1138 if (BE (dfa->nbackref, 0))
1140 at_init_state = false;
1141 err = check_subexp_matching_top (mctx, &cur_state->nodes, 0);
1142 if (BE (err != REG_NOERROR, 0))
1145 if (cur_state->has_backref)
1147 err = transit_state_bkref (mctx, &cur_state->nodes);
1148 if (BE (err != REG_NOERROR, 0))
1154 /* If the RE accepts NULL string. */
1155 if (BE (cur_state->halt, 0))
1157 if (!cur_state->has_constraint
1158 || check_halt_state_context (mctx, cur_state, cur_str_idx))
1160 if (!fl_longest_match)
1164 match_last = cur_str_idx;
1170 while (!re_string_eoi (&mctx->input))
1172 re_dfastate_t *old_state = cur_state;
1173 Idx next_char_idx = re_string_cur_idx (&mctx->input) + 1;
1175 if (BE (next_char_idx >= mctx->input.bufs_len, 0)
1176 || (BE (next_char_idx >= mctx->input.valid_len, 0)
1177 && mctx->input.valid_len < mctx->input.len))
1179 err = extend_buffers (mctx);
1180 if (BE (err != REG_NOERROR, 0))
1182 assert (err == REG_ESPACE);
1187 cur_state = transit_state (&err, mctx, cur_state);
1188 if (mctx->state_log != NULL)
1189 cur_state = merge_state_with_log (&err, mctx, cur_state);
1191 if (cur_state == NULL)
1193 /* Reached the invalid state or an error. Try to recover a valid
1194 state using the state log, if available and if we have not
1195 already found a valid (even if not the longest) match. */
1196 if (BE (err != REG_NOERROR, 0))
1199 if (mctx->state_log == NULL
1200 || (match && !fl_longest_match)
1201 || (cur_state = find_recover_state (&err, mctx)) == NULL)
1205 if (BE (at_init_state, 0))
1207 if (old_state == cur_state)
1208 next_start_idx = next_char_idx;
1210 at_init_state = false;
1213 if (cur_state->halt)
1215 /* Reached a halt state.
1216 Check the halt state can satisfy the current context. */
1217 if (!cur_state->has_constraint
1218 || check_halt_state_context (mctx, cur_state,
1219 re_string_cur_idx (&mctx->input)))
1221 /* We found an appropriate halt state. */
1222 match_last = re_string_cur_idx (&mctx->input);
1225 /* We found a match, do not modify match_first below. */
1226 p_match_first = NULL;
1227 if (!fl_longest_match)
1234 *p_match_first += next_start_idx;
1239 /* Check NODE match the current context. */
1243 check_halt_node_context (const re_dfa_t *dfa, Idx node, unsigned int context)
1245 re_token_type_t type = dfa->nodes[node].type;
1246 unsigned int constraint = dfa->nodes[node].constraint;
1247 if (type != END_OF_RE)
1251 if (NOT_SATISFY_NEXT_CONSTRAINT (constraint, context))
1256 /* Check the halt state STATE match the current context.
1257 Return 0 if not match, if the node, STATE has, is a halt node and
1258 match the context, return the node. */
1262 check_halt_state_context (const re_match_context_t *mctx,
1263 const re_dfastate_t *state, Idx idx)
1266 unsigned int context;
1268 assert (state->halt);
1270 context = re_string_context_at (&mctx->input, idx, mctx->eflags);
1271 for (i = 0; i < state->nodes.nelem; ++i)
1272 if (check_halt_node_context (mctx->dfa, state->nodes.elems[i], context))
1273 return state->nodes.elems[i];
1277 /* Compute the next node to which "NFA" transit from NODE("NFA" is a NFA
1278 corresponding to the DFA).
1279 Return the destination node, and update EPS_VIA_NODES;
1280 return REG_MISSING in case of errors. */
1284 proceed_next_node (const re_match_context_t *mctx, Idx nregs, regmatch_t *regs,
1285 Idx *pidx, Idx node, re_node_set *eps_via_nodes,
1286 struct re_fail_stack_t *fs)
1288 const re_dfa_t *const dfa = mctx->dfa;
1291 if (IS_EPSILON_NODE (dfa->nodes[node].type))
1293 re_node_set *cur_nodes = &mctx->state_log[*pidx]->nodes;
1294 re_node_set *edests = &dfa->edests[node];
1296 ok = re_node_set_insert (eps_via_nodes, node);
1299 /* Pick up a valid destination, or return REG_MISSING if none
1301 for (dest_node = REG_MISSING, i = 0; i < edests->nelem; ++i)
1303 Idx candidate = edests->elems[i];
1304 if (!re_node_set_contains (cur_nodes, candidate))
1306 if (dest_node == REG_MISSING)
1307 dest_node = candidate;
1311 /* In order to avoid infinite loop like "(a*)*", return the second
1312 epsilon-transition if the first was already considered. */
1313 if (re_node_set_contains (eps_via_nodes, dest_node))
1316 /* Otherwise, push the second epsilon-transition on the fail stack. */
1318 && push_fail_stack (fs, *pidx, candidate, nregs, regs,
1322 /* We know we are going to exit. */
1331 re_token_type_t type = dfa->nodes[node].type;
1333 #ifdef RE_ENABLE_I18N
1334 if (dfa->nodes[node].accept_mb)
1335 naccepted = check_node_accept_bytes (dfa, node, &mctx->input, *pidx);
1337 #endif /* RE_ENABLE_I18N */
1338 if (type == OP_BACK_REF)
1340 Idx subexp_idx = dfa->nodes[node].opr.idx + 1;
1341 naccepted = regs[subexp_idx].rm_eo - regs[subexp_idx].rm_so;
1344 if (regs[subexp_idx].rm_so == -1 || regs[subexp_idx].rm_eo == -1)
1348 char *buf = (char *) re_string_get_buffer (&mctx->input);
1349 if (memcmp (buf + regs[subexp_idx].rm_so, buf + *pidx,
1358 ok = re_node_set_insert (eps_via_nodes, node);
1361 dest_node = dfa->edests[node].elems[0];
1362 if (re_node_set_contains (&mctx->state_log[*pidx]->nodes,
1369 || check_node_accept (mctx, dfa->nodes + node, *pidx))
1371 Idx dest_node = dfa->nexts[node];
1372 *pidx = (naccepted == 0) ? *pidx + 1 : *pidx + naccepted;
1373 if (fs && (*pidx > mctx->match_last || mctx->state_log[*pidx] == NULL
1374 || !re_node_set_contains (&mctx->state_log[*pidx]->nodes,
1377 re_node_set_empty (eps_via_nodes);
1384 static reg_errcode_t
1386 push_fail_stack (struct re_fail_stack_t *fs, Idx str_idx, Idx dest_node,
1387 Idx nregs, regmatch_t *regs, re_node_set *eps_via_nodes)
1390 Idx num = fs->num++;
1391 if (fs->num == fs->alloc)
1393 struct re_fail_stack_ent_t *new_array;
1394 new_array = realloc (fs->stack, (sizeof (struct re_fail_stack_ent_t)
1396 if (new_array == NULL)
1399 fs->stack = new_array;
1401 fs->stack[num].idx = str_idx;
1402 fs->stack[num].node = dest_node;
1403 fs->stack[num].regs = re_malloc (regmatch_t, nregs);
1404 if (fs->stack[num].regs == NULL)
1406 memcpy (fs->stack[num].regs, regs, sizeof (regmatch_t) * nregs);
1407 err = re_node_set_init_copy (&fs->stack[num].eps_via_nodes, eps_via_nodes);
1413 pop_fail_stack (struct re_fail_stack_t *fs, Idx *pidx, Idx nregs,
1414 regmatch_t *regs, re_node_set *eps_via_nodes)
1416 Idx num = --fs->num;
1417 assert (REG_VALID_INDEX (num));
1418 *pidx = fs->stack[num].idx;
1419 memcpy (regs, fs->stack[num].regs, sizeof (regmatch_t) * nregs);
1420 re_node_set_free (eps_via_nodes);
1421 re_free (fs->stack[num].regs);
1422 *eps_via_nodes = fs->stack[num].eps_via_nodes;
1423 return fs->stack[num].node;
1426 /* Set the positions where the subexpressions are starts/ends to registers
1428 Note: We assume that pmatch[0] is already set, and
1429 pmatch[i].rm_so == pmatch[i].rm_eo == -1 for 0 < i < nmatch. */
1431 static reg_errcode_t
1433 set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
1434 regmatch_t *pmatch, bool fl_backtrack)
1436 const re_dfa_t *dfa = (const re_dfa_t *) preg->buffer;
1438 re_node_set eps_via_nodes;
1439 struct re_fail_stack_t *fs;
1440 struct re_fail_stack_t fs_body = { 0, 2, NULL };
1441 regmatch_t *prev_idx_match;
1442 bool prev_idx_match_malloced = false;
1445 assert (nmatch > 1);
1446 assert (mctx->state_log != NULL);
1451 fs->stack = re_malloc (struct re_fail_stack_ent_t, fs->alloc);
1452 if (fs->stack == NULL)
1458 cur_node = dfa->init_node;
1459 re_node_set_init_empty (&eps_via_nodes);
1461 if (__libc_use_alloca (nmatch * sizeof (regmatch_t)))
1462 prev_idx_match = (regmatch_t *) alloca (nmatch * sizeof (regmatch_t));
1465 prev_idx_match = re_malloc (regmatch_t, nmatch);
1466 if (prev_idx_match == NULL)
1468 free_fail_stack_return (fs);
1471 prev_idx_match_malloced = true;
1473 memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
1475 for (idx = pmatch[0].rm_so; idx <= pmatch[0].rm_eo ;)
1477 update_regs (dfa, pmatch, prev_idx_match, cur_node, idx, nmatch);
1479 if (idx == pmatch[0].rm_eo && cur_node == mctx->last_node)
1484 for (reg_idx = 0; reg_idx < nmatch; ++reg_idx)
1485 if (pmatch[reg_idx].rm_so > -1 && pmatch[reg_idx].rm_eo == -1)
1487 if (reg_idx == nmatch)
1489 re_node_set_free (&eps_via_nodes);
1490 if (prev_idx_match_malloced)
1491 re_free (prev_idx_match);
1492 return free_fail_stack_return (fs);
1494 cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
1499 re_node_set_free (&eps_via_nodes);
1500 if (prev_idx_match_malloced)
1501 re_free (prev_idx_match);
1506 /* Proceed to next node. */
1507 cur_node = proceed_next_node (mctx, nmatch, pmatch, &idx, cur_node,
1508 &eps_via_nodes, fs);
1510 if (BE (! REG_VALID_INDEX (cur_node), 0))
1512 if (BE (cur_node == REG_ERROR, 0))
1514 re_node_set_free (&eps_via_nodes);
1515 if (prev_idx_match_malloced)
1516 re_free (prev_idx_match);
1517 free_fail_stack_return (fs);
1521 cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
1525 re_node_set_free (&eps_via_nodes);
1526 if (prev_idx_match_malloced)
1527 re_free (prev_idx_match);
1532 re_node_set_free (&eps_via_nodes);
1533 if (prev_idx_match_malloced)
1534 re_free (prev_idx_match);
1535 return free_fail_stack_return (fs);
1538 static reg_errcode_t
1540 free_fail_stack_return (struct re_fail_stack_t *fs)
1545 for (fs_idx = 0; fs_idx < fs->num; ++fs_idx)
1547 re_node_set_free (&fs->stack[fs_idx].eps_via_nodes);
1548 re_free (fs->stack[fs_idx].regs);
1550 re_free (fs->stack);
1557 update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
1558 regmatch_t *prev_idx_match, Idx cur_node, Idx cur_idx, Idx nmatch)
1560 int type = dfa->nodes[cur_node].type;
1561 if (type == OP_OPEN_SUBEXP)
1563 Idx reg_num = dfa->nodes[cur_node].opr.idx + 1;
1565 /* We are at the first node of this sub expression. */
1566 if (reg_num < nmatch)
1568 pmatch[reg_num].rm_so = cur_idx;
1569 pmatch[reg_num].rm_eo = -1;
1572 else if (type == OP_CLOSE_SUBEXP)
1574 Idx reg_num = dfa->nodes[cur_node].opr.idx + 1;
1575 if (reg_num < nmatch)
1577 /* We are at the last node of this sub expression. */
1578 if (pmatch[reg_num].rm_so < cur_idx)
1580 pmatch[reg_num].rm_eo = cur_idx;
1581 /* This is a non-empty match or we are not inside an optional
1582 subexpression. Accept this right away. */
1583 memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
1587 if (dfa->nodes[cur_node].opt_subexp
1588 && prev_idx_match[reg_num].rm_so != -1)
1589 /* We transited through an empty match for an optional
1590 subexpression, like (a?)*, and this is not the subexp's
1591 first match. Copy back the old content of the registers
1592 so that matches of an inner subexpression are undone as
1593 well, like in ((a?))*. */
1594 memcpy (pmatch, prev_idx_match, sizeof (regmatch_t) * nmatch);
1596 /* We completed a subexpression, but it may be part of
1597 an optional one, so do not update PREV_IDX_MATCH. */
1598 pmatch[reg_num].rm_eo = cur_idx;
1604 /* This function checks the STATE_LOG from the SCTX->last_str_idx to 0
1605 and sift the nodes in each states according to the following rules.
1606 Updated state_log will be wrote to STATE_LOG.
1608 Rules: We throw away the Node `a' in the STATE_LOG[STR_IDX] if...
1609 1. When STR_IDX == MATCH_LAST(the last index in the state_log):
1610 If `a' isn't the LAST_NODE and `a' can't epsilon transit to
1611 the LAST_NODE, we throw away the node `a'.
1612 2. When 0 <= STR_IDX < MATCH_LAST and `a' accepts
1613 string `s' and transit to `b':
1614 i. If 'b' isn't in the STATE_LOG[STR_IDX+strlen('s')], we throw
1616 ii. If 'b' is in the STATE_LOG[STR_IDX+strlen('s')] but 'b' is
1617 thrown away, we throw away the node `a'.
1618 3. When 0 <= STR_IDX < MATCH_LAST and 'a' epsilon transit to 'b':
1619 i. If 'b' isn't in the STATE_LOG[STR_IDX], we throw away the
1621 ii. If 'b' is in the STATE_LOG[STR_IDX] but 'b' is thrown away,
1622 we throw away the node `a'. */
1624 #define STATE_NODE_CONTAINS(state,node) \
1625 ((state) != NULL && re_node_set_contains (&(state)->nodes, node))
1627 static reg_errcode_t
1629 sift_states_backward (const re_match_context_t *mctx, re_sift_context_t *sctx)
1633 Idx str_idx = sctx->last_str_idx;
1634 re_node_set cur_dest;
1637 assert (mctx->state_log != NULL && mctx->state_log[str_idx] != NULL);
1640 /* Build sifted state_log[str_idx]. It has the nodes which can epsilon
1641 transit to the last_node and the last_node itself. */
1642 err = re_node_set_init_1 (&cur_dest, sctx->last_node);
1643 if (BE (err != REG_NOERROR, 0))
1645 err = update_cur_sifted_state (mctx, sctx, str_idx, &cur_dest);
1646 if (BE (err != REG_NOERROR, 0))
1649 /* Then check each states in the state_log. */
1652 /* Update counters. */
1653 null_cnt = (sctx->sifted_states[str_idx] == NULL) ? null_cnt + 1 : 0;
1654 if (null_cnt > mctx->max_mb_elem_len)
1656 memset (sctx->sifted_states, '\0',
1657 sizeof (re_dfastate_t *) * str_idx);
1658 re_node_set_free (&cur_dest);
1661 re_node_set_empty (&cur_dest);
1664 if (mctx->state_log[str_idx])
1666 err = build_sifted_states (mctx, sctx, str_idx, &cur_dest);
1667 if (BE (err != REG_NOERROR, 0))
1671 /* Add all the nodes which satisfy the following conditions:
1672 - It can epsilon transit to a node in CUR_DEST.
1674 And update state_log. */
1675 err = update_cur_sifted_state (mctx, sctx, str_idx, &cur_dest);
1676 if (BE (err != REG_NOERROR, 0))
1681 re_node_set_free (&cur_dest);
1685 static reg_errcode_t
1687 build_sifted_states (const re_match_context_t *mctx, re_sift_context_t *sctx,
1688 Idx str_idx, re_node_set *cur_dest)
1690 const re_dfa_t *const dfa = mctx->dfa;
1691 const re_node_set *cur_src = &mctx->state_log[str_idx]->non_eps_nodes;
1694 /* Then build the next sifted state.
1695 We build the next sifted state on `cur_dest', and update
1696 `sifted_states[str_idx]' with `cur_dest'.
1698 `cur_dest' is the sifted state from `state_log[str_idx + 1]'.
1699 `cur_src' points the node_set of the old `state_log[str_idx]'
1700 (with the epsilon nodes pre-filtered out). */
1701 for (i = 0; i < cur_src->nelem; i++)
1703 Idx prev_node = cur_src->elems[i];
1708 re_token_type_t type = dfa->nodes[prev_node].type;
1709 assert (!IS_EPSILON_NODE (type));
1711 #ifdef RE_ENABLE_I18N
1712 /* If the node may accept `multi byte'. */
1713 if (dfa->nodes[prev_node].accept_mb)
1714 naccepted = sift_states_iter_mb (mctx, sctx, prev_node,
1715 str_idx, sctx->last_str_idx);
1716 #endif /* RE_ENABLE_I18N */
1718 /* We don't check backreferences here.
1719 See update_cur_sifted_state(). */
1721 && check_node_accept (mctx, dfa->nodes + prev_node, str_idx)
1722 && STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + 1],
1723 dfa->nexts[prev_node]))
1729 if (sctx->limits.nelem)
1731 Idx to_idx = str_idx + naccepted;
1732 if (check_dst_limits (mctx, &sctx->limits,
1733 dfa->nexts[prev_node], to_idx,
1734 prev_node, str_idx))
1737 ok = re_node_set_insert (cur_dest, prev_node);
1745 /* Helper functions. */
1747 static reg_errcode_t
1749 clean_state_log_if_needed (re_match_context_t *mctx, Idx next_state_log_idx)
1751 Idx top = mctx->state_log_top;
1753 if (next_state_log_idx >= mctx->input.bufs_len
1754 || (next_state_log_idx >= mctx->input.valid_len
1755 && mctx->input.valid_len < mctx->input.len))
1758 err = extend_buffers (mctx);
1759 if (BE (err != REG_NOERROR, 0))
1763 if (top < next_state_log_idx)
1765 memset (mctx->state_log + top + 1, '\0',
1766 sizeof (re_dfastate_t *) * (next_state_log_idx - top));
1767 mctx->state_log_top = next_state_log_idx;
1772 static reg_errcode_t
1774 merge_state_array (const re_dfa_t *dfa, re_dfastate_t **dst,
1775 re_dfastate_t **src, Idx num)
1779 for (st_idx = 0; st_idx < num; ++st_idx)
1781 if (dst[st_idx] == NULL)
1782 dst[st_idx] = src[st_idx];
1783 else if (src[st_idx] != NULL)
1785 re_node_set merged_set;
1786 err = re_node_set_init_union (&merged_set, &dst[st_idx]->nodes,
1787 &src[st_idx]->nodes);
1788 if (BE (err != REG_NOERROR, 0))
1790 dst[st_idx] = re_acquire_state (&err, dfa, &merged_set);
1791 re_node_set_free (&merged_set);
1792 if (BE (err != REG_NOERROR, 0))
1799 static reg_errcode_t
1801 update_cur_sifted_state (const re_match_context_t *mctx,
1802 re_sift_context_t *sctx, Idx str_idx,
1803 re_node_set *dest_nodes)
1805 const re_dfa_t *const dfa = mctx->dfa;
1806 reg_errcode_t err = REG_NOERROR;
1807 const re_node_set *candidates;
1808 candidates = ((mctx->state_log[str_idx] == NULL) ? NULL
1809 : &mctx->state_log[str_idx]->nodes);
1811 if (dest_nodes->nelem == 0)
1812 sctx->sifted_states[str_idx] = NULL;
1817 /* At first, add the nodes which can epsilon transit to a node in
1819 err = add_epsilon_src_nodes (dfa, dest_nodes, candidates);
1820 if (BE (err != REG_NOERROR, 0))
1823 /* Then, check the limitations in the current sift_context. */
1824 if (sctx->limits.nelem)
1826 err = check_subexp_limits (dfa, dest_nodes, candidates, &sctx->limits,
1827 mctx->bkref_ents, str_idx);
1828 if (BE (err != REG_NOERROR, 0))
1833 sctx->sifted_states[str_idx] = re_acquire_state (&err, dfa, dest_nodes);
1834 if (BE (err != REG_NOERROR, 0))
1838 if (candidates && mctx->state_log[str_idx]->has_backref)
1840 err = sift_states_bkref (mctx, sctx, str_idx, candidates);
1841 if (BE (err != REG_NOERROR, 0))
1847 static reg_errcode_t
1849 add_epsilon_src_nodes (const re_dfa_t *dfa, re_node_set *dest_nodes,
1850 const re_node_set *candidates)
1852 reg_errcode_t err = REG_NOERROR;
1855 re_dfastate_t *state = re_acquire_state (&err, dfa, dest_nodes);
1856 if (BE (err != REG_NOERROR, 0))
1859 if (!state->inveclosure.alloc)
1861 err = re_node_set_alloc (&state->inveclosure, dest_nodes->nelem);
1862 if (BE (err != REG_NOERROR, 0))
1864 for (i = 0; i < dest_nodes->nelem; i++)
1865 re_node_set_merge (&state->inveclosure,
1866 dfa->inveclosures + dest_nodes->elems[i]);
1868 return re_node_set_add_intersect (dest_nodes, candidates,
1869 &state->inveclosure);
1872 static reg_errcode_t
1874 sub_epsilon_src_nodes (const re_dfa_t *dfa, Idx node, re_node_set *dest_nodes,
1875 const re_node_set *candidates)
1879 re_node_set *inv_eclosure = dfa->inveclosures + node;
1880 re_node_set except_nodes;
1881 re_node_set_init_empty (&except_nodes);
1882 for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx)
1884 Idx cur_node = inv_eclosure->elems[ecl_idx];
1885 if (cur_node == node)
1887 if (IS_EPSILON_NODE (dfa->nodes[cur_node].type))
1889 Idx edst1 = dfa->edests[cur_node].elems[0];
1890 Idx edst2 = ((dfa->edests[cur_node].nelem > 1)
1891 ? dfa->edests[cur_node].elems[1] : REG_MISSING);
1892 if ((!re_node_set_contains (inv_eclosure, edst1)
1893 && re_node_set_contains (dest_nodes, edst1))
1894 || (REG_VALID_NONZERO_INDEX (edst2)
1895 && !re_node_set_contains (inv_eclosure, edst2)
1896 && re_node_set_contains (dest_nodes, edst2)))
1898 err = re_node_set_add_intersect (&except_nodes, candidates,
1899 dfa->inveclosures + cur_node);
1900 if (BE (err != REG_NOERROR, 0))
1902 re_node_set_free (&except_nodes);
1908 for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx)
1910 Idx cur_node = inv_eclosure->elems[ecl_idx];
1911 if (!re_node_set_contains (&except_nodes, cur_node))
1913 Idx idx = re_node_set_contains (dest_nodes, cur_node) - 1;
1914 re_node_set_remove_at (dest_nodes, idx);
1917 re_node_set_free (&except_nodes);
1923 check_dst_limits (const re_match_context_t *mctx, const re_node_set *limits,
1924 Idx dst_node, Idx dst_idx, Idx src_node, Idx src_idx)
1926 const re_dfa_t *const dfa = mctx->dfa;
1927 Idx lim_idx, src_pos, dst_pos;
1929 Idx dst_bkref_idx = search_cur_bkref_entry (mctx, dst_idx);
1930 Idx src_bkref_idx = search_cur_bkref_entry (mctx, src_idx);
1931 for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx)
1934 struct re_backref_cache_entry *ent;
1935 ent = mctx->bkref_ents + limits->elems[lim_idx];
1936 subexp_idx = dfa->nodes[ent->node].opr.idx;
1938 dst_pos = check_dst_limits_calc_pos (mctx, limits->elems[lim_idx],
1939 subexp_idx, dst_node, dst_idx,
1941 src_pos = check_dst_limits_calc_pos (mctx, limits->elems[lim_idx],
1942 subexp_idx, src_node, src_idx,
1946 <src> <dst> ( <subexp> )
1947 ( <subexp> ) <src> <dst>
1948 ( <subexp1> <src> <subexp2> <dst> <subexp3> ) */
1949 if (src_pos == dst_pos)
1950 continue; /* This is unrelated limitation. */
1959 check_dst_limits_calc_pos_1 (const re_match_context_t *mctx, int boundaries,
1960 Idx subexp_idx, Idx from_node, Idx bkref_idx)
1962 const re_dfa_t *const dfa = mctx->dfa;
1963 const re_node_set *eclosures = dfa->eclosures + from_node;
1966 /* Else, we are on the boundary: examine the nodes on the epsilon
1968 for (node_idx = 0; node_idx < eclosures->nelem; ++node_idx)
1970 Idx node = eclosures->elems[node_idx];
1971 switch (dfa->nodes[node].type)
1974 if (bkref_idx != REG_MISSING)
1976 struct re_backref_cache_entry *ent = mctx->bkref_ents + bkref_idx;
1982 if (ent->node != node)
1985 if (subexp_idx < BITSET_WORD_BITS
1986 && !(ent->eps_reachable_subexps_map
1987 & ((bitset_word_t) 1 << subexp_idx)))
1990 /* Recurse trying to reach the OP_OPEN_SUBEXP and
1991 OP_CLOSE_SUBEXP cases below. But, if the
1992 destination node is the same node as the source
1993 node, don't recurse because it would cause an
1994 infinite loop: a regex that exhibits this behavior
1996 dst = dfa->edests[node].elems[0];
1997 if (dst == from_node)
2001 else /* if (boundaries & 2) */
2006 check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx,
2008 if (cpos == -1 /* && (boundaries & 1) */)
2010 if (cpos == 0 && (boundaries & 2))
2013 if (subexp_idx < BITSET_WORD_BITS)
2014 ent->eps_reachable_subexps_map
2015 &= ~((bitset_word_t) 1 << subexp_idx);
2017 while (ent++->more);
2021 case OP_OPEN_SUBEXP:
2022 if ((boundaries & 1) && subexp_idx == dfa->nodes[node].opr.idx)
2026 case OP_CLOSE_SUBEXP:
2027 if ((boundaries & 2) && subexp_idx == dfa->nodes[node].opr.idx)
2036 return (boundaries & 2) ? 1 : 0;
2041 check_dst_limits_calc_pos (const re_match_context_t *mctx, Idx limit,
2042 Idx subexp_idx, Idx from_node, Idx str_idx,
2045 struct re_backref_cache_entry *lim = mctx->bkref_ents + limit;
2048 /* If we are outside the range of the subexpression, return -1 or 1. */
2049 if (str_idx < lim->subexp_from)
2052 if (lim->subexp_to < str_idx)
2055 /* If we are within the subexpression, return 0. */
2056 boundaries = (str_idx == lim->subexp_from);
2057 boundaries |= (str_idx == lim->subexp_to) << 1;
2058 if (boundaries == 0)
2061 /* Else, examine epsilon closure. */
2062 return check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx,
2063 from_node, bkref_idx);
2066 /* Check the limitations of sub expressions LIMITS, and remove the nodes
2067 which are against limitations from DEST_NODES. */
2069 static reg_errcode_t
2071 check_subexp_limits (const re_dfa_t *dfa, re_node_set *dest_nodes,
2072 const re_node_set *candidates, re_node_set *limits,
2073 struct re_backref_cache_entry *bkref_ents, Idx str_idx)
2076 Idx node_idx, lim_idx;
2078 for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx)
2081 struct re_backref_cache_entry *ent;
2082 ent = bkref_ents + limits->elems[lim_idx];
2084 if (str_idx <= ent->subexp_from || ent->str_idx < str_idx)
2085 continue; /* This is unrelated limitation. */
2087 subexp_idx = dfa->nodes[ent->node].opr.idx;
2088 if (ent->subexp_to == str_idx)
2090 Idx ops_node = REG_MISSING;
2091 Idx cls_node = REG_MISSING;
2092 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2094 Idx node = dest_nodes->elems[node_idx];
2095 re_token_type_t type = dfa->nodes[node].type;
2096 if (type == OP_OPEN_SUBEXP
2097 && subexp_idx == dfa->nodes[node].opr.idx)
2099 else if (type == OP_CLOSE_SUBEXP
2100 && subexp_idx == dfa->nodes[node].opr.idx)
2104 /* Check the limitation of the open subexpression. */
2105 /* Note that (ent->subexp_to = str_idx != ent->subexp_from). */
2106 if (REG_VALID_INDEX (ops_node))
2108 err = sub_epsilon_src_nodes (dfa, ops_node, dest_nodes,
2110 if (BE (err != REG_NOERROR, 0))
2114 /* Check the limitation of the close subexpression. */
2115 if (REG_VALID_INDEX (cls_node))
2116 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2118 Idx node = dest_nodes->elems[node_idx];
2119 if (!re_node_set_contains (dfa->inveclosures + node,
2121 && !re_node_set_contains (dfa->eclosures + node,
2124 /* It is against this limitation.
2125 Remove it form the current sifted state. */
2126 err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2128 if (BE (err != REG_NOERROR, 0))
2134 else /* (ent->subexp_to != str_idx) */
2136 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2138 Idx node = dest_nodes->elems[node_idx];
2139 re_token_type_t type = dfa->nodes[node].type;
2140 if (type == OP_CLOSE_SUBEXP || type == OP_OPEN_SUBEXP)
2142 if (subexp_idx != dfa->nodes[node].opr.idx)
2144 /* It is against this limitation.
2145 Remove it form the current sifted state. */
2146 err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2148 if (BE (err != REG_NOERROR, 0))
2157 static reg_errcode_t
2159 sift_states_bkref (const re_match_context_t *mctx, re_sift_context_t *sctx,
2160 Idx str_idx, const re_node_set *candidates)
2162 const re_dfa_t *const dfa = mctx->dfa;
2165 re_sift_context_t local_sctx;
2166 Idx first_idx = search_cur_bkref_entry (mctx, str_idx);
2168 if (first_idx == REG_MISSING)
2171 local_sctx.sifted_states = NULL; /* Mark that it hasn't been initialized. */
2173 for (node_idx = 0; node_idx < candidates->nelem; ++node_idx)
2176 re_token_type_t type;
2177 struct re_backref_cache_entry *entry;
2178 node = candidates->elems[node_idx];
2179 type = dfa->nodes[node].type;
2180 /* Avoid infinite loop for the REs like "()\1+". */
2181 if (node == sctx->last_node && str_idx == sctx->last_str_idx)
2183 if (type != OP_BACK_REF)
2186 entry = mctx->bkref_ents + first_idx;
2187 enabled_idx = first_idx;
2194 re_dfastate_t *cur_state;
2196 if (entry->node != node)
2198 subexp_len = entry->subexp_to - entry->subexp_from;
2199 to_idx = str_idx + subexp_len;
2200 dst_node = (subexp_len ? dfa->nexts[node]
2201 : dfa->edests[node].elems[0]);
2203 if (to_idx > sctx->last_str_idx
2204 || sctx->sifted_states[to_idx] == NULL
2205 || !STATE_NODE_CONTAINS (sctx->sifted_states[to_idx], dst_node)
2206 || check_dst_limits (mctx, &sctx->limits, node,
2207 str_idx, dst_node, to_idx))
2210 if (local_sctx.sifted_states == NULL)
2213 err = re_node_set_init_copy (&local_sctx.limits, &sctx->limits);
2214 if (BE (err != REG_NOERROR, 0))
2217 local_sctx.last_node = node;
2218 local_sctx.last_str_idx = str_idx;
2219 ok = re_node_set_insert (&local_sctx.limits, enabled_idx);
2225 cur_state = local_sctx.sifted_states[str_idx];
2226 err = sift_states_backward (mctx, &local_sctx);
2227 if (BE (err != REG_NOERROR, 0))
2229 if (sctx->limited_states != NULL)
2231 err = merge_state_array (dfa, sctx->limited_states,
2232 local_sctx.sifted_states,
2234 if (BE (err != REG_NOERROR, 0))
2237 local_sctx.sifted_states[str_idx] = cur_state;
2238 re_node_set_remove (&local_sctx.limits, enabled_idx);
2240 /* mctx->bkref_ents may have changed, reload the pointer. */
2241 entry = mctx->bkref_ents + enabled_idx;
2243 while (enabled_idx++, entry++->more);
2247 if (local_sctx.sifted_states != NULL)
2249 re_node_set_free (&local_sctx.limits);
2256 #ifdef RE_ENABLE_I18N
2259 sift_states_iter_mb (const re_match_context_t *mctx, re_sift_context_t *sctx,
2260 Idx node_idx, Idx str_idx, Idx max_str_idx)
2262 const re_dfa_t *const dfa = mctx->dfa;
2264 /* Check the node can accept `multi byte'. */
2265 naccepted = check_node_accept_bytes (dfa, node_idx, &mctx->input, str_idx);
2266 if (naccepted > 0 && str_idx + naccepted <= max_str_idx &&
2267 !STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + naccepted],
2268 dfa->nexts[node_idx]))
2269 /* The node can't accept the `multi byte', or the
2270 destination was already thrown away, then the node
2271 could't accept the current input `multi byte'. */
2273 /* Otherwise, it is sure that the node could accept
2274 `naccepted' bytes input. */
2277 #endif /* RE_ENABLE_I18N */
2280 /* Functions for state transition. */
2282 /* Return the next state to which the current state STATE will transit by
2283 accepting the current input byte, and update STATE_LOG if necessary.
2284 If STATE can accept a multibyte char/collating element/back reference
2285 update the destination of STATE_LOG. */
2287 static re_dfastate_t *
2289 transit_state (reg_errcode_t *err, re_match_context_t *mctx,
2290 re_dfastate_t *state)
2292 re_dfastate_t **trtable;
2295 #ifdef RE_ENABLE_I18N
2296 /* If the current state can accept multibyte. */
2297 if (BE (state->accept_mb, 0))
2299 *err = transit_state_mb (mctx, state);
2300 if (BE (*err != REG_NOERROR, 0))
2303 #endif /* RE_ENABLE_I18N */
2305 /* Then decide the next state with the single byte. */
2308 /* don't use transition table */
2309 return transit_state_sb (err, mctx, state);
2312 /* Use transition table */
2313 ch = re_string_fetch_byte (&mctx->input);
2316 trtable = state->trtable;
2317 if (BE (trtable != NULL, 1))
2320 trtable = state->word_trtable;
2321 if (BE (trtable != NULL, 1))
2323 unsigned int context;
2325 = re_string_context_at (&mctx->input,
2326 re_string_cur_idx (&mctx->input) - 1,
2328 if (IS_WORD_CONTEXT (context))
2329 return trtable[ch + SBC_MAX];
2334 if (!build_trtable (mctx->dfa, state))
2340 /* Retry, we now have a transition table. */
2344 /* Update the state_log if we need */
2345 static re_dfastate_t *
2347 merge_state_with_log (reg_errcode_t *err, re_match_context_t *mctx,
2348 re_dfastate_t *next_state)
2350 const re_dfa_t *const dfa = mctx->dfa;
2351 Idx cur_idx = re_string_cur_idx (&mctx->input);
2353 if (cur_idx > mctx->state_log_top)
2355 mctx->state_log[cur_idx] = next_state;
2356 mctx->state_log_top = cur_idx;
2358 else if (mctx->state_log[cur_idx] == 0)
2360 mctx->state_log[cur_idx] = next_state;
2364 re_dfastate_t *pstate;
2365 unsigned int context;
2366 re_node_set next_nodes, *log_nodes, *table_nodes = NULL;
2367 /* If (state_log[cur_idx] != 0), it implies that cur_idx is
2368 the destination of a multibyte char/collating element/
2369 back reference. Then the next state is the union set of
2370 these destinations and the results of the transition table. */
2371 pstate = mctx->state_log[cur_idx];
2372 log_nodes = pstate->entrance_nodes;
2373 if (next_state != NULL)
2375 table_nodes = next_state->entrance_nodes;
2376 *err = re_node_set_init_union (&next_nodes, table_nodes,
2378 if (BE (*err != REG_NOERROR, 0))
2382 next_nodes = *log_nodes;
2383 /* Note: We already add the nodes of the initial state,
2384 then we don't need to add them here. */
2386 context = re_string_context_at (&mctx->input,
2387 re_string_cur_idx (&mctx->input) - 1,
2389 next_state = mctx->state_log[cur_idx]
2390 = re_acquire_state_context (err, dfa, &next_nodes, context);
2391 /* We don't need to check errors here, since the return value of
2392 this function is next_state and ERR is already set. */
2394 if (table_nodes != NULL)
2395 re_node_set_free (&next_nodes);
2398 if (BE (dfa->nbackref, 0) && next_state != NULL)
2400 /* Check OP_OPEN_SUBEXP in the current state in case that we use them
2401 later. We must check them here, since the back references in the
2402 next state might use them. */
2403 *err = check_subexp_matching_top (mctx, &next_state->nodes,
2405 if (BE (*err != REG_NOERROR, 0))
2408 /* If the next state has back references. */
2409 if (next_state->has_backref)
2411 *err = transit_state_bkref (mctx, &next_state->nodes);
2412 if (BE (*err != REG_NOERROR, 0))
2414 next_state = mctx->state_log[cur_idx];
2421 /* Skip bytes in the input that correspond to part of a
2422 multi-byte match, then look in the log for a state
2423 from which to restart matching. */
2424 static re_dfastate_t *
2426 find_recover_state (reg_errcode_t *err, re_match_context_t *mctx)
2428 re_dfastate_t *cur_state;
2431 Idx max = mctx->state_log_top;
2432 Idx cur_str_idx = re_string_cur_idx (&mctx->input);
2436 if (++cur_str_idx > max)
2438 re_string_skip_bytes (&mctx->input, 1);
2440 while (mctx->state_log[cur_str_idx] == NULL);
2442 cur_state = merge_state_with_log (err, mctx, NULL);
2444 while (*err == REG_NOERROR && cur_state == NULL);
2448 /* Helper functions for transit_state. */
2450 /* From the node set CUR_NODES, pick up the nodes whose types are
2451 OP_OPEN_SUBEXP and which have corresponding back references in the regular
2452 expression. And register them to use them later for evaluating the
2453 correspoding back references. */
2455 static reg_errcode_t
2457 check_subexp_matching_top (re_match_context_t *mctx, re_node_set *cur_nodes,
2460 const re_dfa_t *const dfa = mctx->dfa;
2464 /* TODO: This isn't efficient.
2465 Because there might be more than one nodes whose types are
2466 OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
2469 for (node_idx = 0; node_idx < cur_nodes->nelem; ++node_idx)
2471 Idx node = cur_nodes->elems[node_idx];
2472 if (dfa->nodes[node].type == OP_OPEN_SUBEXP
2473 && dfa->nodes[node].opr.idx < BITSET_WORD_BITS
2474 && (dfa->used_bkref_map
2475 & ((bitset_word_t) 1 << dfa->nodes[node].opr.idx)))
2477 err = match_ctx_add_subtop (mctx, node, str_idx);
2478 if (BE (err != REG_NOERROR, 0))
2486 /* Return the next state to which the current state STATE will transit by
2487 accepting the current input byte. */
2489 static re_dfastate_t *
2490 transit_state_sb (reg_errcode_t *err, re_match_context_t *mctx,
2491 re_dfastate_t *state)
2493 const re_dfa_t *const dfa = mctx->dfa;
2494 re_node_set next_nodes;
2495 re_dfastate_t *next_state;
2496 Idx node_cnt, cur_str_idx = re_string_cur_idx (&mctx->input);
2497 unsigned int context;
2499 *err = re_node_set_alloc (&next_nodes, state->nodes.nelem + 1);
2500 if (BE (*err != REG_NOERROR, 0))
2502 for (node_cnt = 0; node_cnt < state->nodes.nelem; ++node_cnt)
2504 Idx cur_node = state->nodes.elems[node_cnt];
2505 if (check_node_accept (mctx, dfa->nodes + cur_node, cur_str_idx))
2507 *err = re_node_set_merge (&next_nodes,
2508 dfa->eclosures + dfa->nexts[cur_node]);
2509 if (BE (*err != REG_NOERROR, 0))
2511 re_node_set_free (&next_nodes);
2516 context = re_string_context_at (&mctx->input, cur_str_idx, mctx->eflags);
2517 next_state = re_acquire_state_context (err, dfa, &next_nodes, context);
2518 /* We don't need to check errors here, since the return value of
2519 this function is next_state and ERR is already set. */
2521 re_node_set_free (&next_nodes);
2522 re_string_skip_bytes (&mctx->input, 1);
2527 #ifdef RE_ENABLE_I18N
2528 static reg_errcode_t
2530 transit_state_mb (re_match_context_t *mctx, re_dfastate_t *pstate)
2532 const re_dfa_t *const dfa = mctx->dfa;
2536 for (i = 0; i < pstate->nodes.nelem; ++i)
2538 re_node_set dest_nodes, *new_nodes;
2539 Idx cur_node_idx = pstate->nodes.elems[i];
2542 unsigned int context;
2543 re_dfastate_t *dest_state;
2545 if (!dfa->nodes[cur_node_idx].accept_mb)
2548 if (dfa->nodes[cur_node_idx].constraint)
2550 context = re_string_context_at (&mctx->input,
2551 re_string_cur_idx (&mctx->input),
2553 if (NOT_SATISFY_NEXT_CONSTRAINT (dfa->nodes[cur_node_idx].constraint,
2558 /* How many bytes the node can accept? */
2559 naccepted = check_node_accept_bytes (dfa, cur_node_idx, &mctx->input,
2560 re_string_cur_idx (&mctx->input));
2564 /* The node can accepts `naccepted' bytes. */
2565 dest_idx = re_string_cur_idx (&mctx->input) + naccepted;
2566 mctx->max_mb_elem_len = ((mctx->max_mb_elem_len < naccepted) ? naccepted
2567 : mctx->max_mb_elem_len);
2568 err = clean_state_log_if_needed (mctx, dest_idx);
2569 if (BE (err != REG_NOERROR, 0))
2572 assert (dfa->nexts[cur_node_idx] != REG_MISSING);
2574 new_nodes = dfa->eclosures + dfa->nexts[cur_node_idx];
2576 dest_state = mctx->state_log[dest_idx];
2577 if (dest_state == NULL)
2578 dest_nodes = *new_nodes;
2581 err = re_node_set_init_union (&dest_nodes,
2582 dest_state->entrance_nodes, new_nodes);
2583 if (BE (err != REG_NOERROR, 0))
2586 context = re_string_context_at (&mctx->input, dest_idx - 1,
2588 mctx->state_log[dest_idx]
2589 = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2590 if (dest_state != NULL)
2591 re_node_set_free (&dest_nodes);
2592 if (BE (mctx->state_log[dest_idx] == NULL && err != REG_NOERROR, 0))
2597 #endif /* RE_ENABLE_I18N */
2599 static reg_errcode_t
2601 transit_state_bkref (re_match_context_t *mctx, const re_node_set *nodes)
2603 const re_dfa_t *const dfa = mctx->dfa;
2606 Idx cur_str_idx = re_string_cur_idx (&mctx->input);
2608 for (i = 0; i < nodes->nelem; ++i)
2610 Idx dest_str_idx, prev_nelem, bkc_idx;
2611 Idx node_idx = nodes->elems[i];
2612 unsigned int context;
2613 const re_token_t *node = dfa->nodes + node_idx;
2614 re_node_set *new_dest_nodes;
2616 /* Check whether `node' is a backreference or not. */
2617 if (node->type != OP_BACK_REF)
2620 if (node->constraint)
2622 context = re_string_context_at (&mctx->input, cur_str_idx,
2624 if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
2628 /* `node' is a backreference.
2629 Check the substring which the substring matched. */
2630 bkc_idx = mctx->nbkref_ents;
2631 err = get_subexp (mctx, node_idx, cur_str_idx);
2632 if (BE (err != REG_NOERROR, 0))
2635 /* And add the epsilon closures (which is `new_dest_nodes') of
2636 the backreference to appropriate state_log. */
2638 assert (dfa->nexts[node_idx] != REG_MISSING);
2640 for (; bkc_idx < mctx->nbkref_ents; ++bkc_idx)
2643 re_dfastate_t *dest_state;
2644 struct re_backref_cache_entry *bkref_ent;
2645 bkref_ent = mctx->bkref_ents + bkc_idx;
2646 if (bkref_ent->node != node_idx || bkref_ent->str_idx != cur_str_idx)
2648 subexp_len = bkref_ent->subexp_to - bkref_ent->subexp_from;
2649 new_dest_nodes = (subexp_len == 0
2650 ? dfa->eclosures + dfa->edests[node_idx].elems[0]
2651 : dfa->eclosures + dfa->nexts[node_idx]);
2652 dest_str_idx = (cur_str_idx + bkref_ent->subexp_to
2653 - bkref_ent->subexp_from);
2654 context = re_string_context_at (&mctx->input, dest_str_idx - 1,
2656 dest_state = mctx->state_log[dest_str_idx];
2657 prev_nelem = ((mctx->state_log[cur_str_idx] == NULL) ? 0
2658 : mctx->state_log[cur_str_idx]->nodes.nelem);
2659 /* Add `new_dest_node' to state_log. */
2660 if (dest_state == NULL)
2662 mctx->state_log[dest_str_idx]
2663 = re_acquire_state_context (&err, dfa, new_dest_nodes,
2665 if (BE (mctx->state_log[dest_str_idx] == NULL
2666 && err != REG_NOERROR, 0))
2671 re_node_set dest_nodes;
2672 err = re_node_set_init_union (&dest_nodes,
2673 dest_state->entrance_nodes,
2675 if (BE (err != REG_NOERROR, 0))
2677 re_node_set_free (&dest_nodes);
2680 mctx->state_log[dest_str_idx]
2681 = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2682 re_node_set_free (&dest_nodes);
2683 if (BE (mctx->state_log[dest_str_idx] == NULL
2684 && err != REG_NOERROR, 0))
2687 /* We need to check recursively if the backreference can epsilon
2690 && mctx->state_log[cur_str_idx]->nodes.nelem > prev_nelem)
2692 err = check_subexp_matching_top (mctx, new_dest_nodes,
2694 if (BE (err != REG_NOERROR, 0))
2696 err = transit_state_bkref (mctx, new_dest_nodes);
2697 if (BE (err != REG_NOERROR, 0))
2707 /* Enumerate all the candidates which the backreference BKREF_NODE can match
2708 at BKREF_STR_IDX, and register them by match_ctx_add_entry().
2709 Note that we might collect inappropriate candidates here.
2710 However, the cost of checking them strictly here is too high, then we
2711 delay these checking for prune_impossible_nodes(). */
2713 static reg_errcode_t
2715 get_subexp (re_match_context_t *mctx, Idx bkref_node, Idx bkref_str_idx)
2717 const re_dfa_t *const dfa = mctx->dfa;
2718 Idx subexp_num, sub_top_idx;
2719 const char *buf = (const char *) re_string_get_buffer (&mctx->input);
2720 /* Return if we have already checked BKREF_NODE at BKREF_STR_IDX. */
2721 Idx cache_idx = search_cur_bkref_entry (mctx, bkref_str_idx);
2722 if (cache_idx != REG_MISSING)
2724 const struct re_backref_cache_entry *entry
2725 = mctx->bkref_ents + cache_idx;
2727 if (entry->node == bkref_node)
2728 return REG_NOERROR; /* We already checked it. */
2729 while (entry++->more);
2732 subexp_num = dfa->nodes[bkref_node].opr.idx;
2734 /* For each sub expression */
2735 for (sub_top_idx = 0; sub_top_idx < mctx->nsub_tops; ++sub_top_idx)
2738 re_sub_match_top_t *sub_top = mctx->sub_tops[sub_top_idx];
2739 re_sub_match_last_t *sub_last;
2740 Idx sub_last_idx, sl_str, bkref_str_off;
2742 if (dfa->nodes[sub_top->node].opr.idx != subexp_num)
2743 continue; /* It isn't related. */
2745 sl_str = sub_top->str_idx;
2746 bkref_str_off = bkref_str_idx;
2747 /* At first, check the last node of sub expressions we already
2749 for (sub_last_idx = 0; sub_last_idx < sub_top->nlasts; ++sub_last_idx)
2751 regoff_t sl_str_diff;
2752 sub_last = sub_top->lasts[sub_last_idx];
2753 sl_str_diff = sub_last->str_idx - sl_str;
2754 /* The matched string by the sub expression match with the substring
2755 at the back reference? */
2756 if (sl_str_diff > 0)
2758 if (BE (bkref_str_off + sl_str_diff > mctx->input.valid_len, 0))
2760 /* Not enough chars for a successful match. */
2761 if (bkref_str_off + sl_str_diff > mctx->input.len)
2764 err = clean_state_log_if_needed (mctx,
2767 if (BE (err != REG_NOERROR, 0))
2769 buf = (const char *) re_string_get_buffer (&mctx->input);
2771 if (memcmp (buf + bkref_str_off, buf + sl_str, sl_str_diff) != 0)
2772 /* We don't need to search this sub expression any more. */
2775 bkref_str_off += sl_str_diff;
2776 sl_str += sl_str_diff;
2777 err = get_subexp_sub (mctx, sub_top, sub_last, bkref_node,
2780 /* Reload buf, since the preceding call might have reallocated
2782 buf = (const char *) re_string_get_buffer (&mctx->input);
2784 if (err == REG_NOMATCH)
2786 if (BE (err != REG_NOERROR, 0))
2790 if (sub_last_idx < sub_top->nlasts)
2792 if (sub_last_idx > 0)
2794 /* Then, search for the other last nodes of the sub expression. */
2795 for (; sl_str <= bkref_str_idx; ++sl_str)
2798 regoff_t sl_str_off;
2799 const re_node_set *nodes;
2800 sl_str_off = sl_str - sub_top->str_idx;
2801 /* The matched string by the sub expression match with the substring
2802 at the back reference? */
2805 if (BE (bkref_str_off >= mctx->input.valid_len, 0))
2807 /* If we are at the end of the input, we cannot match. */
2808 if (bkref_str_off >= mctx->input.len)
2811 err = extend_buffers (mctx);
2812 if (BE (err != REG_NOERROR, 0))
2815 buf = (const char *) re_string_get_buffer (&mctx->input);
2817 if (buf [bkref_str_off++] != buf[sl_str - 1])
2818 break; /* We don't need to search this sub expression
2821 if (mctx->state_log[sl_str] == NULL)
2823 /* Does this state have a ')' of the sub expression? */
2824 nodes = &mctx->state_log[sl_str]->nodes;
2825 cls_node = find_subexp_node (dfa, nodes, subexp_num,
2827 if (cls_node == REG_MISSING)
2829 if (sub_top->path == NULL)
2831 sub_top->path = calloc (sizeof (state_array_t),
2832 sl_str - sub_top->str_idx + 1);
2833 if (sub_top->path == NULL)
2836 /* Can the OP_OPEN_SUBEXP node arrive the OP_CLOSE_SUBEXP node
2837 in the current context? */
2838 err = check_arrival (mctx, sub_top->path, sub_top->node,
2839 sub_top->str_idx, cls_node, sl_str,
2841 if (err == REG_NOMATCH)
2843 if (BE (err != REG_NOERROR, 0))
2845 sub_last = match_ctx_add_sublast (sub_top, cls_node, sl_str);
2846 if (BE (sub_last == NULL, 0))
2848 err = get_subexp_sub (mctx, sub_top, sub_last, bkref_node,
2850 if (err == REG_NOMATCH)
2857 /* Helper functions for get_subexp(). */
2859 /* Check SUB_LAST can arrive to the back reference BKREF_NODE at BKREF_STR.
2860 If it can arrive, register the sub expression expressed with SUB_TOP
2863 static reg_errcode_t
2865 get_subexp_sub (re_match_context_t *mctx, const re_sub_match_top_t *sub_top,
2866 re_sub_match_last_t *sub_last, Idx bkref_node, Idx bkref_str)
2870 /* Can the subexpression arrive the back reference? */
2871 err = check_arrival (mctx, &sub_last->path, sub_last->node,
2872 sub_last->str_idx, bkref_node, bkref_str,
2874 if (err != REG_NOERROR)
2876 err = match_ctx_add_entry (mctx, bkref_node, bkref_str, sub_top->str_idx,
2878 if (BE (err != REG_NOERROR, 0))
2880 to_idx = bkref_str + sub_last->str_idx - sub_top->str_idx;
2881 return clean_state_log_if_needed (mctx, to_idx);
2884 /* Find the first node which is '(' or ')' and whose index is SUBEXP_IDX.
2885 Search '(' if FL_OPEN, or search ')' otherwise.
2886 TODO: This function isn't efficient...
2887 Because there might be more than one nodes whose types are
2888 OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
2894 find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
2895 Idx subexp_idx, int type)
2898 for (cls_idx = 0; cls_idx < nodes->nelem; ++cls_idx)
2900 Idx cls_node = nodes->elems[cls_idx];
2901 const re_token_t *node = dfa->nodes + cls_node;
2902 if (node->type == type
2903 && node->opr.idx == subexp_idx)
2909 /* Check whether the node TOP_NODE at TOP_STR can arrive to the node
2910 LAST_NODE at LAST_STR. We record the path onto PATH since it will be
2912 Return REG_NOERROR if it can arrive, or REG_NOMATCH otherwise. */
2914 static reg_errcode_t
2916 check_arrival (re_match_context_t *mctx, state_array_t *path, Idx top_node,
2917 Idx top_str, Idx last_node, Idx last_str, int type)
2919 const re_dfa_t *const dfa = mctx->dfa;
2920 reg_errcode_t err = REG_NOERROR;
2921 Idx subexp_num, backup_cur_idx, str_idx, null_cnt;
2922 re_dfastate_t *cur_state = NULL;
2923 re_node_set *cur_nodes, next_nodes;
2924 re_dfastate_t **backup_state_log;
2925 unsigned int context;
2927 subexp_num = dfa->nodes[top_node].opr.idx;
2928 /* Extend the buffer if we need. */
2929 if (BE (path->alloc < last_str + mctx->max_mb_elem_len + 1, 0))
2931 re_dfastate_t **new_array;
2932 Idx old_alloc = path->alloc;
2933 Idx new_alloc = old_alloc + last_str + mctx->max_mb_elem_len + 1;
2934 if (BE (new_alloc < old_alloc, 0)
2935 || BE (SIZE_MAX / sizeof (re_dfastate_t *) < new_alloc, 0))
2937 new_array = re_realloc (path->array, re_dfastate_t *, new_alloc);
2938 if (BE (new_array == NULL, 0))
2940 path->array = new_array;
2941 path->alloc = new_alloc;
2942 memset (new_array + old_alloc, '\0',
2943 sizeof (re_dfastate_t *) * (path->alloc - old_alloc));
2946 str_idx = path->next_idx ? path->next_idx : top_str;
2948 /* Temporary modify MCTX. */
2949 backup_state_log = mctx->state_log;
2950 backup_cur_idx = mctx->input.cur_idx;
2951 mctx->state_log = path->array;
2952 mctx->input.cur_idx = str_idx;
2954 /* Setup initial node set. */
2955 context = re_string_context_at (&mctx->input, str_idx - 1, mctx->eflags);
2956 if (str_idx == top_str)
2958 err = re_node_set_init_1 (&next_nodes, top_node);
2959 if (BE (err != REG_NOERROR, 0))
2961 err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
2962 if (BE (err != REG_NOERROR, 0))
2964 re_node_set_free (&next_nodes);
2970 cur_state = mctx->state_log[str_idx];
2971 if (cur_state && cur_state->has_backref)
2973 err = re_node_set_init_copy (&next_nodes, &cur_state->nodes);
2974 if (BE (err != REG_NOERROR, 0))
2978 re_node_set_init_empty (&next_nodes);
2980 if (str_idx == top_str || (cur_state && cur_state->has_backref))
2982 if (next_nodes.nelem)
2984 err = expand_bkref_cache (mctx, &next_nodes, str_idx,
2986 if (BE (err != REG_NOERROR, 0))
2988 re_node_set_free (&next_nodes);
2992 cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
2993 if (BE (cur_state == NULL && err != REG_NOERROR, 0))
2995 re_node_set_free (&next_nodes);
2998 mctx->state_log[str_idx] = cur_state;
3001 for (null_cnt = 0; str_idx < last_str && null_cnt <= mctx->max_mb_elem_len;)
3003 re_node_set_empty (&next_nodes);
3004 if (mctx->state_log[str_idx + 1])
3006 err = re_node_set_merge (&next_nodes,
3007 &mctx->state_log[str_idx + 1]->nodes);
3008 if (BE (err != REG_NOERROR, 0))
3010 re_node_set_free (&next_nodes);
3016 err = check_arrival_add_next_nodes (mctx, str_idx,
3017 &cur_state->non_eps_nodes,
3019 if (BE (err != REG_NOERROR, 0))
3021 re_node_set_free (&next_nodes);
3026 if (next_nodes.nelem)
3028 err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
3029 if (BE (err != REG_NOERROR, 0))
3031 re_node_set_free (&next_nodes);
3034 err = expand_bkref_cache (mctx, &next_nodes, str_idx,
3036 if (BE (err != REG_NOERROR, 0))
3038 re_node_set_free (&next_nodes);
3042 context = re_string_context_at (&mctx->input, str_idx - 1, mctx->eflags);
3043 cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
3044 if (BE (cur_state == NULL && err != REG_NOERROR, 0))
3046 re_node_set_free (&next_nodes);
3049 mctx->state_log[str_idx] = cur_state;
3050 null_cnt = cur_state == NULL ? null_cnt + 1 : 0;
3052 re_node_set_free (&next_nodes);
3053 cur_nodes = (mctx->state_log[last_str] == NULL ? NULL
3054 : &mctx->state_log[last_str]->nodes);
3055 path->next_idx = str_idx;
3058 mctx->state_log = backup_state_log;
3059 mctx->input.cur_idx = backup_cur_idx;
3061 /* Then check the current node set has the node LAST_NODE. */
3062 if (cur_nodes != NULL && re_node_set_contains (cur_nodes, last_node))
3068 /* Helper functions for check_arrival. */
3070 /* Calculate the destination nodes of CUR_NODES at STR_IDX, and append them
3072 TODO: This function is similar to the functions transit_state*(),
3073 however this function has many additional works.
3074 Can't we unify them? */
3076 static reg_errcode_t
3078 check_arrival_add_next_nodes (re_match_context_t *mctx, Idx str_idx,
3079 re_node_set *cur_nodes, re_node_set *next_nodes)
3081 const re_dfa_t *const dfa = mctx->dfa;
3084 reg_errcode_t err = REG_NOERROR;
3085 re_node_set union_set;
3086 re_node_set_init_empty (&union_set);
3087 for (cur_idx = 0; cur_idx < cur_nodes->nelem; ++cur_idx)
3090 Idx cur_node = cur_nodes->elems[cur_idx];
3092 re_token_type_t type = dfa->nodes[cur_node].type;
3093 assert (!IS_EPSILON_NODE (type));
3095 #ifdef RE_ENABLE_I18N
3096 /* If the node may accept `multi byte'. */
3097 if (dfa->nodes[cur_node].accept_mb)
3099 naccepted = check_node_accept_bytes (dfa, cur_node, &mctx->input,
3103 re_dfastate_t *dest_state;
3104 Idx next_node = dfa->nexts[cur_node];
3105 Idx next_idx = str_idx + naccepted;
3106 dest_state = mctx->state_log[next_idx];
3107 re_node_set_empty (&union_set);
3110 err = re_node_set_merge (&union_set, &dest_state->nodes);
3111 if (BE (err != REG_NOERROR, 0))
3113 re_node_set_free (&union_set);
3117 ok = re_node_set_insert (&union_set, next_node);
3120 re_node_set_free (&union_set);
3123 mctx->state_log[next_idx] = re_acquire_state (&err, dfa,
3125 if (BE (mctx->state_log[next_idx] == NULL
3126 && err != REG_NOERROR, 0))
3128 re_node_set_free (&union_set);
3133 #endif /* RE_ENABLE_I18N */
3135 || check_node_accept (mctx, dfa->nodes + cur_node, str_idx))
3137 ok = re_node_set_insert (next_nodes, dfa->nexts[cur_node]);
3140 re_node_set_free (&union_set);
3145 re_node_set_free (&union_set);
3149 /* For all the nodes in CUR_NODES, add the epsilon closures of them to
3150 CUR_NODES, however exclude the nodes which are:
3151 - inside the sub expression whose number is EX_SUBEXP, if FL_OPEN.
3152 - out of the sub expression whose number is EX_SUBEXP, if !FL_OPEN.
3155 static reg_errcode_t
3157 check_arrival_expand_ecl (const re_dfa_t *dfa, re_node_set *cur_nodes,
3158 Idx ex_subexp, int type)
3161 Idx idx, outside_node;
3162 re_node_set new_nodes;
3164 assert (cur_nodes->nelem);
3166 err = re_node_set_alloc (&new_nodes, cur_nodes->nelem);
3167 if (BE (err != REG_NOERROR, 0))
3169 /* Create a new node set NEW_NODES with the nodes which are epsilon
3170 closures of the node in CUR_NODES. */
3172 for (idx = 0; idx < cur_nodes->nelem; ++idx)
3174 Idx cur_node = cur_nodes->elems[idx];
3175 const re_node_set *eclosure = dfa->eclosures + cur_node;
3176 outside_node = find_subexp_node (dfa, eclosure, ex_subexp, type);
3177 if (outside_node == REG_MISSING)
3179 /* There are no problematic nodes, just merge them. */
3180 err = re_node_set_merge (&new_nodes, eclosure);
3181 if (BE (err != REG_NOERROR, 0))
3183 re_node_set_free (&new_nodes);
3189 /* There are problematic nodes, re-calculate incrementally. */
3190 err = check_arrival_expand_ecl_sub (dfa, &new_nodes, cur_node,
3192 if (BE (err != REG_NOERROR, 0))
3194 re_node_set_free (&new_nodes);
3199 re_node_set_free (cur_nodes);
3200 *cur_nodes = new_nodes;
3204 /* Helper function for check_arrival_expand_ecl.
3205 Check incrementally the epsilon closure of TARGET, and if it isn't
3206 problematic append it to DST_NODES. */
3208 static reg_errcode_t
3210 check_arrival_expand_ecl_sub (const re_dfa_t *dfa, re_node_set *dst_nodes,
3211 Idx target, Idx ex_subexp, int type)
3214 for (cur_node = target; !re_node_set_contains (dst_nodes, cur_node);)
3218 if (dfa->nodes[cur_node].type == type
3219 && dfa->nodes[cur_node].opr.idx == ex_subexp)
3221 if (type == OP_CLOSE_SUBEXP)
3223 ok = re_node_set_insert (dst_nodes, cur_node);
3229 ok = re_node_set_insert (dst_nodes, cur_node);
3232 if (dfa->edests[cur_node].nelem == 0)
3234 if (dfa->edests[cur_node].nelem == 2)
3237 err = check_arrival_expand_ecl_sub (dfa, dst_nodes,
3238 dfa->edests[cur_node].elems[1],
3240 if (BE (err != REG_NOERROR, 0))
3243 cur_node = dfa->edests[cur_node].elems[0];
3249 /* For all the back references in the current state, calculate the
3250 destination of the back references by the appropriate entry
3251 in MCTX->BKREF_ENTS. */
3253 static reg_errcode_t
3255 expand_bkref_cache (re_match_context_t *mctx, re_node_set *cur_nodes,
3256 Idx cur_str, Idx subexp_num, int type)
3258 const re_dfa_t *const dfa = mctx->dfa;
3260 Idx cache_idx_start = search_cur_bkref_entry (mctx, cur_str);
3261 struct re_backref_cache_entry *ent;
3263 if (cache_idx_start == REG_MISSING)
3267 ent = mctx->bkref_ents + cache_idx_start;
3270 Idx to_idx, next_node;
3272 /* Is this entry ENT is appropriate? */
3273 if (!re_node_set_contains (cur_nodes, ent->node))
3276 to_idx = cur_str + ent->subexp_to - ent->subexp_from;
3277 /* Calculate the destination of the back reference, and append it
3278 to MCTX->STATE_LOG. */
3279 if (to_idx == cur_str)
3281 /* The backreference did epsilon transit, we must re-check all the
3282 node in the current state. */
3283 re_node_set new_dests;
3284 reg_errcode_t err2, err3;
3285 next_node = dfa->edests[ent->node].elems[0];
3286 if (re_node_set_contains (cur_nodes, next_node))
3288 err = re_node_set_init_1 (&new_dests, next_node);
3289 err2 = check_arrival_expand_ecl (dfa, &new_dests, subexp_num, type);
3290 err3 = re_node_set_merge (cur_nodes, &new_dests);
3291 re_node_set_free (&new_dests);
3292 if (BE (err != REG_NOERROR || err2 != REG_NOERROR
3293 || err3 != REG_NOERROR, 0))
3295 err = (err != REG_NOERROR ? err
3296 : (err2 != REG_NOERROR ? err2 : err3));
3299 /* TODO: It is still inefficient... */
3304 re_node_set union_set;
3305 next_node = dfa->nexts[ent->node];
3306 if (mctx->state_log[to_idx])
3309 if (re_node_set_contains (&mctx->state_log[to_idx]->nodes,
3312 err = re_node_set_init_copy (&union_set,
3313 &mctx->state_log[to_idx]->nodes);
3314 ok = re_node_set_insert (&union_set, next_node);
3315 if (BE (err != REG_NOERROR || ! ok, 0))
3317 re_node_set_free (&union_set);
3318 err = err != REG_NOERROR ? err : REG_ESPACE;
3324 err = re_node_set_init_1 (&union_set, next_node);
3325 if (BE (err != REG_NOERROR, 0))
3328 mctx->state_log[to_idx] = re_acquire_state (&err, dfa, &union_set);
3329 re_node_set_free (&union_set);
3330 if (BE (mctx->state_log[to_idx] == NULL
3331 && err != REG_NOERROR, 0))
3335 while (ent++->more);
3339 /* Build transition table for the state.
3340 Return true if successful. */
3344 build_trtable (const re_dfa_t *dfa, re_dfastate_t *state)
3349 bool need_word_trtable = false;
3350 bitset_word_t elem, mask;
3351 bool dests_node_malloced = false;
3352 bool dest_states_malloced = false;
3353 Idx ndests; /* Number of the destination states from `state'. */
3354 re_dfastate_t **trtable;
3355 re_dfastate_t **dest_states = NULL, **dest_states_word, **dest_states_nl;
3356 re_node_set follows, *dests_node;
3358 bitset_t acceptable;
3362 re_node_set dests_node[SBC_MAX];
3363 bitset_t dests_ch[SBC_MAX];
3366 /* We build DFA states which corresponds to the destination nodes
3367 from `state'. `dests_node[i]' represents the nodes which i-th
3368 destination state contains, and `dests_ch[i]' represents the
3369 characters which i-th destination state accepts. */
3370 if (__libc_use_alloca (sizeof (struct dests_alloc)))
3371 dests_alloc = (struct dests_alloc *) alloca (sizeof (struct dests_alloc));
3374 dests_alloc = re_malloc (struct dests_alloc, 1);
3375 if (BE (dests_alloc == NULL, 0))
3377 dests_node_malloced = true;
3379 dests_node = dests_alloc->dests_node;
3380 dests_ch = dests_alloc->dests_ch;
3382 /* Initialize transiton table. */
3383 state->word_trtable = state->trtable = NULL;
3385 /* At first, group all nodes belonging to `state' into several
3387 ndests = group_nodes_into_DFAstates (dfa, state, dests_node, dests_ch);
3388 if (BE (! REG_VALID_NONZERO_INDEX (ndests), 0))
3390 if (dests_node_malloced)
3394 state->trtable = (re_dfastate_t **)
3395 calloc (sizeof (re_dfastate_t *), SBC_MAX);
3401 err = re_node_set_alloc (&follows, ndests + 1);
3402 if (BE (err != REG_NOERROR, 0))
3405 /* Avoid arithmetic overflow in size calculation. */
3406 if (BE ((((SIZE_MAX - (sizeof (re_node_set) + sizeof (bitset_t)) * SBC_MAX)
3407 / (3 * sizeof (re_dfastate_t *)))
3412 if (__libc_use_alloca ((sizeof (re_node_set) + sizeof (bitset_t)) * SBC_MAX
3413 + ndests * 3 * sizeof (re_dfastate_t *)))
3414 dest_states = (re_dfastate_t **)
3415 alloca (ndests * 3 * sizeof (re_dfastate_t *));
3418 dest_states = (re_dfastate_t **)
3419 malloc (ndests * 3 * sizeof (re_dfastate_t *));
3420 if (BE (dest_states == NULL, 0))
3423 if (dest_states_malloced)
3425 re_node_set_free (&follows);
3426 for (i = 0; i < ndests; ++i)
3427 re_node_set_free (dests_node + i);
3428 if (dests_node_malloced)
3432 dest_states_malloced = true;
3434 dest_states_word = dest_states + ndests;
3435 dest_states_nl = dest_states_word + ndests;
3436 bitset_empty (acceptable);
3438 /* Then build the states for all destinations. */
3439 for (i = 0; i < ndests; ++i)
3442 re_node_set_empty (&follows);
3443 /* Merge the follows of this destination states. */
3444 for (j = 0; j < dests_node[i].nelem; ++j)
3446 next_node = dfa->nexts[dests_node[i].elems[j]];
3447 if (next_node != REG_MISSING)
3449 err = re_node_set_merge (&follows, dfa->eclosures + next_node);
3450 if (BE (err != REG_NOERROR, 0))
3454 dest_states[i] = re_acquire_state_context (&err, dfa, &follows, 0);
3455 if (BE (dest_states[i] == NULL && err != REG_NOERROR, 0))
3457 /* If the new state has context constraint,
3458 build appropriate states for these contexts. */
3459 if (dest_states[i]->has_constraint)
3461 dest_states_word[i] = re_acquire_state_context (&err, dfa, &follows,
3463 if (BE (dest_states_word[i] == NULL && err != REG_NOERROR, 0))
3466 if (dest_states[i] != dest_states_word[i] && dfa->mb_cur_max > 1)
3467 need_word_trtable = true;
3469 dest_states_nl[i] = re_acquire_state_context (&err, dfa, &follows,
3471 if (BE (dest_states_nl[i] == NULL && err != REG_NOERROR, 0))
3476 dest_states_word[i] = dest_states[i];
3477 dest_states_nl[i] = dest_states[i];
3479 bitset_merge (acceptable, dests_ch[i]);
3482 if (!BE (need_word_trtable, 0))
3484 /* We don't care about whether the following character is a word
3485 character, or we are in a single-byte character set so we can
3486 discern by looking at the character code: allocate a
3487 256-entry transition table. */
3488 trtable = state->trtable =
3489 (re_dfastate_t **) calloc (sizeof (re_dfastate_t *), SBC_MAX);
3490 if (BE (trtable == NULL, 0))
3493 /* For all characters ch...: */
3494 for (i = 0; i < BITSET_WORDS; ++i)
3495 for (ch = i * BITSET_WORD_BITS, elem = acceptable[i], mask = 1;
3497 mask <<= 1, elem >>= 1, ++ch)
3498 if (BE (elem & 1, 0))
3500 /* There must be exactly one destination which accepts
3501 character ch. See group_nodes_into_DFAstates. */
3502 for (j = 0; (dests_ch[j][i] & mask) == 0; ++j)
3505 /* j-th destination accepts the word character ch. */
3506 if (dfa->word_char[i] & mask)
3507 trtable[ch] = dest_states_word[j];
3509 trtable[ch] = dest_states[j];
3514 /* We care about whether the following character is a word
3515 character, and we are in a multi-byte character set: discern
3516 by looking at the character code: build two 256-entry
3517 transition tables, one starting at trtable[0] and one
3518 starting at trtable[SBC_MAX]. */
3519 trtable = state->word_trtable =
3520 (re_dfastate_t **) calloc (sizeof (re_dfastate_t *), 2 * SBC_MAX);
3521 if (BE (trtable == NULL, 0))
3524 /* For all characters ch...: */
3525 for (i = 0; i < BITSET_WORDS; ++i)
3526 for (ch = i * BITSET_WORD_BITS, elem = acceptable[i], mask = 1;
3528 mask <<= 1, elem >>= 1, ++ch)
3529 if (BE (elem & 1, 0))
3531 /* There must be exactly one destination which accepts
3532 character ch. See group_nodes_into_DFAstates. */
3533 for (j = 0; (dests_ch[j][i] & mask) == 0; ++j)
3536 /* j-th destination accepts the word character ch. */
3537 trtable[ch] = dest_states[j];
3538 trtable[ch + SBC_MAX] = dest_states_word[j];
3543 if (bitset_contain (acceptable, NEWLINE_CHAR))
3545 /* The current state accepts newline character. */
3546 for (j = 0; j < ndests; ++j)
3547 if (bitset_contain (dests_ch[j], NEWLINE_CHAR))
3549 /* k-th destination accepts newline character. */
3550 trtable[NEWLINE_CHAR] = dest_states_nl[j];
3551 if (need_word_trtable)
3552 trtable[NEWLINE_CHAR + SBC_MAX] = dest_states_nl[j];
3553 /* There must be only one destination which accepts
3554 newline. See group_nodes_into_DFAstates. */
3559 if (dest_states_malloced)
3562 re_node_set_free (&follows);
3563 for (i = 0; i < ndests; ++i)
3564 re_node_set_free (dests_node + i);
3566 if (dests_node_malloced)
3572 /* Group all nodes belonging to STATE into several destinations.
3573 Then for all destinations, set the nodes belonging to the destination
3574 to DESTS_NODE[i] and set the characters accepted by the destination
3575 to DEST_CH[i]. This function return the number of destinations. */
3579 group_nodes_into_DFAstates (const re_dfa_t *dfa, const re_dfastate_t *state,
3580 re_node_set *dests_node, bitset_t *dests_ch)
3585 Idx ndests; /* Number of the destinations from `state'. */
3586 bitset_t accepts; /* Characters a node can accept. */
3587 const re_node_set *cur_nodes = &state->nodes;
3588 bitset_empty (accepts);
3591 /* For all the nodes belonging to `state', */
3592 for (i = 0; i < cur_nodes->nelem; ++i)
3594 re_token_t *node = &dfa->nodes[cur_nodes->elems[i]];
3595 re_token_type_t type = node->type;
3596 unsigned int constraint = node->constraint;
3598 /* Enumerate all single byte character this node can accept. */
3599 if (type == CHARACTER)
3600 bitset_set (accepts, node->opr.c);
3601 else if (type == SIMPLE_BRACKET)
3603 bitset_merge (accepts, node->opr.sbcset);
3605 else if (type == OP_PERIOD)
3607 #ifdef RE_ENABLE_I18N
3608 if (dfa->mb_cur_max > 1)
3609 bitset_merge (accepts, dfa->sb_char);
3612 bitset_set_all (accepts);
3613 if (!(dfa->syntax & RE_DOT_NEWLINE))
3614 bitset_clear (accepts, '\n');
3615 if (dfa->syntax & RE_DOT_NOT_NULL)
3616 bitset_clear (accepts, '\0');
3618 #ifdef RE_ENABLE_I18N
3619 else if (type == OP_UTF8_PERIOD)
3621 if (ASCII_CHARS % BITSET_WORD_BITS == 0)
3622 memset (accepts, -1, ASCII_CHARS / CHAR_BIT);
3624 bitset_merge (accepts, utf8_sb_map);
3625 if (!(dfa->syntax & RE_DOT_NEWLINE))
3626 bitset_clear (accepts, '\n');
3627 if (dfa->syntax & RE_DOT_NOT_NULL)
3628 bitset_clear (accepts, '\0');
3634 /* Check the `accepts' and sift the characters which are not
3635 match it the context. */
3638 if (constraint & NEXT_NEWLINE_CONSTRAINT)
3640 bool accepts_newline = bitset_contain (accepts, NEWLINE_CHAR);
3641 bitset_empty (accepts);
3642 if (accepts_newline)
3643 bitset_set (accepts, NEWLINE_CHAR);
3647 if (constraint & NEXT_ENDBUF_CONSTRAINT)
3649 bitset_empty (accepts);
3653 if (constraint & NEXT_WORD_CONSTRAINT)
3655 bitset_word_t any_set = 0;
3656 if (type == CHARACTER && !node->word_char)
3658 bitset_empty (accepts);
3661 #ifdef RE_ENABLE_I18N
3662 if (dfa->mb_cur_max > 1)
3663 for (j = 0; j < BITSET_WORDS; ++j)
3664 any_set |= (accepts[j] &= (dfa->word_char[j] | ~dfa->sb_char[j]));
3667 for (j = 0; j < BITSET_WORDS; ++j)
3668 any_set |= (accepts[j] &= dfa->word_char[j]);
3672 if (constraint & NEXT_NOTWORD_CONSTRAINT)
3674 bitset_word_t any_set = 0;
3675 if (type == CHARACTER && node->word_char)
3677 bitset_empty (accepts);
3680 #ifdef RE_ENABLE_I18N
3681 if (dfa->mb_cur_max > 1)
3682 for (j = 0; j < BITSET_WORDS; ++j)
3683 any_set |= (accepts[j] &= ~(dfa->word_char[j] & dfa->sb_char[j]));
3686 for (j = 0; j < BITSET_WORDS; ++j)
3687 any_set |= (accepts[j] &= ~dfa->word_char[j]);
3693 /* Then divide `accepts' into DFA states, or create a new
3694 state. Above, we make sure that accepts is not empty. */
3695 for (j = 0; j < ndests; ++j)
3697 bitset_t intersec; /* Intersection sets, see below. */
3699 /* Flags, see below. */
3700 bitset_word_t has_intersec, not_subset, not_consumed;
3702 /* Optimization, skip if this state doesn't accept the character. */
3703 if (type == CHARACTER && !bitset_contain (dests_ch[j], node->opr.c))
3706 /* Enumerate the intersection set of this state and `accepts'. */
3708 for (k = 0; k < BITSET_WORDS; ++k)
3709 has_intersec |= intersec[k] = accepts[k] & dests_ch[j][k];
3710 /* And skip if the intersection set is empty. */
3714 /* Then check if this state is a subset of `accepts'. */
3715 not_subset = not_consumed = 0;
3716 for (k = 0; k < BITSET_WORDS; ++k)
3718 not_subset |= remains[k] = ~accepts[k] & dests_ch[j][k];
3719 not_consumed |= accepts[k] = accepts[k] & ~dests_ch[j][k];
3722 /* If this state isn't a subset of `accepts', create a
3723 new group state, which has the `remains'. */
3726 bitset_copy (dests_ch[ndests], remains);
3727 bitset_copy (dests_ch[j], intersec);
3728 err = re_node_set_init_copy (dests_node + ndests, &dests_node[j]);
3729 if (BE (err != REG_NOERROR, 0))
3734 /* Put the position in the current group. */
3735 ok = re_node_set_insert (&dests_node[j], cur_nodes->elems[i]);
3739 /* If all characters are consumed, go to next node. */
3743 /* Some characters remain, create a new group. */
3746 bitset_copy (dests_ch[ndests], accepts);
3747 err = re_node_set_init_1 (dests_node + ndests, cur_nodes->elems[i]);
3748 if (BE (err != REG_NOERROR, 0))
3751 bitset_empty (accepts);
3756 for (j = 0; j < ndests; ++j)
3757 re_node_set_free (dests_node + j);
3761 #ifdef RE_ENABLE_I18N
3762 /* Check how many bytes the node `dfa->nodes[node_idx]' accepts.
3763 Return the number of the bytes the node accepts.
3764 STR_IDX is the current index of the input string.
3766 This function handles the nodes which can accept one character, or
3767 one collating element like '.', '[a-z]', opposite to the other nodes
3768 can only accept one byte. */
3772 check_node_accept_bytes (const re_dfa_t *dfa, Idx node_idx,
3773 const re_string_t *input, Idx str_idx)
3775 const re_token_t *node = dfa->nodes + node_idx;
3776 int char_len, elem_len;
3779 if (BE (node->type == OP_UTF8_PERIOD, 0))
3781 unsigned char c = re_string_byte_at (input, str_idx), d;
3782 if (BE (c < 0xc2, 1))
3785 if (str_idx + 2 > input->len)
3788 d = re_string_byte_at (input, str_idx + 1);
3790 return (d < 0x80 || d > 0xbf) ? 0 : 2;
3794 if (c == 0xe0 && d < 0xa0)
3800 if (c == 0xf0 && d < 0x90)
3806 if (c == 0xf8 && d < 0x88)
3812 if (c == 0xfc && d < 0x84)
3818 if (str_idx + char_len > input->len)
3821 for (i = 1; i < char_len; ++i)
3823 d = re_string_byte_at (input, str_idx + i);
3824 if (d < 0x80 || d > 0xbf)
3830 char_len = re_string_char_size_at (input, str_idx);
3831 if (node->type == OP_PERIOD)
3835 /* FIXME: I don't think this if is needed, as both '\n'
3836 and '\0' are char_len == 1. */
3837 /* '.' accepts any one character except the following two cases. */
3838 if ((!(dfa->syntax & RE_DOT_NEWLINE) &&
3839 re_string_byte_at (input, str_idx) == '\n') ||
3840 ((dfa->syntax & RE_DOT_NOT_NULL) &&
3841 re_string_byte_at (input, str_idx) == '\0'))
3846 elem_len = re_string_elem_size_at (input, str_idx);
3847 if ((elem_len <= 1 && char_len <= 1) || char_len == 0)
3850 if (node->type == COMPLEX_BRACKET)
3852 const re_charset_t *cset = node->opr.mbcset;
3854 const unsigned char *pin
3855 = ((const unsigned char *) re_string_get_buffer (input) + str_idx);
3860 wchar_t wc = ((cset->nranges || cset->nchar_classes || cset->nmbchars)
3861 ? re_string_wchar_at (input, str_idx) : 0);
3863 /* match with multibyte character? */
3864 for (i = 0; i < cset->nmbchars; ++i)
3865 if (wc == cset->mbchars[i])
3867 match_len = char_len;
3868 goto check_node_accept_bytes_match;
3870 /* match with character_class? */
3871 for (i = 0; i < cset->nchar_classes; ++i)
3873 wctype_t wt = cset->char_classes[i];
3874 if (__iswctype (wc, wt))
3876 match_len = char_len;
3877 goto check_node_accept_bytes_match;
3882 nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
3885 unsigned int in_collseq = 0;
3886 const int32_t *table, *indirect;
3887 const unsigned char *weights, *extra;
3888 const char *collseqwc;
3890 /* This #include defines a local function! */
3891 # include <locale/weight.h>
3893 /* match with collating_symbol? */
3894 if (cset->ncoll_syms)
3895 extra = (const unsigned char *)
3896 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB);
3897 for (i = 0; i < cset->ncoll_syms; ++i)
3899 const unsigned char *coll_sym = extra + cset->coll_syms[i];
3900 /* Compare the length of input collating element and
3901 the length of current collating element. */
3902 if (*coll_sym != elem_len)
3904 /* Compare each bytes. */
3905 for (j = 0; j < *coll_sym; j++)
3906 if (pin[j] != coll_sym[1 + j])
3910 /* Match if every bytes is equal. */
3912 goto check_node_accept_bytes_match;
3918 if (elem_len <= char_len)
3920 collseqwc = _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQWC);
3921 in_collseq = __collseq_table_lookup (collseqwc, wc);
3924 in_collseq = find_collation_sequence_value (pin, elem_len);
3926 /* match with range expression? */
3927 for (i = 0; i < cset->nranges; ++i)
3928 if (cset->range_starts[i] <= in_collseq
3929 && in_collseq <= cset->range_ends[i])
3931 match_len = elem_len;
3932 goto check_node_accept_bytes_match;
3935 /* match with equivalence_class? */
3936 if (cset->nequiv_classes)
3938 const unsigned char *cp = pin;
3939 table = (const int32_t *)
3940 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
3941 weights = (const unsigned char *)
3942 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_WEIGHTMB);
3943 extra = (const unsigned char *)
3944 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAMB);
3945 indirect = (const int32_t *)
3946 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_INDIRECTMB);
3947 idx = findidx (&cp);
3949 for (i = 0; i < cset->nequiv_classes; ++i)
3951 int32_t equiv_class_idx = cset->equiv_classes[i];
3952 size_t weight_len = weights[idx];
3953 if (weight_len == weights[equiv_class_idx])
3956 while (cnt <= weight_len
3957 && (weights[equiv_class_idx + 1 + cnt]
3958 == weights[idx + 1 + cnt]))
3960 if (cnt > weight_len)
3962 match_len = elem_len;
3963 goto check_node_accept_bytes_match;
3972 /* match with range expression? */
3973 #if __GNUC__ >= 2 && ! (__STDC_VERSION__ < 199901L && __STRICT_ANSI__)
3974 wchar_t cmp_buf[] = {L'\0', L'\0', wc, L'\0', L'\0', L'\0'};
3976 wchar_t cmp_buf[] = {L'\0', L'\0', L'\0', L'\0', L'\0', L'\0'};
3979 for (i = 0; i < cset->nranges; ++i)
3981 cmp_buf[0] = cset->range_starts[i];
3982 cmp_buf[4] = cset->range_ends[i];
3983 if (wcscoll (cmp_buf, cmp_buf + 2) <= 0
3984 && wcscoll (cmp_buf + 2, cmp_buf + 4) <= 0)
3986 match_len = char_len;
3987 goto check_node_accept_bytes_match;
3991 check_node_accept_bytes_match:
3992 if (!cset->non_match)
3999 return (elem_len > char_len) ? elem_len : char_len;
4008 find_collation_sequence_value (const unsigned char *mbs, size_t mbs_len)
4010 uint32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
4015 /* No valid character. Match it as a single byte character. */
4016 const unsigned char *collseq = (const unsigned char *)
4017 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQMB);
4018 return collseq[mbs[0]];
4025 const unsigned char *extra = (const unsigned char *)
4026 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB);
4027 int32_t extrasize = (const unsigned char *)
4028 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB + 1) - extra;
4030 for (idx = 0; idx < extrasize;)
4034 int32_t elem_mbs_len;
4035 /* Skip the name of collating element name. */
4036 idx = idx + extra[idx] + 1;
4037 elem_mbs_len = extra[idx++];
4038 if (mbs_len == elem_mbs_len)
4040 for (mbs_cnt = 0; mbs_cnt < elem_mbs_len; ++mbs_cnt)
4041 if (extra[idx + mbs_cnt] != mbs[mbs_cnt])
4043 if (mbs_cnt == elem_mbs_len)
4044 /* Found the entry. */
4047 /* Skip the byte sequence of the collating element. */
4048 idx += elem_mbs_len;
4049 /* Adjust for the alignment. */
4050 idx = (idx + 3) & ~3;
4051 /* Skip the collation sequence value. */
4052 idx += sizeof (uint32_t);
4053 /* Skip the wide char sequence of the collating element. */
4054 idx = idx + sizeof (uint32_t) * (extra[idx] + 1);
4055 /* If we found the entry, return the sequence value. */
4057 return *(uint32_t *) (extra + idx);
4058 /* Skip the collation sequence value. */
4059 idx += sizeof (uint32_t);
4065 #endif /* RE_ENABLE_I18N */
4067 /* Check whether the node accepts the byte which is IDX-th
4068 byte of the INPUT. */
4072 check_node_accept (const re_match_context_t *mctx, const re_token_t *node,
4076 ch = re_string_byte_at (&mctx->input, idx);
4080 if (node->opr.c != ch)
4084 case SIMPLE_BRACKET:
4085 if (!bitset_contain (node->opr.sbcset, ch))
4089 #ifdef RE_ENABLE_I18N
4090 case OP_UTF8_PERIOD:
4091 if (ch >= ASCII_CHARS)
4096 if ((ch == '\n' && !(mctx->dfa->syntax & RE_DOT_NEWLINE))
4097 || (ch == '\0' && (mctx->dfa->syntax & RE_DOT_NOT_NULL)))
4105 if (node->constraint)
4107 /* The node has constraints. Check whether the current context
4108 satisfies the constraints. */
4109 unsigned int context = re_string_context_at (&mctx->input, idx,
4111 if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
4118 /* Extend the buffers, if the buffers have run out. */
4120 static reg_errcode_t
4122 extend_buffers (re_match_context_t *mctx)
4125 re_string_t *pstr = &mctx->input;
4127 /* Avoid overflow. */
4128 if (BE (SIZE_MAX / 2 / sizeof (re_dfastate_t *) <= pstr->bufs_len, 0))
4131 /* Double the lengthes of the buffers. */
4132 ret = re_string_realloc_buffers (pstr, pstr->bufs_len * 2);
4133 if (BE (ret != REG_NOERROR, 0))
4136 if (mctx->state_log != NULL)
4138 /* And double the length of state_log. */
4139 /* XXX We have no indication of the size of this buffer. If this
4140 allocation fail we have no indication that the state_log array
4141 does not have the right size. */
4142 re_dfastate_t **new_array = re_realloc (mctx->state_log, re_dfastate_t *,
4143 pstr->bufs_len + 1);
4144 if (BE (new_array == NULL, 0))
4146 mctx->state_log = new_array;
4149 /* Then reconstruct the buffers. */
4152 #ifdef RE_ENABLE_I18N
4153 if (pstr->mb_cur_max > 1)
4155 ret = build_wcs_upper_buffer (pstr);
4156 if (BE (ret != REG_NOERROR, 0))
4160 #endif /* RE_ENABLE_I18N */
4161 build_upper_buffer (pstr);
4165 #ifdef RE_ENABLE_I18N
4166 if (pstr->mb_cur_max > 1)
4167 build_wcs_buffer (pstr);
4169 #endif /* RE_ENABLE_I18N */
4171 if (pstr->trans != NULL)
4172 re_string_translate_buffer (pstr);
4179 /* Functions for matching context. */
4181 /* Initialize MCTX. */
4183 static reg_errcode_t
4185 match_ctx_init (re_match_context_t *mctx, int eflags, Idx n)
4187 mctx->eflags = eflags;
4188 mctx->match_last = REG_MISSING;
4191 /* Avoid overflow. */
4192 size_t max_object_size =
4193 MAX (sizeof (struct re_backref_cache_entry),
4194 sizeof (re_sub_match_top_t *));
4195 if (BE (SIZE_MAX / max_object_size < n, 0))
4198 mctx->bkref_ents = re_malloc (struct re_backref_cache_entry, n);
4199 mctx->sub_tops = re_malloc (re_sub_match_top_t *, n);
4200 if (BE (mctx->bkref_ents == NULL || mctx->sub_tops == NULL, 0))
4203 /* Already zero-ed by the caller.
4205 mctx->bkref_ents = NULL;
4206 mctx->nbkref_ents = 0;
4207 mctx->nsub_tops = 0; */
4208 mctx->abkref_ents = n;
4209 mctx->max_mb_elem_len = 1;
4210 mctx->asub_tops = n;
4214 /* Clean the entries which depend on the current input in MCTX.
4215 This function must be invoked when the matcher changes the start index
4216 of the input, or changes the input string. */
4220 match_ctx_clean (re_match_context_t *mctx)
4223 for (st_idx = 0; st_idx < mctx->nsub_tops; ++st_idx)
4226 re_sub_match_top_t *top = mctx->sub_tops[st_idx];
4227 for (sl_idx = 0; sl_idx < top->nlasts; ++sl_idx)
4229 re_sub_match_last_t *last = top->lasts[sl_idx];
4230 re_free (last->path.array);
4233 re_free (top->lasts);
4236 re_free (top->path->array);
4237 re_free (top->path);
4242 mctx->nsub_tops = 0;
4243 mctx->nbkref_ents = 0;
4246 /* Free all the memory associated with MCTX. */
4250 match_ctx_free (re_match_context_t *mctx)
4252 /* First, free all the memory associated with MCTX->SUB_TOPS. */
4253 match_ctx_clean (mctx);
4254 re_free (mctx->sub_tops);
4255 re_free (mctx->bkref_ents);
4258 /* Add a new backreference entry to MCTX.
4259 Note that we assume that caller never call this function with duplicate
4260 entry, and call with STR_IDX which isn't smaller than any existing entry.
4263 static reg_errcode_t
4265 match_ctx_add_entry (re_match_context_t *mctx, Idx node, Idx str_idx, Idx from,
4268 if (mctx->nbkref_ents >= mctx->abkref_ents)
4270 struct re_backref_cache_entry* new_entry;
4271 new_entry = re_realloc (mctx->bkref_ents, struct re_backref_cache_entry,
4272 mctx->abkref_ents * 2);
4273 if (BE (new_entry == NULL, 0))
4275 re_free (mctx->bkref_ents);
4278 mctx->bkref_ents = new_entry;
4279 memset (mctx->bkref_ents + mctx->nbkref_ents, '\0',
4280 sizeof (struct re_backref_cache_entry) * mctx->abkref_ents);
4281 mctx->abkref_ents *= 2;
4283 if (mctx->nbkref_ents > 0
4284 && mctx->bkref_ents[mctx->nbkref_ents - 1].str_idx == str_idx)
4285 mctx->bkref_ents[mctx->nbkref_ents - 1].more = 1;
4287 mctx->bkref_ents[mctx->nbkref_ents].node = node;
4288 mctx->bkref_ents[mctx->nbkref_ents].str_idx = str_idx;
4289 mctx->bkref_ents[mctx->nbkref_ents].subexp_from = from;
4290 mctx->bkref_ents[mctx->nbkref_ents].subexp_to = to;
4292 /* This is a cache that saves negative results of check_dst_limits_calc_pos.
4293 If bit N is clear, means that this entry won't epsilon-transition to
4294 an OP_OPEN_SUBEXP or OP_CLOSE_SUBEXP for the N+1-th subexpression. If
4295 it is set, check_dst_limits_calc_pos_1 will recurse and try to find one
4298 A backreference does not epsilon-transition unless it is empty, so set
4299 to all zeros if FROM != TO. */
4300 mctx->bkref_ents[mctx->nbkref_ents].eps_reachable_subexps_map
4301 = (from == to ? -1 : 0);
4303 mctx->bkref_ents[mctx->nbkref_ents++].more = 0;
4304 if (mctx->max_mb_elem_len < to - from)
4305 mctx->max_mb_elem_len = to - from;
4309 /* Return the first entry with the same str_idx, or REG_MISSING if none is
4310 found. Note that MCTX->BKREF_ENTS is already sorted by MCTX->STR_IDX. */
4314 search_cur_bkref_entry (const re_match_context_t *mctx, Idx str_idx)
4316 Idx left, right, mid, last;
4317 last = right = mctx->nbkref_ents;
4318 for (left = 0; left < right;)
4320 mid = (left + right) / 2;
4321 if (mctx->bkref_ents[mid].str_idx < str_idx)
4326 if (left < last && mctx->bkref_ents[left].str_idx == str_idx)
4332 /* Register the node NODE, whose type is OP_OPEN_SUBEXP, and which matches
4335 static reg_errcode_t
4337 match_ctx_add_subtop (re_match_context_t *mctx, Idx node, Idx str_idx)
4340 assert (mctx->sub_tops != NULL);
4341 assert (mctx->asub_tops > 0);
4343 if (BE (mctx->nsub_tops == mctx->asub_tops, 0))
4345 Idx new_asub_tops = mctx->asub_tops * 2;
4346 re_sub_match_top_t **new_array = re_realloc (mctx->sub_tops,
4347 re_sub_match_top_t *,
4349 if (BE (new_array == NULL, 0))
4351 mctx->sub_tops = new_array;
4352 mctx->asub_tops = new_asub_tops;
4354 mctx->sub_tops[mctx->nsub_tops] = calloc (1, sizeof (re_sub_match_top_t));
4355 if (BE (mctx->sub_tops[mctx->nsub_tops] == NULL, 0))
4357 mctx->sub_tops[mctx->nsub_tops]->node = node;
4358 mctx->sub_tops[mctx->nsub_tops++]->str_idx = str_idx;
4362 /* Register the node NODE, whose type is OP_CLOSE_SUBEXP, and which matches
4363 at STR_IDX, whose corresponding OP_OPEN_SUBEXP is SUB_TOP. */
4365 static re_sub_match_last_t *
4367 match_ctx_add_sublast (re_sub_match_top_t *subtop, Idx node, Idx str_idx)
4369 re_sub_match_last_t *new_entry;
4370 if (BE (subtop->nlasts == subtop->alasts, 0))
4372 Idx new_alasts = 2 * subtop->alasts + 1;
4373 re_sub_match_last_t **new_array = re_realloc (subtop->lasts,
4374 re_sub_match_last_t *,
4376 if (BE (new_array == NULL, 0))
4378 subtop->lasts = new_array;
4379 subtop->alasts = new_alasts;
4381 new_entry = calloc (1, sizeof (re_sub_match_last_t));
4382 if (BE (new_entry != NULL, 1))
4384 subtop->lasts[subtop->nlasts] = new_entry;
4385 new_entry->node = node;
4386 new_entry->str_idx = str_idx;
4394 sift_ctx_init (re_sift_context_t *sctx, re_dfastate_t **sifted_sts,
4395 re_dfastate_t **limited_sts, Idx last_node, Idx last_str_idx)
4397 sctx->sifted_states = sifted_sts;
4398 sctx->limited_states = limited_sts;
4399 sctx->last_node = last_node;
4400 sctx->last_str_idx = last_str_idx;
4401 re_node_set_init_empty (&sctx->limits);