win32/regexec.c

   1 /*
   2   regexec.c - TRE POSIX compatible matching functions (and more).
   3
   4   Copyright (c) 2001-2009 Ville Laurikari <vl@iki.fi>
   5   All rights reserved.
   6
   7   Redistribution and use in source and binary forms, with or without
   8   modification, are permitted provided that the following conditions
   9   are met:
  10
  11     1. Redistributions of source code must retain the above copyright
  12        notice, this list of conditions and the following disclaimer.
  13
  14     2. Redistributions in binary form must reproduce the above copyright
  15        notice, this list of conditions and the following disclaimer in the
  16        documentation and/or other materials provided with the distribution.
  17
  18   THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDER AND CONTRIBUTORS
  19   ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
  20   LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
  21   A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE COPYRIGHT
  22   HOLDER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
  23   SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
  24   LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
  25   DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
  26   THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
  27   (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
  28   OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
  29
  30 */
  31
  32 #include <stdlib.h>
  33 #include <string.h>
  34 #include <wchar.h>
  35 #include <wctype.h>
  36 #include <limits.h>
  37 #include <stdint.h>
  38
  39 #include <regex.h>
  40
  41 #include "tre.h"
  42
  43 #include <assert.h>
  44
  45 static void
  46 tre_fill_pmatch(size_t nmatch, regmatch_t pmatch[], int cflags,
  47     const tre_tnfa_t *tnfa, regoff_t *tags, regoff_t match_eo);
  48
  49 /***********************************************************************
  50  from tre-match-utils.h
  51 ***********************************************************************/
  52
  53 #define GET_NEXT_WCHAR() do {                                                 \
  54     prev_c = next_c; pos += pos_add_next;                                     \
  55     if ((pos_add_next = mbtowc(&next_c, str_byte, MB_LEN_MAX)) <= 0) {        \
  56         if (pos_add_next < 0) { ret = REG_NOMATCH; goto error_exit; }         \
  57         else pos_add_next++;                                                  \
  58     }                                                                         \
  59     str_byte += pos_add_next;                                                 \
  60   } while (0)
  61
  62 #define IS_WORD_CHAR(c)  ((c) == L'_' || tre_isalnum(c))
  63
  64 #define CHECK_ASSERTIONS(assertions)                \
  65   (((assertions & ASSERT_AT_BOL)                \
  66     && (pos > 0 || reg_notbol)                  \
  67     && (prev_c != L'\n' || !reg_newline))             \
  68    || ((assertions & ASSERT_AT_EOL)               \
  69        && (next_c != L'\0' || reg_noteol)             \
  70        && (next_c != L'\n' || !reg_newline))              \
  71    || ((assertions & ASSERT_AT_BOW)               \
  72        && (IS_WORD_CHAR(prev_c) || !IS_WORD_CHAR(next_c)))                \
  73    || ((assertions & ASSERT_AT_EOW)               \
  74        && (!IS_WORD_CHAR(prev_c) || IS_WORD_CHAR(next_c)))          \
  75    || ((assertions & ASSERT_AT_WB)                \
  76        && (pos != 0 && next_c != L'\0'                \
  77      && IS_WORD_CHAR(prev_c) == IS_WORD_CHAR(next_c)))          \
  78    || ((assertions & ASSERT_AT_WB_NEG)                \
  79        && (pos == 0 || next_c == L'\0'                \
  80      || IS_WORD_CHAR(prev_c) != IS_WORD_CHAR(next_c))))
  81
  82 #define CHECK_CHAR_CLASSES(trans_i, tnfa, eflags)                             \
  83   (((trans_i->assertions & ASSERT_CHAR_CLASS)                                 \
  84        && !(tnfa->cflags & REG_ICASE)                                         \
  85        && !tre_isctype((tre_cint_t)prev_c, trans_i->u.class))                 \
  86     || ((trans_i->assertions & ASSERT_CHAR_CLASS)                             \
  87         && (tnfa->cflags & REG_ICASE)                                         \
  88         && !tre_isctype(tre_tolower((tre_cint_t)prev_c),trans_i->u.class)     \
  89   && !tre_isctype(tre_toupper((tre_cint_t)prev_c),trans_i->u.class))    \
  90     || ((trans_i->assertions & ASSERT_CHAR_CLASS_NEG)                         \
  91         && tre_neg_char_classes_match(trans_i->neg_classes,(tre_cint_t)prev_c,\
  92                                       tnfa->cflags & REG_ICASE)))
  93
  94
  95
  96
  97 /* Returns 1 if `t1' wins `t2', 0 otherwise. */
  98 static int
  99 tre_tag_order(int num_tags, tre_tag_direction_t *tag_directions,
 100         regoff_t *t1, regoff_t *t2)
 101 {
 102   int i;
 103   for (i = 0; i < num_tags; i++)
 104     {
 105       if (tag_directions[i] == TRE_TAG_MINIMIZE)
 106   {
 107     if (t1[i] < t2[i])
 108       return 1;
 109     if (t1[i] > t2[i])
 110       return 0;
 111   }
 112       else
 113   {
 114     if (t1[i] > t2[i])
 115       return 1;
 116     if (t1[i] < t2[i])
 117       return 0;
 118   }
 119     }
 120   /*  assert(0);*/
 121   return 0;
 122 }
 123
 124 static int
 125 tre_neg_char_classes_match(tre_ctype_t *classes, tre_cint_t wc, int icase)
 126 {
 127   while (*classes != (tre_ctype_t)0)
 128     if ((!icase && tre_isctype(wc, *classes))
 129   || (icase && (tre_isctype(tre_toupper(wc), *classes)
 130           || tre_isctype(tre_tolower(wc), *classes))))
 131       return 1; /* Match. */
 132     else
 133       classes++;
 134   return 0; /* No match. */
 135 }
 136
 137
 138 /***********************************************************************
 139  from tre-match-parallel.c
 140 ***********************************************************************/
 141
 142 /*
 143   This algorithm searches for matches basically by reading characters
 144   in the searched string one by one, starting at the beginning.  All
 145   matching paths in the TNFA are traversed in parallel.  When two or
 146   more paths reach the same state, exactly one is chosen according to
 147   tag ordering rules; if returning submatches is not required it does
 148   not matter which path is chosen.
 149
 150   The worst case time required for finding the leftmost and longest
 151   match, or determining that there is no match, is always linearly
 152   dependent on the length of the text being searched.
 153
 154   This algorithm cannot handle TNFAs with back referencing nodes.
 155   See `tre-match-backtrack.c'.
 156 */
 157
 158 typedef struct {
 159   tre_tnfa_transition_t *state;
 160   regoff_t *tags;
 161 } tre_tnfa_reach_t;
 162
 163 typedef struct {
 164   regoff_t pos;
 165   regoff_t **tags;
 166 } tre_reach_pos_t;
 167
 168
 169 static reg_errcode_t
 170 tre_tnfa_run_parallel(const tre_tnfa_t *tnfa, const void *string,
 171           regoff_t *match_tags, int eflags,
 172           regoff_t *match_end_ofs)
 173 {
 174   /* State variables required by GET_NEXT_WCHAR. */
 175   tre_char_t prev_c = 0, next_c = 0;
 176   const char *str_byte = string;
 177   regoff_t pos = -1;
 178   regoff_t pos_add_next = 1;
 179 #ifdef TRE_MBSTATE
 180   mbstate_t mbstate;
 181 #endif /* TRE_MBSTATE */
 182   int reg_notbol = eflags & REG_NOTBOL;
 183   int reg_noteol = eflags & REG_NOTEOL;
 184   int reg_newline = tnfa->cflags & REG_NEWLINE;
 185   reg_errcode_t ret;
 186
 187   char *buf;
 188   tre_tnfa_transition_t *trans_i;
 189   tre_tnfa_reach_t *reach, *reach_next, *reach_i, *reach_next_i;
 190   tre_reach_pos_t *reach_pos;
 191   int *tag_i;
 192   int num_tags, i;
 193
 194   regoff_t match_eo = -1;    /* end offset of match (-1 if no match found yet) */
 195   int new_match = 0;
 196   regoff_t *tmp_tags = NULL;
 197   regoff_t *tmp_iptr;
 198
 199 #ifdef TRE_MBSTATE
 200   memset(&mbstate, '\0', sizeof(mbstate));
 201 #endif /* TRE_MBSTATE */
 202
 203   if (!match_tags)
 204     num_tags = 0;
 205   else
 206     num_tags = tnfa->num_tags;
 207
 208   /* Allocate memory for temporary data required for matching.  This needs to
 209      be done for every matching operation to be thread safe.  This allocates
 210      everything in a single large block with calloc(). */
 211   {
 212     size_t tbytes, rbytes, pbytes, xbytes, total_bytes;
 213     char *tmp_buf;
 214
 215     /* Ensure that tbytes and xbytes*num_states cannot overflow, and that
 216      * they don't contribute more than 1/8 of SIZE_MAX to total_bytes. */
 217     if (num_tags > SIZE_MAX/(8 * sizeof(regoff_t) * tnfa->num_states))
 218       return REG_ESPACE;
 219
 220     /* Likewise check rbytes. */
 221     if (tnfa->num_states+1 > SIZE_MAX/(8 * sizeof(*reach_next)))
 222       return REG_ESPACE;
 223
 224     /* Likewise check pbytes. */
 225     if (tnfa->num_states > SIZE_MAX/(8 * sizeof(*reach_pos)))
 226       return REG_ESPACE;
 227
 228     /* Compute the length of the block we need. */
 229     tbytes = sizeof(*tmp_tags) * num_tags;
 230     rbytes = sizeof(*reach_next) * (tnfa->num_states + 1);
 231     pbytes = sizeof(*reach_pos) * tnfa->num_states;
 232     xbytes = sizeof(regoff_t) * num_tags;
 233     total_bytes =
 234       (sizeof(long) - 1) * 4 /* for alignment paddings */
 235       + (rbytes + xbytes * tnfa->num_states) * 2 + tbytes + pbytes;
 236
 237     /* Allocate the memory. */
 238     buf = calloc(total_bytes, 1);
 239     if (buf == NULL)
 240       return REG_ESPACE;
 241
 242     /* Get the various pointers within tmp_buf (properly aligned). */
 243     tmp_tags = (void *)buf;
 244     tmp_buf = buf + tbytes;
 245     tmp_buf += ALIGN(tmp_buf, long);
 246     reach_next = (void *)tmp_buf;
 247     tmp_buf += rbytes;
 248     tmp_buf += ALIGN(tmp_buf, long);
 249     reach = (void *)tmp_buf;
 250     tmp_buf += rbytes;
 251     tmp_buf += ALIGN(tmp_buf, long);
 252     reach_pos = (void *)tmp_buf;
 253     tmp_buf += pbytes;
 254     tmp_buf += ALIGN(tmp_buf, long);
 255     for (i = 0; i < tnfa->num_states; i++)
 256       {
 257   reach[i].tags = (void *)tmp_buf;
 258   tmp_buf += xbytes;
 259   reach_next[i].tags = (void *)tmp_buf;
 260   tmp_buf += xbytes;
 261       }
 262   }
 263
 264   for (i = 0; i < tnfa->num_states; i++)
 265     reach_pos[i].pos = -1;
 266
 267   GET_NEXT_WCHAR();
 268   pos = 0;
 269
 270   reach_next_i = reach_next;
 271   while (1)
 272     {
 273       /* If no match found yet, add the initial states to `reach_next'. */
 274       if (match_eo < 0)
 275   {
 276     trans_i = tnfa->initial;
 277     while (trans_i->state != NULL)
 278       {
 279         if (reach_pos[trans_i->state_id].pos < pos)
 280     {
 281       if (trans_i->assertions
 282           && CHECK_ASSERTIONS(trans_i->assertions))
 283         {
 284           trans_i++;
 285           continue;
 286         }
 287
 288       reach_next_i->state = trans_i->state;
 289       for (i = 0; i < num_tags; i++)
 290         reach_next_i->tags[i] = -1;
 291       tag_i = trans_i->tags;
 292       if (tag_i)
 293         while (*tag_i >= 0)
 294           {
 295       if (*tag_i < num_tags)
 296         reach_next_i->tags[*tag_i] = pos;
 297       tag_i++;
 298           }
 299       if (reach_next_i->state == tnfa->final)
 300         {
 301           match_eo = pos;
 302           new_match = 1;
 303           for (i = 0; i < num_tags; i++)
 304       match_tags[i] = reach_next_i->tags[i];
 305         }
 306       reach_pos[trans_i->state_id].pos = pos;
 307       reach_pos[trans_i->state_id].tags = &reach_next_i->tags;
 308       reach_next_i++;
 309     }
 310         trans_i++;
 311       }
 312     reach_next_i->state = NULL;
 313   }
 314       else
 315   {
 316     if (num_tags == 0 || reach_next_i == reach_next)
 317       /* We have found a match. */
 318       break;
 319   }
 320
 321       /* Check for end of string. */
 322       if (!next_c) break;
 323
 324       GET_NEXT_WCHAR();
 325
 326       /* Swap `reach' and `reach_next'. */
 327       reach_i = reach;
 328       reach = reach_next;
 329       reach_next = reach_i;
 330
 331       /* For each state in `reach', weed out states that don't fulfill the
 332    minimal matching conditions. */
 333       if (tnfa->num_minimals && new_match)
 334   {
 335     new_match = 0;
 336     reach_next_i = reach_next;
 337     for (reach_i = reach; reach_i->state; reach_i++)
 338       {
 339         int skip = 0;
 340         for (i = 0; tnfa->minimal_tags[i] >= 0; i += 2)
 341     {
 342       int end = tnfa->minimal_tags[i];
 343       int start = tnfa->minimal_tags[i + 1];
 344       if (end >= num_tags)
 345         {
 346           skip = 1;
 347           break;
 348         }
 349       else if (reach_i->tags[start] == match_tags[start]
 350          && reach_i->tags[end] < match_tags[end])
 351         {
 352           skip = 1;
 353           break;
 354         }
 355     }
 356         if (!skip)
 357     {
 358       reach_next_i->state = reach_i->state;
 359       tmp_iptr = reach_next_i->tags;
 360       reach_next_i->tags = reach_i->tags;
 361       reach_i->tags = tmp_iptr;
 362       reach_next_i++;
 363     }
 364       }
 365     reach_next_i->state = NULL;
 366
 367     /* Swap `reach' and `reach_next'. */
 368     reach_i = reach;
 369     reach = reach_next;
 370     reach_next = reach_i;
 371   }
 372
 373       /* For each state in `reach' see if there is a transition leaving with
 374    the current input symbol to a state not yet in `reach_next', and
 375    add the destination states to `reach_next'. */
 376       reach_next_i = reach_next;
 377       for (reach_i = reach; reach_i->state; reach_i++)
 378   {
 379     for (trans_i = reach_i->state; trans_i->state; trans_i++)
 380       {
 381         /* Does this transition match the input symbol? */
 382         if (trans_i->code_min <= (tre_cint_t)prev_c &&
 383       trans_i->code_max >= (tre_cint_t)prev_c)
 384     {
 385       if (trans_i->assertions
 386           && (CHECK_ASSERTIONS(trans_i->assertions)
 387         || CHECK_CHAR_CLASSES(trans_i, tnfa, eflags)))
 388         {
 389           continue;
 390         }
 391
 392       /* Compute the tags after this transition. */
 393       for (i = 0; i < num_tags; i++)
 394         tmp_tags[i] = reach_i->tags[i];
 395       tag_i = trans_i->tags;
 396       if (tag_i != NULL)
 397         while (*tag_i >= 0)
 398           {
 399       if (*tag_i < num_tags)
 400         tmp_tags[*tag_i] = pos;
 401       tag_i++;
 402           }
 403
 404       if (reach_pos[trans_i->state_id].pos < pos)
 405         {
 406           /* Found an unvisited node. */
 407           reach_next_i->state = trans_i->state;
 408           tmp_iptr = reach_next_i->tags;
 409           reach_next_i->tags = tmp_tags;
 410           tmp_tags = tmp_iptr;
 411           reach_pos[trans_i->state_id].pos = pos;
 412           reach_pos[trans_i->state_id].tags = &reach_next_i->tags;
 413
 414           if (reach_next_i->state == tnfa->final
 415         && (match_eo == -1
 416             || (num_tags > 0
 417           && reach_next_i->tags[0] <= match_tags[0])))
 418       {
 419         match_eo = pos;
 420         new_match = 1;
 421         for (i = 0; i < num_tags; i++)
 422           match_tags[i] = reach_next_i->tags[i];
 423       }
 424           reach_next_i++;
 425
 426         }
 427       else
 428         {
 429           assert(reach_pos[trans_i->state_id].pos == pos);
 430           /* Another path has also reached this state.  We choose
 431        the winner by examining the tag values for both
 432        paths. */
 433           if (tre_tag_order(num_tags, tnfa->tag_directions,
 434           tmp_tags,
 435           *reach_pos[trans_i->state_id].tags))
 436       {
 437         /* The new path wins. */
 438         tmp_iptr = *reach_pos[trans_i->state_id].tags;
 439         *reach_pos[trans_i->state_id].tags = tmp_tags;
 440         if (trans_i->state == tnfa->final)
 441           {
 442             match_eo = pos;
 443             new_match = 1;
 444             for (i = 0; i < num_tags; i++)
 445         match_tags[i] = tmp_tags[i];
 446           }
 447         tmp_tags = tmp_iptr;
 448       }
 449         }
 450     }
 451       }
 452   }
 453       reach_next_i->state = NULL;
 454     }
 455
 456   *match_end_ofs = match_eo;
 457   ret = match_eo >= 0 ? REG_OK : REG_NOMATCH;
 458 error_exit:
 459   xfree(buf);
 460   return ret;
 461 }
 462
 463
 464
 465 /***********************************************************************
 466  from tre-match-backtrack.c
 467 ***********************************************************************/
 468
 469 /*
 470   This matcher is for regexps that use back referencing.  Regexp matching
 471   with back referencing is an NP-complete problem on the number of back
 472   references.  The easiest way to match them is to use a backtracking
 473   routine which basically goes through all possible paths in the TNFA
 474   and chooses the one which results in the best (leftmost and longest)
 475   match.  This can be spectacularly expensive and may run out of stack
 476   space, but there really is no better known generic algorithm.  Quoting
 477   Henry Spencer from comp.compilers:
 478   <URL: http://compilers.iecc.com/comparch/article/93-03-102>
 479
 480     POSIX.2 REs require longest match, which is really exciting to
 481     implement since the obsolete ("basic") variant also includes
 482     \<digit>.  I haven't found a better way of tackling this than doing
 483     a preliminary match using a DFA (or simulation) on a modified RE
 484     that just replicates subREs for \<digit>, and then doing a
 485     backtracking match to determine whether the subRE matches were
 486     right.  This can be rather slow, but I console myself with the
 487     thought that people who use \<digit> deserve very slow execution.
 488     (Pun unintentional but very appropriate.)
 489
 490 */
 491
 492 typedef struct {
 493   regoff_t pos;
 494   const char *str_byte;
 495   tre_tnfa_transition_t *state;
 496   int state_id;
 497   int next_c;
 498   regoff_t *tags;
 499 #ifdef TRE_MBSTATE
 500   mbstate_t mbstate;
 501 #endif /* TRE_MBSTATE */
 502 } tre_backtrack_item_t;
 503
 504 typedef struct tre_backtrack_struct {
 505   tre_backtrack_item_t item;
 506   struct tre_backtrack_struct *prev;
 507   struct tre_backtrack_struct *next;
 508 } *tre_backtrack_t;
 509
 510 #ifdef TRE_MBSTATE
 511 #define BT_STACK_MBSTATE_IN  stack->item.mbstate = (mbstate)
 512 #define BT_STACK_MBSTATE_OUT (mbstate) = stack->item.mbstate
 513 #else /* !TRE_MBSTATE */
 514 #define BT_STACK_MBSTATE_IN
 515 #define BT_STACK_MBSTATE_OUT
 516 #endif /* !TRE_MBSTATE */
 517
 518 #define tre_bt_mem_new      tre_mem_new
 519 #define tre_bt_mem_alloc    tre_mem_alloc
 520 #define tre_bt_mem_destroy    tre_mem_destroy
 521
 522
 523 #define BT_STACK_PUSH(_pos, _str_byte, _str_wide, _state, _state_id, _next_c, _tags, _mbstate) \
 524   do                        \
 525     {                       \
 526       int i;                      \
 527       if (!stack->next)                   \
 528   {                     \
 529     tre_backtrack_t s;                  \
 530     s = tre_bt_mem_alloc(mem, sizeof(*s));            \
 531     if (!s)                   \
 532       {                     \
 533         tre_bt_mem_destroy(mem);                \
 534         if (tags)                   \
 535     xfree(tags);                  \
 536         if (pmatch)                 \
 537     xfree(pmatch);                  \
 538         if (states_seen)                  \
 539     xfree(states_seen);               \
 540         return REG_ESPACE;                \
 541       }                     \
 542     s->prev = stack;                  \
 543     s->next = NULL;                 \
 544     s->item.tags = tre_bt_mem_alloc(mem,              \
 545             sizeof(*tags) * tnfa->num_tags);    \
 546     if (!s->item.tags)                  \
 547       {                     \
 548         tre_bt_mem_destroy(mem);                \
 549         if (tags)                   \
 550     xfree(tags);                  \
 551         if (pmatch)                 \
 552     xfree(pmatch);                  \
 553         if (states_seen)                  \
 554     xfree(states_seen);               \
 555         return REG_ESPACE;                \
 556       }                     \
 557     stack->next = s;                  \
 558     stack = s;                    \
 559   }                     \
 560       else                      \
 561   stack = stack->next;                  \
 562       stack->item.pos = (_pos);                 \
 563       stack->item.str_byte = (_str_byte);             \
 564       stack->item.state = (_state);               \
 565       stack->item.state_id = (_state_id);             \
 566       stack->item.next_c = (_next_c);               \
 567       for (i = 0; i < tnfa->num_tags; i++)              \
 568   stack->item.tags[i] = (_tags)[i];             \
 569       BT_STACK_MBSTATE_IN;                  \
 570     }                       \
 571   while (0)
 572
 573 #define BT_STACK_POP()                    \
 574   do                        \
 575     {                       \
 576       int i;                      \
 577       assert(stack->prev);                  \
 578       pos = stack->item.pos;                  \
 579       str_byte = stack->item.str_byte;                \
 580       state = stack->item.state;                \
 581       next_c = stack->item.next_c;                \
 582       for (i = 0; i < tnfa->num_tags; i++)              \
 583   tags[i] = stack->item.tags[i];                \
 584       BT_STACK_MBSTATE_OUT;                 \
 585       stack = stack->prev;                  \
 586     }                       \
 587   while (0)
 588
 589 #undef MIN
 590 #define MIN(a, b) ((a) <= (b) ? (a) : (b))
 591
 592 static reg_errcode_t
 593 tre_tnfa_run_backtrack(const tre_tnfa_t *tnfa, const void *string,
 594            regoff_t *match_tags, int eflags, regoff_t *match_end_ofs)
 595 {
 596   /* State variables required by GET_NEXT_WCHAR. */
 597   tre_char_t prev_c = 0, next_c = 0;
 598   const char *str_byte = string;
 599   regoff_t pos = 0;
 600   regoff_t pos_add_next = 1;
 601 #ifdef TRE_MBSTATE
 602   mbstate_t mbstate;
 603 #endif /* TRE_MBSTATE */
 604   int reg_notbol = eflags & REG_NOTBOL;
 605   int reg_noteol = eflags & REG_NOTEOL;
 606   int reg_newline = tnfa->cflags & REG_NEWLINE;
 607
 608   /* These are used to remember the necessary values of the above
 609      variables to return to the position where the current search
 610      started from. */
 611   int next_c_start;
 612   const char *str_byte_start;
 613   regoff_t pos_start = -1;
 614 #ifdef TRE_MBSTATE
 615   mbstate_t mbstate_start;
 616 #endif /* TRE_MBSTATE */
 617
 618   /* End offset of best match so far, or -1 if no match found yet. */
 619   regoff_t match_eo = -1;
 620   /* Tag arrays. */
 621   int *next_tags;
 622   regoff_t *tags = NULL;
 623   /* Current TNFA state. */
 624   tre_tnfa_transition_t *state;
 625   int *states_seen = NULL;
 626
 627   /* Memory allocator to for allocating the backtracking stack. */
 628   tre_mem_t mem = tre_bt_mem_new();
 629
 630   /* The backtracking stack. */
 631   tre_backtrack_t stack;
 632
 633   tre_tnfa_transition_t *trans_i;
 634   regmatch_t *pmatch = NULL;
 635   int ret;
 636
 637 #ifdef TRE_MBSTATE
 638   memset(&mbstate, '\0', sizeof(mbstate));
 639 #endif /* TRE_MBSTATE */
 640
 641   if (!mem)
 642     return REG_ESPACE;
 643   stack = tre_bt_mem_alloc(mem, sizeof(*stack));
 644   if (!stack)
 645     {
 646       ret = REG_ESPACE;
 647       goto error_exit;
 648     }
 649   stack->prev = NULL;
 650   stack->next = NULL;
 651
 652   if (tnfa->num_tags)
 653     {
 654       tags = xmalloc(sizeof(*tags) * tnfa->num_tags);
 655       if (!tags)
 656   {
 657     ret = REG_ESPACE;
 658     goto error_exit;
 659   }
 660     }
 661   if (tnfa->num_submatches)
 662     {
 663       pmatch = xmalloc(sizeof(*pmatch) * tnfa->num_submatches);
 664       if (!pmatch)
 665   {
 666     ret = REG_ESPACE;
 667     goto error_exit;
 668   }
 669     }
 670   if (tnfa->num_states)
 671     {
 672       states_seen = xmalloc(sizeof(*states_seen) * tnfa->num_states);
 673       if (!states_seen)
 674   {
 675     ret = REG_ESPACE;
 676     goto error_exit;
 677   }
 678     }
 679
 680  retry:
 681   {
 682     int i;
 683     for (i = 0; i < tnfa->num_tags; i++)
 684       {
 685   tags[i] = -1;
 686   if (match_tags)
 687     match_tags[i] = -1;
 688       }
 689     for (i = 0; i < tnfa->num_states; i++)
 690       states_seen[i] = 0;
 691   }
 692
 693   state = NULL;
 694   pos = pos_start;
 695   GET_NEXT_WCHAR();
 696   pos_start = pos;
 697   next_c_start = next_c;
 698   str_byte_start = str_byte;
 699 #ifdef TRE_MBSTATE
 700   mbstate_start = mbstate;
 701 #endif /* TRE_MBSTATE */
 702
 703   /* Handle initial states. */
 704   next_tags = NULL;
 705   for (trans_i = tnfa->initial; trans_i->state; trans_i++)
 706     {
 707       if (trans_i->assertions && CHECK_ASSERTIONS(trans_i->assertions))
 708   {
 709     continue;
 710   }
 711       if (state == NULL)
 712   {
 713     /* Start from this state. */
 714     state = trans_i->state;
 715     next_tags = trans_i->tags;
 716   }
 717       else
 718   {
 719     /* Backtrack to this state. */
 720     BT_STACK_PUSH(pos, str_byte, 0, trans_i->state,
 721       trans_i->state_id, next_c, tags, mbstate);
 722     {
 723       int *tmp = trans_i->tags;
 724       if (tmp)
 725         while (*tmp >= 0)
 726     stack->item.tags[*tmp++] = pos;
 727     }
 728   }
 729     }
 730
 731   if (next_tags)
 732     for (; *next_tags >= 0; next_tags++)
 733       tags[*next_tags] = pos;
 734
 735
 736   if (state == NULL)
 737     goto backtrack;
 738
 739   while (1)
 740     {
 741       tre_tnfa_transition_t *next_state;
 742       int empty_br_match;
 743
 744       if (state == tnfa->final)
 745   {
 746     if (match_eo < pos
 747         || (match_eo == pos
 748       && match_tags
 749       && tre_tag_order(tnfa->num_tags, tnfa->tag_directions,
 750            tags, match_tags)))
 751       {
 752         int i;
 753         /* This match wins the previous match. */
 754         match_eo = pos;
 755         if (match_tags)
 756     for (i = 0; i < tnfa->num_tags; i++)
 757       match_tags[i] = tags[i];
 758       }
 759     /* Our TNFAs never have transitions leaving from the final state,
 760        so we jump right to backtracking. */
 761     goto backtrack;
 762   }
 763
 764       /* Go to the next character in the input string. */
 765       empty_br_match = 0;
 766       trans_i = state;
 767       if (trans_i->state && trans_i->assertions & ASSERT_BACKREF)
 768   {
 769     /* This is a back reference state.  All transitions leaving from
 770        this state have the same back reference "assertion".  Instead
 771        of reading the next character, we match the back reference. */
 772     regoff_t so, eo;
 773     int bt = trans_i->u.backref;
 774     regoff_t bt_len;
 775     int result;
 776
 777     /* Get the substring we need to match against.  Remember to
 778        turn off REG_NOSUB temporarily. */
 779     tre_fill_pmatch(bt + 1, pmatch, tnfa->cflags & ~REG_NOSUB,
 780         tnfa, tags, pos);
 781     so = pmatch[bt].rm_so;
 782     eo = pmatch[bt].rm_eo;
 783     bt_len = eo - so;
 784
 785     result = strncmp((const char*)string + so, str_byte - 1,
 786          (size_t)bt_len);
 787
 788     if (result == 0)
 789       {
 790         /* Back reference matched.  Check for infinite loop. */
 791         if (bt_len == 0)
 792     empty_br_match = 1;
 793         if (empty_br_match && states_seen[trans_i->state_id])
 794     {
 795       goto backtrack;
 796     }
 797
 798         states_seen[trans_i->state_id] = empty_br_match;
 799
 800         /* Advance in input string and resync `prev_c', `next_c'
 801      and pos. */
 802         str_byte += bt_len - 1;
 803         pos += bt_len - 1;
 804         GET_NEXT_WCHAR();
 805       }
 806     else
 807       {
 808         goto backtrack;
 809       }
 810   }
 811       else
 812   {
 813     /* Check for end of string. */
 814     if (next_c == L'\0')
 815     goto backtrack;
 816
 817     /* Read the next character. */
 818     GET_NEXT_WCHAR();
 819   }
 820
 821       next_state = NULL;
 822       for (trans_i = state; trans_i->state; trans_i++)
 823   {
 824     if (trans_i->code_min <= (tre_cint_t)prev_c
 825         && trans_i->code_max >= (tre_cint_t)prev_c)
 826       {
 827         if (trans_i->assertions
 828       && (CHECK_ASSERTIONS(trans_i->assertions)
 829           || CHECK_CHAR_CLASSES(trans_i, tnfa, eflags)))
 830     {
 831       continue;
 832     }
 833
 834         if (next_state == NULL)
 835     {
 836       /* First matching transition. */
 837       next_state = trans_i->state;
 838       next_tags = trans_i->tags;
 839     }
 840         else
 841     {
 842       /* Second matching transition.  We may need to backtrack here
 843          to take this transition instead of the first one, so we
 844          push this transition in the backtracking stack so we can
 845          jump back here if needed. */
 846       BT_STACK_PUSH(pos, str_byte, 0, trans_i->state,
 847         trans_i->state_id, next_c, tags, mbstate);
 848       {
 849         int *tmp;
 850         for (tmp = trans_i->tags; tmp && *tmp >= 0; tmp++)
 851           stack->item.tags[*tmp] = pos;
 852       }
 853 #if 0 /* XXX - it's important not to look at all transitions here to keep
 854    the stack small! */
 855       break;
 856 #endif
 857     }
 858       }
 859   }
 860
 861       if (next_state != NULL)
 862   {
 863     /* Matching transitions were found.  Take the first one. */
 864     state = next_state;
 865
 866     /* Update the tag values. */
 867     if (next_tags)
 868       while (*next_tags >= 0)
 869         tags[*next_tags++] = pos;
 870   }
 871       else
 872   {
 873   backtrack:
 874     /* A matching transition was not found.  Try to backtrack. */
 875     if (stack->prev)
 876       {
 877         if (stack->item.state->assertions & ASSERT_BACKREF)
 878     {
 879       states_seen[stack->item.state_id] = 0;
 880     }
 881
 882         BT_STACK_POP();
 883       }
 884     else if (match_eo < 0)
 885       {
 886         /* Try starting from a later position in the input string. */
 887         /* Check for end of string. */
 888         if (next_c == L'\0')
 889         {
 890           break;
 891         }
 892         next_c = next_c_start;
 893 #ifdef TRE_MBSTATE
 894         mbstate = mbstate_start;
 895 #endif /* TRE_MBSTATE */
 896         str_byte = str_byte_start;
 897         goto retry;
 898       }
 899     else
 900       {
 901         break;
 902       }
 903   }
 904     }
 905
 906   ret = match_eo >= 0 ? REG_OK : REG_NOMATCH;
 907   *match_end_ofs = match_eo;
 908
 909  error_exit:
 910   tre_bt_mem_destroy(mem);
 911 #ifndef TRE_USE_ALLOCA
 912   if (tags)
 913     xfree(tags);
 914   if (pmatch)
 915     xfree(pmatch);
 916   if (states_seen)
 917     xfree(states_seen);
 918 #endif /* !TRE_USE_ALLOCA */
 919
 920   return ret;
 921 }
 922
 923 /***********************************************************************
 924  from regexec.c
 925 ***********************************************************************/
 926
 927 /* Fills the POSIX.2 regmatch_t array according to the TNFA tag and match
 928    endpoint values. */
 929 static void
 930 tre_fill_pmatch(size_t nmatch, regmatch_t pmatch[], int cflags,
 931     const tre_tnfa_t *tnfa, regoff_t *tags, regoff_t match_eo)
 932 {
 933   tre_submatch_data_t *submatch_data;
 934   unsigned int i, j;
 935   int *parents;
 936
 937   i = 0;
 938   if (match_eo >= 0 && !(cflags & REG_NOSUB))
 939     {
 940       /* Construct submatch offsets from the tags. */
 941       submatch_data = tnfa->submatch_data;
 942       while (i < tnfa->num_submatches && i < nmatch)
 943   {
 944     if (submatch_data[i].so_tag == tnfa->end_tag)
 945       pmatch[i].rm_so = match_eo;
 946     else
 947       pmatch[i].rm_so = tags[submatch_data[i].so_tag];
 948
 949     if (submatch_data[i].eo_tag == tnfa->end_tag)
 950       pmatch[i].rm_eo = match_eo;
 951     else
 952       pmatch[i].rm_eo = tags[submatch_data[i].eo_tag];
 953
 954     /* If either of the endpoints were not used, this submatch
 955        was not part of the match. */
 956     if (pmatch[i].rm_so == -1 || pmatch[i].rm_eo == -1)
 957       pmatch[i].rm_so = pmatch[i].rm_eo = -1;
 958
 959     i++;
 960   }
 961       /* Reset all submatches that are not within all of their parent
 962    submatches. */
 963       i = 0;
 964       while (i < tnfa->num_submatches && i < nmatch)
 965   {
 966     if (pmatch[i].rm_eo == -1)
 967       assert(pmatch[i].rm_so == -1);
 968     assert(pmatch[i].rm_so <= pmatch[i].rm_eo);
 969
 970     parents = submatch_data[i].parents;
 971     if (parents != NULL)
 972       for (j = 0; parents[j] >= 0; j++)
 973         {
 974     if (pmatch[i].rm_so < pmatch[parents[j]].rm_so
 975         || pmatch[i].rm_eo > pmatch[parents[j]].rm_eo)
 976       pmatch[i].rm_so = pmatch[i].rm_eo = -1;
 977         }
 978     i++;
 979   }
 980     }
 981
 982   while (i < nmatch)
 983     {
 984       pmatch[i].rm_so = -1;
 985       pmatch[i].rm_eo = -1;
 986       i++;
 987     }
 988 }
 989
 990
 991 /*
 992   Wrapper functions for POSIX compatible regexp matching.
 993 */
 994
 995 int
 996 regexec(const regex_t *__restrict preg, const char *__restrict string,
 997     size_t nmatch, regmatch_t * __restrict pmatch, int eflags)
 998 {
 999   tre_tnfa_t *tnfa = (void *)preg->TRE_REGEX_T_FIELD;
1000   reg_errcode_t status;
1001   regoff_t *tags = NULL, eo;
1002   if (tnfa->cflags & REG_NOSUB) nmatch = 0;
1003   if (tnfa->num_tags > 0 && nmatch > 0)
1004     {
1005       tags = xmalloc(sizeof(*tags) * tnfa->num_tags);
1006       if (tags == NULL)
1007   return REG_ESPACE;
1008     }
1009
1010   /* Dispatch to the appropriate matcher. */
1011   if (tnfa->have_backrefs)
1012     {
1013       /* The regex has back references, use the backtracking matcher. */
1014       status = tre_tnfa_run_backtrack(tnfa, string, tags, eflags, &eo);
1015     }
1016   else
1017     {
1018       /* Exact matching, no back references, use the parallel matcher. */
1019       status = tre_tnfa_run_parallel(tnfa, string, tags, eflags, &eo);
1020     }
1021
1022   if (status == REG_OK)
1023     /* A match was found, so fill the submatch registers. */
1024     tre_fill_pmatch(nmatch, pmatch, tnfa->cflags, tnfa, tags, eo);
1025   if (tags)
1026     xfree(tags);
1027   return status;
1028 }