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