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