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   wchar_t wc;
 965   int clen;
 966
 967   if (!ctx->nofirstsub)
 968     {
 969       STACK_PUSH(stack, int, ctx->submatch_id);
 970       STACK_PUSH(stack, int, PARSE_MARK_FOR_SUBMATCH);
 971       ctx->submatch_id++;
 972     }
 973   STACK_PUSH(stack, int, PARSE_RE);
 974   ctx->re_start = ctx->re;
 975
 976
 977   /* The following is basically just a recursive descent parser.  I use
 978      an explicit stack instead of recursive functions mostly because of
 979      two reasons: compatibility with systems which have an overflowable
 980      call stack, and efficiency (both in lines of code and speed).  */
 981   while (tre_stack_num_objects(stack) > bottom && status == REG_OK)
 982     {
 983       if (status != REG_OK)
 984         break;
 985       symbol = tre_stack_pop_int(stack);
 986       switch (symbol)
 987         {
 988         case PARSE_RE:
 989           /* Parse a full regexp.  A regexp is one or more branches,
 990              separated by the union operator `|'. */
 991           if (ctx->cflags & REG_EXTENDED)
 992             STACK_PUSHX(stack, int, PARSE_UNION);
 993           STACK_PUSHX(stack, int, PARSE_BRANCH);
 994           break;
 995
 996         case PARSE_BRANCH:
 997           /* Parse a branch.  A branch is one or more pieces, concatenated.
 998              A piece is an atom possibly followed by a postfix operator. */
 999           STACK_PUSHX(stack, int, PARSE_CATENATION);
1000           STACK_PUSHX(stack, int, PARSE_PIECE);
1001           break;
1002
1003         case PARSE_PIECE:
1004           /* Parse a piece.  A piece is an atom possibly followed by one
1005              or more postfix operators. */
1006             STACK_PUSHX(stack, int, PARSE_POSTFIX);
1007           STACK_PUSHX(stack, int, PARSE_ATOM);
1008           break;
1009
1010         case PARSE_CATENATION:
1011           /* If the expression has not ended, parse another piece. */
1012           {
1013             tre_char_t c;
1014             if (!*ctx->re)
1015               break;
1016             c = *ctx->re;
1017                 if (ctx->cflags & REG_EXTENDED && c == CHAR_PIPE)
1018                   break;
1019                 if ((ctx->cflags & REG_EXTENDED
1020                      && c == CHAR_RPAREN && depth > 0)
1021                     || (!(ctx->cflags & REG_EXTENDED)
1022                         && (c == CHAR_BACKSLASH
1023                             && *(ctx->re + 1) == CHAR_RPAREN)))
1024                   {
1025                     if (!(ctx->cflags & REG_EXTENDED) && depth == 0)
1026                       status = REG_EPAREN;
1027                     depth--;
1028                     if (!(ctx->cflags & REG_EXTENDED))
1029                       ctx->re += 2;
1030                     break;
1031                   }
1032
1033               {
1034                 /* Default case, left associative concatenation. */
1035                 STACK_PUSHX(stack, int, PARSE_CATENATION);
1036                 STACK_PUSHX(stack, voidptr, result);
1037                 STACK_PUSHX(stack, int, PARSE_POST_CATENATION);
1038                 STACK_PUSHX(stack, int, PARSE_PIECE);
1039               }
1040             break;
1041           }
1042
1043         case PARSE_POST_CATENATION:
1044           {
1045             tre_ast_node_t *tree = tre_stack_pop_voidptr(stack);
1046             tre_ast_node_t *tmp_node;
1047             tmp_node = tre_ast_new_catenation(ctx->mem, tree, result);
1048             if (!tmp_node)
1049               return REG_ESPACE;
1050             result = tmp_node;
1051             break;
1052           }
1053
1054         case PARSE_UNION:
1055           if (!*ctx->re)
1056             break;
1057           switch (*ctx->re)
1058             {
1059             case CHAR_PIPE:
1060               STACK_PUSHX(stack, int, PARSE_UNION);
1061               STACK_PUSHX(stack, voidptr, result);
1062               STACK_PUSHX(stack, int, PARSE_POST_UNION);
1063               STACK_PUSHX(stack, int, PARSE_BRANCH);
1064               ctx->re++;
1065               break;
1066
1067             case CHAR_RPAREN:
1068               ctx->re++;
1069               break;
1070
1071             default:
1072               break;
1073             }
1074           break;
1075
1076         case PARSE_POST_UNION:
1077           {
1078             tre_ast_node_t *tmp_node;
1079             tre_ast_node_t *tree = tre_stack_pop_voidptr(stack);
1080             tmp_node = tre_ast_new_union(ctx->mem, tree, result);
1081             if (!tmp_node)
1082               return REG_ESPACE;
1083             result = tmp_node;
1084             break;
1085           }
1086
1087         case PARSE_POSTFIX:
1088           /* Parse postfix operators. */
1089           if (!*ctx->re)
1090             break;
1091           switch (*ctx->re)
1092             {
1093             case CHAR_PLUS:
1094             case CHAR_QUESTIONMARK:
1095               if (!(ctx->cflags & REG_EXTENDED))
1096                 break;
1097                 /*FALLTHROUGH*/
1098             case CHAR_STAR:
1099               {
1100                 tre_ast_node_t *tmp_node;
1101                 int minimal = 0;
1102                 int rep_min = 0;
1103                 int rep_max = -1;
1104
1105                 if (*ctx->re == CHAR_PLUS)
1106                   rep_min = 1;
1107                 if (*ctx->re == CHAR_QUESTIONMARK)
1108                   rep_max = 1;
1109
1110                 ctx->re++;
1111                 tmp_node = tre_ast_new_iter(ctx->mem, result, rep_min, rep_max,
1112                                             minimal);
1113                 if (tmp_node == NULL)
1114                   return REG_ESPACE;
1115                 result = tmp_node;
1116                 STACK_PUSHX(stack, int, PARSE_POSTFIX);
1117               }
1118               break;
1119
1120             case CHAR_BACKSLASH:
1121               /* "\{" is special without REG_EXTENDED */
1122               if (!(ctx->cflags & REG_EXTENDED)
1123                   && *(ctx->re + 1) == CHAR_LBRACE)
1124                 {
1125                   ctx->re++;
1126                   goto parse_brace;
1127                 }
1128               else
1129                 break;
1130
1131             case CHAR_LBRACE:
1132               /* "{" is literal without REG_EXTENDED */
1133               if (!(ctx->cflags & REG_EXTENDED))
1134                 break;
1135
1136             parse_brace:
1137               ctx->re++;
1138
1139               status = tre_parse_bound(ctx, &result);
1140               if (status != REG_OK)
1141                 return status;
1142               STACK_PUSHX(stack, int, PARSE_POSTFIX);
1143               break;
1144             }
1145           break;
1146
1147         case PARSE_ATOM:
1148           /* Parse an atom.  An atom is a regular expression enclosed in `()',
1149              an empty set of `()', a bracket expression, `.', `^', `$',
1150              a `\' followed by a character, or a single character. */
1151
1152           switch (*ctx->re)
1153             {
1154             case CHAR_LPAREN:  /* parenthesized subexpression */
1155
1156               if (ctx->cflags & REG_EXTENDED)
1157                 {
1158                 lparen:
1159                   depth++;
1160                     {
1161                       ctx->re++;
1162                       /* First parse a whole RE, then mark the resulting tree
1163                          for submatching. */
1164                       STACK_PUSHX(stack, int, ctx->submatch_id);
1165                       STACK_PUSHX(stack, int, PARSE_MARK_FOR_SUBMATCH);
1166                       STACK_PUSHX(stack, int, PARSE_RE);
1167                       ctx->submatch_id++;
1168                     }
1169                 }
1170               else
1171                 goto parse_literal;
1172               break;
1173
1174             case CHAR_LBRACKET: /* bracket expression */
1175               ctx->re++;
1176               status = tre_parse_bracket(ctx, &result);
1177               if (status != REG_OK)
1178                 return status;
1179               break;
1180
1181             case CHAR_BACKSLASH:
1182               /* If this is "\(" or "\)" chew off the backslash and
1183                  try again. */
1184               if (!(ctx->cflags & REG_EXTENDED) && *(ctx->re + 1) == CHAR_LPAREN)
1185                 {
1186                   ctx->re++;
1187                   goto lparen;
1188                 }
1189               if (!(ctx->cflags & REG_EXTENDED) && *(ctx->re + 1) == CHAR_RPAREN)
1190                 {
1191                   goto empty_atom;
1192                 }
1193
1194               /* If a macro is used, parse the expanded macro recursively. */
1195               {
1196                 const char *buf = tre_expand_macro(ctx->re + 1);
1197                 if (buf)
1198                   {
1199                     tre_parse_ctx_t subctx;
1200                     memcpy(&subctx, ctx, sizeof(subctx));
1201                     subctx.re = buf;
1202                     subctx.nofirstsub = 1;
1203                     status = tre_parse(&subctx);
1204                     if (status != REG_OK)
1205                       return status;
1206                     ctx->re += 2;
1207                     ctx->position = subctx.position;
1208                     result = subctx.result;
1209                     break;
1210                   }
1211               }
1212
1213               if (!ctx->re[1])
1214                 /* Trailing backslash. */
1215                 return REG_EESCAPE;
1216
1217               ctx->re++;
1218               switch (*ctx->re)
1219                 {
1220                 case 'b':
1221                   result = tre_ast_new_literal(ctx->mem, ASSERTION,
1222                                                ASSERT_AT_WB, -1);
1223                   ctx->re++;
1224                   break;
1225                 case 'B':
1226                   result = tre_ast_new_literal(ctx->mem, ASSERTION,
1227                                                ASSERT_AT_WB_NEG, -1);
1228                   ctx->re++;
1229                   break;
1230                 case '<':
1231                   result = tre_ast_new_literal(ctx->mem, ASSERTION,
1232                                                ASSERT_AT_BOW, -1);
1233                   ctx->re++;
1234                   break;
1235                 case '>':
1236                   result = tre_ast_new_literal(ctx->mem, ASSERTION,
1237                                                ASSERT_AT_EOW, -1);
1238                   ctx->re++;
1239                   break;
1240                 case 'x':
1241                   ctx->re++;
1242                   if (ctx->re[0] != CHAR_LBRACE)
1243                     {
1244                       /* 8 bit hex char. */
1245                       char tmp[3] = {0, 0, 0};
1246                       long val;
1247
1248                       if (tre_isxdigit(ctx->re[0]))
1249                         {
1250                           tmp[0] = (char)ctx->re[0];
1251                           ctx->re++;
1252                         }
1253                       if (tre_isxdigit(ctx->re[0]))
1254                         {
1255                           tmp[1] = (char)ctx->re[0];
1256                           ctx->re++;
1257                         }
1258                       val = strtol(tmp, NULL, 16);
1259                       result = tre_ast_new_literal(ctx->mem, (int)val,
1260                                                    (int)val, ctx->position);
1261                       ctx->position++;
1262                       break;
1263                     }
1264                   else if (*ctx->re)
1265                     {
1266                       /* Wide char. */
1267                       char tmp[32];
1268                       long val;
1269                       int i = 0;
1270                       ctx->re++;
1271                       while (*ctx->re && i < sizeof tmp)
1272                         {
1273                           if (ctx->re[0] == CHAR_RBRACE)
1274                             break;
1275                           if (tre_isxdigit(ctx->re[0]))
1276                             {
1277                               tmp[i] = (char)ctx->re[0];
1278                               i++;
1279                               ctx->re++;
1280                               continue;
1281                             }
1282                           return REG_EBRACE;
1283                         }
1284                       ctx->re++;
1285                       tmp[i] = 0;
1286                       val = strtol(tmp, NULL, 16);
1287                       result = tre_ast_new_literal(ctx->mem, (int)val, (int)val,
1288                                                    ctx->position);
1289                       ctx->position++;
1290                       break;
1291                     }
1292                   /*FALLTHROUGH*/
1293
1294                 default:
1295                   if (tre_isdigit(*ctx->re))
1296                     {
1297                       /* Back reference. */
1298                       int val = *ctx->re - '0';
1299                       result = tre_ast_new_literal(ctx->mem, BACKREF, val,
1300                                                    ctx->position);
1301                       if (result == NULL)
1302                         return REG_ESPACE;
1303                       ctx->position++;
1304                       ctx->max_backref = MAX(val, ctx->max_backref);
1305                       ctx->re++;
1306                     }
1307                   else
1308                     {
1309                       /* Escaped character. */
1310                       result = tre_ast_new_literal(ctx->mem, *ctx->re, *ctx->re,
1311                                                    ctx->position);
1312                       ctx->position++;
1313                       ctx->re++;
1314                     }
1315                   break;
1316                 }
1317               if (result == NULL)
1318                 return REG_ESPACE;
1319               break;
1320
1321             case CHAR_PERIOD:    /* the any-symbol */
1322               if (ctx->cflags & REG_NEWLINE)
1323                 {
1324                   tre_ast_node_t *tmp1;
1325                   tre_ast_node_t *tmp2;
1326                   tmp1 = tre_ast_new_literal(ctx->mem, 0, '\n' - 1,
1327                                              ctx->position);
1328                   if (!tmp1)
1329                     return REG_ESPACE;
1330                   tmp2 = tre_ast_new_literal(ctx->mem, '\n' + 1, TRE_CHAR_MAX,
1331                                              ctx->position + 1);
1332                   if (!tmp2)
1333                     return REG_ESPACE;
1334                   result = tre_ast_new_union(ctx->mem, tmp1, tmp2);
1335                   if (!result)
1336                     return REG_ESPACE;
1337                   ctx->position += 2;
1338                 }
1339               else
1340                 {
1341                   result = tre_ast_new_literal(ctx->mem, 0, TRE_CHAR_MAX,
1342                                                ctx->position);
1343                   if (!result)
1344                     return REG_ESPACE;
1345                   ctx->position++;
1346                 }
1347               ctx->re++;
1348               break;
1349
1350             case CHAR_CARET:     /* beginning of line assertion */
1351               /* '^' has a special meaning everywhere in EREs, and at
1352                  beginning of BRE. */
1353               if (ctx->cflags & REG_EXTENDED
1354                   || ctx->re == ctx->re_start)
1355                 {
1356                   if (!(ctx->cflags & REG_EXTENDED))
1357                     STACK_PUSHX(stack, int, PARSE_CATENATION);
1358                   result = tre_ast_new_literal(ctx->mem, ASSERTION,
1359                                                ASSERT_AT_BOL, -1);
1360                   if (result == NULL)
1361                     return REG_ESPACE;
1362                   ctx->re++;
1363                 }
1364               else
1365                 goto parse_literal;
1366               break;
1367
1368             case CHAR_DOLLAR:    /* end of line assertion. */
1369               /* '$' is special everywhere in EREs, and in the end of the
1370                  string in BREs. */
1371               if (ctx->cflags & REG_EXTENDED
1372                   || !*(ctx->re + 1))
1373                 {
1374                   result = tre_ast_new_literal(ctx->mem, ASSERTION,
1375                                                ASSERT_AT_EOL, -1);
1376                   if (result == NULL)
1377                     return REG_ESPACE;
1378                   ctx->re++;
1379                 }
1380               else
1381                 goto parse_literal;
1382               break;
1383
1384             case CHAR_RPAREN:
1385               if (!depth)
1386                 goto parse_literal;
1387             case CHAR_STAR:
1388             case CHAR_PIPE:
1389             case CHAR_LBRACE:
1390             case CHAR_PLUS:
1391             case CHAR_QUESTIONMARK:
1392               if (!(ctx->cflags & REG_EXTENDED))
1393                 goto parse_literal;
1394
1395             case 0:
1396             empty_atom:
1397               result = tre_ast_new_literal(ctx->mem, EMPTY, -1, -1);
1398               if (!result)
1399                 return REG_ESPACE;
1400               break;
1401
1402             default:
1403             parse_literal:
1404
1405               clen = mbtowc(&wc, ctx->re, -1);
1406               if (clen<0) clen=1, wc=WEOF;
1407
1408               /* Note that we can't use an tre_isalpha() test here, since there
1409                  may be characters which are alphabetic but neither upper or
1410                  lower case. */
1411               if (ctx->cflags & REG_ICASE
1412                   && (tre_isupper(wc) || tre_islower(wc)))
1413                 {
1414                   tre_ast_node_t *tmp1;
1415                   tre_ast_node_t *tmp2;
1416
1417                   /* XXX - Can there be more than one opposite-case
1418                      counterpoints for some character in some locale?  Or
1419                      more than two characters which all should be regarded
1420                      the same character if case is ignored?  If yes, there
1421                      does not seem to be a portable way to detect it.  I guess
1422                      that at least for multi-character collating elements there
1423                      could be several opposite-case counterpoints, but they
1424                      cannot be supported portably anyway. */
1425                   tmp1 = tre_ast_new_literal(ctx->mem, tre_toupper(wc),
1426                                              tre_toupper(wc),
1427                                              ctx->position);
1428                   if (!tmp1)
1429                     return REG_ESPACE;
1430                   tmp2 = tre_ast_new_literal(ctx->mem, tre_tolower(wc),
1431                                              tre_tolower(wc),
1432                                              ctx->position);
1433                   if (!tmp2)
1434                     return REG_ESPACE;
1435                   result = tre_ast_new_union(ctx->mem, tmp1, tmp2);
1436                   if (!result)
1437                     return REG_ESPACE;
1438                 }
1439               else
1440                 {
1441                   result = tre_ast_new_literal(ctx->mem, wc, wc,
1442                                                ctx->position);
1443                   if (!result)
1444                     return REG_ESPACE;
1445                 }
1446               ctx->position++;
1447               ctx->re += clen;
1448               break;
1449             }
1450           break;
1451
1452         case PARSE_MARK_FOR_SUBMATCH:
1453           {
1454             int submatch_id = tre_stack_pop_int(stack);
1455
1456             if (result->submatch_id >= 0)
1457               {
1458                 tre_ast_node_t *n, *tmp_node;
1459                 n = tre_ast_new_literal(ctx->mem, EMPTY, -1, -1);
1460                 if (n == NULL)
1461                   return REG_ESPACE;
1462                 tmp_node = tre_ast_new_catenation(ctx->mem, n, result);
1463                 if (tmp_node == NULL)
1464                   return REG_ESPACE;
1465                 tmp_node->num_submatches = result->num_submatches;
1466                 result = tmp_node;
1467               }
1468             result->submatch_id = submatch_id;
1469             result->num_submatches++;
1470             break;
1471           }
1472
1473         case PARSE_RESTORE_CFLAGS:
1474           ctx->cflags = tre_stack_pop_int(stack);
1475           break;
1476
1477         default:
1478           assert(0);
1479           break;
1480         }
1481     }
1482
1483   /* Check for missing closing parentheses. */
1484   if (depth > 0)
1485     return REG_EPAREN;
1486
1487   if (status == REG_OK)
1488     ctx->result = result;
1489
1490   return status;
1491 }
1492
1493
1494
1495 /***********************************************************************
1496  from tre-compile.c
1497 ***********************************************************************/
1498
1499
1500 /*
1501   TODO:
1502    - Fix tre_ast_to_tnfa() to recurse using a stack instead of recursive
1503      function calls.
1504 */
1505
1506 /*
1507   Algorithms to setup tags so that submatch addressing can be done.
1508 */
1509
1510
1511 /* Inserts a catenation node to the root of the tree given in `node'.
1512    As the left child a new tag with number `tag_id' to `node' is added,
1513    and the right child is the old root. */
1514 static reg_errcode_t
1515 tre_add_tag_left(tre_mem_t mem, tre_ast_node_t *node, int tag_id)
1516 {
1517   tre_catenation_t *c;
1518
1519   c = tre_mem_alloc(mem, sizeof(*c));
1520   if (c == NULL)
1521     return REG_ESPACE;
1522   c->left = tre_ast_new_literal(mem, TAG, tag_id, -1);
1523   if (c->left == NULL)
1524     return REG_ESPACE;
1525   c->right = tre_mem_alloc(mem, sizeof(tre_ast_node_t));
1526   if (c->right == NULL)
1527     return REG_ESPACE;
1528
1529   c->right->obj = node->obj;
1530   c->right->type = node->type;
1531   c->right->nullable = -1;
1532   c->right->submatch_id = -1;
1533   c->right->firstpos = NULL;
1534   c->right->lastpos = NULL;
1535   c->right->num_tags = 0;
1536   node->obj = c;
1537   node->type = CATENATION;
1538   return REG_OK;
1539 }
1540
1541 /* Inserts a catenation node to the root of the tree given in `node'.
1542    As the right child a new tag with number `tag_id' to `node' is added,
1543    and the left child is the old root. */
1544 static reg_errcode_t
1545 tre_add_tag_right(tre_mem_t mem, tre_ast_node_t *node, int tag_id)
1546 {
1547   tre_catenation_t *c;
1548
1549   c = tre_mem_alloc(mem, sizeof(*c));
1550   if (c == NULL)
1551     return REG_ESPACE;
1552   c->right = tre_ast_new_literal(mem, TAG, tag_id, -1);
1553   if (c->right == NULL)
1554     return REG_ESPACE;
1555   c->left = tre_mem_alloc(mem, sizeof(tre_ast_node_t));
1556   if (c->left == NULL)
1557     return REG_ESPACE;
1558
1559   c->left->obj = node->obj;
1560   c->left->type = node->type;
1561   c->left->nullable = -1;
1562   c->left->submatch_id = -1;
1563   c->left->firstpos = NULL;
1564   c->left->lastpos = NULL;
1565   c->left->num_tags = 0;
1566   node->obj = c;
1567   node->type = CATENATION;
1568   return REG_OK;
1569 }
1570
1571 typedef enum {
1572   ADDTAGS_RECURSE,
1573   ADDTAGS_AFTER_ITERATION,
1574   ADDTAGS_AFTER_UNION_LEFT,
1575   ADDTAGS_AFTER_UNION_RIGHT,
1576   ADDTAGS_AFTER_CAT_LEFT,
1577   ADDTAGS_AFTER_CAT_RIGHT,
1578   ADDTAGS_SET_SUBMATCH_END
1579 } tre_addtags_symbol_t;
1580
1581
1582 typedef struct {
1583   int tag;
1584   int next_tag;
1585 } tre_tag_states_t;
1586
1587
1588 /* Go through `regset' and set submatch data for submatches that are
1589    using this tag. */
1590 static void
1591 tre_purge_regset(int *regset, tre_tnfa_t *tnfa, int tag)
1592 {
1593   int i;
1594
1595   for (i = 0; regset[i] >= 0; i++)
1596     {
1597       int id = regset[i] / 2;
1598       int start = !(regset[i] % 2);
1599       if (start)
1600         tnfa->submatch_data[id].so_tag = tag;
1601       else
1602         tnfa->submatch_data[id].eo_tag = tag;
1603     }
1604   regset[0] = -1;
1605 }
1606
1607
1608 /* Adds tags to appropriate locations in the parse tree in `tree', so that
1609    subexpressions marked for submatch addressing can be traced. */
1610 static reg_errcode_t
1611 tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree,
1612              tre_tnfa_t *tnfa)
1613 {
1614   reg_errcode_t status = REG_OK;
1615   tre_addtags_symbol_t symbol;
1616   tre_ast_node_t *node = tree; /* Tree node we are currently looking at. */
1617   int bottom = tre_stack_num_objects(stack);
1618   /* True for first pass (counting number of needed tags) */
1619   int first_pass = (mem == NULL || tnfa == NULL);
1620   int *regset, *orig_regset;
1621   int num_tags = 0; /* Total number of tags. */
1622   int num_minimals = 0;  /* Number of special minimal tags. */
1623   int tag = 0;      /* The tag that is to be added next. */
1624   int next_tag = 1; /* Next tag to use after this one. */
1625   int *parents;     /* Stack of submatches the current submatch is
1626                        contained in. */
1627   int minimal_tag = -1; /* Tag that marks the beginning of a minimal match. */
1628   tre_tag_states_t *saved_states;
1629
1630   tre_tag_direction_t direction = TRE_TAG_MINIMIZE;
1631   if (!first_pass)
1632     {
1633       tnfa->end_tag = 0;
1634       tnfa->minimal_tags[0] = -1;
1635     }
1636
1637   regset = xmalloc(sizeof(*regset) * ((tnfa->num_submatches + 1) * 2));
1638   if (regset == NULL)
1639     return REG_ESPACE;
1640   regset[0] = -1;
1641   orig_regset = regset;
1642
1643   parents = xmalloc(sizeof(*parents) * (tnfa->num_submatches + 1));
1644   if (parents == NULL)
1645     {
1646       xfree(regset);
1647       return REG_ESPACE;
1648     }
1649   parents[0] = -1;
1650
1651   saved_states = xmalloc(sizeof(*saved_states) * (tnfa->num_submatches + 1));
1652   if (saved_states == NULL)
1653     {
1654       xfree(regset);
1655       xfree(parents);
1656       return REG_ESPACE;
1657     }
1658   else
1659     {
1660       unsigned int i;
1661       for (i = 0; i <= tnfa->num_submatches; i++)
1662         saved_states[i].tag = -1;
1663     }
1664
1665   STACK_PUSH(stack, voidptr, node);
1666   STACK_PUSH(stack, int, ADDTAGS_RECURSE);
1667
1668   while (tre_stack_num_objects(stack) > bottom)
1669     {
1670       if (status != REG_OK)
1671         break;
1672
1673       symbol = (tre_addtags_symbol_t)tre_stack_pop_int(stack);
1674       switch (symbol)
1675         {
1676
1677         case ADDTAGS_SET_SUBMATCH_END:
1678           {
1679             int id = tre_stack_pop_int(stack);
1680             int i;
1681
1682             /* Add end of this submatch to regset. */
1683             for (i = 0; regset[i] >= 0; i++);
1684             regset[i] = id * 2 + 1;
1685             regset[i + 1] = -1;
1686
1687             /* Pop this submatch from the parents stack. */
1688             for (i = 0; parents[i] >= 0; i++);
1689             parents[i - 1] = -1;
1690             break;
1691           }
1692
1693         case ADDTAGS_RECURSE:
1694           node = tre_stack_pop_voidptr(stack);
1695
1696           if (node->submatch_id >= 0)
1697             {
1698               int id = node->submatch_id;
1699               int i;
1700
1701
1702               /* Add start of this submatch to regset. */
1703               for (i = 0; regset[i] >= 0; i++);
1704               regset[i] = id * 2;
1705               regset[i + 1] = -1;
1706
1707               if (!first_pass)
1708                 {
1709                   for (i = 0; parents[i] >= 0; i++);
1710                   tnfa->submatch_data[id].parents = NULL;
1711                   if (i > 0)
1712                     {
1713                       int *p = xmalloc(sizeof(*p) * (i + 1));
1714                       if (p == NULL)
1715                         {
1716                           status = REG_ESPACE;
1717                           break;
1718                         }
1719                       assert(tnfa->submatch_data[id].parents == NULL);
1720                       tnfa->submatch_data[id].parents = p;
1721                       for (i = 0; parents[i] >= 0; i++)
1722                         p[i] = parents[i];
1723                       p[i] = -1;
1724                     }
1725                 }
1726
1727               /* Add end of this submatch to regset after processing this
1728                  node. */
1729               STACK_PUSHX(stack, int, node->submatch_id);
1730               STACK_PUSHX(stack, int, ADDTAGS_SET_SUBMATCH_END);
1731             }
1732
1733           switch (node->type)
1734             {
1735             case LITERAL:
1736               {
1737                 tre_literal_t *lit = node->obj;
1738
1739                 if (!IS_SPECIAL(lit) || IS_BACKREF(lit))
1740                   {
1741                     int i;
1742                     if (regset[0] >= 0)
1743                       {
1744                         /* Regset is not empty, so add a tag before the
1745                            literal or backref. */
1746                         if (!first_pass)
1747                           {
1748                             status = tre_add_tag_left(mem, node, tag);
1749                             tnfa->tag_directions[tag] = direction;
1750                             if (minimal_tag >= 0)
1751                               {
1752                                 for (i = 0; tnfa->minimal_tags[i] >= 0; i++);
1753                                 tnfa->minimal_tags[i] = tag;
1754                                 tnfa->minimal_tags[i + 1] = minimal_tag;
1755                                 tnfa->minimal_tags[i + 2] = -1;
1756                                 minimal_tag = -1;
1757                                 num_minimals++;
1758                               }
1759                             tre_purge_regset(regset, tnfa, tag);
1760                           }
1761                         else
1762                           {
1763                             node->num_tags = 1;
1764                           }
1765
1766                         regset[0] = -1;
1767                         tag = next_tag;
1768                         num_tags++;
1769                         next_tag++;
1770                       }
1771                   }
1772                 else
1773                   {
1774                     assert(!IS_TAG(lit));
1775                   }
1776                 break;
1777               }
1778             case CATENATION:
1779               {
1780                 tre_catenation_t *cat = node->obj;
1781                 tre_ast_node_t *left = cat->left;
1782                 tre_ast_node_t *right = cat->right;
1783                 int reserved_tag = -1;
1784
1785
1786                 /* After processing right child. */
1787                 STACK_PUSHX(stack, voidptr, node);
1788                 STACK_PUSHX(stack, int, ADDTAGS_AFTER_CAT_RIGHT);
1789
1790                 /* Process right child. */
1791                 STACK_PUSHX(stack, voidptr, right);
1792                 STACK_PUSHX(stack, int, ADDTAGS_RECURSE);
1793
1794                 /* After processing left child. */
1795                 STACK_PUSHX(stack, int, next_tag + left->num_tags);
1796                 if (left->num_tags > 0 && right->num_tags > 0)
1797                   {
1798                     /* Reserve the next tag to the right child. */
1799                     reserved_tag = next_tag;
1800                     next_tag++;
1801                   }
1802                 STACK_PUSHX(stack, int, reserved_tag);
1803                 STACK_PUSHX(stack, int, ADDTAGS_AFTER_CAT_LEFT);
1804
1805                 /* Process left child. */
1806                 STACK_PUSHX(stack, voidptr, left);
1807                 STACK_PUSHX(stack, int, ADDTAGS_RECURSE);
1808
1809                 }
1810               break;
1811             case ITERATION:
1812               {
1813                 tre_iteration_t *iter = node->obj;
1814
1815                 if (first_pass)
1816                   {
1817                     STACK_PUSHX(stack, int, regset[0] >= 0 || iter->minimal);
1818                   }
1819                 else
1820                   {
1821                     STACK_PUSHX(stack, int, tag);
1822                     STACK_PUSHX(stack, int, iter->minimal);
1823                   }
1824                 STACK_PUSHX(stack, voidptr, node);
1825                 STACK_PUSHX(stack, int, ADDTAGS_AFTER_ITERATION);
1826
1827                 STACK_PUSHX(stack, voidptr, iter->arg);
1828                 STACK_PUSHX(stack, int, ADDTAGS_RECURSE);
1829
1830                 /* Regset is not empty, so add a tag here. */
1831                 if (regset[0] >= 0 || iter->minimal)
1832                   {
1833                     if (!first_pass)
1834                       {
1835                         int i;
1836                         status = tre_add_tag_left(mem, node, tag);
1837                         if (iter->minimal)
1838                           tnfa->tag_directions[tag] = TRE_TAG_MAXIMIZE;
1839                         else
1840                           tnfa->tag_directions[tag] = direction;
1841                         if (minimal_tag >= 0)
1842                           {
1843                             for (i = 0; tnfa->minimal_tags[i] >= 0; i++);
1844                             tnfa->minimal_tags[i] = tag;
1845                             tnfa->minimal_tags[i + 1] = minimal_tag;
1846                             tnfa->minimal_tags[i + 2] = -1;
1847                             minimal_tag = -1;
1848                             num_minimals++;
1849                           }
1850                         tre_purge_regset(regset, tnfa, tag);
1851                       }
1852
1853                     regset[0] = -1;
1854                     tag = next_tag;
1855                     num_tags++;
1856                     next_tag++;
1857                   }
1858                 direction = TRE_TAG_MINIMIZE;
1859               }
1860               break;
1861             case UNION:
1862               {
1863                 tre_union_t *uni = node->obj;
1864                 tre_ast_node_t *left = uni->left;
1865                 tre_ast_node_t *right = uni->right;
1866                 int left_tag;
1867                 int right_tag;
1868
1869                 if (regset[0] >= 0)
1870                   {
1871                     left_tag = next_tag;
1872                     right_tag = next_tag + 1;
1873                   }
1874                 else
1875                   {
1876                     left_tag = tag;
1877                     right_tag = next_tag;
1878                   }
1879
1880                 /* After processing right child. */
1881                 STACK_PUSHX(stack, int, right_tag);
1882                 STACK_PUSHX(stack, int, left_tag);
1883                 STACK_PUSHX(stack, voidptr, regset);
1884                 STACK_PUSHX(stack, int, regset[0] >= 0);
1885                 STACK_PUSHX(stack, voidptr, node);
1886                 STACK_PUSHX(stack, voidptr, right);
1887                 STACK_PUSHX(stack, voidptr, left);
1888                 STACK_PUSHX(stack, int, ADDTAGS_AFTER_UNION_RIGHT);
1889
1890                 /* Process right child. */
1891                 STACK_PUSHX(stack, voidptr, right);
1892                 STACK_PUSHX(stack, int, ADDTAGS_RECURSE);
1893
1894                 /* After processing left child. */
1895                 STACK_PUSHX(stack, int, ADDTAGS_AFTER_UNION_LEFT);
1896
1897                 /* Process left child. */
1898                 STACK_PUSHX(stack, voidptr, left);
1899                 STACK_PUSHX(stack, int, ADDTAGS_RECURSE);
1900
1901                 /* Regset is not empty, so add a tag here. */
1902                 if (regset[0] >= 0)
1903                   {
1904                     if (!first_pass)
1905                       {
1906                         int i;
1907                         status = tre_add_tag_left(mem, node, tag);
1908                         tnfa->tag_directions[tag] = direction;
1909                         if (minimal_tag >= 0)
1910                           {
1911                             for (i = 0; tnfa->minimal_tags[i] >= 0; i++);
1912                             tnfa->minimal_tags[i] = tag;
1913                             tnfa->minimal_tags[i + 1] = minimal_tag;
1914                             tnfa->minimal_tags[i + 2] = -1;
1915                             minimal_tag = -1;
1916                             num_minimals++;
1917                           }
1918                         tre_purge_regset(regset, tnfa, tag);
1919                       }
1920
1921                     regset[0] = -1;
1922                     tag = next_tag;
1923                     num_tags++;
1924                     next_tag++;
1925                   }
1926
1927                 if (node->num_submatches > 0)
1928                   {
1929                     /* The next two tags are reserved for markers. */
1930                     next_tag++;
1931                     tag = next_tag;
1932                     next_tag++;
1933                   }
1934
1935                 break;
1936               }
1937             }
1938
1939           if (node->submatch_id >= 0)
1940             {
1941               int i;
1942               /* Push this submatch on the parents stack. */
1943               for (i = 0; parents[i] >= 0; i++);
1944               parents[i] = node->submatch_id;
1945               parents[i + 1] = -1;
1946             }
1947
1948           break; /* end case: ADDTAGS_RECURSE */
1949
1950         case ADDTAGS_AFTER_ITERATION:
1951           {
1952             int minimal = 0;
1953             int enter_tag;
1954             node = tre_stack_pop_voidptr(stack);
1955             if (first_pass)
1956               {
1957                 node->num_tags = ((tre_iteration_t *)node->obj)->arg->num_tags
1958                   + tre_stack_pop_int(stack);
1959                 minimal_tag = -1;
1960               }
1961             else
1962               {
1963                 minimal = tre_stack_pop_int(stack);
1964                 enter_tag = tre_stack_pop_int(stack);
1965                 if (minimal)
1966                   minimal_tag = enter_tag;
1967               }
1968
1969             if (!first_pass)
1970               {
1971                 if (minimal)
1972                   direction = TRE_TAG_MINIMIZE;
1973                 else
1974                   direction = TRE_TAG_MAXIMIZE;
1975               }
1976             break;
1977           }
1978
1979         case ADDTAGS_AFTER_CAT_LEFT:
1980           {
1981             int new_tag = tre_stack_pop_int(stack);
1982             next_tag = tre_stack_pop_int(stack);
1983             if (new_tag >= 0)
1984               {
1985                 tag = new_tag;
1986               }
1987             break;
1988           }
1989
1990         case ADDTAGS_AFTER_CAT_RIGHT:
1991           node = tre_stack_pop_voidptr(stack);
1992           if (first_pass)
1993             node->num_tags = ((tre_catenation_t *)node->obj)->left->num_tags
1994               + ((tre_catenation_t *)node->obj)->right->num_tags;
1995           break;
1996
1997         case ADDTAGS_AFTER_UNION_LEFT:
1998           /* Lift the bottom of the `regset' array so that when processing
1999              the right operand the items currently in the array are
2000              invisible.  The original bottom was saved at ADDTAGS_UNION and
2001              will be restored at ADDTAGS_AFTER_UNION_RIGHT below. */
2002           while (*regset >= 0)
2003             regset++;
2004           break;
2005
2006         case ADDTAGS_AFTER_UNION_RIGHT:
2007           {
2008             int added_tags, tag_left, tag_right;
2009             tre_ast_node_t *left = tre_stack_pop_voidptr(stack);
2010             tre_ast_node_t *right = tre_stack_pop_voidptr(stack);
2011             node = tre_stack_pop_voidptr(stack);
2012             added_tags = tre_stack_pop_int(stack);
2013             if (first_pass)
2014               {
2015                 node->num_tags = ((tre_union_t *)node->obj)->left->num_tags
2016                   + ((tre_union_t *)node->obj)->right->num_tags + added_tags
2017                   + ((node->num_submatches > 0) ? 2 : 0);
2018               }
2019             regset = tre_stack_pop_voidptr(stack);
2020             tag_left = tre_stack_pop_int(stack);
2021             tag_right = tre_stack_pop_int(stack);
2022
2023             /* Add tags after both children, the left child gets a smaller
2024                tag than the right child.  This guarantees that we prefer
2025                the left child over the right child. */
2026             /* XXX - This is not always necessary (if the children have
2027                tags which must be seen for every match of that child). */
2028             /* XXX - Check if this is the only place where tre_add_tag_right
2029                is used.  If so, use tre_add_tag_left (putting the tag before
2030                the child as opposed after the child) and throw away
2031                tre_add_tag_right. */
2032             if (node->num_submatches > 0)
2033               {
2034                 if (!first_pass)
2035                   {
2036                     status = tre_add_tag_right(mem, left, tag_left);
2037                     tnfa->tag_directions[tag_left] = TRE_TAG_MAXIMIZE;
2038                     status = tre_add_tag_right(mem, right, tag_right);
2039                     tnfa->tag_directions[tag_right] = TRE_TAG_MAXIMIZE;
2040                   }
2041                 num_tags += 2;
2042               }
2043             direction = TRE_TAG_MAXIMIZE;
2044             break;
2045           }
2046
2047         default:
2048           assert(0);
2049           break;
2050
2051         } /* end switch(symbol) */
2052     } /* end while(tre_stack_num_objects(stack) > bottom) */
2053
2054   if (!first_pass)
2055     tre_purge_regset(regset, tnfa, tag);
2056
2057   if (!first_pass && minimal_tag >= 0)
2058     {
2059       int i;
2060       for (i = 0; tnfa->minimal_tags[i] >= 0; i++);
2061       tnfa->minimal_tags[i] = tag;
2062       tnfa->minimal_tags[i + 1] = minimal_tag;
2063       tnfa->minimal_tags[i + 2] = -1;
2064       minimal_tag = -1;
2065       num_minimals++;
2066     }
2067
2068   assert(tree->num_tags == num_tags);
2069   tnfa->end_tag = num_tags;
2070   tnfa->num_tags = num_tags;
2071   tnfa->num_minimals = num_minimals;
2072   xfree(orig_regset);
2073   xfree(parents);
2074   xfree(saved_states);
2075   return status;
2076 }
2077
2078
2079
2080 /*
2081   AST to TNFA compilation routines.
2082 */
2083
2084 typedef enum {
2085   COPY_RECURSE,
2086   COPY_SET_RESULT_PTR
2087 } tre_copyast_symbol_t;
2088
2089 /* Flags for tre_copy_ast(). */
2090 #define COPY_REMOVE_TAGS         1
2091 #define COPY_MAXIMIZE_FIRST_TAG  2
2092
2093 static reg_errcode_t
2094 tre_copy_ast(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *ast,
2095              int flags, int *pos_add, tre_tag_direction_t *tag_directions,
2096              tre_ast_node_t **copy, int *max_pos)
2097 {
2098   reg_errcode_t status = REG_OK;
2099   int bottom = tre_stack_num_objects(stack);
2100   int num_copied = 0;
2101   int first_tag = 1;
2102   tre_ast_node_t **result = copy;
2103   tre_copyast_symbol_t symbol;
2104
2105   STACK_PUSH(stack, voidptr, ast);
2106   STACK_PUSH(stack, int, COPY_RECURSE);
2107
2108   while (status == REG_OK && tre_stack_num_objects(stack) > bottom)
2109     {
2110       tre_ast_node_t *node;
2111       if (status != REG_OK)
2112         break;
2113
2114       symbol = (tre_copyast_symbol_t)tre_stack_pop_int(stack);
2115       switch (symbol)
2116         {
2117         case COPY_SET_RESULT_PTR:
2118           result = tre_stack_pop_voidptr(stack);
2119           break;
2120         case COPY_RECURSE:
2121           node = tre_stack_pop_voidptr(stack);
2122           switch (node->type)
2123             {
2124             case LITERAL:
2125               {
2126                 tre_literal_t *lit = node->obj;
2127                 int pos = lit->position;
2128                 int min = lit->code_min;
2129                 int max = lit->code_max;
2130                 if (!IS_SPECIAL(lit) || IS_BACKREF(lit))
2131                   {
2132                     /* XXX - e.g. [ab] has only one position but two
2133                        nodes, so we are creating holes in the state space
2134                        here.  Not fatal, just wastes memory. */
2135                     pos += *pos_add;
2136                     num_copied++;
2137                   }
2138                 else if (IS_TAG(lit) && (flags & COPY_REMOVE_TAGS))
2139                   {
2140                     /* Change this tag to empty. */
2141                     min = EMPTY;
2142                     max = pos = -1;
2143                   }
2144                 else if (IS_TAG(lit) && (flags & COPY_MAXIMIZE_FIRST_TAG)
2145                          && first_tag)
2146                   {
2147                     /* Maximize the first tag. */
2148                     tag_directions[max] = TRE_TAG_MAXIMIZE;
2149                     first_tag = 0;
2150                   }
2151                 *result = tre_ast_new_literal(mem, min, max, pos);
2152                 if (*result == NULL)
2153                   status = REG_ESPACE;
2154
2155                 if (pos > *max_pos)
2156                   *max_pos = pos;
2157                 break;
2158               }
2159             case UNION:
2160               {
2161                 tre_union_t *uni = node->obj;
2162                 tre_union_t *tmp;
2163                 *result = tre_ast_new_union(mem, uni->left, uni->right);
2164                 if (*result == NULL)
2165                   {
2166                     status = REG_ESPACE;
2167                     break;
2168                   }
2169                 tmp = (*result)->obj;
2170                 result = &tmp->left;
2171                 STACK_PUSHX(stack, voidptr, uni->right);
2172                 STACK_PUSHX(stack, int, COPY_RECURSE);
2173                 STACK_PUSHX(stack, voidptr, &tmp->right);
2174                 STACK_PUSHX(stack, int, COPY_SET_RESULT_PTR);
2175                 STACK_PUSHX(stack, voidptr, uni->left);
2176                 STACK_PUSHX(stack, int, COPY_RECURSE);
2177                 break;
2178               }
2179             case CATENATION:
2180               {
2181                 tre_catenation_t *cat = node->obj;
2182                 tre_catenation_t *tmp;
2183                 *result = tre_ast_new_catenation(mem, cat->left, cat->right);
2184                 if (*result == NULL)
2185                   {
2186                     status = REG_ESPACE;
2187                     break;
2188                   }
2189                 tmp = (*result)->obj;
2190                 tmp->left = NULL;
2191                 tmp->right = NULL;
2192                 result = &tmp->left;
2193
2194                 STACK_PUSHX(stack, voidptr, cat->right);
2195                 STACK_PUSHX(stack, int, COPY_RECURSE);
2196                 STACK_PUSHX(stack, voidptr, &tmp->right);
2197                 STACK_PUSHX(stack, int, COPY_SET_RESULT_PTR);
2198                 STACK_PUSHX(stack, voidptr, cat->left);
2199                 STACK_PUSHX(stack, int, COPY_RECURSE);
2200                 break;
2201               }
2202             case ITERATION:
2203               {
2204                 tre_iteration_t *iter = node->obj;
2205                 STACK_PUSHX(stack, voidptr, iter->arg);
2206                 STACK_PUSHX(stack, int, COPY_RECURSE);
2207                 *result = tre_ast_new_iter(mem, iter->arg, iter->min,
2208                                            iter->max, iter->minimal);
2209                 if (*result == NULL)
2210                   {
2211                     status = REG_ESPACE;
2212                     break;
2213                   }
2214                 iter = (*result)->obj;
2215                 result = &iter->arg;
2216                 break;
2217               }
2218             default:
2219               assert(0);
2220               break;
2221             }
2222           break;
2223         }
2224     }
2225   *pos_add += num_copied;
2226   return status;
2227 }
2228
2229 typedef enum {
2230   EXPAND_RECURSE,
2231   EXPAND_AFTER_ITER
2232 } tre_expand_ast_symbol_t;
2233
2234 /* Expands each iteration node that has a finite nonzero minimum or maximum
2235    iteration count to a catenated sequence of copies of the node. */
2236 static reg_errcode_t
2237 tre_expand_ast(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *ast,
2238                int *position, tre_tag_direction_t *tag_directions,
2239                int *max_depth)
2240 {
2241   reg_errcode_t status = REG_OK;
2242   int bottom = tre_stack_num_objects(stack);
2243   int pos_add = 0;
2244   int pos_add_total = 0;
2245   int max_pos = 0;
2246   int iter_depth = 0;
2247
2248   STACK_PUSHR(stack, voidptr, ast);
2249   STACK_PUSHR(stack, int, EXPAND_RECURSE);
2250   while (status == REG_OK && tre_stack_num_objects(stack) > bottom)
2251     {
2252       tre_ast_node_t *node;
2253       tre_expand_ast_symbol_t symbol;
2254
2255       if (status != REG_OK)
2256         break;
2257
2258       symbol = (tre_expand_ast_symbol_t)tre_stack_pop_int(stack);
2259       node = tre_stack_pop_voidptr(stack);
2260       switch (symbol)
2261         {
2262         case EXPAND_RECURSE:
2263           switch (node->type)
2264             {
2265             case LITERAL:
2266               {
2267                 tre_literal_t *lit= node->obj;
2268                 if (!IS_SPECIAL(lit) || IS_BACKREF(lit))
2269                   {
2270                     lit->position += pos_add;
2271                     if (lit->position > max_pos)
2272                       max_pos = lit->position;
2273                   }
2274                 break;
2275               }
2276             case UNION:
2277               {
2278                 tre_union_t *uni = node->obj;
2279                 STACK_PUSHX(stack, voidptr, uni->right);
2280                 STACK_PUSHX(stack, int, EXPAND_RECURSE);
2281                 STACK_PUSHX(stack, voidptr, uni->left);
2282                 STACK_PUSHX(stack, int, EXPAND_RECURSE);
2283                 break;
2284               }
2285             case CATENATION:
2286               {
2287                 tre_catenation_t *cat = node->obj;
2288                 STACK_PUSHX(stack, voidptr, cat->right);
2289                 STACK_PUSHX(stack, int, EXPAND_RECURSE);
2290                 STACK_PUSHX(stack, voidptr, cat->left);
2291                 STACK_PUSHX(stack, int, EXPAND_RECURSE);
2292                 break;
2293               }
2294             case ITERATION:
2295               {
2296                 tre_iteration_t *iter = node->obj;
2297                 STACK_PUSHX(stack, int, pos_add);
2298                 STACK_PUSHX(stack, voidptr, node);
2299                 STACK_PUSHX(stack, int, EXPAND_AFTER_ITER);
2300                 STACK_PUSHX(stack, voidptr, iter->arg);
2301                 STACK_PUSHX(stack, int, EXPAND_RECURSE);
2302                 /* If we are going to expand this node at EXPAND_AFTER_ITER
2303                    then don't increase the `pos' fields of the nodes now, it
2304                    will get done when expanding. */
2305                 if (iter->min > 1 || iter->max > 1)
2306                   pos_add = 0;
2307                 iter_depth++;
2308                 break;
2309               }
2310             default:
2311               assert(0);
2312               break;
2313             }
2314           break;
2315         case EXPAND_AFTER_ITER:
2316           {
2317             tre_iteration_t *iter = node->obj;
2318             int pos_add_last;
2319             pos_add = tre_stack_pop_int(stack);
2320             pos_add_last = pos_add;
2321             if (iter->min > 1 || iter->max > 1)
2322               {
2323                 tre_ast_node_t *seq1 = NULL, *seq2 = NULL;
2324                 int j;
2325                 int pos_add_save = pos_add;
2326
2327                 /* Create a catenated sequence of copies of the node. */
2328                 for (j = 0; j < iter->min; j++)
2329                   {
2330                     tre_ast_node_t *copy;
2331                     /* Remove tags from all but the last copy. */
2332                     int flags = ((j + 1 < iter->min)
2333                                  ? COPY_REMOVE_TAGS
2334                                  : COPY_MAXIMIZE_FIRST_TAG);
2335                     pos_add_save = pos_add;
2336                     status = tre_copy_ast(mem, stack, iter->arg, flags,
2337                                           &pos_add, tag_directions, &copy,
2338                                           &max_pos);
2339                     if (status != REG_OK)
2340                       return status;
2341                     if (seq1 != NULL)
2342                       seq1 = tre_ast_new_catenation(mem, seq1, copy);
2343                     else
2344                       seq1 = copy;
2345                     if (seq1 == NULL)
2346                       return REG_ESPACE;
2347                   }
2348
2349                 if (iter->max == -1)
2350                   {
2351                     /* No upper limit. */
2352                     pos_add_save = pos_add;
2353                     status = tre_copy_ast(mem, stack, iter->arg, 0,
2354                                           &pos_add, NULL, &seq2, &max_pos);
2355                     if (status != REG_OK)
2356                       return status;
2357                     seq2 = tre_ast_new_iter(mem, seq2, 0, -1, 0);
2358                     if (seq2 == NULL)
2359                       return REG_ESPACE;
2360                   }
2361                 else
2362                   {
2363                     for (j = iter->min; j < iter->max; j++)
2364                       {
2365                         tre_ast_node_t *tmp, *copy;
2366                         pos_add_save = pos_add;
2367                         status = tre_copy_ast(mem, stack, iter->arg, 0,
2368                                               &pos_add, NULL, &copy, &max_pos);
2369                         if (status != REG_OK)
2370                           return status;
2371                         if (seq2 != NULL)
2372                           seq2 = tre_ast_new_catenation(mem, copy, seq2);
2373                         else
2374                           seq2 = copy;
2375                         if (seq2 == NULL)
2376                           return REG_ESPACE;
2377                         tmp = tre_ast_new_literal(mem, EMPTY, -1, -1);
2378                         if (tmp == NULL)
2379                           return REG_ESPACE;
2380                         seq2 = tre_ast_new_union(mem, tmp, seq2);
2381                         if (seq2 == NULL)
2382                           return REG_ESPACE;
2383                       }
2384                   }
2385
2386                 pos_add = pos_add_save;
2387                 if (seq1 == NULL)
2388                   seq1 = seq2;
2389                 else if (seq2 != NULL)
2390                   seq1 = tre_ast_new_catenation(mem, seq1, seq2);
2391                 if (seq1 == NULL)
2392                   return REG_ESPACE;
2393                 node->obj = seq1->obj;
2394                 node->type = seq1->type;
2395               }
2396
2397             iter_depth--;
2398             pos_add_total += pos_add - pos_add_last;
2399             if (iter_depth == 0)
2400               pos_add = pos_add_total;
2401
2402             break;
2403           }
2404         default:
2405           assert(0);
2406           break;
2407         }
2408     }
2409
2410   *position += pos_add_total;
2411
2412   /* `max_pos' should never be larger than `*position' if the above
2413      code works, but just an extra safeguard let's make sure
2414      `*position' is set large enough so enough memory will be
2415      allocated for the transition table. */
2416   if (max_pos > *position)
2417     *position = max_pos;
2418
2419   return status;
2420 }
2421
2422 static tre_pos_and_tags_t *
2423 tre_set_empty(tre_mem_t mem)
2424 {
2425   tre_pos_and_tags_t *new_set;
2426
2427   new_set = tre_mem_calloc(mem, sizeof(*new_set));
2428   if (new_set == NULL)
2429     return NULL;
2430
2431   new_set[0].position = -1;
2432   new_set[0].code_min = -1;
2433   new_set[0].code_max = -1;
2434
2435   return new_set;
2436 }
2437
2438 static tre_pos_and_tags_t *
2439 tre_set_one(tre_mem_t mem, int position, int code_min, int code_max,
2440             tre_ctype_t class, tre_ctype_t *neg_classes, int backref)
2441 {
2442   tre_pos_and_tags_t *new_set;
2443
2444   new_set = tre_mem_calloc(mem, sizeof(*new_set) * 2);
2445   if (new_set == NULL)
2446     return NULL;
2447
2448   new_set[0].position = position;
2449   new_set[0].code_min = code_min;
2450   new_set[0].code_max = code_max;
2451   new_set[0].class = class;
2452   new_set[0].neg_classes = neg_classes;
2453   new_set[0].backref = backref;
2454   new_set[1].position = -1;
2455   new_set[1].code_min = -1;
2456   new_set[1].code_max = -1;
2457
2458   return new_set;
2459 }
2460
2461 static tre_pos_and_tags_t *
2462 tre_set_union(tre_mem_t mem, tre_pos_and_tags_t *set1, tre_pos_and_tags_t *set2,
2463               int *tags, int assertions)
2464 {
2465   int s1, s2, i, j;
2466   tre_pos_and_tags_t *new_set;
2467   int *new_tags;
2468   int num_tags;
2469
2470   for (num_tags = 0; tags != NULL && tags[num_tags] >= 0; num_tags++);
2471   for (s1 = 0; set1[s1].position >= 0; s1++);
2472   for (s2 = 0; set2[s2].position >= 0; s2++);
2473   new_set = tre_mem_calloc(mem, sizeof(*new_set) * (s1 + s2 + 1));
2474   if (!new_set )
2475     return NULL;
2476
2477   for (s1 = 0; set1[s1].position >= 0; s1++)
2478     {
2479       new_set[s1].position = set1[s1].position;
2480       new_set[s1].code_min = set1[s1].code_min;
2481       new_set[s1].code_max = set1[s1].code_max;
2482       new_set[s1].assertions = set1[s1].assertions | assertions;
2483       new_set[s1].class = set1[s1].class;
2484       new_set[s1].neg_classes = set1[s1].neg_classes;
2485       new_set[s1].backref = set1[s1].backref;
2486       if (set1[s1].tags == NULL && tags == NULL)
2487         new_set[s1].tags = NULL;
2488       else
2489         {
2490           for (i = 0; set1[s1].tags != NULL && set1[s1].tags[i] >= 0; i++);
2491           new_tags = tre_mem_alloc(mem, (sizeof(*new_tags)
2492                                          * (i + num_tags + 1)));
2493           if (new_tags == NULL)
2494             return NULL;
2495           for (j = 0; j < i; j++)
2496             new_tags[j] = set1[s1].tags[j];
2497           for (i = 0; i < num_tags; i++)
2498             new_tags[j + i] = tags[i];
2499           new_tags[j + i] = -1;
2500           new_set[s1].tags = new_tags;
2501         }
2502     }
2503
2504   for (s2 = 0; set2[s2].position >= 0; s2++)
2505     {
2506       new_set[s1 + s2].position = set2[s2].position;
2507       new_set[s1 + s2].code_min = set2[s2].code_min;
2508       new_set[s1 + s2].code_max = set2[s2].code_max;
2509       /* XXX - why not | assertions here as well? */
2510       new_set[s1 + s2].assertions = set2[s2].assertions;
2511       new_set[s1 + s2].class = set2[s2].class;
2512       new_set[s1 + s2].neg_classes = set2[s2].neg_classes;
2513       new_set[s1 + s2].backref = set2[s2].backref;
2514       if (set2[s2].tags == NULL)
2515         new_set[s1 + s2].tags = NULL;
2516       else
2517         {
2518           for (i = 0; set2[s2].tags[i] >= 0; i++);
2519           new_tags = tre_mem_alloc(mem, sizeof(*new_tags) * (i + 1));
2520           if (new_tags == NULL)
2521             return NULL;
2522           for (j = 0; j < i; j++)
2523             new_tags[j] = set2[s2].tags[j];
2524           new_tags[j] = -1;
2525           new_set[s1 + s2].tags = new_tags;
2526         }
2527     }
2528   new_set[s1 + s2].position = -1;
2529   return new_set;
2530 }
2531
2532 /* Finds the empty path through `node' which is the one that should be
2533    taken according to POSIX.2 rules, and adds the tags on that path to
2534    `tags'.   `tags' may be NULL.  If `num_tags_seen' is not NULL, it is
2535    set to the number of tags seen on the path. */
2536 static reg_errcode_t
2537 tre_match_empty(tre_stack_t *stack, tre_ast_node_t *node, int *tags,
2538                 int *assertions, int *params, int *num_tags_seen,
2539                 int *params_seen)
2540 {
2541   tre_literal_t *lit;
2542   tre_union_t *uni;
2543   tre_catenation_t *cat;
2544   tre_iteration_t *iter;
2545   int i;
2546   int bottom = tre_stack_num_objects(stack);
2547   reg_errcode_t status = REG_OK;
2548   if (num_tags_seen)
2549     *num_tags_seen = 0;
2550
2551   status = tre_stack_push_voidptr(stack, node);
2552
2553   /* Walk through the tree recursively. */
2554   while (status == REG_OK && tre_stack_num_objects(stack) > bottom)
2555     {
2556       node = tre_stack_pop_voidptr(stack);
2557
2558       switch (node->type)
2559         {
2560         case LITERAL:
2561           lit = (tre_literal_t *)node->obj;
2562           switch (lit->code_min)
2563             {
2564             case TAG:
2565               if (lit->code_max >= 0)
2566                 {
2567                   if (tags != NULL)
2568                     {
2569                       /* Add the tag to `tags'. */
2570                       for (i = 0; tags[i] >= 0; i++)
2571                         if (tags[i] == lit->code_max)
2572                           break;
2573                       if (tags[i] < 0)
2574                         {
2575                           tags[i] = lit->code_max;
2576                           tags[i + 1] = -1;
2577                         }
2578                     }
2579                   if (num_tags_seen)
2580                     (*num_tags_seen)++;
2581                 }
2582               break;
2583             case ASSERTION:
2584               assert(lit->code_max >= 1
2585                      || lit->code_max <= ASSERT_LAST);
2586               if (assertions != NULL)
2587                 *assertions |= lit->code_max;
2588               break;
2589             case EMPTY:
2590               break;
2591             default:
2592               assert(0);
2593               break;
2594             }
2595           break;
2596
2597         case UNION:
2598           /* Subexpressions starting earlier take priority over ones
2599              starting later, so we prefer the left subexpression over the
2600              right subexpression. */
2601           uni = (tre_union_t *)node->obj;
2602           if (uni->left->nullable)
2603             STACK_PUSHX(stack, voidptr, uni->left)
2604           else if (uni->right->nullable)
2605             STACK_PUSHX(stack, voidptr, uni->right)
2606           else
2607             assert(0);
2608           break;
2609
2610         case CATENATION:
2611           /* The path must go through both children. */
2612           cat = (tre_catenation_t *)node->obj;
2613           assert(cat->left->nullable);
2614           assert(cat->right->nullable);
2615           STACK_PUSHX(stack, voidptr, cat->left);
2616           STACK_PUSHX(stack, voidptr, cat->right);
2617           break;
2618
2619         case ITERATION:
2620           /* A match with an empty string is preferred over no match at
2621              all, so we go through the argument if possible. */
2622           iter = (tre_iteration_t *)node->obj;
2623           if (iter->arg->nullable)
2624             STACK_PUSHX(stack, voidptr, iter->arg);
2625           break;
2626
2627         default:
2628           assert(0);
2629           break;
2630         }
2631     }
2632
2633   return status;
2634 }
2635
2636
2637 typedef enum {
2638   NFL_RECURSE,
2639   NFL_POST_UNION,
2640   NFL_POST_CATENATION,
2641   NFL_POST_ITERATION
2642 } tre_nfl_stack_symbol_t;
2643
2644
2645 /* Computes and fills in the fields `nullable', `firstpos', and `lastpos' for
2646    the nodes of the AST `tree'. */
2647 static reg_errcode_t
2648 tre_compute_nfl(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree)
2649 {
2650   int bottom = tre_stack_num_objects(stack);
2651
2652   STACK_PUSHR(stack, voidptr, tree);
2653   STACK_PUSHR(stack, int, NFL_RECURSE);
2654
2655   while (tre_stack_num_objects(stack) > bottom)
2656     {
2657       tre_nfl_stack_symbol_t symbol;
2658       tre_ast_node_t *node;
2659
2660       symbol = (tre_nfl_stack_symbol_t)tre_stack_pop_int(stack);
2661       node = tre_stack_pop_voidptr(stack);
2662       switch (symbol)
2663         {
2664         case NFL_RECURSE:
2665           switch (node->type)
2666             {
2667             case LITERAL:
2668               {
2669                 tre_literal_t *lit = (tre_literal_t *)node->obj;
2670                 if (IS_BACKREF(lit))
2671                   {
2672                     /* Back references: nullable = false, firstpos = {i},
2673                        lastpos = {i}. */
2674                     node->nullable = 0;
2675                     node->firstpos = tre_set_one(mem, lit->position, 0,
2676                                              TRE_CHAR_MAX, 0, NULL, -1);
2677                     if (!node->firstpos)
2678                       return REG_ESPACE;
2679                     node->lastpos = tre_set_one(mem, lit->position, 0,
2680                                                 TRE_CHAR_MAX, 0, NULL,
2681                                                 (int)lit->code_max);
2682                     if (!node->lastpos)
2683                       return REG_ESPACE;
2684                   }
2685                 else if (lit->code_min < 0)
2686                   {
2687                     /* Tags, empty strings, params, and zero width assertions:
2688                        nullable = true, firstpos = {}, and lastpos = {}. */
2689                     node->nullable = 1;
2690                     node->firstpos = tre_set_empty(mem);
2691                     if (!node->firstpos)
2692                       return REG_ESPACE;
2693                     node->lastpos = tre_set_empty(mem);
2694                     if (!node->lastpos)
2695                       return REG_ESPACE;
2696                   }
2697                 else
2698                   {
2699                     /* Literal at position i: nullable = false, firstpos = {i},
2700                        lastpos = {i}. */
2701                     node->nullable = 0;
2702                     node->firstpos =
2703                       tre_set_one(mem, lit->position, (int)lit->code_min,
2704                                   (int)lit->code_max, 0, NULL, -1);
2705                     if (!node->firstpos)
2706                       return REG_ESPACE;
2707                     node->lastpos = tre_set_one(mem, lit->position,
2708                                                 (int)lit->code_min,
2709                                                 (int)lit->code_max,
2710                                                 lit->u.class, lit->neg_classes,
2711                                                 -1);
2712                     if (!node->lastpos)
2713                       return REG_ESPACE;
2714                   }
2715                 break;
2716               }
2717
2718             case UNION:
2719               /* Compute the attributes for the two subtrees, and after that
2720                  for this node. */
2721               STACK_PUSHR(stack, voidptr, node);
2722               STACK_PUSHR(stack, int, NFL_POST_UNION);
2723               STACK_PUSHR(stack, voidptr, ((tre_union_t *)node->obj)->right);
2724               STACK_PUSHR(stack, int, NFL_RECURSE);
2725               STACK_PUSHR(stack, voidptr, ((tre_union_t *)node->obj)->left);
2726               STACK_PUSHR(stack, int, NFL_RECURSE);
2727               break;
2728
2729             case CATENATION:
2730               /* Compute the attributes for the two subtrees, and after that
2731                  for this node. */
2732               STACK_PUSHR(stack, voidptr, node);
2733               STACK_PUSHR(stack, int, NFL_POST_CATENATION);
2734               STACK_PUSHR(stack, voidptr, ((tre_catenation_t *)node->obj)->right);
2735               STACK_PUSHR(stack, int, NFL_RECURSE);
2736               STACK_PUSHR(stack, voidptr, ((tre_catenation_t *)node->obj)->left);
2737               STACK_PUSHR(stack, int, NFL_RECURSE);
2738               break;
2739
2740             case ITERATION:
2741               /* Compute the attributes for the subtree, and after that for
2742                  this node. */
2743               STACK_PUSHR(stack, voidptr, node);
2744               STACK_PUSHR(stack, int, NFL_POST_ITERATION);
2745               STACK_PUSHR(stack, voidptr, ((tre_iteration_t *)node->obj)->arg);
2746               STACK_PUSHR(stack, int, NFL_RECURSE);
2747               break;
2748             }
2749           break; /* end case: NFL_RECURSE */
2750
2751         case NFL_POST_UNION:
2752           {
2753             tre_union_t *uni = (tre_union_t *)node->obj;
2754             node->nullable = uni->left->nullable || uni->right->nullable;
2755             node->firstpos = tre_set_union(mem, uni->left->firstpos,
2756                                            uni->right->firstpos, NULL, 0);
2757             if (!node->firstpos)
2758               return REG_ESPACE;
2759             node->lastpos = tre_set_union(mem, uni->left->lastpos,
2760                                           uni->right->lastpos, NULL, 0);
2761             if (!node->lastpos)
2762               return REG_ESPACE;
2763             break;
2764           }
2765
2766         case NFL_POST_ITERATION:
2767           {
2768             tre_iteration_t *iter = (tre_iteration_t *)node->obj;
2769
2770             if (iter->min == 0 || iter->arg->nullable)
2771               node->nullable = 1;
2772             else
2773               node->nullable = 0;
2774             node->firstpos = iter->arg->firstpos;
2775             node->lastpos = iter->arg->lastpos;
2776             break;
2777           }
2778
2779         case NFL_POST_CATENATION:
2780           {
2781             int num_tags, *tags, assertions, params_seen;
2782             int *params;
2783             reg_errcode_t status;
2784             tre_catenation_t *cat = node->obj;
2785             node->nullable = cat->left->nullable && cat->right->nullable;
2786
2787             /* Compute firstpos. */
2788             if (cat->left->nullable)
2789               {
2790                 /* The left side matches the empty string.  Make a first pass
2791                    with tre_match_empty() to get the number of tags and
2792                    parameters. */
2793                 status = tre_match_empty(stack, cat->left,
2794                                          NULL, NULL, NULL, &num_tags,
2795                                          &params_seen);
2796                 if (status != REG_OK)
2797                   return status;
2798                 /* Allocate arrays for the tags and parameters. */
2799                 tags = xmalloc(sizeof(*tags) * (num_tags + 1));
2800                 if (!tags)
2801                   return REG_ESPACE;
2802                 tags[0] = -1;
2803                 assertions = 0;
2804                 /* Second pass with tre_mach_empty() to get the list of
2805                    tags and parameters. */
2806                 status = tre_match_empty(stack, cat->left, tags,
2807                                          &assertions, params, NULL, NULL);
2808                 if (status != REG_OK)
2809                   {
2810                     xfree(tags);
2811                     return status;
2812                   }
2813                 node->firstpos =
2814                   tre_set_union(mem, cat->right->firstpos, cat->left->firstpos,
2815                                 tags, assertions);
2816                 xfree(tags);
2817                 if (!node->firstpos)
2818                   return REG_ESPACE;
2819               }
2820             else
2821               {
2822                 node->firstpos = cat->left->firstpos;
2823               }
2824
2825             /* Compute lastpos. */
2826             if (cat->right->nullable)
2827               {
2828                 /* The right side matches the empty string.  Make a first pass
2829                    with tre_match_empty() to get the number of tags and
2830                    parameters. */
2831                 status = tre_match_empty(stack, cat->right,
2832                                          NULL, NULL, NULL, &num_tags,
2833                                          &params_seen);
2834                 if (status != REG_OK)
2835                   return status;
2836                 /* Allocate arrays for the tags and parameters. */
2837                 tags = xmalloc(sizeof(int) * (num_tags + 1));
2838                 if (!tags)
2839                   return REG_ESPACE;
2840                 tags[0] = -1;
2841                 assertions = 0;
2842                 /* Second pass with tre_mach_empty() to get the list of
2843                    tags and parameters. */
2844                 status = tre_match_empty(stack, cat->right, tags,
2845                                          &assertions, params, NULL, NULL);
2846                 if (status != REG_OK)
2847                   {
2848                     xfree(tags);
2849                     return status;
2850                   }
2851                 node->lastpos =
2852                   tre_set_union(mem, cat->left->lastpos, cat->right->lastpos,
2853                                 tags, assertions);
2854                 xfree(tags);
2855                 if (!node->lastpos)
2856                   return REG_ESPACE;
2857               }
2858             else
2859               {
2860                 node->lastpos = cat->right->lastpos;
2861               }
2862             break;
2863           }
2864
2865         default:
2866           assert(0);
2867           break;
2868         }
2869     }
2870
2871   return REG_OK;
2872 }
2873
2874
2875 /* Adds a transition from each position in `p1' to each position in `p2'. */
2876 static reg_errcode_t
2877 tre_make_trans(tre_pos_and_tags_t *p1, tre_pos_and_tags_t *p2,
2878                tre_tnfa_transition_t *transitions,
2879                int *counts, int *offs)
2880 {
2881   tre_pos_and_tags_t *orig_p2 = p2;
2882   tre_tnfa_transition_t *trans;
2883   int i, j, k, l, dup, prev_p2_pos;
2884
2885   if (transitions != NULL)
2886     while (p1->position >= 0)
2887       {
2888         p2 = orig_p2;
2889         prev_p2_pos = -1;
2890         while (p2->position >= 0)
2891           {
2892             /* Optimization: if this position was already handled, skip it. */
2893             if (p2->position == prev_p2_pos)
2894               {
2895                 p2++;
2896                 continue;
2897               }
2898             prev_p2_pos = p2->position;
2899             /* Set `trans' to point to the next unused transition from
2900                position `p1->position'. */
2901             trans = transitions + offs[p1->position];
2902             while (trans->state != NULL)
2903               {
2904 #if 0
2905                 /* If we find a previous transition from `p1->position' to
2906                    `p2->position', it is overwritten.  This can happen only
2907                    if there are nested loops in the regexp, like in "((a)*)*".
2908                    In POSIX.2 repetition using the outer loop is always
2909                    preferred over using the inner loop.  Therefore the
2910                    transition for the inner loop is useless and can be thrown
2911                    away. */
2912                 /* XXX - The same position is used for all nodes in a bracket
2913                    expression, so this optimization cannot be used (it will
2914                    break bracket expressions) unless I figure out a way to
2915                    detect it here. */
2916                 if (trans->state_id == p2->position)
2917                   {
2918                     break;
2919                   }
2920 #endif
2921                 trans++;
2922               }
2923
2924             if (trans->state == NULL)
2925               (trans + 1)->state = NULL;
2926             /* Use the character ranges, assertions, etc. from `p1' for
2927                the transition from `p1' to `p2'. */
2928             trans->code_min = p1->code_min;
2929             trans->code_max = p1->code_max;
2930             trans->state = transitions + offs[p2->position];
2931             trans->state_id = p2->position;
2932             trans->assertions = p1->assertions | p2->assertions
2933               | (p1->class ? ASSERT_CHAR_CLASS : 0)
2934               | (p1->neg_classes != NULL ? ASSERT_CHAR_CLASS_NEG : 0);
2935             if (p1->backref >= 0)
2936               {
2937                 assert((trans->assertions & ASSERT_CHAR_CLASS) == 0);
2938                 assert(p2->backref < 0);
2939                 trans->u.backref = p1->backref;
2940                 trans->assertions |= ASSERT_BACKREF;
2941               }
2942             else
2943               trans->u.class = p1->class;
2944             if (p1->neg_classes != NULL)
2945               {
2946                 for (i = 0; p1->neg_classes[i] != (tre_ctype_t)0; i++);
2947                 trans->neg_classes =
2948                   xmalloc(sizeof(*trans->neg_classes) * (i + 1));
2949                 if (trans->neg_classes == NULL)
2950                   return REG_ESPACE;
2951                 for (i = 0; p1->neg_classes[i] != (tre_ctype_t)0; i++)
2952                   trans->neg_classes[i] = p1->neg_classes[i];
2953                 trans->neg_classes[i] = (tre_ctype_t)0;
2954               }
2955             else
2956               trans->neg_classes = NULL;
2957
2958             /* Find out how many tags this transition has. */
2959             i = 0;
2960             if (p1->tags != NULL)
2961               while(p1->tags[i] >= 0)
2962                 i++;
2963             j = 0;
2964             if (p2->tags != NULL)
2965               while(p2->tags[j] >= 0)
2966                 j++;
2967
2968             /* If we are overwriting a transition, free the old tag array. */
2969             if (trans->tags != NULL)
2970               xfree(trans->tags);
2971             trans->tags = NULL;
2972
2973             /* If there were any tags, allocate an array and fill it. */
2974             if (i + j > 0)
2975               {
2976                 trans->tags = xmalloc(sizeof(*trans->tags) * (i + j + 1));
2977                 if (!trans->tags)
2978                   return REG_ESPACE;
2979                 i = 0;
2980                 if (p1->tags != NULL)
2981                   while(p1->tags[i] >= 0)
2982                     {
2983                       trans->tags[i] = p1->tags[i];
2984                       i++;
2985                     }
2986                 l = i;
2987                 j = 0;
2988                 if (p2->tags != NULL)
2989                   while (p2->tags[j] >= 0)
2990                     {
2991                       /* Don't add duplicates. */
2992                       dup = 0;
2993                       for (k = 0; k < i; k++)
2994                         if (trans->tags[k] == p2->tags[j])
2995                           {
2996                             dup = 1;
2997                             break;
2998                           }
2999                       if (!dup)
3000                         trans->tags[l++] = p2->tags[j];
3001                       j++;
3002                     }
3003                 trans->tags[l] = -1;
3004               }
3005
3006             p2++;
3007           }
3008         p1++;
3009       }
3010   else
3011     /* Compute a maximum limit for the number of transitions leaving
3012        from each state. */
3013     while (p1->position >= 0)
3014       {
3015         p2 = orig_p2;
3016         while (p2->position >= 0)
3017           {
3018             counts[p1->position]++;
3019             p2++;
3020           }
3021         p1++;
3022       }
3023   return REG_OK;
3024 }
3025
3026 /* Converts the syntax tree to a TNFA.  All the transitions in the TNFA are
3027    labelled with one character range (there are no transitions on empty
3028    strings).  The TNFA takes O(n^2) space in the worst case, `n' is size of
3029    the regexp. */
3030 static reg_errcode_t
3031 tre_ast_to_tnfa(tre_ast_node_t *node, tre_tnfa_transition_t *transitions,
3032                 int *counts, int *offs)
3033 {
3034   tre_union_t *uni;
3035   tre_catenation_t *cat;
3036   tre_iteration_t *iter;
3037   reg_errcode_t errcode = REG_OK;
3038
3039   /* XXX - recurse using a stack!. */
3040   switch (node->type)
3041     {
3042     case LITERAL:
3043       break;
3044     case UNION:
3045       uni = (tre_union_t *)node->obj;
3046       errcode = tre_ast_to_tnfa(uni->left, transitions, counts, offs);
3047       if (errcode != REG_OK)
3048         return errcode;
3049       errcode = tre_ast_to_tnfa(uni->right, transitions, counts, offs);
3050       break;
3051
3052     case CATENATION:
3053       cat = (tre_catenation_t *)node->obj;
3054       /* Add a transition from each position in cat->left->lastpos
3055          to each position in cat->right->firstpos. */
3056       errcode = tre_make_trans(cat->left->lastpos, cat->right->firstpos,
3057                                transitions, counts, offs);
3058       if (errcode != REG_OK)
3059         return errcode;
3060       errcode = tre_ast_to_tnfa(cat->left, transitions, counts, offs);
3061       if (errcode != REG_OK)
3062         return errcode;
3063       errcode = tre_ast_to_tnfa(cat->right, transitions, counts, offs);
3064       break;
3065
3066     case ITERATION:
3067       iter = (tre_iteration_t *)node->obj;
3068       assert(iter->max == -1 || iter->max == 1);
3069
3070       if (iter->max == -1)
3071         {
3072           assert(iter->min == 0 || iter->min == 1);
3073           /* Add a transition from each last position in the iterated
3074              expression to each first position. */
3075           errcode = tre_make_trans(iter->arg->lastpos, iter->arg->firstpos,
3076                                    transitions, counts, offs);
3077           if (errcode != REG_OK)
3078             return errcode;
3079         }
3080       errcode = tre_ast_to_tnfa(iter->arg, transitions, counts, offs);
3081       break;
3082     }
3083   return errcode;
3084 }
3085
3086
3087 #define ERROR_EXIT(err)           \
3088   do                              \
3089     {                             \
3090       errcode = err;              \
3091       if (/*CONSTCOND*/1)         \
3092         goto error_exit;          \
3093     }                             \
3094  while (/*CONSTCOND*/0)
3095
3096
3097 int
3098 regcomp(regex_t *preg, const char *regex, int cflags)
3099 {
3100   tre_stack_t *stack;
3101   tre_ast_node_t *tree, *tmp_ast_l, *tmp_ast_r;
3102   tre_pos_and_tags_t *p;
3103   int *counts = NULL, *offs = NULL;
3104   int i, add = 0;
3105   tre_tnfa_transition_t *transitions, *initial;
3106   tre_tnfa_t *tnfa = NULL;
3107   tre_submatch_data_t *submatch_data;
3108   tre_tag_direction_t *tag_directions = NULL;
3109   reg_errcode_t errcode;
3110   tre_mem_t mem;
3111
3112   /* Parse context. */
3113   tre_parse_ctx_t parse_ctx;
3114
3115   /* Allocate a stack used throughout the compilation process for various
3116      purposes. */
3117   stack = tre_stack_new(512, 10240, 128);
3118   if (!stack)
3119     return REG_ESPACE;
3120   /* Allocate a fast memory allocator. */
3121   mem = tre_mem_new();
3122   if (!mem)
3123     {
3124       tre_stack_destroy(stack);
3125       return REG_ESPACE;
3126     }
3127
3128   /* Parse the regexp. */
3129   memset(&parse_ctx, 0, sizeof(parse_ctx));
3130   parse_ctx.mem = mem;
3131   parse_ctx.stack = stack;
3132   parse_ctx.re = regex;
3133   parse_ctx.cflags = cflags;
3134   parse_ctx.max_backref = -1;
3135   errcode = tre_parse(&parse_ctx);
3136   if (errcode != REG_OK)
3137     ERROR_EXIT(errcode);
3138   preg->re_nsub = parse_ctx.submatch_id - 1;
3139   tree = parse_ctx.result;
3140
3141   /* Back references and approximate matching cannot currently be used
3142      in the same regexp. */
3143   if (parse_ctx.max_backref >= 0 && parse_ctx.have_approx)
3144     ERROR_EXIT(REG_BADPAT);
3145
3146 #ifdef TRE_DEBUG
3147   tre_ast_print(tree);
3148 #endif /* TRE_DEBUG */
3149
3150   /* Referring to nonexistent subexpressions is illegal. */
3151   if (parse_ctx.max_backref > (int)preg->re_nsub)
3152     ERROR_EXIT(REG_ESUBREG);
3153
3154   /* Allocate the TNFA struct. */
3155   tnfa = xcalloc(1, sizeof(tre_tnfa_t));
3156   if (tnfa == NULL)
3157     ERROR_EXIT(REG_ESPACE);
3158   tnfa->have_backrefs = parse_ctx.max_backref >= 0;
3159   tnfa->have_approx = parse_ctx.have_approx;
3160   tnfa->num_submatches = parse_ctx.submatch_id;
3161
3162   /* Set up tags for submatch addressing.  If REG_NOSUB is set and the
3163      regexp does not have back references, this can be skipped. */
3164   if (tnfa->have_backrefs || !(cflags & REG_NOSUB))
3165     {
3166
3167       /* Figure out how many tags we will need. */
3168       errcode = tre_add_tags(NULL, stack, tree, tnfa);
3169       if (errcode != REG_OK)
3170         ERROR_EXIT(errcode);
3171
3172       if (tnfa->num_tags > 0)
3173         {
3174           tag_directions = xmalloc(sizeof(*tag_directions)
3175                                    * (tnfa->num_tags + 1));
3176           if (tag_directions == NULL)
3177             ERROR_EXIT(REG_ESPACE);
3178           tnfa->tag_directions = tag_directions;
3179           memset(tag_directions, -1,
3180                  sizeof(*tag_directions) * (tnfa->num_tags + 1));
3181         }
3182       tnfa->minimal_tags = xcalloc((unsigned)tnfa->num_tags * 2 + 1,
3183                                    sizeof(tnfa->minimal_tags));
3184       if (tnfa->minimal_tags == NULL)
3185         ERROR_EXIT(REG_ESPACE);
3186
3187       submatch_data = xcalloc((unsigned)parse_ctx.submatch_id,
3188                               sizeof(*submatch_data));
3189       if (submatch_data == NULL)
3190         ERROR_EXIT(REG_ESPACE);
3191       tnfa->submatch_data = submatch_data;
3192
3193       errcode = tre_add_tags(mem, stack, tree, tnfa);
3194       if (errcode != REG_OK)
3195         ERROR_EXIT(errcode);
3196
3197     }
3198
3199   /* Expand iteration nodes. */
3200   errcode = tre_expand_ast(mem, stack, tree, &parse_ctx.position,
3201                            tag_directions, &tnfa->params_depth);
3202   if (errcode != REG_OK)
3203     ERROR_EXIT(errcode);
3204
3205   /* Add a dummy node for the final state.
3206      XXX - For certain patterns this dummy node can be optimized away,
3207            for example "a*" or "ab*".   Figure out a simple way to detect
3208            this possibility. */
3209   tmp_ast_l = tree;
3210   tmp_ast_r = tre_ast_new_literal(mem, 0, 0, parse_ctx.position++);
3211   if (tmp_ast_r == NULL)
3212     ERROR_EXIT(REG_ESPACE);
3213
3214   tree = tre_ast_new_catenation(mem, tmp_ast_l, tmp_ast_r);
3215   if (tree == NULL)
3216     ERROR_EXIT(REG_ESPACE);
3217
3218   errcode = tre_compute_nfl(mem, stack, tree);
3219   if (errcode != REG_OK)
3220     ERROR_EXIT(errcode);
3221
3222   counts = xmalloc(sizeof(int) * parse_ctx.position);
3223   if (counts == NULL)
3224     ERROR_EXIT(REG_ESPACE);
3225
3226   offs = xmalloc(sizeof(int) * parse_ctx.position);
3227   if (offs == NULL)
3228     ERROR_EXIT(REG_ESPACE);
3229
3230   for (i = 0; i < parse_ctx.position; i++)
3231     counts[i] = 0;
3232   tre_ast_to_tnfa(tree, NULL, counts, NULL);
3233
3234   add = 0;
3235   for (i = 0; i < parse_ctx.position; i++)
3236     {
3237       offs[i] = add;
3238       add += counts[i] + 1;
3239       counts[i] = 0;
3240     }
3241   transitions = xcalloc((unsigned)add + 1, sizeof(*transitions));
3242   if (transitions == NULL)
3243     ERROR_EXIT(REG_ESPACE);
3244   tnfa->transitions = transitions;
3245   tnfa->num_transitions = add;
3246
3247   errcode = tre_ast_to_tnfa(tree, transitions, counts, offs);
3248   if (errcode != REG_OK)
3249     ERROR_EXIT(errcode);
3250
3251   tnfa->firstpos_chars = NULL;
3252
3253   p = tree->firstpos;
3254   i = 0;
3255   while (p->position >= 0)
3256     {
3257       i++;
3258       p++;
3259     }
3260
3261   initial = xcalloc((unsigned)i + 1, sizeof(tre_tnfa_transition_t));
3262   if (initial == NULL)
3263     ERROR_EXIT(REG_ESPACE);
3264   tnfa->initial = initial;
3265
3266   i = 0;
3267   for (p = tree->firstpos; p->position >= 0; p++)
3268     {
3269       initial[i].state = transitions + offs[p->position];
3270       initial[i].state_id = p->position;
3271       initial[i].tags = NULL;
3272       /* Copy the arrays p->tags, and p->params, they are allocated
3273          from a tre_mem object. */
3274       if (p->tags)
3275         {
3276           int j;
3277           for (j = 0; p->tags[j] >= 0; j++);
3278           initial[i].tags = xmalloc(sizeof(*p->tags) * (j + 1));
3279           if (!initial[i].tags)
3280             ERROR_EXIT(REG_ESPACE);
3281           memcpy(initial[i].tags, p->tags, sizeof(*p->tags) * (j + 1));
3282         }
3283       initial[i].assertions = p->assertions;
3284       i++;
3285     }
3286   initial[i].state = NULL;
3287
3288   tnfa->num_transitions = add;
3289   tnfa->final = transitions + offs[tree->lastpos[0].position];
3290   tnfa->num_states = parse_ctx.position;
3291   tnfa->cflags = cflags;
3292
3293   tre_mem_destroy(mem);
3294   tre_stack_destroy(stack);
3295   xfree(counts);
3296   xfree(offs);
3297
3298   preg->TRE_REGEX_T_FIELD = (void *)tnfa;
3299   return REG_OK;
3300
3301  error_exit:
3302   /* Free everything that was allocated and return the error code. */
3303   tre_mem_destroy(mem);
3304   if (stack != NULL)
3305     tre_stack_destroy(stack);
3306   if (counts != NULL)
3307     xfree(counts);
3308   if (offs != NULL)
3309     xfree(offs);
3310   preg->TRE_REGEX_T_FIELD = (void *)tnfa;
3311   regfree(preg);
3312   return errcode;
3313 }
3314
3315
3316
3317
3318 void
3319 regfree(regex_t *preg)
3320 {
3321   tre_tnfa_t *tnfa;
3322   unsigned int i;
3323   tre_tnfa_transition_t *trans;
3324
3325   tnfa = (void *)preg->TRE_REGEX_T_FIELD;
3326   if (!tnfa)
3327     return;
3328
3329   for (i = 0; i < tnfa->num_transitions; i++)
3330     if (tnfa->transitions[i].state)
3331       {
3332         if (tnfa->transitions[i].tags)
3333           xfree(tnfa->transitions[i].tags);
3334         if (tnfa->transitions[i].neg_classes)
3335           xfree(tnfa->transitions[i].neg_classes);
3336       }
3337   if (tnfa->transitions)
3338     xfree(tnfa->transitions);
3339
3340   if (tnfa->initial)
3341     {
3342       for (trans = tnfa->initial; trans->state; trans++)
3343         {
3344           if (trans->tags)
3345             xfree(trans->tags);
3346         }
3347       xfree(tnfa->initial);
3348     }
3349
3350   if (tnfa->submatch_data)
3351     {
3352       for (i = 0; i < tnfa->num_submatches; i++)
3353         if (tnfa->submatch_data[i].parents)
3354           xfree(tnfa->submatch_data[i].parents);
3355       xfree(tnfa->submatch_data);
3356     }
3357
3358   if (tnfa->tag_directions)
3359     xfree(tnfa->tag_directions);
3360   if (tnfa->firstpos_chars)
3361     xfree(tnfa->firstpos_chars);
3362   if (tnfa->minimal_tags)
3363     xfree(tnfa->minimal_tags);
3364   xfree(tnfa);
3365 }