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