1 /* Extended regular expression matching and search library.
2 Copyright (C) 2002, 2003, 2004, 2005 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 Lesser General Public
8 License as published by the Free Software Foundation; either
9 version 2.1 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 Lesser General Public License for more details.
16 You should have received a copy of the GNU Lesser General Public
17 License along with the GNU C Library; if not, write to the Free
18 Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
21 static reg_errcode_t
match_ctx_init (re_match_context_t
*cache
, int eflags
,
22 int n
) internal_function
;
23 static void match_ctx_clean (re_match_context_t
*mctx
) internal_function
;
24 static void match_ctx_free (re_match_context_t
*cache
) internal_function
;
25 static reg_errcode_t
match_ctx_add_entry (re_match_context_t
*cache
, int node
,
26 int str_idx
, int from
, int to
)
28 static int search_cur_bkref_entry (const re_match_context_t
*mctx
, int str_idx
)
30 static reg_errcode_t
match_ctx_add_subtop (re_match_context_t
*mctx
, int node
,
31 int str_idx
) internal_function
;
32 static re_sub_match_last_t
* match_ctx_add_sublast (re_sub_match_top_t
*subtop
,
33 int node
, int str_idx
)
35 static void sift_ctx_init (re_sift_context_t
*sctx
, re_dfastate_t
**sifted_sts
,
36 re_dfastate_t
**limited_sts
, int last_node
,
39 static reg_errcode_t
re_search_internal (const regex_t
*preg
,
40 const char *string
, int length
,
41 int start
, int range
, int stop
,
42 size_t nmatch
, regmatch_t pmatch
[],
43 int eflags
) internal_function
;
44 static int re_search_2_stub (struct re_pattern_buffer
*bufp
,
45 const char *string1
, int length1
,
46 const char *string2
, int length2
,
47 int start
, int range
, struct re_registers
*regs
,
48 int stop
, int ret_len
) internal_function
;
49 static int re_search_stub (struct re_pattern_buffer
*bufp
,
50 const char *string
, int length
, int start
,
51 int range
, int stop
, struct re_registers
*regs
,
52 int ret_len
) internal_function
;
53 static unsigned re_copy_regs (struct re_registers
*regs
, regmatch_t
*pmatch
,
54 int nregs
, int regs_allocated
) internal_function
;
55 static inline re_dfastate_t
*acquire_init_state_context
56 (reg_errcode_t
*err
, const re_match_context_t
*mctx
, int idx
)
57 __attribute ((always_inline
)) internal_function
;
58 static reg_errcode_t
prune_impossible_nodes (re_match_context_t
*mctx
)
60 static int check_matching (re_match_context_t
*mctx
, int fl_longest_match
,
61 int *p_match_first
) internal_function
;
62 static int check_halt_node_context (const re_dfa_t
*dfa
, int node
,
63 unsigned int context
) internal_function
;
64 static int check_halt_state_context (const re_match_context_t
*mctx
,
65 const re_dfastate_t
*state
, int idx
)
67 static void update_regs (const re_dfa_t
*dfa
, regmatch_t
*pmatch
,
68 regmatch_t
*prev_idx_match
, int cur_node
,
69 int cur_idx
, int nmatch
) internal_function
;
70 static int proceed_next_node (const re_match_context_t
*mctx
,
71 int nregs
, regmatch_t
*regs
,
72 int *pidx
, int node
, re_node_set
*eps_via_nodes
,
73 struct re_fail_stack_t
*fs
) internal_function
;
74 static reg_errcode_t
push_fail_stack (struct re_fail_stack_t
*fs
,
75 int str_idx
, int dest_node
, int nregs
,
77 re_node_set
*eps_via_nodes
)
79 static int pop_fail_stack (struct re_fail_stack_t
*fs
, int *pidx
, int nregs
,
80 regmatch_t
*regs
, re_node_set
*eps_via_nodes
)
82 static reg_errcode_t
set_regs (const regex_t
*preg
,
83 const re_match_context_t
*mctx
,
84 size_t nmatch
, regmatch_t
*pmatch
,
85 int fl_backtrack
) internal_function
;
86 static reg_errcode_t
free_fail_stack_return (struct re_fail_stack_t
*fs
)
90 static int sift_states_iter_mb (const re_match_context_t
*mctx
,
91 re_sift_context_t
*sctx
,
92 int node_idx
, int str_idx
, int max_str_idx
)
94 #endif /* RE_ENABLE_I18N */
95 static reg_errcode_t
sift_states_backward (const re_match_context_t
*mctx
,
96 re_sift_context_t
*sctx
)
98 static reg_errcode_t
build_sifted_states (const re_match_context_t
*mctx
,
99 re_sift_context_t
*sctx
, int str_idx
,
100 re_node_set
*cur_dest
)
102 static reg_errcode_t
update_cur_sifted_state (const re_match_context_t
*mctx
,
103 re_sift_context_t
*sctx
,
105 re_node_set
*dest_nodes
)
107 static reg_errcode_t
add_epsilon_src_nodes (const re_dfa_t
*dfa
,
108 re_node_set
*dest_nodes
,
109 const re_node_set
*candidates
)
111 static reg_errcode_t
sub_epsilon_src_nodes (const re_dfa_t
*dfa
, int node
,
112 re_node_set
*dest_nodes
,
113 const re_node_set
*and_nodes
)
115 static int check_dst_limits (const re_match_context_t
*mctx
,
117 int dst_node
, int dst_idx
, int src_node
,
118 int src_idx
) internal_function
;
119 static int check_dst_limits_calc_pos_1 (const re_match_context_t
*mctx
,
120 int boundaries
, int subexp_idx
,
121 int from_node
, int bkref_idx
)
123 static int check_dst_limits_calc_pos (const re_match_context_t
*mctx
,
124 int limit
, int subexp_idx
,
125 int node
, int str_idx
,
126 int bkref_idx
) internal_function
;
127 static reg_errcode_t
check_subexp_limits (const re_dfa_t
*dfa
,
128 re_node_set
*dest_nodes
,
129 const re_node_set
*candidates
,
131 struct re_backref_cache_entry
*bkref_ents
,
132 int str_idx
) internal_function
;
133 static reg_errcode_t
sift_states_bkref (const re_match_context_t
*mctx
,
134 re_sift_context_t
*sctx
,
135 int str_idx
, const re_node_set
*candidates
)
137 static reg_errcode_t
clean_state_log_if_needed (re_match_context_t
*mctx
,
138 int next_state_log_idx
)
140 static reg_errcode_t
merge_state_array (const re_dfa_t
*dfa
,
142 re_dfastate_t
**src
, int num
)
144 static re_dfastate_t
*find_recover_state (reg_errcode_t
*err
,
145 re_match_context_t
*mctx
) internal_function
;
146 static re_dfastate_t
*transit_state (reg_errcode_t
*err
,
147 re_match_context_t
*mctx
,
148 re_dfastate_t
*state
) internal_function
;
149 static re_dfastate_t
*merge_state_with_log (reg_errcode_t
*err
,
150 re_match_context_t
*mctx
,
151 re_dfastate_t
*next_state
)
153 static reg_errcode_t
check_subexp_matching_top (re_match_context_t
*mctx
,
154 re_node_set
*cur_nodes
,
155 int str_idx
) internal_function
;
157 static re_dfastate_t
*transit_state_sb (reg_errcode_t
*err
,
158 re_match_context_t
*mctx
,
159 re_dfastate_t
*pstate
)
162 #ifdef RE_ENABLE_I18N
163 static reg_errcode_t
transit_state_mb (re_match_context_t
*mctx
,
164 re_dfastate_t
*pstate
)
166 #endif /* RE_ENABLE_I18N */
167 static reg_errcode_t
transit_state_bkref (re_match_context_t
*mctx
,
168 const re_node_set
*nodes
)
170 static reg_errcode_t
get_subexp (re_match_context_t
*mctx
,
171 int bkref_node
, int bkref_str_idx
)
173 static reg_errcode_t
get_subexp_sub (re_match_context_t
*mctx
,
174 const re_sub_match_top_t
*sub_top
,
175 re_sub_match_last_t
*sub_last
,
176 int bkref_node
, int bkref_str
)
178 static int find_subexp_node (const re_dfa_t
*dfa
, const re_node_set
*nodes
,
179 int subexp_idx
, int type
) internal_function
;
180 static reg_errcode_t
check_arrival (re_match_context_t
*mctx
,
181 state_array_t
*path
, int top_node
,
182 int top_str
, int last_node
, int last_str
,
183 int type
) internal_function
;
184 static reg_errcode_t
check_arrival_add_next_nodes (re_match_context_t
*mctx
,
186 re_node_set
*cur_nodes
,
187 re_node_set
*next_nodes
)
189 static reg_errcode_t
check_arrival_expand_ecl (const re_dfa_t
*dfa
,
190 re_node_set
*cur_nodes
,
191 int ex_subexp
, int type
)
193 static reg_errcode_t
check_arrival_expand_ecl_sub (const re_dfa_t
*dfa
,
194 re_node_set
*dst_nodes
,
195 int target
, int ex_subexp
,
196 int type
) internal_function
;
197 static reg_errcode_t
expand_bkref_cache (re_match_context_t
*mctx
,
198 re_node_set
*cur_nodes
, int cur_str
,
199 int subexp_num
, int type
)
201 static int build_trtable (const re_dfa_t
*dfa
,
202 re_dfastate_t
*state
) internal_function
;
203 #ifdef RE_ENABLE_I18N
204 static int check_node_accept_bytes (const re_dfa_t
*dfa
, int node_idx
,
205 const re_string_t
*input
, int idx
)
208 static unsigned int find_collation_sequence_value (const unsigned char *mbs
,
212 #endif /* RE_ENABLE_I18N */
213 static int group_nodes_into_DFAstates (const re_dfa_t
*dfa
,
214 const re_dfastate_t
*state
,
215 re_node_set
*states_node
,
216 bitset_t
*states_ch
) internal_function
;
217 static int check_node_accept (const re_match_context_t
*mctx
,
218 const re_token_t
*node
, int idx
)
220 static reg_errcode_t
extend_buffers (re_match_context_t
*mctx
)
223 /* Entry point for POSIX code. */
225 /* regexec searches for a given pattern, specified by PREG, in the
228 If NMATCH is zero or REG_NOSUB was set in the cflags argument to
229 `regcomp', we ignore PMATCH. Otherwise, we assume PMATCH has at
230 least NMATCH elements, and we set them to the offsets of the
231 corresponding matched substrings.
233 EFLAGS specifies `execution flags' which affect matching: if
234 REG_NOTBOL is set, then ^ does not match at the beginning of the
235 string; if REG_NOTEOL is set, then $ does not match at the end.
237 We return 0 if we find a match and REG_NOMATCH if not. */
240 regexec (preg
, string
, nmatch
, pmatch
, eflags
)
241 const regex_t
*__restrict preg
;
242 const char *__restrict string
;
249 re_dfa_t
*dfa
= (re_dfa_t
*) preg
->buffer
;
251 if (eflags
& ~(REG_NOTBOL
| REG_NOTEOL
| REG_STARTEND
))
254 if (eflags
& REG_STARTEND
)
256 start
= pmatch
[0].rm_so
;
257 length
= pmatch
[0].rm_eo
;
262 length
= strlen (string
);
265 __libc_lock_lock (dfa
->lock
);
267 err
= re_search_internal (preg
, string
, length
, start
, length
- start
,
268 length
, 0, NULL
, eflags
);
270 err
= re_search_internal (preg
, string
, length
, start
, length
- start
,
271 length
, nmatch
, pmatch
, eflags
);
272 __libc_lock_unlock (dfa
->lock
);
273 return err
!= REG_NOERROR
;
277 # include <shlib-compat.h>
278 versioned_symbol (libc
, __regexec
, regexec
, GLIBC_2_3_4
);
280 # if SHLIB_COMPAT (libc, GLIBC_2_0, GLIBC_2_3_4)
281 __typeof__ (__regexec
) __compat_regexec
;
284 attribute_compat_text_section
285 __compat_regexec (const regex_t
*__restrict preg
,
286 const char *__restrict string
, size_t nmatch
,
287 regmatch_t pmatch
[], int eflags
)
289 return regexec (preg
, string
, nmatch
, pmatch
,
290 eflags
& (REG_NOTBOL
| REG_NOTEOL
));
292 compat_symbol (libc
, __compat_regexec
, regexec
, GLIBC_2_0
);
296 /* Entry points for GNU code. */
298 /* re_match, re_search, re_match_2, re_search_2
300 The former two functions operate on STRING with length LENGTH,
301 while the later two operate on concatenation of STRING1 and STRING2
302 with lengths LENGTH1 and LENGTH2, respectively.
304 re_match() matches the compiled pattern in BUFP against the string,
305 starting at index START.
307 re_search() first tries matching at index START, then it tries to match
308 starting from index START + 1, and so on. The last start position tried
309 is START + RANGE. (Thus RANGE = 0 forces re_search to operate the same
312 The parameter STOP of re_{match,search}_2 specifies that no match exceeding
313 the first STOP characters of the concatenation of the strings should be
316 If REGS is not NULL, and BUFP->no_sub is not set, the offsets of the match
317 and all groups is stroed in REGS. (For the "_2" variants, the offsets are
318 computed relative to the concatenation, not relative to the individual
321 On success, re_match* functions return the length of the match, re_search*
322 return the position of the start of the match. Return value -1 means no
323 match was found and -2 indicates an internal error. */
326 re_match (bufp
, string
, length
, start
, regs
)
327 struct re_pattern_buffer
*bufp
;
330 struct re_registers
*regs
;
332 return re_search_stub (bufp
, string
, length
, start
, 0, length
, regs
, 1);
335 weak_alias (__re_match
, re_match
)
339 re_search (bufp
, string
, length
, start
, range
, regs
)
340 struct re_pattern_buffer
*bufp
;
342 int length
, start
, range
;
343 struct re_registers
*regs
;
345 return re_search_stub (bufp
, string
, length
, start
, range
, length
, regs
, 0);
348 weak_alias (__re_search
, re_search
)
352 re_match_2 (bufp
, string1
, length1
, string2
, length2
, start
, regs
, stop
)
353 struct re_pattern_buffer
*bufp
;
354 const char *string1
, *string2
;
355 int length1
, length2
, start
, stop
;
356 struct re_registers
*regs
;
358 return re_search_2_stub (bufp
, string1
, length1
, string2
, length2
,
359 start
, 0, regs
, stop
, 1);
362 weak_alias (__re_match_2
, re_match_2
)
366 re_search_2 (bufp
, string1
, length1
, string2
, length2
, start
, range
, regs
, stop
)
367 struct re_pattern_buffer
*bufp
;
368 const char *string1
, *string2
;
369 int length1
, length2
, start
, range
, stop
;
370 struct re_registers
*regs
;
372 return re_search_2_stub (bufp
, string1
, length1
, string2
, length2
,
373 start
, range
, regs
, stop
, 0);
376 weak_alias (__re_search_2
, re_search_2
)
380 re_search_2_stub (bufp
, string1
, length1
, string2
, length2
, start
, range
, regs
,
382 struct re_pattern_buffer
*bufp
;
383 const char *string1
, *string2
;
384 int length1
, length2
, start
, range
, stop
, ret_len
;
385 struct re_registers
*regs
;
389 int len
= length1
+ length2
;
392 if (BE (length1
< 0 || length2
< 0 || stop
< 0, 0))
395 /* Concatenate the strings. */
399 char *s
= re_malloc (char, len
);
401 if (BE (s
== NULL
, 0))
404 memcpy (__mempcpy (s
, string1
, length1
), string2
, length2
);
406 memcpy (s
, string1
, length1
);
407 memcpy (s
+ length1
, string2
, length2
);
417 rval
= re_search_stub (bufp
, str
, len
, start
, range
, stop
, regs
,
420 re_free ((char *) str
);
424 /* The parameters have the same meaning as those of re_search.
425 Additional parameters:
426 If RET_LEN is nonzero the length of the match is returned (re_match style);
427 otherwise the position of the match is returned. */
430 re_search_stub (bufp
, string
, length
, start
, range
, stop
, regs
, ret_len
)
431 struct re_pattern_buffer
*bufp
;
433 int length
, start
, range
, stop
, ret_len
;
434 struct re_registers
*regs
;
436 reg_errcode_t result
;
440 re_dfa_t
*dfa
= (re_dfa_t
*) bufp
->buffer
;
442 /* Check for out-of-range. */
443 if (BE (start
< 0 || start
> length
, 0))
445 if (BE (start
+ range
> length
, 0))
446 range
= length
- start
;
447 else if (BE (start
+ range
< 0, 0))
450 __libc_lock_lock (dfa
->lock
);
452 eflags
|= (bufp
->not_bol
) ? REG_NOTBOL
: 0;
453 eflags
|= (bufp
->not_eol
) ? REG_NOTEOL
: 0;
455 /* Compile fastmap if we haven't yet. */
456 if (range
> 0 && bufp
->fastmap
!= NULL
&& !bufp
->fastmap_accurate
)
457 re_compile_fastmap (bufp
);
459 if (BE (bufp
->no_sub
, 0))
462 /* We need at least 1 register. */
465 else if (BE (bufp
->regs_allocated
== REGS_FIXED
&&
466 regs
->num_regs
< bufp
->re_nsub
+ 1, 0))
468 nregs
= regs
->num_regs
;
469 if (BE (nregs
< 1, 0))
471 /* Nothing can be copied to regs. */
477 nregs
= bufp
->re_nsub
+ 1;
478 pmatch
= re_malloc (regmatch_t
, nregs
);
479 if (BE (pmatch
== NULL
, 0))
485 result
= re_search_internal (bufp
, string
, length
, start
, range
, stop
,
486 nregs
, pmatch
, eflags
);
490 /* I hope we needn't fill ther regs with -1's when no match was found. */
491 if (result
!= REG_NOERROR
)
493 else if (regs
!= NULL
)
495 /* If caller wants register contents data back, copy them. */
496 bufp
->regs_allocated
= re_copy_regs (regs
, pmatch
, nregs
,
497 bufp
->regs_allocated
);
498 if (BE (bufp
->regs_allocated
== REGS_UNALLOCATED
, 0))
502 if (BE (rval
== 0, 1))
506 assert (pmatch
[0].rm_so
== start
);
507 rval
= pmatch
[0].rm_eo
- start
;
510 rval
= pmatch
[0].rm_so
;
514 __libc_lock_unlock (dfa
->lock
);
519 re_copy_regs (regs
, pmatch
, nregs
, regs_allocated
)
520 struct re_registers
*regs
;
522 int nregs
, regs_allocated
;
524 int rval
= REGS_REALLOCATE
;
526 int need_regs
= nregs
+ 1;
527 /* We need one extra element beyond `num_regs' for the `-1' marker GNU code
530 /* Have the register data arrays been allocated? */
531 if (regs_allocated
== REGS_UNALLOCATED
)
532 { /* No. So allocate them with malloc. */
533 regs
->start
= re_malloc (regoff_t
, need_regs
);
534 regs
->end
= re_malloc (regoff_t
, need_regs
);
535 if (BE (regs
->start
== NULL
, 0) || BE (regs
->end
== NULL
, 0))
536 return REGS_UNALLOCATED
;
537 regs
->num_regs
= need_regs
;
539 else if (regs_allocated
== REGS_REALLOCATE
)
540 { /* Yes. If we need more elements than were already
541 allocated, reallocate them. If we need fewer, just
543 if (BE (need_regs
> regs
->num_regs
, 0))
545 regoff_t
*new_start
= re_realloc (regs
->start
, regoff_t
, need_regs
);
546 regoff_t
*new_end
= re_realloc (regs
->end
, regoff_t
, need_regs
);
547 if (BE (new_start
== NULL
, 0) || BE (new_end
== NULL
, 0))
548 return REGS_UNALLOCATED
;
549 regs
->start
= new_start
;
551 regs
->num_regs
= need_regs
;
556 assert (regs_allocated
== REGS_FIXED
);
557 /* This function may not be called with REGS_FIXED and nregs too big. */
558 assert (regs
->num_regs
>= nregs
);
563 for (i
= 0; i
< nregs
; ++i
)
565 regs
->start
[i
] = pmatch
[i
].rm_so
;
566 regs
->end
[i
] = pmatch
[i
].rm_eo
;
568 for ( ; i
< regs
->num_regs
; ++i
)
569 regs
->start
[i
] = regs
->end
[i
] = -1;
574 /* Set REGS to hold NUM_REGS registers, storing them in STARTS and
575 ENDS. Subsequent matches using PATTERN_BUFFER and REGS will use
576 this memory for recording register information. STARTS and ENDS
577 must be allocated using the malloc library routine, and must each
578 be at least NUM_REGS * sizeof (regoff_t) bytes long.
580 If NUM_REGS == 0, then subsequent matches should allocate their own
583 Unless this function is called, the first search or match using
584 PATTERN_BUFFER will allocate its own register data, without
585 freeing the old data. */
588 re_set_registers (bufp
, regs
, num_regs
, starts
, ends
)
589 struct re_pattern_buffer
*bufp
;
590 struct re_registers
*regs
;
592 regoff_t
*starts
, *ends
;
596 bufp
->regs_allocated
= REGS_REALLOCATE
;
597 regs
->num_regs
= num_regs
;
598 regs
->start
= starts
;
603 bufp
->regs_allocated
= REGS_UNALLOCATED
;
605 regs
->start
= regs
->end
= (regoff_t
*) 0;
609 weak_alias (__re_set_registers
, re_set_registers
)
612 /* Entry points compatible with 4.2 BSD regex library. We don't define
613 them unless specifically requested. */
615 #if defined _REGEX_RE_COMP || defined _LIBC
623 return 0 == regexec (&re_comp_buf
, s
, 0, NULL
, 0);
625 #endif /* _REGEX_RE_COMP */
627 /* Internal entry point. */
629 /* Searches for a compiled pattern PREG in the string STRING, whose
630 length is LENGTH. NMATCH, PMATCH, and EFLAGS have the same
631 mingings with regexec. START, and RANGE have the same meanings
633 Return REG_NOERROR if we find a match, and REG_NOMATCH if not,
634 otherwise return the error code.
635 Note: We assume front end functions already check ranges.
636 (START + RANGE >= 0 && START + RANGE <= LENGTH) */
639 re_search_internal (preg
, string
, length
, start
, range
, stop
, nmatch
, pmatch
,
643 int length
, start
, range
, stop
, eflags
;
648 const re_dfa_t
*dfa
= (const re_dfa_t
*) preg
->buffer
;
649 int left_lim
, right_lim
, incr
;
650 int fl_longest_match
, match_first
, match_kind
, match_last
= -1;
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 && range
&& !preg
->can_be_null
) ? preg
->fastmap
: NULL
;
660 RE_TRANSLATE_TYPE t
= preg
->translate
;
662 #if !(defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L))
663 memset (&mctx
, '\0', sizeof (re_match_context_t
));
667 extra_nmatch
= (nmatch
> preg
->re_nsub
) ? nmatch
- (preg
->re_nsub
+ 1) : 0;
668 nmatch
-= extra_nmatch
;
670 /* Check if the DFA haven't been compiled. */
671 if (BE (preg
->used
== 0 || dfa
->init_state
== NULL
672 || dfa
->init_state_word
== NULL
|| dfa
->init_state_nl
== NULL
673 || dfa
->init_state_begbuf
== NULL
, 0))
677 /* We assume front-end functions already check them. */
678 assert (start
+ range
>= 0 && start
+ range
<= length
);
681 /* If initial states with non-begbuf contexts have no elements,
682 the regex must be anchored. If preg->newline_anchor is set,
683 we'll never use init_state_nl, so do not check it. */
684 if (dfa
->init_state
->nodes
.nelem
== 0
685 && dfa
->init_state_word
->nodes
.nelem
== 0
686 && (dfa
->init_state_nl
->nodes
.nelem
== 0
687 || !preg
->newline_anchor
))
689 if (start
!= 0 && start
+ range
!= 0)
694 /* We must check the longest matching, if nmatch > 0. */
695 fl_longest_match
= (nmatch
!= 0 || dfa
->nbackref
);
697 err
= re_string_allocate (&mctx
.input
, string
, length
, dfa
->nodes_len
+ 1,
698 preg
->translate
, preg
->syntax
& RE_ICASE
, dfa
);
699 if (BE (err
!= REG_NOERROR
, 0))
701 mctx
.input
.stop
= stop
;
702 mctx
.input
.raw_stop
= stop
;
703 mctx
.input
.newline_anchor
= preg
->newline_anchor
;
705 err
= match_ctx_init (&mctx
, eflags
, dfa
->nbackref
* 2);
706 if (BE (err
!= REG_NOERROR
, 0))
709 /* We will log all the DFA states through which the dfa pass,
710 if nmatch > 1, or this dfa has "multibyte node", which is a
711 back-reference or a node which can accept multibyte character or
712 multi character collating element. */
713 if (nmatch
> 1 || dfa
->has_mb_node
)
715 mctx
.state_log
= re_malloc (re_dfastate_t
*, mctx
.input
.bufs_len
+ 1);
716 if (BE (mctx
.state_log
== NULL
, 0))
723 mctx
.state_log
= NULL
;
726 mctx
.input
.tip_context
= (eflags
& REG_NOTBOL
) ? CONTEXT_BEGBUF
727 : CONTEXT_NEWLINE
| CONTEXT_BEGBUF
;
729 /* Check incrementally whether of not the input string match. */
730 incr
= (range
< 0) ? -1 : 1;
731 left_lim
= (range
< 0) ? start
+ range
: start
;
732 right_lim
= (range
< 0) ? start
: start
+ range
;
733 sb
= dfa
->mb_cur_max
== 1;
736 ? ((sb
|| !(preg
->syntax
& RE_ICASE
|| t
) ? 4 : 0)
737 | (range
>= 0 ? 2 : 0)
738 | (t
!= NULL
? 1 : 0))
741 for (;; match_first
+= incr
)
744 if (match_first
< left_lim
|| right_lim
< match_first
)
747 /* Advance as rapidly as possible through the string, until we
748 find a plausible place to start matching. This may be done
749 with varying efficiency, so there are various possibilities:
750 only the most common of them are specialized, in order to
751 save on code size. We use a switch statement for speed. */
759 /* Fastmap with single-byte translation, match forward. */
760 while (BE (match_first
< right_lim
, 1)
761 && !fastmap
[t
[(unsigned char) string
[match_first
]]])
763 goto forward_match_found_start_or_reached_end
;
766 /* Fastmap without translation, match forward. */
767 while (BE (match_first
< right_lim
, 1)
768 && !fastmap
[(unsigned char) string
[match_first
]])
771 forward_match_found_start_or_reached_end
:
772 if (BE (match_first
== right_lim
, 0))
774 ch
= match_first
>= length
775 ? 0 : (unsigned char) string
[match_first
];
776 if (!fastmap
[t
? t
[ch
] : ch
])
783 /* Fastmap without multi-byte translation, match backwards. */
784 while (match_first
>= left_lim
)
786 ch
= match_first
>= length
787 ? 0 : (unsigned char) string
[match_first
];
788 if (fastmap
[t
? t
[ch
] : ch
])
792 if (match_first
< left_lim
)
797 /* In this case, we can't determine easily the current byte,
798 since it might be a component byte of a multibyte
799 character. Then we use the constructed buffer instead. */
802 /* If MATCH_FIRST is out of the valid range, reconstruct the
804 unsigned int offset
= match_first
- mctx
.input
.raw_mbs_idx
;
805 if (BE (offset
>= (unsigned int) mctx
.input
.valid_raw_len
, 0))
807 err
= re_string_reconstruct (&mctx
.input
, match_first
,
809 if (BE (err
!= REG_NOERROR
, 0))
812 offset
= match_first
- mctx
.input
.raw_mbs_idx
;
814 /* If MATCH_FIRST is out of the buffer, leave it as '\0'.
815 Note that MATCH_FIRST must not be smaller than 0. */
816 ch
= (match_first
>= length
817 ? 0 : re_string_byte_at (&mctx
.input
, offset
));
821 if (match_first
< left_lim
|| match_first
> right_lim
)
830 /* Reconstruct the buffers so that the matcher can assume that
831 the matching starts from the beginning of the buffer. */
832 err
= re_string_reconstruct (&mctx
.input
, match_first
, eflags
);
833 if (BE (err
!= REG_NOERROR
, 0))
836 #ifdef RE_ENABLE_I18N
837 /* Don't consider this char as a possible match start if it part,
838 yet isn't the head, of a multibyte character. */
839 if (!sb
&& !re_string_first_byte (&mctx
.input
, 0))
843 /* It seems to be appropriate one, then use the matcher. */
844 /* We assume that the matching starts from 0. */
845 mctx
.state_log_top
= mctx
.nbkref_ents
= mctx
.max_mb_elem_len
= 0;
846 match_last
= check_matching (&mctx
, fl_longest_match
,
847 range
>= 0 ? &match_first
: NULL
);
848 if (match_last
!= -1)
850 if (BE (match_last
== -2, 0))
857 mctx
.match_last
= match_last
;
858 if ((!preg
->no_sub
&& nmatch
> 1) || dfa
->nbackref
)
860 re_dfastate_t
*pstate
= mctx
.state_log
[match_last
];
861 mctx
.last_node
= check_halt_state_context (&mctx
, pstate
,
864 if ((!preg
->no_sub
&& nmatch
> 1 && dfa
->has_plural_match
)
867 err
= prune_impossible_nodes (&mctx
);
868 if (err
== REG_NOERROR
)
870 if (BE (err
!= REG_NOMATCH
, 0))
875 break; /* We found a match. */
879 match_ctx_clean (&mctx
);
883 assert (match_last
!= -1);
884 assert (err
== REG_NOERROR
);
887 /* Set pmatch[] if we need. */
892 /* Initialize registers. */
893 for (reg_idx
= 1; reg_idx
< nmatch
; ++reg_idx
)
894 pmatch
[reg_idx
].rm_so
= pmatch
[reg_idx
].rm_eo
= -1;
896 /* Set the points where matching start/end. */
898 pmatch
[0].rm_eo
= mctx
.match_last
;
900 if (!preg
->no_sub
&& nmatch
> 1)
902 err
= set_regs (preg
, &mctx
, nmatch
, pmatch
,
903 dfa
->has_plural_match
&& dfa
->nbackref
> 0);
904 if (BE (err
!= REG_NOERROR
, 0))
908 /* At last, add the offset to the each registers, since we slided
909 the buffers so that we could assume that the matching starts
911 for (reg_idx
= 0; reg_idx
< nmatch
; ++reg_idx
)
912 if (pmatch
[reg_idx
].rm_so
!= -1)
914 #ifdef RE_ENABLE_I18N
915 if (BE (mctx
.input
.offsets_needed
!= 0, 0))
917 pmatch
[reg_idx
].rm_so
=
918 (pmatch
[reg_idx
].rm_so
== mctx
.input
.valid_len
919 ? mctx
.input
.valid_raw_len
920 : mctx
.input
.offsets
[pmatch
[reg_idx
].rm_so
]);
921 pmatch
[reg_idx
].rm_eo
=
922 (pmatch
[reg_idx
].rm_eo
== mctx
.input
.valid_len
923 ? mctx
.input
.valid_raw_len
924 : mctx
.input
.offsets
[pmatch
[reg_idx
].rm_eo
]);
927 assert (mctx
.input
.offsets_needed
== 0);
929 pmatch
[reg_idx
].rm_so
+= match_first
;
930 pmatch
[reg_idx
].rm_eo
+= match_first
;
932 for (reg_idx
= 0; reg_idx
< extra_nmatch
; ++reg_idx
)
934 pmatch
[nmatch
+ reg_idx
].rm_so
= -1;
935 pmatch
[nmatch
+ reg_idx
].rm_eo
= -1;
939 for (reg_idx
= 0; reg_idx
+ 1 < nmatch
; reg_idx
++)
940 if (dfa
->subexp_map
[reg_idx
] != reg_idx
)
942 pmatch
[reg_idx
+ 1].rm_so
943 = pmatch
[dfa
->subexp_map
[reg_idx
] + 1].rm_so
;
944 pmatch
[reg_idx
+ 1].rm_eo
945 = pmatch
[dfa
->subexp_map
[reg_idx
] + 1].rm_eo
;
950 re_free (mctx
.state_log
);
952 match_ctx_free (&mctx
);
953 re_string_destruct (&mctx
.input
);
958 prune_impossible_nodes (mctx
)
959 re_match_context_t
*mctx
;
961 const re_dfa_t
*const dfa
= mctx
->dfa
;
962 int halt_node
, match_last
;
964 re_dfastate_t
**sifted_states
;
965 re_dfastate_t
**lim_states
= NULL
;
966 re_sift_context_t sctx
;
968 assert (mctx
->state_log
!= NULL
);
970 match_last
= mctx
->match_last
;
971 halt_node
= mctx
->last_node
;
972 sifted_states
= re_malloc (re_dfastate_t
*, match_last
+ 1);
973 if (BE (sifted_states
== NULL
, 0))
980 lim_states
= re_malloc (re_dfastate_t
*, match_last
+ 1);
981 if (BE (lim_states
== NULL
, 0))
988 memset (lim_states
, '\0',
989 sizeof (re_dfastate_t
*) * (match_last
+ 1));
990 sift_ctx_init (&sctx
, sifted_states
, lim_states
, halt_node
,
992 ret
= sift_states_backward (mctx
, &sctx
);
993 re_node_set_free (&sctx
.limits
);
994 if (BE (ret
!= REG_NOERROR
, 0))
996 if (sifted_states
[0] != NULL
|| lim_states
[0] != NULL
)
1006 } while (mctx
->state_log
[match_last
] == NULL
1007 || !mctx
->state_log
[match_last
]->halt
);
1008 halt_node
= check_halt_state_context (mctx
,
1009 mctx
->state_log
[match_last
],
1012 ret
= merge_state_array (dfa
, sifted_states
, lim_states
,
1014 re_free (lim_states
);
1016 if (BE (ret
!= REG_NOERROR
, 0))
1021 sift_ctx_init (&sctx
, sifted_states
, lim_states
, halt_node
, match_last
);
1022 ret
= sift_states_backward (mctx
, &sctx
);
1023 re_node_set_free (&sctx
.limits
);
1024 if (BE (ret
!= REG_NOERROR
, 0))
1027 re_free (mctx
->state_log
);
1028 mctx
->state_log
= sifted_states
;
1029 sifted_states
= NULL
;
1030 mctx
->last_node
= halt_node
;
1031 mctx
->match_last
= match_last
;
1034 re_free (sifted_states
);
1035 re_free (lim_states
);
1039 /* Acquire an initial state and return it.
1040 We must select appropriate initial state depending on the context,
1041 since initial states may have constraints like "\<", "^", etc.. */
1043 static inline re_dfastate_t
*
1044 acquire_init_state_context (err
, mctx
, idx
)
1046 const re_match_context_t
*mctx
;
1049 const re_dfa_t
*const dfa
= mctx
->dfa
;
1050 if (dfa
->init_state
->has_constraint
)
1052 unsigned int context
;
1053 context
= re_string_context_at (&mctx
->input
, idx
- 1, mctx
->eflags
);
1054 if (IS_WORD_CONTEXT (context
))
1055 return dfa
->init_state_word
;
1056 else if (IS_ORDINARY_CONTEXT (context
))
1057 return dfa
->init_state
;
1058 else if (IS_BEGBUF_CONTEXT (context
) && IS_NEWLINE_CONTEXT (context
))
1059 return dfa
->init_state_begbuf
;
1060 else if (IS_NEWLINE_CONTEXT (context
))
1061 return dfa
->init_state_nl
;
1062 else if (IS_BEGBUF_CONTEXT (context
))
1064 /* It is relatively rare case, then calculate on demand. */
1065 return re_acquire_state_context (err
, dfa
,
1066 dfa
->init_state
->entrance_nodes
,
1070 /* Must not happen? */
1071 return dfa
->init_state
;
1074 return dfa
->init_state
;
1077 /* Check whether the regular expression match input string INPUT or not,
1078 and return the index where the matching end, return -1 if not match,
1079 or return -2 in case of an error.
1080 FL_LONGEST_MATCH means we want the POSIX longest matching.
1081 If P_MATCH_FIRST is not NULL, and the match fails, it is set to the
1082 next place where we may want to try matching.
1083 Note that the matcher assume that the maching starts from the current
1084 index of the buffer. */
1087 check_matching (mctx
, fl_longest_match
, p_match_first
)
1088 re_match_context_t
*mctx
;
1089 int fl_longest_match
;
1092 const re_dfa_t
*const dfa
= mctx
->dfa
;
1095 int match_last
= -1;
1096 int cur_str_idx
= re_string_cur_idx (&mctx
->input
);
1097 re_dfastate_t
*cur_state
;
1098 int at_init_state
= p_match_first
!= NULL
;
1099 int next_start_idx
= cur_str_idx
;
1102 cur_state
= acquire_init_state_context (&err
, mctx
, cur_str_idx
);
1103 /* An initial state must not be NULL (invalid). */
1104 if (BE (cur_state
== NULL
, 0))
1106 assert (err
== REG_ESPACE
);
1110 if (mctx
->state_log
!= NULL
)
1112 mctx
->state_log
[cur_str_idx
] = cur_state
;
1114 /* Check OP_OPEN_SUBEXP in the initial state in case that we use them
1115 later. E.g. Processing back references. */
1116 if (BE (dfa
->nbackref
, 0))
1119 err
= check_subexp_matching_top (mctx
, &cur_state
->nodes
, 0);
1120 if (BE (err
!= REG_NOERROR
, 0))
1123 if (cur_state
->has_backref
)
1125 err
= transit_state_bkref (mctx
, &cur_state
->nodes
);
1126 if (BE (err
!= REG_NOERROR
, 0))
1132 /* If the RE accepts NULL string. */
1133 if (BE (cur_state
->halt
, 0))
1135 if (!cur_state
->has_constraint
1136 || check_halt_state_context (mctx
, cur_state
, cur_str_idx
))
1138 if (!fl_longest_match
)
1142 match_last
= cur_str_idx
;
1148 while (!re_string_eoi (&mctx
->input
))
1150 re_dfastate_t
*old_state
= cur_state
;
1151 int next_char_idx
= re_string_cur_idx (&mctx
->input
) + 1;
1153 if (BE (next_char_idx
>= mctx
->input
.bufs_len
, 0)
1154 || (BE (next_char_idx
>= mctx
->input
.valid_len
, 0)
1155 && mctx
->input
.valid_len
< mctx
->input
.len
))
1157 err
= extend_buffers (mctx
);
1158 if (BE (err
!= REG_NOERROR
, 0))
1160 assert (err
== REG_ESPACE
);
1165 cur_state
= transit_state (&err
, mctx
, cur_state
);
1166 if (mctx
->state_log
!= NULL
)
1167 cur_state
= merge_state_with_log (&err
, mctx
, cur_state
);
1169 if (cur_state
== NULL
)
1171 /* Reached the invalid state or an error. Try to recover a valid
1172 state using the state log, if available and if we have not
1173 already found a valid (even if not the longest) match. */
1174 if (BE (err
!= REG_NOERROR
, 0))
1177 if (mctx
->state_log
== NULL
1178 || (match
&& !fl_longest_match
)
1179 || (cur_state
= find_recover_state (&err
, mctx
)) == NULL
)
1183 if (BE (at_init_state
, 0))
1185 if (old_state
== cur_state
)
1186 next_start_idx
= next_char_idx
;
1191 if (cur_state
->halt
)
1193 /* Reached a halt state.
1194 Check the halt state can satisfy the current context. */
1195 if (!cur_state
->has_constraint
1196 || check_halt_state_context (mctx
, cur_state
,
1197 re_string_cur_idx (&mctx
->input
)))
1199 /* We found an appropriate halt state. */
1200 match_last
= re_string_cur_idx (&mctx
->input
);
1203 /* We found a match, do not modify match_first below. */
1204 p_match_first
= NULL
;
1205 if (!fl_longest_match
)
1212 *p_match_first
+= next_start_idx
;
1217 /* Check NODE match the current context. */
1219 static int check_halt_node_context (dfa
, node
, context
)
1220 const re_dfa_t
*dfa
;
1222 unsigned int context
;
1224 re_token_type_t type
= dfa
->nodes
[node
].type
;
1225 unsigned int constraint
= dfa
->nodes
[node
].constraint
;
1226 if (type
!= END_OF_RE
)
1230 if (NOT_SATISFY_NEXT_CONSTRAINT (constraint
, context
))
1235 /* Check the halt state STATE match the current context.
1236 Return 0 if not match, if the node, STATE has, is a halt node and
1237 match the context, return the node. */
1240 check_halt_state_context (mctx
, state
, idx
)
1241 const re_match_context_t
*mctx
;
1242 const re_dfastate_t
*state
;
1246 unsigned int context
;
1248 assert (state
->halt
);
1250 context
= re_string_context_at (&mctx
->input
, idx
, mctx
->eflags
);
1251 for (i
= 0; i
< state
->nodes
.nelem
; ++i
)
1252 if (check_halt_node_context (mctx
->dfa
, state
->nodes
.elems
[i
], context
))
1253 return state
->nodes
.elems
[i
];
1257 /* Compute the next node to which "NFA" transit from NODE("NFA" is a NFA
1258 corresponding to the DFA).
1259 Return the destination node, and update EPS_VIA_NODES, return -1 in case
1263 proceed_next_node (mctx
, nregs
, regs
, pidx
, node
, eps_via_nodes
, fs
)
1264 const re_match_context_t
*mctx
;
1266 int nregs
, *pidx
, node
;
1267 re_node_set
*eps_via_nodes
;
1268 struct re_fail_stack_t
*fs
;
1270 const re_dfa_t
*const dfa
= mctx
->dfa
;
1272 if (IS_EPSILON_NODE (dfa
->nodes
[node
].type
))
1274 re_node_set
*cur_nodes
= &mctx
->state_log
[*pidx
]->nodes
;
1275 re_node_set
*edests
= &dfa
->edests
[node
];
1277 err
= re_node_set_insert (eps_via_nodes
, node
);
1278 if (BE (err
< 0, 0))
1280 /* Pick up a valid destination, or return -1 if none is found. */
1281 for (dest_node
= -1, i
= 0; i
< edests
->nelem
; ++i
)
1283 int candidate
= edests
->elems
[i
];
1284 if (!re_node_set_contains (cur_nodes
, candidate
))
1286 if (dest_node
== -1)
1287 dest_node
= candidate
;
1291 /* In order to avoid infinite loop like "(a*)*", return the second
1292 epsilon-transition if the first was already considered. */
1293 if (re_node_set_contains (eps_via_nodes
, dest_node
))
1296 /* Otherwise, push the second epsilon-transition on the fail stack. */
1298 && push_fail_stack (fs
, *pidx
, candidate
, nregs
, regs
,
1302 /* We know we are going to exit. */
1311 re_token_type_t type
= dfa
->nodes
[node
].type
;
1313 #ifdef RE_ENABLE_I18N
1314 if (dfa
->nodes
[node
].accept_mb
)
1315 naccepted
= check_node_accept_bytes (dfa
, node
, &mctx
->input
, *pidx
);
1317 #endif /* RE_ENABLE_I18N */
1318 if (type
== OP_BACK_REF
)
1320 int subexp_idx
= dfa
->nodes
[node
].opr
.idx
+ 1;
1321 naccepted
= regs
[subexp_idx
].rm_eo
- regs
[subexp_idx
].rm_so
;
1324 if (regs
[subexp_idx
].rm_so
== -1 || regs
[subexp_idx
].rm_eo
== -1)
1328 char *buf
= (char *) re_string_get_buffer (&mctx
->input
);
1329 if (memcmp (buf
+ regs
[subexp_idx
].rm_so
, buf
+ *pidx
,
1338 err
= re_node_set_insert (eps_via_nodes
, node
);
1339 if (BE (err
< 0, 0))
1341 dest_node
= dfa
->edests
[node
].elems
[0];
1342 if (re_node_set_contains (&mctx
->state_log
[*pidx
]->nodes
,
1349 || check_node_accept (mctx
, dfa
->nodes
+ node
, *pidx
))
1351 int dest_node
= dfa
->nexts
[node
];
1352 *pidx
= (naccepted
== 0) ? *pidx
+ 1 : *pidx
+ naccepted
;
1353 if (fs
&& (*pidx
> mctx
->match_last
|| mctx
->state_log
[*pidx
] == NULL
1354 || !re_node_set_contains (&mctx
->state_log
[*pidx
]->nodes
,
1357 re_node_set_empty (eps_via_nodes
);
1364 static reg_errcode_t
1365 push_fail_stack (fs
, str_idx
, dest_node
, nregs
, regs
, eps_via_nodes
)
1366 struct re_fail_stack_t
*fs
;
1367 int str_idx
, dest_node
, nregs
;
1369 re_node_set
*eps_via_nodes
;
1372 int num
= fs
->num
++;
1373 if (fs
->num
== fs
->alloc
)
1375 struct re_fail_stack_ent_t
*new_array
;
1376 new_array
= realloc (fs
->stack
, (sizeof (struct re_fail_stack_ent_t
)
1378 if (new_array
== NULL
)
1381 fs
->stack
= new_array
;
1383 fs
->stack
[num
].idx
= str_idx
;
1384 fs
->stack
[num
].node
= dest_node
;
1385 fs
->stack
[num
].regs
= re_malloc (regmatch_t
, nregs
);
1386 if (fs
->stack
[num
].regs
== NULL
)
1388 memcpy (fs
->stack
[num
].regs
, regs
, sizeof (regmatch_t
) * nregs
);
1389 err
= re_node_set_init_copy (&fs
->stack
[num
].eps_via_nodes
, eps_via_nodes
);
1394 pop_fail_stack (fs
, pidx
, nregs
, regs
, eps_via_nodes
)
1395 struct re_fail_stack_t
*fs
;
1398 re_node_set
*eps_via_nodes
;
1400 int num
= --fs
->num
;
1402 *pidx
= fs
->stack
[num
].idx
;
1403 memcpy (regs
, fs
->stack
[num
].regs
, sizeof (regmatch_t
) * nregs
);
1404 re_node_set_free (eps_via_nodes
);
1405 re_free (fs
->stack
[num
].regs
);
1406 *eps_via_nodes
= fs
->stack
[num
].eps_via_nodes
;
1407 return fs
->stack
[num
].node
;
1410 /* Set the positions where the subexpressions are starts/ends to registers
1412 Note: We assume that pmatch[0] is already set, and
1413 pmatch[i].rm_so == pmatch[i].rm_eo == -1 for 0 < i < nmatch. */
1415 static reg_errcode_t
1416 set_regs (preg
, mctx
, nmatch
, pmatch
, fl_backtrack
)
1417 const regex_t
*preg
;
1418 const re_match_context_t
*mctx
;
1423 const re_dfa_t
*dfa
= (const re_dfa_t
*) preg
->buffer
;
1425 re_node_set eps_via_nodes
;
1426 struct re_fail_stack_t
*fs
;
1427 struct re_fail_stack_t fs_body
= { 0, 2, NULL
};
1428 regmatch_t
*prev_idx_match
;
1429 int prev_idx_match_malloced
= 0;
1432 assert (nmatch
> 1);
1433 assert (mctx
->state_log
!= NULL
);
1438 fs
->stack
= re_malloc (struct re_fail_stack_ent_t
, fs
->alloc
);
1439 if (fs
->stack
== NULL
)
1445 cur_node
= dfa
->init_node
;
1446 re_node_set_init_empty (&eps_via_nodes
);
1448 if (__libc_use_alloca (nmatch
* sizeof (regmatch_t
)))
1449 prev_idx_match
= (regmatch_t
*) alloca (nmatch
* sizeof (regmatch_t
));
1452 prev_idx_match
= re_malloc (regmatch_t
, nmatch
);
1453 if (prev_idx_match
== NULL
)
1455 free_fail_stack_return (fs
);
1458 prev_idx_match_malloced
= 1;
1460 memcpy (prev_idx_match
, pmatch
, sizeof (regmatch_t
) * nmatch
);
1462 for (idx
= pmatch
[0].rm_so
; idx
<= pmatch
[0].rm_eo
;)
1464 update_regs (dfa
, pmatch
, prev_idx_match
, cur_node
, idx
, nmatch
);
1466 if (idx
== pmatch
[0].rm_eo
&& cur_node
== mctx
->last_node
)
1471 for (reg_idx
= 0; reg_idx
< nmatch
; ++reg_idx
)
1472 if (pmatch
[reg_idx
].rm_so
> -1 && pmatch
[reg_idx
].rm_eo
== -1)
1474 if (reg_idx
== nmatch
)
1476 re_node_set_free (&eps_via_nodes
);
1477 if (prev_idx_match_malloced
)
1478 re_free (prev_idx_match
);
1479 return free_fail_stack_return (fs
);
1481 cur_node
= pop_fail_stack (fs
, &idx
, nmatch
, pmatch
,
1486 re_node_set_free (&eps_via_nodes
);
1487 if (prev_idx_match_malloced
)
1488 re_free (prev_idx_match
);
1493 /* Proceed to next node. */
1494 cur_node
= proceed_next_node (mctx
, nmatch
, pmatch
, &idx
, cur_node
,
1495 &eps_via_nodes
, fs
);
1497 if (BE (cur_node
< 0, 0))
1499 if (BE (cur_node
== -2, 0))
1501 re_node_set_free (&eps_via_nodes
);
1502 if (prev_idx_match_malloced
)
1503 re_free (prev_idx_match
);
1504 free_fail_stack_return (fs
);
1508 cur_node
= pop_fail_stack (fs
, &idx
, nmatch
, pmatch
,
1512 re_node_set_free (&eps_via_nodes
);
1513 if (prev_idx_match_malloced
)
1514 re_free (prev_idx_match
);
1519 re_node_set_free (&eps_via_nodes
);
1520 if (prev_idx_match_malloced
)
1521 re_free (prev_idx_match
);
1522 return free_fail_stack_return (fs
);
1525 static reg_errcode_t
1526 free_fail_stack_return (fs
)
1527 struct re_fail_stack_t
*fs
;
1532 for (fs_idx
= 0; fs_idx
< fs
->num
; ++fs_idx
)
1534 re_node_set_free (&fs
->stack
[fs_idx
].eps_via_nodes
);
1535 re_free (fs
->stack
[fs_idx
].regs
);
1537 re_free (fs
->stack
);
1543 update_regs (dfa
, pmatch
, prev_idx_match
, cur_node
, cur_idx
, nmatch
)
1544 const re_dfa_t
*dfa
;
1545 regmatch_t
*pmatch
, *prev_idx_match
;
1546 int cur_node
, cur_idx
, nmatch
;
1548 int type
= dfa
->nodes
[cur_node
].type
;
1549 if (type
== OP_OPEN_SUBEXP
)
1551 int reg_num
= dfa
->nodes
[cur_node
].opr
.idx
+ 1;
1553 /* We are at the first node of this sub expression. */
1554 if (reg_num
< nmatch
)
1556 pmatch
[reg_num
].rm_so
= cur_idx
;
1557 pmatch
[reg_num
].rm_eo
= -1;
1560 else if (type
== OP_CLOSE_SUBEXP
)
1562 int reg_num
= dfa
->nodes
[cur_node
].opr
.idx
+ 1;
1563 if (reg_num
< nmatch
)
1565 /* We are at the last node of this sub expression. */
1566 if (pmatch
[reg_num
].rm_so
< cur_idx
)
1568 pmatch
[reg_num
].rm_eo
= cur_idx
;
1569 /* This is a non-empty match or we are not inside an optional
1570 subexpression. Accept this right away. */
1571 memcpy (prev_idx_match
, pmatch
, sizeof (regmatch_t
) * nmatch
);
1575 if (dfa
->nodes
[cur_node
].opt_subexp
1576 && prev_idx_match
[reg_num
].rm_so
!= -1)
1577 /* We transited through an empty match for an optional
1578 subexpression, like (a?)*, and this is not the subexp's
1579 first match. Copy back the old content of the registers
1580 so that matches of an inner subexpression are undone as
1581 well, like in ((a?))*. */
1582 memcpy (pmatch
, prev_idx_match
, sizeof (regmatch_t
) * nmatch
);
1584 /* We completed a subexpression, but it may be part of
1585 an optional one, so do not update PREV_IDX_MATCH. */
1586 pmatch
[reg_num
].rm_eo
= cur_idx
;
1592 /* This function checks the STATE_LOG from the SCTX->last_str_idx to 0
1593 and sift the nodes in each states according to the following rules.
1594 Updated state_log will be wrote to STATE_LOG.
1596 Rules: We throw away the Node `a' in the STATE_LOG[STR_IDX] if...
1597 1. When STR_IDX == MATCH_LAST(the last index in the state_log):
1598 If `a' isn't the LAST_NODE and `a' can't epsilon transit to
1599 the LAST_NODE, we throw away the node `a'.
1600 2. When 0 <= STR_IDX < MATCH_LAST and `a' accepts
1601 string `s' and transit to `b':
1602 i. If 'b' isn't in the STATE_LOG[STR_IDX+strlen('s')], we throw
1604 ii. If 'b' is in the STATE_LOG[STR_IDX+strlen('s')] but 'b' is
1605 thrown away, we throw away the node `a'.
1606 3. When 0 <= STR_IDX < MATCH_LAST and 'a' epsilon transit to 'b':
1607 i. If 'b' isn't in the STATE_LOG[STR_IDX], we throw away the
1609 ii. If 'b' is in the STATE_LOG[STR_IDX] but 'b' is thrown away,
1610 we throw away the node `a'. */
1612 #define STATE_NODE_CONTAINS(state,node) \
1613 ((state) != NULL && re_node_set_contains (&(state)->nodes, node))
1615 static reg_errcode_t
1616 sift_states_backward (mctx
, sctx
)
1617 const re_match_context_t
*mctx
;
1618 re_sift_context_t
*sctx
;
1622 int str_idx
= sctx
->last_str_idx
;
1623 re_node_set cur_dest
;
1626 assert (mctx
->state_log
!= NULL
&& mctx
->state_log
[str_idx
] != NULL
);
1629 /* Build sifted state_log[str_idx]. It has the nodes which can epsilon
1630 transit to the last_node and the last_node itself. */
1631 err
= re_node_set_init_1 (&cur_dest
, sctx
->last_node
);
1632 if (BE (err
!= REG_NOERROR
, 0))
1634 err
= update_cur_sifted_state (mctx
, sctx
, str_idx
, &cur_dest
);
1635 if (BE (err
!= REG_NOERROR
, 0))
1638 /* Then check each states in the state_log. */
1641 /* Update counters. */
1642 null_cnt
= (sctx
->sifted_states
[str_idx
] == NULL
) ? null_cnt
+ 1 : 0;
1643 if (null_cnt
> mctx
->max_mb_elem_len
)
1645 memset (sctx
->sifted_states
, '\0',
1646 sizeof (re_dfastate_t
*) * str_idx
);
1647 re_node_set_free (&cur_dest
);
1650 re_node_set_empty (&cur_dest
);
1653 if (mctx
->state_log
[str_idx
])
1655 err
= build_sifted_states (mctx
, sctx
, str_idx
, &cur_dest
);
1656 if (BE (err
!= REG_NOERROR
, 0))
1660 /* Add all the nodes which satisfy the following conditions:
1661 - It can epsilon transit to a node in CUR_DEST.
1663 And update state_log. */
1664 err
= update_cur_sifted_state (mctx
, sctx
, str_idx
, &cur_dest
);
1665 if (BE (err
!= REG_NOERROR
, 0))
1670 re_node_set_free (&cur_dest
);
1674 static reg_errcode_t
1675 build_sifted_states (mctx
, sctx
, str_idx
, cur_dest
)
1676 const re_match_context_t
*mctx
;
1677 re_sift_context_t
*sctx
;
1679 re_node_set
*cur_dest
;
1681 const re_dfa_t
*const dfa
= mctx
->dfa
;
1682 const re_node_set
*cur_src
= &mctx
->state_log
[str_idx
]->non_eps_nodes
;
1685 /* Then build the next sifted state.
1686 We build the next sifted state on `cur_dest', and update
1687 `sifted_states[str_idx]' with `cur_dest'.
1689 `cur_dest' is the sifted state from `state_log[str_idx + 1]'.
1690 `cur_src' points the node_set of the old `state_log[str_idx]'
1691 (with the epsilon nodes pre-filtered out). */
1692 for (i
= 0; i
< cur_src
->nelem
; i
++)
1694 int prev_node
= cur_src
->elems
[i
];
1699 re_token_type_t type
= dfa
->nodes
[prev_node
].type
;
1700 assert (!IS_EPSILON_NODE (type
));
1702 #ifdef RE_ENABLE_I18N
1703 /* If the node may accept `multi byte'. */
1704 if (dfa
->nodes
[prev_node
].accept_mb
)
1705 naccepted
= sift_states_iter_mb (mctx
, sctx
, prev_node
,
1706 str_idx
, sctx
->last_str_idx
);
1707 #endif /* RE_ENABLE_I18N */
1709 /* We don't check backreferences here.
1710 See update_cur_sifted_state(). */
1712 && check_node_accept (mctx
, dfa
->nodes
+ prev_node
, str_idx
)
1713 && STATE_NODE_CONTAINS (sctx
->sifted_states
[str_idx
+ 1],
1714 dfa
->nexts
[prev_node
]))
1720 if (sctx
->limits
.nelem
)
1722 int to_idx
= str_idx
+ naccepted
;
1723 if (check_dst_limits (mctx
, &sctx
->limits
,
1724 dfa
->nexts
[prev_node
], to_idx
,
1725 prev_node
, str_idx
))
1728 ret
= re_node_set_insert (cur_dest
, prev_node
);
1729 if (BE (ret
== -1, 0))
1736 /* Helper functions. */
1738 static reg_errcode_t
1739 clean_state_log_if_needed (mctx
, next_state_log_idx
)
1740 re_match_context_t
*mctx
;
1741 int next_state_log_idx
;
1743 int top
= mctx
->state_log_top
;
1745 if (next_state_log_idx
>= mctx
->input
.bufs_len
1746 || (next_state_log_idx
>= mctx
->input
.valid_len
1747 && mctx
->input
.valid_len
< mctx
->input
.len
))
1750 err
= extend_buffers (mctx
);
1751 if (BE (err
!= REG_NOERROR
, 0))
1755 if (top
< next_state_log_idx
)
1757 memset (mctx
->state_log
+ top
+ 1, '\0',
1758 sizeof (re_dfastate_t
*) * (next_state_log_idx
- top
));
1759 mctx
->state_log_top
= next_state_log_idx
;
1764 static reg_errcode_t
1765 merge_state_array (dfa
, dst
, src
, num
)
1766 const re_dfa_t
*dfa
;
1767 re_dfastate_t
**dst
;
1768 re_dfastate_t
**src
;
1773 for (st_idx
= 0; st_idx
< num
; ++st_idx
)
1775 if (dst
[st_idx
] == NULL
)
1776 dst
[st_idx
] = src
[st_idx
];
1777 else if (src
[st_idx
] != NULL
)
1779 re_node_set merged_set
;
1780 err
= re_node_set_init_union (&merged_set
, &dst
[st_idx
]->nodes
,
1781 &src
[st_idx
]->nodes
);
1782 if (BE (err
!= REG_NOERROR
, 0))
1784 dst
[st_idx
] = re_acquire_state (&err
, dfa
, &merged_set
);
1785 re_node_set_free (&merged_set
);
1786 if (BE (err
!= REG_NOERROR
, 0))
1793 static reg_errcode_t
1794 update_cur_sifted_state (mctx
, sctx
, str_idx
, dest_nodes
)
1795 const re_match_context_t
*mctx
;
1796 re_sift_context_t
*sctx
;
1798 re_node_set
*dest_nodes
;
1800 const re_dfa_t
*const dfa
= mctx
->dfa
;
1801 reg_errcode_t err
= REG_NOERROR
;
1802 const re_node_set
*candidates
;
1803 candidates
= ((mctx
->state_log
[str_idx
] == NULL
) ? NULL
1804 : &mctx
->state_log
[str_idx
]->nodes
);
1806 if (dest_nodes
->nelem
== 0)
1807 sctx
->sifted_states
[str_idx
] = NULL
;
1812 /* At first, add the nodes which can epsilon transit to a node in
1814 err
= add_epsilon_src_nodes (dfa
, dest_nodes
, candidates
);
1815 if (BE (err
!= REG_NOERROR
, 0))
1818 /* Then, check the limitations in the current sift_context. */
1819 if (sctx
->limits
.nelem
)
1821 err
= check_subexp_limits (dfa
, dest_nodes
, candidates
, &sctx
->limits
,
1822 mctx
->bkref_ents
, str_idx
);
1823 if (BE (err
!= REG_NOERROR
, 0))
1828 sctx
->sifted_states
[str_idx
] = re_acquire_state (&err
, dfa
, dest_nodes
);
1829 if (BE (err
!= REG_NOERROR
, 0))
1833 if (candidates
&& mctx
->state_log
[str_idx
]->has_backref
)
1835 err
= sift_states_bkref (mctx
, sctx
, str_idx
, candidates
);
1836 if (BE (err
!= REG_NOERROR
, 0))
1842 static reg_errcode_t
1843 add_epsilon_src_nodes (dfa
, dest_nodes
, candidates
)
1844 const re_dfa_t
*dfa
;
1845 re_node_set
*dest_nodes
;
1846 const re_node_set
*candidates
;
1848 reg_errcode_t err
= REG_NOERROR
;
1851 re_dfastate_t
*state
= re_acquire_state (&err
, dfa
, dest_nodes
);
1852 if (BE (err
!= REG_NOERROR
, 0))
1855 if (!state
->inveclosure
.alloc
)
1857 err
= re_node_set_alloc (&state
->inveclosure
, dest_nodes
->nelem
);
1858 if (BE (err
!= REG_NOERROR
, 0))
1860 for (i
= 0; i
< dest_nodes
->nelem
; i
++)
1861 re_node_set_merge (&state
->inveclosure
,
1862 dfa
->inveclosures
+ dest_nodes
->elems
[i
]);
1864 return re_node_set_add_intersect (dest_nodes
, candidates
,
1865 &state
->inveclosure
);
1868 static reg_errcode_t
1869 sub_epsilon_src_nodes (dfa
, node
, dest_nodes
, candidates
)
1870 const re_dfa_t
*dfa
;
1872 re_node_set
*dest_nodes
;
1873 const re_node_set
*candidates
;
1877 re_node_set
*inv_eclosure
= dfa
->inveclosures
+ node
;
1878 re_node_set except_nodes
;
1879 re_node_set_init_empty (&except_nodes
);
1880 for (ecl_idx
= 0; ecl_idx
< inv_eclosure
->nelem
; ++ecl_idx
)
1882 int cur_node
= inv_eclosure
->elems
[ecl_idx
];
1883 if (cur_node
== node
)
1885 if (IS_EPSILON_NODE (dfa
->nodes
[cur_node
].type
))
1887 int edst1
= dfa
->edests
[cur_node
].elems
[0];
1888 int edst2
= ((dfa
->edests
[cur_node
].nelem
> 1)
1889 ? dfa
->edests
[cur_node
].elems
[1] : -1);
1890 if ((!re_node_set_contains (inv_eclosure
, edst1
)
1891 && re_node_set_contains (dest_nodes
, edst1
))
1893 && !re_node_set_contains (inv_eclosure
, edst2
)
1894 && re_node_set_contains (dest_nodes
, edst2
)))
1896 err
= re_node_set_add_intersect (&except_nodes
, candidates
,
1897 dfa
->inveclosures
+ cur_node
);
1898 if (BE (err
!= REG_NOERROR
, 0))
1900 re_node_set_free (&except_nodes
);
1906 for (ecl_idx
= 0; ecl_idx
< inv_eclosure
->nelem
; ++ecl_idx
)
1908 int cur_node
= inv_eclosure
->elems
[ecl_idx
];
1909 if (!re_node_set_contains (&except_nodes
, cur_node
))
1911 int idx
= re_node_set_contains (dest_nodes
, cur_node
) - 1;
1912 re_node_set_remove_at (dest_nodes
, idx
);
1915 re_node_set_free (&except_nodes
);
1920 check_dst_limits (mctx
, limits
, dst_node
, dst_idx
, src_node
, src_idx
)
1921 const re_match_context_t
*mctx
;
1922 re_node_set
*limits
;
1923 int dst_node
, dst_idx
, src_node
, src_idx
;
1925 const re_dfa_t
*const dfa
= mctx
->dfa
;
1926 int lim_idx
, src_pos
, dst_pos
;
1928 int dst_bkref_idx
= search_cur_bkref_entry (mctx
, dst_idx
);
1929 int src_bkref_idx
= search_cur_bkref_entry (mctx
, src_idx
);
1930 for (lim_idx
= 0; lim_idx
< limits
->nelem
; ++lim_idx
)
1933 struct re_backref_cache_entry
*ent
;
1934 ent
= mctx
->bkref_ents
+ limits
->elems
[lim_idx
];
1935 subexp_idx
= dfa
->nodes
[ent
->node
].opr
.idx
;
1937 dst_pos
= check_dst_limits_calc_pos (mctx
, limits
->elems
[lim_idx
],
1938 subexp_idx
, dst_node
, dst_idx
,
1940 src_pos
= check_dst_limits_calc_pos (mctx
, limits
->elems
[lim_idx
],
1941 subexp_idx
, src_node
, src_idx
,
1945 <src> <dst> ( <subexp> )
1946 ( <subexp> ) <src> <dst>
1947 ( <subexp1> <src> <subexp2> <dst> <subexp3> ) */
1948 if (src_pos
== dst_pos
)
1949 continue; /* This is unrelated limitation. */
1957 check_dst_limits_calc_pos_1 (mctx
, boundaries
, subexp_idx
, from_node
, bkref_idx
)
1958 const re_match_context_t
*mctx
;
1959 int boundaries
, subexp_idx
, from_node
, bkref_idx
;
1961 const re_dfa_t
*const dfa
= mctx
->dfa
;
1962 const re_node_set
*eclosures
= dfa
->eclosures
+ from_node
;
1965 /* Else, we are on the boundary: examine the nodes on the epsilon
1967 for (node_idx
= 0; node_idx
< eclosures
->nelem
; ++node_idx
)
1969 int node
= eclosures
->elems
[node_idx
];
1970 switch (dfa
->nodes
[node
].type
)
1973 if (bkref_idx
!= -1)
1975 struct re_backref_cache_entry
*ent
= mctx
->bkref_ents
+ bkref_idx
;
1980 if (ent
->node
!= node
)
1983 if (subexp_idx
< BITSET_WORD_BITS
1984 && !(ent
->eps_reachable_subexps_map
1985 & ((bitset_word_t
) 1 << subexp_idx
)))
1988 /* Recurse trying to reach the OP_OPEN_SUBEXP and
1989 OP_CLOSE_SUBEXP cases below. But, if the
1990 destination node is the same node as the source
1991 node, don't recurse because it would cause an
1992 infinite loop: a regex that exhibits this behavior
1994 dst
= dfa
->edests
[node
].elems
[0];
1995 if (dst
== from_node
)
1999 else /* if (boundaries & 2) */
2004 check_dst_limits_calc_pos_1 (mctx
, boundaries
, subexp_idx
,
2006 if (cpos
== -1 /* && (boundaries & 1) */)
2008 if (cpos
== 0 && (boundaries
& 2))
2011 if (subexp_idx
< BITSET_WORD_BITS
)
2012 ent
->eps_reachable_subexps_map
2013 &= ~((bitset_word_t
) 1 << subexp_idx
);
2015 while (ent
++->more
);
2019 case OP_OPEN_SUBEXP
:
2020 if ((boundaries
& 1) && subexp_idx
== dfa
->nodes
[node
].opr
.idx
)
2024 case OP_CLOSE_SUBEXP
:
2025 if ((boundaries
& 2) && subexp_idx
== dfa
->nodes
[node
].opr
.idx
)
2034 return (boundaries
& 2) ? 1 : 0;
2038 check_dst_limits_calc_pos (mctx
, limit
, subexp_idx
, from_node
, str_idx
, bkref_idx
)
2039 const re_match_context_t
*mctx
;
2040 int limit
, subexp_idx
, from_node
, str_idx
, bkref_idx
;
2042 struct re_backref_cache_entry
*lim
= mctx
->bkref_ents
+ limit
;
2045 /* If we are outside the range of the subexpression, return -1 or 1. */
2046 if (str_idx
< lim
->subexp_from
)
2049 if (lim
->subexp_to
< str_idx
)
2052 /* If we are within the subexpression, return 0. */
2053 boundaries
= (str_idx
== lim
->subexp_from
);
2054 boundaries
|= (str_idx
== lim
->subexp_to
) << 1;
2055 if (boundaries
== 0)
2058 /* Else, examine epsilon closure. */
2059 return check_dst_limits_calc_pos_1 (mctx
, boundaries
, subexp_idx
,
2060 from_node
, bkref_idx
);
2063 /* Check the limitations of sub expressions LIMITS, and remove the nodes
2064 which are against limitations from DEST_NODES. */
2066 static reg_errcode_t
2067 check_subexp_limits (dfa
, dest_nodes
, candidates
, limits
, bkref_ents
, str_idx
)
2068 const re_dfa_t
*dfa
;
2069 re_node_set
*dest_nodes
;
2070 const re_node_set
*candidates
;
2071 re_node_set
*limits
;
2072 struct re_backref_cache_entry
*bkref_ents
;
2076 int node_idx
, lim_idx
;
2078 for (lim_idx
= 0; lim_idx
< limits
->nelem
; ++lim_idx
)
2081 struct re_backref_cache_entry
*ent
;
2082 ent
= bkref_ents
+ limits
->elems
[lim_idx
];
2084 if (str_idx
<= ent
->subexp_from
|| ent
->str_idx
< str_idx
)
2085 continue; /* This is unrelated limitation. */
2087 subexp_idx
= dfa
->nodes
[ent
->node
].opr
.idx
;
2088 if (ent
->subexp_to
== str_idx
)
2092 for (node_idx
= 0; node_idx
< dest_nodes
->nelem
; ++node_idx
)
2094 int node
= dest_nodes
->elems
[node_idx
];
2095 re_token_type_t type
= dfa
->nodes
[node
].type
;
2096 if (type
== OP_OPEN_SUBEXP
2097 && subexp_idx
== dfa
->nodes
[node
].opr
.idx
)
2099 else if (type
== OP_CLOSE_SUBEXP
2100 && subexp_idx
== dfa
->nodes
[node
].opr
.idx
)
2104 /* Check the limitation of the open subexpression. */
2105 /* Note that (ent->subexp_to = str_idx != ent->subexp_from). */
2108 err
= sub_epsilon_src_nodes (dfa
, ops_node
, dest_nodes
,
2110 if (BE (err
!= REG_NOERROR
, 0))
2114 /* Check the limitation of the close subexpression. */
2116 for (node_idx
= 0; node_idx
< dest_nodes
->nelem
; ++node_idx
)
2118 int node
= dest_nodes
->elems
[node_idx
];
2119 if (!re_node_set_contains (dfa
->inveclosures
+ node
,
2121 && !re_node_set_contains (dfa
->eclosures
+ node
,
2124 /* It is against this limitation.
2125 Remove it form the current sifted state. */
2126 err
= sub_epsilon_src_nodes (dfa
, node
, dest_nodes
,
2128 if (BE (err
!= REG_NOERROR
, 0))
2134 else /* (ent->subexp_to != str_idx) */
2136 for (node_idx
= 0; node_idx
< dest_nodes
->nelem
; ++node_idx
)
2138 int node
= dest_nodes
->elems
[node_idx
];
2139 re_token_type_t type
= dfa
->nodes
[node
].type
;
2140 if (type
== OP_CLOSE_SUBEXP
|| type
== OP_OPEN_SUBEXP
)
2142 if (subexp_idx
!= dfa
->nodes
[node
].opr
.idx
)
2144 /* It is against this limitation.
2145 Remove it form the current sifted state. */
2146 err
= sub_epsilon_src_nodes (dfa
, node
, dest_nodes
,
2148 if (BE (err
!= REG_NOERROR
, 0))
2157 static reg_errcode_t
2158 sift_states_bkref (mctx
, sctx
, str_idx
, candidates
)
2159 const re_match_context_t
*mctx
;
2160 re_sift_context_t
*sctx
;
2162 const re_node_set
*candidates
;
2164 const re_dfa_t
*const dfa
= mctx
->dfa
;
2167 re_sift_context_t local_sctx
;
2168 int first_idx
= search_cur_bkref_entry (mctx
, str_idx
);
2170 if (first_idx
== -1)
2173 local_sctx
.sifted_states
= NULL
; /* Mark that it hasn't been initialized. */
2175 for (node_idx
= 0; node_idx
< candidates
->nelem
; ++node_idx
)
2178 re_token_type_t type
;
2179 struct re_backref_cache_entry
*entry
;
2180 node
= candidates
->elems
[node_idx
];
2181 type
= dfa
->nodes
[node
].type
;
2182 /* Avoid infinite loop for the REs like "()\1+". */
2183 if (node
== sctx
->last_node
&& str_idx
== sctx
->last_str_idx
)
2185 if (type
!= OP_BACK_REF
)
2188 entry
= mctx
->bkref_ents
+ first_idx
;
2189 enabled_idx
= first_idx
;
2196 re_dfastate_t
*cur_state
;
2198 if (entry
->node
!= node
)
2200 subexp_len
= entry
->subexp_to
- entry
->subexp_from
;
2201 to_idx
= str_idx
+ subexp_len
;
2202 dst_node
= (subexp_len
? dfa
->nexts
[node
]
2203 : dfa
->edests
[node
].elems
[0]);
2205 if (to_idx
> sctx
->last_str_idx
2206 || sctx
->sifted_states
[to_idx
] == NULL
2207 || !STATE_NODE_CONTAINS (sctx
->sifted_states
[to_idx
], dst_node
)
2208 || check_dst_limits (mctx
, &sctx
->limits
, node
,
2209 str_idx
, dst_node
, to_idx
))
2212 if (local_sctx
.sifted_states
== NULL
)
2215 err
= re_node_set_init_copy (&local_sctx
.limits
, &sctx
->limits
);
2216 if (BE (err
!= REG_NOERROR
, 0))
2219 local_sctx
.last_node
= node
;
2220 local_sctx
.last_str_idx
= str_idx
;
2221 ret
= re_node_set_insert (&local_sctx
.limits
, enabled_idx
);
2222 if (BE (ret
< 0, 0))
2227 cur_state
= local_sctx
.sifted_states
[str_idx
];
2228 err
= sift_states_backward (mctx
, &local_sctx
);
2229 if (BE (err
!= REG_NOERROR
, 0))
2231 if (sctx
->limited_states
!= NULL
)
2233 err
= merge_state_array (dfa
, sctx
->limited_states
,
2234 local_sctx
.sifted_states
,
2236 if (BE (err
!= REG_NOERROR
, 0))
2239 local_sctx
.sifted_states
[str_idx
] = cur_state
;
2240 re_node_set_remove (&local_sctx
.limits
, enabled_idx
);
2242 /* mctx->bkref_ents may have changed, reload the pointer. */
2243 entry
= mctx
->bkref_ents
+ enabled_idx
;
2245 while (enabled_idx
++, entry
++->more
);
2249 if (local_sctx
.sifted_states
!= NULL
)
2251 re_node_set_free (&local_sctx
.limits
);
2258 #ifdef RE_ENABLE_I18N
2260 sift_states_iter_mb (mctx
, sctx
, node_idx
, str_idx
, max_str_idx
)
2261 const re_match_context_t
*mctx
;
2262 re_sift_context_t
*sctx
;
2263 int node_idx
, str_idx
, max_str_idx
;
2265 const re_dfa_t
*const dfa
= mctx
->dfa
;
2267 /* Check the node can accept `multi byte'. */
2268 naccepted
= check_node_accept_bytes (dfa
, node_idx
, &mctx
->input
, str_idx
);
2269 if (naccepted
> 0 && str_idx
+ naccepted
<= max_str_idx
&&
2270 !STATE_NODE_CONTAINS (sctx
->sifted_states
[str_idx
+ naccepted
],
2271 dfa
->nexts
[node_idx
]))
2272 /* The node can't accept the `multi byte', or the
2273 destination was already thrown away, then the node
2274 could't accept the current input `multi byte'. */
2276 /* Otherwise, it is sure that the node could accept
2277 `naccepted' bytes input. */
2280 #endif /* RE_ENABLE_I18N */
2283 /* Functions for state transition. */
2285 /* Return the next state to which the current state STATE will transit by
2286 accepting the current input byte, and update STATE_LOG if necessary.
2287 If STATE can accept a multibyte char/collating element/back reference
2288 update the destination of STATE_LOG. */
2290 static re_dfastate_t
*
2291 transit_state (err
, mctx
, state
)
2293 re_match_context_t
*mctx
;
2294 re_dfastate_t
*state
;
2296 re_dfastate_t
**trtable
;
2299 #ifdef RE_ENABLE_I18N
2300 /* If the current state can accept multibyte. */
2301 if (BE (state
->accept_mb
, 0))
2303 *err
= transit_state_mb (mctx
, state
);
2304 if (BE (*err
!= REG_NOERROR
, 0))
2307 #endif /* RE_ENABLE_I18N */
2309 /* Then decide the next state with the single byte. */
2312 /* don't use transition table */
2313 return transit_state_sb (err
, mctx
, state
);
2316 /* Use transition table */
2317 ch
= re_string_fetch_byte (&mctx
->input
);
2320 trtable
= state
->trtable
;
2321 if (BE (trtable
!= NULL
, 1))
2324 trtable
= state
->word_trtable
;
2325 if (BE (trtable
!= NULL
, 1))
2327 unsigned int context
;
2329 = re_string_context_at (&mctx
->input
,
2330 re_string_cur_idx (&mctx
->input
) - 1,
2332 if (IS_WORD_CONTEXT (context
))
2333 return trtable
[ch
+ SBC_MAX
];
2338 if (!build_trtable (mctx
->dfa
, state
))
2344 /* Retry, we now have a transition table. */
2348 /* Update the state_log if we need */
2350 merge_state_with_log (err
, mctx
, next_state
)
2352 re_match_context_t
*mctx
;
2353 re_dfastate_t
*next_state
;
2355 const re_dfa_t
*const dfa
= mctx
->dfa
;
2356 int 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. */
2430 find_recover_state (err
, mctx
)
2432 re_match_context_t
*mctx
;
2434 re_dfastate_t
*cur_state
;
2437 int max
= mctx
->state_log_top
;
2438 int cur_str_idx
= re_string_cur_idx (&mctx
->input
);
2442 if (++cur_str_idx
> max
)
2444 re_string_skip_bytes (&mctx
->input
, 1);
2446 while (mctx
->state_log
[cur_str_idx
] == NULL
);
2448 cur_state
= merge_state_with_log (err
, mctx
, NULL
);
2450 while (*err
== REG_NOERROR
&& cur_state
== NULL
);
2454 /* Helper functions for transit_state. */
2456 /* From the node set CUR_NODES, pick up the nodes whose types are
2457 OP_OPEN_SUBEXP and which have corresponding back references in the regular
2458 expression. And register them to use them later for evaluating the
2459 correspoding back references. */
2461 static reg_errcode_t
2462 check_subexp_matching_top (mctx
, cur_nodes
, str_idx
)
2463 re_match_context_t
*mctx
;
2464 re_node_set
*cur_nodes
;
2467 const re_dfa_t
*const dfa
= mctx
->dfa
;
2471 /* TODO: This isn't efficient.
2472 Because there might be more than one nodes whose types are
2473 OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
2476 for (node_idx
= 0; node_idx
< cur_nodes
->nelem
; ++node_idx
)
2478 int node
= cur_nodes
->elems
[node_idx
];
2479 if (dfa
->nodes
[node
].type
== OP_OPEN_SUBEXP
2480 && dfa
->nodes
[node
].opr
.idx
< BITSET_WORD_BITS
2481 && (dfa
->used_bkref_map
2482 & ((bitset_word_t
) 1 << dfa
->nodes
[node
].opr
.idx
)))
2484 err
= match_ctx_add_subtop (mctx
, node
, str_idx
);
2485 if (BE (err
!= REG_NOERROR
, 0))
2493 /* Return the next state to which the current state STATE will transit by
2494 accepting the current input byte. */
2496 static re_dfastate_t
*
2497 transit_state_sb (err
, mctx
, state
)
2499 re_match_context_t
*mctx
;
2500 re_dfastate_t
*state
;
2502 const re_dfa_t
*const dfa
= mctx
->dfa
;
2503 re_node_set next_nodes
;
2504 re_dfastate_t
*next_state
;
2505 int node_cnt
, cur_str_idx
= re_string_cur_idx (&mctx
->input
);
2506 unsigned int context
;
2508 *err
= re_node_set_alloc (&next_nodes
, state
->nodes
.nelem
+ 1);
2509 if (BE (*err
!= REG_NOERROR
, 0))
2511 for (node_cnt
= 0; node_cnt
< state
->nodes
.nelem
; ++node_cnt
)
2513 int cur_node
= state
->nodes
.elems
[node_cnt
];
2514 if (check_node_accept (mctx
, dfa
->nodes
+ cur_node
, cur_str_idx
))
2516 *err
= re_node_set_merge (&next_nodes
,
2517 dfa
->eclosures
+ dfa
->nexts
[cur_node
]);
2518 if (BE (*err
!= REG_NOERROR
, 0))
2520 re_node_set_free (&next_nodes
);
2525 context
= re_string_context_at (&mctx
->input
, cur_str_idx
, mctx
->eflags
);
2526 next_state
= re_acquire_state_context (err
, dfa
, &next_nodes
, context
);
2527 /* We don't need to check errors here, since the return value of
2528 this function is next_state and ERR is already set. */
2530 re_node_set_free (&next_nodes
);
2531 re_string_skip_bytes (&mctx
->input
, 1);
2536 #ifdef RE_ENABLE_I18N
2537 static reg_errcode_t
2538 transit_state_mb (mctx
, pstate
)
2539 re_match_context_t
*mctx
;
2540 re_dfastate_t
*pstate
;
2542 const re_dfa_t
*const dfa
= mctx
->dfa
;
2546 for (i
= 0; i
< pstate
->nodes
.nelem
; ++i
)
2548 re_node_set dest_nodes
, *new_nodes
;
2549 int cur_node_idx
= pstate
->nodes
.elems
[i
];
2550 int naccepted
, dest_idx
;
2551 unsigned int context
;
2552 re_dfastate_t
*dest_state
;
2554 if (!dfa
->nodes
[cur_node_idx
].accept_mb
)
2557 if (dfa
->nodes
[cur_node_idx
].constraint
)
2559 context
= re_string_context_at (&mctx
->input
,
2560 re_string_cur_idx (&mctx
->input
),
2562 if (NOT_SATISFY_NEXT_CONSTRAINT (dfa
->nodes
[cur_node_idx
].constraint
,
2567 /* How many bytes the node can accept? */
2568 naccepted
= check_node_accept_bytes (dfa
, cur_node_idx
, &mctx
->input
,
2569 re_string_cur_idx (&mctx
->input
));
2573 /* The node can accepts `naccepted' bytes. */
2574 dest_idx
= re_string_cur_idx (&mctx
->input
) + naccepted
;
2575 mctx
->max_mb_elem_len
= ((mctx
->max_mb_elem_len
< naccepted
) ? naccepted
2576 : mctx
->max_mb_elem_len
);
2577 err
= clean_state_log_if_needed (mctx
, dest_idx
);
2578 if (BE (err
!= REG_NOERROR
, 0))
2581 assert (dfa
->nexts
[cur_node_idx
] != -1);
2583 new_nodes
= dfa
->eclosures
+ dfa
->nexts
[cur_node_idx
];
2585 dest_state
= mctx
->state_log
[dest_idx
];
2586 if (dest_state
== NULL
)
2587 dest_nodes
= *new_nodes
;
2590 err
= re_node_set_init_union (&dest_nodes
,
2591 dest_state
->entrance_nodes
, new_nodes
);
2592 if (BE (err
!= REG_NOERROR
, 0))
2595 context
= re_string_context_at (&mctx
->input
, dest_idx
- 1,
2597 mctx
->state_log
[dest_idx
]
2598 = re_acquire_state_context (&err
, dfa
, &dest_nodes
, context
);
2599 if (dest_state
!= NULL
)
2600 re_node_set_free (&dest_nodes
);
2601 if (BE (mctx
->state_log
[dest_idx
] == NULL
&& err
!= REG_NOERROR
, 0))
2606 #endif /* RE_ENABLE_I18N */
2608 static reg_errcode_t
2609 transit_state_bkref (mctx
, nodes
)
2610 re_match_context_t
*mctx
;
2611 const re_node_set
*nodes
;
2613 const re_dfa_t
*const dfa
= mctx
->dfa
;
2616 int cur_str_idx
= re_string_cur_idx (&mctx
->input
);
2618 for (i
= 0; i
< nodes
->nelem
; ++i
)
2620 int dest_str_idx
, prev_nelem
, bkc_idx
;
2621 int node_idx
= nodes
->elems
[i
];
2622 unsigned int context
;
2623 const re_token_t
*node
= dfa
->nodes
+ node_idx
;
2624 re_node_set
*new_dest_nodes
;
2626 /* Check whether `node' is a backreference or not. */
2627 if (node
->type
!= OP_BACK_REF
)
2630 if (node
->constraint
)
2632 context
= re_string_context_at (&mctx
->input
, cur_str_idx
,
2634 if (NOT_SATISFY_NEXT_CONSTRAINT (node
->constraint
, context
))
2638 /* `node' is a backreference.
2639 Check the substring which the substring matched. */
2640 bkc_idx
= mctx
->nbkref_ents
;
2641 err
= get_subexp (mctx
, node_idx
, cur_str_idx
);
2642 if (BE (err
!= REG_NOERROR
, 0))
2645 /* And add the epsilon closures (which is `new_dest_nodes') of
2646 the backreference to appropriate state_log. */
2648 assert (dfa
->nexts
[node_idx
] != -1);
2650 for (; bkc_idx
< mctx
->nbkref_ents
; ++bkc_idx
)
2653 re_dfastate_t
*dest_state
;
2654 struct re_backref_cache_entry
*bkref_ent
;
2655 bkref_ent
= mctx
->bkref_ents
+ bkc_idx
;
2656 if (bkref_ent
->node
!= node_idx
|| bkref_ent
->str_idx
!= cur_str_idx
)
2658 subexp_len
= bkref_ent
->subexp_to
- bkref_ent
->subexp_from
;
2659 new_dest_nodes
= (subexp_len
== 0
2660 ? dfa
->eclosures
+ dfa
->edests
[node_idx
].elems
[0]
2661 : dfa
->eclosures
+ dfa
->nexts
[node_idx
]);
2662 dest_str_idx
= (cur_str_idx
+ bkref_ent
->subexp_to
2663 - bkref_ent
->subexp_from
);
2664 context
= re_string_context_at (&mctx
->input
, dest_str_idx
- 1,
2666 dest_state
= mctx
->state_log
[dest_str_idx
];
2667 prev_nelem
= ((mctx
->state_log
[cur_str_idx
] == NULL
) ? 0
2668 : mctx
->state_log
[cur_str_idx
]->nodes
.nelem
);
2669 /* Add `new_dest_node' to state_log. */
2670 if (dest_state
== NULL
)
2672 mctx
->state_log
[dest_str_idx
]
2673 = re_acquire_state_context (&err
, dfa
, new_dest_nodes
,
2675 if (BE (mctx
->state_log
[dest_str_idx
] == NULL
2676 && err
!= REG_NOERROR
, 0))
2681 re_node_set dest_nodes
;
2682 err
= re_node_set_init_union (&dest_nodes
,
2683 dest_state
->entrance_nodes
,
2685 if (BE (err
!= REG_NOERROR
, 0))
2687 re_node_set_free (&dest_nodes
);
2690 mctx
->state_log
[dest_str_idx
]
2691 = re_acquire_state_context (&err
, dfa
, &dest_nodes
, context
);
2692 re_node_set_free (&dest_nodes
);
2693 if (BE (mctx
->state_log
[dest_str_idx
] == NULL
2694 && err
!= REG_NOERROR
, 0))
2697 /* We need to check recursively if the backreference can epsilon
2700 && mctx
->state_log
[cur_str_idx
]->nodes
.nelem
> prev_nelem
)
2702 err
= check_subexp_matching_top (mctx
, new_dest_nodes
,
2704 if (BE (err
!= REG_NOERROR
, 0))
2706 err
= transit_state_bkref (mctx
, new_dest_nodes
);
2707 if (BE (err
!= REG_NOERROR
, 0))
2717 /* Enumerate all the candidates which the backreference BKREF_NODE can match
2718 at BKREF_STR_IDX, and register them by match_ctx_add_entry().
2719 Note that we might collect inappropriate candidates here.
2720 However, the cost of checking them strictly here is too high, then we
2721 delay these checking for prune_impossible_nodes(). */
2723 static reg_errcode_t
2724 get_subexp (mctx
, bkref_node
, bkref_str_idx
)
2725 re_match_context_t
*mctx
;
2726 int bkref_node
, bkref_str_idx
;
2728 const re_dfa_t
*const dfa
= mctx
->dfa
;
2729 int subexp_num
, sub_top_idx
;
2730 const char *buf
= (const char *) re_string_get_buffer (&mctx
->input
);
2731 /* Return if we have already checked BKREF_NODE at BKREF_STR_IDX. */
2732 int cache_idx
= search_cur_bkref_entry (mctx
, bkref_str_idx
);
2733 if (cache_idx
!= -1)
2735 const struct re_backref_cache_entry
*entry
2736 = mctx
->bkref_ents
+ cache_idx
;
2738 if (entry
->node
== bkref_node
)
2739 return REG_NOERROR
; /* We already checked it. */
2740 while (entry
++->more
);
2743 subexp_num
= dfa
->nodes
[bkref_node
].opr
.idx
;
2745 /* For each sub expression */
2746 for (sub_top_idx
= 0; sub_top_idx
< mctx
->nsub_tops
; ++sub_top_idx
)
2749 re_sub_match_top_t
*sub_top
= mctx
->sub_tops
[sub_top_idx
];
2750 re_sub_match_last_t
*sub_last
;
2751 int sub_last_idx
, sl_str
, bkref_str_off
;
2753 if (dfa
->nodes
[sub_top
->node
].opr
.idx
!= subexp_num
)
2754 continue; /* It isn't related. */
2756 sl_str
= sub_top
->str_idx
;
2757 bkref_str_off
= bkref_str_idx
;
2758 /* At first, check the last node of sub expressions we already
2760 for (sub_last_idx
= 0; sub_last_idx
< sub_top
->nlasts
; ++sub_last_idx
)
2763 sub_last
= sub_top
->lasts
[sub_last_idx
];
2764 sl_str_diff
= sub_last
->str_idx
- sl_str
;
2765 /* The matched string by the sub expression match with the substring
2766 at the back reference? */
2767 if (sl_str_diff
> 0)
2769 if (BE (bkref_str_off
+ sl_str_diff
> mctx
->input
.valid_len
, 0))
2771 /* Not enough chars for a successful match. */
2772 if (bkref_str_off
+ sl_str_diff
> mctx
->input
.len
)
2775 err
= clean_state_log_if_needed (mctx
,
2778 if (BE (err
!= REG_NOERROR
, 0))
2780 buf
= (const char *) re_string_get_buffer (&mctx
->input
);
2782 if (memcmp (buf
+ bkref_str_off
, buf
+ sl_str
, sl_str_diff
) != 0)
2783 /* We don't need to search this sub expression any more. */
2786 bkref_str_off
+= sl_str_diff
;
2787 sl_str
+= sl_str_diff
;
2788 err
= get_subexp_sub (mctx
, sub_top
, sub_last
, bkref_node
,
2791 /* Reload buf, since the preceding call might have reallocated
2793 buf
= (const char *) re_string_get_buffer (&mctx
->input
);
2795 if (err
== REG_NOMATCH
)
2797 if (BE (err
!= REG_NOERROR
, 0))
2801 if (sub_last_idx
< sub_top
->nlasts
)
2803 if (sub_last_idx
> 0)
2805 /* Then, search for the other last nodes of the sub expression. */
2806 for (; sl_str
<= bkref_str_idx
; ++sl_str
)
2808 int cls_node
, sl_str_off
;
2809 const re_node_set
*nodes
;
2810 sl_str_off
= sl_str
- sub_top
->str_idx
;
2811 /* The matched string by the sub expression match with the substring
2812 at the back reference? */
2815 if (BE (bkref_str_off
>= mctx
->input
.valid_len
, 0))
2817 /* If we are at the end of the input, we cannot match. */
2818 if (bkref_str_off
>= mctx
->input
.len
)
2821 err
= extend_buffers (mctx
);
2822 if (BE (err
!= REG_NOERROR
, 0))
2825 buf
= (const char *) re_string_get_buffer (&mctx
->input
);
2827 if (buf
[bkref_str_off
++] != buf
[sl_str
- 1])
2828 break; /* We don't need to search this sub expression
2831 if (mctx
->state_log
[sl_str
] == NULL
)
2833 /* Does this state have a ')' of the sub expression? */
2834 nodes
= &mctx
->state_log
[sl_str
]->nodes
;
2835 cls_node
= find_subexp_node (dfa
, nodes
, subexp_num
,
2839 if (sub_top
->path
== NULL
)
2841 sub_top
->path
= calloc (sizeof (state_array_t
),
2842 sl_str
- sub_top
->str_idx
+ 1);
2843 if (sub_top
->path
== NULL
)
2846 /* Can the OP_OPEN_SUBEXP node arrive the OP_CLOSE_SUBEXP node
2847 in the current context? */
2848 err
= check_arrival (mctx
, sub_top
->path
, sub_top
->node
,
2849 sub_top
->str_idx
, cls_node
, sl_str
,
2851 if (err
== REG_NOMATCH
)
2853 if (BE (err
!= REG_NOERROR
, 0))
2855 sub_last
= match_ctx_add_sublast (sub_top
, cls_node
, sl_str
);
2856 if (BE (sub_last
== NULL
, 0))
2858 err
= get_subexp_sub (mctx
, sub_top
, sub_last
, bkref_node
,
2860 if (err
== REG_NOMATCH
)
2867 /* Helper functions for get_subexp(). */
2869 /* Check SUB_LAST can arrive to the back reference BKREF_NODE at BKREF_STR.
2870 If it can arrive, register the sub expression expressed with SUB_TOP
2873 static reg_errcode_t
2874 get_subexp_sub (mctx
, sub_top
, sub_last
, bkref_node
, bkref_str
)
2875 re_match_context_t
*mctx
;
2876 const re_sub_match_top_t
*sub_top
;
2877 re_sub_match_last_t
*sub_last
;
2878 int bkref_node
, bkref_str
;
2882 /* Can the subexpression arrive the back reference? */
2883 err
= check_arrival (mctx
, &sub_last
->path
, sub_last
->node
,
2884 sub_last
->str_idx
, bkref_node
, bkref_str
,
2886 if (err
!= REG_NOERROR
)
2888 err
= match_ctx_add_entry (mctx
, bkref_node
, bkref_str
, sub_top
->str_idx
,
2890 if (BE (err
!= REG_NOERROR
, 0))
2892 to_idx
= bkref_str
+ sub_last
->str_idx
- sub_top
->str_idx
;
2893 return clean_state_log_if_needed (mctx
, to_idx
);
2896 /* Find the first node which is '(' or ')' and whose index is SUBEXP_IDX.
2897 Search '(' if FL_OPEN, or search ')' otherwise.
2898 TODO: This function isn't efficient...
2899 Because there might be more than one nodes whose types are
2900 OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
2905 find_subexp_node (dfa
, nodes
, subexp_idx
, type
)
2906 const re_dfa_t
*dfa
;
2907 const re_node_set
*nodes
;
2908 int subexp_idx
, type
;
2911 for (cls_idx
= 0; cls_idx
< nodes
->nelem
; ++cls_idx
)
2913 int cls_node
= nodes
->elems
[cls_idx
];
2914 const re_token_t
*node
= dfa
->nodes
+ cls_node
;
2915 if (node
->type
== type
2916 && node
->opr
.idx
== subexp_idx
)
2922 /* Check whether the node TOP_NODE at TOP_STR can arrive to the node
2923 LAST_NODE at LAST_STR. We record the path onto PATH since it will be
2925 Return REG_NOERROR if it can arrive, or REG_NOMATCH otherwise. */
2927 static reg_errcode_t
2928 check_arrival (mctx
, path
, top_node
, top_str
, last_node
, last_str
,
2930 re_match_context_t
*mctx
;
2931 state_array_t
*path
;
2932 int top_node
, top_str
, last_node
, last_str
, type
;
2934 const re_dfa_t
*const dfa
= mctx
->dfa
;
2935 reg_errcode_t err
= REG_NOERROR
;
2936 int subexp_num
, backup_cur_idx
, str_idx
, null_cnt
;
2937 re_dfastate_t
*cur_state
= NULL
;
2938 re_node_set
*cur_nodes
, next_nodes
;
2939 re_dfastate_t
**backup_state_log
;
2940 unsigned int context
;
2942 subexp_num
= dfa
->nodes
[top_node
].opr
.idx
;
2943 /* Extend the buffer if we need. */
2944 if (BE (path
->alloc
< last_str
+ mctx
->max_mb_elem_len
+ 1, 0))
2946 re_dfastate_t
**new_array
;
2947 int old_alloc
= path
->alloc
;
2948 path
->alloc
+= last_str
+ mctx
->max_mb_elem_len
+ 1;
2949 new_array
= re_realloc (path
->array
, re_dfastate_t
*, path
->alloc
);
2950 if (BE (new_array
== NULL
, 0))
2952 path
->alloc
= old_alloc
;
2955 path
->array
= new_array
;
2956 memset (new_array
+ old_alloc
, '\0',
2957 sizeof (re_dfastate_t
*) * (path
->alloc
- old_alloc
));
2960 str_idx
= path
->next_idx
== 0 ? top_str
: path
->next_idx
;
2962 /* Temporary modify MCTX. */
2963 backup_state_log
= mctx
->state_log
;
2964 backup_cur_idx
= mctx
->input
.cur_idx
;
2965 mctx
->state_log
= path
->array
;
2966 mctx
->input
.cur_idx
= str_idx
;
2968 /* Setup initial node set. */
2969 context
= re_string_context_at (&mctx
->input
, str_idx
- 1, mctx
->eflags
);
2970 if (str_idx
== top_str
)
2972 err
= re_node_set_init_1 (&next_nodes
, top_node
);
2973 if (BE (err
!= REG_NOERROR
, 0))
2975 err
= check_arrival_expand_ecl (dfa
, &next_nodes
, subexp_num
, type
);
2976 if (BE (err
!= REG_NOERROR
, 0))
2978 re_node_set_free (&next_nodes
);
2984 cur_state
= mctx
->state_log
[str_idx
];
2985 if (cur_state
&& cur_state
->has_backref
)
2987 err
= re_node_set_init_copy (&next_nodes
, &cur_state
->nodes
);
2988 if (BE (err
!= REG_NOERROR
, 0))
2992 re_node_set_init_empty (&next_nodes
);
2994 if (str_idx
== top_str
|| (cur_state
&& cur_state
->has_backref
))
2996 if (next_nodes
.nelem
)
2998 err
= expand_bkref_cache (mctx
, &next_nodes
, str_idx
,
3000 if (BE (err
!= REG_NOERROR
, 0))
3002 re_node_set_free (&next_nodes
);
3006 cur_state
= re_acquire_state_context (&err
, dfa
, &next_nodes
, context
);
3007 if (BE (cur_state
== NULL
&& err
!= REG_NOERROR
, 0))
3009 re_node_set_free (&next_nodes
);
3012 mctx
->state_log
[str_idx
] = cur_state
;
3015 for (null_cnt
= 0; str_idx
< last_str
&& null_cnt
<= mctx
->max_mb_elem_len
;)
3017 re_node_set_empty (&next_nodes
);
3018 if (mctx
->state_log
[str_idx
+ 1])
3020 err
= re_node_set_merge (&next_nodes
,
3021 &mctx
->state_log
[str_idx
+ 1]->nodes
);
3022 if (BE (err
!= REG_NOERROR
, 0))
3024 re_node_set_free (&next_nodes
);
3030 err
= check_arrival_add_next_nodes (mctx
, str_idx
,
3031 &cur_state
->non_eps_nodes
,
3033 if (BE (err
!= REG_NOERROR
, 0))
3035 re_node_set_free (&next_nodes
);
3040 if (next_nodes
.nelem
)
3042 err
= check_arrival_expand_ecl (dfa
, &next_nodes
, subexp_num
, type
);
3043 if (BE (err
!= REG_NOERROR
, 0))
3045 re_node_set_free (&next_nodes
);
3048 err
= expand_bkref_cache (mctx
, &next_nodes
, str_idx
,
3050 if (BE (err
!= REG_NOERROR
, 0))
3052 re_node_set_free (&next_nodes
);
3056 context
= re_string_context_at (&mctx
->input
, str_idx
- 1, mctx
->eflags
);
3057 cur_state
= re_acquire_state_context (&err
, dfa
, &next_nodes
, context
);
3058 if (BE (cur_state
== NULL
&& err
!= REG_NOERROR
, 0))
3060 re_node_set_free (&next_nodes
);
3063 mctx
->state_log
[str_idx
] = cur_state
;
3064 null_cnt
= cur_state
== NULL
? null_cnt
+ 1 : 0;
3066 re_node_set_free (&next_nodes
);
3067 cur_nodes
= (mctx
->state_log
[last_str
] == NULL
? NULL
3068 : &mctx
->state_log
[last_str
]->nodes
);
3069 path
->next_idx
= str_idx
;
3072 mctx
->state_log
= backup_state_log
;
3073 mctx
->input
.cur_idx
= backup_cur_idx
;
3075 /* Then check the current node set has the node LAST_NODE. */
3076 if (cur_nodes
!= NULL
&& re_node_set_contains (cur_nodes
, last_node
))
3082 /* Helper functions for check_arrival. */
3084 /* Calculate the destination nodes of CUR_NODES at STR_IDX, and append them
3086 TODO: This function is similar to the functions transit_state*(),
3087 however this function has many additional works.
3088 Can't we unify them? */
3090 static reg_errcode_t
3091 check_arrival_add_next_nodes (mctx
, str_idx
, cur_nodes
, next_nodes
)
3092 re_match_context_t
*mctx
;
3094 re_node_set
*cur_nodes
, *next_nodes
;
3096 const re_dfa_t
*const dfa
= mctx
->dfa
;
3099 reg_errcode_t err
= REG_NOERROR
;
3100 re_node_set union_set
;
3101 re_node_set_init_empty (&union_set
);
3102 for (cur_idx
= 0; cur_idx
< cur_nodes
->nelem
; ++cur_idx
)
3105 int cur_node
= cur_nodes
->elems
[cur_idx
];
3107 re_token_type_t type
= dfa
->nodes
[cur_node
].type
;
3108 assert (!IS_EPSILON_NODE (type
));
3110 #ifdef RE_ENABLE_I18N
3111 /* If the node may accept `multi byte'. */
3112 if (dfa
->nodes
[cur_node
].accept_mb
)
3114 naccepted
= check_node_accept_bytes (dfa
, cur_node
, &mctx
->input
,
3118 re_dfastate_t
*dest_state
;
3119 int next_node
= dfa
->nexts
[cur_node
];
3120 int next_idx
= str_idx
+ naccepted
;
3121 dest_state
= mctx
->state_log
[next_idx
];
3122 re_node_set_empty (&union_set
);
3125 err
= re_node_set_merge (&union_set
, &dest_state
->nodes
);
3126 if (BE (err
!= REG_NOERROR
, 0))
3128 re_node_set_free (&union_set
);
3132 result
= re_node_set_insert (&union_set
, next_node
);
3133 if (BE (result
< 0, 0))
3135 re_node_set_free (&union_set
);
3138 mctx
->state_log
[next_idx
] = re_acquire_state (&err
, dfa
,
3140 if (BE (mctx
->state_log
[next_idx
] == NULL
3141 && err
!= REG_NOERROR
, 0))
3143 re_node_set_free (&union_set
);
3148 #endif /* RE_ENABLE_I18N */
3150 || check_node_accept (mctx
, dfa
->nodes
+ cur_node
, str_idx
))
3152 result
= re_node_set_insert (next_nodes
, dfa
->nexts
[cur_node
]);
3153 if (BE (result
< 0, 0))
3155 re_node_set_free (&union_set
);
3160 re_node_set_free (&union_set
);
3164 /* For all the nodes in CUR_NODES, add the epsilon closures of them to
3165 CUR_NODES, however exclude the nodes which are:
3166 - inside the sub expression whose number is EX_SUBEXP, if FL_OPEN.
3167 - out of the sub expression whose number is EX_SUBEXP, if !FL_OPEN.
3170 static reg_errcode_t
3171 check_arrival_expand_ecl (dfa
, cur_nodes
, ex_subexp
, type
)
3172 const re_dfa_t
*dfa
;
3173 re_node_set
*cur_nodes
;
3174 int ex_subexp
, type
;
3177 int idx
, outside_node
;
3178 re_node_set new_nodes
;
3180 assert (cur_nodes
->nelem
);
3182 err
= re_node_set_alloc (&new_nodes
, cur_nodes
->nelem
);
3183 if (BE (err
!= REG_NOERROR
, 0))
3185 /* Create a new node set NEW_NODES with the nodes which are epsilon
3186 closures of the node in CUR_NODES. */
3188 for (idx
= 0; idx
< cur_nodes
->nelem
; ++idx
)
3190 int cur_node
= cur_nodes
->elems
[idx
];
3191 const re_node_set
*eclosure
= dfa
->eclosures
+ cur_node
;
3192 outside_node
= find_subexp_node (dfa
, eclosure
, ex_subexp
, type
);
3193 if (outside_node
== -1)
3195 /* There are no problematic nodes, just merge them. */
3196 err
= re_node_set_merge (&new_nodes
, eclosure
);
3197 if (BE (err
!= REG_NOERROR
, 0))
3199 re_node_set_free (&new_nodes
);
3205 /* There are problematic nodes, re-calculate incrementally. */
3206 err
= check_arrival_expand_ecl_sub (dfa
, &new_nodes
, cur_node
,
3208 if (BE (err
!= REG_NOERROR
, 0))
3210 re_node_set_free (&new_nodes
);
3215 re_node_set_free (cur_nodes
);
3216 *cur_nodes
= new_nodes
;
3220 /* Helper function for check_arrival_expand_ecl.
3221 Check incrementally the epsilon closure of TARGET, and if it isn't
3222 problematic append it to DST_NODES. */
3224 static reg_errcode_t
3225 check_arrival_expand_ecl_sub (dfa
, dst_nodes
, target
, ex_subexp
, type
)
3226 const re_dfa_t
*dfa
;
3227 int target
, ex_subexp
, type
;
3228 re_node_set
*dst_nodes
;
3231 for (cur_node
= target
; !re_node_set_contains (dst_nodes
, cur_node
);)
3235 if (dfa
->nodes
[cur_node
].type
== type
3236 && dfa
->nodes
[cur_node
].opr
.idx
== ex_subexp
)
3238 if (type
== OP_CLOSE_SUBEXP
)
3240 err
= re_node_set_insert (dst_nodes
, cur_node
);
3241 if (BE (err
== -1, 0))
3246 err
= re_node_set_insert (dst_nodes
, cur_node
);
3247 if (BE (err
== -1, 0))
3249 if (dfa
->edests
[cur_node
].nelem
== 0)
3251 if (dfa
->edests
[cur_node
].nelem
== 2)
3253 err
= check_arrival_expand_ecl_sub (dfa
, dst_nodes
,
3254 dfa
->edests
[cur_node
].elems
[1],
3256 if (BE (err
!= REG_NOERROR
, 0))
3259 cur_node
= dfa
->edests
[cur_node
].elems
[0];
3265 /* For all the back references in the current state, calculate the
3266 destination of the back references by the appropriate entry
3267 in MCTX->BKREF_ENTS. */
3269 static reg_errcode_t
3270 expand_bkref_cache (mctx
, cur_nodes
, cur_str
, subexp_num
,
3272 re_match_context_t
*mctx
;
3273 int cur_str
, subexp_num
, type
;
3274 re_node_set
*cur_nodes
;
3276 const re_dfa_t
*const dfa
= mctx
->dfa
;
3278 int cache_idx_start
= search_cur_bkref_entry (mctx
, cur_str
);
3279 struct re_backref_cache_entry
*ent
;
3281 if (cache_idx_start
== -1)
3285 ent
= mctx
->bkref_ents
+ cache_idx_start
;
3288 int to_idx
, next_node
;
3290 /* Is this entry ENT is appropriate? */
3291 if (!re_node_set_contains (cur_nodes
, ent
->node
))
3294 to_idx
= cur_str
+ ent
->subexp_to
- ent
->subexp_from
;
3295 /* Calculate the destination of the back reference, and append it
3296 to MCTX->STATE_LOG. */
3297 if (to_idx
== cur_str
)
3299 /* The backreference did epsilon transit, we must re-check all the
3300 node in the current state. */
3301 re_node_set new_dests
;
3302 reg_errcode_t err2
, err3
;
3303 next_node
= dfa
->edests
[ent
->node
].elems
[0];
3304 if (re_node_set_contains (cur_nodes
, next_node
))
3306 err
= re_node_set_init_1 (&new_dests
, next_node
);
3307 err2
= check_arrival_expand_ecl (dfa
, &new_dests
, subexp_num
, type
);
3308 err3
= re_node_set_merge (cur_nodes
, &new_dests
);
3309 re_node_set_free (&new_dests
);
3310 if (BE (err
!= REG_NOERROR
|| err2
!= REG_NOERROR
3311 || err3
!= REG_NOERROR
, 0))
3313 err
= (err
!= REG_NOERROR
? err
3314 : (err2
!= REG_NOERROR
? err2
: err3
));
3317 /* TODO: It is still inefficient... */
3322 re_node_set union_set
;
3323 next_node
= dfa
->nexts
[ent
->node
];
3324 if (mctx
->state_log
[to_idx
])
3327 if (re_node_set_contains (&mctx
->state_log
[to_idx
]->nodes
,
3330 err
= re_node_set_init_copy (&union_set
,
3331 &mctx
->state_log
[to_idx
]->nodes
);
3332 ret
= re_node_set_insert (&union_set
, next_node
);
3333 if (BE (err
!= REG_NOERROR
|| ret
< 0, 0))
3335 re_node_set_free (&union_set
);
3336 err
= err
!= REG_NOERROR
? err
: REG_ESPACE
;
3342 err
= re_node_set_init_1 (&union_set
, next_node
);
3343 if (BE (err
!= REG_NOERROR
, 0))
3346 mctx
->state_log
[to_idx
] = re_acquire_state (&err
, dfa
, &union_set
);
3347 re_node_set_free (&union_set
);
3348 if (BE (mctx
->state_log
[to_idx
] == NULL
3349 && err
!= REG_NOERROR
, 0))
3353 while (ent
++->more
);
3357 /* Build transition table for the state.
3358 Return 1 if succeeded, otherwise return NULL. */
3361 build_trtable (dfa
, state
)
3362 const re_dfa_t
*dfa
;
3363 re_dfastate_t
*state
;
3366 int i
, j
, ch
, need_word_trtable
= 0;
3367 bitset_word_t elem
, mask
;
3368 bool dests_node_malloced
= false;
3369 bool dest_states_malloced
= false;
3370 int ndests
; /* Number of the destination states from `state'. */
3371 re_dfastate_t
**trtable
;
3372 re_dfastate_t
**dest_states
= NULL
, **dest_states_word
, **dest_states_nl
;
3373 re_node_set follows
, *dests_node
;
3375 bitset_t acceptable
;
3379 re_node_set dests_node
[SBC_MAX
];
3380 bitset_t dests_ch
[SBC_MAX
];
3383 /* We build DFA states which corresponds to the destination nodes
3384 from `state'. `dests_node[i]' represents the nodes which i-th
3385 destination state contains, and `dests_ch[i]' represents the
3386 characters which i-th destination state accepts. */
3387 if (__libc_use_alloca (sizeof (struct dests_alloc
)))
3388 dests_alloc
= (struct dests_alloc
*) alloca (sizeof (struct dests_alloc
));
3391 dests_alloc
= re_malloc (struct dests_alloc
, 1);
3392 if (BE (dests_alloc
== NULL
, 0))
3394 dests_node_malloced
= true;
3396 dests_node
= dests_alloc
->dests_node
;
3397 dests_ch
= dests_alloc
->dests_ch
;
3399 /* Initialize transiton table. */
3400 state
->word_trtable
= state
->trtable
= NULL
;
3402 /* At first, group all nodes belonging to `state' into several
3404 ndests
= group_nodes_into_DFAstates (dfa
, state
, dests_node
, dests_ch
);
3405 if (BE (ndests
<= 0, 0))
3407 if (dests_node_malloced
)
3409 /* Return 0 in case of an error, 1 otherwise. */
3412 state
->trtable
= (re_dfastate_t
**)
3413 calloc (sizeof (re_dfastate_t
*), SBC_MAX
);
3419 err
= re_node_set_alloc (&follows
, ndests
+ 1);
3420 if (BE (err
!= REG_NOERROR
, 0))
3423 if (__libc_use_alloca ((sizeof (re_node_set
) + sizeof (bitset_t
)) * SBC_MAX
3424 + ndests
* 3 * sizeof (re_dfastate_t
*)))
3425 dest_states
= (re_dfastate_t
**)
3426 alloca (ndests
* 3 * sizeof (re_dfastate_t
*));
3429 dest_states
= (re_dfastate_t
**)
3430 malloc (ndests
* 3 * sizeof (re_dfastate_t
*));
3431 if (BE (dest_states
== NULL
, 0))
3434 if (dest_states_malloced
)
3436 re_node_set_free (&follows
);
3437 for (i
= 0; i
< ndests
; ++i
)
3438 re_node_set_free (dests_node
+ i
);
3439 if (dests_node_malloced
)
3443 dest_states_malloced
= true;
3445 dest_states_word
= dest_states
+ ndests
;
3446 dest_states_nl
= dest_states_word
+ ndests
;
3447 bitset_empty (acceptable
);
3449 /* Then build the states for all destinations. */
3450 for (i
= 0; i
< ndests
; ++i
)
3453 re_node_set_empty (&follows
);
3454 /* Merge the follows of this destination states. */
3455 for (j
= 0; j
< dests_node
[i
].nelem
; ++j
)
3457 next_node
= dfa
->nexts
[dests_node
[i
].elems
[j
]];
3458 if (next_node
!= -1)
3460 err
= re_node_set_merge (&follows
, dfa
->eclosures
+ next_node
);
3461 if (BE (err
!= REG_NOERROR
, 0))
3465 dest_states
[i
] = re_acquire_state_context (&err
, dfa
, &follows
, 0);
3466 if (BE (dest_states
[i
] == NULL
&& err
!= REG_NOERROR
, 0))
3468 /* If the new state has context constraint,
3469 build appropriate states for these contexts. */
3470 if (dest_states
[i
]->has_constraint
)
3472 dest_states_word
[i
] = re_acquire_state_context (&err
, dfa
, &follows
,
3474 if (BE (dest_states_word
[i
] == NULL
&& err
!= REG_NOERROR
, 0))
3477 if (dest_states
[i
] != dest_states_word
[i
] && dfa
->mb_cur_max
> 1)
3478 need_word_trtable
= 1;
3480 dest_states_nl
[i
] = re_acquire_state_context (&err
, dfa
, &follows
,
3482 if (BE (dest_states_nl
[i
] == NULL
&& err
!= REG_NOERROR
, 0))
3487 dest_states_word
[i
] = dest_states
[i
];
3488 dest_states_nl
[i
] = dest_states
[i
];
3490 bitset_merge (acceptable
, dests_ch
[i
]);
3493 if (!BE (need_word_trtable
, 0))
3495 /* We don't care about whether the following character is a word
3496 character, or we are in a single-byte character set so we can
3497 discern by looking at the character code: allocate a
3498 256-entry transition table. */
3499 trtable
= state
->trtable
=
3500 (re_dfastate_t
**) calloc (sizeof (re_dfastate_t
*), SBC_MAX
);
3501 if (BE (trtable
== NULL
, 0))
3504 /* For all characters ch...: */
3505 for (i
= 0; i
< BITSET_WORDS
; ++i
)
3506 for (ch
= i
* BITSET_WORD_BITS
, elem
= acceptable
[i
], mask
= 1;
3508 mask
<<= 1, elem
>>= 1, ++ch
)
3509 if (BE (elem
& 1, 0))
3511 /* There must be exactly one destination which accepts
3512 character ch. See group_nodes_into_DFAstates. */
3513 for (j
= 0; (dests_ch
[j
][i
] & mask
) == 0; ++j
)
3516 /* j-th destination accepts the word character ch. */
3517 if (dfa
->word_char
[i
] & mask
)
3518 trtable
[ch
] = dest_states_word
[j
];
3520 trtable
[ch
] = dest_states
[j
];
3525 /* We care about whether the following character is a word
3526 character, and we are in a multi-byte character set: discern
3527 by looking at the character code: build two 256-entry
3528 transition tables, one starting at trtable[0] and one
3529 starting at trtable[SBC_MAX]. */
3530 trtable
= state
->word_trtable
=
3531 (re_dfastate_t
**) calloc (sizeof (re_dfastate_t
*), 2 * SBC_MAX
);
3532 if (BE (trtable
== NULL
, 0))
3535 /* For all characters ch...: */
3536 for (i
= 0; i
< BITSET_WORDS
; ++i
)
3537 for (ch
= i
* BITSET_WORD_BITS
, elem
= acceptable
[i
], mask
= 1;
3539 mask
<<= 1, elem
>>= 1, ++ch
)
3540 if (BE (elem
& 1, 0))
3542 /* There must be exactly one destination which accepts
3543 character ch. See group_nodes_into_DFAstates. */
3544 for (j
= 0; (dests_ch
[j
][i
] & mask
) == 0; ++j
)
3547 /* j-th destination accepts the word character ch. */
3548 trtable
[ch
] = dest_states
[j
];
3549 trtable
[ch
+ SBC_MAX
] = dest_states_word
[j
];
3554 if (bitset_contain (acceptable
, NEWLINE_CHAR
))
3556 /* The current state accepts newline character. */
3557 for (j
= 0; j
< ndests
; ++j
)
3558 if (bitset_contain (dests_ch
[j
], NEWLINE_CHAR
))
3560 /* k-th destination accepts newline character. */
3561 trtable
[NEWLINE_CHAR
] = dest_states_nl
[j
];
3562 if (need_word_trtable
)
3563 trtable
[NEWLINE_CHAR
+ SBC_MAX
] = dest_states_nl
[j
];
3564 /* There must be only one destination which accepts
3565 newline. See group_nodes_into_DFAstates. */
3570 if (dest_states_malloced
)
3573 re_node_set_free (&follows
);
3574 for (i
= 0; i
< ndests
; ++i
)
3575 re_node_set_free (dests_node
+ i
);
3577 if (dests_node_malloced
)
3583 /* Group all nodes belonging to STATE into several destinations.
3584 Then for all destinations, set the nodes belonging to the destination
3585 to DESTS_NODE[i] and set the characters accepted by the destination
3586 to DEST_CH[i]. This function return the number of destinations. */
3589 group_nodes_into_DFAstates (dfa
, state
, dests_node
, dests_ch
)
3590 const re_dfa_t
*dfa
;
3591 const re_dfastate_t
*state
;
3592 re_node_set
*dests_node
;
3598 int 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 memset (accepts
, '\xff', sizeof (bitset_t
) / 2);
3635 if (!(dfa
->syntax
& RE_DOT_NEWLINE
))
3636 bitset_clear (accepts
, '\n');
3637 if (dfa
->syntax
& RE_DOT_NOT_NULL
)
3638 bitset_clear (accepts
, '\0');
3644 /* Check the `accepts' and sift the characters which are not
3645 match it the context. */
3648 if (constraint
& NEXT_NEWLINE_CONSTRAINT
)
3650 bool accepts_newline
= bitset_contain (accepts
, NEWLINE_CHAR
);
3651 bitset_empty (accepts
);
3652 if (accepts_newline
)
3653 bitset_set (accepts
, NEWLINE_CHAR
);
3657 if (constraint
& NEXT_ENDBUF_CONSTRAINT
)
3659 bitset_empty (accepts
);
3663 if (constraint
& NEXT_WORD_CONSTRAINT
)
3665 bitset_word_t any_set
= 0;
3666 if (type
== CHARACTER
&& !node
->word_char
)
3668 bitset_empty (accepts
);
3671 #ifdef RE_ENABLE_I18N
3672 if (dfa
->mb_cur_max
> 1)
3673 for (j
= 0; j
< BITSET_WORDS
; ++j
)
3674 any_set
|= (accepts
[j
] &= (dfa
->word_char
[j
] | ~dfa
->sb_char
[j
]));
3677 for (j
= 0; j
< BITSET_WORDS
; ++j
)
3678 any_set
|= (accepts
[j
] &= dfa
->word_char
[j
]);
3682 if (constraint
& NEXT_NOTWORD_CONSTRAINT
)
3684 bitset_word_t any_set
= 0;
3685 if (type
== CHARACTER
&& node
->word_char
)
3687 bitset_empty (accepts
);
3690 #ifdef RE_ENABLE_I18N
3691 if (dfa
->mb_cur_max
> 1)
3692 for (j
= 0; j
< BITSET_WORDS
; ++j
)
3693 any_set
|= (accepts
[j
] &= ~(dfa
->word_char
[j
] & dfa
->sb_char
[j
]));
3696 for (j
= 0; j
< BITSET_WORDS
; ++j
)
3697 any_set
|= (accepts
[j
] &= ~dfa
->word_char
[j
]);
3703 /* Then divide `accepts' into DFA states, or create a new
3704 state. Above, we make sure that accepts is not empty. */
3705 for (j
= 0; j
< ndests
; ++j
)
3707 bitset_t intersec
; /* Intersection sets, see below. */
3709 /* Flags, see below. */
3710 bitset_word_t has_intersec
, not_subset
, not_consumed
;
3712 /* Optimization, skip if this state doesn't accept the character. */
3713 if (type
== CHARACTER
&& !bitset_contain (dests_ch
[j
], node
->opr
.c
))
3716 /* Enumerate the intersection set of this state and `accepts'. */
3718 for (k
= 0; k
< BITSET_WORDS
; ++k
)
3719 has_intersec
|= intersec
[k
] = accepts
[k
] & dests_ch
[j
][k
];
3720 /* And skip if the intersection set is empty. */
3724 /* Then check if this state is a subset of `accepts'. */
3725 not_subset
= not_consumed
= 0;
3726 for (k
= 0; k
< BITSET_WORDS
; ++k
)
3728 not_subset
|= remains
[k
] = ~accepts
[k
] & dests_ch
[j
][k
];
3729 not_consumed
|= accepts
[k
] = accepts
[k
] & ~dests_ch
[j
][k
];
3732 /* If this state isn't a subset of `accepts', create a
3733 new group state, which has the `remains'. */
3736 bitset_copy (dests_ch
[ndests
], remains
);
3737 bitset_copy (dests_ch
[j
], intersec
);
3738 err
= re_node_set_init_copy (dests_node
+ ndests
, &dests_node
[j
]);
3739 if (BE (err
!= REG_NOERROR
, 0))
3744 /* Put the position in the current group. */
3745 result
= re_node_set_insert (&dests_node
[j
], cur_nodes
->elems
[i
]);
3746 if (BE (result
< 0, 0))
3749 /* If all characters are consumed, go to next node. */
3753 /* Some characters remain, create a new group. */
3756 bitset_copy (dests_ch
[ndests
], accepts
);
3757 err
= re_node_set_init_1 (dests_node
+ ndests
, cur_nodes
->elems
[i
]);
3758 if (BE (err
!= REG_NOERROR
, 0))
3761 bitset_empty (accepts
);
3766 for (j
= 0; j
< ndests
; ++j
)
3767 re_node_set_free (dests_node
+ j
);
3771 #ifdef RE_ENABLE_I18N
3772 /* Check how many bytes the node `dfa->nodes[node_idx]' accepts.
3773 Return the number of the bytes the node accepts.
3774 STR_IDX is the current index of the input string.
3776 This function handles the nodes which can accept one character, or
3777 one collating element like '.', '[a-z]', opposite to the other nodes
3778 can only accept one byte. */
3781 check_node_accept_bytes (dfa
, node_idx
, input
, str_idx
)
3782 const re_dfa_t
*dfa
;
3783 int node_idx
, str_idx
;
3784 const re_string_t
*input
;
3786 const re_token_t
*node
= dfa
->nodes
+ node_idx
;
3787 int char_len
, elem_len
;
3790 if (BE (node
->type
== OP_UTF8_PERIOD
, 0))
3792 unsigned char c
= re_string_byte_at (input
, str_idx
), d
;
3793 if (BE (c
< 0xc2, 1))
3796 if (str_idx
+ 2 > input
->len
)
3799 d
= re_string_byte_at (input
, str_idx
+ 1);
3801 return (d
< 0x80 || d
> 0xbf) ? 0 : 2;
3805 if (c
== 0xe0 && d
< 0xa0)
3811 if (c
== 0xf0 && d
< 0x90)
3817 if (c
== 0xf8 && d
< 0x88)
3823 if (c
== 0xfc && d
< 0x84)
3829 if (str_idx
+ char_len
> input
->len
)
3832 for (i
= 1; i
< char_len
; ++i
)
3834 d
= re_string_byte_at (input
, str_idx
+ i
);
3835 if (d
< 0x80 || d
> 0xbf)
3841 char_len
= re_string_char_size_at (input
, str_idx
);
3842 if (node
->type
== OP_PERIOD
)
3846 /* FIXME: I don't think this if is needed, as both '\n'
3847 and '\0' are char_len == 1. */
3848 /* '.' accepts any one character except the following two cases. */
3849 if ((!(dfa
->syntax
& RE_DOT_NEWLINE
) &&
3850 re_string_byte_at (input
, str_idx
) == '\n') ||
3851 ((dfa
->syntax
& RE_DOT_NOT_NULL
) &&
3852 re_string_byte_at (input
, str_idx
) == '\0'))
3857 elem_len
= re_string_elem_size_at (input
, str_idx
);
3858 if ((elem_len
<= 1 && char_len
<= 1) || char_len
== 0)
3861 if (node
->type
== COMPLEX_BRACKET
)
3863 const re_charset_t
*cset
= node
->opr
.mbcset
;
3865 const unsigned char *pin
3866 = ((const unsigned char *) re_string_get_buffer (input
) + str_idx
);
3871 wchar_t wc
= ((cset
->nranges
|| cset
->nchar_classes
|| cset
->nmbchars
)
3872 ? re_string_wchar_at (input
, str_idx
) : 0);
3874 /* match with multibyte character? */
3875 for (i
= 0; i
< cset
->nmbchars
; ++i
)
3876 if (wc
== cset
->mbchars
[i
])
3878 match_len
= char_len
;
3879 goto check_node_accept_bytes_match
;
3881 /* match with character_class? */
3882 for (i
= 0; i
< cset
->nchar_classes
; ++i
)
3884 wctype_t wt
= cset
->char_classes
[i
];
3885 if (__iswctype (wc
, wt
))
3887 match_len
= char_len
;
3888 goto check_node_accept_bytes_match
;
3893 nrules
= _NL_CURRENT_WORD (LC_COLLATE
, _NL_COLLATE_NRULES
);
3896 unsigned int in_collseq
= 0;
3897 const int32_t *table
, *indirect
;
3898 const unsigned char *weights
, *extra
;
3899 const char *collseqwc
;
3901 /* This #include defines a local function! */
3902 # include <locale/weight.h>
3904 /* match with collating_symbol? */
3905 if (cset
->ncoll_syms
)
3906 extra
= (const unsigned char *)
3907 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_SYMB_EXTRAMB
);
3908 for (i
= 0; i
< cset
->ncoll_syms
; ++i
)
3910 const unsigned char *coll_sym
= extra
+ cset
->coll_syms
[i
];
3911 /* Compare the length of input collating element and
3912 the length of current collating element. */
3913 if (*coll_sym
!= elem_len
)
3915 /* Compare each bytes. */
3916 for (j
= 0; j
< *coll_sym
; j
++)
3917 if (pin
[j
] != coll_sym
[1 + j
])
3921 /* Match if every bytes is equal. */
3923 goto check_node_accept_bytes_match
;
3929 if (elem_len
<= char_len
)
3931 collseqwc
= _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_COLLSEQWC
);
3932 in_collseq
= __collseq_table_lookup (collseqwc
, wc
);
3935 in_collseq
= find_collation_sequence_value (pin
, elem_len
);
3937 /* match with range expression? */
3938 for (i
= 0; i
< cset
->nranges
; ++i
)
3939 if (cset
->range_starts
[i
] <= in_collseq
3940 && in_collseq
<= cset
->range_ends
[i
])
3942 match_len
= elem_len
;
3943 goto check_node_accept_bytes_match
;
3946 /* match with equivalence_class? */
3947 if (cset
->nequiv_classes
)
3949 const unsigned char *cp
= pin
;
3950 table
= (const int32_t *)
3951 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_TABLEMB
);
3952 weights
= (const unsigned char *)
3953 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_WEIGHTMB
);
3954 extra
= (const unsigned char *)
3955 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_EXTRAMB
);
3956 indirect
= (const int32_t *)
3957 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_INDIRECTMB
);
3958 idx
= findidx (&cp
);
3960 for (i
= 0; i
< cset
->nequiv_classes
; ++i
)
3962 int32_t equiv_class_idx
= cset
->equiv_classes
[i
];
3963 size_t weight_len
= weights
[idx
];
3964 if (weight_len
== weights
[equiv_class_idx
])
3967 while (cnt
<= weight_len
3968 && (weights
[equiv_class_idx
+ 1 + cnt
]
3969 == weights
[idx
+ 1 + cnt
]))
3971 if (cnt
> weight_len
)
3973 match_len
= elem_len
;
3974 goto check_node_accept_bytes_match
;
3983 /* match with range expression? */
3985 wchar_t cmp_buf
[] = {L
'\0', L
'\0', wc
, L
'\0', L
'\0', L
'\0'};
3987 wchar_t cmp_buf
[] = {L
'\0', L
'\0', L
'\0', L
'\0', L
'\0', L
'\0'};
3990 for (i
= 0; i
< cset
->nranges
; ++i
)
3992 cmp_buf
[0] = cset
->range_starts
[i
];
3993 cmp_buf
[4] = cset
->range_ends
[i
];
3994 if (wcscoll (cmp_buf
, cmp_buf
+ 2) <= 0
3995 && wcscoll (cmp_buf
+ 2, cmp_buf
+ 4) <= 0)
3997 match_len
= char_len
;
3998 goto check_node_accept_bytes_match
;
4002 check_node_accept_bytes_match
:
4003 if (!cset
->non_match
)
4010 return (elem_len
> char_len
) ? elem_len
: char_len
;
4018 find_collation_sequence_value (mbs
, mbs_len
)
4019 const unsigned char *mbs
;
4022 uint32_t nrules
= _NL_CURRENT_WORD (LC_COLLATE
, _NL_COLLATE_NRULES
);
4027 /* No valid character. Match it as a single byte character. */
4028 const unsigned char *collseq
= (const unsigned char *)
4029 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_COLLSEQMB
);
4030 return collseq
[mbs
[0]];
4037 const unsigned char *extra
= (const unsigned char *)
4038 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_SYMB_EXTRAMB
);
4039 int32_t extrasize
= (const unsigned char *)
4040 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_SYMB_EXTRAMB
+ 1) - extra
;
4042 for (idx
= 0; idx
< extrasize
;)
4044 int mbs_cnt
, found
= 0;
4045 int32_t elem_mbs_len
;
4046 /* Skip the name of collating element name. */
4047 idx
= idx
+ extra
[idx
] + 1;
4048 elem_mbs_len
= extra
[idx
++];
4049 if (mbs_len
== elem_mbs_len
)
4051 for (mbs_cnt
= 0; mbs_cnt
< elem_mbs_len
; ++mbs_cnt
)
4052 if (extra
[idx
+ mbs_cnt
] != mbs
[mbs_cnt
])
4054 if (mbs_cnt
== elem_mbs_len
)
4055 /* Found the entry. */
4058 /* Skip the byte sequence of the collating element. */
4059 idx
+= elem_mbs_len
;
4060 /* Adjust for the alignment. */
4061 idx
= (idx
+ 3) & ~3;
4062 /* Skip the collation sequence value. */
4063 idx
+= sizeof (uint32_t);
4064 /* Skip the wide char sequence of the collating element. */
4065 idx
= idx
+ sizeof (uint32_t) * (extra
[idx
] + 1);
4066 /* If we found the entry, return the sequence value. */
4068 return *(uint32_t *) (extra
+ idx
);
4069 /* Skip the collation sequence value. */
4070 idx
+= sizeof (uint32_t);
4076 #endif /* RE_ENABLE_I18N */
4078 /* Check whether the node accepts the byte which is IDX-th
4079 byte of the INPUT. */
4082 check_node_accept (mctx
, node
, idx
)
4083 const re_match_context_t
*mctx
;
4084 const re_token_t
*node
;
4088 ch
= re_string_byte_at (&mctx
->input
, idx
);
4092 if (node
->opr
.c
!= ch
)
4096 case SIMPLE_BRACKET
:
4097 if (!bitset_contain (node
->opr
.sbcset
, ch
))
4101 #ifdef RE_ENABLE_I18N
4102 case OP_UTF8_PERIOD
:
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 extend_buffers (mctx
)
4134 re_match_context_t
*mctx
;
4137 re_string_t
*pstr
= &mctx
->input
;
4139 /* Double the lengthes of the buffers. */
4140 ret
= re_string_realloc_buffers (pstr
, pstr
->bufs_len
* 2);
4141 if (BE (ret
!= REG_NOERROR
, 0))
4144 if (mctx
->state_log
!= NULL
)
4146 /* And double the length of state_log. */
4147 /* XXX We have no indication of the size of this buffer. If this
4148 allocation fail we have no indication that the state_log array
4149 does not have the right size. */
4150 re_dfastate_t
**new_array
= re_realloc (mctx
->state_log
, re_dfastate_t
*,
4151 pstr
->bufs_len
+ 1);
4152 if (BE (new_array
== NULL
, 0))
4154 mctx
->state_log
= new_array
;
4157 /* Then reconstruct the buffers. */
4160 #ifdef RE_ENABLE_I18N
4161 if (pstr
->mb_cur_max
> 1)
4163 ret
= build_wcs_upper_buffer (pstr
);
4164 if (BE (ret
!= REG_NOERROR
, 0))
4168 #endif /* RE_ENABLE_I18N */
4169 build_upper_buffer (pstr
);
4173 #ifdef RE_ENABLE_I18N
4174 if (pstr
->mb_cur_max
> 1)
4175 build_wcs_buffer (pstr
);
4177 #endif /* RE_ENABLE_I18N */
4179 if (pstr
->trans
!= NULL
)
4180 re_string_translate_buffer (pstr
);
4187 /* Functions for matching context. */
4189 /* Initialize MCTX. */
4191 static reg_errcode_t
4192 match_ctx_init (mctx
, eflags
, n
)
4193 re_match_context_t
*mctx
;
4196 mctx
->eflags
= eflags
;
4197 mctx
->match_last
= -1;
4200 mctx
->bkref_ents
= re_malloc (struct re_backref_cache_entry
, n
);
4201 mctx
->sub_tops
= re_malloc (re_sub_match_top_t
*, n
);
4202 if (BE (mctx
->bkref_ents
== NULL
|| mctx
->sub_tops
== NULL
, 0))
4205 /* Already zero-ed by the caller.
4207 mctx->bkref_ents = NULL;
4208 mctx->nbkref_ents = 0;
4209 mctx->nsub_tops = 0; */
4210 mctx
->abkref_ents
= n
;
4211 mctx
->max_mb_elem_len
= 1;
4212 mctx
->asub_tops
= n
;
4216 /* Clean the entries which depend on the current input in MCTX.
4217 This function must be invoked when the matcher changes the start index
4218 of the input, or changes the input string. */
4221 match_ctx_clean (mctx
)
4222 re_match_context_t
*mctx
;
4225 for (st_idx
= 0; st_idx
< mctx
->nsub_tops
; ++st_idx
)
4228 re_sub_match_top_t
*top
= mctx
->sub_tops
[st_idx
];
4229 for (sl_idx
= 0; sl_idx
< top
->nlasts
; ++sl_idx
)
4231 re_sub_match_last_t
*last
= top
->lasts
[sl_idx
];
4232 re_free (last
->path
.array
);
4235 re_free (top
->lasts
);
4238 re_free (top
->path
->array
);
4239 re_free (top
->path
);
4244 mctx
->nsub_tops
= 0;
4245 mctx
->nbkref_ents
= 0;
4248 /* Free all the memory associated with MCTX. */
4251 match_ctx_free (mctx
)
4252 re_match_context_t
*mctx
;
4254 /* First, free all the memory associated with MCTX->SUB_TOPS. */
4255 match_ctx_clean (mctx
);
4256 re_free (mctx
->sub_tops
);
4257 re_free (mctx
->bkref_ents
);
4260 /* Add a new backreference entry to MCTX.
4261 Note that we assume that caller never call this function with duplicate
4262 entry, and call with STR_IDX which isn't smaller than any existing entry.
4265 static reg_errcode_t
4266 match_ctx_add_entry (mctx
, node
, str_idx
, from
, to
)
4267 re_match_context_t
*mctx
;
4268 int node
, str_idx
, from
, to
;
4270 if (mctx
->nbkref_ents
>= mctx
->abkref_ents
)
4272 struct re_backref_cache_entry
* new_entry
;
4273 new_entry
= re_realloc (mctx
->bkref_ents
, struct re_backref_cache_entry
,
4274 mctx
->abkref_ents
* 2);
4275 if (BE (new_entry
== NULL
, 0))
4277 re_free (mctx
->bkref_ents
);
4280 mctx
->bkref_ents
= new_entry
;
4281 memset (mctx
->bkref_ents
+ mctx
->nbkref_ents
, '\0',
4282 sizeof (struct re_backref_cache_entry
) * mctx
->abkref_ents
);
4283 mctx
->abkref_ents
*= 2;
4285 if (mctx
->nbkref_ents
> 0
4286 && mctx
->bkref_ents
[mctx
->nbkref_ents
- 1].str_idx
== str_idx
)
4287 mctx
->bkref_ents
[mctx
->nbkref_ents
- 1].more
= 1;
4289 mctx
->bkref_ents
[mctx
->nbkref_ents
].node
= node
;
4290 mctx
->bkref_ents
[mctx
->nbkref_ents
].str_idx
= str_idx
;
4291 mctx
->bkref_ents
[mctx
->nbkref_ents
].subexp_from
= from
;
4292 mctx
->bkref_ents
[mctx
->nbkref_ents
].subexp_to
= to
;
4294 /* This is a cache that saves negative results of check_dst_limits_calc_pos.
4295 If bit N is clear, means that this entry won't epsilon-transition to
4296 an OP_OPEN_SUBEXP or OP_CLOSE_SUBEXP for the N+1-th subexpression. If
4297 it is set, check_dst_limits_calc_pos_1 will recurse and try to find one
4300 A backreference does not epsilon-transition unless it is empty, so set
4301 to all zeros if FROM != TO. */
4302 mctx
->bkref_ents
[mctx
->nbkref_ents
].eps_reachable_subexps_map
4303 = (from
== to
? ~0 : 0);
4305 mctx
->bkref_ents
[mctx
->nbkref_ents
++].more
= 0;
4306 if (mctx
->max_mb_elem_len
< to
- from
)
4307 mctx
->max_mb_elem_len
= to
- from
;
4311 /* Search for the first entry which has the same str_idx, or -1 if none is
4312 found. Note that MCTX->BKREF_ENTS is already sorted by MCTX->STR_IDX. */
4315 search_cur_bkref_entry (mctx
, str_idx
)
4316 const re_match_context_t
*mctx
;
4319 int left
, right
, mid
, last
;
4320 last
= right
= mctx
->nbkref_ents
;
4321 for (left
= 0; left
< right
;)
4323 mid
= (left
+ right
) / 2;
4324 if (mctx
->bkref_ents
[mid
].str_idx
< str_idx
)
4329 if (left
< last
&& mctx
->bkref_ents
[left
].str_idx
== str_idx
)
4335 /* Register the node NODE, whose type is OP_OPEN_SUBEXP, and which matches
4338 static reg_errcode_t
4339 match_ctx_add_subtop (mctx
, node
, str_idx
)
4340 re_match_context_t
*mctx
;
4344 assert (mctx
->sub_tops
!= NULL
);
4345 assert (mctx
->asub_tops
> 0);
4347 if (BE (mctx
->nsub_tops
== mctx
->asub_tops
, 0))
4349 int new_asub_tops
= mctx
->asub_tops
* 2;
4350 re_sub_match_top_t
**new_array
= re_realloc (mctx
->sub_tops
,
4351 re_sub_match_top_t
*,
4353 if (BE (new_array
== NULL
, 0))
4355 mctx
->sub_tops
= new_array
;
4356 mctx
->asub_tops
= new_asub_tops
;
4358 mctx
->sub_tops
[mctx
->nsub_tops
] = calloc (1, sizeof (re_sub_match_top_t
));
4359 if (BE (mctx
->sub_tops
[mctx
->nsub_tops
] == NULL
, 0))
4361 mctx
->sub_tops
[mctx
->nsub_tops
]->node
= node
;
4362 mctx
->sub_tops
[mctx
->nsub_tops
++]->str_idx
= str_idx
;
4366 /* Register the node NODE, whose type is OP_CLOSE_SUBEXP, and which matches
4367 at STR_IDX, whose corresponding OP_OPEN_SUBEXP is SUB_TOP. */
4369 static re_sub_match_last_t
*
4370 match_ctx_add_sublast (subtop
, node
, str_idx
)
4371 re_sub_match_top_t
*subtop
;
4374 re_sub_match_last_t
*new_entry
;
4375 if (BE (subtop
->nlasts
== subtop
->alasts
, 0))
4377 int new_alasts
= 2 * subtop
->alasts
+ 1;
4378 re_sub_match_last_t
**new_array
= re_realloc (subtop
->lasts
,
4379 re_sub_match_last_t
*,
4381 if (BE (new_array
== NULL
, 0))
4383 subtop
->lasts
= new_array
;
4384 subtop
->alasts
= new_alasts
;
4386 new_entry
= calloc (1, sizeof (re_sub_match_last_t
));
4387 if (BE (new_entry
!= NULL
, 1))
4389 subtop
->lasts
[subtop
->nlasts
] = new_entry
;
4390 new_entry
->node
= node
;
4391 new_entry
->str_idx
= str_idx
;
4398 sift_ctx_init (sctx
, sifted_sts
, limited_sts
, last_node
, last_str_idx
)
4399 re_sift_context_t
*sctx
;
4400 re_dfastate_t
**sifted_sts
, **limited_sts
;
4401 int last_node
, last_str_idx
;
4403 sctx
->sifted_states
= sifted_sts
;
4404 sctx
->limited_states
= limited_sts
;
4405 sctx
->last_node
= last_node
;
4406 sctx
->last_str_idx
= last_str_idx
;
4407 re_node_set_init_empty (&sctx
->limits
);