1 /* Extended regular expression matching and search library.
2 Copyright (C) 2002, 2003, 2004, 2005, 2007 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
4 Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>.
6 The GNU C Library is free software; you can redistribute it and/or
7 modify it under the terms of the GNU Lesser General Public
8 License as published by the Free Software Foundation; either
9 version 2.1 of the License, or (at your option) any later version.
11 The GNU C Library is distributed in the hope that it will be useful,
12 but WITHOUT ANY WARRANTY; without even the implied warranty of
13 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
14 Lesser General Public License for more details.
16 You should have received a copy of the GNU Lesser General Public
17 License along with the GNU C Library; if not, write to the Free
18 Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
21 static reg_errcode_t
match_ctx_init (re_match_context_t
*cache
, int eflags
,
22 int n
) internal_function
;
23 static void match_ctx_clean (re_match_context_t
*mctx
) internal_function
;
24 static void match_ctx_free (re_match_context_t
*cache
) internal_function
;
25 static reg_errcode_t
match_ctx_add_entry (re_match_context_t
*cache
, int node
,
26 int str_idx
, int from
, int to
)
28 static int search_cur_bkref_entry (const re_match_context_t
*mctx
, int str_idx
)
30 static reg_errcode_t
match_ctx_add_subtop (re_match_context_t
*mctx
, int node
,
31 int str_idx
) internal_function
;
32 static re_sub_match_last_t
* match_ctx_add_sublast (re_sub_match_top_t
*subtop
,
33 int node
, int str_idx
)
35 static void sift_ctx_init (re_sift_context_t
*sctx
, re_dfastate_t
**sifted_sts
,
36 re_dfastate_t
**limited_sts
, int last_node
,
39 static reg_errcode_t
re_search_internal (const regex_t
*preg
,
40 const char *string
, int length
,
41 int start
, int range
, int stop
,
42 size_t nmatch
, regmatch_t pmatch
[],
43 int eflags
) internal_function
;
44 static int re_search_2_stub (struct re_pattern_buffer
*bufp
,
45 const char *string1
, int length1
,
46 const char *string2
, int length2
,
47 int start
, int range
, struct re_registers
*regs
,
48 int stop
, int ret_len
) internal_function
;
49 static int re_search_stub (struct re_pattern_buffer
*bufp
,
50 const char *string
, int length
, int start
,
51 int range
, int stop
, struct re_registers
*regs
,
52 int ret_len
) internal_function
;
53 static unsigned re_copy_regs (struct re_registers
*regs
, regmatch_t
*pmatch
,
54 int nregs
, int regs_allocated
) internal_function
;
55 static reg_errcode_t
prune_impossible_nodes (re_match_context_t
*mctx
)
57 static int check_matching (re_match_context_t
*mctx
, int fl_longest_match
,
58 int *p_match_first
) internal_function
;
59 static int check_halt_state_context (const re_match_context_t
*mctx
,
60 const re_dfastate_t
*state
, int idx
)
62 static void update_regs (const re_dfa_t
*dfa
, regmatch_t
*pmatch
,
63 regmatch_t
*prev_idx_match
, int cur_node
,
64 int cur_idx
, int nmatch
) internal_function
;
65 static reg_errcode_t
push_fail_stack (struct re_fail_stack_t
*fs
,
66 int str_idx
, int dest_node
, int nregs
,
68 re_node_set
*eps_via_nodes
)
70 static reg_errcode_t
set_regs (const regex_t
*preg
,
71 const re_match_context_t
*mctx
,
72 size_t nmatch
, regmatch_t
*pmatch
,
73 int fl_backtrack
) internal_function
;
74 static reg_errcode_t
free_fail_stack_return (struct re_fail_stack_t
*fs
)
78 static int sift_states_iter_mb (const re_match_context_t
*mctx
,
79 re_sift_context_t
*sctx
,
80 int node_idx
, int str_idx
, int max_str_idx
)
82 #endif /* RE_ENABLE_I18N */
83 static reg_errcode_t
sift_states_backward (const re_match_context_t
*mctx
,
84 re_sift_context_t
*sctx
)
86 static reg_errcode_t
build_sifted_states (const re_match_context_t
*mctx
,
87 re_sift_context_t
*sctx
, int str_idx
,
88 re_node_set
*cur_dest
)
90 static reg_errcode_t
update_cur_sifted_state (const re_match_context_t
*mctx
,
91 re_sift_context_t
*sctx
,
93 re_node_set
*dest_nodes
)
95 static reg_errcode_t
add_epsilon_src_nodes (const re_dfa_t
*dfa
,
96 re_node_set
*dest_nodes
,
97 const re_node_set
*candidates
)
99 static int check_dst_limits (const re_match_context_t
*mctx
,
101 int dst_node
, int dst_idx
, int src_node
,
102 int src_idx
) internal_function
;
103 static int check_dst_limits_calc_pos_1 (const re_match_context_t
*mctx
,
104 int boundaries
, int subexp_idx
,
105 int from_node
, int bkref_idx
)
107 static int check_dst_limits_calc_pos (const re_match_context_t
*mctx
,
108 int limit
, int subexp_idx
,
109 int node
, int str_idx
,
110 int bkref_idx
) internal_function
;
111 static reg_errcode_t
check_subexp_limits (const re_dfa_t
*dfa
,
112 re_node_set
*dest_nodes
,
113 const re_node_set
*candidates
,
115 struct re_backref_cache_entry
*bkref_ents
,
116 int str_idx
) internal_function
;
117 static reg_errcode_t
sift_states_bkref (const re_match_context_t
*mctx
,
118 re_sift_context_t
*sctx
,
119 int str_idx
, const re_node_set
*candidates
)
121 static reg_errcode_t
merge_state_array (const re_dfa_t
*dfa
,
123 re_dfastate_t
**src
, int num
)
125 static re_dfastate_t
*find_recover_state (reg_errcode_t
*err
,
126 re_match_context_t
*mctx
) internal_function
;
127 static re_dfastate_t
*transit_state (reg_errcode_t
*err
,
128 re_match_context_t
*mctx
,
129 re_dfastate_t
*state
) internal_function
;
130 static re_dfastate_t
*merge_state_with_log (reg_errcode_t
*err
,
131 re_match_context_t
*mctx
,
132 re_dfastate_t
*next_state
)
134 static reg_errcode_t
check_subexp_matching_top (re_match_context_t
*mctx
,
135 re_node_set
*cur_nodes
,
136 int str_idx
) internal_function
;
138 static re_dfastate_t
*transit_state_sb (reg_errcode_t
*err
,
139 re_match_context_t
*mctx
,
140 re_dfastate_t
*pstate
)
143 #ifdef RE_ENABLE_I18N
144 static reg_errcode_t
transit_state_mb (re_match_context_t
*mctx
,
145 re_dfastate_t
*pstate
)
147 #endif /* RE_ENABLE_I18N */
148 static reg_errcode_t
transit_state_bkref (re_match_context_t
*mctx
,
149 const re_node_set
*nodes
)
151 static reg_errcode_t
get_subexp (re_match_context_t
*mctx
,
152 int bkref_node
, int bkref_str_idx
)
154 static reg_errcode_t
get_subexp_sub (re_match_context_t
*mctx
,
155 const re_sub_match_top_t
*sub_top
,
156 re_sub_match_last_t
*sub_last
,
157 int bkref_node
, int bkref_str
)
159 static int find_subexp_node (const re_dfa_t
*dfa
, const re_node_set
*nodes
,
160 int subexp_idx
, int type
) internal_function
;
161 static reg_errcode_t
check_arrival (re_match_context_t
*mctx
,
162 state_array_t
*path
, int top_node
,
163 int top_str
, int last_node
, int last_str
,
164 int type
) internal_function
;
165 static reg_errcode_t
check_arrival_add_next_nodes (re_match_context_t
*mctx
,
167 re_node_set
*cur_nodes
,
168 re_node_set
*next_nodes
)
170 static reg_errcode_t
check_arrival_expand_ecl (const re_dfa_t
*dfa
,
171 re_node_set
*cur_nodes
,
172 int ex_subexp
, int type
)
174 static reg_errcode_t
check_arrival_expand_ecl_sub (const re_dfa_t
*dfa
,
175 re_node_set
*dst_nodes
,
176 int target
, int ex_subexp
,
177 int type
) internal_function
;
178 static reg_errcode_t
expand_bkref_cache (re_match_context_t
*mctx
,
179 re_node_set
*cur_nodes
, int cur_str
,
180 int subexp_num
, int type
)
182 static int build_trtable (const re_dfa_t
*dfa
,
183 re_dfastate_t
*state
) internal_function
;
184 #ifdef RE_ENABLE_I18N
185 static int check_node_accept_bytes (const re_dfa_t
*dfa
, int node_idx
,
186 const re_string_t
*input
, int idx
)
189 static unsigned int find_collation_sequence_value (const unsigned char *mbs
,
193 #endif /* RE_ENABLE_I18N */
194 static int group_nodes_into_DFAstates (const re_dfa_t
*dfa
,
195 const re_dfastate_t
*state
,
196 re_node_set
*states_node
,
197 bitset_t
*states_ch
) internal_function
;
198 static int check_node_accept (const re_match_context_t
*mctx
,
199 const re_token_t
*node
, int idx
)
201 static reg_errcode_t
extend_buffers (re_match_context_t
*mctx
)
204 /* Entry point for POSIX code. */
206 /* regexec searches for a given pattern, specified by PREG, in the
209 If NMATCH is zero or REG_NOSUB was set in the cflags argument to
210 `regcomp', we ignore PMATCH. Otherwise, we assume PMATCH has at
211 least NMATCH elements, and we set them to the offsets of the
212 corresponding matched substrings.
214 EFLAGS specifies `execution flags' which affect matching: if
215 REG_NOTBOL is set, then ^ does not match at the beginning of the
216 string; if REG_NOTEOL is set, then $ does not match at the end.
218 We return 0 if we find a match and REG_NOMATCH if not. */
221 regexec (preg
, string
, nmatch
, pmatch
, eflags
)
222 const regex_t
*__restrict preg
;
223 const char *__restrict string
;
231 re_dfa_t
*dfa
= (re_dfa_t
*) preg
->buffer
;
234 if (eflags
& ~(REG_NOTBOL
| REG_NOTEOL
| REG_STARTEND
))
237 if (eflags
& REG_STARTEND
)
239 start
= pmatch
[0].rm_so
;
240 length
= pmatch
[0].rm_eo
;
245 length
= strlen (string
);
248 __libc_lock_lock (dfa
->lock
);
250 err
= re_search_internal (preg
, string
, length
, start
, length
- start
,
251 length
, 0, NULL
, eflags
);
253 err
= re_search_internal (preg
, string
, length
, start
, length
- start
,
254 length
, nmatch
, pmatch
, eflags
);
255 __libc_lock_unlock (dfa
->lock
);
256 return err
!= REG_NOERROR
;
260 # include <shlib-compat.h>
261 versioned_symbol (libc
, __regexec
, regexec
, GLIBC_2_3_4
);
263 # if SHLIB_COMPAT (libc, GLIBC_2_0, GLIBC_2_3_4)
264 __typeof__ (__regexec
) __compat_regexec
;
267 attribute_compat_text_section
268 __compat_regexec (const regex_t
*__restrict preg
,
269 const char *__restrict string
, size_t nmatch
,
270 regmatch_t pmatch
[], int eflags
)
272 return regexec (preg
, string
, nmatch
, pmatch
,
273 eflags
& (REG_NOTBOL
| REG_NOTEOL
));
275 compat_symbol (libc
, __compat_regexec
, regexec
, GLIBC_2_0
);
279 /* Entry points for GNU code. */
281 /* re_match, re_search, re_match_2, re_search_2
283 The former two functions operate on STRING with length LENGTH,
284 while the later two operate on concatenation of STRING1 and STRING2
285 with lengths LENGTH1 and LENGTH2, respectively.
287 re_match() matches the compiled pattern in BUFP against the string,
288 starting at index START.
290 re_search() first tries matching at index START, then it tries to match
291 starting from index START + 1, and so on. The last start position tried
292 is START + RANGE. (Thus RANGE = 0 forces re_search to operate the same
295 The parameter STOP of re_{match,search}_2 specifies that no match exceeding
296 the first STOP characters of the concatenation of the strings should be
299 If REGS is not NULL, and BUFP->no_sub is not set, the offsets of the match
300 and all groups is stroed in REGS. (For the "_2" variants, the offsets are
301 computed relative to the concatenation, not relative to the individual
304 On success, re_match* functions return the length of the match, re_search*
305 return the position of the start of the match. Return value -1 means no
306 match was found and -2 indicates an internal error. */
309 re_match (bufp
, string
, length
, start
, regs
)
310 struct re_pattern_buffer
*bufp
;
313 struct re_registers
*regs
;
315 return re_search_stub (bufp
, string
, length
, start
, 0, length
, regs
, 1);
318 weak_alias (__re_match
, re_match
)
322 re_search (bufp
, string
, length
, start
, range
, regs
)
323 struct re_pattern_buffer
*bufp
;
325 int length
, start
, range
;
326 struct re_registers
*regs
;
328 return re_search_stub (bufp
, string
, length
, start
, range
, length
, regs
, 0);
331 weak_alias (__re_search
, re_search
)
335 re_match_2 (bufp
, string1
, length1
, string2
, length2
, start
, regs
, stop
)
336 struct re_pattern_buffer
*bufp
;
337 const char *string1
, *string2
;
338 int length1
, length2
, start
, stop
;
339 struct re_registers
*regs
;
341 return re_search_2_stub (bufp
, string1
, length1
, string2
, length2
,
342 start
, 0, regs
, stop
, 1);
345 weak_alias (__re_match_2
, re_match_2
)
349 re_search_2 (bufp
, string1
, length1
, string2
, length2
, start
, range
, regs
, stop
)
350 struct re_pattern_buffer
*bufp
;
351 const char *string1
, *string2
;
352 int length1
, length2
, start
, range
, stop
;
353 struct re_registers
*regs
;
355 return re_search_2_stub (bufp
, string1
, length1
, string2
, length2
,
356 start
, range
, regs
, stop
, 0);
359 weak_alias (__re_search_2
, re_search_2
)
363 re_search_2_stub (bufp
, string1
, length1
, string2
, length2
, start
, range
, regs
,
365 struct re_pattern_buffer
*bufp
;
366 const char *string1
, *string2
;
367 int length1
, length2
, start
, range
, stop
, ret_len
;
368 struct re_registers
*regs
;
372 int len
= length1
+ length2
;
375 if (BE (length1
< 0 || length2
< 0 || stop
< 0, 0))
378 /* Concatenate the strings. */
382 char *s
= re_malloc (char, len
);
384 if (BE (s
== NULL
, 0))
387 memcpy (__mempcpy (s
, string1
, length1
), string2
, length2
);
389 memcpy (s
, string1
, length1
);
390 memcpy (s
+ length1
, string2
, length2
);
400 rval
= re_search_stub (bufp
, str
, len
, start
, range
, stop
, regs
,
403 re_free ((char *) str
);
407 /* The parameters have the same meaning as those of re_search.
408 Additional parameters:
409 If RET_LEN is nonzero the length of the match is returned (re_match style);
410 otherwise the position of the match is returned. */
413 re_search_stub (bufp
, string
, length
, start
, range
, stop
, regs
, ret_len
)
414 struct re_pattern_buffer
*bufp
;
416 int length
, start
, range
, stop
, ret_len
;
417 struct re_registers
*regs
;
419 reg_errcode_t result
;
424 re_dfa_t
*dfa
= (re_dfa_t
*) bufp
->buffer
;
427 /* Check for out-of-range. */
428 if (BE (start
< 0 || start
> length
, 0))
430 if (BE (start
+ range
> length
, 0))
431 range
= length
- start
;
432 else if (BE (start
+ range
< 0, 0))
435 __libc_lock_lock (dfa
->lock
);
437 eflags
|= (bufp
->not_bol
) ? REG_NOTBOL
: 0;
438 eflags
|= (bufp
->not_eol
) ? REG_NOTEOL
: 0;
440 /* Compile fastmap if we haven't yet. */
441 if (range
> 0 && bufp
->fastmap
!= NULL
&& !bufp
->fastmap_accurate
)
442 re_compile_fastmap (bufp
);
444 if (BE (bufp
->no_sub
, 0))
447 /* We need at least 1 register. */
450 else if (BE (bufp
->regs_allocated
== REGS_FIXED
&&
451 regs
->num_regs
< bufp
->re_nsub
+ 1, 0))
453 nregs
= regs
->num_regs
;
454 if (BE (nregs
< 1, 0))
456 /* Nothing can be copied to regs. */
462 nregs
= bufp
->re_nsub
+ 1;
463 pmatch
= re_malloc (regmatch_t
, nregs
);
464 if (BE (pmatch
== NULL
, 0))
470 result
= re_search_internal (bufp
, string
, length
, start
, range
, stop
,
471 nregs
, pmatch
, eflags
);
475 /* I hope we needn't fill ther regs with -1's when no match was found. */
476 if (result
!= REG_NOERROR
)
478 else if (regs
!= NULL
)
480 /* If caller wants register contents data back, copy them. */
481 bufp
->regs_allocated
= re_copy_regs (regs
, pmatch
, nregs
,
482 bufp
->regs_allocated
);
483 if (BE (bufp
->regs_allocated
== REGS_UNALLOCATED
, 0))
487 if (BE (rval
== 0, 1))
491 assert (pmatch
[0].rm_so
== start
);
492 rval
= pmatch
[0].rm_eo
- start
;
495 rval
= pmatch
[0].rm_so
;
499 __libc_lock_unlock (dfa
->lock
);
504 re_copy_regs (regs
, pmatch
, nregs
, regs_allocated
)
505 struct re_registers
*regs
;
507 int nregs
, regs_allocated
;
509 int rval
= REGS_REALLOCATE
;
511 int need_regs
= nregs
+ 1;
512 /* We need one extra element beyond `num_regs' for the `-1' marker GNU code
515 /* Have the register data arrays been allocated? */
516 if (regs_allocated
== REGS_UNALLOCATED
)
517 { /* No. So allocate them with malloc. */
518 regs
->start
= re_malloc (regoff_t
, need_regs
);
519 regs
->end
= re_malloc (regoff_t
, need_regs
);
520 if (BE (regs
->start
== NULL
, 0) || BE (regs
->end
== NULL
, 0))
521 return REGS_UNALLOCATED
;
522 regs
->num_regs
= need_regs
;
524 else if (regs_allocated
== REGS_REALLOCATE
)
525 { /* Yes. If we need more elements than were already
526 allocated, reallocate them. If we need fewer, just
528 if (BE (need_regs
> regs
->num_regs
, 0))
530 regoff_t
*new_start
= re_realloc (regs
->start
, regoff_t
, need_regs
);
531 regoff_t
*new_end
= re_realloc (regs
->end
, regoff_t
, need_regs
);
532 if (BE (new_start
== NULL
, 0) || BE (new_end
== NULL
, 0))
533 return REGS_UNALLOCATED
;
534 regs
->start
= new_start
;
536 regs
->num_regs
= need_regs
;
541 assert (regs_allocated
== REGS_FIXED
);
542 /* This function may not be called with REGS_FIXED and nregs too big. */
543 assert (regs
->num_regs
>= nregs
);
548 for (i
= 0; i
< nregs
; ++i
)
550 regs
->start
[i
] = pmatch
[i
].rm_so
;
551 regs
->end
[i
] = pmatch
[i
].rm_eo
;
553 for ( ; i
< regs
->num_regs
; ++i
)
554 regs
->start
[i
] = regs
->end
[i
] = -1;
559 /* Set REGS to hold NUM_REGS registers, storing them in STARTS and
560 ENDS. Subsequent matches using PATTERN_BUFFER and REGS will use
561 this memory for recording register information. STARTS and ENDS
562 must be allocated using the malloc library routine, and must each
563 be at least NUM_REGS * sizeof (regoff_t) bytes long.
565 If NUM_REGS == 0, then subsequent matches should allocate their own
568 Unless this function is called, the first search or match using
569 PATTERN_BUFFER will allocate its own register data, without
570 freeing the old data. */
573 re_set_registers (bufp
, regs
, num_regs
, starts
, ends
)
574 struct re_pattern_buffer
*bufp
;
575 struct re_registers
*regs
;
577 regoff_t
*starts
, *ends
;
581 bufp
->regs_allocated
= REGS_REALLOCATE
;
582 regs
->num_regs
= num_regs
;
583 regs
->start
= starts
;
588 bufp
->regs_allocated
= REGS_UNALLOCATED
;
590 regs
->start
= regs
->end
= (regoff_t
*) 0;
594 weak_alias (__re_set_registers
, re_set_registers
)
597 /* Entry points compatible with 4.2 BSD regex library. We don't define
598 them unless specifically requested. */
600 #if defined _REGEX_RE_COMP || defined _LIBC
608 return 0 == regexec (&re_comp_buf
, s
, 0, NULL
, 0);
610 #endif /* _REGEX_RE_COMP */
612 /* Internal entry point. */
614 /* Searches for a compiled pattern PREG in the string STRING, whose
615 length is LENGTH. NMATCH, PMATCH, and EFLAGS have the same
616 mingings with regexec. START, and RANGE have the same meanings
618 Return REG_NOERROR if we find a match, and REG_NOMATCH if not,
619 otherwise return the error code.
620 Note: We assume front end functions already check ranges.
621 (START + RANGE >= 0 && START + RANGE <= LENGTH) */
624 re_search_internal (preg
, string
, length
, start
, range
, stop
, nmatch
, pmatch
,
628 int length
, start
, range
, stop
, eflags
;
633 const re_dfa_t
*dfa
= (const re_dfa_t
*) preg
->buffer
;
634 int left_lim
, right_lim
, incr
;
635 int fl_longest_match
, match_first
, match_kind
, match_last
= -1;
638 #if defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L)
639 re_match_context_t mctx
= { .dfa
= dfa
};
641 re_match_context_t mctx
;
643 char *fastmap
= (preg
->fastmap
!= NULL
&& preg
->fastmap_accurate
644 && range
&& !preg
->can_be_null
) ? preg
->fastmap
: NULL
;
645 RE_TRANSLATE_TYPE t
= preg
->translate
;
647 #if !(defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L))
648 memset (&mctx
, '\0', sizeof (re_match_context_t
));
652 extra_nmatch
= (nmatch
> preg
->re_nsub
) ? nmatch
- (preg
->re_nsub
+ 1) : 0;
653 nmatch
-= extra_nmatch
;
655 /* Check if the DFA haven't been compiled. */
656 if (BE (preg
->used
== 0 || dfa
->init_state
== NULL
657 || dfa
->init_state_word
== NULL
|| dfa
->init_state_nl
== NULL
658 || dfa
->init_state_begbuf
== NULL
, 0))
662 /* We assume front-end functions already check them. */
663 assert (start
+ range
>= 0 && start
+ range
<= length
);
666 /* If initial states with non-begbuf contexts have no elements,
667 the regex must be anchored. If preg->newline_anchor is set,
668 we'll never use init_state_nl, so do not check it. */
669 if (dfa
->init_state
->nodes
.nelem
== 0
670 && dfa
->init_state_word
->nodes
.nelem
== 0
671 && (dfa
->init_state_nl
->nodes
.nelem
== 0
672 || !preg
->newline_anchor
))
674 if (start
!= 0 && start
+ range
!= 0)
679 /* We must check the longest matching, if nmatch > 0. */
680 fl_longest_match
= (nmatch
!= 0 || dfa
->nbackref
);
682 err
= re_string_allocate (&mctx
.input
, string
, length
, dfa
->nodes_len
+ 1,
683 preg
->translate
, preg
->syntax
& RE_ICASE
, dfa
);
684 if (BE (err
!= REG_NOERROR
, 0))
686 mctx
.input
.stop
= stop
;
687 mctx
.input
.raw_stop
= stop
;
688 mctx
.input
.newline_anchor
= preg
->newline_anchor
;
690 err
= match_ctx_init (&mctx
, eflags
, dfa
->nbackref
* 2);
691 if (BE (err
!= REG_NOERROR
, 0))
694 /* We will log all the DFA states through which the dfa pass,
695 if nmatch > 1, or this dfa has "multibyte node", which is a
696 back-reference or a node which can accept multibyte character or
697 multi character collating element. */
698 if (nmatch
> 1 || dfa
->has_mb_node
)
700 mctx
.state_log
= re_malloc (re_dfastate_t
*, mctx
.input
.bufs_len
+ 1);
701 if (BE (mctx
.state_log
== NULL
, 0))
708 mctx
.state_log
= NULL
;
711 mctx
.input
.tip_context
= (eflags
& REG_NOTBOL
) ? CONTEXT_BEGBUF
712 : CONTEXT_NEWLINE
| CONTEXT_BEGBUF
;
714 /* Check incrementally whether of not the input string match. */
715 incr
= (range
< 0) ? -1 : 1;
716 left_lim
= (range
< 0) ? start
+ range
: start
;
717 right_lim
= (range
< 0) ? start
: start
+ range
;
718 sb
= dfa
->mb_cur_max
== 1;
721 ? ((sb
|| !(preg
->syntax
& RE_ICASE
|| t
) ? 4 : 0)
722 | (range
>= 0 ? 2 : 0)
723 | (t
!= NULL
? 1 : 0))
726 for (;; match_first
+= incr
)
729 if (match_first
< left_lim
|| right_lim
< match_first
)
732 /* Advance as rapidly as possible through the string, until we
733 find a plausible place to start matching. This may be done
734 with varying efficiency, so there are various possibilities:
735 only the most common of them are specialized, in order to
736 save on code size. We use a switch statement for speed. */
744 /* Fastmap with single-byte translation, match forward. */
745 while (BE (match_first
< right_lim
, 1)
746 && !fastmap
[t
[(unsigned char) string
[match_first
]]])
748 goto forward_match_found_start_or_reached_end
;
751 /* Fastmap without translation, match forward. */
752 while (BE (match_first
< right_lim
, 1)
753 && !fastmap
[(unsigned char) string
[match_first
]])
756 forward_match_found_start_or_reached_end
:
757 if (BE (match_first
== right_lim
, 0))
759 ch
= match_first
>= length
760 ? 0 : (unsigned char) string
[match_first
];
761 if (!fastmap
[t
? t
[ch
] : ch
])
768 /* Fastmap without multi-byte translation, match backwards. */
769 while (match_first
>= left_lim
)
771 ch
= match_first
>= length
772 ? 0 : (unsigned char) string
[match_first
];
773 if (fastmap
[t
? t
[ch
] : ch
])
777 if (match_first
< left_lim
)
782 /* In this case, we can't determine easily the current byte,
783 since it might be a component byte of a multibyte
784 character. Then we use the constructed buffer instead. */
787 /* If MATCH_FIRST is out of the valid range, reconstruct the
789 unsigned int offset
= match_first
- mctx
.input
.raw_mbs_idx
;
790 if (BE (offset
>= (unsigned int) mctx
.input
.valid_raw_len
, 0))
792 err
= re_string_reconstruct (&mctx
.input
, match_first
,
794 if (BE (err
!= REG_NOERROR
, 0))
797 offset
= match_first
- mctx
.input
.raw_mbs_idx
;
799 /* If MATCH_FIRST is out of the buffer, leave it as '\0'.
800 Note that MATCH_FIRST must not be smaller than 0. */
801 ch
= (match_first
>= length
802 ? 0 : re_string_byte_at (&mctx
.input
, offset
));
806 if (match_first
< left_lim
|| match_first
> right_lim
)
815 /* Reconstruct the buffers so that the matcher can assume that
816 the matching starts from the beginning of the buffer. */
817 err
= re_string_reconstruct (&mctx
.input
, match_first
, eflags
);
818 if (BE (err
!= REG_NOERROR
, 0))
821 #ifdef RE_ENABLE_I18N
822 /* Don't consider this char as a possible match start if it part,
823 yet isn't the head, of a multibyte character. */
824 if (!sb
&& !re_string_first_byte (&mctx
.input
, 0))
828 /* It seems to be appropriate one, then use the matcher. */
829 /* We assume that the matching starts from 0. */
830 mctx
.state_log_top
= mctx
.nbkref_ents
= mctx
.max_mb_elem_len
= 0;
831 match_last
= check_matching (&mctx
, fl_longest_match
,
832 range
>= 0 ? &match_first
: NULL
);
833 if (match_last
!= -1)
835 if (BE (match_last
== -2, 0))
842 mctx
.match_last
= match_last
;
843 if ((!preg
->no_sub
&& nmatch
> 1) || dfa
->nbackref
)
845 re_dfastate_t
*pstate
= mctx
.state_log
[match_last
];
846 mctx
.last_node
= check_halt_state_context (&mctx
, pstate
,
849 if ((!preg
->no_sub
&& nmatch
> 1 && dfa
->has_plural_match
)
852 err
= prune_impossible_nodes (&mctx
);
853 if (err
== REG_NOERROR
)
855 if (BE (err
!= REG_NOMATCH
, 0))
860 break; /* We found a match. */
864 match_ctx_clean (&mctx
);
868 assert (match_last
!= -1);
869 assert (err
== REG_NOERROR
);
872 /* Set pmatch[] if we need. */
877 /* Initialize registers. */
878 for (reg_idx
= 1; reg_idx
< nmatch
; ++reg_idx
)
879 pmatch
[reg_idx
].rm_so
= pmatch
[reg_idx
].rm_eo
= -1;
881 /* Set the points where matching start/end. */
883 pmatch
[0].rm_eo
= mctx
.match_last
;
885 if (!preg
->no_sub
&& nmatch
> 1)
887 err
= set_regs (preg
, &mctx
, nmatch
, pmatch
,
888 dfa
->has_plural_match
&& dfa
->nbackref
> 0);
889 if (BE (err
!= REG_NOERROR
, 0))
893 /* At last, add the offset to the each registers, since we slided
894 the buffers so that we could assume that the matching starts
896 for (reg_idx
= 0; reg_idx
< nmatch
; ++reg_idx
)
897 if (pmatch
[reg_idx
].rm_so
!= -1)
899 #ifdef RE_ENABLE_I18N
900 if (BE (mctx
.input
.offsets_needed
!= 0, 0))
902 pmatch
[reg_idx
].rm_so
=
903 (pmatch
[reg_idx
].rm_so
== mctx
.input
.valid_len
904 ? mctx
.input
.valid_raw_len
905 : mctx
.input
.offsets
[pmatch
[reg_idx
].rm_so
]);
906 pmatch
[reg_idx
].rm_eo
=
907 (pmatch
[reg_idx
].rm_eo
== mctx
.input
.valid_len
908 ? mctx
.input
.valid_raw_len
909 : mctx
.input
.offsets
[pmatch
[reg_idx
].rm_eo
]);
912 assert (mctx
.input
.offsets_needed
== 0);
914 pmatch
[reg_idx
].rm_so
+= match_first
;
915 pmatch
[reg_idx
].rm_eo
+= match_first
;
917 for (reg_idx
= 0; reg_idx
< extra_nmatch
; ++reg_idx
)
919 pmatch
[nmatch
+ reg_idx
].rm_so
= -1;
920 pmatch
[nmatch
+ reg_idx
].rm_eo
= -1;
924 for (reg_idx
= 0; reg_idx
+ 1 < nmatch
; reg_idx
++)
925 if (dfa
->subexp_map
[reg_idx
] != reg_idx
)
927 pmatch
[reg_idx
+ 1].rm_so
928 = pmatch
[dfa
->subexp_map
[reg_idx
] + 1].rm_so
;
929 pmatch
[reg_idx
+ 1].rm_eo
930 = pmatch
[dfa
->subexp_map
[reg_idx
] + 1].rm_eo
;
935 re_free (mctx
.state_log
);
937 match_ctx_free (&mctx
);
938 re_string_destruct (&mctx
.input
);
943 prune_impossible_nodes (mctx
)
944 re_match_context_t
*mctx
;
946 const re_dfa_t
*const dfa
= mctx
->dfa
;
947 int halt_node
, match_last
;
949 re_dfastate_t
**sifted_states
;
950 re_dfastate_t
**lim_states
= NULL
;
951 re_sift_context_t sctx
;
953 assert (mctx
->state_log
!= NULL
);
955 match_last
= mctx
->match_last
;
956 halt_node
= mctx
->last_node
;
957 sifted_states
= re_malloc (re_dfastate_t
*, match_last
+ 1);
958 if (BE (sifted_states
== NULL
, 0))
965 lim_states
= re_malloc (re_dfastate_t
*, match_last
+ 1);
966 if (BE (lim_states
== NULL
, 0))
973 memset (lim_states
, '\0',
974 sizeof (re_dfastate_t
*) * (match_last
+ 1));
975 sift_ctx_init (&sctx
, sifted_states
, lim_states
, halt_node
,
977 ret
= sift_states_backward (mctx
, &sctx
);
978 re_node_set_free (&sctx
.limits
);
979 if (BE (ret
!= REG_NOERROR
, 0))
981 if (sifted_states
[0] != NULL
|| lim_states
[0] != NULL
)
991 } while (mctx
->state_log
[match_last
] == NULL
992 || !mctx
->state_log
[match_last
]->halt
);
993 halt_node
= check_halt_state_context (mctx
,
994 mctx
->state_log
[match_last
],
997 ret
= merge_state_array (dfa
, sifted_states
, lim_states
,
999 re_free (lim_states
);
1001 if (BE (ret
!= REG_NOERROR
, 0))
1006 sift_ctx_init (&sctx
, sifted_states
, lim_states
, halt_node
, match_last
);
1007 ret
= sift_states_backward (mctx
, &sctx
);
1008 re_node_set_free (&sctx
.limits
);
1009 if (BE (ret
!= REG_NOERROR
, 0))
1012 re_free (mctx
->state_log
);
1013 mctx
->state_log
= sifted_states
;
1014 sifted_states
= NULL
;
1015 mctx
->last_node
= halt_node
;
1016 mctx
->match_last
= match_last
;
1019 re_free (sifted_states
);
1020 re_free (lim_states
);
1024 /* Acquire an initial state and return it.
1025 We must select appropriate initial state depending on the context,
1026 since initial states may have constraints like "\<", "^", etc.. */
1028 static inline re_dfastate_t
*
1029 __attribute ((always_inline
)) internal_function
1030 acquire_init_state_context (reg_errcode_t
*err
, const re_match_context_t
*mctx
,
1033 const re_dfa_t
*const dfa
= mctx
->dfa
;
1034 if (dfa
->init_state
->has_constraint
)
1036 unsigned int context
;
1037 context
= re_string_context_at (&mctx
->input
, idx
- 1, mctx
->eflags
);
1038 if (IS_WORD_CONTEXT (context
))
1039 return dfa
->init_state_word
;
1040 else if (IS_ORDINARY_CONTEXT (context
))
1041 return dfa
->init_state
;
1042 else if (IS_BEGBUF_CONTEXT (context
) && IS_NEWLINE_CONTEXT (context
))
1043 return dfa
->init_state_begbuf
;
1044 else if (IS_NEWLINE_CONTEXT (context
))
1045 return dfa
->init_state_nl
;
1046 else if (IS_BEGBUF_CONTEXT (context
))
1048 /* It is relatively rare case, then calculate on demand. */
1049 return re_acquire_state_context (err
, dfa
,
1050 dfa
->init_state
->entrance_nodes
,
1054 /* Must not happen? */
1055 return dfa
->init_state
;
1058 return dfa
->init_state
;
1061 /* Check whether the regular expression match input string INPUT or not,
1062 and return the index where the matching end, return -1 if not match,
1063 or return -2 in case of an error.
1064 FL_LONGEST_MATCH means we want the POSIX longest matching.
1065 If P_MATCH_FIRST is not NULL, and the match fails, it is set to the
1066 next place where we may want to try matching.
1067 Note that the matcher assume that the maching starts from the current
1068 index of the buffer. */
1072 check_matching (re_match_context_t
*mctx
, int fl_longest_match
,
1075 const re_dfa_t
*const dfa
= mctx
->dfa
;
1078 int match_last
= -1;
1079 int cur_str_idx
= re_string_cur_idx (&mctx
->input
);
1080 re_dfastate_t
*cur_state
;
1081 int at_init_state
= p_match_first
!= NULL
;
1082 int next_start_idx
= cur_str_idx
;
1085 cur_state
= acquire_init_state_context (&err
, mctx
, cur_str_idx
);
1086 /* An initial state must not be NULL (invalid). */
1087 if (BE (cur_state
== NULL
, 0))
1089 assert (err
== REG_ESPACE
);
1093 if (mctx
->state_log
!= NULL
)
1095 mctx
->state_log
[cur_str_idx
] = cur_state
;
1097 /* Check OP_OPEN_SUBEXP in the initial state in case that we use them
1098 later. E.g. Processing back references. */
1099 if (BE (dfa
->nbackref
, 0))
1102 err
= check_subexp_matching_top (mctx
, &cur_state
->nodes
, 0);
1103 if (BE (err
!= REG_NOERROR
, 0))
1106 if (cur_state
->has_backref
)
1108 err
= transit_state_bkref (mctx
, &cur_state
->nodes
);
1109 if (BE (err
!= REG_NOERROR
, 0))
1115 /* If the RE accepts NULL string. */
1116 if (BE (cur_state
->halt
, 0))
1118 if (!cur_state
->has_constraint
1119 || check_halt_state_context (mctx
, cur_state
, cur_str_idx
))
1121 if (!fl_longest_match
)
1125 match_last
= cur_str_idx
;
1131 while (!re_string_eoi (&mctx
->input
))
1133 re_dfastate_t
*old_state
= cur_state
;
1134 int next_char_idx
= re_string_cur_idx (&mctx
->input
) + 1;
1136 if (BE (next_char_idx
>= mctx
->input
.bufs_len
, 0)
1137 || (BE (next_char_idx
>= mctx
->input
.valid_len
, 0)
1138 && mctx
->input
.valid_len
< mctx
->input
.len
))
1140 err
= extend_buffers (mctx
);
1141 if (BE (err
!= REG_NOERROR
, 0))
1143 assert (err
== REG_ESPACE
);
1148 cur_state
= transit_state (&err
, mctx
, cur_state
);
1149 if (mctx
->state_log
!= NULL
)
1150 cur_state
= merge_state_with_log (&err
, mctx
, cur_state
);
1152 if (cur_state
== NULL
)
1154 /* Reached the invalid state or an error. Try to recover a valid
1155 state using the state log, if available and if we have not
1156 already found a valid (even if not the longest) match. */
1157 if (BE (err
!= REG_NOERROR
, 0))
1160 if (mctx
->state_log
== NULL
1161 || (match
&& !fl_longest_match
)
1162 || (cur_state
= find_recover_state (&err
, mctx
)) == NULL
)
1166 if (BE (at_init_state
, 0))
1168 if (old_state
== cur_state
)
1169 next_start_idx
= next_char_idx
;
1174 if (cur_state
->halt
)
1176 /* Reached a halt state.
1177 Check the halt state can satisfy the current context. */
1178 if (!cur_state
->has_constraint
1179 || check_halt_state_context (mctx
, cur_state
,
1180 re_string_cur_idx (&mctx
->input
)))
1182 /* We found an appropriate halt state. */
1183 match_last
= re_string_cur_idx (&mctx
->input
);
1186 /* We found a match, do not modify match_first below. */
1187 p_match_first
= NULL
;
1188 if (!fl_longest_match
)
1195 *p_match_first
+= next_start_idx
;
1200 /* Check NODE match the current context. */
1204 check_halt_node_context (const re_dfa_t
*dfa
, int node
, unsigned int context
)
1206 re_token_type_t type
= dfa
->nodes
[node
].type
;
1207 unsigned int constraint
= dfa
->nodes
[node
].constraint
;
1208 if (type
!= END_OF_RE
)
1212 if (NOT_SATISFY_NEXT_CONSTRAINT (constraint
, context
))
1217 /* Check the halt state STATE match the current context.
1218 Return 0 if not match, if the node, STATE has, is a halt node and
1219 match the context, return the node. */
1223 check_halt_state_context (const re_match_context_t
*mctx
,
1224 const re_dfastate_t
*state
, int idx
)
1227 unsigned int context
;
1229 assert (state
->halt
);
1231 context
= re_string_context_at (&mctx
->input
, idx
, mctx
->eflags
);
1232 for (i
= 0; i
< state
->nodes
.nelem
; ++i
)
1233 if (check_halt_node_context (mctx
->dfa
, state
->nodes
.elems
[i
], context
))
1234 return state
->nodes
.elems
[i
];
1238 /* Compute the next node to which "NFA" transit from NODE("NFA" is a NFA
1239 corresponding to the DFA).
1240 Return the destination node, and update EPS_VIA_NODES, return -1 in case
1245 proceed_next_node (const re_match_context_t
*mctx
, int nregs
, regmatch_t
*regs
,
1246 int *pidx
, int node
, re_node_set
*eps_via_nodes
,
1247 struct re_fail_stack_t
*fs
)
1249 const re_dfa_t
*const dfa
= mctx
->dfa
;
1251 if (IS_EPSILON_NODE (dfa
->nodes
[node
].type
))
1253 re_node_set
*cur_nodes
= &mctx
->state_log
[*pidx
]->nodes
;
1254 re_node_set
*edests
= &dfa
->edests
[node
];
1256 err
= re_node_set_insert (eps_via_nodes
, node
);
1257 if (BE (err
< 0, 0))
1259 /* Pick up a valid destination, or return -1 if none is found. */
1260 for (dest_node
= -1, i
= 0; i
< edests
->nelem
; ++i
)
1262 int candidate
= edests
->elems
[i
];
1263 if (!re_node_set_contains (cur_nodes
, candidate
))
1265 if (dest_node
== -1)
1266 dest_node
= candidate
;
1270 /* In order to avoid infinite loop like "(a*)*", return the second
1271 epsilon-transition if the first was already considered. */
1272 if (re_node_set_contains (eps_via_nodes
, dest_node
))
1275 /* Otherwise, push the second epsilon-transition on the fail stack. */
1277 && push_fail_stack (fs
, *pidx
, candidate
, nregs
, regs
,
1281 /* We know we are going to exit. */
1290 re_token_type_t type
= dfa
->nodes
[node
].type
;
1292 #ifdef RE_ENABLE_I18N
1293 if (dfa
->nodes
[node
].accept_mb
)
1294 naccepted
= check_node_accept_bytes (dfa
, node
, &mctx
->input
, *pidx
);
1296 #endif /* RE_ENABLE_I18N */
1297 if (type
== OP_BACK_REF
)
1299 int subexp_idx
= dfa
->nodes
[node
].opr
.idx
+ 1;
1300 naccepted
= regs
[subexp_idx
].rm_eo
- regs
[subexp_idx
].rm_so
;
1303 if (regs
[subexp_idx
].rm_so
== -1 || regs
[subexp_idx
].rm_eo
== -1)
1307 char *buf
= (char *) re_string_get_buffer (&mctx
->input
);
1308 if (memcmp (buf
+ regs
[subexp_idx
].rm_so
, buf
+ *pidx
,
1317 err
= re_node_set_insert (eps_via_nodes
, node
);
1318 if (BE (err
< 0, 0))
1320 dest_node
= dfa
->edests
[node
].elems
[0];
1321 if (re_node_set_contains (&mctx
->state_log
[*pidx
]->nodes
,
1328 || check_node_accept (mctx
, dfa
->nodes
+ node
, *pidx
))
1330 int dest_node
= dfa
->nexts
[node
];
1331 *pidx
= (naccepted
== 0) ? *pidx
+ 1 : *pidx
+ naccepted
;
1332 if (fs
&& (*pidx
> mctx
->match_last
|| mctx
->state_log
[*pidx
] == NULL
1333 || !re_node_set_contains (&mctx
->state_log
[*pidx
]->nodes
,
1336 re_node_set_empty (eps_via_nodes
);
1343 static reg_errcode_t
1345 push_fail_stack (struct re_fail_stack_t
*fs
, int str_idx
, int dest_node
,
1346 int nregs
, regmatch_t
*regs
, re_node_set
*eps_via_nodes
)
1349 int num
= fs
->num
++;
1350 if (fs
->num
== fs
->alloc
)
1352 struct re_fail_stack_ent_t
*new_array
;
1353 new_array
= realloc (fs
->stack
, (sizeof (struct re_fail_stack_ent_t
)
1355 if (new_array
== NULL
)
1358 fs
->stack
= new_array
;
1360 fs
->stack
[num
].idx
= str_idx
;
1361 fs
->stack
[num
].node
= dest_node
;
1362 fs
->stack
[num
].regs
= re_malloc (regmatch_t
, nregs
);
1363 if (fs
->stack
[num
].regs
== NULL
)
1365 memcpy (fs
->stack
[num
].regs
, regs
, sizeof (regmatch_t
) * nregs
);
1366 err
= re_node_set_init_copy (&fs
->stack
[num
].eps_via_nodes
, eps_via_nodes
);
1372 pop_fail_stack (struct re_fail_stack_t
*fs
, int *pidx
, int nregs
,
1373 regmatch_t
*regs
, re_node_set
*eps_via_nodes
)
1375 int num
= --fs
->num
;
1377 *pidx
= fs
->stack
[num
].idx
;
1378 memcpy (regs
, fs
->stack
[num
].regs
, sizeof (regmatch_t
) * nregs
);
1379 re_node_set_free (eps_via_nodes
);
1380 re_free (fs
->stack
[num
].regs
);
1381 *eps_via_nodes
= fs
->stack
[num
].eps_via_nodes
;
1382 return fs
->stack
[num
].node
;
1385 /* Set the positions where the subexpressions are starts/ends to registers
1387 Note: We assume that pmatch[0] is already set, and
1388 pmatch[i].rm_so == pmatch[i].rm_eo == -1 for 0 < i < nmatch. */
1390 static reg_errcode_t
1392 set_regs (const regex_t
*preg
, const re_match_context_t
*mctx
, size_t nmatch
,
1393 regmatch_t
*pmatch
, int fl_backtrack
)
1395 const re_dfa_t
*dfa
= (const re_dfa_t
*) preg
->buffer
;
1397 re_node_set eps_via_nodes
;
1398 struct re_fail_stack_t
*fs
;
1399 struct re_fail_stack_t fs_body
= { 0, 2, NULL
};
1400 regmatch_t
*prev_idx_match
;
1401 int prev_idx_match_malloced
= 0;
1404 assert (nmatch
> 1);
1405 assert (mctx
->state_log
!= NULL
);
1410 fs
->stack
= re_malloc (struct re_fail_stack_ent_t
, fs
->alloc
);
1411 if (fs
->stack
== NULL
)
1417 cur_node
= dfa
->init_node
;
1418 re_node_set_init_empty (&eps_via_nodes
);
1420 if (__libc_use_alloca (nmatch
* sizeof (regmatch_t
)))
1421 prev_idx_match
= (regmatch_t
*) alloca (nmatch
* sizeof (regmatch_t
));
1424 prev_idx_match
= re_malloc (regmatch_t
, nmatch
);
1425 if (prev_idx_match
== NULL
)
1427 free_fail_stack_return (fs
);
1430 prev_idx_match_malloced
= 1;
1432 memcpy (prev_idx_match
, pmatch
, sizeof (regmatch_t
) * nmatch
);
1434 for (idx
= pmatch
[0].rm_so
; idx
<= pmatch
[0].rm_eo
;)
1436 update_regs (dfa
, pmatch
, prev_idx_match
, cur_node
, idx
, nmatch
);
1438 if (idx
== pmatch
[0].rm_eo
&& cur_node
== mctx
->last_node
)
1443 for (reg_idx
= 0; reg_idx
< nmatch
; ++reg_idx
)
1444 if (pmatch
[reg_idx
].rm_so
> -1 && pmatch
[reg_idx
].rm_eo
== -1)
1446 if (reg_idx
== nmatch
)
1448 re_node_set_free (&eps_via_nodes
);
1449 if (prev_idx_match_malloced
)
1450 re_free (prev_idx_match
);
1451 return free_fail_stack_return (fs
);
1453 cur_node
= pop_fail_stack (fs
, &idx
, nmatch
, pmatch
,
1458 re_node_set_free (&eps_via_nodes
);
1459 if (prev_idx_match_malloced
)
1460 re_free (prev_idx_match
);
1465 /* Proceed to next node. */
1466 cur_node
= proceed_next_node (mctx
, nmatch
, pmatch
, &idx
, cur_node
,
1467 &eps_via_nodes
, fs
);
1469 if (BE (cur_node
< 0, 0))
1471 if (BE (cur_node
== -2, 0))
1473 re_node_set_free (&eps_via_nodes
);
1474 if (prev_idx_match_malloced
)
1475 re_free (prev_idx_match
);
1476 free_fail_stack_return (fs
);
1480 cur_node
= pop_fail_stack (fs
, &idx
, nmatch
, pmatch
,
1484 re_node_set_free (&eps_via_nodes
);
1485 if (prev_idx_match_malloced
)
1486 re_free (prev_idx_match
);
1491 re_node_set_free (&eps_via_nodes
);
1492 if (prev_idx_match_malloced
)
1493 re_free (prev_idx_match
);
1494 return free_fail_stack_return (fs
);
1497 static reg_errcode_t
1499 free_fail_stack_return (struct re_fail_stack_t
*fs
)
1504 for (fs_idx
= 0; fs_idx
< fs
->num
; ++fs_idx
)
1506 re_node_set_free (&fs
->stack
[fs_idx
].eps_via_nodes
);
1507 re_free (fs
->stack
[fs_idx
].regs
);
1509 re_free (fs
->stack
);
1516 update_regs (const re_dfa_t
*dfa
, regmatch_t
*pmatch
,
1517 regmatch_t
*prev_idx_match
, int cur_node
, int cur_idx
, int nmatch
)
1519 int type
= dfa
->nodes
[cur_node
].type
;
1520 if (type
== OP_OPEN_SUBEXP
)
1522 int reg_num
= dfa
->nodes
[cur_node
].opr
.idx
+ 1;
1524 /* We are at the first node of this sub expression. */
1525 if (reg_num
< nmatch
)
1527 pmatch
[reg_num
].rm_so
= cur_idx
;
1528 pmatch
[reg_num
].rm_eo
= -1;
1531 else if (type
== OP_CLOSE_SUBEXP
)
1533 int reg_num
= dfa
->nodes
[cur_node
].opr
.idx
+ 1;
1534 if (reg_num
< nmatch
)
1536 /* We are at the last node of this sub expression. */
1537 if (pmatch
[reg_num
].rm_so
< cur_idx
)
1539 pmatch
[reg_num
].rm_eo
= cur_idx
;
1540 /* This is a non-empty match or we are not inside an optional
1541 subexpression. Accept this right away. */
1542 memcpy (prev_idx_match
, pmatch
, sizeof (regmatch_t
) * nmatch
);
1546 if (dfa
->nodes
[cur_node
].opt_subexp
1547 && prev_idx_match
[reg_num
].rm_so
!= -1)
1548 /* We transited through an empty match for an optional
1549 subexpression, like (a?)*, and this is not the subexp's
1550 first match. Copy back the old content of the registers
1551 so that matches of an inner subexpression are undone as
1552 well, like in ((a?))*. */
1553 memcpy (pmatch
, prev_idx_match
, sizeof (regmatch_t
) * nmatch
);
1555 /* We completed a subexpression, but it may be part of
1556 an optional one, so do not update PREV_IDX_MATCH. */
1557 pmatch
[reg_num
].rm_eo
= cur_idx
;
1563 /* This function checks the STATE_LOG from the SCTX->last_str_idx to 0
1564 and sift the nodes in each states according to the following rules.
1565 Updated state_log will be wrote to STATE_LOG.
1567 Rules: We throw away the Node `a' in the STATE_LOG[STR_IDX] if...
1568 1. When STR_IDX == MATCH_LAST(the last index in the state_log):
1569 If `a' isn't the LAST_NODE and `a' can't epsilon transit to
1570 the LAST_NODE, we throw away the node `a'.
1571 2. When 0 <= STR_IDX < MATCH_LAST and `a' accepts
1572 string `s' and transit to `b':
1573 i. If 'b' isn't in the STATE_LOG[STR_IDX+strlen('s')], we throw
1575 ii. If 'b' is in the STATE_LOG[STR_IDX+strlen('s')] but 'b' is
1576 thrown away, we throw away the node `a'.
1577 3. When 0 <= STR_IDX < MATCH_LAST and 'a' epsilon transit to 'b':
1578 i. If 'b' isn't in the STATE_LOG[STR_IDX], we throw away the
1580 ii. If 'b' is in the STATE_LOG[STR_IDX] but 'b' is thrown away,
1581 we throw away the node `a'. */
1583 #define STATE_NODE_CONTAINS(state,node) \
1584 ((state) != NULL && re_node_set_contains (&(state)->nodes, node))
1586 static reg_errcode_t
1588 sift_states_backward (const re_match_context_t
*mctx
, re_sift_context_t
*sctx
)
1592 int str_idx
= sctx
->last_str_idx
;
1593 re_node_set cur_dest
;
1596 assert (mctx
->state_log
!= NULL
&& mctx
->state_log
[str_idx
] != NULL
);
1599 /* Build sifted state_log[str_idx]. It has the nodes which can epsilon
1600 transit to the last_node and the last_node itself. */
1601 err
= re_node_set_init_1 (&cur_dest
, sctx
->last_node
);
1602 if (BE (err
!= REG_NOERROR
, 0))
1604 err
= update_cur_sifted_state (mctx
, sctx
, str_idx
, &cur_dest
);
1605 if (BE (err
!= REG_NOERROR
, 0))
1608 /* Then check each states in the state_log. */
1611 /* Update counters. */
1612 null_cnt
= (sctx
->sifted_states
[str_idx
] == NULL
) ? null_cnt
+ 1 : 0;
1613 if (null_cnt
> mctx
->max_mb_elem_len
)
1615 memset (sctx
->sifted_states
, '\0',
1616 sizeof (re_dfastate_t
*) * str_idx
);
1617 re_node_set_free (&cur_dest
);
1620 re_node_set_empty (&cur_dest
);
1623 if (mctx
->state_log
[str_idx
])
1625 err
= build_sifted_states (mctx
, sctx
, str_idx
, &cur_dest
);
1626 if (BE (err
!= REG_NOERROR
, 0))
1630 /* Add all the nodes which satisfy the following conditions:
1631 - It can epsilon transit to a node in CUR_DEST.
1633 And update state_log. */
1634 err
= update_cur_sifted_state (mctx
, sctx
, str_idx
, &cur_dest
);
1635 if (BE (err
!= REG_NOERROR
, 0))
1640 re_node_set_free (&cur_dest
);
1644 static reg_errcode_t
1646 build_sifted_states (const re_match_context_t
*mctx
, re_sift_context_t
*sctx
,
1647 int str_idx
, re_node_set
*cur_dest
)
1649 const re_dfa_t
*const dfa
= mctx
->dfa
;
1650 const re_node_set
*cur_src
= &mctx
->state_log
[str_idx
]->non_eps_nodes
;
1653 /* Then build the next sifted state.
1654 We build the next sifted state on `cur_dest', and update
1655 `sifted_states[str_idx]' with `cur_dest'.
1657 `cur_dest' is the sifted state from `state_log[str_idx + 1]'.
1658 `cur_src' points the node_set of the old `state_log[str_idx]'
1659 (with the epsilon nodes pre-filtered out). */
1660 for (i
= 0; i
< cur_src
->nelem
; i
++)
1662 int prev_node
= cur_src
->elems
[i
];
1667 re_token_type_t type
= dfa
->nodes
[prev_node
].type
;
1668 assert (!IS_EPSILON_NODE (type
));
1670 #ifdef RE_ENABLE_I18N
1671 /* If the node may accept `multi byte'. */
1672 if (dfa
->nodes
[prev_node
].accept_mb
)
1673 naccepted
= sift_states_iter_mb (mctx
, sctx
, prev_node
,
1674 str_idx
, sctx
->last_str_idx
);
1675 #endif /* RE_ENABLE_I18N */
1677 /* We don't check backreferences here.
1678 See update_cur_sifted_state(). */
1680 && check_node_accept (mctx
, dfa
->nodes
+ prev_node
, str_idx
)
1681 && STATE_NODE_CONTAINS (sctx
->sifted_states
[str_idx
+ 1],
1682 dfa
->nexts
[prev_node
]))
1688 if (sctx
->limits
.nelem
)
1690 int to_idx
= str_idx
+ naccepted
;
1691 if (check_dst_limits (mctx
, &sctx
->limits
,
1692 dfa
->nexts
[prev_node
], to_idx
,
1693 prev_node
, str_idx
))
1696 ret
= re_node_set_insert (cur_dest
, prev_node
);
1697 if (BE (ret
== -1, 0))
1704 /* Helper functions. */
1706 static reg_errcode_t
1708 clean_state_log_if_needed (re_match_context_t
*mctx
, int next_state_log_idx
)
1710 int top
= mctx
->state_log_top
;
1712 if (next_state_log_idx
>= mctx
->input
.bufs_len
1713 || (next_state_log_idx
>= mctx
->input
.valid_len
1714 && mctx
->input
.valid_len
< mctx
->input
.len
))
1717 err
= extend_buffers (mctx
);
1718 if (BE (err
!= REG_NOERROR
, 0))
1722 if (top
< next_state_log_idx
)
1724 memset (mctx
->state_log
+ top
+ 1, '\0',
1725 sizeof (re_dfastate_t
*) * (next_state_log_idx
- top
));
1726 mctx
->state_log_top
= next_state_log_idx
;
1731 static reg_errcode_t
1733 merge_state_array (const re_dfa_t
*dfa
, re_dfastate_t
**dst
,
1734 re_dfastate_t
**src
, int num
)
1738 for (st_idx
= 0; st_idx
< num
; ++st_idx
)
1740 if (dst
[st_idx
] == NULL
)
1741 dst
[st_idx
] = src
[st_idx
];
1742 else if (src
[st_idx
] != NULL
)
1744 re_node_set merged_set
;
1745 err
= re_node_set_init_union (&merged_set
, &dst
[st_idx
]->nodes
,
1746 &src
[st_idx
]->nodes
);
1747 if (BE (err
!= REG_NOERROR
, 0))
1749 dst
[st_idx
] = re_acquire_state (&err
, dfa
, &merged_set
);
1750 re_node_set_free (&merged_set
);
1751 if (BE (err
!= REG_NOERROR
, 0))
1758 static reg_errcode_t
1760 update_cur_sifted_state (const re_match_context_t
*mctx
,
1761 re_sift_context_t
*sctx
, int str_idx
,
1762 re_node_set
*dest_nodes
)
1764 const re_dfa_t
*const dfa
= mctx
->dfa
;
1765 reg_errcode_t err
= REG_NOERROR
;
1766 const re_node_set
*candidates
;
1767 candidates
= ((mctx
->state_log
[str_idx
] == NULL
) ? NULL
1768 : &mctx
->state_log
[str_idx
]->nodes
);
1770 if (dest_nodes
->nelem
== 0)
1771 sctx
->sifted_states
[str_idx
] = NULL
;
1776 /* At first, add the nodes which can epsilon transit to a node in
1778 err
= add_epsilon_src_nodes (dfa
, dest_nodes
, candidates
);
1779 if (BE (err
!= REG_NOERROR
, 0))
1782 /* Then, check the limitations in the current sift_context. */
1783 if (sctx
->limits
.nelem
)
1785 err
= check_subexp_limits (dfa
, dest_nodes
, candidates
, &sctx
->limits
,
1786 mctx
->bkref_ents
, str_idx
);
1787 if (BE (err
!= REG_NOERROR
, 0))
1792 sctx
->sifted_states
[str_idx
] = re_acquire_state (&err
, dfa
, dest_nodes
);
1793 if (BE (err
!= REG_NOERROR
, 0))
1797 if (candidates
&& mctx
->state_log
[str_idx
]->has_backref
)
1799 err
= sift_states_bkref (mctx
, sctx
, str_idx
, candidates
);
1800 if (BE (err
!= REG_NOERROR
, 0))
1806 static reg_errcode_t
1808 add_epsilon_src_nodes (const re_dfa_t
*dfa
, re_node_set
*dest_nodes
,
1809 const re_node_set
*candidates
)
1811 reg_errcode_t err
= REG_NOERROR
;
1814 re_dfastate_t
*state
= re_acquire_state (&err
, dfa
, dest_nodes
);
1815 if (BE (err
!= REG_NOERROR
, 0))
1818 if (!state
->inveclosure
.alloc
)
1820 err
= re_node_set_alloc (&state
->inveclosure
, dest_nodes
->nelem
);
1821 if (BE (err
!= REG_NOERROR
, 0))
1823 for (i
= 0; i
< dest_nodes
->nelem
; i
++)
1824 re_node_set_merge (&state
->inveclosure
,
1825 dfa
->inveclosures
+ dest_nodes
->elems
[i
]);
1827 return re_node_set_add_intersect (dest_nodes
, candidates
,
1828 &state
->inveclosure
);
1831 static reg_errcode_t
1833 sub_epsilon_src_nodes (const re_dfa_t
*dfa
, int node
, re_node_set
*dest_nodes
,
1834 const re_node_set
*candidates
)
1838 re_node_set
*inv_eclosure
= dfa
->inveclosures
+ node
;
1839 re_node_set except_nodes
;
1840 re_node_set_init_empty (&except_nodes
);
1841 for (ecl_idx
= 0; ecl_idx
< inv_eclosure
->nelem
; ++ecl_idx
)
1843 int cur_node
= inv_eclosure
->elems
[ecl_idx
];
1844 if (cur_node
== node
)
1846 if (IS_EPSILON_NODE (dfa
->nodes
[cur_node
].type
))
1848 int edst1
= dfa
->edests
[cur_node
].elems
[0];
1849 int edst2
= ((dfa
->edests
[cur_node
].nelem
> 1)
1850 ? dfa
->edests
[cur_node
].elems
[1] : -1);
1851 if ((!re_node_set_contains (inv_eclosure
, edst1
)
1852 && re_node_set_contains (dest_nodes
, edst1
))
1854 && !re_node_set_contains (inv_eclosure
, edst2
)
1855 && re_node_set_contains (dest_nodes
, edst2
)))
1857 err
= re_node_set_add_intersect (&except_nodes
, candidates
,
1858 dfa
->inveclosures
+ cur_node
);
1859 if (BE (err
!= REG_NOERROR
, 0))
1861 re_node_set_free (&except_nodes
);
1867 for (ecl_idx
= 0; ecl_idx
< inv_eclosure
->nelem
; ++ecl_idx
)
1869 int cur_node
= inv_eclosure
->elems
[ecl_idx
];
1870 if (!re_node_set_contains (&except_nodes
, cur_node
))
1872 int idx
= re_node_set_contains (dest_nodes
, cur_node
) - 1;
1873 re_node_set_remove_at (dest_nodes
, idx
);
1876 re_node_set_free (&except_nodes
);
1882 check_dst_limits (const re_match_context_t
*mctx
, re_node_set
*limits
,
1883 int dst_node
, int dst_idx
, int src_node
, int src_idx
)
1885 const re_dfa_t
*const dfa
= mctx
->dfa
;
1886 int lim_idx
, src_pos
, dst_pos
;
1888 int dst_bkref_idx
= search_cur_bkref_entry (mctx
, dst_idx
);
1889 int src_bkref_idx
= search_cur_bkref_entry (mctx
, src_idx
);
1890 for (lim_idx
= 0; lim_idx
< limits
->nelem
; ++lim_idx
)
1893 struct re_backref_cache_entry
*ent
;
1894 ent
= mctx
->bkref_ents
+ limits
->elems
[lim_idx
];
1895 subexp_idx
= dfa
->nodes
[ent
->node
].opr
.idx
;
1897 dst_pos
= check_dst_limits_calc_pos (mctx
, limits
->elems
[lim_idx
],
1898 subexp_idx
, dst_node
, dst_idx
,
1900 src_pos
= check_dst_limits_calc_pos (mctx
, limits
->elems
[lim_idx
],
1901 subexp_idx
, src_node
, src_idx
,
1905 <src> <dst> ( <subexp> )
1906 ( <subexp> ) <src> <dst>
1907 ( <subexp1> <src> <subexp2> <dst> <subexp3> ) */
1908 if (src_pos
== dst_pos
)
1909 continue; /* This is unrelated limitation. */
1918 check_dst_limits_calc_pos_1 (const re_match_context_t
*mctx
, int boundaries
,
1919 int subexp_idx
, int from_node
, int bkref_idx
)
1921 const re_dfa_t
*const dfa
= mctx
->dfa
;
1922 const re_node_set
*eclosures
= dfa
->eclosures
+ from_node
;
1925 /* Else, we are on the boundary: examine the nodes on the epsilon
1927 for (node_idx
= 0; node_idx
< eclosures
->nelem
; ++node_idx
)
1929 int node
= eclosures
->elems
[node_idx
];
1930 switch (dfa
->nodes
[node
].type
)
1933 if (bkref_idx
!= -1)
1935 struct re_backref_cache_entry
*ent
= mctx
->bkref_ents
+ bkref_idx
;
1940 if (ent
->node
!= node
)
1943 if (subexp_idx
< BITSET_WORD_BITS
1944 && !(ent
->eps_reachable_subexps_map
1945 & ((bitset_word_t
) 1 << subexp_idx
)))
1948 /* Recurse trying to reach the OP_OPEN_SUBEXP and
1949 OP_CLOSE_SUBEXP cases below. But, if the
1950 destination node is the same node as the source
1951 node, don't recurse because it would cause an
1952 infinite loop: a regex that exhibits this behavior
1954 dst
= dfa
->edests
[node
].elems
[0];
1955 if (dst
== from_node
)
1959 else /* if (boundaries & 2) */
1964 check_dst_limits_calc_pos_1 (mctx
, boundaries
, subexp_idx
,
1966 if (cpos
== -1 /* && (boundaries & 1) */)
1968 if (cpos
== 0 && (boundaries
& 2))
1971 if (subexp_idx
< BITSET_WORD_BITS
)
1972 ent
->eps_reachable_subexps_map
1973 &= ~((bitset_word_t
) 1 << subexp_idx
);
1975 while (ent
++->more
);
1979 case OP_OPEN_SUBEXP
:
1980 if ((boundaries
& 1) && subexp_idx
== dfa
->nodes
[node
].opr
.idx
)
1984 case OP_CLOSE_SUBEXP
:
1985 if ((boundaries
& 2) && subexp_idx
== dfa
->nodes
[node
].opr
.idx
)
1994 return (boundaries
& 2) ? 1 : 0;
1999 check_dst_limits_calc_pos (const re_match_context_t
*mctx
, int limit
,
2000 int subexp_idx
, int from_node
, int str_idx
,
2003 struct re_backref_cache_entry
*lim
= mctx
->bkref_ents
+ limit
;
2006 /* If we are outside the range of the subexpression, return -1 or 1. */
2007 if (str_idx
< lim
->subexp_from
)
2010 if (lim
->subexp_to
< str_idx
)
2013 /* If we are within the subexpression, return 0. */
2014 boundaries
= (str_idx
== lim
->subexp_from
);
2015 boundaries
|= (str_idx
== lim
->subexp_to
) << 1;
2016 if (boundaries
== 0)
2019 /* Else, examine epsilon closure. */
2020 return check_dst_limits_calc_pos_1 (mctx
, boundaries
, subexp_idx
,
2021 from_node
, bkref_idx
);
2024 /* Check the limitations of sub expressions LIMITS, and remove the nodes
2025 which are against limitations from DEST_NODES. */
2027 static reg_errcode_t
2029 check_subexp_limits (const re_dfa_t
*dfa
, re_node_set
*dest_nodes
,
2030 const re_node_set
*candidates
, re_node_set
*limits
,
2031 struct re_backref_cache_entry
*bkref_ents
, int str_idx
)
2034 int node_idx
, lim_idx
;
2036 for (lim_idx
= 0; lim_idx
< limits
->nelem
; ++lim_idx
)
2039 struct re_backref_cache_entry
*ent
;
2040 ent
= bkref_ents
+ limits
->elems
[lim_idx
];
2042 if (str_idx
<= ent
->subexp_from
|| ent
->str_idx
< str_idx
)
2043 continue; /* This is unrelated limitation. */
2045 subexp_idx
= dfa
->nodes
[ent
->node
].opr
.idx
;
2046 if (ent
->subexp_to
== str_idx
)
2050 for (node_idx
= 0; node_idx
< dest_nodes
->nelem
; ++node_idx
)
2052 int node
= dest_nodes
->elems
[node_idx
];
2053 re_token_type_t type
= dfa
->nodes
[node
].type
;
2054 if (type
== OP_OPEN_SUBEXP
2055 && subexp_idx
== dfa
->nodes
[node
].opr
.idx
)
2057 else if (type
== OP_CLOSE_SUBEXP
2058 && subexp_idx
== dfa
->nodes
[node
].opr
.idx
)
2062 /* Check the limitation of the open subexpression. */
2063 /* Note that (ent->subexp_to = str_idx != ent->subexp_from). */
2066 err
= sub_epsilon_src_nodes (dfa
, ops_node
, dest_nodes
,
2068 if (BE (err
!= REG_NOERROR
, 0))
2072 /* Check the limitation of the close subexpression. */
2074 for (node_idx
= 0; node_idx
< dest_nodes
->nelem
; ++node_idx
)
2076 int node
= dest_nodes
->elems
[node_idx
];
2077 if (!re_node_set_contains (dfa
->inveclosures
+ node
,
2079 && !re_node_set_contains (dfa
->eclosures
+ node
,
2082 /* It is against this limitation.
2083 Remove it form the current sifted state. */
2084 err
= sub_epsilon_src_nodes (dfa
, node
, dest_nodes
,
2086 if (BE (err
!= REG_NOERROR
, 0))
2092 else /* (ent->subexp_to != str_idx) */
2094 for (node_idx
= 0; node_idx
< dest_nodes
->nelem
; ++node_idx
)
2096 int node
= dest_nodes
->elems
[node_idx
];
2097 re_token_type_t type
= dfa
->nodes
[node
].type
;
2098 if (type
== OP_CLOSE_SUBEXP
|| type
== OP_OPEN_SUBEXP
)
2100 if (subexp_idx
!= dfa
->nodes
[node
].opr
.idx
)
2102 /* It is against this limitation.
2103 Remove it form the current sifted state. */
2104 err
= sub_epsilon_src_nodes (dfa
, node
, dest_nodes
,
2106 if (BE (err
!= REG_NOERROR
, 0))
2115 static reg_errcode_t
2117 sift_states_bkref (const re_match_context_t
*mctx
, re_sift_context_t
*sctx
,
2118 int str_idx
, const re_node_set
*candidates
)
2120 const re_dfa_t
*const dfa
= mctx
->dfa
;
2123 re_sift_context_t local_sctx
;
2124 int first_idx
= search_cur_bkref_entry (mctx
, str_idx
);
2126 if (first_idx
== -1)
2129 local_sctx
.sifted_states
= NULL
; /* Mark that it hasn't been initialized. */
2131 for (node_idx
= 0; node_idx
< candidates
->nelem
; ++node_idx
)
2134 re_token_type_t type
;
2135 struct re_backref_cache_entry
*entry
;
2136 node
= candidates
->elems
[node_idx
];
2137 type
= dfa
->nodes
[node
].type
;
2138 /* Avoid infinite loop for the REs like "()\1+". */
2139 if (node
== sctx
->last_node
&& str_idx
== sctx
->last_str_idx
)
2141 if (type
!= OP_BACK_REF
)
2144 entry
= mctx
->bkref_ents
+ first_idx
;
2145 enabled_idx
= first_idx
;
2152 re_dfastate_t
*cur_state
;
2154 if (entry
->node
!= node
)
2156 subexp_len
= entry
->subexp_to
- entry
->subexp_from
;
2157 to_idx
= str_idx
+ subexp_len
;
2158 dst_node
= (subexp_len
? dfa
->nexts
[node
]
2159 : dfa
->edests
[node
].elems
[0]);
2161 if (to_idx
> sctx
->last_str_idx
2162 || sctx
->sifted_states
[to_idx
] == NULL
2163 || !STATE_NODE_CONTAINS (sctx
->sifted_states
[to_idx
], dst_node
)
2164 || check_dst_limits (mctx
, &sctx
->limits
, node
,
2165 str_idx
, dst_node
, to_idx
))
2168 if (local_sctx
.sifted_states
== NULL
)
2171 err
= re_node_set_init_copy (&local_sctx
.limits
, &sctx
->limits
);
2172 if (BE (err
!= REG_NOERROR
, 0))
2175 local_sctx
.last_node
= node
;
2176 local_sctx
.last_str_idx
= str_idx
;
2177 ret
= re_node_set_insert (&local_sctx
.limits
, enabled_idx
);
2178 if (BE (ret
< 0, 0))
2183 cur_state
= local_sctx
.sifted_states
[str_idx
];
2184 err
= sift_states_backward (mctx
, &local_sctx
);
2185 if (BE (err
!= REG_NOERROR
, 0))
2187 if (sctx
->limited_states
!= NULL
)
2189 err
= merge_state_array (dfa
, sctx
->limited_states
,
2190 local_sctx
.sifted_states
,
2192 if (BE (err
!= REG_NOERROR
, 0))
2195 local_sctx
.sifted_states
[str_idx
] = cur_state
;
2196 re_node_set_remove (&local_sctx
.limits
, enabled_idx
);
2198 /* mctx->bkref_ents may have changed, reload the pointer. */
2199 entry
= mctx
->bkref_ents
+ enabled_idx
;
2201 while (enabled_idx
++, entry
++->more
);
2205 if (local_sctx
.sifted_states
!= NULL
)
2207 re_node_set_free (&local_sctx
.limits
);
2214 #ifdef RE_ENABLE_I18N
2217 sift_states_iter_mb (const re_match_context_t
*mctx
, re_sift_context_t
*sctx
,
2218 int node_idx
, int str_idx
, int max_str_idx
)
2220 const re_dfa_t
*const dfa
= mctx
->dfa
;
2222 /* Check the node can accept `multi byte'. */
2223 naccepted
= check_node_accept_bytes (dfa
, node_idx
, &mctx
->input
, str_idx
);
2224 if (naccepted
> 0 && str_idx
+ naccepted
<= max_str_idx
&&
2225 !STATE_NODE_CONTAINS (sctx
->sifted_states
[str_idx
+ naccepted
],
2226 dfa
->nexts
[node_idx
]))
2227 /* The node can't accept the `multi byte', or the
2228 destination was already thrown away, then the node
2229 could't accept the current input `multi byte'. */
2231 /* Otherwise, it is sure that the node could accept
2232 `naccepted' bytes input. */
2235 #endif /* RE_ENABLE_I18N */
2238 /* Functions for state transition. */
2240 /* Return the next state to which the current state STATE will transit by
2241 accepting the current input byte, and update STATE_LOG if necessary.
2242 If STATE can accept a multibyte char/collating element/back reference
2243 update the destination of STATE_LOG. */
2245 static re_dfastate_t
*
2247 transit_state (reg_errcode_t
*err
, re_match_context_t
*mctx
,
2248 re_dfastate_t
*state
)
2250 re_dfastate_t
**trtable
;
2253 #ifdef RE_ENABLE_I18N
2254 /* If the current state can accept multibyte. */
2255 if (BE (state
->accept_mb
, 0))
2257 *err
= transit_state_mb (mctx
, state
);
2258 if (BE (*err
!= REG_NOERROR
, 0))
2261 #endif /* RE_ENABLE_I18N */
2263 /* Then decide the next state with the single byte. */
2266 /* don't use transition table */
2267 return transit_state_sb (err
, mctx
, state
);
2270 /* Use transition table */
2271 ch
= re_string_fetch_byte (&mctx
->input
);
2274 trtable
= state
->trtable
;
2275 if (BE (trtable
!= NULL
, 1))
2278 trtable
= state
->word_trtable
;
2279 if (BE (trtable
!= NULL
, 1))
2281 unsigned int context
;
2283 = re_string_context_at (&mctx
->input
,
2284 re_string_cur_idx (&mctx
->input
) - 1,
2286 if (IS_WORD_CONTEXT (context
))
2287 return trtable
[ch
+ SBC_MAX
];
2292 if (!build_trtable (mctx
->dfa
, state
))
2298 /* Retry, we now have a transition table. */
2302 /* Update the state_log if we need */
2305 merge_state_with_log (reg_errcode_t
*err
, re_match_context_t
*mctx
,
2306 re_dfastate_t
*next_state
)
2308 const re_dfa_t
*const dfa
= mctx
->dfa
;
2309 int cur_idx
= re_string_cur_idx (&mctx
->input
);
2311 if (cur_idx
> mctx
->state_log_top
)
2313 mctx
->state_log
[cur_idx
] = next_state
;
2314 mctx
->state_log_top
= cur_idx
;
2316 else if (mctx
->state_log
[cur_idx
] == 0)
2318 mctx
->state_log
[cur_idx
] = next_state
;
2322 re_dfastate_t
*pstate
;
2323 unsigned int context
;
2324 re_node_set next_nodes
, *log_nodes
, *table_nodes
= NULL
;
2325 /* If (state_log[cur_idx] != 0), it implies that cur_idx is
2326 the destination of a multibyte char/collating element/
2327 back reference. Then the next state is the union set of
2328 these destinations and the results of the transition table. */
2329 pstate
= mctx
->state_log
[cur_idx
];
2330 log_nodes
= pstate
->entrance_nodes
;
2331 if (next_state
!= NULL
)
2333 table_nodes
= next_state
->entrance_nodes
;
2334 *err
= re_node_set_init_union (&next_nodes
, table_nodes
,
2336 if (BE (*err
!= REG_NOERROR
, 0))
2340 next_nodes
= *log_nodes
;
2341 /* Note: We already add the nodes of the initial state,
2342 then we don't need to add them here. */
2344 context
= re_string_context_at (&mctx
->input
,
2345 re_string_cur_idx (&mctx
->input
) - 1,
2347 next_state
= mctx
->state_log
[cur_idx
]
2348 = re_acquire_state_context (err
, dfa
, &next_nodes
, context
);
2349 /* We don't need to check errors here, since the return value of
2350 this function is next_state and ERR is already set. */
2352 if (table_nodes
!= NULL
)
2353 re_node_set_free (&next_nodes
);
2356 if (BE (dfa
->nbackref
, 0) && next_state
!= NULL
)
2358 /* Check OP_OPEN_SUBEXP in the current state in case that we use them
2359 later. We must check them here, since the back references in the
2360 next state might use them. */
2361 *err
= check_subexp_matching_top (mctx
, &next_state
->nodes
,
2363 if (BE (*err
!= REG_NOERROR
, 0))
2366 /* If the next state has back references. */
2367 if (next_state
->has_backref
)
2369 *err
= transit_state_bkref (mctx
, &next_state
->nodes
);
2370 if (BE (*err
!= REG_NOERROR
, 0))
2372 next_state
= mctx
->state_log
[cur_idx
];
2379 /* Skip bytes in the input that correspond to part of a
2380 multi-byte match, then look in the log for a state
2381 from which to restart matching. */
2384 find_recover_state (reg_errcode_t
*err
, re_match_context_t
*mctx
)
2386 re_dfastate_t
*cur_state
;
2389 int max
= mctx
->state_log_top
;
2390 int cur_str_idx
= re_string_cur_idx (&mctx
->input
);
2394 if (++cur_str_idx
> max
)
2396 re_string_skip_bytes (&mctx
->input
, 1);
2398 while (mctx
->state_log
[cur_str_idx
] == NULL
);
2400 cur_state
= merge_state_with_log (err
, mctx
, NULL
);
2402 while (*err
== REG_NOERROR
&& cur_state
== NULL
);
2406 /* Helper functions for transit_state. */
2408 /* From the node set CUR_NODES, pick up the nodes whose types are
2409 OP_OPEN_SUBEXP and which have corresponding back references in the regular
2410 expression. And register them to use them later for evaluating the
2411 correspoding back references. */
2413 static reg_errcode_t
2415 check_subexp_matching_top (re_match_context_t
*mctx
, re_node_set
*cur_nodes
,
2418 const re_dfa_t
*const dfa
= mctx
->dfa
;
2422 /* TODO: This isn't efficient.
2423 Because there might be more than one nodes whose types are
2424 OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
2427 for (node_idx
= 0; node_idx
< cur_nodes
->nelem
; ++node_idx
)
2429 int node
= cur_nodes
->elems
[node_idx
];
2430 if (dfa
->nodes
[node
].type
== OP_OPEN_SUBEXP
2431 && dfa
->nodes
[node
].opr
.idx
< BITSET_WORD_BITS
2432 && (dfa
->used_bkref_map
2433 & ((bitset_word_t
) 1 << dfa
->nodes
[node
].opr
.idx
)))
2435 err
= match_ctx_add_subtop (mctx
, node
, str_idx
);
2436 if (BE (err
!= REG_NOERROR
, 0))
2444 /* Return the next state to which the current state STATE will transit by
2445 accepting the current input byte. */
2447 static re_dfastate_t
*
2448 transit_state_sb (reg_errcode_t
*err
, re_match_context_t
*mctx
,
2449 re_dfastate_t
*state
)
2451 const re_dfa_t
*const dfa
= mctx
->dfa
;
2452 re_node_set next_nodes
;
2453 re_dfastate_t
*next_state
;
2454 int node_cnt
, cur_str_idx
= re_string_cur_idx (&mctx
->input
);
2455 unsigned int context
;
2457 *err
= re_node_set_alloc (&next_nodes
, state
->nodes
.nelem
+ 1);
2458 if (BE (*err
!= REG_NOERROR
, 0))
2460 for (node_cnt
= 0; node_cnt
< state
->nodes
.nelem
; ++node_cnt
)
2462 int cur_node
= state
->nodes
.elems
[node_cnt
];
2463 if (check_node_accept (mctx
, dfa
->nodes
+ cur_node
, cur_str_idx
))
2465 *err
= re_node_set_merge (&next_nodes
,
2466 dfa
->eclosures
+ dfa
->nexts
[cur_node
]);
2467 if (BE (*err
!= REG_NOERROR
, 0))
2469 re_node_set_free (&next_nodes
);
2474 context
= re_string_context_at (&mctx
->input
, cur_str_idx
, mctx
->eflags
);
2475 next_state
= re_acquire_state_context (err
, dfa
, &next_nodes
, context
);
2476 /* We don't need to check errors here, since the return value of
2477 this function is next_state and ERR is already set. */
2479 re_node_set_free (&next_nodes
);
2480 re_string_skip_bytes (&mctx
->input
, 1);
2485 #ifdef RE_ENABLE_I18N
2486 static reg_errcode_t
2488 transit_state_mb (re_match_context_t
*mctx
, re_dfastate_t
*pstate
)
2490 const re_dfa_t
*const dfa
= mctx
->dfa
;
2494 for (i
= 0; i
< pstate
->nodes
.nelem
; ++i
)
2496 re_node_set dest_nodes
, *new_nodes
;
2497 int cur_node_idx
= pstate
->nodes
.elems
[i
];
2498 int naccepted
, dest_idx
;
2499 unsigned int context
;
2500 re_dfastate_t
*dest_state
;
2502 if (!dfa
->nodes
[cur_node_idx
].accept_mb
)
2505 if (dfa
->nodes
[cur_node_idx
].constraint
)
2507 context
= re_string_context_at (&mctx
->input
,
2508 re_string_cur_idx (&mctx
->input
),
2510 if (NOT_SATISFY_NEXT_CONSTRAINT (dfa
->nodes
[cur_node_idx
].constraint
,
2515 /* How many bytes the node can accept? */
2516 naccepted
= check_node_accept_bytes (dfa
, cur_node_idx
, &mctx
->input
,
2517 re_string_cur_idx (&mctx
->input
));
2521 /* The node can accepts `naccepted' bytes. */
2522 dest_idx
= re_string_cur_idx (&mctx
->input
) + naccepted
;
2523 mctx
->max_mb_elem_len
= ((mctx
->max_mb_elem_len
< naccepted
) ? naccepted
2524 : mctx
->max_mb_elem_len
);
2525 err
= clean_state_log_if_needed (mctx
, dest_idx
);
2526 if (BE (err
!= REG_NOERROR
, 0))
2529 assert (dfa
->nexts
[cur_node_idx
] != -1);
2531 new_nodes
= dfa
->eclosures
+ dfa
->nexts
[cur_node_idx
];
2533 dest_state
= mctx
->state_log
[dest_idx
];
2534 if (dest_state
== NULL
)
2535 dest_nodes
= *new_nodes
;
2538 err
= re_node_set_init_union (&dest_nodes
,
2539 dest_state
->entrance_nodes
, new_nodes
);
2540 if (BE (err
!= REG_NOERROR
, 0))
2543 context
= re_string_context_at (&mctx
->input
, dest_idx
- 1,
2545 mctx
->state_log
[dest_idx
]
2546 = re_acquire_state_context (&err
, dfa
, &dest_nodes
, context
);
2547 if (dest_state
!= NULL
)
2548 re_node_set_free (&dest_nodes
);
2549 if (BE (mctx
->state_log
[dest_idx
] == NULL
&& err
!= REG_NOERROR
, 0))
2554 #endif /* RE_ENABLE_I18N */
2556 static reg_errcode_t
2558 transit_state_bkref (re_match_context_t
*mctx
, const re_node_set
*nodes
)
2560 const re_dfa_t
*const dfa
= mctx
->dfa
;
2563 int cur_str_idx
= re_string_cur_idx (&mctx
->input
);
2565 for (i
= 0; i
< nodes
->nelem
; ++i
)
2567 int dest_str_idx
, prev_nelem
, bkc_idx
;
2568 int node_idx
= nodes
->elems
[i
];
2569 unsigned int context
;
2570 const re_token_t
*node
= dfa
->nodes
+ node_idx
;
2571 re_node_set
*new_dest_nodes
;
2573 /* Check whether `node' is a backreference or not. */
2574 if (node
->type
!= OP_BACK_REF
)
2577 if (node
->constraint
)
2579 context
= re_string_context_at (&mctx
->input
, cur_str_idx
,
2581 if (NOT_SATISFY_NEXT_CONSTRAINT (node
->constraint
, context
))
2585 /* `node' is a backreference.
2586 Check the substring which the substring matched. */
2587 bkc_idx
= mctx
->nbkref_ents
;
2588 err
= get_subexp (mctx
, node_idx
, cur_str_idx
);
2589 if (BE (err
!= REG_NOERROR
, 0))
2592 /* And add the epsilon closures (which is `new_dest_nodes') of
2593 the backreference to appropriate state_log. */
2595 assert (dfa
->nexts
[node_idx
] != -1);
2597 for (; bkc_idx
< mctx
->nbkref_ents
; ++bkc_idx
)
2600 re_dfastate_t
*dest_state
;
2601 struct re_backref_cache_entry
*bkref_ent
;
2602 bkref_ent
= mctx
->bkref_ents
+ bkc_idx
;
2603 if (bkref_ent
->node
!= node_idx
|| bkref_ent
->str_idx
!= cur_str_idx
)
2605 subexp_len
= bkref_ent
->subexp_to
- bkref_ent
->subexp_from
;
2606 new_dest_nodes
= (subexp_len
== 0
2607 ? dfa
->eclosures
+ dfa
->edests
[node_idx
].elems
[0]
2608 : dfa
->eclosures
+ dfa
->nexts
[node_idx
]);
2609 dest_str_idx
= (cur_str_idx
+ bkref_ent
->subexp_to
2610 - bkref_ent
->subexp_from
);
2611 context
= re_string_context_at (&mctx
->input
, dest_str_idx
- 1,
2613 dest_state
= mctx
->state_log
[dest_str_idx
];
2614 prev_nelem
= ((mctx
->state_log
[cur_str_idx
] == NULL
) ? 0
2615 : mctx
->state_log
[cur_str_idx
]->nodes
.nelem
);
2616 /* Add `new_dest_node' to state_log. */
2617 if (dest_state
== NULL
)
2619 mctx
->state_log
[dest_str_idx
]
2620 = re_acquire_state_context (&err
, dfa
, new_dest_nodes
,
2622 if (BE (mctx
->state_log
[dest_str_idx
] == NULL
2623 && err
!= REG_NOERROR
, 0))
2628 re_node_set dest_nodes
;
2629 err
= re_node_set_init_union (&dest_nodes
,
2630 dest_state
->entrance_nodes
,
2632 if (BE (err
!= REG_NOERROR
, 0))
2634 re_node_set_free (&dest_nodes
);
2637 mctx
->state_log
[dest_str_idx
]
2638 = re_acquire_state_context (&err
, dfa
, &dest_nodes
, context
);
2639 re_node_set_free (&dest_nodes
);
2640 if (BE (mctx
->state_log
[dest_str_idx
] == NULL
2641 && err
!= REG_NOERROR
, 0))
2644 /* We need to check recursively if the backreference can epsilon
2647 && mctx
->state_log
[cur_str_idx
]->nodes
.nelem
> prev_nelem
)
2649 err
= check_subexp_matching_top (mctx
, new_dest_nodes
,
2651 if (BE (err
!= REG_NOERROR
, 0))
2653 err
= transit_state_bkref (mctx
, new_dest_nodes
);
2654 if (BE (err
!= REG_NOERROR
, 0))
2664 /* Enumerate all the candidates which the backreference BKREF_NODE can match
2665 at BKREF_STR_IDX, and register them by match_ctx_add_entry().
2666 Note that we might collect inappropriate candidates here.
2667 However, the cost of checking them strictly here is too high, then we
2668 delay these checking for prune_impossible_nodes(). */
2670 static reg_errcode_t
2672 get_subexp (re_match_context_t
*mctx
, int bkref_node
, int bkref_str_idx
)
2674 const re_dfa_t
*const dfa
= mctx
->dfa
;
2675 int subexp_num
, sub_top_idx
;
2676 const char *buf
= (const char *) re_string_get_buffer (&mctx
->input
);
2677 /* Return if we have already checked BKREF_NODE at BKREF_STR_IDX. */
2678 int cache_idx
= search_cur_bkref_entry (mctx
, bkref_str_idx
);
2679 if (cache_idx
!= -1)
2681 const struct re_backref_cache_entry
*entry
2682 = mctx
->bkref_ents
+ cache_idx
;
2684 if (entry
->node
== bkref_node
)
2685 return REG_NOERROR
; /* We already checked it. */
2686 while (entry
++->more
);
2689 subexp_num
= dfa
->nodes
[bkref_node
].opr
.idx
;
2691 /* For each sub expression */
2692 for (sub_top_idx
= 0; sub_top_idx
< mctx
->nsub_tops
; ++sub_top_idx
)
2695 re_sub_match_top_t
*sub_top
= mctx
->sub_tops
[sub_top_idx
];
2696 re_sub_match_last_t
*sub_last
;
2697 int sub_last_idx
, sl_str
, bkref_str_off
;
2699 if (dfa
->nodes
[sub_top
->node
].opr
.idx
!= subexp_num
)
2700 continue; /* It isn't related. */
2702 sl_str
= sub_top
->str_idx
;
2703 bkref_str_off
= bkref_str_idx
;
2704 /* At first, check the last node of sub expressions we already
2706 for (sub_last_idx
= 0; sub_last_idx
< sub_top
->nlasts
; ++sub_last_idx
)
2709 sub_last
= sub_top
->lasts
[sub_last_idx
];
2710 sl_str_diff
= sub_last
->str_idx
- sl_str
;
2711 /* The matched string by the sub expression match with the substring
2712 at the back reference? */
2713 if (sl_str_diff
> 0)
2715 if (BE (bkref_str_off
+ sl_str_diff
> mctx
->input
.valid_len
, 0))
2717 /* Not enough chars for a successful match. */
2718 if (bkref_str_off
+ sl_str_diff
> mctx
->input
.len
)
2721 err
= clean_state_log_if_needed (mctx
,
2724 if (BE (err
!= REG_NOERROR
, 0))
2726 buf
= (const char *) re_string_get_buffer (&mctx
->input
);
2728 if (memcmp (buf
+ bkref_str_off
, buf
+ sl_str
, sl_str_diff
) != 0)
2729 /* We don't need to search this sub expression any more. */
2732 bkref_str_off
+= sl_str_diff
;
2733 sl_str
+= sl_str_diff
;
2734 err
= get_subexp_sub (mctx
, sub_top
, sub_last
, bkref_node
,
2737 /* Reload buf, since the preceding call might have reallocated
2739 buf
= (const char *) re_string_get_buffer (&mctx
->input
);
2741 if (err
== REG_NOMATCH
)
2743 if (BE (err
!= REG_NOERROR
, 0))
2747 if (sub_last_idx
< sub_top
->nlasts
)
2749 if (sub_last_idx
> 0)
2751 /* Then, search for the other last nodes of the sub expression. */
2752 for (; sl_str
<= bkref_str_idx
; ++sl_str
)
2754 int cls_node
, sl_str_off
;
2755 const re_node_set
*nodes
;
2756 sl_str_off
= sl_str
- sub_top
->str_idx
;
2757 /* The matched string by the sub expression match with the substring
2758 at the back reference? */
2761 if (BE (bkref_str_off
>= mctx
->input
.valid_len
, 0))
2763 /* If we are at the end of the input, we cannot match. */
2764 if (bkref_str_off
>= mctx
->input
.len
)
2767 err
= extend_buffers (mctx
);
2768 if (BE (err
!= REG_NOERROR
, 0))
2771 buf
= (const char *) re_string_get_buffer (&mctx
->input
);
2773 if (buf
[bkref_str_off
++] != buf
[sl_str
- 1])
2774 break; /* We don't need to search this sub expression
2777 if (mctx
->state_log
[sl_str
] == NULL
)
2779 /* Does this state have a ')' of the sub expression? */
2780 nodes
= &mctx
->state_log
[sl_str
]->nodes
;
2781 cls_node
= find_subexp_node (dfa
, nodes
, subexp_num
,
2785 if (sub_top
->path
== NULL
)
2787 sub_top
->path
= calloc (sizeof (state_array_t
),
2788 sl_str
- sub_top
->str_idx
+ 1);
2789 if (sub_top
->path
== NULL
)
2792 /* Can the OP_OPEN_SUBEXP node arrive the OP_CLOSE_SUBEXP node
2793 in the current context? */
2794 err
= check_arrival (mctx
, sub_top
->path
, sub_top
->node
,
2795 sub_top
->str_idx
, cls_node
, sl_str
,
2797 if (err
== REG_NOMATCH
)
2799 if (BE (err
!= REG_NOERROR
, 0))
2801 sub_last
= match_ctx_add_sublast (sub_top
, cls_node
, sl_str
);
2802 if (BE (sub_last
== NULL
, 0))
2804 err
= get_subexp_sub (mctx
, sub_top
, sub_last
, bkref_node
,
2806 if (err
== REG_NOMATCH
)
2813 /* Helper functions for get_subexp(). */
2815 /* Check SUB_LAST can arrive to the back reference BKREF_NODE at BKREF_STR.
2816 If it can arrive, register the sub expression expressed with SUB_TOP
2819 static reg_errcode_t
2821 get_subexp_sub (re_match_context_t
*mctx
, const re_sub_match_top_t
*sub_top
,
2822 re_sub_match_last_t
*sub_last
, int bkref_node
, int bkref_str
)
2826 /* Can the subexpression arrive the back reference? */
2827 err
= check_arrival (mctx
, &sub_last
->path
, sub_last
->node
,
2828 sub_last
->str_idx
, bkref_node
, bkref_str
,
2830 if (err
!= REG_NOERROR
)
2832 err
= match_ctx_add_entry (mctx
, bkref_node
, bkref_str
, sub_top
->str_idx
,
2834 if (BE (err
!= REG_NOERROR
, 0))
2836 to_idx
= bkref_str
+ sub_last
->str_idx
- sub_top
->str_idx
;
2837 return clean_state_log_if_needed (mctx
, to_idx
);
2840 /* Find the first node which is '(' or ')' and whose index is SUBEXP_IDX.
2841 Search '(' if FL_OPEN, or search ')' otherwise.
2842 TODO: This function isn't efficient...
2843 Because there might be more than one nodes whose types are
2844 OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
2850 find_subexp_node (const re_dfa_t
*dfa
, const re_node_set
*nodes
,
2851 int subexp_idx
, int type
)
2854 for (cls_idx
= 0; cls_idx
< nodes
->nelem
; ++cls_idx
)
2856 int cls_node
= nodes
->elems
[cls_idx
];
2857 const re_token_t
*node
= dfa
->nodes
+ cls_node
;
2858 if (node
->type
== type
2859 && node
->opr
.idx
== subexp_idx
)
2865 /* Check whether the node TOP_NODE at TOP_STR can arrive to the node
2866 LAST_NODE at LAST_STR. We record the path onto PATH since it will be
2868 Return REG_NOERROR if it can arrive, or REG_NOMATCH otherwise. */
2870 static reg_errcode_t
2872 check_arrival (re_match_context_t
*mctx
, state_array_t
*path
, int top_node
,
2873 int top_str
, int last_node
, int last_str
, int type
)
2875 const re_dfa_t
*const dfa
= mctx
->dfa
;
2876 reg_errcode_t err
= REG_NOERROR
;
2877 int subexp_num
, backup_cur_idx
, str_idx
, null_cnt
;
2878 re_dfastate_t
*cur_state
= NULL
;
2879 re_node_set
*cur_nodes
, next_nodes
;
2880 re_dfastate_t
**backup_state_log
;
2881 unsigned int context
;
2883 subexp_num
= dfa
->nodes
[top_node
].opr
.idx
;
2884 /* Extend the buffer if we need. */
2885 if (BE (path
->alloc
< last_str
+ mctx
->max_mb_elem_len
+ 1, 0))
2887 re_dfastate_t
**new_array
;
2888 int old_alloc
= path
->alloc
;
2889 path
->alloc
+= last_str
+ mctx
->max_mb_elem_len
+ 1;
2890 new_array
= re_realloc (path
->array
, re_dfastate_t
*, path
->alloc
);
2891 if (BE (new_array
== NULL
, 0))
2893 path
->alloc
= old_alloc
;
2896 path
->array
= new_array
;
2897 memset (new_array
+ old_alloc
, '\0',
2898 sizeof (re_dfastate_t
*) * (path
->alloc
- old_alloc
));
2901 str_idx
= path
->next_idx
?: top_str
;
2903 /* Temporary modify MCTX. */
2904 backup_state_log
= mctx
->state_log
;
2905 backup_cur_idx
= mctx
->input
.cur_idx
;
2906 mctx
->state_log
= path
->array
;
2907 mctx
->input
.cur_idx
= str_idx
;
2909 /* Setup initial node set. */
2910 context
= re_string_context_at (&mctx
->input
, str_idx
- 1, mctx
->eflags
);
2911 if (str_idx
== top_str
)
2913 err
= re_node_set_init_1 (&next_nodes
, top_node
);
2914 if (BE (err
!= REG_NOERROR
, 0))
2916 err
= check_arrival_expand_ecl (dfa
, &next_nodes
, subexp_num
, type
);
2917 if (BE (err
!= REG_NOERROR
, 0))
2919 re_node_set_free (&next_nodes
);
2925 cur_state
= mctx
->state_log
[str_idx
];
2926 if (cur_state
&& cur_state
->has_backref
)
2928 err
= re_node_set_init_copy (&next_nodes
, &cur_state
->nodes
);
2929 if (BE (err
!= REG_NOERROR
, 0))
2933 re_node_set_init_empty (&next_nodes
);
2935 if (str_idx
== top_str
|| (cur_state
&& cur_state
->has_backref
))
2937 if (next_nodes
.nelem
)
2939 err
= expand_bkref_cache (mctx
, &next_nodes
, str_idx
,
2941 if (BE (err
!= REG_NOERROR
, 0))
2943 re_node_set_free (&next_nodes
);
2947 cur_state
= re_acquire_state_context (&err
, dfa
, &next_nodes
, context
);
2948 if (BE (cur_state
== NULL
&& err
!= REG_NOERROR
, 0))
2950 re_node_set_free (&next_nodes
);
2953 mctx
->state_log
[str_idx
] = cur_state
;
2956 for (null_cnt
= 0; str_idx
< last_str
&& null_cnt
<= mctx
->max_mb_elem_len
;)
2958 re_node_set_empty (&next_nodes
);
2959 if (mctx
->state_log
[str_idx
+ 1])
2961 err
= re_node_set_merge (&next_nodes
,
2962 &mctx
->state_log
[str_idx
+ 1]->nodes
);
2963 if (BE (err
!= REG_NOERROR
, 0))
2965 re_node_set_free (&next_nodes
);
2971 err
= check_arrival_add_next_nodes (mctx
, str_idx
,
2972 &cur_state
->non_eps_nodes
,
2974 if (BE (err
!= REG_NOERROR
, 0))
2976 re_node_set_free (&next_nodes
);
2981 if (next_nodes
.nelem
)
2983 err
= check_arrival_expand_ecl (dfa
, &next_nodes
, subexp_num
, type
);
2984 if (BE (err
!= REG_NOERROR
, 0))
2986 re_node_set_free (&next_nodes
);
2989 err
= expand_bkref_cache (mctx
, &next_nodes
, str_idx
,
2991 if (BE (err
!= REG_NOERROR
, 0))
2993 re_node_set_free (&next_nodes
);
2997 context
= re_string_context_at (&mctx
->input
, str_idx
- 1, mctx
->eflags
);
2998 cur_state
= re_acquire_state_context (&err
, dfa
, &next_nodes
, context
);
2999 if (BE (cur_state
== NULL
&& err
!= REG_NOERROR
, 0))
3001 re_node_set_free (&next_nodes
);
3004 mctx
->state_log
[str_idx
] = cur_state
;
3005 null_cnt
= cur_state
== NULL
? null_cnt
+ 1 : 0;
3007 re_node_set_free (&next_nodes
);
3008 cur_nodes
= (mctx
->state_log
[last_str
] == NULL
? NULL
3009 : &mctx
->state_log
[last_str
]->nodes
);
3010 path
->next_idx
= str_idx
;
3013 mctx
->state_log
= backup_state_log
;
3014 mctx
->input
.cur_idx
= backup_cur_idx
;
3016 /* Then check the current node set has the node LAST_NODE. */
3017 if (cur_nodes
!= NULL
&& re_node_set_contains (cur_nodes
, last_node
))
3023 /* Helper functions for check_arrival. */
3025 /* Calculate the destination nodes of CUR_NODES at STR_IDX, and append them
3027 TODO: This function is similar to the functions transit_state*(),
3028 however this function has many additional works.
3029 Can't we unify them? */
3031 static reg_errcode_t
3033 check_arrival_add_next_nodes (re_match_context_t
*mctx
, int str_idx
,
3034 re_node_set
*cur_nodes
, re_node_set
*next_nodes
)
3036 const re_dfa_t
*const dfa
= mctx
->dfa
;
3039 #ifdef RE_ENABLE_I18N
3040 reg_errcode_t err
= REG_NOERROR
;
3042 re_node_set union_set
;
3043 re_node_set_init_empty (&union_set
);
3044 for (cur_idx
= 0; cur_idx
< cur_nodes
->nelem
; ++cur_idx
)
3047 int cur_node
= cur_nodes
->elems
[cur_idx
];
3049 re_token_type_t type
= dfa
->nodes
[cur_node
].type
;
3050 assert (!IS_EPSILON_NODE (type
));
3052 #ifdef RE_ENABLE_I18N
3053 /* If the node may accept `multi byte'. */
3054 if (dfa
->nodes
[cur_node
].accept_mb
)
3056 naccepted
= check_node_accept_bytes (dfa
, cur_node
, &mctx
->input
,
3060 re_dfastate_t
*dest_state
;
3061 int next_node
= dfa
->nexts
[cur_node
];
3062 int next_idx
= str_idx
+ naccepted
;
3063 dest_state
= mctx
->state_log
[next_idx
];
3064 re_node_set_empty (&union_set
);
3067 err
= re_node_set_merge (&union_set
, &dest_state
->nodes
);
3068 if (BE (err
!= REG_NOERROR
, 0))
3070 re_node_set_free (&union_set
);
3074 result
= re_node_set_insert (&union_set
, next_node
);
3075 if (BE (result
< 0, 0))
3077 re_node_set_free (&union_set
);
3080 mctx
->state_log
[next_idx
] = re_acquire_state (&err
, dfa
,
3082 if (BE (mctx
->state_log
[next_idx
] == NULL
3083 && err
!= REG_NOERROR
, 0))
3085 re_node_set_free (&union_set
);
3090 #endif /* RE_ENABLE_I18N */
3092 || check_node_accept (mctx
, dfa
->nodes
+ cur_node
, str_idx
))
3094 result
= re_node_set_insert (next_nodes
, dfa
->nexts
[cur_node
]);
3095 if (BE (result
< 0, 0))
3097 re_node_set_free (&union_set
);
3102 re_node_set_free (&union_set
);
3106 /* For all the nodes in CUR_NODES, add the epsilon closures of them to
3107 CUR_NODES, however exclude the nodes which are:
3108 - inside the sub expression whose number is EX_SUBEXP, if FL_OPEN.
3109 - out of the sub expression whose number is EX_SUBEXP, if !FL_OPEN.
3112 static reg_errcode_t
3114 check_arrival_expand_ecl (const re_dfa_t
*dfa
, re_node_set
*cur_nodes
,
3115 int ex_subexp
, int type
)
3118 int idx
, outside_node
;
3119 re_node_set new_nodes
;
3121 assert (cur_nodes
->nelem
);
3123 err
= re_node_set_alloc (&new_nodes
, cur_nodes
->nelem
);
3124 if (BE (err
!= REG_NOERROR
, 0))
3126 /* Create a new node set NEW_NODES with the nodes which are epsilon
3127 closures of the node in CUR_NODES. */
3129 for (idx
= 0; idx
< cur_nodes
->nelem
; ++idx
)
3131 int cur_node
= cur_nodes
->elems
[idx
];
3132 const re_node_set
*eclosure
= dfa
->eclosures
+ cur_node
;
3133 outside_node
= find_subexp_node (dfa
, eclosure
, ex_subexp
, type
);
3134 if (outside_node
== -1)
3136 /* There are no problematic nodes, just merge them. */
3137 err
= re_node_set_merge (&new_nodes
, eclosure
);
3138 if (BE (err
!= REG_NOERROR
, 0))
3140 re_node_set_free (&new_nodes
);
3146 /* There are problematic nodes, re-calculate incrementally. */
3147 err
= check_arrival_expand_ecl_sub (dfa
, &new_nodes
, cur_node
,
3149 if (BE (err
!= REG_NOERROR
, 0))
3151 re_node_set_free (&new_nodes
);
3156 re_node_set_free (cur_nodes
);
3157 *cur_nodes
= new_nodes
;
3161 /* Helper function for check_arrival_expand_ecl.
3162 Check incrementally the epsilon closure of TARGET, and if it isn't
3163 problematic append it to DST_NODES. */
3165 static reg_errcode_t
3167 check_arrival_expand_ecl_sub (const re_dfa_t
*dfa
, re_node_set
*dst_nodes
,
3168 int target
, int ex_subexp
, int type
)
3171 for (cur_node
= target
; !re_node_set_contains (dst_nodes
, cur_node
);)
3175 if (dfa
->nodes
[cur_node
].type
== type
3176 && dfa
->nodes
[cur_node
].opr
.idx
== ex_subexp
)
3178 if (type
== OP_CLOSE_SUBEXP
)
3180 err
= re_node_set_insert (dst_nodes
, cur_node
);
3181 if (BE (err
== -1, 0))
3186 err
= re_node_set_insert (dst_nodes
, cur_node
);
3187 if (BE (err
== -1, 0))
3189 if (dfa
->edests
[cur_node
].nelem
== 0)
3191 if (dfa
->edests
[cur_node
].nelem
== 2)
3193 err
= check_arrival_expand_ecl_sub (dfa
, dst_nodes
,
3194 dfa
->edests
[cur_node
].elems
[1],
3196 if (BE (err
!= REG_NOERROR
, 0))
3199 cur_node
= dfa
->edests
[cur_node
].elems
[0];
3205 /* For all the back references in the current state, calculate the
3206 destination of the back references by the appropriate entry
3207 in MCTX->BKREF_ENTS. */
3209 static reg_errcode_t
3211 expand_bkref_cache (re_match_context_t
*mctx
, re_node_set
*cur_nodes
,
3212 int cur_str
, int subexp_num
, int type
)
3214 const re_dfa_t
*const dfa
= mctx
->dfa
;
3216 int cache_idx_start
= search_cur_bkref_entry (mctx
, cur_str
);
3217 struct re_backref_cache_entry
*ent
;
3219 if (cache_idx_start
== -1)
3223 ent
= mctx
->bkref_ents
+ cache_idx_start
;
3226 int to_idx
, next_node
;
3228 /* Is this entry ENT is appropriate? */
3229 if (!re_node_set_contains (cur_nodes
, ent
->node
))
3232 to_idx
= cur_str
+ ent
->subexp_to
- ent
->subexp_from
;
3233 /* Calculate the destination of the back reference, and append it
3234 to MCTX->STATE_LOG. */
3235 if (to_idx
== cur_str
)
3237 /* The backreference did epsilon transit, we must re-check all the
3238 node in the current state. */
3239 re_node_set new_dests
;
3240 reg_errcode_t err2
, err3
;
3241 next_node
= dfa
->edests
[ent
->node
].elems
[0];
3242 if (re_node_set_contains (cur_nodes
, next_node
))
3244 err
= re_node_set_init_1 (&new_dests
, next_node
);
3245 err2
= check_arrival_expand_ecl (dfa
, &new_dests
, subexp_num
, type
);
3246 err3
= re_node_set_merge (cur_nodes
, &new_dests
);
3247 re_node_set_free (&new_dests
);
3248 if (BE (err
!= REG_NOERROR
|| err2
!= REG_NOERROR
3249 || err3
!= REG_NOERROR
, 0))
3251 err
= (err
!= REG_NOERROR
? err
3252 : (err2
!= REG_NOERROR
? err2
: err3
));
3255 /* TODO: It is still inefficient... */
3260 re_node_set union_set
;
3261 next_node
= dfa
->nexts
[ent
->node
];
3262 if (mctx
->state_log
[to_idx
])
3265 if (re_node_set_contains (&mctx
->state_log
[to_idx
]->nodes
,
3268 err
= re_node_set_init_copy (&union_set
,
3269 &mctx
->state_log
[to_idx
]->nodes
);
3270 ret
= re_node_set_insert (&union_set
, next_node
);
3271 if (BE (err
!= REG_NOERROR
|| ret
< 0, 0))
3273 re_node_set_free (&union_set
);
3274 err
= err
!= REG_NOERROR
? err
: REG_ESPACE
;
3280 err
= re_node_set_init_1 (&union_set
, next_node
);
3281 if (BE (err
!= REG_NOERROR
, 0))
3284 mctx
->state_log
[to_idx
] = re_acquire_state (&err
, dfa
, &union_set
);
3285 re_node_set_free (&union_set
);
3286 if (BE (mctx
->state_log
[to_idx
] == NULL
3287 && err
!= REG_NOERROR
, 0))
3291 while (ent
++->more
);
3295 /* Build transition table for the state.
3296 Return 1 if succeeded, otherwise return NULL. */
3300 build_trtable (const re_dfa_t
*dfa
, re_dfastate_t
*state
)
3303 int i
, j
, ch
, need_word_trtable
= 0;
3304 bitset_word_t elem
, mask
;
3305 bool dests_node_malloced
= false;
3306 bool dest_states_malloced
= false;
3307 int ndests
; /* Number of the destination states from `state'. */
3308 re_dfastate_t
**trtable
;
3309 re_dfastate_t
**dest_states
= NULL
, **dest_states_word
, **dest_states_nl
;
3310 re_node_set follows
, *dests_node
;
3312 bitset_t acceptable
;
3316 re_node_set dests_node
[SBC_MAX
];
3317 bitset_t dests_ch
[SBC_MAX
];
3320 /* We build DFA states which corresponds to the destination nodes
3321 from `state'. `dests_node[i]' represents the nodes which i-th
3322 destination state contains, and `dests_ch[i]' represents the
3323 characters which i-th destination state accepts. */
3324 if (__libc_use_alloca (sizeof (struct dests_alloc
)))
3325 dests_alloc
= (struct dests_alloc
*) alloca (sizeof (struct dests_alloc
));
3328 dests_alloc
= re_malloc (struct dests_alloc
, 1);
3329 if (BE (dests_alloc
== NULL
, 0))
3331 dests_node_malloced
= true;
3333 dests_node
= dests_alloc
->dests_node
;
3334 dests_ch
= dests_alloc
->dests_ch
;
3336 /* Initialize transiton table. */
3337 state
->word_trtable
= state
->trtable
= NULL
;
3339 /* At first, group all nodes belonging to `state' into several
3341 ndests
= group_nodes_into_DFAstates (dfa
, state
, dests_node
, dests_ch
);
3342 if (BE (ndests
<= 0, 0))
3344 if (dests_node_malloced
)
3346 /* Return 0 in case of an error, 1 otherwise. */
3349 state
->trtable
= (re_dfastate_t
**)
3350 calloc (sizeof (re_dfastate_t
*), SBC_MAX
);
3356 err
= re_node_set_alloc (&follows
, ndests
+ 1);
3357 if (BE (err
!= REG_NOERROR
, 0))
3360 if (__libc_use_alloca ((sizeof (re_node_set
) + sizeof (bitset_t
)) * SBC_MAX
3361 + ndests
* 3 * sizeof (re_dfastate_t
*)))
3362 dest_states
= (re_dfastate_t
**)
3363 alloca (ndests
* 3 * sizeof (re_dfastate_t
*));
3366 dest_states
= (re_dfastate_t
**)
3367 malloc (ndests
* 3 * sizeof (re_dfastate_t
*));
3368 if (BE (dest_states
== NULL
, 0))
3371 if (dest_states_malloced
)
3373 re_node_set_free (&follows
);
3374 for (i
= 0; i
< ndests
; ++i
)
3375 re_node_set_free (dests_node
+ i
);
3376 if (dests_node_malloced
)
3380 dest_states_malloced
= true;
3382 dest_states_word
= dest_states
+ ndests
;
3383 dest_states_nl
= dest_states_word
+ ndests
;
3384 bitset_empty (acceptable
);
3386 /* Then build the states for all destinations. */
3387 for (i
= 0; i
< ndests
; ++i
)
3390 re_node_set_empty (&follows
);
3391 /* Merge the follows of this destination states. */
3392 for (j
= 0; j
< dests_node
[i
].nelem
; ++j
)
3394 next_node
= dfa
->nexts
[dests_node
[i
].elems
[j
]];
3395 if (next_node
!= -1)
3397 err
= re_node_set_merge (&follows
, dfa
->eclosures
+ next_node
);
3398 if (BE (err
!= REG_NOERROR
, 0))
3402 dest_states
[i
] = re_acquire_state_context (&err
, dfa
, &follows
, 0);
3403 if (BE (dest_states
[i
] == NULL
&& err
!= REG_NOERROR
, 0))
3405 /* If the new state has context constraint,
3406 build appropriate states for these contexts. */
3407 if (dest_states
[i
]->has_constraint
)
3409 dest_states_word
[i
] = re_acquire_state_context (&err
, dfa
, &follows
,
3411 if (BE (dest_states_word
[i
] == NULL
&& err
!= REG_NOERROR
, 0))
3414 if (dest_states
[i
] != dest_states_word
[i
] && dfa
->mb_cur_max
> 1)
3415 need_word_trtable
= 1;
3417 dest_states_nl
[i
] = re_acquire_state_context (&err
, dfa
, &follows
,
3419 if (BE (dest_states_nl
[i
] == NULL
&& err
!= REG_NOERROR
, 0))
3424 dest_states_word
[i
] = dest_states
[i
];
3425 dest_states_nl
[i
] = dest_states
[i
];
3427 bitset_merge (acceptable
, dests_ch
[i
]);
3430 if (!BE (need_word_trtable
, 0))
3432 /* We don't care about whether the following character is a word
3433 character, or we are in a single-byte character set so we can
3434 discern by looking at the character code: allocate a
3435 256-entry transition table. */
3436 trtable
= state
->trtable
=
3437 (re_dfastate_t
**) calloc (sizeof (re_dfastate_t
*), SBC_MAX
);
3438 if (BE (trtable
== NULL
, 0))
3441 /* For all characters ch...: */
3442 for (i
= 0; i
< BITSET_WORDS
; ++i
)
3443 for (ch
= i
* BITSET_WORD_BITS
, elem
= acceptable
[i
], mask
= 1;
3445 mask
<<= 1, elem
>>= 1, ++ch
)
3446 if (BE (elem
& 1, 0))
3448 /* There must be exactly one destination which accepts
3449 character ch. See group_nodes_into_DFAstates. */
3450 for (j
= 0; (dests_ch
[j
][i
] & mask
) == 0; ++j
)
3453 /* j-th destination accepts the word character ch. */
3454 if (dfa
->word_char
[i
] & mask
)
3455 trtable
[ch
] = dest_states_word
[j
];
3457 trtable
[ch
] = dest_states
[j
];
3462 /* We care about whether the following character is a word
3463 character, and we are in a multi-byte character set: discern
3464 by looking at the character code: build two 256-entry
3465 transition tables, one starting at trtable[0] and one
3466 starting at trtable[SBC_MAX]. */
3467 trtable
= state
->word_trtable
=
3468 (re_dfastate_t
**) calloc (sizeof (re_dfastate_t
*), 2 * SBC_MAX
);
3469 if (BE (trtable
== NULL
, 0))
3472 /* For all characters ch...: */
3473 for (i
= 0; i
< BITSET_WORDS
; ++i
)
3474 for (ch
= i
* BITSET_WORD_BITS
, elem
= acceptable
[i
], mask
= 1;
3476 mask
<<= 1, elem
>>= 1, ++ch
)
3477 if (BE (elem
& 1, 0))
3479 /* There must be exactly one destination which accepts
3480 character ch. See group_nodes_into_DFAstates. */
3481 for (j
= 0; (dests_ch
[j
][i
] & mask
) == 0; ++j
)
3484 /* j-th destination accepts the word character ch. */
3485 trtable
[ch
] = dest_states
[j
];
3486 trtable
[ch
+ SBC_MAX
] = dest_states_word
[j
];
3491 if (bitset_contain (acceptable
, NEWLINE_CHAR
))
3493 /* The current state accepts newline character. */
3494 for (j
= 0; j
< ndests
; ++j
)
3495 if (bitset_contain (dests_ch
[j
], NEWLINE_CHAR
))
3497 /* k-th destination accepts newline character. */
3498 trtable
[NEWLINE_CHAR
] = dest_states_nl
[j
];
3499 if (need_word_trtable
)
3500 trtable
[NEWLINE_CHAR
+ SBC_MAX
] = dest_states_nl
[j
];
3501 /* There must be only one destination which accepts
3502 newline. See group_nodes_into_DFAstates. */
3507 if (dest_states_malloced
)
3510 re_node_set_free (&follows
);
3511 for (i
= 0; i
< ndests
; ++i
)
3512 re_node_set_free (dests_node
+ i
);
3514 if (dests_node_malloced
)
3520 /* Group all nodes belonging to STATE into several destinations.
3521 Then for all destinations, set the nodes belonging to the destination
3522 to DESTS_NODE[i] and set the characters accepted by the destination
3523 to DEST_CH[i]. This function return the number of destinations. */
3527 group_nodes_into_DFAstates (const re_dfa_t
*dfa
, const re_dfastate_t
*state
,
3528 re_node_set
*dests_node
, bitset_t
*dests_ch
)
3533 int ndests
; /* Number of the destinations from `state'. */
3534 bitset_t accepts
; /* Characters a node can accept. */
3535 const re_node_set
*cur_nodes
= &state
->nodes
;
3536 bitset_empty (accepts
);
3539 /* For all the nodes belonging to `state', */
3540 for (i
= 0; i
< cur_nodes
->nelem
; ++i
)
3542 re_token_t
*node
= &dfa
->nodes
[cur_nodes
->elems
[i
]];
3543 re_token_type_t type
= node
->type
;
3544 unsigned int constraint
= node
->constraint
;
3546 /* Enumerate all single byte character this node can accept. */
3547 if (type
== CHARACTER
)
3548 bitset_set (accepts
, node
->opr
.c
);
3549 else if (type
== SIMPLE_BRACKET
)
3551 bitset_merge (accepts
, node
->opr
.sbcset
);
3553 else if (type
== OP_PERIOD
)
3555 #ifdef RE_ENABLE_I18N
3556 if (dfa
->mb_cur_max
> 1)
3557 bitset_merge (accepts
, dfa
->sb_char
);
3560 bitset_set_all (accepts
);
3561 if (!(dfa
->syntax
& RE_DOT_NEWLINE
))
3562 bitset_clear (accepts
, '\n');
3563 if (dfa
->syntax
& RE_DOT_NOT_NULL
)
3564 bitset_clear (accepts
, '\0');
3566 #ifdef RE_ENABLE_I18N
3567 else if (type
== OP_UTF8_PERIOD
)
3569 memset (accepts
, '\xff', sizeof (bitset_t
) / 2);
3570 if (!(dfa
->syntax
& RE_DOT_NEWLINE
))
3571 bitset_clear (accepts
, '\n');
3572 if (dfa
->syntax
& RE_DOT_NOT_NULL
)
3573 bitset_clear (accepts
, '\0');
3579 /* Check the `accepts' and sift the characters which are not
3580 match it the context. */
3583 if (constraint
& NEXT_NEWLINE_CONSTRAINT
)
3585 bool accepts_newline
= bitset_contain (accepts
, NEWLINE_CHAR
);
3586 bitset_empty (accepts
);
3587 if (accepts_newline
)
3588 bitset_set (accepts
, NEWLINE_CHAR
);
3592 if (constraint
& NEXT_ENDBUF_CONSTRAINT
)
3594 bitset_empty (accepts
);
3598 if (constraint
& NEXT_WORD_CONSTRAINT
)
3600 bitset_word_t any_set
= 0;
3601 if (type
== CHARACTER
&& !node
->word_char
)
3603 bitset_empty (accepts
);
3606 #ifdef RE_ENABLE_I18N
3607 if (dfa
->mb_cur_max
> 1)
3608 for (j
= 0; j
< BITSET_WORDS
; ++j
)
3609 any_set
|= (accepts
[j
] &= (dfa
->word_char
[j
] | ~dfa
->sb_char
[j
]));
3612 for (j
= 0; j
< BITSET_WORDS
; ++j
)
3613 any_set
|= (accepts
[j
] &= dfa
->word_char
[j
]);
3617 if (constraint
& NEXT_NOTWORD_CONSTRAINT
)
3619 bitset_word_t any_set
= 0;
3620 if (type
== CHARACTER
&& node
->word_char
)
3622 bitset_empty (accepts
);
3625 #ifdef RE_ENABLE_I18N
3626 if (dfa
->mb_cur_max
> 1)
3627 for (j
= 0; j
< BITSET_WORDS
; ++j
)
3628 any_set
|= (accepts
[j
] &= ~(dfa
->word_char
[j
] & dfa
->sb_char
[j
]));
3631 for (j
= 0; j
< BITSET_WORDS
; ++j
)
3632 any_set
|= (accepts
[j
] &= ~dfa
->word_char
[j
]);
3638 /* Then divide `accepts' into DFA states, or create a new
3639 state. Above, we make sure that accepts is not empty. */
3640 for (j
= 0; j
< ndests
; ++j
)
3642 bitset_t intersec
; /* Intersection sets, see below. */
3644 /* Flags, see below. */
3645 bitset_word_t has_intersec
, not_subset
, not_consumed
;
3647 /* Optimization, skip if this state doesn't accept the character. */
3648 if (type
== CHARACTER
&& !bitset_contain (dests_ch
[j
], node
->opr
.c
))
3651 /* Enumerate the intersection set of this state and `accepts'. */
3653 for (k
= 0; k
< BITSET_WORDS
; ++k
)
3654 has_intersec
|= intersec
[k
] = accepts
[k
] & dests_ch
[j
][k
];
3655 /* And skip if the intersection set is empty. */
3659 /* Then check if this state is a subset of `accepts'. */
3660 not_subset
= not_consumed
= 0;
3661 for (k
= 0; k
< BITSET_WORDS
; ++k
)
3663 not_subset
|= remains
[k
] = ~accepts
[k
] & dests_ch
[j
][k
];
3664 not_consumed
|= accepts
[k
] = accepts
[k
] & ~dests_ch
[j
][k
];
3667 /* If this state isn't a subset of `accepts', create a
3668 new group state, which has the `remains'. */
3671 bitset_copy (dests_ch
[ndests
], remains
);
3672 bitset_copy (dests_ch
[j
], intersec
);
3673 err
= re_node_set_init_copy (dests_node
+ ndests
, &dests_node
[j
]);
3674 if (BE (err
!= REG_NOERROR
, 0))
3679 /* Put the position in the current group. */
3680 result
= re_node_set_insert (&dests_node
[j
], cur_nodes
->elems
[i
]);
3681 if (BE (result
< 0, 0))
3684 /* If all characters are consumed, go to next node. */
3688 /* Some characters remain, create a new group. */
3691 bitset_copy (dests_ch
[ndests
], accepts
);
3692 err
= re_node_set_init_1 (dests_node
+ ndests
, cur_nodes
->elems
[i
]);
3693 if (BE (err
!= REG_NOERROR
, 0))
3696 bitset_empty (accepts
);
3701 for (j
= 0; j
< ndests
; ++j
)
3702 re_node_set_free (dests_node
+ j
);
3706 #ifdef RE_ENABLE_I18N
3707 /* Check how many bytes the node `dfa->nodes[node_idx]' accepts.
3708 Return the number of the bytes the node accepts.
3709 STR_IDX is the current index of the input string.
3711 This function handles the nodes which can accept one character, or
3712 one collating element like '.', '[a-z]', opposite to the other nodes
3713 can only accept one byte. */
3717 check_node_accept_bytes (const re_dfa_t
*dfa
, int node_idx
,
3718 const re_string_t
*input
, int str_idx
)
3720 const re_token_t
*node
= dfa
->nodes
+ node_idx
;
3721 int char_len
, elem_len
;
3724 if (BE (node
->type
== OP_UTF8_PERIOD
, 0))
3726 unsigned char c
= re_string_byte_at (input
, str_idx
), d
;
3727 if (BE (c
< 0xc2, 1))
3730 if (str_idx
+ 2 > input
->len
)
3733 d
= re_string_byte_at (input
, str_idx
+ 1);
3735 return (d
< 0x80 || d
> 0xbf) ? 0 : 2;
3739 if (c
== 0xe0 && d
< 0xa0)
3745 if (c
== 0xf0 && d
< 0x90)
3751 if (c
== 0xf8 && d
< 0x88)
3757 if (c
== 0xfc && d
< 0x84)
3763 if (str_idx
+ char_len
> input
->len
)
3766 for (i
= 1; i
< char_len
; ++i
)
3768 d
= re_string_byte_at (input
, str_idx
+ i
);
3769 if (d
< 0x80 || d
> 0xbf)
3775 char_len
= re_string_char_size_at (input
, str_idx
);
3776 if (node
->type
== OP_PERIOD
)
3780 /* FIXME: I don't think this if is needed, as both '\n'
3781 and '\0' are char_len == 1. */
3782 /* '.' accepts any one character except the following two cases. */
3783 if ((!(dfa
->syntax
& RE_DOT_NEWLINE
) &&
3784 re_string_byte_at (input
, str_idx
) == '\n') ||
3785 ((dfa
->syntax
& RE_DOT_NOT_NULL
) &&
3786 re_string_byte_at (input
, str_idx
) == '\0'))
3791 elem_len
= re_string_elem_size_at (input
, str_idx
);
3792 if ((elem_len
<= 1 && char_len
<= 1) || char_len
== 0)
3795 if (node
->type
== COMPLEX_BRACKET
)
3797 const re_charset_t
*cset
= node
->opr
.mbcset
;
3799 const unsigned char *pin
3800 = ((const unsigned char *) re_string_get_buffer (input
) + str_idx
);
3805 wchar_t wc
= ((cset
->nranges
|| cset
->nchar_classes
|| cset
->nmbchars
)
3806 ? re_string_wchar_at (input
, str_idx
) : 0);
3808 /* match with multibyte character? */
3809 for (i
= 0; i
< cset
->nmbchars
; ++i
)
3810 if (wc
== cset
->mbchars
[i
])
3812 match_len
= char_len
;
3813 goto check_node_accept_bytes_match
;
3815 /* match with character_class? */
3816 for (i
= 0; i
< cset
->nchar_classes
; ++i
)
3818 wctype_t wt
= cset
->char_classes
[i
];
3819 if (__iswctype (wc
, wt
))
3821 match_len
= char_len
;
3822 goto check_node_accept_bytes_match
;
3827 nrules
= _NL_CURRENT_WORD (LC_COLLATE
, _NL_COLLATE_NRULES
);
3830 unsigned int in_collseq
= 0;
3831 const int32_t *table
, *indirect
;
3832 const unsigned char *weights
, *extra
;
3833 const char *collseqwc
;
3834 /* This #include defines a local function! */
3835 # include <locale/weight.h>
3837 /* match with collating_symbol? */
3838 if (cset
->ncoll_syms
)
3839 extra
= (const unsigned char *)
3840 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_SYMB_EXTRAMB
);
3841 for (i
= 0; i
< cset
->ncoll_syms
; ++i
)
3843 const unsigned char *coll_sym
= extra
+ cset
->coll_syms
[i
];
3844 /* Compare the length of input collating element and
3845 the length of current collating element. */
3846 if (*coll_sym
!= elem_len
)
3848 /* Compare each bytes. */
3849 for (j
= 0; j
< *coll_sym
; j
++)
3850 if (pin
[j
] != coll_sym
[1 + j
])
3854 /* Match if every bytes is equal. */
3856 goto check_node_accept_bytes_match
;
3862 if (elem_len
<= char_len
)
3864 collseqwc
= _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_COLLSEQWC
);
3865 in_collseq
= __collseq_table_lookup (collseqwc
, wc
);
3868 in_collseq
= find_collation_sequence_value (pin
, elem_len
);
3870 /* match with range expression? */
3871 for (i
= 0; i
< cset
->nranges
; ++i
)
3872 if (cset
->range_starts
[i
] <= in_collseq
3873 && in_collseq
<= cset
->range_ends
[i
])
3875 match_len
= elem_len
;
3876 goto check_node_accept_bytes_match
;
3879 /* match with equivalence_class? */
3880 if (cset
->nequiv_classes
)
3882 const unsigned char *cp
= pin
;
3883 table
= (const int32_t *)
3884 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_TABLEMB
);
3885 weights
= (const unsigned char *)
3886 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_WEIGHTMB
);
3887 extra
= (const unsigned char *)
3888 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_EXTRAMB
);
3889 indirect
= (const int32_t *)
3890 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_INDIRECTMB
);
3891 int32_t idx
= findidx (&cp
);
3893 for (i
= 0; i
< cset
->nequiv_classes
; ++i
)
3895 int32_t equiv_class_idx
= cset
->equiv_classes
[i
];
3896 size_t weight_len
= weights
[idx
& 0xffffff];
3897 if (weight_len
== weights
[equiv_class_idx
& 0xffffff]
3898 && (idx
>> 24) == (equiv_class_idx
>> 24))
3903 equiv_class_idx
&= 0xffffff;
3905 while (cnt
<= weight_len
3906 && (weights
[equiv_class_idx
+ 1 + cnt
]
3907 == weights
[idx
+ 1 + cnt
]))
3909 if (cnt
> weight_len
)
3911 match_len
= elem_len
;
3912 goto check_node_accept_bytes_match
;
3921 /* match with range expression? */
3923 wchar_t cmp_buf
[] = {L
'\0', L
'\0', wc
, L
'\0', L
'\0', L
'\0'};
3925 wchar_t cmp_buf
[] = {L
'\0', L
'\0', L
'\0', L
'\0', L
'\0', L
'\0'};
3928 for (i
= 0; i
< cset
->nranges
; ++i
)
3930 cmp_buf
[0] = cset
->range_starts
[i
];
3931 cmp_buf
[4] = cset
->range_ends
[i
];
3932 if (wcscoll (cmp_buf
, cmp_buf
+ 2) <= 0
3933 && wcscoll (cmp_buf
+ 2, cmp_buf
+ 4) <= 0)
3935 match_len
= char_len
;
3936 goto check_node_accept_bytes_match
;
3940 check_node_accept_bytes_match
:
3941 if (!cset
->non_match
)
3948 return (elem_len
> char_len
) ? elem_len
: char_len
;
3957 find_collation_sequence_value (const unsigned char *mbs
, size_t mbs_len
)
3959 uint32_t nrules
= _NL_CURRENT_WORD (LC_COLLATE
, _NL_COLLATE_NRULES
);
3964 /* No valid character. Match it as a single byte character. */
3965 const unsigned char *collseq
= (const unsigned char *)
3966 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_COLLSEQMB
);
3967 return collseq
[mbs
[0]];
3974 const unsigned char *extra
= (const unsigned char *)
3975 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_SYMB_EXTRAMB
);
3976 int32_t extrasize
= (const unsigned char *)
3977 _NL_CURRENT (LC_COLLATE
, _NL_COLLATE_SYMB_EXTRAMB
+ 1) - extra
;
3979 for (idx
= 0; idx
< extrasize
;)
3981 int mbs_cnt
, found
= 0;
3982 int32_t elem_mbs_len
;
3983 /* Skip the name of collating element name. */
3984 idx
= idx
+ extra
[idx
] + 1;
3985 elem_mbs_len
= extra
[idx
++];
3986 if (mbs_len
== elem_mbs_len
)
3988 for (mbs_cnt
= 0; mbs_cnt
< elem_mbs_len
; ++mbs_cnt
)
3989 if (extra
[idx
+ mbs_cnt
] != mbs
[mbs_cnt
])
3991 if (mbs_cnt
== elem_mbs_len
)
3992 /* Found the entry. */
3995 /* Skip the byte sequence of the collating element. */
3996 idx
+= elem_mbs_len
;
3997 /* Adjust for the alignment. */
3998 idx
= (idx
+ 3) & ~3;
3999 /* Skip the collation sequence value. */
4000 idx
+= sizeof (uint32_t);
4001 /* Skip the wide char sequence of the collating element. */
4002 idx
= idx
+ sizeof (uint32_t) * (extra
[idx
] + 1);
4003 /* If we found the entry, return the sequence value. */
4005 return *(uint32_t *) (extra
+ idx
);
4006 /* Skip the collation sequence value. */
4007 idx
+= sizeof (uint32_t);
4013 #endif /* RE_ENABLE_I18N */
4015 /* Check whether the node accepts the byte which is IDX-th
4016 byte of the INPUT. */
4020 check_node_accept (const re_match_context_t
*mctx
, const re_token_t
*node
,
4024 ch
= re_string_byte_at (&mctx
->input
, idx
);
4028 if (node
->opr
.c
!= ch
)
4032 case SIMPLE_BRACKET
:
4033 if (!bitset_contain (node
->opr
.sbcset
, ch
))
4037 #ifdef RE_ENABLE_I18N
4038 case OP_UTF8_PERIOD
:
4044 if ((ch
== '\n' && !(mctx
->dfa
->syntax
& RE_DOT_NEWLINE
))
4045 || (ch
== '\0' && (mctx
->dfa
->syntax
& RE_DOT_NOT_NULL
)))
4053 if (node
->constraint
)
4055 /* The node has constraints. Check whether the current context
4056 satisfies the constraints. */
4057 unsigned int context
= re_string_context_at (&mctx
->input
, idx
,
4059 if (NOT_SATISFY_NEXT_CONSTRAINT (node
->constraint
, context
))
4066 /* Extend the buffers, if the buffers have run out. */
4068 static reg_errcode_t
4070 extend_buffers (re_match_context_t
*mctx
)
4073 re_string_t
*pstr
= &mctx
->input
;
4075 /* Double the lengthes of the buffers. */
4076 ret
= re_string_realloc_buffers (pstr
, pstr
->bufs_len
* 2);
4077 if (BE (ret
!= REG_NOERROR
, 0))
4080 if (mctx
->state_log
!= NULL
)
4082 /* And double the length of state_log. */
4083 /* XXX We have no indication of the size of this buffer. If this
4084 allocation fail we have no indication that the state_log array
4085 does not have the right size. */
4086 re_dfastate_t
**new_array
= re_realloc (mctx
->state_log
, re_dfastate_t
*,
4087 pstr
->bufs_len
+ 1);
4088 if (BE (new_array
== NULL
, 0))
4090 mctx
->state_log
= new_array
;
4093 /* Then reconstruct the buffers. */
4096 #ifdef RE_ENABLE_I18N
4097 if (pstr
->mb_cur_max
> 1)
4099 ret
= build_wcs_upper_buffer (pstr
);
4100 if (BE (ret
!= REG_NOERROR
, 0))
4104 #endif /* RE_ENABLE_I18N */
4105 build_upper_buffer (pstr
);
4109 #ifdef RE_ENABLE_I18N
4110 if (pstr
->mb_cur_max
> 1)
4111 build_wcs_buffer (pstr
);
4113 #endif /* RE_ENABLE_I18N */
4115 if (pstr
->trans
!= NULL
)
4116 re_string_translate_buffer (pstr
);
4123 /* Functions for matching context. */
4125 /* Initialize MCTX. */
4127 static reg_errcode_t
4129 match_ctx_init (re_match_context_t
*mctx
, int eflags
, int n
)
4131 mctx
->eflags
= eflags
;
4132 mctx
->match_last
= -1;
4135 mctx
->bkref_ents
= re_malloc (struct re_backref_cache_entry
, n
);
4136 mctx
->sub_tops
= re_malloc (re_sub_match_top_t
*, n
);
4137 if (BE (mctx
->bkref_ents
== NULL
|| mctx
->sub_tops
== NULL
, 0))
4140 /* Already zero-ed by the caller.
4142 mctx->bkref_ents = NULL;
4143 mctx->nbkref_ents = 0;
4144 mctx->nsub_tops = 0; */
4145 mctx
->abkref_ents
= n
;
4146 mctx
->max_mb_elem_len
= 1;
4147 mctx
->asub_tops
= n
;
4151 /* Clean the entries which depend on the current input in MCTX.
4152 This function must be invoked when the matcher changes the start index
4153 of the input, or changes the input string. */
4157 match_ctx_clean (re_match_context_t
*mctx
)
4160 for (st_idx
= 0; st_idx
< mctx
->nsub_tops
; ++st_idx
)
4163 re_sub_match_top_t
*top
= mctx
->sub_tops
[st_idx
];
4164 for (sl_idx
= 0; sl_idx
< top
->nlasts
; ++sl_idx
)
4166 re_sub_match_last_t
*last
= top
->lasts
[sl_idx
];
4167 re_free (last
->path
.array
);
4170 re_free (top
->lasts
);
4173 re_free (top
->path
->array
);
4174 re_free (top
->path
);
4179 mctx
->nsub_tops
= 0;
4180 mctx
->nbkref_ents
= 0;
4183 /* Free all the memory associated with MCTX. */
4187 match_ctx_free (re_match_context_t
*mctx
)
4189 /* First, free all the memory associated with MCTX->SUB_TOPS. */
4190 match_ctx_clean (mctx
);
4191 re_free (mctx
->sub_tops
);
4192 re_free (mctx
->bkref_ents
);
4195 /* Add a new backreference entry to MCTX.
4196 Note that we assume that caller never call this function with duplicate
4197 entry, and call with STR_IDX which isn't smaller than any existing entry.
4200 static reg_errcode_t
4202 match_ctx_add_entry (re_match_context_t
*mctx
, int node
, int str_idx
, int from
,
4205 if (mctx
->nbkref_ents
>= mctx
->abkref_ents
)
4207 struct re_backref_cache_entry
* new_entry
;
4208 new_entry
= re_realloc (mctx
->bkref_ents
, struct re_backref_cache_entry
,
4209 mctx
->abkref_ents
* 2);
4210 if (BE (new_entry
== NULL
, 0))
4212 re_free (mctx
->bkref_ents
);
4215 mctx
->bkref_ents
= new_entry
;
4216 memset (mctx
->bkref_ents
+ mctx
->nbkref_ents
, '\0',
4217 sizeof (struct re_backref_cache_entry
) * mctx
->abkref_ents
);
4218 mctx
->abkref_ents
*= 2;
4220 if (mctx
->nbkref_ents
> 0
4221 && mctx
->bkref_ents
[mctx
->nbkref_ents
- 1].str_idx
== str_idx
)
4222 mctx
->bkref_ents
[mctx
->nbkref_ents
- 1].more
= 1;
4224 mctx
->bkref_ents
[mctx
->nbkref_ents
].node
= node
;
4225 mctx
->bkref_ents
[mctx
->nbkref_ents
].str_idx
= str_idx
;
4226 mctx
->bkref_ents
[mctx
->nbkref_ents
].subexp_from
= from
;
4227 mctx
->bkref_ents
[mctx
->nbkref_ents
].subexp_to
= to
;
4229 /* This is a cache that saves negative results of check_dst_limits_calc_pos.
4230 If bit N is clear, means that this entry won't epsilon-transition to
4231 an OP_OPEN_SUBEXP or OP_CLOSE_SUBEXP for the N+1-th subexpression. If
4232 it is set, check_dst_limits_calc_pos_1 will recurse and try to find one
4235 A backreference does not epsilon-transition unless it is empty, so set
4236 to all zeros if FROM != TO. */
4237 mctx
->bkref_ents
[mctx
->nbkref_ents
].eps_reachable_subexps_map
4238 = (from
== to
? ~0 : 0);
4240 mctx
->bkref_ents
[mctx
->nbkref_ents
++].more
= 0;
4241 if (mctx
->max_mb_elem_len
< to
- from
)
4242 mctx
->max_mb_elem_len
= to
- from
;
4246 /* Search for the first entry which has the same str_idx, or -1 if none is
4247 found. Note that MCTX->BKREF_ENTS is already sorted by MCTX->STR_IDX. */
4251 search_cur_bkref_entry (const re_match_context_t
*mctx
, int str_idx
)
4253 int left
, right
, mid
, last
;
4254 last
= right
= mctx
->nbkref_ents
;
4255 for (left
= 0; left
< right
;)
4257 mid
= (left
+ right
) / 2;
4258 if (mctx
->bkref_ents
[mid
].str_idx
< str_idx
)
4263 if (left
< last
&& mctx
->bkref_ents
[left
].str_idx
== str_idx
)
4269 /* Register the node NODE, whose type is OP_OPEN_SUBEXP, and which matches
4272 static reg_errcode_t
4274 match_ctx_add_subtop (re_match_context_t
*mctx
, int node
, int str_idx
)
4277 assert (mctx
->sub_tops
!= NULL
);
4278 assert (mctx
->asub_tops
> 0);
4280 if (BE (mctx
->nsub_tops
== mctx
->asub_tops
, 0))
4282 int new_asub_tops
= mctx
->asub_tops
* 2;
4283 re_sub_match_top_t
**new_array
= re_realloc (mctx
->sub_tops
,
4284 re_sub_match_top_t
*,
4286 if (BE (new_array
== NULL
, 0))
4288 mctx
->sub_tops
= new_array
;
4289 mctx
->asub_tops
= new_asub_tops
;
4291 mctx
->sub_tops
[mctx
->nsub_tops
] = calloc (1, sizeof (re_sub_match_top_t
));
4292 if (BE (mctx
->sub_tops
[mctx
->nsub_tops
] == NULL
, 0))
4294 mctx
->sub_tops
[mctx
->nsub_tops
]->node
= node
;
4295 mctx
->sub_tops
[mctx
->nsub_tops
++]->str_idx
= str_idx
;
4299 /* Register the node NODE, whose type is OP_CLOSE_SUBEXP, and which matches
4300 at STR_IDX, whose corresponding OP_OPEN_SUBEXP is SUB_TOP. */
4302 static re_sub_match_last_t
*
4304 match_ctx_add_sublast (re_sub_match_top_t
*subtop
, int node
, int str_idx
)
4306 re_sub_match_last_t
*new_entry
;
4307 if (BE (subtop
->nlasts
== subtop
->alasts
, 0))
4309 int new_alasts
= 2 * subtop
->alasts
+ 1;
4310 re_sub_match_last_t
**new_array
= re_realloc (subtop
->lasts
,
4311 re_sub_match_last_t
*,
4313 if (BE (new_array
== NULL
, 0))
4315 subtop
->lasts
= new_array
;
4316 subtop
->alasts
= new_alasts
;
4318 new_entry
= calloc (1, sizeof (re_sub_match_last_t
));
4319 if (BE (new_entry
!= NULL
, 1))
4321 subtop
->lasts
[subtop
->nlasts
] = new_entry
;
4322 new_entry
->node
= node
;
4323 new_entry
->str_idx
= str_idx
;
4331 sift_ctx_init (re_sift_context_t
*sctx
, re_dfastate_t
**sifted_sts
,
4332 re_dfastate_t
**limited_sts
, int last_node
, int last_str_idx
)
4334 sctx
->sifted_states
= sifted_sts
;
4335 sctx
->limited_states
= limited_sts
;
4336 sctx
->last_node
= last_node
;
4337 sctx
->last_str_idx
= last_str_idx
;
4338 re_node_set_init_empty (&sctx
->limits
);