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                         /* reject repetitions after empty expression in BRE */
 842                         if (!ere)
 843                                 return REG_BADRPT;
 844                 case '|':
 845                         /* extension: treat \| as alternation in BRE */
 846                         if (!ere) {
 847                                 node = tre_ast_new_literal(ctx->mem, EMPTY, -1, -1);
 848                                 s--;
 849                                 goto end;
 850                         }
 851                         /* fallthrough */
 852                 default:
 853                         if (!ere && (unsigned)*s-'1' < 9) {
 854                                 /* back reference */
 855                                 int val = *s - '0';
 856                                 node = tre_ast_new_literal(ctx->mem, BACKREF, val, ctx->position++);
 857                                 ctx->max_backref = MAX(val, ctx->max_backref);
 858                         } else {
 859                                 /* extension: accept unknown escaped char
 860                                    as a literal */
 861                                 goto parse_literal;
 862                         }
 863                 }
 864                 s++;
 865                 break;
 866         case '.':
 867                 if (ctx->cflags & REG_NEWLINE) {
 868                         tre_ast_node_t *tmp1, *tmp2;
 869                         tmp1 = tre_ast_new_literal(ctx->mem, 0, '\n'-1, ctx->position++);
 870                         tmp2 = tre_ast_new_literal(ctx->mem, '\n'+1, TRE_CHAR_MAX, ctx->position++);
 871                         if (tmp1 && tmp2)
 872                                 node = tre_ast_new_union(ctx->mem, tmp1, tmp2);
 873                         else
 874                                 node = 0;
 875                 } else {
 876                         node = tre_ast_new_literal(ctx->mem, 0, TRE_CHAR_MAX, ctx->position++);
 877                 }
 878                 s++;
 879                 break;
 880         case '^':
 881                 /* '^' has a special meaning everywhere in EREs, and at beginning of BRE. */
 882                 if (!ere && s != ctx->re)
 883                         goto parse_literal;
 884                 node = tre_ast_new_literal(ctx->mem, ASSERTION, ASSERT_AT_BOL, -1);
 885                 s++;
 886                 break;
 887         case '$':
 888                 /* '$' is special everywhere in EREs, and in the end of the string in BREs. */
 889                 if (!ere && s[1])
 890                         goto parse_literal;
 891                 node = tre_ast_new_literal(ctx->mem, ASSERTION, ASSERT_AT_EOL, -1);
 892                 s++;
 893                 break;
 894         case '*':
 895                 return REG_BADPAT;
 896         case '{':
 897         case '+':
 898         case '?':
 899                 /* reject repetitions after empty expression in ERE */
 900                 if (ere)
 901                         return REG_BADRPT;
 902         case '|':
 903                 if (!ere)
 904                         goto parse_literal;
 905         case 0:
 906                 node = tre_ast_new_literal(ctx->mem, EMPTY, -1, -1);
 907                 break;
 908         default:
 909 parse_literal:
 910                 len = mbtowc(&wc, s, -1);
 911                 if (len < 0)
 912                         return REG_BADPAT;
 913                 if (ctx->cflags & REG_ICASE && (tre_isupper(wc) || tre_islower(wc))) {
 914                         tre_ast_node_t *tmp1, *tmp2;
 915                         /* multiple opposite case characters are not supported */
 916                         tmp1 = tre_ast_new_literal(ctx->mem, tre_toupper(wc), tre_toupper(wc), ctx->position);
 917                         tmp2 = tre_ast_new_literal(ctx->mem, tre_tolower(wc), tre_tolower(wc), ctx->position);
 918                         if (tmp1 && tmp2)
 919                                 node = tre_ast_new_union(ctx->mem, tmp1, tmp2);
 920                         else
 921                                 node = 0;
 922                 } else {
 923                         node = tre_ast_new_literal(ctx->mem, wc, wc, ctx->position);
 924                 }
 925                 ctx->position++;
 926                 s += len;
 927                 break;
 928         }
 929 end:
 930         if (!node)
 931                 return REG_ESPACE;
 932         ctx->n = node;
 933         ctx->s = s;
 934         return REG_OK;
 935 }
 936
 937 #define PUSHPTR(err, s, v) do { \
 938         if ((err = tre_stack_push_voidptr(s, v)) != REG_OK) \
 939                 return err; \
 940 } while(0)
 941
 942 #define PUSHINT(err, s, v) do { \
 943         if ((err = tre_stack_push_int(s, v)) != REG_OK) \
 944                 return err; \
 945 } while(0)
 946
 947 static reg_errcode_t tre_parse(tre_parse_ctx_t *ctx)
 948 {
 949         tre_ast_node_t *nbranch=0, *nunion=0;
 950         int ere = ctx->cflags & REG_EXTENDED;
 951         const char *s = ctx->re;
 952         int subid = 0;
 953         int depth = 0;
 954         reg_errcode_t err;
 955         tre_stack_t *stack = ctx->stack;
 956
 957         PUSHINT(err, stack, subid++);
 958         for (;;) {
 959                 if ((!ere && *s == '\\' && s[1] == '(') ||
 960                     (ere && *s == '(')) {
 961                         PUSHPTR(err, stack, nunion);
 962                         PUSHPTR(err, stack, nbranch);
 963                         PUSHINT(err, stack, subid++);
 964                         s++;
 965                         if (!ere)
 966                                 s++;
 967                         depth++;
 968                         nbranch = nunion = 0;
 969                         continue;
 970                 }
 971                 if ((!ere && *s == '\\' && s[1] == ')') ||
 972                     (ere && *s == ')' && depth)) {
 973                         ctx->n = tre_ast_new_literal(ctx->mem, EMPTY, -1, -1);
 974                         if (!ctx->n)
 975                                 return REG_ESPACE;
 976                 } else {
 977                         err = parse_atom(ctx, s);
 978                         if (err != REG_OK)
 979                                 return err;
 980                         s = ctx->s;
 981                 }
 982
 983         parse_iter:
 984                 /* extension: repetitions are rejected after an empty node
 985                    eg. (+), |*, {2}, but assertions are not treated as empty
 986                    so ^* or $? are accepted currently. */
 987                 switch (*s) {
 988                 case '+':
 989                 case '?':
 990                         if (!ere)
 991                                 break;
 992                         /* fallthrough */
 993                 case '*':;
 994                         int min=0, max=-1;
 995                         if (*s == '+')
 996                                 min = 1;
 997                         if (*s == '?')
 998                                 max = 1;
 999                         s++;
1000                         ctx->n = tre_ast_new_iter(ctx->mem, ctx->n, min, max, 0);
1001                         if (!ctx->n)
1002                                 return REG_ESPACE;
1003                         /* extension: multiple consecutive *+?{,} is unspecified,
1004                            but (a+)+ has to be supported so accepting a++ makes
1005                            sense, note however that the RE_DUP_MAX limit can be
1006                            circumvented: (a{255}){255} uses a lot of memory.. */
1007                         goto parse_iter;
1008                 case '\\':
1009                         if (ere || s[1] != '{')
1010                                 break;
1011                         s++;
1012                         goto parse_brace;
1013                 case '{':
1014                         if (!ere)
1015                                 break;
1016                 parse_brace:
1017                         err = parse_dup(ctx, s+1);
1018                         if (err != REG_OK)
1019                                 return err;
1020                         s = ctx->s;
1021                         goto parse_iter;
1022                 }
1023
1024                 nbranch = tre_ast_new_catenation(ctx->mem, nbranch, ctx->n);
1025                 if ((ere && *s == '|') ||
1026                     (ere && *s == ')' && depth) ||
1027                     (!ere && *s == '\\' && s[1] == ')') ||
1028                     /* extension: treat \| as alternation in BRE */
1029                     (!ere && *s == '\\' && s[1] == '|') ||
1030                     !*s) {
1031                         /* extension: empty branch is unspecified (), (|a), (a|)
1032                            here they are not rejected but match on empty string */
1033                         int c = *s;
1034                         nunion = tre_ast_new_union(ctx->mem, nunion, nbranch);
1035                         nbranch = 0;
1036
1037                         if (c == '\\' && s[1] == '|') {
1038                                 s+=2;
1039                         } else if (c == '|') {
1040                                 s++;
1041                         } else {
1042                                 if (c == '\\') {
1043                                         if (!depth) return REG_EPAREN;
1044                                         s+=2;
1045                                 } else if (c == ')')
1046                                         s++;
1047                                 depth--;
1048                                 err = marksub(ctx, nunion, tre_stack_pop_int(stack));
1049                                 if (err != REG_OK)
1050                                         return err;
1051                                 if (!c && depth<0) {
1052                                         ctx->submatch_id = subid;
1053                                         return REG_OK;
1054                                 }
1055                                 if (!c || depth<0)
1056                                         return REG_EPAREN;
1057                                 nbranch = tre_stack_pop_voidptr(stack);
1058                                 nunion = tre_stack_pop_voidptr(stack);
1059                                 goto parse_iter;
1060                         }
1061                 }
1062         }
1063 }
1064
1065
1066 /***********************************************************************
1067  from tre-compile.c
1068 ***********************************************************************/
1069
1070
1071 /*
1072   TODO:
1073    - Fix tre_ast_to_tnfa() to recurse using a stack instead of recursive
1074      function calls.
1075 */
1076
1077 /*
1078   Algorithms to setup tags so that submatch addressing can be done.
1079 */
1080
1081
1082 /* Inserts a catenation node to the root of the tree given in `node'.
1083    As the left child a new tag with number `tag_id' to `node' is added,
1084    and the right child is the old root. */
1085 static reg_errcode_t
1086 tre_add_tag_left(tre_mem_t mem, tre_ast_node_t *node, int tag_id)
1087 {
1088   tre_catenation_t *c;
1089
1090   c = tre_mem_alloc(mem, sizeof(*c));
1091   if (c == NULL)
1092     return REG_ESPACE;
1093   c->left = tre_ast_new_literal(mem, TAG, tag_id, -1);
1094   if (c->left == NULL)
1095     return REG_ESPACE;
1096   c->right = tre_mem_alloc(mem, sizeof(tre_ast_node_t));
1097   if (c->right == NULL)
1098     return REG_ESPACE;
1099
1100   c->right->obj = node->obj;
1101   c->right->type = node->type;
1102   c->right->nullable = -1;
1103   c->right->submatch_id = -1;
1104   c->right->firstpos = NULL;
1105   c->right->lastpos = NULL;
1106   c->right->num_tags = 0;
1107   node->obj = c;
1108   node->type = CATENATION;
1109   return REG_OK;
1110 }
1111
1112 /* Inserts a catenation node to the root of the tree given in `node'.
1113    As the right child a new tag with number `tag_id' to `node' is added,
1114    and the left child is the old root. */
1115 static reg_errcode_t
1116 tre_add_tag_right(tre_mem_t mem, tre_ast_node_t *node, int tag_id)
1117 {
1118   tre_catenation_t *c;
1119
1120   c = tre_mem_alloc(mem, sizeof(*c));
1121   if (c == NULL)
1122     return REG_ESPACE;
1123   c->right = tre_ast_new_literal(mem, TAG, tag_id, -1);
1124   if (c->right == NULL)
1125     return REG_ESPACE;
1126   c->left = tre_mem_alloc(mem, sizeof(tre_ast_node_t));
1127   if (c->left == NULL)
1128     return REG_ESPACE;
1129
1130   c->left->obj = node->obj;
1131   c->left->type = node->type;
1132   c->left->nullable = -1;
1133   c->left->submatch_id = -1;
1134   c->left->firstpos = NULL;
1135   c->left->lastpos = NULL;
1136   c->left->num_tags = 0;
1137   node->obj = c;
1138   node->type = CATENATION;
1139   return REG_OK;
1140 }
1141
1142 typedef enum {
1143   ADDTAGS_RECURSE,
1144   ADDTAGS_AFTER_ITERATION,
1145   ADDTAGS_AFTER_UNION_LEFT,
1146   ADDTAGS_AFTER_UNION_RIGHT,
1147   ADDTAGS_AFTER_CAT_LEFT,
1148   ADDTAGS_AFTER_CAT_RIGHT,
1149   ADDTAGS_SET_SUBMATCH_END
1150 } tre_addtags_symbol_t;
1151
1152
1153 typedef struct {
1154   int tag;
1155   int next_tag;
1156 } tre_tag_states_t;
1157
1158
1159 /* Go through `regset' and set submatch data for submatches that are
1160    using this tag. */
1161 static void
1162 tre_purge_regset(int *regset, tre_tnfa_t *tnfa, int tag)
1163 {
1164   int i;
1165
1166   for (i = 0; regset[i] >= 0; i++)
1167     {
1168       int id = regset[i] / 2;
1169       int start = !(regset[i] % 2);
1170       if (start)
1171         tnfa->submatch_data[id].so_tag = tag;
1172       else
1173         tnfa->submatch_data[id].eo_tag = tag;
1174     }
1175   regset[0] = -1;
1176 }
1177
1178
1179 /* Adds tags to appropriate locations in the parse tree in `tree', so that
1180    subexpressions marked for submatch addressing can be traced. */
1181 static reg_errcode_t
1182 tre_add_tags(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree,
1183              tre_tnfa_t *tnfa)
1184 {
1185   reg_errcode_t status = REG_OK;
1186   tre_addtags_symbol_t symbol;
1187   tre_ast_node_t *node = tree; /* Tree node we are currently looking at. */
1188   int bottom = tre_stack_num_objects(stack);
1189   /* True for first pass (counting number of needed tags) */
1190   int first_pass = (mem == NULL || tnfa == NULL);
1191   int *regset, *orig_regset;
1192   int num_tags = 0; /* Total number of tags. */
1193   int num_minimals = 0;  /* Number of special minimal tags. */
1194   int tag = 0;      /* The tag that is to be added next. */
1195   int next_tag = 1; /* Next tag to use after this one. */
1196   int *parents;     /* Stack of submatches the current submatch is
1197                        contained in. */
1198   int minimal_tag = -1; /* Tag that marks the beginning of a minimal match. */
1199   tre_tag_states_t *saved_states;
1200
1201   tre_tag_direction_t direction = TRE_TAG_MINIMIZE;
1202   if (!first_pass)
1203     {
1204       tnfa->end_tag = 0;
1205       tnfa->minimal_tags[0] = -1;
1206     }
1207
1208   regset = xmalloc(sizeof(*regset) * ((tnfa->num_submatches + 1) * 2));
1209   if (regset == NULL)
1210     return REG_ESPACE;
1211   regset[0] = -1;
1212   orig_regset = regset;
1213
1214   parents = xmalloc(sizeof(*parents) * (tnfa->num_submatches + 1));
1215   if (parents == NULL)
1216     {
1217       xfree(regset);
1218       return REG_ESPACE;
1219     }
1220   parents[0] = -1;
1221
1222   saved_states = xmalloc(sizeof(*saved_states) * (tnfa->num_submatches + 1));
1223   if (saved_states == NULL)
1224     {
1225       xfree(regset);
1226       xfree(parents);
1227       return REG_ESPACE;
1228     }
1229   else
1230     {
1231       unsigned int i;
1232       for (i = 0; i <= tnfa->num_submatches; i++)
1233         saved_states[i].tag = -1;
1234     }
1235
1236   STACK_PUSH(stack, voidptr, node);
1237   STACK_PUSH(stack, int, ADDTAGS_RECURSE);
1238
1239   while (tre_stack_num_objects(stack) > bottom)
1240     {
1241       if (status != REG_OK)
1242         break;
1243
1244       symbol = (tre_addtags_symbol_t)tre_stack_pop_int(stack);
1245       switch (symbol)
1246         {
1247
1248         case ADDTAGS_SET_SUBMATCH_END:
1249           {
1250             int id = tre_stack_pop_int(stack);
1251             int i;
1252
1253             /* Add end of this submatch to regset. */
1254             for (i = 0; regset[i] >= 0; i++);
1255             regset[i] = id * 2 + 1;
1256             regset[i + 1] = -1;
1257
1258             /* Pop this submatch from the parents stack. */
1259             for (i = 0; parents[i] >= 0; i++);
1260             parents[i - 1] = -1;
1261             break;
1262           }
1263
1264         case ADDTAGS_RECURSE:
1265           node = tre_stack_pop_voidptr(stack);
1266
1267           if (node->submatch_id >= 0)
1268             {
1269               int id = node->submatch_id;
1270               int i;
1271
1272
1273               /* Add start of this submatch to regset. */
1274               for (i = 0; regset[i] >= 0; i++);
1275               regset[i] = id * 2;
1276               regset[i + 1] = -1;
1277
1278               if (!first_pass)
1279                 {
1280                   for (i = 0; parents[i] >= 0; i++);
1281                   tnfa->submatch_data[id].parents = NULL;
1282                   if (i > 0)
1283                     {
1284                       int *p = xmalloc(sizeof(*p) * (i + 1));
1285                       if (p == NULL)
1286                         {
1287                           status = REG_ESPACE;
1288                           break;
1289                         }
1290                       assert(tnfa->submatch_data[id].parents == NULL);
1291                       tnfa->submatch_data[id].parents = p;
1292                       for (i = 0; parents[i] >= 0; i++)
1293                         p[i] = parents[i];
1294                       p[i] = -1;
1295                     }
1296                 }
1297
1298               /* Add end of this submatch to regset after processing this
1299                  node. */
1300               STACK_PUSHX(stack, int, node->submatch_id);
1301               STACK_PUSHX(stack, int, ADDTAGS_SET_SUBMATCH_END);
1302             }
1303
1304           switch (node->type)
1305             {
1306             case LITERAL:
1307               {
1308                 tre_literal_t *lit = node->obj;
1309
1310                 if (!IS_SPECIAL(lit) || IS_BACKREF(lit))
1311                   {
1312                     int i;
1313                     if (regset[0] >= 0)
1314                       {
1315                         /* Regset is not empty, so add a tag before the
1316                            literal or backref. */
1317                         if (!first_pass)
1318                           {
1319                             status = tre_add_tag_left(mem, node, tag);
1320                             tnfa->tag_directions[tag] = direction;
1321                             if (minimal_tag >= 0)
1322                               {
1323                                 for (i = 0; tnfa->minimal_tags[i] >= 0; i++);
1324                                 tnfa->minimal_tags[i] = tag;
1325                                 tnfa->minimal_tags[i + 1] = minimal_tag;
1326                                 tnfa->minimal_tags[i + 2] = -1;
1327                                 minimal_tag = -1;
1328                                 num_minimals++;
1329                               }
1330                             tre_purge_regset(regset, tnfa, tag);
1331                           }
1332                         else
1333                           {
1334                             node->num_tags = 1;
1335                           }
1336
1337                         regset[0] = -1;
1338                         tag = next_tag;
1339                         num_tags++;
1340                         next_tag++;
1341                       }
1342                   }
1343                 else
1344                   {
1345                     assert(!IS_TAG(lit));
1346                   }
1347                 break;
1348               }
1349             case CATENATION:
1350               {
1351                 tre_catenation_t *cat = node->obj;
1352                 tre_ast_node_t *left = cat->left;
1353                 tre_ast_node_t *right = cat->right;
1354                 int reserved_tag = -1;
1355
1356
1357                 /* After processing right child. */
1358                 STACK_PUSHX(stack, voidptr, node);
1359                 STACK_PUSHX(stack, int, ADDTAGS_AFTER_CAT_RIGHT);
1360
1361                 /* Process right child. */
1362                 STACK_PUSHX(stack, voidptr, right);
1363                 STACK_PUSHX(stack, int, ADDTAGS_RECURSE);
1364
1365                 /* After processing left child. */
1366                 STACK_PUSHX(stack, int, next_tag + left->num_tags);
1367                 if (left->num_tags > 0 && right->num_tags > 0)
1368                   {
1369                     /* Reserve the next tag to the right child. */
1370                     reserved_tag = next_tag;
1371                     next_tag++;
1372                   }
1373                 STACK_PUSHX(stack, int, reserved_tag);
1374                 STACK_PUSHX(stack, int, ADDTAGS_AFTER_CAT_LEFT);
1375
1376                 /* Process left child. */
1377                 STACK_PUSHX(stack, voidptr, left);
1378                 STACK_PUSHX(stack, int, ADDTAGS_RECURSE);
1379
1380                 }
1381               break;
1382             case ITERATION:
1383               {
1384                 tre_iteration_t *iter = node->obj;
1385
1386                 if (first_pass)
1387                   {
1388                     STACK_PUSHX(stack, int, regset[0] >= 0 || iter->minimal);
1389                   }
1390                 else
1391                   {
1392                     STACK_PUSHX(stack, int, tag);
1393                     STACK_PUSHX(stack, int, iter->minimal);
1394                   }
1395                 STACK_PUSHX(stack, voidptr, node);
1396                 STACK_PUSHX(stack, int, ADDTAGS_AFTER_ITERATION);
1397
1398                 STACK_PUSHX(stack, voidptr, iter->arg);
1399                 STACK_PUSHX(stack, int, ADDTAGS_RECURSE);
1400
1401                 /* Regset is not empty, so add a tag here. */
1402                 if (regset[0] >= 0 || iter->minimal)
1403                   {
1404                     if (!first_pass)
1405                       {
1406                         int i;
1407                         status = tre_add_tag_left(mem, node, tag);
1408                         if (iter->minimal)
1409                           tnfa->tag_directions[tag] = TRE_TAG_MAXIMIZE;
1410                         else
1411                           tnfa->tag_directions[tag] = direction;
1412                         if (minimal_tag >= 0)
1413                           {
1414                             for (i = 0; tnfa->minimal_tags[i] >= 0; i++);
1415                             tnfa->minimal_tags[i] = tag;
1416                             tnfa->minimal_tags[i + 1] = minimal_tag;
1417                             tnfa->minimal_tags[i + 2] = -1;
1418                             minimal_tag = -1;
1419                             num_minimals++;
1420                           }
1421                         tre_purge_regset(regset, tnfa, tag);
1422                       }
1423
1424                     regset[0] = -1;
1425                     tag = next_tag;
1426                     num_tags++;
1427                     next_tag++;
1428                   }
1429                 direction = TRE_TAG_MINIMIZE;
1430               }
1431               break;
1432             case UNION:
1433               {
1434                 tre_union_t *uni = node->obj;
1435                 tre_ast_node_t *left = uni->left;
1436                 tre_ast_node_t *right = uni->right;
1437                 int left_tag;
1438                 int right_tag;
1439
1440                 if (regset[0] >= 0)
1441                   {
1442                     left_tag = next_tag;
1443                     right_tag = next_tag + 1;
1444                   }
1445                 else
1446                   {
1447                     left_tag = tag;
1448                     right_tag = next_tag;
1449                   }
1450
1451                 /* After processing right child. */
1452                 STACK_PUSHX(stack, int, right_tag);
1453                 STACK_PUSHX(stack, int, left_tag);
1454                 STACK_PUSHX(stack, voidptr, regset);
1455                 STACK_PUSHX(stack, int, regset[0] >= 0);
1456                 STACK_PUSHX(stack, voidptr, node);
1457                 STACK_PUSHX(stack, voidptr, right);
1458                 STACK_PUSHX(stack, voidptr, left);
1459                 STACK_PUSHX(stack, int, ADDTAGS_AFTER_UNION_RIGHT);
1460
1461                 /* Process right child. */
1462                 STACK_PUSHX(stack, voidptr, right);
1463                 STACK_PUSHX(stack, int, ADDTAGS_RECURSE);
1464
1465                 /* After processing left child. */
1466                 STACK_PUSHX(stack, int, ADDTAGS_AFTER_UNION_LEFT);
1467
1468                 /* Process left child. */
1469                 STACK_PUSHX(stack, voidptr, left);
1470                 STACK_PUSHX(stack, int, ADDTAGS_RECURSE);
1471
1472                 /* Regset is not empty, so add a tag here. */
1473                 if (regset[0] >= 0)
1474                   {
1475                     if (!first_pass)
1476                       {
1477                         int i;
1478                         status = tre_add_tag_left(mem, node, tag);
1479                         tnfa->tag_directions[tag] = direction;
1480                         if (minimal_tag >= 0)
1481                           {
1482                             for (i = 0; tnfa->minimal_tags[i] >= 0; i++);
1483                             tnfa->minimal_tags[i] = tag;
1484                             tnfa->minimal_tags[i + 1] = minimal_tag;
1485                             tnfa->minimal_tags[i + 2] = -1;
1486                             minimal_tag = -1;
1487                             num_minimals++;
1488                           }
1489                         tre_purge_regset(regset, tnfa, tag);
1490                       }
1491
1492                     regset[0] = -1;
1493                     tag = next_tag;
1494                     num_tags++;
1495                     next_tag++;
1496                   }
1497
1498                 if (node->num_submatches > 0)
1499                   {
1500                     /* The next two tags are reserved for markers. */
1501                     next_tag++;
1502                     tag = next_tag;
1503                     next_tag++;
1504                   }
1505
1506                 break;
1507               }
1508             }
1509
1510           if (node->submatch_id >= 0)
1511             {
1512               int i;
1513               /* Push this submatch on the parents stack. */
1514               for (i = 0; parents[i] >= 0; i++);
1515               parents[i] = node->submatch_id;
1516               parents[i + 1] = -1;
1517             }
1518
1519           break; /* end case: ADDTAGS_RECURSE */
1520
1521         case ADDTAGS_AFTER_ITERATION:
1522           {
1523             int minimal = 0;
1524             int enter_tag;
1525             node = tre_stack_pop_voidptr(stack);
1526             if (first_pass)
1527               {
1528                 node->num_tags = ((tre_iteration_t *)node->obj)->arg->num_tags
1529                   + tre_stack_pop_int(stack);
1530                 minimal_tag = -1;
1531               }
1532             else
1533               {
1534                 minimal = tre_stack_pop_int(stack);
1535                 enter_tag = tre_stack_pop_int(stack);
1536                 if (minimal)
1537                   minimal_tag = enter_tag;
1538               }
1539
1540             if (!first_pass)
1541               {
1542                 if (minimal)
1543                   direction = TRE_TAG_MINIMIZE;
1544                 else
1545                   direction = TRE_TAG_MAXIMIZE;
1546               }
1547             break;
1548           }
1549
1550         case ADDTAGS_AFTER_CAT_LEFT:
1551           {
1552             int new_tag = tre_stack_pop_int(stack);
1553             next_tag = tre_stack_pop_int(stack);
1554             if (new_tag >= 0)
1555               {
1556                 tag = new_tag;
1557               }
1558             break;
1559           }
1560
1561         case ADDTAGS_AFTER_CAT_RIGHT:
1562           node = tre_stack_pop_voidptr(stack);
1563           if (first_pass)
1564             node->num_tags = ((tre_catenation_t *)node->obj)->left->num_tags
1565               + ((tre_catenation_t *)node->obj)->right->num_tags;
1566           break;
1567
1568         case ADDTAGS_AFTER_UNION_LEFT:
1569           /* Lift the bottom of the `regset' array so that when processing
1570              the right operand the items currently in the array are
1571              invisible.  The original bottom was saved at ADDTAGS_UNION and
1572              will be restored at ADDTAGS_AFTER_UNION_RIGHT below. */
1573           while (*regset >= 0)
1574             regset++;
1575           break;
1576
1577         case ADDTAGS_AFTER_UNION_RIGHT:
1578           {
1579             int added_tags, tag_left, tag_right;
1580             tre_ast_node_t *left = tre_stack_pop_voidptr(stack);
1581             tre_ast_node_t *right = tre_stack_pop_voidptr(stack);
1582             node = tre_stack_pop_voidptr(stack);
1583             added_tags = tre_stack_pop_int(stack);
1584             if (first_pass)
1585               {
1586                 node->num_tags = ((tre_union_t *)node->obj)->left->num_tags
1587                   + ((tre_union_t *)node->obj)->right->num_tags + added_tags
1588                   + ((node->num_submatches > 0) ? 2 : 0);
1589               }
1590             regset = tre_stack_pop_voidptr(stack);
1591             tag_left = tre_stack_pop_int(stack);
1592             tag_right = tre_stack_pop_int(stack);
1593
1594             /* Add tags after both children, the left child gets a smaller
1595                tag than the right child.  This guarantees that we prefer
1596                the left child over the right child. */
1597             /* XXX - This is not always necessary (if the children have
1598                tags which must be seen for every match of that child). */
1599             /* XXX - Check if this is the only place where tre_add_tag_right
1600                is used.  If so, use tre_add_tag_left (putting the tag before
1601                the child as opposed after the child) and throw away
1602                tre_add_tag_right. */
1603             if (node->num_submatches > 0)
1604               {
1605                 if (!first_pass)
1606                   {
1607                     status = tre_add_tag_right(mem, left, tag_left);
1608                     tnfa->tag_directions[tag_left] = TRE_TAG_MAXIMIZE;
1609                     if (status == REG_OK)
1610                       status = tre_add_tag_right(mem, right, tag_right);
1611                     tnfa->tag_directions[tag_right] = TRE_TAG_MAXIMIZE;
1612                   }
1613                 num_tags += 2;
1614               }
1615             direction = TRE_TAG_MAXIMIZE;
1616             break;
1617           }
1618
1619         default:
1620           assert(0);
1621           break;
1622
1623         } /* end switch(symbol) */
1624     } /* end while(tre_stack_num_objects(stack) > bottom) */
1625
1626   if (!first_pass)
1627     tre_purge_regset(regset, tnfa, tag);
1628
1629   if (!first_pass && minimal_tag >= 0)
1630     {
1631       int i;
1632       for (i = 0; tnfa->minimal_tags[i] >= 0; i++);
1633       tnfa->minimal_tags[i] = tag;
1634       tnfa->minimal_tags[i + 1] = minimal_tag;
1635       tnfa->minimal_tags[i + 2] = -1;
1636       minimal_tag = -1;
1637       num_minimals++;
1638     }
1639
1640   assert(tree->num_tags == num_tags);
1641   tnfa->end_tag = num_tags;
1642   tnfa->num_tags = num_tags;
1643   tnfa->num_minimals = num_minimals;
1644   xfree(orig_regset);
1645   xfree(parents);
1646   xfree(saved_states);
1647   return status;
1648 }
1649
1650
1651
1652 /*
1653   AST to TNFA compilation routines.
1654 */
1655
1656 typedef enum {
1657   COPY_RECURSE,
1658   COPY_SET_RESULT_PTR
1659 } tre_copyast_symbol_t;
1660
1661 /* Flags for tre_copy_ast(). */
1662 #define COPY_REMOVE_TAGS         1
1663 #define COPY_MAXIMIZE_FIRST_TAG  2
1664
1665 static reg_errcode_t
1666 tre_copy_ast(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *ast,
1667              int flags, int *pos_add, tre_tag_direction_t *tag_directions,
1668              tre_ast_node_t **copy, int *max_pos)
1669 {
1670   reg_errcode_t status = REG_OK;
1671   int bottom = tre_stack_num_objects(stack);
1672   int num_copied = 0;
1673   int first_tag = 1;
1674   tre_ast_node_t **result = copy;
1675   tre_copyast_symbol_t symbol;
1676
1677   STACK_PUSH(stack, voidptr, ast);
1678   STACK_PUSH(stack, int, COPY_RECURSE);
1679
1680   while (status == REG_OK && tre_stack_num_objects(stack) > bottom)
1681     {
1682       tre_ast_node_t *node;
1683       if (status != REG_OK)
1684         break;
1685
1686       symbol = (tre_copyast_symbol_t)tre_stack_pop_int(stack);
1687       switch (symbol)
1688         {
1689         case COPY_SET_RESULT_PTR:
1690           result = tre_stack_pop_voidptr(stack);
1691           break;
1692         case COPY_RECURSE:
1693           node = tre_stack_pop_voidptr(stack);
1694           switch (node->type)
1695             {
1696             case LITERAL:
1697               {
1698                 tre_literal_t *lit = node->obj;
1699                 int pos = lit->position;
1700                 int min = lit->code_min;
1701                 int max = lit->code_max;
1702                 if (!IS_SPECIAL(lit) || IS_BACKREF(lit))
1703                   {
1704                     /* XXX - e.g. [ab] has only one position but two
1705                        nodes, so we are creating holes in the state space
1706                        here.  Not fatal, just wastes memory. */
1707                     pos += *pos_add;
1708                     num_copied++;
1709                   }
1710                 else if (IS_TAG(lit) && (flags & COPY_REMOVE_TAGS))
1711                   {
1712                     /* Change this tag to empty. */
1713                     min = EMPTY;
1714                     max = pos = -1;
1715                   }
1716                 else if (IS_TAG(lit) && (flags & COPY_MAXIMIZE_FIRST_TAG)
1717                          && first_tag)
1718                   {
1719                     /* Maximize the first tag. */
1720                     tag_directions[max] = TRE_TAG_MAXIMIZE;
1721                     first_tag = 0;
1722                   }
1723                 *result = tre_ast_new_literal(mem, min, max, pos);
1724                 if (*result == NULL)
1725                   status = REG_ESPACE;
1726                 else {
1727                   tre_literal_t *p = (*result)->obj;
1728                   p->class = lit->class;
1729                   p->neg_classes = lit->neg_classes;
1730                 }
1731
1732                 if (pos > *max_pos)
1733                   *max_pos = pos;
1734                 break;
1735               }
1736             case UNION:
1737               {
1738                 tre_union_t *uni = node->obj;
1739                 tre_union_t *tmp;
1740                 *result = tre_ast_new_union(mem, uni->left, uni->right);
1741                 if (*result == NULL)
1742                   {
1743                     status = REG_ESPACE;
1744                     break;
1745                   }
1746                 tmp = (*result)->obj;
1747                 result = &tmp->left;
1748                 STACK_PUSHX(stack, voidptr, uni->right);
1749                 STACK_PUSHX(stack, int, COPY_RECURSE);
1750                 STACK_PUSHX(stack, voidptr, &tmp->right);
1751                 STACK_PUSHX(stack, int, COPY_SET_RESULT_PTR);
1752                 STACK_PUSHX(stack, voidptr, uni->left);
1753                 STACK_PUSHX(stack, int, COPY_RECURSE);
1754                 break;
1755               }
1756             case CATENATION:
1757               {
1758                 tre_catenation_t *cat = node->obj;
1759                 tre_catenation_t *tmp;
1760                 *result = tre_ast_new_catenation(mem, cat->left, cat->right);
1761                 if (*result == NULL)
1762                   {
1763                     status = REG_ESPACE;
1764                     break;
1765                   }
1766                 tmp = (*result)->obj;
1767                 tmp->left = NULL;
1768                 tmp->right = NULL;
1769                 result = &tmp->left;
1770
1771                 STACK_PUSHX(stack, voidptr, cat->right);
1772                 STACK_PUSHX(stack, int, COPY_RECURSE);
1773                 STACK_PUSHX(stack, voidptr, &tmp->right);
1774                 STACK_PUSHX(stack, int, COPY_SET_RESULT_PTR);
1775                 STACK_PUSHX(stack, voidptr, cat->left);
1776                 STACK_PUSHX(stack, int, COPY_RECURSE);
1777                 break;
1778               }
1779             case ITERATION:
1780               {
1781                 tre_iteration_t *iter = node->obj;
1782                 STACK_PUSHX(stack, voidptr, iter->arg);
1783                 STACK_PUSHX(stack, int, COPY_RECURSE);
1784                 *result = tre_ast_new_iter(mem, iter->arg, iter->min,
1785                                            iter->max, iter->minimal);
1786                 if (*result == NULL)
1787                   {
1788                     status = REG_ESPACE;
1789                     break;
1790                   }
1791                 iter = (*result)->obj;
1792                 result = &iter->arg;
1793                 break;
1794               }
1795             default:
1796               assert(0);
1797               break;
1798             }
1799           break;
1800         }
1801     }
1802   *pos_add += num_copied;
1803   return status;
1804 }
1805
1806 typedef enum {
1807   EXPAND_RECURSE,
1808   EXPAND_AFTER_ITER
1809 } tre_expand_ast_symbol_t;
1810
1811 /* Expands each iteration node that has a finite nonzero minimum or maximum
1812    iteration count to a catenated sequence of copies of the node. */
1813 static reg_errcode_t
1814 tre_expand_ast(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *ast,
1815                int *position, tre_tag_direction_t *tag_directions)
1816 {
1817   reg_errcode_t status = REG_OK;
1818   int bottom = tre_stack_num_objects(stack);
1819   int pos_add = 0;
1820   int pos_add_total = 0;
1821   int max_pos = 0;
1822   int iter_depth = 0;
1823
1824   STACK_PUSHR(stack, voidptr, ast);
1825   STACK_PUSHR(stack, int, EXPAND_RECURSE);
1826   while (status == REG_OK && tre_stack_num_objects(stack) > bottom)
1827     {
1828       tre_ast_node_t *node;
1829       tre_expand_ast_symbol_t symbol;
1830
1831       if (status != REG_OK)
1832         break;
1833
1834       symbol = (tre_expand_ast_symbol_t)tre_stack_pop_int(stack);
1835       node = tre_stack_pop_voidptr(stack);
1836       switch (symbol)
1837         {
1838         case EXPAND_RECURSE:
1839           switch (node->type)
1840             {
1841             case LITERAL:
1842               {
1843                 tre_literal_t *lit= node->obj;
1844                 if (!IS_SPECIAL(lit) || IS_BACKREF(lit))
1845                   {
1846                     lit->position += pos_add;
1847                     if (lit->position > max_pos)
1848                       max_pos = lit->position;
1849                   }
1850                 break;
1851               }
1852             case UNION:
1853               {
1854                 tre_union_t *uni = node->obj;
1855                 STACK_PUSHX(stack, voidptr, uni->right);
1856                 STACK_PUSHX(stack, int, EXPAND_RECURSE);
1857                 STACK_PUSHX(stack, voidptr, uni->left);
1858                 STACK_PUSHX(stack, int, EXPAND_RECURSE);
1859                 break;
1860               }
1861             case CATENATION:
1862               {
1863                 tre_catenation_t *cat = node->obj;
1864                 STACK_PUSHX(stack, voidptr, cat->right);
1865                 STACK_PUSHX(stack, int, EXPAND_RECURSE);
1866                 STACK_PUSHX(stack, voidptr, cat->left);
1867                 STACK_PUSHX(stack, int, EXPAND_RECURSE);
1868                 break;
1869               }
1870             case ITERATION:
1871               {
1872                 tre_iteration_t *iter = node->obj;
1873                 STACK_PUSHX(stack, int, pos_add);
1874                 STACK_PUSHX(stack, voidptr, node);
1875                 STACK_PUSHX(stack, int, EXPAND_AFTER_ITER);
1876                 STACK_PUSHX(stack, voidptr, iter->arg);
1877                 STACK_PUSHX(stack, int, EXPAND_RECURSE);
1878                 /* If we are going to expand this node at EXPAND_AFTER_ITER
1879                    then don't increase the `pos' fields of the nodes now, it
1880                    will get done when expanding. */
1881                 if (iter->min > 1 || iter->max > 1)
1882                   pos_add = 0;
1883                 iter_depth++;
1884                 break;
1885               }
1886             default:
1887               assert(0);
1888               break;
1889             }
1890           break;
1891         case EXPAND_AFTER_ITER:
1892           {
1893             tre_iteration_t *iter = node->obj;
1894             int pos_add_last;
1895             pos_add = tre_stack_pop_int(stack);
1896             pos_add_last = pos_add;
1897             if (iter->min > 1 || iter->max > 1)
1898               {
1899                 tre_ast_node_t *seq1 = NULL, *seq2 = NULL;
1900                 int j;
1901                 int pos_add_save = pos_add;
1902
1903                 /* Create a catenated sequence of copies of the node. */
1904                 for (j = 0; j < iter->min; j++)
1905                   {
1906                     tre_ast_node_t *copy;
1907                     /* Remove tags from all but the last copy. */
1908                     int flags = ((j + 1 < iter->min)
1909                                  ? COPY_REMOVE_TAGS
1910                                  : COPY_MAXIMIZE_FIRST_TAG);
1911                     pos_add_save = pos_add;
1912                     status = tre_copy_ast(mem, stack, iter->arg, flags,
1913                                           &pos_add, tag_directions, &copy,
1914                                           &max_pos);
1915                     if (status != REG_OK)
1916                       return status;
1917                     if (seq1 != NULL)
1918                       seq1 = tre_ast_new_catenation(mem, seq1, copy);
1919                     else
1920                       seq1 = copy;
1921                     if (seq1 == NULL)
1922                       return REG_ESPACE;
1923                   }
1924
1925                 if (iter->max == -1)
1926                   {
1927                     /* No upper limit. */
1928                     pos_add_save = pos_add;
1929                     status = tre_copy_ast(mem, stack, iter->arg, 0,
1930                                           &pos_add, NULL, &seq2, &max_pos);
1931                     if (status != REG_OK)
1932                       return status;
1933                     seq2 = tre_ast_new_iter(mem, seq2, 0, -1, 0);
1934                     if (seq2 == NULL)
1935                       return REG_ESPACE;
1936                   }
1937                 else
1938                   {
1939                     for (j = iter->min; j < iter->max; j++)
1940                       {
1941                         tre_ast_node_t *tmp, *copy;
1942                         pos_add_save = pos_add;
1943                         status = tre_copy_ast(mem, stack, iter->arg, 0,
1944                                               &pos_add, NULL, &copy, &max_pos);
1945                         if (status != REG_OK)
1946                           return status;
1947                         if (seq2 != NULL)
1948                           seq2 = tre_ast_new_catenation(mem, copy, seq2);
1949                         else
1950                           seq2 = copy;
1951                         if (seq2 == NULL)
1952                           return REG_ESPACE;
1953                         tmp = tre_ast_new_literal(mem, EMPTY, -1, -1);
1954                         if (tmp == NULL)
1955                           return REG_ESPACE;
1956                         seq2 = tre_ast_new_union(mem, tmp, seq2);
1957                         if (seq2 == NULL)
1958                           return REG_ESPACE;
1959                       }
1960                   }
1961
1962                 pos_add = pos_add_save;
1963                 if (seq1 == NULL)
1964                   seq1 = seq2;
1965                 else if (seq2 != NULL)
1966                   seq1 = tre_ast_new_catenation(mem, seq1, seq2);
1967                 if (seq1 == NULL)
1968                   return REG_ESPACE;
1969                 node->obj = seq1->obj;
1970                 node->type = seq1->type;
1971               }
1972
1973             iter_depth--;
1974             pos_add_total += pos_add - pos_add_last;
1975             if (iter_depth == 0)
1976               pos_add = pos_add_total;
1977
1978             break;
1979           }
1980         default:
1981           assert(0);
1982           break;
1983         }
1984     }
1985
1986   *position += pos_add_total;
1987
1988   /* `max_pos' should never be larger than `*position' if the above
1989      code works, but just an extra safeguard let's make sure
1990      `*position' is set large enough so enough memory will be
1991      allocated for the transition table. */
1992   if (max_pos > *position)
1993     *position = max_pos;
1994
1995   return status;
1996 }
1997
1998 static tre_pos_and_tags_t *
1999 tre_set_empty(tre_mem_t mem)
2000 {
2001   tre_pos_and_tags_t *new_set;
2002
2003   new_set = tre_mem_calloc(mem, sizeof(*new_set));
2004   if (new_set == NULL)
2005     return NULL;
2006
2007   new_set[0].position = -1;
2008   new_set[0].code_min = -1;
2009   new_set[0].code_max = -1;
2010
2011   return new_set;
2012 }
2013
2014 static tre_pos_and_tags_t *
2015 tre_set_one(tre_mem_t mem, int position, int code_min, int code_max,
2016             tre_ctype_t class, tre_ctype_t *neg_classes, int backref)
2017 {
2018   tre_pos_and_tags_t *new_set;
2019
2020   new_set = tre_mem_calloc(mem, sizeof(*new_set) * 2);
2021   if (new_set == NULL)
2022     return NULL;
2023
2024   new_set[0].position = position;
2025   new_set[0].code_min = code_min;
2026   new_set[0].code_max = code_max;
2027   new_set[0].class = class;
2028   new_set[0].neg_classes = neg_classes;
2029   new_set[0].backref = backref;
2030   new_set[1].position = -1;
2031   new_set[1].code_min = -1;
2032   new_set[1].code_max = -1;
2033
2034   return new_set;
2035 }
2036
2037 static tre_pos_and_tags_t *
2038 tre_set_union(tre_mem_t mem, tre_pos_and_tags_t *set1, tre_pos_and_tags_t *set2,
2039               int *tags, int assertions)
2040 {
2041   int s1, s2, i, j;
2042   tre_pos_and_tags_t *new_set;
2043   int *new_tags;
2044   int num_tags;
2045
2046   for (num_tags = 0; tags != NULL && tags[num_tags] >= 0; num_tags++);
2047   for (s1 = 0; set1[s1].position >= 0; s1++);
2048   for (s2 = 0; set2[s2].position >= 0; s2++);
2049   new_set = tre_mem_calloc(mem, sizeof(*new_set) * (s1 + s2 + 1));
2050   if (!new_set )
2051     return NULL;
2052
2053   for (s1 = 0; set1[s1].position >= 0; s1++)
2054     {
2055       new_set[s1].position = set1[s1].position;
2056       new_set[s1].code_min = set1[s1].code_min;
2057       new_set[s1].code_max = set1[s1].code_max;
2058       new_set[s1].assertions = set1[s1].assertions | assertions;
2059       new_set[s1].class = set1[s1].class;
2060       new_set[s1].neg_classes = set1[s1].neg_classes;
2061       new_set[s1].backref = set1[s1].backref;
2062       if (set1[s1].tags == NULL && tags == NULL)
2063         new_set[s1].tags = NULL;
2064       else
2065         {
2066           for (i = 0; set1[s1].tags != NULL && set1[s1].tags[i] >= 0; i++);
2067           new_tags = tre_mem_alloc(mem, (sizeof(*new_tags)
2068                                          * (i + num_tags + 1)));
2069           if (new_tags == NULL)
2070             return NULL;
2071           for (j = 0; j < i; j++)
2072             new_tags[j] = set1[s1].tags[j];
2073           for (i = 0; i < num_tags; i++)
2074             new_tags[j + i] = tags[i];
2075           new_tags[j + i] = -1;
2076           new_set[s1].tags = new_tags;
2077         }
2078     }
2079
2080   for (s2 = 0; set2[s2].position >= 0; s2++)
2081     {
2082       new_set[s1 + s2].position = set2[s2].position;
2083       new_set[s1 + s2].code_min = set2[s2].code_min;
2084       new_set[s1 + s2].code_max = set2[s2].code_max;
2085       /* XXX - why not | assertions here as well? */
2086       new_set[s1 + s2].assertions = set2[s2].assertions;
2087       new_set[s1 + s2].class = set2[s2].class;
2088       new_set[s1 + s2].neg_classes = set2[s2].neg_classes;
2089       new_set[s1 + s2].backref = set2[s2].backref;
2090       if (set2[s2].tags == NULL)
2091         new_set[s1 + s2].tags = NULL;
2092       else
2093         {
2094           for (i = 0; set2[s2].tags[i] >= 0; i++);
2095           new_tags = tre_mem_alloc(mem, sizeof(*new_tags) * (i + 1));
2096           if (new_tags == NULL)
2097             return NULL;
2098           for (j = 0; j < i; j++)
2099             new_tags[j] = set2[s2].tags[j];
2100           new_tags[j] = -1;
2101           new_set[s1 + s2].tags = new_tags;
2102         }
2103     }
2104   new_set[s1 + s2].position = -1;
2105   return new_set;
2106 }
2107
2108 /* Finds the empty path through `node' which is the one that should be
2109    taken according to POSIX.2 rules, and adds the tags on that path to
2110    `tags'.   `tags' may be NULL.  If `num_tags_seen' is not NULL, it is
2111    set to the number of tags seen on the path. */
2112 static reg_errcode_t
2113 tre_match_empty(tre_stack_t *stack, tre_ast_node_t *node, int *tags,
2114                 int *assertions, int *num_tags_seen)
2115 {
2116   tre_literal_t *lit;
2117   tre_union_t *uni;
2118   tre_catenation_t *cat;
2119   tre_iteration_t *iter;
2120   int i;
2121   int bottom = tre_stack_num_objects(stack);
2122   reg_errcode_t status = REG_OK;
2123   if (num_tags_seen)
2124     *num_tags_seen = 0;
2125
2126   status = tre_stack_push_voidptr(stack, node);
2127
2128   /* Walk through the tree recursively. */
2129   while (status == REG_OK && tre_stack_num_objects(stack) > bottom)
2130     {
2131       node = tre_stack_pop_voidptr(stack);
2132
2133       switch (node->type)
2134         {
2135         case LITERAL:
2136           lit = (tre_literal_t *)node->obj;
2137           switch (lit->code_min)
2138             {
2139             case TAG:
2140               if (lit->code_max >= 0)
2141                 {
2142                   if (tags != NULL)
2143                     {
2144                       /* Add the tag to `tags'. */
2145                       for (i = 0; tags[i] >= 0; i++)
2146                         if (tags[i] == lit->code_max)
2147                           break;
2148                       if (tags[i] < 0)
2149                         {
2150                           tags[i] = lit->code_max;
2151                           tags[i + 1] = -1;
2152                         }
2153                     }
2154                   if (num_tags_seen)
2155                     (*num_tags_seen)++;
2156                 }
2157               break;
2158             case ASSERTION:
2159               assert(lit->code_max >= 1
2160                      || lit->code_max <= ASSERT_LAST);
2161               if (assertions != NULL)
2162                 *assertions |= lit->code_max;
2163               break;
2164             case EMPTY:
2165               break;
2166             default:
2167               assert(0);
2168               break;
2169             }
2170           break;
2171
2172         case UNION:
2173           /* Subexpressions starting earlier take priority over ones
2174              starting later, so we prefer the left subexpression over the
2175              right subexpression. */
2176           uni = (tre_union_t *)node->obj;
2177           if (uni->left->nullable)
2178             STACK_PUSHX(stack, voidptr, uni->left)
2179           else if (uni->right->nullable)
2180             STACK_PUSHX(stack, voidptr, uni->right)
2181           else
2182             assert(0);
2183           break;
2184
2185         case CATENATION:
2186           /* The path must go through both children. */
2187           cat = (tre_catenation_t *)node->obj;
2188           assert(cat->left->nullable);
2189           assert(cat->right->nullable);
2190           STACK_PUSHX(stack, voidptr, cat->left);
2191           STACK_PUSHX(stack, voidptr, cat->right);
2192           break;
2193
2194         case ITERATION:
2195           /* A match with an empty string is preferred over no match at
2196              all, so we go through the argument if possible. */
2197           iter = (tre_iteration_t *)node->obj;
2198           if (iter->arg->nullable)
2199             STACK_PUSHX(stack, voidptr, iter->arg);
2200           break;
2201
2202         default:
2203           assert(0);
2204           break;
2205         }
2206     }
2207
2208   return status;
2209 }
2210
2211
2212 typedef enum {
2213   NFL_RECURSE,
2214   NFL_POST_UNION,
2215   NFL_POST_CATENATION,
2216   NFL_POST_ITERATION
2217 } tre_nfl_stack_symbol_t;
2218
2219
2220 /* Computes and fills in the fields `nullable', `firstpos', and `lastpos' for
2221    the nodes of the AST `tree'. */
2222 static reg_errcode_t
2223 tre_compute_nfl(tre_mem_t mem, tre_stack_t *stack, tre_ast_node_t *tree)
2224 {
2225   int bottom = tre_stack_num_objects(stack);
2226
2227   STACK_PUSHR(stack, voidptr, tree);
2228   STACK_PUSHR(stack, int, NFL_RECURSE);
2229
2230   while (tre_stack_num_objects(stack) > bottom)
2231     {
2232       tre_nfl_stack_symbol_t symbol;
2233       tre_ast_node_t *node;
2234
2235       symbol = (tre_nfl_stack_symbol_t)tre_stack_pop_int(stack);
2236       node = tre_stack_pop_voidptr(stack);
2237       switch (symbol)
2238         {
2239         case NFL_RECURSE:
2240           switch (node->type)
2241             {
2242             case LITERAL:
2243               {
2244                 tre_literal_t *lit = (tre_literal_t *)node->obj;
2245                 if (IS_BACKREF(lit))
2246                   {
2247                     /* Back references: nullable = false, firstpos = {i},
2248                        lastpos = {i}. */
2249                     node->nullable = 0;
2250                     node->firstpos = tre_set_one(mem, lit->position, 0,
2251                                              TRE_CHAR_MAX, 0, NULL, -1);
2252                     if (!node->firstpos)
2253                       return REG_ESPACE;
2254                     node->lastpos = tre_set_one(mem, lit->position, 0,
2255                                                 TRE_CHAR_MAX, 0, NULL,
2256                                                 (int)lit->code_max);
2257                     if (!node->lastpos)
2258                       return REG_ESPACE;
2259                   }
2260                 else if (lit->code_min < 0)
2261                   {
2262                     /* Tags, empty strings, params, and zero width assertions:
2263                        nullable = true, firstpos = {}, and lastpos = {}. */
2264                     node->nullable = 1;
2265                     node->firstpos = tre_set_empty(mem);
2266                     if (!node->firstpos)
2267                       return REG_ESPACE;
2268                     node->lastpos = tre_set_empty(mem);
2269                     if (!node->lastpos)
2270                       return REG_ESPACE;
2271                   }
2272                 else
2273                   {
2274                     /* Literal at position i: nullable = false, firstpos = {i},
2275                        lastpos = {i}. */
2276                     node->nullable = 0;
2277                     node->firstpos =
2278                       tre_set_one(mem, lit->position, (int)lit->code_min,
2279                                   (int)lit->code_max, 0, NULL, -1);
2280                     if (!node->firstpos)
2281                       return REG_ESPACE;
2282                     node->lastpos = tre_set_one(mem, lit->position,
2283                                                 (int)lit->code_min,
2284                                                 (int)lit->code_max,
2285                                                 lit->class, lit->neg_classes,
2286                                                 -1);
2287                     if (!node->lastpos)
2288                       return REG_ESPACE;
2289                   }
2290                 break;
2291               }
2292
2293             case UNION:
2294               /* Compute the attributes for the two subtrees, and after that
2295                  for this node. */
2296               STACK_PUSHR(stack, voidptr, node);
2297               STACK_PUSHR(stack, int, NFL_POST_UNION);
2298               STACK_PUSHR(stack, voidptr, ((tre_union_t *)node->obj)->right);
2299               STACK_PUSHR(stack, int, NFL_RECURSE);
2300               STACK_PUSHR(stack, voidptr, ((tre_union_t *)node->obj)->left);
2301               STACK_PUSHR(stack, int, NFL_RECURSE);
2302               break;
2303
2304             case CATENATION:
2305               /* Compute the attributes for the two subtrees, and after that
2306                  for this node. */
2307               STACK_PUSHR(stack, voidptr, node);
2308               STACK_PUSHR(stack, int, NFL_POST_CATENATION);
2309               STACK_PUSHR(stack, voidptr, ((tre_catenation_t *)node->obj)->right);
2310               STACK_PUSHR(stack, int, NFL_RECURSE);
2311               STACK_PUSHR(stack, voidptr, ((tre_catenation_t *)node->obj)->left);
2312               STACK_PUSHR(stack, int, NFL_RECURSE);
2313               break;
2314
2315             case ITERATION:
2316               /* Compute the attributes for the subtree, and after that for
2317                  this node. */
2318               STACK_PUSHR(stack, voidptr, node);
2319               STACK_PUSHR(stack, int, NFL_POST_ITERATION);
2320               STACK_PUSHR(stack, voidptr, ((tre_iteration_t *)node->obj)->arg);
2321               STACK_PUSHR(stack, int, NFL_RECURSE);
2322               break;
2323             }
2324           break; /* end case: NFL_RECURSE */
2325
2326         case NFL_POST_UNION:
2327           {
2328             tre_union_t *uni = (tre_union_t *)node->obj;
2329             node->nullable = uni->left->nullable || uni->right->nullable;
2330             node->firstpos = tre_set_union(mem, uni->left->firstpos,
2331                                            uni->right->firstpos, NULL, 0);
2332             if (!node->firstpos)
2333               return REG_ESPACE;
2334             node->lastpos = tre_set_union(mem, uni->left->lastpos,
2335                                           uni->right->lastpos, NULL, 0);
2336             if (!node->lastpos)
2337               return REG_ESPACE;
2338             break;
2339           }
2340
2341         case NFL_POST_ITERATION:
2342           {
2343             tre_iteration_t *iter = (tre_iteration_t *)node->obj;
2344
2345             if (iter->min == 0 || iter->arg->nullable)
2346               node->nullable = 1;
2347             else
2348               node->nullable = 0;
2349             node->firstpos = iter->arg->firstpos;
2350             node->lastpos = iter->arg->lastpos;
2351             break;
2352           }
2353
2354         case NFL_POST_CATENATION:
2355           {
2356             int num_tags, *tags, assertions;
2357             reg_errcode_t status;
2358             tre_catenation_t *cat = node->obj;
2359             node->nullable = cat->left->nullable && cat->right->nullable;
2360
2361             /* Compute firstpos. */
2362             if (cat->left->nullable)
2363               {
2364                 /* The left side matches the empty string.  Make a first pass
2365                    with tre_match_empty() to get the number of tags and
2366                    parameters. */
2367                 status = tre_match_empty(stack, cat->left,
2368                                          NULL, NULL, &num_tags);
2369                 if (status != REG_OK)
2370                   return status;
2371                 /* Allocate arrays for the tags and parameters. */
2372                 tags = xmalloc(sizeof(*tags) * (num_tags + 1));
2373                 if (!tags)
2374                   return REG_ESPACE;
2375                 tags[0] = -1;
2376                 assertions = 0;
2377                 /* Second pass with tre_mach_empty() to get the list of
2378                    tags and parameters. */
2379                 status = tre_match_empty(stack, cat->left, tags,
2380                                          &assertions, NULL);
2381                 if (status != REG_OK)
2382                   {
2383                     xfree(tags);
2384                     return status;
2385                   }
2386                 node->firstpos =
2387                   tre_set_union(mem, cat->right->firstpos, cat->left->firstpos,
2388                                 tags, assertions);
2389                 xfree(tags);
2390                 if (!node->firstpos)
2391                   return REG_ESPACE;
2392               }
2393             else
2394               {
2395                 node->firstpos = cat->left->firstpos;
2396               }
2397
2398             /* Compute lastpos. */
2399             if (cat->right->nullable)
2400               {
2401                 /* The right side matches the empty string.  Make a first pass
2402                    with tre_match_empty() to get the number of tags and
2403                    parameters. */
2404                 status = tre_match_empty(stack, cat->right,
2405                                          NULL, NULL, &num_tags);
2406                 if (status != REG_OK)
2407                   return status;
2408                 /* Allocate arrays for the tags and parameters. */
2409                 tags = xmalloc(sizeof(int) * (num_tags + 1));
2410                 if (!tags)
2411                   return REG_ESPACE;
2412                 tags[0] = -1;
2413                 assertions = 0;
2414                 /* Second pass with tre_mach_empty() to get the list of
2415                    tags and parameters. */
2416                 status = tre_match_empty(stack, cat->right, tags,
2417                                          &assertions, NULL);
2418                 if (status != REG_OK)
2419                   {
2420                     xfree(tags);
2421                     return status;
2422                   }
2423                 node->lastpos =
2424                   tre_set_union(mem, cat->left->lastpos, cat->right->lastpos,
2425                                 tags, assertions);
2426                 xfree(tags);
2427                 if (!node->lastpos)
2428                   return REG_ESPACE;
2429               }
2430             else
2431               {
2432                 node->lastpos = cat->right->lastpos;
2433               }
2434             break;
2435           }
2436
2437         default:
2438           assert(0);
2439           break;
2440         }
2441     }
2442
2443   return REG_OK;
2444 }
2445
2446
2447 /* Adds a transition from each position in `p1' to each position in `p2'. */
2448 static reg_errcode_t
2449 tre_make_trans(tre_pos_and_tags_t *p1, tre_pos_and_tags_t *p2,
2450                tre_tnfa_transition_t *transitions,
2451                int *counts, int *offs)
2452 {
2453   tre_pos_and_tags_t *orig_p2 = p2;
2454   tre_tnfa_transition_t *trans;
2455   int i, j, k, l, dup, prev_p2_pos;
2456
2457   if (transitions != NULL)
2458     while (p1->position >= 0)
2459       {
2460         p2 = orig_p2;
2461         prev_p2_pos = -1;
2462         while (p2->position >= 0)
2463           {
2464             /* Optimization: if this position was already handled, skip it. */
2465             if (p2->position == prev_p2_pos)
2466               {
2467                 p2++;
2468                 continue;
2469               }
2470             prev_p2_pos = p2->position;
2471             /* Set `trans' to point to the next unused transition from
2472                position `p1->position'. */
2473             trans = transitions + offs[p1->position];
2474             while (trans->state != NULL)
2475               {
2476 #if 0
2477                 /* If we find a previous transition from `p1->position' to
2478                    `p2->position', it is overwritten.  This can happen only
2479                    if there are nested loops in the regexp, like in "((a)*)*".
2480                    In POSIX.2 repetition using the outer loop is always
2481                    preferred over using the inner loop.  Therefore the
2482                    transition for the inner loop is useless and can be thrown
2483                    away. */
2484                 /* XXX - The same position is used for all nodes in a bracket
2485                    expression, so this optimization cannot be used (it will
2486                    break bracket expressions) unless I figure out a way to
2487                    detect it here. */
2488                 if (trans->state_id == p2->position)
2489                   {
2490                     break;
2491                   }
2492 #endif
2493                 trans++;
2494               }
2495
2496             if (trans->state == NULL)
2497               (trans + 1)->state = NULL;
2498             /* Use the character ranges, assertions, etc. from `p1' for
2499                the transition from `p1' to `p2'. */
2500             trans->code_min = p1->code_min;
2501             trans->code_max = p1->code_max;
2502             trans->state = transitions + offs[p2->position];
2503             trans->state_id = p2->position;
2504             trans->assertions = p1->assertions | p2->assertions
2505               | (p1->class ? ASSERT_CHAR_CLASS : 0)
2506               | (p1->neg_classes != NULL ? ASSERT_CHAR_CLASS_NEG : 0);
2507             if (p1->backref >= 0)
2508               {
2509                 assert((trans->assertions & ASSERT_CHAR_CLASS) == 0);
2510                 assert(p2->backref < 0);
2511                 trans->u.backref = p1->backref;
2512                 trans->assertions |= ASSERT_BACKREF;
2513               }
2514             else
2515               trans->u.class = p1->class;
2516             if (p1->neg_classes != NULL)
2517               {
2518                 for (i = 0; p1->neg_classes[i] != (tre_ctype_t)0; i++);
2519                 trans->neg_classes =
2520                   xmalloc(sizeof(*trans->neg_classes) * (i + 1));
2521                 if (trans->neg_classes == NULL)
2522                   return REG_ESPACE;
2523                 for (i = 0; p1->neg_classes[i] != (tre_ctype_t)0; i++)
2524                   trans->neg_classes[i] = p1->neg_classes[i];
2525                 trans->neg_classes[i] = (tre_ctype_t)0;
2526               }
2527             else
2528               trans->neg_classes = NULL;
2529
2530             /* Find out how many tags this transition has. */
2531             i = 0;
2532             if (p1->tags != NULL)
2533               while(p1->tags[i] >= 0)
2534                 i++;
2535             j = 0;
2536             if (p2->tags != NULL)
2537               while(p2->tags[j] >= 0)
2538                 j++;
2539
2540             /* If we are overwriting a transition, free the old tag array. */
2541             if (trans->tags != NULL)
2542               xfree(trans->tags);
2543             trans->tags = NULL;
2544
2545             /* If there were any tags, allocate an array and fill it. */
2546             if (i + j > 0)
2547               {
2548                 trans->tags = xmalloc(sizeof(*trans->tags) * (i + j + 1));
2549                 if (!trans->tags)
2550                   return REG_ESPACE;
2551                 i = 0;
2552                 if (p1->tags != NULL)
2553                   while(p1->tags[i] >= 0)
2554                     {
2555                       trans->tags[i] = p1->tags[i];
2556                       i++;
2557                     }
2558                 l = i;
2559                 j = 0;
2560                 if (p2->tags != NULL)
2561                   while (p2->tags[j] >= 0)
2562                     {
2563                       /* Don't add duplicates. */
2564                       dup = 0;
2565                       for (k = 0; k < i; k++)
2566                         if (trans->tags[k] == p2->tags[j])
2567                           {
2568                             dup = 1;
2569                             break;
2570                           }
2571                       if (!dup)
2572                         trans->tags[l++] = p2->tags[j];
2573                       j++;
2574                     }
2575                 trans->tags[l] = -1;
2576               }
2577
2578             p2++;
2579           }
2580         p1++;
2581       }
2582   else
2583     /* Compute a maximum limit for the number of transitions leaving
2584        from each state. */
2585     while (p1->position >= 0)
2586       {
2587         p2 = orig_p2;
2588         while (p2->position >= 0)
2589           {
2590             counts[p1->position]++;
2591             p2++;
2592           }
2593         p1++;
2594       }
2595   return REG_OK;
2596 }
2597
2598 /* Converts the syntax tree to a TNFA.  All the transitions in the TNFA are
2599    labelled with one character range (there are no transitions on empty
2600    strings).  The TNFA takes O(n^2) space in the worst case, `n' is size of
2601    the regexp. */
2602 static reg_errcode_t
2603 tre_ast_to_tnfa(tre_ast_node_t *node, tre_tnfa_transition_t *transitions,
2604                 int *counts, int *offs)
2605 {
2606   tre_union_t *uni;
2607   tre_catenation_t *cat;
2608   tre_iteration_t *iter;
2609   reg_errcode_t errcode = REG_OK;
2610
2611   /* XXX - recurse using a stack!. */
2612   switch (node->type)
2613     {
2614     case LITERAL:
2615       break;
2616     case UNION:
2617       uni = (tre_union_t *)node->obj;
2618       errcode = tre_ast_to_tnfa(uni->left, transitions, counts, offs);
2619       if (errcode != REG_OK)
2620         return errcode;
2621       errcode = tre_ast_to_tnfa(uni->right, transitions, counts, offs);
2622       break;
2623
2624     case CATENATION:
2625       cat = (tre_catenation_t *)node->obj;
2626       /* Add a transition from each position in cat->left->lastpos
2627          to each position in cat->right->firstpos. */
2628       errcode = tre_make_trans(cat->left->lastpos, cat->right->firstpos,
2629                                transitions, counts, offs);
2630       if (errcode != REG_OK)
2631         return errcode;
2632       errcode = tre_ast_to_tnfa(cat->left, transitions, counts, offs);
2633       if (errcode != REG_OK)
2634         return errcode;
2635       errcode = tre_ast_to_tnfa(cat->right, transitions, counts, offs);
2636       break;
2637
2638     case ITERATION:
2639       iter = (tre_iteration_t *)node->obj;
2640       assert(iter->max == -1 || iter->max == 1);
2641
2642       if (iter->max == -1)
2643         {
2644           assert(iter->min == 0 || iter->min == 1);
2645           /* Add a transition from each last position in the iterated
2646              expression to each first position. */
2647           errcode = tre_make_trans(iter->arg->lastpos, iter->arg->firstpos,
2648                                    transitions, counts, offs);
2649           if (errcode != REG_OK)
2650             return errcode;
2651         }
2652       errcode = tre_ast_to_tnfa(iter->arg, transitions, counts, offs);
2653       break;
2654     }
2655   return errcode;
2656 }
2657
2658
2659 #define ERROR_EXIT(err)           \
2660   do                              \
2661     {                             \
2662       errcode = err;              \
2663       if (/*CONSTCOND*/1)         \
2664         goto error_exit;          \
2665     }                             \
2666  while (/*CONSTCOND*/0)
2667
2668
2669 int
2670 regcomp(regex_t *restrict preg, const char *restrict regex, int cflags)
2671 {
2672   tre_stack_t *stack;
2673   tre_ast_node_t *tree, *tmp_ast_l, *tmp_ast_r;
2674   tre_pos_and_tags_t *p;
2675   int *counts = NULL, *offs = NULL;
2676   int i, add = 0;
2677   tre_tnfa_transition_t *transitions, *initial;
2678   tre_tnfa_t *tnfa = NULL;
2679   tre_submatch_data_t *submatch_data;
2680   tre_tag_direction_t *tag_directions = NULL;
2681   reg_errcode_t errcode;
2682   tre_mem_t mem;
2683
2684   /* Parse context. */
2685   tre_parse_ctx_t parse_ctx;
2686
2687   /* Allocate a stack used throughout the compilation process for various
2688      purposes. */
2689   stack = tre_stack_new(512, 10240, 128);
2690   if (!stack)
2691     return REG_ESPACE;
2692   /* Allocate a fast memory allocator. */
2693   mem = tre_mem_new();
2694   if (!mem)
2695     {
2696       tre_stack_destroy(stack);
2697       return REG_ESPACE;
2698     }
2699
2700   /* Parse the regexp. */
2701   memset(&parse_ctx, 0, sizeof(parse_ctx));
2702   parse_ctx.mem = mem;
2703   parse_ctx.stack = stack;
2704   parse_ctx.re = regex;
2705   parse_ctx.cflags = cflags;
2706   parse_ctx.max_backref = -1;
2707   errcode = tre_parse(&parse_ctx);
2708   if (errcode != REG_OK)
2709     ERROR_EXIT(errcode);
2710   preg->re_nsub = parse_ctx.submatch_id - 1;
2711   tree = parse_ctx.n;
2712
2713 #ifdef TRE_DEBUG
2714   tre_ast_print(tree);
2715 #endif /* TRE_DEBUG */
2716
2717   /* Referring to nonexistent subexpressions is illegal. */
2718   if (parse_ctx.max_backref > (int)preg->re_nsub)
2719     ERROR_EXIT(REG_ESUBREG);
2720
2721   /* Allocate the TNFA struct. */
2722   tnfa = xcalloc(1, sizeof(tre_tnfa_t));
2723   if (tnfa == NULL)
2724     ERROR_EXIT(REG_ESPACE);
2725   tnfa->have_backrefs = parse_ctx.max_backref >= 0;
2726   tnfa->have_approx = 0;
2727   tnfa->num_submatches = parse_ctx.submatch_id;
2728
2729   /* Set up tags for submatch addressing.  If REG_NOSUB is set and the
2730      regexp does not have back references, this can be skipped. */
2731   if (tnfa->have_backrefs || !(cflags & REG_NOSUB))
2732     {
2733
2734       /* Figure out how many tags we will need. */
2735       errcode = tre_add_tags(NULL, stack, tree, tnfa);
2736       if (errcode != REG_OK)
2737         ERROR_EXIT(errcode);
2738
2739       if (tnfa->num_tags > 0)
2740         {
2741           tag_directions = xmalloc(sizeof(*tag_directions)
2742                                    * (tnfa->num_tags + 1));
2743           if (tag_directions == NULL)
2744             ERROR_EXIT(REG_ESPACE);
2745           tnfa->tag_directions = tag_directions;
2746           memset(tag_directions, -1,
2747                  sizeof(*tag_directions) * (tnfa->num_tags + 1));
2748         }
2749       tnfa->minimal_tags = xcalloc((unsigned)tnfa->num_tags * 2 + 1,
2750                                    sizeof(*tnfa->minimal_tags));
2751       if (tnfa->minimal_tags == NULL)
2752         ERROR_EXIT(REG_ESPACE);
2753
2754       submatch_data = xcalloc((unsigned)parse_ctx.submatch_id,
2755                               sizeof(*submatch_data));
2756       if (submatch_data == NULL)
2757         ERROR_EXIT(REG_ESPACE);
2758       tnfa->submatch_data = submatch_data;
2759
2760       errcode = tre_add_tags(mem, stack, tree, tnfa);
2761       if (errcode != REG_OK)
2762         ERROR_EXIT(errcode);
2763
2764     }
2765
2766   /* Expand iteration nodes. */
2767   errcode = tre_expand_ast(mem, stack, tree, &parse_ctx.position,
2768                            tag_directions);
2769   if (errcode != REG_OK)
2770     ERROR_EXIT(errcode);
2771
2772   /* Add a dummy node for the final state.
2773      XXX - For certain patterns this dummy node can be optimized away,
2774            for example "a*" or "ab*".   Figure out a simple way to detect
2775            this possibility. */
2776   tmp_ast_l = tree;
2777   tmp_ast_r = tre_ast_new_literal(mem, 0, 0, parse_ctx.position++);
2778   if (tmp_ast_r == NULL)
2779     ERROR_EXIT(REG_ESPACE);
2780
2781   tree = tre_ast_new_catenation(mem, tmp_ast_l, tmp_ast_r);
2782   if (tree == NULL)
2783     ERROR_EXIT(REG_ESPACE);
2784
2785   errcode = tre_compute_nfl(mem, stack, tree);
2786   if (errcode != REG_OK)
2787     ERROR_EXIT(errcode);
2788
2789   counts = xmalloc(sizeof(int) * parse_ctx.position);
2790   if (counts == NULL)
2791     ERROR_EXIT(REG_ESPACE);
2792
2793   offs = xmalloc(sizeof(int) * parse_ctx.position);
2794   if (offs == NULL)
2795     ERROR_EXIT(REG_ESPACE);
2796
2797   for (i = 0; i < parse_ctx.position; i++)
2798     counts[i] = 0;
2799   tre_ast_to_tnfa(tree, NULL, counts, NULL);
2800
2801   add = 0;
2802   for (i = 0; i < parse_ctx.position; i++)
2803     {
2804       offs[i] = add;
2805       add += counts[i] + 1;
2806       counts[i] = 0;
2807     }
2808   transitions = xcalloc((unsigned)add + 1, sizeof(*transitions));
2809   if (transitions == NULL)
2810     ERROR_EXIT(REG_ESPACE);
2811   tnfa->transitions = transitions;
2812   tnfa->num_transitions = add;
2813
2814   errcode = tre_ast_to_tnfa(tree, transitions, counts, offs);
2815   if (errcode != REG_OK)
2816     ERROR_EXIT(errcode);
2817
2818   tnfa->firstpos_chars = NULL;
2819
2820   p = tree->firstpos;
2821   i = 0;
2822   while (p->position >= 0)
2823     {
2824       i++;
2825       p++;
2826     }
2827
2828   initial = xcalloc((unsigned)i + 1, sizeof(tre_tnfa_transition_t));
2829   if (initial == NULL)
2830     ERROR_EXIT(REG_ESPACE);
2831   tnfa->initial = initial;
2832
2833   i = 0;
2834   for (p = tree->firstpos; p->position >= 0; p++)
2835     {
2836       initial[i].state = transitions + offs[p->position];
2837       initial[i].state_id = p->position;
2838       initial[i].tags = NULL;
2839       /* Copy the arrays p->tags, and p->params, they are allocated
2840          from a tre_mem object. */
2841       if (p->tags)
2842         {
2843           int j;
2844           for (j = 0; p->tags[j] >= 0; j++);
2845           initial[i].tags = xmalloc(sizeof(*p->tags) * (j + 1));
2846           if (!initial[i].tags)
2847             ERROR_EXIT(REG_ESPACE);
2848           memcpy(initial[i].tags, p->tags, sizeof(*p->tags) * (j + 1));
2849         }
2850       initial[i].assertions = p->assertions;
2851       i++;
2852     }
2853   initial[i].state = NULL;
2854
2855   tnfa->num_transitions = add;
2856   tnfa->final = transitions + offs[tree->lastpos[0].position];
2857   tnfa->num_states = parse_ctx.position;
2858   tnfa->cflags = cflags;
2859
2860   tre_mem_destroy(mem);
2861   tre_stack_destroy(stack);
2862   xfree(counts);
2863   xfree(offs);
2864
2865   preg->TRE_REGEX_T_FIELD = (void *)tnfa;
2866   return REG_OK;
2867
2868  error_exit:
2869   /* Free everything that was allocated and return the error code. */
2870   tre_mem_destroy(mem);
2871   if (stack != NULL)
2872     tre_stack_destroy(stack);
2873   if (counts != NULL)
2874     xfree(counts);
2875   if (offs != NULL)
2876     xfree(offs);
2877   preg->TRE_REGEX_T_FIELD = (void *)tnfa;
2878   regfree(preg);
2879   return errcode;
2880 }
2881
2882
2883
2884
2885 void
2886 regfree(regex_t *preg)
2887 {
2888   tre_tnfa_t *tnfa;
2889   unsigned int i;
2890   tre_tnfa_transition_t *trans;
2891
2892   tnfa = (void *)preg->TRE_REGEX_T_FIELD;
2893   if (!tnfa)
2894     return;
2895
2896   for (i = 0; i < tnfa->num_transitions; i++)
2897     if (tnfa->transitions[i].state)
2898       {
2899         if (tnfa->transitions[i].tags)
2900           xfree(tnfa->transitions[i].tags);
2901         if (tnfa->transitions[i].neg_classes)
2902           xfree(tnfa->transitions[i].neg_classes);
2903       }
2904   if (tnfa->transitions)
2905     xfree(tnfa->transitions);
2906
2907   if (tnfa->initial)
2908     {
2909       for (trans = tnfa->initial; trans->state; trans++)
2910         {
2911           if (trans->tags)
2912             xfree(trans->tags);
2913         }
2914       xfree(tnfa->initial);
2915     }
2916
2917   if (tnfa->submatch_data)
2918     {
2919       for (i = 0; i < tnfa->num_submatches; i++)
2920         if (tnfa->submatch_data[i].parents)
2921           xfree(tnfa->submatch_data[i].parents);
2922       xfree(tnfa->submatch_data);
2923     }
2924
2925   if (tnfa->tag_directions)
2926     xfree(tnfa->tag_directions);
2927   if (tnfa->firstpos_chars)
2928     xfree(tnfa->firstpos_chars);
2929   if (tnfa->minimal_tags)
2930     xfree(tnfa->minimal_tags);
2931   xfree(tnfa);
2932 }