1 /* Extended regular expression matching and search library.
2 Copyright (C) 2002-2012 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
4 Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>.
6 This program is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by
8 the Free Software Foundation; either version 2, or (at your option)
11 This program is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 GNU General Public License for more details.
16 You should have received a copy of the GNU General Public License along
17 with this program; if not, see <http://www.gnu.org/licenses/>. */
19 static reg_errcode_t match_ctx_init (re_match_context_t *cache, int eflags,
20 Idx n) internal_function;
21 static void match_ctx_clean (re_match_context_t *mctx) internal_function;
22 static void match_ctx_free (re_match_context_t *cache) internal_function;
23 static reg_errcode_t match_ctx_add_entry (re_match_context_t *cache, Idx node,
24 Idx str_idx, Idx from, Idx to)
26 static Idx search_cur_bkref_entry (const re_match_context_t *mctx, Idx str_idx)
28 static reg_errcode_t match_ctx_add_subtop (re_match_context_t *mctx, Idx node,
29 Idx str_idx) internal_function;
30 static re_sub_match_last_t * match_ctx_add_sublast (re_sub_match_top_t *subtop,
31 Idx node, Idx str_idx)
33 static void sift_ctx_init (re_sift_context_t *sctx, re_dfastate_t **sifted_sts,
34 re_dfastate_t **limited_sts, Idx last_node,
37 static reg_errcode_t re_search_internal (const regex_t *preg,
38 const char *string, Idx length,
39 Idx start, Idx last_start, Idx stop,
40 size_t nmatch, regmatch_t pmatch[],
41 int eflags) internal_function;
42 static regoff_t re_search_2_stub (struct re_pattern_buffer *bufp,
43 const char *string1, Idx length1,
44 const char *string2, Idx length2,
45 Idx start, regoff_t range,
46 struct re_registers *regs,
47 Idx stop, bool ret_len) internal_function;
48 static regoff_t re_search_stub (struct re_pattern_buffer *bufp,
49 const char *string, Idx length, Idx start,
50 regoff_t range, Idx stop,
51 struct re_registers *regs,
52 bool ret_len) internal_function;
53 static unsigned re_copy_regs (struct re_registers *regs, regmatch_t *pmatch,
54 Idx nregs, int regs_allocated) internal_function;
55 static reg_errcode_t prune_impossible_nodes (re_match_context_t *mctx)
57 static Idx check_matching (re_match_context_t *mctx, bool fl_longest_match,
58 Idx *p_match_first) internal_function;
59 static Idx check_halt_state_context (const re_match_context_t *mctx,
60 const re_dfastate_t *state, Idx idx)
62 static void update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
63 regmatch_t *prev_idx_match, Idx cur_node,
64 Idx cur_idx, Idx nmatch) internal_function;
65 static reg_errcode_t push_fail_stack (struct re_fail_stack_t *fs,
66 Idx str_idx, Idx dest_node, Idx nregs,
68 re_node_set *eps_via_nodes)
70 static reg_errcode_t set_regs (const regex_t *preg,
71 const re_match_context_t *mctx,
72 size_t nmatch, regmatch_t *pmatch,
73 bool fl_backtrack) internal_function;
74 static reg_errcode_t free_fail_stack_return (struct re_fail_stack_t *fs)
78 static int sift_states_iter_mb (const re_match_context_t *mctx,
79 re_sift_context_t *sctx,
80 Idx node_idx, Idx str_idx, Idx max_str_idx)
82 #endif /* RE_ENABLE_I18N */
83 static reg_errcode_t sift_states_backward (const re_match_context_t *mctx,
84 re_sift_context_t *sctx)
86 static reg_errcode_t build_sifted_states (const re_match_context_t *mctx,
87 re_sift_context_t *sctx, Idx str_idx,
88 re_node_set *cur_dest)
90 static reg_errcode_t update_cur_sifted_state (const re_match_context_t *mctx,
91 re_sift_context_t *sctx,
93 re_node_set *dest_nodes)
95 static reg_errcode_t add_epsilon_src_nodes (const re_dfa_t *dfa,
96 re_node_set *dest_nodes,
97 const re_node_set *candidates)
99 static bool check_dst_limits (const re_match_context_t *mctx,
100 const re_node_set *limits,
101 Idx dst_node, Idx dst_idx, Idx src_node,
102 Idx src_idx) internal_function;
103 static int check_dst_limits_calc_pos_1 (const re_match_context_t *mctx,
104 int boundaries, Idx subexp_idx,
105 Idx from_node, Idx bkref_idx)
107 static int check_dst_limits_calc_pos (const re_match_context_t *mctx,
108 Idx limit, Idx subexp_idx,
109 Idx node, Idx str_idx,
110 Idx bkref_idx) internal_function;
111 static reg_errcode_t check_subexp_limits (const re_dfa_t *dfa,
112 re_node_set *dest_nodes,
113 const re_node_set *candidates,
115 struct re_backref_cache_entry *bkref_ents,
116 Idx str_idx) internal_function;
117 static reg_errcode_t sift_states_bkref (const re_match_context_t *mctx,
118 re_sift_context_t *sctx,
119 Idx str_idx, const re_node_set *candidates)
121 static reg_errcode_t merge_state_array (const re_dfa_t *dfa,
123 re_dfastate_t **src, Idx num)
125 static re_dfastate_t *find_recover_state (reg_errcode_t *err,
126 re_match_context_t *mctx) internal_function;
127 static re_dfastate_t *transit_state (reg_errcode_t *err,
128 re_match_context_t *mctx,
129 re_dfastate_t *state) internal_function;
130 static re_dfastate_t *merge_state_with_log (reg_errcode_t *err,
131 re_match_context_t *mctx,
132 re_dfastate_t *next_state)
134 static reg_errcode_t check_subexp_matching_top (re_match_context_t *mctx,
135 re_node_set *cur_nodes,
136 Idx str_idx) internal_function;
138 static re_dfastate_t *transit_state_sb (reg_errcode_t *err,
139 re_match_context_t *mctx,
140 re_dfastate_t *pstate)
143 #ifdef RE_ENABLE_I18N
144 static reg_errcode_t transit_state_mb (re_match_context_t *mctx,
145 re_dfastate_t *pstate)
147 #endif /* RE_ENABLE_I18N */
148 static reg_errcode_t transit_state_bkref (re_match_context_t *mctx,
149 const re_node_set *nodes)
151 static reg_errcode_t get_subexp (re_match_context_t *mctx,
152 Idx bkref_node, Idx bkref_str_idx)
154 static reg_errcode_t get_subexp_sub (re_match_context_t *mctx,
155 const re_sub_match_top_t *sub_top,
156 re_sub_match_last_t *sub_last,
157 Idx bkref_node, Idx bkref_str)
159 static Idx find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
160 Idx subexp_idx, int type) internal_function;
161 static reg_errcode_t check_arrival (re_match_context_t *mctx,
162 state_array_t *path, Idx top_node,
163 Idx top_str, Idx last_node, Idx last_str,
164 int type) internal_function;
165 static reg_errcode_t check_arrival_add_next_nodes (re_match_context_t *mctx,
167 re_node_set *cur_nodes,
168 re_node_set *next_nodes)
170 static reg_errcode_t check_arrival_expand_ecl (const re_dfa_t *dfa,
171 re_node_set *cur_nodes,
172 Idx ex_subexp, int type)
174 static reg_errcode_t check_arrival_expand_ecl_sub (const re_dfa_t *dfa,
175 re_node_set *dst_nodes,
176 Idx target, Idx ex_subexp,
177 int type) internal_function;
178 static reg_errcode_t expand_bkref_cache (re_match_context_t *mctx,
179 re_node_set *cur_nodes, Idx cur_str,
180 Idx subexp_num, int type)
182 static bool build_trtable (const re_dfa_t *dfa,
183 re_dfastate_t *state) internal_function;
184 #ifdef RE_ENABLE_I18N
185 static int check_node_accept_bytes (const re_dfa_t *dfa, Idx node_idx,
186 const re_string_t *input, Idx idx)
189 static unsigned int find_collation_sequence_value (const unsigned char *mbs,
193 #endif /* RE_ENABLE_I18N */
194 static Idx group_nodes_into_DFAstates (const re_dfa_t *dfa,
195 const re_dfastate_t *state,
196 re_node_set *states_node,
197 bitset_t *states_ch) internal_function;
198 static bool check_node_accept (const re_match_context_t *mctx,
199 const re_token_t *node, Idx idx)
201 static reg_errcode_t extend_buffers (re_match_context_t *mctx)
204 /* Entry point for POSIX code. */
206 /* regexec searches for a given pattern, specified by PREG, in the
209 If NMATCH is zero or REG_NOSUB was set in the cflags argument to
210 'regcomp', we ignore PMATCH. Otherwise, we assume PMATCH has at
211 least NMATCH elements, and we set them to the offsets of the
212 corresponding matched substrings.
214 EFLAGS specifies "execution flags" which affect matching: if
215 REG_NOTBOL is set, then ^ does not match at the beginning of the
216 string; if REG_NOTEOL is set, then $ does not match at the end.
218 We return 0 if we find a match and REG_NOMATCH if not. */
221 regexec (preg, string, nmatch, pmatch, eflags)
222 const regex_t *_Restrict_ preg;
223 const char *_Restrict_ string;
225 regmatch_t pmatch[_Restrict_arr_];
231 re_dfa_t *dfa = preg->buffer;
234 if (eflags & ~(REG_NOTBOL | REG_NOTEOL | REG_STARTEND))
237 if (eflags & REG_STARTEND)
239 start = pmatch[0].rm_so;
240 length = pmatch[0].rm_eo;
245 length = strlen (string);
248 __libc_lock_lock (dfa->lock);
250 err = re_search_internal (preg, string, length, start, length,
251 length, 0, NULL, eflags);
253 err = re_search_internal (preg, string, length, start, length,
254 length, nmatch, pmatch, eflags);
255 __libc_lock_unlock (dfa->lock);
256 return err != REG_NOERROR;
260 # include <shlib-compat.h>
261 versioned_symbol (libc, __regexec, regexec, GLIBC_2_3_4);
263 # if SHLIB_COMPAT (libc, GLIBC_2_0, GLIBC_2_3_4)
264 __typeof__ (__regexec) __compat_regexec;
267 attribute_compat_text_section
268 __compat_regexec (const regex_t *_Restrict_ preg,
269 const char *_Restrict_ string, size_t nmatch,
270 regmatch_t pmatch[], int eflags)
272 return regexec (preg, string, nmatch, pmatch,
273 eflags & (REG_NOTBOL | REG_NOTEOL));
275 compat_symbol (libc, __compat_regexec, regexec, GLIBC_2_0);
279 /* Entry points for GNU code. */
281 /* re_match, re_search, re_match_2, re_search_2
283 The former two functions operate on STRING with length LENGTH,
284 while the later two operate on concatenation of STRING1 and STRING2
285 with lengths LENGTH1 and LENGTH2, respectively.
287 re_match() matches the compiled pattern in BUFP against the string,
288 starting at index START.
290 re_search() first tries matching at index START, then it tries to match
291 starting from index START + 1, and so on. The last start position tried
292 is START + RANGE. (Thus RANGE = 0 forces re_search to operate the same
295 The parameter STOP of re_{match,search}_2 specifies that no match exceeding
296 the first STOP characters of the concatenation of the strings should be
299 If REGS is not NULL, and BUFP->no_sub is not set, the offsets of the match
300 and all groups is stored in REGS. (For the "_2" variants, the offsets are
301 computed relative to the concatenation, not relative to the individual
304 On success, re_match* functions return the length of the match, re_search*
305 return the position of the start of the match. Return value -1 means no
306 match was found and -2 indicates an internal error. */
309 re_match (bufp, string, length, start, regs)
310 struct re_pattern_buffer *bufp;
313 struct re_registers *regs;
315 return re_search_stub (bufp, string, length, start, 0, length, regs, true);
318 weak_alias (__re_match, re_match)
322 re_search (bufp, string, length, start, range, regs)
323 struct re_pattern_buffer *bufp;
327 struct re_registers *regs;
329 return re_search_stub (bufp, string, length, start, range, length, regs,
333 weak_alias (__re_search, re_search)
337 re_match_2 (bufp, string1, length1, string2, length2, start, regs, stop)
338 struct re_pattern_buffer *bufp;
339 const char *string1, *string2;
340 Idx length1, length2, start, stop;
341 struct re_registers *regs;
343 return re_search_2_stub (bufp, string1, length1, string2, length2,
344 start, 0, regs, stop, true);
347 weak_alias (__re_match_2, re_match_2)
351 re_search_2 (bufp, string1, length1, string2, length2, start, range, regs, stop)
352 struct re_pattern_buffer *bufp;
353 const char *string1, *string2;
354 Idx length1, length2, start, stop;
356 struct re_registers *regs;
358 return re_search_2_stub (bufp, string1, length1, string2, length2,
359 start, range, regs, stop, false);
362 weak_alias (__re_search_2, re_search_2)
366 re_search_2_stub (struct re_pattern_buffer *bufp,
367 const char *string1, Idx length1,
368 const char *string2, Idx length2,
369 Idx start, regoff_t range, struct re_registers *regs,
370 Idx stop, bool ret_len)
374 Idx len = length1 + length2;
377 if (BE (length1 < 0 || length2 < 0 || stop < 0 || len < length1, 0))
380 /* Concatenate the strings. */
384 s = re_malloc (char, len);
386 if (BE (s == NULL, 0))
389 memcpy (__mempcpy (s, string1, length1), string2, length2);
391 memcpy (s, string1, length1);
392 memcpy (s + length1, string2, length2);
401 rval = re_search_stub (bufp, str, len, start, range, stop, regs,
407 /* The parameters have the same meaning as those of re_search.
408 Additional parameters:
409 If RET_LEN is true the length of the match is returned (re_match style);
410 otherwise the position of the match is returned. */
413 re_search_stub (struct re_pattern_buffer *bufp,
414 const char *string, Idx length,
415 Idx start, regoff_t range, Idx stop, struct re_registers *regs,
418 reg_errcode_t result;
424 re_dfa_t *dfa = bufp->buffer;
426 Idx last_start = start + range;
428 /* Check for out-of-range. */
429 if (BE (start < 0 || start > length, 0))
431 if (BE (length < last_start || (0 <= range && last_start < start), 0))
433 else if (BE (last_start < 0 || (range < 0 && start <= last_start), 0))
436 __libc_lock_lock (dfa->lock);
438 eflags |= (bufp->not_bol) ? REG_NOTBOL : 0;
439 eflags |= (bufp->not_eol) ? REG_NOTEOL : 0;
441 /* Compile fastmap if we haven't yet. */
442 if (start < last_start && bufp->fastmap != NULL && !bufp->fastmap_accurate)
443 re_compile_fastmap (bufp);
445 if (BE (bufp->no_sub, 0))
448 /* We need at least 1 register. */
451 else if (BE (bufp->regs_allocated == REGS_FIXED
452 && regs->num_regs <= bufp->re_nsub, 0))
454 nregs = regs->num_regs;
455 if (BE (nregs < 1, 0))
457 /* Nothing can be copied to regs. */
463 nregs = bufp->re_nsub + 1;
464 pmatch = re_malloc (regmatch_t, nregs);
465 if (BE (pmatch == NULL, 0))
471 result = re_search_internal (bufp, string, length, start, last_start, stop,
472 nregs, pmatch, eflags);
476 /* I hope we needn't fill their regs with -1's when no match was found. */
477 if (result != REG_NOERROR)
478 rval = result == REG_NOMATCH ? -1 : -2;
479 else if (regs != NULL)
481 /* If caller wants register contents data back, copy them. */
482 bufp->regs_allocated = re_copy_regs (regs, pmatch, nregs,
483 bufp->regs_allocated);
484 if (BE (bufp->regs_allocated == REGS_UNALLOCATED, 0))
488 if (BE (rval == 0, 1))
492 assert (pmatch[0].rm_so == start);
493 rval = pmatch[0].rm_eo - start;
496 rval = pmatch[0].rm_so;
500 __libc_lock_unlock (dfa->lock);
505 re_copy_regs (struct re_registers *regs, regmatch_t *pmatch, Idx nregs,
508 int rval = REGS_REALLOCATE;
510 Idx need_regs = nregs + 1;
511 /* We need one extra element beyond 'num_regs' for the '-1' marker GNU code
514 /* Have the register data arrays been allocated? */
515 if (regs_allocated == REGS_UNALLOCATED)
516 { /* No. So allocate them with malloc. */
517 regs->start = re_malloc (regoff_t, need_regs);
518 if (BE (regs->start == NULL, 0))
519 return REGS_UNALLOCATED;
520 regs->end = re_malloc (regoff_t, need_regs);
521 if (BE (regs->end == NULL, 0))
523 re_free (regs->start);
524 return REGS_UNALLOCATED;
526 regs->num_regs = need_regs;
528 else if (regs_allocated == REGS_REALLOCATE)
529 { /* Yes. If we need more elements than were already
530 allocated, reallocate them. If we need fewer, just
532 if (BE (need_regs > regs->num_regs, 0))
534 regoff_t *new_start = re_realloc (regs->start, regoff_t, need_regs);
536 if (BE (new_start == NULL, 0))
537 return REGS_UNALLOCATED;
538 new_end = re_realloc (regs->end, regoff_t, need_regs);
539 if (BE (new_end == NULL, 0))
542 return REGS_UNALLOCATED;
544 regs->start = new_start;
546 regs->num_regs = need_regs;
551 assert (regs_allocated == REGS_FIXED);
552 /* This function may not be called with REGS_FIXED and nregs too big. */
553 assert (regs->num_regs >= nregs);
558 for (i = 0; i < nregs; ++i)
560 regs->start[i] = pmatch[i].rm_so;
561 regs->end[i] = pmatch[i].rm_eo;
563 for ( ; i < regs->num_regs; ++i)
564 regs->start[i] = regs->end[i] = -1;
569 /* Set REGS to hold NUM_REGS registers, storing them in STARTS and
570 ENDS. Subsequent matches using PATTERN_BUFFER and REGS will use
571 this memory for recording register information. STARTS and ENDS
572 must be allocated using the malloc library routine, and must each
573 be at least NUM_REGS * sizeof (regoff_t) bytes long.
575 If NUM_REGS == 0, then subsequent matches should allocate their own
578 Unless this function is called, the first search or match using
579 PATTERN_BUFFER will allocate its own register data, without
580 freeing the old data. */
583 re_set_registers (bufp, regs, num_regs, starts, ends)
584 struct re_pattern_buffer *bufp;
585 struct re_registers *regs;
586 __re_size_t num_regs;
587 regoff_t *starts, *ends;
591 bufp->regs_allocated = REGS_REALLOCATE;
592 regs->num_regs = num_regs;
593 regs->start = starts;
598 bufp->regs_allocated = REGS_UNALLOCATED;
600 regs->start = regs->end = NULL;
604 weak_alias (__re_set_registers, re_set_registers)
607 /* Entry points compatible with 4.2 BSD regex library. We don't define
608 them unless specifically requested. */
610 #if defined _REGEX_RE_COMP || defined _LIBC
618 return 0 == regexec (&re_comp_buf, s, 0, NULL, 0);
620 #endif /* _REGEX_RE_COMP */
622 /* Internal entry point. */
624 /* Searches for a compiled pattern PREG in the string STRING, whose
625 length is LENGTH. NMATCH, PMATCH, and EFLAGS have the same
626 meaning as with regexec. LAST_START is START + RANGE, where
627 START and RANGE have the same meaning as with re_search.
628 Return REG_NOERROR if we find a match, and REG_NOMATCH if not,
629 otherwise return the error code.
630 Note: We assume front end functions already check ranges.
631 (0 <= LAST_START && LAST_START <= LENGTH) */
634 __attribute_warn_unused_result__
635 re_search_internal (const regex_t *preg,
636 const char *string, Idx length,
637 Idx start, Idx last_start, Idx stop,
638 size_t nmatch, regmatch_t pmatch[],
642 const re_dfa_t *dfa = preg->buffer;
643 Idx left_lim, right_lim;
645 bool fl_longest_match;
648 Idx match_last = REG_MISSING;
652 #if defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L)
653 re_match_context_t mctx = { .dfa = dfa };
655 re_match_context_t mctx;
657 char *fastmap = ((preg->fastmap != NULL && preg->fastmap_accurate
658 && start != last_start && !preg->can_be_null)
659 ? preg->fastmap : NULL);
660 RE_TRANSLATE_TYPE t = preg->translate;
662 #if !(defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L))
663 memset (&mctx, '\0', sizeof (re_match_context_t));
667 extra_nmatch = (nmatch > preg->re_nsub) ? nmatch - (preg->re_nsub + 1) : 0;
668 nmatch -= extra_nmatch;
670 /* Check if the DFA haven't been compiled. */
671 if (BE (preg->used == 0 || dfa->init_state == NULL
672 || dfa->init_state_word == NULL || dfa->init_state_nl == NULL
673 || dfa->init_state_begbuf == NULL, 0))
677 /* We assume front-end functions already check them. */
678 assert (0 <= last_start && last_start <= length);
681 /* If initial states with non-begbuf contexts have no elements,
682 the regex must be anchored. If preg->newline_anchor is set,
683 we'll never use init_state_nl, so do not check it. */
684 if (dfa->init_state->nodes.nelem == 0
685 && dfa->init_state_word->nodes.nelem == 0
686 && (dfa->init_state_nl->nodes.nelem == 0
687 || !preg->newline_anchor))
689 if (start != 0 && last_start != 0)
691 start = last_start = 0;
694 /* We must check the longest matching, if nmatch > 0. */
695 fl_longest_match = (nmatch != 0 || dfa->nbackref);
697 err = re_string_allocate (&mctx.input, string, length, dfa->nodes_len + 1,
698 preg->translate, (preg->syntax & RE_ICASE) != 0,
700 if (BE (err != REG_NOERROR, 0))
702 mctx.input.stop = stop;
703 mctx.input.raw_stop = stop;
704 mctx.input.newline_anchor = preg->newline_anchor;
706 err = match_ctx_init (&mctx, eflags, dfa->nbackref * 2);
707 if (BE (err != REG_NOERROR, 0))
710 /* We will log all the DFA states through which the dfa pass,
711 if nmatch > 1, or this dfa has "multibyte node", which is a
712 back-reference or a node which can accept multibyte character or
713 multi character collating element. */
714 if (nmatch > 1 || dfa->has_mb_node)
716 /* Avoid overflow. */
717 if (BE ((MIN (IDX_MAX, SIZE_MAX / sizeof (re_dfastate_t *))
718 <= mctx.input.bufs_len), 0))
724 mctx.state_log = re_malloc (re_dfastate_t *, mctx.input.bufs_len + 1);
725 if (BE (mctx.state_log == NULL, 0))
732 mctx.state_log = NULL;
735 mctx.input.tip_context = (eflags & REG_NOTBOL) ? CONTEXT_BEGBUF
736 : CONTEXT_NEWLINE | CONTEXT_BEGBUF;
738 /* Check incrementally whether of not the input string match. */
739 incr = (last_start < start) ? -1 : 1;
740 left_lim = (last_start < start) ? last_start : start;
741 right_lim = (last_start < start) ? start : last_start;
742 sb = dfa->mb_cur_max == 1;
745 ? ((sb || !(preg->syntax & RE_ICASE || t) ? 4 : 0)
746 | (start <= last_start ? 2 : 0)
747 | (t != NULL ? 1 : 0))
750 for (;; match_first += incr)
753 if (match_first < left_lim || right_lim < match_first)
756 /* Advance as rapidly as possible through the string, until we
757 find a plausible place to start matching. This may be done
758 with varying efficiency, so there are various possibilities:
759 only the most common of them are specialized, in order to
760 save on code size. We use a switch statement for speed. */
768 /* Fastmap with single-byte translation, match forward. */
769 while (BE (match_first < right_lim, 1)
770 && !fastmap[t[(unsigned char) string[match_first]]])
772 goto forward_match_found_start_or_reached_end;
775 /* Fastmap without translation, match forward. */
776 while (BE (match_first < right_lim, 1)
777 && !fastmap[(unsigned char) string[match_first]])
780 forward_match_found_start_or_reached_end:
781 if (BE (match_first == right_lim, 0))
783 ch = match_first >= length
784 ? 0 : (unsigned char) string[match_first];
785 if (!fastmap[t ? t[ch] : ch])
792 /* Fastmap without multi-byte translation, match backwards. */
793 while (match_first >= left_lim)
795 ch = match_first >= length
796 ? 0 : (unsigned char) string[match_first];
797 if (fastmap[t ? t[ch] : ch])
801 if (match_first < left_lim)
806 /* In this case, we can't determine easily the current byte,
807 since it might be a component byte of a multibyte
808 character. Then we use the constructed buffer instead. */
811 /* If MATCH_FIRST is out of the valid range, reconstruct the
813 __re_size_t offset = match_first - mctx.input.raw_mbs_idx;
814 if (BE (offset >= (__re_size_t) mctx.input.valid_raw_len, 0))
816 err = re_string_reconstruct (&mctx.input, match_first,
818 if (BE (err != REG_NOERROR, 0))
821 offset = match_first - mctx.input.raw_mbs_idx;
823 /* If MATCH_FIRST is out of the buffer, leave it as '\0'.
824 Note that MATCH_FIRST must not be smaller than 0. */
825 ch = (match_first >= length
826 ? 0 : re_string_byte_at (&mctx.input, offset));
830 if (match_first < left_lim || match_first > right_lim)
839 /* Reconstruct the buffers so that the matcher can assume that
840 the matching starts from the beginning of the buffer. */
841 err = re_string_reconstruct (&mctx.input, match_first, eflags);
842 if (BE (err != REG_NOERROR, 0))
845 #ifdef RE_ENABLE_I18N
846 /* Don't consider this char as a possible match start if it part,
847 yet isn't the head, of a multibyte character. */
848 if (!sb && !re_string_first_byte (&mctx.input, 0))
852 /* It seems to be appropriate one, then use the matcher. */
853 /* We assume that the matching starts from 0. */
854 mctx.state_log_top = mctx.nbkref_ents = mctx.max_mb_elem_len = 0;
855 match_last = check_matching (&mctx, fl_longest_match,
856 start <= last_start ? &match_first : NULL);
857 if (match_last != REG_MISSING)
859 if (BE (match_last == REG_ERROR, 0))
866 mctx.match_last = match_last;
867 if ((!preg->no_sub && nmatch > 1) || dfa->nbackref)
869 re_dfastate_t *pstate = mctx.state_log[match_last];
870 mctx.last_node = check_halt_state_context (&mctx, pstate,
873 if ((!preg->no_sub && nmatch > 1 && dfa->has_plural_match)
876 err = prune_impossible_nodes (&mctx);
877 if (err == REG_NOERROR)
879 if (BE (err != REG_NOMATCH, 0))
881 match_last = REG_MISSING;
884 break; /* We found a match. */
888 match_ctx_clean (&mctx);
892 assert (match_last != REG_MISSING);
893 assert (err == REG_NOERROR);
896 /* Set pmatch[] if we need. */
901 /* Initialize registers. */
902 for (reg_idx = 1; reg_idx < nmatch; ++reg_idx)
903 pmatch[reg_idx].rm_so = pmatch[reg_idx].rm_eo = -1;
905 /* Set the points where matching start/end. */
907 pmatch[0].rm_eo = mctx.match_last;
908 /* FIXME: This function should fail if mctx.match_last exceeds
909 the maximum possible regoff_t value. We need a new error
910 code REG_OVERFLOW. */
912 if (!preg->no_sub && nmatch > 1)
914 err = set_regs (preg, &mctx, nmatch, pmatch,
915 dfa->has_plural_match && dfa->nbackref > 0);
916 if (BE (err != REG_NOERROR, 0))
920 /* At last, add the offset to each register, since we slid
921 the buffers so that we could assume that the matching starts
923 for (reg_idx = 0; reg_idx < nmatch; ++reg_idx)
924 if (pmatch[reg_idx].rm_so != -1)
926 #ifdef RE_ENABLE_I18N
927 if (BE (mctx.input.offsets_needed != 0, 0))
929 pmatch[reg_idx].rm_so =
930 (pmatch[reg_idx].rm_so == mctx.input.valid_len
931 ? mctx.input.valid_raw_len
932 : mctx.input.offsets[pmatch[reg_idx].rm_so]);
933 pmatch[reg_idx].rm_eo =
934 (pmatch[reg_idx].rm_eo == mctx.input.valid_len
935 ? mctx.input.valid_raw_len
936 : mctx.input.offsets[pmatch[reg_idx].rm_eo]);
939 assert (mctx.input.offsets_needed == 0);
941 pmatch[reg_idx].rm_so += match_first;
942 pmatch[reg_idx].rm_eo += match_first;
944 for (reg_idx = 0; reg_idx < extra_nmatch; ++reg_idx)
946 pmatch[nmatch + reg_idx].rm_so = -1;
947 pmatch[nmatch + reg_idx].rm_eo = -1;
951 for (reg_idx = 0; reg_idx + 1 < nmatch; reg_idx++)
952 if (dfa->subexp_map[reg_idx] != reg_idx)
954 pmatch[reg_idx + 1].rm_so
955 = pmatch[dfa->subexp_map[reg_idx] + 1].rm_so;
956 pmatch[reg_idx + 1].rm_eo
957 = pmatch[dfa->subexp_map[reg_idx] + 1].rm_eo;
962 re_free (mctx.state_log);
964 match_ctx_free (&mctx);
965 re_string_destruct (&mctx.input);
970 __attribute_warn_unused_result__
971 prune_impossible_nodes (re_match_context_t *mctx)
973 const re_dfa_t *const dfa = mctx->dfa;
974 Idx halt_node, match_last;
976 re_dfastate_t **sifted_states;
977 re_dfastate_t **lim_states = NULL;
978 re_sift_context_t sctx;
980 assert (mctx->state_log != NULL);
982 match_last = mctx->match_last;
983 halt_node = mctx->last_node;
985 /* Avoid overflow. */
986 if (BE (MIN (IDX_MAX, SIZE_MAX / sizeof (re_dfastate_t *)) <= match_last, 0))
989 sifted_states = re_malloc (re_dfastate_t *, match_last + 1);
990 if (BE (sifted_states == NULL, 0))
997 lim_states = re_malloc (re_dfastate_t *, match_last + 1);
998 if (BE (lim_states == NULL, 0))
1005 memset (lim_states, '\0',
1006 sizeof (re_dfastate_t *) * (match_last + 1));
1007 sift_ctx_init (&sctx, sifted_states, lim_states, halt_node,
1009 ret = sift_states_backward (mctx, &sctx);
1010 re_node_set_free (&sctx.limits);
1011 if (BE (ret != REG_NOERROR, 0))
1013 if (sifted_states[0] != NULL || lim_states[0] != NULL)
1018 if (! REG_VALID_INDEX (match_last))
1023 } while (mctx->state_log[match_last] == NULL
1024 || !mctx->state_log[match_last]->halt);
1025 halt_node = check_halt_state_context (mctx,
1026 mctx->state_log[match_last],
1029 ret = merge_state_array (dfa, sifted_states, lim_states,
1031 re_free (lim_states);
1033 if (BE (ret != REG_NOERROR, 0))
1038 sift_ctx_init (&sctx, sifted_states, lim_states, halt_node, match_last);
1039 ret = sift_states_backward (mctx, &sctx);
1040 re_node_set_free (&sctx.limits);
1041 if (BE (ret != REG_NOERROR, 0))
1043 if (sifted_states[0] == NULL)
1049 re_free (mctx->state_log);
1050 mctx->state_log = sifted_states;
1051 sifted_states = NULL;
1052 mctx->last_node = halt_node;
1053 mctx->match_last = match_last;
1056 re_free (sifted_states);
1057 re_free (lim_states);
1061 /* Acquire an initial state and return it.
1062 We must select appropriate initial state depending on the context,
1063 since initial states may have constraints like "\<", "^", etc.. */
1065 static inline re_dfastate_t *
1066 __attribute ((always_inline)) internal_function
1067 acquire_init_state_context (reg_errcode_t *err, const re_match_context_t *mctx,
1070 const re_dfa_t *const dfa = mctx->dfa;
1071 if (dfa->init_state->has_constraint)
1073 unsigned int context;
1074 context = re_string_context_at (&mctx->input, idx - 1, mctx->eflags);
1075 if (IS_WORD_CONTEXT (context))
1076 return dfa->init_state_word;
1077 else if (IS_ORDINARY_CONTEXT (context))
1078 return dfa->init_state;
1079 else if (IS_BEGBUF_CONTEXT (context) && IS_NEWLINE_CONTEXT (context))
1080 return dfa->init_state_begbuf;
1081 else if (IS_NEWLINE_CONTEXT (context))
1082 return dfa->init_state_nl;
1083 else if (IS_BEGBUF_CONTEXT (context))
1085 /* It is relatively rare case, then calculate on demand. */
1086 return re_acquire_state_context (err, dfa,
1087 dfa->init_state->entrance_nodes,
1091 /* Must not happen? */
1092 return dfa->init_state;
1095 return dfa->init_state;
1098 /* Check whether the regular expression match input string INPUT or not,
1099 and return the index where the matching end. Return REG_MISSING if
1100 there is no match, and return REG_ERROR in case of an error.
1101 FL_LONGEST_MATCH means we want the POSIX longest matching.
1102 If P_MATCH_FIRST is not NULL, and the match fails, it is set to the
1103 next place where we may want to try matching.
1104 Note that the matcher assumes that the matching starts from the current
1105 index of the buffer. */
1108 internal_function __attribute_warn_unused_result__
1109 check_matching (re_match_context_t *mctx, bool fl_longest_match,
1112 const re_dfa_t *const dfa = mctx->dfa;
1115 Idx match_last = REG_MISSING;
1116 Idx cur_str_idx = re_string_cur_idx (&mctx->input);
1117 re_dfastate_t *cur_state;
1118 bool at_init_state = p_match_first != NULL;
1119 Idx next_start_idx = cur_str_idx;
1122 cur_state = acquire_init_state_context (&err, mctx, cur_str_idx);
1123 /* An initial state must not be NULL (invalid). */
1124 if (BE (cur_state == NULL, 0))
1126 assert (err == REG_ESPACE);
1130 if (mctx->state_log != NULL)
1132 mctx->state_log[cur_str_idx] = cur_state;
1134 /* Check OP_OPEN_SUBEXP in the initial state in case that we use them
1135 later. E.g. Processing back references. */
1136 if (BE (dfa->nbackref, 0))
1138 at_init_state = false;
1139 err = check_subexp_matching_top (mctx, &cur_state->nodes, 0);
1140 if (BE (err != REG_NOERROR, 0))
1143 if (cur_state->has_backref)
1145 err = transit_state_bkref (mctx, &cur_state->nodes);
1146 if (BE (err != REG_NOERROR, 0))
1152 /* If the RE accepts NULL string. */
1153 if (BE (cur_state->halt, 0))
1155 if (!cur_state->has_constraint
1156 || check_halt_state_context (mctx, cur_state, cur_str_idx))
1158 if (!fl_longest_match)
1162 match_last = cur_str_idx;
1168 while (!re_string_eoi (&mctx->input))
1170 re_dfastate_t *old_state = cur_state;
1171 Idx next_char_idx = re_string_cur_idx (&mctx->input) + 1;
1173 if ((BE (next_char_idx >= mctx->input.bufs_len, 0)
1174 && mctx->input.bufs_len < mctx->input.len)
1175 || (BE (next_char_idx >= mctx->input.valid_len, 0)
1176 && mctx->input.valid_len < mctx->input.len))
1178 err = extend_buffers (mctx);
1179 if (BE (err != REG_NOERROR, 0))
1181 assert (err == REG_ESPACE);
1186 cur_state = transit_state (&err, mctx, cur_state);
1187 if (mctx->state_log != NULL)
1188 cur_state = merge_state_with_log (&err, mctx, cur_state);
1190 if (cur_state == NULL)
1192 /* Reached the invalid state or an error. Try to recover a valid
1193 state using the state log, if available and if we have not
1194 already found a valid (even if not the longest) match. */
1195 if (BE (err != REG_NOERROR, 0))
1198 if (mctx->state_log == NULL
1199 || (match && !fl_longest_match)
1200 || (cur_state = find_recover_state (&err, mctx)) == NULL)
1204 if (BE (at_init_state, 0))
1206 if (old_state == cur_state)
1207 next_start_idx = next_char_idx;
1209 at_init_state = false;
1212 if (cur_state->halt)
1214 /* Reached a halt state.
1215 Check the halt state can satisfy the current context. */
1216 if (!cur_state->has_constraint
1217 || check_halt_state_context (mctx, cur_state,
1218 re_string_cur_idx (&mctx->input)))
1220 /* We found an appropriate halt state. */
1221 match_last = re_string_cur_idx (&mctx->input);
1224 /* We found a match, do not modify match_first below. */
1225 p_match_first = NULL;
1226 if (!fl_longest_match)
1233 *p_match_first += next_start_idx;
1238 /* Check NODE match the current context. */
1242 check_halt_node_context (const re_dfa_t *dfa, Idx node, unsigned int context)
1244 re_token_type_t type = dfa->nodes[node].type;
1245 unsigned int constraint = dfa->nodes[node].constraint;
1246 if (type != END_OF_RE)
1250 if (NOT_SATISFY_NEXT_CONSTRAINT (constraint, context))
1255 /* Check the halt state STATE match the current context.
1256 Return 0 if not match, if the node, STATE has, is a halt node and
1257 match the context, return the node. */
1261 check_halt_state_context (const re_match_context_t *mctx,
1262 const re_dfastate_t *state, Idx idx)
1265 unsigned int context;
1267 assert (state->halt);
1269 context = re_string_context_at (&mctx->input, idx, mctx->eflags);
1270 for (i = 0; i < state->nodes.nelem; ++i)
1271 if (check_halt_node_context (mctx->dfa, state->nodes.elems[i], context))
1272 return state->nodes.elems[i];
1276 /* Compute the next node to which "NFA" transit from NODE("NFA" is a NFA
1277 corresponding to the DFA).
1278 Return the destination node, and update EPS_VIA_NODES;
1279 return REG_MISSING in case of errors. */
1283 proceed_next_node (const re_match_context_t *mctx, Idx nregs, regmatch_t *regs,
1284 Idx *pidx, Idx node, re_node_set *eps_via_nodes,
1285 struct re_fail_stack_t *fs)
1287 const re_dfa_t *const dfa = mctx->dfa;
1290 if (IS_EPSILON_NODE (dfa->nodes[node].type))
1292 re_node_set *cur_nodes = &mctx->state_log[*pidx]->nodes;
1293 re_node_set *edests = &dfa->edests[node];
1295 ok = re_node_set_insert (eps_via_nodes, node);
1298 /* Pick up a valid destination, or return REG_MISSING if none
1300 for (dest_node = REG_MISSING, i = 0; i < edests->nelem; ++i)
1302 Idx candidate = edests->elems[i];
1303 if (!re_node_set_contains (cur_nodes, candidate))
1305 if (dest_node == REG_MISSING)
1306 dest_node = candidate;
1310 /* In order to avoid infinite loop like "(a*)*", return the second
1311 epsilon-transition if the first was already considered. */
1312 if (re_node_set_contains (eps_via_nodes, dest_node))
1315 /* Otherwise, push the second epsilon-transition on the fail stack. */
1317 && push_fail_stack (fs, *pidx, candidate, nregs, regs,
1321 /* We know we are going to exit. */
1330 re_token_type_t type = dfa->nodes[node].type;
1332 #ifdef RE_ENABLE_I18N
1333 if (dfa->nodes[node].accept_mb)
1334 naccepted = check_node_accept_bytes (dfa, node, &mctx->input, *pidx);
1336 #endif /* RE_ENABLE_I18N */
1337 if (type == OP_BACK_REF)
1339 Idx subexp_idx = dfa->nodes[node].opr.idx + 1;
1340 naccepted = regs[subexp_idx].rm_eo - regs[subexp_idx].rm_so;
1343 if (regs[subexp_idx].rm_so == -1 || regs[subexp_idx].rm_eo == -1)
1347 char *buf = (char *) re_string_get_buffer (&mctx->input);
1348 if (memcmp (buf + regs[subexp_idx].rm_so, buf + *pidx,
1357 ok = re_node_set_insert (eps_via_nodes, node);
1360 dest_node = dfa->edests[node].elems[0];
1361 if (re_node_set_contains (&mctx->state_log[*pidx]->nodes,
1368 || check_node_accept (mctx, dfa->nodes + node, *pidx))
1370 Idx dest_node = dfa->nexts[node];
1371 *pidx = (naccepted == 0) ? *pidx + 1 : *pidx + naccepted;
1372 if (fs && (*pidx > mctx->match_last || mctx->state_log[*pidx] == NULL
1373 || !re_node_set_contains (&mctx->state_log[*pidx]->nodes,
1376 re_node_set_empty (eps_via_nodes);
1383 static reg_errcode_t
1384 internal_function __attribute_warn_unused_result__
1385 push_fail_stack (struct re_fail_stack_t *fs, Idx str_idx, Idx dest_node,
1386 Idx nregs, regmatch_t *regs, re_node_set *eps_via_nodes)
1389 Idx num = fs->num++;
1390 if (fs->num == fs->alloc)
1392 struct re_fail_stack_ent_t *new_array;
1393 new_array = realloc (fs->stack, (sizeof (struct re_fail_stack_ent_t)
1395 if (new_array == NULL)
1398 fs->stack = new_array;
1400 fs->stack[num].idx = str_idx;
1401 fs->stack[num].node = dest_node;
1402 fs->stack[num].regs = re_malloc (regmatch_t, nregs);
1403 if (fs->stack[num].regs == NULL)
1405 memcpy (fs->stack[num].regs, regs, sizeof (regmatch_t) * nregs);
1406 err = re_node_set_init_copy (&fs->stack[num].eps_via_nodes, eps_via_nodes);
1412 pop_fail_stack (struct re_fail_stack_t *fs, Idx *pidx, Idx nregs,
1413 regmatch_t *regs, re_node_set *eps_via_nodes)
1415 Idx num = --fs->num;
1416 assert (REG_VALID_INDEX (num));
1417 *pidx = fs->stack[num].idx;
1418 memcpy (regs, fs->stack[num].regs, sizeof (regmatch_t) * nregs);
1419 re_node_set_free (eps_via_nodes);
1420 re_free (fs->stack[num].regs);
1421 *eps_via_nodes = fs->stack[num].eps_via_nodes;
1422 return fs->stack[num].node;
1425 /* Set the positions where the subexpressions are starts/ends to registers
1427 Note: We assume that pmatch[0] is already set, and
1428 pmatch[i].rm_so == pmatch[i].rm_eo == -1 for 0 < i < nmatch. */
1430 static reg_errcode_t
1431 internal_function __attribute_warn_unused_result__
1432 set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
1433 regmatch_t *pmatch, bool fl_backtrack)
1435 const re_dfa_t *dfa = preg->buffer;
1437 re_node_set eps_via_nodes;
1438 struct re_fail_stack_t *fs;
1439 struct re_fail_stack_t fs_body = { 0, 2, NULL };
1440 regmatch_t *prev_idx_match;
1441 bool prev_idx_match_malloced = false;
1444 assert (nmatch > 1);
1445 assert (mctx->state_log != NULL);
1450 fs->stack = re_malloc (struct re_fail_stack_ent_t, fs->alloc);
1451 if (fs->stack == NULL)
1457 cur_node = dfa->init_node;
1458 re_node_set_init_empty (&eps_via_nodes);
1460 if (__libc_use_alloca (nmatch * sizeof (regmatch_t)))
1461 prev_idx_match = (regmatch_t *) alloca (nmatch * sizeof (regmatch_t));
1464 prev_idx_match = re_malloc (regmatch_t, nmatch);
1465 if (prev_idx_match == NULL)
1467 free_fail_stack_return (fs);
1470 prev_idx_match_malloced = true;
1472 memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
1474 for (idx = pmatch[0].rm_so; idx <= pmatch[0].rm_eo ;)
1476 update_regs (dfa, pmatch, prev_idx_match, cur_node, idx, nmatch);
1478 if (idx == pmatch[0].rm_eo && cur_node == mctx->last_node)
1483 for (reg_idx = 0; reg_idx < nmatch; ++reg_idx)
1484 if (pmatch[reg_idx].rm_so > -1 && pmatch[reg_idx].rm_eo == -1)
1486 if (reg_idx == nmatch)
1488 re_node_set_free (&eps_via_nodes);
1489 if (prev_idx_match_malloced)
1490 re_free (prev_idx_match);
1491 return free_fail_stack_return (fs);
1493 cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
1498 re_node_set_free (&eps_via_nodes);
1499 if (prev_idx_match_malloced)
1500 re_free (prev_idx_match);
1505 /* Proceed to next node. */
1506 cur_node = proceed_next_node (mctx, nmatch, pmatch, &idx, cur_node,
1507 &eps_via_nodes, fs);
1509 if (BE (! REG_VALID_INDEX (cur_node), 0))
1511 if (BE (cur_node == REG_ERROR, 0))
1513 re_node_set_free (&eps_via_nodes);
1514 if (prev_idx_match_malloced)
1515 re_free (prev_idx_match);
1516 free_fail_stack_return (fs);
1520 cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
1524 re_node_set_free (&eps_via_nodes);
1525 if (prev_idx_match_malloced)
1526 re_free (prev_idx_match);
1531 re_node_set_free (&eps_via_nodes);
1532 if (prev_idx_match_malloced)
1533 re_free (prev_idx_match);
1534 return free_fail_stack_return (fs);
1537 static reg_errcode_t
1539 free_fail_stack_return (struct re_fail_stack_t *fs)
1544 for (fs_idx = 0; fs_idx < fs->num; ++fs_idx)
1546 re_node_set_free (&fs->stack[fs_idx].eps_via_nodes);
1547 re_free (fs->stack[fs_idx].regs);
1549 re_free (fs->stack);
1556 update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
1557 regmatch_t *prev_idx_match, Idx cur_node, Idx cur_idx, Idx nmatch)
1559 int type = dfa->nodes[cur_node].type;
1560 if (type == OP_OPEN_SUBEXP)
1562 Idx reg_num = dfa->nodes[cur_node].opr.idx + 1;
1564 /* We are at the first node of this sub expression. */
1565 if (reg_num < nmatch)
1567 pmatch[reg_num].rm_so = cur_idx;
1568 pmatch[reg_num].rm_eo = -1;
1571 else if (type == OP_CLOSE_SUBEXP)
1573 Idx reg_num = dfa->nodes[cur_node].opr.idx + 1;
1574 if (reg_num < nmatch)
1576 /* We are at the last node of this sub expression. */
1577 if (pmatch[reg_num].rm_so < cur_idx)
1579 pmatch[reg_num].rm_eo = cur_idx;
1580 /* This is a non-empty match or we are not inside an optional
1581 subexpression. Accept this right away. */
1582 memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
1586 if (dfa->nodes[cur_node].opt_subexp
1587 && prev_idx_match[reg_num].rm_so != -1)
1588 /* We transited through an empty match for an optional
1589 subexpression, like (a?)*, and this is not the subexp's
1590 first match. Copy back the old content of the registers
1591 so that matches of an inner subexpression are undone as
1592 well, like in ((a?))*. */
1593 memcpy (pmatch, prev_idx_match, sizeof (regmatch_t) * nmatch);
1595 /* We completed a subexpression, but it may be part of
1596 an optional one, so do not update PREV_IDX_MATCH. */
1597 pmatch[reg_num].rm_eo = cur_idx;
1603 /* This function checks the STATE_LOG from the SCTX->last_str_idx to 0
1604 and sift the nodes in each states according to the following rules.
1605 Updated state_log will be wrote to STATE_LOG.
1607 Rules: We throw away the Node 'a' in the STATE_LOG[STR_IDX] if...
1608 1. When STR_IDX == MATCH_LAST(the last index in the state_log):
1609 If 'a' isn't the LAST_NODE and 'a' can't epsilon transit to
1610 the LAST_NODE, we throw away the node 'a'.
1611 2. When 0 <= STR_IDX < MATCH_LAST and 'a' accepts
1612 string 's' and transit to 'b':
1613 i. If 'b' isn't in the STATE_LOG[STR_IDX+strlen('s')], we throw
1615 ii. If 'b' is in the STATE_LOG[STR_IDX+strlen('s')] but 'b' is
1616 thrown away, we throw away the node 'a'.
1617 3. When 0 <= STR_IDX < MATCH_LAST and 'a' epsilon transit to 'b':
1618 i. If 'b' isn't in the STATE_LOG[STR_IDX], we throw away the
1620 ii. If 'b' is in the STATE_LOG[STR_IDX] but 'b' is thrown away,
1621 we throw away the node 'a'. */
1623 #define STATE_NODE_CONTAINS(state,node) \
1624 ((state) != NULL && re_node_set_contains (&(state)->nodes, node))
1626 static reg_errcode_t
1628 sift_states_backward (const re_match_context_t *mctx, re_sift_context_t *sctx)
1632 Idx str_idx = sctx->last_str_idx;
1633 re_node_set cur_dest;
1636 assert (mctx->state_log != NULL && mctx->state_log[str_idx] != NULL);
1639 /* Build sifted state_log[str_idx]. It has the nodes which can epsilon
1640 transit to the last_node and the last_node itself. */
1641 err = re_node_set_init_1 (&cur_dest, sctx->last_node);
1642 if (BE (err != REG_NOERROR, 0))
1644 err = update_cur_sifted_state (mctx, sctx, str_idx, &cur_dest);
1645 if (BE (err != REG_NOERROR, 0))
1648 /* Then check each states in the state_log. */
1651 /* Update counters. */
1652 null_cnt = (sctx->sifted_states[str_idx] == NULL) ? null_cnt + 1 : 0;
1653 if (null_cnt > mctx->max_mb_elem_len)
1655 memset (sctx->sifted_states, '\0',
1656 sizeof (re_dfastate_t *) * str_idx);
1657 re_node_set_free (&cur_dest);
1660 re_node_set_empty (&cur_dest);
1663 if (mctx->state_log[str_idx])
1665 err = build_sifted_states (mctx, sctx, str_idx, &cur_dest);
1666 if (BE (err != REG_NOERROR, 0))
1670 /* Add all the nodes which satisfy the following conditions:
1671 - It can epsilon transit to a node in CUR_DEST.
1673 And update state_log. */
1674 err = update_cur_sifted_state (mctx, sctx, str_idx, &cur_dest);
1675 if (BE (err != REG_NOERROR, 0))
1680 re_node_set_free (&cur_dest);
1684 static reg_errcode_t
1685 internal_function __attribute_warn_unused_result__
1686 build_sifted_states (const re_match_context_t *mctx, re_sift_context_t *sctx,
1687 Idx str_idx, re_node_set *cur_dest)
1689 const re_dfa_t *const dfa = mctx->dfa;
1690 const re_node_set *cur_src = &mctx->state_log[str_idx]->non_eps_nodes;
1693 /* Then build the next sifted state.
1694 We build the next sifted state on 'cur_dest', and update
1695 'sifted_states[str_idx]' with 'cur_dest'.
1697 'cur_dest' is the sifted state from 'state_log[str_idx + 1]'.
1698 'cur_src' points the node_set of the old 'state_log[str_idx]'
1699 (with the epsilon nodes pre-filtered out). */
1700 for (i = 0; i < cur_src->nelem; i++)
1702 Idx prev_node = cur_src->elems[i];
1707 re_token_type_t type = dfa->nodes[prev_node].type;
1708 assert (!IS_EPSILON_NODE (type));
1710 #ifdef RE_ENABLE_I18N
1711 /* If the node may accept "multi byte". */
1712 if (dfa->nodes[prev_node].accept_mb)
1713 naccepted = sift_states_iter_mb (mctx, sctx, prev_node,
1714 str_idx, sctx->last_str_idx);
1715 #endif /* RE_ENABLE_I18N */
1717 /* We don't check backreferences here.
1718 See update_cur_sifted_state(). */
1720 && check_node_accept (mctx, dfa->nodes + prev_node, str_idx)
1721 && STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + 1],
1722 dfa->nexts[prev_node]))
1728 if (sctx->limits.nelem)
1730 Idx to_idx = str_idx + naccepted;
1731 if (check_dst_limits (mctx, &sctx->limits,
1732 dfa->nexts[prev_node], to_idx,
1733 prev_node, str_idx))
1736 ok = re_node_set_insert (cur_dest, prev_node);
1744 /* Helper functions. */
1746 static reg_errcode_t
1748 clean_state_log_if_needed (re_match_context_t *mctx, Idx next_state_log_idx)
1750 Idx top = mctx->state_log_top;
1752 if ((next_state_log_idx >= mctx->input.bufs_len
1753 && mctx->input.bufs_len < mctx->input.len)
1754 || (next_state_log_idx >= mctx->input.valid_len
1755 && mctx->input.valid_len < mctx->input.len))
1758 err = extend_buffers (mctx);
1759 if (BE (err != REG_NOERROR, 0))
1763 if (top < next_state_log_idx)
1765 memset (mctx->state_log + top + 1, '\0',
1766 sizeof (re_dfastate_t *) * (next_state_log_idx - top));
1767 mctx->state_log_top = next_state_log_idx;
1772 static reg_errcode_t
1774 merge_state_array (const re_dfa_t *dfa, re_dfastate_t **dst,
1775 re_dfastate_t **src, Idx num)
1779 for (st_idx = 0; st_idx < num; ++st_idx)
1781 if (dst[st_idx] == NULL)
1782 dst[st_idx] = src[st_idx];
1783 else if (src[st_idx] != NULL)
1785 re_node_set merged_set;
1786 err = re_node_set_init_union (&merged_set, &dst[st_idx]->nodes,
1787 &src[st_idx]->nodes);
1788 if (BE (err != REG_NOERROR, 0))
1790 dst[st_idx] = re_acquire_state (&err, dfa, &merged_set);
1791 re_node_set_free (&merged_set);
1792 if (BE (err != REG_NOERROR, 0))
1799 static reg_errcode_t
1801 update_cur_sifted_state (const re_match_context_t *mctx,
1802 re_sift_context_t *sctx, Idx str_idx,
1803 re_node_set *dest_nodes)
1805 const re_dfa_t *const dfa = mctx->dfa;
1806 reg_errcode_t err = REG_NOERROR;
1807 const re_node_set *candidates;
1808 candidates = ((mctx->state_log[str_idx] == NULL) ? NULL
1809 : &mctx->state_log[str_idx]->nodes);
1811 if (dest_nodes->nelem == 0)
1812 sctx->sifted_states[str_idx] = NULL;
1817 /* At first, add the nodes which can epsilon transit to a node in
1819 err = add_epsilon_src_nodes (dfa, dest_nodes, candidates);
1820 if (BE (err != REG_NOERROR, 0))
1823 /* Then, check the limitations in the current sift_context. */
1824 if (sctx->limits.nelem)
1826 err = check_subexp_limits (dfa, dest_nodes, candidates, &sctx->limits,
1827 mctx->bkref_ents, str_idx);
1828 if (BE (err != REG_NOERROR, 0))
1833 sctx->sifted_states[str_idx] = re_acquire_state (&err, dfa, dest_nodes);
1834 if (BE (err != REG_NOERROR, 0))
1838 if (candidates && mctx->state_log[str_idx]->has_backref)
1840 err = sift_states_bkref (mctx, sctx, str_idx, candidates);
1841 if (BE (err != REG_NOERROR, 0))
1847 static reg_errcode_t
1848 internal_function __attribute_warn_unused_result__
1849 add_epsilon_src_nodes (const re_dfa_t *dfa, re_node_set *dest_nodes,
1850 const re_node_set *candidates)
1852 reg_errcode_t err = REG_NOERROR;
1855 re_dfastate_t *state = re_acquire_state (&err, dfa, dest_nodes);
1856 if (BE (err != REG_NOERROR, 0))
1859 if (!state->inveclosure.alloc)
1861 err = re_node_set_alloc (&state->inveclosure, dest_nodes->nelem);
1862 if (BE (err != REG_NOERROR, 0))
1864 for (i = 0; i < dest_nodes->nelem; i++)
1866 err = re_node_set_merge (&state->inveclosure,
1867 dfa->inveclosures + dest_nodes->elems[i]);
1868 if (BE (err != REG_NOERROR, 0))
1872 return re_node_set_add_intersect (dest_nodes, candidates,
1873 &state->inveclosure);
1876 static reg_errcode_t
1878 sub_epsilon_src_nodes (const re_dfa_t *dfa, Idx node, re_node_set *dest_nodes,
1879 const re_node_set *candidates)
1883 re_node_set *inv_eclosure = dfa->inveclosures + node;
1884 re_node_set except_nodes;
1885 re_node_set_init_empty (&except_nodes);
1886 for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx)
1888 Idx cur_node = inv_eclosure->elems[ecl_idx];
1889 if (cur_node == node)
1891 if (IS_EPSILON_NODE (dfa->nodes[cur_node].type))
1893 Idx edst1 = dfa->edests[cur_node].elems[0];
1894 Idx edst2 = ((dfa->edests[cur_node].nelem > 1)
1895 ? dfa->edests[cur_node].elems[1] : REG_MISSING);
1896 if ((!re_node_set_contains (inv_eclosure, edst1)
1897 && re_node_set_contains (dest_nodes, edst1))
1898 || (REG_VALID_NONZERO_INDEX (edst2)
1899 && !re_node_set_contains (inv_eclosure, edst2)
1900 && re_node_set_contains (dest_nodes, edst2)))
1902 err = re_node_set_add_intersect (&except_nodes, candidates,
1903 dfa->inveclosures + cur_node);
1904 if (BE (err != REG_NOERROR, 0))
1906 re_node_set_free (&except_nodes);
1912 for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx)
1914 Idx cur_node = inv_eclosure->elems[ecl_idx];
1915 if (!re_node_set_contains (&except_nodes, cur_node))
1917 Idx idx = re_node_set_contains (dest_nodes, cur_node) - 1;
1918 re_node_set_remove_at (dest_nodes, idx);
1921 re_node_set_free (&except_nodes);
1927 check_dst_limits (const re_match_context_t *mctx, const re_node_set *limits,
1928 Idx dst_node, Idx dst_idx, Idx src_node, Idx src_idx)
1930 const re_dfa_t *const dfa = mctx->dfa;
1931 Idx lim_idx, src_pos, dst_pos;
1933 Idx dst_bkref_idx = search_cur_bkref_entry (mctx, dst_idx);
1934 Idx src_bkref_idx = search_cur_bkref_entry (mctx, src_idx);
1935 for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx)
1938 struct re_backref_cache_entry *ent;
1939 ent = mctx->bkref_ents + limits->elems[lim_idx];
1940 subexp_idx = dfa->nodes[ent->node].opr.idx;
1942 dst_pos = check_dst_limits_calc_pos (mctx, limits->elems[lim_idx],
1943 subexp_idx, dst_node, dst_idx,
1945 src_pos = check_dst_limits_calc_pos (mctx, limits->elems[lim_idx],
1946 subexp_idx, src_node, src_idx,
1950 <src> <dst> ( <subexp> )
1951 ( <subexp> ) <src> <dst>
1952 ( <subexp1> <src> <subexp2> <dst> <subexp3> ) */
1953 if (src_pos == dst_pos)
1954 continue; /* This is unrelated limitation. */
1963 check_dst_limits_calc_pos_1 (const re_match_context_t *mctx, int boundaries,
1964 Idx subexp_idx, Idx from_node, Idx bkref_idx)
1966 const re_dfa_t *const dfa = mctx->dfa;
1967 const re_node_set *eclosures = dfa->eclosures + from_node;
1970 /* Else, we are on the boundary: examine the nodes on the epsilon
1972 for (node_idx = 0; node_idx < eclosures->nelem; ++node_idx)
1974 Idx node = eclosures->elems[node_idx];
1975 switch (dfa->nodes[node].type)
1978 if (bkref_idx != REG_MISSING)
1980 struct re_backref_cache_entry *ent = mctx->bkref_ents + bkref_idx;
1986 if (ent->node != node)
1989 if (subexp_idx < BITSET_WORD_BITS
1990 && !(ent->eps_reachable_subexps_map
1991 & ((bitset_word_t) 1 << subexp_idx)))
1994 /* Recurse trying to reach the OP_OPEN_SUBEXP and
1995 OP_CLOSE_SUBEXP cases below. But, if the
1996 destination node is the same node as the source
1997 node, don't recurse because it would cause an
1998 infinite loop: a regex that exhibits this behavior
2000 dst = dfa->edests[node].elems[0];
2001 if (dst == from_node)
2005 else /* if (boundaries & 2) */
2010 check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx,
2012 if (cpos == -1 /* && (boundaries & 1) */)
2014 if (cpos == 0 && (boundaries & 2))
2017 if (subexp_idx < BITSET_WORD_BITS)
2018 ent->eps_reachable_subexps_map
2019 &= ~((bitset_word_t) 1 << subexp_idx);
2021 while (ent++->more);
2025 case OP_OPEN_SUBEXP:
2026 if ((boundaries & 1) && subexp_idx == dfa->nodes[node].opr.idx)
2030 case OP_CLOSE_SUBEXP:
2031 if ((boundaries & 2) && subexp_idx == dfa->nodes[node].opr.idx)
2040 return (boundaries & 2) ? 1 : 0;
2045 check_dst_limits_calc_pos (const re_match_context_t *mctx, Idx limit,
2046 Idx subexp_idx, Idx from_node, Idx str_idx,
2049 struct re_backref_cache_entry *lim = mctx->bkref_ents + limit;
2052 /* If we are outside the range of the subexpression, return -1 or 1. */
2053 if (str_idx < lim->subexp_from)
2056 if (lim->subexp_to < str_idx)
2059 /* If we are within the subexpression, return 0. */
2060 boundaries = (str_idx == lim->subexp_from);
2061 boundaries |= (str_idx == lim->subexp_to) << 1;
2062 if (boundaries == 0)
2065 /* Else, examine epsilon closure. */
2066 return check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx,
2067 from_node, bkref_idx);
2070 /* Check the limitations of sub expressions LIMITS, and remove the nodes
2071 which are against limitations from DEST_NODES. */
2073 static reg_errcode_t
2075 check_subexp_limits (const re_dfa_t *dfa, re_node_set *dest_nodes,
2076 const re_node_set *candidates, re_node_set *limits,
2077 struct re_backref_cache_entry *bkref_ents, Idx str_idx)
2080 Idx node_idx, lim_idx;
2082 for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx)
2085 struct re_backref_cache_entry *ent;
2086 ent = bkref_ents + limits->elems[lim_idx];
2088 if (str_idx <= ent->subexp_from || ent->str_idx < str_idx)
2089 continue; /* This is unrelated limitation. */
2091 subexp_idx = dfa->nodes[ent->node].opr.idx;
2092 if (ent->subexp_to == str_idx)
2094 Idx ops_node = REG_MISSING;
2095 Idx cls_node = REG_MISSING;
2096 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2098 Idx node = dest_nodes->elems[node_idx];
2099 re_token_type_t type = dfa->nodes[node].type;
2100 if (type == OP_OPEN_SUBEXP
2101 && subexp_idx == dfa->nodes[node].opr.idx)
2103 else if (type == OP_CLOSE_SUBEXP
2104 && subexp_idx == dfa->nodes[node].opr.idx)
2108 /* Check the limitation of the open subexpression. */
2109 /* Note that (ent->subexp_to = str_idx != ent->subexp_from). */
2110 if (REG_VALID_INDEX (ops_node))
2112 err = sub_epsilon_src_nodes (dfa, ops_node, dest_nodes,
2114 if (BE (err != REG_NOERROR, 0))
2118 /* Check the limitation of the close subexpression. */
2119 if (REG_VALID_INDEX (cls_node))
2120 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2122 Idx node = dest_nodes->elems[node_idx];
2123 if (!re_node_set_contains (dfa->inveclosures + node,
2125 && !re_node_set_contains (dfa->eclosures + node,
2128 /* It is against this limitation.
2129 Remove it form the current sifted state. */
2130 err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2132 if (BE (err != REG_NOERROR, 0))
2138 else /* (ent->subexp_to != str_idx) */
2140 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2142 Idx node = dest_nodes->elems[node_idx];
2143 re_token_type_t type = dfa->nodes[node].type;
2144 if (type == OP_CLOSE_SUBEXP || type == OP_OPEN_SUBEXP)
2146 if (subexp_idx != dfa->nodes[node].opr.idx)
2148 /* It is against this limitation.
2149 Remove it form the current sifted state. */
2150 err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2152 if (BE (err != REG_NOERROR, 0))
2161 static reg_errcode_t
2162 internal_function __attribute_warn_unused_result__
2163 sift_states_bkref (const re_match_context_t *mctx, re_sift_context_t *sctx,
2164 Idx str_idx, const re_node_set *candidates)
2166 const re_dfa_t *const dfa = mctx->dfa;
2169 re_sift_context_t local_sctx;
2170 Idx first_idx = search_cur_bkref_entry (mctx, str_idx);
2172 if (first_idx == REG_MISSING)
2175 local_sctx.sifted_states = NULL; /* Mark that it hasn't been initialized. */
2177 for (node_idx = 0; node_idx < candidates->nelem; ++node_idx)
2180 re_token_type_t type;
2181 struct re_backref_cache_entry *entry;
2182 node = candidates->elems[node_idx];
2183 type = dfa->nodes[node].type;
2184 /* Avoid infinite loop for the REs like "()\1+". */
2185 if (node == sctx->last_node && str_idx == sctx->last_str_idx)
2187 if (type != OP_BACK_REF)
2190 entry = mctx->bkref_ents + first_idx;
2191 enabled_idx = first_idx;
2198 re_dfastate_t *cur_state;
2200 if (entry->node != node)
2202 subexp_len = entry->subexp_to - entry->subexp_from;
2203 to_idx = str_idx + subexp_len;
2204 dst_node = (subexp_len ? dfa->nexts[node]
2205 : dfa->edests[node].elems[0]);
2207 if (to_idx > sctx->last_str_idx
2208 || sctx->sifted_states[to_idx] == NULL
2209 || !STATE_NODE_CONTAINS (sctx->sifted_states[to_idx], dst_node)
2210 || check_dst_limits (mctx, &sctx->limits, node,
2211 str_idx, dst_node, to_idx))
2214 if (local_sctx.sifted_states == NULL)
2217 err = re_node_set_init_copy (&local_sctx.limits, &sctx->limits);
2218 if (BE (err != REG_NOERROR, 0))
2221 local_sctx.last_node = node;
2222 local_sctx.last_str_idx = str_idx;
2223 ok = re_node_set_insert (&local_sctx.limits, enabled_idx);
2229 cur_state = local_sctx.sifted_states[str_idx];
2230 err = sift_states_backward (mctx, &local_sctx);
2231 if (BE (err != REG_NOERROR, 0))
2233 if (sctx->limited_states != NULL)
2235 err = merge_state_array (dfa, sctx->limited_states,
2236 local_sctx.sifted_states,
2238 if (BE (err != REG_NOERROR, 0))
2241 local_sctx.sifted_states[str_idx] = cur_state;
2242 re_node_set_remove (&local_sctx.limits, enabled_idx);
2244 /* mctx->bkref_ents may have changed, reload the pointer. */
2245 entry = mctx->bkref_ents + enabled_idx;
2247 while (enabled_idx++, entry++->more);
2251 if (local_sctx.sifted_states != NULL)
2253 re_node_set_free (&local_sctx.limits);
2260 #ifdef RE_ENABLE_I18N
2263 sift_states_iter_mb (const re_match_context_t *mctx, re_sift_context_t *sctx,
2264 Idx node_idx, Idx str_idx, Idx max_str_idx)
2266 const re_dfa_t *const dfa = mctx->dfa;
2268 /* Check the node can accept "multi byte". */
2269 naccepted = check_node_accept_bytes (dfa, node_idx, &mctx->input, str_idx);
2270 if (naccepted > 0 && str_idx + naccepted <= max_str_idx &&
2271 !STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + naccepted],
2272 dfa->nexts[node_idx]))
2273 /* The node can't accept the "multi byte", or the
2274 destination was already thrown away, then the node
2275 could't accept the current input "multi byte". */
2277 /* Otherwise, it is sure that the node could accept
2278 'naccepted' bytes input. */
2281 #endif /* RE_ENABLE_I18N */
2284 /* Functions for state transition. */
2286 /* Return the next state to which the current state STATE will transit by
2287 accepting the current input byte, and update STATE_LOG if necessary.
2288 If STATE can accept a multibyte char/collating element/back reference
2289 update the destination of STATE_LOG. */
2291 static re_dfastate_t *
2292 internal_function __attribute_warn_unused_result__
2293 transit_state (reg_errcode_t *err, re_match_context_t *mctx,
2294 re_dfastate_t *state)
2296 re_dfastate_t **trtable;
2299 #ifdef RE_ENABLE_I18N
2300 /* If the current state can accept multibyte. */
2301 if (BE (state->accept_mb, 0))
2303 *err = transit_state_mb (mctx, state);
2304 if (BE (*err != REG_NOERROR, 0))
2307 #endif /* RE_ENABLE_I18N */
2309 /* Then decide the next state with the single byte. */
2312 /* don't use transition table */
2313 return transit_state_sb (err, mctx, state);
2316 /* Use transition table */
2317 ch = re_string_fetch_byte (&mctx->input);
2320 trtable = state->trtable;
2321 if (BE (trtable != NULL, 1))
2324 trtable = state->word_trtable;
2325 if (BE (trtable != NULL, 1))
2327 unsigned int context;
2329 = re_string_context_at (&mctx->input,
2330 re_string_cur_idx (&mctx->input) - 1,
2332 if (IS_WORD_CONTEXT (context))
2333 return trtable[ch + SBC_MAX];
2338 if (!build_trtable (mctx->dfa, state))
2344 /* Retry, we now have a transition table. */
2348 /* Update the state_log if we need */
2349 static re_dfastate_t *
2351 merge_state_with_log (reg_errcode_t *err, re_match_context_t *mctx,
2352 re_dfastate_t *next_state)
2354 const re_dfa_t *const dfa = mctx->dfa;
2355 Idx cur_idx = re_string_cur_idx (&mctx->input);
2357 if (cur_idx > mctx->state_log_top)
2359 mctx->state_log[cur_idx] = next_state;
2360 mctx->state_log_top = cur_idx;
2362 else if (mctx->state_log[cur_idx] == 0)
2364 mctx->state_log[cur_idx] = next_state;
2368 re_dfastate_t *pstate;
2369 unsigned int context;
2370 re_node_set next_nodes, *log_nodes, *table_nodes = NULL;
2371 /* If (state_log[cur_idx] != 0), it implies that cur_idx is
2372 the destination of a multibyte char/collating element/
2373 back reference. Then the next state is the union set of
2374 these destinations and the results of the transition table. */
2375 pstate = mctx->state_log[cur_idx];
2376 log_nodes = pstate->entrance_nodes;
2377 if (next_state != NULL)
2379 table_nodes = next_state->entrance_nodes;
2380 *err = re_node_set_init_union (&next_nodes, table_nodes,
2382 if (BE (*err != REG_NOERROR, 0))
2386 next_nodes = *log_nodes;
2387 /* Note: We already add the nodes of the initial state,
2388 then we don't need to add them here. */
2390 context = re_string_context_at (&mctx->input,
2391 re_string_cur_idx (&mctx->input) - 1,
2393 next_state = mctx->state_log[cur_idx]
2394 = re_acquire_state_context (err, dfa, &next_nodes, context);
2395 /* We don't need to check errors here, since the return value of
2396 this function is next_state and ERR is already set. */
2398 if (table_nodes != NULL)
2399 re_node_set_free (&next_nodes);
2402 if (BE (dfa->nbackref, 0) && next_state != NULL)
2404 /* Check OP_OPEN_SUBEXP in the current state in case that we use them
2405 later. We must check them here, since the back references in the
2406 next state might use them. */
2407 *err = check_subexp_matching_top (mctx, &next_state->nodes,
2409 if (BE (*err != REG_NOERROR, 0))
2412 /* If the next state has back references. */
2413 if (next_state->has_backref)
2415 *err = transit_state_bkref (mctx, &next_state->nodes);
2416 if (BE (*err != REG_NOERROR, 0))
2418 next_state = mctx->state_log[cur_idx];
2425 /* Skip bytes in the input that correspond to part of a
2426 multi-byte match, then look in the log for a state
2427 from which to restart matching. */
2428 static re_dfastate_t *
2430 find_recover_state (reg_errcode_t *err, re_match_context_t *mctx)
2432 re_dfastate_t *cur_state;
2435 Idx max = mctx->state_log_top;
2436 Idx cur_str_idx = re_string_cur_idx (&mctx->input);
2440 if (++cur_str_idx > max)
2442 re_string_skip_bytes (&mctx->input, 1);
2444 while (mctx->state_log[cur_str_idx] == NULL);
2446 cur_state = merge_state_with_log (err, mctx, NULL);
2448 while (*err == REG_NOERROR && cur_state == NULL);
2452 /* Helper functions for transit_state. */
2454 /* From the node set CUR_NODES, pick up the nodes whose types are
2455 OP_OPEN_SUBEXP and which have corresponding back references in the regular
2456 expression. And register them to use them later for evaluating the
2457 corresponding back references. */
2459 static reg_errcode_t
2461 check_subexp_matching_top (re_match_context_t *mctx, re_node_set *cur_nodes,
2464 const re_dfa_t *const dfa = mctx->dfa;
2468 /* TODO: This isn't efficient.
2469 Because there might be more than one nodes whose types are
2470 OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
2473 for (node_idx = 0; node_idx < cur_nodes->nelem; ++node_idx)
2475 Idx node = cur_nodes->elems[node_idx];
2476 if (dfa->nodes[node].type == OP_OPEN_SUBEXP
2477 && dfa->nodes[node].opr.idx < BITSET_WORD_BITS
2478 && (dfa->used_bkref_map
2479 & ((bitset_word_t) 1 << dfa->nodes[node].opr.idx)))
2481 err = match_ctx_add_subtop (mctx, node, str_idx);
2482 if (BE (err != REG_NOERROR, 0))
2490 /* Return the next state to which the current state STATE will transit by
2491 accepting the current input byte. */
2493 static re_dfastate_t *
2494 transit_state_sb (reg_errcode_t *err, re_match_context_t *mctx,
2495 re_dfastate_t *state)
2497 const re_dfa_t *const dfa = mctx->dfa;
2498 re_node_set next_nodes;
2499 re_dfastate_t *next_state;
2500 Idx node_cnt, cur_str_idx = re_string_cur_idx (&mctx->input);
2501 unsigned int context;
2503 *err = re_node_set_alloc (&next_nodes, state->nodes.nelem + 1);
2504 if (BE (*err != REG_NOERROR, 0))
2506 for (node_cnt = 0; node_cnt < state->nodes.nelem; ++node_cnt)
2508 Idx cur_node = state->nodes.elems[node_cnt];
2509 if (check_node_accept (mctx, dfa->nodes + cur_node, cur_str_idx))
2511 *err = re_node_set_merge (&next_nodes,
2512 dfa->eclosures + dfa->nexts[cur_node]);
2513 if (BE (*err != REG_NOERROR, 0))
2515 re_node_set_free (&next_nodes);
2520 context = re_string_context_at (&mctx->input, cur_str_idx, mctx->eflags);
2521 next_state = re_acquire_state_context (err, dfa, &next_nodes, context);
2522 /* We don't need to check errors here, since the return value of
2523 this function is next_state and ERR is already set. */
2525 re_node_set_free (&next_nodes);
2526 re_string_skip_bytes (&mctx->input, 1);
2531 #ifdef RE_ENABLE_I18N
2532 static reg_errcode_t
2534 transit_state_mb (re_match_context_t *mctx, re_dfastate_t *pstate)
2536 const re_dfa_t *const dfa = mctx->dfa;
2540 for (i = 0; i < pstate->nodes.nelem; ++i)
2542 re_node_set dest_nodes, *new_nodes;
2543 Idx cur_node_idx = pstate->nodes.elems[i];
2546 unsigned int context;
2547 re_dfastate_t *dest_state;
2549 if (!dfa->nodes[cur_node_idx].accept_mb)
2552 if (dfa->nodes[cur_node_idx].constraint)
2554 context = re_string_context_at (&mctx->input,
2555 re_string_cur_idx (&mctx->input),
2557 if (NOT_SATISFY_NEXT_CONSTRAINT (dfa->nodes[cur_node_idx].constraint,
2562 /* How many bytes the node can accept? */
2563 naccepted = check_node_accept_bytes (dfa, cur_node_idx, &mctx->input,
2564 re_string_cur_idx (&mctx->input));
2568 /* The node can accepts 'naccepted' bytes. */
2569 dest_idx = re_string_cur_idx (&mctx->input) + naccepted;
2570 mctx->max_mb_elem_len = ((mctx->max_mb_elem_len < naccepted) ? naccepted
2571 : mctx->max_mb_elem_len);
2572 err = clean_state_log_if_needed (mctx, dest_idx);
2573 if (BE (err != REG_NOERROR, 0))
2576 assert (dfa->nexts[cur_node_idx] != REG_MISSING);
2578 new_nodes = dfa->eclosures + dfa->nexts[cur_node_idx];
2580 dest_state = mctx->state_log[dest_idx];
2581 if (dest_state == NULL)
2582 dest_nodes = *new_nodes;
2585 err = re_node_set_init_union (&dest_nodes,
2586 dest_state->entrance_nodes, new_nodes);
2587 if (BE (err != REG_NOERROR, 0))
2590 context = re_string_context_at (&mctx->input, dest_idx - 1,
2592 mctx->state_log[dest_idx]
2593 = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2594 if (dest_state != NULL)
2595 re_node_set_free (&dest_nodes);
2596 if (BE (mctx->state_log[dest_idx] == NULL && err != REG_NOERROR, 0))
2601 #endif /* RE_ENABLE_I18N */
2603 static reg_errcode_t
2605 transit_state_bkref (re_match_context_t *mctx, const re_node_set *nodes)
2607 const re_dfa_t *const dfa = mctx->dfa;
2610 Idx cur_str_idx = re_string_cur_idx (&mctx->input);
2612 for (i = 0; i < nodes->nelem; ++i)
2614 Idx dest_str_idx, prev_nelem, bkc_idx;
2615 Idx node_idx = nodes->elems[i];
2616 unsigned int context;
2617 const re_token_t *node = dfa->nodes + node_idx;
2618 re_node_set *new_dest_nodes;
2620 /* Check whether 'node' is a backreference or not. */
2621 if (node->type != OP_BACK_REF)
2624 if (node->constraint)
2626 context = re_string_context_at (&mctx->input, cur_str_idx,
2628 if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
2632 /* 'node' is a backreference.
2633 Check the substring which the substring matched. */
2634 bkc_idx = mctx->nbkref_ents;
2635 err = get_subexp (mctx, node_idx, cur_str_idx);
2636 if (BE (err != REG_NOERROR, 0))
2639 /* And add the epsilon closures (which is 'new_dest_nodes') of
2640 the backreference to appropriate state_log. */
2642 assert (dfa->nexts[node_idx] != REG_MISSING);
2644 for (; bkc_idx < mctx->nbkref_ents; ++bkc_idx)
2647 re_dfastate_t *dest_state;
2648 struct re_backref_cache_entry *bkref_ent;
2649 bkref_ent = mctx->bkref_ents + bkc_idx;
2650 if (bkref_ent->node != node_idx || bkref_ent->str_idx != cur_str_idx)
2652 subexp_len = bkref_ent->subexp_to - bkref_ent->subexp_from;
2653 new_dest_nodes = (subexp_len == 0
2654 ? dfa->eclosures + dfa->edests[node_idx].elems[0]
2655 : dfa->eclosures + dfa->nexts[node_idx]);
2656 dest_str_idx = (cur_str_idx + bkref_ent->subexp_to
2657 - bkref_ent->subexp_from);
2658 context = re_string_context_at (&mctx->input, dest_str_idx - 1,
2660 dest_state = mctx->state_log[dest_str_idx];
2661 prev_nelem = ((mctx->state_log[cur_str_idx] == NULL) ? 0
2662 : mctx->state_log[cur_str_idx]->nodes.nelem);
2663 /* Add 'new_dest_node' to state_log. */
2664 if (dest_state == NULL)
2666 mctx->state_log[dest_str_idx]
2667 = re_acquire_state_context (&err, dfa, new_dest_nodes,
2669 if (BE (mctx->state_log[dest_str_idx] == NULL
2670 && err != REG_NOERROR, 0))
2675 re_node_set dest_nodes;
2676 err = re_node_set_init_union (&dest_nodes,
2677 dest_state->entrance_nodes,
2679 if (BE (err != REG_NOERROR, 0))
2681 re_node_set_free (&dest_nodes);
2684 mctx->state_log[dest_str_idx]
2685 = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2686 re_node_set_free (&dest_nodes);
2687 if (BE (mctx->state_log[dest_str_idx] == NULL
2688 && err != REG_NOERROR, 0))
2691 /* We need to check recursively if the backreference can epsilon
2694 && mctx->state_log[cur_str_idx]->nodes.nelem > prev_nelem)
2696 err = check_subexp_matching_top (mctx, new_dest_nodes,
2698 if (BE (err != REG_NOERROR, 0))
2700 err = transit_state_bkref (mctx, new_dest_nodes);
2701 if (BE (err != REG_NOERROR, 0))
2711 /* Enumerate all the candidates which the backreference BKREF_NODE can match
2712 at BKREF_STR_IDX, and register them by match_ctx_add_entry().
2713 Note that we might collect inappropriate candidates here.
2714 However, the cost of checking them strictly here is too high, then we
2715 delay these checking for prune_impossible_nodes(). */
2717 static reg_errcode_t
2718 internal_function __attribute_warn_unused_result__
2719 get_subexp (re_match_context_t *mctx, Idx bkref_node, Idx bkref_str_idx)
2721 const re_dfa_t *const dfa = mctx->dfa;
2722 Idx subexp_num, sub_top_idx;
2723 const char *buf = (const char *) re_string_get_buffer (&mctx->input);
2724 /* Return if we have already checked BKREF_NODE at BKREF_STR_IDX. */
2725 Idx cache_idx = search_cur_bkref_entry (mctx, bkref_str_idx);
2726 if (cache_idx != REG_MISSING)
2728 const struct re_backref_cache_entry *entry
2729 = mctx->bkref_ents + cache_idx;
2731 if (entry->node == bkref_node)
2732 return REG_NOERROR; /* We already checked it. */
2733 while (entry++->more);
2736 subexp_num = dfa->nodes[bkref_node].opr.idx;
2738 /* For each sub expression */
2739 for (sub_top_idx = 0; sub_top_idx < mctx->nsub_tops; ++sub_top_idx)
2742 re_sub_match_top_t *sub_top = mctx->sub_tops[sub_top_idx];
2743 re_sub_match_last_t *sub_last;
2744 Idx sub_last_idx, sl_str, bkref_str_off;
2746 if (dfa->nodes[sub_top->node].opr.idx != subexp_num)
2747 continue; /* It isn't related. */
2749 sl_str = sub_top->str_idx;
2750 bkref_str_off = bkref_str_idx;
2751 /* At first, check the last node of sub expressions we already
2753 for (sub_last_idx = 0; sub_last_idx < sub_top->nlasts; ++sub_last_idx)
2755 regoff_t sl_str_diff;
2756 sub_last = sub_top->lasts[sub_last_idx];
2757 sl_str_diff = sub_last->str_idx - sl_str;
2758 /* The matched string by the sub expression match with the substring
2759 at the back reference? */
2760 if (sl_str_diff > 0)
2762 if (BE (bkref_str_off + sl_str_diff > mctx->input.valid_len, 0))
2764 /* Not enough chars for a successful match. */
2765 if (bkref_str_off + sl_str_diff > mctx->input.len)
2768 err = clean_state_log_if_needed (mctx,
2771 if (BE (err != REG_NOERROR, 0))
2773 buf = (const char *) re_string_get_buffer (&mctx->input);
2775 if (memcmp (buf + bkref_str_off, buf + sl_str, sl_str_diff) != 0)
2776 /* We don't need to search this sub expression any more. */
2779 bkref_str_off += sl_str_diff;
2780 sl_str += sl_str_diff;
2781 err = get_subexp_sub (mctx, sub_top, sub_last, bkref_node,
2784 /* Reload buf, since the preceding call might have reallocated
2786 buf = (const char *) re_string_get_buffer (&mctx->input);
2788 if (err == REG_NOMATCH)
2790 if (BE (err != REG_NOERROR, 0))
2794 if (sub_last_idx < sub_top->nlasts)
2796 if (sub_last_idx > 0)
2798 /* Then, search for the other last nodes of the sub expression. */
2799 for (; sl_str <= bkref_str_idx; ++sl_str)
2802 regoff_t sl_str_off;
2803 const re_node_set *nodes;
2804 sl_str_off = sl_str - sub_top->str_idx;
2805 /* The matched string by the sub expression match with the substring
2806 at the back reference? */
2809 if (BE (bkref_str_off >= mctx->input.valid_len, 0))
2811 /* If we are at the end of the input, we cannot match. */
2812 if (bkref_str_off >= mctx->input.len)
2815 err = extend_buffers (mctx);
2816 if (BE (err != REG_NOERROR, 0))
2819 buf = (const char *) re_string_get_buffer (&mctx->input);
2821 if (buf [bkref_str_off++] != buf[sl_str - 1])
2822 break; /* We don't need to search this sub expression
2825 if (mctx->state_log[sl_str] == NULL)
2827 /* Does this state have a ')' of the sub expression? */
2828 nodes = &mctx->state_log[sl_str]->nodes;
2829 cls_node = find_subexp_node (dfa, nodes, subexp_num,
2831 if (cls_node == REG_MISSING)
2833 if (sub_top->path == NULL)
2835 sub_top->path = calloc (sizeof (state_array_t),
2836 sl_str - sub_top->str_idx + 1);
2837 if (sub_top->path == NULL)
2840 /* Can the OP_OPEN_SUBEXP node arrive the OP_CLOSE_SUBEXP node
2841 in the current context? */
2842 err = check_arrival (mctx, sub_top->path, sub_top->node,
2843 sub_top->str_idx, cls_node, sl_str,
2845 if (err == REG_NOMATCH)
2847 if (BE (err != REG_NOERROR, 0))
2849 sub_last = match_ctx_add_sublast (sub_top, cls_node, sl_str);
2850 if (BE (sub_last == NULL, 0))
2852 err = get_subexp_sub (mctx, sub_top, sub_last, bkref_node,
2854 if (err == REG_NOMATCH)
2861 /* Helper functions for get_subexp(). */
2863 /* Check SUB_LAST can arrive to the back reference BKREF_NODE at BKREF_STR.
2864 If it can arrive, register the sub expression expressed with SUB_TOP
2867 static reg_errcode_t
2869 get_subexp_sub (re_match_context_t *mctx, const re_sub_match_top_t *sub_top,
2870 re_sub_match_last_t *sub_last, Idx bkref_node, Idx bkref_str)
2874 /* Can the subexpression arrive the back reference? */
2875 err = check_arrival (mctx, &sub_last->path, sub_last->node,
2876 sub_last->str_idx, bkref_node, bkref_str,
2878 if (err != REG_NOERROR)
2880 err = match_ctx_add_entry (mctx, bkref_node, bkref_str, sub_top->str_idx,
2882 if (BE (err != REG_NOERROR, 0))
2884 to_idx = bkref_str + sub_last->str_idx - sub_top->str_idx;
2885 return clean_state_log_if_needed (mctx, to_idx);
2888 /* Find the first node which is '(' or ')' and whose index is SUBEXP_IDX.
2889 Search '(' if FL_OPEN, or search ')' otherwise.
2890 TODO: This function isn't efficient...
2891 Because there might be more than one nodes whose types are
2892 OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
2898 find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
2899 Idx subexp_idx, int type)
2902 for (cls_idx = 0; cls_idx < nodes->nelem; ++cls_idx)
2904 Idx cls_node = nodes->elems[cls_idx];
2905 const re_token_t *node = dfa->nodes + cls_node;
2906 if (node->type == type
2907 && node->opr.idx == subexp_idx)
2913 /* Check whether the node TOP_NODE at TOP_STR can arrive to the node
2914 LAST_NODE at LAST_STR. We record the path onto PATH since it will be
2916 Return REG_NOERROR if it can arrive, or REG_NOMATCH otherwise. */
2918 static reg_errcode_t
2919 internal_function __attribute_warn_unused_result__
2920 check_arrival (re_match_context_t *mctx, state_array_t *path, Idx top_node,
2921 Idx top_str, Idx last_node, Idx last_str, int type)
2923 const re_dfa_t *const dfa = mctx->dfa;
2924 reg_errcode_t err = REG_NOERROR;
2925 Idx subexp_num, backup_cur_idx, str_idx, null_cnt;
2926 re_dfastate_t *cur_state = NULL;
2927 re_node_set *cur_nodes, next_nodes;
2928 re_dfastate_t **backup_state_log;
2929 unsigned int context;
2931 subexp_num = dfa->nodes[top_node].opr.idx;
2932 /* Extend the buffer if we need. */
2933 if (BE (path->alloc < last_str + mctx->max_mb_elem_len + 1, 0))
2935 re_dfastate_t **new_array;
2936 Idx old_alloc = path->alloc;
2937 Idx incr_alloc = last_str + mctx->max_mb_elem_len + 1;
2939 if (BE (IDX_MAX - old_alloc < incr_alloc, 0))
2941 new_alloc = old_alloc + incr_alloc;
2942 if (BE (SIZE_MAX / sizeof (re_dfastate_t *) < new_alloc, 0))
2944 new_array = re_realloc (path->array, re_dfastate_t *, new_alloc);
2945 if (BE (new_array == NULL, 0))
2947 path->array = new_array;
2948 path->alloc = new_alloc;
2949 memset (new_array + old_alloc, '\0',
2950 sizeof (re_dfastate_t *) * (path->alloc - old_alloc));
2953 str_idx = path->next_idx ? path->next_idx : top_str;
2955 /* Temporary modify MCTX. */
2956 backup_state_log = mctx->state_log;
2957 backup_cur_idx = mctx->input.cur_idx;
2958 mctx->state_log = path->array;
2959 mctx->input.cur_idx = str_idx;
2961 /* Setup initial node set. */
2962 context = re_string_context_at (&mctx->input, str_idx - 1, mctx->eflags);
2963 if (str_idx == top_str)
2965 err = re_node_set_init_1 (&next_nodes, top_node);
2966 if (BE (err != REG_NOERROR, 0))
2968 err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
2969 if (BE (err != REG_NOERROR, 0))
2971 re_node_set_free (&next_nodes);
2977 cur_state = mctx->state_log[str_idx];
2978 if (cur_state && cur_state->has_backref)
2980 err = re_node_set_init_copy (&next_nodes, &cur_state->nodes);
2981 if (BE (err != REG_NOERROR, 0))
2985 re_node_set_init_empty (&next_nodes);
2987 if (str_idx == top_str || (cur_state && cur_state->has_backref))
2989 if (next_nodes.nelem)
2991 err = expand_bkref_cache (mctx, &next_nodes, str_idx,
2993 if (BE (err != REG_NOERROR, 0))
2995 re_node_set_free (&next_nodes);
2999 cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
3000 if (BE (cur_state == NULL && err != REG_NOERROR, 0))
3002 re_node_set_free (&next_nodes);
3005 mctx->state_log[str_idx] = cur_state;
3008 for (null_cnt = 0; str_idx < last_str && null_cnt <= mctx->max_mb_elem_len;)
3010 re_node_set_empty (&next_nodes);
3011 if (mctx->state_log[str_idx + 1])
3013 err = re_node_set_merge (&next_nodes,
3014 &mctx->state_log[str_idx + 1]->nodes);
3015 if (BE (err != REG_NOERROR, 0))
3017 re_node_set_free (&next_nodes);
3023 err = check_arrival_add_next_nodes (mctx, str_idx,
3024 &cur_state->non_eps_nodes,
3026 if (BE (err != REG_NOERROR, 0))
3028 re_node_set_free (&next_nodes);
3033 if (next_nodes.nelem)
3035 err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
3036 if (BE (err != REG_NOERROR, 0))
3038 re_node_set_free (&next_nodes);
3041 err = expand_bkref_cache (mctx, &next_nodes, str_idx,
3043 if (BE (err != REG_NOERROR, 0))
3045 re_node_set_free (&next_nodes);
3049 context = re_string_context_at (&mctx->input, str_idx - 1, mctx->eflags);
3050 cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
3051 if (BE (cur_state == NULL && err != REG_NOERROR, 0))
3053 re_node_set_free (&next_nodes);
3056 mctx->state_log[str_idx] = cur_state;
3057 null_cnt = cur_state == NULL ? null_cnt + 1 : 0;
3059 re_node_set_free (&next_nodes);
3060 cur_nodes = (mctx->state_log[last_str] == NULL ? NULL
3061 : &mctx->state_log[last_str]->nodes);
3062 path->next_idx = str_idx;
3065 mctx->state_log = backup_state_log;
3066 mctx->input.cur_idx = backup_cur_idx;
3068 /* Then check the current node set has the node LAST_NODE. */
3069 if (cur_nodes != NULL && re_node_set_contains (cur_nodes, last_node))
3075 /* Helper functions for check_arrival. */
3077 /* Calculate the destination nodes of CUR_NODES at STR_IDX, and append them
3079 TODO: This function is similar to the functions transit_state*(),
3080 however this function has many additional works.
3081 Can't we unify them? */
3083 static reg_errcode_t
3084 internal_function __attribute_warn_unused_result__
3085 check_arrival_add_next_nodes (re_match_context_t *mctx, Idx str_idx,
3086 re_node_set *cur_nodes, re_node_set *next_nodes)
3088 const re_dfa_t *const dfa = mctx->dfa;
3091 #ifdef RE_ENABLE_I18N
3092 reg_errcode_t err = REG_NOERROR;
3094 re_node_set union_set;
3095 re_node_set_init_empty (&union_set);
3096 for (cur_idx = 0; cur_idx < cur_nodes->nelem; ++cur_idx)
3099 Idx cur_node = cur_nodes->elems[cur_idx];
3101 re_token_type_t type = dfa->nodes[cur_node].type;
3102 assert (!IS_EPSILON_NODE (type));
3104 #ifdef RE_ENABLE_I18N
3105 /* If the node may accept "multi byte". */
3106 if (dfa->nodes[cur_node].accept_mb)
3108 naccepted = check_node_accept_bytes (dfa, cur_node, &mctx->input,
3112 re_dfastate_t *dest_state;
3113 Idx next_node = dfa->nexts[cur_node];
3114 Idx next_idx = str_idx + naccepted;
3115 dest_state = mctx->state_log[next_idx];
3116 re_node_set_empty (&union_set);
3119 err = re_node_set_merge (&union_set, &dest_state->nodes);
3120 if (BE (err != REG_NOERROR, 0))
3122 re_node_set_free (&union_set);
3126 ok = re_node_set_insert (&union_set, next_node);
3129 re_node_set_free (&union_set);
3132 mctx->state_log[next_idx] = re_acquire_state (&err, dfa,
3134 if (BE (mctx->state_log[next_idx] == NULL
3135 && err != REG_NOERROR, 0))
3137 re_node_set_free (&union_set);
3142 #endif /* RE_ENABLE_I18N */
3144 || check_node_accept (mctx, dfa->nodes + cur_node, str_idx))
3146 ok = re_node_set_insert (next_nodes, dfa->nexts[cur_node]);
3149 re_node_set_free (&union_set);
3154 re_node_set_free (&union_set);
3158 /* For all the nodes in CUR_NODES, add the epsilon closures of them to
3159 CUR_NODES, however exclude the nodes which are:
3160 - inside the sub expression whose number is EX_SUBEXP, if FL_OPEN.
3161 - out of the sub expression whose number is EX_SUBEXP, if !FL_OPEN.
3164 static reg_errcode_t
3166 check_arrival_expand_ecl (const re_dfa_t *dfa, re_node_set *cur_nodes,
3167 Idx ex_subexp, int type)
3170 Idx idx, outside_node;
3171 re_node_set new_nodes;
3173 assert (cur_nodes->nelem);
3175 err = re_node_set_alloc (&new_nodes, cur_nodes->nelem);
3176 if (BE (err != REG_NOERROR, 0))
3178 /* Create a new node set NEW_NODES with the nodes which are epsilon
3179 closures of the node in CUR_NODES. */
3181 for (idx = 0; idx < cur_nodes->nelem; ++idx)
3183 Idx cur_node = cur_nodes->elems[idx];
3184 const re_node_set *eclosure = dfa->eclosures + cur_node;
3185 outside_node = find_subexp_node (dfa, eclosure, ex_subexp, type);
3186 if (outside_node == REG_MISSING)
3188 /* There are no problematic nodes, just merge them. */
3189 err = re_node_set_merge (&new_nodes, eclosure);
3190 if (BE (err != REG_NOERROR, 0))
3192 re_node_set_free (&new_nodes);
3198 /* There are problematic nodes, re-calculate incrementally. */
3199 err = check_arrival_expand_ecl_sub (dfa, &new_nodes, cur_node,
3201 if (BE (err != REG_NOERROR, 0))
3203 re_node_set_free (&new_nodes);
3208 re_node_set_free (cur_nodes);
3209 *cur_nodes = new_nodes;
3213 /* Helper function for check_arrival_expand_ecl.
3214 Check incrementally the epsilon closure of TARGET, and if it isn't
3215 problematic append it to DST_NODES. */
3217 static reg_errcode_t
3218 internal_function __attribute_warn_unused_result__
3219 check_arrival_expand_ecl_sub (const re_dfa_t *dfa, re_node_set *dst_nodes,
3220 Idx target, Idx ex_subexp, int type)
3223 for (cur_node = target; !re_node_set_contains (dst_nodes, cur_node);)
3227 if (dfa->nodes[cur_node].type == type
3228 && dfa->nodes[cur_node].opr.idx == ex_subexp)
3230 if (type == OP_CLOSE_SUBEXP)
3232 ok = re_node_set_insert (dst_nodes, cur_node);
3238 ok = re_node_set_insert (dst_nodes, cur_node);
3241 if (dfa->edests[cur_node].nelem == 0)
3243 if (dfa->edests[cur_node].nelem == 2)
3246 err = check_arrival_expand_ecl_sub (dfa, dst_nodes,
3247 dfa->edests[cur_node].elems[1],
3249 if (BE (err != REG_NOERROR, 0))
3252 cur_node = dfa->edests[cur_node].elems[0];
3258 /* For all the back references in the current state, calculate the
3259 destination of the back references by the appropriate entry
3260 in MCTX->BKREF_ENTS. */
3262 static reg_errcode_t
3263 internal_function __attribute_warn_unused_result__
3264 expand_bkref_cache (re_match_context_t *mctx, re_node_set *cur_nodes,
3265 Idx cur_str, Idx subexp_num, int type)
3267 const re_dfa_t *const dfa = mctx->dfa;
3269 Idx cache_idx_start = search_cur_bkref_entry (mctx, cur_str);
3270 struct re_backref_cache_entry *ent;
3272 if (cache_idx_start == REG_MISSING)
3276 ent = mctx->bkref_ents + cache_idx_start;
3279 Idx to_idx, next_node;
3281 /* Is this entry ENT is appropriate? */
3282 if (!re_node_set_contains (cur_nodes, ent->node))
3285 to_idx = cur_str + ent->subexp_to - ent->subexp_from;
3286 /* Calculate the destination of the back reference, and append it
3287 to MCTX->STATE_LOG. */
3288 if (to_idx == cur_str)
3290 /* The backreference did epsilon transit, we must re-check all the
3291 node in the current state. */
3292 re_node_set new_dests;
3293 reg_errcode_t err2, err3;
3294 next_node = dfa->edests[ent->node].elems[0];
3295 if (re_node_set_contains (cur_nodes, next_node))
3297 err = re_node_set_init_1 (&new_dests, next_node);
3298 err2 = check_arrival_expand_ecl (dfa, &new_dests, subexp_num, type);
3299 err3 = re_node_set_merge (cur_nodes, &new_dests);
3300 re_node_set_free (&new_dests);
3301 if (BE (err != REG_NOERROR || err2 != REG_NOERROR
3302 || err3 != REG_NOERROR, 0))
3304 err = (err != REG_NOERROR ? err
3305 : (err2 != REG_NOERROR ? err2 : err3));
3308 /* TODO: It is still inefficient... */
3313 re_node_set union_set;
3314 next_node = dfa->nexts[ent->node];
3315 if (mctx->state_log[to_idx])
3318 if (re_node_set_contains (&mctx->state_log[to_idx]->nodes,
3321 err = re_node_set_init_copy (&union_set,
3322 &mctx->state_log[to_idx]->nodes);
3323 ok = re_node_set_insert (&union_set, next_node);
3324 if (BE (err != REG_NOERROR || ! ok, 0))
3326 re_node_set_free (&union_set);
3327 err = err != REG_NOERROR ? err : REG_ESPACE;
3333 err = re_node_set_init_1 (&union_set, next_node);
3334 if (BE (err != REG_NOERROR, 0))
3337 mctx->state_log[to_idx] = re_acquire_state (&err, dfa, &union_set);
3338 re_node_set_free (&union_set);
3339 if (BE (mctx->state_log[to_idx] == NULL
3340 && err != REG_NOERROR, 0))
3344 while (ent++->more);
3348 /* Build transition table for the state.
3349 Return true if successful. */
3353 build_trtable (const re_dfa_t *dfa, re_dfastate_t *state)
3358 bool need_word_trtable = false;
3359 bitset_word_t elem, mask;
3360 bool dests_node_malloced = false;
3361 bool dest_states_malloced = false;
3362 Idx ndests; /* Number of the destination states from 'state'. */
3363 re_dfastate_t **trtable;
3364 re_dfastate_t **dest_states = NULL, **dest_states_word, **dest_states_nl;
3365 re_node_set follows, *dests_node;
3367 bitset_t acceptable;
3371 re_node_set dests_node[SBC_MAX];
3372 bitset_t dests_ch[SBC_MAX];
3375 /* We build DFA states which corresponds to the destination nodes
3376 from 'state'. 'dests_node[i]' represents the nodes which i-th
3377 destination state contains, and 'dests_ch[i]' represents the
3378 characters which i-th destination state accepts. */
3379 if (__libc_use_alloca (sizeof (struct dests_alloc)))
3380 dests_alloc = (struct dests_alloc *) alloca (sizeof (struct dests_alloc));
3383 dests_alloc = re_malloc (struct dests_alloc, 1);
3384 if (BE (dests_alloc == NULL, 0))
3386 dests_node_malloced = true;
3388 dests_node = dests_alloc->dests_node;
3389 dests_ch = dests_alloc->dests_ch;
3391 /* Initialize transition table. */
3392 state->word_trtable = state->trtable = NULL;
3394 /* At first, group all nodes belonging to 'state' into several
3396 ndests = group_nodes_into_DFAstates (dfa, state, dests_node, dests_ch);
3397 if (BE (! REG_VALID_NONZERO_INDEX (ndests), 0))
3399 if (dests_node_malloced)
3401 /* Return false in case of an error, true otherwise. */
3404 state->trtable = (re_dfastate_t **)
3405 calloc (sizeof (re_dfastate_t *), SBC_MAX);
3406 if (BE (state->trtable == NULL, 0))
3413 err = re_node_set_alloc (&follows, ndests + 1);
3414 if (BE (err != REG_NOERROR, 0))
3417 /* Avoid arithmetic overflow in size calculation. */
3418 if (BE ((((SIZE_MAX - (sizeof (re_node_set) + sizeof (bitset_t)) * SBC_MAX)
3419 / (3 * sizeof (re_dfastate_t *)))
3424 if (__libc_use_alloca ((sizeof (re_node_set) + sizeof (bitset_t)) * SBC_MAX
3425 + ndests * 3 * sizeof (re_dfastate_t *)))
3426 dest_states = (re_dfastate_t **)
3427 alloca (ndests * 3 * sizeof (re_dfastate_t *));
3430 dest_states = (re_dfastate_t **)
3431 malloc (ndests * 3 * sizeof (re_dfastate_t *));
3432 if (BE (dest_states == NULL, 0))
3435 if (dest_states_malloced)
3437 re_node_set_free (&follows);
3438 for (i = 0; i < ndests; ++i)
3439 re_node_set_free (dests_node + i);
3440 if (dests_node_malloced)
3444 dest_states_malloced = true;
3446 dest_states_word = dest_states + ndests;
3447 dest_states_nl = dest_states_word + ndests;
3448 bitset_empty (acceptable);
3450 /* Then build the states for all destinations. */
3451 for (i = 0; i < ndests; ++i)
3454 re_node_set_empty (&follows);
3455 /* Merge the follows of this destination states. */
3456 for (j = 0; j < dests_node[i].nelem; ++j)
3458 next_node = dfa->nexts[dests_node[i].elems[j]];
3459 if (next_node != REG_MISSING)
3461 err = re_node_set_merge (&follows, dfa->eclosures + next_node);
3462 if (BE (err != REG_NOERROR, 0))
3466 dest_states[i] = re_acquire_state_context (&err, dfa, &follows, 0);
3467 if (BE (dest_states[i] == NULL && err != REG_NOERROR, 0))
3469 /* If the new state has context constraint,
3470 build appropriate states for these contexts. */
3471 if (dest_states[i]->has_constraint)
3473 dest_states_word[i] = re_acquire_state_context (&err, dfa, &follows,
3475 if (BE (dest_states_word[i] == NULL && err != REG_NOERROR, 0))
3478 if (dest_states[i] != dest_states_word[i] && dfa->mb_cur_max > 1)
3479 need_word_trtable = true;
3481 dest_states_nl[i] = re_acquire_state_context (&err, dfa, &follows,
3483 if (BE (dest_states_nl[i] == NULL && err != REG_NOERROR, 0))
3488 dest_states_word[i] = dest_states[i];
3489 dest_states_nl[i] = dest_states[i];
3491 bitset_merge (acceptable, dests_ch[i]);
3494 if (!BE (need_word_trtable, 0))
3496 /* We don't care about whether the following character is a word
3497 character, or we are in a single-byte character set so we can
3498 discern by looking at the character code: allocate a
3499 256-entry transition table. */
3500 trtable = state->trtable =
3501 (re_dfastate_t **) calloc (sizeof (re_dfastate_t *), SBC_MAX);
3502 if (BE (trtable == NULL, 0))
3505 /* For all characters ch...: */
3506 for (i = 0; i < BITSET_WORDS; ++i)
3507 for (ch = i * BITSET_WORD_BITS, elem = acceptable[i], mask = 1;
3509 mask <<= 1, elem >>= 1, ++ch)
3510 if (BE (elem & 1, 0))
3512 /* There must be exactly one destination which accepts
3513 character ch. See group_nodes_into_DFAstates. */
3514 for (j = 0; (dests_ch[j][i] & mask) == 0; ++j)
3517 /* j-th destination accepts the word character ch. */
3518 if (dfa->word_char[i] & mask)
3519 trtable[ch] = dest_states_word[j];
3521 trtable[ch] = dest_states[j];
3526 /* We care about whether the following character is a word
3527 character, and we are in a multi-byte character set: discern
3528 by looking at the character code: build two 256-entry
3529 transition tables, one starting at trtable[0] and one
3530 starting at trtable[SBC_MAX]. */
3531 trtable = state->word_trtable =
3532 (re_dfastate_t **) calloc (sizeof (re_dfastate_t *), 2 * SBC_MAX);
3533 if (BE (trtable == NULL, 0))
3536 /* For all characters ch...: */
3537 for (i = 0; i < BITSET_WORDS; ++i)
3538 for (ch = i * BITSET_WORD_BITS, elem = acceptable[i], mask = 1;
3540 mask <<= 1, elem >>= 1, ++ch)
3541 if (BE (elem & 1, 0))
3543 /* There must be exactly one destination which accepts
3544 character ch. See group_nodes_into_DFAstates. */
3545 for (j = 0; (dests_ch[j][i] & mask) == 0; ++j)
3548 /* j-th destination accepts the word character ch. */
3549 trtable[ch] = dest_states[j];
3550 trtable[ch + SBC_MAX] = dest_states_word[j];
3555 if (bitset_contain (acceptable, NEWLINE_CHAR))
3557 /* The current state accepts newline character. */
3558 for (j = 0; j < ndests; ++j)
3559 if (bitset_contain (dests_ch[j], NEWLINE_CHAR))
3561 /* k-th destination accepts newline character. */
3562 trtable[NEWLINE_CHAR] = dest_states_nl[j];
3563 if (need_word_trtable)
3564 trtable[NEWLINE_CHAR + SBC_MAX] = dest_states_nl[j];
3565 /* There must be only one destination which accepts
3566 newline. See group_nodes_into_DFAstates. */
3571 if (dest_states_malloced)
3574 re_node_set_free (&follows);
3575 for (i = 0; i < ndests; ++i)
3576 re_node_set_free (dests_node + i);
3578 if (dests_node_malloced)
3584 /* Group all nodes belonging to STATE into several destinations.
3585 Then for all destinations, set the nodes belonging to the destination
3586 to DESTS_NODE[i] and set the characters accepted by the destination
3587 to DEST_CH[i]. This function return the number of destinations. */
3591 group_nodes_into_DFAstates (const re_dfa_t *dfa, const re_dfastate_t *state,
3592 re_node_set *dests_node, bitset_t *dests_ch)
3597 Idx ndests; /* Number of the destinations from 'state'. */
3598 bitset_t accepts; /* Characters a node can accept. */
3599 const re_node_set *cur_nodes = &state->nodes;
3600 bitset_empty (accepts);
3603 /* For all the nodes belonging to 'state', */
3604 for (i = 0; i < cur_nodes->nelem; ++i)
3606 re_token_t *node = &dfa->nodes[cur_nodes->elems[i]];
3607 re_token_type_t type = node->type;
3608 unsigned int constraint = node->constraint;
3610 /* Enumerate all single byte character this node can accept. */
3611 if (type == CHARACTER)
3612 bitset_set (accepts, node->opr.c);
3613 else if (type == SIMPLE_BRACKET)
3615 bitset_merge (accepts, node->opr.sbcset);
3617 else if (type == OP_PERIOD)
3619 #ifdef RE_ENABLE_I18N
3620 if (dfa->mb_cur_max > 1)
3621 bitset_merge (accepts, dfa->sb_char);
3624 bitset_set_all (accepts);
3625 if (!(dfa->syntax & RE_DOT_NEWLINE))
3626 bitset_clear (accepts, '\n');
3627 if (dfa->syntax & RE_DOT_NOT_NULL)
3628 bitset_clear (accepts, '\0');
3630 #ifdef RE_ENABLE_I18N
3631 else if (type == OP_UTF8_PERIOD)
3633 if (ASCII_CHARS % BITSET_WORD_BITS == 0)
3634 memset (accepts, -1, ASCII_CHARS / CHAR_BIT);
3636 bitset_merge (accepts, utf8_sb_map);
3637 if (!(dfa->syntax & RE_DOT_NEWLINE))
3638 bitset_clear (accepts, '\n');
3639 if (dfa->syntax & RE_DOT_NOT_NULL)
3640 bitset_clear (accepts, '\0');
3646 /* Check the 'accepts' and sift the characters which are not
3647 match it the context. */
3650 if (constraint & NEXT_NEWLINE_CONSTRAINT)
3652 bool accepts_newline = bitset_contain (accepts, NEWLINE_CHAR);
3653 bitset_empty (accepts);
3654 if (accepts_newline)
3655 bitset_set (accepts, NEWLINE_CHAR);
3659 if (constraint & NEXT_ENDBUF_CONSTRAINT)
3661 bitset_empty (accepts);
3665 if (constraint & NEXT_WORD_CONSTRAINT)
3667 bitset_word_t any_set = 0;
3668 if (type == CHARACTER && !node->word_char)
3670 bitset_empty (accepts);
3673 #ifdef RE_ENABLE_I18N
3674 if (dfa->mb_cur_max > 1)
3675 for (j = 0; j < BITSET_WORDS; ++j)
3676 any_set |= (accepts[j] &= (dfa->word_char[j] | ~dfa->sb_char[j]));
3679 for (j = 0; j < BITSET_WORDS; ++j)
3680 any_set |= (accepts[j] &= dfa->word_char[j]);
3684 if (constraint & NEXT_NOTWORD_CONSTRAINT)
3686 bitset_word_t any_set = 0;
3687 if (type == CHARACTER && node->word_char)
3689 bitset_empty (accepts);
3692 #ifdef RE_ENABLE_I18N
3693 if (dfa->mb_cur_max > 1)
3694 for (j = 0; j < BITSET_WORDS; ++j)
3695 any_set |= (accepts[j] &= ~(dfa->word_char[j] & dfa->sb_char[j]));
3698 for (j = 0; j < BITSET_WORDS; ++j)
3699 any_set |= (accepts[j] &= ~dfa->word_char[j]);
3705 /* Then divide 'accepts' into DFA states, or create a new
3706 state. Above, we make sure that accepts is not empty. */
3707 for (j = 0; j < ndests; ++j)
3709 bitset_t intersec; /* Intersection sets, see below. */
3711 /* Flags, see below. */
3712 bitset_word_t has_intersec, not_subset, not_consumed;
3714 /* Optimization, skip if this state doesn't accept the character. */
3715 if (type == CHARACTER && !bitset_contain (dests_ch[j], node->opr.c))
3718 /* Enumerate the intersection set of this state and 'accepts'. */
3720 for (k = 0; k < BITSET_WORDS; ++k)
3721 has_intersec |= intersec[k] = accepts[k] & dests_ch[j][k];
3722 /* And skip if the intersection set is empty. */
3726 /* Then check if this state is a subset of 'accepts'. */
3727 not_subset = not_consumed = 0;
3728 for (k = 0; k < BITSET_WORDS; ++k)
3730 not_subset |= remains[k] = ~accepts[k] & dests_ch[j][k];
3731 not_consumed |= accepts[k] = accepts[k] & ~dests_ch[j][k];
3734 /* If this state isn't a subset of 'accepts', create a
3735 new group state, which has the 'remains'. */
3738 bitset_copy (dests_ch[ndests], remains);
3739 bitset_copy (dests_ch[j], intersec);
3740 err = re_node_set_init_copy (dests_node + ndests, &dests_node[j]);
3741 if (BE (err != REG_NOERROR, 0))
3746 /* Put the position in the current group. */
3747 ok = re_node_set_insert (&dests_node[j], cur_nodes->elems[i]);
3751 /* If all characters are consumed, go to next node. */
3755 /* Some characters remain, create a new group. */
3758 bitset_copy (dests_ch[ndests], accepts);
3759 err = re_node_set_init_1 (dests_node + ndests, cur_nodes->elems[i]);
3760 if (BE (err != REG_NOERROR, 0))
3763 bitset_empty (accepts);
3768 for (j = 0; j < ndests; ++j)
3769 re_node_set_free (dests_node + j);
3773 #ifdef RE_ENABLE_I18N
3774 /* Check how many bytes the node 'dfa->nodes[node_idx]' accepts.
3775 Return the number of the bytes the node accepts.
3776 STR_IDX is the current index of the input string.
3778 This function handles the nodes which can accept one character, or
3779 one collating element like '.', '[a-z]', opposite to the other nodes
3780 can only accept one byte. */
3784 check_node_accept_bytes (const re_dfa_t *dfa, Idx node_idx,
3785 const re_string_t *input, Idx str_idx)
3787 const re_token_t *node = dfa->nodes + node_idx;
3788 int char_len, elem_len;
3791 if (BE (node->type == OP_UTF8_PERIOD, 0))
3793 unsigned char c = re_string_byte_at (input, str_idx), d;
3794 if (BE (c < 0xc2, 1))
3797 if (str_idx + 2 > input->len)
3800 d = re_string_byte_at (input, str_idx + 1);
3802 return (d < 0x80 || d > 0xbf) ? 0 : 2;
3806 if (c == 0xe0 && d < 0xa0)
3812 if (c == 0xf0 && d < 0x90)
3818 if (c == 0xf8 && d < 0x88)
3824 if (c == 0xfc && d < 0x84)
3830 if (str_idx + char_len > input->len)
3833 for (i = 1; i < char_len; ++i)
3835 d = re_string_byte_at (input, str_idx + i);
3836 if (d < 0x80 || d > 0xbf)
3842 char_len = re_string_char_size_at (input, str_idx);
3843 if (node->type == OP_PERIOD)
3847 /* FIXME: I don't think this if is needed, as both '\n'
3848 and '\0' are char_len == 1. */
3849 /* '.' accepts any one character except the following two cases. */
3850 if ((!(dfa->syntax & RE_DOT_NEWLINE) &&
3851 re_string_byte_at (input, str_idx) == '\n') ||
3852 ((dfa->syntax & RE_DOT_NOT_NULL) &&
3853 re_string_byte_at (input, str_idx) == '\0'))
3858 elem_len = re_string_elem_size_at (input, str_idx);
3859 if ((elem_len <= 1 && char_len <= 1) || char_len == 0)
3862 if (node->type == COMPLEX_BRACKET)
3864 const re_charset_t *cset = node->opr.mbcset;
3866 const unsigned char *pin
3867 = ((const unsigned char *) re_string_get_buffer (input) + str_idx);
3872 wchar_t wc = ((cset->nranges || cset->nchar_classes || cset->nmbchars)
3873 ? re_string_wchar_at (input, str_idx) : 0);
3875 /* match with multibyte character? */
3876 for (i = 0; i < cset->nmbchars; ++i)
3877 if (wc == cset->mbchars[i])
3879 match_len = char_len;
3880 goto check_node_accept_bytes_match;
3882 /* match with character_class? */
3883 for (i = 0; i < cset->nchar_classes; ++i)
3885 wctype_t wt = cset->char_classes[i];
3886 if (__iswctype (wc, wt))
3888 match_len = char_len;
3889 goto check_node_accept_bytes_match;
3894 nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
3897 unsigned int in_collseq = 0;
3898 const int32_t *table, *indirect;
3899 const unsigned char *weights, *extra;
3900 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, elem_len);
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 && defined __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) * (*(int32_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 (MIN (IDX_MAX, SIZE_MAX / sizeof (re_dfastate_t *)) / 2
4145 <= pstr->bufs_len, 0))
4148 /* Double the lengths of the buffers. */
4149 ret = re_string_realloc_buffers (pstr, MIN (pstr->len, pstr->bufs_len * 2));
4150 if (BE (ret != REG_NOERROR, 0))
4153 if (mctx->state_log != NULL)
4155 /* And double the length of state_log. */
4156 /* XXX We have no indication of the size of this buffer. If this
4157 allocation fail we have no indication that the state_log array
4158 does not have the right size. */
4159 re_dfastate_t **new_array = re_realloc (mctx->state_log, re_dfastate_t *,
4160 pstr->bufs_len + 1);
4161 if (BE (new_array == NULL, 0))
4163 mctx->state_log = new_array;
4166 /* Then reconstruct the buffers. */
4169 #ifdef RE_ENABLE_I18N
4170 if (pstr->mb_cur_max > 1)
4172 ret = build_wcs_upper_buffer (pstr);
4173 if (BE (ret != REG_NOERROR, 0))
4177 #endif /* RE_ENABLE_I18N */
4178 build_upper_buffer (pstr);
4182 #ifdef RE_ENABLE_I18N
4183 if (pstr->mb_cur_max > 1)
4184 build_wcs_buffer (pstr);
4186 #endif /* RE_ENABLE_I18N */
4188 if (pstr->trans != NULL)
4189 re_string_translate_buffer (pstr);
4196 /* Functions for matching context. */
4198 /* Initialize MCTX. */
4200 static reg_errcode_t
4201 internal_function __attribute_warn_unused_result__
4202 match_ctx_init (re_match_context_t *mctx, int eflags, Idx n)
4204 mctx->eflags = eflags;
4205 mctx->match_last = REG_MISSING;
4208 /* Avoid overflow. */
4209 size_t max_object_size =
4210 MAX (sizeof (struct re_backref_cache_entry),
4211 sizeof (re_sub_match_top_t *));
4212 if (BE (MIN (IDX_MAX, SIZE_MAX / max_object_size) < n, 0))
4215 mctx->bkref_ents = re_malloc (struct re_backref_cache_entry, n);
4216 mctx->sub_tops = re_malloc (re_sub_match_top_t *, n);
4217 if (BE (mctx->bkref_ents == NULL || mctx->sub_tops == NULL, 0))
4220 /* Already zero-ed by the caller.
4222 mctx->bkref_ents = NULL;
4223 mctx->nbkref_ents = 0;
4224 mctx->nsub_tops = 0; */
4225 mctx->abkref_ents = n;
4226 mctx->max_mb_elem_len = 1;
4227 mctx->asub_tops = n;
4231 /* Clean the entries which depend on the current input in MCTX.
4232 This function must be invoked when the matcher changes the start index
4233 of the input, or changes the input string. */
4237 match_ctx_clean (re_match_context_t *mctx)
4240 for (st_idx = 0; st_idx < mctx->nsub_tops; ++st_idx)
4243 re_sub_match_top_t *top = mctx->sub_tops[st_idx];
4244 for (sl_idx = 0; sl_idx < top->nlasts; ++sl_idx)
4246 re_sub_match_last_t *last = top->lasts[sl_idx];
4247 re_free (last->path.array);
4250 re_free (top->lasts);
4253 re_free (top->path->array);
4254 re_free (top->path);
4259 mctx->nsub_tops = 0;
4260 mctx->nbkref_ents = 0;
4263 /* Free all the memory associated with MCTX. */
4267 match_ctx_free (re_match_context_t *mctx)
4269 /* First, free all the memory associated with MCTX->SUB_TOPS. */
4270 match_ctx_clean (mctx);
4271 re_free (mctx->sub_tops);
4272 re_free (mctx->bkref_ents);
4275 /* Add a new backreference entry to MCTX.
4276 Note that we assume that caller never call this function with duplicate
4277 entry, and call with STR_IDX which isn't smaller than any existing entry.
4280 static reg_errcode_t
4281 internal_function __attribute_warn_unused_result__
4282 match_ctx_add_entry (re_match_context_t *mctx, Idx node, Idx str_idx, Idx from,
4285 if (mctx->nbkref_ents >= mctx->abkref_ents)
4287 struct re_backref_cache_entry* new_entry;
4288 new_entry = re_realloc (mctx->bkref_ents, struct re_backref_cache_entry,
4289 mctx->abkref_ents * 2);
4290 if (BE (new_entry == NULL, 0))
4292 re_free (mctx->bkref_ents);
4295 mctx->bkref_ents = new_entry;
4296 memset (mctx->bkref_ents + mctx->nbkref_ents, '\0',
4297 sizeof (struct re_backref_cache_entry) * mctx->abkref_ents);
4298 mctx->abkref_ents *= 2;
4300 if (mctx->nbkref_ents > 0
4301 && mctx->bkref_ents[mctx->nbkref_ents - 1].str_idx == str_idx)
4302 mctx->bkref_ents[mctx->nbkref_ents - 1].more = 1;
4304 mctx->bkref_ents[mctx->nbkref_ents].node = node;
4305 mctx->bkref_ents[mctx->nbkref_ents].str_idx = str_idx;
4306 mctx->bkref_ents[mctx->nbkref_ents].subexp_from = from;
4307 mctx->bkref_ents[mctx->nbkref_ents].subexp_to = to;
4309 /* This is a cache that saves negative results of check_dst_limits_calc_pos.
4310 If bit N is clear, means that this entry won't epsilon-transition to
4311 an OP_OPEN_SUBEXP or OP_CLOSE_SUBEXP for the N+1-th subexpression. If
4312 it is set, check_dst_limits_calc_pos_1 will recurse and try to find one
4315 A backreference does not epsilon-transition unless it is empty, so set
4316 to all zeros if FROM != TO. */
4317 mctx->bkref_ents[mctx->nbkref_ents].eps_reachable_subexps_map
4318 = (from == to ? -1 : 0);
4320 mctx->bkref_ents[mctx->nbkref_ents++].more = 0;
4321 if (mctx->max_mb_elem_len < to - from)
4322 mctx->max_mb_elem_len = to - from;
4326 /* Return the first entry with the same str_idx, or REG_MISSING if none is
4327 found. Note that MCTX->BKREF_ENTS is already sorted by MCTX->STR_IDX. */
4331 search_cur_bkref_entry (const re_match_context_t *mctx, Idx str_idx)
4333 Idx left, right, mid, last;
4334 last = right = mctx->nbkref_ents;
4335 for (left = 0; left < right;)
4337 mid = (left + right) / 2;
4338 if (mctx->bkref_ents[mid].str_idx < str_idx)
4343 if (left < last && mctx->bkref_ents[left].str_idx == str_idx)
4349 /* Register the node NODE, whose type is OP_OPEN_SUBEXP, and which matches
4352 static reg_errcode_t
4353 internal_function __attribute_warn_unused_result__
4354 match_ctx_add_subtop (re_match_context_t *mctx, Idx node, Idx str_idx)
4357 assert (mctx->sub_tops != NULL);
4358 assert (mctx->asub_tops > 0);
4360 if (BE (mctx->nsub_tops == mctx->asub_tops, 0))
4362 Idx new_asub_tops = mctx->asub_tops * 2;
4363 re_sub_match_top_t **new_array = re_realloc (mctx->sub_tops,
4364 re_sub_match_top_t *,
4366 if (BE (new_array == NULL, 0))
4368 mctx->sub_tops = new_array;
4369 mctx->asub_tops = new_asub_tops;
4371 mctx->sub_tops[mctx->nsub_tops] = calloc (1, sizeof (re_sub_match_top_t));
4372 if (BE (mctx->sub_tops[mctx->nsub_tops] == NULL, 0))
4374 mctx->sub_tops[mctx->nsub_tops]->node = node;
4375 mctx->sub_tops[mctx->nsub_tops++]->str_idx = str_idx;
4379 /* Register the node NODE, whose type is OP_CLOSE_SUBEXP, and which matches
4380 at STR_IDX, whose corresponding OP_OPEN_SUBEXP is SUB_TOP. */
4382 static re_sub_match_last_t *
4384 match_ctx_add_sublast (re_sub_match_top_t *subtop, Idx node, Idx str_idx)
4386 re_sub_match_last_t *new_entry;
4387 if (BE (subtop->nlasts == subtop->alasts, 0))
4389 Idx new_alasts = 2 * subtop->alasts + 1;
4390 re_sub_match_last_t **new_array = re_realloc (subtop->lasts,
4391 re_sub_match_last_t *,
4393 if (BE (new_array == NULL, 0))
4395 subtop->lasts = new_array;
4396 subtop->alasts = new_alasts;
4398 new_entry = calloc (1, sizeof (re_sub_match_last_t));
4399 if (BE (new_entry != NULL, 1))
4401 subtop->lasts[subtop->nlasts] = new_entry;
4402 new_entry->node = node;
4403 new_entry->str_idx = str_idx;
4411 sift_ctx_init (re_sift_context_t *sctx, re_dfastate_t **sifted_sts,
4412 re_dfastate_t **limited_sts, Idx last_node, Idx last_str_idx)
4414 sctx->sifted_states = sifted_sts;
4415 sctx->limited_states = limited_sts;
4416 sctx->last_node = last_node;
4417 sctx->last_str_idx = last_str_idx;
4418 re_node_set_init_empty (&sctx->limits);