1 /* Extended regular expression matching and search library.
2 Copyright (C) 2002, 2003, 2004 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 void match_ctx_free_subtops (re_match_context_t
*mctx
)
27 static reg_errcode_t
match_ctx_add_entry (re_match_context_t
*cache
, int node
,
28 int str_idx
, int from
, int to
)
30 static int search_cur_bkref_entry (re_match_context_t
*mctx
, int str_idx
)
32 static reg_errcode_t
match_ctx_add_subtop (re_match_context_t
*mctx
, int node
,
33 int str_idx
) internal_function
;
34 static re_sub_match_last_t
* match_ctx_add_sublast (re_sub_match_top_t
*subtop
,
35 int node
, int str_idx
)
37 static void sift_ctx_init (re_sift_context_t
*sctx
, re_dfastate_t
**sifted_sts
,
38 re_dfastate_t
**limited_sts
, int last_node
,
41 static reg_errcode_t
re_search_internal (const regex_t
*preg
,
42 const char *string
, int length
,
43 int start
, int range
, int stop
,
44 size_t nmatch
, regmatch_t pmatch
[],
45 int eflags
) internal_function
;
46 static int re_search_2_stub (struct re_pattern_buffer
*bufp
,
47 const char *string1
, int length1
,
48 const char *string2
, int length2
,
49 int start
, int range
, struct re_registers
*regs
,
50 int stop
, int ret_len
) internal_function
;
51 static int re_search_stub (struct re_pattern_buffer
*bufp
,
52 const char *string
, int length
, int start
,
53 int range
, int stop
, struct re_registers
*regs
,
54 int ret_len
) internal_function
;
55 static unsigned re_copy_regs (struct re_registers
*regs
, regmatch_t
*pmatch
,
56 int nregs
, int regs_allocated
) internal_function
;
57 static inline re_dfastate_t
*acquire_init_state_context
58 (reg_errcode_t
*err
, const re_match_context_t
*mctx
, int idx
)
59 __attribute ((always_inline
)) internal_function
;
60 static reg_errcode_t
prune_impossible_nodes (re_match_context_t
*mctx
)
62 static int check_matching (re_match_context_t
*mctx
, int fl_longest_match
,
65 static int check_halt_node_context (const re_dfa_t
*dfa
, int node
,
66 unsigned int context
) internal_function
;
67 static int check_halt_state_context (const re_match_context_t
*mctx
,
68 const re_dfastate_t
*state
, int idx
)
70 static void update_regs (re_dfa_t
*dfa
, regmatch_t
*pmatch
,
71 regmatch_t
*prev_idx_match
, int cur_node
,
72 int cur_idx
, int nmatch
) internal_function
;
73 static int proceed_next_node (const re_match_context_t
*mctx
,
74 int nregs
, regmatch_t
*regs
,
75 int *pidx
, int node
, re_node_set
*eps_via_nodes
,
76 struct re_fail_stack_t
*fs
) internal_function
;
77 static reg_errcode_t
push_fail_stack (struct re_fail_stack_t
*fs
,
78 int str_idx
, int *dests
, int nregs
,
80 re_node_set
*eps_via_nodes
) internal_function
;
81 static int pop_fail_stack (struct re_fail_stack_t
*fs
, int *pidx
, int nregs
,
82 regmatch_t
*regs
, re_node_set
*eps_via_nodes
) internal_function
;
83 static reg_errcode_t
set_regs (const regex_t
*preg
,
84 const re_match_context_t
*mctx
,
85 size_t nmatch
, regmatch_t
*pmatch
,
86 int fl_backtrack
) internal_function
;
87 static reg_errcode_t
free_fail_stack_return (struct re_fail_stack_t
*fs
) internal_function
;
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
) internal_function
;
93 #endif /* RE_ENABLE_I18N */
94 static reg_errcode_t
sift_states_backward (re_match_context_t
*mctx
,
95 re_sift_context_t
*sctx
) internal_function
;
96 static reg_errcode_t
build_sifted_states (re_match_context_t
*mctx
,
97 re_sift_context_t
*sctx
, int str_idx
,
98 re_node_set
*cur_dest
) internal_function
;
99 static reg_errcode_t
update_cur_sifted_state (re_match_context_t
*mctx
,
100 re_sift_context_t
*sctx
,
102 re_node_set
*dest_nodes
) internal_function
;
103 static reg_errcode_t
add_epsilon_src_nodes (re_dfa_t
*dfa
,
104 re_node_set
*dest_nodes
,
105 const re_node_set
*candidates
) internal_function
;
106 static reg_errcode_t
sub_epsilon_src_nodes (re_dfa_t
*dfa
, int node
,
107 re_node_set
*dest_nodes
,
108 const re_node_set
*and_nodes
) internal_function
;
109 static int check_dst_limits (re_match_context_t
*mctx
, re_node_set
*limits
,
110 int dst_node
, int dst_idx
, int src_node
,
111 int src_idx
) internal_function
;
112 static int check_dst_limits_calc_pos_1 (re_match_context_t
*mctx
,
113 int boundaries
, int subexp_idx
,
114 int from_node
, int bkref_idx
) internal_function
;
115 static int check_dst_limits_calc_pos (re_match_context_t
*mctx
,
116 int limit
, int subexp_idx
,
117 int node
, int str_idx
,
118 int bkref_idx
) internal_function
;
119 static reg_errcode_t
check_subexp_limits (re_dfa_t
*dfa
,
120 re_node_set
*dest_nodes
,
121 const re_node_set
*candidates
,
123 struct re_backref_cache_entry
*bkref_ents
,
124 int str_idx
) internal_function
;
125 static reg_errcode_t
sift_states_bkref (re_match_context_t
*mctx
,
126 re_sift_context_t
*sctx
,
127 int str_idx
, const re_node_set
*candidates
) internal_function
;
128 static reg_errcode_t
clean_state_log_if_needed (re_match_context_t
*mctx
,
129 int next_state_log_idx
) internal_function
;
130 static reg_errcode_t
merge_state_array (re_dfa_t
*dfa
, re_dfastate_t
**dst
,
131 re_dfastate_t
**src
, int num
) internal_function
;
132 static re_dfastate_t
*find_recover_state (reg_errcode_t
*err
,
133 re_match_context_t
*mctx
) internal_function
;
134 static re_dfastate_t
*transit_state (reg_errcode_t
*err
,
135 re_match_context_t
*mctx
,
136 re_dfastate_t
*state
) internal_function
;
137 static re_dfastate_t
*merge_state_with_log (reg_errcode_t
*err
,
138 re_match_context_t
*mctx
,
139 re_dfastate_t
*next_state
) internal_function
;
140 static reg_errcode_t
check_subexp_matching_top (re_match_context_t
*mctx
,
141 re_node_set
*cur_nodes
,
142 int str_idx
) internal_function
;
144 static re_dfastate_t
*transit_state_sb (reg_errcode_t
*err
,
145 re_match_context_t
*mctx
,
146 re_dfastate_t
*pstate
) internal_function
;
148 #ifdef RE_ENABLE_I18N
149 static reg_errcode_t
transit_state_mb (re_match_context_t
*mctx
,
150 re_dfastate_t
*pstate
) internal_function
;
151 #endif /* RE_ENABLE_I18N */
152 static reg_errcode_t
transit_state_bkref (re_match_context_t
*mctx
,
153 const re_node_set
*nodes
) internal_function
;
154 static reg_errcode_t
get_subexp (re_match_context_t
*mctx
,
155 int bkref_node
, int bkref_str_idx
) internal_function
;
156 static reg_errcode_t
get_subexp_sub (re_match_context_t
*mctx
,
157 const re_sub_match_top_t
*sub_top
,
158 re_sub_match_last_t
*sub_last
,
159 int bkref_node
, int bkref_str
) internal_function
;
160 static int find_subexp_node (const re_dfa_t
*dfa
, const re_node_set
*nodes
,
161 int subexp_idx
, int type
) internal_function
;
162 static reg_errcode_t
check_arrival (re_match_context_t
*mctx
,
163 state_array_t
*path
, int top_node
,
164 int top_str
, int last_node
, int last_str
,
165 int type
) internal_function
;
166 static reg_errcode_t
check_arrival_add_next_nodes (re_match_context_t
*mctx
,
168 re_node_set
*cur_nodes
,
169 re_node_set
*next_nodes
) internal_function
;
170 static reg_errcode_t
check_arrival_expand_ecl (re_dfa_t
*dfa
,
171 re_node_set
*cur_nodes
,
172 int ex_subexp
, int type
) internal_function
;
173 static reg_errcode_t
check_arrival_expand_ecl_sub (re_dfa_t
*dfa
,
174 re_node_set
*dst_nodes
,
175 int target
, int ex_subexp
,
176 int type
) internal_function
;
177 static reg_errcode_t
expand_bkref_cache (re_match_context_t
*mctx
,
178 re_node_set
*cur_nodes
, int cur_str
,
179 int subexp_num
, int type
) internal_function
;
180 static re_dfastate_t
**build_trtable (re_dfa_t
*dfa
,
181 re_dfastate_t
*state
) internal_function
;
182 #ifdef RE_ENABLE_I18N
183 static int check_node_accept_bytes (re_dfa_t
*dfa
, int node_idx
,
184 const re_string_t
*input
, int idx
) internal_function
;
186 static unsigned int find_collation_sequence_value (const unsigned char *mbs
,
187 size_t name_len
) internal_function
;
189 #endif /* RE_ENABLE_I18N */
190 static int group_nodes_into_DFAstates (re_dfa_t
*dfa
,
191 const re_dfastate_t
*state
,
192 re_node_set
*states_node
,
193 bitset
*states_ch
) internal_function
;
194 static int check_node_accept (const re_match_context_t
*mctx
,
195 const re_token_t
*node
, int idx
) internal_function
;
196 static reg_errcode_t
extend_buffers (re_match_context_t
*mctx
) internal_function
;
198 /* Entry point for POSIX code. */
200 /* regexec searches for a given pattern, specified by PREG, in the
203 If NMATCH is zero or REG_NOSUB was set in the cflags argument to
204 `regcomp', we ignore PMATCH. Otherwise, we assume PMATCH has at
205 least NMATCH elements, and we set them to the offsets of the
206 corresponding matched substrings.
208 EFLAGS specifies `execution flags' which affect matching: if
209 REG_NOTBOL is set, then ^ does not match at the beginning of the
210 string; if REG_NOTEOL is set, then $ does not match at the end.
212 We return 0 if we find a match and REG_NOMATCH if not. */
215 regexec (preg
, string
, nmatch
, pmatch
, eflags
)
216 const regex_t
*__restrict preg
;
217 const char *__restrict string
;
225 if (eflags
& ~(REG_NOTBOL
| REG_NOTEOL
| REG_STARTEND
))
228 if (eflags
& REG_STARTEND
)
230 start
= pmatch
[0].rm_so
;
231 length
= pmatch
[0].rm_eo
;
236 length
= strlen (string
);
239 err
= re_search_internal (preg
, string
, length
, start
, length
- start
,
240 length
, 0, NULL
, eflags
);
242 err
= re_search_internal (preg
, string
, length
, start
, length
- start
,
243 length
, nmatch
, pmatch
, eflags
);
244 return err
!= REG_NOERROR
;
248 # include <shlib-compat.h>
249 versioned_symbol (libc
, __regexec
, regexec
, GLIBC_2_3_4
);
251 # if SHLIB_COMPAT (libc, GLIBC_2_0, GLIBC_2_3_4)
252 __typeof__ (__regexec
) __compat_regexec
;
255 attribute_compat_text_section
256 __compat_regexec (const regex_t
*__restrict preg
,
257 const char *__restrict string
, size_t nmatch
,
258 regmatch_t pmatch
[], int eflags
)
260 return regexec (preg
, string
, nmatch
, pmatch
,
261 eflags
& (REG_NOTBOL
| REG_NOTEOL
));
263 compat_symbol (libc
, __compat_regexec
, regexec
, GLIBC_2_0
);
267 /* Entry points for GNU code. */
269 /* re_match, re_search, re_match_2, re_search_2
271 The former two functions operate on STRING with length LENGTH,
272 while the later two operate on concatenation of STRING1 and STRING2
273 with lengths LENGTH1 and LENGTH2, respectively.
275 re_match() matches the compiled pattern in BUFP against the string,
276 starting at index START.
278 re_search() first tries matching at index START, then it tries to match
279 starting from index START + 1, and so on. The last start position tried
280 is START + RANGE. (Thus RANGE = 0 forces re_search to operate the same
283 The parameter STOP of re_{match,search}_2 specifies that no match exceeding
284 the first STOP characters of the concatenation of the strings should be
287 If REGS is not NULL, and BUFP->no_sub is not set, the offsets of the match
288 and all groups is stroed in REGS. (For the "_2" variants, the offsets are
289 computed relative to the concatenation, not relative to the individual
292 On success, re_match* functions return the length of the match, re_search*
293 return the position of the start of the match. Return value -1 means no
294 match was found and -2 indicates an internal error. */
297 re_match (bufp
, string
, length
, start
, regs
)
298 struct re_pattern_buffer
*bufp
;
301 struct re_registers
*regs
;
303 return re_search_stub (bufp
, string
, length
, start
, 0, length
, regs
, 1);
306 weak_alias (__re_match
, re_match
)
310 re_search (bufp
, string
, length
, start
, range
, regs
)
311 struct re_pattern_buffer
*bufp
;
313 int length
, start
, range
;
314 struct re_registers
*regs
;
316 return re_search_stub (bufp
, string
, length
, start
, range
, length
, regs
, 0);
319 weak_alias (__re_search
, re_search
)
323 re_match_2 (bufp
, string1
, length1
, string2
, length2
, start
, regs
, stop
)
324 struct re_pattern_buffer
*bufp
;
325 const char *string1
, *string2
;
326 int length1
, length2
, start
, stop
;
327 struct re_registers
*regs
;
329 return re_search_2_stub (bufp
, string1
, length1
, string2
, length2
,
330 start
, 0, regs
, stop
, 1);
333 weak_alias (__re_match_2
, re_match_2
)
337 re_search_2 (bufp
, string1
, length1
, string2
, length2
, start
, range
, regs
, stop
)
338 struct re_pattern_buffer
*bufp
;
339 const char *string1
, *string2
;
340 int length1
, length2
, start
, range
, stop
;
341 struct re_registers
*regs
;
343 return re_search_2_stub (bufp
, string1
, length1
, string2
, length2
,
344 start
, range
, regs
, stop
, 0);
347 weak_alias (__re_search_2
, re_search_2
)
351 re_search_2_stub (bufp
, string1
, length1
, string2
, length2
, start
, range
, regs
,
353 struct re_pattern_buffer
*bufp
;
354 const char *string1
, *string2
;
355 int length1
, length2
, start
, range
, stop
, ret_len
;
356 struct re_registers
*regs
;
360 int len
= length1
+ length2
;
363 if (BE (length1
< 0 || length2
< 0 || stop
< 0, 0))
366 /* Concatenate the strings. */
370 char *s
= re_malloc (char, len
);
372 if (BE (s
== NULL
, 0))
374 memcpy (s
, string1
, length1
);
375 memcpy (s
+ length1
, string2
, length2
);
384 rval
= re_search_stub (bufp
, str
, len
, start
, range
, stop
, regs
,
387 re_free ((char *) str
);
391 /* The parameters have the same meaning as those of re_search.
392 Additional parameters:
393 If RET_LEN is nonzero the length of the match is returned (re_match style);
394 otherwise the position of the match is returned. */
397 re_search_stub (bufp
, string
, length
, start
, range
, stop
, regs
, ret_len
)
398 struct re_pattern_buffer
*bufp
;
400 int length
, start
, range
, stop
, ret_len
;
401 struct re_registers
*regs
;
403 reg_errcode_t result
;
408 /* Check for out-of-range. */
409 if (BE (start
< 0 || start
> length
, 0))
411 if (BE (start
+ range
> length
, 0))
412 range
= length
- start
;
413 else if (BE (start
+ range
< 0, 0))
416 eflags
|= (bufp
->not_bol
) ? REG_NOTBOL
: 0;
417 eflags
|= (bufp
->not_eol
) ? REG_NOTEOL
: 0;
419 /* Compile fastmap if we haven't yet. */
420 if (range
> 0 && bufp
->fastmap
!= NULL
&& !bufp
->fastmap_accurate
)
421 re_compile_fastmap (bufp
);
423 if (BE (bufp
->no_sub
, 0))
426 /* We need at least 1 register. */
429 else if (BE (bufp
->regs_allocated
== REGS_FIXED
&&
430 regs
->num_regs
< bufp
->re_nsub
+ 1, 0))
432 nregs
= regs
->num_regs
;
433 if (BE (nregs
< 1, 0))
435 /* Nothing can be copied to regs. */
441 nregs
= bufp
->re_nsub
+ 1;
442 pmatch
= re_malloc (regmatch_t
, nregs
);
443 if (BE (pmatch
== NULL
, 0))
446 result
= re_search_internal (bufp
, string
, length
, start
, range
, stop
,
447 nregs
, pmatch
, eflags
);
451 /* I hope we needn't fill ther regs with -1's when no match was found. */
452 if (result
!= REG_NOERROR
)
454 else if (regs
!= NULL
)
456 /* If caller wants register contents data back, copy them. */
457 bufp
->regs_allocated
= re_copy_regs (regs
, pmatch
, nregs
,
458 bufp
->regs_allocated
);
459 if (BE (bufp
->regs_allocated
== REGS_UNALLOCATED
, 0))
463 if (BE (rval
== 0, 1))
467 assert (pmatch
[0].rm_so
== start
);
468 rval
= pmatch
[0].rm_eo
- start
;
471 rval
= pmatch
[0].rm_so
;
478 re_copy_regs (regs
, pmatch
, nregs
, regs_allocated
)
479 struct re_registers
*regs
;
481 int nregs
, regs_allocated
;
483 int rval
= REGS_REALLOCATE
;
485 int need_regs
= nregs
+ 1;
486 /* We need one extra element beyond `num_regs' for the `-1' marker GNU code
489 /* Have the register data arrays been allocated? */
490 if (regs_allocated
== REGS_UNALLOCATED
)
491 { /* No. So allocate them with malloc. */
492 regs
->start
= re_malloc (regoff_t
, need_regs
);
493 regs
->end
= re_malloc (regoff_t
, need_regs
);
494 if (BE (regs
->start
== NULL
, 0) || BE (regs
->end
== NULL
, 0))
495 return REGS_UNALLOCATED
;
496 regs
->num_regs
= need_regs
;
498 else if (regs_allocated
== REGS_REALLOCATE
)
499 { /* Yes. If we need more elements than were already
500 allocated, reallocate them. If we need fewer, just
502 if (BE (need_regs
> regs
->num_regs
, 0))
504 regoff_t
*new_start
= re_realloc (regs
->start
, regoff_t
, need_regs
);
505 regoff_t
*new_end
= re_realloc (regs
->end
, regoff_t
, need_regs
);
506 if (BE (new_start
== NULL
, 0) || BE (new_end
== NULL
, 0))
507 return REGS_UNALLOCATED
;
508 regs
->start
= new_start
;
510 regs
->num_regs
= need_regs
;
515 assert (regs_allocated
== REGS_FIXED
);
516 /* This function may not be called with REGS_FIXED and nregs too big. */
517 assert (regs
->num_regs
>= nregs
);
522 for (i
= 0; i
< nregs
; ++i
)
524 regs
->start
[i
] = pmatch
[i
].rm_so
;
525 regs
->end
[i
] = pmatch
[i
].rm_eo
;
527 for ( ; i
< regs
->num_regs
; ++i
)
528 regs
->start
[i
] = regs
->end
[i
] = -1;
533 /* Set REGS to hold NUM_REGS registers, storing them in STARTS and
534 ENDS. Subsequent matches using PATTERN_BUFFER and REGS will use
535 this memory for recording register information. STARTS and ENDS
536 must be allocated using the malloc library routine, and must each
537 be at least NUM_REGS * sizeof (regoff_t) bytes long.
539 If NUM_REGS == 0, then subsequent matches should allocate their own
542 Unless this function is called, the first search or match using
543 PATTERN_BUFFER will allocate its own register data, without
544 freeing the old data. */
547 re_set_registers (bufp
, regs
, num_regs
, starts
, ends
)
548 struct re_pattern_buffer
*bufp
;
549 struct re_registers
*regs
;
551 regoff_t
*starts
, *ends
;
555 bufp
->regs_allocated
= REGS_REALLOCATE
;
556 regs
->num_regs
= num_regs
;
557 regs
->start
= starts
;
562 bufp
->regs_allocated
= REGS_UNALLOCATED
;
564 regs
->start
= regs
->end
= (regoff_t
*) 0;
568 weak_alias (__re_set_registers
, re_set_registers
)
571 /* Entry points compatible with 4.2 BSD regex library. We don't define
572 them unless specifically requested. */
574 #if defined _REGEX_RE_COMP || defined _LIBC
582 return 0 == regexec (&re_comp_buf
, s
, 0, NULL
, 0);
584 #endif /* _REGEX_RE_COMP */
586 /* Internal entry point. */
588 /* Searches for a compiled pattern PREG in the string STRING, whose
589 length is LENGTH. NMATCH, PMATCH, and EFLAGS have the same
590 mingings with regexec. START, and RANGE have the same meanings
592 Return REG_NOERROR if we find a match, and REG_NOMATCH if not,
593 otherwise return the error code.
594 Note: We assume front end functions already check ranges.
595 (START + RANGE >= 0 && START + RANGE <= LENGTH) */
598 re_search_internal (preg
, string
, length
, start
, range
, stop
, nmatch
, pmatch
,
602 int length
, start
, range
, stop
, eflags
;
607 re_dfa_t
*dfa
= (re_dfa_t
*)preg
->buffer
;
608 int left_lim
, right_lim
, incr
;
609 int fl_longest_match
, match_first
, match_kind
, match_last
= -1;
611 #if defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L)
612 re_match_context_t mctx
= { .dfa
= dfa
};
614 re_match_context_t mctx
;
616 char *fastmap
= (preg
->fastmap
!= NULL
&& preg
->fastmap_accurate
617 && range
&& !preg
->can_be_null
) ? preg
->fastmap
: NULL
;
618 unsigned RE_TRANSLATE_TYPE t
= (unsigned RE_TRANSLATE_TYPE
) preg
->translate
;
620 #if !(defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L))
621 memset (&mctx
, '\0', sizeof (re_match_context_t
));
625 /* Check if the DFA haven't been compiled. */
626 if (BE (preg
->used
== 0 || dfa
->init_state
== NULL
627 || dfa
->init_state_word
== NULL
|| dfa
->init_state_nl
== NULL
628 || dfa
->init_state_begbuf
== NULL
, 0))
632 /* We assume front-end functions already check them. */
633 assert (start
+ range
>= 0 && start
+ range
<= length
);
636 /* If initial states with non-begbuf contexts have no elements,
637 the regex must be anchored. If preg->newline_anchor is set,
638 we'll never use init_state_nl, so do not check it. */
639 if (dfa
->init_state
->nodes
.nelem
== 0
640 && dfa
->init_state_word
->nodes
.nelem
== 0
641 && (dfa
->init_state_nl
->nodes
.nelem
== 0
642 || !preg
->newline_anchor
))
644 if (start
!= 0 && start
+ range
!= 0)
649 /* We must check the longest matching, if nmatch > 0. */
650 fl_longest_match
= (nmatch
!= 0 || dfa
->nbackref
);
652 err
= re_string_allocate (&mctx
.input
, string
, length
, dfa
->nodes_len
+ 1,
653 preg
->translate
, preg
->syntax
& RE_ICASE
, dfa
);
654 if (BE (err
!= REG_NOERROR
, 0))
656 mctx
.input
.stop
= stop
;
657 mctx
.input
.raw_stop
= stop
;
658 mctx
.input
.newline_anchor
= preg
->newline_anchor
;
660 err
= match_ctx_init (&mctx
, eflags
, dfa
->nbackref
* 2);
661 if (BE (err
!= REG_NOERROR
, 0))
664 /* We will log all the DFA states through which the dfa pass,
665 if nmatch > 1, or this dfa has "multibyte node", which is a
666 back-reference or a node which can accept multibyte character or
667 multi character collating element. */
668 if (nmatch
> 1 || dfa
->has_mb_node
)
670 mctx
.state_log
= re_malloc (re_dfastate_t
*, mctx
.input
.bufs_len
+ 1);
671 if (BE (mctx
.state_log
== NULL
, 0))
678 mctx
.state_log
= NULL
;
681 mctx
.input
.tip_context
= (eflags
& REG_NOTBOL
) ? CONTEXT_BEGBUF
682 : CONTEXT_NEWLINE
| CONTEXT_BEGBUF
;
684 /* Check incrementally whether of not the input string match. */
685 incr
= (range
< 0) ? -1 : 1;
686 left_lim
= (range
< 0) ? start
+ range
: start
;
687 right_lim
= (range
< 0) ? start
: start
+ range
;
688 sb
= dfa
->mb_cur_max
== 1;
691 ? ((sb
|| !(preg
->syntax
& RE_ICASE
|| t
) ? 4 : 0)
692 | (range
>= 0 ? 2 : 0)
693 | (t
!= NULL
? 1 : 0))
696 for (;; match_first
+= incr
)
699 if (match_first
< left_lim
|| right_lim
< match_first
)
702 /* Advance as rapidly as possible through the string, until we
703 find a plausible place to start matching. This may be done
704 with varying efficiency, so there are various possibilities:
705 only the most common of them are specialized, in order to
706 save on code size. We use a switch statement for speed. */
714 /* Fastmap with single-byte translation, match forward. */
715 while (BE (match_first
< right_lim
, 1)
716 && !fastmap
[t
[(unsigned char) string
[match_first
]]])
718 goto forward_match_found_start_or_reached_end
;
721 /* Fastmap without translation, match forward. */
722 while (BE (match_first
< right_lim
, 1)
723 && !fastmap
[(unsigned char) string
[match_first
]])
726 forward_match_found_start_or_reached_end
:
727 if (BE (match_first
== right_lim
, 0))
729 ch
= match_first
>= length
730 ? 0 : (unsigned char) string
[match_first
];
731 if (!fastmap
[t
? t
[ch
] : ch
])
738 /* Fastmap without multi-byte translation, match backwards. */
739 while (match_first
>= left_lim
)
741 ch
= match_first
>= length
742 ? 0 : (unsigned char) string
[match_first
];
743 if (fastmap
[t
? t
[ch
] : ch
])
747 if (match_first
< left_lim
)
752 /* In this case, we can't determine easily the current byte,
753 since it might be a component byte of a multibyte
754 character. Then we use the constructed buffer instead. */
757 /* If MATCH_FIRST is out of the valid range, reconstruct the
759 unsigned int offset
= match_first
- mctx
.input
.raw_mbs_idx
;
760 if (BE (offset
>= (unsigned int) mctx
.input
.valid_raw_len
, 0))
762 err
= re_string_reconstruct (&mctx
.input
, match_first
,
764 if (BE (err
!= REG_NOERROR
, 0))
767 offset
= match_first
- mctx
.input
.raw_mbs_idx
;
769 /* If MATCH_FIRST is out of the buffer, leave it as '\0'.
770 Note that MATCH_FIRST must not be smaller than 0. */
771 ch
= (match_first
>= length
772 ? 0 : re_string_byte_at (&mctx
.input
, offset
));
776 if (match_first
< left_lim
|| match_first
> right_lim
)
785 /* Reconstruct the buffers so that the matcher can assume that
786 the matching starts from the beginning of the buffer. */
787 err
= re_string_reconstruct (&mctx
.input
, match_first
, eflags
);
788 if (BE (err
!= REG_NOERROR
, 0))
791 #ifdef RE_ENABLE_I18N
792 /* Don't consider this char as a possible match start if it part,
793 yet isn't the head, of a multibyte character. */
794 if (!sb
&& !re_string_first_byte (&mctx
.input
, 0))
798 /* It seems to be appropriate one, then use the matcher. */
799 /* We assume that the matching starts from 0. */
800 mctx
.state_log_top
= mctx
.nbkref_ents
= mctx
.max_mb_elem_len
= 0;
801 match_last
= check_matching (&mctx
, fl_longest_match
,
802 range
>= 0 ? &match_first
: NULL
);
803 if (match_last
!= -1)
805 if (BE (match_last
== -2, 0))
812 mctx
.match_last
= match_last
;
813 if ((!preg
->no_sub
&& nmatch
> 1) || dfa
->nbackref
)
815 re_dfastate_t
*pstate
= mctx
.state_log
[match_last
];
816 mctx
.last_node
= check_halt_state_context (&mctx
, pstate
,
819 if ((!preg
->no_sub
&& nmatch
> 1 && dfa
->has_plural_match
)
822 err
= prune_impossible_nodes (&mctx
);
823 if (err
== REG_NOERROR
)
825 if (BE (err
!= REG_NOMATCH
, 0))
830 break; /* We found a match. */
834 match_ctx_clean (&mctx
);
838 assert (match_last
!= -1);
839 assert (err
== REG_NOERROR
);
842 /* Set pmatch[] if we need. */
847 /* Initialize registers. */
848 for (reg_idx
= 1; reg_idx
< nmatch
; ++reg_idx
)
849 pmatch
[reg_idx
].rm_so
= pmatch
[reg_idx
].rm_eo
= -1;
851 /* Set the points where matching start/end. */
853 pmatch
[0].rm_eo
= mctx
.match_last
;
855 if (!preg
->no_sub
&& nmatch
> 1)
857 err
= set_regs (preg
, &mctx
, nmatch
, pmatch
,
858 dfa
->has_plural_match
&& dfa
->nbackref
> 0);
859 if (BE (err
!= REG_NOERROR
, 0))
863 /* At last, add the offset to the each registers, since we slided
864 the buffers so that we could assume that the matching starts
866 for (reg_idx
= 0; reg_idx
< nmatch
; ++reg_idx
)
867 if (pmatch
[reg_idx
].rm_so
!= -1)
869 #ifdef RE_ENABLE_I18N
870 if (BE (mctx
.input
.offsets_needed
!= 0, 0))
872 if (pmatch
[reg_idx
].rm_so
== mctx
.input
.valid_len
)
873 pmatch
[reg_idx
].rm_so
+= mctx
.input
.valid_raw_len
- mctx
.input
.valid_len
;
875 pmatch
[reg_idx
].rm_so
= mctx
.input
.offsets
[pmatch
[reg_idx
].rm_so
];
876 if (pmatch
[reg_idx
].rm_eo
== mctx
.input
.valid_len
)
877 pmatch
[reg_idx
].rm_eo
+= mctx
.input
.valid_raw_len
- mctx
.input
.valid_len
;
879 pmatch
[reg_idx
].rm_eo
= mctx
.input
.offsets
[pmatch
[reg_idx
].rm_eo
];
882 assert (mctx
.input
.offsets_needed
== 0);
884 pmatch
[reg_idx
].rm_so
+= match_first
;
885 pmatch
[reg_idx
].rm_eo
+= match_first
;
890 re_free (mctx
.state_log
);
892 match_ctx_free (&mctx
);
893 re_string_destruct (&mctx
.input
);
898 prune_impossible_nodes (mctx
)
899 re_match_context_t
*mctx
;
901 re_dfa_t
*const dfa
= mctx
->dfa
;
902 int halt_node
, match_last
;
904 re_dfastate_t
**sifted_states
;
905 re_dfastate_t
**lim_states
= NULL
;
906 re_sift_context_t sctx
;
908 assert (mctx
->state_log
!= NULL
);
910 match_last
= mctx
->match_last
;
911 halt_node
= mctx
->last_node
;
912 sifted_states
= re_malloc (re_dfastate_t
*, match_last
+ 1);
913 if (BE (sifted_states
== NULL
, 0))
920 lim_states
= re_malloc (re_dfastate_t
*, match_last
+ 1);
921 if (BE (lim_states
== NULL
, 0))
928 memset (lim_states
, '\0',
929 sizeof (re_dfastate_t
*) * (match_last
+ 1));
930 sift_ctx_init (&sctx
, sifted_states
, lim_states
, halt_node
,
932 ret
= sift_states_backward (mctx
, &sctx
);
933 re_node_set_free (&sctx
.limits
);
934 if (BE (ret
!= REG_NOERROR
, 0))
936 if (sifted_states
[0] != NULL
|| lim_states
[0] != NULL
)
946 } while (mctx
->state_log
[match_last
] == NULL
947 || !mctx
->state_log
[match_last
]->halt
);
948 halt_node
= check_halt_state_context (mctx
,
949 mctx
->state_log
[match_last
],
952 ret
= merge_state_array (dfa
, sifted_states
, lim_states
,
954 re_free (lim_states
);
956 if (BE (ret
!= REG_NOERROR
, 0))
961 sift_ctx_init (&sctx
, sifted_states
, lim_states
, halt_node
, match_last
);
962 ret
= sift_states_backward (mctx
, &sctx
);
963 re_node_set_free (&sctx
.limits
);
964 if (BE (ret
!= REG_NOERROR
, 0))
967 re_free (mctx
->state_log
);
968 mctx
->state_log
= sifted_states
;
969 sifted_states
= NULL
;
970 mctx
->last_node
= halt_node
;
971 mctx
->match_last
= match_last
;
974 re_free (sifted_states
);
975 re_free (lim_states
);
979 /* Acquire an initial state and return it.
980 We must select appropriate initial state depending on the context,
981 since initial states may have constraints like "\<", "^", etc.. */
983 static inline re_dfastate_t
*
984 acquire_init_state_context (err
, mctx
, idx
)
986 const re_match_context_t
*mctx
;
989 re_dfa_t
*const dfa
= mctx
->dfa
;
990 if (dfa
->init_state
->has_constraint
)
992 unsigned int context
;
993 context
= re_string_context_at (&mctx
->input
, idx
- 1, mctx
->eflags
);
994 if (IS_WORD_CONTEXT (context
))
995 return dfa
->init_state_word
;
996 else if (IS_ORDINARY_CONTEXT (context
))
997 return dfa
->init_state
;
998 else if (IS_BEGBUF_CONTEXT (context
) && IS_NEWLINE_CONTEXT (context
))
999 return dfa
->init_state_begbuf
;
1000 else if (IS_NEWLINE_CONTEXT (context
))
1001 return dfa
->init_state_nl
;
1002 else if (IS_BEGBUF_CONTEXT (context
))
1004 /* It is relatively rare case, then calculate on demand. */
1005 return re_acquire_state_context (err
, dfa
,
1006 dfa
->init_state
->entrance_nodes
,
1010 /* Must not happen? */
1011 return dfa
->init_state
;
1014 return dfa
->init_state
;
1017 /* Check whether the regular expression match input string INPUT or not,
1018 and return the index where the matching end, return -1 if not match,
1019 or return -2 in case of an error.
1020 FL_LONGEST_MATCH means we want the POSIX longest matching.
1021 If P_MATCH_FIRST is not NULL, and the match fails, it is set to the
1022 next place where we may want to try matching.
1023 Note that the matcher assume that the maching starts from the current
1024 index of the buffer. */
1027 check_matching (mctx
, fl_longest_match
, p_match_first
)
1028 re_match_context_t
*mctx
;
1029 int fl_longest_match
;
1032 re_dfa_t
*const dfa
= mctx
->dfa
;
1035 int match_last
= -1;
1036 int cur_str_idx
= re_string_cur_idx (&mctx
->input
);
1037 re_dfastate_t
*cur_state
;
1038 int at_init_state
= p_match_first
!= NULL
;
1039 int next_start_idx
= cur_str_idx
;
1042 cur_state
= acquire_init_state_context (&err
, mctx
, cur_str_idx
);
1043 /* An initial state must not be NULL (invalid). */
1044 if (BE (cur_state
== NULL
, 0))
1046 assert (err
== REG_ESPACE
);
1050 if (mctx
->state_log
!= NULL
)
1052 mctx
->state_log
[cur_str_idx
] = cur_state
;
1054 /* Check OP_OPEN_SUBEXP in the initial state in case that we use them
1055 later. E.g. Processing back references. */
1056 if (BE (dfa
->nbackref
, 0))
1059 err
= check_subexp_matching_top (mctx
, &cur_state
->nodes
, 0);
1060 if (BE (err
!= REG_NOERROR
, 0))
1063 if (cur_state
->has_backref
)
1065 err
= transit_state_bkref (mctx
, &cur_state
->nodes
);
1066 if (BE (err
!= REG_NOERROR
, 0))
1072 /* If the RE accepts NULL string. */
1073 if (BE (cur_state
->halt
, 0))
1075 if (!cur_state
->has_constraint
1076 || check_halt_state_context (mctx
, cur_state
, cur_str_idx
))
1078 if (!fl_longest_match
)
1082 match_last
= cur_str_idx
;
1088 while (!re_string_eoi (&mctx
->input
))
1090 re_dfastate_t
*old_state
= cur_state
;
1091 int next_char_idx
= re_string_cur_idx (&mctx
->input
) + 1;
1093 if (BE (next_char_idx
>= mctx
->input
.bufs_len
, 0)
1094 || (BE (next_char_idx
>= mctx
->input
.valid_len
, 0)
1095 && mctx
->input
.valid_len
< mctx
->input
.len
))
1097 err
= extend_buffers (mctx
);
1098 if (BE (err
!= REG_NOERROR
, 0))
1100 assert (err
== REG_ESPACE
);
1105 cur_state
= transit_state (&err
, mctx
, cur_state
);
1106 if (mctx
->state_log
!= NULL
)
1107 cur_state
= merge_state_with_log (&err
, mctx
, cur_state
);
1109 if (cur_state
== NULL
)
1111 /* Reached the invalid state or an error. Try to recover a valid
1112 state using the state log, if available and if we have not
1113 already found a valid (even if not the longest) match. */
1114 if (BE (err
!= REG_NOERROR
, 0))
1117 if (mctx
->state_log
== NULL
1118 || (match
&& !fl_longest_match
)
1119 || (cur_state
= find_recover_state (&err
, mctx
)) == NULL
)
1123 if (BE (at_init_state
, 0))
1125 if (old_state
== cur_state
)
1126 next_start_idx
= next_char_idx
;
1131 if (cur_state
->halt
)
1133 /* Reached a halt state.
1134 Check the halt state can satisfy the current context. */
1135 if (!cur_state
->has_constraint
1136 || check_halt_state_context (mctx
, cur_state
,
1137 re_string_cur_idx (&mctx
->input
)))
1139 /* We found an appropriate halt state. */
1140 match_last
= re_string_cur_idx (&mctx
->input
);
1143 /* We found a match, do not modify match_first below. */
1144 p_match_first
= NULL
;
1145 if (!fl_longest_match
)
1152 *p_match_first
+= next_start_idx
;
1157 /* Check NODE match the current context. */
1159 static int check_halt_node_context (dfa
, node
, context
)
1160 const re_dfa_t
*dfa
;
1162 unsigned int context
;
1164 re_token_type_t type
= dfa
->nodes
[node
].type
;
1165 unsigned int constraint
= dfa
->nodes
[node
].constraint
;
1166 if (type
!= END_OF_RE
)
1170 if (NOT_SATISFY_NEXT_CONSTRAINT (constraint
, context
))
1175 /* Check the halt state STATE match the current context.
1176 Return 0 if not match, if the node, STATE has, is a halt node and
1177 match the context, return the node. */
1180 check_halt_state_context (mctx
, state
, idx
)
1181 const re_match_context_t
*mctx
;
1182 const re_dfastate_t
*state
;
1186 unsigned int context
;
1188 assert (state
->halt
);
1190 context
= re_string_context_at (&mctx
->input
, idx
, mctx
->eflags
);
1191 for (i
= 0; i
< state
->nodes
.nelem
; ++i
)
1192 if (check_halt_node_context (mctx
->dfa
, state
->nodes
.elems
[i
], context
))
1193 return state
->nodes
.elems
[i
];
1197 /* Compute the next node to which "NFA" transit from NODE("NFA" is a NFA
1198 corresponding to the DFA).
1199 Return the destination node, and update EPS_VIA_NODES, return -1 in case
1203 proceed_next_node (mctx
, nregs
, regs
, pidx
, node
, eps_via_nodes
, fs
)
1204 const re_match_context_t
*mctx
;
1206 int nregs
, *pidx
, node
;
1207 re_node_set
*eps_via_nodes
;
1208 struct re_fail_stack_t
*fs
;
1210 re_dfa_t
*const dfa
= mctx
->dfa
;
1211 int i
, err
, dest_node
;
1213 if (IS_EPSILON_NODE (dfa
->nodes
[node
].type
))
1215 re_node_set
*cur_nodes
= &mctx
->state_log
[*pidx
]->nodes
;
1216 int ndest
, dest_nodes
[2];
1217 err
= re_node_set_insert (eps_via_nodes
, node
);
1218 if (BE (err
< 0, 0))
1220 /* Pick up valid destinations. */
1221 for (ndest
= 0, i
= 0; i
< dfa
->edests
[node
].nelem
; ++i
)
1223 int candidate
= dfa
->edests
[node
].elems
[i
];
1224 if (!re_node_set_contains (cur_nodes
, candidate
))
1226 dest_nodes
[0] = (ndest
== 0) ? candidate
: dest_nodes
[0];
1227 dest_nodes
[1] = (ndest
== 1) ? candidate
: dest_nodes
[1];
1231 return ndest
== 0 ? -1 : (ndest
== 1 ? dest_nodes
[0] : 0);
1232 /* In order to avoid infinite loop like "(a*)*". */
1233 if (re_node_set_contains (eps_via_nodes
, dest_nodes
[0]))
1234 return dest_nodes
[1];
1236 && push_fail_stack (fs
, *pidx
, dest_nodes
, nregs
, regs
,
1239 return dest_nodes
[0];
1244 re_token_type_t type
= dfa
->nodes
[node
].type
;
1246 #ifdef RE_ENABLE_I18N
1247 if (ACCEPT_MB_NODE (type
))
1248 naccepted
= check_node_accept_bytes (dfa
, node
, &mctx
->input
, *pidx
);
1250 #endif /* RE_ENABLE_I18N */
1251 if (type
== OP_BACK_REF
)
1253 int subexp_idx
= dfa
->nodes
[node
].opr
.idx
;
1254 naccepted
= regs
[subexp_idx
].rm_eo
- regs
[subexp_idx
].rm_so
;
1257 if (regs
[subexp_idx
].rm_so
== -1 || regs
[subexp_idx
].rm_eo
== -1)
1261 char *buf
= (char *) re_string_get_buffer (&mctx
->input
);
1262 if (memcmp (buf
+ regs
[subexp_idx
].rm_so
, buf
+ *pidx
,
1270 err
= re_node_set_insert (eps_via_nodes
, node
);
1271 if (BE (err
< 0, 0))
1273 dest_node
= dfa
->edests
[node
].elems
[0];
1274 if (re_node_set_contains (&mctx
->state_log
[*pidx
]->nodes
,
1281 || check_node_accept (mctx
, dfa
->nodes
+ node
, *pidx
))
1283 dest_node
= dfa
->nexts
[node
];
1284 *pidx
= (naccepted
== 0) ? *pidx
+ 1 : *pidx
+ naccepted
;
1285 if (fs
&& (*pidx
> mctx
->match_last
|| mctx
->state_log
[*pidx
] == NULL
1286 || !re_node_set_contains (&mctx
->state_log
[*pidx
]->nodes
,
1289 re_node_set_empty (eps_via_nodes
);
1296 static reg_errcode_t
1297 push_fail_stack (fs
, str_idx
, dests
, nregs
, regs
, eps_via_nodes
)
1298 struct re_fail_stack_t
*fs
;
1299 int str_idx
, *dests
, nregs
;
1301 re_node_set
*eps_via_nodes
;
1304 int num
= fs
->num
++;
1305 if (fs
->num
== fs
->alloc
)
1307 struct re_fail_stack_ent_t
*new_array
;
1308 new_array
= realloc (fs
->stack
, (sizeof (struct re_fail_stack_ent_t
)
1310 if (new_array
== NULL
)
1313 fs
->stack
= new_array
;
1315 fs
->stack
[num
].idx
= str_idx
;
1316 fs
->stack
[num
].node
= dests
[1];
1317 fs
->stack
[num
].regs
= re_malloc (regmatch_t
, nregs
);
1318 if (fs
->stack
[num
].regs
== NULL
)
1320 memcpy (fs
->stack
[num
].regs
, regs
, sizeof (regmatch_t
) * nregs
);
1321 err
= re_node_set_init_copy (&fs
->stack
[num
].eps_via_nodes
, eps_via_nodes
);
1326 pop_fail_stack (fs
, pidx
, nregs
, regs
, eps_via_nodes
)
1327 struct re_fail_stack_t
*fs
;
1330 re_node_set
*eps_via_nodes
;
1332 int num
= --fs
->num
;
1334 *pidx
= fs
->stack
[num
].idx
;
1335 memcpy (regs
, fs
->stack
[num
].regs
, sizeof (regmatch_t
) * nregs
);
1336 re_node_set_free (eps_via_nodes
);
1337 re_free (fs
->stack
[num
].regs
);
1338 *eps_via_nodes
= fs
->stack
[num
].eps_via_nodes
;
1339 return fs
->stack
[num
].node
;
1342 /* Set the positions where the subexpressions are starts/ends to registers
1344 Note: We assume that pmatch[0] is already set, and
1345 pmatch[i].rm_so == pmatch[i].rm_eo == -1 for 0 < i < nmatch. */
1347 static reg_errcode_t
1348 set_regs (preg
, mctx
, nmatch
, pmatch
, fl_backtrack
)
1349 const regex_t
*preg
;
1350 const re_match_context_t
*mctx
;
1355 re_dfa_t
*dfa
= (re_dfa_t
*) preg
->buffer
;
1356 int idx
, cur_node
, real_nmatch
;
1357 re_node_set eps_via_nodes
;
1358 struct re_fail_stack_t
*fs
;
1359 struct re_fail_stack_t fs_body
= { 0, 2, NULL
};
1360 regmatch_t
*prev_idx_match
;
1363 assert (nmatch
> 1);
1364 assert (mctx
->state_log
!= NULL
);
1369 fs
->stack
= re_malloc (struct re_fail_stack_ent_t
, fs
->alloc
);
1370 if (fs
->stack
== NULL
)
1376 cur_node
= dfa
->init_node
;
1377 real_nmatch
= (nmatch
<= preg
->re_nsub
) ? nmatch
: preg
->re_nsub
+ 1;
1378 re_node_set_init_empty (&eps_via_nodes
);
1380 prev_idx_match
= (regmatch_t
*) alloca (sizeof (regmatch_t
) * real_nmatch
);
1381 memcpy (prev_idx_match
, pmatch
, sizeof (regmatch_t
) * real_nmatch
);
1383 for (idx
= pmatch
[0].rm_so
; idx
<= pmatch
[0].rm_eo
;)
1385 update_regs (dfa
, pmatch
, prev_idx_match
, cur_node
, idx
, real_nmatch
);
1387 if (idx
== pmatch
[0].rm_eo
&& cur_node
== mctx
->last_node
)
1392 for (reg_idx
= 0; reg_idx
< nmatch
; ++reg_idx
)
1393 if (pmatch
[reg_idx
].rm_so
> -1 && pmatch
[reg_idx
].rm_eo
== -1)
1395 if (reg_idx
== nmatch
)
1397 re_node_set_free (&eps_via_nodes
);
1398 return free_fail_stack_return (fs
);
1400 cur_node
= pop_fail_stack (fs
, &idx
, nmatch
, pmatch
,
1405 re_node_set_free (&eps_via_nodes
);
1410 /* Proceed to next node. */
1411 cur_node
= proceed_next_node (mctx
, nmatch
, pmatch
, &idx
, cur_node
,
1412 &eps_via_nodes
, fs
);
1414 if (BE (cur_node
< 0, 0))
1416 if (BE (cur_node
== -2, 0))
1418 re_node_set_free (&eps_via_nodes
);
1419 free_fail_stack_return (fs
);
1423 cur_node
= pop_fail_stack (fs
, &idx
, nmatch
, pmatch
,
1427 re_node_set_free (&eps_via_nodes
);
1432 re_node_set_free (&eps_via_nodes
);
1433 return free_fail_stack_return (fs
);
1436 static reg_errcode_t
1437 free_fail_stack_return (fs
)
1438 struct re_fail_stack_t
*fs
;
1443 for (fs_idx
= 0; fs_idx
< fs
->num
; ++fs_idx
)
1445 re_node_set_free (&fs
->stack
[fs_idx
].eps_via_nodes
);
1446 re_free (fs
->stack
[fs_idx
].regs
);
1448 re_free (fs
->stack
);
1454 update_regs (dfa
, pmatch
, prev_idx_match
, cur_node
, cur_idx
, nmatch
)
1456 regmatch_t
*pmatch
, *prev_idx_match
;
1457 int cur_node
, cur_idx
, nmatch
;
1459 int type
= dfa
->nodes
[cur_node
].type
;
1460 if (type
== OP_OPEN_SUBEXP
)
1462 int reg_num
= dfa
->nodes
[cur_node
].opr
.idx
+ 1;
1464 /* We are at the first node of this sub expression. */
1465 if (reg_num
< nmatch
)
1467 pmatch
[reg_num
].rm_so
= cur_idx
;
1468 pmatch
[reg_num
].rm_eo
= -1;
1471 else if (type
== OP_CLOSE_SUBEXP
)
1473 int reg_num
= dfa
->nodes
[cur_node
].opr
.idx
+ 1;
1474 if (reg_num
< nmatch
)
1476 /* We are at the last node of this sub expression. */
1477 if (pmatch
[reg_num
].rm_so
< cur_idx
)
1479 pmatch
[reg_num
].rm_eo
= cur_idx
;
1480 /* This is a non-empty match or we are not inside an optional
1481 subexpression. Accept this right away. */
1482 memcpy (prev_idx_match
, pmatch
, sizeof (regmatch_t
) * nmatch
);
1486 if (dfa
->nodes
[cur_node
].opt_subexp
1487 && prev_idx_match
[reg_num
].rm_so
!= -1)
1488 /* We transited through an empty match for an optional
1489 subexpression, like (a?)*, and this is not the subexp's
1490 first match. Copy back the old content of the registers
1491 so that matches of an inner subexpression are undone as
1492 well, like in ((a?))*. */
1493 memcpy (pmatch
, prev_idx_match
, sizeof (regmatch_t
) * nmatch
);
1495 /* We completed a subexpression, but it may be part of
1496 an optional one, so do not update PREV_IDX_MATCH. */
1497 pmatch
[reg_num
].rm_eo
= cur_idx
;
1503 /* This function checks the STATE_LOG from the SCTX->last_str_idx to 0
1504 and sift the nodes in each states according to the following rules.
1505 Updated state_log will be wrote to STATE_LOG.
1507 Rules: We throw away the Node `a' in the STATE_LOG[STR_IDX] if...
1508 1. When STR_IDX == MATCH_LAST(the last index in the state_log):
1509 If `a' isn't the LAST_NODE and `a' can't epsilon transit to
1510 the LAST_NODE, we throw away the node `a'.
1511 2. When 0 <= STR_IDX < MATCH_LAST and `a' accepts
1512 string `s' and transit to `b':
1513 i. If 'b' isn't in the STATE_LOG[STR_IDX+strlen('s')], we throw
1515 ii. If 'b' is in the STATE_LOG[STR_IDX+strlen('s')] but 'b' is
1516 thrown away, we throw away the node `a'.
1517 3. When 0 <= STR_IDX < MATCH_LAST and 'a' epsilon transit to 'b':
1518 i. If 'b' isn't in the STATE_LOG[STR_IDX], we throw away the
1520 ii. If 'b' is in the STATE_LOG[STR_IDX] but 'b' is thrown away,
1521 we throw away the node `a'. */
1523 #define STATE_NODE_CONTAINS(state,node) \
1524 ((state) != NULL && re_node_set_contains (&(state)->nodes, node))
1526 static reg_errcode_t
1527 sift_states_backward (mctx
, sctx
)
1528 re_match_context_t
*mctx
;
1529 re_sift_context_t
*sctx
;
1533 int str_idx
= sctx
->last_str_idx
;
1534 re_node_set cur_dest
;
1537 assert (mctx
->state_log
!= NULL
&& mctx
->state_log
[str_idx
] != NULL
);
1540 /* Build sifted state_log[str_idx]. It has the nodes which can epsilon
1541 transit to the last_node and the last_node itself. */
1542 err
= re_node_set_init_1 (&cur_dest
, sctx
->last_node
);
1543 if (BE (err
!= REG_NOERROR
, 0))
1545 err
= update_cur_sifted_state (mctx
, sctx
, str_idx
, &cur_dest
);
1546 if (BE (err
!= REG_NOERROR
, 0))
1549 /* Then check each states in the state_log. */
1552 /* Update counters. */
1553 null_cnt
= (sctx
->sifted_states
[str_idx
] == NULL
) ? null_cnt
+ 1 : 0;
1554 if (null_cnt
> mctx
->max_mb_elem_len
)
1556 memset (sctx
->sifted_states
, '\0',
1557 sizeof (re_dfastate_t
*) * str_idx
);
1558 re_node_set_free (&cur_dest
);
1561 re_node_set_empty (&cur_dest
);
1564 if (mctx
->state_log
[str_idx
])
1566 err
= build_sifted_states (mctx
, sctx
, str_idx
, &cur_dest
);
1567 if (BE (err
!= REG_NOERROR
, 0))
1571 /* Add all the nodes which satisfy the following conditions:
1572 - It can epsilon transit to a node in CUR_DEST.
1574 And update state_log. */
1575 err
= update_cur_sifted_state (mctx
, sctx
, str_idx
, &cur_dest
);
1576 if (BE (err
!= REG_NOERROR
, 0))
1581 re_node_set_free (&cur_dest
);
1585 static reg_errcode_t
1586 build_sifted_states (mctx
, sctx
, str_idx
, cur_dest
)
1587 re_match_context_t
*mctx
;
1588 re_sift_context_t
*sctx
;
1590 re_node_set
*cur_dest
;
1592 re_dfa_t
*const dfa
= mctx
->dfa
;
1593 re_node_set
*cur_src
= &mctx
->state_log
[str_idx
]->nodes
;
1596 /* Then build the next sifted state.
1597 We build the next sifted state on `cur_dest', and update
1598 `sifted_states[str_idx]' with `cur_dest'.
1600 `cur_dest' is the sifted state from `state_log[str_idx + 1]'.
1601 `cur_src' points the node_set of the old `state_log[str_idx]'. */
1602 for (i
= 0; i
< cur_src
->nelem
; i
++)
1604 int prev_node
= cur_src
->elems
[i
];
1606 re_token_type_t type
= dfa
->nodes
[prev_node
].type
;
1609 if (IS_EPSILON_NODE (type
))
1611 #ifdef RE_ENABLE_I18N
1612 /* If the node may accept `multi byte'. */
1613 if (ACCEPT_MB_NODE (type
))
1614 naccepted
= sift_states_iter_mb (mctx
, sctx
, prev_node
,
1615 str_idx
, sctx
->last_str_idx
);
1616 #endif /* RE_ENABLE_I18N */
1618 /* We don't check backreferences here.
1619 See update_cur_sifted_state(). */
1621 && check_node_accept (mctx
, dfa
->nodes
+ prev_node
, str_idx
)
1622 && STATE_NODE_CONTAINS (sctx
->sifted_states
[str_idx
+ 1],
1623 dfa
->nexts
[prev_node
]))
1629 if (sctx
->limits
.nelem
)
1631 int to_idx
= str_idx
+ naccepted
;
1632 if (check_dst_limits (mctx
, &sctx
->limits
,
1633 dfa
->nexts
[prev_node
], to_idx
,
1634 prev_node
, str_idx
))
1637 ret
= re_node_set_insert (cur_dest
, prev_node
);
1638 if (BE (ret
== -1, 0))
1645 /* Helper functions. */
1647 static reg_errcode_t
1648 clean_state_log_if_needed (mctx
, next_state_log_idx
)
1649 re_match_context_t
*mctx
;
1650 int next_state_log_idx
;
1652 int top
= mctx
->state_log_top
;
1654 if (next_state_log_idx
>= mctx
->input
.bufs_len
1655 || (next_state_log_idx
>= mctx
->input
.valid_len
1656 && mctx
->input
.valid_len
< mctx
->input
.len
))
1659 err
= extend_buffers (mctx
);
1660 if (BE (err
!= REG_NOERROR
, 0))
1664 if (top
< next_state_log_idx
)
1666 memset (mctx
->state_log
+ top
+ 1, '\0',
1667 sizeof (re_dfastate_t
*) * (next_state_log_idx
- top
));
1668 mctx
->state_log_top
= next_state_log_idx
;
1673 static reg_errcode_t
1674 merge_state_array (dfa
, dst
, src
, num
)
1676 re_dfastate_t
**dst
;
1677 re_dfastate_t
**src
;
1682 for (st_idx
= 0; st_idx
< num
; ++st_idx
)
1684 if (dst
[st_idx
] == NULL
)
1685 dst
[st_idx
] = src
[st_idx
];
1686 else if (src
[st_idx
] != NULL
)
1688 re_node_set merged_set
;
1689 err
= re_node_set_init_union (&merged_set
, &dst
[st_idx
]->nodes
,
1690 &src
[st_idx
]->nodes
);
1691 if (BE (err
!= REG_NOERROR
, 0))
1693 dst
[st_idx
] = re_acquire_state (&err
, dfa
, &merged_set
);
1694 re_node_set_free (&merged_set
);
1695 if (BE (err
!= REG_NOERROR
, 0))
1702 static reg_errcode_t
1703 update_cur_sifted_state (mctx
, sctx
, str_idx
, dest_nodes
)
1704 re_match_context_t
*mctx
;
1705 re_sift_context_t
*sctx
;
1707 re_node_set
*dest_nodes
;
1709 re_dfa_t
*const dfa
= mctx
->dfa
;
1711 const re_node_set
*candidates
;
1712 candidates
= ((mctx
->state_log
[str_idx
] == NULL
) ? NULL
1713 : &mctx
->state_log
[str_idx
]->nodes
);
1715 if (dest_nodes
->nelem
== 0)
1716 sctx
->sifted_states
[str_idx
] = NULL
;
1721 /* At first, add the nodes which can epsilon transit to a node in
1723 err
= add_epsilon_src_nodes (dfa
, dest_nodes
, candidates
);
1724 if (BE (err
!= REG_NOERROR
, 0))
1727 /* Then, check the limitations in the current sift_context. */
1728 if (sctx
->limits
.nelem
)
1730 err
= check_subexp_limits (dfa
, dest_nodes
, candidates
, &sctx
->limits
,
1731 mctx
->bkref_ents
, str_idx
);
1732 if (BE (err
!= REG_NOERROR
, 0))
1737 sctx
->sifted_states
[str_idx
] = re_acquire_state (&err
, dfa
, dest_nodes
);
1738 if (BE (err
!= REG_NOERROR
, 0))
1742 if (candidates
&& mctx
->state_log
[str_idx
]->has_backref
)
1744 err
= sift_states_bkref (mctx
, sctx
, str_idx
, candidates
);
1745 if (BE (err
!= REG_NOERROR
, 0))
1751 static reg_errcode_t
1752 add_epsilon_src_nodes (dfa
, dest_nodes
, candidates
)
1754 re_node_set
*dest_nodes
;
1755 const re_node_set
*candidates
;
1759 re_node_set src_copy
;
1761 err
= re_node_set_init_copy (&src_copy
, dest_nodes
);
1762 if (BE (err
!= REG_NOERROR
, 0))
1764 for (src_idx
= 0; src_idx
< src_copy
.nelem
; ++src_idx
)
1766 err
= re_node_set_add_intersect (dest_nodes
, candidates
,
1768 + src_copy
.elems
[src_idx
]);
1769 if (BE (err
!= REG_NOERROR
, 0))
1771 re_node_set_free (&src_copy
);
1775 re_node_set_free (&src_copy
);
1779 static reg_errcode_t
1780 sub_epsilon_src_nodes (dfa
, node
, dest_nodes
, candidates
)
1783 re_node_set
*dest_nodes
;
1784 const re_node_set
*candidates
;
1788 re_node_set
*inv_eclosure
= dfa
->inveclosures
+ node
;
1789 re_node_set except_nodes
;
1790 re_node_set_init_empty (&except_nodes
);
1791 for (ecl_idx
= 0; ecl_idx
< inv_eclosure
->nelem
; ++ecl_idx
)
1793 int cur_node
= inv_eclosure
->elems
[ecl_idx
];
1794 if (cur_node
== node
)
1796 if (IS_EPSILON_NODE (dfa
->nodes
[cur_node
].type
))
1798 int edst1
= dfa
->edests
[cur_node
].elems
[0];
1799 int edst2
= ((dfa
->edests
[cur_node
].nelem
> 1)
1800 ? dfa
->edests
[cur_node
].elems
[1] : -1);
1801 if ((!re_node_set_contains (inv_eclosure
, edst1
)
1802 && re_node_set_contains (dest_nodes
, edst1
))
1804 && !re_node_set_contains (inv_eclosure
, edst2
)
1805 && re_node_set_contains (dest_nodes
, edst2
)))
1807 err
= re_node_set_add_intersect (&except_nodes
, candidates
,
1808 dfa
->inveclosures
+ cur_node
);
1809 if (BE (err
!= REG_NOERROR
, 0))
1811 re_node_set_free (&except_nodes
);
1817 for (ecl_idx
= 0; ecl_idx
< inv_eclosure
->nelem
; ++ecl_idx
)
1819 int cur_node
= inv_eclosure
->elems
[ecl_idx
];
1820 if (!re_node_set_contains (&except_nodes
, cur_node
))
1822 int idx
= re_node_set_contains (dest_nodes
, cur_node
) - 1;
1823 re_node_set_remove_at (dest_nodes
, idx
);
1826 re_node_set_free (&except_nodes
);
1831 check_dst_limits (mctx
, limits
, dst_node
, dst_idx
, src_node
, src_idx
)
1832 re_match_context_t
*mctx
;
1833 re_node_set
*limits
;
1834 int dst_node
, dst_idx
, src_node
, src_idx
;
1836 re_dfa_t
*const dfa
= mctx
->dfa
;
1837 int lim_idx
, src_pos
, dst_pos
;
1839 int dst_bkref_idx
= search_cur_bkref_entry (mctx
, dst_idx
);
1840 int src_bkref_idx
= search_cur_bkref_entry (mctx
, src_idx
);
1841 for (lim_idx
= 0; lim_idx
< limits
->nelem
; ++lim_idx
)
1844 struct re_backref_cache_entry
*ent
;
1845 ent
= mctx
->bkref_ents
+ limits
->elems
[lim_idx
];
1846 subexp_idx
= dfa
->nodes
[ent
->node
].opr
.idx
- 1;
1848 dst_pos
= check_dst_limits_calc_pos (mctx
, limits
->elems
[lim_idx
],
1849 subexp_idx
, dst_node
, dst_idx
,
1851 src_pos
= check_dst_limits_calc_pos (mctx
, limits
->elems
[lim_idx
],
1852 subexp_idx
, src_node
, src_idx
,
1856 <src> <dst> ( <subexp> )
1857 ( <subexp> ) <src> <dst>
1858 ( <subexp1> <src> <subexp2> <dst> <subexp3> ) */
1859 if (src_pos
== dst_pos
)
1860 continue; /* This is unrelated limitation. */
1868 check_dst_limits_calc_pos_1 (mctx
, boundaries
, subexp_idx
, from_node
, bkref_idx
)
1869 re_match_context_t
*mctx
;
1870 int boundaries
, subexp_idx
, from_node
, bkref_idx
;
1872 re_dfa_t
*const dfa
= mctx
->dfa
;
1873 re_node_set
*eclosures
= dfa
->eclosures
+ from_node
;
1876 /* Else, we are on the boundary: examine the nodes on the epsilon
1878 for (node_idx
= 0; node_idx
< eclosures
->nelem
; ++node_idx
)
1880 int node
= eclosures
->elems
[node_idx
];
1881 switch (dfa
->nodes
[node
].type
)
1885 struct re_backref_cache_entry
*ent
= mctx
->bkref_ents
+ bkref_idx
;
1890 if (ent
->node
!= node
|| ent
->subexp_from
!= ent
->subexp_to
)
1893 /* Recurse trying to reach the OP_OPEN_SUBEXP and
1894 OP_CLOSE_SUBEXP cases below. But, if the
1895 destination node is the same node as the source
1896 node, don't recurse because it would cause an
1897 infinite loop: a regex that exhibits this behavior
1899 dst
= dfa
->edests
[node
].elems
[0];
1900 if (dst
== from_node
)
1904 else /* if (boundaries & 2) */
1908 cpos
= check_dst_limits_calc_pos_1 (mctx
, boundaries
,
1909 subexp_idx
, dst
, bkref_idx
);
1911 if (cpos
== -1 && (boundaries
& 1))
1914 if (cpos
== 0 /* && (boundaries & 2) */)
1917 while (ent
++->more
);
1921 case OP_OPEN_SUBEXP
:
1922 if ((boundaries
& 1) && subexp_idx
== dfa
->nodes
[node
].opr
.idx
)
1926 case OP_CLOSE_SUBEXP
:
1927 if ((boundaries
& 2) && subexp_idx
== dfa
->nodes
[node
].opr
.idx
)
1936 return (boundaries
& 2) ? 1 : 0;
1940 check_dst_limits_calc_pos (mctx
, limit
, subexp_idx
, from_node
, str_idx
, bkref_idx
)
1941 re_match_context_t
*mctx
;
1942 int limit
, subexp_idx
, from_node
, str_idx
, bkref_idx
;
1944 struct re_backref_cache_entry
*lim
= mctx
->bkref_ents
+ limit
;
1947 /* If we are outside the range of the subexpression, return -1 or 1. */
1948 if (str_idx
< lim
->subexp_from
)
1951 if (lim
->subexp_to
< str_idx
)
1954 /* If we are within the subexpression, return 0. */
1955 boundaries
= (str_idx
== lim
->subexp_from
);
1956 boundaries
|= (str_idx
== lim
->subexp_to
) << 1;
1957 if (boundaries
== 0)
1960 /* Else, examine epsilon closure. */
1961 return check_dst_limits_calc_pos_1 (mctx
, boundaries
, subexp_idx
,
1962 from_node
, bkref_idx
);
1965 /* Check the limitations of sub expressions LIMITS, and remove the nodes
1966 which are against limitations from DEST_NODES. */
1968 static reg_errcode_t
1969 check_subexp_limits (dfa
, dest_nodes
, candidates
, limits
, bkref_ents
, str_idx
)
1971 re_node_set
*dest_nodes
;
1972 const re_node_set
*candidates
;
1973 re_node_set
*limits
;
1974 struct re_backref_cache_entry
*bkref_ents
;
1978 int node_idx
, lim_idx
;
1980 for (lim_idx
= 0; lim_idx
< limits
->nelem
; ++lim_idx
)
1983 struct re_backref_cache_entry
*ent
;
1984 ent
= bkref_ents
+ limits
->elems
[lim_idx
];
1986 if (str_idx
<= ent
->subexp_from
|| ent
->str_idx
< str_idx
)
1987 continue; /* This is unrelated limitation. */
1989 subexp_idx
= dfa
->nodes
[ent
->node
].opr
.idx
- 1;
1990 if (ent
->subexp_to
== str_idx
)
1994 for (node_idx
= 0; node_idx
< dest_nodes
->nelem
; ++node_idx
)
1996 int node
= dest_nodes
->elems
[node_idx
];
1997 re_token_type_t type
= dfa
->nodes
[node
].type
;
1998 if (type
== OP_OPEN_SUBEXP
1999 && subexp_idx
== dfa
->nodes
[node
].opr
.idx
)
2001 else if (type
== OP_CLOSE_SUBEXP
2002 && subexp_idx
== dfa
->nodes
[node
].opr
.idx
)
2006 /* Check the limitation of the open subexpression. */
2007 /* Note that (ent->subexp_to = str_idx != ent->subexp_from). */
2010 err
= sub_epsilon_src_nodes (dfa
, ops_node
, dest_nodes
,
2012 if (BE (err
!= REG_NOERROR
, 0))
2016 /* Check the limitation of the close subexpression. */
2018 for (node_idx
= 0; node_idx
< dest_nodes
->nelem
; ++node_idx
)
2020 int node
= dest_nodes
->elems
[node_idx
];
2021 if (!re_node_set_contains (dfa
->inveclosures
+ node
,
2023 && !re_node_set_contains (dfa
->eclosures
+ node
,
2026 /* It is against this limitation.
2027 Remove it form the current sifted state. */
2028 err
= sub_epsilon_src_nodes (dfa
, node
, dest_nodes
,
2030 if (BE (err
!= REG_NOERROR
, 0))
2036 else /* (ent->subexp_to != str_idx) */
2038 for (node_idx
= 0; node_idx
< dest_nodes
->nelem
; ++node_idx
)
2040 int node
= dest_nodes
->elems
[node_idx
];
2041 re_token_type_t type
= dfa
->nodes
[node
].type
;
2042 if (type
== OP_CLOSE_SUBEXP
|| type
== OP_OPEN_SUBEXP
)
2044 if (subexp_idx
!= dfa
->nodes
[node
].opr
.idx
)
2046 if ((type
== OP_CLOSE_SUBEXP
&& ent
->subexp_to
!= str_idx
)
2047 || (type
== OP_OPEN_SUBEXP
))
2049 /* It is against this limitation.
2050 Remove it form the current sifted state. */
2051 err
= sub_epsilon_src_nodes (dfa
, node
, dest_nodes
,
2053 if (BE (err
!= REG_NOERROR
, 0))
2063 static reg_errcode_t
2064 sift_states_bkref (mctx
, sctx
, str_idx
, candidates
)
2065 re_match_context_t
*mctx
;
2066 re_sift_context_t
*sctx
;
2068 const re_node_set
*candidates
;
2070 re_dfa_t
*const dfa
= mctx
->dfa
;
2073 re_sift_context_t local_sctx
;
2074 int first_idx
= search_cur_bkref_entry (mctx
, str_idx
);
2076 if (first_idx
== -1)
2079 local_sctx
.sifted_states
= NULL
; /* Mark that it hasn't been initialized. */
2081 for (node_idx
= 0; node_idx
< candidates
->nelem
; ++node_idx
)
2084 re_token_type_t type
;
2085 struct re_backref_cache_entry
*entry
;
2086 node
= candidates
->elems
[node_idx
];
2087 type
= dfa
->nodes
[node
].type
;
2088 /* Avoid infinite loop for the REs like "()\1+". */
2089 if (node
== sctx
->last_node
&& str_idx
== sctx
->last_str_idx
)
2091 if (type
!= OP_BACK_REF
)
2094 entry
= mctx
->bkref_ents
+ first_idx
;
2095 enabled_idx
= first_idx
;
2098 int subexp_len
, to_idx
, dst_node
;
2099 re_dfastate_t
*cur_state
;
2101 if (entry
->node
!= node
)
2103 subexp_len
= entry
->subexp_to
- entry
->subexp_from
;
2104 to_idx
= str_idx
+ subexp_len
;
2105 dst_node
= (subexp_len
? dfa
->nexts
[node
]
2106 : dfa
->edests
[node
].elems
[0]);
2108 if (to_idx
> sctx
->last_str_idx
2109 || sctx
->sifted_states
[to_idx
] == NULL
2110 || !STATE_NODE_CONTAINS (sctx
->sifted_states
[to_idx
], dst_node
)
2111 || check_dst_limits (mctx
, &sctx
->limits
, node
,
2112 str_idx
, dst_node
, to_idx
))
2115 if (local_sctx
.sifted_states
== NULL
)
2118 err
= re_node_set_init_copy (&local_sctx
.limits
, &sctx
->limits
);
2119 if (BE (err
!= REG_NOERROR
, 0))
2122 local_sctx
.last_node
= node
;
2123 local_sctx
.last_str_idx
= str_idx
;
2124 err
= re_node_set_insert (&local_sctx
.limits
, enabled_idx
);
2125 if (BE (err
< 0, 0))
2130 cur_state
= local_sctx
.sifted_states
[str_idx
];
2131 err
= sift_states_backward (mctx
, &local_sctx
);
2132 if (BE (err
!= REG_NOERROR
, 0))
2134 if (sctx
->limited_states
!= NULL
)
2136 err
= merge_state_array (dfa
, sctx
->limited_states
,
2137 local_sctx
.sifted_states
,
2139 if (BE (err
!= REG_NOERROR
, 0))
2142 local_sctx
.sifted_states
[str_idx
] = cur_state
;
2143 re_node_set_remove (&local_sctx
.limits
, enabled_idx
);
2145 /* mctx->bkref_ents may have changed, reload the pointer. */
2146 entry
= mctx
->bkref_ents
+ enabled_idx
;
2148 while (enabled_idx
++, entry
++->more
);
2152 if (local_sctx
.sifted_states
!= NULL
)
2154 re_node_set_free (&local_sctx
.limits
);
2161 #ifdef RE_ENABLE_I18N
2163 sift_states_iter_mb (mctx
, sctx
, node_idx
, str_idx
, max_str_idx
)
2164 const re_match_context_t
*mctx
;
2165 re_sift_context_t
*sctx
;
2166 int node_idx
, str_idx
, max_str_idx
;
2168 re_dfa_t
*const dfa
= mctx
->dfa
;
2170 /* Check the node can accept `multi byte'. */
2171 naccepted
= check_node_accept_bytes (dfa
, node_idx
, &mctx
->input
, str_idx
);
2172 if (naccepted
> 0 && str_idx
+ naccepted
<= max_str_idx
&&
2173 !STATE_NODE_CONTAINS (sctx
->sifted_states
[str_idx
+ naccepted
],
2174 dfa
->nexts
[node_idx
]))
2175 /* The node can't accept the `multi byte', or the
2176 destination was already thrown away, then the node
2177 could't accept the current input `multi byte'. */
2179 /* Otherwise, it is sure that the node could accept
2180 `naccepted' bytes input. */
2183 #endif /* RE_ENABLE_I18N */
2186 /* Functions for state transition. */
2188 /* Return the next state to which the current state STATE will transit by
2189 accepting the current input byte, and update STATE_LOG if necessary.
2190 If STATE can accept a multibyte char/collating element/back reference
2191 update the destination of STATE_LOG. */
2193 static re_dfastate_t
*
2194 transit_state (err
, mctx
, state
)
2196 re_match_context_t
*mctx
;
2197 re_dfastate_t
*state
;
2199 re_dfa_t
*const dfa
= mctx
->dfa
;
2200 re_dfastate_t
**trtable
;
2203 #ifdef RE_ENABLE_I18N
2204 /* If the current state can accept multibyte. */
2205 if (BE (state
->accept_mb
, 0))
2207 *err
= transit_state_mb (mctx
, state
);
2208 if (BE (*err
!= REG_NOERROR
, 0))
2211 #endif /* RE_ENABLE_I18N */
2213 /* Then decide the next state with the single byte. */
2216 /* Use transition table */
2217 ch
= re_string_fetch_byte (&mctx
->input
);
2218 trtable
= state
->trtable
;
2219 if (trtable
== NULL
)
2221 trtable
= build_trtable (dfa
, state
);
2222 if (trtable
== NULL
)
2228 if (BE (state
->word_trtable
, 0))
2230 unsigned int context
;
2232 = re_string_context_at (&mctx
->input
,
2233 re_string_cur_idx (&mctx
->input
) - 1,
2235 if (IS_WORD_CONTEXT (context
))
2236 return trtable
[ch
+ SBC_MAX
];
2245 /* don't use transition table */
2246 return transit_state_sb (err
, mctx
, state
);
2250 /* Update the state_log if we need */
2252 merge_state_with_log (err
, mctx
, next_state
)
2254 re_match_context_t
*mctx
;
2255 re_dfastate_t
*next_state
;
2257 re_dfa_t
*const dfa
= mctx
->dfa
;
2258 int cur_idx
= re_string_cur_idx (&mctx
->input
);
2260 if (cur_idx
> mctx
->state_log_top
)
2262 mctx
->state_log
[cur_idx
] = next_state
;
2263 mctx
->state_log_top
= cur_idx
;
2265 else if (mctx
->state_log
[cur_idx
] == 0)
2267 mctx
->state_log
[cur_idx
] = next_state
;
2271 re_dfastate_t
*pstate
;
2272 unsigned int context
;
2273 re_node_set next_nodes
, *log_nodes
, *table_nodes
= NULL
;
2274 /* If (state_log[cur_idx] != 0), it implies that cur_idx is
2275 the destination of a multibyte char/collating element/
2276 back reference. Then the next state is the union set of
2277 these destinations and the results of the transition table. */
2278 pstate
= mctx
->state_log
[cur_idx
];
2279 log_nodes
= pstate
->entrance_nodes
;
2280 if (next_state
!= NULL
)
2282 table_nodes
= next_state
->entrance_nodes
;
2283 *err
= re_node_set_init_union (&next_nodes
, table_nodes
,
2285 if (BE (*err
!= REG_NOERROR
, 0))
2289 next_nodes
= *log_nodes
;
2290 /* Note: We already add the nodes of the initial state,
2291 then we don't need to add them here. */
2293 context
= re_string_context_at (&mctx
->input
,
2294 re_string_cur_idx (&mctx
->input
) - 1,
2296 next_state
= mctx
->state_log
[cur_idx
]
2297 = re_acquire_state_context (err
, dfa
, &next_nodes
, context
);
2298 /* We don't need to check errors here, since the return value of
2299 this function is next_state and ERR is already set. */
2301 if (table_nodes
!= NULL
)
2302 re_node_set_free (&next_nodes
);
2305 if (BE (dfa
->nbackref
, 0) && next_state
!= NULL
)
2307 /* Check OP_OPEN_SUBEXP in the current state in case that we use them
2308 later. We must check them here, since the back references in the
2309 next state might use them. */
2310 *err
= check_subexp_matching_top (mctx
, &next_state
->nodes
,
2312 if (BE (*err
!= REG_NOERROR
, 0))
2315 /* If the next state has back references. */
2316 if (next_state
->has_backref
)
2318 *err
= transit_state_bkref (mctx
, &next_state
->nodes
);
2319 if (BE (*err
!= REG_NOERROR
, 0))
2321 next_state
= mctx
->state_log
[cur_idx
];
2328 /* Skip bytes in the input that correspond to part of a
2329 multi-byte match, then look in the log for a state
2330 from which to restart matching. */
2332 find_recover_state (err
, mctx
)
2334 re_match_context_t
*mctx
;
2336 re_dfastate_t
*cur_state
= NULL
;
2339 int max
= mctx
->state_log_top
;
2340 int cur_str_idx
= re_string_cur_idx (&mctx
->input
);
2344 if (++cur_str_idx
> max
)
2346 re_string_skip_bytes (&mctx
->input
, 1);
2348 while (mctx
->state_log
[cur_str_idx
] == NULL
);
2350 cur_state
= merge_state_with_log (err
, mctx
, NULL
);
2352 while (err
== REG_NOERROR
&& cur_state
== NULL
);
2356 /* Helper functions for transit_state. */
2358 /* From the node set CUR_NODES, pick up the nodes whose types are
2359 OP_OPEN_SUBEXP and which have corresponding back references in the regular
2360 expression. And register them to use them later for evaluating the
2361 correspoding back references. */
2363 static reg_errcode_t
2364 check_subexp_matching_top (mctx
, cur_nodes
, str_idx
)
2365 re_match_context_t
*mctx
;
2366 re_node_set
*cur_nodes
;
2369 re_dfa_t
*const dfa
= mctx
->dfa
;
2373 /* TODO: This isn't efficient.
2374 Because there might be more than one nodes whose types are
2375 OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
2378 for (node_idx
= 0; node_idx
< cur_nodes
->nelem
; ++node_idx
)
2380 int node
= cur_nodes
->elems
[node_idx
];
2381 if (dfa
->nodes
[node
].type
== OP_OPEN_SUBEXP
2382 && dfa
->nodes
[node
].opr
.idx
< (8 * sizeof (dfa
->used_bkref_map
))
2383 && dfa
->used_bkref_map
& (1 << dfa
->nodes
[node
].opr
.idx
))
2385 err
= match_ctx_add_subtop (mctx
, node
, str_idx
);
2386 if (BE (err
!= REG_NOERROR
, 0))
2394 /* Return the next state to which the current state STATE will transit by
2395 accepting the current input byte. */
2397 static re_dfastate_t
*
2398 transit_state_sb (err
, mctx
, state
)
2400 re_match_context_t
*mctx
;
2401 re_dfastate_t
*state
;
2403 re_dfa_t
*const dfa
= mctx
->dfa
;
2404 re_node_set next_nodes
;
2405 re_dfastate_t
*next_state
;
2406 int node_cnt
, cur_str_idx
= re_string_cur_idx (&mctx
->input
);
2407 unsigned int context
;
2409 *err
= re_node_set_alloc (&next_nodes
, state
->nodes
.nelem
+ 1);
2410 if (BE (*err
!= REG_NOERROR
, 0))
2412 for (node_cnt
= 0; node_cnt
< state
->nodes
.nelem
; ++node_cnt
)
2414 int cur_node
= state
->nodes
.elems
[node_cnt
];
2415 if (check_node_accept (mctx
, dfa
->nodes
+ cur_node
, cur_str_idx
))
2417 *err
= re_node_set_merge (&next_nodes
,
2418 dfa
->eclosures
+ dfa
->nexts
[cur_node
]);
2419 if (BE (*err
!= REG_NOERROR
, 0))
2421 re_node_set_free (&next_nodes
);
2426 context
= re_string_context_at (&mctx
->input
, cur_str_idx
, mctx
->eflags
);
2427 next_state
= re_acquire_state_context (err
, dfa
, &next_nodes
, context
);
2428 /* We don't need to check errors here, since the return value of
2429 this function is next_state and ERR is already set. */
2431 re_node_set_free (&next_nodes
);
2432 re_string_skip_bytes (&mctx
->input
, 1);
2437 #ifdef RE_ENABLE_I18N
2438 static reg_errcode_t
2439 transit_state_mb (mctx
, pstate
)
2440 re_match_context_t
*mctx
;
2441 re_dfastate_t
*pstate
;
2443 re_dfa_t
*const dfa
= mctx
->dfa
;
2447 for (i
= 0; i
< pstate
->nodes
.nelem
; ++i
)
2449 re_node_set dest_nodes
, *new_nodes
;
2450 int cur_node_idx
= pstate
->nodes
.elems
[i
];
2451 int naccepted
= 0, dest_idx
;
2452 unsigned int context
;
2453 re_dfastate_t
*dest_state
;
2455 if (dfa
->nodes
[cur_node_idx
].constraint
)
2457 context
= re_string_context_at (&mctx
->input
,
2458 re_string_cur_idx (&mctx
->input
),
2460 if (NOT_SATISFY_NEXT_CONSTRAINT (dfa
->nodes
[cur_node_idx
].constraint
,
2465 /* How many bytes the node can accept? */
2466 if (ACCEPT_MB_NODE (dfa
->nodes
[cur_node_idx
].type
))
2467 naccepted
= check_node_accept_bytes (dfa
, cur_node_idx
, &mctx
->input
,
2468 re_string_cur_idx (&mctx
->input
));
2472 /* The node can accepts `naccepted' bytes. */
2473 dest_idx
= re_string_cur_idx (&mctx
->input
) + naccepted
;
2474 mctx
->max_mb_elem_len
= ((mctx
->max_mb_elem_len
< naccepted
) ? naccepted
2475 : mctx
->max_mb_elem_len
);
2476 err
= clean_state_log_if_needed (mctx
, dest_idx
);
2477 if (BE (err
!= REG_NOERROR
, 0))
2480 assert (dfa
->nexts
[cur_node_idx
] != -1);
2482 /* `cur_node_idx' may point the entity of the OP_CONTEXT_NODE,
2483 then we use pstate->nodes.elems[i] instead. */
2484 new_nodes
= dfa
->eclosures
+ dfa
->nexts
[pstate
->nodes
.elems
[i
]];
2486 dest_state
= mctx
->state_log
[dest_idx
];
2487 if (dest_state
== NULL
)
2488 dest_nodes
= *new_nodes
;
2491 err
= re_node_set_init_union (&dest_nodes
,
2492 dest_state
->entrance_nodes
, new_nodes
);
2493 if (BE (err
!= REG_NOERROR
, 0))
2496 context
= re_string_context_at (&mctx
->input
, dest_idx
- 1, mctx
->eflags
);
2497 mctx
->state_log
[dest_idx
]
2498 = re_acquire_state_context (&err
, dfa
, &dest_nodes
, context
);
2499 if (dest_state
!= NULL
)
2500 re_node_set_free (&dest_nodes
);
2501 if (BE (mctx
->state_log
[dest_idx
] == NULL
&& err
!= REG_NOERROR
, 0))
2506 #endif /* RE_ENABLE_I18N */
2508 static reg_errcode_t
2509 transit_state_bkref (mctx
, nodes
)
2510 re_match_context_t
*mctx
;
2511 const re_node_set
*nodes
;
2513 re_dfa_t
*const dfa
= mctx
->dfa
;
2516 int cur_str_idx
= re_string_cur_idx (&mctx
->input
);
2518 for (i
= 0; i
< nodes
->nelem
; ++i
)
2520 int dest_str_idx
, prev_nelem
, bkc_idx
;
2521 int node_idx
= nodes
->elems
[i
];
2522 unsigned int context
;
2523 const re_token_t
*node
= dfa
->nodes
+ node_idx
;
2524 re_node_set
*new_dest_nodes
;
2526 /* Check whether `node' is a backreference or not. */
2527 if (node
->type
!= OP_BACK_REF
)
2530 if (node
->constraint
)
2532 context
= re_string_context_at (&mctx
->input
, cur_str_idx
,
2534 if (NOT_SATISFY_NEXT_CONSTRAINT (node
->constraint
, context
))
2538 /* `node' is a backreference.
2539 Check the substring which the substring matched. */
2540 bkc_idx
= mctx
->nbkref_ents
;
2541 err
= get_subexp (mctx
, node_idx
, cur_str_idx
);
2542 if (BE (err
!= REG_NOERROR
, 0))
2545 /* And add the epsilon closures (which is `new_dest_nodes') of
2546 the backreference to appropriate state_log. */
2548 assert (dfa
->nexts
[node_idx
] != -1);
2550 for (; bkc_idx
< mctx
->nbkref_ents
; ++bkc_idx
)
2553 re_dfastate_t
*dest_state
;
2554 struct re_backref_cache_entry
*bkref_ent
;
2555 bkref_ent
= mctx
->bkref_ents
+ bkc_idx
;
2556 if (bkref_ent
->node
!= node_idx
|| bkref_ent
->str_idx
!= cur_str_idx
)
2558 subexp_len
= bkref_ent
->subexp_to
- bkref_ent
->subexp_from
;
2559 new_dest_nodes
= (subexp_len
== 0
2560 ? dfa
->eclosures
+ dfa
->edests
[node_idx
].elems
[0]
2561 : dfa
->eclosures
+ dfa
->nexts
[node_idx
]);
2562 dest_str_idx
= (cur_str_idx
+ bkref_ent
->subexp_to
2563 - bkref_ent
->subexp_from
);
2564 context
= re_string_context_at (&mctx
->input
, dest_str_idx
- 1,
2566 dest_state
= mctx
->state_log
[dest_str_idx
];
2567 prev_nelem
= ((mctx
->state_log
[cur_str_idx
] == NULL
) ? 0
2568 : mctx
->state_log
[cur_str_idx
]->nodes
.nelem
);
2569 /* Add `new_dest_node' to state_log. */
2570 if (dest_state
== NULL
)
2572 mctx
->state_log
[dest_str_idx
]
2573 = re_acquire_state_context (&err
, dfa
, new_dest_nodes
,
2575 if (BE (mctx
->state_log
[dest_str_idx
] == NULL
2576 && err
!= REG_NOERROR
, 0))
2581 re_node_set dest_nodes
;
2582 err
= re_node_set_init_union (&dest_nodes
,
2583 dest_state
->entrance_nodes
,
2585 if (BE (err
!= REG_NOERROR
, 0))
2587 re_node_set_free (&dest_nodes
);
2590 mctx
->state_log
[dest_str_idx
]
2591 = re_acquire_state_context (&err
, dfa
, &dest_nodes
, context
);
2592 re_node_set_free (&dest_nodes
);
2593 if (BE (mctx
->state_log
[dest_str_idx
] == NULL
2594 && err
!= REG_NOERROR
, 0))
2597 /* We need to check recursively if the backreference can epsilon
2600 && mctx
->state_log
[cur_str_idx
]->nodes
.nelem
> prev_nelem
)
2602 err
= check_subexp_matching_top (mctx
, new_dest_nodes
,
2604 if (BE (err
!= REG_NOERROR
, 0))
2606 err
= transit_state_bkref (mctx
, new_dest_nodes
);
2607 if (BE (err
!= REG_NOERROR
, 0))
2617 /* Enumerate all the candidates which the backreference BKREF_NODE can match
2618 at BKREF_STR_IDX, and register them by match_ctx_add_entry().
2619 Note that we might collect inappropriate candidates here.
2620 However, the cost of checking them strictly here is too high, then we
2621 delay these checking for prune_impossible_nodes(). */
2623 static reg_errcode_t
2624 get_subexp (mctx
, bkref_node
, bkref_str_idx
)
2625 re_match_context_t
*mctx
;
2626 int bkref_node
, bkref_str_idx
;
2628 re_dfa_t
*const dfa
= mctx
->dfa
;
2629 int subexp_num
, sub_top_idx
;
2630 const char *buf
= (const char *) re_string_get_buffer (&mctx
->input
);
2631 /* Return if we have already checked BKREF_NODE at BKREF_STR_IDX. */
2632 int cache_idx
= search_cur_bkref_entry (mctx
, bkref_str_idx
);
2633 if (cache_idx
!= -1)
2635 const struct re_backref_cache_entry
*entry
= mctx
->bkref_ents
+ cache_idx
;
2637 if (entry
->node
== bkref_node
)
2638 return REG_NOERROR
; /* We already checked it. */
2639 while (entry
++->more
);
2642 subexp_num
= dfa
->nodes
[bkref_node
].opr
.idx
- 1;
2644 /* For each sub expression */
2645 for (sub_top_idx
= 0; sub_top_idx
< mctx
->nsub_tops
; ++sub_top_idx
)
2648 re_sub_match_top_t
*sub_top
= mctx
->sub_tops
[sub_top_idx
];
2649 re_sub_match_last_t
*sub_last
;
2650 int sub_last_idx
, sl_str
, bkref_str_off
;
2652 if (dfa
->nodes
[sub_top
->node
].opr
.idx
!= subexp_num
)
2653 continue; /* It isn't related. */
2655 sl_str
= sub_top
->str_idx
;
2656 bkref_str_off
= bkref_str_idx
;
2657 /* At first, check the last node of sub expressions we already
2659 for (sub_last_idx
= 0; sub_last_idx
< sub_top
->nlasts
; ++sub_last_idx
)
2662 sub_last
= sub_top
->lasts
[sub_last_idx
];
2663 sl_str_diff
= sub_last
->str_idx
- sl_str
;
2664 /* The matched string by the sub expression match with the substring
2665 at the back reference? */
2666 if (sl_str_diff
> 0)
2668 if (BE (bkref_str_off
+ sl_str_diff
> mctx
->input
.valid_len
, 0))
2670 /* Not enough chars for a successful match. */
2671 if (bkref_str_off
+ sl_str_diff
> mctx
->input
.len
)
2674 err
= clean_state_log_if_needed (mctx
,
2677 if (BE (err
!= REG_NOERROR
, 0))
2679 buf
= (const char *) re_string_get_buffer (&mctx
->input
);
2681 if (memcmp (buf
+ bkref_str_off
, buf
+ sl_str
, sl_str_diff
) != 0)
2682 break; /* We don't need to search this sub expression any more. */
2684 bkref_str_off
+= sl_str_diff
;
2685 sl_str
+= sl_str_diff
;
2686 err
= get_subexp_sub (mctx
, sub_top
, sub_last
, bkref_node
,
2689 /* Reload buf, since the preceding call might have reallocated
2691 buf
= (const char *) re_string_get_buffer (&mctx
->input
);
2693 if (err
== REG_NOMATCH
)
2695 if (BE (err
!= REG_NOERROR
, 0))
2699 if (sub_last_idx
< sub_top
->nlasts
)
2701 if (sub_last_idx
> 0)
2703 /* Then, search for the other last nodes of the sub expression. */
2704 for (; sl_str
<= bkref_str_idx
; ++sl_str
)
2706 int cls_node
, sl_str_off
;
2707 const re_node_set
*nodes
;
2708 sl_str_off
= sl_str
- sub_top
->str_idx
;
2709 /* The matched string by the sub expression match with the substring
2710 at the back reference? */
2713 if (BE (bkref_str_off
>= mctx
->input
.valid_len
, 0))
2715 /* If we are at the end of the input, we cannot match. */
2716 if (bkref_str_off
>= mctx
->input
.len
)
2719 err
= extend_buffers (mctx
);
2720 if (BE (err
!= REG_NOERROR
, 0))
2723 buf
= (const char *) re_string_get_buffer (&mctx
->input
);
2725 if (buf
[bkref_str_off
++] != buf
[sl_str
- 1])
2726 break; /* We don't need to search this sub expression
2729 if (mctx
->state_log
[sl_str
] == NULL
)
2731 /* Does this state have a ')' of the sub expression? */
2732 nodes
= &mctx
->state_log
[sl_str
]->nodes
;
2733 cls_node
= find_subexp_node (dfa
, nodes
, subexp_num
, OP_CLOSE_SUBEXP
);
2736 if (sub_top
->path
== NULL
)
2738 sub_top
->path
= calloc (sizeof (state_array_t
),
2739 sl_str
- sub_top
->str_idx
+ 1);
2740 if (sub_top
->path
== NULL
)
2743 /* Can the OP_OPEN_SUBEXP node arrive the OP_CLOSE_SUBEXP node
2744 in the current context? */
2745 err
= check_arrival (mctx
, sub_top
->path
, sub_top
->node
,
2746 sub_top
->str_idx
, cls_node
, sl_str
, OP_CLOSE_SUBEXP
);
2747 if (err
== REG_NOMATCH
)
2749 if (BE (err
!= REG_NOERROR
, 0))
2751 sub_last
= match_ctx_add_sublast (sub_top
, cls_node
, sl_str
);
2752 if (BE (sub_last
== NULL
, 0))
2754 err
= get_subexp_sub (mctx
, sub_top
, sub_last
, bkref_node
,
2756 if (err
== REG_NOMATCH
)
2763 /* Helper functions for get_subexp(). */
2765 /* Check SUB_LAST can arrive to the back reference BKREF_NODE at BKREF_STR.
2766 If it can arrive, register the sub expression expressed with SUB_TOP
2769 static reg_errcode_t
2770 get_subexp_sub (mctx
, sub_top
, sub_last
, bkref_node
, bkref_str
)
2771 re_match_context_t
*mctx
;
2772 const re_sub_match_top_t
*sub_top
;
2773 re_sub_match_last_t
*sub_last
;
2774 int bkref_node
, bkref_str
;
2778 /* Can the subexpression arrive the back reference? */
2779 err
= check_arrival (mctx
, &sub_last
->path
, sub_last
->node
,
2780 sub_last
->str_idx
, bkref_node
, bkref_str
, OP_OPEN_SUBEXP
);
2781 if (err
!= REG_NOERROR
)
2783 err
= match_ctx_add_entry (mctx
, bkref_node
, bkref_str
, sub_top
->str_idx
,
2785 if (BE (err
!= REG_NOERROR
, 0))
2787 to_idx
= bkref_str
+ sub_last
->str_idx
- sub_top
->str_idx
;
2788 return clean_state_log_if_needed (mctx
, to_idx
);
2791 /* Find the first node which is '(' or ')' and whose index is SUBEXP_IDX.
2792 Search '(' if FL_OPEN, or search ')' otherwise.
2793 TODO: This function isn't efficient...
2794 Because there might be more than one nodes whose types are
2795 OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
2800 find_subexp_node (dfa
, nodes
, subexp_idx
, type
)
2801 const re_dfa_t
*dfa
;
2802 const re_node_set
*nodes
;
2803 int subexp_idx
, type
;
2806 for (cls_idx
= 0; cls_idx
< nodes
->nelem
; ++cls_idx
)
2808 int cls_node
= nodes
->elems
[cls_idx
];
2809 const re_token_t
*node
= dfa
->nodes
+ cls_node
;
2810 if (node
->type
== type
2811 && node
->opr
.idx
== subexp_idx
)
2817 /* Check whether the node TOP_NODE at TOP_STR can arrive to the node
2818 LAST_NODE at LAST_STR. We record the path onto PATH since it will be
2820 Return REG_NOERROR if it can arrive, or REG_NOMATCH otherwise. */
2822 static reg_errcode_t
2823 check_arrival (mctx
, path
, top_node
, top_str
, last_node
, last_str
,
2825 re_match_context_t
*mctx
;
2826 state_array_t
*path
;
2827 int top_node
, top_str
, last_node
, last_str
, type
;
2829 re_dfa_t
*const dfa
= mctx
->dfa
;
2831 int subexp_num
, backup_cur_idx
, str_idx
, null_cnt
;
2832 re_dfastate_t
*cur_state
= NULL
;
2833 re_node_set
*cur_nodes
, next_nodes
;
2834 re_dfastate_t
**backup_state_log
;
2835 unsigned int context
;
2837 subexp_num
= dfa
->nodes
[top_node
].opr
.idx
;
2838 /* Extend the buffer if we need. */
2839 if (BE (path
->alloc
< last_str
+ mctx
->max_mb_elem_len
+ 1, 0))
2841 re_dfastate_t
**new_array
;
2842 int old_alloc
= path
->alloc
;
2843 path
->alloc
+= last_str
+ mctx
->max_mb_elem_len
+ 1;
2844 new_array
= re_realloc (path
->array
, re_dfastate_t
*, path
->alloc
);
2845 if (new_array
== NULL
)
2847 path
->alloc
= old_alloc
;
2850 path
->array
= new_array
;
2851 memset (new_array
+ old_alloc
, '\0',
2852 sizeof (re_dfastate_t
*) * (path
->alloc
- old_alloc
));
2855 str_idx
= path
->next_idx
== 0 ? top_str
: path
->next_idx
;
2857 /* Temporary modify MCTX. */
2858 backup_state_log
= mctx
->state_log
;
2859 backup_cur_idx
= mctx
->input
.cur_idx
;
2860 mctx
->state_log
= path
->array
;
2861 mctx
->input
.cur_idx
= str_idx
;
2863 /* Setup initial node set. */
2864 context
= re_string_context_at (&mctx
->input
, str_idx
- 1, mctx
->eflags
);
2865 if (str_idx
== top_str
)
2867 err
= re_node_set_init_1 (&next_nodes
, top_node
);
2868 if (BE (err
!= REG_NOERROR
, 0))
2870 err
= check_arrival_expand_ecl (dfa
, &next_nodes
, subexp_num
, type
);
2871 if (BE (err
!= REG_NOERROR
, 0))
2873 re_node_set_free (&next_nodes
);
2879 cur_state
= mctx
->state_log
[str_idx
];
2880 if (cur_state
&& cur_state
->has_backref
)
2882 err
= re_node_set_init_copy (&next_nodes
, &cur_state
->nodes
);
2883 if (BE ( err
!= REG_NOERROR
, 0))
2887 re_node_set_init_empty (&next_nodes
);
2889 if (str_idx
== top_str
|| (cur_state
&& cur_state
->has_backref
))
2891 if (next_nodes
.nelem
)
2893 err
= expand_bkref_cache (mctx
, &next_nodes
, str_idx
,
2895 if (BE ( err
!= REG_NOERROR
, 0))
2897 re_node_set_free (&next_nodes
);
2901 cur_state
= re_acquire_state_context (&err
, dfa
, &next_nodes
, context
);
2902 if (BE (cur_state
== NULL
&& err
!= REG_NOERROR
, 0))
2904 re_node_set_free (&next_nodes
);
2907 mctx
->state_log
[str_idx
] = cur_state
;
2910 for (null_cnt
= 0; str_idx
< last_str
&& null_cnt
<= mctx
->max_mb_elem_len
;)
2912 re_node_set_empty (&next_nodes
);
2913 if (mctx
->state_log
[str_idx
+ 1])
2915 err
= re_node_set_merge (&next_nodes
,
2916 &mctx
->state_log
[str_idx
+ 1]->nodes
);
2917 if (BE (err
!= REG_NOERROR
, 0))
2919 re_node_set_free (&next_nodes
);
2925 err
= check_arrival_add_next_nodes (mctx
, str_idx
,
2926 &cur_state
->nodes
, &next_nodes
);
2927 if (BE (err
!= REG_NOERROR
, 0))
2929 re_node_set_free (&next_nodes
);
2934 if (next_nodes
.nelem
)
2936 err
= check_arrival_expand_ecl (dfa
, &next_nodes
, subexp_num
, type
);
2937 if (BE (err
!= REG_NOERROR
, 0))
2939 re_node_set_free (&next_nodes
);
2942 err
= expand_bkref_cache (mctx
, &next_nodes
, str_idx
,
2944 if (BE ( err
!= REG_NOERROR
, 0))
2946 re_node_set_free (&next_nodes
);
2950 context
= re_string_context_at (&mctx
->input
, str_idx
- 1, mctx
->eflags
);
2951 cur_state
= re_acquire_state_context (&err
, dfa
, &next_nodes
, context
);
2952 if (BE (cur_state
== NULL
&& err
!= REG_NOERROR
, 0))
2954 re_node_set_free (&next_nodes
);
2957 mctx
->state_log
[str_idx
] = cur_state
;
2958 null_cnt
= cur_state
== NULL
? null_cnt
+ 1 : 0;
2960 re_node_set_free (&next_nodes
);
2961 cur_nodes
= (mctx
->state_log
[last_str
] == NULL
? NULL
2962 : &mctx
->state_log
[last_str
]->nodes
);
2963 path
->next_idx
= str_idx
;
2966 mctx
->state_log
= backup_state_log
;
2967 mctx
->input
.cur_idx
= backup_cur_idx
;
2969 /* Then check the current node set has the node LAST_NODE. */
2970 if (cur_nodes
!= NULL
&& re_node_set_contains (cur_nodes
, last_node
))
2976 /* Helper functions for check_arrival. */
2978 /* Calculate the destination nodes of CUR_NODES at STR_IDX, and append them
2980 TODO: This function is similar to the functions transit_state*(),
2981 however this function has many additional works.
2982 Can't we unify them? */
2984 static reg_errcode_t
2985 check_arrival_add_next_nodes (mctx
, str_idx
, cur_nodes
, next_nodes
)
2986 re_match_context_t
*mctx
;
2988 re_node_set
*cur_nodes
, *next_nodes
;
2990 re_dfa_t
*const dfa
= mctx
->dfa
;
2994 re_node_set union_set
;
2995 re_node_set_init_empty (&union_set
);
2996 for (cur_idx
= 0; cur_idx
< cur_nodes
->nelem
; ++cur_idx
)
2999 int cur_node
= cur_nodes
->elems
[cur_idx
];
3000 re_token_type_t type
= dfa
->nodes
[cur_node
].type
;
3001 if (IS_EPSILON_NODE (type
))
3003 #ifdef RE_ENABLE_I18N
3004 /* If the node may accept `multi byte'. */
3005 if (ACCEPT_MB_NODE (type
))
3007 naccepted
= check_node_accept_bytes (dfa
, cur_node
, &mctx
->input
,
3011 re_dfastate_t
*dest_state
;
3012 int next_node
= dfa
->nexts
[cur_node
];
3013 int next_idx
= str_idx
+ naccepted
;
3014 dest_state
= mctx
->state_log
[next_idx
];
3015 re_node_set_empty (&union_set
);
3018 err
= re_node_set_merge (&union_set
, &dest_state
->nodes
);
3019 if (BE (err
!= REG_NOERROR
, 0))
3021 re_node_set_free (&union_set
);
3025 result
= re_node_set_insert (&union_set
, next_node
);
3026 if (BE (result
< 0, 0))
3028 re_node_set_free (&union_set
);
3031 mctx
->state_log
[next_idx
] = re_acquire_state (&err
, dfa
,
3033 if (BE (mctx
->state_log
[next_idx
] == NULL
3034 && err
!= REG_NOERROR
, 0))
3036 re_node_set_free (&union_set
);
3041 #endif /* RE_ENABLE_I18N */
3043 || check_node_accept (mctx
, dfa
->nodes
+ cur_node
, str_idx
))
3045 result
= re_node_set_insert (next_nodes
, dfa
->nexts
[cur_node
]);
3046 if (BE (result
< 0, 0))
3048 re_node_set_free (&union_set
);
3053 re_node_set_free (&union_set
);
3057 /* For all the nodes in CUR_NODES, add the epsilon closures of them to
3058 CUR_NODES, however exclude the nodes which are:
3059 - inside the sub expression whose number is EX_SUBEXP, if FL_OPEN.
3060 - out of the sub expression whose number is EX_SUBEXP, if !FL_OPEN.
3063 static reg_errcode_t
3064 check_arrival_expand_ecl (dfa
, cur_nodes
, ex_subexp
, type
)
3066 re_node_set
*cur_nodes
;
3067 int ex_subexp
, type
;
3070 int idx
, outside_node
;
3071 re_node_set new_nodes
;
3073 assert (cur_nodes
->nelem
);
3075 err
= re_node_set_alloc (&new_nodes
, cur_nodes
->nelem
);
3076 if (BE (err
!= REG_NOERROR
, 0))
3078 /* Create a new node set NEW_NODES with the nodes which are epsilon
3079 closures of the node in CUR_NODES. */
3081 for (idx
= 0; idx
< cur_nodes
->nelem
; ++idx
)
3083 int cur_node
= cur_nodes
->elems
[idx
];
3084 re_node_set
*eclosure
= dfa
->eclosures
+ cur_node
;
3085 outside_node
= find_subexp_node (dfa
, eclosure
, ex_subexp
, type
);
3086 if (outside_node
== -1)
3088 /* There are no problematic nodes, just merge them. */
3089 err
= re_node_set_merge (&new_nodes
, eclosure
);
3090 if (BE (err
!= REG_NOERROR
, 0))
3092 re_node_set_free (&new_nodes
);
3098 /* There are problematic nodes, re-calculate incrementally. */
3099 err
= check_arrival_expand_ecl_sub (dfa
, &new_nodes
, cur_node
,
3101 if (BE (err
!= REG_NOERROR
, 0))
3103 re_node_set_free (&new_nodes
);
3108 re_node_set_free (cur_nodes
);
3109 *cur_nodes
= new_nodes
;
3113 /* Helper function for check_arrival_expand_ecl.
3114 Check incrementally the epsilon closure of TARGET, and if it isn't
3115 problematic append it to DST_NODES. */
3117 static reg_errcode_t
3118 check_arrival_expand_ecl_sub (dfa
, dst_nodes
, target
, ex_subexp
, type
)
3120 int target
, ex_subexp
, type
;
3121 re_node_set
*dst_nodes
;
3124 for (cur_node
= target
; !re_node_set_contains (dst_nodes
, cur_node
);)
3128 if (dfa
->nodes
[cur_node
].type
== type
3129 && dfa
->nodes
[cur_node
].opr
.idx
== ex_subexp
)
3131 if (type
== OP_CLOSE_SUBEXP
)
3133 err
= re_node_set_insert (dst_nodes
, cur_node
);
3134 if (BE (err
== -1, 0))
3139 err
= re_node_set_insert (dst_nodes
, cur_node
);
3140 if (BE (err
== -1, 0))
3142 if (dfa
->edests
[cur_node
].nelem
== 0)
3144 if (dfa
->edests
[cur_node
].nelem
== 2)
3146 err
= check_arrival_expand_ecl_sub (dfa
, dst_nodes
,
3147 dfa
->edests
[cur_node
].elems
[1],
3149 if (BE (err
!= REG_NOERROR
, 0))
3152 cur_node
= dfa
->edests
[cur_node
].elems
[0];
3158 /* For all the back references in the current state, calculate the
3159 destination of the back references by the appropriate entry
3160 in MCTX->BKREF_ENTS. */
3162 static reg_errcode_t
3163 expand_bkref_cache (mctx
, cur_nodes
, cur_str
, subexp_num
,
3165 re_match_context_t
*mctx
;
3166 int cur_str
, subexp_num
, type
;
3167 re_node_set
*cur_nodes
;
3169 re_dfa_t
*const dfa
= mctx
->dfa
;
3171 int cache_idx_start
= search_cur_bkref_entry (mctx
, cur_str
);
3172 struct re_backref_cache_entry
*ent
;
3174 if (cache_idx_start
== -1)
3178 ent
= mctx
->bkref_ents
+ cache_idx_start
;
3181 int to_idx
, next_node
;
3183 /* Is this entry ENT is appropriate? */
3184 if (!re_node_set_contains (cur_nodes
, ent
->node
))
3187 to_idx
= cur_str
+ ent
->subexp_to
- ent
->subexp_from
;
3188 /* Calculate the destination of the back reference, and append it
3189 to MCTX->STATE_LOG. */
3190 if (to_idx
== cur_str
)
3192 /* The backreference did epsilon transit, we must re-check all the
3193 node in the current state. */
3194 re_node_set new_dests
;
3195 reg_errcode_t err2
, err3
;
3196 next_node
= dfa
->edests
[ent
->node
].elems
[0];
3197 if (re_node_set_contains (cur_nodes
, next_node
))
3199 err
= re_node_set_init_1 (&new_dests
, next_node
);
3200 err2
= check_arrival_expand_ecl (dfa
, &new_dests
, subexp_num
, type
);
3201 err3
= re_node_set_merge (cur_nodes
, &new_dests
);
3202 re_node_set_free (&new_dests
);
3203 if (BE (err
!= REG_NOERROR
|| err2
!= REG_NOERROR
3204 || err3
!= REG_NOERROR
, 0))
3206 err
= (err
!= REG_NOERROR
? err
3207 : (err2
!= REG_NOERROR
? err2
: err3
));
3210 /* TODO: It is still inefficient... */
3215 re_node_set union_set
;
3216 next_node
= dfa
->nexts
[ent
->node
];
3217 if (mctx
->state_log
[to_idx
])
3220 if (re_node_set_contains (&mctx
->state_log
[to_idx
]->nodes
,
3223 err
= re_node_set_init_copy (&union_set
,
3224 &mctx
->state_log
[to_idx
]->nodes
);
3225 ret
= re_node_set_insert (&union_set
, next_node
);
3226 if (BE (err
!= REG_NOERROR
|| ret
< 0, 0))
3228 re_node_set_free (&union_set
);
3229 err
= err
!= REG_NOERROR
? err
: REG_ESPACE
;
3235 err
= re_node_set_init_1 (&union_set
, next_node
);
3236 if (BE (err
!= REG_NOERROR
, 0))
3239 mctx
->state_log
[to_idx
] = re_acquire_state (&err
, dfa
, &union_set
);
3240 re_node_set_free (&union_set
);
3241 if (BE (mctx
->state_log
[to_idx
] == NULL
3242 && err
!= REG_NOERROR
, 0))
3246 while (ent
++->more
);
3250 /* Build transition table for the state.
3251 Return the new table if succeeded, otherwise return NULL. */
3253 static re_dfastate_t
**
3254 build_trtable (dfa
, state
)
3256 re_dfastate_t
*state
;
3260 unsigned int elem
, mask
;
3261 int dests_node_malloced
= 0, dest_states_malloced
= 0;
3262 int ndests
; /* Number of the destination states from `state'. */
3263 re_dfastate_t
**trtable
;
3264 re_dfastate_t
**dest_states
= NULL
, **dest_states_word
, **dest_states_nl
;
3265 re_node_set follows
, *dests_node
;
3269 /* We build DFA states which corresponds to the destination nodes
3270 from `state'. `dests_node[i]' represents the nodes which i-th
3271 destination state contains, and `dests_ch[i]' represents the
3272 characters which i-th destination state accepts. */
3274 if (__libc_use_alloca ((sizeof (re_node_set
) + sizeof (bitset
)) * SBC_MAX
))
3275 dests_node
= (re_node_set
*)
3276 alloca ((sizeof (re_node_set
) + sizeof (bitset
)) * SBC_MAX
);
3280 dests_node
= (re_node_set
*)
3281 malloc ((sizeof (re_node_set
) + sizeof (bitset
)) * SBC_MAX
);
3282 if (BE (dests_node
== NULL
, 0))
3284 dests_node_malloced
= 1;
3286 dests_ch
= (bitset
*) (dests_node
+ SBC_MAX
);
3288 /* Initialize transiton table. */
3289 state
->word_trtable
= 0;
3291 /* At first, group all nodes belonging to `state' into several
3293 ndests
= group_nodes_into_DFAstates (dfa
, state
, dests_node
, dests_ch
);
3294 if (BE (ndests
<= 0, 0))
3296 if (dests_node_malloced
)
3298 /* Return NULL in case of an error, trtable otherwise. */
3301 state
->trtable
= (re_dfastate_t
**)
3302 calloc (sizeof (re_dfastate_t
*), SBC_MAX
);;
3303 return state
->trtable
;
3308 err
= re_node_set_alloc (&follows
, ndests
+ 1);
3309 if (BE (err
!= REG_NOERROR
, 0))
3313 if (__libc_use_alloca ((sizeof (re_node_set
) + sizeof (bitset
)) * SBC_MAX
3314 + ndests
* 3 * sizeof (re_dfastate_t
*)))
3315 dest_states
= (re_dfastate_t
**)
3316 alloca (ndests
* 3 * sizeof (re_dfastate_t
*));
3320 dest_states
= (re_dfastate_t
**)
3321 malloc (ndests
* 3 * sizeof (re_dfastate_t
*));
3322 if (BE (dest_states
== NULL
, 0))
3325 if (dest_states_malloced
)
3327 re_node_set_free (&follows
);
3328 for (i
= 0; i
< ndests
; ++i
)
3329 re_node_set_free (dests_node
+ i
);
3330 if (dests_node_malloced
)
3334 dest_states_malloced
= 1;
3336 dest_states_word
= dest_states
+ ndests
;
3337 dest_states_nl
= dest_states_word
+ ndests
;
3338 bitset_empty (acceptable
);
3340 /* Then build the states for all destinations. */
3341 for (i
= 0; i
< ndests
; ++i
)
3344 re_node_set_empty (&follows
);
3345 /* Merge the follows of this destination states. */
3346 for (j
= 0; j
< dests_node
[i
].nelem
; ++j
)
3348 next_node
= dfa
->nexts
[dests_node
[i
].elems
[j
]];
3349 if (next_node
!= -1)
3351 err
= re_node_set_merge (&follows
, dfa
->eclosures
+ next_node
);
3352 if (BE (err
!= REG_NOERROR
, 0))
3356 dest_states
[i
] = re_acquire_state_context (&err
, dfa
, &follows
, 0);
3357 if (BE (dest_states
[i
] == NULL
&& err
!= REG_NOERROR
, 0))
3359 /* If the new state has context constraint,
3360 build appropriate states for these contexts. */
3361 if (dest_states
[i
]->has_constraint
)
3363 dest_states_word
[i
] = re_acquire_state_context (&err
, dfa
, &follows
,
3365 if (BE (dest_states_word
[i
] == NULL
&& err
!= REG_NOERROR
, 0))
3368 if (dest_states
[i
] != dest_states_word
[i
]
3369 && dfa
->mb_cur_max
> 1)
3370 state
->word_trtable
= 1;
3372 dest_states_nl
[i
] = re_acquire_state_context (&err
, dfa
, &follows
,
3374 if (BE (dest_states_nl
[i
] == NULL
&& err
!= REG_NOERROR
, 0))
3379 dest_states_word
[i
] = dest_states
[i
];
3380 dest_states_nl
[i
] = dest_states
[i
];
3382 bitset_merge (acceptable
, dests_ch
[i
]);
3385 if (!BE (state
->word_trtable
, 0))
3387 /* We don't care about whether the following character is a word
3388 character, or we are in a single-byte character set so we can
3389 discern by looking at the character code: allocate a
3390 256-entry transition table. */
3391 trtable
= (re_dfastate_t
**) calloc (sizeof (re_dfastate_t
*), SBC_MAX
);
3392 if (BE (trtable
== NULL
, 0))
3395 /* For all characters ch...: */
3396 for (i
= 0; i
< BITSET_UINTS
; ++i
)
3397 for (ch
= i
* UINT_BITS
, elem
= acceptable
[i
], mask
= 1;
3399 mask
<<= 1, elem
>>= 1, ++ch
)
3400 if (BE (elem
& 1, 0))
3402 /* There must be exactly one destination which accepts
3403 character ch. See group_nodes_into_DFAstates. */
3404 for (j
= 0; (dests_ch
[j
][i
] & mask
) == 0; ++j
)
3407 /* j-th destination accepts the word character ch. */
3408 if (dfa
->word_char
[i
] & mask
)
3409 trtable
[ch
] = dest_states_word
[j
];
3411 trtable
[ch
] = dest_states
[j
];
3416 /* We care about whether the following character is a word
3417 character, and we are in a multi-byte character set: discern
3418 by looking at the character code: build two 256-entry
3419 transition tables, one starting at trtable[0] and one
3420 starting at trtable[SBC_MAX]. */
3421 trtable
= (re_dfastate_t
**) calloc (sizeof (re_dfastate_t
*),
3423 if (BE (trtable
== NULL
, 0))
3426 /* For all characters ch...: */
3427 for (i
= 0; i
< BITSET_UINTS
; ++i
)
3428 for (ch
= i
* UINT_BITS
, elem
= acceptable
[i
], mask
= 1;
3430 mask
<<= 1, elem
>>= 1, ++ch
)
3431 if (BE (elem
& 1, 0))
3433 /* There must be exactly one destination which accepts
3434 character ch. See group_nodes_into_DFAstates. */
3435 for (j
= 0; (dests_ch
[j
][i
] & mask
) == 0; ++j
)
3438 /* j-th destination accepts the word character ch. */
3439 trtable
[ch
] = dest_states
[j
];
3440 trtable
[ch
+ SBC_MAX
] = dest_states_word
[j
];
3445 if (bitset_contain (acceptable
, NEWLINE_CHAR
))
3447 /* The current state accepts newline character. */
3448 for (j
= 0; j
< ndests
; ++j
)
3449 if (bitset_contain (dests_ch
[j
], NEWLINE_CHAR
))
3451 /* k-th destination accepts newline character. */
3452 trtable
[NEWLINE_CHAR
] = dest_states_nl
[j
];
3453 if (state
->word_trtable
)
3454 trtable
[NEWLINE_CHAR
+ SBC_MAX
] = dest_states_nl
[j
];
3455 /* There must be only one destination which accepts
3456 newline. See group_nodes_into_DFAstates. */
3461 if (dest_states_malloced
)
3464 re_node_set_free (&follows
);
3465 for (i
= 0; i
< ndests
; ++i
)
3466 re_node_set_free (dests_node
+ i
);
3468 if (dests_node_malloced
)
3471 state
->trtable
= trtable
;
3475 /* Group all nodes belonging to STATE into several destinations.
3476 Then for all destinations, set the nodes belonging to the destination
3477 to DESTS_NODE[i] and set the characters accepted by the destination
3478 to DEST_CH[i]. This function return the number of destinations. */
3481 group_nodes_into_DFAstates (dfa
, state
, dests_node
, dests_ch
)
3483 const re_dfastate_t
*state
;
3484 re_node_set
*dests_node
;
3490 int ndests
; /* Number of the destinations from `state'. */
3491 bitset accepts
; /* Characters a node can accept. */
3492 const re_node_set
*cur_nodes
= &state
->nodes
;
3493 bitset_empty (accepts
);
3496 /* For all the nodes belonging to `state', */
3497 for (i
= 0; i
< cur_nodes
->nelem
; ++i
)
3499 re_token_t
*node
= &dfa
->nodes
[cur_nodes
->elems
[i
]];
3500 re_token_type_t type
= node
->type
;
3501 unsigned int constraint
= node
->constraint
;
3503 /* Enumerate all single byte character this node can accept. */
3504 if (type
== CHARACTER
)
3505 bitset_set (accepts
, node
->opr
.c
);
3506 else if (type
== SIMPLE_BRACKET
)
3508 bitset_merge (accepts
, node
->opr
.sbcset
);
3510 else if (type
== OP_PERIOD
)
3512 #ifdef RE_ENABLE_I18N
3513 if (dfa
->mb_cur_max
> 1)
3514 bitset_merge (accepts
, dfa
->sb_char
);
3517 bitset_set_all (accepts
);
3518 if (!(dfa
->syntax
& RE_DOT_NEWLINE
))
3519 bitset_clear (accepts
, '\n');
3520 if (dfa
->syntax
& RE_DOT_NOT_NULL
)
3521 bitset_clear (accepts
, '\0');
3523 #ifdef RE_ENABLE_I18N
3524 else if (type
== OP_UTF8_PERIOD
)
3526 memset (accepts
, 255, sizeof (unsigned int) * BITSET_UINTS
/ 2);
3527 if (!(dfa
->syntax
& RE_DOT_NEWLINE
))
3528 bitset_clear (accepts
, '\n');
3529 if (dfa
->syntax
& RE_DOT_NOT_NULL
)
3530 bitset_clear (accepts
, '\0');
3536 /* Check the `accepts' and sift the characters which are not
3537 match it the context. */
3540 if (constraint
& NEXT_NEWLINE_CONSTRAINT
)
3542 int accepts_newline
= bitset_contain (accepts
, NEWLINE_CHAR
);
3543 bitset_empty (accepts
);
3544 if (accepts_newline
)
3545 bitset_set (accepts
, NEWLINE_CHAR
);
3549 if (constraint
& NEXT_ENDBUF_CONSTRAINT
)
3551 bitset_empty (accepts
);
3555 if (constraint
& NEXT_WORD_CONSTRAINT
)
3557 unsigned int any_set
= 0;
3558 if (type
== CHARACTER
&& !node
->word_char
)
3560 bitset_empty (accepts
);
3563 #ifdef RE_ENABLE_I18N
3564 if (dfa
->mb_cur_max
> 1)
3565 for (j
= 0; j
< BITSET_UINTS
; ++j
)
3566 any_set
|= (accepts
[j
] &= (dfa
->word_char
[j
] | ~dfa
->sb_char
[j
]));
3569 for (j
= 0; j
< BITSET_UINTS
; ++j
)
3570 any_set
|= (accepts
[j
] &= dfa
->word_char
[j
]);
3574 if (constraint
& NEXT_NOTWORD_CONSTRAINT
)
3576 unsigned int any_set
= 0;
3577 if (type
== CHARACTER
&& node
->word_char
)
3579 bitset_empty (accepts
);
3582 #ifdef RE_ENABLE_I18N
3583 if (dfa
->mb_cur_max
> 1)
3584 for (j
= 0; j
< BITSET_UINTS
; ++j
)
3585 any_set
|= (accepts
[j
] &= ~(dfa
->word_char
[j
] & dfa
->sb_char
[j
]));
3588 for (j
= 0; j
< BITSET_UINTS
; ++j
)
3589 any_set
|= (accepts
[j
] &= ~dfa
->word_char
[j
]);
3595 /* Then divide `accepts' into DFA states, or create a new
3596 state. Above, we make sure that accepts is not empty. */
3597 for (j
= 0; j
< ndests
; ++j
)
3599 bitset intersec
; /* Intersection sets, see below. */
3601 /* Flags, see below. */
3602 int has_intersec
, not_subset
, not_consumed
;
3604 /* Optimization, skip if this state doesn't accept the character. */
3605 if (type
== CHARACTER
&& !bitset_contain (dests_ch
[j
], node
->opr
.c
))
3608 /* Enumerate the intersection set of this state and `accepts'. */
3610 for (k
= 0; k
< BITSET_UINTS
; ++k
)
3611 has_intersec
|= intersec
[k
] = accepts
[k
] & dests_ch
[j
][k
];
3612 /* And skip if the intersection set is empty. */
3616 /* Then check if this state is a subset of `accepts'. */
3617 not_subset
= not_consumed
= 0;
3618 for (k
= 0; k
< BITSET_UINTS
; ++k
)
3620 not_subset
|= remains
[k
] = ~accepts
[k
] & dests_ch
[j
][k
];
3621 not_consumed
|= accepts
[k
] = accepts
[k
] & ~dests_ch
[j
][k
];
3624 /* If this state isn't a subset of `accepts', create a
3625 new group state, which has the `remains'. */
3628 bitset_copy (dests_ch
[ndests
], remains
);
3629 bitset_copy (dests_ch
[j
], intersec
);
3630 err
= re_node_set_init_copy (dests_node
+ ndests
, &dests_node
[j
]);
3631 if (BE (err
!= REG_NOERROR
, 0))
3636 /* Put the position in the current group. */
3637 result
= re_node_set_insert (&dests_node
[j
], cur_nodes
->elems
[i
]);
3638 if (BE (result
< 0, 0))
3641 /* If all characters are consumed, go to next node. */
3645 /* Some characters remain, create a new group. */
3648 bitset_copy (dests_ch
[ndests
], accepts
);
3649 err
= re_node_set_init_1 (dests_node
+ ndests
, cur_nodes
->elems
[i
]);
3650 if (BE (err
!= REG_NOERROR
, 0))
3653 bitset_empty (accepts
);
3658 for (j
= 0; j
< ndests
; ++j
)
3659 re_node_set_free (dests_node
+ j
);
3663 #ifdef RE_ENABLE_I18N
3664 /* Check how many bytes the node `dfa->nodes[node_idx]' accepts.
3665 Return the number of the bytes the node accepts.
3666 STR_IDX is the current index of the input string.
3668 This function handles the nodes which can accept one character, or
3669 one collating element like '.', '[a-z]', opposite to the other nodes
3670 can only accept one byte. */
3673 check_node_accept_bytes (dfa
, node_idx
, input
, str_idx
)
3675 int node_idx
, str_idx
;
3676 const re_string_t
*input
;
3678 const re_token_t
*node
= dfa
->nodes
+ node_idx
;
3679 int char_len
, elem_len
;
3682 if (BE (node
->type
== OP_UTF8_PERIOD
, 0))
3684 unsigned char c
= re_string_byte_at (input
, str_idx
), d
;
3685 if (BE (c
< 0xc2, 1))
3688 if (str_idx
+ 2 > input
->len
)
3691 d
= re_string_byte_at (input
, str_idx
+ 1);
3693 return (d
< 0x80 || d
> 0xbf) ? 0 : 2;
3697 if (c
== 0xe0 && d
< 0xa0)
3703 if (c
== 0xf0 && d
< 0x90)
3709 if (c
== 0xf8 && d
< 0x88)
3715 if (c
== 0xfc && d
< 0x84)
3721 if (str_idx
+ char_len
> input
->len
)
3724 for (i
= 1; i
< char_len
; ++i
)
3726 d
= re_string_byte_at (input
, str_idx
+ i
);
3727 if (d
< 0x80 || d
> 0xbf)
3733 char_len
= re_string_char_size_at (input
, str_idx
);
3734 if (node
->type
== OP_PERIOD
)
3738 /* FIXME: I don't think this if is needed, as both '\n'
3739 and '\0' are char_len == 1. */
3740 /* '.' accepts any one character except the following two cases. */
3741 if ((!(dfa
->syntax
& RE_DOT_NEWLINE
) &&
3742 re_string_byte_at (input
, str_idx
) == '\n') ||
3743 ((dfa
->syntax
& RE_DOT_NOT_NULL
) &&
3744 re_string_byte_at (input
, str_idx
) == '\0'))
3749 elem_len
= re_string_elem_size_at (input
, str_idx
);
3750 if ((elem_len
<= 1 && char_len
<= 1) || char_len
== 0)
3753 if (node
->type
== COMPLEX_BRACKET
)
3755 const re_charset_t
*cset
= node
->opr
.mbcset
;
3757 const unsigned char *pin
= ((char *) re_string_get_buffer (input
)
3763 wchar_t wc
= ((cset
->nranges
|| cset
->nchar_classes
|| cset
->nmbchars
)
3764 ? re_string_wchar_at (input
, str_idx
) : 0);
3766 /* match with multibyte character? */
3767 for (i
= 0; i
< cset
->nmbchars
; ++i
)
3768 if (wc
== cset
->mbchars
[i
])
3770 match_len
= char_len
;
3771 goto check_node_accept_bytes_match
;
3773 /* match with character_class? */
3774 for (i
= 0; i
< cset
->nchar_classes
; ++i
)
3776 wctype_t wt
= cset
->char_classes
[i
];
3777 if (__iswctype (wc
, wt
))
3779 match_len
= char_len
;
3780 goto check_node_accept_bytes_match
;
3785 nrules
= _NL_CURRENT_WORD (LC_COLLATE
, _NL_COLLATE_NRULES
);
3788 unsigned int in_collseq
= 0;
3789 const int32_t *table
, *indirect
;
3790 const unsigned char *weights
, *extra
;
3791 const char *collseqwc
;
3793 /* This #include defines a local function! */
3794 # include <locale/weight.h>
3796 /* match with collating_symbol? */
3797 if (cset
->ncoll_syms
)
3798 extra
= (const unsigned char *)
3799 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_SYMB_EXTRAMB
);
3800 for (i
= 0; i
< cset
->ncoll_syms
; ++i
)
3802 const unsigned char *coll_sym
= extra
+ cset
->coll_syms
[i
];
3803 /* Compare the length of input collating element and
3804 the length of current collating element. */
3805 if (*coll_sym
!= elem_len
)
3807 /* Compare each bytes. */
3808 for (j
= 0; j
< *coll_sym
; j
++)
3809 if (pin
[j
] != coll_sym
[1 + j
])
3813 /* Match if every bytes is equal. */
3815 goto check_node_accept_bytes_match
;
3821 if (elem_len
<= char_len
)
3823 collseqwc
= _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_COLLSEQWC
);
3824 in_collseq
= __collseq_table_lookup (collseqwc
, wc
);
3827 in_collseq
= find_collation_sequence_value (pin
, elem_len
);
3829 /* match with range expression? */
3830 for (i
= 0; i
< cset
->nranges
; ++i
)
3831 if (cset
->range_starts
[i
] <= in_collseq
3832 && in_collseq
<= cset
->range_ends
[i
])
3834 match_len
= elem_len
;
3835 goto check_node_accept_bytes_match
;
3838 /* match with equivalence_class? */
3839 if (cset
->nequiv_classes
)
3841 const unsigned char *cp
= pin
;
3842 table
= (const int32_t *)
3843 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_TABLEMB
);
3844 weights
= (const unsigned char *)
3845 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_WEIGHTMB
);
3846 extra
= (const unsigned char *)
3847 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_EXTRAMB
);
3848 indirect
= (const int32_t *)
3849 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_INDIRECTMB
);
3850 idx
= findidx (&cp
);
3852 for (i
= 0; i
< cset
->nequiv_classes
; ++i
)
3854 int32_t equiv_class_idx
= cset
->equiv_classes
[i
];
3855 size_t weight_len
= weights
[idx
];
3856 if (weight_len
== weights
[equiv_class_idx
])
3859 while (cnt
<= weight_len
3860 && (weights
[equiv_class_idx
+ 1 + cnt
]
3861 == weights
[idx
+ 1 + cnt
]))
3863 if (cnt
> weight_len
)
3865 match_len
= elem_len
;
3866 goto check_node_accept_bytes_match
;
3875 /* match with range expression? */
3877 wchar_t cmp_buf
[] = {L
'\0', L
'\0', wc
, L
'\0', L
'\0', L
'\0'};
3879 wchar_t cmp_buf
[] = {L
'\0', L
'\0', L
'\0', L
'\0', L
'\0', L
'\0'};
3882 for (i
= 0; i
< cset
->nranges
; ++i
)
3884 cmp_buf
[0] = cset
->range_starts
[i
];
3885 cmp_buf
[4] = cset
->range_ends
[i
];
3886 if (wcscoll (cmp_buf
, cmp_buf
+ 2) <= 0
3887 && wcscoll (cmp_buf
+ 2, cmp_buf
+ 4) <= 0)
3889 match_len
= char_len
;
3890 goto check_node_accept_bytes_match
;
3894 check_node_accept_bytes_match
:
3895 if (!cset
->non_match
)
3902 return (elem_len
> char_len
) ? elem_len
: char_len
;
3910 find_collation_sequence_value (mbs
, mbs_len
)
3911 const unsigned char *mbs
;
3914 uint32_t nrules
= _NL_CURRENT_WORD (LC_COLLATE
, _NL_COLLATE_NRULES
);
3919 /* No valid character. Match it as a single byte character. */
3920 const unsigned char *collseq
= (const unsigned char *)
3921 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_COLLSEQMB
);
3922 return collseq
[mbs
[0]];
3929 const unsigned char *extra
= (const unsigned char *)
3930 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_SYMB_EXTRAMB
);
3931 int32_t extrasize
= (const unsigned char *)
3932 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_SYMB_EXTRAMB
+ 1) - extra
;
3934 for (idx
= 0; idx
< extrasize
;)
3936 int mbs_cnt
, found
= 0;
3937 int32_t elem_mbs_len
;
3938 /* Skip the name of collating element name. */
3939 idx
= idx
+ extra
[idx
] + 1;
3940 elem_mbs_len
= extra
[idx
++];
3941 if (mbs_len
== elem_mbs_len
)
3943 for (mbs_cnt
= 0; mbs_cnt
< elem_mbs_len
; ++mbs_cnt
)
3944 if (extra
[idx
+ mbs_cnt
] != mbs
[mbs_cnt
])
3946 if (mbs_cnt
== elem_mbs_len
)
3947 /* Found the entry. */
3950 /* Skip the byte sequence of the collating element. */
3951 idx
+= elem_mbs_len
;
3952 /* Adjust for the alignment. */
3953 idx
= (idx
+ 3) & ~3;
3954 /* Skip the collation sequence value. */
3955 idx
+= sizeof (uint32_t);
3956 /* Skip the wide char sequence of the collating element. */
3957 idx
= idx
+ sizeof (uint32_t) * (extra
[idx
] + 1);
3958 /* If we found the entry, return the sequence value. */
3960 return *(uint32_t *) (extra
+ idx
);
3961 /* Skip the collation sequence value. */
3962 idx
+= sizeof (uint32_t);
3968 #endif /* RE_ENABLE_I18N */
3970 /* Check whether the node accepts the byte which is IDX-th
3971 byte of the INPUT. */
3974 check_node_accept (mctx
, node
, idx
)
3975 const re_match_context_t
*mctx
;
3976 const re_token_t
*node
;
3979 re_dfa_t
*const dfa
= mctx
->dfa
;
3981 if (node
->constraint
)
3983 /* The node has constraints. Check whether the current context
3984 satisfies the constraints. */
3985 unsigned int context
= re_string_context_at (&mctx
->input
, idx
,
3987 if (NOT_SATISFY_NEXT_CONSTRAINT (node
->constraint
, context
))
3990 ch
= re_string_byte_at (&mctx
->input
, idx
);
3994 return node
->opr
.c
== ch
;
3995 case SIMPLE_BRACKET
:
3996 return bitset_contain (node
->opr
.sbcset
, ch
);
3997 #ifdef RE_ENABLE_I18N
3998 case OP_UTF8_PERIOD
:
4004 return !((ch
== '\n' && !(dfa
->syntax
& RE_DOT_NEWLINE
))
4005 || (ch
== '\0' && (dfa
->syntax
& RE_DOT_NOT_NULL
)));
4011 /* Extend the buffers, if the buffers have run out. */
4013 static reg_errcode_t
4014 extend_buffers (mctx
)
4015 re_match_context_t
*mctx
;
4018 re_string_t
*pstr
= &mctx
->input
;
4020 /* Double the lengthes of the buffers. */
4021 ret
= re_string_realloc_buffers (pstr
, pstr
->bufs_len
* 2);
4022 if (BE (ret
!= REG_NOERROR
, 0))
4025 if (mctx
->state_log
!= NULL
)
4027 /* And double the length of state_log. */
4028 /* XXX We have no indication of the size of this buffer. If this
4029 allocation fail we have no indication that the state_log array
4030 does not have the right size. */
4031 re_dfastate_t
**new_array
= re_realloc (mctx
->state_log
, re_dfastate_t
*,
4032 pstr
->bufs_len
+ 1);
4033 if (BE (new_array
== NULL
, 0))
4035 mctx
->state_log
= new_array
;
4038 /* Then reconstruct the buffers. */
4041 #ifdef RE_ENABLE_I18N
4042 if (pstr
->mb_cur_max
> 1)
4044 ret
= build_wcs_upper_buffer (pstr
);
4045 if (BE (ret
!= REG_NOERROR
, 0))
4049 #endif /* RE_ENABLE_I18N */
4050 build_upper_buffer (pstr
);
4054 #ifdef RE_ENABLE_I18N
4055 if (pstr
->mb_cur_max
> 1)
4056 build_wcs_buffer (pstr
);
4058 #endif /* RE_ENABLE_I18N */
4060 if (pstr
->trans
!= NULL
)
4061 re_string_translate_buffer (pstr
);
4068 /* Functions for matching context. */
4070 /* Initialize MCTX. */
4072 static reg_errcode_t
4073 match_ctx_init (mctx
, eflags
, n
)
4074 re_match_context_t
*mctx
;
4077 mctx
->eflags
= eflags
;
4078 mctx
->match_last
= -1;
4081 mctx
->bkref_ents
= re_malloc (struct re_backref_cache_entry
, n
);
4082 mctx
->sub_tops
= re_malloc (re_sub_match_top_t
*, n
);
4083 if (BE (mctx
->bkref_ents
== NULL
|| mctx
->sub_tops
== NULL
, 0))
4086 /* Already zero-ed by the caller.
4088 mctx->bkref_ents = NULL;
4089 mctx->nbkref_ents = 0;
4090 mctx->nsub_tops = 0; */
4091 mctx
->abkref_ents
= n
;
4092 mctx
->max_mb_elem_len
= 1;
4093 mctx
->asub_tops
= n
;
4097 /* Clean the entries which depend on the current input in MCTX.
4098 This function must be invoked when the matcher changes the start index
4099 of the input, or changes the input string. */
4102 match_ctx_clean (mctx
)
4103 re_match_context_t
*mctx
;
4105 match_ctx_free_subtops (mctx
);
4106 mctx
->nsub_tops
= 0;
4107 mctx
->nbkref_ents
= 0;
4110 /* Free all the memory associated with MCTX. */
4113 match_ctx_free (mctx
)
4114 re_match_context_t
*mctx
;
4116 match_ctx_free_subtops (mctx
);
4117 re_free (mctx
->sub_tops
);
4118 re_free (mctx
->bkref_ents
);
4121 /* Free all the memory associated with MCTX->SUB_TOPS. */
4124 match_ctx_free_subtops (mctx
)
4125 re_match_context_t
*mctx
;
4128 for (st_idx
= 0; st_idx
< mctx
->nsub_tops
; ++st_idx
)
4131 re_sub_match_top_t
*top
= mctx
->sub_tops
[st_idx
];
4132 for (sl_idx
= 0; sl_idx
< top
->nlasts
; ++sl_idx
)
4134 re_sub_match_last_t
*last
= top
->lasts
[sl_idx
];
4135 re_free (last
->path
.array
);
4138 re_free (top
->lasts
);
4141 re_free (top
->path
->array
);
4142 re_free (top
->path
);
4148 /* Add a new backreference entry to MCTX.
4149 Note that we assume that caller never call this function with duplicate
4150 entry, and call with STR_IDX which isn't smaller than any existing entry.
4153 static reg_errcode_t
4154 match_ctx_add_entry (mctx
, node
, str_idx
, from
, to
)
4155 re_match_context_t
*mctx
;
4156 int node
, str_idx
, from
, to
;
4158 if (mctx
->nbkref_ents
>= mctx
->abkref_ents
)
4160 struct re_backref_cache_entry
* new_entry
;
4161 new_entry
= re_realloc (mctx
->bkref_ents
, struct re_backref_cache_entry
,
4162 mctx
->abkref_ents
* 2);
4163 if (BE (new_entry
== NULL
, 0))
4165 re_free (mctx
->bkref_ents
);
4168 mctx
->bkref_ents
= new_entry
;
4169 memset (mctx
->bkref_ents
+ mctx
->nbkref_ents
, '\0',
4170 sizeof (struct re_backref_cache_entry
) * mctx
->abkref_ents
);
4171 mctx
->abkref_ents
*= 2;
4173 if (mctx
->nbkref_ents
> 0
4174 && mctx
->bkref_ents
[mctx
->nbkref_ents
- 1].str_idx
== str_idx
)
4175 mctx
->bkref_ents
[mctx
->nbkref_ents
- 1].more
= 1;
4177 mctx
->bkref_ents
[mctx
->nbkref_ents
].node
= node
;
4178 mctx
->bkref_ents
[mctx
->nbkref_ents
].str_idx
= str_idx
;
4179 mctx
->bkref_ents
[mctx
->nbkref_ents
].subexp_from
= from
;
4180 mctx
->bkref_ents
[mctx
->nbkref_ents
].subexp_to
= to
;
4181 mctx
->bkref_ents
[mctx
->nbkref_ents
++].more
= 0;
4182 if (mctx
->max_mb_elem_len
< to
- from
)
4183 mctx
->max_mb_elem_len
= to
- from
;
4187 /* Search for the first entry which has the same str_idx, or -1 if none is
4188 found. Note that MCTX->BKREF_ENTS is already sorted by MCTX->STR_IDX. */
4191 search_cur_bkref_entry (mctx
, str_idx
)
4192 re_match_context_t
*mctx
;
4195 int left
, right
, mid
, last
;
4196 last
= right
= mctx
->nbkref_ents
;
4197 for (left
= 0; left
< right
;)
4199 mid
= (left
+ right
) / 2;
4200 if (mctx
->bkref_ents
[mid
].str_idx
< str_idx
)
4205 if (left
< last
&& mctx
->bkref_ents
[left
].str_idx
== str_idx
)
4211 /* Register the node NODE, whose type is OP_OPEN_SUBEXP, and which matches
4214 static reg_errcode_t
4215 match_ctx_add_subtop (mctx
, node
, str_idx
)
4216 re_match_context_t
*mctx
;
4220 assert (mctx
->sub_tops
!= NULL
);
4221 assert (mctx
->asub_tops
> 0);
4223 if (BE (mctx
->nsub_tops
== mctx
->asub_tops
, 0))
4225 int new_asub_tops
= mctx
->asub_tops
* 2;
4226 re_sub_match_top_t
**new_array
= re_realloc (mctx
->sub_tops
,
4227 re_sub_match_top_t
*,
4229 if (BE (new_array
== NULL
, 0))
4231 mctx
->sub_tops
= new_array
;
4232 mctx
->asub_tops
= new_asub_tops
;
4234 mctx
->sub_tops
[mctx
->nsub_tops
] = calloc (1, sizeof (re_sub_match_top_t
));
4235 if (BE (mctx
->sub_tops
[mctx
->nsub_tops
] == NULL
, 0))
4237 mctx
->sub_tops
[mctx
->nsub_tops
]->node
= node
;
4238 mctx
->sub_tops
[mctx
->nsub_tops
++]->str_idx
= str_idx
;
4242 /* Register the node NODE, whose type is OP_CLOSE_SUBEXP, and which matches
4243 at STR_IDX, whose corresponding OP_OPEN_SUBEXP is SUB_TOP. */
4245 static re_sub_match_last_t
*
4246 match_ctx_add_sublast (subtop
, node
, str_idx
)
4247 re_sub_match_top_t
*subtop
;
4250 re_sub_match_last_t
*new_entry
;
4251 if (BE (subtop
->nlasts
== subtop
->alasts
, 0))
4253 int new_alasts
= 2 * subtop
->alasts
+ 1;
4254 re_sub_match_last_t
**new_array
= re_realloc (subtop
->lasts
,
4255 re_sub_match_last_t
*,
4257 if (BE (new_array
== NULL
, 0))
4259 subtop
->lasts
= new_array
;
4260 subtop
->alasts
= new_alasts
;
4262 new_entry
= calloc (1, sizeof (re_sub_match_last_t
));
4263 if (BE (new_entry
!= NULL
, 1))
4265 subtop
->lasts
[subtop
->nlasts
] = new_entry
;
4266 new_entry
->node
= node
;
4267 new_entry
->str_idx
= str_idx
;
4274 sift_ctx_init (sctx
, sifted_sts
, limited_sts
, last_node
, last_str_idx
)
4275 re_sift_context_t
*sctx
;
4276 re_dfastate_t
**sifted_sts
, **limited_sts
;
4277 int last_node
, last_str_idx
;
4279 sctx
->sifted_states
= sifted_sts
;
4280 sctx
->limited_states
= limited_sts
;
4281 sctx
->last_node
= last_node
;
4282 sctx
->last_str_idx
= last_str_idx
;
4283 re_node_set_init_empty (&sctx
->limits
);