gdb - Local mods (compile)
[dragonfly.git] / 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 #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 }