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