1 /* 2 tre-match-backtrack.c - TRE backtracking regex matching engine 3 4 This software is released under a BSD-style license. 5 See the file LICENSE for details and copyright. 6 7 */ 8 9 /* 10 This matcher is for regexps that use back referencing. Regexp matching 11 with back referencing is an NP-complete problem on the number of back 12 references. The easiest way to match them is to use a backtracking 13 routine which basically goes through all possible paths in the TNFA 14 and chooses the one which results in the best (leftmost and longest) 15 match. This can be spectacularly expensive and may run out of stack 16 space, but there really is no better known generic algorithm. Quoting 17 Henry Spencer from comp.compilers: 18 <URL: http://compilers.iecc.com/comparch/article/93-03-102> 19 20 POSIX.2 REs require longest match, which is really exciting to 21 implement since the obsolete ("basic") variant also includes 22 \<digit>. I haven't found a better way of tackling this than doing 23 a preliminary match using a DFA (or simulation) on a modified RE 24 that just replicates subREs for \<digit>, and then doing a 25 backtracking match to determine whether the subRE matches were 26 right. This can be rather slow, but I console myself with the 27 thought that people who use \<digit> deserve very slow execution. 28 (Pun unintentional but very appropriate.) 29 30 */ 31 32 33 #ifdef HAVE_CONFIG_H 34 #include <config.h> 35 #endif /* HAVE_CONFIG_H */ 36 37 /* Unset TRE_USE_ALLOCA to avoid using the stack to hold all the state 38 info while running */ 39 #undef TRE_USE_ALLOCA 40 41 #ifdef TRE_USE_ALLOCA 42 /* AIX requires this to be the first thing in the file. */ 43 #ifndef __GNUC__ 44 # if HAVE_ALLOCA_H 45 # include <alloca.h> 46 # else 47 # ifdef _AIX 48 #pragma alloca 49 # else 50 # ifndef alloca /* predefined by HP cc +Olibcalls */ 51 char *alloca (); 52 # endif 53 # endif 54 # endif 55 #endif 56 #endif /* TRE_USE_ALLOCA */ 57 58 #include <assert.h> 59 #include <stdlib.h> 60 #include <string.h> 61 #ifdef HAVE_WCHAR_H 62 #include <wchar.h> 63 #endif /* HAVE_WCHAR_H */ 64 #ifdef HAVE_WCTYPE_H 65 #include <wctype.h> 66 #endif /* HAVE_WCTYPE_H */ 67 #ifndef TRE_WCHAR 68 #include <ctype.h> 69 #endif /* !TRE_WCHAR */ 70 #ifdef HAVE_MALLOC_H 71 #include <malloc.h> 72 #endif /* HAVE_MALLOC_H */ 73 74 #include "tre-internal.h" 75 #include "tre-mem.h" 76 #include "tre-match-utils.h" 77 #include "tre.h" 78 #include "xmalloc.h" 79 80 typedef struct { 81 int pos; 82 unsigned int pos_add_next; 83 const char *str_byte; 84 #ifdef TRE_WCHAR 85 const wchar_t *str_wide; 86 #endif /* TRE_WCHAR */ 87 tre_tnfa_transition_t *state; 88 int state_id; 89 int next_c; 90 tre_tag_t *tags; 91 #ifdef TRE_MBSTATE 92 mbstate_t mbstate; 93 #endif /* TRE_MBSTATE */ 94 } tre_backtrack_item_t; 95 96 typedef struct tre_backtrack_struct { 97 tre_backtrack_item_t item; 98 struct tre_backtrack_struct *prev; 99 struct tre_backtrack_struct *next; 100 } *tre_backtrack_t; 101 102 #ifdef TRE_WCHAR 103 #define BT_STACK_WIDE_IN(_str_wide) stack->item.str_wide = (_str_wide) 104 #define BT_STACK_WIDE_OUT (str_wide) = stack->item.str_wide 105 #else /* !TRE_WCHAR */ 106 #define BT_STACK_WIDE_IN(_str_wide) 107 #define BT_STACK_WIDE_OUT 108 #endif /* !TRE_WCHAR */ 109 110 #ifdef TRE_MBSTATE 111 #define BT_STACK_MBSTATE_IN stack->item.mbstate = (mbstate) 112 #define BT_STACK_MBSTATE_OUT (mbstate) = stack->item.mbstate 113 #else /* !TRE_MBSTATE */ 114 #define BT_STACK_MBSTATE_IN 115 #define BT_STACK_MBSTATE_OUT 116 #endif /* !TRE_MBSTATE */ 117 118 119 #ifdef TRE_USE_ALLOCA 120 #define tre_bt_mem_new tre_mem_newa 121 #define tre_bt_mem_alloc tre_mem_alloca 122 #define tre_bt_mem_destroy(obj) do { } while (0) 123 #else /* !TRE_USE_ALLOCA */ 124 #define tre_bt_mem_new tre_mem_new 125 #define tre_bt_mem_alloc tre_mem_alloc 126 #define tre_bt_mem_destroy tre_mem_destroy 127 #endif /* !TRE_USE_ALLOCA */ 128 129 130 #define BT_STACK_PUSH(_pos, _pos_add_next, _str_byte, _str_wide, _state, _state_id, _next_c, _tags, _mbstate) \ 131 do \ 132 { \ 133 if (!stack->next) \ 134 { \ 135 tre_backtrack_t s; \ 136 s = tre_bt_mem_alloc(mem, sizeof(*s)); \ 137 if (!s) \ 138 { \ 139 tre_bt_mem_destroy(mem); \ 140 if (tags) \ 141 xfree(tags); \ 142 if (pmatch) \ 143 xfree(pmatch); \ 144 if (states_seen) \ 145 xfree(states_seen); \ 146 return REG_ESPACE; \ 147 } \ 148 s->prev = stack; \ 149 s->next = NULL; \ 150 s->item.tags = tre_bt_mem_alloc(mem, \ 151 num_tags * sizeof(*tags)); \ 152 if (!s->item.tags) \ 153 { \ 154 tre_bt_mem_destroy(mem); \ 155 if (tags) \ 156 xfree(tags); \ 157 if (pmatch) \ 158 xfree(pmatch); \ 159 if (states_seen) \ 160 xfree(states_seen); \ 161 return REG_ESPACE; \ 162 } \ 163 stack->next = s; \ 164 stack = s; \ 165 } \ 166 else \ 167 stack = stack->next; \ 168 stack->item.pos = (_pos); \ 169 stack->item.pos_add_next = (_pos_add_next); \ 170 stack->item.str_byte = (_str_byte); \ 171 BT_STACK_WIDE_IN(_str_wide); \ 172 stack->item.state = (_state); \ 173 stack->item.state_id = (_state_id); \ 174 stack->item.next_c = (_next_c); \ 175 memcpy(stack->item.tags, (_tags), num_tags * sizeof(*(_tags))); \ 176 BT_STACK_MBSTATE_IN; \ 177 } \ 178 while (/*CONSTCOND*/0) 179 180 #define BT_STACK_POP() \ 181 do \ 182 { \ 183 assert(stack->prev); \ 184 pos = stack->item.pos; \ 185 pos_add_next = stack->item.pos_add_next; \ 186 str_byte = stack->item.str_byte; \ 187 BT_STACK_WIDE_OUT; \ 188 state = stack->item.state; \ 189 next_c = stack->item.next_c; \ 190 memcpy(tags, stack->item.tags, num_tags * sizeof(*tags)); \ 191 BT_STACK_MBSTATE_OUT; \ 192 stack = stack->prev; \ 193 } \ 194 while (/*CONSTCOND*/0) 195 196 #undef MIN 197 #define MIN(a, b) ((a) <= (b) ? (a) : (b)) 198 199 reg_errcode_t 200 tre_tnfa_run_backtrack(const tre_tnfa_t *tnfa, const void *string, 201 int len, tre_str_type_t type, tre_tag_t *match_tags, 202 int eflags, int *match_end_ofs) 203 { 204 /* State variables required by GET_NEXT_WCHAR. */ 205 tre_char_t prev_c = 0, next_c = 0; 206 const char *str_byte = string; 207 int pos = 0; 208 unsigned int pos_add_next = 1; 209 #ifdef TRE_WCHAR 210 const wchar_t *str_wide = string; 211 #ifdef TRE_MBSTATE 212 mbstate_t mbstate; 213 #endif /* TRE_MBSTATE */ 214 #endif /* TRE_WCHAR */ 215 int reg_notbol = eflags & REG_NOTBOL; 216 int reg_noteol = eflags & REG_NOTEOL; 217 int reg_newline = tnfa->cflags & REG_NEWLINE; 218 int i; 219 220 /* These are used to remember the necessary values of the above 221 variables to return to the position where the current search 222 started from. */ 223 int next_c_start; 224 const char *str_byte_start; 225 int pos_start = -1; 226 #ifdef TRE_WCHAR 227 const wchar_t *str_wide_start; 228 #endif /* TRE_WCHAR */ 229 #ifdef TRE_MBSTATE 230 mbstate_t mbstate_start; 231 #endif /* TRE_MBSTATE */ 232 233 /* End offset of best match so far, or -1 if no match found yet. */ 234 int match_eo = -1; 235 /* Tag arrays. */ 236 int *next_tags; 237 tre_tag_t *tags = NULL; 238 /* Current TNFA state. */ 239 tre_tnfa_transition_t *state; 240 int *states_seen = NULL; 241 242 /* Memory allocator to for allocating the backtracking stack. */ 243 tre_mem_t mem = tre_bt_mem_new(); 244 245 /* The backtracking stack. */ 246 tre_backtrack_t stack; 247 248 tre_tnfa_transition_t *trans_i; 249 regmatch_t *pmatch = NULL; 250 reg_errcode_t ret; 251 252 int num_tags = tnfa->num_tags; 253 int touch = 1; 254 char *buf; 255 int tbytes; 256 257 #ifdef TRE_MBSTATE 258 memset(&mbstate, '\0', sizeof(mbstate)); 259 #endif /* TRE_MBSTATE */ 260 261 if (!mem) 262 return REG_ESPACE; 263 stack = tre_bt_mem_alloc(mem, sizeof(*stack)); 264 if (!stack) 265 { 266 ret = REG_ESPACE; 267 goto error_exit; 268 } 269 stack->prev = NULL; 270 stack->next = NULL; 271 272 DPRINT(("tnfa_execute_backtrack, input type %d\n", type)); 273 DPRINT(("len = %d\n", len)); 274 275 { 276 int pbytes, sbytes, total_bytes; 277 char *tmp_buf; 278 /* Compute the length of the block we need. */ 279 tbytes = sizeof(*tags) * num_tags; 280 pbytes = sizeof(*pmatch) * tnfa->num_submatches; 281 sbytes = sizeof(*states_seen) * tnfa->num_states; 282 total_bytes = 283 (sizeof(long) - 1) * 2 /* for alignment paddings */ 284 + tbytes + pbytes + sbytes; 285 286 DPRINT(("tre_tnfa_run_backtrack, allocate %d bytes\n", total_bytes)); 287 /* Allocate the memory. */ 288 #ifdef TRE_USE_ALLOCA 289 buf = alloca(total_bytes); 290 #else /* !TRE_USE_ALLOCA */ 291 buf = xmalloc((unsigned)total_bytes); 292 #endif /* !TRE_USE_ALLOCA */ 293 if (buf == NULL) 294 return REG_ESPACE; 295 296 /* Get the various pointers within tmp_buf (properly aligned). */ 297 tags = (void *)buf; 298 tmp_buf = buf + tbytes; 299 tmp_buf += ALIGN(tmp_buf, long); 300 pmatch = (void *)tmp_buf; 301 tmp_buf += pbytes; 302 tmp_buf += ALIGN(tmp_buf, long); 303 states_seen = (void *)tmp_buf; 304 } 305 306 retry: 307 { 308 memset(tags, 0, num_tags * sizeof(*tags)); 309 if (match_tags) 310 memset(match_tags, 0, num_tags * sizeof(*match_tags)); 311 for (i = 0; i < tnfa->num_states; i++) 312 states_seen[i] = 0; 313 } 314 315 state = NULL; 316 pos = pos_start; 317 GET_NEXT_WCHAR(); 318 pos_start = pos; 319 next_c_start = next_c; 320 str_byte_start = str_byte; 321 #ifdef TRE_WCHAR 322 str_wide_start = str_wide; 323 #endif /* TRE_WCHAR */ 324 #ifdef TRE_MBSTATE 325 mbstate_start = mbstate; 326 #endif /* TRE_MBSTATE */ 327 328 /* Handle initial states. */ 329 next_tags = NULL; 330 for (trans_i = tnfa->initial; trans_i->state; trans_i++) 331 { 332 DPRINT(("> init %p, prev_c %lc\n", trans_i->state, (tre_cint_t)prev_c)); 333 if (trans_i->assertions && CHECK_ASSERTIONS(trans_i->assertions)) 334 { 335 DPRINT(("assert failed\n")); 336 continue; 337 } 338 if (state == NULL) 339 { 340 /* Start from this state. */ 341 state = trans_i->state; 342 next_tags = trans_i->tags; 343 } 344 else 345 { 346 /* Backtrack to this state. */ 347 DPRINT(("saving state %d for backtracking\n", trans_i->state_id)); 348 BT_STACK_PUSH(pos, pos_add_next, str_byte, str_wide, trans_i->state, 349 trans_i->state_id, next_c, tags, mbstate); 350 { 351 int *tmp = trans_i->tags; 352 if (tmp) 353 { 354 while (*tmp >= 0) 355 tre_tag_set(stack->item.tags, *tmp++, pos, touch); 356 touch++; 357 } 358 } 359 } 360 } 361 362 if (next_tags) 363 { 364 for (; *next_tags >= 0; next_tags++) 365 tre_tag_set(tags, *next_tags, pos, touch); 366 touch++; 367 } 368 369 370 DPRINT(("entering match loop, pos %d, str_byte %p\n", pos, str_byte)); 371 DPRINT(("pos:chr/code | state and tags\n")); 372 DPRINT(("-------------+------------------------------------------------\n")); 373 374 if (state == NULL) 375 goto backtrack; 376 377 while (/*CONSTCOND*/1) 378 { 379 tre_tnfa_transition_t *next_state; 380 int empty_br_match; 381 382 DPRINT(("start loop\n")); 383 384 if (match_eo >= 0 && tnfa->num_minimals) 385 { 386 int skip = 0; 387 #ifdef TRE_DEBUG 388 DPRINT(("Checking minimal conditions: match_eo=%d match_tags=", 389 match_eo)); 390 tre_print_tags(match_tags, tnfa->num_tags); 391 DPRINT(("\n")); 392 #endif /* TRE_DEBUG */ 393 for (i = 0; tnfa->minimal_tags[i] >= 0; i += 2) 394 { 395 int end = tnfa->minimal_tags[i]; 396 int start = tnfa->minimal_tags[i + 1]; 397 DPRINT((" Minimal start %d, end %d\n", start, end)); 398 if (tre_minimal_tag_order(start, end, match_tags, tags) > 0) 399 { 400 skip = 1; 401 break; 402 } 403 } 404 if (!skip) 405 { 406 #ifdef TRE_DEBUG 407 DPRINT((" Keeping tags=")); 408 tre_print_tags(tags, tnfa->num_tags); 409 DPRINT(("\n")); 410 #endif /* TRE_DEBUG */ 411 } 412 else 413 { 414 #ifdef TRE_DEBUG 415 DPRINT((" Throwing out tags=")); 416 tre_print_tags(tags, tnfa->num_tags); 417 DPRINT(("\n")); 418 #endif /* TRE_DEBUG */ 419 goto backtrack; 420 } 421 } 422 423 if (state == tnfa->final) 424 { 425 DPRINT((" match found, match_eo=%d pos=%d\n", match_eo, pos)); 426 427 if (match_eo >= 0 && tnfa->num_minimals) 428 { 429 int compare = 0; 430 #ifdef TRE_DEBUG 431 DPRINT(("Checking minimal conditions: match_eo=%d " 432 "match_tags=", match_eo)); 433 tre_print_tags(match_tags, tnfa->num_tags); 434 DPRINT(("\n")); 435 #endif /* TRE_DEBUG */ 436 for (i = 0; tnfa->minimal_tags[i] >= 0; i += 2) 437 { 438 int end = tnfa->minimal_tags[i]; 439 int start = tnfa->minimal_tags[i + 1]; 440 DPRINT((" Minimal start %d, end %d\n", start, end)); 441 if ((compare = tre_minimal_tag_order(start, end, 442 match_tags, tags)) != 0) 443 break; 444 } 445 if (compare > 0) 446 { 447 #ifdef TRE_DEBUG 448 DPRINT((" Throwing out new match, tags=")); 449 tre_print_tags(tags, tnfa->num_tags); 450 DPRINT(("\n")); 451 #endif /* TRE_DEBUG */ 452 goto backtrack; 453 } 454 else if (compare < 0) 455 { 456 #ifdef TRE_DEBUG 457 DPRINT((" Throwing out old match, tags=")); 458 tre_print_tags(match_tags, tnfa->num_tags); 459 DPRINT(("\n")); 460 #endif /* TRE_DEBUG */ 461 match_eo = -1; 462 } 463 } 464 465 if (match_eo < pos 466 || (match_eo == pos 467 && match_tags 468 && tre_tag_order(tnfa->num_tags, tnfa->tag_directions, 469 tags, match_tags))) 470 { 471 /* This match wins the previous match. */ 472 #ifdef TRE_DEBUG 473 DPRINT((" win previous tags=")); 474 tre_print_tags(tags, tnfa->num_tags); 475 DPRINT(("\n")); 476 #endif /* TRE_DEBUG */ 477 match_eo = pos; 478 if (match_tags) 479 memcpy(match_tags, tags, num_tags * sizeof(*tags)); 480 } 481 /* Our TNFAs never have transitions leaving from the final state, 482 so we jump right to backtracking. */ 483 goto backtrack; 484 } 485 486 #ifdef TRE_DEBUG 487 DPRINT(("%3d:%2lc/%05d | %p ", pos, (tre_cint_t)next_c, (int)next_c, 488 state)); 489 tre_print_tags(tags, tnfa->num_tags); 490 DPRINT(("\n")); 491 #endif /* TRE_DEBUG */ 492 493 /* Go to the next character in the input string. */ 494 empty_br_match = 0; 495 trans_i = state; 496 if (trans_i->state && trans_i->assertions & ASSERT_BACKREF) 497 { 498 /* This is a back reference state. All transitions leaving from 499 this state have the same back reference "assertion". Instead 500 of reading the next character, we match the back reference. */ 501 int so, eo, bt = trans_i->u.backref; 502 int bt_len; 503 int result; 504 505 DPRINT((" should match back reference %d\n", bt)); 506 /* Get the substring we need to match against. Remember to 507 turn off REG_NOSUB temporarily. */ 508 ret = tre_fill_pmatch(bt + 1, pmatch, tnfa->cflags & ~REG_NOSUB, 509 tnfa, tags, pos); 510 if (ret != REG_OK) goto error_exit; 511 so = pmatch[bt].rm_so; 512 eo = pmatch[bt].rm_eo; 513 bt_len = eo - so; 514 515 #ifdef TRE_DEBUG 516 { 517 int slen; 518 if (len < 0) 519 slen = bt_len; 520 else 521 slen = MIN(bt_len, len - pos); 522 523 if (type == STR_BYTE) 524 { 525 DPRINT((" substring (len %d) is [%d, %d]: '%.*s'\n", 526 bt_len, so, eo, bt_len, (char*)string + so)); 527 DPRINT((" current string is '%.*s'\n", slen, str_byte - 1)); 528 } 529 #ifdef TRE_WCHAR 530 else if (type == STR_WIDE) 531 { 532 DPRINT((" substring (len %d) is [%d, %d]: '%.*" STRF "'\n", 533 bt_len, so, eo, bt_len, (wchar_t*)string + so)); 534 DPRINT((" current string is '%.*" STRF "'\n", 535 slen, str_wide - 1)); 536 } 537 #endif /* TRE_WCHAR */ 538 } 539 #endif 540 541 if (so < 0) 542 { 543 result = 1; /* Back reference of nomatch doesn't match */ 544 } 545 else if (len < 0) 546 { 547 #ifdef TRE_WCHAR 548 if (type == STR_WIDE) 549 result = wcsncmp((const wchar_t*)string + so, str_wide - 1, 550 (size_t)bt_len); 551 else 552 #endif /* TRE_WCHAR */ 553 result = strncmp((const char*)string + so, str_byte - 1, 554 (size_t)bt_len); 555 } 556 else if (len - pos < bt_len) 557 result = 1; 558 #ifdef TRE_WCHAR 559 else if (type == STR_WIDE) 560 result = wmemcmp((const wchar_t*)string + so, str_wide - 1, 561 (size_t)bt_len); 562 #endif /* TRE_WCHAR */ 563 else 564 result = memcmp((const char*)string + so, str_byte - 1, 565 (size_t)bt_len); 566 567 if (result == 0) 568 { 569 /* Back reference matched. Check for infinite loop. */ 570 if (bt_len == 0) 571 empty_br_match = 1; 572 if (empty_br_match && states_seen[trans_i->state_id]) 573 { 574 DPRINT((" avoid loop\n")); 575 goto backtrack; 576 } 577 578 states_seen[trans_i->state_id] = empty_br_match; 579 580 /* Advance in input string and resync `prev_c', `next_c' 581 and pos. */ 582 DPRINT((" back reference matched\n")); 583 str_byte += bt_len - 1; 584 #ifdef TRE_WCHAR 585 str_wide += bt_len - 1; 586 #endif /* TRE_WCHAR */ 587 pos += bt_len - 1; 588 GET_NEXT_WCHAR(); 589 DPRINT((" pos now %d\n", pos)); 590 } 591 else 592 { 593 DPRINT((" back reference did not match\n")); 594 goto backtrack; 595 } 596 } 597 else 598 { 599 /* Check for end of string. */ 600 if (len < 0) 601 { 602 if (next_c == L'\0') 603 goto backtrack; 604 } 605 else 606 { 607 if (pos >= len) 608 goto backtrack; 609 } 610 611 /* Read the next character. */ 612 GET_NEXT_WCHAR(); 613 } 614 615 next_state = NULL; 616 for (trans_i = state; trans_i->state; trans_i++) 617 { 618 DPRINT((" transition %d-%d (%c-%c) %d to %d\n", 619 trans_i->code_min, trans_i->code_max, 620 trans_i->code_min, trans_i->code_max, 621 trans_i->assertions, trans_i->state_id)); 622 if (trans_i->code_min <= (tre_cint_t)prev_c 623 && trans_i->code_max >= (tre_cint_t)prev_c) 624 { 625 if (trans_i->assertions 626 && (CHECK_ASSERTIONS(trans_i->assertions) 627 || CHECK_CHAR_CLASSES(trans_i, tnfa, eflags))) 628 { 629 DPRINT((" assertion failed\n")); 630 continue; 631 } 632 633 if (next_state == NULL) 634 { 635 /* First matching transition. */ 636 DPRINT((" Next state is %d\n", trans_i->state_id)); 637 next_state = trans_i->state; 638 next_tags = trans_i->tags; 639 } 640 else 641 { 642 /* Second matching transition. We may need to backtrack here 643 to take this transition instead of the first one, so we 644 push this transition in the backtracking stack so we can 645 jump back here if needed. */ 646 DPRINT((" saving state %d for backtracking\n", 647 trans_i->state_id)); 648 BT_STACK_PUSH(pos, pos_add_next, str_byte, str_wide, 649 trans_i->state, trans_i->state_id, next_c, 650 tags, mbstate); 651 { 652 int *tmp; 653 for (tmp = trans_i->tags; tmp && *tmp >= 0; tmp++) 654 tre_tag_set(stack->item.tags, *tmp, pos, touch); 655 touch++; 656 } 657 #if 0 /* XXX - it's important not to look at all transitions here to keep 658 the stack small! */ 659 break; 660 #endif 661 } 662 } 663 } 664 665 if (next_state != NULL) 666 { 667 /* Matching transitions were found. Take the first one. */ 668 state = next_state; 669 670 /* Update the tag values. */ 671 if (next_tags) 672 { 673 while (*next_tags >= 0) 674 tre_tag_set(tags, *next_tags++, pos, touch); 675 touch++; 676 } 677 } 678 else 679 { 680 backtrack: 681 /* A matching transition was not found. Try to backtrack. */ 682 if (stack->prev) 683 { 684 DPRINT((" backtracking\n")); 685 if (stack->item.state->assertions & ASSERT_BACKREF) 686 { 687 DPRINT((" states_seen[%d] = 0\n", 688 stack->item.state_id)); 689 states_seen[stack->item.state_id] = 0; 690 } 691 692 BT_STACK_POP(); 693 } 694 else if (match_eo < 0) 695 { 696 /* Try starting from a later position in the input string. */ 697 /* Check for end of string. */ 698 if (pos == pos_start) 699 { 700 if (len < 0) 701 { 702 if (next_c == L'\0') 703 { 704 DPRINT(("end of string.\n")); 705 break; 706 } 707 } 708 else 709 { 710 if (pos >= len) 711 { 712 DPRINT(("end of string.\n")); 713 break; 714 } 715 } 716 } 717 DPRINT(("restarting from next start position\n")); 718 next_c = next_c_start; 719 #ifdef TRE_MBSTATE 720 mbstate = mbstate_start; 721 #endif /* TRE_MBSTATE */ 722 str_byte = str_byte_start; 723 #ifdef TRE_WCHAR 724 str_wide = str_wide_start; 725 #endif /* TRE_WCHAR */ 726 goto retry; 727 } 728 else 729 { 730 DPRINT(("finished\n")); 731 break; 732 } 733 } 734 } 735 736 ret = match_eo >= 0 ? REG_OK : REG_NOMATCH; 737 *match_end_ofs = match_eo; 738 739 error_exit: 740 tre_bt_mem_destroy(mem); 741 #ifndef TRE_USE_ALLOCA 742 if (buf) 743 xfree(buf); 744 #endif /* !TRE_USE_ALLOCA */ 745 746 return ret; 747 } 748