1 /* -*- buffer-read-only: t -*- vi: set ro: */
2 /* DO NOT EDIT! GENERATED AUTOMATICALLY! */
3 /* Extended regular expression matching and search library.
4 Copyright (C) 2002-2014 Free Software Foundation, Inc.
5 This file is part of the GNU C Library.
6 Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>.
8 The GNU C Library is free software; you can redistribute it and/or
9 modify it under the terms of the GNU General Public
10 License as published by the Free Software Foundation; either
11 version 3 of the License, or (at your option) any later version.
13 The GNU C Library is distributed in the hope that it will be useful,
14 but WITHOUT ANY WARRANTY; without even the implied warranty of
15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
16 General Public License for more details.
18 You should have received a copy of the GNU General Public
19 License along with the GNU C Library; if not, see
20 <http://www.gnu.org/licenses/>. */
22 static reg_errcode_t match_ctx_init (re_match_context_t *cache, int eflags,
23 Idx n) internal_function;
24 static void match_ctx_clean (re_match_context_t *mctx) internal_function;
25 static void match_ctx_free (re_match_context_t *cache) internal_function;
26 static reg_errcode_t match_ctx_add_entry (re_match_context_t *cache, Idx node,
27 Idx str_idx, Idx from, Idx to)
29 static Idx search_cur_bkref_entry (const re_match_context_t *mctx, Idx str_idx)
31 static reg_errcode_t match_ctx_add_subtop (re_match_context_t *mctx, Idx node,
32 Idx str_idx) internal_function;
33 static re_sub_match_last_t * match_ctx_add_sublast (re_sub_match_top_t *subtop,
34 Idx node, Idx str_idx)
36 static void sift_ctx_init (re_sift_context_t *sctx, re_dfastate_t **sifted_sts,
37 re_dfastate_t **limited_sts, Idx last_node,
40 static reg_errcode_t re_search_internal (const regex_t *preg,
41 const char *string, Idx length,
42 Idx start, Idx last_start, Idx stop,
43 size_t nmatch, regmatch_t pmatch[],
44 int eflags) internal_function;
45 static regoff_t re_search_2_stub (struct re_pattern_buffer *bufp,
46 const char *string1, Idx length1,
47 const char *string2, Idx length2,
48 Idx start, regoff_t range,
49 struct re_registers *regs,
50 Idx stop, bool ret_len) internal_function;
51 static regoff_t re_search_stub (struct re_pattern_buffer *bufp,
52 const char *string, Idx length, Idx start,
53 regoff_t range, Idx stop,
54 struct re_registers *regs,
55 bool ret_len) internal_function;
56 static unsigned re_copy_regs (struct re_registers *regs, regmatch_t *pmatch,
57 Idx nregs, int regs_allocated) internal_function;
58 static reg_errcode_t prune_impossible_nodes (re_match_context_t *mctx)
60 static Idx check_matching (re_match_context_t *mctx, bool fl_longest_match,
61 Idx *p_match_first) internal_function;
62 static Idx check_halt_state_context (const re_match_context_t *mctx,
63 const re_dfastate_t *state, Idx idx)
65 static void update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
66 regmatch_t *prev_idx_match, Idx cur_node,
67 Idx cur_idx, Idx nmatch) internal_function;
68 static reg_errcode_t push_fail_stack (struct re_fail_stack_t *fs,
69 Idx str_idx, Idx dest_node, Idx nregs,
71 re_node_set *eps_via_nodes)
73 static reg_errcode_t set_regs (const regex_t *preg,
74 const re_match_context_t *mctx,
75 size_t nmatch, regmatch_t *pmatch,
76 bool fl_backtrack) internal_function;
77 static reg_errcode_t free_fail_stack_return (struct re_fail_stack_t *fs)
81 static int sift_states_iter_mb (const re_match_context_t *mctx,
82 re_sift_context_t *sctx,
83 Idx node_idx, Idx str_idx, Idx max_str_idx)
85 #endif /* RE_ENABLE_I18N */
86 static reg_errcode_t sift_states_backward (const re_match_context_t *mctx,
87 re_sift_context_t *sctx)
89 static reg_errcode_t build_sifted_states (const re_match_context_t *mctx,
90 re_sift_context_t *sctx, Idx str_idx,
91 re_node_set *cur_dest)
93 static reg_errcode_t update_cur_sifted_state (const re_match_context_t *mctx,
94 re_sift_context_t *sctx,
96 re_node_set *dest_nodes)
98 static reg_errcode_t add_epsilon_src_nodes (const re_dfa_t *dfa,
99 re_node_set *dest_nodes,
100 const re_node_set *candidates)
102 static bool check_dst_limits (const re_match_context_t *mctx,
103 const re_node_set *limits,
104 Idx dst_node, Idx dst_idx, Idx src_node,
105 Idx src_idx) internal_function;
106 static int check_dst_limits_calc_pos_1 (const re_match_context_t *mctx,
107 int boundaries, Idx subexp_idx,
108 Idx from_node, Idx bkref_idx)
110 static int check_dst_limits_calc_pos (const re_match_context_t *mctx,
111 Idx limit, Idx subexp_idx,
112 Idx node, Idx str_idx,
113 Idx bkref_idx) internal_function;
114 static reg_errcode_t check_subexp_limits (const re_dfa_t *dfa,
115 re_node_set *dest_nodes,
116 const re_node_set *candidates,
118 struct re_backref_cache_entry *bkref_ents,
119 Idx str_idx) internal_function;
120 static reg_errcode_t sift_states_bkref (const re_match_context_t *mctx,
121 re_sift_context_t *sctx,
122 Idx str_idx, const re_node_set *candidates)
124 static reg_errcode_t merge_state_array (const re_dfa_t *dfa,
126 re_dfastate_t **src, Idx num)
128 static re_dfastate_t *find_recover_state (reg_errcode_t *err,
129 re_match_context_t *mctx) internal_function;
130 static re_dfastate_t *transit_state (reg_errcode_t *err,
131 re_match_context_t *mctx,
132 re_dfastate_t *state) internal_function;
133 static re_dfastate_t *merge_state_with_log (reg_errcode_t *err,
134 re_match_context_t *mctx,
135 re_dfastate_t *next_state)
137 static reg_errcode_t check_subexp_matching_top (re_match_context_t *mctx,
138 re_node_set *cur_nodes,
139 Idx str_idx) internal_function;
141 static re_dfastate_t *transit_state_sb (reg_errcode_t *err,
142 re_match_context_t *mctx,
143 re_dfastate_t *pstate)
146 #ifdef RE_ENABLE_I18N
147 static reg_errcode_t transit_state_mb (re_match_context_t *mctx,
148 re_dfastate_t *pstate)
150 #endif /* RE_ENABLE_I18N */
151 static reg_errcode_t transit_state_bkref (re_match_context_t *mctx,
152 const re_node_set *nodes)
154 static reg_errcode_t get_subexp (re_match_context_t *mctx,
155 Idx bkref_node, Idx bkref_str_idx)
157 static reg_errcode_t get_subexp_sub (re_match_context_t *mctx,
158 const re_sub_match_top_t *sub_top,
159 re_sub_match_last_t *sub_last,
160 Idx bkref_node, Idx bkref_str)
162 static Idx find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
163 Idx subexp_idx, int type) internal_function;
164 static reg_errcode_t check_arrival (re_match_context_t *mctx,
165 state_array_t *path, Idx top_node,
166 Idx top_str, Idx last_node, Idx last_str,
167 int type) internal_function;
168 static reg_errcode_t check_arrival_add_next_nodes (re_match_context_t *mctx,
170 re_node_set *cur_nodes,
171 re_node_set *next_nodes)
173 static reg_errcode_t check_arrival_expand_ecl (const re_dfa_t *dfa,
174 re_node_set *cur_nodes,
175 Idx ex_subexp, int type)
177 static reg_errcode_t check_arrival_expand_ecl_sub (const re_dfa_t *dfa,
178 re_node_set *dst_nodes,
179 Idx target, Idx ex_subexp,
180 int type) internal_function;
181 static reg_errcode_t expand_bkref_cache (re_match_context_t *mctx,
182 re_node_set *cur_nodes, Idx cur_str,
183 Idx subexp_num, int type)
185 static bool build_trtable (const re_dfa_t *dfa,
186 re_dfastate_t *state) internal_function;
187 #ifdef RE_ENABLE_I18N
188 static int check_node_accept_bytes (const re_dfa_t *dfa, Idx node_idx,
189 const re_string_t *input, Idx idx)
192 static unsigned int find_collation_sequence_value (const unsigned char *mbs,
196 #endif /* RE_ENABLE_I18N */
197 static Idx group_nodes_into_DFAstates (const re_dfa_t *dfa,
198 const re_dfastate_t *state,
199 re_node_set *states_node,
200 bitset_t *states_ch) internal_function;
201 static bool check_node_accept (const re_match_context_t *mctx,
202 const re_token_t *node, Idx idx)
204 static reg_errcode_t extend_buffers (re_match_context_t *mctx, int min_len)
207 /* Entry point for POSIX code. */
209 /* regexec searches for a given pattern, specified by PREG, in the
212 If NMATCH is zero or REG_NOSUB was set in the cflags argument to
213 'regcomp', we ignore PMATCH. Otherwise, we assume PMATCH has at
214 least NMATCH elements, and we set them to the offsets of the
215 corresponding matched substrings.
217 EFLAGS specifies "execution flags" which affect matching: if
218 REG_NOTBOL is set, then ^ does not match at the beginning of the
219 string; if REG_NOTEOL is set, then $ does not match at the end.
221 We return 0 if we find a match and REG_NOMATCH if not. */
224 regexec (preg, string, nmatch, pmatch, eflags)
225 const regex_t *_Restrict_ preg;
226 const char *_Restrict_ string;
228 regmatch_t pmatch[_Restrict_arr_];
233 re_dfa_t *dfa = preg->buffer;
235 if (eflags & ~(REG_NOTBOL | REG_NOTEOL | REG_STARTEND))
238 if (eflags & REG_STARTEND)
240 start = pmatch[0].rm_so;
241 length = pmatch[0].rm_eo;
246 length = strlen (string);
249 lock_lock (dfa->lock);
251 err = re_search_internal (preg, string, length, start, length,
252 length, 0, NULL, eflags);
254 err = re_search_internal (preg, string, length, start, length,
255 length, nmatch, pmatch, eflags);
256 lock_unlock (dfa->lock);
257 return err != REG_NOERROR;
261 # include <shlib-compat.h>
262 versioned_symbol (libc, __regexec, regexec, GLIBC_2_3_4);
264 # if SHLIB_COMPAT (libc, GLIBC_2_0, GLIBC_2_3_4)
265 __typeof__ (__regexec) __compat_regexec;
268 attribute_compat_text_section
269 __compat_regexec (const regex_t *_Restrict_ preg,
270 const char *_Restrict_ string, size_t nmatch,
271 regmatch_t pmatch[], int eflags)
273 return regexec (preg, string, nmatch, pmatch,
274 eflags & (REG_NOTBOL | REG_NOTEOL));
276 compat_symbol (libc, __compat_regexec, regexec, GLIBC_2_0);
280 /* Entry points for GNU code. */
282 /* re_match, re_search, re_match_2, re_search_2
284 The former two functions operate on STRING with length LENGTH,
285 while the later two operate on concatenation of STRING1 and STRING2
286 with lengths LENGTH1 and LENGTH2, respectively.
288 re_match() matches the compiled pattern in BUFP against the string,
289 starting at index START.
291 re_search() first tries matching at index START, then it tries to match
292 starting from index START + 1, and so on. The last start position tried
293 is START + RANGE. (Thus RANGE = 0 forces re_search to operate the same
296 The parameter STOP of re_{match,search}_2 specifies that no match exceeding
297 the first STOP characters of the concatenation of the strings should be
300 If REGS is not NULL, and BUFP->no_sub is not set, the offsets of the match
301 and all groups is stored in REGS. (For the "_2" variants, the offsets are
302 computed relative to the concatenation, not relative to the individual
305 On success, re_match* functions return the length of the match, re_search*
306 return the position of the start of the match. Return value -1 means no
307 match was found and -2 indicates an internal error. */
310 re_match (bufp, string, length, start, regs)
311 struct re_pattern_buffer *bufp;
314 struct re_registers *regs;
316 return re_search_stub (bufp, string, length, start, 0, length, regs, true);
319 weak_alias (__re_match, re_match)
323 re_search (bufp, string, length, start, range, regs)
324 struct re_pattern_buffer *bufp;
328 struct re_registers *regs;
330 return re_search_stub (bufp, string, length, start, range, length, regs,
334 weak_alias (__re_search, re_search)
338 re_match_2 (bufp, string1, length1, string2, length2, start, regs, stop)
339 struct re_pattern_buffer *bufp;
340 const char *string1, *string2;
341 Idx length1, length2, start, stop;
342 struct re_registers *regs;
344 return re_search_2_stub (bufp, string1, length1, string2, length2,
345 start, 0, regs, stop, true);
348 weak_alias (__re_match_2, re_match_2)
352 re_search_2 (bufp, string1, length1, string2, length2, start, range, regs, stop)
353 struct re_pattern_buffer *bufp;
354 const char *string1, *string2;
355 Idx length1, length2, start, stop;
357 struct re_registers *regs;
359 return re_search_2_stub (bufp, string1, length1, string2, length2,
360 start, range, regs, stop, false);
363 weak_alias (__re_search_2, re_search_2)
367 re_search_2_stub (struct re_pattern_buffer *bufp,
368 const char *string1, Idx length1,
369 const char *string2, Idx length2,
370 Idx start, regoff_t range, struct re_registers *regs,
371 Idx stop, bool ret_len)
375 Idx len = length1 + length2;
378 if (BE (length1 < 0 || length2 < 0 || stop < 0 || len < length1, 0))
381 /* Concatenate the strings. */
385 s = re_malloc (char, len);
387 if (BE (s == NULL, 0))
390 memcpy (__mempcpy (s, string1, length1), string2, length2);
392 memcpy (s, string1, length1);
393 memcpy (s + length1, string2, length2);
402 rval = re_search_stub (bufp, str, len, start, range, stop, regs,
408 /* The parameters have the same meaning as those of re_search.
409 Additional parameters:
410 If RET_LEN is true the length of the match is returned (re_match style);
411 otherwise the position of the match is returned. */
414 re_search_stub (struct re_pattern_buffer *bufp,
415 const char *string, Idx length,
416 Idx start, regoff_t range, Idx stop, struct re_registers *regs,
419 reg_errcode_t result;
424 re_dfa_t *dfa = bufp->buffer;
425 Idx last_start = start + range;
427 /* Check for out-of-range. */
428 if (BE (start < 0 || start > length, 0))
430 if (BE (length < last_start || (0 <= range && last_start < start), 0))
432 else if (BE (last_start < 0 || (range < 0 && start <= last_start), 0))
435 lock_lock (dfa->lock);
437 eflags |= (bufp->not_bol) ? REG_NOTBOL : 0;
438 eflags |= (bufp->not_eol) ? REG_NOTEOL : 0;
440 /* Compile fastmap if we haven't yet. */
441 if (start < last_start && bufp->fastmap != NULL && !bufp->fastmap_accurate)
442 re_compile_fastmap (bufp);
444 if (BE (bufp->no_sub, 0))
447 /* We need at least 1 register. */
450 else if (BE (bufp->regs_allocated == REGS_FIXED
451 && regs->num_regs <= bufp->re_nsub, 0))
453 nregs = regs->num_regs;
454 if (BE (nregs < 1, 0))
456 /* Nothing can be copied to regs. */
462 nregs = bufp->re_nsub + 1;
463 pmatch = re_malloc (regmatch_t, nregs);
464 if (BE (pmatch == NULL, 0))
470 result = re_search_internal (bufp, string, length, start, last_start, stop,
471 nregs, pmatch, eflags);
475 /* I hope we needn't fill their regs with -1's when no match was found. */
476 if (result != REG_NOERROR)
477 rval = result == REG_NOMATCH ? -1 : -2;
478 else if (regs != NULL)
480 /* If caller wants register contents data back, copy them. */
481 bufp->regs_allocated = re_copy_regs (regs, pmatch, nregs,
482 bufp->regs_allocated);
483 if (BE (bufp->regs_allocated == REGS_UNALLOCATED, 0))
487 if (BE (rval == 0, 1))
491 assert (pmatch[0].rm_so == start);
492 rval = pmatch[0].rm_eo - start;
495 rval = pmatch[0].rm_so;
499 lock_unlock (dfa->lock);
504 re_copy_regs (struct re_registers *regs, regmatch_t *pmatch, Idx nregs,
507 int rval = REGS_REALLOCATE;
509 Idx need_regs = nregs + 1;
510 /* We need one extra element beyond 'num_regs' for the '-1' marker GNU code
513 /* Have the register data arrays been allocated? */
514 if (regs_allocated == REGS_UNALLOCATED)
515 { /* No. So allocate them with malloc. */
516 regs->start = re_malloc (regoff_t, need_regs);
517 if (BE (regs->start == NULL, 0))
518 return REGS_UNALLOCATED;
519 regs->end = re_malloc (regoff_t, need_regs);
520 if (BE (regs->end == NULL, 0))
522 re_free (regs->start);
523 return REGS_UNALLOCATED;
525 regs->num_regs = need_regs;
527 else if (regs_allocated == REGS_REALLOCATE)
528 { /* Yes. If we need more elements than were already
529 allocated, reallocate them. If we need fewer, just
531 if (BE (need_regs > regs->num_regs, 0))
533 regoff_t *new_start = re_realloc (regs->start, regoff_t, need_regs);
535 if (BE (new_start == NULL, 0))
536 return REGS_UNALLOCATED;
537 new_end = re_realloc (regs->end, regoff_t, need_regs);
538 if (BE (new_end == NULL, 0))
541 return REGS_UNALLOCATED;
543 regs->start = new_start;
545 regs->num_regs = need_regs;
550 assert (regs_allocated == REGS_FIXED);
551 /* This function may not be called with REGS_FIXED and nregs too big. */
552 assert (regs->num_regs >= nregs);
557 for (i = 0; i < nregs; ++i)
559 regs->start[i] = pmatch[i].rm_so;
560 regs->end[i] = pmatch[i].rm_eo;
562 for ( ; i < regs->num_regs; ++i)
563 regs->start[i] = regs->end[i] = -1;
568 /* Set REGS to hold NUM_REGS registers, storing them in STARTS and
569 ENDS. Subsequent matches using PATTERN_BUFFER and REGS will use
570 this memory for recording register information. STARTS and ENDS
571 must be allocated using the malloc library routine, and must each
572 be at least NUM_REGS * sizeof (regoff_t) bytes long.
574 If NUM_REGS == 0, then subsequent matches should allocate their own
577 Unless this function is called, the first search or match using
578 PATTERN_BUFFER will allocate its own register data, without
579 freeing the old data. */
582 re_set_registers (bufp, regs, num_regs, starts, ends)
583 struct re_pattern_buffer *bufp;
584 struct re_registers *regs;
585 __re_size_t num_regs;
586 regoff_t *starts, *ends;
590 bufp->regs_allocated = REGS_REALLOCATE;
591 regs->num_regs = num_regs;
592 regs->start = starts;
597 bufp->regs_allocated = REGS_UNALLOCATED;
599 regs->start = regs->end = NULL;
603 weak_alias (__re_set_registers, re_set_registers)
606 /* Entry points compatible with 4.2 BSD regex library. We don't define
607 them unless specifically requested. */
609 #if defined _REGEX_RE_COMP || defined _LIBC
617 return 0 == regexec (&re_comp_buf, s, 0, NULL, 0);
619 #endif /* _REGEX_RE_COMP */
621 /* Internal entry point. */
623 /* Searches for a compiled pattern PREG in the string STRING, whose
624 length is LENGTH. NMATCH, PMATCH, and EFLAGS have the same
625 meaning as with regexec. LAST_START is START + RANGE, where
626 START and RANGE have the same meaning as with re_search.
627 Return REG_NOERROR if we find a match, and REG_NOMATCH if not,
628 otherwise return the error code.
629 Note: We assume front end functions already check ranges.
630 (0 <= LAST_START && LAST_START <= LENGTH) */
633 __attribute_warn_unused_result__
634 re_search_internal (const regex_t *preg,
635 const char *string, Idx length,
636 Idx start, Idx last_start, Idx stop,
637 size_t nmatch, regmatch_t pmatch[],
641 const re_dfa_t *dfa = preg->buffer;
642 Idx left_lim, right_lim;
644 bool fl_longest_match;
647 Idx match_last = REG_MISSING;
651 #if defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L)
652 re_match_context_t mctx = { .dfa = dfa };
654 re_match_context_t mctx;
656 char *fastmap = ((preg->fastmap != NULL && preg->fastmap_accurate
657 && start != last_start && !preg->can_be_null)
658 ? preg->fastmap : NULL);
659 RE_TRANSLATE_TYPE t = preg->translate;
661 #if !(defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L))
662 memset (&mctx, '\0', sizeof (re_match_context_t));
666 extra_nmatch = (nmatch > preg->re_nsub) ? nmatch - (preg->re_nsub + 1) : 0;
667 nmatch -= extra_nmatch;
669 /* Check if the DFA haven't been compiled. */
670 if (BE (preg->used == 0 || dfa->init_state == NULL
671 || dfa->init_state_word == NULL || dfa->init_state_nl == NULL
672 || dfa->init_state_begbuf == NULL, 0))
676 /* We assume front-end functions already check them. */
677 assert (0 <= last_start && last_start <= length);
680 /* If initial states with non-begbuf contexts have no elements,
681 the regex must be anchored. If preg->newline_anchor is set,
682 we'll never use init_state_nl, so do not check it. */
683 if (dfa->init_state->nodes.nelem == 0
684 && dfa->init_state_word->nodes.nelem == 0
685 && (dfa->init_state_nl->nodes.nelem == 0
686 || !preg->newline_anchor))
688 if (start != 0 && last_start != 0)
690 start = last_start = 0;
693 /* We must check the longest matching, if nmatch > 0. */
694 fl_longest_match = (nmatch != 0 || dfa->nbackref);
696 err = re_string_allocate (&mctx.input, string, length, dfa->nodes_len + 1,
697 preg->translate, (preg->syntax & RE_ICASE) != 0,
699 if (BE (err != REG_NOERROR, 0))
701 mctx.input.stop = stop;
702 mctx.input.raw_stop = stop;
703 mctx.input.newline_anchor = preg->newline_anchor;
705 err = match_ctx_init (&mctx, eflags, dfa->nbackref * 2);
706 if (BE (err != REG_NOERROR, 0))
709 /* We will log all the DFA states through which the dfa pass,
710 if nmatch > 1, or this dfa has "multibyte node", which is a
711 back-reference or a node which can accept multibyte character or
712 multi character collating element. */
713 if (nmatch > 1 || dfa->has_mb_node)
715 /* Avoid overflow. */
716 if (BE ((MIN (IDX_MAX, SIZE_MAX / sizeof (re_dfastate_t *))
717 <= mctx.input.bufs_len), 0))
723 mctx.state_log = re_malloc (re_dfastate_t *, mctx.input.bufs_len + 1);
724 if (BE (mctx.state_log == NULL, 0))
731 mctx.state_log = NULL;
734 mctx.input.tip_context = (eflags & REG_NOTBOL) ? CONTEXT_BEGBUF
735 : CONTEXT_NEWLINE | CONTEXT_BEGBUF;
737 /* Check incrementally whether the input string matches. */
738 incr = (last_start < start) ? -1 : 1;
739 left_lim = (last_start < start) ? last_start : start;
740 right_lim = (last_start < start) ? start : last_start;
741 sb = dfa->mb_cur_max == 1;
744 ? ((sb || !(preg->syntax & RE_ICASE || t) ? 4 : 0)
745 | (start <= last_start ? 2 : 0)
746 | (t != NULL ? 1 : 0))
749 for (;; match_first += incr)
752 if (match_first < left_lim || right_lim < match_first)
755 /* Advance as rapidly as possible through the string, until we
756 find a plausible place to start matching. This may be done
757 with varying efficiency, so there are various possibilities:
758 only the most common of them are specialized, in order to
759 save on code size. We use a switch statement for speed. */
767 /* Fastmap with single-byte translation, match forward. */
768 while (BE (match_first < right_lim, 1)
769 && !fastmap[t[(unsigned char) string[match_first]]])
771 goto forward_match_found_start_or_reached_end;
774 /* Fastmap without translation, match forward. */
775 while (BE (match_first < right_lim, 1)
776 && !fastmap[(unsigned char) string[match_first]])
779 forward_match_found_start_or_reached_end:
780 if (BE (match_first == right_lim, 0))
782 ch = match_first >= length
783 ? 0 : (unsigned char) string[match_first];
784 if (!fastmap[t ? t[ch] : ch])
791 /* Fastmap without multi-byte translation, match backwards. */
792 while (match_first >= left_lim)
794 ch = match_first >= length
795 ? 0 : (unsigned char) string[match_first];
796 if (fastmap[t ? t[ch] : ch])
800 if (match_first < left_lim)
805 /* In this case, we can't determine easily the current byte,
806 since it might be a component byte of a multibyte
807 character. Then we use the constructed buffer instead. */
810 /* If MATCH_FIRST is out of the valid range, reconstruct the
812 __re_size_t offset = match_first - mctx.input.raw_mbs_idx;
813 if (BE (offset >= (__re_size_t) mctx.input.valid_raw_len, 0))
815 err = re_string_reconstruct (&mctx.input, match_first,
817 if (BE (err != REG_NOERROR, 0))
820 offset = match_first - mctx.input.raw_mbs_idx;
822 /* If MATCH_FIRST is out of the buffer, leave it as '\0'.
823 Note that MATCH_FIRST must not be smaller than 0. */
824 ch = (match_first >= length
825 ? 0 : re_string_byte_at (&mctx.input, offset));
829 if (match_first < left_lim || match_first > right_lim)
838 /* Reconstruct the buffers so that the matcher can assume that
839 the matching starts from the beginning of the buffer. */
840 err = re_string_reconstruct (&mctx.input, match_first, eflags);
841 if (BE (err != REG_NOERROR, 0))
844 #ifdef RE_ENABLE_I18N
845 /* Don't consider this char as a possible match start if it part,
846 yet isn't the head, of a multibyte character. */
847 if (!sb && !re_string_first_byte (&mctx.input, 0))
851 /* It seems to be appropriate one, then use the matcher. */
852 /* We assume that the matching starts from 0. */
853 mctx.state_log_top = mctx.nbkref_ents = mctx.max_mb_elem_len = 0;
854 match_last = check_matching (&mctx, fl_longest_match,
855 start <= last_start ? &match_first : NULL);
856 if (match_last != REG_MISSING)
858 if (BE (match_last == REG_ERROR, 0))
865 mctx.match_last = match_last;
866 if ((!preg->no_sub && nmatch > 1) || dfa->nbackref)
868 re_dfastate_t *pstate = mctx.state_log[match_last];
869 mctx.last_node = check_halt_state_context (&mctx, pstate,
872 if ((!preg->no_sub && nmatch > 1 && dfa->has_plural_match)
875 err = prune_impossible_nodes (&mctx);
876 if (err == REG_NOERROR)
878 if (BE (err != REG_NOMATCH, 0))
880 match_last = REG_MISSING;
883 break; /* We found a match. */
887 match_ctx_clean (&mctx);
891 assert (match_last != REG_MISSING);
892 assert (err == REG_NOERROR);
895 /* Set pmatch[] if we need. */
900 /* Initialize registers. */
901 for (reg_idx = 1; reg_idx < nmatch; ++reg_idx)
902 pmatch[reg_idx].rm_so = pmatch[reg_idx].rm_eo = -1;
904 /* Set the points where matching start/end. */
906 pmatch[0].rm_eo = mctx.match_last;
907 /* FIXME: This function should fail if mctx.match_last exceeds
908 the maximum possible regoff_t value. We need a new error
909 code REG_OVERFLOW. */
911 if (!preg->no_sub && nmatch > 1)
913 err = set_regs (preg, &mctx, nmatch, pmatch,
914 dfa->has_plural_match && dfa->nbackref > 0);
915 if (BE (err != REG_NOERROR, 0))
919 /* At last, add the offset to each register, since we slid
920 the buffers so that we could assume that the matching starts
922 for (reg_idx = 0; reg_idx < nmatch; ++reg_idx)
923 if (pmatch[reg_idx].rm_so != -1)
925 #ifdef RE_ENABLE_I18N
926 if (BE (mctx.input.offsets_needed != 0, 0))
928 pmatch[reg_idx].rm_so =
929 (pmatch[reg_idx].rm_so == mctx.input.valid_len
930 ? mctx.input.valid_raw_len
931 : mctx.input.offsets[pmatch[reg_idx].rm_so]);
932 pmatch[reg_idx].rm_eo =
933 (pmatch[reg_idx].rm_eo == mctx.input.valid_len
934 ? mctx.input.valid_raw_len
935 : mctx.input.offsets[pmatch[reg_idx].rm_eo]);
938 assert (mctx.input.offsets_needed == 0);
940 pmatch[reg_idx].rm_so += match_first;
941 pmatch[reg_idx].rm_eo += match_first;
943 for (reg_idx = 0; reg_idx < extra_nmatch; ++reg_idx)
945 pmatch[nmatch + reg_idx].rm_so = -1;
946 pmatch[nmatch + reg_idx].rm_eo = -1;
950 for (reg_idx = 0; reg_idx + 1 < nmatch; reg_idx++)
951 if (dfa->subexp_map[reg_idx] != reg_idx)
953 pmatch[reg_idx + 1].rm_so
954 = pmatch[dfa->subexp_map[reg_idx] + 1].rm_so;
955 pmatch[reg_idx + 1].rm_eo
956 = pmatch[dfa->subexp_map[reg_idx] + 1].rm_eo;
961 re_free (mctx.state_log);
963 match_ctx_free (&mctx);
964 re_string_destruct (&mctx.input);
969 __attribute_warn_unused_result__
970 prune_impossible_nodes (re_match_context_t *mctx)
972 const re_dfa_t *const dfa = mctx->dfa;
973 Idx halt_node, match_last;
975 re_dfastate_t **sifted_states;
976 re_dfastate_t **lim_states = NULL;
977 re_sift_context_t sctx;
979 assert (mctx->state_log != NULL);
981 match_last = mctx->match_last;
982 halt_node = mctx->last_node;
984 /* Avoid overflow. */
985 if (BE (MIN (IDX_MAX, SIZE_MAX / sizeof (re_dfastate_t *)) <= match_last, 0))
988 sifted_states = re_malloc (re_dfastate_t *, match_last + 1);
989 if (BE (sifted_states == NULL, 0))
996 lim_states = re_malloc (re_dfastate_t *, match_last + 1);
997 if (BE (lim_states == NULL, 0))
1004 memset (lim_states, '\0',
1005 sizeof (re_dfastate_t *) * (match_last + 1));
1006 sift_ctx_init (&sctx, sifted_states, lim_states, halt_node,
1008 ret = sift_states_backward (mctx, &sctx);
1009 re_node_set_free (&sctx.limits);
1010 if (BE (ret != REG_NOERROR, 0))
1012 if (sifted_states[0] != NULL || lim_states[0] != NULL)
1017 if (! REG_VALID_INDEX (match_last))
1022 } while (mctx->state_log[match_last] == NULL
1023 || !mctx->state_log[match_last]->halt);
1024 halt_node = check_halt_state_context (mctx,
1025 mctx->state_log[match_last],
1028 ret = merge_state_array (dfa, sifted_states, lim_states,
1030 re_free (lim_states);
1032 if (BE (ret != REG_NOERROR, 0))
1037 sift_ctx_init (&sctx, sifted_states, lim_states, halt_node, match_last);
1038 ret = sift_states_backward (mctx, &sctx);
1039 re_node_set_free (&sctx.limits);
1040 if (BE (ret != REG_NOERROR, 0))
1042 if (sifted_states[0] == NULL)
1048 re_free (mctx->state_log);
1049 mctx->state_log = sifted_states;
1050 sifted_states = NULL;
1051 mctx->last_node = halt_node;
1052 mctx->match_last = match_last;
1055 re_free (sifted_states);
1056 re_free (lim_states);
1060 /* Acquire an initial state and return it.
1061 We must select appropriate initial state depending on the context,
1062 since initial states may have constraints like "\<", "^", etc.. */
1064 static inline re_dfastate_t *
1065 __attribute__ ((always_inline)) internal_function
1066 acquire_init_state_context (reg_errcode_t *err, const re_match_context_t *mctx,
1069 const re_dfa_t *const dfa = mctx->dfa;
1070 if (dfa->init_state->has_constraint)
1072 unsigned int context;
1073 context = re_string_context_at (&mctx->input, idx - 1, mctx->eflags);
1074 if (IS_WORD_CONTEXT (context))
1075 return dfa->init_state_word;
1076 else if (IS_ORDINARY_CONTEXT (context))
1077 return dfa->init_state;
1078 else if (IS_BEGBUF_CONTEXT (context) && IS_NEWLINE_CONTEXT (context))
1079 return dfa->init_state_begbuf;
1080 else if (IS_NEWLINE_CONTEXT (context))
1081 return dfa->init_state_nl;
1082 else if (IS_BEGBUF_CONTEXT (context))
1084 /* It is relatively rare case, then calculate on demand. */
1085 return re_acquire_state_context (err, dfa,
1086 dfa->init_state->entrance_nodes,
1090 /* Must not happen? */
1091 return dfa->init_state;
1094 return dfa->init_state;
1097 /* Check whether the regular expression match input string INPUT or not,
1098 and return the index where the matching end. Return REG_MISSING if
1099 there is no match, and return REG_ERROR in case of an error.
1100 FL_LONGEST_MATCH means we want the POSIX longest matching.
1101 If P_MATCH_FIRST is not NULL, and the match fails, it is set to the
1102 next place where we may want to try matching.
1103 Note that the matcher assumes that the matching starts from the current
1104 index of the buffer. */
1107 internal_function __attribute_warn_unused_result__
1108 check_matching (re_match_context_t *mctx, bool fl_longest_match,
1111 const re_dfa_t *const dfa = mctx->dfa;
1114 Idx match_last = REG_MISSING;
1115 Idx cur_str_idx = re_string_cur_idx (&mctx->input);
1116 re_dfastate_t *cur_state;
1117 bool at_init_state = p_match_first != NULL;
1118 Idx next_start_idx = cur_str_idx;
1121 cur_state = acquire_init_state_context (&err, mctx, cur_str_idx);
1122 /* An initial state must not be NULL (invalid). */
1123 if (BE (cur_state == NULL, 0))
1125 assert (err == REG_ESPACE);
1129 if (mctx->state_log != NULL)
1131 mctx->state_log[cur_str_idx] = cur_state;
1133 /* Check OP_OPEN_SUBEXP in the initial state in case that we use them
1134 later. E.g. Processing back references. */
1135 if (BE (dfa->nbackref, 0))
1137 at_init_state = false;
1138 err = check_subexp_matching_top (mctx, &cur_state->nodes, 0);
1139 if (BE (err != REG_NOERROR, 0))
1142 if (cur_state->has_backref)
1144 err = transit_state_bkref (mctx, &cur_state->nodes);
1145 if (BE (err != REG_NOERROR, 0))
1151 /* If the RE accepts NULL string. */
1152 if (BE (cur_state->halt, 0))
1154 if (!cur_state->has_constraint
1155 || check_halt_state_context (mctx, cur_state, cur_str_idx))
1157 if (!fl_longest_match)
1161 match_last = cur_str_idx;
1167 while (!re_string_eoi (&mctx->input))
1169 re_dfastate_t *old_state = cur_state;
1170 Idx next_char_idx = re_string_cur_idx (&mctx->input) + 1;
1172 if ((BE (next_char_idx >= mctx->input.bufs_len, 0)
1173 && mctx->input.bufs_len < mctx->input.len)
1174 || (BE (next_char_idx >= mctx->input.valid_len, 0)
1175 && mctx->input.valid_len < mctx->input.len))
1177 err = extend_buffers (mctx, next_char_idx + 1);
1178 if (BE (err != REG_NOERROR, 0))
1180 assert (err == REG_ESPACE);
1185 cur_state = transit_state (&err, mctx, cur_state);
1186 if (mctx->state_log != NULL)
1187 cur_state = merge_state_with_log (&err, mctx, cur_state);
1189 if (cur_state == NULL)
1191 /* Reached the invalid state or an error. Try to recover a valid
1192 state using the state log, if available and if we have not
1193 already found a valid (even if not the longest) match. */
1194 if (BE (err != REG_NOERROR, 0))
1197 if (mctx->state_log == NULL
1198 || (match && !fl_longest_match)
1199 || (cur_state = find_recover_state (&err, mctx)) == NULL)
1203 if (BE (at_init_state, 0))
1205 if (old_state == cur_state)
1206 next_start_idx = next_char_idx;
1208 at_init_state = false;
1211 if (cur_state->halt)
1213 /* Reached a halt state.
1214 Check the halt state can satisfy the current context. */
1215 if (!cur_state->has_constraint
1216 || check_halt_state_context (mctx, cur_state,
1217 re_string_cur_idx (&mctx->input)))
1219 /* We found an appropriate halt state. */
1220 match_last = re_string_cur_idx (&mctx->input);
1223 /* We found a match, do not modify match_first below. */
1224 p_match_first = NULL;
1225 if (!fl_longest_match)
1232 *p_match_first += next_start_idx;
1237 /* Check NODE match the current context. */
1241 check_halt_node_context (const re_dfa_t *dfa, Idx node, unsigned int context)
1243 re_token_type_t type = dfa->nodes[node].type;
1244 unsigned int constraint = dfa->nodes[node].constraint;
1245 if (type != END_OF_RE)
1249 if (NOT_SATISFY_NEXT_CONSTRAINT (constraint, context))
1254 /* Check the halt state STATE match the current context.
1255 Return 0 if not match, if the node, STATE has, is a halt node and
1256 match the context, return the node. */
1260 check_halt_state_context (const re_match_context_t *mctx,
1261 const re_dfastate_t *state, Idx idx)
1264 unsigned int context;
1266 assert (state->halt);
1268 context = re_string_context_at (&mctx->input, idx, mctx->eflags);
1269 for (i = 0; i < state->nodes.nelem; ++i)
1270 if (check_halt_node_context (mctx->dfa, state->nodes.elems[i], context))
1271 return state->nodes.elems[i];
1275 /* Compute the next node to which "NFA" transit from NODE("NFA" is a NFA
1276 corresponding to the DFA).
1277 Return the destination node, and update EPS_VIA_NODES;
1278 return REG_MISSING in case of errors. */
1282 proceed_next_node (const re_match_context_t *mctx, Idx nregs, regmatch_t *regs,
1283 Idx *pidx, Idx node, re_node_set *eps_via_nodes,
1284 struct re_fail_stack_t *fs)
1286 const re_dfa_t *const dfa = mctx->dfa;
1289 if (IS_EPSILON_NODE (dfa->nodes[node].type))
1291 re_node_set *cur_nodes = &mctx->state_log[*pidx]->nodes;
1292 re_node_set *edests = &dfa->edests[node];
1294 ok = re_node_set_insert (eps_via_nodes, node);
1297 /* Pick up a valid destination, or return REG_MISSING if none
1299 for (dest_node = REG_MISSING, i = 0; i < edests->nelem; ++i)
1301 Idx candidate = edests->elems[i];
1302 if (!re_node_set_contains (cur_nodes, candidate))
1304 if (dest_node == REG_MISSING)
1305 dest_node = candidate;
1309 /* In order to avoid infinite loop like "(a*)*", return the second
1310 epsilon-transition if the first was already considered. */
1311 if (re_node_set_contains (eps_via_nodes, dest_node))
1314 /* Otherwise, push the second epsilon-transition on the fail stack. */
1316 && push_fail_stack (fs, *pidx, candidate, nregs, regs,
1320 /* We know we are going to exit. */
1329 re_token_type_t type = dfa->nodes[node].type;
1331 #ifdef RE_ENABLE_I18N
1332 if (dfa->nodes[node].accept_mb)
1333 naccepted = check_node_accept_bytes (dfa, node, &mctx->input, *pidx);
1335 #endif /* RE_ENABLE_I18N */
1336 if (type == OP_BACK_REF)
1338 Idx subexp_idx = dfa->nodes[node].opr.idx + 1;
1339 naccepted = regs[subexp_idx].rm_eo - regs[subexp_idx].rm_so;
1342 if (regs[subexp_idx].rm_so == -1 || regs[subexp_idx].rm_eo == -1)
1346 char *buf = (char *) re_string_get_buffer (&mctx->input);
1347 if (memcmp (buf + regs[subexp_idx].rm_so, buf + *pidx,
1356 ok = re_node_set_insert (eps_via_nodes, node);
1359 dest_node = dfa->edests[node].elems[0];
1360 if (re_node_set_contains (&mctx->state_log[*pidx]->nodes,
1367 || check_node_accept (mctx, dfa->nodes + node, *pidx))
1369 Idx dest_node = dfa->nexts[node];
1370 *pidx = (naccepted == 0) ? *pidx + 1 : *pidx + naccepted;
1371 if (fs && (*pidx > mctx->match_last || mctx->state_log[*pidx] == NULL
1372 || !re_node_set_contains (&mctx->state_log[*pidx]->nodes,
1375 re_node_set_empty (eps_via_nodes);
1382 static reg_errcode_t
1383 internal_function __attribute_warn_unused_result__
1384 push_fail_stack (struct re_fail_stack_t *fs, Idx str_idx, Idx dest_node,
1385 Idx nregs, regmatch_t *regs, re_node_set *eps_via_nodes)
1388 Idx num = fs->num++;
1389 if (fs->num == fs->alloc)
1391 struct re_fail_stack_ent_t *new_array;
1392 new_array = realloc (fs->stack, (sizeof (struct re_fail_stack_ent_t)
1394 if (new_array == NULL)
1397 fs->stack = new_array;
1399 fs->stack[num].idx = str_idx;
1400 fs->stack[num].node = dest_node;
1401 fs->stack[num].regs = re_malloc (regmatch_t, nregs);
1402 if (fs->stack[num].regs == NULL)
1404 memcpy (fs->stack[num].regs, regs, sizeof (regmatch_t) * nregs);
1405 err = re_node_set_init_copy (&fs->stack[num].eps_via_nodes, eps_via_nodes);
1411 pop_fail_stack (struct re_fail_stack_t *fs, Idx *pidx, Idx nregs,
1412 regmatch_t *regs, re_node_set *eps_via_nodes)
1414 Idx num = --fs->num;
1415 assert (REG_VALID_INDEX (num));
1416 *pidx = fs->stack[num].idx;
1417 memcpy (regs, fs->stack[num].regs, sizeof (regmatch_t) * nregs);
1418 re_node_set_free (eps_via_nodes);
1419 re_free (fs->stack[num].regs);
1420 *eps_via_nodes = fs->stack[num].eps_via_nodes;
1421 return fs->stack[num].node;
1424 /* Set the positions where the subexpressions are starts/ends to registers
1426 Note: We assume that pmatch[0] is already set, and
1427 pmatch[i].rm_so == pmatch[i].rm_eo == -1 for 0 < i < nmatch. */
1429 static reg_errcode_t
1430 internal_function __attribute_warn_unused_result__
1431 set_regs (const regex_t *preg, const re_match_context_t *mctx, size_t nmatch,
1432 regmatch_t *pmatch, bool fl_backtrack)
1434 const re_dfa_t *dfa = preg->buffer;
1436 re_node_set eps_via_nodes;
1437 struct re_fail_stack_t *fs;
1438 struct re_fail_stack_t fs_body = { 0, 2, NULL };
1439 regmatch_t *prev_idx_match;
1440 bool prev_idx_match_malloced = false;
1443 assert (nmatch > 1);
1444 assert (mctx->state_log != NULL);
1449 fs->stack = re_malloc (struct re_fail_stack_ent_t, fs->alloc);
1450 if (fs->stack == NULL)
1456 cur_node = dfa->init_node;
1457 re_node_set_init_empty (&eps_via_nodes);
1459 if (__libc_use_alloca (nmatch * sizeof (regmatch_t)))
1460 prev_idx_match = (regmatch_t *) alloca (nmatch * sizeof (regmatch_t));
1463 prev_idx_match = re_malloc (regmatch_t, nmatch);
1464 if (prev_idx_match == NULL)
1466 free_fail_stack_return (fs);
1469 prev_idx_match_malloced = true;
1471 memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
1473 for (idx = pmatch[0].rm_so; idx <= pmatch[0].rm_eo ;)
1475 update_regs (dfa, pmatch, prev_idx_match, cur_node, idx, nmatch);
1477 if (idx == pmatch[0].rm_eo && cur_node == mctx->last_node)
1482 for (reg_idx = 0; reg_idx < nmatch; ++reg_idx)
1483 if (pmatch[reg_idx].rm_so > -1 && pmatch[reg_idx].rm_eo == -1)
1485 if (reg_idx == nmatch)
1487 re_node_set_free (&eps_via_nodes);
1488 if (prev_idx_match_malloced)
1489 re_free (prev_idx_match);
1490 return free_fail_stack_return (fs);
1492 cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
1497 re_node_set_free (&eps_via_nodes);
1498 if (prev_idx_match_malloced)
1499 re_free (prev_idx_match);
1504 /* Proceed to next node. */
1505 cur_node = proceed_next_node (mctx, nmatch, pmatch, &idx, cur_node,
1506 &eps_via_nodes, fs);
1508 if (BE (! REG_VALID_INDEX (cur_node), 0))
1510 if (BE (cur_node == REG_ERROR, 0))
1512 re_node_set_free (&eps_via_nodes);
1513 if (prev_idx_match_malloced)
1514 re_free (prev_idx_match);
1515 free_fail_stack_return (fs);
1519 cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
1523 re_node_set_free (&eps_via_nodes);
1524 if (prev_idx_match_malloced)
1525 re_free (prev_idx_match);
1530 re_node_set_free (&eps_via_nodes);
1531 if (prev_idx_match_malloced)
1532 re_free (prev_idx_match);
1533 return free_fail_stack_return (fs);
1536 static reg_errcode_t
1538 free_fail_stack_return (struct re_fail_stack_t *fs)
1543 for (fs_idx = 0; fs_idx < fs->num; ++fs_idx)
1545 re_node_set_free (&fs->stack[fs_idx].eps_via_nodes);
1546 re_free (fs->stack[fs_idx].regs);
1548 re_free (fs->stack);
1555 update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
1556 regmatch_t *prev_idx_match, Idx cur_node, Idx cur_idx, Idx nmatch)
1558 int type = dfa->nodes[cur_node].type;
1559 if (type == OP_OPEN_SUBEXP)
1561 Idx reg_num = dfa->nodes[cur_node].opr.idx + 1;
1563 /* We are at the first node of this sub expression. */
1564 if (reg_num < nmatch)
1566 pmatch[reg_num].rm_so = cur_idx;
1567 pmatch[reg_num].rm_eo = -1;
1570 else if (type == OP_CLOSE_SUBEXP)
1572 Idx reg_num = dfa->nodes[cur_node].opr.idx + 1;
1573 if (reg_num < nmatch)
1575 /* We are at the last node of this sub expression. */
1576 if (pmatch[reg_num].rm_so < cur_idx)
1578 pmatch[reg_num].rm_eo = cur_idx;
1579 /* This is a non-empty match or we are not inside an optional
1580 subexpression. Accept this right away. */
1581 memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
1585 if (dfa->nodes[cur_node].opt_subexp
1586 && prev_idx_match[reg_num].rm_so != -1)
1587 /* We transited through an empty match for an optional
1588 subexpression, like (a?)*, and this is not the subexp's
1589 first match. Copy back the old content of the registers
1590 so that matches of an inner subexpression are undone as
1591 well, like in ((a?))*. */
1592 memcpy (pmatch, prev_idx_match, sizeof (regmatch_t) * nmatch);
1594 /* We completed a subexpression, but it may be part of
1595 an optional one, so do not update PREV_IDX_MATCH. */
1596 pmatch[reg_num].rm_eo = cur_idx;
1602 /* This function checks the STATE_LOG from the SCTX->last_str_idx to 0
1603 and sift the nodes in each states according to the following rules.
1604 Updated state_log will be wrote to STATE_LOG.
1606 Rules: We throw away the Node 'a' in the STATE_LOG[STR_IDX] if...
1607 1. When STR_IDX == MATCH_LAST(the last index in the state_log):
1608 If 'a' isn't the LAST_NODE and 'a' can't epsilon transit to
1609 the LAST_NODE, we throw away the node 'a'.
1610 2. When 0 <= STR_IDX < MATCH_LAST and 'a' accepts
1611 string 's' and transit to 'b':
1612 i. If 'b' isn't in the STATE_LOG[STR_IDX+strlen('s')], we throw
1614 ii. If 'b' is in the STATE_LOG[STR_IDX+strlen('s')] but 'b' is
1615 thrown away, we throw away the node 'a'.
1616 3. When 0 <= STR_IDX < MATCH_LAST and 'a' epsilon transit to 'b':
1617 i. If 'b' isn't in the STATE_LOG[STR_IDX], we throw away the
1619 ii. If 'b' is in the STATE_LOG[STR_IDX] but 'b' is thrown away,
1620 we throw away the node 'a'. */
1622 #define STATE_NODE_CONTAINS(state,node) \
1623 ((state) != NULL && re_node_set_contains (&(state)->nodes, node))
1625 static reg_errcode_t
1627 sift_states_backward (const re_match_context_t *mctx, re_sift_context_t *sctx)
1631 Idx str_idx = sctx->last_str_idx;
1632 re_node_set cur_dest;
1635 assert (mctx->state_log != NULL && mctx->state_log[str_idx] != NULL);
1638 /* Build sifted state_log[str_idx]. It has the nodes which can epsilon
1639 transit to the last_node and the last_node itself. */
1640 err = re_node_set_init_1 (&cur_dest, sctx->last_node);
1641 if (BE (err != REG_NOERROR, 0))
1643 err = update_cur_sifted_state (mctx, sctx, str_idx, &cur_dest);
1644 if (BE (err != REG_NOERROR, 0))
1647 /* Then check each states in the state_log. */
1650 /* Update counters. */
1651 null_cnt = (sctx->sifted_states[str_idx] == NULL) ? null_cnt + 1 : 0;
1652 if (null_cnt > mctx->max_mb_elem_len)
1654 memset (sctx->sifted_states, '\0',
1655 sizeof (re_dfastate_t *) * str_idx);
1656 re_node_set_free (&cur_dest);
1659 re_node_set_empty (&cur_dest);
1662 if (mctx->state_log[str_idx])
1664 err = build_sifted_states (mctx, sctx, str_idx, &cur_dest);
1665 if (BE (err != REG_NOERROR, 0))
1669 /* Add all the nodes which satisfy the following conditions:
1670 - It can epsilon transit to a node in CUR_DEST.
1672 And update state_log. */
1673 err = update_cur_sifted_state (mctx, sctx, str_idx, &cur_dest);
1674 if (BE (err != REG_NOERROR, 0))
1679 re_node_set_free (&cur_dest);
1683 static reg_errcode_t
1684 internal_function __attribute_warn_unused_result__
1685 build_sifted_states (const re_match_context_t *mctx, re_sift_context_t *sctx,
1686 Idx str_idx, re_node_set *cur_dest)
1688 const re_dfa_t *const dfa = mctx->dfa;
1689 const re_node_set *cur_src = &mctx->state_log[str_idx]->non_eps_nodes;
1692 /* Then build the next sifted state.
1693 We build the next sifted state on 'cur_dest', and update
1694 'sifted_states[str_idx]' with 'cur_dest'.
1696 'cur_dest' is the sifted state from 'state_log[str_idx + 1]'.
1697 'cur_src' points the node_set of the old 'state_log[str_idx]'
1698 (with the epsilon nodes pre-filtered out). */
1699 for (i = 0; i < cur_src->nelem; i++)
1701 Idx prev_node = cur_src->elems[i];
1706 re_token_type_t type = dfa->nodes[prev_node].type;
1707 assert (!IS_EPSILON_NODE (type));
1709 #ifdef RE_ENABLE_I18N
1710 /* If the node may accept "multi byte". */
1711 if (dfa->nodes[prev_node].accept_mb)
1712 naccepted = sift_states_iter_mb (mctx, sctx, prev_node,
1713 str_idx, sctx->last_str_idx);
1714 #endif /* RE_ENABLE_I18N */
1716 /* We don't check backreferences here.
1717 See update_cur_sifted_state(). */
1719 && check_node_accept (mctx, dfa->nodes + prev_node, str_idx)
1720 && STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + 1],
1721 dfa->nexts[prev_node]))
1727 if (sctx->limits.nelem)
1729 Idx to_idx = str_idx + naccepted;
1730 if (check_dst_limits (mctx, &sctx->limits,
1731 dfa->nexts[prev_node], to_idx,
1732 prev_node, str_idx))
1735 ok = re_node_set_insert (cur_dest, prev_node);
1743 /* Helper functions. */
1745 static reg_errcode_t
1747 clean_state_log_if_needed (re_match_context_t *mctx, Idx next_state_log_idx)
1749 Idx top = mctx->state_log_top;
1751 if ((next_state_log_idx >= mctx->input.bufs_len
1752 && mctx->input.bufs_len < mctx->input.len)
1753 || (next_state_log_idx >= mctx->input.valid_len
1754 && mctx->input.valid_len < mctx->input.len))
1757 err = extend_buffers (mctx, next_state_log_idx + 1);
1758 if (BE (err != REG_NOERROR, 0))
1762 if (top < next_state_log_idx)
1764 memset (mctx->state_log + top + 1, '\0',
1765 sizeof (re_dfastate_t *) * (next_state_log_idx - top));
1766 mctx->state_log_top = next_state_log_idx;
1771 static reg_errcode_t
1773 merge_state_array (const re_dfa_t *dfa, re_dfastate_t **dst,
1774 re_dfastate_t **src, Idx num)
1778 for (st_idx = 0; st_idx < num; ++st_idx)
1780 if (dst[st_idx] == NULL)
1781 dst[st_idx] = src[st_idx];
1782 else if (src[st_idx] != NULL)
1784 re_node_set merged_set;
1785 err = re_node_set_init_union (&merged_set, &dst[st_idx]->nodes,
1786 &src[st_idx]->nodes);
1787 if (BE (err != REG_NOERROR, 0))
1789 dst[st_idx] = re_acquire_state (&err, dfa, &merged_set);
1790 re_node_set_free (&merged_set);
1791 if (BE (err != REG_NOERROR, 0))
1798 static reg_errcode_t
1800 update_cur_sifted_state (const re_match_context_t *mctx,
1801 re_sift_context_t *sctx, Idx str_idx,
1802 re_node_set *dest_nodes)
1804 const re_dfa_t *const dfa = mctx->dfa;
1805 reg_errcode_t err = REG_NOERROR;
1806 const re_node_set *candidates;
1807 candidates = ((mctx->state_log[str_idx] == NULL) ? NULL
1808 : &mctx->state_log[str_idx]->nodes);
1810 if (dest_nodes->nelem == 0)
1811 sctx->sifted_states[str_idx] = NULL;
1816 /* At first, add the nodes which can epsilon transit to a node in
1818 err = add_epsilon_src_nodes (dfa, dest_nodes, candidates);
1819 if (BE (err != REG_NOERROR, 0))
1822 /* Then, check the limitations in the current sift_context. */
1823 if (sctx->limits.nelem)
1825 err = check_subexp_limits (dfa, dest_nodes, candidates, &sctx->limits,
1826 mctx->bkref_ents, str_idx);
1827 if (BE (err != REG_NOERROR, 0))
1832 sctx->sifted_states[str_idx] = re_acquire_state (&err, dfa, dest_nodes);
1833 if (BE (err != REG_NOERROR, 0))
1837 if (candidates && mctx->state_log[str_idx]->has_backref)
1839 err = sift_states_bkref (mctx, sctx, str_idx, candidates);
1840 if (BE (err != REG_NOERROR, 0))
1846 static reg_errcode_t
1847 internal_function __attribute_warn_unused_result__
1848 add_epsilon_src_nodes (const re_dfa_t *dfa, re_node_set *dest_nodes,
1849 const re_node_set *candidates)
1851 reg_errcode_t err = REG_NOERROR;
1854 re_dfastate_t *state = re_acquire_state (&err, dfa, dest_nodes);
1855 if (BE (err != REG_NOERROR, 0))
1858 if (!state->inveclosure.alloc)
1860 err = re_node_set_alloc (&state->inveclosure, dest_nodes->nelem);
1861 if (BE (err != REG_NOERROR, 0))
1863 for (i = 0; i < dest_nodes->nelem; i++)
1865 err = re_node_set_merge (&state->inveclosure,
1866 dfa->inveclosures + dest_nodes->elems[i]);
1867 if (BE (err != REG_NOERROR, 0))
1871 return re_node_set_add_intersect (dest_nodes, candidates,
1872 &state->inveclosure);
1875 static reg_errcode_t
1877 sub_epsilon_src_nodes (const re_dfa_t *dfa, Idx node, re_node_set *dest_nodes,
1878 const re_node_set *candidates)
1882 re_node_set *inv_eclosure = dfa->inveclosures + node;
1883 re_node_set except_nodes;
1884 re_node_set_init_empty (&except_nodes);
1885 for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx)
1887 Idx cur_node = inv_eclosure->elems[ecl_idx];
1888 if (cur_node == node)
1890 if (IS_EPSILON_NODE (dfa->nodes[cur_node].type))
1892 Idx edst1 = dfa->edests[cur_node].elems[0];
1893 Idx edst2 = ((dfa->edests[cur_node].nelem > 1)
1894 ? dfa->edests[cur_node].elems[1] : REG_MISSING);
1895 if ((!re_node_set_contains (inv_eclosure, edst1)
1896 && re_node_set_contains (dest_nodes, edst1))
1897 || (REG_VALID_NONZERO_INDEX (edst2)
1898 && !re_node_set_contains (inv_eclosure, edst2)
1899 && re_node_set_contains (dest_nodes, edst2)))
1901 err = re_node_set_add_intersect (&except_nodes, candidates,
1902 dfa->inveclosures + cur_node);
1903 if (BE (err != REG_NOERROR, 0))
1905 re_node_set_free (&except_nodes);
1911 for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx)
1913 Idx cur_node = inv_eclosure->elems[ecl_idx];
1914 if (!re_node_set_contains (&except_nodes, cur_node))
1916 Idx idx = re_node_set_contains (dest_nodes, cur_node) - 1;
1917 re_node_set_remove_at (dest_nodes, idx);
1920 re_node_set_free (&except_nodes);
1926 check_dst_limits (const re_match_context_t *mctx, const re_node_set *limits,
1927 Idx dst_node, Idx dst_idx, Idx src_node, Idx src_idx)
1929 const re_dfa_t *const dfa = mctx->dfa;
1930 Idx lim_idx, src_pos, dst_pos;
1932 Idx dst_bkref_idx = search_cur_bkref_entry (mctx, dst_idx);
1933 Idx src_bkref_idx = search_cur_bkref_entry (mctx, src_idx);
1934 for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx)
1937 struct re_backref_cache_entry *ent;
1938 ent = mctx->bkref_ents + limits->elems[lim_idx];
1939 subexp_idx = dfa->nodes[ent->node].opr.idx;
1941 dst_pos = check_dst_limits_calc_pos (mctx, limits->elems[lim_idx],
1942 subexp_idx, dst_node, dst_idx,
1944 src_pos = check_dst_limits_calc_pos (mctx, limits->elems[lim_idx],
1945 subexp_idx, src_node, src_idx,
1949 <src> <dst> ( <subexp> )
1950 ( <subexp> ) <src> <dst>
1951 ( <subexp1> <src> <subexp2> <dst> <subexp3> ) */
1952 if (src_pos == dst_pos)
1953 continue; /* This is unrelated limitation. */
1962 check_dst_limits_calc_pos_1 (const re_match_context_t *mctx, int boundaries,
1963 Idx subexp_idx, Idx from_node, Idx bkref_idx)
1965 const re_dfa_t *const dfa = mctx->dfa;
1966 const re_node_set *eclosures = dfa->eclosures + from_node;
1969 /* Else, we are on the boundary: examine the nodes on the epsilon
1971 for (node_idx = 0; node_idx < eclosures->nelem; ++node_idx)
1973 Idx node = eclosures->elems[node_idx];
1974 switch (dfa->nodes[node].type)
1977 if (bkref_idx != REG_MISSING)
1979 struct re_backref_cache_entry *ent = mctx->bkref_ents + bkref_idx;
1985 if (ent->node != node)
1988 if (subexp_idx < BITSET_WORD_BITS
1989 && !(ent->eps_reachable_subexps_map
1990 & ((bitset_word_t) 1 << subexp_idx)))
1993 /* Recurse trying to reach the OP_OPEN_SUBEXP and
1994 OP_CLOSE_SUBEXP cases below. But, if the
1995 destination node is the same node as the source
1996 node, don't recurse because it would cause an
1997 infinite loop: a regex that exhibits this behavior
1999 dst = dfa->edests[node].elems[0];
2000 if (dst == from_node)
2004 else /* if (boundaries & 2) */
2009 check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx,
2011 if (cpos == -1 /* && (boundaries & 1) */)
2013 if (cpos == 0 && (boundaries & 2))
2016 if (subexp_idx < BITSET_WORD_BITS)
2017 ent->eps_reachable_subexps_map
2018 &= ~((bitset_word_t) 1 << subexp_idx);
2020 while (ent++->more);
2024 case OP_OPEN_SUBEXP:
2025 if ((boundaries & 1) && subexp_idx == dfa->nodes[node].opr.idx)
2029 case OP_CLOSE_SUBEXP:
2030 if ((boundaries & 2) && subexp_idx == dfa->nodes[node].opr.idx)
2039 return (boundaries & 2) ? 1 : 0;
2044 check_dst_limits_calc_pos (const re_match_context_t *mctx, Idx limit,
2045 Idx subexp_idx, Idx from_node, Idx str_idx,
2048 struct re_backref_cache_entry *lim = mctx->bkref_ents + limit;
2051 /* If we are outside the range of the subexpression, return -1 or 1. */
2052 if (str_idx < lim->subexp_from)
2055 if (lim->subexp_to < str_idx)
2058 /* If we are within the subexpression, return 0. */
2059 boundaries = (str_idx == lim->subexp_from);
2060 boundaries |= (str_idx == lim->subexp_to) << 1;
2061 if (boundaries == 0)
2064 /* Else, examine epsilon closure. */
2065 return check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx,
2066 from_node, bkref_idx);
2069 /* Check the limitations of sub expressions LIMITS, and remove the nodes
2070 which are against limitations from DEST_NODES. */
2072 static reg_errcode_t
2074 check_subexp_limits (const re_dfa_t *dfa, re_node_set *dest_nodes,
2075 const re_node_set *candidates, re_node_set *limits,
2076 struct re_backref_cache_entry *bkref_ents, Idx str_idx)
2079 Idx node_idx, lim_idx;
2081 for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx)
2084 struct re_backref_cache_entry *ent;
2085 ent = bkref_ents + limits->elems[lim_idx];
2087 if (str_idx <= ent->subexp_from || ent->str_idx < str_idx)
2088 continue; /* This is unrelated limitation. */
2090 subexp_idx = dfa->nodes[ent->node].opr.idx;
2091 if (ent->subexp_to == str_idx)
2093 Idx ops_node = REG_MISSING;
2094 Idx cls_node = REG_MISSING;
2095 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2097 Idx node = dest_nodes->elems[node_idx];
2098 re_token_type_t type = dfa->nodes[node].type;
2099 if (type == OP_OPEN_SUBEXP
2100 && subexp_idx == dfa->nodes[node].opr.idx)
2102 else if (type == OP_CLOSE_SUBEXP
2103 && subexp_idx == dfa->nodes[node].opr.idx)
2107 /* Check the limitation of the open subexpression. */
2108 /* Note that (ent->subexp_to = str_idx != ent->subexp_from). */
2109 if (REG_VALID_INDEX (ops_node))
2111 err = sub_epsilon_src_nodes (dfa, ops_node, dest_nodes,
2113 if (BE (err != REG_NOERROR, 0))
2117 /* Check the limitation of the close subexpression. */
2118 if (REG_VALID_INDEX (cls_node))
2119 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2121 Idx node = dest_nodes->elems[node_idx];
2122 if (!re_node_set_contains (dfa->inveclosures + node,
2124 && !re_node_set_contains (dfa->eclosures + node,
2127 /* It is against this limitation.
2128 Remove it form the current sifted state. */
2129 err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2131 if (BE (err != REG_NOERROR, 0))
2137 else /* (ent->subexp_to != str_idx) */
2139 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2141 Idx node = dest_nodes->elems[node_idx];
2142 re_token_type_t type = dfa->nodes[node].type;
2143 if (type == OP_CLOSE_SUBEXP || type == OP_OPEN_SUBEXP)
2145 if (subexp_idx != dfa->nodes[node].opr.idx)
2147 /* It is against this limitation.
2148 Remove it form the current sifted state. */
2149 err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2151 if (BE (err != REG_NOERROR, 0))
2160 static reg_errcode_t
2161 internal_function __attribute_warn_unused_result__
2162 sift_states_bkref (const re_match_context_t *mctx, re_sift_context_t *sctx,
2163 Idx str_idx, const re_node_set *candidates)
2165 const re_dfa_t *const dfa = mctx->dfa;
2168 re_sift_context_t local_sctx;
2169 Idx first_idx = search_cur_bkref_entry (mctx, str_idx);
2171 if (first_idx == REG_MISSING)
2174 local_sctx.sifted_states = NULL; /* Mark that it hasn't been initialized. */
2176 for (node_idx = 0; node_idx < candidates->nelem; ++node_idx)
2179 re_token_type_t type;
2180 struct re_backref_cache_entry *entry;
2181 node = candidates->elems[node_idx];
2182 type = dfa->nodes[node].type;
2183 /* Avoid infinite loop for the REs like "()\1+". */
2184 if (node == sctx->last_node && str_idx == sctx->last_str_idx)
2186 if (type != OP_BACK_REF)
2189 entry = mctx->bkref_ents + first_idx;
2190 enabled_idx = first_idx;
2197 re_dfastate_t *cur_state;
2199 if (entry->node != node)
2201 subexp_len = entry->subexp_to - entry->subexp_from;
2202 to_idx = str_idx + subexp_len;
2203 dst_node = (subexp_len ? dfa->nexts[node]
2204 : dfa->edests[node].elems[0]);
2206 if (to_idx > sctx->last_str_idx
2207 || sctx->sifted_states[to_idx] == NULL
2208 || !STATE_NODE_CONTAINS (sctx->sifted_states[to_idx], dst_node)
2209 || check_dst_limits (mctx, &sctx->limits, node,
2210 str_idx, dst_node, to_idx))
2213 if (local_sctx.sifted_states == NULL)
2216 err = re_node_set_init_copy (&local_sctx.limits, &sctx->limits);
2217 if (BE (err != REG_NOERROR, 0))
2220 local_sctx.last_node = node;
2221 local_sctx.last_str_idx = str_idx;
2222 ok = re_node_set_insert (&local_sctx.limits, enabled_idx);
2228 cur_state = local_sctx.sifted_states[str_idx];
2229 err = sift_states_backward (mctx, &local_sctx);
2230 if (BE (err != REG_NOERROR, 0))
2232 if (sctx->limited_states != NULL)
2234 err = merge_state_array (dfa, sctx->limited_states,
2235 local_sctx.sifted_states,
2237 if (BE (err != REG_NOERROR, 0))
2240 local_sctx.sifted_states[str_idx] = cur_state;
2241 re_node_set_remove (&local_sctx.limits, enabled_idx);
2243 /* mctx->bkref_ents may have changed, reload the pointer. */
2244 entry = mctx->bkref_ents + enabled_idx;
2246 while (enabled_idx++, entry++->more);
2250 if (local_sctx.sifted_states != NULL)
2252 re_node_set_free (&local_sctx.limits);
2259 #ifdef RE_ENABLE_I18N
2262 sift_states_iter_mb (const re_match_context_t *mctx, re_sift_context_t *sctx,
2263 Idx node_idx, Idx str_idx, Idx max_str_idx)
2265 const re_dfa_t *const dfa = mctx->dfa;
2267 /* Check the node can accept "multi byte". */
2268 naccepted = check_node_accept_bytes (dfa, node_idx, &mctx->input, str_idx);
2269 if (naccepted > 0 && str_idx + naccepted <= max_str_idx &&
2270 !STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + naccepted],
2271 dfa->nexts[node_idx]))
2272 /* The node can't accept the "multi byte", or the
2273 destination was already thrown away, then the node
2274 could't accept the current input "multi byte". */
2276 /* Otherwise, it is sure that the node could accept
2277 'naccepted' bytes input. */
2280 #endif /* RE_ENABLE_I18N */
2283 /* Functions for state transition. */
2285 /* Return the next state to which the current state STATE will transit by
2286 accepting the current input byte, and update STATE_LOG if necessary.
2287 If STATE can accept a multibyte char/collating element/back reference
2288 update the destination of STATE_LOG. */
2290 static re_dfastate_t *
2291 internal_function __attribute_warn_unused_result__
2292 transit_state (reg_errcode_t *err, re_match_context_t *mctx,
2293 re_dfastate_t *state)
2295 re_dfastate_t **trtable;
2298 #ifdef RE_ENABLE_I18N
2299 /* If the current state can accept multibyte. */
2300 if (BE (state->accept_mb, 0))
2302 *err = transit_state_mb (mctx, state);
2303 if (BE (*err != REG_NOERROR, 0))
2306 #endif /* RE_ENABLE_I18N */
2308 /* Then decide the next state with the single byte. */
2311 /* don't use transition table */
2312 return transit_state_sb (err, mctx, state);
2315 /* Use transition table */
2316 ch = re_string_fetch_byte (&mctx->input);
2319 trtable = state->trtable;
2320 if (BE (trtable != NULL, 1))
2323 trtable = state->word_trtable;
2324 if (BE (trtable != NULL, 1))
2326 unsigned int context;
2328 = re_string_context_at (&mctx->input,
2329 re_string_cur_idx (&mctx->input) - 1,
2331 if (IS_WORD_CONTEXT (context))
2332 return trtable[ch + SBC_MAX];
2337 if (!build_trtable (mctx->dfa, state))
2343 /* Retry, we now have a transition table. */
2347 /* Update the state_log if we need */
2348 static re_dfastate_t *
2350 merge_state_with_log (reg_errcode_t *err, re_match_context_t *mctx,
2351 re_dfastate_t *next_state)
2353 const re_dfa_t *const dfa = mctx->dfa;
2354 Idx cur_idx = re_string_cur_idx (&mctx->input);
2356 if (cur_idx > mctx->state_log_top)
2358 mctx->state_log[cur_idx] = next_state;
2359 mctx->state_log_top = cur_idx;
2361 else if (mctx->state_log[cur_idx] == 0)
2363 mctx->state_log[cur_idx] = next_state;
2367 re_dfastate_t *pstate;
2368 unsigned int context;
2369 re_node_set next_nodes, *log_nodes, *table_nodes = NULL;
2370 /* If (state_log[cur_idx] != 0), it implies that cur_idx is
2371 the destination of a multibyte char/collating element/
2372 back reference. Then the next state is the union set of
2373 these destinations and the results of the transition table. */
2374 pstate = mctx->state_log[cur_idx];
2375 log_nodes = pstate->entrance_nodes;
2376 if (next_state != NULL)
2378 table_nodes = next_state->entrance_nodes;
2379 *err = re_node_set_init_union (&next_nodes, table_nodes,
2381 if (BE (*err != REG_NOERROR, 0))
2385 next_nodes = *log_nodes;
2386 /* Note: We already add the nodes of the initial state,
2387 then we don't need to add them here. */
2389 context = re_string_context_at (&mctx->input,
2390 re_string_cur_idx (&mctx->input) - 1,
2392 next_state = mctx->state_log[cur_idx]
2393 = re_acquire_state_context (err, dfa, &next_nodes, context);
2394 /* We don't need to check errors here, since the return value of
2395 this function is next_state and ERR is already set. */
2397 if (table_nodes != NULL)
2398 re_node_set_free (&next_nodes);
2401 if (BE (dfa->nbackref, 0) && next_state != NULL)
2403 /* Check OP_OPEN_SUBEXP in the current state in case that we use them
2404 later. We must check them here, since the back references in the
2405 next state might use them. */
2406 *err = check_subexp_matching_top (mctx, &next_state->nodes,
2408 if (BE (*err != REG_NOERROR, 0))
2411 /* If the next state has back references. */
2412 if (next_state->has_backref)
2414 *err = transit_state_bkref (mctx, &next_state->nodes);
2415 if (BE (*err != REG_NOERROR, 0))
2417 next_state = mctx->state_log[cur_idx];
2424 /* Skip bytes in the input that correspond to part of a
2425 multi-byte match, then look in the log for a state
2426 from which to restart matching. */
2427 static re_dfastate_t *
2429 find_recover_state (reg_errcode_t *err, re_match_context_t *mctx)
2431 re_dfastate_t *cur_state;
2434 Idx max = mctx->state_log_top;
2435 Idx cur_str_idx = re_string_cur_idx (&mctx->input);
2439 if (++cur_str_idx > max)
2441 re_string_skip_bytes (&mctx->input, 1);
2443 while (mctx->state_log[cur_str_idx] == NULL);
2445 cur_state = merge_state_with_log (err, mctx, NULL);
2447 while (*err == REG_NOERROR && cur_state == NULL);
2451 /* Helper functions for transit_state. */
2453 /* From the node set CUR_NODES, pick up the nodes whose types are
2454 OP_OPEN_SUBEXP and which have corresponding back references in the regular
2455 expression. And register them to use them later for evaluating the
2456 corresponding back references. */
2458 static reg_errcode_t
2460 check_subexp_matching_top (re_match_context_t *mctx, re_node_set *cur_nodes,
2463 const re_dfa_t *const dfa = mctx->dfa;
2467 /* TODO: This isn't efficient.
2468 Because there might be more than one nodes whose types are
2469 OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
2472 for (node_idx = 0; node_idx < cur_nodes->nelem; ++node_idx)
2474 Idx node = cur_nodes->elems[node_idx];
2475 if (dfa->nodes[node].type == OP_OPEN_SUBEXP
2476 && dfa->nodes[node].opr.idx < BITSET_WORD_BITS
2477 && (dfa->used_bkref_map
2478 & ((bitset_word_t) 1 << dfa->nodes[node].opr.idx)))
2480 err = match_ctx_add_subtop (mctx, node, str_idx);
2481 if (BE (err != REG_NOERROR, 0))
2489 /* Return the next state to which the current state STATE will transit by
2490 accepting the current input byte. */
2492 static re_dfastate_t *
2493 transit_state_sb (reg_errcode_t *err, re_match_context_t *mctx,
2494 re_dfastate_t *state)
2496 const re_dfa_t *const dfa = mctx->dfa;
2497 re_node_set next_nodes;
2498 re_dfastate_t *next_state;
2499 Idx node_cnt, cur_str_idx = re_string_cur_idx (&mctx->input);
2500 unsigned int context;
2502 *err = re_node_set_alloc (&next_nodes, state->nodes.nelem + 1);
2503 if (BE (*err != REG_NOERROR, 0))
2505 for (node_cnt = 0; node_cnt < state->nodes.nelem; ++node_cnt)
2507 Idx cur_node = state->nodes.elems[node_cnt];
2508 if (check_node_accept (mctx, dfa->nodes + cur_node, cur_str_idx))
2510 *err = re_node_set_merge (&next_nodes,
2511 dfa->eclosures + dfa->nexts[cur_node]);
2512 if (BE (*err != REG_NOERROR, 0))
2514 re_node_set_free (&next_nodes);
2519 context = re_string_context_at (&mctx->input, cur_str_idx, mctx->eflags);
2520 next_state = re_acquire_state_context (err, dfa, &next_nodes, context);
2521 /* We don't need to check errors here, since the return value of
2522 this function is next_state and ERR is already set. */
2524 re_node_set_free (&next_nodes);
2525 re_string_skip_bytes (&mctx->input, 1);
2530 #ifdef RE_ENABLE_I18N
2531 static reg_errcode_t
2533 transit_state_mb (re_match_context_t *mctx, re_dfastate_t *pstate)
2535 const re_dfa_t *const dfa = mctx->dfa;
2539 for (i = 0; i < pstate->nodes.nelem; ++i)
2541 re_node_set dest_nodes, *new_nodes;
2542 Idx cur_node_idx = pstate->nodes.elems[i];
2545 unsigned int context;
2546 re_dfastate_t *dest_state;
2548 if (!dfa->nodes[cur_node_idx].accept_mb)
2551 if (dfa->nodes[cur_node_idx].constraint)
2553 context = re_string_context_at (&mctx->input,
2554 re_string_cur_idx (&mctx->input),
2556 if (NOT_SATISFY_NEXT_CONSTRAINT (dfa->nodes[cur_node_idx].constraint,
2561 /* How many bytes the node can accept? */
2562 naccepted = check_node_accept_bytes (dfa, cur_node_idx, &mctx->input,
2563 re_string_cur_idx (&mctx->input));
2567 /* The node can accepts 'naccepted' bytes. */
2568 dest_idx = re_string_cur_idx (&mctx->input) + naccepted;
2569 mctx->max_mb_elem_len = ((mctx->max_mb_elem_len < naccepted) ? naccepted
2570 : mctx->max_mb_elem_len);
2571 err = clean_state_log_if_needed (mctx, dest_idx);
2572 if (BE (err != REG_NOERROR, 0))
2575 assert (dfa->nexts[cur_node_idx] != REG_MISSING);
2577 new_nodes = dfa->eclosures + dfa->nexts[cur_node_idx];
2579 dest_state = mctx->state_log[dest_idx];
2580 if (dest_state == NULL)
2581 dest_nodes = *new_nodes;
2584 err = re_node_set_init_union (&dest_nodes,
2585 dest_state->entrance_nodes, new_nodes);
2586 if (BE (err != REG_NOERROR, 0))
2589 context = re_string_context_at (&mctx->input, dest_idx - 1,
2591 mctx->state_log[dest_idx]
2592 = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2593 if (dest_state != NULL)
2594 re_node_set_free (&dest_nodes);
2595 if (BE (mctx->state_log[dest_idx] == NULL && err != REG_NOERROR, 0))
2600 #endif /* RE_ENABLE_I18N */
2602 static reg_errcode_t
2604 transit_state_bkref (re_match_context_t *mctx, const re_node_set *nodes)
2606 const re_dfa_t *const dfa = mctx->dfa;
2609 Idx cur_str_idx = re_string_cur_idx (&mctx->input);
2611 for (i = 0; i < nodes->nelem; ++i)
2613 Idx dest_str_idx, prev_nelem, bkc_idx;
2614 Idx node_idx = nodes->elems[i];
2615 unsigned int context;
2616 const re_token_t *node = dfa->nodes + node_idx;
2617 re_node_set *new_dest_nodes;
2619 /* Check whether 'node' is a backreference or not. */
2620 if (node->type != OP_BACK_REF)
2623 if (node->constraint)
2625 context = re_string_context_at (&mctx->input, cur_str_idx,
2627 if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
2631 /* 'node' is a backreference.
2632 Check the substring which the substring matched. */
2633 bkc_idx = mctx->nbkref_ents;
2634 err = get_subexp (mctx, node_idx, cur_str_idx);
2635 if (BE (err != REG_NOERROR, 0))
2638 /* And add the epsilon closures (which is 'new_dest_nodes') of
2639 the backreference to appropriate state_log. */
2641 assert (dfa->nexts[node_idx] != REG_MISSING);
2643 for (; bkc_idx < mctx->nbkref_ents; ++bkc_idx)
2646 re_dfastate_t *dest_state;
2647 struct re_backref_cache_entry *bkref_ent;
2648 bkref_ent = mctx->bkref_ents + bkc_idx;
2649 if (bkref_ent->node != node_idx || bkref_ent->str_idx != cur_str_idx)
2651 subexp_len = bkref_ent->subexp_to - bkref_ent->subexp_from;
2652 new_dest_nodes = (subexp_len == 0
2653 ? dfa->eclosures + dfa->edests[node_idx].elems[0]
2654 : dfa->eclosures + dfa->nexts[node_idx]);
2655 dest_str_idx = (cur_str_idx + bkref_ent->subexp_to
2656 - bkref_ent->subexp_from);
2657 context = re_string_context_at (&mctx->input, dest_str_idx - 1,
2659 dest_state = mctx->state_log[dest_str_idx];
2660 prev_nelem = ((mctx->state_log[cur_str_idx] == NULL) ? 0
2661 : mctx->state_log[cur_str_idx]->nodes.nelem);
2662 /* Add 'new_dest_node' to state_log. */
2663 if (dest_state == NULL)
2665 mctx->state_log[dest_str_idx]
2666 = re_acquire_state_context (&err, dfa, new_dest_nodes,
2668 if (BE (mctx->state_log[dest_str_idx] == NULL
2669 && err != REG_NOERROR, 0))
2674 re_node_set dest_nodes;
2675 err = re_node_set_init_union (&dest_nodes,
2676 dest_state->entrance_nodes,
2678 if (BE (err != REG_NOERROR, 0))
2680 re_node_set_free (&dest_nodes);
2683 mctx->state_log[dest_str_idx]
2684 = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2685 re_node_set_free (&dest_nodes);
2686 if (BE (mctx->state_log[dest_str_idx] == NULL
2687 && err != REG_NOERROR, 0))
2690 /* We need to check recursively if the backreference can epsilon
2693 && mctx->state_log[cur_str_idx]->nodes.nelem > prev_nelem)
2695 err = check_subexp_matching_top (mctx, new_dest_nodes,
2697 if (BE (err != REG_NOERROR, 0))
2699 err = transit_state_bkref (mctx, new_dest_nodes);
2700 if (BE (err != REG_NOERROR, 0))
2710 /* Enumerate all the candidates which the backreference BKREF_NODE can match
2711 at BKREF_STR_IDX, and register them by match_ctx_add_entry().
2712 Note that we might collect inappropriate candidates here.
2713 However, the cost of checking them strictly here is too high, then we
2714 delay these checking for prune_impossible_nodes(). */
2716 static reg_errcode_t
2717 internal_function __attribute_warn_unused_result__
2718 get_subexp (re_match_context_t *mctx, Idx bkref_node, Idx bkref_str_idx)
2720 const re_dfa_t *const dfa = mctx->dfa;
2721 Idx subexp_num, sub_top_idx;
2722 const char *buf = (const char *) re_string_get_buffer (&mctx->input);
2723 /* Return if we have already checked BKREF_NODE at BKREF_STR_IDX. */
2724 Idx cache_idx = search_cur_bkref_entry (mctx, bkref_str_idx);
2725 if (cache_idx != REG_MISSING)
2727 const struct re_backref_cache_entry *entry
2728 = mctx->bkref_ents + cache_idx;
2730 if (entry->node == bkref_node)
2731 return REG_NOERROR; /* We already checked it. */
2732 while (entry++->more);
2735 subexp_num = dfa->nodes[bkref_node].opr.idx;
2737 /* For each sub expression */
2738 for (sub_top_idx = 0; sub_top_idx < mctx->nsub_tops; ++sub_top_idx)
2741 re_sub_match_top_t *sub_top = mctx->sub_tops[sub_top_idx];
2742 re_sub_match_last_t *sub_last;
2743 Idx sub_last_idx, sl_str, bkref_str_off;
2745 if (dfa->nodes[sub_top->node].opr.idx != subexp_num)
2746 continue; /* It isn't related. */
2748 sl_str = sub_top->str_idx;
2749 bkref_str_off = bkref_str_idx;
2750 /* At first, check the last node of sub expressions we already
2752 for (sub_last_idx = 0; sub_last_idx < sub_top->nlasts; ++sub_last_idx)
2754 regoff_t sl_str_diff;
2755 sub_last = sub_top->lasts[sub_last_idx];
2756 sl_str_diff = sub_last->str_idx - sl_str;
2757 /* The matched string by the sub expression match with the substring
2758 at the back reference? */
2759 if (sl_str_diff > 0)
2761 if (BE (bkref_str_off + sl_str_diff > mctx->input.valid_len, 0))
2763 /* Not enough chars for a successful match. */
2764 if (bkref_str_off + sl_str_diff > mctx->input.len)
2767 err = clean_state_log_if_needed (mctx,
2770 if (BE (err != REG_NOERROR, 0))
2772 buf = (const char *) re_string_get_buffer (&mctx->input);
2774 if (memcmp (buf + bkref_str_off, buf + sl_str, sl_str_diff) != 0)
2775 /* We don't need to search this sub expression any more. */
2778 bkref_str_off += sl_str_diff;
2779 sl_str += sl_str_diff;
2780 err = get_subexp_sub (mctx, sub_top, sub_last, bkref_node,
2783 /* Reload buf, since the preceding call might have reallocated
2785 buf = (const char *) re_string_get_buffer (&mctx->input);
2787 if (err == REG_NOMATCH)
2789 if (BE (err != REG_NOERROR, 0))
2793 if (sub_last_idx < sub_top->nlasts)
2795 if (sub_last_idx > 0)
2797 /* Then, search for the other last nodes of the sub expression. */
2798 for (; sl_str <= bkref_str_idx; ++sl_str)
2801 regoff_t sl_str_off;
2802 const re_node_set *nodes;
2803 sl_str_off = sl_str - sub_top->str_idx;
2804 /* The matched string by the sub expression match with the substring
2805 at the back reference? */
2808 if (BE (bkref_str_off >= mctx->input.valid_len, 0))
2810 /* If we are at the end of the input, we cannot match. */
2811 if (bkref_str_off >= mctx->input.len)
2814 err = extend_buffers (mctx, bkref_str_off + 1);
2815 if (BE (err != REG_NOERROR, 0))
2818 buf = (const char *) re_string_get_buffer (&mctx->input);
2820 if (buf [bkref_str_off++] != buf[sl_str - 1])
2821 break; /* We don't need to search this sub expression
2824 if (mctx->state_log[sl_str] == NULL)
2826 /* Does this state have a ')' of the sub expression? */
2827 nodes = &mctx->state_log[sl_str]->nodes;
2828 cls_node = find_subexp_node (dfa, nodes, subexp_num,
2830 if (cls_node == REG_MISSING)
2832 if (sub_top->path == NULL)
2834 sub_top->path = calloc (sizeof (state_array_t),
2835 sl_str - sub_top->str_idx + 1);
2836 if (sub_top->path == NULL)
2839 /* Can the OP_OPEN_SUBEXP node arrive the OP_CLOSE_SUBEXP node
2840 in the current context? */
2841 err = check_arrival (mctx, sub_top->path, sub_top->node,
2842 sub_top->str_idx, cls_node, sl_str,
2844 if (err == REG_NOMATCH)
2846 if (BE (err != REG_NOERROR, 0))
2848 sub_last = match_ctx_add_sublast (sub_top, cls_node, sl_str);
2849 if (BE (sub_last == NULL, 0))
2851 err = get_subexp_sub (mctx, sub_top, sub_last, bkref_node,
2853 if (err == REG_NOMATCH)
2860 /* Helper functions for get_subexp(). */
2862 /* Check SUB_LAST can arrive to the back reference BKREF_NODE at BKREF_STR.
2863 If it can arrive, register the sub expression expressed with SUB_TOP
2866 static reg_errcode_t
2868 get_subexp_sub (re_match_context_t *mctx, const re_sub_match_top_t *sub_top,
2869 re_sub_match_last_t *sub_last, Idx bkref_node, Idx bkref_str)
2873 /* Can the subexpression arrive the back reference? */
2874 err = check_arrival (mctx, &sub_last->path, sub_last->node,
2875 sub_last->str_idx, bkref_node, bkref_str,
2877 if (err != REG_NOERROR)
2879 err = match_ctx_add_entry (mctx, bkref_node, bkref_str, sub_top->str_idx,
2881 if (BE (err != REG_NOERROR, 0))
2883 to_idx = bkref_str + sub_last->str_idx - sub_top->str_idx;
2884 return clean_state_log_if_needed (mctx, to_idx);
2887 /* Find the first node which is '(' or ')' and whose index is SUBEXP_IDX.
2888 Search '(' if FL_OPEN, or search ')' otherwise.
2889 TODO: This function isn't efficient...
2890 Because there might be more than one nodes whose types are
2891 OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
2897 find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
2898 Idx subexp_idx, int type)
2901 for (cls_idx = 0; cls_idx < nodes->nelem; ++cls_idx)
2903 Idx cls_node = nodes->elems[cls_idx];
2904 const re_token_t *node = dfa->nodes + cls_node;
2905 if (node->type == type
2906 && node->opr.idx == subexp_idx)
2912 /* Check whether the node TOP_NODE at TOP_STR can arrive to the node
2913 LAST_NODE at LAST_STR. We record the path onto PATH since it will be
2915 Return REG_NOERROR if it can arrive, or REG_NOMATCH otherwise. */
2917 static reg_errcode_t
2918 internal_function __attribute_warn_unused_result__
2919 check_arrival (re_match_context_t *mctx, state_array_t *path, Idx top_node,
2920 Idx top_str, Idx last_node, Idx last_str, int type)
2922 const re_dfa_t *const dfa = mctx->dfa;
2923 reg_errcode_t err = REG_NOERROR;
2924 Idx subexp_num, backup_cur_idx, str_idx, null_cnt;
2925 re_dfastate_t *cur_state = NULL;
2926 re_node_set *cur_nodes, next_nodes;
2927 re_dfastate_t **backup_state_log;
2928 unsigned int context;
2930 subexp_num = dfa->nodes[top_node].opr.idx;
2931 /* Extend the buffer if we need. */
2932 if (BE (path->alloc < last_str + mctx->max_mb_elem_len + 1, 0))
2934 re_dfastate_t **new_array;
2935 Idx old_alloc = path->alloc;
2936 Idx incr_alloc = last_str + mctx->max_mb_elem_len + 1;
2938 if (BE (IDX_MAX - old_alloc < incr_alloc, 0))
2940 new_alloc = old_alloc + incr_alloc;
2941 if (BE (SIZE_MAX / sizeof (re_dfastate_t *) < new_alloc, 0))
2943 new_array = re_realloc (path->array, re_dfastate_t *, new_alloc);
2944 if (BE (new_array == NULL, 0))
2946 path->array = new_array;
2947 path->alloc = new_alloc;
2948 memset (new_array + old_alloc, '\0',
2949 sizeof (re_dfastate_t *) * (path->alloc - old_alloc));
2952 str_idx = path->next_idx ? path->next_idx : top_str;
2954 /* Temporary modify MCTX. */
2955 backup_state_log = mctx->state_log;
2956 backup_cur_idx = mctx->input.cur_idx;
2957 mctx->state_log = path->array;
2958 mctx->input.cur_idx = str_idx;
2960 /* Setup initial node set. */
2961 context = re_string_context_at (&mctx->input, str_idx - 1, mctx->eflags);
2962 if (str_idx == top_str)
2964 err = re_node_set_init_1 (&next_nodes, top_node);
2965 if (BE (err != REG_NOERROR, 0))
2967 err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
2968 if (BE (err != REG_NOERROR, 0))
2970 re_node_set_free (&next_nodes);
2976 cur_state = mctx->state_log[str_idx];
2977 if (cur_state && cur_state->has_backref)
2979 err = re_node_set_init_copy (&next_nodes, &cur_state->nodes);
2980 if (BE (err != REG_NOERROR, 0))
2984 re_node_set_init_empty (&next_nodes);
2986 if (str_idx == top_str || (cur_state && cur_state->has_backref))
2988 if (next_nodes.nelem)
2990 err = expand_bkref_cache (mctx, &next_nodes, str_idx,
2992 if (BE (err != REG_NOERROR, 0))
2994 re_node_set_free (&next_nodes);
2998 cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
2999 if (BE (cur_state == NULL && err != REG_NOERROR, 0))
3001 re_node_set_free (&next_nodes);
3004 mctx->state_log[str_idx] = cur_state;
3007 for (null_cnt = 0; str_idx < last_str && null_cnt <= mctx->max_mb_elem_len;)
3009 re_node_set_empty (&next_nodes);
3010 if (mctx->state_log[str_idx + 1])
3012 err = re_node_set_merge (&next_nodes,
3013 &mctx->state_log[str_idx + 1]->nodes);
3014 if (BE (err != REG_NOERROR, 0))
3016 re_node_set_free (&next_nodes);
3022 err = check_arrival_add_next_nodes (mctx, str_idx,
3023 &cur_state->non_eps_nodes,
3025 if (BE (err != REG_NOERROR, 0))
3027 re_node_set_free (&next_nodes);
3032 if (next_nodes.nelem)
3034 err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
3035 if (BE (err != REG_NOERROR, 0))
3037 re_node_set_free (&next_nodes);
3040 err = expand_bkref_cache (mctx, &next_nodes, str_idx,
3042 if (BE (err != REG_NOERROR, 0))
3044 re_node_set_free (&next_nodes);
3048 context = re_string_context_at (&mctx->input, str_idx - 1, mctx->eflags);
3049 cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
3050 if (BE (cur_state == NULL && err != REG_NOERROR, 0))
3052 re_node_set_free (&next_nodes);
3055 mctx->state_log[str_idx] = cur_state;
3056 null_cnt = cur_state == NULL ? null_cnt + 1 : 0;
3058 re_node_set_free (&next_nodes);
3059 cur_nodes = (mctx->state_log[last_str] == NULL ? NULL
3060 : &mctx->state_log[last_str]->nodes);
3061 path->next_idx = str_idx;
3064 mctx->state_log = backup_state_log;
3065 mctx->input.cur_idx = backup_cur_idx;
3067 /* Then check the current node set has the node LAST_NODE. */
3068 if (cur_nodes != NULL && re_node_set_contains (cur_nodes, last_node))
3074 /* Helper functions for check_arrival. */
3076 /* Calculate the destination nodes of CUR_NODES at STR_IDX, and append them
3078 TODO: This function is similar to the functions transit_state*(),
3079 however this function has many additional works.
3080 Can't we unify them? */
3082 static reg_errcode_t
3083 internal_function __attribute_warn_unused_result__
3084 check_arrival_add_next_nodes (re_match_context_t *mctx, Idx str_idx,
3085 re_node_set *cur_nodes, re_node_set *next_nodes)
3087 const re_dfa_t *const dfa = mctx->dfa;
3090 #ifdef RE_ENABLE_I18N
3091 reg_errcode_t err = REG_NOERROR;
3093 re_node_set union_set;
3094 re_node_set_init_empty (&union_set);
3095 for (cur_idx = 0; cur_idx < cur_nodes->nelem; ++cur_idx)
3098 Idx cur_node = cur_nodes->elems[cur_idx];
3100 re_token_type_t type = dfa->nodes[cur_node].type;
3101 assert (!IS_EPSILON_NODE (type));
3103 #ifdef RE_ENABLE_I18N
3104 /* If the node may accept "multi byte". */
3105 if (dfa->nodes[cur_node].accept_mb)
3107 naccepted = check_node_accept_bytes (dfa, cur_node, &mctx->input,
3111 re_dfastate_t *dest_state;
3112 Idx next_node = dfa->nexts[cur_node];
3113 Idx next_idx = str_idx + naccepted;
3114 dest_state = mctx->state_log[next_idx];
3115 re_node_set_empty (&union_set);
3118 err = re_node_set_merge (&union_set, &dest_state->nodes);
3119 if (BE (err != REG_NOERROR, 0))
3121 re_node_set_free (&union_set);
3125 ok = re_node_set_insert (&union_set, next_node);
3128 re_node_set_free (&union_set);
3131 mctx->state_log[next_idx] = re_acquire_state (&err, dfa,
3133 if (BE (mctx->state_log[next_idx] == NULL
3134 && err != REG_NOERROR, 0))
3136 re_node_set_free (&union_set);
3141 #endif /* RE_ENABLE_I18N */
3143 || check_node_accept (mctx, dfa->nodes + cur_node, str_idx))
3145 ok = re_node_set_insert (next_nodes, dfa->nexts[cur_node]);
3148 re_node_set_free (&union_set);
3153 re_node_set_free (&union_set);
3157 /* For all the nodes in CUR_NODES, add the epsilon closures of them to
3158 CUR_NODES, however exclude the nodes which are:
3159 - inside the sub expression whose number is EX_SUBEXP, if FL_OPEN.
3160 - out of the sub expression whose number is EX_SUBEXP, if !FL_OPEN.
3163 static reg_errcode_t
3165 check_arrival_expand_ecl (const re_dfa_t *dfa, re_node_set *cur_nodes,
3166 Idx ex_subexp, int type)
3169 Idx idx, outside_node;
3170 re_node_set new_nodes;
3172 assert (cur_nodes->nelem);
3174 err = re_node_set_alloc (&new_nodes, cur_nodes->nelem);
3175 if (BE (err != REG_NOERROR, 0))
3177 /* Create a new node set NEW_NODES with the nodes which are epsilon
3178 closures of the node in CUR_NODES. */
3180 for (idx = 0; idx < cur_nodes->nelem; ++idx)
3182 Idx cur_node = cur_nodes->elems[idx];
3183 const re_node_set *eclosure = dfa->eclosures + cur_node;
3184 outside_node = find_subexp_node (dfa, eclosure, ex_subexp, type);
3185 if (outside_node == REG_MISSING)
3187 /* There are no problematic nodes, just merge them. */
3188 err = re_node_set_merge (&new_nodes, eclosure);
3189 if (BE (err != REG_NOERROR, 0))
3191 re_node_set_free (&new_nodes);
3197 /* There are problematic nodes, re-calculate incrementally. */
3198 err = check_arrival_expand_ecl_sub (dfa, &new_nodes, cur_node,
3200 if (BE (err != REG_NOERROR, 0))
3202 re_node_set_free (&new_nodes);
3207 re_node_set_free (cur_nodes);
3208 *cur_nodes = new_nodes;
3212 /* Helper function for check_arrival_expand_ecl.
3213 Check incrementally the epsilon closure of TARGET, and if it isn't
3214 problematic append it to DST_NODES. */
3216 static reg_errcode_t
3217 internal_function __attribute_warn_unused_result__
3218 check_arrival_expand_ecl_sub (const re_dfa_t *dfa, re_node_set *dst_nodes,
3219 Idx target, Idx ex_subexp, int type)
3222 for (cur_node = target; !re_node_set_contains (dst_nodes, cur_node);)
3226 if (dfa->nodes[cur_node].type == type
3227 && dfa->nodes[cur_node].opr.idx == ex_subexp)
3229 if (type == OP_CLOSE_SUBEXP)
3231 ok = re_node_set_insert (dst_nodes, cur_node);
3237 ok = re_node_set_insert (dst_nodes, cur_node);
3240 if (dfa->edests[cur_node].nelem == 0)
3242 if (dfa->edests[cur_node].nelem == 2)
3245 err = check_arrival_expand_ecl_sub (dfa, dst_nodes,
3246 dfa->edests[cur_node].elems[1],
3248 if (BE (err != REG_NOERROR, 0))
3251 cur_node = dfa->edests[cur_node].elems[0];
3257 /* For all the back references in the current state, calculate the
3258 destination of the back references by the appropriate entry
3259 in MCTX->BKREF_ENTS. */
3261 static reg_errcode_t
3262 internal_function __attribute_warn_unused_result__
3263 expand_bkref_cache (re_match_context_t *mctx, re_node_set *cur_nodes,
3264 Idx cur_str, Idx subexp_num, int type)
3266 const re_dfa_t *const dfa = mctx->dfa;
3268 Idx cache_idx_start = search_cur_bkref_entry (mctx, cur_str);
3269 struct re_backref_cache_entry *ent;
3271 if (cache_idx_start == REG_MISSING)
3275 ent = mctx->bkref_ents + cache_idx_start;
3278 Idx to_idx, next_node;
3280 /* Is this entry ENT is appropriate? */
3281 if (!re_node_set_contains (cur_nodes, ent->node))
3284 to_idx = cur_str + ent->subexp_to - ent->subexp_from;
3285 /* Calculate the destination of the back reference, and append it
3286 to MCTX->STATE_LOG. */
3287 if (to_idx == cur_str)
3289 /* The backreference did epsilon transit, we must re-check all the
3290 node in the current state. */
3291 re_node_set new_dests;
3292 reg_errcode_t err2, err3;
3293 next_node = dfa->edests[ent->node].elems[0];
3294 if (re_node_set_contains (cur_nodes, next_node))
3296 err = re_node_set_init_1 (&new_dests, next_node);
3297 err2 = check_arrival_expand_ecl (dfa, &new_dests, subexp_num, type);
3298 err3 = re_node_set_merge (cur_nodes, &new_dests);
3299 re_node_set_free (&new_dests);
3300 if (BE (err != REG_NOERROR || err2 != REG_NOERROR
3301 || err3 != REG_NOERROR, 0))
3303 err = (err != REG_NOERROR ? err
3304 : (err2 != REG_NOERROR ? err2 : err3));
3307 /* TODO: It is still inefficient... */
3312 re_node_set union_set;
3313 next_node = dfa->nexts[ent->node];
3314 if (mctx->state_log[to_idx])
3317 if (re_node_set_contains (&mctx->state_log[to_idx]->nodes,
3320 err = re_node_set_init_copy (&union_set,
3321 &mctx->state_log[to_idx]->nodes);
3322 ok = re_node_set_insert (&union_set, next_node);
3323 if (BE (err != REG_NOERROR || ! ok, 0))
3325 re_node_set_free (&union_set);
3326 err = err != REG_NOERROR ? err : REG_ESPACE;
3332 err = re_node_set_init_1 (&union_set, next_node);
3333 if (BE (err != REG_NOERROR, 0))
3336 mctx->state_log[to_idx] = re_acquire_state (&err, dfa, &union_set);
3337 re_node_set_free (&union_set);
3338 if (BE (mctx->state_log[to_idx] == NULL
3339 && err != REG_NOERROR, 0))
3343 while (ent++->more);
3347 /* Build transition table for the state.
3348 Return true if successful. */
3352 build_trtable (const re_dfa_t *dfa, re_dfastate_t *state)
3357 bool need_word_trtable = false;
3358 bitset_word_t elem, mask;
3359 bool dests_node_malloced = false;
3360 bool dest_states_malloced = false;
3361 Idx ndests; /* Number of the destination states from 'state'. */
3362 re_dfastate_t **trtable;
3363 re_dfastate_t **dest_states = NULL, **dest_states_word, **dest_states_nl;
3364 re_node_set follows, *dests_node;
3366 bitset_t acceptable;
3370 re_node_set dests_node[SBC_MAX];
3371 bitset_t dests_ch[SBC_MAX];
3374 /* We build DFA states which corresponds to the destination nodes
3375 from 'state'. 'dests_node[i]' represents the nodes which i-th
3376 destination state contains, and 'dests_ch[i]' represents the
3377 characters which i-th destination state accepts. */
3378 if (__libc_use_alloca (sizeof (struct dests_alloc)))
3379 dests_alloc = (struct dests_alloc *) alloca (sizeof (struct dests_alloc));
3382 dests_alloc = re_malloc (struct dests_alloc, 1);
3383 if (BE (dests_alloc == NULL, 0))
3385 dests_node_malloced = true;
3387 dests_node = dests_alloc->dests_node;
3388 dests_ch = dests_alloc->dests_ch;
3390 /* Initialize transition table. */
3391 state->word_trtable = state->trtable = NULL;
3393 /* At first, group all nodes belonging to 'state' into several
3395 ndests = group_nodes_into_DFAstates (dfa, state, dests_node, dests_ch);
3396 if (BE (! REG_VALID_NONZERO_INDEX (ndests), 0))
3398 if (dests_node_malloced)
3400 /* Return false in case of an error, true otherwise. */
3403 state->trtable = (re_dfastate_t **)
3404 calloc (sizeof (re_dfastate_t *), SBC_MAX);
3405 if (BE (state->trtable == NULL, 0))
3412 err = re_node_set_alloc (&follows, ndests + 1);
3413 if (BE (err != REG_NOERROR, 0))
3416 /* Avoid arithmetic overflow in size calculation. */
3417 if (BE ((((SIZE_MAX - (sizeof (re_node_set) + sizeof (bitset_t)) * SBC_MAX)
3418 / (3 * sizeof (re_dfastate_t *)))
3423 if (__libc_use_alloca ((sizeof (re_node_set) + sizeof (bitset_t)) * SBC_MAX
3424 + ndests * 3 * sizeof (re_dfastate_t *)))
3425 dest_states = (re_dfastate_t **)
3426 alloca (ndests * 3 * sizeof (re_dfastate_t *));
3429 dest_states = (re_dfastate_t **)
3430 malloc (ndests * 3 * sizeof (re_dfastate_t *));
3431 if (BE (dest_states == NULL, 0))
3434 if (dest_states_malloced)
3436 re_node_set_free (&follows);
3437 for (i = 0; i < ndests; ++i)
3438 re_node_set_free (dests_node + i);
3439 if (dests_node_malloced)
3443 dest_states_malloced = true;
3445 dest_states_word = dest_states + ndests;
3446 dest_states_nl = dest_states_word + ndests;
3447 bitset_empty (acceptable);
3449 /* Then build the states for all destinations. */
3450 for (i = 0; i < ndests; ++i)
3453 re_node_set_empty (&follows);
3454 /* Merge the follows of this destination states. */
3455 for (j = 0; j < dests_node[i].nelem; ++j)
3457 next_node = dfa->nexts[dests_node[i].elems[j]];
3458 if (next_node != REG_MISSING)
3460 err = re_node_set_merge (&follows, dfa->eclosures + next_node);
3461 if (BE (err != REG_NOERROR, 0))
3465 dest_states[i] = re_acquire_state_context (&err, dfa, &follows, 0);
3466 if (BE (dest_states[i] == NULL && err != REG_NOERROR, 0))
3468 /* If the new state has context constraint,
3469 build appropriate states for these contexts. */
3470 if (dest_states[i]->has_constraint)
3472 dest_states_word[i] = re_acquire_state_context (&err, dfa, &follows,
3474 if (BE (dest_states_word[i] == NULL && err != REG_NOERROR, 0))
3477 if (dest_states[i] != dest_states_word[i] && dfa->mb_cur_max > 1)
3478 need_word_trtable = true;
3480 dest_states_nl[i] = re_acquire_state_context (&err, dfa, &follows,
3482 if (BE (dest_states_nl[i] == NULL && err != REG_NOERROR, 0))
3487 dest_states_word[i] = dest_states[i];
3488 dest_states_nl[i] = dest_states[i];
3490 bitset_merge (acceptable, dests_ch[i]);
3493 if (!BE (need_word_trtable, 0))
3495 /* We don't care about whether the following character is a word
3496 character, or we are in a single-byte character set so we can
3497 discern by looking at the character code: allocate a
3498 256-entry transition table. */
3499 trtable = state->trtable =
3500 (re_dfastate_t **) calloc (sizeof (re_dfastate_t *), SBC_MAX);
3501 if (BE (trtable == NULL, 0))
3504 /* For all characters ch...: */
3505 for (i = 0; i < BITSET_WORDS; ++i)
3506 for (ch = i * BITSET_WORD_BITS, elem = acceptable[i], mask = 1;
3508 mask <<= 1, elem >>= 1, ++ch)
3509 if (BE (elem & 1, 0))
3511 /* There must be exactly one destination which accepts
3512 character ch. See group_nodes_into_DFAstates. */
3513 for (j = 0; (dests_ch[j][i] & mask) == 0; ++j)
3516 /* j-th destination accepts the word character ch. */
3517 if (dfa->word_char[i] & mask)
3518 trtable[ch] = dest_states_word[j];
3520 trtable[ch] = dest_states[j];
3525 /* We care about whether the following character is a word
3526 character, and we are in a multi-byte character set: discern
3527 by looking at the character code: build two 256-entry
3528 transition tables, one starting at trtable[0] and one
3529 starting at trtable[SBC_MAX]. */
3530 trtable = state->word_trtable =
3531 (re_dfastate_t **) calloc (sizeof (re_dfastate_t *), 2 * SBC_MAX);
3532 if (BE (trtable == NULL, 0))
3535 /* For all characters ch...: */
3536 for (i = 0; i < BITSET_WORDS; ++i)
3537 for (ch = i * BITSET_WORD_BITS, elem = acceptable[i], mask = 1;
3539 mask <<= 1, elem >>= 1, ++ch)
3540 if (BE (elem & 1, 0))
3542 /* There must be exactly one destination which accepts
3543 character ch. See group_nodes_into_DFAstates. */
3544 for (j = 0; (dests_ch[j][i] & mask) == 0; ++j)
3547 /* j-th destination accepts the word character ch. */
3548 trtable[ch] = dest_states[j];
3549 trtable[ch + SBC_MAX] = dest_states_word[j];
3554 if (bitset_contain (acceptable, NEWLINE_CHAR))
3556 /* The current state accepts newline character. */
3557 for (j = 0; j < ndests; ++j)
3558 if (bitset_contain (dests_ch[j], NEWLINE_CHAR))
3560 /* k-th destination accepts newline character. */
3561 trtable[NEWLINE_CHAR] = dest_states_nl[j];
3562 if (need_word_trtable)
3563 trtable[NEWLINE_CHAR + SBC_MAX] = dest_states_nl[j];
3564 /* There must be only one destination which accepts
3565 newline. See group_nodes_into_DFAstates. */
3570 if (dest_states_malloced)
3573 re_node_set_free (&follows);
3574 for (i = 0; i < ndests; ++i)
3575 re_node_set_free (dests_node + i);
3577 if (dests_node_malloced)
3583 /* Group all nodes belonging to STATE into several destinations.
3584 Then for all destinations, set the nodes belonging to the destination
3585 to DESTS_NODE[i] and set the characters accepted by the destination
3586 to DEST_CH[i]. This function return the number of destinations. */
3590 group_nodes_into_DFAstates (const re_dfa_t *dfa, const re_dfastate_t *state,
3591 re_node_set *dests_node, bitset_t *dests_ch)
3596 Idx ndests; /* Number of the destinations from 'state'. */
3597 bitset_t accepts; /* Characters a node can accept. */
3598 const re_node_set *cur_nodes = &state->nodes;
3599 bitset_empty (accepts);
3602 /* For all the nodes belonging to 'state', */
3603 for (i = 0; i < cur_nodes->nelem; ++i)
3605 re_token_t *node = &dfa->nodes[cur_nodes->elems[i]];
3606 re_token_type_t type = node->type;
3607 unsigned int constraint = node->constraint;
3609 /* Enumerate all single byte character this node can accept. */
3610 if (type == CHARACTER)
3611 bitset_set (accepts, node->opr.c);
3612 else if (type == SIMPLE_BRACKET)
3614 bitset_merge (accepts, node->opr.sbcset);
3616 else if (type == OP_PERIOD)
3618 #ifdef RE_ENABLE_I18N
3619 if (dfa->mb_cur_max > 1)
3620 bitset_merge (accepts, dfa->sb_char);
3623 bitset_set_all (accepts);
3624 if (!(dfa->syntax & RE_DOT_NEWLINE))
3625 bitset_clear (accepts, '\n');
3626 if (dfa->syntax & RE_DOT_NOT_NULL)
3627 bitset_clear (accepts, '\0');
3629 #ifdef RE_ENABLE_I18N
3630 else if (type == OP_UTF8_PERIOD)
3632 if (ASCII_CHARS % BITSET_WORD_BITS == 0)
3633 memset (accepts, -1, ASCII_CHARS / CHAR_BIT);
3635 bitset_merge (accepts, utf8_sb_map);
3636 if (!(dfa->syntax & RE_DOT_NEWLINE))
3637 bitset_clear (accepts, '\n');
3638 if (dfa->syntax & RE_DOT_NOT_NULL)
3639 bitset_clear (accepts, '\0');
3645 /* Check the 'accepts' and sift the characters which are not
3646 match it the context. */
3649 if (constraint & NEXT_NEWLINE_CONSTRAINT)
3651 bool accepts_newline = bitset_contain (accepts, NEWLINE_CHAR);
3652 bitset_empty (accepts);
3653 if (accepts_newline)
3654 bitset_set (accepts, NEWLINE_CHAR);
3658 if (constraint & NEXT_ENDBUF_CONSTRAINT)
3660 bitset_empty (accepts);
3664 if (constraint & NEXT_WORD_CONSTRAINT)
3666 bitset_word_t any_set = 0;
3667 if (type == CHARACTER && !node->word_char)
3669 bitset_empty (accepts);
3672 #ifdef RE_ENABLE_I18N
3673 if (dfa->mb_cur_max > 1)
3674 for (j = 0; j < BITSET_WORDS; ++j)
3675 any_set |= (accepts[j] &= (dfa->word_char[j] | ~dfa->sb_char[j]));
3678 for (j = 0; j < BITSET_WORDS; ++j)
3679 any_set |= (accepts[j] &= dfa->word_char[j]);
3683 if (constraint & NEXT_NOTWORD_CONSTRAINT)
3685 bitset_word_t any_set = 0;
3686 if (type == CHARACTER && node->word_char)
3688 bitset_empty (accepts);
3691 #ifdef RE_ENABLE_I18N
3692 if (dfa->mb_cur_max > 1)
3693 for (j = 0; j < BITSET_WORDS; ++j)
3694 any_set |= (accepts[j] &= ~(dfa->word_char[j] & dfa->sb_char[j]));
3697 for (j = 0; j < BITSET_WORDS; ++j)
3698 any_set |= (accepts[j] &= ~dfa->word_char[j]);
3704 /* Then divide 'accepts' into DFA states, or create a new
3705 state. Above, we make sure that accepts is not empty. */
3706 for (j = 0; j < ndests; ++j)
3708 bitset_t intersec; /* Intersection sets, see below. */
3710 /* Flags, see below. */
3711 bitset_word_t has_intersec, not_subset, not_consumed;
3713 /* Optimization, skip if this state doesn't accept the character. */
3714 if (type == CHARACTER && !bitset_contain (dests_ch[j], node->opr.c))
3717 /* Enumerate the intersection set of this state and 'accepts'. */
3719 for (k = 0; k < BITSET_WORDS; ++k)
3720 has_intersec |= intersec[k] = accepts[k] & dests_ch[j][k];
3721 /* And skip if the intersection set is empty. */
3725 /* Then check if this state is a subset of 'accepts'. */
3726 not_subset = not_consumed = 0;
3727 for (k = 0; k < BITSET_WORDS; ++k)
3729 not_subset |= remains[k] = ~accepts[k] & dests_ch[j][k];
3730 not_consumed |= accepts[k] = accepts[k] & ~dests_ch[j][k];
3733 /* If this state isn't a subset of 'accepts', create a
3734 new group state, which has the 'remains'. */
3737 bitset_copy (dests_ch[ndests], remains);
3738 bitset_copy (dests_ch[j], intersec);
3739 err = re_node_set_init_copy (dests_node + ndests, &dests_node[j]);
3740 if (BE (err != REG_NOERROR, 0))
3745 /* Put the position in the current group. */
3746 ok = re_node_set_insert (&dests_node[j], cur_nodes->elems[i]);
3750 /* If all characters are consumed, go to next node. */
3754 /* Some characters remain, create a new group. */
3757 bitset_copy (dests_ch[ndests], accepts);
3758 err = re_node_set_init_1 (dests_node + ndests, cur_nodes->elems[i]);
3759 if (BE (err != REG_NOERROR, 0))
3762 bitset_empty (accepts);
3767 for (j = 0; j < ndests; ++j)
3768 re_node_set_free (dests_node + j);
3772 #ifdef RE_ENABLE_I18N
3773 /* Check how many bytes the node 'dfa->nodes[node_idx]' accepts.
3774 Return the number of the bytes the node accepts.
3775 STR_IDX is the current index of the input string.
3777 This function handles the nodes which can accept one character, or
3778 one collating element like '.', '[a-z]', opposite to the other nodes
3779 can only accept one byte. */
3783 check_node_accept_bytes (const re_dfa_t *dfa, Idx node_idx,
3784 const re_string_t *input, Idx str_idx)
3786 const re_token_t *node = dfa->nodes + node_idx;
3787 int char_len, elem_len;
3790 if (BE (node->type == OP_UTF8_PERIOD, 0))
3792 unsigned char c = re_string_byte_at (input, str_idx), d;
3793 if (BE (c < 0xc2, 1))
3796 if (str_idx + 2 > input->len)
3799 d = re_string_byte_at (input, str_idx + 1);
3801 return (d < 0x80 || d > 0xbf) ? 0 : 2;
3805 if (c == 0xe0 && d < 0xa0)
3811 if (c == 0xf0 && d < 0x90)
3817 if (c == 0xf8 && d < 0x88)
3823 if (c == 0xfc && d < 0x84)
3829 if (str_idx + char_len > input->len)
3832 for (i = 1; i < char_len; ++i)
3834 d = re_string_byte_at (input, str_idx + i);
3835 if (d < 0x80 || d > 0xbf)
3841 char_len = re_string_char_size_at (input, str_idx);
3842 if (node->type == OP_PERIOD)
3846 /* FIXME: I don't think this if is needed, as both '\n'
3847 and '\0' are char_len == 1. */
3848 /* '.' accepts any one character except the following two cases. */
3849 if ((!(dfa->syntax & RE_DOT_NEWLINE) &&
3850 re_string_byte_at (input, str_idx) == '\n') ||
3851 ((dfa->syntax & RE_DOT_NOT_NULL) &&
3852 re_string_byte_at (input, str_idx) == '\0'))
3857 elem_len = re_string_elem_size_at (input, str_idx);
3858 if ((elem_len <= 1 && char_len <= 1) || char_len == 0)
3861 if (node->type == COMPLEX_BRACKET)
3863 const re_charset_t *cset = node->opr.mbcset;
3865 const unsigned char *pin
3866 = ((const unsigned char *) re_string_get_buffer (input) + str_idx);
3871 wchar_t wc = ((cset->nranges || cset->nchar_classes || cset->nmbchars)
3872 ? re_string_wchar_at (input, str_idx) : 0);
3874 /* match with multibyte character? */
3875 for (i = 0; i < cset->nmbchars; ++i)
3876 if (wc == cset->mbchars[i])
3878 match_len = char_len;
3879 goto check_node_accept_bytes_match;
3881 /* match with character_class? */
3882 for (i = 0; i < cset->nchar_classes; ++i)
3884 wctype_t wt = cset->char_classes[i];
3885 if (__iswctype (wc, wt))
3887 match_len = char_len;
3888 goto check_node_accept_bytes_match;
3893 nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
3896 unsigned int in_collseq = 0;
3897 const int32_t *table, *indirect;
3898 const unsigned char *weights, *extra;
3899 const char *collseqwc;
3900 /* This #include defines a local function! */
3901 # include <locale/weight.h>
3903 /* match with collating_symbol? */
3904 if (cset->ncoll_syms)
3905 extra = (const unsigned char *)
3906 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB);
3907 for (i = 0; i < cset->ncoll_syms; ++i)
3909 const unsigned char *coll_sym = extra + cset->coll_syms[i];
3910 /* Compare the length of input collating element and
3911 the length of current collating element. */
3912 if (*coll_sym != elem_len)
3914 /* Compare each bytes. */
3915 for (j = 0; j < *coll_sym; j++)
3916 if (pin[j] != coll_sym[1 + j])
3920 /* Match if every bytes is equal. */
3922 goto check_node_accept_bytes_match;
3928 if (elem_len <= char_len)
3930 collseqwc = _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQWC);
3931 in_collseq = __collseq_table_lookup (collseqwc, wc);
3934 in_collseq = find_collation_sequence_value (pin, elem_len);
3936 /* match with range expression? */
3937 /* FIXME: Implement rational ranges here, too. */
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 for (i = 0; i < cset->nranges; ++i)
3991 if (cset->range_starts[i] <= wc && wc <= cset->range_ends[i])
3993 match_len = char_len;
3994 goto check_node_accept_bytes_match;
3998 check_node_accept_bytes_match:
3999 if (!cset->non_match)
4006 return (elem_len > char_len) ? elem_len : char_len;
4015 find_collation_sequence_value (const unsigned char *mbs, size_t mbs_len)
4017 uint32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
4022 /* No valid character. Match it as a single byte character. */
4023 const unsigned char *collseq = (const unsigned char *)
4024 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQMB);
4025 return collseq[mbs[0]];
4032 const unsigned char *extra = (const unsigned char *)
4033 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB);
4034 int32_t extrasize = (const unsigned char *)
4035 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB + 1) - extra;
4037 for (idx = 0; idx < extrasize;)
4041 int32_t elem_mbs_len;
4042 /* Skip the name of collating element name. */
4043 idx = idx + extra[idx] + 1;
4044 elem_mbs_len = extra[idx++];
4045 if (mbs_len == elem_mbs_len)
4047 for (mbs_cnt = 0; mbs_cnt < elem_mbs_len; ++mbs_cnt)
4048 if (extra[idx + mbs_cnt] != mbs[mbs_cnt])
4050 if (mbs_cnt == elem_mbs_len)
4051 /* Found the entry. */
4054 /* Skip the byte sequence of the collating element. */
4055 idx += elem_mbs_len;
4056 /* Adjust for the alignment. */
4057 idx = (idx + 3) & ~3;
4058 /* Skip the collation sequence value. */
4059 idx += sizeof (uint32_t);
4060 /* Skip the wide char sequence of the collating element. */
4061 idx = idx + sizeof (uint32_t) * (*(int32_t *) (extra + idx) + 1);
4062 /* If we found the entry, return the sequence value. */
4064 return *(uint32_t *) (extra + idx);
4065 /* Skip the collation sequence value. */
4066 idx += sizeof (uint32_t);
4072 #endif /* RE_ENABLE_I18N */
4074 /* Check whether the node accepts the byte which is IDX-th
4075 byte of the INPUT. */
4079 check_node_accept (const re_match_context_t *mctx, const re_token_t *node,
4083 ch = re_string_byte_at (&mctx->input, idx);
4087 if (node->opr.c != ch)
4091 case SIMPLE_BRACKET:
4092 if (!bitset_contain (node->opr.sbcset, ch))
4096 #ifdef RE_ENABLE_I18N
4097 case OP_UTF8_PERIOD:
4098 if (ch >= ASCII_CHARS)
4103 if ((ch == '\n' && !(mctx->dfa->syntax & RE_DOT_NEWLINE))
4104 || (ch == '\0' && (mctx->dfa->syntax & RE_DOT_NOT_NULL)))
4112 if (node->constraint)
4114 /* The node has constraints. Check whether the current context
4115 satisfies the constraints. */
4116 unsigned int context = re_string_context_at (&mctx->input, idx,
4118 if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
4125 /* Extend the buffers, if the buffers have run out. */
4127 static reg_errcode_t
4128 internal_function __attribute_warn_unused_result__
4129 extend_buffers (re_match_context_t *mctx, int min_len)
4132 re_string_t *pstr = &mctx->input;
4134 /* Avoid overflow. */
4135 if (BE (MIN (IDX_MAX, SIZE_MAX / sizeof (re_dfastate_t *)) / 2
4136 <= pstr->bufs_len, 0))
4139 /* Double the lengths of the buffers, but allocate at least MIN_LEN. */
4140 ret = re_string_realloc_buffers (pstr,
4142 MIN (pstr->len, pstr->bufs_len * 2)));
4143 if (BE (ret != REG_NOERROR, 0))
4146 if (mctx->state_log != NULL)
4148 /* And double the length of state_log. */
4149 /* XXX We have no indication of the size of this buffer. If this
4150 allocation fail we have no indication that the state_log array
4151 does not have the right size. */
4152 re_dfastate_t **new_array = re_realloc (mctx->state_log, re_dfastate_t *,
4153 pstr->bufs_len + 1);
4154 if (BE (new_array == NULL, 0))
4156 mctx->state_log = new_array;
4159 /* Then reconstruct the buffers. */
4162 #ifdef RE_ENABLE_I18N
4163 if (pstr->mb_cur_max > 1)
4165 ret = build_wcs_upper_buffer (pstr);
4166 if (BE (ret != REG_NOERROR, 0))
4170 #endif /* RE_ENABLE_I18N */
4171 build_upper_buffer (pstr);
4175 #ifdef RE_ENABLE_I18N
4176 if (pstr->mb_cur_max > 1)
4177 build_wcs_buffer (pstr);
4179 #endif /* RE_ENABLE_I18N */
4181 if (pstr->trans != NULL)
4182 re_string_translate_buffer (pstr);
4189 /* Functions for matching context. */
4191 /* Initialize MCTX. */
4193 static reg_errcode_t
4194 internal_function __attribute_warn_unused_result__
4195 match_ctx_init (re_match_context_t *mctx, int eflags, Idx n)
4197 mctx->eflags = eflags;
4198 mctx->match_last = REG_MISSING;
4201 /* Avoid overflow. */
4202 size_t max_object_size =
4203 MAX (sizeof (struct re_backref_cache_entry),
4204 sizeof (re_sub_match_top_t *));
4205 if (BE (MIN (IDX_MAX, SIZE_MAX / max_object_size) < n, 0))
4208 mctx->bkref_ents = re_malloc (struct re_backref_cache_entry, n);
4209 mctx->sub_tops = re_malloc (re_sub_match_top_t *, n);
4210 if (BE (mctx->bkref_ents == NULL || mctx->sub_tops == NULL, 0))
4213 /* Already zero-ed by the caller.
4215 mctx->bkref_ents = NULL;
4216 mctx->nbkref_ents = 0;
4217 mctx->nsub_tops = 0; */
4218 mctx->abkref_ents = n;
4219 mctx->max_mb_elem_len = 1;
4220 mctx->asub_tops = n;
4224 /* Clean the entries which depend on the current input in MCTX.
4225 This function must be invoked when the matcher changes the start index
4226 of the input, or changes the input string. */
4230 match_ctx_clean (re_match_context_t *mctx)
4233 for (st_idx = 0; st_idx < mctx->nsub_tops; ++st_idx)
4236 re_sub_match_top_t *top = mctx->sub_tops[st_idx];
4237 for (sl_idx = 0; sl_idx < top->nlasts; ++sl_idx)
4239 re_sub_match_last_t *last = top->lasts[sl_idx];
4240 re_free (last->path.array);
4243 re_free (top->lasts);
4246 re_free (top->path->array);
4247 re_free (top->path);
4252 mctx->nsub_tops = 0;
4253 mctx->nbkref_ents = 0;
4256 /* Free all the memory associated with MCTX. */
4260 match_ctx_free (re_match_context_t *mctx)
4262 /* First, free all the memory associated with MCTX->SUB_TOPS. */
4263 match_ctx_clean (mctx);
4264 re_free (mctx->sub_tops);
4265 re_free (mctx->bkref_ents);
4268 /* Add a new backreference entry to MCTX.
4269 Note that we assume that caller never call this function with duplicate
4270 entry, and call with STR_IDX which isn't smaller than any existing entry.
4273 static reg_errcode_t
4274 internal_function __attribute_warn_unused_result__
4275 match_ctx_add_entry (re_match_context_t *mctx, Idx node, Idx str_idx, Idx from,
4278 if (mctx->nbkref_ents >= mctx->abkref_ents)
4280 struct re_backref_cache_entry* new_entry;
4281 new_entry = re_realloc (mctx->bkref_ents, struct re_backref_cache_entry,
4282 mctx->abkref_ents * 2);
4283 if (BE (new_entry == NULL, 0))
4285 re_free (mctx->bkref_ents);
4288 mctx->bkref_ents = new_entry;
4289 memset (mctx->bkref_ents + mctx->nbkref_ents, '\0',
4290 sizeof (struct re_backref_cache_entry) * mctx->abkref_ents);
4291 mctx->abkref_ents *= 2;
4293 if (mctx->nbkref_ents > 0
4294 && mctx->bkref_ents[mctx->nbkref_ents - 1].str_idx == str_idx)
4295 mctx->bkref_ents[mctx->nbkref_ents - 1].more = 1;
4297 mctx->bkref_ents[mctx->nbkref_ents].node = node;
4298 mctx->bkref_ents[mctx->nbkref_ents].str_idx = str_idx;
4299 mctx->bkref_ents[mctx->nbkref_ents].subexp_from = from;
4300 mctx->bkref_ents[mctx->nbkref_ents].subexp_to = to;
4302 /* This is a cache that saves negative results of check_dst_limits_calc_pos.
4303 If bit N is clear, means that this entry won't epsilon-transition to
4304 an OP_OPEN_SUBEXP or OP_CLOSE_SUBEXP for the N+1-th subexpression. If
4305 it is set, check_dst_limits_calc_pos_1 will recurse and try to find one
4308 A backreference does not epsilon-transition unless it is empty, so set
4309 to all zeros if FROM != TO. */
4310 mctx->bkref_ents[mctx->nbkref_ents].eps_reachable_subexps_map
4311 = (from == to ? -1 : 0);
4313 mctx->bkref_ents[mctx->nbkref_ents++].more = 0;
4314 if (mctx->max_mb_elem_len < to - from)
4315 mctx->max_mb_elem_len = to - from;
4319 /* Return the first entry with the same str_idx, or REG_MISSING if none is
4320 found. Note that MCTX->BKREF_ENTS is already sorted by MCTX->STR_IDX. */
4324 search_cur_bkref_entry (const re_match_context_t *mctx, Idx str_idx)
4326 Idx left, right, mid, last;
4327 last = right = mctx->nbkref_ents;
4328 for (left = 0; left < right;)
4330 mid = (left + right) / 2;
4331 if (mctx->bkref_ents[mid].str_idx < str_idx)
4336 if (left < last && mctx->bkref_ents[left].str_idx == str_idx)
4342 /* Register the node NODE, whose type is OP_OPEN_SUBEXP, and which matches
4345 static reg_errcode_t
4346 internal_function __attribute_warn_unused_result__
4347 match_ctx_add_subtop (re_match_context_t *mctx, Idx node, Idx str_idx)
4350 assert (mctx->sub_tops != NULL);
4351 assert (mctx->asub_tops > 0);
4353 if (BE (mctx->nsub_tops == mctx->asub_tops, 0))
4355 Idx new_asub_tops = mctx->asub_tops * 2;
4356 re_sub_match_top_t **new_array = re_realloc (mctx->sub_tops,
4357 re_sub_match_top_t *,
4359 if (BE (new_array == NULL, 0))
4361 mctx->sub_tops = new_array;
4362 mctx->asub_tops = new_asub_tops;
4364 mctx->sub_tops[mctx->nsub_tops] = calloc (1, sizeof (re_sub_match_top_t));
4365 if (BE (mctx->sub_tops[mctx->nsub_tops] == NULL, 0))
4367 mctx->sub_tops[mctx->nsub_tops]->node = node;
4368 mctx->sub_tops[mctx->nsub_tops++]->str_idx = str_idx;
4372 /* Register the node NODE, whose type is OP_CLOSE_SUBEXP, and which matches
4373 at STR_IDX, whose corresponding OP_OPEN_SUBEXP is SUB_TOP. */
4375 static re_sub_match_last_t *
4377 match_ctx_add_sublast (re_sub_match_top_t *subtop, Idx node, Idx str_idx)
4379 re_sub_match_last_t *new_entry;
4380 if (BE (subtop->nlasts == subtop->alasts, 0))
4382 Idx new_alasts = 2 * subtop->alasts + 1;
4383 re_sub_match_last_t **new_array = re_realloc (subtop->lasts,
4384 re_sub_match_last_t *,
4386 if (BE (new_array == NULL, 0))
4388 subtop->lasts = new_array;
4389 subtop->alasts = new_alasts;
4391 new_entry = calloc (1, sizeof (re_sub_match_last_t));
4392 if (BE (new_entry != NULL, 1))
4394 subtop->lasts[subtop->nlasts] = new_entry;
4395 new_entry->node = node;
4396 new_entry->str_idx = str_idx;
4404 sift_ctx_init (re_sift_context_t *sctx, re_dfastate_t **sifted_sts,
4405 re_dfastate_t **limited_sts, Idx last_node, Idx last_str_idx)
4407 sctx->sifted_states = sifted_sts;
4408 sctx->limited_states = limited_sts;
4409 sctx->last_node = last_node;
4410 sctx->last_str_idx = last_str_idx;
4411 re_node_set_init_empty (&sctx->limits);