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

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