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

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