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 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, dfa);
707 if (BE (err != REG_NOERROR, 0))
709 mctx.input.stop = stop;
710 mctx.input.raw_stop = stop;
711 mctx.input.newline_anchor = preg->newline_anchor;
713 err = match_ctx_init (&mctx, eflags, dfa->nbackref * 2);
714 if (BE (err != REG_NOERROR, 0))
717 /* We will log all the DFA states through which the dfa pass,
718 if nmatch > 1, or this dfa has "multibyte node", which is a
719 back-reference or a node which can accept multibyte character or
720 multi character collating element. */
721 if (nmatch > 1 || dfa->has_mb_node)
723 /* Avoid overflow. */
724 if (BE (SIZE_MAX / sizeof (re_dfastate_t *) <= mctx.input.bufs_len, 0))
730 mctx.state_log = re_malloc (re_dfastate_t *, mctx.input.bufs_len + 1);
731 if (BE (mctx.state_log == NULL, 0))
738 mctx.state_log = NULL;
741 mctx.input.tip_context = (eflags & REG_NOTBOL) ? CONTEXT_BEGBUF
742 : CONTEXT_NEWLINE | CONTEXT_BEGBUF;
744 /* Check incrementally whether of not the input string match. */
745 incr = (last_start < start) ? -1 : 1;
746 left_lim = (last_start < start) ? last_start : start;
747 right_lim = (last_start < start) ? start : last_start;
748 sb = dfa->mb_cur_max == 1;
751 ? ((sb || !(preg->syntax & RE_ICASE || t) ? 4 : 0)
752 | (start <= last_start ? 2 : 0)
753 | (t != NULL ? 1 : 0))
756 for (;; match_first += incr)
759 if (match_first < left_lim || right_lim < match_first)
762 /* Advance as rapidly as possible through the string, until we
763 find a plausible place to start matching. This may be done
764 with varying efficiency, so there are various possibilities:
765 only the most common of them are specialized, in order to
766 save on code size. We use a switch statement for speed. */
774 /* Fastmap with single-byte translation, match forward. */
775 while (BE (match_first < right_lim, 1)
776 && !fastmap[t[(unsigned char) string[match_first]]])
778 goto forward_match_found_start_or_reached_end;
781 /* Fastmap without translation, match forward. */
782 while (BE (match_first < right_lim, 1)
783 && !fastmap[(unsigned char) string[match_first]])
786 forward_match_found_start_or_reached_end:
787 if (BE (match_first == right_lim, 0))
789 ch = match_first >= length
790 ? 0 : (unsigned char) string[match_first];
791 if (!fastmap[t ? t[ch] : ch])
798 /* Fastmap without multi-byte translation, match backwards. */
799 while (match_first >= left_lim)
801 ch = match_first >= length
802 ? 0 : (unsigned char) string[match_first];
803 if (fastmap[t ? t[ch] : ch])
807 if (match_first < left_lim)
812 /* In this case, we can't determine easily the current byte,
813 since it might be a component byte of a multibyte
814 character. Then we use the constructed buffer instead. */
817 /* If MATCH_FIRST is out of the valid range, reconstruct the
819 __re_size_t offset = match_first - mctx.input.raw_mbs_idx;
820 if (BE (offset >= (__re_size_t) mctx.input.valid_raw_len, 0))
822 err = re_string_reconstruct (&mctx.input, match_first,
824 if (BE (err != REG_NOERROR, 0))
827 offset = match_first - mctx.input.raw_mbs_idx;
829 /* If MATCH_FIRST is out of the buffer, leave it as '\0'.
830 Note that MATCH_FIRST must not be smaller than 0. */
831 ch = (match_first >= length
832 ? 0 : re_string_byte_at (&mctx.input, offset));
836 if (match_first < left_lim || match_first > right_lim)
845 /* Reconstruct the buffers so that the matcher can assume that
846 the matching starts from the beginning of the buffer. */
847 err = re_string_reconstruct (&mctx.input, match_first, eflags);
848 if (BE (err != REG_NOERROR, 0))
851 #ifdef RE_ENABLE_I18N
852 /* Don't consider this char as a possible match start if it part,
853 yet isn't the head, of a multibyte character. */
854 if (!sb && !re_string_first_byte (&mctx.input, 0))
858 /* It seems to be appropriate one, then use the matcher. */
859 /* We assume that the matching starts from 0. */
860 mctx.state_log_top = mctx.nbkref_ents = mctx.max_mb_elem_len = 0;
861 match_last = check_matching (&mctx, fl_longest_match,
862 start <= last_start ? &match_first : NULL);
863 if (match_last != REG_MISSING)
865 if (BE (match_last == REG_ERROR, 0))
872 mctx.match_last = match_last;
873 if ((!preg->no_sub && nmatch > 1) || dfa->nbackref)
875 re_dfastate_t *pstate = mctx.state_log[match_last];
876 mctx.last_node = check_halt_state_context (&mctx, pstate,
879 if ((!preg->no_sub && nmatch > 1 && dfa->has_plural_match)
882 err = prune_impossible_nodes (&mctx);
883 if (err == REG_NOERROR)
885 if (BE (err != REG_NOMATCH, 0))
887 match_last = REG_MISSING;
890 break; /* We found a match. */
894 match_ctx_clean (&mctx);
898 assert (match_last != REG_MISSING);
899 assert (err == REG_NOERROR);
902 /* Set pmatch[] if we need. */
907 /* Initialize registers. */
908 for (reg_idx = 1; reg_idx < nmatch; ++reg_idx)
909 pmatch[reg_idx].rm_so = pmatch[reg_idx].rm_eo = -1;
911 /* Set the points where matching start/end. */
913 pmatch[0].rm_eo = mctx.match_last;
914 /* FIXME: This function should fail if mctx.match_last exceeds
915 the maximum possible regoff_t value. We need a new error
916 code REG_OVERFLOW. */
918 if (!preg->no_sub && nmatch > 1)
920 err = set_regs (preg, &mctx, nmatch, pmatch,
921 dfa->has_plural_match && dfa->nbackref > 0);
922 if (BE (err != REG_NOERROR, 0))
926 /* At last, add the offset to the each registers, since we slided
927 the buffers so that we could assume that the matching starts
929 for (reg_idx = 0; reg_idx < nmatch; ++reg_idx)
930 if (pmatch[reg_idx].rm_so != -1)
932 #ifdef RE_ENABLE_I18N
933 if (BE (mctx.input.offsets_needed != 0, 0))
935 pmatch[reg_idx].rm_so =
936 (pmatch[reg_idx].rm_so == mctx.input.valid_len
937 ? mctx.input.valid_raw_len
938 : mctx.input.offsets[pmatch[reg_idx].rm_so]);
939 pmatch[reg_idx].rm_eo =
940 (pmatch[reg_idx].rm_eo == mctx.input.valid_len
941 ? mctx.input.valid_raw_len
942 : mctx.input.offsets[pmatch[reg_idx].rm_eo]);
945 assert (mctx.input.offsets_needed == 0);
947 pmatch[reg_idx].rm_so += match_first;
948 pmatch[reg_idx].rm_eo += match_first;
950 for (reg_idx = 0; reg_idx < extra_nmatch; ++reg_idx)
952 pmatch[nmatch + reg_idx].rm_so = -1;
953 pmatch[nmatch + reg_idx].rm_eo = -1;
957 for (reg_idx = 0; reg_idx + 1 < nmatch; reg_idx++)
958 if (dfa->subexp_map[reg_idx] != reg_idx)
960 pmatch[reg_idx + 1].rm_so
961 = pmatch[dfa->subexp_map[reg_idx] + 1].rm_so;
962 pmatch[reg_idx + 1].rm_eo
963 = pmatch[dfa->subexp_map[reg_idx] + 1].rm_eo;
968 re_free (mctx.state_log);
970 match_ctx_free (&mctx);
971 re_string_destruct (&mctx.input);
977 prune_impossible_nodes (re_match_context_t *mctx)
979 const re_dfa_t *const dfa = mctx->dfa;
980 Idx halt_node, match_last;
982 re_dfastate_t **sifted_states;
983 re_dfastate_t **lim_states = NULL;
984 re_sift_context_t sctx;
986 assert (mctx->state_log != NULL);
988 match_last = mctx->match_last;
989 halt_node = mctx->last_node;
991 /* Avoid overflow. */
992 if (BE (SIZE_MAX / sizeof (re_dfastate_t *) <= match_last, 0))
995 sifted_states = re_malloc (re_dfastate_t *, match_last + 1);
996 if (BE (sifted_states == NULL, 0))
1003 lim_states = re_malloc (re_dfastate_t *, match_last + 1);
1004 if (BE (lim_states == NULL, 0))
1011 memset (lim_states, '\0',
1012 sizeof (re_dfastate_t *) * (match_last + 1));
1013 sift_ctx_init (&sctx, sifted_states, lim_states, halt_node,
1015 ret = sift_states_backward (mctx, &sctx);
1016 re_node_set_free (&sctx.limits);
1017 if (BE (ret != REG_NOERROR, 0))
1019 if (sifted_states[0] != NULL || lim_states[0] != NULL)
1024 if (! REG_VALID_INDEX (match_last))
1029 } while (mctx->state_log[match_last] == NULL
1030 || !mctx->state_log[match_last]->halt);
1031 halt_node = check_halt_state_context (mctx,
1032 mctx->state_log[match_last],
1035 ret = merge_state_array (dfa, sifted_states, lim_states,
1037 re_free (lim_states);
1039 if (BE (ret != REG_NOERROR, 0))
1044 sift_ctx_init (&sctx, sifted_states, lim_states, halt_node, match_last);
1045 ret = sift_states_backward (mctx, &sctx);
1046 re_node_set_free (&sctx.limits);
1047 if (BE (ret != REG_NOERROR, 0))
1050 re_free (mctx->state_log);
1051 mctx->state_log = sifted_states;
1052 sifted_states = NULL;
1053 mctx->last_node = halt_node;
1054 mctx->match_last = match_last;
1057 re_free (sifted_states);
1058 re_free (lim_states);
1062 /* Acquire an initial state and return it.
1063 We must select appropriate initial state depending on the context,
1064 since initial states may have constraints like "\<", "^", etc.. */
1066 static inline re_dfastate_t *
1067 __attribute ((always_inline)) internal_function
1068 acquire_init_state_context (reg_errcode_t *err, const re_match_context_t *mctx,
1071 const re_dfa_t *const dfa = mctx->dfa;
1072 if (dfa->init_state->has_constraint)
1074 unsigned int context;
1075 context = re_string_context_at (&mctx->input, idx - 1, mctx->eflags);
1076 if (IS_WORD_CONTEXT (context))
1077 return dfa->init_state_word;
1078 else if (IS_ORDINARY_CONTEXT (context))
1079 return dfa->init_state;
1080 else if (IS_BEGBUF_CONTEXT (context) && IS_NEWLINE_CONTEXT (context))
1081 return dfa->init_state_begbuf;
1082 else if (IS_NEWLINE_CONTEXT (context))
1083 return dfa->init_state_nl;
1084 else if (IS_BEGBUF_CONTEXT (context))
1086 /* It is relatively rare case, then calculate on demand. */
1087 return re_acquire_state_context (err, dfa,
1088 dfa->init_state->entrance_nodes,
1092 /* Must not happen? */
1093 return dfa->init_state;
1096 return dfa->init_state;
1099 /* Check whether the regular expression match input string INPUT or not,
1100 and return the index where the matching end. Return REG_MISSING if
1101 there is no match, and return REG_ERROR in case of an error.
1102 FL_LONGEST_MATCH means we want the POSIX longest matching.
1103 If P_MATCH_FIRST is not NULL, and the match fails, it is set to the
1104 next place where we may want to try matching.
1105 Note that the matcher assume that the maching starts from the current
1106 index of the buffer. */
1110 check_matching (re_match_context_t *mctx, bool fl_longest_match,
1113 const re_dfa_t *const dfa = mctx->dfa;
1116 Idx match_last = REG_MISSING;
1117 Idx cur_str_idx = re_string_cur_idx (&mctx->input);
1118 re_dfastate_t *cur_state;
1119 bool at_init_state = p_match_first != NULL;
1120 Idx next_start_idx = cur_str_idx;
1123 cur_state = acquire_init_state_context (&err, mctx, cur_str_idx);
1124 /* An initial state must not be NULL (invalid). */
1125 if (BE (cur_state == NULL, 0))
1127 assert (err == REG_ESPACE);
1131 if (mctx->state_log != NULL)
1133 mctx->state_log[cur_str_idx] = cur_state;
1135 /* Check OP_OPEN_SUBEXP in the initial state in case that we use them
1136 later. E.g. Processing back references. */
1137 if (BE (dfa->nbackref, 0))
1139 at_init_state = false;
1140 err = check_subexp_matching_top (mctx, &cur_state->nodes, 0);
1141 if (BE (err != REG_NOERROR, 0))
1144 if (cur_state->has_backref)
1146 err = transit_state_bkref (mctx, &cur_state->nodes);
1147 if (BE (err != REG_NOERROR, 0))
1153 /* If the RE accepts NULL string. */
1154 if (BE (cur_state->halt, 0))
1156 if (!cur_state->has_constraint
1157 || check_halt_state_context (mctx, cur_state, cur_str_idx))
1159 if (!fl_longest_match)
1163 match_last = cur_str_idx;
1169 while (!re_string_eoi (&mctx->input))
1171 re_dfastate_t *old_state = cur_state;
1172 Idx next_char_idx = re_string_cur_idx (&mctx->input) + 1;
1174 if (BE (next_char_idx >= mctx->input.bufs_len, 0)
1175 || (BE (next_char_idx >= mctx->input.valid_len, 0)
1176 && mctx->input.valid_len < mctx->input.len))
1178 err = extend_buffers (mctx);
1179 if (BE (err != REG_NOERROR, 0))
1181 assert (err == REG_ESPACE);
1186 cur_state = transit_state (&err, mctx, cur_state);
1187 if (mctx->state_log != NULL)
1188 cur_state = merge_state_with_log (&err, mctx, cur_state);
1190 if (cur_state == NULL)
1192 /* Reached the invalid state or an error. Try to recover a valid
1193 state using the state log, if available and if we have not
1194 already found a valid (even if not the longest) match. */
1195 if (BE (err != REG_NOERROR, 0))
1198 if (mctx->state_log == NULL
1199 || (match && !fl_longest_match)
1200 || (cur_state = find_recover_state (&err, mctx)) == NULL)
1204 if (BE (at_init_state, 0))
1206 if (old_state == cur_state)
1207 next_start_idx = next_char_idx;
1209 at_init_state = false;
1212 if (cur_state->halt)
1214 /* Reached a halt state.
1215 Check the halt state can satisfy the current context. */
1216 if (!cur_state->has_constraint
1217 || check_halt_state_context (mctx, cur_state,
1218 re_string_cur_idx (&mctx->input)))
1220 /* We found an appropriate halt state. */
1221 match_last = re_string_cur_idx (&mctx->input);
1224 /* We found a match, do not modify match_first below. */
1225 p_match_first = NULL;
1226 if (!fl_longest_match)
1233 *p_match_first += next_start_idx;
1238 /* Check NODE match the current context. */
1242 check_halt_node_context (const re_dfa_t *dfa, Idx node, unsigned int context)
1244 re_token_type_t type = dfa->nodes[node].type;
1245 unsigned int constraint = dfa->nodes[node].constraint;
1246 if (type != END_OF_RE)
1250 if (NOT_SATISFY_NEXT_CONSTRAINT (constraint, context))
1255 /* Check the halt state STATE match the current context.
1256 Return 0 if not match, if the node, STATE has, is a halt node and
1257 match the context, return the node. */
1261 check_halt_state_context (const re_match_context_t *mctx,
1262 const re_dfastate_t *state, Idx idx)
1265 unsigned int context;
1267 assert (state->halt);
1269 context = re_string_context_at (&mctx->input, idx, mctx->eflags);
1270 for (i = 0; i < state->nodes.nelem; ++i)
1271 if (check_halt_node_context (mctx->dfa, state->nodes.elems[i], context))
1272 return state->nodes.elems[i];
1276 /* Compute the next node to which "NFA" transit from NODE("NFA" is a NFA
1277 corresponding to the DFA).
1278 Return the destination node, and update EPS_VIA_NODES;
1279 return REG_MISSING in case of errors. */
1283 proceed_next_node (const re_match_context_t *mctx, Idx nregs, regmatch_t *regs,
1284 Idx *pidx, Idx node, re_node_set *eps_via_nodes,
1285 struct re_fail_stack_t *fs)
1287 const re_dfa_t *const dfa = mctx->dfa;
1290 if (IS_EPSILON_NODE (dfa->nodes[node].type))
1292 re_node_set *cur_nodes = &mctx->state_log[*pidx]->nodes;
1293 re_node_set *edests = &dfa->edests[node];
1295 ok = re_node_set_insert (eps_via_nodes, node);
1298 /* Pick up a valid destination, or return REG_MISSING if none
1300 for (dest_node = REG_MISSING, i = 0; i < edests->nelem; ++i)
1302 Idx candidate = edests->elems[i];
1303 if (!re_node_set_contains (cur_nodes, candidate))
1305 if (dest_node == REG_MISSING)
1306 dest_node = candidate;
1310 /* In order to avoid infinite loop like "(a*)*", return the second
1311 epsilon-transition if the first was already considered. */
1312 if (re_node_set_contains (eps_via_nodes, dest_node))
1315 /* Otherwise, push the second epsilon-transition on the fail stack. */
1317 && push_fail_stack (fs, *pidx, candidate, nregs, regs,
1321 /* We know we are going to exit. */
1330 re_token_type_t type = dfa->nodes[node].type;
1332 #ifdef RE_ENABLE_I18N
1333 if (dfa->nodes[node].accept_mb)
1334 naccepted = check_node_accept_bytes (dfa, node, &mctx->input, *pidx);
1336 #endif /* RE_ENABLE_I18N */
1337 if (type == OP_BACK_REF)
1339 Idx subexp_idx = dfa->nodes[node].opr.idx + 1;
1340 naccepted = regs[subexp_idx].rm_eo - regs[subexp_idx].rm_so;
1343 if (regs[subexp_idx].rm_so == -1 || regs[subexp_idx].rm_eo == -1)
1347 char *buf = (char *) re_string_get_buffer (&mctx->input);
1348 if (memcmp (buf + regs[subexp_idx].rm_so, buf + *pidx,
1357 ok = re_node_set_insert (eps_via_nodes, node);
1360 dest_node = dfa->edests[node].elems[0];
1361 if (re_node_set_contains (&mctx->state_log[*pidx]->nodes,
1368 || check_node_accept (mctx, dfa->nodes + node, *pidx))
1370 Idx dest_node = dfa->nexts[node];
1371 *pidx = (naccepted == 0) ? *pidx + 1 : *pidx + naccepted;
1372 if (fs && (*pidx > mctx->match_last || mctx->state_log[*pidx] == NULL
1373 || !re_node_set_contains (&mctx->state_log[*pidx]->nodes,
1376 re_node_set_empty (eps_via_nodes);
1383 static reg_errcode_t
1385 push_fail_stack (struct re_fail_stack_t *fs, Idx str_idx, Idx dest_node,
1386 Idx nregs, regmatch_t *regs, re_node_set *eps_via_nodes)
1389 Idx num = fs->num++;
1390 if (fs->num == fs->alloc)
1392 struct re_fail_stack_ent_t *new_array;
1393 new_array = realloc (fs->stack, (sizeof (struct re_fail_stack_ent_t)
1395 if (new_array == NULL)
1398 fs->stack = new_array;
1400 fs->stack[num].idx = str_idx;
1401 fs->stack[num].node = dest_node;
1402 fs->stack[num].regs = re_malloc (regmatch_t, nregs);
1403 if (fs->stack[num].regs == NULL)
1405 memcpy (fs->stack[num].regs, regs, sizeof (regmatch_t) * nregs);
1406 err = re_node_set_init_copy (&fs->stack[num].eps_via_nodes, eps_via_nodes);
1412 pop_fail_stack (struct re_fail_stack_t *fs, Idx *pidx, Idx nregs,
1413 regmatch_t *regs, re_node_set *eps_via_nodes)
1415 Idx num = --fs->num;
1416 assert (REG_VALID_INDEX (num));
1417 *pidx = fs->stack[num].idx;
1418 memcpy (regs, fs->stack[num].regs, sizeof (regmatch_t) * nregs);
1419 re_node_set_free (eps_via_nodes);
1420 re_free (fs->stack[num].regs);
1421 *eps_via_nodes = fs->stack[num].eps_via_nodes;
1422 return fs->stack[num].node;
1425 /* Set the positions where the subexpressions are starts/ends to registers
1427 Note: We assume that pmatch[0] is already set, and
1428 pmatch[i].rm_so == pmatch[i].rm_eo == -1 for 0 < i < nmatch. */
1430 static reg_errcode_t
1432 set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
1433 regmatch_t *pmatch, bool fl_backtrack)
1435 const re_dfa_t *dfa = (const re_dfa_t *) preg->buffer;
1437 re_node_set eps_via_nodes;
1438 struct re_fail_stack_t *fs;
1439 struct re_fail_stack_t fs_body = { 0, 2, NULL };
1440 regmatch_t *prev_idx_match;
1441 bool prev_idx_match_malloced = false;
1444 assert (nmatch > 1);
1445 assert (mctx->state_log != NULL);
1450 fs->stack = re_malloc (struct re_fail_stack_ent_t, fs->alloc);
1451 if (fs->stack == NULL)
1457 cur_node = dfa->init_node;
1458 re_node_set_init_empty (&eps_via_nodes);
1460 if (__libc_use_alloca (nmatch * sizeof (regmatch_t)))
1461 prev_idx_match = (regmatch_t *) alloca (nmatch * sizeof (regmatch_t));
1464 prev_idx_match = re_malloc (regmatch_t, nmatch);
1465 if (prev_idx_match == NULL)
1467 free_fail_stack_return (fs);
1470 prev_idx_match_malloced = true;
1472 memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
1474 for (idx = pmatch[0].rm_so; idx <= pmatch[0].rm_eo ;)
1476 update_regs (dfa, pmatch, prev_idx_match, cur_node, idx, nmatch);
1478 if (idx == pmatch[0].rm_eo && cur_node == mctx->last_node)
1483 for (reg_idx = 0; reg_idx < nmatch; ++reg_idx)
1484 if (pmatch[reg_idx].rm_so > -1 && pmatch[reg_idx].rm_eo == -1)
1486 if (reg_idx == nmatch)
1488 re_node_set_free (&eps_via_nodes);
1489 if (prev_idx_match_malloced)
1490 re_free (prev_idx_match);
1491 return free_fail_stack_return (fs);
1493 cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
1498 re_node_set_free (&eps_via_nodes);
1499 if (prev_idx_match_malloced)
1500 re_free (prev_idx_match);
1505 /* Proceed to next node. */
1506 cur_node = proceed_next_node (mctx, nmatch, pmatch, &idx, cur_node,
1507 &eps_via_nodes, fs);
1509 if (BE (! REG_VALID_INDEX (cur_node), 0))
1511 if (BE (cur_node == REG_ERROR, 0))
1513 re_node_set_free (&eps_via_nodes);
1514 if (prev_idx_match_malloced)
1515 re_free (prev_idx_match);
1516 free_fail_stack_return (fs);
1520 cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
1524 re_node_set_free (&eps_via_nodes);
1525 if (prev_idx_match_malloced)
1526 re_free (prev_idx_match);
1531 re_node_set_free (&eps_via_nodes);
1532 if (prev_idx_match_malloced)
1533 re_free (prev_idx_match);
1534 return free_fail_stack_return (fs);
1537 static reg_errcode_t
1539 free_fail_stack_return (struct re_fail_stack_t *fs)
1544 for (fs_idx = 0; fs_idx < fs->num; ++fs_idx)
1546 re_node_set_free (&fs->stack[fs_idx].eps_via_nodes);
1547 re_free (fs->stack[fs_idx].regs);
1549 re_free (fs->stack);
1556 update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
1557 regmatch_t *prev_idx_match, Idx cur_node, Idx cur_idx, Idx nmatch)
1559 int type = dfa->nodes[cur_node].type;
1560 if (type == OP_OPEN_SUBEXP)
1562 Idx reg_num = dfa->nodes[cur_node].opr.idx + 1;
1564 /* We are at the first node of this sub expression. */
1565 if (reg_num < nmatch)
1567 pmatch[reg_num].rm_so = cur_idx;
1568 pmatch[reg_num].rm_eo = -1;
1571 else if (type == OP_CLOSE_SUBEXP)
1573 Idx reg_num = dfa->nodes[cur_node].opr.idx + 1;
1574 if (reg_num < nmatch)
1576 /* We are at the last node of this sub expression. */
1577 if (pmatch[reg_num].rm_so < cur_idx)
1579 pmatch[reg_num].rm_eo = cur_idx;
1580 /* This is a non-empty match or we are not inside an optional
1581 subexpression. Accept this right away. */
1582 memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
1586 if (dfa->nodes[cur_node].opt_subexp
1587 && prev_idx_match[reg_num].rm_so != -1)
1588 /* We transited through an empty match for an optional
1589 subexpression, like (a?)*, and this is not the subexp's
1590 first match. Copy back the old content of the registers
1591 so that matches of an inner subexpression are undone as
1592 well, like in ((a?))*. */
1593 memcpy (pmatch, prev_idx_match, sizeof (regmatch_t) * nmatch);
1595 /* We completed a subexpression, but it may be part of
1596 an optional one, so do not update PREV_IDX_MATCH. */
1597 pmatch[reg_num].rm_eo = cur_idx;
1603 /* This function checks the STATE_LOG from the SCTX->last_str_idx to 0
1604 and sift the nodes in each states according to the following rules.
1605 Updated state_log will be wrote to STATE_LOG.
1607 Rules: We throw away the Node `a' in the STATE_LOG[STR_IDX] if...
1608 1. When STR_IDX == MATCH_LAST(the last index in the state_log):
1609 If `a' isn't the LAST_NODE and `a' can't epsilon transit to
1610 the LAST_NODE, we throw away the node `a'.
1611 2. When 0 <= STR_IDX < MATCH_LAST and `a' accepts
1612 string `s' and transit to `b':
1613 i. If 'b' isn't in the STATE_LOG[STR_IDX+strlen('s')], we throw
1615 ii. If 'b' is in the STATE_LOG[STR_IDX+strlen('s')] but 'b' is
1616 thrown away, we throw away the node `a'.
1617 3. When 0 <= STR_IDX < MATCH_LAST and 'a' epsilon transit to 'b':
1618 i. If 'b' isn't in the STATE_LOG[STR_IDX], we throw away the
1620 ii. If 'b' is in the STATE_LOG[STR_IDX] but 'b' is thrown away,
1621 we throw away the node `a'. */
1623 #define STATE_NODE_CONTAINS(state,node) \
1624 ((state) != NULL && re_node_set_contains (&(state)->nodes, node))
1626 static reg_errcode_t
1628 sift_states_backward (const re_match_context_t *mctx, re_sift_context_t *sctx)
1632 Idx str_idx = sctx->last_str_idx;
1633 re_node_set cur_dest;
1636 assert (mctx->state_log != NULL && mctx->state_log[str_idx] != NULL);
1639 /* Build sifted state_log[str_idx]. It has the nodes which can epsilon
1640 transit to the last_node and the last_node itself. */
1641 err = re_node_set_init_1 (&cur_dest, sctx->last_node);
1642 if (BE (err != REG_NOERROR, 0))
1644 err = update_cur_sifted_state (mctx, sctx, str_idx, &cur_dest);
1645 if (BE (err != REG_NOERROR, 0))
1648 /* Then check each states in the state_log. */
1651 /* Update counters. */
1652 null_cnt = (sctx->sifted_states[str_idx] == NULL) ? null_cnt + 1 : 0;
1653 if (null_cnt > mctx->max_mb_elem_len)
1655 memset (sctx->sifted_states, '\0',
1656 sizeof (re_dfastate_t *) * str_idx);
1657 re_node_set_free (&cur_dest);
1660 re_node_set_empty (&cur_dest);
1663 if (mctx->state_log[str_idx])
1665 err = build_sifted_states (mctx, sctx, str_idx, &cur_dest);
1666 if (BE (err != REG_NOERROR, 0))
1670 /* Add all the nodes which satisfy the following conditions:
1671 - It can epsilon transit to a node in CUR_DEST.
1673 And update state_log. */
1674 err = update_cur_sifted_state (mctx, sctx, str_idx, &cur_dest);
1675 if (BE (err != REG_NOERROR, 0))
1680 re_node_set_free (&cur_dest);
1684 static reg_errcode_t
1686 build_sifted_states (const re_match_context_t *mctx, re_sift_context_t *sctx,
1687 Idx str_idx, re_node_set *cur_dest)
1689 const re_dfa_t *const dfa = mctx->dfa;
1690 const re_node_set *cur_src = &mctx->state_log[str_idx]->non_eps_nodes;
1693 /* Then build the next sifted state.
1694 We build the next sifted state on `cur_dest', and update
1695 `sifted_states[str_idx]' with `cur_dest'.
1697 `cur_dest' is the sifted state from `state_log[str_idx + 1]'.
1698 `cur_src' points the node_set of the old `state_log[str_idx]'
1699 (with the epsilon nodes pre-filtered out). */
1700 for (i = 0; i < cur_src->nelem; i++)
1702 Idx prev_node = cur_src->elems[i];
1707 re_token_type_t type = dfa->nodes[prev_node].type;
1708 assert (!IS_EPSILON_NODE (type));
1710 #ifdef RE_ENABLE_I18N
1711 /* If the node may accept `multi byte'. */
1712 if (dfa->nodes[prev_node].accept_mb)
1713 naccepted = sift_states_iter_mb (mctx, sctx, prev_node,
1714 str_idx, sctx->last_str_idx);
1715 #endif /* RE_ENABLE_I18N */
1717 /* We don't check backreferences here.
1718 See update_cur_sifted_state(). */
1720 && check_node_accept (mctx, dfa->nodes + prev_node, str_idx)
1721 && STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + 1],
1722 dfa->nexts[prev_node]))
1728 if (sctx->limits.nelem)
1730 Idx to_idx = str_idx + naccepted;
1731 if (check_dst_limits (mctx, &sctx->limits,
1732 dfa->nexts[prev_node], to_idx,
1733 prev_node, str_idx))
1736 ok = re_node_set_insert (cur_dest, prev_node);
1744 /* Helper functions. */
1746 static reg_errcode_t
1748 clean_state_log_if_needed (re_match_context_t *mctx, Idx next_state_log_idx)
1750 Idx top = mctx->state_log_top;
1752 if (next_state_log_idx >= mctx->input.bufs_len
1753 || (next_state_log_idx >= mctx->input.valid_len
1754 && mctx->input.valid_len < mctx->input.len))
1757 err = extend_buffers (mctx);
1758 if (BE (err != REG_NOERROR, 0))
1762 if (top < next_state_log_idx)
1764 memset (mctx->state_log + top + 1, '\0',
1765 sizeof (re_dfastate_t *) * (next_state_log_idx - top));
1766 mctx->state_log_top = next_state_log_idx;
1771 static reg_errcode_t
1773 merge_state_array (const re_dfa_t *dfa, re_dfastate_t **dst,
1774 re_dfastate_t **src, Idx num)
1778 for (st_idx = 0; st_idx < num; ++st_idx)
1780 if (dst[st_idx] == NULL)
1781 dst[st_idx] = src[st_idx];
1782 else if (src[st_idx] != NULL)
1784 re_node_set merged_set;
1785 err = re_node_set_init_union (&merged_set, &dst[st_idx]->nodes,
1786 &src[st_idx]->nodes);
1787 if (BE (err != REG_NOERROR, 0))
1789 dst[st_idx] = re_acquire_state (&err, dfa, &merged_set);
1790 re_node_set_free (&merged_set);
1791 if (BE (err != REG_NOERROR, 0))
1798 static reg_errcode_t
1800 update_cur_sifted_state (const re_match_context_t *mctx,
1801 re_sift_context_t *sctx, Idx str_idx,
1802 re_node_set *dest_nodes)
1804 const re_dfa_t *const dfa = mctx->dfa;
1805 reg_errcode_t err = REG_NOERROR;
1806 const re_node_set *candidates;
1807 candidates = ((mctx->state_log[str_idx] == NULL) ? NULL
1808 : &mctx->state_log[str_idx]->nodes);
1810 if (dest_nodes->nelem == 0)
1811 sctx->sifted_states[str_idx] = NULL;
1816 /* At first, add the nodes which can epsilon transit to a node in
1818 err = add_epsilon_src_nodes (dfa, dest_nodes, candidates);
1819 if (BE (err != REG_NOERROR, 0))
1822 /* Then, check the limitations in the current sift_context. */
1823 if (sctx->limits.nelem)
1825 err = check_subexp_limits (dfa, dest_nodes, candidates, &sctx->limits,
1826 mctx->bkref_ents, str_idx);
1827 if (BE (err != REG_NOERROR, 0))
1832 sctx->sifted_states[str_idx] = re_acquire_state (&err, dfa, dest_nodes);
1833 if (BE (err != REG_NOERROR, 0))
1837 if (candidates && mctx->state_log[str_idx]->has_backref)
1839 err = sift_states_bkref (mctx, sctx, str_idx, candidates);
1840 if (BE (err != REG_NOERROR, 0))
1846 static reg_errcode_t
1848 add_epsilon_src_nodes (const re_dfa_t *dfa, re_node_set *dest_nodes,
1849 const re_node_set *candidates)
1851 reg_errcode_t err = REG_NOERROR;
1854 re_dfastate_t *state = re_acquire_state (&err, dfa, dest_nodes);
1855 if (BE (err != REG_NOERROR, 0))
1858 if (!state->inveclosure.alloc)
1860 err = re_node_set_alloc (&state->inveclosure, dest_nodes->nelem);
1861 if (BE (err != REG_NOERROR, 0))
1863 for (i = 0; i < dest_nodes->nelem; i++)
1864 re_node_set_merge (&state->inveclosure,
1865 dfa->inveclosures + dest_nodes->elems[i]);
1867 return re_node_set_add_intersect (dest_nodes, candidates,
1868 &state->inveclosure);
1871 static reg_errcode_t
1873 sub_epsilon_src_nodes (const re_dfa_t *dfa, Idx node, re_node_set *dest_nodes,
1874 const re_node_set *candidates)
1878 re_node_set *inv_eclosure = dfa->inveclosures + node;
1879 re_node_set except_nodes;
1880 re_node_set_init_empty (&except_nodes);
1881 for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx)
1883 Idx cur_node = inv_eclosure->elems[ecl_idx];
1884 if (cur_node == node)
1886 if (IS_EPSILON_NODE (dfa->nodes[cur_node].type))
1888 Idx edst1 = dfa->edests[cur_node].elems[0];
1889 Idx edst2 = ((dfa->edests[cur_node].nelem > 1)
1890 ? dfa->edests[cur_node].elems[1] : REG_MISSING);
1891 if ((!re_node_set_contains (inv_eclosure, edst1)
1892 && re_node_set_contains (dest_nodes, edst1))
1893 || (REG_VALID_NONZERO_INDEX (edst2)
1894 && !re_node_set_contains (inv_eclosure, edst2)
1895 && re_node_set_contains (dest_nodes, edst2)))
1897 err = re_node_set_add_intersect (&except_nodes, candidates,
1898 dfa->inveclosures + cur_node);
1899 if (BE (err != REG_NOERROR, 0))
1901 re_node_set_free (&except_nodes);
1907 for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx)
1909 Idx cur_node = inv_eclosure->elems[ecl_idx];
1910 if (!re_node_set_contains (&except_nodes, cur_node))
1912 Idx idx = re_node_set_contains (dest_nodes, cur_node) - 1;
1913 re_node_set_remove_at (dest_nodes, idx);
1916 re_node_set_free (&except_nodes);
1922 check_dst_limits (const re_match_context_t *mctx, const re_node_set *limits,
1923 Idx dst_node, Idx dst_idx, Idx src_node, Idx src_idx)
1925 const re_dfa_t *const dfa = mctx->dfa;
1926 Idx lim_idx, src_pos, dst_pos;
1928 Idx dst_bkref_idx = search_cur_bkref_entry (mctx, dst_idx);
1929 Idx src_bkref_idx = search_cur_bkref_entry (mctx, src_idx);
1930 for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx)
1933 struct re_backref_cache_entry *ent;
1934 ent = mctx->bkref_ents + limits->elems[lim_idx];
1935 subexp_idx = dfa->nodes[ent->node].opr.idx;
1937 dst_pos = check_dst_limits_calc_pos (mctx, limits->elems[lim_idx],
1938 subexp_idx, dst_node, dst_idx,
1940 src_pos = check_dst_limits_calc_pos (mctx, limits->elems[lim_idx],
1941 subexp_idx, src_node, src_idx,
1945 <src> <dst> ( <subexp> )
1946 ( <subexp> ) <src> <dst>
1947 ( <subexp1> <src> <subexp2> <dst> <subexp3> ) */
1948 if (src_pos == dst_pos)
1949 continue; /* This is unrelated limitation. */
1958 check_dst_limits_calc_pos_1 (const re_match_context_t *mctx, int boundaries,
1959 Idx subexp_idx, Idx from_node, Idx bkref_idx)
1961 const re_dfa_t *const dfa = mctx->dfa;
1962 const re_node_set *eclosures = dfa->eclosures + from_node;
1965 /* Else, we are on the boundary: examine the nodes on the epsilon
1967 for (node_idx = 0; node_idx < eclosures->nelem; ++node_idx)
1969 Idx node = eclosures->elems[node_idx];
1970 switch (dfa->nodes[node].type)
1973 if (bkref_idx != REG_MISSING)
1975 struct re_backref_cache_entry *ent = mctx->bkref_ents + bkref_idx;
1981 if (ent->node != node)
1984 if (subexp_idx < BITSET_WORD_BITS
1985 && !(ent->eps_reachable_subexps_map
1986 & ((bitset_word_t) 1 << subexp_idx)))
1989 /* Recurse trying to reach the OP_OPEN_SUBEXP and
1990 OP_CLOSE_SUBEXP cases below. But, if the
1991 destination node is the same node as the source
1992 node, don't recurse because it would cause an
1993 infinite loop: a regex that exhibits this behavior
1995 dst = dfa->edests[node].elems[0];
1996 if (dst == from_node)
2000 else /* if (boundaries & 2) */
2005 check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx,
2007 if (cpos == -1 /* && (boundaries & 1) */)
2009 if (cpos == 0 && (boundaries & 2))
2012 if (subexp_idx < BITSET_WORD_BITS)
2013 ent->eps_reachable_subexps_map
2014 &= ~((bitset_word_t) 1 << subexp_idx);
2016 while (ent++->more);
2020 case OP_OPEN_SUBEXP:
2021 if ((boundaries & 1) && subexp_idx == dfa->nodes[node].opr.idx)
2025 case OP_CLOSE_SUBEXP:
2026 if ((boundaries & 2) && subexp_idx == dfa->nodes[node].opr.idx)
2035 return (boundaries & 2) ? 1 : 0;
2040 check_dst_limits_calc_pos (const re_match_context_t *mctx, Idx limit,
2041 Idx subexp_idx, Idx from_node, Idx str_idx,
2044 struct re_backref_cache_entry *lim = mctx->bkref_ents + limit;
2047 /* If we are outside the range of the subexpression, return -1 or 1. */
2048 if (str_idx < lim->subexp_from)
2051 if (lim->subexp_to < str_idx)
2054 /* If we are within the subexpression, return 0. */
2055 boundaries = (str_idx == lim->subexp_from);
2056 boundaries |= (str_idx == lim->subexp_to) << 1;
2057 if (boundaries == 0)
2060 /* Else, examine epsilon closure. */
2061 return check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx,
2062 from_node, bkref_idx);
2065 /* Check the limitations of sub expressions LIMITS, and remove the nodes
2066 which are against limitations from DEST_NODES. */
2068 static reg_errcode_t
2070 check_subexp_limits (const re_dfa_t *dfa, re_node_set *dest_nodes,
2071 const re_node_set *candidates, re_node_set *limits,
2072 struct re_backref_cache_entry *bkref_ents, Idx str_idx)
2075 Idx node_idx, lim_idx;
2077 for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx)
2080 struct re_backref_cache_entry *ent;
2081 ent = bkref_ents + limits->elems[lim_idx];
2083 if (str_idx <= ent->subexp_from || ent->str_idx < str_idx)
2084 continue; /* This is unrelated limitation. */
2086 subexp_idx = dfa->nodes[ent->node].opr.idx;
2087 if (ent->subexp_to == str_idx)
2089 Idx ops_node = REG_MISSING;
2090 Idx cls_node = REG_MISSING;
2091 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2093 Idx node = dest_nodes->elems[node_idx];
2094 re_token_type_t type = dfa->nodes[node].type;
2095 if (type == OP_OPEN_SUBEXP
2096 && subexp_idx == dfa->nodes[node].opr.idx)
2098 else if (type == OP_CLOSE_SUBEXP
2099 && subexp_idx == dfa->nodes[node].opr.idx)
2103 /* Check the limitation of the open subexpression. */
2104 /* Note that (ent->subexp_to = str_idx != ent->subexp_from). */
2105 if (REG_VALID_INDEX (ops_node))
2107 err = sub_epsilon_src_nodes (dfa, ops_node, dest_nodes,
2109 if (BE (err != REG_NOERROR, 0))
2113 /* Check the limitation of the close subexpression. */
2114 if (REG_VALID_INDEX (cls_node))
2115 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2117 Idx node = dest_nodes->elems[node_idx];
2118 if (!re_node_set_contains (dfa->inveclosures + node,
2120 && !re_node_set_contains (dfa->eclosures + node,
2123 /* It is against this limitation.
2124 Remove it form the current sifted state. */
2125 err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2127 if (BE (err != REG_NOERROR, 0))
2133 else /* (ent->subexp_to != str_idx) */
2135 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2137 Idx node = dest_nodes->elems[node_idx];
2138 re_token_type_t type = dfa->nodes[node].type;
2139 if (type == OP_CLOSE_SUBEXP || type == OP_OPEN_SUBEXP)
2141 if (subexp_idx != dfa->nodes[node].opr.idx)
2143 /* It is against this limitation.
2144 Remove it form the current sifted state. */
2145 err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2147 if (BE (err != REG_NOERROR, 0))
2156 static reg_errcode_t
2158 sift_states_bkref (const re_match_context_t *mctx, re_sift_context_t *sctx,
2159 Idx str_idx, const re_node_set *candidates)
2161 const re_dfa_t *const dfa = mctx->dfa;
2164 re_sift_context_t local_sctx;
2165 Idx first_idx = search_cur_bkref_entry (mctx, str_idx);
2167 if (first_idx == REG_MISSING)
2170 local_sctx.sifted_states = NULL; /* Mark that it hasn't been initialized. */
2172 for (node_idx = 0; node_idx < candidates->nelem; ++node_idx)
2175 re_token_type_t type;
2176 struct re_backref_cache_entry *entry;
2177 node = candidates->elems[node_idx];
2178 type = dfa->nodes[node].type;
2179 /* Avoid infinite loop for the REs like "()\1+". */
2180 if (node == sctx->last_node && str_idx == sctx->last_str_idx)
2182 if (type != OP_BACK_REF)
2185 entry = mctx->bkref_ents + first_idx;
2186 enabled_idx = first_idx;
2193 re_dfastate_t *cur_state;
2195 if (entry->node != node)
2197 subexp_len = entry->subexp_to - entry->subexp_from;
2198 to_idx = str_idx + subexp_len;
2199 dst_node = (subexp_len ? dfa->nexts[node]
2200 : dfa->edests[node].elems[0]);
2202 if (to_idx > sctx->last_str_idx
2203 || sctx->sifted_states[to_idx] == NULL
2204 || !STATE_NODE_CONTAINS (sctx->sifted_states[to_idx], dst_node)
2205 || check_dst_limits (mctx, &sctx->limits, node,
2206 str_idx, dst_node, to_idx))
2209 if (local_sctx.sifted_states == NULL)
2212 err = re_node_set_init_copy (&local_sctx.limits, &sctx->limits);
2213 if (BE (err != REG_NOERROR, 0))
2216 local_sctx.last_node = node;
2217 local_sctx.last_str_idx = str_idx;
2218 ok = re_node_set_insert (&local_sctx.limits, enabled_idx);
2224 cur_state = local_sctx.sifted_states[str_idx];
2225 err = sift_states_backward (mctx, &local_sctx);
2226 if (BE (err != REG_NOERROR, 0))
2228 if (sctx->limited_states != NULL)
2230 err = merge_state_array (dfa, sctx->limited_states,
2231 local_sctx.sifted_states,
2233 if (BE (err != REG_NOERROR, 0))
2236 local_sctx.sifted_states[str_idx] = cur_state;
2237 re_node_set_remove (&local_sctx.limits, enabled_idx);
2239 /* mctx->bkref_ents may have changed, reload the pointer. */
2240 entry = mctx->bkref_ents + enabled_idx;
2242 while (enabled_idx++, entry++->more);
2246 if (local_sctx.sifted_states != NULL)
2248 re_node_set_free (&local_sctx.limits);
2255 #ifdef RE_ENABLE_I18N
2258 sift_states_iter_mb (const re_match_context_t *mctx, re_sift_context_t *sctx,
2259 Idx node_idx, Idx str_idx, Idx max_str_idx)
2261 const re_dfa_t *const dfa = mctx->dfa;
2263 /* Check the node can accept `multi byte'. */
2264 naccepted = check_node_accept_bytes (dfa, node_idx, &mctx->input, str_idx);
2265 if (naccepted > 0 && str_idx + naccepted <= max_str_idx &&
2266 !STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + naccepted],
2267 dfa->nexts[node_idx]))
2268 /* The node can't accept the `multi byte', or the
2269 destination was already thrown away, then the node
2270 could't accept the current input `multi byte'. */
2272 /* Otherwise, it is sure that the node could accept
2273 `naccepted' bytes input. */
2276 #endif /* RE_ENABLE_I18N */
2279 /* Functions for state transition. */
2281 /* Return the next state to which the current state STATE will transit by
2282 accepting the current input byte, and update STATE_LOG if necessary.
2283 If STATE can accept a multibyte char/collating element/back reference
2284 update the destination of STATE_LOG. */
2286 static re_dfastate_t *
2288 transit_state (reg_errcode_t *err, re_match_context_t *mctx,
2289 re_dfastate_t *state)
2291 re_dfastate_t **trtable;
2294 #ifdef RE_ENABLE_I18N
2295 /* If the current state can accept multibyte. */
2296 if (BE (state->accept_mb, 0))
2298 *err = transit_state_mb (mctx, state);
2299 if (BE (*err != REG_NOERROR, 0))
2302 #endif /* RE_ENABLE_I18N */
2304 /* Then decide the next state with the single byte. */
2307 /* don't use transition table */
2308 return transit_state_sb (err, mctx, state);
2311 /* Use transition table */
2312 ch = re_string_fetch_byte (&mctx->input);
2315 trtable = state->trtable;
2316 if (BE (trtable != NULL, 1))
2319 trtable = state->word_trtable;
2320 if (BE (trtable != NULL, 1))
2322 unsigned int context;
2324 = re_string_context_at (&mctx->input,
2325 re_string_cur_idx (&mctx->input) - 1,
2327 if (IS_WORD_CONTEXT (context))
2328 return trtable[ch + SBC_MAX];
2333 if (!build_trtable (mctx->dfa, state))
2339 /* Retry, we now have a transition table. */
2343 /* Update the state_log if we need */
2344 static re_dfastate_t *
2346 merge_state_with_log (reg_errcode_t *err, re_match_context_t *mctx,
2347 re_dfastate_t *next_state)
2349 const re_dfa_t *const dfa = mctx->dfa;
2350 Idx cur_idx = re_string_cur_idx (&mctx->input);
2352 if (cur_idx > mctx->state_log_top)
2354 mctx->state_log[cur_idx] = next_state;
2355 mctx->state_log_top = cur_idx;
2357 else if (mctx->state_log[cur_idx] == 0)
2359 mctx->state_log[cur_idx] = next_state;
2363 re_dfastate_t *pstate;
2364 unsigned int context;
2365 re_node_set next_nodes, *log_nodes, *table_nodes = NULL;
2366 /* If (state_log[cur_idx] != 0), it implies that cur_idx is
2367 the destination of a multibyte char/collating element/
2368 back reference. Then the next state is the union set of
2369 these destinations and the results of the transition table. */
2370 pstate = mctx->state_log[cur_idx];
2371 log_nodes = pstate->entrance_nodes;
2372 if (next_state != NULL)
2374 table_nodes = next_state->entrance_nodes;
2375 *err = re_node_set_init_union (&next_nodes, table_nodes,
2377 if (BE (*err != REG_NOERROR, 0))
2381 next_nodes = *log_nodes;
2382 /* Note: We already add the nodes of the initial state,
2383 then we don't need to add them here. */
2385 context = re_string_context_at (&mctx->input,
2386 re_string_cur_idx (&mctx->input) - 1,
2388 next_state = mctx->state_log[cur_idx]
2389 = re_acquire_state_context (err, dfa, &next_nodes, context);
2390 /* We don't need to check errors here, since the return value of
2391 this function is next_state and ERR is already set. */
2393 if (table_nodes != NULL)
2394 re_node_set_free (&next_nodes);
2397 if (BE (dfa->nbackref, 0) && next_state != NULL)
2399 /* Check OP_OPEN_SUBEXP in the current state in case that we use them
2400 later. We must check them here, since the back references in the
2401 next state might use them. */
2402 *err = check_subexp_matching_top (mctx, &next_state->nodes,
2404 if (BE (*err != REG_NOERROR, 0))
2407 /* If the next state has back references. */
2408 if (next_state->has_backref)
2410 *err = transit_state_bkref (mctx, &next_state->nodes);
2411 if (BE (*err != REG_NOERROR, 0))
2413 next_state = mctx->state_log[cur_idx];
2420 /* Skip bytes in the input that correspond to part of a
2421 multi-byte match, then look in the log for a state
2422 from which to restart matching. */
2423 static re_dfastate_t *
2425 find_recover_state (reg_errcode_t *err, re_match_context_t *mctx)
2427 re_dfastate_t *cur_state;
2430 Idx max = mctx->state_log_top;
2431 Idx cur_str_idx = re_string_cur_idx (&mctx->input);
2435 if (++cur_str_idx > max)
2437 re_string_skip_bytes (&mctx->input, 1);
2439 while (mctx->state_log[cur_str_idx] == NULL);
2441 cur_state = merge_state_with_log (err, mctx, NULL);
2443 while (*err == REG_NOERROR && cur_state == NULL);
2447 /* Helper functions for transit_state. */
2449 /* From the node set CUR_NODES, pick up the nodes whose types are
2450 OP_OPEN_SUBEXP and which have corresponding back references in the regular
2451 expression. And register them to use them later for evaluating the
2452 correspoding back references. */
2454 static reg_errcode_t
2456 check_subexp_matching_top (re_match_context_t *mctx, re_node_set *cur_nodes,
2459 const re_dfa_t *const dfa = mctx->dfa;
2463 /* TODO: This isn't efficient.
2464 Because there might be more than one nodes whose types are
2465 OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
2468 for (node_idx = 0; node_idx < cur_nodes->nelem; ++node_idx)
2470 Idx node = cur_nodes->elems[node_idx];
2471 if (dfa->nodes[node].type == OP_OPEN_SUBEXP
2472 && dfa->nodes[node].opr.idx < BITSET_WORD_BITS
2473 && (dfa->used_bkref_map
2474 & ((bitset_word_t) 1 << dfa->nodes[node].opr.idx)))
2476 err = match_ctx_add_subtop (mctx, node, str_idx);
2477 if (BE (err != REG_NOERROR, 0))
2485 /* Return the next state to which the current state STATE will transit by
2486 accepting the current input byte. */
2488 static re_dfastate_t *
2489 transit_state_sb (reg_errcode_t *err, re_match_context_t *mctx,
2490 re_dfastate_t *state)
2492 const re_dfa_t *const dfa = mctx->dfa;
2493 re_node_set next_nodes;
2494 re_dfastate_t *next_state;
2495 Idx node_cnt, cur_str_idx = re_string_cur_idx (&mctx->input);
2496 unsigned int context;
2498 *err = re_node_set_alloc (&next_nodes, state->nodes.nelem + 1);
2499 if (BE (*err != REG_NOERROR, 0))
2501 for (node_cnt = 0; node_cnt < state->nodes.nelem; ++node_cnt)
2503 Idx cur_node = state->nodes.elems[node_cnt];
2504 if (check_node_accept (mctx, dfa->nodes + cur_node, cur_str_idx))
2506 *err = re_node_set_merge (&next_nodes,
2507 dfa->eclosures + dfa->nexts[cur_node]);
2508 if (BE (*err != REG_NOERROR, 0))
2510 re_node_set_free (&next_nodes);
2515 context = re_string_context_at (&mctx->input, cur_str_idx, mctx->eflags);
2516 next_state = re_acquire_state_context (err, dfa, &next_nodes, context);
2517 /* We don't need to check errors here, since the return value of
2518 this function is next_state and ERR is already set. */
2520 re_node_set_free (&next_nodes);
2521 re_string_skip_bytes (&mctx->input, 1);
2526 #ifdef RE_ENABLE_I18N
2527 static reg_errcode_t
2529 transit_state_mb (re_match_context_t *mctx, re_dfastate_t *pstate)
2531 const re_dfa_t *const dfa = mctx->dfa;
2535 for (i = 0; i < pstate->nodes.nelem; ++i)
2537 re_node_set dest_nodes, *new_nodes;
2538 Idx cur_node_idx = pstate->nodes.elems[i];
2541 unsigned int context;
2542 re_dfastate_t *dest_state;
2544 if (!dfa->nodes[cur_node_idx].accept_mb)
2547 if (dfa->nodes[cur_node_idx].constraint)
2549 context = re_string_context_at (&mctx->input,
2550 re_string_cur_idx (&mctx->input),
2552 if (NOT_SATISFY_NEXT_CONSTRAINT (dfa->nodes[cur_node_idx].constraint,
2557 /* How many bytes the node can accept? */
2558 naccepted = check_node_accept_bytes (dfa, cur_node_idx, &mctx->input,
2559 re_string_cur_idx (&mctx->input));
2563 /* The node can accepts `naccepted' bytes. */
2564 dest_idx = re_string_cur_idx (&mctx->input) + naccepted;
2565 mctx->max_mb_elem_len = ((mctx->max_mb_elem_len < naccepted) ? naccepted
2566 : mctx->max_mb_elem_len);
2567 err = clean_state_log_if_needed (mctx, dest_idx);
2568 if (BE (err != REG_NOERROR, 0))
2571 assert (dfa->nexts[cur_node_idx] != REG_MISSING);
2573 new_nodes = dfa->eclosures + dfa->nexts[cur_node_idx];
2575 dest_state = mctx->state_log[dest_idx];
2576 if (dest_state == NULL)
2577 dest_nodes = *new_nodes;
2580 err = re_node_set_init_union (&dest_nodes,
2581 dest_state->entrance_nodes, new_nodes);
2582 if (BE (err != REG_NOERROR, 0))
2585 context = re_string_context_at (&mctx->input, dest_idx - 1,
2587 mctx->state_log[dest_idx]
2588 = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2589 if (dest_state != NULL)
2590 re_node_set_free (&dest_nodes);
2591 if (BE (mctx->state_log[dest_idx] == NULL && err != REG_NOERROR, 0))
2596 #endif /* RE_ENABLE_I18N */
2598 static reg_errcode_t
2600 transit_state_bkref (re_match_context_t *mctx, const re_node_set *nodes)
2602 const re_dfa_t *const dfa = mctx->dfa;
2605 Idx cur_str_idx = re_string_cur_idx (&mctx->input);
2607 for (i = 0; i < nodes->nelem; ++i)
2609 Idx dest_str_idx, prev_nelem, bkc_idx;
2610 Idx node_idx = nodes->elems[i];
2611 unsigned int context;
2612 const re_token_t *node = dfa->nodes + node_idx;
2613 re_node_set *new_dest_nodes;
2615 /* Check whether `node' is a backreference or not. */
2616 if (node->type != OP_BACK_REF)
2619 if (node->constraint)
2621 context = re_string_context_at (&mctx->input, cur_str_idx,
2623 if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
2627 /* `node' is a backreference.
2628 Check the substring which the substring matched. */
2629 bkc_idx = mctx->nbkref_ents;
2630 err = get_subexp (mctx, node_idx, cur_str_idx);
2631 if (BE (err != REG_NOERROR, 0))
2634 /* And add the epsilon closures (which is `new_dest_nodes') of
2635 the backreference to appropriate state_log. */
2637 assert (dfa->nexts[node_idx] != REG_MISSING);
2639 for (; bkc_idx < mctx->nbkref_ents; ++bkc_idx)
2642 re_dfastate_t *dest_state;
2643 struct re_backref_cache_entry *bkref_ent;
2644 bkref_ent = mctx->bkref_ents + bkc_idx;
2645 if (bkref_ent->node != node_idx || bkref_ent->str_idx != cur_str_idx)
2647 subexp_len = bkref_ent->subexp_to - bkref_ent->subexp_from;
2648 new_dest_nodes = (subexp_len == 0
2649 ? dfa->eclosures + dfa->edests[node_idx].elems[0]
2650 : dfa->eclosures + dfa->nexts[node_idx]);
2651 dest_str_idx = (cur_str_idx + bkref_ent->subexp_to
2652 - bkref_ent->subexp_from);
2653 context = re_string_context_at (&mctx->input, dest_str_idx - 1,
2655 dest_state = mctx->state_log[dest_str_idx];
2656 prev_nelem = ((mctx->state_log[cur_str_idx] == NULL) ? 0
2657 : mctx->state_log[cur_str_idx]->nodes.nelem);
2658 /* Add `new_dest_node' to state_log. */
2659 if (dest_state == NULL)
2661 mctx->state_log[dest_str_idx]
2662 = re_acquire_state_context (&err, dfa, new_dest_nodes,
2664 if (BE (mctx->state_log[dest_str_idx] == NULL
2665 && err != REG_NOERROR, 0))
2670 re_node_set dest_nodes;
2671 err = re_node_set_init_union (&dest_nodes,
2672 dest_state->entrance_nodes,
2674 if (BE (err != REG_NOERROR, 0))
2676 re_node_set_free (&dest_nodes);
2679 mctx->state_log[dest_str_idx]
2680 = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2681 re_node_set_free (&dest_nodes);
2682 if (BE (mctx->state_log[dest_str_idx] == NULL
2683 && err != REG_NOERROR, 0))
2686 /* We need to check recursively if the backreference can epsilon
2689 && mctx->state_log[cur_str_idx]->nodes.nelem > prev_nelem)
2691 err = check_subexp_matching_top (mctx, new_dest_nodes,
2693 if (BE (err != REG_NOERROR, 0))
2695 err = transit_state_bkref (mctx, new_dest_nodes);
2696 if (BE (err != REG_NOERROR, 0))
2706 /* Enumerate all the candidates which the backreference BKREF_NODE can match
2707 at BKREF_STR_IDX, and register them by match_ctx_add_entry().
2708 Note that we might collect inappropriate candidates here.
2709 However, the cost of checking them strictly here is too high, then we
2710 delay these checking for prune_impossible_nodes(). */
2712 static reg_errcode_t
2714 get_subexp (re_match_context_t *mctx, Idx bkref_node, Idx bkref_str_idx)
2716 const re_dfa_t *const dfa = mctx->dfa;
2717 Idx subexp_num, sub_top_idx;
2718 const char *buf = (const char *) re_string_get_buffer (&mctx->input);
2719 /* Return if we have already checked BKREF_NODE at BKREF_STR_IDX. */
2720 Idx cache_idx = search_cur_bkref_entry (mctx, bkref_str_idx);
2721 if (cache_idx != REG_MISSING)
2723 const struct re_backref_cache_entry *entry
2724 = mctx->bkref_ents + cache_idx;
2726 if (entry->node == bkref_node)
2727 return REG_NOERROR; /* We already checked it. */
2728 while (entry++->more);
2731 subexp_num = dfa->nodes[bkref_node].opr.idx;
2733 /* For each sub expression */
2734 for (sub_top_idx = 0; sub_top_idx < mctx->nsub_tops; ++sub_top_idx)
2737 re_sub_match_top_t *sub_top = mctx->sub_tops[sub_top_idx];
2738 re_sub_match_last_t *sub_last;
2739 Idx sub_last_idx, sl_str, bkref_str_off;
2741 if (dfa->nodes[sub_top->node].opr.idx != subexp_num)
2742 continue; /* It isn't related. */
2744 sl_str = sub_top->str_idx;
2745 bkref_str_off = bkref_str_idx;
2746 /* At first, check the last node of sub expressions we already
2748 for (sub_last_idx = 0; sub_last_idx < sub_top->nlasts; ++sub_last_idx)
2750 regoff_t sl_str_diff;
2751 sub_last = sub_top->lasts[sub_last_idx];
2752 sl_str_diff = sub_last->str_idx - sl_str;
2753 /* The matched string by the sub expression match with the substring
2754 at the back reference? */
2755 if (sl_str_diff > 0)
2757 if (BE (bkref_str_off + sl_str_diff > mctx->input.valid_len, 0))
2759 /* Not enough chars for a successful match. */
2760 if (bkref_str_off + sl_str_diff > mctx->input.len)
2763 err = clean_state_log_if_needed (mctx,
2766 if (BE (err != REG_NOERROR, 0))
2768 buf = (const char *) re_string_get_buffer (&mctx->input);
2770 if (memcmp (buf + bkref_str_off, buf + sl_str, sl_str_diff) != 0)
2771 /* We don't need to search this sub expression any more. */
2774 bkref_str_off += sl_str_diff;
2775 sl_str += sl_str_diff;
2776 err = get_subexp_sub (mctx, sub_top, sub_last, bkref_node,
2779 /* Reload buf, since the preceding call might have reallocated
2781 buf = (const char *) re_string_get_buffer (&mctx->input);
2783 if (err == REG_NOMATCH)
2785 if (BE (err != REG_NOERROR, 0))
2789 if (sub_last_idx < sub_top->nlasts)
2791 if (sub_last_idx > 0)
2793 /* Then, search for the other last nodes of the sub expression. */
2794 for (; sl_str <= bkref_str_idx; ++sl_str)
2797 regoff_t sl_str_off;
2798 const re_node_set *nodes;
2799 sl_str_off = sl_str - sub_top->str_idx;
2800 /* The matched string by the sub expression match with the substring
2801 at the back reference? */
2804 if (BE (bkref_str_off >= mctx->input.valid_len, 0))
2806 /* If we are at the end of the input, we cannot match. */
2807 if (bkref_str_off >= mctx->input.len)
2810 err = extend_buffers (mctx);
2811 if (BE (err != REG_NOERROR, 0))
2814 buf = (const char *) re_string_get_buffer (&mctx->input);
2816 if (buf [bkref_str_off++] != buf[sl_str - 1])
2817 break; /* We don't need to search this sub expression
2820 if (mctx->state_log[sl_str] == NULL)
2822 /* Does this state have a ')' of the sub expression? */
2823 nodes = &mctx->state_log[sl_str]->nodes;
2824 cls_node = find_subexp_node (dfa, nodes, subexp_num,
2826 if (cls_node == REG_MISSING)
2828 if (sub_top->path == NULL)
2830 sub_top->path = calloc (sizeof (state_array_t),
2831 sl_str - sub_top->str_idx + 1);
2832 if (sub_top->path == NULL)
2835 /* Can the OP_OPEN_SUBEXP node arrive the OP_CLOSE_SUBEXP node
2836 in the current context? */
2837 err = check_arrival (mctx, sub_top->path, sub_top->node,
2838 sub_top->str_idx, cls_node, sl_str,
2840 if (err == REG_NOMATCH)
2842 if (BE (err != REG_NOERROR, 0))
2844 sub_last = match_ctx_add_sublast (sub_top, cls_node, sl_str);
2845 if (BE (sub_last == NULL, 0))
2847 err = get_subexp_sub (mctx, sub_top, sub_last, bkref_node,
2849 if (err == REG_NOMATCH)
2856 /* Helper functions for get_subexp(). */
2858 /* Check SUB_LAST can arrive to the back reference BKREF_NODE at BKREF_STR.
2859 If it can arrive, register the sub expression expressed with SUB_TOP
2862 static reg_errcode_t
2864 get_subexp_sub (re_match_context_t *mctx, const re_sub_match_top_t *sub_top,
2865 re_sub_match_last_t *sub_last, Idx bkref_node, Idx bkref_str)
2869 /* Can the subexpression arrive the back reference? */
2870 err = check_arrival (mctx, &sub_last->path, sub_last->node,
2871 sub_last->str_idx, bkref_node, bkref_str,
2873 if (err != REG_NOERROR)
2875 err = match_ctx_add_entry (mctx, bkref_node, bkref_str, sub_top->str_idx,
2877 if (BE (err != REG_NOERROR, 0))
2879 to_idx = bkref_str + sub_last->str_idx - sub_top->str_idx;
2880 return clean_state_log_if_needed (mctx, to_idx);
2883 /* Find the first node which is '(' or ')' and whose index is SUBEXP_IDX.
2884 Search '(' if FL_OPEN, or search ')' otherwise.
2885 TODO: This function isn't efficient...
2886 Because there might be more than one nodes whose types are
2887 OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
2893 find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
2894 Idx subexp_idx, int type)
2897 for (cls_idx = 0; cls_idx < nodes->nelem; ++cls_idx)
2899 Idx cls_node = nodes->elems[cls_idx];
2900 const re_token_t *node = dfa->nodes + cls_node;
2901 if (node->type == type
2902 && node->opr.idx == subexp_idx)
2908 /* Check whether the node TOP_NODE at TOP_STR can arrive to the node
2909 LAST_NODE at LAST_STR. We record the path onto PATH since it will be
2911 Return REG_NOERROR if it can arrive, or REG_NOMATCH otherwise. */
2913 static reg_errcode_t
2915 check_arrival (re_match_context_t *mctx, state_array_t *path, Idx top_node,
2916 Idx top_str, Idx last_node, Idx last_str, int type)
2918 const re_dfa_t *const dfa = mctx->dfa;
2919 reg_errcode_t err = REG_NOERROR;
2920 Idx subexp_num, backup_cur_idx, str_idx, null_cnt;
2921 re_dfastate_t *cur_state = NULL;
2922 re_node_set *cur_nodes, next_nodes;
2923 re_dfastate_t **backup_state_log;
2924 unsigned int context;
2926 subexp_num = dfa->nodes[top_node].opr.idx;
2927 /* Extend the buffer if we need. */
2928 if (BE (path->alloc < last_str + mctx->max_mb_elem_len + 1, 0))
2930 re_dfastate_t **new_array;
2931 Idx old_alloc = path->alloc;
2932 Idx new_alloc = old_alloc + last_str + mctx->max_mb_elem_len + 1;
2933 if (BE (new_alloc < old_alloc, 0)
2934 || BE (SIZE_MAX / sizeof (re_dfastate_t *) < new_alloc, 0))
2936 new_array = re_realloc (path->array, re_dfastate_t *, new_alloc);
2937 if (BE (new_array == NULL, 0))
2939 path->array = new_array;
2940 path->alloc = new_alloc;
2941 memset (new_array + old_alloc, '\0',
2942 sizeof (re_dfastate_t *) * (path->alloc - old_alloc));
2945 str_idx = path->next_idx ? path->next_idx : top_str;
2947 /* Temporary modify MCTX. */
2948 backup_state_log = mctx->state_log;
2949 backup_cur_idx = mctx->input.cur_idx;
2950 mctx->state_log = path->array;
2951 mctx->input.cur_idx = str_idx;
2953 /* Setup initial node set. */
2954 context = re_string_context_at (&mctx->input, str_idx - 1, mctx->eflags);
2955 if (str_idx == top_str)
2957 err = re_node_set_init_1 (&next_nodes, top_node);
2958 if (BE (err != REG_NOERROR, 0))
2960 err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
2961 if (BE (err != REG_NOERROR, 0))
2963 re_node_set_free (&next_nodes);
2969 cur_state = mctx->state_log[str_idx];
2970 if (cur_state && cur_state->has_backref)
2972 err = re_node_set_init_copy (&next_nodes, &cur_state->nodes);
2973 if (BE (err != REG_NOERROR, 0))
2977 re_node_set_init_empty (&next_nodes);
2979 if (str_idx == top_str || (cur_state && cur_state->has_backref))
2981 if (next_nodes.nelem)
2983 err = expand_bkref_cache (mctx, &next_nodes, str_idx,
2985 if (BE (err != REG_NOERROR, 0))
2987 re_node_set_free (&next_nodes);
2991 cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
2992 if (BE (cur_state == NULL && err != REG_NOERROR, 0))
2994 re_node_set_free (&next_nodes);
2997 mctx->state_log[str_idx] = cur_state;
3000 for (null_cnt = 0; str_idx < last_str && null_cnt <= mctx->max_mb_elem_len;)
3002 re_node_set_empty (&next_nodes);
3003 if (mctx->state_log[str_idx + 1])
3005 err = re_node_set_merge (&next_nodes,
3006 &mctx->state_log[str_idx + 1]->nodes);
3007 if (BE (err != REG_NOERROR, 0))
3009 re_node_set_free (&next_nodes);
3015 err = check_arrival_add_next_nodes (mctx, str_idx,
3016 &cur_state->non_eps_nodes,
3018 if (BE (err != REG_NOERROR, 0))
3020 re_node_set_free (&next_nodes);
3025 if (next_nodes.nelem)
3027 err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
3028 if (BE (err != REG_NOERROR, 0))
3030 re_node_set_free (&next_nodes);
3033 err = expand_bkref_cache (mctx, &next_nodes, str_idx,
3035 if (BE (err != REG_NOERROR, 0))
3037 re_node_set_free (&next_nodes);
3041 context = re_string_context_at (&mctx->input, str_idx - 1, mctx->eflags);
3042 cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
3043 if (BE (cur_state == NULL && err != REG_NOERROR, 0))
3045 re_node_set_free (&next_nodes);
3048 mctx->state_log[str_idx] = cur_state;
3049 null_cnt = cur_state == NULL ? null_cnt + 1 : 0;
3051 re_node_set_free (&next_nodes);
3052 cur_nodes = (mctx->state_log[last_str] == NULL ? NULL
3053 : &mctx->state_log[last_str]->nodes);
3054 path->next_idx = str_idx;
3057 mctx->state_log = backup_state_log;
3058 mctx->input.cur_idx = backup_cur_idx;
3060 /* Then check the current node set has the node LAST_NODE. */
3061 if (cur_nodes != NULL && re_node_set_contains (cur_nodes, last_node))
3067 /* Helper functions for check_arrival. */
3069 /* Calculate the destination nodes of CUR_NODES at STR_IDX, and append them
3071 TODO: This function is similar to the functions transit_state*(),
3072 however this function has many additional works.
3073 Can't we unify them? */
3075 static reg_errcode_t
3077 check_arrival_add_next_nodes (re_match_context_t *mctx, Idx str_idx,
3078 re_node_set *cur_nodes, re_node_set *next_nodes)
3080 const re_dfa_t *const dfa = mctx->dfa;
3083 reg_errcode_t err = REG_NOERROR;
3084 re_node_set union_set;
3085 re_node_set_init_empty (&union_set);
3086 for (cur_idx = 0; cur_idx < cur_nodes->nelem; ++cur_idx)
3089 Idx cur_node = cur_nodes->elems[cur_idx];
3091 re_token_type_t type = dfa->nodes[cur_node].type;
3092 assert (!IS_EPSILON_NODE (type));
3094 #ifdef RE_ENABLE_I18N
3095 /* If the node may accept `multi byte'. */
3096 if (dfa->nodes[cur_node].accept_mb)
3098 naccepted = check_node_accept_bytes (dfa, cur_node, &mctx->input,
3102 re_dfastate_t *dest_state;
3103 Idx next_node = dfa->nexts[cur_node];
3104 Idx next_idx = str_idx + naccepted;
3105 dest_state = mctx->state_log[next_idx];
3106 re_node_set_empty (&union_set);
3109 err = re_node_set_merge (&union_set, &dest_state->nodes);
3110 if (BE (err != REG_NOERROR, 0))
3112 re_node_set_free (&union_set);
3116 ok = re_node_set_insert (&union_set, next_node);
3119 re_node_set_free (&union_set);
3122 mctx->state_log[next_idx] = re_acquire_state (&err, dfa,
3124 if (BE (mctx->state_log[next_idx] == NULL
3125 && err != REG_NOERROR, 0))
3127 re_node_set_free (&union_set);
3132 #endif /* RE_ENABLE_I18N */
3134 || check_node_accept (mctx, dfa->nodes + cur_node, str_idx))
3136 ok = re_node_set_insert (next_nodes, dfa->nexts[cur_node]);
3139 re_node_set_free (&union_set);
3144 re_node_set_free (&union_set);
3148 /* For all the nodes in CUR_NODES, add the epsilon closures of them to
3149 CUR_NODES, however exclude the nodes which are:
3150 - inside the sub expression whose number is EX_SUBEXP, if FL_OPEN.
3151 - out of the sub expression whose number is EX_SUBEXP, if !FL_OPEN.
3154 static reg_errcode_t
3156 check_arrival_expand_ecl (const re_dfa_t *dfa, re_node_set *cur_nodes,
3157 Idx ex_subexp, int type)
3160 Idx idx, outside_node;
3161 re_node_set new_nodes;
3163 assert (cur_nodes->nelem);
3165 err = re_node_set_alloc (&new_nodes, cur_nodes->nelem);
3166 if (BE (err != REG_NOERROR, 0))
3168 /* Create a new node set NEW_NODES with the nodes which are epsilon
3169 closures of the node in CUR_NODES. */
3171 for (idx = 0; idx < cur_nodes->nelem; ++idx)
3173 Idx cur_node = cur_nodes->elems[idx];
3174 const re_node_set *eclosure = dfa->eclosures + cur_node;
3175 outside_node = find_subexp_node (dfa, eclosure, ex_subexp, type);
3176 if (outside_node == REG_MISSING)
3178 /* There are no problematic nodes, just merge them. */
3179 err = re_node_set_merge (&new_nodes, eclosure);
3180 if (BE (err != REG_NOERROR, 0))
3182 re_node_set_free (&new_nodes);
3188 /* There are problematic nodes, re-calculate incrementally. */
3189 err = check_arrival_expand_ecl_sub (dfa, &new_nodes, cur_node,
3191 if (BE (err != REG_NOERROR, 0))
3193 re_node_set_free (&new_nodes);
3198 re_node_set_free (cur_nodes);
3199 *cur_nodes = new_nodes;
3203 /* Helper function for check_arrival_expand_ecl.
3204 Check incrementally the epsilon closure of TARGET, and if it isn't
3205 problematic append it to DST_NODES. */
3207 static reg_errcode_t
3209 check_arrival_expand_ecl_sub (const re_dfa_t *dfa, re_node_set *dst_nodes,
3210 Idx target, Idx ex_subexp, int type)
3213 for (cur_node = target; !re_node_set_contains (dst_nodes, cur_node);)
3217 if (dfa->nodes[cur_node].type == type
3218 && dfa->nodes[cur_node].opr.idx == ex_subexp)
3220 if (type == OP_CLOSE_SUBEXP)
3222 ok = re_node_set_insert (dst_nodes, cur_node);
3228 ok = re_node_set_insert (dst_nodes, cur_node);
3231 if (dfa->edests[cur_node].nelem == 0)
3233 if (dfa->edests[cur_node].nelem == 2)
3236 err = check_arrival_expand_ecl_sub (dfa, dst_nodes,
3237 dfa->edests[cur_node].elems[1],
3239 if (BE (err != REG_NOERROR, 0))
3242 cur_node = dfa->edests[cur_node].elems[0];
3248 /* For all the back references in the current state, calculate the
3249 destination of the back references by the appropriate entry
3250 in MCTX->BKREF_ENTS. */
3252 static reg_errcode_t
3254 expand_bkref_cache (re_match_context_t *mctx, re_node_set *cur_nodes,
3255 Idx cur_str, Idx subexp_num, int type)
3257 const re_dfa_t *const dfa = mctx->dfa;
3259 Idx cache_idx_start = search_cur_bkref_entry (mctx, cur_str);
3260 struct re_backref_cache_entry *ent;
3262 if (cache_idx_start == REG_MISSING)
3266 ent = mctx->bkref_ents + cache_idx_start;
3269 Idx to_idx, next_node;
3271 /* Is this entry ENT is appropriate? */
3272 if (!re_node_set_contains (cur_nodes, ent->node))
3275 to_idx = cur_str + ent->subexp_to - ent->subexp_from;
3276 /* Calculate the destination of the back reference, and append it
3277 to MCTX->STATE_LOG. */
3278 if (to_idx == cur_str)
3280 /* The backreference did epsilon transit, we must re-check all the
3281 node in the current state. */
3282 re_node_set new_dests;
3283 reg_errcode_t err2, err3;
3284 next_node = dfa->edests[ent->node].elems[0];
3285 if (re_node_set_contains (cur_nodes, next_node))
3287 err = re_node_set_init_1 (&new_dests, next_node);
3288 err2 = check_arrival_expand_ecl (dfa, &new_dests, subexp_num, type);
3289 err3 = re_node_set_merge (cur_nodes, &new_dests);
3290 re_node_set_free (&new_dests);
3291 if (BE (err != REG_NOERROR || err2 != REG_NOERROR
3292 || err3 != REG_NOERROR, 0))
3294 err = (err != REG_NOERROR ? err
3295 : (err2 != REG_NOERROR ? err2 : err3));
3298 /* TODO: It is still inefficient... */
3303 re_node_set union_set;
3304 next_node = dfa->nexts[ent->node];
3305 if (mctx->state_log[to_idx])
3308 if (re_node_set_contains (&mctx->state_log[to_idx]->nodes,
3311 err = re_node_set_init_copy (&union_set,
3312 &mctx->state_log[to_idx]->nodes);
3313 ok = re_node_set_insert (&union_set, next_node);
3314 if (BE (err != REG_NOERROR || ! ok, 0))
3316 re_node_set_free (&union_set);
3317 err = err != REG_NOERROR ? err : REG_ESPACE;
3323 err = re_node_set_init_1 (&union_set, next_node);
3324 if (BE (err != REG_NOERROR, 0))
3327 mctx->state_log[to_idx] = re_acquire_state (&err, dfa, &union_set);
3328 re_node_set_free (&union_set);
3329 if (BE (mctx->state_log[to_idx] == NULL
3330 && err != REG_NOERROR, 0))
3334 while (ent++->more);
3338 /* Build transition table for the state.
3339 Return true if successful. */
3343 build_trtable (const re_dfa_t *dfa, re_dfastate_t *state)
3348 bool need_word_trtable = false;
3349 bitset_word_t elem, mask;
3350 bool dests_node_malloced = false;
3351 bool dest_states_malloced = false;
3352 Idx ndests; /* Number of the destination states from `state'. */
3353 re_dfastate_t **trtable;
3354 re_dfastate_t **dest_states = NULL, **dest_states_word, **dest_states_nl;
3355 re_node_set follows, *dests_node;
3357 bitset_t acceptable;
3361 re_node_set dests_node[SBC_MAX];
3362 bitset_t dests_ch[SBC_MAX];
3365 /* We build DFA states which corresponds to the destination nodes
3366 from `state'. `dests_node[i]' represents the nodes which i-th
3367 destination state contains, and `dests_ch[i]' represents the
3368 characters which i-th destination state accepts. */
3369 if (__libc_use_alloca (sizeof (struct dests_alloc)))
3370 dests_alloc = (struct dests_alloc *) alloca (sizeof (struct dests_alloc));
3373 dests_alloc = re_malloc (struct dests_alloc, 1);
3374 if (BE (dests_alloc == NULL, 0))
3376 dests_node_malloced = true;
3378 dests_node = dests_alloc->dests_node;
3379 dests_ch = dests_alloc->dests_ch;
3381 /* Initialize transiton table. */
3382 state->word_trtable = state->trtable = NULL;
3384 /* At first, group all nodes belonging to `state' into several
3386 ndests = group_nodes_into_DFAstates (dfa, state, dests_node, dests_ch);
3387 if (BE (! REG_VALID_NONZERO_INDEX (ndests), 0))
3389 if (dests_node_malloced)
3393 state->trtable = (re_dfastate_t **)
3394 calloc (sizeof (re_dfastate_t *), SBC_MAX);
3400 err = re_node_set_alloc (&follows, ndests + 1);
3401 if (BE (err != REG_NOERROR, 0))
3404 /* Avoid arithmetic overflow in size calculation. */
3405 if (BE ((((SIZE_MAX - (sizeof (re_node_set) + sizeof (bitset_t)) * SBC_MAX)
3406 / (3 * sizeof (re_dfastate_t *)))
3411 if (__libc_use_alloca ((sizeof (re_node_set) + sizeof (bitset_t)) * SBC_MAX
3412 + ndests * 3 * sizeof (re_dfastate_t *)))
3413 dest_states = (re_dfastate_t **)
3414 alloca (ndests * 3 * sizeof (re_dfastate_t *));
3417 dest_states = (re_dfastate_t **)
3418 malloc (ndests * 3 * sizeof (re_dfastate_t *));
3419 if (BE (dest_states == NULL, 0))
3422 if (dest_states_malloced)
3424 re_node_set_free (&follows);
3425 for (i = 0; i < ndests; ++i)
3426 re_node_set_free (dests_node + i);
3427 if (dests_node_malloced)
3431 dest_states_malloced = true;
3433 dest_states_word = dest_states + ndests;
3434 dest_states_nl = dest_states_word + ndests;
3435 bitset_empty (acceptable);
3437 /* Then build the states for all destinations. */
3438 for (i = 0; i < ndests; ++i)
3441 re_node_set_empty (&follows);
3442 /* Merge the follows of this destination states. */
3443 for (j = 0; j < dests_node[i].nelem; ++j)
3445 next_node = dfa->nexts[dests_node[i].elems[j]];
3446 if (next_node != REG_MISSING)
3448 err = re_node_set_merge (&follows, dfa->eclosures + next_node);
3449 if (BE (err != REG_NOERROR, 0))
3453 dest_states[i] = re_acquire_state_context (&err, dfa, &follows, 0);
3454 if (BE (dest_states[i] == NULL && err != REG_NOERROR, 0))
3456 /* If the new state has context constraint,
3457 build appropriate states for these contexts. */
3458 if (dest_states[i]->has_constraint)
3460 dest_states_word[i] = re_acquire_state_context (&err, dfa, &follows,
3462 if (BE (dest_states_word[i] == NULL && err != REG_NOERROR, 0))
3465 if (dest_states[i] != dest_states_word[i] && dfa->mb_cur_max > 1)
3466 need_word_trtable = true;
3468 dest_states_nl[i] = re_acquire_state_context (&err, dfa, &follows,
3470 if (BE (dest_states_nl[i] == NULL && err != REG_NOERROR, 0))
3475 dest_states_word[i] = dest_states[i];
3476 dest_states_nl[i] = dest_states[i];
3478 bitset_merge (acceptable, dests_ch[i]);
3481 if (!BE (need_word_trtable, 0))
3483 /* We don't care about whether the following character is a word
3484 character, or we are in a single-byte character set so we can
3485 discern by looking at the character code: allocate a
3486 256-entry transition table. */
3487 trtable = state->trtable =
3488 (re_dfastate_t **) calloc (sizeof (re_dfastate_t *), SBC_MAX);
3489 if (BE (trtable == NULL, 0))
3492 /* For all characters ch...: */
3493 for (i = 0; i < BITSET_WORDS; ++i)
3494 for (ch = i * BITSET_WORD_BITS, elem = acceptable[i], mask = 1;
3496 mask <<= 1, elem >>= 1, ++ch)
3497 if (BE (elem & 1, 0))
3499 /* There must be exactly one destination which accepts
3500 character ch. See group_nodes_into_DFAstates. */
3501 for (j = 0; (dests_ch[j][i] & mask) == 0; ++j)
3504 /* j-th destination accepts the word character ch. */
3505 if (dfa->word_char[i] & mask)
3506 trtable[ch] = dest_states_word[j];
3508 trtable[ch] = dest_states[j];
3513 /* We care about whether the following character is a word
3514 character, and we are in a multi-byte character set: discern
3515 by looking at the character code: build two 256-entry
3516 transition tables, one starting at trtable[0] and one
3517 starting at trtable[SBC_MAX]. */
3518 trtable = state->word_trtable =
3519 (re_dfastate_t **) calloc (sizeof (re_dfastate_t *), 2 * SBC_MAX);
3520 if (BE (trtable == NULL, 0))
3523 /* For all characters ch...: */
3524 for (i = 0; i < BITSET_WORDS; ++i)
3525 for (ch = i * BITSET_WORD_BITS, elem = acceptable[i], mask = 1;
3527 mask <<= 1, elem >>= 1, ++ch)
3528 if (BE (elem & 1, 0))
3530 /* There must be exactly one destination which accepts
3531 character ch. See group_nodes_into_DFAstates. */
3532 for (j = 0; (dests_ch[j][i] & mask) == 0; ++j)
3535 /* j-th destination accepts the word character ch. */
3536 trtable[ch] = dest_states[j];
3537 trtable[ch + SBC_MAX] = dest_states_word[j];
3542 if (bitset_contain (acceptable, NEWLINE_CHAR))
3544 /* The current state accepts newline character. */
3545 for (j = 0; j < ndests; ++j)
3546 if (bitset_contain (dests_ch[j], NEWLINE_CHAR))
3548 /* k-th destination accepts newline character. */
3549 trtable[NEWLINE_CHAR] = dest_states_nl[j];
3550 if (need_word_trtable)
3551 trtable[NEWLINE_CHAR + SBC_MAX] = dest_states_nl[j];
3552 /* There must be only one destination which accepts
3553 newline. See group_nodes_into_DFAstates. */
3558 if (dest_states_malloced)
3561 re_node_set_free (&follows);
3562 for (i = 0; i < ndests; ++i)
3563 re_node_set_free (dests_node + i);
3565 if (dests_node_malloced)
3571 /* Group all nodes belonging to STATE into several destinations.
3572 Then for all destinations, set the nodes belonging to the destination
3573 to DESTS_NODE[i] and set the characters accepted by the destination
3574 to DEST_CH[i]. This function return the number of destinations. */
3578 group_nodes_into_DFAstates (const re_dfa_t *dfa, const re_dfastate_t *state,
3579 re_node_set *dests_node, bitset_t *dests_ch)
3584 Idx ndests; /* Number of the destinations from `state'. */
3585 bitset_t accepts; /* Characters a node can accept. */
3586 const re_node_set *cur_nodes = &state->nodes;
3587 bitset_empty (accepts);
3590 /* For all the nodes belonging to `state', */
3591 for (i = 0; i < cur_nodes->nelem; ++i)
3593 re_token_t *node = &dfa->nodes[cur_nodes->elems[i]];
3594 re_token_type_t type = node->type;
3595 unsigned int constraint = node->constraint;
3597 /* Enumerate all single byte character this node can accept. */
3598 if (type == CHARACTER)
3599 bitset_set (accepts, node->opr.c);
3600 else if (type == SIMPLE_BRACKET)
3602 bitset_merge (accepts, node->opr.sbcset);
3604 else if (type == OP_PERIOD)
3606 #ifdef RE_ENABLE_I18N
3607 if (dfa->mb_cur_max > 1)
3608 bitset_merge (accepts, dfa->sb_char);
3611 bitset_set_all (accepts);
3612 if (!(dfa->syntax & RE_DOT_NEWLINE))
3613 bitset_clear (accepts, '\n');
3614 if (dfa->syntax & RE_DOT_NOT_NULL)
3615 bitset_clear (accepts, '\0');
3617 #ifdef RE_ENABLE_I18N
3618 else if (type == OP_UTF8_PERIOD)
3620 if (ASCII_CHARS % BITSET_WORD_BITS == 0)
3621 memset (accepts, -1, ASCII_CHARS / CHAR_BIT);
3623 bitset_merge (accepts, utf8_sb_map);
3624 if (!(dfa->syntax & RE_DOT_NEWLINE))
3625 bitset_clear (accepts, '\n');
3626 if (dfa->syntax & RE_DOT_NOT_NULL)
3627 bitset_clear (accepts, '\0');
3633 /* Check the `accepts' and sift the characters which are not
3634 match it the context. */
3637 if (constraint & NEXT_NEWLINE_CONSTRAINT)
3639 bool accepts_newline = bitset_contain (accepts, NEWLINE_CHAR);
3640 bitset_empty (accepts);
3641 if (accepts_newline)
3642 bitset_set (accepts, NEWLINE_CHAR);
3646 if (constraint & NEXT_ENDBUF_CONSTRAINT)
3648 bitset_empty (accepts);
3652 if (constraint & NEXT_WORD_CONSTRAINT)
3654 bitset_word_t any_set = 0;
3655 if (type == CHARACTER && !node->word_char)
3657 bitset_empty (accepts);
3660 #ifdef RE_ENABLE_I18N
3661 if (dfa->mb_cur_max > 1)
3662 for (j = 0; j < BITSET_WORDS; ++j)
3663 any_set |= (accepts[j] &= (dfa->word_char[j] | ~dfa->sb_char[j]));
3666 for (j = 0; j < BITSET_WORDS; ++j)
3667 any_set |= (accepts[j] &= dfa->word_char[j]);
3671 if (constraint & NEXT_NOTWORD_CONSTRAINT)
3673 bitset_word_t any_set = 0;
3674 if (type == CHARACTER && node->word_char)
3676 bitset_empty (accepts);
3679 #ifdef RE_ENABLE_I18N
3680 if (dfa->mb_cur_max > 1)
3681 for (j = 0; j < BITSET_WORDS; ++j)
3682 any_set |= (accepts[j] &= ~(dfa->word_char[j] & dfa->sb_char[j]));
3685 for (j = 0; j < BITSET_WORDS; ++j)
3686 any_set |= (accepts[j] &= ~dfa->word_char[j]);
3692 /* Then divide `accepts' into DFA states, or create a new
3693 state. Above, we make sure that accepts is not empty. */
3694 for (j = 0; j < ndests; ++j)
3696 bitset_t intersec; /* Intersection sets, see below. */
3698 /* Flags, see below. */
3699 bitset_word_t has_intersec, not_subset, not_consumed;
3701 /* Optimization, skip if this state doesn't accept the character. */
3702 if (type == CHARACTER && !bitset_contain (dests_ch[j], node->opr.c))
3705 /* Enumerate the intersection set of this state and `accepts'. */
3707 for (k = 0; k < BITSET_WORDS; ++k)
3708 has_intersec |= intersec[k] = accepts[k] & dests_ch[j][k];
3709 /* And skip if the intersection set is empty. */
3713 /* Then check if this state is a subset of `accepts'. */
3714 not_subset = not_consumed = 0;
3715 for (k = 0; k < BITSET_WORDS; ++k)
3717 not_subset |= remains[k] = ~accepts[k] & dests_ch[j][k];
3718 not_consumed |= accepts[k] = accepts[k] & ~dests_ch[j][k];
3721 /* If this state isn't a subset of `accepts', create a
3722 new group state, which has the `remains'. */
3725 bitset_copy (dests_ch[ndests], remains);
3726 bitset_copy (dests_ch[j], intersec);
3727 err = re_node_set_init_copy (dests_node + ndests, &dests_node[j]);
3728 if (BE (err != REG_NOERROR, 0))
3733 /* Put the position in the current group. */
3734 ok = re_node_set_insert (&dests_node[j], cur_nodes->elems[i]);
3738 /* If all characters are consumed, go to next node. */
3742 /* Some characters remain, create a new group. */
3745 bitset_copy (dests_ch[ndests], accepts);
3746 err = re_node_set_init_1 (dests_node + ndests, cur_nodes->elems[i]);
3747 if (BE (err != REG_NOERROR, 0))
3750 bitset_empty (accepts);
3755 for (j = 0; j < ndests; ++j)
3756 re_node_set_free (dests_node + j);
3760 #ifdef RE_ENABLE_I18N
3761 /* Check how many bytes the node `dfa->nodes[node_idx]' accepts.
3762 Return the number of the bytes the node accepts.
3763 STR_IDX is the current index of the input string.
3765 This function handles the nodes which can accept one character, or
3766 one collating element like '.', '[a-z]', opposite to the other nodes
3767 can only accept one byte. */
3771 check_node_accept_bytes (const re_dfa_t *dfa, Idx node_idx,
3772 const re_string_t *input, Idx str_idx)
3774 const re_token_t *node = dfa->nodes + node_idx;
3775 int char_len, elem_len;
3778 if (BE (node->type == OP_UTF8_PERIOD, 0))
3780 unsigned char c = re_string_byte_at (input, str_idx), d;
3781 if (BE (c < 0xc2, 1))
3784 if (str_idx + 2 > input->len)
3787 d = re_string_byte_at (input, str_idx + 1);
3789 return (d < 0x80 || d > 0xbf) ? 0 : 2;
3793 if (c == 0xe0 && d < 0xa0)
3799 if (c == 0xf0 && d < 0x90)
3805 if (c == 0xf8 && d < 0x88)
3811 if (c == 0xfc && d < 0x84)
3817 if (str_idx + char_len > input->len)
3820 for (i = 1; i < char_len; ++i)
3822 d = re_string_byte_at (input, str_idx + i);
3823 if (d < 0x80 || d > 0xbf)
3829 char_len = re_string_char_size_at (input, str_idx);
3830 if (node->type == OP_PERIOD)
3834 /* FIXME: I don't think this if is needed, as both '\n'
3835 and '\0' are char_len == 1. */
3836 /* '.' accepts any one character except the following two cases. */
3837 if ((!(dfa->syntax & RE_DOT_NEWLINE) &&
3838 re_string_byte_at (input, str_idx) == '\n') ||
3839 ((dfa->syntax & RE_DOT_NOT_NULL) &&
3840 re_string_byte_at (input, str_idx) == '\0'))
3845 elem_len = re_string_elem_size_at (input, str_idx);
3846 if ((elem_len <= 1 && char_len <= 1) || char_len == 0)
3849 if (node->type == COMPLEX_BRACKET)
3851 const re_charset_t *cset = node->opr.mbcset;
3853 const unsigned char *pin
3854 = ((const unsigned char *) re_string_get_buffer (input) + str_idx);
3859 wchar_t wc = ((cset->nranges || cset->nchar_classes || cset->nmbchars)
3860 ? re_string_wchar_at (input, str_idx) : 0);
3862 /* match with multibyte character? */
3863 for (i = 0; i < cset->nmbchars; ++i)
3864 if (wc == cset->mbchars[i])
3866 match_len = char_len;
3867 goto check_node_accept_bytes_match;
3869 /* match with character_class? */
3870 for (i = 0; i < cset->nchar_classes; ++i)
3872 wctype_t wt = cset->char_classes[i];
3873 if (__iswctype (wc, wt))
3875 match_len = char_len;
3876 goto check_node_accept_bytes_match;
3881 nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
3884 unsigned int in_collseq = 0;
3885 const int32_t *table, *indirect;
3886 const unsigned char *weights, *extra;
3887 const char *collseqwc;
3889 /* This #include defines a local function! */
3890 # include <locale/weight.h>
3892 /* match with collating_symbol? */
3893 if (cset->ncoll_syms)
3894 extra = (const unsigned char *)
3895 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB);
3896 for (i = 0; i < cset->ncoll_syms; ++i)
3898 const unsigned char *coll_sym = extra + cset->coll_syms[i];
3899 /* Compare the length of input collating element and
3900 the length of current collating element. */
3901 if (*coll_sym != elem_len)
3903 /* Compare each bytes. */
3904 for (j = 0; j < *coll_sym; j++)
3905 if (pin[j] != coll_sym[1 + j])
3909 /* Match if every bytes is equal. */
3911 goto check_node_accept_bytes_match;
3917 if (elem_len <= char_len)
3919 collseqwc = _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQWC);
3920 in_collseq = __collseq_table_lookup (collseqwc, wc);
3923 in_collseq = find_collation_sequence_value (pin, elem_len);
3925 /* match with range expression? */
3926 for (i = 0; i < cset->nranges; ++i)
3927 if (cset->range_starts[i] <= in_collseq
3928 && in_collseq <= cset->range_ends[i])
3930 match_len = elem_len;
3931 goto check_node_accept_bytes_match;
3934 /* match with equivalence_class? */
3935 if (cset->nequiv_classes)
3937 const unsigned char *cp = pin;
3938 table = (const int32_t *)
3939 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
3940 weights = (const unsigned char *)
3941 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_WEIGHTMB);
3942 extra = (const unsigned char *)
3943 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAMB);
3944 indirect = (const int32_t *)
3945 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_INDIRECTMB);
3946 idx = findidx (&cp);
3948 for (i = 0; i < cset->nequiv_classes; ++i)
3950 int32_t equiv_class_idx = cset->equiv_classes[i];
3951 size_t weight_len = weights[idx];
3952 if (weight_len == weights[equiv_class_idx])
3955 while (cnt <= weight_len
3956 && (weights[equiv_class_idx + 1 + cnt]
3957 == weights[idx + 1 + cnt]))
3959 if (cnt > weight_len)
3961 match_len = elem_len;
3962 goto check_node_accept_bytes_match;
3971 /* match with range expression? */
3972 #if __GNUC__ >= 2 && ! (__STDC_VERSION__ < 199901L && __STRICT_ANSI__)
3973 wchar_t cmp_buf[] = {L'\0', L'\0', wc, L'\0', L'\0', L'\0'};
3975 wchar_t cmp_buf[] = {L'\0', L'\0', L'\0', L'\0', L'\0', L'\0'};
3978 for (i = 0; i < cset->nranges; ++i)
3980 cmp_buf[0] = cset->range_starts[i];
3981 cmp_buf[4] = cset->range_ends[i];
3982 if (wcscoll (cmp_buf, cmp_buf + 2) <= 0
3983 && wcscoll (cmp_buf + 2, cmp_buf + 4) <= 0)
3985 match_len = char_len;
3986 goto check_node_accept_bytes_match;
3990 check_node_accept_bytes_match:
3991 if (!cset->non_match)
3998 return (elem_len > char_len) ? elem_len : char_len;
4007 find_collation_sequence_value (const unsigned char *mbs, size_t mbs_len)
4009 uint32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
4014 /* No valid character. Match it as a single byte character. */
4015 const unsigned char *collseq = (const unsigned char *)
4016 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQMB);
4017 return collseq[mbs[0]];
4024 const unsigned char *extra = (const unsigned char *)
4025 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB);
4026 int32_t extrasize = (const unsigned char *)
4027 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB + 1) - extra;
4029 for (idx = 0; idx < extrasize;)
4033 int32_t elem_mbs_len;
4034 /* Skip the name of collating element name. */
4035 idx = idx + extra[idx] + 1;
4036 elem_mbs_len = extra[idx++];
4037 if (mbs_len == elem_mbs_len)
4039 for (mbs_cnt = 0; mbs_cnt < elem_mbs_len; ++mbs_cnt)
4040 if (extra[idx + mbs_cnt] != mbs[mbs_cnt])
4042 if (mbs_cnt == elem_mbs_len)
4043 /* Found the entry. */
4046 /* Skip the byte sequence of the collating element. */
4047 idx += elem_mbs_len;
4048 /* Adjust for the alignment. */
4049 idx = (idx + 3) & ~3;
4050 /* Skip the collation sequence value. */
4051 idx += sizeof (uint32_t);
4052 /* Skip the wide char sequence of the collating element. */
4053 idx = idx + sizeof (uint32_t) * (extra[idx] + 1);
4054 /* If we found the entry, return the sequence value. */
4056 return *(uint32_t *) (extra + idx);
4057 /* Skip the collation sequence value. */
4058 idx += sizeof (uint32_t);
4064 #endif /* RE_ENABLE_I18N */
4066 /* Check whether the node accepts the byte which is IDX-th
4067 byte of the INPUT. */
4071 check_node_accept (const re_match_context_t *mctx, const re_token_t *node,
4075 ch = re_string_byte_at (&mctx->input, idx);
4079 if (node->opr.c != ch)
4083 case SIMPLE_BRACKET:
4084 if (!bitset_contain (node->opr.sbcset, ch))
4088 #ifdef RE_ENABLE_I18N
4089 case OP_UTF8_PERIOD:
4090 if (ch >= ASCII_CHARS)
4095 if ((ch == '\n' && !(mctx->dfa->syntax & RE_DOT_NEWLINE))
4096 || (ch == '\0' && (mctx->dfa->syntax & RE_DOT_NOT_NULL)))
4104 if (node->constraint)
4106 /* The node has constraints. Check whether the current context
4107 satisfies the constraints. */
4108 unsigned int context = re_string_context_at (&mctx->input, idx,
4110 if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
4117 /* Extend the buffers, if the buffers have run out. */
4119 static reg_errcode_t
4121 extend_buffers (re_match_context_t *mctx)
4124 re_string_t *pstr = &mctx->input;
4126 /* Avoid overflow. */
4127 if (BE (SIZE_MAX / 2 / sizeof (re_dfastate_t *) <= pstr->bufs_len, 0))
4130 /* Double the lengthes of the buffers. */
4131 ret = re_string_realloc_buffers (pstr, pstr->bufs_len * 2);
4132 if (BE (ret != REG_NOERROR, 0))
4135 if (mctx->state_log != NULL)
4137 /* And double the length of state_log. */
4138 /* XXX We have no indication of the size of this buffer. If this
4139 allocation fail we have no indication that the state_log array
4140 does not have the right size. */
4141 re_dfastate_t **new_array = re_realloc (mctx->state_log, re_dfastate_t *,
4142 pstr->bufs_len + 1);
4143 if (BE (new_array == NULL, 0))
4145 mctx->state_log = new_array;
4148 /* Then reconstruct the buffers. */
4151 #ifdef RE_ENABLE_I18N
4152 if (pstr->mb_cur_max > 1)
4154 ret = build_wcs_upper_buffer (pstr);
4155 if (BE (ret != REG_NOERROR, 0))
4159 #endif /* RE_ENABLE_I18N */
4160 build_upper_buffer (pstr);
4164 #ifdef RE_ENABLE_I18N
4165 if (pstr->mb_cur_max > 1)
4166 build_wcs_buffer (pstr);
4168 #endif /* RE_ENABLE_I18N */
4170 if (pstr->trans != NULL)
4171 re_string_translate_buffer (pstr);
4178 /* Functions for matching context. */
4180 /* Initialize MCTX. */
4182 static reg_errcode_t
4184 match_ctx_init (re_match_context_t *mctx, int eflags, Idx n)
4186 mctx->eflags = eflags;
4187 mctx->match_last = REG_MISSING;
4190 /* Avoid overflow. */
4191 size_t max_object_size =
4192 MAX (sizeof (struct re_backref_cache_entry),
4193 sizeof (re_sub_match_top_t *));
4194 if (BE (SIZE_MAX / max_object_size < n, 0))
4197 mctx->bkref_ents = re_malloc (struct re_backref_cache_entry, n);
4198 mctx->sub_tops = re_malloc (re_sub_match_top_t *, n);
4199 if (BE (mctx->bkref_ents == NULL || mctx->sub_tops == NULL, 0))
4202 /* Already zero-ed by the caller.
4204 mctx->bkref_ents = NULL;
4205 mctx->nbkref_ents = 0;
4206 mctx->nsub_tops = 0; */
4207 mctx->abkref_ents = n;
4208 mctx->max_mb_elem_len = 1;
4209 mctx->asub_tops = n;
4213 /* Clean the entries which depend on the current input in MCTX.
4214 This function must be invoked when the matcher changes the start index
4215 of the input, or changes the input string. */
4219 match_ctx_clean (re_match_context_t *mctx)
4222 for (st_idx = 0; st_idx < mctx->nsub_tops; ++st_idx)
4225 re_sub_match_top_t *top = mctx->sub_tops[st_idx];
4226 for (sl_idx = 0; sl_idx < top->nlasts; ++sl_idx)
4228 re_sub_match_last_t *last = top->lasts[sl_idx];
4229 re_free (last->path.array);
4232 re_free (top->lasts);
4235 re_free (top->path->array);
4236 re_free (top->path);
4241 mctx->nsub_tops = 0;
4242 mctx->nbkref_ents = 0;
4245 /* Free all the memory associated with MCTX. */
4249 match_ctx_free (re_match_context_t *mctx)
4251 /* First, free all the memory associated with MCTX->SUB_TOPS. */
4252 match_ctx_clean (mctx);
4253 re_free (mctx->sub_tops);
4254 re_free (mctx->bkref_ents);
4257 /* Add a new backreference entry to MCTX.
4258 Note that we assume that caller never call this function with duplicate
4259 entry, and call with STR_IDX which isn't smaller than any existing entry.
4262 static reg_errcode_t
4264 match_ctx_add_entry (re_match_context_t *mctx, Idx node, Idx str_idx, Idx from,
4267 if (mctx->nbkref_ents >= mctx->abkref_ents)
4269 struct re_backref_cache_entry* new_entry;
4270 new_entry = re_realloc (mctx->bkref_ents, struct re_backref_cache_entry,
4271 mctx->abkref_ents * 2);
4272 if (BE (new_entry == NULL, 0))
4274 re_free (mctx->bkref_ents);
4277 mctx->bkref_ents = new_entry;
4278 memset (mctx->bkref_ents + mctx->nbkref_ents, '\0',
4279 sizeof (struct re_backref_cache_entry) * mctx->abkref_ents);
4280 mctx->abkref_ents *= 2;
4282 if (mctx->nbkref_ents > 0
4283 && mctx->bkref_ents[mctx->nbkref_ents - 1].str_idx == str_idx)
4284 mctx->bkref_ents[mctx->nbkref_ents - 1].more = 1;
4286 mctx->bkref_ents[mctx->nbkref_ents].node = node;
4287 mctx->bkref_ents[mctx->nbkref_ents].str_idx = str_idx;
4288 mctx->bkref_ents[mctx->nbkref_ents].subexp_from = from;
4289 mctx->bkref_ents[mctx->nbkref_ents].subexp_to = to;
4291 /* This is a cache that saves negative results of check_dst_limits_calc_pos.
4292 If bit N is clear, means that this entry won't epsilon-transition to
4293 an OP_OPEN_SUBEXP or OP_CLOSE_SUBEXP for the N+1-th subexpression. If
4294 it is set, check_dst_limits_calc_pos_1 will recurse and try to find one
4297 A backreference does not epsilon-transition unless it is empty, so set
4298 to all zeros if FROM != TO. */
4299 mctx->bkref_ents[mctx->nbkref_ents].eps_reachable_subexps_map
4300 = (from == to ? -1 : 0);
4302 mctx->bkref_ents[mctx->nbkref_ents++].more = 0;
4303 if (mctx->max_mb_elem_len < to - from)
4304 mctx->max_mb_elem_len = to - from;
4308 /* Return the first entry with the same str_idx, or REG_MISSING if none is
4309 found. Note that MCTX->BKREF_ENTS is already sorted by MCTX->STR_IDX. */
4313 search_cur_bkref_entry (const re_match_context_t *mctx, Idx str_idx)
4315 Idx left, right, mid, last;
4316 last = right = mctx->nbkref_ents;
4317 for (left = 0; left < right;)
4319 mid = (left + right) / 2;
4320 if (mctx->bkref_ents[mid].str_idx < str_idx)
4325 if (left < last && mctx->bkref_ents[left].str_idx == str_idx)
4331 /* Register the node NODE, whose type is OP_OPEN_SUBEXP, and which matches
4334 static reg_errcode_t
4336 match_ctx_add_subtop (re_match_context_t *mctx, Idx node, Idx str_idx)
4339 assert (mctx->sub_tops != NULL);
4340 assert (mctx->asub_tops > 0);
4342 if (BE (mctx->nsub_tops == mctx->asub_tops, 0))
4344 Idx new_asub_tops = mctx->asub_tops * 2;
4345 re_sub_match_top_t **new_array = re_realloc (mctx->sub_tops,
4346 re_sub_match_top_t *,
4348 if (BE (new_array == NULL, 0))
4350 mctx->sub_tops = new_array;
4351 mctx->asub_tops = new_asub_tops;
4353 mctx->sub_tops[mctx->nsub_tops] = calloc (1, sizeof (re_sub_match_top_t));
4354 if (BE (mctx->sub_tops[mctx->nsub_tops] == NULL, 0))
4356 mctx->sub_tops[mctx->nsub_tops]->node = node;
4357 mctx->sub_tops[mctx->nsub_tops++]->str_idx = str_idx;
4361 /* Register the node NODE, whose type is OP_CLOSE_SUBEXP, and which matches
4362 at STR_IDX, whose corresponding OP_OPEN_SUBEXP is SUB_TOP. */
4364 static re_sub_match_last_t *
4366 match_ctx_add_sublast (re_sub_match_top_t *subtop, Idx node, Idx str_idx)
4368 re_sub_match_last_t *new_entry;
4369 if (BE (subtop->nlasts == subtop->alasts, 0))
4371 Idx new_alasts = 2 * subtop->alasts + 1;
4372 re_sub_match_last_t **new_array = re_realloc (subtop->lasts,
4373 re_sub_match_last_t *,
4375 if (BE (new_array == NULL, 0))
4377 subtop->lasts = new_array;
4378 subtop->alasts = new_alasts;
4380 new_entry = calloc (1, sizeof (re_sub_match_last_t));
4381 if (BE (new_entry != NULL, 1))
4383 subtop->lasts[subtop->nlasts] = new_entry;
4384 new_entry->node = node;
4385 new_entry->str_idx = str_idx;
4393 sift_ctx_init (re_sift_context_t *sctx, re_dfastate_t **sifted_sts,
4394 re_dfastate_t **limited_sts, Idx last_node, Idx last_str_idx)
4396 sctx->sifted_states = sifted_sts;
4397 sctx->limited_states = limited_sts;
4398 sctx->last_node = last_node;
4399 sctx->last_str_idx = last_str_idx;
4400 re_node_set_init_empty (&sctx->limits);