]> git.ipfire.org Git - thirdparty/glibc.git/blame - posix/regexec.c
projects / thirdparty / glibc.git / blame
? search:
summary | shortlog | log | commit | commitdiff | tree
blob | blame (incremental) | history | HEAD
[BZ #1466]
[thirdparty/glibc.git] / posix / regexec.c
CommitLineData
3b0bdc72 1/* Extended regular expression matching and search library.
1c99f950 2 Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
3b0bdc72
UD		 3 This file is part of the GNU C Library.
4 Contributed by Isamu Hasegawa <isamu@yamato.ibm.com>.
5
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.
10
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.
15
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
19 02111-1307 USA. */
20
a9388965 21static reg_errcode_t match_ctx_init (re_match_context_t *cache, int eflags,
56b168be 22 int n) internal_function;
3ce12656
UD		 23static void match_ctx_clean (re_match_context_t *mctx) internal_function;
24static void match_ctx_free (re_match_context_t *cache) internal_function;
a9388965 25static reg_errcode_t match_ctx_add_entry (re_match_context_t *cache, int node,
e3a87852
UD		 26 int str_idx, int from, int to)
27 internal_function;
01ed6ceb 28static int search_cur_bkref_entry (const re_match_context_t *mctx, int str_idx)
e3a87852 29 internal_function;
6291ee3c 30static reg_errcode_t match_ctx_add_subtop (re_match_context_t *mctx, int node,
3ce12656 31 int str_idx) internal_function;
6291ee3c 32static re_sub_match_last_t * match_ctx_add_sublast (re_sub_match_top_t *subtop,
e3a87852
UD		 33 int node, int str_idx)
34 internal_function;
0742e48e 35static void sift_ctx_init (re_sift_context_t *sctx, re_dfastate_t **sifted_sts,
15a7d175 36 re_dfastate_t **limited_sts, int last_node,
d2c38eb3 37 int last_str_idx)
e3a87852 38 internal_function;
a9388965 39static reg_errcode_t re_search_internal (const regex_t *preg,
15a7d175
UD		 40 const char *string, int length,
41 int start, int range, int stop,
42 size_t nmatch, regmatch_t pmatch[],
3ce12656 43 int eflags) internal_function;
ac3d553b 44static int re_search_2_stub (struct re_pattern_buffer *bufp,
15a7d175
UD		 45 const char *string1, int length1,
46 const char *string2, int length2,
47 int start, int range, struct re_registers *regs,
3ce12656 48 int stop, int ret_len) internal_function;
ac3d553b 49static int re_search_stub (struct re_pattern_buffer *bufp,
15a7d175
UD		 50 const char *string, int length, int start,
51 int range, int stop, struct re_registers *regs,
3ce12656 52 int ret_len) internal_function;
ac3d553b 53static unsigned re_copy_regs (struct re_registers *regs, regmatch_t *pmatch,
3ce12656 54 int nregs, int regs_allocated) internal_function;
a334319f
UD		 55static inline re_dfastate_t *acquire_init_state_context
56 (reg_errcode_t *err, const re_match_context_t *mctx, int idx)
57 __attribute ((always_inline)) internal_function;
e3a87852
UD		 58static reg_errcode_t prune_impossible_nodes (re_match_context_t *mctx)
59 internal_function;
15bad1a5 60static int check_matching (re_match_context_t *mctx, int fl_longest_match,
76b864c8 61 int *p_match_first) internal_function;
a334319f
UD		 62static int check_halt_node_context (const re_dfa_t *dfa, int node,
63 unsigned int context) internal_function;
e3a87852
UD		 64static int check_halt_state_context (const re_match_context_t *mctx,
65 const re_dfastate_t *state, int idx)
66 internal_function;
76b864c8 67static void update_regs (const re_dfa_t *dfa, regmatch_t *pmatch,
6b6557e8 68 regmatch_t *prev_idx_match, int cur_node,
3ce12656 69 int cur_idx, int nmatch) internal_function;
a334319f
UD		 70static int proceed_next_node (const re_match_context_t *mctx,
71 int nregs, regmatch_t *regs,
72 int *pidx, int node, re_node_set *eps_via_nodes,
73 struct re_fail_stack_t *fs) internal_function;
1b2c2628 74static reg_errcode_t push_fail_stack (struct re_fail_stack_t *fs,
5cf1ec52 75 int str_idx, int dest_node, int nregs,
15a7d175 76 regmatch_t *regs,
76b864c8
UD		 77 re_node_set *eps_via_nodes)
78 internal_function;
a334319f 79static int pop_fail_stack (struct re_fail_stack_t *fs, int *pidx, int nregs,
76b864c8
UD		 80 regmatch_t *regs, re_node_set *eps_via_nodes)
81 internal_function;
612546c6 82static reg_errcode_t set_regs (const regex_t *preg,
15a7d175
UD		 83 const re_match_context_t *mctx,
84 size_t nmatch, regmatch_t *pmatch,
3ce12656 85 int fl_backtrack) internal_function;
76b864c8
UD		 86static reg_errcode_t free_fail_stack_return (struct re_fail_stack_t *fs)
87 internal_function;
485d775d 88
434d3784 89#ifdef RE_ENABLE_I18N
e3a87852 90static int sift_states_iter_mb (const re_match_context_t *mctx,
15a7d175 91 re_sift_context_t *sctx,
76b864c8
UD		 92 int node_idx, int str_idx, int max_str_idx)
93 internal_function;
434d3784 94#endif /* RE_ENABLE_I18N */
76b864c8
UD		 95static reg_errcode_t sift_states_backward (const re_match_context_t *mctx,
96 re_sift_context_t *sctx)
97 internal_function;
98static reg_errcode_t build_sifted_states (const re_match_context_t *mctx,
e40a38b3 99 re_sift_context_t *sctx, int str_idx,
76b864c8
UD		 100 re_node_set *cur_dest)
101 internal_function;
102static reg_errcode_t update_cur_sifted_state (const re_match_context_t *mctx,
15a7d175
UD		 103 re_sift_context_t *sctx,
104 int str_idx,
76b864c8
UD		 105 re_node_set *dest_nodes)
106 internal_function;
107static reg_errcode_t add_epsilon_src_nodes (const re_dfa_t *dfa,
15a7d175 108 re_node_set *dest_nodes,
76b864c8
UD		 109 const re_node_set *candidates)
110 internal_function;
111static reg_errcode_t sub_epsilon_src_nodes (const re_dfa_t *dfa, int node,
a334319f 112 re_node_set *dest_nodes,
76b864c8
UD		 113 const re_node_set *and_nodes)
114 internal_function;
01ed6ceb
UD		 115static int check_dst_limits (const re_match_context_t *mctx,
116 re_node_set *limits,
e3a87852
UD		 117 int dst_node, int dst_idx, int src_node,
118 int src_idx) internal_function;
01ed6ceb 119static int check_dst_limits_calc_pos_1 (const re_match_context_t *mctx,
e40a38b3 120 int boundaries, int subexp_idx,
76b864c8
UD		 121 int from_node, int bkref_idx)
122 internal_function;
01ed6ceb 123static int check_dst_limits_calc_pos (const re_match_context_t *mctx,
e40a38b3
UD		 124 int limit, int subexp_idx,
125 int node, int str_idx,
126 int bkref_idx) internal_function;
76b864c8 127static reg_errcode_t check_subexp_limits (const re_dfa_t *dfa,
15a7d175
UD		 128 re_node_set *dest_nodes,
129 const re_node_set *candidates,
130 re_node_set *limits,
131 struct re_backref_cache_entry *bkref_ents,
3ce12656 132 int str_idx) internal_function;
76b864c8 133static reg_errcode_t sift_states_bkref (const re_match_context_t *mctx,
15a7d175 134 re_sift_context_t *sctx,
76b864c8
UD		 135 int str_idx, const re_node_set *candidates)
136 internal_function;
a334319f 137static reg_errcode_t clean_state_log_if_needed (re_match_context_t *mctx,
76b864c8
UD		 138 int next_state_log_idx)
139 internal_function;
140static reg_errcode_t merge_state_array (const re_dfa_t *dfa,
141 re_dfastate_t **dst,
142 re_dfastate_t **src, int num)
143 internal_function;
4c595adb
UD		 144static re_dfastate_t *find_recover_state (reg_errcode_t *err,
145 re_match_context_t *mctx) internal_function;
e3a87852 146static re_dfastate_t *transit_state (reg_errcode_t *err,
15a7d175 147 re_match_context_t *mctx,
3ce12656 148 re_dfastate_t *state) internal_function;
4c595adb
UD		 149static re_dfastate_t *merge_state_with_log (reg_errcode_t *err,
150 re_match_context_t *mctx,
76b864c8
UD		 151 re_dfastate_t *next_state)
152 internal_function;
e3a87852 153static reg_errcode_t check_subexp_matching_top (re_match_context_t *mctx,
6291ee3c 154 re_node_set *cur_nodes,
3ce12656 155 int str_idx) internal_function;
c13c99fa 156#if 0
e3a87852
UD		 157static re_dfastate_t *transit_state_sb (reg_errcode_t *err,
158 re_match_context_t *mctx,
76b864c8
UD		 159 re_dfastate_t *pstate)
160 internal_function;
c13c99fa 161#endif
434d3784 162#ifdef RE_ENABLE_I18N
e3a87852 163static reg_errcode_t transit_state_mb (re_match_context_t *mctx,
76b864c8
UD		 164 re_dfastate_t *pstate)
165 internal_function;
434d3784 166#endif /* RE_ENABLE_I18N */
e3a87852 167static reg_errcode_t transit_state_bkref (re_match_context_t *mctx,
76b864c8
UD		 168 const re_node_set *nodes)
169 internal_function;
e3a87852 170static reg_errcode_t get_subexp (re_match_context_t *mctx,
76b864c8
UD		 171 int bkref_node, int bkref_str_idx)
172 internal_function;
e3a87852 173static reg_errcode_t get_subexp_sub (re_match_context_t *mctx,
fe9434bb 174 const re_sub_match_top_t *sub_top,
6291ee3c 175 re_sub_match_last_t *sub_last,
76b864c8
UD		 176 int bkref_node, int bkref_str)
177 internal_function;
fe9434bb 178static int find_subexp_node (const re_dfa_t *dfa, const re_node_set *nodes,
3ce12656 179 int subexp_idx, int type) internal_function;
e3a87852 180static reg_errcode_t check_arrival (re_match_context_t *mctx,
6291ee3c
UD		 181 state_array_t *path, int top_node,
182 int top_str, int last_node, int last_str,
3ce12656 183 int type) internal_function;
e3a87852 184static reg_errcode_t check_arrival_add_next_nodes (re_match_context_t *mctx,
6291ee3c
UD		 185 int str_idx,
186 re_node_set *cur_nodes,
76b864c8
UD		 187 re_node_set *next_nodes)
188 internal_function;
6efbd82c 189static reg_errcode_t check_arrival_expand_ecl (const re_dfa_t *dfa,
6291ee3c 190 re_node_set *cur_nodes,
76b864c8
UD		 191 int ex_subexp, int type)
192 internal_function;
6efbd82c 193static reg_errcode_t check_arrival_expand_ecl_sub (const re_dfa_t *dfa,
6291ee3c
UD		 194 re_node_set *dst_nodes,
195 int target, int ex_subexp,
3ce12656 196 int type) internal_function;
e3a87852 197static reg_errcode_t expand_bkref_cache (re_match_context_t *mctx,
6291ee3c 198 re_node_set *cur_nodes, int cur_str,
76b864c8
UD		 199 int subexp_num, int type)
200 internal_function;
201static int build_trtable (const re_dfa_t *dfa,
ab4b89fe 202 re_dfastate_t *state) internal_function;
434d3784 203#ifdef RE_ENABLE_I18N
c42b4152 204static int check_node_accept_bytes (const re_dfa_t *dfa, int node_idx,
76b864c8
UD		 205 const re_string_t *input, int idx)
206 internal_function;
434d3784 207# ifdef _LIBC
c202c2c5 208static unsigned int find_collation_sequence_value (const unsigned char *mbs,
76b864c8
UD		 209 size_t name_len)
210 internal_function;
434d3784
UD		 211# endif /* _LIBC */
212#endif /* RE_ENABLE_I18N */
01ed6ceb 213static int group_nodes_into_DFAstates (const re_dfa_t *dfa,
15a7d175
UD		 214 const re_dfastate_t *state,
215 re_node_set *states_node,
2c05d33f 216 bitset_t *states_ch) internal_function;
e3a87852 217static int check_node_accept (const re_match_context_t *mctx,
76b864c8
UD		 218 const re_token_t *node, int idx)
219 internal_function;
220static reg_errcode_t extend_buffers (re_match_context_t *mctx)
221 internal_function;
3b0bdc72
UD		 222\f
223/* Entry point for POSIX code. */
224
225/* regexec searches for a given pattern, specified by PREG, in the
226 string STRING.
227
228 If NMATCH is zero or REG_NOSUB was set in the cflags argument to
229 `regcomp', we ignore PMATCH. Otherwise, we assume PMATCH has at
230 least NMATCH elements, and we set them to the offsets of the
231 corresponding matched substrings.
232
233 EFLAGS specifies `execution flags' which affect matching: if
234 REG_NOTBOL is set, then ^ does not match at the beginning of the
235 string; if REG_NOTEOL is set, then $ does not match at the end.
236
237 We return 0 if we find a match and REG_NOMATCH if not. */
238
239int
240regexec (preg, string, nmatch, pmatch, eflags)
92b27c74
UD		 241 const regex_t *__restrict preg;
242 const char *__restrict string;
3b0bdc72
UD		 243 size_t nmatch;
244 regmatch_t pmatch[];
245 int eflags;
246{
a9388965 247 reg_errcode_t err;
6fefb4e0 248 int start, length;
76b864c8 249 re_dfa_t *dfa = (re_dfa_t *) preg->buffer;
3f2fb223
UD		 250
251 if (eflags & ~(REG_NOTBOL | REG_NOTEOL | REG_STARTEND))
252 return REG_BADPAT;
253
6fefb4e0
UD		 254 if (eflags & REG_STARTEND)
255 {
256 start = pmatch[0].rm_so;
257 length = pmatch[0].rm_eo;
258 }
259 else
260 {
261 start = 0;
262 length = strlen (string);
263 }
7b918993
UD		 264
265 __libc_lock_lock (dfa->lock);
3b0bdc72 266 if (preg->no_sub)
6fefb4e0
UD		 267 err = re_search_internal (preg, string, length, start, length - start,
268 length, 0, NULL, eflags);
3b0bdc72 269 else
6fefb4e0
UD		 270 err = re_search_internal (preg, string, length, start, length - start,
271 length, nmatch, pmatch, eflags);
7b918993 272 __libc_lock_unlock (dfa->lock);
a9388965 273 return err != REG_NOERROR;
3b0bdc72 274}
3f2fb223 275
3b0bdc72 276#ifdef _LIBC
3f2fb223
UD		 277# include <shlib-compat.h>
278versioned_symbol (libc, __regexec, regexec, GLIBC_2_3_4);
279
280# if SHLIB_COMPAT (libc, GLIBC_2_0, GLIBC_2_3_4)
281__typeof__ (__regexec) __compat_regexec;
282
283int
78678039 284attribute_compat_text_section
3f2fb223
UD		 285__compat_regexec (const regex_t *__restrict preg,
286 const char *__restrict string, size_t nmatch,
287 regmatch_t pmatch[], int eflags)
288{
289 return regexec (preg, string, nmatch, pmatch,
290 eflags & (REG_NOTBOL | REG_NOTEOL));
291}
292compat_symbol (libc, __compat_regexec, regexec, GLIBC_2_0);
293# endif
3b0bdc72
UD		 294#endif
295
296/* Entry points for GNU code. */
297
ac3d553b
UD		 298/* re_match, re_search, re_match_2, re_search_2
299
300 The former two functions operate on STRING with length LENGTH,
301 while the later two operate on concatenation of STRING1 and STRING2
302 with lengths LENGTH1 and LENGTH2, respectively.
303
304 re_match() matches the compiled pattern in BUFP against the string,
305 starting at index START.
306
307 re_search() first tries matching at index START, then it tries to match
308 starting from index START + 1, and so on. The last start position tried
309 is START + RANGE. (Thus RANGE = 0 forces re_search to operate the same
310 way as re_match().)
311
312 The parameter STOP of re_{match,search}_2 specifies that no match exceeding
313 the first STOP characters of the concatenation of the strings should be
314 concerned.
315
316 If REGS is not NULL, and BUFP->no_sub is not set, the offsets of the match
317 and all groups is stroed in REGS. (For the "_2" variants, the offsets are
318 computed relative to the concatenation, not relative to the individual
319 strings.)
320
321 On success, re_match* functions return the length of the match, re_search*
322 return the position of the start of the match. Return value -1 means no
323 match was found and -2 indicates an internal error. */
3b0bdc72
UD		 324
325int
ac3d553b
UD		 326re_match (bufp, string, length, start, regs)
327 struct re_pattern_buffer *bufp;
3b0bdc72
UD		 328 const char *string;
329 int length, start;
330 struct re_registers *regs;
331{
ac3d553b 332 return re_search_stub (bufp, string, length, start, 0, length, regs, 1);
3b0bdc72
UD		 333}
334#ifdef _LIBC
335weak_alias (__re_match, re_match)
336#endif
337
ac3d553b
UD		 338int
339re_search (bufp, string, length, start, range, regs)
340 struct re_pattern_buffer *bufp;
341 const char *string;
342 int length, start, range;
343 struct re_registers *regs;
344{
345 return re_search_stub (bufp, string, length, start, range, length, regs, 0);
346}
347#ifdef _LIBC
348weak_alias (__re_search, re_search)
349#endif
3b0bdc72
UD		 350
351int
ac3d553b
UD		 352re_match_2 (bufp, string1, length1, string2, length2, start, regs, stop)
353 struct re_pattern_buffer *bufp;
354 const char *string1, *string2;
355 int length1, length2, start, stop;
356 struct re_registers *regs;
3b0bdc72 357{
ac3d553b 358 return re_search_2_stub (bufp, string1, length1, string2, length2,
15a7d175 359 start, 0, regs, stop, 1);
3b0bdc72
UD		 360}
361#ifdef _LIBC
362weak_alias (__re_match_2, re_match_2)
363#endif
364
3b0bdc72 365int
ac3d553b
UD		 366re_search_2 (bufp, string1, length1, string2, length2, start, range, regs, stop)
367 struct re_pattern_buffer *bufp;
368 const char *string1, *string2;
369 int length1, length2, start, range, stop;
370 struct re_registers *regs;
371{
372 return re_search_2_stub (bufp, string1, length1, string2, length2,
15a7d175 373 start, range, regs, stop, 0);
ac3d553b
UD		 374}
375#ifdef _LIBC
376weak_alias (__re_search_2, re_search_2)
377#endif
378
379static int
380re_search_2_stub (bufp, string1, length1, string2, length2, start, range, regs,
15a7d175 381 stop, ret_len)
ac3d553b
UD		 382 struct re_pattern_buffer *bufp;
383 const char *string1, *string2;
384 int length1, length2, start, range, stop, ret_len;
385 struct re_registers *regs;
386{
387 const char *str;
388 int rval;
389 int len = length1 + length2;
390 int free_str = 0;
391
392 if (BE (length1 < 0 || length2 < 0 || stop < 0, 0))
393 return -2;
394
395 /* Concatenate the strings. */
396 if (length2 > 0)
397 if (length1 > 0)
398 {
15a7d175
UD		 399 char *s = re_malloc (char, len);
400
401 if (BE (s == NULL, 0))
402 return -2;
c42b4152
UD		 403#ifdef _LIBC
404 memcpy (__mempcpy (s, string1, length1), string2, length2);
405#else
15a7d175
UD		 406 memcpy (s, string1, length1);
407 memcpy (s + length1, string2, length2);
c42b4152 408#endif
15a7d175
UD		 409 str = s;
410 free_str = 1;
ac3d553b
UD		 411 }
412 else
413 str = string2;
414 else
415 str = string1;
416
417 rval = re_search_stub (bufp, str, len, start, range, stop, regs,
15a7d175 418 ret_len);
ac3d553b 419 if (free_str)
1b2c2628 420 re_free ((char *) str);
ac3d553b
UD		 421 return rval;
422}
423
424/* The parameters have the same meaning as those of re_search.
425 Additional parameters:
426 If RET_LEN is nonzero the length of the match is returned (re_match style);
427 otherwise the position of the match is returned. */
428
429static int
430re_search_stub (bufp, string, length, start, range, stop, regs, ret_len)
431 struct re_pattern_buffer *bufp;
432 const char *string;
433 int length, start, range, stop, ret_len;
434 struct re_registers *regs;
3b0bdc72 435{
a9388965 436 reg_errcode_t result;
3b0bdc72 437 regmatch_t *pmatch;
ac3d553b
UD		 438 int nregs, rval;
439 int eflags = 0;
76b864c8 440 re_dfa_t *dfa = (re_dfa_t *) bufp->buffer;
ac3d553b
UD		 441
442 /* Check for out-of-range. */
a877402c 443 if (BE (start < 0 || start > length, 0))
ac3d553b
UD		 444 return -1;
445 if (BE (start + range > length, 0))
446 range = length - start;
a877402c
UD		 447 else if (BE (start + range < 0, 0))
448 range = -start;
3b0bdc72 449
7b918993
UD		 450 __libc_lock_lock (dfa->lock);
451
3b0bdc72
UD		 452 eflags |= (bufp->not_bol) ? REG_NOTBOL : 0;
453 eflags |= (bufp->not_eol) ? REG_NOTEOL : 0;
454
ac3d553b
UD		 455 /* Compile fastmap if we haven't yet. */
456 if (range > 0 && bufp->fastmap != NULL && !bufp->fastmap_accurate)
457 re_compile_fastmap (bufp);
458
459 if (BE (bufp->no_sub, 0))
460 regs = NULL;
3b0bdc72
UD		 461
462 /* We need at least 1 register. */
ac3d553b
UD		 463 if (regs == NULL)
464 nregs = 1;
465 else if (BE (bufp->regs_allocated == REGS_FIXED &&
15a7d175 466 regs->num_regs < bufp->re_nsub + 1, 0))
ac3d553b
UD		 467 {
468 nregs = regs->num_regs;
469 if (BE (nregs < 1, 0))
15a7d175
UD		 470 {
471 /* Nothing can be copied to regs. */
472 regs = NULL;
473 nregs = 1;
474 }
ac3d553b
UD		 475 }
476 else
477 nregs = bufp->re_nsub + 1;
3b0bdc72 478 pmatch = re_malloc (regmatch_t, nregs);
bc15410e 479 if (BE (pmatch == NULL, 0))
7b918993
UD		 480 {
481 rval = -2;
482 goto out;
483 }
3b0bdc72 484
ac3d553b 485 result = re_search_internal (bufp, string, length, start, range, stop,
15a7d175 486 nregs, pmatch, eflags);
3b0bdc72 487
ac3d553b
UD		 488 rval = 0;
489
490 /* I hope we needn't fill ther regs with -1's when no match was found. */
491 if (result != REG_NOERROR)
492 rval = -1;
493 else if (regs != NULL)
3b0bdc72 494 {
ac3d553b
UD		 495 /* If caller wants register contents data back, copy them. */
496 bufp->regs_allocated = re_copy_regs (regs, pmatch, nregs,
15a7d175 497 bufp->regs_allocated);
ac3d553b 498 if (BE (bufp->regs_allocated == REGS_UNALLOCATED, 0))
15a7d175 499 rval = -2;
3b0bdc72
UD		 500 }
501
ac3d553b 502 if (BE (rval == 0, 1))
3b0bdc72 503 {
ac3d553b 504 if (ret_len)
15a7d175
UD		 505 {
506 assert (pmatch[0].rm_so == start);
507 rval = pmatch[0].rm_eo - start;
508 }
ac3d553b 509 else
15a7d175 510 rval = pmatch[0].rm_so;
3b0bdc72 511 }
3b0bdc72 512 re_free (pmatch);
7b918993
UD		 513 out:
514 __libc_lock_unlock (dfa->lock);
3b0bdc72
UD		 515 return rval;
516}
3b0bdc72 517
ac3d553b
UD		 518static unsigned
519re_copy_regs (regs, pmatch, nregs, regs_allocated)
3b0bdc72 520 struct re_registers *regs;
ac3d553b
UD		 521 regmatch_t *pmatch;
522 int nregs, regs_allocated;
3b0bdc72 523{
ac3d553b
UD		 524 int rval = REGS_REALLOCATE;
525 int i;
526 int need_regs = nregs + 1;
527 /* We need one extra element beyond `num_regs' for the `-1' marker GNU code
528 uses. */
529
530 /* Have the register data arrays been allocated? */
531 if (regs_allocated == REGS_UNALLOCATED)
44777771 532 { /* No. So allocate them with malloc. */
a96c63ed
UD		 533 regs->start = re_malloc (regoff_t, need_regs);
534 regs->end = re_malloc (regoff_t, need_regs);
535 if (BE (regs->start == NULL, 0) || BE (regs->end == NULL, 0))
15a7d175 536 return REGS_UNALLOCATED;
ac3d553b
UD		 537 regs->num_regs = need_regs;
538 }
539 else if (regs_allocated == REGS_REALLOCATE)
540 { /* Yes. If we need more elements than were already
15a7d175
UD		 541 allocated, reallocate them. If we need fewer, just
542 leave it alone. */
951d6408 543 if (BE (need_regs > regs->num_regs, 0))
15a7d175 544 {
44777771
UD		 545 regoff_t *new_start = re_realloc (regs->start, regoff_t, need_regs);
546 regoff_t *new_end = re_realloc (regs->end, regoff_t, need_regs);
547 if (BE (new_start == NULL, 0) || BE (new_end == NULL, 0))
a96c63ed 548 return REGS_UNALLOCATED;
44777771
UD		 549 regs->start = new_start;
550 regs->end = new_end;
15a7d175
UD		 551 regs->num_regs = need_regs;
552 }
ac3d553b
UD		 553 }
554 else
555 {
556 assert (regs_allocated == REGS_FIXED);
557 /* This function may not be called with REGS_FIXED and nregs too big. */
558 assert (regs->num_regs >= nregs);
559 rval = REGS_FIXED;
560 }
561
562 /* Copy the regs. */
563 for (i = 0; i < nregs; ++i)
564 {
565 regs->start[i] = pmatch[i].rm_so;
566 regs->end[i] = pmatch[i].rm_eo;
567 }
568 for ( ; i < regs->num_regs; ++i)
569 regs->start[i] = regs->end[i] = -1;
570
571 return rval;
3b0bdc72 572}
3b0bdc72
UD		 573
574/* Set REGS to hold NUM_REGS registers, storing them in STARTS and
575 ENDS. Subsequent matches using PATTERN_BUFFER and REGS will use
576 this memory for recording register information. STARTS and ENDS
577 must be allocated using the malloc library routine, and must each
578 be at least NUM_REGS * sizeof (regoff_t) bytes long.
579
580 If NUM_REGS == 0, then subsequent matches should allocate their own
581 register data.
582
583 Unless this function is called, the first search or match using
584 PATTERN_BUFFER will allocate its own register data, without
585 freeing the old data. */
586
587void
588re_set_registers (bufp, regs, num_regs, starts, ends)
589 struct re_pattern_buffer *bufp;
590 struct re_registers *regs;
591 unsigned num_regs;
592 regoff_t *starts, *ends;
593{
594 if (num_regs)
595 {
596 bufp->regs_allocated = REGS_REALLOCATE;
597 regs->num_regs = num_regs;
598 regs->start = starts;
599 regs->end = ends;
600 }
601 else
602 {
603 bufp->regs_allocated = REGS_UNALLOCATED;
604 regs->num_regs = 0;
605 regs->start = regs->end = (regoff_t *) 0;
606 }
607}
608#ifdef _LIBC
609weak_alias (__re_set_registers, re_set_registers)
610#endif
611\f
612/* Entry points compatible with 4.2 BSD regex library. We don't define
613 them unless specifically requested. */
614
615#if defined _REGEX_RE_COMP || defined _LIBC
616int
617# ifdef _LIBC
618weak_function
619# endif
620re_exec (s)
621 const char *s;
622{
623 return 0 == regexec (&re_comp_buf, s, 0, NULL, 0);
624}
625#endif /* _REGEX_RE_COMP */
626\f
3b0bdc72
UD		 627/* Internal entry point. */
628
629/* Searches for a compiled pattern PREG in the string STRING, whose
630 length is LENGTH. NMATCH, PMATCH, and EFLAGS have the same
631 mingings with regexec. START, and RANGE have the same meanings
632 with re_search.
a9388965
UD		 633 Return REG_NOERROR if we find a match, and REG_NOMATCH if not,
634 otherwise return the error code.
3b0bdc72
UD		 635 Note: We assume front end functions already check ranges.
636 (START + RANGE >= 0 && START + RANGE <= LENGTH) */
637
a9388965 638static reg_errcode_t
ac3d553b 639re_search_internal (preg, string, length, start, range, stop, nmatch, pmatch,
15a7d175 640 eflags)
3b0bdc72
UD		 641 const regex_t *preg;
642 const char *string;
ac3d553b 643 int length, start, range, stop, eflags;
3b0bdc72
UD		 644 size_t nmatch;
645 regmatch_t pmatch[];
646{
a9388965 647 reg_errcode_t err;
76b864c8 648 const re_dfa_t *dfa = (const re_dfa_t *) preg->buffer;
612546c6 649 int left_lim, right_lim, incr;
bb677c95 650 int fl_longest_match, match_first, match_kind, match_last = -1;
963d8d78 651 int extra_nmatch;
bb677c95 652 int sb, ch;
e3a87852
UD		 653#if defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L)
654 re_match_context_t mctx = { .dfa = dfa };
655#else
3b0bdc72 656 re_match_context_t mctx;
e3a87852 657#endif
bb677c95
UD		 658 char *fastmap = (preg->fastmap != NULL && preg->fastmap_accurate
659 && range && !preg->can_be_null) ? preg->fastmap : NULL;
997470b3 660 RE_TRANSLATE_TYPE t = preg->translate;
3b0bdc72 661
e3a87852
UD		 662#if !(defined _LIBC || (defined __STDC_VERSION__ && __STDC_VERSION__ >= 199901L))
663 memset (&mctx, '\0', sizeof (re_match_context_t));
664 mctx.dfa = dfa;
665#endif
666
963d8d78
UD		 667 extra_nmatch = (nmatch > preg->re_nsub) ? nmatch - (preg->re_nsub + 1) : 0;
668 nmatch -= extra_nmatch;
669
3b0bdc72 670 /* Check if the DFA haven't been compiled. */
bc15410e 671 if (BE (preg->used == 0 || dfa->init_state == NULL
15a7d175
UD		 672 || dfa->init_state_word == NULL || dfa->init_state_nl == NULL
673 || dfa->init_state_begbuf == NULL, 0))
a9388965 674 return REG_NOMATCH;
3b0bdc72 675
c70f81dd
UD		 676#ifdef DEBUG
677 /* We assume front-end functions already check them. */
678 assert (start + range >= 0 && start + range <= length);
679#endif
680
681 /* If initial states with non-begbuf contexts have no elements,
682 the regex must be anchored. If preg->newline_anchor is set,
683 we'll never use init_state_nl, so do not check it. */
684 if (dfa->init_state->nodes.nelem == 0
685 && dfa->init_state_word->nodes.nelem == 0
686 && (dfa->init_state_nl->nodes.nelem == 0
687 || !preg->newline_anchor))
688 {
689 if (start != 0 && start + range != 0)
690 return REG_NOMATCH;
691 start = range = 0;
692 }
693
3b0bdc72 694 /* We must check the longest matching, if nmatch > 0. */
6291ee3c 695 fl_longest_match = (nmatch != 0 || dfa->nbackref);
3b0bdc72 696
56b168be 697 err = re_string_allocate (&mctx.input, string, length, dfa->nodes_len + 1,
f0c7c524 698 preg->translate, preg->syntax & RE_ICASE, dfa);
612546c6 699 if (BE (err != REG_NOERROR, 0))
1b2c2628 700 goto free_return;
56b168be
UD		 701 mctx.input.stop = stop;
702 mctx.input.raw_stop = stop;
703 mctx.input.newline_anchor = preg->newline_anchor;
612546c6 704
56b168be 705 err = match_ctx_init (&mctx, eflags, dfa->nbackref * 2);
612546c6 706 if (BE (err != REG_NOERROR, 0))
1b2c2628 707 goto free_return;
612546c6 708
3b0bdc72
UD		 709 /* We will log all the DFA states through which the dfa pass,
710 if nmatch > 1, or this dfa has "multibyte node", which is a
711 back-reference or a node which can accept multibyte character or
712 multi character collating element. */
713 if (nmatch > 1 || dfa->has_mb_node)
a9388965 714 {
56b168be 715 mctx.state_log = re_malloc (re_dfastate_t *, mctx.input.bufs_len + 1);
612546c6 716 if (BE (mctx.state_log == NULL, 0))
15a7d175
UD		 717 {
718 err = REG_ESPACE;
719 goto free_return;
720 }
a9388965 721 }
3b0bdc72 722 else
612546c6 723 mctx.state_log = NULL;
3b0bdc72 724
612546c6 725 match_first = start;
56b168be
UD		 726 mctx.input.tip_context = (eflags & REG_NOTBOL) ? CONTEXT_BEGBUF
727 : CONTEXT_NEWLINE | CONTEXT_BEGBUF;
612546c6 728
3b0bdc72 729 /* Check incrementally whether of not the input string match. */
612546c6
UD		 730 incr = (range < 0) ? -1 : 1;
731 left_lim = (range < 0) ? start + range : start;
732 right_lim = (range < 0) ? start : start + range;
3c0fb574 733 sb = dfa->mb_cur_max == 1;
bb677c95
UD		 734 match_kind =
735 (fastmap
736 ? ((sb || !(preg->syntax & RE_ICASE || t) ? 4 : 0)
737 | (range >= 0 ? 2 : 0)
738 | (t != NULL ? 1 : 0))
739 : 8);
740
741 for (;; match_first += incr)
3b0bdc72 742 {
bb677c95
UD		 743 err = REG_NOMATCH;
744 if (match_first < left_lim || right_lim < match_first)
745 goto free_return;
746
747 /* Advance as rapidly as possible through the string, until we
748 find a plausible place to start matching. This may be done
749 with varying efficiency, so there are various possibilities:
750 only the most common of them are specialized, in order to
751 save on code size. We use a switch statement for speed. */
752 switch (match_kind)
1b2c2628 753 {
bb677c95
UD		 754 case 8:
755 /* No fastmap. */
756 break;
757
758 case 7:
759 /* Fastmap with single-byte translation, match forward. */
760 while (BE (match_first < right_lim, 1)
761 && !fastmap[t[(unsigned char) string[match_first]]])
762 ++match_first;
763 goto forward_match_found_start_or_reached_end;
764
765 case 6:
766 /* Fastmap without translation, match forward. */
767 while (BE (match_first < right_lim, 1)
768 && !fastmap[(unsigned char) string[match_first]])
769 ++match_first;
770
771 forward_match_found_start_or_reached_end:
772 if (BE (match_first == right_lim, 0))
1b2c2628 773 {
bb677c95
UD		 774 ch = match_first >= length
775 ? 0 : (unsigned char) string[match_first];
776 if (!fastmap[t ? t[ch] : ch])
777 goto free_return;
1b2c2628 778 }
bb677c95
UD		 779 break;
780
781 case 4:
782 case 5:
783 /* Fastmap without multi-byte translation, match backwards. */
784 while (match_first >= left_lim)
1b2c2628 785 {
bb677c95
UD		 786 ch = match_first >= length
787 ? 0 : (unsigned char) string[match_first];
788 if (fastmap[t ? t[ch] : ch])
789 break;
790 --match_first;
791 }
792 if (match_first < left_lim)
793 goto free_return;
794 break;
1b2c2628 795
bb677c95
UD		 796 default:
797 /* In this case, we can't determine easily the current byte,
798 since it might be a component byte of a multibyte
799 character. Then we use the constructed buffer instead. */
800 for (;;)
801 {
802 /* If MATCH_FIRST is out of the valid range, reconstruct the
803 buffers. */
804 unsigned int offset = match_first - mctx.input.raw_mbs_idx;
805 if (BE (offset >= (unsigned int) mctx.input.valid_raw_len, 0))
1b2c2628 806 {
bb677c95
UD		 807 err = re_string_reconstruct (&mctx.input, match_first,
808 eflags);
809 if (BE (err != REG_NOERROR, 0))
810 goto free_return;
811
812 offset = match_first - mctx.input.raw_mbs_idx;
1b2c2628 813 }
bb677c95
UD		 814 /* If MATCH_FIRST is out of the buffer, leave it as '\0'.
815 Note that MATCH_FIRST must not be smaller than 0. */
816 ch = (match_first >= length
817 ? 0 : re_string_byte_at (&mctx.input, offset));
818 if (fastmap[ch])
1b2c2628 819 break;
bb677c95
UD		 820 match_first += incr;
821 if (match_first < left_lim || match_first > right_lim)
822 {
823 err = REG_NOMATCH;
824 goto free_return;
825 }
1b2c2628 826 }
bb677c95 827 break;
1b2c2628 828 }
612546c6 829
1b2c2628 830 /* Reconstruct the buffers so that the matcher can assume that
fe9434bb 831 the matching starts from the beginning of the buffer. */
56b168be 832 err = re_string_reconstruct (&mctx.input, match_first, eflags);
1b2c2628
UD		 833 if (BE (err != REG_NOERROR, 0))
834 goto free_return;
bb677c95 835
3b0bdc72 836#ifdef RE_ENABLE_I18N
bb677c95
UD		 837 /* Don't consider this char as a possible match start if it part,
838 yet isn't the head, of a multibyte character. */
839 if (!sb && !re_string_first_byte (&mctx.input, 0))
840 continue;
3b0bdc72 841#endif
bb677c95
UD		 842
843 /* It seems to be appropriate one, then use the matcher. */
844 /* We assume that the matching starts from 0. */
845 mctx.state_log_top = mctx.nbkref_ents = mctx.max_mb_elem_len = 0;
846 match_last = check_matching (&mctx, fl_longest_match,
847 range >= 0 ? &match_first : NULL);
848 if (match_last != -1)
1b2c2628 849 {
bb677c95 850 if (BE (match_last == -2, 0))
1b2c2628 851 {
bb677c95
UD		 852 err = REG_ESPACE;
853 goto free_return;
854 }
855 else
856 {
857 mctx.match_last = match_last;
858 if ((!preg->no_sub && nmatch > 1) || dfa->nbackref)
1b2c2628 859 {
bb677c95
UD		 860 re_dfastate_t *pstate = mctx.state_log[match_last];
861 mctx.last_node = check_halt_state_context (&mctx, pstate,
862 match_last);
1b2c2628 863 }
bb677c95
UD		 864 if ((!preg->no_sub && nmatch > 1 && dfa->has_plural_match)
865 || dfa->nbackref)
6291ee3c 866 {
bb677c95
UD		 867 err = prune_impossible_nodes (&mctx);
868 if (err == REG_NOERROR)
869 break;
870 if (BE (err != REG_NOMATCH, 0))
871 goto free_return;
872 match_last = -1;
6291ee3c 873 }
bb677c95
UD		 874 else
875 break; /* We found a match. */
1b2c2628
UD		 876 }
877 }
bb677c95
UD		 878
879 match_ctx_clean (&mctx);
3b0bdc72
UD		 880 }
881
bb677c95
UD		 882#ifdef DEBUG
883 assert (match_last != -1);
884 assert (err == REG_NOERROR);
885#endif
886
3b0bdc72 887 /* Set pmatch[] if we need. */
bb677c95 888 if (nmatch > 0)
3b0bdc72
UD		 889 {
890 int reg_idx;
891
892 /* Initialize registers. */
97fd3a30 893 for (reg_idx = 1; reg_idx < nmatch; ++reg_idx)
15a7d175 894 pmatch[reg_idx].rm_so = pmatch[reg_idx].rm_eo = -1;
3b0bdc72
UD		 895
896 /* Set the points where matching start/end. */
612546c6 897 pmatch[0].rm_so = 0;
6291ee3c 898 pmatch[0].rm_eo = mctx.match_last;
3b0bdc72
UD		 899
900 if (!preg->no_sub && nmatch > 1)
15a7d175 901 {
15a7d175
UD		 902 err = set_regs (preg, &mctx, nmatch, pmatch,
903 dfa->has_plural_match && dfa->nbackref > 0);
904 if (BE (err != REG_NOERROR, 0))
905 goto free_return;
906 }
612546c6
UD		 907
908 /* At last, add the offset to the each registers, since we slided
97fd3a30
UD		 909 the buffers so that we could assume that the matching starts
910 from 0. */
612546c6 911 for (reg_idx = 0; reg_idx < nmatch; ++reg_idx)
15a7d175
UD		 912 if (pmatch[reg_idx].rm_so != -1)
913 {
c0d5034e 914#ifdef RE_ENABLE_I18N
56b168be 915 if (BE (mctx.input.offsets_needed != 0, 0))
bb3f4825 916 {
01ed6ceb
UD		 917 pmatch[reg_idx].rm_so =
918 (pmatch[reg_idx].rm_so == mctx.input.valid_len
919 ? mctx.input.valid_raw_len
920 : mctx.input.offsets[pmatch[reg_idx].rm_so]);
921 pmatch[reg_idx].rm_eo =
922 (pmatch[reg_idx].rm_eo == mctx.input.valid_len
923 ? mctx.input.valid_raw_len
924 : mctx.input.offsets[pmatch[reg_idx].rm_eo]);
bb3f4825 925 }
c0d5034e 926#else
56b168be 927 assert (mctx.input.offsets_needed == 0);
c0d5034e 928#endif
15a7d175
UD		 929 pmatch[reg_idx].rm_so += match_first;
930 pmatch[reg_idx].rm_eo += match_first;
931 }
963d8d78
UD		 932 for (reg_idx = 0; reg_idx < extra_nmatch; ++reg_idx)
933 {
934 pmatch[nmatch + reg_idx].rm_so = -1;
935 pmatch[nmatch + reg_idx].rm_eo = -1;
936 }
c06a6956
UD		 937
938 if (dfa->subexp_map)
963d8d78 939 for (reg_idx = 0; reg_idx + 1 < nmatch; reg_idx++)
c06a6956
UD		 940 if (dfa->subexp_map[reg_idx] != reg_idx)
941 {
942 pmatch[reg_idx + 1].rm_so
943 = pmatch[dfa->subexp_map[reg_idx] + 1].rm_so;
944 pmatch[reg_idx + 1].rm_eo
945 = pmatch[dfa->subexp_map[reg_idx] + 1].rm_eo;
946 }
3b0bdc72 947 }
bb677c95 948
1b2c2628 949 free_return:
612546c6 950 re_free (mctx.state_log);
3b0bdc72
UD		 951 if (dfa->nbackref)
952 match_ctx_free (&mctx);
56b168be 953 re_string_destruct (&mctx.input);
1b2c2628 954 return err;
3b0bdc72
UD		 955}
956
6291ee3c 957static reg_errcode_t
e3a87852 958prune_impossible_nodes (mctx)
6291ee3c
UD		 959 re_match_context_t *mctx;
960{
76b864c8 961 const re_dfa_t *const dfa = mctx->dfa;
6291ee3c
UD		 962 int halt_node, match_last;
963 reg_errcode_t ret;
6291ee3c
UD		 964 re_dfastate_t **sifted_states;
965 re_dfastate_t **lim_states = NULL;
966 re_sift_context_t sctx;
967#ifdef DEBUG
968 assert (mctx->state_log != NULL);
969#endif
970 match_last = mctx->match_last;
971 halt_node = mctx->last_node;
972 sifted_states = re_malloc (re_dfastate_t *, match_last + 1);
973 if (BE (sifted_states == NULL, 0))
974 {
975 ret = REG_ESPACE;
976 goto free_return;
977 }
978 if (dfa->nbackref)
979 {
980 lim_states = re_malloc (re_dfastate_t *, match_last + 1);
981 if (BE (lim_states == NULL, 0))
982 {
983 ret = REG_ESPACE;
984 goto free_return;
985 }
986 while (1)
987 {
988 memset (lim_states, '\0',
989 sizeof (re_dfastate_t *) * (match_last + 1));
6291ee3c 990 sift_ctx_init (&sctx, sifted_states, lim_states, halt_node,
d2c38eb3 991 match_last);
e3a87852 992 ret = sift_states_backward (mctx, &sctx);
6291ee3c
UD		 993 re_node_set_free (&sctx.limits);
994 if (BE (ret != REG_NOERROR, 0))
995 goto free_return;
996 if (sifted_states[0] != NULL || lim_states[0] != NULL)
997 break;
998 do
999 {
1000 --match_last;
1001 if (match_last < 0)
1002 {
1003 ret = REG_NOMATCH;
1004 goto free_return;
1005 }
97fd3a30
UD		 1006 } while (mctx->state_log[match_last] == NULL
1007 || !mctx->state_log[match_last]->halt);
e3a87852 1008 halt_node = check_halt_state_context (mctx,
6291ee3c 1009 mctx->state_log[match_last],
e3a87852 1010 match_last);
6291ee3c
UD		 1011 }
1012 ret = merge_state_array (dfa, sifted_states, lim_states,
1013 match_last + 1);
1014 re_free (lim_states);
1015 lim_states = NULL;
1016 if (BE (ret != REG_NOERROR, 0))
1017 goto free_return;
1018 }
1019 else
1020 {
d2c38eb3 1021 sift_ctx_init (&sctx, sifted_states, lim_states, halt_node, match_last);
e3a87852 1022 ret = sift_states_backward (mctx, &sctx);
6291ee3c
UD		 1023 re_node_set_free (&sctx.limits);
1024 if (BE (ret != REG_NOERROR, 0))
1025 goto free_return;
1026 }
1027 re_free (mctx->state_log);
1028 mctx->state_log = sifted_states;
1029 sifted_states = NULL;
1030 mctx->last_node = halt_node;
1031 mctx->match_last = match_last;
1032 ret = REG_NOERROR;
1033 free_return:
1034 re_free (sifted_states);
1035 re_free (lim_states);
1036 return ret;
1037}
1038
a9388965 1039/* Acquire an initial state and return it.
3b0bdc72
UD		 1040 We must select appropriate initial state depending on the context,
1041 since initial states may have constraints like "\<", "^", etc.. */
1042
bb3f4825 1043static inline re_dfastate_t *
a334319f
UD		 1044acquire_init_state_context (err, mctx, idx)
1045 reg_errcode_t *err;
1046 const re_match_context_t *mctx;
1047 int idx;
3b0bdc72 1048{
76b864c8 1049 const re_dfa_t *const dfa = mctx->dfa;
3b0bdc72
UD		 1050 if (dfa->init_state->has_constraint)
1051 {
1052 unsigned int context;
56b168be 1053 context = re_string_context_at (&mctx->input, idx - 1, mctx->eflags);
3b0bdc72 1054 if (IS_WORD_CONTEXT (context))
15a7d175 1055 return dfa->init_state_word;
3b0bdc72 1056 else if (IS_ORDINARY_CONTEXT (context))
15a7d175 1057 return dfa->init_state;
3b0bdc72 1058 else if (IS_BEGBUF_CONTEXT (context) && IS_NEWLINE_CONTEXT (context))
15a7d175 1059 return dfa->init_state_begbuf;
3b0bdc72 1060 else if (IS_NEWLINE_CONTEXT (context))
15a7d175 1061 return dfa->init_state_nl;
3b0bdc72 1062 else if (IS_BEGBUF_CONTEXT (context))
15a7d175
UD		 1063 {
1064 /* It is relatively rare case, then calculate on demand. */
4c595adb
UD		 1065 return re_acquire_state_context (err, dfa,
1066 dfa->init_state->entrance_nodes,
1067 context);
15a7d175 1068 }
3b0bdc72 1069 else
15a7d175
UD		 1070 /* Must not happen? */
1071 return dfa->init_state;
3b0bdc72
UD		 1072 }
1073 else
1074 return dfa->init_state;
1075}
1076
1077/* Check whether the regular expression match input string INPUT or not,
a9388965
UD		 1078 and return the index where the matching end, return -1 if not match,
1079 or return -2 in case of an error.
612546c6 1080 FL_LONGEST_MATCH means we want the POSIX longest matching.
15bad1a5
UD		 1081 If P_MATCH_FIRST is not NULL, and the match fails, it is set to the
1082 next place where we may want to try matching.
612546c6
UD		 1083 Note that the matcher assume that the maching starts from the current
1084 index of the buffer. */
3b0bdc72
UD		 1085
1086static int
a334319f 1087check_matching (mctx, fl_longest_match, p_match_first)
76b864c8
UD		 1088 re_match_context_t *mctx;
1089 int fl_longest_match;
1090 int *p_match_first;
3b0bdc72 1091{
76b864c8 1092 const re_dfa_t *const dfa = mctx->dfa;
a9388965 1093 reg_errcode_t err;
612546c6
UD		 1094 int match = 0;
1095 int match_last = -1;
56b168be 1096 int cur_str_idx = re_string_cur_idx (&mctx->input);
3b0bdc72 1097 re_dfastate_t *cur_state;
4c595adb
UD		 1098 int at_init_state = p_match_first != NULL;
1099 int next_start_idx = cur_str_idx;
3b0bdc72 1100
4c595adb 1101 err = REG_NOERROR;
e3a87852 1102 cur_state = acquire_init_state_context (&err, mctx, cur_str_idx);
4c595adb 1103 /* An initial state must not be NULL (invalid). */
bc15410e 1104 if (BE (cur_state == NULL, 0))
4c595adb
UD		 1105 {
1106 assert (err == REG_ESPACE);
1107 return -2;
1108 }
0742e48e 1109
4c595adb 1110 if (mctx->state_log != NULL)
6291ee3c 1111 {
4c595adb 1112 mctx->state_log[cur_str_idx] = cur_state;
6291ee3c 1113
4c595adb
UD		 1114 /* Check OP_OPEN_SUBEXP in the initial state in case that we use them
1115 later. E.g. Processing back references. */
1116 if (BE (dfa->nbackref, 0))
bb3f4825 1117 {
4c595adb
UD		 1118 at_init_state = 0;
1119 err = check_subexp_matching_top (mctx, &cur_state->nodes, 0);
bb3f4825
UD		 1120 if (BE (err != REG_NOERROR, 0))
1121 return err;
4c595adb
UD		 1122
1123 if (cur_state->has_backref)
1124 {
1125 err = transit_state_bkref (mctx, &cur_state->nodes);
1126 if (BE (err != REG_NOERROR, 0))
1127 return err;
1128 }
bb3f4825 1129 }
0742e48e
UD		 1130 }
1131
3b0bdc72 1132 /* If the RE accepts NULL string. */
bb3f4825 1133 if (BE (cur_state->halt, 0))
3b0bdc72
UD		 1134 {
1135 if (!cur_state->has_constraint
e3a87852 1136 || check_halt_state_context (mctx, cur_state, cur_str_idx))
15a7d175
UD		 1137 {
1138 if (!fl_longest_match)
1139 return cur_str_idx;
1140 else
1141 {
1142 match_last = cur_str_idx;
1143 match = 1;
1144 }
1145 }
3b0bdc72
UD		 1146 }
1147
56b168be 1148 while (!re_string_eoi (&mctx->input))
3b0bdc72 1149 {
15bad1a5 1150 re_dfastate_t *old_state = cur_state;
bb677c95
UD		 1151 int next_char_idx = re_string_cur_idx (&mctx->input) + 1;
1152
1153 if (BE (next_char_idx >= mctx->input.bufs_len, 0)
1154 || (BE (next_char_idx >= mctx->input.valid_len, 0)
1155 && mctx->input.valid_len < mctx->input.len))
1156 {
1157 err = extend_buffers (mctx);
1158 if (BE (err != REG_NOERROR, 0))
1159 {
1160 assert (err == REG_ESPACE);
1161 return -2;
1162 }
1163 }
1164
e3a87852 1165 cur_state = transit_state (&err, mctx, cur_state);
4c595adb
UD		 1166 if (mctx->state_log != NULL)
1167 cur_state = merge_state_with_log (&err, mctx, cur_state);
15bad1a5 1168
4c595adb 1169 if (cur_state == NULL)
15a7d175 1170 {
4c595adb
UD		 1171 /* Reached the invalid state or an error. Try to recover a valid
1172 state using the state log, if available and if we have not
1173 already found a valid (even if not the longest) match. */
15a7d175
UD		 1174 if (BE (err != REG_NOERROR, 0))
1175 return -2;
4c595adb
UD		 1176
1177 if (mctx->state_log == NULL
1178 || (match && !fl_longest_match)
1179 || (cur_state = find_recover_state (&err, mctx)) == NULL)
15a7d175 1180 break;
4c595adb
UD		 1181 }
1182
bb677c95 1183 if (BE (at_init_state, 0))
4c595adb
UD		 1184 {
1185 if (old_state == cur_state)
bb677c95 1186 next_start_idx = next_char_idx;
c13c99fa 1187 else
4c595adb 1188 at_init_state = 0;
15a7d175 1189 }
3b0bdc72 1190
4c595adb 1191 if (cur_state->halt)
15a7d175 1192 {
4c595adb 1193 /* Reached a halt state.
15a7d175
UD		 1194 Check the halt state can satisfy the current context. */
1195 if (!cur_state->has_constraint
e3a87852 1196 || check_halt_state_context (mctx, cur_state,
56b168be 1197 re_string_cur_idx (&mctx->input)))
15a7d175
UD		 1198 {
1199 /* We found an appropriate halt state. */
56b168be 1200 match_last = re_string_cur_idx (&mctx->input);
15a7d175 1201 match = 1;
bb677c95
UD		 1202
1203 /* We found a match, do not modify match_first below. */
1204 p_match_first = NULL;
15a7d175
UD		 1205 if (!fl_longest_match)
1206 break;
1207 }
1208 }
bb677c95 1209 }
15bad1a5 1210
bb677c95 1211 if (p_match_first)
4c595adb 1212 *p_match_first += next_start_idx;
15bad1a5 1213
3b0bdc72
UD		 1214 return match_last;
1215}
1216
1217/* Check NODE match the current context. */
1218
a334319f
UD		 1219static int check_halt_node_context (dfa, node, context)
1220 const re_dfa_t *dfa;
1221 int node;
1222 unsigned int context;
3b0bdc72 1223{
3b0bdc72 1224 re_token_type_t type = dfa->nodes[node].type;
485d775d
UD		 1225 unsigned int constraint = dfa->nodes[node].constraint;
1226 if (type != END_OF_RE)
3b0bdc72 1227 return 0;
485d775d
UD		 1228 if (!constraint)
1229 return 1;
1230 if (NOT_SATISFY_NEXT_CONSTRAINT (constraint, context))
3b0bdc72
UD		 1231 return 0;
1232 return 1;
1233}
1234
1235/* Check the halt state STATE match the current context.
1236 Return 0 if not match, if the node, STATE has, is a halt node and
1237 match the context, return the node. */
1238
1239static int
a334319f
UD		 1240check_halt_state_context (mctx, state, idx)
1241 const re_match_context_t *mctx;
1242 const re_dfastate_t *state;
1243 int idx;
3b0bdc72 1244{
3b0bdc72
UD		 1245 int i;
1246 unsigned int context;
1247#ifdef DEBUG
1248 assert (state->halt);
1249#endif
56b168be 1250 context = re_string_context_at (&mctx->input, idx, mctx->eflags);
3b0bdc72 1251 for (i = 0; i < state->nodes.nelem; ++i)
e3a87852 1252 if (check_halt_node_context (mctx->dfa, state->nodes.elems[i], context))
3b0bdc72
UD		 1253 return state->nodes.elems[i];
1254 return 0;
1255}
1256
a9388965
UD		 1257/* Compute the next node to which "NFA" transit from NODE("NFA" is a NFA
1258 corresponding to the DFA).
1259 Return the destination node, and update EPS_VIA_NODES, return -1 in case
1260 of errors. */
3b0bdc72
UD		 1261
1262static int
a334319f
UD		 1263proceed_next_node (mctx, nregs, regs, pidx, node, eps_via_nodes, fs)
1264 const re_match_context_t *mctx;
1265 regmatch_t *regs;
1266 int nregs, *pidx, node;
1267 re_node_set *eps_via_nodes;
1268 struct re_fail_stack_t *fs;
3b0bdc72 1269{
76b864c8 1270 const re_dfa_t *const dfa = mctx->dfa;
2d87db5b 1271 int i, err;
3b0bdc72
UD		 1272 if (IS_EPSILON_NODE (dfa->nodes[node].type))
1273 {
485d775d 1274 re_node_set *cur_nodes = &mctx->state_log[*pidx]->nodes;
5cf1ec52
UD		 1275 re_node_set *edests = &dfa->edests[node];
1276 int dest_node;
a9388965 1277 err = re_node_set_insert (eps_via_nodes, node);
bc15410e 1278 if (BE (err < 0, 0))
44777771 1279 return -2;
5cf1ec52
UD		 1280 /* Pick up a valid destination, or return -1 if none is found. */
1281 for (dest_node = -1, i = 0; i < edests->nelem; ++i)
15a7d175 1282 {
5cf1ec52 1283 int candidate = edests->elems[i];
15a7d175
UD		 1284 if (!re_node_set_contains (cur_nodes, candidate))
1285 continue;
5cf1ec52
UD		 1286 if (dest_node == -1)
1287 dest_node = candidate;
1288
1289 else
1290 {
1291 /* In order to avoid infinite loop like "(a*)*", return the second
1292 epsilon-transition if the first was already considered. */
1293 if (re_node_set_contains (eps_via_nodes, dest_node))
1294 return candidate;
1295
1296 /* Otherwise, push the second epsilon-transition on the fail stack. */
1297 else if (fs != NULL
1298 && push_fail_stack (fs, *pidx, candidate, nregs, regs,
1299 eps_via_nodes))
1300 return -2;
1301
1302 /* We know we are going to exit. */
1303 break;
1304 }
1305 }
1306 return dest_node;
3b0bdc72
UD		 1307 }
1308 else
1309 {
485d775d 1310 int naccepted = 0;
3b0bdc72 1311 re_token_type_t type = dfa->nodes[node].type;
3b0bdc72 1312
434d3784 1313#ifdef RE_ENABLE_I18N
02f3550c 1314 if (dfa->nodes[node].accept_mb)
56b168be 1315 naccepted = check_node_accept_bytes (dfa, node, &mctx->input, *pidx);
434d3784
UD		 1316 else
1317#endif /* RE_ENABLE_I18N */
1318 if (type == OP_BACK_REF)
15a7d175 1319 {
d8f73de8 1320 int subexp_idx = dfa->nodes[node].opr.idx + 1;
15a7d175
UD		 1321 naccepted = regs[subexp_idx].rm_eo - regs[subexp_idx].rm_so;
1322 if (fs != NULL)
1323 {
1324 if (regs[subexp_idx].rm_so == -1 || regs[subexp_idx].rm_eo == -1)
1325 return -1;
1326 else if (naccepted)
1327 {
56b168be 1328 char *buf = (char *) re_string_get_buffer (&mctx->input);
6291ee3c
UD		 1329 if (memcmp (buf + regs[subexp_idx].rm_so, buf + *pidx,
1330 naccepted) != 0)
15a7d175
UD		 1331 return -1;
1332 }
1333 }
1334
1335 if (naccepted == 0)
1336 {
2d87db5b 1337 int dest_node;
15a7d175
UD		 1338 err = re_node_set_insert (eps_via_nodes, node);
1339 if (BE (err < 0, 0))
1340 return -2;
1341 dest_node = dfa->edests[node].elems[0];
1342 if (re_node_set_contains (&mctx->state_log[*pidx]->nodes,
1343 dest_node))
1344 return dest_node;
1345 }
1346 }
3b0bdc72
UD		 1347
1348 if (naccepted != 0
e3a87852 1349 || check_node_accept (mctx, dfa->nodes + node, *pidx))
15a7d175 1350 {
2d87db5b 1351 int dest_node = dfa->nexts[node];
15a7d175
UD		 1352 *pidx = (naccepted == 0) ? *pidx + 1 : *pidx + naccepted;
1353 if (fs && (*pidx > mctx->match_last || mctx->state_log[*pidx] == NULL
1354 || !re_node_set_contains (&mctx->state_log[*pidx]->nodes,
1355 dest_node)))
1356 return -1;
1357 re_node_set_empty (eps_via_nodes);
1358 return dest_node;
1359 }
3b0bdc72 1360 }
a3022b82
UD		 1361 return -1;
1362}
1363
1364static reg_errcode_t
a334319f
UD		 1365push_fail_stack (fs, str_idx, dest_node, nregs, regs, eps_via_nodes)
1366 struct re_fail_stack_t *fs;
1367 int str_idx, dest_node, nregs;
1368 regmatch_t *regs;
1369 re_node_set *eps_via_nodes;
a3022b82
UD		 1370{
1371 reg_errcode_t err;
1372 int num = fs->num++;
1373 if (fs->num == fs->alloc)
1374 {
1b2c2628 1375 struct re_fail_stack_ent_t *new_array;
1b2c2628 1376 new_array = realloc (fs->stack, (sizeof (struct re_fail_stack_ent_t)
44777771 1377 * fs->alloc * 2));
1b2c2628 1378 if (new_array == NULL)
15a7d175 1379 return REG_ESPACE;
44777771 1380 fs->alloc *= 2;
1b2c2628 1381 fs->stack = new_array;
a3022b82
UD		 1382 }
1383 fs->stack[num].idx = str_idx;
5cf1ec52 1384 fs->stack[num].node = dest_node;
a3022b82 1385 fs->stack[num].regs = re_malloc (regmatch_t, nregs);
5a299c96
UD		 1386 if (fs->stack[num].regs == NULL)
1387 return REG_ESPACE;
a3022b82
UD		 1388 memcpy (fs->stack[num].regs, regs, sizeof (regmatch_t) * nregs);
1389 err = re_node_set_init_copy (&fs->stack[num].eps_via_nodes, eps_via_nodes);
1390 return err;
1391}
1b2c2628 1392
a3022b82 1393static int
a334319f
UD		 1394pop_fail_stack (fs, pidx, nregs, regs, eps_via_nodes)
1395 struct re_fail_stack_t *fs;
1396 int *pidx, nregs;
1397 regmatch_t *regs;
1398 re_node_set *eps_via_nodes;
a3022b82
UD		 1399{
1400 int num = --fs->num;
1401 assert (num >= 0);
44777771 1402 *pidx = fs->stack[num].idx;
a3022b82
UD		 1403 memcpy (regs, fs->stack[num].regs, sizeof (regmatch_t) * nregs);
1404 re_node_set_free (eps_via_nodes);
485d775d 1405 re_free (fs->stack[num].regs);
a3022b82
UD		 1406 *eps_via_nodes = fs->stack[num].eps_via_nodes;
1407 return fs->stack[num].node;
3b0bdc72
UD		 1408}
1409
1410/* Set the positions where the subexpressions are starts/ends to registers
1411 PMATCH.
1412 Note: We assume that pmatch[0] is already set, and
97fd3a30 1413 pmatch[i].rm_so == pmatch[i].rm_eo == -1 for 0 < i < nmatch. */
3b0bdc72 1414
a9388965 1415static reg_errcode_t
a334319f
UD		 1416set_regs (preg, mctx, nmatch, pmatch, fl_backtrack)
1417 const regex_t *preg;
1418 const re_match_context_t *mctx;
1419 size_t nmatch;
1420 regmatch_t *pmatch;
1421 int fl_backtrack;
3b0bdc72 1422{
76b864c8 1423 const re_dfa_t *dfa = (const re_dfa_t *) preg->buffer;
963d8d78 1424 int idx, cur_node;
3b0bdc72 1425 re_node_set eps_via_nodes;
a3022b82 1426 struct re_fail_stack_t *fs;
6b6557e8
UD		 1427 struct re_fail_stack_t fs_body = { 0, 2, NULL };
1428 regmatch_t *prev_idx_match;
2d87db5b 1429 int prev_idx_match_malloced = 0;
6b6557e8 1430
3b0bdc72
UD		 1431#ifdef DEBUG
1432 assert (nmatch > 1);
612546c6 1433 assert (mctx->state_log != NULL);
3b0bdc72 1434#endif
a3022b82
UD		 1435 if (fl_backtrack)
1436 {
1437 fs = &fs_body;
1438 fs->stack = re_malloc (struct re_fail_stack_ent_t, fs->alloc);
6b6557e8
UD		 1439 if (fs->stack == NULL)
1440 return REG_ESPACE;
a3022b82
UD		 1441 }
1442 else
1443 fs = NULL;
6b6557e8 1444
3b0bdc72 1445 cur_node = dfa->init_node;
3b0bdc72 1446 re_node_set_init_empty (&eps_via_nodes);
6b6557e8 1447
2d87db5b
UD		 1448 if (__libc_use_alloca (nmatch * sizeof (regmatch_t)))
1449 prev_idx_match = (regmatch_t *) alloca (nmatch * sizeof (regmatch_t));
1450 else
1451 {
1452 prev_idx_match = re_malloc (regmatch_t, nmatch);
1453 if (prev_idx_match == NULL)
1454 {
1455 free_fail_stack_return (fs);
1456 return REG_ESPACE;
1457 }
1458 prev_idx_match_malloced = 1;
1459 }
963d8d78 1460 memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
6b6557e8 1461
3b0bdc72
UD		 1462 for (idx = pmatch[0].rm_so; idx <= pmatch[0].rm_eo ;)
1463 {
963d8d78 1464 update_regs (dfa, pmatch, prev_idx_match, cur_node, idx, nmatch);
6b6557e8 1465
a3022b82 1466 if (idx == pmatch[0].rm_eo && cur_node == mctx->last_node)
15a7d175
UD		 1467 {
1468 int reg_idx;
1469 if (fs)
1470 {
1471 for (reg_idx = 0; reg_idx < nmatch; ++reg_idx)
1472 if (pmatch[reg_idx].rm_so > -1 && pmatch[reg_idx].rm_eo == -1)
1473 break;
1474 if (reg_idx == nmatch)
1475 {
1476 re_node_set_free (&eps_via_nodes);
2d87db5b
UD		 1477 if (prev_idx_match_malloced)
1478 re_free (prev_idx_match);
15a7d175
UD		 1479 return free_fail_stack_return (fs);
1480 }
1481 cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
1482 &eps_via_nodes);
1483 }
1484 else
1485 {
1486 re_node_set_free (&eps_via_nodes);
2d87db5b
UD		 1487 if (prev_idx_match_malloced)
1488 re_free (prev_idx_match);
15a7d175
UD		 1489 return REG_NOERROR;
1490 }
1491 }
3b0bdc72
UD		 1492
1493 /* Proceed to next node. */
e3a87852 1494 cur_node = proceed_next_node (mctx, nmatch, pmatch, &idx, cur_node,
15a7d175 1495 &eps_via_nodes, fs);
a3022b82 1496
bc15410e 1497 if (BE (cur_node < 0, 0))
15a7d175 1498 {
44777771
UD		 1499 if (BE (cur_node == -2, 0))
1500 {
1501 re_node_set_free (&eps_via_nodes);
2d87db5b
UD		 1502 if (prev_idx_match_malloced)
1503 re_free (prev_idx_match);
44777771
UD		 1504 free_fail_stack_return (fs);
1505 return REG_ESPACE;
1506 }
15a7d175
UD		 1507 if (fs)
1508 cur_node = pop_fail_stack (fs, &idx, nmatch, pmatch,
1509 &eps_via_nodes);
1510 else
1511 {
1512 re_node_set_free (&eps_via_nodes);
2d87db5b
UD		 1513 if (prev_idx_match_malloced)
1514 re_free (prev_idx_match);
15a7d175
UD		 1515 return REG_NOMATCH;
1516 }
1517 }
3b0bdc72
UD		 1518 }
1519 re_node_set_free (&eps_via_nodes);
2d87db5b
UD		 1520 if (prev_idx_match_malloced)
1521 re_free (prev_idx_match);
485d775d
UD		 1522 return free_fail_stack_return (fs);
1523}
1524
1525static reg_errcode_t
a334319f
UD		 1526free_fail_stack_return (fs)
1527 struct re_fail_stack_t *fs;
485d775d
UD		 1528{
1529 if (fs)
1530 {
1531 int fs_idx;
1532 for (fs_idx = 0; fs_idx < fs->num; ++fs_idx)
15a7d175
UD		 1533 {
1534 re_node_set_free (&fs->stack[fs_idx].eps_via_nodes);
1535 re_free (fs->stack[fs_idx].regs);
1536 }
485d775d
UD		 1537 re_free (fs->stack);
1538 }
a9388965 1539 return REG_NOERROR;
3b0bdc72
UD		 1540}
1541
81c64d40 1542static void
a334319f 1543update_regs (dfa, pmatch, prev_idx_match, cur_node, cur_idx, nmatch)
76b864c8 1544 const re_dfa_t *dfa;
a334319f
UD		 1545 regmatch_t *pmatch, *prev_idx_match;
1546 int cur_node, cur_idx, nmatch;
81c64d40
UD		 1547{
1548 int type = dfa->nodes[cur_node].type;
81c64d40
UD		 1549 if (type == OP_OPEN_SUBEXP)
1550 {
6b6557e8
UD		 1551 int reg_num = dfa->nodes[cur_node].opr.idx + 1;
1552
81c64d40 1553 /* We are at the first node of this sub expression. */
6b6557e8
UD		 1554 if (reg_num < nmatch)
1555 {
1556 pmatch[reg_num].rm_so = cur_idx;
1557 pmatch[reg_num].rm_eo = -1;
1558 }
81c64d40
UD		 1559 }
1560 else if (type == OP_CLOSE_SUBEXP)
6b6557e8
UD		 1561 {
1562 int reg_num = dfa->nodes[cur_node].opr.idx + 1;
1563 if (reg_num < nmatch)
1564 {
1565 /* We are at the last node of this sub expression. */
1566 if (pmatch[reg_num].rm_so < cur_idx)
1567 {
1568 pmatch[reg_num].rm_eo = cur_idx;
1569 /* This is a non-empty match or we are not inside an optional
1570 subexpression. Accept this right away. */
1571 memcpy (prev_idx_match, pmatch, sizeof (regmatch_t) * nmatch);
1572 }
1573 else
1574 {
1575 if (dfa->nodes[cur_node].opt_subexp
1576 && prev_idx_match[reg_num].rm_so != -1)
1577 /* We transited through an empty match for an optional
1578 subexpression, like (a?)*, and this is not the subexp's
1579 first match. Copy back the old content of the registers
1580 so that matches of an inner subexpression are undone as
1581 well, like in ((a?))*. */
1582 memcpy (pmatch, prev_idx_match, sizeof (regmatch_t) * nmatch);
1583 else
1584 /* We completed a subexpression, but it may be part of
1585 an optional one, so do not update PREV_IDX_MATCH. */
1586 pmatch[reg_num].rm_eo = cur_idx;
1587 }
1588 }
1589 }
0742e48e 1590}
81c64d40 1591
0742e48e 1592/* This function checks the STATE_LOG from the SCTX->last_str_idx to 0
612546c6
UD		 1593 and sift the nodes in each states according to the following rules.
1594 Updated state_log will be wrote to STATE_LOG.
3b0bdc72
UD		 1595
1596 Rules: We throw away the Node `a' in the STATE_LOG[STR_IDX] if...
1597 1. When STR_IDX == MATCH_LAST(the last index in the state_log):
15a7d175
UD		 1598 If `a' isn't the LAST_NODE and `a' can't epsilon transit to
1599 the LAST_NODE, we throw away the node `a'.
612546c6 1600 2. When 0 <= STR_IDX < MATCH_LAST and `a' accepts
15a7d175
UD		 1601 string `s' and transit to `b':
1602 i. If 'b' isn't in the STATE_LOG[STR_IDX+strlen('s')], we throw
1603 away the node `a'.
1604 ii. If 'b' is in the STATE_LOG[STR_IDX+strlen('s')] but 'b' is
bb3f4825 1605 thrown away, we throw away the node `a'.
d0b96fc4 1606 3. When 0 <= STR_IDX < MATCH_LAST and 'a' epsilon transit to 'b':
15a7d175
UD		 1607 i. If 'b' isn't in the STATE_LOG[STR_IDX], we throw away the
1608 node `a'.
bb3f4825 1609 ii. If 'b' is in the STATE_LOG[STR_IDX] but 'b' is thrown away,
15a7d175 1610 we throw away the node `a'. */
3b0bdc72
UD		 1611
1612#define STATE_NODE_CONTAINS(state,node) \
1613 ((state) != NULL && re_node_set_contains (&(state)->nodes, node))
1614
a9388965 1615static reg_errcode_t
a334319f 1616sift_states_backward (mctx, sctx)
76b864c8 1617 const re_match_context_t *mctx;
a334319f 1618 re_sift_context_t *sctx;
3b0bdc72 1619{
a9388965 1620 reg_errcode_t err;
0742e48e
UD		 1621 int null_cnt = 0;
1622 int str_idx = sctx->last_str_idx;
1623 re_node_set cur_dest;
3b0bdc72
UD		 1624
1625#ifdef DEBUG
612546c6 1626 assert (mctx->state_log != NULL && mctx->state_log[str_idx] != NULL);
3b0bdc72 1627#endif
3b0bdc72
UD		 1628
1629 /* Build sifted state_log[str_idx]. It has the nodes which can epsilon
1630 transit to the last_node and the last_node itself. */
0742e48e 1631 err = re_node_set_init_1 (&cur_dest, sctx->last_node);
bc15410e 1632 if (BE (err != REG_NOERROR, 0))
a9388965 1633 return err;
e3a87852 1634 err = update_cur_sifted_state (mctx, sctx, str_idx, &cur_dest);
0742e48e 1635 if (BE (err != REG_NOERROR, 0))
1b2c2628 1636 goto free_return;
3b0bdc72
UD		 1637
1638 /* Then check each states in the state_log. */
612546c6 1639 while (str_idx > 0)
3b0bdc72 1640 {
3b0bdc72 1641 /* Update counters. */
0742e48e
UD		 1642 null_cnt = (sctx->sifted_states[str_idx] == NULL) ? null_cnt + 1 : 0;
1643 if (null_cnt > mctx->max_mb_elem_len)
15a7d175
UD		 1644 {
1645 memset (sctx->sifted_states, '\0',
1646 sizeof (re_dfastate_t *) * str_idx);
1647 re_node_set_free (&cur_dest);
1648 return REG_NOERROR;
1649 }
0742e48e 1650 re_node_set_empty (&cur_dest);
3b0bdc72 1651 --str_idx;
15a7d175 1652
e40a38b3
UD		 1653 if (mctx->state_log[str_idx])
1654 {
1655 err = build_sifted_states (mctx, sctx, str_idx, &cur_dest);
1656 if (BE (err != REG_NOERROR, 0))
1657 goto free_return;
15a7d175 1658 }
3b0bdc72 1659
0742e48e 1660 /* Add all the nodes which satisfy the following conditions:
15a7d175
UD		 1661 - It can epsilon transit to a node in CUR_DEST.
1662 - It is in CUR_SRC.
1663 And update state_log. */
e3a87852 1664 err = update_cur_sifted_state (mctx, sctx, str_idx, &cur_dest);
0742e48e 1665 if (BE (err != REG_NOERROR, 0))
15a7d175 1666 goto free_return;
3b0bdc72 1667 }
1b2c2628
UD		 1668 err = REG_NOERROR;
1669 free_return:
0742e48e 1670 re_node_set_free (&cur_dest);
1b2c2628 1671 return err;
3b0bdc72
UD		 1672}
1673
e40a38b3 1674static reg_errcode_t
a334319f 1675build_sifted_states (mctx, sctx, str_idx, cur_dest)
76b864c8 1676 const re_match_context_t *mctx;
a334319f
UD		 1677 re_sift_context_t *sctx;
1678 int str_idx;
1679 re_node_set *cur_dest;
e40a38b3 1680{
76b864c8
UD		 1681 const re_dfa_t *const dfa = mctx->dfa;
1682 const re_node_set *cur_src = &mctx->state_log[str_idx]->non_eps_nodes;
e40a38b3
UD		 1683 int i;
1684
1685 /* Then build the next sifted state.
1686 We build the next sifted state on `cur_dest', and update
1687 `sifted_states[str_idx]' with `cur_dest'.
1688 Note:
1689 `cur_dest' is the sifted state from `state_log[str_idx + 1]'.
5cf1ec52
UD		 1690 `cur_src' points the node_set of the old `state_log[str_idx]'
1691 (with the epsilon nodes pre-filtered out). */
e40a38b3
UD		 1692 for (i = 0; i < cur_src->nelem; i++)
1693 {
1694 int prev_node = cur_src->elems[i];
1695 int naccepted = 0;
e40a38b3
UD		 1696 int ret;
1697
a334319f 1698#ifdef DEBUG
02f3550c 1699 re_token_type_t type = dfa->nodes[prev_node].type;
5cf1ec52
UD		 1700 assert (!IS_EPSILON_NODE (type));
1701#endif
e40a38b3
UD		 1702#ifdef RE_ENABLE_I18N
1703 /* If the node may accept `multi byte'. */
02f3550c 1704 if (dfa->nodes[prev_node].accept_mb)
e40a38b3
UD		 1705 naccepted = sift_states_iter_mb (mctx, sctx, prev_node,
1706 str_idx, sctx->last_str_idx);
1707#endif /* RE_ENABLE_I18N */
1708
1709 /* We don't check backreferences here.
1710 See update_cur_sifted_state(). */
1711 if (!naccepted
1712 && check_node_accept (mctx, dfa->nodes + prev_node, str_idx)
1713 && STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + 1],
1714 dfa->nexts[prev_node]))
1715 naccepted = 1;
1716
1717 if (naccepted == 0)
1718 continue;
1719
1720 if (sctx->limits.nelem)
1721 {
1722 int to_idx = str_idx + naccepted;
1723 if (check_dst_limits (mctx, &sctx->limits,
1724 dfa->nexts[prev_node], to_idx,
1725 prev_node, str_idx))
1726 continue;
1727 }
1728 ret = re_node_set_insert (cur_dest, prev_node);
1729 if (BE (ret == -1, 0))
1730 return REG_ESPACE;
1731 }
1732
1733 return REG_NOERROR;
1734}
1735
3b0bdc72
UD		 1736/* Helper functions. */
1737
25337753 1738static reg_errcode_t
a334319f
UD		 1739clean_state_log_if_needed (mctx, next_state_log_idx)
1740 re_match_context_t *mctx;
1741 int next_state_log_idx;
3b0bdc72
UD		 1742{
1743 int top = mctx->state_log_top;
612546c6 1744
56b168be
UD		 1745 if (next_state_log_idx >= mctx->input.bufs_len
1746 || (next_state_log_idx >= mctx->input.valid_len
1747 && mctx->input.valid_len < mctx->input.len))
612546c6
UD		 1748 {
1749 reg_errcode_t err;
1750 err = extend_buffers (mctx);
1751 if (BE (err != REG_NOERROR, 0))
15a7d175 1752 return err;
612546c6
UD		 1753 }
1754
3b0bdc72
UD		 1755 if (top < next_state_log_idx)
1756 {
612546c6 1757 memset (mctx->state_log + top + 1, '\0',
15a7d175 1758 sizeof (re_dfastate_t *) * (next_state_log_idx - top));
3b0bdc72
UD		 1759 mctx->state_log_top = next_state_log_idx;
1760 }
612546c6 1761 return REG_NOERROR;
3b0bdc72
UD		 1762}
1763
1b2c2628 1764static reg_errcode_t
a334319f 1765merge_state_array (dfa, dst, src, num)
76b864c8 1766 const re_dfa_t *dfa;
a334319f
UD		 1767 re_dfastate_t **dst;
1768 re_dfastate_t **src;
1769 int num;
3b0bdc72 1770{
0742e48e
UD		 1771 int st_idx;
1772 reg_errcode_t err;
1773 for (st_idx = 0; st_idx < num; ++st_idx)
1774 {
1775 if (dst[st_idx] == NULL)
15a7d175 1776 dst[st_idx] = src[st_idx];
0742e48e 1777 else if (src[st_idx] != NULL)
15a7d175
UD		 1778 {
1779 re_node_set merged_set;
1780 err = re_node_set_init_union (&merged_set, &dst[st_idx]->nodes,
1781 &src[st_idx]->nodes);
1782 if (BE (err != REG_NOERROR, 0))
1783 return err;
1784 dst[st_idx] = re_acquire_state (&err, dfa, &merged_set);
1785 re_node_set_free (&merged_set);
1786 if (BE (err != REG_NOERROR, 0))
1787 return err;
1788 }
0742e48e
UD		 1789 }
1790 return REG_NOERROR;
3b0bdc72
UD		 1791}
1792
0742e48e 1793static reg_errcode_t
a334319f 1794update_cur_sifted_state (mctx, sctx, str_idx, dest_nodes)
76b864c8 1795 const re_match_context_t *mctx;
a334319f
UD		 1796 re_sift_context_t *sctx;
1797 int str_idx;
1798 re_node_set *dest_nodes;
3b0bdc72 1799{
76b864c8 1800 const re_dfa_t *const dfa = mctx->dfa;
c0c9615c 1801 reg_errcode_t err = REG_NOERROR;
0742e48e 1802 const re_node_set *candidates;
e40a38b3 1803 candidates = ((mctx->state_log[str_idx] == NULL) ? NULL
15a7d175 1804 : &mctx->state_log[str_idx]->nodes);
0742e48e 1805
e40a38b3
UD		 1806 if (dest_nodes->nelem == 0)
1807 sctx->sifted_states[str_idx] = NULL;
1808 else
485d775d 1809 {
e40a38b3
UD		 1810 if (candidates)
1811 {
1812 /* At first, add the nodes which can epsilon transit to a node in
1813 DEST_NODE. */
1814 err = add_epsilon_src_nodes (dfa, dest_nodes, candidates);
1815 if (BE (err != REG_NOERROR, 0))
1816 return err;
0742e48e 1817
e40a38b3
UD		 1818 /* Then, check the limitations in the current sift_context. */
1819 if (sctx->limits.nelem)
1820 {
1821 err = check_subexp_limits (dfa, dest_nodes, candidates, &sctx->limits,
1822 mctx->bkref_ents, str_idx);
1823 if (BE (err != REG_NOERROR, 0))
1824 return err;
1825 }
1826 }
1827
1828 sctx->sifted_states[str_idx] = re_acquire_state (&err, dfa, dest_nodes);
0742e48e 1829 if (BE (err != REG_NOERROR, 0))
15a7d175 1830 return err;
0742e48e
UD		 1831 }
1832
e40a38b3 1833 if (candidates && mctx->state_log[str_idx]->has_backref)
0742e48e 1834 {
d2c38eb3 1835 err = sift_states_bkref (mctx, sctx, str_idx, candidates);
0742e48e 1836 if (BE (err != REG_NOERROR, 0))
15a7d175 1837 return err;
0742e48e
UD		 1838 }
1839 return REG_NOERROR;
3b0bdc72
UD		 1840}
1841
a9388965 1842static reg_errcode_t
a334319f 1843add_epsilon_src_nodes (dfa, dest_nodes, candidates)
76b864c8 1844 const re_dfa_t *dfa;
a334319f
UD		 1845 re_node_set *dest_nodes;
1846 const re_node_set *candidates;
3b0bdc72 1847{
5cf1ec52
UD		 1848 reg_errcode_t err = REG_NOERROR;
1849 int i;
0742e48e 1850
5cf1ec52 1851 re_dfastate_t *state = re_acquire_state (&err, dfa, dest_nodes);
0742e48e
UD		 1852 if (BE (err != REG_NOERROR, 0))
1853 return err;
5cf1ec52
UD		 1854
1855 if (!state->inveclosure.alloc)
3b0bdc72 1856 {
5cf1ec52 1857 err = re_node_set_alloc (&state->inveclosure, dest_nodes->nelem);
0742e48e 1858 if (BE (err != REG_NOERROR, 0))
5cf1ec52
UD		 1859 return REG_ESPACE;
1860 for (i = 0; i < dest_nodes->nelem; i++)
1861 re_node_set_merge (&state->inveclosure,
1862 dfa->inveclosures + dest_nodes->elems[i]);
0742e48e 1863 }
5cf1ec52
UD		 1864 return re_node_set_add_intersect (dest_nodes, candidates,
1865 &state->inveclosure);
0742e48e 1866}
3b0bdc72 1867
0742e48e 1868static reg_errcode_t
a334319f 1869sub_epsilon_src_nodes (dfa, node, dest_nodes, candidates)
76b864c8 1870 const re_dfa_t *dfa;
a334319f
UD		 1871 int node;
1872 re_node_set *dest_nodes;
1873 const re_node_set *candidates;
0742e48e
UD		 1874{
1875 int ecl_idx;
1876 reg_errcode_t err;
1877 re_node_set *inv_eclosure = dfa->inveclosures + node;
1878 re_node_set except_nodes;
1879 re_node_set_init_empty (&except_nodes);
1880 for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx)
1881 {
15a7d175
UD		 1882 int cur_node = inv_eclosure->elems[ecl_idx];
1883 if (cur_node == node)
1884 continue;
1885 if (IS_EPSILON_NODE (dfa->nodes[cur_node].type))
1886 {
1887 int edst1 = dfa->edests[cur_node].elems[0];
1888 int edst2 = ((dfa->edests[cur_node].nelem > 1)
1889 ? dfa->edests[cur_node].elems[1] : -1);
1890 if ((!re_node_set_contains (inv_eclosure, edst1)
1891 && re_node_set_contains (dest_nodes, edst1))
1892 || (edst2 > 0
1893 && !re_node_set_contains (inv_eclosure, edst2)
1894 && re_node_set_contains (dest_nodes, edst2)))
1895 {
1896 err = re_node_set_add_intersect (&except_nodes, candidates,
1897 dfa->inveclosures + cur_node);
1898 if (BE (err != REG_NOERROR, 0))
1899 {
1900 re_node_set_free (&except_nodes);
1901 return err;
1902 }
1903 }
1904 }
0742e48e
UD		 1905 }
1906 for (ecl_idx = 0; ecl_idx < inv_eclosure->nelem; ++ecl_idx)
1907 {
15a7d175
UD		 1908 int cur_node = inv_eclosure->elems[ecl_idx];
1909 if (!re_node_set_contains (&except_nodes, cur_node))
1910 {
1911 int idx = re_node_set_contains (dest_nodes, cur_node) - 1;
1912 re_node_set_remove_at (dest_nodes, idx);
1913 }
0742e48e
UD		 1914 }
1915 re_node_set_free (&except_nodes);
1916 return REG_NOERROR;
1917}
1918
a3022b82 1919static int
a334319f 1920check_dst_limits (mctx, limits, dst_node, dst_idx, src_node, src_idx)
01ed6ceb 1921 const re_match_context_t *mctx;
a334319f
UD		 1922 re_node_set *limits;
1923 int dst_node, dst_idx, src_node, src_idx;
a3022b82 1924{
76b864c8 1925 const re_dfa_t *const dfa = mctx->dfa;
a3022b82
UD		 1926 int lim_idx, src_pos, dst_pos;
1927
e40a38b3
UD		 1928 int dst_bkref_idx = search_cur_bkref_entry (mctx, dst_idx);
1929 int src_bkref_idx = search_cur_bkref_entry (mctx, src_idx);
a3022b82
UD		 1930 for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx)
1931 {
485d775d 1932 int subexp_idx;
a3022b82
UD		 1933 struct re_backref_cache_entry *ent;
1934 ent = mctx->bkref_ents + limits->elems[lim_idx];
d8f73de8 1935 subexp_idx = dfa->nodes[ent->node].opr.idx;
a3022b82 1936
e3a87852 1937 dst_pos = check_dst_limits_calc_pos (mctx, limits->elems[lim_idx],
e40a38b3
UD		 1938 subexp_idx, dst_node, dst_idx,
1939 dst_bkref_idx);
e3a87852 1940 src_pos = check_dst_limits_calc_pos (mctx, limits->elems[lim_idx],
e40a38b3
UD		 1941 subexp_idx, src_node, src_idx,
1942 src_bkref_idx);
a3022b82
UD		 1943
1944 /* In case of:
15a7d175
UD		 1945 <src> <dst> ( <subexp> )
1946 ( <subexp> ) <src> <dst>
1947 ( <subexp1> <src> <subexp2> <dst> <subexp3> ) */
a3022b82 1948 if (src_pos == dst_pos)
15a7d175 1949 continue; /* This is unrelated limitation. */
a3022b82 1950 else
15a7d175 1951 return 1;
a3022b82
UD		 1952 }
1953 return 0;
1954}
1955
1956static int
a334319f 1957check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx, from_node, bkref_idx)
01ed6ceb 1958 const re_match_context_t *mctx;
a334319f 1959 int boundaries, subexp_idx, from_node, bkref_idx;
a3022b82 1960{
76b864c8
UD		 1961 const re_dfa_t *const dfa = mctx->dfa;
1962 const re_node_set *eclosures = dfa->eclosures + from_node;
1cef7b3c 1963 int node_idx;
d0b96fc4 1964
d0b96fc4
UD		 1965 /* Else, we are on the boundary: examine the nodes on the epsilon
1966 closure. */
1cef7b3c
UD		 1967 for (node_idx = 0; node_idx < eclosures->nelem; ++node_idx)
1968 {
1969 int node = eclosures->elems[node_idx];
d0b96fc4
UD		 1970 switch (dfa->nodes[node].type)
1971 {
1972 case OP_BACK_REF:
d8f73de8
UD		 1973 if (bkref_idx != -1)
1974 {
1975 struct re_backref_cache_entry *ent = mctx->bkref_ents + bkref_idx;
1976 do
1977 {
1978 int dst, cpos;
d0b96fc4 1979
d8f73de8
UD		 1980 if (ent->node != node)
1981 continue;
d0b96fc4 1982
2c05d33f
UD		 1983 if (subexp_idx < BITSET_WORD_BITS
1984 && !(ent->eps_reachable_subexps_map
1985 & ((bitset_word_t) 1 << subexp_idx)))
d8f73de8 1986 continue;
d0b96fc4 1987
d8f73de8
UD		 1988 /* Recurse trying to reach the OP_OPEN_SUBEXP and
1989 OP_CLOSE_SUBEXP cases below. But, if the
1990 destination node is the same node as the source
1991 node, don't recurse because it would cause an
1992 infinite loop: a regex that exhibits this behavior
1993 is ()\1*\1* */
1994 dst = dfa->edests[node].elems[0];
1995 if (dst == from_node)
1996 {
1997 if (boundaries & 1)
1998 return -1;
1999 else /* if (boundaries & 2) */
2000 return 0;
2001 }
7db61208 2002
d8f73de8
UD		 2003 cpos =
2004 check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx,
2005 dst, bkref_idx);
2006 if (cpos == -1 /* && (boundaries & 1) */)
2007 return -1;
2008 if (cpos == 0 && (boundaries & 2))
2009 return 0;
2010
2c05d33f
UD		 2011 if (subexp_idx < BITSET_WORD_BITS)
2012 ent->eps_reachable_subexps_map
2013 &= ~((bitset_word_t) 1 << subexp_idx);
d8f73de8
UD		 2014 }
2015 while (ent++->more);
2016 }
2017 break;
f0c7c524 2018
d0b96fc4 2019 case OP_OPEN_SUBEXP:
e40a38b3 2020 if ((boundaries & 1) && subexp_idx == dfa->nodes[node].opr.idx)
d0b96fc4
UD		 2021 return -1;
2022 break;
f0c7c524 2023
d0b96fc4 2024 case OP_CLOSE_SUBEXP:
e40a38b3 2025 if ((boundaries & 2) && subexp_idx == dfa->nodes[node].opr.idx)
d0b96fc4
UD		 2026 return 0;
2027 break;
2028
2029 default:
15a7d175
UD		 2030 break;
2031 }
a3022b82 2032 }
d0b96fc4 2033
e40a38b3
UD		 2034 return (boundaries & 2) ? 1 : 0;
2035}
2036
2037static int
a334319f 2038check_dst_limits_calc_pos (mctx, limit, subexp_idx, from_node, str_idx, bkref_idx)
01ed6ceb 2039 const re_match_context_t *mctx;
a334319f 2040 int limit, subexp_idx, from_node, str_idx, bkref_idx;
e40a38b3
UD		 2041{
2042 struct re_backref_cache_entry *lim = mctx->bkref_ents + limit;
2043 int boundaries;
2044
2045 /* If we are outside the range of the subexpression, return -1 or 1. */
2046 if (str_idx < lim->subexp_from)
2047 return -1;
2048
2049 if (lim->subexp_to < str_idx)
d0b96fc4 2050 return 1;
e40a38b3
UD		 2051
2052 /* If we are within the subexpression, return 0. */
2053 boundaries = (str_idx == lim->subexp_from);
2054 boundaries |= (str_idx == lim->subexp_to) << 1;
2055 if (boundaries == 0)
d0b96fc4 2056 return 0;
e40a38b3
UD		 2057
2058 /* Else, examine epsilon closure. */
2059 return check_dst_limits_calc_pos_1 (mctx, boundaries, subexp_idx,
2060 from_node, bkref_idx);
a3022b82
UD		 2061}
2062
0742e48e
UD		 2063/* Check the limitations of sub expressions LIMITS, and remove the nodes
2064 which are against limitations from DEST_NODES. */
2065
2066static reg_errcode_t
a334319f 2067check_subexp_limits (dfa, dest_nodes, candidates, limits, bkref_ents, str_idx)
76b864c8 2068 const re_dfa_t *dfa;
a334319f
UD		 2069 re_node_set *dest_nodes;
2070 const re_node_set *candidates;
2071 re_node_set *limits;
2072 struct re_backref_cache_entry *bkref_ents;
2073 int str_idx;
0742e48e
UD		 2074{
2075 reg_errcode_t err;
2076 int node_idx, lim_idx;
2077
2078 for (lim_idx = 0; lim_idx < limits->nelem; ++lim_idx)
2079 {
485d775d 2080 int subexp_idx;
0742e48e
UD		 2081 struct re_backref_cache_entry *ent;
2082 ent = bkref_ents + limits->elems[lim_idx];
2083
2084 if (str_idx <= ent->subexp_from || ent->str_idx < str_idx)
15a7d175 2085 continue; /* This is unrelated limitation. */
0742e48e 2086
d8f73de8 2087 subexp_idx = dfa->nodes[ent->node].opr.idx;
0742e48e 2088 if (ent->subexp_to == str_idx)
15a7d175
UD		 2089 {
2090 int ops_node = -1;
2091 int cls_node = -1;
2092 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2093 {
2094 int node = dest_nodes->elems[node_idx];
46bf9de7 2095 re_token_type_t type = dfa->nodes[node].type;
15a7d175
UD		 2096 if (type == OP_OPEN_SUBEXP
2097 && subexp_idx == dfa->nodes[node].opr.idx)
2098 ops_node = node;
2099 else if (type == OP_CLOSE_SUBEXP
2100 && subexp_idx == dfa->nodes[node].opr.idx)
2101 cls_node = node;
2102 }
2103
2104 /* Check the limitation of the open subexpression. */
2105 /* Note that (ent->subexp_to = str_idx != ent->subexp_from). */
2106 if (ops_node >= 0)
2107 {
46bf9de7
UD		 2108 err = sub_epsilon_src_nodes (dfa, ops_node, dest_nodes,
2109 candidates);
15a7d175
UD		 2110 if (BE (err != REG_NOERROR, 0))
2111 return err;
2112 }
46bf9de7 2113
15a7d175 2114 /* Check the limitation of the close subexpression. */
46bf9de7
UD		 2115 if (cls_node >= 0)
2116 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2117 {
2118 int node = dest_nodes->elems[node_idx];
2119 if (!re_node_set_contains (dfa->inveclosures + node,
2120 cls_node)
2121 && !re_node_set_contains (dfa->eclosures + node,
2122 cls_node))
2123 {
2124 /* It is against this limitation.
2125 Remove it form the current sifted state. */
2126 err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2127 candidates);
2128 if (BE (err != REG_NOERROR, 0))
2129 return err;
2130 --node_idx;
2131 }
2132 }
15a7d175 2133 }
0742e48e 2134 else /* (ent->subexp_to != str_idx) */
15a7d175
UD		 2135 {
2136 for (node_idx = 0; node_idx < dest_nodes->nelem; ++node_idx)
2137 {
2138 int node = dest_nodes->elems[node_idx];
46bf9de7 2139 re_token_type_t type = dfa->nodes[node].type;
15a7d175
UD		 2140 if (type == OP_CLOSE_SUBEXP || type == OP_OPEN_SUBEXP)
2141 {
2142 if (subexp_idx != dfa->nodes[node].opr.idx)
2143 continue;
d8f73de8
UD		 2144 /* It is against this limitation.
2145 Remove it form the current sifted state. */
2146 err = sub_epsilon_src_nodes (dfa, node, dest_nodes,
2147 candidates);
2148 if (BE (err != REG_NOERROR, 0))
2149 return err;
15a7d175
UD		 2150 }
2151 }
2152 }
0742e48e
UD		 2153 }
2154 return REG_NOERROR;
2155}
2156
0742e48e 2157static reg_errcode_t
a334319f 2158sift_states_bkref (mctx, sctx, str_idx, candidates)
76b864c8 2159 const re_match_context_t *mctx;
a334319f
UD		 2160 re_sift_context_t *sctx;
2161 int str_idx;
2162 const re_node_set *candidates;
0742e48e 2163{
76b864c8 2164 const re_dfa_t *const dfa = mctx->dfa;
0742e48e 2165 reg_errcode_t err;
0742e48e
UD		 2166 int node_idx, node;
2167 re_sift_context_t local_sctx;
e40a38b3
UD		 2168 int first_idx = search_cur_bkref_entry (mctx, str_idx);
2169
2170 if (first_idx == -1)
2171 return REG_NOERROR;
2172
0742e48e
UD		 2173 local_sctx.sifted_states = NULL; /* Mark that it hasn't been initialized. */
2174
2175 for (node_idx = 0; node_idx < candidates->nelem; ++node_idx)
2176 {
e40a38b3 2177 int enabled_idx;
0742e48e 2178 re_token_type_t type;
e40a38b3 2179 struct re_backref_cache_entry *entry;
0742e48e
UD		 2180 node = candidates->elems[node_idx];
2181 type = dfa->nodes[node].type;
0742e48e
UD		 2182 /* Avoid infinite loop for the REs like "()\1+". */
2183 if (node == sctx->last_node && str_idx == sctx->last_str_idx)
15a7d175 2184 continue;
e40a38b3
UD		 2185 if (type != OP_BACK_REF)
2186 continue;
2187
2188 entry = mctx->bkref_ents + first_idx;
2189 enabled_idx = first_idx;
2190 do
15a7d175 2191 {
2d87db5b
UD		 2192 int subexp_len;
2193 int to_idx;
2194 int dst_node;
2195 int ret;
e40a38b3
UD		 2196 re_dfastate_t *cur_state;
2197
2198 if (entry->node != node)
2199 continue;
2200 subexp_len = entry->subexp_to - entry->subexp_from;
2201 to_idx = str_idx + subexp_len;
2202 dst_node = (subexp_len ? dfa->nexts[node]
2203 : dfa->edests[node].elems[0]);
2204
2205 if (to_idx > sctx->last_str_idx
2206 || sctx->sifted_states[to_idx] == NULL
2207 || !STATE_NODE_CONTAINS (sctx->sifted_states[to_idx], dst_node)
2208 || check_dst_limits (mctx, &sctx->limits, node,
2209 str_idx, dst_node, to_idx))
2210 continue;
2211
2212 if (local_sctx.sifted_states == NULL)
15a7d175 2213 {
e40a38b3
UD		 2214 local_sctx = *sctx;
2215 err = re_node_set_init_copy (&local_sctx.limits, &sctx->limits);
2216 if (BE (err != REG_NOERROR, 0))
2217 goto free_return;
2218 }
2219 local_sctx.last_node = node;
2220 local_sctx.last_str_idx = str_idx;
2d87db5b
UD		 2221 ret = re_node_set_insert (&local_sctx.limits, enabled_idx);
2222 if (BE (ret < 0, 0))
e40a38b3
UD		 2223 {
2224 err = REG_ESPACE;
2225 goto free_return;
15a7d175 2226 }
e40a38b3
UD		 2227 cur_state = local_sctx.sifted_states[str_idx];
2228 err = sift_states_backward (mctx, &local_sctx);
2229 if (BE (err != REG_NOERROR, 0))
2230 goto free_return;
2231 if (sctx->limited_states != NULL)
2232 {
2233 err = merge_state_array (dfa, sctx->limited_states,
2234 local_sctx.sifted_states,
2235 str_idx + 1);
2236 if (BE (err != REG_NOERROR, 0))
2237 goto free_return;
2238 }
2239 local_sctx.sifted_states[str_idx] = cur_state;
2240 re_node_set_remove (&local_sctx.limits, enabled_idx);
2241
2242 /* mctx->bkref_ents may have changed, reload the pointer. */
2243 entry = mctx->bkref_ents + enabled_idx;
15a7d175 2244 }
e40a38b3 2245 while (enabled_idx++, entry++->more);
0742e48e 2246 }
1b2c2628
UD		 2247 err = REG_NOERROR;
2248 free_return:
0742e48e
UD		 2249 if (local_sctx.sifted_states != NULL)
2250 {
0742e48e
UD		 2251 re_node_set_free (&local_sctx.limits);
2252 }
2253
1b2c2628 2254 return err;
0742e48e
UD		 2255}
2256
2257
2258#ifdef RE_ENABLE_I18N
2259static int
a334319f
UD		 2260sift_states_iter_mb (mctx, sctx, node_idx, str_idx, max_str_idx)
2261 const re_match_context_t *mctx;
2262 re_sift_context_t *sctx;
2263 int node_idx, str_idx, max_str_idx;
0742e48e 2264{
c42b4152 2265 const re_dfa_t *const dfa = mctx->dfa;
0742e48e
UD		 2266 int naccepted;
2267 /* Check the node can accept `multi byte'. */
56b168be 2268 naccepted = check_node_accept_bytes (dfa, node_idx, &mctx->input, str_idx);
0742e48e
UD		 2269 if (naccepted > 0 && str_idx + naccepted <= max_str_idx &&
2270 !STATE_NODE_CONTAINS (sctx->sifted_states[str_idx + naccepted],
15a7d175 2271 dfa->nexts[node_idx]))
0742e48e 2272 /* The node can't accept the `multi byte', or the
bb3f4825 2273 destination was already thrown away, then the node
0742e48e
UD		 2274 could't accept the current input `multi byte'. */
2275 naccepted = 0;
2276 /* Otherwise, it is sure that the node could accept
2277 `naccepted' bytes input. */
2278 return naccepted;
2279}
2280#endif /* RE_ENABLE_I18N */
2281
3b0bdc72
UD		 2282\f
2283/* Functions for state transition. */
2284
2285/* Return the next state to which the current state STATE will transit by
2286 accepting the current input byte, and update STATE_LOG if necessary.
2287 If STATE can accept a multibyte char/collating element/back reference
2288 update the destination of STATE_LOG. */
2289
2290static re_dfastate_t *
a334319f
UD		 2291transit_state (err, mctx, state)
2292 reg_errcode_t *err;
2293 re_match_context_t *mctx;
2294 re_dfastate_t *state;
3b0bdc72 2295{
58845a70 2296 re_dfastate_t **trtable;
3b0bdc72
UD		 2297 unsigned char ch;
2298
bb677c95
UD		 2299#ifdef RE_ENABLE_I18N
2300 /* If the current state can accept multibyte. */
2301 if (BE (state->accept_mb, 0))
612546c6 2302 {
bb677c95 2303 *err = transit_state_mb (mctx, state);
612546c6 2304 if (BE (*err != REG_NOERROR, 0))
15a7d175 2305 return NULL;
612546c6 2306 }
434d3784 2307#endif /* RE_ENABLE_I18N */
3b0bdc72 2308
4c595adb 2309 /* Then decide the next state with the single byte. */
ab4b89fe
UD		 2310#if 0
2311 if (0)
2312 /* don't use transition table */
2313 return transit_state_sb (err, mctx, state);
2314#endif
2315
2316 /* Use transition table */
2317 ch = re_string_fetch_byte (&mctx->input);
2318 for (;;)
4c595adb 2319 {
4c595adb 2320 trtable = state->trtable;
ab4b89fe
UD		 2321 if (BE (trtable != NULL, 1))
2322 return trtable[ch];
2323
2324 trtable = state->word_trtable;
2325 if (BE (trtable != NULL, 1))
4c595adb
UD		 2326 {
2327 unsigned int context;
2328 context
2329 = re_string_context_at (&mctx->input,
2330 re_string_cur_idx (&mctx->input) - 1,
2331 mctx->eflags);
2332 if (IS_WORD_CONTEXT (context))
2333 return trtable[ch + SBC_MAX];
c13c99fa 2334 else
4c595adb 2335 return trtable[ch];
15a7d175 2336 }
ab4b89fe
UD		 2337
2338 if (!build_trtable (mctx->dfa, state))
2339 {
2340 *err = REG_ESPACE;
2341 return NULL;
2342 }
2343
2344 /* Retry, we now have a transition table. */
3b0bdc72 2345 }
4c595adb 2346}
3b0bdc72 2347
4c595adb 2348/* Update the state_log if we need */
58845a70 2349re_dfastate_t *
a334319f
UD		 2350merge_state_with_log (err, mctx, next_state)
2351 reg_errcode_t *err;
2352 re_match_context_t *mctx;
2353 re_dfastate_t *next_state;
58845a70 2354{
c42b4152 2355 const re_dfa_t *const dfa = mctx->dfa;
4c595adb
UD		 2356 int cur_idx = re_string_cur_idx (&mctx->input);
2357
2358 if (cur_idx > mctx->state_log_top)
3b0bdc72 2359 {
4c595adb
UD		 2360 mctx->state_log[cur_idx] = next_state;
2361 mctx->state_log_top = cur_idx;
2362 }
2363 else if (mctx->state_log[cur_idx] == 0)
2364 {
2365 mctx->state_log[cur_idx] = next_state;
2366 }
2367 else
2368 {
2369 re_dfastate_t *pstate;
2370 unsigned int context;
2371 re_node_set next_nodes, *log_nodes, *table_nodes = NULL;
2372 /* If (state_log[cur_idx] != 0), it implies that cur_idx is
2373 the destination of a multibyte char/collating element/
2374 back reference. Then the next state is the union set of
2375 these destinations and the results of the transition table. */
2376 pstate = mctx->state_log[cur_idx];
2377 log_nodes = pstate->entrance_nodes;
2378 if (next_state != NULL)
2379 {
2380 table_nodes = next_state->entrance_nodes;
2381 *err = re_node_set_init_union (&next_nodes, table_nodes,
15a7d175 2382 log_nodes);
4c595adb
UD		 2383 if (BE (*err != REG_NOERROR, 0))
2384 return NULL;
2385 }
2386 else
2387 next_nodes = *log_nodes;
2388 /* Note: We already add the nodes of the initial state,
2389 then we don't need to add them here. */
2390
2391 context = re_string_context_at (&mctx->input,
2392 re_string_cur_idx (&mctx->input) - 1,
2393 mctx->eflags);
2394 next_state = mctx->state_log[cur_idx]
2395 = re_acquire_state_context (err, dfa, &next_nodes, context);
2396 /* We don't need to check errors here, since the return value of
2397 this function is next_state and ERR is already set. */
2398
2399 if (table_nodes != NULL)
2400 re_node_set_free (&next_nodes);
6291ee3c
UD		 2401 }
2402
bb3f4825 2403 if (BE (dfa->nbackref, 0) && next_state != NULL)
6291ee3c 2404 {
bb3f4825
UD		 2405 /* Check OP_OPEN_SUBEXP in the current state in case that we use them
2406 later. We must check them here, since the back references in the
2407 next state might use them. */
e3a87852 2408 *err = check_subexp_matching_top (mctx, &next_state->nodes,
6291ee3c
UD		 2409 cur_idx);
2410 if (BE (*err != REG_NOERROR, 0))
2411 return NULL;
6291ee3c 2412
bb3f4825
UD		 2413 /* If the next state has back references. */
2414 if (next_state->has_backref)
2415 {
e3a87852 2416 *err = transit_state_bkref (mctx, &next_state->nodes);
bb3f4825
UD		 2417 if (BE (*err != REG_NOERROR, 0))
2418 return NULL;
2419 next_state = mctx->state_log[cur_idx];
2420 }
3b0bdc72 2421 }
4c595adb 2422
3b0bdc72
UD		 2423 return next_state;
2424}
2425
4c595adb
UD		 2426/* Skip bytes in the input that correspond to part of a
2427 multi-byte match, then look in the log for a state
2428 from which to restart matching. */
2429re_dfastate_t *
a334319f
UD		 2430find_recover_state (err, mctx)
2431 reg_errcode_t *err;
2432 re_match_context_t *mctx;
4c595adb 2433{
1878e9af 2434 re_dfastate_t *cur_state;
4c595adb
UD		 2435 do
2436 {
2437 int max = mctx->state_log_top;
2438 int cur_str_idx = re_string_cur_idx (&mctx->input);
2439
2440 do
2441 {
2442 if (++cur_str_idx > max)
2443 return NULL;
2444 re_string_skip_bytes (&mctx->input, 1);
2445 }
2446 while (mctx->state_log[cur_str_idx] == NULL);
2447
2448 cur_state = merge_state_with_log (err, mctx, NULL);
2449 }
2d87db5b 2450 while (*err == REG_NOERROR && cur_state == NULL);
4c595adb
UD		 2451 return cur_state;
2452}
2453
3b0bdc72
UD		 2454/* Helper functions for transit_state. */
2455
6291ee3c
UD		 2456/* From the node set CUR_NODES, pick up the nodes whose types are
2457 OP_OPEN_SUBEXP and which have corresponding back references in the regular
2458 expression. And register them to use them later for evaluating the
2459 correspoding back references. */
2460
2461static reg_errcode_t
a334319f
UD		 2462check_subexp_matching_top (mctx, cur_nodes, str_idx)
2463 re_match_context_t *mctx;
2464 re_node_set *cur_nodes;
2465 int str_idx;
6291ee3c 2466{
76b864c8 2467 const re_dfa_t *const dfa = mctx->dfa;
6291ee3c
UD		 2468 int node_idx;
2469 reg_errcode_t err;
2470
2471 /* TODO: This isn't efficient.
2472 Because there might be more than one nodes whose types are
2473 OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
2474 nodes.
2475 E.g. RE: (a){2} */
2476 for (node_idx = 0; node_idx < cur_nodes->nelem; ++node_idx)
2477 {
2478 int node = cur_nodes->elems[node_idx];
2479 if (dfa->nodes[node].type == OP_OPEN_SUBEXP
2c05d33f
UD		 2480 && dfa->nodes[node].opr.idx < BITSET_WORD_BITS
2481 && (dfa->used_bkref_map
2482 & ((bitset_word_t) 1 << dfa->nodes[node].opr.idx)))
6291ee3c
UD		 2483 {
2484 err = match_ctx_add_subtop (mctx, node, str_idx);
2485 if (BE (err != REG_NOERROR, 0))
2486 return err;
2487 }
2488 }
2489 return REG_NOERROR;
2490}
2491
c13c99fa 2492#if 0
3b0bdc72
UD		 2493/* Return the next state to which the current state STATE will transit by
2494 accepting the current input byte. */
2495
2496static re_dfastate_t *
a334319f
UD		 2497transit_state_sb (err, mctx, state)
2498 reg_errcode_t *err;
2499 re_match_context_t *mctx;
2500 re_dfastate_t *state;
3b0bdc72 2501{
c42b4152 2502 const re_dfa_t *const dfa = mctx->dfa;
3b0bdc72
UD		 2503 re_node_set next_nodes;
2504 re_dfastate_t *next_state;
56b168be 2505 int node_cnt, cur_str_idx = re_string_cur_idx (&mctx->input);
3b0bdc72
UD		 2506 unsigned int context;
2507
a9388965 2508 *err = re_node_set_alloc (&next_nodes, state->nodes.nelem + 1);
bc15410e 2509 if (BE (*err != REG_NOERROR, 0))
a9388965 2510 return NULL;
3b0bdc72
UD		 2511 for (node_cnt = 0; node_cnt < state->nodes.nelem; ++node_cnt)
2512 {
2513 int cur_node = state->nodes.elems[node_cnt];
e3a87852 2514 if (check_node_accept (mctx, dfa->nodes + cur_node, cur_str_idx))
15a7d175
UD		 2515 {
2516 *err = re_node_set_merge (&next_nodes,
2517 dfa->eclosures + dfa->nexts[cur_node]);
2518 if (BE (*err != REG_NOERROR, 0))
2519 {
2520 re_node_set_free (&next_nodes);
2521 return NULL;
2522 }
2523 }
3b0bdc72 2524 }
56b168be 2525 context = re_string_context_at (&mctx->input, cur_str_idx, mctx->eflags);
a9388965
UD		 2526 next_state = re_acquire_state_context (err, dfa, &next_nodes, context);
2527 /* We don't need to check errors here, since the return value of
2528 this function is next_state and ERR is already set. */
2529
3b0bdc72 2530 re_node_set_free (&next_nodes);
56b168be 2531 re_string_skip_bytes (&mctx->input, 1);
3b0bdc72
UD		 2532 return next_state;
2533}
c13c99fa 2534#endif
3b0bdc72 2535
434d3784 2536#ifdef RE_ENABLE_I18N
a9388965 2537static reg_errcode_t
a334319f
UD		 2538transit_state_mb (mctx, pstate)
2539 re_match_context_t *mctx;
2540 re_dfastate_t *pstate;
3b0bdc72 2541{
c42b4152 2542 const re_dfa_t *const dfa = mctx->dfa;
a9388965 2543 reg_errcode_t err;
3b0bdc72
UD		 2544 int i;
2545
2546 for (i = 0; i < pstate->nodes.nelem; ++i)
2547 {
2548 re_node_set dest_nodes, *new_nodes;
2549 int cur_node_idx = pstate->nodes.elems[i];
963d8d78 2550 int naccepted, dest_idx;
3b0bdc72
UD		 2551 unsigned int context;
2552 re_dfastate_t *dest_state;
2553
963d8d78
UD		 2554 if (!dfa->nodes[cur_node_idx].accept_mb)
2555 continue;
2556
485d775d 2557 if (dfa->nodes[cur_node_idx].constraint)
15a7d175 2558 {
56b168be
UD		 2559 context = re_string_context_at (&mctx->input,
2560 re_string_cur_idx (&mctx->input),
2561 mctx->eflags);
15a7d175
UD		 2562 if (NOT_SATISFY_NEXT_CONSTRAINT (dfa->nodes[cur_node_idx].constraint,
2563 context))
2564 continue;
2565 }
3b0bdc72 2566
ad7f28c2 2567 /* How many bytes the node can accept? */
963d8d78
UD		 2568 naccepted = check_node_accept_bytes (dfa, cur_node_idx, &mctx->input,
2569 re_string_cur_idx (&mctx->input));
3b0bdc72 2570 if (naccepted == 0)
15a7d175 2571 continue;
3b0bdc72
UD		 2572
2573 /* The node can accepts `naccepted' bytes. */
56b168be 2574 dest_idx = re_string_cur_idx (&mctx->input) + naccepted;
0742e48e 2575 mctx->max_mb_elem_len = ((mctx->max_mb_elem_len < naccepted) ? naccepted
15a7d175 2576 : mctx->max_mb_elem_len);
7c1be3ec 2577 err = clean_state_log_if_needed (mctx, dest_idx);
612546c6 2578 if (BE (err != REG_NOERROR, 0))
15a7d175 2579 return err;
3b0bdc72
UD		 2580#ifdef DEBUG
2581 assert (dfa->nexts[cur_node_idx] != -1);
2582#endif
963d8d78 2583 new_nodes = dfa->eclosures + dfa->nexts[cur_node_idx];
3b0bdc72 2584
612546c6 2585 dest_state = mctx->state_log[dest_idx];
3b0bdc72 2586 if (dest_state == NULL)
15a7d175 2587 dest_nodes = *new_nodes;
3b0bdc72 2588 else
15a7d175
UD		 2589 {
2590 err = re_node_set_init_union (&dest_nodes,
2591 dest_state->entrance_nodes, new_nodes);
2592 if (BE (err != REG_NOERROR, 0))
2593 return err;
2594 }
01ed6ceb
UD		 2595 context = re_string_context_at (&mctx->input, dest_idx - 1,
2596 mctx->eflags);
612546c6 2597 mctx->state_log[dest_idx]
15a7d175 2598 = re_acquire_state_context (&err, dfa, &dest_nodes, context);
3b0bdc72 2599 if (dest_state != NULL)
15a7d175 2600 re_node_set_free (&dest_nodes);
1b2c2628 2601 if (BE (mctx->state_log[dest_idx] == NULL && err != REG_NOERROR, 0))
15a7d175 2602 return err;
3b0bdc72 2603 }
a9388965 2604 return REG_NOERROR;
3b0bdc72 2605}
434d3784 2606#endif /* RE_ENABLE_I18N */
3b0bdc72 2607
a9388965 2608static reg_errcode_t
a334319f
UD		 2609transit_state_bkref (mctx, nodes)
2610 re_match_context_t *mctx;
2611 const re_node_set *nodes;
3b0bdc72 2612{
6efbd82c 2613 const re_dfa_t *const dfa = mctx->dfa;
a9388965 2614 reg_errcode_t err;
0742e48e 2615 int i;
56b168be 2616 int cur_str_idx = re_string_cur_idx (&mctx->input);
3b0bdc72
UD		 2617
2618 for (i = 0; i < nodes->nelem; ++i)
2619 {
6291ee3c 2620 int dest_str_idx, prev_nelem, bkc_idx;
3b0bdc72
UD		 2621 int node_idx = nodes->elems[i];
2622 unsigned int context;
fe9434bb 2623 const re_token_t *node = dfa->nodes + node_idx;
3b0bdc72
UD		 2624 re_node_set *new_dest_nodes;
2625
2626 /* Check whether `node' is a backreference or not. */
6291ee3c 2627 if (node->type != OP_BACK_REF)
15a7d175 2628 continue;
485d775d
UD		 2629
2630 if (node->constraint)
15a7d175 2631 {
56b168be
UD		 2632 context = re_string_context_at (&mctx->input, cur_str_idx,
2633 mctx->eflags);
15a7d175
UD		 2634 if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
2635 continue;
2636 }
3b0bdc72
UD		 2637
2638 /* `node' is a backreference.
15a7d175 2639 Check the substring which the substring matched. */
6291ee3c 2640 bkc_idx = mctx->nbkref_ents;
e3a87852 2641 err = get_subexp (mctx, node_idx, cur_str_idx);
612546c6 2642 if (BE (err != REG_NOERROR, 0))
15a7d175 2643 goto free_return;
3b0bdc72
UD		 2644
2645 /* And add the epsilon closures (which is `new_dest_nodes') of
15a7d175 2646 the backreference to appropriate state_log. */
3b0bdc72
UD		 2647#ifdef DEBUG
2648 assert (dfa->nexts[node_idx] != -1);
2649#endif
6291ee3c 2650 for (; bkc_idx < mctx->nbkref_ents; ++bkc_idx)
15a7d175
UD		 2651 {
2652 int subexp_len;
2653 re_dfastate_t *dest_state;
2654 struct re_backref_cache_entry *bkref_ent;
2655 bkref_ent = mctx->bkref_ents + bkc_idx;
2656 if (bkref_ent->node != node_idx || bkref_ent->str_idx != cur_str_idx)
2657 continue;
2658 subexp_len = bkref_ent->subexp_to - bkref_ent->subexp_from;
2659 new_dest_nodes = (subexp_len == 0
2660 ? dfa->eclosures + dfa->edests[node_idx].elems[0]
2661 : dfa->eclosures + dfa->nexts[node_idx]);
2662 dest_str_idx = (cur_str_idx + bkref_ent->subexp_to
2663 - bkref_ent->subexp_from);
56b168be
UD		 2664 context = re_string_context_at (&mctx->input, dest_str_idx - 1,
2665 mctx->eflags);
15a7d175
UD		 2666 dest_state = mctx->state_log[dest_str_idx];
2667 prev_nelem = ((mctx->state_log[cur_str_idx] == NULL) ? 0
2668 : mctx->state_log[cur_str_idx]->nodes.nelem);
2669 /* Add `new_dest_node' to state_log. */
2670 if (dest_state == NULL)
2671 {
2672 mctx->state_log[dest_str_idx]
2673 = re_acquire_state_context (&err, dfa, new_dest_nodes,
2674 context);
2675 if (BE (mctx->state_log[dest_str_idx] == NULL
2676 && err != REG_NOERROR, 0))
2677 goto free_return;
2678 }
2679 else
2680 {
2681 re_node_set dest_nodes;
2682 err = re_node_set_init_union (&dest_nodes,
2683 dest_state->entrance_nodes,
2684 new_dest_nodes);
2685 if (BE (err != REG_NOERROR, 0))
2686 {
2687 re_node_set_free (&dest_nodes);
2688 goto free_return;
2689 }
2690 mctx->state_log[dest_str_idx]
2691 = re_acquire_state_context (&err, dfa, &dest_nodes, context);
2692 re_node_set_free (&dest_nodes);
2693 if (BE (mctx->state_log[dest_str_idx] == NULL
2694 && err != REG_NOERROR, 0))
2695 goto free_return;
2696 }
2697 /* We need to check recursively if the backreference can epsilon
2698 transit. */
2699 if (subexp_len == 0
2700 && mctx->state_log[cur_str_idx]->nodes.nelem > prev_nelem)
2701 {
e3a87852 2702 err = check_subexp_matching_top (mctx, new_dest_nodes,
6291ee3c
UD		 2703 cur_str_idx);
2704 if (BE (err != REG_NOERROR, 0))
2705 goto free_return;
e3a87852 2706 err = transit_state_bkref (mctx, new_dest_nodes);
15a7d175
UD		 2707 if (BE (err != REG_NOERROR, 0))
2708 goto free_return;
2709 }
2710 }
3b0bdc72 2711 }
1b2c2628
UD		 2712 err = REG_NOERROR;
2713 free_return:
1b2c2628 2714 return err;
3b0bdc72
UD		 2715}
2716
6291ee3c
UD		 2717/* Enumerate all the candidates which the backreference BKREF_NODE can match
2718 at BKREF_STR_IDX, and register them by match_ctx_add_entry().
2719 Note that we might collect inappropriate candidates here.
2720 However, the cost of checking them strictly here is too high, then we
2721 delay these checking for prune_impossible_nodes(). */
3b0bdc72 2722
6291ee3c 2723static reg_errcode_t
a334319f
UD		 2724get_subexp (mctx, bkref_node, bkref_str_idx)
2725 re_match_context_t *mctx;
2726 int bkref_node, bkref_str_idx;
3b0bdc72 2727{
6efbd82c 2728 const re_dfa_t *const dfa = mctx->dfa;
6291ee3c 2729 int subexp_num, sub_top_idx;
56b168be 2730 const char *buf = (const char *) re_string_get_buffer (&mctx->input);
6291ee3c
UD		 2731 /* Return if we have already checked BKREF_NODE at BKREF_STR_IDX. */
2732 int cache_idx = search_cur_bkref_entry (mctx, bkref_str_idx);
e40a38b3 2733 if (cache_idx != -1)
6291ee3c 2734 {
01ed6ceb
UD		 2735 const struct re_backref_cache_entry *entry
2736 = mctx->bkref_ents + cache_idx;
e40a38b3
UD		 2737 do
2738 if (entry->node == bkref_node)
2739 return REG_NOERROR; /* We already checked it. */
2740 while (entry++->more);
6291ee3c 2741 }
e40a38b3 2742
d8f73de8 2743 subexp_num = dfa->nodes[bkref_node].opr.idx;
6291ee3c
UD		 2744
2745 /* For each sub expression */
2746 for (sub_top_idx = 0; sub_top_idx < mctx->nsub_tops; ++sub_top_idx)
2747 {
2748 reg_errcode_t err;
2749 re_sub_match_top_t *sub_top = mctx->sub_tops[sub_top_idx];
2750 re_sub_match_last_t *sub_last;
7c1be3ec 2751 int sub_last_idx, sl_str, bkref_str_off;
6291ee3c
UD		 2752
2753 if (dfa->nodes[sub_top->node].opr.idx != subexp_num)
2754 continue; /* It isn't related. */
2755
2756 sl_str = sub_top->str_idx;
7c1be3ec 2757 bkref_str_off = bkref_str_idx;
6291ee3c
UD		 2758 /* At first, check the last node of sub expressions we already
2759 evaluated. */
2760 for (sub_last_idx = 0; sub_last_idx < sub_top->nlasts; ++sub_last_idx)
2761 {
2762 int sl_str_diff;
2763 sub_last = sub_top->lasts[sub_last_idx];
2764 sl_str_diff = sub_last->str_idx - sl_str;
2765 /* The matched string by the sub expression match with the substring
2766 at the back reference? */
c1baba0f
UD		 2767 if (sl_str_diff > 0)
2768 {
2769 if (BE (bkref_str_off + sl_str_diff > mctx->input.valid_len, 0))
2770 {
2771 /* Not enough chars for a successful match. */
2772 if (bkref_str_off + sl_str_diff > mctx->input.len)
2773 break;
2774
2775 err = clean_state_log_if_needed (mctx,
2776 bkref_str_off
2777 + sl_str_diff);
2778 if (BE (err != REG_NOERROR, 0))
2779 return err;
2780 buf = (const char *) re_string_get_buffer (&mctx->input);
2781 }
2782 if (memcmp (buf + bkref_str_off, buf + sl_str, sl_str_diff) != 0)
01ed6ceb
UD		 2783 /* We don't need to search this sub expression any more. */
2784 break;
c1baba0f 2785 }
7c1be3ec 2786 bkref_str_off += sl_str_diff;
6291ee3c 2787 sl_str += sl_str_diff;
e3a87852 2788 err = get_subexp_sub (mctx, sub_top, sub_last, bkref_node,
6291ee3c 2789 bkref_str_idx);
3ee363e2 2790
7c1be3ec
UD		 2791 /* Reload buf, since the preceding call might have reallocated
2792 the buffer. */
56b168be 2793 buf = (const char *) re_string_get_buffer (&mctx->input);
3ee363e2 2794
6291ee3c
UD		 2795 if (err == REG_NOMATCH)
2796 continue;
2797 if (BE (err != REG_NOERROR, 0))
2798 return err;
2799 }
7c1be3ec 2800
6291ee3c
UD		 2801 if (sub_last_idx < sub_top->nlasts)
2802 continue;
2803 if (sub_last_idx > 0)
2804 ++sl_str;
2805 /* Then, search for the other last nodes of the sub expression. */
2806 for (; sl_str <= bkref_str_idx; ++sl_str)
2807 {
2808 int cls_node, sl_str_off;
fe9434bb 2809 const re_node_set *nodes;
6291ee3c
UD		 2810 sl_str_off = sl_str - sub_top->str_idx;
2811 /* The matched string by the sub expression match with the substring
2812 at the back reference? */
c1baba0f
UD		 2813 if (sl_str_off > 0)
2814 {
2815 if (BE (bkref_str_off >= mctx->input.valid_len, 0))
2816 {
2817 /* If we are at the end of the input, we cannot match. */
2818 if (bkref_str_off >= mctx->input.len)
2819 break;
2820
2821 err = extend_buffers (mctx);
2822 if (BE (err != REG_NOERROR, 0))
2823 return err;
2824
2825 buf = (const char *) re_string_get_buffer (&mctx->input);
2826 }
2827 if (buf [bkref_str_off++] != buf[sl_str - 1])
2828 break; /* We don't need to search this sub expression
2829 any more. */
2830 }
6291ee3c
UD		 2831 if (mctx->state_log[sl_str] == NULL)
2832 continue;
2833 /* Does this state have a ')' of the sub expression? */
2834 nodes = &mctx->state_log[sl_str]->nodes;
01ed6ceb
UD		 2835 cls_node = find_subexp_node (dfa, nodes, subexp_num,
2836 OP_CLOSE_SUBEXP);
6291ee3c
UD		 2837 if (cls_node == -1)
2838 continue; /* No. */
2839 if (sub_top->path == NULL)
2840 {
2841 sub_top->path = calloc (sizeof (state_array_t),
2842 sl_str - sub_top->str_idx + 1);
2843 if (sub_top->path == NULL)
2844 return REG_ESPACE;
2845 }
2846 /* Can the OP_OPEN_SUBEXP node arrive the OP_CLOSE_SUBEXP node
2847 in the current context? */
e3a87852 2848 err = check_arrival (mctx, sub_top->path, sub_top->node,
01ed6ceb
UD		 2849 sub_top->str_idx, cls_node, sl_str,
2850 OP_CLOSE_SUBEXP);
6291ee3c
UD		 2851 if (err == REG_NOMATCH)
2852 continue;
2853 if (BE (err != REG_NOERROR, 0))
2854 return err;
2855 sub_last = match_ctx_add_sublast (sub_top, cls_node, sl_str);
2856 if (BE (sub_last == NULL, 0))
2857 return REG_ESPACE;
e3a87852 2858 err = get_subexp_sub (mctx, sub_top, sub_last, bkref_node,
6291ee3c
UD		 2859 bkref_str_idx);
2860 if (err == REG_NOMATCH)
2861 continue;
2862 }
2863 }
2864 return REG_NOERROR;
2865}
2866
2867/* Helper functions for get_subexp(). */
2868
2869/* Check SUB_LAST can arrive to the back reference BKREF_NODE at BKREF_STR.
2870 If it can arrive, register the sub expression expressed with SUB_TOP
2871 and SUB_LAST. */
2872
2873static reg_errcode_t
a334319f
UD		 2874get_subexp_sub (mctx, sub_top, sub_last, bkref_node, bkref_str)
2875 re_match_context_t *mctx;
2876 const re_sub_match_top_t *sub_top;
2877 re_sub_match_last_t *sub_last;
2878 int bkref_node, bkref_str;
6291ee3c
UD		 2879{
2880 reg_errcode_t err;
2881 int to_idx;
2882 /* Can the subexpression arrive the back reference? */
e3a87852 2883 err = check_arrival (mctx, &sub_last->path, sub_last->node,
01ed6ceb
UD		 2884 sub_last->str_idx, bkref_node, bkref_str,
2885 OP_OPEN_SUBEXP);
6291ee3c
UD		 2886 if (err != REG_NOERROR)
2887 return err;
2888 err = match_ctx_add_entry (mctx, bkref_node, bkref_str, sub_top->str_idx,
2889 sub_last->str_idx);
2890 if (BE (err != REG_NOERROR, 0))
2891 return err;
2892 to_idx = bkref_str + sub_last->str_idx - sub_top->str_idx;
c1baba0f 2893 return clean_state_log_if_needed (mctx, to_idx);
6291ee3c
UD		 2894}
2895
2896/* Find the first node which is '(' or ')' and whose index is SUBEXP_IDX.
2897 Search '(' if FL_OPEN, or search ')' otherwise.
2898 TODO: This function isn't efficient...
2899 Because there might be more than one nodes whose types are
2900 OP_OPEN_SUBEXP and whose index is SUBEXP_IDX, we must check all
2901 nodes.
2902 E.g. RE: (a){2} */
2903
2904static int
a334319f
UD		 2905find_subexp_node (dfa, nodes, subexp_idx, type)
2906 const re_dfa_t *dfa;
2907 const re_node_set *nodes;
2908 int subexp_idx, type;
6291ee3c
UD		 2909{
2910 int cls_idx;
2911 for (cls_idx = 0; cls_idx < nodes->nelem; ++cls_idx)
2912 {
2913 int cls_node = nodes->elems[cls_idx];
fe9434bb 2914 const re_token_t *node = dfa->nodes + cls_node;
0ce7f49c 2915 if (node->type == type
6291ee3c
UD		 2916 && node->opr.idx == subexp_idx)
2917 return cls_node;
2918 }
2919 return -1;
2920}
2921
2922/* Check whether the node TOP_NODE at TOP_STR can arrive to the node
2923 LAST_NODE at LAST_STR. We record the path onto PATH since it will be
2924 heavily reused.
2925 Return REG_NOERROR if it can arrive, or REG_NOMATCH otherwise. */
2926
2927static reg_errcode_t
a334319f
UD		 2928check_arrival (mctx, path, top_node, top_str, last_node, last_str,
2929 type)
2930 re_match_context_t *mctx;
2931 state_array_t *path;
2932 int top_node, top_str, last_node, last_str, type;
6291ee3c 2933{
6efbd82c 2934 const re_dfa_t *const dfa = mctx->dfa;
c0c9615c 2935 reg_errcode_t err = REG_NOERROR;
6291ee3c
UD		 2936 int subexp_num, backup_cur_idx, str_idx, null_cnt;
2937 re_dfastate_t *cur_state = NULL;
2938 re_node_set *cur_nodes, next_nodes;
2939 re_dfastate_t **backup_state_log;
2940 unsigned int context;
2941
2942 subexp_num = dfa->nodes[top_node].opr.idx;
2943 /* Extend the buffer if we need. */
951d6408 2944 if (BE (path->alloc < last_str + mctx->max_mb_elem_len + 1, 0))
6291ee3c
UD		 2945 {
2946 re_dfastate_t **new_array;
2947 int old_alloc = path->alloc;
2948 path->alloc += last_str + mctx->max_mb_elem_len + 1;
2949 new_array = re_realloc (path->array, re_dfastate_t *, path->alloc);
6efbd82c 2950 if (BE (new_array == NULL, 0))
951d6408
UD		 2951 {
2952 path->alloc = old_alloc;
2953 return REG_ESPACE;
2954 }
6291ee3c
UD		 2955 path->array = new_array;
2956 memset (new_array + old_alloc, '\0',
2957 sizeof (re_dfastate_t *) * (path->alloc - old_alloc));
2958 }
2959
a334319f 2960 str_idx = path->next_idx == 0 ? top_str : path->next_idx;
6291ee3c
UD		 2961
2962 /* Temporary modify MCTX. */
2963 backup_state_log = mctx->state_log;
56b168be 2964 backup_cur_idx = mctx->input.cur_idx;
6291ee3c 2965 mctx->state_log = path->array;
56b168be 2966 mctx->input.cur_idx = str_idx;
6291ee3c
UD		 2967
2968 /* Setup initial node set. */
56b168be 2969 context = re_string_context_at (&mctx->input, str_idx - 1, mctx->eflags);
6291ee3c
UD		 2970 if (str_idx == top_str)
2971 {
2972 err = re_node_set_init_1 (&next_nodes, top_node);
2973 if (BE (err != REG_NOERROR, 0))
2974 return err;
0ce7f49c 2975 err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
6291ee3c
UD		 2976 if (BE (err != REG_NOERROR, 0))
2977 {
2978 re_node_set_free (&next_nodes);
2979 return err;
2980 }
2981 }
2982 else
2983 {
2984 cur_state = mctx->state_log[str_idx];
2985 if (cur_state && cur_state->has_backref)
2986 {
2987 err = re_node_set_init_copy (&next_nodes, &cur_state->nodes);
6efbd82c 2988 if (BE (err != REG_NOERROR, 0))
6291ee3c
UD		 2989 return err;
2990 }
2991 else
2992 re_node_set_init_empty (&next_nodes);
2993 }
2994 if (str_idx == top_str || (cur_state && cur_state->has_backref))
2995 {
2996 if (next_nodes.nelem)
2997 {
d2c38eb3 2998 err = expand_bkref_cache (mctx, &next_nodes, str_idx,
0ce7f49c 2999 subexp_num, type);
6efbd82c 3000 if (BE (err != REG_NOERROR, 0))
6291ee3c
UD		 3001 {
3002 re_node_set_free (&next_nodes);
3003 return err;
3004 }
3005 }
3006 cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
3007 if (BE (cur_state == NULL && err != REG_NOERROR, 0))
3008 {
3009 re_node_set_free (&next_nodes);
3010 return err;
3011 }
3012 mctx->state_log[str_idx] = cur_state;
3013 }
3014
3015 for (null_cnt = 0; str_idx < last_str && null_cnt <= mctx->max_mb_elem_len;)
3016 {
3017 re_node_set_empty (&next_nodes);
3018 if (mctx->state_log[str_idx + 1])
3019 {
3020 err = re_node_set_merge (&next_nodes,
3021 &mctx->state_log[str_idx + 1]->nodes);
3022 if (BE (err != REG_NOERROR, 0))
3023 {
3024 re_node_set_free (&next_nodes);
3025 return err;
3026 }
3027 }
3028 if (cur_state)
3029 {
e3a87852 3030 err = check_arrival_add_next_nodes (mctx, str_idx,
6efbd82c
UD		 3031 &cur_state->non_eps_nodes,
3032 &next_nodes);
6291ee3c
UD		 3033 if (BE (err != REG_NOERROR, 0))
3034 {
3035 re_node_set_free (&next_nodes);
3036 return err;
3037 }
3038 }
3039 ++str_idx;
3040 if (next_nodes.nelem)
3041 {
0ce7f49c 3042 err = check_arrival_expand_ecl (dfa, &next_nodes, subexp_num, type);
6291ee3c
UD		 3043 if (BE (err != REG_NOERROR, 0))
3044 {
3045 re_node_set_free (&next_nodes);
3046 return err;
3047 }
d2c38eb3 3048 err = expand_bkref_cache (mctx, &next_nodes, str_idx,
0ce7f49c 3049 subexp_num, type);
6efbd82c 3050 if (BE (err != REG_NOERROR, 0))
6291ee3c
UD		 3051 {
3052 re_node_set_free (&next_nodes);
3053 return err;
3054 }
3055 }
56b168be 3056 context = re_string_context_at (&mctx->input, str_idx - 1, mctx->eflags);
6291ee3c
UD		 3057 cur_state = re_acquire_state_context (&err, dfa, &next_nodes, context);
3058 if (BE (cur_state == NULL && err != REG_NOERROR, 0))
3059 {
3060 re_node_set_free (&next_nodes);
3061 return err;
3062 }
3063 mctx->state_log[str_idx] = cur_state;
3064 null_cnt = cur_state == NULL ? null_cnt + 1 : 0;
3065 }
3066 re_node_set_free (&next_nodes);
3067 cur_nodes = (mctx->state_log[last_str] == NULL ? NULL
3068 : &mctx->state_log[last_str]->nodes);
3069 path->next_idx = str_idx;
3070
3071 /* Fix MCTX. */
3072 mctx->state_log = backup_state_log;
56b168be 3073 mctx->input.cur_idx = backup_cur_idx;
6291ee3c 3074
6291ee3c 3075 /* Then check the current node set has the node LAST_NODE. */
c0d5034e
UD		 3076 if (cur_nodes != NULL && re_node_set_contains (cur_nodes, last_node))
3077 return REG_NOERROR;
3078
3079 return REG_NOMATCH;
6291ee3c
UD		 3080}
3081
3082/* Helper functions for check_arrival. */
3083
3084/* Calculate the destination nodes of CUR_NODES at STR_IDX, and append them
3085 to NEXT_NODES.
3086 TODO: This function is similar to the functions transit_state*(),
3087 however this function has many additional works.
3088 Can't we unify them? */
3089
3090static reg_errcode_t
a334319f
UD		 3091check_arrival_add_next_nodes (mctx, str_idx, cur_nodes, next_nodes)
3092 re_match_context_t *mctx;
3093 int str_idx;
3094 re_node_set *cur_nodes, *next_nodes;
6291ee3c 3095{
c42b4152 3096 const re_dfa_t *const dfa = mctx->dfa;
d2c38eb3 3097 int result;
6291ee3c 3098 int cur_idx;
c0c9615c 3099 reg_errcode_t err = REG_NOERROR;
6291ee3c
UD		 3100 re_node_set union_set;
3101 re_node_set_init_empty (&union_set);
3102 for (cur_idx = 0; cur_idx < cur_nodes->nelem; ++cur_idx)
3103 {
3104 int naccepted = 0;
3105 int cur_node = cur_nodes->elems[cur_idx];
a334319f 3106#ifdef DEBUG
02f3550c 3107 re_token_type_t type = dfa->nodes[cur_node].type;
5cf1ec52
UD		 3108 assert (!IS_EPSILON_NODE (type));
3109#endif
6291ee3c
UD		 3110#ifdef RE_ENABLE_I18N
3111 /* If the node may accept `multi byte'. */
02f3550c 3112 if (dfa->nodes[cur_node].accept_mb)
6291ee3c 3113 {
56b168be 3114 naccepted = check_node_accept_bytes (dfa, cur_node, &mctx->input,
6291ee3c
UD		 3115 str_idx);
3116 if (naccepted > 1)
3117 {
3118 re_dfastate_t *dest_state;
3119 int next_node = dfa->nexts[cur_node];
3120 int next_idx = str_idx + naccepted;
3121 dest_state = mctx->state_log[next_idx];
3122 re_node_set_empty (&union_set);
3123 if (dest_state)
3124 {
3125 err = re_node_set_merge (&union_set, &dest_state->nodes);
3126 if (BE (err != REG_NOERROR, 0))
3127 {
3128 re_node_set_free (&union_set);
3129 return err;
3130 }
6291ee3c 3131 }
d2c38eb3
UD		 3132 result = re_node_set_insert (&union_set, next_node);
3133 if (BE (result < 0, 0))
6291ee3c 3134 {
44777771
UD		 3135 re_node_set_free (&union_set);
3136 return REG_ESPACE;
6291ee3c
UD		 3137 }
3138 mctx->state_log[next_idx] = re_acquire_state (&err, dfa,
3139 &union_set);
3140 if (BE (mctx->state_log[next_idx] == NULL
3141 && err != REG_NOERROR, 0))
3142 {
3143 re_node_set_free (&union_set);
3144 return err;
3145 }
3146 }
3147 }
3148#endif /* RE_ENABLE_I18N */
3149 if (naccepted
e3a87852 3150 || check_node_accept (mctx, dfa->nodes + cur_node, str_idx))
6291ee3c 3151 {
d2c38eb3
UD		 3152 result = re_node_set_insert (next_nodes, dfa->nexts[cur_node]);
3153 if (BE (result < 0, 0))
6291ee3c
UD		 3154 {
3155 re_node_set_free (&union_set);
3156 return REG_ESPACE;
3157 }
3158 }
3159 }
3160 re_node_set_free (&union_set);
3161 return REG_NOERROR;
3162}
3163
3164/* For all the nodes in CUR_NODES, add the epsilon closures of them to
3165 CUR_NODES, however exclude the nodes which are:
3166 - inside the sub expression whose number is EX_SUBEXP, if FL_OPEN.
3167 - out of the sub expression whose number is EX_SUBEXP, if !FL_OPEN.
3168*/
3169
3170static reg_errcode_t
a334319f 3171check_arrival_expand_ecl (dfa, cur_nodes, ex_subexp, type)
6efbd82c 3172 const re_dfa_t *dfa;
a334319f
UD		 3173 re_node_set *cur_nodes;
3174 int ex_subexp, type;
6291ee3c
UD		 3175{
3176 reg_errcode_t err;
3177 int idx, outside_node;
3178 re_node_set new_nodes;
3179#ifdef DEBUG
3180 assert (cur_nodes->nelem);
3181#endif
3182 err = re_node_set_alloc (&new_nodes, cur_nodes->nelem);
3183 if (BE (err != REG_NOERROR, 0))
3184 return err;
3185 /* Create a new node set NEW_NODES with the nodes which are epsilon
3186 closures of the node in CUR_NODES. */
3187
3188 for (idx = 0; idx < cur_nodes->nelem; ++idx)
3189 {
3190 int cur_node = cur_nodes->elems[idx];
6efbd82c 3191 const re_node_set *eclosure = dfa->eclosures + cur_node;
0ce7f49c 3192 outside_node = find_subexp_node (dfa, eclosure, ex_subexp, type);
6291ee3c
UD		 3193 if (outside_node == -1)
3194 {
3195 /* There are no problematic nodes, just merge them. */
3196 err = re_node_set_merge (&new_nodes, eclosure);
3197 if (BE (err != REG_NOERROR, 0))
3198 {
3199 re_node_set_free (&new_nodes);
3200 return err;
3201 }
3202 }
3203 else
3204 {
3205 /* There are problematic nodes, re-calculate incrementally. */
3206 err = check_arrival_expand_ecl_sub (dfa, &new_nodes, cur_node,
0ce7f49c 3207 ex_subexp, type);
6291ee3c
UD		 3208 if (BE (err != REG_NOERROR, 0))
3209 {
3210 re_node_set_free (&new_nodes);
3211 return err;
3212 }
3213 }
3214 }
3215 re_node_set_free (cur_nodes);
3216 *cur_nodes = new_nodes;
3217 return REG_NOERROR;
3218}
3219
3220/* Helper function for check_arrival_expand_ecl.
3221 Check incrementally the epsilon closure of TARGET, and if it isn't
3222 problematic append it to DST_NODES. */
3223
3224static reg_errcode_t
a334319f 3225check_arrival_expand_ecl_sub (dfa, dst_nodes, target, ex_subexp, type)
6efbd82c 3226 const re_dfa_t *dfa;
a334319f
UD		 3227 int target, ex_subexp, type;
3228 re_node_set *dst_nodes;
6291ee3c 3229{
0ce7f49c 3230 int cur_node;
6291ee3c
UD		 3231 for (cur_node = target; !re_node_set_contains (dst_nodes, cur_node);)
3232 {
3233 int err;
6291ee3c 3234
0ce7f49c 3235 if (dfa->nodes[cur_node].type == type
6291ee3c
UD		 3236 && dfa->nodes[cur_node].opr.idx == ex_subexp)
3237 {
0ce7f49c 3238 if (type == OP_CLOSE_SUBEXP)
6291ee3c
UD		 3239 {
3240 err = re_node_set_insert (dst_nodes, cur_node);
3241 if (BE (err == -1, 0))
3242 return REG_ESPACE;
3243 }
3244 break;
3245 }
3246 err = re_node_set_insert (dst_nodes, cur_node);
3247 if (BE (err == -1, 0))
3248 return REG_ESPACE;
3249 if (dfa->edests[cur_node].nelem == 0)
3250 break;
3251 if (dfa->edests[cur_node].nelem == 2)
3252 {
3253 err = check_arrival_expand_ecl_sub (dfa, dst_nodes,
3254 dfa->edests[cur_node].elems[1],
0ce7f49c 3255 ex_subexp, type);
6291ee3c
UD		 3256 if (BE (err != REG_NOERROR, 0))
3257 return err;
3258 }
3259 cur_node = dfa->edests[cur_node].elems[0];
3260 }
3261 return REG_NOERROR;
3262}
3263
3264
3265/* For all the back references in the current state, calculate the
3266 destination of the back references by the appropriate entry
3267 in MCTX->BKREF_ENTS. */
3268
3269static reg_errcode_t
a334319f
UD		 3270expand_bkref_cache (mctx, cur_nodes, cur_str, subexp_num,
3271 type)
3272 re_match_context_t *mctx;
3273 int cur_str, subexp_num, type;
3274 re_node_set *cur_nodes;
6291ee3c 3275{
76b864c8 3276 const re_dfa_t *const dfa = mctx->dfa;
6291ee3c 3277 reg_errcode_t err;
e40a38b3
UD		 3278 int cache_idx_start = search_cur_bkref_entry (mctx, cur_str);
3279 struct re_backref_cache_entry *ent;
6291ee3c 3280
e40a38b3
UD		 3281 if (cache_idx_start == -1)
3282 return REG_NOERROR;
3283
3284 restart:
3285 ent = mctx->bkref_ents + cache_idx_start;
3286 do
6291ee3c
UD		 3287 {
3288 int to_idx, next_node;
e40a38b3 3289
6291ee3c
UD		 3290 /* Is this entry ENT is appropriate? */
3291 if (!re_node_set_contains (cur_nodes, ent->node))
3292 continue; /* No. */
3293
3294 to_idx = cur_str + ent->subexp_to - ent->subexp_from;
3295 /* Calculate the destination of the back reference, and append it
3296 to MCTX->STATE_LOG. */
3297 if (to_idx == cur_str)
3298 {
3299 /* The backreference did epsilon transit, we must re-check all the
3300 node in the current state. */
3301 re_node_set new_dests;
3302 reg_errcode_t err2, err3;
3303 next_node = dfa->edests[ent->node].elems[0];
3304 if (re_node_set_contains (cur_nodes, next_node))
3305 continue;
3306 err = re_node_set_init_1 (&new_dests, next_node);
0ce7f49c 3307 err2 = check_arrival_expand_ecl (dfa, &new_dests, subexp_num, type);
6291ee3c
UD		 3308 err3 = re_node_set_merge (cur_nodes, &new_dests);
3309 re_node_set_free (&new_dests);
3310 if (BE (err != REG_NOERROR || err2 != REG_NOERROR
3311 || err3 != REG_NOERROR, 0))
3312 {
3313 err = (err != REG_NOERROR ? err
3314 : (err2 != REG_NOERROR ? err2 : err3));
3315 return err;
3316 }
3317 /* TODO: It is still inefficient... */
e40a38b3 3318 goto restart;
6291ee3c
UD		 3319 }
3320 else
3321 {
3322 re_node_set union_set;
3323 next_node = dfa->nexts[ent->node];
3324 if (mctx->state_log[to_idx])
3325 {
3326 int ret;
3327 if (re_node_set_contains (&mctx->state_log[to_idx]->nodes,
3328 next_node))
3329 continue;
3330 err = re_node_set_init_copy (&union_set,
3331 &mctx->state_log[to_idx]->nodes);
3332 ret = re_node_set_insert (&union_set, next_node);
3333 if (BE (err != REG_NOERROR || ret < 0, 0))
3334 {
3335 re_node_set_free (&union_set);
3336 err = err != REG_NOERROR ? err : REG_ESPACE;
3337 return err;
3338 }
3339 }
3340 else
3341 {
3342 err = re_node_set_init_1 (&union_set, next_node);
3343 if (BE (err != REG_NOERROR, 0))
3344 return err;
3345 }
3346 mctx->state_log[to_idx] = re_acquire_state (&err, dfa, &union_set);
3347 re_node_set_free (&union_set);
3348 if (BE (mctx->state_log[to_idx] == NULL
3349 && err != REG_NOERROR, 0))
3350 return err;
3351 }
3352 }
e40a38b3 3353 while (ent++->more);
6291ee3c
UD		 3354 return REG_NOERROR;
3355}
3356
3357/* Build transition table for the state.
ab4b89fe 3358 Return 1 if succeeded, otherwise return NULL. */
6291ee3c 3359
ab4b89fe 3360static int
a334319f 3361build_trtable (dfa, state)
76b864c8
UD		 3362 const re_dfa_t *dfa;
3363 re_dfastate_t *state;
6291ee3c
UD		 3364{
3365 reg_errcode_t err;
ab4b89fe 3366 int i, j, ch, need_word_trtable = 0;
2c05d33f
UD		 3367 bitset_word_t elem, mask;
3368 bool dests_node_malloced = false;
3369 bool dest_states_malloced = false;
6291ee3c
UD		 3370 int ndests; /* Number of the destination states from `state'. */
3371 re_dfastate_t **trtable;
3372 re_dfastate_t **dest_states = NULL, **dest_states_word, **dest_states_nl;
3373 re_node_set follows, *dests_node;
2c05d33f
UD		 3374 bitset_t *dests_ch;
3375 bitset_t acceptable;
3376
3377 struct dests_alloc
3378 {
3379 re_node_set dests_node[SBC_MAX];
3380 bitset_t dests_ch[SBC_MAX];
3381 } *dests_alloc;
3b0bdc72
UD		 3382
3383 /* We build DFA states which corresponds to the destination nodes
3384 from `state'. `dests_node[i]' represents the nodes which i-th
3385 destination state contains, and `dests_ch[i]' represents the
3386 characters which i-th destination state accepts. */
2c05d33f
UD		 3387 if (__libc_use_alloca (sizeof (struct dests_alloc)))
3388 dests_alloc = (struct dests_alloc *) alloca (sizeof (struct dests_alloc));
05dab910 3389 else
05dab910 3390 {
2c05d33f
UD		 3391 dests_alloc = re_malloc (struct dests_alloc, 1);
3392 if (BE (dests_alloc == NULL, 0))
ab4b89fe 3393 return 0;
2c05d33f 3394 dests_node_malloced = true;
05dab910 3395 }
2c05d33f
UD		 3396 dests_node = dests_alloc->dests_node;
3397 dests_ch = dests_alloc->dests_ch;
3b0bdc72
UD		 3398
3399 /* Initialize transiton table. */
ab4b89fe 3400 state->word_trtable = state->trtable = NULL;
3b0bdc72
UD		 3401
3402 /* At first, group all nodes belonging to `state' into several
3403 destinations. */
56b168be 3404 ndests = group_nodes_into_DFAstates (dfa, state, dests_node, dests_ch);
bc15410e 3405 if (BE (ndests <= 0, 0))
3b0bdc72 3406 {
05dab910 3407 if (dests_node_malloced)
2c05d33f 3408 free (dests_alloc);
ab4b89fe 3409 /* Return 0 in case of an error, 1 otherwise. */
05dab910 3410 if (ndests == 0)
c13c99fa 3411 {
3ce12656 3412 state->trtable = (re_dfastate_t **)
ab4b89fe
UD		 3413 calloc (sizeof (re_dfastate_t *), SBC_MAX);
3414 return 1;
c13c99fa 3415 }
ab4b89fe 3416 return 0;
3b0bdc72
UD		 3417 }
3418
a9388965 3419 err = re_node_set_alloc (&follows, ndests + 1);
05dab910
RM		 3420 if (BE (err != REG_NOERROR, 0))
3421 goto out_free;
3422
2c05d33f 3423 if (__libc_use_alloca ((sizeof (re_node_set) + sizeof (bitset_t)) * SBC_MAX
05dab910
RM		 3424 + ndests * 3 * sizeof (re_dfastate_t *)))
3425 dest_states = (re_dfastate_t **)
ab4b89fe 3426 alloca (ndests * 3 * sizeof (re_dfastate_t *));
05dab910 3427 else
05dab910
RM		 3428 {
3429 dest_states = (re_dfastate_t **)
ab4b89fe 3430 malloc (ndests * 3 * sizeof (re_dfastate_t *));
05dab910
RM		 3431 if (BE (dest_states == NULL, 0))
3432 {
3433out_free:
3434 if (dest_states_malloced)
3435 free (dest_states);
3436 re_node_set_free (&follows);
3437 for (i = 0; i < ndests; ++i)
3438 re_node_set_free (dests_node + i);
05dab910 3439 if (dests_node_malloced)
2c05d33f 3440 free (dests_alloc);
ab4b89fe 3441 return 0;
05dab910 3442 }
2c05d33f 3443 dest_states_malloced = true;
05dab910
RM		 3444 }
3445 dest_states_word = dest_states + ndests;
3446 dest_states_nl = dest_states_word + ndests;
3447 bitset_empty (acceptable);
a9388965 3448
3b0bdc72
UD		 3449 /* Then build the states for all destinations. */
3450 for (i = 0; i < ndests; ++i)
3451 {
3452 int next_node;
3453 re_node_set_empty (&follows);
3454 /* Merge the follows of this destination states. */
3455 for (j = 0; j < dests_node[i].nelem; ++j)
15a7d175
UD		 3456 {
3457 next_node = dfa->nexts[dests_node[i].elems[j]];
3458 if (next_node != -1)
3459 {
3460 err = re_node_set_merge (&follows, dfa->eclosures + next_node);
3461 if (BE (err != REG_NOERROR, 0))
05dab910 3462 goto out_free;
15a7d175
UD		 3463 }
3464 }
a9388965 3465 dest_states[i] = re_acquire_state_context (&err, dfa, &follows, 0);
bc15410e 3466 if (BE (dest_states[i] == NULL && err != REG_NOERROR, 0))
15a7d175 3467 goto out_free;
3b0bdc72 3468 /* If the new state has context constraint,
15a7d175 3469 build appropriate states for these contexts. */
3b0bdc72 3470 if (dest_states[i]->has_constraint)
15a7d175
UD		 3471 {
3472 dest_states_word[i] = re_acquire_state_context (&err, dfa, &follows,
3473 CONTEXT_WORD);
3474 if (BE (dest_states_word[i] == NULL && err != REG_NOERROR, 0))
3475 goto out_free;
3ce12656 3476
ab4b89fe
UD		 3477 if (dest_states[i] != dest_states_word[i] && dfa->mb_cur_max > 1)
3478 need_word_trtable = 1;
3ce12656 3479
15a7d175
UD		 3480 dest_states_nl[i] = re_acquire_state_context (&err, dfa, &follows,
3481 CONTEXT_NEWLINE);
3482 if (BE (dest_states_nl[i] == NULL && err != REG_NOERROR, 0))
3483 goto out_free;
3ce12656 3484 }
3b0bdc72 3485 else
15a7d175
UD		 3486 {
3487 dest_states_word[i] = dest_states[i];
3488 dest_states_nl[i] = dest_states[i];
3489 }
3b0bdc72
UD		 3490 bitset_merge (acceptable, dests_ch[i]);
3491 }
3492
ab4b89fe 3493 if (!BE (need_word_trtable, 0))
3ce12656
UD		 3494 {
3495 /* We don't care about whether the following character is a word
3496 character, or we are in a single-byte character set so we can
3497 discern by looking at the character code: allocate a
3498 256-entry transition table. */
ab4b89fe
UD		 3499 trtable = state->trtable =
3500 (re_dfastate_t **) calloc (sizeof (re_dfastate_t *), SBC_MAX);
3ce12656
UD		 3501 if (BE (trtable == NULL, 0))
3502 goto out_free;
3503
3504 /* For all characters ch...: */
2c05d33f
UD		 3505 for (i = 0; i < BITSET_WORDS; ++i)
3506 for (ch = i * BITSET_WORD_BITS, elem = acceptable[i], mask = 1;
3ce12656
UD		 3507 elem;
3508 mask <<= 1, elem >>= 1, ++ch)
3509 if (BE (elem & 1, 0))
3510 {
3511 /* There must be exactly one destination which accepts
3512 character ch. See group_nodes_into_DFAstates. */
3513 for (j = 0; (dests_ch[j][i] & mask) == 0; ++j)
3514 ;
6b6557e8 3515
3ce12656 3516 /* j-th destination accepts the word character ch. */
56b168be 3517 if (dfa->word_char[i] & mask)
3ce12656
UD		 3518 trtable[ch] = dest_states_word[j];
3519 else
3520 trtable[ch] = dest_states[j];
3521 }
3522 }
3523 else
3524 {
3525 /* We care about whether the following character is a word
3526 character, and we are in a multi-byte character set: discern
3527 by looking at the character code: build two 256-entry
3528 transition tables, one starting at trtable[0] and one
3529 starting at trtable[SBC_MAX]. */
ab4b89fe
UD		 3530 trtable = state->word_trtable =
3531 (re_dfastate_t **) calloc (sizeof (re_dfastate_t *), 2 * SBC_MAX);
3ce12656
UD		 3532 if (BE (trtable == NULL, 0))
3533 goto out_free;
6b6557e8 3534
3ce12656 3535 /* For all characters ch...: */
2c05d33f
UD		 3536 for (i = 0; i < BITSET_WORDS; ++i)
3537 for (ch = i * BITSET_WORD_BITS, elem = acceptable[i], mask = 1;
3ce12656
UD		 3538 elem;
3539 mask <<= 1, elem >>= 1, ++ch)
3540 if (BE (elem & 1, 0))
3541 {
3542 /* There must be exactly one destination which accepts
3543 character ch. See group_nodes_into_DFAstates. */
3544 for (j = 0; (dests_ch[j][i] & mask) == 0; ++j)
3545 ;
6b6557e8 3546
3ce12656
UD		 3547 /* j-th destination accepts the word character ch. */
3548 trtable[ch] = dest_states[j];
3549 trtable[ch + SBC_MAX] = dest_states_word[j];
3550 }
3551 }
6b6557e8 3552
3b0bdc72 3553 /* new line */
c202c2c5
UD		 3554 if (bitset_contain (acceptable, NEWLINE_CHAR))
3555 {
3556 /* The current state accepts newline character. */
3ce12656
UD		 3557 for (j = 0; j < ndests; ++j)
3558 if (bitset_contain (dests_ch[j], NEWLINE_CHAR))
15a7d175
UD		 3559 {
3560 /* k-th destination accepts newline character. */
3ce12656 3561 trtable[NEWLINE_CHAR] = dest_states_nl[j];
ab4b89fe 3562 if (need_word_trtable)
3ce12656 3563 trtable[NEWLINE_CHAR + SBC_MAX] = dest_states_nl[j];
15a7d175
UD		 3564 /* There must be only one destination which accepts
3565 newline. See group_nodes_into_DFAstates. */
3566 break;
3567 }
c202c2c5 3568 }
3b0bdc72 3569
05dab910
RM		 3570 if (dest_states_malloced)
3571 free (dest_states);
3b0bdc72
UD		 3572
3573 re_node_set_free (&follows);
3574 for (i = 0; i < ndests; ++i)
3575 re_node_set_free (dests_node + i);
3576
05dab910 3577 if (dests_node_malloced)
2c05d33f 3578 free (dests_alloc);
3b0bdc72 3579
ab4b89fe 3580 return 1;
3b0bdc72
UD		 3581}
3582
3583/* Group all nodes belonging to STATE into several destinations.
3584 Then for all destinations, set the nodes belonging to the destination
3585 to DESTS_NODE[i] and set the characters accepted by the destination
3586 to DEST_CH[i]. This function return the number of destinations. */
3587
3588static int
a334319f 3589group_nodes_into_DFAstates (dfa, state, dests_node, dests_ch)
01ed6ceb
UD		 3590 const re_dfa_t *dfa;
3591 const re_dfastate_t *state;
3592 re_node_set *dests_node;
2c05d33f 3593 bitset_t *dests_ch;
3b0bdc72 3594{
a9388965 3595 reg_errcode_t err;
d2c38eb3 3596 int result;
3b0bdc72
UD		 3597 int i, j, k;
3598 int ndests; /* Number of the destinations from `state'. */
2c05d33f 3599 bitset_t accepts; /* Characters a node can accept. */
3b0bdc72
UD		 3600 const re_node_set *cur_nodes = &state->nodes;
3601 bitset_empty (accepts);
3602 ndests = 0;
3603
3604 /* For all the nodes belonging to `state', */
3605 for (i = 0; i < cur_nodes->nelem; ++i)
3606 {
3b0bdc72
UD		 3607 re_token_t *node = &dfa->nodes[cur_nodes->elems[i]];
3608 re_token_type_t type = node->type;
485d775d 3609 unsigned int constraint = node->constraint;
3b0bdc72
UD		 3610
3611 /* Enumerate all single byte character this node can accept. */
3612 if (type == CHARACTER)
15a7d175 3613 bitset_set (accepts, node->opr.c);
3b0bdc72 3614 else if (type == SIMPLE_BRACKET)
15a7d175
UD		 3615 {
3616 bitset_merge (accepts, node->opr.sbcset);
3617 }
3b0bdc72 3618 else if (type == OP_PERIOD)
15a7d175 3619 {
65e6becf
UD		 3620#ifdef RE_ENABLE_I18N
3621 if (dfa->mb_cur_max > 1)
3622 bitset_merge (accepts, dfa->sb_char);
3623 else
0ce7f49c 3624#endif
65e6becf 3625 bitset_set_all (accepts);
56b168be 3626 if (!(dfa->syntax & RE_DOT_NEWLINE))
15a7d175 3627 bitset_clear (accepts, '\n');
56b168be 3628 if (dfa->syntax & RE_DOT_NOT_NULL)
15a7d175
UD		 3629 bitset_clear (accepts, '\0');
3630 }
c0d5034e 3631#ifdef RE_ENABLE_I18N
ad7f28c2
UD		 3632 else if (type == OP_UTF8_PERIOD)
3633 {
2c05d33f 3634 memset (accepts, '\xff', sizeof (bitset_t) / 2);
56b168be 3635 if (!(dfa->syntax & RE_DOT_NEWLINE))
ad7f28c2 3636 bitset_clear (accepts, '\n');
56b168be 3637 if (dfa->syntax & RE_DOT_NOT_NULL)
ad7f28c2
UD		 3638 bitset_clear (accepts, '\0');
3639 }
c0d5034e 3640#endif
3b0bdc72 3641 else
15a7d175 3642 continue;
3b0bdc72
UD		 3643
3644 /* Check the `accepts' and sift the characters which are not
15a7d175 3645 match it the context. */
3b0bdc72 3646 if (constraint)
15a7d175 3647 {
15a7d175
UD		 3648 if (constraint & NEXT_NEWLINE_CONSTRAINT)
3649 {
2c05d33f 3650 bool accepts_newline = bitset_contain (accepts, NEWLINE_CHAR);
15a7d175
UD		 3651 bitset_empty (accepts);
3652 if (accepts_newline)
3653 bitset_set (accepts, NEWLINE_CHAR);
3654 else
3655 continue;
3656 }
66b110e8
UD		 3657 if (constraint & NEXT_ENDBUF_CONSTRAINT)
3658 {
3659 bitset_empty (accepts);
3660 continue;
3661 }
c13c99fa 3662
66b110e8 3663 if (constraint & NEXT_WORD_CONSTRAINT)
65e6becf 3664 {
2c05d33f 3665 bitset_word_t any_set = 0;
1cef7b3c
UD		 3666 if (type == CHARACTER && !node->word_char)
3667 {
3668 bitset_empty (accepts);
3669 continue;
3670 }
65e6becf
UD		 3671#ifdef RE_ENABLE_I18N
3672 if (dfa->mb_cur_max > 1)
2c05d33f 3673 for (j = 0; j < BITSET_WORDS; ++j)
457beec8 3674 any_set |= (accepts[j] &= (dfa->word_char[j] | ~dfa->sb_char[j]));
65e6becf
UD		 3675 else
3676#endif
2c05d33f 3677 for (j = 0; j < BITSET_WORDS; ++j)
457beec8
UD		 3678 any_set |= (accepts[j] &= dfa->word_char[j]);
3679 if (!any_set)
3680 continue;
65e6becf 3681 }
66b110e8 3682 if (constraint & NEXT_NOTWORD_CONSTRAINT)
65e6becf 3683 {
2c05d33f 3684 bitset_word_t any_set = 0;
1cef7b3c
UD		 3685 if (type == CHARACTER && node->word_char)
3686 {
3687 bitset_empty (accepts);
3688 continue;
3689 }
65e6becf
UD		 3690#ifdef RE_ENABLE_I18N
3691 if (dfa->mb_cur_max > 1)
2c05d33f 3692 for (j = 0; j < BITSET_WORDS; ++j)
457beec8 3693 any_set |= (accepts[j] &= ~(dfa->word_char[j] & dfa->sb_char[j]));
65e6becf
UD		 3694 else
3695#endif
2c05d33f 3696 for (j = 0; j < BITSET_WORDS; ++j)
457beec8
UD		 3697 any_set |= (accepts[j] &= ~dfa->word_char[j]);
3698 if (!any_set)
3699 continue;
65e6becf 3700 }
15a7d175 3701 }
3b0bdc72
UD		 3702
3703 /* Then divide `accepts' into DFA states, or create a new
457beec8 3704 state. Above, we make sure that accepts is not empty. */
3b0bdc72 3705 for (j = 0; j < ndests; ++j)
15a7d175 3706 {
2c05d33f
UD		 3707 bitset_t intersec; /* Intersection sets, see below. */
3708 bitset_t remains;
15a7d175 3709 /* Flags, see below. */
2c05d33f 3710 bitset_word_t has_intersec, not_subset, not_consumed;
15a7d175
UD		 3711
3712 /* Optimization, skip if this state doesn't accept the character. */
3713 if (type == CHARACTER && !bitset_contain (dests_ch[j], node->opr.c))
3714 continue;
3715
3716 /* Enumerate the intersection set of this state and `accepts'. */
3717 has_intersec = 0;
2c05d33f 3718 for (k = 0; k < BITSET_WORDS; ++k)
15a7d175
UD		 3719 has_intersec |= intersec[k] = accepts[k] & dests_ch[j][k];
3720 /* And skip if the intersection set is empty. */
3721 if (!has_intersec)
3722 continue;
3723
3724 /* Then check if this state is a subset of `accepts'. */
3725 not_subset = not_consumed = 0;
2c05d33f 3726 for (k = 0; k < BITSET_WORDS; ++k)
15a7d175
UD		 3727 {
3728 not_subset |= remains[k] = ~accepts[k] & dests_ch[j][k];
3729 not_consumed |= accepts[k] = accepts[k] & ~dests_ch[j][k];
3730 }
3731
3732 /* If this state isn't a subset of `accepts', create a
3733 new group state, which has the `remains'. */
3734 if (not_subset)
3735 {
3736 bitset_copy (dests_ch[ndests], remains);
3737 bitset_copy (dests_ch[j], intersec);
3738 err = re_node_set_init_copy (dests_node + ndests, &dests_node[j]);
3739 if (BE (err != REG_NOERROR, 0))
3740 goto error_return;
3741 ++ndests;
3742 }
3743
3744 /* Put the position in the current group. */
d2c38eb3
UD		 3745 result = re_node_set_insert (&dests_node[j], cur_nodes->elems[i]);
3746 if (BE (result < 0, 0))
15a7d175
UD		 3747 goto error_return;
3748
3749 /* If all characters are consumed, go to next node. */
3750 if (!not_consumed)
3751 break;
3752 }
3b0bdc72
UD		 3753 /* Some characters remain, create a new group. */
3754 if (j == ndests)
15a7d175
UD		 3755 {
3756 bitset_copy (dests_ch[ndests], accepts);
3757 err = re_node_set_init_1 (dests_node + ndests, cur_nodes->elems[i]);
3758 if (BE (err != REG_NOERROR, 0))
3759 goto error_return;
3760 ++ndests;
3761 bitset_empty (accepts);
3762 }
3b0bdc72
UD		 3763 }
3764 return ndests;
1b2c2628
UD		 3765 error_return:
3766 for (j = 0; j < ndests; ++j)
3767 re_node_set_free (dests_node + j);
3768 return -1;
3b0bdc72
UD		 3769}
3770
434d3784
UD		 3771#ifdef RE_ENABLE_I18N
3772/* Check how many bytes the node `dfa->nodes[node_idx]' accepts.
3773 Return the number of the bytes the node accepts.
3774 STR_IDX is the current index of the input string.
3775
3776 This function handles the nodes which can accept one character, or
3777 one collating element like '.', '[a-z]', opposite to the other nodes
3778 can only accept one byte. */
3b0bdc72
UD		 3779
3780static int
a334319f 3781check_node_accept_bytes (dfa, node_idx, input, str_idx)
c42b4152
UD		 3782 const re_dfa_t *dfa;
3783 int node_idx, str_idx;
3784 const re_string_t *input;
3b0bdc72 3785{
3b0bdc72 3786 const re_token_t *node = dfa->nodes + node_idx;
ad7f28c2 3787 int char_len, elem_len;
434d3784 3788 int i;
ad7f28c2
UD		 3789
3790 if (BE (node->type == OP_UTF8_PERIOD, 0))
3791 {
3792 unsigned char c = re_string_byte_at (input, str_idx), d;
3793 if (BE (c < 0xc2, 1))
3794 return 0;
3795
3796 if (str_idx + 2 > input->len)
3797 return 0;
3798
3799 d = re_string_byte_at (input, str_idx + 1);
3800 if (c < 0xe0)
3801 return (d < 0x80 || d > 0xbf) ? 0 : 2;
3802 else if (c < 0xf0)
3803 {
3804 char_len = 3;
3805 if (c == 0xe0 && d < 0xa0)
3806 return 0;
3807 }
3808 else if (c < 0xf8)
3809 {
3810 char_len = 4;
3811 if (c == 0xf0 && d < 0x90)
3812 return 0;
3813 }
3814 else if (c < 0xfc)
3815 {
3816 char_len = 5;
3817 if (c == 0xf8 && d < 0x88)
3818 return 0;
3819 }
3820 else if (c < 0xfe)
3821 {
3822 char_len = 6;
3823 if (c == 0xfc && d < 0x84)
3824 return 0;
3825 }
3826 else
3827 return 0;
3828
3829 if (str_idx + char_len > input->len)
3830 return 0;
3831
3832 for (i = 1; i < char_len; ++i)
3833 {
3834 d = re_string_byte_at (input, str_idx + i);
3835 if (d < 0x80 || d > 0xbf)
3836 return 0;
3837 }
3838 return char_len;
3839 }
3840
3841 char_len = re_string_char_size_at (input, str_idx);
3b0bdc72
UD		 3842 if (node->type == OP_PERIOD)
3843 {
ad7f28c2
UD		 3844 if (char_len <= 1)
3845 return 0;
3846 /* FIXME: I don't think this if is needed, as both '\n'
3847 and '\0' are char_len == 1. */
434d3784 3848 /* '.' accepts any one character except the following two cases. */
56b168be 3849 if ((!(dfa->syntax & RE_DOT_NEWLINE) &&
15a7d175 3850 re_string_byte_at (input, str_idx) == '\n') ||
56b168be 3851 ((dfa->syntax & RE_DOT_NOT_NULL) &&
15a7d175
UD		 3852 re_string_byte_at (input, str_idx) == '\0'))
3853 return 0;
3b0bdc72
UD		 3854 return char_len;
3855 }
ad7f28c2
UD		 3856
3857 elem_len = re_string_elem_size_at (input, str_idx);
6c2a04a7 3858 if ((elem_len <= 1 && char_len <= 1) || char_len == 0)
ad7f28c2
UD		 3859 return 0;
3860
3861 if (node->type == COMPLEX_BRACKET)
3b0bdc72
UD		 3862 {
3863 const re_charset_t *cset = node->opr.mbcset;
434d3784 3864# ifdef _LIBC
1c99f950
UD		 3865 const unsigned char *pin
3866 = ((const unsigned char *) re_string_get_buffer (input) + str_idx);
5f93cd52
UD		 3867 int j;
3868 uint32_t nrules;
434d3784
UD		 3869# endif /* _LIBC */
3870 int match_len = 0;
3871 wchar_t wc = ((cset->nranges || cset->nchar_classes || cset->nmbchars)
15a7d175 3872 ? re_string_wchar_at (input, str_idx) : 0);
434d3784
UD		 3873
3874 /* match with multibyte character? */
3875 for (i = 0; i < cset->nmbchars; ++i)
15a7d175
UD		 3876 if (wc == cset->mbchars[i])
3877 {
3878 match_len = char_len;
3879 goto check_node_accept_bytes_match;
3880 }
434d3784
UD		 3881 /* match with character_class? */
3882 for (i = 0; i < cset->nchar_classes; ++i)
15a7d175
UD		 3883 {
3884 wctype_t wt = cset->char_classes[i];
3885 if (__iswctype (wc, wt))
3886 {
3887 match_len = char_len;
3888 goto check_node_accept_bytes_match;
3889 }
3890 }
434d3784
UD		 3891
3892# ifdef _LIBC
5f93cd52 3893 nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
3b0bdc72 3894 if (nrules != 0)
15a7d175
UD		 3895 {
3896 unsigned int in_collseq = 0;
3897 const int32_t *table, *indirect;
3898 const unsigned char *weights, *extra;
3899 const char *collseqwc;
3900 int32_t idx;
3901 /* This #include defines a local function! */
434d3784 3902# include <locale/weight.h>
3b0bdc72 3903
15a7d175
UD		 3904 /* match with collating_symbol? */
3905 if (cset->ncoll_syms)
3906 extra = (const unsigned char *)
3907 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB);
3908 for (i = 0; i < cset->ncoll_syms; ++i)
3909 {
3910 const unsigned char *coll_sym = extra + cset->coll_syms[i];
3911 /* Compare the length of input collating element and
3912 the length of current collating element. */
3913 if (*coll_sym != elem_len)
3914 continue;
3915 /* Compare each bytes. */
3916 for (j = 0; j < *coll_sym; j++)
3917 if (pin[j] != coll_sym[1 + j])
3918 break;
3919 if (j == *coll_sym)
3920 {
3921 /* Match if every bytes is equal. */
3922 match_len = j;
3923 goto check_node_accept_bytes_match;
3924 }
3925 }
3926
3927 if (cset->nranges)
3928 {
3929 if (elem_len <= char_len)
3930 {
3931 collseqwc = _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQWC);
25337753 3932 in_collseq = __collseq_table_lookup (collseqwc, wc);
15a7d175
UD		 3933 }
3934 else
3935 in_collseq = find_collation_sequence_value (pin, elem_len);
3936 }
3937 /* match with range expression? */
3938 for (i = 0; i < cset->nranges; ++i)
3939 if (cset->range_starts[i] <= in_collseq
3940 && in_collseq <= cset->range_ends[i])
3941 {
3942 match_len = elem_len;
3943 goto check_node_accept_bytes_match;
3944 }
3945
3946 /* match with equivalence_class? */
3947 if (cset->nequiv_classes)
3948 {
3949 const unsigned char *cp = pin;
3950 table = (const int32_t *)
3951 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_TABLEMB);
3952 weights = (const unsigned char *)
3953 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_WEIGHTMB);
3954 extra = (const unsigned char *)
3955 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_EXTRAMB);
3956 indirect = (const int32_t *)
3957 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_INDIRECTMB);
3958 idx = findidx (&cp);
3959 if (idx > 0)
3960 for (i = 0; i < cset->nequiv_classes; ++i)
3961 {
3962 int32_t equiv_class_idx = cset->equiv_classes[i];
3963 size_t weight_len = weights[idx];
3964 if (weight_len == weights[equiv_class_idx])
3965 {
3966 int cnt = 0;
3967 while (cnt <= weight_len
3968 && (weights[equiv_class_idx + 1 + cnt]
3969 == weights[idx + 1 + cnt]))
3970 ++cnt;
3971 if (cnt > weight_len)
3972 {
3973 match_len = elem_len;
3974 goto check_node_accept_bytes_match;
3975 }
3976 }
3977 }
3978 }
3979 }
434d3784
UD		 3980 else
3981# endif /* _LIBC */
15a7d175
UD		 3982 {
3983 /* match with range expression? */
92b27c74 3984#if __GNUC__ >= 2
15a7d175 3985 wchar_t cmp_buf[] = {L'\0', L'\0', wc, L'\0', L'\0', L'\0'};
92b27c74 3986#else
15a7d175
UD		 3987 wchar_t cmp_buf[] = {L'\0', L'\0', L'\0', L'\0', L'\0', L'\0'};
3988 cmp_buf[2] = wc;
92b27c74 3989#endif
15a7d175
UD		 3990 for (i = 0; i < cset->nranges; ++i)
3991 {
3992 cmp_buf[0] = cset->range_starts[i];
3993 cmp_buf[4] = cset->range_ends[i];
3994 if (wcscoll (cmp_buf, cmp_buf + 2) <= 0
3995 && wcscoll (cmp_buf + 2, cmp_buf + 4) <= 0)
3996 {
3997 match_len = char_len;
3998 goto check_node_accept_bytes_match;
3999 }
4000 }
4001 }
434d3784
UD		 4002 check_node_accept_bytes_match:
4003 if (!cset->non_match)
15a7d175 4004 return match_len;
434d3784 4005 else
15a7d175
UD		 4006 {
4007 if (match_len > 0)
4008 return 0;
4009 else
4010 return (elem_len > char_len) ? elem_len : char_len;
4011 }
3b0bdc72
UD		 4012 }
4013 return 0;
4014}
4015
434d3784 4016# ifdef _LIBC
3b0bdc72 4017static unsigned int
a334319f
UD		 4018find_collation_sequence_value (mbs, mbs_len)
4019 const unsigned char *mbs;
4020 size_t mbs_len;
3b0bdc72
UD		 4021{
4022 uint32_t nrules = _NL_CURRENT_WORD (LC_COLLATE, _NL_COLLATE_NRULES);
4023 if (nrules == 0)
4024 {
4025 if (mbs_len == 1)
15a7d175
UD		 4026 {
4027 /* No valid character. Match it as a single byte character. */
4028 const unsigned char *collseq = (const unsigned char *)
4029 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_COLLSEQMB);
4030 return collseq[mbs[0]];
4031 }
3b0bdc72
UD		 4032 return UINT_MAX;
4033 }
4034 else
4035 {
4036 int32_t idx;
4037 const unsigned char *extra = (const unsigned char *)
15a7d175 4038 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB);
6c2a04a7
UD		 4039 int32_t extrasize = (const unsigned char *)
4040 _NL_CURRENT (LC_COLLATE, _NL_COLLATE_SYMB_EXTRAMB + 1) - extra;
3b0bdc72 4041
6c2a04a7 4042 for (idx = 0; idx < extrasize;)
15a7d175
UD		 4043 {
4044 int mbs_cnt, found = 0;
4045 int32_t elem_mbs_len;
4046 /* Skip the name of collating element name. */
4047 idx = idx + extra[idx] + 1;
4048 elem_mbs_len = extra[idx++];
4049 if (mbs_len == elem_mbs_len)
4050 {
4051 for (mbs_cnt = 0; mbs_cnt < elem_mbs_len; ++mbs_cnt)
4052 if (extra[idx + mbs_cnt] != mbs[mbs_cnt])
4053 break;
4054 if (mbs_cnt == elem_mbs_len)
4055 /* Found the entry. */
4056 found = 1;
4057 }
4058 /* Skip the byte sequence of the collating element. */
4059 idx += elem_mbs_len;
4060 /* Adjust for the alignment. */
4061 idx = (idx + 3) & ~3;
4062 /* Skip the collation sequence value. */
4063 idx += sizeof (uint32_t);
4064 /* Skip the wide char sequence of the collating element. */
4065 idx = idx + sizeof (uint32_t) * (extra[idx] + 1);
4066 /* If we found the entry, return the sequence value. */
4067 if (found)
4068 return *(uint32_t *) (extra + idx);
4069 /* Skip the collation sequence value. */
4070 idx += sizeof (uint32_t);
4071 }
6c2a04a7 4072 return UINT_MAX;
3b0bdc72
UD		 4073 }
4074}
434d3784
UD		 4075# endif /* _LIBC */
4076#endif /* RE_ENABLE_I18N */
3b0bdc72
UD		 4077
4078/* Check whether the node accepts the byte which is IDX-th
4079 byte of the INPUT. */
4080
4081static int
a334319f
UD		 4082check_node_accept (mctx, node, idx)
4083 const re_match_context_t *mctx;
4084 const re_token_t *node;
4085 int idx;
3b0bdc72 4086{
3b0bdc72 4087 unsigned char ch;
56b168be 4088 ch = re_string_byte_at (&mctx->input, idx);
ad7f28c2
UD		 4089 switch (node->type)
4090 {
4091 case CHARACTER:
5cf1ec52
UD		 4092 if (node->opr.c != ch)
4093 return 0;
4094 break;
4095
ad7f28c2 4096 case SIMPLE_BRACKET:
5cf1ec52
UD		 4097 if (!bitset_contain (node->opr.sbcset, ch))
4098 return 0;
4099 break;
4100
c0d5034e 4101#ifdef RE_ENABLE_I18N
ad7f28c2
UD		 4102 case OP_UTF8_PERIOD:
4103 if (ch >= 0x80)
4104 return 0;
4105 /* FALLTHROUGH */
c0d5034e 4106#endif
ad7f28c2 4107 case OP_PERIOD:
5cf1ec52
UD		 4108 if ((ch == '\n' && !(mctx->dfa->syntax & RE_DOT_NEWLINE))
4109 || (ch == '\0' && (mctx->dfa->syntax & RE_DOT_NOT_NULL)))
4110 return 0;
4111 break;
4112
ad7f28c2
UD		 4113 default:
4114 return 0;
4115 }
5cf1ec52
UD		 4116
4117 if (node->constraint)
4118 {
4119 /* The node has constraints. Check whether the current context
4120 satisfies the constraints. */
4121 unsigned int context = re_string_context_at (&mctx->input, idx,
4122 mctx->eflags);
4123 if (NOT_SATISFY_NEXT_CONSTRAINT (node->constraint, context))
4124 return 0;
4125 }
4126
4127 return 1;
3b0bdc72 4128}
612546c6
UD		 4129
4130/* Extend the buffers, if the buffers have run out. */
4131
4132static reg_errcode_t
a334319f
UD		 4133extend_buffers (mctx)
4134 re_match_context_t *mctx;
612546c6
UD		 4135{
4136 reg_errcode_t ret;
56b168be 4137 re_string_t *pstr = &mctx->input;
612546c6
UD		 4138
4139 /* Double the lengthes of the buffers. */
4140 ret = re_string_realloc_buffers (pstr, pstr->bufs_len * 2);
4141 if (BE (ret != REG_NOERROR, 0))
4142 return ret;
4143
4144 if (mctx->state_log != NULL)
4145 {
4146 /* And double the length of state_log. */
951d6408
UD		 4147 /* XXX We have no indication of the size of this buffer. If this
4148 allocation fail we have no indication that the state_log array
4149 does not have the right size. */
4150 re_dfastate_t **new_array = re_realloc (mctx->state_log, re_dfastate_t *,
4151 pstr->bufs_len + 1);
1b2c2628 4152 if (BE (new_array == NULL, 0))
15a7d175 4153 return REG_ESPACE;
1b2c2628 4154 mctx->state_log = new_array;
612546c6
UD		 4155 }
4156
4157 /* Then reconstruct the buffers. */
4158 if (pstr->icase)
4159 {
4160#ifdef RE_ENABLE_I18N
3c0fb574 4161 if (pstr->mb_cur_max > 1)
bb3f4825
UD		 4162 {
4163 ret = build_wcs_upper_buffer (pstr);
4164 if (BE (ret != REG_NOERROR, 0))
4165 return ret;
4166 }
612546c6
UD		 4167 else
4168#endif /* RE_ENABLE_I18N */
15a7d175 4169 build_upper_buffer (pstr);
612546c6
UD		 4170 }
4171 else
4172 {
4173#ifdef RE_ENABLE_I18N
3c0fb574 4174 if (pstr->mb_cur_max > 1)
15a7d175 4175 build_wcs_buffer (pstr);
612546c6
UD		 4176 else
4177#endif /* RE_ENABLE_I18N */
15a7d175
UD		 4178 {
4179 if (pstr->trans != NULL)
4180 re_string_translate_buffer (pstr);
15a7d175 4181 }
612546c6
UD		 4182 }
4183 return REG_NOERROR;
4184}
4185
3b0bdc72
UD		 4186\f
4187/* Functions for matching context. */
4188
6291ee3c
UD		 4189/* Initialize MCTX. */
4190
a9388965 4191static reg_errcode_t
a334319f
UD		 4192match_ctx_init (mctx, eflags, n)
4193 re_match_context_t *mctx;
4194 int eflags, n;
3b0bdc72
UD		 4195{
4196 mctx->eflags = eflags;
612546c6 4197 mctx->match_last = -1;
3b0bdc72 4198 if (n > 0)
a9388965
UD		 4199 {
4200 mctx->bkref_ents = re_malloc (struct re_backref_cache_entry, n);
6291ee3c
UD		 4201 mctx->sub_tops = re_malloc (re_sub_match_top_t *, n);
4202 if (BE (mctx->bkref_ents == NULL || mctx->sub_tops == NULL, 0))
15a7d175 4203 return REG_ESPACE;
a9388965 4204 }
56b168be
UD		 4205 /* Already zero-ed by the caller.
4206 else
4207 mctx->bkref_ents = NULL;
4208 mctx->nbkref_ents = 0;
4209 mctx->nsub_tops = 0; */
3b0bdc72 4210 mctx->abkref_ents = n;
6291ee3c 4211 mctx->max_mb_elem_len = 1;
6291ee3c 4212 mctx->asub_tops = n;
a9388965 4213 return REG_NOERROR;
3b0bdc72
UD		 4214}
4215
6291ee3c
UD		 4216/* Clean the entries which depend on the current input in MCTX.
4217 This function must be invoked when the matcher changes the start index
4218 of the input, or changes the input string. */
4219
4220static void
a334319f
UD		 4221match_ctx_clean (mctx)
4222 re_match_context_t *mctx;
6291ee3c
UD		 4223{
4224 int st_idx;
4225 for (st_idx = 0; st_idx < mctx->nsub_tops; ++st_idx)
4226 {
4227 int sl_idx;
4228 re_sub_match_top_t *top = mctx->sub_tops[st_idx];
4229 for (sl_idx = 0; sl_idx < top->nlasts; ++sl_idx)
4230 {
4231 re_sub_match_last_t *last = top->lasts[sl_idx];
4232 re_free (last->path.array);
4233 re_free (last);
4234 }
4235 re_free (top->lasts);
4236 if (top->path)
4237 {
4238 re_free (top->path->array);
4239 re_free (top->path);
4240 }
4241 free (top);
4242 }
cb265fec
UD		 4243
4244 mctx->nsub_tops = 0;
4245 mctx->nbkref_ents = 0;
4246}
4247
4248/* Free all the memory associated with MCTX. */
4249
4250static void
a334319f
UD		 4251match_ctx_free (mctx)
4252 re_match_context_t *mctx;
cb265fec
UD		 4253{
4254 /* First, free all the memory associated with MCTX->SUB_TOPS. */
4255 match_ctx_clean (mctx);
4256 re_free (mctx->sub_tops);
4257 re_free (mctx->bkref_ents);
6291ee3c
UD		 4258}
4259
4260/* Add a new backreference entry to MCTX.
4261 Note that we assume that caller never call this function with duplicate
4262 entry, and call with STR_IDX which isn't smaller than any existing entry.
4263*/
3b0bdc72 4264
a9388965 4265static reg_errcode_t
a334319f
UD		 4266match_ctx_add_entry (mctx, node, str_idx, from, to)
4267 re_match_context_t *mctx;
4268 int node, str_idx, from, to;
3b0bdc72
UD		 4269{
4270 if (mctx->nbkref_ents >= mctx->abkref_ents)
4271 {
1b2c2628
UD		 4272 struct re_backref_cache_entry* new_entry;
4273 new_entry = re_realloc (mctx->bkref_ents, struct re_backref_cache_entry,
15a7d175 4274 mctx->abkref_ents * 2);
1b2c2628 4275 if (BE (new_entry == NULL, 0))
15a7d175
UD		 4276 {
4277 re_free (mctx->bkref_ents);
4278 return REG_ESPACE;
4279 }
1b2c2628 4280 mctx->bkref_ents = new_entry;
3b0bdc72 4281 memset (mctx->bkref_ents + mctx->nbkref_ents, '\0',
15a7d175 4282 sizeof (struct re_backref_cache_entry) * mctx->abkref_ents);
3b0bdc72
UD		 4283 mctx->abkref_ents *= 2;
4284 }
e40a38b3
UD		 4285 if (mctx->nbkref_ents > 0
4286 && mctx->bkref_ents[mctx->nbkref_ents - 1].str_idx == str_idx)
4287 mctx->bkref_ents[mctx->nbkref_ents - 1].more = 1;
4288
3b0bdc72 4289 mctx->bkref_ents[mctx->nbkref_ents].node = node;
0742e48e
UD		 4290 mctx->bkref_ents[mctx->nbkref_ents].str_idx = str_idx;
4291 mctx->bkref_ents[mctx->nbkref_ents].subexp_from = from;
e40a38b3 4292 mctx->bkref_ents[mctx->nbkref_ents].subexp_to = to;
7db61208
UD		 4293
4294 /* This is a cache that saves negative results of check_dst_limits_calc_pos.
4295 If bit N is clear, means that this entry won't epsilon-transition to
4296 an OP_OPEN_SUBEXP or OP_CLOSE_SUBEXP for the N+1-th subexpression. If
4297 it is set, check_dst_limits_calc_pos_1 will recurse and try to find one
4298 such node.
4299
4300 A backreference does not epsilon-transition unless it is empty, so set
4301 to all zeros if FROM != TO. */
4302 mctx->bkref_ents[mctx->nbkref_ents].eps_reachable_subexps_map
4303 = (from == to ? ~0 : 0);
4304
e40a38b3 4305 mctx->bkref_ents[mctx->nbkref_ents++].more = 0;
0742e48e
UD		 4306 if (mctx->max_mb_elem_len < to - from)
4307 mctx->max_mb_elem_len = to - from;
a9388965 4308 return REG_NOERROR;
3b0bdc72 4309}
0742e48e 4310
e40a38b3
UD		 4311/* Search for the first entry which has the same str_idx, or -1 if none is
4312 found. Note that MCTX->BKREF_ENTS is already sorted by MCTX->STR_IDX. */
6291ee3c
UD		 4313
4314static int
a334319f 4315search_cur_bkref_entry (mctx, str_idx)
01ed6ceb 4316 const re_match_context_t *mctx;
a334319f 4317 int str_idx;
6291ee3c 4318{
e40a38b3
UD		 4319 int left, right, mid, last;
4320 last = right = mctx->nbkref_ents;
6291ee3c
UD		 4321 for (left = 0; left < right;)
4322 {
4323 mid = (left + right) / 2;
4324 if (mctx->bkref_ents[mid].str_idx < str_idx)
4325 left = mid + 1;
4326 else
4327 right = mid;
4328 }
e40a38b3
UD		 4329 if (left < last && mctx->bkref_ents[left].str_idx == str_idx)
4330 return left;
4331 else
4332 return -1;
6291ee3c
UD		 4333}
4334
6291ee3c
UD		 4335/* Register the node NODE, whose type is OP_OPEN_SUBEXP, and which matches
4336 at STR_IDX. */
4337
4338static reg_errcode_t
a334319f
UD		 4339match_ctx_add_subtop (mctx, node, str_idx)
4340 re_match_context_t *mctx;
4341 int node, str_idx;
6291ee3c
UD		 4342{
4343#ifdef DEBUG
4344 assert (mctx->sub_tops != NULL);
4345 assert (mctx->asub_tops > 0);
4346#endif
951d6408 4347 if (BE (mctx->nsub_tops == mctx->asub_tops, 0))
6291ee3c 4348 {
951d6408
UD		 4349 int new_asub_tops = mctx->asub_tops * 2;
4350 re_sub_match_top_t **new_array = re_realloc (mctx->sub_tops,
4351 re_sub_match_top_t *,
4352 new_asub_tops);
6291ee3c
UD		 4353 if (BE (new_array == NULL, 0))
4354 return REG_ESPACE;
4355 mctx->sub_tops = new_array;
951d6408 4356 mctx->asub_tops = new_asub_tops;
6291ee3c
UD		 4357 }
4358 mctx->sub_tops[mctx->nsub_tops] = calloc (1, sizeof (re_sub_match_top_t));
951d6408 4359 if (BE (mctx->sub_tops[mctx->nsub_tops] == NULL, 0))
6291ee3c
UD		 4360 return REG_ESPACE;
4361 mctx->sub_tops[mctx->nsub_tops]->node = node;
4362 mctx->sub_tops[mctx->nsub_tops++]->str_idx = str_idx;
4363 return REG_NOERROR;
4364}
4365
4366/* Register the node NODE, whose type is OP_CLOSE_SUBEXP, and which matches
4367 at STR_IDX, whose corresponding OP_OPEN_SUBEXP is SUB_TOP. */
4368
4369static re_sub_match_last_t *
a334319f
UD		 4370match_ctx_add_sublast (subtop, node, str_idx)
4371 re_sub_match_top_t *subtop;
4372 int node, str_idx;
6291ee3c
UD		 4373{
4374 re_sub_match_last_t *new_entry;
951d6408 4375 if (BE (subtop->nlasts == subtop->alasts, 0))
6291ee3c 4376 {
951d6408
UD		 4377 int new_alasts = 2 * subtop->alasts + 1;
4378 re_sub_match_last_t **new_array = re_realloc (subtop->lasts,
4379 re_sub_match_last_t *,
4380 new_alasts);
6291ee3c
UD		 4381 if (BE (new_array == NULL, 0))
4382 return NULL;
4383 subtop->lasts = new_array;
951d6408 4384 subtop->alasts = new_alasts;
6291ee3c
UD		 4385 }
4386 new_entry = calloc (1, sizeof (re_sub_match_last_t));
951d6408
UD		 4387 if (BE (new_entry != NULL, 1))
4388 {
4389 subtop->lasts[subtop->nlasts] = new_entry;
4390 new_entry->node = node;
4391 new_entry->str_idx = str_idx;
4392 ++subtop->nlasts;
4393 }
6291ee3c
UD		 4394 return new_entry;
4395}
4396
0742e48e 4397static void
a334319f
UD		 4398sift_ctx_init (sctx, sifted_sts, limited_sts, last_node, last_str_idx)
4399 re_sift_context_t *sctx;
4400 re_dfastate_t **sifted_sts, **limited_sts;
4401 int last_node, last_str_idx;
0742e48e
UD		 4402{
4403 sctx->sifted_states = sifted_sts;
4404 sctx->limited_states = limited_sts;
4405 sctx->last_node = last_node;
4406 sctx->last_str_idx = last_str_idx;
0742e48e
UD		 4407 re_node_set_init_empty (&sctx->limits);
4408}
A mirror of the official glibc repository