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