nsz Git - musl/blob - src/regex/regcomp.c

   1 /*
   2   regcomp.c - TRE POSIX compatible regex compilation functions.
   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 <string.h>
  33 #include <errno.h>
  34 #include <stdlib.h>
  35 #include <regex.h>
  36 #include <limits.h>
  37 #include <stdint.h>
  38
  39 #include "tre.h"
  40
  41 #include <assert.h>
  42
  43 /***********************************************************************
  44  from tre-compile.h
  45 ***********************************************************************/
  46
  47 typedef struct {
  48   int position;
  49   int code_min;
  50   int code_max;
  51   int *tags;
  52   int assertions;
  53   tre_ctype_t class;
  54   tre_ctype_t *neg_classes;
  55   int backref;
  56   int *params;
  57 } tre_pos_and_tags_t;
  58
  59
  60 /***********************************************************************
  61  from tre-ast.c and tre-ast.h
  62 ***********************************************************************/
  63
  64 /* The different AST node types. */
  65 typedef enum {
  66   LITERAL,
  67   CATENATION,
  68   ITERATION,
  69   UNION
  70 } tre_ast_type_t;
  71
  72 /* Special subtypes of TRE_LITERAL. */
  73 #define EMPTY     -1   /* Empty leaf (denotes empty string). */
  74 #define ASSERTION -2   /* Assertion leaf. */
  75 #define TAG       -3   /* Tag leaf. */
  76 #define BACKREF   -4   /* Back reference leaf. */
  77
  78 #define IS_SPECIAL(x)   ((x)->code_min < 0)
  79 #define IS_EMPTY(x)     ((x)->code_min == EMPTY)
  80 #define IS_ASSERTION(x) ((x)->code_min == ASSERTION)
  81 #define IS_TAG(x)       ((x)->code_min == TAG)
  82 #define IS_BACKREF(x)   ((x)->code_min == BACKREF)
  83
  84
  85 /* A generic AST node.  All AST nodes consist of this node on the top
  86    level with `obj' pointing to the actual content. */
  87 typedef struct {
  88   tre_ast_type_t type;   /* Type of the node. */
  89   void *obj;             /* Pointer to actual node. */
  90   int nullable;
  91   int submatch_id;
  92   int num_submatches;
  93   int num_tags;
  94   tre_pos_and_tags_t *firstpos;
  95   tre_pos_and_tags_t *lastpos;
  96 } tre_ast_node_t;
  97
  98
  99 /* A "literal" node.  These are created for assertions, back references,
 100    tags, matching parameter settings, and all expressions that match one
 101    character. */
 102 typedef struct {
 103   long code_min;
 104   long code_max;
 105   int position;
 106   union {
 107     tre_ctype_t class;
 108     int *params;
 109   } u;
 110   tre_ctype_t *neg_classes;
 111 } tre_literal_t;
 112
 113 /* A "catenation" node.  These are created when two regexps are concatenated.
 114    If there are more than one subexpressions in sequence, the `left' part
 115    holds all but the last, and `right' part holds the last subexpression
 116    (catenation is left associative). */
 117 typedef struct {
 118   tre_ast_node_t *left;
 119   tre_ast_node_t *right;
 120 } tre_catenation_t;
 121
 122 /* An "iteration" node.  These are created for the "*", "+", "?", and "{m,n}"
 123    operators. */
 124 typedef struct {
 125   /* Subexpression to match. */
 126   tre_ast_node_t *arg;
 127   /* Minimum number of consecutive matches. */
 128   int min;
 129   /* Maximum number of consecutive matches. */
 130   int max;
 131   /* If 0, match as many characters as possible, if 1 match as few as
 132      possible.  Note that this does not always mean the same thing as
 133      matching as many/few repetitions as possible. */
 134   unsigned int minimal:1;
 135 } tre_iteration_t;
 136
 137 /* An "union" node.  These are created for the "|" operator. */
 138 typedef struct {
 139   tre_ast_node_t *left;
 140   tre_ast_node_t *right;
 141 } tre_union_t;
 142
 143 static tre_ast_node_t *
 144 tre_ast_new_node(tre_mem_t mem, tre_ast_type_t type, size_t size);
 145
 146 static tre_ast_node_t *
 147 tre_ast_new_literal(tre_mem_t mem, int code_min, int code_max, int position);
 148
 149 static tre_ast_node_t *
 150 tre_ast_new_iter(tre_mem_t mem, tre_ast_node_t *arg, int min, int max,
 151                  int minimal);
 152
 153 static tre_ast_node_t *
 154 tre_ast_new_union(tre_mem_t mem, tre_ast_node_t *left, tre_ast_node_t *right);
 155
 156 static tre_ast_node_t *
 157 tre_ast_new_catenation(tre_mem_t mem, tre_ast_node_t *left,
 158                        tre_ast_node_t *right);
 159
 160
 161 static tre_ast_node_t *
 162 tre_ast_new_node(tre_mem_t mem, tre_ast_type_t type, size_t size)
 163 {
 164   tre_ast_node_t *node;
 165
 166   node = tre_mem_calloc(mem, sizeof(*node));
 167   if (!node)
 168     return NULL;
 169   node->obj = tre_mem_calloc(mem, size);
 170   if (!node->obj)
 171     return NULL;
 172   node->type = type;
 173   node->nullable = -1;
 174   node->submatch_id = -1;
 175
 176   return node;
 177 }
 178
 179 static tre_ast_node_t *
 180 tre_ast_new_literal(tre_mem_t mem, int code_min, int code_max, int position)
 181 {
 182   tre_ast_node_t *node;
 183   tre_literal_t *lit;
 184
 185   node = tre_ast_new_node(mem, LITERAL, sizeof(tre_literal_t));
 186   if (!node)
 187     return NULL;
 188   lit = node->obj;
 189   lit->code_min = code_min;
 190   lit->code_max = code_max;
 191   lit->position = position;
 192
 193   return node;
 194 }
 195
 196 static tre_ast_node_t *
 197 tre_ast_new_iter(tre_mem_t mem, tre_ast_node_t *arg, int min, int max,
 198                  int minimal)
 199 {
 200   tre_ast_node_t *node;
 201   tre_iteration_t *iter;
 202
 203   node = tre_ast_new_node(mem, ITERATION, sizeof(tre_iteration_t));
 204   if (!node)
 205     return NULL;
 206   iter = node->obj;
 207   iter->arg = arg;
 208   iter->min = min;
 209   iter->max = max;
 210   iter->minimal = minimal;
 211   node->num_submatches = arg->num_submatches;
 212
 213   return node;
 214 }
 215
 216 static tre_ast_node_t *
 217 tre_ast_new_union(tre_mem_t mem, tre_ast_node_t *left, tre_ast_node_t *right)
 218 {
 219   tre_ast_node_t *node;
 220
 221   node = tre_ast_new_node(mem, UNION, sizeof(tre_union_t));
 222   if (node == NULL)
 223     return NULL;
 224   ((tre_union_t *)node->obj)->left = left;
 225   ((tre_union_t *)node->obj)->right = right;
 226   node->num_submatches = left->num_submatches + right->num_submatches;
 227
 228   return node;
 229 }
 230
 231 static tre_ast_node_t *
 232 tre_ast_new_catenation(tre_mem_t mem, tre_ast_node_t *left,
 233                        tre_ast_node_t *right)
 234 {
 235   tre_ast_node_t *node;
 236
 237   node = tre_ast_new_node(mem, CATENATION, sizeof(tre_catenation_t));
 238   if (node == NULL)
 239     return NULL;
 240   ((tre_catenation_t *)node->obj)->left = left;
 241   ((tre_catenation_t *)node->obj)->right = right;
 242   node->num_submatches = left->num_submatches + right->num_submatches;
 243
 244   return node;
 245 }
 246
 247
 248 /***********************************************************************
 249  from tre-stack.c and tre-stack.h
 250 ***********************************************************************/
 251
 252 typedef struct tre_stack_rec tre_stack_t;
 253
 254 /* Creates a new stack object.  `size' is initial size in bytes, `max_size'
 255    is maximum size, and `increment' specifies how much more space will be
 256    allocated with realloc() if all space gets used up.  Returns the stack
 257    object or NULL if out of memory. */
 258 static tre_stack_t *
 259 tre_stack_new(int size, int max_size, int increment);
 260
 261 /* Frees the stack object. */
 262 static void
 263 tre_stack_destroy(tre_stack_t *s);
 264
 265 /* Returns the current number of objects in the stack. */
 266 static int
 267 tre_stack_num_objects(tre_stack_t *s);
 268
 269 /* Each tre_stack_push_*(tre_stack_t *s, <type> value) function pushes
 270    `value' on top of stack `s'.  Returns REG_ESPACE if out of memory.
 271    This tries to realloc() more space before failing if maximum size
 272    has not yet been reached.  Returns REG_OK if successful. */
 273 #define declare_pushf(typetag, type)                                          \
 274   static reg_errcode_t tre_stack_push_ ## typetag(tre_stack_t *s, type value)
 275
 276 declare_pushf(voidptr, void *);
 277 declare_pushf(int, int);
 278
 279 /* Each tre_stack_pop_*(tre_stack_t *s) function pops the topmost
 280    element off of stack `s' and returns it.  The stack must not be
 281    empty. */
 282 #define declare_popf(typetag, type)               \
 283   static type tre_stack_pop_ ## typetag(tre_stack_t *s)
 284
 285 declare_popf(voidptr, void *);
 286 declare_popf(int, int);
 287
 288 /* Just to save some typing. */
 289 #define STACK_PUSH(s, typetag, value)                                         \
 290   do                                                                          \
 291     {                                                                         \
 292       status = tre_stack_push_ ## typetag(s, value);                          \
 293     }                                                                         \
 294   while (/*CONSTCOND*/0)
 295
 296 #define STACK_PUSHX(s, typetag, value)                                        \
 297   {                                                                           \
 298     status = tre_stack_push_ ## typetag(s, value);                            \
 299     if (status != REG_OK)                                                     \
 300       break;                                                                  \
 301   }
 302
 303 #define STACK_PUSHR(s, typetag, value)                                        \
 304   {                                                                           \
 305     reg_errcode_t _status;                                                    \
 306     _status = tre_stack_push_ ## typetag(s, value);                           \
 307     if (_status != REG_OK)                                                    \
 308       return _status;                                                         \
 309   }
 310
 311 union tre_stack_item {
 312   void *voidptr_value;
 313   int int_value;
 314 };
 315
 316 struct tre_stack_rec {
 317   int size;
 318   int max_size;
 319   int increment;
 320   int ptr;
 321   union tre_stack_item *stack;
 322 };
 323
 324
 325 static tre_stack_t *
 326 tre_stack_new(int size, int max_size, int increment)
 327 {
 328   tre_stack_t *s;
 329
 330   s = xmalloc(sizeof(*s));
 331   if (s != NULL)
 332     {
 333       s->stack = xmalloc(sizeof(*s->stack) * size);
 334       if (s->stack == NULL)
 335         {
 336           xfree(s);
 337           return NULL;
 338         }
 339       s->size = size;
 340       s->max_size = max_size;
 341       s->increment = increment;
 342       s->ptr = 0;
 343     }
 344   return s;
 345 }
 346
 347 static void
 348 tre_stack_destroy(tre_stack_t *s)
 349 {
 350   xfree(s->stack);
 351   xfree(s);
 352 }
 353
 354 static int
 355 tre_stack_num_objects(tre_stack_t *s)
 356 {
 357   return s->ptr;
 358 }
 359
 360 static reg_errcode_t
 361 tre_stack_push(tre_stack_t *s, union tre_stack_item value)
 362 {
 363   if (s->ptr < s->size)
 364     {
 365       s->stack[s->ptr] = value;
 366       s->ptr++;
 367     }
 368   else
 369     {
 370       if (s->size >= s->max_size)
 371         {
 372           return REG_ESPACE;
 373         }
 374       else
 375         {
 376           union tre_stack_item *new_buffer;
 377           int new_size;
 378           new_size = s->size + s->increment;
 379           if (new_size > s->max_size)
 380             new_size = s->max_size;
 381           new_buffer = xrealloc(s->stack, sizeof(*new_buffer) * new_size);
 382           if (new_buffer == NULL)
 383             {
 384               return REG_ESPACE;
 385             }
 386           assert(new_size > s->size);
 387           s->size = new_size;
 388           s->stack = new_buffer;
 389           tre_stack_push(s, value);
 390         }
 391     }
 392   return REG_OK;
 393 }
 394
 395 #define define_pushf(typetag, type)  \
 396   declare_pushf(typetag, type) {     \
 397     union tre_stack_item item;       \
 398     item.typetag ## _value = value;  \
 399     return tre_stack_push(s, item);  \
 400 }
 401
 402 define_pushf(int, int)
 403 define_pushf(voidptr, void *)
 404
 405 #define define_popf(typetag, type)                  \
 406   declare_popf(typetag, type) {                     \
 407     return s->stack[--s->ptr].typetag ## _value;    \
 408   }
 409
 410 define_popf(int, int)
 411 define_popf(voidptr, void *)
 412
 413
 414 /***********************************************************************
 415  from tre-parse.c and tre-parse.h
 416 ***********************************************************************/
 417
 418 /* Parse context. */
 419 typedef struct {
 420   /* Memory allocator.  The AST is allocated using this. */
 421   tre_mem_t mem;
 422   /* Stack used for keeping track of regexp syntax. */
 423   tre_stack_t *stack;
 424   /* The parse result. */
 425   tre_ast_node_t *result;
 426   /* The regexp to parse and its length. */
 427   const char *re;
 428   /* The first character of the entire regexp. */
 429   const char *re_start;
 430   /* Current submatch ID. */
 431   int submatch_id;
 432   /* Current position (number of literal). */
 433   int position;
 434   /* The highest back reference or -1 if none seen so far. */
 435   int max_backref;
 436   /* This flag is set if the regexp uses approximate matching. */
 437   int have_approx;
 438   /* Compilation flags. */
 439   int cflags;
 440   /* If this flag is set the top-level submatch is not captured. */
 441   int nofirstsub;
 442 } tre_parse_ctx_t;
 443
 444 /* Parses a wide character regexp pattern into a syntax tree.  This parser
 445    handles both syntaxes (BRE and ERE), including the TRE extensions. */
 446 static reg_errcode_t
 447 tre_parse(tre_parse_ctx_t *ctx);
 448
 449
 450 /*
 451   This parser is just a simple recursive descent parser for POSIX.2
 452   regexps.  The parser supports both the obsolete default syntax and
 453   the "extended" syntax, and some nonstandard extensions.
 454 */
 455
 456 /* Characters with special meanings in regexp syntax. */
 457 #define CHAR_PIPE          '|'
 458 #define CHAR_LPAREN        '('
 459 #define CHAR_RPAREN        ')'
 460 #define CHAR_LBRACE        '{'
 461 #define CHAR_RBRACE        '}'
 462 #define CHAR_LBRACKET      '['
 463 #define CHAR_RBRACKET      ']'
 464 #define CHAR_MINUS         '-'
 465 #define CHAR_STAR          '*'
 466 #define CHAR_QUESTIONMARK  '?'
 467 #define CHAR_PLUS          '+'
 468 #define CHAR_PERIOD        '.'
 469 #define CHAR_COLON         ':'
 470 #define CHAR_EQUAL         '='
 471 #define CHAR_COMMA         ','
 472 #define CHAR_CARET         '^'
 473 #define CHAR_DOLLAR        '$'
 474 #define CHAR_BACKSLASH     '\\'
 475 #define CHAR_HASH          '#'
 476 #define CHAR_TILDE         '~'
 477
 478
 479 /* Some macros for expanding \w, \s, etc. */
 480 static const struct tre_macro_struct {
 481   const char c;
 482   const char *expansion;
 483 } tre_macros[] =
 484   { {'t', "\t"},           {'n', "\n"},            {'r', "\r"},
 485     {'f', "\f"},           {'a', "\a"},            {'e', "\033"},
 486     {'w', "[[:alnum:]_]"}, {'W', "[^[:alnum:]_]"}, {'s', "[[:space:]]"},
 487     {'S', "[^[:space:]]"}, {'d', "[[:digit:]]"},   {'D', "[^[:digit:]]"},
 488     { 0, NULL }
 489   };
 490
 491
 492 /* Expands a macro delimited by `regex' and `regex_end' to `buf', which
 493    must have at least `len' items.  Sets buf[0] to zero if the there
 494    is no match in `tre_macros'. */
 495 static const char *
 496 tre_expand_macro(const char *regex)
 497 {
 498   int i;
 499
 500   if (!*regex)
 501     return 0;
 502
 503   for (i = 0; tre_macros[i].expansion && tre_macros[i].c != *regex; i++);
 504   return tre_macros[i].expansion;
 505 }
 506
 507 static reg_errcode_t
 508 tre_new_item(tre_mem_t mem, int min, int max, int *i, int *max_i,
 509          tre_ast_node_t ***items)
 510 {
 511   reg_errcode_t status;
 512   tre_ast_node_t **array = *items;
 513   /* Allocate more space if necessary. */
 514   if (*i >= *max_i)
 515     {
 516       tre_ast_node_t **new_items;
 517       /* If the array is already 1024 items large, give up -- there's
 518          probably an error in the regexp (e.g. not a '\0' terminated
 519          string and missing ']') */
 520       if (*max_i > 1024)
 521         return REG_ESPACE;
 522       *max_i *= 2;
 523       new_items = xrealloc(array, sizeof(*items) * *max_i);
 524       if (new_items == NULL)
 525         return REG_ESPACE;
 526       *items = array = new_items;
 527     }
 528   array[*i] = tre_ast_new_literal(mem, min, max, -1);
 529   status = array[*i] == NULL ? REG_ESPACE : REG_OK;
 530   (*i)++;
 531   return status;
 532 }
 533
 534
 535 static int
 536 tre_compare_items(const void *a, const void *b)
 537 {
 538   const tre_ast_node_t *node_a = *(tre_ast_node_t * const *)a;
 539   const tre_ast_node_t *node_b = *(tre_ast_node_t * const *)b;
 540   tre_literal_t *l_a = node_a->obj, *l_b = node_b->obj;
 541   int a_min = l_a->code_min, b_min = l_b->code_min;
 542
 543   if (a_min < b_min)
 544     return -1;
 545   else if (a_min > b_min)
 546     return 1;
 547   else
 548     return 0;
 549 }
 550
 551 /* Maximum number of character classes that can occur in a negated bracket
 552    expression.  */
 553 #define MAX_NEG_CLASSES 64
 554
 555 /* Maximum length of character class names. */
 556 #define MAX_CLASS_NAME
 557
 558 static reg_errcode_t
 559 tre_parse_bracket_items(tre_parse_ctx_t *ctx, int negate,
 560                         tre_ctype_t neg_classes[], int *num_neg_classes,
 561                         tre_ast_node_t ***items, int *num_items,
 562                         int *items_size)
 563 {
 564   const char *re = ctx->re;
 565   reg_errcode_t status = REG_OK;
 566   tre_ctype_t class = (tre_ctype_t)0;
 567   int i = *num_items;
 568   int max_i = *items_size;
 569   int skip;
 570
 571   /* Build an array of the items in the bracket expression. */
 572   while (status == REG_OK)
 573     {
 574       skip = 0;
 575       if (!*re)
 576         {
 577           status = REG_EBRACK;
 578         }
 579       else if (*re == CHAR_RBRACKET && re > ctx->re)
 580         {
 581           re++;
 582           break;
 583         }
 584       else
 585         {
 586           tre_cint_t min = 0, max = 0;
 587           wchar_t wc;
 588           int clen = mbtowc(&wc, re, -1);
 589
 590           if (clen<0) clen=1, wc=WEOF;
 591
 592           class = (tre_ctype_t)0;
 593           if (*(re + clen) == CHAR_MINUS && *(re + clen + 1) != CHAR_RBRACKET)
 594             {
 595               min = wc;
 596               re += clen+1;
 597               clen = mbtowc(&wc, re, -1);
 598               if (clen<0) clen=1, wc=WEOF;
 599               max = wc;
 600               re += clen;
 601               /* XXX - Should use collation order instead of encoding values
 602                  in character ranges. */
 603               if (min > max)
 604                 status = REG_ERANGE;
 605             }
 606           else if (*re == CHAR_LBRACKET && *(re + 1) == CHAR_PERIOD)
 607             status = REG_ECOLLATE;
 608           else if (*re == CHAR_LBRACKET && *(re + 1) == CHAR_EQUAL)
 609             status = REG_ECOLLATE;
 610           else if (*re == CHAR_LBRACKET && *(re + 1) == CHAR_COLON)
 611             {
 612               char tmp_str[64];
 613               const char *endptr = re + 2;
 614               int len;
 615               while (*endptr && *endptr != CHAR_COLON)
 616                 endptr++;
 617               if (*endptr)
 618                 {
 619                   len = MIN(endptr - re - 2, 63);
 620                   strncpy(tmp_str, re + 2, len);
 621                   tmp_str[len] = '\0';
 622                   class = tre_ctype(tmp_str);
 623                   if (!class)
 624                     status = REG_ECTYPE;
 625                   re = endptr + 2;
 626                 }
 627               else
 628                 status = REG_ECTYPE;
 629               min = 0;
 630               max = TRE_CHAR_MAX;
 631             }
 632           else
 633             {
 634               if (*re == CHAR_MINUS && *(re + 1) != CHAR_RBRACKET
 635                   && ctx->re != re)
 636                 /* Two ranges are not allowed to share and endpoint. */
 637                 status = REG_ERANGE;
 638               min = max = wc;
 639               re += clen;
 640             }
 641
 642           if (status != REG_OK)
 643             break;
 644
 645           if (class && negate)
 646             if (*num_neg_classes >= MAX_NEG_CLASSES)
 647               status = REG_ESPACE;
 648             else
 649               neg_classes[(*num_neg_classes)++] = class;
 650           else if (!skip)
 651             {
 652               status = tre_new_item(ctx->mem, min, max, &i, &max_i, items);
 653               if (status != REG_OK)
 654                 break;
 655               ((tre_literal_t*)((*items)[i-1])->obj)->u.class = class;
 656             }
 657
 658           /* Add opposite-case counterpoints if REG_ICASE is present.
 659              This is broken if there are more than two "same" characters. */
 660           if (ctx->cflags & REG_ICASE && !class && status == REG_OK && !skip)
 661             {
 662               tre_cint_t cmin, ccurr;
 663
 664               while (min <= max)
 665                 {
 666                   if (tre_islower(min))
 667                     {
 668                       cmin = ccurr = tre_toupper(min++);
 669                       while (tre_islower(min) && tre_toupper(min) == ccurr + 1
 670                              && min <= max)
 671                         ccurr = tre_toupper(min++);
 672                       status = tre_new_item(ctx->mem, cmin, ccurr,
 673                                             &i, &max_i, items);
 674                     }
 675                   else if (tre_isupper(min))
 676                     {
 677                       cmin = ccurr = tre_tolower(min++);
 678                       while (tre_isupper(min) && tre_tolower(min) == ccurr + 1
 679                              && min <= max)
 680                         ccurr = tre_tolower(min++);
 681                       status = tre_new_item(ctx->mem, cmin, ccurr,
 682                                             &i, &max_i, items);
 683                     }
 684                   else min++;
 685                   if (status != REG_OK)
 686                     break;
 687                 }
 688               if (status != REG_OK)
 689                 break;
 690             }
 691         }
 692     }
 693   *num_items = i;
 694   *items_size = max_i;
 695   ctx->re = re;
 696   return status;
 697 }
 698
 699 static reg_errcode_t
 700 tre_parse_bracket(tre_parse_ctx_t *ctx, tre_ast_node_t **result)
 701 {
 702   tre_ast_node_t *node = NULL;
 703   int negate = 0;
 704   reg_errcode_t status = REG_OK;
 705   tre_ast_node_t **items, *u, *n;
 706   int i = 0, j, max_i = 32, curr_max, curr_min;
 707   tre_ctype_t neg_classes[MAX_NEG_CLASSES];
 708   int num_neg_classes = 0;
 709
 710   /* Start off with an array of `max_i' elements. */
 711   items = xmalloc(sizeof(*items) * max_i);
 712   if (items == NULL)
 713     return REG_ESPACE;
 714
 715   if (*ctx->re == CHAR_CARET)
 716     {
 717       negate = 1;
 718       ctx->re++;
 719     }
 720
 721   status = tre_parse_bracket_items(ctx, negate, neg_classes, &num_neg_classes,
 722                                    &items, &i, &max_i);
 723
 724   if (status != REG_OK)
 725     goto parse_bracket_done;
 726
 727   /* Sort the array if we need to negate it. */
 728   if (negate)
 729     qsort(items, (unsigned)i, sizeof(*items), tre_compare_items);
 730
 731   curr_max = curr_min = 0;
 732   /* Build a union of the items in the array, negated if necessary. */
 733   for (j = 0; j < i && status == REG_OK; j++)
 734     {
 735       int min, max;
 736       tre_literal_t *l = items[j]->obj;
 737       min = l->code_min;
 738       max = l->code_max;
 739
 740       if (negate)
 741         {
 742           if (min < curr_max)
 743             {
 744               /* Overlap. */
 745               curr_max = MAX(max + 1, curr_max);
 746               l = NULL;
 747             }
 748           else
 749             {
 750               /* No overlap. */
 751               curr_max = min - 1;
 752               if (curr_max >= curr_min)
 753                 {
 754                   l->code_min = curr_min;
 755                   l->code_max = curr_max;
 756                 }
 757               else
 758                 {
 759                   l = NULL;
 760                 }
 761               curr_min = curr_max = max + 1;
 762             }
 763         }
 764
 765       if (l != NULL)
 766         {
 767           int k;
 768           l->position = ctx->position;
 769           if (num_neg_classes > 0)
 770             {
 771               l->neg_classes = tre_mem_alloc(ctx->mem,
 772                                              (sizeof(l->neg_classes)
 773                                               * (num_neg_classes + 1)));
 774               if (l->neg_classes == NULL)
 775                 {
 776                   status = REG_ESPACE;
 777                   break;
 778                 }
 779               for (k = 0; k < num_neg_classes; k++)
 780                 l->neg_classes[k] = neg_classes[k];
 781               l->neg_classes[k] = (tre_ctype_t)0;
 782             }
 783           else
 784             l->neg_classes = NULL;
 785           if (node == NULL)
 786             node = items[j];
 787           else
 788             {
 789               u = tre_ast_new_union(ctx->mem, node, items[j]);
 790               if (u == NULL)
 791                 status = REG_ESPACE;
 792               node = u;
 793             }
 794         }
 795     }
 796
 797   if (status != REG_OK)
 798     goto parse_bracket_done;
 799
 800   if (negate)
 801     {
 802       int k;
 803       n = tre_ast_new_literal(ctx->mem, curr_min, TRE_CHAR_MAX, ctx->position);
 804       if (n == NULL)
 805         status = REG_ESPACE;
 806       else
 807         {
 808           tre_literal_t *l = n->obj;
 809           if (num_neg_classes > 0)
 810             {
 811               l->neg_classes = tre_mem_alloc(ctx->mem,
 812                                              (sizeof(l->neg_classes)
 813                                               * (num_neg_classes + 1)));
 814               if (l->neg_classes == NULL)
 815                 {
 816                   status = REG_ESPACE;
 817                   goto parse_bracket_done;
 818                 }
 819               for (k = 0; k < num_neg_classes; k++)
 820                 l->neg_classes[k] = neg_classes[k];
 821               l->neg_classes[k] = (tre_ctype_t)0;
 822             }
 823           else
 824             l->neg_classes = NULL;
 825           if (node == NULL)
 826             node = n;
 827           else
 828             {
 829               u = tre_ast_new_union(ctx->mem, node, n);
 830               if (u == NULL)
 831                 status = REG_ESPACE;
 832               node = u;
 833             }
 834         }
 835     }
 836
 837   if (status != REG_OK)
 838     goto parse_bracket_done;
 839
 840 #ifdef TRE_DEBUG
 841   tre_ast_print(node);
 842 #endif /* TRE_DEBUG */
 843
 844  parse_bracket_done:
 845   xfree(items);
 846   ctx->position++;
 847   *result = node;
 848   return status;
 849 }
 850
 851
 852 /* Parses a positive decimal integer.  Returns -1 if the string does not
 853    contain a valid number. */
 854 static int
 855 tre_parse_int(const char **regex)
 856 {
 857   int num = -1;
 858   const char *r = *regex;
 859   while (*r-'0'<10U)
 860     {
 861       if (num < 0)
 862         num = 0;
 863       num = num * 10 + *r - '0';
 864       r++;
 865     }
 866   *regex = r;
 867   return num;
 868 }
 869
 870
 871 static reg_errcode_t
 872 tre_parse_bound(tre_parse_ctx_t *ctx, tre_ast_node_t **result)
 873 {
 874   int min, max;
 875   const char *r = ctx->re;
 876   int minimal = 0;
 877
 878   /* Parse number (minimum repetition count). */
 879   min = -1;
 880   if (*r >= '0' && *r <= '9') {
 881     min = tre_parse_int(&r);
 882   }
 883
 884   /* Parse comma and second number (maximum repetition count). */
 885   max = min;
 886   if (*r == CHAR_COMMA)
 887     {
 888       r++;
 889       max = tre_parse_int(&r);
 890     }
 891
 892   /* Check that the repeat counts are sane. */
 893   if ((max >= 0 && min > max) || max > RE_DUP_MAX)
 894     return REG_BADBR;
 895
 896   /* Missing }. */
 897   if (!*r)
 898     return REG_EBRACE;
 899
 900   /* Empty contents of {}. */
 901   if (r == ctx->re)
 902     return REG_BADBR;
 903
 904   /* Parse the ending '}' or '\}'.*/
 905   if (ctx->cflags & REG_EXTENDED)
 906     {
 907       if (*r != CHAR_RBRACE)
 908         return REG_BADBR;
 909       r++;
 910     }
 911   else
 912     {
 913       if (*r != CHAR_BACKSLASH || *(r + 1) != CHAR_RBRACE)
 914         return REG_BADBR;
 915       r += 2;
 916     }
 917
 918   /* Create the AST node(s). */
 919   if (min == 0 && max == 0)
 920     {
 921       *result = tre_ast_new_literal(ctx->mem, EMPTY, -1, -1);
 922       if (*result == NULL)
 923         return REG_ESPACE;
 924     }
 925   else
 926     {
 927       if (min < 0 && max < 0)
 928         /* Only approximate parameters set, no repetitions. */
 929         min = max = 1;
 930
 931       *result = tre_ast_new_iter(ctx->mem, *result, min, max, minimal);
 932       if (!*result)
 933         return REG_ESPACE;
 934     }
 935
 936   ctx->re = r;
 937   return REG_OK;
 938 }
 939
 940 typedef enum {
 941   PARSE_RE = 0,
 942   PARSE_ATOM,
 943   PARSE_MARK_FOR_SUBMATCH,
 944   PARSE_BRANCH,
 945   PARSE_PIECE,
 946   PARSE_CATENATION,
 947   PARSE_POST_CATENATION,
 948   PARSE_UNION,
 949   PARSE_POST_UNION,
 950   PARSE_POSTFIX,
 951   PARSE_RESTORE_CFLAGS
 952 } tre_parse_re_stack_symbol_t;
 953
 954
 955 static reg_errcode_t
 956 tre_parse(tre_parse_ctx_t *ctx)
 957 {
 958   tre_ast_node_t *result = NULL;
 959   tre_parse_re_stack_symbol_t symbol;
 960   reg_errcode_t status = REG_OK;
 961   tre_stack_t *stack = ctx->stack;
 962   int bottom = tre_stack_num_objects(stack);
 963   int depth = 0;
 964
 965   if (!ctx->nofirstsub)
 966     {
 967       STACK_PUSH(stack, int, ctx->submatch_id);
 968       STACK_PUSH(stack, int, PARSE_MARK_FOR_SUBMATCH);
 969       ctx->submatch_id++;
 970     }
 971   STACK_PUSH(stack, int, PARSE_RE);
 972   ctx->re_start = ctx->re;
 973
 974
 975   /* The following is basically just a recursive descent parser.  I use
 976      an explicit stack instead of recursive functions mostly because of
 977      two reasons: compatibility with systems which have an overflowable
 978      call stack, and efficiency (both in lines of code and speed).  */
 979   while (tre_stack_num_objects(stack) > bottom && status == REG_OK)
 980     {
 981       if (status != REG_OK)
 982         break;
 983       symbol = tre_stack_pop_int(stack);
 984       switch (symbol)
 985         {
 986         case PARSE_RE:
 987           /* Parse a full regexp.  A regexp is one or more branches,
 988              separated by the union operator `|'. */
 989           if (ctx->cflags & REG_EXTENDED)
 990             STACK_PUSHX(stack, int, PARSE_UNION);
 991           STACK_PUSHX(stack, int, PARSE_BRANCH);
 992           break;
 993
 994         case PARSE_BRANCH:
 995           /* Parse a branch.  A branch is one or more pieces, concatenated.
 996              A piece is an atom possibly followed by a postfix operator. */
 997           STACK_PUSHX(stack, int, PARSE_CATENATION);
 998           STACK_PUSHX(stack, int, PARSE_PIECE);
 999           break;
1000
1001         case PARSE_PIECE:
1002           /* Parse a piece.  A piece is an atom possibly followed by one
1003              or more postfix operators. */
1004             STACK_PUSHX(stack, int, PARSE_POSTFIX);
1005           STACK_PUSHX(stack, int, PARSE_ATOM);
1006           break;
1007
1008         case PARSE_CATENATION:
1009           /* If the expression has not ended, parse another piece. */
1010           {
1011             tre_char_t c;
1012             if (!*ctx->re)
1013               break;
1014             c = *ctx->re;
1015                 if (ctx->cflags & REG_EXTENDED && c == CHAR_PIPE)
1016                   break;
1017                 if ((ctx->cflags & REG_EXTENDED
1018                      && c == CHAR_RPAREN && depth > 0)
1019                     || (!(ctx->cflags & REG_EXTENDED)
1020                         && (c == CHAR_BACKSLASH
1021                             && *(ctx->re + 1) == CHAR_RPAREN)))
1022                   {
1023                     if (!(ctx->cflags & REG_EXTENDED) && depth == 0)
1024                       status = REG_EPAREN;
1025                     depth--;
1026                     if (!(ctx->cflags & REG_EXTENDED))
1027                       ctx->re += 2;
1028                     break;
1029                   }
1030
1031               {
1032                 /* Default case, left associative concatenation. */
1033                 STACK_PUSHX(stack, int, PARSE_CATENATION);
1034                 STACK_PUSHX(stack, voidptr, result);
1035                 STACK_PUSHX(stack, int, PARSE_POST_CATENATION);
1036                 STACK_PUSHX(stack, int, PARSE_PIECE);
1037               }
1038             break;
1039           }
1040
1041         case PARSE_POST_CATENATION:
1042           {
1043             tre_ast_node_t *tree = tre_stack_pop_voidptr(stack);
1044             tre_ast_node_t *tmp_node;
1045             tmp_node = tre_ast_new_catenation(ctx->mem, tree, result);
1046             if (!tmp_node)
1047               return REG_ESPACE;
1048             result = tmp_node;
1049             break;
1050           }
1051
1052         case PARSE_UNION:
1053           if (!*ctx->re)
1054             break;
1055           switch (*ctx->re)
1056             {
1057             case CHAR_PIPE:
1058               STACK_PUSHX(stack, int, PARSE_UNION);
1059               STACK_PUSHX(stack, voidptr, result);
1060               STACK_PUSHX(stack, int, PARSE_POST_UNION);
1061               STACK_PUSHX(stack, int, PARSE_BRANCH);
1062               ctx->re++;
1063               break;
1064
1065             case CHAR_RPAREN:
1066               ctx->re++;
1067               break;
1068
1069             default:
1070               break;
1071             }
1072           break;
1073
1074         case PARSE_POST_UNION:
1075           {
1076             tre_ast_node_t *tmp_node;
1077             tre_ast_node_t *tree = tre_stack_pop_voidptr(stack);
1078             tmp_node = tre_ast_new_union(ctx->mem, tree, result);
1079             if (!tmp_node)
1080               return REG_ESPACE;
1081             result = tmp_node;
1082             break;
1083           }
1084
1085         case PARSE_POSTFIX:
1086           /* Parse postfix operators. */
1087           if (!*ctx->re)
1088             break;
1089           switch (*ctx->re)
1090             {
1091             case CHAR_PLUS:
1092             case CHAR_QUESTIONMARK:
1093               if (!(ctx->cflags & REG_EXTENDED))
1094                 break;
1095                 /*FALLTHROUGH*/
1096             case CHAR_STAR:
1097               {
1098                 tre_ast_node_t *tmp_node;
1099                 int minimal = 0;
1100                 int rep_min = 0;
1101                 int rep_max = -1;
1102
1103                 if (*ctx->re == CHAR_PLUS)
1104                   rep_min = 1;
1105                 if (*ctx->re == CHAR_QUESTIONMARK)
1106                   rep_max = 1;
1107
1108                   {
1109                     if (*(ctx->re + 1) == CHAR_QUESTIONMARK)
1110                       {
1111                         minimal = 1;
1112                         ctx->re++;
1113                       }
1114                     else if (*(ctx->re + 1) == CHAR_STAR
1115                              || *(ctx->re + 1) == CHAR_PLUS)
1116                       {
1117                         /* These are reserved for future extensions. */
1118                         return REG_BADRPT;
1119                       }
1120                   }
1121
1122                 ctx->re++;
1123                 tmp_node = tre_ast_new_iter(ctx->mem, result, rep_min, rep_max,
1124                                             minimal);
1125                 if (tmp_node == NULL)
1126                   return REG_ESPACE;
1127                 result = tmp_node;
1128                 STACK_PUSHX(stack, int, PARSE_POSTFIX);
1129               }
1130               break;
1131
1132             case CHAR_BACKSLASH:
1133               /* "\{" is special without REG_EXTENDED */
1134               if (!(ctx->cflags & REG_EXTENDED)
1135                   && *(ctx->re + 1) == CHAR_LBRACE)
1136                 {
1137                   ctx->re++;
1138                   goto parse_brace;
1139                 }
1140               else
1141                 break;
1142
1143             case CHAR_LBRACE:
1144               /* "{" is literal without REG_EXTENDED */
1145               if (!(ctx->cflags & REG_EXTENDED))
1146                 break;
1147
1148             parse_brace:
1149               ctx->re++;
1150
1151               status = tre_parse_bound(ctx, &result);
1152               if (status != REG_OK)
1153                 return status;
1154               STACK_PUSHX(stack, int, PARSE_POSTFIX);
1155               break;
1156             }
1157           break;
1158
1159         case PARSE_ATOM:
1160           /* Parse an atom.  An atom is a regular expression enclosed in `()',
1161              an empty set of `()', a bracket expression, `.', `^', `$',
1162              a `\' followed by a character, or a single character. */
1163
1164           /* End of regexp? (empty string). */
1165           if (!*ctx->re)
1166             goto parse_literal;
1167
1168           switch (*ctx->re)
1169             {
1170             case CHAR_LPAREN:  /* parenthesized subexpression */
1171
1172               if (ctx->cflags & REG_EXTENDED
1173                   || (ctx->re > ctx->re_start
1174                       && *(ctx->re - 1) == CHAR_BACKSLASH))
1175                 {
1176                   depth++;
1177                     {
1178                       ctx->re++;
1179                       /* First parse a whole RE, then mark the resulting tree
1180                          for submatching. */
1181                       STACK_PUSHX(stack, int, ctx->submatch_id);
1182                       STACK_PUSHX(stack, int, PARSE_MARK_FOR_SUBMATCH);
1183                       STACK_PUSHX(stack, int, PARSE_RE);
1184                       ctx->submatch_id++;
1185                     }
1186                 }
1187               else
1188                 goto parse_literal;
1189               break;
1190
1191             case CHAR_RPAREN:  /* end of current subexpression */
1192               if ((ctx->cflags & REG_EXTENDED && depth > 0)
1193                   || (ctx->re > ctx->re_start
1194                       && *(ctx->re - 1) == CHAR_BACKSLASH))
1195                 {
1196                   /* We were expecting an atom, but instead the current
1197                      subexpression was closed.  POSIX leaves the meaning of
1198                      this to be implementation-defined.  We interpret this as
1199                      an empty expression (which matches an empty string).  */
1200                   result = tre_ast_new_literal(ctx->mem, EMPTY, -1, -1);
1201                   if (result == NULL)
1202                     return REG_ESPACE;
1203                   if (!(ctx->cflags & REG_EXTENDED))
1204                     ctx->re--;
1205                 }
1206               else
1207                 goto parse_literal;
1208               break;
1209
1210             case CHAR_LBRACKET: /* bracket expression */
1211               ctx->re++;
1212               status = tre_parse_bracket(ctx, &result);
1213               if (status != REG_OK)
1214                 return status;
1215               break;
1216
1217             case CHAR_BACKSLASH:
1218               /* If this is "\(" or "\)" chew off the backslash and
1219                  try again. */
1220               if (!(ctx->cflags & REG_EXTENDED)
1221                   && (*(ctx->re + 1) == CHAR_LPAREN
1222                       || *(ctx->re + 1) == CHAR_RPAREN))
1223                 {
1224                   ctx->re++;
1225                   STACK_PUSHX(stack, int, PARSE_ATOM);
1226                   break;
1227                 }
1228
1229               /* If a macro is used, parse the expanded macro recursively. */
1230               {
1231                 const char *buf = tre_expand_macro(ctx->re + 1);
1232                 if (buf)
1233                   {
1234                     tre_parse_ctx_t subctx;
1235                     memcpy(&subctx, ctx, sizeof(subctx));
1236                     subctx.re = buf;
1237                     subctx.nofirstsub = 1;
1238                     status = tre_parse(&subctx);
1239                     if (status != REG_OK)
1240                       return status;
1241                     ctx->re += 2;
1242                     ctx->position = subctx.position;
1243                     result = subctx.result;
1244                     break;
1245                   }
1246               }
1247
1248               if (!*ctx->re)
1249                 /* Trailing backslash. */
1250                 return REG_EESCAPE;
1251
1252               ctx->re++;
1253               switch (*ctx->re)
1254                 {
1255                 case 'b':
1256                   result = tre_ast_new_literal(ctx->mem, ASSERTION,
1257                                                ASSERT_AT_WB, -1);
1258                   ctx->re++;
1259                   break;
1260                 case 'B':
1261                   result = tre_ast_new_literal(ctx->mem, ASSERTION,
1262                                                ASSERT_AT_WB_NEG, -1);
1263                   ctx->re++;
1264                   break;
1265                 case '<':
1266                   result = tre_ast_new_literal(ctx->mem, ASSERTION,
1267                                                ASSERT_AT_BOW, -1);
1268                   ctx->re++;
1269                   break;
1270                 case '>':
1271                   result = tre_ast_new_literal(ctx->mem, ASSERTION,
1272                                                ASSERT_AT_EOW, -1);
1273                   ctx->re++;
1274                   break;
1275                 case 'x':
1276                   ctx->re++;
1277                   if (ctx->re[0] != CHAR_LBRACE)
1278                     {
1279                       /* 8 bit hex char. */
1280                       char tmp[3] = {0, 0, 0};
1281                       long val;
1282
1283                       if (tre_isxdigit(ctx->re[0]))
1284                         {
1285                           tmp[0] = (char)ctx->re[0];
1286                           ctx->re++;
1287                         }
1288                       if (tre_isxdigit(ctx->re[0]))
1289                         {
1290                           tmp[1] = (char)ctx->re[0];
1291                           ctx->re++;
1292                         }
1293                       val = strtol(tmp, NULL, 16);
1294                       result = tre_ast_new_literal(ctx->mem, (int)val,
1295                                                    (int)val, ctx->position);
1296                       ctx->position++;
1297                       break;
1298                     }
1299                   else if (*ctx->re)
1300                     {
1301                       /* Wide char. */
1302                       char tmp[32];
1303                       long val;
1304                       int i = 0;
1305                       ctx->re++;
1306                       while (*ctx->re && i < sizeof tmp)
1307                         {
1308                           if (ctx->re[0] == CHAR_RBRACE)
1309                             break;
1310                           if (tre_isxdigit(ctx->re[0]))
1311                             {
1312                               tmp[i] = (char)ctx->re[0];
1313                               i++;
1314                               ctx->re++;
1315                               continue;
1316                             }
1317                           return REG_EBRACE;
1318                         }
1319                       ctx->re++;
1320                       tmp[i] = 0;
1321                       val = strtol(tmp, NULL, 16);
1322                       result = tre_ast_new_literal(ctx->mem, (int)val, (int)val,
1323                                                    ctx->position);
1324                       ctx->position++;
1325                       break;
1326                     }
1327                   /*FALLTHROUGH*/
1328
1329                 default:
1330                   if (tre_isdigit(*ctx->re))
1331                     {
1332                       /* Back reference. */
1333                       int val = *ctx->re - '0';
1334                       result = tre_ast_new_literal(ctx->mem, BACKREF, val,
1335                                                    ctx->position);
1336                       if (result == NULL)
1337                         return REG_ESPACE;
1338                       ctx->position++;
1339                       ctx->max_backref = MAX(val, ctx->max_backref);
1340                       ctx->re++;
1341                     }
1342                   else
1343                     {
1344                       /* Escaped character. */
1345                       result = tre_ast_new_literal(ctx->mem, *ctx->re, *ctx->re,
1346                                                    ctx->position);
1347                       ctx->position++;
1348                       ctx->re++;
1349                     }
1350                   break;
1351                 }
1352               if (result == NULL)
1353                 return REG_ESPACE;
1354               break;
1355
1356             case CHAR_PERIOD:    /* the any-symbol */
1357               if (ctx->cflags & REG_NEWLINE)
1358                 {
1359                   tre_ast_node_t *tmp1;
1360                   tre_ast_node_t *tmp2;
1361                   tmp1 = tre_ast_new_literal(ctx->mem, 0, '\n' - 1,
1362                                              ctx->position);
1363                   if (!tmp1)
1364                     return REG_ESPACE;
1365                   tmp2 = tre_ast_new_literal(ctx->mem, '\n' + 1, TRE_CHAR_MAX,
1366                                              ctx->position + 1);
1367                   if (!tmp2)
1368                     return REG_ESPACE;
1369                   result = tre_ast_new_union(ctx->mem, tmp1, tmp2);
1370                   if (!result)
1371                     return REG_ESPACE;
1372                   ctx->position += 2;
1373                 }
1374               else
1375                 {
1376                   result = tre_ast_new_literal(ctx->mem, 0, TRE_CHAR_MAX,
1377                                                ctx->position);
1378                   if (!result)
1379                     return REG_ESPACE;
1380                   ctx->position++;
1381                 }
1382               ctx->re++;
1383               break;
1384
1385             case CHAR_CARET:     /* beginning of line assertion */
1386               /* '^' has a special meaning everywhere in EREs, and in the
1387                  beginning of the RE and after \( is BREs. */
1388               if (ctx->cflags & REG_EXTENDED
1389                   || (ctx->re - 2 >= ctx->re_start
1390                       && *(ctx->re - 2) == CHAR_BACKSLASH
1391                       && *(ctx->re - 1) == CHAR_LPAREN)
1392                   || ctx->re == ctx->re_start)
1393                 {
1394                   result = tre_ast_new_literal(ctx->mem, ASSERTION,
1395                                                ASSERT_AT_BOL, -1);
1396                   if (result == NULL)
1397                     return REG_ESPACE;
1398                   ctx->re++;
1399                 }
1400               else
1401                 goto parse_literal;
1402               break;
1403
1404             case CHAR_DOLLAR:    /* end of line assertion. */
1405               /* '$' is special everywhere in EREs, and in the end of the
1406                  string and before \) is BREs. */
1407               if (ctx->cflags & REG_EXTENDED
1408                   || (*(ctx->re + 1) == CHAR_BACKSLASH
1409                       && *(ctx->re + 2) == CHAR_RPAREN)
1410                   || !*(ctx->re + 1))
1411                 {
1412                   result = tre_ast_new_literal(ctx->mem, ASSERTION,
1413                                                ASSERT_AT_EOL, -1);
1414                   if (result == NULL)
1415                     return REG_ESPACE;
1416                   ctx->re++;
1417                 }
1418               else
1419                 goto parse_literal;
1420               break;
1421
1422             default:
1423             parse_literal:
1424
1425               /* We are expecting an atom.  If the subexpression (or the whole
1426                  regexp ends here, we interpret it as an empty expression
1427                  (which matches an empty string).  */
1428               if (
1429                   (!*ctx->re
1430                    || *ctx->re == CHAR_STAR
1431                    || (ctx->cflags & REG_EXTENDED
1432                        && (*ctx->re == CHAR_PIPE
1433                            || *ctx->re == CHAR_LBRACE
1434                            || *ctx->re == CHAR_PLUS
1435                            || *ctx->re == CHAR_QUESTIONMARK))
1436                    /* Test for "\)" in BRE mode. */
1437                    || (!(ctx->cflags & REG_EXTENDED)
1438                        && !*(ctx->re + 1)
1439                        && *ctx->re == CHAR_BACKSLASH
1440                        && *(ctx->re + 1) == CHAR_LBRACE)))
1441                 {
1442                   result = tre_ast_new_literal(ctx->mem, EMPTY, -1, -1);
1443                   if (!result)
1444                     return REG_ESPACE;
1445                   break;
1446                 }
1447
1448               wchar_t wc;
1449               int clen = mbtowc(&wc, ctx->re, -1);
1450               if (clen<0) clen=1, wc=WEOF;
1451
1452               /* Note that we can't use an tre_isalpha() test here, since there
1453                  may be characters which are alphabetic but neither upper or
1454                  lower case. */
1455               if (ctx->cflags & REG_ICASE
1456                   && (tre_isupper(wc) || tre_islower(wc)))
1457                 {
1458                   tre_ast_node_t *tmp1;
1459                   tre_ast_node_t *tmp2;
1460
1461                   /* XXX - Can there be more than one opposite-case
1462                      counterpoints for some character in some locale?  Or
1463                      more than two characters which all should be regarded
1464                      the same character if case is ignored?  If yes, there
1465                      does not seem to be a portable way to detect it.  I guess
1466                      that at least for multi-character collating elements there
1467                      could be several opposite-case counterpoints, but they
1468                      cannot be supported portably anyway. */
1469                   tmp1 = tre_ast_new_literal(ctx->mem, tre_toupper(wc),
1470                                              tre_toupper(wc),
1471                                              ctx->position);
1472                   if (!tmp1)
1473                     return REG_ESPACE;
1474                   tmp2 = tre_ast_new_literal(ctx->mem, tre_tolower(wc),
1475                                              tre_tolower(wc),
1476                                              ctx->position);
1477                   if (!tmp2)
1478                     return REG_ESPACE;
1479                   result = tre_ast_new_union(ctx->mem, tmp1, tmp2);
1480                   if (!result)
1481                     return REG_ESPACE;
1482                 }
1483               else
1484                 {
1485                   result = tre_ast_new_literal(ctx->mem, wc, wc,
1486                                                ctx->position);
1487                   if (!result)
1488                     return REG_ESPACE;
1489                 }
1490               ctx->position++;
1491               ctx->re += clen;
1492               break;
1493             }
1494           break;
1495
1496         case PARSE_MARK_FOR_SUBMATCH:
1497           {
1498             int submatch_id = tre_stack_pop_int(stack);
1499
1500             if (result->submatch_id >= 0)
1501               {
1502                 tre_ast_node_t *n, *tmp_node;
1503                 n = tre_ast_new_literal(ctx->mem, EMPTY, -1, -1);
1504                 if (n == NULL)
1505                   return REG_ESPACE;
1506                 tmp_node = tre_ast_new_catenation(ctx->mem, n, result);
1507                 if (tmp_node == NULL)
1508                   return REG_ESPACE;
1509                 tmp_node->num_submatches = result->num_submatches;
1510                 result = tmp_node;
1511               }
1512             result->submatch_id = submatch_id;
1513             result->num_submatches++;
1514             break;
1515           }
1516
1517         case PARSE_RESTORE_CFLAGS:
1518           ctx->cflags = tre_stack_pop_int(stack);
1519           break;
1520
1521         default:
1522           assert(0);
1523           break;
1524         }
1525     }
1526
1527   /* Check for missing closing parentheses. */
1528   if (depth > 0)
1529     return REG_EPAREN;
1530
1531   if (status == REG_OK)
1532     ctx->result = result;
1533
1534   return status;
1535 }
1536
1537
1538
1539 /***********************************************************************
1540  from tre-compile.c
1541 ***********************************************************************/
1542
1543
1544 /*
1545   TODO:
1546    - Fix tre_ast_to_tnfa() to recurse using a stack instead of recursive
1547      function calls.
1548 */
1549
1550 /*
1551   Algorithms to setup tags so that submatch addressing can be done.
1552 */
1553
1554
1555 /* Inserts a catenation node to the root of the tree given in `node'.
1556    As the left child a new tag with number `tag_id' to `node' is added,
1557    and the right child is the old root. */
1558 static reg_errcode_t
1559 tre_add_tag_left(tre_mem_t mem, tre_ast_node_t *node, int tag_id)
1560 {
1561   tre_catenation_t *c;
1562
1563   c = tre_mem_alloc(mem, sizeof(*c));
1564   if (c == NULL)
1565     return REG_ESPACE;
1566   c->left = tre_ast_new_literal(mem, TAG, tag_id, -1);
1567   if (c->left == NULL)
1568     return REG_ESPACE;
1569   c->right = tre_mem_alloc(mem, sizeof(tre_ast_node_t));
1570   if (c->right == NULL)
1571     return REG_ESPACE;
1572
1573   c->right->obj = node->obj;
1574   c->right->type = node->type;
1575   c->right->nullable = -1;
1576   c->right->submatch_id = -1;
1577   c->right->firstpos = NULL;
1578   c->right->lastpos = NULL;
1579   c->right->num_tags = 0;
1580   node->obj = c;
1581   node->type = CATENATION;
1582   return REG_OK;
1583 }
1584
1585 /* Inserts a catenation node to the root of the tree given in `node'.
1586    As the right child a new tag with number `tag_id' to `node' is added,
1587    and the left child is the old root. */
1588 static reg_errcode_t
1589 tre_add_tag_right(tre_mem_t mem, tre_ast_node_t *node, int tag_id)
1590 {
1591   tre_catenation_t *c;
1592
1593   c = tre_mem_alloc(mem, sizeof(*c));
1594   if (c == NULL)
1595     return REG_ESPACE;
1596   c->right = tre_ast_new_literal(mem, TAG, tag_id, -1);
1597   if (c->right == NULL)
1598     return REG_ESPACE;
1599   c->left = tre_mem_alloc(mem, sizeof(tre_ast_node_t));
1600   if (c->left == NULL)
1601     return REG_ESPACE;
1602
1603   c->left->obj = node->obj;
1604   c->left->type = node->type;
1605   c->left->nullable = -1;
1606   c->left->submatch_id = -1;
1607   c->left->firstpos = NULL;
1608   c->left->lastpos = NULL;
1609   c->left->num_tags = 0;
1610   node->obj = c;
1611   node->type = CATENATION;
1612   return REG_OK;
1613 }
1614
1615 typedef enum {
1616   ADDTAGS_RECURSE,
1617   ADDTAGS_AFTER_ITERATION,
1618   ADDTAGS_AFTER_UNION_LEFT,
1619   ADDTAGS_AFTER_UNION_RIGHT,
1620   ADDTAGS_AFTER_CAT_LEFT,
1621   ADDTAGS_AFTER_CAT_RIGHT,
1622   ADDTAGS_SET_SUBMATCH_END
1623 } tre_addtags_symbol_t;
1624
1625
1626 typedef struct {
1627   int tag;
1628   int next_tag;
1629 } tre_tag_states_t;
1630
1631
1632 /* Go through `regset' and set submatch data for submatches that are
1633    using this tag. */
1634 static void
1635 tre_purge_regset(int *regset, tre_tnfa_t *tnfa, int tag)
1636 {
1637   int i;
1638
1639   for (i = 0; regset[i] >= 0; i++)
1640     {
1641       int id = regset[i] / 2;
1642       int start = !(regset[i] % 2);
1643       if (start)
1644         tnfa->submatch_data[id].so_tag = tag;
1645       else
1646         tnfa->submatch_data[id].eo_tag = tag;
1647     }
1648   regset[0] = -1;
1649 }
1650
1651
1652 /* Adds tags to appropriate locations in the parse tree in `tree', so that
1653    subexpressions marked for submatch addressing can be traced. */
1654 static reg_errcode_t
1655 tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree,
1656              tre_tnfa_t *tnfa)
1657 {
1658   reg_errcode_t status = REG_OK;
1659   tre_addtags_symbol_t symbol;
1660   tre_ast_node_t *node = tree; /* Tree node we are currently looking at. */
1661   int bottom = tre_stack_num_objects(stack);
1662   /* True for first pass (counting number of needed tags) */
1663   int first_pass = (mem == NULL || tnfa == NULL);
1664   int *regset, *orig_regset;
1665   int num_tags = 0; /* Total number of tags. */
1666   int num_minimals = 0;  /* Number of special minimal tags. */
1667   int tag = 0;      /* The tag that is to be added next. */
1668   int next_tag = 1; /* Next tag to use after this one. */
1669   int *parents;     /* Stack of submatches the current submatch is
1670                        contained in. */
1671   int minimal_tag = -1; /* Tag that marks the beginning of a minimal match. */
1672   tre_tag_states_t *saved_states;
1673
1674   tre_tag_direction_t direction = TRE_TAG_MINIMIZE;
1675   if (!first_pass)
1676     {
1677       tnfa->end_tag = 0;
1678       tnfa->minimal_tags[0] = -1;
1679     }
1680
1681   regset = xmalloc(sizeof(*regset) * ((tnfa->num_submatches + 1) * 2));
1682   if (regset == NULL)
1683     return REG_ESPACE;
1684   regset[0] = -1;
1685   orig_regset = regset;
1686
1687   parents = xmalloc(sizeof(*parents) * (tnfa->num_submatches + 1));
1688   if (parents == NULL)
1689     {
1690       xfree(regset);
1691       return REG_ESPACE;
1692     }
1693   parents[0] = -1;
1694
1695   saved_states = xmalloc(sizeof(*saved_states) * (tnfa->num_submatches + 1));
1696   if (saved_states == NULL)
1697     {
1698       xfree(regset);
1699       xfree(parents);
1700       return REG_ESPACE;
1701     }
1702   else
1703     {
1704       unsigned int i;
1705       for (i = 0; i <= tnfa->num_submatches; i++)
1706         saved_states[i].tag = -1;
1707     }
1708
1709   STACK_PUSH(stack, voidptr, node);
1710   STACK_PUSH(stack, int, ADDTAGS_RECURSE);
1711
1712   while (tre_stack_num_objects(stack) > bottom)
1713     {
1714       if (status != REG_OK)
1715         break;
1716
1717       symbol = (tre_addtags_symbol_t)tre_stack_pop_int(stack);
1718       switch (symbol)
1719         {
1720
1721         case ADDTAGS_SET_SUBMATCH_END:
1722           {
1723             int id = tre_stack_pop_int(stack);
1724             int i;
1725
1726             /* Add end of this submatch to regset. */
1727             for (i = 0; regset[i] >= 0; i++);
1728             regset[i] = id * 2 + 1;
1729             regset[i + 1] = -1;
1730
1731             /* Pop this submatch from the parents stack. */
1732             for (i = 0; parents[i] >= 0; i++);
1733             parents[i - 1] = -1;
1734             break;
1735           }
1736
1737         case ADDTAGS_RECURSE:
1738           node = tre_stack_pop_voidptr(stack);
1739
1740           if (node->submatch_id >= 0)
1741             {
1742               int id = node->submatch_id;
1743               int i;
1744
1745
1746               /* Add start of this submatch to regset. */
1747               for (i = 0; regset[i] >= 0; i++);
1748               regset[i] = id * 2;
1749               regset[i + 1] = -1;
1750
1751               if (!first_pass)
1752                 {
1753                   for (i = 0; parents[i] >= 0; i++);
1754                   tnfa->submatch_data[id].parents = NULL;
1755                   if (i > 0)
1756                     {
1757                       int *p = xmalloc(sizeof(*p) * (i + 1));
1758                       if (p == NULL)
1759                         {
1760                           status = REG_ESPACE;
1761                           break;
1762                         }
1763                       assert(tnfa->submatch_data[id].parents == NULL);
1764                       tnfa->submatch_data[id].parents = p;
1765                       for (i = 0; parents[i] >= 0; i++)
1766                         p[i] = parents[i];
1767                       p[i] = -1;
1768                     }
1769                 }
1770
1771               /* Add end of this submatch to regset after processing this
1772                  node. */
1773               STACK_PUSHX(stack, int, node->submatch_id);
1774               STACK_PUSHX(stack, int, ADDTAGS_SET_SUBMATCH_END);
1775             }
1776
1777           switch (node->type)
1778             {
1779             case LITERAL:
1780               {
1781                 tre_literal_t *lit = node->obj;
1782
1783                 if (!IS_SPECIAL(lit) || IS_BACKREF(lit))
1784                   {
1785                     int i;
1786                     if (regset[0] >= 0)
1787                       {
1788                         /* Regset is not empty, so add a tag before the
1789                            literal or backref. */
1790                         if (!first_pass)
1791                           {
1792                             status = tre_add_tag_left(mem, node, tag);
1793                             tnfa->tag_directions[tag] = direction;
1794                             if (minimal_tag >= 0)
1795                               {
1796                                 for (i = 0; tnfa->minimal_tags[i] >= 0; i++);
1797                                 tnfa->minimal_tags[i] = tag;
1798                                 tnfa->minimal_tags[i + 1] = minimal_tag;
1799                                 tnfa->minimal_tags[i + 2] = -1;
1800                                 minimal_tag = -1;
1801                                 num_minimals++;
1802                               }
1803                             tre_purge_regset(regset, tnfa, tag);
1804                           }
1805                         else
1806                           {
1807                             node->num_tags = 1;
1808                           }
1809
1810                         regset[0] = -1;
1811                         tag = next_tag;
1812                         num_tags++;
1813                         next_tag++;
1814                       }
1815                   }
1816                 else
1817                   {
1818                     assert(!IS_TAG(lit));
1819                   }
1820                 break;
1821               }
1822             case CATENATION:
1823               {
1824                 tre_catenation_t *cat = node->obj;
1825                 tre_ast_node_t *left = cat->left;
1826                 tre_ast_node_t *right = cat->right;
1827                 int reserved_tag = -1;
1828
1829
1830                 /* After processing right child. */
1831                 STACK_PUSHX(stack, voidptr, node);
1832                 STACK_PUSHX(stack, int, ADDTAGS_AFTER_CAT_RIGHT);
1833
1834                 /* Process right child. */
1835                 STACK_PUSHX(stack, voidptr, right);
1836                 STACK_PUSHX(stack, int, ADDTAGS_RECURSE);
1837
1838                 /* After processing left child. */
1839                 STACK_PUSHX(stack, int, next_tag + left->num_tags);
1840                 if (left->num_tags > 0 && right->num_tags > 0)
1841                   {
1842                     /* Reserve the next tag to the right child. */
1843                     reserved_tag = next_tag;
1844                     next_tag++;
1845                   }
1846                 STACK_PUSHX(stack, int, reserved_tag);
1847                 STACK_PUSHX(stack, int, ADDTAGS_AFTER_CAT_LEFT);
1848
1849                 /* Process left child. */
1850                 STACK_PUSHX(stack, voidptr, left);
1851                 STACK_PUSHX(stack, int, ADDTAGS_RECURSE);
1852
1853                 }
1854               break;
1855             case ITERATION:
1856               {
1857                 tre_iteration_t *iter = node->obj;
1858
1859                 if (first_pass)
1860                   {
1861                     STACK_PUSHX(stack, int, regset[0] >= 0 || iter->minimal);
1862                   }
1863                 else
1864                   {
1865                     STACK_PUSHX(stack, int, tag);
1866                     STACK_PUSHX(stack, int, iter->minimal);
1867                   }
1868                 STACK_PUSHX(stack, voidptr, node);
1869                 STACK_PUSHX(stack, int, ADDTAGS_AFTER_ITERATION);
1870
1871                 STACK_PUSHX(stack, voidptr, iter->arg);
1872                 STACK_PUSHX(stack, int, ADDTAGS_RECURSE);
1873
1874                 /* Regset is not empty, so add a tag here. */
1875                 if (regset[0] >= 0 || iter->minimal)
1876                   {
1877                     if (!first_pass)
1878                       {
1879                         int i;
1880                         status = tre_add_tag_left(mem, node, tag);
1881                         if (iter->minimal)
1882                           tnfa->tag_directions[tag] = TRE_TAG_MAXIMIZE;
1883                         else
1884                           tnfa->tag_directions[tag] = direction;
1885                         if (minimal_tag >= 0)
1886                           {
1887                             for (i = 0; tnfa->minimal_tags[i] >= 0; i++);
1888                             tnfa->minimal_tags[i] = tag;
1889                             tnfa->minimal_tags[i + 1] = minimal_tag;
1890                             tnfa->minimal_tags[i + 2] = -1;
1891                             minimal_tag = -1;
1892                             num_minimals++;
1893                           }
1894                         tre_purge_regset(regset, tnfa, tag);
1895                       }
1896
1897                     regset[0] = -1;
1898                     tag = next_tag;
1899                     num_tags++;
1900                     next_tag++;
1901                   }
1902                 direction = TRE_TAG_MINIMIZE;
1903               }
1904               break;
1905             case UNION:
1906               {
1907                 tre_union_t *uni = node->obj;
1908                 tre_ast_node_t *left = uni->left;
1909                 tre_ast_node_t *right = uni->right;
1910                 int left_tag;
1911                 int right_tag;
1912
1913                 if (regset[0] >= 0)
1914                   {
1915                     left_tag = next_tag;
1916                     right_tag = next_tag + 1;
1917                   }
1918                 else
1919                   {
1920                     left_tag = tag;
1921                     right_tag = next_tag;
1922                   }
1923
1924                 /* After processing right child. */
1925                 STACK_PUSHX(stack, int, right_tag);
1926                 STACK_PUSHX(stack, int, left_tag);
1927                 STACK_PUSHX(stack, voidptr, regset);
1928                 STACK_PUSHX(stack, int, regset[0] >= 0);
1929                 STACK_PUSHX(stack, voidptr, node);
1930                 STACK_PUSHX(stack, voidptr, right);
1931                 STACK_PUSHX(stack, voidptr, left);
1932                 STACK_PUSHX(stack, int, ADDTAGS_AFTER_UNION_RIGHT);
1933
1934                 /* Process right child. */
1935                 STACK_PUSHX(stack, voidptr, right);
1936                 STACK_PUSHX(stack, int, ADDTAGS_RECURSE);
1937
1938                 /* After processing left child. */
1939                 STACK_PUSHX(stack, int, ADDTAGS_AFTER_UNION_LEFT);
1940
1941                 /* Process left child. */
1942                 STACK_PUSHX(stack, voidptr, left);
1943                 STACK_PUSHX(stack, int, ADDTAGS_RECURSE);
1944
1945                 /* Regset is not empty, so add a tag here. */
1946                 if (regset[0] >= 0)
1947                   {
1948                     if (!first_pass)
1949                       {
1950                         int i;
1951                         status = tre_add_tag_left(mem, node, tag);
1952                         tnfa->tag_directions[tag] = direction;
1953                         if (minimal_tag >= 0)
1954                           {
1955                             for (i = 0; tnfa->minimal_tags[i] >= 0; i++);
1956                             tnfa->minimal_tags[i] = tag;
1957                             tnfa->minimal_tags[i + 1] = minimal_tag;
1958                             tnfa->minimal_tags[i + 2] = -1;
1959                             minimal_tag = -1;
1960                             num_minimals++;
1961                           }
1962                         tre_purge_regset(regset, tnfa, tag);
1963                       }
1964
1965                     regset[0] = -1;
1966                     tag = next_tag;
1967                     num_tags++;
1968                     next_tag++;
1969                   }
1970
1971                 if (node->num_submatches > 0)
1972                   {
1973                     /* The next two tags are reserved for markers. */
1974                     next_tag++;
1975                     tag = next_tag;
1976                     next_tag++;
1977                   }
1978
1979                 break;
1980               }
1981             }
1982
1983           if (node->submatch_id >= 0)
1984             {
1985               int i;
1986               /* Push this submatch on the parents stack. */
1987               for (i = 0; parents[i] >= 0; i++);
1988               parents[i] = node->submatch_id;
1989               parents[i + 1] = -1;
1990             }
1991
1992           break; /* end case: ADDTAGS_RECURSE */
1993
1994         case ADDTAGS_AFTER_ITERATION:
1995           {
1996             int minimal = 0;
1997             int enter_tag;
1998             node = tre_stack_pop_voidptr(stack);
1999             if (first_pass)
2000               {
2001                 node->num_tags = ((tre_iteration_t *)node->obj)->arg->num_tags
2002                   + tre_stack_pop_int(stack);
2003                 minimal_tag = -1;
2004               }
2005             else
2006               {
2007                 minimal = tre_stack_pop_int(stack);
2008                 enter_tag = tre_stack_pop_int(stack);
2009                 if (minimal)
2010                   minimal_tag = enter_tag;
2011               }
2012
2013             if (!first_pass)
2014               {
2015                 if (minimal)
2016                   direction = TRE_TAG_MINIMIZE;
2017                 else
2018                   direction = TRE_TAG_MAXIMIZE;
2019               }
2020             break;
2021           }
2022
2023         case ADDTAGS_AFTER_CAT_LEFT:
2024           {
2025             int new_tag = tre_stack_pop_int(stack);
2026             next_tag = tre_stack_pop_int(stack);
2027             if (new_tag >= 0)
2028               {
2029                 tag = new_tag;
2030               }
2031             break;
2032           }
2033
2034         case ADDTAGS_AFTER_CAT_RIGHT:
2035           node = tre_stack_pop_voidptr(stack);
2036           if (first_pass)
2037             node->num_tags = ((tre_catenation_t *)node->obj)->left->num_tags
2038               + ((tre_catenation_t *)node->obj)->right->num_tags;
2039           break;
2040
2041         case ADDTAGS_AFTER_UNION_LEFT:
2042           /* Lift the bottom of the `regset' array so that when processing
2043              the right operand the items currently in the array are
2044              invisible.  The original bottom was saved at ADDTAGS_UNION and
2045              will be restored at ADDTAGS_AFTER_UNION_RIGHT below. */
2046           while (*regset >= 0)
2047             regset++;
2048           break;
2049
2050         case ADDTAGS_AFTER_UNION_RIGHT:
2051           {
2052             int added_tags, tag_left, tag_right;
2053             tre_ast_node_t *left = tre_stack_pop_voidptr(stack);
2054             tre_ast_node_t *right = tre_stack_pop_voidptr(stack);
2055             node = tre_stack_pop_voidptr(stack);
2056             added_tags = tre_stack_pop_int(stack);
2057             if (first_pass)
2058               {
2059                 node->num_tags = ((tre_union_t *)node->obj)->left->num_tags
2060                   + ((tre_union_t *)node->obj)->right->num_tags + added_tags
2061                   + ((node->num_submatches > 0) ? 2 : 0);
2062               }
2063             regset = tre_stack_pop_voidptr(stack);
2064             tag_left = tre_stack_pop_int(stack);
2065             tag_right = tre_stack_pop_int(stack);
2066
2067             /* Add tags after both children, the left child gets a smaller
2068                tag than the right child.  This guarantees that we prefer
2069                the left child over the right child. */
2070             /* XXX - This is not always necessary (if the children have
2071                tags which must be seen for every match of that child). */
2072             /* XXX - Check if this is the only place where tre_add_tag_right
2073                is used.  If so, use tre_add_tag_left (putting the tag before
2074                the child as opposed after the child) and throw away
2075                tre_add_tag_right. */
2076             if (node->num_submatches > 0)
2077               {
2078                 if (!first_pass)
2079                   {
2080                     status = tre_add_tag_right(mem, left, tag_left);
2081                     tnfa->tag_directions[tag_left] = TRE_TAG_MAXIMIZE;
2082                     status = tre_add_tag_right(mem, right, tag_right);
2083                     tnfa->tag_directions[tag_right] = TRE_TAG_MAXIMIZE;
2084                   }
2085                 num_tags += 2;
2086               }
2087             direction = TRE_TAG_MAXIMIZE;
2088             break;
2089           }
2090
2091         default:
2092           assert(0);
2093           break;
2094
2095         } /* end switch(symbol) */
2096     } /* end while(tre_stack_num_objects(stack) > bottom) */
2097
2098   if (!first_pass)
2099     tre_purge_regset(regset, tnfa, tag);
2100
2101   if (!first_pass && minimal_tag >= 0)
2102     {
2103       int i;
2104       for (i = 0; tnfa->minimal_tags[i] >= 0; i++);
2105       tnfa->minimal_tags[i] = tag;
2106       tnfa->minimal_tags[i + 1] = minimal_tag;
2107       tnfa->minimal_tags[i + 2] = -1;
2108       minimal_tag = -1;
2109       num_minimals++;
2110     }
2111
2112   assert(tree->num_tags == num_tags);
2113   tnfa->end_tag = num_tags;
2114   tnfa->num_tags = num_tags;
2115   tnfa->num_minimals = num_minimals;
2116   xfree(orig_regset);
2117   xfree(parents);
2118   xfree(saved_states);
2119   return status;
2120 }
2121
2122
2123
2124 /*
2125   AST to TNFA compilation routines.
2126 */
2127
2128 typedef enum {
2129   COPY_RECURSE,
2130   COPY_SET_RESULT_PTR
2131 } tre_copyast_symbol_t;
2132
2133 /* Flags for tre_copy_ast(). */
2134 #define COPY_REMOVE_TAGS         1
2135 #define COPY_MAXIMIZE_FIRST_TAG  2
2136
2137 static reg_errcode_t
2138 tre_copy_ast(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *ast,
2139              int flags, int *pos_add, tre_tag_direction_t *tag_directions,
2140              tre_ast_node_t **copy, int *max_pos)
2141 {
2142   reg_errcode_t status = REG_OK;
2143   int bottom = tre_stack_num_objects(stack);
2144   int num_copied = 0;
2145   int first_tag = 1;
2146   tre_ast_node_t **result = copy;
2147   tre_copyast_symbol_t symbol;
2148
2149   STACK_PUSH(stack, voidptr, ast);
2150   STACK_PUSH(stack, int, COPY_RECURSE);
2151
2152   while (status == REG_OK && tre_stack_num_objects(stack) > bottom)
2153     {
2154       tre_ast_node_t *node;
2155       if (status != REG_OK)
2156         break;
2157
2158       symbol = (tre_copyast_symbol_t)tre_stack_pop_int(stack);
2159       switch (symbol)
2160         {
2161         case COPY_SET_RESULT_PTR:
2162           result = tre_stack_pop_voidptr(stack);
2163           break;
2164         case COPY_RECURSE:
2165           node = tre_stack_pop_voidptr(stack);
2166           switch (node->type)
2167             {
2168             case LITERAL:
2169               {
2170                 tre_literal_t *lit = node->obj;
2171                 int pos = lit->position;
2172                 int min = lit->code_min;
2173                 int max = lit->code_max;
2174                 if (!IS_SPECIAL(lit) || IS_BACKREF(lit))
2175                   {
2176                     /* XXX - e.g. [ab] has only one position but two
2177                        nodes, so we are creating holes in the state space
2178                        here.  Not fatal, just wastes memory. */
2179                     pos += *pos_add;
2180                     num_copied++;
2181                   }
2182                 else if (IS_TAG(lit) && (flags & COPY_REMOVE_TAGS))
2183                   {
2184                     /* Change this tag to empty. */
2185                     min = EMPTY;
2186                     max = pos = -1;
2187                   }
2188                 else if (IS_TAG(lit) && (flags & COPY_MAXIMIZE_FIRST_TAG)
2189                          && first_tag)
2190                   {
2191                     /* Maximize the first tag. */
2192                     tag_directions[max] = TRE_TAG_MAXIMIZE;
2193                     first_tag = 0;
2194                   }
2195                 *result = tre_ast_new_literal(mem, min, max, pos);
2196                 if (*result == NULL)
2197                   status = REG_ESPACE;
2198
2199                 if (pos > *max_pos)
2200                   *max_pos = pos;
2201                 break;
2202               }
2203             case UNION:
2204               {
2205                 tre_union_t *uni = node->obj;
2206                 tre_union_t *tmp;
2207                 *result = tre_ast_new_union(mem, uni->left, uni->right);
2208                 if (*result == NULL)
2209                   {
2210                     status = REG_ESPACE;
2211                     break;
2212                   }
2213                 tmp = (*result)->obj;
2214                 result = &tmp->left;
2215                 STACK_PUSHX(stack, voidptr, uni->right);
2216                 STACK_PUSHX(stack, int, COPY_RECURSE);
2217                 STACK_PUSHX(stack, voidptr, &tmp->right);
2218                 STACK_PUSHX(stack, int, COPY_SET_RESULT_PTR);
2219                 STACK_PUSHX(stack, voidptr, uni->left);
2220                 STACK_PUSHX(stack, int, COPY_RECURSE);
2221                 break;
2222               }
2223             case CATENATION:
2224               {
2225                 tre_catenation_t *cat = node->obj;
2226                 tre_catenation_t *tmp;
2227                 *result = tre_ast_new_catenation(mem, cat->left, cat->right);
2228                 if (*result == NULL)
2229                   {
2230                     status = REG_ESPACE;
2231                     break;
2232                   }
2233                 tmp = (*result)->obj;
2234                 tmp->left = NULL;
2235                 tmp->right = NULL;
2236                 result = &tmp->left;
2237
2238                 STACK_PUSHX(stack, voidptr, cat->right);
2239                 STACK_PUSHX(stack, int, COPY_RECURSE);
2240                 STACK_PUSHX(stack, voidptr, &tmp->right);
2241                 STACK_PUSHX(stack, int, COPY_SET_RESULT_PTR);
2242                 STACK_PUSHX(stack, voidptr, cat->left);
2243                 STACK_PUSHX(stack, int, COPY_RECURSE);
2244                 break;
2245               }
2246             case ITERATION:
2247               {
2248                 tre_iteration_t *iter = node->obj;
2249                 STACK_PUSHX(stack, voidptr, iter->arg);
2250                 STACK_PUSHX(stack, int, COPY_RECURSE);
2251                 *result = tre_ast_new_iter(mem, iter->arg, iter->min,
2252                                            iter->max, iter->minimal);
2253                 if (*result == NULL)
2254                   {
2255                     status = REG_ESPACE;
2256                     break;
2257                   }
2258                 iter = (*result)->obj;
2259                 result = &iter->arg;
2260                 break;
2261               }
2262             default:
2263               assert(0);
2264               break;
2265             }
2266           break;
2267         }
2268     }
2269   *pos_add += num_copied;
2270   return status;
2271 }
2272
2273 typedef enum {
2274   EXPAND_RECURSE,
2275   EXPAND_AFTER_ITER
2276 } tre_expand_ast_symbol_t;
2277
2278 /* Expands each iteration node that has a finite nonzero minimum or maximum
2279    iteration count to a catenated sequence of copies of the node. */
2280 static reg_errcode_t
2281 tre_expand_ast(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *ast,
2282                int *position, tre_tag_direction_t *tag_directions,
2283                int *max_depth)
2284 {
2285   reg_errcode_t status = REG_OK;
2286   int bottom = tre_stack_num_objects(stack);
2287   int pos_add = 0;
2288   int pos_add_total = 0;
2289   int max_pos = 0;
2290   int iter_depth = 0;
2291
2292   STACK_PUSHR(stack, voidptr, ast);
2293   STACK_PUSHR(stack, int, EXPAND_RECURSE);
2294   while (status == REG_OK && tre_stack_num_objects(stack) > bottom)
2295     {
2296       tre_ast_node_t *node;
2297       tre_expand_ast_symbol_t symbol;
2298
2299       if (status != REG_OK)
2300         break;
2301
2302       symbol = (tre_expand_ast_symbol_t)tre_stack_pop_int(stack);
2303       node = tre_stack_pop_voidptr(stack);
2304       switch (symbol)
2305         {
2306         case EXPAND_RECURSE:
2307           switch (node->type)
2308             {
2309             case LITERAL:
2310               {
2311                 tre_literal_t *lit= node->obj;
2312                 if (!IS_SPECIAL(lit) || IS_BACKREF(lit))
2313                   {
2314                     lit->position += pos_add;
2315                     if (lit->position > max_pos)
2316                       max_pos = lit->position;
2317                   }
2318                 break;
2319               }
2320             case UNION:
2321               {
2322                 tre_union_t *uni = node->obj;
2323                 STACK_PUSHX(stack, voidptr, uni->right);
2324                 STACK_PUSHX(stack, int, EXPAND_RECURSE);
2325                 STACK_PUSHX(stack, voidptr, uni->left);
2326                 STACK_PUSHX(stack, int, EXPAND_RECURSE);
2327                 break;
2328               }
2329             case CATENATION:
2330               {
2331                 tre_catenation_t *cat = node->obj;
2332                 STACK_PUSHX(stack, voidptr, cat->right);
2333                 STACK_PUSHX(stack, int, EXPAND_RECURSE);
2334                 STACK_PUSHX(stack, voidptr, cat->left);
2335                 STACK_PUSHX(stack, int, EXPAND_RECURSE);
2336                 break;
2337               }
2338             case ITERATION:
2339               {
2340                 tre_iteration_t *iter = node->obj;
2341                 STACK_PUSHX(stack, int, pos_add);
2342                 STACK_PUSHX(stack, voidptr, node);
2343                 STACK_PUSHX(stack, int, EXPAND_AFTER_ITER);
2344                 STACK_PUSHX(stack, voidptr, iter->arg);
2345                 STACK_PUSHX(stack, int, EXPAND_RECURSE);
2346                 /* If we are going to expand this node at EXPAND_AFTER_ITER
2347                    then don't increase the `pos' fields of the nodes now, it
2348                    will get done when expanding. */
2349                 if (iter->min > 1 || iter->max > 1)
2350                   pos_add = 0;
2351                 iter_depth++;
2352                 break;
2353               }
2354             default:
2355               assert(0);
2356               break;
2357             }
2358           break;
2359         case EXPAND_AFTER_ITER:
2360           {
2361             tre_iteration_t *iter = node->obj;
2362             int pos_add_last;
2363             pos_add = tre_stack_pop_int(stack);
2364             pos_add_last = pos_add;
2365             if (iter->min > 1 || iter->max > 1)
2366               {
2367                 tre_ast_node_t *seq1 = NULL, *seq2 = NULL;
2368                 int j;
2369                 int pos_add_save = pos_add;
2370
2371                 /* Create a catenated sequence of copies of the node. */
2372                 for (j = 0; j < iter->min; j++)
2373                   {
2374                     tre_ast_node_t *copy;
2375                     /* Remove tags from all but the last copy. */
2376                     int flags = ((j + 1 < iter->min)
2377                                  ? COPY_REMOVE_TAGS
2378                                  : COPY_MAXIMIZE_FIRST_TAG);
2379                     pos_add_save = pos_add;
2380                     status = tre_copy_ast(mem, stack, iter->arg, flags,
2381                                           &pos_add, tag_directions, &copy,
2382                                           &max_pos);
2383                     if (status != REG_OK)
2384                       return status;
2385                     if (seq1 != NULL)
2386                       seq1 = tre_ast_new_catenation(mem, seq1, copy);
2387                     else
2388                       seq1 = copy;
2389                     if (seq1 == NULL)
2390                       return REG_ESPACE;
2391                   }
2392
2393                 if (iter->max == -1)
2394                   {
2395                     /* No upper limit. */
2396                     pos_add_save = pos_add;
2397                     status = tre_copy_ast(mem, stack, iter->arg, 0,
2398                                           &pos_add, NULL, &seq2, &max_pos);
2399                     if (status != REG_OK)
2400                       return status;
2401                     seq2 = tre_ast_new_iter(mem, seq2, 0, -1, 0);
2402                     if (seq2 == NULL)
2403                       return REG_ESPACE;
2404                   }
2405                 else
2406                   {
2407                     for (j = iter->min; j < iter->max; j++)
2408                       {
2409                         tre_ast_node_t *tmp, *copy;
2410                         pos_add_save = pos_add;
2411                         status = tre_copy_ast(mem, stack, iter->arg, 0,
2412                                               &pos_add, NULL, &copy, &max_pos);
2413                         if (status != REG_OK)
2414                           return status;
2415                         if (seq2 != NULL)
2416                           seq2 = tre_ast_new_catenation(mem, copy, seq2);
2417                         else
2418                           seq2 = copy;
2419                         if (seq2 == NULL)
2420                           return REG_ESPACE;
2421                         tmp = tre_ast_new_literal(mem, EMPTY, -1, -1);
2422                         if (tmp == NULL)
2423                           return REG_ESPACE;
2424                         seq2 = tre_ast_new_union(mem, tmp, seq2);
2425                         if (seq2 == NULL)
2426                           return REG_ESPACE;
2427                       }
2428                   }
2429
2430                 pos_add = pos_add_save;
2431                 if (seq1 == NULL)
2432                   seq1 = seq2;
2433                 else if (seq2 != NULL)
2434                   seq1 = tre_ast_new_catenation(mem, seq1, seq2);
2435                 if (seq1 == NULL)
2436                   return REG_ESPACE;
2437                 node->obj = seq1->obj;
2438                 node->type = seq1->type;
2439               }
2440
2441             iter_depth--;
2442             pos_add_total += pos_add - pos_add_last;
2443             if (iter_depth == 0)
2444               pos_add = pos_add_total;
2445
2446             break;
2447           }
2448         default:
2449           assert(0);
2450           break;
2451         }
2452     }
2453
2454   *position += pos_add_total;
2455
2456   /* `max_pos' should never be larger than `*position' if the above
2457      code works, but just an extra safeguard let's make sure
2458      `*position' is set large enough so enough memory will be
2459      allocated for the transition table. */
2460   if (max_pos > *position)
2461     *position = max_pos;
2462
2463   return status;
2464 }
2465
2466 static tre_pos_and_tags_t *
2467 tre_set_empty(tre_mem_t mem)
2468 {
2469   tre_pos_and_tags_t *new_set;
2470
2471   new_set = tre_mem_calloc(mem, sizeof(*new_set));
2472   if (new_set == NULL)
2473     return NULL;
2474
2475   new_set[0].position = -1;
2476   new_set[0].code_min = -1;
2477   new_set[0].code_max = -1;
2478
2479   return new_set;
2480 }
2481
2482 static tre_pos_and_tags_t *
2483 tre_set_one(tre_mem_t mem, int position, int code_min, int code_max,
2484             tre_ctype_t class, tre_ctype_t *neg_classes, int backref)
2485 {
2486   tre_pos_and_tags_t *new_set;
2487
2488   new_set = tre_mem_calloc(mem, sizeof(*new_set) * 2);
2489   if (new_set == NULL)
2490     return NULL;
2491
2492   new_set[0].position = position;
2493   new_set[0].code_min = code_min;
2494   new_set[0].code_max = code_max;
2495   new_set[0].class = class;
2496   new_set[0].neg_classes = neg_classes;
2497   new_set[0].backref = backref;
2498   new_set[1].position = -1;
2499   new_set[1].code_min = -1;
2500   new_set[1].code_max = -1;
2501
2502   return new_set;
2503 }
2504
2505 static tre_pos_and_tags_t *
2506 tre_set_union(tre_mem_t mem, tre_pos_and_tags_t *set1, tre_pos_and_tags_t *set2,
2507               int *tags, int assertions)
2508 {
2509   int s1, s2, i, j;
2510   tre_pos_and_tags_t *new_set;
2511   int *new_tags;
2512   int num_tags;
2513
2514   for (num_tags = 0; tags != NULL && tags[num_tags] >= 0; num_tags++);
2515   for (s1 = 0; set1[s1].position >= 0; s1++);
2516   for (s2 = 0; set2[s2].position >= 0; s2++);
2517   new_set = tre_mem_calloc(mem, sizeof(*new_set) * (s1 + s2 + 1));
2518   if (!new_set )
2519     return NULL;
2520
2521   for (s1 = 0; set1[s1].position >= 0; s1++)
2522     {
2523       new_set[s1].position = set1[s1].position;
2524       new_set[s1].code_min = set1[s1].code_min;
2525       new_set[s1].code_max = set1[s1].code_max;
2526       new_set[s1].assertions = set1[s1].assertions | assertions;
2527       new_set[s1].class = set1[s1].class;
2528       new_set[s1].neg_classes = set1[s1].neg_classes;
2529       new_set[s1].backref = set1[s1].backref;
2530       if (set1[s1].tags == NULL && tags == NULL)
2531         new_set[s1].tags = NULL;
2532       else
2533         {
2534           for (i = 0; set1[s1].tags != NULL && set1[s1].tags[i] >= 0; i++);
2535           new_tags = tre_mem_alloc(mem, (sizeof(*new_tags)
2536                                          * (i + num_tags + 1)));
2537           if (new_tags == NULL)
2538             return NULL;
2539           for (j = 0; j < i; j++)
2540             new_tags[j] = set1[s1].tags[j];
2541           for (i = 0; i < num_tags; i++)
2542             new_tags[j + i] = tags[i];
2543           new_tags[j + i] = -1;
2544           new_set[s1].tags = new_tags;
2545         }
2546     }
2547
2548   for (s2 = 0; set2[s2].position >= 0; s2++)
2549     {
2550       new_set[s1 + s2].position = set2[s2].position;
2551       new_set[s1 + s2].code_min = set2[s2].code_min;
2552       new_set[s1 + s2].code_max = set2[s2].code_max;
2553       /* XXX - why not | assertions here as well? */
2554       new_set[s1 + s2].assertions = set2[s2].assertions;
2555       new_set[s1 + s2].class = set2[s2].class;
2556       new_set[s1 + s2].neg_classes = set2[s2].neg_classes;
2557       new_set[s1 + s2].backref = set2[s2].backref;
2558       if (set2[s2].tags == NULL)
2559         new_set[s1 + s2].tags = NULL;
2560       else
2561         {
2562           for (i = 0; set2[s2].tags[i] >= 0; i++);
2563           new_tags = tre_mem_alloc(mem, sizeof(*new_tags) * (i + 1));
2564           if (new_tags == NULL)
2565             return NULL;
2566           for (j = 0; j < i; j++)
2567             new_tags[j] = set2[s2].tags[j];
2568           new_tags[j] = -1;
2569           new_set[s1 + s2].tags = new_tags;
2570         }
2571     }
2572   new_set[s1 + s2].position = -1;
2573   return new_set;
2574 }
2575
2576 /* Finds the empty path through `node' which is the one that should be
2577    taken according to POSIX.2 rules, and adds the tags on that path to
2578    `tags'.   `tags' may be NULL.  If `num_tags_seen' is not NULL, it is
2579    set to the number of tags seen on the path. */
2580 static reg_errcode_t
2581 tre_match_empty(tre_stack_t *stack, tre_ast_node_t *node, int *tags,
2582                 int *assertions, int *params, int *num_tags_seen,
2583                 int *params_seen)
2584 {
2585   tre_literal_t *lit;
2586   tre_union_t *uni;
2587   tre_catenation_t *cat;
2588   tre_iteration_t *iter;
2589   int i;
2590   int bottom = tre_stack_num_objects(stack);
2591   reg_errcode_t status = REG_OK;
2592   if (num_tags_seen)
2593     *num_tags_seen = 0;
2594
2595   status = tre_stack_push_voidptr(stack, node);
2596
2597   /* Walk through the tree recursively. */
2598   while (status == REG_OK && tre_stack_num_objects(stack) > bottom)
2599     {
2600       node = tre_stack_pop_voidptr(stack);
2601
2602       switch (node->type)
2603         {
2604         case LITERAL:
2605           lit = (tre_literal_t *)node->obj;
2606           switch (lit->code_min)
2607             {
2608             case TAG:
2609               if (lit->code_max >= 0)
2610                 {
2611                   if (tags != NULL)
2612                     {
2613                       /* Add the tag to `tags'. */
2614                       for (i = 0; tags[i] >= 0; i++)
2615                         if (tags[i] == lit->code_max)
2616                           break;
2617                       if (tags[i] < 0)
2618                         {
2619                           tags[i] = lit->code_max;
2620                           tags[i + 1] = -1;
2621                         }
2622                     }
2623                   if (num_tags_seen)
2624                     (*num_tags_seen)++;
2625                 }
2626               break;
2627             case ASSERTION:
2628               assert(lit->code_max >= 1
2629                      || lit->code_max <= ASSERT_LAST);
2630               if (assertions != NULL)
2631                 *assertions |= lit->code_max;
2632               break;
2633             case EMPTY:
2634               break;
2635             default:
2636               assert(0);
2637               break;
2638             }
2639           break;
2640
2641         case UNION:
2642           /* Subexpressions starting earlier take priority over ones
2643              starting later, so we prefer the left subexpression over the
2644              right subexpression. */
2645           uni = (tre_union_t *)node->obj;
2646           if (uni->left->nullable)
2647             STACK_PUSHX(stack, voidptr, uni->left)
2648           else if (uni->right->nullable)
2649             STACK_PUSHX(stack, voidptr, uni->right)
2650           else
2651             assert(0);
2652           break;
2653
2654         case CATENATION:
2655           /* The path must go through both children. */
2656           cat = (tre_catenation_t *)node->obj;
2657           assert(cat->left->nullable);
2658           assert(cat->right->nullable);
2659           STACK_PUSHX(stack, voidptr, cat->left);
2660           STACK_PUSHX(stack, voidptr, cat->right);
2661           break;
2662
2663         case ITERATION:
2664           /* A match with an empty string is preferred over no match at
2665              all, so we go through the argument if possible. */
2666           iter = (tre_iteration_t *)node->obj;
2667           if (iter->arg->nullable)
2668             STACK_PUSHX(stack, voidptr, iter->arg);
2669           break;
2670
2671         default:
2672           assert(0);
2673           break;
2674         }
2675     }
2676
2677   return status;
2678 }
2679
2680
2681 typedef enum {
2682   NFL_RECURSE,
2683   NFL_POST_UNION,
2684   NFL_POST_CATENATION,
2685   NFL_POST_ITERATION
2686 } tre_nfl_stack_symbol_t;
2687
2688
2689 /* Computes and fills in the fields `nullable', `firstpos', and `lastpos' for
2690    the nodes of the AST `tree'. */
2691 static reg_errcode_t
2692 tre_compute_nfl(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree)
2693 {
2694   int bottom = tre_stack_num_objects(stack);
2695
2696   STACK_PUSHR(stack, voidptr, tree);
2697   STACK_PUSHR(stack, int, NFL_RECURSE);
2698
2699   while (tre_stack_num_objects(stack) > bottom)
2700     {
2701       tre_nfl_stack_symbol_t symbol;
2702       tre_ast_node_t *node;
2703
2704       symbol = (tre_nfl_stack_symbol_t)tre_stack_pop_int(stack);
2705       node = tre_stack_pop_voidptr(stack);
2706       switch (symbol)
2707         {
2708         case NFL_RECURSE:
2709           switch (node->type)
2710             {
2711             case LITERAL:
2712               {
2713                 tre_literal_t *lit = (tre_literal_t *)node->obj;
2714                 if (IS_BACKREF(lit))
2715                   {
2716                     /* Back references: nullable = false, firstpos = {i},
2717                        lastpos = {i}. */
2718                     node->nullable = 0;
2719                     node->firstpos = tre_set_one(mem, lit->position, 0,
2720                                              TRE_CHAR_MAX, 0, NULL, -1);
2721                     if (!node->firstpos)
2722                       return REG_ESPACE;
2723                     node->lastpos = tre_set_one(mem, lit->position, 0,
2724                                                 TRE_CHAR_MAX, 0, NULL,
2725                                                 (int)lit->code_max);
2726                     if (!node->lastpos)
2727                       return REG_ESPACE;
2728                   }
2729                 else if (lit->code_min < 0)
2730                   {
2731                     /* Tags, empty strings, params, and zero width assertions:
2732                        nullable = true, firstpos = {}, and lastpos = {}. */
2733                     node->nullable = 1;
2734                     node->firstpos = tre_set_empty(mem);
2735                     if (!node->firstpos)
2736                       return REG_ESPACE;
2737                     node->lastpos = tre_set_empty(mem);
2738                     if (!node->lastpos)
2739                       return REG_ESPACE;
2740                   }
2741                 else
2742                   {
2743                     /* Literal at position i: nullable = false, firstpos = {i},
2744                        lastpos = {i}. */
2745                     node->nullable = 0;
2746                     node->firstpos =
2747                       tre_set_one(mem, lit->position, (int)lit->code_min,
2748                                   (int)lit->code_max, 0, NULL, -1);
2749                     if (!node->firstpos)
2750                       return REG_ESPACE;
2751                     node->lastpos = tre_set_one(mem, lit->position,
2752                                                 (int)lit->code_min,
2753                                                 (int)lit->code_max,
2754                                                 lit->u.class, lit->neg_classes,
2755                                                 -1);
2756                     if (!node->lastpos)
2757                       return REG_ESPACE;
2758                   }
2759                 break;
2760               }
2761
2762             case UNION:
2763               /* Compute the attributes for the two subtrees, and after that
2764                  for this node. */
2765               STACK_PUSHR(stack, voidptr, node);
2766               STACK_PUSHR(stack, int, NFL_POST_UNION);
2767               STACK_PUSHR(stack, voidptr, ((tre_union_t *)node->obj)->right);
2768               STACK_PUSHR(stack, int, NFL_RECURSE);
2769               STACK_PUSHR(stack, voidptr, ((tre_union_t *)node->obj)->left);
2770               STACK_PUSHR(stack, int, NFL_RECURSE);
2771               break;
2772
2773             case CATENATION:
2774               /* Compute the attributes for the two subtrees, and after that
2775                  for this node. */
2776               STACK_PUSHR(stack, voidptr, node);
2777               STACK_PUSHR(stack, int, NFL_POST_CATENATION);
2778               STACK_PUSHR(stack, voidptr, ((tre_catenation_t *)node->obj)->right);
2779               STACK_PUSHR(stack, int, NFL_RECURSE);
2780               STACK_PUSHR(stack, voidptr, ((tre_catenation_t *)node->obj)->left);
2781               STACK_PUSHR(stack, int, NFL_RECURSE);
2782               break;
2783
2784             case ITERATION:
2785               /* Compute the attributes for the subtree, and after that for
2786                  this node. */
2787               STACK_PUSHR(stack, voidptr, node);
2788               STACK_PUSHR(stack, int, NFL_POST_ITERATION);
2789               STACK_PUSHR(stack, voidptr, ((tre_iteration_t *)node->obj)->arg);
2790               STACK_PUSHR(stack, int, NFL_RECURSE);
2791               break;
2792             }
2793           break; /* end case: NFL_RECURSE */
2794
2795         case NFL_POST_UNION:
2796           {
2797             tre_union_t *uni = (tre_union_t *)node->obj;
2798             node->nullable = uni->left->nullable || uni->right->nullable;
2799             node->firstpos = tre_set_union(mem, uni->left->firstpos,
2800                                            uni->right->firstpos, NULL, 0);
2801             if (!node->firstpos)
2802               return REG_ESPACE;
2803             node->lastpos = tre_set_union(mem, uni->left->lastpos,
2804                                           uni->right->lastpos, NULL, 0);
2805             if (!node->lastpos)
2806               return REG_ESPACE;
2807             break;
2808           }
2809
2810         case NFL_POST_ITERATION:
2811           {
2812             tre_iteration_t *iter = (tre_iteration_t *)node->obj;
2813
2814             if (iter->min == 0 || iter->arg->nullable)
2815               node->nullable = 1;
2816             else
2817               node->nullable = 0;
2818             node->firstpos = iter->arg->firstpos;
2819             node->lastpos = iter->arg->lastpos;
2820             break;
2821           }
2822
2823         case NFL_POST_CATENATION:
2824           {
2825             int num_tags, *tags, assertions, params_seen;
2826             int *params;
2827             reg_errcode_t status;
2828             tre_catenation_t *cat = node->obj;
2829             node->nullable = cat->left->nullable && cat->right->nullable;
2830
2831             /* Compute firstpos. */
2832             if (cat->left->nullable)
2833               {
2834                 /* The left side matches the empty string.  Make a first pass
2835                    with tre_match_empty() to get the number of tags and
2836                    parameters. */
2837                 status = tre_match_empty(stack, cat->left,
2838                                          NULL, NULL, NULL, &num_tags,
2839                                          &params_seen);
2840                 if (status != REG_OK)
2841                   return status;
2842                 /* Allocate arrays for the tags and parameters. */
2843                 tags = xmalloc(sizeof(*tags) * (num_tags + 1));
2844                 if (!tags)
2845                   return REG_ESPACE;
2846                 tags[0] = -1;
2847                 assertions = 0;
2848                 /* Second pass with tre_mach_empty() to get the list of
2849                    tags and parameters. */
2850                 status = tre_match_empty(stack, cat->left, tags,
2851                                          &assertions, params, NULL, NULL);
2852                 if (status != REG_OK)
2853                   {
2854                     xfree(tags);
2855                     return status;
2856                   }
2857                 node->firstpos =
2858                   tre_set_union(mem, cat->right->firstpos, cat->left->firstpos,
2859                                 tags, assertions);
2860                 xfree(tags);
2861                 if (!node->firstpos)
2862                   return REG_ESPACE;
2863               }
2864             else
2865               {
2866                 node->firstpos = cat->left->firstpos;
2867               }
2868
2869             /* Compute lastpos. */
2870             if (cat->right->nullable)
2871               {
2872                 /* The right side matches the empty string.  Make a first pass
2873                    with tre_match_empty() to get the number of tags and
2874                    parameters. */
2875                 status = tre_match_empty(stack, cat->right,
2876                                          NULL, NULL, NULL, &num_tags,
2877                                          &params_seen);
2878                 if (status != REG_OK)
2879                   return status;
2880                 /* Allocate arrays for the tags and parameters. */
2881                 tags = xmalloc(sizeof(int) * (num_tags + 1));
2882                 if (!tags)
2883                   return REG_ESPACE;
2884                 tags[0] = -1;
2885                 assertions = 0;
2886                 /* Second pass with tre_mach_empty() to get the list of
2887                    tags and parameters. */
2888                 status = tre_match_empty(stack, cat->right, tags,
2889                                          &assertions, params, NULL, NULL);
2890                 if (status != REG_OK)
2891                   {
2892                     xfree(tags);
2893                     return status;
2894                   }
2895                 node->lastpos =
2896                   tre_set_union(mem, cat->left->lastpos, cat->right->lastpos,
2897                                 tags, assertions);
2898                 xfree(tags);
2899                 if (!node->lastpos)
2900                   return REG_ESPACE;
2901               }
2902             else
2903               {
2904                 node->lastpos = cat->right->lastpos;
2905               }
2906             break;
2907           }
2908
2909         default:
2910           assert(0);
2911           break;
2912         }
2913     }
2914
2915   return REG_OK;
2916 }
2917
2918
2919 /* Adds a transition from each position in `p1' to each position in `p2'. */
2920 static reg_errcode_t
2921 tre_make_trans(tre_pos_and_tags_t *p1, tre_pos_and_tags_t *p2,
2922                tre_tnfa_transition_t *transitions,
2923                int *counts, int *offs)
2924 {
2925   tre_pos_and_tags_t *orig_p2 = p2;
2926   tre_tnfa_transition_t *trans;
2927   int i, j, k, l, dup, prev_p2_pos;
2928
2929   if (transitions != NULL)
2930     while (p1->position >= 0)
2931       {
2932         p2 = orig_p2;
2933         prev_p2_pos = -1;
2934         while (p2->position >= 0)
2935           {
2936             /* Optimization: if this position was already handled, skip it. */
2937             if (p2->position == prev_p2_pos)
2938               {
2939                 p2++;
2940                 continue;
2941               }
2942             prev_p2_pos = p2->position;
2943             /* Set `trans' to point to the next unused transition from
2944                position `p1->position'. */
2945             trans = transitions + offs[p1->position];
2946             while (trans->state != NULL)
2947               {
2948 #if 0
2949                 /* If we find a previous transition from `p1->position' to
2950                    `p2->position', it is overwritten.  This can happen only
2951                    if there are nested loops in the regexp, like in "((a)*)*".
2952                    In POSIX.2 repetition using the outer loop is always
2953                    preferred over using the inner loop.  Therefore the
2954                    transition for the inner loop is useless and can be thrown
2955                    away. */
2956                 /* XXX - The same position is used for all nodes in a bracket
2957                    expression, so this optimization cannot be used (it will
2958                    break bracket expressions) unless I figure out a way to
2959                    detect it here. */
2960                 if (trans->state_id == p2->position)
2961                   {
2962                     break;
2963                   }
2964 #endif
2965                 trans++;
2966               }
2967
2968             if (trans->state == NULL)
2969               (trans + 1)->state = NULL;
2970             /* Use the character ranges, assertions, etc. from `p1' for
2971                the transition from `p1' to `p2'. */
2972             trans->code_min = p1->code_min;
2973             trans->code_max = p1->code_max;
2974             trans->state = transitions + offs[p2->position];
2975             trans->state_id = p2->position;
2976             trans->assertions = p1->assertions | p2->assertions
2977               | (p1->class ? ASSERT_CHAR_CLASS : 0)
2978               | (p1->neg_classes != NULL ? ASSERT_CHAR_CLASS_NEG : 0);
2979             if (p1->backref >= 0)
2980               {
2981                 assert((trans->assertions & ASSERT_CHAR_CLASS) == 0);
2982                 assert(p2->backref < 0);
2983                 trans->u.backref = p1->backref;
2984                 trans->assertions |= ASSERT_BACKREF;
2985               }
2986             else
2987               trans->u.class = p1->class;
2988             if (p1->neg_classes != NULL)
2989               {
2990                 for (i = 0; p1->neg_classes[i] != (tre_ctype_t)0; i++);
2991                 trans->neg_classes =
2992                   xmalloc(sizeof(*trans->neg_classes) * (i + 1));
2993                 if (trans->neg_classes == NULL)
2994                   return REG_ESPACE;
2995                 for (i = 0; p1->neg_classes[i] != (tre_ctype_t)0; i++)
2996                   trans->neg_classes[i] = p1->neg_classes[i];
2997                 trans->neg_classes[i] = (tre_ctype_t)0;
2998               }
2999             else
3000               trans->neg_classes = NULL;
3001
3002             /* Find out how many tags this transition has. */
3003             i = 0;
3004             if (p1->tags != NULL)
3005               while(p1->tags[i] >= 0)
3006                 i++;
3007             j = 0;
3008             if (p2->tags != NULL)
3009               while(p2->tags[j] >= 0)
3010                 j++;
3011
3012             /* If we are overwriting a transition, free the old tag array. */
3013             if (trans->tags != NULL)
3014               xfree(trans->tags);
3015             trans->tags = NULL;
3016
3017             /* If there were any tags, allocate an array and fill it. */
3018             if (i + j > 0)
3019               {
3020                 trans->tags = xmalloc(sizeof(*trans->tags) * (i + j + 1));
3021                 if (!trans->tags)
3022                   return REG_ESPACE;
3023                 i = 0;
3024                 if (p1->tags != NULL)
3025                   while(p1->tags[i] >= 0)
3026                     {
3027                       trans->tags[i] = p1->tags[i];
3028                       i++;
3029                     }
3030                 l = i;
3031                 j = 0;
3032                 if (p2->tags != NULL)
3033                   while (p2->tags[j] >= 0)
3034                     {
3035                       /* Don't add duplicates. */
3036                       dup = 0;
3037                       for (k = 0; k < i; k++)
3038                         if (trans->tags[k] == p2->tags[j])
3039                           {
3040                             dup = 1;
3041                             break;
3042                           }
3043                       if (!dup)
3044                         trans->tags[l++] = p2->tags[j];
3045                       j++;
3046                     }
3047                 trans->tags[l] = -1;
3048               }
3049
3050             p2++;
3051           }
3052         p1++;
3053       }
3054   else
3055     /* Compute a maximum limit for the number of transitions leaving
3056        from each state. */
3057     while (p1->position >= 0)
3058       {
3059         p2 = orig_p2;
3060         while (p2->position >= 0)
3061           {
3062             counts[p1->position]++;
3063             p2++;
3064           }
3065         p1++;
3066       }
3067   return REG_OK;
3068 }
3069
3070 /* Converts the syntax tree to a TNFA.  All the transitions in the TNFA are
3071    labelled with one character range (there are no transitions on empty
3072    strings).  The TNFA takes O(n^2) space in the worst case, `n' is size of
3073    the regexp. */
3074 static reg_errcode_t
3075 tre_ast_to_tnfa(tre_ast_node_t *node, tre_tnfa_transition_t *transitions,
3076                 int *counts, int *offs)
3077 {
3078   tre_union_t *uni;
3079   tre_catenation_t *cat;
3080   tre_iteration_t *iter;
3081   reg_errcode_t errcode = REG_OK;
3082
3083   /* XXX - recurse using a stack!. */
3084   switch (node->type)
3085     {
3086     case LITERAL:
3087       break;
3088     case UNION:
3089       uni = (tre_union_t *)node->obj;
3090       errcode = tre_ast_to_tnfa(uni->left, transitions, counts, offs);
3091       if (errcode != REG_OK)
3092         return errcode;
3093       errcode = tre_ast_to_tnfa(uni->right, transitions, counts, offs);
3094       break;
3095
3096     case CATENATION:
3097       cat = (tre_catenation_t *)node->obj;
3098       /* Add a transition from each position in cat->left->lastpos
3099          to each position in cat->right->firstpos. */
3100       errcode = tre_make_trans(cat->left->lastpos, cat->right->firstpos,
3101                                transitions, counts, offs);
3102       if (errcode != REG_OK)
3103         return errcode;
3104       errcode = tre_ast_to_tnfa(cat->left, transitions, counts, offs);
3105       if (errcode != REG_OK)
3106         return errcode;
3107       errcode = tre_ast_to_tnfa(cat->right, transitions, counts, offs);
3108       break;
3109
3110     case ITERATION:
3111       iter = (tre_iteration_t *)node->obj;
3112       assert(iter->max == -1 || iter->max == 1);
3113
3114       if (iter->max == -1)
3115         {
3116           assert(iter->min == 0 || iter->min == 1);
3117           /* Add a transition from each last position in the iterated
3118              expression to each first position. */
3119           errcode = tre_make_trans(iter->arg->lastpos, iter->arg->firstpos,
3120                                    transitions, counts, offs);
3121           if (errcode != REG_OK)
3122             return errcode;
3123         }
3124       errcode = tre_ast_to_tnfa(iter->arg, transitions, counts, offs);
3125       break;
3126     }
3127   return errcode;
3128 }
3129
3130
3131 #define ERROR_EXIT(err)           \
3132   do                              \
3133     {                             \
3134       errcode = err;              \
3135       if (/*CONSTCOND*/1)         \
3136         goto error_exit;          \
3137     }                             \
3138  while (/*CONSTCOND*/0)
3139
3140
3141 int
3142 regcomp(regex_t *preg, const char *regex, int cflags)
3143 {
3144   tre_stack_t *stack;
3145   tre_ast_node_t *tree, *tmp_ast_l, *tmp_ast_r;
3146   tre_pos_and_tags_t *p;
3147   int *counts = NULL, *offs = NULL;
3148   int i, add = 0;
3149   tre_tnfa_transition_t *transitions, *initial;
3150   tre_tnfa_t *tnfa = NULL;
3151   tre_submatch_data_t *submatch_data;
3152   tre_tag_direction_t *tag_directions = NULL;
3153   reg_errcode_t errcode;
3154   tre_mem_t mem;
3155
3156   /* Parse context. */
3157   tre_parse_ctx_t parse_ctx;
3158
3159   /* Allocate a stack used throughout the compilation process for various
3160      purposes. */
3161   stack = tre_stack_new(512, 10240, 128);
3162   if (!stack)
3163     return REG_ESPACE;
3164   /* Allocate a fast memory allocator. */
3165   mem = tre_mem_new();
3166   if (!mem)
3167     {
3168       tre_stack_destroy(stack);
3169       return REG_ESPACE;
3170     }
3171
3172   /* Parse the regexp. */
3173   memset(&parse_ctx, 0, sizeof(parse_ctx));
3174   parse_ctx.mem = mem;
3175   parse_ctx.stack = stack;
3176   parse_ctx.re = regex;
3177   parse_ctx.cflags = cflags;
3178   parse_ctx.max_backref = -1;
3179   errcode = tre_parse(&parse_ctx);
3180   if (errcode != REG_OK)
3181     ERROR_EXIT(errcode);
3182   preg->re_nsub = parse_ctx.submatch_id - 1;
3183   tree = parse_ctx.result;
3184
3185   /* Back references and approximate matching cannot currently be used
3186      in the same regexp. */
3187   if (parse_ctx.max_backref >= 0 && parse_ctx.have_approx)
3188     ERROR_EXIT(REG_BADPAT);
3189
3190 #ifdef TRE_DEBUG
3191   tre_ast_print(tree);
3192 #endif /* TRE_DEBUG */
3193
3194   /* Referring to nonexistent subexpressions is illegal. */
3195   if (parse_ctx.max_backref > (int)preg->re_nsub)
3196     ERROR_EXIT(REG_ESUBREG);
3197
3198   /* Allocate the TNFA struct. */
3199   tnfa = xcalloc(1, sizeof(tre_tnfa_t));
3200   if (tnfa == NULL)
3201     ERROR_EXIT(REG_ESPACE);
3202   tnfa->have_backrefs = parse_ctx.max_backref >= 0;
3203   tnfa->have_approx = parse_ctx.have_approx;
3204   tnfa->num_submatches = parse_ctx.submatch_id;
3205
3206   /* Set up tags for submatch addressing.  If REG_NOSUB is set and the
3207      regexp does not have back references, this can be skipped. */
3208   if (tnfa->have_backrefs || !(cflags & REG_NOSUB))
3209     {
3210
3211       /* Figure out how many tags we will need. */
3212       errcode = tre_add_tags(NULL, stack, tree, tnfa);
3213       if (errcode != REG_OK)
3214         ERROR_EXIT(errcode);
3215
3216       if (tnfa->num_tags > 0)
3217         {
3218           tag_directions = xmalloc(sizeof(*tag_directions)
3219                                    * (tnfa->num_tags + 1));
3220           if (tag_directions == NULL)
3221             ERROR_EXIT(REG_ESPACE);
3222           tnfa->tag_directions = tag_directions;
3223           memset(tag_directions, -1,
3224                  sizeof(*tag_directions) * (tnfa->num_tags + 1));
3225         }
3226       tnfa->minimal_tags = xcalloc((unsigned)tnfa->num_tags * 2 + 1,
3227                                    sizeof(tnfa->minimal_tags));
3228       if (tnfa->minimal_tags == NULL)
3229         ERROR_EXIT(REG_ESPACE);
3230
3231       submatch_data = xcalloc((unsigned)parse_ctx.submatch_id,
3232                               sizeof(*submatch_data));
3233       if (submatch_data == NULL)
3234         ERROR_EXIT(REG_ESPACE);
3235       tnfa->submatch_data = submatch_data;
3236
3237       errcode = tre_add_tags(mem, stack, tree, tnfa);
3238       if (errcode != REG_OK)
3239         ERROR_EXIT(errcode);
3240
3241     }
3242
3243   /* Expand iteration nodes. */
3244   errcode = tre_expand_ast(mem, stack, tree, &parse_ctx.position,
3245                            tag_directions, &tnfa->params_depth);
3246   if (errcode != REG_OK)
3247     ERROR_EXIT(errcode);
3248
3249   /* Add a dummy node for the final state.
3250      XXX - For certain patterns this dummy node can be optimized away,
3251            for example "a*" or "ab*".   Figure out a simple way to detect
3252            this possibility. */
3253   tmp_ast_l = tree;
3254   tmp_ast_r = tre_ast_new_literal(mem, 0, 0, parse_ctx.position++);
3255   if (tmp_ast_r == NULL)
3256     ERROR_EXIT(REG_ESPACE);
3257
3258   tree = tre_ast_new_catenation(mem, tmp_ast_l, tmp_ast_r);
3259   if (tree == NULL)
3260     ERROR_EXIT(REG_ESPACE);
3261
3262   errcode = tre_compute_nfl(mem, stack, tree);
3263   if (errcode != REG_OK)
3264     ERROR_EXIT(errcode);
3265
3266   counts = xmalloc(sizeof(int) * parse_ctx.position);
3267   if (counts == NULL)
3268     ERROR_EXIT(REG_ESPACE);
3269
3270   offs = xmalloc(sizeof(int) * parse_ctx.position);
3271   if (offs == NULL)
3272     ERROR_EXIT(REG_ESPACE);
3273
3274   for (i = 0; i < parse_ctx.position; i++)
3275     counts[i] = 0;
3276   tre_ast_to_tnfa(tree, NULL, counts, NULL);
3277
3278   add = 0;
3279   for (i = 0; i < parse_ctx.position; i++)
3280     {
3281       offs[i] = add;
3282       add += counts[i] + 1;
3283       counts[i] = 0;
3284     }
3285   transitions = xcalloc((unsigned)add + 1, sizeof(*transitions));
3286   if (transitions == NULL)
3287     ERROR_EXIT(REG_ESPACE);
3288   tnfa->transitions = transitions;
3289   tnfa->num_transitions = add;
3290
3291   errcode = tre_ast_to_tnfa(tree, transitions, counts, offs);
3292   if (errcode != REG_OK)
3293     ERROR_EXIT(errcode);
3294
3295   tnfa->firstpos_chars = NULL;
3296
3297   p = tree->firstpos;
3298   i = 0;
3299   while (p->position >= 0)
3300     {
3301       i++;
3302       p++;
3303     }
3304
3305   initial = xcalloc((unsigned)i + 1, sizeof(tre_tnfa_transition_t));
3306   if (initial == NULL)
3307     ERROR_EXIT(REG_ESPACE);
3308   tnfa->initial = initial;
3309
3310   i = 0;
3311   for (p = tree->firstpos; p->position >= 0; p++)
3312     {
3313       initial[i].state = transitions + offs[p->position];
3314       initial[i].state_id = p->position;
3315       initial[i].tags = NULL;
3316       /* Copy the arrays p->tags, and p->params, they are allocated
3317          from a tre_mem object. */
3318       if (p->tags)
3319         {
3320           int j;
3321           for (j = 0; p->tags[j] >= 0; j++);
3322           initial[i].tags = xmalloc(sizeof(*p->tags) * (j + 1));
3323           if (!initial[i].tags)
3324             ERROR_EXIT(REG_ESPACE);
3325           memcpy(initial[i].tags, p->tags, sizeof(*p->tags) * (j + 1));
3326         }
3327       initial[i].assertions = p->assertions;
3328       i++;
3329     }
3330   initial[i].state = NULL;
3331
3332   tnfa->num_transitions = add;
3333   tnfa->final = transitions + offs[tree->lastpos[0].position];
3334   tnfa->num_states = parse_ctx.position;
3335   tnfa->cflags = cflags;
3336
3337   tre_mem_destroy(mem);
3338   tre_stack_destroy(stack);
3339   xfree(counts);
3340   xfree(offs);
3341
3342   preg->TRE_REGEX_T_FIELD = (void *)tnfa;
3343   return REG_OK;
3344
3345  error_exit:
3346   /* Free everything that was allocated and return the error code. */
3347   tre_mem_destroy(mem);
3348   if (stack != NULL)
3349     tre_stack_destroy(stack);
3350   if (counts != NULL)
3351     xfree(counts);
3352   if (offs != NULL)
3353     xfree(offs);
3354   preg->TRE_REGEX_T_FIELD = (void *)tnfa;
3355   regfree(preg);
3356   return errcode;
3357 }
3358
3359
3360
3361
3362 void
3363 regfree(regex_t *preg)
3364 {
3365   tre_tnfa_t *tnfa;
3366   unsigned int i;
3367   tre_tnfa_transition_t *trans;
3368
3369   tnfa = (void *)preg->TRE_REGEX_T_FIELD;
3370   if (!tnfa)
3371     return;
3372
3373   for (i = 0; i < tnfa->num_transitions; i++)
3374     if (tnfa->transitions[i].state)
3375       {
3376         if (tnfa->transitions[i].tags)
3377           xfree(tnfa->transitions[i].tags);
3378         if (tnfa->transitions[i].neg_classes)
3379           xfree(tnfa->transitions[i].neg_classes);
3380       }
3381   if (tnfa->transitions)
3382     xfree(tnfa->transitions);
3383
3384   if (tnfa->initial)
3385     {
3386       for (trans = tnfa->initial; trans->state; trans++)
3387         {
3388           if (trans->tags)
3389             xfree(trans->tags);
3390         }
3391       xfree(tnfa->initial);
3392     }
3393
3394   if (tnfa->submatch_data)
3395     {
3396       for (i = 0; i < tnfa->num_submatches; i++)
3397         if (tnfa->submatch_data[i].parents)
3398           xfree(tnfa->submatch_data[i].parents);
3399       xfree(tnfa->submatch_data);
3400     }
3401
3402   if (tnfa->tag_directions)
3403     xfree(tnfa->tag_directions);
3404   if (tnfa->firstpos_chars)
3405     xfree(tnfa->firstpos_chars);
3406   if (tnfa->minimal_tags)
3407     xfree(tnfa->minimal_tags);
3408   xfree(tnfa);
3409 }