1 /* -*- buffer-read-only: t -*- vi: set ro: */
2 /* DO NOT EDIT! GENERATED AUTOMATICALLY! */
3 /* Extended regular expression matching and search library.
4 Copyright (C) 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 Free
5 Software Foundation, Inc.
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) */
642 internal_function __attribute_warn_unused_result__
643 re_search_internal (const regex_t *preg,
644 const char *string, Idx length,
645 Idx start, Idx last_start, Idx stop,
646 size_t nmatch, regmatch_t pmatch[],
650 const re_dfa_t *dfa = (const re_dfa_t *) preg->buffer;
651 Idx left_lim, right_lim;
653 bool fl_longest_match;
656 Idx match_last = REG_MISSING;
660 #if defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L)
661 re_match_context_t mctx = { .dfa = dfa };
663 re_match_context_t mctx;
665 char *fastmap = ((preg->fastmap != NULL && preg->fastmap_accurate
666 && start != last_start && !preg->can_be_null)
667 ? preg->fastmap : NULL);
668 RE_TRANSLATE_TYPE t = preg->translate;
670 #if !(defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L))
671 memset (&mctx, '\0', sizeof (re_match_context_t));
675 extra_nmatch = (nmatch > preg->re_nsub) ? nmatch - (preg->re_nsub + 1) : 0;
676 nmatch -= extra_nmatch;
678 /* Check if the DFA haven't been compiled. */
679 if (BE (preg->used == 0 || dfa->init_state == NULL
680 || dfa->init_state_word == NULL || dfa->init_state_nl == NULL
681 || dfa->init_state_begbuf == NULL, 0))
685 /* We assume front-end functions already check them. */
686 assert (0 <= last_start && last_start <= length);
689 /* If initial states with non-begbuf contexts have no elements,
690 the regex must be anchored. If preg->newline_anchor is set,
691 we'll never use init_state_nl, so do not check it. */
692 if (dfa->init_state->nodes.nelem == 0
693 && dfa->init_state_word->nodes.nelem == 0
694 && (dfa->init_state_nl->nodes.nelem == 0
695 || !preg->newline_anchor))
697 if (start != 0 && last_start != 0)
699 start = last_start = 0;
702 /* We must check the longest matching, if nmatch > 0. */
703 fl_longest_match = (nmatch != 0 || dfa->nbackref);
705 err = re_string_allocate (&mctx.input, string, length, dfa->nodes_len + 1,
706 preg->translate, (preg->syntax & RE_ICASE) != 0,
708 if (BE (err != REG_NOERROR, 0))
710 mctx.input.stop = stop;
711 mctx.input.raw_stop = stop;
712 mctx.input.newline_anchor = preg->newline_anchor;
714 err = match_ctx_init (&mctx, eflags, dfa->nbackref * 2);
715 if (BE (err != REG_NOERROR, 0))
718 /* We will log all the DFA states through which the dfa pass,
719 if nmatch > 1, or this dfa has "multibyte node", which is a
720 back-reference or a node which can accept multibyte character or
721 multi character collating element. */
722 if (nmatch > 1 || dfa->has_mb_node)
724 /* Avoid overflow. */
725 if (BE (SIZE_MAX / sizeof (re_dfastate_t *) <= mctx.input.bufs_len, 0))
731 mctx.state_log = re_malloc (re_dfastate_t *, mctx.input.bufs_len + 1);
732 if (BE (mctx.state_log == NULL, 0))
739 mctx.state_log = NULL;
742 mctx.input.tip_context = (eflags & REG_NOTBOL) ? CONTEXT_BEGBUF
743 : CONTEXT_NEWLINE | CONTEXT_BEGBUF;
745 /* Check incrementally whether of not the input string match. */
746 incr = (last_start < start) ? -1 : 1;
747 left_lim = (last_start < start) ? last_start : start;
748 right_lim = (last_start < start) ? start : last_start;
749 sb = dfa->mb_cur_max == 1;
752 ? ((sb || !(preg->syntax & RE_ICASE || t) ? 4 : 0)
753 | (start <= last_start ? 2 : 0)
754 | (t != NULL ? 1 : 0))
757 for (;; match_first += incr)
760 if (match_first < left_lim || right_lim < match_first)
763 /* Advance as rapidly as possible through the string, until we
764 find a plausible place to start matching. This may be done
765 with varying efficiency, so there are various possibilities:
766 only the most common of them are specialized, in order to
767 save on code size. We use a switch statement for speed. */
775 /* Fastmap with single-byte translation, match forward. */
776 while (BE (match_first < right_lim, 1)
777 && !fastmap[t[(unsigned char) string[match_first]]])
779 goto forward_match_found_start_or_reached_end;
782 /* Fastmap without translation, match forward. */
783 while (BE (match_first < right_lim, 1)
784 && !fastmap[(unsigned char) string[match_first]])
787 forward_match_found_start_or_reached_end:
788 if (BE (match_first == right_lim, 0))
790 ch = match_first >= length
791 ? 0 : (unsigned char) string[match_first];
792 if (!fastmap[t ? t[ch] : ch])
799 /* Fastmap without multi-byte translation, match backwards. */
800 while (match_first >= left_lim)
802 ch = match_first >= length
803 ? 0 : (unsigned char) string[match_first];
804 if (fastmap[t ? t[ch] : ch])
808 if (match_first < left_lim)
813 /* In this case, we can't determine easily the current byte,
814 since it might be a component byte of a multibyte
815 character. Then we use the constructed buffer instead. */
818 /* If MATCH_FIRST is out of the valid range, reconstruct the
820 __re_size_t offset = match_first - mctx.input.raw_mbs_idx;
821 if (BE (offset >= (__re_size_t) mctx.input.valid_raw_len, 0))
823 err = re_string_reconstruct (&mctx.input, match_first,
825 if (BE (err != REG_NOERROR, 0))
828 offset = match_first - mctx.input.raw_mbs_idx;
830 /* If MATCH_FIRST is out of the buffer, leave it as '\0'.
831 Note that MATCH_FIRST must not be smaller than 0. */
832 ch = (match_first >= length
833 ? 0 : re_string_byte_at (&mctx.input, offset));
837 if (match_first < left_lim || match_first > right_lim)
846 /* Reconstruct the buffers so that the matcher can assume that
847 the matching starts from the beginning of the buffer. */
848 err = re_string_reconstruct (&mctx.input, match_first, eflags);
849 if (BE (err != REG_NOERROR, 0))
852 #ifdef RE_ENABLE_I18N
853 /* Don't consider this char as a possible match start if it part,
854 yet isn't the head, of a multibyte character. */
855 if (!sb && !re_string_first_byte (&mctx.input, 0))
859 /* It seems to be appropriate one, then use the matcher. */
860 /* We assume that the matching starts from 0. */
861 mctx.state_log_top = mctx.nbkref_ents = mctx.max_mb_elem_len = 0;
862 match_last = check_matching (&mctx, fl_longest_match,
863 start <= last_start ? &match_first : NULL);
864 if (match_last != REG_MISSING)
866 if (BE (match_last == REG_ERROR, 0))
873 mctx.match_last = match_last;
874 if ((!preg->no_sub && nmatch > 1) || dfa->nbackref)
876 re_dfastate_t *pstate = mctx.state_log[match_last];
877 mctx.last_node = check_halt_state_context (&mctx, pstate,
880 if ((!preg->no_sub && nmatch > 1 && dfa->has_plural_match)
883 err = prune_impossible_nodes (&mctx);
884 if (err == REG_NOERROR)
886 if (BE (err != REG_NOMATCH, 0))
888 match_last = REG_MISSING;
891 break; /* We found a match. */
895 match_ctx_clean (&mctx);
899 assert (match_last != REG_MISSING);
900 assert (err == REG_NOERROR);
903 /* Set pmatch[] if we need. */
908 /* Initialize registers. */
909 for (reg_idx = 1; reg_idx < nmatch; ++reg_idx)
910 pmatch[reg_idx].rm_so = pmatch[reg_idx].rm_eo = -1;
912 /* Set the points where matching start/end. */
914 pmatch[0].rm_eo = mctx.match_last;
915 /* FIXME: This function should fail if mctx.match_last exceeds
916 the maximum possible regoff_t value. We need a new error
917 code REG_OVERFLOW. */
919 if (!preg->no_sub && nmatch > 1)
921 err = set_regs (preg, &mctx, nmatch, pmatch,
922 dfa->has_plural_match && dfa->nbackref > 0);
923 if (BE (err != REG_NOERROR, 0))
927 /* At last, add the offset to the each registers, since we slided
928 the buffers so that we could assume that the matching starts
930 for (reg_idx = 0; reg_idx < nmatch; ++reg_idx)
931 if (pmatch[reg_idx].rm_so != -1)
933 #ifdef RE_ENABLE_I18N
934 if (BE (mctx.input.offsets_needed != 0, 0))
936 pmatch[reg_idx].rm_so =
937 (pmatch[reg_idx].rm_so == mctx.input.valid_len
938 ? mctx.input.valid_raw_len
939 : mctx.input.offsets[pmatch[reg_idx].rm_so]);
940 pmatch[reg_idx].rm_eo =
941 (pmatch[reg_idx].rm_eo == mctx.input.valid_len
942 ? mctx.input.valid_raw_len
943 : mctx.input.offsets[pmatch[reg_idx].rm_eo]);
946 assert (mctx.input.offsets_needed == 0);
948 pmatch[reg_idx].rm_so += match_first;
949 pmatch[reg_idx].rm_eo += match_first;
951 for (reg_idx = 0; reg_idx < extra_nmatch; ++reg_idx)
953 pmatch[nmatch + reg_idx].rm_so = -1;
954 pmatch[nmatch + reg_idx].rm_eo = -1;
958 for (reg_idx = 0; reg_idx + 1 < nmatch; reg_idx++)
959 if (dfa->subexp_map[reg_idx] != reg_idx)
961 pmatch[reg_idx + 1].rm_so
962 = pmatch[dfa->subexp_map[reg_idx] + 1].rm_so;
963 pmatch[reg_idx + 1].rm_eo
964 = pmatch[dfa->subexp_map[reg_idx] + 1].rm_eo;
969 re_free (mctx.state_log);
971 match_ctx_free (&mctx);
972 re_string_destruct (&mctx.input);
977 internal_function __attribute_warn_unused_result__
978 prune_impossible_nodes (re_match_context_t *mctx)
980 const re_dfa_t *const dfa = mctx->dfa;
981 Idx halt_node, match_last;
983 re_dfastate_t **sifted_states;
984 re_dfastate_t **lim_states = NULL;
985 re_sift_context_t sctx;
987 assert (mctx->state_log != NULL);
989 match_last = mctx->match_last;
990 halt_node = mctx->last_node;
992 /* Avoid overflow. */
993 if (BE (SIZE_MAX / sizeof (re_dfastate_t *) <= match_last, 0))
996 sifted_states = re_malloc (re_dfastate_t *, match_last + 1);
997 if (BE (sifted_states == NULL, 0))
1004 lim_states = re_malloc (re_dfastate_t *, match_last + 1);
1005 if (BE (lim_states == NULL, 0))
1012 memset (lim_states, '\0',
1013 sizeof (re_dfastate_t *) * (match_last + 1));
1014 sift_ctx_init (&sctx, sifted_states, lim_states, halt_node,
1016 ret = sift_states_backward (mctx, &sctx);
1017 re_node_set_free (&sctx.limits);
1018 if (BE (ret != REG_NOERROR, 0))
1020 if (sifted_states[0] != NULL || lim_states[0] != NULL)
1025 if (! REG_VALID_INDEX (match_last))
1030 } while (mctx->state_log[match_last] == NULL
1031 || !mctx->state_log[match_last]->halt);
1032 halt_node = check_halt_state_context (mctx,
1033 mctx->state_log[match_last],
1036 ret = merge_state_array (dfa, sifted_states, lim_states,
1038 re_free (lim_states);
1040 if (BE (ret != REG_NOERROR, 0))
1045 sift_ctx_init (&sctx, sifted_states, lim_states, halt_node, match_last);
1046 ret = sift_states_backward (mctx, &sctx);
1047 re_node_set_free (&sctx.limits);
1048 if (BE (ret != REG_NOERROR, 0))
1050 if (sifted_states[0] == NULL)
1056 re_free (mctx->state_log);
1057 mctx->state_log = sifted_states;
1058 sifted_states = NULL;
1059 mctx->last_node = halt_node;
1060 mctx->match_last = match_last;
1063 re_free (sifted_states);
1064 re_free (lim_states);
1068 /* Acquire an initial state and return it.
1069 We must select appropriate initial state depending on the context,
1070 since initial states may have constraints like "\<", "^", etc.. */
1072 static inline re_dfastate_t *
1073 __attribute ((always_inline)) internal_function
1074 acquire_init_state_context (reg_errcode_t *err, const re_match_context_t *mctx,
1077 const re_dfa_t *const dfa = mctx->dfa;
1078 if (dfa->init_state->has_constraint)
1080 unsigned int context;
1081 context = re_string_context_at (&mctx->input, idx - 1, mctx->eflags);
1082 if (IS_WORD_CONTEXT (context))
1083 return dfa->init_state_word;
1084 else if (IS_ORDINARY_CONTEXT (context))
1085 return dfa->init_state;
1086 else if (IS_BEGBUF_CONTEXT (context) && IS_NEWLINE_CONTEXT (context))
1087 return dfa->init_state_begbuf;
1088 else if (IS_NEWLINE_CONTEXT (context))
1089 return dfa->init_state_nl;
1090 else if (IS_BEGBUF_CONTEXT (context))
1092 /* It is relatively rare case, then calculate on demand. */
1093 return re_acquire_state_context (err, dfa,
1094 dfa->init_state->entrance_nodes,
1098 /* Must not happen? */
1099 return dfa->init_state;
1102 return dfa->init_state;
1105 /* Check whether the regular expression match input string INPUT or not,
1106 and return the index where the matching end. Return REG_MISSING if
1107 there is no match, and return REG_ERROR in case of an error.
1108 FL_LONGEST_MATCH means we want the POSIX longest matching.
1109 If P_MATCH_FIRST is not NULL, and the match fails, it is set to the
1110 next place where we may want to try matching.
1111 Note that the matcher assume that the maching starts from the current
1112 index of the buffer. */
1115 internal_function __attribute_warn_unused_result__
1116 check_matching (re_match_context_t *mctx, bool fl_longest_match,
1119 const re_dfa_t *const dfa = mctx->dfa;
1122 Idx match_last = REG_MISSING;
1123 Idx cur_str_idx = re_string_cur_idx (&mctx->input);
1124 re_dfastate_t *cur_state;
1125 bool at_init_state = p_match_first != NULL;
1126 Idx next_start_idx = cur_str_idx;
1129 cur_state = acquire_init_state_context (&err, mctx, cur_str_idx);
1130 /* An initial state must not be NULL (invalid). */
1131 if (BE (cur_state == NULL, 0))
1133 assert (err == REG_ESPACE);
1137 if (mctx->state_log != NULL)
1139 mctx->state_log[cur_str_idx] = cur_state;
1141 /* Check OP_OPEN_SUBEXP in the initial state in case that we use them
1142 later. E.g. Processing back references. */
1143 if (BE (dfa->nbackref, 0))
1145 at_init_state = false;
1146 err = check_subexp_matching_top (mctx, &cur_state->nodes, 0);
1147 if (BE (err != REG_NOERROR, 0))
1150 if (cur_state->has_backref)
1152 err = transit_state_bkref (mctx, &cur_state->nodes);
1153 if (BE (err != REG_NOERROR, 0))
1159 /* If the RE accepts NULL string. */
1160 if (BE (cur_state->halt, 0))
1162 if (!cur_state->has_constraint
1163 || check_halt_state_context (mctx, cur_state, cur_str_idx))
1165 if (!fl_longest_match)
1169 match_last = cur_str_idx;
1175 while (!re_string_eoi (&mctx->input))
1177 re_dfastate_t *old_state = cur_state;
1178 Idx next_char_idx = re_string_cur_idx (&mctx->input) + 1;
1180 if (BE (next_char_idx >= mctx->input.bufs_len, 0)
1181 || (BE (next_char_idx >= mctx->input.valid_len, 0)
1182 && mctx->input.valid_len < mctx->input.len))
1184 err = extend_buffers (mctx);
1185 if (BE (err != REG_NOERROR, 0))
1187 assert (err == REG_ESPACE);
1192 cur_state = transit_state (&err, mctx, cur_state);
1193 if (mctx->state_log != NULL)
1194 cur_state = merge_state_with_log (&err, mctx, cur_state);
1196 if (cur_state == NULL)
1198 /* Reached the invalid state or an error. Try to recover a valid
1199 state using the state log, if available and if we have not
1200 already found a valid (even if not the longest) match. */
1201 if (BE (err != REG_NOERROR, 0))
1204 if (mctx->state_log == NULL
1205 || (match && !fl_longest_match)
1206 || (cur_state = find_recover_state (&err, mctx)) == NULL)
1210 if (BE (at_init_state, 0))
1212 if (old_state == cur_state)
1213 next_start_idx = next_char_idx;
1215 at_init_state = false;
1218 if (cur_state->halt)
1220 /* Reached a halt state.
1221 Check the halt state can satisfy the current context. */
1222 if (!cur_state->has_constraint
1223 || check_halt_state_context (mctx, cur_state,
1224 re_string_cur_idx (&mctx->input)))
1226 /* We found an appropriate halt state. */
1227 match_last = re_string_cur_idx (&mctx->input);
1230 /* We found a match, do not modify match_first below. */
1231 p_match_first = NULL;
1232 if (!fl_longest_match)
1239 *p_match_first += next_start_idx;
1244 /* Check NODE match the current context. */
1248 check_halt_node_context (const re_dfa_t *dfa, Idx node, unsigned int context)
1250 re_token_type_t type = dfa->nodes[node].type;
1251 unsigned int constraint = dfa->nodes[node].constraint;
1252 if (type != END_OF_RE)
1256 if (NOT_SATISFY_NEXT_CONSTRAINT (constraint, context))
1261 /* Check the halt state STATE match the current context.
1262 Return 0 if not match, if the node, STATE has, is a halt node and
1263 match the context, return the node. */
1267 check_halt_state_context (const re_match_context_t *mctx,
1268 const re_dfastate_t *state, Idx idx)
1271 unsigned int context;
1273 assert (state->halt);
1275 context = re_string_context_at (&mctx->input, idx, mctx->eflags);
1276 for (i = 0; i < state->nodes.nelem; ++i)
1277 if (check_halt_node_context (mctx->dfa, state->nodes.elems[i], context))
1278 return state->nodes.elems[i];
1282 /* Compute the next node to which "NFA" transit from NODE("NFA" is a NFA
1283 corresponding to the DFA).
1284 Return the destination node, and update EPS_VIA_NODES;
1285 return REG_MISSING in case of errors. */
1289 proceed_next_node (const re_match_context_t *mctx, Idx nregs, regmatch_t *regs,
1290 Idx *pidx, Idx node, re_node_set *eps_via_nodes,
1291 struct re_fail_stack_t *fs)
1293 const re_dfa_t *const dfa = mctx->dfa;
1296 if (IS_EPSILON_NODE (dfa->nodes[node].type))
1298 re_node_set *cur_nodes = &mctx->state_log[*pidx]->nodes;
1299 re_node_set *edests = &dfa->edests[node];
1301 ok = re_node_set_insert (eps_via_nodes, node);
1304 /* Pick up a valid destination, or return REG_MISSING if none
1306 for (dest_node = REG_MISSING, i = 0; i < edests->nelem; ++i)
1308 Idx candidate = edests->elems[i];
1309 if (!re_node_set_contains (cur_nodes, candidate))
1311 if (dest_node == REG_MISSING)
1312 dest_node = candidate;
1316 /* In order to avoid infinite loop like "(a*)*", return the second
1317 epsilon-transition if the first was already considered. */
1318 if (re_node_set_contains (eps_via_nodes, dest_node))
1321 /* Otherwise, push the second epsilon-transition on the fail stack. */
1323 && push_fail_stack (fs, *pidx, candidate, nregs, regs,
1327 /* We know we are going to exit. */
1336 re_token_type_t type = dfa->nodes[node].type;
1338 #ifdef RE_ENABLE_I18N
1339 if (dfa->nodes[node].accept_mb)
1340 naccepted = check_node_accept_bytes (dfa, node, &mctx->input, *pidx);
1342 #endif /* RE_ENABLE_I18N */
1343 if (type == OP_BACK_REF)
1345 Idx subexp_idx = dfa->nodes[node].opr.idx + 1;
1346 naccepted = regs[subexp_idx].rm_eo - regs[subexp_idx].rm_so;
1349 if (regs[subexp_idx].rm_so == -1 || regs[subexp_idx].rm_eo == -1)
1353 char *buf = (char *) re_string_get_buffer (&mctx->input);
1354 if (memcmp (buf + regs[subexp_idx].rm_so, buf + *pidx,
1363 ok = re_node_set_insert (eps_via_nodes, node);
1366 dest_node = dfa->edests[node].elems[0];
1367 if (re_node_set_contains (&mctx->state_log[*pidx]->nodes,
1374 || check_node_accept (mctx, dfa->nodes + node, *pidx))
1376 Idx dest_node = dfa->nexts[node];
1377 *pidx = (naccepted == 0) ? *pidx + 1 : *pidx + naccepted;
1378 if (fs && (*pidx > mctx->match_last || mctx->state_log[*pidx] == NULL
1379 || !re_node_set_contains (&mctx->state_log[*pidx]->nodes,
1382 re_node_set_empty (eps_via_nodes);
1389 static reg_errcode_t
1390 internal_function __attribute_warn_unused_result__
1391 push_fail_stack (struct re_fail_stack_t *fs, Idx str_idx, Idx dest_node,
1392 Idx nregs, regmatch_t *regs, re_node_set *eps_via_nodes)
1395 Idx num = fs->num++;
1396 if (fs->num == fs->alloc)
1398 struct re_fail_stack_ent_t *new_array;
1399 new_array = realloc (fs->stack, (sizeof (struct re_fail_stack_ent_t)
1401 if (new_array == NULL)
1404 fs->stack = new_array;
1406 fs->stack[num].idx = str_idx;
1407 fs->stack[num].node = dest_node;
1408 fs->stack[num].regs = re_malloc (regmatch_t, nregs);
1409 if (fs->stack[num].regs == NULL)
1411 memcpy (fs->stack[num].regs, regs, sizeof (regmatch_t) * nregs);
1412 err = re_node_set_init_copy (&fs->stack[num].eps_via_nodes, eps_via_nodes);
1418 pop_fail_stack (struct re_fail_stack_t *fs, Idx *pidx, Idx nregs,
1419 regmatch_t *regs, re_node_set *eps_via_nodes)
1421 Idx num = --fs->num;
1422 assert (REG_VALID_INDEX (num));
1423 *pidx = fs->stack[num].idx;
1424 memcpy (regs, fs->stack[num].regs, sizeof (regmatch_t) * nregs);
1425 re_node_set_free (eps_via_nodes);
1426 re_free (fs->stack[num].regs);
1427 *eps_via_nodes = fs->stack[num].eps_via_nodes;
1428 return fs->stack[num].node;
1431 /* Set the positions where the subexpressions are starts/ends to registers
1433 Note: We assume that pmatch[0] is already set, and
1434 pmatch[i].rm_so == pmatch[i].rm_eo == -1 for 0 < i < nmatch. */
1436 static reg_errcode_t
1437 internal_function __attribute_warn_unused_result__
1438 set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
1439 regmatch_t *pmatch, bool fl_backtrack)
1441 const re_dfa_t *dfa = (const re_dfa_t *) preg->buffer;
1443 re_node_set eps_via_nodes;
1444 struct re_fail_stack_t *fs;
1445 struct re_fail_stack_t fs_body = { 0, 2, NULL };
1446 regmatch_t *prev_idx_match;
1447 bool prev_idx_match_malloced = false;
1450 assert (nmatch > 1);
1451 assert (mctx->state_log != NULL);
1456 fs->stack = re_malloc (struct re_fail_stack_ent_t, fs->alloc);
1457 if (fs->stack == NULL)
1463 cur_node = dfa->init_node;
1464 re_node_set_init_empty (&eps_via_nodes);
1466 if (__libc_use_alloca (nmatch * sizeof (regmatch_t)))
1467 prev_idx_match = (regmatch_t *) alloca (nmatch * sizeof (regmatch_t));
1470 prev_idx_match = re_malloc (regmatch_t, nmatch);
1471 if (prev_idx_match == NULL)
1473 free_fail_stack_return (fs);
1476 prev_idx_match_malloced = true;
1478 memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
1480 for (idx = pmatch[0].rm_so; idx <= pmatch[0].rm_eo ;)
1482 update_regs (dfa, pmatch, prev_idx_match, cur_node, idx, nmatch);
1484 if (idx == pmatch[0].rm_eo && cur_node == mctx->last_node)
1489 for (reg_idx = 0; reg_idx < nmatch; ++reg_idx)
1490 if (pmatch[reg_idx].rm_so > -1 && pmatch[reg_idx].rm_eo == -1)
1492 if (reg_idx == nmatch)
1494 re_node_set_free (&eps_via_nodes);
1495 if (prev_idx_match_malloced)
1496 re_free (prev_idx_match);
1497 return free_fail_stack_return (fs);
1499 cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
1504 re_node_set_free (&eps_via_nodes);
1505 if (prev_idx_match_malloced)
1506 re_free (prev_idx_match);
1511 /* Proceed to next node. */
1512 cur_node = proceed_next_node (mctx, nmatch, pmatch, &idx, cur_node,
1513 &eps_via_nodes, fs);
1515 if (BE (! REG_VALID_INDEX (cur_node), 0))
1517 if (BE (cur_node == REG_ERROR, 0))
1519 re_node_set_free (&eps_via_nodes);
1520 if (prev_idx_match_malloced)
1521 re_free (prev_idx_match);
1522 free_fail_stack_return (fs);
1526 cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
1530 re_node_set_free (&eps_via_nodes);
1531 if (prev_idx_match_malloced)
1532 re_free (prev_idx_match);
1537 re_node_set_free (&eps_via_nodes);
1538 if (prev_idx_match_malloced)
1539 re_free (prev_idx_match);
1540 return free_fail_stack_return (fs);
1543 static reg_errcode_t
1545 free_fail_stack_return (struct re_fail_stack_t *fs)
1550 for (fs_idx = 0; fs_idx < fs->num; ++fs_idx)
1552 re_node_set_free (&fs->stack[fs_idx].eps_via_nodes);
1553 re_free (fs->stack[fs_idx].regs);
1555 re_free (fs->stack);
1562 update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
1563 regmatch_t *prev_idx_match, Idx cur_node, Idx cur_idx, Idx nmatch)
1565 int type = dfa->nodes[cur_node].type;
1566 if (type == OP_OPEN_SUBEXP)
1568 Idx reg_num = dfa->nodes[cur_node].opr.idx + 1;
1570 /* We are at the first node of this sub expression. */
1571 if (reg_num < nmatch)
1573 pmatch[reg_num].rm_so = cur_idx;
1574 pmatch[reg_num].rm_eo = -1;
1577 else if (type == OP_CLOSE_SUBEXP)
1579 Idx reg_num = dfa->nodes[cur_node].opr.idx + 1;
1580 if (reg_num < nmatch)
1582 /* We are at the last node of this sub expression. */
1583 if (pmatch[reg_num].rm_so < cur_idx)
1585 pmatch[reg_num].rm_eo = cur_idx;
1586 /* This is a non-empty match or we are not inside an optional
1587 subexpression. Accept this right away. */
1588 memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
1592 if (dfa->nodes[cur_node].opt_subexp
1593 && prev_idx_match[reg_num].rm_so != -1)
1594 /* We transited through an empty match for an optional
1595 subexpression, like (a?)*, and this is not the subexp's
1596 first match. Copy back the old content of the registers
1597 so that matches of an inner subexpression are undone as
1598 well, like in ((a?))*. */
1599 memcpy (pmatch, prev_idx_match, sizeof (regmatch_t) * nmatch);
1601 /* We completed a subexpression, but it may be part of
1602 an optional one, so do not update PREV_IDX_MATCH. */
1603 pmatch[reg_num].rm_eo = cur_idx;
1609 /* This function checks the STATE_LOG from the SCTX->last_str_idx to 0
1610 and sift the nodes in each states according to the following rules.
1611 Updated state_log will be wrote to STATE_LOG.
1613 Rules: We throw away the Node `a' in the STATE_LOG[STR_IDX] if...
1614 1. When STR_IDX == MATCH_LAST(the last index in the state_log):
1615 If `a' isn't the LAST_NODE and `a' can't epsilon transit to
1616 the LAST_NODE, we throw away the node `a'.
1617 2. When 0 <= STR_IDX < MATCH_LAST and `a' accepts
1618 string `s' and transit to `b':
1619 i. If 'b' isn't in the STATE_LOG[STR_IDX+strlen('s')], we throw
1621 ii. If 'b' is in the STATE_LOG[STR_IDX+strlen('s')] but 'b' is
1622 thrown away, we throw away the node `a'.
1623 3. When 0 <= STR_IDX < MATCH_LAST and 'a' epsilon transit to 'b':
1624 i. If 'b' isn't in the STATE_LOG[STR_IDX], we throw away the
1626 ii. If 'b' is in the STATE_LOG[STR_IDX] but 'b' is thrown away,
1627 we throw away the node `a'. */
1629 #define STATE_NODE_CONTAINS(state,node) \
1630 ((state) != NULL && re_node_set_contains (&(state)->nodes, node))
1632 static reg_errcode_t
1634 sift_states_backward (const re_match_context_t *mctx, re_sift_context_t *sctx)
1638 Idx str_idx = sctx->last_str_idx;
1639 re_node_set cur_dest;
1642 assert (mctx->state_log != NULL && mctx->state_log[str_idx] != NULL);
1645 /* Build sifted state_log[str_idx]. It has the nodes which can epsilon
1646 transit to the last_node and the last_node itself. */
1647 err = re_node_set_init_1 (&cur_dest, sctx->last_node);
1648 if (BE (err != REG_NOERROR, 0))
1650 err = update_cur_sifted_state (mctx, sctx, str_idx, &cur_dest);
1651 if (BE (err != REG_NOERROR, 0))
1654 /* Then check each states in the state_log. */
1657 /* Update counters. */
1658 null_cnt = (sctx->sifted_states[str_idx] == NULL) ? null_cnt + 1 : 0;
1659 if (null_cnt > mctx->max_mb_elem_len)
1661 memset (sctx->sifted_states, '\0',
1662 sizeof (re_dfastate_t *) * str_idx);
1663 re_node_set_free (&cur_dest);
1666 re_node_set_empty (&cur_dest);
1669 if (mctx->state_log[str_idx])
1671 err = build_sifted_states (mctx, sctx, str_idx, &cur_dest);
1672 if (BE (err != REG_NOERROR, 0))
1676 /* Add all the nodes which satisfy the following conditions:
1677 - It can epsilon transit to a node in CUR_DEST.
1679 And update state_log. */
1680 err = update_cur_sifted_state (mctx, sctx, str_idx, &cur_dest);
1681 if (BE (err != REG_NOERROR, 0))
1686 re_node_set_free (&cur_dest);
1690 static reg_errcode_t
1691 internal_function __attribute_warn_unused_result__
1692 build_sifted_states (const re_match_context_t *mctx, re_sift_context_t *sctx,
1693 Idx str_idx, re_node_set *cur_dest)
1695 const re_dfa_t *const dfa = mctx->dfa;
1696 const re_node_set *cur_src = &mctx->state_log[str_idx]->non_eps_nodes;
1699 /* Then build the next sifted state.
1700 We build the next sifted state on `cur_dest', and update
1701 `sifted_states[str_idx]' with `cur_dest'.
1703 `cur_dest' is the sifted state from `state_log[str_idx + 1]'.
1704 `cur_src' points the node_set of the old `state_log[str_idx]'
1705 (with the epsilon nodes pre-filtered out). */
1706 for (i = 0; i < cur_src->nelem; i++)
1708 Idx prev_node = cur_src->elems[i];
1713 re_token_type_t type = dfa->nodes[prev_node].type;
1714 assert (!IS_EPSILON_NODE (type));
1716 #ifdef RE_ENABLE_I18N
1717 /* If the node may accept `multi byte'. */
1718 if (dfa->nodes[prev_node].accept_mb)
1719 naccepted = sift_states_iter_mb (mctx, sctx, prev_node,
1720 str_idx, sctx->last_str_idx);
1721 #endif /* RE_ENABLE_I18N */
1723 /* We don't check backreferences here.
1724 See update_cur_sifted_state(). */
1726 && check_node_accept (mctx, dfa->nodes + prev_node, str_idx)
1727 && STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + 1],
1728 dfa->nexts[prev_node]))
1734 if (sctx->limits.nelem)
1736 Idx to_idx = str_idx + naccepted;
1737 if (check_dst_limits (mctx, &sctx->limits,
1738 dfa->nexts[prev_node], to_idx,
1739 prev_node, str_idx))
1742 ok = re_node_set_insert (cur_dest, prev_node);
1750 /* Helper functions. */
1752 static reg_errcode_t
1754 clean_state_log_if_needed (re_match_context_t *mctx, Idx next_state_log_idx)
1756 Idx top = mctx->state_log_top;
1758 if (next_state_log_idx >= mctx->input.bufs_len
1759 || (next_state_log_idx >= mctx->input.valid_len
1760 && mctx->input.valid_len < mctx->input.len))
1763 err = extend_buffers (mctx);
1764 if (BE (err != REG_NOERROR, 0))
1768 if (top < next_state_log_idx)
1770 memset (mctx->state_log + top + 1, '\0',
1771 sizeof (re_dfastate_t *) * (next_state_log_idx - top));
1772 mctx->state_log_top = next_state_log_idx;
1777 static reg_errcode_t
1779 merge_state_array (const re_dfa_t *dfa, re_dfastate_t **dst,
1780 re_dfastate_t **src, Idx num)
1784 for (st_idx = 0; st_idx < num; ++st_idx)
1786 if (dst[st_idx] == NULL)
1787 dst[st_idx] = src[st_idx];
1788 else if (src[st_idx] != NULL)
1790 re_node_set merged_set;
1791 err = re_node_set_init_union (&merged_set, &dst[st_idx]->nodes,
1792 &src[st_idx]->nodes);
1793 if (BE (err != REG_NOERROR, 0))
1795 dst[st_idx] = re_acquire_state (&err, dfa, &merged_set);
1796 re_node_set_free (&merged_set);
1797 if (BE (err != REG_NOERROR, 0))
1804 static reg_errcode_t
1806 update_cur_sifted_state (const re_match_context_t *mctx,
1807 re_sift_context_t *sctx, Idx str_idx,
1808 re_node_set *dest_nodes)
1810 const re_dfa_t *const dfa = mctx->dfa;
1811 reg_errcode_t err = REG_NOERROR;
1812 const re_node_set *candidates;
1813 candidates = ((mctx->state_log[str_idx] == NULL) ? NULL
1814 : &mctx->state_log[str_idx]->nodes);
1816 if (dest_nodes->nelem == 0)
1817 sctx->sifted_states[str_idx] = NULL;
1822 /* At first, add the nodes which can epsilon transit to a node in
1824 err = add_epsilon_src_nodes (dfa, dest_nodes, candidates);
1825 if (BE (err != REG_NOERROR, 0))
1828 /* Then, check the limitations in the current sift_context. */
1829 if (sctx->limits.nelem)
1831 err = check_subexp_limits (dfa, dest_nodes, candidates, &sctx->limits,
1832 mctx->bkref_ents, str_idx);
1833 if (BE (err != REG_NOERROR, 0))
1838 sctx->sifted_states[str_idx] = re_acquire_state (&err, dfa, dest_nodes);
1839 if (BE (err != REG_NOERROR, 0))
1843 if (candidates && mctx->state_log[str_idx]->has_backref)
1845 err = sift_states_bkref (mctx, sctx, str_idx, candidates);
1846 if (BE (err != REG_NOERROR, 0))
1852 static reg_errcode_t
1853 internal_function __attribute_warn_unused_result__
1854 add_epsilon_src_nodes (const re_dfa_t *dfa, re_node_set *dest_nodes,
1855 const re_node_set *candidates)
1857 reg_errcode_t err = REG_NOERROR;
1860 re_dfastate_t *state = re_acquire_state (&err, dfa, dest_nodes);
1861 if (BE (err != REG_NOERROR, 0))
1864 if (!state->inveclosure.alloc)
1866 err = re_node_set_alloc (&state->inveclosure, dest_nodes->nelem);
1867 if (BE (err != REG_NOERROR, 0))
1869 for (i = 0; i < dest_nodes->nelem; i++)
1871 err = re_node_set_merge (&state->inveclosure,
1872 dfa->inveclosures + dest_nodes->elems[i]);
1873 if (BE (err != REG_NOERROR, 0))
1877 return re_node_set_add_intersect (dest_nodes, candidates,
1878 &state->inveclosure);
1881 static reg_errcode_t
1883 sub_epsilon_src_nodes (const re_dfa_t *dfa, Idx node, re_node_set *dest_nodes,
1884 const re_node_set *candidates)
1888 re_node_set *inv_eclosure = dfa->inveclosures + node;
1889 re_node_set except_nodes;
1890 re_node_set_init_empty (&except_nodes);
1891 for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx)
1893 Idx cur_node = inv_eclosure->elems[ecl_idx];
1894 if (cur_node == node)
1896 if (IS_EPSILON_NODE (dfa->nodes[cur_node].type))
1898 Idx edst1 = dfa->edests[cur_node].elems[0];
1899 Idx edst2 = ((dfa->edests[cur_node].nelem > 1)
1900 ? dfa->edests[cur_node].elems[1] : REG_MISSING);
1901 if ((!re_node_set_contains (inv_eclosure, edst1)
1902 && re_node_set_contains (dest_nodes, edst1))
1903 || (REG_VALID_NONZERO_INDEX (edst2)
1904 && !re_node_set_contains (inv_eclosure, edst2)
1905 && re_node_set_contains (dest_nodes, edst2)))
1907 err = re_node_set_add_intersect (&except_nodes, candidates,
1908 dfa->inveclosures + cur_node);
1909 if (BE (err != REG_NOERROR, 0))
1911 re_node_set_free (&except_nodes);
1917 for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx)
1919 Idx cur_node = inv_eclosure->elems[ecl_idx];
1920 if (!re_node_set_contains (&except_nodes, cur_node))
1922 Idx idx = re_node_set_contains (dest_nodes, cur_node) - 1;
1923 re_node_set_remove_at (dest_nodes, idx);
1926 re_node_set_free (&except_nodes);
1932 check_dst_limits (const re_match_context_t *mctx, const re_node_set *limits,
1933 Idx dst_node, Idx dst_idx, Idx src_node, Idx src_idx)
1935 const re_dfa_t *const dfa = mctx->dfa;
1936 Idx lim_idx, src_pos, dst_pos;
1938 Idx dst_bkref_idx = search_cur_bkref_entry (mctx, dst_idx);
1939 Idx src_bkref_idx = search_cur_bkref_entry (mctx, src_idx);
1940 for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx)
1943 struct re_backref_cache_entry *ent;
1944 ent = mctx->bkref_ents + limits->elems[lim_idx];
1945 subexp_idx = dfa->nodes[ent->node].opr.idx;
1947 dst_pos = check_dst_limits_calc_pos (mctx, limits->elems[lim_idx],
1948 subexp_idx, dst_node, dst_idx,
1950 src_pos = check_dst_limits_calc_pos (mctx, limits->elems[lim_idx],
1951 subexp_idx, src_node, src_idx,
1955 <src> <dst> ( <subexp> )
1956 ( <subexp> ) <src> <dst>
1957 ( <subexp1> <src> <subexp2> <dst> <subexp3> ) */
1958 if (src_pos == dst_pos)
1959 continue; /* This is unrelated limitation. */
1968 check_dst_limits_calc_pos_1 (const re_match_context_t *mctx, int boundaries,
1969 Idx subexp_idx, Idx from_node, Idx bkref_idx)
1971 const re_dfa_t *const dfa = mctx->dfa;
1972 const re_node_set *eclosures = dfa->eclosures + from_node;
1975 /* Else, we are on the boundary: examine the nodes on the epsilon
1977 for (node_idx = 0; node_idx < eclosures->nelem; ++node_idx)
1979 Idx node = eclosures->elems[node_idx];
1980 switch (dfa->nodes[node].type)
1983 if (bkref_idx != REG_MISSING)
1985 struct re_backref_cache_entry *ent = mctx->bkref_ents + bkref_idx;
1991 if (ent->node != node)
1994 if (subexp_idx < BITSET_WORD_BITS
1995 && !(ent->eps_reachable_subexps_map
1996 & ((bitset_word_t) 1 << subexp_idx)))
1999 /* Recurse trying to reach the OP_OPEN_SUBEXP and
2000 OP_CLOSE_SUBEXP cases below. But, if the
2001 destination node is the same node as the source
2002 node, don't recurse because it would cause an
2003 infinite loop: a regex that exhibits this behavior
2005 dst = dfa->edests[node].elems[0];
2006 if (dst == from_node)
2010 else /* if (boundaries & 2) */
2015 check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx,
2017 if (cpos == -1 /* && (boundaries & 1) */)
2019 if (cpos == 0 && (boundaries & 2))
2022 if (subexp_idx < BITSET_WORD_BITS)
2023 ent->eps_reachable_subexps_map
2024 &= ~((bitset_word_t) 1 << subexp_idx);
2026 while (ent++->more);
2030 case OP_OPEN_SUBEXP:
2031 if ((boundaries & 1) && subexp_idx == dfa->nodes[node].opr.idx)
2035 case OP_CLOSE_SUBEXP:
2036 if ((boundaries & 2) && subexp_idx == dfa->nodes[node].opr.idx)
2045 return (boundaries & 2) ? 1 : 0;
2050 check_dst_limits_calc_pos (const re_match_context_t *mctx, Idx limit,
2051 Idx subexp_idx, Idx from_node, Idx str_idx,
2054 struct re_backref_cache_entry *lim = mctx->bkref_ents + limit;
2057 /* If we are outside the range of the subexpression, return -1 or 1. */
2058 if (str_idx < lim->subexp_from)
2061 if (lim->subexp_to < str_idx)
2064 /* If we are within the subexpression, return 0. */
2065 boundaries = (str_idx == lim->subexp_from);
2066 boundaries |= (str_idx == lim->subexp_to) << 1;
2067 if (boundaries == 0)
2070 /* Else, examine epsilon closure. */
2071 return check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx,
2072 from_node, bkref_idx);
2075 /* Check the limitations of sub expressions LIMITS, and remove the nodes
2076 which are against limitations from DEST_NODES. */
2078 static reg_errcode_t
2080 check_subexp_limits (const re_dfa_t *dfa, re_node_set *dest_nodes,
2081 const re_node_set *candidates, re_node_set *limits,
2082 struct re_backref_cache_entry *bkref_ents, Idx str_idx)
2085 Idx node_idx, lim_idx;
2087 for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx)
2090 struct re_backref_cache_entry *ent;
2091 ent = bkref_ents + limits->elems[lim_idx];
2093 if (str_idx <= ent->subexp_from || ent->str_idx < str_idx)
2094 continue; /* This is unrelated limitation. */
2096 subexp_idx = dfa->nodes[ent->node].opr.idx;
2097 if (ent->subexp_to == str_idx)
2099 Idx ops_node = REG_MISSING;
2100 Idx cls_node = REG_MISSING;
2101 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2103 Idx node = dest_nodes->elems[node_idx];
2104 re_token_type_t type = dfa->nodes[node].type;
2105 if (type == OP_OPEN_SUBEXP
2106 && subexp_idx == dfa->nodes[node].opr.idx)
2108 else if (type == OP_CLOSE_SUBEXP
2109 && subexp_idx == dfa->nodes[node].opr.idx)
2113 /* Check the limitation of the open subexpression. */
2114 /* Note that (ent->subexp_to = str_idx != ent->subexp_from). */
2115 if (REG_VALID_INDEX (ops_node))
2117 err = sub_epsilon_src_nodes (dfa, ops_node, dest_nodes,
2119 if (BE (err != REG_NOERROR, 0))
2123 /* Check the limitation of the close subexpression. */
2124 if (REG_VALID_INDEX (cls_node))
2125 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2127 Idx node = dest_nodes->elems[node_idx];
2128 if (!re_node_set_contains (dfa->inveclosures + node,
2130 && !re_node_set_contains (dfa->eclosures + node,
2133 /* It is against this limitation.
2134 Remove it form the current sifted state. */
2135 err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2137 if (BE (err != REG_NOERROR, 0))
2143 else /* (ent->subexp_to != str_idx) */
2145 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2147 Idx node = dest_nodes->elems[node_idx];
2148 re_token_type_t type = dfa->nodes[node].type;
2149 if (type == OP_CLOSE_SUBEXP || type == OP_OPEN_SUBEXP)
2151 if (subexp_idx != dfa->nodes[node].opr.idx)
2153 /* It is against this limitation.
2154 Remove it form the current sifted state. */
2155 err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2157 if (BE (err != REG_NOERROR, 0))
2166 static reg_errcode_t
2167 internal_function __attribute_warn_unused_result__
2168 sift_states_bkref (const re_match_context_t *mctx, re_sift_context_t *sctx,
2169 Idx str_idx, const re_node_set *candidates)
2171 const re_dfa_t *const dfa = mctx->dfa;
2174 re_sift_context_t local_sctx;
2175 Idx first_idx = search_cur_bkref_entry (mctx, str_idx);
2177 if (first_idx == REG_MISSING)
2180 local_sctx.sifted_states = NULL; /* Mark that it hasn't been initialized. */
2182 for (node_idx = 0; node_idx < candidates->nelem; ++node_idx)
2185 re_token_type_t type;
2186 struct re_backref_cache_entry *entry;
2187 node = candidates->elems[node_idx];
2188 type = dfa->nodes[node].type;
2189 /* Avoid infinite loop for the REs like "()\1+". */
2190 if (node == sctx->last_node && str_idx == sctx->last_str_idx)
2192 if (type != OP_BACK_REF)
2195 entry = mctx->bkref_ents + first_idx;
2196 enabled_idx = first_idx;
2203 re_dfastate_t *cur_state;
2205 if (entry->node != node)
2207 subexp_len = entry->subexp_to - entry->subexp_from;
2208 to_idx = str_idx + subexp_len;
2209 dst_node = (subexp_len ? dfa->nexts[node]
2210 : dfa->edests[node].elems[0]);
2212 if (to_idx > sctx->last_str_idx
2213 || sctx->sifted_states[to_idx] == NULL
2214 || !STATE_NODE_CONTAINS (sctx->sifted_states[to_idx], dst_node)
2215 || check_dst_limits (mctx, &sctx->limits, node,
2216 str_idx, dst_node, to_idx))
2219 if (local_sctx.sifted_states == NULL)
2222 err = re_node_set_init_copy (&local_sctx.limits, &sctx->limits);
2223 if (BE (err != REG_NOERROR, 0))
2226 local_sctx.last_node = node;
2227 local_sctx.last_str_idx = str_idx;
2228 ok = re_node_set_insert (&local_sctx.limits, enabled_idx);
2234 cur_state = local_sctx.sifted_states[str_idx];
2235 err = sift_states_backward (mctx, &local_sctx);
2236 if (BE (err != REG_NOERROR, 0))
2238 if (sctx->limited_states != NULL)
2240 err = merge_state_array (dfa, sctx->limited_states,
2241 local_sctx.sifted_states,
2243 if (BE (err != REG_NOERROR, 0))
2246 local_sctx.sifted_states[str_idx] = cur_state;
2247 re_node_set_remove (&local_sctx.limits, enabled_idx);
2249 /* mctx->bkref_ents may have changed, reload the pointer. */
2250 entry = mctx->bkref_ents + enabled_idx;
2252 while (enabled_idx++, entry++->more);
2256 if (local_sctx.sifted_states != NULL)
2258 re_node_set_free (&local_sctx.limits);
2265 #ifdef RE_ENABLE_I18N
2268 sift_states_iter_mb (const re_match_context_t *mctx, re_sift_context_t *sctx,
2269 Idx node_idx, Idx str_idx, Idx max_str_idx)
2271 const re_dfa_t *const dfa = mctx->dfa;
2273 /* Check the node can accept `multi byte'. */
2274 naccepted = check_node_accept_bytes (dfa, node_idx, &mctx->input, str_idx);
2275 if (naccepted > 0 && str_idx + naccepted <= max_str_idx &&
2276 !STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + naccepted],
2277 dfa->nexts[node_idx]))
2278 /* The node can't accept the `multi byte', or the
2279 destination was already thrown away, then the node
2280 could't accept the current input `multi byte'. */
2282 /* Otherwise, it is sure that the node could accept
2283 `naccepted' bytes input. */
2286 #endif /* RE_ENABLE_I18N */
2289 /* Functions for state transition. */
2291 /* Return the next state to which the current state STATE will transit by
2292 accepting the current input byte, and update STATE_LOG if necessary.
2293 If STATE can accept a multibyte char/collating element/back reference
2294 update the destination of STATE_LOG. */
2296 static re_dfastate_t *
2297 internal_function __attribute_warn_unused_result__
2298 transit_state (reg_errcode_t *err, re_match_context_t *mctx,
2299 re_dfastate_t *state)
2301 re_dfastate_t **trtable;
2304 #ifdef RE_ENABLE_I18N
2305 /* If the current state can accept multibyte. */
2306 if (BE (state->accept_mb, 0))
2308 *err = transit_state_mb (mctx, state);
2309 if (BE (*err != REG_NOERROR, 0))
2312 #endif /* RE_ENABLE_I18N */
2314 /* Then decide the next state with the single byte. */
2317 /* don't use transition table */
2318 return transit_state_sb (err, mctx, state);
2321 /* Use transition table */
2322 ch = re_string_fetch_byte (&mctx->input);
2325 trtable = state->trtable;
2326 if (BE (trtable != NULL, 1))
2329 trtable = state->word_trtable;
2330 if (BE (trtable != NULL, 1))
2332 unsigned int context;
2334 = re_string_context_at (&mctx->input,
2335 re_string_cur_idx (&mctx->input) - 1,
2337 if (IS_WORD_CONTEXT (context))
2338 return trtable[ch + SBC_MAX];
2343 if (!build_trtable (mctx->dfa, state))
2349 /* Retry, we now have a transition table. */
2353 /* Update the state_log if we need */
2354 static re_dfastate_t *
2356 merge_state_with_log (reg_errcode_t *err, re_match_context_t *mctx,
2357 re_dfastate_t *next_state)
2359 const re_dfa_t *const dfa = mctx->dfa;
2360 Idx cur_idx = re_string_cur_idx (&mctx->input);
2362 if (cur_idx > mctx->state_log_top)
2364 mctx->state_log[cur_idx] = next_state;
2365 mctx->state_log_top = cur_idx;
2367 else if (mctx->state_log[cur_idx] == 0)
2369 mctx->state_log[cur_idx] = next_state;
2373 re_dfastate_t *pstate;
2374 unsigned int context;
2375 re_node_set next_nodes, *log_nodes, *table_nodes = NULL;
2376 /* If (state_log[cur_idx] != 0), it implies that cur_idx is
2377 the destination of a multibyte char/collating element/
2378 back reference. Then the next state is the union set of
2379 these destinations and the results of the transition table. */
2380 pstate = mctx->state_log[cur_idx];
2381 log_nodes = pstate->entrance_nodes;
2382 if (next_state != NULL)
2384 table_nodes = next_state->entrance_nodes;
2385 *err = re_node_set_init_union (&next_nodes, table_nodes,
2387 if (BE (*err != REG_NOERROR, 0))
2391 next_nodes = *log_nodes;
2392 /* Note: We already add the nodes of the initial state,
2393 then we don't need to add them here. */
2395 context = re_string_context_at (&mctx->input,
2396 re_string_cur_idx (&mctx->input) - 1,
2398 next_state = mctx->state_log[cur_idx]
2399 = re_acquire_state_context (err, dfa, &next_nodes, context);
2400 /* We don't need to check errors here, since the return value of
2401 this function is next_state and ERR is already set. */
2403 if (table_nodes != NULL)
2404 re_node_set_free (&next_nodes);
2407 if (BE (dfa->nbackref, 0) && next_state != NULL)
2409 /* Check OP_OPEN_SUBEXP in the current state in case that we use them
2410 later. We must check them here, since the back references in the
2411 next state might use them. */
2412 *err = check_subexp_matching_top (mctx, &next_state->nodes,
2414 if (BE (*err != REG_NOERROR, 0))
2417 /* If the next state has back references. */
2418 if (next_state->has_backref)
2420 *err = transit_state_bkref (mctx, &next_state->nodes);
2421 if (BE (*err != REG_NOERROR, 0))
2423 next_state = mctx->state_log[cur_idx];
2430 /* Skip bytes in the input that correspond to part of a
2431 multi-byte match, then look in the log for a state
2432 from which to restart matching. */
2433 static re_dfastate_t *
2435 find_recover_state (reg_errcode_t *err, re_match_context_t *mctx)
2437 re_dfastate_t *cur_state;
2440 Idx max = mctx->state_log_top;
2441 Idx cur_str_idx = re_string_cur_idx (&mctx->input);
2445 if (++cur_str_idx > max)
2447 re_string_skip_bytes (&mctx->input, 1);
2449 while (mctx->state_log[cur_str_idx] == NULL);
2451 cur_state = merge_state_with_log (err, mctx, NULL);
2453 while (*err == REG_NOERROR && cur_state == NULL);
2457 /* Helper functions for transit_state. */
2459 /* From the node set CUR_NODES, pick up the nodes whose types are
2460 OP_OPEN_SUBEXP and which have corresponding back references in the regular
2461 expression. And register them to use them later for evaluating the
2462 correspoding back references. */
2464 static reg_errcode_t
2466 check_subexp_matching_top (re_match_context_t *mctx, re_node_set *cur_nodes,
2469 const re_dfa_t *const dfa = mctx->dfa;
2473 /* TODO: This isn't efficient.
2474 Because there might be more than one nodes whose types are
2475 OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
2478 for (node_idx = 0; node_idx < cur_nodes->nelem; ++node_idx)
2480 Idx node = cur_nodes->elems[node_idx];
2481 if (dfa->nodes[node].type == OP_OPEN_SUBEXP
2482 && dfa->nodes[node].opr.idx < BITSET_WORD_BITS
2483 && (dfa->used_bkref_map
2484 & ((bitset_word_t) 1 << dfa->nodes[node].opr.idx)))
2486 err = match_ctx_add_subtop (mctx, node, str_idx);
2487 if (BE (err != REG_NOERROR, 0))
2495 /* Return the next state to which the current state STATE will transit by
2496 accepting the current input byte. */
2498 static re_dfastate_t *
2499 transit_state_sb (reg_errcode_t *err, re_match_context_t *mctx,
2500 re_dfastate_t *state)
2502 const re_dfa_t *const dfa = mctx->dfa;
2503 re_node_set next_nodes;
2504 re_dfastate_t *next_state;
2505 Idx node_cnt, cur_str_idx = re_string_cur_idx (&mctx->input);
2506 unsigned int context;
2508 *err = re_node_set_alloc (&next_nodes, state->nodes.nelem + 1);
2509 if (BE (*err != REG_NOERROR, 0))
2511 for (node_cnt = 0; node_cnt < state->nodes.nelem; ++node_cnt)
2513 Idx cur_node = state->nodes.elems[node_cnt];
2514 if (check_node_accept (mctx, dfa->nodes + cur_node, cur_str_idx))
2516 *err = re_node_set_merge (&next_nodes,
2517 dfa->eclosures + dfa->nexts[cur_node]);
2518 if (BE (*err != REG_NOERROR, 0))
2520 re_node_set_free (&next_nodes);
2525 context = re_string_context_at (&mctx->input, cur_str_idx, mctx->eflags);
2526 next_state = re_acquire_state_context (err, dfa, &next_nodes, context);
2527 /* We don't need to check errors here, since the return value of
2528 this function is next_state and ERR is already set. */
2530 re_node_set_free (&next_nodes);
2531 re_string_skip_bytes (&mctx->input, 1);
2536 #ifdef RE_ENABLE_I18N
2537 static reg_errcode_t
2539 transit_state_mb (re_match_context_t *mctx, re_dfastate_t *pstate)
2541 const re_dfa_t *const dfa = mctx->dfa;
2545 for (i = 0; i < pstate->nodes.nelem; ++i)
2547 re_node_set dest_nodes, *new_nodes;
2548 Idx cur_node_idx = pstate->nodes.elems[i];
2551 unsigned int context;
2552 re_dfastate_t *dest_state;
2554 if (!dfa->nodes[cur_node_idx].accept_mb)
2557 if (dfa->nodes[cur_node_idx].constraint)
2559 context = re_string_context_at (&mctx->input,
2560 re_string_cur_idx (&mctx->input),
2562 if (NOT_SATISFY_NEXT_CONSTRAINT (dfa->nodes[cur_node_idx].constraint,
2567 /* How many bytes the node can accept? */
2568 naccepted = check_node_accept_bytes (dfa, cur_node_idx, &mctx->input,
2569 re_string_cur_idx (&mctx->input));
2573 /* The node can accepts `naccepted' bytes. */
2574 dest_idx = re_string_cur_idx (&mctx->input) + naccepted;
2575 mctx->max_mb_elem_len = ((mctx->max_mb_elem_len < naccepted) ? naccepted
2576 : mctx->max_mb_elem_len);
2577 err = clean_state_log_if_needed (mctx, dest_idx);
2578 if (BE (err != REG_NOERROR, 0))
2581 assert (dfa->nexts[cur_node_idx] != REG_MISSING);
2583 new_nodes = dfa->eclosures + dfa->nexts[cur_node_idx];
2585 dest_state = mctx->state_log[dest_idx];
2586 if (dest_state == NULL)
2587 dest_nodes = *new_nodes;
2590 err = re_node_set_init_union (&dest_nodes,
2591 dest_state->entrance_nodes, new_nodes);
2592 if (BE (err != REG_NOERROR, 0))
2595 context = re_string_context_at (&mctx->input, dest_idx - 1,
2597 mctx->state_log[dest_idx]
2598 = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2599 if (dest_state != NULL)
2600 re_node_set_free (&dest_nodes);
2601 if (BE (mctx->state_log[dest_idx] == NULL && err != REG_NOERROR, 0))
2606 #endif /* RE_ENABLE_I18N */
2608 static reg_errcode_t
2610 transit_state_bkref (re_match_context_t *mctx, const re_node_set *nodes)
2612 const re_dfa_t *const dfa = mctx->dfa;
2615 Idx cur_str_idx = re_string_cur_idx (&mctx->input);
2617 for (i = 0; i < nodes->nelem; ++i)
2619 Idx dest_str_idx, prev_nelem, bkc_idx;
2620 Idx node_idx = nodes->elems[i];
2621 unsigned int context;
2622 const re_token_t *node = dfa->nodes + node_idx;
2623 re_node_set *new_dest_nodes;
2625 /* Check whether `node' is a backreference or not. */
2626 if (node->type != OP_BACK_REF)
2629 if (node->constraint)
2631 context = re_string_context_at (&mctx->input, cur_str_idx,
2633 if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
2637 /* `node' is a backreference.
2638 Check the substring which the substring matched. */
2639 bkc_idx = mctx->nbkref_ents;
2640 err = get_subexp (mctx, node_idx, cur_str_idx);
2641 if (BE (err != REG_NOERROR, 0))
2644 /* And add the epsilon closures (which is `new_dest_nodes') of
2645 the backreference to appropriate state_log. */
2647 assert (dfa->nexts[node_idx] != REG_MISSING);
2649 for (; bkc_idx < mctx->nbkref_ents; ++bkc_idx)
2652 re_dfastate_t *dest_state;
2653 struct re_backref_cache_entry *bkref_ent;
2654 bkref_ent = mctx->bkref_ents + bkc_idx;
2655 if (bkref_ent->node != node_idx || bkref_ent->str_idx != cur_str_idx)
2657 subexp_len = bkref_ent->subexp_to - bkref_ent->subexp_from;
2658 new_dest_nodes = (subexp_len == 0
2659 ? dfa->eclosures + dfa->edests[node_idx].elems[0]
2660 : dfa->eclosures + dfa->nexts[node_idx]);
2661 dest_str_idx = (cur_str_idx + bkref_ent->subexp_to
2662 - bkref_ent->subexp_from);
2663 context = re_string_context_at (&mctx->input, dest_str_idx - 1,
2665 dest_state = mctx->state_log[dest_str_idx];
2666 prev_nelem = ((mctx->state_log[cur_str_idx] == NULL) ? 0
2667 : mctx->state_log[cur_str_idx]->nodes.nelem);
2668 /* Add `new_dest_node' to state_log. */
2669 if (dest_state == NULL)
2671 mctx->state_log[dest_str_idx]
2672 = re_acquire_state_context (&err, dfa, new_dest_nodes,
2674 if (BE (mctx->state_log[dest_str_idx] == NULL
2675 && err != REG_NOERROR, 0))
2680 re_node_set dest_nodes;
2681 err = re_node_set_init_union (&dest_nodes,
2682 dest_state->entrance_nodes,
2684 if (BE (err != REG_NOERROR, 0))
2686 re_node_set_free (&dest_nodes);
2689 mctx->state_log[dest_str_idx]
2690 = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2691 re_node_set_free (&dest_nodes);
2692 if (BE (mctx->state_log[dest_str_idx] == NULL
2693 && err != REG_NOERROR, 0))
2696 /* We need to check recursively if the backreference can epsilon
2699 && mctx->state_log[cur_str_idx]->nodes.nelem > prev_nelem)
2701 err = check_subexp_matching_top (mctx, new_dest_nodes,
2703 if (BE (err != REG_NOERROR, 0))
2705 err = transit_state_bkref (mctx, new_dest_nodes);
2706 if (BE (err != REG_NOERROR, 0))
2716 /* Enumerate all the candidates which the backreference BKREF_NODE can match
2717 at BKREF_STR_IDX, and register them by match_ctx_add_entry().
2718 Note that we might collect inappropriate candidates here.
2719 However, the cost of checking them strictly here is too high, then we
2720 delay these checking for prune_impossible_nodes(). */
2722 static reg_errcode_t
2723 internal_function __attribute_warn_unused_result__
2724 get_subexp (re_match_context_t *mctx, Idx bkref_node, Idx bkref_str_idx)
2726 const re_dfa_t *const dfa = mctx->dfa;
2727 Idx subexp_num, sub_top_idx;
2728 const char *buf = (const char *) re_string_get_buffer (&mctx->input);
2729 /* Return if we have already checked BKREF_NODE at BKREF_STR_IDX. */
2730 Idx cache_idx = search_cur_bkref_entry (mctx, bkref_str_idx);
2731 if (cache_idx != REG_MISSING)
2733 const struct re_backref_cache_entry *entry
2734 = mctx->bkref_ents + cache_idx;
2736 if (entry->node == bkref_node)
2737 return REG_NOERROR; /* We already checked it. */
2738 while (entry++->more);
2741 subexp_num = dfa->nodes[bkref_node].opr.idx;
2743 /* For each sub expression */
2744 for (sub_top_idx = 0; sub_top_idx < mctx->nsub_tops; ++sub_top_idx)
2747 re_sub_match_top_t *sub_top = mctx->sub_tops[sub_top_idx];
2748 re_sub_match_last_t *sub_last;
2749 Idx sub_last_idx, sl_str, bkref_str_off;
2751 if (dfa->nodes[sub_top->node].opr.idx != subexp_num)
2752 continue; /* It isn't related. */
2754 sl_str = sub_top->str_idx;
2755 bkref_str_off = bkref_str_idx;
2756 /* At first, check the last node of sub expressions we already
2758 for (sub_last_idx = 0; sub_last_idx < sub_top->nlasts; ++sub_last_idx)
2760 regoff_t sl_str_diff;
2761 sub_last = sub_top->lasts[sub_last_idx];
2762 sl_str_diff = sub_last->str_idx - sl_str;
2763 /* The matched string by the sub expression match with the substring
2764 at the back reference? */
2765 if (sl_str_diff > 0)
2767 if (BE (bkref_str_off + sl_str_diff > mctx->input.valid_len, 0))
2769 /* Not enough chars for a successful match. */
2770 if (bkref_str_off + sl_str_diff > mctx->input.len)
2773 err = clean_state_log_if_needed (mctx,
2776 if (BE (err != REG_NOERROR, 0))
2778 buf = (const char *) re_string_get_buffer (&mctx->input);
2780 if (memcmp (buf + bkref_str_off, buf + sl_str, sl_str_diff) != 0)
2781 /* We don't need to search this sub expression any more. */
2784 bkref_str_off += sl_str_diff;
2785 sl_str += sl_str_diff;
2786 err = get_subexp_sub (mctx, sub_top, sub_last, bkref_node,
2789 /* Reload buf, since the preceding call might have reallocated
2791 buf = (const char *) re_string_get_buffer (&mctx->input);
2793 if (err == REG_NOMATCH)
2795 if (BE (err != REG_NOERROR, 0))
2799 if (sub_last_idx < sub_top->nlasts)
2801 if (sub_last_idx > 0)
2803 /* Then, search for the other last nodes of the sub expression. */
2804 for (; sl_str <= bkref_str_idx; ++sl_str)
2807 regoff_t sl_str_off;
2808 const re_node_set *nodes;
2809 sl_str_off = sl_str - sub_top->str_idx;
2810 /* The matched string by the sub expression match with the substring
2811 at the back reference? */
2814 if (BE (bkref_str_off >= mctx->input.valid_len, 0))
2816 /* If we are at the end of the input, we cannot match. */
2817 if (bkref_str_off >= mctx->input.len)
2820 err = extend_buffers (mctx);
2821 if (BE (err != REG_NOERROR, 0))
2824 buf = (const char *) re_string_get_buffer (&mctx->input);
2826 if (buf [bkref_str_off++] != buf[sl_str - 1])
2827 break; /* We don't need to search this sub expression
2830 if (mctx->state_log[sl_str] == NULL)
2832 /* Does this state have a ')' of the sub expression? */
2833 nodes = &mctx->state_log[sl_str]->nodes;
2834 cls_node = find_subexp_node (dfa, nodes, subexp_num,
2836 if (cls_node == REG_MISSING)
2838 if (sub_top->path == NULL)
2840 sub_top->path = calloc (sizeof (state_array_t),
2841 sl_str - sub_top->str_idx + 1);
2842 if (sub_top->path == NULL)
2845 /* Can the OP_OPEN_SUBEXP node arrive the OP_CLOSE_SUBEXP node
2846 in the current context? */
2847 err = check_arrival (mctx, sub_top->path, sub_top->node,
2848 sub_top->str_idx, cls_node, sl_str,
2850 if (err == REG_NOMATCH)
2852 if (BE (err != REG_NOERROR, 0))
2854 sub_last = match_ctx_add_sublast (sub_top, cls_node, sl_str);
2855 if (BE (sub_last == NULL, 0))
2857 err = get_subexp_sub (mctx, sub_top, sub_last, bkref_node,
2859 if (err == REG_NOMATCH)
2866 /* Helper functions for get_subexp(). */
2868 /* Check SUB_LAST can arrive to the back reference BKREF_NODE at BKREF_STR.
2869 If it can arrive, register the sub expression expressed with SUB_TOP
2872 static reg_errcode_t
2874 get_subexp_sub (re_match_context_t *mctx, const re_sub_match_top_t *sub_top,
2875 re_sub_match_last_t *sub_last, Idx bkref_node, Idx bkref_str)
2879 /* Can the subexpression arrive the back reference? */
2880 err = check_arrival (mctx, &sub_last->path, sub_last->node,
2881 sub_last->str_idx, bkref_node, bkref_str,
2883 if (err != REG_NOERROR)
2885 err = match_ctx_add_entry (mctx, bkref_node, bkref_str, sub_top->str_idx,
2887 if (BE (err != REG_NOERROR, 0))
2889 to_idx = bkref_str + sub_last->str_idx - sub_top->str_idx;
2890 return clean_state_log_if_needed (mctx, to_idx);
2893 /* Find the first node which is '(' or ')' and whose index is SUBEXP_IDX.
2894 Search '(' if FL_OPEN, or search ')' otherwise.
2895 TODO: This function isn't efficient...
2896 Because there might be more than one nodes whose types are
2897 OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
2903 find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
2904 Idx subexp_idx, int type)
2907 for (cls_idx = 0; cls_idx < nodes->nelem; ++cls_idx)
2909 Idx cls_node = nodes->elems[cls_idx];
2910 const re_token_t *node = dfa->nodes + cls_node;
2911 if (node->type == type
2912 && node->opr.idx == subexp_idx)
2918 /* Check whether the node TOP_NODE at TOP_STR can arrive to the node
2919 LAST_NODE at LAST_STR. We record the path onto PATH since it will be
2921 Return REG_NOERROR if it can arrive, or REG_NOMATCH otherwise. */
2923 static reg_errcode_t
2924 internal_function __attribute_warn_unused_result__
2925 check_arrival (re_match_context_t *mctx, state_array_t *path, Idx top_node,
2926 Idx top_str, Idx last_node, Idx last_str, int type)
2928 const re_dfa_t *const dfa = mctx->dfa;
2929 reg_errcode_t err = REG_NOERROR;
2930 Idx subexp_num, backup_cur_idx, str_idx, null_cnt;
2931 re_dfastate_t *cur_state = NULL;
2932 re_node_set *cur_nodes, next_nodes;
2933 re_dfastate_t **backup_state_log;
2934 unsigned int context;
2936 subexp_num = dfa->nodes[top_node].opr.idx;
2937 /* Extend the buffer if we need. */
2938 if (BE (path->alloc < last_str + mctx->max_mb_elem_len + 1, 0))
2940 re_dfastate_t **new_array;
2941 Idx old_alloc = path->alloc;
2942 Idx new_alloc = old_alloc + last_str + mctx->max_mb_elem_len + 1;
2943 if (BE (new_alloc < old_alloc, 0)
2944 || BE (SIZE_MAX / sizeof (re_dfastate_t *) < new_alloc, 0))
2946 new_array = re_realloc (path->array, re_dfastate_t *, new_alloc);
2947 if (BE (new_array == NULL, 0))
2949 path->array = new_array;
2950 path->alloc = new_alloc;
2951 memset (new_array + old_alloc, '\0',
2952 sizeof (re_dfastate_t *) * (path->alloc - old_alloc));
2955 str_idx = path->next_idx ? path->next_idx : top_str;
2957 /* Temporary modify MCTX. */
2958 backup_state_log = mctx->state_log;
2959 backup_cur_idx = mctx->input.cur_idx;
2960 mctx->state_log = path->array;
2961 mctx->input.cur_idx = str_idx;
2963 /* Setup initial node set. */
2964 context = re_string_context_at (&mctx->input, str_idx - 1, mctx->eflags);
2965 if (str_idx == top_str)
2967 err = re_node_set_init_1 (&next_nodes, top_node);
2968 if (BE (err != REG_NOERROR, 0))
2970 err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
2971 if (BE (err != REG_NOERROR, 0))
2973 re_node_set_free (&next_nodes);
2979 cur_state = mctx->state_log[str_idx];
2980 if (cur_state && cur_state->has_backref)
2982 err = re_node_set_init_copy (&next_nodes, &cur_state->nodes);
2983 if (BE (err != REG_NOERROR, 0))
2987 re_node_set_init_empty (&next_nodes);
2989 if (str_idx == top_str || (cur_state && cur_state->has_backref))
2991 if (next_nodes.nelem)
2993 err = expand_bkref_cache (mctx, &next_nodes, str_idx,
2995 if (BE (err != REG_NOERROR, 0))
2997 re_node_set_free (&next_nodes);
3001 cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
3002 if (BE (cur_state == NULL && err != REG_NOERROR, 0))
3004 re_node_set_free (&next_nodes);
3007 mctx->state_log[str_idx] = cur_state;
3010 for (null_cnt = 0; str_idx < last_str && null_cnt <= mctx->max_mb_elem_len;)
3012 re_node_set_empty (&next_nodes);
3013 if (mctx->state_log[str_idx + 1])
3015 err = re_node_set_merge (&next_nodes,
3016 &mctx->state_log[str_idx + 1]->nodes);
3017 if (BE (err != REG_NOERROR, 0))
3019 re_node_set_free (&next_nodes);
3025 err = check_arrival_add_next_nodes (mctx, str_idx,
3026 &cur_state->non_eps_nodes,
3028 if (BE (err != REG_NOERROR, 0))
3030 re_node_set_free (&next_nodes);
3035 if (next_nodes.nelem)
3037 err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
3038 if (BE (err != REG_NOERROR, 0))
3040 re_node_set_free (&next_nodes);
3043 err = expand_bkref_cache (mctx, &next_nodes, str_idx,
3045 if (BE (err != REG_NOERROR, 0))
3047 re_node_set_free (&next_nodes);
3051 context = re_string_context_at (&mctx->input, str_idx - 1, mctx->eflags);
3052 cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
3053 if (BE (cur_state == NULL && err != REG_NOERROR, 0))
3055 re_node_set_free (&next_nodes);
3058 mctx->state_log[str_idx] = cur_state;
3059 null_cnt = cur_state == NULL ? null_cnt + 1 : 0;
3061 re_node_set_free (&next_nodes);
3062 cur_nodes = (mctx->state_log[last_str] == NULL ? NULL
3063 : &mctx->state_log[last_str]->nodes);
3064 path->next_idx = str_idx;
3067 mctx->state_log = backup_state_log;
3068 mctx->input.cur_idx = backup_cur_idx;
3070 /* Then check the current node set has the node LAST_NODE. */
3071 if (cur_nodes != NULL && re_node_set_contains (cur_nodes, last_node))
3077 /* Helper functions for check_arrival. */
3079 /* Calculate the destination nodes of CUR_NODES at STR_IDX, and append them
3081 TODO: This function is similar to the functions transit_state*(),
3082 however this function has many additional works.
3083 Can't we unify them? */
3085 static reg_errcode_t
3086 internal_function __attribute_warn_unused_result__
3087 check_arrival_add_next_nodes (re_match_context_t *mctx, Idx str_idx,
3088 re_node_set *cur_nodes, re_node_set *next_nodes)
3090 const re_dfa_t *const dfa = mctx->dfa;
3093 #ifdef RE_ENABLE_I18N
3094 reg_errcode_t err = REG_NOERROR;
3096 re_node_set union_set;
3097 re_node_set_init_empty (&union_set);
3098 for (cur_idx = 0; cur_idx < cur_nodes->nelem; ++cur_idx)
3101 Idx cur_node = cur_nodes->elems[cur_idx];
3103 re_token_type_t type = dfa->nodes[cur_node].type;
3104 assert (!IS_EPSILON_NODE (type));
3106 #ifdef RE_ENABLE_I18N
3107 /* If the node may accept `multi byte'. */
3108 if (dfa->nodes[cur_node].accept_mb)
3110 naccepted = check_node_accept_bytes (dfa, cur_node, &mctx->input,
3114 re_dfastate_t *dest_state;
3115 Idx next_node = dfa->nexts[cur_node];
3116 Idx next_idx = str_idx + naccepted;
3117 dest_state = mctx->state_log[next_idx];
3118 re_node_set_empty (&union_set);
3121 err = re_node_set_merge (&union_set, &dest_state->nodes);
3122 if (BE (err != REG_NOERROR, 0))
3124 re_node_set_free (&union_set);
3128 ok = re_node_set_insert (&union_set, next_node);
3131 re_node_set_free (&union_set);
3134 mctx->state_log[next_idx] = re_acquire_state (&err, dfa,
3136 if (BE (mctx->state_log[next_idx] == NULL
3137 && err != REG_NOERROR, 0))
3139 re_node_set_free (&union_set);
3144 #endif /* RE_ENABLE_I18N */
3146 || check_node_accept (mctx, dfa->nodes + cur_node, str_idx))
3148 ok = re_node_set_insert (next_nodes, dfa->nexts[cur_node]);
3151 re_node_set_free (&union_set);
3156 re_node_set_free (&union_set);
3160 /* For all the nodes in CUR_NODES, add the epsilon closures of them to
3161 CUR_NODES, however exclude the nodes which are:
3162 - inside the sub expression whose number is EX_SUBEXP, if FL_OPEN.
3163 - out of the sub expression whose number is EX_SUBEXP, if !FL_OPEN.
3166 static reg_errcode_t
3168 check_arrival_expand_ecl (const re_dfa_t *dfa, re_node_set *cur_nodes,
3169 Idx ex_subexp, int type)
3172 Idx idx, outside_node;
3173 re_node_set new_nodes;
3175 assert (cur_nodes->nelem);
3177 err = re_node_set_alloc (&new_nodes, cur_nodes->nelem);
3178 if (BE (err != REG_NOERROR, 0))
3180 /* Create a new node set NEW_NODES with the nodes which are epsilon
3181 closures of the node in CUR_NODES. */
3183 for (idx = 0; idx < cur_nodes->nelem; ++idx)
3185 Idx cur_node = cur_nodes->elems[idx];
3186 const re_node_set *eclosure = dfa->eclosures + cur_node;
3187 outside_node = find_subexp_node (dfa, eclosure, ex_subexp, type);
3188 if (outside_node == REG_MISSING)
3190 /* There are no problematic nodes, just merge them. */
3191 err = re_node_set_merge (&new_nodes, eclosure);
3192 if (BE (err != REG_NOERROR, 0))
3194 re_node_set_free (&new_nodes);
3200 /* There are problematic nodes, re-calculate incrementally. */
3201 err = check_arrival_expand_ecl_sub (dfa, &new_nodes, cur_node,
3203 if (BE (err != REG_NOERROR, 0))
3205 re_node_set_free (&new_nodes);
3210 re_node_set_free (cur_nodes);
3211 *cur_nodes = new_nodes;
3215 /* Helper function for check_arrival_expand_ecl.
3216 Check incrementally the epsilon closure of TARGET, and if it isn't
3217 problematic append it to DST_NODES. */
3219 static reg_errcode_t
3220 internal_function __attribute_warn_unused_result__
3221 check_arrival_expand_ecl_sub (const re_dfa_t *dfa, re_node_set *dst_nodes,
3222 Idx target, Idx ex_subexp, int type)
3225 for (cur_node = target; !re_node_set_contains (dst_nodes, cur_node);)
3229 if (dfa->nodes[cur_node].type == type
3230 && dfa->nodes[cur_node].opr.idx == ex_subexp)
3232 if (type == OP_CLOSE_SUBEXP)
3234 ok = re_node_set_insert (dst_nodes, cur_node);
3240 ok = re_node_set_insert (dst_nodes, cur_node);
3243 if (dfa->edests[cur_node].nelem == 0)
3245 if (dfa->edests[cur_node].nelem == 2)
3248 err = check_arrival_expand_ecl_sub (dfa, dst_nodes,
3249 dfa->edests[cur_node].elems[1],
3251 if (BE (err != REG_NOERROR, 0))
3254 cur_node = dfa->edests[cur_node].elems[0];
3260 /* For all the back references in the current state, calculate the
3261 destination of the back references by the appropriate entry
3262 in MCTX->BKREF_ENTS. */
3264 static reg_errcode_t
3265 internal_function __attribute_warn_unused_result__
3266 expand_bkref_cache (re_match_context_t *mctx, re_node_set *cur_nodes,
3267 Idx cur_str, Idx subexp_num, int type)
3269 const re_dfa_t *const dfa = mctx->dfa;
3271 Idx cache_idx_start = search_cur_bkref_entry (mctx, cur_str);
3272 struct re_backref_cache_entry *ent;
3274 if (cache_idx_start == REG_MISSING)
3278 ent = mctx->bkref_ents + cache_idx_start;
3281 Idx to_idx, next_node;
3283 /* Is this entry ENT is appropriate? */
3284 if (!re_node_set_contains (cur_nodes, ent->node))
3287 to_idx = cur_str + ent->subexp_to - ent->subexp_from;
3288 /* Calculate the destination of the back reference, and append it
3289 to MCTX->STATE_LOG. */
3290 if (to_idx == cur_str)
3292 /* The backreference did epsilon transit, we must re-check all the
3293 node in the current state. */
3294 re_node_set new_dests;
3295 reg_errcode_t err2, err3;
3296 next_node = dfa->edests[ent->node].elems[0];
3297 if (re_node_set_contains (cur_nodes, next_node))
3299 err = re_node_set_init_1 (&new_dests, next_node);
3300 err2 = check_arrival_expand_ecl (dfa, &new_dests, subexp_num, type);
3301 err3 = re_node_set_merge (cur_nodes, &new_dests);
3302 re_node_set_free (&new_dests);
3303 if (BE (err != REG_NOERROR || err2 != REG_NOERROR
3304 || err3 != REG_NOERROR, 0))
3306 err = (err != REG_NOERROR ? err
3307 : (err2 != REG_NOERROR ? err2 : err3));
3310 /* TODO: It is still inefficient... */
3315 re_node_set union_set;
3316 next_node = dfa->nexts[ent->node];
3317 if (mctx->state_log[to_idx])
3320 if (re_node_set_contains (&mctx->state_log[to_idx]->nodes,
3323 err = re_node_set_init_copy (&union_set,
3324 &mctx->state_log[to_idx]->nodes);
3325 ok = re_node_set_insert (&union_set, next_node);
3326 if (BE (err != REG_NOERROR || ! ok, 0))
3328 re_node_set_free (&union_set);
3329 err = err != REG_NOERROR ? err : REG_ESPACE;
3335 err = re_node_set_init_1 (&union_set, next_node);
3336 if (BE (err != REG_NOERROR, 0))
3339 mctx->state_log[to_idx] = re_acquire_state (&err, dfa, &union_set);
3340 re_node_set_free (&union_set);
3341 if (BE (mctx->state_log[to_idx] == NULL
3342 && err != REG_NOERROR, 0))
3346 while (ent++->more);
3350 /* Build transition table for the state.
3351 Return true if successful. */
3355 build_trtable (const re_dfa_t *dfa, re_dfastate_t *state)
3360 bool need_word_trtable = false;
3361 bitset_word_t elem, mask;
3362 bool dests_node_malloced = false;
3363 bool dest_states_malloced = false;
3364 Idx ndests; /* Number of the destination states from `state'. */
3365 re_dfastate_t **trtable;
3366 re_dfastate_t **dest_states = NULL, **dest_states_word, **dest_states_nl;
3367 re_node_set follows, *dests_node;
3369 bitset_t acceptable;
3373 re_node_set dests_node[SBC_MAX];
3374 bitset_t dests_ch[SBC_MAX];
3377 /* We build DFA states which corresponds to the destination nodes
3378 from `state'. `dests_node[i]' represents the nodes which i-th
3379 destination state contains, and `dests_ch[i]' represents the
3380 characters which i-th destination state accepts. */
3381 if (__libc_use_alloca (sizeof (struct dests_alloc)))
3382 dests_alloc = (struct dests_alloc *) alloca (sizeof (struct dests_alloc));
3385 dests_alloc = re_malloc (struct dests_alloc, 1);
3386 if (BE (dests_alloc == NULL, 0))
3388 dests_node_malloced = true;
3390 dests_node = dests_alloc->dests_node;
3391 dests_ch = dests_alloc->dests_ch;
3393 /* Initialize transiton table. */
3394 state->word_trtable = state->trtable = NULL;
3396 /* At first, group all nodes belonging to `state' into several
3398 ndests = group_nodes_into_DFAstates (dfa, state, dests_node, dests_ch);
3399 if (BE (! REG_VALID_NONZERO_INDEX (ndests), 0))
3401 if (dests_node_malloced)
3405 state->trtable = (re_dfastate_t **)
3406 calloc (sizeof (re_dfastate_t *), SBC_MAX);
3412 err = re_node_set_alloc (&follows, ndests + 1);
3413 if (BE (err != REG_NOERROR, 0))
3416 /* Avoid arithmetic overflow in size calculation. */
3417 if (BE ((((SIZE_MAX - (sizeof (re_node_set) + sizeof (bitset_t)) * SBC_MAX)
3418 / (3 * sizeof (re_dfastate_t *)))
3423 if (__libc_use_alloca ((sizeof (re_node_set) + sizeof (bitset_t)) * SBC_MAX
3424 + ndests * 3 * sizeof (re_dfastate_t *)))
3425 dest_states = (re_dfastate_t **)
3426 alloca (ndests * 3 * sizeof (re_dfastate_t *));
3429 dest_states = (re_dfastate_t **)
3430 malloc (ndests * 3 * sizeof (re_dfastate_t *));
3431 if (BE (dest_states == NULL, 0))
3434 if (dest_states_malloced)
3436 re_node_set_free (&follows);
3437 for (i = 0; i < ndests; ++i)
3438 re_node_set_free (dests_node + i);
3439 if (dests_node_malloced)
3443 dest_states_malloced = true;
3445 dest_states_word = dest_states + ndests;
3446 dest_states_nl = dest_states_word + ndests;
3447 bitset_empty (acceptable);
3449 /* Then build the states for all destinations. */
3450 for (i = 0; i < ndests; ++i)
3453 re_node_set_empty (&follows);
3454 /* Merge the follows of this destination states. */
3455 for (j = 0; j < dests_node[i].nelem; ++j)
3457 next_node = dfa->nexts[dests_node[i].elems[j]];
3458 if (next_node != REG_MISSING)
3460 err = re_node_set_merge (&follows, dfa->eclosures + next_node);
3461 if (BE (err != REG_NOERROR, 0))
3465 dest_states[i] = re_acquire_state_context (&err, dfa, &follows, 0);
3466 if (BE (dest_states[i] == NULL && err != REG_NOERROR, 0))
3468 /* If the new state has context constraint,
3469 build appropriate states for these contexts. */
3470 if (dest_states[i]->has_constraint)
3472 dest_states_word[i] = re_acquire_state_context (&err, dfa, &follows,
3474 if (BE (dest_states_word[i] == NULL && err != REG_NOERROR, 0))
3477 if (dest_states[i] != dest_states_word[i] && dfa->mb_cur_max > 1)
3478 need_word_trtable = true;
3480 dest_states_nl[i] = re_acquire_state_context (&err, dfa, &follows,
3482 if (BE (dest_states_nl[i] == NULL && err != REG_NOERROR, 0))
3487 dest_states_word[i] = dest_states[i];
3488 dest_states_nl[i] = dest_states[i];
3490 bitset_merge (acceptable, dests_ch[i]);
3493 if (!BE (need_word_trtable, 0))
3495 /* We don't care about whether the following character is a word
3496 character, or we are in a single-byte character set so we can
3497 discern by looking at the character code: allocate a
3498 256-entry transition table. */
3499 trtable = state->trtable =
3500 (re_dfastate_t **) calloc (sizeof (re_dfastate_t *), SBC_MAX);
3501 if (BE (trtable == NULL, 0))
3504 /* For all characters ch...: */
3505 for (i = 0; i < BITSET_WORDS; ++i)
3506 for (ch = i * BITSET_WORD_BITS, elem = acceptable[i], mask = 1;
3508 mask <<= 1, elem >>= 1, ++ch)
3509 if (BE (elem & 1, 0))
3511 /* There must be exactly one destination which accepts
3512 character ch. See group_nodes_into_DFAstates. */
3513 for (j = 0; (dests_ch[j][i] & mask) == 0; ++j)
3516 /* j-th destination accepts the word character ch. */
3517 if (dfa->word_char[i] & mask)
3518 trtable[ch] = dest_states_word[j];
3520 trtable[ch] = dest_states[j];
3525 /* We care about whether the following character is a word
3526 character, and we are in a multi-byte character set: discern
3527 by looking at the character code: build two 256-entry
3528 transition tables, one starting at trtable[0] and one
3529 starting at trtable[SBC_MAX]. */
3530 trtable = state->word_trtable =
3531 (re_dfastate_t **) calloc (sizeof (re_dfastate_t *), 2 * SBC_MAX);
3532 if (BE (trtable == NULL, 0))
3535 /* For all characters ch...: */
3536 for (i = 0; i < BITSET_WORDS; ++i)
3537 for (ch = i * BITSET_WORD_BITS, elem = acceptable[i], mask = 1;
3539 mask <<= 1, elem >>= 1, ++ch)
3540 if (BE (elem & 1, 0))
3542 /* There must be exactly one destination which accepts
3543 character ch. See group_nodes_into_DFAstates. */
3544 for (j = 0; (dests_ch[j][i] & mask) == 0; ++j)
3547 /* j-th destination accepts the word character ch. */
3548 trtable[ch] = dest_states[j];
3549 trtable[ch + SBC_MAX] = dest_states_word[j];
3554 if (bitset_contain (acceptable, NEWLINE_CHAR))
3556 /* The current state accepts newline character. */
3557 for (j = 0; j < ndests; ++j)
3558 if (bitset_contain (dests_ch[j], NEWLINE_CHAR))
3560 /* k-th destination accepts newline character. */
3561 trtable[NEWLINE_CHAR] = dest_states_nl[j];
3562 if (need_word_trtable)
3563 trtable[NEWLINE_CHAR + SBC_MAX] = dest_states_nl[j];
3564 /* There must be only one destination which accepts
3565 newline. See group_nodes_into_DFAstates. */
3570 if (dest_states_malloced)
3573 re_node_set_free (&follows);
3574 for (i = 0; i < ndests; ++i)
3575 re_node_set_free (dests_node + i);
3577 if (dests_node_malloced)
3583 /* Group all nodes belonging to STATE into several destinations.
3584 Then for all destinations, set the nodes belonging to the destination
3585 to DESTS_NODE[i] and set the characters accepted by the destination
3586 to DEST_CH[i]. This function return the number of destinations. */
3590 group_nodes_into_DFAstates (const re_dfa_t *dfa, const re_dfastate_t *state,
3591 re_node_set *dests_node, bitset_t *dests_ch)
3596 Idx ndests; /* Number of the destinations from `state'. */
3597 bitset_t accepts; /* Characters a node can accept. */
3598 const re_node_set *cur_nodes = &state->nodes;
3599 bitset_empty (accepts);
3602 /* For all the nodes belonging to `state', */
3603 for (i = 0; i < cur_nodes->nelem; ++i)
3605 re_token_t *node = &dfa->nodes[cur_nodes->elems[i]];
3606 re_token_type_t type = node->type;
3607 unsigned int constraint = node->constraint;
3609 /* Enumerate all single byte character this node can accept. */
3610 if (type == CHARACTER)
3611 bitset_set (accepts, node->opr.c);
3612 else if (type == SIMPLE_BRACKET)
3614 bitset_merge (accepts, node->opr.sbcset);
3616 else if (type == OP_PERIOD)
3618 #ifdef RE_ENABLE_I18N
3619 if (dfa->mb_cur_max > 1)
3620 bitset_merge (accepts, dfa->sb_char);
3623 bitset_set_all (accepts);
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');
3629 #ifdef RE_ENABLE_I18N
3630 else if (type == OP_UTF8_PERIOD)
3632 if (ASCII_CHARS % BITSET_WORD_BITS == 0)
3633 memset (accepts, -1, ASCII_CHARS / CHAR_BIT);
3635 bitset_merge (accepts, utf8_sb_map);
3636 if (!(dfa->syntax & RE_DOT_NEWLINE))
3637 bitset_clear (accepts, '\n');
3638 if (dfa->syntax & RE_DOT_NOT_NULL)
3639 bitset_clear (accepts, '\0');
3645 /* Check the `accepts' and sift the characters which are not
3646 match it the context. */
3649 if (constraint & NEXT_NEWLINE_CONSTRAINT)
3651 bool accepts_newline = bitset_contain (accepts, NEWLINE_CHAR);
3652 bitset_empty (accepts);
3653 if (accepts_newline)
3654 bitset_set (accepts, NEWLINE_CHAR);
3658 if (constraint & NEXT_ENDBUF_CONSTRAINT)
3660 bitset_empty (accepts);
3664 if (constraint & NEXT_WORD_CONSTRAINT)
3666 bitset_word_t any_set = 0;
3667 if (type == CHARACTER && !node->word_char)
3669 bitset_empty (accepts);
3672 #ifdef RE_ENABLE_I18N
3673 if (dfa->mb_cur_max > 1)
3674 for (j = 0; j < BITSET_WORDS; ++j)
3675 any_set |= (accepts[j] &= (dfa->word_char[j] | ~dfa->sb_char[j]));
3678 for (j = 0; j < BITSET_WORDS; ++j)
3679 any_set |= (accepts[j] &= dfa->word_char[j]);
3683 if (constraint & NEXT_NOTWORD_CONSTRAINT)
3685 bitset_word_t any_set = 0;
3686 if (type == CHARACTER && node->word_char)
3688 bitset_empty (accepts);
3691 #ifdef RE_ENABLE_I18N
3692 if (dfa->mb_cur_max > 1)
3693 for (j = 0; j < BITSET_WORDS; ++j)
3694 any_set |= (accepts[j] &= ~(dfa->word_char[j] & dfa->sb_char[j]));
3697 for (j = 0; j < BITSET_WORDS; ++j)
3698 any_set |= (accepts[j] &= ~dfa->word_char[j]);
3704 /* Then divide `accepts' into DFA states, or create a new
3705 state. Above, we make sure that accepts is not empty. */
3706 for (j = 0; j < ndests; ++j)
3708 bitset_t intersec; /* Intersection sets, see below. */
3710 /* Flags, see below. */
3711 bitset_word_t has_intersec, not_subset, not_consumed;
3713 /* Optimization, skip if this state doesn't accept the character. */
3714 if (type == CHARACTER && !bitset_contain (dests_ch[j], node->opr.c))
3717 /* Enumerate the intersection set of this state and `accepts'. */
3719 for (k = 0; k < BITSET_WORDS; ++k)
3720 has_intersec |= intersec[k] = accepts[k] & dests_ch[j][k];
3721 /* And skip if the intersection set is empty. */
3725 /* Then check if this state is a subset of `accepts'. */
3726 not_subset = not_consumed = 0;
3727 for (k = 0; k < BITSET_WORDS; ++k)
3729 not_subset |= remains[k] = ~accepts[k] & dests_ch[j][k];
3730 not_consumed |= accepts[k] = accepts[k] & ~dests_ch[j][k];
3733 /* If this state isn't a subset of `accepts', create a
3734 new group state, which has the `remains'. */
3737 bitset_copy (dests_ch[ndests], remains);
3738 bitset_copy (dests_ch[j], intersec);
3739 err = re_node_set_init_copy (dests_node + ndests, &dests_node[j]);
3740 if (BE (err != REG_NOERROR, 0))
3745 /* Put the position in the current group. */
3746 ok = re_node_set_insert (&dests_node[j], cur_nodes->elems[i]);
3750 /* If all characters are consumed, go to next node. */
3754 /* Some characters remain, create a new group. */
3757 bitset_copy (dests_ch[ndests], accepts);
3758 err = re_node_set_init_1 (dests_node + ndests, cur_nodes->elems[i]);
3759 if (BE (err != REG_NOERROR, 0))
3762 bitset_empty (accepts);
3767 for (j = 0; j < ndests; ++j)
3768 re_node_set_free (dests_node + j);
3772 #ifdef RE_ENABLE_I18N
3773 /* Check how many bytes the node `dfa->nodes[node_idx]' accepts.
3774 Return the number of the bytes the node accepts.
3775 STR_IDX is the current index of the input string.
3777 This function handles the nodes which can accept one character, or
3778 one collating element like '.', '[a-z]', opposite to the other nodes
3779 can only accept one byte. */
3783 check_node_accept_bytes (const re_dfa_t *dfa, Idx node_idx,
3784 const re_string_t *input, Idx str_idx)
3786 const re_token_t *node = dfa->nodes + node_idx;
3787 int char_len, elem_len;
3790 if (BE (node->type == OP_UTF8_PERIOD, 0))
3792 unsigned char c = re_string_byte_at (input, str_idx), d;
3793 if (BE (c < 0xc2, 1))
3796 if (str_idx + 2 > input->len)
3799 d = re_string_byte_at (input, str_idx + 1);
3801 return (d < 0x80 || d > 0xbf) ? 0 : 2;
3805 if (c == 0xe0 && d < 0xa0)
3811 if (c == 0xf0 && d < 0x90)
3817 if (c == 0xf8 && d < 0x88)
3823 if (c == 0xfc && d < 0x84)
3829 if (str_idx + char_len > input->len)
3832 for (i = 1; i < char_len; ++i)
3834 d = re_string_byte_at (input, str_idx + i);
3835 if (d < 0x80 || d > 0xbf)
3841 char_len = re_string_char_size_at (input, str_idx);
3842 if (node->type == OP_PERIOD)
3846 /* FIXME: I don't think this if is needed, as both '\n'
3847 and '\0' are char_len == 1. */
3848 /* '.' accepts any one character except the following two cases. */
3849 if ((!(dfa->syntax & RE_DOT_NEWLINE) &&
3850 re_string_byte_at (input, str_idx) == '\n') ||
3851 ((dfa->syntax & RE_DOT_NOT_NULL) &&
3852 re_string_byte_at (input, str_idx) == '\0'))
3857 elem_len = re_string_elem_size_at (input, str_idx);
3858 if ((elem_len <= 1 && char_len <= 1) || char_len == 0)
3861 if (node->type == COMPLEX_BRACKET)
3863 const re_charset_t *cset = node->opr.mbcset;
3865 const unsigned char *pin
3866 = ((const unsigned char *) re_string_get_buffer (input) + str_idx);
3871 wchar_t wc = ((cset->nranges || cset->nchar_classes || cset->nmbchars)
3872 ? re_string_wchar_at (input, str_idx) : 0);
3874 /* match with multibyte character? */
3875 for (i = 0; i < cset->nmbchars; ++i)
3876 if (wc == cset->mbchars[i])
3878 match_len = char_len;
3879 goto check_node_accept_bytes_match;
3881 /* match with character_class? */
3882 for (i = 0; i < cset->nchar_classes; ++i)
3884 wctype_t wt = cset->char_classes[i];
3885 if (__iswctype (wc, wt))
3887 match_len = char_len;
3888 goto check_node_accept_bytes_match;
3893 nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
3896 unsigned int in_collseq = 0;
3897 const int32_t *table, *indirect;
3898 const unsigned char *weights, *extra;
3899 const char *collseqwc;
3901 /* This #include defines a local function! */
3902 # include <locale/weight.h>
3904 /* match with collating_symbol? */
3905 if (cset->ncoll_syms)
3906 extra = (const unsigned char *)
3907 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB);
3908 for (i = 0; i < cset->ncoll_syms; ++i)
3910 const unsigned char *coll_sym = extra + cset->coll_syms[i];
3911 /* Compare the length of input collating element and
3912 the length of current collating element. */
3913 if (*coll_sym != elem_len)
3915 /* Compare each bytes. */
3916 for (j = 0; j < *coll_sym; j++)
3917 if (pin[j] != coll_sym[1 + j])
3921 /* Match if every bytes is equal. */
3923 goto check_node_accept_bytes_match;
3929 if (elem_len <= char_len)
3931 collseqwc = _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQWC);
3932 in_collseq = __collseq_table_lookup (collseqwc, wc);
3935 in_collseq = find_collation_sequence_value (pin, elem_len);
3937 /* match with range expression? */
3938 for (i = 0; i < cset->nranges; ++i)
3939 if (cset->range_starts[i] <= in_collseq
3940 && in_collseq <= cset->range_ends[i])
3942 match_len = elem_len;
3943 goto check_node_accept_bytes_match;
3946 /* match with equivalence_class? */
3947 if (cset->nequiv_classes)
3949 const unsigned char *cp = pin;
3950 table = (const int32_t *)
3951 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
3952 weights = (const unsigned char *)
3953 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_WEIGHTMB);
3954 extra = (const unsigned char *)
3955 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAMB);
3956 indirect = (const int32_t *)
3957 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_INDIRECTMB);
3958 int32_t idx = findidx (&cp);
3960 for (i = 0; i < cset->nequiv_classes; ++i)
3962 int32_t equiv_class_idx = cset->equiv_classes[i];
3963 size_t weight_len = weights[idx & 0xffffff];
3964 if (weight_len == weights[equiv_class_idx & 0xffffff]
3965 && (idx >> 24) == (equiv_class_idx >> 24))
3970 equiv_class_idx &= 0xffffff;
3972 while (cnt <= weight_len
3973 && (weights[equiv_class_idx + 1 + cnt]
3974 == weights[idx + 1 + cnt]))
3976 if (cnt > weight_len)
3978 match_len = elem_len;
3979 goto check_node_accept_bytes_match;
3988 /* match with range expression? */
3989 #if __GNUC__ >= 2 && ! (__STDC_VERSION__ < 199901L && __STRICT_ANSI__)
3990 wchar_t cmp_buf[] = {L'\0', L'\0', wc, L'\0', L'\0', L'\0'};
3992 wchar_t cmp_buf[] = {L'\0', L'\0', L'\0', L'\0', L'\0', L'\0'};
3995 for (i = 0; i < cset->nranges; ++i)
3997 cmp_buf[0] = cset->range_starts[i];
3998 cmp_buf[4] = cset->range_ends[i];
3999 if (wcscoll (cmp_buf, cmp_buf + 2) <= 0
4000 && wcscoll (cmp_buf + 2, cmp_buf + 4) <= 0)
4002 match_len = char_len;
4003 goto check_node_accept_bytes_match;
4007 check_node_accept_bytes_match:
4008 if (!cset->non_match)
4015 return (elem_len > char_len) ? elem_len : char_len;
4024 find_collation_sequence_value (const unsigned char *mbs, size_t mbs_len)
4026 uint32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
4031 /* No valid character. Match it as a single byte character. */
4032 const unsigned char *collseq = (const unsigned char *)
4033 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQMB);
4034 return collseq[mbs[0]];
4041 const unsigned char *extra = (const unsigned char *)
4042 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB);
4043 int32_t extrasize = (const unsigned char *)
4044 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB + 1) - extra;
4046 for (idx = 0; idx < extrasize;)
4050 int32_t elem_mbs_len;
4051 /* Skip the name of collating element name. */
4052 idx = idx + extra[idx] + 1;
4053 elem_mbs_len = extra[idx++];
4054 if (mbs_len == elem_mbs_len)
4056 for (mbs_cnt = 0; mbs_cnt < elem_mbs_len; ++mbs_cnt)
4057 if (extra[idx + mbs_cnt] != mbs[mbs_cnt])
4059 if (mbs_cnt == elem_mbs_len)
4060 /* Found the entry. */
4063 /* Skip the byte sequence of the collating element. */
4064 idx += elem_mbs_len;
4065 /* Adjust for the alignment. */
4066 idx = (idx + 3) & ~3;
4067 /* Skip the collation sequence value. */
4068 idx += sizeof (uint32_t);
4069 /* Skip the wide char sequence of the collating element. */
4070 idx = idx + sizeof (uint32_t) * (extra[idx] + 1);
4071 /* If we found the entry, return the sequence value. */
4073 return *(uint32_t *) (extra + idx);
4074 /* Skip the collation sequence value. */
4075 idx += sizeof (uint32_t);
4081 #endif /* RE_ENABLE_I18N */
4083 /* Check whether the node accepts the byte which is IDX-th
4084 byte of the INPUT. */
4088 check_node_accept (const re_match_context_t *mctx, const re_token_t *node,
4092 ch = re_string_byte_at (&mctx->input, idx);
4096 if (node->opr.c != ch)
4100 case SIMPLE_BRACKET:
4101 if (!bitset_contain (node->opr.sbcset, ch))
4105 #ifdef RE_ENABLE_I18N
4106 case OP_UTF8_PERIOD:
4107 if (ch >= ASCII_CHARS)
4112 if ((ch == '\n' && !(mctx->dfa->syntax & RE_DOT_NEWLINE))
4113 || (ch == '\0' && (mctx->dfa->syntax & RE_DOT_NOT_NULL)))
4121 if (node->constraint)
4123 /* The node has constraints. Check whether the current context
4124 satisfies the constraints. */
4125 unsigned int context = re_string_context_at (&mctx->input, idx,
4127 if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
4134 /* Extend the buffers, if the buffers have run out. */
4136 static reg_errcode_t
4137 internal_function __attribute_warn_unused_result__
4138 extend_buffers (re_match_context_t *mctx)
4141 re_string_t *pstr = &mctx->input;
4143 /* Avoid overflow. */
4144 if (BE (SIZE_MAX / 2 / sizeof (re_dfastate_t *) <= pstr->bufs_len, 0))
4147 /* Double the lengthes of the buffers. */
4148 ret = re_string_realloc_buffers (pstr, pstr->bufs_len * 2);
4149 if (BE (ret != REG_NOERROR, 0))
4152 if (mctx->state_log != NULL)
4154 /* And double the length of state_log. */
4155 /* XXX We have no indication of the size of this buffer. If this
4156 allocation fail we have no indication that the state_log array
4157 does not have the right size. */
4158 re_dfastate_t **new_array = re_realloc (mctx->state_log, re_dfastate_t *,
4159 pstr->bufs_len + 1);
4160 if (BE (new_array == NULL, 0))
4162 mctx->state_log = new_array;
4165 /* Then reconstruct the buffers. */
4168 #ifdef RE_ENABLE_I18N
4169 if (pstr->mb_cur_max > 1)
4171 ret = build_wcs_upper_buffer (pstr);
4172 if (BE (ret != REG_NOERROR, 0))
4176 #endif /* RE_ENABLE_I18N */
4177 build_upper_buffer (pstr);
4181 #ifdef RE_ENABLE_I18N
4182 if (pstr->mb_cur_max > 1)
4183 build_wcs_buffer (pstr);
4185 #endif /* RE_ENABLE_I18N */
4187 if (pstr->trans != NULL)
4188 re_string_translate_buffer (pstr);
4195 /* Functions for matching context. */
4197 /* Initialize MCTX. */
4199 static reg_errcode_t
4200 internal_function __attribute_warn_unused_result__
4201 match_ctx_init (re_match_context_t *mctx, int eflags, Idx n)
4203 mctx->eflags = eflags;
4204 mctx->match_last = REG_MISSING;
4207 /* Avoid overflow. */
4208 size_t max_object_size =
4209 MAX (sizeof (struct re_backref_cache_entry),
4210 sizeof (re_sub_match_top_t *));
4211 if (BE (SIZE_MAX / max_object_size < n, 0))
4214 mctx->bkref_ents = re_malloc (struct re_backref_cache_entry, n);
4215 mctx->sub_tops = re_malloc (re_sub_match_top_t *, n);
4216 if (BE (mctx->bkref_ents == NULL || mctx->sub_tops == NULL, 0))
4219 /* Already zero-ed by the caller.
4221 mctx->bkref_ents = NULL;
4222 mctx->nbkref_ents = 0;
4223 mctx->nsub_tops = 0; */
4224 mctx->abkref_ents = n;
4225 mctx->max_mb_elem_len = 1;
4226 mctx->asub_tops = n;
4230 /* Clean the entries which depend on the current input in MCTX.
4231 This function must be invoked when the matcher changes the start index
4232 of the input, or changes the input string. */
4236 match_ctx_clean (re_match_context_t *mctx)
4239 for (st_idx = 0; st_idx < mctx->nsub_tops; ++st_idx)
4242 re_sub_match_top_t *top = mctx->sub_tops[st_idx];
4243 for (sl_idx = 0; sl_idx < top->nlasts; ++sl_idx)
4245 re_sub_match_last_t *last = top->lasts[sl_idx];
4246 re_free (last->path.array);
4249 re_free (top->lasts);
4252 re_free (top->path->array);
4253 re_free (top->path);
4258 mctx->nsub_tops = 0;
4259 mctx->nbkref_ents = 0;
4262 /* Free all the memory associated with MCTX. */
4266 match_ctx_free (re_match_context_t *mctx)
4268 /* First, free all the memory associated with MCTX->SUB_TOPS. */
4269 match_ctx_clean (mctx);
4270 re_free (mctx->sub_tops);
4271 re_free (mctx->bkref_ents);
4274 /* Add a new backreference entry to MCTX.
4275 Note that we assume that caller never call this function with duplicate
4276 entry, and call with STR_IDX which isn't smaller than any existing entry.
4279 static reg_errcode_t
4280 internal_function __attribute_warn_unused_result__
4281 match_ctx_add_entry (re_match_context_t *mctx, Idx node, Idx str_idx, Idx from,
4284 if (mctx->nbkref_ents >= mctx->abkref_ents)
4286 struct re_backref_cache_entry* new_entry;
4287 new_entry = re_realloc (mctx->bkref_ents, struct re_backref_cache_entry,
4288 mctx->abkref_ents * 2);
4289 if (BE (new_entry == NULL, 0))
4291 re_free (mctx->bkref_ents);
4294 mctx->bkref_ents = new_entry;
4295 memset (mctx->bkref_ents + mctx->nbkref_ents, '\0',
4296 sizeof (struct re_backref_cache_entry) * mctx->abkref_ents);
4297 mctx->abkref_ents *= 2;
4299 if (mctx->nbkref_ents > 0
4300 && mctx->bkref_ents[mctx->nbkref_ents - 1].str_idx == str_idx)
4301 mctx->bkref_ents[mctx->nbkref_ents - 1].more = 1;
4303 mctx->bkref_ents[mctx->nbkref_ents].node = node;
4304 mctx->bkref_ents[mctx->nbkref_ents].str_idx = str_idx;
4305 mctx->bkref_ents[mctx->nbkref_ents].subexp_from = from;
4306 mctx->bkref_ents[mctx->nbkref_ents].subexp_to = to;
4308 /* This is a cache that saves negative results of check_dst_limits_calc_pos.
4309 If bit N is clear, means that this entry won't epsilon-transition to
4310 an OP_OPEN_SUBEXP or OP_CLOSE_SUBEXP for the N+1-th subexpression. If
4311 it is set, check_dst_limits_calc_pos_1 will recurse and try to find one
4314 A backreference does not epsilon-transition unless it is empty, so set
4315 to all zeros if FROM != TO. */
4316 mctx->bkref_ents[mctx->nbkref_ents].eps_reachable_subexps_map
4317 = (from == to ? -1 : 0);
4319 mctx->bkref_ents[mctx->nbkref_ents++].more = 0;
4320 if (mctx->max_mb_elem_len < to - from)
4321 mctx->max_mb_elem_len = to - from;
4325 /* Return the first entry with the same str_idx, or REG_MISSING if none is
4326 found. Note that MCTX->BKREF_ENTS is already sorted by MCTX->STR_IDX. */
4330 search_cur_bkref_entry (const re_match_context_t *mctx, Idx str_idx)
4332 Idx left, right, mid, last;
4333 last = right = mctx->nbkref_ents;
4334 for (left = 0; left < right;)
4336 mid = (left + right) / 2;
4337 if (mctx->bkref_ents[mid].str_idx < str_idx)
4342 if (left < last && mctx->bkref_ents[left].str_idx == str_idx)
4348 /* Register the node NODE, whose type is OP_OPEN_SUBEXP, and which matches
4351 static reg_errcode_t
4352 internal_function __attribute_warn_unused_result__
4353 match_ctx_add_subtop (re_match_context_t *mctx, Idx node, Idx str_idx)
4356 assert (mctx->sub_tops != NULL);
4357 assert (mctx->asub_tops > 0);
4359 if (BE (mctx->nsub_tops == mctx->asub_tops, 0))
4361 Idx new_asub_tops = mctx->asub_tops * 2;
4362 re_sub_match_top_t **new_array = re_realloc (mctx->sub_tops,
4363 re_sub_match_top_t *,
4365 if (BE (new_array == NULL, 0))
4367 mctx->sub_tops = new_array;
4368 mctx->asub_tops = new_asub_tops;
4370 mctx->sub_tops[mctx->nsub_tops] = calloc (1, sizeof (re_sub_match_top_t));
4371 if (BE (mctx->sub_tops[mctx->nsub_tops] == NULL, 0))
4373 mctx->sub_tops[mctx->nsub_tops]->node = node;
4374 mctx->sub_tops[mctx->nsub_tops++]->str_idx = str_idx;
4378 /* Register the node NODE, whose type is OP_CLOSE_SUBEXP, and which matches
4379 at STR_IDX, whose corresponding OP_OPEN_SUBEXP is SUB_TOP. */
4381 static re_sub_match_last_t *
4383 match_ctx_add_sublast (re_sub_match_top_t *subtop, Idx node, Idx str_idx)
4385 re_sub_match_last_t *new_entry;
4386 if (BE (subtop->nlasts == subtop->alasts, 0))
4388 Idx new_alasts = 2 * subtop->alasts + 1;
4389 re_sub_match_last_t **new_array = re_realloc (subtop->lasts,
4390 re_sub_match_last_t *,
4392 if (BE (new_array == NULL, 0))
4394 subtop->lasts = new_array;
4395 subtop->alasts = new_alasts;
4397 new_entry = calloc (1, sizeof (re_sub_match_last_t));
4398 if (BE (new_entry != NULL, 1))
4400 subtop->lasts[subtop->nlasts] = new_entry;
4401 new_entry->node = node;
4402 new_entry->str_idx = str_idx;
4410 sift_ctx_init (re_sift_context_t *sctx, re_dfastate_t **sifted_sts,
4411 re_dfastate_t **limited_sts, Idx last_node, Idx last_str_idx)
4413 sctx->sifted_states = sifted_sts;
4414 sctx->limited_states = limited_sts;
4415 sctx->last_node = last_node;
4416 sctx->last_str_idx = last_str_idx;
4417 re_node_set_init_empty (&sctx->limits);