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