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