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