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 #ifndef TRE_USE_ALLOCA 261 buf = NULL; 262 #endif 263 264 if (!mem) 265 return REG_ESPACE; 266 stack = tre_bt_mem_alloc(mem, sizeof(*stack)); 267 if (!stack) 268 { 269 ret = REG_ESPACE; 270 goto error_exit; 271 } 272 stack->prev = NULL; 273 stack->next = NULL; 274 275 DPRINT(("tnfa_execute_backtrack, input type %d\n", type)); 276 DPRINT(("len = %d\n", len)); 277 278 { 279 int pbytes, sbytes, total_bytes; 280 char *tmp_buf; 281 /* Compute the length of the block we need. */ 282 tbytes = sizeof(*tags) * num_tags; 283 pbytes = sizeof(*pmatch) * tnfa->num_submatches; 284 sbytes = sizeof(*states_seen) * tnfa->num_states; 285 total_bytes = 286 (sizeof(long) - 1) * 2 /* for alignment paddings */ 287 + tbytes + pbytes + sbytes; 288 289 DPRINT(("tre_tnfa_run_backtrack, allocate %d bytes\n", total_bytes)); 290 /* Allocate the memory. */ 291 #ifdef TRE_USE_ALLOCA 292 buf = alloca(total_bytes); 293 #else /* !TRE_USE_ALLOCA */ 294 buf = xmalloc((unsigned)total_bytes); 295 #endif /* !TRE_USE_ALLOCA */ 296 if (buf == NULL) 297 return REG_ESPACE; 298 299 /* Get the various pointers within tmp_buf (properly aligned). */ 300 tags = (void *)buf; 301 tmp_buf = buf + tbytes; 302 tmp_buf += ALIGN(tmp_buf, long); 303 pmatch = (void *)tmp_buf; 304 tmp_buf += pbytes; 305 tmp_buf += ALIGN(tmp_buf, long); 306 states_seen = (void *)tmp_buf; 307 } 308 309 retry: 310 { 311 memset(tags, 0, num_tags * sizeof(*tags)); 312 if (match_tags) 313 memset(match_tags, 0, num_tags * sizeof(*match_tags)); 314 for (i = 0; i < tnfa->num_states; i++) 315 states_seen[i] = 0; 316 } 317 318 state = NULL; 319 pos = pos_start; 320 GET_NEXT_WCHAR(); 321 pos_start = pos; 322 next_c_start = next_c; 323 str_byte_start = str_byte; 324 #ifdef TRE_WCHAR 325 str_wide_start = str_wide; 326 #endif /* TRE_WCHAR */ 327 #ifdef TRE_MBSTATE 328 mbstate_start = mbstate; 329 #endif /* TRE_MBSTATE */ 330 331 /* Handle initial states. */ 332 next_tags = NULL; 333 for (trans_i = tnfa->initial; trans_i->state; trans_i++) 334 { 335 DPRINT(("> init %p, prev_c %lc\n", trans_i->state, (tre_cint_t)prev_c)); 336 if (trans_i->assertions && CHECK_ASSERTIONS(trans_i->assertions)) 337 { 338 DPRINT(("assert failed\n")); 339 continue; 340 } 341 if (state == NULL) 342 { 343 /* Start from this state. */ 344 state = trans_i->state; 345 next_tags = trans_i->tags; 346 } 347 else 348 { 349 /* Backtrack to this state. */ 350 DPRINT(("saving state %d for backtracking\n", trans_i->state_id)); 351 BT_STACK_PUSH(pos, pos_add_next, str_byte, str_wide, trans_i->state, 352 trans_i->state_id, next_c, tags, mbstate); 353 { 354 int *tmp = trans_i->tags; 355 if (tmp) 356 { 357 while (*tmp >= 0) 358 tre_tag_set(stack->item.tags, *tmp++, pos, touch); 359 touch++; 360 } 361 } 362 } 363 } 364 365 if (next_tags) 366 { 367 for (; *next_tags >= 0; next_tags++) 368 tre_tag_set(tags, *next_tags, pos, touch); 369 touch++; 370 } 371 372 373 DPRINT(("entering match loop, pos %d, str_byte %p\n", pos, str_byte)); 374 DPRINT(("pos:chr/code | state and tags\n")); 375 DPRINT(("-------------+------------------------------------------------\n")); 376 377 if (state == NULL) 378 goto backtrack; 379 380 while (/*CONSTCOND*/1) 381 { 382 tre_tnfa_transition_t *next_state; 383 int empty_br_match; 384 385 DPRINT(("start loop\n")); 386 387 if (match_eo >= 0 && tnfa->num_minimals) 388 { 389 int skip = 0; 390 #ifdef TRE_DEBUG 391 DPRINT(("Checking minimal conditions: match_eo=%d match_tags=", 392 match_eo)); 393 tre_print_tags(match_tags, tnfa->num_tags); 394 DPRINT(("\n")); 395 #endif /* TRE_DEBUG */ 396 for (i = 0; tnfa->minimal_tags[i] >= 0; i += 2) 397 { 398 int end = tnfa->minimal_tags[i]; 399 int start = tnfa->minimal_tags[i + 1]; 400 DPRINT((" Minimal start %d, end %d\n", start, end)); 401 if (tre_minimal_tag_order(start, end, match_tags, tags) > 0) 402 { 403 skip = 1; 404 break; 405 } 406 } 407 if (!skip) 408 { 409 #ifdef TRE_DEBUG 410 DPRINT((" Keeping tags=")); 411 tre_print_tags(tags, tnfa->num_tags); 412 DPRINT(("\n")); 413 #endif /* TRE_DEBUG */ 414 } 415 else 416 { 417 #ifdef TRE_DEBUG 418 DPRINT((" Throwing out tags=")); 419 tre_print_tags(tags, tnfa->num_tags); 420 DPRINT(("\n")); 421 #endif /* TRE_DEBUG */ 422 goto backtrack; 423 } 424 } 425 426 if (state == tnfa->final) 427 { 428 DPRINT((" match found, match_eo=%d pos=%d\n", match_eo, pos)); 429 430 if (match_eo >= 0 && tnfa->num_minimals) 431 { 432 int compare = 0; 433 #ifdef TRE_DEBUG 434 DPRINT(("Checking minimal conditions: match_eo=%d " 435 "match_tags=", match_eo)); 436 tre_print_tags(match_tags, tnfa->num_tags); 437 DPRINT(("\n")); 438 #endif /* TRE_DEBUG */ 439 for (i = 0; tnfa->minimal_tags[i] >= 0; i += 2) 440 { 441 int end = tnfa->minimal_tags[i]; 442 int start = tnfa->minimal_tags[i + 1]; 443 DPRINT((" Minimal start %d, end %d\n", start, end)); 444 if ((compare = tre_minimal_tag_order(start, end, 445 match_tags, tags)) != 0) 446 break; 447 } 448 if (compare > 0) 449 { 450 #ifdef TRE_DEBUG 451 DPRINT((" Throwing out new match, tags=")); 452 tre_print_tags(tags, tnfa->num_tags); 453 DPRINT(("\n")); 454 #endif /* TRE_DEBUG */ 455 goto backtrack; 456 } 457 else if (compare < 0) 458 { 459 #ifdef TRE_DEBUG 460 DPRINT((" Throwing out old match, tags=")); 461 tre_print_tags(match_tags, tnfa->num_tags); 462 DPRINT(("\n")); 463 #endif /* TRE_DEBUG */ 464 match_eo = -1; 465 } 466 } 467 468 if (match_eo < pos 469 || (match_eo == pos 470 && match_tags 471 && tre_tag_order(tnfa->num_tags, tnfa->tag_directions, 472 tags, match_tags))) 473 { 474 /* This match wins the previous match. */ 475 #ifdef TRE_DEBUG 476 DPRINT((" win previous tags=")); 477 tre_print_tags(tags, tnfa->num_tags); 478 DPRINT(("\n")); 479 #endif /* TRE_DEBUG */ 480 match_eo = pos; 481 if (match_tags) 482 memcpy(match_tags, tags, num_tags * sizeof(*tags)); 483 } 484 /* Our TNFAs never have transitions leaving from the final state, 485 so we jump right to backtracking. */ 486 goto backtrack; 487 } 488 489 #ifdef TRE_DEBUG 490 DPRINT(("%3d:%2lc/%05d | %p ", pos, (tre_cint_t)next_c, (int)next_c, 491 state)); 492 tre_print_tags(tags, tnfa->num_tags); 493 DPRINT(("\n")); 494 #endif /* TRE_DEBUG */ 495 496 /* Go to the next character in the input string. */ 497 empty_br_match = 0; 498 trans_i = state; 499 if (trans_i->state && trans_i->assertions & ASSERT_BACKREF) 500 { 501 /* This is a back reference state. All transitions leaving from 502 this state have the same back reference "assertion". Instead 503 of reading the next character, we match the back reference. */ 504 int so, eo, bt = trans_i->u.backref; 505 int bt_len; 506 int result; 507 508 DPRINT((" should match back reference %d\n", bt)); 509 /* Get the substring we need to match against. Remember to 510 turn off REG_NOSUB temporarily. */ 511 ret = tre_fill_pmatch(bt + 1, pmatch, tnfa->cflags & ~REG_NOSUB, 512 tnfa, tags, pos); 513 if (ret != REG_OK) goto error_exit; 514 so = pmatch[bt].rm_so; 515 eo = pmatch[bt].rm_eo; 516 bt_len = eo - so; 517 518 #ifdef TRE_DEBUG 519 { 520 int slen; 521 if (len < 0) 522 slen = bt_len; 523 else 524 slen = MIN(bt_len, len - pos); 525 526 if (type == STR_BYTE) 527 { 528 DPRINT((" substring (len %d) is [%d, %d]: '%.*s'\n", 529 bt_len, so, eo, bt_len, (char*)string + so)); 530 DPRINT((" current string is '%.*s'\n", slen, str_byte - 1)); 531 } 532 #ifdef TRE_WCHAR 533 else if (type == STR_WIDE) 534 { 535 DPRINT((" substring (len %d) is [%d, %d]: '%.*" STRF "'\n", 536 bt_len, so, eo, bt_len, (wchar_t*)string + so)); 537 DPRINT((" current string is '%.*" STRF "'\n", 538 slen, str_wide - 1)); 539 } 540 #endif /* TRE_WCHAR */ 541 } 542 #endif 543 544 if (so < 0) 545 { 546 result = 1; /* Back reference of nomatch doesn't match */ 547 } 548 else if (len < 0) 549 { 550 #ifdef TRE_WCHAR 551 if (type == STR_WIDE) 552 result = wcsncmp((const wchar_t*)string + so, str_wide - 1, 553 (size_t)bt_len); 554 else 555 #endif /* TRE_WCHAR */ 556 result = strncmp((const char*)string + so, str_byte - 1, 557 (size_t)bt_len); 558 } 559 else if (len - pos < bt_len) 560 result = 1; 561 #ifdef TRE_WCHAR 562 else if (type == STR_WIDE) 563 result = wmemcmp((const wchar_t*)string + so, str_wide - 1, 564 (size_t)bt_len); 565 #endif /* TRE_WCHAR */ 566 else 567 result = memcmp((const char*)string + so, str_byte - 1, 568 (size_t)bt_len); 569 570 if (result == 0) 571 { 572 /* Back reference matched. Check for infinite loop. */ 573 if (bt_len == 0) 574 empty_br_match = 1; 575 if (empty_br_match && states_seen[trans_i->state_id]) 576 { 577 DPRINT((" avoid loop\n")); 578 goto backtrack; 579 } 580 581 states_seen[trans_i->state_id] = empty_br_match; 582 583 /* Advance in input string and resync `prev_c', `next_c' 584 and pos. */ 585 DPRINT((" back reference matched\n")); 586 str_byte += bt_len - 1; 587 #ifdef TRE_WCHAR 588 str_wide += bt_len - 1; 589 #endif /* TRE_WCHAR */ 590 pos += bt_len - 1; 591 GET_NEXT_WCHAR(); 592 DPRINT((" pos now %d\n", pos)); 593 } 594 else 595 { 596 DPRINT((" back reference did not match\n")); 597 goto backtrack; 598 } 599 } 600 else 601 { 602 /* Check for end of string. */ 603 if (len < 0) 604 { 605 if (next_c == L'\0') 606 goto backtrack; 607 } 608 else 609 { 610 if (pos >= len) 611 goto backtrack; 612 } 613 614 /* Read the next character. */ 615 GET_NEXT_WCHAR(); 616 } 617 618 next_state = NULL; 619 for (trans_i = state; trans_i->state; trans_i++) 620 { 621 DPRINT((" transition %d-%d (%c-%c) %d to %d\n", 622 trans_i->code_min, trans_i->code_max, 623 trans_i->code_min, trans_i->code_max, 624 trans_i->assertions, trans_i->state_id)); 625 if (trans_i->code_min <= (tre_cint_t)prev_c 626 && trans_i->code_max >= (tre_cint_t)prev_c) 627 { 628 if (trans_i->assertions 629 && (CHECK_ASSERTIONS(trans_i->assertions) 630 || CHECK_CHAR_CLASSES(trans_i, tnfa, eflags))) 631 { 632 DPRINT((" assertion failed\n")); 633 continue; 634 } 635 636 if (next_state == NULL) 637 { 638 /* First matching transition. */ 639 DPRINT((" Next state is %d\n", trans_i->state_id)); 640 next_state = trans_i->state; 641 next_tags = trans_i->tags; 642 } 643 else 644 { 645 /* Second matching transition. We may need to backtrack here 646 to take this transition instead of the first one, so we 647 push this transition in the backtracking stack so we can 648 jump back here if needed. */ 649 DPRINT((" saving state %d for backtracking\n", 650 trans_i->state_id)); 651 BT_STACK_PUSH(pos, pos_add_next, str_byte, str_wide, 652 trans_i->state, trans_i->state_id, next_c, 653 tags, mbstate); 654 { 655 int *tmp; 656 for (tmp = trans_i->tags; tmp && *tmp >= 0; tmp++) 657 tre_tag_set(stack->item.tags, *tmp, pos, touch); 658 touch++; 659 } 660 #if 0 /* XXX - it's important not to look at all transitions here to keep 661 the stack small! */ 662 break; 663 #endif 664 } 665 } 666 } 667 668 if (next_state != NULL) 669 { 670 /* Matching transitions were found. Take the first one. */ 671 state = next_state; 672 673 /* Update the tag values. */ 674 if (next_tags) 675 { 676 while (*next_tags >= 0) 677 tre_tag_set(tags, *next_tags++, pos, touch); 678 touch++; 679 } 680 } 681 else 682 { 683 backtrack: 684 /* A matching transition was not found. Try to backtrack. */ 685 if (stack->prev) 686 { 687 DPRINT((" backtracking\n")); 688 if (stack->item.state->assertions & ASSERT_BACKREF) 689 { 690 DPRINT((" states_seen[%d] = 0\n", 691 stack->item.state_id)); 692 states_seen[stack->item.state_id] = 0; 693 } 694 695 BT_STACK_POP(); 696 } 697 else if (match_eo < 0) 698 { 699 /* Try starting from a later position in the input string. */ 700 /* Check for end of string. */ 701 if (pos == pos_start) 702 { 703 if (len < 0) 704 { 705 if (next_c == L'\0') 706 { 707 DPRINT(("end of string.\n")); 708 break; 709 } 710 } 711 else 712 { 713 if (pos >= len) 714 { 715 DPRINT(("end of string.\n")); 716 break; 717 } 718 } 719 } 720 DPRINT(("restarting from next start position\n")); 721 next_c = next_c_start; 722 #ifdef TRE_MBSTATE 723 mbstate = mbstate_start; 724 #endif /* TRE_MBSTATE */ 725 str_byte = str_byte_start; 726 #ifdef TRE_WCHAR 727 str_wide = str_wide_start; 728 #endif /* TRE_WCHAR */ 729 goto retry; 730 } 731 else 732 { 733 DPRINT(("finished\n")); 734 break; 735 } 736 } 737 } 738 739 ret = match_eo >= 0 ? REG_OK : REG_NOMATCH; 740 *match_end_ofs = match_eo; 741 742 error_exit: 743 tre_bt_mem_destroy(mem); 744 #ifndef TRE_USE_ALLOCA 745 if (buf) 746 xfree(buf); 747 #endif /* !TRE_USE_ALLOCA */ 748 749 return ret; 750 } 751