1 /* Extended regular expression matching and search library.
2 Copyright (C) 2002-2013 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
4 Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>.
6 The GNU C Library is free software; you can redistribute it and/or
7 modify it under the terms of the GNU General Public
8 License as published by the Free Software Foundation; either
9 version 3 of the License, or (at your option) any later version.
11 The GNU C Library is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 General Public License for more details.
16 You should have received a copy of the GNU General Public
17 License along with the GNU C Library; if not, see
18 <http://www.gnu.org/licenses/>. */
20 static reg_errcode_t
match_ctx_init (re_match_context_t
*cache
, int eflags
,
21 Idx n
) internal_function
;
22 static void match_ctx_clean (re_match_context_t
*mctx
) internal_function
;
23 static void match_ctx_free (re_match_context_t
*cache
) internal_function
;
24 static reg_errcode_t
match_ctx_add_entry (re_match_context_t
*cache
, Idx node
,
25 Idx str_idx
, Idx from
, Idx to
)
27 static Idx
search_cur_bkref_entry (const re_match_context_t
*mctx
, Idx str_idx
)
29 static reg_errcode_t
match_ctx_add_subtop (re_match_context_t
*mctx
, Idx node
,
30 Idx str_idx
) internal_function
;
31 static re_sub_match_last_t
* match_ctx_add_sublast (re_sub_match_top_t
*subtop
,
32 Idx node
, Idx str_idx
)
34 static void sift_ctx_init (re_sift_context_t
*sctx
, re_dfastate_t
**sifted_sts
,
35 re_dfastate_t
**limited_sts
, Idx last_node
,
38 static reg_errcode_t
re_search_internal (const regex_t
*preg
,
39 const char *string
, Idx length
,
40 Idx start
, Idx last_start
, Idx stop
,
41 size_t nmatch
, regmatch_t pmatch
[],
42 int eflags
) internal_function
;
43 static regoff_t
re_search_2_stub (struct re_pattern_buffer
*bufp
,
44 const char *string1
, Idx length1
,
45 const char *string2
, Idx length2
,
46 Idx start
, regoff_t range
,
47 struct re_registers
*regs
,
48 Idx stop
, bool ret_len
) internal_function
;
49 static regoff_t
re_search_stub (struct re_pattern_buffer
*bufp
,
50 const char *string
, Idx length
, Idx start
,
51 regoff_t range
, Idx stop
,
52 struct re_registers
*regs
,
53 bool ret_len
) internal_function
;
54 static unsigned re_copy_regs (struct re_registers
*regs
, regmatch_t
*pmatch
,
55 Idx nregs
, int regs_allocated
) internal_function
;
56 static reg_errcode_t
prune_impossible_nodes (re_match_context_t
*mctx
)
58 static Idx
check_matching (re_match_context_t
*mctx
, bool fl_longest_match
,
59 Idx
*p_match_first
) internal_function
;
60 static Idx
check_halt_state_context (const re_match_context_t
*mctx
,
61 const re_dfastate_t
*state
, Idx idx
)
63 static void update_regs (const re_dfa_t
*dfa
, regmatch_t
*pmatch
,
64 regmatch_t
*prev_idx_match
, Idx cur_node
,
65 Idx cur_idx
, Idx nmatch
) internal_function
;
66 static reg_errcode_t
push_fail_stack (struct re_fail_stack_t
*fs
,
67 Idx str_idx
, Idx dest_node
, Idx nregs
,
69 re_node_set
*eps_via_nodes
)
71 static reg_errcode_t
set_regs (const regex_t
*preg
,
72 const re_match_context_t
*mctx
,
73 size_t nmatch
, regmatch_t
*pmatch
,
74 bool fl_backtrack
) internal_function
;
75 static reg_errcode_t
free_fail_stack_return (struct re_fail_stack_t
*fs
)
79 static int sift_states_iter_mb (const re_match_context_t
*mctx
,
80 re_sift_context_t
*sctx
,
81 Idx node_idx
, Idx str_idx
, Idx max_str_idx
)
83 #endif /* RE_ENABLE_I18N */
84 static reg_errcode_t
sift_states_backward (const re_match_context_t
*mctx
,
85 re_sift_context_t
*sctx
)
87 static reg_errcode_t
build_sifted_states (const re_match_context_t
*mctx
,
88 re_sift_context_t
*sctx
, Idx str_idx
,
89 re_node_set
*cur_dest
)
91 static reg_errcode_t
update_cur_sifted_state (const re_match_context_t
*mctx
,
92 re_sift_context_t
*sctx
,
94 re_node_set
*dest_nodes
)
96 static reg_errcode_t
add_epsilon_src_nodes (const re_dfa_t
*dfa
,
97 re_node_set
*dest_nodes
,
98 const re_node_set
*candidates
)
100 static bool check_dst_limits (const re_match_context_t
*mctx
,
101 const re_node_set
*limits
,
102 Idx dst_node
, Idx dst_idx
, Idx src_node
,
103 Idx src_idx
) internal_function
;
104 static int check_dst_limits_calc_pos_1 (const re_match_context_t
*mctx
,
105 int boundaries
, Idx subexp_idx
,
106 Idx from_node
, Idx bkref_idx
)
108 static int check_dst_limits_calc_pos (const re_match_context_t
*mctx
,
109 Idx limit
, Idx subexp_idx
,
110 Idx node
, Idx str_idx
,
111 Idx bkref_idx
) internal_function
;
112 static reg_errcode_t
check_subexp_limits (const re_dfa_t
*dfa
,
113 re_node_set
*dest_nodes
,
114 const re_node_set
*candidates
,
116 struct re_backref_cache_entry
*bkref_ents
,
117 Idx str_idx
) internal_function
;
118 static reg_errcode_t
sift_states_bkref (const re_match_context_t
*mctx
,
119 re_sift_context_t
*sctx
,
120 Idx str_idx
, const re_node_set
*candidates
)
122 static reg_errcode_t
merge_state_array (const re_dfa_t
*dfa
,
124 re_dfastate_t
**src
, Idx num
)
126 static re_dfastate_t
*find_recover_state (reg_errcode_t
*err
,
127 re_match_context_t
*mctx
) internal_function
;
128 static re_dfastate_t
*transit_state (reg_errcode_t
*err
,
129 re_match_context_t
*mctx
,
130 re_dfastate_t
*state
) internal_function
;
131 static re_dfastate_t
*merge_state_with_log (reg_errcode_t
*err
,
132 re_match_context_t
*mctx
,
133 re_dfastate_t
*next_state
)
135 static reg_errcode_t
check_subexp_matching_top (re_match_context_t
*mctx
,
136 re_node_set
*cur_nodes
,
137 Idx str_idx
) internal_function
;
139 static re_dfastate_t
*transit_state_sb (reg_errcode_t
*err
,
140 re_match_context_t
*mctx
,
141 re_dfastate_t
*pstate
)
144 #ifdef RE_ENABLE_I18N
145 static reg_errcode_t
transit_state_mb (re_match_context_t
*mctx
,
146 re_dfastate_t
*pstate
)
148 #endif /* RE_ENABLE_I18N */
149 static reg_errcode_t
transit_state_bkref (re_match_context_t
*mctx
,
150 const re_node_set
*nodes
)
152 static reg_errcode_t
get_subexp (re_match_context_t
*mctx
,
153 Idx bkref_node
, Idx bkref_str_idx
)
155 static reg_errcode_t
get_subexp_sub (re_match_context_t
*mctx
,
156 const re_sub_match_top_t
*sub_top
,
157 re_sub_match_last_t
*sub_last
,
158 Idx bkref_node
, Idx bkref_str
)
160 static Idx
find_subexp_node (const re_dfa_t
*dfa
, const re_node_set
*nodes
,
161 Idx subexp_idx
, int type
) internal_function
;
162 static reg_errcode_t
check_arrival (re_match_context_t
*mctx
,
163 state_array_t
*path
, Idx top_node
,
164 Idx top_str
, Idx last_node
, Idx last_str
,
165 int type
) internal_function
;
166 static reg_errcode_t
check_arrival_add_next_nodes (re_match_context_t
*mctx
,
168 re_node_set
*cur_nodes
,
169 re_node_set
*next_nodes
)
171 static reg_errcode_t
check_arrival_expand_ecl (const re_dfa_t
*dfa
,
172 re_node_set
*cur_nodes
,
173 Idx ex_subexp
, int type
)
175 static reg_errcode_t
check_arrival_expand_ecl_sub (const re_dfa_t
*dfa
,
176 re_node_set
*dst_nodes
,
177 Idx target
, Idx ex_subexp
,
178 int type
) internal_function
;
179 static reg_errcode_t
expand_bkref_cache (re_match_context_t
*mctx
,
180 re_node_set
*cur_nodes
, Idx cur_str
,
181 Idx subexp_num
, int type
)
183 static bool build_trtable (const re_dfa_t
*dfa
,
184 re_dfastate_t
*state
) internal_function
;
185 #ifdef RE_ENABLE_I18N
186 static int check_node_accept_bytes (const re_dfa_t
*dfa
, Idx node_idx
,
187 const re_string_t
*input
, Idx idx
)
190 static unsigned int find_collation_sequence_value (const unsigned char *mbs
,
194 #endif /* RE_ENABLE_I18N */
195 static Idx
group_nodes_into_DFAstates (const re_dfa_t
*dfa
,
196 const re_dfastate_t
*state
,
197 re_node_set
*states_node
,
198 bitset_t
*states_ch
) internal_function
;
199 static bool check_node_accept (const re_match_context_t
*mctx
,
200 const re_token_t
*node
, Idx idx
)
202 static reg_errcode_t
extend_buffers (re_match_context_t
*mctx
, int min_len
)
205 /* Entry point for POSIX code. */
207 /* regexec searches for a given pattern, specified by PREG, in the
210 If NMATCH is zero or REG_NOSUB was set in the cflags argument to
211 'regcomp', we ignore PMATCH. Otherwise, we assume PMATCH has at
212 least NMATCH elements, and we set them to the offsets of the
213 corresponding matched substrings.
215 EFLAGS specifies "execution flags" which affect matching: if
216 REG_NOTBOL is set, then ^ does not match at the beginning of the
217 string; if REG_NOTEOL is set, then $ does not match at the end.
219 We return 0 if we find a match and REG_NOMATCH if not. */
222 regexec (preg
, string
, nmatch
, pmatch
, eflags
)
223 const regex_t
*_Restrict_ preg
;
224 const char *_Restrict_ string
;
226 regmatch_t pmatch
[_Restrict_arr_
];
232 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 __libc_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 __libc_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
;
425 re_dfa_t
*dfa
= bufp
->buffer
;
427 Idx last_start
= start
+ range
;
429 /* Check for out-of-range. */
430 if (BE (start
< 0 || start
> length
, 0))
432 if (BE (length
< last_start
|| (0 <= range
&& last_start
< start
), 0))
434 else if (BE (last_start
< 0 || (range
< 0 && start
<= last_start
), 0))
437 __libc_lock_lock (dfa
->lock
);
439 eflags
|= (bufp
->not_bol
) ? REG_NOTBOL
: 0;
440 eflags
|= (bufp
->not_eol
) ? REG_NOTEOL
: 0;
442 /* Compile fastmap if we haven't yet. */
443 if (start
< last_start
&& bufp
->fastmap
!= NULL
&& !bufp
->fastmap_accurate
)
444 re_compile_fastmap (bufp
);
446 if (BE (bufp
->no_sub
, 0))
449 /* We need at least 1 register. */
452 else if (BE (bufp
->regs_allocated
== REGS_FIXED
453 && regs
->num_regs
<= bufp
->re_nsub
, 0))
455 nregs
= regs
->num_regs
;
456 if (BE (nregs
< 1, 0))
458 /* Nothing can be copied to regs. */
464 nregs
= bufp
->re_nsub
+ 1;
465 pmatch
= re_malloc (regmatch_t
, nregs
);
466 if (BE (pmatch
== NULL
, 0))
472 result
= re_search_internal (bufp
, string
, length
, start
, last_start
, stop
,
473 nregs
, pmatch
, eflags
);
477 /* I hope we needn't fill their regs with -1's when no match was found. */
478 if (result
!= REG_NOERROR
)
479 rval
= result
== REG_NOMATCH
? -1 : -2;
480 else if (regs
!= NULL
)
482 /* If caller wants register contents data back, copy them. */
483 bufp
->regs_allocated
= re_copy_regs (regs
, pmatch
, nregs
,
484 bufp
->regs_allocated
);
485 if (BE (bufp
->regs_allocated
== REGS_UNALLOCATED
, 0))
489 if (BE (rval
== 0, 1))
493 assert (pmatch
[0].rm_so
== start
);
494 rval
= pmatch
[0].rm_eo
- start
;
497 rval
= pmatch
[0].rm_so
;
501 __libc_lock_unlock (dfa
->lock
);
506 re_copy_regs (struct re_registers
*regs
, regmatch_t
*pmatch
, Idx nregs
,
509 int rval
= REGS_REALLOCATE
;
511 Idx need_regs
= nregs
+ 1;
512 /* We need one extra element beyond 'num_regs' for the '-1' marker GNU code
515 /* Have the register data arrays been allocated? */
516 if (regs_allocated
== REGS_UNALLOCATED
)
517 { /* No. So allocate them with malloc. */
518 regs
->start
= re_malloc (regoff_t
, need_regs
);
519 if (BE (regs
->start
== NULL
, 0))
520 return REGS_UNALLOCATED
;
521 regs
->end
= re_malloc (regoff_t
, need_regs
);
522 if (BE (regs
->end
== NULL
, 0))
524 re_free (regs
->start
);
525 return REGS_UNALLOCATED
;
527 regs
->num_regs
= need_regs
;
529 else if (regs_allocated
== REGS_REALLOCATE
)
530 { /* Yes. If we need more elements than were already
531 allocated, reallocate them. If we need fewer, just
533 if (BE (need_regs
> regs
->num_regs
, 0))
535 regoff_t
*new_start
= re_realloc (regs
->start
, regoff_t
, need_regs
);
537 if (BE (new_start
== NULL
, 0))
538 return REGS_UNALLOCATED
;
539 new_end
= re_realloc (regs
->end
, regoff_t
, need_regs
);
540 if (BE (new_end
== NULL
, 0))
543 return REGS_UNALLOCATED
;
545 regs
->start
= new_start
;
547 regs
->num_regs
= need_regs
;
552 assert (regs_allocated
== REGS_FIXED
);
553 /* This function may not be called with REGS_FIXED and nregs too big. */
554 assert (regs
->num_regs
>= nregs
);
559 for (i
= 0; i
< nregs
; ++i
)
561 regs
->start
[i
] = pmatch
[i
].rm_so
;
562 regs
->end
[i
] = pmatch
[i
].rm_eo
;
564 for ( ; i
< regs
->num_regs
; ++i
)
565 regs
->start
[i
] = regs
->end
[i
] = -1;
570 /* Set REGS to hold NUM_REGS registers, storing them in STARTS and
571 ENDS. Subsequent matches using PATTERN_BUFFER and REGS will use
572 this memory for recording register information. STARTS and ENDS
573 must be allocated using the malloc library routine, and must each
574 be at least NUM_REGS * sizeof (regoff_t) bytes long.
576 If NUM_REGS == 0, then subsequent matches should allocate their own
579 Unless this function is called, the first search or match using
580 PATTERN_BUFFER will allocate its own register data, without
581 freeing the old data. */
584 re_set_registers (bufp
, regs
, num_regs
, starts
, ends
)
585 struct re_pattern_buffer
*bufp
;
586 struct re_registers
*regs
;
587 __re_size_t num_regs
;
588 regoff_t
*starts
, *ends
;
592 bufp
->regs_allocated
= REGS_REALLOCATE
;
593 regs
->num_regs
= num_regs
;
594 regs
->start
= starts
;
599 bufp
->regs_allocated
= REGS_UNALLOCATED
;
601 regs
->start
= regs
->end
= NULL
;
605 weak_alias (__re_set_registers
, re_set_registers
)
608 /* Entry points compatible with 4.2 BSD regex library. We don't define
609 them unless specifically requested. */
611 #if defined _REGEX_RE_COMP || defined _LIBC
619 return 0 == regexec (&re_comp_buf
, s
, 0, NULL
, 0);
621 #endif /* _REGEX_RE_COMP */
623 /* Internal entry point. */
625 /* Searches for a compiled pattern PREG in the string STRING, whose
626 length is LENGTH. NMATCH, PMATCH, and EFLAGS have the same
627 meaning as with regexec. LAST_START is START + RANGE, where
628 START and RANGE have the same meaning as with re_search.
629 Return REG_NOERROR if we find a match, and REG_NOMATCH if not,
630 otherwise return the error code.
631 Note: We assume front end functions already check ranges.
632 (0 <= LAST_START && LAST_START <= LENGTH) */
635 __attribute_warn_unused_result__
636 re_search_internal (const regex_t
*preg
,
637 const char *string
, Idx length
,
638 Idx start
, Idx last_start
, Idx stop
,
639 size_t nmatch
, regmatch_t pmatch
[],
643 const re_dfa_t
*dfa
= preg
->buffer
;
644 Idx left_lim
, right_lim
;
646 bool fl_longest_match
;
649 Idx match_last
= REG_MISSING
;
653 #if defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L)
654 re_match_context_t mctx
= { .dfa
= dfa
};
656 re_match_context_t mctx
;
658 char *fastmap
= ((preg
->fastmap
!= NULL
&& preg
->fastmap_accurate
659 && start
!= last_start
&& !preg
->can_be_null
)
660 ? preg
->fastmap
: NULL
);
661 RE_TRANSLATE_TYPE t
= preg
->translate
;
663 #if !(defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L))
664 memset (&mctx
, '\0', sizeof (re_match_context_t
));
668 extra_nmatch
= (nmatch
> preg
->re_nsub
) ? nmatch
- (preg
->re_nsub
+ 1) : 0;
669 nmatch
-= extra_nmatch
;
671 /* Check if the DFA haven't been compiled. */
672 if (BE (preg
->used
== 0 || dfa
->init_state
== NULL
673 || dfa
->init_state_word
== NULL
|| dfa
->init_state_nl
== NULL
674 || dfa
->init_state_begbuf
== NULL
, 0))
678 /* We assume front-end functions already check them. */
679 assert (0 <= last_start
&& last_start
<= length
);
682 /* If initial states with non-begbuf contexts have no elements,
683 the regex must be anchored. If preg->newline_anchor is set,
684 we'll never use init_state_nl, so do not check it. */
685 if (dfa
->init_state
->nodes
.nelem
== 0
686 && dfa
->init_state_word
->nodes
.nelem
== 0
687 && (dfa
->init_state_nl
->nodes
.nelem
== 0
688 || !preg
->newline_anchor
))
690 if (start
!= 0 && last_start
!= 0)
692 start
= last_start
= 0;
695 /* We must check the longest matching, if nmatch > 0. */
696 fl_longest_match
= (nmatch
!= 0 || dfa
->nbackref
);
698 err
= re_string_allocate (&mctx
.input
, string
, length
, dfa
->nodes_len
+ 1,
699 preg
->translate
, (preg
->syntax
& RE_ICASE
) != 0,
701 if (BE (err
!= REG_NOERROR
, 0))
703 mctx
.input
.stop
= stop
;
704 mctx
.input
.raw_stop
= stop
;
705 mctx
.input
.newline_anchor
= preg
->newline_anchor
;
707 err
= match_ctx_init (&mctx
, eflags
, dfa
->nbackref
* 2);
708 if (BE (err
!= REG_NOERROR
, 0))
711 /* We will log all the DFA states through which the dfa pass,
712 if nmatch > 1, or this dfa has "multibyte node", which is a
713 back-reference or a node which can accept multibyte character or
714 multi character collating element. */
715 if (nmatch
> 1 || dfa
->has_mb_node
)
717 /* Avoid overflow. */
718 if (BE ((MIN (IDX_MAX
, SIZE_MAX
/ sizeof (re_dfastate_t
*))
719 <= mctx
.input
.bufs_len
), 0))
725 mctx
.state_log
= re_malloc (re_dfastate_t
*, mctx
.input
.bufs_len
+ 1);
726 if (BE (mctx
.state_log
== NULL
, 0))
733 mctx
.state_log
= NULL
;
736 mctx
.input
.tip_context
= (eflags
& REG_NOTBOL
) ? CONTEXT_BEGBUF
737 : CONTEXT_NEWLINE
| CONTEXT_BEGBUF
;
739 /* Check incrementally whether the input string matches. */
740 incr
= (last_start
< start
) ? -1 : 1;
741 left_lim
= (last_start
< start
) ? last_start
: start
;
742 right_lim
= (last_start
< start
) ? start
: last_start
;
743 sb
= dfa
->mb_cur_max
== 1;
746 ? ((sb
|| !(preg
->syntax
& RE_ICASE
|| t
) ? 4 : 0)
747 | (start
<= last_start
? 2 : 0)
748 | (t
!= NULL
? 1 : 0))
751 for (;; match_first
+= incr
)
754 if (match_first
< left_lim
|| right_lim
< match_first
)
757 /* Advance as rapidly as possible through the string, until we
758 find a plausible place to start matching. This may be done
759 with varying efficiency, so there are various possibilities:
760 only the most common of them are specialized, in order to
761 save on code size. We use a switch statement for speed. */
769 /* Fastmap with single-byte translation, match forward. */
770 while (BE (match_first
< right_lim
, 1)
771 && !fastmap
[t
[(unsigned char) string
[match_first
]]])
773 goto forward_match_found_start_or_reached_end
;
776 /* Fastmap without translation, match forward. */
777 while (BE (match_first
< right_lim
, 1)
778 && !fastmap
[(unsigned char) string
[match_first
]])
781 forward_match_found_start_or_reached_end
:
782 if (BE (match_first
== right_lim
, 0))
784 ch
= match_first
>= length
785 ? 0 : (unsigned char) string
[match_first
];
786 if (!fastmap
[t
? t
[ch
] : ch
])
793 /* Fastmap without multi-byte translation, match backwards. */
794 while (match_first
>= left_lim
)
796 ch
= match_first
>= length
797 ? 0 : (unsigned char) string
[match_first
];
798 if (fastmap
[t
? t
[ch
] : ch
])
802 if (match_first
< left_lim
)
807 /* In this case, we can't determine easily the current byte,
808 since it might be a component byte of a multibyte
809 character. Then we use the constructed buffer instead. */
812 /* If MATCH_FIRST is out of the valid range, reconstruct the
814 __re_size_t offset
= match_first
- mctx
.input
.raw_mbs_idx
;
815 if (BE (offset
>= (__re_size_t
) mctx
.input
.valid_raw_len
, 0))
817 err
= re_string_reconstruct (&mctx
.input
, match_first
,
819 if (BE (err
!= REG_NOERROR
, 0))
822 offset
= match_first
- mctx
.input
.raw_mbs_idx
;
824 /* If MATCH_FIRST is out of the buffer, leave it as '\0'.
825 Note that MATCH_FIRST must not be smaller than 0. */
826 ch
= (match_first
>= length
827 ? 0 : re_string_byte_at (&mctx
.input
, offset
));
831 if (match_first
< left_lim
|| match_first
> right_lim
)
840 /* Reconstruct the buffers so that the matcher can assume that
841 the matching starts from the beginning of the buffer. */
842 err
= re_string_reconstruct (&mctx
.input
, match_first
, eflags
);
843 if (BE (err
!= REG_NOERROR
, 0))
846 #ifdef RE_ENABLE_I18N
847 /* Don't consider this char as a possible match start if it part,
848 yet isn't the head, of a multibyte character. */
849 if (!sb
&& !re_string_first_byte (&mctx
.input
, 0))
853 /* It seems to be appropriate one, then use the matcher. */
854 /* We assume that the matching starts from 0. */
855 mctx
.state_log_top
= mctx
.nbkref_ents
= mctx
.max_mb_elem_len
= 0;
856 match_last
= check_matching (&mctx
, fl_longest_match
,
857 start
<= last_start
? &match_first
: NULL
);
858 if (match_last
!= REG_MISSING
)
860 if (BE (match_last
== REG_ERROR
, 0))
867 mctx
.match_last
= match_last
;
868 if ((!preg
->no_sub
&& nmatch
> 1) || dfa
->nbackref
)
870 re_dfastate_t
*pstate
= mctx
.state_log
[match_last
];
871 mctx
.last_node
= check_halt_state_context (&mctx
, pstate
,
874 if ((!preg
->no_sub
&& nmatch
> 1 && dfa
->has_plural_match
)
877 err
= prune_impossible_nodes (&mctx
);
878 if (err
== REG_NOERROR
)
880 if (BE (err
!= REG_NOMATCH
, 0))
882 match_last
= REG_MISSING
;
885 break; /* We found a match. */
889 match_ctx_clean (&mctx
);
893 assert (match_last
!= REG_MISSING
);
894 assert (err
== REG_NOERROR
);
897 /* Set pmatch[] if we need. */
902 /* Initialize registers. */
903 for (reg_idx
= 1; reg_idx
< nmatch
; ++reg_idx
)
904 pmatch
[reg_idx
].rm_so
= pmatch
[reg_idx
].rm_eo
= -1;
906 /* Set the points where matching start/end. */
908 pmatch
[0].rm_eo
= mctx
.match_last
;
909 /* FIXME: This function should fail if mctx.match_last exceeds
910 the maximum possible regoff_t value. We need a new error
911 code REG_OVERFLOW. */
913 if (!preg
->no_sub
&& nmatch
> 1)
915 err
= set_regs (preg
, &mctx
, nmatch
, pmatch
,
916 dfa
->has_plural_match
&& dfa
->nbackref
> 0);
917 if (BE (err
!= REG_NOERROR
, 0))
921 /* At last, add the offset to each register, since we slid
922 the buffers so that we could assume that the matching starts
924 for (reg_idx
= 0; reg_idx
< nmatch
; ++reg_idx
)
925 if (pmatch
[reg_idx
].rm_so
!= -1)
927 #ifdef RE_ENABLE_I18N
928 if (BE (mctx
.input
.offsets_needed
!= 0, 0))
930 pmatch
[reg_idx
].rm_so
=
931 (pmatch
[reg_idx
].rm_so
== mctx
.input
.valid_len
932 ? mctx
.input
.valid_raw_len
933 : mctx
.input
.offsets
[pmatch
[reg_idx
].rm_so
]);
934 pmatch
[reg_idx
].rm_eo
=
935 (pmatch
[reg_idx
].rm_eo
== mctx
.input
.valid_len
936 ? mctx
.input
.valid_raw_len
937 : mctx
.input
.offsets
[pmatch
[reg_idx
].rm_eo
]);
940 assert (mctx
.input
.offsets_needed
== 0);
942 pmatch
[reg_idx
].rm_so
+= match_first
;
943 pmatch
[reg_idx
].rm_eo
+= match_first
;
945 for (reg_idx
= 0; reg_idx
< extra_nmatch
; ++reg_idx
)
947 pmatch
[nmatch
+ reg_idx
].rm_so
= -1;
948 pmatch
[nmatch
+ reg_idx
].rm_eo
= -1;
952 for (reg_idx
= 0; reg_idx
+ 1 < nmatch
; reg_idx
++)
953 if (dfa
->subexp_map
[reg_idx
] != reg_idx
)
955 pmatch
[reg_idx
+ 1].rm_so
956 = pmatch
[dfa
->subexp_map
[reg_idx
] + 1].rm_so
;
957 pmatch
[reg_idx
+ 1].rm_eo
958 = pmatch
[dfa
->subexp_map
[reg_idx
] + 1].rm_eo
;
963 re_free (mctx
.state_log
);
965 match_ctx_free (&mctx
);
966 re_string_destruct (&mctx
.input
);
971 __attribute_warn_unused_result__
972 prune_impossible_nodes (re_match_context_t
*mctx
)
974 const re_dfa_t
*const dfa
= mctx
->dfa
;
975 Idx halt_node
, match_last
;
977 re_dfastate_t
**sifted_states
;
978 re_dfastate_t
**lim_states
= NULL
;
979 re_sift_context_t sctx
;
981 assert (mctx
->state_log
!= NULL
);
983 match_last
= mctx
->match_last
;
984 halt_node
= mctx
->last_node
;
986 /* Avoid overflow. */
987 if (BE (MIN (IDX_MAX
, SIZE_MAX
/ sizeof (re_dfastate_t
*)) <= match_last
, 0))
990 sifted_states
= re_malloc (re_dfastate_t
*, match_last
+ 1);
991 if (BE (sifted_states
== NULL
, 0))
998 lim_states
= re_malloc (re_dfastate_t
*, match_last
+ 1);
999 if (BE (lim_states
== NULL
, 0))
1006 memset (lim_states
, '\0',
1007 sizeof (re_dfastate_t
*) * (match_last
+ 1));
1008 sift_ctx_init (&sctx
, sifted_states
, lim_states
, halt_node
,
1010 ret
= sift_states_backward (mctx
, &sctx
);
1011 re_node_set_free (&sctx
.limits
);
1012 if (BE (ret
!= REG_NOERROR
, 0))
1014 if (sifted_states
[0] != NULL
|| lim_states
[0] != NULL
)
1019 if (! REG_VALID_INDEX (match_last
))
1024 } while (mctx
->state_log
[match_last
] == NULL
1025 || !mctx
->state_log
[match_last
]->halt
);
1026 halt_node
= check_halt_state_context (mctx
,
1027 mctx
->state_log
[match_last
],
1030 ret
= merge_state_array (dfa
, sifted_states
, lim_states
,
1032 re_free (lim_states
);
1034 if (BE (ret
!= REG_NOERROR
, 0))
1039 sift_ctx_init (&sctx
, sifted_states
, lim_states
, halt_node
, match_last
);
1040 ret
= sift_states_backward (mctx
, &sctx
);
1041 re_node_set_free (&sctx
.limits
);
1042 if (BE (ret
!= REG_NOERROR
, 0))
1044 if (sifted_states
[0] == NULL
)
1050 re_free (mctx
->state_log
);
1051 mctx
->state_log
= sifted_states
;
1052 sifted_states
= NULL
;
1053 mctx
->last_node
= halt_node
;
1054 mctx
->match_last
= match_last
;
1057 re_free (sifted_states
);
1058 re_free (lim_states
);
1062 /* Acquire an initial state and return it.
1063 We must select appropriate initial state depending on the context,
1064 since initial states may have constraints like "\<", "^", etc.. */
1066 static inline re_dfastate_t
*
1067 __attribute__ ((always_inline
)) internal_function
1068 acquire_init_state_context (reg_errcode_t
*err
, const re_match_context_t
*mctx
,
1071 const re_dfa_t
*const dfa
= mctx
->dfa
;
1072 if (dfa
->init_state
->has_constraint
)
1074 unsigned int context
;
1075 context
= re_string_context_at (&mctx
->input
, idx
- 1, mctx
->eflags
);
1076 if (IS_WORD_CONTEXT (context
))
1077 return dfa
->init_state_word
;
1078 else if (IS_ORDINARY_CONTEXT (context
))
1079 return dfa
->init_state
;
1080 else if (IS_BEGBUF_CONTEXT (context
) && IS_NEWLINE_CONTEXT (context
))
1081 return dfa
->init_state_begbuf
;
1082 else if (IS_NEWLINE_CONTEXT (context
))
1083 return dfa
->init_state_nl
;
1084 else if (IS_BEGBUF_CONTEXT (context
))
1086 /* It is relatively rare case, then calculate on demand. */
1087 return re_acquire_state_context (err
, dfa
,
1088 dfa
->init_state
->entrance_nodes
,
1092 /* Must not happen? */
1093 return dfa
->init_state
;
1096 return dfa
->init_state
;
1099 /* Check whether the regular expression match input string INPUT or not,
1100 and return the index where the matching end. Return REG_MISSING if
1101 there is no match, and return REG_ERROR in case of an error.
1102 FL_LONGEST_MATCH means we want the POSIX longest matching.
1103 If P_MATCH_FIRST is not NULL, and the match fails, it is set to the
1104 next place where we may want to try matching.
1105 Note that the matcher assumes that the matching starts from the current
1106 index of the buffer. */
1109 internal_function __attribute_warn_unused_result__
1110 check_matching (re_match_context_t
*mctx
, bool fl_longest_match
,
1113 const re_dfa_t
*const dfa
= mctx
->dfa
;
1116 Idx match_last
= REG_MISSING
;
1117 Idx cur_str_idx
= re_string_cur_idx (&mctx
->input
);
1118 re_dfastate_t
*cur_state
;
1119 bool at_init_state
= p_match_first
!= NULL
;
1120 Idx next_start_idx
= cur_str_idx
;
1123 cur_state
= acquire_init_state_context (&err
, mctx
, cur_str_idx
);
1124 /* An initial state must not be NULL (invalid). */
1125 if (BE (cur_state
== NULL
, 0))
1127 assert (err
== REG_ESPACE
);
1131 if (mctx
->state_log
!= NULL
)
1133 mctx
->state_log
[cur_str_idx
] = cur_state
;
1135 /* Check OP_OPEN_SUBEXP in the initial state in case that we use them
1136 later. E.g. Processing back references. */
1137 if (BE (dfa
->nbackref
, 0))
1139 at_init_state
= false;
1140 err
= check_subexp_matching_top (mctx
, &cur_state
->nodes
, 0);
1141 if (BE (err
!= REG_NOERROR
, 0))
1144 if (cur_state
->has_backref
)
1146 err
= transit_state_bkref (mctx
, &cur_state
->nodes
);
1147 if (BE (err
!= REG_NOERROR
, 0))
1153 /* If the RE accepts NULL string. */
1154 if (BE (cur_state
->halt
, 0))
1156 if (!cur_state
->has_constraint
1157 || check_halt_state_context (mctx
, cur_state
, cur_str_idx
))
1159 if (!fl_longest_match
)
1163 match_last
= cur_str_idx
;
1169 while (!re_string_eoi (&mctx
->input
))
1171 re_dfastate_t
*old_state
= cur_state
;
1172 Idx next_char_idx
= re_string_cur_idx (&mctx
->input
) + 1;
1174 if ((BE (next_char_idx
>= mctx
->input
.bufs_len
, 0)
1175 && mctx
->input
.bufs_len
< mctx
->input
.len
)
1176 || (BE (next_char_idx
>= mctx
->input
.valid_len
, 0)
1177 && mctx
->input
.valid_len
< mctx
->input
.len
))
1179 err
= extend_buffers (mctx
, next_char_idx
+ 1);
1180 if (BE (err
!= REG_NOERROR
, 0))
1182 assert (err
== REG_ESPACE
);
1187 cur_state
= transit_state (&err
, mctx
, cur_state
);
1188 if (mctx
->state_log
!= NULL
)
1189 cur_state
= merge_state_with_log (&err
, mctx
, cur_state
);
1191 if (cur_state
== NULL
)
1193 /* Reached the invalid state or an error. Try to recover a valid
1194 state using the state log, if available and if we have not
1195 already found a valid (even if not the longest) match. */
1196 if (BE (err
!= REG_NOERROR
, 0))
1199 if (mctx
->state_log
== NULL
1200 || (match
&& !fl_longest_match
)
1201 || (cur_state
= find_recover_state (&err
, mctx
)) == NULL
)
1205 if (BE (at_init_state
, 0))
1207 if (old_state
== cur_state
)
1208 next_start_idx
= next_char_idx
;
1210 at_init_state
= false;
1213 if (cur_state
->halt
)
1215 /* Reached a halt state.
1216 Check the halt state can satisfy the current context. */
1217 if (!cur_state
->has_constraint
1218 || check_halt_state_context (mctx
, cur_state
,
1219 re_string_cur_idx (&mctx
->input
)))
1221 /* We found an appropriate halt state. */
1222 match_last
= re_string_cur_idx (&mctx
->input
);
1225 /* We found a match, do not modify match_first below. */
1226 p_match_first
= NULL
;
1227 if (!fl_longest_match
)
1234 *p_match_first
+= next_start_idx
;
1239 /* Check NODE match the current context. */
1243 check_halt_node_context (const re_dfa_t
*dfa
, Idx node
, unsigned int context
)
1245 re_token_type_t type
= dfa
->nodes
[node
].type
;
1246 unsigned int constraint
= dfa
->nodes
[node
].constraint
;
1247 if (type
!= END_OF_RE
)
1251 if (NOT_SATISFY_NEXT_CONSTRAINT (constraint
, context
))
1256 /* Check the halt state STATE match the current context.
1257 Return 0 if not match, if the node, STATE has, is a halt node and
1258 match the context, return the node. */
1262 check_halt_state_context (const re_match_context_t
*mctx
,
1263 const re_dfastate_t
*state
, Idx idx
)
1266 unsigned int context
;
1268 assert (state
->halt
);
1270 context
= re_string_context_at (&mctx
->input
, idx
, mctx
->eflags
);
1271 for (i
= 0; i
< state
->nodes
.nelem
; ++i
)
1272 if (check_halt_node_context (mctx
->dfa
, state
->nodes
.elems
[i
], context
))
1273 return state
->nodes
.elems
[i
];
1277 /* Compute the next node to which "NFA" transit from NODE("NFA" is a NFA
1278 corresponding to the DFA).
1279 Return the destination node, and update EPS_VIA_NODES;
1280 return REG_MISSING in case of errors. */
1284 proceed_next_node (const re_match_context_t
*mctx
, Idx nregs
, regmatch_t
*regs
,
1285 Idx
*pidx
, Idx node
, re_node_set
*eps_via_nodes
,
1286 struct re_fail_stack_t
*fs
)
1288 const re_dfa_t
*const dfa
= mctx
->dfa
;
1291 if (IS_EPSILON_NODE (dfa
->nodes
[node
].type
))
1293 re_node_set
*cur_nodes
= &mctx
->state_log
[*pidx
]->nodes
;
1294 re_node_set
*edests
= &dfa
->edests
[node
];
1296 ok
= re_node_set_insert (eps_via_nodes
, node
);
1299 /* Pick up a valid destination, or return REG_MISSING if none
1301 for (dest_node
= REG_MISSING
, i
= 0; i
< edests
->nelem
; ++i
)
1303 Idx candidate
= edests
->elems
[i
];
1304 if (!re_node_set_contains (cur_nodes
, candidate
))
1306 if (dest_node
== REG_MISSING
)
1307 dest_node
= candidate
;
1311 /* In order to avoid infinite loop like "(a*)*", return the second
1312 epsilon-transition if the first was already considered. */
1313 if (re_node_set_contains (eps_via_nodes
, dest_node
))
1316 /* Otherwise, push the second epsilon-transition on the fail stack. */
1318 && push_fail_stack (fs
, *pidx
, candidate
, nregs
, regs
,
1322 /* We know we are going to exit. */
1331 re_token_type_t type
= dfa
->nodes
[node
].type
;
1333 #ifdef RE_ENABLE_I18N
1334 if (dfa
->nodes
[node
].accept_mb
)
1335 naccepted
= check_node_accept_bytes (dfa
, node
, &mctx
->input
, *pidx
);
1337 #endif /* RE_ENABLE_I18N */
1338 if (type
== OP_BACK_REF
)
1340 Idx subexp_idx
= dfa
->nodes
[node
].opr
.idx
+ 1;
1341 naccepted
= regs
[subexp_idx
].rm_eo
- regs
[subexp_idx
].rm_so
;
1344 if (regs
[subexp_idx
].rm_so
== -1 || regs
[subexp_idx
].rm_eo
== -1)
1348 char *buf
= (char *) re_string_get_buffer (&mctx
->input
);
1349 if (memcmp (buf
+ regs
[subexp_idx
].rm_so
, buf
+ *pidx
,
1358 ok
= re_node_set_insert (eps_via_nodes
, node
);
1361 dest_node
= dfa
->edests
[node
].elems
[0];
1362 if (re_node_set_contains (&mctx
->state_log
[*pidx
]->nodes
,
1369 || check_node_accept (mctx
, dfa
->nodes
+ node
, *pidx
))
1371 Idx dest_node
= dfa
->nexts
[node
];
1372 *pidx
= (naccepted
== 0) ? *pidx
+ 1 : *pidx
+ naccepted
;
1373 if (fs
&& (*pidx
> mctx
->match_last
|| mctx
->state_log
[*pidx
] == NULL
1374 || !re_node_set_contains (&mctx
->state_log
[*pidx
]->nodes
,
1377 re_node_set_empty (eps_via_nodes
);
1384 static reg_errcode_t
1385 internal_function __attribute_warn_unused_result__
1386 push_fail_stack (struct re_fail_stack_t
*fs
, Idx str_idx
, Idx dest_node
,
1387 Idx nregs
, regmatch_t
*regs
, re_node_set
*eps_via_nodes
)
1390 Idx num
= fs
->num
++;
1391 if (fs
->num
== fs
->alloc
)
1393 struct re_fail_stack_ent_t
*new_array
;
1394 new_array
= realloc (fs
->stack
, (sizeof (struct re_fail_stack_ent_t
)
1396 if (new_array
== NULL
)
1399 fs
->stack
= new_array
;
1401 fs
->stack
[num
].idx
= str_idx
;
1402 fs
->stack
[num
].node
= dest_node
;
1403 fs
->stack
[num
].regs
= re_malloc (regmatch_t
, nregs
);
1404 if (fs
->stack
[num
].regs
== NULL
)
1406 memcpy (fs
->stack
[num
].regs
, regs
, sizeof (regmatch_t
) * nregs
);
1407 err
= re_node_set_init_copy (&fs
->stack
[num
].eps_via_nodes
, eps_via_nodes
);
1413 pop_fail_stack (struct re_fail_stack_t
*fs
, Idx
*pidx
, Idx nregs
,
1414 regmatch_t
*regs
, re_node_set
*eps_via_nodes
)
1416 Idx num
= --fs
->num
;
1417 assert (REG_VALID_INDEX (num
));
1418 *pidx
= fs
->stack
[num
].idx
;
1419 memcpy (regs
, fs
->stack
[num
].regs
, sizeof (regmatch_t
) * nregs
);
1420 re_node_set_free (eps_via_nodes
);
1421 re_free (fs
->stack
[num
].regs
);
1422 *eps_via_nodes
= fs
->stack
[num
].eps_via_nodes
;
1423 return fs
->stack
[num
].node
;
1426 /* Set the positions where the subexpressions are starts/ends to registers
1428 Note: We assume that pmatch[0] is already set, and
1429 pmatch[i].rm_so == pmatch[i].rm_eo == -1 for 0 < i < nmatch. */
1431 static reg_errcode_t
1432 internal_function __attribute_warn_unused_result__
1433 set_regs (const regex_t
*preg
, const re_match_context_t
*mctx
, size_t nmatch
,
1434 regmatch_t
*pmatch
, bool fl_backtrack
)
1436 const re_dfa_t
*dfa
= preg
->buffer
;
1438 re_node_set eps_via_nodes
;
1439 struct re_fail_stack_t
*fs
;
1440 struct re_fail_stack_t fs_body
= { 0, 2, NULL
};
1441 regmatch_t
*prev_idx_match
;
1442 bool prev_idx_match_malloced
= false;
1445 assert (nmatch
> 1);
1446 assert (mctx
->state_log
!= NULL
);
1451 fs
->stack
= re_malloc (struct re_fail_stack_ent_t
, fs
->alloc
);
1452 if (fs
->stack
== NULL
)
1458 cur_node
= dfa
->init_node
;
1459 re_node_set_init_empty (&eps_via_nodes
);
1461 if (__libc_use_alloca (nmatch
* sizeof (regmatch_t
)))
1462 prev_idx_match
= (regmatch_t
*) alloca (nmatch
* sizeof (regmatch_t
));
1465 prev_idx_match
= re_malloc (regmatch_t
, nmatch
);
1466 if (prev_idx_match
== NULL
)
1468 free_fail_stack_return (fs
);
1471 prev_idx_match_malloced
= true;
1473 memcpy (prev_idx_match
, pmatch
, sizeof (regmatch_t
) * nmatch
);
1475 for (idx
= pmatch
[0].rm_so
; idx
<= pmatch
[0].rm_eo
;)
1477 update_regs (dfa
, pmatch
, prev_idx_match
, cur_node
, idx
, nmatch
);
1479 if (idx
== pmatch
[0].rm_eo
&& cur_node
== mctx
->last_node
)
1484 for (reg_idx
= 0; reg_idx
< nmatch
; ++reg_idx
)
1485 if (pmatch
[reg_idx
].rm_so
> -1 && pmatch
[reg_idx
].rm_eo
== -1)
1487 if (reg_idx
== nmatch
)
1489 re_node_set_free (&eps_via_nodes
);
1490 if (prev_idx_match_malloced
)
1491 re_free (prev_idx_match
);
1492 return free_fail_stack_return (fs
);
1494 cur_node
= pop_fail_stack (fs
, &idx
, nmatch
, pmatch
,
1499 re_node_set_free (&eps_via_nodes
);
1500 if (prev_idx_match_malloced
)
1501 re_free (prev_idx_match
);
1506 /* Proceed to next node. */
1507 cur_node
= proceed_next_node (mctx
, nmatch
, pmatch
, &idx
, cur_node
,
1508 &eps_via_nodes
, fs
);
1510 if (BE (! REG_VALID_INDEX (cur_node
), 0))
1512 if (BE (cur_node
== REG_ERROR
, 0))
1514 re_node_set_free (&eps_via_nodes
);
1515 if (prev_idx_match_malloced
)
1516 re_free (prev_idx_match
);
1517 free_fail_stack_return (fs
);
1521 cur_node
= pop_fail_stack (fs
, &idx
, nmatch
, pmatch
,
1525 re_node_set_free (&eps_via_nodes
);
1526 if (prev_idx_match_malloced
)
1527 re_free (prev_idx_match
);
1532 re_node_set_free (&eps_via_nodes
);
1533 if (prev_idx_match_malloced
)
1534 re_free (prev_idx_match
);
1535 return free_fail_stack_return (fs
);
1538 static reg_errcode_t
1540 free_fail_stack_return (struct re_fail_stack_t
*fs
)
1545 for (fs_idx
= 0; fs_idx
< fs
->num
; ++fs_idx
)
1547 re_node_set_free (&fs
->stack
[fs_idx
].eps_via_nodes
);
1548 re_free (fs
->stack
[fs_idx
].regs
);
1550 re_free (fs
->stack
);
1557 update_regs (const re_dfa_t
*dfa
, regmatch_t
*pmatch
,
1558 regmatch_t
*prev_idx_match
, Idx cur_node
, Idx cur_idx
, Idx nmatch
)
1560 int type
= dfa
->nodes
[cur_node
].type
;
1561 if (type
== OP_OPEN_SUBEXP
)
1563 Idx reg_num
= dfa
->nodes
[cur_node
].opr
.idx
+ 1;
1565 /* We are at the first node of this sub expression. */
1566 if (reg_num
< nmatch
)
1568 pmatch
[reg_num
].rm_so
= cur_idx
;
1569 pmatch
[reg_num
].rm_eo
= -1;
1572 else if (type
== OP_CLOSE_SUBEXP
)
1574 Idx reg_num
= dfa
->nodes
[cur_node
].opr
.idx
+ 1;
1575 if (reg_num
< nmatch
)
1577 /* We are at the last node of this sub expression. */
1578 if (pmatch
[reg_num
].rm_so
< cur_idx
)
1580 pmatch
[reg_num
].rm_eo
= cur_idx
;
1581 /* This is a non-empty match or we are not inside an optional
1582 subexpression. Accept this right away. */
1583 memcpy (prev_idx_match
, pmatch
, sizeof (regmatch_t
) * nmatch
);
1587 if (dfa
->nodes
[cur_node
].opt_subexp
1588 && prev_idx_match
[reg_num
].rm_so
!= -1)
1589 /* We transited through an empty match for an optional
1590 subexpression, like (a?)*, and this is not the subexp's
1591 first match. Copy back the old content of the registers
1592 so that matches of an inner subexpression are undone as
1593 well, like in ((a?))*. */
1594 memcpy (pmatch
, prev_idx_match
, sizeof (regmatch_t
) * nmatch
);
1596 /* We completed a subexpression, but it may be part of
1597 an optional one, so do not update PREV_IDX_MATCH. */
1598 pmatch
[reg_num
].rm_eo
= cur_idx
;
1604 /* This function checks the STATE_LOG from the SCTX->last_str_idx to 0
1605 and sift the nodes in each states according to the following rules.
1606 Updated state_log will be wrote to STATE_LOG.
1608 Rules: We throw away the Node 'a' in the STATE_LOG[STR_IDX] if...
1609 1. When STR_IDX == MATCH_LAST(the last index in the state_log):
1610 If 'a' isn't the LAST_NODE and 'a' can't epsilon transit to
1611 the LAST_NODE, we throw away the node 'a'.
1612 2. When 0 <= STR_IDX < MATCH_LAST and 'a' accepts
1613 string 's' and transit to 'b':
1614 i. If 'b' isn't in the STATE_LOG[STR_IDX+strlen('s')], we throw
1616 ii. If 'b' is in the STATE_LOG[STR_IDX+strlen('s')] but 'b' is
1617 thrown away, we throw away the node 'a'.
1618 3. When 0 <= STR_IDX < MATCH_LAST and 'a' epsilon transit to 'b':
1619 i. If 'b' isn't in the STATE_LOG[STR_IDX], we throw away the
1621 ii. If 'b' is in the STATE_LOG[STR_IDX] but 'b' is thrown away,
1622 we throw away the node 'a'. */
1624 #define STATE_NODE_CONTAINS(state,node) \
1625 ((state) != NULL && re_node_set_contains (&(state)->nodes, node))
1627 static reg_errcode_t
1629 sift_states_backward (const re_match_context_t
*mctx
, re_sift_context_t
*sctx
)
1633 Idx str_idx
= sctx
->last_str_idx
;
1634 re_node_set cur_dest
;
1637 assert (mctx
->state_log
!= NULL
&& mctx
->state_log
[str_idx
] != NULL
);
1640 /* Build sifted state_log[str_idx]. It has the nodes which can epsilon
1641 transit to the last_node and the last_node itself. */
1642 err
= re_node_set_init_1 (&cur_dest
, sctx
->last_node
);
1643 if (BE (err
!= REG_NOERROR
, 0))
1645 err
= update_cur_sifted_state (mctx
, sctx
, str_idx
, &cur_dest
);
1646 if (BE (err
!= REG_NOERROR
, 0))
1649 /* Then check each states in the state_log. */
1652 /* Update counters. */
1653 null_cnt
= (sctx
->sifted_states
[str_idx
] == NULL
) ? null_cnt
+ 1 : 0;
1654 if (null_cnt
> mctx
->max_mb_elem_len
)
1656 memset (sctx
->sifted_states
, '\0',
1657 sizeof (re_dfastate_t
*) * str_idx
);
1658 re_node_set_free (&cur_dest
);
1661 re_node_set_empty (&cur_dest
);
1664 if (mctx
->state_log
[str_idx
])
1666 err
= build_sifted_states (mctx
, sctx
, str_idx
, &cur_dest
);
1667 if (BE (err
!= REG_NOERROR
, 0))
1671 /* Add all the nodes which satisfy the following conditions:
1672 - It can epsilon transit to a node in CUR_DEST.
1674 And update state_log. */
1675 err
= update_cur_sifted_state (mctx
, sctx
, str_idx
, &cur_dest
);
1676 if (BE (err
!= REG_NOERROR
, 0))
1681 re_node_set_free (&cur_dest
);
1685 static reg_errcode_t
1686 internal_function __attribute_warn_unused_result__
1687 build_sifted_states (const re_match_context_t
*mctx
, re_sift_context_t
*sctx
,
1688 Idx str_idx
, re_node_set
*cur_dest
)
1690 const re_dfa_t
*const dfa
= mctx
->dfa
;
1691 const re_node_set
*cur_src
= &mctx
->state_log
[str_idx
]->non_eps_nodes
;
1694 /* Then build the next sifted state.
1695 We build the next sifted state on 'cur_dest', and update
1696 'sifted_states[str_idx]' with 'cur_dest'.
1698 'cur_dest' is the sifted state from 'state_log[str_idx + 1]'.
1699 'cur_src' points the node_set of the old 'state_log[str_idx]'
1700 (with the epsilon nodes pre-filtered out). */
1701 for (i
= 0; i
< cur_src
->nelem
; i
++)
1703 Idx prev_node
= cur_src
->elems
[i
];
1708 re_token_type_t type
= dfa
->nodes
[prev_node
].type
;
1709 assert (!IS_EPSILON_NODE (type
));
1711 #ifdef RE_ENABLE_I18N
1712 /* If the node may accept "multi byte". */
1713 if (dfa
->nodes
[prev_node
].accept_mb
)
1714 naccepted
= sift_states_iter_mb (mctx
, sctx
, prev_node
,
1715 str_idx
, sctx
->last_str_idx
);
1716 #endif /* RE_ENABLE_I18N */
1718 /* We don't check backreferences here.
1719 See update_cur_sifted_state(). */
1721 && check_node_accept (mctx
, dfa
->nodes
+ prev_node
, str_idx
)
1722 && STATE_NODE_CONTAINS (sctx
->sifted_states
[str_idx
+ 1],
1723 dfa
->nexts
[prev_node
]))
1729 if (sctx
->limits
.nelem
)
1731 Idx to_idx
= str_idx
+ naccepted
;
1732 if (check_dst_limits (mctx
, &sctx
->limits
,
1733 dfa
->nexts
[prev_node
], to_idx
,
1734 prev_node
, str_idx
))
1737 ok
= re_node_set_insert (cur_dest
, prev_node
);
1745 /* Helper functions. */
1747 static reg_errcode_t
1749 clean_state_log_if_needed (re_match_context_t
*mctx
, Idx next_state_log_idx
)
1751 Idx top
= mctx
->state_log_top
;
1753 if ((next_state_log_idx
>= mctx
->input
.bufs_len
1754 && mctx
->input
.bufs_len
< mctx
->input
.len
)
1755 || (next_state_log_idx
>= mctx
->input
.valid_len
1756 && mctx
->input
.valid_len
< mctx
->input
.len
))
1759 err
= extend_buffers (mctx
, next_state_log_idx
+ 1);
1760 if (BE (err
!= REG_NOERROR
, 0))
1764 if (top
< next_state_log_idx
)
1766 memset (mctx
->state_log
+ top
+ 1, '\0',
1767 sizeof (re_dfastate_t
*) * (next_state_log_idx
- top
));
1768 mctx
->state_log_top
= next_state_log_idx
;
1773 static reg_errcode_t
1775 merge_state_array (const re_dfa_t
*dfa
, re_dfastate_t
**dst
,
1776 re_dfastate_t
**src
, Idx num
)
1780 for (st_idx
= 0; st_idx
< num
; ++st_idx
)
1782 if (dst
[st_idx
] == NULL
)
1783 dst
[st_idx
] = src
[st_idx
];
1784 else if (src
[st_idx
] != NULL
)
1786 re_node_set merged_set
;
1787 err
= re_node_set_init_union (&merged_set
, &dst
[st_idx
]->nodes
,
1788 &src
[st_idx
]->nodes
);
1789 if (BE (err
!= REG_NOERROR
, 0))
1791 dst
[st_idx
] = re_acquire_state (&err
, dfa
, &merged_set
);
1792 re_node_set_free (&merged_set
);
1793 if (BE (err
!= REG_NOERROR
, 0))
1800 static reg_errcode_t
1802 update_cur_sifted_state (const re_match_context_t
*mctx
,
1803 re_sift_context_t
*sctx
, Idx str_idx
,
1804 re_node_set
*dest_nodes
)
1806 const re_dfa_t
*const dfa
= mctx
->dfa
;
1807 reg_errcode_t err
= REG_NOERROR
;
1808 const re_node_set
*candidates
;
1809 candidates
= ((mctx
->state_log
[str_idx
] == NULL
) ? NULL
1810 : &mctx
->state_log
[str_idx
]->nodes
);
1812 if (dest_nodes
->nelem
== 0)
1813 sctx
->sifted_states
[str_idx
] = NULL
;
1818 /* At first, add the nodes which can epsilon transit to a node in
1820 err
= add_epsilon_src_nodes (dfa
, dest_nodes
, candidates
);
1821 if (BE (err
!= REG_NOERROR
, 0))
1824 /* Then, check the limitations in the current sift_context. */
1825 if (sctx
->limits
.nelem
)
1827 err
= check_subexp_limits (dfa
, dest_nodes
, candidates
, &sctx
->limits
,
1828 mctx
->bkref_ents
, str_idx
);
1829 if (BE (err
!= REG_NOERROR
, 0))
1834 sctx
->sifted_states
[str_idx
] = re_acquire_state (&err
, dfa
, dest_nodes
);
1835 if (BE (err
!= REG_NOERROR
, 0))
1839 if (candidates
&& mctx
->state_log
[str_idx
]->has_backref
)
1841 err
= sift_states_bkref (mctx
, sctx
, str_idx
, candidates
);
1842 if (BE (err
!= REG_NOERROR
, 0))
1848 static reg_errcode_t
1849 internal_function __attribute_warn_unused_result__
1850 add_epsilon_src_nodes (const re_dfa_t
*dfa
, re_node_set
*dest_nodes
,
1851 const re_node_set
*candidates
)
1853 reg_errcode_t err
= REG_NOERROR
;
1856 re_dfastate_t
*state
= re_acquire_state (&err
, dfa
, dest_nodes
);
1857 if (BE (err
!= REG_NOERROR
, 0))
1860 if (!state
->inveclosure
.alloc
)
1862 err
= re_node_set_alloc (&state
->inveclosure
, dest_nodes
->nelem
);
1863 if (BE (err
!= REG_NOERROR
, 0))
1865 for (i
= 0; i
< dest_nodes
->nelem
; i
++)
1867 err
= re_node_set_merge (&state
->inveclosure
,
1868 dfa
->inveclosures
+ dest_nodes
->elems
[i
]);
1869 if (BE (err
!= REG_NOERROR
, 0))
1873 return re_node_set_add_intersect (dest_nodes
, candidates
,
1874 &state
->inveclosure
);
1877 static reg_errcode_t
1879 sub_epsilon_src_nodes (const re_dfa_t
*dfa
, Idx node
, re_node_set
*dest_nodes
,
1880 const re_node_set
*candidates
)
1884 re_node_set
*inv_eclosure
= dfa
->inveclosures
+ node
;
1885 re_node_set except_nodes
;
1886 re_node_set_init_empty (&except_nodes
);
1887 for (ecl_idx
= 0; ecl_idx
< inv_eclosure
->nelem
; ++ecl_idx
)
1889 Idx cur_node
= inv_eclosure
->elems
[ecl_idx
];
1890 if (cur_node
== node
)
1892 if (IS_EPSILON_NODE (dfa
->nodes
[cur_node
].type
))
1894 Idx edst1
= dfa
->edests
[cur_node
].elems
[0];
1895 Idx edst2
= ((dfa
->edests
[cur_node
].nelem
> 1)
1896 ? dfa
->edests
[cur_node
].elems
[1] : REG_MISSING
);
1897 if ((!re_node_set_contains (inv_eclosure
, edst1
)
1898 && re_node_set_contains (dest_nodes
, edst1
))
1899 || (REG_VALID_NONZERO_INDEX (edst2
)
1900 && !re_node_set_contains (inv_eclosure
, edst2
)
1901 && re_node_set_contains (dest_nodes
, edst2
)))
1903 err
= re_node_set_add_intersect (&except_nodes
, candidates
,
1904 dfa
->inveclosures
+ cur_node
);
1905 if (BE (err
!= REG_NOERROR
, 0))
1907 re_node_set_free (&except_nodes
);
1913 for (ecl_idx
= 0; ecl_idx
< inv_eclosure
->nelem
; ++ecl_idx
)
1915 Idx cur_node
= inv_eclosure
->elems
[ecl_idx
];
1916 if (!re_node_set_contains (&except_nodes
, cur_node
))
1918 Idx idx
= re_node_set_contains (dest_nodes
, cur_node
) - 1;
1919 re_node_set_remove_at (dest_nodes
, idx
);
1922 re_node_set_free (&except_nodes
);
1928 check_dst_limits (const re_match_context_t
*mctx
, const re_node_set
*limits
,
1929 Idx dst_node
, Idx dst_idx
, Idx src_node
, Idx src_idx
)
1931 const re_dfa_t
*const dfa
= mctx
->dfa
;
1932 Idx lim_idx
, src_pos
, dst_pos
;
1934 Idx dst_bkref_idx
= search_cur_bkref_entry (mctx
, dst_idx
);
1935 Idx src_bkref_idx
= search_cur_bkref_entry (mctx
, src_idx
);
1936 for (lim_idx
= 0; lim_idx
< limits
->nelem
; ++lim_idx
)
1939 struct re_backref_cache_entry
*ent
;
1940 ent
= mctx
->bkref_ents
+ limits
->elems
[lim_idx
];
1941 subexp_idx
= dfa
->nodes
[ent
->node
].opr
.idx
;
1943 dst_pos
= check_dst_limits_calc_pos (mctx
, limits
->elems
[lim_idx
],
1944 subexp_idx
, dst_node
, dst_idx
,
1946 src_pos
= check_dst_limits_calc_pos (mctx
, limits
->elems
[lim_idx
],
1947 subexp_idx
, src_node
, src_idx
,
1951 <src> <dst> ( <subexp> )
1952 ( <subexp> ) <src> <dst>
1953 ( <subexp1> <src> <subexp2> <dst> <subexp3> ) */
1954 if (src_pos
== dst_pos
)
1955 continue; /* This is unrelated limitation. */
1964 check_dst_limits_calc_pos_1 (const re_match_context_t
*mctx
, int boundaries
,
1965 Idx subexp_idx
, Idx from_node
, Idx bkref_idx
)
1967 const re_dfa_t
*const dfa
= mctx
->dfa
;
1968 const re_node_set
*eclosures
= dfa
->eclosures
+ from_node
;
1971 /* Else, we are on the boundary: examine the nodes on the epsilon
1973 for (node_idx
= 0; node_idx
< eclosures
->nelem
; ++node_idx
)
1975 Idx node
= eclosures
->elems
[node_idx
];
1976 switch (dfa
->nodes
[node
].type
)
1979 if (bkref_idx
!= REG_MISSING
)
1981 struct re_backref_cache_entry
*ent
= mctx
->bkref_ents
+ bkref_idx
;
1987 if (ent
->node
!= node
)
1990 if (subexp_idx
< BITSET_WORD_BITS
1991 && !(ent
->eps_reachable_subexps_map
1992 & ((bitset_word_t
) 1 << subexp_idx
)))
1995 /* Recurse trying to reach the OP_OPEN_SUBEXP and
1996 OP_CLOSE_SUBEXP cases below. But, if the
1997 destination node is the same node as the source
1998 node, don't recurse because it would cause an
1999 infinite loop: a regex that exhibits this behavior
2001 dst
= dfa
->edests
[node
].elems
[0];
2002 if (dst
== from_node
)
2006 else /* if (boundaries & 2) */
2011 check_dst_limits_calc_pos_1 (mctx
, boundaries
, subexp_idx
,
2013 if (cpos
== -1 /* && (boundaries & 1) */)
2015 if (cpos
== 0 && (boundaries
& 2))
2018 if (subexp_idx
< BITSET_WORD_BITS
)
2019 ent
->eps_reachable_subexps_map
2020 &= ~((bitset_word_t
) 1 << subexp_idx
);
2022 while (ent
++->more
);
2026 case OP_OPEN_SUBEXP
:
2027 if ((boundaries
& 1) && subexp_idx
== dfa
->nodes
[node
].opr
.idx
)
2031 case OP_CLOSE_SUBEXP
:
2032 if ((boundaries
& 2) && subexp_idx
== dfa
->nodes
[node
].opr
.idx
)
2041 return (boundaries
& 2) ? 1 : 0;
2046 check_dst_limits_calc_pos (const re_match_context_t
*mctx
, Idx limit
,
2047 Idx subexp_idx
, Idx from_node
, Idx str_idx
,
2050 struct re_backref_cache_entry
*lim
= mctx
->bkref_ents
+ limit
;
2053 /* If we are outside the range of the subexpression, return -1 or 1. */
2054 if (str_idx
< lim
->subexp_from
)
2057 if (lim
->subexp_to
< str_idx
)
2060 /* If we are within the subexpression, return 0. */
2061 boundaries
= (str_idx
== lim
->subexp_from
);
2062 boundaries
|= (str_idx
== lim
->subexp_to
) << 1;
2063 if (boundaries
== 0)
2066 /* Else, examine epsilon closure. */
2067 return check_dst_limits_calc_pos_1 (mctx
, boundaries
, subexp_idx
,
2068 from_node
, bkref_idx
);
2071 /* Check the limitations of sub expressions LIMITS, and remove the nodes
2072 which are against limitations from DEST_NODES. */
2074 static reg_errcode_t
2076 check_subexp_limits (const re_dfa_t
*dfa
, re_node_set
*dest_nodes
,
2077 const re_node_set
*candidates
, re_node_set
*limits
,
2078 struct re_backref_cache_entry
*bkref_ents
, Idx str_idx
)
2081 Idx node_idx
, lim_idx
;
2083 for (lim_idx
= 0; lim_idx
< limits
->nelem
; ++lim_idx
)
2086 struct re_backref_cache_entry
*ent
;
2087 ent
= bkref_ents
+ limits
->elems
[lim_idx
];
2089 if (str_idx
<= ent
->subexp_from
|| ent
->str_idx
< str_idx
)
2090 continue; /* This is unrelated limitation. */
2092 subexp_idx
= dfa
->nodes
[ent
->node
].opr
.idx
;
2093 if (ent
->subexp_to
== str_idx
)
2095 Idx ops_node
= REG_MISSING
;
2096 Idx cls_node
= REG_MISSING
;
2097 for (node_idx
= 0; node_idx
< dest_nodes
->nelem
; ++node_idx
)
2099 Idx node
= dest_nodes
->elems
[node_idx
];
2100 re_token_type_t type
= dfa
->nodes
[node
].type
;
2101 if (type
== OP_OPEN_SUBEXP
2102 && subexp_idx
== dfa
->nodes
[node
].opr
.idx
)
2104 else if (type
== OP_CLOSE_SUBEXP
2105 && subexp_idx
== dfa
->nodes
[node
].opr
.idx
)
2109 /* Check the limitation of the open subexpression. */
2110 /* Note that (ent->subexp_to = str_idx != ent->subexp_from). */
2111 if (REG_VALID_INDEX (ops_node
))
2113 err
= sub_epsilon_src_nodes (dfa
, ops_node
, dest_nodes
,
2115 if (BE (err
!= REG_NOERROR
, 0))
2119 /* Check the limitation of the close subexpression. */
2120 if (REG_VALID_INDEX (cls_node
))
2121 for (node_idx
= 0; node_idx
< dest_nodes
->nelem
; ++node_idx
)
2123 Idx node
= dest_nodes
->elems
[node_idx
];
2124 if (!re_node_set_contains (dfa
->inveclosures
+ node
,
2126 && !re_node_set_contains (dfa
->eclosures
+ node
,
2129 /* It is against this limitation.
2130 Remove it form the current sifted state. */
2131 err
= sub_epsilon_src_nodes (dfa
, node
, dest_nodes
,
2133 if (BE (err
!= REG_NOERROR
, 0))
2139 else /* (ent->subexp_to != str_idx) */
2141 for (node_idx
= 0; node_idx
< dest_nodes
->nelem
; ++node_idx
)
2143 Idx node
= dest_nodes
->elems
[node_idx
];
2144 re_token_type_t type
= dfa
->nodes
[node
].type
;
2145 if (type
== OP_CLOSE_SUBEXP
|| type
== OP_OPEN_SUBEXP
)
2147 if (subexp_idx
!= dfa
->nodes
[node
].opr
.idx
)
2149 /* It is against this limitation.
2150 Remove it form the current sifted state. */
2151 err
= sub_epsilon_src_nodes (dfa
, node
, dest_nodes
,
2153 if (BE (err
!= REG_NOERROR
, 0))
2162 static reg_errcode_t
2163 internal_function __attribute_warn_unused_result__
2164 sift_states_bkref (const re_match_context_t
*mctx
, re_sift_context_t
*sctx
,
2165 Idx str_idx
, const re_node_set
*candidates
)
2167 const re_dfa_t
*const dfa
= mctx
->dfa
;
2170 re_sift_context_t local_sctx
;
2171 Idx first_idx
= search_cur_bkref_entry (mctx
, str_idx
);
2173 if (first_idx
== REG_MISSING
)
2176 local_sctx
.sifted_states
= NULL
; /* Mark that it hasn't been initialized. */
2178 for (node_idx
= 0; node_idx
< candidates
->nelem
; ++node_idx
)
2181 re_token_type_t type
;
2182 struct re_backref_cache_entry
*entry
;
2183 node
= candidates
->elems
[node_idx
];
2184 type
= dfa
->nodes
[node
].type
;
2185 /* Avoid infinite loop for the REs like "()\1+". */
2186 if (node
== sctx
->last_node
&& str_idx
== sctx
->last_str_idx
)
2188 if (type
!= OP_BACK_REF
)
2191 entry
= mctx
->bkref_ents
+ first_idx
;
2192 enabled_idx
= first_idx
;
2199 re_dfastate_t
*cur_state
;
2201 if (entry
->node
!= node
)
2203 subexp_len
= entry
->subexp_to
- entry
->subexp_from
;
2204 to_idx
= str_idx
+ subexp_len
;
2205 dst_node
= (subexp_len
? dfa
->nexts
[node
]
2206 : dfa
->edests
[node
].elems
[0]);
2208 if (to_idx
> sctx
->last_str_idx
2209 || sctx
->sifted_states
[to_idx
] == NULL
2210 || !STATE_NODE_CONTAINS (sctx
->sifted_states
[to_idx
], dst_node
)
2211 || check_dst_limits (mctx
, &sctx
->limits
, node
,
2212 str_idx
, dst_node
, to_idx
))
2215 if (local_sctx
.sifted_states
== NULL
)
2218 err
= re_node_set_init_copy (&local_sctx
.limits
, &sctx
->limits
);
2219 if (BE (err
!= REG_NOERROR
, 0))
2222 local_sctx
.last_node
= node
;
2223 local_sctx
.last_str_idx
= str_idx
;
2224 ok
= re_node_set_insert (&local_sctx
.limits
, enabled_idx
);
2230 cur_state
= local_sctx
.sifted_states
[str_idx
];
2231 err
= sift_states_backward (mctx
, &local_sctx
);
2232 if (BE (err
!= REG_NOERROR
, 0))
2234 if (sctx
->limited_states
!= NULL
)
2236 err
= merge_state_array (dfa
, sctx
->limited_states
,
2237 local_sctx
.sifted_states
,
2239 if (BE (err
!= REG_NOERROR
, 0))
2242 local_sctx
.sifted_states
[str_idx
] = cur_state
;
2243 re_node_set_remove (&local_sctx
.limits
, enabled_idx
);
2245 /* mctx->bkref_ents may have changed, reload the pointer. */
2246 entry
= mctx
->bkref_ents
+ enabled_idx
;
2248 while (enabled_idx
++, entry
++->more
);
2252 if (local_sctx
.sifted_states
!= NULL
)
2254 re_node_set_free (&local_sctx
.limits
);
2261 #ifdef RE_ENABLE_I18N
2264 sift_states_iter_mb (const re_match_context_t
*mctx
, re_sift_context_t
*sctx
,
2265 Idx node_idx
, Idx str_idx
, Idx max_str_idx
)
2267 const re_dfa_t
*const dfa
= mctx
->dfa
;
2269 /* Check the node can accept "multi byte". */
2270 naccepted
= check_node_accept_bytes (dfa
, node_idx
, &mctx
->input
, str_idx
);
2271 if (naccepted
> 0 && str_idx
+ naccepted
<= max_str_idx
&&
2272 !STATE_NODE_CONTAINS (sctx
->sifted_states
[str_idx
+ naccepted
],
2273 dfa
->nexts
[node_idx
]))
2274 /* The node can't accept the "multi byte", or the
2275 destination was already thrown away, then the node
2276 could't accept the current input "multi byte". */
2278 /* Otherwise, it is sure that the node could accept
2279 'naccepted' bytes input. */
2282 #endif /* RE_ENABLE_I18N */
2285 /* Functions for state transition. */
2287 /* Return the next state to which the current state STATE will transit by
2288 accepting the current input byte, and update STATE_LOG if necessary.
2289 If STATE can accept a multibyte char/collating element/back reference
2290 update the destination of STATE_LOG. */
2292 static re_dfastate_t
*
2293 internal_function __attribute_warn_unused_result__
2294 transit_state (reg_errcode_t
*err
, re_match_context_t
*mctx
,
2295 re_dfastate_t
*state
)
2297 re_dfastate_t
**trtable
;
2300 #ifdef RE_ENABLE_I18N
2301 /* If the current state can accept multibyte. */
2302 if (BE (state
->accept_mb
, 0))
2304 *err
= transit_state_mb (mctx
, state
);
2305 if (BE (*err
!= REG_NOERROR
, 0))
2308 #endif /* RE_ENABLE_I18N */
2310 /* Then decide the next state with the single byte. */
2313 /* don't use transition table */
2314 return transit_state_sb (err
, mctx
, state
);
2317 /* Use transition table */
2318 ch
= re_string_fetch_byte (&mctx
->input
);
2321 trtable
= state
->trtable
;
2322 if (BE (trtable
!= NULL
, 1))
2325 trtable
= state
->word_trtable
;
2326 if (BE (trtable
!= NULL
, 1))
2328 unsigned int context
;
2330 = re_string_context_at (&mctx
->input
,
2331 re_string_cur_idx (&mctx
->input
) - 1,
2333 if (IS_WORD_CONTEXT (context
))
2334 return trtable
[ch
+ SBC_MAX
];
2339 if (!build_trtable (mctx
->dfa
, state
))
2345 /* Retry, we now have a transition table. */
2349 /* Update the state_log if we need */
2350 static re_dfastate_t
*
2352 merge_state_with_log (reg_errcode_t
*err
, re_match_context_t
*mctx
,
2353 re_dfastate_t
*next_state
)
2355 const re_dfa_t
*const dfa
= mctx
->dfa
;
2356 Idx cur_idx
= re_string_cur_idx (&mctx
->input
);
2358 if (cur_idx
> mctx
->state_log_top
)
2360 mctx
->state_log
[cur_idx
] = next_state
;
2361 mctx
->state_log_top
= cur_idx
;
2363 else if (mctx
->state_log
[cur_idx
] == 0)
2365 mctx
->state_log
[cur_idx
] = next_state
;
2369 re_dfastate_t
*pstate
;
2370 unsigned int context
;
2371 re_node_set next_nodes
, *log_nodes
, *table_nodes
= NULL
;
2372 /* If (state_log[cur_idx] != 0), it implies that cur_idx is
2373 the destination of a multibyte char/collating element/
2374 back reference. Then the next state is the union set of
2375 these destinations and the results of the transition table. */
2376 pstate
= mctx
->state_log
[cur_idx
];
2377 log_nodes
= pstate
->entrance_nodes
;
2378 if (next_state
!= NULL
)
2380 table_nodes
= next_state
->entrance_nodes
;
2381 *err
= re_node_set_init_union (&next_nodes
, table_nodes
,
2383 if (BE (*err
!= REG_NOERROR
, 0))
2387 next_nodes
= *log_nodes
;
2388 /* Note: We already add the nodes of the initial state,
2389 then we don't need to add them here. */
2391 context
= re_string_context_at (&mctx
->input
,
2392 re_string_cur_idx (&mctx
->input
) - 1,
2394 next_state
= mctx
->state_log
[cur_idx
]
2395 = re_acquire_state_context (err
, dfa
, &next_nodes
, context
);
2396 /* We don't need to check errors here, since the return value of
2397 this function is next_state and ERR is already set. */
2399 if (table_nodes
!= NULL
)
2400 re_node_set_free (&next_nodes
);
2403 if (BE (dfa
->nbackref
, 0) && next_state
!= NULL
)
2405 /* Check OP_OPEN_SUBEXP in the current state in case that we use them
2406 later. We must check them here, since the back references in the
2407 next state might use them. */
2408 *err
= check_subexp_matching_top (mctx
, &next_state
->nodes
,
2410 if (BE (*err
!= REG_NOERROR
, 0))
2413 /* If the next state has back references. */
2414 if (next_state
->has_backref
)
2416 *err
= transit_state_bkref (mctx
, &next_state
->nodes
);
2417 if (BE (*err
!= REG_NOERROR
, 0))
2419 next_state
= mctx
->state_log
[cur_idx
];
2426 /* Skip bytes in the input that correspond to part of a
2427 multi-byte match, then look in the log for a state
2428 from which to restart matching. */
2429 static re_dfastate_t
*
2431 find_recover_state (reg_errcode_t
*err
, re_match_context_t
*mctx
)
2433 re_dfastate_t
*cur_state
;
2436 Idx max
= mctx
->state_log_top
;
2437 Idx cur_str_idx
= re_string_cur_idx (&mctx
->input
);
2441 if (++cur_str_idx
> max
)
2443 re_string_skip_bytes (&mctx
->input
, 1);
2445 while (mctx
->state_log
[cur_str_idx
] == NULL
);
2447 cur_state
= merge_state_with_log (err
, mctx
, NULL
);
2449 while (*err
== REG_NOERROR
&& cur_state
== NULL
);
2453 /* Helper functions for transit_state. */
2455 /* From the node set CUR_NODES, pick up the nodes whose types are
2456 OP_OPEN_SUBEXP and which have corresponding back references in the regular
2457 expression. And register them to use them later for evaluating the
2458 corresponding back references. */
2460 static reg_errcode_t
2462 check_subexp_matching_top (re_match_context_t
*mctx
, re_node_set
*cur_nodes
,
2465 const re_dfa_t
*const dfa
= mctx
->dfa
;
2469 /* TODO: This isn't efficient.
2470 Because there might be more than one nodes whose types are
2471 OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
2474 for (node_idx
= 0; node_idx
< cur_nodes
->nelem
; ++node_idx
)
2476 Idx node
= cur_nodes
->elems
[node_idx
];
2477 if (dfa
->nodes
[node
].type
== OP_OPEN_SUBEXP
2478 && dfa
->nodes
[node
].opr
.idx
< BITSET_WORD_BITS
2479 && (dfa
->used_bkref_map
2480 & ((bitset_word_t
) 1 << dfa
->nodes
[node
].opr
.idx
)))
2482 err
= match_ctx_add_subtop (mctx
, node
, str_idx
);
2483 if (BE (err
!= REG_NOERROR
, 0))
2491 /* Return the next state to which the current state STATE will transit by
2492 accepting the current input byte. */
2494 static re_dfastate_t
*
2495 transit_state_sb (reg_errcode_t
*err
, re_match_context_t
*mctx
,
2496 re_dfastate_t
*state
)
2498 const re_dfa_t
*const dfa
= mctx
->dfa
;
2499 re_node_set next_nodes
;
2500 re_dfastate_t
*next_state
;
2501 Idx node_cnt
, cur_str_idx
= re_string_cur_idx (&mctx
->input
);
2502 unsigned int context
;
2504 *err
= re_node_set_alloc (&next_nodes
, state
->nodes
.nelem
+ 1);
2505 if (BE (*err
!= REG_NOERROR
, 0))
2507 for (node_cnt
= 0; node_cnt
< state
->nodes
.nelem
; ++node_cnt
)
2509 Idx cur_node
= state
->nodes
.elems
[node_cnt
];
2510 if (check_node_accept (mctx
, dfa
->nodes
+ cur_node
, cur_str_idx
))
2512 *err
= re_node_set_merge (&next_nodes
,
2513 dfa
->eclosures
+ dfa
->nexts
[cur_node
]);
2514 if (BE (*err
!= REG_NOERROR
, 0))
2516 re_node_set_free (&next_nodes
);
2521 context
= re_string_context_at (&mctx
->input
, cur_str_idx
, mctx
->eflags
);
2522 next_state
= re_acquire_state_context (err
, dfa
, &next_nodes
, context
);
2523 /* We don't need to check errors here, since the return value of
2524 this function is next_state and ERR is already set. */
2526 re_node_set_free (&next_nodes
);
2527 re_string_skip_bytes (&mctx
->input
, 1);
2532 #ifdef RE_ENABLE_I18N
2533 static reg_errcode_t
2535 transit_state_mb (re_match_context_t
*mctx
, re_dfastate_t
*pstate
)
2537 const re_dfa_t
*const dfa
= mctx
->dfa
;
2541 for (i
= 0; i
< pstate
->nodes
.nelem
; ++i
)
2543 re_node_set dest_nodes
, *new_nodes
;
2544 Idx cur_node_idx
= pstate
->nodes
.elems
[i
];
2547 unsigned int context
;
2548 re_dfastate_t
*dest_state
;
2550 if (!dfa
->nodes
[cur_node_idx
].accept_mb
)
2553 if (dfa
->nodes
[cur_node_idx
].constraint
)
2555 context
= re_string_context_at (&mctx
->input
,
2556 re_string_cur_idx (&mctx
->input
),
2558 if (NOT_SATISFY_NEXT_CONSTRAINT (dfa
->nodes
[cur_node_idx
].constraint
,
2563 /* How many bytes the node can accept? */
2564 naccepted
= check_node_accept_bytes (dfa
, cur_node_idx
, &mctx
->input
,
2565 re_string_cur_idx (&mctx
->input
));
2569 /* The node can accepts 'naccepted' bytes. */
2570 dest_idx
= re_string_cur_idx (&mctx
->input
) + naccepted
;
2571 mctx
->max_mb_elem_len
= ((mctx
->max_mb_elem_len
< naccepted
) ? naccepted
2572 : mctx
->max_mb_elem_len
);
2573 err
= clean_state_log_if_needed (mctx
, dest_idx
);
2574 if (BE (err
!= REG_NOERROR
, 0))
2577 assert (dfa
->nexts
[cur_node_idx
] != REG_MISSING
);
2579 new_nodes
= dfa
->eclosures
+ dfa
->nexts
[cur_node_idx
];
2581 dest_state
= mctx
->state_log
[dest_idx
];
2582 if (dest_state
== NULL
)
2583 dest_nodes
= *new_nodes
;
2586 err
= re_node_set_init_union (&dest_nodes
,
2587 dest_state
->entrance_nodes
, new_nodes
);
2588 if (BE (err
!= REG_NOERROR
, 0))
2591 context
= re_string_context_at (&mctx
->input
, dest_idx
- 1,
2593 mctx
->state_log
[dest_idx
]
2594 = re_acquire_state_context (&err
, dfa
, &dest_nodes
, context
);
2595 if (dest_state
!= NULL
)
2596 re_node_set_free (&dest_nodes
);
2597 if (BE (mctx
->state_log
[dest_idx
] == NULL
&& err
!= REG_NOERROR
, 0))
2602 #endif /* RE_ENABLE_I18N */
2604 static reg_errcode_t
2606 transit_state_bkref (re_match_context_t
*mctx
, const re_node_set
*nodes
)
2608 const re_dfa_t
*const dfa
= mctx
->dfa
;
2611 Idx cur_str_idx
= re_string_cur_idx (&mctx
->input
);
2613 for (i
= 0; i
< nodes
->nelem
; ++i
)
2615 Idx dest_str_idx
, prev_nelem
, bkc_idx
;
2616 Idx node_idx
= nodes
->elems
[i
];
2617 unsigned int context
;
2618 const re_token_t
*node
= dfa
->nodes
+ node_idx
;
2619 re_node_set
*new_dest_nodes
;
2621 /* Check whether 'node' is a backreference or not. */
2622 if (node
->type
!= OP_BACK_REF
)
2625 if (node
->constraint
)
2627 context
= re_string_context_at (&mctx
->input
, cur_str_idx
,
2629 if (NOT_SATISFY_NEXT_CONSTRAINT (node
->constraint
, context
))
2633 /* 'node' is a backreference.
2634 Check the substring which the substring matched. */
2635 bkc_idx
= mctx
->nbkref_ents
;
2636 err
= get_subexp (mctx
, node_idx
, cur_str_idx
);
2637 if (BE (err
!= REG_NOERROR
, 0))
2640 /* And add the epsilon closures (which is 'new_dest_nodes') of
2641 the backreference to appropriate state_log. */
2643 assert (dfa
->nexts
[node_idx
] != REG_MISSING
);
2645 for (; bkc_idx
< mctx
->nbkref_ents
; ++bkc_idx
)
2648 re_dfastate_t
*dest_state
;
2649 struct re_backref_cache_entry
*bkref_ent
;
2650 bkref_ent
= mctx
->bkref_ents
+ bkc_idx
;
2651 if (bkref_ent
->node
!= node_idx
|| bkref_ent
->str_idx
!= cur_str_idx
)
2653 subexp_len
= bkref_ent
->subexp_to
- bkref_ent
->subexp_from
;
2654 new_dest_nodes
= (subexp_len
== 0
2655 ? dfa
->eclosures
+ dfa
->edests
[node_idx
].elems
[0]
2656 : dfa
->eclosures
+ dfa
->nexts
[node_idx
]);
2657 dest_str_idx
= (cur_str_idx
+ bkref_ent
->subexp_to
2658 - bkref_ent
->subexp_from
);
2659 context
= re_string_context_at (&mctx
->input
, dest_str_idx
- 1,
2661 dest_state
= mctx
->state_log
[dest_str_idx
];
2662 prev_nelem
= ((mctx
->state_log
[cur_str_idx
] == NULL
) ? 0
2663 : mctx
->state_log
[cur_str_idx
]->nodes
.nelem
);
2664 /* Add 'new_dest_node' to state_log. */
2665 if (dest_state
== NULL
)
2667 mctx
->state_log
[dest_str_idx
]
2668 = re_acquire_state_context (&err
, dfa
, new_dest_nodes
,
2670 if (BE (mctx
->state_log
[dest_str_idx
] == NULL
2671 && err
!= REG_NOERROR
, 0))
2676 re_node_set dest_nodes
;
2677 err
= re_node_set_init_union (&dest_nodes
,
2678 dest_state
->entrance_nodes
,
2680 if (BE (err
!= REG_NOERROR
, 0))
2682 re_node_set_free (&dest_nodes
);
2685 mctx
->state_log
[dest_str_idx
]
2686 = re_acquire_state_context (&err
, dfa
, &dest_nodes
, context
);
2687 re_node_set_free (&dest_nodes
);
2688 if (BE (mctx
->state_log
[dest_str_idx
] == NULL
2689 && err
!= REG_NOERROR
, 0))
2692 /* We need to check recursively if the backreference can epsilon
2695 && mctx
->state_log
[cur_str_idx
]->nodes
.nelem
> prev_nelem
)
2697 err
= check_subexp_matching_top (mctx
, new_dest_nodes
,
2699 if (BE (err
!= REG_NOERROR
, 0))
2701 err
= transit_state_bkref (mctx
, new_dest_nodes
);
2702 if (BE (err
!= REG_NOERROR
, 0))
2712 /* Enumerate all the candidates which the backreference BKREF_NODE can match
2713 at BKREF_STR_IDX, and register them by match_ctx_add_entry().
2714 Note that we might collect inappropriate candidates here.
2715 However, the cost of checking them strictly here is too high, then we
2716 delay these checking for prune_impossible_nodes(). */
2718 static reg_errcode_t
2719 internal_function __attribute_warn_unused_result__
2720 get_subexp (re_match_context_t
*mctx
, Idx bkref_node
, Idx bkref_str_idx
)
2722 const re_dfa_t
*const dfa
= mctx
->dfa
;
2723 Idx subexp_num
, sub_top_idx
;
2724 const char *buf
= (const char *) re_string_get_buffer (&mctx
->input
);
2725 /* Return if we have already checked BKREF_NODE at BKREF_STR_IDX. */
2726 Idx cache_idx
= search_cur_bkref_entry (mctx
, bkref_str_idx
);
2727 if (cache_idx
!= REG_MISSING
)
2729 const struct re_backref_cache_entry
*entry
2730 = mctx
->bkref_ents
+ cache_idx
;
2732 if (entry
->node
== bkref_node
)
2733 return REG_NOERROR
; /* We already checked it. */
2734 while (entry
++->more
);
2737 subexp_num
= dfa
->nodes
[bkref_node
].opr
.idx
;
2739 /* For each sub expression */
2740 for (sub_top_idx
= 0; sub_top_idx
< mctx
->nsub_tops
; ++sub_top_idx
)
2743 re_sub_match_top_t
*sub_top
= mctx
->sub_tops
[sub_top_idx
];
2744 re_sub_match_last_t
*sub_last
;
2745 Idx sub_last_idx
, sl_str
, bkref_str_off
;
2747 if (dfa
->nodes
[sub_top
->node
].opr
.idx
!= subexp_num
)
2748 continue; /* It isn't related. */
2750 sl_str
= sub_top
->str_idx
;
2751 bkref_str_off
= bkref_str_idx
;
2752 /* At first, check the last node of sub expressions we already
2754 for (sub_last_idx
= 0; sub_last_idx
< sub_top
->nlasts
; ++sub_last_idx
)
2756 regoff_t sl_str_diff
;
2757 sub_last
= sub_top
->lasts
[sub_last_idx
];
2758 sl_str_diff
= sub_last
->str_idx
- sl_str
;
2759 /* The matched string by the sub expression match with the substring
2760 at the back reference? */
2761 if (sl_str_diff
> 0)
2763 if (BE (bkref_str_off
+ sl_str_diff
> mctx
->input
.valid_len
, 0))
2765 /* Not enough chars for a successful match. */
2766 if (bkref_str_off
+ sl_str_diff
> mctx
->input
.len
)
2769 err
= clean_state_log_if_needed (mctx
,
2772 if (BE (err
!= REG_NOERROR
, 0))
2774 buf
= (const char *) re_string_get_buffer (&mctx
->input
);
2776 if (memcmp (buf
+ bkref_str_off
, buf
+ sl_str
, sl_str_diff
) != 0)
2777 /* We don't need to search this sub expression any more. */
2780 bkref_str_off
+= sl_str_diff
;
2781 sl_str
+= sl_str_diff
;
2782 err
= get_subexp_sub (mctx
, sub_top
, sub_last
, bkref_node
,
2785 /* Reload buf, since the preceding call might have reallocated
2787 buf
= (const char *) re_string_get_buffer (&mctx
->input
);
2789 if (err
== REG_NOMATCH
)
2791 if (BE (err
!= REG_NOERROR
, 0))
2795 if (sub_last_idx
< sub_top
->nlasts
)
2797 if (sub_last_idx
> 0)
2799 /* Then, search for the other last nodes of the sub expression. */
2800 for (; sl_str
<= bkref_str_idx
; ++sl_str
)
2803 regoff_t sl_str_off
;
2804 const re_node_set
*nodes
;
2805 sl_str_off
= sl_str
- sub_top
->str_idx
;
2806 /* The matched string by the sub expression match with the substring
2807 at the back reference? */
2810 if (BE (bkref_str_off
>= mctx
->input
.valid_len
, 0))
2812 /* If we are at the end of the input, we cannot match. */
2813 if (bkref_str_off
>= mctx
->input
.len
)
2816 err
= extend_buffers (mctx
, bkref_str_off
+ 1);
2817 if (BE (err
!= REG_NOERROR
, 0))
2820 buf
= (const char *) re_string_get_buffer (&mctx
->input
);
2822 if (buf
[bkref_str_off
++] != buf
[sl_str
- 1])
2823 break; /* We don't need to search this sub expression
2826 if (mctx
->state_log
[sl_str
] == NULL
)
2828 /* Does this state have a ')' of the sub expression? */
2829 nodes
= &mctx
->state_log
[sl_str
]->nodes
;
2830 cls_node
= find_subexp_node (dfa
, nodes
, subexp_num
,
2832 if (cls_node
== REG_MISSING
)
2834 if (sub_top
->path
== NULL
)
2836 sub_top
->path
= calloc (sizeof (state_array_t
),
2837 sl_str
- sub_top
->str_idx
+ 1);
2838 if (sub_top
->path
== NULL
)
2841 /* Can the OP_OPEN_SUBEXP node arrive the OP_CLOSE_SUBEXP node
2842 in the current context? */
2843 err
= check_arrival (mctx
, sub_top
->path
, sub_top
->node
,
2844 sub_top
->str_idx
, cls_node
, sl_str
,
2846 if (err
== REG_NOMATCH
)
2848 if (BE (err
!= REG_NOERROR
, 0))
2850 sub_last
= match_ctx_add_sublast (sub_top
, cls_node
, sl_str
);
2851 if (BE (sub_last
== NULL
, 0))
2853 err
= get_subexp_sub (mctx
, sub_top
, sub_last
, bkref_node
,
2855 if (err
== REG_NOMATCH
)
2862 /* Helper functions for get_subexp(). */
2864 /* Check SUB_LAST can arrive to the back reference BKREF_NODE at BKREF_STR.
2865 If it can arrive, register the sub expression expressed with SUB_TOP
2868 static reg_errcode_t
2870 get_subexp_sub (re_match_context_t
*mctx
, const re_sub_match_top_t
*sub_top
,
2871 re_sub_match_last_t
*sub_last
, Idx bkref_node
, Idx bkref_str
)
2875 /* Can the subexpression arrive the back reference? */
2876 err
= check_arrival (mctx
, &sub_last
->path
, sub_last
->node
,
2877 sub_last
->str_idx
, bkref_node
, bkref_str
,
2879 if (err
!= REG_NOERROR
)
2881 err
= match_ctx_add_entry (mctx
, bkref_node
, bkref_str
, sub_top
->str_idx
,
2883 if (BE (err
!= REG_NOERROR
, 0))
2885 to_idx
= bkref_str
+ sub_last
->str_idx
- sub_top
->str_idx
;
2886 return clean_state_log_if_needed (mctx
, to_idx
);
2889 /* Find the first node which is '(' or ')' and whose index is SUBEXP_IDX.
2890 Search '(' if FL_OPEN, or search ')' otherwise.
2891 TODO: This function isn't efficient...
2892 Because there might be more than one nodes whose types are
2893 OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
2899 find_subexp_node (const re_dfa_t
*dfa
, const re_node_set
*nodes
,
2900 Idx subexp_idx
, int type
)
2903 for (cls_idx
= 0; cls_idx
< nodes
->nelem
; ++cls_idx
)
2905 Idx cls_node
= nodes
->elems
[cls_idx
];
2906 const re_token_t
*node
= dfa
->nodes
+ cls_node
;
2907 if (node
->type
== type
2908 && node
->opr
.idx
== subexp_idx
)
2914 /* Check whether the node TOP_NODE at TOP_STR can arrive to the node
2915 LAST_NODE at LAST_STR. We record the path onto PATH since it will be
2917 Return REG_NOERROR if it can arrive, or REG_NOMATCH otherwise. */
2919 static reg_errcode_t
2920 internal_function __attribute_warn_unused_result__
2921 check_arrival (re_match_context_t
*mctx
, state_array_t
*path
, Idx top_node
,
2922 Idx top_str
, Idx last_node
, Idx last_str
, int type
)
2924 const re_dfa_t
*const dfa
= mctx
->dfa
;
2925 reg_errcode_t err
= REG_NOERROR
;
2926 Idx subexp_num
, backup_cur_idx
, str_idx
, null_cnt
;
2927 re_dfastate_t
*cur_state
= NULL
;
2928 re_node_set
*cur_nodes
, next_nodes
;
2929 re_dfastate_t
**backup_state_log
;
2930 unsigned int context
;
2932 subexp_num
= dfa
->nodes
[top_node
].opr
.idx
;
2933 /* Extend the buffer if we need. */
2934 if (BE (path
->alloc
< last_str
+ mctx
->max_mb_elem_len
+ 1, 0))
2936 re_dfastate_t
**new_array
;
2937 Idx old_alloc
= path
->alloc
;
2938 Idx incr_alloc
= last_str
+ mctx
->max_mb_elem_len
+ 1;
2940 if (BE (IDX_MAX
- old_alloc
< incr_alloc
, 0))
2942 new_alloc
= old_alloc
+ incr_alloc
;
2943 if (BE (SIZE_MAX
/ sizeof (re_dfastate_t
*) < new_alloc
, 0))
2945 new_array
= re_realloc (path
->array
, re_dfastate_t
*, new_alloc
);
2946 if (BE (new_array
== NULL
, 0))
2948 path
->array
= new_array
;
2949 path
->alloc
= new_alloc
;
2950 memset (new_array
+ old_alloc
, '\0',
2951 sizeof (re_dfastate_t
*) * (path
->alloc
- old_alloc
));
2954 str_idx
= path
->next_idx
? path
->next_idx
: top_str
;
2956 /* Temporary modify MCTX. */
2957 backup_state_log
= mctx
->state_log
;
2958 backup_cur_idx
= mctx
->input
.cur_idx
;
2959 mctx
->state_log
= path
->array
;
2960 mctx
->input
.cur_idx
= str_idx
;
2962 /* Setup initial node set. */
2963 context
= re_string_context_at (&mctx
->input
, str_idx
- 1, mctx
->eflags
);
2964 if (str_idx
== top_str
)
2966 err
= re_node_set_init_1 (&next_nodes
, top_node
);
2967 if (BE (err
!= REG_NOERROR
, 0))
2969 err
= check_arrival_expand_ecl (dfa
, &next_nodes
, subexp_num
, type
);
2970 if (BE (err
!= REG_NOERROR
, 0))
2972 re_node_set_free (&next_nodes
);
2978 cur_state
= mctx
->state_log
[str_idx
];
2979 if (cur_state
&& cur_state
->has_backref
)
2981 err
= re_node_set_init_copy (&next_nodes
, &cur_state
->nodes
);
2982 if (BE (err
!= REG_NOERROR
, 0))
2986 re_node_set_init_empty (&next_nodes
);
2988 if (str_idx
== top_str
|| (cur_state
&& cur_state
->has_backref
))
2990 if (next_nodes
.nelem
)
2992 err
= expand_bkref_cache (mctx
, &next_nodes
, str_idx
,
2994 if (BE (err
!= REG_NOERROR
, 0))
2996 re_node_set_free (&next_nodes
);
3000 cur_state
= re_acquire_state_context (&err
, dfa
, &next_nodes
, context
);
3001 if (BE (cur_state
== NULL
&& err
!= REG_NOERROR
, 0))
3003 re_node_set_free (&next_nodes
);
3006 mctx
->state_log
[str_idx
] = cur_state
;
3009 for (null_cnt
= 0; str_idx
< last_str
&& null_cnt
<= mctx
->max_mb_elem_len
;)
3011 re_node_set_empty (&next_nodes
);
3012 if (mctx
->state_log
[str_idx
+ 1])
3014 err
= re_node_set_merge (&next_nodes
,
3015 &mctx
->state_log
[str_idx
+ 1]->nodes
);
3016 if (BE (err
!= REG_NOERROR
, 0))
3018 re_node_set_free (&next_nodes
);
3024 err
= check_arrival_add_next_nodes (mctx
, str_idx
,
3025 &cur_state
->non_eps_nodes
,
3027 if (BE (err
!= REG_NOERROR
, 0))
3029 re_node_set_free (&next_nodes
);
3034 if (next_nodes
.nelem
)
3036 err
= check_arrival_expand_ecl (dfa
, &next_nodes
, subexp_num
, type
);
3037 if (BE (err
!= REG_NOERROR
, 0))
3039 re_node_set_free (&next_nodes
);
3042 err
= expand_bkref_cache (mctx
, &next_nodes
, str_idx
,
3044 if (BE (err
!= REG_NOERROR
, 0))
3046 re_node_set_free (&next_nodes
);
3050 context
= re_string_context_at (&mctx
->input
, str_idx
- 1, mctx
->eflags
);
3051 cur_state
= re_acquire_state_context (&err
, dfa
, &next_nodes
, context
);
3052 if (BE (cur_state
== NULL
&& err
!= REG_NOERROR
, 0))
3054 re_node_set_free (&next_nodes
);
3057 mctx
->state_log
[str_idx
] = cur_state
;
3058 null_cnt
= cur_state
== NULL
? null_cnt
+ 1 : 0;
3060 re_node_set_free (&next_nodes
);
3061 cur_nodes
= (mctx
->state_log
[last_str
] == NULL
? NULL
3062 : &mctx
->state_log
[last_str
]->nodes
);
3063 path
->next_idx
= str_idx
;
3066 mctx
->state_log
= backup_state_log
;
3067 mctx
->input
.cur_idx
= backup_cur_idx
;
3069 /* Then check the current node set has the node LAST_NODE. */
3070 if (cur_nodes
!= NULL
&& re_node_set_contains (cur_nodes
, last_node
))
3076 /* Helper functions for check_arrival. */
3078 /* Calculate the destination nodes of CUR_NODES at STR_IDX, and append them
3080 TODO: This function is similar to the functions transit_state*(),
3081 however this function has many additional works.
3082 Can't we unify them? */
3084 static reg_errcode_t
3085 internal_function __attribute_warn_unused_result__
3086 check_arrival_add_next_nodes (re_match_context_t
*mctx
, Idx str_idx
,
3087 re_node_set
*cur_nodes
, re_node_set
*next_nodes
)
3089 const re_dfa_t
*const dfa
= mctx
->dfa
;
3092 #ifdef RE_ENABLE_I18N
3093 reg_errcode_t err
= REG_NOERROR
;
3095 re_node_set union_set
;
3096 re_node_set_init_empty (&union_set
);
3097 for (cur_idx
= 0; cur_idx
< cur_nodes
->nelem
; ++cur_idx
)
3100 Idx cur_node
= cur_nodes
->elems
[cur_idx
];
3102 re_token_type_t type
= dfa
->nodes
[cur_node
].type
;
3103 assert (!IS_EPSILON_NODE (type
));
3105 #ifdef RE_ENABLE_I18N
3106 /* If the node may accept "multi byte". */
3107 if (dfa
->nodes
[cur_node
].accept_mb
)
3109 naccepted
= check_node_accept_bytes (dfa
, cur_node
, &mctx
->input
,
3113 re_dfastate_t
*dest_state
;
3114 Idx next_node
= dfa
->nexts
[cur_node
];
3115 Idx next_idx
= str_idx
+ naccepted
;
3116 dest_state
= mctx
->state_log
[next_idx
];
3117 re_node_set_empty (&union_set
);
3120 err
= re_node_set_merge (&union_set
, &dest_state
->nodes
);
3121 if (BE (err
!= REG_NOERROR
, 0))
3123 re_node_set_free (&union_set
);
3127 ok
= re_node_set_insert (&union_set
, next_node
);
3130 re_node_set_free (&union_set
);
3133 mctx
->state_log
[next_idx
] = re_acquire_state (&err
, dfa
,
3135 if (BE (mctx
->state_log
[next_idx
] == NULL
3136 && err
!= REG_NOERROR
, 0))
3138 re_node_set_free (&union_set
);
3143 #endif /* RE_ENABLE_I18N */
3145 || check_node_accept (mctx
, dfa
->nodes
+ cur_node
, str_idx
))
3147 ok
= re_node_set_insert (next_nodes
, dfa
->nexts
[cur_node
]);
3150 re_node_set_free (&union_set
);
3155 re_node_set_free (&union_set
);
3159 /* For all the nodes in CUR_NODES, add the epsilon closures of them to
3160 CUR_NODES, however exclude the nodes which are:
3161 - inside the sub expression whose number is EX_SUBEXP, if FL_OPEN.
3162 - out of the sub expression whose number is EX_SUBEXP, if !FL_OPEN.
3165 static reg_errcode_t
3167 check_arrival_expand_ecl (const re_dfa_t
*dfa
, re_node_set
*cur_nodes
,
3168 Idx ex_subexp
, int type
)
3171 Idx idx
, outside_node
;
3172 re_node_set new_nodes
;
3174 assert (cur_nodes
->nelem
);
3176 err
= re_node_set_alloc (&new_nodes
, cur_nodes
->nelem
);
3177 if (BE (err
!= REG_NOERROR
, 0))
3179 /* Create a new node set NEW_NODES with the nodes which are epsilon
3180 closures of the node in CUR_NODES. */
3182 for (idx
= 0; idx
< cur_nodes
->nelem
; ++idx
)
3184 Idx cur_node
= cur_nodes
->elems
[idx
];
3185 const re_node_set
*eclosure
= dfa
->eclosures
+ cur_node
;
3186 outside_node
= find_subexp_node (dfa
, eclosure
, ex_subexp
, type
);
3187 if (outside_node
== REG_MISSING
)
3189 /* There are no problematic nodes, just merge them. */
3190 err
= re_node_set_merge (&new_nodes
, eclosure
);
3191 if (BE (err
!= REG_NOERROR
, 0))
3193 re_node_set_free (&new_nodes
);
3199 /* There are problematic nodes, re-calculate incrementally. */
3200 err
= check_arrival_expand_ecl_sub (dfa
, &new_nodes
, cur_node
,
3202 if (BE (err
!= REG_NOERROR
, 0))
3204 re_node_set_free (&new_nodes
);
3209 re_node_set_free (cur_nodes
);
3210 *cur_nodes
= new_nodes
;
3214 /* Helper function for check_arrival_expand_ecl.
3215 Check incrementally the epsilon closure of TARGET, and if it isn't
3216 problematic append it to DST_NODES. */
3218 static reg_errcode_t
3219 internal_function __attribute_warn_unused_result__
3220 check_arrival_expand_ecl_sub (const re_dfa_t
*dfa
, re_node_set
*dst_nodes
,
3221 Idx target
, Idx ex_subexp
, int type
)
3224 for (cur_node
= target
; !re_node_set_contains (dst_nodes
, cur_node
);)
3228 if (dfa
->nodes
[cur_node
].type
== type
3229 && dfa
->nodes
[cur_node
].opr
.idx
== ex_subexp
)
3231 if (type
== OP_CLOSE_SUBEXP
)
3233 ok
= re_node_set_insert (dst_nodes
, cur_node
);
3239 ok
= re_node_set_insert (dst_nodes
, cur_node
);
3242 if (dfa
->edests
[cur_node
].nelem
== 0)
3244 if (dfa
->edests
[cur_node
].nelem
== 2)
3247 err
= check_arrival_expand_ecl_sub (dfa
, dst_nodes
,
3248 dfa
->edests
[cur_node
].elems
[1],
3250 if (BE (err
!= REG_NOERROR
, 0))
3253 cur_node
= dfa
->edests
[cur_node
].elems
[0];
3259 /* For all the back references in the current state, calculate the
3260 destination of the back references by the appropriate entry
3261 in MCTX->BKREF_ENTS. */
3263 static reg_errcode_t
3264 internal_function __attribute_warn_unused_result__
3265 expand_bkref_cache (re_match_context_t
*mctx
, re_node_set
*cur_nodes
,
3266 Idx cur_str
, Idx subexp_num
, int type
)
3268 const re_dfa_t
*const dfa
= mctx
->dfa
;
3270 Idx cache_idx_start
= search_cur_bkref_entry (mctx
, cur_str
);
3271 struct re_backref_cache_entry
*ent
;
3273 if (cache_idx_start
== REG_MISSING
)
3277 ent
= mctx
->bkref_ents
+ cache_idx_start
;
3280 Idx to_idx
, next_node
;
3282 /* Is this entry ENT is appropriate? */
3283 if (!re_node_set_contains (cur_nodes
, ent
->node
))
3286 to_idx
= cur_str
+ ent
->subexp_to
- ent
->subexp_from
;
3287 /* Calculate the destination of the back reference, and append it
3288 to MCTX->STATE_LOG. */
3289 if (to_idx
== cur_str
)
3291 /* The backreference did epsilon transit, we must re-check all the
3292 node in the current state. */
3293 re_node_set new_dests
;
3294 reg_errcode_t err2
, err3
;
3295 next_node
= dfa
->edests
[ent
->node
].elems
[0];
3296 if (re_node_set_contains (cur_nodes
, next_node
))
3298 err
= re_node_set_init_1 (&new_dests
, next_node
);
3299 err2
= check_arrival_expand_ecl (dfa
, &new_dests
, subexp_num
, type
);
3300 err3
= re_node_set_merge (cur_nodes
, &new_dests
);
3301 re_node_set_free (&new_dests
);
3302 if (BE (err
!= REG_NOERROR
|| err2
!= REG_NOERROR
3303 || err3
!= REG_NOERROR
, 0))
3305 err
= (err
!= REG_NOERROR
? err
3306 : (err2
!= REG_NOERROR
? err2
: err3
));
3309 /* TODO: It is still inefficient... */
3314 re_node_set union_set
;
3315 next_node
= dfa
->nexts
[ent
->node
];
3316 if (mctx
->state_log
[to_idx
])
3319 if (re_node_set_contains (&mctx
->state_log
[to_idx
]->nodes
,
3322 err
= re_node_set_init_copy (&union_set
,
3323 &mctx
->state_log
[to_idx
]->nodes
);
3324 ok
= re_node_set_insert (&union_set
, next_node
);
3325 if (BE (err
!= REG_NOERROR
|| ! ok
, 0))
3327 re_node_set_free (&union_set
);
3328 err
= err
!= REG_NOERROR
? err
: REG_ESPACE
;
3334 err
= re_node_set_init_1 (&union_set
, next_node
);
3335 if (BE (err
!= REG_NOERROR
, 0))
3338 mctx
->state_log
[to_idx
] = re_acquire_state (&err
, dfa
, &union_set
);
3339 re_node_set_free (&union_set
);
3340 if (BE (mctx
->state_log
[to_idx
] == NULL
3341 && err
!= REG_NOERROR
, 0))
3345 while (ent
++->more
);
3349 /* Build transition table for the state.
3350 Return true if successful. */
3354 build_trtable (const re_dfa_t
*dfa
, re_dfastate_t
*state
)
3359 bool need_word_trtable
= false;
3360 bitset_word_t elem
, mask
;
3361 bool dests_node_malloced
= false;
3362 bool dest_states_malloced
= false;
3363 Idx ndests
; /* Number of the destination states from 'state'. */
3364 re_dfastate_t
**trtable
;
3365 re_dfastate_t
**dest_states
= NULL
, **dest_states_word
, **dest_states_nl
;
3366 re_node_set follows
, *dests_node
;
3368 bitset_t acceptable
;
3372 re_node_set dests_node
[SBC_MAX
];
3373 bitset_t dests_ch
[SBC_MAX
];
3376 /* We build DFA states which corresponds to the destination nodes
3377 from 'state'. 'dests_node[i]' represents the nodes which i-th
3378 destination state contains, and 'dests_ch[i]' represents the
3379 characters which i-th destination state accepts. */
3380 if (__libc_use_alloca (sizeof (struct dests_alloc
)))
3381 dests_alloc
= (struct dests_alloc
*) alloca (sizeof (struct dests_alloc
));
3384 dests_alloc
= re_malloc (struct dests_alloc
, 1);
3385 if (BE (dests_alloc
== NULL
, 0))
3387 dests_node_malloced
= true;
3389 dests_node
= dests_alloc
->dests_node
;
3390 dests_ch
= dests_alloc
->dests_ch
;
3392 /* Initialize transition table. */
3393 state
->word_trtable
= state
->trtable
= NULL
;
3395 /* At first, group all nodes belonging to 'state' into several
3397 ndests
= group_nodes_into_DFAstates (dfa
, state
, dests_node
, dests_ch
);
3398 if (BE (! REG_VALID_NONZERO_INDEX (ndests
), 0))
3400 if (dests_node_malloced
)
3402 /* Return false in case of an error, true otherwise. */
3405 state
->trtable
= (re_dfastate_t
**)
3406 calloc (sizeof (re_dfastate_t
*), SBC_MAX
);
3407 if (BE (state
->trtable
== NULL
, 0))
3414 err
= re_node_set_alloc (&follows
, ndests
+ 1);
3415 if (BE (err
!= REG_NOERROR
, 0))
3418 /* Avoid arithmetic overflow in size calculation. */
3419 if (BE ((((SIZE_MAX
- (sizeof (re_node_set
) + sizeof (bitset_t
)) * SBC_MAX
)
3420 / (3 * sizeof (re_dfastate_t
*)))
3425 if (__libc_use_alloca ((sizeof (re_node_set
) + sizeof (bitset_t
)) * SBC_MAX
3426 + ndests
* 3 * sizeof (re_dfastate_t
*)))
3427 dest_states
= (re_dfastate_t
**)
3428 alloca (ndests
* 3 * sizeof (re_dfastate_t
*));
3431 dest_states
= (re_dfastate_t
**)
3432 malloc (ndests
* 3 * sizeof (re_dfastate_t
*));
3433 if (BE (dest_states
== NULL
, 0))
3436 if (dest_states_malloced
)
3438 re_node_set_free (&follows
);
3439 for (i
= 0; i
< ndests
; ++i
)
3440 re_node_set_free (dests_node
+ i
);
3441 if (dests_node_malloced
)
3445 dest_states_malloced
= true;
3447 dest_states_word
= dest_states
+ ndests
;
3448 dest_states_nl
= dest_states_word
+ ndests
;
3449 bitset_empty (acceptable
);
3451 /* Then build the states for all destinations. */
3452 for (i
= 0; i
< ndests
; ++i
)
3455 re_node_set_empty (&follows
);
3456 /* Merge the follows of this destination states. */
3457 for (j
= 0; j
< dests_node
[i
].nelem
; ++j
)
3459 next_node
= dfa
->nexts
[dests_node
[i
].elems
[j
]];
3460 if (next_node
!= REG_MISSING
)
3462 err
= re_node_set_merge (&follows
, dfa
->eclosures
+ next_node
);
3463 if (BE (err
!= REG_NOERROR
, 0))
3467 dest_states
[i
] = re_acquire_state_context (&err
, dfa
, &follows
, 0);
3468 if (BE (dest_states
[i
] == NULL
&& err
!= REG_NOERROR
, 0))
3470 /* If the new state has context constraint,
3471 build appropriate states for these contexts. */
3472 if (dest_states
[i
]->has_constraint
)
3474 dest_states_word
[i
] = re_acquire_state_context (&err
, dfa
, &follows
,
3476 if (BE (dest_states_word
[i
] == NULL
&& err
!= REG_NOERROR
, 0))
3479 if (dest_states
[i
] != dest_states_word
[i
] && dfa
->mb_cur_max
> 1)
3480 need_word_trtable
= true;
3482 dest_states_nl
[i
] = re_acquire_state_context (&err
, dfa
, &follows
,
3484 if (BE (dest_states_nl
[i
] == NULL
&& err
!= REG_NOERROR
, 0))
3489 dest_states_word
[i
] = dest_states
[i
];
3490 dest_states_nl
[i
] = dest_states
[i
];
3492 bitset_merge (acceptable
, dests_ch
[i
]);
3495 if (!BE (need_word_trtable
, 0))
3497 /* We don't care about whether the following character is a word
3498 character, or we are in a single-byte character set so we can
3499 discern by looking at the character code: allocate a
3500 256-entry transition table. */
3501 trtable
= state
->trtable
=
3502 (re_dfastate_t
**) calloc (sizeof (re_dfastate_t
*), SBC_MAX
);
3503 if (BE (trtable
== NULL
, 0))
3506 /* For all characters ch...: */
3507 for (i
= 0; i
< BITSET_WORDS
; ++i
)
3508 for (ch
= i
* BITSET_WORD_BITS
, elem
= acceptable
[i
], mask
= 1;
3510 mask
<<= 1, elem
>>= 1, ++ch
)
3511 if (BE (elem
& 1, 0))
3513 /* There must be exactly one destination which accepts
3514 character ch. See group_nodes_into_DFAstates. */
3515 for (j
= 0; (dests_ch
[j
][i
] & mask
) == 0; ++j
)
3518 /* j-th destination accepts the word character ch. */
3519 if (dfa
->word_char
[i
] & mask
)
3520 trtable
[ch
] = dest_states_word
[j
];
3522 trtable
[ch
] = dest_states
[j
];
3527 /* We care about whether the following character is a word
3528 character, and we are in a multi-byte character set: discern
3529 by looking at the character code: build two 256-entry
3530 transition tables, one starting at trtable[0] and one
3531 starting at trtable[SBC_MAX]. */
3532 trtable
= state
->word_trtable
=
3533 (re_dfastate_t
**) calloc (sizeof (re_dfastate_t
*), 2 * SBC_MAX
);
3534 if (BE (trtable
== NULL
, 0))
3537 /* For all characters ch...: */
3538 for (i
= 0; i
< BITSET_WORDS
; ++i
)
3539 for (ch
= i
* BITSET_WORD_BITS
, elem
= acceptable
[i
], mask
= 1;
3541 mask
<<= 1, elem
>>= 1, ++ch
)
3542 if (BE (elem
& 1, 0))
3544 /* There must be exactly one destination which accepts
3545 character ch. See group_nodes_into_DFAstates. */
3546 for (j
= 0; (dests_ch
[j
][i
] & mask
) == 0; ++j
)
3549 /* j-th destination accepts the word character ch. */
3550 trtable
[ch
] = dest_states
[j
];
3551 trtable
[ch
+ SBC_MAX
] = dest_states_word
[j
];
3556 if (bitset_contain (acceptable
, NEWLINE_CHAR
))
3558 /* The current state accepts newline character. */
3559 for (j
= 0; j
< ndests
; ++j
)
3560 if (bitset_contain (dests_ch
[j
], NEWLINE_CHAR
))
3562 /* k-th destination accepts newline character. */
3563 trtable
[NEWLINE_CHAR
] = dest_states_nl
[j
];
3564 if (need_word_trtable
)
3565 trtable
[NEWLINE_CHAR
+ SBC_MAX
] = dest_states_nl
[j
];
3566 /* There must be only one destination which accepts
3567 newline. See group_nodes_into_DFAstates. */
3572 if (dest_states_malloced
)
3575 re_node_set_free (&follows
);
3576 for (i
= 0; i
< ndests
; ++i
)
3577 re_node_set_free (dests_node
+ i
);
3579 if (dests_node_malloced
)
3585 /* Group all nodes belonging to STATE into several destinations.
3586 Then for all destinations, set the nodes belonging to the destination
3587 to DESTS_NODE[i] and set the characters accepted by the destination
3588 to DEST_CH[i]. This function return the number of destinations. */
3592 group_nodes_into_DFAstates (const re_dfa_t
*dfa
, const re_dfastate_t
*state
,
3593 re_node_set
*dests_node
, bitset_t
*dests_ch
)
3598 Idx ndests
; /* Number of the destinations from 'state'. */
3599 bitset_t accepts
; /* Characters a node can accept. */
3600 const re_node_set
*cur_nodes
= &state
->nodes
;
3601 bitset_empty (accepts
);
3604 /* For all the nodes belonging to 'state', */
3605 for (i
= 0; i
< cur_nodes
->nelem
; ++i
)
3607 re_token_t
*node
= &dfa
->nodes
[cur_nodes
->elems
[i
]];
3608 re_token_type_t type
= node
->type
;
3609 unsigned int constraint
= node
->constraint
;
3611 /* Enumerate all single byte character this node can accept. */
3612 if (type
== CHARACTER
)
3613 bitset_set (accepts
, node
->opr
.c
);
3614 else if (type
== SIMPLE_BRACKET
)
3616 bitset_merge (accepts
, node
->opr
.sbcset
);
3618 else if (type
== OP_PERIOD
)
3620 #ifdef RE_ENABLE_I18N
3621 if (dfa
->mb_cur_max
> 1)
3622 bitset_merge (accepts
, dfa
->sb_char
);
3625 bitset_set_all (accepts
);
3626 if (!(dfa
->syntax
& RE_DOT_NEWLINE
))
3627 bitset_clear (accepts
, '\n');
3628 if (dfa
->syntax
& RE_DOT_NOT_NULL
)
3629 bitset_clear (accepts
, '\0');
3631 #ifdef RE_ENABLE_I18N
3632 else if (type
== OP_UTF8_PERIOD
)
3634 if (ASCII_CHARS
% BITSET_WORD_BITS
== 0)
3635 memset (accepts
, -1, ASCII_CHARS
/ CHAR_BIT
);
3637 bitset_merge (accepts
, utf8_sb_map
);
3638 if (!(dfa
->syntax
& RE_DOT_NEWLINE
))
3639 bitset_clear (accepts
, '\n');
3640 if (dfa
->syntax
& RE_DOT_NOT_NULL
)
3641 bitset_clear (accepts
, '\0');
3647 /* Check the 'accepts' and sift the characters which are not
3648 match it the context. */
3651 if (constraint
& NEXT_NEWLINE_CONSTRAINT
)
3653 bool accepts_newline
= bitset_contain (accepts
, NEWLINE_CHAR
);
3654 bitset_empty (accepts
);
3655 if (accepts_newline
)
3656 bitset_set (accepts
, NEWLINE_CHAR
);
3660 if (constraint
& NEXT_ENDBUF_CONSTRAINT
)
3662 bitset_empty (accepts
);
3666 if (constraint
& NEXT_WORD_CONSTRAINT
)
3668 bitset_word_t any_set
= 0;
3669 if (type
== CHARACTER
&& !node
->word_char
)
3671 bitset_empty (accepts
);
3674 #ifdef RE_ENABLE_I18N
3675 if (dfa
->mb_cur_max
> 1)
3676 for (j
= 0; j
< BITSET_WORDS
; ++j
)
3677 any_set
|= (accepts
[j
] &= (dfa
->word_char
[j
] | ~dfa
->sb_char
[j
]));
3680 for (j
= 0; j
< BITSET_WORDS
; ++j
)
3681 any_set
|= (accepts
[j
] &= dfa
->word_char
[j
]);
3685 if (constraint
& NEXT_NOTWORD_CONSTRAINT
)
3687 bitset_word_t any_set
= 0;
3688 if (type
== CHARACTER
&& node
->word_char
)
3690 bitset_empty (accepts
);
3693 #ifdef RE_ENABLE_I18N
3694 if (dfa
->mb_cur_max
> 1)
3695 for (j
= 0; j
< BITSET_WORDS
; ++j
)
3696 any_set
|= (accepts
[j
] &= ~(dfa
->word_char
[j
] & dfa
->sb_char
[j
]));
3699 for (j
= 0; j
< BITSET_WORDS
; ++j
)
3700 any_set
|= (accepts
[j
] &= ~dfa
->word_char
[j
]);
3706 /* Then divide 'accepts' into DFA states, or create a new
3707 state. Above, we make sure that accepts is not empty. */
3708 for (j
= 0; j
< ndests
; ++j
)
3710 bitset_t intersec
; /* Intersection sets, see below. */
3712 /* Flags, see below. */
3713 bitset_word_t has_intersec
, not_subset
, not_consumed
;
3715 /* Optimization, skip if this state doesn't accept the character. */
3716 if (type
== CHARACTER
&& !bitset_contain (dests_ch
[j
], node
->opr
.c
))
3719 /* Enumerate the intersection set of this state and 'accepts'. */
3721 for (k
= 0; k
< BITSET_WORDS
; ++k
)
3722 has_intersec
|= intersec
[k
] = accepts
[k
] & dests_ch
[j
][k
];
3723 /* And skip if the intersection set is empty. */
3727 /* Then check if this state is a subset of 'accepts'. */
3728 not_subset
= not_consumed
= 0;
3729 for (k
= 0; k
< BITSET_WORDS
; ++k
)
3731 not_subset
|= remains
[k
] = ~accepts
[k
] & dests_ch
[j
][k
];
3732 not_consumed
|= accepts
[k
] = accepts
[k
] & ~dests_ch
[j
][k
];
3735 /* If this state isn't a subset of 'accepts', create a
3736 new group state, which has the 'remains'. */
3739 bitset_copy (dests_ch
[ndests
], remains
);
3740 bitset_copy (dests_ch
[j
], intersec
);
3741 err
= re_node_set_init_copy (dests_node
+ ndests
, &dests_node
[j
]);
3742 if (BE (err
!= REG_NOERROR
, 0))
3747 /* Put the position in the current group. */
3748 ok
= re_node_set_insert (&dests_node
[j
], cur_nodes
->elems
[i
]);
3752 /* If all characters are consumed, go to next node. */
3756 /* Some characters remain, create a new group. */
3759 bitset_copy (dests_ch
[ndests
], accepts
);
3760 err
= re_node_set_init_1 (dests_node
+ ndests
, cur_nodes
->elems
[i
]);
3761 if (BE (err
!= REG_NOERROR
, 0))
3764 bitset_empty (accepts
);
3769 for (j
= 0; j
< ndests
; ++j
)
3770 re_node_set_free (dests_node
+ j
);
3774 #ifdef RE_ENABLE_I18N
3775 /* Check how many bytes the node 'dfa->nodes[node_idx]' accepts.
3776 Return the number of the bytes the node accepts.
3777 STR_IDX is the current index of the input string.
3779 This function handles the nodes which can accept one character, or
3780 one collating element like '.', '[a-z]', opposite to the other nodes
3781 can only accept one byte. */
3785 check_node_accept_bytes (const re_dfa_t
*dfa
, Idx node_idx
,
3786 const re_string_t
*input
, Idx str_idx
)
3788 const re_token_t
*node
= dfa
->nodes
+ node_idx
;
3789 int char_len
, elem_len
;
3792 if (BE (node
->type
== OP_UTF8_PERIOD
, 0))
3794 unsigned char c
= re_string_byte_at (input
, str_idx
), d
;
3795 if (BE (c
< 0xc2, 1))
3798 if (str_idx
+ 2 > input
->len
)
3801 d
= re_string_byte_at (input
, str_idx
+ 1);
3803 return (d
< 0x80 || d
> 0xbf) ? 0 : 2;
3807 if (c
== 0xe0 && d
< 0xa0)
3813 if (c
== 0xf0 && d
< 0x90)
3819 if (c
== 0xf8 && d
< 0x88)
3825 if (c
== 0xfc && d
< 0x84)
3831 if (str_idx
+ char_len
> input
->len
)
3834 for (i
= 1; i
< char_len
; ++i
)
3836 d
= re_string_byte_at (input
, str_idx
+ i
);
3837 if (d
< 0x80 || d
> 0xbf)
3843 char_len
= re_string_char_size_at (input
, str_idx
);
3844 if (node
->type
== OP_PERIOD
)
3848 /* FIXME: I don't think this if is needed, as both '\n'
3849 and '\0' are char_len == 1. */
3850 /* '.' accepts any one character except the following two cases. */
3851 if ((!(dfa
->syntax
& RE_DOT_NEWLINE
) &&
3852 re_string_byte_at (input
, str_idx
) == '\n') ||
3853 ((dfa
->syntax
& RE_DOT_NOT_NULL
) &&
3854 re_string_byte_at (input
, str_idx
) == '\0'))
3859 elem_len
= re_string_elem_size_at (input
, str_idx
);
3860 if ((elem_len
<= 1 && char_len
<= 1) || char_len
== 0)
3863 if (node
->type
== COMPLEX_BRACKET
)
3865 const re_charset_t
*cset
= node
->opr
.mbcset
;
3867 const unsigned char *pin
3868 = ((const unsigned char *) re_string_get_buffer (input
) + str_idx
);
3873 wchar_t wc
= ((cset
->nranges
|| cset
->nchar_classes
|| cset
->nmbchars
)
3874 ? re_string_wchar_at (input
, str_idx
) : 0);
3876 /* match with multibyte character? */
3877 for (i
= 0; i
< cset
->nmbchars
; ++i
)
3878 if (wc
== cset
->mbchars
[i
])
3880 match_len
= char_len
;
3881 goto check_node_accept_bytes_match
;
3883 /* match with character_class? */
3884 for (i
= 0; i
< cset
->nchar_classes
; ++i
)
3886 wctype_t wt
= cset
->char_classes
[i
];
3887 if (__iswctype (wc
, wt
))
3889 match_len
= char_len
;
3890 goto check_node_accept_bytes_match
;
3895 nrules
= _NL_CURRENT_WORD (LC_COLLATE
, _NL_COLLATE_NRULES
);
3898 unsigned int in_collseq
= 0;
3899 const int32_t *table
, *indirect
;
3900 const unsigned char *weights
, *extra
;
3901 const char *collseqwc
;
3902 /* This #include defines a local function! */
3903 # include <locale/weight.h>
3905 /* match with collating_symbol? */
3906 if (cset
->ncoll_syms
)
3907 extra
= (const unsigned char *)
3908 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_SYMB_EXTRAMB
);
3909 for (i
= 0; i
< cset
->ncoll_syms
; ++i
)
3911 const unsigned char *coll_sym
= extra
+ cset
->coll_syms
[i
];
3912 /* Compare the length of input collating element and
3913 the length of current collating element. */
3914 if (*coll_sym
!= elem_len
)
3916 /* Compare each bytes. */
3917 for (j
= 0; j
< *coll_sym
; j
++)
3918 if (pin
[j
] != coll_sym
[1 + j
])
3922 /* Match if every bytes is equal. */
3924 goto check_node_accept_bytes_match
;
3930 if (elem_len
<= char_len
)
3932 collseqwc
= _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_COLLSEQWC
);
3933 in_collseq
= __collseq_table_lookup (collseqwc
, wc
);
3936 in_collseq
= find_collation_sequence_value (pin
, elem_len
);
3938 /* match with range expression? */
3939 /* FIXME: Implement rational ranges here, too. */
3940 for (i
= 0; i
< cset
->nranges
; ++i
)
3941 if (cset
->range_starts
[i
] <= in_collseq
3942 && in_collseq
<= cset
->range_ends
[i
])
3944 match_len
= elem_len
;
3945 goto check_node_accept_bytes_match
;
3948 /* match with equivalence_class? */
3949 if (cset
->nequiv_classes
)
3951 const unsigned char *cp
= pin
;
3952 table
= (const int32_t *)
3953 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_TABLEMB
);
3954 weights
= (const unsigned char *)
3955 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_WEIGHTMB
);
3956 extra
= (const unsigned char *)
3957 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_EXTRAMB
);
3958 indirect
= (const int32_t *)
3959 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_INDIRECTMB
);
3960 int32_t idx
= findidx (&cp
, elem_len
);
3962 for (i
= 0; i
< cset
->nequiv_classes
; ++i
)
3964 int32_t equiv_class_idx
= cset
->equiv_classes
[i
];
3965 size_t weight_len
= weights
[idx
& 0xffffff];
3966 if (weight_len
== weights
[equiv_class_idx
& 0xffffff]
3967 && (idx
>> 24) == (equiv_class_idx
>> 24))
3972 equiv_class_idx
&= 0xffffff;
3974 while (cnt
<= weight_len
3975 && (weights
[equiv_class_idx
+ 1 + cnt
]
3976 == weights
[idx
+ 1 + cnt
]))
3978 if (cnt
> weight_len
)
3980 match_len
= elem_len
;
3981 goto check_node_accept_bytes_match
;
3990 /* match with range expression? */
3991 for (i
= 0; i
< cset
->nranges
; ++i
)
3993 if (cset
->range_starts
[i
] <= wc
&& wc
<= cset
->range_ends
[i
])
3995 match_len
= char_len
;
3996 goto check_node_accept_bytes_match
;
4000 check_node_accept_bytes_match
:
4001 if (!cset
->non_match
)
4008 return (elem_len
> char_len
) ? elem_len
: char_len
;
4017 find_collation_sequence_value (const unsigned char *mbs
, size_t mbs_len
)
4019 uint32_t nrules
= _NL_CURRENT_WORD (LC_COLLATE
, _NL_COLLATE_NRULES
);
4024 /* No valid character. Match it as a single byte character. */
4025 const unsigned char *collseq
= (const unsigned char *)
4026 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_COLLSEQMB
);
4027 return collseq
[mbs
[0]];
4034 const unsigned char *extra
= (const unsigned char *)
4035 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_SYMB_EXTRAMB
);
4036 int32_t extrasize
= (const unsigned char *)
4037 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_SYMB_EXTRAMB
+ 1) - extra
;
4039 for (idx
= 0; idx
< extrasize
;)
4043 int32_t elem_mbs_len
;
4044 /* Skip the name of collating element name. */
4045 idx
= idx
+ extra
[idx
] + 1;
4046 elem_mbs_len
= extra
[idx
++];
4047 if (mbs_len
== elem_mbs_len
)
4049 for (mbs_cnt
= 0; mbs_cnt
< elem_mbs_len
; ++mbs_cnt
)
4050 if (extra
[idx
+ mbs_cnt
] != mbs
[mbs_cnt
])
4052 if (mbs_cnt
== elem_mbs_len
)
4053 /* Found the entry. */
4056 /* Skip the byte sequence of the collating element. */
4057 idx
+= elem_mbs_len
;
4058 /* Adjust for the alignment. */
4059 idx
= (idx
+ 3) & ~3;
4060 /* Skip the collation sequence value. */
4061 idx
+= sizeof (uint32_t);
4062 /* Skip the wide char sequence of the collating element. */
4063 idx
= idx
+ sizeof (uint32_t) * (*(int32_t *) (extra
+ idx
) + 1);
4064 /* If we found the entry, return the sequence value. */
4066 return *(uint32_t *) (extra
+ idx
);
4067 /* Skip the collation sequence value. */
4068 idx
+= sizeof (uint32_t);
4074 #endif /* RE_ENABLE_I18N */
4076 /* Check whether the node accepts the byte which is IDX-th
4077 byte of the INPUT. */
4081 check_node_accept (const re_match_context_t
*mctx
, const re_token_t
*node
,
4085 ch
= re_string_byte_at (&mctx
->input
, idx
);
4089 if (node
->opr
.c
!= ch
)
4093 case SIMPLE_BRACKET
:
4094 if (!bitset_contain (node
->opr
.sbcset
, ch
))
4098 #ifdef RE_ENABLE_I18N
4099 case OP_UTF8_PERIOD
:
4100 if (ch
>= ASCII_CHARS
)
4102 #if defined __GNUC__ && __GNUC__ >= 7
4103 __attribute__ ((fallthrough
));
4108 if ((ch
== '\n' && !(mctx
->dfa
->syntax
& RE_DOT_NEWLINE
))
4109 || (ch
== '\0' && (mctx
->dfa
->syntax
& RE_DOT_NOT_NULL
)))
4117 if (node
->constraint
)
4119 /* The node has constraints. Check whether the current context
4120 satisfies the constraints. */
4121 unsigned int context
= re_string_context_at (&mctx
->input
, idx
,
4123 if (NOT_SATISFY_NEXT_CONSTRAINT (node
->constraint
, context
))
4130 /* Extend the buffers, if the buffers have run out. */
4132 static reg_errcode_t
4133 internal_function __attribute_warn_unused_result__
4134 extend_buffers (re_match_context_t
*mctx
, int min_len
)
4137 re_string_t
*pstr
= &mctx
->input
;
4139 /* Avoid overflow. */
4140 if (BE (MIN (IDX_MAX
, SIZE_MAX
/ sizeof (re_dfastate_t
*)) / 2
4141 <= pstr
->bufs_len
, 0))
4144 /* Double the lengths of the buffers, but allocate at least MIN_LEN. */
4145 ret
= re_string_realloc_buffers (pstr
,
4147 MIN (pstr
->len
, pstr
->bufs_len
* 2)));
4148 if (BE (ret
!= REG_NOERROR
, 0))
4151 if (mctx
->state_log
!= NULL
)
4153 /* And double the length of state_log. */
4154 /* XXX We have no indication of the size of this buffer. If this
4155 allocation fail we have no indication that the state_log array
4156 does not have the right size. */
4157 re_dfastate_t
**new_array
= re_realloc (mctx
->state_log
, re_dfastate_t
*,
4158 pstr
->bufs_len
+ 1);
4159 if (BE (new_array
== NULL
, 0))
4161 mctx
->state_log
= new_array
;
4164 /* Then reconstruct the buffers. */
4167 #ifdef RE_ENABLE_I18N
4168 if (pstr
->mb_cur_max
> 1)
4170 ret
= build_wcs_upper_buffer (pstr
);
4171 if (BE (ret
!= REG_NOERROR
, 0))
4175 #endif /* RE_ENABLE_I18N */
4176 build_upper_buffer (pstr
);
4180 #ifdef RE_ENABLE_I18N
4181 if (pstr
->mb_cur_max
> 1)
4182 build_wcs_buffer (pstr
);
4184 #endif /* RE_ENABLE_I18N */
4186 if (pstr
->trans
!= NULL
)
4187 re_string_translate_buffer (pstr
);
4194 /* Functions for matching context. */
4196 /* Initialize MCTX. */
4198 static reg_errcode_t
4199 internal_function __attribute_warn_unused_result__
4200 match_ctx_init (re_match_context_t
*mctx
, int eflags
, Idx n
)
4202 mctx
->eflags
= eflags
;
4203 mctx
->match_last
= REG_MISSING
;
4206 /* Avoid overflow. */
4207 size_t max_object_size
=
4208 MAX (sizeof (struct re_backref_cache_entry
),
4209 sizeof (re_sub_match_top_t
*));
4210 if (BE (MIN (IDX_MAX
, SIZE_MAX
/ max_object_size
) < n
, 0))
4213 mctx
->bkref_ents
= re_malloc (struct re_backref_cache_entry
, n
);
4214 mctx
->sub_tops
= re_malloc (re_sub_match_top_t
*, n
);
4215 if (BE (mctx
->bkref_ents
== NULL
|| mctx
->sub_tops
== NULL
, 0))
4218 /* Already zero-ed by the caller.
4220 mctx->bkref_ents = NULL;
4221 mctx->nbkref_ents = 0;
4222 mctx->nsub_tops = 0; */
4223 mctx
->abkref_ents
= n
;
4224 mctx
->max_mb_elem_len
= 1;
4225 mctx
->asub_tops
= n
;
4229 /* Clean the entries which depend on the current input in MCTX.
4230 This function must be invoked when the matcher changes the start index
4231 of the input, or changes the input string. */
4235 match_ctx_clean (re_match_context_t
*mctx
)
4238 for (st_idx
= 0; st_idx
< mctx
->nsub_tops
; ++st_idx
)
4241 re_sub_match_top_t
*top
= mctx
->sub_tops
[st_idx
];
4242 for (sl_idx
= 0; sl_idx
< top
->nlasts
; ++sl_idx
)
4244 re_sub_match_last_t
*last
= top
->lasts
[sl_idx
];
4245 re_free (last
->path
.array
);
4248 re_free (top
->lasts
);
4251 re_free (top
->path
->array
);
4252 re_free (top
->path
);
4257 mctx
->nsub_tops
= 0;
4258 mctx
->nbkref_ents
= 0;
4261 /* Free all the memory associated with MCTX. */
4265 match_ctx_free (re_match_context_t
*mctx
)
4267 /* First, free all the memory associated with MCTX->SUB_TOPS. */
4268 match_ctx_clean (mctx
);
4269 re_free (mctx
->sub_tops
);
4270 re_free (mctx
->bkref_ents
);
4273 /* Add a new backreference entry to MCTX.
4274 Note that we assume that caller never call this function with duplicate
4275 entry, and call with STR_IDX which isn't smaller than any existing entry.
4278 static reg_errcode_t
4279 internal_function __attribute_warn_unused_result__
4280 match_ctx_add_entry (re_match_context_t
*mctx
, Idx node
, Idx str_idx
, Idx from
,
4283 if (mctx
->nbkref_ents
>= mctx
->abkref_ents
)
4285 struct re_backref_cache_entry
* new_entry
;
4286 new_entry
= re_realloc (mctx
->bkref_ents
, struct re_backref_cache_entry
,
4287 mctx
->abkref_ents
* 2);
4288 if (BE (new_entry
== NULL
, 0))
4290 re_free (mctx
->bkref_ents
);
4293 mctx
->bkref_ents
= new_entry
;
4294 memset (mctx
->bkref_ents
+ mctx
->nbkref_ents
, '\0',
4295 sizeof (struct re_backref_cache_entry
) * mctx
->abkref_ents
);
4296 mctx
->abkref_ents
*= 2;
4298 if (mctx
->nbkref_ents
> 0
4299 && mctx
->bkref_ents
[mctx
->nbkref_ents
- 1].str_idx
== str_idx
)
4300 mctx
->bkref_ents
[mctx
->nbkref_ents
- 1].more
= 1;
4302 mctx
->bkref_ents
[mctx
->nbkref_ents
].node
= node
;
4303 mctx
->bkref_ents
[mctx
->nbkref_ents
].str_idx
= str_idx
;
4304 mctx
->bkref_ents
[mctx
->nbkref_ents
].subexp_from
= from
;
4305 mctx
->bkref_ents
[mctx
->nbkref_ents
].subexp_to
= to
;
4307 /* This is a cache that saves negative results of check_dst_limits_calc_pos.
4308 If bit N is clear, means that this entry won't epsilon-transition to
4309 an OP_OPEN_SUBEXP or OP_CLOSE_SUBEXP for the N+1-th subexpression. If
4310 it is set, check_dst_limits_calc_pos_1 will recurse and try to find one
4313 A backreference does not epsilon-transition unless it is empty, so set
4314 to all zeros if FROM != TO. */
4315 mctx
->bkref_ents
[mctx
->nbkref_ents
].eps_reachable_subexps_map
4316 = (from
== to
? -1 : 0);
4318 mctx
->bkref_ents
[mctx
->nbkref_ents
++].more
= 0;
4319 if (mctx
->max_mb_elem_len
< to
- from
)
4320 mctx
->max_mb_elem_len
= to
- from
;
4324 /* Return the first entry with the same str_idx, or REG_MISSING if none is
4325 found. Note that MCTX->BKREF_ENTS is already sorted by MCTX->STR_IDX. */
4329 search_cur_bkref_entry (const re_match_context_t
*mctx
, Idx str_idx
)
4331 Idx left
, right
, mid
, last
;
4332 last
= right
= mctx
->nbkref_ents
;
4333 for (left
= 0; left
< right
;)
4335 mid
= (left
+ right
) / 2;
4336 if (mctx
->bkref_ents
[mid
].str_idx
< str_idx
)
4341 if (left
< last
&& mctx
->bkref_ents
[left
].str_idx
== str_idx
)
4347 /* Register the node NODE, whose type is OP_OPEN_SUBEXP, and which matches
4350 static reg_errcode_t
4351 internal_function __attribute_warn_unused_result__
4352 match_ctx_add_subtop (re_match_context_t
*mctx
, Idx node
, Idx str_idx
)
4355 assert (mctx
->sub_tops
!= NULL
);
4356 assert (mctx
->asub_tops
> 0);
4358 if (BE (mctx
->nsub_tops
== mctx
->asub_tops
, 0))
4360 Idx new_asub_tops
= mctx
->asub_tops
* 2;
4361 re_sub_match_top_t
**new_array
= re_realloc (mctx
->sub_tops
,
4362 re_sub_match_top_t
*,
4364 if (BE (new_array
== NULL
, 0))
4366 mctx
->sub_tops
= new_array
;
4367 mctx
->asub_tops
= new_asub_tops
;
4369 mctx
->sub_tops
[mctx
->nsub_tops
] = calloc (1, sizeof (re_sub_match_top_t
));
4370 if (BE (mctx
->sub_tops
[mctx
->nsub_tops
] == NULL
, 0))
4372 mctx
->sub_tops
[mctx
->nsub_tops
]->node
= node
;
4373 mctx
->sub_tops
[mctx
->nsub_tops
++]->str_idx
= str_idx
;
4377 /* Register the node NODE, whose type is OP_CLOSE_SUBEXP, and which matches
4378 at STR_IDX, whose corresponding OP_OPEN_SUBEXP is SUB_TOP. */
4380 static re_sub_match_last_t
*
4382 match_ctx_add_sublast (re_sub_match_top_t
*subtop
, Idx node
, Idx str_idx
)
4384 re_sub_match_last_t
*new_entry
;
4385 if (BE (subtop
->nlasts
== subtop
->alasts
, 0))
4387 Idx new_alasts
= 2 * subtop
->alasts
+ 1;
4388 re_sub_match_last_t
**new_array
= re_realloc (subtop
->lasts
,
4389 re_sub_match_last_t
*,
4391 if (BE (new_array
== NULL
, 0))
4393 subtop
->lasts
= new_array
;
4394 subtop
->alasts
= new_alasts
;
4396 new_entry
= calloc (1, sizeof (re_sub_match_last_t
));
4397 if (BE (new_entry
!= NULL
, 1))
4399 subtop
->lasts
[subtop
->nlasts
] = new_entry
;
4400 new_entry
->node
= node
;
4401 new_entry
->str_idx
= str_idx
;
4409 sift_ctx_init (re_sift_context_t
*sctx
, re_dfastate_t
**sifted_sts
,
4410 re_dfastate_t
**limited_sts
, Idx last_node
, Idx last_str_idx
)
4412 sctx
->sifted_states
= sifted_sts
;
4413 sctx
->limited_states
= limited_sts
;
4414 sctx
->last_node
= last_node
;
4415 sctx
->last_str_idx
= last_str_idx
;
4416 re_node_set_init_empty (&sctx
->limits
);