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