contrib/tre/lib/tre-match-backtrack.c

   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 }